|
1-Masala:Chiziqli dasturlash masalasini simpleks usulda yechish
Funksiya maksimal qiymati toping
cheklovlarga muvofiq:
|
|
x1 +
|
|
x2
|
|
|
|
x1 +
|
|
x2
|
|
|
|
x1 +
|
|
x2
|
|
|
|
x1 +
|
|
x2
|
|
|
x1 ≥ 0 x2 ≥ 0
|
Yechim
1.Bu muammoni hal qilishning zarur shartidir:
cheklash tizimining o'ng qismidagi raqamlar salbiy bo'lmasligi kerak.
Bu holat amalga oshiriladi.
2. Bu muammoni hal qilishning zarur shartidir:
barcha cheklovlar tenglamalar bo'lishi kerak.
|
-
|
|
x1
|
-
|
|
x2
|
≤
|
4
|
|
|
x1
|
-
|
2
|
x2
|
≤
|
2
|
|
|
x1
|
+
|
|
x2
|
≤
|
15
|
-
|
2
|
x1
|
+
|
|
x2
|
≤
|
2
|
|
-
|
|
x1
|
-
|
|
x2
|
+
|
|
S1
|
|
|
|
|
|
|
|
|
|
=
|
4
|
|
|
x1
|
-
|
2
|
x2
|
|
|
|
+
|
|
S2
|
|
|
|
|
|
|
=
|
2
|
|
|
x1
|
+
|
|
x2
|
|
|
|
|
|
|
+
|
|
S3
|
|
|
|
=
|
15
|
-
|
2
|
x1
|
+
|
|
x2
|
|
|
|
|
|
|
|
|
|
+
|
|
S4
|
=
|
2
|
S1 ≥ 0, S2 ≥ 0, S3 ≥ 0, S4 ≥ 0. Kiritilgan S1, S2, S3, S4 o'zgaruvchilarga slack o'zgaruvchilar deyiladi.
3. Boshlang'ich asosni va topilgan boshlang'ich asosga mos keladigan f funktsiyaning qiymatini topish.
Asos nima? Agar u ushbu tenglamaga bitta koeffitsient bilan kirsa va boshqa tenglamalar tizimiga kirmasa (tenglamaning o'ng tomonida manfiy bo'lmagan son bo'lsa), o'zgaruvchi tenglama uchun asosiy o'zgaruvchi deb ataladi.
Agar har bir tenglama asosiy o'zgaruvchiga ega bo'lsa, unda tizim asosga ega deb aytishadi.
Asosiy bo'lmagan o'zgaruvchilar asosiy bo'lmagan deyiladi.
Simpleks usulning g'oyasi nima?
Har bir asos bitta funktsiya qiymatiga mos keladi. Ulardan biri f funktsiyasining maksimal qiymati.
Biz bir asosdan boshqasiga o'tamiz.
Keyingi asos shunday tanlanadiki, f funksiyaning qiymati hozirgidan kam bo'lmaydi.
Shubhasiz, har qanday muammo uchun mumkin bo'lgan asoslar soni unchalik katta emas.
Shunday qilib, ertami-kechmi javob olinadi.
Qanday qilib biz bir asosdan boshqasiga o'tamiz?
Yechimni jadvallar shaklida yozib olish qulayroq. Jadvalning har bir qatori tizim tenglamasiga teng. Ajratib ko'rsatilgan qator funksiyaning koeffitsiyentlaridan iborat (quyidagi jadvalga qarang). Bu bizga har safar o'zgaruvchilarni qayta yozmaslikka imkon beradi. Bu vaqtni tejaydi.
Belgilangan qatorda maksimal ijobiy koeffitsientni tanlang (biz har qanday ijobiy koeffitsientni tanlashimiz mumkin).
Bu f funktsiyaning bizdan kam bo'lmagan qiymatini olish uchun kerak.
Ustun tanlanadi.
Tanlangan ustunning musbat koeffitsientlari uchun koeffitsientni sanaymiz va minimal qiymatni tanlaymiz.
Bu boshqa asosga o'tgandan keyin tenglamalarning o'ng qismida manfiy bo'lmagan sonlarni olish uchun kerak.
Qator tanlanadi.
Asosiy bo'ladigan element topiladi. Keyingi, biz hisoblash kerak bo'ladi.
Bizning tizimimiz asosga egami?
|
-
|
|
x1
|
-
|
|
x2
|
+
|
|
S1
|
|
|
|
|
|
|
|
|
|
=
|
4
|
|
|
x1
|
-
|
2
|
x2
|
|
|
|
+
|
|
S2
|
|
|
|
|
|
|
=
|
2
|
|
|
x1
|
+
|
|
x2
|
|
|
|
|
|
|
+
|
|
S3
|
|
|
|
=
|
15
|
-
|
2
|
x1
|
+
|
|
x2
|
|
|
|
|
|
|
|
|
|
+
|
|
S4
|
=
|
2
|
Bizning tizimimizda asos bor. Biz muammoni hal qilishni boshlashimiz mumkin.
F=-5x1+5x2
Asosiy bo'lmagan o'zgaruvchilar nolga teng. Yodda, biz asosiy o'zgaruvchilar qiymatlari topishingiz mumkin. (tizimga qarang)
Funktsiya F faqat asosiy bo'lmagan o'zgaruvchilarni o'z ichiga oladi. Shuning uchun bu asos uchun f funktsiyasining qiymati ongda topiladi.
x1 = 0 x2 = 0
S1 = 4 S2 = 2 S3 = 15 S4 = 2 => F = 0
Dastlabki asos topildi. F funksiyaning boshlang'ich asosga mos qiymati topildi.
4. F funksiyaning maksimal qiymatini topish.
Step №1
x1
|
x2
|
S1
|
S2
|
S3
|
S4
|
const.
|
Θ
|
-1
|
-1
|
1
|
0
|
0
|
0
|
4
|
|
1
|
-2
|
0
|
1
|
0
|
0
|
2
|
|
1
|
1
|
0
|
0
|
1
|
0
|
15
|
15 : 1 = 15
|
-2
|
1
|
0
|
0
|
0
|
1
|
2
|
2 : 1 = 2
|
-5
|
5
|
0
|
0
|
0
|
0
|
F - 0
|
|
-3
|
0
|
1
|
0
|
0
|
1
|
6
|
|
-3
|
0
|
0
|
1
|
0
|
2
|
6
|
|
3
|
0
|
0
|
0
|
1
|
-1
|
13
|
|
-2
|
1
|
0
|
0
|
0
|
1
|
2
|
|
5
|
0
|
0
|
0
|
0
|
-5
|
F - 10
|
|
Asosiy bo'lmagan o'zgaruvchilar nolga teng. Yodda, biz asosiy o'zgaruvchilar qiymatlari topishingiz mumkin. (jadvalga qarang)
Funktsiya F faqat asosiy bo'lmagan o'zgaruvchilarni o'z ichiga oladi. Shuning uchun bu asos uchun f funktsiyasining qiymati ongda topiladi. (jadvaldagi ajratib ko'rsatilgan qatorga qarang)
x1 = 0 S4 = 0
x2 = 2 S1 = 6 S2 = 6 S3 = 13 => F - 10 = 0 => F = 10
Step №2
x1
|
x2
|
S1
|
S2
|
S3
|
S4
|
const.
|
Θ
|
-3
|
0
|
1
|
0
|
0
|
1
|
6
|
|
-3
|
0
|
0
|
1
|
0
|
2
|
6
|
|
3
|
0
|
0
|
0
|
1
|
-1
|
13
|
13 : 3 ≈ 4,333
|
-2
|
1
|
0
|
0
|
0
|
1
|
2
|
|
5
|
0
|
0
|
0
|
0
|
-5
|
F - 10
|
|
-3
|
0
|
1
|
0
|
0
|
1
|
6
|
|
-3
|
0
|
0
|
1
|
0
|
2
|
6
|
|
1
|
0
|
0
|
0
|
1/3
|
-1/3
|
13/3
|
|
-2
|
1
|
0
|
0
|
0
|
1
|
2
|
|
5
|
0
|
0
|
0
|
0
|
-5
|
F - 10
|
|
0
|
0
|
1
|
0
|
1
|
0
|
19
|
|
0
|
0
|
0
|
1
|
1
|
1
|
19
|
|
1
|
0
|
0
|
0
|
1/3
|
-1/3
|
13/3
|
|
0
|
1
|
0
|
0
|
2/3
|
1/3
|
32/3
|
|
0
|
0
|
0
|
0
|
-5/3
|
-10/3
|
F - 95/3
|
|
Asosiy bo'lmagan o'zgaruvchilar nolga teng. Yodda, biz asosiy o'zgaruvchilar qiymatlari topishingiz mumkin. (jadvalga qarang)
Funktsiya F faqat asosiy bo'lmagan o'zgaruvchilarni o'z ichiga oladi. Shuning uchun bu asos uchun f funktsiyasining qiymati ongda topiladi. (jadvaldagi ajratib ko'rsatilgan qatorga qarang)
S3 = 0 S4 = 0
x1 = 13/3 x2 = 32/3 S1 = 19 S2 = 19 => F - 95/3 = 0 => F = 95/3
Ajratib ko'rsatilgan qatorda musbat koeffitsiyentlar mavjud emas. Shuning uchun f funksiyaning maksimal qiymati topildi.
Natijada:
x1 = 13/3 x2 = 32/3
Fmax = 95/3
2-Masala:Chiziqli dasturlash masalasini grafik usulda yechish
Do'stlaringiz bilan baham: |
