Il metodo del simplesso è. Risolvere il problema utilizzando il metodo del simplesso

Questo metodo è un metodo di enumerazione mirata di soluzioni di riferimento per un problema di programmazione lineare. Permette, in un numero finito di passaggi, sia di trovare una soluzione ottimale sia di stabilire che non esiste una soluzione ottimale.

1. Indicare un metodo per trovare la soluzione di riferimento ottimale
2. Indicare il metodo di transizione da una soluzione di riferimento all'altra, in cui il valore della funzione obiettivo sarà più vicino a quello ottimale, vale a dire indicare un modo per migliorare la soluzione di riferimento
3. Stabilisci criteri che ti consentano di interrompere tempestivamente la ricerca di soluzioni di supporto nella soluzione ottimale o di trarre una conclusione sull'assenza di una soluzione ottimale.

Algoritmo del metodo del simplesso per la risoluzione di problemi di programmazione lineare

1. Riportare il problema in forma canonica
2. Trovare la soluzione di supporto iniziale con una “base unitaria” (se non esiste una soluzione di supporto, allora il problema non ha soluzione a causa dell’incompatibilità del sistema di vincoli)
3. Calcolare le stime delle scomposizioni vettoriali in base alla soluzione di riferimento e compilare la tabella del metodo del simplesso
4. Se il criterio dell'unicità della soluzione ottima è soddisfatto, la soluzione del problema termina
5. Se la condizione per l'esistenza di un insieme di soluzioni ottime è soddisfatta, tutte le soluzioni ottime vengono trovate mediante una semplice enumerazione

Un esempio di risoluzione di un problema utilizzando il metodo del simplesso

Risolvi il problema utilizzando il metodo del simplesso:

Soluzione:

Portiamo il problema in forma canonica.

Per fare ciò, introduciamo un'ulteriore variabile x 6 con coefficiente +1 a sinistra del primo vincolo di disuguaglianza. La variabile x 6 è inclusa nella funzione obiettivo con un coefficiente pari a zero (cioè non è inclusa).

Noi abbiamo:

Troviamo la soluzione di supporto iniziale. Per fare ciò, uguagliamo le variabili libere (non risolte) a zero x1 = x2 = x3 = 0.

Noi abbiamo soluzione di riferimento X1 = (0,0,0,24,30,6) con base unitaria B1 = (A4, A5, A6).

Calcoliamo stime di decomposizioni vettoriali condizioni in base alla soluzione di riferimento secondo la formula:

Δ k = C b X k - c k

• C b = (c 1, c 2, ..., c m) - vettore dei coefficienti della funzione obiettivo per le variabili di base
• X k = (x 1k, x 2k, ..., x mk) - vettore di sviluppo del corrispondente vettore A k secondo la base della soluzione di riferimento
• C k è il coefficiente della funzione obiettivo per la variabile x k.

Le stime dei vettori compresi nella base sono sempre pari a zero. Vengono scritti la soluzione di riferimento, i coefficienti di espansione e le stime delle espansioni dei vettori di condizione basate sulla soluzione di riferimento tavola semplice:

Nella parte superiore della tabella, per facilitare il calcolo delle stime, sono scritti i coefficienti della funzione obiettivo. Nella prima colonna "B" sono scritti i vettori compresi nella base della soluzione di riferimento. L'ordine in cui sono scritti questi vettori corrisponde al numero di incognite consentite nelle equazioni dei vincoli. Nella seconda colonna della tabella "C b" i coefficienti della funzione obiettivo per le variabili di base sono scritti nello stesso ordine. A posizione corretta I coefficienti della funzione obiettivo nella colonna "C b" della stima dei vettori unitari compresi nella base sono sempre pari a zero.

Nell'ultima riga della tabella con le stime di Δ k nella colonna “A 0” sono scritti i valori della funzione obiettivo sulla soluzione di riferimento Z(X 1).

La soluzione di supporto iniziale non è ottimale, poiché nel problema di massimo le stime Δ 1 = -2, Δ 3 = -9 per i vettori A 1 e A 3 sono negative.

Secondo il teorema sul miglioramento della soluzione di supporto, se in un problema di massimo almeno un vettore ha una stima negativa, allora si può trovare una nuova soluzione di supporto su cui il valore della funzione obiettivo sarà maggiore.

Determiniamo quale dei due vettori porterà ad un incremento maggiore nella funzione obiettivo.

L'incremento della funzione obiettivo si trova dalla formula: .

Calcoliamo i valori del parametro θ 01 per la prima e la terza colonna utilizzando la formula:

Otteniamo θ 01 = 6 per l = 1, θ 03 = 3 per l = 1 (Tabella 26.1).

Troviamo l'incremento della funzione obiettivo introducendo nella base il primo vettore ΔZ 1 = - 6*(- 2) = 12 e il terzo vettore ΔZ 3 = - 3*(- 9) = 27.

Di conseguenza, per un approccio più rapido alla soluzione ottima, è necessario introdurre nella base della soluzione di riferimento il vettore A3 al posto del primo vettore della base A6, poiché il minimo del parametro θ 03 si ottiene nella prima riga ( l = 1).

Eseguiamo la trasformazione di Jordan con l'elemento X13 = 2, otteniamo la seconda soluzione di riferimento X2 = (0,0,3,21,42,0) con base B2 = (A3, A4, A5). (Tabella 26.2)

Questa soluzione non è ottimale, poiché il vettore A2 ha una stima negativa Δ2 = - 6. Per migliorare la soluzione è necessario introdurre il vettore A2 nella base della soluzione di riferimento.

Determiniamo il numero del vettore derivato dalla base. Per fare ciò calcoliamo il parametro θ 02 per la seconda colonna, è uguale a 7 per l = 2. Di conseguenza, dalla base ricaviamo il secondo vettore base A4. Eseguiamo la trasformazione di Jordan con l'elemento x 22 = 3, otteniamo la terza soluzione di riferimento X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Tabella 26.3).

