Kratka teorija
Linearno programiranje je grana matematičkog programiranja koja se koristi u razvoju metoda za pronalaženje ekstrema linearnih funkcija nekoliko varijabli pod linearnim dodatnim ograničenjima nametnutim varijablama. Prema vrsti problema koje rješava njegove metode se dijele na univerzalne i specijalne. Univerzalnim metodama mogu se riješiti svi problemi linearnog programiranja (LPP). Posebne metode uzimaju u obzir značajke modela problema, njegovu ciljnu funkciju i sustav ograničenja. Značajka problema linearnog programiranja je da funkcija cilja doseže ekstrem na granici područja mogućih rješenja.
Grafička metoda za rješavanje problema linearnog programiranja omogućuje vizualizaciju njihove strukture, identificiranje značajki i otvara načine proučavanja 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 kompliciranije, au prostorima dimenzija većih od tri grafičko rješenje je, općenito govoreći, nemoguće. Slučaj dviju varijabli nema poseban praktični značaj, ali njegovo razmatranje pojašnjava svojstva ograničenja LLP-a, dovodi do ideje o njegovom rješavanju i čini metode rješenja i načine njihove praktične implementacije geometrijski jasnima.
Ako ograničenja i funkcija cilja sadrže više od dvije varijable, tada je potrebno (ili metodom sekvencijalnog poboljšanja rješenja) - univerzalno je i može se koristiti za rješavanje bilo kojeg problema. Za neke primijenjene probleme linearnog programiranja, kao što su , razvijene su posebne metode rješavanja.
Primjer rješenja problema
Zadatak
Poduzeć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 treći tip. Za proizvodnju jedinice proizvoda 2 potrebno je utrošiti kg prve vrste, sirovine druge vrste i sirovine treće vrste. Proizvodnja je opskrbljena sirovinama svake vrste u količinama od kg, kg, kg. Tržišna cijena jedinice proizvoda 1 je tisuća rubalja, a jedinica proizvoda 2 je tisuća rubalja.
Potreban:
- Konstruirajte matematički model problema.
- Grafičkom metodom rješavanja problema linearnog programiranja izraditi plan proizvodnje proizvoda koji osigurava maksimalan prihod od njihove prodaje.
Kako bi se osiguralo da je rješenje problema linearnog programiranja što točnije i točnije, mnogi jeftino naručuju probni rad na ovoj stranici. Više detalja (kako predati zahtjev, cijene, rokovi, načini plaćanja) možete pročitati na stranici Kupi ispitni rad iz linearnog programiranja...
Rješenje problema
Izgradnja modela
Označimo s i broj proizvedenih proizvoda 1. i 2. vrste.
Zatim ograničenja resursa:
Osim toga, prema značenju zadatka
Ciljna funkcija ekonomsko-matematičkog modela, koja izražava prihod od prodaje:
Dobivamo sljedeći ekonomsko-matematički model:
Konstrukcija domene izvedivih rješenja
Riješimo dobiveni problem linearnog programiranja grafički:
Da bismo konstruirali područje mogućih rješenja, konstruiramo granične linije koje odgovaraju ovim nejednakostima u koordinatnom sustavu:
Pronađimo točke kroz koje prolaze linije:
Rješenje svake nejednadžbe ZLP sustava ograničenja je poluravnina koja sadrži graničnu liniju i nalazi se s jedne strane od nje.
Za definiranje poluravnine, uzmite bilo koju točku, na primjer, koja ne pripada pravoj (1), i zamijenite koordinate (0;0) u odgovarajuću nejednadžbu. Jer nejednakost je istinita:
Područje rješenja odgovarajuće 1. nejednadžbe odgovara lijevoj poluravnini
Uzmimo bilo koju točku, na primjer, koja ne pripada liniji (2), i zamijenimo koordinate (0;0) u odgovarajuću nejednadžbu. Jer nejednakost je istinita:
Uzmimo bilo koju točku, na primjer, koja ne pripada pravoj (3), i zamijenimo koordinate (0;0) u odgovarajuću nejednadžbu. Jer nejednakost je istinita:
Područje rješenja odgovarajuće 2. nejednadžbe odgovara lijevoj poluravnini
Područje izvedivih rješenja je brojka.
Pronalaženje rješenja problema LP
Konstruiramo vektor čije su koordinate proporcionalne koeficijentima funkcije cilja. Ovdje je koeficijent proporcionalnosti.
Nacrtajte liniju razine okomito na konstruirani vektor.
Liniju razine pomičemo u smjeru vektora tako da u ekstremnoj točki dodiruje područje mogućih rješenja. Rješenje maksimuma je točka , čije se koordinate nalaze kao točka presjeka pravaca (2) i (1).
Odgovor
Dakle, potrebno je proizvesti 56 proizvoda 1. vrste i 64 proizvoda 2. vrste. U tom će slučaju prihod od prodaje proizvoda biti maksimalan i iznositi 5104 novčane jedinice.
Metoda grafičkog rješenja, ako problem s dvije varijable ima linearna ograničenja i funkcija cilja je kvadratna, ovdje se detaljno raspravlja
Na stranici je detaljno opisano rješenje problema linearnog programiranja pomoću simpleks metode, osim toga prikazana je konstrukcija problema dualnog linearnog programiranja i pronalaženje njegovog rješenja rješavanjem izravnog problema.
Transportni problem i potencijalna metoda
Detaljno je razmotren transportni problem, njegov matematički model i metode rješavanja - nalaženje referentnog plana metodom minimalnog elementa i traženje optimalnog rješenja metodom potencijala.
Konveksno programiranje - grafička metoda
Dan je primjer rješavanja problema kvadratnog konveksnog programiranja grafičkom metodom.
U ovoj lekciji ćemo se upoznati s metodom grafičkog rješavanja problemi linearnog programiranja, odnosno takve probleme u kojima se traži rješenje sustava linearnih jednadžbi i (ili) nejednadžbi (sustava ograničenja) u kojima funkcija cilja - linearna funkcija - poprima optimalnu vrijednost.
S obzirom na to da se preglednost grafičkog rješenja postiže samo u ravnini, s grafičkim prikazom problema možemo se upoznati samo u dvodimenzionalnom prostoru. Ovaj prikaz je prikladan za sustav ograničenja nejednakosti s dvije varijable ili za sustave jednadžbi u kojima je broj varijabli veći od broja jednadžbi za 2, odnosno broj slobodnih varijabli je dva.
Stoga grafička metoda ima tako 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 vizualnih prikaza rješenja problema linearnog programiranja, grafička metoda je od određenog interesa. Osim toga, omogućuje nam geometrijsku potvrdu valjanosti teoremi linearnog programiranja .
Teorijske osnove grafičke metode
Dakle, ovo je problem linearnog programiranja. Potrebno je pronaći nenegativne vrijednosti varijabli i zadovoljiti sustav nejednakosti
pri kojoj linearni oblik poprima optimalnu vrijednost.
Primjer 3.
Primjer 4. Riješite problem linearnog programiranja pomoću grafičke metode u kojoj trebate pronaći minimum funkcije pod ograničenjima
Nastavljamo zajedno rješavati zadatke grafičkom metodom
Dosadašnji zaključci temeljeni su na činjenici da je skup rješenja problema linearnog programiranja konfiguriran tako da je optimalno rješenje konačno i jedinstveno. Sada pogledajmo primjere u kojima je ovaj uvjet prekršen. U ovim je primjerima poligon rješenja konstruiran kao što je prikazano u prethodnim primjerima; zadržimo se na značajkama koje razlikuju ove iznimne primjere.
Primjer 5. Riješite problem linearnog programiranja pomoću grafičke metode u kojoj trebate pronaći maksimum funkcije pod ograničenjima
Riješenje. Slika prikazuje: neograničeno poliedarsko područje rješenja za ovaj sustav ograničenja, liniju početne razine (crna), vektor (bordo boje) koji pokazuje smjer kretanja linije početne razine za pronalaženje maksimuma ciljne funkcije.
Lako je vidjeti da funkcija F može neograničeno rasti pod zadanim sustavom ograničenja, pa možemo uvjetno napisati da .
Primjer 6. Riješite problem linearnog programiranja pomoću grafičke metode u kojoj trebate pronaći maksimum funkcije pod ograničenjima
Najjednostavnija i najočiglednija metoda linearnog programiranja (LP) je grafička metoda. Koristi se za rješavanje LP problema s dvije varijable. Razmotrimo LP problem u standardnom obliku:
max f(x 1 , x 2 , ..., x n) = ,
, i = 1, 2, …, m,
x j 0, j = 1, 2, …, n.
Stavimo n=2 a problem ćemo razmotriti u avionu. Neka je sustav nejednadžbi konzistentan (ima barem jedno rješenje).
Svaka nejednadžba ovog sustava geometrijski definira poluravninu s rubnom linijom a i 1 x 1 + a i 2 x 2 = b i, i = 1, 2, …, m. Uvjeti nenegativnosti definiraju poluravnine s graničnim ravnim linijama x 1 = 0, odnosno x 2 = 0. Sustav je konzistentan, stoga poluravnine, poput konveksnih skupova, sijekući se čine zajednički dio, koji je konveksan skup i skup je točaka, pri čemu su koordinate svake točke rješenje tog sustava. Skup tih točaka naziva se poligon rješenja. To može biti točka, segment, zraka, omeđeni ili neomeđeni mnogokut.
Dakle, geometrijski, ZLP je traženje takve točke poligona rješenja čije koordinate daju maksimalnu (minimalnu) vrijednost linearnoj funkciji cilja, a sve točke poligona rješenja su dopustiva rješenja.
Linearna jednadžba opisuje skup točaka koje leže na istoj liniji. Linearna nejednadžba opisuje neko područje na ravnini. Odredimo koji dio ravnine opisuje nejednadžba 2x 1 + 3x 2 12.
Prvo, konstruirajmo ravnu liniju 2x 1 + 3x 2= 12. Prolazi kroz točke (6; 0) i (0; 4). Da bi se utvrdilo koja poluravnina zadovoljava nejednadžbu, potrebno je odabrati bilo koju točku na grafu koja ne pripada pravcu i njene koordinate zamijeniti u nejednadžbu. Ako nejednakost vrijedi, tada je dana točka moguće rješenje, a poluravnina koja sadrži točku zadovoljava nejednadžbu. Za zamjenu u nejednadžbu prikladno je koristiti ishodište. Zamijenimo x 1 = x 2 = 0 u nejednadžbu 2x 1 + 3x 2 12. Dobit ćemo 2x0 + 3x0 12. Ova tvrdnja je točna, dakle, nejednadžba 2x 1 + 3x 2 12 odgovara donjoj poluravnini koja sadrži točku (0; 0). To se odražava na grafikonu prikazanom na sl. 1.1.
Slično, sva ograničenja LP problema mogu se grafički prikazati.
Rješenje svake nejednadžbe ZLP sustava ograničenja je poluravnina koja sadrži graničnu liniju i nalazi se s jedne strane od nje. Sjecište poluravnina, od kojih je svaka određena odgovarajućom nejednadžbom sustava, naziva se područjem dopustivih rješenja ili područjem definicije. Mora se zapamtiti da područje izvodljivih rješenja zadovoljava uvjete nenegativnosti ( x j 0, j = 1, 2, …, n). Koordinate bilo koje točke koja pripada domeni definicije valjano su rješenje problema.
Za pronalaženje ekstremne vrijednosti funkcije cilja pri grafičkom rješavanju problema LP koristi se vektor gradijenta čije su koordinate parcijalne derivacije funkcije cilja, tj.
Ovaj vektor pokazuje smjer najbrže promjene funkcije cilja. Izravna linija s 1 x 1 + s 2 x 2 = f(x 0), okomito na vektor gradijenta, je linija razine funkcije cilja. U bilo kojoj točki na liniji razine funkcija cilja ima istu vrijednost. Izjednačimo ciljnu funkciju s konstantnom vrijednošću "A". Mijenjajući vrijednost "a", dobivamo familiju paralelnih linija, od kojih je svaka linija razine funkcije cilja.
Važno svojstvo linije razine linearne funkcije je da kada se linija paralelno pomakne u jednom smjeru, razina samo raste, a kada se pomakne u drugom smjeru samo opada.
S geometrijskog gledišta, u problemu linearnog programiranja, tražimo takvu kutnu točku ili skup točaka iz dopustivog skupa rješenja na kojima se postiže linija najviše (najniže) razine, koja se nalazi dalje (bliže) od ostali u smjeru najbržeg rasta.
Grafička metoda za rješavanje ZLP-a sastoji se od sljedećih koraka.
1. Konstruirano je poligonalno područje dopustivih rješenja (ADS) PLP-a.
2. Vektor gradijenta funkcije cilja (TF) konstruiran je u nekoj točki x 0 koja pripada ODR-u:
3. Linija razine c 1 x 1 + c 2 x 2 = a (a je konstantna vrijednost) - ravna linija okomita na vektor gradijenta - pomiče se u smjeru ovog vektora u slučaju maksimiziranja f (x 1, x 2) dok ne napusti ODR. Granična točka (ili točke) područja tijekom ovog kretanja je najveća točka f(x 1, x 2).
4. Za pronalaženje koordinata maksimalne točke dovoljno je riješiti dvije jednadžbe ravne crte dobivene iz odgovarajućih ograničenja i dajući maksimalnu točku u sjecištu. Vrijednost f(x 1, x 2) pronađena u rezultirajućoj točki je najveća.
Pri minimiziranju (maksimiziranju) funkcije f(x 1, x 2) linija razine se pomiče u smjeru suprotnom od vektora gradijenta. Ako pravac koji odgovara liniji razine ne napušta ODR tijekom svog kretanja, tada minimum (maksimum) funkcije f(x 1, x 2) ne postoji.
Ako je linija razine paralelna s bilo kojim funkcionalnim ograničenjem problema, tada će se optimalna vrijednost CF-a postići u bilo kojoj točki tog ograničenja koja leži između dviju optimalnih kutnih točaka, i, prema tome, bilo koja od tih točaka je optimalno rješenje ZLP-a. Moguće situacije za grafičko rješavanje LP problema prikazane su u tablici. 1.3.
Tablica 1.3
| № | Vrsta ODR-a | Vrsta optimalnog rješenja | Bilješke |
| Poligonalno zatvoreno | Jedina odluka | ||
| Jedina odluka | |||
| Poligonalni | CF nije ograničen odozdo | ||
| CF nije ograničen odozgo | |||
| Poligonalno otvoreno | Jedina odluka | ||
| Beskrajna rješenja | |||
| Segment linije | Jedina odluka |
Razmotrimo grafičko rješenje problema linearnog programiranja koristeći sljedeći primjer.
Primjer 1.1. Planiranje proizvodnje šivaćeg poduzeća (problem odijela).
Planirano je izdati dvije vrste odijela - muško i žensko. Za žensko odijelo potrebno je 1 m vune, 2 m lavsana i 1 osoba/dan rada. Za muško odijelo - 3,5 m vune, 0,5 m lavsana i 1 osoba / dan rada. Ukupno je 350 m vune, 240 m lavsana i 150 čovjek/dana rada. Potrebno je odrediti koliko odijela svake vrste treba izraditi da bi se osigurala maksimalna zarada, ako je zarada od prodaje ženskog odijela 10 novčanih jedinica, a od muškog 20 novčanih jedinica. Treba imati na umu da je potrebno sašiti najmanje 60 muških odijela.
Uvedimo sljedeće oznake: x 1 - broj ženskih odijela; x 2 – broj muških odijela. Zarada od prodaje ženskih odijela je 10x 1, a od prodaje muških odijela - 20x 2, tj. potrebno je maksimizirati funkciju cilja:
10x 1 + 20x 2
Ograničenja zadatka imaju oblik:
x 1 + x 2 150,
2 x 1 + 0,5 x 2 240,
x 1 + 3,5 x 2 350,
x 2 60,
x 1 0.
Prvo ograničenje rada je x 1 + x 2 150. Pravac x 1 + x 2 = 150 prolazi kroz točke (150; 0) i (0; 150) (slika 1.2).
Drugo ograničenje na lavsan je 2 x 1 + 0,5 x 2 240. Ravna linija 2 x 1 + 0,5 x 2 = 240 prolazi kroz točke (120; 0) i (0; 480). Treće ograničenje na vunu x 1 + 3,5x 2 350. Dodajmo četvrto ograničenje na broj muških odijela x 2 60. Rješenje ove nejednadžbe je poluravnina koja leži iznad pravca x 2 = 60. Na sl. 1.3 područje izvedivih rješenja je osjenčano. Za određivanje smjera kretanja prema optimumu konstruiramo vektor gradijenta čije su koordinate parcijalne derivacije ciljne funkcije, tj.
Da biste konstruirali takav vektor, trebate spojiti točku (10;20) s ishodištem. Kod maksimiziranja funkcije cilja potrebno je kretati se u smjeru vektora gradijenta, a kod minimiziranja u suprotnom smjeru. Radi praktičnosti, možete konstruirati vektor proporcionalan vektoru . Dakle, na Sl. 1.4 prikazuje vektor gradijenta (30;60).
Za određivanje smjera kretanja prema optimumu konstruiramo vektor gradijenta čije su koordinate parcijalne derivacije ciljne funkcije, tj.
U našem slučaju, pomicat ćemo liniju razine dok ne napusti područje mogućih rješenja. U krajnjoj, kutnoj točki, postiže se maksimum funkcije cilja. Da biste pronašli koordinate ove točke, dovoljno je riješiti dvije jednadžbe ravne linije dobivene iz odgovarajućih ograničenja i dajući maksimalnu točku na sjecištu:
x 1 + 3,5 x 2 = 350,
x 1 + x 2 = 150.
Odavde je lako zapisati rješenje izvornog ZLP-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 POMOĆU DODATKA ZA PRETRAŽIVANJE RJEŠENJA U EXCEL OKRUŽENJU
1.3.1. Opće informacije o radu s proračunskom tablicom Excel
Razmotrimo neke aspekte rada s procesorom proračunskih tablica Excel, koji će pojednostaviti izračune potrebne za rješavanje problema optimizacije. Tablični procesor je softverski proizvod dizajniran za automatizaciju obrade tabličnih podataka.
Excel elementi zaslona. Nakon pokretanja programa Excel na ekranu se pojavljuje tablica čiji je izgled prikazan na slici 1.5.
Ova se slika naziva radni list. To je mreža redaka i stupaca, čija sjecišta tvore pravokutnike koji se nazivaju ćelije. Radni listovi namijenjeni su za unos podataka, izvođenje izračuna, organiziranje baze podataka itd. Prozor programa Excel prikazuje glavne elemente programa: naslovnu traku, traku izbornika, statusnu traku, gumbe za upravljanje prozorom.
Rad s formulama. Programi za proračunske tablice koriste formule za izvođenje mnogo različitih izračuna. Pomoću programa Excel možete brzo izraditi formulu. Formula se sastoji od tri glavna dijela:
1) znak jednakosti;
2) skup vrijednosti ili referenci u ćelijama s kojima se izvode izračuni;
3) operatori.
4) Ako nema znaka jednakosti, tada Excel podatke ne tumači kao formulu, već kao podatke unesene u ćeliju. Formule se mogu unijeti izravno u ćeliju ili u traku formule - bilo tekst ili brojevi. U tom slučaju trebate izvršiti sljedeće korake:
· označite ćeliju koja treba sadržavati formulu i unesite znak (=);
· unesite operator ili znak radnje;
· odaberite drugu ćeliju uključenu u formulu;
· pritisnite tipku Enter.
Unesena formula pojavit će se u traci formule, a rezultat izračuna u ćeliji.
Korištenje funkcija u formulama. Kako biste olakšali unos formula, možete koristiti Excel funkcije. Funkcije su formule ugrađene u Excel. Excel sadrži mnoge formule. Grupiraju se u različite vrste: logičke, matematičke, inženjerske, statističke itd.
Da biste aktivirali određenu formulu, kliknite gumbe Umetni, Funkcije. Prozor čarobnjaka za funkcije koji se pojavljuje na lijevoj strani sadrži popis vrsta funkcija. Nakon odabira vrste, s desne strane nalazi se popis samih funkcija. Funkcija se odabire klikom na odgovarajući naziv.
Različite funkcije izvode različite vrste izračuna prema određenim pravilima. Kada je funkcija jedan objekt u ćeliji radnog lista, počinje znakom (=), nakon čega slijedi naziv funkcije, a zatim argumenti funkcije, u zagradama.
Find a Solution dodatak je programu Excel koji vam omogućuje rješavanje problema optimizacije. Ako naredba Traži rješenje nije dostupna u izborniku Alati, morate preuzeti ovaj dodatak. Odaberite naredbu Tools => Add-ons i aktivirajte dodatak Search for a solution. Ako se ovaj dodatak ne nalazi u dijaloškom okviru Dodaci, trebate otići na upravljačku ploču sustava Windows, kliknuti ikonu Dodaj ili ukloni programe i upotrijebiti Excel (ili Office) instalacijski program za instalaciju dodatka Pronađi rješenje -u.
Nakon odabira naredbi Alati => Traži rješenje, pojavit će se dijaloški okvir Traži rješenje.
Postoje tri glavne opcije u dijaloškom okviru Find Solution;
Postavite ciljnu ćeliju.
Mijenjanje stanica.
Ograničenja.
Najprije morate ispuniti polje Postavi ciljnu ćeliju. U svim zadacima za alat Find a Solution optimiziran je rezultat u jednoj od ćelija radnog lista. Ciljna ćelija povezana je s drugim ćelijama na tom radnom listu pomoću formula. Alat Pronađi rješenje koristi formule koje proizvode rezultat u ciljnoj ćeliji za testiranje mogućih rješenja. Možete odabrati pronaći najmanju ili najveću vrijednost za ciljnu ćeliju ili postaviti određenu vrijednost.
Druga važna opcija u alatu Find Solution je opcija Promjena ćelija. Ovdje navedete ćelije čije će se vrijednosti promijeniti kako bi se optimizirao rezultat u ciljnoj ćeliji. Možete navesti do 200 promjenjivih ćelija kako biste pronašli rješenje. Dva su glavna zahtjeva za te ćelije: ne smiju sadržavati formule, a promjene u njihovim vrijednostima moraju se odraziti na promjenu rezultata u ciljnoj ćeliji. Drugim riječima, ciljna stanica ovisi o stanicama koje se modificiraju.
Treći parametar koji je potrebno unijeti na kartici Traži rješenje su ograničenja.
Za rješavanje problema potrebno je:
1) navesti adrese ćelija u koje će biti smješten rezultat odluke (promjenjive ćelije);
2) upisati početne podatke;
3) uvesti ovisnost za funkciju cilja;
4) uvesti ovisnosti za ograničenja,
5) pokrenite naredbu Traži rješenja;
6) dodijeliti ćeliju ciljnoj funkciji (set target cell);
7) uvoditi ograničenja;
8) unesite parametre za rješavanje PLP-a.
Razmotrimo tehnologiju rješenja koristeći uvjete primjera 1.1 (problem odijela).
Ekonomski i 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 maks
Ograničenja zadatka imaju oblik:
x 1 + x 2 150 - ograničenje rada;
2 x x 1 + 0,5 x x 2.240 - ograničenje na lavsan;
x 1 + 3,5 x x 2 350 - granica vune;
x 2 60 - ograničenje na muška odijela;
x 1 0 - ograničenje ženskih odijela.
1. Odredite adrese ćelija u koje će biti smješten rezultat rješenja (promjenjive ćelije).
Označimo s x 1 , x 2 broj boja svake vrste. U našem problemu, optimalne vrijednosti vektora = (x 1, x 2) bit će smještene u ćelije A2: B2, optimalna vrijednost funkcije cilja - u ćeliju S3.
2. Unesite početne podatke.
Unesite početne podatke zadatka kao što je prikazano na sl. 1.6.
3. Uvesti ovisnost za funkciju cilja.
· Postavite pokazivač u ćeliju "NW", ćelija će biti odabrana.
· Postavite kursor na gumb Function Wizard koji se nalazi na alatnoj traci.
· Unesi Unesi. Na zaslonu se pojavljuje dijaloški okvir čarobnjaka za funkcije 1. od 2. koraka.
· U prozoru Funkcije odaberite liniju SUMPROIZVOD (slika 1.7). Na ekranu
· pojavljuje se dijaloški okvir SUMPRODUCT (slika 1.8).
· Unesite u red Array 1 A2:B2.
· Unesite AZ:VZ u red Niza 2.
Niz 1 koristit će se pri unosu ovisnosti za ograničenja, tako da se mora napraviti apsolutna referenca na ovaj niz. Na sl. Slika 1.9 pokazuje da je funkcija uvedena u ćeliju SZ.
5. Unesite ovisnosti za ograničenja (Slika 1.10).
· Postavite pokazivač u ćeliju NW.
· Na alatnoj traci nalazi se gumb Kopiraj u međuspremnik.
· Postavite kursor u ćeliju C4.
· Postavite kursor u ćeliju C5.
· Na alatnoj traci, gumb Zalijepi iz međuspremnika.
· Postavite pokazivač u ćeliju Sat.
· Na alatnoj traci, gumb Zalijepi iz međuspremnika.
· Postavite kursor u ćeliju C7.
· Na alatnoj traci kliknite gumb Zalijepi iz međuspremnika. (Sadržaj ćelija C4-C7 mora biti označen. One moraju sadržavati informacije, kao što je prikazano na primjer na slici 1.11; sadržaj ćelije C5 prikazan je kao primjer.)
· U liniji Izbornik postavite pokazivač miša na Servis. U proširenom izborniku odaberite naredbu Traži rješenje. Pojavljuje se dijaloški okvir Traženje rješenja (Slika 1.12).
5. Pokrenite naredbu Traži rješenje.
6. Dodijelite ćeliju ciljnoj funkciji (postavite ciljnu ćeliju), označite adrese ćelija koje treba promijeniti.
· Postavite kursor u redak Postavi ciljnu ćeliju.
· Unesite adresu ćelije $S$3.
· Unesite tip funkcije cilja ovisno o uvjetima vašeg problema. Da biste to učinili, zabilježite čemu je funkcija cilja jednaka - Maksimalna vrijednost ili Minimalna vrijednost.
· Postavite kursor u red mijenjajući ćelije.
· Unesite adrese potrebnih varijabli A$2:B$2 (slika 1.13).
7. Uvedite ograničenja.
· Postavite pokazivač miša na gumb Dodaj. Pojavljuje se dijaloški okvir Add Constraint.
· Unesite znak zabrane.
· U retku Ograničenje unesite adresu $D$4 (Slika 1.14).
· Postavite pokazivač miša na gumb Dodaj. Ponovno će se pojaviti dijaloški okvir Dodaj ograničenje.
· Unesite preostala ograničenja problema koristeći gore opisani algoritam.
· Nakon unosa posljednjeg ograničenja kliknite na gumb U redu. Na ekranu će se pojaviti dijaloški okvir Traži rješenje s unesenim uvjetima (Slika 1.15).
8. Unesite parametre za rješavanje problema linearnog programiranja.
· U dijaloškom okviru postavite pokazivač miša na gumb Mogućnosti. Na ekranu će se pojaviti dijaloški okvir Mogućnosti pretraživanja rješenja (Slika 1.16).
· Označite okvire u Linearni model (ovo će osigurati korištenje simpleks metode) i Nenegativne vrijednosti.
· Postavite pokazivač miša na gumb OK. Na zaslonu će se pojaviti dijaloški okvir Search for Solution.
· Postavite pokazivač miša na gumb Pokreni.
Nakon kratkog vremena pojavit će se dijaloški okvir Rezultati pretraživanja rješenja i početna tablica s popunjenim ćelijama AZ:VZ za vrijednosti x i i ćelijom SZ s maksimalnom vrijednošću funkcije cilja (slika 1.17).
Ako navedete vrstu izvješća Stabilnost, možete dobiti dodatne informacije o optimalnom rješenju (Sl. 1.18).
Kao rezultat rješavanja problema, dobiven je odgovor: potrebno je sašiti 70 komada. ženska odijela i 80 kom. muška odijela kako biste ostvarili maksimalnu zaradu od 2300 USD.
1.4. DUALNOST U PROBLEMIMA LINEARNOG PROGRAMIRANJA. ANALIZA DOBIVENIH OPTIMALNIH RJEŠENJA
Godine 1975. naš sunarodnjak L.V. Kantorovich je dobio Nobelovu nagradu za ekonomiju (zajedno s američkim ekonomistom T. Koopmansom) za razvoj teorije optimalnog korištenja resursa (vidi Dodatak 1).
Usko povezan sa svakim problemom linearnog programiranja je drugi linearni problem koji se zove dualni; izvorni problem naziva se izvorni ili izravni. Veza između izvornog i dualnog problema leži, posebice, u činjenici da se rješenje jednog od njih može dobiti izravno 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 zapravo je neovisni problem linearnog programiranja i može se riješiti neovisno o drugom.
Dualni problem u odnosu na izvorni sastavlja se prema sljedećim pravilima:
1) funkcija cilja izvornog problema formulirana je kao maksimum, a funkcija cilja dualnog problema formulirana je kao minimum, dok u problemu maksimuma sve nejednakosti u funkcionalnim ograničenjima imaju oblik (), u problemu minimuma imaju oblik ( );
2) matrica A, sastavljena od koeficijenata za nepoznata ograničenja u sustavu izvornog problema, i slična matrica A T u dualnom problemu dobivene su jedna iz druge transponiranjem;
3) broj varijabli u dualnom problemu jednak je broju funkcionalnih ograničenja u izvornom problemu, a broj ograničenja u sustavu dualnog problema jednak je broju varijabli u izvornom;
4) koeficijenti za nepoznanice u funkciji cilja dualnog problema su slobodni članovi u sustavu ograničenja izvornog problema, a desne strane u ograničenjima dualnog problema su koeficijenti za nepoznanice u objektivna funkcija izvornika; j 0.
Dva predstavljena problema čine par simetričnih dualnih problema. Glavne tvrdnje o međusobno dualnim problemima sadržane su u sljedeća dva teorema.
Prvi teorem dualnosti. Za međusobno dualne probleme javlja se jedan od međusobno isključivih slučajeva.
1. U izravnim i dualnim problemima postoje optimalna rješenja,
u ovom slučaju vrijednosti cilja funkcioniraju na optimalnim rješenjima
odgovarati
2. U izravnom problemu dopustivi skup nije prazan, a funkcija cilja na tom skupu nije omeđena odozgo. U tom će slučaju dualni problem imati prazan dopustivi skup.
3. U dualnom problemu dopustivi skup nije prazan, a funkcija cilja na tom skupu nije omeđena odozdo. U tom slučaju ispada da je dopustivi skup izravnog problema prazan.
4. Oba razmatrana problema imaju prazne dopustive skupove.
Drugi teorem dualnosti (komplementarni teorem o nerigidnosti). Neka = ( x 1, x 2,..., x n) je prihvatljivo rješenje izravnog problema, a = (y 1,y 2,...,y t) je prihvatljivo rješenje dualnog problema. Da bi oni bili optimalno rješenje izravnog, odnosno dualnog problema, potrebno je i dovoljno da vrijede sljedeće relacije:
(1.4)
(1.5)
Uvjeti (1.4) i (1.5) omogućuju da se, znajući optimalno rješenje jednog od međusobno dualnih problema, pronađe optimalno rješenje drugog problema.
Razmotrimo još jedan teorem, čiji će se zaključci dalje koristiti.
Teorem o procjeni. Vrijednosti varijabli y i u optimalnom rješenju dualnog problema predstavljaju procjene utjecaja slobodnih članova b i sustava ograničenja (nejednakosti) izravnog problema na vrijednost
Rješavanjem ZLP-a simpleks metodom istovremeno rješavamo dualni ZLP. Varijable dualnog problema y i nazivaju se objektivno određene procjene.
Razmotrimo ekonomsku interpretaciju dualnog problema koristeći problem tepiha kao primjer.
Primjer 1 .2. Koristeći tvrdnju problema s tepihom, riješite sljedeće zadatke.
1. Formulirajte ekonomsko-matematički model problema tepiha za maksimalne ukupne troškove proizvodnje, koristeći podatke u tablici. 1.1.
2. Koristeći Search for a solution pronađite proizvodni plan pri kojem će ukupni trošak proizvodnje biti maksimalan.
3. Formulirajte ekonomsko-matematički model dualnog problema na problem tepiha.
4. Pronađite optimalni plan za dualni problem, koristeći teoreme dualnosti, objasnite jednakost nuli X 1 i X 4.
5. Pomoću protokola Solution Search provedite analizu rezultirajućeg optimalnog rješenja izvornog problema.
6. Odredite kako će se ukupni trošak i plan proizvodnje promijeniti kada se vijek trajanja cijevi poveća za 12 jedinica.
1. Formulirajmo ekonomski i matematički model problema.
Označimo s X 1, X 2, X 3, X 4 broj tepiha svake vrste. Ciljna funkcija ima oblik
F(X) = 3X 1 + 4X 2 + 3X 3 + X 4 max,
i ograničenja resursa
7H 1 + 2H 2 + 2H 3 + 6X 4 80,
5H 1 + 8H 2 + 4 X 3 + ZH 4 480,
2X 1 + 4 X 2 + X 3 + 8X 4 130,
X 1, X 2, X 3, X 4 0.
2. Potražite optimalni plan izdavanja.
Problem ćemo riješiti pomoću Excel dodatka Traži rješenje. Tehnologija rješavanja problema detaljno je obrađena u problemu kostima. U našem problemu, optimalne vrijednosti vektora X = (X 1, X 2, X 3, X 4) bit će smještene u ćelije VZ:EZ, optimalna vrijednost funkcije cilja - u ćeliju F4.
Unesite početne podatke. Najprije opisujemo ciljnu funkciju pomoću funkcije - SUMPROIZVOD (slika 1.19). Zatim ćemo unijeti podatke za lijeve dijelove ograničenja. U Search for a solution unijet ćemo smjer funkcije cilja, adrese traženih varijabli te dodati ograničenja. Na ekranu će se pojaviti dijaloški okvir Traži rješenje s unesenim uvjetima (Slika 1.20).
Nakon unosa parametara za rješavanje problema kliknite gumb Izvrši. Na ekranu će se pojaviti poruka da je rješenje pronađeno (Slika 1.21).
Dobiveno rješenje znači da je maksimalni prihod 150 tisuća rubalja. tvornica može primiti 30 tepiha druge vrste i 10 tepiha treće vrste nakon proizvodnje. U ovom slučaju, resursi "rad" i "oprema" bit će u potpunosti iskorišteni, a od 480 kg pređe (resurs "sirovina") iskoristit će se 280 kg.
Izrada izvješća na temelju rezultata traženja rješenja. Excel omogućuje prikaz rezultata traženja rješenja u obliku izvješća (tablica 1.4). Postoje tri vrste takvih izvješća:
· Rezultati (odgovor). Izvješće uključuje početne i konačne vrijednosti ciljnih i modificiranih ćelija te dodatne informacije o ograničenjima.
· Stabilnost (osjetljivost). Izvješće koje sadrži informacije o osjetljivosti rješenja na male promjene u ćelijama koje se mijenjaju ili u formulama ograničenja.
· Ograničenja. Uz izvorne i odredišne vrijednosti zahvaćenih i ciljnih stanica, izvješće uključuje gornje i donje granice vrijednosti koje utjecajne stanice mogu prihvatiti ako su ograničenja zadovoljena.
Ako problem linearnog programiranja ima samo dvije varijable, tada se može riješiti grafički.
Razmotrimo problem linearnog programiranja s dvije varijable i:
(1.1)
;
(1.2)
Ovdje su proizvoljni brojevi. Zadatak može biti ili pronaći maksimum (max) ili pronaći minimum (min). Sustav ograničenja može sadržavati i znakove i znakove.
Konstrukcija domene izvedivih rješenja
Grafička metoda za rješavanje problema (1) je sljedeća.
Prvo crtamo koordinatne osi i odabiremo mjerilo. Svaka od nejednakosti sustava ograničenja (1.2) definira poluravninu omeđenu odgovarajućom ravnom linijom.
Dakle, prva nejednakost
(1.2.1)
definira poluravninu omeđenu pravcem. S jedne strane ove ravne linije, a s druge strane. Na vrlo ravnoj liniji. Da bismo saznali s koje strane vrijedi nejednakost (1.2.1), odaberemo proizvoljnu točku koja ne leži na pravcu. Zatim zamijenimo koordinate te točke u (1.2.1). Ako nejednakost vrijedi, tada poluravnina sadrži odabranu točku. Ako nejednakost ne vrijedi, tada se poluravnina nalazi s druge strane (ne sadrži odabranu točku). Osjenčaj poluravninu za koju vrijedi nejednakost (1.2.1).
Isto činimo i za preostale nejednakosti sustava (1.2). Na ovaj način dobivamo osjenčane poluravnine. Točke područja izvodljivih rješenja zadovoljavaju sve nejednadžbe (1.2). Stoga je grafički gledano područje izvodljivih rješenja (ADA) sjecište svih izgrađenih poluravnina. Sjenčanje ODR-a. To je konveksni mnogokut čija lica pripadaju konstruiranim ravnima. Također, ODF može biti neograničena konveksna figura, segment, zraka ili ravna linija.
Također se može dogoditi da poluravnine nemaju zajedničkih točaka. Tada je domena izvodljivih rješenja prazan skup. Ovaj problem nema rješenja.
Metoda se može pojednostaviti. Ne morate zasjenčiti svaku poluravninu, ali prvo konstruirajte sve ravne linije
(2)
Zatim odaberite proizvoljnu točku koja ne pripada nijednom od ovih pravaca. Zamijenite koordinate te točke u sustav nejednadžbi (1.2). Ako su sve nejednakosti zadovoljene, tada je područje izvodljivih rješenja ograničeno konstruiranim ravnim linijama i uključuje odabranu točku. Osjenčamo područje mogućih rješenja duž granica linija tako da uključuje odabranu točku.
Ako barem jedna nejednakost nije zadovoljena, odaberite drugu točku. I tako dalje dok se ne nađe jedna točka čije koordinate zadovoljavaju sustav (1.2).
Pronalaženje ekstrema funkcije cilja
Dakle, imamo osjenčanu regiju izvedivih rješenja (ADA). Ograničena je izlomljenom linijom koja se sastoji od odsječaka i zraka koje pripadaju izgrađenim ravnim linijama (2). ODS je uvijek konveksan skup. Može biti ili ograničen skup ili neomeđen po nekim pravcima.
Sada možemo tražiti ekstrem funkcije cilja
(1.1)
.
Da biste to učinili, odaberite bilo koji broj i izgradite ravnu liniju
(3)
.
Radi lakšeg daljnjeg prikaza, pretpostavljamo da ova ravna linija prolazi kroz ODR. Na ovom pravcu funkcija cilja je konstantna i jednaka . takva ravna crta naziva se linija razine funkcije. Ova pravac dijeli ravninu na dvije poluravnine. Na jednoj poluravnini
.
Na drugoj poluravni
.
To jest, s jedne strane ravne crte (3) funkcija cilja raste. I što dalje pomičemo točku od prave (3), vrijednost će biti veća. S druge strane pravca (3) funkcija cilja opada. I što dalje pomičemo točku od ravne linije (3) na drugu stranu, vrijednost će biti manja. Ako povučemo ravnu liniju paralelnu s linijom (3), tada će nova ravna crta također biti linija razine funkcije cilja, ali s drugom vrijednošću.
Dakle, da bi se našla maksimalna vrijednost funkcije cilja, potrebno je povući ravnu liniju paralelnu s ravnom linijom (3), što dalje od nje u smjeru rastućih vrijednosti, a koja prolazi kroz barem jednu točku od ODD. Za pronalaženje minimalne vrijednosti funkcije cilja potrebno je povući ravnu liniju paralelnu s pravcem (3) i što dalje od nje u smjeru opadanja vrijednosti, a koja prolazi kroz barem jednu točku ODD.
Ako je ODR neograničen, može doći do slučaja kada se takva izravna crta ne može povući. Odnosno, kako god ravnu liniju udaljili od linije razine (3) u smjeru porasta (smanjenja), ravna će uvijek prolaziti kroz ODR. U ovom slučaju može biti proizvoljno velika (mala). Stoga ne postoji maksimalna (minimalna) vrijednost. Problem nema rješenja.
Promotrimo slučaj kada krajnji pravac paralelan s proizvoljnim pravcem oblika (3) prolazi kroz jedan vrh ODR poligona. Iz grafa odredimo koordinate tog vrha. Tada se najveća (minimalna) vrijednost funkcije cilja određuje formulom:
.
Rješenje problema je
.
Također može postojati slučaj kada je ravna linija paralelna s jednom od strana ODR-a. Tada pravac prolazi kroz dva vrha poligona ODR. Odredimo koordinate tih vrhova. Da biste odredili najveću (minimalnu) vrijednost funkcije cilja, možete koristiti koordinate bilo kojeg od ovih vrhova:
.
Problem ima beskonačno mnogo rješenja. Rješenje je bilo koja točka koja se nalazi na segmentu između točaka i , uključujući točke i same sebe.
Primjer rješavanja problema linearnog programiranja grafičkom metodom
Zadatak
Tvrtka proizvodi haljine dva modela A i B. Koriste se tri vrste tkanina. Za izradu jedne haljine modela A potrebno je 2 m tkanine prve vrste, 1 m tkanine druge vrste, 2 m tkanine treće vrste. Za izradu jedne haljine modela B potrebno je 3 m tkanine prve vrste, 1 m tkanine druge vrste, 2 m tkanine treće vrste. Zalihe tkanine prve vrste su 21 m, druge vrste - 10 m, treće vrste - 16 m. Puštanje jednog proizvoda vrste A donosi prihod od 400 den. jedinica, jedan proizvod tipa B - 300 den. jedinice
Napravite plan proizvodnje koji će poduzeću osigurati najveći prihod. Riješi zadatak grafički.
Riješenje
Neka varijable i označavaju broj proizvedenih haljina, modela A odnosno B. 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 bit će:
(m)
Budući da broj proizvedenih haljina ne može biti negativan, dakle
i .
Prihod od proizvedenih haljina bit će:
(den. jedinice)
Tada ekonomsko-matematički model problema ima oblik:
Rješavamo ga grafički.
Nacrtamo koordinatne osi i .
Gradimo ravnu liniju.
U .
U .
Nacrtajte ravnu liniju kroz točke (0; 7) i (10,5; 0).
Gradimo ravnu liniju.
U .
U .
Nacrtaj ravnu liniju kroz točke (0; 10) i (10; 0).
Gradimo ravnu liniju.
U .
U .
Nacrtajte ravnu liniju kroz točke (0; 8) i (8; 0).
Područje osjenčamo tako da točka (2; 2) padne u osjenčani dio. Dobivamo četverokut OABC.
(A1.1) .
U .
U .
Nacrtajte ravnu liniju kroz točke (0; 4) i (3; 0).
Nadalje primjećujemo da budući da su koeficijenti i funkcije cilja pozitivni (400 i 300), ona raste kako i raste. Povučemo pravac paralelan s pravcem (A1.1), što dalje od njega u smjeru povećanja , a prolazi kroz barem jednu točku četverokuta OABC. Takav pravac prolazi točkom C. Iz konstrukcije odredimo njegove koordinate.
.
Rješenje problema: ;
Odgovor
.
Odnosno, da bi se ostvario najveći prihod, potrebno je napraviti 8 haljina modela A. Zarada će biti 3200 den. jedinice
Primjer 2
Zadatak
Grafički riješiti problem linearnog programiranja.
Riješenje
Rješavamo ga grafički.
Nacrtamo koordinatne osi i .
Gradimo ravnu liniju.
U .
U .
Nacrtajte ravnu liniju kroz točke (0; 6) i (6; 0).
Gradimo ravnu liniju.
Odavde.
U .
U .
Nacrtajte ravnu liniju kroz točke (3; 0) i (7; 2).
Gradimo ravnu liniju.
Gradimo ravnu liniju (os apscisa).
Područje dopustivih rješenja (ADA) ograničeno je konstruiranim ravnim linijama. Da bismo saznali koju stranu, uočavamo da točka pripada ODR-u jer zadovoljava sustav nejednakosti:
Područje duž granica izgrađenih linija osjenčamo tako da točka (4; 1) padne u osjenčani dio. Dobili smo trokut ABC.
Gradimo proizvoljni pravac razine funkcije cilja, npr.
.
U .
U .
Nacrtajte ravnu liniju kroz točke (0; 6) i (4; 0).
Budući da ciljna funkcija raste s porastom i , povlačimo ravnu liniju paralelnu s ravninom i što dalje od nje u smjeru povećanja , a prolazi kroz barem jednu točku trokuta ABC. Takav pravac prolazi točkom C. Iz konstrukcije odredimo njegove koordinate.
.
Rješenje problema: ;
Odgovor
Primjer bez rješenja
Zadatak
Grafički riješiti problem linearnog programiranja. Nađite najveću i najmanju vrijednost funkcije cilja.
Riješenje
Zadatak rješavamo grafički.
Nacrtamo koordinatne osi i .
Gradimo ravnu liniju.
U .
U .
Nacrtajte ravnu liniju kroz točke (0; 8) i (2.667; 0).
Gradimo ravnu liniju.
U .
U .
Nacrtajte ravnu liniju kroz točke (0; 3) i (6; 0).
Gradimo ravnu liniju.
U .
U .
Nacrtajte ravnu liniju kroz točke (3; 0) i (6; 3).
Ravne linije su koordinatne osi.
Područje prihvatljivih rješenja (ADA) ograničeno je konstruiranim ravnima i koordinatnim osima. Da bismo saznali koju stranu, uočavamo da točka pripada ODR-u jer zadovoljava sustav nejednakosti:
Osjenčamo područje tako da točka (3; 3) padne u osjenčani dio. Dobivamo neomeđenu površinu omeđenu izlomljenom linijom ABCDE.
Gradimo proizvoljni pravac razine funkcije cilja, npr.
(A3.1) .
U .
U .
Nacrtajte ravnu liniju kroz točke (0; 7) i (7; 0).
Budući da su koeficijenti i pozitivni, raste s povećanjem i .
Da biste pronašli maksimum, potrebno je povući paralelnu liniju koja je što dalje u smjeru povećanja , a prolazi kroz barem jednu točku područja ABCDE. Međutim, budući da je područje neograničeno na strani velikih vrijednosti i , takva se ravna crta ne može povući. Bez obzira koju liniju povukli, uvijek će postojati točke u regiji koje su udaljenije u smjeru povećanja i . Stoga ne postoji maksimum. možete ga učiniti velikim koliko želite.
Tražimo minimum. Nacrtamo ravnu liniju paralelnu s ravnom linijom (A3.1) i što dalje od nje u smjeru opadanja , a koja prolazi kroz barem jednu točku područja ABCDE. Takav pravac prolazi točkom C. Iz konstrukcije odredimo njegove koordinate.
.
Minimalna vrijednost funkcije cilja:
Odgovor
Ne postoji najveća vrijednost.
Minimalna vrijednost
.
Razmotrimo prvo najjednostavniji slučaj, kada su točno dvije varijable uključene u LLP:
Svaka od nejednakosti (a)-(b) sustava ograničenja problema (3.8) geometrijski definira poluravninu, redom, s graničnim ravnima, X 1 =0 i X 2 =0. Svaka od rubnih linija dijeli ravninu x 1 Ox 2 na dvije poluravnine. Sva rješenja izvorne nejednadžbe leže u jednoj od formiranih poluravnina (svih točaka poluravnine) i stoga zamjenom koordinata bilo koje njezine točke u odgovarajuću nejednadžbu ona se pretvara u pravi identitet. Uzimajući to u obzir, određuje se poluravnina u kojoj leže rješenja nejednadžbe, tj. odabirom bilo koje točke iz bilo koje poluravnine i zamjenom njezinih koordinata u odgovarajuću nejednadžbu. Ako nejednakost vrijedi za danu točku, onda vrijedi i za bilo koju drugu točku iz iste poluravnine. Inače, rješenja nejednadžbe leže u drugoj poluravnini.
Ako je sustav nejednadžbi (a)-(b) konzistentan, tada je područje njegovih rješenja skup točaka koje pripadaju svim navedenim poluravninama. Kako je skup sjecišnih točaka tih poluravnina konveksan, područje dopuštenih rješenja problema (3.8) je konveksan skup, koji se naziva poligon rješenja (ranije uvedeni termin “poliedar rješenja” obično se koristi ako je n 3 ). Stranice ovog mnogokuta leže na ravnim crtama, čije su jednadžbe dobivene iz izvornog sustava ograničenja zamjenom znakova nejednakosti točnim znakovima jednakosti.
Dakle, početni ZLP sastoji se od pronalaska točke u poligonu odluke u kojoj funkcija cilja F poprima najveću (minimalnu) vrijednost.
Ova točka postoji kada poligon rješenja nije prazan i funkcija cilja na njemu je omeđena odozgo. U navedenim uvjetima, na jednom od vrhova poligona rješenja funkcija cilja poprima maksimalnu vrijednost. Da biste odredili ovaj vrh, konstruirajte liniju razine L: c 1 x 1 +c 2 x 2 =h (gdje je h neka konstanta), okomitu na vektor gradijenta i prolazi kroz poligon rješenja, i pomaknite je paralelno duž vektora gradijenta sve dok ne prođe kroz svoju posljednju zajedničku točku presjeka s poligonom rješenja (prilikom konstruiranja gradijentnog vektora, točka (c 1 ; c 2) je položena u ravninu x 1 Ox 2 i na nju se povlači usmjereni segment iz ishodište koordinata). Koordinate navedene točke određuju optimalni plan za ovaj zadatak.
Sumirajući sve navedeno, predstavljamo algoritam za grafičku metodu rješavanja ZLP-a.
Algoritam za grafičku metodu rješavanja ZLP
1. Konstruirajte poligon rješenja zadan sustavom ograničenja izvornog ZLP.
2. Ako je konstruirani poligon rješenja prazan skup, tada izvorni ZLP nema rješenja. U suprotnom, konstruirajte vektor gradijenta i nacrtajte proizvoljnu liniju razine L, pomičući je, kada rješavate maksimalni problem, u smjeru vektora (ili u suprotnom smjeru za minimalni problem) kako biste odredili ekstremnu točku poligona rješenja, gdje se postiže maksimum (minimum) ciljne funkcije problema .
3. Izračunajte koordinate pronađene optimalne točke 
, rješavanje sustava jednadžbi dviju rubnih linija koje se u njemu sijeku.
4. Zamjenom pronađenog optimalnog rješenja u ciljnu funkciju zadatka izračunati njezinu optimalnu vrijednost, tj. 
.
Pri grafičkoj konstrukciji skupa dopustivih rješenja PLP-a (poligona rješenja) moguće su sljedeće situacije.
