Per capire la maggior quantità di denaro che si potrebbe fare soggetta ad alcuni vincoli , è possibile utilizzare il metodo simplex . Originariamente scoperto da un ingegnere Air Force , George B. Dantzig , nel 1947 , il metodo simplex è un metodo di programmazione lineare che massimizza ( o minimizza ) una funzione soggetta a vincoli in forma di uguaglianze lineari . Geometricamente , le disuguaglianze formano una regione poligonale . Il metodo simplex tenta tutti i vertici di questa regione finché non trova quella che fa la funzione assume il massimo valore . Istruzioni
1
Determinare se il problema è un problema di massimizzazione standard. In questi tipi di problemi , le seguenti condizioni devono essere soddisfatte : La funzione deve essere massimizzata , costante delle disuguaglianze devono essere tutti non negativo , le variabili devono essere tutti non negativo e le disuguaglianze devono tutte essere minore o uguale a . Ad esempio , il seguente è un problema di massimizzazione norma :
Massimizza F = 5x + 6y soggetta ai vincoli
4x + 2y
3x + y
x + 2y
dove x e y sono entrambi non negativo
2
Convertire ogni disuguaglianza in una parità con l’aggiunta . una variabile di gioco per ogni disuguaglianza. Ad esempio , dopo l’aggiunta di variabili lenti , le disuguaglianze diventano :
4x + 2y + u = 10
3x + y + v = 5
x + 2y + w = 8
3
Assicurarsi che tutte le equazioni , compresa la funzione , sono le variabili sul lato sinistro e le costanti a destra. Per esempio , nell’esempio tutte le equazioni già hanno la forma giusta eccezione della funzione . Riscrivere la funzione come indicato :
– 5x – 6y + F = 0
4
Convertire il sistema di equazioni in una matrice chiamata simplex tableau iniziale. Ogni riga della matrice corrisponde ai coefficienti delle equazioni . Mettere i numeri della funzione nella riga inferiore . Ad esempio , il tableau simplex iniziale dell’esempio è :
xyuvw F
4 2 1 0 0 0 10
3 1 0 1 0 0 5
1 2 0 0 1 0 8
-5 -6 0 0 0 -1 0
5
Trova l’indicatore più negativo nel tableau simplex iniziale. Gli “indicatori ” sono i numeri nella parte inferiore ( tranne per il più in basso numero ) . Nell’esempio , l’indicatore più negativa è -6 nella seconda colonna . Questa colonna viene chiamato colonna pivot.
6
Trovare il più piccolo rapporto nella colonna pivot. Rapporti Form prendendo più a destra numero in ogni riga e dividendolo per un numero corrispondente nella colonna pivot . Fate questo per ogni riga tranne la riga dell’indicatore. Per esempio , i rapporti nell’esempio sono :
10/2 = 5
5/1 = 5
8/2 = 4
minimo rapporto sulla colonna perno è 4 , che corrisponde alla terza fila .
7
Utilizza operazioni di riga della matrice di modificare tutti gli altri numeri nella colonna perno a 0 . ad esempio , sottrarre la prima riga dalla riga perno per formare uno 0 nella prima riga . Sottrarre due volte la seconda riga dalla riga perno per formare uno 0 nella seconda fila . Il risultato è il seguente:
xyuvw F
3 0 1 0 -1 0 2
5 0 0 2 0 2 -1
1 2 0 0 1 0 8
-8 0 0 0 -3 -1 -24
8
Controllare che tutti gli indicatori sono non negativi . Se è così, allora si è fatto. In caso contrario , passare al punto 5 .
9
Leggere la soluzione dalla matrice finale . Ad esempio , se la matrice finale è
xyuvw F
1 0 0 3 4 0 4
0 3 0 4 4 0 6
0 0 2 4 3 0 4
0 0 0 3 3 1 5
cercano le colonne con un unico numero diverso da zero . Questa colonna si dà il valore di tale variabile nella soluzione . Per trovare il valore , dividere il più a destra il numero per il numero diverso da zero . In questa matrice finale , la soluzione è :
x = 4/1 o 4
y = 6/3 o 2
u = 4/2 o 2
e il valore massimo della funzione F è 5 .