Chiziqli dasturlash masalalarini yechishning jadval usuli
Reja:
Jadvalni to`ldirish qoidasi.
Masalani yechishning algoritmi.
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.
Tengsizliklar sistemasi kanonik ko`rinishga keltiriladi.
Tenglamalar sistemasida bazis o`zgaruvchilar aniqlab olinadi. Bunda bazis o`zgaruvchilarning qiymati nomanfiy bo`lishi shart.
Maqsad funksiyasi erkin o`zgaruvchilar orqali ifodalab olinadi.
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:
Jadvalning birinchi ustuniga bazis o`zgaruvchilar qo`yiladi. Shuningdek bu yerga maqsad funksiyasi ham qo`yiladi.
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.
Do'stlaringiz bilan baham: | 
