Чизиқли программалаштириш масаласи. Чизиқли программалаштириш масаласини ечиш усуллари. Чизиқли программалаштиришда иккиланма назария

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

чизиқли функцияни минималлаштиринг
,
бунда ; ; - скаляр кўпайтма; озод ҳадлар ва номаълумлар олдидаги коэффициентлар векторлардан иборат
.
Чизиқли программалаштириш масаласи ёзилишининг матрица шакли. Қуйидаги чегаравий шартларда

чизиқли функцияни минималлаштиринг
,
бунда - сатрли матрица; - система матрицаси;
, - устунли матрица.


Чизиқли программалаштириш масаласи ёзилишининг йиғинди белгилари шаклидаги кўринишии. Қуйидаги чегаравий шартларда

чизиқли функцияни минималлаштиринг
.


Чизиқли программалаштиришнинг баъзи теоремалари.
Теорема (чизиқли тенгсизликни, чизиқли тенгламага алмаштириш).
Тенгсизликнинг
(2)
ҳар бир ечимига, бўлганда,
(3)
тенгламанинг ягона ечими мос келади ва аксинча.
Исбот. (2) тенгсизликнинг ечими, бўлсин. У ҳолда қуйидаги сонли тенгсизлик ўринли
.
Белгилаш киритамиз .
У ҳолда

Бунда, . Бу дегани , (3) тенгламанинг илдизи бўлиб, ни қаноатлантиради.
Демак, агар чегаравий шартлар системасида тенгсизликлар бўлса (бундай ҳолда чизиқли программалаштириш масаласи стандарт шаклда берилган дейилади), у ҳолда ҳар бир тенгсизликка, қўшимча ўзгарувчи киритиб, тенгламалар системасини ҳосил қилиш мумкин. Қўшимча ўзгарувчиларни мувозанат ўзгарувчилар ҳам дейилади.
Мана шундан, каноник бўлмаган чизиқли программалаштириш масаласидан, каноник шаклга ўтиш қоидаси келиб чиқади. Масала каноник шаклга ўтиши учун, ҳар бир тенгсизликка мувозанат ўзгарувчилар киритилади. Агар тенгсизликнинг белгиси бўлса, мувозанат ўзгарувчи тенгсизликка мусбат ишора билан, тенгсизликнинг белгиси бўлса, манфий ишора билан киритилади. Мақсад функцияга мувозанат ўзгарувчилар киритилмайди.
Мисол. Тенгсизликларни тенгламаларга ўтказинг:
а) .
б) .
Ечиш.
а)
б)
Теорема (чегараланган соҳадаги, мақсад функция экстремуми). Агар чизиқли программалаштириш масаласидаги, берилган чегаравий шартлар системасининг, мумкин бўлган ечимлар соҳаси, ёпиқ ва чекли бўлса, бу таянч ечимлар орасидан ҳеч бўлмаганда биттаси, берилган масаланинг оптимал ечими бўлади.






Теорема (чегараланмаган соҳадаги, мақсад функция экстремуми). Агар мумкин бўлган ечимлар соҳаси чегараланмаган бўлса, оптимал ечим мавжуд бўлишиининг зарур ва етарли шарти, максимум масалада мақсад функция юқоридан чегараланган, ёки минимум масалада эса қуйидан чегараланган бўлади.
Агар теоремалар шарти бажарилмаса, мақсад функция, мумкин бўлган ечимлар соҳасида чегараланмаган бўлади.



Мисол. Чегаравий шартлар системасини каноник шаклга келтиринг:

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