Algoritmo simplex e punti estremi
Per questa domanda la mia scorciatoia è LP = programma lineare, BFS = soluzione fattibile di base, SEF = forma di uguaglianza standard.
Poiché l'algoritmo Simplex itera da punto estremo a punto estremo (corrispondente al fatto che Simplex itera da BFS a BFS quando l'LP è in SEF), come funziona geometricamente l'algoritmo Simplex quando la regione ammissibile è un poliedro che non può essere realizzato in SEF (ad es. Mezzo spazio)? Supponiamo di avere un LP per il quale la regione ammissibile non ha punti estremi. Quindi possiamo scrivere un LP "equivalente" che è in SEF ed eseguire invece l'algoritmo Simplex su di esso. Ma ci sono punti estremi per questo nuovo poliedro, mentre non ce ne sono per l'originale, per ipotesi. All'inizio pensavo che i punti estremi di un LP corrispondessero biettivamente ai punti estremi dell'altro, ma evidentemente non è così.
Quindi, quando esattamente i punti estremi della versione SEF di un LP corrispondono in modo biettivo ai punti estremi dell'originale? Inoltre, quando una tale biiezione non vale, come dovremmo interpretare geometricamente ciò che l'algoritmo Simplex sta facendo in termini di LP originale?
Risposte
l'algoritmo Simplex itera da un punto estremo all'altro
Tecnicamente no. L'algoritmo simplex itera di base in base . Succede solo che soluzioni di base fattibili corrispondono a punti estremi. (per esempio, il dual simplex itera attraverso soluzioni di base duali ammissibili, che non sono punti estremi della regione ammissibile primale).
Considera un LP in forma standard, che scrive \begin{align} \min \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & Ax = b\\ &x \geq 0 \end{align}La regione ammissibile di quel LP è sempre poliedrica. Se non ha punti estremi, allora è vuoto (e non ci sono soluzioni fattibili di base) o un sottospazio affine di$\mathbb{R}^{n}$. Ora, quest'ultimo caso non può accadere, perché nessun sottospazio affine può essere un sottoinsieme di$\mathbb{R}_{+}^{n}$.
Ora, tornando a (quello che penso sia) la tua domanda originale: dato un poliedro originale e una rappresentazione SEF per esso, quella rappresentazione ha punti estremi e corrispondono ai punti estremi del polyhderon originale? La risposta è: sì, il SEF avrà punti estremi e no, potrebbero non corrispondere sempre ai punti estremi del tuo poliedro originale.
Ecco un semplice esempio: prendere $\mathcal{P} = \{x \in \mathbb{R}\}$, che è un poliedro unidimensionale. La sua formulazione ha una variabile libera e nessun vincolo.
Per creare una rappresentazione SEF, sostituire $x$ di $x^{+} - x^{-}$ con $x^{\pm} \geq 0$. Adesso,$(0, 0)$ è un punto estremo di quel SEF, che corrisponde a $x=0$, che non è un punto estremo di $\mathcal{P}$.
Non sono sicuro di aver compreso appieno la tua domanda, ma immagino che la tua confusione derivi dal presupposto che una soluzione di base sia un "punto estremo". Una soluzione di base (non necessariamente primaria o doppia fattibile) è solo l'intersezione di vincoli del numero di righe (alcuni dei quali potrebbero essere limiti). È possibile che un problema non abbia una soluzione fattibile primaria o duale in quanto il risultato è irrealizzabile o illimitato. Gli algoritmi simplex da manuale a volte ignorano il fatto che una qualche forma di approccio di fase 1 è necessaria per stabilire un BFS per avviare effettivamente l'algoritmo. È possibile che una fase primaria 1 trovi il problema primario non fattibile ed è anche possibile che una fase duale 1 trovi il problema illimitato.
Aggiornamento: la risposta di mtanneau probabilmente sta dicendo tutto quello che c'è da dire, per un singolo vincolo con variabili libere si applica lo stesso. Voglio solo aggiungere che le implementazioni simplex funzionano direttamente con variabili libere e non le convertono in due variabili limitate da 0. Ma lo stesso vale, l'algoritmo itera su soluzioni di base e si stabilisce la convenzione che le variabili libere non di base prendono il valore 0. Si noti inoltre che per i poliedri limitati, le soluzioni di base corrispondono a punti estremi.