Meniul
Acasăexcela

Care este metoda grafică. Metoda grafica de rezolvare a problemelor

Cea mai simplă și mai evidentă metodă de rezolvare a problemei programare liniară(ZLP) este o metodă grafică. Se bazează pe interpretarea geometrică a problemei de programare liniară și este folosit pentru a rezolva ZLP cu două necunoscute:

Vom lua în considerare soluția acestei probleme într-un plan. Fiecare inegalitate a sistemului de constrângeri funcționale definește geometric un semiplan cu o linie de limită a p x, + + a j2 x 2 = b n i = 1, T. Condițiile de non-negativitate definesc semiplanuri cu linii de limită X (= 0, x 2= 0 în consecință. Dacă sistemul este consistent, atunci semiplanurile, care se intersectează, formează o parte comună, care este o mulțime convexă și reprezintă o colecție de puncte; coordonatele fiecăruia dintre aceste puncte sunt o soluție a acestui sistem. Mulțimea acestor puncte se numește poligon soluție. Poate fi un punct, un segment, o rază, un poligon mărginit sau nemărginit.

Geometric, ZLP este găsirea unui punct de colț al poligonului soluție ale cărui coordonate furnizează valoarea maximă (minimă) a funcției obiective liniare, Mai mult, toate punctele poligonului soluție sunt soluții admisibile.

Ecuație liniară descrie un set de puncte situate pe aceeași linie. O inegalitate liniară descrie o regiune din plan.

Să determinăm care parte a planului descrie inegalitatea 2x ( + 3x 2 12.

Mai întâi, să construim o linie dreaptă 2x, + Zx 2 = 12. Trece prin punctele (6; 0) și (0; 4). În al doilea rând, determinăm care semiplan satisface inegalitatea. Pentru a face acest lucru, selectați orice punct din grafic care nu aparține dreptei și înlocuiți coordonatele acestuia în inegalitate. Dacă inegalitatea este valabilă, atunci punct dat este o soluție admisibilă și semiplanul care conține punctul satisface inegalitatea. Este convenabil să folosiți originea coordonatelor pentru a înlocui inegalitatea. Să înlocuim x ( = x 2 = 0 la inegalitatea 2x, + 3x 2 12. Se obține 2 0 + 3 0

În mod similar, puteți descrie grafic toate constrângerile unei probleme de programare liniară.

Soluția fiecărei inegalități a sistemului de constrângeri ZLP este un semiplan care conține linia de limită și este situat pe o parte a acesteia. Intersecția semiplanurilor, fiecare dintre acestea fiind determinată de inegalitatea corespunzătoare a sistemului, se numește zona de soluții fezabile(ODR) sau domeniul definirii.

Trebuie amintit că regiunea soluțiilor fezabile satisface condițiile de non-negativitate (Xj > 0, j = 1, P). Coordonatele oricărui punct aparținând domeniului de definiție sunt o soluție validă a problemei.

Pentru a găsi valoarea extremă a funcției obiectiv atunci când rezolvați grafic ZLP, utilizați vector gradient, ale căror coordonate sunt derivate parțiale ale funcției obiectiv:

Acest vector arată direcția celei mai rapide schimbări în funcția obiectiv. Drept c [ x l + c 2 x 2 = f(x 0), perpendicular pe vectorul gradient este linie de nivel funcția țintă (Fig. 2.2.2). În orice punct al liniei de nivel, funcția obiectiv ia aceeași valoare. Să echivalăm funcția țintă valoare constantă A. Schimbarea sensului A, obținem o familie de drepte paralele, fiecare dintre acestea fiind o linie de nivel a funcției obiectiv.


Orez. 2.2.2.

Proprietate importantă linii de nivel funcție liniară este că atunci când linia este deplasată paralel într-o parte, nivelul este doar crește iar când este deplasat pe cealaltă parte - numai scade.

Metoda grafică de rezolvare a PLP constă în patru etape:

  • 1. Se construiește regiunea soluțiilor admisibile (ADA) a PLP.
  • 2. Vectorul de gradient al funcției obiectiv (TF) este construit cu începutul în punct x 0(0; 0): V = (s, de la 2).
  • 3. Linia de nivel CjXj + c 2 x 2 = a (a - valoare constantă) - o dreaptă perpendiculară pe vectorul gradient V, - se deplasează în direcția vectorului gradient în cazul maximizării funcției obiectiv f(x v x 2) până când iese din ODR. Când minimizați /(*, x 2) linia de nivel se deplasează în direcția opusă vectorului de gradient. Punctul (sau punctele) extreme ale ODR în timpul acestei mișcări este punctul maxim (minim). f(x pjc 2).

Dacă linia dreaptă corespunzătoare liniei de nivel nu părăsește ODR în timpul mișcării sale, atunci minimul (maximul) funcției f(x p x 2) nu există.

Dacă linia nivelului funcției țintă este paralelă cu constrângerea funcțională a sarcinii la care valoare optimă CF, atunci valoarea optimă CF va fi atinsă în orice punct al acestei constrângeri situat între două puncte de colț optime și, în consecință, oricare dintre aceste puncte este soluția optimă a ZLP.

4. Se determină coordonatele punctului maxim (minim). Pentru a face acest lucru, este suficient să rezolvi un sistem de ecuații de drepte care dau un punct maxim (minim) la intersecție. Sens f(x ( , x 2), găsită în punctul rezultat este valoarea maximă (minimă) a funcției obiectiv.

Situații posibile solutie grafica PAP-urile sunt prezentate în tabel. 2.2.1.

Tabelul 2.2.1

Tipul ODR

Tip de soluție optimă

Limitat

Singura decizie

Soluții nesfârșite

Nelimitat

CF nu este limitat de jos

CF nu este limitat de sus

Singura decizie

Soluții nesfârșite

Singura decizie

Soluții nesfârșite

Exemplul 2.2.1. Planificarea producției unei întreprinderi de cusut (problema legată de costume).

Este planificată lansarea a două tipuri de costume - pentru bărbați și pentru femei. Costumul de femeie necesită 1 m de lână, 2 m de lavsan și 1 bărbat-zi de muncă; pentru bărbați - 3,5 m lână, 0,5 m lavsan și 1 om-zi de muncă. În total sunt 350 m lână, 240 m lavsan și 150 om-zile de muncă.

Este necesar să se determine câte costume de fiecare tip trebuie făcute pentru a asigura un profit maxim dacă profitul din vânzarea unui costum de damă este de 10 den. unități, iar de la bărbați - 20 den. unitati Trebuie avut în vedere că este necesar să coaseți cel puțin 60 de costume pentru bărbați.

Modelul economic și matematic al problemei

Variabile: X, - numărul de costume de damă; x 2 - numărul de costume pentru bărbați.

Funcție obiectivă:

Restricții:

Prima constrângere (pe lână) are forma x ( + 3,5x 2 x ( + 3,5x 2 = 350 trece prin punctele (350; 0) si (0; 100). A doua constrangere (dupa lavsan) are forma 2x (+ 0,5x 2 2x x + 0,5x 2 = 240 trece prin punctele (120; 0) și (0; 480). A treia restricție (la muncă) are forma x y + x 2 150. Direct x ( + x 2 = 150 trece prin punctele (150; 0) și (0; 150). A patra constrângere (asupra numărului de costume pentru bărbați) are forma x 2> 60. Soluția acestei inegalități este semiplanul situat deasupra dreptei x 2 = 60.

Ca rezultat al intersecției celor patru semiplane construite, obținem un poligon, care este regiunea soluțiilor fezabile la problema noastră. Orice punct din acest poligon satisface toate cele patru inegalități funcționale, iar pentru orice punct din afara acestui poligon cel puțin o inegalitate va fi încălcată.

În fig. 2.2.3 regiunea soluțiilor fezabile (ADA) este umbrită. Pentru a determina direcția de mișcare spre optim, construim un vector gradient V, ale cărui coordonate sunt derivate parțiale ale funcției obiectiv:

Pentru a construi un astfel de vector, trebuie să conectați punctul (10; 20) la origine. Pentru comoditate, puteți construi un vector proporțional cu vectorul V. Astfel, în Fig. 2.2.3 arată vectorul (30; 60).

Apoi vom construi o linie de nivel 10xj + 20x 2 = A. Să echivalăm funcția țintă cu o valoare constantă A. Schimbarea sensului A, obținem o familie de drepte paralele, fiecare dintre acestea fiind o linie de nivel a funcției obiectiv.

Metoda grafică este destul de simplă și intuitivă pentru rezolvarea problemelor de programare liniară cu două variabile. Se bazeaza pe geometric prezentarea soluțiilor fezabile și a TF-urilor problemei.

Fiecare dintre inegalitățile problemei de programare liniară (1.2) definește un anumit semiplan pe planul de coordonate (Fig. 2.1), iar sistemul de inegalități în ansamblu definește intersecția planurilor corespunzătoare. Mulțimea punctelor de intersecție ale acestor semiplane se numește zona de soluții fezabile(ODR). ODR reprezintă întotdeauna convex figura, adică având următoarea proprietate: dacă două puncte A și B aparțin acestei figuri, atunci îi aparține întregul segment AB. ODR poate fi reprezentat grafic printr-un poligon convex, o zonă poligonală convexă nelimitată, un segment, o rază sau un punct. Dacă sistemul de constrângeri din problema (1.2) este inconsecvent, ODS este o mulțime goală.

Toate cele de mai sus se aplică și în cazul în care sistemul de restricții (1.2) include egalități, deoarece orice egalitate

poate fi reprezentat ca un sistem de două inegalități (vezi Fig. 2.1)

CF la valoare fixa definește o linie dreaptă pe un plan. Schimbând valorile lui L, obținem o familie de drepte paralele numite linii de nivel.

Acest lucru se datorează faptului că modificarea valorii lui L va presupune o modificare numai a lungimii segmentului tăiat de linia de nivel pe axă (ordonată inițială), iar coeficientul unghiular al dreptei va rămâne constant (vezi Fig. 2.1). Prin urmare, pentru a o rezolva, va fi suficient să construiți una dintre liniile de nivel, alegând în mod arbitrar valoarea lui L.

Vectorul cu coordonatele din coeficienții CF la și este perpendicular pe fiecare dintre liniile de nivel (vezi Fig. 2.1). Direcția vectorului coincide cu direcția crescând CF, care este punct important sa rezolve probleme. Direcţie Descendentă CF este opusă direcției vectorului.

Esența metodei grafice este următoarea. În direcția (contra direcției) vectorului din ODR, se caută punctul optim. Punctul optim este punctul prin care trece linia de nivel, corespunzător celei mai mari (mai mici) valori a funcției. Soluția optimă este întotdeauna situată la limita ODD-ului, de exemplu, la ultimul vârf al poligonului ODD prin care va trece linia țintă, sau pe toată latura sa.

Când se caută o soluție optimă pentru problemele de programare liniară, sunt posibile următoarele situații: există o soluție unică a problemei; există un număr infinit de soluții (alternativă); TF nu este limitat; regiunea soluțiilor fezabile este un singur punct; problema nu are solutii.

Figura 2.1 Interpretarea geometrică a constrângerilor și CF a problemei.

Metode de rezolvare a problemelor LP folosind metoda grafică.

I. În constrângerile problemei (1.2), înlocuiți semnele de inegalitate cu semne de egalitate exacte și construiți liniile drepte corespunzătoare.

II. Găsiți și umbriți semiplanurile permise de fiecare dintre constrângerile de inegalitate ale problemei (1.2). Pentru a face acest lucru, trebuie să înlocuiți coordonatele unui punct [de exemplu, (0;0)] într-o inegalitate specifică și să verificați adevărul inegalității rezultate.

Dacă inegalitatea este adevărată,

Acea este necesar să umbriți semiplanul care conține acest punct;

in caz contrar(inegalitatea este falsă) trebuie să umbrim semiplanul care nu conține punctul dat.

Deoarece și trebuie să fie non-negative, atunci lor valori valide va fi întotdeauna deasupra axei și în dreapta axei, adică în primul cadran.

Constrângerile de egalitate permit numai acele puncte care se află pe linia corespunzătoare. Prin urmare, este necesar să evidențiați astfel de linii drepte pe grafic.

III. Definiți ODR ca o parte a planului care aparține simultan tuturor zonelor permise și selectați-o. În absența ODD, problema nu are soluții.

IV. Dacă ODR nu este un set gol, atunci trebuie să construiți linia țintă, de exemplu. oricare dintre liniile de nivel (unde L este un număr arbitrar, de exemplu, un multiplu și, de exemplu, convenabil pentru calcule). Metoda de construcție este similară construcției constrângerilor directe.

V. Construiți un vector care începe în punctul (0;0) și se termină în punct. Dacă linia țintă și vectorul sunt construite corect, atunci o vor face perpendicular.

VI. Când căutați CF maxim, trebuie să mutați linia țintă in directia vector, când se caută CF minim - împotriva direcției vector. Ultimul vârf al ODR în direcția de mișcare va fi punctul de maxim sau minim al CF. Dacă un astfel de punct(e) nu există, atunci putem concluziona că TF nelimitat pe multe planuri de sus (când se caută un maxim) sau de jos (când se caută un minim).

VII. Determinați coordonatele punctului max (min) al filtrului digital și calculați valoarea filtrului digital. Pentru a calcula coordonatele punctului optim, este necesar să se rezolve un sistem de ecuații ale dreptelor la intersecția cărora se află.

Cea mai simplă și mai vizuală metodă de programare liniară (LP) este metoda grafică. Este folosit pentru a rezolva probleme LP cu două variabile. Luați în considerare problema LP în formă standard:

max f(x 1 , x 2 , ..., x n) = ,

, i = 1, 2, …, m,

x j 0, j = 1, 2, …, n.

Sa punem n=2și vom lua în considerare problema în avion. Fie ca sistemul de inegalități să fie consistent (să aibă cel puțin o soluție).

Fiecare inegalitate a acestui sistem definește geometric un semiplan cu linia limită a i 1 x 1 + a i 2 x 2 = b i, i = 1, 2, …, m. Condițiile de non-negativitate definesc semiplanuri cu linii drepte de limită x 1 = 0, respectiv x 2 = 0. Sistemul este consistent, prin urmare semiplanurile, ca și mulțimile convexe, care se intersectează, formează o parte comună, care este o mulțime convexă și este o colecție de puncte, unde coordonatele fiecărui punct sunt o soluție a acestui sistem. Mulțimea acestor puncte se numește poligon soluție. Poate fi un punct, un segment, o rază, un poligon mărginit sau nemărginit.

Astfel, din punct de vedere geometric, ZLP este căutarea unui astfel de punct al poligonului soluție, ale cărui coordonate furnizează valoarea maximă (minimă) funcției liniare a obiectivului, iar toate punctele poligonului soluție sunt soluții admisibile.

O ecuație liniară descrie un set de puncte situate pe aceeași dreaptă. O inegalitate liniară descrie o regiune din plan. Să determinăm care parte a planului este descrisă de inegalitatea 2x 1 + 3x 2 12.

Mai întâi, să construim o linie dreaptă 2x 1 + 3x 2= 12. Trece prin punctele (6; 0) și (0; 4). Pentru a determina ce semiplan satisface inegalitatea, este necesar să selectați orice punct din grafic care nu aparține dreptei și să înlocuiți coordonatele acestuia în inegalitate. Dacă inegalitatea este valabilă, atunci punctul dat este o soluție fezabilă, iar semiplanul care conține punctul satisface inegalitatea. Pentru a înlocui inegalitatea, este convenabil să folosiți punctul de origine. Înlocuiți x 1 = x 2 = 0 în inegalitatea 2x 1 + 3x 2 12. Se obține 2x0 + 3x0 12. Această afirmație este adevărată, prin urmare, inegalitatea 2x 1 + 3x 2 12 corespunde semiplanului inferior care conține punctul (0; 0). Acest lucru este reflectat în graficul prezentat în fig. 1.1.

În mod similar, toate constrângerile problemei LP pot fi reprezentate grafic.

Soluția fiecărei inegalități a sistemului de constrângeri ZLP este un semiplan care conține linia de limită și este situat pe o parte a acesteia. Intersecția semiplanurilor, fiecare dintre acestea fiind determinată de inegalitatea corespunzătoare a sistemului, se numește regiunea soluțiilor admisibile sau regiunea de definiție. Trebuie amintit că regiunea soluțiilor fezabile îndeplinește condițiile de non-negativitate ( x j 0, j = 1, 2, …, n). Coordonatele oricărui punct aparținând domeniului de definiție sunt o soluție validă a problemei.

Pentru a afla valoarea extremă a funcției obiectiv la rezolvarea grafică a problemelor LP, se folosește un vector gradient, ale cărui coordonate sunt derivate parțiale ale funcției obiectiv, i.e.


Acest vector arată direcția celei mai rapide schimbări în funcția obiectiv. Linie directă cu 1 x 1 + cu 2 x 2 = f(x 0), perpendicular pe vectorul gradient, este linia de nivel a funcției obiectiv. În orice punct al liniei de nivel, funcția obiectiv ia aceeași valoare. Să echivalăm funcția țintă cu o valoare constantă "A". Schimbând valoarea lui „a”, obținem o familie de drepte paralele, fiecare dintre acestea fiind o linie de nivel a funcției obiectiv.

O proprietate importantă a liniei de nivel a unei funcții liniare este aceea că, atunci când linia este deplasată paralel într-o direcție, nivelul crește doar, iar atunci când este deplasată în cealaltă direcție, scade.

Din punct de vedere geometric, într-o problemă de programare liniară, căutăm un astfel de punct de colț sau un set de puncte dintr-un set admisibil de soluții la care se ajunge la linia de nivel cel mai înalt (cel mai jos), situată mai departe (mai aproape) decât celelalte în direcția celei mai rapide creșteri.

Metoda grafică de rezolvare a ZLP constă din următorii pași.

1. Se construiește o regiune poligonală de soluții admisibile (ADS) a PLP.

2. Vectorul de gradient al funcției obiectiv (TF) este construit la un punct x 0 aparținând ODR:

3. Linia de nivel c 1 x 1 + c 2 x 2 = a (a este o valoare constantă) - o dreaptă perpendiculară pe vectorul gradient - se deplasează în direcția acestui vector în cazul maximizării f (x 1, x 2) până când iese din ODR. Punctul (sau punctele) limită al zonei în timpul acestei mișcări este punctul maxim f(x 1, x 2).

4. Pentru a găsi coordonatele punctului maxim, este suficient să rezolvi două ecuații drepte obținute din restricțiile corespunzătoare și dând punctul maxim la intersecție. Valoarea f(x 1, x 2) găsită în punctul rezultat este maximă.

La minimizarea (maximizarea) funcției f(x 1, x 2), linia de nivel se deplasează în direcția opusă vectorului gradient. Dacă linia dreaptă corespunzătoare liniei de nivel nu părăsește ODR în timpul mișcării sale, atunci minimul (maximul) funcției f(x 1, x 2) nu există.

Dacă linia de nivel este paralelă cu orice constrângere funcțională a problemei, atunci valoarea optimă a CF va fi atinsă în orice punct al acestei constrângeri situat între două puncte de colț optime și, în consecință, oricare dintre aceste puncte este soluția optimă pentru ZLP. Situațiile posibile pentru rezolvarea grafică a problemelor LP sunt prezentate în Tabel. 1.3.

Tabelul 1.3

№ Tipul ODR Tip de soluție optimă Note
Poligonal închis Singura decizie
Singura decizie
Poligonal CF nu este limitat de jos
CF nu este limitat de sus
Poligonal deschis Singura decizie
Soluții nesfârșite
Segment de linie Singura decizie

Să luăm în considerare soluția grafică a problemelor de programare liniară folosind următorul exemplu.

Exemplul 1.1. Planificarea producției unei întreprinderi de cusut (problema legată de costume).

Este planificată lansarea a două tipuri de costume - pentru bărbați și pentru femei. Un costum de femeie necesita 1 m de lana, 2 m de lavsan si 1 persoana/zi de travaliu. Pentru un costum barbatesc - 3,5 m lana, 0,5 m lavsan si 1 persoana/zi de munca. In total sunt 350 m lana, 240 m lavsan si 150 om/zile de munca. Este necesar să se determine câte costume de fiecare tip trebuie făcute pentru a asigura un profit maxim, dacă profitul din vânzarea unui costum de damă este de 10 unități bănești, iar de la un costum de bărbați - 20 de unități monetare. Trebuie avut în vedere că este necesar să coaseți cel puțin 60 de costume pentru bărbați.

Să introducem următoarea notație: x 1 - numărul de costume de damă; x 2 – numărul de costume pentru bărbați. Profitul din vânzarea costumelor de damă este de 10x 1, iar din vânzarea de costume de bărbați - 20x 2, adică. este necesar să se maximizeze funcția obiectiv:

10x 1 + 20x 2

Constrângerile sarcinii au forma:

x 1 + x 2 150,

2 x 1 + 0,5x 2 240,

x 1 + 3,5x 2 350,

x 2 60,

x 1 0.

Prima limitare a travaliului este x 1 + x 2 150. Linia dreaptă x 1 + x 2 = 150 trece prin punctele (150; 0) și (0; 150) (Fig. 1.2).

A doua constrângere asupra lavsanului este 2 x 1 + 0,5x 2 240. Linia dreaptă 2 x 1 + 0,5x 2 = 240 trece prin punctele (120; 0) și (0; 480). A treia limitare la lână x 1 + 3,5x 2 350. Să adăugăm o a patra limitare la numărul de costume pentru bărbați x 2 60. Soluția acestei inegalități este semiplanul situat deasupra dreptei x 2 = 60. În fig. 1.3 regiunea soluțiilor fezabile este umbrită. Pentru a determina direcția de mișcare spre optim, construim un vector de gradient, ale cărui coordonate sunt derivate parțiale ale funcției obiectiv, i.e.

Pentru a construi un astfel de vector, trebuie să conectați punctul (10;20) la origine. Când maximizați funcția obiectiv, este necesar să vă deplasați în direcția vectorului de gradient, iar când minimizați, în direcție opusă. Pentru comoditate, puteți construi un vector proporțional cu vectorul . Deci, în fig. 1.4 prezintă vectorul gradient (30;60).

Pentru a determina direcția de mișcare spre optim, construim un vector de gradient, ale cărui coordonate sunt derivate parțiale ale funcției obiectiv, i.e.

În cazul nostru, vom muta linia de nivel până iese din regiunea soluțiilor fezabile. În punctul extrem, de colț, se atinge maximul funcției obiectiv. Pentru a găsi coordonatele acestui punct, este suficient să rezolvați două ecuații drepte obținute din restricțiile corespunzătoare și să dați un punct maxim la intersecție:

x 1 + 3,5x 2 = 350,

x 1 + x 2 = 150.

De aici este ușor să scrieți soluția la ZLP original: max f(x)= 2300 și se realizează la x 1 = 70 și x 2 = 80 (vezi Fig. 1.4).

1.3.TEHNOLOGIE PENTRU SOLUȚIONAREA PROBLEMELOR DE PROGRAMARE LINEARĂ UTILIZAREA SUPLIMENTULUI DE CĂUTARE SOLUȚIE ÎN MEDIU EXCEL

1.3.1. Informații generale despre lucrul cu foaia de calcul procesor Excel

Să luăm în considerare câteva aspecte ale lucrului cu procesorul de foi de calcul Excel, care va simplifica calculele necesare pentru rezolvarea problemelor de optimizare. Un procesor de masă este software, conceput pentru a automatiza prelucrarea datelor tabulare.

Elemente de ecran Excel. După lansați Excel Pe ecran apare un tabel, al cărui aspect este prezentat în Fig. 1.5.

Această imagine se numește foaie de lucru. Este o grilă de rânduri și coloane, ale căror intersecții formează dreptunghiuri numite celule. Fișele de lucru sunt concepute pentru introducerea datelor, efectuarea calculelor, organizarea unei baze de informații etc. fereastra Excel afișează principalul elemente software: bară de titlu, bară de meniu, bară de stare, butoane de control al ferestrei.

Lucrul cu formule.În programe foi de calcul formulele sunt folosite pentru a efectua multe calcule diferite. CU folosind Excel puteți crea rapid o formulă. Formula constă din trei părți principale:

1) semn egal;

2) un set de valori sau referințe în celulele cu care se efectuează calculele;

3) operatori.

4) Dacă nu există semn egal, atunci Excel interpretează datele nu ca o formulă, ci ca date introduse într-o celulă. Formulele pot fi introduse direct într-o celulă sau în bara de formule - fie text, fie numere. În acest caz, trebuie să faci următoarele acțiuni:

· selectați celula care trebuie să conțină formula și introduceți semnul (=);

· introduceți un operator sau un semn de acțiune;

· selectați o altă celulă inclusă în formulă;

· apăsați tasta Enter.

Formula introdusă va apărea în bara de formule, iar rezultatul calculului va apărea în celulă.

Utilizarea funcțiilor în formule. Pentru a ușura introducerea formulelor, puteți utiliza funcțiile Excel. Funcțiile sunt formule integrate în Excel. Excel conține multe formule. Ele sunt grupate după tipuri variate: logic, matematic, ingineresc, statistic etc.

Pentru a activa o anumită formulă, faceți clic pe butoanele Inserare, Funcții. Fereastra Function Wizard care apare în stânga conține o listă de tipuri de funcții. După selectarea unui tip, o listă cu funcțiile în sine va fi plasată în partea dreaptă. O funcție este selectată făcând clic pe numele corespunzător.

Funcții diverse a executa tipuri diferite calcule după anumite reguli. Când o funcție este un singur obiect dintr-o celulă de foaie de lucru, începe cu un semn (=), urmat de numele funcției și apoi de argumentele funcției, cuprinse între paranteze.

Find a Solution este un program de completare Excel care vă permite să rezolvați probleme de optimizare. Dacă comanda Căutare soluție nu este disponibilă în meniul Instrumente, atunci trebuie să descărcați acest supliment. Selectați comanda Tools => Add-ons și activați programul de completare Căutare soluție. Dacă acest program de completare nu se află în caseta de dialog Suplimente, atunci trebuie să accesați panoul Gestionare Windows, faceți clic pe pictograma Adăugare/Eliminare programe și utilizați programul Instalare Excel(sau Office) instalați programul de completare Căutare soluție.

După selectarea comenzilor Tools => Search for a solution, va apărea caseta de dialog Search for a solution.

Există trei opțiuni principale în caseta de dialog Găsiți soluție;

Setați celula țintă.

Schimbarea celulelor.

Restricții.

Mai întâi trebuie să completați câmpul Setați celula țintă. În toate sarcinile pentru instrumentul Găsiți o soluție, rezultatul într-una dintre celulele foii de lucru este optimizat. Celula țintă este legată de alte celule din foaia de lucru folosind formule. Instrumentul Găsire soluție utilizează formule care produc un rezultat în celula țintă pentru a verifica solutii posibile. Puteți alege să căutați cel mai mic sau cea mai mare valoare pentru celula țintă sau setați o anumită valoare.

Al doilea parametru important Instrumentul Găsiți soluție este opțiunea Schimbarea celulelor. Aici specificați celulele ale căror valori vor fi modificate pentru a optimiza rezultatul în celula țintă. Puteți specifica până la 200 de celule modificabile pentru a găsi o soluție. Există două cerințe principale pentru aceste celule: nu trebuie să conțină formule, iar modificările valorilor lor trebuie să se reflecte într-o modificare a rezultatului în celula țintă. Cu alte cuvinte, celula țintă depinde de celulele care sunt modificate.

Al treilea parametru care trebuie introdus în fila Căutare soluție este restricțiile.

Pentru a rezolva problema aveți nevoie de:

1) indicați adresele celulelor în care va fi plasat rezultatul deciziei (celule modificabile);

2) introduceți datele inițiale;

3) introducerea unei dependenţe pentru funcţia obiectiv;

4) introduceți dependențe pentru restricții,

5) rulați comanda Căutare soluții;

6) atribuiți o celulă funcției țintă (setați celula țintă);

7) introducerea restricțiilor;

8) introduceți parametrii pentru rezolvarea PLP.

Să luăm în considerare tehnologia soluției folosind condițiile din Exemplul 1.1 (problema costumului).

Modelul economic și matematic al problemei

Fie x 1 numărul de costume pentru femei; x 2 - numărul de costume pentru bărbați,

10 x x 1 + 20 x x 2 max

Constrângerile sarcinii au forma:

x 1 + x 2 150 - limitarea muncii;

2 x x 1 + 0,5 x X 2.240 - limita la lavsan;

x 1 + 3,5 x x 2 350 - limita de lana;

x 2 60 - limită la costume pentru bărbați;

x 1 0 - restricție privind costumele pentru femei.

1. Specificați adresele celulelor în care va fi plasat rezultatul soluției (celule modificabile).

Notați cu x 1 , x 2 numărul de costume din fiecare tip. În problema noastră, valorile optime ale vectorului = (x 1, x 2) vor fi plasate în celulele A2:B2, valoarea optimă a funcției obiectiv - în celula S3.

2. Introduceți datele inițiale.

Introduceți datele inițiale ale sarcinii așa cum se arată în Fig. 1.6.

3. Introduceți o dependență pentru funcția obiectiv.

· Plasați cursorul în celula „NW”, celula va fi selectată.

· Plasați cursorul pe butonul Function Wizard situat pe bara de instrumente.

· Introduceți Enter. Pe ecran apare caseta de dialog Function Wizard pasul 1 din 2.

· În fereastra Funcții, selectați linia SUMPRODUCT (Fig. 1.7). Pe ecran

· apare caseta de dialog SUMPRODUCT (Fig. 1.8).

· Introduceți în linia Array 1 A2:B2.

· Introduceți AZ:VZ în linia Array 2.

Matricea 1 va fi folosită atunci când introduceți dependențe pentru constrângeri, așa că pe această matrice trebuie să faceți legătură absolută. În fig. Figura 1.9 arată că o funcție a fost introdusă în celula SZ.

5. Introduceți dependențe pentru constrângeri (Figura 1.10).

· Plasați cursorul în celula NW.

· Pe bara de instrumente există un buton Copiere în Clipboard.

· Plasați cursorul în celula C4.

· Plasați cursorul în celula C5.

· Pe bara de instrumente, butonul Lipire din Clipboard.

· Plasați cursorul în celula Sat.

· Pe bara de instrumente, butonul Lipire din Clipboard.

· Plasați cursorul în celula C7.

· În bara de instrumente, faceți clic pe butonul Lipire din Clipboard. (Conținutul celulelor C4-C7 trebuie verificat. Ele trebuie să conțină informații, așa cum se arată, de exemplu, în Fig. 1.11; conținutul celulei C5 este prezentat ca exemplu.)

· În linia Meniu, plasați cursorul mouse-ului pe Service. În meniul extins, selectați comanda Căutare soluție. Apare caseta de dialog Căutare soluție (Fig. 1.12).

5. Rulați comanda Căutare soluție.

6. Atribuiți o celulă funcției țintă (setați celula țintă), indicați adresele celulelor care urmează să fie modificate.

· Plasați cursorul în linia de celule țintă Setați.

· Introduceți adresa celulei $С$3.

· Introduceți tipul funcției obiectiv în funcție de condițiile problemei dvs. Pentru a face acest lucru, rețineți cu ce funcția obiectiv este egală - Valoare maximă sau Valoare minimă.

· Plasați cursorul într-un rând prin schimbarea celulelor.

· Introduceți adresele variabilelor necesare A$2:B$2 (Fig. 1.13).

7. Introduceți restricții.

· Plasați cursorul mouse-ului pe butonul Adăugare. Apare caseta de dialog Add Constraint.

· Introduceți un semn de restricție.

· În linia Restriction, introduceți adresa $D$4 (Fig. 1.14).

· Plasați cursorul mouse-ului pe butonul Adăugare. Caseta de dialog Adăugare restricție va reapărea.

· Introduceți constrângerile rămase ale problemei utilizând algoritmul descris mai sus.

