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

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.
2.Simpleks usulining dasturiy ta’minoti.

Oldingi paragraflarda biz chiziqli dasturlash masalalari, chiziqli dasturlash masalasini echishning simpleks usuli, uning algoritmi bilan tanishgan edik. Endi ana shu simpleks usuli algoritmiga asosan uning dasturiy ta’minotini hosil qilishni ko’rib chiqamiz.

Ma’lumki, simpleks usuli bo’yicha bir nechta jadvallar hosil qilinadi. Ana shu jadvallarda simpleks usuli uchun kerakli ma’lumotlar kiritiladi. Masalan, 3 ta no’malumli bo’lgan holdagi chiziqli dasturlash masalasi quyidagi ko’rinishga ega:
Z_mах =c₁x₁+c₂x₂+ c₃ x₃
a₁₁x₁ + a₁₂x₂ + a₁₃ x₃  b₁ ,
a₂₁x₁ + a₂₂x₂ + a₂₃ x₃  b₂ , (2.3.1)
a₃₁x₁ + a₃₂x₂ + a₃₃ x₃  b₃ ,
х_{1 , 2 ,3}  0
Ushbu tengsizliklar sistemasini tenglamalar sistemasiga keltirish uchun qo’shimcha o’zgaruvchilar kiritganda so’ng u quyidagi ko’rinishga ega bo’ladi:
a₁₁x₁ + a₁₂x₂ + a₁₃ x₃ + y₁ = b₁ ,
a₂₁x₁ + a₂₂x₂ +a₂₃ x₃ + y₂ = b₂ ,
a₃₁x₁ + a₃₂x₂ + a₃₃ x₃ + y₃ = b₃ . (2.3.2)
Z_mах = c₁x₁+c₂x₂+ c₃ x₃ +c₄ y₁+c₅ y₂+ c₆ y₃ =
=c₁x₁+c₂x₂+ c₃ x₃ +0y₁+0y₂+0y₃ .

Endi (2.3.2) da berilganlarni simpleks jadvalga joylashtirsak, u quyidagi ko’rinishga keladi :

2.3.1-jadval

Bazis o’zgaruv-chilar	Cj	Bi		х1		х2		x3
				с1		с2		c3
Y1	С4	b1		a11		a12		a13
Y2	с 5	b2		a21		a22		a23
Y3	С6	b3		a31		a32		a33
Zj - Cj			0		- с1		- с2		- сn

Ana shu jadvalni biz DELPHI formasida yaratamiz. Buning uchun Delphining Additional komponentlar palitrasidagi Stringgrid komponentasidan foydalanamiz. Dasturda ishlayotganda o’zgaruvchilar o’rnida aniq sonlar qo’yiladi. Shuning uchun quyidagi misolni qaraymiz.

Z_mах =x₁+2x₂+ 3x₃