2-мавзу. Чизиқли дастурлаш режа

2-мавзу. ЧИЗИҚЛИ ДАСТУРЛАШ


Режа:

1. 
   Чизиқли дастурлаш (ЧД) масаласининг қўйилиши ва унинг турли формаларда ифодаланиши. Асосий тушунчалар.
   
2. 
   Чизиқли дастурлаш масаласининг геометрик талқини ва уни график усулда ечиш.
   
3. 
   Чизиқли дастурлаш масаласини ечишнинг симплекс усули.
   
4. 
   Сунъий базис усули.
   
5. 
   Аралаш шартли масалалар.
   

1. Маълумки, чизиқли дастурлаш математик дастурлашнинг таркибий қисми бўлиб ҳисобланади. Чизиқли дастурлаш масаласини умумий ҳолда қараймиз.

(1)
чизиқли функция ва
(2)
(3)
чизиқли чеклаш шартлари системаси берилган бўлсин, бунда ва лар берилган ўзгармас миқдорлар.
Чизиқли дастурлаш масаласи, бу ўзгарувчиларнинг шундай қийматларини топиш керакки, улар (2), (3) чеклаш системасини қаноатлантириб, (1) чизиқли функция минимум (максимум) қийматга эга бўлсин.
Чизиқли дастурлаш масаласининг умумий қўйилишини бир неча формаларда (шаклларда) ёзиш мумкин.

1. 
   Векторлар шаклида ёзилиши. Ушбу белгилашларни киритамиз:
   

бўлиб, скаляр кўпайтма бўлсин. Бу ҳолда чизиқли дастурлаш масаласини вектор кўринишда қуйидагича ифодалаш мумкин:

чизиқли функция минимумга эга бўладиган Х векторнинг
(4)
шартларни қаноатлантирувчи қийматини топинг.
2. Матрица шаклида ёзилиши.
шартларни қаноатлантирувчи чизиқли функция минимум қийматга эга бўладиган векторнинг қийматини топинг, бунда сатр матрица, устун матрица ва система матрицаси ҳамда устун матрица бўлади.
3. Йиғинди белгиси орқали ёзилиши.

шартларни қаноатлантирувчи чизиқли функция минимумга эга бўладиган ўзгарувчиларнинг қийматини топинг.
1-таъриф. (2) ва (3) шартларни қаноатлантирувчи векторга чизиқли дастурлаш масаласининг мумкин бўлган ечими ёки қисқача режаси (плани) дейилади.
2-таъриф. (4) ёйилмага кирувчи ларнинг мусбат ҳадли векторлари чизиқли боғланмаган бўлса, режага таянч режа (ечим) дейилади.
векторлар ўлчовли бўлганлиги учун таянч режа таърифидан кўринадики, унинг мусбат ҳадли коэффициентлари m дан катта бўлмайди.
3-таъриф. Таянч режа (ечим) та мусбат компонентларга эга бўлса, унга махсусмас, акс ҳолда махсус режа дейилади.
4-таъриф. Чизиқли функция минимум (максимум) қийматга эга бўладиган режа (ечим)га чизиқли дастурлаш масаласининг оптимал режаси (ечими) дейилади.
Чизиқли дастурлаш масаласи ечимининг айрим хоссаларини қараймиз:
1) чизиқли дастурлаш масаласи чеклаш шартлари системасининг режалари (мумкин бўлган ечимлари) тўплами бўш тўпламни ёки Rⁿ фазонинг қавариқ тўпламини ташкил этади;
2) чизиқли дастурлаш масаласининг режалари тўплами бўш тўплам бўлмаса ва мақсадли функция бу тўпламда юқоридан (қуйидан) чегараланган бўлса, масала максимум (минимум) оптимал ечимга эга бўлади;
3) чизиқли дастурлаш масаласининг оптимал ечими мавжуд бўлса, бу ечим мумкин бўлган ечимлар тўпламининг чегаравий нуқталарида бўлади.

2. Чизиқли дастурлаш масаласининг геометрик талқинини (тасвирини) , айрим ҳолларда бўлганда ифодалаш мумкин. Чизиқли дастурлаш масаласи қуйидагича берилган бўлсин:

тенгсизликлар системасини қаноатлантирувчи ва ўзгарувчиларнинг шундай қийматини топиш керакки, функция максимум қийматга эга бўлсин.
Ечиш. 1) тенгсизлик билан аниқланадиган геометрик тасвирни аниқлаймиз. Бунинг учун олдин тўғри чизиқни координат текислигида ясаймиз. Маълумки, тўғри чизиқ ва нуқталардан ўтади.
Энди тенгсизликка мос геометрик тасвирни аниқлаш учун, берилган тенгсизликка координатлар боши нуқтанинг координаталарини қўямиз: ёки тенгсизлик бажарилади, шунинг учун тенгсизлик билан аниқланадиган геометрик тасвир координатлар боши, нуқтани ўз ичига олган ярим текисликдан иборат бўлади.
2) Худди юқоридагидек колган тенгсизликларга мос келган ярим текисликларни ясаймиз. , бу тўғри чизиқ нуқталардан ўтади. тенгсизлик бажарилади.

1-чизма
3) тўғри чизиқ нуқталардан ўтади.

бўлади.
4) ярим текисликларни ҳам ясаймиз:
Шундай қилиб, берилган тенгсизликлар системасини қаноатлантирадиган мумкин бўлган ечимлар тўплами - ечимлар кўпбурчагини ҳосил қилдик. Маълумки, бу тўплам қавариқ тўпламдан иборат, яъни биринчи хосса бажарилади (1-чизма).
Эндиги масала бу тўпламнинг шундай нуқтасини топиш керакки, чизиқли функция қийматга эга бўлсин. Текисликда F бир хил қийматлар қабул қиладиган нуқталарнинг жойланишини топамиз. Бунинг учун деб оламиз. Бу ҳолда тенглама ҳосил бўлиб, бу функция бир хил қиймат қабул қиладиган тўғри чизиқдир. нинг ўрнига ҳар хил қийматлар қўйиш билан параллел тўғри чизиқларни ҳосил қиламиз. Бу тўғри чизиқларнинг ҳар бирига сатҳ чизиғи (яъни функция бир хил қийматлар қабул қилувчи тўғри чизиқ) дейилади.
Чизиқли функция коэффициентларидан тузилган векторни қараймиз. Бу векторга перпендикуляр чизиқни ўтказамиз (бу сатҳ чизиқлардан бири) ва уни ўзига параллел мумкин бўлган ечимлар тўплами билан кесишмай қолгунча силжитамиз. Бу ерда, масалада максимал қиймат топилиши керак бўлса, векторнинг йўналиши бўйича, минимал қиймат топилиши керак бўлса, векторнинг йўналишига қарама-қарши томонга силжитилади.
тўғри чизиқни ўзига-ўзини параллел қанчалик силжитилмасин, бари бир мумкин бўлган ечимлар тўпламини кесиб ўтаверса, чизиқли функция юқоридан (минимал қийматлар учун қуйидан) чегараланмаган бўлади ва оптимал ечимга эга бўлмайди. Қаралаётган масалада чизиқни параллел силжитилганда мумкин бўлган ечимлар тўплами билан Д нуқтада охирги умумий нуқтада эга бўлиб, бу нуқтада функция максимал қийматга эга бўлади. Маълумки, бу нуқта , тўғри чизиқларнинг кесишган нуқтаси бўлиб, уларни биргаликда ечиб нуқтанинг координаталарини аниқлаймиз:

.
Шундай қилиб, Д нуқтанинг координаталари масала ечими бўлади.
.
Бу билан чизиқли дастурлаш масаласининг 3-хоссанинг ҳам бажарилишини кўрсатдик.

3. Чизиқли дастурлаш масаласини ечишнинг симплекс усули. Пайқаш мумкинки, ечимлар кўпбурчагининг шундай бурчак нуқтаси мавжудки, бу нуқтада чизиқли функция оптимал қийматга эга бўлади. Ечимлар кўпбурчагининг ҳар бир бурчак нуқтасига бирорта таянч ечим мос келади. Таянч ечим та чизиқли боғланмаган векторлар системаси орқали аниқланиб, бу системада та векторлар қатнашади. Оптимал ечимни топиш учун фақат таянч ечимлар текширилади. Бундай масалада таянч ечимлар сонининг юқори чегараси гуруҳлашлар сони билан аниқланади. ва лар катта сонлар бўлганда оптимал ечимни, ҳамма таянч ечимларни саралаб (текшириб) топиш жуда катта мураккабликка олиб келади. Шунинг учун, бирор тартибланган схема бўйича бир таянч ечимдан иккинчи таянч ечимга ўтиш алгоритмига эга бўлишга тўғри келади. Бундай схема бўлиб, симплекс усул ҳисобланади.

Чизиқли дастурлаш масаласини симплекс усул билан ечишга кўпинча режани (ечимни) кетма-кет яхшилаш усули ҳам деб юритилади. Бундай аталишида усулнинг асосий ғояси, қуйидаги кетма-кет амалга ошириладиган қадамлардир:
1-қадам, бошланғич мумкин бўлган ечим топилади;
2-қадам, топилган ечимнинг оптималлиги текширилади;
3-қадам, ечим оптимал бўлмаса, 2-қадамда оптимал ечимга яқинроқ бошқа мумкин бўлган ечимга ўтилади. Кейин, яна 2-қадамга ва ҳакозо оптимал ечим олингунча давом эттирилади. Масала ечимга эга бўлмаса ёки мақсадли функция ечимлар кўпбурчагида чегараланмаган бўлса, симплекс усул билан ечиш жараёнида буни аниқлаш имконияти яратилади.
Базис режани топиш. Қуйидаги чизиқли дастурлаш масаласи қўйилган бўлсин: чизиқли функциянинг

чеклаш шартларини қаноатлантирувчи минимум қийматини топиш талаб этилади. Бунда . Бундай қўйилган масалага чизиқли дастурлашнинг каноник масаласи дейилади.
Чеклаш шартлари m та векторлар бўлсин. Бу ҳолда
, (5)
чизиқли функциянинг
(6)
, (7)
чеклаш шартларини қаноатлантирувчи минимум қийматни топиш масаласи ҳосил бўлади. (6) системани вектор шаклида ёзсак:
(8)
ёйилма ҳосил бўлади, бунда

векторлар ўлчовли фазонинг чизиқли боғланмаган бирлик векторлари бўлади. Булар бу фазонинг базисини ташкил этади. Шунинг учун, (8) ёйилмада базис ўзгарувчилари учун ларни олиб, озод ўзгарувчиларни 0 га тенг деб, ҳамда эканлигини ҳисобга олиб, бирлик векторлар бўлганлиги учун
(9)
бошланғич режани ҳосил қиламиз. (9) режа
(10)
ёйилмага мос келиб, векторлар чизиқли боғланмаган, демак бошланғич олинган режа таянч режа ҳам бўлади.
Энди сисмплес усулнинг оптималлик шартини қараймиз. Чизиқли дастурлашнинг (5)-(7) масаласи қўйилган бўлиб, режа мавжуд ва у махсусмас бўлсин. Бу ҳолда (9) таянч ечим учун ушбуни ҳосил қиламиз:
, (11)
, (12)
бунда ҳамма чизиқли функциянинг бу режага мос келган қийматини ифодалайди.
Исталган вектор базис векторлари орқали ягона ёйилмага:
(13)
эга бўлади, шунинг учун вектор ёйилмасига бу базисда чизиқли функциянинг ягона
(14)
қиймати мос келади. - векторга мос чизиқли функциядаги коэффициентлари бўлсин. Куйидаги теоремани исботсиз келтирамиз:
1-теорема. Бирор вектор учун баҳо бажарилса, режа оптимал бўлмайди ва шундай режани топиш мумкинки, тенгсизлик бажарилади (теореманинг исботини ўқув режаси кенгроқ курслардан топиш мумкин).
1-натижа. Бирор режа учун ҳамма векторлар учун шу базисдаги ёйилмаси учун

шарт бажарилса, режа оптимал бўлади.
(5)-(7) чизиқли дастурлаш масаласи максимумга ечилаётган бўлса қуйидаги теорема ўринли бўлади.
2-теорема. Бирор вектор учун баҳо бажарилса, режа оптимал бўлмайди ва шундай ечим мавжудки, тенгсизлик бажарилади.
2-натижа. Бирор режа ва ҳамма лар учун

шарт бажарилса, режа оптимал бўлади.
Энди симплекс усул алгоритмини қараймиз.
режа (5)-(7) чизиқли дастурлаш масаласининг таянч ечими бўлсин. Бу таянч ечим оптималлигини текшириш учун (6) система векторларни базис векторлари орқали ёйиб баҳоларни ҳисоблаймиз. Базис бирлик базис бўлганлиги учун векторларнинг бу базисдаги ёйилмаси коэффициентлари учун унинг компонентлари хизмат қилади, яъни бўлади. Кейинги ҳисоблашларни бажариш учун жадваллар тузиш кулай. С_б­ - базис устунга базис векторига мос келган чизиқли функциядаги коэффициентларни ёзамиз. А₀ устунига бошланғич режани ёзиб, ҳисоблашлар натижасида шу устундан оптимал ечим қийматини аниқлаймиз. устунларга, j - векторнинг базис ёйилмасидаги коэффициентлари ёзилиб, бундан кейин уларни билан белгилаймиз. (m+1) - сатрнинг А₀ устунига чизиқли функциянинг қиймати ёзилади, лар устунларига баҳонинг қийматлари ёзилади.
Функциянинг ва қийматларини қуйидаги скаляр кўпайтмалар шаклида топилади:
,
,
бунда базис векторларининг чизиқли функциядаги мос коэффициент-ларидир. Шундай қилиб, 1-симплекс жадвални ҳосил қиламиз.
1-симплекс жадвал.