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

2	0	3	5	3	0
5	0	3	0	2	9
5	5	3	2	7	0
0	7	1	8	6	7
5	5	4	49	0	2
0	3	0	0	5	2

 

 
                                                    

 

(а)   (б) (в)

Рисунок 1

Ответ: Lmin=1+4+5+1+1+2=14

A1          B2  A4 B1

A2          B4  A5 B5

A3          B6  A6          B3          

Таким образом, повысив стоимость клетки, в которой  по условию содержится запретная  перевозка, мы создали оптимальный  план, в который данная клетка не входит.

Основная идея этого метода: оптимальность решения  задачи не нарушается при уменьшении (увеличении) элементов строки (столбца)на одну и ту же величину di(dj).

Алгоритм решения:

1. Получение нулей в каждой строке.

Находят наименьший элемент di в каждой строке, который вычитают из всех ее элементов и получают новую матрицу (рисунок 1 (а))Аналогично в каждом столбце определяют его минимальный элемент dj, который вычитают из всех его элементов с получением следующей матрицы (рисунок 1 (б)).

2. Поиск оптимального решения

Рассматривается одна из строк имеющая один нуль, обводится в квадрат, и зачеркиваются все остальные нули столбца, в котором находится данный нуль. Аналогичная операция выполняется последовательно для всех строк, и если понадобится аналогично для столбцов (рисунок 1 (в)).

Если в каждой строке находится по одному нулю, то найдено оптимальное решение. Переносим его на первоначальную матрицу (рисунок 1 (а)).  Если же нет, то переходим к шагу 3.

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

Зачеркивают произвольно 2 столбца и 1 строку:

Определяют  наименьшее число из тех клеток, которые не зачеркнуты.

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

Если эти операции не приводят к оптимальному решению, то цикл повторяется, начиная с шага 2 и до получения оптимума.

В рассмотренном  мною примере мы сразу нашли оптимальное  решение задачи, что встречается  не так часто. Иногда нужно пройти большое количество шагов, чтоб найти  оптимальный вариант. Данный метод применим для задач, в которых количество потребителей соответствует количеству поставщиков.[3]

2.2 Обязательная  поставка

Данная поставка чаще всего зафиксирована договором  между потребителем и поставщиком  и должна быть обязательно осуществлена.

Рассмотрим  пример решения такой задачи.

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

Запасы поставщиков	Потребности потребителей
	200	300	100	200	300
100	4	5	7	4	1
200	5	8	8	9	3
300	2	4	5	4	6
500	7	1	2	2	4

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

Таблица 2. Исключение обязательной поставки

Запасы поставщиков	Потребности потребителей
	200	300	100	100	300
100	4	5	7	4	1
200	5	8	8	9	3
200	2	4	5	4	6
500	7	1	2	2	4

Далее задача решается как обычная транспортная задача.

 

2.3 Задача с  запретом поставки и обязательной  поставкой

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

 Итак, дана задача: на складах хранится сахарный песок, который необходимо завезти в кондитерские цеха. Номера складов и номера кондитерских даны (таблица 4). Текущие тарифы перевозки сахарного песка [руб./т], ежемесячные запасы сахарного песка [т/мес] на складах и потребности кондитерских в сахарном песке [т/мес] указаны (таблица 4).

При этом необходимо учитывать, что из-за ремонтных работ временно нет возможности перевозить сахарный песок с некоторых складов в некоторые кондитерские. В таблице 3 это показано в графе "Запрет перевозки" в формате № склада х № кондитерского цеха. Например, «3x3» обозначает, что нельзя перевозить сахарный песок со склада № 3 в кондитерский цех № 3.

Кроме того, необходимо учесть, что некоторые кондитерские цеха имеют договоры на гарантированную поставку сахарного песка с определенных складов. В таблице 4 это показано в графе "Гарантированная поставка" в формате № склада х № хлебопекарни = объем поставки. Например, «3x5=40» обозначает, что между складом № 3 и магазином № 5 заключен договор на обязательную поставку 40 т сахарного песка.

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

Таблица 3. Запрещенные и гарантированные поставки

Запрет перевозки	Гарантированная поставка, т/мес.
3x3, 4x5	3x5=40

 

 

 

 

 

Таблица 4.Запасы, потребности и тарифы перевозок

Склады	Кондитерские  цеха
		1	2	3	4	5	Запас, т/мес.
1	4	6	8	2	2	80
2	3	1	5	6	5	70
3	5	2	1	6	3	60
4	3	7	2	4	9	55
5	2	5	8	2	4	65
Спрос, т/мес.	78	57	59	63	74

Прежде чем проверять  сбалансированность задачи, надо исключить объем гарантированной поставки из дальнейшего рассмотрения. Для этого вычтем 40 т из следующих величин:

из запаса третьего склада  = 60-40= 20т/мес.;

из потребности  в сахарном песке пятого кондитерского цеха

b2 = 74-40 = 34 т/мес.

Согласно условию задачи сахарный песок хранится и перевозится в мешках по 50 кг, то есть единицами измерения переменных хij являются мешки муки. Но запасы сахарного песка на складах и потребности в ней магазинов заданы в тоннах. Поэтому для проверки баланса и дальнейшего решения задачи приведем эти величины к одной единице измерения - мешкам. Например, запас сахарного песка на первом складе равен 80 т-мес = 1600 меш/мес,  а потребность      третьего   кондитерского цеха      составляет      59 т/месс = 1180меш./мес. Также мы производим расчет и на остальных складах и кондитерских цехах.

Для данной ТЗ имеет место  соотношение:

                        склады                                        кондитерские  цеха 1600+1400+400+1100+1300= 5800 < 1360+1140+1180+1260+680=5620 .

Ежемесячный   суммарный   запас   сахарного песка   на   складах больше суммарной потребности кондитерских на 180 мешков сахара, откуда следует вывод: ТЗ не закрытой модели. Чтоб сделать модель закрытой, мы вводим фиктивный кондитерский цех с потребностью 180 мешков

Черным цветом закрашены ячейки, в которых запрет поставки или гарантированная поставка, которую мы исключили из рассмотрения.                                                          

 Таблица  5.Транспортная матрица задачи

Склады	Кондитерские  цеха
	1360	1140	1180	1260	680		180
1600	4[1360]	6[240]	8	2	2		0
1400	3	1[900]	5[500]	6	5		0
400	5	2	1	6[400]	3	0
1100	3	7	2[680]	4[420]	9		0
1300	2	5	8	2[440]	4[680]		0[180]

Посчитаем ранг 6+5-1=10

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

(1,1): min (1600; 1360) = 1360

(1,2): min (1600-1360; 1140) =240

(2,2): min (1400; 1140-240) =900

(2,3): min (1400-900; 1180) =500

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

(4,3): min (1100; 1180-500) =680

(3,4): min (400; 1260) =400

(4,4): min (1100-680; 1260-400) =420

(5,4): min (1300; 1260-400-420) =440

(5,5): min (1300-440; 680) =680

(5,6): min (1300-440-680; 180) =180

F=4*1360+6*240+1*900+5*500+2*680+6*400+4*420+2*440+4*680=19320

Сделаем проверку:

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

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

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

Строим матрицу оценок по формуле Vi+Uj+Cji=0 (для заполненной клетки) и Vi+Uj+Cji (для пустой клетки):

       0 0 -2 -10 -12 -10

       4 0  0  -1   -4  -5

       7 2 зп   0  зп   -4

       7 9 0    0   гп   -2

       8 9 8    0     0    0 

 Не забываем  каждый раз проверять ранг!   

Как мы видим, в  нашей матрице оценок много отрицательных  значений, это значит, что мы нашли  не оптимальный вариант поставки.

Используем  цикл пересчета: Min (420;180)=180

 

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

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

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

       0 0 -2 -10 -12 -8

       4 0  0  -1   -4  -3

       7 2 зп   0  зп   -2

       7 9 0    0    гп   0

       8 9 8    0     0    2 

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

 

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

 

 

Таблица 8. 3 этап решения

Склады	Кондитерские  цеха
	1360	1140	1180	1260	680		180	Vi
1600	4[1360]	6[240]	8	2	2		0	0
1400	3	1[900]	5[320]	6	5		0[180]	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		-5