S. I. Xudoyberdiyev iqtisodiy matematik usullar va

J ^J J J J


a_;
chiziqli cheklash shartlari sistemasi berilgan bo’lsin, bunda berilgan o’zgarmas miqdorlar.

Chiziqli dasturlash masalasi, bu x₁, x₂,...,x_n o’zgaruvchilarning shunday qiymatlarini topish kerakki, ular (2), (3) cheklash sistemasini qanoatlantirib, (1) chiziqli funksiya minimum (maksimum) qiymatga ega bo’lsin.

Chiziqli dasturlash masalasining umumiy qo’yilishini bir necha formalarda (shakllarda) yozish mumkin.

1. 
   Vektorlar shaklida yozilishi. Ushbu belgilashlarni kiritamiz:
   

a

1n

a

a

11

a

a

12

a

A =

a₂ =

, A =

Ao =

V ^bm У

V ^a m1 У

V ^a mn У

V^am2 У

C = (c₁,c₂,...,c_n), X = (x₁,x₂,...,x_n) bo’lib, CX = cx₁ + c₂x₂ +... + c_nx_n skalyar ko’paytma bo’lsin. Bu holda chiziqli dasturlash masalasini vektor ko’rinishda quyidagicha ifodalash mumkin:

Z = CX

chiziqli funksiya minimumga ega bo’ladigan X vektorning

^A1 ^x1 + ^A2^x2 + ... + ^An^xn = ^A0 ^{, X} > ^{0 (4)}

shartlarni qanoatlantiruvchi qiymatini toping.

2. 
   Matritsa shaklida yozilishi.
   

AX = A₀, X > 0 shartlarni qanoatlantiruvchi Z = CX chiziqli funksiya minimum qiymatga ega bo’ladigan X vektorning qiymatini toping, bunda

C = (cj,c₂,...,c_n) satr matritsa, X =
ustun matritsa va A = (a_tj) sistema

• 
  ^xn у
  

matritsasi hamda A_n =

0

V ^bn у
ustun matritsa bo’ladi.

A¹

3. 
   Yig’indi belgisi orqali yozilishi.
   

n

• 
  a x = b , i = 1,2,...,m; x > 0, j = 1,2,...,n
  

ij j j j

j=1

n

shartlarni qanoatlantiruvchi Z = V^c_jx_j chiziqli funksiya minimumga ega

j=1

bo’ladigan x_j o’zgaruvchilarning qiymatini toping.

1. 
   ta’rif. (2) va (3) shartlarni qanoatlantiruvchi X = (x₁, x₂,..., x_n) vektorga chiziqli dasturlash masalasining mumkin bo’lgan yechimi yoki qisqacha rejasi (plani) deyiladi.
   
2. 
   ta’rif. (4) yoyilmaga kiruvchi x larning musbat hadli A_i (i = 1,2,...,m) vektorlari chiziqli bog’lanmagan bo’lsa, X = (x₁,x₂,...,x_n) rejaga tayanch reja (yechim) deyiladi.
   

A_i (i = 1,2,...,m) vektorlar m o’lchovli bo’lganligi uchun tayanch reja ta’rifidan ko’rinadiki, uning musbat hadli koeffitsiyentlari m dan katta bo’lmaydi.

3. 
   ta’rif. Tayanch reja (yechim) m ta musbat komponentlarga ega bo’lsa, unga maxsusmas, aks holda maxsus reja deyiladi.
   
4. 
   ta’rif. Chiziqli funksiya minimum (maksimum) qiymatga ega bo’ladigan reja (yechim)ga chiziqli dasturlash masalasining optimal rejasi (yechimi) deyiladi.
   

Chiziqli dasturlash masalasi yechimining ayrim xossalarini qaraymiz:

1. 
   chiziqli dasturlash masalasi cheklash shartlari sistemasining rejalari
   

(mumkin bo’lgan yechimlari) to’plami bo’sh to’plamni yoki Rn fazoning qavariq to’plamini tashkil etadi;

2. 
   chiziqli dasturlash masalasining rejalari to’plami bo’sh to’plam bo’lmasa va maqsadli funksiya bu to’plamda yuqoridan (quyidan) chegaralangan bo’lsa, masala maksimum (minimum) optimal yechimga ega bo’ladi;
   
3. 
   chiziqli dasturlash masalasining optimal yechimi mavjud bo’lsa, bu
   

yechim mumkin bo’lgan yechimlar to’plamining chegaraviy nuqtalarida bo’ladi.

2. 
   Chiziqli dasturlash masalasining geometrik talqinini (tasvirini) n = 2, ayrim hollarda n = 3 bo’lganda ifodalash mumkin. Chiziqli dasturlash masalasi quyidagicha berilgan bo’lsin:
   

• 
  2x1 + 3x2 < 9, x_l — 2x₂ < 2. x_l + x₂ < 8, x₁ > 0, x₂ > 0
  

tengsizliklar sistemasini qanoatlantiruvchi x₁ va x₂ o’zgaruvchilarning shunday qiymatini topish kerakki, f = x₁ — x₂ funksiya maksimum qiymatga ega bo’lsin.

Yechish. 1) — 2x_x + 3x₂ < 9 tengsizlik bilan aniqlanadigan geometrik tasvirni aniqlaymiz. Buning uchun oldin — 2x_x + 3x₂ = 9 to’g’ri chiziqni x₁Ox₂ koordinat tekisligida yasaymiz. Ma’lumki, to’g’ri chiziq A (0;3) va B (—4,5;0) nuqtalardan o’tadi.

Endi — 2x_l + 3x₂ < 9 tengsizlikka mos geometrik tasvirni aniqlash uchun, berilgan tengsizlikka koordinatlar boshi O (0;0) nuqtaning koordinata-larini qo’yamiz: — 2 • 0 + 3 • 0 < 9 yoki 0 < 9 tengsizlik bajariladi, shuning uchun

• 
  2xj + 3x₂ < 9 tengsizlik bilan aniqlanadigan geometrik tasvir koordinatlar boshi, O (0;0) nuqtani o’z ichiga olgan yarim tekislikdan iborat bo’ladi.
  

2. 
   
   1-chizma
   
   3) x_x + x₂ = 8 to’g’ri chiziq A₂ (0;8), B₂ (8;0) nuqtalardan o’tadi.
   Xuddi yuqoridagidek kolgan tengsizliklarga mos kelgan yarim tekisliklarni yasaymiz. x_x — 2x₂ = 2, bu to’g’ri chiziq Aj (0;—1), B_l (2;0) nuqtalardan o’tadi. x_x — 2x₂ < 2, 0 — 2 • 0 < 2,0 < 2 tengsizlik bajariladi.
   

x₁ + x₂ < 8, 0 + 0 < 8, 0 < 8 bo’ladi.

4. 
   x₁ > 0, x₂ > 0 yarim tekisliklarni ham yasaymiz:
   

Shunday qilib, berilgan tengsizliklar sistemasini qanoatlantiradigan mumkin bo’lgan yechimlar to’plami - ОАСДВ yechimlar ko’pburchagini hosil qildik. Ma’lumki, bu to’plam qavariq to’plamdan iborat, ya’ni birinchi xossa baj ariladi (1 -chizma).

Endigi masala bu to’plamning shunday nuqtasini topish kerakki, F = x₁ - x₂ chiziqli funksiya max qiymatga ega bo’lsin. Tekislikda F bir xil qiymatlar qabul qiladigan nuqtalarning joylanishini topamiz. Buning uchun F = a deb olamiz. Bu holda x₁ - x₂ = a tenglama hosil bo’lib, bu F funksiya bir xil a qiymat qabul qiladigan to’g’ri chiziqdir. a ning o’rniga har xil

qiymatlar qo’yish bilan £ parallel to’g’ri chiziqlarni hosil qilamiz. Bu to’g’ri chiziqlarning har biriga sath chizig’i (ya’ni funksiya bir xil qiymatlar qabul qiluvchi to’g’ri chiziq) deyiladi.

Chiziqli funksiya koeffitsiyentlaridan tuzilgan q(1, -1) vektorni qaraymiz.

Bu vektorga perpendikulyar £ chiziqni o’tkazamiz (bu sath chiziqlardan biri) va uni o’ziga parallel mumkin bo’lgan yechimlar to’plami bilan kesishmay qolguncha siljitamiz. Bu yerda, masalada maksimal qiymat topilishi kerak bo’lsa, vektorning yo’nalishi bo’yicha, minimal qiymat topilishi kerak bo’lsa, vektorning yo’nalishiga qarama-qarshi tomonga siljitiladi.

£ to’g’ri chiziqni o’ziga-o’zini parallel qanchalik siljitilmasin, bari bir mumkin bo’lgan yechimlar to’plamini kesib o’taversa, chiziqli funksiya yuqoridan (minimal qiymatlar uchun quyidan) chegaralanmagan bo’ladi va

optimal yechimga ega bo’lmaydi. Qaralayotgan masalada £ chiziqni parallel siljitilganda ОАСДВ mumkin bo’lgan yechimlar to’plami bilan D nuqtada oxirgi umumiy nuqtada ega bo’lib, bu nuqtada funksiya maksimal qiymatga ega bo’ladi. Ma’lumki, bu nuqta x₁ - 2x₂ = 2, x₁ + x₂ = 8 to’g’ri chiziqlarning kesishgan nuqtasi bo’lib, ularni birgalikda yechib nuqtaning koordinatalarini aniqlaymiz:

f x₁ - 2 x₂ = 2 [ x₁ + x₂ = 8 2

3x1 = 18, x1 = 6, 6 - 2x₂ = 2, - 2x2 = -4, x₂ = 2 .

Shunday qilib, D nuqtaning x₁ = 6, x₂ = 2 koordinatalari masala yechimi bo’ladi.

F = 6 - 2 = 4.

max

Bu bilan chiziqli dasturlash masalasining 3-xossaning ham bajarilishini ko’rsatdik.

3. 
   Chiziqli dasturlash masalasini yechishning simpleks usuli. Payqash mumkinki, yechimlar ko’pburchagining shunday burchak nuqtasi mavjudki, bu nuqtada chiziqli funksiya optimal qiymatga ega bo’ladi. Yechimlar ko’pburchagining har bir burchak nuqtasiga birorta tayanch yechim mos keladi.
   

Tayanch yechim m ta chiziqli bog’lanmagan vektorlar sistemasi orqali aniqlanib, bu sistemada n ta A₁,A₂,...,A_n vektorlar qatnashadi. Optimal yechimni topish uchun faqat tayanch yechimlar tekshiriladi. Bunday masalada tayanch yechimlar sonining yuqori chegarasi Cm guruhlashlar soni bilan aniqlanadi. m va n lar katta sonlar bo’lganda optimal yechimni, hamma tayanch yechimlarni saralab (tekshirib) topish juda katta murakkablikka olib keladi. Shuning uchun, biror tartiblangan sxema bo’yicha bir tayanch yechimdan ikkinchi tayanch yechimga o’tish algoritmiga ega bo’lishga to’g’ri keladi. Bunday sxema bo’lib, simpleks usul hisoblanadi.

Chiziqli dasturlash masalasini simpleks usul bilan yechishga ko’pincha rejani (yechimni) ketma-ket yaxshilash usuli ham deb yuritiladi. Bunday atalishida usulning asosiy g’oyasi, quyidagi ketma-ket amalga oshiriladigan qadamlardir:

1. 
   qadam, boshlang’ich mumkin bo’lgan yechim topiladi;
   
2. 
   qadam, topilgan yechimning optimalligi tekshiriladi;
   
3. 
   qadam, yechim optimal bo’lmasa, 2-qadamda optimal yechimga yaqinroq boshqa mumkin bo’lgan yechimga o’tiladi. Keyin, yana 2-qadamga va hakozo optimal yechim olinguncha davom ettiriladi. Masala yechimga ega bo’lmasa yoki maqsadli funksiya yechimlar ko’pburchagida chegaralanmagan bo’lsa, simpleks usul bilan yechish jarayonida buni aniqlash imkoniyati yaratiladi.
   

Bazis rejani topish. Quyidagi chiziqli dasturlash masalasi qo’yilgan bo’lsin: z = c₁ x₁ + c₂x₂ +... + c_nx_n chiziqli funksiyaning

«11 ^x1 + ^a12 ^x2 + ... + ^a1n^xn = К ^a21 ^x1 + «22 ^x2 + ... + ^a2n^xn = К

a_m1 x + a_m2x₂ +... + ax_n = b_m, x,. > 0 (j = 1,2,...,n)

m1 1 m2 2 mn n m “ j

cheklash shartlarini qanoatlantiruvchi minimum qiymatini topish talab etiladi. Bunda b_} > 0, (j = 1,2,..., m). Bunday qo’yilgan masalaga chiziqli dasturlashning

kanonik masalasi deyiladi.

Cheklash shartlari m ta vektorlar bo’lsin. Bu holda

^Z = ^C1 ^x1 + ^C2^x2 + ... + ^Cn^xn , (5)

chiziqli funksiyaning

^a11 ^x1 + ^a12 ^x2 + ... + ^a1n^xn = К ^a21 ^x1 + ^a22 ^x2 + ... + ^a2n^xn = К

<sup>(6)

a</sup>m1 ^x1 + ^am2^x2 + ... + Vn = ^bm <sup>,

x</sup>j > ^0(j = l,²,...,«К ⁽⁷⁾

cheklash shartlarini qanoatlantiruvchi minimum qiymatni topish masalasi hosil bo’ladi. (6) sistemani vektor shaklida yozsak:

^x1 ^A1 + ^x2 ^A2 + ... + ^xm^Am + ^xm+1 ^Am+1... + ^x n^An = ^A0 ⁽⁸⁾


f_a >

1,m+1

a

1n

a

a

2,m+1

2n

A =

A =

m+1

A =

V⁰ J

V1 J

V ^a mn J

a

_V m,m+1 _J

Г ь"		Г1 ^
b2	, A =	0
V ^bm J		v^0,

yoyilma hosil bo’ladi, bunda

Л =

A₂ =

A₁,A₂,...,A_m vektorlar m o’lchovli fazoning chiziqli bog’lanmagan birlik vektorlari bo’ladi. Bular bu fazoning bazisini tashkil etadi. Shuning uchun, (8) yoyilmada bazis o’zgaruvchilari uchun x₁, x₂,...,x_m larni olib, ozod

x_m+₁, x_m+₂,..., x_n o’zgaruvchilarni 0 ga teng deb, hamda b_} > 0, (j = 1,2,...,m) ekanligini hisobga olib, A₁,A₂,...,A_m birlik vektorlar bo’lganligi uchun

^X0 ^(x1 ^b1, ^X2 ^b2

b

(9)

,x„

^{0, X}m+2 = ^0,...^{, X}n = °)

boshlang’ich rejani hosil qilamiz. (9) reja

^X1^A1 + ^X2 ^A2 + ... + ^Xm^Am = ^A0 ⁽¹⁰⁾

yoyilmaga mos kelib, A₁,A₂,...,A_m vektorlar chiziqli bog’lanmagan, demak boshlang’ich olingan reja tayanch reja ham bo’ladi.

Mavzuning tayanch tushunchalari Mumkin bo’lgan yechim, tayanch reja, maxsusmas reja, maxsus reja, optimal reja, yechimlar ko’pburchagi, sath chizig’i, simpleks usul, rejani ketma- ket yaxshilash, ochuvchi (kalit) element, yo’naltiruvchi (kalit) satr, yo’naltiruvchi (kalit) ustun, bosh satr, chiziqli dasturlashning kanonik masalasi, boshlang’ich reja, optimallik sharti, simpleks usul algoritmi, sun’iy bazis, aralash shartli masalalar.

Takrorlash uchun savollar

1. 
   Chiziqli dasturlash (CHD ) nima?
   
2. 
   Chiziqli dasturlash masalasi (CHDM) vektor formada qanday yoziladi?
   
3. 
   CHDM ning kanonik ko’rinishi nima?
   
4. 
   CHDMning geometrik tasvirini nechta o’zgaruvchi uchun ko’rsatish mumkin?
   
5. 
   Simpleks usulning mohiyati nimadan iborat?
   
6. 
   Simpleks usulning optimallik sharti qanday?
   
7. 
   Ochuvchi (kalit) element deb nimaga aytiladi?
   
8. 
   Yo’naltiruvchi (kalit) ustun va satr deb nimaga aytiladi?
   
9. 
   Bosh satr qanday satr?
   
10. 
    Maqsadli funksiya nima?
    
11. 
    Cheklash shartlarida qanday shartlar bo’lishi mumkin?
    
12. 
    (m+1) satr baholari qanday topiladi?
    
13. 
    Birinchi simpleks jadval qanday tuziladi?
    
14. 
    Qanday holda 2-simpleks jadvalni tuzishga o’tiladi?
    
15. 
    2-simpleks jadval qanday tuziladi?
    

16. 
    Chiziqli funksiyaning chegaralanmaganlik sharti simpleks jadvalda qanday ifodalanadi?
    
17. 
    Simpleks jadvallardan optimal yechimning yagonaligi qanday aniqlanadi?
    
18. 
    Sun’iy o’zgaruvchi qanday holda kiritiladi?
    
19. 
    Sun’iy bazis usuli nima?
    
20. 
    Qanday masalalarga aralash shartli masalalar deyiladi?
    
21. 
    Aralash shartli masalalar qanday masalaga keltiriladi?
    

Mustaqil ish uchun topshiriqlar

va minimum qiymatlarini geometrik

2. f = x₁ + 2 x₂
Ushbu CHDMning maksimum usulda toping.

1. f = 5x₁ + 3x₂,

4x₁ + 3x₂ > 12,

— 2x1 + 4x₂ < 8, x₁ < 5,

^x2 < ^4,

x₁ > 0, x₂ > 0.

x₁ + x₂ > 1,

— 3x1 + 6x₂ < 3, 5 x₁ — 2 x ₂ < 3, x₁ > 0, x₂ > 0.

2. 
   
   4. f = 4 x₁ + 2 x₂,
   f = 10x₁ + 6x₂,
   

x₁ + x₂ > 1,

7x₁ + 9x₂ < 63,

x₁ < 6, x2 < 5,

x₁ > 0, x₂ > 0.

^f = 3^x1 + ^x₂^,

x₁ + 2x₂ < 6, 5x1 — 4x₂ > —2, 7x₁ + 5x₂ > 35, x₁ > 0, x₂ > 0.

5x₁ + 3x₂ > 15, 3x₁ — 5x₂ < 15, x₁ + 2x₂ < 10, x₁ > 0, x₂ > 0.

6. f = 12 x₁ + 15x ₂

5

x₁ + x₂ < 6,

2x₁ + x₂ < 20, x₁ + 2x₂ < 10, x₁ > 0, x₂ > 0.

5Xj + 3x₂ < 15,

2 x₁ + 6 x₂ < 12,

<^x2 < ^2,

2x₁ < 6, x₁ > 0, x₂ > 0.

10-19 masalalarda ikki xildagi mahsulot ishlab chiqarish uchun uch turdagi xom ashyo ishlatiladi. i (i = 1,2,3) turdagi xom ashyo miqdori b_i. Bir birlik j (j = 1,2) xildagi mahsulotni ishlab chiqarish uchun zarur bo’lgan i (i = 1,2,3) turdagi xom ashyo miqdori (a_v), xom ashyo zahirasi b va 1 birlik mahsulotni realizatsiya qilishdan olinadigan foyda (c_}), quyidagi matritsa bilan berilgan bo’lsin:

f
^a11	^a12	^b1
^a21	^a22	^b2
^a31	^a32	^b3
v ^c1	^C2	f

Umumiy foyda f eng katta bo’ladigan mahsulotlar ishlab chiqarish rejasini simpleks usuldan foydalanib tuzing:

	f		Л		f		Л
	10	9	1870		15	4	1095
10.	5	11	1455	11.	11	5	855
	4	15	1815		9	10	1080
	v^1	9	f j		v3	2	f j
	f				f		Л
	8	2	840		11	3	671
12.	6	3	870	13.	8	4	588
	3	2	560		5	3	423
	v ^6	2	f J		v5	2	f j
	f				f		Л
	2	1	438		16	4	784
14.	3	6	747	15.	8	7	552
	3	7	812		5	9	567
	v7	5	f j		v4	6	f j

	f		>		f		Л
	2	3	428		4	3	440
16.	3	6	672	17.	3	4	393
	2	8	672		3	5	450
	v ^3	8	f J		v ^6	5	f j

	4	3	480		12	3	684
18.	3	4	444	19.	10	5	690
	2	6	556		3	6	558
	v ^2	4	f )		v ^2	3	f ,

20. z = 5Xj + 3x₂ + 4x₃ - x₄ chiziqli funksiyaning

x₁ + 3x₂ + 2 x₃ + 2 x₄ = 3, 2 xj + 2 x2 + x3 + 2 x4 = 3,

x > 0, (j = 1,2,3,4)

cheklash shartlarini qanoatlantiruvchi maksimum qiymatini sun’iy bazis usulidan foydalanib toping.

21. 
    z = - x₁ + 3x₂ + 2 x₃ chiziqli funksiyaning
    

xj + x₂ + 2x3 > —5, 2x₁ - 3x₂ + x₃ < 3,

2x₁ - 5 x₂ + 6x₃ < 5,

x > 0, (j = 1,2,3)

cheklash shartlari sistemasini qanoatlantiruvchi minimum qiymatini simpleks usul bilan toping.

21. 
    z = x₁ - 2x₂ + 3x₃ -10x₄ chiziqli funksiyaning
    

x₁ + x₂ + 2x₃ - 6x₄ = 1, x₁ + x₂ + 4x₃ - 8 x₄ = 1,

4x_j + 2x₂ + x₃ - 4x₄ = 3,

x > 0, (j = 1,2,3,4)

cheklash shartlari sistemasini qanoatlantiruvchi maksimum qiymatini toping. z = 5 x_j + 2x₂ - x₃ chiziqli funksiyaning

23.

2x_j + x₂ + x₃ < 5, 3x_j + 2 x₂ + x₃ = 6, 5x_j + 3x₂ + 4x₃ > 1,

x_; > 0, (j = 1,2,3)

cheklash shartlari sistemasini qanoatlantiruvchi maksimum qiymatini toping. z = 2 x_j + 3x₂ + (^2) x₃ chiziqli funksiyaning

24.

2x_j + x₂ + 3x₃ > 6,

2x_j + 4x₂ + 3x₃ > 10, 3x_j + 4x₂ + 2x₃ > 12, x, > 0, (j = 1,2,3)

cheklash shartlarini qanoatlantiruvchi minimum qiymatini toping.

ADABIY OTLAR

1. 
   Safayeva Q., Beknazarova N. Operatsiyalarni tekshirishning matematik usullari. 1-qism. - Toshkent, O’qituvchi, 1984.
   
2. 
   Karasev A.I., Aksyutina Z.M., Saveleva T.I. Kurs visshey matematiki dlya ekonomicheskix vuzov. Chast II. - M.: Visshaya shkola, 1982, 320 s.
   
3. 
   Kuznesov Yu.N. i dr. Matematicheskoye programmirovaniye. - M.: Visshaya shkola, 1980, 300 s.
   
4. 
   Malik G.S. Osnovi ekonomiko-matematicheskiye metodi v planirovanii.
   

• 
  M.: Visshaya shkola, 1988, 279 s.
  

5. 
   Arzamassev A.A., Shestakov A.A. Kratkiy kurs visshey matematiki. - M.: Sentorosoyuz, 1965, 460 s.
   
6. 
   Taxa X. Vvedeniye v issledovaniye operatsii. Tom 1,2. - M.: Mir, 1985.
   
7. 
   Kuznesov A.V., Sakovich V.A., Xolod N.I. Visshaya matematika. Matema­ticheskoye programmirovaniye, Izd-vo: Visheyshaya shkola, 2001 g., 352 str.
   

2.