Ii-bob. Chiziqli programmalashtirish masalasining simpleks algoritmi

II-BOB. CHIZIQLI PROGRAMMALASHTIRISH MASALASINING SIMPLEKS ALGORITMI

2.1. Chiziqli tenglamalar sistemasining nomanfiy

yechimlarini topish

n o‘zgaruvchili m ta chiziqli tenglama ushbu ko‘rinishga ega

yoki qisqacha

(2.1.1) sistemada , matritsaning rangi va . (2.1.1) sistemaning m ta o‘zgaruvchilari oldidagi koeffitsiyentlardan tuzilgan matritsa determinanti noldan farqli bo‘lsa, u holda m ta o‘zgaruvchi bazis o‘zgaruvchi, qolgan tasi bazis bo‘lmagan yoki erkli o‘zgaruvchi deyiladi.

Bazis o‘zgaruvchilar guruhining mumkin bo‘lgan maksimal soni bo‘ladi, ya’ni dan katta bo‘lolmaydi.
Aytaylik, masala bazis o‘zgaruvchilar bo‘lsin, ya’ni

ChP masalasini yechishda o‘zgaruvchilarning va maqsad funksiya o‘zgaruvchilarning nomanfiy bo‘lishi amaliy ahamiyatga ega shuning uchun (2.1.1) chiziqli tenglamalar sistemasining nomanfiy yechimlarini topish zarur bo‘ladi.

Aytaylik, (2.1.1) chiziqli tenglamalar sistemasida barcha ozod hadlar nomanfiy sonlardan iborat bo‘lsin, aks holda -1 ga tenglamaning har ikki qismini ko‘paytirib musbat holga keltiramiz.
Dastlabki jadvalni yozamiz.

Bazis o‘zgaruchilar		Ozod hadlar
			(2.2.2)

Masalani yechish hal qiluvchi elementni tanlashdan boshlanadi. Buni quyidagicha amalga oshiramiz.

1. 
   Hal qiluvchi ustunni shunday tanlaymizki, unda hech bo‘lmaganda bitta musbat element bo‘lsin.
   
2. 
   Aytaylik, hal qiluvchi ustunda bir nechta musbat elementlar bor bo‘lsin. Bunday holda ularga mos ozod hadlarni shu elementlarga nisbatini olamiz va ularning eng kichigini hal qiluvchi element qilib tanlaymiz. (agar ustunda faqat bitta musbat element bo‘lsa, shu sonli hal qiluvchi element sifatida qabul qilamiz). Bunday almashtirish simpleks almashtirish deyiladi.