Силаева Т.А. - Методы решения задач оптимального проектирования ВС (Методы решения задач оптимального проектирования ВС (Силаева Т.А.)), страница 9

3.4. 3. Наиболее нлн/и наименее удаленная от/(Х)= со грань влв грани многогранника (при я= 2 сторона илн стороны многоугольника) области ХР параллельна поверхности (линии) постоянного уровня функцин /(Х) = со. Тогда решением ЗЛП будет все множество точек, лежащих на этих гранях много- гранника (сторонах многоугольника). Прк этом минимум достигается в точках с наименьшим в ХВ зяачевием функции У(Х), а максимум — с нанбольшим.

На рис. 3.5 представлены примеры таких областей и решений ЗЛП при л= 2. В случае области Хс), изображенной па рис. 3.5, з, минимум достигается на множестве решений, являющихся точками отрезка АВ, а максимум — отрезка СВ. Отрезки АВ к С() параллельны ливням постоянного уровня функции У(Х) = со и )1(Х) = сс. Для области ХЭ~, показанной ка ркс. 3,5, б, минимум при решении ЗЛП достигается в точке Х', а максимум — на множестве точек отрезка СВ. В случае области Ф ХЮ2 на рис, 3.5, в максимум достигается в точке Х, а минимум — на множестве точек отрезка АВ. а) Рис.

3.5 4. Наиболее и наименее удаленные от Г(Х) = со грани многогранника (при л= 2 стороны многоугольника) ограниченной области ХР не' параллельны поверхностям (линиям) постоянного уровня функции Г(Х) . Тогда ЗЛП имеет единственные минимум и максимум в наиболее и наименее удаленных от Г(Х) = с о точках области ХР. На рис, 3.6, а,б,в приведены примеры при и= 2 таких областей ХВ3 (з виде четырехугольника) и Х04 (в виде отрезка прямой) к решений ЗЛП для трех различных целевых функций: У(Х) ° У~(Х) к У2(Х)- Ми нкмум достигается в Х1, а максимум — в Хз.

Ряс. 3.6 Графический метод решения ЗЛП Оп удобен для решения двумерных ЗЛП, но его невозможно применить к ЗЛП с размерностью а> 3. Тогда используют симплекс-метод, описываемый киже. Алгоритм решения ЗЛП графическим методом состоит в следующем. 1. Графически изображаем область ХЮ (как решение системы заданных ограничений) к линию постоянного уровня функции Г(Х) = с с с указанием стрелкой направления возрастания целевой функцив У(Х) .

2. Если Х — пустое множество (когда система неравенств, задаваемая ограничениями, несовместна), то решений ЗЛП иет в переходим к и. 5. 3. Находим наиболее я навмеяее удаленные от линии постоянного уровня функции у(Х) = со вершины Х0 кли/я параллельные этой линии стороны многоугольника (вли многоугольной области) ХВ, если они существуют. 4. Определяем оптимальные решения ЗЛП, которыми являются найденные в п.

3 вершины многоугольника (многоугольной области) ХВ и все множество точек сторон ХВ, выделенных в и. 3. При этом минимум достигается в точке (точках) с наименьшим в ХВ значением функции У(Х), а максимум— с наибольшим. 5, Конец алгоритма. 62 Симплекс-метод Данцига для решения ЗЛП частного вида Рассмотрим решение симплекс-методом ЗЛП в случае ограничений частного вида, когда имеется гп ограниченвй (3.2) со знаком неравенства «ь», сводимых к каноничесйой форме (3.4), т.е.

решается задача ех1г г(Х), Х где у'(Х) = с о+ ~~> с; х, прн ограничениях: у = а з — ~ а эх,-1 0 ((= 1,т~, ~=! х,> 0 (1= 1,я), а о> 0 ()= 1,т). Симплекс-метод позволвет за конечное число итераций найти оптимальное решение, так как на каждой его итерации осуществляется переход от одной вершины многогранника нли многоугольника ХР к другой (от одного базисного решения к другому) в направлении возрастания функции при повске ее максимума или убывания функции при минимуме, и итерации выполняются вплоть до нахождения вершины (двух вершин), соответствующей экстремуму, а чнсло вершин конечно.

Базисным решением называется такая совокупность значений л (1= 1,л ) и у, ()= 1,лз~, что я нз всех и+ т переменных равны нулю, а т переменных выражены через оставшиеся переменные в соответствии с лз соотношеннямв связи типа (3.4). л переменных, приравненных к нулю, называют небазисными. Остальные лз переменных образуют базис, и их называют базнснымв.

Если базисное решение допустимо, то оно называется базисным допустимым решением. Симплекс-метод основан иа следующих утверждениях линейного программирования: 1) если ограничения имеют допустимое решение, то опи имеют н базисное решение; 2) область ХР допустимых решений является выпуклым множеством; 3) базисные допустимыо решения соответствуют вершинам выпуклого множества ХР; 4) есле целевая функция имеет конечный экстремум, то по крайней мере одно оптимальное решеяие является допустимым базисным. Отсюда следует, что оптимальное регпение ЗЛП яеобходимо искать среди допустимых базисных решений, являющихся вершинами многогранника илн многогранной области (прв л= 2 многоугольника или многоугольной области) ХР.

Симплекс-метод основан на процедуре, называемой шагом модифицированного жорданова исключения с разрешающим элементом а, (выбор а„описан ниже в п. 3.2 алгоритма решения ЗЛП частного вида). Данная процедура означает переход от табл. 3.1 на текущей итерации й к табл. 3.2 на следующей итерации я+ 1. Таблица 8.1 ом ( итерац точь Х' Таблица 2.2 5) меняются местами х, 6) конец алгоритма. Алгоритм решения ЗЛП стоит в следующем.

и у„; Таблица 8.2 Строка г и столбец з, где находится разрешаюгций элемент а„, называются разрешающими строкой и столбцом соответственно. В базисном столбце находятся базисные переметные н целевая функция (капрнмер„в табл. 3.1 это у (,)= 1,т )и У'). В небазисных столбцах в первой строке таблицы ва каждогй итерации находятся небазисные переменные со знаком минус,(например, в табл.

3.1 на )«-й итерации небазисными переменныыи являются х,. ~( = 1, и ) ). Алгоритм перехода от табл. 3.1 к табл. 3.2 состоит в следующем: 1) все элементы разрешающего столбца з, кроме разрешакщего элемента, меняют знак на противоположный; ' 2) элементы разрешающей строки г делятся на а„; 3) элементы разрешающего столбца з делятся на и»«; 4) остальные элементы вычисляются по формуле: Ь .- а, ЪГг~ Г У У (ю= 1,т+ 1, (и г, )= О,л,,)х з); (35) и„ частного вида симплекс-методом со- 1. Ограничения у.= и .

+ ~Ч~' и ..(- х .~ 1= $ вую функцию У= со+,~, ~ — с;)~ — х;) записываем в виде табл. З.З на нулевой итерацив. За базисные переменные принимаем у. ()= 1,т), а за небазисные — х; ((= 1, и). В столбце свободных членов на нулевой итерации находятся свободные члены из ограничений и целевой функции. Если решается задача на максимум функции г(З(), то в по следней строке записываем выражение для «~=» на ин =», на минимум ,~'(Х) — для «- у'=».

2. Находим допустимое базисное решение. Так ак как все а о > О ~~)= 1,т ), то в качестве допустимого базисного решения примем следующее: все небазисные пе- ременныех табл. 3.3 равны нулю, а каящый у в базисыом столу бце равен свободному члену, находящемуся в )'-й строке, т.е. Отметим, что при этом все ограявчения х,.< О и у -> 0 вы- ноя няются. 3. Определяем оптимальное решение, для чего анализируем последнюю У-строку табл. 3.3.

3.1. Если все элементы этой строки з небазисных столбцах неотрицательные (т.е. — с > О, 1= 1, и пря поиске максимума )'(Х) и с,. ~ О, ! = 1, п пря минимуме !'(Х) ), то допустимое базисное решение, полученное в л'. 2, будет и оптимальным, и решение ЗЛП заканчивается (переходим и п.

4). 3.2. Если среди элементов )"-строки в небазисных столбцах есть по крайней мере одия отрицательный, то для его устранения осуществляем итерапию, заключающуюся в выполнении шага модифицированного жордаыова исключении с разрешающим элементом а . За разрешающая столбец з берем тот, в котором нахог» дится наибольший по модулю отрицательнь|й элемент у-строки в яебазисных столбцах. Для определения номера г разрешающей строки вычисляем а р отношение — для всех )= 1, т, при которых а х> О.

/« В качестве разрешающей выбираем ту строку г, для которой это отношение минимально: а,р ар — ш)п — а гг 1= 1,»» )« а > р Если в столбце з все а, > 0 (~ = 1, т ), то выбираем другой разрешающий столбец г, в котором находится наибольший ло модулю (средн оставшихся) отрицательный элемент у'-строки в небазисных столбцах. Если в любом выбранном столбце з все аз< 0 ()'= 1,т), то это является признаком неограниченности решения, т.е, не существует конечного решения данной ЗЛП.

В этом случае переходим к л, 4. 68 После выбора разрешающих столбца г и строки г проводим шаг модифицированного я«орланова исключения с разрешающвм элементом а „, помечаеиым в таблице символом «*». Данный шаг избавляет от отрицательного элемента в у-строке столбца з (- с, при поиске иакснмумау(Х) н с, при минимуме). Зги шаги повторяем до тех пор, пока все элементы з у-строке в небазисных столбцах ые станут неотрицательными. Тогда решение ЗЛП заканчиваем, и в качестве оптииальпого решения принимаем следующее: есе небазисные переменные (те х( н у, которые стоят в пебазясных столбцах в первой строке полученной таблицы па последней итерации) равны нулю, а все базисные переменные (все х; и у.