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

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

Пусть в пунктах A1,A2, . . . ,Am находятся порожние вагоны,

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

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

Эти вагоны должны быть поданы под погрузку в пункты B1,B2, . . . , Bn, причем заявки этих пунктов составляют, соответственно, b1,b2, . . . , bn вагонов. В общем случае исходными данными являются:

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

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

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

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

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

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

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

a=(a1, a2, . . . , am), a*=(a1*,a2*,. . . , am*) –

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

b=(b1, b2, . . . , bn) – вектор потребностей ПН.

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

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    

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

Идея преобразования состоит в том, чтобы реальным пунктам A1, A2, . . . , Am поставить в соответствие эти пункты, но с запасами a1,a2,…,am и, якобы другие, но по существу те же пункты с другими индексами Am+1, Am+2, …, Am+m с запасами a1*,a2*,…,am* и соответствующими стоимостями перемещений вагонов. Тогда вышеприведенная таблица преобразуется в таблицу

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
Заявки      

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

В соответствии с предложенным выше алгоритмом для вагонов других форм собственности из пункта A1 вводим фиктивный пункт A3, а для соответствующих вагонов из пункта A2 – фиктивный пункт A4. Кроме того,

так как суммарное число заявок (140) меньше суммарного числа запасов (160), то для приведения задачи к классической транспортной задаче вводим фиктивный пункт назначения B4 с заявкой 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.

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

v2 – u1 = 80, v1 – u2 = 110, v2 – u2 = 90,

v3 – u2 =100, v1 – u3 =260, v1 – u4 = 220, v4 – u4 = 0.

Полагая u1 = 0, для остальных значений потенциалов из этой системы получим: v2 = 80, v1 = 100, u2 = - 10, v3 = 90, u3 = - 160, u4 = - 120, v4 = - 120. Вычислим теперь значения псевдостоимостей Ĉij = vj – ui для свободных клеток: Ĉ11 = 100, Ĉ13 = 90, Ĉ14 = - 120, Ĉ24 = - 110, Ĉ32 = 240, Ĉ33 = 250, Ĉ34 = 40, Ĉ42 = 200, Ĉ43 = 210, Ĉ44 = 0. Для всех свободных клеток, кроме трех, выполняются неравенства Ĉij ≤Cij. Для клеток (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    
  Заявки          

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

v2 – u1 = 80, v3 – u1 =90, v3 – u2 = 100, v1 – u2 = 110,

v2 – u3 = 190, v1 – u4 =220, v4 – u4 = 00.

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

u1 = 0, v2 = 80, v3 =90, v1 = 100, u2 = - 10, u3 = - 110, u4 = - 120, v4 = - 120. Отсюда для псевдостоимостей свободных клеток получим: Ĉ11 = 100,

Ĉ14 = - 120, Ĉ22 = 90, Ĉ24 = - 110, Ĉ31 = 220, Ĉ33 = 200, Ĉ34 = - 10, Ĉ42 = 200,

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

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

Задания

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

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

№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 – Сети Петри.

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

Наши рекомендации