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

Определим транспортные расходы по доставке одной тонны груза от i-го поставщика j-му потребителю (табл.4.2).

 

Таблица 4.2

Транспортные расходы по доставке одной тонны груза от i-го поставщика j-му потребителю, руб

	М-н Вагон Вилс	Автосервис "Митроф-Авто"	Автосервис "Заркало"	СТО "Carluck"	М-н автозапчастей ПАИС
ООО «Энерго»	200	150	200	250	200
ООО «Интертерминал-Предпортовый»	500	350	400	450	500
ООО «Предприятие Алиди»	1100	1250	1200	1250	1100
ООО «Северный легион»	1300	1300	1350	1350	1300
ООО «Складской комплекс Царское село»	1400	1200	1300	1350	1400

 

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

 

,

 

где Cij - транспортные расходы по доставке одной тонны груза от i-го поставщика j-му потребителю, руб./т.; Xij - количество продукции, поставляемой от i-го поставщика j-му потребителю, т.

Достижение минимального значения целевой функции происходит при определенных условиях (ограничениях). Первое из них состоит в том, что по оптимальному варианту от каждого поставщика планировалось то количество продукции, которым он располагает:

 

 

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

 

 

Также в модели указывается условие неотрицательности:

 

 

После построения модели решается задача прикрепления поставщиков потребителям. Расчеты могут выполняться методом потенциалов (табл. 4.3). В этой таблице кроме ресурсов поставщиков, потребностей потребителей и транспортных расходов, имеются столбец и строка для записи потенциалов Ui и Vj, которые дают возможность определить оптимальность плана закрепления поставщиков за потребителями. В правом верхнем углу ячеек указана стоимость доставки продукции (руб/т).

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

 

 

 

 

 

 

 

Таблица 4.3

Исходный план

Потребители		М1	М2	М3	М4	М5	Ресурсы поставщиков, Аi, т
Поставщик	Vj   Ui	V1	V2	V3	V4	V5
С1	U1	6200	9150	200	250	200	15
С2	U2	500	6350	400	450	500	6
С3	U3	1100	11250	81200	1250	1100	9
С4	U4	1300	1300	21350	161350	1300	18
С5	U5	1400	1200	1300	11350	81400	9
Потребность Bj, т		6	16	10	17	8	57

 

Проверка исходного плана. Необходимо проверить исходный план на соответствие следующим условиям: Число «загруженных» клеток в таблице должно быть на единицу меньше суммы чисел поставщиков и потребителей, у нас их 9 (5 + 5 – 1), т.е. условие соблюдено и удовлетворяет условию невырожденности плана. Не должно быть ни одного занятого квадрата, который оказался бы единственным в строке и столбце таблицы, т.е. условие соблюдено. 

Далее проверяем на оптимальность. Для осуществления проверки ис- ходного плана на оптимальность необходимо рассчитать потенциалы Ui и Vj. Эти потенциалы определяются только для «загруженных» ячеек. Сумма индексов Ui и Vj должна быть равна транспортным издержкам соответст- вующих ячеек. В этом примере U1 + V1 =200; U1 + V2 = 150; U2 + V2 = 350; U3 + V2 = 1250; U3 + V3 = 1200; U4 + V3 = 1350; U4 + V4 = 1350; U5 + V4 = 1350; U5 + V5 = 1400.

Определяем потенциалы для всех потребителей и поставщиков, принявU1=0 и представим их в табл. 4.4.

 

Таблица 4.4

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

Потребители		М1	М2	М3	М4	М5	Ресурсы поставщиков, Аi, т
Поставщик	Vj   Ui	200	150	100	100	150
С1	0	6200	9150	200	250	200	15
С2	200	500	6350	400	450	500	6
С3	1100	1100	11250	81200	1250	1100	9
С4	1250	1300	1300	21350	161350	1300	18
С5	1250	1400	1200	1300	11350	81400	9
Потребность Bj, т		6	16	10	17	8	57

 

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

С3-М1: 1100+200> 1100; ∆21 = 1100+200-1100 = 200

С4-М1: 1250+200 >1300; ∆41 = 1250+200-1300 = 150

С5-М1: 1250 + 200 > 1400; ∆51 = 1250+200-1400= 50

 
С4-М2: 1250+150 > 1300; ∆42 = 1250 + 150 - 1300 = 100

С5-М2: 1250+150 > 1200; ∆52 = 1250 + 150 -1 200 = 200

С5-М3: 1250 + 100 > 1300; ∆23 = 1250 + 100 - 1300 = 50 
С3-М5: 1100 + 150 > 1100; ∆35 = 1100 + 150 - 1100 = 50

С4-М5: 1250+150 >1300; ∆45 = 1250 + 150 – 1300 = 100 
max = 200

 

Выбираем максимальную оценку свободного квадрата С3-М1=1100 
Для этого в перспективныйквадрат С3-М1 поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Данные представлены в табл. 4.5.

 

Таблица 4.5

Перемещение поставки в квадрат С3-М1

Потребители		М1	М2	М3	М4	М5	Ресурсы поставщиков, Аi, т
Поставщик	Vj   Ui	200	150	100	100	150
С1	0	6   200 [-]	9    150 [+]	200	250	200	15
С2	200	500	6    350	400	450	500	6
С3	1100	1000 [+]	1 [-] 1250	8   1200	1250	1100	9
С4	1250	1300	1300	21350	161350	1300	18
С5	1250	1400	1200	1300	11350	81400	9
Потребность Bj, т		6	16	10	17	8	57

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

 

Таблица 4.6

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

Потребители		М1	М2	М3	М4	М5	Ресурсы поставщиков, Аi, т
Поставщик	Vj   Ui	200	150	300	300	350
С1	0	5 200	10 150	200 300	250 300	200 350	15
С2	200	500 400	6 350	400 500	450 500	500 550	6
С3	900	1 1100	1250 1200	8 1200 [-]	1250 1200	1100 1250 [+]	9
С4	1050	1300 1250	1300 1200	2 1350 [+]	16 1350 [-]	1300 1400	18
С5	1050	1400 1250	1200 1200	1300 1350	1 1350 [+]	8 1400 [-]	9
Потребность Bj, т		6	16	10	17	8	57

 
Снова проверим оптимальность плана. Найдем предварительные потенциалы Ui, Vj. по занятым клеткам таблицы, в которых Ui + Vj = Cij,полагая, что u1 = 0.

 
U1 + V1 =200; 0 + v1 = 200; v1 = 200 
U3 + V1 = 1100; 200 + u3 = 1100; u3 = 900 
U3 + V3 = 1200; 900 + v3 = 1200; v3 = 300

U4 + V3 = 1350; 300 + u4 = 1350; u4 = 1050

U4 + V4 = 1350; 1050 + v4 = 1350; v4 = 300 
U5 + V4 = 1350; 300+ u5 = 1350; u5 = 1050 
U5 + V5 = 1400; 1050+ v5 = 1400; v5 = 350 
U1 + V2 = 150; 0 + v2 = 150; v2 = 150 
U2 + V2 = 350; 150 + u2 = 350; u2 = 200