MоP

2 Ходыкин В.Ф., Преображенский А.А. Сборник задач по математическому программированию

________________________________________________________________________________________________

Данный сборник предназначен для студентов и преподавателей вузов, изучающих и преподающих методы решения экстремальных задач. Авторы сборника разрешают бесплатное его использование на занятиях и для самостоятельного изучения. Запрещается публикация сборника в целом и любых его частей в любом виде. Предполагается издание сборника контрольных работ по всем темам сборника. Контрольные работы состоят из простых, в вычислительном плане, задач, а так же ответов на все задачи. Условия приобретения будут высланы в ответе на письмо по адресу: khodykinvf@mail.ru .

@ Ходыкин В,Ф,, Преображенский А,А,, 2002

____________________________________________________________________________________________

Введение

Успешная реализация достижений научно-технического прогресса тесно связана с использованием математических методов и средств вычислительной техники при решении задач из различных областей человеческой деятельности. Большое значение приобретает использование указанных методов и средств при решении экономических задач. Для эффективного функционирования экономических объектов необходимо установить оптимальное управление во всех структурных подразделениях, которое позволяет рационально использовать трудовые и производственные ресурсы.

Многие экономические процессы можно описать с помощью математических соотношений, в виде математических моделей. С использованием математических моделей можно определить такие значения неизвестных параметров экономической системы, при которых некоторая цель принимала бы экстремальные значения. Например, необходимо определить суточный план производства продукции различного вида, при котором предприятие получило бы максимальную прибыль.

Математическое программирование – это раздел прикладной матема-

тики, который разрабатывает теоретические основы и методы решения экстремальных задач.

Для решения задач математического программирования сложно использовать классические методы нахождения экстремума, так как в таких задачах целевая функция достигает своего экстремального значения на границе области допустимых значений неизвестных переменных. Полный перебор граничных точек во многих задачах невозможен из-за их бесконечного количества. Но даже если допустимых точек конечное число, полный перебор нерационален.

К математическому программированию относятся ряд разделов, основными из которых являются следующие разделы.

4 Ходыкин В.Ф., Преображенский А.А. Сборник задач по математическому программированию

________________________________________________________________________________________________

1.Линейное программирование. К данному разделу относятся задачи, в которых целевая функция и ограничения задачи являются линейными.

2.Нелинейное программирование. Данный раздел изучает задачи, в которых целевая функция и (или) ограничения могут быть нелинейными.

3.Динамическое программирование. В этом разделе изучаются задачи, в

которых процесс решения можно разбить на отдельные этапы.

4.Целочисленное программирование. К данному разделу относятся зада-

чи, в которых неизвестные переменные могут принимать только целочисленные значения.

5.Стохастическое программирование. Данный раздел изучает задачи, в

которых содержатся случайные величины в целевой функции и (или) в ограничениях.

6.Параметрическое программирование. В этом разделе рассматриваются задачи, в которых коэффициенты при неизвестных переменных в целевой функции и (или) в ограничениях зависят от некоторых параметров.

7.Дробно-линейное программирование. К данному разделу относятся оп-

тимизационные задачи, в которых целевая функция представляет собой отношение двух линейных функций, а ограничения, определяющие область возможных изменений переменных, являются линейными.

______________________________________________________________________________________________

Тема 1. Математическое моделирование экономических задач

При изучении сложных процессов, явлений, в том числе и экономических, очень часто применяется моделирование. Суть его состоит в том, что изучаемое явление воспроизводится в экспериментальных условиях с помощью модели в другом масштабе. Модель – это специально создаваемый объект, на котором воспроизводятся вполне определённые характеристики исследуемого объекта с целью его изучения, а моделирование – вполне определённое конкретное отображение рассматриваемых характеристик изучаемого объекта в целях его исследования.

Математическое моделирование является наиболее совершенным и вместе с тем эффективным методом моделирования. Именно в этом случае применяются мощные средства математического анализа, так как по своей природе математические методы не могут прилагаться непосредственно к действительности, а только к математическим моделям. Результаты исследования такой модели будут иметь практический интерес, если сама модель достаточно адекватна рассматриваемому явлению, то есть достаточно хорошо отображает реальную ситуацию.

1.1. Этапы принятия решений

Для принятия оптимальных управленческих решений необходимо выполнить следующие этапы.

I.Изучить исследуемый экономический объект.

II.Сформулировать экономическую постановку задачи.

III.Построить математическую модель задачи на основании экономической постановки.

IV. Выбрать методы решения данной задачи.

V.Выбрать или разработать программное обеспечение для решения

данной задачи.

VI. Решить поставленную задачу.

VII. Провести анализ полученных результатов.

6 Ходыкин В.Ф., Преображенский А.А. Сборник задач по математическому программированию

________________________________________________________________________________________________

Если полученные результаты удовлетворяют всем требованиям, то они используются в процессе принятия решений. В противном случае выполняется необходимая корректировка экономической постановки задачи, и процесс принятия решений продолжается с третьего этапа.

1.2. Построение математических моделей экономических задач

Из содержания экономической постановки задачи определяются неизвестные переменные, значения которых необходимо определить в процессе решения задачи.

Неизвестные переменные обозначаются латинскими буквами и могут иметь несколько индексов: xi, xij, yk. Например, xij – объём перевезенной про-

дукции от i-го поставщика к j-му потребителю.

Математическая модель задачи состоит из следующих элементов.

1.Целевая функция (критерий оптимальности). Данную функцию будем обозначать через z. Она должна количественно отражать значение цели в зависимости от значений неизвестных переменных. Целевая функция может быть на нахождение максимального значения (прибыль предприятия) или минимального значения (себестоимость, затраты).

2.Ограничения задачи. В реальной экономической системе существуют ограничения, например, на объём используемых ресурсов, которые должны быть учтены при построении математической модели. Ограничения должны быть записаны в виде математических соотношений (уравнений или неравенств).

3.Условия неотрицательности переменных. Неизвестные переменные за-

дачи отражают некоторые реальные параметры экономической системы, которые, как правило, не могут принимать отрицательных значений, поэтому соответствующие неизвестные переменные должны быть положительными или нулевыми.

Если целевая функция и ограничения задачи линейные, то задача называ-

ется задачей линейного программирования (ЗЛП).

______________________________________________________________________________________________

Пример задачи линейного программирования:

1.3. Примеры построения моделей экономических задач

Качество разрабатываемых моделей в значительной мере определяется опытом, интуицией, а также творческими способностями каждого исследователя. Невозможно дать готовые рецепты, как строить математическую модель в той или иной конкретной ситуации. Тем не менее, анализ накопленного опыта позволяет выявить рациональные приёмы, которые облегчают и рационализируют процесс построения моделей. Рассмотрим их на примерах построения математических моделейнаиболеераспространенныхтиповоптимизационныхзадач.

Модель1. Задачанахожденияоптимальногопланавыпускапродукции

Экономическая постановка.

Предприятие производит n видов продукции с использованием m видов ресурсов. Для производства единицы продукции используется строго определённое количество ресурсов того или иного вида. Ресурсы каждого вида на предприятии ограничены. Предприятие получает определённую прибыль от реализации единицы продукции. Необходимо найти такой план производства продукции, при котором предприятие получит максимальную общую прибыль.

Математическая постановка.

Введём обозначения заданных параметров:

j – индекс вида продукции, j = 1,n; i – индекс вида ресурсов, i = 1,m;

аij – затратыресурсовi-говиданапроизводствоединицыпродукцииj-говида; Аi – заданное ограничение на имеющийся объём ресурсов i-го вида;

Рj – прибыль, получаемая от реализации единицы продукции j-го вида.

8 Ходыкин В.Ф., Преображенский А.А. Сборник задач по математическому программированию

________________________________________________________________________________________________

Введём неизвестные переменные:

xj – объём продукции j–го вида, который планируется произвести.

В терминах введённых обозначений данная задача запишется следующим образом:

Модель 2. Задача составления рациона

Экономическая постановка.

В некотором фермерском хозяйстве производится откорм животных. Для откорма используется n видов кормов, содержащих m видов питательных веществ. Известно содержание питательных веществ (кальций, фосфор и др.) в единице корма каждого вида. Для полноценного питания животных необходимо потребление питательных веществ не меньше заданных количеств. Известна стоимость единицы каждого корма. Необходимо определить рацион кормления животных, при котором общие затраты на откорм будут минимальными.

Математическая постановка.

Введём обозначения заданных параметров: j – индекс вида кормов, j =1, n ;

i – индекс вида питательных веществ, i =1, m ;

аij – содержание i−го питательного вещества в единице корма j-го вида; Аi – необходимое суточное потребление питательного вещества i–го вида; cj – стоимость единицы кормов j-го вида.

Введём неизвестные переменные:

хj – планируемый суточный объём кормления животных j-м видом корма. В терминах введённых обозначений данная задача запишется следующим

образом:

______________________________________________________________________________________________

Модель 3.Транспортная задача

Экономическая постановка.

Имеется m поставщиков и n потребителей однородной продукции. Известны удельные затраты на доставку единицы продукции от каждого поставщика каждому потребителю. Запасы продукции у поставщиков ограничены. Известны также потребности в продукции каждого потребителя. Необходимо определить такой план перевозки продукции от поставщиков к потребителям, при котором общие затраты на перевозку будут минимальными.

Математическая постановка.

Введём обозначения заданных параметров: j – индекс потребителей, j =1,n ;

i – индекс поставщиков, i =1,m ;

Аi – объём имеющейся продукции i-го поставщика; Вj – объём потребности в продукции j-го потребителя;

cij – удельные затраты на перевозку единицы продукции от i-го поставщика j-му потребителю.

Введём неизвестные переменные:

хij – планируемый объём перевозки продукции от i-го поставщика j-му потребителю.

В терминах введённых обозначений данная задача запишется следующим образом.

z = c11x11 + c12x12 +…+ c1nx1n + c21x21 +…+ cm(n-1)xm (n-1) + cmnxmn → min; (1)

10 Ходыкин В.Ф., Преображенский А.А. Сборник задач по математическому программированию

________________________________________________________________________________________________

Ограничения задачи.

I. От каждого поставщика можно вывести объём продукции не более

xm1 + xm2 +…+ xmn ≤ Am.

II. Потребность каждого потребителя в продукции должна быть удовле-

Математическую модель часто удобно записывать в свёрнутом виде. Например, математическая модель транспортной задачи запишется следующим

Модель 4. Задача о назначениях

Экономическая постановка.

Имеются n видов работ и n исполнителей. Каждый из исполнителей может выполнить любую, но только одну работу. Задана эффективность выполнения каждой работы, каждым исполнителем. Необходимо закрепить исполнителей за работами такимобразом, чтобыобщаяэффективностьвыполненияработбыламаксимальной.