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

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

1 2 3 4

20 110 40 110
1 60 1

2

5

3

2 120 1

6

5

2

3 100 6

3

7

4


В левом верхнем углу произвольной (i, j)-клетки (i- номер строки, j - номер столбца) стоит так называемый коэффициент затрат - затраты на перевозку единицы груза от i – поставщика к j – потребителю. Например, в левом верхнем углу клетки (1,4) стоит число 3, следовательно, перевозка единицы груза от 1-го поставщика к 4-му потребителю обойдется в 3 условных денеж¬ных единицы и т. д.
Задача ставится следующим образом. Найти объемы перевозок для каждой пары "поставщик — потребитель " так, чтобы:
• предложения всех поставщиков были реализованы;
• спросы всех потребителей были удовлетворены;
• суммарные затраты на перевозку были бы минимальны.