Транспортная политика в Республике Беларусь
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?енки свободных клеток
S11= 4-(2-1) = 3
S13=1-(3-1) = -1
S14=0-(0-1) = 1
S22=5-(3+0) = 2
S33=6-(3-1) = 4
S34=0-(0-1) = 1
Построенный план не оптимален. В базис вводим переменную Х13 и переходим к новому плану (таблица 5.8 ):
Таблица 5.8 Новый опорный план
Ai1901201060Ui100490 210 10- 1200140 25360 008050 130 260- 1 Vj 2 3 3 0
Полученному решению отвечают затраты:
Z=2*90+10*1+140*2+50*1+30*2=580
Проверяем полученный опорный план на оптимальность:
S11= 4-(2-1) = 3
S14= 0-(0-1) = 1
S22= 5-(3+0) = 2
S23= 3-(2+0) = 1
S33= 6-(2-1) = 5
S34= 0-(0-1) = 1
Полученный опорный план является оптимальным, так как все оценки незагруженных клеток неотрицательны. По этому плану "Белмагистральавтотранс" отправляет от первого поставщика 90 единиц продукции (тонн) потребителю В4 (Германия) и 10 единиц продукции потребителю В3 (Латвия). От второго поставщика "Белмагистральавтотранс" перевозит 140 единиц продукции потребителю В1 (Литва), при этом на складе остаётся 60 единиц продукции. От третьего поставщика "Белмагистральавтотранс" везёт 50 единиц потребителю В1 (Литва) и 30 единиц потребителю В2 (Венгрия). Затраты при этом будут минимальными и составят Zmin = 580 ден. ед.
(тыс.долл.США ).
5.3. Применение закрытой модели транспортной задачи (тип 2)
"Белмагистральавтотранс", АТЭП-10, АТЭП-11, "Интертехавто"
(Ai (i= 1,4)) на различный срок предоставляют складские помещения фирмам Bj (j=1,4) за плату Cij. Выделяемая площадь ai, потребность фирм в площадях bj ( тыс. кв. м) и арендные платы Cij из раiёта 100 ден. ед.
Таблица 5. 9- Исходные данные
Ai B1 B2 B3 B4 Ui A1 15 20 18 - 140 A2 19 17 16 - 100 A3 12 14 21 - 100 A4 18 15 20 - 60 Vj 200 100 150 -
Проверим условие ?ai = ? bj
- ai = 140+100+100+60=400
- bj = 200+100+150=450
Таким образом, условие закрытости модели не выполняется, поэтому надо вводить фиктивное предприятие, предоставляющее складские площади в размере а5=50 кв м и арендной платой С5j=0 (j=1,3). После введения фиктивного предприятия открытая модель задачи преобразовалась в закрытую. Составим распределительную таблицу:
Таблица 5.10 - Распределительная задача
AiB1B2B3Ui"Белмагистарльавтотранс"152018140"АТЕП-10"191716100"АТЭП-11"121421100"Интертехавто"18152060 A500050 Потребность в площадях 200100150
450
Экономико-математическая модель задачи примет вид:
Пусть Хij- площадь, выделяемая "Белмагистральавтотранс" предприятию Bj (i=1.5;j=1.3)
Тогда суммарная прибыль, получаемая "Белмагистральавтотранс" от предприятий, представлена целевой функцией:
F = CijXij (1)
Система ограничений примет вид:
?Xij = ai (i=1.5) (2)
?Cij=bi (j=1.3)
Xij ? (i=1.5;j=1.3) (3)
Решим поставленную задачу методом потенциалов. Начальный опорный план определим по правилу минимального элемента.
Таблица 5.11 Построение начального опорного плана
Ai200 100 150 Ui 140 - 40 15 100 20 + * 1815 100 100 19 17 1619 100 12 14 100 2119 60 + 10 18 15 - 50 20 18500000 Vj 0 5 2
Получен невырожденный опорный план, которому соответствует значение целевой функции: F1 = 40*15+100*20+100*19+100*21+18*10+50*20=7780
Найдём потенциалы (из условия, что для каждой загруженной клетки (Ui+Vj=Cij)
U1+V1=15
U1+V2=20
U2+V1=19
U3+V3=21
U4+V1=18
U4+V3=20
U3+V1=0
Поскольку число уравнений на единицу меньше числа потенциалов, то одному из них придадим произвольное значение. Положим, например, V1=0. Все остальные потенциалы определяются однозначно:
U1=15; U2=19; U4=18; U5=0;
V2=20-U1=20-15=5;
V3=20-U4=20-18=2;
U3=21-V3=21-2=19;
Определяем оценки свободных клеток:
Sij=Cij-(Ui+Vj)
S13=18-915+2)=1
S22=17-(19+5)= -7
S31=12-(19+0)= - 7
S23=16-(19+2)= - 5
S32=14-(19+5)= - 10
S42=15-(18+5)= - 8
S52=0-(0+5)= - 5
S53=0-(0+2)= - 2
Полученный план не оптимален. Среди оценок имеется положительная S13=1.Необходимо загрузить клетку (1,3). Построим замкнутый цикл для клетки (1,3). В отрицательных вершинах цикла наименьшее количество площадей равно
min (40,50) = 40.
Получаем новый план распределения площадей:
Таблица 5.12- Новый план распределения площадей
Ai200 100 150 Ui 140 15 100 20 40 1815 100 100 19 17 1619 100 12 14 100 2119 60 50 18 15 10 20 1850 50 0 000 Vj 0 4 2
Получен опорный план, которому соответствует значение целевой функции:
F2=100*20+40*18+100*19+100*21+50*18+10*20=7820
Найдём потенциалы:
U1+V2=20 V1=0;U2=19;U4=18;U5=0;
U1+V3=18 V3=20-U4=20-18=2;
U2+V1=19 U1=18-V3=18-2=16;
U3+V3=21 U3=21-V3=21-2=19;
U4+V1=18 V2=20-U1=20-16=4;
U4+V3=20
U5+V1=0
Определяем оценки свободных клеток:
S11=15-(16+0)= - 1
S22=17-(19+4)= -5
S31=14-(19+4)= - 9
S23=16-(19+2)= - 5
S42=15-(18+4)= - 7
S52=0-(0+4)= - 4
S53=0-(0+2)= - 2
Так как все оценки клеток отрицательны, то полученный план размещения складских площадей оптимален, а так как среди оценок нет нулевых, то оптимальный план