Optimallashtirish masalalarini yechish. Chiziqli dasturlash masalasini grafik usulda yechish

Cheklanishlar sistemasini qanoatlantiruvchi echimga mumkin bo’lgan echim deb ataladi.
Maqsad funksiyani maksimallashtiradigan (yoki minimallashtiradigan) mumkin bo’lgan echimga optimal echim deb ataladi.
O’zgaruvchilarning bironta bir manfiy bo’lmagan qiymatlar to’plamiga javob bermaydigan chiziqli va chiziqli bo’lmagan cheklanishlar sistemasi birgalikda bo’lmagan deb aytiladi va bunday masalalar yechimga ega bo’lmaydi.
bo’lgan sistemalar mumkin bo’lgan
yechimga
esa hech ega
Birgalikda bo’lmaganda bitta bo’ladi.
Matematik dasturlash mavjud bo’lgan hamma variantlarda oldindan qo’yilgan shartlar bajarilganda echimning optimal variantini topishga xizmat qiladi.
Chiziqli dasturlash masalasini ifodalashning bir necha variantlari mavjud bo’lib, ularning ikki turi ko’p qo’llaniladi.
Har qanday tengsizlik cheklanishni qo’shimcha manfiy
ko’rinishdagi bo’lmagan
o’zgaruvchilarni qo’shish orqali tenglama ko’rinishga aylantirish mumkin.

a1 x1 a2 x2 ... an xn a

Har qanday tengsizlikni qo’shimcha manfiy bo’lmagan o’zgaruvchi qo’shish orqali tenglikka keltirish mumkin.
shart quyidagi ikkita cheklanishga
ekvivalentdir:
o’zgaruvchilarga qo’shimcha o’zgaruvchilar
deyiladi.
Bu ko’rinishda ifodalangan masalaga standart chiziqli dasturlash masalasi deb aytiladi.
xn 1
1
xn
1
a1 x1 a2 x2 ... an xn a
xn 0
Chiziqli dasturlash masalasining
kanonik ko’rinishi deb quyidagiga aytiladi:
xi 0, i 1, 2,...n.
cheklanishlar sistemasi
Bu masala matritsa ko’rinishida quyidagicha yoziladi:
AX=B
(7)
... х bm
. . . . . . . . . . . . . .
(6)
...
...
(5)
am1x1 am2 x2 am nxn
a12x2 a22x2
a11x1 a21x1
z maqsad funksiya
х b1
х b2
max(c1x1 c2 x2 ...
a1n xn a2n xn
cn xn )