Стохастикалық бағдарламалау модельдері сызықтық және сызықтық емес болып кездеседі. Көбінесе сызықтық бағдарламалау есептерінің модельдеріне сәйкестендіріліп құрылатын сызықтық модельдер кездеседі.

Сызықтық модельдерде мақсатты функциядағы белгісіздердің коэффициенттері , шектеулердегі матрица коэффициенттері А және шектеулердің бос мүшелері кездейсоқ шамалар болуы мүмкін. Мұндай жағдайда кездейсоқ шамалардың үлестірілуі беріледі (тәуекел жағдайы) немесе белгісіз болады (анықталмаған).

Есептерді стохастикалық жолмен шығару оптималды жоспарды бір мәнді анықтамайды, ал көп варианттың кез келгені ықтималдылығына байланысты оптималды болуы мүмкін.

Загрузка...

Математикалық бағдарламалау есептерінің кез келгенінде айнымалыларға қойылған шектеулерге сәйкес мақсатты функцияның экстремумын табу қажет. Осыған дейін мақсатты функция мен шектеулері сызықтық болып келген есептер қарастырылды. Ал нақты есептерде сызықтық емес тәуелділіктер кӛптеп кездесетіндіктен сызықтық емес бағдарламалау теориясының жасалу қажеттігі туды. Қазіргі кезде сызықтық емес бағдарламалау есептері жылдам дамып келеді.

Математикалық бағдарламалау есептерінің мақсатты функциясы мен шектеулері сызықтық емес болса, онда ондай есептер сызықтық емес бағдарламалау есептері деп аталады.

Қарастырылып жатқан ағымдағы тасымалдау жоспарының тиімділігі

аг+/3;у<0(А)

-шартымен анықталады.Ол кестенің барлық ұяшықтары үшін орындалуы тиіс. Потенциалдар деп аталатын аг жэне /3} белгісіздері, тек толтырылған ұяшықтар

бойынша анықталатын      аг + /3}Су(В)

— шарттарынан анықталады.

Толтырылған ұяшықтар саны (т+п-1) -ге тең, ал белгісіздер саны -(т+п). (т+п) — белгісіздерді анықтау үшін (т+п-1) теңдеулер жүйесі бар. Сонда, қандай бір болмасын шешімді анықтау үшін белгісіздердің біреуін кез-келген санға тең деп, еркімізше алу жеткілікті. Бұрын қарастырылған мысалға қайта оралайық. Ол мысалға потенциалдар әдісін пайдаланып, тиімді жоспар құрудың бірінші кезеңі қарастырылған болатын. Алғашқы жоспар анықталған. Біз тиімділікке жақынырақ ең кіші элементтер әдісімен табылған алғашқы жоспарды пайдаланамыз.Екішпі кезеңге көшейік.

Толтырылған ұяшықтар;                                                                 Теңдеулер

‘о,+Д=5

(1,2)                                                                         «і+А=1°

(2,3)

(3,2)

с^+А =12

а2 + А = 4 а32=0

Мысал үшін ах = 0, деп алайық. Сонда алғашқы үш теңдеулерден

д = 5,/32 = 10,/33 =12  болып анықталады.

а4 =4-р3 =4-12 = -8,а3 =-Ю

аг және /3} мәндерін кесте құрып анықтаған дұрыс. Ол үшін бұрыңғы қорлар

мен сұраныстар орнына аг жэне /3; мәндерін орналастырамыз.

(В) шартын, оған эквивалентті

Оі=С,-Р}                                                                                                                                                                            (С)

А=Суг(Д)

шарттары түрінде жазайық. Оларды бірікт3ріп, мынадай ережеғе келтіруге

болады:

Белгісіз потенциал — толтырылған ұяшықтағы тасымалдау құнынан белгілі мәнді азайту арқылы алынады.

Осы ережені біздің мысалдағы щжэне /3} мәндерін анықтауға қолданамыз

Кесте 8

  0 60  

50

  10
               
а2             70
а3          50    
    5

10

12
    А

А

А

сәйкес қүн мәндері

