Simpleksni quyidagi zlp usuli yordamida yeching. Chiziqli dasturlash masalalarini yechish xizmati. Simpleks masalani usul bilan yechish

Simpleks usuli bilan masalani yechish misoli, shuningdek, dual masalani yechish misoli ko'rib chiqiladi.

Tarkib

Vazifa

Tovarlarning uch guruhini amalga oshirish uchun tijorat korxonasi b 1 = 240, b 2 = 200, b 3 = 160 birlik miqdorida uchta turdagi cheklangan moddiy va pul resurslariga ega. Shu bilan birga, 1 ming rubl uchun 1 guruh tovarlarni sotish uchun. aylanmada birinchi turdagi resurs 11 = 2 birlik, ikkinchi turdagi resurs 21 = 4 birlik, uchinchi turdagi resurs 31 = 4 birlik miqdorida sarflanadi. birliklar. 1 ming rubl uchun 2 va 3 guruhli tovarlarni sotish uchun. aylanmasi mos ravishda birinchi turdagi resurs 12 = 3, a 13 = 6 birlik, ikkinchi turdagi resurs 22 = 2, 23 = 4 birlik, resurs miqdorida sarflanadi. uchinchi turdagi a 32 = 6, a 33 = 8 birlik miqdorida. 1 ming rubl uchun uchta guruh tovarlarini sotishdan olingan foyda. aylanma mos ravishda c 1 \u003d 4, c 2 \u003d 5, c 3 \u003d 4 (ming rubl). Savdo korxonasining foydasi maksimal bo'lishi uchun tovar aylanmasining rejalashtirilgan hajmi va tuzilishini aniqlang.

Tovar aylanishini rejalashtirishning bevosita muammosiga, echiladigan simpleks usuli, tuzing ikki tomonlama muammo chiziqli dasturlash.
O'rnatish o'zgaruvchilarning konjugat juftlari to'g'ridan-to'g'ri va ikki tomonlama muammolar.
Konjugat juft o'zgaruvchilarga ko'ra, to'g'ridan-to'g'ri muammoning echimidan olinadi ikki tomonlama muammoni hal qilish, unda resurslarni baholash tovarlarni sotishga sarflanadi.

Simpleks masalani usul bilan yechish

X 1, x 2, x 3 - sotilgan tovarlar soni, ming rubl, mos ravishda 1, 2, 3 guruh bo'lsin. Keyin masalaning matematik modeli quyidagi ko'rinishga ega bo'ladi:

F = 4 x 1 + 5 x 2 + 4 x 3 ->maks

0)))(~)" title="(!LANG:delim(lbrace)(matritsa(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

Simpleksni usul bilan yechamiz.

Tengsizliklarni tenglikka aylantirish uchun x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 qo‘shimcha o‘zgaruvchilar kiritamiz.

Asos sifatida biz x 4 \u003d 240 ni olamiz; x5 = 200; x6 = 160.

Ma'lumotlar kiritiladi simpleks jadvali

Simpleks jadval raqami 1

Maqsad funktsiyasi:

0 240 + 0 200 + 0 160 = 0

Biz ballarni formula bo'yicha hisoblaymiz:

D 1 \u003d 0 2 + 0 4 + 0 4 - 4 \u003d - 4
D 2 \u003d 0 3 + 0 2 + 0 6 - 5 \u003d - 5
D 3 \u003d 0 6 + 0 4 + 0 8 - 4 \u003d - 4
D 4 \u003d 0 1 + 0 0 + 0 0 - 0 \u003d 0
D 5 \u003d 0 0 + 0 1 + 0 0 - 0 \u003d 0
D 6 \u003d 0 0 + 0 0 + 0 1 - 0 \u003d 0

Salbiy baholar mavjud bo'lganligi sababli, reja optimal emas. Eng past reyting:

Bazisga x 2 o'zgaruvchisini kiritamiz.

Biz asosni qoldirib, o'zgaruvchini aniqlaymiz. Buning uchun biz x 2 ustuni uchun eng kichik manfiy bo'lmagan nisbatni topamiz.

= 26.667

Eng kichik manfiy bo'lmagan: Q 3 = 26,667. Bazisdan x 6 o'zgaruvchisini olamiz

3 qatorni 6 ga bo'ling.
1-qatordan 3-qatorni 3 ga ko'paytiring
2-qatordan 3-qatorni 2 ga ko'paytiring


Biz hisoblaymiz:

Biz yangi jadvalni olamiz:

Simpleks jadval raqami 2

Maqsad funktsiyasi:

0 160 + 0 440/3 + 5 80/3 = 400/3

Biz ballarni formula bo'yicha hisoblaymiz:

D 1 \u003d 0 0 + 0 8/3 + 5 2/3 - 4 \u003d - 2/3
D 2 \u003d 0 0 + 0 0 + 5 1 - 5 \u003d 0
D 3 \u003d 0 2 + 0 4/3 + 5 4/3 - 4 \u003d 8/3
D 4 \u003d 0 1 + 0 0 + 5 0 - 0 \u003d 0
D 5 \u003d 0 0 + 0 1 + 5 0 - 0 \u003d 0
D 6 \u003d 0 (-1) / 2 + 0 (-1) / 3 + 5 1/6 - 0 \u003d 5/6

D 1 = - 2/3 salbiy baho bo'lgani uchun reja optimal emas.

Bazisga x 1 o'zgaruvchisini kiritamiz.

Biz asosni qoldirib, o'zgaruvchini aniqlaymiz. Buning uchun biz x 1 ustun uchun eng kichik manfiy bo'lmagan nisbatni topamiz.

Eng kichik manfiy bo'lmagan: Q 3 \u003d 40. Biz x 2 o'zgaruvchisini asosdan olamiz

3-qatorni 2/3 ga bo'ling.
2-qatordan 3-qatorni 8/3 ga ko'paytiring


Biz hisoblaymiz:

Biz yangi jadvalni olamiz:

Simpleks jadval raqami 3

Maqsad funktsiyasi:

0 160 + 0 40 + 4 40 = 160

Biz ballarni formula bo'yicha hisoblaymiz:

D 1 \u003d 0 0 + 0 0 + 4 1 - 4 \u003d 0
D 2 \u003d 0 0 + 0 (-4) + 4 3/2 - 5 \u003d 1
D 3 \u003d 0 2 + 0 (-4) + 4 2 - 4 \u003d 4
D 4 \u003d 0 1 + 0 0 + 4 0 - 0 \u003d 0
D 5 \u003d 0 0 + 0 1 + 4 0 - 0 \u003d 0
D 6 \u003d 0 (-1) / 2 + 0 (-1) + 4 1/4 - 0 \u003d 1

Salbiy baholar yo'qligi sababli, reja optimaldir.

Muammoning yechimi:

x 1 = 40; x2 = 0; x 3 \u003d 0; x 4 = 160; x5 = 40; x6 = 0; F max = 160

Ya'ni, birinchi turdagi tovarlarni 40 ming rubl miqdorida sotish kerak. 2 va 3 turdagi tovarlarni sotish shart emas. Bunday holda, maksimal foyda F max = 160 ming rubl bo'ladi.

Ikki tomonlama muammoni hal qilish

Ikki tomonlama muammo quyidagicha ko'rinadi:

Z = 240 y 1 + 200 y 2 + 160 y 3 ->min

Title="(!LANG:delim(lbrace)(matritsa(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}

Tengsizliklarni tenglikka aylantirish uchun y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 qo‘shimcha o‘zgaruvchilar kiritamiz.

To'g'ridan-to'g'ri va dual masalalarning o'zgaruvchilar juftliklari quyidagi shaklga ega:

To'g'ridan-to'g'ri masalaning oxirgi 3-sonli simpleks jadvalidan biz ikkilamchi masalaning echimini topamiz:

Z min = F max = 160;
y 1 \u003d D 4 \u003d 0; y 2 \u003d D 5 \u003d 0; y 3 \u003d D 6 \u003d 1; y 4 \u003d D 1 \u003d 0; y 5 \u003d D 2 \u003d 1; y 6 \u003d D 3 \u003d 4;

Y1=0; y2 = 0; y 3 = 1; Z min = 160;

Simpleks usuli− bu tayanch rejalarni tartibli sanab o‘tish usulidir (tartib berish keyingi rejaga o‘tishda maqsad funksiyasi qiymatining monoton o‘zgarishi bilan ta’minlanadi). Bunday holda, printsipga rioya qilish kerak: har bir keyingi qadam yaxshilanishi yoki o'ta og'ir holatlarda maqsad funktsiyasining qiymatini yomonlashtirmasligi kerak.

MChJni hal qilish uchun simpleks usuli u kanonik shaklga qisqartiriladi, ya'ni. cheklovlardan - tengsizliklardan cheklash - tenglik qilish kerak. Buning uchun har bir cheklov qo'shimcha salbiy bo'lmagan bilan to'ldiriladi balans o'zgaruvchisi tengsizlik belgisi “£” bo‘lsa “+” belgisi bilan, tengsizlik belgisi “³” bo‘lsa, “–” belgisi bilan.

Maqsad funktsiyasida bu qo'shimcha o'zgaruvchilar nol koeffitsientlar bilan kiradi, ya'ni. maqsad funksiya yozuvi o'zgarmaydi. Salbiy bo'lmagan shartga tobe bo'lmagan har bir o'zgaruvchini ikkita manfiy bo'lmagan o'zgaruvchilarning farqi sifatida ko'rsatish mumkin: .

Agar vazifa cheklovlari resurslarning mavjudligi va sarflanishini aks ettirsa, u holda kanonik shaklda yozilgan topshiriq rejasidagi qo'shimcha o'zgaruvchining raqamli qiymati foydalanilmagan resurs miqdoriga teng bo'ladi.

Muammoni simpleks usuli bilan hal qilish uchun biz foydalanamiz chiziqli tenglamalar tizimining qisqartirilgan simpleks jadvallari va o'zgartirilgan Iordaniyani yo'q qilish usuli.

1. Biz birinchi asosiy rejani tuzamiz

Vazifa bir xil bo'lib qoladi. Tengsizliklar tizimining standart shaklini (1) qo'shimcha muvozanat o'zgaruvchilari kiritish orqali tenglamalar tizimining kanonik shakliga keltiramiz. x 3 , x 4 , x 5 ,x 6 .

Iqtisodiy ma'noda qo'shimcha o'zgaruvchilar qiymatlari x 3 , x 4 , x 5 mahsulot sotilgandan keyin xomashyo balansini aniqlash.

Olingan tenglamalar tizimining matritsasi quyidagi ko'rinishga ega:

Buni matritsada ko'rish mumkin A 4-tartibning asosiy minori determinant bo'lib, qo'shimcha o'zgaruvchilar uchun birlik koeffitsientlaridan tashkil topgan. x 3 , x 4 , x 5 ,x 6 , chunki u nolga teng emas va 1 ga teng. Bu shuni anglatadiki, bu o'zgaruvchilar uchun ustun vektorlari chiziqli mustaqil, ya'ni. shakl asos, va mos keladigan o'zgaruvchilar x 3 , x 4 , x 5 ,x 6 ta Asosiy(Asosiy). O'zgaruvchilar x 1 , x 2 chaqiriladi ozod(kichik).

Erkin o'zgaruvchilar bo'lsa x 1 va x 2 so'rang turli ma'nolar, keyin, tizimni asosiy o'zgaruvchilarga nisbatan yechish, biz cheksiz maxsus echimlar to'plamini olamiz. Agar bo'sh o'zgaruvchilar uchun faqat nol qiymatlar o'rnatilgan bo'lsa, u holda ma'lum echimlarning cheksiz to'plamidan, asosiy yechimlar- asosiy rejalar.

O'zgaruvchilarning asosiy bo'lishi mumkinligini bilish uchun ushbu o'zgaruvchilarning koeffitsientlaridan tashkil topgan determinantni hisoblash kerak. Agar bu determinant nolga teng bo'lmasa, bu o'zgaruvchilar asosiy bo'lishi mumkin.


Asosiy echimlar soni va asosiy o'zgaruvchilar guruhlari mos keladigan soni dan ko'p bo'lmasligi mumkin, bu erda n o'zgaruvchilarning umumiy soni, r asosiy o'zgaruvchilar soni, r≤ m≤ n.

Bizning vazifamiz uchun r = 4; n= 6. Keyin , ya'ni. 4 ta asosiy oʻzgaruvchidan iborat 15 ta guruh (yoki 15 ta asosiy yechim) mumkin.

Asosiy o'zgaruvchilarga nisbatan tenglamalar tizimini yechamiz x 3 , x 4 , x 5 ,x 6:

Erkin o'zgaruvchilar deb faraz qilsak x 1 = 0, x 2 = 0, biz asosiy o'zgaruvchilarning qiymatlarini olamiz: x 3 = 312; x 4 = 15; x 5 = 24;x 6 = -10, ya'ni. asosiy yechim = (0; 0; 312; 15; 24; -10) bo'ladi.

Bu asosiy yechim qabul qilib bo'lmaydigan, chunki x 6 = –10 ≤ 0 va cheklash sharti bilan x 6 ≥ 0. Shuning uchun, o'zgaruvchi o'rniga x 6 asos sifatida siz bepullar orasidan boshqa o'zgaruvchini olishingiz kerak x 1 yoki x 2 .

Biz keyingi yechimni qisqartirilgan simpleks jadvallari yordamida amalga oshiramiz, birinchi jadvalning qatorlarini tizim koeffitsientlari bilan quyidagi tarzda to'ldiramiz (1-jadval):

1-jadval

F- satr deyiladi indeks. U qarama-qarshi belgilar bilan olingan ob'ektiv funktsiya koeffitsientlari bilan to'ldiriladi, chunki funktsiya tenglamasi quyidagicha ifodalanishi mumkin. F = 0 – (– 4x 1 – 3x 2).

Bepul a'zolar ustunida b i salbiy element mavjud b 4 = -10, ya'ni. tizimning yechimi yaroqsiz. To'g'ri echimni olish uchun (tayanch reja), element b 4 salbiy bo'lmasligi kerak.

Tanlang x 6 - salbiy bepul a'zosi bo'lgan chiziq. Ushbu qatorda salbiy elementlar mavjud. Ulardan birini tanlang, masalan, "-1" in x 1 - ustun va x 1 - ustun sifatida qabul qilinadi ruxsat ustuni(u o'zgaruvchi ekanligini aniqlaydi x 1 bepuldan asosiyga o'tadi).

Biz bepul a'zolarni baham ko'ramiz b i tegishli elementlar bo'yicha a hisoblanadi hal qiluvchi ustun, biz olamiz baholash munosabatlariΘ i==(24, 15, 12, 10). Ulardan biz eng kichik ijobiyni tanlaymiz (min i=10) mos keladi ruxsat liniyasi. Ruxsat qatori o'zgaruvchini belgilaydi x j, bu keyingi bosqichda asosdan chiqib ketadi va erkin bo'ladi. Shunung uchun x 6-satr ruxsat beruvchi chiziq va "-1" elementi faollashtiruvchi element. Biz uni aylantiramiz. O'zgaruvchilar x 1 va x 6 almashtirildi.

Taxminiy nisbatlar t i Har bir satrda qoidalar bilan belgilanadi:

1) t i= agar b i va a hisoblanadi bor turli belgilar;

2) t i= ∞ agar b i= 0 va a hisoblanadi < 0;

3) t i= ∞ agar a hisoblanadi = 0;

4) t i= 0 agar b i= 0 va a hisoblanadi > 0;

5) t i= agar b i va a hisoblanadi bir xil belgilarga ega.

Biz ruxsat beruvchi element bilan o'zgartirilgan Iordaniyani yo'q qilish (MJJI) qadamini qo'yamiz va quyidagi qoida bo'yicha yangi jadval tuzamiz (2-jadval):

1) hal qiluvchi element (RE) o'rniga qiymat o'rnatiladi, uning teskarisi, ya'ni. ;

2) ruxsat beruvchi chiziqning elementlari RE ga bo'linadi;

3) hal qiluvchi ustunning elementlari RE ga bo'linadi va belgi o'zgaradi;

4) qolgan elementlar to'rtburchaklar qoidasiga muvofiq topiladi:

Jadvaldan. 2 erkin a'zolar ekanligini ko'rsatadi b i-ustun salbiy emas, shuning uchun dastlabki ruxsat etilgan yechim olinadi - birinchi asosiy reja= (10; 0; 182; 5; 4; 0). Bunday holda, funktsiyaning qiymati F() = 40. Geometrik jihatdan bu tepaga to'g'ri keladi F(10; 0) eritma ko`pburchagi (1-rasm).

jadval 2

2. Biz rejani optimallik uchun tekshiramiz. Asosiy reja optimal emas, chunki ichida F-chiziq "-4" manfiy koeffitsientga ega. Biz rejani yaxshilaymiz.

3. Yangi asosni topish

Ruxsat beruvchi elementni qoidaga muvofiq tanlaymiz:

Biz eng kichik salbiy koeffitsientni tanlaymiz F- faollashtirish ustunini belgilaydigan "-4" qatori - x 6; o'zgaruvchan x 6 asosiy tilga tarjima qilish;

Biz t nisbatlarini topamiz i, ular orasida biz ruxsat beruvchi qatorga mos keladigan eng kichik ijobiyni tanlaymiz:

min Θ i = min(14, 5, 2, ∞) = 2, demak x 5 - chiziq - ruxsat beruvchi, o'zgaruvchan x 5 biz bepul tarjima qilamiz (o'zgaruvchilar x 5 va x 6 almashtirildi).

Ruxsat beruvchi satr va ustunning kesishmasida "2" ruxsat beruvchi element joylashgan;

Biz SHMZhI qadamini bajaramiz, biz stol quramiz. Yuqoridagi qoida bo'yicha 3 va yangi ma'lumot rejasini oling = (12; 0; 156; 3; 0; 2).

3-jadval

4. Yangi asosiy rejani optimallikni tekshirish

Asosiy reja ham optimal emas, chunki ichida F-chiziq "-1" manfiy koeffitsientga ega. Funktsiya qiymati F() = 48, bu geometrik jihatdan tepaga mos keladi E(12; 0) eritma ko`pburchagi (1-rasm). Biz rejani yaxshilaymiz.

5. Yangi asosni topish

x 2-ustun ruxsat etilgan, chunki ichida F-satrda eng kichik manfiy koeffitsient "-1" joylashgan x 2-ustun (D 2 = -1). Eng kichik t ni topish i: min Θ i = min(≈ 9, 6, ∞, 24) = 6, demak x 4-qator - ruxsat beruvchi. Ruxsat beruvchi element "1/2". O'zgaruvchilarni almashtirish x 2 va x to'rtta. Biz SHMZhI qadamini bajaramiz, biz stol quramiz. 4, biz yangi mos yozuvlar rejasini olamiz = (9; 6; 51; 0; 0; 5).

6. Asosiy rejani optimallik uchun tekshirish

DA F-chiziq, barcha koeffitsientlar manfiy emas, shuning uchun mos yozuvlar rejasi optimaldir. Geometrik jihatdan nuqtaga mos keladi D(9;6) (1-rasmga qarang). Optimal reja maqsad funksiyaning maksimal qiymatini beradi c.u.

Uch turdagi ko'ylaklarni ishlab chiqarish uchun iplar, tugmalar va matolardan foydalaniladi. Jadvalda iplar, tugmalar va matolarning zaxiralari, ularning bitta ko'ylakni tikish uchun sarflanishi ko'rsatilgan. Maksimal foyda va uni ta'minlaydigan mahsulotni chiqarishning optimal rejasini toping (topish ).

