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.
Amaliy mashg‘ulot uchun misollar
Quyidagi chiziqli dasturlash masalalarini grafik va simpleks usullarda yeching. Natijalarni solishtiring.
1.5х1+4х2 20 2.- 5х1+4х2 20
2х1+3х2 24 -2х1 -3х2 -6
2х1+3х2 20 х1-3х2 3
х10, х2 0 х10, х2 0
F(x1; х2)= 3х1+ 2х2 F(x1; х2)= 2х1+ 3х2-1
3. 5х1-4х2 -20 4.- 2х1-х2 2
-2х1-3х2 -24 х1 -2х2 2
-х1+3х2 -3 х1+х2 5
х10, х2 0 х10, х2 0
F(x1; х2)=х1+ 3х2 +2 F(x1; х2)= -х1+ х2
5. 2х1+х2 2 6. х1+х2 3
х1- х2 4 -х1 -2х2 6
-3х1+3х2 12 х1 + х2 12
х1+х2 8 х1- 3х2 3
х10, х2 0 х10, х2 0
F(x1; х2)= -4х1- 2х2 F(x1; х2)= х1 +х2
7. 3х1+х2 3 8. -х1+х2 2
6х1 14x2 21 х2 2
х13,5 -2х1 + х2 -6
2х2 9 х2 5,5
3х1- 5х210 х12
х10, х2 0 х10, х2 0
F(x1; х2)= -х1- х2 F(x1; х2)= х1+ х2
9. 31-х2 1 10. х1-х2 - 2
5х1 -3x2 15 х1 +3x26
х22,5 х1 + 6х2 6
2х1 -x2-2 10x1 + 7х2 80
х1+х21 - х1+15x23
х10, х2 0 х10, х2 0
F(x1; х2)= х1+ 3х2 -2 F(x1; х2)= 2х1+ х2
11. 2х1+2х2 13 12. х1+х2 3
x2 3 -x1+х2 2
х14 х1 + х2 6
3х1 +2x2 6 2x1 + х2 10
х10 х1+3x2 9
х2 0 х10, х2 0
F(x1; х2)= х1- 3х2 -3 F(x1; х2)= 4х1+3х2 -1
13. х1-х2 5 14. х1-х2 1
4х1 - 2x2 13 -3x1+ 10х2 2
х1+4x28 х1 + х2 11
x1+4х2 4 3x2 - х2 12
2х1+ 3х2 24 х10
х10, х2 0 х2 0
F(x1; х2)= 2х1+3 х2 -7 F(x1; х2)= х1+ х2
15. 2х1+3х2 6 16. 4х1-5х2 4
2х1 +x2 4 4x1 -3х2 12
х11 5х1 - 3х2 6
х1 -x2 -1 x1-3х2 3
2х1+х21 10х1-7x270
х10, х2 0 х10, х2 0
F(x1; х2)= х1+ 2х2 F(x1; х2)= 3х1+ х2 +3
17. -4х1+5х2 29 18. 3х1+4х2 36
3х1 -x2 14 x1+ х2 3
5х1+2x2 38 5х1 + 3х2 21
х1 0 х10, х2 0
х2 0 F(x1; х2)= 4х1+ 7х2
F(x1; х2)= 6х1+3х2 +21
19. -4х1+5х2 29 20. х1-2х2 4
3х1 -x2 14 2x1 +х2 36
5х1+2x238 х2 10
х1 0 x1-х2 -4
х20 3х1+4x224
F(x1; х2)= 4х1+ 3х2 -7 х10, х2 0
F(x1; х2)= х1+ х2 +24
4.Excel dasturiy vositasida chiziqli dasturlash masalasini yechish
Chiziqli dasturlash masalasini Excel jadval protsessorida yechish uchun oldin masala shartlari kiritilib, keyin Сервис menyusidagi Поиск решения protsedurasidan foydalaniladi.
Masala shartlarini kiritish quyidagi qadamlardan iborat:
1.Masala shartlarini kiritish uchun forma tayyorlash.
2.Boshlang‘ich ma'lumotlarni kiritish.
3.Matematik modelga bog‘liq bog‘lanishlarni kiritish.
4.Maqsad funksiyasini kiritish.
5.Cheklanish va chegaraviy shartlarni kiritish.
Misol uchun yuqoridagi 3.3. punktda berilgan birinchi chiziqli dasturlash masalasini komp'yuterda Excel vositasida "Поиск решения" protsedurasi yordamida yechish ketma ketligini ko‘rib chiqamiz:
1.Excel oynasida masala shartlarini kiritish uchun forma tayyorlaymiz.
2.Ma'lumotlarni mos yacheykalarga kiritamiz.
3.E4 yacheykasiga =B4*$B$3+C4*$C$3+D4*$D$3 formulasini kiritamiz.
4.Bu E4 yacheykadan E5,E6,E7,E8 yacheykalariga nusxa ko‘chiramiz.
5."Поиск решения" protsedurasini ishga tushiramiz, ya'ni menyuning "Сервис" bo‘limidan "Поиск решения" protsedurasi tanlaymiz.
6.Ochilgan "Поиск решения" protsedurasi muloqot oynasida quyidagilarni kiritamiz:
6.1.Sichqoncha bilan maqsad funksiyasi qatoridagi formula kiritilgan E4 yacheykasini ko‘rsatamiz.
6.2.Maqsad funksiyasi ekstremumini (masalan, muloqot oynasidan "максимальному значению" tanlanadi) tanlaymiz.
6.3."Изменяя ячейки" maydoniga o‘tib o‘zgaruvchilar qiymati ko‘rsatilgan adreslarni kiritamiz. Buning oson yo‘li shu yacheykalarni sichqonchada ajratishdir.
6.4.Chegaralanishlarni kiritish. Bu jarayon kursor "Ограничения" maydoniga qo‘yilib "Добавить'" tugmasini bosish bilan amalga oshiriladi. Natijada "Добавление ограничения" oynasi ochiladi.
6.5."Ссылка на ячейку" maydoniga birinchi chegaralanish uchun kiritilgan formula yacheykasi E5 sichqonchada ko‘rsatiladi, keyin matematik formulada berilgan shart belgisi tanlanadi va "Ограничение" maydoniga mos b ozod had qiymati turgan yacheyka adresi ko‘rsatiladi (yoki kiritiladi). Bu jarayon boshqa chegaralanishlar uchun ham qaytariladi.
6.6.Xuddi 6.5. punktidagi kabi chegaraviy shartlar ham kiritiladi. "Ссылка на ячейку" maydoniga B3 yacheykasi ko‘rsatilib, “>=” belgisi tanlanadi va keyin "Ограничение" maydoniga 0 qiymat beriladi. Boshqa o‘zgaruvchilar chegaraviy sharti ham shu usulda kiritiladi.
7 .”Выполнить” buyrug‘i beriladi va natijada quyidagi natijaga ega bo‘lamiz.
8.Natijani saqlab qo‘yish uchun “Результаты поиска решения” muloqot oynasidan Ok tugmasini bosamiz.
Oxirgi oynadan ko‘rinib turibdiki optimal yechim quyidagicha: x1=0.16667; x2=1.16667; x3=0; Z=-0.3333.
Amaliy mashg‘ulot uchun misollar
2 bo’lim va 3 bo’limning 3.3. punktidagi misollarni Excel dasturiy vositasida yeching va natijalarni solishtiring.
5.Chiziqli dasturlash masalasini yechishning sun'iy bazis usuli
Amalda uchraydigan ayrim chiziqli dasturlash masalalari planga ega bo‘lgan holda birlik matritsani o‘z ichiga olmaydi va cheklanishlar tizimida noma'lumlar soni cheklanishlar sonidan yetarlicha katta bo‘ladi. Bunday masalalarni yechishda "sun'iy bazis usuli" qo‘llaniladi.
Sun'iy bazis usuli.
Quyidagi chiziqli dasturlash masalasini qaraymiz:
Bu yerda bi≥0, va tizim birlik matritsani o‘z ichiga olmaydi deb faraz qilamiz. Masalaning shartiga birlik matritsani kiritish uchun tizimdagi har bir tenglamaga sun'iy o‘zgaruvchilar deb ataluvchi y1, y2, …, ym noma'lumlarni mos ravishda qo‘shamiz va uni quyidagi ko‘rinishda yozamiz:
Quyidagi, yordamchi maqsad funksiyasini tuzamiz F=y1+y2+…+ym va uning yuqoridagi shartni qanoatlantiradigan minimumini topamiz. Agar minF>0 bo‘lsa, qo‘yilgan masala y1= y2,= …= ym =0 bo‘lganda, xi≥0 shartni qanoatlan-tiradigan yechimga ega bo‘lmaydi. Agar minF=0 bo‘lsa, bazis yechim masalaning optimal yechimi bo‘ladi. Buning uchun yordamchi maqsad funksiyasini nolga olib keluvchi masalani simpleks usulida yechamiz.
Misol. Ushbu Z=x1+x2+3x3 funksiyaning cheklanish shartlari quyidagicha bo‘lgan
x1-x3+4x4=3
2x1 -x2=2
3x1 -2x2-x4=1
xjі0, j=1,2,3,4
va uni qanoatlantiradigan minimumi topilsin.
Echish. Cheklanish shartlari bazis noma'lumlarga nisbatan yechilmagan bo‘lganligi uchun simpleks usuldan foydalanib bo‘lmaydi. Bu masalani simpleks jadval usuli bilan yechish uchun sun'iy bazis usulidan foydalanamiz. y1, y2, y3 sun'iy noma'lumlar yordamida bu masalaga mos chiziqli dasturlash masalasini quyidagicha yozamiz:
y1=3-(x1-x3+4x4),
y2=3-(2x1 -x2),
y3=1-( 3x1 -2x2-x4)
Bu tizim uchun manfiy bo‘lmagan xj≥0 j=1, 2, 3, 4 larni va quyidagi
F= y1+ y2+ y3
yordamchi maqsad funksiyaga minimum qiymat beruvchi y1, y2, y3 larni topamiz.
Boshlang‘ich jadvalda bazis noma'lumlar uchun y1, y2, y3 larni olib, quyidagiga ega bo‘lamiz.
y1+x1--x3+4x4=3
y2+2x1 -x2=3
y3+3x1 -2x2-x4=1
F+6 x1-3 x2-x3+3x4=7
Z- x1- x2-2x3=0
Bu masalaga mos simpleks jadval quyidagicha bo‘ladi:
|
1
|
-x1
|
-x2
|
-x3
|
-x4
|
y1
|
3
|
1
|
0
|
-1
|
4
|
y2
|
3
|
2
|
-1
|
0
|
0
|
y3
|
1
|
3
|
-2
|
0
|
-1
|
F
|
7
|
6
|
-3
|
-1
|
3
|
Z
|
0
|
-1
|
-1
|
-2
|
0
|
Simpleks jadvalning biridan ikkinchisiga ketma-ket o‘tib, quyidagi jadvallarni tuzamiz
|
1
|
-y3
|
-x2
|
-x3
|
-x4
|
Y1
|
8/3
|
-1/3
|
2/3
|
-1
|
13/3
|
Y2
|
7/3
|
-2/3
|
1/3
|
0
|
2/3
|
X1
|
1/3
|
1/3
|
-2/3
|
0
|
-1/3
|
F
|
5
|
-2
|
1
|
-1
|
5
|
Z
|
1/3
|
1/3
|
-5/3
|
-2
|
-1/3
|
|
1
|
-y3
|
-y1
|
-x3
|
-x4
|
X2
|
4
|
-1/2
|
3/2
|
-3/2
|
13/2
|
Y2
|
1
|
-1/2
|
-1/2
|
1/2
|
-3/2
|
X1
|
3
|
0
|
1
|
-1
|
4
|
F
|
1
|
-3/2
|
-3/2
|
1/2
|
-3/2
|
Z
|
21/3
|
-1/2
|
-5/2
|
-9/2
|
21/2
|
|
1
|
-y3
|
-y1
|
-y2
|
-x4
|
x2
|
7
|
-2
|
0
|
3
|
2
|
x3
|
2
|
-1
|
-1
|
2
|
-3
|
x1
|
5
|
-1
|
0
|
2
|
1
|
F
|
0
|
-1
|
-1
|
-1
|
-0
|
Z
|
16
|
-4
|
-2
|
9
|
-3
|
Oxirgi jadvalda F dan boshlanuvchi satrda musbat element mavjud emas. Demak, topilgan {5;7;2;0;0;0} yechim optimal yechim bo‘ladi, chunki bu yechimda F=0. Demak, y1= y2= y3=0 da Zmin=16 bo‘lib, x1=5; x2=7; x3=2; x4=0 .
Dostları ilə paylaş: |