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

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

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

Пункты отправления Пункты назначения Запасы 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

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

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

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

:

X=  0 40 0 80 30 0 100 100 0 0 60 0 0 0 90

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

S=

8

·

40

+

5

·

80

+

9

·

30

+

10

·

100

+

5

·

100

+

7

·

60

+

14

·

90

=

4170

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

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

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

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

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

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

.

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

Среди чисел α_ij нет положительных. Следовательно данный опорный план является оптимальным.