Chiziqli dasturlash masalasini yechishning Simpleks usuli Chiziqli dasturlash masalasi umumiy holda simpleks usulda

Copilot

1. 
   Masalani quyidagi z funksiyasi yordamida ifodalashimiz:
   $$z = c_1x_1 + c_2x_2 + \ldots + c_nx_n$$
   Bu yerda $c_i$ - ko’rsatkichlar, $x_i$ - o’zgaruvchilar.
   
2. 
   Quyidagi masala shartlarini ko’rib chiqamiz:
   

• 
  $$a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n \leq b_1$$
  
• 
  $$a_{21}x_1 + a_{22}x_2 + \ldots + a_{2n}x_n \leq b_2$$
  
• 
  $$\ldots$$
  
• 
  $$a_{m1}x_1 + a_{m2}x_2 + \ldots + a_{mn}x_n \leq b_m$$
  
• 
  $$x_1 \geq 0, x_2 \geq 0, \ldots, x_n \geq 0$$
  

3. 
   Ushbu masaladan quyidagi simpleks jadvalini tuzamiz:
   
4. 
   Jadvaldagi manfiy sonlarni qaraymiz. Agar barcha sonlar musbat bo’lsa, masalaning tayanch echimi topilgan hisoblanadi. Aks holda, manfiy sonlardan birini tanlaymiz. Misol uchun, $l$-satrdagi $a_l$ ozod sonni tanlab olaylik.
   
5. 
   Ozod sonlar va $k$-ustundagi mos koefisientlarni qaraymiz. Agar ularning ishoralari bir xil bo’lsa, ozod sonlarni mos koefisientlarga bo’lamiz.
   
6. 
   Hosil bo’lgan nisbatlarning eng kichigini tanlab olamiz:
   $$p = \min \left(\frac{a_{i1}}{a_{i1}}, \frac{a_{i2}}{a_{i2}}, \ldots, \frac{a_{in}}{a_{in}}\right)$$
   Bu erda $p$ - tanlab olingan juftliklar soni.
   
7. 
   $p$-ga mos keluvchi $k$-ustundagi element bosh element deyiladi. Agar bosh element $j$-satrga mos kelsa, $a_{jk}$ - bosh element bo’ladi, $j$-satr hal qiluvchi satr deyiladi.
   
8. 
   Jadvalni yangilab turamiz: