Mavzu: Chiziqli dasturlash masalalari uchun tayanch yechim tushunchasi, ularni aniqlash usullari Toshkent-2023 Chiziqli dasturlash masalalari uchun tayanch yechim tushunchasi, ularni aniqlash usullari

Chiziqli dasturlash masalasini analitik yechish usuli (simpleks usul)
D astlab berilgan chiziqli programmalashtirish masalasining chegaraviy shartlarida m ta o`zaro chiziqli bog`liq bo`lmagan birlik vektorlar mavjud deb faraz qilamiz. Umumiylikni buzmagan holda bu vektorlar birinchi m ta vektorlardan iborat deylik. U holda masala quyidagi ko`rinishda bo`ladi:
(1)

(2)
(3)

(1) sistemani vektor ko’rinishda yozamiz:
( 4)
v ektorlar n o`lchovli vektor fazodagi o`zaro chiziqli bog`liq bo`lmagan birlik vektorlardan iborat bo`lib, bu fazoning bazisini tashkil qiladi. (1) da
o `zgaruvchilarni bazis o`zgaruvchilar, o`zgaruvchilarni esa bazis bo`lmagan (ozod) o`zgaruvchilar deb qabul qilib, bazis bo`lmagan o`zgaruvchilarni nolga tenglaymiz.
N atijada: (5)
boshlang`ich yechimni hosil kilamiz. (5) yechimga quyidagi
( 6)
y oyilma mos keladi. Bu yoyilmadagi vektorlar o`zaro chiziqli bog`liq bo`lmagan vektorlar bo`lganligi sababli, topilgan boshlang`ich (5) yechim tayanch yechim bo`ladi.
Endi boshlang`ich yechimdan foydalanib, yangi tayanch yechimni topish mumkinligini ko`rsatamiz. vektorlar n o`lchovli vektor
f azoning bazisini tashkil qilgani uchun vektorlarning ixtiyoriysini Pj bazis vektorlar orqali faqat bir xil yoyilmasini topish mumkin, ya’ni: uchun (7)
Faraz qilaylik, bazisga kirmagan birorta vektor, masalan ning yoyilmasidagi koeffitsientlardan kamida bittasi (masalan, ) noldan farqli bo`lsin: (8)
Ixtiyoriy ni olib, (8) tenglikning ikki tomonini unga ko`paytirib, hosil bo`lgan natijani (6) dan ayiramiz. Natijada quyidagi tenglikka ega bo`lamiz:
( 9)
A gar sonlarning har biri nomanfiy
b o`lsa, vektor yechim
b o`ladi. X dan farq qiluvchi X` yechim qidirilayotgani uchun ning faqat musbat qiymatlari qaraladi. Shuning uchun
bo`lgan komponentalarni ko`ramiz. Demak, shunday topishimiz kerakki, hamma i lar uchun ,
b o`lganda tengsizlik bajarilsin.
B unlardan, tengsizlik hosil bo` ladi.
X ` yechim tengsizlik qanoatlantiriladigan
u chun yechimdir. Lekin tayanch yechim o`z ichiga m+1 ta komponentlarni olmaydi, shuning uchun X` yechimdagi kamida bitta komponentani nolga aylantirish kerak. Faraz qilaylik, bajarilsin.
B u holda X` yechimning k komponentasi
b o`ladi. qiymatini (9) ga qo`yib quyidagi yoyilmani hosil qilamiz:

yechim mos keladi. Demak, yangi yechimning komponentalari

q uyidagicha aniqlanar ekan:
(10)
B undan keyingi tayanch yechimni hosil qilish uchun bazisga irmagan ixtiyoriy vektorning bazis vektorlar orqali yoyilmasini aniqlash hamda shunday sonni topish kerakki, uning yordamida yangi vektor bazisga kirsin va eski bazis vektorlardan birortasi bazisdan chiqsin. Shunday qilib, yangi tayanch yechimlarni hosil qilish jarayoni bazisga kiritiladigan va bazisdan chiqariladigan vektorni tanlashdan iboratdir. Bazisga kiritiladigan vektorni tanlash kriteriysi simpleks usulning asosiy elementlaridan biri hisoblanadi. Agar bazisga kiritilayotgan vektorning yoyilmasida barcha bo`lsa, (9) yoyilmadagi birorta vektorni bazisdan chiqaruvchi ni topib bo`lmaydi. Bu holda X` yechim m+1 musbat komponentalarni o`z ichiga oladi.

vektorlar sistemasi esa o`zaro chiziqli bog`liq bo`lib, qavariq ko`pburchakning chetki nuqtasini emas, balki ichki nuqtasini ifodalaydi. Bu nuqtada esa chiziqli funksiya o`zining minimum qiymatiga erisholmaydi. Bu holda chiziqli funksiya quyidan chegaralanmagan bo`ladi.

Xulosa
Chiziqli dasturlash masalalari tushunchasi, kompyuterlar yordamida matematik formulalarni, algoritmlarni va jarayonlarni yechish orqali aniqlangan ko`plab muammolardan iboratdir. Bu muammolarning bir qismi ko`p xil algoritmlarni va jarayonlarni samarali bajarishni talab qiladi. Bunday muammolarni yechish uchun tayanch yechim tushunchasi, bu muammolarni o`z ichiga oluvchi matematik tushunchalarni va modellarni yaratishga yordam beradi. Bu modellar kompyuter dasturlariga o`tkaziladi va ular arqali muammolarni yechish yoki ularga yaqin yechimlarni topish mumkin.
Muammo va vaziyatlarni aniqlash usullari, masalan, chiziqli dasturlashda mashinali o`quv usullari, dasturlarning nazorati, yomonliklar aniqlash, asosiy modellar yaratish, hisoblash va yechish jarayonlari, tahlil va tasniflash, matematikaviy optimizatsiya va boshqa ko`plab usullar bo`lishi mumkin.
Shuningdek, muammolarni yechish uchun bajariladigan chiziqli dasturlash algoritmlari va jarayonlari ham mavjud. Bunday algoritmlar, qo`shimcha ma’lumot olish, taqqoslash, klasifikatsiya, aniqlash, tahlil, tasniflash va optimizatsiya kabi vazifalarni bajarish uchun yordam beradi. Chiziqli dasturlash muammolari keng ko`p sohada, masalan, texnologiyalarda, moliya sohasida, tibbiyotda, transportda, oziq-ovqat sanoatida, ish joyida va boshqa ko`plab sohalarda yuzaga keladi. Shu sababli, chiziqli dasturlash masalalari va ularni yechish usullari, texnologiya sohasida muhim ahamiyatga ega.