CHIZIQLI DASTURLASH MASALALARINI YECHISHNING SODYYEKS USULI
Bu usul chiziqli dasturlash masalasining etalon yechimlarini maqsadli sanab o'tish usulidir. Bu optimal echimni topish yoki optimal yechim yo'qligini aniqlash uchun cheklangan miqdordagi qadamlarni bajarishga imkon beradi.
Chiziqli dasturlash masalalarini yechishning simpleks usulining algoritmi
Muammoni simpleks usuli bilan hal qilish uchun siz quyidagilarni bajarishingiz kerak:
1. Muammoni kanonik shaklga keltiring
Chiziqli dasturlash
"Birlik asosi" bilan dastlabki mos yozuvlar yechimini toping (agar mos yozuvlar yechimi bo'lmasa, cheklovlar tizimining mos kelmasligi sababli muammoning echimi 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.
Simpleks usuli bilan masalani yechishga misol
1-misol
Simpleks usuli yordamida muammoni hal qiling:
Funktsiya qiymatini minimallashtirish
F = 10×1 - 4×3 maksimal
Tengsizliklar ko'rinishidagi cheklovlar mavjudligida
Muammoni kanonik shaklga keltiramiz.
Buning uchun birinchi tengsizlik cheklovining chap tomoniga +1 koeffitsientli qo'shimcha x 5 o'zgaruvchisini kiritamiz. X 5 o'zgaruvchisi nol koeffitsienti bilan maqsad funktsiyasiga kiritilgan (ya'ni, kiritilmagan).
Biz olamiz:
F = 10×1 - 4×3+0∙x5 maks
Tengsizliklar ko'rinishidagi cheklovlar mavjudligida
Biz dastlabki mos yozuvlar yechimini topamiz. Buning uchun erkin (hal qilinmagan) o'zgaruvchilarni nolga tenglashtiramiz x1 = x3 = 0.
Biz mos yozuvlar yechimini olamiz X1 = (0.0.0.5.9/15.6) birlik asosi B1 = (A4, A5, A6).
Shart vektorlarining kengayish baholarini quyidagi formula yordamida mos yozuvlar yechimining asosi bo'yicha hisoblaymiz:
D k \u003d C b X k - c k
· C b = (s 1 , s 2 , … , s m) - asosiy oʻzgaruvchilarga ega boʻlgan maqsad funksiya koeffitsientlari vektori.
· X k = (x 1k , x 2k , … , x mk) - mos keladigan A vektorning etalon yechim asosiga kengayish vektori.
· C to - x to o'zgaruvchisi uchun maqsad funksiya koeffitsienti.
Bazisga kiritilgan vektorlarning baholari har doim nolga teng.
Etalon yechim, kengayish koeffitsientlari va shartli vektorlarning kengayish baholari etalon yechimning asosi nuqtai nazaridan simpleks jadvalida yoziladi:
Jadvalning tepasida, hisob-kitoblarni hisoblash qulayligi uchun maqsad funktsiyasining koeffitsientlari yozilgan. Birinchi ustun "B" mos yozuvlar yechimining asosiga kiritilgan vektorlarni o'z ichiga oladi. Ushbu vektorlarni yozish tartibi cheklash tenglamalarida ruxsat etilgan noma'lumlar soniga mos keladi. "B bilan" jadvalining ikkinchi ustunida maqsad funktsiyasining koeffitsientlari bir xil tartibda asosiy o'zgaruvchilar bilan yoziladi. "C b" ustunidagi maqsad funktsiyasi koeffitsientlarini to'g'ri joylashtirish bilan, bazaga kiritilgan birlik vektorlarining baholari har doim nolga teng.
Jadvalning oxirgi qatorida D k baholari bilan "A 0" ustunida maqsad funktsiyasining qiymatlari Z(X 1) mos yozuvlar yechimida yoziladi.
Dastlabki mos yozuvlar yechimi optimal emas, chunki maksimal masalada A 1 va A 3 vektorlari uchun D 1 = -2, D 3 = -9 baholar manfiydir.
Etakchi yechimni takomillashtirish teoremasiga ko‘ra, agar maksimal masaladagi kamida bitta vektor manfiy bahoga ega bo‘lsa, u holda maqsad funksiyasining qiymati kattaroq bo‘ladigan yangi etalon yechim topish mumkin.
Keling, ikkita vektordan qaysi biri maqsad funktsiyasining kattaroq o'sishiga olib kelishini aniqlaylik.
Maqsad funktsiyasining o'sishi quyidagi formula bo'yicha topiladi:
Birinchi va uchinchi ustunlar uchun th 01 parametrining qiymatlarini formuladan foydalanib hisoblaymiz:
l = 1 uchun th 01 = 6, l = 1 uchun th 03 = 3 ni olamiz (26.1-jadval).
Bazisga birinchi vektor kiritilganda maqsad funksiyaning o'sishini topamiz
DZ 1 \u003d - 6 * (- 2) \u003d 12,
uchinchi vektor DZ 3 = - 3*(- 9) = 27.
Shuning uchun optimal yechimga tezroq yondashish uchun A6 bazisning birinchi vektori o‘rniga etalon yechim asosiga A3 vektorini kiritish kerak, chunki birinchi qatorda th 03 parametrining minimaliga erishiladi. (l = 1).
X13 = 2 elementi bilan Iordaniya konvertatsiyasini bajaramiz, biz ikkinchi mos yozuvlar yechimini olamiz
X2 = (0.0.3.21.42.0)
B2 = (A3, A4, A5) asosi bilan.
(26.2-jadval)
Bu yechim optimal emas, chunki A2 vektori D2 = - 6 manfiy bahoga ega.
Yechimni yaxshilash uchun A2 vektorini etalon yechim asosiga kiritish kerak.
Bazisdan olingan vektor sonini aniqlaymiz. Buning uchun biz ikkinchi ustun uchun th 02 parametrini hisoblaymiz, u l = 2 uchun 7 ga teng.
Shuning uchun bazisdan biz A4 asosining ikkinchi vektorini chiqaramiz.
X 22 = 3 elementi bilan Iordaniya konvertatsiyasini bajaramiz, biz uchinchi mos yozuvlar yechimini olamiz
X3 = (0.7.10.0.63.0)
B2 \u003d (A3, A2, A5) (26.3-jadval).
Ushbu yechim yagona optimal hisoblanadi, chunki asosga kiritilmagan barcha vektorlar uchun baholar ijobiydir
D 1 \u003d 7/2, D 4 \u003d 2, D 6 \u003d 7/2.
Javob: max Z(X) = 201 da X = (0,7,10,0,63).
⇐ Oldingi123456789Keyingi ⇒
Davlat ta'lim muassasasi yuqoriroq
kasb-hunar ta'limi
"N.E. Bauman nomidagi Moskva davlat texnika universiteti"
Kaluga filiali
“Simpleks usulida chiziqli dasturlash masalasini yechish”.
Ishning maqsadi: chiziqli dasturlashning to'g'ridan-to'g'ri va dual muammolarini echish usuli - Simpleksni amalda qo'llashni o'rganish va o'rganish.
Nazariy qism.
Chiziqli dasturlash masalasini matematik shakllantirish.
Matematik dasturlash masalalarini ko'rib chiqish amaliyotidan kelib chiqadiki, ularni umumiy ma'noda yechish deyarli mumkin emas. Muammolarning alohida sinflarini (turlarini) ko'rib chiqish maqsadga muvofiqdir. Har bir bunday sinf uchun faqat shu sinfdagi masalalar uchun maqbul bo'lgan yechim algoritmini shakllantirish mumkin. Matematik dasturlashda eng rivojlanganlari chiziqli dasturlash (LP) masalalaridir.
Chiziqli dasturlash masalalarida maqsad funktsiyasi chiziqli bo'lib, cheklash shartlari chiziqli tenglik va chiziqli tengsizliklarni o'z ichiga oladi. O'zgaruvchilar salbiy bo'lmaganlik talabiga bo'ysunishi mumkin yoki bo'lmasligi mumkin. Bir xil chiziqli dasturlash masalasi turli shakllarda yozilishi mumkin. Agar barcha cheklovlar tengsizliklar shaklida bo'lsa, u holda masala standart shaklda yoziladi. Agar uning barcha cheklovlari bundan mustasno
tenglik bo’lsa, chiziqli dasturlash masalasi kanonik shaklda yoziladi.
Chiziqli dasturlash masalasining umumiy ko'rinishi
,
Cheklovlar:
1. Barcha cheklovlarning o'ng qismlari manfiy bo'lmasligi kerak . Agar koeffitsientlardan birortasi bo'lsa< 0, то необходимо коэффициенты ограничения слева и справа домножить на "-1" и изменить знак данного ограничения на противоположный;
2. Barcha cheklovlar tenglik sifatida taqdim etilishi kerak, shuning uchun tengsizlikdan tenglikka o'tishda qo'shimcha o'zgaruvchilar apparati qo'llaniladi.
Agar dastlabki cheklovlar ba'zi bir resurs iste'molini aniqlasa ("" belgisi), keyin o'zgaruvchilar resursning qolgan qismi yoki foydalanilmagan qismi sifatida talqin qilinishi kerak. Bunday holda, u qoldiq o'zgaruvchidir va "+" belgisi bilan tenglamaga kiritiladi.
Agar dastlabki cheklovlar biron bir manbaning ortiqcha miqdorini aniqlasa ("" belgisi), ortiqcha o'zgaruvchi kiritiladi. "-" belgisi.
Oʻzgaruvchilar:
Barcha o'zgaruvchilar salbiy bo'lmasligi kerak, ya'ni. .
Agar o'zgaruvchining belgisi cheklovi bo'lmasa, u ikki manfiy bo'lmagan o'zgaruvchilarning ayirmasi sifatida ko'rsatilishi kerak: , bu erda . Bunday almashtirish ushbu o'zgaruvchini o'z ichiga olgan barcha cheklovlarda, shuningdek, maqsad funktsiyasini ifodalashda qo'llanilishi kerak.
Agar bunday o'zgaruvchi optimal yechimga tushsa, u holda
Maqsad funktsiyasi:
Maksimal yoki minimallashtirish uchun.
Tenglik va tengsizliklar ko'rinishidagi cheklovlar tizimi qavariq to'plamni - qavariq ko'pburchakni hosil qiladi. Ushbu to'plam cheklangan yoki cheksiz bo'lishi mumkin. Chiziqli dasturlash masalasining maqsad funksiyasi ham qavariq funksiya hisoblanadi. Shunday qilib, chiziqli dasturlash masalasi qavariq dasturlash masalasining alohida holatidir.
Tenglik ko'rinishidagi chiziqli dasturlash muammosi uchun cheklovlar tizimini ko'rib chiqing
(1)
Chiziqli tenglamalar tizimi (1) kamida bitta yechimga ega bo'lsa, izchil bo'ladi. Agar tenglamalardan biri boshqalarning chiziqli birikmasi sifatida ifodalanishi mumkin bo'lsa, tizim (1) ortiqcha deb ataladi.
(1) sistemada o'zgaruvchilar soni (n noma'lum) cheklashlar sonidan m ko'p bo'ladi.Bu tizimning darajasi m (tizim ortiqcha emas) va bu tizim (1) ga teng deb faraz qilamiz. izchil bo’ladi.Unda ularning umumiy sonidan m o’zgaruvchi asosiy o’zgaruvchilarni hosil qiladi, boshqa o’zgaruvchilar esa noasosiy deyiladi.Agar tenglamalar sistemasi yechimga ega bo’lsa, u ham asosiy yechimga ega bo’ladi.Tenglamalar tizimining yechimi (1) agar uning barcha komponentlari manfiy bo'lmasa joiz deyiladi.Agar chiziqli tenglamalar sistemasi ruxsat etilgan yechimga ega bo'lsa, u holda u ham asosiy ruxsat etilgan yechimga ega bo'ladi.(1) sistemaning barcha mumkin bo'lgan yechimlarining qavariq to'plami, ya'ni to'plami. chiziqli dasturlash masalasining yechimlari qavariqdir.Ushbu to'plam tekisliklar (giperplanlar) tomonidan tuzilganligi sababli, u qavariq ko'pburchak ko'rinishiga ega.Asosiy mumkin bo'lgan yechim qavariq ko'pburchakning ekstremal nuqtasiga (uning yuzlari yoki cho'qqilari) mos keladi. chiziqli dasturlash muammosining optimal yechimi mavjud bo'lsa, unda asos mavjud optimal yechim hisoblanadi.
Chiziqli dasturlash masalasining maqsad funksiyasi tekislik (yoki uchdan ortiq o'zgaruvchilar uchun giperplan) tenglamasidir. Chiziqli dasturlash masalasining maqsad funktsiyasi qavariq ko'pburchakning tepasida yoki uning yuzlaridan birida maksimal yoki minimal qiymatiga etadi. Shunday qilib, chiziqli dasturlash masalasining yechimi (yechimlari) qavariq ko'pburchakning cho'qqilarida yotadi va uni topish uchun qavariq ko'pburchak cho'qqilarida maqsad funktsiyasining qiymatlarini hisoblash kerak. shartlar-muammoning cheklovlari.
Chiziqli dasturlash masalasini grafik usulda yechish.
Matematik modelni yaratishning qiyinligi o'zgaruvchilarni aniqlash va keyinchalik ushbu o'zgaruvchilarning matematik funktsiyalari shaklida maqsad va cheklovlarni ifodalashda yotadi. Agar model faqat ikkita o'zgaruvchini o'z ichiga olgan bo'lsa, u holda chiziqli dasturlash masalasini grafik tarzda echish mumkin. Uchta o'zgaruvchi bo'lsa, grafik echim kamroq vizual bo'ladi va o'zgaruvchilarning katta qiymati bilan bu hatto mumkin emas. Biroq, grafik yechim chiziqli dasturlash masalasini hal qilishning umumiy usulini ishlab chiqish uchun asos bo'lib xizmat qiladigan xulosalar chiqarishga imkon beradi.
Grafik usuldan foydalanishning birinchi bosqichi amalga oshirilishi mumkin bo'lgan echimlarni geometrik tarzda ifodalashdir, ya'ni. modelning barcha cheklovlari bir vaqtning o'zida qondiriladigan ruxsat etilgan echimlar (ODD.) sohasini qurish. Qabul qilinganda grafik yechim o'zgaruvchi gorizontal o'q bo'ylab chiziladi va - vertikal bo'ylab. SDEni shakllantirishda o'zgaruvchilarning salbiy bo'lmasligi shartini bajarish zarurati bilan bog'liq bo'lgan nomaqbul echimlarni olishning oldini olish kerak. Qurilishdan oldin, ODR joylashgan kvadrantlarni aniqlash kerak. Kvadrantlar o'zgaruvchilarning belgilari bilan aniqlanadi va . O'zgaruvchilarning manfiy bo'lmasligi shartlari va ularning ruxsat etilgan qiymatlari oralig'ini birinchi kvadrant bilan cheklaydi. Agar o'zgaruvchi belgi bilan chegaralanmagan bo'lsa, u holda maydon birinchi va ikkinchi kvadrantlar bilan, agar , bo'lsa - birinchi va to'rtinchi kvadrantlar bilan chegaralanadi. Tekislikdagi yechim fazosining boshqa chegaralari cheklash tenglamalari bo'yicha tuzilgan to'g'ri chiziqlar bilan ko'rsatiladi, agar belgi "=" belgisi bilan almashtirilgan bo'lsa. Bunday holda, quyidagilarni hisobga olish kerak: barcha cheklovlarning o'ng tomonlari salbiy bo'lmasligi kerak. . Har qanday cheklov bo'lsa< 0, то необходимо коэффициенты соответствующего ограничения слева и справа до-множить на "-1" и изменить знак неравенства данного ограничения на противоположный. Области, в которых выполняются соответствующие ограничения в виде неравенств, указываются стрелками, направленными в сторону допустимых значений переменных.
Qurilishlar natijasida eritmalar bo'shlig'ini aniqlaydigan ko'pburchak olinadi. Agar cheklovlardan birida "=" belgisi bo'lsa, ODD segmentga aylanadi.
Eritma ko'pburchagining maydoni yoki chegaralariga tegishli bo'lgan har bir nuqtada barcha cheklovlar bajariladi, shuning uchun bu nuqtalarga mos keladigan barcha echimlar haqiqiydir. Yechim fazosi cheksiz sonli shunday nuqtalarni o'z ichiga oladi, shunga qaramay, optimal echimni topish mumkin. Buning uchun o'zgaruvchilar tekisligida qurish kerak , maqsad funktsiyasining gradienti. Optimal nuqtani aniqlash hal qilinishi kerak bo'lgan muammoga bog'liq.
Agar maqsad funktsiyasida maksimallashtirish masalasi aniqlansa, u holda optimal nuqta gradientni oshirish yo'nalishi bo'yicha, agar minimallashtirish masalasi aniqlangan bo'lsa, u holda maqsad funktsiyasi gradientini kamaytirish yo'nalishi bo'yicha joylashadi. Optimal nuqtani aniqlash uchun biz maqsad funktsiyasini qabul qilib bo'lmaydigan yechimlar hududiga siljiguncha gradientni oshirish (kamaytirish) yo'nalishiga o'tkazamiz.
Yechim fazosida optimal nuqta topilgach, uning koordinatalari va undagi maqsad funksiyasining qiymati aniqlanadi. Optimal nuqtani tanlashning to'g'riligini eritma ko'pburchak uchlaridagi maqsad funktsiyasini hisoblash orqali tekshirish mumkin. LLPda amalga oshirilishi mumkin bo'lgan echimlar sohasi har doim konveks to'plamidir, ya'ni. shunday to'plamki, bu to'plamga tegishli har qanday ikkita nuqta bilan bir qatorda, bu ikki nuqtani bog'lovchi segment ham bir xil to'plamga tegishli. Har qanday funktsiya gradient yo'nalishi bo'yicha eng tez o'sadi.
Simpleks usulida chiziqli dasturlash masalasini yechish.
bevosita vazifa.
Lineer dasturlash masalasini kanonik shaklda ko'rib chiqing:
Funksiyaning maksimal (minimal) ni toping sharoitlarda
Bu muammoning yechimi borligi taxmin qilinmoqda. Optimal yechimni topish uchun yo'l qo'yiladigan asosiy yechimlarni topish va ulardan optimal asosiy yechimni tanlash kerak.
Simpleks usuli algebraik usul chiziqli dasturlash masalalarini yechish. Hisoblash jarayonida eritma ko'pburchak (ODP) cho'qqilari har bir cho'qqida optimallik shartlarini tekshirish bilan ketma-ket chetlab o'tiladi. Bundan tashqari, qo'shni cho'qqiga har bir o'tish maqsad funktsiyasining yaxshilanishi bilan birga keladi.
Simpleks usulining hisoblash protseduralari.
LLPni echishning grafik usuli bilan optimal yechim har doim yechim maydonining burchak (ekstremal) nuqtalaridan biriga to'g'ri keladi. Bu natija simpleks usulini qurish asosida yotadi. Simpleks usuli yechim fazosining geometrik tasvirining ko'rinishiga ega emas.
Simpleks usuli tartiblangan jarayonni amalga oshiradi, bunda dastlabki ruxsat etilgan burchak nuqtasidan boshlab, maqbul yechim nuqtasi topilgunga qadar bir ruxsat etilgan chekka nuqtadan ikkinchisiga ketma-ket o'tishlar amalga oshiriladi.
Belgilaymiz: - kanonik shaklda keltirilgan MChJdagi o'zgaruvchilarning umumiy soni; - boshlang'ich o'zgaruvchilar soni; - cheklashlar soni, - qo'shimcha o'zgaruvchilar soni, keyin .
Eritma ko'pburchakning har bir tepasida - nolga teng bo'lmagan o'zgaruvchilar va () - nol o'zgaruvchilar mavjud.
Nolga teng bo'lmagan o'zgaruvchilar asosiy, nol o'zgaruvchilar esa asosiy bo'lmaganlar deb ataladi.
Biz tenglik tizimini maqsad funktsiyasining tengligi bilan to'ldiramiz, shu bilan birga biz uni har qanday cho'qqi uchun asosda doimo mavjud bo'lgan asosiy o'zgaruvchi deb hisoblaymiz.
Yechimni olish uchun dastlabki ruxsat etilgan asos tuziladi, unda asosiy o'zgaruvchilar birlik vektorlari sifatida ifodalanishi kerak. Bu shuni anglatadiki, berilgan cho'qqini ifodalovchi tenglamalar har bir asosiy o'zgaruvchini 1 omil bilan faqat bitta qatorga kiritishi kerak.
Simpleks jadvalini tuzish uchun dastlabki qabul qilinadigan asosni tanlashda CT(0) ning birinchi bosqichida boshlang'ich o'zgaruvchilar nolga tenglashtiriladi va asosiy bo'lmagan, kiritilgan qo'shimcha o'zgaruvchilar orasida koeffitsientlari birga teng bo'lgan o'zgaruvchilar tanlanadi. (2) - (4) tengliklardagi o'zgaruvchilar bazaviy bo'lib, koeffitsientlari 0 ga teng bo'lgan - qatoriga kiritiladi. Simpleks jadvalini to'ldirish uchun maqsad funksiyani ko'rinishga o'tkazish kerak. . Shunday qilib, biz nihoyat olamiz:
Simpleks jadvalini tuzishda quyidagi qoidalarga amal qilinadi:
eng chap ustun asosiy o'zgaruvchilarni o'z ichiga oladi va ;
eng o'ng ustunda cheklovlarning o'ng qismlari mavjud;
Birinchi qatorda ma'lum bir tartibda o'zgaruvchilar mavjud:
birinchidan, keyin asosiy bo'lmagan o'zgaruvchilar, asosiy o'zgaruvchilar o'ng tomondan (IF) oldingi oxirgi ustunlarda joylashgan. Koeffitsientlarni CT(0) ga yozamiz:
|
|
|
|
|
|
|
AGAR
|
|
1
|
|
|
0
|
0
|
0
|
0
|
|
0
|
|
|
1
|
0
|
0
|
|
|
0
|
|
|
0
|
1
|
0
|
|
|
0
|
|
|
0
|
0
|
1
|
|
Har qanday cho'qqining optimalligi joriy simpleks jadvali qatoridagi asosiy bo'lmagan o'zgaruvchilar koeffitsientlari bilan aniqlanadi:
Maksimallashtirish muammosi uchun - qatoridagi asosiy bo'lmagan o'zgaruvchilar uchun barcha koeffitsientlar manfiy bo'lmagan (>0) bo'lsa, bu cho'qqi optimal hisoblanadi;
Minimallashtirish muammosi uchun bu cho'qqi optimal bo'ladi, agar - qatoridagi asosiy bo'lmagan o'zgaruvchilar uchun barcha koeffitsientlar ijobiy bo'lmasa (< 0).
Agar maksimallashtirish (minimallashtirish) masalasida - qatoridagi bitta asosiy bo'lmagan o'zgaruvchi koeffitsientga ega bo'lsa.<0(>0), keyin joriy nuqta optimal emas va asosni o'zgartirish kerak. Buning uchun - qatorida eng salbiy (musbat) koeffitsientga ega bo'lgan asosiy bo'lmagan o'zgaruvchini tanlang. Tanlangan asosiy bo'lmagan o'zgaruvchi yangi bazaga kiritiladi, shuning uchun u kiritilgan o'zgaruvchi deb ataladi. Bazisdan olinadigan bazis o'zgaruvchiga istisno o'zgaruvchisi deyiladi.
Cheklangan o'zgaruvchi asosiy o'zgaruvchi bo'lib, kiritilgan o'zgaruvchini kiritgandan so'ng qo'shni cho'qqiga o'tishda birinchi navbatda "0" ga aylanadi.
Kiritilgan o'zgaruvchining ustuni hal qiluvchi ustun deb ataladi.
Chiqarilgan o'zgaruvchining qatori hal qiluvchi qator deb ataladi.
Ruxsat beruvchi ustun va qatorning kesishishi ruxsat beruvchi elementni (RE) belgilaydi.
Cheklangan o'zgaruvchini aniqlash uchun:
barcha asosiy o'zgaruvchilarning o'ng qismlarini (satrdan tashqari) hal qiluvchi ustunning mos keladigan ijobiy koeffitsientlariga bo'lish;
olingan nisbatlardan eng kichigini tanlang.
"0" ga va manfiy qiymatga bo'linishga yo'l qo'yilmaydi, chunki bu kesishuvchi cho'qqining yo'qligiga yoki ODT dan tashqaridagi cho'qqiga olib keladi.
Qo'shni cho'qqiga o'tish uchun ST(0) va ST(1) o'rtasidagi munosabatni aniqlaydigan o'tish matritsasi B(0) hosil qilish kerak: ST(1) = B(0) ST(0).
Birlik ortslari (n - 1) ustunlar shaklida, identifikatsiya matritsasining birlik ortslariga muvofiq tartibga solingan va asosiy diagonalda nolga teng bo'lmagan elementli bitta ixtiyoriy ustunga ega bo'lgan n o'lchamli ixtiyoriy kvadrat matritsa uchun, teskari matritsa quyidagi qoidaga muvofiq amalga oshiriladi:
j-ustunning har bir elementi RE ga bo'linadi va belgini teskarisiga o'zgartiradi, hal qiluvchi elementdan tashqari.
Sun'iy boshlang'ich asos. M - usul.
Agar boshlang'ich cheklov "="" tenglik shaklida yozilsa yoki "" belgisiga ega bo'lsa, u holda qabul qilinadigan boshlang'ich asosiy yechimni darhol olish mumkin emas, chunki masalani standart shaklda yozishda qo'shimcha o'zgaruvchilar kiritilgandan so'ng, a varianti hosil boʻlgan tenglamalar birlik vektorlari koʻrinishida dastlabki ruxsat etilgan asosni shakllantirishga imkon bermasa, paydo boʻlishi mumkin.
Bunday holda, dastlabki ruxsat etilgan bazani topish uchun qo'shimcha sun'iy o'zgaruvchilar kiritiladi. Sun'iy o'zgaruvchilar vazifa mazmuni bilan bog'liq emas, ularni kiritish faqat tegishli hisoblash sxemasi barcha sun'iy o'zgaruvchilar nolga teng bo'lgan optimal echimni ta'minlasagina ruxsat etiladi.
R o'zgaruvchilari ODT cho'qqilaridan biriga keyingi o'tish nuqtai nazaridan dastlabki ruxsat etilgan asosni aniqlaydi. Maqsad funksiyasida sun'iy o'zgaruvchilardan foydalanganlik uchun M jazo kiritiladi.Mni maksimallashtirish masalasida manfiy (M)<<0), в задаче минимизации М положительное (М>>0).
M xossasi: Asl MChJning har bir o'zgaruvchisi olishi mumkin bo'lgan har qanday qiymatni aniqlaydigan har qanday chekli qiymat bilan qo'shish (ayirish) paytida uning qiymati (M o'zgaruvchisi) o'zgarmaydi, xususan,
Formula (1.2), o'zgaruvchilarning manfiy emasligiga cheklovlar (ha, yo'q) - formula (1.3) (1.1) i = 1, ... m (1.2) (1.3) Chiziqli dasturlash masalalarini echish algoritmi ularni olib kelishni talab qiladi. maqsad funktsiyasi qachon kanonik shaklga ...
|
