16-mavzu. Ikki o’zgaruvchili chiziqli dasturlash masalasini yechish

18-mavzu. Chiziqli dasturlash masalasini simpleks usulda yechish.

Chiziqli dasturlash masalasini yechishning universal usuli simleks usuldir. Bu usul amerikalik matematik G.Dansig tomonidan ishlab chiqilgan. Kanonik ko’rinishda berilgan (5)-(7) chiziqli dasturlash masalasining (6) chegaralari sistemasi matritsasi va kengaytirilgan matritsasining rangi ga teng bo’lsin. matritsaning biror bazis minorini olamiz. Aniqlik uchun bu minor dastlabki ta satr va ta ustundan iborat bo’lsin. Agar bo’lsa u holda (6) sistemaning nomerli tenglamalarini tashlab yuborish mumkin. Shuning uchun deb hisoblaymiz. (6) sistemani bazis o’zgaruvchilarga nisbatan yechamiz:

bu yerda – erkli o’zgaruvchilar ihtiyoriy qiymatlar qabul qila oladi. Ularni nolga teng desak (5) sistemaning quyidagi hususiy yechimini aniqlaymiz:

Bu yechimni boshqacha ko’rinishda yozish ham mumkiin:

(11) yechim (6) sistemaning bazis yechimi deb ataladi.
Bazis o’zgaruvchilarning har bir tanlanishiga (6) sistemaning bitta bazis yechimi mos keladi. Agar (11) yechimning har bir komponentesi nomanfiy bo’lsa, ya’ni bo’lsa, u holda (11) ni (5)-(7) chiziqli daturlash masalasining bazis rejasi yoki rejalar to’plamining burchak nuqtasi deb ataymiz. Agar sonlar orasida nolga teng bo’lganlari bor bo’lsa (11) ni aynigan burchak nuqta unga mos chiziqli dasturlash masalasini esa aynigan masala deb aytamiz.
Simpleks usul ushbu tasdiqqa asoslanadi: (5)-(7) chiziqli dasturlash masalasida maqsad funksiya rejalar to’plamining burchak nuqtalaridan birining ustida minimumga erishadi.
ta o’zgaruvchilar orasidan tanlangan ta bazis o’zgaruvchiga bitta bazis yechim mos kelishini yuqorida ta’kidlab o’tdik. Demak bazis yechimlar soni dan ortmaydi. Chiziqli dasturlash masalasini yechish uchun maqsad funksiyaning buchak nuqtalaridagi qiymatlarini hisoblash va taqqoslash yetarli. Lekin, o’zgaruvchilar soni kattalashganda bunday urinish qiyinlashadi. Simpleks usulda maqsad funksiyaning kamayishi tomon burchak nuqtalar almashtirib boriladi.