Yechish
.
Aytaylik,
A
va
B
tovarlarni haftalik ishlab chiqarish rejasi mos
ravishda
x
1
birlik va
x
2
birlik bo„lsin.
Masala shartidan quyidagi tengsizliklar sistemasini tuzamiz
36
4
,
0
2
,
0
36
3
,
0
4
,
0
40
25
,
0
5
,
0
2
1
2
1
2
1
x
x
x
x
x
x
(1.3.412)
0
,
0
2
1
x
x
(1.3.513)
max
3
5
2
1
x
x
x
F
(1.3.614)
Masalada noma`lumlar soni ikkita, chegaraviy shartlar tengsizliklar
ko„rinishida berilgan, shuning uchun optimal yechim grafik usulda aniqlanadi.
(1.3.4) va (1.3.5) chegaraviy shartlardagi tengsizliklar
1
2
x Ox
koordinatlar
tekisligida yarim tekisliklardan iborat bo`lib, uning chegaralari mos ravishda
quyidagi to„g„ri chiziqlardan iborat (1.8 - rasm).
17
1
2
1
1
2
2
1
2
3
0,5
0, 25
40
( )
0, 4
0,3
36
(
)
0, 2
0, 4
36
( )
x
x
a
x
x
a
x
x
a
Yarim tekisliklarning kesishishidan hosil bo„lgan ko„pburchakni aniqlab,
normal vektor yordamida
)
3
;
5
(
N
, maqsad funksiya maksimal qiymatga
erishadigan nuqtani aniqlaymiz.
1.3.7 - rasm.
Rasmdan ko„rinadiki, maqsad funksiya
ABCDO
ko„pburchakning
C
nuqtasida maksimal qiymatga erishadi.
Bu nuqta esa
a
1
va
a
2
to„g„ri chiziqlar kesishishidan hosil bo„lib, uning
koordinatalari, quyidagi tenglamalar sistemasi yechimlaridan iborat
)
(a
)
(a
.
36
3
,
0
4
,
0
40
25
,
0
5
,
0
2
1
2
1
2
1
x
x
x
x
Sistema yechimlari
1
2
;
60; 40
x x
. Maqsad funksiyasining optimal qiymati
esa
420
40
3
60
5
3
5
max
2
1
x
x
x
F
.
Demak, firma 420 birlik foyda olishi uchun,
A
tovar ishlab chiqarishni 60
birlik,
B
tovarni esa 40 birlik kabi rejalashtirish zarur ekan.
Misol
.
Grafik usulda funksiyaning ekstremal qiymatlarini aniqlang
18
7
6
4
3
2
1
x
x
x
x
x
F
chegaraviy shartlarda
1
2
3
4
1
3
4
5
6
18
3
6
0
1, 4
j
x
x
x
x
x
x
x
x
j
Yechim.
Birinchi va ikkinchi chegaraviy shartlarni tengsizliklarga
aylantiramiz. Ikkinchi shartdagi
4
x
o„zgaruvchini birinchi shartga qo„yib,
ixchamlasak quyidagini hosil qilamiz:
18
1
2
3
4
1
3
3
6
6 3
0
1, 4
j
x
x
x
x
x
x
x
j
So„ngra, birinchi shartdagi
3
x
o„zgaruvchining qiymatini ikkinchi shartga
qo„ysak quyidagini hosil qilamiz:
3
1
2
4
1
2
6
3
4
3
12
0
1, 4
j
x
x
x
x
x
x
x
j
Masala shartiga ko„ra
3
x
va
4
x
manfiy bo„lmaganligi uchun, ular teng
bo„lgan ifodalar ham manfiy emas.
3
x
va
4
x
o„zgaruvchilarning bu ifodalari
maqsad funksiyaga qo„yiladi.
3
x
va
4
x
noma`lumlarni birinchi va ikkinchi
shartlardan tashlab yuborilsa, quyidagi model hosil bo„ladi:
2
,
1
0
12
3
4
6
3
2
1
2
1
2
1
j
x
x
x
x
x
x
x
x
F
j
Masalada noma`lumlar soni ikkita bo„lib, chegaraviy shartlar tengsizliklar
ko„rinishida bo`lgani uchun, masalaning optimal yechimini topishda grafik usuldan
foydalanilsa bo„ladi.
Yarim tekisliklarning kesishishi natijasida hosil bo„lgan ko„pburchakdan,
normal vektor
(1; 1)
N
foydalanib, maqsad funksiya maksimal qiymatga
erishadigan nuqtani aniqlaymiz.
1.3.8 – rasm.
Rasmdan ko„rinadiki, maqsad funksiya maksimal qiymatga quyidagi to„g„ri
chiziqlarning kesishish nuqtasida erishadi:
4
2
x
1
x
N
2
0
2 3 4
6
F=0
19
1
2
1
2
3
6
4
3
12
x
x
x
x
Bu nuqtaning koordinatalari (2; 4/3) dan iborat. Minimal nuqta esa (0,0)
nuqtada hosil bo„ladi. Natijada quyidagi javoblarni olamiz:
3
10
3
4
;
2
max
F
.
20
II-bob. Chiziqli programmalashtirish masalasining simpleks algoritmi
2.1. Chiziqli tenglamalar sistemasining nomanfiy yechimlarini topish
n
o„zgaruvchili
m
ta chiziqli tenglama ushbu ko„rinishga ega
m
n
mn
j
mj
m
m
i
n
in
j
ij
i
i
n
n
j
j
n
n
j
ij
b
x
a
x
a
x
a
x
a
b
x
a
x
a
x
a
x
a
b
x
a
x
a
x
a
x
a
b
x
a
x
a
x
a
x
a
2
2
1
1
2
2
1
1
2
2
2
2
22
1
21
1
1
2
12
1
11
1
.
1
.
2
,
,
yoki qisqacha
m
i
b
x
a
i
n
j
j
ij
,
1
1
(2.1.1) sistemada
n
j
m
i
a
ij
,
1
;
,
1
,
, matritsaning rangi
m
r
va
n
m
. (2.1.1)
sistemaning
m
ta o„zgaruvchilari oldidagi
n
m
koeffitsientlardan tuzilgan
matritsa determinanti noldan farqli bo„lsa, u holda
m
ta o„zgaruvchi bazis
o„zgaruvchi, qolgan
m
n
tasi bazis bo„lmagan yoki erkli o„zgaruvchi deyiladi.
Bazis o„zgaruvchilar guruhining mumkin bo„lgan maksimal soni
m
n
С
bo„ladi,
ya‟ni
m
n
С
dan katta bo„lolmaydi.
Aytaylik, masala
m
x
x
x
,
,
,
2
1
bazis o„zgaruvchilar bo„lsin, ya‟ni
0
2
1
2
22
21
1
12
11
mm
m
m
m
m
a
a
a
a
a
a
a
a
a
A
ChP masalasini yechishda
m
x
x
x
,
,
,
2
1
o„zgaruvchilarning va maqsad funksiya
o„zgaruvchilarning nomanfiy bo„lishi amaliy ahamiyatga ega shuning uchun
(2.1.1) chiziqli tenglamalar sistemasining nomanfiy yechimlarini topish zarur
bo„ladi.
Aytaylik, (2.1.1) chiziqli tenglamalar sistemasida barcha ozod hadlar
nomanfiy sonlardan iborat bo„lsin, aks holda -1 ga tenglamaning har ikki qismini
ko„paytirib musbat holga keltiramiz.
Dastlabki jadvalni yozamiz.
21
Bazis o„zgaruchilar
n
j
x
x
x
x
2
1
Ozod
hadlar
mn
mj
m
m
in
ij
i
i
n
j
n
ij
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
2
1
2
1
2
2
22
21
1
12
11
m
i
b
b
b
b
2
1
(2.2.2)
Masalani yechish hal qiluvchi elementni tanlashdan boshlanadi. Buni quyidagicha
amalga oshiramiz.
1)
Hal qiluvchi ustunni shunday tanlaymizki, unda hech bo„lmaganda bitta
musbat element bo„lsin.
2)
Aytaylik, hal qiluvchi ustunda bir nechta musbat elementlar bor bo„lsin.
Bunday holda ularga mos ozod hadlarni shu elementlarga nisbatini olamiz va
ularning eng kichigini hal qiluvchi element qilib tanlaymiz. (agar ustunda faqat
bitta musbat element bo„lsa, shu sonli hal qiluvchi element sifatida qabul qilamiz).
Bunday almashtirish simpleks almashtirish deyiladi.
| 