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

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

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

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

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

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

	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[80]	12	13	15	11	10[40]	120
4	3	8	16	7	2[300][-]	4[40][+]	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

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

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 6) = 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₅ = 5; -4 + v₅ = 5; v₅ = 9

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

u₄ + v₆ = 4; -7 + v₆ = 4; v₆ = 11

u₃ + v₆ = 10; 11 + u₃ = 10; u₃ = -1

u₃ + v₁ = 8; -1 + v₁ = 8; v₁ = 9

u₆ + v₁ = 5; 9 + u₆ = 5; u₆ = -4

u₅ + v₆ = 5; 11 + u₅ = 5; u₅ = -6

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

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

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

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

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

Минимальные затраты составят: F(x) = 8*20 + 9*320 + 4*280 + 8*80 + 10*40 + 2*300 + 4*40 + 5*200 + 5*120 + 2*200 = 7960

Вывод

Из 1-го склада необходимо груз направить к 2-у потребителю (20), к 3-у потребителю (320). Из 2-го склада необходимо весь груз направить к 2-у потребителю. Из 3-го склада необходимо груз направить к 1-у потребителю (80), к 6-у потребителю (40). Из 4-го склада необходимо груз направить к 5-у потребителю (300), к 6-у потребителю (40). Из 5-го склада необходимо весь груз направить к 6-у потребителю. Из 6-го склада необходимо весь груз направить к 1-у потребителю. Из 7-го склада необходимо весь груз направить к 4-у потребителю.

Задача имеет множество оптимальных планов, поскольку оценка для (1;4),(2;5) равна 0.