Метод потенциалов для решения транспортной задачи в матричной форме. Задача оптимального распределения ресурсов

Построить оптимальный план перевозок каменного угля с пяти станций Аi (i = 1,2,3,4,5), до девяти крупных потребителей, имеющих подъездные пути Вj (j = 1,2,…,9).

Данные о наличии ресурсов на пяти станциях отправления Аi приведены в таблице 1, данные о размерах прибытия груза Вj на девять станций назначения – в таблице 2.

Расстояние перевозки от каждой i–й станции отправления до каждой j–й станции назначения указано в правом верхнем углу каждой клетки матрицы. В левом верхнем углу ряда клеток матрицы указаны ограничения пропускной способности.

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

F(х) = 45·90 + 30·50 + 75·60 + 80·10 + 80·25 + 10·20 + 105·35 + 15·70 + 135·40 + 135·60 + 95·30 + 55·40 + 95·10 + 20·35 + 5·25 + 20·80 = 39700 ден. ед.

Требуется найти оптимальную трассу участка железнодорожного пути между пунктами А и В, из которых второй лежит к северо-востоку от первого. Местность, по которой пройдет магистраль, является пересеченной и включает лесистые зоны, холмы, болота, реку. Поэтому стоимость строительства равных по длине участков пути может быть различной. Требуется так провести дорогу из А в В, чтобы суммарные затраты на сооружение участка были минимальны.