n o‘lchovli fazoning har bir nuqtasi (x 1 ,x 2 ,…x n) bilan R n o‘lchamli vektorni bog‘laymiz. x=(x 1 ,x 2 ,…x n) boshi boshida va oxiri nuqtada (x 1 ,x 2 ,…x n). Ko'p vektorlar X R n da =(x 1,x 2,...x n) komponentlari m chiziqli tengsizlikni qanoatlantiradi:
A 11 x 1 +a 12 x 2 +...+a 1 n x n ≤ b 1
a 21 x 1 +a 22 x 2 +...+a 2 n x n ≤ b 2
. . . . . . . . . . . . (2)
a m 1 x 1 +a m 2 x 2 +...+a m n x n ≤ b m
sistemaning yechimlar to'plami deyiladi chiziqli tengsizliklar.
Ta'rifda barcha tengsizliklar ≤ belgisi bilan yoziladi. ga ko'paytirish
(-1) har qanday tengsizlik, siz uning belgisini teskarisiga o'zgartirishingiz mumkin. ³ va ≤ belgisi bilan chiziqli tengsizliklar sistemalari uchun yechimlar to'plami aniqlanadi.
Modellashtirish muammolari
Modellashtirish nazariyasining predmeti
Modellashtirish - bu bir ob'ektni (asl nusxani) boshqasiga (model) almashtirish va modelning xususiyatlarini aniqlash va o'rganish. Buning uchun almashtirish amalga oshiriladi soddalashtirish, tannarxni pasaytirish, asl nusxaning xususiyatlarini o'rganishni jadallashtirish.
IN umumiy holat asl ob'ekt tabiiy yoki sun'iy, haqiqiy yoki xayoliy tizim bo'lishi mumkin. U juda ko'p parametrlarga ega va ma'lum xususiyatlar bilan tavsiflanadi. Tizim xususiyatlarining miqdoriy o'lchovi ko'plab xususiyatlar bilan ta'minlanadi, tizim tashqi ta'sirlar ta'sirida o'z xususiyatlarini namoyon qiladi.
Ko'pgina parametrlar va ularning qiymatlari uning ichki qismini aks ettiradi tarkib - tuzilish va ishlash tamoyillari. Xususiyatlari asosan unga xosdir tashqi belgilar boshqalar bilan muloqot qilishda muhim ahamiyatga ega.
Agar modelda asl nusxani o'rganishga xalaqit beradigan xususiyatlar mavjud bo'lmasa, modellashtirish tavsiya etiladi.
Modellashtirish nazariyasi - bu modellarni yaratish qoidalari, ta'riflari, usullari va vositalarining o'zaro bog'liq to'plami. Modellarning o'zi modellashtirish nazariyasining predmeti hisoblanadi.
Modellashtirish nazariyasi asosiy komponent hisoblanadi umumiy nazariya tizimlar - tizimologiya, bu erda amalga oshirilishi mumkin bo'lgan modellar asosiy printsip sifatida qabul qilinadi: tizim har biri uning mohiyatining ma'lum bir tomonini aks ettiruvchi cheklangan modellar to'plami bilan ifodalanishi mumkin.
Tizimli tadqiqotlarda modellashtirishning roli va o'rni.
Har qanday tizimni bilish () asosan uning modelini yaratishga to'g'ri keladi. Har bir qurilma yoki strukturani ishlab chiqarishdan oldin uning model-loyihasi ishlab chiqiladi. Har qanday san’at asari voqelikni aks ettiruvchi namunadir.
Matematikaning yutuqlari turli ob'ektlar va jarayonlarning matematik modellarining tarqalishiga olib keldi. Ta'kidlanishicha, turli jismoniy tabiatga ega tizimlarning ishlash dinamikasi bir xil turdagi bog'liqliklarga ega, bu esa ularni shaxsiy kompyuterda taqlid qilish imkonini beradi.
Model tasnifi
Jismoniy modellar. Tasniflash modelning asl nusxadan mavhumlik darajasiga asoslanadi. Ilgari barcha modellarni 2 guruhga bo'lish mumkin - jismoniy va mavhum (matematik).
F.M. odatda ekvivalent yoki asliga o'xshash, lekin ehtimol boshqa jismoniy tabiatga ega bo'lgan tizimni nazarda tutadi. F.M. turlari:
Tabiiy;
Kvazi-tabiiy;
Katta o'lchamli;
Analog;
Tabiiy modellar- bu o'rganilayotgan haqiqiy tizimlar (modellar, prototiplar). Ular asl tizim bilan to'liq muvofiqligi (yozuvlari) bor, lekin qimmat.
Kvazi-tabiiy modellar- tabiiy va matematik modellar to'plami. Ushbu turdagi tizimning bir qismi modeli uning tavsifining murakkabligi (inson operatori modeli) tufayli matematik bo'lishi mumkin bo'lmaganda yoki tizimning bir qismini boshqa qismlar bilan o'zaro aloqada o'rganish kerak bo'lganda, lekin ular hali mavjud bo'lmaganda yoki ularning kiritish juda qimmat (hisoblash poligonlari , ACS).
Masshtabli model - bu asliyat bilan bir xil fizik tabiatga ega bo'lgan tizim, lekin undan masshtab jihatidan farq qiladi. Uslubiy asos masshtabli modellashtirish - o'xshashlik nazariyasi. Samolyotlarni loyihalashda miqyosli modellar joylashtirish echimlari variantlarini tahlil qilish uchun ishlatilishi mumkin.
Analog modellar fizik tabiati asl nusxadan farq qiladigan, lekin ishlash jarayonlari asl nusxaga o'xshash tizimlar deyiladi. Analog modelni yaratish uchun o'rganilayotgan tizimning matematik tavsifi talab qilinadi. Analog modellar sifatida mexanik, gidravlik, pnevmatik va elektr tizimlari qo'llaniladi. Analog modellashtirish VT uskunalarini mantiqiy elementlar darajasida o'rganishda qo'llaniladi va elektr zanjirlari, shuningdek, tizim darajasida, tizimning ishlashi, masalan, differentsial yoki algebraik tenglamalar bilan tavsiflanganda.
Matematik modellar. Matematik modellar - tizimning ishlash jarayonini aks ettiruvchi matematik munosabatlardan foydalangan holda, mavhum til yordamida tizimning rasmiylashtirilgan tasviri. Matematik modelni tuzish uchun har qanday matematik vositalardan - algebraik, differentsial, integral hisob, to'plam nazariyasi, algoritmlar nazariyasi va boshqalardan foydalanish mumkin. Umuman olganda, barcha matematika ob'ektlar va jarayonlarning modellarini yig'ish va o'rganish uchun yaratilgan.
Tizimlarni mavhum tavsiflash vositalariga tillar ham kiradi kimyoviy formulalar, diagrammalar, chizmalar, xaritalar, diagrammalar va boshqalar. Model turini tanlash o'rganilayotgan tizimning xususiyatlari va modellashtirish maqsadlari bilan belgilanadi, chunki Modelni o'rganish ma'lum bir guruh savollariga javob olish imkonini beradi. Turli xil ma'lumotlarni olish uchun turli xil ma'lumotlar boshqa turdagi modelni talab qilishi mumkin. Matematik modellarni deterministik va ehtimolli, analitik, raqamli va simulyatsiyaga bo'lish mumkin.
Analitik model Bu taniqli matematik apparat yordamida tenglamani aniq yechish imkonini beruvchi tizimning rasmiylashtirilgan tavsifi.
Raqamli model muayyan boshlang'ich shartlar va modellarning miqdoriy parametrlari uchun faqat qisman echimlarga imkon beradigan turga bog'liqlik bilan tavsiflanadi.
Simulyatsiya modeli- bu tizimning tavsiflari va tashqi ta'sirlar, tizimning ishlashi uchun algoritmlar yoki tashqi va ichki buzilishlar ta'sirida tizim holatini o'zgartirish qoidalari. Ushbu algoritmlar va qoidalar mavjud matematik usullardan analitik va raqamli yechim, lekin ular tizimning ishlash jarayonini simulyatsiya qilish va qiziqish xususiyatlarini hisoblash imkonini beradi. Simulyatsiya modellari analitik va raqamlilarga qaraganda ancha kengroq ob'ektlar va jarayonlar sinfi uchun yaratilishi mumkin. Kompyuterlar simulyatsiya modellarini amalga oshirish uchun ishlatilganligi sababli, universal va maxsus algoritmik tillar ularni rasmiylashtirilgan tavsiflash vositasi bo'lib xizmat qiladi. Ular samolyotlarni tizim darajasida o'rganish uchun eng mos keladi.
Chiziqli tengsizliklar sistemasini yechish sohasini topish zarur bo'lgan bir qancha masalalarni ko'rib chiqamiz.
1-misol:
X 1 + 3x 2 ≤ 6
x 1 - x 2 ≤ 2
Kerakli echimlar to'plami soyali maydonga mos keladi. Yechimlar to'plamining uchlari uch nuqta (0,2), (0,-2) va (3,1). Ular yechimlar to'plamini cheklovchi chiziqlarning kesishish nuqtalari.
Bu misolda yechim to'plami ko'pburchakli qavariq to'plamdir.
2-misol: Quyidagi chiziqli tengsizliklar sistemasining R² dagi yechimlar to‘plamini chizing.
X 1 + 2x 2 ≤ 4
3x 1 + 2x 2 ≤ 6
Kerakli to'plamning uchlari koordinatali ikkita nuqtadir: (0,2) va (1/2, 9/4). Koordinatasi (0,3) bo'lgan nuqta cho'qqi emas, chunki u birinchi tengsizlikni qanoatlantirmaydi. Ushbu yechimlar to'plami cheksizdir.
Yechim 3-misol: Quyidagi chiziqli tengsizliklar sistemasining R² dagi yechimlar to‘plamini chizing.
X 1 - x 2 ³ 1
x 1 + x 2 ≤ 1
Birinchi va ikkinchi tengsizliklarning yechimi soyali pastki sektorning nuqtalari hisoblanadi. Uchinchi tengsizlikning yechimi soyali yuqori yarim tekislikning nuqtalari hisoblanadi. Bu ikki sohaning umumiy nuqtalari yo'qligi sababli, butun tengsizliklar tizimining yechimi yo'q, ya'ni yechim Æ bo'ladi.
Chiziqli dasturlashning asosiy muammosi.
IN umumiy ko'rinish Chiziqli dasturlash muammosi (LPP) quyidagicha tuzilgan.
Vektor toping X=(x 1,x 2, ... x n) R n da, bu maqsad funksiyani maksimal darajaga keltiradigan (yoki minimallashtiradigan)
F(x)=s 1 x 1 +s 2 x 2 +... +s n x n (3)
va m+n chiziqli tengsizliklarni qanoatlantiradi:
A 11 x 1 +a 12 x 2 +...+a 1n x n ≤ b 1
a 21 x 1 +a 22 x 2 +...+a 2n x n ≤ b 2
. . . . . . . . . . . . (4)
a m1 x 1 +a m2 x 2 +...+a mn x n ≤ b m
x 1 ³0, x 2 ³0, ... x n ³0
Dasturlash terminologiyasida chiziqli F(x) funksiya masalaning maqsad funksiyasi deb ataladi. Chiziqli tengsizliklar sistemasi (4) yechimlari to‘plamiga ruxsat berilgan yechimlar to‘plami deyiladi va har qanday vektor X bu to'plamdan mumkin bo'lgan yechim deyiladi. Optimal yechim vektor hisoblanadi X*, bunda maqsad funktsiyasi ruxsat etilgan echimlar to'plamida o'zining maksimal (yoki minimal) qiymatini oladi.
Chiziqli dasturlash masalalarini echishning grafik usuli. Keling, bu masalani grafik (geometrik) usul yordamida qanday yechishini ko'rsatamiz. Buning uchun biz ikkita noma'lumli chiziqli tengsizliklar tizimini ko'rib chiqish bilan cheklanamiz.
F=c 1 x 1 +c 2 x 2 +c 0 maqsad funksiyasi berilsin. Keling, (x 1, x 2) nuqtalar to'plamidan (x 1, x 2) tengsizliklar qo'shma tizimining (4) ruxsat etilgan yechimlari hududidan (faqat x 1 va x 2 o'zgaruvchilarni o'z ichiga olgan) topamiz. chiziqli funksiya F - eng kichik (eng katta) qiymat. Tekislikning har bir i –chi nuqtasi uchun F funksiya F=F i sobit qiymatni oladi. F funksiya F i bir xil qiymatga ega bo‘lgan barcha shunday nuqtalar to‘plami 1 x 1 +c 2 x 2 +c 0 =F i = const bo‘lgan to‘g‘ri chiziq F gradienti (grad F) deb ataladigan qandaydir vektorga perpendikulyar. ). Bu vektor koordinatadan kelib chiqadi va F = (c 1,c 2) koordinatalariga ega. Grad F vektorining xossasiga ko'ra, agar ko'rsatilgan to'g'ri chiziq F vektorning musbat yo'nalishi bo'yicha o'ziga parallel ravishda o'tkazilsa, u holda maqsad funktsiyasining qiymati F=c 1 x 1 +c 2 x 2 +c bo'ladi. Bu to'g'ri chiziqda 0 ortadi, teskari yo'nalishda esa kamayadi.
F=const to‘g‘ri chiziq o‘z cho‘qqisida ruxsat etilgan yechimlar ko‘pburchagiga birinchi marta duch kelganida, grad F vektorining musbat yo‘nalishi bo‘yicha harakatlansin. U holda bu F 1 pozitsiyada F=const chizig'i tayanch chizig'i deb ataladi va bu chiziqda F funktsiyani oladi eng kichik qiymat. Xuddi shu yo'nalishda (musbat) keyingi harakat bilan F=const to'g'ri chiziq amalga oshirilishi mumkin bo'lgan echimlar ko'pburchagining boshqa cho'qqisidan o'tadi va yechim maydonidan chiqib, F 2 to'g'ri chiziqqa ham aylanadi. Unda F funksiya oladi eng yuqori qiymat mumkin bo'lgan echimlar poligonida qabul qilingan barcha qiymatlar orasida. Shunday qilib, F=c 1 x 1 +c 2 x 2 +c 0 maqsad funktsiyasini amalga oshirish mumkin bo'lgan echimlar ko'pburchagi bo'yicha minimallashtirish va maksimallashtirishga ushbu ko'pburchakning F=c 1 x 1 + etalon chiziqlari bilan kesishgan nuqtalarida erishiladi. c 2 x 2 +c 0 = const, vektorga normal grad F=(s 1 , s 2). Mumkin echimlar to'plami bilan mos yozuvlar chizig'ining bunday kesishishi bir nuqtada (ko'pburchakning cho'qqisida) yoki cheksiz nuqtalar to'plamida (agar bu ko'pburchak tomonlari to'plami bo'lsa) bo'lishi mumkin.
Birinchi, ikkinchi, uchinchi topshiriq uchun topshiriq talabaning familiyasi, ismi va otasining ismi bo‘yicha, to‘rtinchi vazifa uchun esa familiyasi va otasining ismi bo‘yicha tanlanadi.
Vazifa № 1
1-jadval
| Birinchi harf | Familiya | Ism | Familiya | ||||||||||||
| a 11 | a 12 | a 21 | a 2 2 | a 31 | a 32 | a 41 | a 4 2 | b 1 | b 2 | b 3 | C0 | C1 | C2 | ||
| A | |||||||||||||||
| B | |||||||||||||||
| IN | |||||||||||||||
| G | |||||||||||||||
| D | |||||||||||||||
| E | |||||||||||||||
| VA | |||||||||||||||
| Z | |||||||||||||||
| VA | |||||||||||||||
| TO | |||||||||||||||
| L | |||||||||||||||
| M | |||||||||||||||
| N | |||||||||||||||
| HAQIDA | |||||||||||||||
| P | |||||||||||||||
| R | |||||||||||||||
| BILAN | |||||||||||||||
| T | |||||||||||||||
| U | |||||||||||||||
| F | |||||||||||||||
| X | |||||||||||||||
| C | |||||||||||||||
| H | |||||||||||||||
| SE | |||||||||||||||
| YuYa | |||||||||||||||
4-misol: Cheklovlar ostida F=14x 1 +4x 2 chiziqli ko'rinishini minimallashtiring:
7x 1 + 2x 2 ³ 14
4 x 1 –7x 2 ≤ 14
Tengsizlik belgilarini aniq tenglik belgilari bilan almashtirib, mumkin bo'lgan echimlar mintaqasi chegaralari uchun tenglamalarni olamiz. Olingan to'g'ri chiziqlar tenglamalaridan foydalanib, biz kerakli maydonni quramiz:
7x 1 +2x 2 =14
4 x 1 – 7x 2 = 14
Tengsizliklar tizimining ruxsat etilgan yechimlari sohasi ABCDE ko'pburchakdir.
5-rasm.
Ekstremum nuqtalarni topish uchun F=14x 1 +4x 2 =0 to'g'ri chiziq va vektor gradF = (14, 4) quramiz. F=0 toʻgʻri chiziqni oʻziga parallel F vektor gradus yoʻnalishi boʻyicha olib boramiz. Bu chiziq birinchi navbatda ABCDE koʻpburchak bilan E(2,0) va A(10/9, 28/9) nuqtalarda uchrashadi, bu yerda. maqsad funksiya F(E) = F(A) =14·2+4∙0=28-min, (chunki vektor grad F AE to'g'ri chiziqqa perpendikulyar bo'lgani uchun) bir xil minimal qiymatni oladi. Shunday qilib, maqsad funktsiyasi AE segmentining istalgan nuqtasida minimal qiymatini oladi.
Rejadan 
asosiy chiziqli dasturlash muammosi shundan kelib chiqadiki, uning ijobiy komponentlari soni dan oshmaydi.
Qo'llab-quvvatlash rejasi, agar u aniq ijobiy komponentlarni o'z ichiga olgan bo'lsa, degenerativ bo'lmagan deb ataladi; aks holda reja buziladi.
Har qanday tizim o'zgaruvchilari chiziqli tenglamalar o'zgaruvchilar bilan (bo'ysungan holda) asosiy deyiladi, agar ular uchun koeffitsientlar matritsasining determinanti noldan farq qilsa. Keyin qolgan o'zgaruvchilar birlamchi bo'lmagan deb ataladi.
O'zgaruvchilari bo'lgan m chiziqli tenglamalar tizimining asosiy yechimi barcha asosiy bo'lmagan o'zgaruvchilar nol qiymatga ega bo'lgan har qanday yechimdir.
Teorema 1. Chiziqli dasturlash masalasining cheklashlar tizimining barcha mumkin bo'lgan yechimlari to'plami qavariqdir.
Teorema 2. Agar chiziqli dasturlash muammosi optimal yechimga ega bo'lsa, u holda mumkin bo'lgan echimlar to'plamining burchak nuqtasiga to'g'ri keladi.
Natija. Agar optimal yechim yagona bo'lmasa, unda bunday echimlar ko'p bo'ladi (masalan, tegishli burchak nuqtalarini bog'laydigan segmentning barcha nuqtalari).
Teorema 3. Chiziqli dasturlash masalasining har bir ruxsat etilgan asosiy yechimi ruxsat etilgan qiymatlar mintaqasining burchak nuqtasiga to'g'ri keladi va aksincha.
Simpleks usuli haqida tushuncha.
Asosiy chiziqli dasturlash masalasini geometrik usul yordamida yechish 2 va 3 o‘zgaruvchilar holatlarida katta ravshanlikka erishadi. Xuddi shu holat uchun Ko'proq o'zgaruvchilar, geometrik usul imkonsiz bo'ladi. Simpleks deb ataladigan usul chiziqli dasturlashning asosiy masalasini echishning analitik usullaridan biridir. Bunday holda, simpleks usulini amalga oshirishda qo'llaniladigan cheklovlar odatda chiziqli tenglamalar tizimi bilan belgilanadi
A 11 x 1 +a 12 x 2 +...+a 1n x n = b 1
a 21 x 1 +a 22 x 2 +...+a 2n x n = b 2
. . . . . . . . . . . . (5)
a m 1 x 1 +a m 2 x 2 +...+a mn x n = b m
manfiy bo'lmagan echimlar orasida biz chiziqli (ob'ektiv) funktsiyani maksimal darajada oshiradigan echimlarni qidiramiz.
F=s 1 x 1 +s 2 x 2 +...+s n x n +s 0
Simpleks usuli teoremalarga asoslanadi:
Teorema 1. Agar ZLP optimal yechimga ega bo'lsa, u holda maqsad funksiyasi mumkin bo'lgan echimlarning qavariq ko'pburchak burchak nuqtalaridan birida ekstremal qiymatni oladi.
Teorema 2. ZLP ning har bir qo'llab-quvvatlovchi yechimi mumkin bo'lgan echimlar poligonining burchak nuqtasiga to'g'ri keladi va aksincha.
Ushbu teoremalarga asoslanib, simpleks usulini amalga oshirishda, har bir keyingi cho'qqida maqsad funktsiyasining qiymati oldingi cho'qqidan kam bo'lmasligi uchun (ko'p bo'lmagan) barcha cho'qqilarni maqsadli qidirish amalga oshiriladi. Shu bilan birga, uchun yakuniy raqam qadamlar, kerakli optimal yechimga erishiladi yoki ZLP hal qilib bo'lmaydiganligi aniqlanadi.
Belgilangan algoritmni amalga oshirish uchun biz (5) max tizimida chiziqli mustaqil o'zgaruvchilar to'plamini tanlaymiz (ular uchun bu o'zgaruvchilar oldidagi koeffitsientlardan tashkil topgan determinant 0 dan farq qiladi). Aniqlik uchun bular x 1, x 2,... x r (r ≤ m) o‘zgaruvchilari bo‘lsin. Ushbu o'zgaruvchilarni qolgan o'zgaruvchilar bilan ifodalaymiz
X 1 = a" 1, r +1 x r+1 + ... + a" 1 n x n + b 1 "
x 2 = a" 2, r +1 x r+1 + ... + a" 2 n x n + b 2 "(6)
. . . . . . . . . . . . . . . .
x r = a" r, r +1 x r+1 + ... + a" r n x n + b r "
Bundan tashqari, biz barcha b 1 "³0, b 2 "³0, b r "³0 deb faraz qilamiz. Agar dastlabki cheklovchi shartlar tengsizliklar bilan aniqlangan bo'lsa, u holda ularni yangi manfiy bo'lmagan o'zgaruvchilarni kiritish orqali (5) ko'rinishga aylantirish mumkin, muvozanat (nivelirlash) deb ataladiganlar.Demak, masalan, 1 x 1 +a 2 x 2 +...+a n x n ≤ b tengsizlikda tengsizlikning chap tomoniga qandaydir x n + qiymatini qo‘shish kifoya. 1 ³ 0 tengsizlikning o'ng va chap tomonlari o'rtasidagi farqga teng bo'lib, a 1 x 1 + a 2 x 2 +…+a n x n + x n +1 = b tenglikni olamiz.Agar chegaralovchi shartlar aralash ko'rsatilgan bo'lsa. yo'l bilan, ya'ni tengsizliklar va tenglamalar orqali, keyin ko'rsatilgan usulda ularni faqat tenglamalarga keltirish mumkin.
Olingan sistemada (6) (noma'lum) o'zgaruvchilar x 1, x 2 ... x z asosiy, butun to'plam (x 1, x 2 ... x z) bazis, qolgan o'zgaruvchilar esa bepul deb ataladi. Cheklashlar tizimi (6) birlik asosiga qisqartirilgan tizim deyiladi. Maqsad funktsiyasi F ga asosiy o'zgaruvchilar o'rniga ularning ifodalarini (6) tizimdagi bo'sh o'zgaruvchilar orqali qo'yamiz.
F = C 0 + C g+1 x g+1 + … + C n x n
Endi, barcha bo'sh o'zgaruvchilar nolga teng deb faraz qilsak, biz asosiy o'zgaruvchilarning qiymatlarini topamiz:
x 1 =b 1 ", x 2 = b 2" , ... x r =b r "
Shu tarzda olingan tizimning (6) ruxsat etilgan yechimi
(b 1 ", b 2", ... b r ", 0, ... 0) asosiy deyiladi.Bu asosiy yechim uchun maqsad funksiyaning qiymati F B = C 0 ga teng bo'ladi.
Simpleks usuli yordamida masalani yechish bir qancha bosqichlarga bo‘linadi, ya’ni berilgan B asosdan biz F B ning yangi asosda qiymati oshib ketadigan yoki hech bo‘lmaganda boshqa B” asosiga o‘tamiz. , kamaymaydi, keyin bajariladi F B "≥ F B. Bundan tashqari, agar hammasi b 1 ">0, b 2 ">0,…., b r ">0 bo'lsa, bu yechim referent deb ataladi va ba'zilariga mos keladi. burchak nuqtasi mumkin bo'lgan echimlar maydoni cheklovlarning dastlabki tizimi bilan belgilanadi. Keyin bir asosiy (etalon) yechimdan ikkinchisiga o'tish mumkin bo'lgan yechimlar ko'pburchagining bir tepasidan boshqa cho'qqiga o'tishga to'g'ri keladi.
2-sonli topshiriq
Tovarlarning uch guruhini sotish uchun tijorat korxonasi , , birlik miqdoridagi uch turdagi organik moddiy va pul resurslariga ega. Shu bilan birga, 1 ming rubl uchun 1 guruh tovarlarni sotish uchun. tovar aylanmasi iste'moli birlik sonida, ikkinchi turdagi resurs birlik sonida, uchinchi turdagi resurs birlik sonida yo'qolgan. 1 ming rubl uchun 2 va 3 guruhli tovarlarni sotish uchun. tovar aylanmasi birinchi turdagi resursga muvofiq , birlik, ikkinchi turdagi resurslar , birlik miqdorida, uchinchi turdagi resurslar , birlik miqdorida sarflanadi. 1 ming rubl uchun uchta mahsulot guruhidan foyda. aylanmasi mos ravishda , , (ming rubl).
Savdo korxonasining foydasi maksimal bo'lishi uchun tovar aylanmasining rejalashtirilgan hajmi va tuzilishini aniqlang.
| Birinchi harf | Familiya | Ism | Familiya | ||||||||||||
| A | |||||||||||||||
| B | |||||||||||||||
| IN | 1 0 | ||||||||||||||
| G | |||||||||||||||
| D | |||||||||||||||
| E | |||||||||||||||
| VA | |||||||||||||||
| Z | |||||||||||||||
| VA | |||||||||||||||
| TO | |||||||||||||||
| L | |||||||||||||||
| M | |||||||||||||||
| N | |||||||||||||||
| HAQIDA | |||||||||||||||
| P | |||||||||||||||
| R | |||||||||||||||
| BILAN | |||||||||||||||
| T | |||||||||||||||
| U | |||||||||||||||
| F | |||||||||||||||
| X | |||||||||||||||
| C | |||||||||||||||
| H | |||||||||||||||
| SH E | |||||||||||||||
| Yu Ya |
5-misol: Cheklovlar ostida F=-x 4 +x 5 maqsad funksiyasini maksimal darajaga keltiring:
Ushbu tenglamalar tizimi izchil, chunki tizim matritsasining darajalari
va kengaytirilgan matritsa 
mos keladi va 3 ga teng. Asosiy o'zgaruvchilarni (birlik ustunlarida joylashgan) x 1, x 2, x 3, erkin o'zgaruvchilar x 4 va x 5 orqali ifodalab, biz tizimga kelamiz.
(7)
(7) sistemaga qo'shimcha ravishda biz asosiy o'zgaruvchilarni erkin o'zgaruvchilar orqali va maqsad funksiyada ifodalashimiz mumkin (bizning misolimizda F = -x 4 + x 5 allaqachon x 4 va x 5 erkin o'zgaruvchilar orqali ifodalangan). Endi x 4 = 0, x 5 =0 deb faraz qilsak, asosiy o'zgaruvchilarni topamiz: x 1 =1, x 2 =2, x 3 =3. Shunday qilib, tenglamalar tizimining birinchi mumkin bo'lgan bazis yechimi (1, 2, 3, 0, 0) dir. Ruxsat etilgan yechim topilganda maqsad funksiya F 0 qiymatiga ega bo'ladi, ya'ni F 1 =0.
Endi F 1 qiymatini oshirishga harakat qilaylik. X 4 ning oshishi F 1 ni kamaytiradi, chunki F = -x 4 + x 5 ifodasida x 4 dan oldin manfiy koeffitsient mavjud va x 5 ning ortishi F 1 ning o'sishini beradi. Shuning uchun, x 1, x 2, x 3 manfiy bo'lmasligi uchun x 5 ni oshiramiz, x 4 = 0 ni qoldiramiz. Ikkinchi tenglamadan (7) biz x 5 ni 2 ga oshirish mumkinligini ko'ramiz (shunday qilib, x 2 0 bo'lib qoladi, x 4 = 0 bilan). Keyin o'zgaruvchilarning qiymati (5, 0, 1, 0, 2) va F qiymati 2 = 2 bo'ladi. Ko'rib turganingizdek, F qiymati ikkinchi bosqichda ortdi.
X 2 va x 4 0 ga teng bo'lganligi sababli, biz x 2 va x 4 ni erkin noma'lum sifatida qabul qilamiz, keyin x 5 = 2x 2 + 2x 4
va (7) tizimdan biz uning ekvivalent tizimiga (8) o'tamiz.
(8)
Bundan tashqari, bu holda F teng bo'ladi
F = 2x 2 + x 4
F ni oshirish uchun biz x 4 ni oshiramiz (chunki x 2 dan oldin manfiy koeffitsient mavjud) (8) sistemaning ikkinchi tenglamasidan ma'lum bo'ladiki, x 3 manfiy bo'lmasa, x 4 qiymati bo'lishi mumkin. x 4 = 1/5 ga keltirilsa, bizda (28/5 , 0, 0, 1/5, 12/5), F 3 =11/5 ga ega bo'lamiz.
Olingan yechim x 2 = x 3 = 0 ekan, biz x 2 va x 3 ni erkin o'zgaruvchilar sifatida qabul qilamiz va x 1, x 4, x 5 ni x 2 va x 3 orqali ifodalaymiz.
X 1 = 28/5 - 7/5 x 2 - 3/5 x 3
x 4 = 1/5 + 1/5 x 2 - 1/5 x 3
x 5 = 12/5 – 3/5 x 2 – 2/5 x 3
F = 11/5 - 4/5 x 2 - 1/5 x 3 bilan
F ifodasidagi x 2 va x 3 koeffitsientlari manfiy bo'lgani uchun endi F qiymatini oshirish mumkin emas. Shuning uchun, x 2 = x 3 = 0 qo'yib, biz yechishda eng katta F = 11/5 qiymatini olamiz (28/5, 0, 0, 1/5, 12/5)
Javob: F max = 11/5 at X* = (28/5, 0, 0, 1/5, 12/5)
Simpleks jadvallar.
Oldingi misolda bo'lgani kabi, ZLP ni bunday mulohazalardan foydalanib echish, yechimni ixcham yozib olish uchun aniq noqulay bo'lganligi sababli, kompyuterda yechim algoritmini dasturlash uchun simpleks deb ataladigan jadvallar qo'llaniladi. Buning uchun biz cheklovlar tizimini birlik asosiga qisqartiramiz
x 1 + a 1, r +1 x r+1 + ... + a 1 n x n = b 1
x i + a i,r+1 x r+1 + .... + a i n x n = b i (9)
x r + a r,r+1 x r+1 + ... + a r n x n = b r
va maqsad funktsiyasi F - shaklga:
F = C g+1 x r +1 + ... + C j x j +…+ C n x n + C 0 (10)
Tenglikni (10) F funksiyasi va C j koeffitsientlari uchun qisqartirilgan (erkin o'zgaruvchilarga) ifoda deb ataymiz - mos keladigan erkin o'zgaruvchilarning x j baholari (indekslari).
Yuqoridagi cheklovlar tizimining koeffitsientlari (9), shuningdek, turli xil yordamchi o'zgaruvchilar simpleks jadvaliga kiritilgan (1-jadval).
1-jadval
| Asosiy o'zgaruvchilar | Bepul a'zolar | x 1 | ... | x i | ... | x r | x g+1 | ... | x j | ... | x n | |
| x 1 | b 1 | ... | ... | a 1,r+1 | ... | a 1j | ... | a 1n | ||||
| ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ||
| x i | b i | ... | ... | va i,r+1 | ... | a ij | ... | a in | ||||
| ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | |
| x r | b r | ... | ... | va r,r+1 | ... | a rj | ... | arn | ||||
| F= | C 0 | ... | ... | - C g+1 | ... | -C j | ... | -Cn |
Noma'lum x i bo'lgan birinchi r ustunlar asosiy o'zgaruvchilari x 1 ,…,x r bo'lgan birlik ustunlaridir. Keyingi n-r ustunlar x r +1 ,…,x n erkin o'zgaruvchilarga ega ustunlardir. Erkin o'zgaruvchilarni x r +1 = …= deb hisoblaymiz
X n = 0, biz x 1 = b 1,…, x r = b r asosiy o'zgaruvchilarni topamiz. Bunda maqsad funksiyaning qiymati F = C 0 ga teng.
Topilgan vektor rejasi X 1 = va maqsad funktsiyasining qiymati F = C 0 amalga oshirilishi mumkin bo'lgan echimlar ko'pburchagining ba'zi cho'qqilariga mos keladi. Boshqa cho'qqiga o'tish va shunga ko'ra, boshqa vektor rejasiga va maqsad funktsiyasining boshqa qiymatiga o'tish ushbu simpleks jadvalini qayta hisoblash orqali amalga oshiriladi.
CHIZIQLI TENGLAMALAR VA TENGSIZLIKLAR I
§ 23 Chiziqli tengsizliklar sistemalari
Chiziqli tengsizliklar tizimi - bir xil noma'lum miqdorni o'z ichiga olgan ikki yoki undan ortiq chiziqli tengsizliklarning har qanday to'plami.
Bunday tizimlarga misol sifatida quyidagi tizimlar kiradi:
Tengsizliklar tizimini yechish deganda tizimning har bir tengsizligi qondiriladigan noma’lum miqdorning barcha qiymatlarini topish tushuniladi.
Keling, yuqoridagi tizimlarni hal qilaylik.
Ikki son qatorni bir-birining ostiga joylashtiramiz (31-rasm); tepada biz ushbu qiymatlarni belgilaymiz X , buning uchun birinchi tengsizlik qanoatlantiriladi ( X > 1) va pastki qismida bu qiymatlar X , buning uchun ikkinchi tengsizlik qanoatlantiriladi ( X > 4).
Natijalarni raqam chiziqlaridagi taqqoslaganda, ikkala tengsizlik bir vaqtning o'zida qanoatlantirilishini ko'ramiz. X > 4. Javob, X > 4.
Birinchi tengsizlik -3 ni beradi X < -б, или X > 2, ikkinchisi - X > -8 yoki X < 8. Далее поступаем так же, как и в первом примере. На одной числовой прямой отмечаем все те значения X , buning uchun tizimning birinchi tengsizligi qanoatlantiriladi va ikkinchi raqam chizig'ida birinchisi ostida joylashgan barcha qiymatlar X , buning uchun tizimning ikkinchi tengsizligi qanoatlantiriladi (32-rasm).
Ushbu ikki natijani taqqoslash shuni ko'rsatadiki, ikkala tengsizlik bir vaqtning o'zida barcha qiymatlar uchun amal qiladi X , 2 dan 8 gacha o'ralgan. Bunday qiymatlar to'plami X qo'sh tengsizlik sifatida yoziladi 2< X < 8.
3-misol. Tengsizliklar sistemasini yeching
Tizimning birinchi tengsizligi 5 ni beradi X < 10, или X < 2, второе X > 4. Shunday qilib, ikkala tengsizlikni bir vaqtda qanoatlantiradigan har qanday son 2 dan va 4 dan ko'p bo'lmasligi kerak (33-rasm).
Ammo bunday raqamlar mavjud emas. Shuning uchun bu tengsizliklar tizimi hech qanday qiymatlar uchun amal qilmaydi X . Bunday tengsizliklar sistemalari nomuvofiq deyiladi.
Mashqlar
Ushbu tengsizliklar sistemasini yeching (No 179 -184):
Tengsizliklarni yeching (No 185, 186):
185. (2X + 3) (2 - 2X ) > 0. 186. (2 - π ) (2X - 15) (X + 4) > 0.
Toping haqiqiy qiymatlar tenglik ma'lumotlariga kiritilgan harflar (№ 187, 188):
Tengsizliklarni yeching (No 189, 190):
189. 1 < 2X - 5 < 2. 190. -2 < 1 - Oh < 5.
191. 15° haroratdagi 6 litr suv bilan kamida 30° haroratli va 40° dan yuqori boʻlmagan suv olish uchun 10 litr suvning harorati qanday boʻlishi kerak?
192. Uchburchakning bir tomoni 4 sm, qolgan ikkitasining yig’indisi 10 sm.Bu tomonlar butun sonlarda ifodalangan bo’lsa, toping.
193. Ma'lumki, ikkita chiziqli tengsizliklar tizimi noma'lum miqdorning hech qanday qiymatlari uchun qanoatlanmaydi. Ushbu tizimning individual tengsizliklari noma'lum miqdorning har qanday qiymatlari uchun qanoatlanmaydi, deb ayta olamizmi?
Grafik usul.. 3
Simpleks usuli.. 6
Sun'iy asos usuli... 8
Ikkilik tamoyili.. 10
Foydalanilgan adabiyotlar ro‘yxati... 12
Kirish
Chiziqli tengsizliklar sistemalarining ayrim xossalari 19-asrning birinchi yarmida analitik mexanikaning ayrim muammolari bilan bogʻliq holda koʻrib chiqilgan. Chiziqli tengsizliklar tizimlarini tizimli o'rganish 19-asrning oxirida boshlangan, ammo chiziqli tengsizliklar nazariyasi haqida faqat 20-asrning 20-yillari oxirida, ular bilan bog'liq etarli miqdordagi natijalar mavjud bo'lganda gapirish mumkin bo'ldi. allaqachon to'plangan.
Endi chiziqli tengsizliklarning chekli tizimlari nazariyasini chiziqli algebraning bir tarmog'i deb hisoblash mumkin, u koeffitsientlar maydonini tartiblashning qo'shimcha talabi bilan paydo bo'lgan.
Ayniqsa, chiziqli tengsizliklar muhim iqtisodchilar uchun, chunki chiziqli tengsizliklar yordamida ishlab chiqarish jarayonlarini modellashtirish va ishlab chiqarish, tashish, resurslarni taqsimlash va hokazolarning eng foydali rejalarini topish mumkin.
Ushbu maqolada aniq muammolarga qo'llaniladigan chiziqli tengsizliklarni echishning asosiy usullari ko'rsatilgan.
Grafik usul
Grafik usul PLP uchun ruxsat etilgan echimlar to'plamini qurish va bu to'plamda maks/min maqsad funktsiyasiga mos keladigan nuqtani topishdan iborat.
Munosabati bilan nogironlar vizual grafik tasvir uchun bu usul faqat ikkita noma'lumli chiziqli tengsizliklar tizimlari va ushbu shaklga tushirilishi mumkin bo'lgan tizimlar uchun qo'llaniladi.
Aniq ko'rsatish uchun grafik usuli, keling, quyidagi muammoni hal qilaylik:
- Birinchi bosqichda amalga oshirilishi mumkin bo'lgan echimlar hududini qurish kerak. Bu misol uchun abscissa sifatida X2 ni, ordinata sifatida X1 ni tanlash va tengsizliklarni quyidagi shaklda yozish eng qulaydir:
Grafiklar ham, mumkin bo'lgan echimlar maydoni ham birinchi chorakda. Chegara nuqtalarini topish uchun (1)=(2), (1)=(3) va (2)=(3) tenglamalarni yechamiz.
Rasmdan ko'rinib turibdiki, ABCDE ko'pburchaklari mumkin bo'lgan yechimlar mintaqasini tashkil qiladi.
Agar amalga oshirish mumkin bo'lgan yechimlar hududi yopiq bo'lmasa, u holda max(f)=+ ∞ yoki min(f)= -∞ bo'ladi.
- Endi f funktsiyaning maksimalini to'g'ridan-to'g'ri topishga o'tishimiz mumkin.
Ko‘pburchak uchlari koordinatalarini f funksiyaga almashtirib, qiymatlarni taqqoslab, shuni topamizki,
f(C)=f(4;1)=19 – funksiyaning maksimali.
Ushbu yondashuv oz sonli uchlari bilan juda foydali. Ammo juda ko'p tepaliklar mavjud bo'lsa, bu protsedura uzoq vaqt talab qilishi mumkin.
Bunda f=a ko'rinishdagi sath chizig'ini ko'rib chiqish qulayroqdir. a sonining -∞ dan +∞ gacha monotonik ortishi bilan f=a to'g'ri chiziqlar normal vektor bo'ylab siljiydi. Agar daraja chizig'ining bunday harakati bilan ma'lum bir X nuqta - amalga oshirilishi mumkin bo'lgan echimlar mintaqasining birinchi umumiy nuqtasi (ABCDE ko'p yuzli) va sath chizig'i mavjud bo'lsa, u holda f (X) to'plamdagi f ning minimal qiymatidir. ABCDE. Agar X sath chizig'i va ABCDE to'plamining oxirgi kesishish nuqtasi bo'lsa, u holda f(X) mumkin bo'lgan echimlar to'plamidagi maksimaldir. Agar a→-∞ sifatida f=a to‘g‘ri chiziq amalga oshirish mumkin bo‘lgan yechimlar to‘plamini kesib o‘tsa, min(f)= -∞. Agar bu a→+∞ kabi sodir bo'lsa, u holda
Bizning misolimizda f=a to'g'ri chiziq ABCDE maydonini C(4;1) nuqtada kesib o'tadi. Bu oxirgi kesishish nuqtasi bo'lgani uchun max(f)=f(C)=f(4;1)=19.
Simpleks usuli
Haqiqiy chiziqli dasturlash muammolari juda ko'p katta raqam cheklovlar va noma'lumlar va kompyuterda bajariladi. Simpleks usuli bu kabi masalalarni yechishda ishlatiladigan eng umumiy algoritmdir. Usulning mohiyati shundaki, ma'lum miqdordagi maxsus simpleks o'zgarishlardan so'ng ZLP kamayadi maxsus turi, ruxsat berilgan. Simpleks usulini amalda ko'rsatish uchun keling, quyidagi muammoni sharhlar bilan hal qilaylik:
- Simpleks usulida masalani yechishni boshlash uchun masalani maxsus shaklga keltirish va simpleks jadvalini to‘ldirish kerak.
Tizim (4) tabiiy cheklovdir va jadvalga mos kelmaydi. (1), (2), (3) tenglamalar mumkin bo'lgan yechimlar mintaqasini tashkil qiladi. Ifoda (5) - maqsad funktsiyasi. Cheklovlar tizimidagi erkin shartlar va ruxsat etilgan echimlar mintaqasi salbiy bo'lmasligi kerak.
Ushbu misolda X3, X4, X5 asosiy noma'lumlardir. Ular erkin noma'lumlar bilan ifodalanishi va maqsad funktsiyasida almashtirilishi kerak.
Endi siz simpleks jadvalini to'ldirishni boshlashingiz mumkin:
| B. | X1 | X2 | X3 | X4 | X5 | C |
| X3 | 0 | -1 | 1 | 1 | 0 | 1 |
| X4 | 0 | 1 | -1 | 0 | 1 | 1 |
| X5 | 1 | 1 | 1 | 0 | 0 | 2 |
| f | 0 | -6 | 7 | 0 | 0 | 3 |
Ushbu jadvalning birinchi ustunida asosiy noma'lumlar, oxirgisi - erkin noma'lumlarning qiymatlari, qolganlari - noma'lumlarning koeffitsientlari.
- Gauss o'zgarishlaridan foydalangan holda f funktsiyasining maksimalini topish uchun oxirgi qatordagi noma'lumlar uchun barcha koeffitsientlar manfiy emasligiga ishonch hosil qilish kerak (minimumni topish uchun barcha koeffitsientlar kichik yoki teng ekanligiga ishonch hosil qiling). nolga).
| B | X1 | X2 | X3 | X4 | X5 | C |
| X3 | -1 | 1 | 1 | 0 | 0 | 1 |
| X4 | 1 | -1 | 0 | 1 | 0 | 1 |
| X5 | 1 | 1 | 0 | 0 | 1 | 2 |
| f | -6 | 7 | 0 | 0 | 0 | 3 |
Buning uchun oxirgi qatorda (3-ustun) manfiy koeffitsientli ustunni tanlang va ushbu ustunning ijobiy elementlari uchun erkin muddat/koeffitsient munosabatini (1/1; 2/1) tuzing. Ushbu nisbatlardan eng kichigini tanlang va mos keladigan chiziqni belgilang.
Biz (3;3) katakchadagi elementni tanladik. Endi Gauss usulidan foydalanib, biz ushbu ustundagi boshqa koeffitsientlarni tiklaymiz, bu bazaning o'zgarishiga olib keladi va biz optimal echimga bir qadam yaqinlashamiz.
| B | X1 | X2 | X3 | X4 | X5 | C |
| X3 | 0 | 0 | 1 | 1 | 0 | 2 |
| X1 | 1 | -1 | 0 | 1 | 0 | 1 |
| X5 | 0 | 2 | 0 | -1 | 1 | 1 |
| f | 0 | 1 | 0 | 6 | 0 | 9 |
Jadvaldan ko'rinib turibdiki, endi oxirgi qatordagi barcha koeffitsientlar noldan katta yoki teng. Bu biz optimal qiymatni topganimizni anglatadi. Erkin noma'lumlar nolga teng, asosiy noma'lumlarning qiymati va f funktsiyasining maksimal qiymati erkin noma'lumlarning qiymatlariga mos keladi.
Ta'rif 1 . Kosmosdagi nuqtalar to'plami R n , uning koordinatalari tenglamani qanoatlantiradi A 1 X 1 + a 2 X 2 +…+ a n x n = b, chaqirdi ( n - 1 )-o'lchovli gipertekislik n- o'lchovli fazo.
Teorema 1. Giperplan barcha bo'shliqni ikkita yarim bo'shliqqa ajratadi. Yarim bo'shliq qavariq to'plamdir.
Cheklangan sonli yarim bo'shliqlarning kesishishi qavariq to'plamdir.
Teorema 2 . bilan chiziqli tengsizlikni yechish n noma'lum
A 1 X 1 + a 2 X 2 +…+ a n x n b
butun fazo giperplan bilan bo'lingan yarim bo'shliqlardan biridir
A 1 X 1 + A 2 X 2 +…+a n x n= b.
ning tizimini ko'rib chiqing m bilan chiziqli tengsizliklar n noma'lum.
Tizimdagi har bir tengsizlikning yechimi ma'lum bir yarim bo'shliqdir. Tizimning yechimi barcha yarim bo'shliqlarning kesishishi bo'ladi. Bu to'plam yopiq va qavariq bo'ladi.
Chiziqli tengsizliklar sistemalarini yechish
ikkita o'zgaruvchi bilan
ning tizimi bo'lsin m ikki o'zgaruvchili chiziqli tengsizliklar.
Har bir tengsizlikning yechimi butun tekislik mos keladigan to'g'ri chiziq bilan bo'lingan yarim tekisliklardan biri bo'ladi. Tizimning yechimi bu yarim tekisliklarning kesishishi bo'ladi. Bu muammoni tekislikda grafik tarzda yechish mumkin X 1 0 X 2 .
37. Qavariq ko‘pburchakning ko‘rinishi
Ta'rif 1. Yopiq qavariq cheklangan kiritilgan R n chekli songa ega burchak nuqtalari, qavariq deyiladi n-o'lchovli ko'pburchak.
Ta'rif 2 . Yopiq qavariq chegaralanmagan o'rnatilgan R n chekli sonli burchak nuqtalariga ega bo'lgan qavariq ko'p burchakli mintaqa deyiladi.
Ta'rif 3 . Bir guruh AR Agar mavjud bo'lsa, n chegaralangan deb ataladi n-bu to'plamni o'z ichiga olgan o'lchamli to'p.
Ta'rif 4. Nuqtalarning qavariq chiziqli birikmasi t i, ifodasidir.
Teorema (qavariq ko'pburchakning tasviri haqidagi teorema). Qavariq ko'pburchakning istalgan nuqtasi uning burchak nuqtalarining qavariq chiziqli birikmasi sifatida ifodalanishi mumkin.
38. Tenglamalar va tengsizliklar sistemasining ruxsat etilgan yechimlari viloyati.
ning tizimi bo'lsin m bilan chiziqli tenglamalar va tengsizliklar n noma'lum.
Ta'rif 1 . Nuqta R n sistemaning mumkin bo'lgan yechimi deyiladi, agar uning koordinatalari sistemaning tenglamalari va tengsizliklarini qanoatlantirsa. Barcha mumkin bo'lgan echimlar to'plami tizimning mumkin bo'lgan echimlar maydoni (PSA) deb ataladi.
Ta'rif 2. Koordinatalari manfiy bo'lmagan mumkin bo'lgan yechim tizimning mumkin bo'lgan yechimi deyiladi. Barcha mumkin bo'lgan echimlar to'plami tizimning amalga oshirilishi mumkin bo'lgan yechim sohasi (ADA) deb ataladi.
Teorema 1 . ODR yopiq, qavariq, chegaralangan (yoki chegaralanmagan) kichik to'plamdir R n.
Teorema 2. Tizimning ruxsat etilgan yechimi, agar bu nuqta ODS ning burchak nuqtasi bo'lsa, mos yozuvlar yechimi hisoblanadi.
Teorema 3 (ODRni ifodalash haqidagi teorema). Agar ODD chegaralangan to'plam bo'lsa, u holda har qanday mumkin bo'lgan yechim ODD burchak nuqtalarining qavariq chiziqli birikmasi sifatida ifodalanishi mumkin (qavariq chiziqli birikma shaklida) qo'llab-quvvatlovchi echimlar tizimlari).
Teorema 4 (tizimning tayanch yechimi mavjudligi haqidagi teorema). Agar tizimda kamida bitta ruxsat etilgan yechim (ADS) bo'lsa, u holda ruxsat etilgan echimlar orasida kamida bitta referent yechim mavjud.
Shuningdek qarang: Chiziqli dasturlash masalasini grafik usulda yechish, Chiziqli dasturlash masalalarining kanonik shakli
Bunday muammo uchun cheklovlar tizimi ikkita o'zgaruvchidagi tengsizliklardan iborat:
maqsad funksiyasi esa shaklga ega F = C 1 x + C 2 y Buni maksimal darajada oshirish kerak.
Keling, savolga javob beraylik: qanday raqamlar juftligi ( x; y) tengsizliklar sistemasining yechimlari, ya'ni tengsizliklarning har birini bir vaqtda qanoatlantiradimi? Boshqacha qilib aytganda, tizimni grafik tarzda yechish nimani anglatadi?
Avval ikkita noma'lumli bitta chiziqli tengsizlikning echimi nima ekanligini tushunishingiz kerak.
Ikki noma'lumli chiziqli tengsizlikni yechish, tengsizlik amal qiladigan noma'lum qiymatlarning barcha juftlarini aniqlashni anglatadi.
Masalan, tengsizlik 3 x
– 5y≥ 42 juftlikni qondirish ( x , y): (100, 2); (3, –10) va hokazo. Vazifa barcha shunday juftlarni topishdir.
Keling, ikkita tengsizlikni ko'rib chiqaylik: bolta
+ tomonidan≤ c, bolta + tomonidan≥ c. Streyt bolta + tomonidan = c tekislikni ikkita yarim tekislikka ajratadi, shunda ulardan birining nuqtalarining koordinatalari tengsizlikni qanoatlantiradi. bolta + tomonidan >c, va boshqa tengsizlik bolta + +tomonidan <c.
Haqiqatan ham, keling, koordinatali nuqtani olaylik x = x 0 ; keyin chiziq ustida yotgan va abscissaga ega nuqta x 0, ordinataga ega
Ishonch hosil qilaylik a< 0, b>0,
c>0. Abtsissa bilan barcha nuqtalar x 0 yuqorida yotadi P(masalan, nuqta M), bor y M>y 0 , va nuqta ostidagi barcha nuqtalar P, abscissa bilan x 0, bor y N<y 0 . Chunki x 0 - bu ixtiyoriy nuqta, u holda chiziqning bir tomonida har doim nuqtalar bo'ladi bolta+ tomonidan > c, yarim tekislikni hosil qiladi va boshqa tomondan - buning uchun nuqtalar bolta + tomonidan< c.
1-rasm
Yarim tekislikdagi tengsizlik belgisi raqamlarga bog'liq a, b , c.
Bu quyidagi usulga olib keladi grafik yechim ikki o'zgaruvchili chiziqli tengsizliklar sistemalari. Tizimni hal qilish uchun sizga kerak:
- Har bir tengsizlik uchun ushbu tengsizlikka mos keladigan tenglama yozing.
- Tenglamalar bilan belgilangan funksiyalarning grafiklari bo'lgan to'g'ri chiziqlarni tuzing.
- Har bir chiziq uchun tengsizlik bilan berilgan yarim tekislikni aniqlang. Buning uchun chiziqda yotmaydigan ixtiyoriy nuqtani oling va uning koordinatalarini tengsizlikka almashtiring. agar tengsizlik to'g'ri bo'lsa, unda tanlangan nuqtani o'z ichiga olgan yarim tekislik asl tengsizlikning yechimidir. Agar tengsizlik noto'g'ri bo'lsa, u holda chiziqning boshqa tomonidagi yarim tekislik bu tengsizlikning echimlari to'plamidir.
- Tengsizliklar tizimini echish uchun tizimning har bir tengsizligining yechimi bo'lgan barcha yarim tekisliklarning kesishish maydonini topish kerak.
Bu maydon bo'sh bo'lib chiqishi mumkin, keyin tengsizliklar tizimi hech qanday yechimga ega emas va mos kelmaydi. Aks holda, tizim izchil deb aytiladi.
Cheklangan sonli yechimlar bo'lishi mumkin va cheksiz to'plam. Hudud yopiq ko'pburchak yoki cheklanmagan bo'lishi mumkin.
Keling, uchta tegishli misolni ko'rib chiqaylik.
Misol 1. Tizimni grafik tarzda yeching:
x + y - 1 ≤ 0;
–2x - 2y + 5 ≤ 0.
- tengsizliklarga mos keladigan x+y–1=0 va –2x–2y+5=0 tenglamalarni ko‘rib chiqing;
- Ushbu tenglamalar orqali berilgan to'g'ri chiziqlarni quramiz.
2-rasm
Tengsizliklar bilan aniqlangan yarim tekisliklarni aniqlaylik. Keling, ixtiyoriy nuqtani olaylik, (0; 0). Keling, ko'rib chiqaylik x+ y– 1 0, nuqtani (0; 0) almashtiring: 0 + 0 – 1 ≤ 0. Bu (0; 0) nuqta yotadigan yarim tekislikda, x + y –
1 ≤ 0, ya'ni. chiziq ostida yotgan yarim tekislik birinchi tengsizlikning yechimidir. Ushbu nuqtani (0; 0) ikkinchisiga almashtirib, biz quyidagilarni olamiz: –2 ∙ 0 – 2 ∙ 0 + 5 ≤ 0, ya'ni. (0; 0) nuqta yotadigan yarim tekislikda, –2 x – 2y+ 5≥ 0 va bizdan qayerda -2 so'rashdi x
– 2y+ 5 ≤ 0, shuning uchun boshqa yarim tekislikda - to'g'ri chiziq ustidagi birida.
Keling, bu ikki yarim tekislikning kesishishini topamiz. Chiziqlar parallel, shuning uchun tekisliklar hech qanday joyda kesishmaydi, demak bu tengsizliklar sistemasi yechimga ega emas va mos kelmaydi.
2-misol. Tengsizliklar sistemasining grafik yechimlarini toping: 
3-rasm
1. Tengsizliklarga mos tenglamalarni yozamiz va to‘g‘ri chiziqlarni tuzamiz.
x + 2y– 2 = 0
| x | 2 | 0 |
| y | 0 | 1 |
y – x – 1 = 0
| x | 0 | 2 |
| y | 1 | 3 |
y + 2 = 0;
y = –2.
2. (0; 0) nuqtani tanlab, yarim tekisliklardagi tengsizliklar belgilarini aniqlaymiz:
0 + 2 ∙ 0 – 2 ≤ 0, ya'ni. x + 2y– to‘g‘ri chiziq ostidagi yarim tekislikda 2 ≤ 0;
0 – 0 – 1 ≤ 0, ya’ni. y –x– to‘g‘ri chiziq ostidagi yarim tekislikda 1 ≤ 0;
0 + 2 =2 ≥ 0, ya'ni. y To'g'ri chiziq ustidagi yarim tekislikda + 2 ≥ 0.
3. Ushbu uchta yarim tekislikning kesishishi uchburchak bo'lgan maydon bo'ladi. Tegishli chiziqlarning kesishish nuqtalari sifatida mintaqaning uchlarini topish qiyin emas
Shunday qilib, A(–3; –2), IN(0; 1), BILAN(6; –2).
Keling, tizimning natijaviy yechim sohasi cheklanmagan boshqa misolni ko'rib chiqaylik.
