Eslatma. Agar (5)-(7) chiziqli dasturlash masalasi aynigan bo’lsa, u holda burchak nuqtani simpleks usulda almashtirish natijasida maqsad funksiya kamaymasligi mumkin. Bunday almashtirish qadamini bo’sh qadam deb ataymiz. Bo’sh qadamlar sikl tashkil etishi ham etmasligi ham mumkin. Amaliyotda cheksiz siklli bo’sh qadam deyarli uchramaydi.
19-Mavzu. Sun’iy bazislar usulida chiziqli dasturlash masalasining burchak nuqtasini aniqlash Bizga kanonik ko’rinishdagi quyidagi chiziqli dasturlash masalasi berilgan bo’lsin:
Aytaylik (2) sistemaning asosiy matritsasi va kengaytirilgan matrisasining rangi ga teng bo’lsin, ya’ni
matritsalar uchun tenglik bajarilsin. Algebra kursidagi Kroneker-Kepelli teoremasiga ko’ra bu holda (2) Sistema birgalikda (yechimga ega) bo’ladi. Agar bo’lsa, u holda (2) sistemaning ta tenglamasini ta tenglamasidan hosil qilish mumkin bo’ladi va demak o’sha ta tenglamani tashlab yuborsak (2) sistemaga teng kuchli tengalamalar sistemasi paydo bo’ladi. Shu sababdan deb xisoblaymiz. Demak matritsaning qaysidir ta ustunidan tuzilgan minor noldan farqli bo’ladi. Aniqlik uchun dastlabki ta ustunidan tuzilgan minor noldan farqli deb olaylik. (2) sistemada desak
determinant noldan farqli sistema xosil bo’ladi. Agar bu sistema yechimga ega bo’lsa, u holda (2) sistema yechimga ega bo’ladi. Agar vektorning barcha komponentalari nomanfiy bo’lsa, u (1)-(3) chiziqli dasturlash masalasining burchak nuqtasi deb ataladi.
(1)-(3) chiziqli dasturlash masalasining burchak nuqtasini topishning sun’iy bazislar usulini ko’rib chiqaylik. (2) sistemada ozod koeffitsientlar nomanfiy bo’lsin. Agar sistemaning biror tenglamasida ozod koeffitsient manfiy bo’lsa, shu tenglamani ga ko’paytirib kerakli holatga o’tib olamiz. Quyidagi chiziqli dasturlash masalasini qaraymiz:
Bu yerda yordamchi funksiya, o’zgaruvchilar sun’iy o’zgaruvchilar deb ataladi. Ravshanki (4)-(6) chiziqli dasturlash masalasi burchak nuqtaga ega. (5) sistemani o’zgaruvchilarga nisbatan yechamiz:
Topilganlarni (4) funksiyaga qo’yamiz:
(8) funksiyada barcha o’zgaruvchilar oldidagi koeffitsientlar musbat bo’lsa, u holda (1)-(3) chiziqli dasturlash masalasi burchak nuqtaga ega bo’lmaydi va demak yechimga ham ega bo’lmaydi. (8) funksiyada o’zgaruvchi oldidagi koeffitsient manfiy bo’lsin, ya’ni . (7) sistemada o’zgaruvchi ustunini qaraymiz:
Agar bu ustunning faqat bitta komponentasi manfiy bo’lsa, u holda koeffitsient hal qiluvchi element deb ataladi. Agar (9) ustundagi bir nechta komponentalar manfiy bo’lsa, u holda bu komponentalar uchun nisbatlar tuzamiz va eng kichigiga mos koeffitsientni hal qiluvchi element deb ataymiz. Agar (9) ustunning marcha koeffitsientlari nomanfiy bo’lsa, u holda (1)-(3) chiziqli dasturlash masalasi burchak nuqtaga ega bo’lmaydi va demak yechimga ham ega bo’lmaydi. hal qiluvchi element bo’lsin. (7) sistemaning tenglamasida deb o’zgaruvchini chapga o’tkazamiz. ning aniqlangan ifodasini (7) sistemaning qolgan tenglamalariga va (8) funksiyaga qo’yamiz:
(10) funksiyada barcha o’zgaruvchilar oldidagi koeffitsientlar musbat bo’lsa, u holda (1)-(3) chiziqli dasturlash masalasi burchak nuqtaga ega bo’lmaydi va demak yechimga ham ega bo’lmaydi. (10) funksiyada o’zgaruvchi oldidagi koeffitsient manfiy bo’lsin, ya’ni . (11) sistemada o’zgaruvchi ustunini qaraymiz:
Agar bu ustunning faqat bitta komponentasi manfiy bo’lsa, u holda koeffitsient hal qiluvchi element deb ataladi. Agar (12) ustundagi bir nechta komponentalar manfiy bo’lsa, u holda bu komponentalar uchun nisbatlar tuzamiz va eng kichigiga mos koeffitsientni hal qiluvchi element deb ataymiz. Agar (12) ustunning marcha koeffitsientlari nomanfiy bo’lsa, u holda (1)-(3) chiziqli dasturlash masalasi burchak nuqtaga ega bo’lmaydi va demak yechimga ham ega bo’lmaydi. hal qiluvchi element bo’lsin. Agar (11) sistemaning tenglamasida sun’iy o’zgaruvchi turgan bo’lsa uni nolga tenglab o’zgaruvchini chapga o’tkazamiz. Agar (11) sistemaning tenglamasida o’zgaruvchilar biri turgan bo’lsa uni o’nga o’zgaruvchini esa chapga o’tkazamiz. ning aniqlangan ifodasini (11) sistemaning qolgan tenglamalariga va (10) funksiyaga qo’yamiz. Bu jarayon toki barcha suniy o’zgaruvchilar nolga aylangunga qadar davom etadi. Natijada o’zgaruvchilardan tasi qolgan tasi orqali ifodalanadi va funksiya nolga aylanadi.
Shunday qilib (1)-(3) chiziqli dasturlash masalasining
