логистика минимальная решение

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

(1;2): 0 + 15 > 3; ∆₁₂ = 0 + 15 - 3 = 12

(1;4): 0 + 17 > 5; ∆₁₄ = 0 + 17 - 5 = 12

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

(3;2): 5 + 15 > 14; ∆₃₂ = 5 + 15 - 14 = 6

(3;4): 5 + 17 > 17; ∆₃₄ = 5 + 17 - 17 = 5

(3;5): 5 + 8 > 8; ∆₃₅ = 5 + 8 - 8 = 5

(4;2): -10 + 15 > 3; ∆₄₂ = -10 + 15 - 3 = 2

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

max(12,12,2,6,5,5,2,10) = 12

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

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

	1	2	3	4	5	Запасы
1	2[100]	3[+]	5[10]	5	8[130][-]	240
2	12	4[90][-]	17	6[20][+]	5	110
3	5	14	10[100]	17	8	100
4	21	3	17	7[95]	6	95
5	6	4	20	16[35][-]	7[50][+]	85
Потребности	100	90	110	150	180

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

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

	1	2	3	4	5	Запасы
1	2[100]	3[35]	5[10]	5	8[95]	240
2	12	4[55]	17	6[55]	5	110
3	5	14	10[100]	17	8	100
4	21	3	17	7[95]	6	95
5	6	4	20	16	7[85]	85
Потребности	100	90	110	150	180

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

u₁ + v₁ = 2; 0 + v₁ = 2; v₁ = 2

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

u₂ + v₂ = 4; 3 + u₂ = 4; u₂ = 1

u₂ + v₄ = 6; 1 + v₄ = 6; v₄ = 5

u₄ + v₄ = 7; 5 + u₄ = 7; u₄ = 2

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

u₃ + v₃ = 10; 5 + u₃ = 10; u₃ = 5

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

u₅ + v₅ = 7; 8 + u₅ = 7; u₅ = -1

	v1=2	v2=3	v3=5	v4=5	v5=8
u1=0	2[100]	3[35]	5[10]	5	8[95]
u2=1	12	4[55]	17	6[55]	5
u3=5	5	14	10[100]	17	8
u4=2	21	3	17	7[95]	6
u5=-1	6	4	20	16	7[85]

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

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

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

(3;5): 5 + 8 > 8; ∆₃₅ = 5 + 8 - 8 = 5

(4;2): 2 + 3 > 3; ∆₄₂ = 2 + 3 - 3 = 2

(4;5): 2 + 8 > 6; ∆₄₅ = 2 + 8 - 6 = 4

max(4,2,5,2,4) = 5

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

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

	1	2	3	4	5	Запасы
1	2[100]	3[35]	5[10][+]	5	8[95][-]	240
2	12	4[55]	17	6[55]	5	110
3	5	14	10[100][-]	17	8[+]	100
4	21	3	17	7[95]	6	95
5	6	4	20	16	7[85]	85
Потребности	100	90	110	150	180

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

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

	1	2	3	4	5	Запасы
1	2[100]	3[35]	5[105]	5	8	240
2	12	4[55]	17	6[55]	5	110
3	5	14	10[5]	17	8[95]	100
4	21	3	17	7[95]	6	95
5	6	4	20	16	7[85]	85
Потребности	100	90	110	150	180

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

u₁ + v₁ = 2; 0 + v₁ = 2; v₁ = 2

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

u₂ + v₂ = 4; 3 + u₂ = 4; u₂ = 1

u₂ + v₄ = 6; 1 + v₄ = 6; v₄ = 5

u₄ + v₄ = 7; 5 + u₄ = 7; u₄ = 2

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

u₃ + v₃ = 10; 5 + u₃ = 10; u₃ = 5

u₃ + v₅ = 8; 5 + v₅ = 8; v₅ = 3

u₅ + v₅ = 7; 3 + u₅ = 7; u₅ = 4

	v1=2	v2=3	v3=5	v4=5	v5=3
u1=0	2[100]	3[35]	5[105]	5	8
u2=1	12	4[55]	17	6[55]	5
u3=5	5	14	10[5]	17	8[95]
u4=2	21	3	17	7[95]	6
u5=4	6	4	20	16	7[85]

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

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

(4;2): 2 + 3 > 3; ∆₄₂ = 2 + 3 - 3 = 2

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

max(2,2,3) = 3

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

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

	1	2	3	4	5	Запасы
1	2[100]	3[35][-]	5[105][+]	5	8	240
2	12	4[55]	17	6[55]	5	110
3	5	14	10[5][-]	17	8[95][+]	100
4	21	3	17	7[95]	6	95
5	6	4[+]	20	16	7[85][-]	85
Потребности	100	90	110	150	180

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

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

	1	2	3	4	5	Запасы
1	2[100]	3[30]	5[110]	5	8	240
2	12	4[55]	17	6[55]	5	110
3	5	14	10	17	8[100]	100
4	21	3	17	7[95]	6	95
5	6	4[5]	20	16	7[80]	85
Потребности	100	90	110	150	180

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

u₁ + v₁ = 2; 0 + v₁ = 2; v₁ = 2

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

u₂ + v₂ = 4; 3 + u₂ = 4; u₂ = 1

u₂ + v₄ = 6; 1 + v₄ = 6; v₄ = 5

u₄ + v₄ = 7; 5 + u₄ = 7; u₄ = 2

u₅ + v₂ = 4; 3 + u₅ = 4; u₅ = 1

u₅ + v₅ = 7; 1 + v₅ = 7; v₅ = 6

u₃ + v₅ = 8; 6 + u₃ = 8; u₃ = 2

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

	v1=2	v2=3	v3=5	v4=5	v5=6
u1=0	2[100]	3[30]	5[110]	5	8
u2=1	12	4[55]	17	6[55]	5
u3=2	5	14	10	17	8[100]
u4=2	21	3	17	7[95]	6
u5=1	6	4[5]	20	16	7[80]

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

(2;5): 1 + 6 > 5; ∆₂₅ = 1 + 6 - 5 = 2

(4;2): 2 + 3 > 3; ∆₄₂ = 2 + 3 - 3 = 2

(4;5): 2 + 6 > 6; ∆₄₅ = 2 + 6 - 6 = 2

max(2,2,2) = 2

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

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

	1	2	3	4	5	Запасы
1	2[100]	3[30]	5[110]	5	8	240
2	12	4[55][-]	17	6[55]	5[+]	110
3	5	14	10	17	8[100]	100
4	21	3	17	7[95]	6	95
5	6	4[5][+]	20	16	7[80][-]	85
Потребности	100	90	110	150	180

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

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

	1	2	3	4	5	Запасы
1	2[100]	3[30]	5[110]	5	8	240
2	12	4	17	6[55]	5[55]	110
3	5	14	10	17	8[100]	100
4	21	3	17	7[95]	6	95
5	6	4[60]	20	16	7[25]	85
Потребности	100	90	110	150	180

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

u₁ + v₁ = 2; 0 + v₁ = 2; v₁ = 2

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

u₅ + v₂ = 4; 3 + u₅ = 4; u₅ = 1

u₅ + v₅ = 7; 1 + v₅ = 7; v₅ = 6

u₂ + v₅ = 5; 6 + u₂ = 5; u₂ = -1

u₂ + v₄ = 6; -1 + v₄ = 6; v₄ = 7

u₄ + v₄ = 7; 7 + u₄ = 7; u₄ = 0

u₃ + v₅ = 8; 6 + u₃ = 8; u₃ = 2

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

	v1=2	v2=3	v3=5	v4=7	v5=6
u1=0	2[100]	3[30]	5[110]	5	8
u2=-1	12	4	17	6[55]	5[55]
u3=2	5	14	10	17	8[100]
u4=0	21	3	17	7[95]	6
u5=1	6	4[60]	20	16	7[25]