Mustaqil ish Mavzu: Chiziqli dasturlash masalalarini yechishda simpleks usul algoritmi va uning tahlili

x_i і0 (i=1,2,…m) (2.1.2)
Masaladagi b) shart uning maqsadini aniqlaydi. Demak masalaning maqsadi mahsulotlarni realizatciya qilishdan korxonaning oladigan umumiy daromadini maksimallashtirishdan iborat va uni
y = c₁x₁ +c₂x₂+ … + c_mx_m (2.1.3)
chiziqli funksiya orqali ifodalash mumkin. Shartga ko’ra y®max. Bu shartni Y_max ko’rinishda belgilaymiz.
Chiziqli dasturlash masalasi umumiy holda 2.1.1-1.1.3 kabi ifodalanadi.
2.1.1-1.1.2 shartlarni qanoatlantiruvchi noma`lumlarning shunday qiymatlarini topish kerakki, ular (2.1.3) chiziqli funksiyaga minimal (maksimal) qiymat bersin. Masalaning (2.1.1) va (2.1.2) shartlari uning chegaraviy shartlari deb, (2.1.3) chiziqli funksiya esa masalaning maqsadi yoki maqsad funksiyasi deb ataladi.
Masaladagi barcha chegaralovchi shartlar va maqsad funksiya chiziqli ekanligi ko’rinib turibdi. Shuning uchun ham (2.1.1)–(2.1.3) masala chiziqli dasturlash masalasi deb ataladi.
Konkret masalalarda (2.1.1) shart tenglamalar sistemasidan, «і» yoki «Ј» ko’rinishdagi tengsizliklar sistemasidan yoki aralash sistemadan iborat bo’lishi
mumkin. Lekin ko’rsatish mumkinki, (2.1.1)–(2.1.3) ko’rinishdagi masalani osonlik bilan quyidagi ko’rinishga keltirish mumkin:

(2.1.4)
x_{1 і} 0, x_{2 і} 0, …, x_{n і} 0, (2.1.5)

Y_min = c₀ + c₁x₁ + c₂x₂+ … + c_nx_n (2.1.6)
(2.1.4)-(2.1.6) ko’rinish chiziqli dasturlash masalasining kanonik ko’rinishi deb ataladi. (2.1.4)–(2.1.6) masala vektorlar yordamida quyidagicha ifodalash mumkin:
P₁x₁ + P₂x₂+ … + P_nx_n = P₀ (2.1.7)
X і 0 (2.1.8)
Y_min = CX (2.1.9)



bu yerda
S = (C₁, C₂, …, C_n) – vektor–qator.
X = (X₁, X₂, …, X_n) – vektor–ustun.
(2.1.4)-(2.1.6) masalaning matritca ko’rinishdagi ifodasi quyidagicha yoziladi:
AX = P₀, (2.1.10)
X і 0, (2.1.11)
Y_min = CX, (2.1.12)
bu erda S = (C₁, C₂, …, C_n) – qator vektor, A = (a_ij) – (4) sistema koeffitcientlaridan tashkil topgan matritca; X = (X₁, X₂, …, X_n) va P₀ = (b₁, b₂, …, b_n) – ustun vektorlar.
(2.1.4)-(2.1.6) masalani yig’indilar yordamida ham ifodalash mumkin:

(2.1.13)

Chiziqli dasturlash masalalarini yechishni simpleks usuli bir tayanch rejasidan boshqa tayanch rejasiga o’tishga asoslangan bo’lib, qaysikim bu yerda maqsad funksiyasini qiymati oshib boradi. Simpleks usulining mohiyati shundan iboratki, dastavval CHDMdagi barcha shartlarni qanoatlantiruvchi mumkin bo’lgan tayanch reja topiladi.
Boshlang’ich tayanch reja chekli sondagi etap (simpleks)dan keyin optimal rejani hosil qilish yo’lini ko’rsatadi va har bir navbatdagi simpleks oldingisiga nisbatan optimal rejaga yaqinroq rejani beradi. Masalani yechish jarayoni optimal yechim topilguncha yoki masalaning maqsad funksiyasi chekli maksimum (minimum)ga ega emasligi aniqlanguncha davom ettiriladi.
Demak, CHDM simpleks usuli bilan yechilganda, berilgan masalaning barcha shartlarini qanoatlantiruvchi boshlang’ich tayanch reja topiladi. Bu boshlang’ich tayanch rejaga asoslanib chekli sondagi simplekslar (bir simpleks jadvalidan, navbatdagi simpleks jadvaliga o’tish) bilan navbatdagi yangi tayanch rejlarni topish va ularning optimalligini tekshirib borish, masalaning optimal yechimga ega ekanligi aniqlanguncha davom ettiriladi.
Simpleks usuli CHDMning quyidagi xossalariga asoslangan:
-agar masala ekstremumga ega bo’lsa u yagona bo’ladi, ya’ni maksimum yoki minimumlardan biri bo’ladi.