Chiziqli dasturlash masalalarini yechish texnologiyasi

CHIZIQLI DASTURLASH MASALALARINI YECHISH TEXNOLOGIYASI SIMPLEKS - EXCEL JADVAL PROTsessorida USUL.
Simpleks usuli chiziqli dasturlashning asosiy masalalarini yechishning analitik usullaridan biridir. U, qoida tariqasida, uch yoki undan ko'p o'zgaruvchilarda, grafik usul imkonsiz bo'lganda qo'llaniladi.
Cheklovlar tizimi odatda chiziqli tenglamalar tizimi bilan beriladi:
 a x a x 11 1  12 2   ... a x 1 nn  b 1 ,
 axax 21 1  22 2   ... ax 2 nn  b 2 ,
 (4.1)
_ ...
 axax m 1 1  m 2 2  ... a x mn n  b m ,
___ ___
qayerda a _{i j} , b _{j -} i  1, n , j  1, m ixtiyoriy sonlar, mos ravishda o‘zgaruvchilarning koeffitsientlari va tenglamaning erkin shartlari deb ataladi.
(4.1) tenglamalar tizimining manfiy bo'lmagan yechimlari orasida chiziqli funktsiyani maksimal darajaga ko'taradiganlarini topish kerak:
𝑍 maks = 𝑐 1 ∙ 𝑥 1 + 𝑐 2 ∙ 𝑥 2 + 𝑐 3 ∙ 𝑥 3 + ⋯ + 𝑐 𝑛 ∙ 𝑥 𝑛 + 𝑐 𝑐 .
x ₁ , x ₂ , ..., x _r ( r  m ) ni boshqa o‘zgaruvchilar bilan ifodalaymiz :
xa 1  ^' 1. r _{ } 1 ^x r 1   ... a ^' 1. n n x  b ^' 1 x 2  a ^' 2. r _ 1 ^x r _ 1   ... a ^' 2. n n x  b ^' 2
(4.2)
.........
x r  a ' r r .  1 x r  1   ... a ' r n n . x  b ' , r
bu yerda b ' ₁  0, b ' ₂  0 , ... , b ' _r  0.
balans (nivelirlash) deb ataladigan yangi salbiy bo'lmagan o'zgaruvchilarni kiritish orqali tenglikka aylantirilishi kerak . Demak, masalan, tengsizlikda a ₁ x ₁  a ₂ x ₂  ...  a _n x _{n .}  b ga qandaydir x _{n  1}  miqdorni qo‘shish kifoya 0 va a ₁ x ₁  a ₂ x ₂  ...  a _n x _n tengligini olamiz.  x _{n  1}  b .
Cheklovchi shartlar aralash tarzda, ya'ni tengsizliklar va tenglamalar orqali ham berilishi mumkin, keyin ko'rsatilgan tarzda ularni tenglamalarga keltirish mumkin. O'zgaruvchilar ^xx ₁ ^, ₂ , ..., ^x _r asosiy , butun toʻplam {𝑥 ₁ , 𝑥 ₂ ,… , 𝑥 _𝑟 } bazis deb ataladi, qolgan oʻzgaruvchilar erkin , cheklovlar tizimi (4.2) birlik bazisga qisqartirilgan tizim deyiladi. 𝑍 _max chiziqli funktsiyaga bazis o'zgaruvchilar o'rniga ularning (4.2) bo'sh bo'lganlar ko'rinishidagi ifodalarini qo'yib, biz hosil bo'lamiz.
Zmax _   ^{ } 0 r _{ } 1 ^x r 1   ... ^ n n x .
Endi, barcha bo'sh o'zgaruvchilarni 0 ga teng qilib, biz asosiy o'zgaruvchilarning qiymatini topamiz:
x ₁  b ' ₁ , x ₂  b ' ₂ , ..., x _r  b ' _r .
tizimning yechimi maqbul bo'ladi, u asosiy bo'ladi . Olingan asosiy yechim uchun chiziqli funktsiyaning qiymati Z ₁   _{0 ga teng bo'ladi} .
Simpleks usuli yordamida masalani yechish bir qancha bosqichlarga bo'linadi, ular bir B _{1 asosdan ikkinchi B 2} asosiga ^Z _{B 1} qiymati kamayishi yoki hech bo'lmaganda o'tishimizdan iborat. , ortib ketmaydi, ya’ni Z B 2  Z B 1 .