равна величине минимального разреза

Решение двойственной ЗЛП к ЗЛП нахождения максимального потока

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

Математическая модель задачи имеет вид:

(19) d_kc_k à min

(20) p_i - p_j + d_k >= 0, k = 1,2.. m,

(21) ps = 0, p _t =1, p_i - не ограничены при i≠s, i≠t,

(22) d_k >= 0.

Совпадение значений целевых функций прямой и двойственной задач линей-

ного программирования подтверждает правильность решения.

ПОРЯДОК РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ НА ЭВМ

Расчет моделей осуществляется на ЭВМ в различных программных средах (MS Excel, Matlab и др.). Рассмотрим решение задач линейного программирова-ния в MS Excel, что вполне доступно и непрограммирующему пользователю.

В качестве типичного примера рассмотрим задачу о производственной

мощности предприятия линейного программирования.

Пусть цех малого предприятия должен изготовить 100 изделий 3-х типов. Каждого изделия нужно сделать не менее 20 штук. На изделия уходит

соответственно 4, 3.4 и 2 кг металла при его общем запасе 340 кг, а также по

4.75, 11 и 2 кг пластмассы при ее общем запасе 700 кг. Сколько изделий каждого типа Х1, Х2 и Х3 надо выпустить для получения максимального объема выпуска в денежном выражении, если цена изделий составляет по калькуляции 4, 3 и 2 гривны?

Математическая модель задачи:

Z = 4*X1 + 3*X2 + 2*X3 à max

X1 >= 20,

X2 >= 20,

X3 >= 20,

4*X1 + 3.4*X2 + 2*X3 <=340,

4.75*X1 + 11*X2 + 2*X3 <=700,

X1 + X2 + X3 =100,

X1, X2, X3 >= 0.

При построении двойственной задачи каждому общему ограничению

прямой задачи ставим в соответствие двойственную переменную, всего 6 пе-

pеменных, которые мы обозначим y1,y2,y3,y4,y5,y6. Из столбцов прямой задачи образуем ограничения двойственной.Обратим внимание на то,что огра-

ничение, соответствующее переменной у6 имеет тип равенства, а, значит, на

эту переменную не накладывается условие отрицательности.

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

Z* = - 20*y1 – 20*y2 – 20*y3 + 340*y4 + 700*y5 +100*y6 àmin

-y1 + 4*y4 + 4.75*y5 + y6 >= 4,

-y2 +3.4* y4 + 11*y5 + y6 >= 3,

-y3 + 2*y4 + 2*y5 + y6 >= 2,

y1, y2,y3,y4,y5 >= 0.

Оформление задачи в MS EXCEL продемонстрировано выше. Ячейки b16:d16

вначале содержат нули. Значения в этих ячейках изменяются в результате работы программы ПОИСК РЕШЕНИЯ. Ограничения в виде формул записаны

в столбце I. Мы показали заполнение таблицы в режиме отображения формул.

При оформлении работы устанавливать этот режим совсем не обязательно.

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

В меню параметры потребуем линейности модели и неотрицательности всех

переменных задачи

После этого нажимаем «ОК» и «Выполнить».

В результате получим следующую таблицу

Конечно решение нужно сохранить, то есть нажать «ОК».

Дадим некоторые пояснения к найденому решению. Количество изделий в оптимальном плане X1 = 56, X2 = 20, X3 = 24. При таком плане предприятие

получает максимальную прибыль - 332 гривны.Сравнение столбцов G, I

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

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

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

РЕШЕНИЕ ДВОЙСТВЕННОЙ ЗАДАЧИ

После пункта «Параметры»

Наконец, нажимая «ОК» и «Выполнить»

Получаем решение двойственной задачи

КОНТРОЛЬНЫЕ ЗАДАНИЯ

Задание 1. Для производства 3-х видов изделий А, В, С используется сырье

типа Ι, ΙΙ и ΙΙΙ, причем закупки сырья типа Ι и ΙΙΙ ограничены возможностя-

ми поставщиков. В таблице приведены нормы затрат сырья, цены на сырье

и на изделия, а также ограничения по закупке сырья.Требуется определить

план производства продукции с целью максимизации прибыли.

1. Записать математическую модель задачи.

2. Решить задачу, используя ЭТ EXCEL.

3. Записать математическую модель двойственной задачи.

4. Решить двойственную задачу, используя ЭТ EXCEL.

5. Сравнить значения целевых функций прямой и двойственной задач.

6. Проверить, что для положительных двойственных оценок соответствующие

ограничения прямой задачи выполняются как строгие равенства при под –

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

РЕШЕНИЕ ЗАДАЧИ О КРАТЧАЙШЕМ ПУТИ

Дана сеть

Данные введем в таблицу EXCEL:

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

В ячейки столбца С записываем веса соответствующих дуг.Столбец D отводим

под переменные задачи. Эти переменные будут в решении принимать значения 1 или 0 в зависимости от того войдет дуга вкратчайшую цепь или нет. Все значения переменных вначале равны нулю. Столбец Е – столбец ну-

мерации вершин.

Ячейка F6 –целевая, а в ячейки F1: F5 запишем формулы:

для строки к запишем сумму таких Ds, которые в своей строке и столбце А

содержат вершину Хк. Полагаем G1 = <1>, а в ячейки G2: G5 запишем

формулы: для строки к запишем сумму таких Ds, которые в своей строке и столбце В содержат переменную Хк.

Заметим, что при оформлении таблицы вместо формул будут появляться некоторые числа и в результате столбцы F и G будут выглядеть иначе, чем

на рисунке.

Вызываем программу ПОИСК РЕШЕНИЯ и заносим в нее данные так как ука

зано в таблице

В меню параметры нужно установить флажки

Затем нажимаем «ОК» и «Выполнить» Получаем

Дальше «ОК»

В ячейке F6 – длина искомого пути. Дуги искомого пути восстановим по столбцу D.

ЗАДАЧА. ДЕРЕВО КРАТЧАЙШИХ ПУТЕЙ.

Задана сеть

Найти дерево кратчайших путей.
Данные введем в таблицу EXCEL:

Столбцы А, B, C, D, E оформляются так же, как и в задаче о кратчайшем

пути в графе.

Ячейка F8 –целевая, в ячейку F7 записываем сумму весов всех

дуг (см. рисунок),

в F1 помещаем сумму тех Ds, которые в своей строке и столбце А содержат вершину Х1,

в F2:F6 помещаем сумму тех Ds, которые в своей строке и столбце В содержат вершину Хк, к – номер записываемой формулы (см. столбец Е)

Вызываем программу ПОИСК РЕШЕНИЯ и заносим в нее данные так как указано в таблице

Обратим внимание на логику алгоритма: выбираем ровно n-1 = 6-1=5 дуг графа. Это связано с тем, чтобы в полученом орграфе никакие две вершины

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

В каждую вершину, кроме источника, заходит только одна дуга.

В таблице «Параметры» устанавливаем птичку в разделе «линейная модель». После запуска программы и сохранения результата получаем:

Сумма всех дуг сети равна 10 ед.Само ордерево имеет вид:

РЕШЕНИЕ ЗАДАЧИ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНОГО ПОТОКА

Дана сеть

В таблице EXCEL располагаем данные о дугах графа в столбцах А, В

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

В ячейке D1 - цель задачи.

В ячейках Е - нумерация вершин без источника и стока.

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

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

Покажем полученное решение на нашем графе. Легко просматривается условие сохранения потока в каждой вершине.Из вершины 1 исходит 13 ед.

Потока и в вершину 11 поступает 13 ед. потока.

Приведенное решение имеет такой недостаток. При значительном количестве

ребер пространство рабочего листа используется неэкономно.Мы покажем как

можно преодолеть этот недостаток. Рабочий лист заполняется следующим образом

Данные задачи содержатся в столбцах A, B, C, D, E. Столбцы F, G, H, I отво-

дятся под переменные, столбец J содержит формулы – условия сохранения по

тока. Покажем заполнение подпрограммы ПОИСК РЕШЕНИЯ и результат расче

та.

В «Параметры» отметим «Модель линейная» и «Неотрицательные решения»

После запуска получаем

Полученная таблица полностью содержит решение задачи.

Например, для дуг, исходящих из вершины 8 получим:

f[8, 9] =0, f[8, 11] = 5.

Значение целевой функции – 13 ед.

Правда, потоки несколько различаются.Но это вполне естественно. Решение

задачи не единственно.Более того, запустив программу при уже полученном

решении еще раз мы можем получить новое решение задачи.

РЕШЕНИЕ ЗАДАЧИ О МАКСИМАЛЬНОМ ПОТОКЕ В СИСТЕМЕ MAPLE