| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| - | x 1 | + | x 2 | - | S 1 | + | R 1 | = | 1 | |||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | Sf. membru | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | W - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S 1 | + | S 2 | = | 12 | |||||||||
| - | x 1 | + | S 1 | + | S 3 | = | 3 |
| x 1 | x 2 | S 1 | S 2 | S 3 | Sf. membru | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F - 13 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
Scopul serviciului. Calculator online folosit pentru rezolvarea problemelor de programare liniară P-metodaîn următoarele forme de înregistrare: forma de înregistrare de bază a metodei simplex, sub formă de tabel simplex, în metoda simplex modificată.
Instructiuni pentru rezolvarea problemelor metoda dual simplex. Selectați numărul de variabile și numărul de rânduri (numărul de constrângeri), faceți clic pe Următorul. Soluția rezultată este salvată într-un fișier Word (vezi exemplu de soluție folosind metoda dual simplex).
În același timp, restricții precum x i ≥ 0 nu iei in calcul.Următoarele sunt, de asemenea, utilizate cu acest calculator:
Metodă grafică de rezolvare a ZLP
Rezolvarea problemei transportului
Rezolvarea unui joc de matrice
Folosind serviciul online, puteți determina prețul unui joc matrice (limitele inferioare și superioare), puteți verifica prezența unui punct de șa, puteți găsi o soluție la o strategie mixtă folosind următoarele metode: minimax, metoda simplex, grafică (geometrică). ), metoda lui Brown.
Extremul unei funcții a două variabile
Probleme de programare dinamică
Distribuiți 5 loturi omogene de mărfuri între trei piețe astfel încât să obțineți venituri maxime din vânzarea acestora. Veniturile din vânzări pe fiecare piață G(X) depind de numărul de loturi vândute de produs X și sunt prezentate în tabel.
| Volumul produsului X (în loturi) | Venitul G(X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
În metoda P, planul optim se obține prin deplasarea de-a lungul pseudoplanurilor. Pseudoplan- un plan în care sunt îndeplinite condițiile de optimitate, iar printre valorile variabilelor de bază x i se numără numere negative. Algoritm pentru metoda dual simplex include următorii pași:
- Întocmirea unui pseudo-plan. Sistemul de constrângeri al problemei inițiale conduce la un sistem de inegalități cu sensul „≤”.
- Verificarea optimității planului. Dacă condiția de optimitate nu este satisfăcută în planul de referință rezultat, atunci problema este rezolvată folosind metoda simplex.
- Selectarea rândului și coloanei de început. Dintre valorile negative ale variabilelor de bază, sunt selectate cele mai mari în valoare absolută. Linia corespunzătoare acestei valori este cea din frunte.
- Calculul unui nou plan de referință. Noul plan se obține prin recalcularea tabelului simplex folosind metoda Jordan-Gauss. Apoi, treceți la etapa 2.
Exemplu. Întreprinderea trebuie să producă unități A1, unități A2 și unități A3 conform planului de producție. Fiecare tip de produs poate fi produs pe două mașini.
Cum să distribuiți munca mașinilor astfel încât timpul total petrecut pentru executarea planului să fie minim? Sunt date matricea costurilor și resursele de timp ale fiecărei mașini. Notați modelul operației studiate într-o formă care să permită utilizarea metodei P.
Se știe că conținutul de n nutrienți A, B și C din dietă ar trebui să fie de cel puțin m1, m2, respectiv m3 unități. Trei tipuri de alimente conțin acești nutrienți. Conținutul de unități nutritive într-un kilogram din fiecare tip de produs este prezentat în tabel. Stabiliți o dietă zilnică care să ofere cantitatea necesară de nutrienți la un cost minim.
Sarcină: Rezolvați problema utilizând algoritmul metodei dual simplex.
Să reducem sistemul de restricții la sistemul de inegalități de sens ≤ prin înmulțirea dreptelor corespunzătoare cu (-1).
Să determinăm valoarea minimă a funcției obiectiv F(X) = 4x 1 + 2x 2 + x 3 în următoarele condiții de constrângere.
- x 1 - x 2 ≤-10
2x 1 + x 2 - x 3 ≤8
Pentru a construi primul plan de referință, reducem sistemul de inegalități la un sistem de ecuații prin introducerea de variabile suplimentare (tranziție la forma canonică).
În prima inegalitate de sens (≤), introducem variabila de bază x 4 . În a doua inegalitate de sens (≤), introducem variabila de bază x 5 .
-1x 1 -1x 2 + 0x 3 + 1x 4 + 0x 5 = -10
2x 1 + 1x 2 -1x 3 + 0x 4 + 1x 5 = 8
Matricea de coeficienți A = a(ij) a acestui sistem de ecuații are forma:
| A= |
|
x 4, x 5,
Presupunând că variabilele libere sunt egale cu zero, obținem primul proiect de referință:
X1 = (0,0,0,-10,8)
| Bază | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x 5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
Iterația #1
Planul 0 dintr-un tabel simplex este un pseudo-plan, așa că determinăm rândul și coloana de început.
Linia principală va fi prima linie, iar variabila x 4 ar trebui derivată din bază.
3. Definirea unei noi variabile de bază. Valoarea minimă a lui θ corespunde coloanei a 2-a, adică. variabila x 2 trebuie introdusă în bază.
| Bază | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x 5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
| θ | 0 | -4: (-1) = 4 | -2: (-1) = 2 | - | - | - |
4. Recalcularea tabelului simplex. Efectuăm transformări ale tabelului simplex folosind metoda Jordano-Gauss.
| Bază | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
Să prezentăm calculul fiecărui element sub forma unui tabel:
| B | x 1 | x 2 | x 3 | x 4 | x 5 |
| -10: -1 | -1: -1 | -1: -1 | 0: -1 | 1: -1 | 0: -1 |
| 8-(-10 1):-1 | 2-(-1 1):-1 | 1-(-1 1):-1 | -1-(0 1):-1 | 0-(1 1):-1 | 1-(0 1):-1 |
| 0-(-10 -2):-1 | -4-(-1 -2):-1 | -2-(-1 -2):-1 | -1-(0 -2):-1 | 0-(1 -2):-1 | 0-(0 -2):-1 |
Iterația #2
1. Verificarea criteriului de optimitate.
Planul 1 dintr-un tabel simplex este un pseudo-plan, așa că determinăm rândul și coloana de început.
2. Definirea unei noi variabile libere.
Dintre valorile negative ale variabilelor de bază, o selectăm pe cea mai mare în valoare absolută.
A doua linie va fi lider, iar variabila x 5 ar trebui derivată din bază.
3. Definirea unei noi variabile de bază. Valoarea minimă a lui θ corespunde celei de-a treia coloane, adică. variabila x 3 trebuie introdusă în bază.
La intersecția rândului principal și coloanei există un element de rezoluție (RE) egal cu (-1).
| Bază | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
| θ | 0 | - | - | -1: (-1) = 1 | - | - |
4. Recalcularea tabelului simplex. Efectuăm transformări.
| Bază | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
| B | x 1 | x 2 | x 3 | x 4 | x 5 |
| 10-(-2 0):-1 | 1-(1 0):-1 | 1-(0 0):-1 | 0-(-1 0):-1 | -1-(1 0):-1 | 0-(1 0):-1 |
| -2: -1 | 1: -1 | 0: -1 | -1: -1 | 1: -1 | 1: -1 |
| 20-(-2 -1):-1 | -2-(1 -1):-1 | 0-(0 -1):-1 | -1-(-1 -1):-1 | -2-(1 -1):-1 | 0-(1 -1):-1 |
În coloana de bază, toate elementele sunt pozitive. Să trecem la algoritmul principal al metodei simplex.
Iterația #3
1. Verificarea criteriului de optimitate.
Nu există valori pozitive printre valorile șirului de index. Prin urmare, acest tabel determină planul optim pentru problemă.
| Bază | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
Planul optim poate fi scris astfel: x 1 = 0, x 2 = 10, x 3 = 2
F(X) = 2 10 + 1 2 = 22
Iată o soluție manuală (nu un applet) a două probleme folosind metoda simplex (asemănătoare cu soluția applet) cu explicații detaliate pentru a înțelege algoritmul de rezolvare a problemelor folosind metoda simplex. Prima problemă conține semne de inegalitate doar „≤” (problema cu bază inițială), a doua poate conține semne „≥”, „≤” sau „=” (problema cu bază artificială), acestea sunt rezolvate diferit.
Metoda simplex, rezolvarea unei probleme cu o bază inițială
1)Metoda simplex pentru o problemă cu o bază inițială (toate semnele de constrângeri de inegalitate „ ≤ „).
Să scriem problema în canonic formă, adică rescriem restricțiile inegalității sub formă de egalități, adăugând bilanț variabile:
Acest sistem este un sistem cu o bază (baza s 1, s 2, s 3, fiecare dintre ele este inclusă într-o singură ecuație a sistemului cu un coeficient de 1), x 1 și x 2 sunt variabile libere. Problemele de rezolvat prin metoda simplex trebuie să aibă următoarele două proprietăţi: - sistemul de constrângeri trebuie să fie un sistem de ecuaţii cu bază; -termenii liberi ai tuturor ecuatiilor din sistem trebuie sa fie nenegativi.
Sistemul rezultat este un sistem cu o bază și termenii săi liberi sunt nenegativi, așa că putem aplica metoda simplex. Să creăm primul tabel simplex (Iterația 0) pentru a rezolva problema metoda simplex, adică un tabel de coeficienți ai funcției obiectiv și un sistem de ecuații pentru variabilele corespunzătoare. Aici „BP” înseamnă coloana variabilelor de bază, „Soluție” înseamnă coloana părților din dreapta ale ecuațiilor sistemului. Soluția nu este optimă, pentru că există coeficienți negativi în rândul z.
iterația metodei simplex 0
|
Atitudine |
|||||||
Pentru a îmbunătăți soluția, să trecem la următoarea iterație metoda simplex, obținem următorul tabel simplex. Pentru a face acest lucru, trebuie să selectați activați coloana, adică o variabilă care va fi inclusă în bază la următoarea iterație a metodei simplex. Este selectat de cel mai mare coeficient negativ absolut din rândul z (în problema maximă) - în iterația inițială a metodei simplex aceasta este coloana x 2 (coeficientul -6).
Apoi selectați activați șirul, adică o variabilă care va părăsi baza la următoarea iterație a metodei simplex. Este selectat după cel mai mic raport al coloanei „Decizie” față de elementele pozitive corespunzătoare ale coloanei de rezoluție (coloana „Ratio”) - în iterația inițială acesta este rândul s 3 (coeficientul 20).
Element permisiv se află la intersecția coloanei de rezolvare și a rândului de rezolvare, celula sa este evidențiată în culoare, este egală cu 1. Prin urmare, la următoarea iterație a metodei simplex, variabila x 2 va înlocui s 1 în bază. Rețineți că relația nu este căutată în șirul z este plasată o liniuță „-”. Dacă există relații minime identice, atunci oricare dintre ele este selectată. Dacă toți coeficienții din coloana rezoluției sunt mai mici sau egali cu 0, atunci soluția problemei este infinită.
Să completăm următorul tabel „Iterația 1”. O vom obține din tabelul „Iterație 0”. Scopul transformărilor ulterioare este de a transforma coloana de rezoluție x2 într-o coloană de unitate (cu un unu în loc de elementul de rezoluție și cu zerouri în loc de elementele rămase).
1) Calculați rândul x 2 din tabelul „Iterația 1”. În primul rând, împărțim toți membrii rândului de rezolvare s 3 din tabelul „Iterația 0” la elementul de rezolvare (în acest caz este egal cu 1) din acest tabel, obținem rândul x 2 în tabelul „Iterația 1” . Deoarece elementul de rezolvare în acest caz este egal cu 1, apoi rândul s 3 din tabelul „Iterația 0” va coincide cu rândul x 2 din tabelul „Iterația 1”. Rândul x 2 din tabelul Iterația 1 am obținut 0 1 0 0 1 20, rândurile rămase din tabelul Iterația 1 vor fi obținute din acest rând și rândurile din tabelul Iterația 0 după cum urmează:
2) Calculul rândului z al tabelului „Iterația 1”. În locul lui -6 în primul rând (z-rând) în coloana x2 a tabelului Iterația 0, ar trebui să existe un 0 în primul rând al tabelului Iterația 1. Pentru a face acest lucru, înmulțiți toate elementele rândului x 2 din tabelul „Iterația 1” 0 1 0 0 1 20 cu 6, obținem 0 6 0 0 6 120 și adăugăm acest rând cu primul rând (z - rând) din tabelul „Iterația 0” -4 -6 0 0 0 0, obținem -4 0 0 0 6 120. În coloana x 2 apare un zero 0, scopul este atins. Elementele coloanei de rezoluție x 2 sunt evidențiate cu roșu.
3) Calculul rândului s 1 din tabelul „Iterația 1”. În loc de 1 în s 1 rând al tabelului „Iterația 0” ar trebui să existe un 0 în tabelul „Iterația 1”. Pentru a face acest lucru, înmulțiți toate elementele rândului x 2 din tabelul „Iterația 1” 0 1 0 0 1 20 cu -1, obțineți 0 -1 0 0 -1 -20 și adăugați acest rând cu s 1 - rândul tabelul „Iterația 0” 2 1 1 0 0 64, obținem rândul 2 0 1 0 -1 44. În coloana x 2 obținem 0 necesar.
4) Calculați rândul s 2 din tabelul „Iterația 1”. În locul 3 în rândul s 2 al tabelului „Iterația 0” ar trebui să fie 0 în tabelul „Iterația 1”. Pentru a face acest lucru, înmulțim toate elementele rândului x 2 din tabelul „Iterația 1” 0 1 0 0 1 20 cu -3, obținem 0 -3 0 0 -3 -60 și adăugăm acest rând cu s 1 - rând de tabelul „Iterația 0” 1 3 0 1 0 72, obținem rândul 1 0 0 1 -3 12. În coloana x 2, se obține 0 necesar coloana x 2 din tabelul „Iterația 1”. o unitate, conține unul 1 și restul 0.
Rândurile din tabelul „Iterația 1” se obțin conform următoarei reguli:
Rând nou = Rând vechi – (Coeficient de coloană de rezoluție a rândului vechi)* (Rând de rezoluție nou).
De exemplu, pentru un șir z avem:
Vechi șir z (-4 -6 0 0 0 0) -(-6)*Șir de rezolvare nou -(0 -6 0 0 -6 -120) =Nou z-șir (-4 0 0 0 6 120).
Pentru următoarele tabele, recalcularea elementelor de tabel se face într-un mod similar, așa că o omitem.
Iterația metodei simplex 1
|
Atitudine |
|||||||
Rezolvarea coloanei x 1, rezolvarea rândului s 2, s 2 părăsește baza, x 1 intră în bază. Exact în același mod, obținem tabelele simplex rămase până când obținem un tabel cu toți coeficienții pozitivi în rândul z. Acesta este un semn al unei mese optime.
iterația metodei simplex 2
|
Atitudine |
|||||||
Rezolvând coloana s 3, rezolvând rândul s 1, s 1 părăsește baza, s 3 intră în bază.
Iterația metodei simplex 3
|
Atitudine |
|||||||
În rândul z, toți coeficienții sunt nenegativi, prin urmare, se obține soluția optimă x 1 = 24, x 2 = 16, z max = 192.
Pasul 0. Etapa pregătitoare.
Reducem problema LP la o formă specială (15).
Pasul 1. Compilarea tabel simplex, corespunzătoare formei speciale:
|
|
|
|||||
|
|
|
|
|
|||
|
|
|
|
|
|
||
|
|
|
|
|
|
||
|
|
|
|
|
|
||
Rețineți că acest tabel corespunde unei soluții de bază admisibile 
probleme (15). Valoarea funcției obiectiv pe această soluție 
Pasul 2. Verificarea optimității
Dacă printre elementele rândului index există tabele simplex 
atunci nu există un singur element pozitiv 
, soluția optimă la problema LP se găsește:. Algoritmul se termină.
Pasul 3. Verificarea indecidibilității
Dacă printre 
există un element pozitiv 
, și în coloana corespunzătoare 
nu există un singur element pozitiv 
, apoi funcția obiectiv L este nemărginită de jos pe mulţimea admisibilă. În acest caz, nu există o soluție optimă. Algoritmul se termină.
Pasul 4. Selectarea unei coloane principale q
Printre elemente 
alege elementul pozitiv maxim 
.Declarăm această coloană ca fiind coloana principală (permisivă).
Pasul 5. Selectarea liniei de conducere p
Printre elementele pozitive ale coloanei 
găsiți elementul 
, pentru care egalitatea este valabilă
.
Şir p Declarăm că este lider (permite). Element 
Declarăm că este liderul (permițând).
Pasul 6 Conversie tabel simplex
Creăm un nou tabel simplex în care:
a) în locul variabilei de bază 
scrie 
, în loc de o variabilă nebază 
scrie 
;
b) elementul conducător se înlocuiește cu valoarea inversă 
;
c) toate elementele coloanei principale (cu excepția 
) înmulțit cu 
;
d) toate elementele liniei de conducere (cu excepția 
) înmulțit cu 
;
e) elementele rămase ale tabelului simplex sunt convertite după următoarea schemă „dreptunghi”.
Produsul a trei factori se scade din elementul:
primul este elementul corespunzător al coloanei principale;
al doilea este elementul corespunzător al liniei de conducere;
a treia este reciproca elementului conducător 
.
Elementul transformat și cei trei factori corespunzători acestuia sunt tocmai vârfurile „dreptunghiului”.
Pasul 7 Trecerea la următoarea iterație se realizează prin revenirea la pasul 2.
2.3. Algoritmul metodei simplex pentru problema maximă
Algoritmul metodei simplex pentru problema maximă diferă de algoritmul pentru problema minimă doar în semnele liniei index a coeficienților din funcția obiectiv 
, și anume:
La pasul 2:
:
La pasul 3
. Funcția obiectiv este nemărginită de sus pe mulțimea admisibilă.
La pasul 4:
.
2.4. Un exemplu de rezolvare a unei probleme folosind metoda simplex
Rezolvați problema scrisă sub forma (15).
Să creăm un tabel simplex:
|
|
|
|
|
|
| |||
|
|
|
Deoarece coeficienții dreptei funcției obiectiv sunt nenegativi, soluția de bază inițială nu este optimă. Valoarea funcției obiectiv pentru această bază L=0.
Selectați coloana principală - aceasta este coloana corespunzătoare variabilei 
.
Selectați linia principală. Pentru aceasta găsim 
. Prin urmare, linia de conducere corespunde variabilei 
.
Transformăm tabelul simplex prin introducerea unei variabile 
în bază și scoaterea variabilei 
de la bază. Obținem tabelul:
|
|
|
|
|
|
|
| ||
|
|
|
O iterație a metodei este finalizată. Să trecem la o nouă iterație. Tabelul rezultat nu este optim. Soluția de bază corespunzătoare tabelului are forma . Valoarea funcției obiectiv pe această bază L= -2.
Coloana principală aici este coloana corespunzătoare variabilei 
. Linia principală – linia corespunzătoare variabilei 
. După efectuarea transformărilor, obținem un tabel simplex:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Încă o iterație finalizată. Să trecem la o nouă iterație.
Linia funcției obiectiv nu conține valori pozitive, ceea ce înseamnă că soluția de bază corespunzătoare este optimă, iar algoritmul se termină.
Ața, nasturii și țesătura sunt folosite pentru a face trei tipuri de cămăși. Stocurile de ață, nasturi și țesături, normele de consum ale acestora pentru coaserea unei cămăși sunt indicate în tabel. Găsiți profitul maxim și planul optim de producție a produsului care îl asigură (găsiți).
| cămașă 1 | cămașă 2 | cămașă 3 | Rezerve | fire (m.) | 1 | 9 | 3 | 96 | nasturi (buc.) | 20 | 10 | 30 | 640 | textil ( | 1 | 2 | 2 | 44 | Profit (r.) | 2 | 5 | 4 |
Rezolvarea problemei
Construirea modelului
Prin și numărul de cămăși de tipul 1, 2 și 3 destinate lansării.
Apoi restricțiile de resurse vor arăta astfel:
Mai mult, conform sensului sarcinii
Funcția obiectivă care exprimă profitul primit:
Obținem următoarea problemă de programare liniară:
Reducerea unei probleme de programare liniară la formă canonică
Să reducem problema la formă canonică. Să introducem variabile suplimentare. Introducem toate variabilele suplimentare în funcția obiectiv cu un coeficient egal cu zero. Adăugăm variabile suplimentare în partea stângă a restricțiilor care nu au o formă preferată și obținem egalități.
Rezolvarea problemei folosind metoda simplex
Completați tabelul simplex:
Întrucât rezolvăm problema la maximum, prezența numerelor negative în linia index atunci când rezolvăm problema la maximum indică faptul că nu am obținut soluția optimă și că este necesar să trecem de la tabelul celei de-a 0-a iterații. la următorul.
Trecem la următoarea iterație după cum urmează:
coloana principală corespunde
Rândul cheie este determinat de raportul minim dintre termenii liberi și membrii coloanei principale (relații simple):
La intersecția coloanei de chei și a rândului de chei găsim elementul de activare, i.e. 9.
Acum trecem la compilarea primei iterații: În loc de un vector unitar, introducem vectorul .
În noul tabel, în locul elementului de activare scriem 1, toate celelalte elemente ale coloanei cheie sunt zerouri. Elementele șirului cheie sunt împărțite în elementul de activare. Toate celelalte elemente ale tabelului sunt calculate folosind regula dreptunghiului.
Coloana cheie pentru prima iterație îi corespunde
Elementul de rezolvare este numărul 4/3. Deducem vectorul de la bază și introducem în schimb vectorul. Obținem tabelul celei de-a 2-a iterații.
Coloana cheie pentru a 2-a iterație îi corespunde
Găsim linia cheie, pentru aceasta definim:
Elementul de rezolvare este numărul 10/3. Deducem vectorul de la bază și introducem în schimb vectorul. Obținem tabelul celei de-a 3-a iterații.
| № | BP | c B | A o | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | Simplex | 2 | 5 | 4 | 0 | 0 | 0 | relaţie | 0 | x 4 | 0 | 96 | 1 | 9 | 3 | 1 | 0 | 0 | 32/3 | x 5 | 0 | 640 | 20 | 10 | 30 | 0 | 1 | 0 | 64 | x 6 | 0 | 44 | 1 | 2 | 2 | 0 | 0 | 1 | 22 | F j - c j | 0 | -2 | -5 | -4 | 0 | 0 | 0 | 1 | x 2 | 5 | 32/3 | 1/9 | 1 | 1/3 | 1/9 | 0 | 0 | 32 | x 5 | 0 | 1600/3 | 170/9 | 0 | 80/3 | -10/9 | 1 | 0 | 20 | x 6 | 0 | 68/3 | 7/9 | 0 | 4/3 | -2/9 | 0 | 1 | 17 | F j - c j | 160/3 | -13/9 | 0 | -7/3 | 5/9 | 0 | 0 | 2 | x 2 | 5 | 5 | -1/12 | 1 | 0 | 1/6 | 0 | -1/4 | -- | x 5 | 0 | 80 | 10/3 | 0 | 0 | 10/3 | 1 | -20 | 24 | x 3 | 4 | 17 | 7/12 | 0 | 1 | -1/6 | 0 | 3/4 | 204/7 | F j - c j | 93 | -1/12 | 0 | 0 | 1/6 | 0 | 7/4 | 3 | x 2 | 5 | 7 | 0 | 1 | 0 | 1/4 | 1/40 | -3/4 | x 1 | 2 | 24 | 1 | 0 | 0 | 1 | 3/10 | -6 | x 3 | 4 | 3 | 0 | 0 | 1 | -3/4 | -7/40 | 17/4 | F j - c j | 95 | 0 | 0 | 0 | 1/4 | 1/40 | 5/4 |
În rândul index, toți termenii sunt nenegativi, deci se obține următoarea soluție la problema de programare liniară (o scriem din coloana de termeni liberi):
Este necesar să coaseți 24 de cămăși de tipul 1, 7 cămăși de tipul 2 și 3 cămăși de tipul 3. În acest caz, profitul primit va fi maxim și se va ridica la 95 de ruble.
Puteți găsi ajutor pentru a vă rezolva problemele pe acest subiect trimițând un mesaj pe VKontakte, Viber sau completând formularul. Costul rezolvării temelor începe de la 7 BYR. per sarcină (200 de ruble rusești), dar nu mai puțin de 10 ruble din Belarus. (300 RUB) pentru întreaga comandă. Design detaliat. Costul asistenței pentru examen online (în acest caz, este necesară plata în avans 100%) este de la 30 BYR. (1000 de ruble rusești) pentru rezolvarea biletului.
