Чизикли программалаштириш масаласининг

Чизикли программалаштириш масаласининг
геометрик маъноси
Режа:


1. Чизикли программалаштириш масаласининг геометрик маъноси
2. Каварик тупламларЧизикли программалаштириш масалаларининг ечим хоссалари
3.Чизикли программалаштириш масаласини ечиш усуллари ва уларнинг иктисодий тахлили
Чизи=ли программалаштириш масаласининг
геометрик маъноси
Чизи=ли программалаштириш масаласининг геометрик маъносини тушуниш учун Олий математика курсининг «Чизи=ли алгебра ва аналитик геометрия» былимидаги баъзи тушунчаларни эсга оламиз.
Масаладаги чеклашлар системасига кирувчи чизи=ли тенгламалар ва чизи=ли тенгсизликларнинг геометрик тасвири (маъноси) =уйидагича былади:
1. ну=талар тыплами нормал векторга эга ты\ри чизи=нинг устида ётган ну=таларни ифодалайди.
2. -=уйи ярим текислик ну=талари тыпламини (ты\ри чизи= ну=талари кирмайди) ифодалайди.
3. -ю=ори ярим текислик нукталари тыпламини (ты\ри чизи= ну=талари кирмайди) ифодалайди.
4. -=уйи ярим текислик ну=талари (ты\ри чизи= киради) тыпламини ифодалайди.
5. -ю=ори ярим текислик ну=талари (ты\ри чизи= щам киради) тыпламини ифодалайди,
Чеклашлари та тенгсизликлар системаси билан берилган чизи=ли программалаштириш масаласини кырайлик.
(3.1)
(3.2)
(3.3)
Ма=сад функциясининг геометрик маъноси шундан иборатки, у ызининг щар бир ани= =ийматида йыналтирувчи векторга эга былган ты\ри чизи=ни ифодалайди.
М а=сад функцияси га гача щар хил =ийматлар бериб параллел ты\ри чизи=лар оиласини щосил =иламиз. (Чиз. 1) вектор мусбат йыналишда бир ты\ри чизи=дан иккинчисига ытганда чизи=ли функция кыпаяди, тескари йыналишда эса камаяди.
Энди (3.2) чеклашлар системасининг геометрик маъносига келсак, унга кирувчи щар бир тенгсизлик ярим текисликни ташкил этадиган чексиз кып ечимга эга. Бирга олинган система (3.2)-(3.3) барча ярим текисликларнинг умумий =исмидан ташкил топган ечимлар кыпбурчагини (Чиз. 2.) ани=лайди, бу кыпбурчакнинг ихтиёрий ички ну=таси ёки томонларида ётган ну=талар тенгламалар системасини =аноатлантиради ва уларни ечимлари былади. +авари= кыпбурчакни аналитик равишда чизи=ли тенгсизликлар системаси ёрдамида бериш мумкинлигини кыриб турибмиз, лекин щар =андай чизи=ли тенгсизликлар системаси =авари= кыпбурчак былади, деб ыйлаш ноты\ри. Агар система биргаликда былмаса, бирорта ну=тани щам ани=ламайди. Масаланинг ечимлар тыпламини ани=ловчи чеклашлар системаси =авари= кыпбурчакдан иборат былиб, ю=оридан чегараланмаган (Чиз. 3) тыплам былиши щам мумкин.
Кыпбурчакни ты\ри чизи= билан кесамиз ва уни йыналишда ызига параллел равишда ысиш (агар max сыралаётган былса) томонга сурамиз.
Агар чизи=ли форма нинг max сыралса, ты\ри чизи=ни токи ечимлар кыпбурчаги пастки ярим текисликда =олгунча суриб борамизки, щеч былмаганда битта ну=та тегишли былиб =олсин, min сыралса биринчи уринган ну=тани оламизки, кыпбурчак ю=ори ярим текисликда =олсин. Топилган ты\ри чизи= таянч ты\ри чизи\и дейилади. Ты\ри чизи=ни нинг max и томонига ёки min и томонига сурилишида 3 щол былиши мумкин.
1). Ты\ри чизи=ни ты\ри чизи= параллел кыринишда (max томонга) шундай чегаравий щолатга келадики, у билан ечим кыпбурчаги умумий бир ну=тага эга былади. ( учи) ну=тасининг координаталари ягона ечим былади (Чиз.4)

2). ты\ри чизи= ечим кыпбурчагининг 1 та ёки 2 та томонига параллел былиб =олади. У щолда томоннинг барча ну=таларида чизи=ли форма максимумига, томоннинг барча ну=таларида минимум =ийматга (Чиз.5.) эга былади

3). Агар масаланинг шартлари бир бирига зид былса, чизи=ли программалаштириш масаласи битта щам ечимга эга эмас (Чиз. 6).

Чизи=ли форманинг ани=ланиш сощаси чегараланмаган, яъни масала ечимлар тыплами =авари= кыпбурчакли тыпламдир. (Чиз. 7)

Бунда агар былса нурнинг щамма ну=таларида чизи=ли функция экстремумга эришади. Чизи=ли функциянинг ани=ланиш сощасини ызгартириб, нурни ну=та атрофида айлантириш билан икки щолга эга былиш мумкин: 1- щол ма=сад функцияси ну=тада максимумга эришади, бунга нур мос келади. 2-щол ма=сад функцияси чегараланмаган былади, бунга нур мос келади.
Шундай =илиб, чизи=ли программалаштириш масаласи ягона ечимга эга былиши мумкин (кыпбурчак учи); чексиз кып ечимга эга былиши мумкин (кыпбурчак томони); ечимга эга былмаслиги мумкин (ечимлар тыплами быш тыплам ёки бу тыпламда ма=сад функцияси чегараланмаган)
Уч номаълумли масалаларда щам худди шундай геометрик тал=ин ыринли. Бу умумий щолдаги масаланинг шартлари фазода =авари= кыпё=лини щосил =илади.
Чизи=ли функция коэффициентлари гипертекислик бо\ламини ани=лайди, у экстремумга кыпё=лининг учларида эришади. Агар экстремумга 1 тадан орти= ну=тада эришса, у щолда у гипертекисликка параллел бутун =иррада ёки бутун ё=да эришади. Чизи=ли программалаштириш масалаларининг геометрик тал=ини 2 ва 3 ызгарувчили масалаларни график усулда ечишга имкон беради. Буни мисолларда кырайлик.
Завод хил мащсулот ишлаб чи=аради. Бунинг учун маълум ми=дорда материал (цемент, арматура) ва маълум ми=дорда мещнат ва энергия сарфлари керак былади. Материал, ишчи кучи ва энергия ресурслари чегараланган.
Мащсулот нархи энг ю=ори былиши учун уларнинг щар биридан неча донадан ишлаб чи=ариш керак?

Кырсаткичлар	Мащсулот тури		Мавжуд ресурслар
	1	2
Мащсулот нархи	250	400	-
Цемент сарфи, кг	80	170	20000
Арматура сарфи, кг	67	55	8000
Мещнат сарфи, ишчи-соати	30	40	6000
Энергия сарфи, квт. соат.	52	67	12000

+уйидаги белгилашларни киритамиз:

турдаги тайёрланадиган мащсулот ми=дори;
турдаги мащсулот нархи;
турдаги 1 та мащсулотга кетадиган -тур ресурснинг сарфи.
-ресурсларнинг мавжуд щажми.
Умумий щолда ма=сад функцияси ва чеклашлар системаси =уйидаги кыринишда былади.
, бу тенгсизликлар сони ресурслар сони нечта былса шунча былади ва манфий эмаслик шарти щам чеклашлар системасига киради. Берилган масаланинг математик моделини ёзайлик:
(3.1)
(3.2)
(3.3)
Ечиш. Масаланинг чеклашлар системаси тенгсизликларни =аноатлантирувчи ечимлар тыплами-кыпбурчакни =урамиз. Масаланинг мумкин былган ечимлари ОАСВ кыпбурчакнинг ичидаги ёки чегараларидаги ну=талардан иборат (8-чизма). Улар ичидан ма=сад функциясига максимум =иймат берувчи ягона ечимни танлаш керак. Ма=сад функциясини 0 га тенглаб таъсир чизи\ини чизамиз, унинг йыналтирувчи в ектори:
Таъсир чизи\ини йыналтиришда пареллел суриб кыпбурчак билан умумий былган энг охирги четки ну=тани ани=лаймиз. Бу ну=та масаланинг оптимал ечими былади. . Демак, завод 1-тур мащсулотдан 40 дона, 2-тур мащсу-лотдан 98 дона ишлаб чи=арса максимал фойда кырар экан. графикнинг тащлили кырсатадики, мащсулотни ишлаб чи=ариш учун цемент ва арматура защираси етади. Агар цемент ва арматура защираси ошса мещнат ва энергия сарфи мащсулот ишлаб чи=ариш ошишига имкон беради. Бу мос чизи=лар координата бошидан га нисбатан узо=да жойлашганидан кыриниб турибди. Ща=и=атдан щам 1- ва 2- тур мащсулот 40 ва 98 дона ишлаб чи=аришига цемент кг, арматура сарф былади.