Eng oddiylari chiziqli deterministik modellardir. Ular nazorat o'zgaruvchilarning chiziqli shakli shaklida berilgan ( X):

W = a 0 + a 1 x 1 + … + a k x k

shaklning chiziqli cheklovlari ostida

b 1 j x 1 + b 2 j x 2 + … + b kj x k ³ bj , j = 1,…, q 1 ;

c 1 j x 1 + c 2 j x 2 + … + c kj x k = cj , j = 1,…, q 2 ;

d 1 j x 1 + d 2 j x 2 + … + d kj x k £ dj , j = 1,…, q 3 .

Cheklovlarning umumiy soni m = q 1 + q 2 + q 3 o'zgaruvchilar sonidan oshib ketishi mumkin (m> k). Bundan tashqari, o'zgaruvchilarning musbatlik sharti ( x i ³ 0).

Chiziqli model uchun javob yuzasi giperplan. Masalan, quyidagi shakldagi chiziqli ikki o'zgaruvchan modelni ko'rib chiqing:

W=–2x 1 –3x 2 (2.2)

quyidagi cheklovlar ostida

(2.3)

2x 1 + 3x 2 £ 18;

x 1 – 4x 2 £4;

–2x 1 + x 2 £2;

X 1 ³ 0; x 2 ³ 0.

Yaroqli diapazon (ta'rif doirasi) OABCD model uchun (2.2) cheklovlar (2.3) orqali hosil bo'ladi (2.2-rasm). Javob yuzasi tekis ko'pburchakdir OA"B"C"D"(2.2-rasm, b).

Muayyan cheklash munosabati uchun mumkin bo'lgan echimlar to'plami mavjud bo'lmasligi mumkin (bo'sh). Bunday to'plamga misol rasmda ko'rsatilgan. 2.3. To'g'ridan-to'g'ri AC Va quyosh ruxsat etilgan qiymatlar oralig'ini yuqoridan cheklash. Uchinchi cheklov to'g'ri chiziqdan pastda ruxsat etilgan qiymatlar mintaqasini kesib tashlaydi AB. Shunday qilib, barcha uchta cheklovni qondiradigan umumiy maydon yo'q.

Chiziqli modellar juda oddiy va shuning uchun ular bir tomondan muammoni sezilarli darajada soddalashtirishni nazarda tutsa, boshqa tomondan ular oddiy va samarali echim usullarini ishlab chiqishga imkon beradi.

DLA ni o'rganishda chiziqli modellar kamdan-kam hollarda va deyarli faqat muammolarni taxminiy tavsiflashda qo'llaniladi.

Chiziqli modellar chiziqli bo'lmagan modellarni bosqichma-bosqich yaqinlashtirish (muammoni chiziqlilashtirish) uchun ishlatilishi mumkin. Ushbu uslub, ayniqsa, o'rganilayotgan makonning kichik joylarini o'rganishda samaralidir. Chiziqli bo'lmagan javob yuzasining alohida bo'limlarini chiziqli model bilan tasvirlash asosini yotadi katta guruh optimallashtirish usullari, chiziqli taktika deb ataladigan usullar.

Chiziqli modellarni o'rganish qiyin emas. Xususan, har bir o'zgaruvchining shakl modelining xususiyatlariga ta'siri

W = a 0 + a 1 x 1 + a 2 x 2 + …+ a k x k

uning koeffitsientlari bilan ifodalanadi:

, i = 1,…, k.

Chiziqli modelning optimalini topish V opt samarali simpleks usulini ishlab chiqdi.

Chiqarilgan xarajatlar to'plami sifatida qaraladigan eng oddiy xarajat modellari ba'zan chiziqli bo'lganlarga qisqartiriladi.

Bunday modelning namunasi klassik hisoblanadi transport xarajatlari modeli (transport muammosi)(2.4-rasm).

Mavjud k ishlab chiqarish punktlari
(i = 1,…, k) Va m iste'mol nuqtalari
(j = 1,…, m) ba'zi mahsulotlar. Har birida ishlab chiqarilgan mahsulot miqdori k ishlab chiqarish nuqtalari, a i; har birida kerakli mahsulot miqdori m iste'mol nuqtalari, bj.

Umumiy ishlab chiqarish va iste'molning tengligi qabul qilinadi:

Tashilgan mahsulot miqdori i- ishlab chiqarish punkti j-iste'mol nuqtasi, teng xij; ushbu mahsulot birligini tashish narxi - ij bilan.

Transportning umumiy qiymati BILAN S berilgan chiziqli model:

quyidagi cheklovlar ostida

Chiziqli modellarga chiziqli differentsial tenglamalar (oddiy yoki qisman hosilalar) shaklidagi modellar ham kiradi.

Chiziqli oddiy differensial tenglama n Buyurtma shakliga ega

Dastlabki shartlar quyidagicha yoziladi

Chiziqli qisman differentsial tenglama shaklga ega

Qisman differensial tenglama sifatida berilgan model boshlang'ich va chegaraviy shartlarni o'z ichiga oladi (F(funktsiyaning aniqlanish sohasi chegarasidagi shartlar) t)).

2.3. Eng oddiy matematik modelni o'rganish
gaz turbinali dvigatelning ishlashi

Gaz turbinali dvigatel (GTE) zamonaviy samolyotlarning asosiy elektr stantsiyasidir.

GTE sxemasi shaklda ko'rsatilgan shaklga ega. 2.5.

Bu yerga 1 - kirish diffuzeri; 2 - kompressor; 3 - yonish kamerasi; 4 - turbina;
5 - chiqish nozli.

GTE ish tsikli quyidagi bosqichlarni o'z ichiga oladi:

1) Tezlik bilan kelayotgan V diffuzor orqali havo oqimi kompressorga kiradi.

2) Turbina bilan bir xil valda aylanadigan kompressor yonish kamerasiga kiradigan havoni siqadi.

3) Yonilg'i (kerosin) doimiy ravishda siqilgan havo bilan aralashtiriladigan yonish kamerasiga AOK qilinadi.

4) Yonish natijasida hosil bo'lgan gaz turbinaga kiradi, bu esa uni tezlikka tezlashtiradi V.

5) Bu tezlikda gaz nozul orqali atmosferaga chiqariladi.

Shu sababli V > V, tortish kuchi hosil bo'ladi R, bu samolyotning atmosferada uchishiga imkon beradi.

Tortishish kuchining o'zgarishi dvigatelni boshqarish tugmachasini (THROT) harakatlantirish orqali yonish kamerasiga yonilg'i quyish tezligini o'zgartirish orqali amalga oshiriladi. Gaz kelebeğini gaz kelebeğining ma'lum bir burchagiga d harakatlanishi uchuvchi tomonidan qo'lda yoki parvoz paytida ACS signallariga muvofiq aktuator yordamida amalga oshiriladi. D surish qiymatining oshishi kuchning oshishiga olib keladi R, va pasayish bu kuchning pasayishi hisoblanadi.

GTE murakkab texnik tizim, unda sezilarli miqdordagi fizik va kimyoviy jarayonlar sodir bo'ladi. Dvigatel barcha turdagi avtomatlashtirish moslamalari, turbina pichoqlarini aylantirish va sovutish tizimlari va boshqalar bilan jihozlangan. Tabiiyki, gaz turbinali dvigatelning ishlashini matematik tavsiflash ham juda og'ir bo'ladi, shu jumladan qisman hosilalardagi differentsial tenglamalar tizimlari, oddiy differentsial tenglamalar, transsendental funktsiyalar, algoritmlar. raqamli tizim dvigatelni boshqarish. Bunday modellar gaz turbinali dvigatellarni loyihalash jarayonida qo'llaniladi.

Parvozlarni boshqarish muammolarini hal qilish uchun ko'proq oddiy model GTE, bu surish kuchining bog'liqligi R gaz kelebeğining gaz kelebeği og'ishining d burchagidan. Bosim kuchini o'zgartirish jarayoni oddiy differensial tenglama bilan tavsiflanadi:

, (2.11)

bu erda t > 0 - dvigatelning vaqt konstantasi, bundan tashqari, bog'liq dizayn xususiyatlari shuningdek, atrof-muhit harorati, uning namligi va boshqa tashqi omillar bo'yicha; k[kg/deg] – mutanosiblik koeffitsienti.

(2.11) tenglamaning dastlabki sharti quyidagicha yoziladi

R(0) = R 0 . (2.12)

Shunday qilib, (2.11) tenglama boshlang'ich shart (2.12) bilan birgalikda oddiy differensial tenglama shaklida yozilgan gaz turbinali dvigatelning eng oddiy matematik modeli 1-chi tartib.

Proportsionallik omilini aniqlash k eksperimental ma'lumotlar asosida qurilgan drossellarning aylanish burchagiga surishning bog'liqligini kalibrlash egri chiziqlaridan foydalaniladi. Grafik qiyaligining tangensi kerakli koeffitsientga teng.

(2.11) tenglamaning (2.12) boshlang'ich sharti bilan integrasiyasi vaqt o'tishi bilan surish kuchining qanday o'zgarishini aniqlash imkonini beradi (2.6-rasm).

Gaz kelebeği burilsa, surish R ortadi va keyin ma'lum bir chegara qiymatida barqarorlashadi, ya'ni. GTE inertial ob'ektdir.

Bosim chegarasi uning o'zgarish tezligi nolga teng bo'lganda (2.11) dan olamiz:

. (2.13)

Ko'tarilish vaqti vosita vaqt doimiysi t qiymatiga bog'liq. Qachonki jarayon barqaror deb hisoblanadi t = t og'iz, surish surish kuchining chegara qiymatining besh foizli yo'lak deb ataladigan qismiga kirganda (2.6-rasm). t qanchalik katta bo'lsa, vosita shunchalik inertial va shuning uchun ko'proq t og'iz

Shaklda. 2.7 t = 0,5 da gaz kelebeği burilish burchagiga qarab surish kuchining harakatini ko'rsatadi.

Uchish paytida tortish kuchi, gaz kelebeği 10 ° ga burilganda, uchinchi soniyada barqaror holatga keladi va 3390 kg qiymatiga etadi. Uchishdan 10 soniya o'tgach, gaz kelebeği 20 ° ga burilsa, tortish kuchi 6780 kg ga o'rnatiladi va yana o'n soniyadan so'ng, gaz kelebeği 30 ° ga burilsa, tortish kuchi 10170 kg ga o'rnatiladi. Tortishish kuchining chegaraviy qiymati
14270 kg.

Shunga o'xshash ma'lumotlar.

3.1. Umumiy vazifa chiziqli dasturlash

Chiziqli dasturlash- bu matematik dasturlashning eng rivojlangan bo'limi bo'lib, uning yordamida chiziqli ulanishlar va cheklovlar bilan ekstremal masalalarni tahlil qilish va yechish amalga oshiriladi.

Chiziqli dasturlash bir qator evristik (taxminan) yechim usullarini o'z ichiga oladi, ular berilgan sharoitlarda hamma narsadan foydalanishga imkon beradi. variantlari eng yaxshi, optimalni tanlash uchun ishlab chiqarish muammolarini hal qilish. Bu usullarga quyidagilar kiradi - grafik, simpleks, potentsial usul (modifikatsiyalangan taqsimlash usuli - MOD), Xichkov, Kreko, Vogel yaqinlashish usuli va boshqalar.

Ushbu usullarning ba'zilari umumiy nom - tarqatish yoki transport usuli bilan birlashtirilgan.

Chiziqli dasturlashning vatani Rossiyadir. Chiziqli dasturlash bo'yicha birinchi ishlar bo'lajak akademik L.V. Kantorovich 1939 yilda nashr etilgan. 1975 yilda u chiziqli dasturlash usullarini ishlab chiqqani uchun iqtisod bo'yicha Nobel mukofotiga sazovor bo'lgan. Akademik L.Vning aksariyat asarlaridan beri. Kantorovich transport muammolarini hal qilishga bag'ishlangan bo'lsa, shuni aytish mumkinki, ushbu Nobel mukofoti ham Rossiya transport fanining xizmatlarini ko'rsatadi.

Avtomobil transportida 1960-yillardan boshlab ko'plab eng muhim ishlab chiqarish muammolarini hal qilish uchun chiziqli dasturlash usullari qo'llanila boshlandi, xususan: yuklarni tashish masofasini qisqartirish; optimal tashish sxemasini tuzish; eng qisqa harakat yo'nalishlarini tanlash; turli, lekin bir-birini almashtiradigan yuklarni tashish vazifalari; smenali kunlik rejalashtirish; kichik partiyali yuklarni tashishni rejalashtirish; avtobuslarni marshrutlar bo'ylab taqsimlash va boshqalar.

Chiziqli dasturlash modelining xususiyatlari quyidagilardan iborat:

Maqsad funksiyasi va cheklovlar ifodalangan chiziqli bog'liqliklar(tenglik yoki tengsizlik);

Bog'liqlar soni har doim noma'lumlar sonidan kamroq (noaniqlik sharti);

Kerakli o'zgaruvchilarning manfiy emasligi. Chiziqli dasturlash modelini qisqartirilgan shaklda yozishning umumiy shakli quyidagicha:

Toping X ij ≥ 0 (j = 1, 2…n) quyidagi turdagi cheklovlar ostida:

Ushbu cheklovlar maqsad funktsiyasini minimallashtiradi (yoki maksimal darajaga keltiradi).

Chiziqli dasturlash modelini yozishning standart shakli chiziqli tenglamalar tizimida yozilgan kanonik shaklda, ya'ni chiziqli tengliklar ko'rinishida, manfiy bo'lmagan sonlarda:

a 11 x 1 + a 12 x 2 + ... + a 1 n x n \u003d b 1;

a 21 x 1 + a 22 x 2 + ... + a 2 n x n \u003d b 2 ; (3.1)

……………………………..

a m x 1 + a m 2 x 2 + ...+ a mn x n = b m ..

Agar model manfiy bo'lmagan sonlarda tengsizliklar ko'rinishida yozilsa, ya'ni u shaklga ega.

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 ; (3.2)

……………………………..

a m x 1 + a m 2 x 2 + …+ a mn x n ≤ b m ,..

keyin bu yozuv ga qisqartiriladi kanonik qo'shimcha o'zgaruvchilarni kiritish orqali (3.1) shakl x n +1> 0 (i=1,2…m) tengsizlikning chap tomoniga (yoki tengsizlik belgisi qarama-qarshi tomonga yo'naltirilgan bo'lsa, o'zgaruvchilar sonining kamayishi). Qo'shimcha o'zgaruvchilar asosni tashkil qiladi.

Chiziqli dasturlash masalasini echishning standart shakli maqsad funktsiyasini minimallashtiradigan manfiy bo'lmagan sonlardagi chiziqli tenglamalar tizimining echimlarini topishdir. Maqsad funktsiyasi keyin shaklga ega bo'ladi

L = c 1 x 1 + c 2 x 2 ... c n x n → min, (3,3)

Qayerda s 1 , s 2 … s n maqsad funksiya koeffitsientlaridir L o'zgaruvchilar bilan X j .

Qo'shimcha o'zgaruvchilar maqsad funktsiyasiga nol koeffitsientlar bilan kiradi.

Maqsad funksiyasini maksimallashtirish holatida L maqsad funktsiyasining o'zgaruvchilari belgilari teskari bo'lishi kerak va biz yana minimallashtirish masalasiga kelamiz, ya'ni. bir vazifa boshqasiga almashtiriladi L- L yoki maks L=min(- L).

Chiziqli tenglamalar tizimining asosiy yechimi (3.1) asosiy bo'lmagan o'zgaruvchilarga nol qiymatlar berilgan yechimdir.

Bazisga kiritilgan o'zgaruvchilar salbiy bo'lmagan asosiy yechim ruxsat etilgan deb ataladi.

Maqsad funksiyasini (3.3) maksimal darajaga tushiradigan (yoki minimallashtiradigan) ruxsat etilgan yechim optimal deb ataladi.

Har bir chiziqli dasturlash muammosi ikki chiziqli dasturlash muammosi deb ataladigan boshqasiga mos keladi. Ikkilamchiga nisbatan dastlabki masala to'g'ridan-to'g'ri muammo deb ataladi. Birlamchi va ikkilamchi masalalar juftlikni hosil qiladi, ular chiziqli dasturlashda qo'sh juftlik deb ataladi. Birlamchi va qo‘sh juftlik birlamchi masala kanonik shaklda yozilsa, assimetrik juftlik, masalalar shartlari tengsizlik sifatida yozilsa, simmetrik juftlik hosil qiladi.

Ikkilamchi masalaning matematik modelini tuzish qoidalari matritsalarni hisoblash qoidalariga asoslanadi.

Ikkilik tushunchasi chiziqli dasturlash masalalarini tahlil qilishda keng qo'llaniladi. Ikkilik xususiyati har bir aniq holatda batafsil ko'rib chiqiladi.

3.2. Grafik-analitik usul

Grafik-analitik usul chiziqli dasturlashning eng oddiy usullaridan biridir. Bu chiziqli dasturlashning mohiyatini, uning geometrik talqinini aniq ochib beradi. Uning kamchiligi shundaki, u 2 yoki 3 ta noma'lum bo'lgan muammolarni hal qilish imkonini beradi, ya'ni u tor doiradagi muammolar uchun qo'llaniladi. Usul analitik geometriya qoidalariga asoslanadi.

Ikki o‘zgaruvchili masalani yechish x 1 Va x 2, masalaning ma'nosiga ko'ra, manfiy bo'lmasligi kerak, Dekart koordinatalari tizimida bajariladi. Tenglamalar x 1=0 va x 2= 0 - birinchi kvadrantning koordinata tizimining o'qlari

Keling, muayyan misol yordamida hal qilish usulini ko'rib chiqaylik.

3.1-misol. Zaxirada 300 tonna penobeton, 200 tonna po‘lat buyumlar mavjud. Avtokorxona ushbu mahsulotlarni qurilayotgan ob'ektga etkazib berishi kerak. Avtomobil kompaniyasida KAMAZ - 5320 va yuk mashinalari mavjud

ZIL-4314. Bir safar uchun KamAZ-5320 6 tonna ko'pikli beton va 2 tonna po'lat etkazib berishi mumkin va sayohatdan olinadigan foyda 4 ming rublni tashkil qiladi. ZIL-4314 bir safarda 2 tonna ko'pikli beton va 4 tonna po'lat etkazib beradi, sayohatdan olingan foyda 6 ming rublni tashkil qiladi. Avtokorxonani eng katta foyda bilan ta'minlaydigan tarzda tashishni tashkil qilish kerak.

Keling, masalaning matematik modelini tuzamiz. KamAZ-5320 va bo'ylab sayohatlarning kerakli sonini x 1 bilan belgilang X 2 ta zarur ZIL-4314 chavandozlari.

Tonna ko'pikli beton mahsulotlarining umumiy tashish hajmi 6 tani tashkil qiladi x 1+ 2x 2, va po'latdan 2 x 1+ 4x 2. Mavjud tovarlar soniga qarab etkazib berish chegarasi 6 ta x 1+ 2x 2 ≤ Ko'pikli beton uchun 300t va 2 x 1+ 4x 2 ≤ po'lat uchun 200t.

Umumiy foyda ming rublda. 4 sifatida ifodalanadi X 1 + 6X 2 , bu maksimal darajada oshirilishi kerak va ko'rib chiqilayotgan muammoda optimallik mezoni hisoblanadi. Shunday qilib, masalaning matematik modeli quyidagicha ko'rinadi. Maqsad funktsiyasini maksimal darajada oshirish kerak

L = 4x 1+ 6x 2 → sharoitlarda maksimal: 6 x 1+ 2x 2 ≤ 300; 2x 1+ 4x 2 ≤ 200; x 1 ≥ 0;x 2 ≥ 0.

6-tenglamani ko'rib chiqing x 1+ 2x 2 = 300. Ushbu tenglama bilan tasvirlangan chiziqni qurish uchun biz ushbu chiziqda yotgan ikkita nuqtani topamiz. Da x 1= 0 to'g'ri chiziq tenglamasidan 2 ni topamiz x 2 = 300, bu erdan x 2 \u003d 150. Shuning uchun, koordinatalari (0,150) bo'lgan A nuqta kerakli chiziqda yotadi. Da x 2= 0, bizda 6 bor x 1\u003d 300, qaerdan x 1 \u003d 50 va nuqta D koordinatali (50,0) ham kerakli chiziqda. Ushbu ikkita nuqta orqali chiziq torting AD(3.1-rasm).

Chiziqli tengsizlik 6 x 1+ 2x 2 ≤ 300 - qurilgan chiziq 6 ning bir tomonida joylashgan yarim tekislik x 1+ 2x 2 = 300. Kerakli yarim tekislik nuqtalari shu chiziqning qaysi tomonida joylashganligini bilish uchun 6 tengsizlikka almashtiramiz. x 1+ 2x 2 ≤ Chegara chizig'ida yotmagan biron bir nuqtaning 300 koordinatasi. Masalan, kelib chiqishi 0-(0,0). U 6∙0 + 2∙0 = 0 tengsizlikni qanoatlantiradi< 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой AD va rasmda. 3.1 soyali.

Tenglama 2 x 1+ 4x 2= 200 ikkita nuqtadan tuziladi. Da x 1 = 0 4x 2 = 200 qayerdan x 2 = 50. Keyin ko'rsating E koordinatalariga ega (0,50) va kerakli chiziqqa tegishli. Da x 2= 0, 2x 2 = 200 nuqta Bilan koordinatalari (100,0) bilan berilgan chiziqda joylashgan. Tengsizlikka nuqta koordinatalarini qo'yish Bilan(0,0), biz 2∙0 + 4∙0 = 0 ni olamiz< 200. Значит, начало координат находится в области допустимых значений от прямой 2x 1+ 4x 2= 200.

Vazifalarni cheklash tizimi rejalarni talab qiladi ( x 1; x 2) barcha to'rtta tengsizlikni qanoatlantiring, ya'ni ruxsat etilgan dizaynlar nuqtalar ( x 1; x 2) bir vaqtning o'zida barcha to'rtta yarim tekislikda bo'lishi kerak. Bu talab faqat poligonning ichida va chegarasida joylashgan nuqtalar tomonidan qondiriladi. OEKD, bu ruxsat etilgan eritmalar ko'pburchagi.

Mumkin yechimlar ko‘pburchagining uchlari nuqtalardir O, E, K, D chiziq segmentlari OE, EK, KD, OD- uning qovurg'alari. Ko'pburchakning istalgan nuqtasi OEKD vazifaning barcha shartlarini qondiradigan rejasidir. Ko'pburchakning uchlari ikkita to'g'ri chiziqning kesishmasidan hosil bo'ladi va masalaning asosiy rejalariga mos keladi, ular orasida eng yaxshi (optimal) reja mavjud. Shunday qilib, mumkin bo'lgan echimlar ko'pburchagida qanchalik ko'p tayanch rejalar bo'lsa, shuncha ko'p bo'ladi.

Maqsad funktsiyasi uchun vizual geometrik tasvirni ham olish mumkin L = 4x 1+ 6x 2. Biz, masalan, maqsad funktsiyasining ba'zi qiymatini aniqlaymiz L= 120. tenglama 4 x 1+ 6x 2 = 120 nuqtadan o'tadigan chiziqni belgilaydi IN koordinatalari (x 1 \u003d 0; x 2 \u003d 20) va nuqta bilan L koordinatalari bilan (( X 1 = 30; X 2 = 0). Chiziq segmenti BL poligon ichida joylashgan OEKD. Shuning uchun, ushbu segmentning barcha rejalari (nuqtalari) uchun maqsad funktsiyasining qiymati bir xil va 120 ga teng. Maqsad funktsiyasining boshqa qiymatlarini berib, biz parallel chiziqlarni olamiz, ular deyiladi. darajali chiziqlar maqsadli funktsiya.

Chiziqni siljitish L o'ziga bir yo'nalishda parallel ravishda biz maqsad funktsiyasining ortishiga erishamiz va teskari yo'nalishda - uning kamayishi. Ushbu misolda to'g'ri chiziqning harakati BL o'ng tomonda biz maksimal darajaga ko'taradigan maqsad funktsiyasining o'sishini aniqlaydi. Buni chiziqqa qadar qilamiz BL ruxsat etilgan eritmalar ko'pburchagi bilan kamida bitta umumiy nuqtaga ega bo'ladi OEKD. Anjirdan. 3.1 dan kelib chiqadiki, maqsad funktsiyasi sathining to'g'ri chizig'i kesishgan oxirgi nuqta nuqta bo'ladi. TO. Bu shuni anglatadiki, nuqta TO optimal vazifa rejasini belgilaydi.

Darajali chiziqqa perpendikulyar o'sish yo'nalishi deyiladi eng katta o'sish yo'nalishi maqsad funktsiyasi va uning maksimal daromadini aniqlaydi. Ushbu yo'nalish chizilgan darajali chiziqlarsiz o'rnatilishi mumkin. Buning uchun o'qlarda kerak x 1 Va x 2 maqsad funksiya koeffitsientlariga teng segmentlarni ajratib qo'ying va ulardan koordinatalarda bo'lgani kabi foydalanib, maqsad funktsiyasining eng katta o'sish vektorini tuzing. Matematikada u deyiladi gradient va grad belgisi bilan belgilanadi. Xususiyat uchun gradient L = 4x 1 + 6x 2 vektor bo'ladi n| 4; 6 | . Uning qurilishi qulayligi uchun biz koordinatalarni, masalan, 10 barobarga oshiramiz, ya'ni. n | 40; 60 | . Maqsad funksiyasining gradientini tuzamiz L, buning uchun koordinatali (40; 60) nuqtani koordinatali nuqta bilan bog'laymiz. Maqsad funksiyasi darajasidagi chiziqlar gradient yo‘nalishiga perpendikulyar chiziladi.

Shunday qilib, u yoki bu tarzda, bu nuqta aniqlangan TO o'zgaruvchilarning qiymatlari berilgan nuqtaning koordinatalariga mos keladigan optimal vazifa rejasini belgilaydi. Koordinatalarni o'rnatish uchun ushbu cho'qqini tashkil etuvchi to'g'ri chiziqlar tenglamalari tizimini echish kerak:

6x 1+ 2x 2= 300;

2x 1+ 4x 2= 200.

Ikkinchi tenglamani 3 ga ko'paytirish orqali x 1 da koeffitsientlarni tenglashtiramiz va ikkinchi tenglamadan birinchisini ayiramiz. Keling, 10 ni olaylik x 2= 300,x 2 = 30. X 2 \u003d 30 qiymatini har qanday tenglamaga, masalan, birinchisiga almashtirib, biz qiymatni aniqlaymiz X 1:

6x 1+ 2X · 30 = 300,

qayerdan 6 x 1 = 300 - 60 = 240, shuning uchun x 1 = 40.

Shunday qilib, avtomobil kompaniyasi uchun eng ko'p foyda olish uchun KamAZ-5320 ga 40 ta sayohat va ZIL-4314 ga 30 ta sayohatni bajarish kerak. Bu holda maksimal foyda bo'ladi

L = 4x 1+ 6x 2\u003d 4 40 + 6 30 \u003d 340 ming rubl.

Ko'rib chiqilgan misol va ikkita o'zgaruvchi bilan optimallashtirish muammosining geometrik talqiniga asoslanib, biz quyidagi xulosalar chiqarishimiz mumkin:

1) ikki o'lchovli fazoda mumkin bo'lgan echimlar maydoni ko'pburchakdir;

2) ko'pburchakning har bir tomoni nolga teng bitta o'zgaruvchining qiymatiga mos keladi;

3) ruxsat etilgan echimlar ko'pburchagining har bir tepasi nolga teng bo'lgan ikkita o'zgaruvchining qiymatlariga mos keladi;

4) maqsad funktsiyasining har bir qiymati to'g'ri chiziqqa mos keladi;

5) masalaning optimal yechimi ko‘pburchak cho‘qqisiga to‘g‘ri keladi, bunda maqsad funksiyasi optimal qiymatga ega bo‘ladi, optimal o‘zgaruvchilar esa shu cho‘qqining koordinatalari hisoblanadi.

Umumiy holda, optimallashtirish masalalari xuddi shunday geometrik talqinga ega. Vazifa rejalari to'plami cho'qqilari mos yozuvlar rejalariga mos keladigan ko'pburchak bo'ladi. Masalani yechishda maqsad funksiyasining katta qiymatiga ega bo‘lgan ko‘pburchakning bir cho‘qqisidan ikkinchisiga o‘tish uning optimal qiymati olinmaguncha amalga oshiriladi. E'tibor bering, optimallashtirish usullarining samaradorligi aniq cho'qqilarni sanab o'tish (iteratsiya) faqat maqsad funktsiyasining eng katta o'sishi yo'nalishida amalga oshirilishida. Shuning uchun, juda ko'p sonli barcha cho'qqilar hisobga olinmaydi, faqat ekstremalga yaqinroq bo'lganlar.

Optimallashtirish masalalari sinfini aniqlashda va uni yechish usulini tanlashda amalga oshirilishi mumkin bo'lgan yechimlar to'plami qavariq yoki qavariq bo'lmagan, chiziqli yoki chiziqli bo'lmagan maqsad funktsiyasi ekanligini bilish kerak.

Ta'rifga ko'ra, to'plam deyiladi qavariq agar har qanday ikkita nuqta uchun ushbu nuqtalarni bog'laydigan butun segment ushbu to'plamga tegishli bo'lsa. Qavariq to'plamlarga misol sifatida, masalan, segment (3.2-rasm, a), aylana shaklidagi tekislik, kub, parallelepiped, shuningdek, uning har bir tomonining bir tomonida butunlay joylashgan ko'pburchaklar mavjud. , va boshqalar.

Shaklda. 3.2b konveks bo'lmagan to'plamlarni ko'rsatadi. Qavariq bo'lmagan to'plamlarda AB segmentining ko'rib chiqilayotgan to'plamga tegishli bo'lmagan kamida ikkita nuqtasini ko'rsatish mumkin.

3.3. Simpleks usuli

Simpleks usuli chiziqli dasturlash masalalarini yechishning keng tarqalgan usuli hisoblanadi. Usul o'z nomini "simpleks" so'zidan oldi, bu eng oddiy konveks ko'pburchakni bildiradi, uning uchlari soni har doim bo'shliq o'lchamidan bittaga ko'p. Simpleks usuli AQSHda 1940-yillarning oxirida matematik J. Dantsig tomonidan ishlab chiqilgan.

Simpleks usuli (3.1) tipidagi kanonik chiziqli tenglamalar tizimining manfiy bo'lmagan asosiy yechimini olishni, maqsad funktsiyasini (3.3) keyinchalik minimallashtirishni (maksimallashtirishni) va shu tarzda optimal qiymatlarni topishni o'z ichiga oladi. zarur o'zgaruvchilar x 1, x 2… x n.

Simpleks usulining g'oyasi shundan iboratki, hisoblash jarayonida birinchi asosiy yechimdan ikkinchi, uchinchi va boshqalarga ketma-ket o'tadi. deb atalmish orqali oddiy transformatsiyalar. Transformatsiyalar simpleks jadvallar ko'rinishida amalga oshiriladi, bu esa hisoblarni sezilarli darajada soddalashtiradi va tezlashtiradi.

Chiziqli tenglamalar tizimining manfiy bo'lmagan asosiy yechimlarini olish uchun noma'lumlarni yo'q qilish jarayonini shunday o'tkazish kerakki, bu jarayonning barcha bosqichlarida tenglamalarning erkin shartlari manfiy bo'lmagan holda qolsin. Bunday holda, quyidagi qoidaga amal qilish kerak: yangi asosiy o'zgaruvchi sifatida kamida bitta ijobiy koeffitsient mavjud bo'lgan har qanday erkin o'zgaruvchi qabul qilinadi; bazisdan oʻzgaruvchi olinadi, bu tenglamalarning erkin shartlarining bazisga kiritilgan oʻzgaruvchisi boʻlgan tenglamalarning tegishli musbat koeffitsientlariga eng kichik nisbatiga mos keladi. Bunday transformatsiyalar deyiladi simpleks konvertorlari.

Bu juda muhim, chunki bitta erkin o'zgaruvchining mumkin bo'lgan eng katta qiymatiga boshqa erkin o'zgaruvchilarning nol qiymatlari bilan mos keladigan ma'lum bir salbiy bo'lmagan yechimni topish uchun ko'rsatilgan o'zgaruvchining diapazonini aniqlash va uning eng kattasini almashtirish o'rniga. mumkin bo'lgan qiymat umumiy qaror bu o'zgaruvchini asosiy sifatida qabul qilish va tizimni yangi asosga o'tib, hisob-kitoblarni ancha soddalashtiradigan simpleks transformatsiyasiga bo'ysunish kifoya.

Simpleks jadvallari yordamida hisob-kitoblar qulay tarzda amalga oshiriladi. Bir jadvaldan ikkinchisiga o'tish bir iteratsiyaga, ya'ni bir asosdan ikkinchisiga o'tishga to'g'ri keladi, shu bilan birga maqsad funktsiyasining qiymati kamayadi. Muayyan miqdordagi iteratsiyalar uchun ular maqsad funktsiyasining optimal (minimal yoki maksimal) qiymati olinadigan asosga o'tadi. Simpleks usulini umumiy shaklda ko'rib chiqamiz.

Chiziqli dasturlashning umumiy vazifasi manfiy bo'lmaganlik shartiga rioya qilgan holda o'zgaruvchilari chiziqli tenglamalar tizimi bilan o'zaro bog'langan maqsad funksiyani minimallashtirish (maksimallashtirish)dan iborat.

Chiziqli shaklni minimallashtirish zarur bo'lsin

L = c 1 x 1 + c 2 x 2 + ... c n x n.

Quyidagi shartlarda (aniqlik uchun tenglamalarda nol va birlik koeffitsientlari saqlanadi):

1x 1+ 0x 2 + ... 0x m + a 1m+ 1x m+1 ... + a 1n x n \u003d b 1;

0x 1+ 1x 2+… 0x m + a 2m+ 1x m+1 ... + a 2n x n \u003d b 2;

……………………………………………

0x 1+ 0x 2 + ... 1x m + a mm + 1x m +1 ... + a mn x n \u003d b m.

Ushbu tenglamalar tizimi allaqachon tayyor asosga ega, chunki har bir cheklov tenglamasi boshqa tenglamalarda, ya'ni o'zgaruvchilar koeffitsientlaridan bo'lmagan birga teng koeffitsientli noma'lumni o'z ichiga oladi. X 1 , X 2 …, x m identifikatsiya matritsasi yaratishingiz mumkin.

Keling, asosiy o'zgaruvchilar uchun tenglamalarni yechamiz:

x 1 \u003d b 1 - (a 1m + 1 x m + 1 ... + a 1n x n);

x 2 \u003d b 2 - (a 2m + 1 x m + 1 ... + a 2n x n);

………………………………

x m \u003d b m - (a mm + 1x m + 1 ... + a mn x n),

va biz asosiy o'zgaruvchilar o'rniga erkin o'zgaruvchilar, ularning ifodalarini erkin o'zgaruvchilar ko'rinishida qo'yib, maqsad funktsiyasini ifodalaymiz:

L=c 1 b 1 +c 2 b 2 +c m b m –(c 1 a 1m +c 2 a 2m+1 +…+c m a mn+1)x m+1 -…-(c 1 a 1n +c 2 a 2n +…+c m a mn)x n …+c n x n..

O'zgaruvchilar x 1, x 2 ..., x m, ularning yordami bilan birinchi asosiy reja topilgan, asosiy, qolganlari esa x m +1 , x m +2 ,…x n – ozod. Tizimda tenglamalar bo'lsa, har doim ko'p asosiy o'zgaruvchilar bo'lishi kerak. Salbiy bo'lmagan shartga asoslanib, erkin o'zgaruvchilarning eng kichik qiymati nolga teng. Tenglamalar tizimining natijaviy asosiy yechimi uning dastlabki mumkin bo'lgan yechimidir, ya'ni. x 1 \u003d b 1, x 2 \u003d b 2, ... x m \u003d b m, x m +1 \u003d 0,…, x n = 0.

Bu yechim maqsad funksiyasining qiymatiga mos keladi

L = c 1 b 1 + c 2 b 2 + ... c m b m.

Dastlabki yechimning optimalligi tekshiriladi. Agar u optimal bo'lmasa, bazisga erkin o'zgaruvchilarni kiritish orqali maqsad funktsiyasining kichikroq qiymati bilan quyidagi mumkin bo'lgan echimlar topiladi. Buning uchun bazisga kiritilishi kerak bo'lgan erkin o'zgaruvchi, shuningdek, bazisdan olib tashlanishi kerak bo'lgan o'zgaruvchi aniqlanadi. Keyin ular oldingi tizimdan keyingi ekvivalent tizimga o'tadilar. Bu simpleks jadvallari yordamida amalga oshiriladi. Masalani yechish maqsad funksiyaning optimal qiymati olinmaguncha davom etadi.

Simpleks jadvallar quyidagicha tuzilgan (3.1-jadvalga qarang). Barcha o'zgaruvchilarni jadvalning yuqori qismiga joylashtiring X 1 , X 2 …, x n va koeffitsientlar cj, ular bilan mos keladigan o'zgaruvchilar maqsad funktsiyasiga kiritilgan. Birinchi ustun c i bazisga kiritilgan o'zgaruvchilar uchun maqsad funksiya koeffitsientidan iborat. Undan keyin asosiy o'zgaruvchilar ustuni va tenglamalarning erkin shartlari keladi. Jadvalning qolgan ustunlari elementlari tenglamalar tizimiga kiradigan o'zgaruvchilarning koeffitsientlari hisoblanadi. Shunday qilib, jadvalning har bir qatori asosiy o'zgaruvchiga nisbatan echilgan tizim tenglamasiga mos keladi. Jadvalda, shuningdek, berilgan asos uchun maqsad funktsiyasiga mos keladigan reja varianti ko'rsatilgan.

Jadvalning pastki qatori deyiladi indeks. Uning har bir elementi (baholash) ∆ j aniqlash

∆j = z j – c j ,

Qayerda cj maqsad funksiyadagi mos o'zgaruvchilar uchun koeffitsientlar; zj - asosiy o'zgaruvchilar va mos keladigan o'zgaruvchilar bilan maqsad funktsiyasi koeffitsientlari mahsuloti yig'indisi - elementlar j-jadvalning ustuni.

Jadval 3.1

Boshlang'ich amaldagi oddiy jadval

1.

2. foydalanish yo'nalishlari mat. iqtisodiyotdagi modellar.

Matematik modellar noma'lum parametrlarning optimal qiymatlarini aniqlash imkonini beradi iqtisodiy tizimlar qaror qabul qilish jarayonida muhim ahamiyatga ega. Matematik dasturlash faqat tanlash jarayonini optimallashtirish imkonini beruvchi apparatni taqdim etadi eng yaxshi variantlar iqtisodiy tizimlarda boshqaruv jarayonida rejalar.

Matematik statistika, optimallashtirish usullari, iqtisodiy usullarda qo'llaniladi. kibernetika, eksperimental masalalar.

Iqtisodiyotdagi murakkab jarayonlar va hodisalarni o'rganishda ko'pincha modellashtirish qo'llaniladi - o'rganilayotgan ob'ektning ko'rib chiqilayotgan xususiyatlarini aniq belgilangan aniq ko'rsatish. Uning mohiyati shundan iboratki, o'rganilayotgan hodisa eksperimental sharoitda boshqa vaqt va fazoviy miqyosdagi model yordamida takrorlanadi. Model - bu maxsus yaratilgan ob'ekt bo'lib, uning yordamida o'rganilayotgan tizimning ma'lum xususiyatlari uni o'rganish uchun takrorlanadi. Matematik modellashtirish o'rganilayotgan ob'ekt haqida ma'lumot olishning eng mukammal va ayni paytda samarali usuli hisoblanadi. Bu iqtisodiyotda tahlil qilish uchun kuchli vositadir. Modellardan foydalangan holda tadqiqot natijalari, tuzilgan model ko'rib chiqilayotgan hodisaga etarlicha adekvat bo'lganda amaliy qiziqish uyg'otadi, ya'ni. haqiqiy vaziyatni aks ettirish uchun etarli.

2. matematik dasturlash fan sifatida, uning tuzilishi. Optimallashtirish muammolari. Iqtisodiy muammolarni hal qilishda klassik optimallashtirish usullarini qo'llashdagi qiyinchiliklar.

Matematik dasturlash amaliy matematikaning rivojlanayotgan bo‘limidir nazariy asos va ekstremal muammolarni hal qilish usullari.

Matematik dasturlash bir qancha bo'limlarni o'z ichiga oladi, ularning asosiylari quyidagilardir:

1. Chiziqli dasturlash. Bu bo'lim noma'lum o'zgaruvchilar birinchi darajali matematik munosabatlarga kiritilgan masalalarni o'z ichiga oladi.

2. Nochiziqli dasturlash. Ushbu bo'limda maqsad funktsiyasi va (yoki) cheklovlar chiziqli bo'lmagan bo'lishi mumkin bo'lgan muammolarni o'z ichiga oladi.

3. Dinamik dasturlash. Ushbu bo'lim hal qilish jarayonini alohida bosqichlarga bo'lish mumkin bo'lgan vazifalarni o'z ichiga oladi.

4. Butun sonli dasturlash. Ushbu bo'limda noma'lum o'zgaruvchilar faqat butun qiymatlarni qabul qilishi mumkin bo'lgan vazifalarni o'z ichiga oladi.

5. Stokastik dasturlash. Ushbu bo'lim maqsad funktsiyasi yoki cheklovlardagi tasodifiy o'zgaruvchilarni o'z ichiga olgan vazifalarni o'z ichiga oladi.

6. Parametrik dasturlash. Ushbu bo'limda maqsad funktsiyasidagi noma'lum o'zgaruvchilarning koeffitsientlari yoki cheklovlar ba'zi parametrlarga bog'liq bo'lgan masalalar kiradi.

Matematik dasturlash muammolarini hal qilish uchun ekstremumni topishning klassik usullaridan foydalanish qiyin, chunki matematik dasturlash muammolarida maqsad funktsiyasi noma'lum o'zgaruvchilarning maqbul qiymatlari mintaqasi chegarasida o'zining ekstremal qiymatiga etadi va hosilalar mavjud emas. chegara nuqtalarida. Ruxsat etilgan ballarni to'liq sanab o'tish ularning sezilarli soni tufayli mumkin emas.

3. Matematik model haqida tushuncha, mat turlari. modellar

Matematik model real hodisa yoki jarayonning matematik belgilar va ifodalarda yozilgan abstraksiyasidir. Matematik modellar iqtisodiy jarayonlar hodisalar esa iqtisodiy va matematik modellar deyiladi

Modellar quyidagilarga bo'linadi:

1. chiziqli, unda barcha bog'liqliklar chiziqli munosabatlar bilan tavsiflanadi,

2. chiziqli bo'lmagan, unda chiziqli bo'lmagan munosabatlar mavjud;

3. stokastik, o'rganilayotgan jarayonlarning tasodifiy tabiatini hisobga oladigan,

4. deterministik, bu barcha parametrlarning o'rtacha qiymatlarini hisobga oladi.

5. dinamik o'rganilayotgan tizimlar bir necha davrlar davomida ishlab chiqilayotgan modellar,

6. statik bu erda vaqt omili hisobga olinmaydi.

7. optimallashtirish qarab tanlov amalga oshiriladigan modellar ekstremizm ba'zi bir mezon,

8. optimallashtirmaslik, unda optimallik mezoni yo'q.

9. makromodellar(butun uy xo'jaligi uchun)

10. mikromodellar(Iqtisodiyotning individual aloqalari yoki jarayonlari).

Matematik modellarning turlari: chiziqli, chiziqli bo'lmagan, kvadratik, butun, diskret, parametrik, chiziqli kasr, dinamik, stokastik.

4. Matematik dasturlash masalalarining umumiy bayoni.

Matematik dasturlash muammosining umumiy bayonini ko'rib chiqing.

Matematik dasturlashning umumiy muammosi maqsad funktsiyasining optimal qiymatini aniqlashdan iborat va o'zgaruvchilar qiymatlari ma'lum bir ruxsat etilgan qiymatlar oralig'iga tegishli bo'lishi kerak. Matematik jihatdan optimal yechimning ta’rifi ko‘p o‘zgaruvchilar funksiyasining ekstremumini (maks yoki min) topishda ifodalanadi.

Z = f(x1, x2, …, xn)

ushbu o'zgaruvchilarning berilgan o'zgarishi oralig'ida

gi (x1, x2,…, xn)Ribi (i = 1, 2,…, m),

bu yerda Ri ≥, =, ≤ belgilaridan biri.

5. Ishlab chiqarish rejasini optimallashtirish muammosi. Iqtisodiy shakllantirish va masalalarning matematik modelini qurish.

Iqtisodiy sozlash:

Kompaniya ishlab chiqaradi n ishlatiladigan mahsulot turlari m xom ashyo turlari. Mahsulot birligini ishlab chiqarish uchun u yoki bu turdagi xom ashyoning qat'iy belgilangan miqdori qo'llaniladi. Korxonada har bir turdagi xom ashyo cheklangan. Korxona mahsulot birligini sotishdan ma'lum foyda oladi. Korxona maksimal umumiy foyda oladigan shunday ishlab chiqarish rejasini topish kerak.

Matematik sozlash:

j = 1, n mahsulot turining indeksi j bo'lsin

i - resurs turi indeksi i = 1, m

va ij - xom ashyo xarajatlari i-ishlab chiqarish birligini ishlab chiqarish uchun tur j- turi;

Ai - i-turdagi resurslarning mavjud hajmining berilgan chegarasi;

Pj - j-turdagi mahsulot birligini sotishdan olingan foyda;

xj - j-chi turdagi mahsulot hajmi.

z \u003d P1x 1 + P2x 2 + ... + Pnx n → maks

a11x 1 + a12x 2 +…+ a1nx n ≤ A1

a21x 1 + a22x 2 +…+ a2nx n ≤ A2

…………………………….

a m1x1 + a m2x2 +…+ a m n x n ≤ Am

xj ≥ 0, j = 1, n

6. Ratsionning vazifasi. Muammoning matematik modelini iqtisodiy shakllantirish va qurish.

Iqtisodiy sozlash

Ba'zi fermalar hayvonlarni boqadi. Semirtirish uchun ishlatiladi n ozuqa turlari. Oziq moddalarning (kaltsiy, fosfor va boshqalar) tarkibi har bir turning ozuqa birligiga ma'lum. Hayvonlarning to'g'ri ovqatlanishi uchun ozuqa moddalarini belgilangan miqdordan kam bo'lmagan miqdorda iste'mol qilish kerak. Har bir ozuqa birligining narxi ma'lum. Hayvonlarni boqish ratsionini aniqlash kerak, unda semizlikning umumiy qiymati minimal bo'ladi.

Matematik sozlash:

j - ozuqa turining indeksi, j = 1, n

i – oziq moddalar turi indeksi, i = 1, m

Ai - i-turdagi ozuqa moddalarining kunlik talab qilinadigan miqdori;

Sj - j-chi turdagi yem birligining narxi.

Noma'lum o'zgaruvchilarni kiritamiz:

xj - hayvonlarni boqishning kunlik hajmi j-chi ko'rinish qattiq.

Kiritilgan belgi nuqtai nazaridan topshiriq berilgan keyin yoziladi

a11x1 + a12x2 +…+ a1nxn ≥ A1

a21x1 + a22x2 +…+ a2nxn ≥ A2

…………………………….

am1x1 + am2x2 +…+ va mnxn ≥Am

xj ≥ 0, j = 1, n

7. Transport vazifasi . Muammoning matematik modelini iqtisodiy shakllantirish va qurish.

Iqtisodiy sozlash :

Mavjud m bir hil mahsulotlarni etkazib beruvchilar va n ushbu mahsulot iste'molchilari. Har bir etkazib beruvchidan har bir iste'molchiga mahsulot birligini etkazib berish uchun ma'lum birlik xarajatlari. Yetkazib beruvchi zaxiralari cheklangan. Har bir iste'molchining mahsulotga bo'lgan ehtiyojlari ham ma'lum.

Mahsulotlarni etkazib beruvchilardan iste'molchilarga tashish uchun bunday rejani aniqlash kerak, bunda transportning umumiy qiymati minimal bo'ladi.

Matematik sozlash :

Keling, belgi bilan tanishtiramiz parametrlarni o'rnatish:

j – iste’molchi indeksi, j = 1, n

i – yetkazib beruvchi indeksi, i = 1, m

Ai - i-chi yetkazib beruvchidan mavjud bo'lgan mahsulotlar hajmi;

Bj - j-chi iste'molchining mahsulotiga bo'lgan talab hajmi;

Cij - i-chi yetkazib beruvchidan j-iste'molchiga mahsulot birligini tashish uchun birlik narxi.

Noma'lum o'zgaruvchilarni kiritamiz:

xij - i-etkazib beruvchidan j-iste'molchigacha bo'lgan mahsulotlarni tashish hajmi.

z = S11x11 + S12x12 +…+S1nx1n + S21x21 +…+ Sm(n -1)xm (n-1) + Smnxmn → min

Vazifa cheklovlari.

I. Har bir etkazib beruvchidan siz mavjud miqdordan ko'p bo'lmagan mahsulotlarni olishingiz mumkin:

x11 + x12 +…+ x1n ≤ A1

x21 + x22 +…+ x2n ≤ A2 (2)

…………………….

xm1 + xm2 +…+ xmn ≤ Am

II. Har bir iste'molchining mahsulotga bo'lgan ehtiyoji qondirilishi kerak

x11 + x21 +…+ xm1 ≥B1

x12 + x22 +…+ xm2 ≥B2

……………………. (3)

x1n + x2n +…+ xmn ≥Bn

III. Salbiy bo'lmagan holat: xij ≥0, i = 1, m ; j = 1, n

Ko'pincha matematik bayonotni katlanmış shaklda yozish qulay:

, i = 1, m , j = 1, n

8. Topshiriqlar yoki topshiriqlarni tanlash muammosi. Muammoning matematik modelini iqtisodiy shakllantirish va qurish.

Iqtisodiy sozlash :

Mavjud n ish turlari va n ijrochilar. Ijrochilarning har biri istalgan, lekin faqat bitta ishni bajarishi mumkin. Har bir ijrochi tomonidan har bir ishni bajarish narxi belgilanadi. Ishni yakunlashning umumiy qiymati minimal bo'lishi uchun ijrochilarni ishlashga tayinlash kerak.

Matematik sozlash .

Berilgan parametrlar uchun yozuvni kiritamiz.

i - ishlarning indeksi, i = 1, m

j - ijrochilar indeksi, j = 1, n

Cij - j-ijrochi tomonidan i-ishni bajarish narxi.

Noma'lum o'zgaruvchilarni kiritamiz. Bu masalada noma'lum o'zgaruvchilar faqat ikkita qiymatni qabul qilishi mumkin, 0 yoki 1. Bunday o'zgaruvchilar null o'zgaruvchilar deb ataladi.

1 - agar i-ish uchun j-chi ijrochi tayinlangan bo'lsa;

0 - aks holda.

Kiritilgan belgi nuqtai nazaridan bu muammoni quyidagicha yozish mumkin:

z = S11x11 + S12x12 +…+S1nx1n + S21x21 …+ S(n-1)(n-1)x(n-1)(n-1) + Snnxnn → min

I guruh cheklovlari.

Har bir ish uchun faqat bitta ijrochi tayinlanishi kerak:

x11 + x12 +…+ x1n = 1

x21 + x22 +…+ x2n = 1

……………………..

xn1 + xn2 +…+ xnn = 1

II. cheklash guruhi.

Har bir ijrochi faqat bitta ishni bajarishi mumkin:

x11 + x21 +…+ xn1 = 1

x12 + x22 +…+ xn2 = 1

……………………..

x1n + x2n +…+ xnn = 1

x ij = ( 0,1) i = 1, n ; j = 1, n

9. Materiallarni kesish muammosi. Muammoning matematik modelini iqtisodiy shakllantirish va qurish.

Iqtisodiy sozlash .

Kesish uchun bir xil o'lchamdagi xom ashyo beriladi. Umumiy chiqindilar minimal bo'lishi uchun uni ma'lum miqdorda ma'lum hajmdagi blankalarga kesish talab qilinadi.

Matematik sozlash .

Keling, belgi bilan tanishtiramiz:

i - bo'sh joylar ko'rsatkichi,

Ai - i-chi turdagi blankalarning kerakli soni;

j - kesish variantlari indeksi,

Cj - j variantiga ko'ra boshlang'ich materialning birligini kesishda chiqindilar hajmi;

va ij - j variant bo'yicha boshlang'ich material birligini kesishda i-turdagi blankalar soni.

Noma'lum o'zgaruvchilarning yozuvlari bilan tanishamiz.

xj - j variantiga muvofiq kesilgan xom ashyo miqdori.

Kiritilgan belgi nuqtai nazaridan bu muammoni quyidagicha yozish mumkin:

z \u003d S1x1 + S2x2 + ... + Snxn → min

a11x1 + a12x2 +…+ a1nxn = A1

a21x1 + a22x2 +…+ a2nxn = A2

…………………………….

am1x1 + am2x2 +…+ amnxn =Am

xj ≥ 0, j = 1, n

Matematik modellardan foydalanish xom ashyoni 20% gacha tejash imkonini beradi.

Kesishning matematik modeli ikki bosqichda qurilgan.

Birinchi bosqichda kesish variantlari quriladi, buning natijasida n variantlari sonining qiymatlari, turli xil kesish variantlari (aij) bilan olingan har bir turdagi blankalar soni, shuningdek qiymatlar chiqindilari (Cj) aniqlanadi.

Manba materiali birligini kesish uchun variantlarni qurish quyidagi jadval shaklida amalga oshiriladi:

variant raqami

Bo'sh i1

i2 bo'sh

bo'sh im

Blankalar o'lchamlari bo'yicha ortib bo'lmaydigan tartibda joylashtirilgan. Variantlarni qurish to'liq sanab o'tish usuli bilan amalga oshiriladi.

10. LP muammo modelining umumiy shakli va uning xususiyatlari

MChJning umumiy shakli:

z \u003d S1x1 + ... + Snxn maks (min)

a11 X1 + a12 X2 + … + a1n Xn R1 a1

a21 X1 + a22 X2 + … + a2n Xn R2 a2

………………………………………………….

am1 X1 + am2 X2 +…+ amnxn Rm am

xj ≥ 0, j = 1, k, k ≤ n

Umumiy shaklda har bir belgi R1 , R2 ,…, Rm belgilaridan birini bildiradi: ≥, = yoki ≤ .

LP muammo modelining umumiy shakli quyidagi xususiyatlarga ega.

1. Cheklovlar tizimi tenglamalar (qattiq shartlar) va tengsizliklar (qattiq bo'lmagan shartlar) ko'rinishida taqdim etiladi.

2. Barcha o'zgaruvchilarga manfiy bo'lmagan shartlar qo'yilmaydi

3. Maqsad funksiyasi maksimal yoki minimalga intiladi.

11. LP muammo modelining standart shakli va uning xususiyatlari

Standart shakl quyidagicha.

z maqsad funksiyasining maksimal yoki minimalini toping:

z = S1x1 + … + Snxn → maksimal (min) (1)

Quyidagi cheklovlarga rioya qilgan holda:

a11 X1 + a12 X2 + … + a1n Xn ≤ a1

a21 X1 + a22 X2 + ... + a2n Xn ≤ a2

…………………………………………..

am1 X1 + am2 X2 +… + amn Xn ≥ am

xj ≥ 0, j = 1, k, k ≤ n

LP muammo modelining standart shaklining xususiyatlari quyidagilardan iborat:

1. cheklashlar tizimi tengsizliklar shaklida taqdim etiladi (qattiq bo'lmagan shartlar)

2. barcha o'zgaruvchilarga manfiy bo'lmagan shartlar qo'yiladi

3. maqsad funksiyasi max yoki min ga intiladi

12. LP muammo modelining kanonik shakli va uning xususiyatlari

Kanonik shakl:

z maqsad funksiyasining minimalini toping:

z = S1x1 + … + Snxn → min

Quyidagi cheklovlarga rioya qilgan holda:

a11 X1 + a12 X2 + ... + a1n Xn = a1

a21 X1 + a22 X2 + ... + a2nxn = a2

…………………………

am1x1 + am2 X2 +… + amn Xn = am

Xj ≥0, j = 1, n

Kanonik shaklning xususiyatlari quyidagilardan iborat:

1. Cheklashlar tizimi tenglamalar (qat'iy shartlar) shaklida taqdim etiladi.

2. Salbiy bo'lmagan shartlar barcha o'zgaruvchilarga tegishli

3. Maqsad funksiyasi intiladi

Ba'zi manbalarda kanonik shaklda taqdim etilgan LP muammosining maqsad funktsiyasi maksimalga intiladi. Bu maksimal maqsad funksiyasi uchun ishlab chiqilgan algoritm bo'yicha masalani yechish qulayligi uchun amalga oshiriladi.

13. Mumkin, ruxsat etilgan, optimal asosiy vazifa rejasi, LP vazifasining ODZ

Ta'rif 1. Chiziqli dasturlash muammosining barcha cheklovlarini qondiradigan noma'lum o'zgaruvchilarning qiymatlari deyiladi. joizdir o'zgaruvchan qiymatlar yoki rejalar .

Ta'rif 2. Chiziqli dasturlash muammosining barcha rejalari to'plami o'zgaruvchilarning ruxsat etilgan qiymatlari domeni deb ataladi ( ODZ ).

Ta'rif 3. Maqsad funktsiyasi ODZda minimal (yoki maksimal) qiymatni oladigan chiziqli dasturlash muammosining rejasi deyiladi. optimal .

14. LP vazifalari yozuvlari turlari: kengaytirilgan, katlanmış, matritsa, vektor.

LP muammoli modellari turli shakllarda yozilishi mumkin.

1. Model yozuvining kengaytirilgan ko'rinishi

Z = c1 X1 + c2 X2 + … + cn Xn → min

a11 X1 + a12 X2 + … + a1n Xn = a1,

a21 X1 + a22 X2 + … + a2n Xn = a2,

……………………………………………

a m1 X1 + am2 X2 + … + amn Xn = am,

Xj ≥ 0, j = 1, n.

2. Yiqilgan ko‘rinish:

,

Xj ≥ 0, j = 1, n.

3. LP masalasining matritsa ko‘rinishidagi modeli:

X ≥ 0

Qayerda

a11 a12 … a1n X1 a1

A= a21 a22 … a2n , X= X2 , A0 = a2

… … … … … …

ertalab soat 12:00 …amn X3

4. LP muammosining vektor ko'rinishidagi modeli:

Qayerda

X1 a11 a12 a1n a1

X2 , a21 , a22 , a2n , a2

… … … … …

Xn soat 1:00 2:00

15. LP muammolarining standart va umumiy shaklidan kanonikga o'tish. Ulanish teoremasi

Umumiy yoki standart shakldan kanonik shaklga o'tish uchun quyidagi usullar qo'llaniladi.

1. O'zgaruvchan konvertatsiya. Agar ba'zi Xk o'zgaruvchisi ijobiy bo'lmasa (Xk ≤ 0), u holda yangi Xk " o'zgaruvchisi kiritiladi, shuning uchun Xk " = –Xk . Shubhasiz, Xk " ≥ 0. Shundan so'ng, har bir cheklov va maqsad funktsiyasida Xk o'zgaruvchisi [ bilan almashtiriladi. – Xk "].

Agar ba'zi Xt o'zgaruvchisi har qanday qiymatlarni qabul qila olsa, u holda u ikkita manfiy bo'lmagan Xt' va Xt'' o'zgaruvchilarning ayirmasi bilan almashtiriladi, ya'ni xt = Xt' – Xt'' deb qabul qilinadi, bunda Xt' 0 ≥ va Xt'' ≥ 0.

2. Cheklov konvertatsiyasi. Agar modeldagi cheklovlardan birortasi tengsizlik ko‘rinishiga ega bo‘lsa, uning chap tomoniga qo‘shish (agar tengsizlik ≤ turdagi bo‘lsa) yoki ayirish (agar tengsizlik ≥ turdagi bo‘lsa) yo‘li bilan tenglikka aylantiriladi. Ushbu o'zgaruvchilar balans o'zgaruvchilari deb ataladi. Balans o'zgaruvchilari nol koeffitsientli maqsad funktsiyasiga kiritilgan. Balans o'zgaruvchisi indeks qiymatini mavjud bo'lganlardan keyin ketma-ket qabul qiladi. Agar, masalan, cheklovlar tizimi 5 ta o'zgaruvchiga ega bo'lsa, unda birinchi balans o'zgaruvchisi X6, ikkinchisi esa X7 va boshqalar bo'ladi.

16. ZLP modelining kanonik shaklidan standartga o'tish

Kanonik shakldan standart shaklga o'tish uchun har biri

Tenglamalar tengsizliklar tizimi bilan almashtiriladi:

Yana bir yo'l - tenglamalar tizimini maxsus shaklga keltirish va ba'zi o'zgaruvchilarni keyinchalik yo'q qilish.

Jordan-Gauss usulidan foydalanib, biz har bir tenglamada asosiy o'zgaruvchini tanlaymiz. Bunday tanlash ekvivalent (elementar) Gauss transformatsiyalari yordamida amalga oshiriladi. Bularga quyidagilar kiradi:

a) har qanday tenglamani noldan boshqa doimiyga ko'paytirish;

b) har qanday boshqa tenglamaning istalgan tenglamasiga qo'shilishi, har qanday doimiyga ko'paytiriladi.

O'zgartirishdan oldin chiziqli tenglamalarning boshlang'ich tizimini matritsa yoki jadval shaklida yozish qulay:

Muammoni standart shaklda yozamiz.

17. Yarim tekislikning giper tekisligi, tayanch giper tekisligi haqida tushuncha.

18. Geometrik. LP masalalarida cheklovlar tizimini va maqsad funktsiyasini talqin qilish

19. Qavariq to'plam: to'plamning ekstremal (burchak) nuqtalari. Qavariq ko‘pburchak

Ta'rif M to'plamga tegishli bo'lgan har qanday ikkita nuqta bilan birga qavariq deyiladi berilgan to'plam, shuningdek, ularni bog'laydigan segmentni ham o'z ichiga oladi.

konveks to'plami

Ta'rif M to'plamning x nuqtasi, agar u berilgan to'plamga to'liq tegishli bo'lgan biron bir segmentning ichki qismi bo'lmasa, burchak yoki ekstremal nuqta deyiladi.

Teorema 1. Segmentning istalgan nuqtasi uning burchak nuqtalarining konveks birikmasi sifatida ifodalanishi mumkin.

x \u003d l 1 A + l 2 B

l 1, l 2 ≥ 0 A va B burchak nuqtalarining konveks birikmasi

l1 + l2 = 1

Teorema 2. Qavariq yopiq to'plamning istalgan nuqtasi uning burchak nuqtalarining qavariq birikmasi sifatida ifodalanishi mumkin.

20. LP masalalarini echishning grafik usulining algoritmi

1. Asl LPP standart shaklda yoki yo'qligi tekshiriladi, agar bo'lmasa, topshiriq standart shaklga o'tkazilishi kerak.

2. Noma'lum o'zgaruvchilar soni tekshiriladi. Agar bu raqam uchdan ortiq bo'lsa, muammoni grafik usul bilan hal qilib bo'lmaydi (boshqalar ham bor samarali usullar kabi muammolarni hal qilish).

3. ZLP uchun o'zgaruvchilarning ruxsat etilgan qiymatlari mintaqasi qurilmoqda.

4. Yo'naltiruvchi vektor qurilmoqda c .

5. Dastlabki izotel ODZ (yo'nalish vektoriga perpendikulyar) orqali o'tkaziladi.

6. Vektor yo'nalishi bo'yicha dastlabki izokoelning aqliy harakati amalga oshiriladi c, agar maqsad funktsiyasining maksimal qiymati aniqlansa yoki qarama-qarshi yo'nalishda, agar uning minimal qiymati aniqlansa, izomaqsad ODZga havola bo'lgunga qadar. Malumot izokoel va ODZning kesishish nuqtalari masalaning optimal nuqtalari bo'ladi.

7. Optimal nuqtaning koordinatalarini aniqlash uchun tegishli chiziqli tenglamalar tizimini yechish kerak.

8. Maqsad funktsiyasining optimal qiymatini topish uchun o'zgaruvchilarning optimal qiymatlarini maqsad funktsiyasiga almashtirish va uning qiymatini hisoblash kerak.

20. grafik algoritm. LP muammoni hal qilish usuli

Grafik usulning algoritmi.

1. Muammoning cheklashlar tizimining har bir shartini ketma-ket qurish orqali ODZni qurish amalga oshiriladi.

2. Yo'naltiruvchi vektor C maqsad funktsiyasining o'zgaruvchilari uchun koeffitsientlar bilan tuziladi.

3. Boshlang‘ich izokoel koordinata vektoriga perpendikulyar koordinatalar koordinatalari orqali o‘tkaziladi.

4. Boshlang‘ich izomaqsad, agar maqsad funksiyasining maksimal qiymati aniqlansa, C vektorining qiymatlarini oshirish yo‘nalishi bo‘yicha yoki agar uning minimal qiymati aniqlansa, teskari yo‘nalishda, izomaqsad a bo‘lgunga qadar aqliy harakatga keltiriladi. ODZga havola. Malumot izokoel va ODZning kesishish nuqtalari masalaning optimal nuqtalari bo'ladi.

5. Optimal nuqtaning koordinatalarini aniqlash uchun kesishmasida optimal nuqta joylashgan sharoitlarning mos chiziqli tenglamalari tizimini yechish kerak.

6. Maqsad funksiyasining optimal qiymatini topish uchun optimal nuqtaning koordinatalarini maqsad funksiyasiga almashtirish va uning qiymatini hisoblash kerak.

23. LP masalasining ruxsat etilgan qiymatlari diapazoni va maqsad funksiyasi haqidagi teoremalar

ODZ teoremasi. LP muammosining ruxsat etilgan yechimlari sohasi konveks to'plamdir (n o'lchovli fazoda yopiq va cheklangan)

Teorema 2. Chiziqli dasturlash masalasining maqsad funksiyasi haqida.

LLP maqsad funktsiyasi o'zining maqbul qiymatini o'zgaruvchilarning maqbul qiymatlari mintaqasining burchak nuqtalaridan birida oladi. Agar maqsad funksiyasi bir nechta burchak nuqtalarida optimal qiymatini qabul qilsa, u holda bu burchak nuqtalarining qavariq birikmasi bo'lgan har qanday nuqtada bir xil qiymatni oladi.

24. Burchak nuqtasi haqidagi teorema. Etarli va zarur shart

25. LP masalalari yechimlari xossalari haqidagi teoremadan xulosalar va xulosalar. Asosiy chiziq tushunchasi.

Teoremalardan olingan natijalar.

Ta'rif. Reja = (x1,x2,…,xn), musbat koordinatalari chiziqli mustaqil vektorlarga to'g'ri keladi. PLP asosiy rejasi .

Natija 1. Malumot rejasi m dan ortiq ijobiy koordinatalarga ega emas.

Agar u aniq m musbat koordinatalarga ega bo'lsa, unda bunday qo'llab-quvvatlash dizayni buzuq bo'lmagan, aks holda degeneratsiya deb ataladi.

Natija 2. Har biri burchak nuqtasi ODZ asosiy rejadir.

27. Simpleks usulining algoritmi.

LP masalalarini simpleks usuli bilan yechishda quyidagi harakatlar ketma-ketligini bajarish kerak.

1. LP muammosining kanonik shaklda ekanligi tekshiriladi. Agar yo'q bo'lsa, unda asl modelni kanonik shaklga aylantirish kerak.

2. Ushbu tayanch reja uchun dastlabki mos yozuvlar rejasi va maqsad funksiyasining qiymati tanlanadi.

3. Dastlabki simpleks jadvali tuziladi.

4. Indeks qatoridagi optimallik baholarining qiymatlari tekshiriladi. Agar ijobiy baholar bo'lmasa, u holda optimal yechim yoziladi va algoritm o'z ishini tugatadi. Aks holda, 5-band bajariladi.

5. Bazada eng katta ijobiy bahoga mos keladigan vektor kiritiladi. Bu ustun yoqish ustuni deb ataladi.

6. Bazisdan vektor olinadi, u 0 formula bilan hisoblangan simpleks nisbatiga mos keladi< Ө ≤ . Berilgan qator yoqish satri deb ataladi.

7. Yangi simpleks jadvali qurildi. B va C B ustunlari mos ravishda o'zgartiriladi.Jadvalning qolgan qismi avvalgisidan Gauss o'zgartirishlari yordamida to'ldiriladi, indeks qatori m+1 qator deb hisoblanadi va Gauss o'zgartirishlari yordamida ham o'zgartiriladi. Biz ushbu algoritmning 4-bandini bajarishga o'tamiz.

Har bir jadvalni tuzganingizdan so'ng, oldingi paragrafda keltirilgan hisob-kitoblarni hisoblash uchun formulalar yordamida hisob-kitoblarning to'g'riligini tekshirishingiz mumkin.

28. Simpleks usulida masalalarni yechish uchun asos tanlash va dastlabki tayanch rejasini qurish.

29. Simpleks jadvallar, ularni to'ldirish. Indeks qatori koeffitsientlarini hisoblash formulalari.

30 . Chiziqli dasturlash masalasi rejasi uchun optimallik teoremasi masalalarni simpleks usulida yechish uchun optimallikni baholash teoremasining natijasidir.

Teorema 1: tizimdagi ba'zi vektor Ā j uchun bo'lsa

X 1 + a 1 m +1 X m +1 + a 1 m +2 X m +2 + ... + a 1 n X n \u003d a 1

X 2 + a 2 m +1 X m +1 + a 2 m +2 X m +2 + ... + a 2 n X n \u003d a 2

…………………………………………………..

X m + a mn +1 X m +1 + a mn +2 X m +2 + ... + a mn X n = a m

Z j – c j > 0 munosabati bajariladi, u holda X B0 rejasi optimal emas va X B1 rejasiga shunday o‘tish mumkinki, Z (X B1) ≤ Z (X B0).

Bu yerda Z j = (S, Ā j) vektorlarning skalyar ko‘paytmasi.

C - Z maqsad funktsiyasining asosiy o'zgaruvchilaridagi koeffitsientlardan tashkil topgan vektor

Ā j - bazis vektorlari bo'yicha mos vektorning kengayish koeffitsientlaridan tashkil topgan vektor.

c j - maqsad funksiya Z koeffitsienti X j o'zgaruvchisi

Natija dan teoremalar: Agar qandaydir X referent rejaning barcha vektorlari Ā 1, Ā 2, …, Ā n bo‘lsa, Z j – c j munosabati< 0, то опорный план Х является оптимальным. Величины (Z j – c j) – называются оценками оптимальности соответствующих векторов.

Shunday qilib, teorema va natija bizga keyingi qo'llab-quvvatlash rejasining maqbul yoki yo'qligini aniqlashga imkon beradi va agar bo'lmasa, maqsad funktsiyasining qiymati kamroq bo'lgan boshqa qo'llab-quvvatlash rejasiga o'tish kerak.

Izoh. Teorema va xulosa muammoning minimal maqsad funksiyasi bilan kanonik shaklda ekanligini taxmin qiladi. Shu bilan birga, simpleks usulidan maksimal maqsad funksiyali masalalarni yechishda ham foydalanish mumkin. Bunday holda, baholarning qiymatlarini tahlil qilishda ularning qarama-qarshi ma'nosi qo'llaniladi, ya'ni barcha optimallik baholari salbiy (ijobiy yoki salbiy) bo'lsa, reja optimal bo'ladi.

31. Bazisga kiruvchi va bazisdan kelib chiquvchi vektorni tanlash. Simpleks munosabat.

Yangi mos yozuvlar rejasiga o'tish uchun bepul vektorlardan biri kerak bazisga kiriting va bazis vektorlarining bir qismini chiqaring. Bazaga kiritish uchun biz kamida bitta ijobiy koordinataga ega vektorni tanlaymiz. A m+1 vektor shunday vektor bo'lsin.

parchalanish -

Javob. vektor, mushuk. uning koordinatalari manfiy bo'lmasa, mos yozuvlar rejasi bo'ladi va ijobiy koordinatalar soni m ga teng bo'ladi.

X1 vektor koordinatalari manfiy bo'lmasligi kerak, ya'ni. .

Agar , keyin bu koordinata manfiy bo'lmaydi.

(5) ga nisbatan minimal i =1 da olinsin, agar olsak

keyin vektorning birinchi koordinatasi 1 X nolga aylanadi.

(6) munosabat deyiladi simpleks munosabati. Shunday qilib, biz boshlang'ich 0 dan ko'chdik X(asosiy vektorlar A1, A2, ... Am) 1 mos yozuvlar rejasiga X(asosiy vektorlar A2,A3,…,Am, Am+1).

32. jadvalning ruxsat beruvchi elementi, uni tanlash. Simpleks jadvalini qayta hisoblash uchun to'liq Iordaniyani yo'q qilish qoidasi.

33. Simpleks jadvalini qayta hisoblashning to'rtburchak qoidasi

34. LP masalasini simpleks usulida yechishda optimal rejaning o'ziga xosligi, optimal rejalar to'plami va optimal rejaning yo'qligi belgisi.

Simpleks usuli bilan muammolarni yechishda quyidagi turdagi optimal echimlar mumkin:

1. O'ziga xoslik . Agar barcha erkin vektorlarning taxminlari qat'iy manfiy bo'lsa, unda olingan qo'llab-quvvatlash dizayni optimal va noyobdir. (oldingi xatboshidagi misolga qarang).

2. Alternativ optimal (optimal echimlar to'plami).

Agar erkin vektorlarning ijobiy bo'lmagan baholari orasida kamida bitta nol baho bo'lsa, unda olingan qo'llab-quvvatlash dizayni optimal bo'ladi, lekin yagona emas. Bunday holda, siz boshqa qo'llab-quvvatlash rejalariga o'tishingiz mumkin (nolga mos keladigan vektorlar asosga kiritiladi) va keyin olingan optimal qo'llab-quvvatlash rejalarining konveks kombinatsiyasi sifatida umumiy optimal echimni yozishingiz mumkin.

3. LLP optimal yechimga ega emas, chunki maqsad funktsiyasi pastdan chegaralanmagan . Simpleks jadvali ijobiy ballga ega bo'lsa va barcha elementlar berilgan ustun manfiy va nolga teng berilgan vektor asosga kiritilishi mumkin. Biroq, bazis vektorlarining hech birini bazisdan chiqarib bo'lmaydi. Bundan kelib chiqadiki, qo'llab-quvvatlanmaydigan rejaga o'tishda maqsad funktsiyasining yanada pasayishi mumkin.

4. LLP optimal yechimga ega emas, chunki cheklovlar tizimi mos kelmaydi. LLP ni hal qilishda odatiy simpleks usuli dastlabki mos yozuvlar rejasi bo'lishi kerakligi sababli, chiziqli tenglamalar tizimi, albatta, mos kelmaydi. Shuning uchun odatiy simpleks usuli bilan yechishda bunday holat yuzaga kelishi mumkin emas.

5. Agar ODZ bir nuqtadan iborat bo'lsa, unda bunday masalaning yechimi ahamiyatsiz bo'lib, uni simpleks usulidan foydalanmasdan olish mumkin.

35. Sun'iy bazis usuli qachon qo'llaniladi?

sun'iy.

36. M-muammoni sun'iy bazis usulida qurish

Agar chiziqli dasturlash muammosi kanonik shaklda bo'lsa, lekin barcha tenglamalar asosiy o'zgaruvchilarni o'z ichiga olmaydi, ya'ni asl asosiy chiziq yo'q. Bunday holda, asosiy o'zgaruvchilar mavjud bo'lmagan tenglamalarga +1 koeffitsienti bilan ba'zi salbiy bo'lmagan o'zgaruvchilarni qo'shish kerak. Bunday o'zgaruvchi deyiladi sun'iy.

Maqsad funktsiyasiga juda katta musbat sonli sun'iy o'zgaruvchi qo'shilishi kerak (chunki maqsad funktsiyasi minimalni topishdir). Bu raqam belgilangan Lotin harfi M. Uni +∞ ga teng deb hisoblash mumkin. Shu munosabat bilan ba'zan sun'iy asos usuli M-usuli deb ataladi. Asl masalaning bunday o'zgarishi kengaytirilgan masalani qurish deyiladi. Agar siz sun'iy o'zgaruvchini topish uchun maqsad funktsiyasi bilan muammoni hal qilsangiz, juda katta musbat sonli maqsad funktsiyasiga qo'shishingiz kerak (chunki maqsad funktsiyasi minimalni topishdir). Bu raqam lotincha M harfi bilan belgilanadi. Uni +∞ ga teng deb hisoblash mumkin. Shu munosabat bilan ba'zan sun'iy asos usuli M-usuli deb ataladi. Asl masalaning bunday o'zgarishi kengaytirilgan masalani qurish deyiladi. Agar muammo maksimalni topish uchun maqsad funksiyasi bilan echilayotgan bo'lsa, sun'iy o'zgaruvchilar maqsad funksiyaga -M koeffitsienti bilan kiradi.

Shunday qilib, kengaytirilgan muammoda biz asosiy chiziqqa egamiz (ba'zi asosiy o'zgaruvchilar sun'iy bo'lsa ham).

Dastlabki simpleks jadvali tuzilgan.

37. sun'iy bazis usulida indeks chizig'ini qurish

Boshlang'ich simpleks jadvali tuziladi, unda indeks qatori ikki qatorga bo'linadi, chunki hisob-kitoblar ikki shartdan iborat. Yuqori satrda M holda smeta muddati, pastki qatorda M da koeffitsientlar ko'rsatilgan. Baholash belgisi M da koeffitsient belgisi bilan belgilanadi, M bo'lmagan muddatning qiymati va belgisidan qat'i nazar, chunki M - juda katta ijobiy raqam.

Shunday qilib, asosga kiritilgan vektorni aniqlash uchun pastki indeks chizig'ini tahlil qilish kerak. Agar bazisdan sun'iy vektor olingan bo'lsa, ikkilamchi muammoning echimini olishning hojati bo'lmasa, keyingi simpleks jadvallarida tegishli ustunni o'tkazib yuborish mumkin (keyingi mavzuga qarang).

Barcha sun'iy vektorlar asosdan chiqarilgandan so'ng, pastki qatorda barcha nol elementlar bo'ladi, sun'iy vektorlarga mos keladigan baholar bundan mustasno. Ular -1 ga teng bo'ladi. Bunday chiziq ko'rib chiqilishidan olib tashlanishi mumkin va keyingi yechim odatdagi simpleks usuli bilan amalga oshirilishi mumkin, agar ikki tomonlama muammoning echimini olishning hojati bo'lmasa (keyingi mavzuga qarang).

38. Sun'iy bazis usulida optimallik mezoni. Belgisi - asl vazifaning dastlabki asosiy rejasini qurish.

39. Dual simpleks usulining algoritmi

Dual simpleks usuli algoritmi:

1. birinchi simpleks jadvalini erkin a'zolar belgilaridan qat'i nazar, odatiy tarzda to'ldiring. Bunday muammoning dastlabki birlik asosiga ega bo'lishi kerak, deb ishoniladi.

2. A0 erkin a'zolar ustunining eng katta mutlaq salbiy elementi bo'yicha yo'naltiruvchi chiziqni tanlang

3. Qo'llanma ustuni indeks chizig'i elementlarining hidoyat chizig'ining salbiy elementlariga nisbatining eng kichik mutlaq qiymatiga muvofiq tanlanadi.

4. Simpleks jadvalini to'liq Iordaniyani yo'q qilish qoidasiga ko'ra qayta hisoblang

5. qabul qilingan rejani qabul qilinishini tekshiring. Qabul qilinadigan mos yozuvlar rejasini olish belgisi A0 ustunida salbiy elementlarning yo'qligi hisoblanadi. Agar A0 ustunida salbiy elementlar mavjud bo'lsa, ikkinchi xatboshiga o'ting. Agar ular yo'q bo'lsa, ular muammoni odatiy tarzda hal qilishga kirishadilar.

6. Dual simpleks usulida optimal yechimni olish belgisi oddiy simpleks usuli uchun optimallik mezoni hisoblanadi.

41. Ochiq va yopiq transport modellari. Ochiq transport modelidan yopiq modelga o'tish.

Transport vazifalari turlari.

Mavjud m mahsulotlarning ma'lum zahiralari bilan bir hil mahsulotlar yetkazib beruvchilar va n ma'lum hajmdagi ehtiyojlar bilan ushbu mahsulotlarning iste'molchilari. Tashish birligi xarajatlari ham ma'lum.

Agar mahsulot zahiralari hajmlarining yig'indisi barcha iste'molchilarning ehtiyojlari hajmiga teng bo'lsa, unda bunday muammo deyiladi. yopiq transport vazifasi

(ya'ni, ∑ Ai = ∑ Bj bo'lsa), aks holda transport muammosi deyiladi. ochiq. Transport muammosini hal qilish uchun uni yopish kerak.

Ochiq tashish vazifasini quyidagi tarzda yopiq vazifaga aylantirish mumkin.

∑Ai > ∑Bj bo'lsin. Bunday holda, ehtiyojlar hajmi ∑Ai – ∑Bj bo'lgan soxta n + 1 iste'molchini joriy qilish kerak.Yetkazib beruvchilardan soxta iste'molchiga tashish uchun birlik xarajatlari 0 ga teng deb hisoblanadi, chunki aslida bunday tashish bo'lmaydi. amalga oshiriladi va mahsulotlarning bir qismi etkazib beruvchilarda qoladi.

Agar ∑Bj > ∑Ai bo'lsa. Bunday holda, inventar hajmi ∑Bj – ∑Ai bo'lgan xayoliy m + 1 yetkazib beruvchini joriy qilish kerak. Xayoliy etkazib beruvchidan iste'molchilarga tashish birlik xarajatlari 0 ga teng deb hisoblanadi, chunki aslida bunday tashish amalga oshirilmaydi va iste'molchilar mahsulotlarning bir qismini olmaydilar.

42. Tashish masalasida dastlabki taqsimotni qurish usullari: shimoli-g'arbiy burchak usuli va matritsadagi eng kichik element usuli.

Malumot rejasini tuzish uchun shimoli-g'arbiy texnika. Ushbu texnikaga ko'ra, trafik qiymatlarini shakllantirish s.-z bilan boshlanadi. stol burchagi, ya'ni. x11 uyasidan. Ushbu usulga ko'ra, birinchi navbatda, birinchi etkazib beruvchining tovarlari taqsimlanadi. Bundan tashqari, birinchi etkazib beruvchi birinchi iste'molchini iloji boricha qoniqtiradi. Keyin, agar etkazib beruvchida hali ham tovarlar bo'lsa,

Matritsadagi eng kichik element usuli.

Usulning mohiyati shundan iboratki, maksimal mumkin bo'lgan ta'minot har doim matritsaning eng past tarifiga mos keladigan hujayraga qo'yiladi.

Birinchidan, biz chiziq uchun eng past narx kuzatilgan chiziqlarning kataklarida belgilar qo'yamiz (masalan, ▼ belgisi bilan). Keyin biz ustunlar bo'yicha jadvalni aylanib chiqamiz va ustunlar bo'yicha eng kichik narx bo'lgan katakchalarda bir xil yozuvlarni qilamiz.

Keyinchalik taqsimlash birinchi navbatda ikkita belgili hujayralar bo'ylab imkon qadar amalga oshiriladi, so'ngra - bittasi bilan, so'ngra muammo (m + n - 1) plombalarga muvozanatlanadi. Jadvalni chapdan o'ngga va yuqoridan pastga o'tkazishda to'ldirishni tashkil qilamiz.

43. Transport vazifalarining xossalari

Transport muammosi quyidagi teoremalarda aks ettirilishi mumkin bo'lgan ba'zi xususiyatlarga ega.

Teorema 1. Yopiq transport muammosi har doim yechimga ega.

Teorema 2. Agar mahsulot zahiralari hajmi va ehtiyojlar hajmi butun sonlar bo'lsa, transport masalasining yechimi ham butun son bo'ladi.

Teorema 3. yopiq transport muammosining cheklovlar tizimi doimo chiziqli bog'liqdir.

Bu teoremadan kelib chiqadiki, yopiq transport masalasini taqsimlash har doim m + n – 1 ta asosiy oʻzgaruvchiga va (m – 1) (n – 1) boʻsh vaqt oʻzgaruvchisiga ega boʻladi.

44. Transport muammolarida degeneratsiya taqsimoti, degeneratsiyadan qutulish. Chizilgan kombinatsiya.

Agar hujayralar soni m + n - 1 dan kam bo'lsa, taqsimot degenerativ deb ataladi.

45. Transport masalasi uchun optimallik teoremalari.

Teorema. Agar transport vazifasini ba'zi taqsimlash uchun siz

shartlar bajariladi:

A). ui+vj = ishg'ol qilingan hujayralar uchun cij

b) ui+vj ≤ sij, erkin hujayralar uchun,

u holda bu taqsimot optimal hisoblanadi.

Ui qiymatlari qator potentsiallari, vj qiymatlari esa ustun potentsiallari deb ataladi.

46. ​​Potentsiallar va ularni hisoblash usullari.

Qator va ustunlarning potentsiallarini topish uchun optimallik teoremasining a) shartiga asoslanib, quyidagi mulohazalardan foydalaniladi.

Bu shart asosida tuzilgan tenglamalar soni m + n – 1, ui va vj noma’lumlar soni esa m + n. Bu. o'zgaruvchilar soni tenglamalar sonidan ko'p va barcha tenglamalar chiziqli mustaqildir. Bunday chiziqli tenglamalar tizimining yechimi noaniq, shuning uchun potentsiallardan biriga istalgan qiymat berilishi kerak. Amalda ui = 0. m + n – 1 noma’lum o‘zgaruvchiga ega m+n – 1 tenglamalar sistemasi olinadi. Ushbu tizimni har qanday usul bilan hal qilish mumkin. Amalda potentsiallarni hisoblash uchun egallangan hujayralar hisobga olinadi, ular uchun potentsiallaridan biri ma'lum bo'ladi va teoremaning a) sharti asosida qolgan noma'lum potentsiallarning qiymatlari hisoblanadi.

47. Transport vazifalarini taqsimlashning optimalligini baholash va optimallik mezonini hisoblash.

Teoremaning b) munosabatiga asoslanib, taxminlarni hisoblash uchun quyidagi formulani yozishimiz mumkin: d ij= ui + vj – sij. Hisob-kitoblarni transport hajmlari bilan aralashtirib yubormaslik uchun ular (baholashlar) aylanalarga o'ralgan.

Erkin TK hujayralarida optimallikni baholash optimallik uchun taqsimotni tekshiradigan optimallik mezoni hisoblanadi. Agar barcha bo'sh hujayralarning baholari noldan kichik yoki teng bo'lsa, bu taqsimot optimal hisoblanadi.

48. transport muammosida zaxiralarni qayta taqsimlash

Agar taqsimlash optimal bo'lmasa, unda materiallarni qayta taqsimlash kerak.

Qayta taqsimlash uchun qayta hisoblash tsikli quriladi. Eng yuqori ijobiy ballga ega bo'lgan katak hujayra sifatida tanlanadi. Ushbu katak "+" belgisi bilan belgilangan, ya'ni unda ma'lum miqdorda etkazib berishni yozish kerak. Ammo keyin bu ustundagi muvozanat buziladi, shuning uchun ushbu ustunning egallangan kataklaridan biri "-" belgisi bilan belgilanishi kerak, ya'ni etkazib berish hajmi bir xil miqdorda kamayishi kerak. Ammo keyin bu chiziq uchun balans o'zgaradi, shuning uchun ushbu chiziqning ba'zi band qilingan kataklari "+" belgisi bilan belgilanishi kerak. Bu jarayon asl katak joylashgan qatorga “-” belgisi qo'yilguncha davom etadi.

Har qanday bepul hujayra uchun qayta hisoblash tsikli mavjud va bundan tashqari, yagona.

49. qayta taqsimlash zanjirlari, ularning turlari.

Ko'rib chiqilayotgan transport rejasi optimal bo'lmasin, ya'ni. ijobiy nisbiy baholar mavjud. Keyin noqulay hujayra olinadi (noqulay bo'lganlardan biri) va uning uchun qayta hisoblash tsikli quriladi, unga ko'ra rejalashtirilgan transport qayta taqsimlanadi. Tsikl singan yopiq chiziq shaklida qurilgan, uning segmentlari ustun bo'ylab yoki chiziq bo'ylab o'tadi. Buzilgan chiziqning burchaklaridan birida mahsulotni da'vo qiladigan noqulay hujayra mavjud, boshqa burchaklarda esa hujayralar to'ldiriladi, ya'ni. siklni qurishda biz nomzod katakchadan boshlaymiz va unga siniq chiziq bo'ylab qaytamiz, lekin biz faqat to'ldirilgan kataklarda (asosiy o'zgaruvchilarga mos keladigan) burilishlar qilishimiz mumkin. Noqulay hujayra Q mahsulotiga da'vo qilsin. Jadvaldagi nomutanosiblikni oldini olish uchun, o'z navbatida, tsikl bo'ylab o'tishlarda kerak.

mavjud trafikga Q qo'shing va ayiring. Burchaklar soni juft bo'lganligi sababli, Q yacheykalarning yarmiga qo'shiladi, ikkinchi yarmida esa ayiriladi. Tsikl nomzod katakchadan soat yo'nalishi bo'yicha yoki teskari yo'nalishda boshlanadi, u erda Q tovarlarni qo'yadi, so'ngra qo'shni katakdan Q ayiriladi, keyin qo'shiladi va hokazo. Q qiymatining o'zi shunday tanlanadiki, hujayralardan biri bo'shatiladi, ammo zaxiralarning hech biri salbiy bo'lmaydi.

Buning uchun Q ayiriladigan katakchalarning eng kichik qaytarilishiga teng Q tanlanishi kerak. Quyidagi rasmda. 7.1 va 7.2 biz tsikllar misollarini va hisoblash qoidasini ko'rsatamiz.

Bunday holda, ikkita hujayra bo'shatiladi. Ammo faqat bitta hujayra o'zaro bo'sh bo'lishi kerak. Ular shunday qilishadi: bo'shatilgan kataklardan biri yangi jadvalda bo'sh holga keltiriladi va boshqa bo'sh yacheykaga nol qo'yiladi. Ushbu katak yangi jadvalda asosiy (to'ldirilgan) hisoblanadi.

50. Qayta taqsimlash hajmini tanlash.

Tashiladigan mahsulotlar hajmini aniqlash. Hisoblash siklidan o'tgan mahsulotlar hajmini aniqlashda biz quyidagi ikkita fikrdan kelib chiqishimiz kerak:

a) jadval katakchalarida transformatsiya qilinganidan keyin manfiy raqamlar olinmasligi kerak;

b) egallagan hujayralardan biri bo'sh bo'lishi kerak.

Ushbu shartlarni bajarish uchun tashilgan mahsulot hajmini quyidagicha tanlash kerak: th=min (xij) -, bu erda (xij) - qayta hisoblash tsiklining katakchalaridan "" belgisi bilan belgilangan tashish hajmi. -” belgisi.

th = min(20;30)=20

th "+" belgisi bilan belgilangan kataklarning qiymatlariga qo'shiladi. th "-" belgisi bilan belgilangan kataklarning qiymatlaridan ayiriladi. Qolgan kataklarning ta'minot qiymati o'zgarishsiz qayta yoziladi. Natijada biz quyidagi jadvalni olamiz.

53. Potentsiallar usulining algoritmi.

Algoritm:

1. Vazifa uchun tenglama qanoatlanganligini tekshiring bo'lmasa, xayoliy yetkazib beruvchi yoki iste'molchi vazifaga kiritiladi

2. Topshiriq sharti transport.jadval shaklida yoziladi

3. Dastlabki baza qurilmoqda

4. Ta'minot va iste'molchilarning salohiyati aniqlanadi

5. Erkin hujayra ballari hisoblanadi. Agar ularning barchasi salbiy bo'lmasa, reja optimaldir va siz javobni yozishingiz kerak. X transport matritsasi va transport xarajatlari miqdorini aniqlang. Agar reja optimal bo'lmasa, ya'ni hisob-kitoblar orasida salbiy bo'lsa, u holda eng katta salbiy qiymatga ega bo'lgan istiqbolli katakchani tanlang. baholang va kattaligidan keyingisiga o'ting.

6. Perspektiv katakchani yuklang. Transport jadvali ko'rinishida yangi asosiy rejani tayyorlang. 4-bandga o'ting.

54. Mahsulotlarni ishlab chiqarish va tashish tannarxini hisobga olish. Ta'minot taqiqlari bilan transport vazifasi.

Ayrim muammolarni hal qilishda nafaqat yuklarni tashish, balki tashiladigan mahsulotlarni ishlab chiqarish xarajatlarini ham hisobga olish kerak. Buning uchun matritsada transp. vazifalar

Bu erda Cij ' - bir mahsulot birligini ishlab chiqarish uchun tushgan xarajatlar.

Cij "- mahsulotning bir birligini tashish xarajatlari.

Ta'minot taqiqlangan vazifalar.

Ba'zi hollarda mahsulotlarni istalgan yo'nalishda tashish mumkin emas.

Buning uchun transport vazifasi matritsasiga, u orqali tashish taqiqlangan, taqiqlovchi tarif M kiritiladi.Bundan tashqari, vazifa odatdagi usulda hal qilinadi.Lekin bu katak har doim manfiy katak balliga to'g'ri keladi.

55. transport muammosida ayrim yetkazib berishlarning majburiy xususiyatini hisobga olgan holda, marshrutlarning o'tkazuvchanligi bo'yicha cheklovlarni hisobga olgan holda.

marshrutlarning o'tkazuvchanligi bo'yicha cheklovlarni hisobga olish.

Ba'zi transport vazifalarida, ba'zi marshrutlarda, kichikroq o'tkazish qobiliyati iste'mol nuqtasi talabini qondirish uchun zarur bo'lganidan ko'ra.

transport muammosida ba'zi etkazib berishlarning majburiy xususiyatini hisobga olgan holda.

Ba'zi hollarda, vazifa, masalan, Ak Bs yo'nalishi bo'ylab, A hajmida birliklarni etkazib berishni talab qiladi. Bunda majburiy ta'minot A nuqta ishlab chiqarish hajmidan va S Bs hajmidan chegirib tashlanadi va ixtiyoriy ta'minotga nisbatan masala hal qilinadi. Optimal yechim olingandan so'ng, ta'minot Ak Bs katakchasida turgan hajmga qo'shiladi.

56. Iqtisodiy bilan mumkin bo'lgan xulosalar. ochiq transport muammolari uchun optimal taqsimotni talqin qilish.

Optimal taqsimotni olgandan so'ng, asl muammoga qaytish va tegishli tejamkorlik qilish kerak. xulosalar. Ular quyidagilar:

1. Agar iste'mol nuqtasi joriy etilsa, bu tahlil qilinayotgan tizimda ortiqcha ishlab chiqarish hajmlari mavjudligini anglatadi va ko'rib chiqilayotgan tizimga zarar etkazmasdan, ushbu ishlab chiqarish punktlarining quvvatlarini bog'lash miqdori bilan kamaytirish mumkin. xayoliy iste'mol nuqtasiga bog'langan.

2. Agar xayoliy ishlab chiqarish punkti joriy etilsa, bu real ishlab chiqarish punktlarining quvvatlari yetarli emasligini va ularni oshirish zarurligini bildiradi. Xayoliy ishlab chiqarish punkti bilan bog'langan iste'mol punktlariga eng yaqin bo'lgan ishlab chiqarish punktlarining quvvati oshiriladi. Ishlab chiqaruvchining quvvati majburiy qiymat bilan oshiriladi. Buning uchun ishlab chiqarishning xayoliy nuqtasiga bog'langan iste'mol nuqtasi ustunini ko'rib chiqing va undagi eng past tarifni toping. Ushbu tarifga mos keladigan ishlab chiqarish punktining quvvatini bog'lash miqdori bilan oshirish eng samarali hisoblanadi.

57. Ikkilik tushunchasi. Ishlab chiqarish rejasini optimallashtirish muammosi misolida ikkilamchi masalalarni iqtisodiy shakllantirish.

Ikkilamchi muammo - bu asl yoki to'g'ridan-to'g'ri muammoning shartlaridan to'g'ridan-to'g'ri ma'lum qoidalardan foydalangan holda tuzilgan chiziqli dasturlashning yordamchi muammosi.

Ishlab chiqarish rejasini optimallashtirish vazifasi bo'lsin. Bu shunday ko'rinadi:

Dastlabki vazifa:

a 11 x 1 + a 12 x 2 +…+ a 1p x p ≤v 1 | 1

a 21 x 1 + a 22 x 2 +…+ a 2p x p ≤v 2 | 2 da

……………….. |.. (1)

A T 1 x 1 +a T 2 x 2 + ... + a T n x n ≤v 1 | da T

x j ≥0, j = 1,n(2)

z = c 1 x 1 +c 2 x 2 +…+c n x n ->max(3)

X \u003d (x 1, x 2, ..., x n)

a ij - j-turdagi mahsulot ishlab chiqarish uchun sarflangan i-turdagi xom ashyolar soni.

Ikki tomonlama muammo

Korxona biron sababga ko'ra mahsulot ishlab chiqara olmasin. To'xtab qolish xarajatlarini kamaytirish uchun kompaniya o'zida mavjud bo'lgan xom ashyoni sotishi mumkin. Xom ashyoni qanday narxda sotish kerak?

i - korxonada mavjud bo'lgan i-turdagi xom ashyoning narxi.

a 11 y 1 + a 21 y 2 + ... + a T 1 y T≥s 1

a 12 x 1 + a 22 y 2 + ... + a T 2 x n ≥s 2

……………….. (1’)

A 1p y 1 +a 2p y 2 +…+ a tp da T≥s P

i ≥0, j = 1,m(2’)

F = b 1 y 1 +b 2 y 2 +…+b m y m ->min(3’)

58. To'g'ridan-to'g'ri va ikkilamchi muammolarning tarkibiy elementlari o'rtasidagi moslik

Har bir chiziqli dasturlash muammosi bog'lanishi mumkin

quyidagi qoidalarga muvofiq dual vazifa:

1. Asl muammoning barcha cheklovlarida erkin shartlar kerak

o'ng tomonda, noma'lumli atamalar esa chap tomonda bo'lsin.

2. Asl muammoning cheklovlari-tengsizliklari belgilari bo'lishi kerak,

bir yo'nalishga qaratilgan.

3. Agar dastlabki masaladagi maqsad funksiyasi minimallashtirilsa, tengsizlik cheklovlari “≤” belgisi bilan yozilishi kerak, u holda qo‘sh masalada maqsad funksiya minimallashtiriladi va tengsizlik cheklovlarining belgilari “≥” bo‘ladi.

4. Asl muammoning har bir cheklovi in ​​o‘zgaruvchisiga mos keladi

ikki tomonlama vazifa. Agar o'zgaruvchi tengsizlikka to'g'ri kelsa, u manfiy emas, agar u tenglikka to'g'ri kelsa, u holda o'zgaruvchi belgi bo'yicha cheklovlarsiz ("ixtiyoriy").

5. Ikkilik masala cheklovlaridagi o'zgaruvchilarning koeffitsientlari quyidagilardan tashkil topgan matritsani ko'chirish yo'li bilan olinadi.

asl muammoning o'zgaruvchilari uchun koeffitsientlar.

6. Dastlabki masalaning erkin shartlari at koeffitsientlari

dual masalaning maqsad funksiyasidagi o'zgaruvchilar va bepul

dual masaladagi atamalar - bu o'zgaruvchilarning koeffitsientlari

asl masalaning vazifalari.Biz ikkilik munosabati o'zaro, ya'ni. dualga nisbatan dual topshiriq asl vazifaga to'g'ri keladi Ikki juft topshiriqlar simmetrik va assimetrik bo'linadi. Simmetrik juftlikda birlamchi va ikkilamchi masalalarning cheklovlari qat'iy bo'lmagan tengsizliklardir va shuning uchun ikkala masalaning o'zgaruvchilari faqat manfiy bo'lmagan qiymatlarni qabul qilishi mumkin.

59. Modelning standart, kanonik va umumiy ko'rinishida yozilgan dastlabki masalalarga qo'sh masalalarni qurish (simmetrik va assimetrik ikki tomonlama masalalarni qurish).

Standart shakl (asl nusxasi)

S a ij x j ≤ b i , i=1,n(1)

x j ≥0, j=1,n(2)

z = S c j x j ->max(3)

Ikkilik standart

S a ij y i ≤ c j , j=1,n(1)

yi ≥0, j=1,m(2)

F = S b i y i ->min(3)

Kanonik shakldagi asl muammo:

S a ij x j = b i , i=1,m(1)

x j ≥0, j=1,n(2)

z = S c j x j ->min(3)

Ikki kanonik

S a ij y i ≤ c j , j=1,n(1)

y i - har qanday (2)

F = S b i y i ->max(3)

Keling, bir juft muammoning iqtisodiy talqinini beraylik. Resurslardan oqilona foydalanish muammosini ko'rib chiqing. Korxonada b1,b2,...bm resurslari bo'lsin, ulardan n-turdagi mahsulotlarni ishlab chiqarish uchun foydalanish mumkin. Shuningdek, j-turdagi mahsulot birligining tannarxi cj (j=1,n) va i-resursning (i=1,m) ishlab chiqarish uchun sarflanishini ham bilib olaylik. j-chi birliklar mahsulotlar - aij.Har bir xj (j=1,n) turdagi ishlab chiqarish hajmini umumiy tannarxni maksimal darajada oshirib aniqlash talab etiladi.

f= c1x1+…+cnxn (1)

Shu bilan birga, resurslarni iste'mol qilish ularning mavjudligidan oshmasligi kerak:

a11x1+…+a1nxn<=b1 }

…………………….. } (2)

am1x1+…+amnxn<=bm }

Iqtisodiy ma'noda ma'lum bo'lganlarning barchasi salbiy emas:

Xj>=0 (j=1,n). (3)

E'tibor bering, bu muammo simmetrik ikki tomonlama muammoni hosil qiladi.

Asimmetrik ikki tomonlama muammolar.

Keling, ZLP ni kanonik shaklda maksimal darajaga olib chiqamiz:

Maks Z=(n;j=1)Scj*xj

(n;j=1)Staij*xj=bi (i=1,m)

Xj>=0 (j=1,n).

60. Asosiy va ikkinchi duallik teoremasi (holat teoremalari va tushuntiring)

Birinchi duallik teoremasi.

Teorema: agar dual masalalardan biri optimal rejaga ega bo'lsa, ikkinchisi echilishi mumkin, ya'ni. tanlov rejasiga ega. Bunda maqsad funksiyalarining ekstremal qiymatlari mos keladi (j=1 dan n gacha) Scjxj*= (i=1 dan m gacha)Sbiyi*, agar asl nusxada bo'lsa. masala maqsad funksiyasi rejalar to‘plamida chegaralanmagan bo‘lsa, ikkilamchi masalada cheklovlar tizimi mos kelmaydi.

Ikkinchi duallik teoremasi va uning iqtisodiy talqini.

Ikkilamchi masalalar juftligini amalga oshirish mumkin bo‘lgan yechimlari optimal bo‘lishi uchun quyidagi shartning bajarilishi zarur va yetarli: xj*(∑aij yi*-cj)=0, j 1 dan n gacha, yi*( ∑aij xj*-bi)=0, I 1 dan m gacha. Bular bir-birini to'ldiruvchi sustlik shartlari. Ulardan kelib chiqadi: agar dual muammoning har qanday cheklovi optimal reja bilan qat'iy tenglikka aylantirilsa, u holda optning tegishli komponenti. Ikkilamchi masala rejasi nolga teng bo'lishi kerak.Agar ba'zi komponentlar opt. plan nolga teng bo'lsa, u holda qo'sh masalaning mos keladigan cheklovi opt.plan tomonidan qat'iy tenglik xj*>0 ga aylantiriladi, shuning uchun (i= 1 dan m gacha)Saij yi*=cj opt.plan, u holda agar xarajatlar>narxlar, ishlab chiqarish hajmi=0 Staij yi* >cj demak, xj*=0

yi*>0 shuning uchun (j=1 dan n gacha) Staij xj*=bi (resurslar poygalari = resurs zaxirasi).

(j=1 dan n gacha) Staij xj*

Teoremaning ma'nosi quyidagicha:

Agar mahsulot-ii \u003d narx birligini ishlab chiqarish uchun resurs iste'moli xarajatlari smetasi bo'lsa, u holda ushbu turdagi mahsulot-ii optimal rejaga kiritilgan;

Agar xarajatlar narxdan oshsa, u holda prod-yu ishlab chiqarilmasligi kerak;

Agar resurs iste'moli = zaxira bo'lsa, u holda bu resursning xarajatlar smetasi ijobiy bo'ladi. Bunday resurs kam deb ataladi. Eng nuqsonli.res-s eng yuqori ballga ega;

Agar resurs to'liq sarflanmagan bo'lsa, u holda uning xarajatlar smetasi = 0.

61. Dastlabki masalaning simpleks jadvalidan ikkilamchi masalaning optimal tayanch rejasini tuzish

Optimal natijaga olib kelgan chiziqli o'zgarishlarning teskari matritsasi ustunlaridan olingan ma'lumotlar. D-1 matritsasining ustunlari juda foydali ma'lumot beradi.

A3 ustuni: S2 resursining "soya" narxi y01=0, ustun qoladi

yagona va birinchi qatordan x3=9 ekanligini o'qish mumkin, ya'ni. topilgan optimal rejani amalga oshirishda 1-resurs ortiqcha bo'ladi va bu ortiqcha (kam foydalanish) atigi 9 an'anaviy birlikni tashkil qiladi.

A4 ustuni: S2 resursining “soya” bahosi y02=1 ga teng, resurs to‘liq foydalaniladi va uning mumkin bo‘lgan o‘sishi maqsad funksiyasining (ya’ni daromad) oshishiga olib keladi. Va chunki y02=1, keyin S2 resursning 1 c.u ga ortishi. tomonidan daromad bo'yicha qo'shimcha beradi.Z = y02· .w2 = = 1,1 = 1 (ming UAH) (bu erda.w2 - S2 resursining o'sishi va .Z - daromadning mos keladigan o'sishi). S2 resursining bunday o'sishi bilan maksimal daromad allaqachon Zmax = 58 ming UAH bo'ladi. + 1 ming UAH = 59 ming UAH. Shaklda. 6.2 ushbu vaziyatni ko'rsatadi, sharhlar quyida keltirilgan. Bundan tashqari, A4 ustunidan S2 resursining 1 c.u ga ko'payishi bilan kelib chiqadi. yangi optimal nuqta uchun T1 mahsulotining chiqishi ½ tonnaga kamayadi (asosiy o'zgaruvchining x1 qatori va A4 ustunining kesishmasida "-1/2") va T2 mahsulotining chiqishi 3 ga oshadi. /2 tonna (chunki A4 ustunidagi x2 asosiy o'zgaruvchisi bo'lgan qatorda bizda "3/2" mavjud. A4 ustuni haqida nima deyilganligi quyida grafik konstruktsiyalar yordamida izohlanadi (6.2-rasm). A5 ustun: "soya" " S3 resursining narxi y03=2 ga teng. Bu S3 resursining 1 c.u ga ko'payishini anglatadi. Z ga qo'shimcha olib keladi.Z = y03 .v3 = 2,1 =2(ming grivna) va Zmax=58 ming grivna bo'ladi. + 2 ming UAH = 60 ming UAH. Shu bilan birga, jadvalning A5 ustunidan quyidagicha. 3, T1 ishlab chiqarish ½ tonnaga oshadi va T2 ½ tonnaga kamayadi. S1 xomashyo zaxirasi (1-qatorga qarang) 3/2 c.u ga oshadi.

62. Dinamik dasturlash usuli g’oyasi va uning geometrik talqini. Bellmanning optimallik printsipi.

Dinamik dasturlash usuli bilan masalaning optimal yechimi funksional tenglama asosida topiladi

Uni aniqlash uchun sizga kerak bo'ladi:

1. jarayonning oxirgi holati uchun funktsional tenglamani yozing (u l \u003d n-1 ga to'g'ri keladi)

fn-1(Sl-1)=optimal(Rn(Sn-1,Un)+f0(Sn))

2. Rn(Sn-1,Un) ni ba'zi bir sobit Sn-1 uchun diskret qiymatlari to'plamidan va tegishli ruxsat etilgan maydonlardan Unni toping (chunki f0(Sn)=0, keyin f1(Sn-1)= optimal(Rn( Sn-1,Un)

Natijada, birinchi qadamdan so'ng Un yechimi va f1(Sn-1) funksiyaning mos qiymati ma'lum bo'ladi.

3. l ning qiymatini bir marta kamaytiring va mos funksional tenglamani yozing. l=n-k (k= 2,n) uchun shunday ko'rinadi

fk(Sn-k)=optimal(Rn-k+1(Sn-k,Un-k+1)+fk-1(Sn-k+1)) (2)

4. (2) ifoda asosida shartli optimal yechim toping.

5. l ning qiymati nimaga tengligini tekshiring.Agar l=0 bo’lsa, shartli optimal yechimlarni hisoblash tugallanadi va jarayonning birinchi holati uchun masalaning optimal yechimi topiladi. Agar l 0 ga teng bo'lmasa, 3-bosqichga o'ting.

6. Hisob-kitoblarning oxiridan boshiga qarab jarayonning har bir keyingi bosqichi uchun masalaning optimal yechimini hisoblang.

Dasturlar dinamikasi usuli ko'p o'zgaruvchilarga ega bo'lgan bitta masalani kichikroq miqdordagi o'zgaruvchilar bilan ketma-ket hal qilingan bir qator masalalar bilan almashtirishga imkon beradi. Qaror bosqichma-bosqich qabul qilinadi. Ko'p bosqichli jarayonni optimallashtirish asos bo'lgan asosiy printsip, shuningdek, hisoblash usulining xususiyatlari Bellman optimallik printsipidir.

Optimal xatti-harakat shunday xususiyatga egaki, dastlabki holat va dastlabki qaror qanday bo'lishidan qat'i nazar, keyingi qarorlar dastlabki qarordan kelib chiqadigan holatga nisbatan maqbul bo'lishi kerak.

Matematik jihatdan u shaklning ifodasi sifatida yoziladi:

fn-1(Sl)=optimal(Rl+1(Sl,Ul+1)+fn-(l+1)(Sl+1)) (1)

(l=0,n-1)Ifodadagi optimum masala shartiga qarab maksimal yoki minimumni bildiradi.

63. DP usulida yechilgan masalalarga qo’yiladigan talablar

Dinamik dasturlash - bu ko'p bosqichli masalalarning optimal echimlarini topishning matematik usuli. Ko'p bosqichli jarayon vaqt o'tishi bilan rivojlanib, bir necha bosqichlarga yoki bosqichlarga bo'lingan jarayondir.

Dinamik dasturlash usulining xususiyatlaridan biri shundaki, ko'p bosqichli jarayonlarga nisbatan qabul qilingan qarorlar bitta akt sifatida emas, balki o'zaro bog'liq bo'lgan qarorlarning butun majmuasi sifatida ko'rib chiqiladi. O’zaro bog’liq bo’lgan qarorlar ketma-ketligi strategiya deb ataladi.Optimal rejalashtirishdan maqsad oldindan tanlangan mezon bo’yicha eng yaxshi natijani ta’minlovchi strategiyani tanlashdan iborat. Bunday strategiya optimal deb ataladi.

Usulning yana bir muhim xususiyati - tarixdan oldingi bosqichdan keyingi bosqichda qabul qilingan optimal qarorning mustaqilligi, ya'ni. optimallashtirilayotgan jarayon qanday qilib hozirgi holatga kelganligi haqida. Optimal yechim faqat hozirgi jarayonni tavsiflovchi omillarni hisobga olgan holda tanlanadi.

Dinamik dasturlar usuli, shuningdek, har bir bosqichda optimal echimni tanlash kelajakda uning oqibatlarini hisobga olgan holda amalga oshirilishi kerakligi bilan tavsiflanadi. Bu shuni anglatadiki, har bir alohida bosqichda jarayonni optimallashtirishda, hech qanday holatda siz keyingi barcha bosqichlarni unutmasligingiz kerak.

64.DP usulida yechilgan masalaning matematik modelini iqtisodiy jihatdan shakllantirish va qurish (kapital qo’yilmalarni taqsimlash masalasi misolida). Bellmanning takrorlanish munosabati.

Keling, oldindan tushuntirib beraylik, dinamik dasturlash usuli, birinchi navbatda, optimallashtirilayotgan jarayon (yoki vaziyat) makon yoki vaqt yoki ikkalasida qo'llaniladigan muammolarga nisbatan qo'llaniladi.

Jarayonning (vaziyatning) o'zi shunchalik murakkab bo'lsinki, uni ma'lum usullar yordamida optimallashtirishning hech qanday usuli yo'q. So'ngra, dinamik dasturlash usuliga ko'ra, KOMPLEKS jarayon (operatsiya, vaziyat) bir qancha bosqichlarga (bosqichlarga) bo'linadi (bo'linadi). Bu buzilish ko'p hollarda tabiiydir, lekin umumiy holatda u sun'iy ravishda kiritiladi. . Misol uchun, har qanday shaxmat o'yinini ko'rib chiqayotganda, har bir o'yinchining har qanday harakati shunchaki xizmat qiladi

butun partiyani alohida bosqichlarga (bosqichlarga) ajratish. Va bitta raketani boshqasiga qarshi ta'qib qilish bo'yicha harbiy operatsiyada butun uzluksiz jarayon sun'iy ravishda bosqichlarga bo'linishi kerak, masalan, kuzatishning har bir soniyasi. Dinamik dasturlash usuli butun murakkab jarayonni optimallashtirishni har bir bosqich uchun shartli optimallashtirish bilan almashtirishga imkon beradi.

(qadamlar) keyin butun jarayonni optimal boshqarish sintezi. Shu bilan birga, usul alohida bosqichda (bosqichda) shartli optimallashtirish, birinchi navbatda, butun operatsiya manfaatlari uchun amalga oshirilishini ta'minlaydi.

n bosqichda erishilgan effektning optimal qiymatini topish imkonini beradigan barcha hisoblar fn(S0) formula (1) bo'yicha amalga oshiriladi, bu asosiy funktsional Bellman tenglamasi yoki takrorlanish munosabati deb ataladi. fn-1 funksiyaning keyingi qiymatini hisoblashda oldingi bosqichda olingan fn-(l+1) funksiyaning qiymati, Rl+1(Sl,Ul+1) ta’sirning bevosita qiymatidan foydalaniladi. berilgan holat Sl tizimlari uchun Ul+1 yechimni tanlash natijasida erishiladi. fn-1(l=0,n-1) funksiya qiymatini hisoblash jarayoni.

U f0(Sn)=0 tabiiy boshlang'ich sharti ostida amalga oshiriladi, ya'ni tizimning yakuniy holatidan tashqarida ta'sir nolga teng.

65. Kapital qo’yilmalarni taqsimlash muammosi (misol).

Kapital qo'yilmalarni optimal taqsimlash muammosini hal qilish uchun biz funktsional Bellman tenglamasidan foydalanamiz. Birinchidan, eng oddiy vaziyatdan foydalanib, biz Bellman funktsional tenglamasining kelib chiqishini ko'rsatamiz, so'ngra bizni qiziqtirgan masalani hal qilish uchun ushbu tenglamadan qanday foydalanishni misol orqali isbotlaymiz.

Ikki korxona o'rtasida K miqdoridagi ajratilgan kapital qo'yilmalarni optimal taqsimlashdan boshlaylik. Korxonalarning rejalashtirish bo'limlari o'zlarining hisob-kitoblari asosida P1 korxona uchun q(x) va P2 korxona uchun h(x) daromad funksiyalarini shakllantirdilar. Bu funktsiyalar shuni anglatadiki, agar birinchi yoki ikkinchi korxona x miqdorida investitsiya olsa, u holda birinchi korxona

daromad q (x) olinadi va ikkinchi h (x) va x qiymati 0 dan K gacha bo'lgan doimiy yoki ma'lum diskret qiymatlarni olishi mumkin.

Shunday qilib, P1 kompaniyasi kapital qo'yilmalarni x miqdorida ajratsin, keyin P2 kompaniyasiga K - x miqdori ajratiladi. Bunda birinchi korxonadan q(x) daromad, ikkinchisidan esa h(K - x) olinadi. Agar K investitsiyalar bitta rejalashtirish davri uchun ajratilgan bo'lsa, u holda ikkita korxonadan olingan umumiy daromad R(K, x) = q(x) + h(K - x) bo'ladi. Shubhasiz, x va shunga mos ravishda K - x tanlanishi kerakki, R(K, x) o'zining maksimal qiymatini oladi, biz buni F(K) bilan belgilaymiz:

Ushbu yozuv to'liqroq yozuvlar uchun skeletga o'xshaydi.

Funktsional Bellman tenglamasi. Kapital qo'yilmalarni ikkita rejalashtirish davriga (ikki bosqich) taqsimlash orqali vazifamizni murakkablashtiring. . Dastlab birinchi korxona P1ga x summasini, P1 ikkinchi korxonasiga x miqdorini ajratishga qaror qilinsin. Umuman olganda, daromad R(K, x) = q(x) + ga teng bo'ladi

h(K - x). Agar investitsiyalar 2 davrga (2 bosqich) taqsimlanishini hisobga olsak, birinchi korxonada investitsiyalar qoldig'i x bo'ladi, bu erda , ikkinchisida - .(K - x), bu erda Shunga ko'ra, daromadlar. ikkinchi davr q( .x) - birinchi ob'ektga ko'ra va h[.(K - x)] - ikkinchisiga ko'ra bo'ladi. Dinamik dasturlashni optimallashtirish, qoida tariqasida, oxirgi bosqichdan boshlanadi. Shuning uchun biz F1 ni ikkinchi bosqichda ikkita korxonadan mumkin bo'lgan maksimal daromadni belgilab, ikkinchi bosqichdan boshlaymiz

bosqich. Oling

Keyin, ko'rib chiqilgan oxirgi (bizning holatimizda, ikkinchi) bosqichga biz avvalgi (bizning holatimizda birinchi) bosqichni qo'shamiz va ikkita bosqichdan maksimal daromadni birgalikda topamiz:

Xuddi shunday, n bosqich uchun biz olamiz

Bu erda Fn-1 - oxirgi (n - 1) bosqichlar uchun eng yaxshi natija beradigan maqsad funktsiyasi. Olingan funktsional Bellman tenglamasi takroriy, ya'ni. Fn qiymatini Fn-1 qiymati bilan bog'laydi.

Umuman olganda, Bellman tenglamasi shaklga ega

bu erda , Fn-1 - (n - 1) oxirgi bosqichlar uchun maksimal daromad, Fn -

barcha n bosqichlar uchun maksimal daromad.

66. Nochiziqli dasturlash masalalarini yechish tushunchasi

Chiziqli bo'lmagan dasturlash masalasi quyidagi umumiy shaklda qo'yilsin: x1, x2, ..., xn o'zgaruvchilarning shartlarga javob beradigan qiymatlarini toping:

va maqsad funktsiyasining kerakli ekstremumini (maksimal yoki minimal) keltiring

f = f(x1, x2,…, xn), (13.2)

bu yerda f(x1, …, xn) va qi(x1, …, xn) (m , 1 i =) haqiqiy chiziqli emas,

n ta real o‘zgaruvchining muntazam funksiyalari.

Umumiy xususiyatlariga ko'ra, chiziqli bo'lmagan dasturlash muammolari mumkin

chiziqlilardan sezilarli darajada farq qiladi. Misol uchun, mumkin bo'lgan echimlar sohasi allaqachon qavariq bo'lmagan bo'lishi mumkin va maqsad funktsiyasining ekstremumini amalga oshirish mumkin bo'lgan sohaning istalgan nuqtasida kuzatish mumkin. Nochiziqli masalalarni yechish usullari ham sezilarli darajada farqlanadi. Keling, ushbu muammolarni hal qilishning faqat ba'zi yondashuvlarini ko'rib chiqaylik.

Avvalo, grafik yondashuv chiziqli bo'lmagan dasturlashning eng oddiy masalalarini echishda ham o'rinlidir. Shunday qilib, agar x1 va x2 o'zgaruvchilari muammoning argumentlari bo'lsa, unda birinchi navbatda mumkin bo'lgan echimlar maydoni ushbu o'zgaruvchilar tekisligida quriladi, so'ngra maqsad funktsiyasi darajalari yordamida sohadagi optimal nuqta aniqlanadi. f(x1,x2).

Chiziqli bo'lmagan dasturlashda ko'p muammolarni hal qilish uchun gradient yondashuv qo'llaniladi. Bir qator gradient usullari mavjud bo'lib, ularning mohiyati maqsad funktsiyasining gradienti - ko'rib chiqilayotgan nuqta uchun maqsadning maksimal o'sish yo'nalishini ko'rsatadigan vektor yordamida optimal natijani topishdir. Umumiy holda, qidiruv protsedurasi dastlabki tanlangan nuqtadan eng yaxshi ko'rsatkichga ega bo'lgan nuqtalargacha iterativ rejimda amalga oshiriladi. Keling, masalan, . - ruxsat etilgan yechimlar sohasi

ko'rib chiqilgan muammo va hisob-kitoblarning iterativ jarayoni nuqtadan boshlanadi

Keyinchalik, birinchi navbatda, maqsad funktsiyasining gradienti bo'ylab o'tish, so'ngra maydonga qaytish amalga oshiriladi. gradient bo'ylab O2 O3 hududining buzilgan chegarasigacha. 13.3 ko'rsatilganki, toq indeksli Ai maydonga tegishli bo'ladi., Juft indeksli Ai nuqtalar esa yo'q.Biz optimal Q nuqtaga yaqinlashganda, ishchi gradientlarning yo'nalishlari yaqinlashadi. Shuning uchun, jarayonni to'xtatish uchun ideal mezon maqsadli gradient va singan chegara gradientining kollinearligi bo'ladi.

67. Parametrik va butun sonli dasturlash tushunchasi .

ZCLP ning bayoni va matematik modeli.

Bo'linmas ob'ektlar bilan bog'liq masalalarda o'zgaruvchilarga butun son shartlari qo'yiladi. Ba'zan bu shartlar barcha o'zgaruvchilarga, ba'zan esa ba'zi o'zgaruvchilarga taalluqlidir.To'liq butun son masalasini ko'rib chiqing.

f=(n,j=1)∑CjXi maks

(n,j=1)∑AijXj=bi, i=1,m

xi-butun son,j=1,n

Endi, umumiy chiziqli dasturlash masalasidan farqli o'laroq, optimal reja reja ko'pburchakning cho'qqisida bo'lishi shart emas.Butun sonli masalalarni yechishning quyidagi usullari mavjud:

1. Kesish usullari

2.Kombinatorlik

3. Taxminiy usullar..

Parametrik dasturlash - matematik dasturlashning optimallashtirish masalalarini o'rganishga bag'ishlangan bo'limi bo'lib, unda ruxsat etilganlik shartlari va maqsad funktsiyasi ba'zi deterministik parametrlarga bog'liq.

Ta'rif. Chiziqli dasturlash (LP) - noma'lumlarga chiziqli cheklovlar qo'yilgan chiziqli funktsiyaning o'ta (maksimal va minimal) qiymatlarini topish va tadqiqot usullari haqidagi fan.

Ushbu chiziqli funktsiya deyiladi maqsad, va matematik jihatdan tenglama yoki tengsizlik sifatida yozilgan cheklovlar deyiladi cheklovlar tizimi.

Ta'rif. Maqsad funksiyasi va uning cheklanishining matematik ifodasi deyiladi iqtisodiy muammoning matematik modeli.

Umuman olganda, chiziqli dasturlash (LP) muammosining matematik modeli quyidagicha yoziladi

cheklovlar bilan:

Qayerda x j- noma'lum; aij, b i, cj konstantalar beriladi.

Cheklash tizimining barcha yoki bir nechta tenglamalarini tengsizlik sifatida yozish mumkin.

Qisqaroq yozuvdagi matematik model shaklga ega

cheklovlar bilan:

Ta'rif. Chiziqli dasturlash masalasining mumkin bo'lgan yechimi (rejasi) vektor = ( x 1 , x 2 ,..., x p), cheklovlar tizimini qondirish.

Ruxsat etilgan eritmalar to'plami ruxsat etilgan eritmalar mintaqasini (ODD) tashkil qiladi.

Ta'rif. Maqsad funksiyasi o'zining ekstremal qiymatiga yetadigan amalga oshirilishi mumkin bo'lgan yechim chiziqli dasturlash masalasining optimal yechimi deb ataladi va opt bilan belgilanadi.

Asosiy ruxsat etilgan yechim (X 1 , X 2 ,...,x r , 0, …, 0) mos yozuvlar yechimidir, bu erda r- cheklash tizimining darajasi.

LP masalasining matematik modeli kanonik va kanonik bo'lmagan bo'lishi mumkin.

7. Chiziqli dasturlash masalalarini grafik usulda yechish. Cheklash funksiyalarining grafiklari. Darajali chiziqlar.

Chiziqli dasturlash masalalarini echishning grafik usuli

Chiziqli dasturlashning eng sodda va vizual usuli grafik usuldir. U kanonik bo'lmagan shaklda berilgan ikkita o'zgaruvchi va kanonik shakldagi ko'p o'zgaruvchilar bilan LP masalalarini hal qilish uchun ishlatiladi, agar ular ikkitadan ko'p bo'sh bo'lmagan o'zgaruvchilarni o'z ichiga olmaydi.

Geometrik nuqtai nazardan, chiziqli dasturlash masalasida bunday burchak nuqtasi yoki ruxsat etilgan echimlar to'plamidan nuqtalar to'plami qidiriladi, bunda eng yuqori (pastki) sath chizig'iga erishiladi, u erdan uzoqroq (yaqinroq) joylashgan. boshqalar eng tez o'sish yo'nalishida.

LP masalalarini grafik echishda maqsad funksiyasining ekstremal qiymatini topish uchun vektordan foydalaniladi L() sirtda X 1 OH 2 , biz belgilaymiz . Ushbu vektor maqsad funktsiyasining eng tez o'zgarishi yo'nalishini ko'rsatadi. Boshqacha qilib aytganda, vektor daraja chizig'ining normalidir L()

Qayerda e 1 va e 2 - o'qlar bo'ylab birlik vektorlar OX 1 va OX mos ravishda 2; shunday = (∂L/∂x 1 , ∂L/∂x 2 ). Vektor koordinatalari maqsad funksiya koeffitsientlaridir L(). Darajali chiziqni qurish amaliy masalalarni hal qilishda batafsil ko'rib chiqiladi.

Muammoni hal qilish algoritmi

1. Muammoning cheklovlar tizimi uchun mumkin bo'lgan echimlar maydonini topamiz.

2. Vektor qurish .

3. Bir daraja chizig'ini chizish L 0 , qaysi perpendikulyar .

4. Biz daraja chizig'ini vazifalar uchun vektor yo'nalishi bo'yicha maksimal va teskari yo'nalishda harakatlantiramiz , minimal vazifalar uchun.

Darajali chiziq amalga oshirilishi mumkin bo'lgan echimlar maydoni bilan faqat bitta umumiy nuqtaga ega bo'lguncha siljiydi. LP muammosining yagona yechimini aniqlaydigan bu nuqta ekstremum nuqta bo'ladi.

Agar daraja chizig'i ODT tomonlaridan biriga parallel ekanligi aniqlansa, u holda bu holda tegishli tomonning barcha nuqtalarida ekstremumga erishiladi va LP muammosi cheksiz ko'p echimlarga ega bo'ladi. Bunday LP muammosi borligi aytiladi alternativ optimal va uning yechimi quyidagi formula bilan topiladi:

Bu erda 0 ≤ t≤ 1, 1 va 2 - ODSning burchak nuqtalarida optimal echimlar.

LP muammosi, agar uni belgilaydigan cheklovlar qarama-qarshi bo'lib chiqsa, uni hal qilib bo'lmaydi.

5. Ekstremum nuqtaning koordinatalarini va undagi maqsad funksiyasining qiymatini topamiz.

3-misol Eng yaxshi mahsulotni chiqarish variantini tanlash

Korxonada 2 turdagi muzqaymoq ishlab chiqariladi: qaymoq va shokolad. Muzqaymoq ishlab chiqarish uchun ikkita boshlang'ich mahsulot ishlatiladi: sut va plomba moddalari, ularning narxi 1 kg muzqaymoq va kunlik materiallar jadvalda keltirilgan.

Bozor tadqiqotlari shuni ko'rsatdiki, yog'li muzqaymoq uchun kunlik talab shokoladli muzqaymoqga bo'lgan talabdan oshadi, lekin 100 kg dan oshmaydi.

Bundan tashqari, shokoladli muzqaymoqga bo'lgan talab kuniga 350 kg dan oshmasligi aniqlandi. 1 kg qaymoqli muzqaymoqning chakana narxi 16 rubl, shokolad - 14 rubl.

Savdo daromadini maksimal darajada oshirish uchun firma har bir turdagi muzqaymoqning qancha qismini ishlab chiqarishi kerak?

Yechim. Belgilang: x 1 - qaymoqli muzqaymoq ishlab chiqarishning kunlik hajmi, kg; x 2 - shokoladli muzqaymoqning kunlik chiqishi, kg.

Keling, masalaning matematik modelini tuzamiz.

Muzqaymoq narxlari ma'lum: mos ravishda 16 rubl va 14 rubl, shuning uchun maqsad funktsiyasi quyidagicha ko'rinadi:

Muzqaymoq uchun sutga cheklovlar qo'ying. Qaymoqli muzqaymoq uchun uning iste'moli 0,8 kg, shokoladli muzqaymoq uchun - 0,5 kg. Sut zaxirasi 400 kg. Shunday qilib, birinchi tengsizlik quyidagicha ko'rinadi:

0,8x 1 + 0,5x 2 ≤400 - birinchi tengsizlik cheklashdir. Qolgan tengsizliklar xuddi shunday tuzilgan.

Natijada tengsizliklar tizimi paydo bo'ladi. har bir tengsizlikning yechim sohasi nimaga teng. Buni har bir tengsizlikka O(0:0) nuqtaning koordinatalarini qo‘yish orqali amalga oshirish mumkin. Natijada biz quyidagilarni olamiz:

Rasm OABDEF- ruxsat etilgan yechimlar sohasi. Biz vektorni quramiz (16; 14). daraja chizig'i L 0 16x 1 +14x 2 =Const tenglama bilan berilgan. Biz har qanday raqamni tanlaymiz, masalan, 0 raqami, keyin 16x 1 +14x 2 =0. Rasmda L 0 chizig'i uchun nolga teng bo'lmagan qandaydir ijobiy son tanlangan. Barcha darajadagi chiziqlar bir-biriga parallel. Darajali chiziqning normal vektori.

Darajali chiziqni vektor yo'nalishi bo'yicha harakatlantiring. chiqish nuqtasi L Mumkin yechimlar mintaqasidan 0 nuqta D, uning koordinatalari tenglamalar bilan berilgan chiziqlarning kesishishi sifatida aniqlanadi:

Tizimni yechish orqali biz nuqtaning koordinatalarini olamiz D(312,5; 300), unda optimal yechim bo'ladi, ya'ni.

Shunday qilib, kompaniya kuniga 312,5 kg yog'li muzqaymoq va 300 kg shokoladli muzqaymoq ishlab chiqarishi kerak, sotishdan olinadigan daromad esa 9200 rublni tashkil qiladi.

8. Ixtiyoriy chiziqli dasturlash masalasini asosiy masalaga qisqartirish. Tengsizliklar orqali berilgan cheklovlarni mos tenglamalarga aylantirish.

9.Simpleks usuli. Usulning xarakteristikasi va algoritmi, uning qo'llanilishi.

Muammoni simpleks usuli bilan hal qilish kerak:

1. Optimal etalon yechimni topish usulini ko'rsating

2. Bir etalon yechimdan ikkinchisiga o'tish usulini belgilang, bunda maqsad funktsiyasining qiymati optimalga yaqinroq bo'ladi, ya'ni. mos yozuvlar yechimini takomillashtirish yo'lini ko'rsating

3. Optimal yechim bo'yicha etalon echimlarni sanab o'tishni o'z vaqtida to'xtatish yoki optimal yechimning yo'qligi to'g'risida xulosa chiqarish imkonini beruvchi mezonlarni belgilang.

Chiziqli dasturlash masalalarini yechishning simpleks usulining algoritmi

1. Muammoni kanonik shaklga keltiring

2. “Birlik asosi” bilan dastlabki qo‘llab-quvvatlash yechimini toping (agar qo‘llab-quvvatlovchi yechim bo‘lmasa, cheklovlar tizimining mos kelmasligi sababli muammoning yechimi yo‘q)

3. Etalon yechimning asosi bo‘yicha vektor kengayishlarining baholarini hisoblang va simpleks usuli jadvalini to‘ldiring.

4. Agar optimal yechimning yagonaligi mezoni qanoatlansa, masalaning yechimi tugaydi.

5. Agar optimal yechimlar to’plamining mavjudligi sharti qanoatlansa, oddiy sanab o’tish yo’li bilan barcha optimal yechimlar topiladi.

10. Transport vazifasi. Transport masalasining ta'rifi, turlari, dastlabki yechimini topish usullari.

Transport muammosi eng keng tarqalgan chiziqli dasturlash muammolaridan biridir. Uning maqsadi - yuklarni tashishning eng oqilona usullari va vositalarini ishlab chiqish, haddan tashqari uzoq masofalarga, yaqinlashib kelayotgan, takroriy tashishlarni bartaraf etishdir.

1. Dastlabki mos yozuvlar yechimini topish;

2. Ushbu yechimning optimalligini tekshirish;

3. Bir asosiy yechimdan ikkinchisiga o‘tish.

2-ma'ruza

IN kanonik shakl

PLP ning ruxsat etilgan yechimi(maqbul reja).

MChJning optimal yechimi.

Zaruriyat

Misol.

Keling, muammoni yozamiz kanonik shakl

ZLP ning grafik yechimining alohida holatlari

Vazifa bo'lganda bundan mustasno yagona optimal yechim uchun va, bo'lishi mumkin maxsus vaziyatlar:

1. vazifa bor cheksiz ko'p optimal echimlar – segmentda funksiyaning ekstremumiga erishiladi ( alternativ optimal)- 2-rasm;

2. vazifa hal etilmaydi ODRning cheksizligi tufayli yoki - 3-rasm;

3. ODR - yagona nuqta Oh, keyin;

4. vazifa hal etilmaydi agar ODR bo'sh maydonga ega bo'lsa.

A

2-rasm 3-rasm

Agar daraja chizig'i mumkin bo'lgan echimlar maydonining yon tomoniga parallel bo'lsa, u holda yon tomonning barcha nuqtalarida ekstremumga erishiladi. Muammo cheksiz ko'p optimal echimlarga ega - alternativ optimal . Optimal yechim formula bo'yicha topiladi

parametr qayerda. 0 dan 1 gacha bo'lgan har qanday qiymat uchun siz segmentning barcha nuqtalarini olishingiz mumkin, ularning har biri uchun funktsiya bir xil qiymatni oladi. Shuning uchun nom - alternativ optimal.

Misol. Chiziqli dasturlash masalasini grafik tarzda yechish ( alternativ optimal):

O'z-o'zini nazorat qilish uchun savollar

1. Chiziqli dasturlash masalasini umumiy shaklda yozing.

2. Chiziqli dasturlash masalasini kanonik va standart shakllarda yozing.

3. Chiziqli dasturlash masalasining umumiy yoki standart shaklidan kanonik masalaga o‘tish uchun qanday o‘zgarishlardan foydalanish mumkin?

4. Chiziqli dasturlash masalasini amalga oshirish mumkin bo'lgan va optimal echimlar ta'rifini bering.

5. Agar funktsiyani minimallashtirish muammosi uchun yechimlarning qaysi biri "eng yaxshi" ?

6. If funktsiyani maksimallashtirish masalasi uchun yechimlarning qaysi biri "eng yaxshi" ?

7. Ikki o‘zgaruvchili chiziqli dasturlash masalasining matematik modelining standart shaklini yozing.

8. Ikki o‘zgaruvchili chiziqli tengsizlik bilan berilgan yarim tekislik qanday quriladi ?

9. Ikki o‘zgaruvchili chiziqli tengsizliklar sistemasining yechimi nima deyiladi? Bunday chiziqli tengsizliklar tizimining mumkin bo'lgan yechimlari sohasini tekislikda tuzing, ular:

1) yagona yechimga ega;

2) yechimlarning cheksiz to‘plamiga ega;

3) yechim yo'q.

10. Chiziqli funksiya uchun yozing vektor gradienti, darajali chiziqlar turini nomlang. Gradient va daraja chiziqlari bir-biriga nisbatan qanday joylashgan?

11. Ikki o'zgaruvchili standart LLPni echishning grafik usuli uchun algoritmni tuzing.

12. Yechim koordinatalari va qiymatlari qanday topiladi?

13. Chiziqli dasturlash masalalari uchun mumkin bo'lgan yechimlar maydonini, gradient va darajali chiziqlarni tuzing, unda:

1) bitta nuqtada erishiladi va - ODR segmentida;

2) ODSning bir nuqtasida erishiladi va .

14. MChJning geometrik rasmini keltiring, agar u:

1) va uchun yagona optimal echimlarga ega;

2) uchun optimal yechimlar majmuasiga ega.

2-ma'ruza

optimal yechim topishning grafik usuli

1. Chiziqli matematik modellarning shakllari va ularni o'zgartirish

2. Chiziqli dasturlash masalasini echishning grafik usuli

3. MChJ GRAFIK ECHIMINING MAXSUS HOLATLARI

4. Chiziqli dasturlashning iqtisodiy masalalarini grafik yechish

Chiziqli matematik modellarning shakllari va ularni o'zgartirish

Chiziqli dasturlash muammosining (LPP) matematik modeli uchta shakldan birida yozilishi mumkin.

IN matematik modelning umumiy shakli maqsad funksiyasining maksimal yoki minimalini topish talab etiladi; cheklash tizimi tengsizliklar va tenglamalarni o'z ichiga oladi; barcha o'zgaruvchilar salbiy bo'lishi mumkin emas.

IN kanonik shakl matematik model maqsad funksiyaning maksimalini topishi kerak; cheklash tizimi faqat tenglamalardan iborat; barcha o'zgaruvchilar salbiy emas.

Matematik modelning standart shaklida funksiyaning maksimal yoki minimalini topish talab qilinadi; barcha cheklovlar tengsizlikdir; barcha o'zgaruvchilar salbiy emas.

O'zgaruvchilarning manfiy bo'lmasligi shartlarini qanoatlantiruvchi cheklovlar tizimining yechimi deyiladi. PLP ning ruxsat etilgan yechimi(maqbul reja).

Mumkin echimlar to'plami deyiladi MChJning mumkin bo'lgan echimlari maydoni.

Maqsad funksiyasi ekstremal qiymatga erishadigan mumkin bo'lgan yechim deyiladi MChJning optimal yechimi.

MChJning uchta shakli ekvivalentdir, chunki ularning har biri matematik transformatsiyalar yordamida boshqa shaklga tushirilishi mumkin.

Zaruriyat matematik modelning bir shaklidan boshqasiga o'tish masalalar yechish usullari bilan bog’liq: masalan, chiziqli dasturlashda keng qo’llaniladigan simpleks usuli kanonik shaklda yozilgan masalaga, grafik usul esa matematik modelning standart shakliga qo’llaniladi.

ZLP kanonik yozuviga o'tish.

Misol.

Keling, muammoni yozamiz kanonik shakl, cheklash tizimining birinchi tengsizligining chap tomoniga “+” belgisi bilan qo‘shimcha (balans) o‘zgaruvchini, ikkinchi tengsizlikning chap tomoniga esa “minus” belgisi bilan qo‘shimcha o‘zgaruvchini kiritish.

Turli qo'shimcha o'zgaruvchilarning iqtisodiy ma'nosi bir xil bo'lmasligi mumkin: bu o'zgaruvchilar kiritilgan cheklovlarning iqtisodiy ma'nosiga bog'liq.

Demak, xomashyodan foydalanish masalasida ular xomashyoning qolgan qismini, optimal texnologiyalarni tanlash masalasida esa ma’lum texnologiyadan foydalangan holda korxonaning foydalanilmagan vaqtini ko’rsatadi; kesish muammosida - ma'lum uzunlikdagi blankalarni rejadan ortiqcha chiqarish va boshqalar.