· După administrare ultima restrictie Faceți clic pe butonul OK. Pe ecran va apărea caseta de dialog Căutare soluție cu condițiile introduse (Fig. 1.15).

8. Introduceți parametrii pentru rezolvarea problemei de programare liniară.

· În caseta de dialog, plasați cursorul mouse-ului pe butonul Opțiuni. Pe ecran va apărea caseta de dialog Opțiuni de căutare a soluției (Fig. 1.16).

· Setați casete de selectare în Windows Model liniar(aceasta va asigura utilizarea metodei simplex) și Valori nenegative.

· Plasați cursorul mouse-ului pe butonul OK. Pe ecran va apărea caseta de dialog Căutare soluție.

· Plasați cursorul mouse-ului pe butonul Run.

După un timp scurt, vor apărea caseta de dialog Rezultate căutare soluție și tabelul inițial cu celule completate AZ:VZ pentru valorile x i și celula SZ cu valoarea maximă a funcției obiectiv (Fig. 1.17).

Dacă specificați tipul de raport Stabilitate, puteți obține informații suplimentare despre soluția optimă (Fig. 1.18).

Ca urmare a rezolvării problemei, s-a primit răspunsul: este necesar să coaseți 70 de bucăți. costume dama si 80 buc. costume pentru bărbați pentru a obține un profit maxim de 2300 USD.

