Транспортная задача: моделирование и оптимизация процесса стратегического использования парка воздушных судов (ВС) на сети воздушных линий (ВЛ) с запретными для посадки аэропортами

ЛЕКЦИЯ НА ТЕМУ «Транспортная задача: моделирование и оптимизация процесса стратегического использования парка воздушных судов (ВС) на сети воздушных линий (ВЛ) с запретными для посадки аэропортами». РАЗБОР ЗАДАЧИ Постановка задачи. Авиакомпания 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 j1 значения грузооборота 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 то вводится фиктивное ВС, а если j1 4 a  b ,, i i 1 3 j то j1 4 вводится фиктивная ВЛ. В нашем случае  a i   b j , поэтому введём i 1 j1 фиктивное ВС 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  512  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 млн. ткм.