Come aggiungere Tagli alla Programmazione Lineare

programmazione lineare è un metodo matematico di ottimizzazione delle funzioni matematiche in un insieme di vincoli . Programmazione lineare intera programmazione lineare richiede un ulteriore passo avanti ponendo un ulteriore vincolo sul set di soluzioni : solo numeri interi sono da considerarsi come soluzioni . Un taglio , in termini di programmazione lineare intera , pone un altro vincolo sul problema matematico già fortemente vincolata . Tuttavia , questo vincolo supplementare non è senza significato - cambia spesso il problema in un modo che permette alla soluzione di apparire più rapidamente . Aggiunta di un taglio di un problema di programmazione lineare intera coinvolge riorganizzare il tableau ottimale la soluzione del problema . Istruzioni
1

risolvere il problema di programmazione lineare intera fino al tableau ottimale è raggiunto. Utilizzare il metodo standard di programmazione lineare intera fino a quando il tableau ottimale è visibile .
2

Scegli uno dei vincoli sul tableau. La scelta è arbitraria . I vincoli del tableau appaiono come righe. Scegliere una riga oltre la riga di fondo ( questa è la funzione di ottimizzazione e non un vincolo ) .
3

Scrivere il vincolo nella sua forma matematica . Dovrebbe essere chiaro dal tableau come scrivere questo . Scrivere ogni elemento della riga moltiplicato per la variabile nella colonna corrispondente . Sommare gli elementi e li corrispondere al numero che appare nella voce di estrema destra nella fila .
4

Manipolare l'equazione in modo che solo i numeri interi appaiono sul lato sinistro e solo frazioni appaiono su il lato destro . Ad esempio, se l'equazione è ( 3/2 ) x + 3y = 58 /30, utilizzare l'algebra per riorganizzare questo x + 3y - 1 = - . ( 1/2) x + 28/30

5

Prendere il lato destro della nuova equazione e vincolarlo . Si noti che il lato destro otterrà solo più piccolo e negativo come gli X - variabile aumenta. Così , vincolato il lato destro sia minore di zero . Il vincolo è ora - ( 1/2) x + 28/30 < 0 . Questo vincolo è il taglio .
6

Aggiungi il taglio al numero intero problema di programmazione lineare originale come un nuovo vincolo . Se il problema originale aveva vincoli " n" , il nuovo problema di programmazione lineare intera con un taglio ha " n + 1 " vincoli , e produrrà una soluzione diversa ( così come un diverso tableau ottimale) .