Con il metodo grafico per la risoluzione dei problemi di PL, abbiamo infatti scelto dall'insieme dei vertici appartenenti al confine dell'insieme delle soluzioni del sistema di disequazioni tale vertice in corrispondenza del quale il valore della funzione obiettivo ha raggiunto il suo massimo (minimo). Nel caso di due variabili, questo metodo è del tutto intuitivo e permette di trovare rapidamente una soluzione al problema.
Se ci sono tre o più variabili nel problema, e nei problemi economici reali questa è esattamente la situazione, è difficile visualizzare l'area delle soluzioni al sistema delle restrizioni. Tali compiti sono risolti usando metodo del simplesso o con il metodo del miglioramento successivo. L'idea del metodo è semplice ed è la seguente.
Secondo una certa regola, si trova il piano di riferimento iniziale (alcuni vertici dell'area di vincolo). Viene verificato se il piano è ottimale. Se sì, allora il problema è risolto. In caso contrario, passa a un altro piano migliorato, a un altro picco. il valore della funzione obiettivo su questo piano (a questo vertice) è ovviamente migliore del precedente. L'algoritmo di transizione viene eseguito utilizzando un passo computazionale, che viene convenientemente scritto sotto forma di tabelle, chiamato tabelle simplex ... Poiché il numero di vertici è finito, allora in un numero finito di passi arriviamo alla soluzione ottima.
Consideriamo il metodo del simplesso usando un esempio specifico del problema di elaborare un piano.
Si noti ancora che il metodo del simplesso è applicabile alla risoluzione di problemi PL canonici ridotti a una forma speciale, cioè aventi una base, membri destri positivi e una funzione obiettivo espressa in termini di variabili non base. Se l'attività non è ridotta a un modulo speciale, sono necessari passaggi aggiuntivi, di cui parleremo in seguito.
Consideriamo il problema di un piano di produzione, avendo precedentemente costruito un modello e ridottolo a una forma speciale.
Compito.
Per la fabbricazione di prodotti UN e V il magazzino può rilasciare non più di 80 unità di materie prime. Inoltre, per la fabbricazione del prodotto UN si consumano due unità e i prodotti V- una unità di materie prime. È necessario pianificare la produzione in modo tale da garantire il massimo profitto se i prodotti UNè necessario realizzare non più di 50 pezzi e prodotti V- non più di 40 pz. Inoltre, il profitto dalla vendita di un prodotto UN- 5 rubli, e da V- 3 rubli.
Costruiamo un modello matematico, che denota per X 1 numero di prodotti A nel piano, per X 2 - numero di prodotti V... quindi il sistema di restrizioni sarà simile a questo:
Portiamo il problema in forma canonica introducendo ulteriori variabili:
(3.10)
F = -5x 1 - 3x 2 → min.
Questo problema ha una forma speciale (con una base, i membri di destra sono non negativi). Può essere risolto usando il metodo del simplesso.
iopalcoscenico. Scrivere un problema su una tabella simplex. Esiste una corrispondenza biunivoca tra il sistema di vincoli del problema (3.10) e la tabella del simplesso. Ci sono tante righe nella tabella quante sono le uguaglianze nel sistema di vincoli e ci sono tante colonne quante sono le variabili libere. Le variabili di base riempiono la prima colonna, le variabili libere - la riga superiore della tabella. La linea di fondo è detta linea di indice e contiene i coefficienti delle variabili nella funzione obiettivo. Inizialmente 0 è scritto nell'angolo in basso a destra se non c'è un termine libero nella funzione; se c'è, allora lo scriviamo con il segno opposto. In questo punto (nell'angolo in basso a destra) ci sarà il valore della funzione obiettivo, che, quando si sposta da una tabella all'altra, dovrebbe aumentare in modulo. Quindi, il nostro sistema di restrizioni corrisponde alla tabella 3.4 e possiamo procedere alla fase II della soluzione.
Tabella 3.4
|
linea di base |
libero |
||
IIpalcoscenico... Verifica dell'ottimalità del piano di supporto.
Questa tabella 3.4 corrisponde al seguente piano di base:
(X 1 , X 2 , X 3 , X 4 , X 5) = (0, 0, 50, 40, 80).
Variabili libere X 1 , X 2 sono uguali a 0; X 1 = 0, X 2 = 0. E le variabili di base X 3 , X 4 , X 5 assumere i valori X 3 = 50, X 4 = 40, X 5 = 80 - dalla colonna dei membri liberi. Valore della funzione obiettivo:
-F = - 5X 1 - 3X 2 = -5 0 - 3 0 = 0.
Il nostro compito è verificare se un determinato piano di base è ottimale. per questo, è necessario visualizzare la linea dell'indice - la linea della funzione obiettivo F.
Sono possibili diverse situazioni.
1. Nell'indice F-string non ha elementi negativi. Ciò significa che il piano è ottimale, puoi scrivere la soluzione al problema. La funzione obiettivo ha raggiunto il suo valore ottimale pari al numero in basso a destra preso con il segno opposto. Passiamo al IV stadio.
2. La riga dell'indice contiene almeno un elemento negativo, la cui colonna non contiene elementi positivi. Quindi concludiamo che la funzione obiettivo F→ ∞ diminuisce illimitatamente.
3. La riga dell'indice contiene un elemento negativo con almeno un elemento positivo nella sua colonna. Quindi passiamo alla fase successiva III. ricalcolare la tabella, migliorando la linea di base.
IIIpalcoscenico... Migliorare la linea di base.
Da elementi indice negativi F-Le righe scelgono il modulo più grande, chiama la risoluzione della colonna corrispondente e segna "".
Per selezionare la riga risolvente è necessario calcolare i rapporti degli elementi della colonna membro libero solo a positivo elementi colonna permissivi. Scegli il minimo tra le relazioni ottenute. L'elemento corrispondente al quale si raggiunge il minimo è detto permissivo. Lo evidenzieremo con un quadrato.
Nel nostro esempio, 
, l'elemento 2 è permissivo. La linea corrispondente a questo elemento è anche chiamata risolvente (Tabella 3.5).
Tabella 3.5
Scelto l'elemento risolutivo, ricalcoliamo la tabella secondo le regole:
1. Nella nuova tabella delle stesse dimensioni di prima, le variabili della riga e della colonna di risoluzione vengono scambiate, il che corrisponde al passaggio a una nuova base. Nel nostro esempio: X 1 è incluso nella base, invece di X 5, che lascia la base ed è ora libero (Tabella 3.6).
Tabella 3.6
|
linea di base |
libero |
||
2. Al posto dell'elemento risolutivo 2, annota il suo numero inverso.
3. Gli elementi della linea risolutiva sono divisi per l'elemento risolutivo.
4. Gli elementi della colonna risolutiva sono divisi per l'elemento risolutivo e scritti con il segno opposto.
5. Per riempire i restanti elementi della Tabella 3.6, ricalcoliamo secondo la regola del rettangolo. Supponiamo di voler contare l'elemento alla posizione 50.
Colleghiamo mentalmente questo elemento con quello risolvente, troviamo il prodotto, sottraiamo il prodotto degli elementi situati sull'altra diagonale del rettangolo risultante. Dividiamo la differenza per l'elemento risolvente.
Così, . Scriviamo 10 nel punto in cui era 50. Allo stesso modo :
, 
, , 
.
Tabella 3.7
Abbiamo una nuova tabella 3.7, le variabili di base sono ora le variabili (x 3, x 4, x 1). Il valore della funzione obiettivo è diventato uguale a -200, cioè diminuito. Per verificare l'ottimalità di questa soluzione di base, è necessario tornare alla fase II. Il processo è ovviamente finito, i criteri di arresto sono i punti 1 e 2 della II tappa.
Porteremo la soluzione al problema fino alla fine. Per fare ciò, controlla la riga dell'indice e, vedendo un elemento negativo in essa, chiama la risoluzione della colonna corrispondente e, secondo la fase III, ricalcola la tabella. Dopo aver compilato le relazioni e scegliendo tra esse il minimo = 40, abbiamo determinato l'elemento risolutivo 1. Ora effettuiamo il ricalcolo secondo le regole 2-5.
Tabella 3.8
|
linea di base |
libero |
||
|
x 3 = 30, X 2 = 40, X 1 = 20. Le variabili libere sono 0, X 5 = 0, X 4 = 0. La funzione obiettivo assume il valore dell'ultimo elemento della colonna dei membri liberi con il segno opposto: - F = -220 F = 220, nel nostro esempio la funzione è stata esaminata per min, e inizialmente F max, quindi il segno in realtà è cambiato due volte. Così, X* = (20, 40, 30, 0, 0), F* = 220. Risposta al problema: È necessario includere 20 prodotti del tipo UN, 40 prodotti di tipo B, mentre il profitto sarà massimo e sarà pari a 220 rubli. Alla fine di questa sezione, presentiamo uno schema a blocchi dell'algoritmo del metodo simplex, che ripete esattamente i passaggi, ma, forse, per alcuni lettori sarà più comodo da usare, poiché le frecce indicano una chiara direzione di azione. I collegamenti sopra i rettangoli nel diagramma di flusso mostrano a quale fase o sottoclausola appartiene il gruppo di trasformazione corrispondente. la regola per trovare il piano di riferimento iniziale sarà formulata nella clausola 3.7.
Domande per l'autocontrollo 1. Come si costruisce una tabella simplex? 2. Come si riflette la variazione di base nella tabella? 3. Formulare un criterio di arresto per il metodo del simplesso. 4. Come organizzare il ricalcolo della tabella? 5. Da quale riga conviene iniziare a ricalcolare la tabella? |
... Algoritmo metodo simplex
Esempio 5.1. Risolvi il seguente problema di programmazione lineare utilizzando il metodo del simplesso:
Soluzione:
io iterazione:
x3, x4, x5, x6 x1,x2... Esprimiamo le variabili di base in termini di quelle libere:
Portiamo la funzione obiettivo alla seguente forma:
Sulla base del problema ottenuto, formeremo la tabella del simplesso iniziale:
Tabella 5.3
Tabella simplex di origine
Relazioni di valutazione |
||||
Secondo la definizione della soluzione di base, le variabili libere sono uguali a zero e i valori delle variabili di base sono uguali ai valori corrispondenti dei numeri liberi, ovvero:
Fase 3: verifica della compatibilità del sistema di restrizione LPP.
A questa iterazione (in Tabella 5.3), non è stato identificato il segno di incompatibilità del sistema di restrizioni (segno 1) (cioè non esiste una riga con un numero libero negativo (tranne la linea della funzione obiettivo), che non non contenere almeno un elemento negativo (es. coefficiente negativo in corrispondenza di una variabile libera)).
A questa iterazione (in Tabella 5.3), il segno dell'illimitatezza della funzione obiettivo (segno 2) non è stato identificato (cioè non esiste una colonna con un elemento negativo nella riga della funzione obiettivo (ad eccezione della colonna di numeri), che non ha almeno un elemento positivo) ...
Poiché la soluzione di base trovata non contiene componenti negativi, è ammissibile.
Fase 6: verifica dell'ottimalità.
La soluzione di base trovata non è ottimale, poiché, secondo il criterio di ottimalità (caratteristica 4), non dovrebbero esserci elementi negativi nella linea della funzione obiettivo (il numero libero di questa linea non viene preso in considerazione quando si considera questa caratteristica) . Pertanto, secondo l'algoritmo del metodo del simplesso, passiamo all'ottavo stadio.
Poiché la soluzione di base trovata è ammissibile, la ricerca della colonna risolvente verrà effettuata secondo il seguente schema: determiniamo le colonne con elementi negativi nella riga della funzione obiettivo (ad eccezione della colonna dei numeri liberi). Secondo la tabella 5.3, ci sono due di queste colonne: la colonna " x1"E la colonna" x2". Di queste colonne viene selezionata quella che contiene l'elemento più piccolo nella riga della funzione obiettivo. Si risolverà. Altoparlante" x2"Contiene l'elemento più piccolo (–3) rispetto alla colonna" x1
Per determinare la linea risolutiva, troviamo i rapporti valutativi positivi dei numeri liberi rispetto agli elementi della colonna risolvente, la linea, che corrisponde al rapporto valutativo positivo più piccolo, è presa come consentito.
Tabella 5.4
Tabella simplex di origine
Nella tabella 5.4, il rapporto stimato positivo più piccolo corrisponde alla riga “ x5”, Pertanto, si risolverà.
L'elemento situato all'intersezione tra la colonna di autorizzazione e la riga di autorizzazione viene accettato come permettendo. Nel nostro esempio, questo è un elemento situato all'intersezione della linea " x5"E colonne" x2».
L'elemento risolutivo mostra una variabile di base e una libera che devono essere scambiate nella tabella simplex per passare a una nuova soluzione di base "migliorata". In questo caso, queste sono variabili x5 e x2, nella nuova tabella simplex (tabella 5.5) li scambiamo.
9.1. Trasformazione dell'elemento di risoluzione.
L'elemento permissivo della tabella 5.4 è trasformato come segue:
Inseriamo il risultato ottenuto in una cella simile nella Tabella 5.5.
9.2. Converti la stringa di risoluzione.
Dividiamo gli elementi della riga di risoluzione della Tabella 5.4 per l'elemento di risoluzione di questa tabella del simplesso, i risultati si inseriscono in celle simili della nuova tabella del simplesso (Tabella 5.5). Le trasformazioni degli elementi della linea di risoluzione sono riportate nella Tabella 5.5.
9.3. Conversione della colonna di risoluzione.
Gli elementi della colonna di risoluzione della Tabella 5.4 sono divisi per l'elemento di risoluzione della tabella simplex data e il risultato è preso con il segno opposto. I risultati ottenuti si inseriscono in celle simili della nuova tabella del simplesso (Tabella 5.5). Le trasformazioni degli elementi della colonna di risoluzione sono mostrate nella Tabella 5.5.
9.4. Converti il resto degli elementi della tabella simplex.
La trasformazione degli elementi rimanenti della tabella simplex (cioè elementi non situati nella riga risolutiva e nella colonna risolvente) viene eseguita secondo la regola del "rettangolo".
Si consideri ad esempio la trasformazione di un elemento posto all'intersezione della stringa " x3"E la colonna" ", la designeremo convenzionalmente come" x3". Nella tabella 5.4, disegna mentalmente un rettangolo, il cui vertice si trova nella cella, il cui valore trasformiamo (cioè nella cella " x3»), E l'altro (vertice diagonale) è nella cella con l'elemento risolvente. Gli altri due vertici (la seconda diagonale) sono determinati in modo univoco. Quindi il valore trasformato della cella " x3"Sarà uguale al valore precedente di questa cella meno la frazione, al cui denominatore c'è un elemento risolvente (dalla Tabella 5.4), e nel numeratore il prodotto di altri due vertici non utilizzati, ovvero:
« x3»: .
I valori di altre celle vengono trasformati in modo simile:
« x3 x1»: ;
« x4»: 
;
« x4 x1»: ;
« x6»: 
;
« x6 x1»: ;
«»: 
;
« x1»: 
.
Come risultato di queste trasformazioni si è ottenuta una nuova tabella del simplesso (tabella 5.5).
II iterazione:
Fase 1: stesura di una tabella simplex.
Tabella 5.5
Tavolo SimplexII iterazioni
Stimato relazione |
||||
| ||||
|
|
Fase 2: determinazione della soluzione di base.
Come risultato delle trasformazioni del simplesso, è stata ottenuta una nuova soluzione di base (Tabella 5.5):
Come puoi vedere, con questa soluzione di base, il valore della funzione obiettivo = 15, che è maggiore rispetto alla precedente soluzione di base.
L'incoerenza del sistema di restrizioni secondo l'attributo 1 nella tabella 5.5 non è stata rilevata.
Fase 4: verifica della limitatezza della funzione obiettivo.
L'illimitatezza della funzione obiettivo in accordo con la caratteristica 2 nella Tabella 5.5 non è stata rivelata.
Fase 5: verifica dell'ammissibilità della soluzione di base trovata.
La soluzione di base trovata secondo la caratteristica 4 non è ottimale, poiché la linea della funzione obiettivo della tabella del simplesso (Tabella 5.5) contiene un elemento negativo: –2 (il numero libero di questa linea non viene preso in considerazione quando si considera questo caratteristica). Pertanto, passiamo alla fase 8.
Fase 8: determinazione dell'elemento risolvente.
8.1. Definizione della colonna risoluzione.
La soluzione di base trovata è ammissibile, definiamo le colonne con elementi negativi nella riga della funzione obiettivo (tranne la colonna dei numeri liberi). Secondo la tabella 5.5, solo una colonna è tale: " x1". Pertanto, lo accettiamo come consentito.
8.2. Determinazione della stringa di autorizzazione.
Secondo i valori ottenuti dei rapporti valutativi positivi nella Tabella 5.6, il minimo è il rapporto corrispondente alla linea " x3". Pertanto, lo accettiamo come consentito.
Tabella 5.6
Tavolo SimplexII iterazioni
Stimato relazione |
||||
3/1 = 3 - min |
||||
Fase 9: trasformazione della tavola del simplesso.
Le trasformazioni di tabelle simplex (tabelle 5.6) vengono eseguite nello stesso modo dell'iterazione precedente. I risultati delle trasformazioni degli elementi di una tabella simplex sono mostrati nella Tabella 5.7.
III iterazione
Sulla base dei risultati delle trasformazioni del simplesso della precedente iterazione, componiamo una nuova tabella del simplesso:
Tabella 5.7
Tavolo SimplexIII iterazioni
Stimato relazione |
||||
| ||||
|
|
Fase 2: determinazione della soluzione di base.
Come risultato delle trasformazioni del simplesso, è stata ottenuta una nuova soluzione di base (Tabella 5.7):
Fase 3: verifica della coerenza del sistema dei vincoli.
L'incoerenza del sistema di restrizioni secondo l'attributo 1 nella tabella 5.7 non è stata rilevata.
Fase 4: verifica della limitatezza della funzione obiettivo.
L'illimitatezza della funzione obiettivo in accordo con la caratteristica 2 nella Tabella 5.7 non è stata rivelata.
Fase 5: verifica dell'ammissibilità della soluzione di base trovata.
La soluzione di base trovata secondo l'attributo 3 è ammissibile, poiché non contiene componenti negativi.
Fase 6: verifica dell'ottimalità della soluzione di base trovata.
La soluzione di base trovata secondo la caratteristica 4 non è ottimale, poiché la linea della funzione obiettivo della tabella del simplesso (Tabella 5.7) contiene un elemento negativo: –3 (il numero libero di questa linea non viene preso in considerazione quando si considera questo caratteristica). Pertanto, passiamo alla fase 8.
Fase 8: determinazione dell'elemento risolvente.
8.1. Definizione della colonna risoluzione.
La soluzione di base trovata è ammissibile, definiamo le colonne con elementi negativi nella riga della funzione obiettivo (tranne la colonna dei numeri liberi). Secondo la tabella 5.7, solo una colonna è tale: " x5". Pertanto, lo accettiamo come consentito.
8.2. Determinazione della stringa di autorizzazione.
Secondo i valori ottenuti dei rapporti valutativi positivi nella Tabella 5.8, il minimo è il rapporto corrispondente alla linea " x4". Pertanto, lo accettiamo come consentito.
Tabella 5.8
Tavolo SimplexIII iterazioni
Stimato relazione |
||||
5/5 = 1 - min |
||||
Fase 9: trasformazione della tavola del simplesso.
Le trasformazioni di tabelle simplex (Tabella 5.8) vengono eseguite nello stesso modo dell'iterazione precedente. I risultati delle trasformazioni degli elementi di una tabella simplex sono mostrati nella Tabella 5.9.
IV iterazione
Fase 1: costruzione di una nuova tabella simplex.
Sulla base dei risultati delle trasformazioni del simplesso della precedente iterazione, componiamo una nuova tabella del simplesso:
Tabella 5.9
Tavolo SimplexIV iterazioni
Stimato relazione |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
Fase 2: determinazione della soluzione di base.
Come risultato delle trasformazioni del simplesso, è stata ottenuta una nuova soluzione di base, secondo la Tabella 5.9, la soluzione è la seguente:
Fase 3: verifica della coerenza del sistema dei vincoli.
L'incoerenza del sistema di restrizioni secondo l'attributo 1 nella tabella 5.9 non è stata rilevata.
Fase 4: verifica della limitatezza della funzione obiettivo.
L'illimitatezza della funzione obiettivo in accordo con la caratteristica 2 nella Tabella 5.9 non è stata rivelata.
Fase 5: verifica dell'ammissibilità della soluzione di base trovata.
La soluzione di base trovata secondo l'attributo 3 è ammissibile, poiché non contiene componenti negativi.
Fase 6: verifica dell'ottimalità della soluzione di base trovata.
La soluzione di base trovata secondo la caratteristica 4 è ottimale, poiché non ci sono elementi negativi nella linea della funzione obiettivo della tabella del simplesso (Tabella 5.9) (il numero libero di questa linea non viene preso in considerazione quando si considera questa caratteristica) .
Fase 7: verifica dell'alternativa della soluzione.
La soluzione trovata è l'unica, poiché non ci sono elementi nulli nella linea della funzione obiettivo (Tabella 5.9) (il numero libero di questa linea non viene preso in considerazione quando si considera questa caratteristica).
Risposta: il valore ottimo della funzione obiettivo del problema considerato = 24, che si ottiene a.
Esempio 5.2. Risolvi il problema di programmazione lineare di cui sopra a condizione che la funzione obiettivo sia ridotta al minimo:
Soluzione:
io iterazione:
Fase 1: formazione della tabella del simplesso iniziale.
Il problema di programmazione lineare originale è dato in una forma standard. Portiamolo alla sua forma canonica introducendo un'ulteriore variabile non negativa in ciascuno dei vincoli di disuguaglianza, i.e.
Nel sistema di equazioni risultante, prendiamo come variabili (di base) consentite x3, x4, x5, x6, allora le variabili libere saranno x1,x2... Esprimiamo le variabili di base in termini di quelle libere.
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| - | x 1 | + | x 2 | - | S 1 | + | R 1 | = | 1 | |||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> L = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | S. membro | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | W - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S 1 | + | S 2 | = | 12 | |||||||||
| - | x 1 | + | S 1 | + | S 3 | = | 3 |
| x 1 | x 2 | S 1 | S 2 | S 3 | S. membro | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | FA - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | FA - 1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | FA - 13 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
Scopo del servizio... Il servizio è progettato per la risoluzione online di problemi di programmazione lineare (LPP) utilizzando il metodo del simplesso nelle seguenti forme di notazione:
- sotto forma di tabella simplex (metodo delle trasformazioni di Jordan); forma base di registrazione;
- metodo del simplesso modificato; in forma colonnare; in forma di riga.
Istruzione. Selezionare il numero di variabili e il numero di righe (numero di vincoli). La soluzione risultante viene salvata in un file Word ed Excel.
In questo caso non tenere conto dei vincoli del tipo x i ≥ 0. Se nell'attività per alcuni x i non ci sono restrizioni, allora l'LPP deve essere portato al CLP o utilizzare questo servizio. La soluzione rileva automaticamente l'uso di M-metodo(metodo semplice con base artificiale) e metodo del simplesso in due fasi.Con questa calcolatrice vengono utilizzati anche:
Metodo grafico per risolvere LPP
Soluzione del problema di trasporto
Soluzione del gioco Matrix
Utilizzando il servizio online, è possibile determinare il prezzo di un gioco a matrice (limite inferiore e superiore), verificare la presenza di un punto di sella, trovare una soluzione a una strategia mista utilizzando i seguenti metodi: minimax, metodo simplex, grafico (geometrico) metodo, metodo di Brown.
Estremo di una funzione di due variabili
Problemi di programmazione dinamica
Distribuisci 5 lotti omogenei di merce tra tre mercati in modo da ottenere il massimo reddito dalla loro vendita. Il reddito delle vendite in ciascun mercato G (X) dipende dal numero di lotti venduti di merci X ed è presentato nella tabella.
| Volume merce X (in lotti) | Reddito G (X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
Algoritmo metodo simplex include i seguenti passaggi:
- Stesura del primo piano di riferimento. Transizione alla forma canonica del problema di programmazione lineare introducendo variabili di bilancio aggiuntive non negative.
- Controllo del piano per l'ottimalità... Se c'è almeno un coefficiente della riga dell'indice inferiore a zero, il piano non è ottimale e deve essere migliorato.
- Definizione dell'interlinea di colonna e riga... Dei coefficienti negativi della riga dell'indice, viene selezionato il più grande in valore assoluto. Quindi gli elementi della colonna dei membri liberi della tabella simplex sono divisi in elementi dello stesso segno della colonna principale.
- Costruire un nuovo piano di riferimento... Il passaggio a un nuovo piano viene effettuato a seguito del ricalcolo della tabella simplex utilizzando il metodo Jordan-Gauss.
Se è necessario trovare l'estremo della funzione obiettivo, allora stiamo parlando di trovare il valore minimo (F (x) → min, vedi l'esempio di risolvere la funzione di minimizzazione) e il valore massimo ((F (x) → max, vedere l'esempio di risoluzione della funzione di massimizzazione)
La soluzione estrema si ottiene sul confine della regione delle soluzioni ammissibili in corrispondenza di uno dei vertici dei vertici del poligono, o sul segmento compreso tra due vertici adiacenti.
Teorema di base della programmazione lineare... Se la funzione obiettivo della LPP raggiunge un valore estremo in un punto nella regione delle soluzioni ammissibili, allora assume questo valore nel punto d'angolo. Se la funzione obiettivo della LPP raggiunge il suo valore estremo in più di un punto d'angolo, assume lo stesso valore in una qualsiasi delle combinazioni lineari convesse di questi punti.
L'essenza del metodo simplex... Lo spostamento al punto ottimale si effettua spostandosi da un punto d'angolo a quello vicino, che è più vicino e veloce a X opz. Un tale schema per l'enumerazione dei punti, chiamato il metodo del simplesso, suggerito da R. Danzig.
I vertici sono caratterizzati da m variabili di base, pertanto il passaggio da un vertice a quello vicino può essere effettuato modificando nella base una sola variabile di base in una variabile dalla non base.
L'implementazione del metodo del simplesso, a causa di varie caratteristiche e formulazioni dei problemi di LP, ha varie modifiche.
La costruzione delle tabelle simplex continua fino ad ottenere una soluzione ottimale. Come utilizzare una tabella simplex per determinare che la soluzione a un problema di programmazione lineare è ottimale?
Se l'ultima riga (valori della funzione obiettivo) non contiene elementi negativi, troverà il piano ottimale.
Osservazione 1. Se una delle variabili di base è uguale a zero, allora il punto estremo corrispondente a tale soluzione di base è degenere. La degenerazione si verifica quando c'è ambiguità nella scelta di una linea guida. Potresti non notare affatto la degenerazione del problema se scegli un'altra linea come guida. In caso di ambiguità, selezionare la riga con l'indice più basso per evitare il loop.
Osservazione 2. Supponiamo che in un punto estremo tutte le differenze del simplesso siano non negative D k ³ 0 (k = 1..n + m), cioè. si ottiene una soluzione ottima, ed esiste un vettore А k - non base per il quale D k = 0. Allora il massimo è raggiunto almeno in due punti, cioè esiste un ottimo alternativo. Se introduciamo questa variabile x k nella base, il valore della funzione obiettivo non cambierà.
Osservazione 3. La soluzione al problema duale si trova nell'ultima tabella simplex. Le ultime m componenti del vettore delle differenze del simplesso (nelle colonne delle variabili di bilancio) sono la soluzione ottima del problema duale. I valori delle funzioni obiettivo dei problemi diretti e duali nei punti ottimali coincidono.
Nota 4. Quando si risolve il problema di minimizzazione, viene introdotto nella base un vettore con la più grande differenza positiva del simplesso. Inoltre, viene applicato lo stesso algoritmo del problema di massimizzazione.
Se la condizione "È necessario che la materia prima del III tipo sia stata consumata completamente", la condizione corrispondente è l'uguaglianza.
Problemi di programmazione lineare. È in una struttura sequenziale che caratterizza il processo in esame. La soluzione si articola in tre fasi principali: la scelta delle variabili, la costruzione di un sistema di vincoli e la ricerca della funzione obiettivo.
Sulla base di questa divisione, la condizione del problema può essere riformulata come segue: l'estremo della funzione obiettivo Z (X) = f (x1, x2, ..., xn) → max (min) e le variabili corrispondenti, se è noto che soddisfano il sistema di vincoli: Φ_i ( x1, x2,…, xn) = 0 per i = 1, 2,…, k; Φ_i (x1, x2,…, xn)) 0 per i = k + 1 , k + 2,…, m.
Il sistema delle restrizioni deve essere ricondotto alla forma canonica, cioè. a un sistema di equazioni lineari, dove il numero di variabili è maggiore del numero di equazioni (m> k). In questo sistema ci saranno sicuramente variabili che possono essere espresse in termini di altre variabili e, se così non fosse, allora possono essere introdotte artificialmente. In questo caso, i primi sono chiamati base o base artificiale e i secondi sono chiamati liberi.
È più conveniente considerare il metodo del simplesso utilizzando un esempio specifico. Sia data una funzione lineare f (x) = 6x1 + 5x2 + 9x3 e un sistema di vincoli: 5x1 + 2x2 + 3x3 ≤ 25; x1 + 6x2 + 2x3 ≤ 20; 4x1 + 3x3 ≤ 18. Occorre trovare la valore massimo della funzione f (x).
Soluzione Nella prima fase, specificare la soluzione iniziale (supporto) del sistema di equazioni in modo assolutamente arbitrario, che deve soddisfare il sistema di vincoli dato. In questo caso, è richiesta l'introduzione di uno artificiale, ad es. variabili di base x4, x5 e x6 come segue: 5x1 + 2x2 + 3x3 + x4 = 25; x1 + 6x2 + 2x3 + x5 = 20; 4x1 + 3x3 + x6 = 18.
Come puoi vedere, le disuguaglianze sono state convertite in uguaglianze grazie alle variabili aggiunte x4, x5, x6, che sono valori non negativi. Quindi, hai portato il sistema alla forma canonica. La variabile x4 appare nella prima equazione con un coefficiente di 1 e in due - con un coefficiente di 0, lo stesso vale per le variabili x5, x6 e le equazioni corrispondenti, che corrisponde alla definizione della base.
Hai preparato il sistema e trovato la soluzione di supporto iniziale - X0 = (0, 0, 0, 25, 20, 18). Presentare ora i coefficienti delle variabili ei termini liberi delle equazioni (i numeri a destra del segno "=") sotto forma di tabella per ottimizzare ulteriori calcoli (vedi Fig.).
L'essenza del metodo simplex è portare questa tabella in una forma in cui tutte le cifre nella riga L saranno valori non negativi. Se risulta che ciò è impossibile, il sistema non ha affatto una soluzione ottimale. Innanzitutto, seleziona l'elemento più piccolo di questa linea, questo è -9. Il numero è nella terza colonna. Converti la corrispondente variabile x3 in quella base. Per fare ciò, dividi la linea per 3 per ottenere 1 nella cella.
Ora hai bisogno che le celle tornino a 0. Per fare ciò, sottrai dalle cifre corrispondenti della terza riga per 3. Dagli elementi della seconda riga - gli elementi della terza, moltiplicati per 2. E, infine, dal elementi della linea L - moltiplicati per (-9). Hai ottenuto la seconda soluzione di riferimento: f (x) = L = 54 a x1 = (0, 0, 6, 7, 8, 0).
