Постановка задачи.

Транспортная задача

Одной из типичных задач линейного программирования является так называемая транспортная задача.

Постановка задачи.

Пусть в m пунктах отправления находятся соответственно , единиц однородного груза, который должен быть доставлен n потребителям в количествах единиц. Заданы стоимости , перевозок единицы груза из i-го пункта отправления j-му пункту потребления.

Необходимо определить такой план перевозок, при котором суммарная стоимость перевозок была бы минимальна.

Обозначим через , количество единиц груза, перевозимого из i-гo склада j-му потребителю; тогда переменные должны удовлетворять следующим ограничительным условиям:

1) ; (1)

2) ; (2)

3) . (3)

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

. (4)

Следовательно, требуется найти m×n количество переменных удовлетво-ряющих указанным условиям и минимизирующих целевую функцию F.

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

I.Определение исходного опорного решения;