Сызыктуу программалоонун маселелери - лк

Тема: Сызыктуу программалоонун маселелери

Сабактын максаты: Сызыктуу программалоонун жалпы жана канондук маселелерин билишет. Сызыктуу программалоонун маселелерин геометриялык сүрөттөшөт.

Каралуучу тапшырмалар:

1. Сызыктуу программалоонун жалпы маселеси

2. Сызыктуу программалоонун канондук маселеси

3. Сызыктуу программалоо маселелеринин геометриялык сүрөттөлүшү

Сызыктуу программалоонун жалпы маселеси

Сызыктуу программалоо - белгисиздерине сызыктуу чектөөлөр коюлган сызыктуу функциянын эң чоң жана эң кичине маанилерин изилдөөнүн жана табуунун методдору жөнүндөгү илим. Демек, сызыктуу рпограммалоо маселелери шарттуу экстремум маселелерине кирет, бирок аларга математикалык анализдин методдорун колдонууга ыңгайсыз, себеби сызыктуу функциянын экстремумдары чектөөлөр менне түзүлгөн областтын ички чектеринди эмес, областын чегинде жайланышат. Бирок, чек арадагы чекиттерди изилдөөгө мүмкүн эмес, себеби ал чекиттерде сызыктуу функциянын айрым туундулары турактуу. Ошондуктан сызыктуу программалоо маселелерин чыгаруу үчүн атайын методдор түзүлгөн.

Сызыктуу программалоонун жалпы маселеси төмөндөгүдөй коюлат:

сызыктуу функциясы жана

сызыктуу чектөөлөрдүн системасы берилген, мындагы берилген турактуу сандар.

(2) чектөөлөр системасын канааттандыруучу жана (1) сызыктуу функцияга минимум берүүчү өзгөрмөлөрүнүн терс эмес маанилерин табуу талап кылынат. (1) функция максат функциясы деп аталат.

(2) чектөөлөрдөгү барабарсыздыктарды барабардыктар түрүндө жазууга болот. Мисалы,

Барабарсыздыгынын сол жагына терс эмес кошумча өзгөрмөсүн кошуп,

барабардыгын алабыз. Эгерде чектөө

түрдөгү барабарсыздык болсо, анда кошумча өзгөрмөсүн кемитебиз:

Ошентип, сызыктуу программалоо маселесин

Түрдө жаза алабыз. (3) түрдөгү маселе сызыктуу программалоонун канондук маселеси деп аталат.

(3) чектөөлө системасынын он жактарын терс эмес деп эсептейбиз:

Эгерде алардын арасында терстери болсо, анда ал теңдемелерди -1 ге көбөйтүп коюуга болот.

(3) маселени вектордук формада жазууга болот:

мында

СХ - скалярдык көбөйтүндү.

(3) -(4) маселенин матрицалык формасы

түрдө жазылат, мында

Аныктама-1. (6) шарттарды канааттандыруучу вектору сызыктуу программалоонун мүмкүн болуучу чыгарылышы же планы деп аталат.

Аныктама-2. Эгерде (5) формуладагы векторлору сызыктуу көз каранды эмес болсо, анда вектору таяныч планы деп аталат.

векторлору өлчөмдүү болгондуктан, анын оң компоненталарынын саны ден ашпайт

Аныктама-3. Эгерде таяныч планын оң компоненталарынын саны туура болсо, анда ал план кубулба эмес деп аталат.

Аныктам-4. Максат функциясына эң кичине (эң чоң) маани берүүчу план сызыктуу программалоонун оптималдык план же оптималдык чыгарылышы деп аталат.

Мындан ары максат функциясын минималдоо маселелерин карайбыз. Эгерде максат функциясын максималдоо керек болсо, анда анын белгисин карама-каршыга өзгөртүп, жаңы фнукциянын минимумун табуу жетиштүү.

Сызыктуу программалоонун эң негизги методдорунун бири болуп симплек-метод эсептелет.

Сызыктуу программалоонун канондук маселеси

максат функциясын максималдоо функциясынын минималдоо маселесине тең күчтө болгондуктан, биз мындан ары минималдоо маселелрин карайбыз.

Симплекс-методдун эң жөнөкөй версиясы сызыктуу программалоонун канондук деп аталуучу

маселесин чыгарууга ылайыкталган. Мында - максат функциясынын коэффициенттеринин вектору; өлчөмдүү тик бурчтуу матрица, ал чектөөлөрдүн коэффициентеринин матрицасы деп аталат; чектөөлөрдүн вектору; - өзгөрмөлөрдүн вектору.

Кеңири түрдө канондук маселе төмөндөгүдөй жазылат:

Сызыктуу программалоонун ар кандай маселесин канондук түргө келтирүүгө болот. Мисалы, барабарсыздык түрдөгү

чектөөнү терс эмес кошумча өзгөрмөсүн киргизип,

түрдө жазууга болот. Эгерде баштапкы барабарсыздык түрдөгү чектөөнүн сол жагы оң жагынан чоң же барабар болсо, анда ага тиешелүү барабардык түрдөгү (3) чектөөдөгү кошумча өзгөрмөнүн белгисин карама-каршыга өзгөртүү керек.

Эгерде өзгөрмөсүнө терс эместик шарты коюлбаган болсо, аны терс эмес жана өзгормөлөрүнүн айырмасына алмаштырууга болот:

Канондук маселени төмөндөгүдөй да коюуга болот:

Сызыктуу теңдемелер системасынын терс эмес чыгарылыштарынын арасынан максат функциясына минималдык маани берүүчү чыгарылышты тандап алуу керек. Эгерде (4) системасынын чыгарылышы жок болсо, б.а. биргелеш эмес болсо, же терс эмес чыгарылыштары жок болсо, анда (2) канондук маселенин да чыгарылышы жок. Эгерде (4) системанын жалгыз гана терс эмес чыгарылышы болсо, анда ла оптималдык чыгарылыш болот. (4) системанын терс эмес чыгарылыштарынын саны бирден көп болгондо гана (2) маселени оптималдоо жөнүндо сөз болушу мүмкүн.

Сызыктуу программалоо маселелеринин геометриялык сүрөттөлүшү

Сызыктуу программалоонун жалпы маселесинде максат функциясы деп аталуучу

сызыктуу функциясынын экстремумун (минимум жана максимумун) табуу талап кылынат, мындагы өзгөрмөлөрү төмөнкү сызыктуу барабарсыздыктар жана барабардыктар түрүндөгү чектөөлөргө баш ийүүгө тийиш:

Айрым учурларда чектөөлөр жалаң барабардыктар түрүндө болгондо), же жалаң барабарсыздыктар түрүндө болгондо) болушу мүмкүн. Көп учурларда өзгөрмөлөр шарттарын канааттандырышат. Сызыктуу программалоо маселелеринде чектөөлөр сөзсүз болууга тийиш, себеби чектөөлөр жок болгон учурда (1) функция минимумга да максимумга да ээ болбойт.

Мисалы.

маселесинде эки өзгөрмө, барабарсыздык түрдөгү эки чектөө жана өзгөрмөлөрдүн терс эместик шарттары бар. Маселенин чектөөлөрү жалпак төрт бурчтукту аныктайт (1-сүрөт).

1-сүрөт

Минималдануучу максат функциянын деңгээл сызыктары, б.а.

барабардыгынын канааттандыруучу чекиттердин көптүгү градиент-векторго перпендикуляр түз сызыктардын түркүмүн түзүшөт. 1-сүрөттө жана маанилерине ылайык келүүчүэки деңгээл сызыгы көрсөтүлгөн. Биз максат функциясынын төрт бурчтуктагы минималдык маанисин табышыбыз керек. Мындай маани деңгээл сызыгы менен төрт бурчтуктун кесилишиндеги с градиентинин кемүү багыты боюнча эң четки чекити болууга тийиш. Бул маани түз сызыгында жатат. Демек, максат функциясынын минималдык мааниси -1 ге барабар жана ал аталган түз сызыктын төрт бурчтукка тиешелүү бөлүгүндо алынат. Минимум чекиттеринин арасында төрт бурчтуктун эки чокусу бар экендигин белгилей кетели.

Жогоруда келтирилген миалда сызыктуу чектөөлөр жалпак төрт бурчтукту туюндурат.

2-сүрөт 3-сүрөт

Эки өзгөрмөлүу маселелердин мүмкүн болуучу чыгарылыштарынын көптүгү 2-сүрөттө көрсөтүлгөндөй, куру көптүк (а), же чектелбеген көптүк (б,в), же бир да чокусу жок фигура (в) болушу мүмкүн. Мүмкүн болуучу чыгарылыштардын көптүгү чектелген жалпак көп бурчтук болгон учурда максат функциянын минимум чекиттеринин арасында бул көп бүрчтуктун эң жок дегенде бир чокусунун сөзсүз болушу геометриялык сүрөттөлүшүнөн келип чыгат (3-сүрөт).

Текшерүүчү суроолор:

1. Сызыктуу программалоо эмне жөнүндөгү илим?

2. Максат функция деген эмне?

3. Канондук маселе деген эмне?

4. Сызыктуу программалоонун мүмкүн болуучу чыгарылышы же планы деп эмнени айтабыз?

5. Таяныч жана кубулма пландар деген эмне?

6. Сызыктуу программалоонун оптималдык планы?

7. Сызыктуу программалоо маселелеринин геометриялык сүрөттөлүшүн түшүндүр?

2