x1- x2 =3
-5x1-3x2+x3=-10
x1+6x2-x3=5
xjі0, j=1,2,3
Z=8x1+4x2-2x3 ®max
Ye ch i sh. Ikki yoqlama masalani tuzamiz. U quyidagi ko‘rinishda bo‘ladi.
y1+y2-5y3+y4≥8
- y2-3y3+6y4≥4
2y1 +y3 - y4≥-2
F=4y1+3y2-10y3+5y4 ®min
Masala shartlarini simpleks jadvalga kiritamiz.
BO‘
|
1
|
SO‘
|
-y1
|
-y2
|
-y3
|
-y4
|
y5
|
-8
|
-1
|
-1
|
5
|
-1
|
y6
|
-4
|
0
|
1
|
3
|
-6
|
y7
|
2
|
-2
|
0
|
-1
|
1
|
F
|
0
|
-4
|
-3
|
10
|
-5
|
F qatorda musbat element (10 soni) mavjud, shu sabab bu son turgan ustun hal qiluvchi bo‘ladi. Bu ustunda ikkita musbat son mavjud, ulardan kattasini 5 sonini olamiz va F qator elementlarining shu qator elementlariga nisbatini qaraymiz, undan musbatlarining eng kichigini tanlaymiz, unga mos element hal qiluvchi bo‘ladi, ya'ni
Min|-4/-1; -3/-1; 10/5; -5/-1|=min{4; 3; 2; 5}=2
Demak, hal qiluvchi element 5 soniga teng. Simpleks almashtirish bajarib quyidagi jadvalga ega bo‘lamiz:
BO‘
|
1
|
SO‘
|
-y1
|
-y2
|
-y5
|
-y4
|
y3
|
-8/5
|
-1/5
|
-1/5
|
1/5
|
-1/5
|
y6
|
4/5
|
3/5
|
8/5
|
-3/5
|
-27/5
|
y7
|
2/5
|
-11/5
|
-1/5
|
1/5
|
4/5
|
F
|
16
|
-2
|
-1
|
-2
|
-3
|
F qator elementlari barchasi manfiy, shu sabab ozod hadlar ustunini qaraymiz, unda manfiy element bor, u -8.5. Bu qator hal qiluvchi bo‘ladi. Yana F qator elementlarining shu qator elementlariga nisbatini qaraymiz, undan musbatlarining eng kichigini tanlaymiz, unga mos element hal qiluvchi bo‘ladi, ya'ni
Min|-2/-1/5; -1/1/5; -2/-1/5; -3/-1/5|=min{10; 5; -10; 15}=5.
Demak, hal qiluvchi element -1/5. Simpleks almashtirish bajarib quyidagi jadvalga ega bo‘lamiz:
BO‘
|
1
|
SO‘
|
-y1
|
-y3
|
-y5
|
-y4
|
y2
|
8
|
1
|
-5
|
-1
|
1
|
y6
|
-12
|
-1
|
8
|
1
|
-7
|
y7
|
2
|
-2
|
-1
|
0
|
1
|
F
|
24
|
-1
|
-5
|
-3
|
-2
|
F qator elementlari barchasi manfiy, shu sabab ozod hadlar ustunini qaraymiz, unda manfiy element bor, u -12. Bu qator hal qiluvchi bo‘ladi. Yana F qator elementlarining shu qator elementlariga nisbatini qaraymiz, undan musbatlarining eng kichigini tanlaymiz, unga mos element hal qiluvchi bo‘ladi, ya'ni
Min|-1/-1; -5/8; -3/1; -2/7|=min{1; -5/8; -3; 2/7}=2/7.
Demak, hal qiluvchi element -7. Simpleks almashtirish bajarib quyidagi jadvalga ega bo‘lamiz:
BO‘
|
1
|
SO‘
|
-y1
|
-y3
|
-y5
|
-y6
|
y2
|
44/7
|
6/7
|
-27/7
|
-6/7
|
1/7
|
y4
|
12/7
|
1/7
|
-8/7
|
-1/7
|
-1/7
|
y7
|
2/7
|
-15/7
|
1/7
|
1/7
|
1/7
|
F
|
192/7
|
-5/7
|
-51/7
|
-23/7
|
-2/7
|
Jadvaldan ko‘rinib turibdiki bu olingan plan optimal bo‘ladi. Demak, ikkilangan masalaning optimal yechimi y*=(0; 44/7; 0; 12/7; 0; 0; 2/7), Fmin=192/7.
Asosiy masala bilan ikkilangan masala o‘zgaruvchilari orasidagi bog‘lan-ishga ko‘ra ya'ni xI↔y5; x2↔y6; x3↔y7; x4↔y1; x5↔y2; x6↔y3; x7↔y4 asosiy masala yechimini ham topish mumkin , ya'ni x*=(23/7; 2/7; 0; 5/7; 0; 5/7; 0) va Zmax=Fmin bo‘lgani uchun Zmax=192/7.
2.Simpleks jadval usuli
Simpleks usuli chiziqli dasturlash masalasini yechishning asosiy usullaridan biri bo‘lib, ketma-ket yaqinlashish usuli yordamida x1,x2, . . .xn o‘zgaruvchilarning shunday optimal qiymatini topadiki, bu qiymatlar maqsad funksiyasiga maksimal (yoki minimal) qiymat beradi.
Quyidagi chiziqli dasturlash masalasi berilgan bo‘lsin:
Masalani yechish uchun simpleks jadval quramiz va simpleks usuli g‘oyasini berish uchun berilgan masalani quyidagicha kanonik formada yozamiz.
Bu yerda xn+i - ozod o‘zgaruvchilar deyiladi. Ularni qulaylik, hamda boshqa o‘zgaruvchilardan farqlash uchun mos ravishda y1,y2, . . .ym deb belgilaymiz va yana quyidagi belgilashlarni kiritamiz bi0=bi; bi,j=ai,j; b0j=cj. Bu belgilashlar asosida quyidagi simpleks jadval deb ataluvchi jadvalni tuzamiz.
BO‘
|
1
|
-x1
|
-x2
|
. . .
|
-xs
|
. . .
|
-xn
|
y1
|
b10
|
b11
|
b12
|
. . .
|
b1s
|
. . .
|
b1n
|
y2
|
b20
|
b21
|
b22
|
. . .
|
b2s
|
. . .
|
b2n
|
. . .
|
. . .
|
. . .
|
. . .
|
. . .
|
. . .
|
. . .
|
. . .
|
ys
|
br0
|
br1
|
br2
|
. . .
|
brs
|
. . .
|
brn
|
. . .
|
. . .
|
. . .
|
. . .
|
. . .
|
. . .
|
. . .
|
. . .
|
ym
|
bm0
|
bm1
|
bm2
|
. . .
|
bms
|
. . .
|
bmn
|
Z
|
b00
|
b01
|
b02
|
. . .
|
b0s
|
. . .
|
b0n
|
Chiziqli dasturlash masalasini simpleks usul yordamida yechish ikki bosqichdan iborat:
1.Boshlang‘ich tayanch planni topish.
2.Tayanch planlar ichidan masalaning optimal planini topish.
Masalaning tayanch planini tuzish.
Boshlang‘ich tayanch planni topish quyidagi algoritm bo‘yicha bajariladi:
1.Simpleks jadvaldan hal qiluvchi elementni topish:
1.1.Hal qiluvchi elementni topish oldin hal qiluvchi ustunni topishdan boshlanadi. Buning uchun ozod hadlar ustuniga qaraladi. Agar ozod xadlar ustunidagi elementlar hammasi musbat bo‘lsa, bu boshlang‘ich plan tayanch plan bo‘ladi va ikkinchi etapga o‘tiladi. Agar manfiy element mavjud bo‘lsa, ulardan modul bo‘yicha eng kattasi tanlanadi (agar bitta bo‘lsa shu element o‘zi olinadi). Misol uchun aytaylik bu element br0 bo‘lsin. Shu br0 element turgan r satr qaraladi. Agar satr elementlaridan hammasi musbat bo‘lsa, masalaning yechimi mavjud bo‘lmaydi (bu holda hisoblashlar shu joyda to‘xtatiladi). Agar satrda manfiy element mavjud bo‘lsa, ulardan modul bo‘yicha eng kattasi tanlanadi (agar bitta bo‘lsa o‘zi olinadi). Shu element turgan ustun hal qiluvchi ustun deyiladi. Misol uchun bu s-chi ustun bo‘lsin.
1.2.Hal qiluvchi satr topiladi. Ozod xadlarni hal qiluvchi ustun elementlariga bo‘lib chiqiladi va ulardan musbatlarining eng kichigi tanlanadi, ya'ni
.
Aytaylik, bu nisbatlar ichida musbatlarning eng kichigi br0/brs bo‘lsin. U holda shu brs element turgan satr hal qiluvchi satr deyiladi, brs elementning o‘zi esa hal qiluvchi element bo‘ladi.
2.Hal qiluvchi ustun va satr o‘zgaruvchilari o‘rinlari almashtiriladi, (ya'ni xs va ys yangi jadvalda o‘rinlari almashadi).
3.Jadvalda simpleks almashtirish bajariladi.
3.1.Hal qiluvchi ustun elementlari hal qiluvchi elementga bo‘lib chiqilib yangi jadvalga yoziladi, ya'ni .
3.2.Hal qiluvchi satr elementlari hal qiluvchi elementga bo‘lib chiqilib yangi jadvalga yoziladi, ya'ni .
3.3.Hal qiluvchi element 1 ga tenglashtirilib o‘ziga bo‘linadi, ya'ni .
3.4.Yangi simpleks jadvalning qolgan elementlari quyidagi formula orqali topiladi.
ёки
Yangi jadvalda bґij -elementni hisoblashda eski jadvaldan bij, bis ,brj, brs elementlarini topish quyidagicha bo‘ladi:
bij - bґij elementning eski jadvaldagi unga mos element;
bis -bij element turgan satr bilan br hal qiluvchi element ustuni kesishmasidagi element;
brj -bij element turgan ustun bilan brs hal qiluvchi element satri kesishmasidagi element;
brs - hal qiluvchi element.
BO‘
|
1
|
-x1
|
-x2
|
. . .
|
-yr
|
. . .
|
-xn
|
y1
|
b’10
|
b’11
|
b’12
|
. . .
|
b’1s
|
. . .
|
b’1n
|
y2
|
b’20
|
b’21
|
b’22
|
. . .
|
b’2s
|
. . .
|
b’2n
|
. . .
|
. . .
|
. . .
|
. . .
|
. . .
|
. . .
|
. . .
|
. . .
|
xs
|
b’r0
|
b’r1
|
b’r2
|
. . .
|
b’rs
|
. . .
|
b’rn
|
. . .
|
. . .
|
. . .
|
. . .
|
. . .
|
. . .
|
. . .
|
. . .
|
ym
|
b'm0
|
b’m1
|
b’m2
|
. . .
|
b’ms
|
. . .
|
b’mn
|
Z
|
b’00
|
b’01
|
b’02
|
. . .
|
b’0s
|
. . .
|
b’0n
|
4.Yangi topilgan simpleks jadvalda tayanch plan mavjud bo‘lsa ikkinchi bosqichga, ya'ni optimal planni topishga o‘tiladi, aks holda yuqoridagi jarayon yangi jadval uchun toki tayanch plan topilguncha qayta takrorlanadi.
Masalaning optimal planini topish.
Agar 1 bosqichdan olingan tayanch planning simpleks jadvaldagi Z-satr elementlari (ozod hadi bґ00 dan tashqari) hammasi musbat bo‘lsa, bu olingan boshlang‘ich tayanch plan yagona va u masalaning optimal plani (echimi) bo‘ladi. Agar Z satrdagi hamma musbat elementlardan kamida bittasi no‘lga teng bo‘lsa, u holda masalaning cheksiz ko‘p optimal plani mavjud bo‘ladi. Agar Z satrdagi elementlardan hech bo‘lmaganda bittasi manfiy bo‘lsa, optimal plan quyidagi algoritim bo‘yicha topiladi:
1. Hal qiluvchi elementni topish.
1.1.Hal qiluvchi ustun topiladi. Z-qatordagi manfiy elementlarning modul bo‘yicha eng kattasi (bitta bo‘lsa o‘zi) tanlanadi. Shu element turgan ustun hal qiluvchi ustun bo‘ladi.
1.2.Hal qiluvchi satr topiladi. Ozod hadlar elementlari hal qiluvchi ustun elementlariga bo‘lib chiqiladi va ulardan musbatlarining eng kichigi olinadi, ya'ni birinchi bosqichning 1.2 punktidagi kabi. Bu songa mos keluvchi ustundagi element hal qiluvchi element va shu element turgan satr esa hal qiluvchi satr bo‘ladi.
2.Hal qiluvchi satr va ustun o‘zgaruvchilari o‘z joylarini almashtiradi.
3.Jadvalda simpleks almashtirish bajariladi. Simpleks almashtirish 1- bosqichdagi 3.1, 3.2, 3.3, 3.4 punktlar kabi bajariladi.
4.Yangi topilgan jadvalning Z satri qaraladi. Agar Z qatordagi hamma elementlar musbat bo‘lsa, olingan oxirgi plan masalaning optimal plani bo‘ladi. Aks holda yuqoridagi 1,2,3 punktlar yana takrorlanadi, toki optimal plan topilguncha.
Izoh: Chiziqli dasturlash masalasida, agar maqsad funksiyasining minumimi izlansa yuqoridagi 1-chi bosqich to‘lig‘icha o‘rinli bo‘lib, 2-bosqichda esa faqat Z -qator elementlari manfiy holatga keltirilishi kerak, ya'ni teskari holat bo‘ladi.
1-misol
z=5x1-x2+3x3
chiziqli funksiyaga maksimum qiymat beruvchi
x1+x2+x3Ј2
4x1+2x2+x3Ј3
x1-x2+2x3Ј-1
-3x1+2x2-2x3Ј5
x1і0, x2 і0,x3і0
chegaraviy tizimning mumkin bo‘lgan yechimlari sohasida noma'lumlar topilsin. Chegaraviy tizimni kanonik ko‘rinishda quyidagicha yozib olamiz:
x1+x2+x3+x4=2
4x1+2x2+x3+x5=3
x1-x2+2x3+x6=-1
-3x1+2x2-2x3+x7=5
x1і0, x2 і0,x3і0
Tenglamada bazis o‘zgaruvchilarni simpleks o‘zgaruvchilardan farqlash uchun х4=у1 , х5=у2 , х6=у3 , х7=у4 belgilashlarni kiritamiz va Simpleks jadval tuzamiz.
So‘
Bo‘
|
1
|
-х1
|
-х2
|
- х3
|
у1
|
2
|
1
|
1
|
1
|
у2
|
3
|
4
|
2
|
1
|
у3
|
-1
|
1
|
-1
|
2
|
у4
|
5
|
-3
|
2
|
-2
|
Z
|
0
|
-5
|
1
|
-3
|
O‘zgaruvchilarning manfiy bo‘lmaslik sharti berilganligini hisobga olib, to‘g‘ridan-to‘g‘ri tayanch yechimni topishga kirishamiz. Ozod hadlar ichida -1 manfiy ishorali koeffitsient bor. Shu qatordan ishorasi manfiy bo‘lgan modul bo‘yicha eng katta elementni topamiz. U х2 ustunidagi -1 elementdir. Qoidaga binoan musbat nisbatlar ichidan eng kichigini topamiz:
+min2/1, 3/2, -1/-1, 5/2}=1/1
Demak, unga mos element х2 ustunidagi -1 element. Bu element hal qiluvchi element bo‘ladi. Endi Simpleks almashtirish qilib, quyidagi jadvalni tuzamiz.
So‘
Bo‘
|
1
|
-х1
|
-y3
|
- х3
|
у1
|
1
|
2
|
1
|
3
|
у2
|
1
|
6
|
2
|
5
|
x2
|
1
|
-1
|
-1
|
-2
|
у4
|
3
|
-1
|
2
|
2
|
z
|
-1
|
-4
|
1
|
-1
|
Bu jadvaldan ko‘rinib turibdiki ozod hadlar musbat, shu sabab tayanch plan mavjud. Endi optimal yechimini topish uchun Z qatoriga qaraymiz. Bu qatorda ikkita manfiy ishorali koeffitsient bor. Ulardan modul bo‘yicha qiymati katta bo‘lgan koeffitsientni tanlab olamiz, u -4 elementidir. Qoidaga binoan hal qiluvchi elementni aniqlab yangi jadval tuzamiz:
+min1/2, 1/6, 1/-1, 3/-1}=1/6
Unga mos element х1 ustunidagi 6 element. Bu element hal qiluvchi element bo‘ladi. Endi Simpleks almashtirish qilib, quyidagi jadvalni tuzamiz.
So‘
Bo‘
|
1
|
-y2
|
-y3
|
- х3
|
У1
|
2/3
|
-1/3
|
1/3
|
4/3
|
X1
|
1/6
|
1/6
|
1/3
|
5/6
|
X2
|
7/6
|
1/6
|
-2/3
|
-7/6
|
У4
|
19/6
|
1/6
|
7/3
|
17/6
|
Z
|
-1/3
|
2/3
|
7/3
|
7/3
|
Ozod hadlar va Z qatoridagi koeffitsientlar musbat. Demak, optimal yechim topildi, ya'ni у2=у3=х3=0 va х1=1/6, х2=7/6 bo‘lganda Z ning maksimal qiymati -1/3 ga teng bo‘ladi, ya'ni z=-1/3.
2-misol.
Berilgan chiziqli dasturlash masalasining maqsad funksiyasiga min qiymat beruvchi yechimni toping.
x1+x2Ј 2
2x1-x2і 2
a1і0, x2і0
Z=x1-x2®min
Chegaraviy tizimni kanonik ko‘rinishda quyidagicha yozib olamiz:
x1+x2+x3 =2
-2x1+x2+x4 =-2
Simpleks jadval quramiz. Birinchi jadvalda ozod hadlar ichida manfiy element mavjud. Shuning uchun tayanch planni topamiz. Bu jadvaldan hal qiluvchi elementni topib, Simpleks almashtirish bajaramiz va ikkinchi jadvalga ega bo‘lamiz. Ikkinchi jadvalda tayanch plan mavjud. Shu sabab undan optimal planni topishga o‘tamiz.
So‘ Bo‘
|
1
|
-x2
|
-x2
|
|
So‘
Bo‘
|
1
|
-y2
|
-x2
|
y1
|
2
|
1
|
1
|
|
y1
|
1
|
1/2
|
3/2
|
y2
|
-2
|
-2
|
1
|
|
x1
|
1
|
-1/2
|
-1/2
|
z
|
0
|
-1
|
1
|
|
z
|
1
|
-1/2
|
1/2
|
Optimal planni topish uchun Z- qator elementlarini manfiy holga keltirish kerak. Buning uchun jadvaldan hal qiluvchi elementni topamiz. Hal qiluvchi element 3/2. Simpleks almashtirish qilib quyidagi jadvalga ega bo‘lamiz.
So‘
Bo‘
|
1
|
-y2
|
-y1
|
x2
|
2/3
|
1/3
|
2/3
|
x1
|
4/3
|
-5/6
|
-1/3
|
Z
|
2/3
|
-7/6
|
-1/3
|
Jadvaldan ko‘rinib turibdiki maqsad funksiyasiga minimal qiymat beruchi nuqta mavjud, ya'ni:
x1=4/3; x2=2/3; zmin=2/3.
|
