ЗАДАЧА 3. Решение транспортной задачи Пункты отправления

• Название: Решение транспортной задачи Пункты отправления
• Дата: 15.06.2018
• Размер: 106.53 Kb.
• Имя файла: ЗАДАЧА 3.docx
• Тип: Решение; #47017
• страница: 6 из 8

Этап II. Улучшение опорного плана

Найдем оптимальный план транспортной задачи методом потенциалов.

Опорный план имеет следующий вид:

X=  0 70 0 80 0 60 40 100 0 0 0 30 0 0 120

При этом плане стоимость перевозок вычисляется так:

S=

8

·

70

+

5

·

80

+

6

·

60

+

10

·

40

+

5

·

100

+

13

·

30

+

14

·

120

=

4290

Проверяем полученный опорный план на оптимальность. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем систему из 7 уравнений с 8 неизвестными:

• 
  β₂−α₁=8
  
• 
  β₄−α₁=5
  
• 
  β₁−α₂=6
  
• 
  β₂−α₂=10
  
• 
  β₃−α₂=5
  
• 
  β₂−α₃=13
  
• 
  β₅−α₃=14
  

Полагая α₁=0, находим β₂=8 β₄=5 α₂=-2 α₃=-5 β₁=4 β₃=3 β₅=9 .

Для каждой свободной клетки вычисляем число α_ij=β_j−α_i−c_ij:

α₁₁=-15, α₁₃=-11, α₁₅=0, α₂₄=-18, α₂₅=0, α₃₁=2, α₃₃=0, α₃₄=-2.

Полученные числа заключаем в рамки и записываем их в соотвестствующие клетки таблицы:

.

Пункты отправления Пункты назначения Запасы B1 B2 B3 B4 B5 A1 19   8   14   5   9   150 −15 70 −11 80 0 A2 6   10   5   25   11   200 60 40 100 −18 0 A3 7   13   8   12   14   150 2 30 0 −2 120 Потребности 60 140 100 80 120 500

Среди чисел α_ij есть положительные. Следовательно данный опорный план не является оптимальным. Наибольшее положительное число 2 находится в пересечении строки A₃ и столбца B₁. Для данной свободной клетки строим цикл пересчета. Для этого вставим в эту клетку знак "+" а остальные клетки цикла поочередно знаки "−" и "+".

Пункты отправления Пункты назначения Запасы B1 B2 B3 B4 B5 A1 19   8   14   5   9   150 −15 70 −11 80 0 A2 6 − 10 + 5   25   11   200 60 40 100 −18 0 A3 7 + 13 − 8   12   14   150 2 30 0 −2 120 Потребности 60 140 100 80 120 500

Наименьшее из чисел в минусовых клетках равно 30. Клетка, в которой находится это число становится свободной. В новой таблице другие числа получаются так. Числам, находящимся в плюсовых клетках добавляется 30, а из чисел, находящихся в минусовых клентках вычитается это число.

Пункты отправления Пункты назначения Запасы B1 B2 B3 B4 B5 A1 19   8   14   5   9   150   70   80   A2 6   10   5   25   11   200 30 70 100     A3 7   13   8   12   14   150 30       120 Потребности 60 140 100 80 120 500

Опорный план имеет следующий вид:

X=  0 70 0 80 0 30 70 100 0 0 30 0 0 0 120

При этом плане стоимость перевозок вычисляется так:

S=

8

·

70

+

5

·

80

+

6

·

30

+

10

·

70

+

5

·

100

+

7

·

30

+

14

·

120

=

4230

Проверяем полученный опорный план на оптимальность. Для этого находим потенциалы пунктов отправления и назначения. Для заполненных клеток составляем систему из 7 уравнений с 8 неизвестными:

• 
  β₂−α₁=8
  
• 
  β₄−α₁=5
  
• 
  β₁−α₂=6
  
• 
  β₂−α₂=10
  
• 
  β₃−α₂=5
  
• 
  β₁−α₃=7
  
• 
  β₅−α₃=14
  

Полагая α₁=0, находим β₂=8 β₄=5 α₂=-2 β₁=4 β₃=3 α₃=-3 β₅=11 .

Для каждой свободной клетки вычисляем число α_ij=β_j−α_i−c_ij:

α₁₁=-15, α₁₃=-11, α₁₅=2, α₂₄=-18, α₂₅=2, α₃₂=-2, α₃₃=-2, α₃₄=-4.

Полученные числа заключаем в рамки и записываем их в соотвестствующие клетки таблицы:

.

Пункты отправления Пункты назначения Запасы B1 B2 B3 B4 B5 A1 19   8   14   5   9   150 −15 70 −11 80 2 A2 6   10   5   25   11   200 30 70 100 −18 2 A3 7   13   8   12   14   150 30 −2 −2 −4 120 Потребности 60 140 100 80 120 500