Chiziqli dasturlash masalasini yechishning simpleks usuli

Chiziqli dasturlash masalasini yechishning simpleks usuli. Payqash mumkinki, yechimlar ko’pburchagining shunday burchak nuqtasi mavjudki, bu nuqtada chiziqli funksiya optimal qiymatga ega bo’ladi. Yechimlar ko’pburchagining har bir burchak nuqtasiga birorta tayanch yechim mos keladi.

Tayanch yechim m ta chiziqli bog’lanmagan vektorlar sistemasi orqali aniqlanib, bu sistemada n ta A₁,A₂,...,A_n vektorlar qatnashadi. Optimal yechimni topish uchun faqat tayanch yechimlar tekshiriladi. Bunday masalada tayanch yechimlar sonining yuqori chegarasi Cm guruhlashlar soni bilan aniqlanadi. m va n lar katta sonlar bo’lganda optimal yechimni, hamma tayanch yechimlarni saralab (tekshirib) topish juda katta murakkablikka olib keladi. Shuning uchun, biror tartiblangan sxema bo’yicha bir tayanch yechimdan ikkinchi tayanch yechimga o’tish algoritmiga ega bo’lishga to’g’ri keladi. Bunday sxema bo’lib, simpleks usul hisoblanadi.

Chiziqli dasturlash masalasini simpleks usul bilan yechishga ko’pincha rejani (yechimni) ketma-ket yaxshilash usuli ham deb yuritiladi. Bunday atalishida usulning asosiy g’oyasi, quyidagi ketma-ket amalga oshiriladigan qadamlardir:

1. 
   qadam, boshlang’ich mumkin bo’lgan yechim topiladi;
   
2. 
   qadam, topilgan yechimning optimalligi tekshiriladi;
   
3. 
   qadam, yechim optimal bo’lmasa, 2-qadamda optimal yechimga yaqinroq boshqa mumkin bo’lgan yechimga o’tiladi. Keyin, yana 2-qadamga va hakozo optimal yechim olinguncha davom ettiriladi. Masala yechimga ega bo’lmasa yoki maqsadli funksiya yechimlar ko’pburchagida chegaralanmagan bo’lsa, simpleks usul bilan yechish jarayonida buni aniqlash imkoniyati yaratiladi.
   

Bazis rejani topish. Quyidagi chiziqli dasturlash masalasi qo’yilgan bo’lsin: z = c₁ x₁ + c₂x₂ +... + c_nx_n chiziqli funksiyaning

«11 ^x1 + ^a12 ^x2 + ... + ^a1n^xn = К ^a21 ^x1 + «22 ^x2 + ... + ^a2n^xn = К

a_m1 x + a_m2x₂ +... + ax_n = b_m, x,. > 0 (j = 1,2,...,n)

m1 1 m2 2 mn n m “ j

cheklash shartlarini qanoatlantiruvchi minimum qiymatini topish talab etiladi. Bunda b_} > 0, (j = 1,2,..., m). Bunday qo’yilgan masalaga chiziqli dasturlashning

kanonik masalasi deyiladi.

Cheklash shartlari m ta vektorlar bo’lsin. Bu holda

^Z = ^C1 ^x1 + ^C2^x2 + ... + ^Cn^xn , (5)

chiziqli funksiyaning

^a11 ^x1 + ^a12 ^x2 + ... + ^a1n^xn = К ^a21 ^x1 + ^a22 ^x2 + ... + ^a2n^xn = К

⁽⁶⁾