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

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

(1;4): 0 + 7 > 5; ∆₁₄ = 0 + 7 - 5 = 2

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

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

	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

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

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

	1	2	3	4	5	Запасы
1	2[100]	3[5]	5[110]	5[25]	8	240
2	12	4	17	6[30]	5[80]	110
3	5	14	10	17	8[100]	100
4	21	3	17	7[95]	6	95
5	6	4[85]	20	16	7	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₃ = 5; 0 + v₃ = 5; v₃ = 5

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

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

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

u₃ + v₅ = 8; 4 + u₃ = 8; u₃ = 4

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

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

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

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

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

max(1,2) = 2

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

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

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

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

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

	1	2	3	4	5	Запасы
1	2[100]	3	5[110]	5[30]	8	240
2	12	4	17	6[30]	5[80]	110
3	5	14	10	17	8[100]	100
4	21	3[5]	17	7[90]	6	95
5	6	4[85]	20	16	7	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₃ = 5; 0 + v₃ = 5; v₃ = 5

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

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

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

u₃ + v₅ = 8; 4 + u₃ = 8; u₃ = 4

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

u₄ + v₂ = 3; 2 + v₂ = 3; v₂ = 1

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

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

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

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

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

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

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

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

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

	1	2	3	4	5	Запасы
1	2[70]	3	5[110]	5[60]	8	240
2	12	4	17	6	5[110]	110
3	5[30]	14	10	17	8[70]	100
4	21	3[5]	17	7[90]	6	95
5	6	4[85]	20	16	7	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₁ = 5; 2 + u₃ = 5; u₃ = 3

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

u₂ + v₅ = 5; 5 + u₂ = 5; u₂ = 0

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

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

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

u₄ + v₂ = 3; 2 + v₂ = 3; v₂ = 1

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

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

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

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

(5;5): 3 + 5 > 7; ∆₅₅ = 3 + 5 - 7 = 1

max(1,1) = 1

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

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

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

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

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

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

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

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

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

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

u₄ + v₂ = 3; 2 + v₂ = 3; v₂ = 1

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

u₄ + v₅ = 6; 2 + v₅ = 6; v₅ = 4

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

u₃ + v₅ = 8; 4 + u₃ = 8; u₃ = 4

u₃ + v₁ = 5; 4 + v₁ = 5; v₁ = 1

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