Meniul
AcasăBrowsere

Căutați soluția MS EXCEL. Cunoștință. Pregatirea unui model de optimizare in MS EXCEL


. Algoritmul metodei simplex

Exemplul 5.1. Rezolvați următoarea problemă programare liniară metoda simplex:

Soluţie:

eu repetare:

x3, x4, x5, x6 x1,x2. Să exprimăm variabilele de bază în termeni de cele libere:

Să reducem funcția țintă la următoarea vedere:

Pe baza problemei obținute, vom forma tabelul simplex inițial:

Tabelul 5.3

Tabel simplex original

Relații evaluative

Conform definiției solutie de baza variabilele libere sunt egale cu zero, iar valorile variabilelor de bază sunt egale cu valorile corespunzătoare ale numerelor libere, adică:

Etapa 3: verificarea compatibilității sistemului de restricții PAP.

La această iterație (în Tabelul 5.3), semnul de incompatibilitate al sistemului de constrângeri (semnul 1) nu este identificat (adică nu există nicio linie cu un număr liber negativ (cu excepția liniei). funcție obiectivă), în care nu ar exista cel puțin un element negativ (adică un coeficient negativ pentru o variabilă liberă)).

La această iterație (în Tabelul 5.3), semnul de nemărginire al funcției obiectiv (semnul 2) nu a fost identificat (adică nu există nicio coloană cu un element negativ în rândul funcției obiectiv (cu excepția coloanei numerelor libere). ) în care nu ar exista cel puţin un element pozitiv) .

Deoarece soluția de bază găsită nu conține componente negative, este admisibilă.

Etapa 6: verificarea optimității.

Soluția de bază găsită nu este optimă, deoarece conform criteriului de optimitate (semnul 4) nu ar trebui să existe elemente negative în linia funcției obiectiv (numărul liber al acestei linii nu este luat în considerare la considerarea acestui criteriu). Prin urmare, conform algoritmului metodei simplex, trecem la etapa 8.

Întrucât soluția de bază găsită este admisibilă, vom căuta coloana de rezolvare după următoarea schemă: determinăm coloanele cu elemente negative din rândul funcției obiectiv (cu excepția coloanei numerelor libere). Conform Tabelului 5.3, există două astfel de coloane: coloana „ x1„și coloana” x2" Din astfel de coloane se selectează cel care conține cel mai mic element din rândul funcției țintă. Ea va fi cea permisivă. Coloana " x2" conține cel mai mic element (–3) în comparație cu coloana " x1

Pentru a determina linia de rezolvare, găsim rapoartele pozitive estimate ale numerelor libere la elementele coloanei de rezolvare; linia care corespunde celui mai mic raport de evaluare pozitivă este acceptată ca rezolvată.

Tabelul 5.4

Tabel simplex original

În tabelul 5.4, cea mai mică relație de evaluare pozitivă corespunde liniei „ x5„, prin urmare, va fi permisiv.

Elementul situat la intersecția coloanei de activare și a rândului de activare este acceptat ca activator. În exemplul nostru, acesta este elementul care se află la intersecția liniei „ x5„și coloane” x2».

Elementul de rezolvare arată o bază și o variabilă liberă care trebuie schimbate în tabelul simplex pentru a trece la o nouă soluție de bază „îmbunătățită”. ÎN în acest caz, acestea sunt variabile x5Și x2, în noul tabel simplex (Tabelul 5.5) le schimbăm.

9.1. Transformarea elementului rezolutiv.

Elementul de rezoluție din tabelul 5.4 este convertit după cum urmează:

Introducem rezultatul rezultat într-o celulă similară din Tabelul 5.5.

9.2. Conversie șir de rezoluție.

Împărțim elementele rândului de rezolvare a tabelului 5.4 la elementul de rezolvare al acestui tabel simplex, rezultatele se încadrează în celule similare ale noului tabel simplex (tabelul 5.5). Transformările elementelor șirului de rezoluție sunt date în Tabelul 5.5.

9.3. Conversia coloanei de rezoluție.

Împărțim elementele coloanei de rezoluție din tabelul 5.4 la elementul de rezoluție al acestui tabel simplex, iar rezultatul este luat cu semnul opus. Rezultatele obținute se încadrează în celule similare ale noului tabel simplex (Tabelul 5.5). Transformările elementelor coloanei de rezoluție sunt date în Tabelul 5.5.

9.4. Transformarea elementelor rămase ale tabelului simplex.

Transformarea elementelor rămase ale tabelului simplex (adică elementele care nu sunt situate în rândul de rezolvare și coloana de rezolvare) se efectuează conform regulii „dreptunghi”.

De exemplu, luați în considerare transformarea unui element situat la intersecția liniei " x3„ și coloanele „”, îl vom desemna condiționat „ x3" În tabelul 5.4, desenăm mental un dreptunghi, al cărui vârf se află în celula a cărei valoare o transformăm (adică în celula „ x3"), iar celălalt (vertex diagonal) este într-o celulă cu un element de rezoluție. Celelalte două vârfuri (ale celei de-a doua diagonale) sunt determinate în mod unic. Apoi valoarea transformată a celulei " x3" va fi egală cu valoarea anterioară a acestei celule minus fracția, în numitorul căreia se află elementul de rezoluție (din tabelul 5.4), iar în numărător este produsul altor două vârfuri neutilizate, adică:

« x3»: .

Valorile altor celule sunt convertite în mod similar:

« x3 x1»: ;

« x4»: ;

« x4 x1»: ;

« x6»: ;

« x6 x1»: ;

«»: ;

« x1»: .

Ca urmare a acestor transformări, a fost obținut un nou tabel simplex (Tabelul 5.5).

II repetare:

Etapa 1: întocmirea unui tabel simplex.

Tabelul 5.5

Tabel simplexII iterații

Estimată

relaţie

Etapa 2: determinarea soluției de bază.

Ca rezultat al transformărilor simplex, a fost obținută o nouă soluție de bază (Tabelul 5.5):

După cum puteți vedea, cu această soluție de bază valoarea funcției obiectiv = 15, care este mai mare decât cu soluția de bază anterioară.

Incoerența sistemului de restricții în conformitate cu caracteristica 1 din Tabelul 5.5 nu a fost identificată.

Etapa 4: verificarea mărginirii funcției obiectiv.

Nelimitarea funcției obiectiv în conformitate cu criteriul 2 din Tabelul 5.5 nu este dezvăluită.

Etapa 5: verificarea admisibilității soluției de bază găsite.

Soluția de bază găsită conform criteriului 4 nu este optimă, deoarece linia funcției obiectiv a tabelului simplex (Tabelul 5.5) conține un element negativ: –2 (numărul liber al acestei linii nu este luat în considerare atunci când se consideră acest lucru caracteristică). Prin urmare, trecem la etapa 8.

Etapa 8: determinarea elementului rezolutiv.

8.1. Definiția coloanei de rezoluție.

Soluția de bază găsită este acceptabilă; determinăm coloanele cu elemente negative în rândul funcției obiectiv (cu excepția coloanei numerelor libere). Conform Tabelului 5.5, există o singură astfel de coloană: „ x1" Prin urmare, îl acceptăm așa cum este permis.

8.2. Definiția unui șir de activare.

Conform valorilor obținute ale relațiilor evaluative pozitive din tabelul 5.6, minimul este relația corespunzătoare liniei „ x3" Prin urmare, îl acceptăm așa cum este permis.

Tabelul 5.6

Tabel simplexII iterații

Estimată

relaţie

3/1=3 – min

Etapa 9: transformarea tabelului simplex.

Transformările tabelului simplex (Tabelul 5.6) sunt efectuate în același mod ca în iterația anterioară. Rezultatele transformărilor elementelor tabelului simplex sunt prezentate în Tabelul 5.7.

III repetare

Pe baza rezultatelor transformărilor simplex ale iterației anterioare, compilam un nou tabel simplex:

Tabelul 5.7

Tabel simplexIII iterații

Estimată

relaţie

Etapa 2: determinarea soluției de bază.

Ca rezultat al transformărilor simplex, a fost obținută o nouă soluție de bază (Tabelul 5.7):

Etapa 3: verificarea compatibilității sistemului de restricții.

Incoerența sistemului de restricții în conformitate cu caracteristica 1 din Tabelul 5.7 nu a fost identificată.

Etapa 4: verificarea mărginirii funcției obiectiv.

Nelimitarea funcției obiectiv în conformitate cu criteriul 2 din Tabelul 5.7 nu este dezvăluită.

Etapa 5: verificarea admisibilității soluției de bază găsite.

Soluția de bază găsită în conformitate cu criteriul 3 este acceptabilă, deoarece nu conține componente negative.

Etapa 6: verificarea optimității soluției de bază găsite.

Soluția de bază găsită conform criteriului 4 nu este optimă, deoarece linia funcției obiectiv a tabelului simplex (Tabelul 5.7) conține un element negativ: –3 (numărul liber al acestei linii nu este luat în considerare atunci când se consideră acest lucru). caracteristică). Prin urmare, trecem la etapa 8.

Etapa 8: determinarea elementului rezolutiv.

8.1. Definiția coloanei de rezoluție.

Soluția de bază găsită este acceptabilă; determinăm coloanele cu elemente negative în rândul funcției obiectiv (cu excepția coloanei numerelor libere). Conform Tabelului 5.7, există o singură astfel de coloană: „ x5" Prin urmare, îl acceptăm așa cum este permis.

8.2. Definiția unui șir de activare.

Conform valorilor obținute ale relațiilor evaluative pozitive din tabelul 5.8, minimul este relația corespunzătoare liniei „ x4" Prin urmare, îl acceptăm așa cum este permis.

Tabelul 5.8

Tabel simplexIII iterații

Estimată

relaţie

5/5=1 – min

Etapa 9: transformarea tabelului simplex.

Transformările tabelului simplex (Tabelul 5.8) sunt efectuate în același mod ca în iterația anterioară. Rezultatele transformărilor elementelor tabelului simplex sunt prezentate în Tabelul 5.9.

IV repetare

Etapa 1: construirea unei noi mese simplex.

Pe baza rezultatelor transformărilor simplex ale iterației anterioare, compilam un nou tabel simplex:

Tabelul 5.9

Tabel simplexIV iterații

Estimată

relaţie

–(–3/5)=3/5

–(1/5)=–1/5

–(9/5)=–9/5

–(–3/5)=3/5

Etapa 2: determinarea soluției de bază.

Ca urmare a transformărilor simplex s-a obținut o nouă soluție de bază; conform tabelului 5.9, soluția este următoarea:

Etapa 3: verificarea compatibilității sistemului de restricții.

Incoerența sistemului de restricții în conformitate cu caracteristica 1 din Tabelul 5.9 nu a fost identificată.

Etapa 4: verificarea mărginirii funcției obiectiv.

Nelimitarea funcției obiectiv în conformitate cu criteriul 2 din Tabelul 5.9 nu este dezvăluită.

Etapa 5: verificarea admisibilității soluției de bază găsite.

Soluția de bază găsită în conformitate cu criteriul 3 este acceptabilă, deoarece nu conține componente negative.

Etapa 6: verificarea optimității soluției de bază găsite.

Soluția de bază găsită în conformitate cu caracteristica 4 este optimă, deoarece nu există elemente negative în linia funcției obiectiv a tabelului simplex (Tabelul 5.9) (numărul liber al acestei linii nu este luat în considerare atunci când se ia în considerare această caracteristică) .

Etapa 7: verificarea alternativei soluției.

Soluția găsită este unică, deoarece nu există elemente zero în linia funcției obiectiv (Tabelul 5.9) (numărul liber al acestei linii nu este luat în considerare atunci când se ia în considerare această caracteristică).

Răspuns: valoare optimă funcţia obiectivă a problemei luate în considerare =24, care se realizează la.

Exemplul 5.2. Rezolvați problema de programare liniară de mai sus, cu condiția ca funcția obiectiv să fie minimizată:

Soluţie:

eu repetare:

Etapa 1: formarea tabelului simplex inițial.

Problema originala programarea liniară este dată în formă standard. Să-l aducem la formă canonică prin introducerea în fiecare dintre constrângerile de inegalitate a unei variabile suplimentare nenegative, i.e.

În sistemul de ecuații rezultat, luăm ca variabile permise (de bază). x3, x4, x5, x6, atunci variabilele libere vor fi x1,x2. Să exprimăm variabilele de bază în termeni de cele libere.

Rezolvarea ZLP folosind metoda simplex folosind tabele EXCEL

Lăsați ZLP-ul original să fie redus la forma canonică, iar sistemul său de restricții să aibă o formă preferată. De exemplu, pentru „Problema privind utilizarea materiilor prime” modelul matematic de tipul corespunzător va fi următorul:

Primul tabel simplex din foaia de lucru EXCEL va arăta ca (Fig. 10):



Presupunând că studentul este familiarizat cu algoritmul metodei simplex tabulare, vom descrie principalele etape ale implementării acesteia folosind tabelele EXCEL.

Etapa 1. Selectați coloana și rândul de activare și evidențiați elementul de activare (vezi Fig. 11).

Etapa 2. Înlocuiți coloanele „Base” și „Cb” în noul tabel conform regulilor de completare a acestora.



    Elementele liniei de autorizare sunt împărțite în elementul de autorizare și sunt scrise în linia corespunzătoare numărului masa noua:

, la i = r. (*)

    Toate celelalte elemente ale noului tabel sunt calculate folosind formulele:

, la i ≠ r (**)

unde este un element al noului tabel simplex, A ij , - elementul tabelului simplex anterior, A rk- element de autorizare, A ik- elementul coloanei de rezoluție, A rj- element al șirului de activare.

Notă . Pentru a folosi capacitatea EXCEL de a copia formule cu modificarea adreselor celulelor incluse în acestea, este recomandabil să programați formule (*) și (**) numai pentru celulele coloanei „B”, dând adrese absolute celulelor care nu schimba. Datele formulei sunt apoi copiate în toate celulele rămase din fiecare rând al noului tabel.

Etapa 4. Elemente ultima linie din noul tabel sunt completate fie folosind formule (**), fie conform regulii de completare a unui rând dat.

Rezultatele calculelor din tabelele EXCEL pentru exemplul nostru sunt prezentate în Fig. 11, iar formulele utilizate în aceste calcule sunt prezentate în Fig. 12.



    Akulich I.L. Programare matematică în exemple și probleme: Proc. manual pentru studenți la economie. specialist. universități - M.: Mai sus. şcoală, 1986.-319 p., ill.

    Sakovich V.A. Cercetare operațională (metode și modele deterministe): un ghid de referință. - Mn.: Mai sus. scoala, 1984.-256p.

    Taha H. Introducere în cercetarea operațională: în 2 cărți. Cartea 1. Pe. din engleza – M.: Mir, 1985.-479 p., ill.

    Ghid pentru orele practice la disciplina „Programare matematică” (programare liniară) pentru studenții specialităților economice / Comp. Turovtsev G.V., Nudny I.P. – Zaporojie, ZGIA, 1984.-31 p.

    Programare matematică. Note de curs pentru studenții la economie cu normă întreagă și cu normă întreagă departamente de corespondență/Glushchevsky V.V., Isaenko A.N. – Zaporojie: ZGIA, 2003. – 150 p.

Lecția 1. Rezolvarea unei probleme de programare liniară în Excel folosind programul de completare Solution Search

Metode și modele economice și matematice. Problema de alocare a resurselor. Un exemplu clasic și o soluție la o problemă de programare liniară. Descrierea modului de utilizare a programului de completare Căutare soluție în Excel. Condiția problemei aici este, mai multe exemple de rezolvare a problemelor folosind EMMM -

#EMMM #Excel #Matprogramming #Căutați o soluție #Easyhelp

Rezolvarea unei probleme de programare liniară folosind programul de completare Căutare soluție

Utilizarea suplimentului Căutare soluții pentru a rezolva probleme de programare liniară. Vă rugăm să evaluați dacă videoclipul v-a fost de ajutor.

Problemă simplă de programare liniară #2. Metoda simplex pentru găsirea maximului.

Rezolvarea unei probleme simple de programare liniară folosind metoda simplex pentru a găsi maximul. Sunt disponibile subtitrări pentru o explicație mai detaliată.




.

Problemă simplă de programare liniară #1. Metoda simplex pentru găsirea minimului.

Rezolvarea unei probleme simple de programare liniară folosind metoda simplex pentru a găsi minimul. Subtitrarile sunt disponibile pentru explicații suplimentare.


- Sarcină simplă programare liniară nr. 3. Metoda simplex pentru găsirea minimului.
- Rezolvarea unei probleme de programare liniară folosind algoritmul metodei dual simplex
- Rezolvarea problemelor LP directe si duale, constructii dubla problema LP.
- Rezolvarea unei probleme de programare liniară cu inegalități neuniforme folosind metoda simplex
- Problemă de programare liniară cu un sistem de ecuații

Cursul 2: Problemă de programare liniară. Problemă de resurse

Se are în vedere rezolvarea unei probleme de programare liniară folosind metoda simplex.
Prelegere și teste la NOU INTUIT

Programare liniară

Rezolvarea unei probleme de programare liniară folosind Găsirea unei soluții MS Excel
Materialul text de pe site se află la:

Lecția 2. Rezolvarea problemei de programare liniară duală în Excel

Analiza stabilității pentru probleme de programare liniară directă și duală în Excel. Vedeți condițiile problemei aici -, mai multe exemple de soluții ale problemei aici -

#Excel #programare matematică #easyhelp

Metoda Simplex Excel VBA (Rezolvarea unei probleme de programare liniară folosind macrocomenzi)

Demonstrație a modului în care funcționează o macrocomandă în Excel. Rezolvarea unei probleme de programare liniară folosind metoda Simplex.
Comandă o macrocomandă - [email protected]

Soluţie munca de laboratorîn Excel pentru a comanda

Metoda simplex pentru rezolvarea problemelor de programare liniară

programare liniară. Tabel simplex. Element permisiv. Șir de permisiune. Coloana permisivă. Relația simplex
Metoda grafica rezolvarea problemelor de optimizare.

Un program care implementează metoda simplex

Programul este disponibil la link-ul de mai jos:

Rezolvarea unei probleme de transport în Excel folosind programul de completare Solution Search

Problemă de programare liniară. Problema transportului. Soluție Excel, analiză de stabilitate. Condiția problemei este aici -, mai multe exemple de rezolvare a problemelor de programare matematică sunt aici -

#excel #programare matematică #Problemă de transport #Programare liniară #Căutare soluție #easyhelp #Analiza de stabilitate

Metoda duală

Metode de optimizare 12. Programare liniară, metoda simplex

Putem efectua manual metoda simplex

Putem efectua manual metoda simplex

Problemă simplă de programare liniară #3. Metoda simplex pentru găsirea minimului.

Foarte solutie detaliata o problemă simplă de programare liniară folosind metoda simplex pentru a găsi minimul.

Problemă simplă de programare liniară #1. Metoda simplex pentru găsirea minimului.
- Problemă simplă de programare liniară #2. Metoda simplex pentru găsirea maximului.
- Rezolvarea unei probleme de programare liniară folosind algoritmul metodei dual simplex
- Rezolvarea problemelor directe, dual LP, construirea problemelor dual LP.
- Rezolvarea unei probleme de programare liniară cu inegalități neuniforme folosind metoda simplex
- Problemă de programare liniară cu un sistem de ecuații

Rezolvarea unei probleme de programare liniară prin metoda grafică

După ce a construit un model al unei probleme de programare liniară în lecția video anterioară, este necesar să găsim soluția acesteia. Una dintre cele mai comune metode de optimizare este metoda grafică. Poate fi folosit dacă numărul de variabile necunoscute X nu depășește două. Avantajele metodei includ simplitatea acesteia; dezavantajele sunt că acuratețea soluției rezultate depinde de cât de corect am observat scara în timpul construcției. Tutorialul nostru video vă va învăța acest lucru.

Dacă acest videoclip ți-a adus un real beneficiu și vrei să-i mulțumești autorului:
WMR: R370550256930
WMZ: Z939960413056

În selecția noastră puteți găsi mai multe tutoriale video despre lucrul cu foi de calcul Microsoft Excel:

Puteți găsi și mai multe alte tutoriale video educaționale pe site-ul nostru:

Rezolvarea problemelor de programare liniară folosind Excel

Probleme de optimizare, probleme de programare liniară, programare dinamică- soluție folosind foi de calcul

Trimiteți-vă munca bună în baza de cunoștințe este simplu. Utilizați formularul de mai jos

Buna treaba la site">

Studenții, studenții absolvenți, tinerii oameni de știință care folosesc baza de cunoștințe în studiile și munca lor vă vor fi foarte recunoscători.

postat pe http://www.allbest.ru/

Rezolvarea problemei cu folosind Excelși metoda simplex

Sarcină (distributivă)

Metoda simplex

Rezolvarea unei probleme folosind Excel

Sarcină (distributivă)

Problema 1 (distributivă)

La întreprindere, 4 tipuri de produse pot fi produse pe 3 mașini interschimbabile separate.

Cunoscut:

· Sarcina de producție pentru lansarea produsului tipuri diferiteîn perioada planificată

· Fond pentru timpul de lucru efectiv al echipamentelor în perioada planificată - ;

· Standarde pentru costul timpului mașinii pentru producerea unei unități de producție - ;

· Profit în rub. din vânzarea unei unităţi de produs produsă pe cutare sau cutare echipament - .

Informațiile inițiale sunt afișate în tabelul din formularul următor.

Tabelul 1. Date inițiale

Fond ef. sclav. timp -

Standarde de consum de timp pe unitate produse - profit pe unitate. produse -

Problema necesită găsirea unui plan pentru distribuirea sarcinii de producție pentru producția de produs între executanți

în care sarcina ar fi finalizată cu profitul total maxim din vânzările de produse.

SOLUŢIE

Dezvoltarea unui model economic și matematic.

Variabilele cerute caracterizează volumul producției de către antreprenor.

Apoi matricea variabilelor cerute

caracterizează planul de distribuire a sarcinilor de producție pentru producția de produs între executanți.

Funcție obiectivă

caracterizarea profitului total din vânzarea tuturor produselor trebuie maximizată.

Restricțiile privind disponibilitatea și utilizarea timpului de lucru efectiv al artiștilor executanți vor lua forma unui sistem de inegalități liniare (2):

Acest sistem de restricții caracterizează condiția ca cheltuiala totală a timpului de lucru efectiv de către fiecare executant în perioada de planificare pentru producția tuturor tipurilor de produse să nu depășească fondul de timp. Astfel, ca urmare a rezolvării problemei, fiecare executant își va primi propria sarcină, în funcție de capacitățile sale. Dacă în rezolvarea unei probleme o variabilă de echilibrare capătă o valoare, aceasta va caracteriza efectivul subutilizat timp de lucru de la unul sau altul executant, care în condiții de producție poate fi folosit pentru a produce produse care depășesc specificațiile.

Următorul bloc de restricții ar trebui să reflecte condiția pentru îndeplinirea obligatorie a țintei generale de producție pentru producția de produse pe tip și va fi reprezentat de sistem ecuatii lineare (3):

Condiție pentru variabile nenegative:

Să aducem problema în formă canonică, pentru aceasta adăugăm variabile la inegalități (2), și adăugăm 4 baze artificiale la egalități (3). Ca rezultat, scriem modelul matematic al problemei în formă canonică:

Metoda simplex

Să decidem aceasta sarcina metoda simplex prin completarea tabelului. Soluția necesită mai multe iterații. Să o arătăm.

tabelul 1

În cele mai multe linia de sus Coeficienții funcției obiectiv sunt introduși în tabel, a doua linie este numele tuturor necunoscutelor incluse în ecuațiile simplex. Prima coloană din stânga conține coeficienții funcției obiectiv, care corespund necunoscutelor de bază incluse în programul original(scris în coloană). Următoarea, a treia, coloana în prima tabel simplex- umplut cu valorile necunoscutelor de bază. Urmează coloanele care reprezintă vectorii de condiție. Numărul lor este 19. În următoarea, prima coloană după matricea condițiilor, sunt scrise sumele tuturor elementelor din rânduri. Coloana înregistrează coeficientii de la împărțirea elementelor coloanei finale B în elementele unei anumite coloane, o matrice de condiții. Din moment ce avem baza artificiala, apoi în linia indexului vor fi două calcule, în primul dintre ele, ținând cont de variabile, iar în al doilea doar o bază artificială. Deoarece avem o problemă de maximizare, este necesar să derivăm baze artificiale din bază. În a doua linie de index, selectați cel mai mare evaluare pozitivă. Aceasta este prima noastră coloană. Să găsim relații de valoare

Și. Din aceste rapoarte îl selectăm pe cel mai mic, pentru noi acesta este al patrulea rând, pentru care raportul estimat este egal cu 1300. Selectați rândul. Ultima coloană este coeficientul cu care fiecare element al rândului este înmulțit în timpul recalculării. Se obține prin împărțirea elementelor coloanei selectate la elementul cheie, care se află la intersecția coloanei selectate și a rândului, pentru noi este 1. Facem recalcularea pentru toate elementele neselectate, care se efectuează ca urmează: din elementul recalculat scădem elementul rând cheie, înmulțit cu coeficientul rândului recalculat: și așa mai departe pentru toate elementele. Din bază derivăm o bază artificială, introducând o variabilă în bază.

Ultimele două linii sunt linii index în care sunt recalculate valorile funcției obiectiv, precum și întreaga linie index, când toate elementele sunt pozitive sau zero - problema va fi rezolvată.

Să o arătăm.

masa 2

Să selectăm coloana cu variabila. Găsim rapoartele estimate, din care selectăm cel mai mic - acesta este 550. Deducem o variabilă artificială din bază și, în același timp, introducem o variabilă în bază. Când o bază artificială este derivată din bază, coloana corespunzătoare este eliminată.

Tabelul 3

Să selectăm coloana. Cel mai mic raport estimat, 600, se găsește în al șaselea rând. Din bază derivăm o bază artificială, introducând o variabilă în bază.

Tabelul 4

Să selectăm coloana cu variabila. Cel mai mic raport estimat, 28,57, se află în primul rând. Deducem o variabilă din bază și introducem o variabilă în bază.

Tabelul 5

Să selectăm coloana cu variabila. Cel mai mic raport estimat, 407,7, se află în al treilea rând. Deducem o variabilă din bază și introducem o variabilă în bază.

Tabelul 6

Să selectăm coloana cu variabila. Cel mai mic raport estimat, 344,3, se găsește în al șaptelea rând. Din bază derivăm o bază artificială, introducând o variabilă în bază.

Tabelul 7

Să selectăm coloana cu variabila. Cel mai mic raport estimat, 3,273, se găsește în al doilea rând. Deducem o variabilă din bază și introducem o variabilă în bază.

Tabelul 8

Să selectăm coloana cu variabila. Cel mai mic raport estimat, 465, se găsește în al șaptelea rând. Deducem o variabilă din bază și introducem o variabilă în bază.

Tabelul 9

Să selectăm coloana cu variabila. Cel mai mic raport estimat, 109, se află în al treilea rând. Deducem o variabilă din bază și introducem o variabilă în bază.

Tabelul 10

Să selectăm coloana cu variabila. Cel mai mic raport estimat, 10, se află în primul rând. Deducem o variabilă din bază și introducem o variabilă în bază.

Tabelul 11

Să selectăm coloana cu variabila. Cel mai mic raport estimat, 147, se află în al doilea rând. Deducem o variabilă din bază și introducem o variabilă în bază.

Tabelul 12

Să selectăm coloana cu variabila. Cel mai mic raport estimat, 367, se află în al cincilea rând. Deducem o variabilă din bază și introducem o variabilă în bază.

Tabelul 13

Să selectăm coloana cu variabila. Cel mai mic raport estimat, 128, se află în al patrulea rând. Deducem o variabilă din bază și introducem o variabilă în bază.

Tabelul 14

Deoarece nu există estimări negative în linia indicelui, se obține un plan optim în care volumul producției este reprezentat de matrice

în același timp, profitul este maxim și se ridică la 17.275,31 ruble.

Rezolvarea problemei folosind excela

Modelul matematic al problemei trebuie transferat la ET EXCEL. Pentru aceasta:

· Luați în considerare organizarea datelor inițiale ale modelului (coeficienți ai funcției obiective și restricții), oferindu-le denumiri clare.

· Rezervați variabilele independente ale modelului matematic în celule separate.

· Într-una dintre celule, creați o formulă care definește funcția obiectiv.

· Selectați celule și plasați în ele formule care corespund părților din stânga constrângerilor.

· Introduceți elementul de meniu „Căutare soluție”, introduceți datele necesare și obțineți soluție optimă sarcini.

· Analizați soluția rezultată și rapoarte.

Să luăm în considerare succesiunea de acțiuni pentru implementarea acestor etape de rezolvare a unei probleme folosind EXCEL.

Să creăm un tabel pentru introducerea datelor inițiale.

Vom introduce datele inițiale în formularul creat.

Coeficienții funcției obiectiv, care exprimă profitul din producerea unei unități de produs de fiecare tip (profit unitar), se scriu în celulele B6: M6.

Coeficienții de constrângere a resurselor care determină nevoia fiecărui tip de resursă de a produce o unitate de ieșire sunt localizați în celulele B9:M15. Celulele P9:P15 conțin partea dreaptă a restricțiilor de resurse. Pentru independenți variabilele problemei- celulele B3:M3 sunt rezervate pentru volumele de producție necesare.

În celula N7, introduceți formula pentru funcția obiectiv folosind comanda de inserare a funcției SUMPRODUCT:

De asemenea, completăm restricțiile din partea dreaptă.

După aceasta, puteți începe să căutați o soluție. Pentru a rezolva problemele de optimizare în EXCEL, utilizați comanda CĂUTARE SOLUȚIE din meniul SERVICE.

Această comandă operează cu trei componente principale ale modelului optimizat construit în ET:

· O celulă care conține funcția obiectivă a problemei.

· Celulele variabile conţinând variabile independente.

· Celulele care conțin părțile din stânga restricțiilor privind resursele disponibile, precum și restricții simple pe variabile independente.

Să luăm în considerare succesiunea de introducere a acestor componente.

Cursorul se află în celula N7 și comanda SERVICE - Căutați o soluție. Pe ecran va apărea o casetă de dialog.

În fereastră, completați câmpul Setați celula țintă, care ar trebui să conțină adresa $N$7. Apoi, setați butonul pentru a căuta valoarea maximă. În câmpul Modificare celule, introduceți adresele variabilelor dorite $B3:$M3. Apoi ar trebui să introduceți restricții folosind butonul Adăugare.

Acum că au fost setate toate restricțiile pentru găsirea soluției optime, putem apăsa butonul:

După aceasta vom obține o soluție la problemă.

Dacă calculele au avut succes, după finalizarea căutării unei soluții, valorile vor fi inserate în tabel și puteți specifica și Tipul de raport - Rezultate, în urma căruia putem obține următorul raport. lucrător timp echipament profit

În consecință, soluția în EXCEL este aceeași cu metoda SIMPLEX, ceea ce înseamnă că problema luată în considerare a fost rezolvată corect.

Postat pe Allbest.ru

...

Documente similare

    Determinarea volumului optim de ieșire metoda matematica, metoda simplex și folosind Excel. Rezolvarea problemei prin distributie optima investiții folosind aplicate programe Excel. Elaborarea unei scheme optime de transport.

    munca de curs, adăugat la 09.10.2012

    Planificarea profitului în producția a două tipuri de combustibil. Intocmirea unui plan optim de productie pentru a obtine profit maxim din vanzarea acestuia. Determinarea planului de bază de transport de marfă folosind metoda costului minim și folosind Excel.

    test, adaugat 11.12.2014

    Algoritm pentru rezolvarea problemelor de programare liniară folosind metoda simplex. Construirea unui model matematic al unei probleme de programare liniară. Rezolvarea unei probleme de programare liniară în Excel. Găsirea profitului și a planului optim de producție.

    lucrare curs, adaugat 21.03.2012

    Folosind metoda simplex, determinarea unui plan de productie pentru a obtine profit maxim astfel incat materiile prime de tip II sa fie complet consumate. Rezolvarea problemelor de programare liniară folosind o foaie de calcul Excel, crearea unui algoritm.

    lucrare curs, adaugat 30.09.2013

    Studiul modelului matematic si economic al companiei in vederea dezvoltarii unei solutii optime de productie pentru obtinerea de profituri maxime si minimizarea costurilor folosind metode de optimizare si programul MS Excel si pachetul de instrumente Matlab.

    teză, adăugată 15.06.2014

    Revizuirea algoritmilor pentru rezolvarea problemelor de programare liniara. Dezvoltarea algoritmului metoda tabulară simplex. Intocmirea unui plan de productie care sa realizeze profituri maxime din vanzari. Construirea unui model matematic al problemei.

    lucrare curs, adaugat 21.11.2013

    Determinarea numărului și tipului de tractoare și amortizoare auto pe care compania ar trebui să le producă pentru a maximiza profiturile. Rezolvarea problemelor de programare liniară folosind metode grafice și simplex folosind editorul de foi de calcul Excel.

    lucrare de curs, adăugată 04.09.2013

    Optimizarea costurilor pentru livrarea produselor către consumatori. Caracteristică problema de transport, forma generala soluții, generalizare; formularea semnificativă și matematică a problemei, rezolvarea folosind MS Excel: listarea programelor, analiza rezultatelor.

    lucru curs, adăugat 02/04/2011

    Bazele matematice optimizare. Enunțul problemei de optimizare. Metode de optimizare. Rezolvarea problemei folosind metoda simplex clasică. Metoda grafică. Rezolvarea problemelor folosind Excel. Coeficienții funcției obiective. Programare liniară, metodă, probleme.

    rezumat, adăugat 21.08.2008

    Determinarea cantității de materii prime achiziționate pentru producție pe lună, pe tot parcursul anului și pe an în ansamblu. Algoritmul acțiunilor necesare, prezentarea rezultatelor în forma grafica. Rezolvarea problemei sub formă tabelară procesor Excelși folosind instrumente VBA.

Pentru a rezolva probleme de programare liniară metoda simplexîn mediul MS Excel, celulele sunt umplute cu date sursă în modul numere și formule de model matematic.

MS Excel vă permite să obțineți o soluție optimă fără a limita dimensiunea sistemului de inegalități ale funcției obiectiv.

Să rezolvăm problema produselor fabricate folosind metoda simplex utilizând add-in-ul „Solution Search” în MS Excel.

1. Completați Foaie de calcul Excelîn modul număr (Fig. 1)

2. Completați tabelul Excel în modul formulă (Fig. 2)

Fig.1 Tabel în modul număr

Fig.1 Tabel în modul formulă

Aici: B9:C9 – rezultat ( cantitate optima produse de fiecare tip);

В6:С6 – coeficienții funcției obiectiv;

B10 – valoarea funcţiei obiectiv;

В3:С5 – coeficienți de limitare;

D12:D14 – partea dreaptă a restricțiilor;

B12:B14 – valori calculate (reale) din partea stângă a restricțiilor.

Să rezolvăm problema folosind comanda Data/Solution Search. Pe ecran apare caseta de dialog Căutare soluție.

În câmpul Setați funcția țintă, va fi afișată o legătură către celula activă, de exemplu. pe B10. În plus, această legătură este absolută. În secțiunea Egal, setați comutatorul la valoarea maximă (minimă) în funcție de funcția țintă. Restricțiile sunt setate folosind butonul Adăugare, care deschide caseta de dialog de introducere a Adăugare restricții.

În câmpul de intrare Cell Link: indicați adresa celulei care conține formula din partea stângă a constrângerii. Apoi semnul raportului este selectat din listă. Câmpul Restricție specifică adresa celulei care o conține partea dreapta restricții. Faceți clic pe butonul Adăugați și repetați până când următoarea limitare. După ce ați introdus toate restricțiile, faceți clic pe OK.

Deoarece toate variabilele poartă condiții de non-negativitate, pozitivitatea lor este setată prin butonul Parametri din caseta de dialog Căutare soluție. După ce faceți clic pe el, pe ecran apare fereastra Opțiuni de căutare a soluției.

Bifați caseta de selectare Faceți variabilele neconstrânse ca non-negative și selectați Metoda soluției Căutați soluții la probleme liniare folosind metoda simplex. Faceți clic pe butonul Găsiți soluție.

Excel va prezenta o fereastră cu rezultatele căutării soluției cu un mesaj că a fost găsită o soluție sau că nu poate găsi o soluție adecvată.

Dacă calculul a avut succes, Excel va prezenta următoarea fereastră de rezumat. Le puteți păstra sau le puteți arunca. În plus, puteți obține unul dintre trei tipuri rapoarte (rezultate , Durabilitate , Limite) care ne permit să înțelegem mai bine rezultatele obținute, inclusiv evaluarea fiabilității acestora.



După găsirea soluției, numărul optim de produse de fiecare tip va apărea în celulele B9:C9.

Când salvați raportul, selectați – Raport asupra rezultatelor (Fig. 3).

Raportul arată că resursa 1 nu este utilizată pe deplin cu 150 kg, în timp ce resursele 2 și 3 sunt utilizate pe deplin.

Ca urmare, s-a obținut un plan optim în care produsele de tip 1 trebuie produse în cantitate de 58 de bucăți, iar produsele de tip 2 în cantitate de 42 de bucăți. În același timp, profitul din vânzarea lor este maxim și se ridică la 4.660 de mii de ruble.

Fig.3 Raport de rezultate

1. Din stația de formare pleacă zilnic trenuri de pasageri și trenuri rapide compuse din loc rezervat, compartiment și vagoane moi. Numărul de locuri într-un vagon cu locuri rezervate este de 54, într-un vagon cu compartiment – ​​36, într-un vagon moale – 18. Tabelul arată compoziția fiecărui tip de tren și numărul de vagoane disponibile în flotă. tipuri variate. Determinați numărul de trenuri rapide și de călători care trebuie formate zilnic astfel încât numărul de pasageri transportați să fie maxim.



Rezolvarea problemelor de transport

Problemele de transport sunt sarcinile de determinare a planului optim pentru transportul mărfurilor de la punctele de plecare date la punctele de consum date.

b 1 b 2 … b k … b g
a 1 }