Ikkilangan simpleks usul

Ikkilangan simpleks usul Reja: Berilgan masalani standart formaga keltirish. Simpleks jadval tuzish. Bir tayanch yechimdan ikkinchi yechimga utish. Tayanch yechimni optimallikka tekshirish. Masalaning yechimini optimallik shartini bajarilishi. Masalaning yechimini yuklik shartini bajarilishi. Ikkilangan simpleks usul oddiy simpleks usulga nisbatan bazi kulayliklarga ega: Ikkilangan simpleks usul bo'yicha echilayotgan masala shartlaridagi ozod xadlar musbat bulmasligi xam mumkin; Ikkilangan simpleks usul bilan bir vaqtning uzida xam berilgan masalaning, hamda ikkilangan masalaning yechimi topiladi yoki ikkila masalaning yechimi mavjud emasligi aniklanadi; Berilgan masalaning chegaralovchi shartlari «» belgi bilan boglangan yoki uning bazi ozod xadlari manfiy bo'lgan masalalarni, ikkilangan simpleks usul bilan echganda bajariladigan hisoblash ishlarining soni kamayadi; Ikkilangan simpleks usul bilan ishlab chiqarishning bazi zarur tavsiflarini aniqlash mumkin. Masalan, bir vaqtning uzida xam ishlab chiqarish planini, xam ishlab chiqarishga sarf kilinadigan xamma vositalarning bahosini hisoblash mumkin. Oddiy simpleks usul singari ikkilangan simpleks usulning xar bir iteratsiyasida (kadamida) n- o'lchovli X vektor tayanch plan almashib boradi. Fakat, shunga etibor berish kerakki, simpleks usuldan farqli ravishda, ikkilangan simpleks usul bilan topilgan n-o'lchovli X vektor tayanch plan bulmasligi mumkin. Bunday planni chala tayanch plan deb ataymiz. Ikkilangan simpleks usul bo'yicha chala tayanch planlarni almashtirish jaraeni tayanch plan topilguncha takrorlanadi. Topilgan tayanch plan esa masalaning optimal plani bo'ladi. teorema. Agar chala tayanch plan masalaning tayanch plani bulsa, u optimal plan xam bo'ladi. teorema. Agar masalaning chala tayanch planining komponentalaridan kamida bittasi, masalan, bo'lib, barcha j lar uchun bulsa, berilgan masala tayanch planga ega bulmaydi. teorema Agar topilgan chala tayanch plan uchun bo'lganda, bo'lib, kamida bitta bulsa, u holda ni yangi chala tayanch plan ga almashtirish natijasida chiziqli funksiyaning qiymati kamayadi. vektorni ga almashtirish uchun bazisdan vektor chikarilib bazisga quyidagi shartlarni kanoatlantiruvchi vektor kiritiladi. , va Misol. quyidagi masala va unga ikkilangan masalaning yechimini ikkilangan simpleks usuli yordami bilan toping. Berilgan masalani kanonik formaga keltiramiz. (I) Bu masalani qo'shimcha o'zgaruvchilarga mos keluvchi vektorlarni bazis vektorlarga aylantirish uchun (I) masaladagi tenglamalarning xar birini (-1)ga kupaytiramiz. Natijada quyidagi masalaga ega bulamiz: (II) Bu masalaga ikkilangan masala quyidagi ko'rinishga ega bo'ladi: (II) masalada vektorlarni bazis vektorlar deb kabul qilib, simpleks jadvalni tuldiramiz. j=1,2,3,4,5,6,7 uchun bo'ladi. Demak, vektor (II) masalaning chala tayanch plani bo'ladi. Ikkilangan masalaning bu bazisdagi yechimi Chala tayanch plan X ning eng kichik manfiy elementiga mos keluvchi vektorni bazisdan chikaramiz va shartni kanoatlantiruvchi vektorni bazisga kiritamiz. - aniklovchi element bo'ladi. Yangi simpleks jadvalda barcha j lar uchun Berilgan masalaning yangi chala tayanch plani - (85, 285, -85) bo'ladi. Yangi bazisga ...