Chiziqli dasturlash masalalari uchun tayanch yechim tushunchasi, ularning aniqlash usullari


Chiziqli dasturlash masalasini kanonik shaklga keltirish


Download 0.86 Mb.
bet4/7
Sana17.06.2023
Hajmi0.86 Mb.
#1552789
1   2   3   4   5   6   7
Bog'liq
Algoritm1

Chiziqli dasturlash masalasini kanonik shaklga keltirish Ixtiyoriy ko‘rinishda yozilgan chiziqli dasturlash masalasini, sodda matematikalmashtirishlar yordamida, unga ekvivalent bo’lgan boshqa ixtiyoriy ko‘rinishdagi chiziqli dasturlash masalasiga keltirish mumkin. Buning uchun, umumiy holda berilgan

chiziqli dasturlash masalasi ustida quyidagi teng kuchli almashtirishlarni bajarish mumkin.



  1. Tengsizlikning ishorasini qarama-qarshisiga almashtirish. “<” ko’rinishdagi tengsizlikning ikkala tomoni ishorasini qarama-qarshisiga almashtirib, “>” ko’rinishdagi tengsizlikka va, aksincha, “>”ni “<”ga keltirish mumkin.

  2. max Y ni min Y ga aylantirish. Har qanday chiziqli dasturlash masalasini kanonik ko‘rinishga keltirish uchun tengsizliklar sistemasini tenglamalar sistemasiga va max Y ni min Y ga aylantirish kerak. max Y ni min Y ga keltirish uchun, max Y ni qarama-qarshi ishora bilan olish, ya’ni max Y min Y yoki aksincha max Y min Y ko‘rinishda olish yetarlidir.
  3. Tengsizliklarni tenglamaga (kanonik shaklga) aylantirish. n noma’lumli


chiziqli tengsizlikni qaraymiz. Bu tengsizlikni tenglamaga aylantirish uchun uning kichik tomoniga nomanfiy o‘zgaruvchini, ya’ni xn 1 0 ni qo‘shamiz.


Natijada n 1 noma’lumli chiziqli tenglamaga ega bo’lamiz:

tengsizlikni tenlamaga aylantirish uchun qo’shilgan xn+1 o’zgaruvchi qo‘shimcha o‘zgaruvchi deb ataladi.



  1. O‘zgaruvchilar uchun to‘g‘ri shart qo‘yish. Agar biror o‘zgaruvchiga To‘g‘ri shart qo‘yilmagan, ya’ni xi , i 1, n o‘zgaruvchi uchun ishorasiga hech qanday cheklash qo‘yilmagan bo‘lsa, u holda bu o‘zgaruvchini ikkita manfiymas o‘zgaruvchilar ayirmasi shaklida ifodalash mumkin, ya’ni x (j1) 0, x (j2) 0

o‘zgaruvchilar bilan x j =x (j1) -x (j2) tenglik yordamida almashtiriladi
1-teorema. Berilgan tengsizlikning har bir X (1 , 2 ,, n ) yechimiga tenglamaning faqat bitta

yechimi mos keladi va aksincha, tenglamaning har bir Y0 yechimiga tengsizlikning faqat bitta X0 yechimi mos keladi.



Download 0.86 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling