Chiziqli dasturlash masalalarini yechish usullari Bajardi: Sanoat farmatsiya fakulteti

2-misol.
Berilgan chiziqli dasturlash masalasining maqsad funksiyasiga min qiymat beruvchi yechimni toping.
x₁+x_2Ј 2
2x₁-x_2і 2
a_1і0, x_2і0
Z=x₁-x_2®min
Chegaraviy tizimni kanonik ko‘rinishda quyidagicha yozib olamiz:
x₁+x₂+x₃ =2
-2x₁+x₂+x₄ =-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:
x₁=4/3; x₂=2/3; z_min=2/3.
Amaliy mashg‘ulot uchun misollar
Quyidagi chiziqli dasturlash masalalarini grafik va simpleks usullarda yeching. Natijalarni solishtiring.

1.5х₁+4х₂ 20 2.- 5х₁+4х₂ 20

2х₁+3х₂ 24 -2х₁ -3х₂ -6
2х₁+3х₂ 20 х₁-3х₂  3
х₁0, х₂  0 х₁0, х₂  0
F(x₁; х₂)= 3х₁+ 2х₂ F(x₁; х₂)= 2х₁+ 3х₂-1

3. 5х₁-4х₂ -20 4.- 2х₁-х₂  2

-2х₁-3х₂ -24 х₁ -2х₂  2
-х₁+3х₂ -3 х₁+х₂  5
х₁0, х₂ 0 х₁0, х₂  0
F(x₁; х₂)=х₁+ 3х₂ +2 F(x₁; х₂)= -х₁+ х₂

5. 2х₁+х₂ 2 6. х₁+х₂  3

х₁- х₂  4 -х₁ -2х₂ 6
-3х₁+3х₂ 12 х₁ + х₂ 12
х₁+х₂  8 х₁- 3х₂  3
х₁0, х₂  0 х₁0, х₂  0
F(x₁; х₂)= -4х₁- 2х₂ F(x₁; х₂)= х₁ +х₂
7. 3х₁+х₂ 3 8. -х₁+х₂  2
6х₁ 14x₂ 21 х₂ 2
х₁3,5 -2х₁ + х₂ -6
2х₂  9 х₂  5,5
3х₁- 5х₂10 х₁2
х₁0, х₂  0 х₁0, х₂  0
F(x₁; х₂)= -х₁- х₂ F(x₁; х₂)= х₁+ х₂

9. 3₁-х₂  1 10. х₁-х₂ - 2

5х₁ -3x₂ 15 х₁ +3x₂6
х₂2,5 х₁ + 6х₂ 6
2х₁ -x₂-2 10x₁ + 7х₂  80
х₁+х₂1 - х₁+15x₂3
х₁0, х₂  0 х₁0, х₂  0
F(x₁; х₂)= х₁+ 3х₂ -2 F(x₁; х₂)= 2х₁+ х₂

11. 2х₁+2х₂ 13 12. х₁+х₂  3

x₂ 3 -x₁+х₂ 2
х₁4 х₁ + х₂ 6
3х₁ +2x₂ 6 2x₁ + х₂  10
х₁0 х₁+3x₂ 9
х₂  0 х₁0, х₂  0
F(x₁; х₂)= х₁- 3х₂ -3 F(x₁; х₂)= 4х₁+3х₂ -1

13. х₁-х₂ 5 14. х₁-х₂  1

4х₁ - 2x₂ 13 -3x₁+ 10х₂ 2
х₁+4x₂8 х₁ + х₂ 11
x1+4х₂  4 3x₂ - х₂  12
2х₁+ 3х₂ 24 х₁0
х₁0, х₂  0 х₂  0
F(x₁; х₂)= 2х₁+3 х₂ -7 F(x₁; х₂)= х₁+ х₂

15. 2х₁+3х₂ 6 16. 4х₁-5х₂  4

2х₁ +x₂ 4 4x₁ -3х₂ 12
х₁1 5х₁ - 3х₂ 6
х₁ -x₂ -1 x₁-3х₂ 3
2х₁+х₂1 10х₁-7x₂70
х₁0, х₂  0 х₁0, х₂  0
F(x₁; х₂)= х₁+ 2х₂ F(x₁; х₂)= 3х₁+ х₂ +3
17. -4х₁+5х₂ 29 18. 3х₁+4х₂  36
3х₁ -x₂ 14 x₁+ х₂  3
5х₁+2x₂  38 5х₁ + 3х₂ 21
х₁ 0 х₁0, х₂  0
х₂ 0 F(x₁; х₂)= 4х₁+ 7х₂
F(x₁; х₂)= 6х₁+3х₂ +21

19. -4х₁+5х₂ 29 20. х₁-2х₂ 4

3х₁ -x₂  14 2x₁ +х₂ 36
5х₁+2x₂38 х₂ 10
х₁ 0 x₁-х₂ -4
х₂0 3х₁+4x₂24
F(x₁; х₂)= 4х₁+ 3х₂ -7 х₁0, х₂  0
F(x₁; х₂)= х₁+ х₂ +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 b_i≥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 y₁, y₂, …, y_m noma'lumlarni mos ravishda qo‘shamiz va uni quyidagi ko‘rinishda yozamiz:

Quyidagi, yordamchi maqsad funksiyasini tuzamiz F=y₁+y₂+…+y_m va uning yuqoridagi shartni qanoatlantiradigan minimumini topamiz. Agar minF>0 bo‘lsa, qo‘yilgan masala y₁= y₂,= …= y_m =0 bo‘lganda, x_i≥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=x₁+x₂+3x₃ funksiyaning cheklanish shartlari quyidagicha bo‘lgan
x₁-x₃+4x₄=3
2x₁ -x₂=2
3x₁ -2x₂-x₄=1
x_jі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. y₁, y₂, y₃ sun'iy noma'lumlar yordamida bu masalaga mos chiziqli dasturlash masalasini quyidagicha yozamiz:
y₁=3-(x₁-x₃+4x₄),
y₂=3-(2x₁ -x₂),
y₃=1-( 3x₁ -2x₂-x₄)
Bu tizim uchun manfiy bo‘lmagan x_j≥0 j=1, 2, 3, 4 larni va quyidagi
F= y₁+ y₂+ y₃
yordamchi maqsad funksiyaga minimum qiymat beruvchi y₁, y₂, y₃ larni topamiz.
Boshlang‘ich jadvalda bazis noma'lumlar uchun y₁, y₂, y₃ larni olib, quyidagiga ega bo‘lamiz.
y₁+x₁--x₃+4x₄=3
y₂+2x₁ -x₂=3
y₃+3x₁ -2x₂-x₄=1
F+6 x₁-3 x₂-x₃+3x₄=7
Z- x₁- x₂-2x₃=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, y₁= y₂= y₃=0 da Z_min=16 bo‘lib, x₁=5; x₂=7; x₃=2; x₄=0 .