Questa soluzione è l'unica ottimale poiché per tutti i vettori non compresi nella base le stime sono positive

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Risposta: massimo Z(X) = 201 a X = (0,7,10,0,63).

Metodo della programmazione lineare in analisi economica

Metodo di programmazione lineare consente di giustificare la soluzione economica più ottimale in condizioni di severe restrizioni legate alle risorse utilizzate nella produzione (immobilizzazioni, materiali, risorse lavorative). L'utilizzo di questo metodo nell'analisi economica consente di risolvere problemi legati principalmente alla pianificazione delle attività di un'organizzazione. Questo metodo aiuta a determinare valori ottimali produzione, nonché la direzione dell’uso più efficace delle risorse produttive a disposizione dell’organizzazione.

Utilizzando questo metodo si risolvono i cosiddetti problemi estremi, che consistono nel trovare i valori estremi, cioè il massimo e il minimo di funzioni di quantità variabili.

Questo periodo si basa sulla risoluzione di un sistema di equazioni lineari nei casi in cui i fenomeni economici analizzati sono collegati da una dipendenza lineare, strettamente funzionale. Il metodo della programmazione lineare viene utilizzato per analizzare le variabili in presenza di determinati fattori limitanti.

È molto comune risolvere il cosiddetto problema del trasporto utilizzando il metodo della programmazione lineare. Il contenuto di questo compito è ridurre al minimo i costi sostenuti in relazione all'operazione Veicolo in base alle restrizioni esistenti relative al numero di veicoli, alla loro capacità di carico, alla durata del loro funzionamento, se è necessario servire il numero massimo di clienti.

Inoltre, questo metodo è ampiamente utilizzato per risolvere il problema della pianificazione. Questo compito consiste in una tale distribuzione del tempo di lavoro per il personale di una determinata organizzazione che sarebbe più accettabile sia per i membri di questo personale che per i clienti dell'organizzazione.

Questo compito è massimizzare il numero di clienti serviti in condizioni di limitazione del numero di membri del personale disponibile, nonché del fondo orario di lavoro.

Pertanto, il metodo di programmazione lineare è molto comune nell'analisi del posizionamento e dell'utilizzo di vari tipi di risorse, nonché nel processo di pianificazione e previsione delle attività delle organizzazioni.

Tuttavia, la programmazione matematica può essere applicata anche a quei fenomeni economici la cui relazione non è lineare. A questo scopo possono essere utilizzati metodi di programmazione non lineare, dinamica e convessa.

La programmazione non lineare si basa sulla natura non lineare della funzione obiettivo o dei vincoli, o su entrambi. Le forme della funzione obiettivo e dei vincoli di disuguaglianza in queste condizioni possono essere diverse.

La programmazione non lineare viene utilizzata nell'analisi economica, in particolare, quando si stabilisce la relazione tra gli indicatori che esprimono l'efficienza delle attività di un'organizzazione e il volume di questa attività, la struttura dei costi di produzione, le condizioni di mercato, ecc.

La programmazione dinamica si basa sulla costruzione di un albero decisionale. Ogni livello di questo albero funge da stadio per determinare le conseguenze di una decisione precedente e per eliminare le opzioni inefficaci per quella decisione. Pertanto, la programmazione dinamica ha una natura multifase e multistadio. Questo tipo di programmazione viene utilizzato nell'analisi economica per trovare opzioni ottimali sviluppo dell’organizzazione presente e futura.

La programmazione convessa è un tipo di programmazione non lineare. Questo tipo di programmazione esprime la natura non lineare del rapporto tra i risultati delle attività di un’organizzazione e i suoi costi. La programmazione convessa (nota anche come concava) analizza le funzioni obiettivo convesse e i sistemi di vincoli convessi (punti di fattibilità). Programmazione convessa applicata in analisi attività economica al fine di minimizzare i costi e concavo - al fine di massimizzare il reddito sotto le restrizioni esistenti sull'azione di fattori che influenzano gli indicatori analizzati in modo opposto. Di conseguenza, con i tipi di programmazione in esame, le funzioni obiettivo convesse sono ridotte al minimo e le funzioni obiettivo concave sono massimizzate.

Programmazione lineare è una tecnica di modellazione matematica progettata per ottimizzare l'uso di risorse limitate. L'LP viene utilizzato con successo in campo militare, industriale, agricoltura, nel settore dei trasporti, nell’economia, nel sistema sanitario e perfino nelle scienze sociali. L'uso diffuso di questo metodo è supportato anche da algoritmi informatici altamente efficienti che implementano questo metodo. Gli algoritmi di ottimizzazione per altri tipi più complessi di modelli e problemi di ricerca operativa (OR), inclusa la programmazione intera, non lineare e stocastica, si basano su algoritmi di programmazione lineare.

Problema di ottimizzazione è un problema economico e matematico che consiste nel trovare il valore ottimale (massimo o minimo) della funzione obiettivo, e i valori delle variabili devono appartenere a un certo intervallo di valori accettabili.

Nella sua forma più generale, il problema della programmazione lineare è scritto matematicamente come segue:

Dove X = (x 1 , X 2 , ... , X N ) ; W– intervallo di valori consentiti delle variabili X 1 , X 2 , ... , X N ;f(X)- funzione obiettivo.

Per risolvere un problema di ottimizzazione è sufficiente trovare la sua soluzione ottima, cioè indica quello a qualsiasi .

Un problema di ottimizzazione è irrisolvibile se non ha una soluzione ottima. In particolare, il problema di massimizzazione sarà irrisolvibile se la funzione obiettivo f(X) non è delimitato dall'alto nell'insieme ammissibile W.

I metodi per risolvere i problemi di ottimizzazione dipendono sia dal tipo di funzione obiettivo f(X), e dalla struttura dell'insieme ammissibile W. Se la funzione target nel problema è una funzione N variabili, allora i metodi di soluzione sono chiamati metodi di programmazione matematica.

