Etapp 0. Ettevalmistav etapp.
LP probleemi taandame erivormile (15).
Samm 1. Koostamine simpleks laud mis vastab erivormile:
|
|
|
|||||
|
|
|
|
|
|||
|
|
|
|
|
|
||
|
|
|
|
|
|
||
|
|
|
|
|
|
||
Pange tähele, et see tabel vastab lubatud põhilahendusele 
probleem (15). Selle lahenduse sihtfunktsiooni väärtus 
2. samm Optimaalsuse kontrollimine
Kui indeksirea elementide hulgas on simpleks tabel 
positiivset elementi pole 
, leitakse LP ülesande optimaalne lahendus:. Algoritm lõpeb.
3. samm Kontrollige lahendamatust
Kui hulgas 
on positiivne element 
ja vastavas veerus 
positiivset elementi pole 
, siis sihtfunktsioon L on lubataval komplektil altpoolt piiramata. Sel juhul pole optimaalset lahendust. Algoritm lõpeb.
4. samm Juhtveeru valimine q
Elementide hulgas 
vali maksimaalne positiivne element 
.See veerg on kuulutatud juhtivaks (lubavaks).
5. samm Juhtliini valik lk
Kolonni positiivsete elementide hulgas 
leida element 
, mille jaoks võrdsus
.
string lk kuulutada juhtivaks (lubavaks). Element 
peremeest kuulutama (lubada).
6. samm Lihtne tabeli teisendus
Koostame uue simplekstabeli, milles:
a) baasmuutuja asemel 
Kirjuta üles 
, mittepõhimuutuja asemel 
Kirjuta üles 
;
b) juhtiv element asendatakse pöördväärtusega 
;
c) kõik juhtiva veeru elemendid (v.a 
) korrutada 
;
d) kõik juhtrea elemendid (v.a 
) korrutada 
;
e) ülejäänud simplekstabeli elemendid teisendatakse järgmise "ristküliku" skeemi järgi.
Elemendist lahutatakse kolme teguri korrutis:
esimene on juhtiva veeru vastav element;
teine on juhtrea vastav element;
kolmas on juhtiva elemendi pöördväärtus 
.
Teisendatav element ja sellele vastavad kolm tegurit on just nimelt "ristküliku" tipud.
7. sammÜleminek järgmisele iteratsioonile viiakse läbi sammuga 2 naastes.
2.3. Simpleksmeetodi algoritm maksimaalse probleemi lahendamiseks
Maksimumülesande simpleksmeetodi algoritm erineb miinimumülesande algoritmist ainult sihtfunktsiooni koefitsientide indeksirea märkide poolest. 
, nimelt:
2. sammus:
:
3. sammus
. Sihtfunktsioon on lubataval hulgal ülalt piiramata.
4. sammus:
.
2.4. Näide ülesande lahendamisest simpleksmeetodil
Lahenda vormile (15) kirjutatud ülesanne.
Loome simplekstabeli:
|
|
|
|
|
|
| |||
|
|
|
Kuna sihtfunktsiooni rea koefitsiendid on mittenegatiivsed, ei ole esialgne põhilahend optimaalne. Selle aluse sihtfunktsiooni väärtus L = 0.
Valige juhtiv veerg – see on muutujale vastav veerg 
.
Valige juhtjoon. Selle jaoks leiame 
. Seetõttu vastab juhtiv rida muutujale 
.
Teostame simplekstabeli teisenduse muutuja sisseviimisega 
alusele ja muutuja väljastamiseks 
aluselt. Teeme tabeli:
|
|
|
|
|
|
|
| ||
|
|
|
Üks meetodi iteratsioon on lõpetatud. Liigume edasi uue iteratsiooni juurde. Saadud tabel on ebaoptimaalne. Tabelile vastav põhilahendus on kujul . Sihtfunktsiooni väärtus selle põhjal L = -2.
Juhtveerg on siin muutujale vastav veerg 
. Juhtjoon – muutujale vastav rida 
. Pärast teisenduste tegemist saame simplekstabeli:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Teine iteratsioon on lõpetatud. Liigume edasi uue iteratsiooni juurde.
Sihtfunktsiooni rida ei sisalda positiivseid väärtusi, mis tähendab, et vastav põhilahendus on optimaalne ja algoritm lõpeb.
Kahekordne simpleksmeetod põhineb duaalsuse teoorial (vt duaalülesande lahendust) ja seda kasutatakse lineaarse programmeerimise ülesannete lahendamiseks, mille vabaliikmed b i võivad võtta mis tahes väärtused ja piirangute süsteem on antud tähenduse ebavõrdsustega " ≤", "≥" või võrdus "=".Teenindusülesanne. Veebikalkulaator, mida kasutatakse lineaarse programmeerimise probleemide lahendamiseks P-meetod järgmistes tähistusvormides: simpleksmeetodi tähistuse põhivorm, simplekstabeli kujul, modifitseeritud simpleksmeetodil.
Juhised probleemide lahendamiseks dual simplex meetod. Valige muutujate arv ja ridade arv (piirangute arv), klõpsake nuppu Edasi. Saadud lahendus salvestatakse Wordi faili (vt lahenduse näidet dual simplex meetodil).
Sel juhul piirangud tüüpi x i ≥ 0 ei võta arvesse.Selle kalkulaatoriga kasutatakse ka järgmist:
Graafiline meetod LLP lahendamiseks
Transpordiprobleemi lahendus
Maatriksmängu lahendus
Internetis teenust kasutades saate määrata maatriksmängu hinna (alumine ja ülemine piir), kontrollida sadulapunkti, leida lahenduse segastrateegiale järgmiste meetoditega: minimax, simpleksmeetod, graafiline (geomeetriline) meetod, Browni meetod.
Kahe muutuja funktsiooni ekstreemum
Dünaamilise programmeerimise probleemid
Jaotage 5 homogeenset kaubapartii kolme turu vahel nii, et saate nende müügist maksimaalset tulu. Müügitulu igal turul G(X) sõltub müüdud kaubapartiide arvust X ja on esitatud tabelis.
| Toote maht X (partiidena) | Tulu 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 |
P-meetodil saadakse optimaalne plaan mööda pseudoplaane liikumise tulemusena. Pseudoplaan- plaan, milles optimaalsuse tingimused on täidetud ja põhimuutujate x i väärtuste hulgas on negatiivsed arvud. Dual Simplex meetodi algoritm sisaldab järgmisi samme:
- Pseudoplaani koostamine. Algülesande piirangute süsteem taandatakse ebavõrdsuste süsteemiks tähendusega "≤".
- Plaani optimaalsuse kontrollimine. Kui saadud baasplaanis optimaalsuse tingimus ei ole täidetud, siis lahendatakse probleem simpleksmeetodil.
- Juhtridade ja veergude valimine. Põhimuutujate negatiivsete väärtuste hulgast valitakse absoluutväärtuses suurimad. Sellele väärtusele vastav rida on ees.
- Uue baasjoone arvutamine. Uus plaan saadakse simplekstabeli ümberarvutamisega Jordani-Gaussi meetodil. Seejärel jätkake 2. etapiga.
Näide. Ettevõte peab väljastama vastavalt tootmisplaanile A1 ühikut, A2 ühikut, A3 ühikut. Igat tüüpi toodet saab toota kahel masinal.
Kuidas jaotada masinate tööd nii, et plaani täitmisele kuluv koguaeg oleks minimaalne? Antakse iga masina kulumaatriks ja ajaressurss. Kirjutage uuritava operatsiooni mudel P-meetodi kasutamist võimaldaval kujul.
Teadaolevalt peaks n toitaine A, B ja C sisaldus toidus olema vastavalt vähemalt m1, m2, m3 ühikut. Neid toitaineid leidub kolme tüüpi toiduainetes. Toitaineühikute sisaldus iga tooteliigi ühes kilogrammis on näidatud tabelis. määrata kindlaks igapäevane dieet, mis tagab minimaalse rahalise kuluga vajaliku koguse toitaineid.
Ülesanne: lahendage ülesanne dual simplex meetodi algoritmi abil.
Toome piirangute süsteemi tähendusvõrratuste süsteemi ≤, korrutades vastavad read arvuga (-1).
Määratleme sihtfunktsiooni F(X) = 4x 1 + 2x 2 + x 3 minimaalse väärtuse järgmistel piirangutingimustel.
- x 1 - x 2 ≤-10
2x 1 + x 2 - x 3 ≤8
Esimese võrdlusplaani koostamiseks taandame võrratuste süsteemi võrrandisüsteemiks lisamuutujate sisseviimisega (üleminek kanoonilisele vormile).
Esimeses tähenduse võrratuses (≤) võtame kasutusele põhimuutuja x 4 . Teises tähendusevõrdsuses (≤) võtame kasutusele põhimuutuja x 5 .
-1x1 -1x2 + 0x3 + 1x4 + 0x5 = -10
2x1 + 1x2 -1x3 + 0x4 + 1x5 = 8
Selle võrrandisüsteemi koefitsientide maatriks A = a(ij) on kujul:
| A= |
|
x 4, x 5,
Eeldades, et vabad muutujad on võrdsed nulliga, saame esimese võrdlusplaani:
X1 = (0,0,0, -10,8)
| Alus | B | x 1 | x2 | x 3 | x4 | x5 |
| x4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
Iteratsioon nr 1
Plaan 0 simplekstabelis on pseudoplaan, seega määratleme juhtiva rea ja veeru.
Juhtrida on esimene rida ja muutuja x 4 tuleks alusest välja võtta.
3. Uue põhimuutuja definitsioon. θ miinimumväärtus vastab 2. veerule, st. muutuja x 2 tuleb sisestada baasi.
| Alus | B | x 1 | x2 | x 3 | x4 | x5 |
| x4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
| θ | 0 | -4: (-1) = 4 | -2: (-1) = 2 | - | - | - |
4. Simplekstabeli ümberarvutamine. Teostame simplekstabelite teisendusi Jordan-Gaussi meetodil.
| Alus | B | x 1 | x2 | x 3 | x4 | x5 |
| x2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
Esitame iga elemendi arvutuse tabeli kujul:
| B | x 1 | x2 | x 3 | x4 | x5 |
| -10: -1 | -1: -1 | -1: -1 | 0: -1 | 1: -1 | 0: -1 |
| 8-(-10 1):-1 | 2-(-1 1):-1 | 1-(-1 1):-1 | -1-(0 1):-1 | 0-(1 1):-1 | 1-(0 1):-1 |
| 0-(-10 -2):-1 | -4-(-1 -2):-1 | -2-(-1 -2):-1 | -1-(0 -2):-1 | 0-(1 -2):-1 | 0-(0 -2):-1 |
Iteratsioon nr 2
1. Optimaalsuse kriteeriumi kontrollimine.
Plaan 1 simplekstabelis on pseudoplaan, seega määratleme juhtiva rea ja veeru.
2. Uue vaba muutuja definitsioon.
Põhimuutujate negatiivsete väärtuste hulgast valime suurima mooduli.
Teine rida on eesotsas ja muutuja x 5 tuleks baasist välja võtta.
3. Uue põhimuutuja definitsioon. θ miinimumväärtus vastab kolmandale veerule, st. muutuja x 3 tuleb sisestada baasi.
Juhtrea ja veeru ristumiskohas on lahutuselement (RE), mis on võrdne (-1).
| Alus | B | x 1 | x2 | x 3 | x4 | x5 |
| x2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
| θ | 0 | - | - | -1: (-1) = 1 | - | - |
4. Simplekstabeli ümberarvutamine. Teostame transformatsioone.
| Alus | B | x 1 | x2 | x 3 | x4 | x5 |
| x2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
| B | x 1 | x2 | x 3 | x4 | x5 |
| 10-(-2 0):-1 | 1-(1 0):-1 | 1-(0 0):-1 | 0-(-1 0):-1 | -1-(1 0):-1 | 0-(1 0):-1 |
| -2: -1 | 1: -1 | 0: -1 | -1: -1 | 1: -1 | 1: -1 |
| 20-(-2 -1):-1 | -2-(1 -1):-1 | 0-(0 -1):-1 | -1-(-1 -1):-1 | -2-(1 -1):-1 | 0-(1 -1):-1 |
Kõik põhiveeru elemendid on positiivsed. Liigume edasi simpleksmeetodi põhialgoritmi juurde.
Iteratsioon nr 3
1. Optimaalsuse kriteeriumi kontrollimine.
Ükski indeksirea väärtustest ei ole positiivne. Seetõttu määrab see tabel optimaalse tööplaani.
| Alus | B | x 1 | x2 | x 3 | x4 | x5 |
| x2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
Optimaalse plaani saab kirjutada järgmiselt: x 1 \u003d 0, x 2 \u003d 10, x 3 \u003d 2
F(X) = 2 10 + 1 2 = 22
Üks optimeerimisülesannete lahendamise meetoditest ( tavaliselt seostatakse miinimumi või maksimumi leidmisega Lineaarse programmeerimise ) nimetatakse . Lihtne meetod sisaldab tervet rühma algoritme ja meetodeid lineaarse programmeerimise probleemide lahendamiseks. Üks neist meetoditest, mis hõlmab algandmete salvestamist ja nende ümberarvutamist spetsiaalses tabelis, nimetatakse tabeliline simpleksmeetod.
Vaatleme tabeli simpleksmeetodi algoritmi lahenduse näitel tootmisülesanne, mis taandub maksimaalset kasumit pakkuva tootmisplaani leidmisele.
Probleemi algandmed simpleksmeetodi jaoks
Ettevõte toodab 4 tüüpi tooteid, töödeldes neid 3 masinal.
Ajapiirangud (min/tk) toodete töötlemiseks masinates on antud maatriksiga A:
Masina tööaja fond (min) on toodud maatriksis B:
Iga tooteühiku müügist saadav kasum (rubla/tk) antakse maatriksiga C:
Tootmisülesande eesmärk
Koostage tootmisplaan, milles maksimeeritakse ettevõtte kasum.
Ülesande lahendamine tabeli simpleksmeetodil
(1) Olgu X1, X2, X3, X4 iga tüübi kavandatud toodete arv. Siis soovitud plaan: ( X1, X2, X3, X4)
(2) Kirjutame plaani piirangud võrrandisüsteemi kujul:
(3) Siis on sihtkasum:
See tähendab, et tootmisplaani rakendamisest saadav kasum peaks olema maksimaalne.
(4) Saadud tingimusliku ekstreemumi probleemi lahendamiseks asendame võrratuste süsteemi lineaarsete võrrandite süsteemiga, lisades sellesse täiendavaid mittenegatiivseid muutujaid ( X5, X6, X7).
(5) Aktsepteerime järgmist võrdlusplaan:
X1=0, X2=0, X3=0, X4=0, X5=252, X6=144, X7=80
(6) Sisestame andmed sisse simpleks laud:
Viimasele reale sisestame vastasmärgiga sihtfunktsiooni koefitsiendid ja selle väärtuse enda;
(7) Valige viimasel real suurim (modulo) negatiivne arv.
Arvuta b = N / valitud_veeru_elemendid
Valime b arvutatud väärtuste hulgast vähemalt.
Valitud veeru ja rea ristumiskoht annab meile lahendava elemendi. Muudame aluse lubavale elemendile vastavaks muutujaks ( X5 kuni X1).
- Lubamise element ise muutub 1-ks.
- Lubava rea elementide puhul - a ij (*) = a ij / RE ( see tähendab, et jagame iga elemendi lubava elemendi väärtusega ja saame uued andmed).
- Lahutava veeru elementide puhul lähtestatakse need lihtsalt nulli.
- Ülejäänud tabeli elemendid arvutatakse ümber ristkülikureegli järgi.
a ij (*) = a ij - (A * B / RE)
Nagu näete, võtame praeguse ümberarvutatava lahtri ja lubamiselemendiga lahtri. Need moodustavad ristküliku vastasnurgad. Järgmisena korrutame väärtused selle ristküliku kahe teise nurga lahtritest. See töö ( A * B) jaga lahutuselemendiga ( RE). Ja lahutage praegusest ümberarvutatud lahtrist ( aij) mis juhtus. Saame uue väärtuse - a ij (*).
(9) Kontrollige uuesti viimast rida ( c) peal negatiivsete arvude olemasolu. Kui neid pole, on optimaalne plaan leitud, liigume probleemi lahendamise viimasesse etappi. Kui on, pole plaan veel optimaalne ja simplekstabel tuleb uuesti ümber arvutada.
Kuna viimasel real on jälle negatiivsed arvud, alustame arvutuste uut iteratsiooni.
(10) Kuna viimasel real puuduvad negatiivsed elemendid, siis see tähendab, et oleme leidnud optimaalse tootmisplaani! Nimelt: toodame neid tooteid, mis on kolinud veergu "Bas" - X1 ja X2. Teame iga toodanguühiku tootmisest saadavat kasumit ( maatriks C). Jääb üle korrutada toodete 1 ja 2 leitud toodangumahud kasumiga 1 tüki kohta, saame lõpliku ( maksimum! ) kasum antud tootmisplaani alusel.
VASTUS:
X1 = 32 tk, X2 = 20 tk, X3 = 0 tk, X4 = 0 tk
P \u003d 48 * 32 + 33 * 20 \u003d 2196 rubla.
Galyautdinov R.R.
© Materjali kopeerimine on lubatud ainult juhul, kui määrate otse hüperlingi
. Simpleksmeetodi algoritm
Näide 5.1. Lahendage simpleksmeetodi abil järgmine lineaarse programmeerimise probleem:
Lahendus:
I iteratsioon:
x3, x4, x5, x6 x1,x2. Põhimuutujaid väljendame vabade kaudu:
Toome sihtfunktsiooni järgmisele kujule:
Saadud ülesande põhjal moodustame esialgse simplekstabeli:
Tabel 5.3
Esialgne simplekstabel
Hinnangulised suhted |
||||
Põhilahenduse definitsiooni kohaselt on vabad muutujad võrdsed nulliga ja põhimuutujate väärtused on võrdsed vabade arvude vastavate väärtustega, st:
3. etapp: elukestva õppe programmi piirangute süsteemi ühilduvuse kontrollimine.
Sellel iteratsioonil (tabelis 5.3) ei ilmnenud piirangusüsteemi (tunnus 1) vastuolu märki (st ei ole negatiivse vaba arvuga rida (v.a sihtfunktsiooni rida), mis ei sisaldaks vähemalt üks negatiivne element (st. vaba muutuja negatiivne koefitsient)).
Sellel iteratsioonil (tabelis 5.3) sihtfunktsiooni piiramatuse märki (märk 2) ei selgunud (st sihtfunktsiooni real ei ole negatiivse elemendiga veergu (v.a vabade arvude veerg) milles oleks vähemalt üks positiivne element) .
Kuna leitud põhilahendus ei sisalda negatiivseid komponente, on see lubatav.
6. etapp: optimaalsuse kontroll.
Leitud põhilahendus ei ole optimaalne, kuna optimaalsuse kriteeriumi (märk 4) järgi ei tohiks sihtfunktsiooni real olla negatiivseid elemente (selle märgi arvestamisel selle rea vaba arvu ei arvestata ). Seetõttu liigume vastavalt simpleksmeetodi algoritmile 8. etappi.
Kuna leitud põhilahend on lubatav, siis otsime lahendavat veergu järgmise skeemi järgi: määrame sihtfunktsiooni real negatiivsete elementidega veerud (v.a vabade arvude veerg). Tabeli 5.3 kohaselt on kaks sellist veergu: veerg " x1" ja veerg " x2". Sellistest veergudest valitakse see, mis sisaldab sihtfunktsiooni real väikseimat elementi. Ta hakkab lahendama. Veerg " x2" sisaldab väikseimat elementi (-3) võrreldes veeruga " x1
Lubatava stringi määramiseks leiame vabade arvude positiivsed hinnangulised suhted lubava veeru elementidega, string, mis vastab väikseimale positiivsele hinnangulisele suhtele, võetakse lubatuks.
Tabel 5.4
Esialgne simplekstabel
Tabelis 5.4 vastab väikseim positiivse hinnangu suhe reale " x5”, seepärast on see lahendatav.
Lubava veeru ja lubamisjoone ristumiskohas asuv element loetakse lubavaks. Meie näites on see element, mis asub joone ristumiskohas x5» ja veerud « x2».
Lahenduselement näitab ühte põhi- ja ühte vaba muutujat, mis tuleb simplekstabelis vahetada, et minna uuele "täiustatud" põhilahendusele. Sel juhul on need muutujad. x5 Ja x2, uues simplekstabelis (tabel 5.5) vahetame need ära.
9.1. Luba elementide teisendamine.
Tabeli 5.4 lubatav element teisendatakse järgmiselt:
Saadud tulemuse sisestame sarnasesse lahtrisse tabelis 5.5.
9.2. Luba stringide teisendamine.
Tabeli 5.4 lubatava rea elemendid on jagatud selle simplekstabeli lubatava elemendiga, tulemused mahuvad uue simplekstabeli (tabel 5.5) sarnastesse lahtritesse. Lubava stringi elementide teisendused on toodud tabelis 5.5.
9.3. Lubav veeru teisendus.
Tabeli 5.4 lahutusveeru elemendid jagatakse selle simplekstabeli lahutuselemendiga ja tulemus võetakse vastupidise märgiga. Saadud tulemused sobivad uue simplekstabeli sarnastesse lahtritesse (tabelid 5.5). Lahutusveeru elementide teisendused on toodud tabelis 5.5.
9.4. Simplekstabeli ülejäänud elementide teisendus.
Lihtküliku tabeli muude elementide (st elemendid, mis ei asu lahutusreas ja lahutusveerus) teisendamine toimub vastavalt "ristküliku" reeglile.
Näiteks kaaluge stringi ristumiskohas asuva elemendi teisendamist " x3" ja veerud "", tähistage seda tingimuslikult kui " x3". Tabelis 5.4 joonistame mõtteliselt ristküliku, mille üks tipp asub lahtris, mille väärtust teisendatakse (st lahtris " x3”) ja teine (diagonaaltipp) on lahutuselemendiga lahtris. Ülejäänud kaks tippu (teise diagonaali) on üheselt määratud. Seejärel lahtri teisendatud väärtus " x3"on võrdne selle lahtri eelmise väärtusega miinus murdosa, mille nimetajas on lahutuselement (tabelist 5.4) ja lugejas kahe teise kasutamata tipu korrutis, st:
« x3»: .
Teiste lahtrite väärtused teisendatakse sarnaselt:
« x 3 x 1»: ;
« x4»: 
;
« x4x1»: ;
« x6»: 
;
« x 6 x 1»: ;
«»: 
;
« x1»: 
.
Nende teisenduste tulemusena saadi uus simplekstabel (tabel 5.5).
II iteratsioon:
1. etapp: simplekstabeli koostamine.
Tabel 5.5
Simplex tabelII iteratsioonid
Hinnanguline suhe |
||||
| ||||
|
|
2. etapp: põhilahuse määramine.
Simpleksteisenduste tulemusena saadi uus aluseline lahendus (tabel 5.5):
Nagu näha, on selle põhilahenduse puhul sihtfunktsiooni väärtus =15, mis on rohkem kui eelmise põhilahenduse puhul.
Tabeli 5.5 märgi 1 kohase piirangute süsteemi vastuolu ei ole tuvastatud.
4. etapp: sihtfunktsiooni piirituse kontrollimine.
Tabeli 5.5 märgi 2 kohase sihtfunktsiooni piiramatust ei ilmnenud.
5. etapp: leitud põhilahenduse vastuvõetavuse kontrollimine.
Tunnusele 4 vastav leitud põhilahend ei ole optimaalne, kuna simplekstabeli sihtfunktsiooni rida (tabel 5.5) sisaldab negatiivset elementi: -2 (selle rea vaba arvu selle arvestamisel arvesse ei võeta tunnusjoon). Liigume edasi 8. sammu juurde.
8. etapp: lubava elemendi määratlus.
8.1. Eraldusvõime veeru määratlus.
Leitud põhilahendus on lubatav, negatiivsete elementidega veerud määrame sihtfunktsiooni real (v.a vabade arvude veerg). Tabeli 5.5 kohaselt on ainult üks selline veerg: " x1". Seetõttu aktsepteerime seda lubatud kujul.
8.2. Lubava stringi definitsioon.
Vastavalt tabelis 5.6 saadud positiivsete hinnanguliste suhtarvude väärtustele on miinimum suhe, mis vastab reale " x3". Seetõttu aktsepteerime seda lubatud kujul.
Tabel 5.6
Simplex tabelII iteratsioonid
Hinnanguline suhe |
||||
3/1=3 – min |
||||
9. etapp: simplekstabeli teisendus.
Simplekstabeli (tabel 5.6) teisendused sooritatakse samamoodi nagu eelmises iteratsioonis. Simplekstabeli elementide teisenduste tulemused on toodud tabelis 5.7.
III iteratsioon
Eelmise iteratsiooni simpleksteisenduste tulemuste põhjal koostame uue simplekstabeli:
Tabel 5.7
Simplex tabelIII iteratsioonid
Hinnanguline suhe |
||||
| ||||
|
|
2. etapp: põhilahuse määramine.
Simpleksteisenduste tulemusena saadi uus põhilahend (tabel 5.7):
3. etapp: piirangute süsteemi ühilduvuse kontrollimine.
Tabeli 5.7 märgi 1 kohase piirangute süsteemi vastuolu ei ole tuvastatud.
4. etapp: sihtfunktsiooni piirituse kontrollimine.
Tabeli 5.7 märgi 2 kohase sihtfunktsiooni piiramatust ei ilmnenud.
5. etapp: leitud põhilahenduse vastuvõetavuse kontrollimine.
Leitud põhilahendus vastavalt kriteeriumile 3 on vastuvõetav, kuna see ei sisalda negatiivseid komponente.
6. etapp: leitud põhilahenduse optimaalsuse kontrollimine.
Tunnusele 4 vastav leitud põhilahend ei ole optimaalne, kuna simplekstabeli sihtfunktsiooni rida (tabel 5.7) sisaldab negatiivset elementi: -3 (selle rea vaba arvu selle arvestamisel arvesse ei võeta tunnusjoon). Liigume edasi 8. sammu juurde.
8. etapp: lubava elemendi määratlus.
8.1. Eraldusvõime veeru määratlus.
Leitud põhilahendus on lubatav, negatiivsete elementidega veerud määrame sihtfunktsiooni real (v.a vabade arvude veerg). Tabeli 5.7 kohaselt on ainult üks selline veerg: " x5". Seetõttu aktsepteerime seda lubatud kujul.
8.2. Lubava stringi definitsioon.
Vastavalt tabelis 5.8 saadud positiivsete hinnanguliste suhtarvude väärtustele on miinimum suhe, mis vastab reale " x4". Seetõttu aktsepteerime seda lubatud kujul.
Tabel 5.8
Simplex tabelIII iteratsioonid
Hinnanguline suhe |
||||
5/5=1 – min |
||||
9. etapp: simplekstabeli teisendus.
Simplekstabeli (tabel 5.8) teisendused sooritatakse samamoodi nagu eelmises iteratsioonis. Simplekstabeli elementide teisenduste tulemused on toodud tabelis 5.9.
IV iteratsioon
1. etapp: uue simplekslaua ehitamine.
Eelmise iteratsiooni simpleksteisenduste tulemuste põhjal koostame uue simplekstabeli:
Tabel 5.9
Simplex tabelIV iteratsioonid
Hinnanguline suhe |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
2. etapp: põhilahuse määramine.
Simpleksteisenduste tulemusena saadi uus põhilahend, mille lahendus on tabeli 5.9 järgi järgmine:
3. etapp: piirangute süsteemi ühilduvuse kontrollimine.
Tabeli 5.9 tunnuse 1 kohase piirangute süsteemi vastuolu ei ilmnenud.
4. etapp: sihtfunktsiooni piirituse kontrollimine.
Tabeli 5.9 märgiga 2 kohase sihtfunktsiooni piiramatust ei ilmnenud.
5. etapp: leitud põhilahenduse vastuvõetavuse kontrollimine.
Leitud põhilahendus vastavalt kriteeriumile 3 on vastuvõetav, kuna see ei sisalda negatiivseid komponente.
6. etapp: leitud põhilahenduse optimaalsuse kontrollimine.
Vastavalt tunnusele 4 leitud põhilahendus on optimaalne, kuna simplekstabeli (tabel 5.9) sihtfunktsiooni real ei ole negatiivseid elemente (selle tunnuse arvestamisel selle rea vaba arvu ei võeta arvesse) .
7. etapp: alternatiivse lahenduse kontrollimine.
Leitud lahendus on ainuke, kuna sihtfunktsiooni real nullelemente pole (tabel 5.9) (selle tunnuse arvestamisel selle rea vaba arvu ei arvestata).
Vastus: vaadeldava ülesande sihtfunktsiooni optimaalne väärtus =24, mis saavutatakse juures.
Näide 5.2. Lahendage ülaltoodud lineaarse programmeerimise probleem, eeldades, et sihtfunktsioon on minimeeritud:
Lahendus:
I iteratsioon:
1. etapp: algse simplekstabeli moodustamine.
Algne lineaarse programmeerimise ülesanne on antud standardkujul. Viime selle kanoonilisele kujule, lisades igasse ebavõrdsuse piirangusse täiendava mittenegatiivse muutuja, s.t.
Saadud võrrandisüsteemis võtame lubatud (põhi)muutujad x3, x4, x5, x6, siis on vabad muutujad x1,x2. Põhimuutujaid väljendame vabade muutujatena.
Kaaluge simpleks meetod lineaarse programmeerimise (LP) ülesannete lahendamiseks. See põhineb üleminekul ühelt võrdlusplaanilt teisele, mille puhul sihtfunktsiooni väärtus suureneb.
Simpleksmeetodi algoritm on järgmine:
- Tõlgime algprobleemi kanooniliseks vormiks lisamuutujate sisseviimisega. Vormi ≤ ebavõrdsuse korral sisestatakse lisamuutujad märgiga (+), kui aga vormiga ≥, siis märgiga (-). Täiendavad muutujad sisestatakse sihtfunktsiooni vastavate märkidega, mille koefitsient on võrdne 0 , sest eesmärkfunktsioon ei tohiks muuta oma majanduslikku tähendust.
- Välja antakse vektoreid Pi muutujate koefitsientidest ja vabade terminite veerust. See toiming määrab ühikvektorite arvu. Reegel on, et ühikvektoreid peaks olema nii palju, kui palju on piirangute süsteemis ebavõrdsust.
- Pärast seda sisestatakse algandmed simplekstabelisse. Ühikvektorid sisestatakse baasi ja neid baasist välja jättes leitakse optimaalne lahendus. Sihtfunktsiooni koefitsiendid kirjutatakse vastupidise märgiga.
- LP-ülesande optimaalsuse kriteerium on see, et lahendus on optimaalne, kui see on sisse lülitatud f– rida kõik koefitsiendid on positiivsed. Loa veeru leidmise reegel – vaadatud f on string ja selle negatiivsete elementide hulgast valitakse väikseim. Vektor Pi selle sisaldamine muutub lubavaks. Lahutuselemendi valimise reegel - koostatakse lahutusveeru positiivsete elementide ja vektori elementide suhted P 0 ja arvust, mis annab väikseima suhte, saab lahutuselement, mille suhtes simplekstabel ümber arvutatakse. Seda elementi sisaldavat stringi nimetatakse lubamisstringiks. Kui eraldusvõime veerus pole positiivseid elemente, pole probleemil lahendust. Pärast lahutuselemendi määramist jätkavad nad uue simplekstabeli ümberarvutamist.
- Uue simplekstabeli täitmise reeglid. Lahutuselemendi asemel pannakse üks maha ja eeldatakse, et teised elemendid on võrdsed 0 . Lahutusvektor lisatakse baasile, millest jäetakse välja vastav nullvektor ja ülejäänud baasvektorid kirjutatakse muutmata kujul. Lubamisjoone elemendid jagatakse lubava elemendiga ja ülejäänud elemendid arvutatakse ümber ristkülikute reegli järgi.
- Seda tehakse kuni f– kõik stringi elemendid ei muutu positiivseks.
Mõelge ülesande lahendusele ülaltoodud algoritmi abil.
Arvestades:
Toome probleemi kanoonilisele vormile:
Koostame vektorid:
Täitke simplekstabel:
:
Arvutage vektori esimene element uuesti P 0, mille jaoks teeme arvudest ristküliku: ja saame: 
.
Sarnased arvutused teostame ka kõigi teiste simplekstabeli elementide jaoks:
Saadud plaanis f– string sisaldab ühte negatiivset elementi – (-5/3), vektoreid P1. See sisaldab oma veerus ainsat positiivset elementi, millest saab lahendav element. Arvutame tabeli selle elemendi suhtes ümber:
Negatiivsete elementide puudumine f- string tähendab leitud optimaalne plaan:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).
- Ashmanov S. A. Lineaarne programmeerimine, M: Nauka, 1998,
- Wentzel E.S. Operatsiooniuuringud, M: Nõukogude raadio, 2001,
- Kuznetsov Yu.N., Kuzubov V.I., Voloshenko A.B. Matemaatiline programmeerimine, M: Kõrgkool, 1986
Kohandatud lineaarne programmeerimislahendus
Meie veebisaidil saate tellida mis tahes selle eriala ülesandeid. Faile saate manustada ja tähtaegu määrata aadressil
