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

№

Задача

31

Имеются три пункта поставки груза А1, А2, А3 и четыре пункта потребления этого груза В1, В2, В3, В4. Запасы в пунктах поставки составляют 60, 80 и 100 т соответственно, а потребность в этом грузе в пунктах потребления составляют 40, 60, 80 и 60 т соответственно. Стоимость перевозок из пунктов поставки в пункты потребления приведены в матрице: | 1 2 3 4 | С= | 4 3 2 0 | | 0 2 2 1 | Требуется составить оптимальный план перевозок груза при условии минимизации общей стоимости перевозок.

Решение:

Строим опорный начальный план задачи по правилу северо-западного угла, т.е. начинаем заполнять таблицу с верхнего левого угла с учетом запасов поставщиков и запросов потребителей:

А/В		В1	В2	В3	В4
		40	60	80	60
А1	60	40 1	20 2	- 3	- 4
А2	80	- 4	40 3	40 2	- 0
А3	100	- 0	- 2	40 2	60 1

Проверяем, выполняется ли условие корректности решения путем проверки равенства N=n+m-1, где N-количество свободных ячеек в таблице, n-количество потребителей, m-количество поставщиков. В отношении данной таблицы данное условие выполняется: 6=3+4-1.

Проводим пересчет коэффициентов по заполненным ячейкам из условия C_ij=α_i+β_j, где C_ij – стоимость перевозки, α_i,β_j-дополнительные пересчетные коэффициенты.

C₁₁=α₁+β₁=1; α₁=0; β₁=1

C₁₂=α₁+β₂=2; β₂=2

C₂₂=α₂+β₂=3; α₂=1

C₂₃=α₂+β₃=2; β₃=1

C₃₃=α₃+β₃=2; α₃=1

C₃₄=α₃+β₄=1; β₄=0

Осуществляем проверку полученного решения на оптимальность по незаполненным ячейкам при условии C_ij≥α_i+β_j

α₁+β₃=1≤3

α₁+β₄=0≤4

α₂+β₁=2≤4

α₂+β₄=1≤0

α₃+β₁=2≤0

α₃+β₂=3≤2

Максимальное несоответствие наблюдается в неравенстве α₃+β₁=2≤0, а следовательно максимальным звеном неоптимальности будет являться звено Х₃₁. Через максимальное звено неоптимальности составляем контур перераспределения ресурсов. Тогда в соответствии с этим контуром получаем новый опрный план:

А/В		В1	В2	В3	В4
		40	60	80	60
А1	60	0 1	60 2	- 3	- 4
А2	80	- 4	0 3	80 2	- 0
А3	100	40 0	- 2	- 2	60 1

Проверяем, выполняется ли условие корректности решения путем проверки равенства N=n+m-1, где N-количество свободных ячеек в таблице, n-количество потребителей, m-количество поставщиков. В отношении данной таблицы данное условие не выполняется: 8=3+4-1, следовательно будем считать две ячейки условно заполненными и добавляем в них нули.

Проводим пересчет коэффициентов по заполненным ячейкам из условия C_ij=α_i+β_j, где C_ij – стоимость перевозки, α_i,β_j-дополнительные пересчетные коэффициенты.

C₁₁=α₁+β₁=1; α₁=0; β₁=1

C₁₂=α₁+β₂=2; β₂=2

C₂₂=α₂+β₂=3; α₂=1

C₂₃=α₂+β₃=2; β₃=1

C₃₁=α₃+β₁=0; α₃= -1

C₃₄=α₃+β₄=1; β₄=2

Осуществляем проверку полученного решения на оптимальность по незаполненным ячейкам при условии C_ij≥α_i+β_j

α₁+β₃=1≤3

α₁+β₄=2≤4

α₂+β₁=2≤4

α₂+β₄=2≤0

α₃+β₂=1≤2

α₃+β₃=0≤2

Несоответствие наблюдается в нескольких неравенствах. Будем считать, что максимальное несоответствие наблюдается в неравенстве α₂+β₄=2≤0, а следовательно максимальным звеном неоптимальности будет являться звено Х₂₄. Через максимальное звено неоптимальности составляем контур перераспределения ресурсов. Тогда в соответствии с этим контуром получаем новый опрный план:

А/В		В1	В2	В3	В4
		40	60	80	60
А1	60	0 1	60 2	- 3	- 4
А2	80	- 4	- 3	20 2	60 0
А3	100	40 0	- 2	60 2	- 1

Проверяем, выполняется ли условие корректности решения путем проверки равенства N=n+m-1, где N-количество свободных ячеек в таблице, n-количество потребителей, m-количество поставщиков. В отношении данной таблицы данное условие не выполняется: 7=3+4-1, следовательно будем считать одну ячейку условно заполненной и добавляем в нее нуль.

Проводим пересчет коэффициентов по заполненным ячейкам из условия C_ij=α_i+β_j, где C_ij – стоимость перевозки, α_i,β_j-дополнительные пересчетные коэффициенты.

C₁₁=α₁+β₁=1; α₁=0; β₁=1

C₁₂=α₁+β₂=2; β₂=2

C₂₃=α₂+β₃=2; α₂= -1

C₂₄=α₂+β₄=0; β₄=1

C₃₁=α₃+β₁=0; α₃= -1

C₃₃=α₃+β₃=2; β₃=3

Осуществляем проверку полученного решения на оптимальность по незаполненным ячейкам при условии C_ij≥α_i+β_j

α₁+β₃=3≤3

α₁+β₄=1≤4

α₂+β₁=0≤4

α₂+β₂=1≤3

α₃+β₂=1≤2

α₃+β₄=0≤1

Т.к. все неравенства выполняются, то построенный план является оптимальным.

Вычисляем конечную стоимость перевозок:

L=0*1+60*2+20*2+60*0+40*0+60*2=280