Matematică și

Modelarea economico-matematice. problemă de programare liniară. Metoda grafică pentru rezolvarea

Metoda grafică pentru rezolvarea problemelor de programare liniară se aplică numai în cazul a două variabile. Să considerăm problema cu două variabile x1 și constrângeri X2 și m - inegalitățile

Primul pas în utilizarea metodei grafice este o reprezentare geometrică a setului tuturor soluțiilor fezabile, adică în construcție pe zona planului în care ambele îndeplinite toate limitările modelului. Această zonă se numește admisibilă. Această din urmă condiție (43) înseamnă că soluțiile fezabile reprezentate prin puncte de primul cadran non-negativ. ecuație

Aceasta este ecuația de o linie dreaptă într-un avion. inegalitate

determină semiplanul, culcat pe o parte a acestei linii. Pentru a determina locația acestei semiplanul în raport cu linia de delimitare, puteți înlocui coordonatele orice punct din inegalitatea corespunzătoare și să verifice-l. Dacă este adevărat, toată semiplanul, care este punctul, este soluția. Locul geometric al punctelor care satisfac un sistem de inegalități (43), este intersecția semiplanuri definite prin linii

Această regiune este un poligon convex sau un set convexă poligonală, în cazul în care este nelimitată. Setul intersecție poligon și

De asemenea, cadran nenegativ este un set de poligon convex. O parte a planului în care restricția în cauză se efectuează sub formă de inegalitate este indicată de săgeata îndreptată în direcția variabilelor admisibile. Căutând zona de soluții fezabile prezentate mai jos.

A doua etapă a metodei grafice este interpretarea geometrică convenabilă a funcției obiectiv. Pe plan, putem trage doar nivelul liniei acestei funcții, adică, linia de la care funcția obiectiv are o valoare constantă definită. Locul geometric al punctelor (x1. X2), în care funcția țintă presupune valoarea determinată de ecuația L.

adică, o linie dreaptă perpendicular pe vectorul c = (c1. c2). care indică direcția de creștere a funcției țintă. Prinderea parametrul L valori posibile, vom obține familia de linii drepte paralele, umple tot avionul. Trecerea de la o linie la alta familie în direcția definită de vectorul, conduce la o creștere a funcției obiectiv. Mișcarea în direcția opusă duce la o scădere a valorii sale. De-a lungul unei funcții obiectiv drept este constantă.

A treia etapă a metodei grafice este transferul paralelă a curbelor de nivel ale funcției obiectiv.

Crucea poligon decizii directe permise și se va muta paralel cu ea însăși, în direcția de creștere L (în cazul în care problema este rezolvată la maximum a funcției obiectiv) sau în direcția de scădere L (dacă doriți să calculeze minimul funcției obiectiv). Deplasarea a avut loc drept până la o astfel de poziție limită atunci când condițiile conținute în poligon este mai mică (în rezolvarea problemei la maxim) sau la partea superioară (în rezolvarea problemelor din cel) semiplanul generat de linia limită corespunzătoare. În acest caz, cel puțin cel puțin un punct din condițiile poligon ar trebui să aparțină acestei linii de limitare. Acest punct definește soluția problemei. În rezolvarea problemelor de programare liniară prin metode grafice sunt trei posibilități:

• deplasare paralelă va avea ca rezultat o linie dreaptă într-o poziție în care acesta va avea un punct comun cu regiunea fezabilă. În acest caz, problema are o soluție unică;
• linie este paralelă cu o parte a zonei de soluții fezabile. În acest caz, minimul este atins la toate punctele din regiunea laterală corespunzătoare a soluțiilor fezabile;
• în direcția de creștere sau descreștere a funcției obiectiv regiune fezabilă este nemărginită. În acest caz, problema nu are nici o soluție.

Planul optim este atins la extremitățile domeniului de definire a funcției obiectiv - la vârfurile poliedru de soluții fezabile.

Noi ilustrează metoda de soluții grafice pentru problema băncii.

Zugrăvi planul setului fezabil de soluții ale problemei corespunzătoare intersecției semiplanuri definite de inegalitățile.

În graficul numărul 1 codifică o linie dreaptă care corespunde primului număr de restricție sarcină 2 codifică o linie dreaptă care corespunde celei de a doua restricție numărul sarcină 3 codifică o linie dreaptă care corespunde celei de a treia problemă de limitare. Săgețile indică jumătate planul respectiv satisface constrângerile problemei. Intersecția acestor semiplanuri este triunghiul ABC, care este un set de soluții fezabile de problema noastră. Noi construim un plan al funcției obiectiv la nivelul liniei L = 0, care va avea forma

Dacă mutat paralel cu ea însăși această funcție obiectiv nivelul liniei care trece printr-o multitudine de soluții viabile în direcția vectorului c = (0,15; 0,1) funcții pentru a crește până la această linie va avea cel puțin un punct în comun cu setul admisibil , linia specificată în poziția extremă trece prin punctul de set de soluții fezabile, în care funcția obiectiv atinge valoarea sa maximă. punctul maxim constatat este situat la intersecția liniilor 1 și 3. Coordonatele sunt obținute prin rezolvarea următorul sistem de ecuații liniare:

Soluția acestui sistem sunt numere x1 = x2 = 70 și 30, care definesc portofoliul optim de active, în care suma maximă profit fmax = 0,15 · 70 + 0,1 x 30 = 13,5. Soluția rezultată este că trebuie să plasați în credite, și 30 de milioane de $. Pentru a investi în titluri de valoare în cadrul acestui scenariu, banca va face un profit de 13,5 milioane de $ la 70 de milioane de $ ..

Sarcină. Micul Compania produce două tipuri de produse: mese și scaune. Pentru fabricarea unui scaun necesită 3 ft lemn, iar pentru a face o secțiune - 7 picioare. La fabricarea de scaun frunze 2 ore de timp de lucru, precum și pentru fabricarea secțiunii - 8 ore. Fiecare scaun aduce un profit de $ 1, și fiecare masă -. $ 3 Câte scaune și mese ar trebui să facă această firmă, dacă are 420 de picioare de lemn și 400 de ore de lucru și vrea să obțină profit maxim.?