Math
Simplesso nel piano
La regione ammissibile sta sul tavolo e sopra pende una lastra all'altezza dell'obiettivo. L'obiettivo è lineare, quindi la lastra è piana e inclinata, e il punto migliore è letteralmente il suo angolo più alto.
Cosa succede
Due variabili e qualche vincolo: ognuno è un muro sul tavolo, e ciò che resta dentro è la regione ammissibile. Sopra pende una lastra la cui altezza in ogni punto è l'obiettivo p·x + q·y. Essendo lineare, la lastra è un piano inclinato e liscio - non ha colline in mezzo -, e il punto migliore è il suo angolo più alto. Da lì viene tutto: la risposta sta sempre in un vertice, e 60 000 sondaggi dentro la regione non ne hanno mai battuto uno. Il simplesso sale quella scala: dall'origine a un angolo vicino più alto, un pivot alla volta, e si ferma dove nessun vicino è più alto. La sua risposta è confrontata con un'enumerazione di tutti i vertici, che della tabella non sa nulla. Spingi un muro di uno e l'ottimo cresce esattamente del suo prezzo ombra - a meno che tre muri si incontrino nell'angolo in alto, e allora un tasso unico non c'è.
Equazioni del modulo
Equazioni massimizzare p·x + q·y con il vincolo a·x + b·y ≤ c per ogni riga, e x ≥ 0, y ≥ 0 la regione ammissibile è l'intersezione di semipiani; l'obiettivo è lineare, quindi la sua lastra sopra la regione è un piano inclinato quindi il massimo si trova in un VERTICE - un punto in cui si incrociano due delle rette (contano anche gli assi) e ogni vincolo è ancora soddisfatto simplesso: si parte dall'origine (ogni c ≥ 0, quindi è ammissibile), ci si sposta su un vertice vicino che aumenta l'obiettivo, ci si ferma quando nessuno lo fa la regola di Bland - entra la variabile di indice minimo tra quelle ammissibili, esce quella di indice base minimo tra i rapporti a pari merito - rende impossibili i cicli il prezzo ombra di una riga è la variabile duale: se si sposta il suo c di h l'ottimo cresce di h·y, a meno che il vertice ottimo sia DEGENERE vertice degenere: più di due rette per lo stesso punto - lì la derivata non esiste, quindi il prezzo ombra non è definito
