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

Иккиланма теоремалар. Иккиланма теоремалар, иккиланган масалалар оптимал ечимлари орасидаги боғлиқликни ўрнатади.
Теорема. Агар иккиланган масаланинг бирортаси оптимал ечимга эга бўлса, у ҳолда иккинчиси ҳам оптимал ечимга эга бўлиб, берилган ва иккиланган масалаларнинг мақсад функциялари бу оптимал ечимларда ўзаро тенг бўлади

Агар иккиланган масаладан бирортаси мақсад функциянинг чегараланмаганлигидан ечимга эга бўлмаса, у ҳолда иккинчиси ҳам чегаравий шартлар системаси биргаликда бўлмаганлигидан ечимга эга бўлмайди.
Мисол 11.7
Умумий шаклда берилган қуйидаги масалага иккиланма масала тузинг:

Берилган масала

Иккиланма масала

Айтайлик, симметрик иккиланган масалалар берилган бўлсин.

Теорема. Иккиланган масалаларнинг мумкин бўлган ечимлари ва оптимал бўлиши учун, қуйидаги тенгликларнинг бажарилиши зарур ва етарли:

.
Бошқача айтганда, агар оптимал ечим чегаравий шартлар системасига қўйилганда, берилган масаланинг - чегара шартида қатъий тенгсизлик бажарилади. Иккиланган масала оптимал ечимининг - координатаси нолга тенг, ва аксинча, агар иккиланган масала оптимал ечимининг - координатаси нолдан фарқли бўлса, у ҳолда берилган масаланинг - чегара шарти, оптимал ечимда тенглик кўринишида бўлади.
Мисол. Берилган масалага иккиланган масала тузинг

Иккиланган масала

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

Берилган масала

Иккиланган масала

Ечиш. Берилган масалани каноник шаклда ёзиб оламиз
чегаравий шартларда

Масала иккиланган симплекс усул билан ечилади




Мисол 11.10. Симметрик иккиланган масалани ечинг:

Берилган масала

Иккиланган масала

Ечиш. Берилган масалани каноник шаклда ёзиб оламиз

чегаравий шартларда

Масала иккиланган симплекс усул билан ечилади

Симплекс жадвал тузиб, иккиланган симплекс усул билан масалани ечамиз.

БН	C	B	2	4	0	0	0
	0 0 0	24 15 4	2 1 0	3 3 (1)	1 0 0	0 1 0	0 0 1
		0	-1	-2	0	0	0
	0 0 2	12 3 4	2 (1) 0	0 0 1	1 0 0	0 1 0	-3 -3 1
		8	-1	0	0	0	2
	0 1 2	6 3 4	0 1 0	0 0 1	1 0 0	-2 1 0	(3) -3 1
		11	0	0	0	1	-1
	0 1 2	2 9 2	0 1 0	0 0 1	1/3 1 -1/3	-2/3 -1 2/3	0 0 1
		13	0	0	1/3	1/3	0

Симплекс жадвалдан .

Иккиланган масала учун .
Масала 11. Корхона миқдорлари мос равишда 18,16, 8, 6 т бўлган, тўрт А, Б, В, Г турдаги ашёлардан, уч турдаги маҳсулот ишлаб чиқаради.
Ҳар бир ашёнинг бир бирлик маҳсулот ишлаб чиқаришдаги меъёри, биринчи тур маҳсулот учун 1,2,1,0 т, иккинчи тур маҳсулот учун – 2,1,1,1 т, учинчи тур маҳсулот учун – 1,1,0,1 т иборат. Корхонанинг бир бирлик маҳсулотни сотишдан оладиган даромади биринчи тур маҳсулот учун – 3 пул бирлиги, иккинчи тур маҳсулот учун – 4 пул бирлиги, учинчи тур маҳсулот учун – 2 пул бирлиги иборат. Бу уч турдаги маҳсулотларни ишлаб чиқаришни шундай режалаштириш керакки, бунда даромад максимал бўлиб, бу оптимал режага мос бўлган, хом ашё миқдорини аниқлаш талаб этилади.
Ечиш. Айтайлик, - уч турдаги маҳсулотларни ишлаб чиқариш режаси бўлса, у ҳолда масаланинг математик модели қуйидаги кўринишда бўлади.

чегаравий шартларда

Масалани иккиланган симплекс усул билан ечамиз. Бунинг учун аввало иккиланган масалани тузамиз

Берилган масалани каноник шаклга келтирамиз

Бунга асосланиб симплекс жадвал тузамиз

БП	С	В	3	4	2	0	0	0	0
	0 0 0 0	18 16 8 6	1 2 1 0	2 1 1 (1)	1 1 0 1	1 0 0 0	0 1 0 0	0 0 1 0	0 0 0 1
		0	-3	-4	-2	0	0	0	0
	0 0 0 4	6 10 2 6	1 2 (1)0	0 0 0 1	-1 0 -1 1	1 0 0 0	0 1 0 0	0 0 1 0	-2 -1 -1 1
		24	-3	0	2	0	0	0	4
	0 0 3 4	4 6 2 6	0 0 1 0	0 0 0 1	0 (2) -1 1	1 0 0 0	0 1 0 0	-1 -2 1 0	-1 1 -1 1
		30	0	0	-1	0	0	3	1
	0 2 3 4	4 3 5 3	0 0 1 0	0 0 0 1	0 1 0 0	1 0 0 0	0 ½ ½ ½	-1 -1 0 1	-1 ½ -1/2 1/2
		33	0	0	0	0	1/2	2	3/2

Жадвалга асосан (пул бирл.).

Иккиланма теоремалар ёрдамида қуйидагини топамиз (пул бирл.).
Бутун сонли программалаштириш масаласи
Кўпгина иқтисодий масалалар чизиқли программалаштириш масаласидаги келтирилиб, унинг бутун сонли ечимини топиш талаб қилинади. Уларга қуйидаги масалалар киради. Бундай масалаларда, ўзгарувчилар, бўлинмайдиган маҳсулот миқдори бирликларидан иборат. Масалан, материалларни қирқиш, ускуналарни юклаш, машиналар (агрегатлар, ускуналар, чорвадаги моллар) миқдори, пароходларни йўналишлар бўйича тақсимлаш, самолётларни рейслар бўйича тақсимлаш ҳамда бўлинмайдиган маҳсулот ишлаб чиқиш масалаларидан иборат.
Бундай масалалар чизиқли ва чизиқсиз бўлиши мумкин. Бунда, бутун сонли чизиқли программалаштириш масаласи чизиқли, яъни, мақсад функция ва уни чегараловчи шартлар чизиқли деб олинади. Бунда оптимал ечим, манфий бўлмаган бутун сонлардан иборат бўлиши талаб этилади.
Масаланинг қўйилиши. Чегаравий шартларда

ушбу чизиқли функциянинг экстремал қийматини аниқланг
.
График усул. Агар чизиқли программалаштириш масаласида иккита ўзгарувчи ва чекловлар системаси фақат тенгсизликлардан иборат бўлса, бу масала гарфик усулда ечилади.
Текисликдаги Декарт координаталар системасида мумкин бўлган ечимлар соҳаси, вектор ва соҳалар чизиғи қурилади. Максимум масалада, соҳалар чизиғи вектор йўналиш бўйича силжитилиб, координаталар бошидан энг узоқда ётган нуқта ва унинг координаталари аниқланади.
Агар бу нуқтанинг координаталари бутун сонли бўлмаса, мумкин бўлган ечимлар соҳасида, бутун сонли катаклар қурилиб, унда шундай ва бутун сонлар топиладики, бу қийматларда мақсад функциянинг қиймати, бутун бўлмаган экстремал ечимга жуда яқин бўлади. Бу катак учларнинг координаталари масаланинг бутун сонли ечими бўлади.
Минимум масала ҳам шу каби ечилади. Мақсад функциянинг бутун сонли минимум қиймати, мумкин бўлган ечимлар соҳасидаги бутун сонли катак учлари координаталарига мос келиб, вектор йўналиш бўйича координаталар бошига энг яқин бўлган, катак учи координаталаридан иборат.
Мисол. Ташкилот ўзининг молиявий аҳволини яхшилаш мақсадида, рақобатбардош маҳсулотларини кўпайтиришни мўлжаллаб, цехларнинг бирида 19/3 майдонни эгаллайдиган қўшимча ускуна қуришни мўлжаллади. Бу қўшимча ускунани сотиб олиш учун ташкилот 10 млн руб. пул ажратди. Лекин ташкилот бу ускуна комплектини 2 тур кўринишда сотиб олади. 1 – тур кўринишдаги ускуна комплекти нархи 1 млн руб., 2 –хил кўринишдаги ускуна комплекти нархи эса 3 млн руб. туради. 1 –тур кўринишдаги ускуна комплекти маҳсулот миқдорини бир сменада 2 бирликка, 2 – тур кўринишдаги ускуна комплекти эса 4 бирликка оширади.
1–тур ускуна комплектини ўрнатиш учун 2 майдон, 2–тур ускуна комплектини ўрнатиш учун эса 1 майдон талаб этилишини билган ҳолда, қўшимча ускуналар жамланмасини аниқлаш керакки, бунда ишлаб чиқарилган маҳсулот ҳажми максимал бўлсин.
Ечиш. Масаланинг математик моделини тузамиз. Фараз қиламиз ташкилот, 1–тур қўшимча ускуна комплектидан миқдорда, миқдорда эса 2–тур ускуна комплектини сотиб олсин. Масаланинг математик модели қуйидагича бўлади


чегаравий шартларда

Бутун сонли программалаштириш масаласини ҳосил қилдик. Масалада номаълумлар сони фақат иккита ( ва ) бўлгани учун, уни график усулда ечиш мумкин. 1- расмдан кўринадики ОАВС – масаланинг мумкин бўлган ечимлар соҳасидир. Масала оптималь ечимга В(9/5, 41/15) нуқтада эришади; бунда мақсад функциянинг максимал қиймати 218/15 бирл. тенг. Бундан келиб чиқиб , (бирл.). Топилган оптимал ечим бутун сонли эмас. Масаланинг мумкин бўлган ечимлар соҳасида, бутун сонли катаклар ясалади.

О