Реферат: Найдём начальный опорный план методом северо-западного угла: Потребление

Постановка задачи.


Имеется 4 пункта производства обуви фирмы «Nike» с объёмами производства:

А1 = 30

А2 = 40

А3 = 70

А4 = 60

Эти производства должны обеспечить обувью 4 пункта потребления с объёмами потребления:

B1 = 35

B2 = 80

B3 = 25

B4 = 70

Матрица транспортных издержек:


9 7 2

Cij = 3 1 5 5

6 8 3 4

2 3 1 1


Проверим задачу на сбалансировку.


30 + 40 + 70 + 60 = 200

35 + 80 + 25 + 70 = 210

200 ≠ 210 → задача не сбалансирована.

Сбалансируем задачу добавив фиктивного производителя с объёмами производства:

А5 = 10


30 + 40 + 70 + 60 + 10 = 210

35 + 80 + 25 + 70 = 210

210 ≠ 210 → задача сбалансирована и можно её решить.


^ Найдём начальный опорный план методом северо-западного угла:



Потребление


Производство


B1



B2


B3


B4


Остаток




35



80


25


70


А1



30


30


−


−


−


0


А2




40


5


35


−


−


35,0


А3



70


−


45


25


−


25,0


А4



60


−


−


−


60


0


А5



10


−


−


−


10


0


Остаток



5,0


45,0


0


10,0






F = (30∙1) + (5∙3) + (35∙1) + (45∙8) + (25∙3) + (60∙1) + (10∙0) = 575


^ Найдём начальный опорный план методом минимального элемента:



Потребление


Производство


B1



B2


B3


B4


Остаток




35



80


25


70


А1



30


25


5


−


−


5,0


А2




40


−


40


−


−


0


А3



70


−


35


−


35


35,0


А4



60


−


−


25


35


35,0


А5



10


10


−


−


−


0


Остаток



25,0


40,35,0


0


35,0






F' = 590


^ Найдём начальный опорный план методом двойного предпочтения:



Потребление


Производство


B1



B2


B3


B4


Остаток




35



80


25


70


А1



30


25


−


−


5


5,0


А2




40


−


40


−


−


0


А3



70


−


40


−


30


40,0


А4



60


−


−


25


35


35,0


А5



10


10


−


−


−


0


Остаток



25,0


40,0


0


35,30,0






F'' = 575


^ Найдём оптимальный опорный план методом потенциалов:


Потребление


Производство


B1



B2


B3


B4


Остаток




35



80


25


70


А1



30


25


−


−


5


5,0


А2




40


−


40


−


−


0


А3



70


−


40


−


30


40,0


А4



60


−


−


25


35


35,0


А5



10


10


−


−


−


0


Остаток



25,0


40,0


0


35,30,0





F = 575


Вычислим потенциалы:



9 7 2

Cij = 3 1 5 5

6 8 3 4

2 3 1 1


0 -3 -5 0

-7 0 2 2

∆ = -3 0 -1 0

-2 3 0 0

0 6 2 2

max ∆ = 6 min (- ) = 5




30



−


−


−


−



40


−



−


−


35


−



35


−


−


25




35


5


5


−



−


F' = 490



9 7 2

Cij = 3 1 5 5

6 8 3 4

2 3 1 1


0 -8 -4 1

-2 0 -2 -2

∆ = 2 0 4 0

-3 -4 0 0

0 0 2 2


max ∆ = 4 min (- ) = 25




30



−


−


−


−



40


−



−


−


35


25



10


−


−


−




60


5


5


−



−


F'' = 485



9 7 2

Cij = 3 1 5 5

6 8 3 4

2 3 1 1


0 -8 -11 -5

4 0 -9 -8

∆ = 2 0 0 0

3 2 -1 0

0 6 -5 -4


max ∆ = 4 min (- ) = 5




30



−


−


−


5



35


−



−


−


35


25



10


−


−


−




60


−


10


−



−


F''' = 535



9 7 2

Cij = 3 1 5 5

6 8 3 4

2 3 1 1


0 -10 -13 -7

0 0 -9 -8

∆ = 4 0 0 0

5 2 -1 0

2 0 -5 -4


max ∆ = 5 min (- ) = 5




30



−


−


−


−



40


−



−


−


30


25



15


5


−


−




55


−


10


−



−


F'''' = 510



9 7 2

Cij = 3 1 5 5

6 8 3 4

2 3 1 1


0 -5 -8 -2

-5 0 -9 -8

∆ = -1 0 0 0

0 2 -1 0

-3 0 -5 -4


max ∆ = 2 min (- ) = 30




30



−


−


−


−



40


−



−


−


−


25



45


5


30


−




25


−


10


−



−


F''''' = 420



9 7 2

Cij = 3 1 5 5

6 8 3 4

2 3 1 1


0 -7 -8 -2

-3 0 -7 -6

∆ = -1 -2 0 0

0 2 -1 0

-1 0 -3 -2


F = 420

План оптимален