II.

для всех заполненных клеток; (5)

III.

для всех пустых клеток. (6)

На основании первого условия оптимальности потенциалы находят из условий

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

Если при проверке второго условия оптимальности окажется, что

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

, то план не оптимальный и можно перейти к нехудшему опорному плану.

3) Переход к нехудшему опорному плану.

Переход к не худшему опорному плану осуществляют при помощи цикла перераспределения груза. Цикл представляет собой замкнутую ломаную, звенья которой взаимно перпендикулярны и вершины цикла, кроме одной, находятся в заполненных клетках.

Приведем примеры разновидностей форм циклов:

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

. Клетке начала цикла присваивают знак «+», во всех остальных вершинах цикла знаки чередуют «–», «+» и т.д. Из клеток цикла со знаками «–» выбирают ту, в которой находится минимальный груз. Это и будет то количество груза, которое нужно перераспределить по циклу, т.е. в клетке со знаком «+» это количество груза прибавляется, а со знаком «–» – вычитается. Клетки, которые не задействованы в цикле, остаются неизменными.

Таким образом, получаем новый опорный план. Подсчитываем транспортные расходы, которые должны быть не более предыдущих. В противном случае где-то допущена ошибка. Новый план опять проверяем на оптимальность, используя условия (5) и (6). Если план оптимальный, то задача решена. Если же план опять не оптимальный, то работаем, согласно пункту 3) до получения оптимального плана и нахождения Z_min.

Транспортная задача открытого типа

Если для транспортной задачи выполняется одно из условий

или

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

Это делают так: если

, то добавляют фиктивного потребителя со спросом

(в распределительной таблице появится дополнительный столбец), если

, то добавляют фиктивного поставщика с предложением

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

Запишем алгоритм решения транспортной задачи:

1) Проверка типа модели ТЗ.

2) Построение начального опорного плана (любым способом).

3) Проверка плана на вырожденность.

4) Проверка плана на оптимальность методом потенциалов:

а) нахождение потенциалов из системы

(для всех заполненных клеток);

б)проверка второго условия оптимальности

(для всех пустых клеток).

5) Переход к нехудшему опорному плану (если это необходимо).

Пример.На складах имеются запасы однотипного товара в количестве а(35; 40; 40; 50), который необходимо доставить потребителям. Потребности потребителей задает вектор b (31; 52; 17; 20). Матрица затрат на доставку единицы товара от i-го поставщика j-му потребителю:

с=

Составить план перевозок с минимальными транспортными затратами.

Решение. Определим тип модели транспортной задачи. Суммарная мощность поставщиков:

35+40+40+50=165 (единиц товара); Суммарный спрос потребителей:

31+52+17+20=120 (единиц товара).

Т.к.

, то имеем модель открытого типа.

Введем фиктивного потребителя, спрос которого равен

165 –120 =45 (единиц товара).

Тарифы

0. Т.о. получаем модель закрытого типа, m= 4 – число поставщиков, n= 5 – число потребителей. Ранг матрицы задачи

. Построим начальный опорный план методом минимального элемента (наименьшей стоимости).

	31		52		17		20	45
35	5	4	3	1	0	0
	15		20
40	2	3	5	8	0	1
	31		9
40	6	8	7	10	0	4
	40
50	5	6	7	2	0	4
	43		2		5
	1		2		3		1	– 4	Таб.1

Число заполненных клеток распределительной таблицы 8 равно рангу матрицы задачи r = 8, следовательно, опорный план является невырожденным.

Транспортные затраты, соответствующие опорному плану:

(ден. ед.).

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

Дополним таблицу 1 столбцом и строкой потенциалов

. Систему потенциалов найдем, используя первое условие оптимальности: для заполненных поставками клеток

;

Из записанной системы находим:

Проверим выполнение второго условия оптимальности. Для всех пустых клеток должно выполняться неравенство:

Практикум по решению линейных задач математического программирования (стр. 9 из 11)

3) Переход к нехудшему опорному плану.

Транспортная задача открытого типа