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

Искомый элемент равен 16

Для этого элемента запасы равны 85, потребности 85. Поскольку минимальным является 85, то вычитаем его.

x₅₄ = min(85,85) = 85.

2	x	x	x	8	0
12	4	x	x	x	0
x	14	10	x	x	0
x	x	17	7	x	0
x	x	x	16	x	85 - 85 = 0
0	0	0	85 - 85 = 0	0	0

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

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

2. Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 9. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 2*60 + 8*180 + 12*40 + 4*70 + 14*20 + 10*80 + 17*30 + 7*65 + 16*85 = 5725

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

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

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

u₂ + v₁ = 12; 2 + u₂ = 12; u₂ = 10

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

u₃ + v₂ = 14; -6 + u₃ = 14; u₃ = 20

u₃ + v₃ = 10; 20 + v₃ = 10; v₃ = -10

u₄ + v₃ = 17; -10 + u₄ = 17; u₄ = 27

u₄ + v₄ = 7; 27 + v₄ = 7; v₄ = -20

u₅ + v₄ = 16; -20 + u₅ = 16; u₅ = 36

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

	v1=2	v2=-6	v3=-10	v4=-20	v5=8
u1=0	2[60]	3	5	5	8[180]
u2=10	12[40]	4[70]	17	6	5
u3=20	5	14[20]	10[80]	17	8
u4=27	21	3	17[30]	7[65]	6
u5=36	6	4	20	16[85]	7

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

(2;5): 10 + 8 > 5; ∆₂₅ = 10 + 8 - 5 = 13

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

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

(4;1): 27 + 2 > 21; ∆₄₁ = 27 + 2 - 21 = 8

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

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

(5;1): 36 + 2 > 6; ∆₅₁ = 36 + 2 - 6 = 32

(5;2): 36 + -6 > 4; ∆₅₂ = 36 + -6 - 4 = 26

(5;3): 36 + -10 > 20; ∆₅₃ = 36 + -10 - 20 = 6

(5;5): 36 + 8 > 7; ∆₅₅ = 36 + 8 - 7 = 37

max(13,17,20,8,18,29,32,26,6,37) = 37

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

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

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

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

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

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

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

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

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

u₅ + v₄ = 16; -1 + v₄ = 16; v₄ = 17

u₄ + v₄ = 7; 17 + u₄ = 7; u₄ = -10

u₄ + v₃ = 17; -10 + v₃ = 17; v₃ = 27

u₃ + v₃ = 10; 27 + u₃ = 10; u₃ = -17

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

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

(1;3): 0 + 27 > 5; ∆₁₃ = 0 + 27 - 5 = 22

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

(2;3): 10 + 27 > 17; ∆₂₃ = 10 + 27 - 17 = 20

(2;4): 10 + 17 > 6; ∆₂₄ = 10 + 17 - 6 = 21

(2;5): 10 + 8 > 5; ∆₂₅ = 10 + 8 - 5 = 13

(5;3): -1 + 27 > 20; ∆₅₃ = -1 + 27 - 20 = 6

max(22,12,20,21,13,6) = 22

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

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

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

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

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

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

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

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

u₅ + v₄ = 16; -1 + v₄ = 16; v₄ = 17

u₄ + v₄ = 7; 17 + u₄ = 7; u₄ = -10

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

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

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

(2;4): 10 + 17 > 6; ∆₂₄ = 10 + 17 - 6 = 21

(2;5): 10 + 8 > 5; ∆₂₅ = 10 + 8 - 5 = 13

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

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

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

max(12,21,13,2,5,5) = 21

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

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

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

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

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

	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

Проверим оптимальность опорного плана. Найдем предварительные потенциалы 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₃ = 10; 5 + u₃ = 10; u₃ = 5

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

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

u₅ + v₄ = 16; -1 + v₄ = 16; v₄ = 17

u₂ + v₄ = 6; 17 + u₂ = 6; u₂ = -11

u₂ + v₂ = 4; -11 + v₂ = 4; v₂ = 15

u₄ + v₄ = 7; 17 + u₄ = 7; u₄ = -10

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