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

Università e Master

Programmazione in C++: le classi

La tecnologia sta prendendo via via sempre più piede e quindi risulta negativo non conoscere almeno un linguaggio di programmazione. Tra i linguaggi più diffusi si trova sicuramente Java, ad esso è secondo C++, un mix tra linguaggio procedurale (ad...
Università e Master

Appunti di programmazione C++

Il C++ è un linguaggio di programmazione sviluppato da Bjarne Stroustrup nel 1983, esso è un linguaggio orientato agli oggetti ed è definito come un miglioramento di un altro linguaggio di programmazione, il C. Il creatore iniziò a svilupparlo circa...
Università e Master

Come trovare il nucleo di una applicazione lineare

Un argomento estremamente importante per l'esame di geometria, riguarda il metodo per trovare il nucleo di una applicazione lineare; infatti, si tratta di avere una certa pratica e dimestichezza in merito. Nella seguente guida vi sarà spiegato in...
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 confrontare funzioni lineari e non lineari

L'argomento calza bene le pagine di un manuale di algebra, nel capitolo del calcolo infinitesimale. La lente della nostra analisi scende sulle funzioni, lineari e non lineari. Scorrete l'articolo per sapere come confrontare funzioni lineari e non lineari....
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...
Superiori

Come risolvere le disequazioni lineari in due incognite

Con il finire della scuola e dei corsi cominciano i periodi degli esami per i liceali e per gli studenti universitari, si mette alla prova quello che si è studiato in tutto l'anno con sacrificio e costanza. Solo chi studia con passione può sapere quanto...
Università e Master

Appunti di programmazione C#

Con l'avvento dell'era digitale i linguaggi di programmazione sono aumentanti a dismisura. Ci sono diverse categorie di linguaggi di programmazione, ognuna studiata e strutturate per agevolare determinati compiti. Dal linguaggio macchina (quello inizialmente...
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 »”.