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

ТРАНСПОРТНАЯ  ЗАДАЧА

Вариант № 3

Имеется три склада,  содержащие однотипную продукцию. Имеется пять потребителей, которые нуждаются в этой продукции. Требуется найти такой план перевозок при котором общие затраты на перевозку всей продукции по всем потребителям будут минимальными.

вj     аi	250	300	350	500	20	180
300	2	4	5	7	9	0
400	1	6	3	5	4	0
900	6	3	2	1	10	0

а_i  -поставщики   в_j- потребители

Решение:

I

1.  Убедимся, что задача с правильным балансом:

3                        5

∑ _аi = 1600 > ∑ _вj    = 1420– Задача открытая. Необходимо ввести фиктивного

_{i= 1                           j = 1}                         потребителя : 1600-1420= 180

2.  Методом  минимальной стоимости построим опорное решение:

    

        2    4    5   7  9   0          
           С=  1    6    3   5  4   0    - Матрица стоимости

        6    3    2   1 10  0

В верхнем правом углу записываем стоимости единицы груза, а нижнем левом поставку. Число заполненных клеток должно быть: 3+6 -1= 8

вj     аi	250	300	350	500	20	180
300	2	4	5	7	9	0
400	1	6	3	5	4	0
900	6	3	2	1	10	0

 Вычисляем значение целевой функции:

Z (X) = 250*2+ 50* 4+ 350*3 + 30*5+ 20*4 + 250*3+ 470* 1+180*0= 3200

3. Вводим потенциалы, для того чтобы проверить оптимальность данного решения:

u _i = c _ij -v_j ; v_j= c _ij-u _i ; c _ij = u _i + v_j

      V₁₌   1                     V_{2 =}  3                      V₃₌  -1                  V₄₌ 1                     V₅₌0        V₆₌0

вj     аi	250	300	350	500	20	180
U1 = 1 300	2 250	4 50	5	7	9	0
U2= 4   400	1	6	3 350	5 30	4 20	0
U3 = 0900	6	3 250	2	1 470	10	0 180

4.Вычисляем оценки для всех свободных клеток по формуле:

∆ _{ij =} u _i + v_j   -  c _ij          ∆ _ij  ≤  0

∆ ₂₁=  4+1-1= 4 ≤ 0

∆₃₁=  0+1-6=-6 ≤  0

∆ ₂₂ = 4+3-6= 1 ≤  0

∆ ₁₃= 1-1-5=-5   ≤  0

∆ ₃₃= 0-1-2=-3≤  0

∆ ₁₄=1+1-7=-5  ≤  0

∆ ₃₅= 0+0-10=-10 ≤  0

∆ ₁₆= 1+0-0=1 ≤  0

∆ ₂₆= 4+0-0=4 ≤  0

Опорное решение не является оптимальным, так как у четырех клеток положительная оценка.

5. Чтобы распределить поставки строим цикл, который включает  клетку (2;6), так как у нее самая большая положительная оценка:

вj     аi	250	300	350	500	20	180
300	2 250	4 50	5	7	9	0
400	1	6	3 350	-       5 30	4 20	+  0 4
900	6	3 250	2	1 470  +	10	0 180 -

Осуществляем сдвиг по циклу на величину:  Ө =30

II

       V₁₌   1                     V_{2 =}  3                      V₃₌  3                    V₄₌ 1                V₅₌4          V₆₌0

вj     аi	250	300	350	500	20	180
U1 = 1 300	2 250	4 50	5	7	9	0
U2= 0   400	1	6	3 350	5	4 20	0 30
U3 = 0900	6	3 250	2	1 500	10	0 150

Вычисляем значение целевой функции:

Z (X) = 250*2 + 50*4+ 350*3 + 20*4+ 30*0 + 250*3+ 500*1+150*0= 3080

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

∆ ₂₁=  1+1-2= 0 ≤ 0

∆ ₃₁= 0+1-1=-1 ≤  0

∆ ₂₂ = 0+3-6=-3 ≤  0

∆ ₁₃= 1+3-5=-2 ≤  0

∆ ₃₃= 0+3-2=1 ≤  0

∆ ₁₄=1+1-7=-5≤  0

∆ ₂₄=0+1-5=-4 ≤  0

∆ ₁₅= 1+4-9=-4 ≤  0

∆ ₃₅= 0+4-9=-6 ≤  0

∆ ₁₆= 1+0-0=1 ≤  0

Данное решение не является оптимальным, есть две клетки с положительной оценкой. Чтобы распределить поставки строим цикл, который включает клетку (1;6).

вj     аi	250	300	350	500	20	180
300	2 250	-          4 50	5	7	9	+  0 1
400	1	6	3 350	5	4 20	0 30
900	6	3 250  +	2	1 500	10	0 150   -