Базисный план, составленный способом северо-западного угла

Грузообразующие пункты	Грузопотребляющие пункты нкты								Итого
	В1		В2		В3		В4
А1		11		7		9		5	300
	200		100
А2		5		13		7		8	500
			250		250
А3		3		12	400	5		9	800
							400
Итого	200		350		650		400		1600

232

полного удовлетворения спроса. Только после этого переходят на сле­дующий столбец. Когда в столбце два пли несколько одинаковых по величине минимальных показателей а., то поставки могут быть раз­метены в любом и ) ник. Результаты составления базисного плана этим способом приведены в табл. 21.

Таблица 21

Базисный план, составленный способом наименьшего элемента по столбцу

Грузообразующие пункты	Грузопотребляющие пункты нкты								Итого
	В1		В2		В3		В4
А1		11		7		9		5	300
			300
А2		5		13		7		8	500
					1000		400
А3		3		12		5		9	800
	200		50		550
Итого	200		350		650		400		1600

При базисном плане, полученном способом наименьшего эле­мента по столбцу (табл. 21). транспортная работа составит

200 • 3 + 300 • 7 + 50 • 12 + 100 • 7 + 550 • 5 + 400 • 8 = 9050 т • км.

Базисный план получился лучше (транспортная работа сократи­лась на 3550 т • км), однако нельзя сказать* является ли он оптималь­ным или нет. Для ответа на этот вопрос необходимо составленный базисный план проверить на оптимальность. Для этих целей разра­ботано несколько методов. Наиболее широкое применение находят методы потенциалов (метода МОДИ), Хичкока, Креко.

Идея метода потенциалов была высказана Л. В. Канторовичем в 1940 г. В 1951 г. американский ученый Дж. Д. Данциг предложил ту же идею, назвав се модифицированным распределительным мето­дом (МОДИ). Идея метода потенциалов, или метола МОДИ, заклю­чается в том, что для проверки допустимого базисного плана на оптимальность определяются особым образом числа, называемые по­тенциалами. Главное требование к потенциалам заключается в том. чтобы каждый показатель а« в загруженной клетке был равен сумме потенциалов своих строки и столбца.

а_ij= U_i+ V_j (7.38)

где U_i — значение потенциала строки;

V_j — значение потенциала столбца.

Совершенно безразлично, с какой строки или столбца начинать определение потенциалов. Безразлично также, каким по величине

233

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

Потенциалы незагруженных (свободных) клеток определяются по формуле

E_ij= а_ij - (U_i+ V_j) (7.39)

где E_ij — потенциал свободной клетки.

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

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

Проверим на оптимальность базисный план, составленный спо­собом наименьшего элемента по столбцу. Для этого матрицу распре­делительного метода дополним одним столбцом и строкой (табл. 22). Поставим в строке А₁ величину потенциала, равную нулю. Тогда, со­гласно формуле (7.38), потенциал столбца В₂ будет равен 7. Потенци­ал строки А₃ будет равен 5, а столбца В₃ - 0 и т. д. Потенциалы незаг­руженных клеток находим по формуле (7.39).

Таблица 22

Грузообразующие пункты	Грузопотребляющие пункты								Итого	Потенциалы строк
	В1		В2		В3		В4
А1	+	11		7	+	9	+	5
			300						300	0
А2		5	-1	13		7		8
	0		+		-100		400		500	7
А3		3		12		5	+	9
	200		-50		+550				800	5
Итого	200		350		650		400		1600	х
Потенциалы столбцов	-2		7		0		1		х	х

В результате проверки допустимого плана на оптимальность по­лучена клетка А₂-В₂, имеющая отрицательный потенциал. Это ука­зывает на то, что план не оптимален и необходимо выполнить пере­распределение закрепления поставщиков за потребителями. Это выполняется следующим образом. Строится контур. Контуром назы­вается замкнутая ломаная линия, образованная прямыми отрезка­ми, углы соединений между которыми равны 90°. Строится контур так, чтобы все углы, кроме одного, располагались в загруженных клетках, а один угол в свободной, наиболее потенциальной клетке. При соблюдении этих правил для каждой свободной (незагружен­ной) клетки можно построить только один контур. Определяют положительные (+) и отрицательные (—) углы контура. Первый положительный угол лежит в незагруженной клетке, для которой строится контур, рядом с ним находятся отрицательные углы и т. д.

Определяется наименее загруженная клетка, занятая отрицатель­ным углом контура. Количество груза, указанное в этой клетке, от­нимается из всех клеток, занятых отрицательными углами контура, и прибавляется во все клетки контура с положительными углами.

Ранее загруженные клетки, которые не оказались расположенны­ми в углах контура, переносятся в матрицу нового варианта закреп­ления потребителей груза за поставщиками без изменения (табл. 23).

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

200 • 3 + 300 • 7 + 50 • 13 + 50 • 7 + 600 • 5 + 400 • 8 = 9900 т • км.

