Ii bob. Simpleks usuli va uning dasturiy ta’minoti chiziqli programmalash va simpleks usuli

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 va tayanch rejani topishdir.

(2.1.15) sistemada berilgan x₁, x₂ , ... , x_n noma’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 0 o’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 nol koeffistient bilan qo’shiladi, ya’ni:

Z_max = c₁x₁+c₂x₂+...+ c_nx_n+c_n+1y₁+c_n+2y₂+...+ c_m y_m =