O’zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti kafedra

Chiziqli dasturlash masalalarini simpleks jadvallar usulida yechish.
Simpleks usuli yordamida chiziqli dasturlashning ko’pgina masalalarini yechish mumkin. Bu usul yordamida chekli qadamlarda optimal yechimlarni topish mumkin. Har bir qadamda shunday mumkin bo’lgan yechimlarni topish kerakki, maqsad funksiyasining qiymati oldingi qadamdagi qiymatidan (miqdoridan) katta (kichik) bo’lsin. Bu jarayon maqsad funksiyasi optimal (maksimum yoki minimum) yechimga ega bo’lguncha davom ettiriladi.
Quyidagi chiziqli dasturlash masalasi berilgan bo’lsin:



Berilgan masalani simpleks usuli yordamida yechish g’oyasini berish uchun berilgan masalani quyidagicha kanonik formada yozib olamiz:


(1)
Ushbu masalani vektor ko’rinishida qayta yozib olamiz
(2)
shartlar bajarilganda

funksiyaning maksimumi topilsin, bu yerda P₁, P₂, …, P_n va P₀ lar m-o’lchovli ustun-vektorlar bo’lib, ular berilgan masaladagi noma’lum va ozod hadlardan tuzilgan:

Ta’rif. reja tayanch reja deb ataladi, agarda barcha o’zgaruvchilarning koeffitsiyentlari chiziqli bog’liqsiz P_j vektorlarda musbat sonlardan iborat bo’lsa.
Teorema. Agar nuqta ko’pyoqli yechimning uchi bo’lsa, u holda (2) yoyilmadagi har bir x_j ( ) larga mos P_j vektorlar o’zaro chiziqli bog’liqsiz bo’ladi.
Bu yerda:
Bazis vektorlar: P_n+1, P_n+2, …, P_n+m
Tayanch reja:
Tayanch reja uchun (1) shartlardagi noma’lumlar o’rniga nol qiymat qo’yib bazis o’zgaruvchi lar topiladi.
Berilgan ma’lumotlar asosida simpleks jadvalini tuzamiz: