Metodo Simplex nuovo piano base online. Esempio di soluzione del problema

Per consentire l'esecuzione dell'applet sul tuo computer, devi fare quanto segue: fare clic su Start>Pannello di controllo>Programmi>Java. Nella finestra Pannello di controllo Java, seleziona la scheda Sicurezza, fai clic sul pulsante Modifica elenco siti, sul pulsante Aggiungi e incolla il percorso di questa pagina dalla barra degli indirizzi del browser nel campo libero. Quindi, fare clic su OK e quindi riavviare il computer.

Per avviare l'applet, fare clic sul pulsante "Simplex". Se il pulsante "Simplex" non è visibile sopra questa riga, Java non è installato sul tuo computer.

Dopo aver cliccato sul pulsante “Simplex”, appare la prima finestra per inserire il numero di variabili e il numero di vincoli del problema sul metodo del simplesso.

Dopo aver fatto clic sul pulsante "ok", viene visualizzata una finestra per l'inserimento dei dati rimanenti del problema utilizzando il metodo del simplesso: modalità di visualizzazione (frazioni decimali o ordinarie), tipo di compito, criterio min o max, immissione dei coefficienti della funzione obiettivo e coefficienti del sistema di vincoli con i segni “≤”, “ ≥ "o "=", non è necessario introdurre restrizioni della forma x i ≥ 0, ne tiene conto nel suo algoritmo.

Dopo aver fatto clic sul pulsante "Risolvi", viene visualizzata una finestra con i risultati della risoluzione del problema .La finestra è composta da due parti; nella parte superiore è presente un campo di testo contenente la descrizione della riduzione del problema originario alla forma canonica, che serve per compilare la prima tabella simplex. Nella parte inferiore della finestra, in un pannello con schede, sono presenti le tabelle simplex di ciascuna iterazione con un piccolo campo di testo in basso che indica la colonna di risoluzione, la riga di risoluzione e altre informazioni, che rendono il programma addestrabile. Nella scheda con la tabella ottimale (ultima) nel campo di testo viene fornito il risultato soluzione ottimale compiti.

Invia eventuali errori notati e commenti sull'applet a: [e-mail protetta] oppure chiama il numero 8 962 700 77 06, di cui ti saremo molto grati.

Programma con metodo M

Programma per risolvere un problema di trasporto

Ecco una soluzione manuale (non applet) di due problemi utilizzando il metodo del simplesso (simile alla soluzione applet) con spiegazioni dettagliate per comprendere l'algoritmo per la risoluzione dei problemi. Il primo problema contiene solo segni di disuguaglianza “≤” (problema con base iniziale), il secondo può contenere segni “≥”, “≤” o “=" (problema con base artificiale), si risolvono diversamente.

Metodo del simplesso, risoluzione di un problema con una base iniziale

1)Metodo del semplice per un problema con base iniziale (tutti i segni di vincoli di disuguaglianza " ≤ ").

Scriviamo il problema canonico forma, cioè riscriviamo le restrizioni sulla disuguaglianza sotto forma di uguaglianze, aggiungendo bilancio variabili:

Questo sistema è un sistema con una base (base s 1, s 2, s 3, ciascuna di esse è inclusa in una sola equazione del sistema con un coefficiente 1), x 1 e x 2 sono variabili libere. I problemi da risolvere utilizzando il metodo del simplesso devono avere le seguenti due proprietà:
-il sistema di vincoli deve essere un sistema di equazioni con base;
I termini liberi di tutte le equazioni del sistema devono essere non negativi.

Il sistema risultante è un sistema con una base e i suoi termini liberi non sono negativi, quindi è possibile applicare il metodo del simplesso. Creiamo la prima tabella simplex (Iterazione 0), ovvero una tabella dei coefficienti della funzione obiettivo e un sistema di equazioni per le variabili corrispondenti. Qui “BP” indica la colonna delle variabili di base, “Soluzione” indica la colonna dei membri di destra delle equazioni del sistema. La soluzione non è ottimale, perché ci sono coefficienti negativi nella riga z.

iterazione 0

BP	Soluzione	Atteggiamento

Per migliorare la soluzione passiamo all'iterazione successiva e otteniamo la seguente tabella del simplesso. Per fare ciò è necessario selezionare abilita colonna, cioè. una variabile che verrà inclusa nella base alla successiva iterazione. Viene selezionato dal coefficiente negativo assoluto più grande nella riga z (nel problema massimo) - nell'iterazione iniziale questa è la colonna x 2 (coefficiente -6).

Quindi seleziona abilita la stringa, cioè. una variabile che lascerà la base alla successiva iterazione. Viene selezionato dal rapporto più piccolo tra la colonna "Decisione" e i corrispondenti elementi positivi della colonna di risoluzione (colonna "Rapporto") - nell'iterazione iniziale questa è la riga s 3 (coefficiente 20).

Elemento permissivo si trova all'intersezione tra la colonna risolutiva e la riga risolutiva, la sua cella è evidenziata a colori, è uguale a 1. Pertanto, alla successiva iterazione, la variabile x 2 sostituirà s 3 nella base. Si noti che la relazione non viene cercata nella stringa z; lì viene inserito un trattino "-". Se esistono relazioni minime identiche, viene selezionata una qualsiasi di esse. Se tutti i coefficienti nella colonna della risoluzione sono minori o uguali a 0, la soluzione del problema è infinita.

Compiliamo la seguente tabella “Iterazione 1”. Lo otterremo dalla tabella “Iterazione 0”. L'obiettivo di ulteriori trasformazioni è trasformare la colonna della risoluzione x2 in una colonna unitaria (con un uno al posto dell'elemento di risoluzione e zeri al posto degli elementi rimanenti).

1) Calcola la riga x 2 della tabella “Iterazione 1”. Per prima cosa dividiamo tutti i membri della riga risolutiva s 3 della tabella “Iterazione 0” per l’elemento risolutivo (è uguale a 1 in in questo caso) di questa tabella, otteniamo la riga x 2 nella tabella “Iterazioni 1”. Perché l'elemento risolutivo in questo caso è pari a 1, allora la riga s 3 della tabella “Iterazione 0” coinciderà con la riga x 2 della tabella “Iterazione 1”. Riga x 2 della tabella dell'Iterazione 1 abbiamo ottenuto 0 1 0 0 1 20, le rimanenti righe della tabella dell'Iterazione 1 saranno ottenute da questa riga e dalle righe della tabella dell'Iterazione 0 come segue:

2) Calcolo della riga z della tabella “Iterazione 1”. Al posto di -6 nella prima riga (riga z) nella colonna x2 della tabella Iterazione 0, dovrebbe esserci uno 0 nella prima riga della tabella Iterazione 1. Per fare ciò, moltiplichiamo tutti gli elementi della riga x 2 della tabella "Iterazione 1" 0 1 0 0 1 20 per 6, otteniamo 0 6 0 0 6 120 e aggiungiamo questa riga con la prima riga (z - riga) della tabella "Iterazione 0" -4 -6 0 0 0 0, otteniamo -4 0 0 0 6 120. Nella colonna x 2 appare uno zero 0, l'obiettivo è raggiunto. Gli elementi della colonna risoluzione x 2 sono evidenziati in rosso.

3) Calcolo della riga s 1 della tabella “Iterazione 1”. Al posto di 1 nella riga 1 della tabella “Iterazione 0” dovrebbe esserci uno 0 nella tabella “Iterazione 1”. Per fare ciò, moltiplica tutti gli elementi della riga x 2 della tabella "Iterazione 1" 0 1 0 0 1 20 per -1, ottieni 0 -1 0 0 -1 -20 e aggiungi questa riga con s 1 - riga della tabella "Iterazione 0" 2 1 1 0 0 64, otteniamo la riga 2 0 1 0 -1 44. Nella colonna x 2 otteniamo lo 0 richiesto.

4) Calcolare la riga s 2 della tabella “Iterazione 1”. Al posto 3 nella riga 2 della tabella "Iterazione 0" dovrebbe esserci 0 nella tabella "Iterazione 1". Per fare ciò, moltiplica tutti gli elementi della riga x 2 della tabella “Iterazione 1” 0 1 0 0 1 20 per -3, ottieni 0 -3 0 0 -3 -60 e aggiungi questa riga con s 2 - riga della tabella "Iterazione 0" 1 3 0 1 0 72, otteniamo la riga 1 0 0 1 -3 12. Nella colonna x 2, si ottiene lo 0 richiesto. La colonna x 2 nella tabella "Iterazione 1" è diventata un'unità , contiene uno 1 e il resto 0.

Le righe della tabella “Iterazione 1” sono ottenute secondo la seguente regola:

Nuova riga = Vecchia riga – (Coefficiente colonna di risoluzione della riga precedente)*(Nuova riga di risoluzione).

Ad esempio, per una z-string abbiamo:

Vecchia corda z (-4 -6 0 0 0 0)
-(-6)*Nuova riga di risoluzione -(0-6 0 0 -6 -120)
=Nuova stringa z(-4 0 0 0 6 120) .

Per le tabelle seguenti, il ricalcolo degli elementi della tabella avviene in modo simile, quindi lo omettiamo.

iterazione 1

						Soluzione	Atteggiamento

Risolvendo la colonna x 1, risolvendo la riga s 2, s 2 lascia la base, x 1 entra nella base. Esattamente allo stesso modo, otteniamo le rimanenti tabelle del simplesso finché non otteniamo una tabella con tutti i coefficienti positivi nella riga z. Questo è un segno di una tabella ottimale.

Iterazione 2

						Soluzione	Atteggiamento

Risolvendo la colonna s 3, risolvendo la riga s 1, s 1 lascia la base, s 3 entra nella base.

Iterazione 3

						Soluzione	Atteggiamento

Nella riga z, tutti i coefficienti sono non negativi, quindi si ottiene la soluzione ottima x 1 = 24, x 2 = 16, z max = 192.

Metodo del simplesso, risoluzione di un problema con una base artificiale

2) Risolviamo il problema con una base artificiale (almeno un segno di vincolo di disuguaglianza “≥” o “=").

Scriviamo il problema in forma canonica (sotto forma di sistema di equazioni, che richiede il metodo del simplesso), per fare questo introduciamo due variabili x 3 ≥ 0 e x 4 ≥ 0, otteniamo:

Il sistema di restrizioni offre solo una variabile di base consentita x 4, solo che è inclusa in una sola equazione nella terza con un coefficiente pari a 1, quindi aggiungiamo le variabili artificiali R 1 ≥ 0 e R 2 ≥ 0 alla prima e alla seconda equazione affinché il metodo del simplesso possa essere applicato, le equazioni di vincolo del sistema devono essere un sistema con una base, cioè in ogni equazione deve esserci una variabile con coefficiente 1, che è inclusa in una sola equazione del sistema, nel nostro caso sono R 1, R 2 e x 4. Abbiamo ricevuto il cosiddetto M-task:

Questo sistemaè un sistema con una base in cui R 1, R 2 e x 4 sono variabili di base, e x 1, x 2 e x 3 sono variabili libere, i termini liberi di tutte le equazioni sono non negativi. Pertanto, per risolvere il problema è possibile utilizzare il metodo del simplesso. Scriviamo la tabella simplex iniziale:

iterazione 0

	Soluzione	Atteggiamento
-16

Per i problemi con base artificiale è stata aggiunta alla tabella la riga “Valutazione”. Si ottiene sommando i coefficienti corrispondenti di righe con variabili artificiali (R) di segno opposto. Sarà presente nella tabella finché almeno una delle variabili artificiali sarà nella base. In base al coefficiente modulo negativo più grande della riga “Valutazione”, viene determinata la colonna risolutiva mentre è nella tabella. Quando la riga "Valutazione" lascia la tabella (non ci sono variabili artificiali nella base), la colonna risolutiva sarà determinata dalla riga z, come nel problema con la base iniziale. In questa tabella, la colonna risolutiva è x 2, viene selezionata in base al punteggio negativo assoluto più grande (-7). La riga risolutiva R 2 viene selezionata in base al rapporto più piccolo tra la colonna "Soluzione" e i corrispondenti elementi positivi della colonna risolutiva, come nel problema senza variabili artificiali. Ciò significa che alla successiva iterazione la variabile x2 passerà da libera a base, e la variabile R2 passerà da base a libera. Scriviamo la seguente tabella simplex:

Risolvendo la colonna x 1, risolvendo la riga R 1, R 1 lascia la base, x 1 entra nella base. Dopodiché non rimangono variabili artificiali nella base, quindi non c'è alcuna riga "Valutazione" nella tabella seguente:

iterazione 2

							Soluzione	Atteggiamento

Successivamente, la colonna della risoluzione viene selezionata dalla riga z. Nella riga z, tutti i coefficienti sono non negativi tranne il coefficiente per la variabile artificiale R 1, che non influenza l'ottimalità quando le variabili artificiali lasciano la base. Si ottiene di conseguenza la soluzione ottima x 1 = 6/5; x2 = 3/5; z massimo = 72/5.

Casi particolari di utilizzo del metodo del simplesso

1) Quando la retta (se si considera un problema di programmazione lineare bidimensionale, e in generale un iperpiano) che rappresenta la funzione obiettivo è parallela alla retta (iperpiano) corrispondente ad uno dei vincoli di disuguaglianza (che al punto ottimo è soddisfatto come uguaglianza esatta), la funzione obiettivo assume uno ed è anche un valore ottimo in un certo insieme di punti sul confine della regione delle soluzioni ammissibili. Queste soluzioni si chiamano soluzioni ottimali alternative. La presenza di soluzioni alternative può essere determinata utilizzando la tabella simplex ottimale. Se la riga z della tabella ottima contiene coefficienti pari a zero di variabili non di base, allora esistono soluzioni alternative.

2) Se nella colonna risolutiva della tabella del simplesso tutti i coefficienti sono minori o uguali a zero, allora è impossibile selezionare una riga risolutiva, in questo caso la soluzione è illimitata.

3) Se i vincoli di un problema di programmazione lineare sono incoerenti (cioè non possono essere soddisfatti simultaneamente), allora il problema non ha soluzioni ammissibili. Questa situazione non può verificarsi se tutte le disuguaglianze che compongono il sistema di restrizioni sono del tipo “≤” con lati destri non negativi, perché in questo caso, variabili aggiuntive possono costituire una soluzione fattibile. Per altri tipi di vincoli vengono utilizzate variabili artificiali. Se il problema ha una soluzione, allora nella tabella ottimale non ci sono variabili artificiali (R i) nella base. Se sono lì, il problema non ha soluzioni.

Se hai già compreso il metodo grafico per risolvere i problemi di programmazione lineare, è ora di passare a metodo del semplice. A differenza del primo, non ha praticamente alcuna restrizione sul problema (numero qualsiasi di variabili, segni diversi, ecc.) e viene modificato a seconda del tipo di problema (ad esempio, il metodo M o il metodo delle basi artificiali).

Quando si risolve un problema utilizzando il metodo del simplesso, i calcoli vengono solitamente eseguiti (per compattezza e chiarezza) in tabelle (metodo del simplesso tabulare) e l'ultima tabella con la soluzione ottimale contiene importanti informazioni aggiuntive: la soluzione al doppio problema, risorse rimanenti , informazioni su risorse scarse, ecc., che consente un'analisi economica di un problema di programmazione lineare (vedere l'esempio 3 di seguito).

Esempi di soluzioni a problemi utilizzando il metodo del simplesso vengono pubblicati gratuitamente per tua comodità: studia, cerca quelli simili, risolvi. Se hai bisogno di aiuto con attività come questa, vai a: Soluzione di programmazione lineare personalizzata.

Risoluzione di problemi utilizzando il metodo del simplesso: esempi online

Compito 1. L'azienda produce scaffali da bagno in due misure: A e B. Gli agenti di vendita stimano che potrebbero essere venduti sul mercato fino a 550 scaffali a settimana. Ogni ripiano di tipo A richiede 2 m2 di materiale, mentre ogni ripiano di tipo B richiede 3 m2 di materiale. L'azienda può ricevere fino a 1200 mq di materiale a settimana. Per produrre uno scaffale di tipo A sono necessari 12 minuti di tempo macchina e per produrre uno scaffale di tipo B - 30 minuti; La macchina può essere utilizzata 160 ore settimanali. Se il profitto derivante dalla vendita degli scaffali di tipo A è 3 unità monetarie, e dai ripiani tipo B - 4 den. unità, quanti scaffali di ciascun tipo dovrebbero essere prodotti a settimana?

Elaborazione di un modello matematico e risoluzione della ZLP utilizzando il metodo del simplesso (pdf, 33 Kb)

Compito 2. Risolvere un problema di programmazione lineare utilizzando il metodo del simplesso.

Soluzione con il metodo del simplesso con base artificiale (pdf, 45 Kb)

Compito 3. L'azienda produce 3 tipologie di prodotti: A1, A2, A3, utilizzando due tipologie di materie prime. Sono noti i costi di ciascun tipo di materia prima per unità di produzione, le riserve di materie prime per il periodo di pianificazione, nonché il profitto derivante da un'unità di produzione di ciascun tipo.

Quanti articoli di ogni tipo devono essere prodotti per massimizzare il profitto?
Determinare lo stato di ciascun tipo di materia prima e il suo valore specifico.
Determinare l'intervallo massimo per le variazioni delle scorte di ciascuna tipologia di materia prima, entro il quale la struttura del piano ottimale, vale a dire La nomenclatura di produzione non cambierà.
Determinare la quantità di prodotti realizzati e il profitto derivante dalla produzione quando si aumenta lo stock di uno dei tipi scarsi di materie prime al massimo valore possibile (entro un dato intervallo di produzione).
Determinare gli intervalli di variazione del profitto di un'unità di produzione di ciascun tipo in corrispondenza dei quali il piano ottimale risultante non cambierà.

Risolvere un problema di programmazione lineare con analisi economica(pdf, 163KB)

Compito 4. Risolvi un problema di programmazione lineare utilizzando il metodo del simplesso:

Soluzione con il metodo del simplesso tabellare con ricerca della pianta di riferimento (pdf, 44 Kb)

Compito 5. Risolvi un problema di programmazione lineare utilizzando il metodo del simplesso:

Soluzione con il metodo del simplesso tabulare (pdf, 47 Kb)

Compito 6. Risolvi il problema utilizzando il metodo del simplesso, considerando come piano di riferimento iniziale il piano indicato nella condizione:

Soluzione con metodo simplex manuale (pdf, 60 Kb)

Compito 7. Risolvi il problema utilizzando il metodo del simplesso modificato.
Per produrre due tipi di prodotti A e B vengono utilizzati tre tipi di apparecchiature tecnologiche. Per produrre un'unità del prodotto A, le attrezzature del primo tipo impiegano a1=4 ore, le attrezzature del secondo tipo a2=8 ore e le attrezzature del terzo tipo a3=9 ore. Per produrre un'unità del prodotto B, le attrezzature del primo tipo impiegano b1=7 ore, le attrezzature del secondo tipo b2=3 ore e le attrezzature del terzo tipo b3=5 ore.
Le attrezzature del primo tipo possono lavorare per la produzione di questi prodotti per non più di t1=49 ore, le attrezzature del secondo tipo per non più di t2=51 ore, le attrezzature del terzo tipo per non più di t3=45 ore.
Utile dalla vendita di un'unità prodotto finito A è ALPHA = 6 rubli e il prodotto B è BETTA = 5 rubli.
Elabora un piano di produzione per i prodotti A e B, garantendo il massimo profitto dalla loro vendita.

Soluzione utilizzando il metodo del simplesso modificato (pdf, 67 Kb)

Compito 8. Trovare la soluzione ottima utilizzando il metodo del dual simplex

Soluzione con il metodo del dual simplex (pdf, 43 Kb)

Esempi di soluzioni a problemi di programmazione lineare

Metodi per risolvere problemi di programmazione lineare

Soluzioni di riferimento ad un problema di programmazione lineare

Sia dato un problema di programmazione lineare in notazione canonica

a condizioni

Indicheremo con l'insieme delle soluzioni i sistemi (2) – (3). Supponiamo che , dov'è il rango della matrice e è il numero di equazioni nel sistema (2).

Dal sistema di vettori colonna della matrice, selezioniamo un sottosistema di vettori linearmente indipendenti. Esiste perché. Questo sistema costituisce una base in . Indichiamo con , . Chiamiamo insieme di valori fondamentali indice, – sottomatrice di base matrici Chiameremo le coordinate del vettore di base , Se non di base Altrimenti.

Scriviamo il sistema (2) nella forma . Dividiamo i termini sul lato sinistro in basilari e non basilari

Definiamo una soluzione particolare di questo sistema come segue. Impostiamo tutte le variabili non di base uguali a zero in (4). Allora il sistema (4) assumerà la forma

Chiamiamo (5) sottosistema di base sistema di equazioni (2). Denotiamo con un vettore composto dalle coordinate di base del vettore . Allora il sistema (2) può essere riscritto in forma di matrice vettoriale

Poiché la sottomatrice è di base, it

non degenerato. Pertanto il sistema (6) ha un’unica soluzione. La soluzione particolare del sistema (2) così ottenuta verrà chiamata soluzione di riferimento problema di programmazione lineare diretta corrispondente alla base. (A volte viene chiamata anche la soluzione di riferimento di base ). Come possiamo vedere, la base corrisponde ad un'unica soluzione di supporto. Ovviamente, il numero di soluzioni di supporto è finito.

Per questa base, determiniamo anche la soluzione di riferimento al problema della programmazione lineare duale. Ricordiamo che il problema duale rispetto a quello canonico ha la forma

a condizioni

Scriviamo il sistema (8) nella forma

Ricordiamo che l'insieme delle soluzioni del sistema (8) è denotato con .

Definiamo il vettore delle variabili duali dalla condizione di soddisfare i vincoli di base nel sistema (9) come uguaglianze. Otteniamo il seguente sistema di equazioni lineari:

Denotiamo con un vettore composto da ba-

coordinate zis del vettore. Allora il sistema (10) può essere riscritto in forma di matrice vettoriale

Anche il sistema (11) ha un'unica soluzione.

Chiamiamolo supporto (di base )decisione problema di programmazione lineare duale corrispondente alla base. Anche questa soluzione di riferimento è determinata in modo univoco.

Quindi, qualsiasi base corrisponde a due vettori: rispettivamente due soluzioni di supporto e problemi di programmazione lineare diretta e duale.

Definiamo ulteriormente le seguenti tipologie di basi e soluzioni di supporto. Se tutte le coordinate della soluzione di appoggio sono non negative, allora viene chiamata la base a cui corrisponde questa soluzione di appoggio accettabile piano di riferimento problema di programmazione lineare diretta e viene chiamata la soluzione di riferimento corrispondente alla stessa base pseudopiano duplice problema. Infatti, affinché la base sia ammissibile, è sufficiente la non negatività delle coordinate della base. Si noti che il piano di riferimento è un vettore ammissibile del problema di programmazione lineare diretta ().

Se la soluzione di riferimento soddisfa tutte le restrizioni (9) del problema duale, allora la base a cui corrisponde tale soluzione di riferimento è detta doppiamente valido . In questo caso, viene chiamato il vettore piano di riferimento problema di programmazione lineare duale e la soluzione di riferimento corrispondente alla stessa base

è chiamato pseudopiano compito diretto.

Per la doppia ammissibilità di una base è sufficiente soddisfare solo le disuguaglianze non di base. Si noti che il piano di riferimento è un vettore ammissibile del problema di programmazione lineare duale ().

Indichiamo le differenze tra i lati sinistro e destro delle disuguaglianze (9) con , . Allora la duplice ammissibilità di una base può essere stabilita verificando la non negatività di tutti. Si noti che, come segue direttamente dalla definizione, tutti i residui di base sono uguali a zero ().

Un esempio di risoluzione di un problema diretto e duale utilizzando il metodo del simplesso

Pertanto, è sufficiente assicurarsi che le disuguaglianze valgano per tutti.

Teorema 1. PermettereE– soluzioni di riferimento del problema di programmazione lineare corrispondenti ad una certa base, allora vale l'uguaglianza .

Prova . Dalle definizioni delle soluzioni di appoggio è facile ricavare le uguaglianze

da qui la validità del teorema.

Teorema 2. (Criterio di ottimalità delle soluzioni di sostegno) Se baseè contemporaneamente ammissibile e doppiamente ammissibile, quindi le corrispondenti soluzioni di sostegnoEsono soluzioni, rispettivamente, dei problemi di programmazione lineare diretta e duale.

Prova. La validità di questa affermazione deriva dalla teoria della dualità nella programmazione lineare e dal Teorema 1.

Teorema 3. Una soluzione ammissibile del problema (1) – (3) è un piano di riferimento del problema se e solo se è il vertice di un insieme poliedrico convesso.

Prova. Permettere – piano di riferimento del problema (1) – (3). Dimostriamolo – parte superiore del set . Per definizione, un piano di riferimento – soluzione di riferimento ammissibile corrispondente a qualche base, cioè – Risoluzione di un sistema di equazioni lineari rispetto a variabili

È facile vedere che questo sistema ha una soluzione unica. Ciò significa che il piano di appoggio della faccia contiene il punto , ha dimensione 0. Pertanto, – parte superiore del set .

Indietro. Permettere – la parte superiore del set. Dimostriamolo – piano di riferimento del problema (1) – (3). Poiché è un vertice, è una faccia dell'insieme la cui dimensione è zero. Pertanto, il vettore ci sono almeno zero componenti, l'insieme dei cui numeri denotiamo . Così, – l'unica soluzione al sistema

Dove . Resta quindi da dimostrare che il sistema di vettori è linearmente indipendente. Supponiamo il contrario. Poi ci sono numeri che non sono tutti uguali a zero, tali che . Ecco perché

Ciò significa che il sistema (12) ha una soluzione diversa da , il che contraddice l'unicità della sua soluzione. Quindi, è la base e il vettore – il corrispondente piano di riferimento del problema (1) – (3). Questo è ciò che era richiesto.

Si noti che una soluzione ammissibile del problema (7), (8) (il problema duale (1) – (3)) è anche un piano di appoggio se e solo se è il vertice dell'insieme ammissibile.

Data di pubblicazione: 2015-01-10; Leggi: 695 | Violazione del copyright della pagina

Studopedia.org - Studopedia.Org - 2014-2018 (0,005 s)…

Per certezza, assumiamo che il problema da risolvere sia trovare il minimo.

1. Ridurre il problema della programmazione lineare alla forma canonica.

Dopo aver introdotto ulteriori variabili, scriviamo il sistema di equazioni e la funzione lineare in una forma chiamata sistema esteso:

Assumiamo che tutte le variabili aggiuntive abbiano lo stesso segno dei termini liberi; altrimenti usiamo il cosiddetto M– un metodo che verrà discusso di seguito.

2. Definire le variabili base e libere.

3. Inseriamo il sistema esteso originale nella prima tavola simplex. Si chiama l'ultima riga della tabella, che fornisce l'equazione per la funzione obiettivo lineare valutazione. Indica i coefficienti della funzione obiettivo. Nella colonna di sinistra della tabella annotiamo le variabili principali (base), nelle colonne successive annotiamo i coefficienti delle variabili libere. La penultima colonna contiene i membri liberi del sistema esteso. L'ultima colonna è preparata per le relazioni di stima necessarie per determinare la variabile base basata sulla relazione (6.29).

4. Determinare la possibilità di risolvere il problema mediante valori secondo i Teoremi 6.7,…, 6.9.

5. Selezionare l'elemento risolutivo (riferimento).

Risoluzione di un problema di produzione utilizzando il metodo del simplesso tabulare

Se il criterio di ottimalità non è soddisfatto (le condizioni del Teorema 6.7 o 6.8 non sono soddisfatte), allora il coefficiente negativo assoluto più grande nell'ultima riga determina la colonna risolutiva (di riferimento) .

Componiamo i rapporti stimati di ciascuna linea secondo le seguenti regole:

1 0) se tutti e hanno segni diversi;

2 0) se tutti e ;

3 0) se ;

4 0) 0 se e ;

5 0) se e hanno gli stessi segni.

Definiamo. Se non esiste un minimo finale, il problema non ha un ottimo finale (). Se il minimo è finito, seleziona la linea Q, su cui viene raggiunta (qualsiasi, se ce ne sono più), e chiamala linea risolutiva (di riferimento). All'intersezione della riga e della colonna risolutiva c'è un elemento risolutivo (riferimento).

6 0) Vai alla tabella successiva secondo le regole:

a) nella colonna di sinistra scriviamo una nuova base: invece della variabile principale - una variabile, ad es. Scambiamo le variabili e ;

b) metterne 1 al posto dell'elemento di sostegno;

c) lasciare gli elementi della tabella originaria nei restanti posti della riga di riferimento della nuova tabella;

d) nei restanti posti della colonna di riferimento inserire gli elementi corrispondenti della tabella originaria, moltiplicati per –1;

d) per il restante posti liberi elementi , , nella nuova tabella annotare i numeri , , , che si trovano come segue:

Per semplificare i calcoli utilizzando queste formule, possono essere formulate come "Regole del rettangolo"(Fig. 6.8): si moltiplicano gli elementi sulle diagonali di un rettangolo con vertici (o , , , , o , , , ) (il prodotto che non contiene l'elemento di supporto si prende con un segno meno) e i prodotti risultanti sono aggiunto;

f) dividere tutti gli elementi ricevuti della nuova tabella per l'elemento di riferimento.

7 0) Utilizzando il valore dell'elemento, determinare se è stato trovato il valore ottimo della funzione obiettivo. Se la risposta è negativa, proseguire la decisione (tornare al punto 6).

Riso. 6.8. Regola del rettangolo per determinare i numeri:

un - , b - , c - .

Viene considerato un algoritmo per convertire le tabelle simplex per soluzioni di base ammissibili non degeneri, vale a dire si è verificata la situazione descritta dal Teorema 6.9. Se il problema di programmazione lineare originale è degenerato, nel corso della sua risoluzione utilizzando il metodo del simplesso potrebbero apparire soluzioni di base degenerate. In questo caso sono possibili i passi inutili del metodo del simplesso, ad es. iterazioni in cui F(X) non cambia. È anche possibile il looping, ad es. una sequenza infinita di passi oziosi. Per prevenirlo, sono stati sviluppati algoritmi speciali: anticicline. Tuttavia, nella stragrande maggioranza dei casi, i passaggi inattivi vengono sostituiti da passaggi con una diminuzione della funzione obiettivo e il processo di soluzione viene completato come risultato di un numero finito di iterazioni.

Esempio 6.8. Risolvi il problema proposto nell'esempio 6.7 utilizzando il metodo del simplesso.

⇐ Precedente45678910111213Avanti ⇒

Data di pubblicazione: 23-01-2015; Leggi: 174 | Violazione del copyright della pagina

Studopedia.org - Studopedia.Org - 2014-2018 (0,002 s)…

Home >> Esempio n. 3. Metodo del semplice. Trovare il valore più grande di una funzione (base artificiale)

Metodo del semplice

	—	x1	+	x2	≥	1
x1	+	3	x2	≤	15
—	2	x1	+	x2	≤	4

Una variabile è detta fondamentale per una determinata equazione se è inclusa in questa equazione con un coefficiente pari a uno e non è inclusa nelle restanti equazioni (a condizione che vi sia un numero positivo sul lato destro dell'equazione).

Se ciascuna equazione ha una variabile di base, allora si dice che il sistema ha una base.
Le variabili che non sono di base sono chiamate libere. (vedi sistema di seguito)

L'idea del metodo del simplesso è quella di passare da una base all'altra, ottenendo un valore della funzione che sia almeno non inferiore a quello esistente (ogni base corrisponde a un singolo valore della funzione).
Ovviamente, il numero di basi possibili per qualsiasi problema è finito (e non molto grande).
Pertanto, prima o poi, la risposta arriverà.

Come avviene il passaggio da una base all'altra?
È più conveniente registrare la soluzione sotto forma di tabelle. Ogni riga equivale ad un'equazione del sistema. La linea evidenziata è composta dai coefficienti della funzione (confronta tu stesso). Ciò consente di evitare di riscrivere le variabili ogni volta, con un notevole risparmio di tempo.
Nella riga evidenziata, seleziona il coefficiente positivo più grande. Ciò è necessario per ottenere un valore della funzione almeno non inferiore a quello esistente.
Colonna selezionata.
Per i coefficienti positivi della colonna selezionata, calcoliamo il rapporto Θ e selezioniamo il valore più piccolo. Ciò è necessario affinché dopo la trasformazione la colonna dei termini liberi rimanga positiva.
Riga selezionata.
Pertanto, è stato determinato l'elemento che farà da base. Poi contiamo.

x 1 = 0 x 2 = 0 S 1 = 0
S2 = 15 S3 = 4 R1 = 1

=> W = 1

x1	x2	S1	S2	S3	R1	San 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

x1	x2	S1	S2	S3	San 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	F-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	F-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	F-13

S1 = 0 S2 = 0
x 1 = 3 x 2 = 4 S 3 = 6

=> FA - 13 = 0 => FA = 13

Non ci sono coefficienti positivi tra i coefficienti della riga selezionata. Di conseguenza è stato trovato il valore massimo della funzione F.

Risposta:

x1 = 3x2 = 4

Fmax = 13

Vai alla soluzione al tuo problema

L'obiettivo

Per vendere tre gruppi di beni, un'impresa commerciale dispone di tre tipi di risorse materiali e monetarie limitate per un importo di b 1 = 240, b 2 = 200, b 3 = 160 unità. Allo stesso tempo, per la vendita di 1 gruppo di merci per 1 mila rubli. rotazione delle merci, la risorsa del primo tipo viene consumata per un importo di a 11 = 2 unità, la risorsa del secondo tipo per un importo di a 21 = 4 unità, la risorsa del terzo tipo per un importo di a 31 = 4 unità. Per la vendita di 2 e 3 gruppi di merci per 1 mila rubli. il fatturato viene consumato in base alla risorsa del primo tipo per un importo di a 12 = 3, a 13 = 6 unità, la risorsa del secondo tipo per un importo di a 22 = 2, a 23 = 4 unità, la risorsa di il terzo tipo nella quantità di a 32 = 6, a 33 = 8 unità. Utile dalla vendita di tre gruppi di beni per 1 mille.

Metodo del simplesso per risolvere ZLP

strofinare. il fatturato è rispettivamente c 1 = 4, c 2 = 5, c 3 = 4 (migliaia di rubli). Determinare il volume pianificato e la struttura del fatturato commerciale in modo da massimizzare il profitto dell'impresa commerciale.

Al problema diretto della pianificazione del fatturato, risolto con il metodo del simplesso, comporre duplice problema programmazione lineare.
Installare coppie coniugate di variabili problemi diretti e duali.
Secondo coppie di variabili coniugate, dalla soluzione del problema diretto si ottiene soluzione del duplice problema, in cui viene prodotto valutazione delle risorse, speso per la vendita di beni.

Risolvere il problema utilizzando il metodo del simplesso

Sia x 1, x 2, x 3 il numero di beni venduti, in migliaia di rubli, 1, 2, 3 - i suoi gruppi, rispettivamente. Allora il modello matematico del problema ha la forma:

F = 4 x 1 + 5 x 2 + 4 x 3 ->max

Risolviamo il metodo del simplesso.

Introduciamo variabili aggiuntive x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 per trasformare le disuguaglianze in uguaglianze.

Prendiamo come base x 4 = 240; x5 = 200; x6 = 160.

Inseriamo i dati in tavola semplice

Tavola semplice n. 1

Funzione obiettivo:

0240 + 0200 + 0160 = 0

Calcoliamo le stime utilizzando la formula:

Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0

Poiché esistono stime negative, il piano non è ottimale. Punteggio più basso:

Introduciamo la variabile x2 nella base.

Definiamo una variabile emergente dalla base. Per fare ciò, troviamo il più piccolo rapporto non negativo per la colonna x2.

= 26.667

Il più piccolo non negativo: Q 3 = 26.667. Dalla base ricaviamo la variabile x 6

Dividi la terza riga per 6.
Dalla prima riga, sottrai la terza riga, moltiplicata per 3
Dalla 2a riga, sottrai la 3a riga, moltiplicata per 2

Calcoliamo:

Otteniamo una nuova tabella:

Tavola simplex n. 2

Funzione obiettivo:

0 160 + 0 440/3 + 5 80/3 = 400/3

Calcoliamo le stime utilizzando la formula:

Δ1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6

Poiché esiste una stima negativa Δ 1 = - 2/3, il piano non è ottimale.

Introduciamo la variabile x 1 nella base.

Definiamo una variabile emergente dalla base. Per fare ciò, troviamo il più piccolo rapporto non negativo per la colonna x 1.

Il più piccolo non negativo: Q 3 = 40. Deriviamo la variabile x 2 dalla base

Dividi la terza riga per 2/3.
Dalla 2a riga, sottrai la 3a riga, moltiplicata per 8/3

Calcoliamo:

Otteniamo una nuova tabella:

Tavola simplex n. 3

Funzione obiettivo:

0 160 + 0 40 + 4 40 = 160

Calcoliamo le stime utilizzando la formula:

Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1

Poiché non ci sono valutazioni negative, il piano è ottimale.

La soluzione del problema:

Risposta

x1 = 40; x2 = 0; x3 = 0; x4 = 160; x5 = 40; x6 = 0; Fmax = 160

Cioè, è necessario vendere il primo tipo di merce per un importo di 40mila.

strofinare. I prodotti di tipo 2 e 3 non devono essere venduti. In questo caso, il profitto massimo sarà F max = 160 mila rubli.

Soluzione del duplice problema

Il problema duale ha la forma:

Z = 240 y 1 + 200 y 2 + 160 y 3 ->min

Introduciamo variabili aggiuntive y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 per trasformare le disuguaglianze in uguaglianze.

Le coppie coniugate di variabili dei problemi diretti e duali hanno la forma:

Dall'ultima tabella del simplesso n. 3 del problema diretto, troviamo la soluzione del problema duale:

Zmin = Fmax = 160;
y1 = Δ4 = 0; y2 = Δ5 = 0; y3 = Δ6 = 1; y4 = Δ1 = 0; y5 = Δ2 = 1; y6 = Δ3 = 4;

Risposta

y1 = 0; y2 = 0; y3 = 1; Zmin = 160;

Il metodo del simplesso è una procedura computazionale basata sul principio del miglioramento sequenziale delle soluzioni quando si passa da un punto base (soluzione di base) a un altro. In questo caso, il valore della funzione obiettivo migliora.

La soluzione base è una delle soluzioni ammissibili situate ai vertici della regione dei valori ammissibili. Controllando l'ottimalità vertice dopo vertice del simplesso, si arriva all'ottimo desiderato. Il metodo del simplesso si basa su questo principio.

Un simplesso è un poligono convesso in uno spazio n-dimensionale con n+1 vertici che non giacciono nello stesso iperpiano (l'iperpiano divide lo spazio in due semispazi).

Ad esempio, la linea dei vincoli di bilancio divide i beni in disponibili e non disponibili.

È stato dimostrato che se esiste una soluzione ottima, allora essa verrà sicuramente trovata dopo un numero finito di iterazioni (passi), esclusi i casi di “ciclismo”.

L'algoritmo del metodo del simplesso è costituito da una serie di fasi.

Primo stadio. Viene costruito un modello di ottimizzazione iniziale. Successivamente, la matrice originaria delle condizioni viene trasformata nella forma canonica ridotta, che, tra tutte le altre forme canoniche, si distingue per il fatto che:

a) i membri destri delle condizioni (termini liberi bi) sono quantità non negative;

b) le condizioni stesse sono uguaglianze;

