7-laboratoriya. Chiziqli dasturlash masalasi. Masala matematik modeli, iqtisodiy tahlili. Reja

Чизикли дастурлаш масалаларини график усулида ечиш.
График усулига кўра чизиқли дастурлаш масалаларни асосан икки ўлчовли фазода, яъни текисликда кўрилади. Уч ўлчовли фазода эса жуда кам кўрилади, чунки қўйилган масала ечимларини ифодаловчи кўпбурчакларни чизиш анча мураккаб бўлади. Учдан юқори ўлчовли фазони тасаввур қилиш эса мумкин эмас.

1. Фараз қилайлик, текисликда

(1)
мақсад функциянинг, х₁, х₂ лар
(2)
тенгсизликлар системасини қаноатлантиргандаги энг кичик қийматини топиш талаб қилинсин.
(2) тенгсизликлар системасини биргаликда деб фараз қилсак, у ҳолда бу тенгсизликлар системасини ўринли ечимлар тўплами бўлган бирор кўпбурчакни ташкил этади.

ABCDEF кўпбурчакнинг шундай нуқтасини топишимиз керакки, бу нуқтада тўғри чизиқ шу кўпбурчак учун таянч тўғри чизиқ бўлиб, (1) функциямиз энг кичик қийматга эришсин.

Масала. Юқоридаги ёқилғи (аралашма) масаласини график усулда ечайлик. (1)
мақсад функциянинг х₁, х₂ лар
(2)
чекланиш тенгсизликлар системасини қаноатлантирадиган қийматларида энг катта қиймати топилсин.
(2) тенгсизликлар системасини тенгламалари системаси кўринишида ёзиб уларга мос келган тўғри чизиқларни чизайлик.

L₁, L₂ - тўғри чизиқларнинг координата ўқлари билан кесишиш нуқталарининг координаталари (0; 62,5) ва (83,3; 0); (0; 150) ва
(75; 0)


F_max =100×70+120×10=8200 cўм,
f=F_max×1000=8200000 сўм бўлган энг кўп фойда олиш учун А аралашмадан 70 тонна В аралашмадан 10 тонна тайёрлаш керак экан.


9-laboratoriya. Chiziqli dasturlash masalasi uchun egizak masala, uning iqtisodiy tahlili. Ikkilanganlik sharti.

Чизиқли дастурлашнинг нормал (стандарт) масаласи, яъни

(1)
мақсад функциянинг, х₁, х₂, . . . , х_n, номаълумлар
(2)
(3)
чекланиш тенгсизликлар системасини қаноатлантирадиган қийматларида, максимум қийматини топиш масаласи қаралаётган бўлсин.
Бу масалага иккиланма масала деб, ушбу
(4)
мақсад функциянинг, номаълумлар
(5)
(6)
чекланиш тенгсизликлар системасини қаноатлантирадиган қийматларида, минимум қийматини топиш масаласига айтилади.
Мисол.

мақсад функциянинг, лар

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

мақсад функциянинг лар
ц
чекланиш тенгсизликлар системасини қаноатлантирадиган қийматларида, минимум қийматини топиш масаласини график усулда ечиш қийинчилик туцдирмайди. Чизмадан кўринадики, иккиланма масаланинг мақсад функцияси (1;0) нуқтада минимумга эришади. . У ҳолда дастлабки масаланинг жавоби бўлади.

Chiziqli programmalashda ikkilanish nazariyasi.
Ikkilangan masalarning juftligi quyidagi ko’rinishlardan birida bo’lishi mumkin.

T/R	Berilgan Masala	Ikkilangan Masala
Simmetrik bo’lmagan masalalar
I	F=CX->min AX=  X 	G=Y ->max YA 
II	F=CX->max AX=  X 	G=Y ->min YA 
Simmetrik masalalar
III	F=CX->min AX=  X 	G=Y ->max YA  Y 
IV	F=CX->max AX=  X 	G=Y ->max YA  Y 

Demak , berilgan masala uchun ikkilangan masala tuzishdan avval , berilgan masalaning shartlari sistemasini tegishli shaklga keltirib , keyin ikkilangan masala tuziladi

1-masala. Ushbu
_{ }
F=_{ }
Masala uchun ikkilangan masala tuzilsin .
Yechish: Qaralayotgan masala simmetrik bo’lmagan masalaning II shakliga doir . Ikkilangan masalada o’zgaruvchilarning soni berilgan masala sistemasining tenglamalari soniga teng , ya’ni uchga teng. Ikkilangan masala maqsad funksiyasining koeffitsientlari berilgan masala tenglamalar sistemasining ozod hadiga , ya’ni 12 , 24 va 18 sonlariga teng bo’ladi.
Berilgan masala funksiyasining maksimumini topish talab qqilingan bo’lib , shartlar sistemasi faqat tenglamalardan iborat. Shu sababdan ikkilangan masalada maqsad funksiyasining minimumi topiladi va uning o’zgaruvchilari ixtiyoriy qiymatlarni (jumladan , manfiy qiymatlarni ham) qabul qilishi mumkin bo’ladi .
Berilgan masalaning har uchala o’zgaruvchilari faqat nomanfiy qiymatlar qabul qilganligi sababli ikkilangan masala shartlar sistemasi “≥” ko’rinishdagi tengsizlikdan iborat bo’ladi . Binobarin , berilgan masala uchun ikkilangan masala quyidagicha bo’ladi :


2-masala . Ushbu


Masala uchun ikkilangan masala tuzilsin.
Yechish Bu masala shu ko’rinishda jadvalagi berilgan masalalarning hech biriga mos kelmaydi, lekin birinchi tengsizlikka (-1)ga ko’paytirib , III shakldagi simmetrik masalani hosil qilamiz :


Bu masalaning ikkilangan masalasi quyidagi masala bo’ladi: