Модели, методи и алгоритми на нелинейното програмиране
Изтегляне 268.41 Kb.
|
По такъв начин началната сепарабелна задача може да бъде апроксимирана с линеен модел и решена с използуване на симплекс-метода при допьлнителните условия за ограничен базис. Задачата е сле-дната:
Да се максимизира (минимизира) при ограниченията: 
условията за ограничен базис. Условията за ограничен базис определят, че за дадено i в базиса може да има най-много две положчтелни  и че ако две  са положителнй, те трябва да са съседни. Това означава, че променли-вата, която е избрана за включване според условието за оптималност на симплекс-метода, ще бъде действително въведена в базиса само ако удовлетворява двете условия за ограничен базис. Иначе за включване се разглежда следващата променлива, която най-добре удовлетворява условието за оптималност. Процедурата се повтаря, докато се намери променлива която да се включи в базиса, или докато се установи невъзможността на такова включване. Последната симплекс-таблица определя приблизителното оптимално решение на задачата.
Когато сепарабелната задача е неизпъкнала, с разгледания метод може да бъде определен локален екстремум. В такива случаи за нами-рането на глобалния екстремум може да бъде използувано СЦП, като началната задача се апроксимира по следния начин: Да се максимизира (минимизира)
х1 < 21/3, което позволява да се определят стойностите за х1k, f1(х1k) и g11(х1k), показани в таблица 10.2. Оттук 
В тази задача на СЦП променливите са  и yik. Когато точност-та на апроксимацията е висока, броят на точките на прекъсване и на определяните от тях ограничения в задачата на СЦП е голям, което може да направи практически невъзможно решаването на тази задача.
Вследствие на използуваната апроксимация и по двата метода, по-някога е възможно получаването на приблизителни оптимални решения, конто не съществуват при началната задача. Такива решения би трябвало да бъдат допълнително анализирани. Пример 10.3. Разглежда се задачата Да се максимизира J = х15 + 2х2 при ограниченията 3х12 + 4х2 < 16 x 1 , x 2 > 0. Лесно може да се види, че точното оптимално решение е х1* = 2,3094, х2 = 0 и J* = 65,6896. За да се реши задачата по метода на ограничения базис, се въвеждат следните функции:
Функциите f2(x2) и g12(х2) са линейни и се оставят без изменение, което позволява х2 да се разглежда като една от променливите. Нека броят на точките на прекъсване по х1 е L1 = 4. От ограничението следва, че и апроксимиращата задача е Да се максимизира при
ограниченията 
условията за ограничен базис В случая получаването на начално допустимо решение е облекче-но, тъй като  не участвува в целевата функция J и не е необходимо
да се въвежда изкуствена променлива. Началната симплекс-таблица е следната 
където S1 > 0 е остатъчна променлива. В съответствие с условията за оптималност . би трябвало да бъде включвана променлива. При това, за да се удовлетвори условието за ограничен базис, с което в базиса ще фигурират две несъседни положителни променливи  
Тук въвеждана променлива е 
Включвани променливи биха могли да бъдат   не е съседна на , въвеждането й в базиса не е допустимо.
В  и в базиса биха останали конто не са съседни. Последната
т 
Това решение е твърде близко до истинското оптимално решение х*1 = 2,3094, х*2 = 0 и J* = 65,6896, което се дължи на сполучливия избор на точките на прекъсване x1k. Когато сепарабелната задача е изпъкнала, (изпъкнали ограничения и вдлъбната или изпъкнала целева функция) апроксимацията може да бъде опростена и не е необходимо използуването на ограничен базис. Нека функцията /,(xt) e вдлъбната, с Li + 1 точки на прекъсване xik, k = 0,Li. Нека uik определя нарастването на променливата xi в интервала (xik-1,xik), к = l,Li, a Sik - стръмността на линейния сегмент н 
при условие, че 0 < uik < xik - xik-1, к = 1,Li.
се включва иi2 и т.н. По същия начин се апроксимират и ограниченията
след което апроксимиращата з където
Апроксимиращата задача в случая на минимизация на изпъкнала функция се получава по същия начин, като се отчита, че Si1 < Si2 < ... < SiLi.
Да се максимизира (минимизира) J = СХ + XTDX при ограниченията
В квадратичната форма XTDX D е симетрична матрица, положително (отрицателно) определена в задачите за минимизация (максимизация) Следователно J е строго изпъкнала (вдлъбната) спрямо X при минимизация (максимизация). Пространство^ на решенията е изпъкнало поради линейността на ограниченията. Тази задача се решава чрез прякото прилагане на условията на Каруш-Кун-Такер. Тези условия са и достатъчни за идентифициране на глобален екстремум поради изпъкналостта на J и на допустимата област. В случая на максимизация моделът може да се запише във форма- та.
За двете множества ограничения АХ — b < 0 и -X < 0 се въве-ждат съответно множителите на Лагранж и условията на Каруш-Кун-Такер се представят във вида 
Тъй като
след въвеждане на допълнителните променливи S в ограниченията АХ + S = b, S > 0, необходимите условия се записват във формата 
След транспониране на първото векторно-матрично уравнение 
и необходимите условия се представят по-компактно във вида 
Вижда се, че задачата е еквивалентна на решаването на система
строгата вдлъбнатост на J и изпъкналостта на g(X) следва, че допусти-мото решение, удовлетворяващо необходимите условия, е оптималното решение и че решението на системата е единствено. Системата може да бъде решена с използуването на първата фаза на двуфазния метод с изкуствени променливи за определянето на допустимо начално решение на линейни задачи (т.3.4.2), като се осигури винаги изпълнението на условието о стойност, si не бива да става базисна, с положителна стойност на същата итерация. Същото се отнася и за променливит и хj.Това е идеята за ограничен базис. Ако квадратичната задача има допустимо решение, сумата на изкуствените променливи се нулира в резултат на изпълнението на първата фаза на метода. П Задачата се записва в матрична форма Да се максимизира при ограниченията 
Матрицата D е отрицателно определена, т.е. J e строго вдлъбната по X. Необходимите и достатъчни условия се представят във вида 
След въвеждане на изкуствените променливи R1 и R2 за първи-те две уравнения по-горе и на минимизираната целева функция R = R1 + R2 началната таблица за фаза 1 е следната 
Тъй като R се минимизира, въвеждана променлива би трябвало да бъде х1 (или х2). Тази променлива наистина може да бъде включена в базиса, защото  (или ) е небазисна и допълнителното условие  се изпълнява. Извеждана променлива е R1и сим-плекс-таблицата на първата итерация е
Въвеждането на x2 в базиса е възможно, тъй като = 0. Изве-ждана променлива е s1. Таблицата на втората итерация е  
Въвеждането на  на третата итерация в базиса е възможно, тъй
к 
Тъй като R — 0, полученото решение е допустимо и то е х*1 = 0, х*2 = 1, J* = 6.
където
Обикновено cj,aij са физически константи, а xj са променливи, конто се избират в процеса на проектиране. Върху знака на аij не се налагат ограничения, но се предполага, че всички cj > 0. Така дефинираните Pj (X) и f(X) са обобщени полиномы, в които може да има отрицателни степени aij, и които се наричат позиноми. Задачите, в които целевата функция и ограниченията са позиноми, се определят като задачи на геометричното програмиране (позино-миалното програмиране). В общия случай това са неизпькнали задачи, но в случайте, когато сj > 0 те могат да бъдат преобразувани в еквива-лентни задачи на изпъкналото програмиране. През 1964 г. Дюфин и Ценер предлагат метод на решение, конто се основава на съответна дуална задача. Предимството е, че дуалната задача се решава значително по-лесно от пряката, записана в позино-миална форма. Методът ще бъде въведен за случая без ограничения. Пряката задача е да се минимизира функцията f(X), представена като позином. Предполага се, че всички променливи са строго положителни, xi > 0. Необходимото условие за минимум се записва във вида 
или понеже xk > 0 
Тъй като J е позином и всички оптимални стойности х*к > 0, минималната стойност J* > 0. Въвеждат се 
Очевидно, уj> 0 и Стойността уj представлява относителния принос на Pj в оптималната стойност J*.
Така записани те се наричат условия за ортогоналност и нормалност. Те определят единствено решение за променливите уj, ако п + 1 = N и всички уравнения са независими, или неединствено решение, когато п + 1 < N. В последния случай обаче може да се определят единствени стойности yj, при конто се минимизира J, като се формулира допълни-телна оптимизационна задача спрямо N - (n + 1) променливи уj. Нека y*j,j = 1,N e единственото решение, определено от необхо-димите условия. То се използува за определяне на J* и х*к по следния начин.
където е отчетено условието за ортогоналност. Вижда се, че стойности-те у*j определят J*. От дефиницията пък на уj, при известии стойности у*j и J*, се намират Р*j = y*j,J*,j = 1, N. Стойностите Р*j се използуват за съставяне на нелинейната система уравнения  
чието решение определя оптималните х*k. По такъв начин решението на началната задача в позиномиална форма е преобразувано в решаване на система линейни уравнения спрямо променливите уi. Тъй като всички у*j са определени от необходимите условия за минимум, решенията х*к удовлетворяват всички уравнения на нелинейната система и могат да бъдат определени след отстраняване на N — п уравнения от нея, които са излишни. Доказано е, че необходимите условия са и достатъчни за иденти-фициране на минимум. Елементите на дуалната задача могат да се разкрият, като се използува следното неравенство на Коши за bi > 0  
където аi > 0 и . Пряката задача се записва във вида 
се дефинира функцията случая yj > 0,  и от неравенството на Коши следва, че
W < J.
 
Пример 10.5. Разглежда се задачата Да се минимизира J = 5х1х2-1х32 + х32х3-1 + 10х23 + 2х1-1х2х3-3 x 1 , x 2 , x 3 > 0. Целевата функция се представя във вида J = 5х1х2-1х32 + х1-2х20х3-1 + 10х10х23х30 + 2х1-1х21х3-3 Вижда се, че N = 4,n = 3, т.е., N = п + 1 и условията за ортого-налност и нормалност водят до единствено решение за уj. Тези условия се записват в матрична форма Каталог: lib lib -> Преводач Елена Атанасова Коректор Ива Данева Формат 84/108/32 Печатни коли 15 дф „абагар" Велико Търново ик „сова" Варна как да се използва тази книга lib -> За медитацията ошо въведение lib -> Поредица ние обичаме животните lib -> Тайната на скорпион lib -> Разчупване на оковите Победа над: Отрицателните мисли lib -> Въведение Изтегляне 268.41 Kb. Сподели с приятели:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||
би тряб - вало да бъде изключвана променлива. От условието за допустимост обаче
ледва, че изключвана променлива в този случай би била S1, при
Следователно
не може да бъде включвана променлива. Следващата най-подходяща за включване е променливата 
Тогава изключвана променлива е с което условието за ограничен базис се удовлетворява. Съответната симплекс-таблица е
и тъй като в базиса фигурира 
, включването на съседната 
в базиса е допустимо. Изключвана променлива е St, при което се получава таблицата
. Тъй като
ключването на 
аблица определя приблизителното оптимално решение, което е
ад този интервал. Тогава fi(хi) се апроксимира по следния начин
адача е 
Практически това
значава, че ако на някоя итерация е базисна променлива с положи-телна
ример 10.4. Да 
ато s1 = 0. Таблицата е _____________________________________________
