Piditkö siitä? Lisää kirjanmerkkeihin

Ongelmien ratkaiseminen simplex-menetelmällä: online-esimerkkejä

Tehtävä 1. Yritys valmistaa kylpyhuonehyllyjä kahdessa koossa - A ja B. Myyjät arvioivat, että markkinoilla voidaan myydä jopa 550 hyllyä viikossa. Jokainen tyypin A hylly vaatii 2 m2 materiaalia ja jokainen tyypin B hylly 3 m2 materiaalia. Yritys voi vastaanottaa jopa 1200 m2 materiaalia viikossa. Yhden A-tyypin hyllyn valmistukseen tarvitaan 12 minuuttia koneaikaa ja yhden B-tyypin hyllyn valmistukseen - 30 minuuttia; Konetta voi käyttää 160 tuntia viikossa. Jos A-tyypin hyllyjen myynnistä saatu voitto on 3 rahayksikköä ja B-tyypin hyllyistä - 4 rahayksikköä. yksikköä, kuinka monta hyllyä kutakin tyyppiä tulisi tuottaa viikossa?

Tehtävä 2. Ratkaise lineaarinen ohjelmointitehtävä simpleksimenetelmällä.

Tehtävä 3. Yritys valmistaa 3 tyyppisiä tuotteita: A1, A2, A3 käyttäen kahdenlaisia ​​raaka-aineita. Tiedetään kunkin raaka-ainetyypin kustannukset tuotantoyksikköä kohti, suunnittelukauden raaka-ainevarastot sekä kunkin lajin tuotantoyksikön tuotto.

1. Kuinka monta tuotetta kutakin tyyppiä pitää tuottaa voiton maksimoimiseksi?
2. Määritä kunkin raaka-aineen tila ja sen erityinen arvo.
3. Määritä kunkin raaka-aineen varastomuutosten enimmäisväli, jonka sisällä optimaalisen suunnitelman rakenne, ts. Tuotantonimikkeistö ei muutu.
4. Määritä tuotettujen tuotteiden määrä ja tuotannosta saatava voitto, kun jonkin niukan raaka-aineen varastoa lisätään mahdollisimman suureen (annetun tuotantoalueen sisällä) arvoon.
5. Määritä kunkin tuotetyypin yksikön voiton muutosvälit, jolloin tuloksena oleva optimaalinen suunnitelma ei muutu.

Tehtävä 4. Ratkaise lineaarinen ohjelmointitehtävä simpleksimenetelmällä:

Tehtävä 5. Ratkaise lineaarinen ohjelmointitehtävä simpleksimenetelmällä:

Tehtävä 6. Ratkaise tehtävä simplex-menetelmällä pitäen alkuperäisenä referenssisuunnitelmana ehdossa annettua suunnitelmaa:

Tehtävä 7. Ratkaise ongelma modifioidulla simpleksimenetelmällä.
Kahden tyyppisten tuotteiden A ja B valmistukseen käytetään kolmen tyyppisiä teknisiä laitteita. Tuote A:n yksikön valmistamiseksi ensimmäisen tyypin laitteet käyttävät a1=4 tuntia, toisen tyypin a2=8 tuntia ja kolmannen tyypin a3=9 tuntia. Tuotteen B yksikön valmistukseen käytetään ensimmäisen tyypin laitteita b1=7 tuntia, toisen tyypin laitteita b2=3 tuntia ja kolmannen tyypin laitteita b3=5 tuntia.
Ensimmäisen tyypin laitteet voivat toimia näiden tuotteiden valmistuksessa enintään t1=49 tuntia, toisen tyypin laitteet enintään t2=51 tuntia, kolmannen tyypin laitteet enintään t3=45 tuntia.
Lopputuotteen A yksikön myynnistä saatu voitto on ALPHA = 6 ruplaa ja tuote B on BETTA = 5 ruplaa.
Laadi tuotteille A ja B tuotantosuunnitelma ja varmista niiden myynnistä mahdollisimman suuri hyöty.

Tehtävä 8. Etsi optimaalinen ratkaisu dual simplex -menetelmällä

Lineaarisen ohjelmoinnin ongelmia. Se on peräkkäisessä rakenteessa, joka kuvaa tarkasteltavaa prosessia. Ratkaisu on jaettu kolmeen päävaiheeseen: muuttujien valinta, rajoitusjärjestelmän rakentaminen ja tavoitefunktion etsiminen.

Tämän jaon perusteella ongelmaehto voidaan muotoilla uudelleen seuraavasti: tavoitefunktion ääriarvo Z(X) = f(x1, x2, … ,xn) → max (min) ja vastaavat muuttujat, jos tiedetään, että ne täyttävät rajoitusjärjestelmän: Φ_i ( x1, x2, … ,xn) = 0, jos i = 1, 2, …, k;Φ_i (x1, x2, … ,xn)) 0 jos i = k+1, k+ 2, …, m.

Rajoitusjärjestelmä on saatettava kanoniseen muotoon, ts. lineaariseen yhtälöjärjestelmään, jossa muuttujien lukumäärä on suurempi kuin yhtälöiden lukumäärä (m > k). Tässä järjestelmässä on varmasti muuttujia, jotka voidaan ilmaista muiden muuttujien kautta, ja jos näin ei ole, niin ne voidaan ottaa käyttöön keinotekoisesti. Tässä tapauksessa ensimmäisiä kutsutaan perustaksi tai keinotekoiseksi perustaksi, ja jälkimmäisiä kutsutaan vapaaksi.

Yksipuolista menetelmää on helpompi tarkastella tietyn esimerkin avulla. Olkoon lineaarinen funktio f(x) = 6x1 + 5x2 + 9x3 ja rajoitusjärjestelmä: 5x1 + 2x2 + 3x3 ≤ 25 x1 + 6x2 + 2x3 ≤ 20. Tarvitsemme maksimiarvon funktion f(x) arvo.

Ratkaisu Määritä ensimmäisessä vaiheessa yhtälöjärjestelmän alkuperäinen (viite)ratkaisu täysin mielivaltaisella tavalla, jonka on täytettävä annettu rajoitusjärjestelmä. Tässä tapauksessa tarvitaan keinotekoisten, ts. perusmuuttujat x4, x5 ja x6: 5x1 + 2x2 + 3x3 + x4 = 25 x1 + 6x2 + 2x3 + x5 = 4x1 + 3x3 + x6 = 18;

Kuten näet, epäyhtälöt on muunnettu tasa-arvoiksi lisättyjen muuttujien x4, x5, x6 ansiosta, jotka ovat ei-negatiivisia suureita. Olet siis tuonut järjestelmän kanoniseen muotoonsa. Muuttuja x4 sisältyy ensimmäiseen yhtälöön kertoimella 1 ja toisessa yhtälössä kertoimella 0, sama pätee muuttujiin x5, x6 ja vastaaviin yhtälöihin, mikä vastaa kantan määritelmää.

Olet valmistellut järjestelmän ja löytänyt alkuperäisen vertailuratkaisun – X0 = (0, 0, 0, 25, 20, 18). Esitä nyt muuttujien kertoimet ja yhtälöiden vapaat termit (luvut "="-merkin oikealla puolella) taulukon muodossa lisälaskutoimien optimoimiseksi (katso kuva).

Yksipuolisen menetelmän ydin on saattaa tämä taulukko muotoon, jossa kaikki rivin L numerot ovat ei-negatiivisia arvoja. Jos tämä osoittautuu mahdottomaksi, järjestelmällä ei ole ollenkaan optimaalista ratkaisua. Valitse ensin tämän rivin pienin elementti, joka on -9. Numero on kolmannessa sarakkeessa. Muunna vastaava x3-muuttuja perusmuuttujaksi. Voit tehdä tämän jakamalla rivin kolmella siten, että solun lopussa on 1.

Nyt tarvitset solut ja kääntääksesi arvoon 0. Voit tehdä tämän vähentämällä kolmannen rivin vastaavista luvuista 3:lla. Toisen rivin elementeistä - kolmannen rivin elementit kerrottuna 2:lla. Ja lopuksi alkaen L-rivin elementit - kerrottuna (-9). Olet saanut toisen vertailuratkaisun: f(x) = L = 54, jossa x1 = (0, 0, 6, 7, 8, 0).

Harkitsemme simplex menetelmä lineaarisen ohjelmoinnin (LP) ongelmien ratkaisemiseen. Se perustuu siirtymiseen vertailusuunnitelmasta toiseen, jonka aikana tavoitefunktion arvo kasvaa.

Simplex-menetelmän algoritmi on seuraava:

1. Muunnamme alkuperäisen ongelman kanoniseen muotoon ottamalla käyttöön lisämuuttujia. Epäyhtälöille, joiden muoto on ≤, lisätään lisämuuttujia merkillä (+), mutta jos muotoa ≥, niin merkillä (-). Tavoitefunktioon lisätään lisämuuttujia vastaavilla etumerkeillä, joiden kerroin on yhtä suuri 0 , koska kohdefunktion ei pitäisi muuttaa taloudellista merkitystään.
2. Vektorit kirjoitetaan ulos P i muuttujien kertoimista ja vapaiden termien sarakkeesta. Tämä toiminto määrittää yksikkövektorien lukumäärän. Sääntönä on, että yksikkövektoreita tulee olla yhtä monta kuin rajoitusjärjestelmässä on epäyhtälöjä.
3. Tämän jälkeen lähdetiedot syötetään simpleksitaulukkoon. Yksikkövektorit viedään kantaan, ja jättämällä ne pois kannasta, löydetään optimaalinen ratkaisu. Tavoitefunktion kertoimet kirjoitetaan vastakkaisella merkillä.
4. Optimiteettimerkki LP-ongelmalle on, että ratkaisu on optimaalinen, jos se on f– rivillä kaikki kertoimet ovat positiivisia. Käyttöönottosarakkeen löytämissääntö - katsottu f– merkkijono ja sen negatiivisista elementeistä valitaan pienin. Vektori P i sen sisältämisestä tulee salliva. Sääntö ratkaisevan elementin valitsemiseksi - erottelevan sarakkeen positiivisten elementtien suhteet vektorin elementteihin kootaan P 0 ja luku, joka antaa pienimmän suhteen, tulee ratkaisevaksi elementiksi, jonka suhteen simpleksitaulukko lasketaan uudelleen. Tämän elementin sisältävää riviä kutsutaan sallivaksi riviksi. Jos resoluutiosarakkeessa ei ole positiivisia elementtejä, ongelmalla ei ole ratkaisua. Kun erotuselementti on määritetty, he jatkavat uuden simpleksitaulukon uudelleenlaskentaa.
5. Säännöt uuden simplex-taulukon täyttämiseksi. Yksikkö asetetaan erotuselementin tilalle, ja muiden elementtien oletetaan olevan yhtä suuria 0 . Resoluutiovektori lisätään kantaan, josta vastaava nollavektori jätetään pois, ja loput kantavektorit kirjoitetaan ilman muutoksia. Resoluutiomerkkijonon elementit jaetaan resoluutioelementillä, ja loput elementit lasketaan uudelleen suorakulmiosäännön mukaisesti.
6. Tätä tehdään asti f– kaikista merkkijonon elementeistä ei tule positiivisia.

Harkitsemme ongelman ratkaisemista käyttämällä edellä käsiteltyä algoritmia.
Annettu:

Tuomme ongelman kanoniseen muotoon:

Kokoamme vektorit:

Täytä simplex-taulukko:

:
Lasketaan vektorin ensimmäinen alkio uudelleen P 0, jolle teemme suorakulmion numeroista: ja saamme: .

Suoritamme samanlaisia ​​laskelmia kaikille muille simpleksitaulukon elementeille:

Saadussa suunnitelmassa f– rivi sisältää yhden negatiivisen elementin – (-5/3), vektori P 1. Sen sarakkeessa on yksi positiivinen elementti, joka on mahdollistava elementti. Lasketaan taulukko uudelleen tämän elementin osalta:

Ei negatiivisia elementtejä f– viiva tarkoittaa löydettyä optimaalinen suunnitelma:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).

• Ashmanov S. A. Lineaarinen ohjelmointi, M: Nauka, 1998,
• Ventzel E.S. Operations Research, M: Neuvostoliiton radio, 2001,
• Kuznetsov Yu.N., Kuzubov V.I., Voloshenko A.B. Matemaattinen ohjelmointi, M: Higher School, 1986.

Mukautettu lineaarinen ohjelmointiratkaisu

Voit tilata mitä tahansa tämän alan tehtäviä verkkosivuiltamme. Voit liittää tiedostoja ja määrittää määräaikoja osoitteessa

Tässä on manuaalinen (ei sovelma) ratkaisu kahdelle tehtävälle simplex-menetelmällä (samanlainen kuin sovelmaratkaisu) yksityiskohtaisten selitysten kanssa, jotta ymmärrät ongelmien ratkaisemisen algoritmin simplex-menetelmällä. Ensimmäinen tehtävä sisältää vain epäyhtälömerkit "≤" (ongelma alkuperustalla), toinen voi sisältää merkkejä "≥", "≤" tai "=" (tehtävä keinotekoisella pohjalla), ne ratkaistaan ​​eri tavalla.

Yksinkertainen menetelmä, ongelman ratkaiseminen alustavasti

1)Yksinkertainen menetelmä ongelmalle, jolla on alkuperusta (kaikki merkit eriarvoisuuden rajoituksista " ≤ ").

Kirjoitetaan ongelma kanoninen muoto, ts. kirjoitamme epätasa-arvorajoitukset uudelleen tasa-arvoiksi lisäämällä tase muuttujat:

Tämä järjestelmä on järjestelmä, jossa on kanta (kanta s 1, s 2, s 3, jokainen niistä sisältyy vain yhteen järjestelmän yhtälöön kertoimella 1), x 1 ja x 2 ovat vapaita muuttujia. Simpleksimenetelmällä ratkaistavissa tehtävissä tulee olla seuraavat kaksi ominaisuutta: - rajoitusjärjestelmän tulee olla yhtälöjärjestelmä, jossa on kanta; -järjestelmän kaikkien yhtälöiden vapaiden termien on oltava ei-negatiivisia.

Tuloksena oleva järjestelmä on järjestelmä, jolla on perusta ja sen vapaat ehdot eivät ole negatiivisia, joten voimme soveltaa simplex menetelmä. Luodaan ensimmäinen simpleksitaulukko (Iteraatio 0) ongelman ratkaisemiseksi simplex menetelmä, eli tavoitefunktion kerrointaulukko ja yhtälöjärjestelmä vastaaville muuttujille. Tässä "BP" tarkoittaa perusmuuttujien saraketta, "Ratkaisu" tarkoittaa systeemiyhtälöiden oikeanpuoleista saraketta. Ratkaisu ei ole optimaalinen, koska z-rivillä on negatiivisia kertoimia.

simpleksimenetelmän iteraatio 0

							Asenne

Ratkaisun parantamiseksi siirrytään seuraavaan iteraatioon simplex menetelmä, saamme seuraavan simpleksitaulukon. Tätä varten sinun on valittava ota sarake käyttöön, eli muuttuja, joka sisällytetään kantaan simpleksimenetelmän seuraavassa iterauksessa. Se valitaan suurimmalla absoluuttisella negatiivisella kertoimella z-rivillä (maksimitehtävässä) - simplex-menetelmän alkuperäisessä iteraatiossa tämä on sarake x 2 (kerroin -6).

Valitse sitten ota merkkijono käyttöön, eli muuttuja, joka poistuu kannasta seuraavassa simplex-menetelmän iteraatiossa. Se valitaan "Päätös"-sarakkeen pienimmällä suhteella resoluutiosarakkeen vastaaviin positiivisiin elementteihin (sarake "Suhde") - alkuperäisessä iteraatiossa tämä on rivi s 3 (kerroin 20).

Salliva elementti on ratkaisevan sarakkeen ja ratkaisevan rivin leikkauskohdassa, sen solu on korostettu värillä, se on yhtä suuri kuin 1. Siksi seuraavassa simpleksimenetelmän iteraatiossa muuttuja x 2 korvaa s 1:n kannassa. Huomaa, että suhdetta ei haeta z-merkkijonosta, ja siihen lisätään viiva. Jos on identtisiä minimirelaatioita, mikä tahansa niistä valitaan. Jos kaikki resoluutiosarakkeen kertoimet ovat pienempiä tai yhtä suuria kuin 0, niin ongelman ratkaisu on ääretön.

Täytä seuraava taulukko “Iteraatio 1”. Saamme sen “Iteration 0” -taulukosta. Jatkomuunnosten tavoitteena on muuttaa x2-resoluutio-sarake yksikkösarakkeeksi (jossa on yksi resoluutioelementin sijaan ja nollia muiden elementtien sijaan).

1) Laske "Iteraatio 1" -taulukon rivi x 2. Ensin jaetaan kaikki "Iteraatio 0" -taulukon ratkaisevan rivin s 3 jäsenet tämän taulukon ratkaisevalla elementillä (tässä tapauksessa se on 1), saadaan rivi x 2 "Iteraatio 1" -taulukossa. . Koska ratkaiseva elementti on tässä tapauksessa yhtä suuri kuin 1, silloin "Iteraatio 0" -taulukon rivi s 3 osuu yhteen "Iteraatio 1" -taulukon rivin x 2 kanssa. Iteraatio 1 -taulukon rivi x 2 sai 0 1 0 0 1 20, loput Iteraatio 1 -taulukon rivit saadaan tästä rivistä ja Iteraatio 0 -taulukon rivit seuraavasti:

2) "Iteraatio 1" -taulukon z-rivin laskenta. Iteraatio 0 -taulukon sarakkeen x2 ensimmäisen rivin (z-rivi) -6:n sijasta Iteraatio 1 -taulukon ensimmäisellä rivillä tulee olla 0. Tätä varten kerrotaan kaikki taulukon "Iteraatio 1" rivin x 2 elementit 0 1 0 0 1 20 6:lla, saadaan 0 6 0 0 6 120 ja lisätään tämä rivi ensimmäiseen riviin (z - rivi) taulukosta "Iteraatio 0" -4 -6 0 0 0 0, saamme -4 0 0 0 6 120. Nolla 0 ilmestyy sarakkeeseen x 2, tavoite on saavutettu. Tarkkuussarakkeen x 2 elementit on korostettu punaisella.

3) "Iteraatio 1" -taulukon rivin s 1 laskeminen. "Iteraatio 0" -taulukon rivin 1 sijasta s 1 -taulukossa "Iteraatio 1" tulee olla 0. Voit tehdä tämän kertomalla taulukon "Iteraatio 1" rivin x 2 kaikki elementit 0 1 0 0 1 20 luvulla -1, saa 0 -1 0 0 -1 -20 ja lisää tämä rivi s 1 - rivillä taulukko "Iteraatio 0" 2 1 1 0 0 64, saamme rivin 2 0 1 0 -1 44. x 2 -sarakkeessa saadaan vaadittu 0.

4) Laske "Iteraatio 1" -taulukon rivi s 2. Taulukon "Iteraatio 0" rivin s 2 kohdassa 3 tulee olla 0 taulukossa "Iteraatio 1". Voit tehdä tämän kertomalla kaikki taulukon "Iteraatio 1" rivin x 2 elementit 0 1 0 0 1 20 luvulla -3, saamme 0 -3 0 0 -3 -60 ja lisää tämä rivi s 1 - rivillä taulukko "Iteraatio 0" 1 3 0 1 0 72, saamme rivin 1 0 0 1 -3 12. x 2 -sarakkeessa saadaan vaadittu 0 "Iteraatio 1" -taulukon sarakkeesta x 2 yksikkö, se sisältää yhden 1 ja loput 0.

Taulukon "Iteraatio 1" rivit saadaan seuraavan säännön mukaisesti:

Uusi rivi = Vanha rivi – (Vanhan rivin resoluutiosarakekerroin)*(Uusi resoluutiorivi).

Esimerkiksi z-merkkijonolle meillä on:

Vanha z-merkkijono (-4 -6 0 0 0 0) -(-6)*Uusi ratkaiseva merkkijono -(0 -6 0 0 -6 -120) =Uusi z-merkkijono (-4 0 0 0 6 120).

Seuraaville taulukoille taulukkoelementtien uudelleenlaskenta suoritetaan samalla tavalla, joten jätämme sen pois.

simpleksimenetelmän iteraatio 1

							Asenne

Ratkaisemalla sarakkeen x 1, ratkaisemalla rivin s 2, s 2 lähtee kannasta, x 1 tulee kantaan. Täsmälleen samalla tavalla saamme loput simpleksitaulukot, kunnes saamme taulukon, jossa on kaikki z-rivillä olevat positiiviset kertoimet. Tämä on merkki optimaalisesta pöydästä.

simpleksimenetelmän iteraatio 2

							Asenne

Ratkaisemalla sarakkeen s 3, ratkaisemalla rivin s 1, s 1 poistuu kannasta, s 3 tulee kantaan.

simpleksimenetelmän iteraatio 3

							Asenne

Z-rivillä kaikki kertoimet ovat ei-negatiivisia, joten saadaan optimaalinen ratkaisu x 1 = 24, x 2 = 16, z max = 192.

Yksinkertainen menetelmä on yhtälöjärjestelmän vaiheittainen suunnatun ratkaisun iteratiivinen prosessi, joka alkaa viiteratkaisulla ja parhaan vaihtoehdon etsimiseksi liikkuu toteutettavissa olevan ratkaisualueen kulmapisteitä pitkin parantaen tavoitefunktion arvoa, kunnes tavoitefunktio saavuttaa optimaalisen arvon.

Palvelun tarkoitus. Palvelu on suunniteltu lineaaristen ohjelmointiongelmien (LPP) online-ratkaisuun simplex-menetelmällä seuraavissa merkintämuodoissa:

• simpleksitaulukon muodossa (Jordan muunnosmenetelmä); perus tallennuslomake;
• modifioitu simpleksimenetelmä; sarakkeen muodossa; rivin muodossa.

Ohjeet. Valitse muuttujien määrä ja rivien määrä (rajoitusten määrä). Tuloksena oleva ratkaisu tallennetaan Word- ja Excel-tiedostoon.

Muuttujien lukumäärä 2 3 4 5 6 7 8 9 10
Rivien määrä (rajoitusten määrä) 1 2 3 4 5 6 7 8 9 10

Älä tässä tapauksessa ota huomioon rajoituksia, kuten x i ≥ 0. Jos tehtävässä ei ole rajoituksia jollekin x i:lle, ZLP on muutettava KZLP:ksi tai käytä tätä palvelua. Ratkaisun yhteydessä käyttö määräytyy automaattisesti M-menetelmä(yksinkertainen menetelmä keinotekoisella pohjalla) ja kaksivaiheinen simpleksimenetelmä.

Tämän laskimen kanssa käytetään myös seuraavia:
Graafinen menetelmä ZLP:n ratkaisemiseen
Ratkaisu kuljetusongelmaan
Matriisipelin ratkaiseminen
Verkkopalvelun avulla voit määrittää matriisipelin hinnan (ala- ja ylärajat), tarkistaa satulapisteen olemassaolon, löytää ratkaisun sekastrategiaan seuraavilla menetelmillä: minimax, simpleksimenetelmä, graafinen (geometrinen). ) menetelmä, Brownin menetelmä.
Kahden muuttujan funktion ääriarvo
Dynaamiset ohjelmointiongelmat
Jaa 5 homogeenista tavaraerää kolmen markkinoiden kesken saadaksesi mahdollisimman suuren tuoton niiden myynnistä. Myyntitulot kullakin markkinoilla G(X) riippuvat tuotteen X myytyjen erien määrästä ja esitetään taulukossa.

Tuotemäärä X (erissä)	Tulot 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

Yksinkertaisen menetelmän algoritmi sisältää seuraavat vaiheet:

1. Ensimmäisen perussuunnitelman laatiminen. Siirtyminen lineaarisen ohjelmointiongelman kanoniseen muotoon ottamalla käyttöön ei-negatiivisia lisätasapainomuuttujia.
2. Tarkistetaan suunnitelman optimaalisuutta. Jos vähintään yksi indeksiviivakerroin on pienempi kuin nolla, suunnitelma ei ole optimaalinen ja sitä on parannettava.
3. Johtavan sarakkeen ja rivin määrittäminen. Indeksirivin negatiivisista kertoimista valitaan absoluuttisesti suurin. Sitten simpleksitaulukon vapaan jäsensarakkeen elementit jaetaan alkusarakkeen saman merkin elementeiksi.
4. Uuden referenssisuunnitelman rakentaminen. Siirtyminen uuteen suunnitelmaan tapahtuu simpleksitaulukon uudelleenlaskennan tuloksena Jordan-Gauss-menetelmällä.

Jos tavoitefunktion ääripää on tarpeen löytää, niin puhutaan minimiarvon (F(x) → min, katso esimerkki funktion minimoinnin ratkaisusta) ja maksimiarvon ((F(x) ) → max, katso esimerkki ratkaisusta funktion maksimoimiseen)

Äärimmäinen ratkaisu saavutetaan toteuttamiskelpoisten ratkaisujen alueen rajalla polygonin kulmapisteiden yhdessä kärjessä tai kahden vierekkäisen kulmapisteen välisellä janalla.

Lineaarisen ohjelmoinnin peruslause. Jos ZLP-tavoitefunktio saavuttaa ääriarvon jossain vaiheessa toteuttamiskelpoisten ratkaisujen alueella, se ottaa tämän arvon kulmapisteestä. Jos ZLP-tavoitefunktio saavuttaa ääriarvon useammassa kuin yhdessä kulmapisteessä, se saa saman arvon missä tahansa näiden pisteiden kuperasta lineaarisesta yhdistelmästä.

Yksipuolisen menetelmän ydin. Siirtyminen optimipisteeseen tapahtuu siirtymällä yhdestä kulmapisteestä viereiseen, mikä tuo lähemmäksi ja nopeammaksi X opt:lle. Tällainen järjestelmä pisteiden laskemiseksi, kutsutaan simplex-menetelmäksi, ehdotti R. Danzig.
Kulmapisteille on ominaista m perusmuuttuja, joten siirtyminen kulmapisteestä viereiseen voidaan suorittaa muuttamalla vain yksi perusmuuttuja kannassa muuttujaksi ei-perustaiseksi.
Simplex-menetelmän toteutuksessa on LP-ongelmien eri ominaisuuksien ja muotoilujen vuoksi useita muunnelmia.

Simpleksipöytien rakentamista jatketaan, kunnes optimaalinen ratkaisu saadaan aikaan. Kuinka voit määrittää simpleksitaulukon avulla, että lineaarisen ohjelmoinnin ongelman ratkaisu on optimaalinen?
Jos viimeinen rivi (tavoitefunktion arvot) ei sisällä negatiivisia elementtejä, se löytää optimaalisen suunnitelman.

Huomautus 1. Jos yksi perusmuuttujista on nolla, niin tällaista perusratkaisua vastaava ääripiste on degeneroitunut. Degeneraatiota tapahtuu, kun ohjelinjan valinnassa on epäselvyyttä. Et ehkä huomaa ongelman rappeutumista ollenkaan, jos valitset toisen rivin oppaaksi. Epäselvyyksissä tulee valita rivi, jolla on alhaisin indeksi, jotta vältytään silmukalta.

Huomautus 2. Olkoot jossain ääripisteessä kaikki simpleksierot ei-negatiivisia D k ³ 0 (k = 1..n+m), ts. saadaan optimaalinen ratkaisu ja on olemassa A k - ei-perusvektori, jolle D k = 0. Tällöin maksimi saavutetaan ainakin kahdessa pisteessä, ts. vaihtoehtoinen optimi on olemassa. Jos lisäämme tämän muuttujan x k kantaan, tavoitefunktion arvo ei muutu.

Huomautus 3. Kaksoistehtävän ratkaisu on viimeisessä simpleksitaulukossa. Yksisuuntaisten erojen vektorin viimeiset m komponenttia (tasapainomuuttujien sarakkeissa) ovat optimaalinen ratkaisu kaksoisongelmaan. Suoran ja kaksoistehtävän tavoitefunktioiden arvot optimaalisissa kohdissa ovat samat.

Huomautus 4. Ratkaistaessa minimointitehtävää, kantaan lisätään vektori, jolla on suurin positiivinen simpleksiero. Seuraavaksi käytetään samaa algoritmia kuin maksimointitehtävässä.

Jos ehto ”Tyypin III raaka-aineet on kulutettava kokonaan” on määritelty, niin vastaava ehto on tasa-arvo.