Scopul - de a găsi în punctul de poligon AFEDCB la care obiectivul funcția Z = 2x1 + 3x2 are o valoare maximă.
Desenați o linie 2x1 + 3x2 = const (linia de nivel), astfel încât să intersecteze AFEDCB poligon (de exemplu, Const = 10). Această linie în figură arată nivelul liniei punctate.
Dacă luăm în considerare valoarea unei funcții obiectiv Z liniară în setul de puncte (x1, x2), linia punctată aparținând segmentului, localizat în interiorul hexagonului, atunci ele sunt egale cu aceeași valoare (Const = 10).
Se determină direcția de creștere a funcției. Pentru a face acest lucru, vom construi un nivel de linie cu o valoare mai mare. Acesta va fi o linie dreaptă paralelă cu construcția, dar locația este corect. Deci, într-o anumită direcție de obiective creșterea valorii funcției în interesul nostru să-l miște cât mai mult posibil în această direcție.
Deplasarea poate fi continuată atâta timp cât linia mobilă intersectează un poligon de soluții fezabile. Ultima poziție a liniei atunci când are un punct comun cu AFEDCB poligon (punctul C), valoarea maximă a funcției obiectiv Z și a ajuns la punctul cu coordonatele x1 = 4/3 ( »1.333), x2 = 10/3 (“ 3.333) . Z = 38/3 care ( »12.667).
Acest obiectiv este rezolvat complet. Din considerente geometrice efectuate este clar că singura soluție. Să facem unele generalizări care decurg din interpretarea geometrică a problemei.
În primul rând. Regiunea Fezabil - poligon convex (convexe De ce zona de soluții fezabile reprezintă punctul setat gol croială dreaptă Beam Dacă da, da un exemplu de limitările sistemului ??????).
În al doilea rând. Valoarea maximă a funcției obiectiv este atins în partea de sus a poligonului de soluții fezabile
47. Condiția de optimalitate pentru rezolvarea problemelor de programare liniară
Esența principiului optimalităii este un efort de a alege o decizii de planificare și gestionare. în cazul în care - componentele pe care le ia în considerare cel mai bine posibilitatea de a condițiilor interne și externe ale activității de producție a subiectului de gestionare.
Cuvintele „cel mai bun“ aici înseamnă alegerea unor criterii de optimalitate, și anume, Anumiți indicatori economici pe baza cărora să compare eficacitatea diferitelor decizii de planificare și management. Criterii de optimalitate tradiționale „profit maxim“, „low cost“, „cantitatea maximă de lucrări (servicii)“ și altele.
Cuvintele „ar lua în considerare posibilitatea de a condițiilor interne și externe ale activității de producție“ înseamnă că alegerea de soluții de management (comportament) impune o serie de condiții, și anume, Selecția se face dintr-o serie de posibile (admisibile) a soluțiilor D; acest domeniu este numit, de asemenea, domeniul de definire a problemei.
Astfel, pentru a pune în practică principiul optimalității în planificarea și managementul - acest lucru înseamnă că pentru a rezolva problema extremă a formei
în cazul în care - notație matematică criteriu de optimalitate - funcția obiectivă a problemei (model) de optimizare.
problema constrânse de optimizare (2.1), (2.2) este de obicei scrisă sub forma:
pentru a găsi maximul sau minimul funcției
Condiția (2.5) este opțională, dar poate fi realizată întotdeauna, dacă este necesar. Desemnarea indică faptul că un anumit una dintre posibilele semne de restricție ≤, = sau ≥. Mai multe notația compactă:
Problema (2.6) - (2.8) - problema generală a condiții optime a programului (matematică), sau - un model matematic al problemei optime de programare, bazată pe construcția (dezvoltare), pe principiile optimalitate, consecvența și caracterul adecvat.
Vector (un set de variabile de control x j. J = 1, 2, n) se numește o soluție fezabilă sau un plan de probleme optime de programare, în cazul în care componentele sale satisfac sistemul de constrângeri xj. Și planul (soluție fezabilă), care oferă o valoare maximă sau minimă a funcției obiectiv f (x1. X2. Xn) este numit un plan de optim (comportament optim, sau pur și simplu decizia) de programare optimă.
Astfel, selectarea gestionarea optimă a comportamentului într-o anumită situație de muncă este legată de realizarea unei poziții sistematică, adecvarea și modelare economică și matematică optimă și soluția a programării optime.
Rezolva problema de programare optimă (pentru a obține o soluție pentru optimizarea modelului economico-matematic) - aceasta înseamnă:
- Mai întâi, găsiți planul optim,
care, ținând seama de interpretarea componentelor sale, și determină comportamentul optim în această situație;
- în al doilea rând, pentru a găsi valoarea optimă (minimă maximă sau) funcția obiectiv. care reprezintă, de asemenea, o evaluare economică a consecințelor soluțiilor propuse (conduită).
Uneori este imposibil să se obțină o soluție a unui model de optimizare: zona de soluții viabile poate fi un set de gol (sarcina este contradictorie) sau funcția obiectiv este nemărginit în domeniu.
Primul caz este legat de incorecte pus în scenă sau probleme economice (e) a dezvoltat modelul economic și matematic (EMM). De exemplu, cu nivelul existent de resurse nu poate fi făcut cunoscut nici măcar suma minimă de muncă, care sunt stabilite într-un stagiu ca obiectivele minime necesare. Dacă în această situație, este încă necesar să se găsească o soluție la problema, este necesar să se construiască un set de non-gol de soluții fezabile prin eliminarea uneia sau mai multor constrângeri, și anume, de fapt, în conformitate cu principiul unei o alternativă.
Al doilea caz înseamnă, de obicei, că EMM este proiectat în mod corect și unele limitări semnificative îi lipsește.
sarcini de programare optime în forma cea mai generală, clasificate în conformitate cu următoarele criterii.
1. Natura relației dintre variabilele:
În cazul (a) toate legăturile funcționale în constrângerile de sistem și funcția obiectiv - funcție liniară, prezența neliniaritate în cel puțin unul dintre aceste elemente conduce la cazul (b).
2. Prin natura variabilelor modificărilor:
În cazul (a) valoarea fiecăruia dintre variabilele de control pot umple complet un anumit domeniu de numere reale, în cazul (b) toate sau cel puțin o variabilă poate lua numai valori întregi.
3. Având în vedere factorul timp:
Problemele (a) de modelare și de luare a deciziilor se efectuează în ipoteza independenței elementelor de timp ale modelului pe o perioadă de timp în care se ia deciziilor de planificare și gestionare. În cazul (b) o astfel de ipoteză este făcută suficient motivată nu poate fi și trebuie să ia în considerare factorul timp.
1. În prezența informații despre variabilele:
a) sarcini cu certitudine absolută (deterministe);
b) sarcinile în condiții de informații incomplete;
c) sarcinile în condiții de incertitudine.
Problemele (b) elementele individuale sunt valori de probabilitate, cu toate acestea, sunt cunoscute sau studii statistice suplimentare pot fi stabilite legi ale distribuțiilor de probabilitate. În cazul (b) se poate face o presupunere cu privire la rezultatele posibile ale elementelor aleatorii, dar nu se poate trage o concluzie cu privire la rezultatul probabil.
2. În conformitate cu numărul de alternative la criteriile de evaluare:
a) o simplă problemă de un criteriu;
b) un complex, sarcini de mai multe criterii.
Problemele (a) acceptabil din punct de vedere economic de a utiliza un criteriu de optimalitate sau să poată proceduri speciale (de exemplu, „cântărire prioritățile“) pentru a reduce căutare multi-criterii la un criteriu; Probleme Exemple multiobiectiv sunt discutate în Capitolul 3.
Combinația de caracteristici permite grupa 1-5 (clasificate) sub forma generală a problemei și tehnicile de programare optime, cum ar fi: 1a) 2a) 3a) 4a) 5a) - obiective și metode de programare liniară, 1b) 2a) 3a) 4a) 5a) - obiective și metode de programare neliniare, 1a), 2b) 3a) 4a) 5a) - probleme și metode întregi (discrete) de programare liniară, etc.
Noi oportunități pentru aplicarea practică largă de metode de programare optime sunt facilități moderne de birouri. O gamă largă de profesioniști în practica lor de zi cu zi de utilizare componentă esențială a calculelor economice și financiare - Microsoft Excel (MS Excel), care conține o caracteristică specială - Solver, care permite modelului să pună în aplicare liniare, neliniare și optimizare discretă. Tehnologia de optimizare folosind Solver cu rezolvarea anumitor tipuri de probleme de programare optimă în mediul MS Excel este discutată în detaliu, de exemplu, în literatura de specialitate.
48. definiții de bază teoria dualității.
Fiecare problemă de programare liniară poate fi asociată cu o altă problemă de programare liniară. În rezolvarea uneia dintre ele va fi rezolvată în mod automat o altă problemă. Astfel de probleme sunt numite vzaimodvoystvennymi. Ne arată cum la această problemă (vom numi originalul) pentru a construi dubla sale.
Luați în considerare problema de fire 3.8 din producția planificată.
Noi construim sarcina sa dublă de după reguli.
Numărul de variabile în problema duală este numărul de inegalități în original.
Matricea Coeficientul problemei dublă este transpusă la coeficienții matricei originale.
Coloana de termeni liberi de problema originală este un șir de coeficienți pentru funcția obiectiv a dublu. Funcția obiectiv este maximizată într-o sarcina la alta este redusă la minimum.
Condițiile de non-negativitate variabilelor corespund problemei inițiale, constrângerile duale ale inegalității vizează alt mod. Pe de altă parte, inegalitățile, restricțiile în original, la o concordanță condițiile de nenegativitate duală.
Rețineți că sarcina I rânduri de coloane ale matricei sunt probleme II. Prin urmare, coeficienții variabilelor în problema yi II - sunt, respectiv, coeficienții de i-lea problema inegalității I.
Inegalitățile sunt conectate prin săgeți, sunt conjugate.