Решение. Обозначим через количество единиц сырья, перевозимого из -го склада на -е предприятие

Обозначим через количество единиц сырья, перевозимого из -го склада на -е предприятие. Тогда условия доставки и вывоза необходимого и имеющегося сырья обеспечиваются за счет выполнения следующих равенств:

(3.6)

При данном плане перевозок общая стоимость перевозок составит

(3.7)

Таким образом, математическая постановка данной транспортной задачи состоит в нахождении такого неотрицательного решения системы линейных уравнений (3.6), при котором целевая функция (3.7) принимает минимальное значение.

Определение опорного плана транспортной задачи. Метод северо-западного угла

Как и при решении задачи линейного программирования симплекс-методом, определение оптимального плана транспортной задачи начинают с нахождения ее опорного плана. Этот план можно находить методом северо-западного угла, методом минимального элемента или методом аппроксимации Фогеля. Сущность этих методов заключается в том, что опорный план находят последовательно за шагов, на каждом из которых в таблице условий задачи заполняют одну клетку, которую называют занятой. Заполнение одной из клеток обеспечивает полностью либо удовлетворение потребности в грузе одного из пунктов назначения (того, в столбце которого находится заполняемая клетка), либо вывоз груза из одного из пунктов отправления (из того, в строке которого находится заполняемая клетка).

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

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

Заметим, что на некотором шаге (но не на последнем) может оказаться, что потребность очередного пункта назначения равна запасам очередного пункта отправления. В этом случае также временно исключают из рассмотрения либо строку, либо столбец (что-нибудь одно). Таким образом, либо оставшиеся запасы соответствующего пункта отправления, либо оставшиеся потребности данного пункта назначения считают равными нулю. Этот нуль записывают в очередную заполняемую клетку и считают ее занятой. Рассмотренная последовательность действий гарантирует получение занятых клеток, в которых стоят неотрицательные компоненты опорного плана. Это является исходным условием для проверки последнего на оптимальность и нахождения оптимального плана.

Метод северо-западного угла.

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

Так, для рассматриваемого примера опорный план строится следующим образом (см. табл. 3.2). Величине присваиваем значение 120, поскольку потребности предприятия А меньше, чем запасы склада I. После этого на складе I остается 40 единиц сырья, которые целиком перевозятся на предприятие В (величина ), поскольку потребности предприятия В превышают остаток на складе I.

Таблица 3.2.

Склады	Предприятия	Запасы
A	B	C	D
I
II
III
Потребности

Для полного удовлетворения потребностей предприятия В не хватает еще 10 единиц сырья, которые, согласно методу северо-западного угла, предлагается завезти со склада II (величина ). В результате этого потребности предприятия В оказываются удовлетворенными и оставшиеся на складе II 140-10=130 единиц сырья (величина ) полностью перевозятся на предприятие С, так как его потребности (190 единиц) больше, чем остаток на складе. Остаток потребностей предприятия С удовлетворяется за счет склада III, откуда перевозятся недостающие 60 единиц сырья (величина ). После этого на складе III остается 110 единиц сырья, что вследствие закрытости рассматриваемой модели совпадает с потребностями последнего предприятия D, и эта величина () записывается в последнюю клетку с тарифом .

Определение оптимального плана транспортной задачи. Метод потенциалов

Для определения оптимального плана используются, как правило, метод потенциалов или дифференциальных рент. Рассмотрим один из них.