Asosiy simpleks usuli bilan yechish

2- лабаратория.
Чизиқли программалаш масалалари (ЧПМ) ларни ечишда Симплекс усул моҳияти ва чизиқли программалаш масалалар бўйича топшириқ вариантларини тузиш бўйича услубий кўрсатмалар.


13-variant



3 x ₁ + 4 x ₂ + 2 x ₃ → maksimal
x ₁ + 2 x ₂ + x ₃ ≤ 18
2 x ₁ + x ₂ + x ₃ ≤ 16
x ₁ + x ₂ ≤ 8
x ₂ + x ₃ ≤ 6


Asosiy simpleks usuli bilan yechish
Har bir tengsizlik cheklovi uchun biz x ₄ ..x ₇ qo'shimcha o'zgaruvchilarni qo'shamiz . Cheklovlarni kanonik shaklda qayta yozing: 
x ₁ + 2 x ₂ + x ₃ + x ₄ = 18 
2 x ₁ + x ₂ + x ₃ + x ₅ = 16 
x ₁ + x ₂ + x ₆ = 8 
x ₂ + x ₃ + x ₇ = 6 
Biz dastlabki asosiy yechimni qidiramiz:
1-cheklov tengsizlikni o'z ichiga oladi, asos qo'shilgan qo'shimcha o'zgaruvchi bo'ladi x ₄
Cheklov 2 tengsizlikni o'z ichiga oladi, asos qo'shilgan qo'shimcha o'zgaruvchi bo'ladi x ₅
Cheklov 3 tengsizlikni o'z ichiga oladi, asos qo'shilgan qo'shimcha o'zgaruvchi x ₆
Cheklov 4 bo'ladi tengsizlikni o'z ichiga oladi, asos qo'shilgan qo'shimcha o'zgaruvchi bo'ladi x ₇


Boshlang'ich simpleks -jadval



Deltalarni hisoblash: D _i = C ₄ a _1i + C ₅ a _2i + C ₆ a _3i + C ₇ a _4i - C _i
Deltalar bilan simpleks jadval



Biz rejani optimallik uchun tekshiramiz: reja optimal emas , chunki D ₁ = -3 manfiy.
Takrorlash 1
Biz hal qiluvchi ustunni aniqlaymiz - minimal delta joylashgan ustun: 2, D ₂ : -4
B koeffitsientlarini 4 ustunning mos _keladigan
qiymatlariga bo'lish orqali Q simpleks munosabatlarini toping . Topilganlarning kesishmasida. satr va ustunda hal qiluvchi element mavjud : 1 Asosiy o'zgaruvchi sifatida x _{2 ni x 7} ni oling .



1, 2, 3-qatorlardan 2-ustundagi mos elementga ko‘paytirilgan 4-qatorni ayirib tashlang.
Yangi deltalarni hisoblash: D _i = C ₄ a _1i + C ₅ a _2i + C ₆ a _3i + C ₂ a _4i - C _i


Yangilangan deltalar bilan simpleks jadval



Joriy reja X: [ 0, 6, 0, 6, 10, 2, 0 ]
Maqsad funksiyasi F: 3 0 + 4 6 + 2 0 + 0 6 + 0 10 + 0 2 + 0 0 = 24
Biz rejani tekshiramiz. optimallik: reja optimal emas , chunki D ₁ = -3 manfiy.
Takrorlash 2
Biz hal qiluvchi ustunni - minimal delta joylashgan ustunni aniqlaymiz: 1, D ₁ : -3
B koeffitsientlarini 1- _ustunning
tegishli qiymatlariga bo'lish orqali Q simpleks bog'liqligini topamiz 3. kesishgan joyda. topilgan satr va ustun, hal qiluvchi element mavjud : 1 Asosiy o'zgaruvchi sifatida x ₆ biz x ₁ ni olamiz .



1, 2, 4-qatorlardan 1-ustundagi mos elementga ko‘paytirilgan 3-qatorni ayirib tashlang.
Yangi deltalarni hisoblang: D _i = C ₄ a _1i + C ₅ a _2i + C ₁ a _3i + C ₂ a _4i - C _i
Yangilangan deltalar bilan simpleks jadval



Joriy reja X: [ 2, 6, 0, 4, 6, 0, 0 ]
Maqsad funksiyasi F: 3 2 + 4 6 + 2 0 + 0 4 + 0 6 + 0 0 + 0 0 = 30
Biz rejani tekshiramiz. optimallik: reja optimal emas , chunki D ₃ = -1 manfiy.
Takrorlash 3
Biz hal qiluvchi ustunni aniqlaymiz - minimal delta joylashgan ustun: 3 , simpleks_QB koeffitsientlarini 2 ustunning mos qiymatlariga bo'lish orqali: -1₃D Topilgan kesishgan joyda satr va ustunda hal qiluvchi element mavjud : 2 Asosiy o'zgaruvchi x ₅ sifatida biz x ₃ ni olamiz .



2-qatorni 2 ga bo'ling. 1, 3, 4-qatorlardan 3-ustundagi mos elementga ko'paytirilgan 2-qatorni ayiring.
Yangi deltalarni hisoblang: D _i = C ₄ a _1i + C ₃ a _2i + C ₁ a _3i + C ₂ a _4i - C _i
Yangilangan deltalar bilan simpleks jadval





Joriy reja X: [ 5, 3, 3, 4, 0, 0, 0 ]


Maqsad funktsiyasi F: 3 5 + 4 3 + 2 3 + 0 4 + 0 0 + 0 0 + 0 0 = 33


Biz rejani tekshiramiz. optimallik: salbiy deltalar yo'q, shuning uchun reja optimaldir .


Javob: x ₁ = 5, x ₂ = 3, x ₃ = 3, F = 33