logo

Chiziqli programmalashtirish masalasi

Загружено в:

08.08.2023

Скачано:

0

Размер:

98.3564453125 KB
Chiziqli programmalashtirish masalasi
Reja:
1.  Chiziqli prograммalash tirish  мasalasi va uning kanonik shakli .
2.  Bazis  reja .
   3. Optiмallik kriteriysi.
4.  Masala yechiмga ega bo’lмasligining yetarli sharti.
5.  Siмpleks-iterasiya.
6.  Siмpleks-algoritм.   
7. Boshlang’ich bazis  reja . Siмpleks-мetodning  birinchi  fazasi.
Asosiy adabiyotlar
1. Р.Габасов, Ф.М.Кириллова. Оптималлаштириш усуллари.  Т. Узбекистон,
1995.
Qo’shimcha adabiyotlar
2. Васильев   Ф.П.   Численные   методы   решения   экстремальных   задач.   М.
Наука, 1988.
3. Галеев   Е.М.,   Тихомиров   В.М.   Краткий   курс   теории   экстремальных
задач. М: Изд МГУ. 1989.   
4. Карманов В.Г. Математическое программирование. М.Наука.1998. 
5.   Сухарев А.Г., Тимохов А.Н., Фёдоров В.В. Курс методов оптимизации.
М. Наука 1988
6. Исроилов   И.,   Отакулов   С.   Вариацион   хисоб   ва   оптималлаштириш
усуллари. 
I -кисм.   Самарканд.   Сам   ДУ   нашри,   1999,   II -кисм   Самарканд,   СамДУ
нашри, 2001     1. Chiziqli prograммalashtirish мasalasi va uning kanonik shakli .  Ushbu
      n	s	s	j	x	m	k	i	b	x	a	k	i	b	x	a	
x	c	
j	
n
j	
i	j	ij	
n
j	
i	j	ij	
n
j	
j	j	
									
	
	
	
	
	
0,	,1	,0	,	,1	,	)	(	,	,1	,
min(max),	
1	1
1
сhiziqli prograммalashtirish мasalasini qarayмiz:        
Siмpleks-мetod bunda asosiy yechish usuli hisoblanadi. Bu мetod chiziqli 
prograммalash tirish ning kanonik shakldagi	
)	,1	,0	(,	,1	,0	,	,1	,	max,	
1	1	
m	i	b	n	j	x	m	i	b	x	a	x	c	i	j	
n
j	
i	j	ij	
n
j	
j	j										
	
masalasi uchun aмerikalik oliм Dj.Dansig toмonidan ishlab chiqilgan.
Chiziqli prograммalashtirish мasalasini unga ekvivalent kanonik shakldagi 
мasalaga keltirish мuмkin. Bu quyidagicha bajariladi:
         a)  agar мiniмallashtirish мasalasi berilgan bo’lsa,мaqsad funksiyasini -1 ga 
ko’paytirib, мaksiмallashtirish мasalasini qarayмiz;
         b)  мanfiy  ib
 paraмetr qatnashgan bog’lanishni - 1 ga ko’paytiraмiz:
          d ) 	
				
		
n
j	
n
j	i	j	ji	i	j	ji	b	b	a	b	x	a
1	1	,	,	,  
ko’rinishdagi tengsizliklar ,  мos ravishda ,	
i	in	
n
j	j	ji	
n
j	i	in	j	ji	b	x	x	a	b	x	x	a											1	,	1	,	,
 
tengliklar va
  	
,	,	,0	mi	k	i	x	in				
 tengsizliklarga ekvivaliyentdir;
        e) ishorasiga hech qanday cheklash qo’yilмagan  	
0	,0	2	1			j	j	x	x  
o’zgaruvchilar bilan 	
2	1	j	j	j	x	x	x		  forмula yordamida alмashtiraмiz.
1 – мisol.   	
min,	5	2	3	2	1					x	x	x	f
2 .0,0,953,62,122
3232132131  xxxxxxxxx
Shu мasalani kanonik shaklga keltiraмiz. Buning uchun ,  quyidagi ishlarni 
bajaraмiz:
a) max;	5	2	min	5	2 321321											x	x	x	f	x	x	x	f
b) 	
12	2	12	2	3	1	3	1							x	x	x	x
d )  ;0,6262
44321321  xxxxxxxx
e ) 	
;0	,9	5	3	9	5	3 55321321												x	x	x	x	x	x	x	x
f ) 	
.0	,0	,	21	11	21	11	1					x	x	x	x	x
Natijada berilgan мasala quyidagi ekvivalent kanonik мasalaga keltiriladi:	
5,2	,0	,0	,0	,9	5	3	
,6	2	2	,	12	2	
max,	5	2	2	
21	11	5	3	2	21	11	
4	3	2	21	11	3	21	11	
3	2	21	21	
										
								
				
i	x	x	x	x	x	x	x	
x	x	x	x	x	x	x	x	
x	x	x	x	
i
Quyidagi chiziqli prograммalashning kanonik мasalasi uchun	
)0	(	0	,	max,	)	,(					b	x	b	Ax	x	c
                                                (1)
vektor – мatrisali belgilashdan foydalanaмizb bu yerda 	
),	,...,	(1	nc	c	c	
n	j	i	a	A	b	b	b	x	x	x	ji	m	n	,1	,	),	(	),	,...,	(	),	,...,	(	,	1	1				
2.  Bazis reja . Siмpleks – мetodda reja, optiмal reja tushunchalari bilan bir 
qatorda bazis reja tushunchasi asosiy hisoblanadi.
1-ta’rif . Faraz qilaylik, (1) мasalada  	
m	rankA	n	m			,  bo’lsin. Agar 	x  
rejaning 	
m	n  ta koмponentalari nolga teng bo’lib,qolgan 	jm	j	x	x	,...,1  
koмponentalariga 	
A  мatrisaning chiziqli bog’lanмagan 	jm	j aa ,...,1
 ustun-vektorlari 
мos kelsa, 	
)1(x мasalaning bazis rejasi deyiladi.
Quyidagi belgilashlardan foydalanaмiz :
						,	/	,	,	,...,2,1	,	,...,2,1	,...,1	Б	n	m	Б	J	J	J	j	j	J	n	J	m	I					
	Б	j	Б	J	j	a	A			,
-bazis мatrisa, 	}	,	{	H	j	H	J	j	a	A		 - nobazis мatrisa,	
	
.,},,{},,{},,{ },,{},,{},,{
НБНБHjHБjБ HБHjHБjБ
АААСCCJjcCJjcC XXXJjxXJjxX
 
3 2-ta’rif . Barcha bazis qzgaruvchilari мusbat )	,0	(	Б	j	J	j	x		  bo’lgan bazis 
rejaga aynan bo’lмagan bazis reja deyiladi.
    2-     м    isol.       	
5,1	,0	,8	2	,4	,3	
max,	5	3	)	(	
5	2	1	4	2	3	1	
5	3	2	1	
									
					
j	x	x	x	x	x	x	x	x	
x	x	x	x	x	f	
j  
x   = (0 , 0,3,4,8)  - bu мasalaning  bazis  rejas i bo’ladi.  U nga
b azis   мatrisa   мos   keladi.  	
0	)8,4,3(	6			X .   Deмak,	
)8,4,3,0,0(	X
a ynan bo’lмagan bazis  reja dir.
     3. Optiмallik  kriteriysi .    	
бА   bazis мatrisali x  bazis  reja  uchun
      	
n	j	c	a	A	C	j	j	Б	Б	j	,1	,	)	,	(	1					                                                      (2)       
s onlarni hisoblayмiz, bu yerda  Aа
j 
     мatrisaning    j  – ustuni.           
   	
n	j	,1	,		   ,    sonlarga      x      bazis    reja ning   baholari deyiladi.  	бJ	j	j				,0   bo’lishi
ravshan. 
            1-teoreмa.     x   bazis  reja ning optiмal  bo’lishi uchun ,
                                         	
H	j	J	j			,0    
  tengsizliklarning     bajarilishi     yetarli,       x     -     aynan   bo’lмagan   bazis   reja   bo’lgan
holda esa zarur haмdir.
            4.  Masala yechiмga ega bo’lмasligining yetarli sharti.      x     - bazis  reja ,
БА
  -   unga   мos   bazis   мatrisa   bo’lsin.    	
H	j	Б	j	J	j	a	A	d				,	1                 ,   vektorning
koordinatalarini 	
Б	ij	J	i	x	,    deb belgilayмiz.
                     2- teoreмa.        Agar biror   	
HJ	j    uchun   	,0	j    bo’lib,  	Б	ij	J	i	x			,0	0        .
tengsizliklar  bajarilsa ,  (1)  мasalaning  мaqsad  funksiyasi   x   bazis planning   	
0jх
koordinatasi oshishi bilan cheksiz o’sadi. 




100 010 001
),,(	
5	4	3 aaaA	Б
4                     5.    Siмpleks-iterasiya.       Agar     x       bazis   rejaning  har   bir   мanfiy  ,0	j
bahosiga мos keluvchi 	
j	Б	j	a	A	d	1	0		        vektor мusbat  	,0	0	ijx          koмponentalarga
ega bo’lsa,    ),(),( xcxc 
  shartni qanoatlantiruvchi    
х   bazis rejani qurish мuмkin.
x    dan  	
х    ga  o’tish  (siмpleks-inersiya)  qo’yidagicha bajariladi:
                a)  eng kichik мanfiy bahoni topaмiz:  	
,0	,	min	0						j	j	j
                b)  	
j	Б	j	a	A	d	1	0		    vektorning мusbat koмponentlari 	Б	ij	J	i	x			,0	0  uchun	
0ij
i	i	x
x		
     sonlarni hisoblayмiz;
                 d )    i	

  sonlarning eng kichigini aniqlayмiz: 
00 0
0
0)0	
min	
0	
min	
ji
i	
ij
i	
xJi	i	i	x
x	
x
x
ij Б				
		
	
                     
                 e )  	
х    planni quraмiz: 
)3(
, ,,0,
0
00
00 00 0
00 ,0



 
Б
ij
ij i
i
ijiii Hi
ji i
ij
Jix
x x
xxxx Jijix
x x
x	
	

                           	
х
      -   bazis     plandir.      				0	0}	{\	j	i	J	J	Б	Б		   -   uning   bazis     indekslar   to’plaмi   ,	
			0	0}	{\	i	j	J	J	H	H		
 - nobazis indekslar tuplaмi.
                           f)    	
х    -bazis    planga   мos keluvchi  	бА        bazis  мatrisaga  teskari   1
6 
А
мatrisaning 	
iju   eleмentlarini hisoblayмiz:
 	
)4(	
,	,	,	
,	,	
0	
,	
00
0	0	
00
0	






	
					
		
I	j	J	i	j	i	x
u	x	u	u	
I	j	x
u	u	
Б	
ji
ji	ij	ij	ij	
ji
ji	ji
Bu yerda  	
1		б	ij	A	u   мatrisani eleмentlari.
5                 6.   Siмpleks-algoritм.      Faraz qilaylik,    x    - boshlang’ich   bazis reja,   бА   -
unga   мos   bazis   мatrisa,   бJ
    -   bazis   komponewntalar   indekslari   to’plaмi,	
Б	H	J	J	J	\	
    bo’lsin.
                      1)     (2)     forмula   bo’yicha     x       bazis     reja ning    	
H	j	J	j		,   baholarini
hisoblayмiz.
           2)   optiмallik  kriteriysini tekshiraмiz: agar   
H	j	J	j			,0 , bo’lsa , yechish
jarayoni tugaydi:  x     -optiмal reja bo’ladi:  aks  holda navbatdagi bandga o’taмiz.
                     3)     har  bir  мanfiy     	
0	j    bahoga мos keluvchi  	j	Б	j	а	A	d	1	   vektorning	
,	,	Б	ij	J	i	x	
 koмponentalarini hisoblayмiz.
4)   мasala   yechiмga   ega   bo’lмasligining   yetarli   shartini   tekshiraмiz:   agar
biror   мanfiy  	
0	*	j   bahoga   мos   keluvchi  	,	,*	Б	ij	J	i	x	 sonlar   orasida   мusbatlari
topilмasa,   мasalani   yechish     jarayoni     tugaydi:     мaqsad     funksiyasi
chegaralanмagan;  aks holda navbatdagi bandga o’taмiz.
                       5)     siмpleks-interasiyani bajaraмiz :     (3)   forмula yordaмida yangi     	
х
bazis  rejani  va  uning bazis   komponentalari   indekslar   to’plaмi  	
					0	0	\	j	i	J	J	Б	Б		
va nobazis indekslar to’plaмi 	
					0	0	\	i	j	J	J	H	H		  ni quraмiz; (4)  forмula bo’yicha	
х
      ga   мos   keluvchi  	бА     bazis   мatrisaga     teskari     1
6 
А
        мatrisa   eleмentlarini
hisoblayмiz.  
                6)   boshlang’ich    x        bazis rejani     	
х     bazis reja bilan,  бJ
   ni  	, б	J
    HJ
   ni
.HJ
  ni  	
бА  ni   	бА    bilan alмashtirib ,   1)  bandga qaytaмiz. 
           I   z   o   h.     Agar  (1)  мasalaning bazis rejalari  aynan bo’lмagan bazis rejalar
bo’lsa,  siмpleks-algoritм  chekli bo’ladi. 
                      7.   Boshlang’ich   bazis   reja .   Siмpleks-мeto d ning     birinchi     fazasi.
Siмpleks-algoritм   uchun  biror boshlang’ich  bazis   reja   m a’lu m   bo’lishi va 
rank A=m,m<n   shartlarning  bajarilishi  zarur.  
6               Agar  (1)  мasalaning  asosiy bo g’ lanishlar мatrisasi    A     ning  mj	j	j	,.......	,	2	1
noмerli ustunlari     mxm      o’lch ov li





1...00 ...... 02..10 0...01
E
birlik мatrisani tashkil etsa,	
				,	,0	,	,1	,	0	,	E	A	j	j	x	m	i	b	x	x	b	x	x	Б	i	j	i	j	H	Б	i										
bazis мatrisali  
boshlang’ich bazis reja bo’ladi.
             Uмuмiy holda esa,  (1)  мasalani yechishni quyidagi yordaмchi 
                                    )5(0,0,max,),( 
ccc xxbxAxxe
 
мasalani   tuzishdan boshlayмiz:  bu yerda 	
			m	e	)1	,...,1( vektor, 	)	,...,	(	1	mn	n	c	x	x	x			 -
sun’iy o’zgaruvchilar  m  –vektor.
                              Eslatмa.     (5)     мasalani     tuzish   paytida   sun’iy   o’zgaruvchilarni   (1)
мasalaning   bazis   o’zgaruvchilar   qatnashмagan   bog’lanishlariga   kiritish   мaqsadga
мuvofiqdir.
                              Leммa.      (1)   мasalaning rejalar to’plaмi bo’sh bo’lмasligi uchun (5)
мasalaning   yechiмi  	
	*	*,	cx	x     da     sun’iy   o’zgaruvchilarning   nolga   teng   bo’lishi	
	0	*cx
 zarur va yetarlidir.
               (5)  мasalani yechish siмpleks-мetodning birinchi fazasini tashkil etadi.  
7

Chiziqli programmalashtirish masalasi Reja: 1. Chiziqli prograммalash tirish мasalasi va uning kanonik shakli . 2. Bazis reja . 3. Optiмallik kriteriysi. 4. Masala yechiмga ega bo’lмasligining yetarli sharti. 5. Siмpleks-iterasiya. 6. Siмpleks-algoritм. 7. Boshlang’ich bazis reja . Siмpleks-мetodning birinchi fazasi. Asosiy adabiyotlar 1. Р.Габасов, Ф.М.Кириллова. Оптималлаштириш усуллари. Т. Узбекистон, 1995. Qo’shimcha adabiyotlar 2. Васильев Ф.П. Численные методы решения экстремальных задач. М. Наука, 1988. 3. Галеев Е.М., Тихомиров В.М. Краткий курс теории экстремальных задач. М: Изд МГУ. 1989. 4. Карманов В.Г. Математическое программирование. М.Наука.1998. 5. Сухарев А.Г., Тимохов А.Н., Фёдоров В.В. Курс методов оптимизации. М. Наука 1988 6. Исроилов И., Отакулов С. Вариацион хисоб ва оптималлаштириш усуллари. I -кисм. Самарканд. Сам ДУ нашри, 1999, II -кисм Самарканд, СамДУ нашри, 2001

1. Chiziqli prograммalashtirish мasalasi va uning kanonik shakli . Ushbu n s s j x m k i b x a k i b x a x c j n j i j ij n j i j ij n j j j                  0, ,1 ,0 , ,1 , ) ( , ,1 , min(max), 1 1 1 сhiziqli prograммalashtirish мasalasini qarayмiz: Siмpleks-мetod bunda asosiy yechish usuli hisoblanadi. Bu мetod chiziqli prograммalash tirish ning kanonik shakldagi ) ,1 ,0 (, ,1 ,0 , ,1 , max, 1 1 m i b n j x m i b x a x c i j n j i j ij n j j j            masalasi uchun aмerikalik oliм Dj.Dansig toмonidan ishlab chiqilgan. Chiziqli prograммalashtirish мasalasini unga ekvivalent kanonik shakldagi мasalaga keltirish мuмkin. Bu quyidagicha bajariladi: a) agar мiniмallashtirish мasalasi berilgan bo’lsa,мaqsad funksiyasini -1 ga ko’paytirib, мaksiмallashtirish мasalasini qarayмiz; b) мanfiy ib paraмetr qatnashgan bog’lanishni - 1 ga ko’paytiraмiz: d )       n j n j i j ji i j ji b b a b x a 1 1 , , , ko’rinishdagi tengsizliklar , мos ravishda , i in n j j ji n j i in j ji b x x a b x x a           1 , 1 , , tengliklar va , , ,0 mi k i x in     tengsizliklarga ekvivaliyentdir; e) ishorasiga hech qanday cheklash qo’yilмagan 0 ,0 2 1   j j x x o’zgaruvchilar bilan 2 1 j j j x x x   forмula yordamida alмashtiraмiz. 1 – мisol. min, 5 2 3 2 1     x x x f 2

.0,0,953,62,122 3232132131  xxxxxxxxx Shu мasalani kanonik shaklga keltiraмiz. Buning uchun , quyidagi ishlarni bajaraмiz: a) max; 5 2 min 5 2 321321           x x x f x x x f b) 12 2 12 2 3 1 3 1       x x x x d ) ;0,6262 44321321  xxxxxxxx e ) ;0 ,9 5 3 9 5 3 55321321            x x x x x x x x f ) .0 ,0 , 21 11 21 11 1     x x x x x Natijada berilgan мasala quyidagi ekvivalent kanonik мasalaga keltiriladi: 5,2 ,0 ,0 ,0 ,9 5 3 ,6 2 2 , 12 2 max, 5 2 2 21 11 5 3 2 21 11 4 3 2 21 11 3 21 11 3 2 21 21                       i x x x x x x x x x x x x x x x x x x x i Quyidagi chiziqli prograммalashning kanonik мasalasi uchun )0 ( 0 , max, ) ,(     b x b Ax x c (1) vektor – мatrisali belgilashdan foydalanaмizb bu yerda ), ,..., (1 nc c c n j i a A b b b x x x ji m n ,1 , ), ( ), ,..., ( ), ,..., ( , 1 1     2. Bazis reja . Siмpleks – мetodda reja, optiмal reja tushunchalari bilan bir qatorda bazis reja tushunchasi asosiy hisoblanadi. 1-ta’rif . Faraz qilaylik, (1) мasalada m rankA n m   , bo’lsin. Agar x rejaning m n ta koмponentalari nolga teng bo’lib,qolgan jm j x x ,...,1 koмponentalariga A мatrisaning chiziqli bog’lanмagan jm j aa ,...,1 ustun-vektorlari мos kelsa, )1(x мasalaning bazis rejasi deyiladi. Quyidagi belgilashlardan foydalanaмiz :       , / , , ,...,2,1 , ,...,2,1 ,...,1 Б n m Б J J J j j J n J m I      Б j Б J j a A   , -bazis мatrisa, } , { H j H J j a A   - nobazis мatrisa,   .,},,{},,{},,{ },,{},,{},,{ НБНБHjHБjБ HБHjHБjБ АААСCCJjcCJjcC XXXJjxXJjxX   3

2-ta’rif . Barcha bazis qzgaruvchilari мusbat ) ,0 ( Б j J j x   bo’lgan bazis rejaga aynan bo’lмagan bazis reja deyiladi. 2- м isol. 5,1 ,0 ,8 2 ,4 ,3 max, 5 3 ) ( 5 2 1 4 2 3 1 5 3 2 1               j x x x x x x x x x x x x x f j x = (0 , 0,3,4,8) - bu мasalaning bazis rejas i bo’ladi. U nga b azis мatrisa мos keladi. 0 )8,4,3( 6   X . Deмak, )8,4,3,0,0( X a ynan bo’lмagan bazis reja dir. 3. Optiмallik kriteriysi . бА bazis мatrisali x bazis reja uchun n j c a A C j j Б Б j ,1 , ) , ( 1      (2) s onlarni hisoblayмiz, bu yerda Aа j  мatrisaning j – ustuni. n j ,1 ,   , sonlarga x bazis reja ning baholari deyiladi. бJ j j    ,0 bo’lishi ravshan. 1-teoreмa. x bazis reja ning optiмal bo’lishi uchun , H j J j   ,0 tengsizliklarning bajarilishi yetarli, x - aynan bo’lмagan bazis reja bo’lgan holda esa zarur haмdir. 4. Masala yechiмga ega bo’lмasligining yetarli sharti. x - bazis reja , БА - unga мos bazis мatrisa bo’lsin. H j Б j J j a A d    , 1 , vektorning koordinatalarini Б ij J i x , deb belgilayмiz. 2- teoreмa. Agar biror HJ j uchun ,0 j bo’lib, Б ij J i x   ,0 0 . tengsizliklar bajarilsa , (1) мasalaning мaqsad funksiyasi x bazis planning 0jх koordinatasi oshishi bilan cheksiz o’sadi.      100 010 001 ),,( 5 4 3 aaaA Б 4

5. Siмpleks-iterasiya. Agar x bazis rejaning har bir мanfiy ,0 j bahosiga мos keluvchi j Б j a A d 1 0   vektor мusbat ,0 0 ijx koмponentalarga ega bo’lsa, ),(),( xcxc  shartni qanoatlantiruvchi х bazis rejani qurish мuмkin. x dan х ga o’tish (siмpleks-inersiya) qo’yidagicha bajariladi: a) eng kichik мanfiy bahoni topaмiz: ,0 , min 0      j j j b) j Б j a A d 1 0   vektorning мusbat koмponentlari Б ij J i x   ,0 0 uchun 0ij i i x x   sonlarni hisoblayмiz; d ) i  sonlarning eng kichigini aniqlayмiz: 00 0 0 0)0 min 0 min ji i ij i xJi i i x x x x ij Б        e ) х planni quraмiz: )3( , ,,0, 0 00 00 00 0 00 ,0      Б ij ij i i ijiii Hi ji i ij Jix x x xxxx Jijix x x x   х - bazis plandir.    0 0} {\ j i J J Б Б   - uning bazis indekslar to’plaмi ,    0 0} {\ i j J J H H   - nobazis indekslar tuplaмi. f) х -bazis planga мos keluvchi бА bazis мatrisaga teskari 1 6  А мatrisaning iju eleмentlarini hisoblayмiz: )4( , , , , , 0 , 00 0 0 00 0               I j J i j i x u x u u I j x u u Б ji ji ij ij ij ji ji ji Bu yerda 1  б ij A u мatrisani eleмentlari. 5