Задачи линейного программирования. _Готовое 84-04-3. Задача 1 3 Задача 2 6 Задача 3 9 Задача 4 15

Название	Задача 1 3 Задача 2 6 Задача 3 9 Задача 4 15
Анкор	Задачи линейного программирования
Дата	20.04.2022
Размер	109.17 Kb.
Формат файла
Имя файла	_Готовое 84-04-3.docx
Тип	Задача #486594
страница	5 из 5

1 2 3 4 5

Этап II. Улучшение опорного плана.

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

u₁ + v₁ = 13; 0 + v₁ = 13; v₁ = 13

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

u₃ + v₄ = 9; 11 + u₃ = 9; u₃ = -2

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

u₂ + v₂ = 4; 10 + u₂ = 4; u₂ = -6

u₂ + v₃ = 2; -6 + v₃ = 2; v₃ = 8

u₁ + v₅ = 3; 0 + v₅ = 3; v₅ = 3

	v₁=13	v₂=10	v₃=8	v₄=11	v₅=3
u₁=0	13[60]	10	6	11[10]	3[150]
u₂=-6	7	4[20]	2[160]	12	13
u₃=-2	14	8[160]	5	9[40]	17

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

(1;3): 0 + 8 > 6; ∆₁₃ = 0 + 8 - 6 = 2 > 0

(3;3): -2 + 8 > 5; ∆₃₃ = -2 + 8 - 5 = 1 > 0

max(2,1) = 2

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

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

	1	2	3	4	5	Запасы
1	13[60]	10	6[+]	11[10][-]	3[150]	220
2	7	4[20][+]	2[160][-]	12	13	180
3	14	8[160][-]	5	9[40][+]	17	200
Потребности	60	180	160	50	150

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

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

	B1	B2	B3	B4	B5	Запасы
A1	13[60]	10	6[10]	11	3[150]	220
A2	7	4[30]	2[150]	12	13	180
A3	14	8[150]	5	9[50]	17	200
Потребности	60	180	160	50	150

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

u₁ + v₁ = 13; 0 + v₁ = 13; v₁ = 13

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

u₂ + v₃ = 2; 6 + u₂ = 2; u₂ = -4

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

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

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

u₁ + v₅ = 3; 0 + v₅ = 3; v₅ = 3

	v₁=13	v₂=8	v₃=6	v₄=9	v₅=3
u₁=0	13[60]	10	6[10]	11	3[150]
u₂=-4	7	4[30]	2[150]	12	13
u₃=0	14	8[150]	5	9[50]	17

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

(2;1): -4 + 13 > 7; ∆₂₁ = -4 + 13 - 7 = 2 > 0

(3;3): 0 + 6 > 5; ∆₃₃ = 0 + 6 - 5 = 1 > 0

max(2,1) = 2

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

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

	1	2	3	4	5	Запасы
1	13[60][-]	10	6[10][+]	11	3[150]	220
2	7[+]	4[30]	2[150][-]	12	13	180
3	14	8[150]	5	9[50]	17	200
Потребности	60	180	160	50	150

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

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

	B1	B2	B3	B4	B5	Запасы
A1	13	10	6[70]	11	3[150]	220
A2	7[60]	4[30]	2[90]	12	13	180
A3	14	8[150]	5	9[50]	17	200
Потребности	60	180	160	50	150

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

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

u₂ + v₃ = 2; 6 + u₂ = 2; u₂ = -4

u₂ + v₁ = 7; -4 + v₁ = 7; v₁ = 11

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

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

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

u₁ + v₅ = 3; 0 + v₅ = 3; v₅ = 3

	v₁=11	v₂=8	v₃=6	v₄=9	v₅=3
u₁=0	13	10	6[70]	11	3[150]
u₂=-4	7[60]	4[30]	2[90]	12	13
u₃=0	14	8[150]	5	9[50]	17

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

(3;3): 0 + 6 > 5; ∆₃₃ = 0 + 6 - 5 = 1 > 0

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

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

	1	2	3	4	5	Запасы
1	13	10	6[70]	11	3[150]	220
2	7[60]	4[30][+]	2[90][-]	12	13	180
3	14	8[150][-]	5[+]	9[50]	17	200
Потребности	60	180	160	50	150

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

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

	B1	B2	B3	B4	B5	Запасы
A1	13	10	6[70]	11	3[150]	220
A2	7[60]	4[120]	2	12	13	180
A3	14	8[60]	5[90]	9[50]	17	200
Потребности	60	180	160	50	150

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

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

u₃ + v₃ = 5; 6 + u₃ = 5; u₃ = -1

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

u₂ + v₂ = 4; 9 + u₂ = 4; u₂ = -5

u₂ + v₁ = 7; -5 + v₁ = 7; v₁ = 12

u₃ + v₄ = 9; -1 + v₄ = 9; v₄ = 10

u₁ + v₅ = 3; 0 + v₅ = 3; v₅ = 3

	v₁=12	v₂=9	v₃=6	v₄=10	v₅=3
u₁=0	13	10	6[70]	11	3[150]
u₂=-5	7[60]	4[120]	2	12	13
u₃=-1	14	8[60]	5[90]	9[50]	17

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

Минимальные затраты составят: F(x) = 6*70 + 3*150 + 7*60 + 4*120 + 8*60 + 5*90 + 9*50 = 3150 ус. ед.

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 3-й пункт (70 ед.), в 5-й пункт (150 ед.)

Из 2-го склада необходимо груз направить в 1-й пункт (60 ед.), в 2-й пункт (120 ед.)

Из 3-го склада необходимо груз направить в 2-й пункт (60 ед.), в 3-й пункт (90 ед.), в 4-й пункт (50 ед.)

1 2 3 4 5