оптимизация. Лабораторная работа 4 Оптимизация производственных связей между предприятиями

• Название: Лабораторная работа 4 Оптимизация производственных связей между предприятиями
• Дата: 23.12.2018
• Размер: 255.5 Kb.
• Имя файла: оптимизация.doc
• Тип: Лабораторная работа; #61497
• страница: 3 из 4

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

(1;5): 0 + 13 > 11; ∆₁₅ = 0 + 13 - 11 = 2 > 0

(1;6): 0 + 16 > 12; ∆₁₆ = 0 + 16 - 12 = 4 > 0

(2;5): -4 + 13 > 5; ∆₂₅ = -4 + 13 - 5 = 4 > 0

(2;6): -4 + 16 > 8; ∆₂₆ = -4 + 16 - 8 = 4 > 0

(4;6): -11 + 16 > 4; ∆₄₆ = -11 + 16 - 4 = 1 > 0

max(2,4,4,4,1) = 4

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

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

	1	2	3	4	5	6	Запасы
1	14[0][-]	8[20]	9[320]	10[0]	11	12[+]	340
2	10	4[280]	6	9	5	8	280
3	8[40][+]	12	13	15	11	10[80][-]	120
4	3[40]	8	16	7	2[300]	4	340
5	11	9	10	12	7	5[200]	200
6	5[120]	7	13	18	21	15	120
7	9	15	18	2[200]	9	20	200
Потребности	200	300	320	200	300	280

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

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

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 8; 0 + v₂ = 8; v₂ = 8

u₂ + v₂ = 4; 8 + u₂ = 4; u₂ = -4

u₁ + v₃ = 9; 0 + v₃ = 9; v₃ = 9

u₁ + v₄ = 10; 0 + v₄ = 10; v₄ = 10

u₇ + v₄ = 2; 10 + u₇ = 2; u₇ = -8

u₁ + v₆ = 12; 0 + v₆ = 12; v₆ = 12

u₃ + v₆ = 10; 12 + u₃ = 10; u₃ = -2

u₃ + v₁ = 8; -2 + v₁ = 8; v₁ = 10

u₄ + v₁ = 3; 10 + u₄ = 3; u₄ = -7

u₄ + v₅ = 2; -7 + v₅ = 2; v₅ = 9

u₆ + v₁ = 5; 10 + u₆ = 5; u₆ = -5

u₅ + v₆ = 5; 12 + u₅ = 5; u₅ = -7

	v1=10	v2=8	v3=9	v4=10	v5=9	v6=12
u1=0	14	8[20]	9[320]	10[0]	11	12[0]
u2=-4	10	4[280]	6	9	5	8
u3=-2	8[40]	12	13	15	11	10[80]
u4=-7	3[40]	8	16	7	2[300]	4
u5=-7	11	9	10	12	7	5[200]
u6=-5	5[120]	7	13	18	21	15
u7=-8	9	15	18	2[200]	9	20

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

(4;6): -7 + 12 > 4; ∆₄₆ = -7 + 12 - 4 = 1 > 0

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

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

	1	2	3	4	5	6	Запасы
1	14	8[20]	9[320]	10[0]	11	12[0]	340
2	10	4[280]	6	9	5	8	280
3	8[40][+]	12	13	15	11	10[80][-]	120
4	3[40][-]	8	16	7	2[300]	4[+]	340
5	11	9	10	12	7	5[200]	200
6	5[120]	7	13	18	21	15	120
7	9	15	18	2[200]	9	20	200
Потребности	200	300	320	200	300	280

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

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

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 8; 0 + v₂ = 8; v₂ = 8

u₂ + v₂ = 4; 8 + u₂ = 4; u₂ = -4

u₁ + v₃ = 9; 0 + v₃ = 9; v₃ = 9

u₁ + v₄ = 10; 0 + v₄ = 10; v₄ = 10

u₇ + v₄ = 2; 10 + u₇ = 2; u₇ = -8

u₁ + v₆ = 12; 0 + v₆ = 12; v₆ = 12

u₃ + v₆ = 10; 12 + u₃ = 10; u₃ = -2

u₃ + v₁ = 8; -2 + v₁ = 8; v₁ = 10

u₆ + v₁ = 5; 10 + u₆ = 5; u₆ = -5

u₄ + v₆ = 4; 12 + u₄ = 4; u₄ = -8

u₄ + v₅ = 2; -8 + v₅ = 2; v₅ = 10

u₅ + v₆ = 5; 12 + u₅ = 5; u₅ = -7

	v1=10	v2=8	v3=9	v4=10	v5=10	v6=12
u1=0	14	8[20]	9[320]	10[0]	11	12[0]
u2=-4	10	4[280]	6	9	5	8
u3=-2	8[80]	12	13	15	11	10[40]
u4=-8	3	8	16	7	2[300]	4[40]
u5=-7	11	9	10	12	7	5[200]
u6=-5	5[120]	7	13	18	21	15
u7=-8	9	15	18	2[200]	9	20