Programmazione lineare a cosa serve, modelli, restrizioni, applicazioni

IL programmazione lineare È un metodo matematico che serve a ottimizzare (massimizzare o minimizzare come richiesto) una funzione le cui variabili sono soggette a restrizioni, a condizione che la funzione e le restrizioni dipendano linearmente dalle variabili.

Generalmente la funzione per ottimizzare una situazione pratica, come il guadagno di un produttore i cui input, lavoro o macchinari sono limitati.

Figura 1. La programmazione lineare è ampiamente utilizzata per ottimizzare i profitti. Fonte: piqsels.

Uno dei casi più semplici è quello di una funzione lineare da massimizzare, che dipende solo da due variabili, chiamate Variabili decisionali. Può essere forma:

Z = k₁x + k₂E

Con k₁ e k₂ costanti. Questa funzione è nota come Funzione obiettivo. Naturalmente ci sono situazioni che meritano più di due variabili per il loro studio, essendo più complessi:

Z = k₁X₁ + K₂X₂ + K₃X₃ +.. .

E le restrizioni sono anche matematicamente modellate attraverso un sistema di equazioni o disquazioni, ugualmente lineari in X E E.

L'insieme di soluzioni di questo sistema è chiamato soluzioni fattibili O punti fattibili. E tra i punti fattibili ce n'è almeno uno, che ottimizza la funzione obiettivo.

La programmazione lineare è stata sviluppata indipendentemente dal fisico e matematico americano.

Il metodo di risoluzione dei problemi noto come Metodo simplex È la creazione di Dantzig, che ha lavorato per la US Air Force, l'Università di Berkeley e la Stanford University.

figura 2. I matematici George Dantzig (a sinistra) e Leonid Kantorovich (a destra). Fonte: f. Zapata.

[TOC]

Modelli di programmazione lineare

Gli elementi necessari per stabilire un modello di programmazione lineare, appropriato per una situazione pratica, sono:

-Funzione obiettivo

-Variabili decisionali

-Restrizioni

Nella funzione obiettiva, ciò che si desidera ottenere è definito. Ad esempio, supponiamo che si desideri massimizzare i profitti ottenuti dalla produzione di determinati prodotti. Quindi viene stabilita la funzione "profitto", secondo il prezzo al quale vengono venduti i prodotti.

In termini matematici, questa funzione può essere espressa abbreviata usando la somma:

Z = ∑k_Yo X_Yo

In questa equazione, k_Yo Sono coefficienti e x_Yo sono le variabili di decisione.

Le variabili decisionali sono gli elementi del sistema il cui controllo è e i loro valori sono numeri reali positivi. Nell'esempio proposto, le variabili di decisione sono la quantità di ciascun prodotto da fabbricare per ottenere il guadagno massimo.

Infine, abbiamo le restrizioni, che sono equazioni lineari o disuguaglianze in termini di variabili di decisione. Descrivono i limiti al problema, che sono noti e possono essere ad esempio le quantità di materie prime disponibili nella produzione.

Può servirti: funzioni superiori a due (esempi)

Tipi di restrizioni

Puoi avere un importo m di limitazioni, a partire da J = 1 Fino a J = m. Matematicamente le restrizioni sono di tre tipi:

1. A_J = ∑ a_ij . X_Yo
2. B_J ≥ ∑ b_ij . X_Yo
3. C_J ≤ ∑ c_ij . X_Yo

La prima restrizione è di tipo di equazione lineare e significa che il valore a_J, che è noto, deve essere rispettato.

Le restanti due restrizioni sono disquazioni lineari e significa che i valori B_J e C_J, noto, può essere rispettato o superato, quando il simbolo che appare è ≥ (maggiore o uguale a) o rispetto o meno, se il simbolo è ≤ (meno o uguale a).

Esempio di modello

I campi di applicazione sono molto diversi, che coprono dall'amministrazione aziendale alla nutrizione, ma per comprendere il metodo, viene quindi proposto un semplice modello di una situazione pratica con due variabili.

Una pasticceria locale è conosciuta per due specialità: la torta della giungla nera e la torta di sacresta.

Nella sua elaborazione richiedono uova e zucchero. Per la giungla nera, sono necessarie 9 uova e 500 g di zucchero, mentre sono necessari 8 uova e 800 g di zucchero. I rispettivi prezzi di vendita sono $ 8 e 10.

Il problema è: quante torte di ogni tipo dovrebbero fare la pasticceria per massimizzare il suo guadagno, sapendo che ha 10 chili di zucchero e 144 uova?

Variabili decisionali

Le variabili di decisione sono "x" e "y", che richiedono valori reali:

-X: la quantità di torte nella giungla nera

-Y: torte di tipo sacrifantino.

Restrizioni

Le restrizioni sono fornite dal fatto che il numero di torte è un importo positivo e ci sono quantità limitate di materie prime per prepararle.

Pertanto, in modo matematico, queste restrizioni acquisiscono la forma:

1. x ≥ 0
2. e ≥0
3. 9x +8y ≤ 144
4. 0.5 x + 0.8 e ≤ 10

Le restrizioni 1 e 2 costituiscono il Condizione di non negatività precedentemente esposto e tutte le disquazioni sollevate sono lineari. Nelle restrizioni 3 e 4 sono i valori che non dovrebbero essere superati: 144 uova e 10 kg di zucchero.

Funzione obiettivo

Infine, la funzione obiettivo è il guadagno ottenuto producendo "x" quantità di torte nella giungla nera più quantità di "y" di sacristinine. È costruito un prezzo multiplicatore per quantità di torte realizzate e aggiunte per ogni tipo. È una funzione lineare che chiameremo G (x, y):

G = 8x + 10y

Metodi di soluzione

Tra le varie metodologie di soluzione ci sono i metodi grafici, l'algoritmo simplex e il metodo del punto interno, per menzionarne alcuni.

- Metodo grafico o geometrico

Quando hai un problema di due variabili come la sezione precedente, le restrizioni determinano una regione poligonale nel piano XY, chiamata regione fattibile O Regione di vitalità.

Figura 3. La regione fattibile, in cui si trova la soluzione del problema di ottimizzazione. Fonte: Wikimedia Commons.

Questa regione è costruita attraverso Linee di restrizione, che sono le linee ottenute dalle disquazioni delle restrizioni, lavorando solo con il segno dell'uguaglianza.

Può servirti: set finito: proprietà, esempi, esercizi risolti

Nel caso della panetteria che desidera ottimizzare i profitti, le linee di restrizione sono:

1. x = 0
2. y = 0
3. 9x +8y = 144
4. 0.5 x + 0.8y = 10

Tutti i punti della regione bloccati da queste linee sono possibili soluzioni, quindi ce ne sono infinite. Tranne nel caso in cui la regione fattibile è vuota, nel qual caso il problema sollevato manca di una soluzione.

Fortunatamente, per il problema della pasticceria la regione fattibile non è vuota, lo abbiamo sotto.

Figura 4. La regione fattibile del problema della pasta. La linea retta 0 attraversa l'origine. Fonte: f. Zapata con geogebra.

La soluzione ottimale, se esiste, è con l'aiuto della funzione oggettiva. Ad esempio, quando si tratta di trovare il massimo guadagno G, hai la seguente riga, che si chiama Iso-Benefice Straight:

G = k₁x + k₂e → y = -k₁x / k₂ + G/ k₂

Con questa linea sono ottenute tutte le coppie (x, y) che forniscono un dato guadagno g, quindi c'è una famiglia di linee in base al valore di G, ma tutte con la stessa pendenza -k₁ / K₂, in modo che siano dritti paralleli.

La soluzione ottimale

Ora, si può dimostrare che la soluzione ottimale di un problema lineare è sempre un estremo o un vertice della regione fattibile. COSÌ:

La soluzione di linea è la più lontana dall'origine e che ha almeno un punto in comune con la regione fattibile.

Se la linea più vicina all'origine ha un intero segmento in comune con la regione fattibile, si dice che ci siano soluzioni infinite. Questo caso si verifica se la pendenza della linea Iso-Benefits è uguale a quella di una qualsiasi delle altre linee che limitano la regione.

Per la nostra pasticceria, i vertici candidati sono A, B e C.

- Metodo simplex di dantzig

Il metodo grafico o geometrico è applicabile per due variabili. Tuttavia, è più complicato quando ci sono tre variabili e impossibile da usare per un numero maggiore di variabili.

Quando si tratta di problemi di più di due variabili, il Metodo simplex, che consiste in una serie di algoritmi per ottimizzare le funzioni oggettive. Le matrici semplici e l'aritmetica vengono generalmente utilizzate per eseguire i calcoli.

Il metodo simplex inizia scegliendo una soluzione fattibile e il controllo se è ottimale. Se è già risolto il problema, ma se non lo è, continua verso una soluzione più vicina all'ottimizzazione. Se esiste la soluzione, l'algoritmo con essa in alcuni tentativi.

Può servirti: qual è la gamma statistica? (Con esempi)

Applicazioni

Programmazione lineare e non lineare applicata in molti campi per prendere le migliori decisioni per ridurre i costi e aumentare i profitti, che non sono sempre monetari, poiché possono essere misurati in tempo, ad esempio, se si cerca di ridurre al minimo il tempo necessario per eseguire una serie di operazioni.

Ecco alcuni campi:

-Nel marketing viene utilizzato per trovare la migliore combinazione di media (social network, televisione, stampa e altri) per pubblicizzare un determinato prodotto.

-Per l'assegnazione del lavoro adeguato al personale di una società o fabbrica o programmi.

-Nella selezione degli alimenti più nutrienti e al costo più basso nelle industrie di bestiame e pollame.

Esercizi risolti

- Esercizio 1

Grafico il modello di programmazione lineare sollevato nelle sezioni precedenti.

Soluzione

È necessario gracciare graficamente l'insieme di valori determinati dal sistema di restrizioni specificate nel problema:

1. x ≥ 0
2. e ≥0
3. 9x +8y ≤ 144
4. 0.5 x + 0.8 e ≤ 10

La regione fornita dalle INEGAZIONI 1 e 2 corrisponde al primo quadrante del piano cartesiano. Per quanto riguarda le disquazioni 3 e 4, inizia trovando le linee di restrizione:

9x +8y = 144

0.5 x + 0.8y = 10 → 5x + 8y = 100

La regione fattibile è un quadrilatero i cui vertici sono punti A, B, C e D.

Il guadagno minimo è 0, quindi la linea 8x + 10 e 10 è il limite inferiore e le linee ISO -Benefit hanno in sospeso -8/10 = -0.8.

Questo valore è diverso dalle pendici delle altre linee di restrizione e poiché la regione fattibile è limitata, esiste la soluzione unica.

Figura 5. Soluzione grafica dell'esercizio 1, che mostra la regione fattibile e la soluzione punto C in uno dei vertici di detto regione. Fonte: f. Zapata.

Questa soluzione corrisponde a una linea di pendenza -0.8 che attraversa uno dei punti A, B o C, le cui coordinate sono:

A (11; 5.625)

B (0; 12.5)

C (16, 0)

Soluzione ottimale

Calcoliamo il valore di G per ciascuno di questi punti:

-(11; 5.625): G_A = 8 x 11 + 10 x 5.625 = 144.25

-(0; 12.5): G_B = 8 x 0 + 10 x 12.5 = 125

-(16, 0): G_C = 8 x 16 + 10 x 0 = 128

Il guadagno più grande è produrre 11 torte nere nella giungla e 5.625 Torte sacripantine. Questa soluzione concorda con quella trovata attraverso il software.

- Esercizio 2

Verifica il risultato dell'esercizio precedente utilizzando la funzione Solver (Solister) disponibile nella maggior parte dei fogli di calcolo come Excel o Calc de Libreoffice, che incorpora l'algoritmo simplex per l'ottimizzazione della programmazione lineare.

Soluzione

Figura 6. Dettaglio della soluzione dell'esercizio 1 attraverso il foglio di calcolo Calc Office libero. Fonte: f. Zapata. Figura 7. Dettaglio della soluzione dell'esercizio 1 attraverso il foglio di calcolo Calc Office libero. Fonte: f. Zapata.

Riferimenti

1. Brillante. Programmazione lineare. Recuperato da: brillante.org.
2. Eppen, g. 2000. Ricerca operativa in scienze amministrative. 5 °. Edizione. Prentice Hall.
3. Haeussler, e. 1992. Matematica per l'amministrazione ed economia. 2 °. Edizione. Gruppo editoriale ibero -merican.
4. Hiru.EUS. Programmazione lineare. Recuperato da: Hiru.EUS.
5. Wikipedia. Programmazione lineare. Recuperato da: è. Wikipedia.org.