Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Первый критерий оптимальности: Решение оптимально тогда и только тогда, когда существует решение такое, что
. (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) является необходимым и достаточным условием.
Нахождение опорных и оптимального планов ТЗ можно вести симплексным методом, но ввиду специфики ТЗ и большого ее прикладного значения разработаны специальные методы.
Нахождение опорных планов ТЗ можно осуществить одним из пяти методов: северо-западного угла, минимальной стоимости, аппроксимации Фогеля, двойного предпочтения и дельта-метода.
Дата публикования: 2015-01-26; Прочитано: 637 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!