Come risolvere problemi di programmazione lineare Utilizzando Simplex

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 < = 10

3x + y < ; = 5

x + 2y < = 8

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 .