Mavzu: Chiziqli dasturlash masalalari. Chiziqli dasturlash masalalarini yechishning simpleks usulini C++ da bajarish

2-Mustaqil ish mavzusi.

Mavzu: Chiziqli dasturlash masalalari. Chiziqli dasturlash masalalarini yechishning simpleks usulini C++ da bajarish (aniq bitta misolda koʻrsatish).

Reja

1. 
   Simpleks usul xakida kiskacha umumiy ma’lumot
   
2. 
   Simpleks usulning algoritmi
   
3. 
   Ba’zi iktisodiy masalalarni simpleks usul yordamida echish
   

1.CHiziqli programmalash sohasini ilk prinsiplari L.V. Kontorovichni “ Математические методы организации и планирования производства ” nomli ishlarida uchraydi(1939y), 1947 yida esa amerika olimi Dansig tomonidan chiziqli programmalash masalasini umumiy qo‘yilgan.

Biz bilamizkichiziqli programmalash masalasi bu chizikli funksionalni ko‘p o‘lchovli fazoda chiziqli cheklovlarni qanoatlantirgan holda minimum yoki maksimum qiymatini topishdan iborat. Bu masaladagi xar bir chiziqli cheklovlar n- o‘lchovli fazoni (n-1)- o‘lchovli yarim fazosi bo‘ladi, demak bundan chikadiki barcha chiziqli cheklovlarni umumiy echimi (mumkin bo‘lgan rejalar to‘plami)n- o‘lchovli fazoda qavariq ko‘pyoq bo‘ladi.

Simpleks usul chiziqli programmalash masalasini mumkin bo‘lgan rejalar to‘plami bo‘lgan ko‘pyoqni uchlari orasidan optimal echimni topish usulidir. Agar masalani o‘zgaruvchilar soni n-ta cheklovlar soni m-ta bo‘lsa u holda ko‘pyoqning uchlari soni S_n^m–ga teng bo‘ladi, bu esa katta son bo‘lib, burchaklarni birma-bir tekshirib chiqish maqsadga muofiq emas.

2. Umumiy holda berilgan kuyidagi chiziqli programmalash masalasini ko‘raylik:

a₁₁x₁+a₁₂x₂+…+a_1nx_n≤b₁

a₂₁x₁+a₂₂x₂+…+a_2nx_n≤b₂

. . . . . . . . . . . . . (1)

a_m1x₁+a_m2x₂+…+a_mnx_n≤b_m,

x_1, x_{2, . . . ,} x_n≥0 shartlarni qanoatlantirgan holda F=c₁x₁+c₂x₂+…+c_nx_n (2) maqsad funksiyaga maksimal qiymat beruvchi x_1, x_{2, . . . ,} x_nlarni topish kerak.

1-qadam. Berilgan (1) tengsizliklar sistemasida yangi x_n+1, x_{n+2, . . . ,} x_n+m, musbat o‘zgaruvchilar kiritib barcha tengsizliklarni tengliklarga aylantirib olamiz. Bu erda yangi kiritilgan o‘zgaruvchilarni iktisodiy ma’nosi: shu o‘zgaruvchi katnashgan tengsizlikga mos keluvchi xom ashyoni ortib qolgan miqdoridir. Demak n+m- o‘zgaruvchili m-ta chiziqli tenglamalar sistemasini xosil qildik va bu sistemada x_n+1, x_{n+2, . . . ,} x_n+m – o‘zgaruvchilar faqat bittadan tenglamada bir koeffitsiet bilan ishtirok etadi.

2-qadam. Xosil bo‘lgan tenglamalar sistemada x_n+1, x_{n+2, . . . ,} x_n+m – o‘zgaruvchilarni bazis o‘zgaruvchilar, x_1, x_{2, . . . ,} x_n–o‘zgaruvchilarni esa erkin o‘zgaruvchilar deb olamiz va bazis o‘zgaruvchilarni erkin o‘zgaruvchilar orqali ifodalaymiz.

x_n+1= b₁ -a₁₁x₁-a₁₂x₂-…-a_1nx_n

x_n+2=b₂ -a₂₁x₁-a₂₂x₂-…-a_2nx_n

. . . . . . . . . . . . . (3)

x_n+m =b_m-a_m1x₁-a_m2x₂-…-a_mnx_n,

bu erda x_1, x_{2, . . . ,} x_n–o‘zgaruvchilarni barchasiga 0 qiymat bersak

x_n+1, x_{n+2, . . . ,} x_n+m – o‘zgaruvchilar mos ravishda b₁, b₂, ..., b_m –qiymatlarni qabul qiladi va (0,0,...,0, b₁, b₂, ..., b_m,) birinchi tayanch reja bo‘ladi.