Pakalpojuma mērķis. Pakalpojums ir paredzēts lineārās programmēšanas problēmu (LPP) tiešsaistes risināšanai, izmantojot simpleksa metodi šādās apzīmējumu formās:
- simpleksa tabulas veidā (Jordānijas transformācijas metode); pamata ierakstīšanas forma;
- modificēta simpleksa metode; kolonnas formā; līnijas formā.
Instrukcijas. Izvēlieties mainīgo skaitu un rindu skaitu (ierobežojumu skaitu). Iegūtais risinājums tiek saglabāts Word un Excel failā. Šajā gadījumā neņemiet vērā ierobežojumus, piemēram, x i ≥ 0. Ja uzdevumā nav ierobežojumu kādam x i, tad ZLP ir jāpārveido par KZLP vai jāizmanto šis pakalpojums. Risinot, lietojums tiek noteikts automātiski M-metode(vienkāršā metode ar mākslīgu pamatu) un divpakāpju simpleksa metode.
Ar šo kalkulatoru tiek izmantoti arī šādi elementi:
Grafiskā metode ZLP risināšanai
Transporta problēmas risinājums
Matricas spēles atrisināšana
Pakalpojuma izmantošana iekš tiešsaistes režīms var noteikt matricas spēles cenu (apakšējo un augšējo robežu), pārbaudīt seglu punkta esamību, rast risinājumu jauktajai stratēģijai, izmantojot šādas metodes: minimax, simplex metode, grafiskā (ģeometriskā) metode, Brauna metode .
Divu mainīgo funkcijas ekstrēmums
Dinamiskās programmēšanas problēmas
Sadaliet 5 viendabīgas preču partijas starp trim tirgiem, lai no to pārdošanas gūtu maksimālus ienākumus. Ienākumi no pārdošanas katrā tirgū G(X) ir atkarīgi no pārdoto preces X partiju skaita un ir parādīti tabulā.
| Produkta apjoms X (partijās) | Ienākumi G(X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
Vienkāršās metodes algoritms ietver šādas darbības:
- Pirmā pamatplāna sastādīšana. Pāreja uz lineārās programmēšanas problēmas kanonisko formu, ieviešot nenegatīvus papildu bilances mainīgos.
- Plāna optimāluma pārbaude. Ja vismaz viena indeksa līnijas koeficients ir mazāks par nulli, tad plāns nav optimāls un ir jāuzlabo.
- Galvenās kolonnas un rindas noteikšana. No indeksa līnijas negatīvajiem koeficientiem tiek izvēlēts lielākais absolūtajā vērtībā. Tad vienkāršās tabulas brīvo locekļu kolonnas elementi tiek sadalīti vienas un tās pašas vadošās kolonnas zīmes elementos.
- Izveidojiet jaunu atsauces plānu. Pāreja uz jaunu plānu tiek veikta vienkāršās tabulas pārrēķina rezultātā, izmantojot Jordan-Gauss metodi.
Ja nepieciešams atrast mērķa funkcijas ekstrēmu, tad runa ir par minimālās vērtības (F(x) → min, skatiet funkcijas minimizēšanas risinājuma piemēru) un maksimālās vērtības (F(x) atrašanu) → max, skatiet funkcijas maksimizēšanas risinājuma piemēru)
Ekstrēms risinājums tiek sasniegts uz iespējamo risinājumu apgabala robežas vienā no daudzstūra stūra punktu virsotnēm vai segmentā starp diviem blakus esošajiem stūra punktiem.
Lineārās programmēšanas pamatteorēma. Ja ZLP mērķa funkcija sasniedz galējo vērtību kādā brīdī iespējamo risinājumu apgabalā, tad tā ņem šo vērtību stūra punktā. Ja ZLP mērķa funkcija sasniedz galējo vērtību vairāk nekā vienā stūra punktā, tad tā iegūst tādu pašu vērtību jebkurā no šo punktu izliektajām lineārajām kombinācijām.
Simpleksās metodes būtība. Pārvietošanās uz optimālo punktu tiek veikta, pārejot no viena stūra punkta uz blakus esošo, kas tuvina un ātrāk tuvina X opt. Šāda punktu uzskaitīšanas shēma, sauc par simplekso metodi, ieteicis R. Dancigs.
Stūra punktus raksturo m pamata mainīgie, tāpēc pāreju no viena stūra punkta uz blakus esošo var veikt, mainot tikai vienu pamata mainīgo bāzē uz mainīgo no nebāzes.
Simpleksās metodes ieviešanai dažādu LP problēmu pazīmju un formulējumu dēļ ir dažādas modifikācijas.
Simpleksu galdu konstrukcija turpinās līdz tiek iegūts optimālais risinājums.
Kā var izmantot simpleksa tabulu, lai noteiktu, vai lineārās programmēšanas problēmas risinājums ir optimāls?
Ja pēdējā rindā (mērķa funkcijas vērtības) nav negatīvu elementu, tā atradīs optimālo plānu.
1. piezīme. Ja viens no pamata mainīgajiem ir vienāds ar nulli, tad šādam pamatrisinājumam atbilstošais galējais punkts ir deģenerēts. Deģenerācija rodas, ja vadlīnijas izvēlē ir neskaidrības. Jūs, iespējams, nepamanīsit problēmas deģenerāciju, ja kā ceļvedi izvēlaties citu līniju. Neskaidrību gadījumā ir jāizvēlas rinda ar zemāko indeksu, lai izvairītos no cilpas.
2. piezīme. Lai kādā galējā punktā visas simpleksās atšķirības būtu nenegatīvas D k ³ 0 (k = 1..n+m), t.i. tiek iegūts optimāls risinājums un eksistē A k - nebāzes vektors, kuram D k = 0. Tad vismaz divos punktos tiek sasniegts maksimums, t.i. ir alternatīvs optimālais variants. Ja šo mainīgo x k ievadīsim bāzē, mērķa funkcijas vērtība nemainīsies.
3. piezīme. Duālās problēmas risinājums ir atrodams pēdējā simpleksa tabulā. Simplekso atšķirību vektora pēdējie m komponenti (bilances mainīgo kolonnās) ir optimālais duālās problēmas risinājums. Tiešo un duālo problēmu mērķfunkciju vērtības optimālos punktos sakrīt.
4. piezīme. Risinot minimizēšanas uzdevumu, bāzē tiek ievadīts vektors ar lielāko pozitīvo simpleksa starpību. Tālāk tiek izmantots tāds pats algoritms kā maksimizācijas problēmai.
Ja ir norādīts nosacījums “Ir nepieciešams, lai III tipa izejvielas būtu pilnībā patērētas”, tad attiecīgais nosacījums ir vienlīdzība.
Analītisks ievads simpleksā metodē
Simpleksā metode ir universāla lineāra programmēšanas metode.Tātad, ja mēs atrisinām ZLP kanoniskā formā, tad ierobežojumu sistēma ir parasta lineāro vienādojumu sistēma. Risinot LP uzdevumus, tiek iegūtas lineāro vienādojumu sistēmas, kurām, kā likums, ir bezgalīgi daudz risinājumu.
Piemēram, lai sistēma ir dota
Šeit vienādojumu skaits ir 2 un nezināmo skaits ir 3, vienādojumu ir mazāk. Izteiksim x 1 un x 2 ar x 3:
Šis ir sistēmas vispārējais risinājums. ja mainīgajam x 3 dotas patvaļīgas skaitliskās vērtības, tad atradīsim sistēmas daļējus risinājumus. Piemēram, x 3 =1 → x 1 =1 → x 2 = 6. Mums ir (1, 6, 1) — konkrēts risinājums. Ļaujiet x 3 =2 → x 1 =-3, x 2 = 1, (-3, 1, 2) - vēl viens konkrēts risinājums. Šādu konkrētu risinājumu ir bezgala daudz.
Mainīgie lielumi x 1 un x 2 tiek saukti par pamata, un mainīgais x 3 - nav pamata, bezmaksas.
Mainīgo lielumu kopa x 1 un x 2 veido pamatu: B (x 1 , x 2). Ja x 3 = 0, tad iegūto konkrēto risinājumu (5, 11, 0) sauc par pamatrisinājumu, kas atbilst bāzei B (x 1 , x 2).
Pamata risinājums ir tāds, kas atbilst brīvo mainīgo nulles vērtībām.
Citus mainīgos varēja ņemt par bāzes mainīgajiem: ( x 1 , x 3) vai ( x 2 , x 3).
Kā pāriet no viena pamata B(x 1 , x 2) uz citu pamatu B(x 1 , x 3)?
Šim nolūkam ir nepieciešams mainīgais x 3 konvertēt uz pamata un x 2 - uz nepamata, t.i., vienādojumos tas ir nepieciešams x 3 izteikt cauri x 2 un aizstāt ar 1:
B(x 1 , x 3), ir: (-19/5; 0; 11/5).
Ja tagad no pamata B(x 1 , x 3) mēs gribēsim iet uz bāzi B(x 2 , x 3), tad
Pamata risinājums, kas atbilst bāzei B (x 2 , x 3): (0;19/4; 7/8).
No trim atrastajiem bāzes risinājumiem bāzei atbilstošais risinājums B (x 1 , x 3) - negatīvs x 1 < 0, нас в ЗЛП интересуют только неотрицательные решения.
Ja LP problēmai ir risinājums, tad tas tiek sasniegts uz kanoniskās formas ierobežojumu sistēmas pamata nenegatīvo risinājumu kopas.
Tāpēc simpleksās metodes ideja ir secīgi pāriet no viena pamata uz otru, kas ir labāks mērķa funkcijas vērtības ziņā.
Piemērs. Atrisiniet LP problēmu.
Funkcija F= x 2 - x 1 → min ir jāsamazina līdz minimumam saskaņā ar doto ierobežojumu sistēmu:
-2x 1 + x 2 + x 3 = 2
x 1 + x 2 + x 5 = 5
x 1 - 2x 2 + x 4 = 12
x i ≥ 0, i = 1, 5
Šos ierobežojumus var uzskatīt par tādiem, kas izriet no nevienlīdzības un mainīgajiem lielumiem x 3 , x 5 , x 4 - kā papildu.
Pierakstīsim ierobežojumus, izvēloties bāzi no mainīgajiem B{ x 3 , x 4 , x 5 }:
Šī bāze atbilst pamata nenegatīvajam risinājumam
x 1 = 0, x 2 = 0, x 3 = 2, x 4 = 2, x 5 = 5 vai (0, 0, 2, 2, 5).
Tagad mums ir jāizsaka F izmantojot ne-pamata mainīgos, mūsu gadījumā tas jau ir izdarīts: F= x 2 - x 1 .
Pārbaudīsim, vai funkcija ir sasniegusi F tā minimālā vērtība. Šim pamata risinājumam F= 0 - 0 = 0 - funkcijas vērtība ir 0. Bet to var samazināt, ja x 1 palielināsies, jo koeficients funkcijā pie x 1 ir negatīvs. Tomēr, palielinoties x 1 mainīgās vērtības x 4 , x 5 samazinājums (sk. ierobežojumu sistēmas otro un trešo vienādību). Mainīgs x 1 nevar palielināt līdz vairāk nekā 2, pretējā gadījumā x 4 kļūs negatīvs (sakarā ar vienādību 2), un ne vairāk kā 5, pretējā gadījumā x 5 - negatīvs. Tātad no vienādību analīzes izriet, ka mainīgais x 1 var palielināt līdz 2, un funkcijas vērtība samazināsies.
Pāriesim uz jauno bāzi B 2, ieviešot mainīgo x 1 vietā x 4 .
B 2 {x 1 , x 3 , x 5 }.
Izteiksim šos pamata mainīgos kā ne-pamata mainīgos. Lai to izdarītu, mēs vispirms izsakām x 1 no otrā vienādojuma un aizstājiet to ar pārējo, ieskaitot funkciju. 
Pamata risinājums, kas atbilst bāzei B 3 {X 1 , X 2 , X 3), tiek uzrakstīts (4, 1, 9, 0, 0), un funkcija ņem vērtību F= -3. Ņemiet vērā, ka vērtība F samazinājās, t.i., uzlabojās salīdzinājumā ar iepriekšējo bāzi.
Aplūkojot mērķa funkcijas formu 
, ņemiet vērā, ka, lai uzlabotu, t.i., samazinātu vērtību F nav iespējams un tikai tad, kad x 4 = 0, x 5 = 0 vērtība F= -3. tiklīdz x 4 , x 5 kļūs pozitīvs, vērtība F tikai pieaugs, jo koeficienti par x 4 , x 5 ir pozitīvi. Tātad funkcija F sasniedza savu optimālo vērtību F* = -3. Tātad mazākā vērtība F, vienāds ar -3, tiek sasniegts plkst x 1 * = 4, x 2 * = 1, x 3 * = 9, x 4 * = 0, x 5 * = 0.
Šis piemērs ļoti skaidri parāda metodes ideju: pakāpeniski pārejot no bāzes uz bāzi, vienmēr pievēršot uzmanību mērķa funkcijas vērtībām, kuras būtu jāuzlabo, mēs nonākam pie pamata, kurā mērķa vērtība funkciju nevar uzlabot; tā ir optimāla. Ņemiet vērā, ka ir ierobežots bāzu skaits, tāpēc soļu skaits, ko veicam, lai nokļūtu vēlamajā bāzē, ir ierobežots.
≤ = ≥ |
≤ = ≥ |
≤ = ≥ |
×
Brīdinājums
Vai dzēst visas šūnas?
Aizvērt Notīrīt
Datu ievades instrukcijas. Skaitļi tiek ievadīti kā veseli skaitļi (piemēri: 487, 5, -7623 utt.), decimāldaļas (piem., 67., 102,54 utt.) vai daļskaitļi. Daļa jāievada formā a/b, kur a un b (b>0) ir veseli skaitļi vai decimālskaitļi. Piemēri 45/5, 6,6/76,4, -7/6,7 utt.
Vienkāršā metode
ZLP risināšanas piemēri, izmantojot simplekso metodi
1. piemērs. Atrisiniet šādu lineārās programmēšanas problēmu:
 |
Vienādojumu sistēmas ierobežojumu labā puse ir šāda:
Pierakstīsim pašreizējo atsauces plānu:
 |
Šis atsauces plāns nav optimāls, jo pēdējā rindā ir negatīvi elementi. Lielākais negatīvais elements modulī ir (-3), tāpēc vektors ir iekļauts bāzē x 
plkst 
. min(40:6, 28:2)=20/3 atbilst 1. rindai. Vektors parādās no bāzes x 3. Veicam Gausa elimināciju kolonnai x 2, ņemot vērā, ka vadošais elements atbilst 1. rindai. Atiestatīsim visus šīs kolonnas elementus, izņemot vadošo elementu. Lai to izdarītu, pievienojiet 2., 3., 4. rindas rindas ar 1. rindu, attiecīgi reizinot ar -1/3, 1/6, 1/2. Tālāk mēs sadalām līniju ar vadošo elementu ar vadošo elementu.
Šis atskaites plāns nav optimāls, jo pēdējā rindā ir negatīvs elements (-3), tāpēc bāzē ir iekļauts vektors x 1 . Mēs nosakām, kurš vektors iziet no bāzes. Lai to izdarītu, mēs aprēķinām 
plkst 
. min(44/3:11/3, 62/3:5/3)=4 atbilst 2. rindai. Vektors parādās no bāzes x 4 . Veicam Gausa elimināciju kolonnai x 1, ņemot vērā, ka vadošais elements atbilst 2. rindai. Atiestatīsim visus šīs kolonnas elementus, izņemot vadošo elementu. Lai to izdarītu, pievienojiet rindu 1, 3, 4 ar 2. rindu, kas attiecīgi reizināta ar 1/11, -5/11, 9/11. Tālāk mēs sadalām līniju ar vadošo elementu ar vadošo elementu.
Vienkāršajai tabulai būs šāda forma:
Pašreizējais atsauces plāns ir optimāls, jo 4. rindā zem mainīgajiem 
nav negatīvu elementu.
Risinājumu var uzrakstīt šādi: 
.
Mērķa funkcijas vērtība šajā punktā: F(X)=
.
2. piemērs. Atrodiet funkcijas maksimumu
Risinājums.
Bāzes vektori x 4 , x 3 tāpēc visi elementi kolonnās x 4 , x 3 zem horizontālās līnijas jābūt nullei.
Atiestatīt visus kolonnas elementus uz nulli x 4, izņemot vadošo elementu. Lai to izdarītu, pievienojiet 3. rindu ar 1. rindu, kas reizināta ar 4. Atiestatiet visus kolonnas elementus uz nulli. x 3, izņemot vadošo elementu. Lai to izdarītu, pievienojiet 3. rindu ar 2. rindu, kas reizināta ar 1.
Vienkāršajai tabulai būs šāda forma:
Šis atskaites plāns nav optimāls, jo pēdējā rindā ir negatīvs elements (-11), tāpēc bāzē ir iekļauts vektors x 2. Mēs nosakām, kurš vektors iziet no bāzes. Lai to izdarītu, mēs aprēķinām 
plkst 
. Tāpēc mērķa funkcija ir neierobežota no augšas. Tie. Lineārās programmēšanas problēma nav atrisināma.
ZLP risināšanas piemēri, izmantojot mākslīgās bāzes metodi
Piemērs 1. Atrodiet funkcijas maksimumu
Risinājums. Tā kā bāzes vektoru skaitam ir jābūt 3, mēs pievienojam mākslīgo mainīgo, un mērķa funkcijai pievienojam šo mainīgo, kas reizināts ar −M, kur M ir ļoti liels skaitlis:
 |
Vienādojumu sistēmas koeficientu matricai ir šāda forma:
Bāzes vektoriem tāpēc visiem elementiem kolonnās zem horizontālās līnijas jābūt nullei.
Atiestatīsim visus kolonnas elementus, izņemot galveno elementu. Lai to izdarītu, pievienojiet 5. rindu ar 3. rindu, kas reizināta ar -1.
Vienkāršajai tabulai būs šāda forma:
Šis atsauces plāns nav optimāls, jo pēdējā rindā ir negatīvi elementi. Lielākais absolūtais negatīvais elements ir (-5), tāpēc vektors tiek iekļauts bāzē.Nosakām, kurš vektors iziet no bāzes. Lai to izdarītu, mēs aprēķinām 
plkst 
atbilst 3. rindai. No bāzes iznāk vektors Izdarīsim kolonnai Gausa izņēmumu, ņemot vērā, ka vadošais elements atbilst 3. rindai. Atiestatīsim visus šīs kolonnas elementus, izņemot vadošo elementu. Lai to izdarītu, pievienojiet līnijas 5. rindu ar 3. rindu, kas reizināta ar 1. Pēc tam sadaliet līniju ar vadošo elementu ar vadošo elementu.
Vienkāršajai tabulai būs šāda forma:
Šis atsauces plāns nav optimāls, jo pēdējā rindā ir negatīvi elementi. Lielākais absolūtais negatīvais elements ir (-3), tāpēc vektors tiek iekļauts bāzē Nosakām, kurš vektors iziet no bāzes. Lai to izdarītu, mēs aprēķinām 
plkst 
atbilst 1. rindai. Vektors iznāk no bāzes x 2. Veicam Gausa elimināciju kolonnai x 1 , ņemot vērā, ka vadošais elements atbilst 1. rindai. Atiestatīsim visus šīs kolonnas elementus, izņemot vadošo elementu. Lai to izdarītu, pievienojiet 2., 3., 4. rindas rindas ar 1. rindu, attiecīgi reizinot ar 3/2, -1/10, 3/2. Tālāk mēs sadalām līniju ar vadošo elementu ar vadošo elementu.
Vienkāršajai tabulai būs šāda forma:
Šis atsauces plāns nav optimāls, jo pēdējā rindā ir negatīvi elementi. Lielākais negatīvais elements modulī (-13/2), tāpēc bāzē ir iekļauts vektors x 3. Mēs nosakām, kurš vektors iziet no bāzes. Lai to izdarītu, mēs aprēķinām 
plkst 
atbilst rindai 3. Vektors iznāk no bāzes x 5 . Veicam Gausa elimināciju kolonnai x 3, ņemot vērā, ka vadošais elements atbilst 3. rindai. Atiestatīsim visus šīs kolonnas elementus, izņemot vadošo elementu. Lai to izdarītu, pievienojiet 1., 2., 4. rindas rindas ar 3. rindu, attiecīgi reizinot ar 5/3, 25/9, 65/9. Tālāk mēs sadalām līniju ar vadošo elementu ar vadošo elementu.
Vienkāršajai tabulai būs šāda forma:
Pašreizējais atskaites plāns ir optimāls, jo zem mainīgajiem 4-5 rindā nav negatīvu elementu.
Sākotnējās problēmas risinājumu var uzrakstīt šādi:
2. piemērs. Atrodiet optimālo plānu lineārās programmēšanas problēmai:
Vienādojumu sistēmas koeficientu matricai ir šāda forma:
Bāzes vektori x 4 , x 5 , x 6 tāpēc visi elementi kolonnās x 4 , x 5 , x 6, zem horizontālās līnijas jābūt nullei.
Atiestatīt visus kolonnas elementus uz nulli x 4, izņemot vadošo elementu. Lai to izdarītu, pievienojiet 4. rindu ar 1. rindu, kas reizināta ar -1. Atiestatīt visus kolonnas elementus uz nulli x 5, izņemot vadošo elementu. Lai to izdarītu, pievienojiet 5. rindu ar 2. rindu, kas reizināta ar -1. Atiestatīt visus kolonnas elementus uz nulli x 6, izņemot vadošo elementu. Lai to izdarītu, pievienojiet 5. rindu ar 3. rindu, kas reizināta ar -1.
Vienkāršajai tabulai būs šāda forma:
5. rindā mainīgajiem atbilstošie elementi x 1 , x 2 , x 3 , x 4 , x 5 , x 6 nav negatīvs, un skaitlis atrodas noteiktās rindas un kolonnas krustpunktā x 0 ir negatīvs. Tad sākotnējai problēmai nav atsauces plāna. Tāpēc tas ir neizšķirams.
Ir nepieciešams atrisināt lineārās programmēšanas problēmu.
Mērķa funkcija:
2x 1 +5x 2 +3x 3 +8x 4 →min
Ierobežojošie nosacījumi:
3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x 1 +7x 2 +x 3 ≥1
Novedīsim ierobežojumu sistēmu līdz kanoniskajai formai, tāpēc no nevienlīdzībām ir jāpāriet uz vienādībām, pievienojot papildu mainīgos.
Tā kā mūsu problēma ir minimizēšanas problēma, mums tā ir jāpārveido par maksimālās meklēšanas problēmu. Lai to izdarītu, mēs mainām mērķa funkcijas koeficientu zīmes uz pretējām. Pirmās nevienādības elementus rakstām nemainītus, pievienojot papildu mainīgo x 5 un mainot zīmi “≤” uz “=”. Tā kā otrajai un trešajai nevienādībai ir “≥” zīmes, ir jāmaina to koeficientu zīmes uz pretējām un jāievada tajos attiecīgi papildu mainīgie x 6 un x 7. Rezultātā mēs iegūstam līdzvērtīgu problēmu:
3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x1 +13x2 -10x3 -5x4 +x6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1
Mēs turpinām sākotnējās simpleksa tabulas veidošanu. Mērķa funkcijas koeficientus ar pretējo zīmi ieraksta tabulas F rindā.
|
Bezmaksas dalībnieks |
|||||
| F | |||||
| X5 | |||||
| X6 | |||||
| X7 |
Mūsu apkopotajā tabulā brīvo terminu kolonnā ir negatīvi elementi, starp kuriem mēs atrodam maksimālo moduli - šis ir elements: -6, tas nosaka vadošo rindu - X6. Šajā rindā mēs atrodam arī maksimālo negatīvo elementu modulī: -10 tas atrodas kolonnā X3, kas būs vadošā kolonna. Mainīgais, kas atrodas pirmajā rindā, tiek izslēgts no bāzes, un mainīgais, kas atbilst vadošajai kolonnai, ir iekļauts bāzē. Pārrēķināsim simpleksa tabulu:
| X1 | X2 | X6 | X4 | Bezmaksas dalībnieks | |
| 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 |
Mūsu apkopotajā tabulā brīvo terminu kolonnā ir negatīvi elementi, starp kuriem mēs atrodam maksimālo moduli - šis ir elements: -0,4, tas nosaka vadošo rindu - X7. Šajā rindā mēs atrodam arī maksimālo negatīvo elementu modulī: -8.3 tas atrodas kolonnā X2, kas būs vadošā kolonna. Mainīgais, kas atrodas pirmajā rindā, tiek izslēgts no bāzes, un mainīgais, kas atbilst vadošajai kolonnai, ir iekļauts bāzē. Pārrēķināsim simpleksa tabulu:
| X1 | X7 | X6 | X4 | Bezmaksas dalībnieks | |
| 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 |
Tā kā brīvo terminu ailē nav negatīvu elementu, ir atrasts pieļaujamais risinājums F rindā ir negatīvi elementi, kas nozīmē, ka iegūtais risinājums nav optimāls. Definēsim vadošo kolonnu. Lai to izdarītu, rindā F atradīsim negatīvo elementu ar maksimālo moduli - tas ir -1,988. Vadošā rinda būs tā, kurai brīvā vārda attiecība pret vadošās kolonnas atbilstošo elementu ir minimāla. Galvenā rinda ir X2, un vadošais elements ir: 0,313.
| X2 | X7 | X6 | X4 | Bezmaksas dalībnieks | |
| 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 |
Tā kā virknē F nav negatīvu elementu, tad
ir atrasts optimālais risinājums. Tā kā sākotnējais uzdevums bija atrast minimumu, optimālais risinājums būs virknes F brīvais termins, kas ņemts ar pretējo zīmi. F=1,924
ar mainīgām vērtībām, kas vienādas: x 3 = 0,539, x 1 = 0,153. Mainīgie lielumi x 2 un x 4 nav iekļauti bāzē, tāpēc x 2 =0 x 4 =0.
Simpleksā metode ir viena no visvairāk efektīvas metodes LP uzdevumu skaitlisks risinājums. Jēdziena “simplex” būtība ir šāda. Ķermenim k-dimensiju telpā simplekss ir kopa, kas sastāv no šī ķermeņa k + 1 virsotnēm. Tātad, ja k = 2, t.i. plaknē simplekss būs trijstūra virsotnes; ja k = 3, simplekss ir tetraedra virsotnes, piemēram, tetraedrs utt. Šis nosaukums metodei tika dots tādēļ, ka tā ir balstīta uz secīgu ODZP virsotņu meklēšanu, lai noteiktu tās virsotnes koordinātas, kurā mērķa funkcijai ir galējā vērtība.
Tas ir sadalīts divos galvenajos posmos. Pirmajā posmā tiek atrasts viens no risinājumiem, kas apmierina ierobežojumu sistēmu. Sistēmas, kurās ir vairāk mainīgo nekā ierobežojumu N > m, sauc par nenoteiktām. Tie tiek reducēti uz noteiktām sistēmām (N = m), pielīdzinot to nulle N-m jebkuri mainīgie. Tas atstāj m vienādojumu sistēmu ar m nezināmajiem, kam ir risinājums, ja sistēmas determinants atšķiras no nulles. Simpleksā metode ievieš pamata mainīgo jeb bāzes jēdzienu. Bāze ir jebkura m mainīgo kopa, kurā determinants, kas sastāv no šo mainīgo koeficientiem m-ierobežojumos, nav nulle. Atpūta N-m mainīgie tiek saukti par ne-pamata vai brīvajiem mainīgajiem. Ja pieņemam, ka visi nebāzes mainīgie ir vienādi ar nulli un atrisinām ierobežojumu sistēmu attiecībā uz pamata mainīgajiem, iegūstam pamata risinājumu.
M vienādojumu sistēmā ar N nezināmajiem pamata risinājumu kopējo skaitu N > m nosaka kombināciju skaits
Tiek izsaukts pamatrisinājums, kurā visi x i 0, i = 1,m pieļaujams pamata risinājums. Tādējādi risinājuma pirmais posms, izmantojot simpleksa metodi, beidzas ar pieņemama pamatrisinājuma atrašanu, pat ja tas ir neveiksmīgs.
Otrajā posmā atrastais risinājums tiek konsekventi pilnveidots.Šajā gadījumā tiek veikta pāreja no viena iespējama pamatrisinājuma uz citu tā, lai mērķfunkcijas vērtība uzlabotu. Risinājuma process, izmantojot simplekso metodi, turpinās, līdz tiek sasniegta mazākā (vai lielākā) mērķa funkcijas vērtība. Ģeometriski tas nozīmē pārvietošanos pa malām no vienas pieļaujamo vērtību daudzskaldņa virsotnes uz otru virzienā uz to, kurā mērķa funkcijas vērtība sasniedz galējību. Simpleksā metode nodrošina optimālu procedūru pamatrisinājumu uzskaitīšanai un nodrošina konverģenci līdz galējam punktam ierobežotā soļu skaitā. Izmantojot simplekso metodi, aprēķini otrajā posmā tiek veikti saskaņā ar šādu shēmu:
1) pamata mainīgie un mērķa funkcija tiek izteikta ar nepamata mainīgajiem;
2) pēc noteikta noteikuma tiek izvēlēts viens no nepamata mainīgajiem, kura vērtības maiņa var uzlabot F(x) vērtību, un tas tiek ievadīts bāzē;
3) tiek noteikts, kurš no pamata mainīgajiem ir jāatvasina no bāzes, savukārt katrā solī izveidotā jaunā pamatmainīgo kopa atšķiras no iepriekšējās tikai ar vienu mainīgo;
4) pamata mainīgie un mērķa funkcija tiek izteikti ar jauniem ne-pamata mainīgajiem, un operācijas 2) un 3) tiek atkārtotas.
Ja kādā simpleksās metodes solī izrādās, ka, mainot jebkura ne-pamata mainīgā lieluma vērtības, nevar uzlabot F(x), tad pēdējais pamata risinājums izrādās optimāls.
Apskatīsim piemēru, kas saistīts ar organizatoriskās un ekonomiskās vadības uzdevumiem un palīdz izprast simpleksās metodes saturu.
1. piemērs. 20 tūkstoši e.e. tika piešķirti aprīkojuma iegādei jaunai vietai. Iekārtas jānovieto uz vietas, kas nepārsniedz 72 m2. Var pasūtīt divu veidu iekārtas: 1) iekārtas, kas maksā 5 tūkstošus g., aizņem 6 m 2 platību un ražo 8 tūkstošus vienību. produkti vienā maiņā; 2) iekārtas 2 tūkstošu vērtībā y.e., kas aizņem 12 m2 platību un saražo 4 tūkstošus vienību maiņā. produktiem. Atrodiet optimālo variantu aprīkojuma iegādei, kas nodrošina maksimālu kopējo vietnes produktivitāti, izmantojot simpleksa metodi.
Nezināmo pirmā un otrā tipa iekārtu daudzumu apzīmēsim attiecīgi ar x 1 un x 2. Mērķa funkciju var uzrakstīt šādi: F(x) = 8x 1 + 4x 2 (max). Teritorijas ierobežojumi: 6x 1 +12x 2 ≤72; izmaksu ierobežojumi: 5x 1 + 2x 2 ≤20 ; mainīgo zīmju ierobežojumi x 1 ≥0 ; x 2 ≥0.
Sadalīsim pirmā ierobežojuma koeficientus ar 6 un reducēsim ierobežojumus līdz vienādību formai, ieviešot papildu mainīgos x 3 un x 4:
x 1 + 2x 2 + x 3 =12, (1)
5x 1 + 2x 2 + x 4 = 20. (2)
Tādējādi uzdevuma ierobežojumi , tiek reducēti uz divu algebrisko vienādojumu sistēmu ar četriem nezināmajiem. Problēmas risināšanas procedūra ir šāda:
1. solis. Lai atrisinātu, izmantojot simplekso metodi, mēs izvēlamies x 2 un x 4 kā pamata mainīgos (BP), jo determinants, ko veido šo mainīgo koeficienti uzdevuma ierobežojumos, atšķiras no nulles.
Tad x 1 un x 3 būs ne-pamata mainīgie (NP). Izteiksim pamatmainīgos un F(x) ar ne-pamata mainīgajiem.
(3)
No otrā ierobežojuma izriet, ka
x 4 = 20 - 2x 2 - 5x 1. (4)
Ņemot vērā iepriekš minēto izteiksmi, mēs iegūstam
x 4 = 8 - 4x 1 + x 3. (5)
Tad
F(x) = 8x1 + 4x2 = 24 + 6x1 - 2x3. (6)
Katrā solī NP ir vienādi ar nulli, tāpēc BP un F(x) būs vienādi ar brīvajiem terminiem attiecīgajās izteiksmēs:
x 1 = 0, x 3 = 0, x 2 = 6, x 4 = 8, F(x) = 24.
Šis risinājums atbilst ODZP virsotnes A koordinātām attēlā. 1. Risinājuma optimālumu pārbauda, izmantojot mērķa funkcijas izteiksmi F(x). Mainīgais x 3 ievada šo izteiksmi ar negatīvu koeficientu; ja nākamajā darbībā bāzē ievadīsit x 3, tas notiks pozitīva vērtība, un no skaitļa 24 tiks atņemta noteikta vērtība, t.i. F(x) vērtība samazināsies. Ja nākamajā solī bāzē ievadīsiet x 1, tad mērķa funkcijas vērtība palielināsies, t.i. uzlabosies.
Izmantojot simplekso metodi, mainīgais, kas vispirms nonāk līdz nullei, ievadot bāzē x 1, tiek izslēgts no bāzes. Analizējot (3) un (5), mēs nosakām, ka x 4 ir jāizslēdz no bāzes. Nākamajā darbībā mainīgie x 1 un x 4 tiks apmainīti.
Simpleksās metodes 2. solis. x 1 un x 2 ir pamata mainīgie, x 3 un x 4 nav pamata mainīgie. Izteiksim pamatmainīgos un F(x) ar nepamata mainīgajiem. No (5) izriet
x 1 = 2+(1/4) x 3-(1/4) x 4 (7)
Rīsi. 1. 1. piemēra grafiskā interpretācija, izmantojot simpleksa metodi.
Aizstājot (7) ar (3), mēs iegūstam
x 2 =5-(5/8)x3 + (1/8)x4
Tad F(x) = 8x1 + 4x2 = 36 - (1/2)x3-(3/4)x4. Rezultātā x 3 = x 4 = 0 (kā ne pamata), x 1 = 2, x 2 = 5, F = 36. Šis risinājums atbilst virsotnes B koordinātām attēlā. 1. Atrastā vērtība būs optimāla, F(x) vērtību nav iespējams uzlabot, jo mainīgie x 3 un x 4 ir iekļauti mērķa funkcijas izteiksmē ar negatīviem koeficientiem.
Tādējādi, izmantojot simpleksa metodi, mēs noskaidrojām, ka vietnes maksimālā produktivitāte ir 36 tūkstoši vienību. preces uz maiņu tiks nodrošinātas pērkot 2 gab. pirmā tipa iekārtas un 5 vienības. otrā tipa aprīkojums. Papildu mainīgajiem x 3 un x 4 ir neizmantoto resursu nozīme. Šajā piemērā visi resursi platības un izmaksu izteiksmē ir pilnībā izmantoti (x 3 = x 4 = 0).
Viena no optimizācijas problēmu risināšanas metodēm ( parasti saistīts ar minimuma vai maksimuma atrašanu) sauc par lineāro programmēšanu. Vienkāršā metode ietver veselu algoritmu un metožu grupu lineārās programmēšanas uzdevumu risināšanai. Viena no šīm metodēm, kas ietver avota datu ierakstīšanu un pārrēķinu īpašā tabulā, tiek izsaukta tabulas simpleksa metode.
Apskatīsim tabulas simpleksās metodes algoritmu, izmantojot risinājuma piemēru ražošanas uzdevums, kas noved pie tāda ražošanas plāna atrašanas, kas nodrošina maksimālu peļņu.
Ievaddati vienkāršās metodes problēmai
Uzņēmums ražo 4 veidu produktus, apstrādājot tos uz 3 iekārtām.
Laika standartus (min./gab.) produktu apstrādei mašīnās nosaka matrica A:
Iekārtas darbības laika fonds (min.) ir norādīts matricā B:
Peļņa no katras preces vienības pārdošanas (RUB/gab.) tiek aprēķināta ar matricu C:
Ražošanas uzdevuma mērķis
Sastādiet ražošanas plānu, kas maksimāli palielinās uzņēmuma peļņu.
Problēmas risināšana, izmantojot tabulas simplekso metodi
(1) Ar X1, X2, X3, X4 apzīmēsim katra veida plānoto produktu skaitu. Tad vēlamais plāns:( X1, X2, X3, X4)
(2) Pierakstīsim plāna ierobežojumus vienādojumu sistēmas veidā:
(3) Tad mērķa peļņa ir:
Tas ir, peļņai no ražošanas plāna izpildes jābūt maksimālai.
(4) Lai atrisinātu iegūto nosacīto ekstrēmu problēmu, nevienādību sistēmu aizvietojam ar lineāru vienādojumu sistēmu, ieviešot tajā papildu nenegatīvus mainīgos ( X5, X6, X7).
(5) Pieņemsim sekojošo atsauces plāns:
X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80
(6) Ievadīsim datus vienkāršā galds:
Pēdējā rindā ievadām mērķfunkcijas koeficientus un pašu tās vērtību ar pretēju zīmi;
(7) Pēdējā rindā atlasiet lielākais (modulo) negatīvs skaitlis.
Aprēķināsim b = N / Izvēlētās_kolonnas_vienumi
No aprēķinātajām b vērtībām mēs izvēlamies vismazāk.
Atlasītās kolonnas un rindas krustpunkts dos mums atrisināšanas elementu. Mēs mainām bāzi uz mainīgo, kas atbilst izšķiršanas elementam ( X5 līdz X1).
- Pats izšķirošais elements pārvēršas par 1.
- Izšķirtspējas līnijas elementiem – a ij (*) = a ij / RE ( tas ir, mēs sadalām katru elementu ar izšķirošā elementa vērtību un iegūstam jaunus datus).
- Izšķirtspējas kolonnas elementiem tie tiek vienkārši atiestatīti uz nulli.
- Mēs pārrēķinām atlikušos tabulas elementus, izmantojot taisnstūra noteikumu.
a ij (*) = a ij – (A * B / RE)
Kā redzat, mēs ņemam pašreizējo šūnu, kas tiek pārrēķināta, un šūnu ar atrisināšanas elementu. Tie veido taisnstūra pretējos stūrus. Tālāk mēs reizinām vērtības no šī taisnstūra pārējo 2 stūru šūnām. Šis darbs ( A * B) dalīt ar izšķirošo elementu ( RE). Un atņemiet no pašreizējās šūnas, kas tiek pārrēķināta ( a ij) kas notika. Mēs iegūstam jaunu vērtību - a ij (*).
(9) Vēlreiz pārbaudiet pēdējo rindiņu ( c) ieslēgts negatīvu skaitļu klātbūtne. Ja to nav, optimālais plāns ir atrasts, dodieties uz pēdējais posms problēmas atrisināšana. Ja ir, plāns vēl nav optimāls, un vienkāršā tabula ir jāpārrēķina vēlreiz.
Tā kā pēdējā rindā atkal ir negatīvi skaitļi, mēs sākam jaunu aprēķinu iterāciju.
(10) Tā kā pēdējā rindā nav negatīvu elementu, tas nozīmē, ka esam atraduši optimālo ražošanas plānu! Proti: ražosim tos produktus, kas ir pārcēlušies uz aili “Bāze” - X1 un X2. Mēs zinām peļņu no katras produkcijas vienības ražošanas ( matrica C). Atliek reizināt atrastos produkcijas 1 un 2 ražošanas apjomus ar peļņu uz 1 gabalu, mēs iegūstam galīgo ( maksimums! ) peļņa konkrētam ražošanas plānam.
ATBILDE:
X1 = 32 gab., X2 = 20 gab., X3 = 0 gab., X4 = 0 gab.
P = 48 * 32 + 33 * 20 = 2196 rubļi.
Gaļautdinovs R.R.
© Materiāla kopēšana ir pieļaujama tikai tad, ja ir tieša hipersaite uz
