Chiziqli dasturlash masalasining geometrik talqini

chiziqli dasturlash masalasining geometrik talqini Reja: chiziqli dasturlash masalasining geometrik talqini. Gipertekisliklar haqida tushunchalar. Geometrik nuqtai nazardan chiziqli dasturlash masalasining ta'rifi. Chegaralangan KavariK to'plam hosil qiluvchi iqtisodiy masalani grafik usulda yechishning umumiy holi. Chegaralanmagan KavariK ko'pburchakni yechish hollari. Quyidagi ko'rinishda yozilgan chiziqli dasturlash masalasini ko'ramiz: Ushbu chiziqli dasturlash masalasining geometrik talqini bilan tanishamiz. Malumki, n ta tartiblishgan x1, x2, …, xn sonlar n-ligi (birlashmasi) n o'lchovli fazoning nuqtasi bo'ladi. Shuning uchun (1)-(3) chiziqli dasturlash masalasining rejasini n o'lchovli fazoning nuqtasi deb qarash mumkin. Bizga malumki, bunday nuqtalar to'plami KavariK to'plamdan iborat bo'ladi. QavariK to'plam chegaralangan (KavariK ko'pburchak), chegaralanmagan (KavariK ko'p Kirrali soha) bo'lishi, bitta nuqtadan iborat bo'lishi yoki bo'sh to'plam bo'lishi ham mumkin. Koordinatalari a1x1 + a2x2+ … + anxn=a tenglamani Kanoatlantiruvchi (x1, x2, …, xn) nuqtalar to'plami gipertekislik deb ataladi. Shu sababli c1x1 + c2x2+ … + cnxn=Y ko'rinishda yozilgan maqsad funksiyani Y funksiyaning turli P qiymatlariga mos keluvchi o'zaro parallel gipertekisliklar oilasi deb qarash mumkin. Har bir gipertekislikning ixtiyoriy nuqtasida Y funksiya bir xil qiymatni Kabul qiladi (demak, o'zgarmas sathda saqlanadi). Shuning uchun ular «sath tekisliklari» deyiladi. Geometrik nuqtai nazardan chiziqli dasturlash masalasini Kuyidagicha ta'riflash mumkin: va (2) shartlarni Kanoatlantiruvchi yechimlar ko'pburchagiga tegishli bo'lgan shunday X* = (x1*, x2*, …, xn* ) nuqtani topish kerakki, bu nuqtada Y maqsad funksiya maksimum (minimum) qiymat beruvchi (3) gipertekisliklar oilasiga tegishli bo'lgan gipertekislik o'tsin. Jumladan, n=2 da (1)-(3) masala Kuyidagicha talqin Kilinadi: (1)-(2) shartlarni Kanoatlantiruvchi yechimlar ko'pburchagiga tegishli bo'lgan shunday X* = (x1*, x2*) nuqtani topish kerakki, bu nuqtadan Y maqsad funksiyaga eng katta (eng kichik) qiymat beruvchi va (3) daraja chiziqlar oilasiga tegishli bo'lgan chiziq o'tsin. chiziqli dasturlash masalasining geometrik talqiniga hamda 2-ma'ruzada tanishgan chiziqli dasturlash masalasi yechimining xossalariga tayanib masalani bazi hollarda grafik usulda yechish mumkin. Ikki o'lchovli fazoda berilgan quyidagi chiziqli dasturlash masalasini ko'ramiz. Faraz Kilaylik, (4) sistema (5) shartni Kanoatlantiruvchi yechimlarga ega bo'lsin. Hamda ulardan tashkil topgan to'plam chekli bo'lsin. (4) va (5) tengsizliklarning har biri ai1x1 + ai2x2= bi (i=1,…,m), x1=0, x2=0 chiziqlar bilan chegaralangan yarim tekisliklarni ifodalaydi. chiziqli funksiya (6) ham malum bir o'zgarmas C0=const qiymatda s1x1 + s2x2= const to'g'ri chiziqni ifodalaydi. yechimlardan tashkil topgan KavariK to'plamni hosil qilish uchun a11x1 + a12x2= b1, a21x1 + a22x2= b2, …, am1x1 + am2x2= bm, x1=0, x2=0 to'g'ri chiziqlar bilan chegaralangan ko'pburchakni yasaymiz. Faraz Kilaylik, bu ko'pburchak ABCDE beshburchakdan iborat bo'lsin 1-shakl chiziqli funksiyani ixtiyoriy o'zgarmas C0 songa teng deb olamiz. Natijada s1x1 + s2x2= C0=const ...