Квадраттық формалар

                      Мазмұны

Кіріспе

1. Квадраттық программалау
2. Квадратты программалау есебін Франк-Вольф әдісімен шығару
2. Квадраттық формалар

              2.1 Квадраттық формаларды канондық түрге келтіру

            2.2 Квадраттық форманың нормалдық түрі

Қорытынды

Қолданылған әдебиеттер тізімі

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Кіріспе

        Квадратты  программалау, квадратты тәуелділікпен  айнымалы арасында арнаулы сипаттайтын  математикалық программалаудың  облысы.

       Басқарудағы программалау ресурстарды бөлудi процесс сияқты көрсетуге болады.  Математикалық программалудың әдісінде негізделген әр түрлі квадраттық программалау әдістері қатары бар.

       Квадратты  программалаудың әдісінің қолданысы   бүгінгі уақытта көкейкесті, себебі  математикалық қалыптың игерушілігі  жоспарлау және компанияның қызметінің  анализын жетілдірудің маңызды  бағыты болып табылады. Математикалық  үлгi түрiндегi мәлiметтердiң берiлуi - мәлiметтi дәлдеп, нұсқаларды құрып, пiшiндеп, тиімді шешiмдi таңдауға мүмкiндiк бередi.

     Квадраттық программалауда мақсат функциясы квадратты және шектеулер сызықты теңдеулер немесе теңсіздіктер т.б. болады

       Сызықты  емес программалау есебінің жалпы  жағдайындағыдай, квадраттық программалау  есептерінің глобальді экстремумын  табудың тиімді әдісі жоқ, егер  кез келген локальді экстремум  бір уақытта глобальді экстремумы белгісіз болады. Берілген есебтің мүмкін болған шешімдерінің жиыны ойыс болса кез келген локальді максимум нүктесі глобальді максимум болады. Егер мақсаттық функция дөңес болса, онда кез келген локальді минимум глобальді нүкте болады. Егер де мақсаттық функция ойыс (дөңес) болса, онда мақсаттық функцияның максимумын (минимумын) табу мәселесі оңай шешіледі. Квадраттық форманың ойыс немесе дөңес болуы оның теріс анықталған, жартылай теріс анықталған, оң анықталған, оң жартылай анықталған немес мүлдем анықталмағандықтарынан келіп шығады.

Сызықтық түрлендірудің  көмегімен квадраттық форманы айнымалының  квадраттарынан ғана құралған канондық түрге келтіруге болады.

       

 

 

1.2 Квадраттық  программалу есебі

Квадраттық форма берілсін:

    

Немесе векторлық-математикалық  түрде

Және сызықтық теңсіздік 

       ,                

векторлық - матрицалық формаларда осылай жазып аламыз:

(4) теңсіздігі қандайда  бір ішкі нүктелері бар Ω облысын анықтасын.

 дөңес функция болғандықтан, матрицасы оң нақтылы және симметриялы деп аламыз

Квадратты программалау есебі  былай құрастырылады:

(1 ) функциясы үшін минимумы (2) функциясының шектеулеріне жететiн  нүктенi iздеп табу:

Бұл квадратты программалау есебі сызықты шектеулер мен  сызықты емес программалаудың квадратты  мақсат функциясы болып табылады. Және төмендегiше құрастыра алады:

        болғандағы

функциясын анықтау 

Бұл жерде  - -бір қалыпты вектор, -симметриялы матрица , - -бір қалыпты вектор және - матрица .

 

Сызықты программалау есебіне  қарағанда квадраттық программалау есебі жеңіл, ал сызықты емес программалу  есебіне қарағанда аздап күрделі.

Келесі мысалды қарастырайық:

Мысалы.

Франк-Больф әдісі.

 

Баранкин-Дорфман әдісінің әрі қарай дамуына Франк және Вольфтың еңбектерінің нәтжесі әсер етті. Олар ұсынған алгоритм әмбебап  болды.

Айталық бізге квадраттыз программалау есебі берілсін:

 шектелуіндегі

                                             (2.54)

мәнін табу керек.

Мұндағы - теріс анықталған (жартылай анықталған) форма. Осы есеп үшін Кун-Таккер шартын жазамыз:

 

                                        (2.55)

.                                                         (2.56)

Франк-Вольф алгоритмін (2.55) шартын қанағаттандыратын кейбір мүмкін болған базистік шешімдер белгілі болған жағдайда қолдануға болады.

                                      (2.57)

функциясы айтылған базистік шешімге сәйкес келеді. Сонымен қатар  мәні ; ; ; айнымалыларына сәйкес келеді. Базиске кірмейтін айнымалылар үшін оған сәйкес -дер нөлге тең болады. Егер болса, онда базистік шешім тиімді шешім болады. Егер болса, онда -ның минимизациясын келесі тәртіппен орындаймыз: -шы қадамның нәтижесінде (2.55) шартымен қатар оған сәйкес келетін симплексті кестені қанағаттандыратын мүмкін болған базистік шешімін, сондай-ақ (2.55) шартын қанағаттандыратын, функциясының оң мәндеріне сәйкес келетін (бірінші этапта деп есептейміз) шешімін (базистік болуы шарт емес) аламыз. базистік шешімін пайдаланып, симплекстік әдіспен (2.55) шектелуінде -ға қатысты сызықты болатын формасын минималдаймыз. , және , векторларын келесі түрде береміз: , , , . Минимизациялау процесінің нәтижесінде базистік шешімдер тізбегін аламыз, мұндағы . Бұл тізбекті кейбір базистік шешімдер үшін келесі шарттардың бірі орындалғанша жалғастыра береміз:

 

, яғни                                     (2.58а)

                                        (2.58б)

Бірінші жағдайда есептің толық шешімі болады. Екінші жағдайда деп есептейміз, онда

 

,                                       (2.59)

мұндағы

                      (2.60)

 

Бұл жерде  нүктесі функциясының мәні минималды болатындай және арасындағы түзу кесінді нүктесі.

 базистік шешімін есепке  ала отырып, функциясын нүктесінде линеарлаймыз, және алынған сызықтық форманы симплекс әдісімен тағыда минималдаймыз. Франк және Вольф әрбір этапта (2.58а) немесе (2.58б) жағдайларының тек екеуі ғана орындалатынын, және этаптың ақырлы сандары арқылы (2.58а) жағдайы міндетті түрде орындалатынын көрсетті.

Егер (2.55) жүйесінің мүмкін болған шешімі табылған болса, онда (2.54) есебінің шектеулі тиімді шешімі болатынын  да атап өтуге болады. Егер (2.55) үшін мүмкін болған шешімді табу мүмкін болмаса, ал жүйесі (2.55)-ті қанағаттандырмайтын мүмкін шешімге ие болса, онда есеп шектеулі шешімге ие болмайды.

2.8-суретте Франк-Вольф  әдісінің ерекшеліктерінің графикалық  иллюстрациясы көрсетілген.  көпбұрышы мүмкін болған облыс болып табылады. Бастапқы нүкте болсын деп есептейік. функциясын нүктесінде линеарлаймыз және алынған функцияны минималдаймыз. Сондай-ақ . Түрлендіруді орындау арқылы (2.58б) шарты орындалатын нүктесіне өтеміз. Одан кейін түзуінде жататын, минималды болатын нүктені таңдаймыз. Бұл нүктесі, сәйкесінше . функциясын нүктесінде линеарлау арқылы және түрлендірудің екі қадамын жасау арқылы нүктесіне, содан кейін сәйкесінше нүктесіне өтеміз. нүктесінде тағыда (2.58б)-да қарастырылған жағдай орын алады. кесіндісінде функциясы минимал мәнді нүктесінде қабылдайды, сондықтан . Келесі этапта (2.58а) шарты орындалатын, есептің шешімін беретін нүктесіне өтеміз. Суретте сондай-ақ бір төбеден екінші төбеге өту кезіндегі сызықты функциялардың өзгеруі көрсетілген.

Франк-Вольф әдісінің келесі есепте қолданылуын көрейік:

 функциясының

 

 

 

шектелуіндегі ең үлкен мәнін  табу керек.

Кун-Такке шартын жазамыз:

 

 

.

 

Берілген шектеулер жүйесінің  келесі түрдегі базистік шешімдерін аламыз:

 

 

 

 

Айнымалылар	1
	90	-23	-6	9	-27

2.17-кесте

 

Сәйкесінше  . Есептің шешімін коэффиценттерінің мәні жазылатын 2.17 түрдегі симплексті кесте арқылы өрнектейміз.

Симплексті кестедегі  соңғы қатардың элементтері келесі формуламен есептелінген

 

.

 

Сондай-ақ егер айнымалы базиске  кірмесе, онда . айнымалысын базиске қосамыз, және айнымалысын базистен алып тастаймыз (шешуші элементті таңдау ережесі дәл Баранкин-Дорфман әдісіндегі сияқты).

Симплекті кесте келесі ережелер бойынша түрлендіріледі:

1) базиске қосылған және  қосылмаған айнымалылардың орнын  ауыстыруға болады;

2) шешуші элементтің орнына  оған кері санды қоюға болады;

3) бағыттаушы баған элементтері  шешуші элементті бөледі.

4) бағыттаушы қатар элементтері  шешуші элементті бөледі және  нәтижесінде оған қарама-қарсы  таңба алынады;

5) қалған элементтері  жоғарыда қарастырылған алгоритмдегідей  жолмен алынады.

 

 

Айнымалылар	1
	387/7	4	-177/7	-18/7	27/7

2.18-кесте

 

Айнымалылар	1
	30	-209/8	177/8	15/4	-45/8

2.19-кесте

Түрлендіру жасау арқылы 2.18-кестені аламыз.

 және  болады, онда есептің шешімін жалғастырамыз. айнымалысын базистен алып тастап және айнымалысын базиске қосу арқылы 2.19-кестені аламыз.

 және сонымен қатар  болса, онда 2) жағдай орын алады. Сондықтан табамыз.

-ді анықтау үшін (2.60) өрнегін  пайдаланамыз.

Келесіні аламыз:

 

 

 

 

 

.

 

Айнымалылар	1
	40	-53/4	7/2	-1/4	-11/4

2.20-кесте.

 

Сондықтан функциясы кесіндісінің нүктесінде ең кіші мәнге ие болады. Функцияны нүктесінде линеарлаймыз. Нәтижесі 2.20-кестеде көрсетілген.