c) la matrice delle condizioni contiene una sottomatrice unitaria completa.

Se i termini liberi sono negativi, entrambi i membri della disuguaglianza vengono moltiplicati per -1 e il segno della disuguaglianza viene invertito. Per trasformare le disuguaglianze in uguaglianze vengono introdotte variabili aggiuntive, che solitamente indicano la quantità di risorse sottoutilizzate. Questo è il loro significato economico.

Infine, se, dopo aver aggiunto ulteriori variabili, la matrice delle condizioni non contiene una sottomatrice di identità completa, vengono introdotte variabili artificiali che non hanno alcun senso economico. Vengono introdotti esclusivamente per ottenere la sottomatrice identità e iniziare il processo di risoluzione del problema utilizzando il metodo del simplesso.

In una soluzione ottimale del problema, tutte le variabili artificiali (AI) devono essere uguali a zero. Per fare ciò, vengono introdotte variabili artificiali nella funzione obiettivo del problema con grandi coefficienti negativi (-M) quando si risolve il problema al massimo e con grandi coefficienti positivi (+M) quando il problema viene risolto al minimo. In questo caso, anche un valore insignificante diverso da zero della variabile artificiale diminuirà (aumenterà) drasticamente il valore della funzione obiettivo. Tipicamente, M dovrebbe essere 1000 volte maggiore dei valori dei coefficienti delle variabili principali.

Seconda fase. Viene costruita una tabella simplex iniziale e viene trovata una soluzione di base iniziale. L’insieme delle variabili che formano la sottomatrice identità viene preso come soluzione base iniziale. I valori di queste variabili sono uguali ai termini liberi. Tutte le altre variabili fuori base sono zero.

Terza fase. Il controllo dell'ottimalità della soluzione di base viene effettuato utilizzando stime speciali dei coefficienti della funzione obiettivo. Se tutte le stime dei coefficienti della funzione obiettivo sono negative o uguali a zero, la soluzione di base esistente è ottimale. Se almeno una stima del coefficiente della funzione obiettivo è maggiore di zero, la soluzione di base esistente non è ottimale e deve essere migliorata.

Quarta fase. Transizione ad una nuova soluzione di base. Ovviamente, il piano ottimale dovrebbe includere una variabile che aumenti al massimo la funzione obiettivo. Quando si risolvono i problemi per ottenere il massimo profitto, il piano ottimale include prodotti la cui produzione è più redditizia. Ciò è determinato dal valore positivo massimo della stima del coefficiente della funzione obiettivo.

La colonna della tabella simplex con questo numero in questa iterazione è chiamata colonna generale.

Per trovare la riga generale, tutti i membri liberi (risorse) vengono divisi negli elementi corrispondenti della colonna generale (tasso di consumo delle risorse per unità di prodotto). Tra i risultati ottenuti viene selezionato quello più piccolo. La linea corrispondente ad una data iterazione è chiamata linea generale. Corrisponde alla risorsa che limita la produzione ad una data iterazione.

Un elemento di una tabella simplex situato all'intersezione di una colonna generale e di una riga è chiamato elemento generale.

Quindi tutti gli elementi della stringa generale (incluso il membro libero) vengono divisi nell'elemento generale. Come risultato di questa operazione, l'elemento generale diventa uguale a uno. Successivamente, è necessario che tutti gli altri elementi della colonna generale diventino uguali a zero, cioè la colonna generale dovrebbe diventare singola. Tutte le righe (tranne quella generale) vengono convertite come segue. Gli elementi risultanti della nuova riga vengono moltiplicati per l'elemento corrispondente della colonna generale e il prodotto risultante viene sottratto dagli elementi della vecchia riga.

Otteniamo i valori delle nuove variabili di base nelle celle corrispondenti della colonna dei termini liberi.

Quinta tappa. La soluzione di base risultante viene verificata per verificarne l'ottimalità (vedere la terza fase). Se è ottimale, i calcoli si interrompono. Altrimenti è necessario trovare una nuova soluzione di base (quarta fase), ecc.

Metodo del semplice

Un esempio di risoluzione di problemi di ottimizzazione della programmazione lineare utilizzando il metodo del simplesso

Sia necessario trovare il piano ottimale per la produzione di due tipi di prodotti (x1 e x2).

Dati iniziali:

Costruiamo un modello di ottimizzazione

– limitazione delle risorse A;

– limitazione delle risorse B.

Riduciamo il problema alla forma canonica ridotta. Per fare ciò è sufficiente introdurre le variabili aggiuntive X3 e X4. Di conseguenza, le disuguaglianze si trasformano in rigorose uguaglianze.

Costruiamo l'originale tavola semplice e trovare la soluzione di base iniziale. Saranno variabili aggiuntive, poiché corrispondono a una sottomatrice unitaria.

1a iterazione. Trova la colonna generale e la riga generale:

L'elemento generale è 5.

2a iterazione. La soluzione di base trovata non è ottimale, perché la linea di rating (Fj-Cj) contiene un elemento positivo. Trova la colonna generale e la riga generale:

massimo(0,0,3,-1,4,0) = 0,2

La soluzione trovata è ottima, poiché tutte le stime speciali della funzione obiettivo Fj – Cj sono uguali a zero o negative. F(x)=29x1=2; x2=5.

Se devi risolvere un problema di programmazione lineare utilizzando le tabelle simplex, allora il ns Servizio Online ti sarà di grande aiuto. Il metodo del simplesso prevede la ricerca sequenziale di tutti i vertici dell'intervallo di valori accettabili per trovare il vertice in cui la funzione assume un valore estremo. Nella prima fase viene trovata una soluzione, che viene migliorata ad ogni passaggio successivo. Questa soluzione è chiamata base. Ecco la sequenza di azioni quando si risolve un problema di programmazione lineare utilizzando il metodo del simplesso:

Primo passo. Nella tabella compilata, prima di tutto, devi guardare la colonna con i membri liberi. Se contiene elementi negativi, è necessario passare al secondo passaggio, in caso contrario al quinto.

Secondo passo. Nella seconda fase è necessario decidere quale variabile escludere dalla base e quale includere per ricalcolare la tabella del simplesso. Per fare ciò, guarda la colonna con i termini liberi e trova un elemento negativo al suo interno. La linea con un elemento negativo verrà chiamata iniziale. In esso troviamo l'elemento negativo massimo in modulo, la colonna corrispondente è quella slave. Se ci sono valori negativi tra i termini liberi, ma non ce ne sono nella riga corrispondente, tale tabella non avrà soluzioni. La variabile nella riga iniziale situata nella colonna dei termini liberi è esclusa dalla base e la variabile corrispondente alla colonna iniziale è inclusa nella base.

Tabella 1.

variabili di base	Membri gratuiti con restrizioni	Variabili non fondamentali
variabili di base	Membri gratuiti con restrizioni	x1	x2	...	xl	...	x n
xn+1	b1	un 11	un 12	...	un 1l	...	un 1n
xn+2	b2	un 21	un 22	...	un 2l	...	un 2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
xn+r	b2	un r1	un r2	...	una rl	...	arn
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
xn+m	b m	un m1	un m2	...	un ml	...	un minuto
F(x)max	F0	-c1	-c2	...	-c1	...	-cn

Terzo passo. Nel terzo passaggio, ricalcoliamo l'intera tabella del simplesso utilizzando formule speciali; queste formule possono essere visualizzate utilizzando.

Quarto passo. Se dopo il ricalcolo rimangono elementi negativi nella colonna dei termini liberi, passare al primo passaggio; se non ce ne sono, al quinto.

Quinto passo. Se hai raggiunto il quinto passaggio, hai trovato una soluzione accettabile. Tuttavia, ciò non significa che sia ottimale. Sarà ottimale solo se tutti gli elementi nella stringa F sono positivi. In caso contrario, è necessario migliorare la soluzione, per la quale troviamo la riga e la colonna principali per il successivo ricalcolo utilizzando il seguente algoritmo. Inizialmente troviamo il numero negativo minimo nella stringa F, escluso il valore della funzione. La colonna con questo numero sarà quella principale. Per trovare la riga iniziale, troviamo il rapporto tra il termine libero corrispondente e l'elemento della colonna iniziale, purché positivi. Il rapporto minimo ti consentirà di determinare la linea principale. Ricalcoliamo nuovamente la tabella utilizzando le formule, ad es. andare al passaggio 3.

Ecco una soluzione manuale (non applet) di due problemi utilizzando il metodo del simplesso (simile alla soluzione dell'applet) con spiegazioni dettagliate per comprendere l'algoritmo per risolvere i problemi utilizzando il metodo del simplesso. Il primo problema contiene solo segni di disuguaglianza “≤” (problema con base iniziale), il secondo può contenere segni “≥”, “≤” o “=" (problema con base artificiale), si risolvono diversamente.

Metodo del simplesso, risoluzione di un problema con una base iniziale

1)Metodo del semplice per un problema con base iniziale (tutti i segni di vincoli di disuguaglianza " ≤ ").

Scriviamo il problema canonico forma, cioè riscriviamo le restrizioni sulla disuguaglianza sotto forma di uguaglianze, aggiungendo bilancio variabili:

Questo sistema è un sistema con una base (base s 1, s 2, s 3, ciascuna di esse è inclusa in una sola equazione del sistema con un coefficiente 1), x 1 e x 2 sono variabili libere. I problemi da risolvere con il metodo del simplesso devono avere le seguenti due proprietà: - il sistema di vincoli deve essere un sistema di equazioni con una base; I termini liberi di tutte le equazioni del sistema devono essere non negativi.

Il sistema risultante è un sistema con una base e i suoi termini liberi non sono negativi, quindi possiamo applicarlo metodo del semplice. Creiamo la prima tabella simplex (Iterazione 0) su cui risolvere il problema metodo del semplice, cioè. una tabella dei coefficienti della funzione obiettivo e un sistema di equazioni per le variabili corrispondenti. Qui “BP” indica la colonna delle variabili di base, “Soluzione” indica la colonna dei membri di destra delle equazioni del sistema. La soluzione non è ottimale, perché ci sono coefficienti negativi nella riga z.

iterazione del metodo del simplesso 0

							Atteggiamento

Per migliorare la soluzione, passiamo all'iterazione successiva metodo del semplice, otteniamo la seguente tabella del simplesso. Per fare ciò è necessario selezionare abilita colonna, cioè. una variabile che verrà inclusa nella base alla successiva iterazione del metodo del simplesso. Viene selezionato dal coefficiente negativo assoluto più grande nella riga z (nel problema massimo) - nell'iterazione iniziale del metodo del simplesso questa è la colonna x 2 (coefficiente -6).

Quindi seleziona abilita la stringa, cioè. una variabile che lascerà la base alla successiva iterazione del metodo del simplesso. Viene selezionato dal rapporto più piccolo tra la colonna "Decisione" e i corrispondenti elementi positivi della colonna di risoluzione (colonna "Rapporto") - nell'iterazione iniziale questa è la riga s 3 (coefficiente 20).

Elemento permissivo si trova all'intersezione tra la colonna risolutiva e la riga risolutiva, la sua cella è evidenziata a colori, è uguale a 1. Pertanto, alla successiva iterazione del metodo del simplesso, la variabile x 2 sostituirà s 1 nella base. Si noti che la relazione non viene cercata nella stringa z; lì viene inserito un trattino "-". Se esistono relazioni minime identiche, viene selezionata una qualsiasi di esse. Se tutti i coefficienti nella colonna della risoluzione sono minori o uguali a 0, la soluzione del problema è infinita.

1) Calcola la riga x 2 della tabella “Iterazione 1”. Innanzitutto, dividiamo tutti i membri della riga risolutiva s 3 della tabella “Iterazione 0” per l'elemento risolutivo (è uguale a 1 in questo caso) di questa tabella, otteniamo la riga x 2 nella tabella “Iterazione 1” . Perché l'elemento risolutivo in questo caso è pari a 1, allora la riga s 3 della tabella “Iterazione 0” coinciderà con la riga x 2 della tabella “Iterazione 1”. Riga x 2 della tabella dell'Iterazione 1 abbiamo ottenuto 0 1 0 0 1 20, le rimanenti righe della tabella dell'Iterazione 1 saranno ottenute da questa riga e dalle righe della tabella dell'Iterazione 0 come segue:

4) Calcolare la riga s 2 della tabella “Iterazione 1”. Al posto 3 nella riga 2 della tabella "Iterazione 0" dovrebbe esserci 0 nella tabella "Iterazione 1". Per fare ciò, moltiplichiamo tutti gli elementi della riga x 2 della tabella "Iterazione 1" 0 1 0 0 1 20 per -3, otteniamo 0 -3 0 0 -3 -60 e aggiungiamo questa riga con s 1 - riga di la tabella "Iterazione 0" 1 3 0 1 0 72, otteniamo la riga 1 0 0 1 -3 12. Nella colonna x 2 si ottiene lo 0 richiesto. La colonna x 2 nella tabella “Iterazione 1” è diventata un'unità, contiene un 1 e il resto 0.

Le righe della tabella “Iterazione 1” sono ottenute secondo la seguente regola:

Nuova riga = Vecchia riga – (Coefficiente colonna di risoluzione della riga precedente)*(Nuova riga di risoluzione).

Ad esempio, per una z-string abbiamo:

Vecchia stringa z (-4 -6 0 0 0 0) -(-6)*Nuova stringa risolvente -(0 -6 0 0 -6 -120) =Nuova stringa z (-4 0 0 0 6 120).

Per le tabelle seguenti, il ricalcolo degli elementi della tabella avviene in modo simile, quindi lo omettiamo.

iterazione del metodo del simplesso 1

							Atteggiamento

iterazione del metodo del simplesso 2

							Atteggiamento

Risolvendo la colonna s 3, risolvendo la riga s 1, s 1 lascia la base, s 3 entra nella base.

iterazione del metodo del simplesso 3

							Atteggiamento

Nella riga z, tutti i coefficienti sono non negativi, quindi si ottiene la soluzione ottima x 1 = 24, x 2 = 16, z max = 192.

Filo, bottoni e tessuto vengono utilizzati per realizzare tre tipi di camicie. Nella tabella sono indicate le scorte di filo, bottoni e tessuto, le norme del loro consumo per cucire una camicia. Trova il massimo profitto e il piano di produzione ottimale del prodotto che lo garantisce (trova).

camicia 1

camicia 2

camicia 3

Riserve

fili (m.)

bottoni (pz.)

640

tessile (

Profitto (r.)

La soluzione del problema

Costruzione di modelli

Attraverso e il numero di magliette del 1o, 2o e 3o tipo destinate al rilascio.

Quindi le restrizioni sulle risorse saranno simili a queste:

Inoltre, secondo il significato del compito

Funzione obiettivo che esprime il profitto ricevuto:

Otteniamo il seguente problema di programmazione lineare:

Riduzione di un problema di programmazione lineare in forma canonica

Riduciamo il problema alla forma canonica. Introduciamo ulteriori variabili. Introduciamo tutte le variabili aggiuntive nella funzione obiettivo con un coefficiente uguale a zero. Aggiungiamo ulteriori variabili al lato sinistro delle restrizioni che non hanno una forma preferita e otteniamo le uguaglianze.

Risolvere il problema utilizzando il metodo del simplesso

Compila la tabella del simplesso:

Poiché stiamo risolvendo il problema al massimo, la presenza di numeri negativi nella riga dell'indice quando risolviamo il problema al massimo indica che non abbiamo ottenuto la soluzione ottima e che è necessario passare dalla tabella della 0a iterazione a quello successivo.

Procediamo alla successiva iterazione come segue:

la colonna principale corrisponde

La riga chiave è determinata dal rapporto minimo tra termini liberi e membri della colonna iniziale (relazioni simplex):

All'intersezione tra la colonna chiave e la riga chiave troviamo l'elemento abilitante, ovvero 9.

Ora procediamo alla compilazione della prima iterazione: invece di un vettore unitario, introduciamo il vettore .

Nella nuova tabella, al posto dell'elemento abilitante scriviamo 1, tutti gli altri elementi della colonna chiave sono zero. Gli elementi della stringa chiave sono divisi nell'elemento abilita. Tutti gli altri elementi della tabella vengono calcolati utilizzando la regola del rettangolo.

La colonna chiave per la prima iterazione corrisponde a

L'elemento risolutivo è il numero 4/3. Deriviamo il vettore dalla base e introduciamo invece il vettore. Otteniamo la tabella della 2a iterazione.

La colonna chiave per la 2a iterazione corrisponde a

Troviamo la linea chiave, per questo definiamo:

L'elemento risolutivo è il numero 10/3. Deriviamo il vettore dalla base e introduciamo invece il vettore. Otteniamo la tabella della 3a iterazione.

№

A o

Semplice

relazione

32/3

640

F j - c j

-2

-5

-4

32/3

1/9

1/3

1/9

1600/3

170/9

80/3

-10/9

68/3

7/9

4/3

-2/9

F j - c j

160/3

-13/9

-7/3

5/9

-1/12

1/6

-1/4

10/3

-20

7/12

-1/6

3/4

204/7

F j - c j

-1/12

1/6

7/4

1/4

1/40

-3/4

3/10

-6

-3/4

-7/40

17/4

F j - c j

1/4

1/40

5/4

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

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

Potresti essere interessato ai seguenti materiali