Многопродуктовая транспортная задача

Многие задачи линейного программирования относят- ся к классу задач, которые называют распределительными, или λ — задачами (лямбда-задачами), а также обобщенными транспортными задачами. В терминах перевозок распредели- тельную задачу можно сформулировать следующим образом: пусть имеются запасы МТС, сконцентрированные в пунктах

отправления, причем в различных пунктах имеются различ- ные виды запасов. Все эти запасы или часть их требуется доставить потребителям, причем для каждого потребителя указано количество запасов МТС. Расходы на перевозку МТС считаются известными. Задача заключается в нахождении плана перевозок, обращающего в минимум суммарные расхо- ды на транспортировку.

Ранее рассматривалась транспортная задача, в которой фигурировал один вид МТС (один продукт). А как быть, если необходимо спланировать перевозку нескольких видов МТС (несколько продуктов)? Для решения данной задачи можно сформулировать два пути:

1. Сформировать по каждому виду перевозимых МТС свою транспортную задачу (однопродуктовую). Частные решения этих задач и будут представлять оптимальный план перевозок.

2. Сформировать одну (многопродуктовую) транспортную задачу.

Рассмотрим более подробно второй путь.

Пример 10.5. Для трех пользователей необходимо попол- нить запасы бензина АИ−76 и АИ−92. Пополнение запасов мо- жет производиться из хранилища города (гор.) и области (обл.). Запасы и потребности бензина представлены в табл. 10.8 и 10.9. Возможности поставщиков (гор. и обл.) и спрос потребителей указаны в табл. 10.10.

Таблица 10.8

Бензин	Склад гор.	Склад обл.
АИ–76	40	60
АИ–93	20	30

Таблица 10.9

Бензин	1 потр.	2 потр.	3 потр.
АИ–76	25	45	30
АИ–93	15	35	—

Протяженность маршрутов представлена в табл. 10.10.

Таблица 10.10

Хранилище	1 потр.	2 потр.	3 потр.
Склад гор.	30	50	60
Склад обл.	100	90	120

В целях упрощения вычислений предположим, что Cij = Lij, где Cij — стоимость перевозки между пунктами i и j; Lij — про- тяженность маршрута между пунктами i и j.

Для того чтобы учесть многопродуктовый характер зада- чи, сформируем транспортную модель следующим образом. Вместо того чтобы рассматривать каждого поставщика как один исходный пункт, разобьем его на несколько пунктов в со- ответствии с количеством видов перевозимых горюче-смазоч- ных материалов (ГСМ). Аналогично поступим и с пунктами на- значения (потребителями). В результате для нашего примера получим 4 поставщика и 5 потребителей (рис. 10.2).

 

Склад  гор.

 

Склад  обл.

1 потр.

 

 

2 потр.

 

3 потр.

 

Рис. 10.2. Схема реализации многопродуктовой задачи

 

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

Транспортная таблица для многопродуктовой транспорт- ной задачи в условиях нашего примера имеет следующий вид (табл. 10.11):

Таблица 10.11

Поставщик