Методы оптимального решения транспортной задачи с дополнительными условиями (ограничениями)

Строим матрицу  оценок:

       0 0 -2 -10 -12 -5

       4 0  0  -1   -4   0

       7 2 зп   0  зп   1

       7 9 0    0   гп   3

       8 9 8    0    0    5 

 

Строим цикл пересчета: Min(240;180)=180

 

 

 

Таблица 9. 4 этап решения

Склады	Кондитерские цеха
	1360	1140	1180	1260	680		180	Vi
1600	4[1360]	6[60]	8	2	2		0[180]	0
1400	3	1[1080]	5[320]	6	5		0	5
400	5	2	1	6[400]	3	0		6
1100	3	7	2[860]	4[240]	9		0	8
1300	2	5	8	2[620]	4[680]		0	10
Uj	-4	-6	-10	-12	-14		0

Строим матрицу  оценок:

       0 0 -2 -10 -12  0

       4 0  0  -1   -4   5

       7 2 зп   0  зп   6

       7 9 0    0   гп   8

       8 9 8    0    0   10 

Строим цикл пересчета: Min(60;320)=60

 

 

Таблица 10. 5 этап решения

Склады	Кондитерские  цеха
	1360	1140	1180	1260	680		180	Vi
1600	4[1360]	6	8[60]	2	2		0[180]	0
1400	3	1[1140]	5[260]	6	5		0	3
400	5	2	1	6[400]	3	0		4
1100	3	7	2[860]	4[240]	9		0	6
1300	2	5	8	2[620]	4[680]		0	8
Uj	-4	-4	-8	-10	-12		0

Строим матрицу  оценок:

       0 2 0   -8 -10  0

       2 0  0  -1   -4   3

       5 2 зп   0  зп   4

       5 9 0    0   гп   6

       6 8 8    0    0   8 

Строим цикл пересчета: Min(260;240)=240

 

 

Таблица 11. 6 этап решения

Склады	Кондитерские  цеха
	1360	1140	1180	1260	680		180	Vi
1600	4[1360]	6	8[60]	2	2		0[180]	0
1400	3	1[1140]	5[20]	6[240]	5		0	3
400	5	2	1	6[400]	3	0		3
1100	3	7	2[1100]	4	9		0	6
1300	2	5	8	2[620]	4[680]		0	7
Uj	-4	-4	-8	-9	-12		0

 

 

 

 

Строим матрицу оценок:

       0 2 0   -7  -10 0

       2 0  0  0   -4   3

       5 2 зп   0  зп   3

       5 9 0    1  гп   6

       6 8 8    0    0   7 

Строим цикл пересчета: Min(60;240)=240

 

 

Таблица 12. 7 этап решения

Склады	Кондитерские  цеха
	1360	1140	1180	1260	680		180	Vi
1600	4[1360]	6	8	2[60]	2		0[180]	0
1400	3	1[1140]	5[80]	6[180]	5		0	-4
400	5	2	1	6[400]	3	0		-4
1100	3	7	2[1100]	4	9		0	-1
1300	2	5	8	2[620]	4[680]		0	0
Uj	-4	-4	-1	-2	-4		0

 

Строим матрицу  оценок:

       0 2 7   0  -2  0

       2 0  0    0  -3   -4

       5 2 зп   0  зп   -4

       5 9 0    4  гп   -1

       6 8 8    0    0   0* 

В матрице оценок количество отрицательных значений не сокращается, а наоборот увеличивается, значит предыдущий этап будет самым оптимальным. По нему и находим целевую функцию (минимальные затраты)

F=4*1360+1*1140+8*60+5*20+2*1100+6*240+6*400+2*620+4*680=14760

Если сравнить с тем, что мы получили методом  северо-западного угла, то разница 4560.

Вывод: метод потенциалов значительно сокращает издержки, находит оптимальный вариант. Но его удобно реализовать, когда в количество поставщиков и потребителей относительно небольшое и мало ограничений. Как мы убедились, если увеличить количество поставщиков и потребителей и ввести несколько ограничений, то реализация задачи методом потенциалов становится  трудоемкой  и очень длительной.[4]

2.4 «Потолок»  транспортных перевозок

Такая задача актуальна, когда больше, чем указано поставлять нельзя. Например, если перевозка идет по мосту, объем перевозок, по которому ограничен. Или вместимость машин ограничена, и большее количество объема не влезет.

Рассмотрим  пример такой задачи. Первоначальные данные к задаче нам даны в таблице 13.

Таблица 13. Первоначальные данные

Склады	Магазины
		1	2	3	4	5	Запас
1	16	10 VV	18	22	26	200
2	30	16	19	18 VV	32	500
3	21	22	26	24	14 V	350
4	25	17	16 V	19	12 VV	550
5	15 V	23	24	26	13V	200
Спрос	200	400	300	400	500

Если таблица стоимостей велика, то перебор всех элементов  затруднителен. В этом случае используют метод двойного предпочтения, суть которого  заключается  в  следующем:  
 В каждом столбце отмечают знаком V клетку с наименьшей стоимостью. Затем тоже проделывают в каждой строке. В результате некоторые клетки имеют отметку VV. В них находится минимальная стоимость, как по столбцу, так и по строке. В эти клетки помещают максимально возможные объемы перевозок, каждый раз, исключая из рассмотрения соответствующие столбцы или строки. Затем распределяют перевозки по ячейкам, отмеченным знаком V. В оставшейся части таблицы перевозки распределяют по наименьшей стоимости.[5]

Полученное решение мы видим в таблице 14.

Таблица 14. Метод двойного предпочтения

Склады	Магазины
		1	2	3	4	5	Запас
1	16	10 [200]	18	22	26	300
2	30	16 [100]	19	18 [400]	32	500
3	21	22 [100]	26 [250]	24	14	350
4	25	17	16 [50]	19	12 [500]	550
5	15 [200]	23	24	26	13	600
Спрос	200	400	300	400	500

 

F= 15*200+10*200+16*100+22*100+26*250+16*50+18*400+12*500=29300

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

Установим «потолок»  перевозки x<=400 и сравним полученный результат.

Таблица 15. Установление «потолка» объема перевозок

Склады	Магазины
		1	2	3	4	5	Запас
1	16	10 [200]	18	22	26	300
2	30	16 [100]	19	18 [400]	32	500
3	21	22 [100]	26 [250]	24	14	350
4	25	17	16 [50]	19	12 [400]	550
5	15 [200]	23	24	26	13 [100]	600
Спрос	200	400	300	400	500

В нашем примере  мы изменили лишь поставку от 4 поставщика 5 потребителю, потому что она оказалась большее 400 единиц.

Посмотрим, как изменилась наша целевая функция:

F=15*200+10*200+16*100+22*100+26*250+16*50+18*400+12*400+13*100 = =29400

Изменения в  целевой функции произошли небольшие, в этом тоже плюс метода двойного предпочтения.

2.5 «Пол» транспортных  перевозок

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

Алгоритм решения  методом дифференциальных рент:

1. Записать матрицу стоимостей перевозок, спрос потребителей и запасы поставщиков.
2. Для каждого потребителя найти поставщика с минимальной стоимостью перевозки.
3. Условно обеспечить каждого потребителя за счет поставщика с минимальной стоимостью перевозки.
4. Определить избытки или недостатки по каждому поставщику.
5. Если по каждому поставщику избытки или недостатки равны нулю, определить стоимость транспортирования и закончить вычисления, если нет перейти к следующему пункту алгоритма.
6. Определить минимальную разность (дифференциальную ренту) для каждого потребителя в стоимости перевозок грузов от поставщиков, имеющих недостатки их.
7. Прибавить дифференциальную ренту к стоимости перевозок для всех поставщиков, имеющих недостатки грузов.
8. Дополнительно отгрузить потребителям, которые не были обеспечены грузами полностью от поставщиков, имеющих недостаток груза, грузы от тех «избыточных» поставщиков, стоимость поставки от которых за счет ее повышения уравнялась со стоимостью поставки от «дефицитных» поставщиков. Таким образом, произойдет перераспределение ранее намеченных поставок груза.

Рассмотрим  пример задачи, в таблице 16 представлены первоначальные данные.

Таблица 16. Первоначальные данные

Склады	Магазины
	900	500	300	400	200	200
800	2	4	5	8	9	6
600	7	9	8	7	5	5
400	6	4	6	4	5	8
100	7	3	8	8	4	9
300	6	1	4	5	6	4
500	1	2	4	9	7	3

 

Таблица 17. Метод  дифференциальных рент.

Склады	Магазины						Определение избытка (недостатка)
	900	500	300	400	200	200
800	2 [400]	4 [200]	5	8	9	6	800
600	7	9	8	7	5 [100]	5 [200]	600
400	6	4	6	4     [400]	5	8	0
100	7	3	8	8	4    [100]	9	-100
300	6	1  [300]	4 [300]	5	6	4	-500
500	1    [500]	2	6	9	7	3	-500
Определение дифференциальной ренты	5	5			4	1

 

F=2*400+4*200+5*100+5*200+4*400+4*100+1*500+1*300+4*300=7100

Метод дифференциальных рент существенно ускоряет получение оптимального плана перевозок, однако сейчас мы рассмотрим, подходит ли данный метод для решения с введенным «полом» перевозок.