Чизиқли программалаштириш масалаларини турли кўринишларда ифодалаш



Download 76,66 Kb.
Sana25.02.2022
Hajmi76,66 Kb.
#271016
TuriПрограмма

Чизиқли программалаштириш масалаларини турли кўринишларда ифодалаш
Чизиқли программалаштириш масаласи умумий ҳолда қуйидагича ифодаланади:
(6)


(7)
(8)
(6) ва (7) шартларни қаноатлантирувчи номаълумларнинг шундай қийматларини топиш керакки, улар (8) чизиқли функцияга минимал (максимал) қиймат берсин. Масаланинг (6) ва (7) шартлари унинг чегараловчи шартлари деб, (8) чизиқли функцияни эса масаланинг мақсади ёки мақсад функцияси деб аталади. Масаладаги (6) шартнинг чап томони ва мақсад функцияси номаълумларга нисбатан чизиқли экани кўриниб турибди. Шунинг учун ҳам (6)-(8) масала чизиқли программалаштириш масаласи деб аталади.
Аниқ масалаларда (6) шарт тенгламалар тизимидан иборат бўлиши мумкин:
(9)


(10)
(11)
(9)-(11) кўриниш чизиқли программалаштириш масаласининг каноник кўриниши деб аталади.
Берилган (9)-(14) масала векторлар ёрдамида қуйидагича ифодаланади:
(12)
(13)
(14)
Бу ерда

-вектор қатор
-вектор устун.
Масаланинг матрица ёрдамидаги ифодаси бундай:
(15)
(16)
(17)
Бу ерда -матрица қатор, коэффицентлардан ташкил топган матрица:
-устун матрица
Берилган масалани йиғиндилар ёрдамида ифодалаш ҳам мумкин:
(18)
(19)
(20)
Чизиқли программалаштириш масалаларини қуйидаги келтирилган таъриф кўринишларида ҳам ифодалаш мумкин.
1-таъриф. Берилган (9)-(11) масаланинг мумкин бўлган ечими ёки режаси деб, унинг (6)-(7) шартларини қаноатлантирувчи векторларга айтилади.
2-таъриф. Агар (12) ёйилмадаги мусбат коэффицентли векторлар ўзаро чизиқли боғлиқ бўлмаса, режа таянч режа дейилади.
3-таъриф. таянч режадаги мусбат компонентлар сони га тенг бўлса, бу режа айнимаган таянч режа, акс ҳолда айниган таянч режа дейилади.
4-таъриф. Чизиқли функция (11) га энг кичик ёки энг катта қиймат берувчи каноник режа масаланинг оптимал режаси ёки оптимал ечими дейилади.


4-§ Тенгсизликни тенгламага айлантириш
та номаълумли
(21)
чизиқли тенгсизлик берилган бўлсин. Бу тенгсизликни тенгламага айлантириш учун унинг кичик томонига манфий бўлмаган номаълум
(22)
ни қўшамиз. Натижада та номаълумли чизиқли тенглама ҳосил бўлади:
(23)
Берилган (21) тенгсизликни тенгламага айлантириш учун қўшилган номаълум қўшимча ўзгарувчи деб аталади.
Шундай йўл билан чизиқли программалаштириш масаласининг чегараловчи шартларидаги тенгсизликларни тенгламага айлантириш мумкин. Бунда шунга эътибор бериш керакки, тизимдаги турли тенгсизликларни тенгламага айлантириш учун қўшиладиган қўшимча ўзгарувчилар бир-биридан фарқли бўлиш керак.
Масалан, чизиқли программалаштириш масаласининг математик модели
(24)


(25)
(26)
Кўринишда бўлса, бу масаладаги тенгсизликларни кичик томонига қўшимча ўзгарувчилар қўшиш ёрдамида тенгламага айлантириш мумкин. Бу ўзгарувчиларга 0 коэффицент билан киритилади. Натижада берилган (24)-(26) масала қуйидаги кўринишга келтирилади:
(27)


(28)
(29)


5-§ Чизиқли программалаштириш масаласи ечимларининг хусусиятлари
Чизиқли программалаштириш масаласининг режалари ва чизиқли функциянинг бир қанча хусусиятлари бор. Қуйида буларнинг хусусиятларига доир бўлган теоремаларни (исботсиз) ва улардан келиб чиқадиган баъзи хулосаларни келтирамиз.
1-теорема. Чизиқли программалаштириш масаласининг режалари қавариқ тўпламни ташкил этади.
2-теорема. Чизиқли программалаштириш масаласининг чизиқли функцияси ўзининг оптимал қийматига шу масаланинг режаларидан ташкил топган қавариқ тўпламнинг четки нуқтасида эришади. Агар чизиқли функция М қавариқ тўпламнинг бирдан ортиқ, четки нуқтасида оптимал қийматга эришса, у шу нуқталарнинг қавариқ комбинациясидан иборат бўлган ихтиёрий нуқтада ҳам ўзининг оптимал қийматига эришади.


3-теорема. Агар та ўзаро чизиқли боғлиқ бўлмаган векторлар берилган бўлиб, улар учун

тенглик барча ларда ўринли бўлса, вектор М қавариқ тўпламнинг четки нуқтаси бўлади.
Юқорида танишган теоремалардан қуйидаги хулосаларни чиқариш мумкин.
1-хулоса. Чизиқли программалаштириш масаласи таянч режаларидан ташкил топган тўплам М қавариқ, тўпламнинг четки нуқталар тўпламига мос келади ва аксинча, ҳар бир таянч режа тўпламининг бирор четки нуқтасига мос келади.
2-хулоса. Чизиқли программалаштириш масаласининг оптимал ечимини М тўпламнинг четки нуқталари орасидан қидириш керак.
Чизиқли программалаштириш масаласини ечиш усуллари М тўпламнинг четки нуқталари ичида оптимал нуқтани қидиришга асосланган. Бу усуллардан бири симплекс усулидир. Симплекс усул асосларининг алгоритм билан танишишдан олдин чизиқли программалаштириш масаласининг геометрик интерпретацияси билан танишайлик.
Download 76,66 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish