Транспортная задача по "Логистике"

 

 

 

 

 

3.2(4250)

 

0       30	60   **2	40         5	60        6	0    15	160
60   **5	0     29	0         9	30  **5	60      *7	150
0       16	0       24	0        14	110    *6	30       26	140
0      13	0      28	90   **4	0       25	60        8	150
60	60	130	200	150	600=600

 

 

 

 

 

3.3(3830)

 

 

 

 

0       30	60   **2	40         5	60        6	0    15	160
60   **5	0     29	0         9	0    **5	90      *7	150
0       16	0       24	0        14	140    *6	0       26	140
0      13	0      28	90   **4	0       25	60        8	150
60	60	130	200	150	600=600

 

 

 

 

(3290)

 

 

Вывод: Метод потребовал 3 итерации, конечная стоимость 3290.Удешевление на 1200 единиц.

 

4.Метод потенциалов

Процедура построения потенциального (оптимального плана) состоит в следующем.

В качестве первого приближения к  оптимальному берется любой опорный  план, в моем случае план, составленный методом северо-западного угла. Для  этого плана потенциалы подчиняются  условию: сумма потенциалов равна  стоимости перевозки единицы  груза C=U+V. Потенциал одного пункта можно задать произвольно (например, равным нулю). Нулевым выбирается потенциал, соответствующий максимально заполненной строчке, или строчке, в которой сумма стоимостей минимальна.  После этого можно найти остальные потенциалы. Стоимости пустых ячеек должны быть больше суммы потенциалов C≥U+V. Если план не оптимален, то план может быть улучшен переносом перевозок по циклу.

Стоимость = 9455

60    30	0        2	5	50        6	50       15	160	U1 = 0
5	60     29	9	5	90        7	150	U2 = -8
16	24	130      14	6	10      26	140	U3 = 11
13	28	4	150    25	8	150	U4 = 19
60	60	130	200	150	600=600
V1 = 30	V2 = 37	V3 =3	V4 = 6	V5 = 15

 

 

 

 

 

 

4.1(9455)

 

30	60        2	5	50        6	50       15	160	U1 = 0
60       5	29	9	5	90        7	150	U2 = -8
16	24	130      14	6	10      26	140	U3 = 11
13	28	4	150    25	8	150	U4 = 19
60	60	130	200	150	600=600
V1 = 13	V2 = 2	V3 =3	V4 = 6	V5 = 15

 

 

 

 

 

4.2(7930)

 

30	60        2	5	50        6	50       15	160	U1 = 0
60       5	29	9	5	90        7	150	U2 = -8
16	24	14	130     6	10      26	140	U3 = 11
13	28	130   4	20    25	8	150	U4 = 19
60	60	130	200	150	600=600
V1 = 13	V2 = 2	V3 =-15	V4 = 6	V5 = 15

 

 

 

 

 

 

4.3(4160)

 

30	60        2	5	50        6	50       15	160	U1 = 0
60       5	29	9	5	90        7	150	U2 = -8
16	24	14	140     6	26	140	U3 = 0
13	28	130   4	10    25	10      8	150	U4 = 19
60	60	130	200	150	600=600
V1 = 13	V2 = 2	V3 =-15	V4 = 6	V5 = 15

 

 

 

 

 

 

 

4.4(3790)

 

 

 

 

 

30	60        2	5	60        6	40       15	160	U1 = 0
60       5	29	9	5	90        7	150	U2 = -8
16	24	14	140     6	26	140	U3 = 0
13	28	130   4	25	20      8	150	U4 = 6
60	60	130	200	150	600=600
V1 = 13	V2 = 2	V3 =-2	V4 = 6	V5 = 15

 

 

 

 

 

4.5(3530)

 

30	60        2	40    5	60        6	15	160	U1 = 0
60       5	29	9	5	90        7	150	U2 = -8
16	24	14	140     6	26	140	U3 = 0
13	28	90   4	25	60      8	150	U4 = 6
60	60	130	200	150	600=600
V1 = 13	V2 = 2	V3 =-2	V4 = 6	V5 = 15

 

 

 

 

 

(3290)

 

 

Вывод: Метод потребовал 5 итераций, конечная стоимость 3290.Удешевление на 6165 единиц.

 

 

 

 

 

 

 

 

 

 

 

5.Венгерский метод

Алгоритм метода содержит следующие шаги.

Шаг 1. Получение нулей в каждой сроке. Для этого в каждой строке определяют наименьший элемент, и его значение отнимают от всех элементов этой строки. Переход к шагу 3.

Шаг 3. Получение нулей в каждом столбце. В преобразованной таблице в каждом столбце определяют минимальный элемент, и его значение вычитают из всех элементов этого столбца. Переход к шагу 3.

Шаг 3. Поиск оптимального решения. Просматривают строку, содержащую наименьшее число нулей. Отмечают один из нулей этой строки и зачеркивают все остальные нули этой строки и того столбца, в котором находится отмеченный нуль. Аналогичные операции последовательно проводят для всех строк. Если назначение, которое получено при всех отмеченных нулях, является полным (т. е.. число отмеченных нулей равно п), то решение является оптимальным, в противном случае следует переходить к шагу 4.

Шаг 4. Поиск минимального набора строк и столбцов, содержащих все нули.

Для этого необходимо отметить:

1) все строки, в которых  не имеется ни одного отмеченного  нуля;

2) все столбцы, содержащие  перечеркнутый нуль хотя бы  в одной из отмеченных строк;

3)все строки, содержащие  отмеченные нули хотя бы в  одном из отмеченных столбцов.

Действия 2) и 3) повторяются  поочередно до тех пор, пока есть что  отмечать. После этого необходимо зачеркнуть каждую непомеченную строку и каждый помеченный столбец.

Цель этого шага – провести минимальное  число горизонтальных и вертикальных прямых, пересекающих по крайней мере один раз все нули.

Шаг 5. Перестановка некоторых нулей.

Взять наименьшее число  из тех клеток, через которые проведены  прямые. Вычесть его из каждого  числа, стоящего в не вычеркнутых  столбцах и прибавить к каждому  числу, стоящему в вычеркнутых строках. Эта операция не изменяет оптимального решения, после чего весь цикл расчета  повторить, начиная с шага 3.

 

30	2	5	6	15	160
5	29	9	5	7	150
16	24	14	6	26	140
13	28	4	25	8	150
60	60	130	200	150	600=600