Mavzu: Sun`iy bazis usuli. Reja

Mavzu: Sun`iy bazis usuli.


REJA:

1. 
   Masalani normal formaga keltirish
   
2. 
   Simpleks jadval tuzish
   
3. 
   Ba’zis yechimini yozish.
   
4. 
   Tayanch yechim aniklash
   
5. 
   Yechim yuklik shartlarini tekshirish.
   
6. 
   Tayanch yechimni optimallikka tekshirish
   

Chiziqli programmalash masalasining boshlangich tayanch plani mavjud va boshlangich planni tuzish mumkin buladigan m-ulchovli birlik matrisa masala shartida katnashadi deb faraz kildik. Bu birlik matrisa yerdami bilan optimal planga utishga yerdam beradigan planni tuzish mumkin. Agar chizikli programmalash masalasining chegaraviy shartlari AXЈR₀ kurinishda berilgan bulsa, kushimcha uzgaruvchilar kiritish mumkin.

Amalda uchraydigan kup chizikli programmalash masalalari planga ega bulgan xolda birlik matrisani uz ichiga olmaydi. Bunday masalalarni yechish uchun «sun’iy bazis vektor» usul kullaniladi.
Umumiy xolda berilgan chizikli programmalash masalasini kuramiz:
a₁₁x₁+a₁₂x₂+...+ a_1nx_n=b₁,
a₂₁x₁+a₂₂x₂+...+ a_2nx_n=b₂,
.....................................
a_m1x₁+a_m2x₂+...+ a_mnx_n=b_m
x_1і0, x_2і0,..., x_nі0
u_min=c₁x₁+ c₂x₂+...+ c_nx_n
masalaning shartiga birlik matrisani kiritish uchun sistemadagi xar bir tenglamaga sun’iy uzgaruvchi deb ataluvchi x_{n+i і}0 noma’lumni mos ravishda kushamiz, xamda
u_min=c₁x₁+ c₂x₂+...+ c_nx_n+M(x_n+1+...+ x_n+m)
funksiyani minimallashtirish bilan boglik bulgan kuyidagi kengaytirilgan masalani xosil kilamiz:
a₁₁x₁+a₁₂x₂+...+ a_1nx_n +x_n+1=b₁,
a₂₁x₁+a₂₂x₂+...+ a_2nx_n+ x_n+2=b₂,
.....................................
a_m1x₁+a_m2x₂+...+ a_mnx_n+ x_n+m=b_m
x_1і0, x_2і0,..., x_nі0, x_n+1і0, x_n+mі0
u_min=c₁x₁+ c₂x₂+...+ c_nx_n +M(x_n+1+...+ x_n+m)
Berilgan masalaning optimal yechimini topish uchun kuyidagi teoremadan foydalanamiz.
Teorema. Agar kengaytirilgan masalaning
X=(x₁, x₂,...,x_n,x_n+1,...,x_n+m)
optimal planida
x_n+i =0 ( )
bulsa, X=(x₁, x₂,...,x_n) plan berilgan masalaning optimal plani buladi.
Kengaytirilgan masalaning optimal planini topish uchun yukoridagi simpleks jadvaldan kushimcha m+2 katori bilan fark kiluvchi simpleks jadvaldan foydalaniladi. Jadvalning (m+1) va (m+2) -katorini tuldirish uchun y_j-c_j ayirmani
y_j-c_j=a_j+b_jM
kurinishda ifodalanadi.
Bazisga (m+2)- katorning musbat elementlarining eng kattasi mos keluvchi vektor kiritiladi. Xamma sun’iy bazis vektorlar bazisdan chikarilguncha (m+2)- katordan sungra, optimal plan topilgunga kadar (m+1)- katordan foydalaniladi. Masalani simpleks usul kullab yechish jarayonida m+2 – katordagi koeffisiyentlarning barchasi manfiy bulsa, masala optimal yechimga ega bulmaydi yoki max _j ustunda birorta xam musbat element katnashmasa, berilgan chizikli programmalash masalasining bazis yechimi mavjud bulishi mumkin, optimal yechimi mavjud bulmaydi. Simpleks usul algoritmi bu xolda xam takrorlanadi. Buni misolda tushuntirish va sun’iy bazis usulini afzalliklarini kursatish kerak. Bu talabalarga mustakil ishlash uchun koldirildi.


Mustakil yechishga doir masalalalar

Kuyidagi chizikli programmalash masalasi yechilsin.

1. 2.

3. 4.