Programarea liniară este știința metodelor de investigare și căutarea celor mai mari și mai mici valori ale unei funcții liniare a cărei constrângeri lineare sunt impuse necunoscutului.
Definiția. O supraaglomerare într-un spațiu n-dimensional este locusul de puncte. ale căror coordonate satisfac ecuația liniară (1), unde sunt numere reale arbitrare
Să presupunem că avem o funcție liniară F în raport cu variabilele.
F (x) = este o funcție țintă sau o formă liniară.
Definiția. Suprafața superioară F (x) = c se numește suprafata superioară a valorilor egale ale formei liniare
- datele de suprafata sunt paralele.
Să presupunem că avem un n-punct.
Definiție: Un punct este numit o combinație liniară convexă de puncte. în cazul în care. unde u
Definiție: Se spune că un set de puncte este convex. dacă acesta, împreună cu oricare două puncte, conține combinația lor arbitrară convexă, liniară.
Definiție: Punctele unghiulare sau extreme ale unui set convex sunt puncte care nu sunt o combinație convexă, liniară a două puncte arbitrare ale aceluiași set.
Definiție: Un punct dintr-un set este numit punct de frontieră. dacă o minge cu centru în acest punct conține atât punctele aparținând setului, cât și un punct care nu îi aparține.
Definiție: Punctele de frontieră formează limita unui set dat.
Definiție: Un set închis este un set care conține toate punctele sale limită.
Definiție: Se spune că un set este limitat. dacă există o minge de rază de lungime finită cu centru în orice punct al setului, care conține complet setul dat. În caz contrar, se spune că setul este nelimitat.
Definiție: Un poligon convex este un set convex, închis, delimitat în planul care are un număr finit de puncte de colț.
Definiție: O linie de susținere a unui poligon convex este o linie. Având un poligon pe o parte a acestuia, cel puțin un punct comun.
Teoremă: Un poligon convex limitat închis este o combinație convexă liniară a punctelor de colț.
Teorema: Intersecția oricărui număr de seturi convexe este convexă (cu excepția cazului în care este neimprimată).
Interpretarea geometrică a setului
soluții ale unui sistem de inegalități liniare cu 2 necunoscute
În forma generală, o inegalitate liniară cu 2 variabile este scrisă după cum urmează (1) sau (2).
La fiecare soluție a inegalităților de la (1) și (2) corespunde un punct pe plan. Semnificația geometrică a setului de soluții ale inegalităților din (1) sau (2) este stabilită de teoreme.
Teorema: Setul de soluții ale unei inegalități liniare (1) este unul dintre cele două jumătăți de avioane, care împarte întregul plan, inclusiv această linie dreaptă, iar cealaltă jumătate de avion cu aceeași linie o multitudine de soluții de o inegalitate (2).
Luăm un sistem de două inegalități
Multe dintre soluțiile sale sunt puncte care aparțin ambelor semi-avioane. Prin teorema 2, intersecțiile lor sunt seturi convexe care au un număr finit de puncte de colț. Metoda inducției matematice a stabilit că setul de soluții ale unui sistem de inegalități m-liniar cu două variabile este un poligon convex (dacă această intersecție este goală).