Avzu: chiziqli modellar

L = 1 x 1 + bilan 2 x 2 + ... bilan n x n.
Shartlar ostida (aniqlik uchun tenglamalarda nol va bitta koeffitsientlar saqlanadi):
1x 1+ 0x 2 + ... 0x m + a 1m + 1x m + 1 ... + a 1n x n = b 1;
0x 1 + 1x 2 +… 0x m + a 2m + 1x m + 1 ... + a 2n x n = b 2;
……………………………………………
0x 1+ 0x 2 + ... 1x m + a mm + 1x m +1 ... + a mn x n = b m.
Ushbu tenglamalar tizimi allaqachon tayyor asosga ega, chunki har bir cheklovlar tenglamasi boshqa tenglamalarda, ya'ni o'zgaruvchilar koeffitsientlarida mavjud bo'lmagan birga teng koeffitsientli noma'lumni o'z ichiga oladi. NS 1 , NS 2 …, x m identifikatsiya matritsasini yaratishingiz mumkin.
Keling, asosiy o'zgaruvchilar uchun tenglamalarni yechamiz:
x 1 = b 1 - (a 1m + 1 x m + 1 ... + a 1n x n);
x 2 = b 2 - (a 2m + 1 x m + 1 ... + a 2n x n);
………………………………
x m = b m - (a mm + 1x m + 1 ... + a mn x n),
va maqsad funksiyasini erkin o‘zgaruvchilar bilan ifodalaymiz, ularning ifodalarini asosiy o‘zgaruvchilar o‘rniga erkin o‘zgaruvchilar bilan almashtiramiz:
L = c 1 b 1 + c 2 b 2 + cmbm - (c 1 a 1m + c 2 a 2m + 1 +… + cma mn + 1) x m + 1 -… - (c 1 a 1n + c 2 a 2n +… + cma mn) xn… + cnx n ..
O'zgaruvchilar x 1, x 2 ..., x m, ularning yordami bilan birinchi asosiy reja topilgan, asosiy, qolganlari esa x m +1, x m +2, ... x n - ozod. Tizimdagi tenglamalar qancha bo'lsa, har doim ko'p asosiy o'zgaruvchilar bo'lishi kerak. Salbiy bo'lmagan shartga asoslanib, erkin o'zgaruvchilarning eng kichik qiymati nolga teng. Tenglamalar tizimining olingan asosiy yechimi uning dastlabki ruxsat etilgan yechimidir, ya'ni. x 1 = b 1, x 2 = b 2, ... x m = b m, x m +1 = 0,..., x n = 0.
Bu yechim maqsad funksiyaning qiymatiga mos keladi
L = c 1 b 1 + c 2 b 2 + ... c m b m.
Dastlabki yechim optimallik uchun sinovdan o'tkaziladi. Agar u optimal bo'lmasa, bazisga erkin o'zgaruvchilarni kiritish orqali maqsad funktsiyasining kichikroq qiymatiga ega bo'lgan quyidagi mumkin bo'lgan echimlar topiladi. Buning uchun bazisga kiritilishi kerak bo'lgan erkin o'zgaruvchini, shuningdek, bazisdan olinishi kerak bo'lgan o'zgaruvchini aniqlang. Keyin oldingi tizimdan keyingi ekvivalent tizimga o'tadi. Bu simpleks jadvallari yordamida amalga oshiriladi. Masalani yechish maqsad funksiyaning optimal qiymati olinmaguncha davom etadi.
Simpleks jadvallar quyidagicha tuzilgan (3.1-jadvalga qarang). Barcha o'zgaruvchilar jadvalning yuqori qismida joylashgan. NS 1 , NS 2 …, x n va koeffitsientlar c j, ular bilan mos keladigan o'zgaruvchilar maqsad funktsiyasiga kiritilgan. Birinchi ustun c i bazisga kiritilgan o'zgaruvchilar uchun maqsad funksiya koeffitsientidan iborat. Undan keyin asosiy o'zgaruvchilar ustuni va tenglamalarning erkin shartlari keladi. Jadvalning qolgan ustunlari elementlari tenglamalar tizimiga kiritilgan o'zgaruvchilarning koeffitsientlarini ifodalaydi. Shunday qilib, jadvalning har bir qatori asosiy o'zgaruvchiga nisbatan echilgan tizim tenglamasiga mos keladi. Jadvalda, shuningdek, berilgan asos uchun maqsad funktsiyasiga mos keladigan reja varianti ko'rsatilgan.
Jadvalning pastki qatori deyiladi indeks... Uning har bir elementi (bahosi) ∆ j aniqlash
∆j = z j - c j,
qayerda c j- maqsad funksiyadagi mos o'zgaruvchilar uchun koeffitsientlar; z j - asosiy o'zgaruvchilar uchun maqsad funktsiyasi koeffitsientlarining tegishli o'zgaruvchilar - elementlar bo'yicha mahsuloti yig'indisi j- Jadvalning ustuni.
stol 3.1