Un esempio di risoluzione di problemi diretti e duali con il metodo del simplesso. Metodo del simplesso per risolvere problemi di programmazione lineare Programmazione lineare utilizzando il metodo del simplesso

Metodo del simplesso per risolvere problemi di programmazione lineare

1. Introduzione. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .3 pagine

2. Metodo del simplesso per la risoluzione di problemi di programmazione lineare. ... ... 4-10 pagine

3. Algoritmo del metodo del simplesso per la risoluzione di problemi di programmazione lineare. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .11 pagine

4. Un esempio di risoluzione di un problema utilizzando il metodo del simplesso. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 11-15 pagine

5. conclusione. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .16 pagine

6. Elenco della letteratura utilizzata. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .17 pag.

1. Introduzione

Il lavoro è dedicato al metodo più comune per risolvere un problema di programmazione lineare (metodo simplex). Il metodo del simplesso è il metodo classico e più sviluppato nella programmazione lineare. Consente, in un numero finito di passaggi, di trovare la soluzione ottima o di stabilire che non esiste una soluzione ottima.

Viene formulato un algoritmo per risolvere il problema, che è illustrato da un esempio.

1. Indica un modo per trovare la soluzione di supporto ottimale

2. Indicare il metodo di transizione da una soluzione di supporto all'altra, in corrispondenza del quale il valore della funzione obiettivo sarà più vicino a quello ottimale, es. indicare un modo per migliorare la soluzione di riferimento

3. Impostare i criteri che consentono di interrompere tempestivamente la ricerca di soluzioni di supporto sulla soluzione ottimale o seguire la conclusione sull'assenza di una soluzione ottimale.

2. Metodo del simplesso per risolvere problemi di programmazione lineare sono

Il metodo simplex per risolvere problemi di programmazione lineare (metodo simplex) è una procedura computazionale basata sul principio del miglioramento sequenziale delle soluzioni - il passaggio da un punto base a un altro, per il quale il valore della funzione obiettivo è maggiore (queste operazioni sono registrate in una tabella simplex).

Questo metodo è un metodo di enumerazione mirata delle soluzioni di supporto di un problema di programmazione lineare. Consente, in un numero finito di passaggi, di trovare la soluzione ottima o di stabilire che non esiste una soluzione ottima. È dimostrato che se esiste una soluzione ottima, allora sarà necessariamente trovata dopo un numero finito di passaggi (tranne il cosiddetto problema degenere, in cui è possibile il fenomeno del "looping", cioè ritorno multiplo nella stessa posizione ).

Il metodo del simplesso è fondamentale per la programmazione lineare. La soluzione del problema inizia considerando uno dei vertici del poliedro delle condizioni. Se il vertice in esame non corrisponde al massimo (minimo), vai a quello vicino, aumentando il valore della funzione obiettivo quando risolvi il problema al massimo e diminuendolo quando risolvi il problema al minimo. Pertanto, il passaggio da un vertice all'altro migliora il valore della funzione obiettivo. Poiché il numero di vertici del politopo è limitato, allora in un numero finito di passi è garantito trovare il valore ottimale o stabilire il fatto che il problema è irrisolvibile.

Questo metodo è universale, applicabile a qualsiasi problema di programmazione lineare in forma canonica. Il sistema di vincoli qui è un sistema di equazioni lineari in cui il numero di incognite è maggiore del numero di equazioni. Se il rango del sistema è r, allora possiamo scegliere r incognite, che esprimiamo in termini di incognite rimanenti. Per certezze, assumiamo di aver selezionato le prime incognite consecutive X1, X2, ..., Xr. Allora il nostro sistema di equazioni può essere scritto come

