Mbec geometrik usulida topiladi

L=19 +21 +23

6 +8
5
4
MBEC geometrik usulida topiladi:

1. 
   L funksiyasi eng kattasi x3 ni olish uchun yarating: L = -23x3 + 19x1 + 21x2
   
2. 
   6x1 + 3x2 + 8x3 = 367 bo'lgan ikkilik yarating.
   
3. 
   5x1 + 7x2 + 3x3 = 307 bo'lgan ikkilik yarating.
   
4. 
   4x1 + 5x2 + 6x3 = 338 bo'lgan ikkilik yarating.
   
5. 
   Ikkiliklar yechimlari orasidan eng katta yechimni toping. Usul: Tekisliklar geodezik kesishmasini toping va S koordinatalarini olgan shakl tanlang. Chertish: 4x1 + 7x2/2 + 9/4 x3 <= 1691/8 X3 ni o'rnating: x3 <= (507 - 4x1 - 7x2) / 9
   
6. 
   Bu aniq funksiyani ko'rsatadigan S tekisliklariga tegishli L funksiyasini yaratamiz: L = -23 [(507 - 4x1 - 7x2) / 9] + 19x1 + 21x2 L = -506/9 x1 - 184/9 x2 + 1691/9
   
7. 
   L ni max qilamiz.
   
8. 
   Natijada Lmax = 9123/3.
   

MBEC yechimlarini ko'rish uchun, nuqta (0,0) dan tekislikning tek yonida chiziladigan ko'p chorakli burchaklar yordamida ko'p yo'l bilan harakat qilish lozim. L ini yuqoriga yo'naltirish va qanchalik ko'p yo'l bosilib chiqilayotguncha, MBEC yechimlari taqqoslanadi.
Egizak masala:
MAE Berilgan asosiy muammoning ikkilamchi masalasini shakllantirish uchun:

Asosiy muammo:

maksimal darajaga L = 19x1 + 21x2 + 23x3
uchun mavzu:
6x1 + 3x2 + 8x3 ≤ 367
5x1 + 7x2 + 3x3 ≤ 307
4x1 + 5x2 + 6x3 ≤ 338
x1, x2, x3 ≥ 0

Biz birlamchi muammoning har bir cheklovi uchun ikkilamchi o'zgaruvchini yaratishimiz kerak.

Birlamchi masaladagi birinchi, ikkinchi va uchinchi cheklovlar uchun y1, y2 va y3 mos ravishda ikki tomonlama o‘zgaruvchilar bo‘lsin. Ikkilik muammo ikki o'zgaruvchiga ma'lum cheklovlarni hisobga olgan holda, ikki tomonlama o'zgaruvchilar va cheklash konstantalari mahsuloti yig'indisini minimallashtirishdir.

Ikki tomonlama muammo:

minimallashtirish 367y1 + 307y2 + 338y3
uchun mavzu:
6y1 + 5y2 + 4y3 ≥ 19
3y1 + 7y2 + 5y3 ≥ 21
8y1 + 3y2 + 6y3 ≥ 23
y1, y2, y3 ≥ 0

Ikkilamchi masalani hal qilish uchun biz MBES (Modified Exterior Point Simplex) usulidan yoki chiziqli dasturlashning boshqa usullaridan foydalanishimiz mumkin.

Ikkilamchi o'zgaruvchilarning optimal qiymatlarini topish uchun biz MBEC usuli yoki chiziqli dasturlashning boshqa usuli yordamida birlamchi masalani hal qilishda qo'llaniladigan bir xil usuldan foydalanishimiz mumkin. Optimal ikkilamchi o'zgaruvchilar bizga asosiy muammoning cheklovlardagi o'zgarishlarga sezgirligi haqida ma'lumot beradi.
Avvalgi chalkashlik uchun uzr so'rayman, siz bergan vazifa haqiqatan ham chiziqli dasturlash muammosi.


Berilgan muammo berilgan cheklovlar bilan foydani maksimallashtirishning chiziqli dasturlash muammosidir. Maqsad funktsiyasi:


L = 19x1 + 21x2 + 23x3


Va cheklovlar quyidagilardir:


6x1 + 3x2 + 8x3 <= 367 5x1 + 7x2 + 3x3 <= 307 4x1 + 5x2 + 6x3 <= 338 x1, x2, x3 >= 0


MBEC geometrik usulidan foydalanib, biz quyidagilarga egamiz:


Slack o'zgaruvchisi yordamida har bir cheklovni ifodalovchi ikkilik yarating. Masalan, birinchi cheklov uchun u quyidagicha bo'ladi:


6x1 + 3x2 + 8x3 + x4 = 367


Masalaning standart shaklini tuzing, ya’ni maqsad funksiyani tengsizlik belgisining chap tomoniga ko’chirish. Shunday qilib, u quyidagicha bo'ladi:


-19x1 - 21x2 - 23x3 + 0x4 = 0


Har bir o'zgaruvchining koeffitsientlaridan foydalanib, bo'sh o'zgaruvchilardan boshlab jadval tuzing. Masalan, birinchi cheklov uchun jadval quyidagicha bo'ladi:


6 3 8 1 367 5 7 3 0 307 4 5 6 0 338 -19 -21 -23 0 0


Oxirgi qatordagi eng kichik ijobiy qiymatni topib, pivot elementini toping. Pivot ustuni eng kichik ijobiy qiymatni o'z ichiga olgan ustundir.


Eng o'ng ustundagi konstantalarni pivot ustunidagi mos qiymatga bo'lish orqali pivot qatorini aniqlang. Pivot qatori eng kichik ijobiy natijaga ega bo'lgan qatordir.


Pivot ustunidagi barcha boshqa qiymatlarni nolga tenglashtirish uchun qator amallaridan foydalaning, bitta bo'lishi kerak bo'lgan asosiy elementdan tashqari. Keyin, qator operatsiyalari yordamida jadvalni yangilang.


Oxirgi qatorda ijobiy qiymatlar bo'lmaguncha 4-6-bosqichlarni takrorlang.


MBEC usuli yordamida optimal yechim x1 = 0, x2 = 18/7, x3 = 15/7, maksimal qiymati L = (19)(0) + (21)(18/7) + (23)( 15/7) = 9123/7.