Reja: kirish. Nazariy qism

Amaliy qism

1.Chiziqli dasturlash masalalarini simpleks usulida yechish

Chiziqli dasturlash masalalarini simpleks usulida yechish bilan quyidagi masalani hal qilish davomida batafsil tanishib chiqamiz.
Bizga quyidagi ko`rinishdagi cheklanishlar va maqsad funksiyasi berilgan bo`lsin:

Cheklanishlar: (4.5)

Maqsad funksiyasi:
Berilgan sistemadagi har bir tengsizlikka bittadan bazis o`zgaruvchilarni kiritib, bu tengsizliklarni tenglama ko`rinishida yozib olamiz va shu orqali chiziqli dasturlashning kanonik masalasi ko`rinishiga ega bo`lamiz:


Hosil qilingan tenglamalar sistemasini vektor shaklida yozamiz:

Bu yerda

Bazis vektorlar: Таянч режа: X* = (0, 0, 8, 5, 28)

Ushbu ma‟lumotlar asosida simpleks jadvalini tuzib, va larning qiymatlarini hisoblaymiz hamda dastlabki X* tayanch rejani optimallikka tekshiramiz.

1-qadam. Jadvalga boshlang`ich ma‟lumotlarni kiritish

Iteratsiya 1 1-jadval

2-qadam. Dastlabki X* tayanch rejani optimallikka tekshirish

Iteratsiya 1 2-jadval

Tayanch reja optimal emasligi muqarrar, chunki 4-satrda manfiy elementlar bor, shartga ko`ra ular barchasi nomanfiy bo`lishi kerak. Demak, yangi tayanch rejani qidiramiz. Buning uchun avval mazkur jadvaldagi yo`naltiruvchi ustun va yo`naltiruvchi satrni topamiz.
Yo`naltiruvchi ustunni topish uchun 2-jadvalning 4 satrida joylashgan qiymatlarning modulini olamiz, moduli eng katta bo`lgan qiymatni tanlaymiz va shu son joylashgan yacheyka (katak) ni belgilaymiz, yacheyka joylashgan ustun yo`naltiruvchi ustun hisoblanadi. Bizning misolimizda, bo`ladi va
yo`naltiruvchi ustun P<sub>2</sub> joylashgan 6-ustun bo`ladi.
Yo`naltiruvchi satrni topish uchun 2-jadvaldagi 4-ustunda joylashgan P<sub>0</sub> ning qiymatlarini mos ravishda yo`naltiruvchi ustun P₂ da joylashgan qiymatlarga bo`lamiz, ular orasidan eng kichik bo`linmani tanlaymiz va shu bo`linma joylashgan satr yo`naltiruvchi satr hisoblanadi. Bizning msolimizda
P₀:P₂ mos ravishda 8:1=8, 5:1=5, 28:7=4. Demak, P₅ joylashgan 3-satr yo`naltiruvchi satr hisoblanadi.

3-qadam. Yo`naltiruvchi ustun hamda satrni aniqlash

Iteratsiya 1 3-jadval

3-jadvalda yo`naltiruvchi ustun va satr ko`rsatilgan.

4-qadam. Yangi iteratsiyaga o`tish

Bu qadamda ish jadvaldagi yo`naltiruvchi satrni to`ldirishdan boshlanadi. Buning uchun yo`naltiruvchi ustun va satrning kesishish yacheykasida joylashgan element ( 7 ) ga satr elementlari mos ravishda bo`lib yoziladi. 3-satrda joylashgan P₅ ning o`rniga P<sub>2</sub> ni yozamiz. 6-ustunda joylashgan yo`naltiruvchi ustundagi P₂ ni qiymatlarining o`rniga 9-ustunda joylashgan P<sub>5</sub> ning qiymatlari mos ravishda qo`yiladi.