3.2. Второй вид транспорта

Себестоимость перевозки одной тонны груза из i-го пункта взаимодействия в j-й пункт назначения вторым видом транспорта определяется следующим образом:

С^Б_ij = b₂ L_ij + с₂, i = 1...3, j = 1...4, (9)

где b₂ = 4 руб./т км – ставка себестоимости движенческой операции на втором виде транспорта;

L_ij – расстояние перевозки вторым видом транспорта из i-го пункта взаимодействия в j-й пункт назначения, км (табл. 2);

с₂ = 10 руб./т. – ставка себестоимости конечной операции на втором виде транспорта.

Результаты расчетов по формуле (9) приведены в таблице 15.

Таблица 15 – Себестоимость перевозки

из пунктов взаимодействия в пункты назначения

СБij, руб./т		Пункты назначения
		В1	В2	В3	В4
Пункты взаимодействия	D1	210	158	98	30
	D2	274	226	170	106
	D3	338	294	242	182

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

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

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

A₁ + A₂ + A₃ + A₄ + A₅ = 86+95+104+113+122=520 т.

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

B₁ + B₂ + B₃ + B₄ =36+86+130+250=502 т.

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

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

С = 214X₁₁ + 184X₁₂ + 208X₁₃ + 106X₂₁ + 262X₂₂ + 118X₂₃ + 94X₃₁ + 214X₃₂ +

+ 106Х₃₃ + 148Х₄₁ +166Х₄₂ +130Х₄₃ +796Х₅₁ +712Х₅₂ +616Х₅₃ + 210Y₁₁+ +274Y₁₂ + 338Y₁₃ + 158Y₂₁ + 226Y₂₂ +294Y₂₃ + 98Y₃₁ + 170Y₃₂ + 242Y₃₃ +30Y₄₁ +106Y₄₂ +182Y₄₃ +622Z₁₁ + 562Z₁₂ + 490Z₁₃ + 406Z₁₄ + 718Z₂₁ +668Z₂₂ +598Z₂₃ + 520Z₂₄ + 814Z₃₁ + 766Z₃₂ + 706Z₃₃ + 634Z₃₄ + 910Z₄₁+868Z₄₂ + 814Z₄₃ + 748Z₄₄ + 1006Z₅₁+ 970Z₅₂+922Z₅₃+ 862Z₅₄ min.

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

Y₁₁ + Y₂₁ + Y₃₁ +Z₁₁ + Z₂₁ + Z₃₁ + Z₄₁+ Z₅₁ = 36,

Y₁₂ + Y₂₂ + Y₃₂ +Z₁₂ + Z₂₂ + Z₃₂ + Z₄₂ +Z₅₂ = 86,

Y₁₃ + Y₂₃ + Y₃₃ +Z₁₃ + Z₂₃ + Z₃₃ + Z₄₃ + Z₅₃ = 130,

Y₁₄ + Y₂₄ + Y₃₄ +Z₁₄ + Z₂₄ + Z₃₄ + Z₄₄ + Z₅₄ = 250.

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

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

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

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

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

X₁₁ + X₂₁ + X₃₁ + X₄₁ + X₅₁  26,

X₁₂ + X₂₂ + X₃₂ + X₄₂ + X₅₂  46,

X₁₃ + X₂₃ + X₃₃ + X₄₃ + X₅₃  186.

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

X₁₁ + X₁₂ + Х₁₃ +Z₁₁ + Z₁₂ + Z₁₃ + Z₁₄  86,

X₂₁ + X₂₂ + Х₂₃ +Z₂₁ + Z₂₂ + Z₂₃ + Z₂₄  95,

X₃₁ + X₃₂ + Х₃₃ +Z₃₁ + Z₃₂ + Z₃₃ + Z₃₄  104,

X₄₁ + X₄₂ + Х₄₃ +Z₄₁ + Z₄₂ + Z₄₃ + Z₄₄  113,

X₅₁ + X₅₂ + Х₅₃ +Z₅₁ + Z₅₂ + Z₅₃ + Z₅₄  122.

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

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

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

Значения запасов груза A_k (k = 1... 5) в пунктах отправления расположены в ячейках D8:H8, заявок на груз В_j (j = 1... 4) в пунктах назначения – в ячейках C9:C12, перерабатывающих способностей D_i (i = 1...3) в пунктах взаимодействия – в ячейках I8:К8.

Значения расстояний перевозки из пунктов отправления в пункты назначения

Lkj расположены в ячейках D9:H12, из пунктов взаимодействия в пункты назначения Lij – в ячейках I9:K12, из пунктов отправления в пункты взаимодействия Lki – в ячейках D13:H15.

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

переменные Xki, (k = 1...5, i = 1... 3) - количество груза, перевозимого из k-го

пункта отправления в i-й пункт взаимодействия первым видом транспорта, расположены в ячейках D29;H31;

переменные Yij, (i = 1... 3, j = 1... 4) - количество груза, перевозимого из i-го

пункта взаимодействия в j-й пункт назначения вторым видом транспорта, расположены в ячейках I25:K28;

переменные Zkj, (k = 1...5, j = 1... 4) - количество груза, перевозимого в прямом сообщении из k-го пункта отправления в j-й пункт назначения первым видом транспорта, расположены в ячейках D25:H28.

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

значения себестоимости САki (k = 1...5, i = 1... 3) перевозки 1 тонны груза из k-го пункта отправления в i-ый пункт взаимодействия первым видом транспорта с учетом затрат на перевалку рассчитаны по формуле (7) в ячейках D21:H23;

значения себестоимости СБij (i = 1...3 , j = 1... 4) перевозки 1 тонны груза из i-го пункта взаимодействия в j-ый пункт назначения вторым видом транспорта рассчитаны по формуле (9) в ячейках I17:K20;

значения себестоимости СВkj (k = 1...5, j = 1... 4) перевозки 1 тонны груза в прямом сообщении из k-го пункта отправления в j-й пункт назначения первым видом транспорта рассчитаны по формуле (10) в ячейках D17:H20;

значения затрат на перевозку груза из k-го пункта отправления в i-ый пункт

взаимодействия первым видом транспорта с учетом затрат на перевалку рассчитаны как произведение САki и Xki в ячейках D33:H41;

значения затрат на перевозку груза из i-го пункта взаимодействия в j-ый пункт назначения вторым видом транспорта рассчитаны как произведение СБij и Yij в ячейках I35:K38;

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

разности между заявками пунктов назначения (ячейки C9:C12) и количеством груза, прибывающего в эти пункты (ячейки L25:L28), рассчитаны в ячейках M25:M28;

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

(ячейки I29:K29), и количеством груза, прибывающего в эти пункты (ячейки

L29:L31), рассчитаны в ячейках I32:K32;

разности между перерабатывающими мощностями пунктов взаимодействия (ячейки I8:K8) и количеством груза, прибывающего в эти пункты (ячейки I29:K29), рассчитаны в ячейках I33:K33;

разности между запасами груза в пунктах отправлении (ячейки D8:H8) и количеством груза, убывающего из этих пунктов (ячейки D32:H32), рассчитаны в ячейках D33:H33.

4) Целевая функция рассчитана в ячейке M7 по формуле (1) как сумма ячеек

D35:H38;D39:H41;I35:K38.

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

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

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

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

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

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

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

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

Первым видом транспорта из пункта отправления A1 груз доставляется в пункт назначения B4 (86т.), в пункты взаимодействия из пункта А1 груз не доставляется. Из пункта отправления A2 груз доставляется в пункты назначения B4 (54 т.) и в пункт взаимодействия D3 (41т.). Из пункта отправления A3 груз доставляется в пункт взаимодействия D1 (26 т.) и D3 (78 т.) Из пункта отправления A4 груз доставляется в пункты взаимодействия D2 (46 т.) и D3 (67 т.) Из пункта отправления A5 груз доставляется в пункты назначения В1 (36 т.) и В2 (68 т.), в пункты взаимодействия из пункта А1 груз не доставляется (табл.16).

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

Перевозимый груз, т		Пункты отправления
		А1	А2	А3	А4	А5
Пункты назначения	В1					36
	В2					68
	В3
	В4	86	54
Пункты взаимодействия	D1			26
	D2				46
	D3		41	78	67
Итого		86	95	104	113	104

Вторым видом транспорта груз доставляется из пункта взаимодействия D1 в пункт назначения B4 (26 т.), из пункта взаимодействия D2 – в пункт назначения B4 (46 т.), из пункта взаимодействия D3 – в пункты назначения B2 (18 т.), В3 (130 т.), В4 (38 т.) (табл.17).

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

Перевозимый груз, т		Пункты взаимодействия
		D1	D2	D3
Пункты назначения	В1
	В2			18
	В3			130
	В4	26	46	38
Итого		26	46	186

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

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

46

26

86 54 26 46 36

38

41 68

78 67

130 1 8