Тест№6. Моделирование оптимального управления порожними вагонами различных форм собственности.

Справочный материал

Пусть в пунктах A₁,A₂,...,A_m находятся порожние вагоны,

причем в пункте A_i находится, соответственно, a_i вагонов перевозчика

и a^*_i вагонов других форм собственности (фирм, иностранных и т. д.).

Эти вагоны должны быть поданы под погрузку в пункты B₁,B₂,..., B_n, причем заявки этих пунктов составляют, соответственно, b₁,b₂,..., b_n вагонов. В общем случае исходными данными являются:

m – число пунктов отправления (ПО);

n – число пунктов назначения (ПН);

C _ij – транспортные расходы по перемещению одного вагона из пункта i в пункт j, " ij; при этом для вагонов других форм собственности эти расходы C_ij^* - это и собственно транспортные расходы и арендная плата и другие финансовые выплаты, которые перевозчик платит владельцам вагонов.

Критерием задачи являются суммарные затраты на перемещение вагонов.

Элементы модели:

– матрица перевозок;

 

C и С^*– матрицы транспортных затрат;

a=(a₁, a₂,..., a_m), a^* =( a₁^*,a₂^*,..., a_m^*) –

вектора возможностей ПО;

b=(b₁, b₂,..., b_n) – вектор потребностей ПН.

Удобно задачу представить в табличном виде:

 

 

Bj Ai	B1	...	Bn	Запасы
A1	C11 C11^*	...	C1n C1n^*	a1 a1^*
A2	C21 C21^*	...	C2n C2n^*	a2 a2^*
...	...	...	...	...
Am	Cm1 Cm1^*	...	Cmn Cmn^*	am am^*
Заявки	b1	...	bn

 

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

Идея преобразования состоит в том, чтобы реальным пунктам A₁, A₂,..., A_m поставить в соответствие эти пункты, но с запасами a₁,a₂,…,a_m и, якобы другие, но по существу те же пункты с другими индексами A_m+1, A_m+2, …, A_m+m с запасами a₁^*,a₂^*,…,a_m^* и соответствующими стоимостями перемещений вагонов. Тогда вышеприведенная таблица преобразуется в таблицу

 

Bj Ai	B1	...	Bn	Запасы
A1	C11	...	C1n	a1
...	...	...	...	...
Am	Cm1	...	Cmn	am
Am+1	C11^*	...	C1n^*	a1^*
…	...	...	...	...
Am+m	Cm1^*	...	Cmn^*	am^*
Заявки	b1	...	bn

 

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

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

 

Bj Ai	B1	B2	B3	Запасы
A1				35+30
A2				70+25
Заявки

 

Здесь, как и выше, в правом верхнем углу каждой клетки, соответствующей перевозкам из A_i в B_j, стоят стоимости C_ij, а в левом нижнем углу – стоимости C_ij^*. В столбике для запасов в каждой клетке первое слагаемое соответствует количеству имеющихся в запасе в этом пункте порожних вагонов перевозчика, а второе слагаемое – количество вагонов других форм собственности. В заявках, естественно, нет разделения по формам собственности.

В соответствии с предложенным выше алгоритмом для вагонов других форм собственности из пункта A₁ вводим фиктивный пункт A₃, а для соответствующих вагонов из пункта A₂ – фиктивный пункт A₄. Кроме того,

так как суммарное число заявок (140) меньше суммарного числа запасов (160), то для приведения задачи к классической транспортной задаче вводим фиктивный пункт назначения B₄ с заявкой 20 (160-140=20) и с нулевыми стоимостями перевозок. Тогда задача преобразуется в задачу, представленную таблицей:

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
A4
Заявки

 

Эта задача является классической сбалансированной транспортной задачей и она может быть решена методами решения этой задачи.

Начальный базисный план можем получить по методу наименьшей стоимости по строчкам. Этот план представлен нижеприведенной таблицей:

 

 

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2	05	20
A3	30
A4
Заявки

Значение критерия (стоимость перевозок) для этого базисного плана будет равно: f(X_б)=80×35+110×05+90×20+100×45+260×30+220×05+00×20=18550.

Чтобы улучшить этот базисный план или убедиться, что план оптимальный, применим метод потенциалов. Выберем для пунктов отправления A_i потенциалы - u_i, а для пунктов назначения B_j, соответственно, потенциалы v_j. Составим систему уравнений для потенциалов, основываясь на базисных клетках предыдущей таблицы:

v₂ – u₁ = 80, v₁ – u₂ = 110, v₂ – u₂ = 90,

v₃ – u₂ =100, v₁ – u₃ =260, v₁ – u₄ = 220, v₄ – u₄ = 0.

 

Полагая u₁ = 0, для остальных значений потенциалов из этой системы получим: v₂ = 80, v₁ = 100, u₂ = - 10, v₃ = 90, u₃ = - 160, u₄ = - 120, v₄ = - 120. Вычислим теперь значения псевдостоимостей Ĉ_ij = v_j – u_i для свободных клеток: Ĉ₁₁ = 100, Ĉ₁₃ = 90, Ĉ₁₄ = - 120, Ĉ₂₄ = - 110, Ĉ₃₂ = 240, Ĉ₃₃ = 250, Ĉ₃₄ = 40, Ĉ₄₂ = 200, Ĉ₄₃ = 210, Ĉ₄₄ = 0. Для всех свободных клеток, кроме трех, выполняются неравенства Ĉ_ij ≤C_ij. Для клеток (3,2), (3,3) и (3,4) имеет место противоположный знак. На основе клетки (3,2) осуществим циклическое перемещение перевозок с целью получения лучшего базисного плана. Переместим 20 единиц груза (20 вагонов) из базисной клетки (2,2) в свободную клетку (3,2), затем для соблюдения баланса из 30 вагонов клетки (3,1) 20 вагонов переместим в клетку (2,1). Цикл замкнулся. Новый базисный план, соответствующий этим перемещениям в таблице, представлен в новой таблице:

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
A4
Заявки

 

Значение критерия для этого базисного плана равно:

f(X_б) = 80×35+110×25+100×45+260×10+190×20+220×05+00×20 = 17550.

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

 

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
A4
Заявки

 

Составляя систему уравнений для потенциалов базисных клеток этой таблицы, получим:

v₂ – u₁ = 80, v₃ – u₁ =90, v₃ – u₂ = 100, v₁ – u₂ = 110,

v₂ – u₃ = 190, v₁ – u₄ =220, v₄ – u₄ = 00.

 

Решая эту систему, для потенциалов получим следующие значения:

u₁ = 0, v₂ = 80, v₃ =90, v₁ = 100, u₂ = - 10, u₃ = - 110, u₄ = - 120, v₄ = - 120. Отсюда для псевдостоимостей свободных клеток получим: Ĉ₁₁ = 100,

Ĉ₁₄ = - 120, Ĉ₂₂ = 90, Ĉ₂₄ = - 110, Ĉ₃₁ = 220, Ĉ₃₃ = 200, Ĉ₃₄ = - 10, Ĉ₄₂ = 200,

Ĉ₄₃ = 210. Нетрудно убедиться, что для всех клеток выполняются

неравенства Ĉ_ij ≤ С_ij, а это означает, что полученный базисный план является оптимальным. Итак, 40вагонов, необходимых для пункта B₁, доставляются в этот пункт следующим образом – 35вагонов перевозчика из пункта A₂ и 5вагонов других форм собственности из этого же пункта; соответственно, 55вагонов для B₂ доставляются – 25вагонов перевозчика из пункта A₁ и 30вагонов других форм собственности из этого же пункта; аналогично, 45вагонов для B₃ доставляются – 10вагонов перевозчика из пункта A₁ и 35вагонов перевозчика из пункта A₂. В фиктивный пункт назначения из-за нулевой стоимости перевозок ничего не направляется, 20 вагонов других форм собственности остаются в пункте A₂.

Задания

В таблицах по каждому варианту представлены: запасы вагонов в пунктах A_i – в последнем столбике таблицы (в правом верхнем углу клетки-вагоны перевозчика, в левом нижнем углу клетки-вагоны других форм собственности), заявки на вагоны от пунктов B_j – в последней строке таблицы, в правом верхнем углу остальных клеток транспортные расходы по перемещению одного вагона из A_i в B_j - C_ij для вагонов перевозчика, а в левом нижнем углу - C_ij^* для вагонов других форм собственности.

Составить оптимальный план распределения вагонов.

№1

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№2

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№3

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№4

	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№5

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№6

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№7

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№8

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№9

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№10

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№11

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№12

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№13

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№14

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№15

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№16

	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№17

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№18

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№19

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№20

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№21

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№22

Bj Ai	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№23

	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№24

	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

№25

	B1	B2	B3	B4	Запасы
A1
A2
A3
Заявки

 

Тест № 7 – Сети Петри.

Справочный материал.