Транспортная политика в Республике Беларусь
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?исваиваем знак "+". Выбираем наименьшее значение из клеток со знаком "-" (min ( 140, 100 ) = 100 ) и перераспределяем продукцию вдоль контура, прибавляя 100 к значениям в клетках со знаком "+" и вычитая из значения в клетках со знаком "-". В результате приходим к таблице5.2.
Таблица 5.2 - Построение опорного плана
AiB1B2B3B4B5UiA15390 24220 1-4A2*100 + 3890 6170 - 10 5 0A340 - 1190 23* + 5 4-2Vj346105
Полученному решению отвечают затраты:
Z2 = 90*2 + 220*1 +100*3 + 90*6 +170*10 + 40*1+190*2 = 3360
Проверяем полученный план на оптимальность и получаем, что S34 = - 3 < 0, значит решение не оптимальное и строим в таблице 2 новый цикл переiёта для клетки (3,4). Так как min (220,90,40) = 40 = Xij, то перераспределяем продукцию вдоль контура, прибавляя 40 к значениям в клетках со знаком "+" и вычитая из значений в клетках со знаком "-". В результате получаем таблицу5.3.
Таблица 5.3 - Нахождение оптимального плана
AiB1B2B3B4B5UiA1 5 3 2 + 90 4 220 - 1 - 6A2140 3 8 180 6 - 40 10 * + 5 0A3 1 190 2 3 40 5 4 - 5Vj376107
Z4= 90*4 + 220*1 + 40*3 + 180*6 + 40*10 + 190*2 + 40*5 = 3060
Среди оценок свободных клеток имеем S25 = - 2 < 0 , следовательно, полученный план перевозок не является оптимальным и для его получения необходимо загрузить клетку (2,5). В итоге вычислений приходим к таблице 5.4.
Таблица 5. 4 - Новый опорный план
AiB1B2B3B4B5UiA1 5 3 2 130 4 180 1 - 4A2 140 3 8 180 6 10 40 5 0A3 1 190 2 3 40 5 4 - 3 Vj35685
Z5 = 130*4 +180*1 +140*3 +180*6+40*5+190*2+40*5 = 2980
Полученный план оказывается оптимальным, так как все оценки незагруженных клеток неотрицательны. По этому плану перевозок "Белмагистральавтотранс" отправляет 130 единиц (тонн) продукции потребителю В4 (Германия) и 180 тонн В5 ( Польша); АТЭП-10 отправляет 140 единиц потребителю В1 ( Литва), 180 единиц потребителю В3 (Латвия) и 40 тонн потребителю В5 ( Польша); АТЭП-11 190 единиц потребителю В2 (Венгрия) и 40 тонн потребителю В4 (Германия).
5.2. Применение открытой модели транспортной задачи ( тип 1)
Имеется три поставщика и четыре потребителя. В роли перевозчика выступает ОАО "Белмагистральавтотранс"
с11 с12 с13 a1 4 2 1 100
с21 с22 с23 а2 2 5 3 200
=
с31 с32 с33 а31 1 2 6 80
b1 b2 b3 z 190 120 10 z
Проверим условие ? ai = ? bj
? ai = 100+200+80 = 380
? bj = 190+120+10 = 320
Условие закрытости модели не выполняется ?ai > ?bj, поэтому введём фиктивного потребителя В4 с потребностью В4 = ? ai - ? bj = 380-320 = 60 и положив соответствующие им тарифы перевозок С14 =
0 ( i= 1,3). После введения фиктивного потребителя открытая модель задачи преобразуется в закрытую.
Составим распределительную таблицу 4. 5.
Таблица 4. 5- Распределительная задача
п о т р е б и т е л ьСкладыB1B2B3B4Запас грузаА14210100А22530200А3126080Потребностьв отгрузке1901201060
Полученная задача - закрытого типа и имеет решение. Математическая модель задачи примет вид :
Z = ?? CijXij min
х11+х12+х13+х14=100
х21+х22+х23+х24=200
х31+х32+х33+х34=80
х11+х21+х31=190
х12+х22+х32=120
х13+х23+х33=10
х14+х24+х34=60 xij?0 ( i =1,3; j=1,4)
Среди уравнений системы будет 6 ( 3+4-1 ) линейно-независимых уравнений и начальное опорное решение должно иметь 6 переменных. Для нахождения начального опорного плана воспользуемся методом " минимального элемента" ( метод наименьшей стоимости ). То есть распределяем перевозки по клеткам, которые имеют наименьший тариф перевозок Cij.
Таблица 6 Нахождение опорного плана
Ai1901201060Ui1004
- 21 40- 3200100 + 220 - 510 360 008080 - 1+ 260- 1 Vj2530
Z1= 2*100+2*110+5*20+3*10+1*80 = 630
Проверяем, является ли полученный план оптимальным в смысле суммарной стоимости перевозок.
Найдём потенциалы складов и потребителей ( из условия, что для каждой загруженной клетки Ui+Vj=Cij ).
U1+V2=2
U2+V1=2
U2+V2=5
U2+V3=3
U2+V4=0
U3+V1=1
Поскольку число уравнений на единицу меньше числа потенциалов, то одному из них придадим произвольное значение. Положим, например U2 = 0. Все остальные потенциалы определяются однозначно:
U1= - 3
U3= - 1
V1= 2
V2= 5
V4= 0
Определяем оценки свободных клеток Sij = Cij ( Ui + Vj )
S11= 4-(2-3) = 5
S13=1-(3-3) = 1
S14= 0-(0-3) =3
S32= 2-(5-1) = - 2
S33= 6-(3-1) = 4
S34=0-(0-1) = 1
Построенный план не оптимален, так как среди оценок есть отрицательные. В базис введём переменную Х32, соответствующую отрицательной оценке. Переходим к новому плану. Полученному решению отвечают затраты:
Z2=100*2+2*130+3*10+60*1+20*2=590
Таблица 5.7- Построение опорного плана
Ai1901201060Ui1004100 - 2+ 10- 1200130 + 2+ 510 - 3008060 - 120 + 260- 1Vj2330
Проверяем полученный план на оптимальность, находим о