Metoda dublă simplex se bazează pe teoria dualității (a se vedea. Soluția problemei duală) și este folosit pentru a rezolva problemele de programare liniară, membrii liberi sunt bi pot lua orice valoare, iar sistemul de constrângeri definite de inegalitățile sens „≤“, „≥“ sau egalitate „=“.
Instrucțiuni pentru rezolvarea problemelor printr-o metodă dual simplă. Selectați numărul de variabile și numărul de rânduri (numărul de restricții), faceți clic pe Următorul. Soluția rezultată este salvată într-un fișier Word (a se vedea soluția de exemplu cu o metodă dual simplă). Cu toate acestea, restricțiile de tipul xi ≥ 0 nu sunt luate în considerare.
Împreună cu acest calculator sunt utilizate și următoarele:
Matrix Game Solution
Cu ajutorul unui serviciu on-line, puteți determina prețul unui joc de matrice (inferior și limitele superioare), verificați punctul de șa, pentru a găsi o soluție metode mixte de strategie: Minimax, metoda simplex, metoda grafică (geometrică), metoda lui Brown.
Funcții dinamice de programare
Distribuiți 5 loturi omogene de bunuri între cele trei piețe, astfel încât să obțineți venitul maxim din vânzarea lor. Venitul din vânzarea pe fiecare piață G (X) depinde de numărul de loturi realizate de mărfuri X și este prezentat în tabel.
Volumul mărfurilor X (în loturi)
În metoda P, planul optim este obținut ca rezultat al deplasării de-a lungul pseudoprogramelor. Un pseudoplan este un plan în care sunt îndeplinite condițiile de optimitate, iar printre valorile variabilelor de bază xi există numere negative. Algoritmul metodei dual simplex include următorii pași:- Compune un pseudoplan. Sistemul de constrângeri al problemei originale conduce la sistemul de inegalitate a sensului "# 8804".
- Verificarea planului de optimitate. Dacă condiția de optimitate nu este satisfăcută în planul de suport obținut, atunci problema este rezolvată prin metoda simplex.
- Selectați rândul și coloana principală. Printre valorile negative ale variabilelor de bază, cele mai mari sunt alese în valoare absolută. Șirul care corespunde acestei valori este linia de vârf.
- Calcularea unui nou plan de referință. Un nou plan este obținut ca rezultat al conversiei tabelului simplex prin metoda Jordan-Gauss. Apoi treceți la pasul 2.
Un exemplu. Întreprinderea trebuie să elibereze, în conformitate cu planul de producție unități A1, unități A2, unități A3. Fiecare tip de produs poate fi produs pe două mașini.
Cum să alocați munca mașinilor astfel încât timpul total petrecut pe plan să fie minim? Sunt date matricea costurilor și resursele de timp ale fiecărei mașini. Înregistrați modelul operației investigate într-o formă care permite utilizarea metodei P.
Sarcină. Rezolva problema utilizând algoritmul metodei simplex simple.
Oferim un sistem de restricții la sistemul de inegalități al sensului ≤ prin înmulțirea rândurilor corespunzătoare cu (-1).
Definim valoarea minimă a funcției obiectiv F (X) = 4x1 + 2x2 + x3 în următoarele condiții de constrângere.
- x1 - x2 ≤ -10
2x1 + x2 - x3 ≤8
Pentru a construi primul plan de suport, introducem sistemul de inegalități în sistemul de ecuații prin introducerea unor variabile suplimentare (trecerea la forma canonică).
În prima inegalitate a sensului (≤) se introduce variabila de bază x4. În a doua inegalitate a sensului (≤) se introduce variabila de bază x5.
-1x1 -1x2 + 0x3 + 1x4 + 0x5 = -10
2x1 + 1x2 -1x3 + 0x4 + 1x5 = 8
Matricea coeficienților A = a (ij) al acestui sistem de ecuații are forma:
Rezolvăm sistemul de ecuații cu privire la variabilele de bază:
x4. x5,
Presupunând că variabilele libere sunt zero, obținem primul plan de suport:
X1 = (0,0,0, -10,8)
Iterația # 1
1. Verificarea criteriului de optimitate.
Planul 0 în tabelul simplex este un pseudoplan, deci definiți rândul și coloana de conducere.
2. Definirea unei noi variabile libere.
Printre valorile negative ale variabilelor de bază, alegem cel mai mare modul.
Prima linie va fi lider, iar variabila x4 ar trebui să fie derivată din bază.
3. Definirea unei noi variabile de bază. Valoarea minimă # 952; corespunde coloanei 2, adică Variabila x2 trebuie introdusă în bază.
La intersecția rândului și coloanei de conducere este elementul de rezolvare (RE), egal cu (-1).
4. Conversia tabelului simplex. Realizăm transformările tabelului simplex prin metoda Jordan-Gauss.
Să reprezentăm calculul fiecărui element sub forma unui tabel:
Iterația nr. 2
1. Verificarea criteriului de optimitate.
Planul 1 în tabelul simplex este un pseudoplan, deci definiți rândul și coloana de conducere.
2. Definirea unei noi variabile libere.
Printre valorile negative ale variabilelor de bază, alegem cel mai mare modul.
Liderul va fi al doilea rând, iar variabila x5 ar trebui să fie derivată din baza.
3. Definirea unei noi variabile de bază. Valoarea minimă # 952; corespunde coloanei a treia; Variabila x3 trebuie introdusă în bază.
La intersecția rândului și coloanei de conducere este elementul de rezolvare (RE), egal cu (-1).
4. Conversia tabelului simplex. Efectuați transformarea.
Sau mai multe detalii:
În coloana de bază, toate elementele sunt pozitive. Acum ne întoarcem la algoritmul de bază al metodei simplex.
Iterația # 3
1. Verificarea criteriului de optimitate.
Printre valorile liniei de index nu există nici o valoare pozitivă. Prin urmare, acest tabel determină planul de sarcini optim.
Planul optim poate fi scris ca: x1 = 0, x2 = 10, x3 = 2
F (X) = 2 • 10 + 1 • 2 = 22
Regulile de introducere a datelor
Adresați-vă întrebările sau lăsați-vă dorințele sau comentariile în partea de jos a paginii în secțiunea Disqus.
De asemenea, puteți lăsa o solicitare de ajutor în rezolvarea problemelor cu partenerii noștri de încredere (aici sau aici).
Articole similare
Trimiteți-le prietenilor: