Simpleks usuli

Simpleks usuli Simpleks usuli degan nom shu usulning muallifi Amerikalik olim Dj. Dantsig tomonidan kiritilgan bo'lib, simpleks so'zining manosi sodda, oddiy deganidir. Bu usulning umumiy g'oyasi quyidagicha: Bizdan biror chiziqli programmalashtirish masalasining eng qulay (optimal) yechimini topish talab qilinsin. Buning uchun qo'yilgan masalaning dastlab biror boshlang'ich yechimi yoki biror eng sodda yechimi olinadi. So'ngra bu yechim orqali elementar chiziqli almashtirishlar natijasida qo'yilgan masalaning yangi yechimini hosil qilamiz va yana elementar chiziqli almashtirishlar yordamida shu jarayonni chiziqli funksiyaning eng qulay yechimini topguncha yoki eng qulay yechimining mavjud emasligini ko'rsatguncha davom ettiriladi. Lekin bu usul bilan chiziqli dasturlash masalalarining eng qulay (eng kichik yoki eng katta qiymatlarini) yechimlarini topish oddiy matematik xususiyatlariga ega bo'lgani bilan bajarilish jarayonida asosiy qiyinchiligi shundaki, har bir bosqichda yangi bazisga nisbatan maqsad funksiya va cheklanish shartlarini qaytadan yozib borishdan iboratdir. Bu juda ko'p bosqichlardan iborat bo'lgan matematik hisoblashlarni quyidagi simpleks jadvali deb ataluvchi jadval yordamida ancha kamaytirish mumkin. Simpleks jadvallar usuli. Faraz qilaylik (1) maqsad funksiyaning x1, x2, , xn lar (2) cheklanish tenglamalar sistemasini qanoatlantiradigan qiymatlarida eng katta qiymatini topish talab qilinsin. (2) sistema x1, x2, ,xm nomalumlarga nisbatan echilgan bo'lsin: (3) (3) ni (1) ga qo'yib maqsad funksiyani va (3) sistemani quyidagi ko'rinishlarda yozib olaylik: yoki (4) (5) dagi x1, x2, x3, , xm lar bazislar yoki bazis nomalumlar bo'lib, xm+1,xj,,xn lar esa ozod nomalumlardir. xm+1,xj,,xn lar esa ozod nomalumlar bo'lgani uchun, xm+1=0, xm+2=0,…, xn=0 desak, x1=, bo'lib, birinchi bazis yechim bo'ladi. (4) va (5) larga asosan birinchi simpleks jadvalini tuzamiz. 1-jadval. 1-jadvalning x1 dan boshlanadigan yo'lida (5) sistemadagi birinchi tenglamaning ozod hadi va nomalumlar oldidagi koeffitsiyentlar, x2 dan boshlanadigan yo'lida esa ikkinchi tenglamaning oldidagi koeffitsiyentlar va ozod had joylashgan va xokazo. f dan boshlanuvchi yo'lida esa (4) tenglikdagi ozod had va nomalumlar oldidagi koeffitsiyentlar joylashtirilgan. 1-simpleks jadvalidan foydalanib, 2- simpleks jadvali quyidagicha tuziladi. f turgan yo'l elementlari orasida manfiylari bo'lsa, shularning eng kichigi joylashgan, yani masalan joylashgan ustun olinadi va bu ustunni hal qiluvchi ustun deyiladi. Endi ozod hadlar bilan ularga mos kelgan hal qiluvchi ustun elementlar nisbatlari tuziladi. Bu nisbatlarning eng kichigi masalan bo'lsin, bu holda ga hal qiluvchi element deyiladi, turgan yo'lga esa hal qiluvchi yo'l deyiladi. Hal qiluvchi element 1-dan farqli bo'lsa, uni 1-ga aylantirib olish mumkin. Buning uchun shu hal qiluvchi element turgan yo'lining hamma elementlarini ga bo'lish kifoya. So'ngra hal qiluvchi ustun elementlarini hal qiluvchi elementdan tashqari hammasini nolga aylantiramiz. Buning uchun -yo'lini - ga ko'paytirib, mos ...