Контрольная работа по дисциплине «Методы оптимальных решений»

Автор работы: Пользователь скрыл имя, 12 Января 2015 в 15:44, контрольная работа

Краткое описание

1. Задачу решите графическим методом.
2. Задание 2
Задачу решите симплексным методом.
Задание 3
Составьте оптимальный план перевозки грузов от поставщиков с грузами 160, 60, 180 т к потребителям с запросами 80, 60, 60 и 200 т. Стоимости перевозок единицы груза от каждого поставщика к каждому потребителю даны матрицей

Вложенные файлы: 1 файл

МОР.doc

— 214.00 Кб (Скачать файл)

Цикл приведен в таблице (1,4 → 1,3 → 2,3 → 2,4).

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

 

1

2

3

4

Запасы

1

8[80]

6[60]

9

2[20]

160

2

7

16

12[60]

12[0]

60

3

6

15

8

3[180]

180

Потребности

80

60

60

200

 

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

u1 + v1 = 8; 0 + v1 = 8; v1 = 8

u1 + v2 = 6; 0 + v2 = 6; v2 = 6

u1 + v4 = 2; 0 + v4 = 2; v4 = 2

u2 + v4 = 12; 2 + u2 = 12; u2 = 10

u2 + v3 = 12; 10 + v3 = 12; v3 = 2

u3 + v4 = 3; 2 + u3 = 3; u3 = 1

 

v1=8

v2=6

v3=2

v4=2

u1=0

8[80]

6[60]

9

2[20]

u2=10

7

16

12[60]

12[0]

u3=1

6

15

8

3[180]


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

(2;1): 10 + 8 > 7; ∆21 = 10 + 8 - 7 = 11

(3;1): 1 + 8 > 6; ∆31 = 1 + 8 - 6 = 3

max(11,3) = 11

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

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

 

1

2

3

4

Запасы

1

8[80][-]

6[60]

9

2[20][+]

160

2

7[+]

16

12[60]

12[0][-]

60

3

6

15

8

3[180]

180

Потребности

80

60

60

200

 

Цикл приведен в таблице (2,1 → 2,4 → 1,4 → 1,1).

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

 

1

2

3

4

Запасы

1

8[80]

6[60]

9

2[20]

160

2

7[0]

16

12[60]

12

60

3

6

15

8

3[180]

180

Потребности

80

60

60

200

 

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

u1 + v1 = 8; 0 + v1 = 8; v1 = 8

u2 + v1 = 7; 8 + u2 = 7; u2 = -1

u2 + v3 = 12; -1 + v3 = 12; v3 = 13

u1 + v2 = 6; 0 + v2 = 6; v2 = 6

u1 + v4 = 2; 0 + v4 = 2; v4 = 2

u3 + v4 = 3; 2 + u3 = 3; u3 = 1

 

v1=8

v2=6

v3=13

v4=2

u1=0

8[80]

6[60]

9

2[20]

u2=-1

7[0]

16

12[60]

12

u3=1

6

15

8

3[180]


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

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

(3;1): 1 + 8 > 6; ∆31 = 1 + 8 - 6 = 3

(3;3): 1 + 13 > 8; ∆33 = 1 + 13 - 8 = 6

max(4,3,6) = 6

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

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

 

1

2

3

4

Запасы

1

8[80][-]

6[60]

9

2[20][+]

160

2

7[0][+]

16

12[60][-]

12

60

3

6

15

8[+]

3[180][-]

180

Потребности

80

60

60

200

 

Цикл приведен в таблице (3,3 → 3,4 → 1,4 → 1,1 → 2,1 → 2,3).

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

 

1

2

3

4

Запасы

1

8[20]

6[60]

9

2[80]

160

2

7[60]

16

12

12

60

3

6

15

8[60]

3[120]

180

Потребности

80

60

60

200

 

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

u1 + v1 = 8; 0 + v1 = 8; v1 = 8

u2 + v1 = 7; 8 + u2 = 7; u2 = -1

u1 + v2 = 6; 0 + v2 = 6; v2 = 6

u1 + v4 = 2; 0 + v4 = 2; v4 = 2

u3 + v4 = 3; 2 + u3 = 3; u3 = 1

u3 + v3 = 8; 1 + v3 = 8; v3 = 7

 

v1=8

v2=6

v3=7

v4=2

u1=0

8[20]

6[60]

9

2[80]

u2=-1

7[60]

16

12

12

u3=1

6

15

8[60]

3[120]


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

(3;1): 1 + 8 > 6; ∆31 = 1 + 8 - 6 = 3

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

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

 

1

2

3

4

Запасы

1

8[20][-]

6[60]

9

2[80][+]

160

2

7[60]

16

12

12

60

3

6[+]

15

8[60]

3[120][-]

180

Потребности

80

60

60

200

 

Цикл приведен в таблице (3,1 → 3,4 → 1,4 → 1,1).

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

 

1

2

3

4

Запасы

1

8

6[60]

9

2[100]

160

2

7[60]

16

12

12

60

3

6[20]

15

8[60]

3[100]

180

Потребности

80

60

60

200

 

Информация о работе Контрольная работа по дисциплине «Методы оптимальных решений»