4.4.2. Методы составления первоначальных опорных планов

Метод северо-западного угла используют для нахождения произвольного опорного плана транспортной задачи.

Схема метода:

1 шаг. Полагают верхний левый элемент матрицы Х

х₁₁ = min (a₁, b₁).

Возможны три случая:

а ) если a₁ < b₁, то х₁₁ = a₁ и всю первую строку, начиная со второго элемента, заполняют прочерками, полагают b₁ := b₁- a₁

б) если a₁ > b₁, то х₁₁ = b₁, а все оставшиеся элементы первого столбца заполняют прочерками, полагают a_1:= a₁- b₁

в) если a₁ = b₁, то х₁₁ = a₁ = b₁, а все оставшиеся элементы первых столбца или строки заполняют прочерками, полагают либо a₁=0, если столбец заполнен прочерками, либо b₁=0, если строка заполнена прочерками.

Затем проделывают первый шаг с оставшейся незаполненной частью матрицы Х.

Пример 4.2.

Методом северо-западного угла составить опорный план следующей задачи:

Вj Аi													Предложение
				4			6				3
													100
				8			4				5
													200
Спрос	80				90				130					300 300

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

Начнем заполнение таблицы перевозок с верхнего («северо-западного») угла. Потребителю требуется 80 единиц груза. Эти 80 единиц груза могут быть доставлены от первого поставщика . Поэтому запишем в клетку количество перевозок и поставим прочерк в клетку (2,1).

Поставщик требует, чтобы с его предприятия было вывезено 100 единиц груза, а пока вывезено только 80. Увезем оставшийся груз к потребителю . Запишем остающиеся у поставщика 20 единиц груза и поставим прочерк в (1,3).

Вj Аi													Предложение
				4			6				3
		80			20				-				100
				8			4				5
		-			70				130				200
Спрос	80				90				130					300 300

Займемся теперь потребителем . Ему требуется 90 единиц груза, а пока доставлено от только 20. Недостающие 70 единиц доставим от поставщика . Продолжая заполнять таблицу, позаботимся об удовлетворении поставщика . От него вывезено 70 единиц груза, в то время как требуется вывезти 200. Увезем оставшийся груз к потребителю и, поскольку наша транспортная задача сбалансирована, именно эти оставшиеся у поставщика 130 единиц груза и нужны потребителю .

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

Метод минимального элемента позволяет построить начальный опорный план транспортной задачи и является вариантом метода северо-западного угла, учитывающим специфику матрицы С = (с_ij)_m∙n В отличие от метода северо-западного угла данный метод иногда позволяет сразу получить достаточно экономичный план и сокращает общее количество итераций по его оптимизации.

Схема метода.

1 шаг. Выбираем клетку матрицы соответствующую min c_ij, т.е

Полагаем х_ij = min(a_i, b_j).

Возможны три случая:

а ) если a_i < b_j, то х_ij = а_i и оставшуюся часть i-й строки, заполняют прочерками, полагают b_j:= b_j - а_i

б) если a_i > b_j, то х_ij = b_j, и оставшиеся элементы j-го столбца заполняют прочерками, полагают a_i := a_i - b_j

в) если a_i = b_j, то х_ij = а_i = b_j, а все оставшиеся элементы j-го столбца или i-й строки заполняют прочерками, полагают либо a_i = 0, если столбец заполнен прочерками, либо b_j = 0, если строка заполнена прочерками.

Затем проделывают первый и второй шаг с оставшейся незаполненной частью матрицы Х.

ПРИМЕР 4.3. Методом минимального элемента составить опорный план ТЗ из примера 4.2.

Итак, исходные данные:

Матрица стоимостей С = ,

b₁ =80; b₂ =90; b₃ =130.

min c_ij =c₁₃=3, помещаем перевозку x₁₃ = min(100, 130) = 100 в соотвутствующую клетку. Поскольку от первого поставщика всё вывезено, ставим прочерки в клетки (1,1) , (1.2). Третьему потребителю осталось поставить 30 единиц.

-	-	100

Для незаполненной части соответствующий минимальный элемент матрицы стоимости c₂₂ = 4. Помещаем в матрицу перевозок

x₂₂ = min(90, 200) = 90. У второго поставщика осталось 110 единиц, из которых 30 будет поставлено третьему потребителю и 80 – четвёртому.

-	-	100
80	90	30

X⁽⁰⁾ =