zadaci linearno programiranje

2.1. Definicija i oblici bilježenja

U slučaju kada su sva ograničenja jednadžbe i sve varijable zadovoljavaju uvjet nenegativnosti, problem linearnog programiranja se naziva kanonski. Može se prikazati u koordinatnom, vektorskom ili matričnom notnom obliku.

a) kanonski problem LP u koordinatnom obliku ima oblik:

,
.

Ovaj problem se može napisati pomoću znaka za zbrajanje:

,

,

,
,
.

b) kanonski LP problem u vektorskom obliku ima oblik: ,

,

Gdje
;
;

,
;;
.

c) kanonski LP problem u matričnom obliku ima oblik:

,
,

Gdje
,,.

2.2. Redukcija općeg linearnog problema

programiranje u kanonski oblik

Pri sastavljanju matematičkih modela ekonomskih problema ograničenja se uglavnom oblikuju u sustave nejednakosti. Stoga je potrebno znati prijeći s njih na sustave jednadžbi. Na primjer, razmotrite linearnu nejednadžbu

i dodati njegovoj lijevoj strani određenu vrijednost
tako da se nejednakost pretvara u jednakost.

Nenegativna varijabla
zove dodatna varijabla. Sljedeći teorem pruža osnovu za mogućnost takve transformacije.

Teorem 2.2.1. Svaka odluka
nejednadžba (2.2.1) odgovara jedinstvenom rješenju jednadžbe (2.2.2) i nejednadžbi
, i, obrnuto, svakom rješenju jednadžbe (2.2.2)c
odgovara rješenju
nejednakosti (2.2.1).

Dokaz. Neka
rješenje nejednadžbe (2.2.1). Zatim. Uzmimo broj
. Jasno je da
. Zamjenom u jednadžbu (2.2.2) dobivamo

Prvi dio teorema je dokazan.

Neka je sada vektor zadovoljava jednadžbu (2.2.2) sa
, tj. odbacivanje nenegativne vrijednosti na lijevoj strani posljednje jednakosti
, primamo itd.

Dakle, dokazani teorem zapravo uspostavlja mogućnost dovođenja bilo kojeg LP problema u kanonski oblik. Da biste to učinili, dovoljno je uvesti u svako ograničenje koje ima oblik nejednakosti svoju dodatnu nenegativnu varijablu. Štoviše, u nejednadžbama oblika (1.2.1) ove varijable će se pojaviti sa znakom "+", au nejednadžbama oblika (1.2.2) - sa znakom "–". Upisuju se dodatne varijable ciljna funkcija s nula koeficijenata i stoga ne utječe na njegovu vrijednost.

Komentar. U budućnosti ćemo predstaviti simpleks metodu za kanonski problem LP pri proučavanju funkcije cilja za minimum. U onim problemima u kojima treba pronaći maksimum
, dovoljno je razmotriti funkciju
, pronađi je minimalna vrijednost, a zatim, mijenjajući predznak u suprotno, odredite željenu maksimalnu vrijednost
.

3. Grafička metoda rješavanja problema

linearno programiranje

3.1. Opći pojmovi, primjeri

U slučajevima kada postoje samo dvije varijable u LP problemu, možete koristiti grafička metoda. Neka je potrebno pronaći najveću (minimalnu) vrijednost funkcije
pod ograničenjima

(3.1.1)

Ova se metoda temelji na mogućnosti grafičkog prikazivanja područja mogućih rješenja problema, tj. zadovoljavajući sustav (3.1.1), te pronalaženje optimalnog rješenja među njima. Područje mogućih rješenja problema konstruirano je kao sjecište (zajednički dio) područja rješenja svakog od zadanih ograničenja (3.1.1). Svaki od njih definira poluravninu s rubom
,
. Da bismo odredili koja je od dvije poluravnine domena rješenja, dovoljno je u nejednadžbu zamijeniti koordinate bilo koje točke koja ne leži na pravcu: ako je ona zadovoljena, tada je domena rješenja poluravnina koja sadrži ovu točku, ako nejednakost nije zadovoljena, tada je domena rješenja poluravnina koja ne sadrži zadanu točku.

Sjecište tih poluravnina tvori određeno područje koje se naziva poligon rješenja, a koji je konveksni skup. (Pretpostavimo da je sustav ograničenja konzistentan, a poligon njegovih rješenja ograničen.) Za pronalaženje optimalnog među mogućim rješenjima koriste se linije razine i referentne prave.

Ravna linija naziva se pravac na kojem je ciljna funkcija uzima konstantnu vrijednost. Jednadžba linije razine ima oblik

, Gdje
. Sve linije razine su paralelne jedna s drugom. Njihovo normalno
.

Referentna linija naziva se linija razine koja ima barem jednu zajedničku točku s područjem mogućih rješenja, u odnosu na koje se to područje nalazi u jednoj od poluravnina (slika 1).

Vrijednosti
povećanje u smjeru vektora
.
Stoga je potrebno pomaknuti liniju razine u smjeru ovog vektora paralelno sa samim sobom do referentne linije 1 L u smjeru ovog vektora paralelno sa samim sobom do referentne linije 2).

u maksimalnom zadatku i u suprotnom smjeru - u minimalnom zadatku (do referentne linije
pod ograničenjima

Navedimo rješenje primjera 1.1. Podsjetimo se da trebamo pronaći maksimum funkcije

Otopina. Gradimo regiju izvedivih rješenja. Brojimo ograničenja problema. U pravokutnom Kartezijevom koordinatnom sustavu (slika 2) konstruiramo ravnu liniju

Da biste to učinili, dovoljno je zamijeniti koordinate bilo koje točke koja ne leži na liniji u nejednadžbu. Budući da je ravno ne prolazi kroz ishodište, nadomjestak
do prvog ograničenja. Dobivamo strogu nejednakost
. Stoga, točka
leži u poluravnini rješenja. Slično, konstruiramo ravnu liniju

i domena rješenja ograničenja (2). Nalazimo zajednički dio poluravnina rješenja, uzimajući u obzir ograničenja (3). Rezultirajuće područje izvedivih rješenja ističemo tamnom bojom na slici 2.

Izgradnja linije razine
i vektor
, što označava smjer porasta funkcije a okomito na pravac

.
Ravna linija
kretati se paralelno sa sobom u smjeru
na referentnu liniju. Nalazimo da funkcija cilja doseže svoj maksimum u točki točka sjecišta linija I
. Rješavanje sustava jednadžbi ovih pravaca
, dobivamo koordinate točke
,
. Stoga, a

optimalno rješenje.
Primjer 3.1. Pronađite minimum funkcije

pod sustavom ograničenja
Otopina. Konstruiramo područje izvedivih rješenja (vidi sliku 3), vektor
i jedna od linija razine
. Pomaknite liniju razine u suprotnom smjeru

, budući da se rješava problem nalaženja minimuma funkcije. Referentna linija u ovom slučaju prolazi kroz točku A (slika 3), čije koordinate ćemo pronaći iz rješenja sustava
Tako,

. Izračunajmo.
Komentar. Zapravo, to ovisi o vrsti regije izvedivih rješenja i funkciji cilja

LP problem može imati jedno rješenje, beskonačan broj rješenja ili uopće ne imati rješenja.
pod ograničenjima

Primjer 3.2. Pronađite minimum funkcije
Otopina. Konstruiramo područje izvedivih rješenja (vidi sliku 3), vektor Otopina. Konstruiramo područje izvodljivih rješenja, normalu linija razine , koji ima dodirnih točaka s ovim područjem. Pomicanje linije razine u smjeru suprotnom od normalnog smjera
, budući da se rješava problem nalaženja minimuma funkcije. Normala ravnih linija a normala rubne crte
, u smjeru kojih se kreću linije razine, paralelne su, jer su im koordinate proporcionalne . Stoga se referentna linija poklapa s graničnom linijom točka sjecišta linija područje izvedivih rješenja i prolazi kroz dvije kutne točke ovog područja

(slika 4).
Problem ima beskonačan broj optimalnih rješenja, koja su točke segmenta
,
.

;
;

,
;
,
;

;
.

Ove točke

nalazimo rješavanjem odgovarajućih sustava jednadžbi:
Izračunajmo.
,
.

Odgovor:

na
Primjer 3.3. Riješite problem linearnog programiranja kretati se u smjeru normale. Zbog činjenice da u ovom smjeru raspon mogućih rješenja nije ograničen, linija razine ide u beskonačnost (slika 5).

Problem nema rješenja zbog neograničenosti funkcije cilja.

nalazimo rješavanjem odgovarajućih sustava jednadžbi:
.

: Problemi linearnog programiranja (LPP)

1. Linearno programiranje

2. Vrste problema linearnog programiranja

3. Obrasci za evidentiranje PAP-ova

4. Kanonski oblik problema linearnog programiranja

Linearno programiranje

Linearno programiranje je grana matematičkog programiranja koja se koristi u razvoju metoda za pronalaženje ekstrema linearne funkcije nekoliko varijabli s linearnim dodatna ograničenja, nametnuti varijablama.

Prema vrsti problema koje rješavaju, metode LP dijele se na univerzalne i specijalne. Korištenjem univerzalne metode Svaki problem linearnog programiranja (LPP) može se riješiti. Posebni uzimaju u obzir značajke modela problema, njegovu ciljnu funkciju i sustav ograničenja.

Glavna značajka problema linearnog programiranja je da se ekstrem funkcije cilja nalazi na granici područja mogućih rješenja.

Slika 1 - Ekstrem funkcije cilja

Matematički model ZLP-a zapisan je na sljedeći način:

max (ili min) Z=z(X),(1)

ODR se može prikazati sustavom linearne jednadžbe odnosno nejednakosti.

Vektor X = (x 1, x 2, .... x p) je vektor upravljanja ili učinak upravljanja.

Dopušteni plan X, u kojem kriterij optimalnosti Z=z(X) dostiže ekstremnu vrijednost, naziva se optimalnim i označava se sa X*, a ekstremna vrijednost funkcije cilja sa Z*=z(X*).

Vrste problema linearnog programiranja

Metode linearnog programiranja široko se koriste u industrijskim poduzećima pri optimizaciji proizvodnog programa, njegovoj raspodjeli po radionicama i vremenskim intervalima, pri utovaru asortimana opreme, planiranju tokova tereta, određivanju plana prometa itd.

Najčešći tip zadataka je zadatak optimalno korištenje sredstva. Neka neka proizvodna jedinica (radionica, poduzeće, udruženje itd.), na temelju tržišnih uvjeta, tehničke mogućnosti i dostupnih resursa, može proizvesti n razne vrste proizvodi poznati pod brojevima j.

Pri proizvodnji proizvoda poduzeće je ograničeno raspoloživim resursima čiju ćemo količinu označiti s m, a vektor resursa B = (b 1, b 2, ..., b t). Poznati su i tehnološki koeficijenti a ij koji pokazuju stopu utroška i-tog resursa za proizvodnju jedinice j-tog proizvoda. Izlazna učinkovitost jedinice j-i proizvodi karakteriziran profitom p j .

Potrebno je utvrditi plan proizvodnje X = (x 1, x 2, ..., x p), maksimizirajući profit poduzeća sa zadanim resursima.

Funkcija cilja izgleda ovako

pod ograničenjima

Često asortiman proizvoda utvrđuje viša organizacija, tj. njegove količine moraju biti unutar određenih granica D u j i D u j: tada se postavlja sljedeće ograničenje:

U osnovi je model problema optimalnog korištenja resursa modeli za optimizaciju godišnjeg proizvodnog programa poduzeća. Model uključuje ograničenja vremena rada opreme.

Zadržavajući isti zapis, pišemo kroz b j i c j, redom, prodajnu cijenu i trošak po jedinici jth proizvoda. Kao kriteriji optimalnosti mogu se uzeti sljedeći:

1) maksimalni profit

2) minimalni troškovi proizvodnje

3) maksimalni učinak u vrijednosnom smislu (prihod od prodaje proizvoda)

Primjer. Poduzeće može proizvesti četiri vrste proizvoda 1, 2, 3 i 4. Zajamčena je prodaja bilo kojeg volumena. Tijekom kvartala, poduzeće ima radnu snagu od 100 radnih smjena, poluproizvode težine 260 kg i alatne strojeve od 370 radnih smjena. Stope potrošnje resursa i dobit po jedinici svake vrste proizvoda prikazani su u tablici 1.

Potrebno:

a) šminkati se matematički model zadatak utvrđivanja plana proizvodnje kojim će se ostvariti maksimalna dobit;

b) riješite zadatak sa zahtjevom pakiranja tako da broj jedinica trećeg proizvoda bude 3 puta više količine prvo jedinice;

c) pronaći optimalan asortiman za dodatni uvjeti: proizvodite prvi proizvod najmanje 25 jedinica, treći - ne više od 30, a drugi i četvrti - u omjeru 1:3.

Tablica 1

Početni podaci

Matematički model problema:

funkcija cilja:

max: Z=40x 1 +50x 2 +100x 3 +80x 4

s ograničenjima:

a) za radna sredstva:

2,5x 1 +2,5x 2 +2x 3 +1,5x 4 ? 100;

za poluproizvode:

4x 1 +10x 2 +4x 3 +6x 4 ? 260;

za alatne strojeve:

8x 1 +7x 2 +4x 3 +10x 4 ? 370;

uvjet nenegativnosti:

b) dodatni zahtjev za konfiguraciju bit će izražen uvjetom

3x 1 =x 3, tj. 3x 1 x 3 =0;

c) predstavimo rubne uvjete i konfiguracijski uvjet na sljedeći način: x 1 25,

x 3?30, 3*x 2 = x 4.

Problem narudžbe ili utovara izmjenjivih grupa opreme. Radi se o o raspodjela narudžbi između m (i=1,..., m) poduzeća (radnje, strojevi, izvođači) različitih proizvodno-tehnoloških karakteristika, ali međusobno zamjenjivih u smislu ispunjavanja narudžbi. Potrebno je izraditi plan izdavanja narudžbi u kojem bi zadatak bio izvršen, a pokazatelj učinkovitosti dosegao ekstremnu vrijednost.

Formulirajmo problem matematički. Neka se n vrsta proizvoda treba proizvesti korištenjem m homogenih grupa opreme. Plan proizvodnje za svaku vrstu proizvoda određeno razdoblje dana skupom x j (j=1,2, …n). Snaga svake vrste opreme je ograničena i jednaka b i. Poznata je tehnološka matrica A=|a ij ||, gdje je a ij broj proizvedenih jedinica j-tog proizvoda u jedinici vremena i-ta oprema. Matrica C je matrica troškova, gdje su c ij troškovi povezani s outputom j-te jedinice proizvoda na i-toj opremi. X je vektor izlaznog volumena.

Model problema će imati sljedeći oblik:

ciljna funkcija - minimiziranje troškova provedbe svih naloga

s ograničenjima:

a) prema snazi ​​opreme

b) za proizvodnju

c) uvjet nenegativnosti

Taj se problem naziva distributivni ili distribucijski problem.

Ako je za neke vrste proizvoda dopušteno prekoračenje plana, tada će ograničenje (b) imati oblik

Sljedeće se također može uzeti kao ciljna dobit:

a) maksimalan profit

b) minimalni trošak strojnog vremena

Jer Svaki model sadrži pojednostavljujuće premise; za ispravnu primjenu dobivenih rezultata potrebno je jasno razumijevanje suštine tih pojednostavljenja, što nam u konačnici omogućuje izvođenje zaključka o njihovoj prihvatljivosti ili nedopustivosti. Najznačajnije pojednostavljenje u razmatranim modelima je pretpostavka izravno proporcionalnog (linearnog) odnosa između obujma potrošnje resursa i obujma proizvodnje, koji se specificira pomoću troškovnih normi a ij . Očito, ova pretpostavka nije uvijek ispunjena. Dakle, obujmi potrošnje mnogih resursa (na primjer dugotrajne imovine) naglo se mijenjaju - ovisno o promjenama u proizvodnom programu X. Druge premise za pojednostavljenje uključuju pretpostavke o neovisnosti cijena j od obujma x j, što vrijedi samo za određene granice njihove promjene. Također je važno poznavati ta "ranjiva" područja jer ona ukazuju na temeljne smjerove za poboljšanje modela.

Obrasci za PAP evidenciju

Postoje 3 oblika bilježenja PAP-a:

1) u obliku funkcija

max(ili min)Z=,max(ili min)Z=,

2) vektorski oblik

(skalarni produkt vektora)

pod ograničenjima

A 1 x 1 +A 2 x 2 +..+A n x n = B

Gdje su vektori

C = (C 1, C 2 .. C n), X = (X 1, X 2 .. X n) i.

3) matrični oblik

pod ograničenjima

gdje je C = (c 1, c 2,...c n),

Kanonski oblik problema linearnog programiranja

Ako su sva ograničenja u problemu linearnog programiranja jednadžbe i uvjeti nenegativnosti nametnuti su svim varijablama x j, tada se to naziva problemom linearnog programiranja u kanonskom obliku ili problemom kanonskog linearnog programiranja (CLP).

pod ograničenjima

Da bi se prešlo sa ZLP na CLLP, potrebno je prijeći s ograničenja nejednakosti na ograničenja jednakosti i zamijeniti varijable koje ne poštuju uvjete nenegativnosti.

Pravila za dovođenje ZLP u kanonski oblik:

1) ako postoje ograničenja desna strana negativan, tada se ovo ograničenje treba pomnožiti s -1;

2) ako među ograničenjima postoje nejednakosti, onda se uvođenjem dodatnih nenegativnih varijabli one pretvaraju u jednakosti;

3) ako neka varijabla xk nema ograničenja predznaka, tada se u funkciji cilja i u svim ograničenjima zamjenjuje razlikom između dvije nove nenegativne varijable: xk=x * k - xl, gdje je l sumarni indeks, x * k>=, xl >=0.

Pogledajmo primjer. Dovedimo to u kanonski oblik:

U svaku jednadžbu sustava ograničenja uvedimo izravnavajuće varijable x 4, x 5, x 6. Sustav ćemo napisati u obliku jednakosti, au prvoj i trećoj jednadžbi sustava ograničenja uvode se varijable x 4, x 6 u lijeva strana sa znakom “+”, a x 5 sa znakom “-” unosi se u drugu jednadžbu.

Slobodni članovi u kanonskom obliku moraju biti pozitivni, pomnožite posljednje dvije jednadžbe s -1:

U kanonskom obliku pisanja problema linearnog programiranja, sve varijable uključene u sustav ograničenja moraju biti nenegativne. Pretpostavimo da

Zamjena ovaj izraz u sustav ograničenja i funkciju cilja i pisanjem varijabli rastućim indeksnim redoslijedom, dobivamo problem linearnog programiranja prikazan u kanonskom obliku:

optimizacija simplex linearno programiranje

Upisivanje funkcije cilja i sustava ograničenja razne zadatke linearno programiranje nije isto: u nekim problemima potrebno je pronaći minimum funkcije cilja, au drugima - maksimum; u nekim slučajevima tražene varijable ovise o jednom indeksu, au drugim o dva; u nekim problemima ograničenja su navedena u obliku sustava linearne nejednakosti, au ostalima – u obliku sustava linearnih jednadžbi. U praksi je također moguće imati probleme u kojima su neka ograničenja u obliku linearnih nejednadžbi, a neka u obliku linearnih jednadžbi. Također, ne moraju svi problemi zahtijevati nenegativnost varijabli.

Uzimanje u obzir takve raznolikosti problema linearnog programiranja zahtijeva razvoj posebnih metoda za rješavanje pojedinih klasa istih. Usmjerit ćemo pažnju na učenje opća svojstva i metode linearnog programiranja napisane u takozvanom kanonskom obliku.

Ako u problemu linearnog programiranja sustav početnih ograničenja poprimi oblik jednadžbi poput

i trebate pronaći maksimum linearne funkcije cilja

tada se problem linearnog programiranja smatra napisanim u kanonskom obliku.

Svaki problem linearnog programiranja može se lako svesti na kanonski oblik. U općem slučaju, za to je dovoljno moći, prvo, svesti problem minimiziranja funkcije cilja na problem njezinog maksimiziranja, drugo, prijeći s ograničenja nejednakosti na ograničenja jednakosti, i treće, promijeniti one varijable koje su ne podliježe uvjetu nenegativnosti .

U slučaju kada treba pronaći minimum funkcije , možemo nastaviti s pronalaženjem maksimuma funkcije , budući da je sljedeća izjava istinita:
.

Ograničenje nejednakosti izvornog problema, koje ima oblik " ", može se pretvoriti u ograničenje jednadžbe dodavanjem dodatne ne-negativne varijable na njegovu lijevu stranu i ograničenja nejednakosti oblika " ” – oduzimanjem dodatne nenegativne varijable s njegove lijeve strane.

Imajte na umu da je broj uvedenih dodatnih nenegativnih varijabli uvijek jednak broju nejednakosti u izvornom sustavu ograničenja.

Dodatne uvedene varijable imaju vrlo specifično ekonomsko značenje. Dakle, ako ograničenja izvornog problema linearnog programiranja odražavaju troškove i dostupnost proizvodnih resursa, tada numerička vrijednost dodatna varijabla pokazuje količinu odgovarajućeg neiskorištenog resursa.

Napomenimo također da ako neka varijabla ne poštuje uvjet nenegativnosti, tada se mora zamijeniti s dvije nenegativne varijable I , prihvativši
.

Primjer. Napišite sljedeći problem linearne optimizacije u kanonskom obliku: pronađite minimum funkcije
pod ograničenjima

Otopina

U ovom zadatku treba pronaći minimum funkcije cilja, a sustav ograničenja uključuje četiri nejednadžbe. Kako biste to napisali u kanonskom obliku, trebate prijeći s ograničenja nejednakosti na ograničenja jednadžbi, te također transformirati funkciju cilja.

Budući da je broj nejednakosti uključenih u sustav ograničenja problema četiri, ovaj se prijelaz mora izvesti uz uvođenje četiri dodatne nenegativne varijable. Štoviše, u drugoj i četvrtoj nejednakosti postoji znak " ", pa dodajemo dodatne varijable na njihovu lijevu stranu. U prvoj i trećoj nejednakosti stoji znak “ “, što znači da oduzimamo dodatne varijable s njihove lijeve strane.

Također transformiramo funkciju cilja, mijenjajući sve predznake u suprotne, i nalazimo njen maksimum.

dakle, ovaj zadatak linearno programiranje bit će napisano u sljedećem kanonskom obliku:

pronaći maksimum funkcije

pod ograničenjima

Kanonski oblik ZLP- problem linearnog programiranja oblika ax = b gdje je a matrica koeficijenata, b vektor ograničenja.

Svrha usluge. Online kalkulator dizajniran je za prijelaz JPP-a na KZLP. Dovođenje problema u kanonski oblik znači da će sva ograničenja imati oblik jednakosti uvođenjem dodatnih varijabli.
Ako nijednoj varijabli x j nije nametnuto ograničenje, tada se ono zamjenjuje razlikom dodatnih varijabli, x j = x j1 - x j2, x j1 ≥ 0, x j2 ≥ 0.

upute. Odaberite broj varijabli i broj redaka (broj ograničenja). Dobiveno rješenje sprema se u Word datoteku.

Broj varijabli 2 3 4 5 6 7 8 9 10
Broj redaka (broj ograničenja) 2 3 4 5 6 7 8 9 10

Kako svesti problem linearnog programiranja na kanonski oblik

Matematički model ZLP-a naziva se osnovni, ako su ograničenja u njemu prikazana u obliku jednadžbi pod uvjetom da su varijable nenegativne.

Matematički model je tzv kanonski, ako je njegov sustav ograničenja predstavljen u obliku sustava od m linearno neovisnih jednadžbi (rang sustava r=m), sustav se dodjeljuje jedinična osnova, definirane su slobodne varijable i funkcija cilja je izražena u terminima slobodnih varijabli. U ovom slučaju, desne strane jednadžbi su nenegativne (b i ≥ 0).

Varijable uključene u jednu od jednadžbi sustava s koeficijentom jedan i odsutne u drugim jednadžbama nazivaju se osnovne nepoznanice, i svi ostali - besplatno.

Rješenje sustava naziva se osnovni, ako su slobodne varijable u njemu jednake 0, a ima oblik:
X baze = (0, 0; b 1 , …, b m), f(X baze) = c 0

Osnovno rješenje je kutna točka skupa rješenja sustava, tj. definira vrh poligona rješenja modela. Među takvim rješenjima je i ono u kojem objektivna funkcija zauzima optimalna vrijednost.

Osnovno rješenje nazivamo referentnim ako je dopustivo, tj. sve desne strane jednadžbi sustava (ili nejednadžbi) su pozitivne b i ≥ 0.

Kompaktni oblik kanonskog modela je:
AX = b
X ≥ 0
Z = CX (maks.)

Pojam dopuštenog rješenja, područje dopuštenih rješenja, optimalno rješenje problemi linearnog programiranja.
Definicija 1. Vektor X koji zadovoljava sustav ZLP ograničenja, uključujući uvjete nenegativnosti, ako ih ima, naziva se dopustivim rješenjem ZLP-a.
Definicija 2. Skup svih prihvatljivih rješenja čini područje prihvatljivih rješenja (ADA) PLP-a.
Definicija 3. Izvedivo rješenje za koje funkcija cilja doseže maksimum (ili minimum) naziva se optimalnim rješenjem.

Primjer br. 1. Smanjite sljedeći LP problem na kanonski oblik: F(X) = 5x 1 + 3x 2 → max pod ograničenjima:
2x 1 + 3x 2 ≤20
3x 1 + x 2 ≤15
4x 1 ≤16
3x 2 ≤12
Model je napisan u standardni obrazac. Uvedimo ravnotežne nenegativne varijable x 3 , x 4 , x 5 , x 6 , koje dodajemo na lijeve strane ograničenja nejednakosti. Sve dodatne varijable uvodimo u funkciju cilja s koeficijentima jednakima nuli:
U prvoj nejednakosti značenja (≤) uvodimo osnovnu varijablu x 3 . U 2. nejednadžbi značenja (≤) uvodimo osnovnu varijablu x 4 . U trećoj nejednadžbi uvodimo osnovnu varijablu x 5 . U 4. nejednadžbi - osnovna varijabla x 6. Dobivamo kanonski oblik modeli:
2x 1 + 3x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 = 20
3x 1 + 1x 2 + 0x 3 + 1x 4 + 0x 5 + 0x 6 = 15
4x 1 + 0x 2 + 0x 3 + 0x 4 + 1x 5 + 0x 6 = 16
0x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 1x 6 = 12
F(X) = 5x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 0x 6 → maks.

Primjer br. 2. Pronađite dva referentna rješenja sustava
x 1 + 2x 4 - 2x 5 = 4
x 3 + 3x 4 + x 5 = 5
x 2 + 3x 5 = 2