Многопродуктовая транспортная задача
Похожие статьи вашей тематики
Многие задачи линейного программирования относят- ся к классу задач, которые называют распределительными, или λ — задачами (лямбда-задачами), а также обобщенными транспортными задачами. В терминах перевозок распредели- тельную задачу можно сформулировать следующим образом: пусть имеются запасы МТС, сконцентрированные в пунктах
отправления, причем в различных пунктах имеются различ- ные виды запасов. Все эти запасы или часть их требуется доставить потребителям, причем для каждого потребителя указано количество запасов МТС. Расходы на перевозку МТС считаются известными. Задача заключается в нахождении плана перевозок, обращающего в минимум суммарные расхо- ды на транспортировку.
Ранее рассматривалась транспортная задача, в которой фигурировал один вид МТС (один продукт). А как быть, если необходимо спланировать перевозку нескольких видов МТС (несколько продуктов)? Для решения данной задачи можно сформулировать два пути:
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
Поставщик
| 
Σ = 16.
