Chiziqli programmalashtirishda ikkilanish nazaryasi. Ikkilanish nazaryasi haqida asosiy tushunchalar

Mavzu: Chiziqli programmalashtirishda ikkilanish nazaryasi.

• Ikkilanish nazaryasi haqida asosiy tushunchalar.
• Ikkilangan masala tuzish usullari.

Reja:
Xar bir chiziqli programmalash masalasiga unga nisbatan ikkilangan masala deb ataluvchi boshqa masalani mos qo’yish mumkin. Berilgan masaladagi maqsad funksiyasi va nomalumlarga qo’yilgan chegaraviy shartlar orqali ikkilangan masalaning maqsad funksiyasini va chegaraviy shartlarni to’la aniqlash mumkin.
Berilgan masala va unga ikkilangan masalalar birgalikda o’zaro ikkilangan ( qo’shma ) masalalar deb ataladi. Agar berilgan masala yoki unga ikkilangan masalalardan birortasi yechimga ega bo’lsa, ularning ikkinchisi xam optimal yechimga ega bo’ladi.
O’zaro ikkilangan masalalarni ko’z oldiga keltirish va ularni iqtisodiy ma’nolarini taxlil qilish uchun quyidagi ishlab chiqarishni rejalashtirish masalasini ko’ramiz.
 
(1)
 
(2)
(3)
Masalaning (1) sharti maxsulot ishlab chiqarish uchun sarf qilinadigan m xil xom ashyoning xar biri chegaralangan ekanligini va ularni meyorida sarf qilish kerakligini ko’rsatadi. Bu yerda ishlab chiqariladigan -maxsulot miqdori,
- xom ashyoning zaxirasi (zapasi)
- koeffissentlar -maxsulotning I birligini ishlab chiqarish uchun sarf qilinadigan - xom ashyo miqdori (normasi)ni ko’rsatadi. maqsad funksiya bo’lib u ishlab chiqarilgan maxsulotlarning pul qiymati maksimum bo’lishi kerakligini ko’rsatadi, bu yerda
- maxsulot I birligini bahosidir.
Masalani vektor formada quyidagicha yozish mumkin:
(4)
(5)
(6)
Faraz qilaylik, korxona malum bir sabablarga ko’ra maxsulot ishlab chiqarishni to’xtatgan bo’lsin. Shu sababli korxona xom ashyo va boshqa ishlab chiqarish vositalarini sotmoqchi bo’ladi. Korxona bu xom ashyolarni sotishdan olgan tushumi maxsulot ishlab chiqarib uni sotishdan olgan tushumidan kam bo’lmasligiga harakat qiladi. Ikkinchi tomondan xom ashyo sotib oluvchi korxona esa ularni kam harajat sarf qilib sotib olishga harakat qiladi. Ikkilangan masala xom ashyolarni sotuvchi va ularni sotib oluvchi korxonalar maqsadini amalga oshirishi kerak.
Buning uchun xom ashyolarni narxi qanday bo’lganda sotuvchi korxona zarar ko’rmaydi hamda sotib oluvchi korxonaning sarf qilgan xarajatlari min bo’ladi.
Matematik nuqtai nazardan ikkilangan masalani quyidagicha yozish mumkin.
(7)


Ikkilangan masaladagi (7) shart xar bir maxsulotning bir birligini ishlab chiqish uchun sarf qilinadigan barcha hom ashyolarning pul qiymati maxsulot bahosidan kam bo’lmaslik shartini ko’rsatadi. (9) shart esa maqsad funksiya bo’lib, u barcha hom ashyolarning baxosi minimal bo’lishi kerakligini ko’rsatadi.
Yuqoridagilardan xulosa qilib, ikkilangan masalalarning matematik modellarini quyidagi ko’rinishda ifodalash mumkin.
Simmetrik bo’lmagan ikkilangan masalalar
1. Berilgan masala Ikkilangan
AX=B YA≤C
X≥0,

2. Berilgan masala Ikkilangan
AX=B, YA≥C
X≥0,
Simmetrik ikkilangan masalalar

• Berilgan masala Ikkilangan masala

AX≥B, YA≤C,
X≥0, Y≥0


• Berilgan masala Ikkilangan masala

AX≤B, YA≥C,
X≥0, Y≥0 ,

Namuna

• Quyidagi mаsаlа uchun ikkilаngаn mаsalа tuzilsin.

Yechish.
Qaralayotgan masala simmetrik bo‘lmagan masalaning II shakliga doir. Ikkilangan masalada o‘zgaruvchilarning soni berilgan masala sistemasining tenglamalari soniga teng, ya’ni uchga teng. Ikkilangan masala maqsad funksiyasining koeffisiyentlari berilgan masala tenglamalar sistemasining ozod hadiga, ya’ni 12, 24 va 18 sonlarigа tеng bo‘ladi. Berilgan masala funksiyasining maksimumini topish talab qilingan bo‘lib, shartlar sistemasi faqat tenglamalardan iborat. Shu sababdan ikkilangan masalada maqsad funksiyasining minimumi topiladi va uning o‘zgaruvchilari ixtiyoriy qiymatlarni (jumladan, manfiy qiymatlarni ham) qabul qilishi mumkin bo‘ladi.
Berilgan masalaning har uchala o‘zgaruvchilari faqat nomanfiy qiymatlar qabul qilganligi sababli ikkilangan masala cheklamalari “” ko‘rininshdagi tengsizlikdan iborat bo‘ladi. Binobarin, berilgan masala uchun ikkilangan masala quyidagicha bo‘ladi.
2. Ushbu masala uchun ikkilangan masala tuzilsin.
Yechish. Bu mаsаlа shu ko‘rinishdа jаdvаldаgi bеrilgаn mаsаlаlаrning hеch birigа mоs kеlmаydi, lеkin birinchi tеngsizlikni chap va o‘ng qismlarini (–1) gа ko‘pаytirib, III shakldagi simmetrik masalani hosil qilish mumkin:
Bu masalaga ikkilangan masala quyidagi ko‘rinishda bo‘ladi:
Z
3. Quyidagi mаsаlа uchun ikkilаngаn mаsalа tuzilsin
4-misоl. Quydаgi bеrilgаn mаsаlаni ikkilаngаn simplеks usul bilаn yeching
Yechish: Bеrilgаn mаsаlаgа x5 vа x6 qo’shimchа o’zgаruvchilаr kiritаmiz vа аyrim tеng kuchli аlmаshtirishlаr bаjаrib uni quyidаgi kаnоnik ko’rinishgа kеltirаmiz:
Mustaqil talim.

• Berilgan masalaga ikkilangan masala tuzilsin.

2. Berilgan masalaga ikkilangan masala tuzing.

3. Berilgan masalaga ikkilangan masalani tuzing.
4. Berilgan masalaga ikkilangan masalani tuzing.