Транспортная задача, как частный случай задач линейного программирования. Тема 6.1. Методы первоначального распределения

Под термином "транспортные задачи" понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), по n потребителям этих ресурсов.
Транспортная задача

На практике наиболее часто встречаются следующие задачи, относящиеся к транспортным:
прикрепление потребителей ресурса к производителям;
привязка пунктов отправления к пунктам назначения;
взаимная привязка грузопотоков прямого и обратного направлений;
отдельные задачи оптимальной загрузки промышленного оборудования;
оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др.

Общее представление транспортной задачи.

Из 3-х пунктов (А1, А2, А3) к четырем пунктам назначения (B1, B2, B3, B4) перевозится однородный груз. Из пункта A1 может быть вывезено 50 т., из А2 – 40 т., из А3 – 20 т. продукции.
В пункт назначения B1 должно поступить 30 т., в В2 – 25 т., в В3 – 35 т., в В4 – 20 т.
Пример транспортной задачи.

Дана матрица затрат на перевозку единицы груза от i-го поставщика к j-ому потребителю.
Необходимо составить план перевозок, обеспечивающий минимальные суммарные затраты на перевозку при условии того, что производимый груз полностью вывозится из пунктов производства, а спрос всех потребителей полностью удовлетворяется.

Метод северо-западного угла потребности (спрос).
При нахождении опорного плана транспортной задачи методом северо-западного угла на каждом шаге рассматривается первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения.
Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного («северо-западный угол») и заканчивается клеткой для неизвестного т.е. идет как бы по диагонали таблицы.