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

3*4 + 2 * 1 = 14

В результате получили, что  для минимизации стоимости используемых ресурсов необходимо, чтобы стоимость  сырья S1 и S2 были соответственно равны 4 и 1 ден.ед. При этом значение целевой функции будет равно 43 ед.

1-ое, 2-ое и 4-е ограничения выполняются как равенство. Это означает, что 1-й, 2-й и 4-й виды ресурсов экономически выгодно использовать, однако оптимальным планом прямой задачи предусмотрено использование только ресурсов х₁ и х₂ (x₁ , х₂ >0).

3- е ограничение выполняется  как  строгое неравенство, т.е. ресурс 3-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x₃ = 0. Сюда же добавим и 4-й ресурс, т.к.  х₄ = 0.

Величина двойственной оценки показывает, на сколько возрастает значение целевой функции при увеличении дефицитного ресурса на единицу.

Для нахождения х₁ и х₂ решим систему уравнений:

 

                                     6x₁ + x₂ + 6x₃ + 3x₄ = 9                                         (51)

                                   3x₁ + x₂ + x₃ + 2x₄ = 7

 

Т.к. х₃ и х₄ равны 0, то система будет выглядеть следующим образом:

 

                                     6x₁ + x₂ = 9                                                            (52)

                                   3x₁ + x₂ = 7

 

                                     x₂ = 9 – 6х₁                                                            (53)

                                   3 x₁ + 9 - 6x₁ = 7

 

                                     x₁ = 0,67                                                                (54)

                                   x₂  = 5

 

Оптимальный план прямой задачи (0,67;5;0;0), а значение целевой функции равно F(х) = 27 * 0,67 + 5 * 5 + 10 * 0 + 14 * 0 = 43 ед.

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

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

В нашей задаче х₁ = 0,67 > 0 и х₂ = 5 > 0, поэтому первое и второе ограничения двойственной задачи обращаются в уравнения, решая которые найдем y₁и  y₂   .

 

                                            6y₁ +  3y₂ = 27                                              (55)

                                               y₁+  y₂   = 5      

 

Решив систему уравнений, получили, что y₁ = 4, а y₂ = 1.

Проверим выполнение первой теоремы двойственности: Z(y) = 9 * 4 + 7 * 1 = 43 и F(x) = 43.

Первая теорема двойственности выполняется, следовательно, найденные планы оптимальны.

 

 

6 Транспортная задача и её решение методом потенциалов 

 

Классическая  транспортная задача ЛП формулируется  следующим образом. Имеется m пунктов производства (поставщиков) и n пунктов потребления (потребителей) однородного продукта. Заданы величины:

a_i - объем производства (запас) i-го поставщика, i=1, m;

b_j - объем потребления   (спрос) j-го потребителя, j=1, n;

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

Требуется составить такой план перевозок, при котором спрос всех потребителей был бы выполнен и при этом общая стоимость всех перевозок была бы минимальна.

Математическая  модель транспортной задачи имеет вид 

 

                                                                                     (56)

 

                                              , при i = 1, m                                 (57)

                                                  , при j = 1, n                                    (58)

                                                       x_ij ≥ 0                                                             (59)

 

Транспортная  задача, в которой суммарные запасы и суммарные потребности совпадают, называется закрытой моделью; в противном случае - открытой. Открытая модель решается приведением к закрытой.

В случае, когда  суммарные запасы превышают суммарные  потребности, т.е.

                                                           >                                      (60)

                                               

вводится  фиктивный n+1 потребитель, потребности  которого

 

                                                         b_n+1 = -                                   (61)

 

В случае, когда суммарные потребности превышают суммарные запасы,  т.е.

                                                           <                                      (62)

 

вводится  фиктивный m+1 поставщик, запасы которого

 

                                                         a_m+1 = -                                  (63)

 

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

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

Основные свойство транспортной задачи

Математические  модели любых транспортных задач  ЛП обладают общими чертами, а именно,

1) коэффициенты целевой функции неотрицательны (стоимости перевозок не могут быть отрицательными величинами);

2) коэффициенты  правых частей ограничений неотрицательны (запасы и потребности продукта);

3) коэффициенты  в ограничениях принимают только  два значения, это нули и единицы. 

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

а) Базисное решение закрытой модели транспортной задачи содержит m+n-1 базисных компонент.

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

б) Оптимальный план закрытой модели транспортной задачи существует всегда.

Так как транспортная задача является задачей линейного  программирования, то её можно решать симплекс-методом, но в силу своей  особенности её можно решить гораздо  проще.

Условия задачи удобно располагать  в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза х_ij≥0, а в маленькие клетки - соответствующие тарифы Cij (рисунок 3).

 

Рисунок 3 – Запись транспортной задачи

 

Затем решение задачи разбивается на два этапа:

- Определение опорного плана

- Нахождение оптимального решения, путем последовательных операций

Найдем в начале допустимое (опорное) решение транспортной задачи. Это решение можно находить, используя метод «северо-западного угла» или метод «минимального элемента».

Метод северо-западного  угла (диагональный). Сущность способа заключается в том, что на каждом шаге заполняется левая верхняя клетка (северо-западная) оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы а_i и не удовлетворятся все потребности b_j. В заключении проверяют, что найденные компоненты плана х_ij удовлетворяют горизонтальным и вертикальным уравнениям.

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

Для определения оптимального плана используем метод потенциалов.

Соотношения (60) и (62) определяют систему из m+n-1 линейных уравнений с m+n известными, имеющую бесчисленное множество решений; для её определённости одному неизвестному придают любое число (обычно альфа равное 0), тогда все остальные неизвестные определяются однозначно.

Критерий оптимальности.

Если известны потенциалы решения x₀ транспортной задачи и для всех незаполненных ячеек выполняются условия a_i + b_j ≤ c_ij, то x₀ является оптимальным планом транспортной задачи.

Если план не оптимален, то необходимо перейти к следующему плану (таблице) так, чтобы транспортные расходы не увеличивались.

Цикл перерасчёта таблицы - это последовательность ячеек, удовлетворяющая условиям:

1. одна ячейка пустая, все остальные занятые;
2. любые две соседние ячейки находятся в одной строке или в одном столбце;
3. никакие три соседние ячейки не могут быть в одной строке или в одном столбце.

Пустой ячейке присваивают знак + , остальным - поочерёдно знаки - и + .

Для перераспределения  плана перевозок с помощью  цикла перерасчёта сначала находят  незаполненную ячейку (r, s), в которой a_r + b_s >c_rs и строят соответствующий цикл; затем в минусовых клетках находят число Далее составляют новую таблицу по следующему правилу:

1. В плюсовых клетках добавляем Х;
2. Из минусовых клеток вычитаем Х;
3. Все остальные клетки вне цикла остаются без изменения.

Получим новую таблицу, дающую новое решение Х, такое, что F(X1)≤F(X0); оно снова проверяется на оптимальность через конечное число шагов, обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует.

Приведем пример транспортной задачи.

Определим оптимальный  план для следующей транспортной задачи.

 

Таблица 7 – Исходные данные

Мощность поставщиков	Мощность потребителей
	136	136	102	136
272	5	4	3	4
238	3	2	5	5
102	1	6	3	2

 

Просуммировав общую  мощность поставщиков и потребителей видим, что мощность поставщиков  превосходит потребности потребителей на 102 ед. Поэтому вводим фиктивного потребителя с мощностью 102 ед. Тарифы на доставку груза равны 0 (таблица 8).

 

Таблица 8 – Исходные данные с добавлением фиктивного поставщика

Мощность поставщиков	Мощность потребителей
	136	136	102	136	102
272	5	4	3	4	0
238	3	2	5	5	0
102	1	6	3	2	0

 

В качестве опорного плана  возьмем план, полученный с помощью  метода «минимального элемента». Рассчитаем потенциалы a_i и b_j  найдем сумму соответствующих потенциалов для каждой свободной ячейки и пересчитаем тарифы (стоимости) для каждой свободной ячейки. (таблица 9).

 

Таблица 9 – Определение опорного плана