Таблица 23

Грузообразующие пункты	Грузопотребляющие пункты								Итого	Потенциалы строк
	В1		В2		В3		В4
А1		11		7		9		5
			300						300	0
А2		5		13		7		8
			50		50		400		500	6
А3		3		12		5		9
	200				600				800	4
Итого	200		350		650		400		1600	х
Потенциалы столбцов	-1		7		1		2		х	х

235

234

Последовательность решения транспортной задачи методом по­тенциалов схематически показана на рис. 44.

Рис. 44. Последовательность решения задач методом потенциалов

Другие способы составления базисного плана.

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

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

При составлении базисного плана поставок способом аппрокси­мации У. Фогеля исходные данные заносятся в таблицу, которая от­личается от матрицы метода потенциалов тем, что имеет дополни­тельную строку и столбец разностей (табл. 24).

236

Таблица 24

Грузообразующие пункты	Грузопотребляющие пункты								Итого	Разности по строкам
	В1		В2		В3		В4
А1		11		7		9		5
			300						300	2
А2		5		13		7		8
									500	2
А3		3		12		5		9
									800	2
Итого	200		350		650		400		1600	х
Разности по столбцам	2		5		2		3		х	х

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

Так, в столбце В, минимальный элемент, равен 3 в клетке А₃В₁. Следующий за ним по величине элемент, равный 5, находится в клет­ке А₂В₁. Разность между ними равна 2. Эта и другие разности по строкам и столбцам записаны в табл. 24.

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

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

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

237

Таблицу 25

Грузообразующие пункты	Грузопотребляющие пункты								Итого	Разности по строкам
	В1		В2		В3		В4
А2		5		13		7		8
			300						500	2
А3		3		12		5		9
	200								800	2
Итого	200		50		650		400		1300	х
Разности по столбцам	2		1		2		2		х	х

Если оказывается несколько одинаковых разностей, имеющих мак­симальное значение (в нашем примере столбцы В₁В₃ и строки А₂ и А₃), ТО в соответствующих им столбцах или строчках находят и загружают седловую точку. Седловой точкой называют клетку таблицы, расстоя­ние которой имеет наименьшее значение (при решении задачи на минимум) из всех расстояний ее строки и столбца или наибольшее значение при решении задачи на максимум.

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

В нашем примере седловой точкой будет клетка А₃В₁ в которую записывается максимально возможная поставка, и т. д.

Способ последующего анализа (способ стрелок). Первоначальное зак­репление потребителей за поставщиками, начиная с первого столбца с учетом наименее возможного расстояния транспортирования, по­требности грузопотребителя и возможности поставщика (см. табл. 21). Полученный базисный план анализируется с целью выявления воз­можностей его улучшения. В строке А₃ можно передвинуть из клетки А₃В₂ в клетку А₃В₃ 50 т, а из клетки А₂В₃ в клетку А₂В₂ вместо этого — 50 т. В результате этого в первом случае расстояние перевозки увели­чится на 7 км, а во втором случае сократится на 6 км. Суммарное сокращение расстояния перевозки составит 1 км.

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

238

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

Если при составлении базисного плана число загруженных клеток получается больше, чем т + п - 1, то при проверке на оптимальность для какой-либо строки или столбца будут найдены два потенциала. Чтобы устранить такую ситуацию, нужно произвести следующие действия:

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

углы контура обозначить попеременно знаками «плюс» и «ми­нус». Углу, лежащему в загруженной клетке, для которой построен контур, присваивается знак «плюс»;

выявить наименьшую загрузку в клетках, занятых углами со зна­ком «плюс», вычесть ее из всех клеток и прибавить во все клетки, занятые углами со знаком «минус».

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

Если число загруженных клеток при составлении базисного пла­на окажется меньше, чем т + п — 1, то недостающее число клеток загружают нулями. Загружать следует те клетки, которые лежат на пересечении строк и столбцов, не имеющих потенциалы, со строка­ми или столбцами, для которых потенциалы уже определены и име­ют наименьшие значения показателя критерия оптимальности.

Дополнительные условия при решении транспортных задач мето­дом потенциалов. Предложение больше спроса. Условия задачи запи­сываются в таблицу, в которую вводится фиктивный столбец Р с ог­раничением по спросу, равный разности между предложением и спросом. Так как груз никуда не вывозится, то в углах клеток стол­бца Р ставятся нули. Задачу решают по алгоритму метода потенциа­лов, рассматривая столбец Р как потребитель груза.

239

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

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

О б я з а т е л ь н а я п о с т а в к а. Если из пункта А_i в обязательном порядке необходимо перевезти в пункт В_j какой-то объем груза, то в этом случае величина обязательной поставки вычитается из суммы спроса и суммы предложений и при решении задачи не учитывается. При определении окончательного результата затраты, связанные с обязательным объемом перевозок, прибавляются к полученному оп­тимальному варианту.

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

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

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