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

Пусть условия транспортной задачи заданы табл. 1

Таблица 1

Поставщики	Потребители	Запасы
Запросы

Заметим, что модель задачи является закрытой. Не учитывая стоимость перевозок, заполняем клетки, начиная с таким образом, чтобы запросы всех потребителей удовлетворялись, а запасы всех поставщиков были бы вывезены. Итак, запас 1-го поставщика – 100 единиц товара, а запрос 1-го потребителя – 200. Поэтому в первую клетку 1-го столбца заносим , исключаем из рассмотрения первого поставщика (его запасы вывезены) и переходим ко второму поставщику, у которого 250 единиц товара. Для того, чтобы удовлетворить первого потребителя, необходимо ещё 100 единиц. Поэтому в клетку первого столбца заносим . Исключаем первого потребителя и переходим ко второму, запасы которого равны 200. У второго поставщика осталось 150 единиц товара, поэтому в клетку заносим . Исключаем из рассмотрения второго поставщика и переходим к третьему. Этот процесс продолжается до тех пор, пока остаётся неисключённой в точности одна строка или один столбец. В результате получим табл. 2.

Таблица 2

Поставщики	Потребители	Запасы
Запросы

Число занятых клеток . Также легко убедиться, что заполненные клетки таблицы не образуют циклов. Следовательно, построенное решение действительно является опорным.

Замечание. Если одновременно и столбец, и строка удовлетворяют ограничениям, очередная переменная, включаемая в базисное решение, обязательно имеет нулевое значение.

Вычислим стоимость перевозки, соответствующую этому опорному плану:

.

Эта стоимость перевозки на самом деле довольно далека от оптимальной, так как при составлении опорного плана не учитывались стоимости перевозок. Поэтому чаще применяют другой метод, описываемый ниже.

Не нашли, что искали? Воспользуйтесь поиском: