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



жүктеу 5.01 Kb.

бет6/13
Дата22.04.2017
өлшемі5.01 Kb.
1   2   3   4   5   6   7   8   9   ...   13

1.8.2. Симметриялық емес екі жақты тапсырмалар, 
екіжақтылықтың негізгі теоремасы 
 
Тікелей тапсырма былайша беріледі:  
       
n
l
l
j
x
m
k
i
b
x
a
k
i
b
x
a
j
i
j
ij
n
j
i
j
ij
n
j

=

+
=
=
Σ
=

Σ
=
=
,
,
1
0
,
1
,
,
1
,
1
1
                    
 болған жағдайда 
   f(x)
 =
x
C
j
j
n
j
Σ
=1
 функциясын арттыру қажет. 
Екі жақты тапсырма мынадай түрге ие болады: 
 
 
болған жағдайда   
 
функциясының мəнін азайту керек. 
k
i
y
n
l
j
c
y
a
l
j
c
y
a
i
j
i
ij
m
i
j
i
ij
m
i
,
1
,
0
,
1
,
,
1
,
1
1
=

+
=
=
Σ
=

Σ
=
=
y
b
y
g
i
i
m
i
Σ
=
=1
)
(

Әлжанова Н.Ш., Сәбитова Х.К. 
 
57
Егер осы тапсырманың  екеуін салыстырсақ, онда екі жақты 
симметриялық  емес  жұпты  құрудың  жалпы  ережесін  қалып-
тастыруға болады. 
1.  Тікелей  тапсырманың  əрбір  i-інші  шектеу  мəніне  екі 
жақты  тапсырманың 
yi
 
 
айнымалысы  сəйкес  келеді 
)
,
1
(
m
i
=
 
жəне  керісінше,  екі  жақты  тапсырманың  əрбір 
j
-інші  шектеу 
мəніне  тікелей  тапсырманың 
x
j
  айнымалысы  сəйкес  келеді 
)
,
1
(
n
j
=

2. Тікелей тапсырманың шектеулер матрицасы: 
 
⎟⎟





⎜⎜





=
a
...
a
a
.......
..........
a
...
a
a
a
...
a
a
mn
m2
m1
2n
22
21
1n
12
11
A
 
 
жəне екі жақты тапсырманың шектеулер матрицасы: 
 
⎟⎟





⎜⎜





=
a
...
a
a
......
..........
a
...
a
a
a
...
a
a
mn
2n
1n
m2
22
12
1
21
11
1
m
А
 
 
өзара тасымалданған. 
3.  Тапсырмалардың  біреуіндегі  шектеулердің  бос  мүшелері 
келесі  тапсырманың  мақсатты  функциясының  айнымалылары 
сəйкес келгенде коэффициенттер болып табылады. Осыған орай 
арттыру керісінше азайту мəніне өзгереді. 
4.  Тікелей  тапсырмадағы  шектеулерді,  яғни  теңсіздіктерді 
арттыру барысында - «
≤» белгісімен жəне азайту барысында ≥» 
белгісімен жазған жөн.  

Экономикалық-математикалық әдістер 
 
58
5.  Тікелей  тапсырманың  əрбір  i-інші  шектеуіне,  яғни 
теңсіздігіне - екі  жақты  тапсырмадағы  сəйкес  айнымалының 
дұрыс мəні (
yi
≥0), ал теңдікке 
yi
айнымалысы, яғни бос мүше 
сəйкес келеді. Керісінше, айнымалының дұрыс мəніне (
x
j
≥0) - 
екі жақты тапсырмада 
j
-інші шектеу-теңсіздік, ал бос айнымалыға 
теңдік сəйкес келеді. 
Мысал. Мына берілген мəндер бойынша екі жақты тапсырма 
құру: 
 
0
,
0
,
0
1
4
2
2
8
2
2
10
3
2
min
3
2
)
(
4
3
1
5
4
3
2
1
5
4
3
2
1
5
4
3
2
1
5
4
3
2
1
3










+

+


+
+

+
=


+


+

+

=
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
I
x
f
 
 
 Шешуі.  Екі  жақты  тапсырманы  құруға  көшпес  бұрын 
алғашқы  тапсырма  көшірмесін  реттеп  алу  қажет.  Мақсатты 
функция  мəні  азаятындықтан,  барлық  шектеу-теңсіздіктерді 
«
≥» түріне келтіріп алу шарт. Бұл үшін үшінші теңсіздікті 1-ге 
көбейтеміз, осыдан кейін шектеулер жүйесі былайша жазылады: 
 








+

+


+
+

+
=


+

4
2
3
2
8
2
2
10
3
2
5
4
3
2
1
5
4
3
2
1
5
4
3
2
1
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
y
y
y
 
 
Екі  жақты  тапсырмада 3 айнымалы: 
,
,
,
3
2
1
y
y
y
  яғни 
алғашқысында  шектеулер  саны  қанша  болса,  сонша  айнымалы 
болады.  Екі  жақты  тапсырманың  мақсатты  функциясын  құрайық, 
соған  қоса  екі  жақты  тапсырманың  мақсатты  функциясының 
айнымалылары  барысындағы  коэффициенттер  ретінде  алғашқы 
тапсырмадағы шектеулердің оң жақ бөлігі танылады: 
 
max
4
8
10
)
(
3
2
1


+
=
y
y
y
y
g


Әлжанова Н.Ш., Сәбитова Х.К. 
 
59
тікелей  тапсырмадағы  мақсатты  функция  мəні  азаятындықтан, 
екі  жақты  тапсырмадағы  мақсатты  функция  мəні  артады.  Екі 
жақты  тапсырма  шектеулерін  құру  барысында  оның  А

матрицасының  тікелей  тапсырма  шектеулерінің  А  матрицасына 
қатысты  алғанда  тасымалданатындығын,  яғни  А  матрицасының 
бағандары А
1
 матрицасының жолдары болатындығын ескереміз. 
Сонымен, екі жақты тапсырманың бірінші шектеуін жазайық: 
 
2
2
2
3
2
1


+
y
y
y
 
 
Бірінші  шектеу  «≤»  белгісімен  жазылады,  өйткені  х

-ге 
дұрыс  мəн  қойылған,  ал  шектеудің  оң  жақ  бөлігі  алғашқы 
тапсырманың  сызықтық  түрінің  айнымалы  х

болғандағы 
коэффициентіне  тең  болады,  яғни  с
1
=2
.  Екі  жақты 
тапсырмадағы екінші шектеу теңдік түрінде жазылады, өйткені  
х
2 
 айнымалысына дұрыс мəн қойылмаған: 
 
1
2
3
2
1

=
+
+

y
y
y
 
 
х
3
≥3
  х
4
≥0
,
  х
5
  болғандықтан,  сəйкесінше  екі  жақты  тапсыр-
маның  үшінші  жəне  төртінші  шектеулері  теңсіздік  түрінде 
жазылады, ал бесінші шектеу теңдік түрінде жазылады, өйткені 
х

айнымалысына  дұрыс  мəн  қойылмаған,  бұл  шектеулердің  оң 
жақ бөлігінде алғашқы тапсырманың сызықтық түріндегі сəйкес 
айнымалылары барысындағы коэффициенттер тұрады: 
 
1
2
3
2
3
1
3
3
2
1
3
2
1
3
2
1
=

+



+





y
y
y
y
y
y
y
y
y
 
 
Алғашқы  тапсырмадағы  бірінші  шектеу  теңдік  түрінде 
болып  келеді,  сондықтан  екі  жақты  тапсырманың  у
1
 
бірінші 
айнымалысы  бос  мүше  болады,  ал  у
2
 
жəне  у
3
 
айнымалыларына 
дұрыс  мəн  қойылған,  өйткені  алғашқы  тапсырмадағы  екінші 
жəне үшінші шектеулер теңсіздіктер болып табылады. Осылайша, 
екі жақты тапсырма мынадай түрге ие болады: 

Экономикалық-математикалық әдістер 
 
60
0
,
0
1
2
3
2
3
1
3
1
2
2
2
2
max
4
8
10
)
(
3
2
3
2
1
3
2
3
2
1
3
2
1
3
2
1
3
2
1











=

+



+






=
+
+



+


+
=
y
y
y
y
y
y
y
y
y
y
y
y
y
y
y
y
y
y
y
y
y
g
 
 
Тікелей  жəне  екі  жақты  тапсырмаларды  шешу  барысында 
олардың  арасында  өзара  тəуелділік  те  бар.  Осы  тəуелділікті 
сипаттайтын теоремалардың біреуін келтірейік. 
7-теорема.  Егер  екі  жақты  тапсырмалар  жұбының  біреуінің 
оңтайлы  жоспары  болса,  онда  екіншісінің  де  осындай  жоспары 
болады, сонымен қатар тапсырмалардың сызықтық түрлеріндегі 
экстремалды мəндері сəйкес болып шығады, яғни 
 
max f(х)= min g(y) 
 
Егер екі жақты тапсырманың біреуінің шешімі болмаса, онда 
екіншісінің де шешімі болуы мүмкін емес.  
 
1.8.3. Екі жақты  симплексті əдіс 
 
Сызықтық бағдарламалаудың канондық  
 
f(х)=c
1
х

+ c
2
х

+... + c
n
х
n   
 

  maх                    
(36) 
 
түріндегі тапсырмасы берілген делік. Мұндағы шектеулер: 
 
   А
1
х

+ А
2
х

+... + А
n
х

 = В,                             (37) 
 
Бұл жерде мына мəн белгілі: 
 
)
38
(
,
1
0
,
,
1
;
2
1
2
1
n
j
n
j
j
x
b
b
b
B
a
a
a
A
j
m
mj
j
j
=

⎟⎟





⎜⎜





=
=
⎟⎟





⎜⎜





=
Μ
Μ
 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
61
Алғашқы m векторлары біркелкі болсын, яғни  
 
⎟⎟





⎜⎜





=
⎟⎟





⎜⎜





=
⎟⎟





⎜⎜





=














=














=
⎟⎟





⎜⎜





=
+
+
+
+
b
b
b
B
a
a
a
A
a
a
a
A
A
A
A
m
mn
n
n
n
mm
m
m
m
m
Μ
Μ
Κ
Μ
Μ
Λ
Μ
Μ
2
1
2
1
1
1
2
1
1
1
2
1
;
;
;
;
1
0
0
0
;
;
0
0
1
0
;
0
0
1
 
 
жəне  b
i
)
,
1
(
m
i
=
  сандарының  ішінде  теріс  мəнділері  бар  делік. 
Егер А
1
, А
2
, ..., А

векторлар жүйесін алғашқы базис десек, онда 
оған сызықтық теңдеулер жүйесінің (37) шешімі болып табылатын  
x=(b
1
,b

 ...,b
m
,0,..,0 
  вектор  сəйкес  келеді,  алайда  ол (36) – (38) 
тапсырмасының  жоспары  болып  табылмайды,  өйткені  оның  b
i
 
компоненттерінің ішінде теріс мəндері бар. 
Анықтама. 
Сызықтық теңдеулер жүйесінің (37) A
1
,...,A

деп 
анықталатын x=(b
1
,b

 ...,b
m
,0,..,0)
 шешімі, егер 
Δ


 0

n
j
,
1
=
 
болса, (36)-(38) тапсырманың бүркеншік жоспары деп аталады. 
Əдеттегідей, алғашқы симплексті кесте құрамыз жəне егер 
кестеде бүркеншік жоспар болса, онда есепті екі жақты симплексті 
əдіспен шешу келесі алгоритм бойынша жүзеге асырылады. 
1-қадам. Бүркеншік жоспардың теріс элементтерінің ішінен 
ең кішісін (абсолюттік шама бойынша ең үлкен мəн) іздейміз. 
Мына мəн белгілі болсын: 
                        
x
i
i
min
=
i
min
 b
i
 =b
r
 < 0 
Бұл A
r
 векторының базистен шығарылатындығын, ал кестенің 
r
-інші тармағының бағыттауыш болып табылатындығын білдіреді. 
2-қадам. 
θ шамасын былайша анықтаймыз:  

Экономикалық-математикалық әдістер 
 
62
           
0
)
(
)
(
0
,
min
>
Ζ
Δ

=
Ζ
Δ

<
Ζ
=
rk
k
rj
j
rj
j
θ
 
 
Бұл A
k
 векторының базиске A
r
 векторының орнына енгізіле-
тіндігін,  ал  k  бағанының  бағыттауыш  болып  табылатындығын 
білдіреді. 
3-қадам. Кестені Гаусс формулалары бойынша қайта құрамыз. 
1-3 қадамдар оңтайлы жоспар алынғанша қайталана береді. 
Бұл  алгоритмді  келесі  тапсырманы  шешу  барысында  қарас-
тырамыз. 
Мысал. max f(х)=-2х
1

2
-3х

  мəнін  табу  керек.  Мұнда 
мыналар белгілі: 
 
3
,
1
,
0
1
6
1
4
12
3
2
2
1
3
2
1
=








+


+

+
+
j
I
I
x
x
x
x
x
x
x
x
j
 
 
Шешуі.  «≥» түріндегі барлық теңсіздіктерді оның екі бөлігін 
де (-1) мəніне  көбейте  отырып, «≤»  түріндегі  теңсіздіктерге 
əкеліп  қоямыз,  яғни  шектеулер  жүйесінің  екінші  жəне  үшінші 
теңсіздіктерінің екі бөлігін де (-1) мəніне көбейтеміз. Осы арқылы 
мынадай жүйе алынады: 
 














+
+
6
4
12
3
2
2
1
3
2
1
x
x
x
x
x
x
x
 
Енді  қосымша  айнымалыларды  енгізу  арқылы  тапсырманы 
канон түріне келтіреміз: 
 






=
+



=
+


=
+
+
+
6
4
12
6
3
2
5
2
1
4
3
2
1
x
x
x
x
x
x
x
x
x
x
 
 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
63
Алғашқы симплексті кесте құрайық 17-кесте: 
 
  
17-кесте 
 
С

В 
А
1
 
А
2
 
А
3
 
А
4
 
А
5
 
А
6
 
А
4
  0 12 1 1 1 1 0 0 
А
5
  0  -4 -1 -1  0  0
 
1 0 
А
6
  0 -6 0 -1 -1 0  0  1 
Δ    0 2 1 3 0 0 0 
 
Көріп отырғанымыздай, алғашқы симплексті кестеде мынадай 
бүркеншік жоспар алынады: 
 
Х = (0, 0, 0, 12, -4, -6) 
 
1-қадам.  В  бағанынан  ең  кіші  элементті  табамыз: 
6
}
6
,
4
min{
min

=


=
x
i
i
 
Бұл  элемент  А
6  
векторына  сəйкес  келеді,  ізінше  бұл  вектор 
базистен  шығарылады,  ал  оған  сəйкес  келетін  тармақ 
бағыттауыш болып табылады. Оны кестеде белгілеп көрсетеміз. 
2-қадам. Θ шамасын анықтайық. 
1
)
3
,
1
min(
)
1
(
3
;
)
1
(
1
min
=
=
⎟⎟


⎜⎜





=
θ
 
Бұл  жерде  тек  бағыттауыш  тармақтың  теріс  элементтеріне 
деген қатынастар ғана қарастырылатындығын ескертіп өтейік. 
Көріп  отырғанымыздай,  ең  кіші  қатынас  А
2
  векторына 
сəйкес келеді, яғни А
2
 векторы базиске енгізіледі, ал оған сəйкес 
келетін  баған  бағыттауыш  болып  табылады,  оны  кестеде 
белгілеп көрсетеміз. 
3-қадам.  Кестені  Жордан-Гаусс  формулалары  бойынша  қайта 
құрамыз. Нəтижесінде 18-кесте мəліметтерін аламыз. 
 
18-кесте 
 
С

В 
А
1
 
А
2
 
А
3
 
А
4
 
А
5
 
А
6
 
А
4
  0 6 1 0 0 1 0 1 
А
5
  0 2 -1 0 1 0 1 -1 
А
2
  -1 6 0 1 1 0 0 -1 
Δ 
 -6 2 0 2 0 0 1 
 
Оңтайлы жоспарға қол жеткіземіз: х = (0, 6, 0)    max f(x) = -6. 

Экономикалық-математикалық әдістер 
 
64
2. ЖЕЛІЛІК ПРОГРАММАЛАУДЫҢ 
ТРАНСПОРТТЫҚ ТАПСЫРМАСЫ 
 
Желілік программалаудың (ЖП) көптеген тапсырмаларының 
ішінен арнайы тапсырмалардың кейбір топтары бөлініп көрсетілді. 
Оларды жалпы тəсілдермен шешу есептік сипаттағы бірқатар 
қиыншылықтармен бірге жүреді. Осыған байланысты арнайы, 
едəуір қарапайым шешу тəсілдері əзірленді. Тапсырмалардың осын-
дай топтарының бірі транспорттық тапсырмалар болып табылады. 
 
 
2.1. Тапсырманың берілуі жəне математикалық 
 моделі 
 
Тапсырманың  берілуі.  А1,  А2, ... , Аm-нің m жіберілу 
пункттерінде біртекті жүктің сəйкес а1, а2, ... , аm бірлігі бар, ол 
В1,  В2, ..., Вn-нің    n  тұтыну  пункттеріне  жеткізілуі  керек.  Ал 
оларға сұраныс сəйкесінше в1, в2, ..., вn бірлігін құрайды. Мұнда 
А  пунктінен  В  пунктіне  (
n
j
m
i
,
1
,
,
1
=
=
)  жүк  бірлігін 
тасымалдауға жұмсалатын транспорттық шығындар С берілген. 
 Барлық  жүк  жіберілу  пунктінен  толығымен  шығарылатын, 
барлық  тұтыну  пункттеріндегі  сұраныс  қамтамасыз  етілетін 
жəне  транспорттық  шығындар  сомасы  минималды  болатын 
тасымалдау жоспарын анықтау керек. 
Тапсырманың  бастапқы  мəліметтерін  бөлуші  деп  аталатын 
келесі кестеге орналастырған ыңғайлы 19-кесте. 
19-кесте 
 
      b

a

b

 
b

 
 
b

 
 
b

 
     a
1
 
 C
11 
X
11
 
    C
12 
X
12
 
 
    C
1j
 
X
1j
 
 
C
1n
 
X
ln
 
    a
2
 
С
21
 
X
21
 
    
C
22
 
X
22
 
 
 
    C
2j
 
X
2j
 
 
 
 С
2n
 
X
2n
 
 
 
 
 
 
 
 
 
     a
i
 
  C
i1
 
X
i1
 
    
C
i2
 
X
i2
 
 
 
     C
ij
 
X
ij
 
 
 
C
in
 
X
in
 
 
 
 
 
 
 
 
 
     a
m
 
 C
m1
 
X
m1
 
   
C
m2
 
X
m2
 
 
 
    C
mj
 
X
mj
 
 
 
 C
mn
 
X
mn
 
 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
65
Тапсырманың  математикалық  моделі.  Тапсырманың  мате-
матикалық моделін құру үшін A
i  
)
,
1
(
m
i
=
 пунктінен B
j  
)
,
1
(
m
j
=
 
пунктіне тасымалданатын жүк бірлігінің көлемін білдіретін X
ij
 ≥ 0
   
(
n
j
m
i
,
1
,
,
1
=
=
) айнымалыларын енгіземіз. Бұл ауыспалылар 
келесі шарттарды қанағаттандыруы керек: 
 
а) барлық өнім жіберілу пунктінен шығарылуы керек: 





⎪⎪




=
+
+
+
+
+
=
+
+
+
+
+
=
+
+
+
+
+
=
+
+
+
+
+
m
mn
mj
m
m
i
in
ij
i
i
n
j
n
j
a
x
x
x
x
a
x
x
x
x
a
x
x
x
x
a
x
x
x
x
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
2
1
2
1
2
2
2
22
21
1
1
1
12
11
)
,
1
(
1
m
i
i
ij
n
j
a
X
=
=
Σ
=

 
 
b)  Барлық  тұтыну  пунктеріндегі  сұраныс  толығымен 
қанағаттандырылуы керек: 





⎪⎪




=
+
+
+
+
+
=
+
+
+
+
+
=
+
+
+
+
+
=
+
+
+
+
+
n
mn
in
n
n
j
mj
ij
j
j
m
i
m
i
b
x
x
x
x
b
x
x
x
x
b
x
x
x
x
b
x
x
x
x
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
2
1
2
1
2
2
2
22
12
1
1
1
21
11
)
,
1
(
1
n
j
j
ij
m
i
b
X
=
=
Σ
=

 
 
c)  Тасымалдау тек бір бағытта, яғни 
)
,
1
,
,
1
(
,
0
)
,
1
(
)
,
1
(
n
j
m
i
ij
n
j
j
в
m
i
i
X
B
A
=
=

=
=
 пунктінен пунктіне 
жүреді. 
 
d) Транспорттық шығындар сомасы минималды болуы қажет: 
 

Экономикалық-математикалық әдістер 
 
66
min
1
1
)
(
2
2
1
1
2
2
2
2
2
2
22
22
21
21
1
1
1
1
12
12
12
11

+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
=
mn
mn
mj
mj
m
m
m
m
i
i
n
n
j
j
n
n
j
j
X
C
X
C
X
C
X
C
in
X
in
C
ij
X
ij
C
X
C
i
X
i
C
X
C
X
C
X
C
X
C
X
C
X
C
X
C
X
C
x
L
Κ
Κ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Κ
Κ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Κ
Κ
Κ
Κ
 
 
X
C
ij
ij
n
j
m
i
X
L


=
=
=

1
1
)
(
min
 
 
мұндағы Х =




















mn
mj
m
m
in
ij
i
i
n
j
n
j
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Κ
Κ
Λ
Λ
Λ
Λ
Λ
Κ
Κ
Λ
Λ
Λ
Λ
Λ
Κ
Κ
Κ
Κ
2
1
2
1
2
2
22
21
1
1
12
11
 - тасымалдау жоспары  
 
Осылайша,  тапсырманың  математикалық  моделі  мынадай 
түрге ие болады: 
min
)
(
1
1

=


=
=
X ij
C ij
x
L
n
j
m
i
                    (1) 
       
m
i
a
i
ij
n
j
X
,
1
,
1
=
=

=
                                      (2) 
n
j
b
j
ij
m
i
X
,
1
,
1
=
=

=
                                   (3) 
)
,
1
,
,
1
,
0
n
j
m
i
ij
X
=
=

                          (4) 

1   2   3   4   5   6   7   8   9   ...   13


©emirb.org 2017
әкімшілігінің қараңыз

войти | регистрация
    Басты бет


загрузить материал