Алгоритм решения транспортной задачи открытого типа методом условно-оптимальных планов

О пределяются суммы поставок по каждой строке , а также избытки и недостатки между ресурсами

поставщиков и предусмотренными поставками по формуле

(15)

Разности R_i называются избытками или недостатками в зависимости от знака, получаемого в результате математического действия. Так, в примере R₁ =200 – 0 = +200, R₂ = 250 – (80 + 150) = +20, R₃ = 100 – 160 = -60, R₄ = 250 – (90 + 190) = -30, R₅ = 200 – (130 + 150) = -80. Полученные значения разностей с сохранением знака записываем во вспомогательную графу матрицы (табл.17).

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

Все строки в зависимости от знака разности классифицируются на избыточные и недостаточные. Строка считается абсолютно избыточной, если R_i > 0 и абсолютно недостаточной, если R_i < 0. Строки, где R_i = 0 классифицируются на относительно избыточные и относительно недостаточные, согласно пункту 1 примечаний к данному алгоритму решения. В примере первая и вторая строки абсолютно избыточные, а третья, четвертая и пятая строки абсолютно недостаточные.

Корректировка матрицы стоимостей. Эта корректировка включает в себя следующие действия:

а) в каждом столбце, имеющем поставку в недостаточной строке определяется клетка с минимальной стоимостью в избыточной строке minC_ij^изб. Например, в первом столбце, в недостающих строках поставок нет, поэтому такая клетка не определяется. Во втором столбце – это будет клетка А₂В₂ с себестоимостью minC₂₂^изб= min{40; 30} = 30 руб./т. В третьем столбце – клетка А₂В₃ с себестоимостью minC₂₃^изб= min{90; 45} = 45 руб./т. В четвертом столбце – клетка А₂В₄, в пятом не определяется, в шестом – клетка А₂В₆ и в седьмом – клетка А₂В₇;

б) в каждом столбце, имеющем перевозку в недостаточной строке, определяется разность между найденной минимальной стоимостью в избыточных строках minC_ij^изб и стоимостью в занятой клетке недостаточной строки

C _ij^зан(-) по формуле (16)

Для первого столбца D ₁ не определяется из-за отсутствия minC_ij^изб, для второго столбца D ₂ = 30 – 25 = 5, для третьего – D ₃ = 45 – 10 = 35 и т.д. Значения D _j фиксируются во вспомогательной строке матрицы перевозок (см. табл.17);

в) определяется наименьшее значение из всех D _j (D = min D _j), которое прибавляется ко всем стоимостям во всех клетках недостающих строк (в том числе и в столбцах, где D _j не определялось). Для плана перевозок, представленного в табл. 17, D = min{5;35;20;35;10} = 5. Получаем новую скорректированную матрицу стоимостей (табл.18).

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

Строка s считается связанной с другой строкой при соблюдении следующих двух условий:

а) в каком-либо столбце k имеется совпадение стоимостей, C_sk = C_ik;

б) в клетке sk имеется поставка x_sk >0.

Связь строк указывает возможное направление переноса поставки, так как в результате корректировки матрицы стоимостей выравниваются стоимости в клетках связанных строк и в матрице появляется новая допустимая клетка с минимальной стоимостью в столбце. Так, после корректировки стоимостей, во втором столбце они выравнялись в клетках А₂В₂ и А₄В₂ (С₂₂ = С₄₂ = 30).

6. Через клетки с выравненными стоимостями строится замкнутый контур от избытка в избыточной строке до недостатка в недостаточной строке. В табл. 17 такая цепь показана пунктирной линией.

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

D x = min {R_нач; R_кон; Х_ij^неч },              (17)

где R_нач – избыток в избыточной строке, с которой начинается контур переноса; R_кон – недостаток в недостаточной строке, с которой заканчивается контур переноса; Х_ij^неч – поставки в нечетных вершинах построенного контура.

Для плана перевозок, представленного в табл. 17 Dx=min{20;30;90} = 20.

8. Осуществляется перенос выбранного значения D x и корректируются поставки в матрице перевозок. Для этого найденное значение D x вычитается от цифровых значений в нечетных вершинах контура и прибавляется к цифровым значениям в четных вершинах. В результате получается новый скорректированный план перевозок (табл.18). Далее выполняются пункты 1–8 алгоритма решения задачи методом условно-оптимальных планов. Согласно пункту 2 алгоритма в новом скорректированном плане перевозок имеются строки с разнозначными разностями R_i, следовательно расчеты необходимо продолжить (табл. 19–21).

Примечания:

При классификации строк на избыточные и недостаточные в таблице могут встретиться нулевые строки (например, вторая строка в табл.18). Для определения знака таких строк находится связь с какой-либо из строк через клетки с выравненными стоимостями и нулевой строке присваивается наименование относительно избыточной или относительно недостаточной в зависимости от того, с какой строкой обнаружится связь. В примере вторая строка табл.19 является относительно недостаточной, так как имеется её связь с четвертой строкой посредством клеток А₂В₂ – А₄В₂ .

Относительно недостаточные строки могут в следующем плане перевозок оказаться относительно избыточными и наоборот. В табл.19 вторая строка стала относительно избыточной, так как имеется её связь через занятые клетки А₁В₅ – А₂В₅ с абсолютно избыточной первой строкой, четвертая строка является относительно избыточной из-за её связи с относительно избыточной второй строкой посредством А₂В₂ – А₄В₂.

При построении замкнутого контура его очертания могут не повторять очертания прямоугольника, т.е. иметь более четырех вершин. Например, в табл.18 контур был построен исходя из того, что кроме новой связи А₁В₅ – А₂В₅ сохранилась и старая связь через клетки с выравненными себестоимостями А₂В₂ – А₄В₂.

Таблица 18

Скорректированный план перевозок ( первая корректировка)

 

Для плана перевозок, представленного в табл. 18

D = min{70; 10; 75; 75; 5; 40; 55} = 5; D x = min {200; 150; 70; 10} = 10.

Таблица 19

Скорректированный план перевозок (вторая к орректировка)

Для плана перевозок, представленного в табл. 19,

D = min{5; 20; 5} = 5; D x = min {190; 140; 150; 80} = 80.

Таблица 20

Скорректированный план перевозок (третья корректировка)

Д ля плана перевозок, представленного в табл. 20, D = min{15} = 15; D x = min {110; 60; 60; 160; 60} = 60.

 

Таблица 21

Скорректированный план перевозок (четвертая корректировка)

Станция отправления	Ресурсы, тыс. т	Станция назначения							Ri (избыток, недостаток)
		В1	В2	В3	В4	В5	В6	В7
		Объем потребления, тыс. т
		80	90	190	130	150	160	150
А1	200	80	40	90	100	35 150	75	80	+50
А2	250	15 80	35 90	50	45	35	70	35 80	+0
А3	100	50	65	90	90	110	60 100	100	+0
А4	250	50	35	20 190	35	75	60 60	70	+0
А5	200	30	65	35	35 130	55	95	35 70	+0

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

Таблица 22

Конечный план перевозок

Станция отправления	Ресурсы, тыс. т	Станция назначения							Ri (избыток, недостаток)
		В1	В2	В3	В4	В5	В6	В7
		Объем потребления, тыс. т
		80	90	190	130	150	160	150
А1	200	80	40	90	100	35 50	75	80
А2	250	10 80	30 90	45	40	30	65	30 80
А3	100	20	35	60	60	80	30 100	70
А4	250	40	25	10 90	25	65	50 60	60
А5	200	15	50	20	20 130	40	80	20 70

Конечное значение целевой функции (суммарная себестоимость перевозок конечного плана) составит

C_кон = f (x) =150· 35 + 80· 10 + 90· 30 + 80· 30 + 100· 30 + 190· 10 + 60· 50 + 130· 20 + 70· 20 = 23050 тыс. руб.

Полученный конечный план необходимо проверить на оптимальность методом потенциалов.

Так как методом потенциалов можно решать только транспортные задачи закрытого типа, данную транспортную задачу открытого типа необходимо привести к закрытому виду. Для этого вводится дополнительный фиктивный п отребитель B_фикт с объемом потребления равным = 1000 – 950 = 50 тыс./т.

Себестоимость перевозок в клетках, связанных с фиктивным потребителем, принимается равной нулю (табл.23).

Таблица 23

Проверка решения методом потенциалов

Станция отправления	Ресурсы, тыс. т	Станция назначения
		В1	В2	В3	В4	В5	В6	В7		Вфикт	Ui
		Объем потребления, тыс. т
		80	90	190	130	150	160		150	50
А1	200	80	40	90	100	35 150	75		80	0 50		100
А2	250	10 80	30 90	45	40	30 0	65 0		30 80	0		105
А3	100	20	35	60	60	80	30 100		70	0		140
А4	250	40	25	10 190	25	65	50 60		60	0		120
А5	200	15	50	20	20 130	40	80		20 70	0		115
Vj		115	135	130	135	135	170		135	100

После введения в матрицу перевозок фиктивного потребителя при проверке на условие “вырождения” выясняется, что задача “вырожденная”, так как N_зан = 10, а сумма m + n = 5 + 8 = 13. Вводятся две фиктивные перевозки, равные нулю в клетки А₂В₅ и А₂В₆. Далее, после присвоения потенциалов строкам и столбцам и проверки плана по условиям оптимальности, выясняется, что нарушений условий оптимальности в данном плане нет. Представленный для проверки план перевозок является оптимальным.

В завершение решения необходимо проанализировать начальный и конечный планы перевозок.

Самым оптимальным планом перевозок несомненно является начальный план, так как при его составлении все потребители прикреплялись к самым выгодным поставщикам. Однако этот план не может быть реализован из-за нехватки продукции в пунктах А₅, А₃ и А₄. Начальный план показывает, что пункт производства А₁ является неперспективным и желательно развивать производство прежде всего в пунктах А₅, А₃ и А₄, причем, в первую очередь, именно в пункте А₅ (до 280 тыс. т продукции). Также можно сказать, что план, представленный в табл.18, вызывает увеличение общей себестоимости перевозок на 20? 5 = 100 тыс.руб., в табл. 19 – на 10· (5 + 5) = 100 тыс. руб., в табл. 20 – еще на 80· (5 + 5 + 5) = 1200 тыс. руб., в табл. 21 – на 60·(5 + + 5 + 5 + 15) = 1800 тыс. руб.

Итого, общие дополнительные затраты, связанные с прикреплением потребителей к менее выгодным поставщикам из-за ограничений производства, составляют 3200 тыс. руб., что подтверждается при сравнении начального и конечного значений целевой функции D C = C_кон – C_нач = = 23050 – 19850 = 3200 тыс. руб.

Также, на каждом этапе расчета можно сопоставить увеличение целевой функции с затратами по альтернативному варианту. Например, план, представленный в табл.21, можно реализовывать, если развитие производства в пункте А₃ до 160 тыс. т не потребует затрат больше чем 1800 тыс. руб.

Необходимо также отметить, что в конечном плане перевозок оказалось не вывезено из пункта А₁ 50 тыс. т продукции в связи с ее суммарным переизбытком.