Chiziqli dasturlash masalalarini yechishning geometrik talqini

3. Chizikli dasturlash masalalarini grafik usulida yechish.
Grafik usuliga ko‘ra chiziqli dasturlash masalalarni asosan ikki o‘lchovli fazoda, ya’ni tekislikda ko‘riladi. Uch o‘lchovli fazoda esa juda kam ko‘riladi, chunki qo‘yilgan masala yechimlarini ifodalovchi ko‘pburchaklarni chizish ancha murakkab bo‘ladi. Uchdan yuqori o‘lchovli fazoni tasavvur qilish esa mumkin emas.
Faraz qilaylik, tekislikda
(1)
maqsad funksiyaning, x₁, x₂ lar
(2)
tengsizliklar sistemasini qanoatlantirgandagi eng kichik qiymatini topish talab qilinsin.
(2) tengsizliklar sistemasini birgalikda deb faraz qilsak, u holda bu tengsizliklar sistemasini o‘rinli yechimlar to‘plami bo‘lgan biror ko‘pburchakni tashkil etadi.

ABCDEF ko‘pburchakning shunday nuqtasini topishimiz kerakki, bu nuqtada to‘tsri chiziq shu ko‘pburchak uchun tayanch to‘tsri chiziq bo‘lib, (1) funksiyamiz eng kichik qiymatga erishsin.

Masala. YUqoridagi yoqilsi (aralashma) masalasini grafik usulda echaylik. (1)
maqsad funksiyaning x₁, x₂ lar
(2)
cheklanish tengsizliklar sistemasini qanoatlantiradigan qiymatlarida eng katta qiymati topilsin.
(2) tengsizliklar sistemasini tenglamalari sistemasi ko‘rinishida yozib ularga mos kelgan to‘tsri chiziqlarni chizaylik.

L₁, L₂ - to‘tsri chiziqlarning koordinata o‘qlari bilan kesishish nuqtalarining koordinatalari (0; 62,5) va (83,3; 0); (0; 150) va
(75; 0)


F_max =100×70+120×10=8200 co‘m,
f=F_max×1000=8200000 so‘m bo‘lgan eng ko‘p foyda olish uchun A aralashmadan 70 tonna V aralashmadan 10 tonna tayyorlash kerak ekan.


4.Simpleks jadval usuli
Simpleks usuli chiziqli dasturlash masalasini yechishning asosiy usullaridan biri bo‘lib, ketma-ket yaqinlashish usuli yordamida x₁,x₂, . . .x_n o‘zgaruvchilarning shunday optimal qiymatini topadiki, bu qiymatlar maqsad funksiyasiga maksimal (yoki minimal) qiymat beradi.
Quyidagi chiziqli dasturlash masalasi berilgan bo‘lsin:

Masalani yechish uchun simpleks jadval quramiz va simpleks usuli g‘oyasini berish uchun berilgan masalani quyidagicha kanonik formada yozamiz.

Bu yerda x_n+i - ozod o‘zgaruvchilar deyiladi. Ularni qulaylik, hamda boshqa o‘zgaruvchilardan farqlash uchun mos ravishda y₁,y₂, . . .y_m deb belgilaymiz va yana quyidagi belgilashlarni kiritamiz b_i0=b_i; b_i,j=a_i,j; b_0j=c_j. Bu belgilashlar asosida quyidagi simpleks jadval deb ataluvchi jadvalni tuzamiz.

BO‘	1	-x1	-x2	. . .	-xs	. . .	-xn
y1	b10	b11	b12	. . .	b1s	. . .	b1n
y2	b20	b21	b22	. . .	b2s	. . .	b2n
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
ys	br0	br1	br2	. . .