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

Чизиқли программалаштириш масалаларини турли кўринишларда ифодалаш
Чизиқли программалаштириш масаласи умумий ҳолда қуйидагича ифодаланади:
(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-хулоса. Чизиқли программалаштириш масаласининг оптимал ечимини М тўпламнинг четки нуқталари орасидан қидириш керак.
Чизиқли программалаштириш масаласини ечиш усуллари М тўпламнинг четки нуқталари ичида оптимал нуқтани қидиришга асосланган. Бу усуллардан бири симплекс усулидир. Симплекс усул асосларининг алгоритм билан танишишдан олдин чизиқли программалаштириш масаласининг геометрик интерпретацияси билан танишайлик.