Линейное программирование

ЛЕКЦИЯ 5. ТРАНСПОРТНАЯ ЗАДАЧА

Одной из типичных задач линейного программирования является так называемая транспортная задача. Она возникает при планировании наиболее рациональных перевозок грузов. В одних случаях это означает определение такого плана перевозок, при котором стоимость последних была бы минимальна, а в других – более важным является выигрыш во времени. Первая задача получила название транспортной задачи по критерию стоимости, а вторая – транспортной задачи по критерию времени.

Первая задача является частным случаем задачи линейного программирования и может быть решена симплексным методом. Однако в силу особенностей этой задачи она решается проще.

Пусть в р пунктах отправления находится соответственно единиц однородного груза, который должен быть доставлен q потребителям в количествах  единиц. Заданы стоимости  перевозок единицы груза из i-го пункта отправления k-му пункту потребления. Обозначим  (i=1, 2, ..., р; k=1, 2, ..., q) количество единиц груза, перевозимого из i-го склада k-му потребителю; тогда переменные  должны удовлетворять следующим ограничительным условиям:[pic 1][pic 2][pic 3][pic 4][pic 5]

1. [pic 6]
2. [pic 7]
3. [pic 8]

Суммарные затраты на перевозки будут равны

[pic 9]

Следовательно, требуется найти pq переменных , удовлетворяющих указанным условиям и минимизирующих целевую функцию L.[pic 10]

Решение такой задачи разбивается на два этапа:

1. определение исходного опорного решения, проверка его на оптимальность,
2. построение последовательных итераций, т. е. приближение к оптимальному решению.

Определение 1. Если

                                                                (5.1)[pic 53]

то задача называется закрытой. Если

                                                                (5.2)[pic 54]

то открытой задачей.

Метод «минимального элемента».

Определим исходное опорное решение. Согласно этому методу, грузы распределяются в первую очередь в те клетки, в которых находится минимальный тариф перевозок . Далее поставки распределяются в незанятые клетки с наименьшими тарифами с учетом оставшихся запасов у поставщиков и удовлетворения спроса потребителей. Процесс распределения продолжают до тех пор, пока все грузы от поставщиков не будут вывезены, а потребители не будут удовлетворены.[pic 55]