Le caratteristiche dei problemi di programmazione lineare sono le seguenti:

indice di ottimalità f(X)è una funzione lineare degli elementi della soluzione X = (x 1 , X 2 , ... , X N ) ;

le condizioni restrittive imposte alle possibili soluzioni assumono la forma di uguaglianze o disuguaglianze lineari.

Problema di programmazione lineare è chiamato problema di ricerca operativa, il cui modello matematico ha la forma:

(2) (3) (4) (5)

In questo caso, il sistema di equazioni lineari (3) e disequazioni (4), (5), che determina l'insieme ammissibile di soluzioni al problema W, chiamato sistema di restrizioni problemi di programmazione lineare e una funzione lineare f(X) chiamato funzione bersaglio O criterio di ottimalità .

Soluzione valida è una raccolta di numeri ( piano ) X = (X 1 , X 2 , ... , X N ) , soddisfacendo i vincoli del problema. Soluzione ottimale – si tratta di un piano in cui la funzione obiettivo assume il suo valore massimo (minimo).

Se il modello matematico di un problema di programmazione lineare ha la forma:

poi dicono che il problema si presenta in forma canonica .

Qualsiasi problema di programmazione lineare può essere ridotto a un problema di programmazione lineare in forma canonica. Per fare ciò, nel caso generale, occorre essere in grado di ridurre il problema di massimizzazione al problema di minimizzazione; passare dai vincoli di disuguaglianza ai vincoli di uguaglianza e sostituire le variabili che non obbediscono alla condizione di non negatività. Massimizzare una determinata funzione equivale a minimizzare la stessa funzione presa con il segno opposto, e viceversa.

La regola per portare un problema di programmazione lineare in forma canonica è la seguente:

se nel problema originale occorre determinare il massimo di una funzione lineare, allora conviene cambiare segno e cercare il minimo di tale funzione;

se il lato destro delle restrizioni è negativo, allora questa restrizione dovrebbe essere moltiplicata per -1;

se ci sono disuguaglianze tra le restrizioni, allora introducendo ulteriori variabili non negative queste si trasformano in uguaglianze;

se qualche variabile X J non ha restrizioni di segno, allora viene sostituita (nella funzione obiettivo e in tutte le restrizioni) dalla differenza tra due nuove variabili non negative: X 3 =x 3 + -X 3 - , Dove X 3 + , X 3 - ≥ 0 .

Esempio 1. Riducendo il problema della programmazione lineare alla forma canonica:

L minimo = 2x 1 +x 2 -X 3 ; 2x 2 -X 3 ≤ 5; X 1 +x 2 -X 3 ≥ -1; 2x 1 -X 2 ≤ -3; X 1 ≤ 0; X 2 ≥ 0; X 3 ≥ 0.

Introduciamo variabili di livellamento in ciascuna equazione del sistema di vincoli X 4 , X 5 , X 6 . Il sistema verrà scritto sotto forma di uguaglianze, e nella prima e terza equazione del sistema di vincoli le variabili X 4 , X 6 vengono inseriti nella parte sinistra con un segno “+” e nella seconda equazione la variabile X 5 viene inserito con il segno "-".

2x 2 -X 3 +x 4 = 5; X 1 +x 2 -X 3 -X 5 = -1; 2x 1 -X 2 +x 6 = -3; X 4 ≥ 0; X 5 ≥ 0; X 6 ≥ 0.

I termini liberi nella forma canonica devono essere positivi; per fare ciò moltiplicare le ultime due equazioni per -1:

2x 2 -X 3 +x 4 = 5; -X 1 -X 2 +x 3 +x 5 = 1; -2x 1 +x 2 -X 6 = 3.

Metodo del simplesso per la risoluzione di problemi di programmazione lineare.

L'algoritmo del metodo del simplesso trova la soluzione ottima considerando un numero limitato di soluzioni di base ammissibili. L’algoritmo del metodo del simplesso inizia sempre con una soluzione base ammissibile e poi cerca di trovare un’altra soluzione base ammissibile che “migliori” il valore della funzione obiettivo. Ciò è possibile solo se un aumento di una qualsiasi variabile zero (non di base) porta ad un miglioramento del valore della funzione obiettivo. Ma affinché una variabile non di base diventi positiva, una delle variabili di base attuali deve essere impostata su zero, cioè convertire in non di base. Ciò è necessario affinché la nuova soluzione contenga esattamente M variabili di base. Secondo la terminologia del metodo del simplesso, viene chiamata la variabile zero selezionata ingresso (alla base) e la variabile base da eliminare è escluso (dalla base).

Chiamiamo due regole per la selezione delle variabili di input e di esclusione nel metodo del simplesso condizione di ottimalità E condizione di ammissibilità . Formuliamo queste regole e consideriamo anche la sequenza di azioni eseguite durante l'implementazione del metodo del simplesso.

Condizione di ottimalità. La variabile di input nel problema di massimizzazione (minimizzazione) è una variabile non di base che ha il coefficiente negativo (positivo) più grande in bersaglio-linea. Se dentro bersaglio-line contiene diversi coefficienti di questo tipo, la scelta della variabile inserita viene effettuata arbitrariamente. La soluzione ottimale si ottiene quando bersaglio-line, tutti i coefficienti per le variabili non di base saranno non negativi (non positivi).

Condizione di ammissibilità. Sia nei problemi di massimizzazione che in quelli di minimizzazione, la variabile base per la quale il rapporto tra il valore del lato destro del vincolo e il coefficiente positivo della colonna principale è minimo viene selezionata come esclusa. Se esistono più variabili di base con questa proprietà, la scelta della variabile esclusa è arbitraria.

Presentiamo un algoritmo per risolvere un problema di programmazione lineare volto a trovare un massimo utilizzando tabelle del simplesso.

F = ñ 1 x 1 +ñ 2 x 2 +…+ñ n x n max

x10, x20,…, xn0.

1° passo. Introduciamo variabili aggiuntive e scriviamo il sistema risultante di equazioni e funzioni lineari sotto forma di un sistema esteso.

F–c 1 x 1 –c 2 x 2 –…–c n x n =0=c p.

2° passo. Componiamo la tabella simplex iniziale.

3° passo. Controlliamo l'adempimento del criterio di ottimalità: la presenza di coefficienti negativi nell'ultima riga. Se non ce ne sono, allora la soluzione è ottima e F * =c o, le variabili di base sono uguali ai coefficienti corrispondenti b j, le variabili non di base sono uguali a zero, cioè X * =(b 1,b 2,…, bm, 0,…, 0).

4° passo. Se il criterio di ottimalità non è soddisfatto, il coefficiente negativo assoluto più grande nell'ultima riga (stimata) determina la colonna risolutiva s.

Per determinare la linea di risoluzione, calcoliamo i rapporti di valutazione e compila l'ultima colonna della tabella.

Il rapporto stimato della i-esima riga è

 se b i e a hanno segni diversi;

 se b i =0 e a è<0;

 se a è =0;

0 se b i =0 e a è >0;

Nella colonna delle relazioni valutative troviamo l'elemento minimo min che definisce la stringa di abilitazione g.

Se non esiste un minimo, il problema non ha un ottimo finale I ed è irrisolvibile.

All'intersezione della riga e della colonna risolutive c'è un elemento risolutivo a gs.

5° passo. Costruiamo la seguente tabella. Per questo

Passiamo al terzo passaggio.

Metodo M Talvolta, quando si risolve uno ZLP, la matrice dei coefficienti per i vincoli del sistema sconosciuto non ha colonne unitarie da cui può essere composta una matrice unitaria, ad es. sorge un problema nella scelta delle variabili di base, oppure la soluzione iniziale è inaccettabile. In questi casi utilizzare metodo delle basi artificiali (metodo M). In tutte le restrizioni in cui non esistono variabili di base, variabili artificiali. Le variabili artificiali vengono introdotte nella funzione obiettivo con un coefficiente (- M) per problemi con max e con un coefficiente (+ M) per problemi con min, dove M è un numero positivo sufficientemente grande. Quindi il problema esteso viene risolto utilizzando le regole del metodo del simplesso. Se tutte le variabili artificiali sono uguali a zero, cioè sono esclusi dalla base, allora si otterrà una soluzione ottima del problema originale, oppure il problema originale verrà ulteriormente risolto e si troverà la sua soluzione ottima o si stabilirà la sua irrisolvibilità. Se almeno una delle variabili artificiali risulta essere diversa da zero, il problema originario non ha soluzione

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 mostrata la soluzione ottimale risultante al problema.

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

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

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 da regola successiva:

Nuova riga = Vecchia riga – (Coefficiente colonna risoluzione riga precedente)*(Nuova riga 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

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

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

Iterazione 3

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

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

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 alternativa soluzioni ottimali . 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 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.

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.

>> >> >> Metodo del simplesso

Metodo del semplice

Qualsiasi soluzione può essere trovata metodo del semplice. Prima di utilizzare il metodo del simplesso, dovresti scrivere il problema originale nella forma di un problema di programmazione lineare di base, se non ha tale forma.

Il metodo del simplesso per risolvere un problema di programmazione lineare si basa sul passaggio da un piano di riferimento a un altro, in cui il valore della funzione obiettivo aumenta(a condizione che questo problema abbia un piano ottimo e ciascuno dei suoi piani di supporto non sia degenerato). La transizione specificata è possibile se si conosce qualche piano di riferimento iniziale. Consideriamo un problema per il quale questo piano può essere scritto direttamente.

Sia necessario trovare il valore massimo della funzione

a condizioni

Qui e – dati numeri costanti

La forma vettoriale di questo problema è la seguente: trova il massimo della funzione

a condizioni

quindi, per definizione, il piano di riferimento è il piano di riferimento di questo problema (le ultime componenti del vettore X sono uguali a zero). Questo piano è determinato dal sistema di vettori unitari che ne costituisce la base M- misurato spazio. Pertanto, ciascuno dei vettori e può anche essere rappresentato come una combinazione lineare di vettori di una data base. Permettere

Mettiamo Poiché i vettori – singolo, quindi e

Teorema 5

(segno di ottimalità del piano di riferimento). Piano di attività di base (22) – (24) è ottimale se per qualsiasi j

Teorema 6.

Se per alcuni j=k e non ci sono numeri positivi tra i numeri , poi la funzione obiettivo(22) compiti (22) – (24) non è limitato ai suoi numerosi piani.

Teorema 7.

Se il piano di riferimento X dell'attività (22) – (24)non degeneratoE , Ma tra i numerice ne sono di positivi (non tutti), allora esiste un piano di riferimento X" tale che

I teoremi formulati consentono di verificare se il piano di riferimento trovato è ottimale e di identificare la fattibilità del passaggio ad un nuovo piano di riferimento.

È più conveniente studiare il piano di riferimento per l'ottimalità, così come l'ulteriore processo computazionale, se le condizioni del problema e i dati iniziali ottenuti dopo aver determinato il piano di riferimento iniziale sono scritti come mostrato nella Tabella. 3.

Nella colonna C 6 di questa tabella sono scritti i coefficienti delle funzioni obiettivo incognite, aventi gli stessi indici dei vettori della base data.

I componenti positivi del piano di riferimento originale sono scritti nella colonna e, come risultato dei calcoli, in essa si ottengono i componenti positivi del piano ottimale. Le colonne di vettori rappresentano i coefficienti dell'espansione di questi vettori nei vettori di una data base.

Nella tabella 3 prima M le righe sono determinate dai dati iniziali del problema e vengono calcolati gli indicatori della (m+1)esima riga. In questa riga, nella colonna del vettore, scrivi il valore della funzione obiettivo che assume per un dato piano di riferimento, e nella colonna del vettore – Senso

Il valore di Z j si trova come prodotto scalare di un vettore e un vettore

Il valore è uguale al prodotto scalare del vettore P 0 e del vettore:

Dopo aver compilato la Tabella 3, viene verificata l'ottimalità del piano di riferimento originale. Per fare ciò, guarda gli elementi dell'esima riga della tabella. Di conseguenza, può verificarsi uno dei tre casi seguenti:

1) per j=m+1, (A ). Numeri per tutti, quindi, in questo caso J da 1 a N;

2) per alcuni J e tutti i valori corrispondenti a questo indice

3) per alcuni indici J, e per ciascuno di essi J almeno uno dei numeri è positivo.

Nel primo caso, in base al criterio di ottimalità, il piano di riferimento iniziale è ottimale. Nel secondo caso la funzione obiettivo non è limitata dall'alto all'insieme dei piani e nel terzo caso è possibile passare dal piano originale a un nuovo piano di riferimento, in cui il valore della funzione obiettivo aumenterà. Questa transizione da un piano di riferimento all'altro viene effettuata escludendo uno qualsiasi dei vettori dalla base originaria e introducendovi un nuovo vettore. Come vettore introdotto nella base, puoi prendere uno qualsiasi dei vettori con l'indice J, per cui . Supponiamo, ad esempio, che si decida di introdurre un vettore nella base

Per determinare il vettore da escludere dalla base, trovare per tutti Lascia che questo minimo venga raggiunto quando io=r. Quindi il vettore viene escluso dalla base e viene chiamato il numero elemento permissivo.

Viene chiamata la colonna e la riga all'intersezione delle quali è presente un elemento risolutivo guide.

Dopo aver selezionato la riga guida e la colonna guida, si trovano un nuovo piano di riferimento e i coefficienti di espansione dei vettori attraverso i vettori della nuova base corrispondenti al nuovo piano di riferimento. Questo è facile da implementare se si utilizza il metodo Jordan-Gauss. In questo caso si può dimostrare che le componenti positive del nuovo piano di riferimento vengono calcolate utilizzando le formule

(25)

e i coefficienti di espansione dei vettori attraverso i vettori della nuova base corrispondente al nuovo piano di riferimento - secondo le formule

(26)

Dopo il calcolo e secondo le formule (25) e (26), i loro valori vengono inseriti nella tabella. 4. Gli elementi dell'esima riga di questa tabella possono essere calcolati utilizzando formule

(27)

(28)

o in base alla loro definizione.

Tabella 3

Tabella 4

La presenza di due modalità per trovare gli elementi dell'esima riga consente di controllare la correttezza dei calcoli eseguiti.

Dalla formula (27) ne consegue che quando si passa da un piano di riferimento all'altro, è consigliabile introdurre nella base un vettore avente l'indice J, in corrispondenza del quale il massimo in valore assoluto è il numero . Tuttavia, per semplificare il processo di calcolo, in futuro determineremo il vettore introdotto nella base in base al valore assoluto massimo dei numeri negativi. Se esistono più di questi numeri, introdurremo nella base un vettore che ha lo stesso indice del massimo dei numeri definiti da questi numeri

Quindi, il passaggio da un piano di riferimento all'altro si riduce al passaggio da una tabella simplex all'altra. Gli elementi della nuova tavola del simplesso possono essere calcolati sia utilizzando le formule ricorrenti (25)-(28) sia utilizzando le regole che da esse derivano direttamente. Queste regole sono le seguenti.

Nelle colonne di vettori inclusi nella base, all'intersezione di righe e colonne di vettori con lo stesso nome, vengono posizionate le unità e tutti gli altri elementi di queste colonne sono impostati uguali a zero.

Gli elementi dei vettori e della riga della nuova tabella simplex, in cui è scritto il vettore entrato in base, si ottengono dagli elementi della stessa riga della tabella originale dividendoli per il valore dell'elemento risolvente. Nella colonna nella riga del vettore di input, inserisci il valore , dove K – indice del vettore di input.

Gli elementi rimanenti delle colonne vettoriali e la nuova tabella del simplesso vengono calcolati utilizzando la regola del triangolo. Per calcolare uno qualsiasi di questi elementi, si trovano tre numeri:

1) un numero che sta nella tavola simplex originale al posto dell'elemento desiderato della nuova tavola simplex;

2) un numero nella tabella simplex originale all'intersezione della riga contenente l'elemento desiderato della nuova tabella simplex e la colonna corrispondente al vettore inserito nella base;

3) un numero nella nuova tabella del simplesso all'intersezione della colonna in cui si trova l'elemento richiesto e la riga del vettore appena introdotto nella base (come notato sopra, questa riga è ottenuta dalla riga della tabella del simplesso originale dividendo i suoi elementi per l'elemento risolvente).

Questi tre numeri formano una specie di triangolo, due dei cui vertici corrispondono ai numeri della tavola simplex originale e il terzo al numero della nuova tavola simplex. Per determinare l'elemento richiesto della nuova tabella simplex, il prodotto del secondo e del terzo viene sottratto dal primo numero.

Dopo aver riempito la nuova tabella simplex, vengono esaminati gli elementi della riga -esima. Se tutto è così, allora il nuovo piano di riferimento è ottimale. Se tra i numeri indicati ce ne sono di negativi, quindi, utilizzando la sequenza di azioni sopra descritta, viene trovato un nuovo piano di riferimento. Questo processo viene continuato finché non si ottiene la progettazione ottimale del problema o si stabilisce la sua irrisolvibilità.

Nel trovare una soluzione al problema della programmazione lineare, abbiamo assunto che questo problema abbia piani di supporto e che ciascuno di questi piani non sia degenere. Se il problema ha piani di supporto degeneri, allora in una delle iterazioni una o più variabili del piano di supporto potrebbero risultare uguali a zero. Pertanto, quando si passa da un piano di riferimento all'altro, il valore della funzione può rimanere lo stesso. Inoltre, è possibile che la funzione mantenga il suo valore per diverse iterazioni, ed è anche possibile ritornare alla base originale. In quest'ultimo caso di solito raccontano cosa è successo looping. Tuttavia, quando si risolvono problemi pratici, questo caso si verifica molto raramente, quindi non ci soffermeremo su di esso.

Pertanto, trovare il piano ottimale utilizzando il metodo del simplesso include i seguenti passaggi:

1. Trova un piano di riferimento.

2. Crea una tabella simplex.

3. Scopri se c'è almeno un numero negativo. In caso contrario, il piano di riferimento trovato è ottimale. Se tra i numeri ci sono numeri negativi, stabiliscono l'irrisolvibilità del problema o passano a un nuovo piano di riferimento.

4. Trova le guide di colonna e riga. La colonna guida è determinata dal numero negativo più grande in valore assoluto e la riga guida è determinata dal minimo dei rapporti tra i componenti della colonna vettoriale e i componenti positivi della colonna guida.

5. Utilizzando le formule (25) – (28), vengono determinati i componenti positivi del nuovo piano di riferimento e i coefficienti di espansione del vettore Pj dai vettori della nuova base e del numero , . Tutti questi numeri sono scritti in una nuova tabella simplex.

6. Controllare l'ottimalità del piano di riferimento trovato. Se il piano non è ottimale ed è necessario passare a un nuovo piano di riferimento, si torna alla fase 4 e se si ottiene un piano ottimale o si stabilisce l'irrisolvibilità, il processo di risoluzione del problema è completato.

Esempio 9.

Per la fabbricazione di vari prodotti UN,IN e C l'impresa ne utilizza tre vari tipi materie prime. Tassi di consumo di materie prime per la produzione di un prodotto di ciascun tipo, prezzo di un prodotto UN,IN E CON, nonché la quantità totale di materie prime di ciascun tipo che possono essere utilizzate dall'impresa, sono riportate nella tabella. 5.

Tabella 5

Prodotti UN,IN E CON può essere prodotto in qualsiasi proporzione (le vendite sono garantite), ma la produzione è limitata alle materie prime di ciascun tipo assegnate all'impresa.

Elaborare un piano di produzione per prodotti in cui il costo totale di tutti i prodotti fabbricati dall'impresa è massimo.

Soluzione. Creiamo un modello matematico del problema. Rilascio del prodotto richiesto UN denotiamo con x 1, prodotti IN - attraverso , prodotti CON - Attraverso . Poiché esistono restrizioni sul fondo delle materie prime di ogni tipo assegnato all'impresa, le variabili devono soddisfare il seguente sistema di disuguaglianze:

(29)

Il costo totale dei prodotti fabbricati dall'impresa, soggetto al rilascio di x 1 prodotti UN, prodotti IN e prodotti CON ammonta a

A seconda del loro contenuto economico, le variabili possono assumere solo valori non negativi:

Arriviamo così al seguente problema matematico: tra tutte le soluzioni non negative del sistema di diseguaglianze (29), è necessario trovarne una in cui la funzione (30) assume il valore massimo.

Scriviamo questo problema sotto forma di un problema di programmazione lineare di base. Per fare ciò, passiamo dai vincoli di disuguaglianza ai vincoli di uguaglianza. Introduciamo tre variabili aggiuntive, a seguito delle quali le restrizioni verranno scritte sotto forma di un sistema di equazioni

In termini economici, queste variabili aggiuntive significano la quantità di materia prima di un tipo o di un altro che non viene utilizzata in un determinato piano di produzione. Per esempio, – Questa è la quantità inutilizzata di materie prime di tipo I.

Scriviamo il sistema di equazioni trasformato in forma vettoriale:

Poiché tra i vettori Poiché esistono tre vettori unitari, il piano di riferimento può essere scritto direttamente per questo problema. Quello è il piano X=(0; 0; 0; 360; 192; 180), definito da un sistema di vettori unitari tridimensionali che costituiscono la base di uno spazio vettoriale tridimensionale.

Componiamo una tabella simplex per l'iterazione I (Tabella 6), calcoliamo i valori e controlliamo l'ottimalità del piano di riferimento iniziale:

Per i vettori di base

Tabella 6

Come si può vedere dalla Tabella 6, i valori di tutte le variabili principali sono uguali a zero e le variabili aggiuntive assumono i loro valori in conformità con i vincoli del problema. Questi valori variabili corrispondono a un “piano” in cui non si produce nulla, non si utilizzano materie prime e il valore della funzione obiettivo è zero (cioè non ci sono costi di produzione). Questo piano, ovviamente, non è ottimale.

Questo può essere visto dalla quarta riga della tabella. 6, poiché contiene tre numeri negativi: e I numeri negativi non solo indicano la possibilità di aumentare il costo totale di produzione, ma mostrano anche quanto questo importo aumenterà quando un'unità dell'uno o dell'altro tipo di prodotto verrà introdotta nel piano.

Quindi, il numero - 9 significa che quando un prodotto è incluso nel piano di produzione UN garantisce un aumento della produzione di 9 rubli. Se includi un prodotto nel piano di produzione IN e C, il costo totale dei prodotti fabbricati aumenterà rispettivamente di 10 e 16 rubli. Pertanto, da un punto di vista economico, è più opportuno includere i prodotti nel piano di produzione CON. Lo stesso va fatto in base al segno formale del metodo del simplesso, poiché il massimo numero negativo in valore assoluto si trova nella 4a riga della colonna vettoriale R 3. Pertanto, introduciamo il vettore nella base R 3. determiniamo il vettore da escludere dalla base. Per fare questo troviamo

Avendo trovato il numero, abbiamo quindi determinato da un punto di vista economico quanti prodotti CON l'impresa può produrre tenendo conto dei tassi di consumo e dei volumi disponibili di materie prime di ciascun tipo. Poiché vi sono rispettivamente 360, 192 e 180 kg di materie prime di questo tipo, e per un prodotto CON le materie prime da spendere di ciascuna tipologia sono rispettivamente 12, 8 e 3 kg, quindi il numero massimo di prodotti CON, che può essere prodotto dall'impresa, è pari a cioè, un fattore limitante per la produzione di prodotti CONè il volume disponibile di materie prime di tipo II. Tenendo conto della sua disponibilità, l'azienda può produrre 24 prodotti CON. In questo caso, le materie prime di tipo II verranno completamente utilizzate.

Pertanto, il vettore R 5 è soggetto ad esclusione dalla base. Colonna vettoriale R Le righe dalla 3 alla 2 sono le guide. Compiliamo una tabella per l'iterazione II (Tabella 7).

Tabella 7

Per prima cosa riempiamo la linea del vettore appena introdotto nella base, cioè la linea il cui numero coincide con il numero della linea guida. Qui la guida è la seconda riga. Gli elementi di questa riga sono nella tabella. 7 si ottengono dai corrispondenti elementi della tabella 6 dividendoli per l'elemento risolutivo (cioè per 8). Inoltre, nella colonna C b Annotiamo il coefficiente nella colonna del vettore inserito nella base. Quindi inseriamo gli elementi delle colonne per i vettori inclusi nella nuova base. In queste colonne, all'intersezione di righe e colonne di vettori con lo stesso nome, inseriamo le unità e tutti gli altri elementi sono impostati uguali a zero.

Per determinare gli elementi rimanenti della tabella. 7 applichiamo la regola del triangolo. Questi elementi possono anche essere calcolati direttamente utilizzando formule di ricorrenza.

Calcoliamo gli elementi della tabella. 7 in piedi in una colonna vettoriale R 0 . Il primo è nella prima riga di questa colonna. Per calcolarlo, troviamo tre numeri:

1) il numero nella tabella. 6 all'intersezione della colonna vettoriale R 0 e 1a riga (360);

2) il numero nella tabella. 6 all'intersezione della colonna vettoriale P 3a e 1a riga (12);

3) il numero nella tabella. 7 all'intersezione della colonna vettoriale R 0 e 2a riga (24).

Sottraendo al primo numero il prodotto degli altri due, troviamo l'elemento richiesto: 360 – 12 x 24 = 72; scrivilo nella prima riga della colonna vettoriale R 0 scheda. 7.

Secondo elemento di colonna del vettore R 0 scheda. 7 era già stato calcolato in precedenza. Per calcolare il terzo elemento di colonna di un vettore R 0 troviamo anche tre numeri. Il primo di essi (180) si trova all'intersezione della 3a riga e colonna del vettore R 0 scheda. 6, secondo (3) – all'intersezione della 3a riga e colonna del vettore P 3 tavoli 6, terzo (24) – all'intersezione della 2a riga e colonna del vettore R 0 scheda. 8. Quindi, l'elemento indicato è 180 - 24 x 3 = 108. Scriviamo il numero 108 nella terza riga della colonna vettoriale R 0 scheda. 7.

Senso F Lo 0 nella 4a riga della colonna dello stesso vettore può essere trovato in due modi:

1) secondo la formula, cioè

2) secondo la regola del triangolo; in questo caso il triangolo è formato dai numeri 0, -16, 24. Questo metodo porta allo stesso risultato: 0 - (-16) x 24 = 384.

Quando si determinano gli elementi della colonna vettoriale utilizzando la regola del triangolo R 0 il terzo numero, situato al vertice inferiore del triangolo, è rimasto sempre invariato e sono cambiati solo i primi due numeri. Teniamone conto quando troviamo gli elementi della colonna vettoriale P 1 tavolo 7. Per calcolare gli elementi indicati, prendiamo i primi due numeri dalle colonne dei vettori P 1 e R 3 tavoli 6, e il terzo numero è dalla tabella. 7. Questo numero si trova all'intersezione della 2a riga e colonna del vettore P 1 dell'ultima tabella. Di conseguenza, otteniamo i valori degli elementi richiesti: 18 – 12 x (3/4) =9; 5 – 3 x (3/4) = 11/4.

Numero nella quarta riga della colonna vettoriale P 1 tavolo 7 può essere trovato in due modi:

1) secondo la formula Z 1 -C 1 = (C,P 1) -C 1 abbiamo

2) secondo la regola del triangolo che otteniamo

Allo stesso modo, troviamo gli elementi della colonna vettoriale P 2 .

Elementi di colonna vettoriale R 5 viene calcolato utilizzando la regola del triangolo. Tuttavia, i triangoli costruiti per definire questi elementi sembrano diversi.

Quando si calcola l'elemento della prima riga della colonna specificata, si ottiene un triangolo formato dai numeri 0,12 e 1/8. Pertanto, l'elemento richiesto è 0 – 12x (1/8) = -3/2. L'elemento nella terza riga di questa colonna è uguale a 0 - 3 x (1/8) = -3/8.

