4 Решение задачи

Проверим выполнение необходимого условия (2) решения задачи.

Суммарный запас груза в пунктах отправки:

A₁ + A₂ + A₃ + A₄ + A₅ + A₆ = 70+75+80+85+90+95= 495 т.

Сумма заявок пунктов назначения:

B₁ + B₂ = 100+370 = 470 т.

Условие выполняется: суммарный запас груза в пунктах отправки превышает сумму заявок пунктов назначения.

Целевая функция (1) записывается следующим образом:

С = 526X₁₁ + 421X₂₁ + 226X₃₁ + 146X₄₁+ 446X₅₁ + 746X₆₁ +211X₁₂ + 176X₂₂ + 171X₃₂ + 146X₄₂+ 161X₅₂ + 506X₆₂+236X₁₃ + 241X₂₃ + 236X₃₃ + 191X₄₃+ 286X₅₃ + 176X₆₃+231X₁₄ + 196X₂₄ + 216X₃₄ + 221X₄₄+ 646X₅₄ + 316X₆₄+ 180Y₁₁ + 264Y₁₂ + 384Y₁₃ + 432Y₁₄ + 114Y₂₁ + 216Y₂₂ + 318Y₂₃ + 420Y₂₄ + 158Z₁₁ + 338Z₁₂ + 108Z₂₁ + 188Z₂₂ + 318Z₃₁ + 123Z₃₂ + 528Z₄₁ + 378Z₄₂ + 738Z₅₁ + 633Z₅₂ + 948Z₆₁ + 888Z₆₂  min.

Ограничения 1 на количество груза (3), прибывающего в пункты назначения, записываются следующим образом:

Z₁₁ + Z₁₂ + Z₁₃+ Z₁₄ + Z₁₅ + Z₁₆ + Y₁₂ + Y₁₁ + Y₁₃ + Y₁₄ =100,

Z₂₁ +Z₂₂ + Z₂₃ + Z₂₄ + Z₂₅ + Z₂₆ + Y₂₁ + Y₂₂ + Y₂₃ + Y₂₄ = 370.

Ограничения 2 на количество груза (4), прибывающего и убывающего из пунктов взаимодействия, записываются следующим образом:

Y₁₁ + Y₁₂ = X₁₁ + X₂₁ + X₃₁+X₄₁ + X₅₁ + X_61,

Y₂₁ + Y₂₂ = X₁₂ + X₂₂ + X₃₂+X₄₂ + X₅₂ + X_62,

Y₃₁ + Y₃₂ = X₁₃ + X₂₃ + X₃₃+X₄₃ + X₅₃ + X_63,

Y₄₁ + Y₄₂ = X₁₄ + X₂₄ + X₃₄+X₄₄ + X₅₄ + X_64.

Ограничения 3 на количество груза (5), перерабатываемого в пунктах взаимодействия, записываются следующим образом:

X₁₁ + X₂₁ + X₃₁+X₄₁ + X₅₁ + X₆₁ 40,

X₁₂ + X₂₂ + X₃₂+X₄₂ + X₅₂ + X₆₂ 45,

X₁₃ + X₂₃ + X₃₃+X₄₃ + X₅₃ + X₆₃ 

X₁₄ + X₂₄ + X₃₄+X₄₄ + X₅₄ + X₆₄  _.

Ограничения 4 на количество груза (6), убывающего из пунктов отправления, записываются следующим образом:

X₁₁ + X₁₂ + X₁₃ + X₁₄ + Z₁₁ + Z₁₂  70,

X₂₁ + X₂₂ + X₂₃ + X₂₄ + Z₂₁ + Z₂₂  75,

X₃₁ + X₃₂ + X₃₃ + X₃₄ + Z₃₁ + Z₃₂ 80,

X₄₁ + X₄₂ + X₄₃ + X₄₄ + Z₄₁ + Z₄₂ 85,

X₅₁ + X₅₂ + X₅₃ + X₅₄+ Z₅₁ + Z₅₂ 90,

X₆₁ + X₆₂ + X₆₃ + X₆₄+ Z₆₁ + Z₆₂ 95.

Решение сформулированной задачи целочисленного линейного программирования осуществляется с использованием средства «Поиск решения» пакета MS Excel методом «ветвей и границ».

На рисунке 1 представлена таблица MS Excel поиска решения, в которой находятся следующие данные.

1) Исходные данные:

значения ставок себестоимости расположены в ячейках:

начальной операции a на первом виде транспорта – в ячейке N3,

операции перевалки d с первого вида транспорта на второй – в ячейке N10,

движенческой операции b₁ на первом виде транспорта – в ячейке N4,

движенческой операции b₂ на втором виде транспорта – в ячейке N14,

конечной операции с₁ на первом виде транспорта – в ячейке N5 ,

конечной операции с₂ на втором виде транспорта – в ячейке N15;

значения запасов груза A_k (k = 1... 6) в пунктах отправления расположены в ячейках F3:F8,

заявок на груз В_j (j = 1... 2) в пунктах назначения – в ячейках G9;K9,

перерабатывающих способностей D_i (i = 1...4) в пунктах взаимодействия – в ячейках B9:E9;

значения расстояний L_kj перевозки из пунктов отправления в пункты назначения расположены в ячейках J3:K8,

L_ij из пунктов взаимодействия в пункты назначения– в ячейках S3:T6,

L_ki из пунктов отправления в пункты взаимодействия L_ki – в ячейках B3:E8.

2) Проектные переменные:

переменные X_ki, (k = 1...6, i = 1... 4) – количество груза, перевозимого из k-го пункта отправления в i-ый пункт взаимодействия первым видом транспорта, – расположены в ячейках C28:H31;

переменные Y_ij, (i = 1... 4, j = 1... 2) – количество груза, перевозимого из i-го пункта взаимодействия в j-ый пункт назначения вторым видом транспорта, – расположены в ячейках I26:L27;

переменные Z_kj, (k = 1...6, j = 1... 2) – количество груза, перевозимого в прямом сообщении из k-го пункта отправления в j-ый пункт назначения первым видом транспорта, – расположены в ячейках C26:H27.

3) Расчетные данные:

значения стоимости С^А_ki (k = 1...6, i = 1... 4) перевозки одной тонны груза из k-го пункта отправления в i-ый пункт взаимодействия первым видом транспорта с учетом затрат на перевалку рассчитаны по формуле (8) в ячейках B14:E19;

значения стоимости С^Б_ij (i = 1... 4, j = 1... 2) перевозки одной тонны груза из i-го пункта взаимодействия в j-ый пункт назначения вторым видом транспорта рассчитаны по формуле (9) в ячейках S14:T17;

значения стоимости С^В_kj (k = 1...6, j = 1... 2) перевозки одной тонны груза в прямом сообщении из k-го пункта отправления в j-ый пункт назначения первым видом транспорта рассчитаны по формуле (7) в ячейках J14:K19;

значения затрат на перевозку груза из k-го пункта отправления в i-ый пункт взаимодействия первым видом транспорта с учетом затрат на перевалку рассчитаны как произведение С^А_ki и X_ki в ячейках C39:H42;

значения затрат на перевозку груза из i-го пункта взаимодействия в j-ый пункт назначения вторым видом транспорта рассчитаны как произведение С^Б_ij и Y_ij в ячейках I37:L38;

значения затрат на перевозку груза в прямом сообщении из k-го пункта отправления в j-ый пункт назначения первым видом транспорта рассчитаны как произведение С^В_kj и Z_kj в ячейках C37:H38;

разности между заявками пунктов назначения и количеством груза, прибывающего в эти пункты, рассчитаны в ячейках N26:N27;

разности между количеством груза, убывающего из пунктов взаимодействия, и количеством груза, прибывающего в эти пункты, рассчитаны в ячейках I32:L32;

разности между перерабатывающими мощностями пунктов взаимодействия и количеством груза, прибывающего в эти пункты, рассчитаны в ячейках I34:L34;

разности между запасами груза в пунктах отправлении и количеством груза, убывающего из этих пунктов, рассчитаны в ячейках C33:H33.

4) Целевая функция рассчитана в ячейке N37 по формуле (1) как сумма ячеек C39:H42; I37:L38; C37:H38.

5) Ограничения задаются следующим образом:

ограничение 1: разности в ячейках N26:N27 должны быть равны нулю;

ограничение 2: разности в ячейках I32:L32 должны быть равны нулю;

ограничение 3: разности в ячейках I34:L34 должны быть неотрицательны;

ограничение 4: разности в ячейках C33:H33 должны быть неотрицательны.

В результате решения задачи получен план перевозок, обеспечивающий минимальные затраты, которые составили 143 670 ден.ед.

Рисунок 1 – Вид таблицы MS Excel решения задачи

Рисунок 2 – Вид таблицы MS Excel расчет целевой функции

Первым видом транспорта из пункта отправления A1 груз доставляется в пункт назначения B1 (70т) и в пункты взаимодействия груз не доставляется. Из пункта отправления A2 груз доставляется в пункты назначения B1 (30т) и B2 (45т), в пункты взаимодействия из пункта A2 груз не доставляется. Из пункта отправления A3 груз доставляется в пункт назначения B2 (45т), в пункты взаимодействия из пункта A3 груз не доставляется. Из пункта отправления А4 груз доставляется в пункт назначения В2 (45т) и в пункт взаимодействия D1 (40т). Из пункта отправления А5 груз доставляется в пункт назначения B2 (45т) и в пункт взаимодействия D2 (45т). Из пункта отправления A6 груз доставляется только в пункты взаимодействия D3 (55т) и D4 (15т). (таблица 16).

Таблица 16 – Доставка груза первым видом транспорта

Перевозимый груз, т		Пункты отправления
		А1	А2	А3	A4	A5	A6
Пун. Назнач	В1	70	30
	В2		45	80	45	45
Пункты взаимодействия	D1				40
	D2					45
	D3						55
	D4						15
Итого		70	75	80	85	90	70

Вторым видом транспорта груз доставляется из пункта взаимодействия D2 в пункты назначения B1 (40 т), B2 (45 т), В3 (55т) и В4 (15 т), из пункта взаимодействия D1 груз не доставляется (таблица 17).

Таблица 17 – Доставка груза вторым видом транспорта

Перевозимый груз, т		Пункты взаимодействия
		D1		D2	D3		D4
Пункты назначения	В1
	В2	40	45		55	15
	итого	40	45		55	15

На рисунке 3 показана схема распределения грузопотоков по маршрутам перевозки от пунктов.

Рисунок 3 – Схема распределения грузопотоков по маршрутам перевозки

Таким образом, в пункт B1 весь груз (100 т) доставляется первым видом транспорта из пункта отправления A1, А2; в пункт B2 – первым видом транспорта из пункта отправления А2 (45 т), А4 (45т), А5 (45т), А3 (80т) и вторым видом транспорта из пункта взаимодействия D1 (40 т), D2(45 т), D3 (55т) и D4 (15т), таким образом сумма перевезенного груза в пункт назначения В2 (370 т). Ни в одном пункте отправления груза не остается, заявка выполнена полностью.

ЗАКЛЮЧЕНИЕ

В данной работе был найден оптимальный план перевозки с минимальными расстояниями и затратами. Использовалось два вида транспорта со своими стоимостными характеристиками. С помощью функции MC Excel «Поиск решения» нашли минимальные затраты и то количество груза которое необходимо перевезти наиболее удобным способом.

Список литературы

1. Курс лекций И.В.Потапов «Взаимодействие видов транспорта на смешанных перевозках»

12