Mavzu: Chiziqli programmalash va simpleks usuli

Cj

Bi

x1

x2

…

xn

y1

y2

…

ym

s1

s2

…

sn

s n+1 = 0

sn+2 = 0

…

sm = 0

y1

sn+1

b1

a11

a12

…

a1n

1

0

…

0

y2

s n+2

b2

a21

a22

…

a2n

0

1

…

0

…

…

…

…

…

…

…

…

…

…

…

…

ym

sm

bm

am1

am2

…

amn

0

0

…

1

Zj - Cj

0

- s1

- s2

…

- sn

0

0

…

0

Bazis bo’lmagan y₁, y₂, ... , y_m 0 noma’lumlar «Bazis o’zgaruvchilar» ustuniga yoziladi.
Bazismas noma’lumlarning s_n+1, s_n+2, ... , s_m koeffistientlari «S_i» ustuniga yoziladi.
b₁, b₂, ... , b_m ozod hadlar «B_i» ustuniga yoziladi.
Z_max =c₁x₁+c₂x₂+...+c_nx_n+0y₁+0y₂+...+0y_m maqsad funksiyaning koeffistientlari Z_j - C_j qatorga qarma - qarshi ishora bilan yoziladi. Bu qator indeks qator deb yuritiladi.
CHDM ning simpleks jadvalida Z_j - C_j indeks qatoridagi hamma noma’lumlarning koeffistientlari musbat bo’lsa masala optimal yechimga ega bo’ladi. Simpleks usuli bilan CHDMni optimal yechimini topishda Z_j - C_j indeks qatoridagi hamma noma’lumlarning koeffistientlari musbat ishoraga keltirish maqsad qilib qo’yiladi.
Simpleks jadvalida Z_j - C_j indeks qatoridagi noma’lumlarining koeffistientlaridan bittasi yoki bir nechtasi manfiy bo’lganida hal qiluvchi elementni tanlashda quyidagi munosabatlar amalga oshishi mumkin.
Simpleks jadvalida hal qiluvchi ustunni (HQU) tanlash.
Agar Z_j - C_j indeks qatoridagi x₁, x₂, ... , x_n noma’lumlarning s₁, s₂, ..., s_n koeffistientlardan birortasi manfiy ishorali son bo’lsa, shu manfiy ishorali son to’rgan ustun HQU bo’ladi.
Agar Z_j - C_j indeks qatorida bunday manfiy sonlar bir nechta bo’lsa, u vaqtda HQUni tanlash uchun shu manfiy sonlarning absolyut qiymatlari bo’yicha eng kattasi olinadi. Bu sonlar ichida, ulardan bir nechtasi bir - biriga teng bo’lsa, u holda ulardan hohlagan birini olib bosh ustun uchun tanlanadi.
Simpleks jadvalida hal qiluvchi satrni (HQS) tanlash.
Simpleks jadvalida HQSni tanlash uchun B_i ozod hadlar ustunidagi hamma sonlarni (agar ularning ishorasi bir xil bo’lsa) HQUdagi mos kelgan sonlarga bo’lib, ulardan eng kichigi tanlanadi. Bu qiymat simpleks jadvadagi ustunga yoziladi. Bunday kichik sonlar bir nechta bo’lsa, ulardan xohlagan birini HQS qilib tanlash mumkin.
Simpleks jadvalini hal qiluvchi elementi (HQE) .
Simpleks jadvalidagi HQU va HQS ning kesishgan kattagidagi son hal qiluvchi element (HQE) bo’ladi.
Yangi simpleks jadvaliga o’tish.
Hal qiluvchi ustun, hal qiluvchi satr va hal qiluvchi element topilgach yangi simpleks jadvalidagi hamma sonlar Jordan chiqarish usuli yordamida topiladi, ya’ni:
hal qiluvchi satrdagi hamma elementlar hal qiluvchi elementga bo’linadi va ishorasi o’zgartirilmasdan yoziladi;
hal qiluvchi ustundagi qolgan hamma elementlar o’rniga nol yoziladi;
qolgan hamma elementlar quyidagi to’g’ri to’rtburchak formulasi yordamida topiladi:
yoki . (Bu yerda i ≠ r,j≠ k)
a_rk element o’rnida hosil qilinadigan b_rk elementni to’g’ri to’rtburchak formulasi bilan topish uchun:Jordan jadvalidan fragment 2.1.3-jadval

…	…	j- hal qiluvchi ustun	…	k-ustun	…
…	…	…	…	…	…
i–hal qiluvchi satr	…	[ aij ] hal qiluvchi element	…	aik (i -satr va k –ustunda joylashgan element)	…
…	…	…	…	…	…
r – satr	…	arj r-satr va j –ustunda joylashgan element	…	ark r-satr va k –ustunda joylashgan element	…
…	…	…	…	…	…

Bu jarayon Z_j-C_j indeks qatoridagi hamma noma’lumlarning koeffistientlari musbat bo’lguncha davom ettiriladi.