Математические методы в решении экономических задач

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

Для этого: 1) Третью строку разделим на 7, в результате получим на месте разрешающего элемента 1.

2) Третью строку умножим на 2 и из первой строки вычтем то, что получилось при умножении. Результат записываем в первую строку.

3) Третью строку домножим на 5 и из второй строки вычтем то, что получилось при умножении. Результат записываем во вторую строку.

4) Третью строку умножим на 49 и прибавим к строке F.

При пересчете у нас в столбике F, таблицы (2.2), опять оказалось отрицательное число, а это говорит о том что решение нужно продолжать.

Далее, разрешающим столбцом у нас будет Х1,т.к отрицательное число -23 находится в нем.

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

Х1 = min ; ; = 63.

Найдя число  = 63, => 2-я строка (Х4) является разрешающей. Следовательно, в базис введем Х1 вместо Х4.

Запишем все расчёты в таблицу

Таблица (2.2)

На пересечении разрешающего столбца и строки находится разрешающий элемент - это число 23/7. Производим пересчет всех коэффициентов таблицы, таким образом , чтоб на месте разрешающего элемента получить 1, а в разрешающем столбце все элементы = 0.

Для этого: 1) Третью строку разделим на  и запишем получившееся в эту же строку.

2) Из первой строки вычтем вторую, умноженную на  и записываем в первую строку.

3) Из третьей строки вычтем вторую умноженную на , результат запишем в третью строку.

4) К строке F прибавим вторую строку умноженную на 23 и запишем в строку F.

Таблица (2.3)

Ответ: из изложенного выше экономического содержания данных таблицы (2.3) следует, что на втором шаге план задачи является оптимальным. Х1* = 63; Х2* = 111. Fmаx= 7329, это значит, что общая стоимость всей произведенной продукции, а она равна 7329 рублей, является максимальной

Решение задачи двойственным методом

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

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

5Х1+2Х2 ≤ 750 Y1

Х1+7Х2 ≤ 840 Y3

F = 30Х₁ +49Х₂ => max

Целевая функция исходной задачи задаётся на максимум, а целевая функция двойственной – на минимум.

Составим матрицу для исходной задачи:

А =

Чтобы составить матрицу для двойственной задачи нужно применить транспонирование (т.е. замена строк – столбцами, а столбцов – стоками)

АТ =

Число переменных в двойственной задаче равно числу соотношений в системе (1.1) исходной задачи, т.е. равно трем.

Коэффициентами в целевой функции двойственной задачи являются свободные члены системы уравнений, т .е 750,807,840.

Целевая функция исходной задачи исследуется на максимум, а система условий содержит только уравнения. Поэтому в двойственной задаче целевая функция исследуется на минимум, а её переменные могут принимать любые значения (в том числе и отрицательные). Следовательно, для исходной задачи двойственная задача такова: умножим правые части ограничений на соответствующие переменные двойственной задачи и сложим их, получим целевую функции

Z(Y) = 750Y1 + 807Y2 + 840Y3 => min.

5Y1 + 4Y2 + Y3 ≥ 30

2Y1 + 5Y2 + 7Y3 ≥ 49

Y1 = 0

Y2 = 7

Y3 = 2

Z(Y) = 750·0 + 807·7+ 840·2 = 7329

Ответ: Z(Y) = F(Х) = 7329, Y1* = 0, Y2* = 7, Y3* = 2.

Транспортная задача линейного программирования

Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

Задача №2

Формулировка транспортной задачи

На три базы: А₁, А₂, А₃ поступил однородный груз в количествах: а₁, а₂, а₃, соответственно. Груз требуется перевезти в пять пунктов: b₁ в пункт В₁, b₂ в пункт В₂, b₃ в пункт В₃, b₄ в пункт В₄, b₅ в пункт В₅.

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

Исходные данные транспортной задачи обычно записываются в таблице:

Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения. Проверяем выполнение необходимого и достаточного условия разрешимости задачи. Находим суммарные запасы поставщиков и запросы потребителей:  400 + 370 + 380 = 1150,  250 + 200 + 290 + 260 + 150 = 1150. => задача с правильным балансом. Составляем начальное опорное решение:

Таблица (1;1)

Т.к. n + m – 1 = 3 + 5 – 1 = 7, а в нашей задаче заполненных клеток всего 6, введём дополнительное число - нуль, на пересечении U1 и V2.

Получаем решение:

X1 =  - опорное решение №1.

Вычисляем значение целевой функции на этом опорном решении F = 250·2+ 150·3 + 80·8 + 290·6 + 120·15 + 260·9 = 500 + 450 + 640 + 1740 + 1800 + 2340 = 7470.

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

Ui + Vj = Сij

Записываем систему уравнений для нахождения потенциалов:

U1 + V1 = 2,

U1 + V2 = 4,

U1 + V5 = 3,

U2 + V2 = 8,

U2 + V3 = 6,

U3 + V2 = 15,

U3 + V4 = 9

Далее одному из потенциалов задаем значение произвольно: пусть U1 = 0. Остальные потенциалы находятся однозначно:

U1 = 0,

V1 = 2, V2 = 4, V5 = 3

U2 = 8 - V2 = 4

U3 = 15 - V2 = 11

V4 = 9 - U3 = -2

V3 = 6 - U2 = 2

Проверяем опорное решение Х1 на оптимальность. С этой целью вычисляем оценки  для всех незаполненных клеток таблицы.

∆13 = U1 + V3 - С13 = 0 + 2 – 5 = - 3,

∆14 = U1 + V4 - С14 = 0 - 2 –11 = - 13,

∆21 = U2 + V1 – С21 = 4 + 2 – 12 = - 6,

∆24 = U2 + V4 – С24 = 4 - 2 – 14 = - 12,

∆25 = U2 + V5 – С25 = 4 + 3 – 11 = - 4,

∆31 = U3 + V1 – С31 = 11 + 2 – 10 = 3,

∆33 = U3 + V3 – С33 = 11 + 2 – 7 = 6,

∆35 = U3 + V5 – С35 = 11 + 3 – 18 = - 4.

Начальное опорное решение не является оптимальным, так как имеются положительные оценки.

Переходим к новому опорному решению. Находим клетку таблицы, которой соответствует наибольшая положительная оценка:

max{3, 6}=6 - для клетки (U3; V3).

Для этой клетки строим цикл.

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

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

Это перемещение производят по следующим правилам:

Каждой из клеток, связанных циклом с данной свободной клеткой приписывают определенный знак, причём свободной клетке – знак плюс, а всем остальным клеткам – поочередно знаки минус и плюс (таблица (1;1)).

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

Описанный выше переход от одного опорного плана транспортной задачи к другому называется сдвигом по циклу пересчета.

Следует отметить, что при сдвиге по циклу пересчета число занятых клеток остается неизменным, а именно остается равным n + m – 1 = 3 + 5 – 1 = 7

X2 =  - опорное решение №2. Полученный новый опорный план проверяем на оптимальность.

Вычисляем значение целевой функции на втором опорном решении:

F = 250· 2 + 0·4+ 150·3+ 200·8+ 170·6 + 120·7 + 260·9 = 500 + 0 + 450 + 1600 + 1020 + 840 + 2340 = 6750.

Далее производим проверку оптимальности опорного решения:

U1 + V1 = 2,

U1 + V2 = 4,

U1 + V5 = 3,

U2 + V2 = 8,

U2 + V3 = 6,

U3 + V4 = 9.

U1 = 0,

V1 = 2, V2 = 4, V5 = 3

U2 = 8 - V2 = 4

V3 = 6 - U2 = 2

U3 = 7 – V3 = 5

V4 = 9 - U3 = 4

Проверяем опорное решение Х2 на оптимальность. С этой целью вычисляем оценки  для всех незаполненных клеток таблицы.

∆13 = U1 + V3 - С13 = 0 + 2 – 5 = - 3,

∆14 = U1 + V4 - С14 = 0 + 4 –11 = - 7,

∆21 = U2 + V1 – С21 = 4 + 2 – 12 = - 6,

∆24 = U2 + V4 – С24 = 4 + 4 – 14 = - 6,

∆25 = U2 + V5 – С25 = 4 + 3 – 11 = - 4,

∆31 = U3 + V1 – С31 = 5 + 2 – 10 = - 3,

∆35 = U3 + V5 – С35 = 5 + 4 – 18 = - 9.

Ответ: общая минимальная стоимость перевозок равна F min = 6750ден.ед при решении

Х2 =  .

Заключение

В результате проделанной работы изучено несколько методов решения задачи линейного программирования, а именно графический, симплекс-метод (аналитический и табличный) для прямой и двойственной задачи линейного программирования, а также изучена транспортная задача.

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

Результаты работы рекомендуется использовать для успешного решения задач линейного программирования и дальнейшего изучения математического и линейного программирования.

Библиографический список

1.  Абрамов Л.M., Капустин В.Ф. Математическое программирование. ―Л., 1981.

2.  Акулич И.Л. Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986.

3.  Баумоль У. Экономическая теория и исследование операций. — М.: Прогресс, 1965.

4.  Калихман И.Л. Линейная алгебра и программирование. — М.: Высш. шк.,1967.

5.  Карасев А.И., Аксютина З.М., Савельева Т.И. Курс высшей математики для экономических вузов. Ч.II. Теория вероятностей и математическое программирование. Линейное программирование: Учеб. пособие для студентов вузов. ― М.: Высш. школа, 1982.

6.  Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. ― М.: Высш. шк., 1980.

7.  Линейное программирование: Учебно-методическое пособие. ― М.: Изд-во МГУ, 1992.

8.  Матвеев В.И., Сагитов Р.В., Шершнев В.Г. Курс линейного программирования для экономистов: Учеб. пособие. — М.: Менеджер, 1998.

9.  Муртаф Б. Современное линейное программирование. — М.: Мир, 1984.

10.  Общий курс высшей математики для экономистов :Учебник / Под ред. В.И. Ермакова. ― М.: ИНФА-М, 2002.