Programmazione lineare è un metodo matematico utilizzato per calcolare la quantità di input diversi per ottimizzare alcuni output dato un insieme di vincoli di funzionamento necessaria. Attività associate a problemi di programmazione lineare includono identificare le variabili, i vincoli identificati e massimizzando l'output desiderato. Programmazione lineare è una tecnica versatile che è usata in industria, agricoltura, raffinazione del petrolio, pianificazione finanziaria e logistica.
Un esempio di programmazione lineare
L'esempio utilizzato in questo articolo è come segue. Il produttore di widget produce due tipi di widget: tipo A e tipo b. Il processo di fabbricazione per entrambi i widget ha due fasi. Esigenze di widget A due ore di lavorazione in passo uno e un'ora di elaborazione in fase due. Widget B ha bisogno di un'ora di elaborazione nel passaggio uno e tre ore di elaborazione in fase due. L'azienda di widget ha 40 operaio-ore di manodopera disponibile per passo uno e 60 operaio-ore disponibili per la fase due. L'azienda fa profitto di $20 su ogni widget A e 15 dollari ogni widget B. Per massimizzare il profitto dovrebbe essere prodotto quale numero di ogni widget? Che cosa è questo massimo profitto?
Verifica il problema è risolvibile
Un problema deve avere le seguenti proprietà per essere risolvibile usando programmazione lineare. Tutte le variabili devono essere continue. Ciò significa che possono essere espressi come frazioni, piuttosto che soli numeri interi. Ci deve essere un unico obiettivo di essere ingrandita o ridotta a icona e i vincoli e l'obiettivo deve essere lineare. Ciò significa che i termini devono essere un singolo valore o un singolo valore moltiplicato per un valore sconosciuto. Nell'esempio, ore e profitto sono entrambi di continuo. Il "numero di widget" è un numero intero, tuttavia può essere presupposto per essere continuo durante il problema e poi arrotondato al numero intero più vicino alla fine. L'obiettivo di essere ingrandita è il profitto. I vincoli sono valori single. Ciò significa che il problema è risolvibile.
Identificare le variabili
Le variabili del problema sono le cose che possiamo scegliere di modificare al fine di massimizzare l'output. Nell'esempio, queste cose sono il numero di widget come e il numero di widget Bs rende l'azienda manifatturiera. Questi sono indicata con A e B rispettivamente.
Identificare i vincoli
I vincoli sono le cose date il problema che non può essere modificato. In tutti i problemi di programmazione lineare il numero di ciascuna delle variabili deve essere impostato a maggiore o uguale a zero:
A > = 0
B > = 0
Questo è perché è impossibile per la fabbricazione di un importo negativo di qualcosa. Nell'esempio, gli altri vincoli sono il numero di operaio-ore a disposizione per lavorare su tutti i passaggi e il numero di operaio-ore richiesto per ogni passaggio per ogni widget. Questi può essere espresso in due equazioni:
2A + B < = 40
A + 3B < = 60
Trovare la funzione di profitto
La funzione di profitto produce il profitto per un dato numero di A e b. Può essere scritta come:
f(A,B) = 20A + 15B
È importante riconoscere che la funzione di profitto non produce il massimo profitto in proprio. Produrrà il profitto per ogni combinazione di A e B, indipendentemente se tale combinazione è possibile o ottimizza il profitto.
Trovare la soluzione
In problemi di programmazione lineare con solo due variabili è possibile risolvere il problema disegnando un grafico bidimensionale dove i due assi del grafico corrispondono alle due variabili. Se ci sono più di due variabili, che il problema deve essere risolto matematicamente. Nell'esempio, la soluzione si trova matematicamente come segue. Perché il profitto deve essere ingrandita, la soluzione deve trovarsi al bordo estremo di ciò che è possibile. Ciò significa che i vincoli identificati possono essere espresso come un insieme di equazioni simultanee:
2A + B = 40
A + 3B = 60
Risolvere questo set di equazioni simultanee dà una = 12 e B = 16. Ciò significa che se l'azienda effettua 12 widget di tipo A e 16 widget di tipo B il profitto sarà massimizzato. Sostituzione di questi valori la funzione di profitto dà:
f(12,16) = 20(12) + 15(16)
f(12,16) = 480
Ciò significa che il profitto massimo è di $480.