Soluzione di tabelle simplex online in dettaglio. Esempio di soluzione del problema

11.4. DOPPIO METODO SEMPLICE

Dai risultati delle sezioni precedenti consegue che per ottenere una soluzione al problema originario, si può passare a quello duale e, utilizzando stime del suo disegno ottimo, determinare la soluzione ottima al problema originario.

Il passaggio al problema duale non è necessario, poiché se consideriamo il primo tableau simplex con unità di base addizionale, allora è facile vedere che le colonne contengono il problema originale e il problema duale è scritto nelle righe.

Come è stato mostrato, quando si risolve il problema diretto a qualsiasi iterazione, la differenza, cioè. grandezza -coefficiente con una variabile, è uguale alla differenza tra i lati destro e sinistro del corrispondente vincolo del problema duale. Se, quando si risolve un problema diretto con una funzione obiettivo massimizzabile, l'iterazione non porta a una soluzione ottimale, almeno per una variabile e solo nell'ottimo per tutte differenza.

Considerando questa condizione tenendo conto della dualità, possiamo scrivere

.

Quindi, se, poi . Ciò significa che quando la soluzione al problema primario non è ottimale, la soluzione al problema duale non è valida. D'altro canto a . Ciò implica che la soluzione ottima del problema primario corrisponda ad una soluzione ammissibile del problema duale.

Ciò ha permesso di sviluppare un nuovo metodo per risolvere problemi di programmazione lineare, quando si utilizza il quale, inizialmente, si ottiene una soluzione inaccettabile, ma "migliore dell'ottimale" (nel solito metodo del simplesso, prima ammissibile, ma subottimale soluzione). Un nuovo metodo chiamato metodo dual simplex, assicura il soddisfacimento della condizione di ottimalità della soluzione e la sua sistematica "approssimazione" all'area delle soluzioni fattibili. Quando la soluzione ottenuta risulta ammissibile, il processo iterativo di calcoli termina, poiché anche questa soluzione è ottimale.

Il metodo dual simplex permette di risolvere problemi di programmazione lineare i cui sistemi di vincoli, con base positiva, contengono termini liberi di qualsiasi segno. Questo metodo consente di ridurre il numero di trasformazioni del sistema di vincoli e la dimensione della tabella simplex. Si consideri l'applicazione del metodo dual simplex utilizzando un esempio.

Esempio. Trova il minimo di una funzione

sotto restrizioni

.

Passiamo alla forma canonica:

sotto restrizioni

Il tableau simplex iniziale ha la forma

Di base variabili	X 1	X 2	X 3	X 4	X 5	Soluzione
X 3 X 4 X 5	–3 –4	–1 –3				–3 –6
	–2	–1

Soluzione di base inizialeottimale, ma non accettabile.

Come il solito metodo simplex, il metodo risolutivo in esame si basa sull'uso di condizioni di ammissibilità e ottimalità.

Condizione di ammissibilità. La più grande variabile di base negativa in valore assoluto viene scelta come variabile esclusa (se ci sono alternative, la scelta viene fatta arbitrariamente). Se tutte le variabili di base sono non negative, il processo di calcolo termina, poiché la soluzione risultante è fattibile e ottima.

Condizione ottimalità. La variabile inclusa nella base viene selezionata tra le variabili non di base come segue. Vengono calcolati i rapporti dei coefficienti del lato sinistro-equazioni ai corrispondenti coefficienti dell'equazione associata alla variabile esclusa. Non vengono prese in considerazione le relazioni con denominatore positivo o nullo. Nel problema di minimizzazione della variabile di input deve corrispondere il più piccolo dei rapporti indicati, e nel problema di massimizzazione, il rapporto con il valore assoluto più piccolo (se ci sono alternative la scelta è arbitraria). Se i denominatori di tutti i rapporti sono zero o positivi, il problema non ha soluzioni ammissibili.

Dopo aver scelto le variabili da includere nella base e da escludere, si esegue la consueta operazione di trasformare le righe della tabella simplex per ottenere la soluzione successiva.

In questo esempio, la variabile esclusa è. I rapporti calcolati per determinare la nuova variabile di base sono riportati nella tabella seguente:

Variabili	X 1	X 2	X 3	X 4	X 5
L'equazione X 4 - equazione	–2 –4	–1 –3
Atteggiamento

La variabile da includere è X 2. La successiva conversione di stringhe risulta in una nuova tabella simplex:

Di base variabili	X 1	X 2	X 3	X 4	X 5	Soluzione
X 3 X 2 X 5						–1 –1

Nuova soluzione anche ottimale, ma ancora non valido. Come nuova variabile esclusa, scegliamo (arbitrariamente) X 3. Definiamo una variabile inclusa.

Variabili	X 1	X 2	X 3	X 4	X 5
L'equazione X 4 - equazione
atteggiamento

Metodo Simplex - questo è un metodo di transizione successiva da una soluzione di base (il vertice del poliedro della soluzione) del sistema di vincoli di un problema di programmazione lineare ad un'altra soluzione di base fino a quando la funzione obiettivo assume il valore ottimo (massimo o minimo).

Il metodo simplex è un metodo universale che può risolvere qualsiasi cosa problema di programmazione lineare, mentre il metodo grafico è adatto solo per un sistema di vincoli a due variabili.

Il metodo simplex è stato proposto dal matematico americano R. Danzig nel 1947, da allora, per le esigenze dell'industria, questo metodo risolve spesso problemi di programmazione lineare con migliaia di variabili e vincoli.

Prima di passare all'algoritmo del metodo simplex, alcune definizioni.

Viene chiamata qualsiasi soluzione non negativa di un sistema di vincoli soluzione accettabile .

Che ci sia un sistema m restrizioni da n variabili ( m n).

Soluzione di base ammissibile è una soluzione contenente m non negativo principale (di base ) variabili e n - m non core . (non di base, o gratuito ) variabili. Le variabili non di base nella soluzione di base sono uguali a zero, mentre le variabili principali, di regola, sono diverse da zero, ovvero sono numeri positivi.

Qualunque m variabili di sistema m equazioni lineari con n vengono chiamate le variabili principale , se il determinante dei coefficienti a loro è diverso da zero. Poi il resto n - m vengono chiamate le variabili non core (o gratuito ).

Algoritmo del metodo Simplex

• Passo 1. Portare il problema della programmazione lineare nella forma canonica. Per fare ciò, sposta i termini liberi sul lato destro (se tra questi termini liberi sono negativi, moltiplica l'equazione o la disuguaglianza corrispondente per - 1) e introduci variabili aggiuntive in ogni vincolo (con un segno più, se nel disuguaglianza originale il segno è minore o uguale a ", e con un segno meno se "maggiore o uguale a").
• Passo 2. Se nel sistema risultante m equazioni, quindi m prendi le variabili come principali, esprimi le principali in termini di quelle non di base e trova la corrispondente soluzione di base. Se la soluzione di base trovata risulta ammissibile, passare alla soluzione di base ammissibile.
• Passaggio 3. Esprimere la funzione obiettivo in termini di variabili minori della soluzione di base ammissibile. Se viene trovato il massimo (minimo) della forma lineare e non ci sono variabili non di base con coefficienti negativi (positivi) nella sua espressione, allora il criterio di ottimalità è soddisfatto e la soluzione di base risultante è ottima - la soluzione è finita. Se, quando si trova il massimo (minimo) di una forma lineare, la sua espressione contiene una o più variabili non fondamentali con coefficienti negativi (positivi), passare a una nuova soluzione di base.
• Passaggio 4. Tra le variabili non basilari incluse nella forma lineare con coefficienti negativi (positivi), scegliere quella che corrisponde al coefficiente (modulo) maggiore e trasferirla su quelle principali. Vai al passaggio 2.

Condizioni importanti

Alcuni casi speciali sono discussi in articoli separati: quando funzione obiettivo massimo - infinito, quando il sistema non ha soluzione, e quando la soluzione ottimale non è l'unica .

Successivamente, analizzeremo un esempio tipico, quando il sistema di vincoli è coerente e c'è un ottimo finito, e solo uno. Una variazione del metodo simplex è metodo di distribuzione per risolvere il problema del trasporto .

Metodo Simplex con tabelle simplex

Costruendo tabelle simplex, è molto più facile risolvere un problema di programmazione lineare che con trasformazioni algebriche, come mostrato nel prossimo paragrafo. I tavoli Simplex sono molto visivi. Esistono diversi tipi di regole per lavorare con le tabelle simplex. Analizzeremo la regola, che viene spesso chiamata regola della colonna iniziale e della riga iniziale.

Sarebbe utile aprire il manuale Azioni con le frazioni in una nuova finestra: ce ne sono abbastanza, frazioni nei problemi sul metodo simplex, per usare un eufemismo.

Esempio.

Introduciamo ulteriori variabili non negative e riduciamo questo sistema di disuguaglianze a un sistema di equazioni equivalente

.

Ciò è stato fatto rispettando la seguente regola: se il segno nel vincolo originario è "minore o uguale a", allora deve essere aggiunta la variabile addizionale, e se "maggiore o uguale a", allora la variabile addizionale deve essere sottratto.

Le variabili aggiuntive introdotte vengono prese come principali (di base). Quindi e sono variabili non di base (libere).

Esprimendo le variabili principali (di base) in termini di non di base (libere), otteniamo

Esprimiamo anche la funzione obiettivo in termini di variabili non di base (libere):

Dai coefficienti delle variabili (incognite) costruiamo il primo tableau simplex.

Tabella 1
Incognite di base	Membri gratuiti	Incognite sciolte		Coefficienti ausiliari
		X1	X2
X3	-2	1	-2
X4	-4	-1	-1
X5	2	1	-1
X6	6	0	1
F	0	-1	-2

L'ultima riga della tabella, che contiene la funzione obiettivo e i coefficienti delle variabili libere in essa, sarà chiamata riga dell'indice.

La soluzione risultante non è ottimale, poiché i coefficienti delle variabili libere nella riga dell'indice sono negativi. Cioè, la soluzione ottimale sarà quella in cui i coefficienti delle variabili libere nella riga dell'indice saranno maggiori o uguali a zero.

Per passare alla tabella successiva, trova il più grande (modulo) dei numeri e . Questo numero è 2. Pertanto, la colonna iniziale è la colonna in cui è scritto

Per determinare la riga iniziale, troviamo il minimo dei rapporti tra i membri liberi e gli elementi della colonna iniziale, e se il numeratore ha un numero positivo e il denominatore è negativo, il rapporto è considerato uguale all'infinito.

.

Pertanto, la riga principale è quella in cui è scritto

L'elemento principale è quindi -2.

Componiamo la seconda tabella simplex.

Inseriamo il nuovo elemento di base nella prima riga e entriamo nella colonna in cui si trovava, inseriamo una nuova variabile libera

Compila la prima riga. Per fare ciò, dividiamo tutti i numeri nella riga iniziale della tabella 1 per l'elemento iniziale e lo scriviamo nella colonna corrispondente della prima riga della tabella 2, ad eccezione del numero nella colonna iniziale, dove il reciproco dell'iniziale viene scritto l'elemento (cioè uno diviso per l'elemento principale).

Completa la colonna dei coefficienti ausiliari. Per questo numero della colonna iniziale della tabella 1, oltre all'elemento iniziale, scriviamo con segni opposti nella colonna dei coefficienti ausiliari della tabella 2.

Tavolo 2
Incognite di base	Membri gratuiti	Incognite sciolte		Coefficienti ausiliari
		X1	X3
X2	1	-1/2	-1/2
X4	-3	-3/2	-1/2	1
X5	3	1/2	-1/2	1
X6	5	1/2	1/2	-1
F	2	-2	-1	2

Chi non ha ancora aperto in una nuova finestra il manuale Azioni con le frazioni, può farlo ora, perché è il momento.

Per ottenere le righe rimanenti della tabella 2, i numeri già nella prima riga di questa tabella vengono moltiplicati per il coefficiente ausiliario nella riga da riempire, e al risultato si aggiunge il numero della tabella 1, che è nella stessa riga con la variabile corrispondente.

Ad esempio, per ottenere il membro gratuito della seconda riga, moltiplichiamo il numero 1 per 1 e aggiungiamo il numero -4 dalla tabella 1. Otteniamo -3. Troviamo il coefficiente per nella seconda riga allo stesso modo: . Poiché nella tabella precedente non è presente una colonna con una nuova variabile libera, il coefficiente della seconda riga nella colonna della nuova variabile libera sarà (ovvero, dalla tabella 1 aggiungiamo 0, poiché non esiste una colonna c nella tabella 1).

La riga dell'indice è compilata allo stesso modo:

La soluzione così ottenuta è ancora una volta non ottimale, in quanto i coefficienti delle variabili libere nella riga dell'indice sono nuovamente negativi.

Per passare alla prossima tabella simplex, troviamo il più grande (modulo) dei numeri e, cioè i moduli dei coefficienti nella linea dell'indice. Questo numero è 2. Pertanto, la colonna iniziale è la colonna che contiene .

Per cercare la riga principale, troviamo il rapporto minimo tra i membri liberi e gli elementi della riga principale. Noi abbiamo:

.

Pertanto, la riga principale è quella in cui è scritto e l'elemento principale è -3/2.

Compilazione della terza tabella simplex

Scriviamo la nuova variabile di base nella prima riga. Nella colonna in cui si trovava, inseriamo una nuova variabile libera.

Prima linea:

Coefficienti ausiliari:

Tabella 3
Incognite di base	Membri gratuiti	Incognite sciolte		Coefficienti ausiliari
		X4	X3
X1	2	-2/3	1/3
X2	2	-1/3	-1/3	1/2
X5	2	1/3	-2/3	-1/2
X6	4	1/3	1/3	-1/2
F	6	-4/3	-1/3	2

La soluzione risultante non è di nuovo ottimale, poiché i coefficienti delle incognite libere nella riga dell'indice sono di nuovo negativi.

Per andare alla quarta tabella simplex, troviamo il più grande dei numeri e . Questo è un numero.

Pertanto, la colonna principale è quella con .

Modulo minimo delle relazioni dei membri liberi con gli elementi della colonna principale:

.

Pertanto, la riga principale è quella in cui è scritto e l'elemento principale è 1/3.

Nella quarta tabella simplex, scriviamo la nuova variabile di base nella prima riga. Nella colonna in cui si trovava, scriviamo una nuova variabile libera.

Prima linea:

Coefficienti ausiliari:

Tabella 4
Incognite di base	Membri gratuiti	Incognite sciolte		Coefficienti ausiliari
		X5	X3
X4	6	3	-2
X1	6	2	-1	2/3
X2	4	1	-1	1/3
X6	2	-1	1	-1/3
F	14	4	-3	4/3

Calcolo delle righe rimanenti utilizzando l'esempio della seconda riga:

Anche la soluzione risultante non è ottimale, ma è già migliore delle precedenti, poiché uno dei coefficienti per variabili libere nella riga dell'indice non è negativo.

Per migliorare il piano, passiamo al prossimo tableau simplex.

Trova il più grande dei numeri 4 e . Questo numero è 4. Pertanto, la colonna iniziale è .

Per trovare la riga principale, trova

.

Pertanto, la linea guida è quella che contiene . Ma erano già insieme tra le variabili libere. Pertanto, per trasferire la variabile successiva da libera a base, selezioniamo un'altra colonna iniziale, quella in cui è scritta.

Per trovare la riga principale, trova

.

Pertanto, la riga chiave è quella in cui è scritto e l'elemento principale è 1.

Nella quinta tabella simplex, la nuova variabile di base è scritta nella prima riga. Nella colonna in cui si trovava, scriviamo una nuova variabile libera.

Prima linea:

Coefficienti ausiliari:

