Mavzu: Butun sonli chiziqli programmalash modellari

Mavzu: Butun sonli chiziqli programmalash modellari
Eng oddiylari chiziqli deterministik modellardir. Ular nazorat o'zgaruvchilarning chiziqli shakli shaklida o'rnatiladi ( NS):
W = a 0 + a 1 x 1 + … + a k x k
shaklning chiziqli cheklovlari ostida
b 1 j x 1 + b 2 j x 2 + … + b kj x k ³ b j , j = 1,…, q 1 ;
c 1 j x 1 + c 2 j x 2 + … + c kj x k = c j , j = 1,…, q 2 ;
d 1 j x 1 + d 2 j x 2 + … + d kj x k £ d j , j = 1,…, q 3 .
Cheklovlarning umumiy soni m = q 1 + q 2 + q 3 o'zgaruvchilar sonidan oshib ketishi mumkin (m> k). Bundan tashqari, odatda o'zgaruvchilarning ijobiyligi sharti kiritiladi ( x i ³ 0).
Chiziqli model uchun javob yuzasi giperplan... Masalan, quyidagi shakldagi ikkita o'zgaruvchining chiziqli modelini ko'rib chiqing:
W =–2x 1 –3x 2 (2.2)
quyidagi cheklovlar ostida

(2.3)

2x 1 + 3x£ 2 18;
x 1 – 4x 2 £ 4;
–2x 1 + x£ 2;
NS 1 ³ 0; x 2 ³ 0.
Yaroqli qiymatlar diapazoni (ta'rif sohasi) OABCD model uchun (2.2) cheklovlar (2.3) orqali hosil bo'ladi (2.2-rasm). Javob yuzasi tekis ko'pburchakdir OA "B" C "D"(2.2-rasm, b).

Cheklovlarning ma'lum nisbati uchun mumkin bo'lgan echimlar to'plami mavjud bo'lmasligi mumkin (bo'sh). Bunday to'plamga misol rasmda ko'rsatilgan. 2.3. To'g'ridan-to'g'ri AS va Quyosh yuqoridan ruxsat etilgan qiymatlar oralig'ini cheklash. Uchinchi cheklov to'g'ri chiziqning pastki qismidan ruxsat etilgan qiymatlar oralig'ini kesib tashlaydi AB. Shunday qilib, barcha uchta cheklovni qondiradigan umumiy maydon yo'q.
Chiziqli modellar juda oddiy va shuning uchun, bir tomondan, muammoni sezilarli darajada soddalashtirishni nazarda tutsa, boshqa tomondan, ular hal qilishning oddiy va samarali usullarini ishlab chiqishga imkon beradi.
DLA ni o'rganishda chiziqli modellar kamdan-kam qo'llaniladi va deyarli faqat muammolarning taxminiy tavsifi uchun.
Chiziqli modellar chiziqli bo'lmagan modellarni bosqichma-bosqich yaqinlashtirish uchun ishlatilishi mumkin (muammoni chiziqlilashtirish). Ushbu uslub, ayniqsa, o'rganilayotgan makonning kichik joylarini o'rganishda samaralidir. Chiziqli bo'lmagan javob yuzasining alohida bo'limlarini chiziqli model bilan ko'rsatish chiziqli taktikalar deb ataladigan optimallashtirish usullarining katta guruhining asosini tashkil qiladi.
Chiziqli modellarni o'rganish qiyin emas. Xususan, har bir o'zgaruvchining shakl modelining xususiyatlariga ta'siri
W = a 0 + a 1 x 1 + a 2 x 2 + …+ a k x k
uning koeffitsientlari bilan ifodalanadi:
, i = 1,…, k.
Optimal chiziqli modelni topish uchun V opt samarali simpleks usulini ishlab chiqdi.
Eng oddiy xarajat modellari ba'zan chiziqli bo'lganlarga qisqartiriladi, ular qilingan xarajatlar to'plami sifatida qaraladi.
Bunday modelga misol klassik hisoblanadi transport xarajatlari modeli (transport muammosi)(2.4-rasm).

U yerda k ishlab chiqarish punktlari
(i = 1,…, k) va m iste'mol nuqtalari
(j = 1,…, m) ba'zi mahsulotlar. Har birida ishlab chiqarilgan mahsulot miqdori k ishlab chiqarish nuqtalari teng a i; har birida talab qilinadigan mahsulot miqdori m iste'mol nuqtalariga teng b j.
Umumiy ishlab chiqarish va iste'molning tengligi qabul qilinadi:
dan tashilgan mahsulot miqdori i- ishlab chiqarish punkti j-inchi iste'mol nuqtasiga teng x ij; ushbu mahsulot birligini tashish narxi - ij bilan.
Transportning umumiy qiymati BILAN S berilgan chiziqli model:

quyidagi cheklovlar ostida

Chiziqli modellarga chiziqli differentsial tenglamalar (oddiy yoki qisman hosilalar) shaklidagi modellar ham kiradi.
Chiziqli oddiy differensial tenglama n-buyurtma shakliga ega dastlabki shartlar quyidagicha yoziladi chiziqli qisman differentsial tenglama shaklga ega
Qisman differensial tenglama ko'rinishida berilgan model boshlang'ich va chegaraviy shartlarni (F funktsiyani aniqlash sohasi chegarasidagi shartlarni) o'z ichiga oladi. t)).