Simpleks jadval. Chiziqli programmalashtirish masalasining optimal yechimini simpleks usuli yordamida topish

Simpleks jadval. Chiziqli programmalashtirish masalasining optimal yechimini simpleks usuli yordamida topish

ChDMni maksimumini topish uchun tuzilagan boshlang’ich simpleks jadvali

Bazis o’zgaruv- chilar	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 koeffisiyentlari «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 koeffisiyentlari 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 koeffisiyentlari 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 koeffisiyentlari musbat ishoraga keltirish maqsad qilib qo’yiladi.

Simpleks jadvalida Z_j - C_j indeks qatoridagi noma’lumlarining koeffisiyentlaridan bittasi yoki bir nechtasi manfiy bo’lganida hal qiluvchi elementni tanlashda quyidagi munosabatlar amalga oshishi mumkin.

1.16. Aynigan chiziqli programmalashtirish masalalari va ularni yechish usullari.

Bizga matematika kursidan ma’lumki ikki algebraik ifoda bir-biri bilan () katta yoki () kichik belgi bilan bog’lanishi natijasida tengsizliklar hosil bo’ladi. Bir yoki ko’p o’zgaruvchili tengsizliklar chiziqli tengsizliklar deyiladi [2]. Masalan,

a₁x₁  c - bir o’zgaruvchili tengsizlik,

a₁x₁ + a₂x₂ {, } c - ikki o’zgaruvchili tengsizlik,

a₁x₁ + a₂x₂ +a₃x₃ {, } c - uch o’zgaruvchili tengsizlik,

a₁x₁ + a₂x₂ +a₃x₃ +...+ a_nx_n {, } c - n o’zgaruvchili tengsizlik.

ChDMlarini geometrik talqini haqida so’z ketganda, ikki noma’lumli tengsizliklar ustida ish olib boriladi.

Chiziqli tengsizliklarning geometrik talqini ularga mos keluvchi yarim (fazo) tekislik bo’ladi. Tenglamani tengsizlikka almashtirgandagi to’g’ri chiziqdan hosil bo’lgan yarim tekislik ko’pincha ikki noma’lumli tengsizliklar yechimlari sohasini ifodalaydi. Shu yarim tekislikka tegishli istalgan nuqta koordinatalari tengsizliklarni qanoatlantiradi, ya’ni shu istalgan nuqtani tengsizlikni yechimi deb qarash mumkin bo’ladi. Bunday nuqtalar to’plamini esa yechimlar to’plami deb qaraladi.

1.17. Iqtisodiy masalalarni simpleks usul bilan yechish

Xo’jalik chorva mollari uchun yem – xashak yetishtirishga ixtisoslashgan. Fermer xo’jaligida yetishtirilishi mumkin bo’lgan yem – xashaklarning turi va resurslari hajmi 1- jadvalda ozuqa birligida keltirilmoqda. Xo’jalikda chorvachilikning qoramolchilik tarmog’ini rivojlantirish imkoniyatlari mavjud. Xo’jalikda istiqbolda chorva mollarining qaysi bir turidan qancha bosh boqilsa ularni sotishdan olinadigan daromad maksimal bo’ladi?

1-jadval

Bir bosh chorva moli uchun ozuqa birligida sarf bo’ladigan yem – xashaklarning turi va resurslari xaqida ma’lumotlar

Yem-xashaklar turi	Chorva mollari turi:				Yem – xashak resurslari, s
	sog’in sigirlar	novvos	g’o’najin	buzoq
1. Konsentrat ozuqalar	12	13	7	4		450
2. Shirali ozuqalar	15	14	8	4		560
3. Dag’al xashaklar	8	6	5	3		300
4. Pichan	5	4	3	2		200
Bir bosh chorva molini sotish bahosi, m. s.	520	480	300	190

Masalaning maqsadi va optimallik mezoni. Chorva mollarining har bir turi bo’yicha bosh sonini topish talab qilinadiki, ularni sotishdan olinadigan daromad maksimal bo’lsin.

Bu iqtisodiy mazmundagi masala ChDM bo’lib u simpleks usuli bilan yechiladi.

Noma’lumlarni quyidagicha belgilaymiz:

x₁ - sog’in sigirlar bosh soni; x₂ - novvoslar bosh soni; x₃ - g’o’najinlar bosh soni; x₄ - buzoqlar bosh soni.

Bular asosiy noma’lumlar deb ataladi.

ChDMni tensizliklar sistemasining ifodalanishi

ChDMning tensizliklar sistemasi xo’jalikdagi yem-xashaklar turi bo’yicha resurslarining chorva mollariga taqsimlanishini ifodalaydi.

Xo’jalikda yetishtiriladigan:

450 s konsentrat ozuqalarning chorva mollariga taqsimlanishi:

12x₁ + 12x₂ + 7x₃ + 3x₄ ≤ 450,

560 s shirali ozuqalarning chorva mollariga taqsimlanishi:

15x₁ + 14x₂ + 8x₃ + 4x₄ ≤ 560,

268 s dag’al ozuqalarning chorva mollariga taqsimlanishi:

8x₁ + 6x₂ + 5x₃ + 3x₄ ≤ 300,

180 s pichanning chorva mollariga taqsimlanishi:

5x₁ + 4x₂ + 3x₃ + 2x₄ ≤ 200.

ChDMning maqsad fuksiyasining ifodalanishi

ChDMning maqsad fuksiyasi chorva mollarini sotishdan olinadigan daromadni maksimallashtirishdan iborat bo’ladi, ya’ni:

Z_mak= 520x₁ + 480x₂ + 300x₃ +190x₄

Demak, biz endi ChDM quyidagicha ifodalashimiz mumkin:

12x₁ + 12x₂ + 7x₃ + 3x₄ ≤ 450,

15x₁ + 14x₂ + 8x₃ + 4x₄ ≤ 560, (1)

8x₁ + 6x₂ + 5x₃ + 3x₄ ≤ 300,

5x₁ + 4x₂ + 3x₃ + 2x₄ ≤ 200.

x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0, x₄ ≥ 0. (2)

shartlarini qanoatlantiruvchi x₁, x₂, x₃, x₄ noma’lumlarning shunday qiymatlarini topish talab qilinadiki, u maqsad funksiyasini ifodalovchi

Z_mak= 520x₁ + 480x₂ + 300x₃ +190x₄

funksionalga maksimal qiymat bersin.

Masalani simpleks usuli bilan yechish uchun boshlang’ich tayanch reja topiladi. Buning uchun (1) tengsizliklar sistemasi tenglamalar sistemasi ko’rinishiga keltiriladi.

Demak, (1) sistemadagi tengsizliklarga mos ravishda musbat yoki nolga teng bo’lgan y₁, y₂, y₃ va y₄ qo’shimcha noma’lumlar musbat ishora bilan qo’shiladi. Bu qo’shimcha noma’lumlar maqsad funksiyasiga nol koeffisiyent bilan kiritiladi.

Natijada ChDM quyidagi ko’rinishni oladi:

12x₁ + 12x₂ + 7x₃ + 3x₄ + y₁ = 450,

15x₁ + 14x₂ + 8x₃ + 4x₄ + y₂ = 560, (1*)

8x₁ + 6x₂ + 5x₃ + 3x₄ + y₃ = 300,

5x₁ + 4x₂ + 3x₃ + 2x₄ + y₄ = 200.