18. Итерация. Задача о диете.

Пусть теперь – двойственный базисный план и не выполняются ни (критерий оптимальности, ), ни (достаточное условие пустоты . Если , то ). Будем строить по (29), (30) и подберем наибольшим, при котором является копланом, а планом задачи. Из (27) вытекает, что искомое находится из соотношения (29) Выберем в (29), (30) , положим и докажем, что с – базисный коплан (т.е. с – новый двойственный базисный план). Для этого достаточно доказать, что не вырождена ( ) и . Невырожденность следует из § 1 (5 .Следствие), так как . Имеем:

.

Итак, построен новый двойственный базисный план . При этом двойственная целевая функция уменьшилась на . Переход называется двойственной симплекс-итерацией, а метод решения задачи (1), использующий проверку условий (26), (32) и итерацию называется двойственным симплекс-методом. Для него можно построить алгоритм обратной матрицы, подобный 1.2.6.

19. Транспортная задача. Условие общего баланса. Условия дефицита и перепроизводства.

Транспортная задача – одна из самых распространённых на практике. Имеется: – количество пунктов поставок (либо хранения) некоторой однотипной продукции, – объёмы поставок ; – количество пунктов потребления этой продукции с известными объёмами . Продукцию можно перевозить из любого пункта поставок в любой пункт потребления, – транспортные издержки на перевозку единицы продукции из -го пункта в -ый, , . Требуется организовать перевозку продукции так, чтобы: 1) вся продукция из пунктов поставок была вывезена; 2) запросы в пунктах потребления были удовлетворены полностью; 3) суммарные транспортные издержки были минимальны.

Обозначим – количество продукции, перевозимое из -го пункта в -ый, , . Математическая модель транспортной задачи:

(транспортные издержки) (1)

(вывоз) (2)

(поставки) (3)

(кол-во продукции) (4)

Теорема 1. Для того чтобы транспортная задача (1)-(4) имела непустое множество планов необходимо и достаточно, чтобы общий объём поставок равнялся общему объёму потребления: . (5)

Следствие. Условие (5) является необходимым и достаточным и для существования оптимального плана (1)-(4).

Действительно. Множество планов транспортной задачи замкнуто и ограничено сверху, следовательно (по теореме Вейерштрасса) не пустота эквивалентна достижимости нижней границы для (1) на нём.

Если условие (5) не выполняется, то возможны два случая:

а) – условие дефицита.

б) – условие избытка.

20. Особенности. Транспортная задача. Лемма 1. Следствия.

Особенности транспортной задачи. Если умножить целевую функцию транспортной задачи на -1, то приходим к задаче линейного программирования в канонической форме. Однако решать её симплекс-методом неудобно из-за большого числа переменных и вида матрицы условий . Действительно, если записывать план в виде , то матрица размерности и вектор будут иметь вид:

(6)

Транспортная задача – одна из самых распространённых на практике. Имеется: – количество пунктов поставок (либо хранения) некоторой однотипной продукции, – объёмы поставок ; – количество пунктов потребления этой продукции с известными объёмами . Продукцию можно перевозить из любого пункта поставок в любой пункт потребления, – транспортные издержки на перевозку единицы продукции из -го пункта в -ый, , . Требуется организовать перевозку продукции так, чтобы: 1) вся продукция из пунктов поставок была вывезена; 2) запросы в пунктах потребления были удовлетворены полностью; 3) суммарные транспортные издержки были минимальны.

Обозначим – количество продукции, перевозимое из -го пункта в -ый, , . Математическая модель транспортной задачи:

(транспортные издержки) (1)

(вывоз) (2)

(поставки) (3)

(кол-во продукции) (4)

Лемма 1. Ранг матрицы (число линейно независимых строк и столбцов) равен : .

Следствие. Основные ограничения (2), (3) транспортной задачи зависимы. Одно из них (любое) есть следствие остальных. Базисный план задачи должен содержать базисных компонент.

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

b₁ b₂ ... b_n

c11 x11	c21 x21	… …	c1n x1n
c21 x21	c22 x22	… …	c2n x2n
… …	… …	… …	… …
cm1 xm1	cm2 xm2	… …	cmn xmn

a₁

a₂

…

a_m

Множество клеток транспортной таблицы будем обозначать , – клетка, стоящая в -ой строке и в -ом столбце и соответствует перевозке из -го пункта поставок в -ый пункт потребления.

Определение. Цепью транспортной таблицы будем называть такую последовательность ее клеток, что:

1. соседние клетки стоят в одной строке либо в одном столбце и

2. ни в одной строке и ни в одном столбце транспортной таблицы не входит более двух клеток цепи (т.е. либо две, либо одна, либо ни одной).

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

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