Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 22)

х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 – Нахождение опорного плана

Получен невырожденный опорный план, которому соответствует значение целевой функции:

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- Построение опорного плана

Проверяем полученный план на оптимальность, находим оценки свободных клеток

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 – Новый опорный план

Полученному решению отвечают затраты:

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 из расчёта 100 ден. ед.

Таблица 5. 9- Исходные данные

Проверим условие Σai = Σ bj

• ai = 140+100+100+60=400

• bj = 200+100+150=450

Таким образом, условие закрытости модели не выполняется, поэтому надо вводить фиктивное предприятие, предоставляющее складские площади в размере а5=50 кв м и арендной платой С5j=0 (j=1,3). После введения фиктивного предприятия открытая модель задачи преобразовалась в закрытую. Составим распределительную таблицу:

Таблица 5.10 - Распределительная задача

Экономико-математическая модель задачи примет вид:

Пусть Х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 – Построение начального опорного плана

Получен невырожденный опорный план, которому соответствует значение целевой функции: F1 = 40*15+100*20+100*19+100*21+18*10+50*20=7780

Найдём потенциалы (из условия, что для каждой загруженной клетки (Ui+Vj=Cij)

Характеристики

Список файлов ВКР