Задача 1 2 задача 2 7 задача 3 10 Ответы на контрольные вопросы 20 задача 1

• Название: Задача 1 2 задача 2 7 задача 3 10 Ответы на контрольные вопросы 20 задача 1
• Дата: 05.04.2022
• Размер: 215.16 Kb.
• Имя файла: Otchyot.docx
• Тип: Задача; #444562
• страница: 5 из 6

Заказы

0

0

0

6-6=0

 

Потребители/Базы

П1

П2

П3

П4

План
поставок

Б1

9 [10]

15

10

1

10

Б2

3 [5]

8 [10]

3 [15]

2

30

Б3

6

2

5

8 [19]

19

Б4

0

0

0

0 [6]

6

Заказы

15

10

15

25

 

m+n-1=7; 4+4-1=7 --- план невырожденный

Подсчитаем целевую функцию

Целевая функция: 9*10+3*5+8*10+3*15+8*19+0*6=

382

Оптимизируем план

Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 9; 0 + v1 = 9; v1 = 9
u2 + v1 = 3; 9 + u2 = 3; u2 = -6
u2 + v2 = 8; -6 + v2 = 8; v2 = 14
u2 + v3 = 3; -6 + v3 = 3; v3 = 9

Для неизвестного потенциала u3 нулевую поставку можно разместить в клетках:
(3;1), v1=9
(3;2), v2=14
(3;3), v3=9
Для неизвестного потенциала u4 нулевую поставку можно разместить в клетках:
(4;1), v1=9
(4;2), v2=14
(4;3), v3=9
Для неизвестного потенциала v4 нулевую поставку можно разместить в клетках:
(1;4), u1=0
(2;4), u2=-6
Среди этих клеток, в которых может быть размещена нулевая поставка, наименьший тариф имеет клетка (4, 3) с c43 = 0. Следовательно, нулевую поставку размещаем в клетку (4, 3), и она становится условно занятой.
u4 + v3 = 0; -9 + v3 = 0; v3 = 9
Ранее поставленный псевдоноль из ячейки (1;2) убираем.
u4 + v4 = 0; -9 + v4 = 0; v4 = 9
u3 + v4 = 8; 9 + u3 = 8; u3 = -1

 

v1=9

v2=14

v3=9

v4=9

 

u1=0

9 [10]

15

10

1

 

u2=-6

3 [5]

8 [10]

3 [15]

2

 

u3=-1

6

2

5

8 [19]

 

u4=-9

0

0

0

0 [6]

 

 

 

 

 

 

 

Потребители/Базы

П1

П2

П3

П4

План
поставок

Б1

9 [10]

15

10

1

10

Б2

3 [5]

8 [10] -

3 [15] +

2

30

Б3

6

2 +

5

8 [19] -

19

Б4

0

0

0 -

0 [6] +

6

Заказы

15

10

15

25

 

Новый опорный план

Потребители/Базы

П1

П2

П3

П4

План
поставок

Б1

9 [10]

15

10

1

10

Б2

3 [5]

8 [10]

3 [15]

2

30

Б3

6

2 [0]

5

8 [19]

19

Б4

0

0

0

0 [6]

6

Заказы

15

10

15

25

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 9; 0 + v1 = 9; v1 = 9
u2 + v1 = 3; 9 + u2 = 3; u2 = -6
u2 + v2 = 8; -6 + v2 = 8; v2 = 14
u3 + v2 = 2; 14 + u3 = 2; u3 = -12
u3 + v4 = 8; -12 + v4 = 8; v4 = 20
u4 + v4 = 0; 20 + u4 = 0; u4 = -20
u2 + v3 = 3; -6 + v3 = 3; v3 = 9

 

v1=9

v2=14

v3=9

v4=9

 

u1=0

9 [10]

15

10

1

 

u2=-6

3 [5]

8 [10]

3 [15]

2

 

u3=-12

6

2

5

8 [19]

 

u4=-20

0

0

0

0 [6]

 

 

 

 

 

 

 

Потребители/Базы

П1

П2

П3

П4