Qualsiasi sistema articolare può essere ridotto a questa forma, ad esempio, con il metodo di Gauss. È vero, non è sempre possibile esprimere in termini delle restanti prime r incognite (l'abbiamo fatto per definire la notazione). Tuttavia, ci saranno sicuramente tali incognite. Queste incognite (variabili) sono chiamate di base, le altre sono libere.

Assegnando determinati valori alle variabili libere e calcolando i valori di quelle di base (espresse in termini di quelle libere), otterremo varie soluzioni al nostro sistema di vincoli. Quindi, qualsiasi soluzione può essere ottenuta. Saremo interessati a soluzioni speciali ottenute nel caso in cui le variabili libere siano uguali a zero. Tali soluzioni sono dette di base, esistono lo stesso numero di diversi tipi di base di un dato sistema di vincoli. Una soluzione di base è chiamata soluzione di base ammissibile o soluzione di supporto se i valori delle variabili in essa contenuti non sono negativi. Se le variabili X1, X2, ..., Xr sono prese come base, allora la soluzione (b1, b2, ..., br, 0, ..., 0) sarà supportata, a condizione che b1, b2 , ... , br ≥ 0.

Il metodo del simplesso si basa su un teorema chiamato teorema fondamentale del metodo del simplesso. Tra i piani ottimi per un problema di programmazione lineare in forma canonica, c'è necessariamente una soluzione di supporto al suo sistema di vincoli. Se il piano ottimale del problema è unico, coincide con una soluzione di supporto. Esistono un numero finito di diverse soluzioni di supporto del sistema di vincoli. Pertanto, la soluzione del problema nella forma canonica potrebbe essere ricercata enumerando le soluzioni di supporto e scegliendo tra queste quella per la quale il valore di F è maggiore. Ma, in primo luogo, tutte le soluzioni di supporto sono sconosciute e devono essere trovate, e, in secondo luogo, nei problemi reali ci sono molte di queste soluzioni e l'enumerazione diretta è difficilmente possibile. Il metodo simplex è una determinata procedura per l'enumerazione diretta delle soluzioni di supporto. Sulla base di alcune soluzioni di supporto precedentemente trovate utilizzando un determinato algoritmo del metodo del simplesso, calcoliamo una nuova soluzione di supporto, su cui il valore della funzione obiettivo F non è inferiore a quello vecchio. Dopo una serie di passaggi, arriviamo a una soluzione di riferimento, che è il piano ottimale.

Quindi, il metodo del simplesso introduce un certo ordine sia quando si trova la prima soluzione di base (originale), sia quando si passa ad altre soluzioni di base.

L'implementazione della soluzione al problema con il metodo del simplesso è chiaramente mostrata nello schema a blocchi (Fig. 1).

Pertanto, l'applicazione del metodo del simplesso si articola in due fasi: trovare una soluzione di base ammissibile ad un sistema di vincoli o accertare il fatto della sua incompatibilità; trovare la soluzione ottimale. Inoltre, ogni fase può includere diversi passaggi corrispondenti all'una o all'altra soluzione di base. Ma poiché il numero di soluzioni di base è sempre limitato, anche il numero di passaggi del metodo del simplesso è limitato.

Lo schema sopra del metodo simplex esprime chiaramente la sua natura algoritmica (la natura di una chiara prescrizione per l'esecuzione di operazioni sequenziali), che consente di programmare e implementare con successo questo metodo su un computer. I problemi con un numero ridotto di variabili e vincoli possono essere risolti manualmente utilizzando il metodo del simplesso.

Descriviamo il suo lato computazionale. I calcoli con il metodo del simplesso sono organizzati sotto forma di tabelle del simplesso, che sono una notazione abbreviata di un problema di programmazione lineare in forma canonica. Prima di compilare una tabella simplex, il problema deve essere trasformato, il sistema di restrizioni ridotto a una forma base ammissibile, con l'aiuto della quale le variabili di base devono essere escluse dalla funzione obiettivo. Considereremo di seguito la questione di queste trasformazioni preliminari. Ora supponiamo che siano già stati completati e che l'attività sia simile a:

Qui, per determinatezza di notazione, si assume che le variabili X1, X2, ..., Xr possano essere prese come variabili di base e che b1, b2, ..., br ≥ 0 (la corrispondente soluzione di base è il riferimento uno).

Per compilare una tabella simplex in tutte le uguaglianze nell'enunciato del problema, i termini contenenti le variabili vengono trasferiti a sinistra, quelli liberi a destra, ad es. il problema si scrive sotto forma di sistema di uguaglianze:

Nota. I nomi delle variabili di base qui sono presi solo per motivi di definizione del record e in una tabella reale potrebbero risultare diversi.

La procedura per lavorare con una tabella simplex. La prima tabella simplex subisce una trasformazione, la cui essenza è il passaggio a una nuova soluzione di riferimento.

L'algoritmo per passare alla tabella successiva è il seguente:

viene scansionata l'ultima riga della tabella (indice) e tra i coefficienti di questa riga (esclusa la colonna dei membri liberi) viene selezionato il numero negativo più piccolo quando si trova il max, o il numero positivo più grande quando si trova il min. Se non ce n'è, allora la soluzione di base originale è ottimale e questa tabella è l'ultima;

viene scansionata la colonna della tabella corrispondente al coefficiente negativo (positivo) selezionato nell'ultima riga - la colonna chiave e i coefficienti positivi vengono selezionati in questa colonna. Se non ce ne sono, allora la funzione obiettivo è illimitata nell'intervallo dei valori ammissibili delle variabili e il problema non ha soluzioni;

tra i coefficienti selezionati della colonna viene selezionato quello per cui il valore assoluto del rapporto tra l'asta libera corrispondente (situata nella colonna delle aste libere) e questo elemento è minimo. Questo coefficiente è chiamato risoluzione e la linea in cui si trova è la chiave;

Per la produzione di tre tipi di camicie vengono utilizzati fili, bottoni e tessuto. Le scorte di fili, bottoni e tessuti, i loro tassi di consumo per cucire una camicia sono mostrati nella tabella. Trova il massimo profitto e il piano di rilascio del prodotto ottimale che lo assicura (trova).

camicia 1

camicia 2

camicia 3

Azioni

filo (m)

1

9

3

96

bottoni (pz.)

20

10

30

640

il panno (

1

2

2

44

Profitto (pag.)

2

5

4

La soluzione del problema

Costruire il modello

Attraverso e il numero di maglie del 1°, 2° e 3° tipo, destinate al rilascio.

Quindi i vincoli delle risorse saranno simili a questo:

Inoltre, ai sensi del problema

Funzione obiettivo che esprime il profitto ottenuto:

Otteniamo il seguente problema di programmazione lineare:

Ridurre un problema di programmazione lineare alla forma canonica

Portiamo il problema in forma canonica. Introduciamo ulteriori variabili. Introduciamo tutte le variabili aggiuntive nella funzione obiettivo con un coefficiente uguale a zero. Aggiungiamo ulteriori variabili ai lati sinistro dei vincoli che non hanno una forma preferita e otteniamo le uguaglianze.

Risolvere il problema usando il metodo del simplesso

Compiliamo la tabella simplex:

Poiché risolviamo il problema di massimo, la presenza di numeri negativi nella riga dell'indice quando si risolve il problema di massimo indica che non abbiamo ottenuto una soluzione ottima e che è necessario passare dalla tabella della 0a iterazione a quella successiva.

Il passaggio all'iterazione successiva viene eseguito come segue:

corrispondenze della colonna principale

La riga chiave è determinata dal rapporto minimo tra membri liberi e membri della colonna principale (relazioni semplici):

All'intersezione della colonna chiave e della riga chiave, troviamo l'elemento risolutivo, ad es. nove.

Ora iniziamo a disegnare la prima iterazione: invece di un vettore unitario, inseriamo un vettore.

Nella nuova tabella, al posto dell'elemento risolutivo, scriviamo 1, tutti gli altri elementi della colonna chiave vengono azzerati. Gli elementi della linea chiave sono suddivisi in elementi di autorizzazione. Tutti gli altri elementi della tabella vengono calcolati secondo la regola del rettangolo.

Colonna chiave per le corrispondenze della prima iterazione

Gli elementi permissivi sono il numero 4/3. Deduciamo il vettore dalla base e inseriamo invece il vettore. Otteniamo la tabella della seconda iterazione.

Colonna chiave per le corrispondenze della seconda iterazione

Troviamo la stringa chiave, per questo definiamo:

L'elemento risolutivo è il numero 10/3. Deduciamo il vettore dalla base e inseriamo invece il vettore. Otteniamo la tabella della terza iterazione.

№

BP

c B

un o

x 1

x 2

x 3

x 4

x 5

x 6

Simplex

2

5

4

0

0

0

relazione

0

x 4

0

96

1

9

3

1

0

0

32/3

x 5

0

640

20

10

30

0

1

0

64

x 6

0

44

1

2

2

0

0

1

22

Fa j - do j

0

-2

-5

-4

0

0

0

1

x 2

5

32/3

1/9

1

1/3

1/9

0

0

32

x 5

0

1600/3

170/9

0

80/3

-10/9

1

0

20

x 6

0

68/3

7/9

0

4/3

-2/9

0

1

17

Fa j - do j

160/3

-13/9

0

-7/3

5/9

0

0

2

x 2

5

5

-1/12

1

0

1/6

0

-1/4

--

x 5

0

80

10/3

0

0

10/3

1

-20

24

x 3

4

17

7/12

0

1

-1/6

0

3/4

204/7

Fa j - do j

93

-1/12

0

0

1/6

0

7/4

3

x 2

5

7

0

1

0

1/4

1/40

-3/4

x 1

2

24

1

0

0

1

3/10

-6

x 3

4

3

0

0

1

-3/4

-7/40

17/4

Fa j - do j

95

0

0

0

1/4

1/40

5/4

Tutti i termini nella riga dell'indice sono non negativi, quindi si ottiene la seguente soluzione al problema di programmazione lineare (la scriviamo dalla colonna dei termini liberi):

È necessario cucire 24 camicie di tipo 1, 7 camicie di tipo 2 e 3 camicie di tipo 3. In questo caso, il profitto risultante sarà massimo e ammonterà a 95 rubli.

... 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

Tavolo simplex originale

				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 rilevato il segno di incompatibilità del sistema di restrizioni (segno 1) (cioè non esiste una riga con un numero libero negativo (tranne la riga della funzione obiettivo), che non non contenere almeno un elemento negativo (es. coefficiente negativo in corrispondenza di una variabile libera)).

A questa iterazione (nella 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), in cui non ci sarebbe 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". Da tali colonne si seleziona 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 stimati positivi dei numeri liberi rispetto agli elementi della colonna permettendo, la linea, che corrisponde al rapporto stimato positivo più piccolo, è presa come consentita.

Tabella 5.4

Tavolo simplex originale

Nella tabella 5.4, il rapporto stimato positivo più piccolo corrisponde alla riga “ x5”, Pertanto, sarà permissivo.

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 che si trova 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 risolutiva della tabella 5.4 per l'elemento risolutivo di questa tabella simplex, i risultati si adattano alle celle simili della nuova tabella simplex (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 simplex (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 dei restanti elementi della tabella simplex (cioè elementi non situati nella riga risolutiva e nella colonna risolvente) viene eseguita secondo la regola del "rettangolo".

Ad esempio, considera la trasformazione di un elemento situato all'intersezione della stringa " x3"E la colonna" ", la designeremo convenzionalmente come" x3". Nella tabella 5.4, disegna mentalmente un rettangolo, un vertice del quale 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, è stata 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, per 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 simplex.

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 l'attributo 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 simplex.

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 minimizzata:

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.

Uno dei metodi per risolvere problemi di ottimizzazione ( solitamente associato alla ricerca di un minimo o di un massimo) si chiama programmazione lineare. Metodo del simplesso include un intero gruppo di algoritmi e metodi per risolvere problemi di programmazione lineare. Uno di tali metodi, che prevede la registrazione dei dati iniziali e il loro ricalcolo in un'apposita tabella, si chiama metodo tabulare simplex.

Considera l'algoritmo del metodo tabulare del simplesso usando l'esempio della soluzione compito di produzione, che si riduce alla ricerca di un piano di produzione che fornisca il massimo profitto.

Dati iniziali del problema per il metodo del simplesso

L'impresa produce 4 tipi di prodotti, elaborandoli su 3 macchine.

Tempi (min./pezzo) Per lavorazione prodotti su macchine, impostati dalla matrice A:

Il fondo del tempo di funzionamento della macchina (min.) è specificato nella matrice B:

Il profitto dalla vendita di ciascuna unità del prodotto (rubli / pezzo) è dato dalla matrice C:

Lo scopo dell'attività di produzione

Elaborare un piano di produzione in cui il profitto dell'impresa sarà massimo.

Risolvere il problema con il metodo tabular simplex

(1) Indichiamo X1, X2, X3, X4 la quantità pianificata di prodotti di ogni tipo. Quindi il piano desiderato: ( X1, X2, X3, X4)

(2) Scriviamo i vincoli del piano sotto forma di un sistema di equazioni:

(3) Quindi il profitto target:

Cioè, il profitto dall'adempimento del piano di produzione dovrebbe essere massimizzato.

(4) Per risolvere il problema risultante per un estremo condizionale, sostituiamo il sistema di disequazioni con un sistema di equazioni lineari introducendovi ulteriori variabili non negative ( X5, X6, X7).

(5) Prendiamo quanto segue piano di base:

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) Inseriamo i dati in tabella simplex:

Nell'ultima riga inseriamo i coefficienti della funzione obiettivo e il suo valore stesso con segno opposto;

(7) Selezioniamo nell'ultima riga il più grande (modulo) un numero negativo.

calcoliamo b = N / Elementi_colonna_selezionati

Tra i valori calcolati di b, scegli meno.

L'intersezione della colonna e della riga selezionate ci darà un elemento di autorizzazione. Sostituiamo la base con la variabile corrispondente all'elemento risolvente ( Da X5 a X1).

• L'elemento risolutivo stesso diventa 1.
• Per gli elementi della retta risolvente - a ij (*) = a ij / RE ( cioè, ogni elemento è diviso per il valore dell'elemento risolvente e otteniamo nuovi dati).
• Per gli elementi di colonna permissivi, vengono semplicemente azzerati.
• Il resto degli elementi della tabella viene ricalcolato in base alla regola del rettangolo.

a ij (*) = a ij - (A * B / RE)

Come puoi vedere, stiamo prendendo la cella corrente da ricalcolare e la cella con l'elemento di risoluzione. Formano gli angoli opposti del rettangolo. Successivamente, moltiplichiamo i valori dalle celle degli altri 2 angoli di questo rettangolo. Questo lavoro ( UN * B) è diviso per l'elemento risolvente ( RIF). E sottrarre dalla cella attualmente ricalcolata ( un ij) cosa è successo. Otteniamo un nuovo valore - a ij (*).

(9) Controlla di nuovo l'ultima riga ( C) Su presenza di numeri negativi... Se non ci sono, è stato trovato il piano ottimale, si procede all'ultima fase di risoluzione del problema. In caso affermativo, il piano non è ancora ottimale e la tabella simplex deve essere ricalcolata nuovamente.

Poiché abbiamo di nuovo numeri negativi nell'ultima riga, iniziamo una nuova iterazione dei calcoli.

(10) Non essendoci elementi negativi nell'ultima riga, questo significa che abbiamo trovato il piano di produzione ottimale! Vale a dire: produrremo quei prodotti che sono passati nella colonna "Base" - X1 e X2. Conosciamo il profitto dalla produzione di ogni unità di produzione ( matrice C). Resta da moltiplicare i volumi di produzione trovati dei prodotti 1 e 2 con un profitto per 1 pezzo, otteniamo il finale ( massimo! ) profitto per un determinato piano di produzione.

RISPONDERE:

X1 = 32 pezzi, X2 = 20 pezzi, X3 = 0 pezzi, X4 = 0 pezzi.

P = 48 * 32 + 33 * 20 = 2 196 rubli.

Galyautdinov R.R.

© La copia del materiale è consentita solo se esiste un collegamento ipertestuale diretto a

È necessario risolvere un problema di programmazione lineare.

Funzione obiettivo:

2x 1 + 5x 2 + 3x 3 + 8x 4 → min

Condizioni limite:

3x 1 + 6x 2 -4x 3 + x 4 ≤12
4x 1 -13x 2 + 10x 3 + 5x 4 ≥6
3x 1 + 7x 2 + x 3 ≥1

Portiamo il sistema delle restrizioni alla forma canonica, per questo è necessario passare dalle diseguaglianze alle uguaglianze, con l'aggiunta di ulteriori variabili.

Poiché la nostra attività è un'attività di minimizzazione, dobbiamo trasformarla in un'attività di ricerca massima. Per fare ciò, cambiamo i segni dei coefficienti della funzione obiettivo al contrario. Scriviamo gli elementi della prima disuguaglianza invariati, aggiungendo un'ulteriore variabile x 5 e cambiando il segno "≤" in "=". Poiché la seconda e la terza diseguaglianza hanno segni "≥", è necessario cambiare i segni dei loro coefficienti al contrario e aggiungere ulteriori variabili x 6 e x 7, rispettivamente. Di conseguenza, otteniamo un problema equivalente:

3x 1 + 6x 2 -4x 3 + x 4 + x 5 = 12
-4x 1 + 13x 2 -10x 3 -5x 4 + x 6 = -6
-3x 1 -7x 2 -x 3 + x 7 = -1

Passiamo alla formazione della tavola simplex originale. Nella riga F della tabella vengono inseriti i coefficienti della funzione obiettivo di segno opposto.

					Membro gratuito
F
X5
X6
X7

Nella tabella che abbiamo compilato, ci sono elementi negativi nella colonna dei membri liberi, tra questi troviamo il massimo in valore assoluto - questo è un elemento: -6, imposta la riga principale - X6. In questa riga troviamo anche il massimo elemento negativo in valore assoluto: -10 è nella colonna X3, che sarà la colonna iniziale. La variabile nella riga principale è esclusa dalla base e la variabile corrispondente alla colonna principale è inclusa nella base. Ricalcoliamo la tabella del simplesso:

	X1	X2	X6	X4	Membro gratuito
F	0.8	8.9	0.3	6.5	-1.8
X5	4.6	0.8	-0.4	3	14.4
X3	0.4	-1.3	-0.1	0.5	0.6
X7	-2.6	-8.3	-0.1	0.5	-0.4

Nella tabella che abbiamo compilato, ci sono elementi negativi nella colonna dei membri liberi, tra questi troviamo il massimo in valore assoluto - questo è un elemento: -0.4, imposta la riga principale - X7. In questa riga troviamo anche il massimo elemento negativo in valore assoluto: -8.3 è nella colonna X2, che sarà la colonna iniziale. La variabile nella riga principale è esclusa dalla base e la variabile corrispondente alla colonna principale è inclusa nella base. Ricalcoliamo la tabella del simplesso:

	X1	X7	X6	X4	Membro gratuito
F	-1.988	1.072	0.193	7.036	-2.229
X5	4.349	0.096	-0.41	3.048	14.361
X3	0.807	-0.157	-0.084	0.422	0.663
X2	0.313	-0.12	0.012	-0.06	0.048

Non essendoci elementi negativi nella colonna dei termini liberi, si è trovata una soluzione ammissibile, nella riga F sono presenti elementi negativi, il che significa che la soluzione ottenuta non è ottimale. Definiamo la colonna principale. Per fare ciò, troviamo nella riga F l'elemento negativo massimo in valore assoluto - questo è -1,988 La riga principale sarà quella per la quale il rapporto tra il membro libero e l'elemento corrispondente della colonna principale è minimo. La riga principale è X2 e l'elemento principale è 0,313.

	X2	X7	X6	X4	Membro gratuito
F	6.351	0.31	0.269	6.655	-1.924
X5	-13.895	1.763	-0.577	3.882	13.694
X3	-2.578	0.152	-0.115	0.577	0.539
X1	3.195	-0.383	0.038	-0.192	0.153

Poiché non ci sono elementi negativi nella stringa F, allora
è stata trovata una soluzione ottimale. Poiché il problema originario era trovare il minimo, la soluzione ottima sarà il termine libero della stringa F, preso con il segno opposto. F = 1.924
con i valori delle variabili uguali: x 3 = 0,539, x 1 = 0,153. Le variabili x 2 e x 4 non sono incluse nella base, quindi x 2 = 0 x 4 = 0.