Матрица условий задачи с введенным фиктивным потребителем, уравнивающим дисбаланс производство-потребление

Пункт отправления	Пункт отправления	Наличие груза, т
В1	В2	В3	В4	В5	В6	Вф
А1							Ф
А2							Ф
А3							Ф
А4							Ф
Потребность в грузе, т								∑130

2-й случай. У поставщика груза меньше, чем нужно потребителю.

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

4.4. Задача с запретами для перевозок разнородных грузов

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

Требуется составить план перевозок и закрепить потребителей за поставщиками так, чтобы транспортная работа была минимальной. Решение задачи осуществляется методом потенциалов на матрице типа табл. 4.1-4.3, но в клетках, соответствующих запрещенным перевозкам, записывают значения расстояний, значительно превышающих самые большие расстояния в матрице (т.е. запрещенные клетки блокируют).

При решении такой матрицы гарантируется отсутствие нагрузок в блокированных клетках.

Рассмотрим следующую задачу: на складах А₁ и А₂ имеется речной песок, а на складах А₃ и А₄ – горный песок в количествах соответственно: 60, 20, 70 и 50 т. Потребителям В₁ и В₂ требуется только горный песок (запрещается возить речной песок из А₁ и А₂) в количествах соответственно 30 и 80 т, а остальным любой (либо горный, либо речной) в следующих размерах: В₂ – 50 т и В₃ – 40 т. Расстояния между пунктами приведены в табл. 4.6.

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

Так как абсолютная величина блокируемого числа безразлична (важно только, что оно значительно больше любого расстояния в таблице), в матрице его обозначают обычно буквой М (много). Под М понимают сколь угодно большое число, т. е. М = ∞. При решении матрицы операции с числом М производят так же, как и с любым другим числом.

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

4.5. Задача с минимизацией времени перевозки скоропортящихся грузов

Условия задачи также формулируются в виде матрицы типа табл. 4.1-4.3.

Лимитирующей в данной задаче является самая длинная перевозка. Лучшим (оптимальным) будет являться план, у которого самая длительная перевозка будет иметь самую наименьшую длительность.

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

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

Шаг 1. Составить матрицу условий так, как это делают при решении обычной транспортной задачи.

Шаг 2. Найти методом потенциалов план, у которого линейная форма достигает минимального значения.

Шаг 3. Определить max t_ij (наибольшее из времен) запланированных перевозок (где x_ij>0).

Шаг 4. Во всех клетках матрицы, где t_ij> max t_ij¹, заменить t_ij на число М = ∞.

Шаг 5. Отыскать для измененной матрицы решение, при котором линейная форма достигает минимума. Если в полученном решении x_ij>0 расположены только в клетках, где t_ij < М, то снова находим max t_ij¹¹ и повторяем шаги 4 и5. Если же в полученном решении имеется хотя бы один x_ij>0, расположенный в клетке с t_ij = М, то оптимальным по критериюt(Х) = max t_ij (x_ij>0 – план перевозок, t(Х) = время наиболее продолжительной перевозки) будет предыдущее решение. Очевидно, что после конечного числа повторений шагов 3,4 и 5 будет получено оптимальное решение, т.е. такой план перевозок, по которому грузы всем потребителям будут доставлены за возможно короткое время.