36
bunda ishlab chiqarilgan mahsulotni
sotishdan keladigan foyda eng katta
bo„lsin.
sarflangan umumiy xarajat eng kam
bo„lsin.
I va II chiziqli programmalash masalalari quyidagi xossalarga ega:
1.
Bir masalada chiziqli
funksiyaning maksimumi izlansa, ikkinchi masalada
minimum topiladi.
2.
Bir masalaning chiziqli funksiyasining koeffitsientlari ikkinchi masalalaning
ozod hadlaridan iborat bo„ladi.
3.
Standart ko„rinishdagi masalada agar maksimum izlansa barcha tengsizliklar
"
"
ko„rinishda, minimum izlansa barcha tengsizliklar rejasini
"
"
da bo„ladi.
4.
Har ikkala masalada o„zgaruvchilar oldidagi koeffitsientlardan tuzilgan
matritsalar bir biriga transponirlangan bo„ladi.
I - masala uchun
II – masala uchun
mn
m
m
n
n
a
a
a
a
a
a
a
a
a
A
2
1
2
22
21
1
21
11
mn
n
n
m
m
a
a
a
a
a
a
a
a
a
A
2
1
2
22
12
1
21
11
5.
Bir masaladagi cheklovlar sistemasidagi tengsizliklar soni ikkinchi
masaladagi o„zgaruvchilar soniga teng bo„ladi.
6. Har ikkala masalada o„zgaruvchilarga qo„yilgan nomanfiylik shartlari
saqlanadi.
7. Ikkilanma masalasini tuzish algoritmi:
1. Dastlabki masalaning barcha tengsizliklari bir xil bo„lsin:
agar dastlabki
masalada maksimum izlansa, cheklovlar sistemasi
"
"
, minimum izlansa
"
"
ko„rinishda bo„lishi kerak.
2.
1
A
matritsaga transponirlangan
1
A
matritsa topamiz.
3. O„zgaruvchilarga qo„yilgan nomanfiylik shartini va yuqoridagilarni hisobga
olib ikkilanma masala tuzamiz.
Ushbu masalaga ikkilanma masala tuzing:
max
3
2
0
,
0
4
3
12
4
2
3
2
1
2
1
2
1
2
1
2
1
2
1
x
x
F
x
x
x
x
x
x
x
x
x
x
Yechish.
1. Dastlabki
masalada maksimum izlanmoqda, shuning uchun
cheklovlar sistemasidagi barcha tengsizliklar sistemasi
"
"
ko„rinishga keltiramiz,
buning uchun birinchi va to„rtinchi tensizliklarni har ikkala qismini -1 ga
ko„paytiramiz.
37
0
,
0
4
3
12
4
2
3
2
1
2
1
2
1
2
1
2
1
x
x
x
x
x
x
x
x
x
x
2. Sistemaning ko„paytirilgan matritsasini tuzamiz.
F
A
:
3
2
4
:
1
1
3
:
1
1
12
:
4
1
2
:
1
3
1
3.
1
A
matritsaga transponirlangan
1
A
matritsani topamiz.
Z
A
4
3
12
2
3
1
1
4
1
2
1
1
1
3
1
4. Ikkilanma masalani yozamiz.
min
4
3
12
2
0
,
0
,
0
,
0
3
4
2
3
4
3
2
1
4
3
2
1
1
3
2
1
4
3
2
1
y
y
y
y
Z
y
y
y
y
y
y
y
y
y
y
y
y
Ikkilanmalik nazariyasining asosiy tengsizligi
Aytaylik, ikki juft I va II ikkilanma masala berilgan bo„lsin. Dastlabki va
ikkilanma masalalarning
n
x
x
x
X
,
,
,
2
1
va
n
y
y
y
Y
,
,
,
2
1
joiz yechimlari
uchun ushbu tengsizlik o„rinli
Y
Z
X
F
yoki
n
j
m
i
i
i
j
j
y
b
x
c
1
1
Isbot.
Dastlabki
masalaning
cheklov
sistemasining
tengsizlariga
m
i
b
x
a
n
j
i
j
ij
,
1
1
mos
ravishda
m
y
y
y
,
,
,
2
1
larga ko„paytirib chap va o„ng
qismlarini qo„shamiz va ushbuga ega bo„lamiz.
m
i
m
i
i
i
j
n
j
ij
i
y
b
x
a
y
1
1
1
(3.1.)
Shunga o„hshash
m
i
j
i
i
n
j
c
y
b
1
,
1
tengsizliklarni har ikkala qismini
n
x
x
x
,
,
,
2
1
o„zgaruvchilarga ko„paytirib qo„shish natijasida ushbuga ega bo„lamiz.
n
j
n
j
j
j
j
m
i
ij
i
x
c
y
a
x
1
1
1
(3.2.)
38
(3.1.) va (3.2.) tengsizliklarning chap qismlari
m
i
i
j
n
j
ij
y
x
a
1
1
ifodadan iborat
bo„lgani uchun tengsizliklarning tranzitivlik xossasiga ko„ra isbotlanishi zarur
bo„lgan tengsizlikni olamiz, ya‟ni
n
j
j
m
i
i
j
j
y
b
x
с
1
1
Optimallikning yetarlilik alomati
Teorema.
Agar o„zaro ikkilanma masalalarning joiz yechimlari
n
x
x
x
X
,
,
,
*
2
1
va
*
*
2
*
1
,
,
,
*
m
y
y
y
y
iborat bo„lib, ular uchun
*
*
y
Z
x
F
(3.3)
tenglik o„rinli bo„lsa, u holda
*
X
- dastlabki I masalaning,
*
y
- esa ikkilanma II
masalaning optimal yechimlari bo„ladi.
Isbot.
Aytaylik
1
X
dastlabki I masalaning ixtiyoriy joiz yechimi bo„lsin. u
holda asosiy tengsizlikka ko„ra
*
1
y
Z
x
F
.
1
X
dastlabki I masalaning ixtiyoriy
yechimi bo„lgani uchun (3.3) dan
*
1
x
F
x
F
ekanligi kelib chiqadi, ya‟ni
*
X
- I
masalaning optimal yechimi. Shunga o„xshash
II masala uchun optimallik
isbotlanadi.
Ikkilanmalikning birinchi teoremasi.
Teorema.
Agar ikkilanma masalalarning biri optimal yechimga ega bo„lsa, u
holda unga ikkilanma masala ham optimal yechimga ega bo„lib, ularning chiziqli
funksiyalarining optimal qiymatlari teng bo„ladi.
min
max
Z
F
yoki
*
*
y
Z
X
F
(3.4)
Agar chiziqli funksiyalardan birortasi chegaralanmaydigan bo„lsa, u holda
unga ikkilanma masala joiz yechimga ega bo„lmaydi.
Isbot.
Teoremaning birinchi qismining tasdiqiga (biz uni isbotsiz qabul
qilamiz) ko„ra, (3.3) tenglik na faqat optimallikning yetarlilik sharti,
balki unga
ikkilanma masala optimalangining zaruriy sharti ham bo„ladi.
Teoremaning ikkinchi qismini isboti teskarisiga faraz qilish metodi
yordamida oson isbotlanadi. Faraz qilaylik, dastlabki masalaning chiziqli
funksiyasi chegaralanmagan bo„lsin, ya‟ni
max
F
, ikkilanma masalalaning
cheklov sharti esa hech bo„lmaganda bitta yechimga ega bo„lsin, ya‟ni
m
y
y
y
Y
,
,
,
2
1
. U holda ikkilanmalikning
asosiy tengsizligiga
y
Z
x
F
ko„ra,
x
F
ning chegaralanmaganligiga zid bo„ladi. Bundan kelib chiqadiki,
max
F
da
dastlabki masalaga ikkilanma masala joiz yechimga ega bo„lmaydi.