Al termine del calcolo di tutti gli elementi della tabella. 7 in esso un nuovo piano di riferimento e coefficienti di espansione vettoriale si ottengono attraverso i vettori base P 4, P 3, P 6 e i valori e . Come si può vedere da questa tabella, il nuovo piano di riferimento per l'attività è il piano X=(0; 0; 24; 72; 0; 108). Con questo piano di produzione vengono realizzati 24 prodotti CON e restano inutilizzati 72 kg di materie prime di tipo 1 e 108 kg di materie prime di tipo III. Il costo di tutti i prodotti realizzati secondo questo piano è di 384 rubli. I numeri indicati sono scritti nella colonna del vettore R 0 scheda. 7. Come puoi vedere, i dati di questa colonna rappresentano ancora i parametri del problema in esame, sebbene abbiano subito cambiamenti significativi. Anche i dati nelle altre colonne sono cambiati e il loro contenuto economico è diventato più complesso. Quindi, ad esempio, prendi i dati della colonna vettoriale R 2 . Il numero 1/2 nella seconda riga di questa colonna mostra quanto dovrebbe essere ridotta la produzione dei prodotti CON, se prevedi di rilasciare un prodotto IN. Numeri 9 e 3/2 nella 1a e 3a riga del vettore P 2 mostrano, rispettivamente, quanta materia prima di tipo I e II sarà necessaria quando inserita nel piano di produzione di un prodotto IN e il numero - 2 nella quarta riga indica se è pianificato il rilascio di un prodotto IN, ciò garantirà un aumento della produzione in termini di valore di 2 rubli. In altre parole, se includi un prodotto nel piano di produzione IN, allora ciò richiederà una riduzione della produzione CON di 1/2 unità e richiederà costi aggiuntivi di 9 kg di materie prime di tipo I e 3/2 kg di materie prime di tipo III, e il costo totale dei prodotti fabbricati secondo il nuovo piano ottimale aumenterà di 2 rubli. Pertanto, i numeri 9 e 3/2 fungono da nuove "norme" per il costo delle materie prime dei tipi I e III per la fabbricazione di un prodotto IN(come si può vedere dalla tabella 6, in precedenza erano pari a 15 e 3), il che si spiega con una diminuzione della produzione del prodotto CON.

Anche i dati della colonna vettoriale hanno lo stesso significato economico R 1 tavolo 7. I numeri scritti nella colonna del vettore hanno un contenuto economico leggermente diverso R 5 . Il numero 1/8 nella seconda riga di questa colonna mostra che un aumento del volume delle materie prime di tipo II di 1 kg consentirebbe di aumentare la produzione di prodotti CON di 1/8 unità Allo stesso tempo sarebbero necessari ulteriori 3/2 kg di materie prime di tipo I e 3/8 kg di materie prime di tipo III. Aumento della produzione del prodotto CON di 1/8 unità porterà ad un aumento della produzione di 2 rubli.

Dal contenuto economico di cui sopra dei dati nella tabella. 7 ne consegue che il piano del problema trovato nell'iterazione II non è ottimale. Questo può essere visto dalla quarta riga della tabella. 7, poiché nella colonna del vettore P 2 di questa linea è un numero negativo - 2. Ciò significa che il vettore deve essere inserito nella base P 2, ovvero il nuovo piano dovrebbe prevedere la produzione di prodotti IN. Nel determinare il possibile numero di prodotti da fabbricare IN si dovrebbe tenere conto della quantità disponibile di materie prime di ciascun tipo, vale a dire: della possibile produzione di prodotti INè definito per , cioè troviamo

Pertanto il vettore deve essere escluso dalla base R 4 ovvero il rilascio del prodotto IN limitato dalle materie prime di tipo I a disposizione dell’impresa. Tenendo conto dei volumi disponibili di queste materie prime, l'azienda dovrebbe produrre 8 prodotti IN. Il numero 9 è l'elemento risolutivo e la colonna del vettore P 2 e 1a riga della tabella. 7 sono guide. Compiliamo una tabella per l'iterazione III (Tabella 8).

Tabella 8

Nella tabella 8, per prima cosa compiliamo gli elementi della 1a riga, che è la riga del vettore appena introdotto nella base R 2 . Gli elementi di questa riga sono ottenuti dagli elementi della 1a riga della tabella. 7 dividendo quest’ultimo per l’elemento risolutivo (cioè per 9). Inoltre, nella colonna C b di questa riga scriviamo .

Quindi inseriamo gli elementi delle colonne dei vettori base e, utilizzando la regola del triangolo, calcoliamo gli elementi delle colonne rimanenti. Di conseguenza, nella tabella. 8 otteniamo un nuovo piano di riferimento X=(0; 8; 20; 0; 0; 96) e coefficienti di espansione vettoriale tramite vettori base e valori corrispondenti e

Verifichiamo se il piano di riferimento fornito è ottimale oppure no. Per fare ciò, considera la quarta riga, tabella. 8. Non ci sono numeri negativi tra i numeri di questa riga. Ciò significa che il piano di riferimento trovato è ottimale e

Un piano produttivo, quindi, che prevede la realizzazione di 8 prodotti IN e 20 prodotti CON, è ottimale. Con questo piano di produzione dei prodotti, le materie prime di tipo I e II vengono completamente utilizzate e 96 kg di materie prime di tipo III rimangono inutilizzate e il costo dei prodotti fabbricati è di 400 rubli.

Il piano di produzione ottimale non prevede la realizzazione di prodotti UN. Introduzione al piano di produzione per i prodotti della tipologia UN comporterebbe una riduzione del costo totale dichiarato. Questo può essere visto dalla quarta riga della colonna vettoriale P 1, dove il numero 5 indica che per un determinato piano è compreso il rilascio di una unità di prodotto UN porta solo ad una diminuzione del costo totale di 5 rubli.

Questo esempio potrebbe essere risolto utilizzando il metodo del simplesso utilizzando una sola tabella (Tabella 9). In questa tabella, tutte e tre le iterazioni del processo computazionale sono registrate in sequenza, una dopo l'altra.

Tabella 9

Come si può vedere dalla tabella. 10, il piano di riferimento originario non è ottimale. Si passa quindi a un nuovo piano di riferimento. Questo può essere fatto perché nelle colonne dei vettori P 1 e P 5 , la cui quarta riga contiene numeri negativi, ha elementi positivi. Per passare a un nuovo piano di riferimento, introduciamo il vettore nella base P 5 ed escludere il vettore dalla base P 4 . Componiamo la tabella II di iterazione.

Tabella 11

Come si può vedere dalla tabella. 11, il nuovo piano di riferimento del problema non è ottimale, poiché si trova nella 4a riga della colonna vettoriale P 1 vale un numero negativo -11/3. Poiché nella colonna di questo vettore non sono presenti elementi positivi, questo problema non ha un piano ottimale.