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

Simpleks jadval. Chiziqli programmalashtirish masalasining optimal yechimini simpleks usuli yordamida topish
ChDMnimaksimuminitopishuchuntuzilagan Бошланғич boshlang’ichsimpleks jadvali

Bazis ўo’zgaruv- chilar	Cj	Bi	x1	x2	…	xn	хn+1	хn+2	…	хm
			s1	s2	…	sn	s n+1	sn+2	…	sm
хn+1	sn+1	b1	a11	a12	…	a1n	1	0	…	0
х n+2	s n+2	b2	a21	a22	…	a2n	0	1	…	0
…	…	…	…	…	…	…	…	…	…	…	…
хm	sm	bm	am1	am2	…	am	0	0	…	1
Zj - Cj		0	- s1	- s2	…	- sn	0	0	…	0

Бошлағич симплекс жадвалини тузишда:
Bazis bўo’lmagan х_n+1, х_n+2, ... , x_m 0 ўnomalumзгарувчиlar «Bazis ўo’zgaruvchilar» ustuniga yoziladi.
Bazismas бўлмаган ўnomalumзгарувчиlarning s_n+1, s_n+2, ... , s_m koeffisiyentlari «S_i» ustuniga yoziladi.
b₁, b₂, b₃ , ... , b_m ozod hadlar «B_i» ustuniga yoziladi.
Z_max=c₁x₁+c₂x₂+c₃x₄+...+ c_nx_n+0x_n+1+0x_n+2+0x_n+3+...0x_m maqsad funksiyaning koeffisiyentlari Z_j - C_j qatorga qarmaqarshiтескари ishora bilan yoziladi. Bu qator indeks qator deb yuritiladi.
 ЧДМ нинг симплекс жадвалида Z_j - C_j индекс қаторидаги ҳамма номаълумларнинг коэффициентлари мусбат бўлса масала оптимал ечимга эга бўлади. Симплекс усули билан ЧДМни оптимал ечимини топишда Z_j - C_j индекс қаторидаги ҳамма номаълумларнинг коэффициентлари мусбат ишорага келтириш мақсад қилиб қўйилади.
ChDMningsimpleksjadvalidaindeksqatoridagihammanomalumlarningkoeffisiyentlarimusbatbo’lsamasalaoptimalyechimgaegabo’ladiSimpleksusulibilanChDMnioptimalyechiminitopishdaindeksqatoridagihammanomalumlarningkoeffisiyentlarimusbatishoragakeltirishmaqsadqilibqo’yiladiЧДМ бошланғич симплекс жадвал тузилганда бошқа симплекс жадвалига ўтишнинг асосий қоидалари
Simpleks jadvalida Z_j - C_j indeks qatoridagi nomaъlumlarining koeffisiyentlaridan bittasi yoki bir nechtasi manfiy bўo’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 bўo’ladi. Bir yoki kўo’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 sўo’z ketganda, ikki nomaъlumli tengsizliklar ustida ish olib boriladi.
Chiziqli tengsizliklarning geometrik talqini ularga mos keluvchi yarim (fazo) tekislik bўo’ladi. Tenglamani tengsizlikka almashtirgandagi tўo’g’ri chiziqdan hosil bўo’lgan yarim tekislik kўo’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 bўo’ladi. Bunday nuqtalar tўo’plamini esa yechimlar tўo’plami deb qaraladi.
1.17. Iqtisodiy masalalarni simpleks usul bilan yechish
Xўo’jalik chorva mollari uchun yem – xashak yetishtirishga ixtisoslashgan. Fermer xўo’jaligida yetishtirilishi mumkin bўo’lgan yem – xashaklarning turi va resurslari hajmi 1- jadvalda ozuqa birligida keltirilmoqda. Xўo’jalikda chorvachilikning qoramolchilik tarmog’ini rivojlantirish imkoniyatlari mavjud. Xўo’jalikda istiqbolda chorva mollarining qaysi bir turidan qancha bosh boqilsa ularni sotishdan olinadigan daromad maksimal bўo’ladi?
1-jadval
Bir bosh chorva moli uchun ozuqa birligida sarf bўo’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		405
2. Shirali ozuqalar	11	10	8	4		408
3. Dag’al xashaklar	8	6	5	3		268
4. Pichan	4	3	4	2		180
Bir bosh chorva molini sotish bahosi, m. s.	520	460	300	190

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

. Масаланинг сонли моделини тузиш

Bu iqtisodiy mazmundagi masala ChDM bўo’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 xўo’jalikdagi yem-xashaklar turi bўo’yicha resurslarining chorva mollariga taqsimlanishini ifodalaydi.
Xўo’jalikda yetishtiriladigan:
405 s konsentrat ozuqalarning chorva mollariga taqsimlanishi:
12x₁ + 13x₂ + 7x₃ + 4x₄ ≤ 405,
2) 408 s shirali ozuqalarning chorva mollariga taqsimlanishi:
11x₁ + 10x₂ + 8x₃ + 4x₄ ≤ 408,
268 s dag’al ozuqalarning chorva mollariga taqsimlanishi:
8x₁ + 6x₂ + 5x₃ + 3x₄ ≤ 268,
180 s pichanning chorva mollariga taqsimlanishi:
4x₁ + 3x₂ + 4x₃ + 2x₄ ≤ 180.
ChDMning maqsad fuksiyasining ifodalanishi
ChDMning maqsad fuksiyasi chorva mollarini sotishdan olinadigan daromadni maksimallashtirishdan iborat bўo’ladi, yaъni:
Z_mak= 520x₁ + 460x₂ + 300x₃ +190x₄
Demak, biz endi ChDM quyidagicha ifodalashimiz mumkin:
12x₁ + 13x₂ + 7x₃ + 4x₄ ≤ 405,
11x₁ + 10x₂ + 8x₃ + 4x₄ ≤ 408, (1)
8x₁ + 6x₂ + 5x₃ + 3x₄ ≤ 268,
4x₁ + 3x₂ + 4x₃ + 2x₄ ≤ 180.
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₁ + 460x₂ + 300x₃ +190x₄ funksionalga maksimal qiymat bersin.

. Симплекс жадвалларини тузиш ва таянч режанинг оптималлигини текшириш. Симплекс жадвалларининг иқтисодий мазмуни

Masalani simpleks usuli bilan yechish uchun boshlang’ich tayanch reja topiladi. Buning uchun (1) tengsizliklar sistemasi каноник, яъни tenglamalar sistemasi kўo’rinishiga keltiriladi.
Demak, (1) sistemadagi tengsizliklarga mos ravishda musbat yoki nolga teng bўo’lgan x₅, x₆, x₇ va x₈ qўo’shimcha nomaъlumlar musbat ishora bilan qўo’shiladi. Bu qўo’shimcha nomaъlumlar maqsad funksiyasiga nolь koeffisiyent bilan kiritiladi.
Natijada ChDM quyidagi kўo’rinishni oladi:
12x₁ + 13x₂ + 7x₃ + 4x₄ – x₅ = 405,
11x₁ + 10x₂ + 8x₃ + 4x₄ – x₆ = 408, (1∙)
8x₁ + 6x₂ + 5x₃ + 3x₄ – x₇ = 268,
4x₁ + 3x₂ + 4x₃ + 2x₄ – x₈ = 180.