Xos chiziqli programmalash masalalari

Xos chiziqli programmalash masalalari va ularni to'g'rilash usullari Reja: Xos chiziqli programmalash masalasi. Xos plan. Xos planni to'g'rilash usuli. Agar bazis vektorlarga mos keluvchi birorta 0 ga teng bulsa, yani (1) yoyilmadagi lardan kamida bittasi nolga teng bulsa, chiziqli programmalash masalasi xos chiziqli programmalash masalasi deyiladi va bazis vektorlarga mos keluvchi tayanch plan - xos plan bo'ladi. yuqorida, simpleks usulini asoslash jarayonida chiziqli programmalash masalalarini xosmas deb faraz kilgan edik. Bu farazga ko'ra simpleks usulning xar bir iteratsiyasidan sung chiziqli funksiyaning qiymati kamaya borishini va chekli sondagi iteratsiyadan sung u uzining optimal qiymatiga erishishi mumkinligini kursatgan edik. Agar masalaning tayanch plani xos plan bulsa, bo'lishi mumkin. U holda bir tayanch plandan ikkinchisiga utganda, chiziqli funksiyaning qiymati uzgarmaydi. Bazan bunday masalalarni yechish jarayonida sikllanish holati, yani malum sondagi iteratsiyadan sung oldingi iteratsiyalardan birortasiga kaytish holati ruy berishi mumkin. sikllanish holati ruy bergan masalalarda optimal plan xech kachon topilmaydi. sikllanish holati, odatda, tayanch plandagi birdan ortik bo'lgan xollarda ruy berishi mumkin. Birdan ortik vektorlar uchun bo'lganda bazisdan chikariladigan vektorni to'g'ri aniqlash sikllanish holatini oldini olishda katta ahamiyatga egadir. Bundan kurinadiki, xos masalalarni yechishga moslashtirilgan usullar masalaning optimal yechimini topishga ishonch bildirib, bazisdan chikariladigan vektorni tanlashning yagona yo'lini ko'rsatishi kerak. Xos chiziqli programmalash masalasining geometrik tasvirini 1-shakldan ko'rish mumkin. Bunda vektor vektorlardan tuziladigan kavarik konusning sirtida yotibdi. R1 R3 R0 R2 1 - shakl Shuning uchun ni vektorlarning kavarik kombinatsiyasi sifatida ifodalab bulmaydi, lekin uni vektorlarning kavarik kombinatsiyasi orqali ifodalash mumkin. ni vektorlarning kavarik kombinatsiyasi orqali ifodalash uchun yoyilmadagi vektorning koeffitsiyenti bo'lishi kerak. Agar vektorni siljitib vektorlardan tashkil topgan kavarik konusning ichiga kiritsak, u holda uni vektorlarning kavarik kombinatsiyasi orqali ifodalash mumkin bo'ladi. vektorni kavarik konusning ichiga siljitish uchun ixtiyoriy kichik son olib, vektorlarning kombinatsiyasini tuzamiz va uni masalaning (2) chegaralovchi shartlarining ung tomoniga kushib yozamiz: (3) hosil bo'lgan vektor vektorlardan tashkil topgan kavarik konusning ichida yotgan (1-shakl). Demak, ni vektorlarning kavarik kombinatsiyasi orqali ifodalash mumkin. Xuddi shuningdek, umumiy holda berilgan masalaning (4) chegaralovchi shartlarini kuyidagicha yozamiz: (5) Faraz kilaylik, bazis vektorlar bo'lib, ular V matritsani tashkil kilsin. U holda (6) berilgan masalaning yechimi va (7) uzgartirilgan (5) chegaralovchi shartli masalaning yechimi bo'ladi. (8) tenglik urinli bo'lganligi uchun (7) ni kuyidagicha ifodalaymiz: (9) Demak, kuyidagicha aniklanadi. , (10) (11) ni shunday kichik son deb kabul qilish mumkinki, tengsizlik barcha lar uchun urinli bo'ladi. Bazisdan chikariladigan vektorni aniqlash uchun (12) qiymatni barcha lar uchun hisoblaymiz. (11) ga asosan nisbat da minimumga erishadi, chunki ni ...