Iqtisodiy masalalarni yechishning asosi matematik modellardir.

Matematik model muammo - bu masalaning mohiyatini tavsiflovchi matematik munosabatlar to'plami.

Matematik modelni yaratish quyidagilarni o'z ichiga oladi:

• muammoli o'zgaruvchilarni tanlash
• cheklovlar tizimini ishlab chiqish
• maqsad funktsiyasini tanlash

Vazifa o'zgaruvchilari iqtisodiy jarayonni to’liq tavsiflovchi X1, X2, Xn miqdorlar deyiladi. Ular odatda vektor sifatida yoziladi: X=(X 1, X 2,...,X n).

Cheklovlar tizimi masalalar - 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 toping (1) va tegishli o'zgaruvchilar X=(X 1, X 2,...,X n), bu o'zgaruvchilar cheklovlar (2) va bo'lmaganlar tizimini qanoatlantirsa. -salbiy 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).

Matematik modelni tuzishga misol

Resurslardan (xom ashyolardan) foydalanish muammosi

Vaziyat: n turdagi mahsulot ishlab chiqarish uchun m turdagi resurslardan foydalaniladi. Matematik modelni yarating.

Ma'lum:

• b i (i = 1,2,3,...,m) — har bir i-turdagi resurs zahiralari;
• a ij (i = 1,2,3,...,m; j=1,2,3,...,n) - hajm birligini ishlab chiqarish uchun har bir i-turdagi resurs xarajatlari. j-chi turdagi mahsulot;
• c j (j = 1,2,3,...,n) - j-chi turdagi mahsulot hajm birligini sotishdan olingan foyda.

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 mahsulot ishlab chiqarish hajmi. .

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 shaklga ega:

Chiziqli dasturlash masalasining kanonik shakli

Umuman olganda, chiziqli dasturlash muammosi 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:

• A - tenglamalar tizimining koeffitsientlari matritsasi
• X — vazifa oʻzgaruvchilari matritsasi ustuni
• Ao — cheklashlar tizimining o'ng qismlarining matritsa-ustunlari

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:

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-misol

Chiziqli 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.

Shu kunlarda ta'lim dasturi iqtisod, moliya va menejment bilan bog'liq mutaxassisliklar "Optimal qarorlar usullari" deb nomlangan fanni o'z ichiga oladi. Ushbu fan doirasida talabalar optimallashtirish, operatsiyalarni tadqiq qilish, qaror qabul qilish va modellashtirishning matematik tomonini o'rganadilar. Asosiy xususiyat Ushbu fan matematik usullarni iqtisodiy muammolarni hal qilishda qo'llash bilan birgalikda o'rganish bilan belgilanadi.

Optimallashtirish vazifalari: umumiy ma'lumot

Agar umumiy holatni ko'rib chiqsak, optimallashtirish masalasining ma'nosi ma'lum bir cheklash sharoitida maqsad funktsiyasini maksimal darajaga tushiradigan (minimallashtiradigan) optimal echim deb ataladigan echimni topishdir.

Funktsiyalarning xususiyatlariga ko'ra, optimallashtirish muammolarini ikki turga bo'lish mumkin:

• chiziqli dasturlash masalasi (barcha funksiyalar chiziqli);
• chiziqli bo'lmagan dasturlash muammosi (kamida bitta funktsiya chiziqli emas).

Optimallashtirish masalalarining alohida holatlari fraksiyonel-chiziqli, dinamik va stokastik dasturlash masalalari hisoblanadi.

Eng ko'p o'rganilgan optimallashtirish muammolari chiziqli dasturlash muammolari (LPP) bo'lib, ularning echimlari faqat butun son qiymatlarni oladi.

PPP: shakllantirish, tasniflash

Chiziqli dasturlash masalasi umumiy holatda chiziqli funksiyaning ma’lum chiziqli cheklovlar ostida minimal (maksimal) ni topishdan iborat.

Umumiy ZLP - bu shakl muammosi

cheklovlar ostida

qayerda o‘zgaruvchilar, berilgan haqiqiy sonlar, maqsad funksiyasi, masala rejasi, (*)-(***) cheklovlar.

ZLP ning muhim xususiyati shundan iboratki, maqsad funksiyaning ekstremumiga mumkin bo'lgan yechimlar mintaqasi chegarasida erishiladi.

Optimal yechim usullarining amaliy iqtisodiy qo'llanilishi quyidagi turdagi muammolarni hal qilishda topiladi:

• aralashmalar bilan bog'liq muammolar (ya'ni, mahsulotlar tarkibini rejalashtirish);
• ishlab chiqarishni rejalashtirishda resurslarni optimal taqsimlash muammolari;

PAP: misollar

Aralash muammosi

Aralashmalar muammosini hal qilish kerakli xususiyatlarga ega aralashmani ta'minlaydigan ma'lum boshlang'ich materiallardan iborat eng arzon to'plamni topishdan iborat.

Resurslarni taqsimlash muammosi

Kompaniya ishlab chiqaradi n ishlab chiqarishni talab qiladigan turli xil mahsulotlar m har xil turlari resurslar. Foydalanilgan resurslarning zaxiralari cheklangan va mos ravishda miqdori b 1, b 2,…, b m c.u. Bundan tashqari, texnologik koeffitsientlar ma'lum a ij, bu qancha birliklarni ko'rsatadi i-bir birlik mahsulot ishlab chiqarish uchun resurs talab qilinadi j-th turi (). Korxonaning mahsulotni sotishdan oladigan foydasi j-th turi, miqdori c j pul birliklari Mahsulot ishlab chiqarish rejasini tuzish kerak, uni amalga oshirish jarayonida korxonaning foydasi eng katta bo'ladi.

Aralashmalar va resurslarni taqsimlash bilan bog'liq masalalar ko'pincha jadval shaklida yoziladi.

Resurslar	Ehtiyojlar			Zaxiralar
	B 1	…	Bn
A 1				b 1
…				…
Am				b m
Foyda	c 1	…	c n

Aralashma va resurslarni taqsimlash muammolarini bir necha usul bilan hal qilish mumkin:

• grafik usul (matematik modelda oz sonli o'zgaruvchilar mavjud bo'lganda);
• simpleks usuli (agar matematik modeldagi o'zgaruvchilar soni ikkitadan ko'p bo'lsa).

Transport muammosi ma'lum bir o'ziga xos tuzilishga ega bo'lgan vazifalar sinfini anglatadi. Eng oddiy transport muammosi - barcha mahsulotlarni tashish uchun minimal xarajatlar bilan mahsulotni jo'nash joylaridan belgilangan manzillarga tashish muammosi.

Aniqlik va idrok etish qulayligi uchun transport muammosining holati odatda quyidagi jadvalda yoziladi:

Umuman olganda, transport muammosini hal qilish bir necha bosqichda amalga oshiriladi:

• I bosqich: dastlabki ma'lumotnoma rejasini qurish;
• II bosqich: mos yozuvlar rejasini optimalligini tekshirish;
• III bosqich: agar u maqbul bo'lmasa, mos yozuvlar rejasini aniqlashtirish.

Dastlabki mos yozuvlar rejasini olishning bir necha usullari mavjud, masalan, shimoli-g'arbiy burchak usuli, Vogel usuli va minimal xarajat usuli.

Rejaning optimalligi potentsial usul yordamida tekshiriladi:

- ishg'ol qilingan hujayralar uchun,
- band bo'lmagan hujayralar uchun.

Agar reja optimal bo'lmasa, unda tsikl quriladi va transport qayta taqsimlanadi.

Xulosa

Bitta maqola doirasida optimal echim usullarining butun nazariyasi va amaliyotini qamrab olishning iloji yo'q, shuning uchun faqat ushbu fan, muammolar va ularni hal qilish usullari haqida umumiy tasavvur berishga imkon beradigan ba'zi fikrlar ko'rib chiqiladi.

Bundan tashqari, optimallashtirish muammolari bo'yicha olingan echimlarni tekshirish uchun siz MS Excel paketining "Yechimlarni qidirish" plaginidan juda samarali foydalanishingiz mumkinligini ta'kidlash yaxshi. Ammo bu, aslida, optimallashtirish muammolarini hal qilish usullarini batafsil ko'rib chiqish kabi boshqa hikoya.

Bu erda optimal echim usullarini o'rganish uchun bir nechta darsliklar mavjud:

1. Bandi B. Chiziqli dasturlash asoslari: Trans. ingliz tilidan – M.: Radio va aloqa, 1989. – 176 b.
2. Kremer N.Sh. Iqtisodiyotda operatsiyalar tadqiqoti: Proc. universitetlar uchun qo'llanma / N.Sh. Kremer, B.A. Putko, I.M. Trishin, M.N. Fridman; Ed. prof. N.Sh. Kremer. – M.: BIRLIK, 2005. – 407 b.

Maxsus optimallashtirish usullarini hal qilish

Biz optimal yechim usullaridan foydalangan holda har qanday muammolarni hal qilishda yordam bera olamiz. Muammolarni hal qilish uchun veb-saytimizda buyurtma berishingiz mumkin. Siz faqat oxirgi muddatni ko'rsatishingiz va faylni vazifa bilan biriktirishingiz kerak. buyurtmangiz bepul.

Operatsion tadqiqotlar murakkab matematik intizom boʻlib, operatsiyalar davomida optimal qarorlar qabul qilish uchun matematik modellarni qurish, tahlil qilish va qoʻllash bilan shugʻullanadi.

Operatsion tadqiqotlar mavzusi- har doim ham bir-biriga mos kelmaydigan va qarama-qarshi bo'lishi mumkin bo'lgan ko'p sonli o'zaro ta'sir qiluvchi birliklardan tashkil topgan tashkiliy boshqaruv tizimlari yoki tashkilotlar.

Operatsion tadqiqotlar maqsadi- tashkilotlarni boshqarish bo'yicha qabul qilingan qarorlarning miqdoriy asoslanishi

Operatsiya- yagona reja bilan birlashtirilgan va aniq maqsadga erishishga qaratilgan boshqariladigan harakatlar tizimi.

Amaliyot davomida boshqaruv parametrlari (o'zgaruvchilari) to'plami deyiladi qaror. Yechim deyiladi qabul qilinadi , agar u ma'lum shartlar to'plamini qondirsa. Yechim deyiladi optimal

, agar u maqbul bo'lsa va ma'lum mezonlarga ko'ra, boshqalardan afzalroq bo'lsa yoki hech bo'lmaganda yomonroq bo'lmasa. Afzallik belgisi

optimallik mezoni deb ataladi. Optimallik mezoni

maqsad funktsiyasini, optimallashtirish yo'nalishini yoki maqsad funktsiyalari to'plamini va mos keladigan optimallashtirish yo'nalishlarini o'z ichiga oladi. Ob'ektiv funktsiya - Bu miqdoriy ko'rsatkich

yechimlarning afzalligi yoki samaradorligi. Optimallashtirish yo'nalishi

- agar maqsad funktsiyasining eng katta (eng kichik) qiymati eng maqbul bo'lsa, bu maksimal (minimal).

Misol uchun, mezon foydani ko'paytirish yoki xarajatlarni minimallashtirish bo'lishi mumkin.

IO muammosining matematik modeli quyidagilarni o'z ichiga oladi:

1) topilishi kerak bo'lgan o'zgaruvchilarning tavsifi;

2) optimallik mezonlarining tavsifi; 3) ruxsat etilgan echimlarning tavsifi (o'zgaruvchilarga qo'yilgan cheklovlar)

IO ning maqsadi maqbul yechimyoki reja ZLP. Barcha rejalar to'plami deyiladi amaldagi maydon yokimumkin bo'lgan echimlar maydoni. Maqsad funktsiyasini maksimal (minimal) etkazib beradigan reja deyiladioptimal reja yokiZLP uchun optimal yechim. Shunday qilib,PIL ni hal qiling – uning optimal rejasini topish demakdir.

Quyidagi aniq qoidalardan foydalangan holda umumiy ZLP ni asosiyga olib kelish juda oddiy.

Maqsad funktsiyasini minimallashtirish f funksiyani maksimallashtirishga teng g = – f.

Tengsizlik cheklovi qo'shimcha o'zgaruvchi bo'lishi sharti bilan tenglamaga ekvivalent bo'ladi.

Agar ba'zi o'zgaruvchilar uchun x j manfiy bo'lmagan shart qo'yilmaydi, keyin o'zgaruvchining o'zgarishi amalga oshiriladi.

Darajali chiziq funktsiyalari f, ya'ni bu funktsiya bir xil sobit qiymatni oladigan chiziq Bilan, ya'ni. f(x 1 , x 2)= c

Nuqtalar to'plami deyiladi qavariq, agar u har qanday ikkita nuqta bilan birga ushbu nuqtalarni bog'laydigan butun segmentni o'z ichiga oladi.

Ikki oʻzgaruvchi boʻlsa, chiziqli tengsizlik (tenglama) yechimlari toʻplami yarim tekislik (toʻgʻri chiziq) boʻladi.

Ushbu yarim tekisliklarning kesishishi (va to'g'ri chiziqlar, agar cheklovlar tizimi tenglamalarga ega bo'lsa) amalga oshirilishi mumkin bo'lgan mintaqani ifodalaydi. Agar u bo'sh bo'lmasa, u qavariq to'plam bo'lib, deyiladi.

eritma ko'pburchagi Uchta o'zgaruvchi bo'lsa, ZLP ning ruxsat etilgan hududi yarim bo'shliqlar va, ehtimol, tekisliklarning kesishishi hisoblanadi va deyiladi.

eritmalar ko'p yuzli Tizim chiziqli tenglamalarchaqirdi, asosli tizim agar har bir tenglamada 1 ga teng koeffitsientli noma'lum bo'lsa, u tizimning boshqa tenglamalarida yo'q. Bu noma'lumlar deyiladi, asosiy – dam olish.

bepul Biz chiziqli tenglamalar tizimini chaqiramiz, kanonikagar bu asosga ega tizim bo'lsa va bu shunday i b ≥ 0. Bu holda asosiy yechim reja bo'lib chiqadi, chunki uning tarkibiy qismlari manfiy emas. Keling, unga qo'ng'iroq qilaylik asosiy (yoki) reja qo'llab-quvvatlovchi

kanonik tizim. Biz chiziqli tenglamalar tizimini chaqiramiz Biz uni OZLP deb nomlaymiz

(KZLP), agar bu masalaning chiziqli tenglamalar tizimi kanonik bo'lsa va maqsad funktsiyasi faqat erkin noma'lumlar bilan ifodalangan bo'lsa. T.

Agar simpleks jadvalida har qanday erkin noma'lum uchun koeffitsientlar orasida kamida bitta ijobiy element mavjud bo'lsa, unda ko'rsatilgan erkin noma'lum asosiy bo'lib chiqadigan asl muammoga ekvivalent yangi kanonik masalaga o'tish mumkin. bu holda asosiy noma'lumlardan biri erkin bo'ladi).. Teorema 2 j (asosiy bazani yaxshilash bo'yicha) j Agar kamida bitta ijobiy element mavjud bo'lsa va asosiy munosabatlar > 0 bo'lsa, u holda asosiy dizaynga ega ekvivalent kanonik masalaga o'tish mumkin.

Teorema 3. (optimallik uchun etarli shart). 0 Agar maksimallashtirish masalasining simpleks jadvali indeks qatorining barcha elementlari manfiy bo'lmasa, bu masalaning asosiy dizayni optimal bo'ladi va

muammoli rejalar majmuasida maqsad funksiyasining maksimali mavjud.. Teorema 4(cheklanmagan maqsad funksiyasi holati) j . j Maksimallashtirish masalasining simpleks jadvalining indeks qatorida manfiy element mavjud bo'lsa

, va noma'lum x ustunida

barcha elementlar ijobiy emas, u holda muammoli rejalar to'plamida maqsad funktsiyasi yuqoridan chegaralanmagan.

Simpleks usuli:

Biz ushbu KZLP ni asl simpleks jadvaliga yozamiz.

Simpleks jadvali indeks qatorining barcha elementlari manfiy bo'lmasa, masalaning asosiy rejasi optimal hisoblanadi (3-teorema).

Agar indeks qatorida manfiy element bo'lsa, uning ustida jadvalda ijobiy element yo'q, u holda maqsad funktsiyasi rejalar to'plamida yuqoridan chegaralanmagan va muammoning echimlari yo'q (4-teorema).

Agar indeks satrining har bir salbiy elementi ustidagi jadvalda kamida bitta ijobiy element mavjud bo'lsa, unda siz asosiy reja oldingisidan yomonroq bo'lmagan yangi simpleks jadvaliga o'tishingiz kerak (2-teorema). Buning uchun (1-teoremaning isbotiga qarang) agar bu asosga ega tizim bo'lsa va bu shunday i jadvaldagi asosiy ustunni tanlang, uning asosida indeks qatorining har qanday salbiy elementi mavjud;

kalit munosabatni tanlang (munosabatlarning eng kichigi

asosiy ustunning ijobiy elementlariga), ularning maxraji asosiy element bo'ladi;

yangi simpleks jadvalini tuzish; Buning uchun kalit qatorni (asosiy element joylashgan qatorni) asosiy elementga bo'ling, so'ngra boshqa barcha qatorlardan (shu jumladan indeks) asosiy ustunning tegishli elementiga ko'paytiriladigan natijani olib tashlang ( Shunday qilib, ushbu ustunning barcha elementlari, kalitdan tashqari, 0 ga teng bo'ladi).

Olingan simpleks jadvalini ko'rib chiqayotganda, paragraflarda tasvirlangan uchta holatdan biri o'zini namoyon qiladi. 2, 3, 4. Agar paragraflarda vaziyatlar yuzaga kelsa. 2 yoki 3, keyin muammoni hal qilish jarayoni tugaydi, lekin 4-bosqichdagi vaziyat yuzaga kelsa, jarayon davom etadi.

Agar biz turli xil asosiy rejalar soni cheklanganligini hisobga olsak, unda ikkita holat mumkin: cheklangan miqdordagi qadamlardan so'ng muammo hal qilinadi (2 yoki 3 holatlar yuzaga keladi);(simpleks jadvallar va asosiy rejalarni davriy takrorlash).

Bu vazifalar deyiladi nosimmetrik ikki tomonlama muammolar.

Keling, ushbu vazifalarni bog'laydigan quyidagi xususiyatlarni ta'kidlaymiz:

Muammolardan biri maksimallashtirish muammosi, ikkinchisi esa minimallashtirish masalasidir.

Maksimallashtirish masalasida barcha tengsizliklar ≤ ga, minimallashtirish masalasida esa barcha tengsizliklar ≥ ga teng.

Bir muammoning noma'lumlari soni ikkinchisining tengsizliklari soniga teng.

Ikkala masalaning tengsizliklaridagi noma'lumlar uchun koeffitsient matritsalari o'zaro ko'chiriladi.

Masalalardan birining tengsizliklarining erkin hadlari boshqa masalaning maqsad funksiyasini ifodalashda mos keladigan noma’lumlar koeffitsientlariga teng.

Ikkilamchi masalani tuzish algoritmi.

1. Asl masala cheklovlar tizimining barcha tengsizliklarini bir ma'noga - kanonik shaklga keltiring.

2. B i ustuni va maqsad funksiya F koeffitsientlarini o'z ichiga olgan A tizimning kengaytirilgan matritsasini tuzing.

3. Ko‘chirilgan A T matritsani toping.

4. Ikkilamchi masalani yozing. Teorema 5.

f(x) ≤ g(Har qanday reja uchun maksimallashtirish muammosining maqsad funktsiyasining qiymati uning har qanday rejalari uchun ikki tomonlama minimallashtirish muammosining maqsad funktsiyasining qiymatidan oshmaydi, ya'ni tengsizlik:),

y chaqirdi.

asosiy ikkilik tengsizligi (Teorema 6.optimallik uchun etarli shart

). (Agar ikki tomonlama muammolarning ba'zi rejalari uchun maqsad funktsiyalarining qiymatlari teng bo'lsa, bu rejalar optimal hisoblanadi.Teorema 7.

asosiy ikkilik teoremasi ().Agar ZLP chekli optimalga ega bo'lsa, uning ikkiligi ham chekli optimalga ega va maqsad funktsiyalarining optimal qiymatlari mos keladi. Ikkilamchi masalalardan birining maqsad funksiyasi cheklanmagan bo'lsa, ikkinchi masala shartlari bir-biriga ziddir.

Teorema 8.

qo'shimcha qattiqlik bo'yicha

).Ikkilamchi masalalarning maqbul echimlari maqbul bo'lishi uchun quyidagi munosabatlarni qondirish zarur va etarli: To'g'ridan-to'g'ri ZLP ning manba qiymatlari ikki tomonlama muammoni optimal hal qilishda o'zgaruvchilar qiymatlarini ifodalaydi.

Dual ZLP ning optimal yechimining komponentlari qo'shimcha o'zgaruvchilarga mos keladigan to'g'ridan-to'g'ri muammoning optimal simpleks jadvalining indeks qatorining mos keladigan elementlariga teng.

11-teorema.

(transport muammosi rejasining optimalligi mezoni).

Tashish rejasi) optimal bo'lishi uchun quyidagi shartlarga javob beradigan raqamlar () va () mavjudligi zarur va etarli: Ushbu transport vazifasi yopiq yoki yo'qligini tekshiring. Ha bo'lsa, ikkinchi bosqichga o'ting. Agar yo'q bo'lsa, soxta etkazib beruvchini yoki soxta iste'molchini joriy qilish orqali uni yopiq muammoga aylantiring.

2-qadam. Yopiq transport masalasining dastlabki mos yozuvlar yechimini (dastlabki mos yozuvlar rejasi) toping.

3-qadam. Olingan qo'llab-quvvatlash yechimining optimalligini tekshiring:

buning uchun yetkazib beruvchi potentsiallarini hisoblash u i va iste'molchilar v j

barcha erkin hujayralar uchun ( i, j) hisob-kitoblarni hisoblash;

agar barcha hisob-kitoblar ijobiy bo'lmasa (), u holda muammoni hal qilish tugallanadi: dastlabki ma'lumotnoma rejasi optimaldir. Agar baholashlar orasida kamida bitta ijobiy bo'lsa, biz to'rtinchi bosqichga o'tamiz.

4-qadam. Hujayrani tanlang ( i * ,j * ) eng katta ijobiy baho bilan va buning uchun yuklarni qayta taqsimlashning yopiq tsiklini qurish. Tsikl tanlangan katakda boshlanadi va tugaydi. i * , j * Biz yangi qo'llab-quvvatlash echimini olamiz, unda hujayra (

) band bo'ladi. Uchinchi bosqichga qaytaylik.

Cheklangan sonli qadamlardan so'ng optimal echim, ya'ni mahsulotni etkazib beruvchilardan iste'molchilarga tashish uchun optimal reja olinadi. Nuqta nuqta deyiladi mahalliy maksimal

, Agar bu nuqtada shunday mahalla mavjud bo'lsa

Optimallik uchun zarur shart-sharoitlar x * Bitta o'zgaruvchining funksiyasi nuqtada bo'lishi uchun

mahalliy ekstremum, bu nuqtada funktsiyaning hosilasi nolga teng bo'lishi kerak,

Funktsiya bir nuqtada mahalliy ekstremumga ega bo'lishi uchun uning barcha qisman hosilalari shu nuqtada yo'qolishi kerak. x * Agar nuqtada x * funktsiyaning birinchi hosilasi nolga teng, ikkinchi hosilasi >0, keyin nuqtadagi funksiya<0 то функция в точке x * 2 ta mahsulot bo'lsa, mahalliy minimumga ega,

mahalliy maksimalga ega. Teorema 4. x * Agar bitta o'zgaruvchining funktsiyasi nuqtada bo'lsa n - gacha hosilalar (

1) tartiblar nolga teng va n tartibning hosilasi 0 ga teng emas, u holda, n Agar x * hatto, keyin davr

minimal nuqta, agar,fn(x)>0<0.

maksimal nuqta, agar fn(x) n Agar x * g'alati, keyin nuqta

- burilish nuqtasi. Raqamli matritsa deyiladi .

kvadratik shakldagi matritsa Kvadrat shakl (5) deyiladi ijobiy aniqlik , agar Q(X) >0 uchun va salbiy ta'riflangan<0

, agar uchun.Q(X) Simmetrik matritsa A Kvadrat shakl (5) deyiladi chaqirdi

, agar undan tuzilgan kvadrat shakl (5) musbat aniqlangan bo'lsa. , agar Q(X) >0 uchun va Nosimmetrik matritsa deyiladi

, agar undan tuzilgan kvadrat shakl (6) manfiy aniq bo'lsa.

Agar burchak ostidagi kichiklarning belgilari almashtirilsa, matritsa manfiy aniq hisoblanadi.

Matritsa ijobiy aniq bo'lishi uchun uning barcha xos qiymatlari noldan katta bo'lishi kerak.

Xususiy qiymatlar– polinomning ildizlari.

Optimallikning yetarli sharti quyidagi teorema bilan berilgan.

Teorema 5. Agar statsionar nuqtada Hessian matritsasi musbat aniq bo'lsa, u holda bu nuqta mahalliy minimal nuqta, agar Hessian matritsasi manfiy aniq bo'lsa, bu nuqta mahalliy maksimal nuqtadir.

Mojaro tomonlarning qarama-qarshi manfaatlaridan kelib chiqadigan qarama-qarshilikdir.

Mojaro holati- manfaatlari to'liq yoki qisman qarama-qarshi bo'lgan tomonlar.

O'yin - Bu har biri o'z maqsadlariga erishishga intiladigan kamida ikkita ishtirokchi bo'lgan haqiqiy yoki rasmiy to'qnashuvdir.

O'yin qoidalari ma'lum bir maqsadga erishishga qaratilgan har bir o'yinchining ruxsat etilgan harakatlarini nomlang.

To'lov orqali o'yin natijalarini miqdoriy baholash deb ataladi.

Juftlik o'yini- faqat ikkita partiya (ikkita o'yinchi) ishtirok etadigan o'yin.

Nol summali o'yin yoki antagonistik - to'lov miqdori nolga teng bo'lgan dubllar o'yini, ya'ni bir o'yinchining yo'qotishi ikkinchisining daromadiga teng bo'lsa.

Qoidalarda nazarda tutilgan harakatlardan birini tanlash va amalga oshirish deyiladi o'yinchining navbati. Harakatlar shaxsiy va tasodifiy bo'lishi mumkin.

Shaxsiy harakat- o'yinchining mumkin bo'lgan harakatlardan birini ongli ravishda tanlashi (masalan, shaxmat o'yinidagi harakat).

Tasodifiy harakat tasodifiy tanlangan harakatdir (masalan, aralashgan palubadan kartani tanlash).

Strategiya o'yinchi - bu o'yinchi shaxsiy harakatni amalga oshirishi kerak bo'lgan har bir vaziyatda o'yinchining aniq tanlovidir.

Optimal strategiya- bu o'yinchining strategiyasi bo'lib, u o'yin ko'p marta takrorlanganda unga maksimal mumkin bo'lgan o'rtacha g'alabani yoki minimal mumkin bo'lgan o'rtacha yo'qotishni ta'minlaydi.

To'lov matritsasi- natijada A matritsasi yoki boshqacha qilib aytganda, o'yin matritsasi s.

Cheklangan o'lchov o'yini(m  n) oʻlchamli (m  n) A matritsasi bilan aniqlangan oʻyin.

Maksimin yoki o'yinning past narxi keling, raqamni alpa = max(i)(min aij)(j) deb ataymiz.

va tegishli strategiya (string) maksimal.

Minimaks yoki o'yinning eng yuqori narxi raqamni Beta = min(j)(max aij)i deb ataymiz

va tegishli strategiya (ustun) minimaks.

O'yinning past narxi har doim o'yinning yuqori narxidan oshmaydi.

Egar nuqtasi bilan o'yin Buning uchun o'yinni chaqirdi. Alp = beta

O'yin narxida v if.v = alp = beta miqdori deyiladi

Aralash strategiya o'yinchi vektor bo'lib, uning har bir komponenti o'yinchining tegishli sof strategiyadan foydalanishining nisbiy chastotasini ko'rsatadi.

Teorema 2 .

Matritsali o'yinlar nazariyasining asosiy teoremasi.

Har bir nol summali matritsali o'yin aralash strategiyalarda yechimga ega.3

T

Agar o'yinchilardan biri optimal aralash strategiyadan foydalansa, ikkinchi o'yinchi o'z strategiyalaridan (shu jumladan, sof strategiyalardan) foydalanish chastotasidan qat'i nazar, uning to'lovi o'yin narxiga  teng bo'ladi.

tabiat bilan o'ynash - biz sherikning xatti-harakati haqida ma'lumotga ega bo'lmagan o'yinXavf r ij

Xavf r = agar bu asosga ega tizim bo'lsa va bu shunday j - o'yinchi strategiyani tanlashda A i shartlarda H j farq deb ataladi i ,

a agar bu asosga ega tizim bo'lsa va bu shunday j Qayerda j- maksimal element ichida

- ustun.

Grafik - bu bo'sh bo'lmagan to'plamlar to'plami

deb ataladigan grafaning uchlari to'plami va juft uchlari to'plami

grafik qirralari.

Agar ko'rib chiqilayotgan cho'qqilar juftlari tartiblangan bo'lsa, u holda grafik

yo'naltirilgan (digraf) deb ataladi, aks holda -

yo'naltirilmagan.

IN

A va B cho'qqilarini bog'laydigan grafikdagi marshrut (yo'l) deyiladi

qirralarning ketma-ketligi, birinchisi A cho'qqisidan keladi, boshi

keyingisi oldingisining oxiriga to'g'ri keladi va oxirgi chekka kiritilgan

yuqori V.

Grafik, agar uning istalgan ikkita uchi uchun yo'l bo'lsa, u bog'langan deb ataladi

ularni ulash. Aks holda, grafik uzilgan deb ataladi.

Grafik chekli deb ataladi, agar uning uchlari soni chekli bo'lsa.

Agar cho'qqi qirraning boshi yoki oxiri bo'lsa, u holda cho'qqi va chekka

hodisa deyiladi. Cho'qqining darajasi (tartibi) - unga tushadigan qirralarning soni.

Grafikdagi Eyler yo'li (Euler zanjiri) hammadan o'tuvchi yo'ldir

grafikning qirralari va bundan tashqari, faqat bir marta.

Eyler tsikli - bu tsikl bo'lgan Eyler yo'li.

Eyler grafigi - Eyler siklini o'z ichiga olgan grafik.

Yarim Eyler grafigi - Eyler yo'lini (zanjirlarini) o'z ichiga olgan grafik.

Eyler teoremasi.

Eyler sikli faqat va faqat grafik ulangan bo'lsa va unda mavjud bo'ladi

toq darajali cho'qqilar yo'q.

Teorema. Grafikdagi Eyler yo'li faqat va agar grafik bo'lsa mavjud bo'ladi

ulangan va toq darajali uchlari soni nolga yoki ikkitaga teng.

Tarmoq (yoki tarmoq diagrammasi) yo'naltirilgan chekli hisoblanadi

boshlang'ich cho'qqisi (manba) va yakuniy cho'qqisi (cho'qqisi) bo'lgan bog'langan grafik.

Grafikdagi yo'lning og'irligi uning qirralari og'irliklarining yig'indisidir.

Bir cho'qqidan ikkinchisiga eng qisqa yo'l yo'l deb ataladi

minimal vazn.

Ushbu yo'lning og'irligi orasidagi masofa deb ataladi

cho'qqilari.

Ish ko'p vaqt talab qiladigan jarayon bo'lib, resurslarni talab qiladi,

yoki ikki yoki undan ortiq ish o'rtasidagi mantiqiy bog'liqlik

Voqea bir yoki bir nechta ishlarning bajarilishi natijasidir

Yo'l - bu bir-biriga bog'langan ketma-ket ishlar zanjiri

boshlanish va tugatish cho'qqilari.

Sayohatning davomiyligi vaqtlar yig'indisi bilan belgilanadi

uning tashkil etuvchi asarlari.

Tarmoq diagrammalarini tuzish qoidalari.

1. Tarmoq diagrammasida blokirovka hodisalari bo'lmasligi kerak (bundan tashqari

yakuniy), ya'ni hech qanday ish bilan ta'qib qilinmaganlar.

2. Garchi oldidan bo‘lmagan voqea (boshlang‘ichdan tashqari) bo‘lmasligi kerak

faqat bitta ish.

3. Tarmoq diagrammasida tsikllar bo'lmasligi kerak.

4. Har qanday ikkita hodisa bir nechta ish bilan bog'langan.

5. Tarmoq diagrammasi tartibli bo'lishi kerak.

Boshlanishi boshlang'ich hodisaga to'g'ri keladigan va oxiri to'g'ri keladigan har qanday yo'l

tugatish to'liq yo'l deb ataladi. Maksimal bilan to'liq yo'l

ishning davomiyligi tanqidiy yo'l deb ataladi

Ierarxiya - bu tizim elementlarini bir-biriga bog'liq bo'lmagan to'plamlarga guruhlash mumkin degan taxminga asoslangan tizimning ma'lum bir turi.

Ierarxiyani tahlil qilish usulining tavsifi

Juftlik taqqoslash matritsalarini qurish

Lambda max ni toping va tizimni og'irliklar vektoriga nisbatan eching

Mahalliy ustuvorliklarning sintezi

Juftlik taqqoslash matritsalarining izchilligini tekshirish

Global ustuvorliklarning sintezi

Butun ierarxiyaning izchilligini baholash

Chiziqli dasturlash - bu o'zgaruvchilar va chiziqli optimallik mezoni o'rtasidagi chiziqli munosabat bilan tavsiflangan ekstremal muammolarni hal qilish usullarini o'rganadigan matematikaning bir bo'limi. Chiziqli dasturlash atamasi haqida bir necha so'z. Bu to'g'ri tushunishni talab qiladi. Bu holda dasturlash, albatta, kompyuter dasturlarini kompilyatsiya qilish emas. Bu erda dasturlashni rejalashtirish, rejalarni shakllantirish, harakatlar dasturini ishlab chiqish deb talqin qilish kerak. Chiziqli dasturlashning matematik muammolari ma'lum ishlab chiqarish va iqtisodiy vaziyatlarni o'rganishni o'z ichiga oladi, ular u yoki bu shaklda muammolar sifatida talqin qilinadi. optimal foydalanish cheklangan resurslar. Chiziqli dasturlash usullari yordamida hal qilinadigan masalalar doirasi ancha keng. Bu, masalan:

• - ishlab chiqarishni rejalashtirishda resurslardan optimal foydalanish muammosi;
• - aralashmalar haqidagi muammo (mahsulotlar tarkibini rejalashtirish);
• - omborlarda saqlash uchun har xil turdagi mahsulotlarning maqbul kombinatsiyasini topish muammosi (inventarizatsiyani boshqarish yoki "qo'l sumkasi muammosi");
• - transport vazifalari (korxona joylashuvi, tovarlar harakati tahlili). Chiziqli dasturlash matematik dasturlashning eng rivojlangan va keng qo'llaniladigan bo'limidir (bundan tashqari, bunga: butun, dinamik, chiziqli bo'lmagan, parametrik dasturlash kiradi). Bu quyidagicha izohlanadi:
• - ko'p sonli iqtisodiy masalalarning matematik modellari kerakli o'zgaruvchilarga nisbatan chiziqli;
• - bu turdagi muammolar hozirda eng ko'p o'rganilgan. Buning uchun maxsus usullar ishlab chiqilgan bo'lib, ular yordamida ushbu muammolar hal qilinadi va tegishli kompyuter dasturlari;
• - ko'plab chiziqli dasturlash masalalari hal qilinib, keng qo'llanilishini topdi;
• - dastlabki formulada chiziqli bo'lmagan ba'zi muammolar bir qator qo'shimcha cheklovlar va taxminlardan so'ng chiziqli bo'lib qolishi yoki chiziqli dasturlash usullari bilan echilishi mumkin bo'lgan shaklga keltirilishi mumkin. Har qanday chiziqli dasturlash masalasining iqtisodiy va matematik modeliga quyidagilar kiradi: optimal qiymati (maksimal yoki minimal) topilishi kerak bo'lgan maqsad funktsiyasi; chiziqli tenglamalar yoki tengsizliklar tizimi ko'rinishidagi cheklovlar; o'zgaruvchilarning manfiy emasligi talabi. Umuman olganda, model quyidagicha yozilgan:
• - maqsad funktsiyasi:

C1x1 + c2x2 + ... + cnxn > max(min);- cheklovlar:

a11x1 + a12x2 + ... + a1nxn (? = ?) b1,

a21x1 + a22x2 + ... + a2nxn (? = ?) b2

am1x1 + am2x2 + ... + amnxn (? = ?) bm;

Salbiy bo'lmaganlik talabi:

Bunda aij, bi, cj () doimiy qiymatlar beriladi. Muammo (2.2) va (2.3) cheklovlarga taalluqli (2.1) funksiyaning optimal qiymatini topishdir. Cheklovlar sistemasi (2.2) masalaning funksional cheklovlari, (2.3) cheklovlar esa to'g'ridan-to'g'ri deyiladi. (2.2) va (2.3) cheklovlarni qanoatlantiradigan vektor chiziqli dasturlash masalasining ruxsat etilgan yechimi (rejasi) deyiladi. Funktsiya (2.1) maksimal (minimal) qiymatiga erishadigan reja optimal deb ataladi.

Quyida chiziqli dasturlash usullari yordamida hal qilinadigan ba'zi tipik masalalarga misollar keltiramiz. Bunday vazifalar real iqtisodiy mazmunga ega. Endi biz ularni faqat PLP nuqtai nazaridan shakllantiramiz va quyida bunday muammolarni hal qilish usullarini ko'rib chiqamiz.

1. Ishlab chiqarishni rejalashtirishda resurslardan optimal foydalanish muammosi. Ushbu sinfdagi masalalarning umumiy ma'nosi quyidagilarga to'g'ri keladi. Kompaniya n xil mahsulot ishlab chiqaradi. Ularni ishlab chiqarish m xil turdagi resurslarni (xom ashyo, materiallar, ish vaqti va boshqalar) talab qiladi. Resurslar cheklangan, ularning reja davridagi zaxiralari mos ravishda b1, b2,..., bm shartli birliklardir. aij texnologik koeffitsientlari ham ma'lum bo'lib, ular j-turdagi () mahsulot birligini ishlab chiqarish uchun qancha i-resurs birligi kerakligini ko'rsatadi. Korxonaning j-turdagi mahsulotni sotishdan olgan foydasi cj ga teng. Rejalashtirish davrida aij, bi va cj qiymatlari doimiy bo'lib qoladi. Korxona foydasi eng yuqori bo'lgan ishlab chiqarish rejasini tuzish kerak. Quyida biz ushbu sinf muammosiga oddiy misol keltiramiz.

Korxona xokkey tayoqlari va shaxmat to'plamlari ishlab chiqarishga ixtisoslashgan. Har bir tayoq kompaniyaga 2 dollar, har bir shaxmat to‘plami esa 4 dollar foyda keltiradi. Har bir tayoq uchun A saytida to'rt soatlik va B saytida ikki soatlik ish kerak bo'ladi. Shaxmat to'plami A maydonida olti soat, B saytida olti soat va C saytida bir soat ishlab chiqariladi. Mavjud ishlab chiqarish A uchastkasining quvvati kuniga 120 n-soat, B uchastkasi - 72 n-soat va C uchastkasi - 10 n-soat. Maksimal foyda olish uchun kompaniya kuniga qancha klub va shaxmat to'plami ishlab chiqarishi kerak?

Belgilangan sinf muammolarining shartlari ko'pincha taqdim etiladi jadval shakli(2.1-jadvalga qarang).

Ushbu shartdan foydalanib, chiziqli dasturlash masalasini tuzamiz. Belgilaymiz: x1 - har kuni ishlab chiqarilgan xokkey tayoqlari soni, x2 - har kuni ishlab chiqarilgan shaxmat to'plamlari soni. PPPni shakllantirish:

4x1 + 6x2? 120,

Shuni ta'kidlab o'tamizki, funktsional cheklovlar tizimidagi har bir tengsizlik bu holda u yoki bu ishlab chiqarish maydonchasiga mos keladi, ya'ni: birinchisi - A uchastkasiga, ikkinchisi - B uchastkasiga, uchinchisi - C uchastkasiga.

Almashlab ekishni hisobga olgan holda ekin maydonlari strukturasini optimallashtirish muammosidagi o‘zgaruvchilar tizimi

Keling, asosiy chiziqli dasturlash muammosini (LPLP) ko'rib chiqaylik: x1, x2, ..., xn o'zgaruvchilarning manfiy bo'lmagan qiymatlarini toping, m shartlarni - tenglikni qondiring.

va bu o'zgaruvchilarning chiziqli funktsiyasini maksimallashtirish

Oddiylik uchun biz barcha shartlarni (1) chiziqli mustaqil (r=m) deb hisoblaymiz va biz o'z fikrimizni shu faraz asosida olib boramiz.

OLP ning ruxsat etilgan yechimini (1) shartlarni qondiradigan har qanday manfiy bo'lmagan qiymatlar to'plamini (2) ruxsat etilgan echimlardan biri deb ataymiz. Biz optimal yechim topishimiz kerak.

Bu muammo har doim yechimga egami? Yo'q, har doim emas.

ZLP hal etilmaydi (optimal yechim yo'q):

Cheklash tizimining mos kelmasligi tufayli. Bular. tizimda 1-rasmda ko'rsatilganidek, yagona yechim yo'q.

1-rasm - Cheklovlar tizimining nomuvofiqligi

Yechimlar to'plamida maqsad funktsiyasining cheksizligi tufayli. Boshqacha qilib aytganda, LLP ni maxda yechishda maqsad funksiyaning qiymati 2-rasmda ko'rsatilganidek, cheksizlikka, LLP esa min da - minus cheksizlikka intiladi.

2-rasm - Yechimlar to'plamidagi maqsad funktsiyasining cheksizligi

ZLP hal qilinishi mumkin:

Yechimlar to'plami bitta nuqtadan iborat. 3-rasmda ko'rsatilganidek, u ham optimal hisoblanadi.

3-rasm - Yechimlar to'plami bir nuqtadan iborat

Yagona optimal PPP qarori. Chegara holatidagi maqsad funksiyasiga mos keladigan to‘g‘ri chiziq yechimlar to‘plami bilan 4-rasmda ko‘rsatilganidek, bir nuqtada kesishadi.

4-rasm - yagona optimal yechim

ZLP ning optimal yechimi yagona emas. N vektor yechimlar to'plamining tomonlaridan biriga perpendikulyar. Bunda 5-rasmda ko'rsatilganidek, AB segmentidagi istalgan nuqta optimal hisoblanadi.

5-rasm - Optimal yechim yagona emas

Simpleks usuli yordamida chiziqli dasturlash masalalarini yechish

Simpleks usuli - LP muammosini hal qilish algoritmi bo'lib, u C maqsad funktsiyasining qiymatini yaxshilash yo'nalishi bo'yicha amalga oshirilishi mumkin bo'lgan echimlar mintaqasining burchak nuqtalarini sanashni amalga oshiradi. Simpleks usuli chiziqli dasturlashda asosiy hisoblanadi.

LP muammosini hal qilish uchun bitiruv loyihasida ushbu usuldan foydalanish quyidagi omillar bilan bog'liq:

Usul universal bo'lib, kanonik shakldagi har qanday chiziqli dasturlash masalasiga qo'llaniladi;

Usulning algoritmik xususiyati uni texnik vositalar yordamida muvaffaqiyatli dasturlash va amalga oshirish imkonini beradi.

Maqsad funksiyasining ekstremumiga har doim mumkin bo'lgan echimlar mintaqasining burchak nuqtalarida erishiladi. Avvalo, ba'zi bir mumkin bo'lgan boshlang'ich (mos yozuvlar) yechim topiladi, ya'ni. mumkin bo'lgan echimlar mintaqasining istalgan burchak nuqtasi. Usulning protsedurasi ushbu yechimning maqbulmi degan savolga javob berishga imkon beradi. Ha bo'lsa, muammo hal qilingan. Agar "yo'q" bo'lsa, maqsadga muvofiq echimlar mintaqasining qo'shni burchak nuqtasiga o'tish amalga oshiriladi, bu erda maqsad funktsiyasining qiymati yaxshilanadi. Mumkin yechimlar mintaqasining burchak nuqtalarini sanash jarayoni maqsad funksiyaning ekstremumiga mos keladigan nuqta topilguncha takrorlanadi.

Ko'pburchakning uchlari soni cheklanganligi sababli, cheklangan miqdordagi qadamlarda optimal qiymatni topish yoki muammoni hal qilib bo'lmaydigan faktni aniqlash kafolatlanadi.

Bu yerda cheklovlar tizimi chiziqli tenglamalar tizimi bo'lib, unda noma'lumlar soni tenglamalar sonidan kattaroqdir. Agar tizimning darajasi teng bo'lsa, u holda qolgan noma'lumlar bilan ifodalangan noma'lumlarni tanlash mumkin. Ishonch hosil qilish uchun, odatda, birinchi navbatdagi noma'lumlar tanlangan deb taxmin qilinadi. Ushbu noma'lumlar (o'zgaruvchilar) asosiy deb ataladi, qolganlari bepul. Asosiy o'zgaruvchilar soni har doim cheklovlar soniga teng.

Erkin o'zgaruvchilarga ma'lum qiymatlarni belgilash va asosiy qiymatlarni hisoblash (erkin bo'lganlar bilan ifodalangan) orqali cheklovlar tizimi uchun turli xil echimlar olinadi. Erkin o'zgaruvchilar nolga teng bo'lgan holatda olingan echimlar alohida qiziqish uyg'otadi. Bunday echimlar asosiy deb ataladi. Asosiy yechim, agar uning o'zgaruvchilari qiymatlari manfiy bo'lmasa, ruxsat etilgan asosiy yechim yoki mos yozuvlar yechim deb ataladi. U barcha cheklovlarga javob beradi.

Cheklovlar tizimiga ega bo'lgan holda, ushbu tizimning har qanday asosiy echimi topiladi. Agar topilgan birinchi asosiy yechim mumkin bo'lsa, u holda uning optimalligi tekshiriladi. Agar u optimal bo'lmasa, boshqa amalga oshirilishi mumkin bo'lgan asosiy echimga o'tish amalga oshiriladi.

Simpleks usuli ushbu yangi yechim bilan chiziqli shakl, agar u optimalga erishmasa, unga yaqinlashishini kafolatlaydi. Ular eng maqbul yechim topmaguncha, yangi mumkin bo'lgan asosli yechim bilan ham xuddi shunday qilishadi.

Agar topilgan birinchi asosiy yechim nomaqbul boʻlib chiqsa, u holda simpleks usulidan foydalanib, boshqa asosiy yechimlarga oʻtish amalga oshiriladi, toki yechimning qaysidir bosqichida asosiy yechim maqbul boʻlib chiqmagunicha yoki nomuvofiqlik haqida xulosa chiqarish mumkin boʻladi. cheklovlar tizimi.

Shunday qilib, simpleks usulini qo'llash ikki bosqichga bo'linadi:

Cheklovlar tizimiga maqbul asosiy yechim topish yoki uning nomuvofiqligi faktini aniqlash;

Cheklashlar sistemasi mos kelsa optimal yechim topish.

Keyingi mumkin bo'lgan yechimga o'tish algoritmi quyidagicha:

Maqsad funksiyasining koeffitsientlari qatorida maksimalni topishda eng kichik manfiy son tanlanadi. Koeffitsientning seriya raqami . Agar yo'q bo'lsa, unda asl asosiy yechim maqbuldir;

Ustun raqami bo'lgan matritsaning elementlari orasida (bu ustun etakchi yoki hal qiluvchi ustun deb ataladi) ijobiy elementlar tanlanadi. Agar ular bo'lmasa, maqsad funktsiyasi o'zgaruvchilarning ruxsat etilgan qiymatlari oralig'ida cheksizdir va muammoning echimi yo'q;

Matritsaning etakchi ustunining tanlangan elementlari orasida tegishli bo'sh atamaning ushbu elementga nisbati qiymati minimal bo'lgan element tanlanadi. Bu element yetakchi, u joylashgan chiziq esa yetakchi deyiladi;

Etakchi elementning qatoriga mos keladigan asosiy o'zgaruvchini erkin toifaga o'tkazish kerak va asosiy elementning ustuniga mos keladigan erkin o'zgaruvchini asosiylar soniga kiritish kerak. Asosiy o'zgaruvchilarning yangi raqamlarini o'z ichiga olgan yangi yechim tuziladi.

Muammoni maksimal darajada echishda rejaning optimalligi sharti: maqsad funktsiyasi koeffitsientlari orasida salbiy elementlar mavjud emas.

Tanlov