Lucrări de laborator nr. 1
Obiectiv: studierea unor instrumente software moderne pentru rezolvarea problemei de programare liniară; soluția practică a problemelor de programare liniară prin metoda grafică, metoda simplex și instrumentele MicrosoftExcel; implementarea software a metodei simplex în limba de programare la nivel înalt.
1. Partea teoretică
Pentru a rezolva problemele de programare liniară în Microsoft Excel, există un add-on Găsirea unei soluții, acces la care se face din meniul Instrumente.
Dacă comanda Find Solution nu este disponibilă în meniul Instrumente. atunci trebuie să instalați Găsirea Add-on. Pentru aceasta, selectați comanda Add-in din meniul Tools. care deschide caseta de dialog din Fig. 1.
În continuare, în această fereastră este instalată caseta de selectare a programului de adăugare pe care doriți să o descărcați și este apăsat butonul OK.
Afișăm folosirea add-on-ului "Găsirea soluțiilor" utilizând exemplul de rezolvare a problemei următoare.
Formularea problemei
Întreprinderea produce și vinde trei tipuri de produse - P1. P2 și P3. Pentru producție sunt utilizate trei tipuri de resurse: componente, materii prime și materiale. Stocurile de resurse și cheltuielile acestora pentru producerea unei unități de producție a fiecărei specii sunt prezentate în tabelul nr. 1.
Profitul din vânzarea unei unități de produs de fiecare tip este de 240, 210 și 180 de unități monetare pentru P1. P2 și, respectiv, P3.
Este necesar să se determine programul de producție al întreprinderii astfel încât profitul din vânzarea producției să fie maxim.
Modelul matematic al problemei
Indicăm variabilele x1. x2 și x3 reprezintă volumele necesare de producție a speciilor P1. P2 și P2. iar F este profitul întreprinderii. Apoi, formularea matematică a problemei prezentate are următoarea formă.
Determinați valorile variabilelor x1. x2 și x3. pentru care se atinge maximul funcției obiective
Funcția obiectivă descrie profitul total din vânzarea produselor din toate cele trei tipuri. Limitările (1), (2) și (3) iau în considerare consumul și, respectiv, stocurile de componente, materii prime și materiale. Deoarece volumele de producție nu pot fi negative, se adaugă condiții
X1 ≥ 0; x2 ≥ 0; x3 ≥ 0. Ordinea soluției optime a problemei
Acțiunile aproximative necesare pentru a rezolva problema de programare liniară folosind Excel pot fi reprezentate ca o serie de pași.
Pasul 1. Datele originale ale sarcinii sunt scrise în foaia de calcul tabelar. Una dintre opțiuni este prezentată în Fig. 2.
Notă. Dacă soluția de bază inițială admisibilă este cunoscută, atunci putem accelera într-o oarecare măsură procesul de găsire a soluției optime. Pentru aceasta, valorile inițiale ale unora sau tuturor variabilelor pot fi specificate manual. În acest exemplu, celulele $ B $ 2, $ C $ 2 și $ D $ 2 sunt folosite pentru a le stoca. Dacă nu este specificată o soluție de bază acceptabilă, Excel determină automat valorile inițiale ale variabilelor task.
Pasul 2. În celula E3 introduceți formula
pentru a calcula valoarea curentă a funcției obiectiv care găsește suma perechilor de produse ale celulelor (B3: D3) cu coeficienții variabilelor în expresia funcției obiectiv pe celule ($ B $ 2: $ D $ 2) cu valorile curente ale variabilelor.
Pasul 3. Pentru a stabili constrângerile problemei care trebuie rezolvată, o formula din celula E3 este copiată în celulele E5, E6 și E7. După aceasta, formulele din tabelul 1 trebuie obținute în aceste celule. 2.
Pasul 4. După crearea tabelului cu datele originale, cursorul este plasat în celula E3 care conține formula pentru calcularea funcției obiectiv. Apoi, în meniul Instrumente, este selectată comanda Find Solution. care deschide caseta de dialog din Fig. 3.
Apoi, în această fereastră (Figura 3) sunt completate următoarele câmpuri ale acestei ferestre:
- în câmp Comutatorul egal al formei extremumului funcției obiectiv este setat la poziția valorii maxime (sau a valorii minime pentru instrucțiunea corespunzătoare a problemei);
- în câmpul Modificarea celulelor, specificați intervalul de celule cu valorile variabilelor de sarcină care sunt alocate în foaia de lucru a foii de calcul (în exemplul respectiv, acestea sunt celulele $ B $ 2: $ D $ 2);
- în câmpul Limite, sunt setate constrângerile din sarcina inițială. Pentru a face acest lucru, cursorul este setat în câmpul de introducere a constrângerilor și este apăsat butonul Adăugare. Ca rezultat, caseta de dialog Add Limit, prezentată în Fig. 4.
Apoi se selectează forma relației care leagă părțile stânga și dreapta ale constrângerii, care este prezentată în Fig. 5.
După ce faceți clic pe butonul Adăugați în fereastra "Adăugați restricție" (sau pe butonul OK pentru a introduce ultima restricție), această restricție se încadrează în lista de constrângeri a sarcinii care este rezolvată. Utilizând butoanele Ștergere și Modificare, puteți șterge sau modifica restricțiile din listă.
Notă. În fereastra "Adăugare restricție", puteți specifica faptul că toate sau unele variabile ar trebui să ia doar valori întregi (a se vedea Figura 5). Aceasta vă permite să obțineți soluții pentru rezolvarea problemelor de programare liniară întreg (integral sau parțial întreg).
Pasul 5. După completarea tuturor câmpurilor ferestrei "Find Solution", faceți clic pe butonul Parametri (Figura 3), care deschide caseta de dialog "Opțiuni de căutare", prezentată în Fig. 6.
În această fereastră, trebuie să selectați casetele de selectare Mod Linear pentru a rezolva problema de programare liniară și Valori non-negative dacă această condiție este suprapusă peste toate variabilele task.
Aici (Figura 6) puteți determina, de asemenea, parametrii procesului decizional: timpul maxim de căutare a deciziei, numărul maxim de iterații, precizia și așa mai departe. Caseta de verificare Afișarea rezultatelor iterațiilor vă permite să urmați pașii pentru a găsi soluția în pași. Caseta de validare automată este activată când variația valorii variabilelor este foarte mare.
Pasul 6. După ce ați setat parametrii necesari în fereastra "Opțiuni căutare soluție", faceți clic pe butonul Execute pentru a găsi soluția la problemă (Figura 3) în fereastra "Find Solution". Dacă găsiți o soluție, o fereastră cu mesajul corespunzător este afișată pe ecran (Figura 7).
Rezultatele sunt afișate pe foaia de lucru a foii de calcul, așa cum se arată în Fig. 8. În special, valorile variabilelor sunt în celulele $ B $ 2: $ D $ 2, valoarea funcției obiectiv este în celula E3.
Astfel, am obținut soluția optimă a problemei inițiale sub forma unui vector, unde
Rezultatele rezolvării problemei de programare liniară pot fi de asemenea salvate ca foi de lucru separate, cu numele Raportul de rezultate, Raportul de sustenabilitate și Raportul limită. Pentru a salva rezultatele ca rapoarte, trebuie mai întâi să selectați tipurile de rapoarte necesare în câmpul Tip raport (Figura 7). În aceeași fereastră, puteți renunța la soluțiile primite și puteți restabili valorile inițiale ale variabilelor.
Un raport privind rezultatele problemei este prezentat în Fig. 9.
Acest raport prezintă o soluție optimă la problema de programare liniară și localizarea acesteia în domeniul soluțiilor fezabile. În grafice, rezultatul este valorile optime ale funcției obiective F * și ale variabilelor de sarcină
Notă. În interpretarea economică, constrângerile aferente corespund unor resurse limitate. Pentru constrângerile grafice independente, diferența arată cantitățile rămase de resurse neutilizate neutilizate. În problema considerată, constrângerile (1) și (3) corespund completă produselor și materialelor care sunt resurse limitate. Constrângerea (2) nu are legătură, adică nu afectează planul optim de producție cu criteriul profitului maxim. Aceasta înseamnă că a doua resursă (materii prime) nu a fost utilizată în cantitate de 292,5 unități.
Raportul asupra stabilității (fig. 10) prezintă variabilele problemei limitei de stabilitate (coloane creștere admisibilă și scăderea coeficientului admisibil al funcției obiectiv), precum și stabilitatea prețurilor umbră de frontieră (adică variabilele problemei duală), în care soluția optimă nu este schimbat. valori mari ale limitelor (1E + 30) înseamnă lipsa efectivă a limitelor corespunzătoare, adică, variabila se poate schimba la infinit.
În coloana Valoarea normalizată, elementul din al doilea rând (-150) arată cât scade valoarea funcției, dacă în soluție variabila x2 este mărită cu una. Pe de altă parte, cu o creștere admisibilă a coeficientului funcției pentru x2 necunoscută cu 150 de unități, valoarea acestei variabile nu se va schimba, adică necunoscutul x2 va fi zero și dacă depășiți creșterea admisibilă (coeficientul de x2 este mărit cu mai mult de 150), atunci necunoscutul x2 din soluție va fi mai mare decât zero.
Raportul privind limitele (Fig. 11) prezintă limitele inferioare și superioare ale posibile variații ale variabilelor (în domeniul soluțiilor fezabile) și corespunzătoare valorile funcției obiective (rezultate coloană țintă) pentru aceste schimbări. În particular, dacă x1 = 0 și x2 și x3 rămân neschimbate, atunci F = 2400 + 2100 + 180191,25 = 34,425; x3 = 0 dacă și x1 și x2 constantă obține F = 240397,5 + 2100 + 1800 = 95400.
Articole similare
Trimiteți-le prietenilor: