Способ наименьшего элемента в матрице

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

Функционал полученного решения

L(x) = 6 * 25 + 12 * 75 +5 * 75+16 * 25 + 18 * 75 + 14 * 50 + 12 * 150 +22 * 25 = 7625 т*км.

Обычно способ наименьшего элемента в матрице дает допустимое решение, более близкое к оптимальному, чем способ северо-западного угла. В условии нашего примера суммарный объем транспортной работы меньше на 2050 т*км (96*75 - 7625 = 2050). Способ наименьшего элемента в матрице целесообразно использовать при решении небольших матриц, поскольку с увеличением размера матрицы его применение затрудняется. В данном случае хорошие результаты позволяет получить способ двойного предпочтения.

Таблица 15

Завод	Строительная площадка						Объём производства, т
	B1		B2	B3	B4	B5
A1	15		12 75	1625	21	18	100
A2	15		22	22	14150	12150	300
A3	10		5 75	17	6	10	75
A4	6		13	1875	2225	18	125
Потребность в кирпиче, т	25		150	100	175	150	600

Способ двойного предпочтения

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

Допустимое распределение, полученное способом двойного предпочтения, обычно не отличается от распределения способом минимального элемента в матрице, что подтвердилось и в нашем случае: загрузки клеток и функциональные элементы совпали.

Способ аппроксимации Фогеля

При этом способе первое допустимое распределение является близким к оптимальному и по сути является приближенным решением задачи.

Таблица 16

Завод	Строительная площадка							Объём производства, т
	B1		B2		B3	B4	B5
A1	15		12 75		1625	21	18	100
A2	15		22		22	14150	12150	300
A3	10		5 75		17	6	10	75
A4	6		13		1875	2225	18	125
Потребность в кирпиче, т	25		150		100	175	150	600

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