Reducerea problemei generale LP la forma canonică. Forma canonică a unei probleme de programare liniară
Scopul serviciului. Calculatorul online este conceput pentru tranziția unui PPP la un KZLP. Aducerea problemei la forma canonică înseamnă că toate constrângerile vor avea forma de egalități prin introducerea de variabile suplimentare.
Dacă nu se impune o constrângere nici unei variabile x j, atunci ea este înlocuită cu diferența de variabile suplimentare, x j = x j1 - x j2, x j1 ≥ 0, x j2 ≥ 0.
Instrucțiuni. Selectați numărul de variabile și numărul de rânduri (număr de constrângeri). Soluția rezultată este salvată într-un fișier Word.
Cum se reduce o problemă de programare liniară la formă canonicăSe numește modelul matematic al ZLP de bază, dacă constrângerile din acesta sunt prezentate sub formă de ecuații cu condiția ca variabilele să fie nenegative.
Modelul matematic se numește canonic, dacă sistemul său de constrângeri este prezentat sub forma unui sistem de m ecuații liniar independente (rangul sistemului r=m), sistemul este alocat baza de unitate, se definesc variabilele libere iar functia obiectiv este exprimata in termeni de variabile libere. În acest caz, părțile din dreapta ecuațiilor sunt nenegative (b i ≥ 0).
Variabilele incluse într-una dintre ecuațiile sistemului cu un coeficient de unu și absente în alte ecuații se numesc necunoscute de bază, și toate celelalte - gratuit.
Soluția sistemului se numește de bază, dacă variabilele libere din acesta sunt egale cu 0 și are forma:
X baze = (0, 0; b 1 , …, b m), f(X baze) = c 0
Soluție de bază este punctul de colț al mulțimii de soluții ale sistemului, adică definește vârful poligonului soluție al modelului. Printre astfel de soluții se numără și cea în care ia funcția obiectiv valoare optimă.
O soluție de bază se numește soluție de referință dacă este admisibilă, adică. toate părțile din dreapta ale ecuațiilor sistemului (sau inegalităților) sunt pozitive b i ≥ 0.
Forma compactă a modelului canonic este:
AX = b
X ≥ 0
Z = CX(max)
Conceptul de soluție admisibilă, o regiune de soluții admisibile, o soluție optimă a unei probleme de programare liniară.
Definiția 1. Un vector X care satisface sistemul de constrângeri ZLP, inclusiv condițiile de non-negativitate, dacă există, este numit o soluție admisibilă pentru ZLP.
Definiția 2. Setul tuturor soluțiilor admisibile formează regiunea soluțiilor admisibile (ADA) a PLP.
Definiția 3. O soluție fezabilă pentru care funcția obiectiv atinge un maxim (sau un minim) se numește soluție optimă.
Exemplul nr. 1. Reduceți următoarea problemă LP la forma canonică: F(X) = 5x 1 + 3x 2 → max sub restricțiile:
2x 1 + 3x 2 ≤20
3x 1 + x 2 ≤15
4x 1 ≤16
3x 2 ≤12
Modelul este scris în formă standard. Să introducem variabile nenegative de echilibru x 3 , x 4 , x 5 , x 6 , pe care le adăugăm la părțile din stânga constrângerilor de inegalitate. Introducem toate variabilele suplimentare în funcția țintă cu coeficienți egali cu zero:
În prima inegalitate de sens (≤), introducem variabila de bază x 3 . În a 2-a inegalitate de sens (≤) introducem variabila de bază x 4 . În a treia inegalitate introducem variabila de bază x 5 . În a patra inegalitate - variabila de bază x 6. Obținem forma canonică a modelului:
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 → max
Exemplul nr. 2. Găsiți două soluții de referință ale sistemului
x 1 + 2x 4 - 2x 5 = 4
x 3 + 3x 4 + x 5 = 5
x 2 + 3x 5 = 2
probleme de programare liniară
2.1. Definiție și forme de înregistrare
În cazul în care toate constrângerile sunt ecuații și toate variabilele satisfac condiția de non-negativitate, problema de programare liniară se numește canonic. Poate fi prezentat sub formă de notație de coordonate, vector sau matrice.
a) problema canonică LP în formă de coordonate are forma:
,
.
Această problemă poate fi scrisă folosind semnul de însumare:
,
,
,
,
.
b) problema canonică LP în formă vectorială are forma: ,
,
Unde 
;
;
,
;
;
.
c) problema canonică LP sub formă de matrice are forma:
,
,
Unde 
,
,
.
2.2. Reducerea problemei liniare generale
programare la forma canonică
La compilarea modelelor matematice ale problemelor economice, constrângerile se formează în principal în sisteme de inegalități. Prin urmare, este necesar să se poată trece de la ele la sisteme de ecuații. De exemplu, luați în considerare inegalitatea liniară
și adăugați în partea stângă o anumită valoare 
astfel încât inegalitatea se transformă în egalitate.
Variabilă nenegativă 
numită variabilă suplimentară. Următoarea teoremă oferă baza pentru posibilitatea unei astfel de transformări.
Teorema 2.2.1. Fiecare decizie 
inegalitatea (2.2.1) corespunde unei soluții unice a ecuației (2.2.2) și inegalității 
, și, invers, fiecărei soluții a ecuației (2.2.2)c 
corespunde soluției 
inegalități (2.2.1).
Dovada. Lăsa 
soluția inegalității (2.2.1). Apoi. Să luăm un număr 
. Este clar că 
. Înlocuind în ecuația (2.2.2), obținem
Prima parte a teoremei a fost demonstrată.
Să fie acum un vector 
satisface ecuația (2.2.2) cu 
, adică eliminând valoarea nenegativă din partea stângă a ultimei egalități 
, primim etc.
Astfel, teorema dovedită stabilește de fapt posibilitatea aducerii oricărei probleme LP la forma canonică. Pentru a face acest lucru, este suficient să introduceți în fiecare constrângere care are forma unei inegalități propria variabilă suplimentară nenegativă. Mai mult, în inegalitățile de forma (1.2.1) aceste variabile vor apărea cu semnul „+”, iar în inegalitățile de forma (1.2.2) – cu semnul „–”. Variabilele suplimentare sunt introduse în funcția obiectiv cu coeficienți zero și, prin urmare, nu afectează valoarea acesteia.
Cometariu. În viitor, vom prezenta metoda simplex pentru problema canonică LP atunci când studiem funcția obiectiv pentru un minim. În acele probleme în care trebuie să găsești maximul 
, este suficient să luăm în considerare funcția 
, găsiți valoarea minimă a acesteia și apoi, schimbând semnul în opus, determinați valoarea maximă dorită 
.
3. Metoda grafică de rezolvare a problemelor
programare liniară
3.1. Concepte generale, exemple
În cazurile în care există doar două variabile în problema LP, metoda grafică poate fi folosită pentru a rezolva. Să fie necesar să se găsească valoarea maximă (minimă) a funcției 
sub restricții
(3.1.1)
Această metodă se bazează pe posibilitatea de a descrie grafic regiunea soluțiilor fezabile la o problemă, de ex. satisfacerea sistemului (3.1.1) și găsirea soluției optime între ele. Regiunea soluțiilor fezabile ale problemei este construită ca intersecția (partea comună) a regiunilor de soluție ale fiecăreia dintre constrângerile date (3.1.1). Fiecare dintre ele definește un semiplan cu graniță 
,
. Pentru a determina care dintre cele două semiplane este aria soluției, este suficient să înlocuiți coordonatele oricărui punct care nu se află pe linie în inegalitate: dacă este satisfăcută, atunci aria soluției este semiplanul care conține acest punct, dar dacă inegalitatea nu este satisfăcută, atunci domeniul soluției este un semiplan care nu conține punctul dat.
Intersecția acestor semiplane formează o anumită zonă numită poligon soluție, care este o mulțime convexă. (Să presupunem că sistemul de constrângeri este consistent, iar poligonul soluțiilor sale este limitat.) Pentru a găsi cea optimă dintre soluțiile fezabile, se folosesc linii de nivel și drepte de referință.
Linie de nivel se numeste linie dreapta pe care functia obiectiv 
ia o valoare constantă. Ecuația liniei de nivel are forma
, Unde 
. Toate liniile de nivel sunt paralele între ele. Normalul lor 
.
Nota de subsol se numeşte linie de nivel care are cel puţin un punct comun cu regiunea soluţiilor fezabile, în raport cu care această regiune se află într-unul din semiplanuri (Fig. 1).
Valori 
crestere in directia vectorului 
. Prin urmare, este necesar să mutați linia de nivel 
în direcţia acestui vector paralel cu el însuşi cu linia de referinţă L 1
în sarcina maximă și în direcția opusă - în sarcina minimă (până la linia de referință L 2).
Să dăm soluția exemplului 1.1. Amintiți-vă că trebuie să găsim maximul funcției 
sub restricții
Soluţie. Construim o regiune de soluții fezabile. Numărăm constrângerile problemei. Într-un sistem de coordonate carteziene dreptunghiulare (Fig. 2), construim o linie dreaptă 
, corespunzător constrângerii (1). Găsim care dintre semiplanurile în care această dreaptă împarte întregul plan de coordonate este domeniul soluțiilor inegalității (1).
Pentru a face acest lucru, este suficient să înlocuiți coordonatele oricărui punct care nu se află pe linie în inegalitate. Din moment ce este drept 
nu trece prin origine, substituie 
la prima limitare. Obținem o inegalitate strictă 
. Prin urmare, punctul 
se află în semiplanul soluțiilor. În mod similar, construim o linie dreaptă 
iar domeniul de soluție al constrângerii (2). Găsim partea comună a semiplanurilor soluțiilor, ținând cont de restricțiile (3). Subliniem regiunea rezultată a soluțiilor fezabile în culoare închisă în Fig. 2.
Construirea unei linii de nivel 
și vector 
, care indică direcția de creștere a funcției 
și perpendicular pe linie
. Linie de nivel 
se deplasează paralel cu sine în direcția 
la linia de referință. Constatăm că funcția obiectiv atinge maximul în acest punct 
punctul de intersecție al liniilor 
Și 
. Rezolvarea unui sistem de ecuații ale acestor drepte 
, obținem coordonatele punctului 
. Prin urmare, și 
,
soluție optimă.
Exemplul 3.1. Găsiți minimul unei funcții 
cu un sistem de restricţii 
Soluţie. Construim regiunea soluțiilor fezabile (vezi Fig. 3), vector 
și una dintre liniile de nivel 
. Mutați linia de nivel în direcția opusă 
, deoarece se rezolvă problema găsirii minimului unei funcții. În acest caz, linia de referință trece prin punctul A (Fig. 3), ale cărui coordonate vor fi găsite din soluția sistemului 
Asa de, 
. Să calculăm.
Cometariu. De fapt, depinde de tipul de domeniu al soluțiilor fezabile și de funcția obiectiv 
O problemă LP poate avea o singură soluție, un număr infinit de soluții sau nicio soluție.
Exemplul 3.2. Găsiți minimul unei funcții 
sub restricții 
Soluţie. Construirea regiunii soluțiilor fezabile, normala liniilor de nivel 
și una dintre liniile de nivel 
, care are puncte comune cu această zonă. Mutarea liniei de nivel 
în direcția opusă direcției normale 
, deoarece se rezolvă problema găsirii minimului unei funcții. Normal de linii de nivel 
si normala liniei de limita 
, în direcția căreia se deplasează liniile de nivel, sunt paralele, deoarece coordonatele lor sunt proporționale 
. Prin urmare, linia de referință coincide cu linia de limită 
regiune a soluțiilor fezabile și trece prin două puncte de colț ale acestei regiuni 
Și 
(Fig. 4).
Problema are un număr infinit de soluții optime, care sunt puncte ale segmentului 
. Aceste puncte 
,
găsim prin rezolvarea sistemelor de ecuații corespunzătoare:
;
;
,
;
,
;
;
.
Să calculăm.
Răspuns: 
la 
,
.
Exemplul 3.3. Rezolvați o problemă de programare liniară
Soluţie. Construim regiunea soluțiilor fezabile, normalul 
și una dintre liniile de nivel. În această problemă este necesar să se găsească maximul funcției obiectiv, deci linia de nivel 
deplasați-vă în direcția normalului. Datorită faptului că în această direcție gama de soluții fezabile nu este limitată, linia de nivel merge la infinit (Fig. 5).
Problema nu are soluție din cauza nelimității funcției obiectiv.
Răspuns: 
.
Pagina 1
Forma canonică a problemei se caracterizează prin următoarele trei trăsături: 1) un sistem omogen de constrângeri sub forma unui sistem de ecuaţii; 2) condiții omogene de non-negativitate care se aplică tuturor variabilelor implicate în problemă și 3) maximizarea unei funcții liniare. În această problemă, toate aceste trei caracteristici sunt încălcate.
Forma canonică a problemei se caracterizează prin următoarele trei trăsături: 1) un sistem omogen de constrângeri sub forma unui sistem de ecuaţii; 2) condiții omogene de non-negativitate care se aplică tuturor variabilelor implicate în problemă și 3) maximizarea unei funcții liniare. În această problemă, toate aceste trei caracteristici sunt încălcate.
Forma canonică a problemei de programare liniară este convenabilă deoarece este ușor de găsit vârful inițial al regiunii fezabile.
Să luăm în considerare forma canonică a problemei de programare liniară și metoda de eliminare Jordan-Gauss.
Forma canonică a unei probleme de programare liniară este adesea convenabilă.
La transformarea unui sistem de constrângeri în forma canonică a unei probleme de programare liniară, inegalitățile (12) și (13) trebuie înlocuite cu egalități. Pentru a face acest lucru, sunt introduse variabile suplimentare nenegative.
Demonstrați că matricele reale de comutație în perechi sunt simultan reduse la forma canonică a Problemei 1128 printr-o transformare de similaritate folosind o matrice ortogonală.
În esență (4) - (5) poate fi considerată ca forma canonică a problemei de programare neliniară, întrucât metodele prezentate în Cap. De obicei, în problemele de programare neliniară nu există nicio cerință ca variabilele să fie întregi.
| Tipuri de restricții și metode de transformare a acestora. |
Forma canonică a problemei se caracterizează prin omogenitatea sistemului de constrângeri sub forma unui sistem de ecuații; maximizarea funcției obiectiv; condiţia de non-negativitate a tuturor variabilelor implicate în problemă.
Forma canonică a problemelor nu adaugă nicio caracteristică suplimentară schemei de calcul luate în considerare.
Să considerăm mai întâi a doua formă canonică a problemei minime.
Algoritmul simplex-mete poate fi împărțit în două etape. În prima etapă se găsește o soluție de bază prin eliminarea variabilelor. Dacă se găsește, atunci avem forma canonică a problemei pentru a trece la a doua etapă. Al doilea pas este de a verifica dacă există un optim mărginit. Dacă există, atunci se determină soluții de bază admisibile și din care se selectează cea optimă.
Dacă problema este rezolvată în formă canonică, atunci se utilizează doar o parte din operațiunile introduse în al doilea paragraf. Astfel, pentru problema minimului canonic se realizează doar cazul paragrafului 3.4.1, fiind necesare doar operațiunile de rearanjare ciclică a stâlpilor, trecerea stâlpului prin zona de frontieră verticală, corectarea încălcărilor structurale și o parte din operația de trunchiere. În mod simetric, la rezolvarea problemei maxime canonice se realizează doar cazul de la paragraful 3.4.2, iar operațiunile de rearanjare ciclică a șirurilor, trecerea unui șir prin zona de frontieră orizontală, corectarea încălcărilor structurale și o altă parte a operației de trunchiere. Necesar. În caz contrar, forma canonică a problemei nu adaugă nicio specificitate suplimentară.
Primul paragraf al introducerii a arătat cum o problemă generală de programare liniară poate fi redusă la una dintre formele canonice. Pentru problemele canonice, descrierea metodei de îmbunătățire secvențială este simplificată în mod formal, deoarece nu este nevoie să se ia în considerare două opțiuni pentru încălcarea condițiilor de optimitate și două opțiuni pentru a ajunge la următorul vârf. Cu toate acestea, aceasta crește dimensiunea matricei de bază A [. /, J ], care determină în principal complexitatea Cu toate acestea, în multe cazuri, aplicarea metodei la formele canonice ale problemei se dovedește a fi de preferat, iar în această secțiune ne vom opri asupra variantelor metodei obținute pentru anumite liniare. probleme de programare.
Pagini: 1
Înregistrarea funcției obiectiv și a sistemului de constrângeri în diverse probleme de programare liniară nu este aceeași: în unele probleme se solicită găsirea minimului funcției obiectiv, iar în altele - maximul; în unele cazuri variabilele căutate depind de un indice, iar în altele de doi; în unele probleme constrângerile sunt specificate sub forma unui sistem de inegalități liniare, iar în altele - sub forma unui sistem de ecuații liniare. În practică, este posibil să existe și probleme în care unele dintre constrângeri sunt sub formă de inegalități liniare, iar unele sunt sub formă de ecuații liniare. De asemenea, nu toate problemele pot necesita non-negativitatea variabilelor.
Luarea în considerare a unei astfel de varietăți de probleme de programare liniară necesită dezvoltarea unor metode speciale pentru rezolvarea claselor individuale ale acestora. Ne vom concentra atenția asupra studierii proprietăților și metodelor generale ale programării liniare, scrise în așa-numita formă canonică.
Dacă într-o problemă de programare liniară sistemul de constrângeri inițiale ia forma unor ecuații ca
și trebuie să găsiți maximul funcției obiectiv liniar
atunci se consideră că problema de programare liniară este scrisă în formă canonică.
Orice problemă de programare liniară poate fi ușor redusă la formă canonică. În cazul general, pentru aceasta este suficient să putem, în primul rând, să reducem problema minimizării funcției obiectiv la problema maximizării acesteia, în al doilea rând, să trecem de la constrângerile de inegalitate la constrângerile de egalitate și, în al treilea rând, să schimbăm acele variabile care sunt nesupus condiției de non-negativitate .
În cazul în care trebuie să găsiți minimul unei funcții
, putem trece la găsirea maximului funcției
, deoarece următoarea afirmație este adevărată: 
.
Constrângerea de inegalitate a problemei inițiale, care are forma „ 
", poate fi transformat într-o constrângere de ecuație prin adăugarea unei variabile suplimentare nenegative în partea stângă și a unei constrângeri de inegalitate de forma " 
” – prin scăderea unei variabile suplimentare nenegative din partea stângă.
Rețineți că numărul de variabile suplimentare nenegative introduse este întotdeauna egal cu numărul de inegalități din sistemul original de constrângeri.
Variabilele suplimentare introduse au o semnificație economică foarte specifică. Astfel, dacă constrângerile problemei de programare liniară inițială reflectă costurile și disponibilitatea resurselor de producție, atunci valoarea numerică a variabilei suplimentare arată cantitatea de resursă neutilizată corespunzătoare.
Rețineți, de asemenea, că dacă unele variabile 
nu respectă condiția de non-negativitate, atunci trebuie înlocuită cu două variabile nenegative 
Și 
, după ce a acceptat 
.
Exemplu. Scrieți următoarea problemă de optimizare liniară în formă canonică: găsiți minimul funcției
sub restricții
Soluţie
În această problemă, trebuie să găsiți minimul funcției obiectiv, iar sistemul de constrângeri include patru inegalități. Pentru a o scrie în formă canonică, trebuie să treceți de la constrângeri de inegalitate la constrângeri de ecuație și, de asemenea, să transformați funcția obiectiv.
Deoarece numărul de inegalități incluse în sistemul de constrângeri al problemei este egal cu patru, această tranziție trebuie efectuată cu introducerea a patru variabile suplimentare nenegative. Mai mult, în a doua și a patra inegalități există un semn „ 
„, așa că adăugăm variabile suplimentare în partea stângă. În prima și a treia inegalități există un semn „ 
„, ceea ce înseamnă că scădem variabile suplimentare din partea stângă.
De asemenea, transformăm funcția obiectiv, schimbând toate semnele la opus și găsim maximul acesteia.
Astfel, această problemă de programare liniară va fi scrisă în următoarea formă canonică:
găsiți maximul unei funcții 
sub restricții 
formă canonică, dacă doriți să maximizați funcția obiectiv, toate constrângerile sistemului sunt ecuații și condiția de non-negativitate este impusă tuturor variabilelor.
Problema de programare liniară este dată în formă simetrică, dacă se cere maximizarea funcției obiectiv, toate restricțiile de sistem sunt inegalități „” (sau minimizați funcția obiectiv, toate restricțiile de sistem sunt inegalități „”) și condiția de non-negativitate este impusă tuturor variabilelor.
Se numește un set de numere soluție acceptabilă (plan), dacă îndeplinește sistemul de restricții al ZLP.
Se numește setul tuturor soluțiilor fezabile domeniul soluțiilor fezabile(ODR).
Se numește o soluție admisibilă pentru care se realizează valoarea maximă (minimă) a funcției plan PAP optim.
Termenii „plan” și „plan optim” provin din aplicații economice.
Toate cele trei forme de înregistrare ZLP sunt echivalente în sensul că există algoritmi pentru tranziția de la o formă la alta. Astfel, dacă există o modalitate de a rezolva o problemă într-una dintre forme, atunci este întotdeauna posibil să se determine planul optim pentru o problemă dată în orice altă formă. Problema în formă simetrică se rezolvă prin metoda grafică, iar în formă canonică prin metoda simplex.
Să luăm în considerare algoritmii de tranziție de la o formă la alta.
Simetric canonic. Tranziția se realizează prin adăugarea unei variabile suplimentare nenegative în partea stângă a fiecărei inegalități. Dacă inegalitatea a fost „≤”, atunci variabila de echilibru este adăugată în partea stângă a inegalității cu semnul „+”. Dacă inegalitatea a fost „”, atunci variabila de echilibru este adăugată în partea stângă a inegalității cu semnul „–”. Noile variabile introduse sunt numite bilanț. Problema minimizării funcției Z se înlocuiește cu problema maximizării funcției (–Z) și se folosește că min Z = –max (–Z).
Canonic simetric. Pentru a realiza o astfel de tranziție, se găsește o soluție generală a sistemului de ecuații – constrângeri, funcția țintă este exprimată în termeni de variabile libere. În continuare, profitând de non-negativitatea variabilelor de bază, le putem exclude din problemă. Forma simetrică a problemei va conține inegalități care raportează doar variabilele libere și o funcție obiectivă care depinde doar de variabilele libere. Valorile variabilelor de bază se găsesc din soluția generală a sistemului original de ecuații.
General canonic. Fiecare variabilă căreia nu a fost impusă condiția de non-negativitate este reprezentată ca diferența a două variabile noi nenegative. Inegalitățile sunt convertite în ecuații prin introducerea unei variabile de echilibru în partea stângă a fiecărei inegalități, în același mod cum a fost descris în trecerea de la forma simetrică la forma canonică. Problema minimizării funcției Z este înlocuită cu problema maximizării funcției (–Z) în același mod cum a fost descris în timpul trecerii de la forma simetrică la forma canonică.
Metodă grafică pentru rezolvarea unei probleme de programare liniară
Setul de puncte este numit convex, dacă pentru oricare două puncte ale mulțimii conține un segment care le conectează.
Exemplul 1
Următoarele seturi de puncte din plan sunt convexe:
Următoarele seturi de puncte din plan nu sunt convexe: 
Teorema 1 Intersecția oricărui număr de mulțimi convexe este o mulțime convexă.
Teorema 2 Să fie două puncte arbitrare în spațiu R n. Atunci pentru orice punct al segmentului [ PQ] trebuie executat: .unde .
Hiperplan in spatiu R n este un set de puncte care satisface ecuația. Rețineți că în cazul bidimensional hiperplanul este o linie dreaptă.
Jumătate de spațiu este o mulţime de puncte care satisface una dintre inegalităţile sau . Un hiperplan împarte punctele din spațiu în două semi-spații. În cazul bidimensional, hiperplanul este un semiplan.
Teorema 3 Un semi-spațiu este o mulțime convexă.
Consecinţă Intersecția oricărui număr de semi-spații este o mulțime convexă.
Poliedru se numește intersecția unuia sau mai multor semi-spații. Un poliedru în cazul bidimensional se numește poligon.
Exemplul 2
Următoarele mulțimi sunt poligoane.
Set limitat
Set nelimitat
Un singur punct
Set gol
Un punct al unei multimi convexe se numeste unghiular, dacă nu se află în interiorul niciunui segment care leagă alte două puncte din mulțime.
Exemplul 3
Colțurile unui triunghi sunt vârfurile sale (există trei). Punctele de colț ale unui cerc sunt punctele cercului care îl delimitează (există un număr infinit de ele).
Punctul de colț al unui poliedru se numește sa top.
Să considerăm ZLP-ul dat în formă simetrică.
Teorema 4 Planul optim al ZLP corespunde vârfului poliedrului de decizie determinat de sistemul său de constrângeri.
