Ўзбeкистон республикаси олий ва ўрта махсус таълим вазирлиги

Chiziqli dasturlash modelining matematik tavsifi. Chiziqli dasturlash masalasini simpleks usulida yechish Chiziqli dasturlash modelining umumiy ko’rinishi
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.


Xulosa
Simpleks usuli Chiziqli dasturlash masalalarini hal qilishning keng tarqalgan usuli. Usul o'z nomini "simpleks" so'zidan oldi, bu eng oddiy konveks ko'pburchakni bildiradi, uning uchlari soni har doim bo'shliq o'lchamidan bittaga ko'p. Simpleks usuli AQSHda 1940-yillarning oxirida matematik J.Dansig tomonidan ishlab chiqilgan.
Simpleks usuli kanonik chiziqli tenglamalar tizimining manfiy bo'lmagan asosiy yechimini olish, maqsad funktsiyasini keyinchalik minimallashtirish (maksimallashtirish) va shu tarzda qidirilayotgan o'zgaruvchilarning optimal qiymatlarini topishni o'z ichiga olar ekan. O'zgartirishlar simpleks jadvallar shaklida amalga oshiriladi, bu esa hisob-kitoblarni sezilarli darajada soddalashtiradi va tezlashtiradi.

Chiziqli tenglamalar tizimining manfiy bo'lmagan asosiy yechimlarini olish uchun noma'lumlarni yo'q qilish jarayonini o'tkazish kerak, shunda tenglamalarning erkin shartlari jarayonning barcha bosqichlarida manfiy bo'lmaydi. Bunday holda, quyidagi qoidaga amal qilish kerak: yangi asosiy o'zgaruvchi sifatida kamida bitta ijobiy koeffitsientga ega bo'lgan har qanday erkin o'zgaruvchi olinadi; o'zgaruvchi tenglamalarning erkin shartlarining bazisga kiritilgan o'zgaruvchi uchun tenglamalarning tegishli musbat koeffitsientlariga eng kichik nisbatiga mos keladigan asosdan olinadi. Bu juda muhim, chunki ko'rsatilgan o'zgaruvchining diapazonini aniqlash va uning maksimal qiymatini almashtirish o'rniga, boshqa erkin o'zgaruvchilarning nol qiymatlarida har qanday erkin o'zgaruvchining mumkin bo'lgan eng katta qiymatiga mos keladigan ma'lum bir salbiy bo'lmagan yechimni topish uchun. mumkin bo'lgan qiymatni umumiy yechimga kiritish uchun ushbu o'zgaruvchini asosiy sifatida qabul qilish va tizimni yangi asosga o'tadigan simpleks transformatsiyasiga topshirish kifoya, bu esa hisob-kitoblarni sezilarli darajada osonlashtiradi.

Simpleks jadvallari yordamida hisob-kitoblar qulay tarzda amalga oshiriladi. Bir jadvaldan ikkinchisiga o'tish bir iteratsiyaga, ya'ni bir asosdan ikkinchisiga o'tishga to'g'ri keladi, shu bilan birga maqsad funktsiyasining qiymati kamayadi. Muayyan miqdordagi iteratsiyalar uchun ular maqsad funktsiyasining optimal (minimal yoki maksimal) qiymati olinadigan asosga o'tadi. Simpleks usulini umumiy ko'rib chiqqanda,chiziqli dasturlashning umumiy muammosi - o'zgaruvchilari chiziqli tenglamalar tizimi bilan o'zaro bog'langan, manfiy bo'lmagan shartga bo'ysunadigan maqsad funktsiyasini minimallashtirish (maksimallashtirish) ekanligini sezish mumkin.
Demak,umumiy holda shunday xulosaga kelamizki, Simpleks usuli har qanday chiziqli programmalashtirish masalasining optimal echimini topishga xizmat qiluvchi eng universal usullardan biridir. Iqtisodiyotning turli soxalarini rejalashtirishda ko‘p masalalarining optimal echimini topishda bu usuldan foydalanish mumkin.
Bu usulda biron bir masalani yechishda avvalo,simpleks jadvalini tuzib olib,uning kanonik ko’rinishga keltirib,maqsad funksiyasini yasab olish lozim.Hamda ishlab chiqarish hajmi manfiy bo’lmasligini ham inobatga olamiz.
Bu bizga Iqtisodiyotda qanday qilib eng ko’p foyda olishni aniqlash uchun simpleks usuli algoritmini hosil qilib berar ekan.