Лекция: Критерии оптимальности.
Первый критерий оптимальности:Решение оптимально тогда и только тогда, когда существует решение такое, что
. (38.1)
Второй критерий оптимальности: чтобы допустимые решения , — пары двойственных задач (I) и (II) были оптимальны, необходимо и достаточно, чтобы выполнялись соотношения:
1) если, то; (38.2)
2) если, то; (38.3)
3) если, то; (38.4)
4) если, то. (38.5)
Пример: используя теоремы двойственности, решить двойственную задачу, если известно решение прямой задачи.
, (38.6)
,, .
Пусть решение задачи найдено одним из стандартных методов:, .
Построим двойственную задачу:
, (38.7)
,, .
По первой теореме двойственности задача разрешима, причем
.
Найдем оптимальный план задачи, используя вторую теорему двойственности. Подставим координаты вектора в ограничения задачи (38.6).
Получим
Следовательно, неравенство должно выполняться как равенство, то есть .
Далее, так как,, то
, .
Получаем систему линейных уравнений:
,,
Планы и, в силу второй теоремы двойственности, являются оптимальными в задачах (38.6) и (38.7) соответственно.
Транспортная задача. Закрытая и открытая модели.
Частным случаем задачи линейного программирования является транспортная задача (ТЗ).
ТЗ в общем виде состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления А1 , А2 , ..., Аm в n пунктов назначения B1 , B2 , ..., Bn. В качестве критерия оптимальности можно взять минимальную стоимость перевозок всего груза, либо минимальное время его доставки.
Рассмотрим задачу с первым критерием, обозначив через — тарифы перевозок единицы груза из i-го пункта отправления в j-й пункт назначения, через ai — запасы груза в пункте Аi, через bj — потребности в грузе пункта Bj , — количество единиц груза, перевозимого из i-го пункта в j-й пункт.
Составим математическую модель задачи. Так как от i-гo поставщика к j-му потребителю запланировано к перевозке единиц груза.
Таблица 39.1
Поставщики | Потребители | Запасы | |||
B1 | B2 | … | Bn | ||
А1 | C11 X11 | C12 X12 | … | C1n X1n | a1 |
А2 | C21 X21 | C22 X22 | … | C2n X2n | a2 |
… | … | … | … | … | … |
Аm | Cm1 Xm1 | Cm2 Xm2 | … | Cmn Xmn | am |
Потребности | b1 | b2 | … | bn | ∑ai=∑bj |
Соответственно математическая постановка задачи состоит в определении минимума целевой функции
(39.1)
при условиях:
, (39.2)
, (39.3)
,; (39.4)
Всякое неотрицательное решение систем уравнений (39.2)-(39.4), определяемое матрицей, называют опорным планом ТЗ, а план при котором функция Z принимает минимальное значение — называется оптимальным планом ТЗ.
Все данные, а затем и опорный план, удобно занести в распределительную таблицу.
Определение. Если общее количество груза в пунктах отправления и общая потребность в нем в пунктах назначения совпадают, т.е.
, (39.5)
то модель ТЗ называется закрытой.
Теорема:любая транспортная задача, у которой суммарный объем запасов совпадает с суммарным объемом потребностей, имеет решение. (Для доказательства теоремы необходимо показать, что линейная функция на множестве планов при заданных условиях ограничена.)
Определение. Если общее количество груза в пунктах отправления и общая потребность в нем в пунктах назначения не совпадают ТЗ называется открытой.
Введением фиктивного потребителя (если ), или фиктивного отправителя (если, любая задача приводится к закрытой модели (во всех фиктивных ячейках таблицы полагают ).
Для разрешимости задачи равенство (39.5) является необходимым и достаточным условием.
Нахождение опорных и оптимального планов ТЗ можно вести симплексным методом, но ввиду специфики ТЗ и большого ее прикладного значения разработаны специальные методы.
Нахождение опорных планов ТЗ можно осуществить одним из пяти методов: северо-западного угла, минимальной стоимости, аппроксимации Фогеля, двойного предпочтения и дельта-метода.