Iqtisodiy masalalarni yechishning asosi matematik modellardir.
Jamlama matematik model o'z ichiga oladi:Matematik model muammo - bu masalaning mohiyatini tavsiflovchi matematik munosabatlar to'plami.
Vazifa o'zgaruvchilari to'liq xarakterlovchi X1, X2, Xn miqdorlar deyiladi iqtisodiy jarayon. Ular odatda vektor sifatida yoziladi: X=(X 1, X 2,...,X n).
Cheklovlar tizimi muammolar - bu ko'rib chiqilayotgan masaladagi cheklangan resurslarni tavsiflovchi tenglamalar va tengsizliklar to'plami.
Ob'ektiv funktsiya vazifalar vazifa sifatini tavsiflovchi va ekstremumini topish kerak bo'lgan vazifa o'zgaruvchilari funktsiyasi deb ataladi.
Umuman olganda, vazifa chiziqli dasturlash quyidagi shaklda yozilishi mumkin:
Bu yozuv quyidagilarni bildiradi: maqsad funksiyasining ekstremumini (1) va tegishli o‘zgaruvchilar X=(X 1 , X 2 ,...,X n) toping, bu o‘zgaruvchilar cheklashlar tizimini (2) va salbiy bo'lmagan holatlar (3) .
Yaroqli yechim Chiziqli dasturlash masalasining (rejasi) cheklovlar sistemasi va manfiy bo'lmagan shartlarni qanoatlantiradigan har qanday n o'lchovli X=(X 1 , X 2 ,...,X n) vektordir.
Muammoning mumkin bo'lgan echimlari (rejalari) to'plami mumkin bo'lgan yechimlar hududi(ODR).
Optimal yechim Chiziqli dasturlash masalasining (rejasi) maqsad funksiyasi ekstremumga yetadigan masalaning shunday ruxsat etilgan yechimi (rejasi).
Holati: n turdagi mahsulot ishlab chiqarish uchun m turdagi resurslardan foydalaniladi. Matematik modelni yarating.
Ma'lum:
Resurslarga (xom ashyolarga) berilgan cheklovlar ostida maksimal foyda olishni ta'minlaydigan ishlab chiqarish rejasini tuzish kerak.
Yechim:
X=(X 1, X 2,...,X n) oʻzgaruvchilar vektorini kiritamiz, bunda x j (j = 1,2,...,n) j-chi turdagi ishlab chiqarish hajmi. mahsulot.
X j mahsulotning ma'lum hajmini ishlab chiqarish uchun i-turdagi resurs xarajatlari ij x j ga teng, shuning uchun barcha turdagi mahsulotlarni ishlab chiqarish uchun resurslardan foydalanishni cheklash quyidagi shaklga ega:
j-turdagi mahsulotni sotishdan olingan foyda c j x j ga teng, shuning uchun maqsad funksiyasi quyidagilarga teng:
Javob- Matematik model quyidagicha ko'rinadi:
Umumiy holatda chiziqli dasturlash masalasi shunday yoziladiki, cheklovlar ham tenglamalar, ham tengsizliklar bo'lib, o'zgaruvchilar manfiy bo'lmagan yoki o'zboshimchalik bilan o'zgarishi mumkin.
Agar barcha cheklovlar tenglama bo'lsa va barcha o'zgaruvchilar manfiy bo'lmagan shartni qondirsa, chiziqli dasturlash muammosi deyiladi. kanonik.
U koordinata, vektor va matritsa belgilarida ifodalanishi mumkin.
Koordinata yozuvidagi kanonik chiziqli dasturlash muammosi quyidagi shaklga ega:
Matritsa yozuvidagi kanonik chiziqli dasturlash muammosi quyidagi shaklga ega:
Simmetrik deb ataladigan chiziqli dasturlash muammolari ko'pincha qo'llaniladi, ular matritsa belgilarida quyidagi shaklga ega:
Chiziqli dasturlash masalalarini yechishning aksariyat usullarida cheklovlar tizimi tenglamalar va o'zgaruvchilarning manfiy bo'lmasligi uchun tabiiy sharoitlardan iborat deb taxmin qilinadi. Biroq, iqtisodiy masalalar modellarini tuzishda cheklovlar asosan tengsizliklar tizimi shaklida shakllanadi, shuning uchun tengsizliklar tizimidan tenglamalar tizimiga o'tishni bilish kerak.
Buni shunday qilish mumkin:a 1 x 1 +a 2 x 2 +...+a n x n ≤b chiziqli tengsizlikni olaylik va uning chap tomoniga ma’lum bir x n+1 qiymat qo‘shamiz, shunda tengsizlik a 1 x 1 +a 2 tengligiga aylanadi. x 2 + ...+a n x n +x n+1 =b. Bundan tashqari, bu qiymat x n+1 manfiy emas.
Keling, misol yordamida hamma narsani ko'rib chiqaylik.
26.1-misolLineer dasturlash masalasini kanonik shaklga keltiring:
Yechim:
Maqsad funksiyasining maksimalini topish masalasiga o'tamiz.
Buning uchun maqsad funksiya koeffitsientlarining belgilarini o'zgartiramiz.
Cheklovlar tizimining ikkinchi va uchinchi tengsizliklarini tenglamalarga aylantirish uchun biz manfiy bo'lmagan qo'shimcha x 4 x 5 o'zgaruvchilarni kiritamiz (matematik modelda bu operatsiya D harfi bilan belgilanadi).
x 4 o'zgaruvchisi ikkinchi tengsizlikning chap tomoniga "+" belgisi bilan kiritiladi, chunki tengsizlik "≤" ko'rinishga ega.
x 5 o'zgaruvchisi uchinchi tengsizlikning chap tomoniga "-" belgisi bilan kiritiladi, chunki tengsizlik "≥" ko'rinishga ega.
X 4 x 5 o'zgaruvchilari maqsad funksiyasiga koeffitsient bilan kiritiladi. nolga teng.
Muammoni kanonik shaklda yozamiz.
Chiziqli dasturlash muammosi (LPP) - bu chiziqli funktsiyaning eng katta (yoki eng kichik) qiymatini qavariq ko'p burchakli to'plamda topish masalasi.
Simpleks usuli chiziqli dasturlash masalasini yechish usulidir. Usulning mohiyati dastlabki amalga oshirilishi mumkin bo'lgan rejani topish va keyinchalik ma'lum bir qavariq ko'pburchak to'plamdagi maqsad funktsiyasining maksimal (yoki minimal) qiymatiga erishilgunga qadar yoki muammoning echilishi mumkin emasligi aniqlanmaguncha rejani takomillashtirishdan iborat.
Quyidagi chiziqli dasturlash masalasini kanonik shaklda ko'rib chiqing:
| (1) |
| (2) |
| (3) |
Yuqorida ko'rsatilganidek, kanonik shaklda yozilgan masala uchun, agar matritsaning ustun vektorlari orasida bo'lsa A Mavjud m birlik va chiziqli mustaqil, siz to'g'ridan-to'g'ri mos yozuvlar rejasini belgilashingiz mumkin. Biroq, kanonik shaklda yozilgan va mos yozuvlar rejalariga ega bo'lgan ko'plab chiziqli dasturlash muammolari uchun matritsaning ustun vektorlari orasida A har doim ham mavjud emas m birlik va chiziqli mustaqil. Quyidagi muammoni ko'rib chiqing:
Faraz qilaylik, funksiyaning maksimalini topishimiz kerak
sharoitlarda
birinchilar qayerda n elementlar nolga teng. O'zgaruvchilar 
sun'iy deyiladi. Vektor ustunlari
  | (28) |
sun'iy asos deb ataladigan asosni tashkil qiladi m-o'lchovli vektor fazosi.
Kengaytirilgan masala mos yozuvlar rejasiga ega bo'lgani uchun uning yechimini simpleks usuli bilan topish mumkin.
Teorema 4. Agar optimal rejada 
kengaytirilgan masala (24)−(26) sun’iy o‘zgaruvchilar qiymatlari 
, Bu 
(21)−(23) masala uchun optimal rejadir.
Shunday qilib, agar kengaytirilgan muammo uchun topilgan optimal rejada sun'iy o'zgaruvchilarning qiymatlari nolga teng bo'lsa, u holda asl muammo uchun optimal reja olinadi. Keling, kengaytirilgan muammoning echimini topish haqida batafsilroq to'xtalamiz.
Malumot rejasi uchun maqsad funksiyasining qiymati (27):
Biz buni sezamiz F(X) va ikkita mustaqil qismdan iborat bo'lib, ulardan biri bog'liqdir M, ikkinchisi esa - yo'q.
Hisoblashdan keyin F(X) va ularning qiymatlari, shuningdek kengaytirilgan topshiriqning dastlabki ma'lumotlari yuqorida ko'rsatilganidek, simpleks jadvaliga kiritiladi. Faqatgina farq shundaki bu jadval oddiy simpleks jadvaliga qaraganda bir qator ko'proq o'z ichiga oladi. Shu bilan birga ( m+1)-chi qatorda bo'lmagan koeffitsientlar mavjud M, va ichida ( m+2)-chi qator - uchun koeffitsientlar M.
Bir mos yozuvlar rejasidan ikkinchisiga o'tishda mutlaq qiymatdagi eng katta manfiy raqamga mos keladigan vektor ( m+2) chiziqlar. Bazisdan chiqarib tashlangan sun'iy vektorni asosga qayta kiritish mantiqiy emas. Boshqa mos yozuvlar rejasiga o'tayotganda, sun'iy vektorlarning hech biri asosdan chiqarib tashlanmasligi mumkin. Bir mos yozuvlar rejasidan ikkinchisiga o'tishda simpleks jadvalini qayta hisoblash simpleks usulining odatiy qoidalariga muvofiq amalga oshiriladi (yuqoriga qarang).
Takroriy jarayon ga muvofiq amalga oshiriladi m+2 qator elementlarga teng m O'zgaruvchilarga mos keladigan +2 qator 
salbiy bo'lmaydi. Bundan tashqari, agar sun'iy o'zgaruvchilar bazadan chiqarib tashlansa, kengaytirilgan muammoning topilgan rejasi dastlabki muammoning ba'zi bir mos yozuvlar rejasiga mos keladi.
m+2 qatorlar, ustunlar x 0 salbiy bo'lsa, asl muammoning yechimi yo'q.
Agar barcha sun'iy o'zgaruvchilar asos va elementdan chiqarib tashlanmasa m+2 qatorlar, ustunlar x 0 nolga teng bo'lsa, u holda asl muammoning mos yozuvlar rejasi buziladi va asos sun'iy asosning vektorlaridan kamida bittasini o'z ichiga oladi.
Agar dastlabki masala bir nechta birlik vektorlarini o'z ichiga olsa, ular sun'iy asosga kiritilishi kerak.
Agar takrorlash paytida m+2 qatori endi salbiy elementlarni o'z ichiga olmaydi, keyin iteratsiya jarayoni davom etadi m+1 qator, kengaytirilgan muammoning optimal rejasi topilmaguncha yoki muammoning echilishi mumkin emasligi aniqlanmaguncha.
Shunday qilib, (21)−(23) chiziqli dasturlash masalasining sun’iy bazis usuli yordamida yechimini topish jarayoni quyidagi asosiy bosqichlarni o‘z ichiga oladi:
Chiziqli dasturlash masalalarini onlayn hal qilish uchun kalkulyatordan foydalaning
Matematik modelning komponentlari
Iqtisodiy masalalarni yechishning asosi matematik modellardir.
Matematik modelni yaratish quyidagilarni o'z ichiga oladi:Matematik model muammo - bu masalaning mohiyatini tavsiflovchi matematik munosabatlar to'plami.
Vazifa o'zgaruvchilari iqtisodiy jarayonni to’liq tavsiflovchi X1, X2, Xn miqdorlar deyiladi. Ular odatda vektor sifatida yoziladi: X=(X1, X2,...,Xn).
Cheklovlar tizimi muammolar - bu ko'rib chiqilayotgan masaladagi cheklangan resurslarni tavsiflovchi tenglamalar va tengsizliklar to'plami.
Ob'ektiv funktsiya vazifalar vazifa sifatini tavsiflovchi va ekstremumini topish kerak bo'lgan vazifa o'zgaruvchilari funktsiyasi deb ataladi.
Umuman olganda, chiziqli dasturlash masalasini quyidagicha yozish mumkin:
Ushbu yozuv quyidagilarni bildiradi: maqsad funktsiyasining ekstremumini (1) va tegishli o'zgaruvchilarni toping X=(X1, X2,...,Xn), bu o'zgaruvchilar cheklashlar tizimini (2) va manfiy emasligini qanoatlantirsa. shartlar (3).
Yaroqli yechim Chiziqli dasturlash masalasining (rejasi) cheklanishlar tizimini va manfiy bo'lmagan shartlarni qanoatlantiradigan har qanday n o'lchovli X=(X1, X2,...,Xn) vektoridir.
Muammoning mumkin bo'lgan echimlari (rejalari) to'plami mumkin bo'lgan yechimlar hududi(ODR).
Matematik modelni tuzishga misol.Resurslardan (xom ashyolardan) foydalanish muammosiOptimal yechim Chiziqli dasturlash masalasining (rejasi) maqsad funksiyasi ekstremumga yetadigan masalaning shunday ruxsat etilgan yechimi (rejasi).
Holati: n turdagi mahsulot ishlab chiqarish uchun m turdagi resurslardan foydalaniladi. Matematik modelni yarating.
Ma'lum:
Resurslarga (xom ashyolarga) berilgan cheklovlar ostida maksimal foyda olishni ta'minlaydigan ishlab chiqarish rejasini tuzish kerak.
Yechim:
X=(X1, X2,...,Xn) oʻzgaruvchilar vektorini kiritamiz, bunda xj (j = 1,2,...,n) j-chi turdagi mahsulot ishlab chiqarish hajmi.
Xj mahsulotning ma'lum hajmini ishlab chiqarish uchun i-turdagi resurs xarajatlari aijxj ga teng, shuning uchun barcha turdagi mahsulotlarni ishlab chiqarish uchun resurslardan foydalanishni cheklash quyidagi shaklga ega:
j-turdagi mahsulotni sotishdan olingan foyda cjxj ga teng, shuning uchun maqsad funksiyasi quyidagilarga teng:
Javob- Matematik model quyidagicha ko'rinadi:
Chiziqli dasturlash masalasining kanonik shakli
Umumiy holatda chiziqli dasturlash masalasi shunday yoziladiki, cheklovlar ham tenglamalar, ham tengsizliklar bo'lib, o'zgaruvchilar manfiy bo'lmagan yoki o'zboshimchalik bilan o'zgarishi mumkin.
Agar barcha cheklovlar tenglama bo'lsa va barcha o'zgaruvchilar manfiy bo'lmagan shartni qondirsa, chiziqli dasturlash muammosi deyiladi. kanonik.
U koordinata, vektor va matritsa belgilarida ifodalanishi mumkin.
Koordinata yozuvidagi kanonik chiziqli dasturlash muammosi quyidagi shaklga ega:
Matritsa yozuvidagi kanonik chiziqli dasturlash muammosi quyidagi shaklga ega:
Simmetrik deb ataladigan chiziqli dasturlash muammolari ko'pincha qo'llaniladi, ular matritsa belgilarida quyidagi shaklga ega:
Umumiy chiziqli dasturlash muammosini kanonik shaklga qisqartirish
Chiziqli dasturlash masalalarini yechishning aksariyat usullarida cheklovlar tizimi tenglamalar va o'zgaruvchilarning manfiy bo'lmasligi uchun tabiiy sharoitlardan iborat deb taxmin qilinadi. Biroq, iqtisodiy masalalar modellarini tuzishda cheklovlar asosan tengsizliklar tizimi shaklida shakllanadi, shuning uchun tengsizliklar tizimidan tenglamalar tizimiga o'tishni bilish kerak.
Buni shunday qilish mumkin:a1x1+a2x2+...+anxn≤b chiziqli tengsizlikni olib, uning chap tomoniga ma’lum xn+1 qiymat qo‘shamiz, shundayki tengsizlik a1x1+a2x2+...+anxn+xn+1=b tenglikka aylanadi. . Bundan tashqari, bu qiymat xn+1 manfiy emas.
Keling, misol yordamida hamma narsani ko'rib chiqaylik.
26.1-misolLineer dasturlash masalasini kanonik shaklga keltiring:
Yechim:
Maqsad funksiyasining maksimalini topish masalasiga o'tamiz.
Buning uchun maqsad funksiya koeffitsientlarining belgilarini o'zgartiramiz.
Cheklovlar tizimining ikkinchi va uchinchi tengsizliklarini tenglamalarga aylantirish uchun biz manfiy bo'lmagan qo'shimcha x4 x5 o'zgaruvchilarni kiritamiz (matematik modelda bu operatsiya D harfi bilan belgilanadi).
x4 o'zgaruvchisi ikkinchi tengsizlikning chap tomoniga "+" belgisi bilan kiritiladi, chunki tengsizlik "≤" ko'rinishga ega.
x5 o'zgaruvchisi uchinchi tengsizlikning chap tomoniga “-” belgisi bilan kiritiladi, chunki tengsizlik “≥” ko'rinishga ega.
Maqsad funksiyasiga x4 x5 o'zgaruvchilari koeffitsient bilan kiritiladi. nolga teng.
Muammoni kanonik shaklda yozamiz:
Umumiy chiziqli dasturlash muammosi (GLP) quyidagicha tuzilgan - muammoli o'zgaruvchilarni toping x 1 , x 2 , ..., x n , ular maqsad funktsiyasining ekstremumini ta'minlaydi
Chiziqli dasturlash muammosining (LPP) ruxsat etilgan yechimi (rejasi) har qandaydir n-o'lchovli vektor X=(x 1 , x 2 , ..., x n) tenglik va tengsizliklar tizimini qondirish. Muammoning mumkin bo'lgan echimlari to'plami amalga oshirish mumkin bo'lgan echimlar sohasini tashkil qiladi D.
Chiziqli dasturlash masalasining optimal yechimi (rejasi) maqsadga muvofiq yechimdir, shunda maqsad funksiyasi Z(X) ekstremumga etadi.
Kanonik chiziqli dasturlash muammosi (CLP) shaklga ega
(1.2)
Uning OZLP dan farqi shundaki, uning cheklovlar tizimi faqat tenglamalar tizimi va barcha o'zgaruvchilar manfiy emas.
OPLP ni OPLP ning kanonik shakliga keltirish:
Dastlabki minimallashtirish masalasini maksimallashtirish masalasi (yoki aksincha, maksimallashtirish masalasini minimallashtirish masalasi) bilan almashtirish uchun maqsad funktsiyasini “-1” ga ko'paytirish va natijada olingan funktsiyaning maksimal (minimal) ni izlash kifoya;
Agar cheklovlar o'rtasida tengsizliklar mavjud bo'lsa, unda qo'shimcha manfiy bo'lmagan o'zgaruvchilarni kiritish orqali x n +1 ≥ 0 ular tenglikka aylanadi:
tengsizlik a men 1 x 1 +…+a ichida x n ≥ b i tenglik bilan almashtiriladi a men 1 x 1 +…+a ichida x n+ x n +1 = b men,
tengsizlik a men 1 x 1 +…+a ichida x n ≤ b i tenglik bilan almashtiriladi a men 1 x 1 +…+a ichida x n+ x n +1 = b i;
Agar biron bir o'zgaruvchi bo'lsa x k hech qanday belgi cheklovlari yo'q, keyin u (maqsad funktsiyasida va barcha cheklovlarda) ikkita yangi salbiy bo'lmagan o'zgaruvchilar orasidagi farq bilan almashtiriladi: x k = x" k – x” k , Qayerda x" k ≥ 0. x” k ≥ 0.
Ikki noma'lumli ZLP ni echishning grafik usuli
Ikki noma'lumli ZLP quyidagi shaklga ega:
Usul amalga oshirish mumkin bo'lgan echimlar mintaqasini grafik tasvirlash va ular orasidan optimal echimni topish imkoniyatiga asoslanadi.
Muammoning amalga oshirilishi mumkin bo'lgan echimlar sohasi (ADA) qavariq ko'pburchak bo'lib, har bir muammoni cheklash tengsizligining yechim sohalarining kesishishi (umumiy qismi) sifatida tuzilgan.
Tengsizlikni yechish sohasi a men 1 x 1 +a men 2 x 2 ≤ b i chiziq joylashgan ikki yarim tekislikdan biri a men 1 x 1 +a men 2 x 2 = b Bu tengsizlikka mos keladigan i koordinata tekisligini ajratadi. Ikki yarim tekislikdan qaysi biri yechim mintaqasi ekanligini aniqlash uchun boʻlinuvchi chiziqda yotmaydigan har qanday nuqtaning koordinatalarini tengsizlikka almashtirish kifoya:
Agar tengsizlik rost bo'lsa, u holda yechim viloyati bu nuqtani o'z ichiga olgan yarim tekislikdir;
Agar tengsizlik to'g'ri bo'lmasa, u holda yechim sohasi bu nuqtani o'z ichiga olmaydigan yarim tekislikdir.
Mumkin bo'lgan echimlar orasida eng maqbulini topish uchun darajali chiziqlar qo'llaniladi.
Bir darajali chiziq to'g'ri chiziqdir Bilan 1 x 1 +Bilan 2 x 2 = l, Qayerda l= const, bunda masalaning maqsad funksiyasi doimiy qiymatni oladi. Barcha darajadagi chiziqlar bir-biriga parallel.
Maqsad funksiyasi gradienti grad Z(X) normal vektorni belgilaydi C = (c 1 , c 2) darajali chiziqlar. Darajali chiziqlardagi maqsad funksiyasi, agar sath chiziqlari normal yo'nalishi bo'yicha harakatlantirilsa, ortadi va teskari yo'nalishda kamayadi.
Malumot chizig'i ODR bilan kamida bitta umumiy nuqtaga ega bo'lgan va ODR yarim tekisliklardan birida joylashgan darajali chiziqdir. Muammoning ODD ikkitadan ortiq qo'llab-quvvatlash chizig'iga ega emas.
ZLP ning optimal yechimi ODR poligonining burchak nuqtasida mos yozuvlar chizig'ida yotadi. Agar mos yozuvlar chizig'i ODR ning bir burchak nuqtasidan o'tsa, ZLP noyob echimga ega va agar qo'llab-quvvatlash chizig'i ODR poligonining chetidan o'tsa, cheksiz miqdordagi echimlar mavjud. Agar ODP bo'sh to'plam bo'lsa (cheklashlar tizimi mos bo'lmaganda) va ODP ekstremum yo'nalishi bo'yicha chegaralanmagan bo'lsa (maqsad funktsiyasi chegaralanmagan) ZLP hech qanday yechimga ega emas.
Ikki noma'lumli ZLP ni grafik usulda echish algoritmi:
ODR qurish.
Oddiy vektorni qurish C = (c 1 , c 2) va daraja chizig'i Bilan 1 x 1 +Bilan 2 x 2 = 0 koordinata boshidan o'tuvchi va vektorga perpendikulyar BILAN.
Darajali chiziqni vektor yo'nalishi bo'yicha mos yozuvlar chizig'iga o'tkazing BILAN maksimal muammoda yoki teskari yo'nalishda - min muammoda.
Agar daraja chizig'i ekstremum yo'nalishi bo'yicha harakat qilganda, ODR cheksizlikka ketsa, u holda ZLP maqsad funktsiyasining cheksizligi tufayli hech qanday yechimga ega emas.
Agar ZLP optimal echimga ega bo'lsa, uni topish uchun ODRni cheklaydigan va mos yozuvlar chizig'i bilan umumiy nuqtalarga ega bo'lgan chiziqlar tenglamalarini birgalikda yeching. Agar ekstremumga ikkita burchak nuqtasida erishilgan bo'lsa, u holda ZLP bu burchak nuqtalari bilan chegaralangan ODR chetiga tegishli cheksiz echimlarga ega. IN Ushbu holatda Ikkala burchak nuqtasining koordinatalari hisoblanadi.
Maqsad funksiyasining ekstremum nuqtasidagi qiymatini hisoblang.
Muammolarni hal qilishning Simpleks usuli
Simpleks usuli quyidagi qoidalarga asoslanadi:
Chiziqli dasturlash masalasining ODPsi chekli sonli burchak nuqtalari bo'lgan qavariq to'plamdir;
ZLP ning optimal yechimi ODRning burchak nuqtalaridan biridir. ODR ning burchak nuqtalari algebraik jihatdan ZLP cheklovlar tizimining ba'zi asosiy (mos yozuvlar) echimlarini ifodalaydi.
ZLP ning asosiy (mos yozuvlar) yechimi shunday maqbul yechim hisoblanadi X 0 =(x 10 , x 20 , ..., x m 0 , 0,…0), buning uchun shartlar vektorlari (tizimdagi noma'lum cheklovlar uchun koeffitsientlar ustunlari) chiziqli mustaqildir.
Nolga teng bo'lmagan koordinatalar x 10 , x 20 , ..., x m 0 eritmalar X 0 bazis o'zgaruvchilari deb ataladi, qolgan yechim koordinatalari X 0 - erkin o'zgaruvchilar. Etakchi yechimning nolga teng bo'lmagan koordinatalari soni darajadan ko'p bo'lishi mumkin emas r PLP cheklovlar tizimlari (PLP cheklovlar tizimidagi chiziqli mustaqil tenglamalar soni). Keyinchalik, PLP cheklovlari tizimi chiziqli mustaqil tenglamalardan iborat deb hisoblaymiz, ya'ni. r = m.
Simpleks usulining ma'nosi ZLP ning bir mos yozuvlar yechimidan boshqasiga (ya'ni, bittadan) maqsadli o'tishdir. burchak nuqtasi ODR boshqasiga) ekstremum yo'nalishi bo'yicha va bosqichlar ketma-ketligidan iborat:
Dastlabki yordam echimini toping;
Bir etalon yechimdan boshqasiga o'tishni amalga oshirish;
Optimal yechimga erishish mezonini aniqlang yoki yechim yo'qligi haqida xulosa chiqaring.
Amalga oshirish algoritmiSimpleks usuli ZLP
Simpleks usul algoritmi PLP ning bir etalon yechimidan ikkinchisiga maqsad funksiyaning ekstremum yo'nalishi bo'yicha o'tadi.
ZLP kanonik shaklda (1.2) berilsin va shart bajarilsin
b i ≥ 0, i=1,2,…,m, (1.3)
(1.3) munosabat har doim manfiy bo'lsa, tegishli tenglamani "-1" ga ko'paytirish orqali bajarilishi mumkin. b i. Shuningdek, (1.2) masala cheklovlaridagi tenglamalar tizimi chiziqli mustaqil va darajaga ega deb hisoblaymiz. r = m. Bunday holda, qo'llab-quvvatlash yechimining vektori mavjud m nolga teng bo'lmagan koordinatalar.
Dastlabki masala (1.2), (1.3) asosiy o'zgaruvchilar joylashgan shaklga keltirilsin x 1 , x 2 , ..., x m erkin o'zgaruvchilar bilan ifodalanadi x m + 1 , x m + 2 , ..., x n
(1.4)
Ushbu munosabatlarga asoslanib, biz 1-jadvalni tuzamiz
1-jadval.
1-jadval simpleks jadvali deb ataladi. Barcha keyingi o'zgarishlar ushbu jadval tarkibidagi o'zgarishlar bilan bog'liq.
Algoritm bilanmurakkab usul:
1. Oxirgi qatorda Z Min masaladagi oddiy jadvallar eng kichik musbat elementni (maksimum masalada, eng kichik manfiy element) topadi, erkin atamani hisobga olmaganda. Ushbu elementga mos keladigan ustun yoqish ustuni deb ataladi.
2. Erkin atamalarning ruxsat ustunining ijobiy elementlariga nisbatini hisoblang (simpleks nisbati). Ushbu simpleks munosabatlarining eng kichigini toping, u rezolyutsiya qatoriga mos keladi;
3. Yechish qatori va yechish ustuni kesishmasida yechish elementi joylashgan.
4. Agar teng kattalikdagi bir nechta simpleks munosabatlar mavjud bo'lsa, u holda ulardan istalganini tanlang. Xuddi shu narsa simpleks jadvalining oxirgi qatorining ijobiy elementlariga ham tegishli.
5. Yoqish elementini topgandan so'ng, keyingi jadvalga o'ting. Ruxsat satri va ustuniga mos keladigan noma'lum o'zgaruvchilar almashtiriladi. Bunday holda, asosiy o'zgaruvchi erkin o'zgaruvchiga aylanadi va aksincha. Simpleks jadvali quyidagicha o'zgartiriladi (2-jadval):
jadval 2
6. 1-jadvalning hal qiluvchi elementiga mos keladigan 2-jadvalning elementi hal qiluvchi elementning o'zaro qiymatiga teng.
7. 1-jadvalning ruxsat beruvchi qatori elementlariga mos keladigan 2-jadval qatorining elementlari 1-jadvalning mos keladigan elementlarini ruxsat beruvchi elementga bo'lish yo'li bilan olinadi.
8. 1-jadvalning yechish ustuni elementlariga mos keladigan 2-jadval ustunining elementlari 1-jadvalning mos keladigan elementlarini yechish elementiga bo'lish yo'li bilan olinadi va qarama-qarshi belgi bilan olinadi.
9. Qolgan elementlar tomonidan hisoblanadi to'rtburchaklar qoidasi: Biz aqliy ravishda 1-jadvalda to'rtburchak chizamiz, uning bir uchi hal qiluvchi elementga (Re), ikkinchisi esa biz izlayotgan elementga to'g'ri keladi; Yangi jadvaldagi elementni 2 (Ne), eski jadval 1ning o‘sha joyidagi elementni (Se) bilan belgilaymiz. Qolgan ikkita A va B cho'qqilari rasmni to'rtburchakga to'ldiradi. U holda 2-jadvaldan talab qilinadigan He elementi He = Se – A*B/Re ga teng.
10. Optimallik mezoni. Jadvalning eng oxirgi qatoridagi barcha elementlar manfiy (maksimum masalada barcha elementlar musbat) bo‘lgan jadval olinishi bilan ekstremum topilgan deb hisoblanadi. Maqsad funksiyasining optimal qiymati Z qatordagi erkin muddatga teng, optimal yechim esa bazis o‘zgaruvchilarning erkin shartlari bilan aniqlanadi. Barcha erkin o'zgaruvchilar nolga o'rnatiladi.
11.Agar rezolyutsiya ustunidagi barcha elementlar salbiy bo'lsa, unda muammoning echimlari yo'q (minimalga erishilmaydi).
ZLP ni hal qilish uchun sun'iy asos usuli
Simpleks usuli algoritmi, agar PLP ning har qanday mos yozuvlar yechimi tanlangan bo'lsa, ya'ni dastlabki PLP (1.2) (1.4) ko'rinishga tushirilganda qo'llaniladi. Sun'iy asos usuli bunday mos yozuvlar yechimini qurish tartibini taklif qiladi.
Sun'iy bazis usuli sun'iy bazis o'zgaruvchilarni kiritishga asoslangan y 1 , y 2 ,…, y m , uning yordamida PLP cheklovlar tizimi (2.2)
(1.5)
shaklga aylantirish mumkin
(1.6)
Tizimlar (1.5) va (1.6) agar hammasi bo'lsa ekvivalent bo'ladi y i nolga teng bo'ladi. Avvalgidek, biz hamma narsaga ishonamiz b i ≥ 0. Uchun da i 0 ga teng bo'lsa, biz muammoni barcha sun'iy asos o'zgaruvchilari bo'lishi uchun o'zgartirishimiz kerak y i erkin o'zgaruvchilarga o'tdi. Bunday o'tishni qo'shimcha maqsad funktsiyasiga nisbatan simpleks usuli algoritmi yordamida amalga oshirish mumkin
F(y) = y 1 + y 2 + ... + y m = d 0 – (d 1 x 1 +d 2 x 2 +…+d n x n). (2.7)
Ushbu usul uchun dastlabki simpleks jadvali o'xshaydi
Birinchidan, simpleks jadvali maqsad funktsiyasiga nisbatan o'zgartiriladi F(y) mos yozuvlar eritmasi olinmaguncha. Malumot yechimi quyidagi mezon bajarilganda topiladi: F(y) = 0 va barcha sun'iy o'zgaruvchilar da i erkin o'zgaruvchilarga tarjima qilingan. So'ngra uchun simpleks jadvalidan bir qator kesib tashlanadi F(y) va uchun ustunlar da i va asl maqsad funksiyasi uchun muammoni hal qiling Z(x) optimal yechim olinmaguncha.
Chiziqli dasturlash oʻzgaruvchilar chiziqli tenglamalar yoki chiziqli tengsizliklar koʻrinishidagi chekli sonli cheklovlarni qondirish sharti bilan cheklangan sonli oʻzgaruvchilarning chiziqli funksiyasining minimal yoki maksimalini topish usullarini oʻrganuvchi matematikaning boʻlimidir.
Shunday qilib, umumiy chiziqli dasturlash muammosini (GLP) quyidagicha shakllantirish mumkin.
Haqiqiy o'zgaruvchilar qiymatlarini toping maqsad funktsiyasi
koordinatalari qanoatlantiradigan nuqtalar to'plamida minimal qiymatni oladi cheklovlar tizimi
Ma'lumki, buyurtma qilingan qiymatlar to'plami n o'zgaruvchilar , , … n o'lchovli fazodagi nuqta bilan ifodalanadi. Quyida biz ushbu nuqtani belgilaymiz X=( , , … ).
Matritsa shaklida chiziqli dasturlash masalasini quyidagicha shakllantirish mumkin:
, A- o'lcham matritsasi,
Nuqta X=( , , … ), barcha shartlarni qanoatlantiruvchi deyiladi haqiqiy nuqta . Barcha ruxsat etilgan nuqtalar to'plami deyiladi amaldagi maydon .
Optimal yechim (optimal reja) chiziqli dasturlash masalasi yechim deb ataladi X=( , , … ), ruxsat etilgan mintaqaga tegishli va chiziqli funktsiya Q optimal (maksimal yoki minimal) qiymatni oladi.
Teorema. Chiziqli dasturlash masalasining cheklashlar tizimining barcha mumkin bo'lgan yechimlari to'plami qavariqdir.
Nuqtalar to'plami deyiladi qavariq , agar u istalgan ikkita nuqta bilan birgalikda ularning ixtiyoriy qavariq chiziqli birikmasini o'z ichiga olsa.
Nuqta X chaqirdi qavariq chiziqli birikma shartlar bajarilgan taqdirda ball
Chiziqli dasturlash muammosining barcha mumkin bo'lgan yechimlari to'plami qavariq ko'p burchakli mintaqa bo'lib, biz bundan buyon uni chaqiramiz. eritmalar ko'p yuzli .
Teorema. Agar ZLP optimal yechimga ega bo‘lsa, u holda maqsad funksiyasi eritma ko‘pburchak cho‘qqilaridan birida maksimal (minimal) qiymatni oladi. Agar maqsad funksiyasi bir nechta nuqtada maksimal (minimal) qiymatni qabul qilsa, u holda bu qiymatni ushbu nuqtalarning qavariq chiziqli birikmasi bo'lgan har qanday nuqtada oladi.
Tizimning ko'plab echimlari orasida m yechimlar ko'p yuzlisini tavsiflovchi chiziqli tenglamalar, asosiy yechimlar deb ataladiganlar ajratiladi.
Tizimning asosiy yechimi m n o'zgaruvchili chiziqli tenglamalar yechim bo'lib, unda hammasi n-m asosiy bo'lmagan o'zgaruvchilar nolga teng. Chiziqli dasturlash masalalarida shunday yechimlar deyiladi qabul qilinadigan asosiy echimlar (mos yozuvlar rejalari).
Teorema. Chiziqli dasturlash masalasining har bir ruxsat etilgan asosiy yechimi yechim ko‘p yuzlining cho‘qqisiga to‘g‘ri keladi va aksincha, yechim ko‘p yuzlining har bir cho‘qqisiga yo‘l qo‘yilgan asosiy yechim mos keladi.
Yuqoridagi teoremalardan muhim xulosa kelib chiqadi:
Agar chiziqli dasturlash muammosi optimal yechimga ega bo'lsa, u holda u hech bo'lmaganda amalga oshirish mumkin bo'lgan asosiy echimlardan bittasiga to'g'ri keladi.
Binobarin, chiziqli dasturlash masalasi maqsadining chiziqli funksiyasining optimalini uning amalga oshirilishi mumkin bo'lgan asosiy yechimlarining chekli soni orasidan izlash kerak.
