Пример решения ТЗ открытого типа

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

1) Проверка типа модели ТЗ (открытая или закрытая). Если ТЗ открытая, вводим фиктивного поставщика или потребителя.

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

3) Проверка плана на вырожденность. Если план вырожденный, то приводим к невырожденному, дописывая в свободные клетки нули.

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

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

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

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

(для всех свободных клеток).

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

Пример решения ТЗ открытого типа

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

с_ij =

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

Решение. Определим тип модели ТЗ.

Суммарная мощность поставщиков: 35+40+40+50=165 (ед. товара);

Суммарный спрос потребителей: 31+52+17+20=120 (ед. товара).

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

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

165–120=45 (ед. товара). Тарифы 0.

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

Построим начальный опорный план методом северо-западного угла.

Стоимость плана (транспортные затраты):

Z (X)=31·5+4·4+40·3+8·8+17·7+15·10+5·2=155+16+120+64+119+150+10=634 у.е.

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

		2)	5)	6)	1)	8)
4)				3
3)
7)
8)
						-3
						– 4

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

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

Z (X ₁)=15·3+20·1+31·2+9·3+2·7+43·6=45+20+62+27+14+258=426 у.е.

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

Дополним таблицу столбцом и строкой потенциалов α _i и β _j. Составим систему потенциалов, используя 1-е условие оптимальности для заполненных поставками клеток :

; ; ; ; ; ; ; ; .

Из этой системы находим: , , , , , , , , .

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

(1; 1) 5 – 0 – 1 = 4 ≥ 0; (1; 2) 4 – 0 – 2 = 2 ≥ 0;

(1; 5) 0 – 0 + 4 = 4 ≥ 0; (2; 3) 5 – 1 – 3 = 1 ≥ 0;

(2; 4) 8 – 1 – 1 = 6 ≥ 0; (2; 5) 0 – 1 + 4 = 3 ≥ 0;

(3; 1) 6 – 4 – 1 = 1 ≥ 0; (3; 2) 8 – 4 – 2 = 2 ≥ 0;

(3; 4) 10 – 4 – 1 = 5 ≥ 0; (4; 1) 5 – 4 – 1 = 0 ≥ 0;

(4; 3) 7 – 4 – 3 = 0 ≥ 0; (4; 4) 2 – 4 – 1 = –3 < 0.

Т.к. среди свободных клеток есть такие, в которых 2-е условие оптимальности не выполняется ( –3 < 0), то план не оптимален. Будем его улучшать.

Для заполнения выбираем клетку (4; 4), т. к. ей соответствует наименьшая отрицательная оценка: 2 – 4 – 1 = –3. Построим цикл перераспределения груза с началом в этой клетке. Выбранной для заполнения клетке присваиваем знак «+», далее знаки чередуем. Среди вершин со знаком «–» выбираем наименьшую поставку:

Θ= – объем перепоставки.

Перераспределив поставки по циклу (передавая по циклу 2 единицы груза), перейдем к новому опорному плану.

		4
		-1
						-2
					– 1

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

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

у.е.

Исследуем 2-й опорный план X ₂ на оптимальность. Найдем значения потенциалов и получим матрицу оценок распределения:

	-1

Условие оптимальности нарушено в клетке (1; 2). Осуществим переход к нехудшему опорному плану. Найдем цикл перераспределения груза с началом в этой клетке (1; 2): Θ= – объем перепоставки.

						-1
					– 2

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

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

у.е.

Исследуем опорный план X ₃ на оптимальность. Найдем значения потенциалов и построим матрицу оценок распределения:

Условие оптимальности выполняется для всех свободных клеток (их оценки все неотрицательные), следовательно, план X ₃ оптимален.

Ответ: Наименьшие транспортные затраты ; оптимальный план распределения поставок:

X ₃ = .