|
Ikkilamchi masala
Minimal qiymatini topish
(4)
Chegaraviy shartlar
(5)
(6)
Ikkilamchi mmasalalar quyidagi xususiyatlarga ega:
1. To‘g‘ridan-to‘g‘ri masalada maqsad funksiyaning maksimali (chiziqli shakl), qo‘sh masalada esa minimali izlanadi.
2. To'g'ridan-to'g'ri masalaning maqsad funktsiyasidagi o'zgaruvchilarning koeffitsientlari ikki tomonlama muammoning cheklovlar tizimining erkin a'zolari va aksincha, to'g'ridan-to'g'ri masalaning cheklovlar tizimining erkin a'zolari o'zgaruvchilarning koeffitsientlari. dual masalaning maqsad funksiyasida.
3. Har bir topshiriqda cheklovlar tizimi tengsizliklar ko'rinishida ko'rsatiladi va ularning barchasi bir xil ma'noga ega, ya'ni: maqsad funktsiyasi (to'g'ridan-to'g'ri masala) maksimalini topishda bu tengsizliklar " belgisi bilan yoziladi. dan kichik yoki teng”, minimal (ikki masala) topilganda esa – “katta yoki teng” belgisi bilan.
4. Cheklash tizimlarida o'zgaruvchilar uchun koeffitsientlar matritsalar bilan tavsiflanadi
bir-biriga nisbatan ko'chirilgan.
7. To'g'ridan-to'g'ri muammoning cheklovlar tizimidagi tengsizliklar soni ikki tomonlama masaladagi o'zgaruvchilar soniga to'g'ri keladi.
8. O‘zgaruvchilarning manfiy bo‘lmaslik shartlari to‘g‘ridan-to‘g‘ri va qo‘sh masalada ham saqlanib qoladi.
Yuqoridagi shartlarni qanoatlantiradigan ikkita chiziqli dasturlash masalalari simmetrik o'zaro dual masalalar deyiladi.
Bunday muammolar o'zaro ikki tomonlama muammolar deb ataladi.
To'g'ridan-to'g'ri masala va uning ikki tomonlama muammosi birgalikda o'zaro ikki tomonlama muammolarni tashkil qiladi va ularning har qandayini asl masala deb hisoblash mumkin, keyin ikkinchisi unga ikkilik bo'lib chiqadi.
Shunday qilib, biz chiziqli dasturlashning to'g'ridan-to'g'ri va dual masalalari o'rtasidagi muvofiqlikni ko'rib chiqdik, ammo hozirgacha faqat kanonik shaklda yozilgan masalalar uchun.
Keling, kanonik masala uchun asl masalaga ikkilangan masalani kompilyatsiya qilish qoidalarini tuzamiz:
1. Dastlabki masalaning cheklash tizimining barcha tengsizliklari bir xil ma’noli (ya’ni bir belgili) tengsizliklarga keltiriladi: agar dastlabki masalada maqsad funksiyasining (chiziqli shakl) maksimali qidirilsa, ular: "Kamroq yoki teng" belgisi bilan, lekin minimal bo'lsa - "katta yoki teng" belgisi bilan yoziladi. Buning uchun bu talab bajarilmagan tengsizliklar minus birga ko'paytiriladi.
2. Avvalgi bandda tasvirlangan o‘zgartirishlardan so‘ng olingan dastlabki masala o‘zgaruvchilari uchun koeffitsientlarning A matritsasini yozing va A matritsaga nisbatan ko‘chirilgan A’ matritsasini tuzing.
3. O‘zgaruvchilar uchun koeffitsientlar sifatida A’ matritsaning elementlarini, erkin a’zolar sifatida esa – o‘zgaruvchilar uchun koeffitsientlarni dastlabki masala maqsadi funksiyasida olib, ikki tomonlama masala bo‘yicha cheklovlar tizimini tuzing va tengsizliklarni yozing. 1-bandda olingan tengsizliklarga nisbatan qarama-qarshi ma'noga ega (ya'ni ular belgini o'zgartiradi).
4. O'zgaruvchilar koeffitsientlari uchun 1-bandda olingan dastlabki masalaning cheklovlar tizimining erkin a'zolarini olib, ikki tomonlama masalaning maqsad funktsiyasini (chiziqli shakli) tuzing.
5. Ular ikkilamchi masalani yechishda nimani topish kerakligini ko’rsatadi, ya’ni: maqsad funksiyasining minimali, agar boshlang’ich masalada maksimal izlansa, maksimal, minimum esa asl masalada qidirilsa.
6. Ikkilik masala o‘zgaruvchilarining manfiy bo‘lmasligi shartini yozing.
1-misol. Quyidagiga ikkilik masalani tuzing
maksimalini toping
Chegaraviy shartlar
Yechim. Dastlabki masala tizimining uchinchi tengsizligi ikki tomonlama masalani tuzish qoidalarining 1-bandiga javob bermaydi. Shunday qilib, uni minus birga ko'paytiramiz:
Ikkilamchi masalani kompilyatsiya qilishni osonlashtirish uchun kengaytirilgan B matritsasidan foydalanish yaxshidir, unda dastlabki muammoning cheklovlar tizimining o'zgaruvchilari uchun koeffitsientlar bilan bir qatorda, biz o'zgaruvchilar uchun erkin shartlar va koeffitsientlarni yozamiz. maqsad funktsiyasi, bu maqsadda qo'shimcha ustunni (chiziq bilan ajratilgan) va qatorni (qizil rang bilan ajratilgan) ajratib ko'rsatish. Biz B matritsani joyiga qo'yamiz va ko'chirilgan B' matritsasidan foydalanib, asl masalaga ikkilangan masalani tuzamiz. B va B matritsalari shaklga ega
,
Shunday qilib, chiziqli dasturlashning ikkilamchi masalasi Chegaraviy shartlarda funksiyaning minimalini topishga keltiriladi.
Keling, to'g'ridan-to'g'ri masala umumiy shaklda yozilganda (cheklashlar tizimida turli xil belgilarga ega bo'lgan tengsizliklar, shuningdek tenglamalar, o'zgaruvchilarning manfiy bo'lmasligi sharti bo'lishi mumkin) ikkita masalani tuzish holatiga to'xtalamiz. shart emas). Bunday vazifalar uchun qoidalar quyidagilar:
1. To‘g‘ridan-to‘g‘ri masaladagi erkin a’zolar – qo‘sh masalada maqsad funksiyasi koeffitsientlari.
2. To`g`ridan-to`g`ri masalada maqsad funksiyasi koeffitsientlari - qo`sh masalada erkin a'zolar.
3. To'g'ridan-to'g'ri masalada kengaytirilgan matritsa - qo'sh masalada ko'chirilgan kengaytirilgan matritsa.
4. To‘g‘ridan-to‘g‘ri masaladagi j-chi noma’lum manfiy emas – “katta yoki teng” belgisi bilan qo‘sh masalada j-chi tengsizlik.
5. Belgili cheklovsiz to'g'ridan-to'g'ri masalada j-chi noma'lum - tenglama ko'rinishidagi qo'sh masalada j-chi cheklov.
6. To‘g‘ridan-to‘g‘ri masaladagi j-chi noma’lum musbat emas – qo‘sh masalada “kichik yoki teng” belgisi bilan j-chi tengsizlik.
7. “Kichik yoki teng” ishorali to‘g‘ridan-to‘g‘ri masaladagi i-chi tengsizlik – qo‘sh masaladagi i-noma’lumlik manfiy emas.
8. Tenglama ko‘rinishidagi to‘g‘ridan-to‘g‘ri masaladagi i-cheklov ishorali cheklovsiz qo‘sh masaladagi i-ma’lum bo‘ladi.
9. “katta yoki teng” belgisi bilan to‘g‘ridan-to‘g‘ri masaladagi i-chi tengsizlik – qo‘sh masaladagi i-noma’lum musbat emas.
Do'stlaringiz bilan baham: |
