3.5.2. Построение оптимального плана. Метод потенциалов.

Лемма:

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

Если i-я компонента оптимального плана двойственной задачи положительна, то i-е ограничение исходной задачи удовлетворяется ее оптимальным решением, как строгое равенство.

Доказательство:

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

Для ЗЛП функция Лагранжа:

 (x, ) = (c, x) + (, b  Ax)

Тогда дифференциальные условия для этой функции:

= 0, i =:

= 0, j =:

Без доказательства.

Теорема:

Если план ТЗ является оптимальным, то ему соответствует система из m+n чисел и , удовлетворяющая условиям:

+ = для > 0

+  для = 0

Числа и называются потенциалами соответственно поставщиков и потребителей.

Доказательство:

Вместо решения исходной транспортной задачи (ЗЛП) решаем двойственную ЗЛП.

ЗЛП:

?

Ax = E , x  0

E =

Двойственная задача:

?

,   0

Т.к. в строке A^T два ненулевых (единичных) элемента (обозначим u_i=_i, v_j=_i, то получаем + 

Пусть =

=

С учетом леммы двойственную задачу надо записать в виде:

, где

+ = для > 0

+  для = 0

Теорема доказана.

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

а) Для любой занятой клетки + =

б) Для любой незанятой + 

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

Алгоритм метода потенциалов:

1. Построение системы потенциалов:

Используем условие + = для занятых клеток. Уравнений m+n-1,

неизвестных m + n. Одну компоненту обнулим (любое или ).

Для данного примера:

пусть =0,

тогда:

(для таблицы данного примера)

2. Проверка выполнения условия оптимальности для незанятых клеток.

Вычисляем характеристические разности :

= +- (см. таблицу стоимостей примера)

Если в любой незанятой клетке  0, то конец.

3. Выбор клетки, в которую необходимо послать перевозку:

Среди > 0 надо выбрать максимальную(для примера +6) .

4. Построение цикла и определение величины перераспределения груза:

Отмечаем плюсом найденную клетку. Стало m+n занятых клеток, т.е. существует цикл. Идем по циклу и расставляем плюсы и минусы, чередуя их . (см. пример)

Затем находим (по минусам , расставленным ранее). Значение записываем в незанятую клетку. Идем по циклу ,

где плюс - добавляем ,

где минус - вычитаем значение из.

Пример:

	5		-
3		1	3
	3	1	

вид таблицы примера

f = 39 ( значение функции f уменьшилось )

5. Проверка полученного опорного плана на оптимальность и переход в случае необходимости к пункту 2.

Мы завершили раздел математического программирования: