Chiziqli dasturlash masalalarini yechish texnologiyasi

Eslatma 1. Tizimning qo'llab-quvvatlovchi yechimlari soni chekli bo'lgani uchun chiziqli dasturlash masalasini yechish jarayoni ham chekli bo'ladi.
Eslatma 2. Agar ichida chiziqli dasturlash muammosi Z maqsad funksiyasining minimalini topishi kerak, keyin 𝐹 = −𝑍 funksiya kiritiladi . Tenglik tufayli 𝑍 + 𝐹 = 0, Z _min = −𝐹 _max va shuning uchun F funksiyani maksimallashtirish masalasini yechish bilan bir vaqtda Z funksiyasini minimallashtirish masalasini hal qilamiz .
Simpleks usuli yordamida chiziqli dasturlash masalalarini echishning asosi bir tayanch rejani boshqasi bilan almashtirish usuli bo'lib, bunda maqsad funksiyasi o'zining optimal qiymatiga etadi. Agar boshlang'ich baza ma'lum bo'lsa, bu almashtirish mumkin.
Misol tariqasida Excel elektron jadval protsessoridan foydalangan holda simpleks usuli texnologiyasini ko'rib chiqamiz .
2-vazifa. 7-variant.
A₁₁=11, A₁₂=10, A₂₁=12, A₂₂=8, A₃₁=4, A₃₂=3, A₄₁=6, A₄₂=6, A₅₁=5, A₅₂=4
B₁=18, B₂=20, B₃=16, B₄=21, B₅=30
C₁=17, C₂=20

Yechish: shartlarni kiritish uchun forma yaratish (4.1-rasm);

• 
  B1 : F3 diapazonidagi katakchalarga tizim tenglamalarining koeffitsientlarini yozing;
  
• 
  A1 : A3 diapazonidagi katakchalarga tenglamalar tizimining erkin koeffitsientlarini yozing;
  
• 
  A4:F4 diapazonidagi katakchalarga maqsad funksiyasining F4 koeffitsientlarini yozing;
  
• 
  B1 : F3 katak diapazonining eng katta musbat elementi B2 katakda, shuning uchun B ustunida ruxsat beruvchi;
  
• 
  B ustunida faollashtiruvchi elementni tanlang, masalan , B2. Agar u 1 ga teng bo'lsa, ikkinchi qator o'zgarishsiz qoldiriladi; agar bo'lmasa, chiziq elementlarini tanlangan yoqish elementining qiymatiga bo'lish kerak, bu 1 ga teng bo'ladi;
  

tanlangan B ustunining qolgan elementlarini tenglashtiruvchi amallarni bajarish uchun nol.

Buning uchun biz A 6 : F9 katakchalari oralig'ida yangi simpleks jadvalini tuzamiz, unda:

• 
  A7: F7 kataklari oralig'ida A2: F2 katakchalari elementlarining qiymatlarini nusxalash;
  
• 
  B6 katakka =B1 - B2 formulasini yozing va markerni sudrab A 6: F6 kataklariga nusxa ko'chiring;
  
• 
  va markerni sudrab A 8: F8 kataklariga ko'chiring ;
  
• 
  B9 katakka = B4 - B2 3 formulasini yozing va markerni sudrab A 9: F9 kataklariga nusxa ko'chiring. Natijada biz ikkinchi simpleks jadvalini olamiz (4.2-rasm).
  

B6 : F8 kataklari diapazonidagi eng katta musbat element B9 yacheykada, shuning uchun B ustuni hal qilinmoqda . Quyidagi amallarni bajaring:

• 
  element sifatida B9 katakchasini ( 2 - raqam ) tanlang ;
  
• 
  B13 katakchasiga = B9 / 2 formulasini yozing, hal qiluvchi element 1 ga teng bo'ladi;
  
• 
  A13 : B13 katakchalar diapazoniga tortib, ushbu formuladan nusxa oling ;
  
• 
  faollashtiruvchi B ustunining qolgan elementlari nolga teng bo'lishi kerak, B14 katakchaga ==B9-B13*12formulasini yozing va markerni sudrab A 14 : H14 katakchalar diapazoniga ko'chiring;
  
• 
  B15 katakka formula =B10-B13*(-44)va usulni yozing
  

A15 : H15 katakchalar diapazoniga ko'chirish uchun markerni "tortib torting" ;

• 
  B16 katakchaga =B11-B13*(-66)formulasini yozing va markerni sudrab olish usulidan foydalanib, uni hujayralar diapazoniga ko'chiring
  

A 13: H13. Biz uchinchi simpleks jadvalini olamiz (4.3-rasm).

x₁ = 9, 5, 𝑥 ₂ = 3,5, 𝑥 ₃ = 0, 𝑥 ₄ = 0, 𝑥 ₅ = 34
x₁=1,66667, x₂=0, x₃=9,33333 , x₄=11 ,
F_max=17x₁+20x₂=17*1.66667 + 20*0=28.33339