Algoritmlarni loyihalash fanidan mustaqil ishi

Agar chiziqli dastur cheklangan optimal yechimga ega bo'lsa, u holda burchak nuqtalaridan biri optimal yechimni ta'minlaydi.
Ushbu da'voning isboti quyidagi ikkita faktning natijalaridan kelib chiqadi:
1-fakt: Har qanday chiziqli dasturning mumkin bo'lgan hududi har doim qavariq to'plamdir.
Barcha cheklovlar chiziqli bo'lgani uchun, amalga oshirilishi mumkin bo'lgan mintaqa (FR) ko'pburchakdir. Bundan tashqari, bu ko'pburchak qavariq to'plamdir. Ikki o'lchovli LP dan yuqori bo'lgan har qanday muammoda FR chegaralari giper tekisliklarning qismlari bo'lib, bu holda FR ko'pburchaklar deb ataladi, bu ham qavariq. Qavariq to'plam - agar siz undan ikkita mumkin bo'lgan nuqtani tanlasangiz, bu ikki nuqtani birlashtiruvchi to'g'ri chiziq segmentidagi barcha nuqtalar ham amalga oshiriladi. Chiziqli dasturlarning FR har doim qavariq to'plamlar ekanligining isboti qarama-qarshilikdan kelib chiqadi. Quyidagi rasmlarda ikki turdagi to'plamlarga misollar ko'rsatilgan: qavariq bo'lmagan va qavariq to'plam.




Har qanday chiziqli dasturda amalga oshirilishi mumkin bo'lgan mintaqalar to'plami deyiladi ko'pburchak , agar u chegaralangan bo'lsa, u politop deb ataladi .
2-fakt: Chiziqli dastur maqsad funktsiyasining izo-qiymati har doim chiziqli funktsiyadir.
Bu fakt har qanday LP muammosidagi maqsad funktsiyasining tabiatidan kelib chiqadi. Quyidagi rasmlarda ikkita tipik turdagi izo-qiymatli maqsad funktsiyalari tasvirlangan.



Yuqoridagi ikkita faktni birlashtirgandan kelib chiqadiki, agar chiziqli dastur bo'sh bo'lmagan, chegaralangan amalga oshirilishi mumkin bo'lgan mintaqaga ega bo'lsa, u holda optimal yechim har doim burchak nuqtalaridan biridir.
Grafik usulning kamchiliklarini bartaraf etish uchun biz ushbu foydali va amaliy xulosadan ko'p o'lchovli LP muammolariga qo'llaniladigan algebraik usulni ishlab chiqishda foydalanamiz.
Chiziqli dasturlar uchun mumkin bo'lgan mintaqaning qavariqligi LP muammolarini hal qilishni osonlashtiradi. Maqsad funksiyasining shu xossasi va chiziqliligi tufayli yechim har doim cho'qqilardan biri hisoblanadi. Bundan tashqari, cho'qqilar soni cheklanganligi sababli, barcha mumkin bo'lgan cho'qqilarni topish kerak, so'ngra optimal nuqtani izlash uchun ushbu cho'qqilardagi maqsad funktsiyasini baholash kerak.
Chiziqli bo'lmagan dasturlar uchun muammoni hal qilish ancha qiyin, chunki yechim mumkin bo'lgan hududning istalgan joyida mumkin bo'lgan mintaqa chegarasida yoki cho'qqida bo'lishi mumkin.
Yaxshiyamki, biznesni optimallashtirish muammolarining aksariyati chiziqli cheklovlarga ega, shuning uchun LP juda mashhur. Bugungi kunda bozorda LP muammolarini hal qiladigan 400 dan ortiq kompyuter paketlari mavjud. Ularning ko'pchiligi cho'qqilarni qidirishga, ya'ni optimal nuqtani qidirishda bir cho'qqidan qo'shniga sakrashga asoslangan.
Siz allaqachon payqadingizki, tengsizliklar va/yoki tengliklar tizimining grafigi amalga oshirilishi mumkin bo'lgan mintaqa deb ataladi . Ushbu ikkita tasvir, grafik va algebraik bir-biriga ekvivalentdir, ya'ni cheklovlarni qondiradigan har qanday nuqtaning koordinatasi amalga oshirilishi mumkin bo'lgan mintaqada joylashgan va amalga oshiriladigan mintaqadagi istalgan nuqtaning koordinatasi barcha cheklovlarni qondiradi.