| Lingua : |
|
| Comunità Encyclopedia |Enciclopedia Risposte |Invia domanda |Conoscenza Vocabolario |Carica conoscenza |
Metodo Simplex |
|
Metodo Simplex per la risoluzione di problemi di programmazione lineare metodo comune. Simplex è un matematico americano GB Danzica nel 1947 prima proposta. È la base teorica: programmazione problema regione ammissibile lineare è un vettore n-dimensionale spazio Rn, poliedrica insieme convesso, il valore ottimale se ci sarà uno dei vertici del convesso istituiti. Soluzione praticabile corrispondenti ai vertici chiamato soluzione di base ammissibile. L'idea di base del metodo simplex sono: in primo luogo trovare una soluzione di base, l'autenticazione, vedere se è la soluzione ottimale, in caso contrario, passare a un altro in base a determinate regole per migliorare la soluzione di base, e quindi identificare, se ancora non lo è, poi convertire, clicca qui ripetuto. A causa del numero limitato di soluzione di base, si è limitato dalla conversione sarà in grado di arrivare alla soluzione ottimale. Se il problema non è la soluzione ottimale può distinguere questo metodo.Contorno Secondo il principio del metodo simplex, problemi di programmazione lineare, le variabili di decisione (variabili di controllo) x1, x2, ... xn valore è chiamato una soluzione per soddisfare tutti i vincoli della soluzione è detta soluzione ammissibile. La funzione obiettivo raggiunge il massimo (o minimo) è chiamato una soluzione fattibile per la soluzione ottimale. In questo modo, una soluzione ottimale per l'intera determinato dai vincoli della funzione obiettivo all'interno della regione ammissibile raggiunge il massimo (o minimo). Lo scopo di risolvere problemi di programmazione lineare è quello di trovare la soluzione ottimale. Soluzione ottimale può essere una delle seguenti condizioni: ① l'esistenza di una soluzione ottimale; ② ci sono infinite soluzioni ottimali; ③ soluzione ottimale non esiste, questo avviene solo in entrambi i casi, che nessuna soluzione fattibile o l' termine constraint non impedisce al valore di funzione obiettivo aumenta indefinitamente (o infiniti aumento nella direzione negativa). Metodo Simplex generalmente passaggi di risoluzione di problemi possono essere riassunti come segue: ① Il problema di programmazione lineare equazioni di vincolo espresso in una forma canonica delle equazioni, trovare la soluzione di base come la soluzione di base ammissibile iniziale. ② Se la soluzione di base non esiste, che i vincoli sono contraddittori, il problema non ha soluzione. ③ Se la soluzione di base esiste, dalla soluzione di base iniziale come punto di partenza, in base alle condizioni di condizioni di ottimo e fattibilità dell'introduzione di una variabile non basico sostituito variabile di base, il valore della funzione obiettivo di trovare un'altra soluzione ammissibile di base migliorate. ④ Premere il Passaggio 3 itera finché il numero di prova corrispondente a soddisfare condizioni di ottimo (quando non può più essere migliorato il valore di funzione obiettivo), la soluzione ottimale è ottenuto. ⑤ Se il processo di scoperta iterativo, il valore della funzione obiettivo illimitata, terminare l'iterazione. Metodo simplex per risolvere problemi di programmazione lineare dipende principalmente dal numero di iterazioni richieste per il numero di vincoli. Ora l'applicazione generale di problemi di programmazione lineare sono il semplice metodo per risolvere il software standard del computer, per 10 ^ 6 variabili decisionali e vincoli 10 ^ 4 problema di programmazione lineare è stato in grado di risolvere per il computer. Metodo simplex modificato Algoritmo simplex originale non è molto economico. 1953 matematico americano GB metodo simplex Danzig per migliorare ogni iterazione errori di arrotondamento accumulati, suggerire miglioramenti metodo simplex. I passaggi di base e metodo simplex sono sostanzialmente uguali, la differenza principale è più in iterazioni successive basato su eliminazione Gaussiana, ma dalla vecchia matrice di base per calcolare direttamente la matrice inversa inversa nuova base, e quindi determinare quale numero di test. In questo modo riduce l'errore di iterazione cumulativo e migliorare la precisione, ma anche di ridurre la quantità di memoria del computer. Metodo del simplesso duale (Metodo del simplesso duale) 1954, il matematico americano C. Lai Muji propone il metodo del simplesso duale. Metodo simplex è una soluzione ammissibile del problema originale in un'altra soluzione ammissibile da iterativamente fino al raggiungimento del numero di test per soddisfare la condizione di ottimalità. La regola del simplesso duale sta iniziando a soddisfare la duplice condizione di fattibilità gradualmente attraverso iterativo di ricerca della soluzione ottimale del problema originale. Mantenuto in soluzioni basate su processo iterativo per la doppia possibilità, lasciando infeasibility gradualmente scomparire. Lasciate che il problema originale è min {cx | Ax = b, x ≥ 0}, allora il problema duale (Dual problema) è max {yb | yA ≤ c}. Quando il problema originale di una soluzione di base soddisfa le condizioni di ottimo, il suo numero di test CBB-1A-C ≤ 0. Che è noto y = CBB-1 (chiamato operatore di fronte) è una soluzione praticabile del problema duale. La fattibilità del cosiddetto doppio incontro, riferendosi al numero di test da soddisfare le condizioni di ottimo. Pertanto, la possibilità di mantenere la premessa di dualità, una soluzione praticabile quando la soluzione di base, che è anche la soluzione ottimale. Altre informazioni Ottimizzazione matematica da George Dantzig ha inventato il metodo del simplesso per problemi di programmazione lineare è risolto tecnologie numericamente popolari. Vi è un algoritmo è irrilevante, ma il nome è simile, è noto metodo Nelder-Mead o discesa metodo simplex, scoperta dal Nelder e Mead (1965), che viene utilizzato per problemi di ottimizzazione libera, un metodo numerico multi-dimensionale, appartenente a di ricerca più generali classi algoritmo. Entrambi i quali sono utilizzati in concetto simplex, che è N-dimensionale in N 1 vertici del guscio convesso è più di un corpo cellulare: una linea retta su un segmento di linea, un triangolo su un aereo, spazio tridimensionale di un tetraedro , e così via. |
| Utente Recensione |
|
Ancora nessun commento |
