Диссертация (Система управления приоритетным обслуживанием воздушных судов при заходе на посадку и пассажиров в аэропорту после прилета), страница 10

Непосредственные повторныерасчеты прямой задачи показывают, что полученный ответ, как и прежде,соответствует вершине D, что обнадеживает, хотя при неотрицательностивесовых коэффициентов Ci допуск (3.4) на C1 получился в данном примереодносторонним.Теперь можно снова вернуться к вопросу получения данныхтаблицы 3.4 без использования строки целевой функции, учитывая при еевосстановлении только факт принадлежности выбранной вершины каклучшего решения.733.4 Формирование матрицы данных для выбранной оптимальнойвершины без использования строки целевой функцииЧтобы решить эту частную задачу, обратимся к исходной таблице 3.1,для которой начало координатX1  X 2  0 являетсяпервой опорнойвершиной, с чего начинается план обхода многогранника.

В прямой задачеэтой ситуации, во-первых, нулевыми являются исходные переменные X 1 иX 2 , и своими обозначениями они уже отличаются от ненулевых переменныхS j . В назначенной ЛПР оптимальной вершине нулевыми переменными могутбыть как координаты X i , так и переменные S j . Поэтому стоит их, как былосказано выше, выделить для наглядности в первой строке и в левом столбценачальной таблицы 3.1 особыми координатами yl , которые для вершины Dсоответствуютискусственнымпеременным S1 и S3 , т.е. пусть S1  y1 , S3  y2 .Во-вторых,припереходеизвершиныAвсоседнюювершинуосуществляется замена одной из имеющихся ненулевых переменных(например, S 2 из общего из множества, указанного в левом столбцетаблица1).

Эта замена осуществляется известным в прямом симплекс-методеспособом назначения ведущего столбца (с помощью строки целевойфункции), ведущей строки и пересчета всех строк таблицы в новую матрицу.В нашем случае отсутствия целевой функции в качестве назначаемогостолбца можно взять первым любой, соответствующий одной из координатX i , а в качестве ведущей строки-туиз принадлежащих к переменным y jстроку, у которой неотрицательное отношениеbjaijминимально.В-третьих, оптимальная вершина преимущественно не являетсяближайшей к началу координат, и поэтому при n=2 отличается не одной, адвумя ненулевыми переменными- вместо X 1 и X 2 ими должны статьпеременные y1 и y2 , как это показано в таблице 3.8.74Таблица 3.8.

Матрица I исходных данных с указанием нулевых переменных вназначенной оптимальной вершине1210008-1+101001010010243000124В связи с этим предлагается перенестиначало преобразований извершины A сразу в оптимальную вершину D путем двойного пересчетатаблицы 3.1. При этом считается, что нам задана симплекс-таблица в видетех же строк, но строка целевой функции пустая, так как весовыекоэффициенты критерия не назначены. Однако имеются координаты лучшейвершинымногогранника.Если известно, чтооптимальнаявершинанаходится в какой-то точке, то исскуственные переменные в этой точкесоответствуют двум равенствам и равны нулю.

Значит, нам просто даны ещестолбцысимплекс-таблицы, в которых исскуственные переменные равнонулю. x 1x1x2Рис 3.3. Сравнение действий при поиске ближайшихсоседних вершин впрямом и предложенном обратном симплекс-методеРазница в известном и предложенном методах состоит в следующем :x275При решении прямой задачи поиск лучшей вершины начинается сначала координат при движении по контуру многогранника.

При решенииобратной задачи необходимо начать движение с лучшей вершины, а не сначала координат, а затем, как и в прямом методе, нужно искать ближайшиесоседние вершины.Обратный метод - зная оптимальную вершину, смотрим всеближайшие вершины, рядом находящиеся, получаем координаты соседнихвершин, как показано на рис 3.3. А дальше уже можно составитьнеобходимые неравенства.Отличие состоит в том, что движение при поиске начинается несначала координат, а с оптимальной вершины.

Во-вторых, это движениепроисходит во всех возможных направлениях движения. Таким образом,обратная задача будет решена, если:1 – есть правило переноса расчета из начала координат в оптимальнуювершину;2 – есть правило выбора всех сближающих соседних вершин;3 – пишутся неравенства для всех соседних вершин согласно критерию(3.1),куда входят все неизвестные коэффициенты,в частности C1 и C2. Получаетсясистема неравенств или условия двухстороннего допуска.Иными словами, предлагается новый ―опорный план‖ с началом в вершинеD.С этой целью исходную таблицу 3.1 преобразуем в матрицу I этогоопорного плана, которая не содержит строки целевой функции, аискусственные переменные S1 и S3 в левом столбце и правой строкезаменены на нулевые переменные y1 и y2 , играющие роль системы отсчетакоординат вместо X 1 и X 2 .76Нужно сразу заметить, что в самом начале решения нам известны лишькоординаты X1 (0)  4 и X 2 (0)  2 вершины D без указания того, какиенеравенства для этой вершины превращаются в равенства, или какиепеременные становятся нулевыми.

Но это нетрудно сделать предварительно,подставив значения X i (0) в имеющиеся ограничения (3.2). В частности, вданном примере из условий (3.2) получим при X1  4 : X 2  21. S1  8  X1  2 X 2  02. S2  1  X1  X 2  33. S3  2  X 2  04. S4  24  4 X1  3 X 2  2Видно, что нулевыми переменными в вершине D стали S1 и S3 ,которые переобозначены через y1 и y2 . В общем случае в имеющиесялинейные неравенстваna xi 1ij i b j ; j  1...k(3.5)вводятся искусственные переменные S j , чтобы получить равенства, решениекоторых при заданных координатах X i (0) оптимальной вершины дает ответ,какие из этих переменных нулевые. Число этих переменных Sl  0(l  1....n)равно n, и их нужно обозначить через yl , если для них выполняются условияnSl  yl  bl   ail xi (0)  0; l  1,.....n(3.6)i 1Проведем теперь необходимые расчеты.

Возьмем в качестве любой изкоординат X i переменную X 1 , что определяет ведущим столбец 2. В этомстолбце среди строк 2 и 4, принадлежащих переменным y1 и y2 , ведущей77является строка 2, не требующая дополнительной нормализации. Поэтомувычтем ее из остальных строк и получим новую промежуточную таблицу 3.9.Таблица 3.9. Таблица данных после замены переменной y1 на X 11210008031100901001020-5-4001-8После обращения к столбцу с X 1 переходим к другой нулевойпеременной X 2 - ведущим стал столбец 3, а в нем принадлежащаяк y2 строка 4–единственная,имеющаянеотрицательныйэлемент1,поэтомуонастановится ведущей. Это позволяет без нормализации пересчитать остальныестроки.

Нетрудно убедиться, что после расчетов из таблицы 3.9 формируетсяматрица II, представленная выше таблицей 3.5.Можнотакжепояснитьгеометрическийсмыслсделанныхпреобразований с помощью рис 3.1 – переход от данных таблицы 3.8 ктаблице 3.9 означает вначале движение от точки A в точку L(на линию 1), азатем - точку D.Рассмотренный способ пересчета при перехода из начала координат X iв новую опорную вершину можно теперь обобщить на случай произвольногочисла nпеременных X i в виде следующих общих правил перехода взаданную оптимальную вершину[29]:- в качестве ведущего столбца поочередно используются столбцы сискомыми ненулевыми переменными X i .78- в назначенном столбце анализируются только те элементы, которыепринадлежат строкам с нулевыми переменными y j (j= 1,…,n) в назначеннойвершине.- из всех строк ведущей является строка, имеющая главнымbнеотрицательный элемент, а отношение j a коэффициентов правом столбце кjэтому элементу минимально;- после выбора ведущей строки стоящая в левом столбце переменная ylзаменяется на переменную X i из ведущего столбца;- ведущая строка нормализуется, чтобы ее главный элемент сталравным1;- остальные строки матрицы пересчитываются известным в прямомсимплекс-методе способом;- во вновь найденной матрице находится новый ведущий столбец (i=2…….n) до тех пор, пока небудут учтены все переменные X i , и процедуравыявления новой ведущей строки и пересчета остальных срок повторяется.- число повторяющихся циклов пересчета равно числу искомыхненулевых переменных, в результате чего будет сформирована матрицаII.Приведенных вычислительных операций достаточно, чтобы целикомописать процесс решения обратной задачи в нужной последовательности,представленной ниже на рис.3.4 в виде блок-схемы обратного симплексметода.3.5 Общая процедура обратного симплекс-метода решения задачилинейного программированияБлок-схема состоит из четырех основных блоков.

Первый блокопределяет необходимые действия при условии, что неравенствам (3.5),определяющим содержание строк таблицы 3.1, соответствует выпуклый79многогранник, находящийся внутри n– мерного параллелепипеда, размерыкоторого будут уточнены ниже. Назначаемая ЛПР заданная вершина сизвестными координатами X i (0) принадлежит этому многограннику, длякоторой значение неизвестной целевой функции Z максимально.Относительно коэффициентов Ci линейной свертки критерия известно лишьто, что все они положительны. Тогда при заданных неравенствах (3.5) икоординатах X i (0) определяются нулевые переменные yl ; l  1....n , и с ихпомощью формируется исходная матрица I, поставив их в соответствующиеэлементы левого столбца и первой строки.Второй блок осуществляет перенос условий задачи из началакоординат взаданную оптимальную вершину с помощью последовательногопереборапеременных X i .В отличие от прямого симплекс-метода при переходе вближайшую соседнюю вершину, совокупность операций по выбору ведущихстолбца и строки и пересчету остальных строк в обратном симплекс-методевыполняется нужное число раз, вместо одного цикла в прямом методе.

Приэтомв каждом i - том цикле вычисления проводятся над преобразованнойматрицей II, полученной на предыдущем шаге. Сами циклы образуютсяпутемпоследовательногоиспользованиястолбцов,принадлежащихуказанным в верхней первой строке переменным X i . При этом необходимосделать следующее замечание – в ряде редких случаев часть координат X i(i  1....k ) оптимальной вершины может быть назначена нулевыми самим ЛПР.Например,если в примере.1 выбрана вершина F, то X1  0 , а для вершины RзначениеX 2  0 .

Поэтому эти переменные в циклах вычисления матрицы II неучаствуют, в связи с чем на рис 3.2 в блоке 3 специально отмечено, что80Рис.3.4 Блок-схема вычислительных операций обратного симплекс-методапри неизвестной целевой функции81i – это номер нулевой переменной, участвующей в расчетах, число цикловбудет равно (n-k), а k - число нулевых переменных в оптимальной вершине.Более подробно этот случай будет рассмотрен ниже примере 3.4.В третьем блоке задающими последовательный перебор являютсянулевые переменныев первом столбце.