Диссертация (Модели и алгоритмы определения приоритетного направления движения воздушного судна по заданным маршрутам), страница 5

 0.sk 1  max;x1  a4 j x2  s j  b j , j  1,...., k  1;(1.9)x1  0; x2  0; s j  0.Анализ выражения (1.9) показывает, что решаемая задача записанасистемой из k  1 равенств и k  1 переменных, решением которой является .x1  0 и x2  2 . Значения остальных параметров1 и 0 находят черезпараметры A1 j и A0 j аналогично параметру 1 .Двойственная задача линейного программирования.Аналогично прямой задаче, представленной в стандартной форме, когдакпxi (i  1,...., n)переменнымприсоединеноmискусственныхнеотрицательных переменных s j ( j  1,..., m)z  [C x]  max;Ax  s  b;.x  0; s  0,Двойственная задача также соответствует минимизации линейнойформы, когда к m переменным  j ( j  1,..., m) присоединено n искусственныхпеременных d j (i  1,...., n)L  [b ]  min;AT   d  c;(1.10)  0; d  0.Между прямой и двойственной задачей существует тесная связькоэффициенты сi целевой функции в прямой задаче являются свободными34членамиограниченийв двойственнойзадаче, свободные членыbjограничений прямой задачи становятся коэффициентами целевой функциидвойственной задачи, строки матрицы А становятся столбцами матрицы AT ,знаки неравенств меняются на противоположные и, наконец, задачамаксимизации z по переменным x m заменяется задачей минимизации L попеременнымm ,причемвсоответствиисдоказаннойтеоремойдвойственности [71] достигнутые результаты оптимизации совпадают:max{z}  min{L}.xТаким образом, существует следующее соответствие:x1…….xns1……..sm zd11dnmLВ свойствах двойственных задач заключен важный смысл, имеющийпрактическуюценностьприпроектированиисистемуправления.Действительно, выбор наилучшей в некотором смысле траектории полетапри ограниченных ресурсах или минимизация отведенных ресурсов, скажемрасхода топлива, для осуществления заданного полета, по существу, естьстороны одного и того же процесса.

Более того, инженеру-проектировщикуважно в первую очередь знать, наряду с оптимальным распределениемпараметров системы хi ,влияние на качество ее работы ресурсныхограничений, выявить узкие места и закладывать припроектированиинаиболее рациональный облик летательного аппарата.Ценность имеющихся ресурсов будет низка, если даже их значительноеувеличение не приведет к существенному улучшению целевой функции ,и,наоборот, те ресурсы, которые сдерживают повышение качества в первуюочередь, имеют наибольшую ценность. Таким образом, параметрыiхарактеризуют относительную ценность ограничений b j , их еще называюттеневыми или, точнее, оптимальными теневыми ценами , оценивающими35влияние ограничений не на любую, а на оптимальную систему с выборомоптимальных параметров xi , при рациональном использовании ресурсов.При этом считается, что общая теневая цена ресурсов, отводимых на каждуюиз выбираемых переменных xi , должна быть не меньше получаемого от этойпеременной <<дохода>> ci в целевой функцииmaj 1ji j  ci .Кроме того, оптимальные теневые цены минимизируют общуюmстоимостьb j 1jjресурсов b j .

Это и порождаетдвойственную задачу(1.10).Существует практическая польза от двойственных переменных [72]. Вопервых, удобнее вместо прямой задачи решать двойственную, когда числоограничений m в исходной задаче значительно больше числа n переменных, послечего легконайти исходные переменные хi.

Во-вторых,большие значения двойственных неотрицательных переменных  jдаютточный адрес тех узких мест или активных ограничений, изменение которых позволит существенно улучшить оптимальную структуру системы.1.1.4 Метод ветвей и границ в задаче построения маршрутаИзвестно [20], что задачу поиска оптимальной траектории для системыВС, как прикладную задачу оптимизации, иногда целесообразно свести кзадаче целочисленного программирования.

При решении подобного классазадач широко применяются комбинаторные методы, основанные наупорядоченном переборе наиболее перспективных вариантов и которыеделятся на две основные группы методов: динамического программированияи ветвей и границ.36В литературе [73] также приводятся сведения о том, что для решениямногомерных задач оптимизации целесообразно совместное применениеуказанных выше методов. При этом решение самой задачи однозначноразбивается на этапы. На первом этапе применяется метод динамическогопрограммирования для получения решения отдельно по каждому изограничений.Результаты,полученныеметодомдинамическогопрограммирования, используются для оценки границ значений целевойфункции.

На втором этапе применяется метод ветвей и границ дляопределения способа разбиения множества допустимых вариантов решенийна подмножества, результатом чего является построенное дерев возможныхвариантов, и способ оценки верхней границы целевой функции.Нижеприведенырезультатыанализаособенностейпримененияуказанных выше методов применительно к задаче, решенной в диссертации.Метод ветвей и границ представляет собой один из комбинаторныхметодов. Его сущность заключается в упорядоченном переборе вариантоврешений и рассмотрении только тех, которые, по определенным признакам,оказываются перспективными.

Остальные варианты решений - исключаются.Упорядоченный перебор вариантов решений при применении методаветвей и границ осуществляется путем последовательного разбиениямножества допустимых решений на подмножества. Элементы разбиения,получаемые при выполнении шагов алгоритма, реализующего данный метод,подвергаются проверке, осуществляемой посредством вычисления оценкиснизу для целевой функции на данном подмножестве. В результатеопределяется, содержит данное подмножество оптимальное решение или нет.Вкачествекритерияисключениясоответствующегоподмножестваиспользуется сравнением с наилучшим из найденных решений.Применение метода ветвей и границ для решения конкретной задачиподразумевает реализацию и выполнение следующих процедур:1) ветвления множества возможных решений;2) вычисления нижних и верхних оценок целевой функции.37Организация и выполнение процедуры ветвления множества возможныхрешений, в зависимости от особенностей решаемой задачи, может бытьреализовано одним из двух способов:1.

ветвление множества допустимых решений исходной задачи D;2. ветвление множества D' получаемого из D путем снятия условияцелочисленности на переменные.Способ ветвления множества допустимых решений исходной задачизаключается в выделении подобластей возможных решений путем фиксациизначений отдельных компонент целочисленных переменных.Способ ветвления множества получаемого из множества допустимыхрешений исходной задачи путем снятия условия целочисленности имеетболее широкую область применения, чем первый. Для осуществленияветвления некоторойоптимизационнаяобластизадачасDi' этимцелевойспособом нафункциейDi'исходнойрешаетсязадачиидействительными переменными.Процедура ветвления реализуется в случае, когда в оптимальномрешении значение хотя бы одной целочисленной переменной по исходнойпостановке задача не является целочисленным.

Тогда среди такихпеременных выбирается одна, например j – я, значение которой в найденномоптимальном решении обозначим через x0[j]. Далее область Di' разделяетсяна две подобласти Di1' и Di2' следующим образом:Di1  Di  ( x[ j ]  [ x0[ j ]]);Di2  Di  ( x[ j ]  [ x0[ j ]]  1);(1.11)где [x0[j]] – целая часть значения x0[j].На рис. 1.11 представлена условная геометрическая интерпретацияветвления.38.Рисунок 1.11 – Иллюстрация условной геометрическая интерпретацияветвленияАнализ рисунка показывает, что из области Di' удаляется часть междуплоскостями вновь введенных ограничений. Так как переменная x[j], поусловиям области допустимых решений исходной задачи – целочисленная, тоиз подобласти допустимых решений исходной задачи Di (DiDi') неисключается ни одного решения.Для формирования нижних и верхних границ оценок целевой функциизадача дискретного программирования была представлена в виде:min f ( x),xDгде х – вектор оптимизационных переменных, среди которых частьдействительных, а часть целочисленных; f(x) – в общем случае нелинейнаяцелевая функция; D – область допустимых решений задачи дискретногопрограммирования общего вида.Нижние оценки целевой функции в зависимости от выбранного способаветвления определяются либо для подобластей DiDi'D, либо для подобластейD' (Di' и D' получены из соответствующих множеств Di и D путемснятия условий целочисленности на дискретные переменные).Математическое описание нижней оценки целевой функции f(x) намножестве Di (или Di') имеет вид: i  inf f ( x)x  Di39Главным условием выбора нижних оценок решения для каждойконкретной задачи является условие ее близости к действительнымзначениям min f(x).Таким образом, математическая запись способа вычисления нижнихоценок целевой функции имеет вид: i  inf f ( x)x  DiОпределенная таким образом ξi является нижней оценкой f(x) на Di (илиDi'), так как DiDi'.Если при решении задачи установлено, что Di   , то для общностиследует полагать, что  i   [32].Совместно с нижней оценкой в методе ветвей и границ используютсяверхние оценки f(x).