Buxoro davlat universiteti

(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.