Chiziqli dasturlashning o‘zaro ikki yoqlama masalalari

x₁- x₂ =3
-5x₁-3x₂+x₃=-10
x₁+6x₂-x₃=5
x_jі0, j=1,2,3
Z=8x₁+4x₂-2x₃ ®max
Ye ch i sh. Ikki yoqlama masalani tuzamiz. U quyidagi ko‘rinishda bo‘ladi.
y₁+y₂-5y₃+y₄≥8
- y₂-3y₃+6y₄≥4
2y₁ +y₃ - y₄≥-2
F=4y₁+3y₂-10y₃+5y₄ ®min

Masala shartlarini simpleks jadvalga kiritamiz.

BO‘	1	SO‘
		-y1	-y2	-y3	-y4
y5	-8	-1	-1	5	-1
y6	-4	0	1	3	-6
y7	2	-2	0	-1	1
F	0	-4	-3	10	-5

F qatorda musbat element (10 soni) mavjud, shu sabab bu son turgan ustun hal qiluvchi bo‘ladi. Bu ustunda ikkita musbat son mavjud, ulardan kattasini 5 sonini olamiz va F qator elementlarining shu qator elementlariga nisbatini qaraymiz, undan musbatlarining eng kichigini tanlaymiz, unga mos element hal qiluvchi bo‘ladi, ya'ni

Min|-4/-1; -3/-1; 10/5; -5/-1|=min{4; 3; 2; 5}=2

Demak, hal qiluvchi element 5 soniga teng. Simpleks almashtirish bajarib quyidagi jadvalga ega bo‘lamiz:

BO‘	1	SO‘
		-y1	-y2	-y5	-y4
y3	-8/5	-1/5	-1/5	1/5	-1/5
y6	4/5	3/5	8/5	-3/5	-27/5
y7	2/5	-11/5	-1/5	1/5	4/5
F	16	-2	-1	-2	-3

F qator elementlari barchasi manfiy, shu sabab ozod hadlar ustunini qaraymiz, unda manfiy element bor, u -8.5. Bu qator hal qiluvchi bo‘ladi. Yana F qator elementlarining shu qator elementlariga nisbatini qaraymiz, undan musbatlarining eng kichigini tanlaymiz, unga mos element hal qiluvchi bo‘ladi, ya'ni

Min|-2/-1/5; -1/1/5; -2/-1/5; -3/-1/5|=min{10; 5; -10; 15}=5.
Demak, hal qiluvchi element -1/5. Simpleks almashtirish bajarib quyidagi jadvalga ega bo‘lamiz:

BO‘	1	SO‘
		-y1	-y3	-y5	-y4
y2	8	1	-5	-1	1
y6	-12	-1	8	1	-7
y7	2	-2	-1	0	1
F	24	-1	-5	-3	-2

F qator elementlari barchasi manfiy, shu sabab ozod hadlar ustunini qaraymiz, unda manfiy element bor, u -12. Bu qator hal qiluvchi bo‘ladi. Yana F qator elementlarining shu qator elementlariga nisbatini qaraymiz, undan musbatlarining eng kichigini tanlaymiz, unga mos element hal qiluvchi bo‘ladi, ya'ni
Min|-1/-1; -5/8; -3/1; -2/7|=min{1; -5/8; -3; 2/7}=2/7.
Demak, hal qiluvchi element -7. Simpleks almashtirish bajarib quyidagi jadvalga ega bo‘lamiz:

BO‘	1	SO‘
		-y1	-y3	-y5	-y6
y2	44/7	6/7	-27/7	-6/7	1/7
y4	12/7	1/7	-8/7	-1/7	-1/7
y7	2/7	-15/7	1/7	1/7	1/7
F	192/7	-5/7	-51/7	-23/7	-2/7

Jadvaldan ko‘rinib turibdiki bu olingan plan optimal bo‘ladi. Demak, ikkilangan masalaning optimal yechimi y^*=(0; 44/7; 0; 12/7; 0; 0; 2/7), F_min=192/7.

Asosiy masala bilan ikkilangan masala o‘zgaruvchilari orasidagi bog‘lan-ishga ko‘ra ya'ni x_I↔y₅; x₂↔y₆; x₃↔y₇; x₄↔y₁; x₅↔y₂; x₆↔y₃; x₇↔y₄ asosiy masala yechimini ham topish mumkin , ya'ni x^*=(23/7; 2/7; 0; 5/7; 0; 5/7; 0) va Z_max=F_min bo‘lgani uchun Z_max=192/7.

Amaliy mashg‘ulot uchun misollar
Quyidagi chiziqli dasturlash masalasiga ikki yoqlama masala tuzing va uning birini yechib, ikkinchisining optimal yechimini aniqlang.

1. 2.

3. 4.

5. 6.

7. 8.

9. 10