Транспортная задача линейного программирования

U₄ = 0,

b₄ = 6, так как a₄ + b₄ = С₄₄ = 6 

a₁= 0, так как a₁ + b₄ = С₁₄ = 6 

b₃ = 5, так как a₁ + b₃ = С₁₃ = 5 

b₁ = 7, так как a₄ + b₁ = С₄₁ = 7     

a₂= - 1, так как a₂ + b₁ = С₂₁ = 6 

b₅ = 6, так как a₂ + b₅ = С₂₅ = 5 

a₃= 1, так как a₃ + b₅ = С₃₅ = 7 

b₂ = 6, так как a₃ + b₂ = С₂₅ = 7 

Если оказалось, что все  эти псевдостоимости не превосходят  стоимостей č_ij £ с_ij, £ ³ то план потенциален и, значит, оптимален. Если же хотя бы в одной свободной клетке псевдостоимость больше стоимости (как в нашем примере), то план не является оптимальным и может быть улучшен переносом перевозок по циклу, соответствующему данной свободной клетке. Цена этого цикла ровна разности между стоимостью и псевдостоимостью в этой свободной клетке. В таблице мы получили в двух клетках č_ij ³ с_ij, теперь можно построить цикл в любой из этих двух клеток. Выгоднее всего строить цикл в той клетке, в которой разность č_ij - с_ij максимальна. В нашем случае в обоих клетках разность одинакова (равна 1), поэтому, для построения цикла выберем, например, клетку (4,2):

Таблица

ПН ПО	В1	В2	В3	В4	В5	ai
А1	10	8	5 42	6 6	9	0
А2	6 + 4	7	8	6	5 - 26	-1
А3	8	7 - 27	10	8	7 + 0	1
А4	7 - 14	5 + û	4	6 6	8	0
bj	7	6	5	6	6

Теперь будем перемещать по циклу число 14, так как оно  является минимальным из чисел, стоящих  в клетках, помеченных знаком - . При  перемещении мы будем вычитать 14 из клеток со знаком - и прибавлять к  клеткам со знаком +. После этого  необходимо подсчитать потенциалы a_i и b_j и цикл расчетов повторяется.

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

1. Взять любой опорный план перевозок, в котором отмечены m +n - 1 базисных клеток (остальные клетки свободные).

2. Определить для этого плана платежи (a_i и b_j) исходя из условия, чтобы в любой базисной клетке псевдостоимости были равны стоимостям. Один из платежей можно назначить произвольно, например, положить равным нулю.

3. Подсчитать псевдостоимости č_i,j = a_i + b_j для всех свободных клеток. Если окажется, что все они не превышают стоимостей, то план оптимален.

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

5. После этого заново подсчитываются платежи и псевдостоимости, и, если план ещё не оптимален, процедура улучшения продолжается до тех пор, пока не будет найден оптимальный план. Так в нашем примере после 2 циклов расчетов получим оптимальный план. При этом стоимость всей перевозки изменялась следующим образом: F₀ = 723, F₁ = 709, F₂ = F_min = 703.

Следует отметить так же, что оптимальный план может иметь  и другой вид, но его стоимость  останется такой же F_min = 703.

Составьте оптимальный план перевозки угля с минимальными транспортными  расходами с шахт Варгашорская (В), Западная (З) и Комсомольская (К), еженедельно  добывающих соответственно 26,32 и 17тыс. т. Покупатели угля расположены в  разных городах В, В, С и D, заявки которых составляют 28, 19, 12 и 16 тыс. т  между поставщиками и потребителями  представлены в транспортной таблице.

 

 

 

 

 

 

 

 

Шахты	Потребители				Добыча угля, тыс. тонн в неделю
	28	19	12	16
Западная	70	76	72	68	32
Варгашорская	80	84	82	77	26
Комсомольская	80	83	82	76	17
Заявки, тыс. тонн	28	19	12	16

Решение:

Математическая модель данной задачи имеет вид:

 

F=70х₁₁+76х₁₂+72х₁₃+68х₁₄+80х₂₁+84х₂₂ +82х₂₃+77х₂₄+80х₉+83х₁₀ +82х₁₁+76х₁₂ →min

 

X₁₁+X₁₂+X₁₃+X₁₄=32

X₂₁+X₂₂+X₂₃+X₂₄=26

X₃₁+X₃₂+X₃₃+X₃₄= 17

X₁₁+X₂₁+X₃₁=28

X₁₂+X₂₂+X₂₃=19

X₁₁+X₁₂+X₁₃=12

X₁₃+X₂₃+X₃₃=16

 

 

 

 

2.Практическая  часть.

2.1 Условие задачи

Груз, хранящийся на складах  в каждом соответственно 60 80 и 106 машин, требуется перевезти в четыре магазина. В первый магазин требуется 44 машины, Во второй 70, в третий 50, а  в четвертый 82. Стоимость прогона  одной машины за 1км составляет 10коп, расстояние между складами и магазинами указаны в таблице.

Маг. Скл.	1	2	3	4
1	13	17	6	8
2	2	7	10	41
3	12	18	2	22

Найти минимальный  по стоимости план перевозок

Метод северо заподного  угла .

Маг. Скл.	44	70	50	82
60	44  13	16 17	6	8
80	2	54  7	26 10	41
106	12	18	24 24	82 22

Шаг  1. Начинаем распространять доставки с верхнего левого угла. Помещаем в данную клетку максимально возможное  количество товара.

 Шаг 2. Уменьшаем доступный  объём поставки из рассмотренной  клетки (от первого поставщика) на  величину сделанной поставки, а  величину потребности на величину той же поставки. Таким образам первый поставщик себя не исчерпал, но удовлетворил потребности первого потребителя.

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

Шаг 4. Определим потребителя  с неудовлетворёнными потребностями  и удовлетворим его.

 

F=24*2+26*10+54*7+44*13+16*17+28*22=3334.

Метод минимальной  стоимости .

Начинаем заполнять  таблицу с клетки чья стоимость  min и продолжаем двигаться по увеличению.

Для того чтобы план считался оптимальным необходимо проверить  потенциал свободных ячеек для  этого достаточно выполнения условий; d_ij=C_IJ-(U₂+V₃)>0. Тоесть если все косвенные стоимости не отрецательны то решение оптимально. Если хотя бы одно из условий не выполняется, осуществляется преобразование таблицы. Так, в способе северо-западного угла (СЗУ) для очередного назначения перевозки выбирается левая верхняя клетка таблицы (при этом никак не учитываются цены перевозок). Наоборот, в способе минимальной стоимости (МС) для заполнения выбирается клетка текущей таблицы с минимальной ценой перевозки, что в большинстве случаев (но не всегда) приводит к более дешевому (а значит и более близкому к оптимальному) начальному плану перевозок.

 

Маг. Скл.	44	70	50	82
60	13	17	6	60  8
80	44-312	36 34 2	10	4 1
106	+34 12	-343418	50 2	22 22

 

F=44*2+50*2+36*7+60*8+34*18+22*22=2016

 

Там где получилось функция наименьшей и следует  начинать решение. В Данном случае метод  наименьшей стоимости.

Для каждой заполненной  клеточки, составляем уравнение U _j+V_i=C _{i j}-цена перевозки. Положим, например, неизвестное u ₁ равным 0 (через него можно из первых трех уравнений найти V2,V4).

 

 

Примем 

                       

                            

                        

                        

                      

                    

 

 

 

 

Для каждой свободной  клетки вычисляется числовая характеристика косвенная стоимость d_ij =C_ij – (U_i+U_j).

 

 

 

 

 

Оценка свободной ячейки A₃B₂ отрецательная следовательно решения не является оптимальным  .

Среди ячеек цикла A₃B_2* A₂B₁ ,номер которых чётные ,найдём ячейку обл. наименьшем значении min={34,44}=34

Маг. Скл.	44	70	50	82
60	13	17	6	60 8
80	10 2	70 7	10	41
106	34 12	18	50 2	22 23

 

 F=60*8+10*2+70*7+34*12+50*2+22*22=1982

Работаем с зап. Клетками .

 v₁+u₃=12                        Примем u₃=0

v₃+u₃=2                           v₁=12-0=12

v₄+u₃=22                         v₃=2-0=2

v₄+u₁=8                         v₄=22-0=22

v₁+u₂=2                         u₁=8-22=-14

v₂+u₂=7                         u₂=2-12=-10

                                      v₂=7-(-10)=17

Найти оценки свободных яцеек.

d₁₁=13-(-14+12)=15

d₁₁=17-(-14+17)=14

d₁₃=6-(-14+2)=18

d₂₃=10-(-10+2)=18

d₂₄=41-(-10+22)=29

d₃₂=18-(0+17)=1

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