|
Oliy ta’lim,fan va innovatsiyalar vazirligi toshkеnt axborot tеxnologiyalari univеrsitеti “Algoritmlarni loyihalash
|
| bet | 5/7 | | Sana | 22.01.2024 | | Hajmi | 149,09 Kb. | | #142747 |
Bog'liq Mustaqil ish Mavzu Chiziqli dasturlash masalalarini yechishda s (1)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 y1, y2, ... , ym 0 noma’lumlar «Bazis o’zgaruvchilar» ustuniga yoziladi.
Bazismas noma’lumlarning sn+1, sn+2, ... , sm koeffistientlari «Si» ustuniga yoziladi.
b1, b2, ... , bm ozod hadlar «Bi» ustuniga yoziladi.
Zmax =c1x1+c2x2+...+cnxn+0y1+0y2+...+0ym maqsad funksiyaning koeffistientlari Zj - Cj qatorga qarma - qarshi ishora bilan yoziladi. Bu qator indeks qator deb yuritiladi.
CHDM ning simpleks jadvalida Zj - Cj indeks qatoridagi hamma noma’lumlarning koeffistientlari musbat bo’lsa masala optimal yechimga ega bo’ladi. Simpleks usuli bilan CHDMni optimal yechimini topishda Zj - Cj indeks qatoridagi hamma noma’lumlarning koeffistientlari musbat ishoraga keltirish maqsad qilib qo’yiladi.
Simpleks jadvalida Zj - Cj 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 Zj - Cj indeks qatoridagi x1, x2, ... , xn noma’lumlarning s1, s2, ..., sn koeffistientlardan birortasi manfiy ishorali son bo’lsa, shu manfiy ishorali son to’rgan ustun HQU bo’ladi.
Agar Zj - Cj 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 Bi 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)
ark element o’rnida hosil qilinadigan brk 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 Zj-Cj 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:
Zmах =c1x1+c2x2+ c3 x3
a11x1 + a12x2 + a13 x3 b1 ,
a21x1 + a22x2 + a23 x3 b2 , (2.3.1)
a31x1 + a32x2 + a33 x3 b3 ,
х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:
a11x1 + a12x2 + a13 x3 + y1 = b1 ,
a21x1 + a22x2 +a23 x3 + y2 = b2 ,
a31x1 + a32x2 + a33 x3 + y3 = b3 . (2.3.2)
Zmах = c1x1+c2x2+ c3 x3 +c4 y1+c5 y2+ c6 y3 =
=c1x1+c2x2+ c3 x3 +0y1+0y2+0y3 .
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.
Zmах =x1+2x2+ 3x3
|
| |
