Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

Главная > Реферат >Математика

Сохрани ссылку на реферат в одной из сетей:

max(16,19,19) = 19

Выбираем максимальную оценку свободной клетки (1;5): 18

Для этого в перспективную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.

1

2

3

4

5

Запасы

1

13[20]

9[20]

15[13][-]

3

18[+]

53

2

7

8

6[7][+]

10[10][-]

9

17

3

16

4

10

11[3][+]

29[27][-]

30

Потребности

20

20

20

13

27

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 4) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

1

2

3

4

5

Запасы

1

13[20]

9[20]

15[3]

3

18[10]

53

2

7

8

6[17]

10

9

17

3

16

4

10

11[13]

29[17]

30

Потребности

20

20

20

13

27

4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1 + v1 = 13; 0 + v1 = 13; v1 = 13

u1 + v2 = 9; 0 + v2 = 9; v2 = 9

u1 + v3 = 15; 0 + v3 = 15; v3 = 15

u2 + v3 = 6; 15 + u2 = 6; u2 = -9

u1 + v5 = 18; 0 + v5 = 18; v5 = 18

u3 + v5 = 29; 18 + u3 = 29; u3 = 11

u3 + v4 = 11; 11 + v4 = 11; v4 = 0

v1=13

v2=9

v3=15

v4=0

v5=18

u1=0

13[20]

9[20]

15[3]

3

18[10]

u2=-9

7

8

6[17]

10

9

u3=11

16

4

10

11[13]

29[17]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

(3;1): 11 + 13 > 16; ∆31 = 11 + 13 - 16 = 8

(3;2): 11 + 9 > 4; ∆32 = 11 + 9 - 4 = 16

(3;3): 11 + 15 > 10; ∆33 = 11 + 15 - 10 = 16

max(8,16,16) = 16

Выбираем максимальную оценку свободной клетки (3;2): 4

Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.

1

2

3

4

5

Запасы

1

13[20]

9[20][-]

15[3]

3

18[10][+]

53

2

7

8

6[17]

10

9

17

3

16

4[+]

10

11[13]

29[17][-]

30

Потребности

20

20

20

13

27

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 5) = 17. Прибавляем 17 к объемам грузов, стоящих в плюсовых клетках и вычитаем 17 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

1

2

3

4

5

Запасы

1

13[20]

9[3]

15[3]

3

18[27]

53

2

7

8

6[17]

10

9

17

3

16

4[17]

10

11[13]

29

30

Потребности

20

20

20

13

27

4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1 + v1 = 13; 0 + v1 = 13; v1 = 13

u1 + v2 = 9; 0 + v2 = 9; v2 = 9

u3 + v2 = 4; 9 + u3 = 4; u3 = -5

u3 + v4 = 11; -5 + v4 = 11; v4 = 16

u1 + v3 = 15; 0 + v3 = 15; v3 = 15

u2 + v3 = 6; 15 + u2 = 6; u2 = -9

u1 + v5 = 18; 0 + v5 = 18; v5 = 18

v1=13

v2=9

v3=15

v4=16

v5=18

u1=0

13[20]

9[3]

15[3]

3

18[27]

u2=-9

7

8

6[17]

10

9

u3=-5

16

4[17]

10

11[13]

29

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

(1;4): 0 + 16 > 3; ∆14 = 0 + 16 - 3 = 13

Выбираем максимальную оценку свободной клетки (1;4): 3

Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.

1

2

3

4

5

Запасы

1

13[20]

9[3][-]

15[3]

3[+]

18[27]

53

2

7

8

6[17]

10

9

17

3

16

4[17][+]

10

11[13][-]

29

30

Потребности

20

20

20

13

27

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 3. Прибавляем 3 к объемам грузов, стоящих в плюсовых клетках и вычитаем 3 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

1

2

3

4

5

Запасы

1

13[20]

9

15[3]

3[3]

18[27]

53

2

7

8

6[17]

10

9

17

3

16

4[20]

10

11[10]

29

30

Потребности

20

20

20

13

27

4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1 + v1 = 13; 0 + v1 = 13; v1 = 13

u1 + v3 = 15; 0 + v3 = 15; v3 = 15

u2 + v3 = 6; 15 + u2 = 6; u2 = -9

u1 + v4 = 3; 0 + v4 = 3; v4 = 3

u3 + v4 = 11; 3 + u3 = 11; u3 = 8

u3 + v2 = 4; 8 + v2 = 4; v2 = -4

u1 + v5 = 18; 0 + v5 = 18; v5 = 18

v1=13

v2=-4

v3=15

v4=3

v5=18

u1=0

13[20]

9

15[3]

3[3]

18[27]

u2=-9

7

8

6[17]

10

9

u3=8

16

4[20]

10

11[10]

29

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

(3;1): 8 + 13 > 16; ∆31 = 8 + 13 - 16 = 5

(3;3): 8 + 15 > 10; ∆33 = 8 + 15 - 10 = 13

max(5,13) = 13

Выбираем максимальную оценку свободной клетки (3;3): 10

Для этого в перспективную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.

1

2

3

4

5

Запасы

1

13[20]

9

15[3][-]

3[3][+]

18[27]

53

2

7

8

6[17]

10

9

17

3

16

4[20]

10[+]

11[10][-]

29

30

Потребности

20

20

20

13

27

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 3) = 3. Прибавляем 3 к объемам грузов, стоящих в плюсовых клетках и вычитаем 3 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

1

2

3

4

5

Запасы

1

13[20]

9

15

3[6]

18[27]

53

2

7

8

6[17]

10

9

17

3

16

4[20]

10[3]

11[7]

29

30

Потребности

20

20

20

13

27

4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1 + v1 = 13; 0 + v1 = 13; v1 = 13

u1 + v4 = 3; 0 + v4 = 3; v4 = 3

u3 + v4 = 11; 3 + u3 = 11; u3 = 8

u3 + v2 = 4; 8 + v2 = 4; v2 = -4

u3 + v3 = 10; 8 + v3 = 10; v3 = 2

u2 + v3 = 6; 2 + u2 = 6; u2 = 4

u1 + v5 = 18; 0 + v5 = 18; v5 = 18

v1=13

v2=-4

v3=2

v4=3

v5=18

u1=0

13[20]

9

15

3[6]

18[27]

u2=4

7

8

6[17]

10

9

u3=8

16

4[20]

10[3]

11[7]

29

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

(2;1): 4 + 13 > 7; ∆21 = 4 + 13 - 7 = 10

(2;5): 4 + 18 > 9; ∆25 = 4 + 18 - 9 = 13

(3;1): 8 + 13 > 16; ∆31 = 8 + 13 - 16 = 5

max(10,13,5) = 13

Выбираем максимальную оценку свободной клетки (2;5): 9

Для этого в перспективную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.

1

2

3

4

5

Запасы

1

13[20]

9

15

3[6][+]

18[27][-]

53

2

7

8

6[17][-]

10

9[+]

17

3

16

4[20]

10[3][+]

11[7][-]

29

30

Потребности

20

20

20

13

27

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 7. Прибавляем 7 к объемам грузов, стоящих в плюсовых клетках и вычитаем 7 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

1

2

3

4

5

Запасы

1

13[20]

9

15

3[13]

18[20]

53

2

7

8

6[10]

10

9[7]

17

3

16

4[20]

10[10]

11

29

30

Потребности

20

20

20

13

27

4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1 + v1 = 13; 0 + v1 = 13; v1 = 13

u1 + v4 = 3; 0 + v4 = 3; v4 = 3

u1 + v5 = 18; 0 + v5 = 18; v5 = 18

u2 + v5 = 9; 18 + u2 = 9; u2 = -9

u2 + v3 = 6; -9 + v3 = 6; v3 = 15

u3 + v3 = 10; 15 + u3 = 10; u3 = -5

u3 + v2 = 4; -5 + v2 = 4; v2 = 9

v1=13

v2=9

v3=15

v4=3

v5=18

u1=0

13[20]

9

15

3[13]

18[20]

u2=-9

7

8

6[10]

10

9[7]

u3=-5

16

4[20]

10[10]

11

29

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.

Минимальные затраты составят:

F(x) = 13*20 + 3*13 + 18*20 + 6*10 + 9*7 + 4*20 + 10*10 = 962



Скачать работу

Похожие работы: