11.4. DUAL SIMPLEX MENETELMÄ
Edellisten osioiden tuloksista seuraa, että alkuperäisen ongelman ratkaisun saamiseksi voidaan siirtyä kaksoisongelmaan ja sen optimaalisen suunnittelun arvioiden perusteella määrittää optimaalinen ratkaisu alkuperäiseen ongelmaan.
Siirtyminen kaksoistehtävään ei ole välttämätöntä, koska jos tarkastellaan ensimmäistä simplex-taulukkoa yksikkölisäperusteella, niin on helppo nähdä, että sarakkeet sisältävät alkuperäisen tehtävän ja kaksoistehtävä kirjoitetaan riveille.
Kuten osoitettiin, kun ratkaistaan suora ongelma missä tahansa iteraatiossa, ero, eli suuruus -kerroin muuttujalla, on yhtä suuri kuin kaksoistehtävän vastaavan rajoitteen oikean ja vasemman puolen välinen erotus. Jos suoritettaessa suoraa ongelmaa maksimoitavalla tavoitefunktiolla iterointi ei johda optimaaliseen ratkaisuun, niin ainakin yhdelle muuttujalle ja vain optimaalisesti kaikille ero.
Kun otetaan huomioon tämä ehto ja kaksinaisuus on otettu huomioon, voimme kirjoittaa
.
Eli jos, sitten. Tämä tarkoittaa, että kun alkuongelman ratkaisu ei ole optimaalinen, kaksoisongelman ratkaisu on virheellinen. Toisaalta 
osoitteessa . Tämä tarkoittaa, että primaaliongelman optimaalinen ratkaisu vastaa kaksoisongelman hyväksyttävää ratkaisua.
Tämä mahdollisti uuden menetelmän kehittämisen lineaaristen ohjelmointiongelmien ratkaisemiseen, jota käytettäessä saadaan aluksi ei-hyväksyttävä, mutta "optimaalista parempi" ratkaisu (tavallisessa simplex-menetelmässä ensin hyväksyttäväksi, mutta alioptimaalinen ratkaisu). Uusi menetelmä ns dual simplex -menetelmä, varmistaa ratkaisun optimaalisuusehdon täyttymisen ja sen systemaattisen "lähestymisen" toteuttamiskelpoisten ratkaisujen alueelle. Kun saatu ratkaisu osoittautuu hyväksyttäväksi, iteratiivinen laskutoimitus päättyy, koska tämä ratkaisu on myös optimaalinen.
Dual simplex -menetelmä mahdollistaa lineaaristen ohjelmointiongelmien ratkaisemisen, joiden rajoitusjärjestelmät sisältävät positiivisella pohjalla minkä tahansa etumerkin vapaita termejä. Tämä menetelmä mahdollistaa rajoitusjärjestelmän muunnosten määrän sekä simpleksitaulukon koon pienentämisen. Harkitse dual simplex -menetelmän soveltamista esimerkin avulla.
Esimerkki. Etsi funktion minimi 
rajoitusten alla
.
Siirrytään kanoniseen muotoon:
rajoitusten alla
Alkuperäisellä simplex-taulukolla on muoto
|
Perus muuttujia |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
Ratkaisu |
|
x 3 x 4 x 5 |
–3 –4 |
–1 –3 |
–3 –6 |
|||
|
–2 |
–1 |
Alkuperäinen perusratkaisuoptimaalinen, mutta ei hyväksyttävä.
Kuten tavallinen simplex-menetelmä, myös käsiteltävä ratkaisumenetelmä perustuu hyväksyttävyys- ja optimaalisuusehtojen käyttöön.
Hyväksyttävä ehto. Poissuljetuksi muuttujaksi valitaan absoluuttisen arvon suurin negatiivinen perusmuuttuja (jos vaihtoehtoja on, valinta tehdään mielivaltaisesti). Jos kaikki perusmuuttujat eivät ole negatiivisia, laskentaprosessi päättyy, koska tuloksena oleva ratkaisu on toteuttamiskelpoinen ja optimaalinen.
Kunto optimaalisuus. Pohjaan sisältyvä muuttuja valitaan ei-perusmuuttujien joukosta seuraavasti. Vasemman puolen kertoimien suhteet lasketaan-yhtälöt poissuljettuun muuttujaan liittyvän yhtälön vastaaviin kertoimiin. Suhteita, joilla on positiivinen tai nolla nimittäjä, ei oteta huomioon. Syötemuuttujan minimointiongelmassa on vastattava pienimmän osoitetuista suhteista ja maksimointitehtävässä suhdetta, jolla on pienin itseisarvo (jos vaihtoehtoja on, valinta tehdään mielivaltaisesti). Jos kaikkien suhteiden nimittäjät ovat nolla tai positiivinen, ongelmalla ei ole toteuttamiskelpoisia ratkaisuja.
Kun on valittu perusteeseen sisällytettävät ja poissuljettavat muuttujat, seuraavan ratkaisun saamiseksi suoritetaan tavallinen simpleksitaulukon rivien muunnostoiminto.
Tässä esimerkissä poissuljettu muuttuja on. Uuden perusmuuttujan määrittämiseksi lasketut suhteet on esitetty seuraavassa taulukossa:
|
Muuttujat |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
Yhtälö x 4 - yhtälö |
–2 –4 |
–1 –3 |
|||
|
Asenne |
Sisällytettävä muuttuja on x 2. Myöhempi merkkijonon muunnos johtaa uuteen simpleksitaulukkoon:
|
Perus muuttujia |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
Ratkaisu |
|
x 3 x 2 x 5 |
–1 –1 |
|||||
Uusi Ratkaisu myös optimaalinen, mutta silti virheellinen. Uudeksi poissuljetuksi muuttujaksi valitsemme (mielivaltaisesti) x 3. Määritellään mukana oleva muuttuja.
|
Muuttujat |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
Yhtälö x 4 - yhtälö |
|||||
|
asenne |
Yksinkertainen menetelmä - Tämä on menetelmä peräkkäiseen siirtymiseen lineaarisen ohjelmointitehtävän rajoitusjärjestelmän yhdestä perusratkaisusta (ratkaisupolyhedrin kärjestä) toiseen perusratkaisuun, kunnes tavoitefunktio saa optimaalisen arvon (maksimi tai minimi).
Simplex-menetelmä on universaali menetelmä, joka voi ratkaista minkä tahansa lineaarisen ohjelmoinnin ongelma, kun taas graafinen menetelmä soveltuu vain kahden muuttujan rajoitusjärjestelmään.
Simplex-menetelmää ehdotti amerikkalainen matemaatikko R. Dantzig vuonna 1947, ja siitä lähtien teollisuuden tarpeisiin tämä menetelmä usein ratkaisee lineaarisen ohjelmoinnin ongelmia, joissa on tuhansia muuttujia ja rajoituksia.
Ennen kuin siirryt simplex-menetelmän algoritmiin, muutama määritelmä.
Mitä tahansa ei-negatiivista ratkaisua rajoitusjärjestelmään kutsutaan hyväksyttävä ratkaisu .
Olkoon järjestelmä m rajoituksia alkaen n muuttujat ( m n).
Hyväksyttävä perusratkaisu on liuos, joka sisältää m ei-negatiivinen suuri (perus ) muuttujat ja n - m ei-ydin . (ei-perus, tai vapaa ) muuttujia. Ei-perusmuuttujat perusratkaisussa ovat yhtä suuria kuin nolla, kun taas päämuuttujat ovat yleensä nollasta poikkeavia, eli ne ovat positiivisia lukuja.
Minkä tahansa m järjestelmän muuttujat m lineaariset yhtälöt kanssa n muuttujia kutsutaan pää , jos niiden kertoimien determinantti on eri kuin nolla. Sitten loput n - m muuttujia kutsutaan ei-ydin (tai vapaa ).
Simplex-menetelmän algoritmi
- Vaihe 1. Tuo lineaarisen ohjelmoinnin ongelma kanoniseen muotoon. Voit tehdä tämän siirtämällä vapaat termit oikealle puolelle (jos näiden vapaiden termien joukossa on negatiivisia, kerro sitten vastaava yhtälö tai epäyhtälö -1:llä) ja lisää jokaiseen rajoitteeseen lisämuuttujia (plus-merkillä, jos alkuperäinen epäyhtälö merkki on pienempi tai yhtä suuri kuin ", ja miinusmerkillä, jos "suurempi tai yhtä suuri").
- Vaihe 2. Jos tuloksena olevassa järjestelmässä m yhtälöt siis m Ota muuttujat päämuuttujiksi, ilmaise päämuuttujat ei-perusmuuttujilla ja etsi vastaava perusratkaisu. Jos löydetty perusratkaisu osoittautuu hyväksyttäväksi, siirry hyväksyttävään perusratkaisuun.
- Vaihe 3. Ilmaise tavoitefunktio toteuttamiskelpoisen perusratkaisun pienemmillä muuttujilla. Jos lineaarisen muodon maksimi (minimi) löytyy ja sen lausekkeessa ei ole ei-perusmuuttujia negatiivisilla (positiivisilla) kertoimilla, niin optimaalisuuskriteeri täyttyy ja tuloksena oleva perusratkaisu on optimaalinen - ratkaisu on ohi. Jos lineaarisen muodon maksimi (minimi) löydettäessä sen lauseke sisältää yhden tai useamman ei-perusmuuttujan negatiivisilla (positiivisilla) kertoimilla, siirry uuteen perusratkaisuun.
- Vaihe 4. Valitse lineaariseen muotoon sisältyvistä ei-perusmuuttujista negatiivisilla (positiivisilla) kertoimilla se, joka vastaa suurinta (modulo) kerrointa, ja siirrä se tärkeimpiin. Siirry vaiheeseen 2.
Tärkeät ehdot
Joitakin erikoistapauksia käsitellään erillisissä artikkeleissa: milloin suurin tavoitefunktio - ääretön, kun järjestelmällä ei ole ratkaisua, ja milloin optimaalinen ratkaisu ei ole ainoa .
Seuraavaksi analysoimme tyypillistä esimerkkiä, kun rajoitusjärjestelmä on johdonmukainen ja on olemassa äärellinen optimi, ja vain yksi. Yksi simpleksimenetelmän muunnelma on jakelumenetelmä kuljetusongelman ratkaisemiseksi .
Simplex-menetelmä simplex-taulukoilla
Lineaarisen ohjelmointitehtävän ratkaiseminen on paljon helpompaa rakentamalla simpleksitaulukoita kuin algebrallisilla muunnoksilla, mikä näkyy seuraavassa kappaleessa. Simplex-taulukot ovat erittäin visuaalisia. Yksipuolisten taulukoiden kanssa työskentelyyn on olemassa useita sääntöjä. Analysoimme sääntöä, jota useimmiten kutsutaan johtavaksi sarakkeeksi ja johtavaksi rivisääntöksi.
Manuaalinen Toiminnot murtolukujen kanssa olisi hyödyllistä avata uuteen ikkunaan: niitä on tarpeeksi, lievästi sanottuna simplex-menetelmän tehtävien murto-osia.
Esimerkki.
Otamme käyttöön muita ei-negatiivisia muuttujia ja vähennämme tämän epäyhtälöjärjestelmän vastaavaksi yhtälöjärjestelmäksi
.
Tämä tehtiin seuraavan säännön mukaisesti: jos alkuperäisen rajoitteen merkki on "pienempi tai yhtä suuri kuin", lisämuuttuja on lisättävä, ja jos "suurempi tai yhtä suuri kuin", lisämuuttuja on oltava vähennetty.
Esitetyt lisämuuttujat ovat pääasiallisia (perusmuuttujia). Sitten ja ovat ei-perusmuuttujia (vapaita) muuttujia.
Ilmaisemalla tärkeimmät (perus)muuttujat ei-perusmuuttujilla (vapailla) saamme
Ilmaistamme tavoitefunktion myös ei-perusmuuttujilla (vapailla) muuttujilla:
Muuttujien (tuntemattomien) kertoimista muodostetaan ensimmäinen simpleksitaulukko.
| pöytä 1 | ||||
| Perus tuntemattomat | Ilmaiset jäsenet | Irrallisia tuntemattomia | Apukertoimet | |
| X1 | X2 | |||
| X3 | -2 | 1 | -2 | |
| X4 | -4 | -1 | -1 | |
| X5 | 2 | 1 | -1 | |
| X6 | 6 | 0 | 1 | |
| F | 0 | -1 | -2 | |
Taulukon viimeistä riviä, joka sisältää tavoitefunktion ja siinä olevien vapaiden muuttujien kertoimet, kutsutaan indeksiriviksi.
Tuloksena oleva ratkaisu ei ole optimaalinen, koska indeksirivin vapaiden muuttujien kertoimet ovat negatiivisia. Toisin sanoen optimaalinen ratkaisu on se, jossa indeksirivin vapaiden muuttujien kertoimet ovat suurempia tai yhtä suuria kuin nolla.
Siirry seuraavaan taulukkoon etsimällä suurin (modulo) numeroista ja . Tämä luku on 2. Siksi johtava sarake on sarake, johon se kirjoitetaan
Eturivin määrittämiseksi löydämme vapaiden jäsenten suhteiden minimin alkusarakkeen elementteihin, ja jos osoittajalla on positiivinen luku ja nimittäjä negatiivinen, suhdetta pidetään äärettömänä.
.
Siksi johtava rivi on se, jolle se kirjoitetaan
Johtava elementti on siis -2.
Laadimme toisen simpleksitaulukon.
Kirjoitamme uuden peruselementin ensimmäiselle riville ja syötämme sarakkeen, jossa se oli, syötämme uuden vapaan muuttujan
Täytä ensimmäinen rivi. Tätä varten jaamme kaikki taulukon 1 eturivin luvut johtavalla elementillä ja kirjoitamme sen taulukon 2 ensimmäisen rivin vastaavaan sarakkeeseen, paitsi alkusarakkeen numero, jossa käänteisluku elementti kirjoitetaan (eli yksi jaettuna johtavalla elementillä).
Täytä apukertoimien sarake. Tälle taulukon 1 johtavan sarakkeen numerolle kirjoitetaan alkuelementin lisäksi vastakkaiset merkit taulukon 2 apukertoimien sarakkeeseen.
| taulukko 2 | ||||
| Perus tuntemattomat | Ilmaiset jäsenet | Irrallisia tuntemattomia | Apukertoimet | |
| X1 | X3 | |||
| X2 | 1 | -1/2 | -1/2 | |
| X4 | -3 | -3/2 | -1/2 | 1 |
| X5 | 3 | 1/2 | -1/2 | 1 |
| X6 | 5 | 1/2 | 1/2 | -1 |
| F | 2 | -2 | -1 | 2 |
Kuka ei ole vielä avannut manuaalista Toiminnot murtolukujen kanssa uuteen ikkunaan, voi tehdä sen nyt, koska on aika.
Jotta saadaan taulukon 2 jäljellä olevat rivit, tämän taulukon ensimmäisellä rivillä jo olevat luvut kerrotaan täytettävän rivin apukertoimella ja tulokseen lisätään numero taulukosta 1, joka on samalla rivillä vastaava muuttuja.
Esimerkiksi toisen rivin vapaan jäsenen saamiseksi kerromme luvun 1 yhdellä ja lisäämme numeron -4 taulukosta 1. Saamme -3. Löydämme kertoimen toiselta riviltä samalla tavalla: 
. Koska edellisessä taulukossa ei ole saraketta uudella vapaalla muuttujalla, uuden vapaan muuttujan sarakkeen toisen rivin kerroin on 
(eli taulukosta 1 lisätään 0, koska taulukossa 1 ei ole saraketta c).
Indeksirivi täytetään samalla tavalla:
Näin saatu ratkaisu ei taaskaan ole optimaalinen, koska indeksirivin vapaiden muuttujien kertoimet ovat jälleen negatiivisia.
Siirrytään seuraavaan simpleksitaulukkoon etsimällä indeksiriviltä suurin (modulo) lukuista ja eli kertoimien moduulit. Tämä luku on 2. Siksi johtava sarake on sarake, joka sisältää .
Etsiäksesi johtavaa riviä, etsitään vapaiden jäsenten vähimmäissuhde eturivin elementteihin. Saamme:
.
Siksi johtava rivi on se, jolle kirjoitetaan, ja johtava elementti on -3/2.
Kolmannen simpleksitaulukon laatiminen
Ensimmäiselle riville kirjoitetaan uusi perusmuuttuja. Sarakkeeseen, jossa se oli, syötetään uusi ilmainen muuttuja .
Ensimmäinen linja:
Apukertoimet:
| Taulukko 3 | ||||
| Perus tuntemattomat | Ilmaiset jäsenet | Irrallisia tuntemattomia | Apukertoimet | |
| X4 | X3 | |||
| X1 | 2 | -2/3 | 1/3 | |
| X2 | 2 | -1/3 | -1/3 | 1/2 |
| X5 | 2 | 1/3 | -2/3 | -1/2 |
| X6 | 4 | 1/3 | 1/3 | -1/2 |
| F | 6 | -4/3 | -1/3 | 2 |
Tuloksena oleva ratkaisu ei taaskaan ole optimaalinen, koska indeksirivin vapaiden tuntemattomien kertoimet ovat jälleen negatiivisia.
Siirrytään neljänteen simpleksitaulukkoon etsimällä suurin luvuista ja . Tämä on numero.
Siksi johtava sarake on sarake, jossa on .
Vapaiden jäsenten ja johtavan sarakkeen elementtien suhteiden vähimmäismoduuli:
.
Siksi johtava rivi on se, jolle kirjoitetaan, ja johtava elementti on 1/3.
Neljännen simpleksitaulukon ensimmäiselle riville kirjoitetaan uusi perusmuuttuja. Sarakkeeseen, jossa se oli, kirjoitamme uuden ilmaisen muuttujan .
Ensimmäinen linja:
Apukertoimet:
| Taulukko 4 | ||||
| Perus tuntemattomat | Ilmaiset jäsenet | Irrallisia tuntemattomia | Apukertoimet | |
| X5 | X3 | |||
| X4 | 6 | 3 | -2 | |
| X1 | 6 | 2 | -1 | 2/3 |
| X2 | 4 | 1 | -1 | 1/3 |
| X6 | 2 | -1 | 1 | -1/3 |
| F | 14 | 4 | -3 | 4/3 |
Jäljellä olevien rivien laskenta toisen rivin esimerkin avulla:
Tuloksena oleva ratkaisu ei myöskään ole optimaalinen, mutta se on jo parempi kuin edelliset, koska yksi indeksirivin vapaiden muuttujien kertoimista on ei-negatiivinen.
Suunnitelman parantamiseksi siirrytään seuraavaan simplex-taulukkoon.
Etsi suurin luvuista 4 ja . Tämä luku on 4. Siksi johtava sarake on .
Etsi johtava rivi etsimällä
.
Siksi johtava rivi on se, joka sisältää . Mutta he olivat jo yhdessä vapaiden muuttujien joukossa. Siksi seuraavan muuttujan siirtämiseksi vapaasta perustilaan valitsemme toisen johtavan sarakkeen - sen, johon kirjoitetaan.
Etsi johtava rivi etsimällä
.
Siksi avainrivi on se, johon kirjoitetaan, ja johtava elementti on 1.
Viidennessä simpleksitaulukossa uusi perusmuuttuja kirjoitetaan ensimmäiselle riville. Sarakkeeseen, jossa se oli, kirjoitamme uuden ilmaisen muuttujan .
Ensimmäinen linja:
Apukertoimet:
| Taulukko 5 | ||||
| Perus tuntemattomat | Ilmaiset jäsenet | Irrallisia tuntemattomia | Apukertoimet | |
| X5 | X6 | |||
| X3 | 2 | -1 | 1 | |
| X4 | 10 | 2 | ||
| X1 | 8 | 1 | ||
| X2 | 6 | 1 | ||
| F | 20 | 1 | 3 | 3 |
Yritetään heti selvittää, onko ratkaisu optimaalinen. Siksi laskemme muille riveille vain vapaat termit (perusmuuttujien arvojen selvittämiseksi, kun vapaat muuttujat ovat nolla) ja indeksirivin vapaiden muuttujien kertoimet.
Vapaat jäsenet:
Toisella rivillä ;
Kolmannella rivillä ;
Neljännellä rivillä.
Hakemistorivi:
Katsomme simpleksitaulukkoa 5. Näemme, että optimaalinen ratkaisu on saatu, koska indeksirivin vapaiden tuntemattomien kertoimet ovat ei-negatiivisia.
Simpleksi menetelmä algebrallisilla muunnoksilla
Ratkaistaan algebrallisilla muunnoksilla sama esimerkki kuin edellisessä kappaleessa. On huomattava, että kun ratkaistaan tämän tyyppistä simpleksimenetelmää, on parempi olla kirjoittamatta tavoitefunktiota muotoon , koska se on helppo hämmentyä merkkeihin. Mutta tässä tapauksessa algoritmin piste, joka määrittää optimaalisuuskriteerin, muutetaan seuraavasti.
Jos lineaarisen muodon maksimi (minimi) löytyy eikä sen lausekkeessa ole ei-perusmuuttujia positiivisilla (negatiivisilla) kertoimilla, niin optimaalisuuskriteeri täyttyy ja tuloksena oleva perusratkaisu on optimaalinen - ratkaisu on ohi. Jos lineaarisen muodon maksimi (minimi) löydettäessä sen lauseke sisältää yhden tai useamman ei-perusmuuttujan positiivisilla (negatiivisilla) kertoimilla, siirry uuteen perusratkaisuun.
Esimerkki. Etsi funktion maksimi rajoitusten alla
Vaihe I. Otamme käyttöön muita ei-negatiivisia muuttujia ja vähennämme tämän epäyhtälöjärjestelmän vastaavaksi yhtälöjärjestelmäksi
.
Esitetyt lisämuuttujat otetaan pääasiallisiksi muuttujiksi, koska tällöin järjestelmän perusratkaisu löytyy helposti. Sitten ja ovat pieniä muuttujia.
Ilmaisemalla päämuuttujat ei-perusmuuttujilla saamme
Näin ollen tämä muuttujien jako perus- ja ei-perusarvoihin vastaa perusratkaisua 
, joka on virheellinen (kaksi muuttujaa ovat negatiivisia), eikä siksi ole optimaalinen. Siirrytään tästä perusratkaisusta parannettuun ratkaisuun.
Päättääksesi, mikä muuttuja tulee muuntaa ei-periaatteellisesta pääasialliseksi, harkitse jompaakumpaa viimeisen negatiivisen vapaan järjestelmän kahdesta käytettävissä olevasta yhtälöstä, esimerkiksi toista. Se osoittaa, että ja voidaan kääntää päämuuttujiksi, koska tässä yhtälössä niillä on positiiviset kertoimet (siis, kun ne kasvavat, ja tämä tapahtuu, jos käännämme jonkin niistä päämuuttujiksi, muuttuja kasvaa).
Yritetään kääntää päämuuttuja . Sen määrittämiseksi, mikä muuttuja tulisi siirtää päämuuttujasta ei-perusmuuttujaan, löydämme järjestelmän vapaiden jäsenten pienimmän suhteen kertoimiin absoluuttisen arvon . Meillä on . Se saadaan kolmannesta yhtälöstä, joka osoittaa, että muuttuja on muutettava ei-perusmuuttujiksi, mikä on positiivista alkuperäisessä perusratkaisussa. Näin ollen tuloksena oleva perusratkaisu sisältää alkuperäisen tapaan kaksi negatiivista komponenttia, eli siirtyminen sellaiseen perusratkaisuun ei parane.
Yksinkertainen menetelmä− tämä on menetelmä viitesuunnitelmien järjestykseen luetteloimiseksi (järjestyksen varmistaa tavoitefunktion arvon yksitoikkoinen muutos siirryttäessä seuraavaan suunnitelmaan). Tässä tapauksessa on noudatettava periaatetta: jokaisen seuraavan askeleen tulee parantaa tai ääritapauksissa ei huonontaa tavoitefunktion arvoa.
LLP:n ratkaisemiseksi simplex menetelmä se pelkistyy kanoniseen muotoon, ts. rajoituksista - eriarvoisuudesta pitää tehdä rajoituksia - tasa-arvoa. Tätä varten jokaista rajoitusta täydennetään ylimääräisellä ei-negatiivisella taseen muuttuja“+”-merkillä, jos eriarvoisuusmerkki on “£”, ja “–”-merkillä, jos eriarvomerkki on “³”.
Tavoitefunktiossa nämä lisämuuttujat tulevat nollakertoimilla, ts. kohdefunktion merkintä ei muutu. Jokainen muuttuja, joka ei ole ei-negatiivisuuden ehdon alainen, voidaan esittää kahden ei-negatiivisen muuttujan erotuksena: .
Jos tehtävärajoitukset heijastavat resurssien olemassaoloa ja kulutusta, niin tehtäväsuunnitelman kanoniseen muotoon kirjoitetun lisämuuttujan numeerinen arvo on yhtä suuri kuin käyttämättömän resurssin määrä.
Käytämme ongelman ratkaisemiseksi simplex-menetelmällä Lineaariyhtälöjärjestelmän lyhennetyt simpleksitaulukot ja modifioitu Jordanin eliminointimenetelmä.
1. Laadimme ensimmäisen perussuunnitelman
Tehtävä pysyy samana. Tuodaan epäyhtälöjärjestelmän standardimuoto (1) yhtälöjärjestelmän kanoniseen muotoon ottamalla käyttöön lisää tasapainomuuttujia x 3 , x 4 , x 5 ,x 6 .
Taloudellisessa mielessä lisämuuttujien arvot x 3 , x 4 , x 5 määrittää raaka-aineiden saldon tuotteiden myynnin jälkeen.
Tuloksena olevan yhtälöjärjestelmän matriisilla on muoto:
Se näkyy matriisissa A 4. kertaluvun perusmolli on determinantti, joka koostuu lisämuuttujien yksikkökertoimista x 3 , x 4 , x 5 ,x 6, koska se on eri kuin nolla ja yhtä suuri kuin 1. Tämä tarkoittaa, että näiden muuttujien sarakevektorit ovat lineaarisesti riippumattomia, ts. muodossa perusta, ja vastaavat muuttujat x 3 , x 4 , x 5 ,x 6 ovat perus(perus). Muuttujat x 1 , x 2 kutsutaan vapaa(alaikäinen).
Jos vapaat muuttujat x 1 ja x 2 asettaa eri arvoja, niin ratkaisemalla järjestelmän perusmuuttujien suhteen saadaan ääretön joukko tiettyjä ratkaisuja. Jos vapaille muuttujille asetetaan vain nolla-arvot, niin loputtomasta määrättyjen ratkaisujen joukosta, perusratkaisuja- perussuunnitelmat.
Jotta saadaan selville, voivatko muuttujat olla perusmuuttujia, on tarpeen laskea näiden muuttujien kertoimista koostuva determinantti. Jos tämä determinantti ei ole nolla, nämä muuttujat voivat olla perusmuuttujia.
Perusratkaisujen lukumäärä ja vastaava määrä perusmuuttujien ryhmiä voi olla enintään , missä n on muuttujien kokonaismäärä, r on perusmuuttujien lukumäärä, r≤ m≤ n.
Tehtävämme puolesta r = 4; n= 6. Sitten ts. 15 4 perusmuuttujan ryhmää on mahdollista (tai 15 perusratkaisua).
Ratkaistaan yhtälöjärjestelmä perusmuuttujien suhteen x 3 , x 4 , x 5 ,x 6:
Olettaen, että vapaat muuttujat x 1 = 0, x 2 = 0, saamme perusmuuttujien arvot: x 3 = 312; x 4 = 15; x 5 = 24;x 6 = -10, so. perusratkaisu on = (0; 0; 312; 15; 24; -10).
Tämä perusratkaisu on mahdotonta hyväksyä, koska x 6 = –10 ≤ 0 ja rajoiteehdon mukaan x 6 ≥ 0. Siksi muuttujan sijaan x 6 perustana sinun on otettava toinen muuttuja vapaasta x 1 tai x 2 .
Suoritamme jatkoratkaisun lyhennetyillä simpleksitaulukoilla täyttämällä ensimmäisen taulukon rivit järjestelmän kertoimilla seuraavasti (taulukko 1):
pöytä 1
F- merkkijonoa kutsutaan indeksi. Se on täynnä kohdefunktion kertoimia, jotka on otettu vastakkaisilla etumerkeillä, koska funktion yhtälö voidaan esittää F = 0 – (– 4x 1 – 3x 2).
Ilmaisten jäsenten sarakkeessa b i on negatiivinen elementti b 4 = -10, so. järjestelmän ratkaisu on virheellinen. Saadaksesi kelvollinen ratkaisu (perussuunnitelma), elementti b 4 on tehtävä ei-negatiiviseksi.
Valita x 6 - rivi, jossa on negatiivinen vapaa jäsen. Tämä rivi sisältää negatiivisia elementtejä. Valitse mikä tahansa niistä, esimerkiksi "-1" tuumaa x 1 -sarake ja x 1 - sarake hyväksy muodossa lupasarake(se määrittää, että muuttuja x 1 siirtyy ilmaisesta perusversioon).
Jaamme ilmaisia jäseniä b i asiaan liittyvistä elementeistä a on ratkaiseva sarake, saamme arvioivat suhteetΘ i==(24, 15, 12, 10). Näistä valitsemme pienimmän positiivisen (minΘ i=10), joka vastaa luparivi. Käyttöoikeusmerkkijono määrittää muuttujan xj, joka seuraavassa vaiheessa ulkonee pohjasta ja tulee vapaaksi. Siksi x 6 -rivi on salliva rivi ja elementti "-1" on mahdollistava elementti. Ympyröimme sen. Muuttujat x 1 ja x 6 vaihdetaan.
Arvioidut suhteet Θ i jokaisella rivillä määräytyvät säännöt:
1) Θ i= jos b i ja a on on erilaisia merkkejä;
2) Θ i= ∞ jos b i= 0 ja a on < 0;
3) Θ i= ∞ jos a on = 0;
4) Θ i= 0 jos b i= 0 ja a on > 0;
5) Θ i= jos b i ja a on on samat merkit.
Otamme modifioidun Jordanin eliminoinnin (MJJI) askeleen permissive-elementillä ja laadimme uuden taulukon (Taulukko 2) seuraavan säännön mukaisesti:
1) Resolution elementin (RE) tilalle asetetaan arvo, sen käänteisarvo, ts. ;
2) sallivan rivin elementit jaetaan RE:ksi;
3) erottelevan sarakkeen elementit jaetaan RE:ksi ja merkki muuttuu;
4) loput elementit löydetään suorakaidesäännön mukaan:
Taulukosta. 2 osoittaa, että vapaat jäsenet sisään b i-sarakkeet eivät ole negatiivisia, joten saadaan alkuperäinen hyväksyttävä ratkaisu - ensimmäinen perussuunnitelma= (10; 0; 182; 5; 4; 0). Tässä tapauksessa funktion arvo F() = 40. Geometrisesti tämä vastaa huippua F(10; 0) ratkaisupolygoni (kuva 1).
taulukko 2
2. Tarkistamme suunnitelman optimaalisen. Perussuunnitelma ei ole optimaalinen, koska sisään F-rivillä on negatiivinen kerroin "-4". Parannamme suunnitelmaa.
3. Uuden perusviivan löytäminen
Valitsemme sallivan elementin säännön mukaan:
Valitsemme pienimmän negatiivisen kertoimen F-rivi "-4", joka määrittää aktivointisarakkeen - x 6; muuttuja x 6 kääntää perus;
Löydämme suhteet Θ i, niistä valitsemme pienimmän positiivisen, joka vastaa sallivaa merkkijonoa:
min Θ i = min(14, 5, 2, ∞) = 2, siis x 5 - rivi - salliva, muuttuva x 5 käännämme vapaaksi (muuttujat x 5 ja x 6 vaihdetaan).
Sallivan rivin ja sarakkeen leikkauskohdassa on salliva elementti "2";
Suoritamme vaiheen SHMZhI, rakennamme pöydän. 3 yllä olevan säännön mukaisesti ja saat uuden vertailusuunnitelman = (12; 0; 156; 3; 0; 2).
Taulukko 3
4. Uuden perussuunnitelman optimaalisen tarkistaminen
Perussuunnitelma ei myöskään ole optimaalinen, koska vuonna F-rivillä on negatiivinen kerroin "-1". Toiminnon arvo F() = 48, joka geometrisesti vastaa huippua E(12; 0) ratkaisupolygoni (kuva 1). Parannamme suunnitelmaa.
5. Uuden perusviivan löytäminen
x 2-sarake on sallittu, koska in F-rivillä pienin negatiivinen kerroin "-1" on x 2-sarake (A 2 = -1). Pienimmän Θ:n löytäminen i: min Θ i = min(≈ 9, 6, ∞, 24) = 6, siis x 4. rivi - salliva. Salliva elementti "1/2". Muuttujien vaihto x 2 ja x neljä . Suoritamme vaiheen SHMZhI, rakennamme pöydän. 4, saamme uuden vertailusuunnitelman = (9; 6; 51; 0; 0; 5).
6. Perussuunnitelman optimaalisen tarkistaminen
AT F-rivillä kaikki kertoimet eivät ole negatiivisia, joten vertailusuunnitelma on optimaalinen. Geometrisesti vastaa pistettä D(9;6) (katso kuva 1). Optimaalinen suunnitelma antaa tavoitefunktion maksimiarvon c.u.
Main idea simplex-menetelmästä LLP:n ratkaisemiseksi koostuu LLP-tukiratkaisujen jatkuvasta parantamisesta.
Yksipuolisen menetelmän kirjoittamiseen on useita tapoja.
- Yksipuolisen menetelmän perusmuoto;
- Simpleksimenetelmä simpleksitaulukon muodossa;
- Modifioitu simpleksimenetelmä;
- Yksinkertainen menetelmä sarakkeen muodossa;
- Yksinkertainen menetelmä rivimuodossa.
Määritellään tavoitefunktion F(X) = 3x 1 +5x 2 +4x 3 maksimiarvo seuraavilla rajoitusehdoilla.
0,1x1 +0,2x2 +0,4x3 ≤1100
0,05x1 +0,02x2 +0,02x3 ≤120
3x1 +x2 +2x3 ≤8000
Ensimmäisen vertailusuunnitelman muodostamiseksi pelkistetään epäyhtälöjärjestelmä yhtälöjärjestelmäksi ottamalla käyttöön lisämuuttujia (siirtymä kanoniseen muotoon).
0,1x1 + 0,2x2 + 0,4x3 + 1x4 + 0x5 + 0x6 = 1100
0,05 x 1 + 0,02 x 2 + 0,02 x 3 + 0 x 4 + 1 x 5 + 0 x 6 = 120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 8000
Simpleksimenetelmän perusmerkintä
| Ratkaisu suoritetaan ilmaisemalla perusmuuttujat ei-perusmuuttujien kautta: x0 = 3x1 +5x2 +4x3 x 4 = 1100-0,1 x 1 -0,2 x 2 -0,4 x 3 x 5 = 120 - 0,05 x 1 - 0,02 x 2 - 0,02 x 3 x 6 = 8000-3x 1 -x 2 -2x 3 |
Simplex-menetelmä simpleksitaulukon muodossa
Ratkaisu suoritetaan simpleksitaulukon muodossa. Lomake on suunniteltu tietokoneella laskemiseen. Keinotekoista perustaa käytettäessä käytetään erityistä numeroa M (yleensä 10000).| Suunnitelma | Perusta | AT | x 1 | x2 | x 3 | x4 | x5 | x6 | min |
| 1 | x4 | 1100 | 0.1 | 0.2 | 0.4 | 1 | 0 | 0 | 5500 |
| x5 | 120 | 0.05 | 0.02 | 0.02 | 0 | 1 | 0 | 6000 | |
| x6 | 8000 | 3 | 1 | 2 | 0 | 0 | 1 | 8000 | |
| Indeksirivi | F(X1) | 0 | -3 | -5 | -4 | 0 | 0 | 0 | 0 |
| 2 | x2 | 5500 | 0.5 | 1 | 2 | 5 | 0 | 0 | 11000 |
| x5 | 10 | 0.04 | 0 | -0.02 | -0.1 | 1 | 0 | 250 | |
| x6 | 2500 | 2.5 | 0 | 0 | -5 | 0 | 1 | 1000 | |
| Indeksirivi | F(X2) | 27500 | -0.5 | 0 | 6 | 25 | 0 | 0 | 0 |
| 3 | x2 | 5375 | 0 | 1 | 2.25 | 6.25 | -12.5 | 0 | 11000 |
| x1 | 250 | 1 | 0 | -0.5 | -2.5 | 25 | 0 | 250 | |
| x6 | 1875 | 0 | 0 | 1.25 | 1.25 | -62.5 | 1 | 1000 | |
| Indeksirivi | F(X3) | 27625 | 0 | 0 | 5.75 | 23.75 | 12.5 | 0 | 0 |
Muokattu simpleksimenetelmä
| Kerroinmatriisi A = a ij Matriisi b. |
Yksinkertainen menetelmä sarakkeen muodossa
| Siirrymme simplex-menetelmän sarakemuotoon. Ilmaisemme jokaisen muuttujan ei-perusmuuttujilla. x 0 = 0-3(-x 1)-5(-x 2)-4(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 1 = 0-1(-x 1)+0(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 2 = 0+0(-x 1)-1(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 3 = 0+0(-x 1)+0(-x 2)-1(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 4 = 1100+0.1(-x 1)+0.2(-x 2)+0.4(-x 3)+1(-x 4)+0(-x 5)+0(-x 6) x 5 = 120+0.05(-x 1)+0.02(-x 2)+0.02(-x 3)+0(-x 4)+1(-x 5)+0(-x 6) x 6 = 8000+3(-x 1)+1(-x 2)+2(-x 3)+0(-x 4)+0(-x 5)+1(-x 6) Tämä järjestelmä vastaa taulukkoa T 0 .
|
Yksinkertainen menetelmä merkkijonomuodossa
Alkuperäiseksi hyväksyttäväksi kantaksi voimme ottaa B 0 =<4, 5, 6>. Se vastaa seuraavaa taulukkoa.
|
Järjestelmän kertoimista koostuvaa matriisia Q kutsutaan simplex pöytä Vastaa kantaa B. Yksipuolista taulua kutsutaan hyväksyttäväksi, tai suoraan hyväksyttäväksi, jos q i0 ≥ 0. Yksipuolisen taulukon Q viimeisen rivin alkioita q i0 kutsutaan suhteellisia arvioita.
Ratkaisumuodot keinotekoisen perustan menetelmällä
Tavoitefunktioon lisättyjen keinotekoisten muuttujien käytölle määrätään niin sanottu M:n sakko, erittäin suuri positiivinen luku, jota ei yleensä määritellä.Tuloksena olevaa perustaa kutsutaan keinotekoiseksi perustaksi ja ratkaisumenetelmää keinotekoiseksi perustaksi.
Lisäksi keinotekoiset muuttujat eivät liity tehtävän sisältöön, mutta niiden avulla voit rakentaa lähtökohdan, ja optimointiprosessi pakottaa nämä muuttujat ottamaan nolla-arvoja ja varmistamaan optimaalisen ratkaisun hyväksyttävyyden.
Ratkaisumuodot keinotekoisen perustan menetelmällä:
- M-menetelmä (simplex-taulukko);
- kaksivaiheinen tai kaksivaiheinen simpleksimenetelmä (Perusmerkintä, Modified simplex -menetelmä, Simplex-menetelmä sarakemuodossa, Simplex-menetelmä rivimuodossa).
Jos tehtävän ehdossa on rajoituksia, joiden merkki on ≥, niin ne voidaan pelkistää muotoon ∑a ji b j kertomalla molemmat epäyhtälön osat -1:llä. Esittelemme m lisämuuttujaa x n+j ≥0(j =1,m ) ja muunnamme rajoitukset yhtälöiden muotoon
(2)
Oletetaan, että kaikki tehtävän x 1 , x 2 ,..., x n alkumuuttujat ovat ei-perusmuuttujia. Silloin lisämuuttujat ovat perusmuuttujia, ja tietyllä rajoitusjärjestelmän ratkaisulla on muoto
x 1 = x 2 = ... = x n = 0, x n+ j = bj, j = 1, m. (3)
Koska tässä tapauksessa tavoitefunktion arvo F 0 = 0, voimme esittää F(x):n seuraavasti:
F(x)=∑c i x i + F 0 =0 (4)
Alkuperäinen simpleksitaulukko (simplex-taulukko 1) on koottu yhtälöiden (2) ja (4) perusteella. Jos lisämuuttujia x n+j edeltää "+"-merkki, kuten kohdassa (2), niin kaikki kertoimet ennen muuttujia x i ja vapaa termi b j syötetään yksipuoliseen taulukkoon ilman muutoksia. Tavoitefunktion kertoimet sen maksimoimisen aikana syötetään simpleksitaulukon alimmalle riville vastakkaisilla etumerkeillä. Yksipuolisen taulukon vapaat jäsenet määrittävät ongelman ratkaisun.
Algoritmi ongelman ratkaisemiseksi on seuraava:
1. vaihe. Ilmaiset jäsenet -sarakkeen elementit näytetään. Jos ne ovat kaikki positiivisia, on löydetty hyväksyttävä perusratkaisu ja edetään algoritmin vaiheeseen 5, joka vastaa optimaalisen ratkaisun löytämistä. Jos alkuperäisessä simplex-taulukossa on negatiivisia vapaita termejä, ratkaisu ei ole kelvollinen ja sinun tulee siirtyä vaiheeseen 2.
2. vaihe. Toteutettavan ratkaisun löytäminen suoritetaan, samalla kun on päätettävä, mikä ei-perusmuuttuja sisällytetään kantaan ja mikä muuttuja poistetaan kannasta.
Pöytä 1.
| perusmuuttujat | Vapaat jäsenet rajoituksissa | Ei-perusmuuttujat | |||||
| x 1 | x2 | ... | x l | ... | x n|||
| xn+1 | b 1 | a 11 | a 12 | ... | a 1l | ... | a 1n |
| xn+2 | b 2 | a 21 | a 22 | ... | a 2l | ... | a 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+r | b2 | a r1 | a r2 | ... | a rl | ... | a rn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+m | b m | m1 | m2 | ... | aml | ... | amn |
| F(x)max | F0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
Tätä varten valitse mikä tahansa vapaiden jäsenten sarakkeen negatiivinen elementti (olkoon se b 2 johtava tai salliva. Jos negatiivisen vapaan jäsenen rivillä ei ole negatiivisia elementtejä, rajoitusjärjestelmä on epäjohdonmukainen ja ongelmalla ei ole ratkaisua.
Samanaikaisesti se muuttuja, joka vaihtaa etumerkkiä ensimmäisenä valitun NP x l:n kasvaessa, suljetaan pois BP:stä. Tämä on x n+r , jonka indeksi r määritetään ehdosta
nuo. muuttuja, joka vastaa vapaan termin pienintä suhdetta valitun johtavan sarakkeen elementtiin. Tätä suhdetta kutsutaan simplex-suhde. Vain positiiviset simpleksisuhteet tulisi ottaa huomioon.
Muuttujaa x n+r vastaava merkkijono kutsutaan johtaa tai sallii. Yksipuolisen taulukon elementtiä a rl , joka on johtavan rivin ja johtavan sarakkeen leikkauskohdassa, kutsutaan johtavaksi eli ratkaisevaksi elementiksi. Johtavan elementin löytäminen päättää työskentelyn jokaiseen seuraavaan simpleksitaulukkoon.
3. vaihe. Lasketaan uusi simpleksitaulukko, jonka alkiot lasketaan uudelleen edellisen vaiheen simpleksitaulukon alkioista ja merkitään alkuluvulla, ts. b" j , a" ji , c" i , F" 0 . Alkiot lasketaan uudelleen seuraavien kaavojen mukaisesti:
Ensin edellisessä yksipuolisessa taulukossa olleet rivit ja sarakkeet täytetään uudessa simpleksitaulukossa. Lauseke (5) tarkoittaa, että alkuelementin tilalla oleva elementti a "rl on yhtä suuri kuin edellisen simpleksitaulukon elementin käänteisluku. Rivin a ri elementit jaetaan alkuelementillä ja sarake a jl jaetaan myös johtavalla alkiolla, mutta ne otetaan päinvastaisella etumerkillä. Alkiot b" r ja c" l lasketaan samalla periaatteella.
Loput kaavat voidaan kirjoittaa helposti käyttämällä .
Suorakulmio on rakennettu vanhan simpleksitaulukon mukaan siten, että yksi sen diagonaaleista muodostuu uudelleen lasketuista (a ji) ja johtavasta (a rl) elementistä (kuva 1). Toinen lävistäjä on yksilöllisesti määritetty. Löytääkseen uuden elementin a "ji, vastakkaisen lävistäjän elementtien tulo jaettuna johtavalla elementillä vähennetään elementistä a ji (tämä ilmaistaan merkillä" - "solussa). Vastaavasti elementit b" j, (j≠r) ja c"i lasketaan uudelleen, (i≠l).
4. vaihe. Uuden simpleksitaulukon analyysi alkaa algoritmin ensimmäisestä vaiheesta. Toimenpidettä jatketaan, kunnes löydetään toteuttamiskelpoinen perusratkaisu, ts. Vapaat jäsenet -sarakkeen kaikkien elementtien on oltava positiivisia.
5. vaihe. Uskomme, että hyväksyttävä perusratkaisu on löydetty. Tarkastellaan tavoitefunktion F(x) rivin kertoimia. Yksipuolisen taulukon optimiteetin merkki on F-rivin ei-perusmuuttujien kertoimien ei-negatiivisuus.
Riisi. 1. Suorakulmion sääntö
Jos F-rivin kertoimien joukossa on negatiivisia (vapaa termiä lukuun ottamatta), sinun on siirryttävä toiseen perusratkaisuun. Tavoitefunktiota maksimoitettaessa kanta sisältää ei-perusmuuttujien (esim. x l) perusarvon, jonka sarake vastaa simpleksitaulukon alarivillä olevan negatiivisen kertoimen c l maksimiabsoluuttista arvoa. Näin voit valita muuttujan, jonka kasvu johtaa tavoitefunktion parantumiseen. Muuttujaa x l vastaavaa saraketta kutsutaan johtavaksi sarakkeeksi. Samalla se muuttuja x n+r jätetään pois kannasta, jonka indeksin r määrää pienin simpleksisuhde:
riviä, joka vastaa riviä x n+r, kutsutaan eturiviksi ja yksipuoleisen taulukon elementtiä a rl , joka on johtavan rivin ja johtavan sarakkeen leikkauskohdassa. johtava elementti.
6. vaihe. 3. vaiheessa annettujen sääntöjen mukaisesti. Toimenpide jatkuu, kunnes optimaalinen ratkaisu löydetään tai todetaan, että sitä ei ole olemassa.
Jos ratkaisua optimoitaessa johtavassa sarakkeessa kaikki elementit ovat ei-positiivisia, eturiviä ei voi valita. Tässä tapauksessa tehtävän sallittujen ratkaisujen alueella olevaa funktiota ei rajoiteta ylhäältä ja F max ->&∞.
Jos ääripään haun seuraavassa vaiheessa yksi perusmuuttujista tulee yhtä suureksi kuin nolla, niin vastaavaa perusratkaisua kutsutaan degeneroituneeksi. Tässä tapauksessa tapahtuu niin sanottu silmukka, jolle on ominaista se, että sama BP:n yhdistelmä alkaa toistua tietyllä taajuudella (funktion F arvo säilyy tässä tapauksessa) ja on mahdotonta vaihtaa uusi hyväksyttävä perusratkaisu. Silmukka on yksi simplex-menetelmän suurimmista haitoista, mutta se on suhteellisen harvinaista. Käytännössä tällaisissa tapauksissa yleensä kieltäydytään syöttämästä kantaan muuttujaa, jonka sarake vastaa tavoitefunktion negatiivisen kertoimen maksimiabsoluuttista arvoa, ja tehdään satunnainen uusi perusratkaisu.
Esimerkki 1. Ratkaise ongelma
max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)
Yksinkertainen menetelmä ja anna geometrinen tulkinta ratkaisuprosessista.
Graafinen tulkinta ongelman ratkaisusta on esitetty kuvassa. 2. Tavoitefunktion maksimiarvo saavutetaan ODZP:n yläosassa koordinaatteilla . Ratkaistaan ongelma käyttämällä simpleksitaulukoita. Kerro toinen rajoite arvolla (-1) ja ota käyttöön lisämuuttujia, jotta epäyhtälöt saadaan yhtäläisyyksien muotoon, sitten
Alkumuuttujat x 1 ja x 2 pidetään ei-perusmuuttujina ja lisämuuttujat x 3 , x 4 ja x 5 katsotaan perusmuuttujiksi ja laaditaan simpleksitaulukko (simplex-taulukko 2). Yksipuolista taulukkoa vastaava ratkaisu. 2, ei kelpaa; johtava elementti hahmotellaan ja valitaan yllä olevan algoritmin vaiheen 2 mukaisesti. Seuraava simplex-välilehti. 3 määrittelee hyväksyttävän perusratkaisun; 2 Johtava elementti hahmotellaan ja valitaan ongelmanratkaisualgoritmin 5. vaiheen mukaisesti. Tab. 4 vastaa tehtävän optimaalista ratkaisua, joten: x 1 = x 5 = 0; x 2 \u003d 4; x 3 \u003d 3; x 4 = 8; F max = 20.
Riisi. 2. Tehtävän graafinen ratkaisu
