Отыскание опорного решения транспортной задачи

Один из методов отыскания опорного решения - это метод северо-западного угла.

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

Пример. Рассмотрим ТЗ для трёх поставщиков и четырех потребителей. Её условия сведём в транспортную таблицу 8.1

Табл.8.1

Обо­значим клетку на пересечении строки ; и столбца через (i, j). При решении транспортной задачи, условия которой при­ведены в табл. 8.1, в левую верхнюю клетку (1.1) транспорт­ной таблицы запишем минимальное из чисел , . В данном случае — это число = 30. Это означает, что весь груз от первого поставщика полностью вывезен: = 30, и строку можно исключить из дальнейшего рассмотрения, приняв остальные переменные этой строки столбца , и равными нулю.

Переходим к клетке (2, 1), находящейся ниже рассмот­ренной. Первому потребителю требуется еще 10 единиц груза, которые можно отправить от второго поставщика. Поэтому чи­сло 10 вписываем в данную клетку: = 10. Так как заявка первого потребителя полностью выполнена , переходим к заполнению вто­рого столбца таблицы, начиная с клетки (2,2). Сюда впишем 40 единиц груза от поставщика , которые у него еще имеются, а 20 которые недостает второму по­требителю, возьмем у поставщика : =20.

В результате мы полностью удовлетворим полностью заявку потребителя . Оставшиеся у третьего поставщика 60 единиц груза распределим следующим образом. 20 единиц груза передадим третьему по­требителю =20 удовлетворив таким образом полностью его заявку. Четвертому потребителю останется =40 единиц груза, что полностью соответствует его заявке.

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

=30, =10, =40, =20, =20, =40 (8.1)

Значение остальных переменных в этом решении равны 0.Для того чтобы это решение было опорным, необходимо выполнение следующего условия: число занятых клеток в транспортной таблице дол­жно быть равно N = m + n—1. В данном случае это условие вы­полнено: заполнено шесть клеток и N = 3 + 4—1=6. Подсчи­таем значение целевой функции, соответствующее найденному опорному решению:

W=3 х 30 + 7 х 5 + 2 х 5 + 1 х 40 + 3 х 25+ 16 х 25 =960 (8.2)

Как правило, опорное решение, полученное методом се­веро-западного угла, значительно отличается от оптимального потому, что при его отыскании мы нигде не учитывали стои­мость перевозок. Рассмотрим более эффективный метод оты­скания опорного решения —