Транспортная политика в Республике Беларусь
Проверим
полученный
план на оптимальность.
Для этого i-ой
строке и j
–му столбцу
ставим в соответствие
числа Ui
и Vj (потенциалы).
Для каждой
базисной переменной
Xij потенциалы
должны удовлетворять
условию Ui+Vj=Cij.
Получаем систему:
U1+V3=2
U1+V5=1
U2+V2=8
U2+V3=6
U2+V4=10
U3+V1=1
U3+V2=2
Так как система состоит из 7 уравнений, а неизвестных 8, то, чтобы найти численное решение этой системы, одно из неизвестных зададим произвольно, тогда остальные переменные найдутся из системы однозначно.
Пусть U2=0, тогда V2=8
V3=6
V4=10
U1=2-V3=2-6 = - 4
U3=2-V2=2-8 = - 6
V1=1-U3= 1-(- 6)=7
V5=1-U1= 1-(- 4)=5
Теперь для небазисных переменных (свободных) рассмотрим оценки:
Sij=Cij-(Ui+Vj)
S11=5- (- 4+7) = 2
S12=3-(- 4+8) = - 1
S14=4-(- 4+10) = -2
S21=3-(0 +7) = - 4
S25=5-(0+5) = 0
S33=3-(- 6+6) = 3
S34=5-(- 6+10) = 1
S35=4-(- 6+5) = 5
В силу критерия оптимальности ( все оценки Sij неотрицательны) делаем вывод, что построенный план не оптимален, т.к. среди оценок есть отрицательные. В базис введём переменную Х21 (отвечающую наибольшей по модулю отрицательной оценке) и строим замкнутый контур с вершинами в загруженных клетках. Присваиваем клеткам в вершинах контура поочерёдно по часовой стрелке знаки "+" и "-", начиная с (2,1), которой присваиваем знак "+". Выбираем наименьшее значение из клеток со знаком "-" (min ( 140, 100 ) = 100 ) и перераспределяем продукцию вдоль контура, прибавляя 100 к значениям в клетках со знаком "+" и вычитая из значения в клетках со знаком "-". В результате приходим к таблице5.2.
Таблица 5.2 - Построение опорного плана
| Ai | B1 | B2 | B3 | B4 | B5 | Ui |
| A1 | 5 | 3 | 90 2 | 4 | 220 1 | -4 |
| A2 | *100 + 3 | 8 | 90 6 | 170 - 10 | 5 | 0 |
| A3 | 40 - 1 | 190 2 | 3 | * + 5 | 4 | -2 |
| Vj | 3 | 4 | 6 | 10 | 5 |
Полученному решению отвечают затраты:
Z2 = 90*2 + 220*1 +100*3 + 90*6 +170*10 + 40*1+190*2 = 3360
Проверяем полученный план на оптимальность и получаем, что S34 = - 3 < 0, значит решение не оптимальное и строим в таблице 2 новый цикл пересчёта для клетки (3,4). Так как min (220,90,40) = 40 = Xij, то перераспределяем продукцию вдоль контура, прибавляя 40 к значениям в клетках со знаком "+" и вычитая из значений в клетках со знаком "-". В результате получаем таблицу5.3.
Таблица 5.3 - Нахождение оптимального плана
| Ai | B1 | B2 | B3 | B4 | B5 | Ui |
| A1 | 5 | 3 | 2 | + 90 4 | 220 - 1 | - 6 |
| A2 | 140 3 | 8 | 180 6 | - 40 10 | * + 5 | 0 |
| A3 | 1 | 190 2 | 3 | 40 5 | 4 | - 5 |
| Vj | 3 | 7 | 6 | 10 | 7 |
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 - Новый опорный план
| Ai | B1 | B2 | B3 | B4 | B5 | Ui |
| A1 | 5 | 3 | 2 | 130 4 | 180 1 | - 4 |
| A2 | 140 3 | 8 | 180 6 | 10 | 40 5 | 0 |
| A3 | 1 | 190 2 | 3 | 40 5 | 4 | - 3 |
| Vj | 3 | 5 | 6 | 8 | 5 |
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- Распределительная задача
| п о т р е б и т е л ь |
| Склады | B1 | B2 | B3 | B4 | Запас груза |
| А1 | 4 | 2 | 1 | 0 | 100 |
| А2 | 2 | 5 | 3 | 0 | 200 |
| А3 | 1 | 2 | 6 | 0 | 80 |
| Потребность | ||||
| в отгрузке | 190 | 120 | 10 | 60 |
Полученная задача - закрытого типа и имеет решение. Математическая модель задачи примет вид :
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 – Нахождение опорного плана
| Ai | 190 | 120 | 10 | 60 | Ui |
| 100 | 4 | 2 | 1 4 | 0 | - 3 |
| 200 | 100 + 2 | 20 - 5 | 10 3 | 60 0 | 0 |
| 80 | 80 - 1 | + 2 | 6 | 0 | - 1 |
| Vj | 2 | 5 | 3 | 0 |
Получен невырожденный опорный план, которому соответствует значение целевой функции:
Z1= 2*100+2*110+5*20+3*10+1*80 = 630
Проверяем, является ли полученный план оптимальным в смысле суммарной стоимости перевозок.
Найдём потенциалы складов и потребителей ( из условия, что для