Chiziqli dasturlash masalalarini yechishning jadval usuli Reja

Chiziqli dasturlash masalalarini yechishning jadval usuli


Reja:

1. 
   Jadvalni to`ldirish qoidasi.
   
2. 
   Masalani yechishning algoritmi.
   
3. 
   Misol.
   

Chiziqli dasturlash masalasini yechishning asosiy usullaridan biri Simpleks usulidir. Bu usul amerikalik olim Dansek tomonidan yaratilgan bo`lib, oddiy yoki sodda usuldir. Bu usul yordamida masalani yechish algoritmi quyidagichadir.

1. 
   Tengsizliklar sistemasi kanonik ko`rinishga keltiriladi.
   

2. 
   Tenglamalar sistemasida bazis o`zgaruvchilar aniqlab olinadi. Bunda bazis o`zgaruvchilarning qiymati nomanfiy bo`lishi shart.
   

3. 
   Maqsad funksiyasi erkin o`zgaruvchilar orqali ifodalab olinadi.
   

4. 
   Masalaning optimalligi tekshiriladi. Yechim optimal bo`ladi, agarda maqsad funksiyadagi barcha koeffitsientlar musbat bo`lsa. Agar biron bir koeffitsient manfiy bo`lsa, shu koeffitsientdagi o`zgaruvchi bazis deb olinadi va u erkin o`zgaruvchi bilan almashtiriladi.
   

Bu masalani yechishning qulay usullaridan biri jadval usulidir. Simpleks jadvali quyidagicha to`ldiriladi:

1. 
   Jadvalning birinchi ustuniga bazis o`zgaruvchilar qo`yiladi. Shuningdek bu yerga maqsad funksiyasi ham qo`yiladi.
   

2. 
   Jadvalning ikkinchi ustuniga ozod hadlar qo`yiladi. Qolgan ustunlarga esa barcha o`zgaruvchilar qo`yiladi. U holda Simpleks jadvali quyidagi ko`rinishga ega bo`ladi.
   

Bazis o`zgaruvchilar	Ozod hadlar	x1	x2	…………	xn
x1
x2
…………
xn
F

Bu jadval yordamida masalani yehish quyidagicha: f qatoridagi musbat son qidiriladi. Agar barcha koeffitsientlar manfiy bo`lsa, u holda optimal yechim topilgan hisoblanadi. Agarda biron bir koeffitsent musbat bo`lsa, shu koeffitsent turgan ustun bazis deb qabul qilinadi. Basiz o`zgaruvchilardan birontasini erkin o`zgaruvchiga o`tkazish uchun hal qiluvchi ustundagi musbat koeffitsientlarga ozod haddagi koeffitsientlar bo`linadi

va ulardan eng kichigi to`g`risida turgan o`zgaruvchi erkin o`zgaruvchi bo`ladi.