Lineaaristen ohjelmointiongelmien eri kirjoitusmuodot.

Yleisessä tapauksessa lineaarinen ohjelmointitehtävä kirjoitetaan siten, että sekä yhtälöt että epäyhtälöt ovat rajoitteita ja muuttujat voivat olla sekä ei-negatiivisia että mielivaltaisesti muuttuvia. Siinä tapauksessa, että kaikki rajoitukset ovat yhtälöitä ja kaikki muuttujat täyttävät epänegatiivisuusehdon, lineaarista ohjelmointiongelmaa kutsutaan kanoniseksi. Se voidaan esittää koordinaatti-, vektori- tai matriisimerkinnällä.

1. Kanonisen lineaarisen ohjelmoinnin ongelma koordinaattimerkinnässä on muotoa

.

Kompaktissa muodossa tämä ongelma voidaan kirjoittaa käyttämällä summausmerkkiä,

(1.7)

2. Kanonisen lineaarisen ohjelmoinnin ongelma vektorimerkinnässä on muotoa

(1.8)

missä ,

.

3. Kanonisen lineaarisen ohjelmoinnin ongelma matriisimerkinnässä on muotoa

(1.9)

, .

Tässä A- yhtälöjärjestelmän kertoimien matriisi, X- ongelmamuuttujien matriisisarake, - rajoitusjärjestelmän oikeanpuoleinen matriisisarake.

Usein käytetään lineaarisia ohjelmointiongelmia nimeltä symmetrinen, joilla matriisimerkinnöissä on muoto

(1.10)

(1.11)

1.4 Yleisen lineaarisen ohjelmoinnin ongelman vähentäminen
kanoniseen muotoon

Useimmissa menetelmissä lineaarisen ohjelmoinnin ongelmien ratkaisemiseksi oletetaan, että rajoitusjärjestelmä koostuu yhtälöistä ja muuttujien ei-negatiivisuuden luonnollisista ehdoista. Talousongelmien matemaattisia malleja laadittaessa rajoitteet kuitenkin muodostuvat pääasiassa epätasa-arvojärjestelmiksi, joten on välttämätöntä pystyä siirtymään epäyhtälöjärjestelmästä yhtälöjärjestelmään. Tätä varten todistamme seuraavan lauseen.

Lause 1.1. Epäyhtälön korvaaminen yhtälöllä. Jokaiseen päätökseen epätasa-arvoa

yhtälölle vastaa ainutlaatuinen ratkaisu

ja eriarvoisuutta

, (1.14)

ja päinvastoin, yhtälön (1.13) ja epäyhtälön (1.14) jokaiselle ratkaisulle vastaa ainutlaatuinen epäyhtälön (1.12) ratkaisu.

Todiste. Päästää Onko ratkaisu epätasa-arvoon (1.12). Merkitsemme tämän epätasa-arvon oikean ja vasemman puolen välistä eroa ts.

Ilmeisesti ... Korvaamme yhtälössä (1.13) muuttujien sijaan arvot , saamme

Siten se täyttää yhtälön (1.13) ja epäyhtälön (1.14). Tämä tarkoittaa, että lauseen ensimmäinen osa on todistettu.

Toteuttakoon se yhtälö (1.13) ja epäyhtälö (1.14), eli meillä on

JA

Hylkäämällä ei-negatiivisen suuren viimeisen yhtälön vasemmalla puolella, saamme

eli tyydyttää epätasa-arvon (1,12). Lause on todistettu.

Jos epäyhtälö, niin sen vasemmalle puolelle on lisättävä ei-negatiivinen muuttuja miinusmerkillä, ts.

Ei-negatiivisia muuttujia, jotka on lisätty epätasa-arvorajoituksiin niiden muuntamiseksi yhtälöiksi kutsutaan lisämuuttujia... Lisämuuttujat lisätään tavoitefunktioon nollakertoimilla eivätkä siksi vaikuta sen arvoon.

Siinä tapauksessa, että ongelmassa on mielivaltaisesti muuttuvia muuttujia, mikä tahansa tällainen muuttuja korvataan kahden ei-negatiivisen muuttujan erolla, ts. , missä ja .

Joskus on välttämätöntä siirtyä ongelmaan minimin löytämisestä maksimin löytämiseen tai päinvastoin. Tätä varten riittää, kun muutetaan tavoitefunktion kaikkien kertoimien etumerkit päinvastaisiksi ja jätetään loput ongelmasta ennalleen. Tällä tavalla saadut maksimi- ja minimiongelmien optimaaliset ratkaisut ovat samat, ja optimaalisten ratkaisujen tavoitefunktioiden arvot eroavat vain etumerkistä.

Esimerkki 1.1. Tuo lineaarisen ohjelmoinnin ongelma kanoniseen muotoon.

Ratkaisu... Siirrytään ongelmaan tavoitefunktion maksimin löytämisestä. Tätä varten muutamme tavoitefunktiokertoimien etumerkkejä. Muuntaaksemme rajoitusjärjestelmän toisen ja kolmannen epäyhtälön yhtälöiksi otamme käyttöön ei-negatiiviset lisämuuttujat (matemaattisessa mallissa tämä operaatio on merkitty kirjaimella D). Muuttuja lisätään toisen epäyhtälön vasemmalle puolelle "+"-merkillä, koska epäyhtälöllä on muoto. Muuttuja lisätään kolmannen epäyhtälön vasemmalle puolelle "-"-merkillä, koska epäyhtälöllä on muoto. Muuttujat syötetään tavoitefunktioon kertoimella, joka on yhtä suuri kuin nolla. Muuttuja, joka ei ole ei-negatiivisuuden ehdon alainen, korvataan erolla , ... Ongelman kirjoittaminen kanonisessa muodossa

Joissakin tapauksissa on välttämätöntä pelkistää kanoninen ongelma symmetriseksi ongelmaksi. Katsotaanpa esimerkkiä.

Esimerkki 1.2. Muodosta lineaarisen ohjelmoinnin ongelma symmetriseen muotoon

Alkuperäisessä asetuksessa LPP:t voivat hyväksyä erilaisia ​​tallennusmuotoja. Joten joissakin tehtävissä tavoitefunktio on maksimoitava, toisissa - minimoitava; jotkut lineaariset rajoitukset voivat olla yhtäläisyyksien muodossa, toiset epätasa-arvoina ja niin edelleen.

LPP-tietueen yhtenäisyyden vuoksi ns kanoninen muoto levyjä.

He sanovat, että ZLP on kirjoitettu kanonisessa muodossa, jos sillä on seuraava muoto:

Huomaa seuraavat kanonisen muodon ominaisuudet:

1) tavoitefunktiota vaaditaan minimoimaan;

2) kaikki lineaariset rajoitukset, lukuun ottamatta vaatimusta muuttujien ei-negatiivisuudesta, ovat yhtäläisyyksiä;

kaikkiin muuttujiin sovelletaan ei-negatiivisuusvaatimuksia.

Osoittakaamme, että mikä tahansa LPP voidaan pelkistää kanoniseen muotoon.

1) Jos LPP:ssä tavoitefunktion f on maksimoitava, laitetaan g = - f ja vaativat funktion g minimoimista. Saamme uuden LPP:n, joka vastaa alkuperäistä siinä mielessä, että jokainen optimaalinen ratkaisu alkuperäiseen ongelmaan on optimaalinen ratkaisu uudelle ongelmalle ja päinvastoin.

2) Oletetaan, että LPP:llä on muodon lineaarinen rajoitus

Korvaamme tämän rajoitteen seuraavilla kahdella rajoituksella:

missä z - uusi muuttuja, joka lisätään tavoitefunktioon kertoimella 0 (eli muuttujaa z ei syötetä tavoitefunktioon). Z-muuttujan arvo voidaan jättää huomioimatta, kun uusi ongelma on ratkaistu.

Samalla tavalla näkymärajoitus korvataan kahdella rajoituksella:

3) Oletetaan, että LPP:ssä kaikkien muuttujien ei vaadita olevan ei-negatiivisia. Sitten jokainen muuttuja , jolle ei ole asetettu ei-negatiivisuusvaatimusta, voidaan esittää kahden ei-negatiivisen muuttujan erotuksena:

Jokainen muuttujan esiintyminen kohdefunktioon tai rajoituksiin, korvaamme eron
... Kun uusi ongelma on ratkaistu (2.6) avulla, palataan aikaisempiin muuttujiin.

Ilmoitetuilla tekniikoilla mikä tahansa LPP pelkistetään kanoniseen muotoon.

Esimerkki. Tuo kanoniseen muotoon

Suoritetaan kuvatut toimet.

Nyt saamme ZLP:n kanonisessa muodossa:

2.7. Perussuunnitelman käsite zlp.

Olkoon ILP annettu kanonisessa muodossa (2.3 - 2.5). Oletetaan, että yhtälöjärjestelmä (2.4) pelkistetään Jordanin muotoon, jossa on ei-negatiiviset oikeat sivut:

(2.6)

missä
.

Vertaamalla vapaat muuttujat nollaan saadaan järjestelmän (2.4) perusratkaisu.

Tilanteesta johtuen
muuttujien arvojen joukko (2.7) täyttää myös rajoitukset (2.5). Siksi (2.6) on LPP:n hyväksyttävä päätös.

Toteutettava ratkaisu (2.7) kutsutaan perushyväksyttävä päätös tai ZLP:n perussuunnitelma. Samaan aikaan he sanovat, että muuttujat
muodostavat hyväksyttävän perustan.

Osoittautuu, että jos ODR on kuvattu geometrisesti, niin jokainen ZLP:n tukisuunnitelma vastaa monitahoisen kärkeä. Siksi seuraava lause on totta.

Jos LPP on ratkaistavissa, on olemassa optimaalinen tukisuunnitelma.

3. Yksinkertainen menetelmä zlp:n ratkaisemiseen

3.1. Simpleksimenetelmän yleiset ominaisuudet ja päävaiheet

Simplex-menetelmän perustajat ovat Neuvostoliiton matemaatikko L.V. Kantorovich ja amerikkalainen matemaatikko J. Danzig.

Mikä tahansa LPP voidaan ratkaista simplex-menetelmällä tai sen ratkaisemattomuus voidaan havaita. Monet LPP:n erikoisluokat voidaan ratkaista muilla menetelmillä, jotka ovat tehokkaampia näille luokille. Simplex-menetelmän etuna on kuitenkin sen monipuolisuus. Lähes kaikkiin tietokoneisiin on kehitetty standardiohjelmia LPP:n ratkaisemiseksi simplex-menetelmällä.

Kuvataanpa simplex-menetelmän yleistä ideaa.

Oletamme, että LPP on kirjoitettu kanonisessa muodossa ja tavoitefunktio on minimoitava. Kuten jo tiedämme, optimaalinen suunnitelma tulisi etsiä LPP:n tukisuunnitelmista. Simpleksimenetelmä ei iteroi kaikkia perussuunnitelmia (mikä olisi usein mahdotonta niiden valtavan määrän vuoksi), vaan jostain alkuperäisestä perussuunnitelmasta lähtien se siirtyy peräkkäin muihin perussuunnitelmiin tavoitefunktion pienentyessä. Simplex-menetelmä lakkaa toimimasta, kun joko optimaalinen perussuunnitelma löydetään tai ongelman havaitaan olevan ratkaisematon.

Kun LPP ratkaistaan ​​simplex-menetelmällä, voidaan erottaa seuraavat vaiheet:

1) LPP:n saattaminen kanoniseen muotoon;

2) lineaariyhtälöjärjestelmän pelkistäminen Jordanin muotoon, jossa on ei-negatiiviset oikeat puolet, samalla kun LPP:n ratkaisemattomuus tarkistetaan lineaaristen rajoitteiden järjestelmän epäjohdonmukaisuuden vuoksi;

3) optimaalisuuden perussuunnitelman tutkimus;

4) LPP-selvitys tavoitefunktion ODR:n alhaalta rajoittumattomuudesta johtuvan ratkaisemattomuuden varalta;

5) siirtyminen uuteen, "parempaan" vertailusuunnitelmaan.

Analyyttinen menetelmä lineaarisen ohjelmoinnin ongelman ratkaisemiseksi on simplex menetelmä. Sen soveltamiseksi eri tavoilla esitetyt LP-ongelmat on pelkistettävä kanoniseen muotoon. Lineaarinen ohjelmointitehtävä, joka on kirjoitettu muotoon (2.1.1) - (2.1.3), on laajennettu muoto yleisen lineaarisen ohjelmoinnin ongelman (LPP) kirjoittamisesta.

Seuraavaa ongelmaa kutsutaan kanoniseksi lineaariseksi ohjelmointiongelmaksi (LCPP):

tasa-arvon muodossa olevien rajoitusten alaisena,

Jos ongelma muodossa (2.3.1) - (2.3.4) täyttää ehdon m = n, sitten sen ratkaisu pelkistetään yhtälöjärjestelmän ratkaisemiseksi

• (2.3.2). Tässä tapauksessa ongelmalla ei ole ratkaisuja, jos ehto
• (2.3.3) ei täyty tai yhtälöjärjestelmällä ei ole ratkaisua.

kunto T

• 1. Mennä maksimointitehtävästä tavoitefunktio (2.3.1) to minimointiongelma tarpeeksi ota kaikki kertoimet Cj tavoitefunktio käänteisillä merkeillä ja ratkaise tuloksena oleva ongelma mahdollisimman paljon. Kun maksimi on löydetty, kohdefunktion arvo on otettava päinvastaisella etumerkillä. Optimaalinen ratkaisu pysyy samana.
• 2. Mennä rajoituksista, kuten "pienempi tai yhtä suuri" tasa-arvoon se tarvitsee plusmerkillä:

3. Mennä "suuremmasta tai yhtä suuresta" rajoituksesta tasa-arvoon se tarvitsee lisää ei-negatiivinen muuttuja miinusmerkillä:

Tässä tapauksessa jokainen epätasa-arvo tuo omansa (n +/) - Olen lisämuuttuja.

• 4. Kaikki yhtäläiset negatiiviset vapaat termit jaetaan-1, jotta ehto (2.3.4) täyttyy.
• 5. Jos jollekin muuttujalle Xj ei-negatiivisuusehtoa ei määrätä, sitten tee muuttujien muutos Xj = x ".- X" x "j> 0, x "> 0. Muunnetussa tehtävässä kaikki muuttujat eivät ole negatiivisia.

Väitetään, että mikä tahansa LPP voidaan pelkistää kanoniseen muotoon.

Esimerkki 2.3.1. Muunnetaan esimerkissä 2.2.2 annettu ongelma kanoniseen muotoonsa. Tavoitefunktio ja rajoitusjärjestelmä ovat seuraavat:

Lisäämme ensimmäiseen epäyhtälöön lisämuuttujan jc 3> 0 plus-merkillä, toiseen x 4> 0 miinusmerkillä ja kolmannessa x 5> 0 myös plusmerkillä. Tuloksena saadaan ongelmalle kanonisessa muodossa oleva rajoitusjärjestelmä:

Näillä rajoituksilla sinun on löydettävä funktion enimmäisarvo:

Tarkastellaanpa lisämuuttujien taloudellista merkitystä resurssien optimaalisen käytön kanonisessa ongelmassa.

Esimerkki 2.3.2. Resurssien optimaalinen käyttö (mattoongelma)[17 J.

Tehtaalla on käytössään tietty määrä kolmenlaisia ​​resursseja: työvoimaa (80 työpäivää), raaka-aineita (480 kg) ja laitteita (130 työstötuntia). Tehdas pystyy valmistamaan neljää erityyppistä mattoa. Taulukossa on tiedot kunkin maton valmistukseen tarvittavien resurssien yksiköiden määrästä ja yrityksen kunkin tavaralajin yksiköstä saamista tuloista. 2.3.1.

On löydettävä sellainen tuotantosuunnitelma, jossa sen kokonaiskustannukset ovat maksimi.

Ongelman taloudellinen ja matemaattinen malli Muuttujat: x x, x 2, x 3, x 4 - kunkin tyyppisten mattojen lukumäärä. Objektiivinen toiminto - tämä on maksimoitava kokonaistuotantokustannus:

Resurssirajoitukset:

Muodostetaan ongelma kanoniseen muotoon ottamalla käyttöön lisämuuttujia x 5, x 6 ja x 7:

Lisäksi osoitetaan, että optimaalinen tuotantosuunnitelma on vektori X * =(0; 30; 10; 0), tavoitefunktion arvo on 150, ts. kokonaistuotannon kustannusten maksimoimiseksi on tarpeen valmistaa 30 toisen tyypin mattoa ja 10 kolmannen tyyppistä mattoa. Korvaa vektorin optimaaliset arvot X KZLP:n rajoituksissa:

Saamme, että resurssit "työvoima" ja "laitteet" käytetään täysimääräisesti, resursseja "raaka-aineita" on runsaasti:

Tässä tapauksessa x sisään osoittaa, että raaka-ainetta on jäljellä 200 kg.

Päämuuttujat siis x v x 2, x 3, x l tarkoittaa kunkin tyyppisten mattojen määrää ja muita muuttujia x 5, x 6 niiden 7 - käyttämättömien resurssien määrä.

Vastaus. Optimaalinen tuotantosuunnitelma X * = (0; 30;

10; 0).

Suunnitelma, tai hyväksyttävä päätös, KZLP:tä kutsutaan vektoriksi X =(jc s X 2 ,..., x n) täyttävät ehdot (2.3.2) - (2.3.4).

Jos kaikki KZLP:n rajoitusjärjestelmän perusratkaisun komponentit ovat ei-negatiivisia, niin tällainen ratkaisu on ns. viitepäätös tai perussuunnitelma. Viitesuunnitelman positiivisten komponenttien määrä ei saa ylittää T.

Perussuunnitelma on ns ei rappeutunut, jos se sisältää T positiivisia komponentteja, muuten sitä kutsutaan rappeutunut.

Optimaalinen suunnitelma tai optimaalinen ratkaisu LPP:tä kutsutaan suunnitelmaksi, joka tuottaa suurimman (pienimmän) arvon lineaarista funktiota (2.3.1).

Kaikkien LPP-suunnitelmien joukko (jos sellaisia ​​on) on kupera monitahoinen. Ratkaisujen polyhedronin jokaista kulman (ääripisteen) pistettä vastaa perussuunnitelma(KZLP-yhtälöjärjestelmän ei-negatiiviset perusratkaisut). Järjestelmä määrittää jokaisen perusviivan T tämän järjestelmän sisältämät lineaarisesti riippumattomat vektorit alkaen P vektorit Д, Д, ..., A p. Jos on optimaalinen rakenne, niin ratkaisupolytoopin kulmapisteessä lineaarifunktio saavuttaa suurimman (pienimmän) arvonsa.

Optimaalisen suunnitelman löytämiseksi riittää, että tutkit vain tukisuunnitelmat. Tehtävän sisältämien referenssisuunnitelmien yläraja määräytyy yhdistelmien lukumäärän mukaan C t s (katso kohta 1.4).

Esimerkki 2.3.3. Hanki ratkaisu rajallisten resurssien optimaalisen käytön ongelmaan (ratkaise LP P):

Ratkaisu. Pelkistetään ongelma kanoniseen muotoon ottamalla käyttöön lisämuuttujia x 3, x 4 ja x 5:

Etsitään kaikki tämän KZLP:n rajoitusjärjestelmän tukisuunnitelmat (l? - 5; / 77 - 3); niiden lukumäärä ei ylitä 10:tä:

Jordan - Gaussin menetelmällä (katso kohta 1.4) kirjoitetaan kaikki yhtälöjärjestelmän perusratkaisut (taulukko 2.3.2).

Kymmenen perusratkaisun joukossa on viisi perusratkaisua:

Kuvassa ilmoitetut referenssisuunnitelmat. 1 vastaavat seuraavia kulmapisteitä ja niissä olevia CF:n arvoja:

Riisi. 2.3.1.

Teorian mukaan LP optimaalinen ratkaisu sisältyy referenssisuunnitelmiin.

Siten tavoitefunktio saavuttaa maksimiarvon, joka on yhtä suuri kuin 2300 pisteessä V vertailutasolla X 5 = (70; 80; 0; 60; 0).

Vastaus. Optimaalinen tehtäväsuunnitelma: x (= 70, x 2 = 80, tavoitefunktion arvo f (x v x 2) = 2300.

kanoninen muoto, jos tavoitefunktion maksimointi vaaditaan, kaikki järjestelmän rajoitukset ovat yhtälöitä ja ei-negatiivisuusehto on asetettu kaikille muuttujille.

Lineaarisen ohjelmoinnin ongelma on annettu symmetrinen muoto, jos tavoitefunktion maksimointi vaaditaan, kaikki järjestelmän rajoitukset ovat epäyhtälöitä "" (tai tavoitefunktion minimoimiseksi kaikki järjestelmän rajoitukset ovat epäyhtälöitä "") ja ei-negatiivisuusehto on asetettu kaikille muuttujille.

Numerojoukkoa kutsutaan hyväksyttävä päätös (suunnitelma) jos se täyttää LPP-rajoitusjärjestelmän.

Kaikkien mahdollisten ratkaisujen joukkoa kutsutaan toteuttamiskelpoisten ratkaisujen alue(ODR).

Kutsutaan toteuttamiskelpoinen ratkaisu, jolla saavutetaan funktion maksimi (minimi) arvo LPP:n optimaalinen suunnitelma.

Termit "suunnitelma" ja "optimaalinen suunnitelma" syntyivät taloudellisista sovelluksista.

Kaikki kolme LPP-merkintämuotoa ovat samanarvoisia siinä mielessä, että on olemassa algoritmeja siirtymiseen muodosta toiseen. Jos siis on olemassa tapa ratkaista ongelma jossakin muodossa, voit aina määrittää optimaalisen suunnitelman missä tahansa muussa muodossa esitetylle ongelmalle. Symmetrisessä muodossa oleva ongelma ratkaistaan ​​graafisella menetelmällä ja kanonisessa muodossa - simplex-menetelmällä.

Tarkastellaan algoritmeja muodosta toiseen siirtymiseen.

• 
  Symmetrinen  kanoninen. Siirtyminen suoritetaan lisäämällä ylimääräinen ei-negatiivinen muuttuja kunkin epäyhtälön vasemmalle puolelle. Jos epäyhtälö oli “≤”, saldomuuttuja lisätään epäyhtälön vasemmalle puolelle “+”-merkillä. Jos epäyhtälö oli "", saldomuuttuja lisätään epäyhtälön vasemmalle puolelle "-"-merkillä. Esitetyt uudet muuttujat ovat ns tase... Funktion Z minimointiongelma korvataan funktion maksimointiongelmalla (–Z) ja käytetään, että min Z = –max (–Z).
• 
  Kanoninen  symmetrinen. Tällaisen siirtymän toteuttamiseksi löydetään yhtälöjärjestelmän yleinen ratkaisu - rajoitteet, tavoitefunktio ilmaistaan ​​vapaina muuttujina. Edelleen käyttämällä perusmuuttujien ei-negatiivisuutta, ne voidaan jättää ongelman ulkopuolelle. Tehtävän symmetrinen muoto sisältää epäyhtälöitä, jotka koskevat vain vapaita muuttujia, ja tavoitefunktion, joka riippuu vain vapaista muuttujista. Perusmuuttujien arvot löytyvät alkuperäisen yhtälöjärjestelmän yleisestä ratkaisusta.
• 
  Yleinen  kanoninen. Jokainen muuttuja, joka ei ole ollut ei-negatiivisuuden ehdon alainen, esitetään kahden uuden ei-negatiivisen muuttujan erotuksena. Epäyhtälöt muunnetaan yhtälöiksi ottamalla kunkin epäyhtälön vasemmalle puolelle tasapainomuuttuja samalla tavalla kuin on kuvattu siirtymisessä symmetrisestä kanoniseen muotoon. Funktion Z minimointiongelma korvataan funktion (–Z) maksimoimisen ongelmalla samalla tavalla kuin kuvattiin siirryttäessä symmetrisestä kanoniseen muotoon.

1. Graafinen menetelmä lineaarisen ohjelmoinnin ongelman ratkaisemiseksi

Pisteiden joukkoa kutsutaan kupera jos se sisältää joukon jollekin kahdelle pisteelle niitä yhdistävän janan.

Esimerkki 1

Seuraavat pistejoukot tasossa ovat kuperia:

Seuraavat tason pistejoukot eivät ole kuperia:

Lause 1 Minkä tahansa määrän kupera joukkojen leikkauspiste on kupera joukko.

Lause 2 Olkoon kaksi mielivaltaista pistettä ja avaruudessa R n... Sitten janan mille tahansa pisteelle [ PQ] on suoritettava:. missä.

Hypertaso avaruudessa R n on joukko pisteitä, jotka täyttävät yhtälön. Huomaa, että kaksiulotteisessa tapauksessa hypertaso on suora.

Puoliväli on joukko pisteitä, jotka täyttävät yhden epäyhtälöistä tai. Hypertaso jakaa avaruuden pisteet kahteen puoliavaruuteen. Kaksiulotteisessa tapauksessa hypertaso on puolitaso.

Lause 3 Puoliavaruus on kupera joukko.

Seuraus Minkä tahansa lukumäärän puolivälien leikkauspiste on kupera joukko.

Polyhedron kutsutaan yhden tai useamman puoliavaruuden leikkauskohtaa. Monitahoista kaksiulotteisessa tapauksessa kutsutaan monikulmioksi.

Esimerkki 2

Seuraavat joukot ovat polygoneja.

Rajoitettu sarja

Rajoittamaton sarja

Yksittäinen piste

Tyhjä setti

Konveksin joukon pistettä kutsutaan kulmikas jos se ei ole missään janassa, joka yhdistää kaksi muuta pistettä joukosta.

Esimerkki 3

Kolmion kulmapisteet ovat sen kärjet (niitä on kolme). Ympyrän kulmapisteet ovat sitä rajoittavan ympyrän pisteet (niitä on ääretön määrä).

Monitahoisen kulmapistettä kutsutaan nimellä huippu.

Tarkastellaan symmetrisessä muodossa annettua LPP:tä.

Lause 4 LPP:n optimaalinen rakenne vastaa sen rajoitusjärjestelmän määräämää ratkaisupolytoopin kärkeä.

Lineaarinen ohjelmointitehtävä muotoa ax = b, jossa a on kertoimien matriisi, b on rajoitteiden vektori.
Esimerkki:

Jokaisessa LP-ongelmassa etsitään muuttujien arvoja sillä ehdolla, että:

• nämä arvot täyttävät tietyn lineaarisen yhtälö- tai epäyhtälöjärjestelmän;
• näillä arvoilla tavoitefunktio olisi minimissä tai maksimissa.

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

Yksi universaaleista LP-menetelmistä on simplex-menetelmä, jota voidaan kuitenkin soveltaa, jos LP-ongelmalla on kanoninen muoto.

Määritelmä... LP-ongelmalla on kanoninen muoto, jos kaikki järjestelmän rajoitukset koostuvat vain yhtälöistä (paitsi muuttujien ei-negatiivisuutta ilmaisevat epäyhtälöt) ja tavoitefunktio on minimoitava.
Esimerkki tällaisesta LP-ongelmasta kanonisessa muodossa on ongelma 1 - tasapainoinen kuljetusongelma rajoitteiden järjestelmällä (1) ja tavoitefunktiolla (2).
Useimmissa taloudellisissa ongelmissa rajoitusjärjestelmä sisältää kuitenkin useimmiten aluksi yhtälöiden lisäksi myös epätasa-arvoa.

lausunto. Mikä tahansa yleinen LP-ongelma voidaan pelkistää kanoniseen muotoon.
Yleisen LP-ongelman pelkistäminen kanoniseen muotoon saavutetaan ottamalla käyttöön uusia (niitä kutsutaan lisämuuttujiksi).
Tämän ongelman rajoitusjärjestelmä (3) koostuu neljästä epäyhtälöstä. Ottamalla käyttöön lisämuuttujia y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0, y 4 ≥ 0, voit siirtyä rajoitusjärjestelmään:

Nämä lisämuuttujat y minulla on täysin selvä taloudellinen merkitys, eli ne tarkoittavat käyttämättömän käyttöajan määrää (koneen seisokkiaika i-th tyyppi).
Esimerkiksi jos ensimmäisen tyypin koneet työskentelivät kaikki 18 tuntia, niin x + y = 18, joten y 1 = 0. Mutta myönnämme mahdollisuuden ensimmäisen koneen käyttöajan epätäydelliseen käyttöön. x + y<18. В этом случае y 1 muuttuu positiiviseksi ja sitä voidaan pitää käyttämättömänä aikarajana. Esimerkiksi, kun tiedät ratkaisun tähän ongelmaan kohdasta 3.3.2, x = 12, y= 6, voimme päätellä rajoitusjärjestelmästä (3.9), että y 1 = y 2 = y 3 = 0 ja y 4 = 12 - 6 = 6. Eli ensimmäisen, toisen, kolmannen tyypin koneet käyttävät työaikansa täysimääräisesti. Mutta neljäs auto on vain puoliksi lastattu, 6 tuntia, ja se on tyhjäkäynnillä annetulla optimaalisella suunnitelmalla. Ehkä tällaisten johtopäätösten jälkeen yrityksen johtaja haluaa ladata sen muilla töillä, vuokrata sen tälle ajalle jne.
Joten ottamalla käyttöön lisämuuttujia, voimme pelkistää kaikki epäyhtälötyyppiset rajoitukset yhtälöksi.

Harkitse sekoitusongelmaa. Rajoitusjärjestelmä on seuraava:
Epäyhtälöt suunnattiin kohti ”enemmän”, joten lisämuuttujat y 1, y 2, y 3 ≥ 0 ottamalla käyttöön ne on vähennettävä vasemmalta puolelta, jotta se tasataan oikean kanssa. Saamme rajoitusjärjestelmän kanonisessa muodossa:
Muuttujat y i ovat myös taloudellisesti järkeviä. Jos muistat ongelman käytännön sisällön, muuttuja y 1 tarkoittaa ylimääräisen aineen A määrää seoksessa, y 2 - ylimääräisen aineen määrää V seoksessa, y 3 - ylijäämä KANSSA seoksessa.
Tavoitefunktion maksimiarvon löytämisen ongelma voidaan pelkistää funktion minimiarvon löytämiseen - F koska väite on ilmeinen, max F = –min (- F). Katso kuvaa: jos jossain vaiheessa x= x 0 toiminto y= F(x) saavuttaa maksiminsa, sitten funktio y= –F(x), symmetrinen sille akselin ympäri HÄRKÄ, samassa kohdassa x 0 saavuttaa minimin ja F max = - (- F min) klo x = x 0 .

Johtopäätös. LP-ongelman esittämiseksi kanonisessa muodossa on välttämätöntä:

• ongelman rajoitusjärjestelmään sisältyvät epätasa-arvot muunnetaan yhtälöiksi ottamalla käyttöön lisämuuttujia;
• jos tavoitefunktio F→ max (maksimoitu), se korvataan funktiolla - F→ min (joka on minimoitu).