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

2 - расм



1 - расм


3 - расм 4 - расм


Мисол. Чизиқли программалаштириш масаласини ечинг


Ечиш. Мумкин бўлган ечимлар соҳасини қурамиз (5-расм). Масаланинг чегаравий шартларини номерлаймиз. Декарт координаталар системасида (1) чегаравий шартга асосан тўғри чизиқни қурамиз. Бу тўғри чизиқ текисликни, иккита ярим текисликка бўлади. Булардан қайси бири қидирилаётган ярим текислик эканлигини аниқлаймиз. Бу тўғри чизиқ координаталар бошидан ўтмаганлиги учун, нуқтанинг координаталарини (1) чегаравий шартга қўйиб , тўғри тенгсизлик 0>2 ни ҳосил қиламиз. Демак О нуқта, қидирилаётган ярим текисликка тегишли экан.
Шу каби, (2) – (4) тўғри чизиқларни қурамиз.



5 -расм

Градиент топдик, градиентга перпендикуляр бўлган функциянинг сатҳ чизиғиини ўтказдик, уни ўзига параллел равишда, йўналиши бўйича силжитамиз. Бу тўғри чизиқ, мумкин бўлган ечимлар соҳаси (1) ва (2) тенгсизликларга мос бўлган, тўғри чизиқларнинг кесишиш нуқтасидан ўтади. Қуйидаги системани ечиб, нуқтанинг координаталарини топамиз

ҳосил қилдик. Бундан эса мақсад функциянинг қиймати келиб чиқади . Демак, .

Чизиқли программалаштириш масаласини симплекс усулда ечиш
Симплекс усул, каноник шаклда берилган чизиқли программалаштириш масаласини ечишнинг универсал усулларидан биридир.
Симплекс усулнинг ғояси (режани кетма-кет яхшилаш усули) шундан иборатки, бунда бирор бошланғич таянч ечимдан бошлаб, кетма-кет таянч ечимлар бўйича, йўналган ҳолда ҳаракатланиб, масаланинг оптимал ечимига эришади. Максимум масалада, мақсад функциянинг қиймати камаймайди. Таянч ечимлар чекли бўлгани учун, чекли сондаги қадамлардан сўнг оптимал ечим аниқланади.
Чизиқли программалаштириш масаласининг оптималлик критерияси, қуйидаги ифодадан иборат
.
Агар максимум масалада, барча баҳолар манфий бўлмаса, у ҳолда топилган ечим оптимал бўлиб, уни яхшилаш шарт эмас. Лекин, агар ҳеч бўлмаганда бирор қиймати манфий бўлса, у ҳолда масаланинг ечимини яхшилаш зарур, бунда га мос бўлган номаълум, базисдаги мос номаълум билан алмаштирилади.
Демак, чизиқли программалаштириш масаласини ечишнинг оптималлик критерияси қуйидагича таърифланади: максимум масалада, чизиқли программалаштириш масаласини ечими оптимал бўлади, агар барча баҳолар манфий бўлмаса (яъни ) ва минимум масалада эса, барча баҳолар мусбат бўлмаса (яъни ).
Чизиқли программалаштириш масаласининг каноник шакли:
Мақсад функция

Чегаравий шартлар


Масалани симплекс усул билан ҳисоблаш учун, симплекс жадвал тузилади.

БН	C	B			...				...
					...				...
…	…	...	1 0 ... 0	0 1 ... 0	... ... ... ...	0 0 ... 1	...	...	... ... ... ...	...
			0	0	...	0			...