1.4. DUALITATE ÎN PROBLEME DE PROGRAMARE LINEARĂ. ANALIZA SOLUȚIILOR OPTIME OBȚINITE

În 1975, compatriotul nostru L.V. Kantorovich a primit Premiul Nobel pentru Economie (împreună cu economistul american T. Koopmans) pentru dezvoltarea teoriei utilizare optimă resurse (vezi Anexa 1).

Fiecare problemă de programare liniară este strâns legată de alta problemă liniară, numit dual; problema inițială se numește originală sau directă. Legătura dintre problemele inițiale și cele duale constă, în special, în faptul că rezolvarea uneia dintre ele poate fi obținută direct din rezolvarea celeilalte.

Variabile dubla problema y i sunt numite estimări determinate obiectiv, sau estimări duale, sau „prețuri” resurselor sau prețuri umbră.

Fiecare dintre problemele de pereche dublă este de fapt o problemă de programare liniară independentă și poate fi rezolvată independent de cealaltă.

Problema duală în raport cu cea inițială este compusă după următoarele reguli:

1) funcția obiectivă problema initiala se formulează pentru maxim, iar funcția obiectivă a problemei duale este formulată pentru minim, în timp ce în problema maximă toate inegalitățile din constrângerile funcționale au forma (), în problema minimului - forma ( );

2) matricea A, compusă din coeficienți pentru constrângeri necunoscute în sistemul problemei inițiale, și o matrice similară A T în problema duală se obțin una de la cealaltă prin transpunere;

3) numărul de variabile din problema duală este egal cu numărul de constrângeri funcționale din problema originală, iar numărul de restricții din sistemul problemei duale este egal cu numărul de variabile din cea originală;

4) coeficienții pentru necunoscutele din funcția obiectivă a problemei duale sunt termenii liberi din sistemul de constrângeri ai problemei inițiale, iar părțile din dreapta din restricțiile problemei duale sunt coeficienții pentru necunoscutele din funcția obiectivă a originalului; j 0.

Cele două probleme prezentate formează o pereche de probleme duale simetrice. Principalele afirmații despre probleme reciproc duale sunt cuprinse în următoarele două teoreme.

Prima teoremă a dualității. Pentru probleme reciproc duale, apare unul dintre cazurile care se exclud reciproc.

1. În problemele directe și duale există soluții optime,
în acest caz, valorile obiectivelor funcţionează pe soluţiile optime
Meci

2. În problema directă, mulțimea admisibilă nu este goală, iar funcția obiectiv pe această mulțime nu este mărginită de sus. În acest caz, problema duală va avea un set admisibil gol.

3. Într-o problemă duală, mulțimea admisibilă nu este goală, iar funcția obiectiv de pe această mulțime nu este mărginită de jos. În acest caz, setul admisibil al problemei directe se dovedește a fi gol.

4. Ambele probleme luate în considerare au seturi admisibile goale.

A doua teoremă de dualitate (teoremă complementară de non-rigiditate). Fie = ( x 1, x 2,..., x n) este o soluție admisibilă a problemei directe, a = (y 1,y 2,...,y t) este o soluție admisibilă a problemei duale. Pentru ca acestea să fie soluții optime la problemele directe și, respectiv, duale, este necesar și suficient ca următoarele relații să aibă loc:

(1.4)

(1.5)

Condițiile (1.4) și (1.5) permit, cunoscând soluție optimă una dintre problemele reciproc duale, găsiți soluția optimă pentru o altă problemă.

Să luăm în considerare o altă teoremă, ale cărei concluzii vor fi folosite în continuare.

Teorema de estimare. Valorile variabilelor y i din soluția optimă a problemei duale reprezintă estimări ale influenței termenilor liberi b i ai sistemului de constrângeri (inegalități) problemei directe asupra valorii

Hotărând ZLP folosind metoda simplex, rezolvăm simultan ZLP-ul dual. Variabilele problemei duale y i se numesc estimări determinate obiectiv.

Să luăm în considerare interpretarea economică a problemei duale folosind problema covorului ca exemplu.

Exemplul 1 .2. Folosind enunțul problemei covorului, finalizați următoarele sarcini.

1. Formulați un model economico-matematic al problemei covoarelor pentru costul total maxim de producție, folosind datele din Tabel. 1.1.

2. Folosind Căutare soluție, găsiți un plan de producție la care costul total de producție va fi maxim.

3. Formulați un model economico-matematic al problemei duale la problema covorului.

4. Găsiți planul optim pentru problema duală, folosind teoreme de dualitate, explicați egalitatea la zero a lui X 1 și X 4.

5. Folosind protocoalele de căutare a soluției, efectuați o analiză a soluției optime rezultate la problema inițială.

6. Determinați cum se vor schimba costul total și planul de producție atunci când durata de viață a țevii crește cu 12 unități.

1. Să formulăm un model economic și matematic al problemei.

Să notăm cu X 1, X 2, X 3, X 4 numărul de covoare de fiecare tip. Funcția obiectiv are forma

F(X) = 3X 1 + 4X 2 + 3X 3 + X 4 max,

și limitările resurselor

7Х 1 + 2Х 2 + 2Х 3 + 6X 4 80,

5Х 1 + 8Х 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. Căutați planul de lansare optim.

Să rezolvăm problema folosind un program de completare Căutare Excel solutii. Tehnologia de rezolvare a problemei a fost discutată în detaliu în problema costumului. În problema noastră, valorile optime ale vectorului X = (X 1, X 2, X 3, X 4) vor fi plasate în celulele VZ:EZ, valoarea optimă a funcției obiectiv - în celulă F4.

Să introducem datele inițiale. Mai întâi, descriem funcția țintă folosind funcția - SUMPRODUCT (Fig. 1.19). Și apoi vom introduce date pentru părțile din stânga a restricțiilor. În Căutarea unei soluții, vom introduce direcția funcției obiectiv, adresele variabilelor căutate și vom adăuga restricții. Pe ecran va apărea caseta de dialog Căutare soluție cu condițiile introduse (Fig. 1.20).

După introducerea parametrilor pentru rezolvarea problemei, faceți clic pe butonul Execute. Pe ecran va apărea un mesaj că a fost găsită o soluție (Fig. 1.21).

Soluția rezultată înseamnă că venitul maxim este de 150 de mii de ruble. o fabrică poate primi 30 de covoare de al doilea tip și 10 covoare de al treilea tip la producție. În acest caz, resursele „muncă” și „echipament” vor fi utilizate integral, iar din 480 kg de fire (resursa „materii prime”) se vor folosi 280 kg.

Crearea unui raport bazat pe rezultatele căutării unei soluții. Excel vă permite să prezentați rezultatele căutării unei soluții sub forma unui raport (Tabelul 1.4). Există trei tipuri de astfel de rapoarte:

· Rezultate (Răspuns). Raportul include valorile inițiale și finale ale celulelor țintă și modificate și informații suplimentare despre restricții.

· Stabilitate (Sensibilitate). Un raport care conține informații despre sensibilitatea unei soluții la mici modificări ale celulelor care sunt modificate sau ale formulelor de constrângere.

· Limite. Pe lângă originalul și valorile finale celulele fiind modificate și celulele țintă, raportul include limite superioare și inferioare ale valorilor pe care celulele care influențează le pot accepta dacă constrângerile sunt îndeplinite.

Să luăm în considerare mai întâi cel mai simplu caz, când exact două variabile sunt incluse în ZLP:

Fiecare dintre inegalitățile (a)-(b) ale sistemului de constrângeri ale problemei (3.8) definește geometric un semiplan, respectiv, cu linii drepte limită, X 1 =0 și X 2 =0. Fiecare dintre liniile de limită împarte planul x 1 Ox 2 în două semiplane. Toate soluțiile la inegalitatea inițială se află într-unul dintre semiplanurile formate (toate punctele semiplanului) și, prin urmare, înlocuirea coordonatelor oricăruia dintre punctele sale în inegalitatea corespunzătoare o transformă într-o adevărată identitate. Ținând cont de acest lucru, se determină semiplanul în care se află soluțiile inegalității, i.e. selectând orice punct din orice semiplan și substituind coordonatele acestuia în inegalitatea corespunzătoare. Dacă o inegalitate este valabilă pentru un punct dat, atunci este valabilă pentru orice alt punct din același semiplan. În caz contrar, soluțiile inegalității se află într-un alt semiplan.

Dacă sistemul de inegalități (a)-(b) este consecvent, atunci domeniul soluțiilor sale este mulțimea de puncte aparținând tuturor semiplanurilor indicate. Deoarece mulțimea punctelor de intersecție ale acestor semiplanuri este convexă, domeniul soluțiilor admisibile la problema (3.8) este o mulțime convexă, care se numește poligon soluție (termenul introdus anterior „poliedru soluție” este de obicei folosit dacă n 3 ). Laturile acestui poligon se află pe linii drepte, ale căror ecuații sunt obținute din sistem original restricții prin înlocuirea semnelor de inegalitate cu semne de egalitate exacte.

Astfel, ZLP inițial constă în găsirea unui punct în poligonul de decizie la care funcția obiectiv F ia valoarea maximă (minimă).

Acest punct există atunci când poligonul soluție nu este gol și funcția obiectiv de pe acesta este mărginită de sus. În condițiile specificate, la unul dintre vârfurile poligonului soluție, funcția obiectiv capătă valoarea maximă. Pentru a determina acest vârf, construiți o linie de nivel L: c 1 x 1 +c 2 x 2 =h (unde h este o constantă), perpendicular pe vectorul gradient și care trece prin poligonul soluție și mutați-l paralel de-a lungul vectorului gradient până când trece prin ultimul său punct comun de intersecție cu poligonul soluție (când se construiește un vector gradient, un punct (c 1 ; c 2) este așezat în planul x 1 Ox 2 și un segment direcționat este trasat către acesta din originea coordonatelor). Coordonatele punctului specificat determină planul optim pentru această sarcină.

Rezumând toate cele de mai sus, prezentăm un algoritm pentru metoda grafică de rezolvare a ZLP.

Algoritm pentru metoda grafică de rezolvare a ZLP

1. Construiți un poligon de soluții specificate de sistemul de restricții al ZLP inițial.


2. Dacă poligonul de soluții construit este o mulțime goală, atunci ZLP original nu are soluții. În caz contrar, construiți un vector gradient și efectuați orice linie nivelul L, deplasându-l pe care la rezolvarea problemei la maximum în direcția vectorului (sau în direcție inversă pentru o problemă minimă) se determină punctul extrem al poligonului soluție, unde se realizează maximul (minimul) funcției obiectiv a problemei.

3. Calculați coordonatele punctului optim găsit , rezolvând un sistem de ecuații a două linii de frontieră care se intersectează în el.

4. Substituind soluția optimă găsită în funcția obiectiv a problemei, calculați valoarea optimă a acesteia, adică: .

La construcție grafică din setul de soluții admisibile ale PLP (poligon soluție), sunt posibile următoarele situații.

În această lecție ne vom familiariza metoda grafica solutii probleme de programare liniară, adică astfel de probleme în care se cere să se găsească o soluție la un sistem de ecuații liniare și (sau) inegalități (sistem de constrângeri) în care funcția obiectiv - o funcție liniară - capătă valoarea optimă.

Datorită faptului că claritatea soluției grafice se realizează numai pe plan, ne putem familiariza cu reprezentare grafică probleme numai în spațiul bidimensional. Această reprezentare este potrivită pentru un sistem de constrângeri de inegalitate cu două variabile sau pentru sisteme de ecuații în care numărul de variabile depășește numărul de ecuații cu 2, adică numărul de variabile libere este două.

Prin urmare, metoda grafică are un domeniu de aplicare atât de restrâns încât nu se poate vorbi despre ea ca o metodă specială pentru rezolvarea problemelor de programare liniară.

Cu toate acestea, să producă reprezentări vizuale Pentru rezolvarea problemelor de programare liniară, metoda grafică prezintă un oarecare interes. În plus, ne permite să confirmăm geometric validitatea teoreme de programare liniară .

Fundamentele teoretice ale metodei grafice

Deci, aceasta este o problemă de programare liniară. Este necesară găsirea valorilor nenegative ale variabilelor și satisfacerea sistemului de inegalități

la care forma liniară capătă valoarea optimă.

Exemplul 3.

Exemplul 4. Rezolvați o problemă de programare liniară folosind o metodă grafică în care trebuie să găsiți minimul unei funcții sub constrângeri

Continuăm să rezolvăm împreună probleme folosind metoda grafică

Concluziile la care s-a ajuns până acum s-au bazat pe faptul că setul de soluții la o problemă de programare liniară este configurat astfel încât soluția optimă să fie finită și unică. Acum să ne uităm la exemple în care această condiție este încălcată. În aceste exemple, poligonul soluției este construit așa cum se arată în exemplele anterioare; să ne oprim asupra caracteristicilor care disting aceste exemple excepționale.

Exemplul 5. Rezolvați o problemă de programare liniară folosind o metodă grafică în care trebuie să găsiți maximul unei funcții sub constrângeri

Soluţie. Figura prezintă: o zonă de soluție poliedrică nelimitată pentru acest sistem de constrângeri, o linie de nivel inițială (neagră), un vector (culoare visiniu) care indică direcția de mișcare a liniei de nivel inițial pentru a găsi maximul funcției obiectiv.

Este ușor de observat că funcția F poate crește fără limită cu sistem dat restricții, așa că putem scrie condiționat că .

Exemplul 6. Rezolvați o problemă de programare liniară folosind o metodă grafică în care trebuie să găsiți maximul unei funcții sub constrângeri