Реферат: Критерии оптимальности.

Первый критерий оптимальности:Решение оптимально тогда и только тогда, когда существует решение такое, что

. (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

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

(39.1)

при условиях:

, (39.2)

, (39.3)

,; (39.4)

Всякое неотрицательное решение систем уравнений (39.2)-(39.4), определяемое матрицей, называют опорным планом ТЗ, а план при котором функция Z принимает минимальное значение — называется оптимальным планом ТЗ.

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

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

, (39.5)

то модель ТЗ называется закрытой.

Теорема:любая транспортная задача, у которой суммарный объем запасов совпадает с суммарным объемом потребностей, имеет решение. (Для доказательства теоремы необходимо показать, что линейная функция на множестве планов при заданных условиях ограничена.)

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

Введением фиктивного потребителя (если ), или фиктивного отправителя (если, любая задача приводится к закрытой модели (во всех фиктивных ячейках таблицы полагают ).

Для разрешимости задачи равенство (39.5) является необходимым и достаточным условием.

Нахождение опорных и оптимального планов ТЗ можно вести симплексным методом, но ввиду специфики ТЗ и большого ее прикладного значения разработаны специальные методы.

Нахождение опорных планов ТЗ можно осуществить одним из пяти методов: северо-западного угла, минимальной стоимости, аппроксимации Фогеля, двойного предпочтения и дельта-метода.