1. Постановка и решение транспортной задачи

Среди задач линейного программирования особое место занимает транспортная задача. Общая формулировка задачи, алгоритм её решения, выбор первоначального опорного плана, критерий оптимальности и особые случаи рассмотрены в курсе лекций «Методы оптимальных решений».

Рассмотрим решение транспортной задачи на примере.

Пример 13. Пусть необходимо организовать перевозку кирпича с т=3 кирпичных заводов на m=4 стройки. Условия транспортной задачи запишем в табличной форме:

Таблица 24. Исходные данные

Поставщики и их мощности (тыс.шт.)		Потребители и их спрос
		Стройка 1	Стройка 2	Стройка 3	Стройка 4
		90	80	120	110
Завод 1	100	6	5	4	4
Завод 2	175	3	7	6	5
Завод 3	125	5	6	5	4

Мощность поставщика – это количество кирпича (тыс.шт.), которое он может отправить потребителям за некоторый период времени. Спрос потребителя – это его возможности по использованию кирпича за тот же период времени. В верхнем левом углу каждой клетки области, выделенной утолщенной линией, задана удельная стоимость c_ij поставки 1 тыс.шт. кирпича по маршруту i-j (с завода i настройку j).

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

Составим первоначальный план поставок продукции методом наименьших затрат. Количество продукции, которое можно перевезти по каждому маршруту, записываем в нижние правые углы клеток таблицы

Находим клетку (маршрут) с минимальной удельной стоимостью. Если таких клеток несколько, можно начать с любой из них. Минимальная стоимость c₂₁=3. По маршруту 2 – 1 (с завода 2 на стройку 1) можно перевезти 90 единиц продукции. Ставим в нижний правый угол клетки 90 и перечеркиваем клетку сплошной линией. Клетка заполнена. При этом спрос стройки 2 удовлетворен полностью, поэтому остальные клетки столбца перечеркиваем пунктирной диагональной линией («вычеркиваем столбец»). На заводе 2 остается 175 – 90 = 85 тыс.шт. кирпича.

Таблица 25. Шаг 1

Поставщики и их мощности (тыс.шт.)		Потребители и их спрос
		Стройка 1	Стройка 2	Стройка 3	Стройка 4
		90	80	120	110
Завод 1	100	6	5	4	4
Завод 2	175	3 90	7	6	5
Завод 3	125	5	6	5	4

В незачеркнутых клетках находим клетку с минимальной удельной стоимостью: c₁₃=4. По соответствующему маршруту 1 – 3 можно перевезти 100 тыс.шт. кирпича. Ставим в нижний правый угол клетки 100, перечеркиваем клетку. На заводе 2 нет остатка продукции, поэтому остальные клетки строки перечеркиваем пунктирной линией (табл.26). На стройку 3 остается привезти 120 – 100 = 20 тыс.шт. кирпича.

Таблица 26. Шаг 2

Поставщики и их мощности (тыс.шт.)		Потребители и их спрос
		Стройка 1	Стройка 2	Стройка 3	Стройка 4
		90	80	120	110
Завод 1	100	6	5	4 100	4
Завод 2	175	3 90	7	6	5
Завод 3	125	5	6	5	4

Далее находим клетку с минимальной удельной стоимостью: c₃₄=4. По соответствующему маршруту 3 – 4 можно перевезти 110 тыс.шт. кирпича, при этом запросы стройки 4 будут удовлетворены полностью. На заводе 3 остатки продукции составят 15 тыс.шт. Ставим в нижний правый угол клетки 110, перечеркиваем клетку и вычеркиваем столбец (табл.27).

Таблица 27. Шаг 3

Поставщики и их мощности (тыс.шт.)		Потребители и их спрос
		Стройка 1	Стройка 2	Стройка 3	Стройка 4
		90	80	120	110
Завод 1	100	6	5	4 100	4
Завод 2	175	3 90	7	6	5
Завод 3	125	5	6	5	4 110

Продолжая далее по тому же алгоритму, последовательно получаем таблицы 28 и 29.

Таблица 28. Шаг 4

Поставщики и их мощности (тыс.шт.)		Потребители и их спрос
		Стройка 1	Стройка 2	Стройка 3	Стройка 4
		90	80	120	110
Завод 1	100	6	5	4 100	4
Завод 2	175	3 90	7	6	5
Завод 3	125	5	6	5 15	4 110

Таблица 29. Первоначальный план, метод наименьших затрат

Поставщики и их мощности (тыс.шт.)		Потребители и их спрос
		Стройка 1	Стройка 2	Стройка 3	Стройка 4
		90	80	120	110
Завод 1	100	6	5	4 100	4
Завод 2	175	3 90	7 80	6 5	5
Завод 3	125	5	6	5 15	4 110

План первоначального распределения поставок определен. Вычислим суммарные затраты на перевозку по всем маршрутам:

F=4*100+3*90+7*80+6*5+5*15+4*110=1775.

Второй метод (метод «северо-западного угла») определения первоначального опорного плана основан на последовательном заполнении свободных клеток, начиная с верхней левой клетки («северо-западный угол»). При последовательном вычеркивании строк и столбцов каждый раз происходит заполнение верхней левой клетки незачеркнутой области. В результате получим первоначальный опорный план (табл.30).

Таблица 30. Первоначальный план, метод «северо-западного угла»

Поставщики и их мощности (тыс.шт.)		Потребители и их спрос
		Стройка 1	Стройка 2	Стройка 3	Стройка 4
		90	80	120	110
Завод 1	100	6 90	5 10	4	4
Завод 2	175	3	7 70	6 105	5
Завод 3	125	5	6	5 15	4 110

Суммарные затраты на поставки по всем маршрутам при таком распределении равны:

F=6*90+5*10+7*70+6*105+5*15 +4*110=2225.

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