Кейбір санға тең болады деп ұйғарылатын потенциал рет

ахи -V і =5- 0 = 5
«2   =С12″^ Тг =10 -0 = 10
«з 13 \ =12 -0 = 12

Енді табылған (Д,/32,Д,) потенциалдарын қарастыруға көшеміз. Оларға сәйкес қойылатын (1, 2, 3) — бағандардан, белгісіз потенциалдарға жауап беретін толтырылған ұяшықтарды іздейміз. 1 -ші бағанда ондай үяшық жоқ. Екінші бағанда -(3,2) -ұяшығы бар. (С) формасын пайдаланып

а332— @2= 0-10 = -10 — мәнін аламыз. Жаңа Кесте -9-ды толтырайық:

Кесте 9

  0 5   60 10   50 12   10
а2               4   70
а3 -10       0   50      
      5   т 10     12  
      А     А     А  

 

3-ші бағанда толтырылған ұяшық -(2, 3). Оған а2 белгісіз потенциалы сәйкес қойылады.     а2 = С23 — /33 = 4 -12 = -8

Осымен потенциалдар жүйесін анықтауды аяқтаймыз.

Тиімділік шарттары (В) -ны тексерейік. Оны толтырылмаған ұяшықтар үшін жүргізу жеткілікті. Өйткені, толтырылған ұяшықтар үшін аталған шарттар

теңдік түрінде анықталады. Егер де алынған сандар теріс таңбалы немесе нөлге тең болса, онда бұл ұяшықта тиімділік сақталады. Керісішпе, егер ұяшықтардың кез-келген біреуінде оң сан болса, онда шешім тиімді емес. Сондықтан, оны жетілдіруге болады. Табылған шешімді тиімділікке тексерейік

¥яшықтар                     Тиімділік шарттары

 

(2,1)                                   «2 + А — С21 = -8 + 5 — 8 = -11

(2,2)                                < 0 а2222 =-8 + 10-6 =

(ЗД)                              -4<0 а3 + Д — С31 = -Ю + 5 — 0

          (з,з)                                                = -5 < 0 «з+А-Сзз =-10 +

12-0 = 2>0

Тиімділік шарты (3, 3) — ұяшығында орындалмай тұр. Олай болса, табылған тасымалдау жоспарын жетілдіруге болады. Потенциалдау әдісінің соңғы қадамын түсіндіруге көшеміз.

Қадам -3. Тасымалдау жоспарын жетілдіру^     Жоспарды жетілдіру тиімділік шарты орындалмайтын (і.}) ұяшығына Ө>0 тасымалын тағайындау арқылы жүргізіледі. Бірақ, нөлден өзгеше тасымалы і -ші жіберушіден тасылатын өнім шамасын көбейтеді. Дәл сол сияқты тұтынушы сұранысының да шамасы 0>0-ге артады. Бұл айтылғандарды жоғарыдағы мысал арқылы былай түсіндіруге болады.

1.    Тиімділік (3, 3) ұяшығында бұзылып тұр. Оған Ө>0 -тасымалын (-0) -тағайындаймыз. Ол тасымал шамасының 0 -ге өскенін білдіреді.

Кесте 10

120 60 50 10
70     70
50   50-0 +0
  60 100 80

3-ші жіберушіден 5+0 -жүк бірлігі кетті. Ол қордан артық. Сондықтан толтырылған ұяшыққа 50-Ө-аз өнім жібереміз де, басқа ұяшыққа +0 -орналастырамыз. Сонда жалпы баланс 50-0+0=50 -сақталады. Мысал -1.   Төмендегі кестеде келтірілген ашық көлік қатынасы есебін жабық есепке келтіріңіз.

Кесте 11

 

 

 

у-шілер

Жібер     Жіберушілердегі қор Тұтынушылар және олардың қажеттілігі
   

 

1

2

3 4
 

 

 

 

100

250

50 10
1 200

5

8

9 1
2 190

3

7

9 2
3 100

5

8

3 9

Шешуі:Есептің шешуін де кесте түрінде келтіреміз.

Кесте 12

Алгоритм Келтірілген алгоритмге сәйкестік
    Орнату

1

Жіберушілердің қорларының

Т

Ү^аг = 200+199+100 =490
  қосындысын анықтаймыз: ^а.

і=\

і=\

2

Барлық қажеттіліктердің

П

Ү^Ъ} = 100+250+50+10 = 410
  қосындысын ^ Ъ} -ді анықтау керек  

3

Алынған нэтижелерді салыстыру. т                    п

Ү^аг> ү^Ъ}( 490 > 410)

4

Егер жіберушілердегі қорлардың  
  жиынтығы қажеттіліктен артық  
  т                   п

болса К = ^ а. — ^ Ъ}. — айырымын

К = 490-410 = 80
  есептеу керек.  

5

Қажеттілігі  К  -ге  тең,   «жалған» «Жалған»   тұтынушыны   5   -ші
  тұтынушу енгіземіз. номермен, қажеттілігін 80 -ге тең
    етш енгіземіз.

6

Кестеге   жаңа   бағана   қосуымыз Қосымша 5 -ші бағана енгіземіз.
  керек.  

7

Жаңа      бағанадағы      тасымалдау Барлық     Сі5 =0,/’ = 1,2,3      -нольге
  құныны    нөлге    теңеп    алыңдар

гу =0)

теңеп аламыз.

8

Жаңа кесте құру керек. Нәтиже төмендегі 2 -ші кестеде
    келтірілген.

  Кесте 13

Жіберу-шілер Қорлар Тұлынушылар және олардың қажеттілігі

1

2

3 4

5

100

250

50 10

80

1 200

5

8

9 1

0

2 190

3

7

9 2

0

3 100

5

8

3 9

0

  Мысал 2. 

Өз бетінше жұмыс жасауға келесі кестеде келтірілген ашық есепті, жабық есепке келтіріңдер.

               Кесте 14

  Қорлар Тұтынушылар және олардың қажеттілігі
     
1

2

3
60

60

50
1 50 5

8

9
2 70 3

7

9
3 60 5

8

3

Мысал 3.   Берілген ашық көлік қатынасы есебін жабық есепке келтіріңдер.

Кесте 15

  Жіберу-шілер- Түтынушылар жэне олардың қажеттілігі
1 2 3 4
  дің қорлары 50 50 40 60
1 30 5 4 6 4
2 70 4 5 5 8
3 70 7 3 4 7

 

Шешуі:Есептің шешу жолын келесі кестеде келтіреміз.

Кесте 16

Алгоритм Келтірілген алгоритмге сәйкестік орнату

1

Жіберушілердің қорларының

т

қосындысын анықтау: г

і=\

Т

£аг = 30+70+70 = 170

г=1

2

Барлық сұраныстардың

п

қосындысын ^ Ъ} -ді анықтау.

ҮЪ} = 50+50+40+60 = 200

3

Алынған нәтижелерді салыстыру. г<^й;(170<200)

4

Егер жіберушілердегі қорлар тұтынушылардың сұраныстарынан аз болса,

3                    4

К = ^Ь^ — ^а* — айырымын табу.

К = 200-170 = 30

5

Қоры     К    -ге     тең,     «жалған жіберуші» енгізу. «Жалған»  жіберушіні  4  -ші  номермен енғіземіз, қор 30 -ға тең деп ұйғарамыз.

6

Кестеге қосымша жол енгізу. Қосымша 4 -ші жол енгіземіз.

7

Жаңа           жолдағы           шығын коэффициенттерін   нөлге   теңеп алыңдар (Су =0). Барлық С4; = 0,7 = 1,2,34 — ұйғарамыз.

8

Жаңа кесте құру керек. Нәтиже     төмендегі     2     -ші     кестеде келтірілген.

Кесте 17

 

 

 

 

 

Жіберу-шілер Жіберу-шілер-

дің қорлары

Тұтынушылар және олардың қажеттілігі
1 2 3 4
50 50 40 60
1 30 5 4 6 4
2 70 4 5 5 8
3 70 7 3 4 7
4 70 0 0 0 0

 

Мысал 4.   Өз беттеріңше орындауға . Ашық есепті жабық есепке келтіріңдер.

Кесте 18

Жіберу-шілер Жіберу-шілер-

дің қорлары

Тұтынушылар және олардың қажеттілігі
1 2 3 4
50 10 20 50
1 30 5 6 1 2
2 50 3 1 5 2
3 20 8 4 2 5
4 20 6 5 2 4

  Алғашқы базисті таралымды (распределение) анықтау

Бұрын қарастырылған 9.3-9.6.4 — пункттерінде біз потенциалдар әдісінің қолданылу ерекшеліктерін келтірдік. Мұнда алғашқы базистік таралымдарды анықтау үшін солтүстік — батыс бұрышы әдісі Фогель әдісі, ең кіші элементтер т.б. әдістер қолданылатындықтары айтылды. § — солтүстік -батыс бұрышы әдісін қолдану жолы көрсетілген болатын. Аталған әдісті бұлай қолдану көптеген кестелер сызуды, артық жұмыстар атқаруды қажет етеді. Сондықтан, көптеген оқулықтарда ол кестелерді бір жерге біріктіріп, пайдалану жолын жеңілдету мүмкіндіктері қарастырылады. Осы бағытта алғашқы базисті таралымды анықтауға қатысты бірнеше әдістерге тоқталайық.

Солтүстік -батыс бұрышы әдісі

Мысал -1.Берілген көлік қатынасы есебі үшін алғашқы базистік таралымдарды анықтаңдар.

Үш жіберуші және төрт тұтынушы пункттер бар. Қорлар мен тұтынушылар сұраныстары, тасымал құндары келесі кестеде келтірілген.

                                                                                              Кесте19

Жіберу-шілер Жіберу-шілер-

дің қорлары

Тұтынушылар және олардың сұраныстары
1 2 3 4
20 110 40 110
1 60 1

хц

2

x12

5

ХіЗ

3

x14

2 120 1

x21

6

x22

5

x23

2

x24

3 100 6

хзі

3

x32

7

хзз

4

x34

Осы кестеде келтірілген мәндерді пайдаланып, есептің:

I.      Экономика — математикалық моделін құрамыз.

II.   Солтүстік -батыс бұрышы әдісін пайдаланудың қысқа жолын көрсетеміз.

  1. Ең кіші элемент әдісін пайдалану ерекшеліктерін қарастырамыз.
  2. Тиімді шешімді потенциалдар әдісін пайдаланып табуға тоқталамыз.

I.  1) Әрбір жіберушілердің қорлары толық пайдаланылуға жіберілуі үшін әрбір жол бойынша, келесі теңдеулер жүйесі құрылады:

хп121314 =60,

x21 + x22 + x23 + x24 = 120,

x34 =100.

2)     Әрбір  тұтынушының  сұраныстары  қанағаттандырылуы  үшін  кесте бағаналары бойында орналасқан элементтерден

хп

+ x21 х31 = 20,

1 9

+ x22 — Х32 = 110,

x13

+ х23- Х33 = 40,

x14

_|_ ү*

94

4,Х34 = 110

теңдеу жүйесін құрамыз.

3) Тасымалданатын жүк көлемі теріс бола алмайтындықтан, қосымша

ху >0(/ = 1,2,3; і = 1,2,3,4)                    (3)

—   шарты қойылады.

4)   Тасымалдаудың қосынды шығыны Ғ шығын коэффициенттері мен жүк шамасы арқылы анықталады:

Ғ-С   -х   +С   -х   +С   -х   +С   -х   +С   -х   +С    -х    +С   -х    +С    -х    +

Есептің математикалық қойылуы:

(1) -(3) шектеулер жүйесінің теріс емес шешімдері жиынынан      X   =   (   хц,   хіг,   …,   Х34)   шешімін   сызықты   (4)   функциясы   ең   кіші   мән қабылдайтындай етіп табу керек.

Көлік   қатынасы   есебінің   экономика   -математикалық   моделінің   негізгі ерекшеліктері мынадай:

—    шектеулер  жүйесі теңдеулер жүйесі түрінде, яғни көлік қатынасы  есебі
канондық түрде беріледі;

—   шектеулер жүйесінің коэффициенттері бірге не нөлге тең;

—   әрбір айнымалы шектеулер жүйесінің құрамына екі реттен енеді: бір рет —
жіберушілердің шектеулер жүйесіне, екінші рет — тұтынушылардың шектеулер жүйесіне.

Солтүстік —батыс бұрышы әдісін қолдану^

Солтүстік -батыс бұрышы әдісін пайдалану жолын көрсету үшін Кесте -1-дің сандық мәліметтер берілген бөлігін бөлек қарастырамыз.

Кесте 20

  20 110 40

110

60      

120      

100      

 

Қойылған есепті жекелеген қадамдарға бөліп қарастырайық. Мұнда да сол жақ шеткі бағана бойында орналасқан қорларды сұраныстарына байланысты қажетті пункттерге тарату мүмкіндіктері қарастырылады.

1)   Айнымалы хц-ге жеткізуге болатын ең үлкен шаманы таратамыз. Басқаша
айтқанда кестенің ( 1; 1) — «Солтүстік -батыс» бұрышына:

x11= тіп(60,20) =20 — жеткізіледі. Сонда 1 -ші тұтынушының қажеттілігі өтеледі. Алдағы уақытта бұл бағанды қарастырмауға болады. Оны диагональ бойындағы тұтас сызықпен ерекшелейміз. Бағананың қалған ұяшықтарын пунктир сызықтары арқылы ерекшелейміз.

2)      Енді жаңа «Солтүстік -батыс» бұрышы үшін (1; 2) — ұяшығын аламыз.
Мұнда қалған 60 — 20 = 40 жүк бірлігі жеткізіледі. х\2 = тіп(40, 110) = 40.
Осымен 1 -ші жеткізушідегі қор бітеді. (1,2)- үұяшығын тұтас сызықпен, ал 1 -ші жол бойындағы қалған ұяшықтарды пунктир сызықтармен ерекшелеп,ол жолды алдағы уақытта қарастырмаймыз.

3)    Кестенің қалған бөлігінен тағы да «Солтүстік -батыс» бұрышын таңдаймыз.

(2, 2) ұяшығына———-    бірлік жүк жеткізіледі. Сонымен 2 -ші тұтынушының

қажеттілігі өтелді. Оны бұрыңғыша қарастырудан шығарамыз.

4)    Жаңа «Солтүстік -батыс» бұрышы — (2; 3) -үяшығы. 120 -70 = 50 бірлік жүк
2-ші жеткізушіде қалған болатын. Оның 40-бірлігін (2; 3) — ұяшығына жеткізіп,
3-ші  тұтынушының  қажеттігін  өтейміз.Үшінші   бағананы  да  қарастырудан шығарамыз.

Жаңа «Солтүстік -батыс» бұрышы үшін (2; 4) — ұяшығын қабылдаймыз. Оған
2-ші жіберушіден қалған 120 -(70 +40) = 10 жүк бірлігін жеткіземіз. Сонда 2 -ші жеткізушінің қоры сарқылады: 120 -(70 +40 +10) = 0. Оны қарастыруданшығарамыз.

6)    Жаңа «Солтүстік -батыс» бұрышы — (3, 4) — ұяшығы. Оған 3 -ші жеткізуші қорындағы   100   бірлік  жүкті   жеткіземіз.   Осымен,   барлық   сұраныстардың қанағаттанғанын көруге болады. (3, 4) ұяшығын тұтас сызықпен ерекшелейміз.

Алғашқы базисті құрудың «Солтүстік -батыс» бұрышы әдісінің негізгі кемшілігі, онда тасымал құны коэффициенттері, яғни шығындалу коэффицинттері ескерілмейді.

Ең кіші элемент әдісгі    Аталған әдіс ең аз шығындану әдісі- деп те

аталады. Әдістің ерекшелігі алдыңғы жағдайдағы кемшілікті жою мүмкіндігі.

Мұнда   жеткізілетін    жүк    «Солтүстік    — батыс»    ұяшығына    емес,    шығын коэффициенті ең аз ұяшыққа жеткізіледі. Бұлай жасау тиімділікке жақындата түседі.

Мысал:     Ең  аз  шығындану  әдісімен   берілген  есептегі  алғашқы   базистік  таралымды анықта.

Шешуі:    Алдыңғы қарастырылған есептің шарты сақталсын, яғни Кесте -2-ні қайта пайдаланамыз.  

  20 110 40 110
60        
120        
100        

 

Жүктерді жеткізу кестесінде ең аз шығындалу коэффициенттері екі (1; 1) және (2; 1) ұяшықтарында орналасқан, эрі 1-ге тең. Екі үяшыққа да жеткізілу керек жүктің максимум шамалары x11= тіп(60,20) =20 жэне х2і = тіп(120, 20) = 20. Екеулері бірдей болғандықтан, олардың қайсысын таңдап алсақ та болады. Мысалы, жүк (2; 1) үяшығына жеткізілетін болсын. Нәтижесінде бірінші тұтынушыны сұранысы    қанағаттандырылады.    Ол үяшықты алдағы уақытта, қарастырудан ойша шығарамыз. (2; 1) — үяшығына 20 санын жазып, диагональ бойын түтас сызықпен ерекшелейміз де, бағананың қалған үяшықтары пунктирмен ерекшеленеді.

Кестенің қалған бөлігінде ең аз шығындалу коэффициенттері екеу: Сі2 = Сг = 2. Ол үяшықтар үшін ең көп жеткізу мүмкіндіктері: (1; 2) -үшін x12= тіп(бОДЮ) =60; (2; 4) — үшін x24 = тіп(120-20, 110) = 110. Екеуінің үлкен сан мэнін x24 = 100- меншіктейміз. Нэтижесінде 2 -ші жолды да қарауды ойша шығарамыз.   Сәйкес   ерекшелеу  жүргізіледі.   Кесте  -3   -тің  өзгерген  түрін келтірейік.

   Кесте 21

  20 110 40 110
60        
120        
100        

Осылайша қалған үяшықтармен жүмыс жасау жалғасады: Келесе: Сп = 2; х\2 = тіп {60, 110} = 60 (жол).

С32= 3; х32 = тіп {100, 110-60} = 50 (бағана). Сз4 = 4;х34 = тіп {100-50, 110-100} = 10 (бағана). Сзз= 5; х3з = тіп {100-60, 40} = 40 (жол толығымен).

         

Кесте

5.

 

 

  20  

110

40 110  
60    

 

 
120    

 

ГОО’
100 б^—— __-—-—

3__———5ТГ

7^———Ш

4^____ ——

 

Екі қарастырылған эдістер бойынша алынған жүктердің таралымдарын салыстырайық. «Солтүстік -батыс» бүрышы эдісі бойынша есептелген қосынды шығын ақша бірлігін шаққанда мынаған тең:

Ғ = 1 • 20 + 2 • 40 + 6 • 70 + 5 • 40 + 2 • 10 + 4 • 100 = 1140;

Ең аз шығындалу эдісі бойынша: Ғ = 1 • 20 + 2 -60 + 3 • 50 + 2 • 100 + 7 • 40 + 4 • 10 = 810.

Салыстырудан «Солтүстік батыс» бұрышы эдісі бойынша табылған қосынды шығын, ең аз шығындалу әдісіне шаққанда элдеқайда көп екенін көреміз. Олай болса, екінші жағдайдағы жауаптың тиімділікке элдеқайда жақын екенін байқаймыз. Есепті шығарудың келесі кезеңі тиімді шешімді іздеу. Оны потенциалдар әдісін пайдаланып табуға болатындығы §9.3- көрсетілді.

Біз алғашқы тасымалдау жоспардың эдісіне тоқталатын боламыз. Ол эдістің атауы американ математигі У.Фогельдің есімімен байланысты.

.
Загрузка...

Тағы рефераттар