T. I. Umarov s. I. Xudoyberdiyev iqtisodiy matematik usullar va

m

Z(X0) = CX0 =2c,x, ,

i=1

m

^Zj = ^C6^Xi = Z ^ci^xj ^{, j} = ^1,2,...^{,n ,}

i=1

bunda C_t bazis vektorlarining chiziqli funksiyadagi mos koeffitsiyent-laridir. Shunday qilib, 1-simpleks jadvalni hosil qilamiz.

1-simpleks jadval.

i

Bazislar

•Й ^ oq

A

C1

C 2

C

C m

C m+1

^Ci

Ck

Cn

4

A2

4

Am

A m+1

^Aj

Ак

Ап

1

A

Q

Xj

1

0

0

0

^X1,m+1

^X1 j

^X1k

^X1n

2

4

C 2

^X2

0

1

0

0

^X2,m+1

^X2 j

^X2k

^X2n

l

А

Cl

^Xl

0

0

1

0

^Xl ,m+1

^Xu

^Xlk

^Xln

m

Am

Cm

^Xm

0

0

0

1

X m , m +1

^Xm

^Xmk

X mn

m+

1

^ZmA ^-Cn

Z

0

0

0

0

Z _- C

,,

Z„ - C„

m?f-1

Birinchi simpleks jadval tuzilgandan keyin uning (m+1) satrini qaraymiz. Chiziqli dasturlash masalasi minimumga yechilayotgan bo’lsa, barcha j = 1,2,...,n lar uchun ^zj - ^cj * ⁰ yoki masala maksimumga yechilayotgan

bo’lsa, Z_} - Cj > 0 bo’lsa, tayanch yechim optimal bo’ladi va chiziqli funksiyaning optimal qiymati Z (X ₀) dan iborat bo’ladi.

Chiziqli dasturlash masalasi minimumga yechilayotgan bo’lib, Z, -C, > 0 bo’lsa, X₀ yechim optimal bo’lmaydi va bu bahoga mos vektorni

bazisga kiritib yechimni yaxshilash mumkin, ya’ni chiziqli funksiyaning oldingi qiymatidan kichikroq qiymatini topish mumkin bo’ladi.

Musbat baholar bir nechta bo’lsa, ulardan eng kattasini bazisga kiritiladi. Eng kattalari bir nechta bo’lsa, ulardan min(C,) bo’lgani oldin bazisga

kiritiladi. Hech bo’lmaganda bitta musbat Z, -C, > 0 baho uchun mos vektor yoyilmasidagi х, koeffitsiyentlari ichida manfiylari bo’lsa, chiziqli funksiya yechimlar ko’pburchagida chegarlanmagan bo’ladi.

Eng katta 9₀, (Z, - C,) = 9_0k (Z_k - C_k) bo’lsin, ya’ni maksimal qiymat k - vektor uchun bo’lsin, m < k < n. Bu holda A_k vektor bazisga kiritilib, min(x_i/x_ik) (x_ik > 0) mos kelgan vektor bazisdan chiqariladi. min(xjx_ik) = x,/x_lk

bo’lsin, ya’ni l - satrdagi A_t vektor bazisdan chiqariladi. x_lk element ochuvchi (kalitli) element deyiladi va bu elementga mos ustun va satrlar yo’naltiruvchi (kalitli) deb ataladi.

Yangi tayanch yechim va vektorlar yangi bazisdagi yoyilmasi (j = 1,2,..., n uchun)

^xj • ,

^xy = ^xj ^xk^{, i} *<sup>1

x</sup>

Ik

x

xj =^, (i = l)

^xlk

formulalar yordamida topiladi. Bu Jordan-Gauss noma’lumlarni to’la yo’qotish formulalaridir, haqiqatan j = k uchun

_x

^xjk = ^x„ —~^x,k = ^{0, (i} *^l), x

xjk =~^JL = 1, (i = l), x

hosil bo’ladi, ya’ni bazisga kiritilgan vektor yoyilmasi uchun ochuvchi element koeffitsiyenti 1 bo’lib qolgan koeffitsiyentlari 0 lardan iborat bo’ladi.

Shunday qilib, A₀, A, (j = 1,2,...,n) vektorlarning yangi bazisdagi

yoyilmasi koeffitsiyentlarini, yangi tayanch yechim bahosi qiymatini hamda chiziqli funksiya qiymatini topish uchun yo’naltiruvchi satr hamma

elementlarini yechuvchi elementga bo’lamiz va bir marta to’liq Jordan-Gauss metodidan foydalanib, 2-simpleks jadvalni tuzamiz.

2-simpleks jadval.

C

C

C

C

C

C

C

r

a

C

0

^za

B

^za

B

m +1

k

2

m

n

1

^C1

1

0

0

0

X

X,

X

X

X

1n

2

C

0

1

0

0

X

X

X,

X

2,m+1

2j

2

C

l

0

0

0

1

X

X,

X

X„

l ,m+1

C

0

0

1

0

X

X,

x„

x„

m

ml

m

7’ _-C

m+1 m+1

Z'

(Л

Z'

(Л

^Zj - ^Cj

Z, - C'

z ' - C.

m+1

0

0

0

0

Hisoblashlarning to’g’ri bajarilganligini

Z (X 0) = c₆x 0,

C,

Z

formulalar yordamida nazorat qilish mumkin.

2-simpleks jadvalning (m+1) satrida hamma baholar Z_} -C_} < 0 bo’lsa

olingan Х 0 yechim optimal bo’ladi. Musbat baholar bo’lsa, keyingi tayanch

yechimni topishga o’tiladi. Jarayon optimal yechimni olguncha davom ettiriladi yoki chiziqli funksiya chegaralanmaganligi ko’rsatiladi. Optimal yechim baholar ichidagi 0 baho fakat bazis vektorlariga mos kelsa, optimal yechim yagona bo’ladi, 0 baho bazisda bo’lmagan vektorga ham mos kelsa, umuman optimal yechim yagona bo’lmaydi.

Chiziqli dasturlash masalasida chiziqli funksiyaning maksimum qiymati topilayotgan bo’lsa va mm(Z_} - C_j) < 0 baholar bir nechta bo’lsa, ulardan

min( C_}) bo’lgan vektor oldin bazisga kiritiladi. Bu holda ham simpleks usul jarayoni, chiziqli funksiyaning minimum qiymatini topishdagidek bo’ladi. 1-misol. z = 4 Xj + 6 x₂ chiziqli funksiyaning 16xj + 4x₂ < 784,

- 8x^ — 7x2 > —552,

5x_x + 9x₂ < 567, x_x > 0, x₂ > 0

cheklash shartlari sistemasini qanoatlantiruvchi maksimum qiymatini toping.

Yechish. Boshlang’ich tayanch yechim qaralgan usulda ozod hadlarning faqat musbat qiymatlarida topilganligi uchun ikkinchi tengsizlikni (-1)ga ko’paytirib

16x₁ + 4x₂ < 784,

• 8x₁ + 7x₂ < 552,

  
  

5x₁ + 9х₂ < 567, x > 0, х₂ > 0 cheklash shart.1a.rini hosil qilamiz. Endi tengsizliklardan tengliklarga o’tamiz: 16x₁ + 4x₂ + x₃ = 784,

• 8x₁ + 7x₂ + x₄ = 552,

  
  

5x₁ + 9x₂ + x₅ = 567, x_j > 0 (j = 1,2,3,4,5).

Oxirgi sistemani vektor formada yozamiz:

	17841		^161		I 41		Г11		Г 01		Г 01
Ao =	552	, Ai =	8	, a2 =	7	, A3 =	0	, A4 =	1	, A5 =	0
	v^567У		v^5 )		v ^9 )		v ^0 )		v ^0 )		v^1 )

A₃, A₄, A₅ birlik vektorlarni boshlang’ich tayanch yechim uchun qabul qilib, х₁, X₂ noma’lumlarni 0 ga teng deymiz. Natijada X₀ =(xj = 0, x₂ = 0, x₃ = 784, x₄ = 552, x₅ = 567) tayanch yechimni olmiz, bunga