Kratka teorija
Linearno programiranje je grana matematičkog programiranja koja se koristi u razvoju metoda za pronalaženje ekstrema linearnih funkcija više varijabli sa linearnim dodatnim ograničenjima na varijable. Prema vrsti zadataka koje treba riješiti, njegove metode se dijele na univerzalne i posebne. Bilo koji problem linearnog programiranja (LPP) može se riješiti korištenjem univerzalnih metoda. Posebne metode uzimaju u obzir posebnosti modela problema, njegovu ciljnu funkciju i sistem ograničenja. Karakteristika problema linearnog programiranja je da ciljna funkcija dostiže svoj ekstrem na granici područja izvodljivih rješenja.
Grafička metoda za rješavanje problema linearnog programiranja omogućava vizualizaciju njihove strukture, identifikaciju karakteristika i otvaranje načina za proučavanje složenijih svojstava. Problem linearnog programiranja s dvije varijable uvijek se može riješiti grafički. Međutim, već u trodimenzionalnom prostoru takvo rješenje postaje komplikovanije, a u prostorima čija je dimenzija veća od tri grafičko rješenje je, općenito govoreći, nemoguće. Slučaj dvije varijable nema poseban praktični značaj, ali njegovo razmatranje pojašnjava svojstva LPP ograničenja, dovodi do ideje o njegovom rješavanju, čini geometrijski jasne načine rješavanja i načine njihove praktične implementacije.
Ako ograničenja i ciljna funkcija sadrže više od dvije varijable, onda je potrebno (ili metodom sekvencijalnog poboljšanja rješenja) - univerzalno je i može se koristiti za rješavanje bilo kojeg LPP-a. Za neke primijenjene probleme linearnog programiranja, kao što su, razvijene su posebne metode rješenja.
Primjer rješavanja problema
Zadatak
Preduzeće proizvodi dvije vrste proizvoda: Proizvod 1 i Proizvod 2. Za proizvodnju jedinice proizvoda 1 potrebno je potrošiti kg sirovina prve vrste, kg sirovina druge vrste, kg sirovina materijala treće vrste. Za proizvodnju jedinice proizvoda 2 potrebno je potrošiti kg prve vrste, sirovina druge vrste, sirovina treće vrste. Proizvodnja je obezbeđena sirovinama svake vrste u količini od kg, kg, kg, respektivno. Tržišna cijena jedinice proizvoda 1 je hiljadu rubalja, a jedinice proizvoda 2 je hiljada rubalja.
Obavezno:
- Izgradite matematički model problema.
- Grafičkom metodom za rješavanje problema linearnog programiranja izraditi plan proizvodnje proizvoda koji obezbjeđuje maksimalan prihod od njihove prodaje.
Kako bi rješenje problema linearnog programiranja bilo što preciznije i tačnije, mnogi jeftino naručuju test na ovoj stranici. Više detalja (kako ostaviti upit, cijene, uslove, način plaćanja) možete pročitati na testu Kupi linearno programiranje...
Rješenje problema
Izgradnja modela
Kroz i označavamo broj proizvedenih proizvoda 1. i 2. tipa.
Tada su ograničenja resursa:
Osim toga, u smislu problema
Ciljna funkcija ekonomsko-matematičkog modela, koja izražava prihod od prodaje:
Dobijamo sljedeći ekonomsko-matematički model:
Izgradnja regiona izvodljivih rješenja
Rešimo rezultujući problem linearnog programiranja grafički:
Da bismo konstruirali područje izvodljivih rješenja, konstruiramo u koordinatnom sistemu granične linije koje odgovaraju ovim ograničenjima nejednakosti:
Nađimo tačke kroz koje prolaze prave:
Rješenje svake nejednakosti LPP sistema ograničenja je poluravnina koja sadrži graničnu liniju i nalazi se na jednoj njenoj strani.
Da biste definirali poluravninu, uzmite bilo koju tačku, na primjer, koja ne pripada pravoj liniji (1), zamijenite koordinate (0; 0) u odgovarajuću nejednačinu. Jer tačna je nejednakost:
Domen rješenja odgovarajuće 1. nejednačine odgovara lijevoj poluravni
Uzmite bilo koju tačku, na primjer, koja ne pripada pravoj liniji (2), zamijenite koordinate (0; 0) u odgovarajuću nejednačinu. Jer tačna je nejednakost:
Uzmite bilo koju tačku, na primjer, koja ne pripada pravoj liniji (3), zamijenite koordinate (0; 0) u odgovarajuću nejednačinu. Jer tačna je nejednakost:
Domen rješenja odgovarajuće 2. nejednačine odgovara lijevoj poluravni
Područje prihvatljivih rješenja je broj.
Pronalaženje rješenja za LP problem
Gradimo vektor čije su koordinate proporcionalne koeficijentima funkcije cilja. Evo koeficijenta proporcionalnosti.
Nacrtajte ravninu okomitu na konstruisani vektor.
Pomaknite liniju nivoa u smjeru vektora tako da dodirne područje izvodljivih rješenja u krajnjoj tački. Rješenje maksimuma je tačka čije se koordinate nalaze kao tačka presjeka pravih (2) i (1).
Odgovori
Dakle, potrebno je proizvesti 56 artikala 1. vrste i 64 artikla 2. vrste. U ovom slučaju prihod od prodaje proizvoda će biti maksimalan i iznosi 5104 novčane jedinice.
Metoda grafičkog rješenja, ako problem s dvije varijable ima linearna ograničenja, a ciljna funkcija je kvadratna, detaljno se razmatra ovdje
Stranica detaljno opisuje rješenje problema linearnog programiranja korištenjem simpleks metode, osim toga prikazuje konstrukciju problema dualnog linearnog programiranja i pronalaženje njegovog rješenja rješavanjem direktnog problema.
Transportni problem i metoda potencijala
Detaljno se razmatra transportni problem, njegov matematički model i metode rješavanja - pronalaženje referentnog plana metodom minimalnih elemenata i pronalaženje optimalnog rješenja metodom potencijala.
Konveksno programiranje - grafička metoda
Prikazan je primjer rješavanja problema kvadratnog konveksnog programiranja grafičkom metodom.
U ovoj lekciji ćemo se upoznati sa grafičkom metodom rešavanja problemi linearnog programiranja, odnosno takvi problemi u kojima se traži rješenje za sistem linearnih jednačina i (ili) nejednačina (sistem ograničenja) u kojima ciljna funkcija - linearna funkcija - poprima optimalnu vrijednost.
Zbog činjenice da se jasnoća grafičkog rješenja postiže samo na ravni, grafički prikaz problema možemo se upoznati samo u dvodimenzionalnom prostoru. Ovaj prikaz je prikladan za sistem ograničenja nejednakosti sa dvije varijable ili za sisteme jednačina u kojima je broj varijabli 2 veći od broja jednačina, odnosno broj slobodnih varijabli je dvije.
Dakle, grafička metoda ima toliko uzak opseg primjene da se o njoj ne može govoriti kao o posebnoj metodi za rješavanje problema linearnog programiranja.
Međutim, za razvoj vizuelnih reprezentacija rješenja problema linearnog programiranja, grafička metoda je od određenog interesa. Osim toga, omogućava vam da geometrijski potvrdite valjanost teoreme linearnog programiranja .
Teorijske osnove grafičke metode
Dakle, problem linearnog programiranja. Potrebno je pronaći nenegativne vrijednosti varijabli i zadovoljiti sistem nejednačina
pri kojoj linearni oblik poprima optimalnu vrijednost.
Primjer 3.
Primjer 4. Grafički riješiti problem linearnog programiranja u kojem je potrebno pronaći minimum funkcije pod ograničenjima
Zajedno nastavljamo grafički rješavati probleme
Do sada su se nalazi temeljili na činjenici da je skup rješenja za problem linearnog programiranja konfiguriran tako da je optimalno rješenje konačno i jedinstveno. Pogledajmo sada primjere kada je ovaj uvjet prekršen. U ovim primjerima, poligon odlučivanja je konstruiran kao što je prikazano u prethodnim primjerima, ali hajde da se zadržimo na karakteristikama koje razlikuju ove izuzetne primjere.
Primjer 5. Grafički riješiti problem linearnog programiranja u kojem je potrebno pronaći maksimum funkcije pod ograničenjima
Rješenje. Na slici je prikazano: neograničeno višestruko područje rješenja ovog sistema ograničenja, linija početnog nivoa (crna), vektor (bordo) koji pokazuje smjer kretanja linije početnog nivoa za pronalaženje maksimuma ciljne funkcije.
Lako je vidjeti da je funkcija F može neograničeno rasti za dati sistem ograničenja, tako da to možemo uslovno napisati.
Primjer 6. Grafički riješiti problem linearnog programiranja u kojem je potrebno pronaći maksimum funkcije pod ograničenjima
Najjednostavniji i najintuitivniji metod linearnog programiranja (LP) je grafički metod. Koristi se za rješavanje LP problema sa dvije varijable. Razmotrite LP problem u standardnom obliku:
max f (x 1 , x 2, ..., x n) = ,
, i = 1, 2, ..., m,
x j 0, j = 1, 2,…, n.
Mi smo stavili n = 2 a problem ćemo razmotriti u avionu. Neka je sistem nejednačina konzistentan (ima barem jedno rješenje).
Svaka nejednakost ovog sistema geometrijski definira poluravninu sa graničnom linijom a i 1 x 1 + a i 2 x 2 = b i, i = 1, 2, …, m. Uslovi nenegativnosti definišu poluravnine sa graničnim linijama x 1 = 0, x 2 = 0, respektivno. Sistem je kompatibilan, dakle, poluravnine, pošto konveksni skupovi, seku, čine zajednički deo, koji je konveksan skup i predstavlja skup tačaka, gde su koordinate svake tačke rešenje ovog sistema. Skup ovih tačaka naziva se poligon odluke. To može biti tačka, prava, zraka, ograničeni i neograničeni poligon.
Dakle, geometrijski, LPP je potraga za takvom tačkom poligona rješenja, čije koordinate daju maksimalnu (minimalnu) vrijednost linearnoj funkciji cilja, a sve točke poligona rješenja su izvodljiva rješenja.
Linearna jednačina opisuje skup tačaka koje leže na jednoj pravoj liniji. Linearna nejednakost opisuje određeno područje u ravnini. Odredimo koji dio ravnine opisuje nejednakost 2x 1 + 3x 2 12.
Prvo konstruirajte pravu 2x 1 + Zx 2= 12. Prolazi kroz tačke (6; 0) i (0; 4). Da bi se odredilo koja poluravnina zadovoljava nejednakost, potrebno je odabrati bilo koju tačku na grafu koja ne pripada pravoj liniji i zamijeniti njene koordinate u nejednakost. Ako nejednakost vrijedi, tada je ova tačka izvodljivo rješenje, a poluravnina koja sadrži tačku zadovoljava nejednakost. Za zamjenu u nejednakosti zgodno je koristiti početnu tačku. Zamijenite x 1 = x 2 = 0 u nejednakost 2x 1 + 3x 2 12. Dobijamo 2x0 + 3x0 12. Ova tvrdnja je tačna, dakle, nejednakost 2x 1 + 3x 2 12 odgovara donjoj poluravni koja sadrži tačku (0; 0). Ovo se odražava na grafikonu prikazanom na Sl. 1.1.
Slično, možete grafički prikazati sva ograničenja LP problema.
Rješenje svake nejednakosti LPP sistema ograničenja je poluravnina koja sadrži graničnu liniju i nalazi se na jednoj njenoj strani. Presek poluravni, od kojih je svaka određena odgovarajućom nejednakošću sistema, naziva se oblast izvodljivih rešenja ili oblast definicije. Treba imati na umu da područje izvodljivih rješenja zadovoljava uslove nenegativnosti ( x j 0, j = 1, 2, ..., n). Koordinate bilo koje tačke koja pripada domenu definicije su izvodljivo rješenje problema.
Za pronalaženje ekstremne vrijednosti funkcije cilja u grafičkom rješenju LP problema koristi se vektorski gradijent čije su koordinate parcijalni izvod funkcije cilja, tj.
Ovaj vektor pokazuje smjer najbrže promjene ciljne funkcije. Ravno sa 1 x 1 + sa 2 x 2 = f (x 0), okomito na vektor gradijenta, je linija nivoa ciljne funkcije. U bilo kojoj tački na liniji nivoa, funkcija cilja poprima istu vrijednost. Izjednačimo ciljnu funkciju sa konstantnom vrijednošću "a"... Promjenom vrijednosti "a", dobijamo porodicu paralelnih pravih linija, od kojih je svaka linija nivoa ciljne funkcije.
Važno svojstvo linije nivoa linearne funkcije je da kada se linija paralelno pomiče u jednom pravcu, nivo se samo povećava, a kada se pomera u drugom smeru, samo opada.
Sa geometrijske tačke gledišta, u problemu linearnog programiranja, traži se takva ugaona tačka ili skup tačaka iz izvodljivog skupa rešenja, na kojoj se dostiže linija najvišeg (najnižeg) nivoa, koja se nalazi dalje (bliže) od ostali u pravcu najbržeg rasta.
Grafička metoda rješavanja LPP-a sastoji se od sljedećih faza.
1. Konstruirana je poligonalna regija izvodljivih rješenja (ODS) LPP-a.
2. Vektorski gradijent funkcije cilja (CF) je konstruisan u nekoj tački x 0 koja pripada ODR:
3. Linija nivoa sa 1 x 1 + c 2 x 2 = a (a je konstantna vrijednost) - prava linija okomita na vektor gradijenta - kreće se u smjeru ovog vektora u slučaju maksimiziranja f (x 1, x 2) sve dok ne napusti granice ODR-a. Granična tačka (ili tačke) područja tokom ovog kretanja je maksimalna tačka f (x 1, x 2).
4. Za pronalaženje koordinata tačke maksimuma dovoljno je riješiti dvije jednadžbe pravih linija koje su dobijene iz odgovarajućih ograničenja i daju maksimalnu tačku na sjecištu. Vrijednost f (x 1, x 2) pronađena u rezultujućoj tački je maksimum.
Kada se minimizira (maksimizira) funkcija f (x 1, x 2), linija nivoa se pomiče u smjeru suprotnom od vektora gradijenta. Ako prava linija koja odgovara liniji nivoa ne napusti ODR tokom svog kretanja, onda minimum (maksimum) funkcije f (x 1, x 2) ne postoji.
Ako je linija nivoa paralelna s nekim funkcionalnim ograničenjem problema, tada će se optimalna vrijednost CF postići u bilo kojoj tački ovog ograničenja koja leži između dvije optimalne kutne tačke, i, prema tome, bilo koja od ovih tačaka je optimalno rješenje ZPP. Moguće situacije za grafičko rješenje LP problema prikazane su u tabeli. 1.3.
Tabela 1.3
| № | ODR tip | Optimalni tip rješenja | Bilješke (uredi) |
| Poligonalno zatvoreno | Samo odluka | ||
| Samo odluka | |||
| Poligonalno | ZF nije ograničen odozdo | ||
| CF nije ograničen odozgo | |||
| Poligonalno otvoren | Samo odluka | ||
| Beskonačan broj rješenja | |||
| Odjeljak | Samo odluka |
Razmotrimo grafičko rješenje problema linearnog programiranja koristeći sljedeći primjer.
Primjer 1.1. Planiranje proizvodnje šivaćeg preduzeća (problem odela).
Planirano je izdavanje dvije vrste odijela - muških i ženskih. Za žensko odijelo potrebno je 1m vune, 2m lavsana i 1 osoba/dan rada. Za muško odijelo - 3,5m vune, 0,5m lavsana i 1 osoba/dan rada. Ukupno ima 350m vune, 240m lavsana i 150 č/dan troškova rada. Potrebno je odrediti koliko odijela svake vrste treba sašiti da bi se osigurala maksimalna zarada, ako je dobit od prodaje ženskog odijela 10 novčanih jedinica, a od muškog odijela 20 novčanih jedinica. Treba imati na umu da se mora sašiti najmanje 60 muških odijela.
Uvedemo sljedeće oznake: x 1 - broj ženskih odijela; x 2 - broj muških odijela. Dobit od prodaje ženskih odijela je 10x 1, a od prodaje muških - 20x 2, tj. potrebno je maksimizirati funkciju cilja:
10x 1 + 20x 2
Ograničenja zadatka su sljedeća:
x 1 + x 2 150,
2 x 1 + 0,5x 2 240,
x 1 + 3,5x 2 350,
x 2 60,
x 1 0.
Prvo ograničenje rada x 1 + x 2 150. Prava linija x 1 + x 2 = 150 prolazi kroz tačke (150; 0) i (0; 150) (slika 1.2).
Drugo ograničenje za lavsan je 2 x 1 + 0,5x 2 240. Prava linija 2 x 1 + 0,5x 2 = 240 prolazi kroz tačke (120; 0) i (0; 480). Treće ograničenje na vunu x 1 + 3,5 x 2 350. Dodajmo i četvrto ograničenje na broj muških odijela x 2 60. Rješenje ove nejednakosti je poluravan koja leži iznad prave x 2 = 60. Na sl. 1.3 područje dopuštenih rješenja je zasjenjeno. Da bismo odredili pravac kretanja do optimuma, konstruišemo vektor gradijenta čije su koordinate parcijalne derivacije ciljne funkcije, tj.
Da biste napravili takav vektor, potrebno je da povežete tačku (10; 20) sa ishodištem. Prilikom maksimiziranja funkcije cilja potrebno je kretati se u smjeru vektora gradijenta, a kod minimiziranja u suprotnom smjeru. Radi praktičnosti, možete izgraditi vektor proporcionalan vektoru. Dakle, na sl. 1.4 prikazuje vektor gradijenta (30; 60).
Da bismo odredili pravac kretanja do optimuma, konstruišemo vektor gradijenta čije su koordinate parcijalne derivacije ciljne funkcije, tj.
U našem slučaju, linija nivoa će se pomicati sve dok ne napusti područje dopuštenih rješenja. U ekstremnoj, kutnoj tački, postiže se maksimum funkcije cilja. Da biste pronašli koordinate ove tačke, dovoljno je riješiti dvije jednadžbe pravih linija koje su dobijene iz odgovarajućih ograničenja i daju maksimalnu tačku na sjecištu:
x 1 + 3,5x 2 = 350,
x 1 + x 2 = 150.
Odavde je lako zapisati rješenje originalnog LPP-a: max f (x)= 2300 i postiže se pri x 1 = 70 i x 2 = 80 (vidi sliku 1.4).
1.3 TEHNOLOGIJA ZA RJEŠAVANJE PROBLEMA LINEARNOG PROGRAMIRANJA KORIŠTENJEM PODEŠAVANJA TRAŽENJE RJEŠENJA U EXCEL OKRUŽENJU
1.3.1. Opće informacije o radu s Excel procesorom proračunskih tablica
Razmotrimo neke aspekte rada sa Excel procesorom proračunskih tablica, koji će pojednostaviti proračune potrebne za rješavanje problema optimizacije. Tabela je softverski proizvod dizajniran za automatizaciju obrade tabelarnih podataka.
Excel elementi ekrana. Nakon pokretanja Excel-a, na ekranu se pojavljuje tabela čiji je prikaz prikazan na slici 1.5.
Ova slika se zove radni list. To je mreža redova i kolona čiji presjeci formiraju pravokutnike koji se nazivaju ćelije. Radni listovi su namijenjeni unosu podataka, proračunima, organizaciji baze podataka itd. Excel prozor prikazuje glavne elemente programa: naslovnu traku, traku menija, statusnu traku, dugmad za kontrolu prozora.
Rad sa formulama. U programima za proračunske tablice, formule se koriste za izvođenje širokog spektra proračuna. Uz Excel možete brzo kreirati formulu. Formula ima tri glavna dijela:
1) znak jednakosti;
2) skup vrijednosti ili referenci na ćelije sa kojima se vrše proračuni;
3) operateri.
4) Ako nema znaka jednakosti, onda Excel podatke ne tumači kao formulu, već kao unos podataka u ćeliju. Formule se mogu unositi direktno u ćeliju ili u traku formule - bilo tekst ili brojevi. U ovom slučaju morate učiniti sljedeće:
· Odaberite ćeliju koja treba da sadrži formulu i unesite znak (=);
· Unesite operator ili znak akcije;
· Odaberite drugu ćeliju koja će biti uključena u formulu;
· Pritisnite tipku Enter.
Unesena formula se pojavljuje u traci formule, a rezultat izračuna se pojavljuje u ćeliji.
Korištenje funkcija u formulama. Možete koristiti Excel funkcije da biste olakšali unos formula. Funkcije su formule ugrađene u Excel. Excel sadrži mnoge formule. Grupirani su u različite vrste: logičke, matematičke, inženjerske, statističke itd.
Da biste aktivirali određenu formulu, pritisnite gumbe Umetanje, Funkcije. Prozor čarobnjaka za funkcije koji se pojavljuje na lijevoj strani sadrži listu tipova funkcija. Nakon odabira tipa, sa desne strane će se postaviti lista samih funkcija. Funkcija se bira klikom na odgovarajući naziv.
Različite funkcije izvode različite vrste proračuna prema specifičnim pravilima. Kada je funkcija jedan objekat u ćeliji radnog lista, ona počinje znakom (=), nakon čega slijedi naziv funkcije, a zatim argumenti funkcije, zatvoreni u zagradama.
Pronalaženje rješenja je Excel dodatak koji vam omogućava da riješite probleme optimizacije. Ako komanda Pronađi rješenje nedostaje u izborniku Alati, tada morate učitati ovaj dodatak. Odaberite Alati => Dodaci i aktivirajte dodatak Find Solution. Ako se ovaj dodatak ne nalazi u dijaloškom okviru Dodaci, potrebno je da odete na Windows Control Panel, kliknete na ikonu Dodaj ili ukloni programe i koristite program za podešavanje programa Excel (ili Office) da instalirate dodatak Pronađi rješenje -in.
Nakon što odaberete Tools => Find Solution, pojavljuje se okvir za dijalog Find Solution.
Postoje tri glavne opcije u dijaloškom okviru Find Solution;
Postavite ciljnu ćeliju.
Promjenom ćelija.
Ograničenja.
Prvo morate popuniti polje Postavi ciljnu ćeliju. U svim zadacima za alat Solver optimizira se rezultat u jednoj od ćelija radnog lista. Ciljna ćelija je povezana sa drugim ćelijama u ovom radnom listu pomoću formula. Solution Finder koristi formule koje proizvode rezultat u ciljnoj ćeliji za testiranje mogućih rješenja. Možete odabrati da tražite najmanju ili najveću vrijednost za ciljnu ćeliju ili postavite određenu vrijednost.
Drugi važan parametar alata Solver je parametar Modify Cells. Ovdje određujete ćelije, vrijednosti u kojima će se promijeniti kako bi se optimizirao rezultat u ciljnoj ćeliji. Možete odrediti do 200 promjenjivih ćelija za traženje rješenja. Postoje dva glavna zahtjeva za ove ćelije: ne bi trebale sadržavati formule i promjene njihovih vrijednosti trebale bi se odraziti na promjenu rezultata u ciljnoj ćeliji. Drugim riječima, ciljna ćelija ovisi o ćelijama koje treba promijeniti.
Treći parametar koji se mora unijeti na kartici Rješavanje su ograničenja.
Da biste riješili problem, morate:
1) naznačiti adrese ćelija u koje će biti smešten rezultat rešenja (promenljive ćelije);
2) upisuje početne podatke;
3) uvesti zavisnost za funkciju cilja;
4) uvesti zavisnosti za ograničavanje,
5) pokrenite komandu Traži rješenja;
6) dodijeliti ćeliju ciljnoj funkciji (postaviti ciljnu ćeliju);
7) uvodi ograničenja;
8) upisati parametre za rješavanje ZJN.
Razmotrimo tehnologiju rješenja koristeći uslove primjera 1.1 (problem odijela).
Ekonomsko-matematički model problema
Neka je x 1 broj ženskih odijela; x 2 - broj muških odijela,
10 x x 1 + 20 x x 2 max
Ograničenja zadatka su sljedeća:
x 1 + x 2 150 - ograničenja rada;
2 x x 1 + 0,5 x NS 2 240 - ograničenje na lavsan;
x 1 + 3,5 x x 2 350 - ograničenje vune;
x 2 60 - ograničenje na muška odijela;
x 1 0 - ograničenje za ženska odijela.
1. Odredite adrese ćelija u koje će se smjestiti rezultat rješenja (modificirane ćelije).
Oznaka x 1, x 2 za broj odijela svake vrste. U našem zadatku, optimalne vrijednosti vektora = (x 1, x 2) bit će smještene u ćelije A2: B2, optimalna vrijednost funkcije cilja - u ćeliju C3.
2. Unesite početne podatke.
Unesite početne podatke zadatka, kao što je prikazano na sl. 1.6.
3. Uvesti zavisnost za funkciju cilja.
· Postavite kursor u "NW" ćeliju, ćelija će biti istaknuta.
· Postavite kursor na dugme Čarobnjaka za funkcije koje se nalazi na traci sa alatkama.
· Unesite Enter. Na ekranu se pojavljuje dijaloški okvir Function Wizard Step 1 of 2.
· U prozoru Funkcije izaberite liniju SUMPRODUCT (Slika 1.7). Na ekranu
· Pojavljuje se dijaloški okvir SUMPRODUCT (Slika 1.8).
U red Niz 1 unesite A2: B2.
· U red Niz 2 unesite AZ: VZ.
Niz 1 će se koristiti prilikom ubacivanja zavisnosti ograničenja, tako da morate napraviti apsolutnu referencu na ovaj niz. Na sl. 1.9 pokazuje da je funkcija uvedena u ćeliju SZ.
5. Uvesti zavisnosti za ograničenja (slika 1.10).
· Postavite kursor u ćeliju SZ.
· Na traci sa alatkama, dugme Kopiraj u međuspremnik.
· Postavite kursor u ćeliju C4.
· Postavite kursor u ćeliju C5.
· Na traci sa alatkama, dugme Paste from clipboard.
· Postavite kursor u ćeliju Sat.
· Na traci sa alatkama, dugme Paste from clipboard.
· Postavite kursor u ćeliju C7.
· Na traci sa alatkama kliknite na dugme Paste from clipboard. (Mora se provjeriti sadržaj ćelija C4-C7. Moraju sadržavati informacije, kao što je prikazano za primjer na slici 1.11; sadržaj ćelije C5 je prikazan kao primjer.)
· Na traci menija, postavite pokazivač miša na uslugu. U proširenom meniju izaberite komandu Find solution. Pojavljuje se dijalog Traženje rješenja (slika 1.12).
5. Pokrenite naredbu Pronađi rješenje.
6. Dodijelite ćeliju za funkciju cilja (postavite ciljnu ćeliju), navedite adrese ćelija koje treba promijeniti.
· Postavite kursor na liniju Postavi ciljnu ćeliju.
· Unesite adresu ćelije $ C $ 3.
· Unesite tip funkcije cilja u zavisnosti od uslova vašeg problema. Da biste to učinili, označite da li je funkcija cilja jednaka maksimalnoj vrijednosti ili minimalnoj vrijednosti.
· Postavite kursor u red Promena ćelija.
· Unesite adrese traženih varijabli A $ 2: B $ 2 (slika 1.13).
7. Uvesti ograničenja.
· Pomerite pokazivač miša preko dugmeta Dodaj. Pojavljuje se okvir za dijalog Add Constraint.
· Uvesti znak ograničenja.
· U red Ograničenje unesite adresu $ D $ 4 (slika 1.14).
· Pomerite pokazivač miša preko dugmeta Dodaj. Dijaloški okvir Dodaj ograničenje ponovo se pojavljuje na ekranu.
· Uvesti ostala ograničenja problema prema gore navedenom algoritmu.
· Nakon što je zadnje ograničenje uvedeno, kliknite na dugme OK. Na ekranu će se pojaviti dijalog Traženje rješenja sa unesenim uslovima (slika 1.15).
8. Unesite parametre za rješavanje problema linearnog programiranja.
· U dijaloškom okviru, postavite pokazivač miša na dugme Opcije. Na ekranu će se pojaviti dijalog parametara pretraživanja rješenja (slika 1.16).
· Postavite potvrdne okvire u poljima Linearni model (ovo će osigurati primjenu simpleks metode) i Nenegativne vrijednosti.
· Pomerite pokazivač miša preko dugmeta OK. Pojavljuje se okvir za dijalog Find Solution.
· Postavite pokazivač miša na dugme Run.
Nakon kratkog vremena pojavit će se dijaloški okvir Rezultati pretraživanja rješenja i originalna tablica sa popunjenim AZ ćelijama: VZ za vrijednosti x i i ćelija C3 sa maksimalnom vrijednošću funkcije cilja (slika 1.17).
Ako navedete tip izvještaja Stabilnost, tada možete dobiti dodatne informacije o optimalnom rješenju (slika 1.18).
Kao rezultat rješavanja problema, dobiven je odgovor: potrebno je sašiti 70 komada. ženskih odijela i 80 kom. muška odijela za maksimalnu zaradu od 2300 USD.
1.4. DUALNOST U PROBLEMAMA LINEARNOG PROGRAMIRANJA. ANALIZA DOBIJENIH OPTIMALNIH RJEŠENJA
Godine 1975. naš sunarodnik L.V. Kantorovich je dobio Nobelovu nagradu za ekonomiju (zajedno sa američkim ekonomistom T. Koopmansom) za razvoj teorije optimalne upotrebe resursa (vidi Dodatak 1).
Usko povezan sa svakim problemom linearnog programiranja je još jedan linearni problem, koji se zove dualni; početni zadatak se naziva početni ili direktni. Veza između izvornog i dualnog problema leži, posebno, u činjenici da se rješenje jednog od njih može dobiti direktno iz rješenja drugog.
Varijable dualnog problema y i nazivaju se objektivno određene procjene, ili dualne procjene, ili "cijene" resursa, ili cijene u sjeni.
Svaki od problema dualnog para je zapravo nezavisan problem linearnog programiranja i može se riješiti nezavisno od drugog.
Dvostruki problem u odnosu na original sastavlja se prema sljedećim pravilima:
1) ciljna funkcija originalnog problema je formulisana za maksimum, a ciljna funkcija dualnog problema - za minimum, dok u zadatku za maksimum sve nejednakosti u funkcionalnim ograničenjima imaju oblik (), u problemu za minimum - obrazac ( );
2) matrica A, sastavljena od koeficijenata na nepoznatim ograničenjima u sistemu originalnog problema, i slična matrica A T u dualnom problemu dobijaju se jedna od druge transpozicijom;
3) broj varijabli u dualnom problemu jednak je broju funkcionalnih ograničenja originalnog problema, a broj ograničenja u sistemu dualnog problema je jednak broju varijabli u originalnom;
4) koeficijenti za nepoznate u ciljnoj funkciji dualnog problema su slobodni članovi u sistemu ograničenja originalnog problema, a desne strane u ograničenjima dualnog problema su koeficijenti za nepoznate u ciljnoj funkciji od original; j 0.
Ova dva problema čine par simetričnih dualnih problema. Glavne tvrdnje o međusobno dualnim problemima sadržane su u sljedeće dvije teoreme.
Prva teorema dualnosti. Za obostrano dvostruke zadatke, odvija se jedan od međusobno isključivih slučajeva.
1. Direktni i dvojni problemi imaju optimalna rješenja,
u ovom slučaju, vrijednosti ciljnih funkcija na optimalnim rješenjima
match
2. U direktnom problemu, dopušteni skup nije prazan, a ciljna funkcija na ovom skupu nije ograničena odozgo. Štaviše, dualni problem će imati prazan dopušteni skup.
3. U dualnom problemu, dopušteni skup nije prazan, a ciljna funkcija na ovom skupu nije ograničena odozdo. U ovom slučaju se ispostavlja da je dopušteni skup direktnog problema prazan.
4. Oba problema koja se razmatraju imaju prazne dopustive skupove.
Druga teorema dualnosti (komplementarna teorema o labavosti). Neka = ( x 1, x 2, ..., xn) je dopušteno rješenje direktnog problema, a = (y 1, y 2,…, y m) je dopušteno rješenje dualnog problema. Da bi oni bili optimalna rješenja direktnog, odnosno dualnog problema, potrebno je i dovoljno da vrijede sljedeće relacije:
(1.4)
(1.5)
Uslovi (1.4) i (1.5) omogućavaju da se, znajući optimalno rešenje jednog od međusobno dualnih problema, pronađe optimalno rešenje za drugi problem.
Razmotrimo još jednu teoremu, čiji će se zaključci koristiti u nastavku.
Teorema procjene. Vrijednosti varijabli y i u optimalnom rješenju dualnog problema su procjene utjecaja slobodnih članova b i sistema ograničenja (nejednakosti) direktnog problema na vrijednost
Rješavajući LPP simpleks metodom, istovremeno rješavamo i dualni LPP. Varijable dualnog problema y i nazivaju se objektivno određene procjene.
Razmotrimo ekonomsku interpretaciju dualnog problema na primjeru problema tepiha.
Primjer 1 .2. Koristeći izjavu o problemu tepiha, dovršite sljedeće zadatke.
1. Formulirati ekonomsko-matematički model problema tepiha za maksimalnu ukupnu cijenu proizvodnje, koristeći podatke u tabeli. 1.1.
2. Koristeći Search Solution Search, pronađite plan proizvodnje koji maksimizira ukupne troškove proizvodnje.
3. Formulirati ekonomski i matematički model dualnog problema na problem tepiha.
4. Pronađite optimalni plan dualnog problema, koristeći teoremu dualnosti, objasnite jednakost sa nulom X 1 i X 4.
5. Koristeći protokole Traganje za rješenjem analizirati dobiveno optimalno rješenje izvornog problema.
6. Odredite kako će se ukupni troškovi i plan proizvodnje promijeniti s povećanjem rezerve resursa cijevi za 12 jedinica.
1. Formulirajmo ekonomski i matematički model problema.
Označimo kroz X 1, X 2, X 3, X 4 broj tepiha svake vrste. Ciljna funkcija ima oblik
F (X) = ZX 1 + 4X 2 + ZX 3 + X 4 max,
i ograničenja resursa
7X 1 + 2X 2 + 2X 3 + 6X 4 80,
5X 1 + 8X 2 + 4 X 3 + ZX 4 480,
2X 1 + 4 X 2 + X 3 + 8X 4 130,
X 1, X 2, X 3, X 4 0.
2. Pronalaženje optimalnog plana izdavanja.
Problem ćemo riješiti korištenjem Excel dodatka Traži rješenje. Tehnologija rješavanja problema detaljno je razmotrena u problemu o odijelima. U našem zadatku, optimalne vrijednosti vektora X = (X 1, X 2, X 3, X 4) bit će smještene u ćelije VZ: EZ, optimalna vrijednost ciljne funkcije - u ćeliji F4.
Unesite početne podatke. Prvo, opisujemo funkciju cilja pomoću funkcije - ZBIR (Slika 1.19). Zatim ćemo unijeti podatke za lijevu stranu ograničenja. U Traganju za rješenjem uvodimo smjer ciljne funkcije, adrese traženih varijabli i dodajemo ograničenja. Na ekranu će se pojaviti dijalog Traženje rješenja sa unesenim uslovima (slika 1.20).
Nakon unosa parametara za rješavanje LPP-a, kliknite na dugme Izvrši. Na ekranu će se pojaviti poruka da je rešenje pronađeno (slika 1.21).
Dobiveno rješenje znači da je maksimalni prihod 150 hiljada rubalja. fabrika po puštanju može dobiti 30 tepiha drugog tipa i 10 tepiha trećeg tipa. U ovom slučaju, resursi „radna snaga“ i „oprema“ će biti u potpunosti iskorišteni, te će se iskoristiti 280 kg od 480 kg pređe (resurs „sirov“).
Generisanje izveštaja na osnovu rezultata potrage za rešenjem. Excel vam omogućava da rezultate pretraživanja rješenja prikažete u obliku izvještaja (tabela 1.4). Postoje tri vrste ovakvih izvještaja:
· Rezultati (odgovor). Izvještaj uključuje izvorne i odredišne vrijednosti ciljnih i izmijenjenih ćelija, te više informacija o ograničenjima.
· Stabilnost (osjetljivost). Izvještaj koji pruža informacije o osjetljivosti rješenja na male promjene u ćelijama koje su promijenjene ili u formulama ograničenja.
· Ograničenja. Osim izvornih i ciljnih vrijednosti modificiranih i ciljnih ćelija, izvještaj uključuje gornju i donju granicu vrijednosti koje ćelije koje utiču mogu preuzeti, podložno ograničenjima.
Ako u problemu linearnog programiranja postoje samo dvije varijable, on se može riješiti grafički.
Razmotrimo problem linearnog programiranja s dvije varijable i:
(1.1)
;
(1.2)
Ovdje postoje proizvoljni brojevi. Zadatak može biti i pronaći maksimum (max) i pronaći minimum (min). U sistemu ograničenja mogu biti prisutni i znakovi i znaci.
Izgradnja regiona izvodljivih rješenja
Grafička metoda rješavanja problema (1) je sljedeća.
Prvo crtamo koordinatne osi i odabiremo razmjer. Svaka od nejednakosti sistema ograničenja (1.2) definira poluravninu ograničenu odgovarajućom pravom.
Dakle, prva nejednakost
(1.2.1)
definira poluravninu omeđenu pravom linijom. S jedne strane ove prave linije, a sa druge strane. Na najravnijoj liniji. Da bismo saznali s koje strane vrijedi nejednakost (1.2.1), biramo proizvoljnu tačku koja ne leži na pravoj liniji. Zatim zamjenjujemo koordinate ove tačke u (1.2.1). Ako nejednakost vrijedi, tada poluravnina sadrži odabranu tačku. Ako nejednakost nije zadovoljena, tada se poluravnina nalazi na drugoj strani (ne sadrži odabranu tačku). Sjenčanje poluravnine za koju vrijedi nejednakost (1.2.1).
Isto radimo i za preostale nejednakosti sistema (1.2). Ovo će nam dati zasjenjene poluravnine. Tačke oblasti izvodljivih rješenja zadovoljavaju sve nejednakosti (1.2). Stoga je grafički područje izvodljivih rješenja (ADS) presjek svih konstruiranih poluravni. Shading ODT. To je konveksan poligon čija lica pripadaju konstruisanim pravim linijama. Također, ODR može biti neograničeni konveksni oblik, segment linije, zraka ili ravna linija.
Može se pojaviti slučaj da poluravnine ne sadrže zajedničke tačke. Tada je domen izvodljivih rješenja prazan skup. Ovaj problem nema rješenja.
Metoda se može pojednostaviti. Ne morate zasjeniti svaku poluravninu, već prvo izgradite sve ravne linije
(2)
Zatim odaberite proizvoljnu tačku koja ne pripada nijednoj od ovih linija. Zamenimo koordinate ove tačke u sistem nejednačina (1.2). Ako su sve nejednakosti zadovoljene, tada je područje izvodljivih rješenja ograničeno konstruiranim pravim linijama i uključuje odabranu tačku. Osjenčamo područje izvodljivih rješenja duž granica pravih linija tako da uključuje odabranu tačku.
Ako barem jedna nejednakost nije zadovoljena, onda biramo drugu tačku. I tako sve dok se ne pronađe jedna tačka čije koordinate zadovoljavaju sistem (1.2).
Pronalaženje ekstrema ciljne funkcije
Dakle, imamo zasjenjeno područje izvodljivih rješenja (ODS). Omeđena je polilinijom koja se sastoji od segmenata i zraka koji pripadaju konstruisanim pravim linijama (2). ODR je uvijek konveksan skup. Može biti ili ograničen skup ili neograničen u nekim smjerovima.
Sada možemo tražiti ekstremum funkcije cilja
(1.1)
.
Da biste to učinili, odaberite bilo koji broj i napravite pravu liniju
(3)
.
Radi pogodnosti daljeg predstavljanja, pretpostavljamo da ova linija prolazi kroz ODR. Na ovoj liniji, ciljna funkcija je konstantna i jednaka. takva ravna linija se zove linija na nivou funkcije. Ova ravna linija dijeli ravan na dvije poluravnine. Na jednoj poluravni
.
Na drugoj poluravni
.
Odnosno, na jednoj strani prave (3) ciljna funkcija raste. I što više odmaknemo tačku od prave linije (3), to će vrijednost biti veća. S druge strane prave linije (3) ciljna funkcija se smanjuje. I što dalje pomjerimo tačku od prave linije (3) na drugu stranu, to će vrijednost biti manja. Ako povučemo pravu liniju paralelnu pravoj liniji (3), tada će nova prava linija biti i linija nivoa ciljne funkcije, ali s drugom vrijednošću.
Dakle, da bi se pronašla maksimalna vrijednost ciljne funkcije, potrebno je povući pravu liniju paralelnu pravoj liniji (3), najudaljeniju od nje u smjeru povećanja vrijednosti i koja prolazi kroz barem jednu tačku ODR-a. Za pronalaženje minimalne vrijednosti ciljne funkcije potrebno je povući pravu liniju paralelnu pravoj liniji (3) i najudaljeniju od nje u smjeru opadanja vrijednosti i koja prolazi kroz barem jednu tačku ODR-a.
Ako je DDR neograničen, onda može nastati slučaj kada se takva prava linija ne može povući. Odnosno, bez obzira na to kako uklonimo pravu liniju sa nivelete (3) u smjeru povećanja (opadanja), prava će uvijek prolaziti kroz ODR. U ovom slučaju može biti proizvoljno veliko (malo). Dakle, ne postoji maksimalna (minimalna) vrijednost. Problem nema rješenja.
Razmotrimo slučaj kada ekstremna ravna linija paralelna proizvoljnoj pravoj liniji oblika (3) prolazi kroz jedan vrh ODR poligona. Iz grafa određujemo koordinate ovog vrha. Tada se maksimalna (minimalna) vrijednost ciljne funkcije određuje formulom:
.
Rješenje problema je
.
Također može postojati slučaj kada je ravna linija paralelna s jednom od lica ODR-a. Tada linija prolazi kroz dva vrha ODR poligona. Odredite koordinate ovih vrhova. Da biste odredili maksimalnu (minimalnu) vrijednost funkcije cilja, možete koristiti koordinate bilo kojeg od ovih vrhova:
.
Problem ima beskonačno mnogo rješenja. Rješenje je svaka tačka koja se nalazi na segmentu između tačaka i, uključujući tačke i njih same.
Primjer rješavanja problema linearnog programiranja pomoću grafičke metode
Zadatak
Kompanija proizvodi haljine dva modela A i B. U ovom slučaju se koriste tri vrste tkanina. Za izradu jedne haljine modela A potrebno je 2 m prve vrste tkanine, 1 m druge vrste tkanine i 2 m treće vrste tkanine. Za izradu jedne haljine modela B potrebno je 3 m prve vrste tkanine, 1 m druge vrste tkanine, 2 m treće vrste tkanine. Zalihe prve vrste tkanine su 21 m, druge vrste - 10 m, treće vrste - 16 m. Izdavanje jednog proizvoda tipa A donosi prihod od 400 den. jedinica, jedan proizvod tipa B - 300 den. jedinice
Napravite plan proizvodnje koji kompaniji daje najveći prihod. Riješite problem grafički.
Rješenje
Označite varijable i broj proizvedenih haljina modela A i B, respektivno. Tada će količina potrošene tkanine prve vrste biti:
(m)
Količina potrošene tkanine druge vrste bit će:
(m)
Količina potrošene tkanine treće vrste će biti:
(m)
Pošto broj proizvedenih haljina ne može biti negativan
i .
Prihod od proizvedenih haljina će biti:
(novčane jedinice)
Tada ekonomsko-matematički model problema ima oblik:
Rešavamo ga grafički.
Crtamo koordinatne ose i.
Gradimo pravu liniju.
U .
U .
Povucite pravu liniju kroz tačke (0; 7) i (10,5; 0).
Gradimo pravu liniju.
U .
U .
Nacrtajte pravu liniju kroz tačke (0; 10) i (10; 0).
Gradimo pravu liniju.
U .
U .
Nacrtajte pravu liniju kroz tačke (0; 8) i (8; 0).
Osjenčanje područja tako da tačka (2; 2) padne u zasjenjeni dio. Dobijamo četvorougao OABC.
(A1.1) .
U .
U .
Nacrtajte pravu liniju kroz tačke (0; 4) i (3; 0).
Nadalje, primjećujemo da pošto su koeficijenti na i ciljne funkcije pozitivni (400 i 300), onda se povećava s povećanjem i. Povlačimo pravu liniju paralelnu pravoj liniji (A1.1), najudaljeniju od nje u uzlaznom smjeru i koja prolazi kroz barem jednu tačku četverougla OABC. Takva prava linija prolazi kroz tačku C. Iz konstrukcije određujemo njene koordinate.
.
Rješenje problema: ;
Odgovori
.
Odnosno, za ostvarivanje najvećeg prihoda potrebno je napraviti 8 haljina modela A. U ovom slučaju prihod će biti 3200 den. jedinice
Primjer 2
Zadatak
Riješite problem linearnog programiranja pomoću grafičke metode.
Rješenje
Rešavamo ga grafički.
Crtamo koordinatne ose i.
Gradimo pravu liniju.
U .
U .
Nacrtajte pravu liniju kroz tačke (0; 6) i (6; 0).
Gradimo pravu liniju.
Odavde.
U .
U .
Povucite pravu liniju kroz tačke (3; 0) i (7; 2).
Gradimo pravu liniju.
Gradimo pravu liniju (os apscisa).
Područje izvodljivih rješenja (ODD) ograničeno je konstruiranim pravim linijama. Da bismo saznali s koje strane, primjećujemo da tačka pripada ODR-u, budući da zadovoljava sistem nejednakosti:
Osjenčamo područje duž granica konstruisanih linija tako da tačka (4; 1) padne u zasjenjeni dio. Dobijamo trougao ABC.
Gradimo proizvoljnu liniju nivoa ciljne funkcije, na primjer,
.
U .
U .
Kroz tačke (0; 6) i (4; 0) povlačimo pravu liniju nivoa.
Pošto ciljna funkcija raste sa povećanjem i tada povlačimo pravu liniju, paralelnu liniji nivoa i što dalje od nje u pravcu rasta, i koja prolazi kroz barem jednu tačku trougla ABC. Takva prava linija prolazi kroz tačku C. Iz konstrukcije određujemo njene koordinate.
.
Rješenje problema: ;
Odgovori
Primjer bez rješenja
Zadatak
Riješite grafički problem linearnog programiranja. Pronađite maksimalnu i minimalnu vrijednost funkcije cilja.
Rješenje
Zadatak rješavamo grafički.
Crtamo koordinatne ose i.
Gradimo pravu liniju.
U .
U .
Povucite pravu liniju kroz tačke (0; 8) i (2,667; 0).
Gradimo pravu liniju.
U .
U .
Nacrtajte pravu liniju kroz tačke (0; 3) i (6; 0).
Gradimo pravu liniju.
U .
U .
Nacrtajte pravu liniju kroz tačke (3; 0) i (6; 3).
Prave su koordinatne ose.
Područje dopuštenih rješenja (ODS) ograničeno je izgrađenim pravim linijama i koordinatnim osa. Da bismo saznali s koje strane, primjećujemo da tačka pripada ODR-u, budući da zadovoljava sistem nejednakosti:
Osjenčamo područje tako da tačka (3; 3) padne u zasjenjeni dio. Dobijamo neograničeno područje ograničeno polilinijom ABCDE.
Gradimo proizvoljnu liniju nivoa ciljne funkcije, na primjer,
(A3.1) .
U .
U .
Nacrtajte pravu liniju kroz tačke (0; 7) i (7; 0).
Pošto su koeficijenti na i pozitivni, on raste sa povećanjem i.
Da biste pronašli maksimum, morate nacrtati paralelnu pravu liniju koja je maksimalno udaljena u uzlaznom smjeru i koja prolazi kroz barem jednu tačku područja ABCDE. Međutim, pošto je regija neograničena sa strane velikih vrijednosti i, takva prava linija se ne može povući. Bez obzira koju pravu liniju povučemo, uvijek će postojati tačke regije koje su udaljenije u pravcu povećanja i. Dakle, ne postoji maksimum. može biti proizvoljno velika.
Tražimo minimum. Povlačimo pravu liniju paralelnu pravoj liniji (A3.1) i najudaljeniju od nje u pravcu opadanja i koja prolazi kroz barem jednu tačku površine ABCDE. Takva prava linija prolazi kroz tačku C. Iz konstrukcije određujemo njene koordinate.
.
Minimalna vrijednost funkcije cilja:
Odgovori
Ne postoji maksimalna vrijednost.
Minimalna vrijednost
.
Razmotrimo prvo najjednostavniji slučaj kada su u LPP uključene tačno dvije varijable:
Svaka od nejednačina (a) - (b) sistema ograničenja problema (3.8) geometrijski definiše poluravninu sa graničnim linijama, X 1 = 0 i X 2 = 0, respektivno. Svaka od graničnih linija dijeli ravan x 1 Ox 2 na dvije poluravnine. Sva rješenja izvorne nejednakosti leže u jednoj od formiranih poluravnina (sve točke poluravnine) i, stoga, kada se koordinate bilo koje njene točke zamijene u odgovarajuću nejednakost, ona je pretvara u pravi identitet . Uzimajući to u obzir, određuje se poluravnina u kojoj leže rješenja nejednakosti, tj. odabirom bilo koje tačke iz bilo koje poluravnine i zamjenom njenih koordinata u odgovarajuću nejednačinu. Ako nejednakost vrijedi za datu tačku, onda vrijedi i za bilo koju drugu tačku iz iste poluravni. Inače, rješenja nejednakosti leže u drugoj poluravni.
Ako je sistem nejednačina (a) - (b) konzistentan, tada je domen njegovih rješenja skup tačaka koje pripadaju svim naznačenim poluravnama. Budući da je skup presječnih tačaka ovih poluravni konveksan, domen izvodljivih rješenja problema (3.8) je konveksan skup, koji se naziva poligon rješenja (ranije uveden termin „politop rješenja” obično se koristi ako se n 3). Stranice ovog poligona leže na pravim linijama, čije se jednačine dobijaju iz originalnog sistema ograničenja zamjenom znakova nejednakosti znakovima tačnih jednakosti.
Dakle, početni LPP se sastoji u pronalaženju tačke poligona odluke u kojoj ciljna funkcija F zauzima maksimalnu (minimalnu) vrijednost.
Ova tačka postoji kada poligon rješenja nije prazan i ciljna funkcija je na njemu ograničena odozgo. Pod ovim uslovima, na jednom od vrhova poligona odluke, funkcija cilja poprima svoju maksimalnu vrednost. Da bi se odredio ovaj vrh, gradi se linija nivoa L: c 1 x 1 + c 2 x 2 = h (gdje je h neka konstanta), okomita na vektor gradijenta i prolazi kroz poligon rješenja, te je pomiče paralelno duž gradijenta vektor sve dok, dok ne prođe kroz svoju poslednju zajedničku tačku preseka sa poligonom rešenja (prilikom konstruisanja vektora gradijenta, tačka se odlaže (c 1; c 2) u ravni x 1 Ox 2 i crta usmereni segment do njega od početka koordinata). Koordinate navedene tačke određuju optimalni plan za ovaj zadatak.
Sumirajući sve navedeno, predstavljamo algoritam za grafičku metodu rješavanja LPP-a.
Algoritam grafičke metode za rješavanje LPP-a
1. Konstruirati poligon rješenja zadanih sistemom ograničenja originalnog LPP-a.
2. Ako je konstruisani poligon rješenja prazan skup, onda originalni LPP nema rješenja. U suprotnom, konstruisati vektor-gradijent i nacrtati proizvoljnu liniju nivoa L, pomerajući se koja, pri rešavanju problema do maksimuma u pravcu vektora (ili u suprotnom smeru za problem do minimuma), određuje ekstremnu tačku poligona rješenja, gdje se postiže maksimum (minimum) ciljne funkcije problema...
3. Izračunajte koordinate pronađene optimalne tačke 
, nakon što je riješio sistem jednačina dvije granične linije koje se u njemu seku.
4. Zamjenom pronađenog optimalnog rješenja u ciljnu funkciju problema izračunati njegovu optimalnu vrijednost, tj. 
.
Prilikom grafičke konstrukcije skupa dopuštenih rješenja LPP-a (poligona rješenja) moguće su sljedeće situacije.
