Транспортная логистика

 

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

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

Улучшение опорного плана. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0(табл.4.4).

 

Таблица 4.4

План прикрепления потребителей к поставщикам

	v1=1350	v2=2250	v3=3400	v4=4850	v5=3550
u1=0	1350         (7)	2550          (1)	550	650	1200
u2= -1700	195	550             (9)	1700          (6)	2950	1400
u3= -2800	700	850	600            (2)	2050          (4)	750            (3)
u4=-3060	1450	1850	550	1450	490            (5)
u5=-2700	800	1000	325	850	850            (5)

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi >cij Выбираем максимальную оценку свободной клетки (1;4): 4200 Для этого в перспективную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Таблица 4.5

План прикрепления потребителей к поставщикам с рассчитанным значениями потенциалов.

	v1=1350	v2=2250	v3=3400	v4=4850	v5=3550	запас
u1=0	1350       (7)	2550    (-)(1)	3400550	4850  (+)    650	35501200	8
u2= -1700	-350       195	550     (+) (9)	1700     (-)(6)	31502950	18501400	15
u3= -2800	-1450700	-550         850	600      (+)(2)	2050     (-)(4)	750            (3)	9
u4=-3060	-1710 1450	-810 1850	340550	17901450	490            (5)	5
u5=-2700	-1350800	-450 1000	700325	2150 850	850            (5)	5
потребность	7	10	8	4	13	42

Цикл приведен в таблице (1,2;1,4;2,2; 2,3; 3,2; 3,3; 3,4;  ). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 1. Прибавляем 1 к объемам грузов, стоящих в плюсовых клетках и вычитаем 1 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план[6].

Таблица 4.6

Скорректированный план прикрепления потребителей к поставщикам

Потребители		М1	М2	М3	М4	М5	Ресурсы поставщиков Ai
Поставщик		1350	800	2000	650	2150
C1	0	7  -    1350	800 2550	2000550	1+    650	21501200	8
C2	-300	1050195	10       550	5          1700	3502950	1850 1400	15
C3	1400	2750 +700	2200850	3             600	3-   2050	3             750	9
C4	-1660	-3101450	-8601850	340550	-10101450	5             490	5
C5	-1300	50800	-5001000	700 325	-650850	5             850	5
Потребность   Bj		7	10	8	4	13	42

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi>cij Выбираем максимальную оценку свободной клетки (3;1): 2050 Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

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

Таблица 4.7

Скорректированный план прикрепления потребителей к поставщикам

Потребители		М1	М2	М3	М4	М5	Ресурсы поставщиков Ai
Поставщик		1350	1000	1250	650	1400
C1	0	4          1350	1000  2550	1250       550	4            650	1400    1200	8
C2	450	1800  +195	10       550	5  -   1700	1100     2950	1850    1400	15
C3	-650	3        -700	350      850	3 +    600	0  2050	3             750	9
C4	-910	440       1450	90     1850	340        550	-260     1450	5             490	5
C5	-550	800         800	450    1000	700         325	100        850	5             850	5
Потребность   Bj		7	10	8	4	13	42

 

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

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

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

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

Скорректированный план прикрепления потребителей к поставщикам                                                                       Таблица 4.8

Потребители		М1	М2	М3	М4	М5	Ресурсы поставщиков Ai
Поставщик		1350	1705	2855	650	3005
C1	0	4-1350	1705  2550	2855      550	4650	3005 + 1200	8
C2	-1155	3+     195	10       550	2-    1700	-505   2950	245      1400	15
C3	-2255	-905     700	-550     850	6 +     600	-205  2050	3-       750	9
C4	-2515	-1165 1450	-810   1850	340        550	-1865 1450	5             490	5
C5	-2155	-805    800	-450   1000	700         325	-1505   850	5850	5
Потребность   Bj		7	10	8	4	13	42

 

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

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

Цикл приведен в таблице (1.1, 1.5 2.1;2.3; 3.3; 3.5). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

 

Скорректированный план прикрепления потребителей к поставщикамТаблица 4.9

Потребители		М1	М2	М3	М4	М5	Ресурсы поставщиков Ai
Поставщик		1350	1705	1100	650	1200
C1	0	2     1350	1705  2550	1100+550	4             650	2-   1200	8
C2	-1155	5       195	10        550	-55     1700	-505     2950	45         1400	15
C3	-450	900   700	1255    850	8 -     600	200      2050	1+      750	9
C4	-710	640 1450	995   1850	390      550	-60       1450	5             490	5
C5	-350	1000 800	1355  1000	750      325	300        850	5            850	5
Потребность   Bj		7	10	8	4	13	42

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi >cij Выбираем максимальную оценку свободной клетки (1;3): 550 Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

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

Таблица 4.10

Скорректированный план прикрепления потребителей к поставщикам

Потребители		М1	М2	М3	М4	М5	Ресурсы поставщиков Ai
Поставщик		1350	1705	550	650	700
C1	0	2      -   1350	1705 2550	2      +    550	4          650	700     1200	8
C2	-1155	5       +   195	10   -    550	-605     1700	-505    950	-455    1400	15
C3	50	1400       700	1755+  850	6     -      600	700   2050	3             750	9
C4	-210	1140     1450	1495  1850	340        550	440   1450	5             490	5
C5	150	1500       800	1855  1000	700        325	800     850	5             850	5
Потребность   Bj		7	10	8	4	13	42