Probleme de programare liniară

În cazul APL ia forma

Luați în considerare un spațiu-coordonat dimensional cu colecții ordonate (puncte).

Definiție 3.1. Setul de puncte de spațiu. ale căror coordonate satisfac ecuația. unde cel puțin unul dintre numerele (), altul decât zero, se numește hiperplana spațiului.







Definiția 3.2. Setul de puncte de spațiu. ale căror coordonate satisfac inegalitatea. se numește jumătate de spațiu. situat pe o parte a

În spațiu, ecuația definește o linie dreaptă, inegalitatea definește o jumătate de plan.

Definiția 3.3. Setul de puncte de spațiu. ale căror coordonate satisfac simultan sistemul hiperplane (), se numește intersecția hiperplane.

Definiție 3.4 O combinație liniară convexă de puncte. . ..., spațiul se numește un punct (.).

O combinație convexă liniară a două puncte de spațiu este un segment care unește aceste puncte.

Definiția 3.5. Un set de puncte dintr-un spațiu se spune că este convex dacă conține, împreună cu oricare două dintre punctele sale, o combinație liniară arbitrară (adică conține, împreună cu oricare două puncte, toate punctele segmentului).

Definiția 3.6. Un punct este numit punct de intersecție al unui set dacă în orice punct de vecinătate arbitrar al unui punct sunt cuprinse ambele puncte din acest set și punctele care nu îi aparțin.

Definiție 3.7. Setul este numit închis. dacă conține toate punctele sale limită, altfel este deschisă.

Definiția 3.8. Un punct se numește punctul unghiular al unui set convex închis dacă nu poate fi reprezentat ca o combinație liniară a oricăror alte două puncte distincte ale acestui set.

Definiție 3.9. Setul este numit 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, setul este numit neîngrădit.

Definiție 3.10. Setul este numit convivial. dacă vreunul dintre punctele sale poate fi îmbinat printr-o linie întreruptă (sau o curbă continuă) care se află în întregime în acest set.

Definiție 3.11. Un set conectat deschis este denumit zonă.

Definiție 3.12. Dacă domeniul conține toate punctele sale limită, atunci se numește o regiune închisă.

Definiția 3.13. Un domeniu închis convex având un număr finit de puncte de colț este numit politop convex-dimensional.

Definiția 3.14. Un set convex închis care are un număr finit de puncte de colț se numește poliedrică convex -dimensională

Definiția 3.15 Intersecția seturilor este setul de puncte care este o parte comună a acestor seturi.

Definiție 3.16. Un set neconstituit de soluții admisibile ale unui ZLP este numit multidron de planuri (soluții).

Definiție 3.17. Punctul unghiular al soluției polytope se numește vârf.

Definiția 3.18. Vârful polyedrului de planuri cu coordonate nonnegative se numește suport. Planul corespunzător acestuia se numește plan de sprijin.

Din definiții rezultă că la fiecare vertex al soluției polytope există un plan de susținere a APL.

Definiție 3.19. Planul de asistență se numește nondegenerat. dacă conține coordonate pozitive și degenerate. dacă coordonatele pozitive sunt mai mici.

Teorema 3.1 (teorema principală a programării liniare). Dacă APL are o soluție optimă, atunci funcția obiectivă are o valoare extremă la unul dintre vârfurile polyedrului planurilor. Dacă funcția obiectiv are o valoare extremă la mai mult de un vertex, atunci ea o ia în orice punct care este combinația lor convexă liniară.

Definiție 3.20. Dacă funcția obiectivă are o valoare extremă la mai mult de un vertex al planului multiedron, atunci se spune că LP are un optim optim.

Definiția 3.21. Setul de puncte care alcătuiesc domeniul soluțiilor admisibile, în cazul a două variabile de control, se numește poligonul soluțiilor (planurilor).

Poligonul soluțiilor poate fi un poligon plan, un set poligonal nelimitat, un segment. Din punct de vedere geometric, LPA este căutarea unui punct al unui poligon al soluțiilor a căror coordonate furnizează cea mai mare sau cea mai mică valoare funcției obiectivului liniar, toate punctele din poligonul soluției fiind soluții admisibile.







Să luăm în considerare metoda grafică de rezolvare a APL.

1) Să presupunem că sistemul de inegalități (3.1) este consecvent (are cel puțin un punct care satisface toate restricțiile dintr-o dată). Pe planul de coordonate, construim un set de soluții admisibile care corespund sistemului de constrângeri (3.1). Fiecare inegalitate a sistemului (3.1) definește o jumătate de plan () cu linia de graniță ().

Să presupunem, de exemplu, că jumătatea planului este determinată de inegalitate. Pentru a construi jumătate de plan (), este suficient să înlocuiți coordonatele oricărui punct (de exemplu, (0, 0)) în inegalitatea corespunzătoare și să verificați adevărul inegalității obținute. Dacă inegalitatea este adevărată, atunci este necesar să se umbrească jumătatea planului care conține punctul dat. Dacă inegalitatea este falsă, atunci umbrați jumătatea planului care nu conține un anumit punct.

Condiții pentru non-negativitatea variabilelor de control. a determina un semi-plan cu linii de graniță. (primul trimestru de coordonare). Deoarece sistemul de constrângeri este consecvent, jumătățile planelor au un domeniu comun. Intersecția semiplanurilor este un set convex și reprezintă o colecție de puncte ale căror coordonate formează soluții admise.

2) Construim gradientul funcției obiective (în acest caz, vectorul geometric):

cu începutul la punctul și sfârșitul punctului. care indică direcția celei mai mari creșteri a funcției obiective.

3) Construim linia de nivel a funcției obiectiv. Această linie este o linie dreaptă (obținem o linie de zero, vezi figura 3.1) și este perpendiculară pe gradient. De regulă, este recomandabil să alegeți valoarea astfel încât linia de nivel corespunzătoare să aibă cel puțin două puncte comune, cu un set de soluții fezabile.

4) La rezolvarea problemei funcției maxime, deplasați linia de nivel în direcția gradientului până când are doar un punct comun cu un set de soluții fezabile. Acest punct, care determină soluția unică a SLA, va fi punctul extremului (maxim). Atunci când rezolvați o problemă pentru o funcție minimă, deplasați linia de nivel în direcția opusă direcției de gradient până când are doar un punct comun cu un set de soluții fezabile. Acest punct, care determină soluția unică a APL, va fi punctul extrem (minim).

5) găsiți coordonatele vârfului poligonului, care este punctul extrem. Pentru a face acest lucru, trebuie să rezolvăm sistemul de ecuații al liniilor a căror intersecție este un vârf dat.

6) Calculați valoarea funcției obiectiv în vertexul rezultat.

Observație 3.1. Dacă, în timp ce se deplasează de-a lungul gradientului, linia de nivel nu lasă un set de soluții admisibile, atunci acest set este nelimitat în direcția de optimizare. În acest caz, se presupune, în mod convențional, fie că.

Observația 3.2. APL nu va avea soluții dacă setul de soluții admisibile este un set gol. Acest lucru înseamnă că sistemul de constrângeri are inegalități incoerente și că nu există un singur punct pe planul de coordonate care să satisfacă toate constrângerile simultan.

Observație 3.3. La ZLP decizie metoda grafică poate satisface cazul când linia de nivel este paralelă cu una dintre laturile unui poligon convex de soluții fezabile, iar această parte este în direcția de optimizare. Apoi, valoarea optimă a funcției obiectiv este atins prin cele două puncte de colț (vârfuri) ale domeniului soluțiilor fezabile și, prin urmare, în toate punctele segmentului care leagă aceste noduri, adică ZLP are un număr infinit de soluții (alternative optime).

Exemplul 3.1. Firma produce două tipuri de înghețată: cremă și ciocolată. Pentru producția de înghețată sunt utilizate două produse inițiale: lapte și umplutură, ale căror costuri pentru 1 kg înghețată și consumabile zilnice sunt prezentate în tabel:

Consumul de materii prime pe 1 kg de înghețată

Studiul pieței a arătat că cererea zilnică de înghețată cremă depășește cererea de ciocolată cu maximum 100 kg. În plus, se constată că cererea de înghețată de ciocolată nu depășește 350 kg pe zi. Prețul de vânzare cu amănuntul de 1 kg de înghețată smântână 16 fre. ciocolata - 14 ruble. Cat de mult inghetata trebuie sa produca fiecare tip

firmă, astfel încât veniturile din vânzarea de produse să fie maximizate? [1; 2].

Soluția. Să desemneze variabilele de control: - volumul zilnic al producției de înghețată cremă, kg; - producția zilnică de înghețată de ciocolată, kg. Să compunem modelul matematic al problemei. Funcția obiectiv va arăta.

Să compunem inegalități pentru constrângerile resurselor. Restricția la lapte are forma: pentru umpluturi :. Vom compila inegalitățile pentru constrângerile de pe piață. Diferența în cererea zilnică pentru 2 tipuri de înghețată este. Limitarea cererii zilnice de înghețată de ciocolată.

Apoi, modelul matematic al problemei va avea forma

Apoi, rezolvăm problema în mod grafic.

1) Construim un set de soluții admisibile. Inegalitatea definește o jumătate de avion situat la stânga și sub linia. care este, drept. Inegalitatea definește o jumătate de avion situat la stânga și sub linia. Constrângerea definește un plan semi-plan situat la stânga și sub linie. Constrângerea definește o jumătate de plan care se află în partea stângă a liniei. restricții. determină primul trimestru de coordonate. Setul de soluții admisibile de LPT nu este gol. Denumim vârfurile poligonului soluțiilor: (Figura 3.2).

2) Construim gradientul funcției obiective:

3) Construim linia de nivel a funcției obiectiv. . Linia nivelului este perpendiculară pe vector.

4) Mutarea unei linii drepte paralele cu ea însăși, găsim punctul limită la care funcția obiectivă părăsește domeniul soluțiilor admisibile (linia punctată în figura 3.2). Punctul limită al unui poligon este un punct.

5) Să găsim coordonatele punctului ca punct de intersecție al liniilor și:

6) Găsiți valoarea funcției obiectiv în momentul respectiv:







Articole similare

Trimiteți-le prietenilor: