Guida alla programmazione lineare

tramite: O2O
Difficoltà: difficile
17

Introduzione

La programmazione lineare è una particolare disciplina sviluppata negli anni ‘40 da George B. Dantzig e John von Neumann. Tale disciplina, inizialmente, venne motivata dalla necessità di risolvere problemi complessi di pianificazione nelle operazioni di guerra. La programmazione lineare tratta lo studio e l'applicazione di tecniche di calcolo o algoritmi specificamente indirizzati alla risoluzione di un problema di ottimizzazione, in cui una funzione lineare soggetta a dati limiti lineari viene massimizzata o minimizzata. Vediamo insieme una guida alla programmazione lineare.

27

Occorrente

  • Carta e penna
  • Un buon libro di matematica (scuola secondaria o universitaria)
  • Formulario
37

Il metodo grafico per la programmazione lineare

Il metodo grafico di risoluzione dei problema di programmazione lineare con 2 incognite viene così descritto. Per prima cosa, rappresentate graficamente la regione ammissibile. Fatto ciò, determinate le coordinate dei vertici frontiera e sostituite le coordinate con la funzione obiettivo. Rilevate quale di esse dà il valore ottimale. Se il risultato presenta una regione ammissibile non delimitata, questo metodo può risultare fuorviante. Nel caso di regione ammissibile delimitata esistono sempre soluzioni ottimali, ma potrebbero esistere o meno quando non lo è. Minimizzate C = 3x + 4y soggetto ai vincoli: 3x - 4y ≤ 12; x + 2y ≥ 4; x ≥ 1, y ≥ 0. In questo caso la soluzione è x = 1, y = 1.5, valore minimo dato C = 9. Un problema di massimizzazione standard con n incognite è un problema in cui occorre massimizzare (non minimizzare) la funzione obiettivo soggetta a vincoli di forma: x≥ 0, y≥ 0, z≥ 0, . . ., ed ulteriori vincoli: Ax + By + Cz + . .. ≤ N; laddove A, B, C, . .. Ed N sono numeri con N non negativo. Notate che la disequazione in questo caso dev’essere "≤," e non "=" o "≥". Per risolvere un problema di massimizzazione standard con il metodo simplesso occorre passare da vertice a vertice lungo il confine del poliedro ammissibile. È necessario incrementare ripetutamente la funzione obiettivo fino a trovare una soluzione ottimale. In alternativa, si stabilisce che essa non esiste. Vediamo come procedere. Convertite ad un sistema di equazioni introducendo variabili slack per trasformare i vincoli in equazioni. Riscrivete la funzione obiettivo in forma standard e tracciate il tableau (o matrice) iniziale. Selezionate la colonna pivot: scegliete il numero negativo con la magnitudine più grande nella fila inferiore (escludendo l’entrata all’estrema destra). La sua colonna è quella pivot.

47

La continuazione del metodo grafico

Proseguiamo con la guida sulla programmazione lineare. Dopo aver selezionato la colonna pivot e scelto il numero negativo, se dovessero esserci 2 candidati, sceglietene uno qualsiasi. Se tutti i numeri nella fila inferiore sono zero o positivi, allora la soluzione base massimizza la funzione oggettiva. Ora selezionate il pivot nella colonna pivot, ricordando che questi devono sempre essere un numero positivo. Per ogni positivo inserite "b" nella colonna pivot e computate il ratio a/b, laddove "a" è un numero nella colonna "Risposta" di quella fila. Di questi ratio test scegliete il più piccolo. Il corrispondente numero "b" è il pivot. Usate il pivot per determinare la colonna nella maniera normale, facendo attenzione a seguire la regole esatte per la formulazione delle operazioni di fila. Fatto ciò, rinominate la fila pivot col nome della colonna pivot. La variabile che in origine denominava la fila pivot è la variabile di partenza o esistente e la variabile che denomina la colonna è la variabile d’entrata.

Continua la lettura
57

La soluzione della programmazione lineare

Per ottenere la soluzione di base corrispondente a qualsiasi tableau col metodo simplesso mettete a zero tutte le variabili che non appaiono come etichette fila (sono le "variabili inattive"). Il valore di una variabile in qualità di etichetta fila ("variabile attiva") è il numero nella colonna all’estrema destra in quella fila, diviso per il numero in quella fila nella colonna etichettata dalla stessa variabile. Nel caso di vincoli non standard, per risolvere un problema con vincoli della forma Ax + By + . .. ≥ N con N positivo, sottraete una variabile surplus dalla sinistra, piuttosto che aggiungere una variabile slack. La soluzione base corrispondente al tableau iniziale non sarà ammissibile, poiché alcune delle variabili attive saranno negative. Di conseguenza, le regole per il pivoting iniziale sono diverse da quelle suddette. Per risolvere un problema di minimizzazione usando il metodo simplesso convertitelo in un problema di massimizzazione. Se dovete minimizzare c, massimizzate invece p = -c. Abbiamo terminato la nostra guida sulla programmazione lineare. Per ulteriori informazioni consultate il link: http://www.profguida.it/Esercizi/Programmazione_lineare.pdf.

67

Guarda il video

77

Consigli

Non dimenticare mai:
  • Se non siete particolarmente a vostro agio con la matematica, fatevi aiutare da un insegnante o da una persona più competente di voi. Prendete lezioni private attraverso le ripetizioni.
Alcuni link che potrebbero esserti utili:

Potrebbe interessarti anche

Segnala contenuti non appropriati

Tipo di contenuto
Devi scegliere almeno una delle opzioni
Descrivi il problema
Devi inserire una descrizione del problema
Si è verificato un errore nel sistema. Riprova più tardi.
Segnala il video che ritieni inappropriato
Devi selezionare il video che desideri segnalare
Verifica la tua identità
Devi verificare la tua identità
chiudi
Grazie per averci aiutato a migliorare la qualità dei nostri contenuti

Guide simili

Superiori

Elementi di algebra lineare

L'algebra lineare è una branca della matematica che studia principalmente gli spazi vettoriali, i vettori, le trasformazioni lineari e i sistemi lineari. Vedremo, in questa guida, quindi, gli elementi base di ognuno di questi argomenti dell'algebra lineare...
Superiori

Come determinare se una funzione è lineare

Attraverso questa semplice ed interessante guida, troveremo ottimi consigli e suggerimenti su come determinare se una funzione è lineare. Nella matematica c'è da dire che le funzioni, costituiscono uno degli argomenti sicuramente più complessi e, quindi...
Superiori

Come risolvere un sistema lineare

In questo articolo si è deciso di dedicarlo ad un argomento molto utile a tutti gli studenti, che si accingono ad affrontarlo a scuola, durante l'anno scolastico. Nello specifico si è ben pensato di parlare sul come poter risolvere, nel modo più veloce...
Superiori

Come risolvere un'equazione differenziale di primo ordine lineare

Se ci troviamo di fronte a un'equazione differenziale di primo ordine lineare potremmo non avere idea di come proseguire. In realtà risolvere questo tipo di equazione non è così difficile, a patto di aver capito esattamente di cosa si tratta. In realtà,...
Superiori

Come rappresentare un'equazione lineare sul piano cartesiano

Un'equazione lineare è un'equazione algebrica di primo grado, ovvero che il grado massimo dei termini che le appartengono è uno. Per poter rappresentare qualsiasi genere di curva sul piano cartesiano, è necessario ridurre l'equazione, di qualunque...
Superiori

Come calcolare l'ingrandimento lineare

Una lente ha la proprietà di convergere i raggi di luce e quindi creare un'immagine virtuale di un oggetto. Questa proprietà della lente di formare immagini virtuali degli oggetti dove viene proiettato il focus è soggetta ad un incremento di grandezza....
Superiori

Come risolvere una congruenza lineare

Quando si ha a che fare con dei calcoli matematici, trovare il metodo più rapido per arrivare alla soluzione può essere davvero difficile. Si tratta di sviluppare nella maniera giusta una serie di calcoli, riducendo al minimo il rischio di errore e...
Superiori

Come risolvere graficamente un sistema lineare

Per sistema di equazioni lineari di si intende un sistema formato da n equazioni lineari in n incognite, se scelgo n=2 il sistema avrà la forma:1) a1x+b1y=c12) a2x+b2y=c2. Come risolvere graficamente un sistema lineare? Farlo significa trovare valori...
I presenti contributi sono stati redatti dagli autori ivi menzionati a solo scopo informativo tramite l’utilizzo della piattaforma www.o2o.it e possono essere modificati dagli stessi in qualsiasi momento. Il sito web, www.o2o.it e Arnoldo Mondadori Editore S.p.A. (già Banzai Media S.r.l. fusa per incorporazione in Arnoldo Mondadori Editore S.p.A.), non garantiscono la veridicità, correttezza e completezza di tali contributi e, pertanto, non si assumono alcuna responsabilità in merito all’utilizzo delle informazioni ivi riportate. Per maggiori informazioni leggi il “Disclaimer »”.