Н. Ш. Альжанова Х. К. Сәбит

Экономикалық-математикалық әдістер 
 
12
n
j
x
b
x
a
x
a
x
a
b
x
a
x
a
x
a
b
x
a
x
a
x
a
j
m
n
mn
m
m
n
n
n
n
,
1
,
0
...
...
...
2
2
1
1
2
2
2
22
1
21
1
1
2
2
11 1
=
≥
⎪
⎪
⎩
⎪⎪
⎨
⎧
=
+
+
+
=
+
+
+
=
+
+
+
Κ
Κ
Κ
Κ
Κ
Κ
 
Шартымен f(х)=c
1
х
1 
+ c
2
х
2 
+ …+ c
n
х
n
→maх табу керек. 
ЖП жалпы есебін канондық формаға келтіру үшін теңсіздік 
түріндегі  барлық  шектеулерді  төменде  берілген  жолдармен 
теңестіру жеткілікті. 
i-ші шектеуді алайық: 
k
i
b
x
a
x
a
x
a
i
n
in
i
i
,
1
,
...
2
2
1
1
=
≤
+
+
+
 
Əрбір 
теңсіздік 
теңдікке 
айналатындай 
етіп 
)
,
1
(
,
0
k
i
x
i
n
=
≥
+
қосымша айнымалыларын енгіземіз: 
k
i
b
x
x
a
x
a
x
a
i
i
n
n
in
i
i
,
1
,
...
2
2
1
1
=
=
+
+
+
+
+
 
Содан  соң  ЖП  жалпы  есептерінде  кейбір  айнымалыларға 
айнымалылардың  теңсіздігі  шарты  қойылады.  Жалпы  есепті 
канондық  формаға  келтіру  үшін  бұл  айнымалыларды  есептен 
шығарып тастау керек немесе айнымалыларға өзгерту керек: 
n
где
j
V
U
V
U
x
j
j
j
j
j
,
1
,
0
,
0
,
=
≥
≥
−
=
 
Осылайша,  ЖП  есептерінің  канондық  формасына  қатысты 
есептер  мен  дəлелдемелердің  барлығын  жүргізе  отырып,  біз 
талқылаудың ортақтығын жоғалтпаймыз. 
f(х)=c
1
х
1 
+ c
2
х
2 
+ … c
n
х
n
  функциясының  минимумын  табу 
қажет  болған  жағдайда  f
1
(х)= - f(х)= -c
1
х
1 
- c
2
х
2 
-… -c
n
х
n
 
функциясының  максимумын  табуға  көшуге  болады,  себебі  min 
f(х) = -max(- f(х))  екендігі бəрімізге белгілі. 
ЖП есебінің канондық формасын мына түрде жазамыз: 
А
1
х
1 
+ А
2
х
2 
+ … А
n
х
n 
= В               (2) 
  x
j
  ≥0, j =
n
,
1
   
                           (3) болғандағы 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
13
f(х) = 
j
j
n
j
X
C
Σ
=1
 → max           (1) табамыз, мұндағы 
;
;
;
;
;
2
1
2
1
2
22
12
2
1
21
11
1
⎟⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎝
⎛
=
⎟⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎝
⎛
=
⎟⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎝
⎛
=
⎟⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎝
⎛
=
b
b
b
B
a
a
a
A
a
a
a
A
a
a
a
A
m
mn
n
n
n
m
m
Μ
Μ
Λ
Μ
Μ
   
 
1-анықтама. (2)-(3) шектеулерін  қанағаттандыратын  кез 
келген  Х = (х
1
,х
2
…,  х
n
)  жазықтық  нүктесі  жоспар  немесе  ЖП 
есебінің ұйғарынды шешімі деп аталады. 
 
2-анықтама. Х = (х
1
,х
2
, …, х
n
)  жоспары тірек жоспары деп 
аталады,  егер  оң  (нольдік  емес)  x
j
  коэффициенттерімен (2) 
жіктеуіне кіретін А
j
 (j = 
n
,
1
) векторлары желілік тəуелсіз жүйе 
құратын болса. 
 
3-анықтама.  Тірек  жоспары  құрамында  теңдей  m 
қосындылары  бар  болатын  болса 
төмендемеген
  деп  аталады. 
Керісінше жағдайда ол төмендеген деп аталады. 
 
4-анықтама. (1) мақсатты  функциясын  максималды 
(минималды)  мəніне  жеткізетін  жоспар  оңтайлы  немесе  ЖП 
есебінің шешімі деп аталады. 
ЖП есебінің негізгі қасиеттерін қарастыруға көшпес бұрын, 
дөңес  жиынтықтардың  бірқатар  қасиеттерін  еске  сала  кетейік, 
себебі олар тығыз түрде өзара байланысқан. 
 
5-анықтама.  Х
1
,Х
2,
…,  Х
n
ЄR
n 
–  n-өлшемдік  евклидтік 
кеңістіктің  туынды  нүктелер  болсын  делік.  Бұл  нүктелердің 
дөңес желілік комбинациясы деп  
X =
x
i
i
n
i
d
Σ
=1
 где   
1
,
,
1
,
0
1
=
=
≥
Σ
=
d
d
i
n
i
n
i
i
 
нүктесі аталады. 

Экономикалық-математикалық әдістер 
 
14
6-анықтама.  ХЄR
n 
–  n-өлшемдік  евклидтік  кеңістіктің 
жиынтығы дөңес деп  аталады, егер өзінің кез келген екі нүкте-
сімен бірге оның құрамында туынды дөңес желі комбинациясы, 
яғни Х
1
ЄХ, Х
2
Є Х, то  х = d
1
x
1
 + d
2
x
2
ЄХ, где d
1
 ≥ 0, d
2 
≥ 0, d
1
+d
2
= 
1 бар болатын болса. 
Геометриялық  тұрғыдан  бұл  дөңес  жиынтықтың  өзінің  кез 
келген  екі  нүктесімен  бірге  осы  нүктелерді  өзара  жалғайтын 
кесіндіге де ие екендігін білдіреді. 
 
7-анықтама.  Дөңес  жиынтықтың  нүктесі  шеткі  деп 
аталады, егер оны осы жиынтықтың қандай да бір екі нүктесінің 
дөңес желілік комбинациясы ретінде бере алмасақ. 
ЖП  есептерін  шешудің  негізгі  қасиеттері  бірқатар  теорема-
лармен анықталады. Бұларды біз дəлелдемелерсіз береміз. 
1-теорема. ЖП есебінің жоспарлар жиынтығы дөңес. 
2-теорема.  ЖП  есебінің  желілік  формасы  өзінің  максиму-
мына (минимумына) жоспарлардың дөңес жиынтығының шеткі 
нүктесінде  жетеді.  Егер  ол  өзінің  максималды  (минималды) 
мəніне бірден көп шеткі нүктеде жетсе, онда ол осы нүктелердің 
дөңес  желілік  комбинациясы  болып  табылатын  кез  келген 
нүктеде сондай мəнге жете алады. 
3-теорема. Х = (х
1
,х
2
,… х
n
) нүктесі шеткі болуы үшін оның 
х
j 
оң компоненттері 
x
B
A
j
j
n
j
=
Σ
=1
 жіктеуіндегі А
j
(j =
n
,
1
) желі-
лік  тəуелсіз  векторлар  жағдайында  коэффициенттер  болғаны 
қажет жəне жеткілікті. 
Егер тірек жоспарының анықтамасын еске түсіретін болсақ, 
онда: 
1)  əрбір  тірек  жоспары  ЖП  есебі  жоспарларының  дөңес 
жиынтығының шеткі нүктесіне сəйкес келетіндігі; 
2)  əрбір шеткі нүктемен (əрбір тірек жоспарымен) берілген 
А
1
,А
2
,…,А
n 
жүйесінің m желілік тəуелсіз векторлары байланысты. 
 
1.4. Желілік программалау есептерін шешудің сызба əдісі 
 
ЖП  есебінің  геометриялық  түсіндірмесін  берейік.  Оны  жазық-
тықта берген дұрыс: желілік форманың максимумын табу талап 
етіледі: 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
15
 а
11
х
1 
+ а
12
х
2    
≤
 
 b
1 
а
2
х
1 
+ а
22
х
2   
≤
 
 b
2                                   
               (2') 
……………………… 
а
m1
х
1 
+ a
m2
 х
2 
≤
 
 b
m 
х
1 
≥ 0, х
2 
≥ 0                                              (3') 
 
шектеулері жағдайында 
f(х)= c
1
х
1 
+ c
2
х
2   
→max                           (1') 
табу қажет. 
Теңсіздікті (3') Х
1
ОХ
2
  оң  квадрант  жазықтығында 
анықтайды.  Шектеулер  жүйесі  теңсіздіктердің  əрбірі (2') 
геометриялық  тұрғыдан  шендес  түзулерге  сəйкес  жартылай 
жазықтығын анықтайды 
а
i1
х
1 
+ a
i2
 х
2 
=
 
 b
i
    i=  
m
,
1
             
         (4) 
Осылайша, есептің желілік формасын анықтау облысы (1
′)–
(3
′) оң Х
1
ОХ
2
 квадрантында орналасқан жартылай жазықтықтар-
дың (2') жалпы бөлігі түрінде болады. Бұл осы жартылай жазық-
тықтарды қиып өтетін көп нүктелер – шешімнің көпбұрышы (n 
≥  3 болғанда – шешімнің көпқыры) деп аталатын дөңес жиынтық. 
ЖП  бастапқы  есебі  шешімнің  f(х)  мақсатты  функциясы  макси-
малды  мəнге  ие  болатын  көпбұрышының  осындай  нүктесін 
табуда  болып  отыр.  Егер  шешімнің  көпбұрышы  бос  болмаса 
жəне  ондағы  мақсатты  функция  жоғарыдан  шектелген  болса, 
онда  бұл  н‰кте  бар.  Мұндай  жағдайларда, 2 теоремаға  сәйкес, 
шешім көпбұрышының с‰йір ұшының (соңғы н‰ктенің) бірінде 
мақсатты  функция  максималды  мәнге  жетеді.  Оны  анықтау 
‰шін  т‰зу  құрамыз    c
1
х
1 
+ c
2
х
2  
= f(х
̅
),  мұндағы  f(х
̅
)=const  және 
оны
 шешімнің көпбұрышы бойымен желілік форманың ұлғаюы 
бағытында  өз-өзіне  параллель  түрде  шешімнің  шешімнің  көп-
бұрышымен  қиысатын  соңғы  ортақ  нүктеден  өткенге  дейін 
қозғаймыз.  Осы  нүкте  координаттары  есептің  оңтайлы  жоспарын 
анықтайды. 
(1
′)–(3′)  есептерін  шешу  барысында  əр  түрлі  жағдайлар 
кездесуі мүмкін екенін де атап өткен жөн. 

Экономикалық-математикалық әдістер 
 
16
1.  Есептің  шешімін  анықтау  облысы  көпбұрыш  түрінде 
болсын.  Мұндағы  мақсатты  функция  бір  ғана  А  нүктесінде 
максималды мəнге ие болатындығы 2-суретте көрсетілген. 
3-суретте  мақсатты  функцияның  максималды  мəнге  АВ  қиын-
дысының  кез  келген  нүктесінде  ие  болатындығы  жағдайы 
көрсетілген.  с(c
1
,c
2
)  векторы  мақсатты  функцияның  ұлғаю 
бағытын көрсетеді. 
 
 
 
 
 
 
 
 
 
 
2-сурет
   
 
 
 
3-сурет
 
 
ІІ.  Есептің  шешімін  анықтау  облысы  шексіз. 4-суретте 
желілік  форманың  жоғарыдан  шектелмегендігі  жағдайы 
көрсетілген. 
 
 
 
 
 
4-сурет 
 
ІІІ.  Есептің    шешімін  анықтау  облысы – бос  жиынтық.  Бұл 
жағдайда  ЖП  есебін  шешу  мүмкін  емес,  себебі  есепті  шектеу 
жүйесі үйлесімсіз. 
Үш  немесе  одан  да  көп  айнымалылары  бар  есеп  берілген 
жағдайда (2
′)–(3′)  шарттары  кеңістікте  дөңес  көпқырлылық 
(дөңес көпқырлы жиынтық) құрайды. 
Желілік  форма  геометрикалық  тұрғыдан  параллель  жазық-
тықтар  (гипержазықтықтар)  тобы  ретінде  түсіндіріледі.  Есепті 
шешу үшін жазықтықты (гипержазықтықты) желілік форманың 
ұлғаюы  бағытында  əзірше  оның  құрамында  көпқырлылықтың 
 
f(х) 
f(х)
 f(х) 
f(х) 
0 
х
2
х
А
 
(
0 
х
2
х
f(х) 
f(х) 
 
f(х) 
А
 
В
 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
17
(көпқырлы  жиынтықтың)  нүктелері  бар  болып  тұрғанға  дейін 
қозғалту  керек.  Жазықтықтың  (гипержазықтықтың)  ең  шекті 
орналасу  қалпы  есептің  шешімін  анықтайды.  ЖП  есептерін 
шешу  қасиеттері  негізінде  жазықтықтың  (гипержазықтықтың) 
шектік  қалпына  көпқырлылықтың  (көп  қырлы  жиынтықтың) 
сүйір  ұшында  немесе  оның  қандай  да  бір  қырының  барлық 
нүктелерінде қол жеткізіледі деп айтуға болады. 
 
 
 
 
 
 
 
 
 
 
5-сурет 
 
Желілік программалау есептерін интерпретациялау негізінде 
оны  шешудің  графикалық  деп  аталатын  тəсілі  құрылады. 
Есептерді екі өлшемді кеңістікте графикалық тəсілмен шешудің 
алгоритмі төмендегі сатылардан тұрады: 
1.  Шектік  түзулер  құрады,  олардың  теңдеулері (2
′)–(3′) 
шектеулеріндегі  теңсіздің  белгілерін  дəл  теңдіктер  белгілеріне 
ауыстыру нəтижесінде алынады. 
2.  Шешімнің көпбұрышын табады. 
3.  с = (с
1 
, с
2
) векторын құрады. 
4.  f(х)= c
1
х
1 
+ c
2
х
2
, түзуін құрып, оның мəнін қандай да бір 
санға тең деп қабылдайды. 
5.  f(х)= c
1
х
1 
+ c
2
х
2
,  түзуін  С  векторы  бағытында  шешімнің 
көпбұрышы  бойымен  жылжытады,  осының  нəтижесінде 
мақсатты  функция  максималды  мəнге  ие  болатын  нүктені 
(нүктелерді)  табады,  немесе  желілік  форманың  шексіздігін 
жоспарлар жиынтығына орнатады. 
6.  Функция максимумы нүктесінің координаттарын анықтайды 
жəне осы нүктедегі желілік форманың мəнін табады. 
Мысал. 
х
1 
х
2 
0
 

Экономикалық-математикалық әдістер 
 
18
2х
1 
+ х
2    
≥ 2
 
-х
1 
+х
2  
≤
 
 2
                     
         
2х
1  
- 3х
2 
≤
 
 6
 
х
1 
+х
2  
≤
 
 8 
х
1 
≥ 0, х
2 
≥ 0         
шарты жағдайында 
f(х)= 3х
1 
+ 2х
2   
→max 
графикалық тəсілмен шешу қажет. 
Бірінші 2х
1 
+х
2  
≥
 
2 теңсіздігін аламыз. 
Шектік  түзі  сызбасын  құрып,  ондағы  теңсіздік  белгісін 
теңдік белгісімен алмастырамыз, яғни 2х
1 
+х
2
 = 2         (*) 
Берілген  түзуді  екі  нүкте  бойынша  құрамыз:  мысалы,  х
1
= 0   
қойып, х
2 
аламыз. 
2 · 0 + х
2 
= 2,   х
2 
 = 2, ал х
2  
= 0, қойып, х
1 
 анықтаймыз.  
2 · х
2 
+ 0
 
= 2,   х
1 
 = 1, 
   х
1        
х
2
 
 
   0       2 
   1       0        
Осылайша, түзу өтетін (*) екі нүктені таптық, дəлірек айтсақ 
А(0,2) жəне В(1,0). Осы нүктелерді х
1
 0 х
2
 жазықтығында табамыз. 
Түзуді осы нүктелер арқылы жүргіземіз. Теңсіздіктің шешімі 
2х
1
+ х
2 
≥ 2 
шекті  түзудің  бір  жағында  орналасқан  жарты  жазықтық 
нүктелері  болады.  Ізделіп  отырған  жарты  жазықтықты  анықтау 
үшін  жарты  жазықтықтың  біріне  жататын  нүктені  алып,  оның 
коррдинаттарының  берілген  теңсіздікті  қанағаттандыра  алатынын 
немесе  алмайтынын  тексеру  керек.  Тексеру  үшін  0(0,0)  нүкте-
лерін алған ыңғайлы. Берілген теңсіздікке осы нүктенің коорди-
наттарын  (х
1
 =0, х
2
  =0)  қоя  отырып,  бұл  нүкте  оның  шешімі 
болмайтынына көз жеткіземіз, себебі 2 · 0 +0 
⋡2. 
Демек,  бұл  теңсіздіктің  шешімі  0(0,0)  нүктелері  жоқ 
жазықтықтың  нүктелері  болады. 6-суретте  бірінші  теңсіздіктің 
шешімі  болып  табылатын  жарты  жазықтық  стрелкамен 
көрсетілген.  Стрелка  маңайындағы  жақшаларда  шектік  түзудің 
номері берілген. 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
19
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
6-сурет 
 
Осы  жолмен  екінші  теңсіздіктің  графикалық  шешімін 
табамыз 
-х
1
 +  х
2 
≤ 2 
Əуелі шектік түзу құрамыз 
   -х
1
 +  х
2 
= 2 
 х
1        
х
2
 
 
0       2 
-2     0        
Ол  А(0,2)  жəне  С(-2,0)  нүктелері  арқылы  өтеді.  Түзуді  осы 
нүктелер арқылы жүргіземіз. 0(0,0) нүктесінің координаттарын  
-х
1
 +  х
2 
≤  2  теңсіздігіне  қойып,  0<2,  яғни  теңсіздікті 
қанағаттандыратын  0(0,0)  нүктесінің  координаттарын  аламыз, 
демек,  екінші  теңсіздіктің  шешімі  жарты  жазықтықтың  шектік 
түзудің  0(0,0)  нүктесі  орналасқан  бөлігіндегі  барлық  нүктелері 
болып табылады. 
Одан əрі қарай үшінші теңсіздіктің шешімін анықтаймыз 
  D
(2)
-
-1
Q
В
  Е
С
(4)
C(3,-2)
    
(1)
  
Х
2
Z
M
(-3)
     3
A
   
2
   
1
2
3
1
   
-1
    -2
     0
-

Экономикалық-математикалық әдістер 
 
20
2х
1
 - 3 х
2 
≤ 6 
2х
1
 - 3х
2 
= 6  шектік түзуді екі нүкте бойынша құрамыз: 
х
1
 = 0 ,      0 -3х
2 
= 6     х
2
 = -2 
х
2
 = 0 ,      2х
1 
-0 = 6     х
1
 =  3  
 
х
1        
х
2
                       Д(0,-2) 
                                  Е (3,0)    
0      - 2 
3       0        
0(0,0)  нүктесі  де  осы  теңсіздікті  қанағаттандырады,  енді 6-
суретте  0(0,0)  нүктесі  бар  жəне,  демек,  теңсіздіктің  шешімі 
болып табылатын жарты жазықтықты стрелкамен көрсетеміз. 
Одан  соң  осы  жолмен  төртінші  теңсіздіктің  графикалық 
шешімін табамыз 
х
1
 +  х
2 
≤ 8 
Шектік түзуді 
х
1
 + х
2 
= 8 
келесі екі нүкте бойынша құрайық: х
1
 = 4 болса, онда 4 + х
2 
= 8, х
2
 = 4, ал  х
1 
= 3 десек, х
2  
анықтаймыз: 
3 + х
2 
= 8,  х
2 
= 5 
М(4,4) жəне N (3,5) нүктелерін тауып, осы нүктелер арқылы 
түзу  жүргіземіз.  0(0,0)  нүктесінің  координаттары  берілген 
теңсіздікті қанағаттандырады, себебі 0 + 0 <8. 
Сондықтан  да  берілген  теңсіздіктің  шешімі  жарты 
жазықтықтың  шектік  түзудің  0(0,0)  нүктесі  орналасқан 
бөлігіндегі нүктелері болып табылады. 
х
1
 ≥0 и х
2
 ≤ 0 шарттары көрсетіп отырғандай, шешім бірінші 
квадрантта. 
Алынған  жарты  жазықтықтардың  қиысуы  берілген  есептің 
шешімінің  көпбұрышын  анықтайды. 6-суретте  көрсетілгендей, 
шешімнің  көпбұрышы  ABEQZ  бесбұрышы  болып  табылады. 
Осы  бесбұрыштағы  кез  келген  нүктенің  координаттары  есептің  
шектеуін  қанағаттандырады,  енді  осы  нүктелер  жиынтығының 
ішінен  
f(х)= 3х
1 
- 2х
2
 
желілік  формасы  өзінің  максималды  мəніне  ие  болатын 
нүктені  табу  қажет.  Бұл  нүктені  табу  үшін  f(х)  функциясының 
ұлғаю  бағытын  көрсететін  С= (c
1 
, c
2
) = (3, - 2) векторын 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
21
құрамыз.  f(х)= 3х
1 
+2х
2 
түзуін  құрып,  f(х)  еркін  мəн  береміз, 
мысалы, f(х)= 6, яғни 3х
1 
- 2х
2 
= 6 түзуін құрамыз. 
Оны  тағы  да  өзінің  екі  нүктесі  бойынша  құрамыз.  х
1 
= 0 
болсын, сонда х
2 
анықталады: 
3 · 0 – 2х
2 
= 6,  х
2
 = -3 
Енді х
2 
= 0 делік, онда 3 х
1 
– 2 · 0 = 6   қайдан х
1 
= 2 
Осылайша, (0, -3) жəне (2,0) нүктелері  арқылы  өтетін  түзу 
құрамыз. 6-суретте  бұл  түзу  үзік  сызықпен  белгіленген.  Осы 
түзуді  өзіне  параллель  түрде  С  векторы  бағытымен  жылжытар 
болсақ,  оның  шешімнің  көпбұрышымен  ортақ  соңғы  нүктесі  Q 
нүктесі  болатындығын  көреміз.  Бұл  нүктенің  координаттары 
оңтайлы жоспар немесе есептің шешімі болып табылады. 
Q  нүктесі 3 жəне 4 түзулерінің  қиысу  нүктесі  болып 
табылады, демек, оның координаттары осы түзулердің теңдеуін 
қанағаттандырады 
           2х
1 
- 3х
2 
= 6 
           х
1  
+  х
2 
= 8 
 
Демек, бұл теңдеулер жүйесін Q нүктесінің координаттарын 
анықтау үшін шешу қажет. Жүйені шеше отырып, табамыз: 
х
1 
= 6, х
2 
= 2, ал   max f(х)= f(Q)= 3 ·6 – 2 ·2 = 18 – 4 = 14 
Сонымен, Х
опт
 = (6,2) жəне  f(х
опт
 )= 14 шешімі алынды. 
 

жүктеу/скачать 1,22 Mb.

Достарыңызбен бөлісу: