Ф-жоокб-01/018 Қазақстан республикасы білім және ғылым министрлігі

Қосжақты есептерді шешу үшін біреуіндегі шешімі табылса жеткілікті, ал екіншісінің шешімі алдыңғысы арқылы анықталады. Әрине шешілетін есеп алдымен сызықтық бағдарламалаудың негізгі есебіне келтірілуге тиіс.; сонда ғана симплекс тәсілін қолдануға болады.

Мысал ретінде өндірісті жоспарлау туралы есепті қарастырайық.

Есеп. Кірпіш зауыты кірпіштің үш түрін А,В,С шығарады және ол үшін үш түрлі І,ІІ,ІІІ ресурстарды пайдаланады. Әрбір кірпішті шығаруға жұмсалатын шикізат, ресурстар дайын өнімнен түсетін пайда келесі кестеде көрсетілген:

Максимум пайда түсіретін өндіріс жоспарын жасау керек.

Шешуі.

Алдымен есептің математикалық моделін құрайстырайық:

5 х₁ + 4х₂ + 6х₃ ≤ 160, х₁ ≥ 0,

4 х₁ + 5 х₂ + 3х₃ ≤ 120, х₂ ≥ 0,

3 х₁ + 2 х₂ + 4х₃ ≤ 100, х₃ ≥ 0,

Оны СБНЕ-ге келтірейік:
F (Х) = 10х₁ + 12х₂ + 9 х₃ + Ох₄ + Ох₅ + Ох₆  max

5 х₁ + 4х₂ + 6х₃ + х₄ = 160,

4 х₁ + 5 х₂ + 3х₃ + х₅ = 120,

3 х₁ + 2 х₂ + 4х₃ + х₆ = 100,

х_j ≥ 0, J =1,6

Оның қосжақты есебін жазайық:

4 y₁ + 5 y₂ + 2х₃ ≥12

6 y₁ + 3 y₂ + 4y₃ ≥ 9

y₁ , y₂ , y₃ ≥ 0

Тиімді шешім:

Х⁰ = (0; 40/3; 160/9; 0; 0; 20/9) ; F _max = 320.

Енді қосжақты есептің тиімді шешімін табайық; ол үшін:

6 4 0

А_б = 3 5 0 ; С_б = (9; 12; 0);

5/18 -2/9 0

А _б ^-1 = -1/6 1/3 0

-7/9 2/9 1

Егер соңғы симплекс кестесіне көңіл аударсақ, онда х₄ , х₅ , х₆ орналасқан тік жолдардағы а_1j коэффициенттері осы кері матрицаны құрайтынын көруге болады. Бұдан қосжақты есептің тиімді шешімін оңай табуға болады:

Y ⁰ = (1/2; 2; 0;) ; Z _min = 320.

Бұл жағдайда А _б ^-1 теріс матрицасын табудың қажеті жоқ, себебі ол алғашқы есепті шешу кезінде анықталды; ал қосжақты есептің тиімді шешімі соңғы кестенің m+1 –жатық жолындағы бірінші кестедегі бірлік векторлар орналасқан тік жолдағы элементтерге тең болады.

2. 
   Экономикалық талдау
   

Алғашқы есептің шешімі бойынша А түрлі кірпіш шығарылмайды, ал В және С түріндегілеп 40/3 және 160/9 мөлшерде шығарылады. Сонымен бірге І және ІІ ресурстар толығымен пайдаланылып, ал ІІІ-ші ресурс толық пайдаланылмайды. (20/9 артылып қалады). Қосжақты есептің шешуі бойынша толық пайдаланылған ресурс үшін y₁ ≥ 0 , ал толық пайдаланылмағаны үшін y₁ = 0.[12]

Сонымен y₁ ресурстардың пайдалану мөлшерін бағалайтын шама, немесе әрбір ресурс түрінің дефициттігін анықтайды.

Енді қосжақты есептің тиімді шешімі сәйкес шектемелерін қарастырайық:

4 ∙ ½ + 5 ∙2 + 2 ∙ 0 = 12 = 12

6 ∙ ½ + 3 ∙2 + 4 ∙ 0 = 9 = 9
Бірінші шектеме теңсіздік, ал қалғаны теңдеулер. Бұл дегеніміз А түріндегі кірпішті шығаруға жұмсалатын шикі заттардың бағасы одан түсетін пайдадан асып кетеді деген сөз, немесе ондай кірпішті шығару пайдалы емес. Екінші және үшінші шектемелі теңдеулер, немесе В және С түріндегі кірпіштерді шығару тиімді.

Осыдан мынадай қорытынды жасауға болады: қосжақты есептің шешімімен тікелей байланысты, әрі алғашқы есептің тиімді шешгіміне әсерін тигізетін факторлардың бағасын береді.

Келесі есептердің қосжақтылық есептерін құрастырып, шешімін табу керек.

Есеп.

2 х₁ + 4х₂ + х₃ +2 х₄ = 28, х₁ ≥ 0, х₄ ≥ 0

- 3 х₁ + 5 х₂ + 3 х₄ ≤ 30, х₂ ≥ 0,

4 х₁ - 2 х₂ + 8 х₄ ≤ 32, х₃ ≥ 0,

Шешуі:

Алғашқы есепке сәйкес қосжақты есепті құрастырайық:

4 y₁ + 5 y₂ - 2х₃ ≥ 3, y₂ ≥ 0;

2 y₁ - 3 y₂ + 8y₃ ≥ -5
Алғашқы есепті шешу үшін жасанды базис тәсілін қолданамыз, немесе келесі кеңейтілген есеп қарастырылады.
F₁ (Х) = х₁ + 3х₂ - 5 х₄ –М ∙ х₅  max
2 х₁ + 4х₂ + х₃ +2 х₄ + х₅ = 28

- 3 х₁ + 5 х₂ - 3 х₄ + х₅ = 30

4 х₁ - 2 х₂ + 8 х₄ + х₇ = 32

х_j ≥ 0, J =1,7

Тиімді шешім:

Х⁰ = (10/11; 72/11; 0; 0) ; F _max = 226/11

Y ⁰ = (7/11; 1/11; 0;) ; Z _min = 226/11.

2. 
   
   
   жүктеу/скачать 1,47 Mb.
   
   Достарыңызбен бөлісу: