Выбери формат для чтения
Загружаем конспект в формате pdf
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
ЛЕКЦИЯ НА ТЕМУ «Транспортная задача: моделирование и
оптимизация процесса стратегического использования парка воздушных
судов (ВС) на сети воздушных линий (ВЛ) с запретными для посадки
аэропортами». РАЗБОР ЗАДАЧИ
Постановка задачи. Авиакомпания Q выполняет рейсы по n=4
воздушным линиям (ВЛ) на m=3 типах воздушных судов (ВС). Известны:
1) cij – транспортные расходы на 1 млн. ткм на i-ом типе ВС по j-ой ВЛ
(ден. усл. ед./млн. ткм);
2) ai – потенциал i-ого типа ВС (млн. ткм);
3) bj – спрос по грузообороту по j-ой ВЛ (млн. ткм).
На ВЛ1 не используется 1 тип ВС, а на ВЛ2 – 2 тип ВС. В этом случае
расходы c11=100 и c22 =100. Исходные данные задачи cij, ai, bj представлены в
таблице. Требуется составить оптимальный план перевозок ВС по ВЛ, (т.е.
найти все значения xij (млн. ткм)), дающий минимальные транспортные
расходы.
Начальное
решение
рекомендуется
находить
по
методу
минимальной стоимости, а затем решать задачу с использованием метода
потенциалов.
Тип ВС
1
2
3
bj
ВЛ 1 ВЛ 2 ВЛ 3 ВЛ 4
100
10
6
9
7
100
6
11
8
6
10
12
40
50
40
50
аi
60
45
55
Математическая постановка задачи:
3
4
Найти минимальное значение целевой функции z c ij x ij и все
i 1 j1
значения грузооборота xij (млн. ткм), если заданы ограничения:
4
xij ai ,
j 1
3
xij 0, i 1, 2,3, j 1, 2, 3, 4.
x b ,
ij
j
i 1
Решение задачи
Данная задача является несбалансированной (задачей открытого типа),
3
т.к. ai 60 45 55 160,
i 1
b
i
40 50 40 50 180 и 160 180.
j 1
3
Если
4
4
3
a b ,
i
i 1
j
то вводится фиктивное ВС, а если
j1
4
a b ,,
i
i 1
3
j
то
j1
4
вводится фиктивная ВЛ. В нашем случае a i b j , поэтому введём
i 1
j1
фиктивное ВС 4. Для этого добавим в таблицу одну строку. Тогда а4 =180160=20, а расходы с41, с42, с43, с44 по всем ВЛ равны 0. Следует обратить
внимание, что в этом случае число ВС равно m+1=4 (это важно).
Тип ВС
1
2
3
4
bj
ВЛ1 ВЛ2 ВЛ3 ВЛ4 аi
100 10
6
9 60
7
100
6
11 45
8
6
10
12 55
0 20
40
50
40
50
Найдём начальное решение (опорный план) методом минимальной
стоимости, для этого сначала определим число базисных (Чбп) и небазисных
переменных (Чнп).
Чбп = Число ВС + Число ВЛ – 1 = (m+1)+n-1= m+n=4+4-1=7;
Чнп = Число ВС x Число ВЛ – Чбп = (m+1)n-( m+n)=16-7=9.
В процессе решения таблицу транспортных расходов и таблицу
перевозок будем объединять в одну. Метод заключается в том, что сначала в
таблице выбирается ячейка с наименьшими расходами cij. Далее переменной
xij присваивается наибольшее значение, допускаемое ограничениями на
прогноз спроса и потенциал ВС. При получении начального решения нужно
следить за балансом базисных и небазисных переменных. Если количество
базисных переменных оказалось меньше, чем небазисных, то такой опорный
план называется вырожденным. В этом случае одной из переменных xij
нужно присвоить значение, равное 0.
Также при составлении начального опорного плана для задачи с
фиктивным ВС (или ВЛ) и запретными для посадки аэропортами нужно
учитывать следующие отличительные особенности, которые не возникают
при использовании обычного метода минимальной стоимости.
1. Необходимо выбирать ячейку с наименьшей стоимостью только
среди реальных ВС (с ячейками, неравными нулю), а потенциал фиктивного
ВС распределять в последнюю очередь.
2. Сначала заполняются строки с «запретными» ячейками (там, где
значения 100).
Тип ВС
ВЛ1 ВЛ2 ВЛ3 ВЛ4 аi
1
2
100
6
40
7
100
6
11
5
8
6
10
50
4
9
20
40
3
bj
10
12
5
20
40
50
40
60
45
55
20
50
В первой строке переменной x13 присвоим значение, равное 40, а переменной
x14 =20. Во второй строке переменная x21 =40, а x24 =5. Далее заполняем
ячейки x32 =50, x34 =5 и x44 =20.
Базисные переменные: x13, x14, x21, x24, x32, x34, x44.
Небазисные переменные: x11, x12, x22, x23, x31, x33, x41, x42, x43.
Соотношение базисных (7) и небазисных (9) переменных выполняется. При
этом значения всех небазисных переменных равны 0.
Найдём начальное решение целевой функции z0:
z0 40 6 20 9 40 7 5 11 50 6 512 20 0 1115 .
Проверим
оптимальность
полученного
плана
с
помощью
метода
потенциалов. Всем ВС поставим в соответствие потенциалы ui, а ВЛ –
потенциалы vj (не следует путать метод потенциалов с потенциалом ВС ai).
Потенциалы находим из условий для базисных переменных ui + vj = cij.
Одному из потенциалов (как правило, это u1) присваиваем произвольное
значение, например, 0. Пусть u1=0. Последовательно находим потенциалы по
значениям стоимостей ячеек x13, x14, x24, x21, x34, x32, x44:
u1 + v3 =6; v3=6 - 0; v3=6;
u1 + v4 =9; v4=9 - 0; v4=9;
u2 + v4 =11; u2=11 - 9; u2=2;
u2 + v1 =7; v1=7 - 2; v1=5;
u3 + v4 =12; u3=12 - 9; u3=3;
u3 + v2=6; v2=6 - 3; v2=3;
u4 + v4 =0; u4=0 - 9; u4=-9.
Для всех небазисных переменных найдём оценки из условия clk* = ul+ vk - clk.
x11 :
c11* = u1 + v1 – c11=0 + 5 – 100= –95;
x12 :
c12* = u1 + v2 – c12=0 + 3 – 10= –7;
x22 :
c22* = u2 + v2 – c22=2 + 3 – 100= –95;
x23 : c23* = u2 + v3 – c23=2 + 6 – 6= 2;
x31 : c31* = u3 + v1 – c31=3 + 5 – 8= 0;
x33 : c33* = u3 + v3 – c33=3 + 6 – 10= –1;
x41 : c41* = u4 + v1 – c41= – 9 + 5 – 0= –4;
x42 : c42* = u4 + v2 – c42= – 9 + 3 – 0= –6;
x43 : c43* = u4 + v3 – c43= – 9 + 6 – 0= –3.
Условие
оптимальности
выполняется,
если
все
оценки
небазисных
переменных неположительны. В данной ситуации условие оптимальности не
выполнено. В этом случае в базис будет вводиться та небазисная переменная,
которая имеет наибольшую положительную оценку. В рассматриваемой
задаче такая переменная только одна – переменная x23 с оценкой, равной 2,
поэтому именно она и будет введена в базис.
На следующем этапе необходимо определить переменную, которая
будет выводиться из базиса, иначе соотношение базисных и небазисных
переменных будет нарушено. Для этого построим замкнутый цикл, который
начинается и заканчивается в ячейке с вводимой в базис переменной x23.
Контур состоит из последовательности горизонтальных и вертикальных
стрелок любой длины, соединяющих ячейки, соответствующие текущим
базисным переменным, и ячейку с вводимой в базис переменной. Вновь
вводимой переменной присвоим знак «+», знаки остальных переменных
будут чередоваться. В контур включаем максимально возможное число
базисных переменных. Получаем контур: x23→ x13 → x14 →x24 → x23.
Тип ВС
1
2
ВЛ1 ВЛ2 ВЛ3 ВЛ4 аi
100
6
-
+
40
7
100
+
6
11
-
5
8
6
10
50
4
9
20
40
3
bj
10
12
5
20
40
50
40
60
45
55
20
50
По условию допустимости выводимой из базиса переменной является
та переменная, которой присвоен знак «-» и которая имеет наименьшее
значение. Это переменная x24 (значение 5 меньше значения 40 в ячейке x13).
Построим новый улучшенный план перевозок. К переменным, которым
присвоен знак «+», прибавим число 5, а от переменных, которым присвоен
знак «-», отнимем 5.
Тип ВС
1
2
ВЛ1 ВЛ2 ВЛ3 ВЛ4 аi
100
6
35
7
100
40
6
6
11
10
50
4
9
25
5
8
3
bj
10
12
5
20
40
50
40
60
45
55
20
50
Получили, что новой базисной переменной стала переменная x23, а
небазисной – переменная x24, остальные базисные и небазисные переменные
не изменились.
Найдём новое базисное решение z1:
z 1 35 6 25 9 40 7 5 6 50 6 5 12 20 0 1105 .
Решение улучшилось на 10 ден. усл. ед. Проверим его оптимальность.
Найдём значения потенциалов для нового опорного плана и оценки
небазисных переменных. Пусть u1=0, тогда
u1 + v3 =6; v3=6 - 0; v3=6;
u1 + v4 =9; v4=9 - 0; v4=9;
u2 + v3 =6; u2=6 - 6; u2=0;
u2 + v1 =7; v1=7 - 0; v1=7;
u3 + v4 =12; u3=12 - 9; u3=3;
u3 + v2=6; v2=6 - 3; v2=3;
u4 + v4 =0; u4=0 - 9; u4=-9.
Для всех небазисных переменных найдем оценки из условия clk* = ul+ vk - clk.
x11 :
c11* = u1 + v1 – c11=0 + 7 – 100= –93;
x12 :
c12* = u1 + v2 – c12=0 + 3 – 10= –7;
x22 :
c22* = u2 + v2 – c22=0+ 3 – 100= –97;
x24 : c24* = u2 + v4 – c24=0 + 9 – 11= –2;
x31 : c31* = u3 + v1 – c31=3 + 7 – 8= 2;
x33 : c33* = u3 + v3 – c33=3 + 6 – 10= –1;
x41 : c41* = u4 + v1 – c41= – 9 + 7 – 0= –2;
x42 : c42* = u4 + v2 – c42= – 9 + 3 – 0= –6;
x43 : c43* = u4 + v3 – c43= – 9 + 6 – 0= –3.
Условие оптимальности не выполняется. В базис будем вводить
переменную x31, которая является единственной, имеющей положительную
оценку. Берём контур: x31→ x21 →x23→ x13 → x14 →x34 → x31.
Тип ВС
ВЛ1 ВЛ2 ВЛ3 ВЛ4 аi
100
1
2
3
6
-
+
35
7
-
100
40
+
+
6
9
25 60
11
5
8
6
10
50
4
bj
10
-
12
5
20
40
50
40
45
55
20
50
Выводимой из базиса переменной является переменная, которой
присвоен знак «-» и которая имеет наименьшее значение. Это переменная x34
(в ячейке x34 стоит знак «-» и значение 5 меньше значений 40 и 35 в ячейках
x21 и x13 соответственно). К переменным, которым присвоен знак «+»,
прибавим число 5, а от переменных, которым присвоен знак «-», отнимем 5.
Получим новый улучшенный план перевозок.
Тип ВС
1
2
3
ВЛ1 ВЛ2 ВЛ3 ВЛ4 аi
100
6
30
7
100
9
30
6
11
6
10
12
35
10
8
5
50
4
bj
10
20
40
50
40
60
45
55
20
50
Найдём новое базисное решение z2:
z 2 30 6 30 9 35 7 10 6 5 8 50 6 20 0 1095 .
Решение улучшилось на 10 ден. усл. ед. Проверим его оптимальность.
Найдём значения потенциалов ui и vj. Пусть u1=0, тогда
u1 + v3 =6; v3=6 - 0; v3=6;
u1 + v4 =9; v4=9 - 0; v4=9;
u2 + v3 =6; u2=6 - 6; u2=0;
u2 + v1 =7; v1=7 - 0; v1=7;
u3 + v1=8; u3=8 - 7; u3=1;
u3 + v2=6; v2=6 - 1; v2=5;
u4 + v4 =0; u4=0 - 9; u4=-9.
Для всех небазисных переменных найдём оценки clk*.
x11 :
c11* = u1 + v1 – c11=0 + 7 – 100= –93;
x12 :
c12* = u1 + v2 – c12=0 + 5 – 10= –5;
x22 :
c22* = u2 + v2 – c22=0+ 5 – 100= –95;
x24 : c24* = u2 + v4 – c24=0 + 9 – 11= –2;
x33 : c33* = u3 + v3 – c33=1 + 6 – 10= –3;
x34 : c34* = u3 + v4 – c34=1 + 9 – 12= –2;
x41 : c41* = u4 + v1 – c41= – 9 + 7 – 0= –2;
x42 : c42* = u4 + v2 – c42= – 9 + 5 – 0= –4;
x43 : c43* = u4 + v3 – c43= – 9 + 6 – 0= –3.
Положительных
оценок
нет,
поэтому
условие
оптимальности
выполняется. Значит, найденное выше решение z2, является оптимальным.
Минимальные транспортные расходы составят 1095 ден. усл. ед.
Из последней таблицы делаем следующие выводы. Потенциал ВС 1
предполагается направить по ВЛ 3 и ВЛ 4 в равных количествах по 30 млн.
ткм. Потенциал ВС 2 – по ВЛ 1 в количестве 35 млн. ткм и ВЛ 3 в количестве
10 млн. ткм. Потенциал ВС 3 – по ВЛ 1 и ВЛ 2 в количествах,
соответственно, 5 млн. ткм и 50 млн. ткм. Отметим, что спрос по
грузообороту для ВЛ 4 останется частично неудовлетворённым, будет
недопоставлено 20 млн. ткм.