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

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

5 Применение экономико-математических методов на автотранспортных предприятиях

5.1 Пример решения закрытой модели транспортной задачи

Имеются три поставщика ОАО "Белмагистральавтотранс", АТЭП – 10 , АТЭП – 11 и пять потребителей некоторой продукции. Количество груза аi, которое может отгрузить поставщик i ( i =1.3), и стоимость перевозки из пункта i в пункт j единицы груза Сij заданы таблицей.( bj- потребности, j= 1,5)

с11 с12 с13 с14 с15 а1 5 3 2 4 1 310

с21 с22 с23 с24 с25 а2 = 3 8 6 10 5 360

с31 с32 с33 с34 с35 а3 1 2 3 5 4 230

b1 b2 b3 b4 b5 z 140 190 180 170 220 z

Составить экономико-математическую модель задачи и найти методом потенциалов оптимальный план перевозки продукции (при котором общие транспортные затраты будут наименьшими).

Для решения строим математическую модель задачи. Через Хij обозначим объём продукции, доставленной от поставщика Аi (i=1,2,3) потребителю Bj (j=1,5). Отметим, что в данном случае сумма количества продукции, которую могут отгрузить все поставщики, совпадает с суммой потребностей потребителей:

310+360+230=140+190+180+170+220- 900 (*)

Значит, задача закрытого типа и имеет решение. Математическая модель задачи принимает вид:

Z=∑∑CijXij min (1)

x11+x12+x13+x14+x15=310

x21+x22+x23+x24+x25=280

x31+x32+x33+x34+x35=320 (2)

x11+x21+x31=140

x12+x22+x32=190

x13+x23+x33=180

x14+x24+x34=170

x15+x25+x35=220

Xi j ≥ 0(i=1,2,3; j=1,5) (3)

Полученную транспортную задачу будем решать методом потенциалов. В силу выполнения условия (*) среди уравнений системы (2) будет 3+5-1=7 линейно независимых и начальное опорное решение должно иметь 7 переменных. Для нахождения его воспользуемся методом "минимального элемента":

Таблица 5.1- Построение опорного плана

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

Z1 = 90*2+220*1+100*8+90*6+170*10+140*1+90*2 =3760

П роверим полученный план на оптимальность. Для этого 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 - Построение опорного плана

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

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

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

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- Распределительная задача

Полученная задача - закрытого типа и имеет решение. Математическая модель задачи примет вид :

Z = ∑∑ CijXij min

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

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