Chiziqli dasturlashtirish masalalari

29-MA’RUZA Chiziqli dasturlashtirish masalalari
REJA:
29.1	Umumiy tushunchalar
29.2	Xom ashyodan foydalanish masalasi
29.3	Chiziqli dasturlashtirish masalalarining umumiy ko’rinishi
29.4	Chiziqli dasturlashtirish masalalarini yechish

Chiziqli dasturlashtirish bu chiziqli funksiyaning o’zgaruvchilariga chiziqli cheklanganlik shartlari qo’yilganda eng katta va eng kichiq qiymatlarini izlash usullari va uni topish hakidagi fandir. Shunday qilib chiziqli dasturlashtirish masalalari funksiyaning shartli ekstremumlarini topish masalalariga kiradi. Lekin bu masalalarni ko’p o’zgaruvchili funksiyaning shartli ekstremumlaridek yecha olmaymiz. Uni quydagi masala yordamida tushuntirishimiz mumkin.

Z= C_j X_j funksiyaning

a₁₁ x₁+a₁₂ x₂+...+a_1nx_n=b₁

a₂₁ x₁+a₂₂ x₂+...+a_2n x_n=b₂
.......................................
a_m1 x₁+a_m2+...+a_mnx₃=b_m

shartlarni qanoatlantiruvchi ekstremumlarini topish masalasini ko’rib chiqaylik. Z-chiziqli funksiya bo’lganligi uchun (z((xj=cj (j=1,2,...,n) lekin Z-chiziqli funksiyaning barcha c_j-koeffitsientlari “nol”ga teng emas, demak zx_j=0 shart barcha x_j lar uchun bajarilmaydi. Shuning uchun soxaning ichida ekstremum yo’q . Bu nuqtalar soxaning chegaralarida bo’lishi mumkin. Lekin biz ularni ham tekshira olmaymiz, chunki xususiy hosilalar o’zgarmasdir. Shu sababli chiziqli dasturlashtirish masalalarini yechishni maxsus usullarni topishga to’g’ri keladi.

Chiziqli dasturlashtirish masalalari iqtisodda juda ko’p ishlatiladi.Xozir biz quyida oddiy iqtisodiy masalalarning matematik modellarini tuzishni ko’rib chiqamiz.
Xom ashyodoan foydalanish masalasi.
Ikki xil B₁ va B₂ maxsulotlar tayorlash uchun uch xil ham ashyo S₁,S₂,vaS₃ ishlatiladi.
1-jadvalda xom ashyo zaxirasi, maxsulot ishlab chiqarish uchun sarf bo’ladigan xom ashyo birligi, bir birlik maxsulotning bahosi berilgan.
1. jadval

Xom ashyo turi	Xom ashyo zaxirasi	Maxsulot birligiga sarflanadigan xom ashyo miqdori
		В1	В2
S1	20	2	5
S2	40	8	5
S3	30	5	6
Daromad		50	40

Bo’larga nisbatan shunday reja tuzish zarurki, umumiy yetishtirilgan maxsulot realizatsiyasidan olinadigan foyda maksimal bo’lib, xom ashyo zaxirasidan ratsional foydalanilsin.

X₁ orqali B₁ maxsulot birligi miqdorini; X₂ orqali B₂ maxsulot birligi miqdorini belgilaymiz.
Xom ashyo zaxirasi birligi miqdorini va xom ashyo zaxirasini nazarda tutib 1-jadvalda berilganlardan foydalanib quyidagi tengsizliklar sistemasini tuzib olamiz

2x1+5x220	(1)
8x1+ 5x2
5x1+ 6x230

Sistemadan ko’rinib turibdiki maxsulot ishlab chiqarish uchun sarf bo’ladigan xom ashyomiz zaxiradan ko’p bo’lishi mumkin emas. Agar B₁ maxsulot ishlab chiqarilmasa x1=0 aks holda x₁ bo’ladi. Xuddi shunday B₂ uchun ham x₂=0 yoki x₂. Demak x₁ va x₂ o’zgaruvchilar manfiy emas ya‘ni х₁х_ B_ maxsulotning x ₁ birligini realizatsiya qilishdan 50 x₁ so’m va B₂ maxsulotning x₂ birligini realizatsiya qilishdan 40 x₂ so’m foyda olinadi, bu foydalarning yigindisi

Z=50х₁+40х₂ (so’m) (2)
Masalaning maqsadiga yetish uchun Z=50x₁+40x₂ chiziqli funksiyaning

2х1+5х2 20

8х1+5х2 40

5х1+6х2 30

х10, х20

shartlarni qanoatlantiruvchi eng katta qiymatini topish kerak.
Bu tuzilgan (2) funksiya maqsad funksiyasi deyiladi va qo’yilgan (1) shartlar sistemasi bilan birga berilgan masalaning matematik modelini tashqil qiladi.
Xom ashyodan foydalanish masalasini n- turdagi maxsulot ishlab chiqarish uchun, m-turdagi xom ashedan foydalanamiz deb va S_i-(i=1,…,m) xom ashyolar soni (i=1,2), p_j(j=1,2,...,n) - maxsulotlar soni; bi-xom ashyo zaxirasi; aij- j- chi maxsulotni bir birligiini ishlab chiqarish uchun sarf boladigan j-chi maxsulotning birligi; Sj-maxsulotni realizatsiya qilishdan olinadigan foyda deb umumlashtirilgan masalani hosil qilishimiz mumkin.
2- jadval

Xom ashyo turi	Xom ashyo zaxirasi	j-chi maxsulotni 1 birligini ishlab chiqarish uchun i-chi xom ashyoning sarf bo’ladigan birligi
		Р1	Р2	……..	Рn
S1	b1	a11	a12	………	a1n
S2	b2	a21	a22	…..	a2n
………………	…………	…………	……..	………	……
Sm	bm	am1	am2	………	amn
FOYDA		С1	С2	……..	Сn

a11 x1+a12 x2+...+a1n xn b1	(4)
a12 x1+a22 x2+...+a2n xn b2
........................................
am1 x1+am2 x2+...+amnbm

shartlarni qanoatlantiruvchi x_j0(j=1,n) Z=c₁ x₁+c₂x₂+...+c_nx_n funksiyaning eng katta qiymatini topish.

Ta‘rif: Reja yoki chiziqli dasturlashtirish masalasining o’rinli yechimlar to’plami deb (1) va (2) shartlarni qanoatlantiruvchi х=(х₁,х₂,...,х_n) vektorga aytiladi.
Ta‘rif. Optimal reja yoki chiziqli dasturlashtirish masalasining optimal yechimi deb, chiziqli funksiyani (maqsad funksiya) eng kichiq qiymatga(katta) erishtiradigan rejaga aytiladi.
Simpleks usulda yechish mumkin bo’lgan masalalar sinfi.
Chiziqli dasturlashtirishning umumiy masalasi berilgan bo’lsin. X₁,...,x₂,…,x_n o’zgaruvchilarning shunday qiymatlarini topaylikki,

F =c₁x₁+c₂ x₂ + ... +c_n x_n = (1)

funksiya eng katta (maksimum) yoki eng kichiq (minimum) qiymatga ega va bunda quyidagi shartlar bajarilsin:

a11x1+a12x2+ ... +a1nxn ≤b1	(2)
a21x1+a22x2+ ... +a2nxn ≤b2
………………………….
am1x1+am2x2+ ... +a mnxn≤bm
x1≥ 0, x2≥ 0, ... , xn≥ 0	(3)

Ma‘lumki, chiziqli dasturlashtirishning umumiy masalasi tenglamalar sistemasi orqali ifodalangan edi. Shuning uchun (2) ni yangi o’zgaruvchilar kiritish yu’li bilan tenglik shaklida ifodalaymiz:

a11x1+a12x2 + ... + a1nxn+ xn+1=b1	(4)
a21x1+a22x2+ ... +a2nxn +xn+2 =b2
………………………….
am1x1+am2x2+ ... +a mnxn+xn+m=bm
x1≥ 0, x2≥ 0, ... , xn≥ 0,…, xn+m ≥ 0

(4) tenglamalar sistemasini (1) va (3) shartlar bajarilganda yechimlarini topish uchun dastlabki simpleks jadvalni (1-jadval) tuzamiz.
Simpleks jadvalni tuzib olish.
Bu jadval quyidagi ketma-ketlikka bo’ysunadi.
1. Dastlabki simpleks jadval quyidagicha tuziladi:
a) "bazis" ustunida faqatgina birlik matritsani tashqil etuvchi o’zgaruvchilar yoziladi;
b) mos ravishda o’zgaruvchilardan oldin yozilgan c_j soni shartli ravishda maqsad funksiyasidagi xj o’zgaruvchilarning koeffitsentlari deyiladi;
v) "reja" ustunidagi elementlar (4) tenglamalar sistemasining ozod xadlari bilan mos tushadi. Shuning uchun bazisga kirmagan o’zgaruvchilar x₁=x₂ = ... x_n= 0 bo’lib, x_n+1=b₁, x_n+2=b₂,…, x_n+m=b_m
Bo’lar bazisga kirmagan yechimdagi har bir x ning qiymatlari orqali aniqlanadi;
g) jadvalning qolgan elementlari (4) tenglamalar sistemasining koeffitsientlariga teng bo’ladi;
d) reja ustunining (m+1) - qatoriga chiziqli formadagi maqsad funksiyasining qiymati yoziladi.Bu qiymat berilgan tayanch reja orqali topiladi.
Z₀ ning qiymati quyidagicha topiladi:
Z₀= (13)
C_i= 0 bo’lganda Z₀ = 0 bo’ladi.
Z_j ning qiymati s vektorning x_j ga skalyar ku’paytmasi orqali topiladi:
z_j= a_ij, (j = ) (14)
е) (m+1) qatorning 1 dan boshlab k gacha hamma j elementlari quyidagicha topiladi:
z_j-c_j=(c_n+1a_1j+c_n+2a_2j+...+c_n+2a_ij+...+c_n+ma_mj) –c_j (15)
z_j=0 Агар x_m+1, x_m+2, …,x_n+m o’zgaruvchilar maqsad funksiyasida "nol" koeffitsientlar bilan qatnashgan bo’lsa, zj-cj=-cj tenglik hamma j = 1,….,m lar uchun u’r inli bo’ladi.