Simpleks jadval. Chiziqli programmalashtirish masalasining optimal yechimini simpleks usuli yordamida topish

x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0, x₄ ≥ 0, y₁ ≥ 0, y₂ ≥ 0, y₃ ≥ 0, y₄ ≥ 0. (2*)

Z_mak= 520x₁ +480x₂ + 300x₃ +190x₄+0y₁ + 0y₂ + 0y₃ +0y₄ (3*)

 Qo’shimcha noma’lumlarning iqtisodiy mazmuni

y₁ - 450 s konsentrat ozuqalarning sarf bo’lmagan qismi, s; y₂ - 560 s shirali ozuqalarning sarf bo’lmagan qismi, s; y₃ - 300 s dag’al ozuqalarning sarf bo’lmagan qismi, s; y₄ - 200 s pichanning sarf bo’lmagan qismi.

Boshlang’ich tayanch rejani topish

Buning uchun (1*) tenglamalar sistemasi qo’shimcha noma’lumlarga nisbatan yechib olinadi. Agar asosiy noma’lumlar nolga tenglashtirilib olinganda, qo’shimcha noma’lumlar musbat yoki nolga teng bo’lsa ChDM boshlang’ich tayanch yechimga ega deyiladi.

y₁ = 450 - (12x₁ + 12x₂ + 7x₃ + 3x₄),

y₂ = 560 - (15x₁ + 14x₂ + 8x₃ + 4x₄), (1**)

y₃ = 300 - (8x₁ + 6x₂ + 5x₃ + 3x₄),

y₄ = 200 - (5x₁ + 4x₂ + 3x₃ + 2x₄),

Z_mak= 0- (-520x₁ - 480x₂ - 300x₃ -190x₄) - 0y₁ +0y₂ + 0y₃ +0y₄ (3**)

Asosiy noma’lumlarni nolga tenglashtirsak, x₁ = x₂ = x₃ = x₄ = 0 da qo’shimcha noma’lumlarning qiymatlari quyidagiga teng bo’ladi:

y₁ = 450, y₂ = 560, y₃ = 300, y₄ = 200.

Demak, y₁ ≥ 0, y₂ ≥ 0, y₃ ≥ 0 va y₄ ≥ 0 shart bajariladi. Masala boshlang’ich tayanch reja (yechim)ga ega.

Boshlang’ich simpleks jadvalini tuzish

«Bazis yechim» ustuniga qo’shimcha noma’lumlar kiritiladi. Bazis noma’lumlar foydalanilmagan (yem-xashak) resurslarining [B_j] ozod hadlar ustunida keltirilgan miqdordagi hajmini ifodalaydi.

[S_j] ustun maqsad funksiyasining bahosi deb nomlanadi. Bu ustunga maqsad funksiyasidagi qo’shimcha noma’lumlarning koeffisiyentlari kiritiladi;

[B_j] ustunga ozod hadlar (resurs)larning qiymatlari kiritiladi;

«Asosiy noma’lumlar» nomli ustunlarning elementlari tenglamalar sistemasidagi asosiy noma’lumlarning koeffisiyentlaridan tashkil topgan matrisa bo’ladi. «Qo’shimcha noma’lumlar» ustunlari esa qo’shimcha noma’lumlarning koeffisiyentlaridan tashkil topgan birlik matrisadan iborat bo’ladi.

Z_j -C_j satr indeks qator deyiladi va unga maqsad funksiyasi noma’lumlarining koeffisiyentlari yoziladi. Bu qator qaysi yo’nalishda rejani yaxshilash mumkinligini va qachon optimal yechimga ega bo’lish yo’llarini ko’rsatadi.

Maqsad funksiyaning qoeffisiyentlari indeks qatoriga qarama – qarshi ishora bilan yoziladi.

ChDMni optimalligini tekshirish. Masala maksimumga yechilayotgan bo’lsa indeks qatordagi manfiy ishorali sonlarning bo’lishi, rejani yaxshilash imkoniyati borligini ko’rsatadi. Agar indeks qatordagi barcha sonlar musbat yoki nol bo’lsa, topilgan qiymatlar optimal yechim bo’ladi.

Masala minimumga yechilsa aksincha bo’ladi. Ya’ni, indeks qatordagi musbat ishorali sonlar rejani yaxshilash mumkinligini anglatadi. Shuningdek, indeks qatordagi barcha sonlar manfiy yoki nol bo’lsa, topilgan qiymatlar optimal yechimni ifodalaydi.

Boshlang’ich simpleks jadvalni tuzamiz.

Boshlang’ich simpleks jadvali