Chiziqli programmalash va simpleks usuli. Ishlab chiqarishni rejalashtirish masalasi

- CHDM ning hamma rejalari (yechimlari) to’plami qavariqdir;
-maqsad funksiyasi o’zining maksimal yoki minimal qiymatiga qavariq ko’p yoqlining qirralarining birida erishadi;
- qavariq ko’p yoqlining har bir qirrasi CHDMning tayanch rejasi bo’ladi.
Bizga quyidagi CHDM berilgan bo’lsin:
Z_max=c₁x₁+c₂x₂+...+ c_nx_n (2.1.14)
a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n b₁,
a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n b₂,
a₃₁x₁+ a₃₂x₂ + ... + a_3nx_n b₃,(2.1.15)
... ... ... ...
a_m1x₁+ a_m2x₂ + ...+ a_mnx_n b_m.
x_{1 , 2 , . . . , n}  0(2.1.16)
Bu CHDM quyidagi mazmunni beradi: (2) tengsizliklar sistemasidagi asosiy noma’lumlar (x₁,x₂,x₃,...,x_n)ning shunday qiymatlarini topish talab qilinadiki, topilgan qiymatlar musbat yoki nolga teng bo’lib, maqsad funksiyasi deb ataluvchi
Z_max =c₁x₁+c₂x₂+...+ c_nx_n
funkstionalga maksimal qiymat bersin.
Qaralayotgan CHDMdagi tenglamalar sistemasida n noma’lumlar soni, m esa tenglamalar sonini ifodalaydi. Amaliyotda: a) noma’lumlar soni tenglamalar sonidan katta (n > m); b) noma’lumlar soni tenglamalar soniga teng (n = m); c) noma’lumlar soni tenglamalar sonidan kichik (n < m) bo’lishi mumkin.
CHDMni yechish uchun birinchi bajaradigan ishimiz (2.1.15) tengsizliklar sistemasini kanonik ko’rinishga, ya’ni tenglamalar sistemasi ko’rinishiga keltirish vatayanch rejani topishdir.
(2.1.15) sistemada berilgan x₁, x₂ , ... , x_nnoma’lumlar (o’zgaruvchilar) asosiy noma’lumlar deb nomlanadi.
Demak, birinchi navbatda tayanch yechim(reja) topiladi.
(2.1.15) tengsizliklar sistemasini tenglamalar sistemasiga keltirish uchun, tengsizliklarning har biriga mos ravishda qo’shimcha noma’lumlar deb ataluvchi musbat yoki nolga teng bo’lgan ushbu y₁, y₂, ... , y_m 0o’zgaruvchilarni qo’shamiz. CHDMni iqtisodiy mazmuniga ko’ra qo’shimcha noma’lumlar (2) sistemaga musbat ishora bilan qo’shiladi.Biz noma’lumlar soni tenglamalar sonidan katta (n > m) bo’lgan holni qaraylik.
a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n+ y₁= b₁,
a₂₁x₁+ a₂₂x₂ + ... + a_2nx_n+ y₂= b₂, (2.1.17)
... ... ... ... ....
a_m1x₁+ a_m2x₂ + ...+ a_mnx_n+ y_m = b_m.
Demak, CHDMda berilgan noma’lumlar asosiy noma’lumlar, tengsizliklar sistemasini tenglamalar sistemasiga aylantirish uchun qo’shiladigan noma’lumlar qo’shimcha noma’lumlar deb ataladi.Qo’shimcha noma’lumlar «» ko’rinishdagi tengsizliklarga musbat, «» ko’rinishdagi tengsizliklarga esa manfiy ishora bilan qo’shiladi.
Chiziqli dasturlash masalasidagi tengsizliklar sistemasini tenglamalar sistemasi ko’rinishiga keltirish uchun qo’shiladigan qo’shimcha noma’lumlar maqsad funksiyasiga nolkoeffistientbilan qo’shiladi, ya’ni:
Z_max= c₁x₁+c₂x₂+...+ c_nx_n+c_n+1y₁+c_n+2y₂+...+ c_my_m =
=c₁x₁+c₂x₂+...+ c_nx_n+0y₁+0y₂+...+0y_m. (2.1.18)
Standart formadagi x₁, x₂ , ... , x_n o’zgaruvchilar bazis noma’lumlar, qo’shimcha kiritilgan y₁, y₂, ... , y_m 0 o’zgaruvchilar bazis bo’lmagan noma’lumlar deyiladi.
Bu yerda masalani echishda qulay bo’lsin uchun bazis no’malumlar sifatida x₁, x₂ , ... , x_n,, basis bo’lmagan no’malumlar sifatida y₁, y₂, ... , y_m tanlangan.
CHDMda boshlang’ich tayanch rejani topish uchun, masaladagi (2.1.15) tengsizliklar sistemasi qo’shimcha noma’lumlarni qo’shish natijasida tenglamalar sistemasi (2.1.17) ga aylantirilgach, bu sistema qo’shimcha noma’lumlarga nisbatan yechib olinadi, ya’ni:
y₁= b₁– (a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n),
y₂= b₂– (a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n),
y₃=b– (a₃₁x₁ + a₃₂x₂ + ... + a_3nx_n),(2.1.19)
... ... ... ... ... …
y_m = b_m– (a_m1x₁ + a_m2x₂+ ... + a_mnx_n).
Maqsad funksiyasini quyidagicha ifodalab olamiz:
Z_max=0-(- c₁x₁-c₂x₂-...- c_nx_n) +0y₁+0y₂+0y₃+...+0y_m.(2.1.20)
Topilgan (2.1.19) sistemadan qoidaga ko’ra asosiy noma’lumlar nolga tenglashtirib olinadi, ya’ni:
x₁= x₂= ... = x_n= 0.
Natijada quyidagi boshlang’ich tayanch rejaga ega bo’lamiz (bu yerda masalaning berilishidagi ozod hadlar musbat deb qaralmoqda):
y₁= b₁,y₂= b₂, y₃ = b₃, ... ,y_m = b_m , Z_max=0.(2.1.21)
CHDMda (2.1.21) ni (boshlang’ich tayanch rejani) umumiy holda quyidagicha yozish qabul qilingan:
X*= (x₁,x₂, ..., x_n, y₁, y₂,… , y_m)= (0, 0, .. ., 0 , b₁, b₂, ... , b_m).
Topilgan tayanch rejaning yechimlari (qiymatlari) musbat bo’lsa berilgan CHDMni simpleks usul bilan yechish mumkin bo’ladi.
Quyidagilarga e’tibor berishimiz lozim:
Agar chegaraviy shartlardagi b_iozod xadlar manfiy ishorali bo’lsa, u holda ularni har doim (-1) ga ko’paytirib, musbat holatga keltirish kerak.
Endi (2.1.19) va (2.1.20) da berilganlarni quyidagi ko’rinishdagi jadvalga joylashtiramiz va uni boshlang’ich simpleks jadval deb nomlaymiz.
Boshlang’ich tayanch reja chekli sondagi etap (simpleks)dan keyin optimal rejani hosil qilish yo’lini ko’rsatadi va har bir navbatdagi simpleks oldingisiga nisbatan optimal rejaga yaqinroq rejani beradi. Masalani yechish jarayoni optimal yechim topilguncha yoki masalaning maqsad funksiyasi chekli maksimum (minimum)ga ega emasligi aniqlanguncha davom ettiriladi.
2.1.2-jadval

Bazis o’zgaruv- Chilar