Tabella 5
Incognite di base	Membri gratuiti	Incognite sciolte		Coefficienti ausiliari
		X5	X6
X3	2	-1	1
X4	10			2
X1	8			1
X2	6			1
F	20	1	3	3

Proviamo a scoprire subito se la soluzione non è ottimale. Pertanto, per le righe rimanenti, calcoliamo solo i termini liberi (per scoprire i valori delle variabili di base quando le variabili libere sono pari a zero) e i coefficienti per le variabili libere nella riga dell'indice.

Membri gratuiti:

Nella seconda riga;

Nella terza riga;

Sulla quarta riga.

Riga dell'indice:

Osserviamo la tabella simplex 5. Vediamo che è stata ottenuta la soluzione ottima, poiché i coefficienti per le incognite libere nella riga dell'indice non sono negativi.

Metodo Simplex con trasformazioni algebriche

Risolviamo per trasformazioni algebriche lo stesso esempio del paragrafo precedente. Va notato che quando si risolve questo tipo di metodo simplex, è meglio non scrivere la funzione obiettivo nel modulo , poiché è facile confondersi nei segni. Ma in questo caso, il punto dell'algoritmo che determina il criterio di ottimalità verrà modificato come segue.

Se si trova il massimo (minimo) della forma lineare e non ci sono variabili non di base con coefficienti positivi (negativi) nella sua espressione, allora il criterio di ottimalità è soddisfatto e la soluzione di base risultante è ottima - la soluzione è finita. Se, quando si trova il massimo (minimo) di una forma lineare, la sua espressione contiene una o più variabili non fondamentali con coefficienti positivi (negativi), passare a una nuova soluzione di base.

Esempio. Trova il massimo di una funzione sotto vincoli

Passaggio I. Introduciamo ulteriori variabili non negative e riduciamo questo sistema di disuguaglianze a un sistema di equazioni equivalente

.

Le variabili aggiuntive introdotte vengono prese come principali, poiché in questo caso la soluzione di base del sistema è facilmente reperibile. Quindi e sono variabili minori.

Esprimendo le variabili principali in termini di quelle non di base, otteniamo

Di conseguenza, questa divisione delle variabili in base e non di base corrisponde alla soluzione di base , che non è valido (due variabili sono negative) e quindi non ottimale. Passiamo da questa soluzione di base a una migliorata.

Per decidere quale variabile deve essere trasferita da non principale a principale, si consideri una delle due equazioni disponibili dell'ultimo sistema con termini liberi negativi, ad esempio la seconda. Mostra che e possono essere tradotti nelle variabili principali, poiché in questa equazione hanno coefficienti positivi (quindi, quando aumentano, e questo accadrà se traduciamo una di esse nelle variabili principali, la variabile aumenterà).

Proviamo a tradurre nella variabile principale. Per determinare quale variabile deve essere trasferita dalla principale alla non base, troviamo il valore assoluto del rapporto più piccolo tra i membri liberi del sistema e i coefficienti a . Abbiamo . Si ottiene dalla terza equazione, che mostra che la variabile deve essere convertita in non di base, che è positiva nella soluzione di base originale. Di conseguenza, la soluzione di base ottenuta, come quella originale, contiene due componenti negative, ovvero non ci sarà alcun miglioramento nel passaggio a tale soluzione di base.

Metodo Simplex− è un metodo di enumerazione ordinata dei piani di riferimento (l'ordinamento è assicurato da una variazione monotona del valore della funzione obiettivo durante il passaggio al piano successivo). In questo caso è necessario osservare il principio: ogni passo successivo dovrebbe migliorare o, in casi estremi, non peggiorare il valore della funzione obiettivo.

Per risolvere il LLP metodo simplex si riduce alla forma canonica, cioè da restrizioni - disuguaglianze è necessario fare restrizioni - uguaglianze. Per fare ciò, ogni vincolo viene integrato con un ulteriore non negativo variabile di bilancio con il segno “+” se il segno di disuguaglianza è “£”, e con il segno “–” se il segno di disuguaglianza è “³”.

Nella funzione obiettivo, queste variabili aggiuntive entrano con coefficienti zero, cioè la voce della funzione di destinazione non cambierà. Ogni variabile che non è soggetta alla condizione di non negatività può essere rappresentata come la differenza di due variabili non negative: .

Se i vincoli delle attività riflettono la presenza e il consumo di risorse, il valore numerico della variabile aggiuntiva nel piano delle attività, scritto in forma canonica, è uguale alla quantità di risorsa inutilizzata.

Per risolvere il problema con il metodo simplex, useremo tabelle simplex abbreviate di un sistema di equazioni lineari e il metodo di eliminazione di Jordan modificato.

1. Elaboriamo il primo piano di base

Il compito rimane lo stesso. Portiamo la forma standard del sistema di disequazioni (1) nella forma canonica del sistema di equazioni introducendo variabili di bilancio addizionali X 3 , X 4 , X 5 ,X 6 .

In senso economico, i valori delle variabili aggiuntive X 3 , X 4 , X 5 determinare il saldo delle materie prime dopo la vendita dei prodotti.

La matrice del sistema di equazioni risultante ha la forma:

Si può vedere che nella matrice UN la base minore del 4° ordine è il determinante, composto da coefficienti unitari per variabili addizionali X 3 , X 4 , X 5 ,X 6, poiché è diverso da zero e uguale a 1. Ciò significa che i vettori colonna per queste variabili sono linearmente indipendenti, cioè modulo base, e le variabili corrispondenti X 3 , X 4 , X 5 ,X 6 sono di base(di base). Variabili X 1 , X 2 sarà chiamato gratuito(minore).

Se variabili libere X 1 e X 2 di impostare valori diversi, quindi, risolvendo il sistema rispetto alle variabili di base, otteniamo un insieme infinito di soluzioni particolari. Se vengono impostati solo valori zero per variabili libere, da un insieme infinito di soluzioni particolari, soluzioni di base- piani di base.

Per scoprire se le variabili possono essere di base, è necessario calcolare il determinante costituito dai coefficienti di queste variabili. Se questo determinante non è uguale a zero, allora queste variabili possono essere di base.

Il numero di soluzioni di base e il corrispondente numero di gruppi di variabili di base non può essere superiore a , dove nè il numero totale di variabili, rè il numero di variabili di base, r≤ m≤ n.

Per il nostro compito r = 4; n= 6. Allora , cioè Sono possibili 15 gruppi di 4 variabili di base (o 15 soluzioni di base).

Risolviamo il sistema di equazioni rispetto alle variabili di base X 3 , X 4 , X 5 ,X 6:

Supponendo che le variabili libere X 1 = 0, X 2 = 0, otteniamo i valori delle variabili di base: X 3 = 312; X 4 = 15; X 5 = 24;X 6 = -10, cioè la soluzione di base sarà = (0; 0; 312; 15; 24; -10).

Questa soluzione di base è inaccettabile, perché X 6 = –10 ≤ 0, e dalla condizione di vincolo X 6 ≥ 0. Pertanto, al posto della variabile X 6 come base, devi prendere un'altra variabile tra le libere X 1 o X 2 .

Effettueremo l'ulteriore soluzione utilizzando tabelle simplex abbreviate, compilando le righe della prima tabella con i coefficienti del sistema come segue (Tabella 1):

Tabella 1

F- viene chiamata la stringa indice. È riempito con coefficienti di funzione oggettivi presi con segni opposti, poiché l'equazione della funzione può essere rappresentata come F = 0 – (– 4X 1 – 3X 2).

Nella colonna dei membri liberi b io c'è un elemento negativo b 4 = -10, cioè la soluzione del sistema non è valida. Per ottenere una soluzione valida (piano di base), l'elemento b 4 deve essere reso non negativo.

Scegliere X 6 - una riga con un membro libero negativo. Questa riga contiene elementi negativi. Scegline uno qualsiasi, ad esempio "-1" in X 1 -colonna, e X 1 - colonna accetta come colonna di autorizzazione(determinerà che la variabile X 1 passerà da gratuito a base).

Condividiamo membri gratuiti b io sugli elementi rilevanti un è colonna risolutiva, otteniamo relazioni valutativeΘ io==(24, 15, 12, 10). Di questi, scegliamo il più piccolo positivo (minΘ io=10), che corrisponderà a linea di autorizzazione. La stringa di autorizzazione definisce una variabile xj, che al passo successivo sporge dalla base e diventa libero. Ecco perchè X 6 -line è una linea permissiva e l'elemento "-1" lo è elemento abilitante. Lo circondiamo. Variabili X 1 e X 6 vengono scambiati.

Rapporti stimati Θ io in ogni riga sono determinati dalle regole:

1) Θ io= se b io e un è avere segni diversi;

2) Θ io= ∞ se b io= 0 e un è < 0;

3) Θ io= ∞ se un è = 0;

4) Θ io= 0 se b io= 0 e un è > 0;

5) Θ io= se b io e un è hanno gli stessi segni.

Facciamo il passaggio dell'eliminazione giordana modificata (MJJI) con un elemento permissivo e compiliamo una nuova tabella (Tabella 2) secondo la seguente regola:

1) al posto dell'elemento risolutivo (RE) viene impostato un valore, il suo inverso, cioè ;

2) gli elementi della linea permissiva sono suddivisi in RE;

3) gli elementi della colonna risolutiva sono suddivisi in RE e il segno cambia;

4) gli elementi rimanenti si trovano secondo la regola del rettangolo:

Dal tavolo. 2 mostra che i membri liberi in b io-le colonne non sono negative, quindi si ottiene la soluzione iniziale ammissibile - primo piano di base= (10; 0; 182; 5; 4; 0). In questo caso, il valore della funzione F() = 40. Geometricamente, corrisponde alla parte superiore F(10; 0) poligono di soluzione (Fig. 1).

Tavolo 2

2. Controlliamo l'ottimalità del piano. Il piano di base non è ottimale, perché in F-line ha un coefficiente negativo "-4". Miglioriamo il piano.

3. Trovare una nuova linea di base

Selezioniamo l'elemento che consente secondo la regola:

Scegliamo il coefficiente negativo più piccolo in F-riga "-4", che determina la colonna di abilitazione - X 6; variabile X 6 tradurre in base;

Troviamo i rapporti Θ io, tra questi scegliamo il più piccolo positivo, che corrisponde alla stringa permissiva:

min Θ io = min(14, 5, 2, ∞) = 2, quindi X 5 - riga - permissiva, variabile X 5 traduciamo in libero (variabili X 5 e X 6 vengono scambiati).

All'intersezione della riga e della colonna permissive si trova l'elemento permissivo "2";

Eseguiamo il passaggio SHMZhI, costruiamo il tavolo. 3 secondo la regola precedente e ottenere un nuovo piano di riferimento = (12; 0; 156; 3; 0; 2).

Tabella 3

4. Verifica dell'ottimalità del nuovo piano di base

Anche il piano di base non è ottimale, poiché in F-line ha un coefficiente negativo "-1". Valore della funzione F() = 48, che corrisponde geometricamente alla parte superiore e(12; 0) poligono di soluzione (Fig. 1). Miglioriamo il piano.

5. Trovare una nuova linea di base

X La colonna 2 è permissiva, poiché in F-line in cui si trova il coefficiente negativo più piccolo "-1". X 2 colonne (Δ 2 = -1). Trovare la Θ più piccola io: min Θ io = min(≈ 9, 6, ∞, 24) = 6, quindi X 4a riga - permissiva. Elemento permissivo "1/2". Scambio di variabili X 2 e X quattro . Eseguiamo il passaggio SHMZhI, costruiamo il tavolo. 4, otteniamo un nuovo piano di riferimento = (9; 6; 51; 0; 0; 5).

6. Verifica dell'ottimalità del piano di base

A F-line, tutti i coefficienti sono non negativi, quindi il piano di riferimento è ottimale. Geometricamente corrisponde a un punto D(9;6) (vedi Fig. 1). Il piano ottimo dà il valore massimo della funzione obiettivo c.u.

Principale l'idea di un metodo simplex per risolvere l'LLP consiste nel miglioramento costante delle soluzioni di supporto LLP.

Esistono diversi modi per scrivere il metodo simplex.

1. La forma base del metodo simplex;
2. Metodo Simplex sotto forma di tabella simplex;
3. Metodo simplex modificato;
4. Metodo Simplex in forma colonnare;
5. Metodo Simplex in forma di riga.

Definiamo il valore massimo della funzione obiettivo F(X) = 3x 1 +5x 2 +4x 3 nelle seguenti condizioni di vincolo.
0,1x 1 +0,2x 2 +0,4x 3 ≤1100
0,05x 1 +0,02x 2 +0,02x 3 ≤120
3x1 +x2 +2x3 ≤8000

Per costruire il primo piano di riferimento, riduciamo il sistema delle disuguaglianze a un sistema di equazioni introducendo variabili aggiuntive (transizione alla forma canonica).
0,1x1 + 0,2x2 + 0,4x3 + 1x4 + 0x5 + 0x6 = 1100
0,05x1 + 0,02x2 + 0,02x3 + 0x4 + 1x5 + 0x6 = 120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 8000

Notazione di base del metodo simplex

La soluzione si effettua esprimendo le variabili di base attraverso quelle non di base: x0 = 3x1 +5x2 +4x3 x 4 = 1100-0,1x 1 -0,2x 2 -0,4x 3 x 5 = 120-0,05x 1 -0,02x 2 -0,02x 3 x 6 = 8000-3x 1 -x 2 -2x 3

Metodo Simplex sotto forma di tabella simplex

La soluzione viene eseguita sotto forma di una tabella simplex. Il modulo è progettato per l'elaborazione su un computer. Quando si utilizza una base artificiale, viene utilizzato un numero speciale M (di solito 10000).

Piano	Base	A	x 1	x2	x 3	x4	x5	x6	min
1	x4	1100	0.1	0.2	0.4	1	0	0	5500
	x5	120	0.05	0.02	0.02	0	1	0	6000
	x6	8000	3	1	2	0	0	1	8000
Riga dell'indice	F(X1)	0	-3	-5	-4	0	0	0	0
2	x2	5500	0.5	1	2	5	0	0	11000
	x5	10	0.04	0	-0.02	-0.1	1	0	250
	x6	2500	2.5	0	0	-5	0	1	1000
Riga dell'indice	F(X2)	27500	-0.5	0	6	25	0	0	0
3	x2	5375	0	1	2.25	6.25	-12.5	0	11000
	x1	250	1	0	-0.5	-2.5	25	0	250
	x6	1875	0	0	1.25	1.25	-62.5	1	1000
Riga dell'indice	F(X3)	27625	0	0	5.75	23.75	12.5	0	0

Metodo simplex modificato

Matrice dei coefficienti A = a ij Matrice b. Iterazione #1. = (4, 5, 6) Matrice c. c = (-3, -5, -4, 0, 0, 0) c B = (0, 0, 0) c N = (-3, -5, -4) Calcoliamo: La matrice B -1 è calcolata mediante addizioni algebriche. u = c B B -1 = (0, 0, 0)

Metodo Simplex in forma colonnare

Passiamo alla forma colonnare del metodo simplex. Esprimiamo ogni variabile in termini di variabili non di base. x 0 = 0-3(-x 1)-5(-x 2)-4(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 1 = 0-1(-x 1)+0(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 2 = 0+0(-x 1)-1(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 3 = 0+0(-x 1)+0(-x 2)-1(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 4 = 1100+0,1(-x 1)+0,2(-x 2)+0,4(-x 3)+1(-x 4)+0(-x 5)+0(-x 6) x 5 = 120+0,05(-x 1)+0,02(-x 2)+0,02(-x 3)+0(-x 4)+1(-x 5)+0(-x 6) x 6 = 8000+3(-x 1)+1(-x 2)+2(-x 3)+0(-x 4)+0(-x 5)+1(-x 6) Questo sistema corrisponde alla tabella T 0 . 0 -1 0 0 0 0 -1 0 0 0 0 -1 1100 0.1 0.2 0.4 120 0.05 0.02 0.02 8000 3 1 2 0 -3 -5 -4

Metodo Simplex in forma di stringa

Come base iniziale ammissibile, possiamo assumere B 0 =<4, 5, 6>. Corrisponderà alla tabella seguente. 1100 0.1 0.2 0.4 1 0 0 120 0.05 0.02 0.02 0 1 0 8000 3 1 2 0 0 1 0 -3 -5 -4 0 0 0

Viene chiamata la matrice Q, composta dai coefficienti del sistema tavola semplice corrispondente alla base B. Viene chiamato un tableau simplex ammissibile, o direttamente ammissibile, se q i0 ≥ 0. Si chiamano gli elementi q i0 dell'ultima riga della tabella simplex Q stime relative.

Forme di soluzione con il metodo della base artificiale

Per l'uso di variabili artificiali introdotte nella funzione obiettivo, viene imposta una cosiddetta penalità di M, un numero positivo molto grande, che di solito non è specificato.
La base risultante è chiamata artificiale e il metodo della soluzione è chiamato metodo della base artificiale.
Inoltre, le variabili artificiali non sono correlate al contenuto dell'attività, ma consentono di costruire un punto di partenza e il processo di ottimizzazione costringe queste variabili ad assumere valori zero e garantire l'ammissibilità della soluzione ottimale.

Forme di soluzione con il metodo della base artificiale:

1. Metodo M (tabella semplice);
2. metodo del simplesso a due o due fasi (notazione di base, metodo del simplesso modificato, metodo del simplesso in forma di colonna, metodo del simplesso in forma di linea).

Se ci sono restrizioni con il segno ≥ nella condizione del problema, allora possono essere ridotte alla forma ∑a ji b j moltiplicando entrambe le parti della disuguaglianza per -1. Introduciamo m variabili aggiuntive x n+j ≥0(j =1,m ) e trasformiamo i vincoli nella forma delle uguaglianze

(2)

Assumiamo che tutte le variabili iniziali del problema x 1 , x 2 ,..., x n siano non basilari. Quindi le variabili aggiuntive saranno di base e una soluzione particolare al sistema di vincoli avrà la forma

x 1 = x 2 = ... = x n = 0, x n+ j = b j , j = 1, m . (3)

Poiché in questo caso il valore della funzione obiettivo F 0 = 0 , possiamo rappresentare F(x) come segue:

F(x)=∑c io x io + F 0 =0 (4)

La tabella simplex iniziale (tabella simplex 1) è compilata sulla base delle equazioni (2) e (4). Se le variabili aggiuntive x n+j sono precedute dal segno “+”, come in (2), allora tutti i coefficienti prima delle variabili x i e del termine libero b j vengono inseriti nella tabella simplex senza modifiche. I coefficienti della funzione obiettivo durante la sua massimizzazione sono inseriti nella riga inferiore della tabella simplex con segni opposti. I membri liberi nella tabella simplex determinano la soluzione del problema.

L'algoritmo per risolvere il problema è il seguente:

1° passo. Gli elementi della colonna dei membri gratuiti vengono cercati. Se sono tutti positivi, allora è stata trovata una soluzione di base accettabile e si dovrebbe procedere al passaggio 5 dell'algoritmo, che corrisponde alla ricerca della soluzione ottimale. Se sono presenti termini liberi negativi nel tableau simplex iniziale, la soluzione non è valida e dovresti andare al passaggio 2.

2° passo. Per trovare una soluzione fattibile, si procede, mentre è necessario decidere quale delle variabili non base includere nella base e quale variabile prelevare dalla base.

Tabella 1.

x n

variabili di base	Membri gratuiti con restrizioni	Variabili non di base
		x 1	x2	...	x l	...
xn+1	b 1	un 11	un 12	...	un 1 l	...	un 1n
xn+2	b 2	un 21	un 22	...	un 2l	...	un 2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
xn+r	b2	un r1	un r2	...	a rl	...	un rn
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
xn+m	bm	un m1	un m2	...	un ml	...	amn
F(x)max	F0	-c 1	-c 2	...	-c 1	...	-c n

Per fare ciò, scegli uno qualsiasi degli elementi negativi della colonna dei membri liberi (lascia che sia b 2 iniziale o consentito. Se non ci sono elementi negativi nella riga con un membro libero negativo, il sistema di restrizioni è incoerente e il problema non ha soluzione.

Allo stesso tempo, viene esclusa dalla BP la variabile che per prima cambia segno con un aumento del NP x l selezionato. Questo sarà x n+r , il cui indice r è determinato dalla condizione

quelli. la variabile che corrisponde al rapporto più piccolo tra il termine libero e l'elemento della colonna iniziale selezionata. Questa relazione si chiama relazione simplex. Dovrebbero essere considerate solo relazioni simplex positive.

Viene chiamata la stringa corrispondente alla variabile x n+r guidare o permettere. L'elemento della tabella simplex a rl , che si trova all'intersezione della riga iniziale e della colonna iniziale, è chiamato elemento iniziale o risolutivo. Trovare l'elemento principale termina il lavoro con ogni successivo tableau simplex.

3° passaggio. Viene calcolata una nuova tabella simplex, i cui elementi vengono ricalcolati dagli elementi della tabella simplex del passaggio precedente e contrassegnati con un primo, ad es. b" j , a" ji , c" i , F" 0 . Gli elementi vengono ricalcolati secondo le seguenti formule:

Innanzitutto, la riga e la colonna che erano all'inizio della precedente tabella simplex verranno riempite nella nuova tabella simplex. L'espressione (5) significa che l'elemento a "rl al posto dell'elemento principale è uguale al reciproco dell'elemento della tabella simplex precedente. Gli elementi della riga a ri sono divisi dall'elemento principale e gli elementi della le colonne a jl sono anch'esse divise per l'elemento principale, ma sono prese con segno opposto Gli elementi b" r e c" l sono calcolati secondo lo stesso principio.

Il resto delle formule può essere facilmente scritto usando .

Il rettangolo è costruito secondo la vecchia tabella simplex in modo tale che una delle sue diagonali sia formata dagli elementi ricalcolati (a ji) e iniziali (a rl) (Fig. 1). La seconda diagonale è determinata in modo univoco. Per trovare un nuovo elemento a "ji, il prodotto di elementi della diagonale opposta, diviso per l'elemento principale, viene sottratto dall'elemento a ji (questo è indicato dal segno" - "alla cella). Allo stesso modo, gli elementi b" j, (j≠r) e c" i vengono ricalcolati, (i≠l).

4° passo. L'analisi di una nuova tabella simplex parte dal 1° passaggio dell'algoritmo. L'azione continua fino a quando non viene trovata una soluzione di base praticabile, ad es. tutti gli elementi della colonna dei membri gratuiti devono essere positivi.

5° passo. Riteniamo che sia stata trovata una soluzione di base accettabile. Osserviamo i coefficienti della retta della funzione obiettivo F(x) . Un segno dell'ottimalità di una tabella simplex è la non negatività dei coefficienti per variabili non di base nella riga F.

Riso. 1. Regola del rettangolo

Se tra i coefficienti della riga F ci sono quelli negativi (ad eccezione del termine libero), è necessario passare a un'altra soluzione di base. Quando si massimizza la funzione obiettivo, la base include quella delle variabili non di base (ad esempio x l), la cui colonna corrisponde al valore assoluto massimo del coefficiente negativo c l nella riga inferiore della tabella simplex. Questo permette di selezionare la variabile il cui incremento porta ad un miglioramento della funzione obiettivo. La colonna corrispondente alla variabile x l è chiamata colonna iniziale. Contestualmente è esclusa dalla base quella variabile x n+r il cui indice r è determinato dal rapporto minimo di simplesso:

La riga corrispondente a x n+r è chiamata riga iniziale e l'elemento della tabella simplex a rl , che si trova all'intersezione della riga iniziale e della colonna iniziale, è chiamato elemento guida.

6° passo. secondo le regole del 3° passaggio. La procedura continua fino a quando non si trova una soluzione ottimale o si conclude che non esiste.

Se nel processo di ottimizzazione della soluzione nella colonna iniziale tutti gli elementi sono non positivi, non è possibile selezionare la riga iniziale. In questo caso, la funzione nel dominio delle soluzioni ammissibili del problema non è limitata dall'alto e F max ->&∞.

Se al passo successivo della ricerca di un estremo una delle variabili di base diventa uguale a zero, allora la corrispondente soluzione di base è detta degenerata. In questo caso si verifica il cosiddetto looping, caratterizzato dal fatto che la stessa combinazione di BP inizia a ripetersi con una certa frequenza (in questo caso viene preservato il valore della funzione F) ed è impossibile passare a una nuova soluzione di base accettabile. Il looping è uno dei principali inconvenienti del metodo simplex, ma è relativamente raro. In pratica, in questi casi, di solito si rifiuta di inserire nella base la variabile la cui colonna corrisponde al valore assoluto massimo del coefficiente negativo nella funzione obiettivo, e si fa la scelta casuale di una nuova soluzione di base.

Esempio 1. Risolvi un problema

max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)

Simplex e dare un'interpretazione geometrica del processo risolutivo.

L'interpretazione grafica della soluzione del problema è mostrata in fig. 2. Il valore massimo della funzione obiettivo viene raggiunto nella parte superiore dell'ODZP con le coordinate . Risolviamo il problema usando le tabelle simplex. Moltiplichiamo il secondo vincolo per (-1) e introduciamo variabili aggiuntive per portare le disuguaglianze nella forma di uguaglianze, quindi

Le variabili iniziali x 1 e x 2 sono considerate non di base e le ulteriori x 3 , x 4 e x 5 sono considerate di base e compiliamo una tabella simplex (tabella simplex 2). La soluzione corrispondente alla tabella simplex. 2, non è valido; l'elemento principale è delineato e selezionato in conformità con il passaggio 2 dell'algoritmo di cui sopra. La prossima scheda simplex. 3 definisce una soluzione di fondo ammissibile; 2 L'elemento principale viene delineato e selezionato in base al 5° passaggio dell'algoritmo per la risoluzione del problema. Tab. 4 corrisponde alla soluzione ottima del problema, quindi: x 1 = x 5 = 0; x 2 \u003d 4; x 3 \u003d 3; x 4 = 8; F max = 20.

Riso. 2. Soluzione grafica del problema