2 – мавзу. Иккиланган чизиқли программалаштириш назарияси

2 – мавзу. Иккиланган чизиқли программалаштириш назарияси


2.1. Иккиланган чизиқли программалаштириш масаласи
2.2. Иккиланма симплекс усул
2.3. Бутун сонли программалаштириш масаласи


2.1. Иккиланган чизиқли программалаштириш масаласи
Ҳар қандай чизиқли программалаштириш масаласи, иккиланган масала деб аталувчи, бошқа чизиқли программалаштириш масаласи билан узвий боғланган. Масалалар орасидаги боғланиш шундан иборатки, улардан ихтиёрий бирини ечиб, иккинчисининг ҳам ечимини аниқлаш мумкин. Ўзаро боғлиқ бўлган бундай масалаларни биргаликда иккиланган масалалар дейилади. Демак, иккиланган масала, берилган ва иккиланган масалалардан иборат экан.
Берилган масала ва иккиланган масалалар орасидаги боғланиш шундан иборатки, бунда берилган масала мақсад функцияси номаълумлари олдидаги коэффициентлар , иккиланган масала чегаравий шартларида озод ҳадлардан иборат, берилган масала чегаравий шартларидаги озод ҳадлар, иккиланган масала мақсад функцияси номаълумлари олдидаги коэффициентлардан иборат, иккиланган масала чегаравий шартларидаги номаълумлар олдидаги коэффициентлардан тузилган матрица, берилган масала чегаравий шартларидаги коэффициентлар транспонирланган матрица кўринишида бўлади. Иккиланган масаланинг ечими берилган масала ечимидан олинади ва аксинча.
Ўзаро иккиланган масалаларнинг иқтисодий талқини. Ресурслардан фойдаланиш масаласи. Корхона турдаги маҳсулот ишлаб чиқарсин. Бу маҳсулотларни ишлаб чиқариш учун, турдаги ресурслар миқдорларда мавжуд бўлсин. - маҳсулотнинг бир бирлигини ишлаб чиқариш учун, – ресурснинг бирлиги сарфланиб, унинг нархи бирликдан иборат бўлсин.
Ишлаб чиқаришни шундай режалаштириш керакки, ресурслардан оптимал фойдаланиб, пул бирлиги ифодасида максимал маҳсулот ишлаб чиқарсин.
Ишлаб чиқаришда режалаштирилган - маҳсулотнинг миқдорини билан белгилаймиз. У ҳолда берилган чизиқли программалаштириш масаласининг математик моделини қуйидагича ифодалаш мумкин.
Векторни топингки, унинг координаталари чегаравий шартлар системасини қаноатлантириб,

мақсад функцияга максимал қиймат берсин
.
Энди маҳсулот ишлаб чиқариш учун сарф қилинадиган ресурсларни баҳолаймиз. Ресурсларнинг бир бирлик нархи, ишлаб чиқариладиган маҳсулотнинг бир бирлик нархи билан, бир хил ўлчов бирлигига эга. билан - хил бир бирлик ресурснинг баҳосини белгилаймиз. У ҳолда иккиланган чизиқли программалаштириш масаласининг математик моделини қуйидагича ифодалаш мумкин.
векторни топингки, унинг координаталари чегаравий шартлар системасини қаноатлантириб,

мақсад функцияга минимал қиймат берсин
.
Кўриб ўтилган, берилган ва иккиланган масалаларни қуйидагича талқин қилиш мумкин.
Берилган масала. Бир бирлик маҳсулотнинг берилган нархи ва чегараланган ресурслардан фойдаланиб, қайси маҳсулотдан қанча миқдорда ишлаб чиқарилганда, маҳсулот ишлаб чиқаришнинг нарх ифодаси максимал?
Иккиланган масала. Бир бирлик маҳсулотнинг берилган берилган нархи ва чегараланган ресурслардан фойдаланиб, умумий ҳаражат минимал бўлиши учун, ҳар бир бирлик ресурснинг нархи қандай бўлиши зарур?