2015-08-21
299
ТРАНСПОРТНАЯ ЗАДАЧА
Важным частным случаем задачи линейного программирования является транспортная задача. Необходимо определить план перевозок некоторого однородного груза, минимизирующий затраты на общую стоимость перевозок, из 
пунктов отправления (производства) 
в 
пунктов потребления 
.
Введем следующие переменные:
– величина предложения продукта в пункте 
, 
– величина спроса на продукт в пункте 
, 
;
– затраты на транспортировку единицы продукта из пункта в пункт ;
– количество продукта, перевозимого из пункта в пункт .
Тогда транспортную задачу можно представить в виде таблицы 1.
Т а б л и ц а 2.1
| Пункты производства | Пункты потребления | Предложение | |||||
| 
| … | 
| … | 
| ||
| 
| 
| … | 
| … | 
| 
|
| 
| 
| … | 
| … | 
| 
|
| … | … | … | … | … | … | … | … |
| 
| 
| … |
| … | 
|
|
| … | … | … | … | … | … | … | … |
| 
|
| … | 
| … | 
| 
|
| Спрос | 
| 
| … |
| … | 
|
В сделанных обозначениях математическую модель транспортной задачи можно записать следующим образом:
|
|
|
(2.1)
(2.2)
(2.3)
Существует несколько вариантов транспортной задачи.
1. Закрытая транспортная задача
Общий спрос равен общему предложению: 
Это равенство является необходимым и достаточным условием существования допустимого плана задачи (2.1) – (2.3).
2. Открытая транспортная задача
а) Пусть существует излишек продукта, т.е. 
б) Пусть существует дефицит продукта, т.е. 
Такую задачу можно свести к закрытой задаче, вводя дополнительный столбец (строку), равный по величине имеющейся разности между общим спросом и общей потребностью, тарифы которого считают условно равными нулю.
3. Транспортная задача с фиксированными перевозками
Если объем перевозок между пунктами и задан, то в задаче (2.1) – (2.3) вводится дополнительное ограничение 
, где 
– заданный объем перевозок.
4. Задача с ограничениями на пропускные способности
Если объем перевозок из пункта в пункт ограничен величиной 
, то в задаче (2.1) – (2.3) вводится дополнительное ограничение 
.
Все приведенные выше модели описывают транспортную задачу в виде задачи линейного программирования. В этой форме она может быть решена стандартными средствами ЛП, например, с помощью симплекс-метода. Однако специфичная форма системы ограничений данной задачи (в виде уравнений-равенств) позволяет существенно упростить обычный симплекс-метод. Такой метод решения транспортной задачи (ТЗ) называют распределительным, или методом потенциалов. По аналогии с общим случаем ЗЛП, решение в нем осуществляется по трем шагам:
- нахождение первоначального опорного решения;
- проверка критерия оптимальности;
- переход к следующему опорному решению.
|
|
|