ko'ylak 1 ko'ylak 2 ko'ylak 3 Aktsiyalar iplar (m.) 1 9 3 96 tugmalar (dona) 20 10 30 640 mato ( 1 2 2 44 Foyda (R.) 2 5 4

Muammoning yechimi

Model qurish

Chiqarish uchun mo'ljallangan 1, 2 va 3-turdagi ko'ylaklar soni va soni.

Keyin resurs cheklovlari quyidagicha ko'rinadi:

Bundan tashqari, vazifaning ma'nosiga ko'ra

Olingan foydani ifodalovchi maqsadli funksiya:

Biz quyidagi chiziqli dasturlash muammosini olamiz:

Chiziqli dasturlash masalasini kanonik shaklga keltirish

Keling, muammoni kanonik shaklga keltiraylik. Keling, qo'shimcha o'zgaruvchilarni kiritamiz. Biz barcha qo'shimcha o'zgaruvchilarni nolga teng koeffitsient bilan maqsad funktsiyasiga kiritamiz. Cheklovlarning mavjud bo'lmagan chap qismlariga qo'shimcha o'zgaruvchilar qo'shamiz afzal turi, va biz tenglikni olamiz.

Muammoni simpleks usulida yechish

Simpleks jadvalini to'ldiring:

Muammoni maksimal darajada yechayotganimiz sababli, masalani maksimal yechishda indeks chizig‘ida manfiy sonlarning bo‘lishi biz optimal yechimni olmaganligimizni va 0-iteratsiya jadvalidan o‘tish zarurligini ko‘rsatadi. keyingisi.

Keyingi iteratsiyaga o'tish quyidagicha amalga oshiriladi:

yetakchi ustun oʻyinlari

Kalit qator bo'sh a'zolar va etakchi ustun a'zolarining minimal nisbati bilan belgilanadi (simpleks nisbatlar):

Kalit ustuni va kalit satrining kesishmasida biz faollashtiruvchi elementni topamiz, ya'ni. 9.

Endi 1-iteratsiyani kompilyatsiya qilishni boshlaymiz: birlik vektor o'rniga vektorni kiritamiz.

Yangi jadvalda ruxsat beruvchi element o'rniga 1 ni yozamiz, kalit ustunining qolgan barcha elementlari nolga teng. Kalit satr elementlari ruxsat beruvchi elementga bo'linadi. Jadvalning barcha boshqa elementlari to'rtburchaklar qoidasiga muvofiq hisoblanadi.

1-iteratsiya mos keladigan kalit ustuni

Yechish elementi 4/3 raqamidir. Biz vektorni bazisdan chiqaramiz va o'rniga vektorni kiritamiz. Biz 2-iteratsiya jadvalini olamiz.

2-iteratsiya uchun kalit ustuni mos keladi

Biz kalit qatorni topamiz, buning uchun biz quyidagilarni aniqlaymiz:

Yechish elementi 10/3 raqamidir. Biz vektorni bazisdan chiqaramiz va o'rniga vektorni kiritamiz. Biz 3-iteratsiya jadvalini olamiz.

№ BP c B A o x 1 x2 x 3 x4 x5 x6 Simpleks 2 5 4 0 0 0 munosabatlar 0 x4 0 96 1 9 3 1 0 0 32/3 x5 0 640 20 10 30 0 1 0 64 x6 0 44 1 2 2 0 0 1 22 F j - c j 0 -2 -5 -4 0 0 0 1 x2 5 32/3 1/9 1 1/3 1/9 0 0 32 x5 0 1600/3 170/9 0 80/3 -10/9 1 0 20 x6 0 68/3 7/9 0 4/3 -2/9 0 1 17 F j - c j 160/3 -13/9 0 -7/3 5/9 0 0 2 x2 5 5 -1/12 1 0 1/6 0 -1/4 -- x5 0 80 10/3 0 0 10/3 1 -20 24 x 3 4 17 7/12 0 1 -1/6 0 3/4 204/7 F j - c j 93 -1/12 0 0 1/6 0 7/4 3 x2 5 7 0 1 0 1/4 1/40 -3/4 x 1 2 24 1 0 0 1 3/10 -6 x 3 4 3 0 0 1 -3/4 -7/40 17/4 F j - c j 95 0 0 0 1/4 1/40 5/4

Indeks qatorida barcha a'zolar manfiy emas, shuning uchun chiziqli dasturlash masalasining quyidagi yechimi olinadi (biz uni bo'sh a'zolar ustunidan yozamiz):

1-turdagi 24 ta, 2-turdagi 7 ta, 3-turdagi 3 ta ko‘ylak tikish kerak. Bunday holda, olingan foyda maksimal bo'ladi va 95 rublni tashkil qiladi.

Chiziqli dasturlash masalasini hal qilish kerak.

Maqsad funktsiyasi:

2x 1 +5x 2 +3x 3 +8x 4 →min

Cheklash shartlari:

3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x1 +7x2 +x3 ≥1

Cheklashlar tizimini kanonik shaklga keltiramiz, buning uchun qo'shimcha o'zgaruvchilar qo'shilgan holda tengsizliklardan tenglikka o'tish kerak.

Bizning muammomiz minimallashtirish muammosi bo'lgani uchun biz uni maksimallashtirish muammosiga aylantirishimiz kerak. Buning uchun maqsad funksiya koeffitsientlarining belgilarini qarama-qarshi bo'lganlarga o'zgartiramiz. Birinchi tengsizlikning elementlarini o'zgartirmasdan yozamiz, unga qo'shimcha x 5 o'zgaruvchisini qo'shamiz va "≤" belgisini "=" ga o'zgartiramiz. Ikkinchi va uchinchi tengsizliklar "≥" belgilariga ega bo'lganligi sababli, ularning koeffitsientlari belgilarini teskarisiga aylantirish va ularga mos ravishda qo'shimcha x 6 va x 7 o'zgaruvchilarni kiritish kerak. Natijada, biz ekvivalent muammoga duch kelamiz:

3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1

Biz boshlang'ich simpleks jadvalini shakllantirishga o'tamiz. Jadvalning F qatorida qarama-qarshi ishorali maqsad funksiya koeffitsientlari mavjud.

bepul a'zo
F
X5
X6
X7

Biz tuzgan jadvalda erkin a'zolar ustunida salbiy elementlar mavjud, biz ular orasida maksimal modulni topamiz - bu element: -6, u etakchi qatorni o'rnatadi - X6. Ushbu qatorda biz maksimal salbiy element modulini ham topamiz: -10 u X3 ustunida joylashgan bo'lib, u etakchi ustun bo'ladi. Boshlovchi qatordagi o‘zgaruvchi asosdan, yetakchi ustunga mos o‘zgaruvchi esa asosga kiritiladi. Simpleks jadvalini qayta hisoblaymiz:

X1 X2 X6 X4 bepul a'zo
F 0.8 8.9 0.3 6.5 -1.8
X5 4.6 0.8 -0.4 3 14.4
X3 0.4 -1.3 -0.1 0.5 0.6
X7 -2.6 -8.3 -0.1 0.5 -0.4

Biz tuzgan jadvalda erkin a'zolar ustunida salbiy elementlar mavjud, biz ular orasida maksimal modulni topamiz - bu element: -0,4, u etakchi qatorni o'rnatadi - X7. Ushbu satrda biz maksimal salbiy element modulini ham topamiz: -8.3 u X2 ustunida joylashgan bo'lib, u etakchi ustun bo'ladi. Boshlovchi qatordagi o‘zgaruvchi asosdan, yetakchi ustunga mos o‘zgaruvchi esa asosga kiritiladi. Simpleks jadvalini qayta hisoblaymiz:

X1 X7 X6 X4 bepul a'zo
F -1.988 1.072 0.193 7.036 -2.229
X5 4.349 0.096 -0.41 3.048 14.361
X3 0.807 -0.157 -0.084 0.422 0.663
X2 0.313 -0.12 0.012 -0.06 0.048

Erkin a'zolar ustunida manfiy elementlar bo'lmagani uchun amalga oshirish mumkin bo'lgan yechim topildi.F qatorda manfiy elementlar mavjud, ya'ni olingan yechim optimal emas. Keling, yetakchi ustunni aniqlaylik. Buning uchun biz F qatorida mutlaq qiymatdagi maksimal manfiy elementni topamiz - bu -1,988 Etakchi qator bo'sh elementning etakchi ustunning mos keladigan elementiga nisbati minimal bo'lgan qator bo'ladi. Etakchi qator X2, yetakchi element esa 0,313.

X2 X7 X6 X4 bepul a'zo
F 6.351 0.31 0.269 6.655 -1.924
X5 -13.895 1.763 -0.577 3.882 13.694
X3 -2.578 0.152 -0.115 0.577 0.539
X1 3.195 -0.383 0.038 -0.192 0.153

F qatorda manfiy elementlar yo'qligi sababli
optimal yechim topildi. Dastlabki vazifa minimalni topish bo'lganligi sababli, qarama-qarshi belgi bilan olingan F qatorning erkin hadi optimal echimdir. F=1,924
o'zgaruvchilar qiymatlari teng bo'lganda: x 3 =0,539, x 1 =0,153. x 2 va x 4 o'zgaruvchilar bazisga kiritilmagan, shuning uchun x 2 =0 x 4 =0.

№3 misol. Simpleks usulida chiziqli dasturlash masalasini yechish.
Funktsiyaning eng katta qiymatini topish (sun'iy asos)

Ushbu yechim saytda taqdim etilgan dasturning namunasidir.


Funksiyaning eng katta qiymatini toping

x 1 ≥ 0 x 2 ≥ 0

1. Tizimning erkin a'zolari salbiy bo'lmasligi kerak.

Bu shart bajarildi.


2. Tizimning har bir cheklovi tenglama bo'lishi kerak.

x 1 - 2 x2 ≤ 4
x 1 - x2 ≥ 1
x 1 + x2 ≤ 8
x 1 - 2 x2 + S1 = 4
x 1 - x2 - S2 = 1
x 1 + x2 + S3 = 8

S 1 ≥ 0, S 2 ≥ 0, S 3 ≥ 0. Kiritilgan o‘zgaruvchilar S 1 , S 2 , S 3 balans o‘zgaruvchilari deyiladi.


3. Topilgan boshlang‘ich bazisga mos keladigan F funksiyaning boshlang‘ich bazisini va qiymatini topish.


Asos nima?
Agar o'zgaruvchi berilgan tenglamaga bilan kirsa, berilgan tenglama uchun asosiy deyiladi birinchi omil va qolgan tenglamalarga kiritilmaydi (agar tenglamaning o'ng tomonida ijobiy raqam bo'lsa).
Agar har bir tenglamaning bazis o'zgaruvchisi bo'lsa, tizim bazisga ega deyiladi.
Asosiy bo'lmagan o'zgaruvchilar erkin o'zgaruvchilar deb ataladi.

Simpleks usulining g'oyasi nimada?
Har bir bazis funksiyaning bitta qiymatiga mos keladi. Ulardan biri eng yuqori qiymat F funktsiyalari.
Biz bir asosdan ikkinchisiga o'tamiz, F funktsiyasining qiymatini mavjud bo'lganidan kam bo'lmagan holda olamiz.
Shubhasiz, har qanday muammo uchun mumkin bo'lgan asoslar soni unchalik katta emas.
Shuning uchun, ertami-kechmi javob olinadi.

Bir asosdan ikkinchisiga o'tish qanday amalga oshiriladi?
Yechimni jadvallar ko'rinishida yozib olish qulayroqdir. Jadvalning har bir satri tizim tenglamasiga teng. Belgilangan chiziq funksiya koeffitsientlaridan iborat (quyidagi jadvalga qarang). Bu har safar o'zgaruvchilarni qayta yozmaslikka imkon beradi, bu esa ko'p vaqtni tejaydi.
Tanlangan qatorda eng katta ijobiy koeffitsientni tanlang (siz har qanday ijobiyni tanlashingiz mumkin).
Bu F funktsiyasining qiymatini mavjud bo'lganidan kam bo'lmagan holda olish uchun kerak.
Ustun tanlandi.
Tanlangan ustunning ijobiy koeffitsientlari uchun biz D nisbatini hisoblaymiz va tanlaymiz eng kichik qiymat.
Bu transformatsiyadan keyin erkin a'zolar ustuni ijobiy bo'lib qolishi uchun kerak.
Qator tanlandi.
Asosiy element bo'ladigan element aniqlanadi. Keyingi, biz hisoblaymiz.

Bizning tizimimizning asosi bormi?

x 1 - 2 x2 + S1 = 4
x 1 - x2 - S2 = 1
x 1 + x2 + S3 = 8

Hech qanday asos yo'q, ya'ni. biz yechimni boshlay olmaymiz.
Uni topish kerak. Buning uchun biz yordamchi masalani hal qilamiz.
Baza oʻzgaruvchisi boʻlmagan tenglamaga sunʼiy oʻzgaruvchi qoʻshamiz.

x 1 - 2 x2 + S1 = 4
x 1 - x2 - S2 + R1 = 1
x 1 + x2 + S3 = 8

R 1 ≥ 0. Kiritilgan o'zgaruvchi R 1 sun'iy o'zgaruvchi deyiladi.

Biz W funksiyasini hisobga olamiz va uning eng kichik qiymatini qidiramiz.

W funksiyaning eng kichik qiymatini topish algoritmi yuqorida muhokama qilingan algoritmdan faqat bitta farqga ega.
Siz buni o'zingiz hal qilishingiz kerak bo'ladi.


x 1x2S1S2S3R1St. a'zosi Θ
1 -2 1 0 0 0 4 4: 1 = 4
1 -1 0 -1 0 1 1 1: 1 = 1
1 1 0 0 1 0 8 8: 1 = 8
-1 1 0 1 0 0 Vt - 1
0 -1 1 1 0 -1 3
1 -1 0 -1 0 1 1
0 2 0 1 1 -1 7
0 0 0 0 0 1 Vt - 0

Erkin o'zgaruvchilarni nolga tenglashtiramiz. Asosiy o'zgaruvchilarning qiymatlarini og'zaki toping. (jadvalga qarang)
W funktsiyasi erkin o'zgaruvchilar bilan ifodalanadi. Demak, berilgan yechim uchun W funksiyaning qiymatini bir zumda topish mumkin. (jadvalning belgilangan qatoriga qarang)

x 2 = 0 S 2 = 0 R 1 = 0
x 1 = 1 S 1 = 3 S 3 = 7		 => W - 0 = 0 => W = 0

Tanlangan chiziqning koeffitsientlari orasida salbiy ko'rsatkichlar yo'q. Shuning uchun W funksiyaning eng kichik qiymati topiladi.
Sun'iy o'zgaruvchidan foydalanmasdan asos olinadi. Qaysi narsa talab qilingan edi.
Sun'iy o'zgaruvchiga mos keladigan ustunni kesib tashlash mumkin.
Natijada, bizning tizimimiz quyidagicha ko'rinadi:

- x2 + S1 + S2 = 3
x 1 - x2 - S2 = 1
2 x2 + S2 + S3 = 7
F = - x 1 + 3 x2
F = -
( 1 + x2 + S2)
+ 3 x2
= -1 + 2 x2 - S2