Metodo del simplesso duale per la risoluzione di problemi di programmazione lineare. Soluzione del problema duale Soluzione del problema duale sul programma di produzione ottimale

Vengono fornite le formulazioni del primo e del secondo teorema di dualità. Viene mostrato come ottenere una soluzione ad un problema duale da una soluzione diretta utilizzando i teoremi della dualità. Esempi di risoluzione dei problemi.

Contenuto

Guarda anche: Regole per la composizione di problemi duali

Qui considereremo la questione di come ottenere una soluzione al problema duale risolvendo un problema diretto.

Teoremi di dualità

Primo teorema della dualità

Se uno dei due problemi duali ha una soluzione ottima, anche il problema duale ha una soluzione ottima. In questo caso, i valori delle funzioni obiettivo dei problemi diretti e duali per soluzioni ottime sono uguali tra loro.

Se uno di una coppia di problemi duali non ha soluzione a causa dell'illimitatezza della funzione obiettivo, allora il problema duale non ha soluzione a causa dell'incompatibilità del sistema di vincoli.

Secondo teorema della dualità

;

Applichiamo il secondo teorema della dualità. Sostituiamo i valori ottimi delle variabili nel sistema di vincoli del problema diretto.
(A1.1.1) ;
(A1.1.2) ;
(A1.1.3) ;
(A1.1.4) .
Poiché la prima e la quarta riga sono disuguaglianze rigorose (non sono uguaglianze), allora
E .

Poiché e , allora la 2a e la 4a riga del problema duale sono uguaglianze:

Sostituiamo i valori già trovati e , abbiamo:

Da qui
;
; .

Il problema duale ha la forma:
;

La sua decisione
;

Esempio 2

Dato un problema di programmazione lineare:
(A2.1.1) ;
(A2.1.2)
Trovare una soluzione a questo problema risolvendo graficamente il problema duale.

(A2.2.1) ;
(A2.2.2)

La soluzione al problema (A2.2) è riportata nella pagina “Risoluzione di problemi di programmazione lineare con il metodo grafico”. La soluzione del problema (A2.2) ha la forma:
; .

Secondo il primo teorema della dualità, il valore ottimale della funzione obiettivo è pari a
.

Applichiamo il secondo teorema della dualità. Sostituiamo i valori ottimi delle variabili nel sistema di vincoli del problema diretto (A2.2).
;
;
.
Poiché la terza linea è una disuguaglianza rigorosa (non sono uguaglianza), allora
.

Poiché e , allora la prima e la seconda riga del problema duale (A2.1) sono uguaglianze:

Sostituiamo il valore trovato.

Risolviamo un sistema di equazioni.
;
;
;
; ;
.

La soluzione del problema originale (A2.1) ha la forma:
; .

Guarda anche:

Un metodo in cui uno dei problemi reciprocamente duali viene prima risolto utilizzando il metodo del simplesso, e poi si trovano la soluzione ottima e quella ottima dell'altro problema utilizzando i teoremi della dualità è chiamato metodo del simplesso doppio.

Teorema 1 (Primo Teorema della Dualità). Se uno dei problemi reciprocamente duali ha una soluzione ottima, allora ce l’ha anche lei

un altro, e i valori ottimali delle loro funzioni obiettivo sono pari a:

Se la funzione obiettivo del problema originale non è vincolata, allora il sistema di vincoli del problema duale è incoerente.

Nota: il contrario della seconda parte del primo teorema della dualità non è vero nel caso generale.

Teorema 2. Componenti del piano ottimo per il problema duale ( avere la condizione di non negatività) sono uguali valori assoluti dei coefficienti

Componenti del piano ottimo per il problema duale ( non limitato dal segno) sono uguali valori dei coefficienti con le variabili corrispondenti della funzione obiettivo del problema originale, espressa in termini di variabili libere della sua soluzione ottima.

Teorema 3. Componenti positivi (diversi da zero) della soluzione ottima di uno dei problemi doppia coppia simmetrica corrispondono alle componenti zero della soluzione ottima di un altro problema, cioè per qualsiasi e:

Teorema 4 (Terzo Teorema della Dualità). Le componenti del progetto ottimo del problema duale sono pari ai valori delle derivate parziali della funzione lineare secondo gli argomenti corrispondenti, cioè

. (7.2)

Interpretazione economica del terzo teorema della dualità: i componenti del piano ottimo per il problema duale mostrano di quante unità monetarie cambierà il profitto (ricavo) massimo derivante dalla vendita di prodotti quando lo stock della risorsa corrispondente cambia di un'unità.

Esempio 9.1. Sulla base della soluzione dell'Esempio 5.2 (file “Algoritmo ed esempi del metodo del simplesso”), utilizzeremo il metodo del simplesso duale per determinare la soluzione ottima del problema duale.

Problema originale	Doppio problema

Questa doppia coppia è simmetrica. I problemi sono scritti in forma standard: riduciamoli alla forma canonica:

Problema originale	Doppio problema

Stabiliamo una corrispondenza tra le variabili di problemi reciprocamente duali.

Basato sulla soluzione dell'Esempio 5.2. La tabella simplex dell'ultima iterazione (Tabella 5.10) si presenta così:

Tabella 9.3

Secondo il Teorema 2, i valori ottimali delle variabili e saranno uguali ai valori assoluti dei coefficienti per le variabili corrispondenti della funzione obiettivo del problema originale, espressi attraverso le variabili libere della sua soluzione ottima.

Utilizzando la Tabella 9.3, scriviamo la funzione obiettivo del problema originale, espressa in termini di variabili libere della sua soluzione ottima:

Quindi, , .

Le variabili , , e non sono presenti nella funzione obiettivo (cioè i loro coefficienti sono pari a zero), pertanto i valori ottimali delle corrispondenti variabili , , e sono pari a zero.

In accordo con il Teorema 1, .

Pertanto, il valore ottimale della funzione obiettivo, che si ottiene a .

Esempio 9.2. Sulla base della soluzione del problema originale, trova la soluzione ottima del problema duale utilizzando il metodo del simplesso duale.

Problema originale	Doppio problema

Questa doppia coppia è asimmetrica. Portiamo il duplice problema in forma canonica.

Problema originale	Doppio problema

Per stabilire la corrispondenza tra le variabili della doppia coppia, introduciamo nel problema originale due variabili fittizie mancanti.

Problema originale	Doppio problema

Stabiliamo una corrispondenza tra le variabili di problemi reciprocamente duali.

Tabella 9.4

Variabili di corrispondenza di una doppia coppia

Risolviamo il problema originale utilizzando il metodo del simplesso.

Utilizzando il metodo Jordan-Gauss, selezioniamo nel sistema di vincoli del problema originale le variabili e ( Nota: non utilizzare variabili fittizie come variabili di base).

Come risultato delle trasformazioni, otteniamo la seguente matrice di coefficienti:

Il sistema di vincoli del problema originale assumerà la seguente forma:

Esprimiamo le variabili di base in termini di variabili libere, di conseguenza il problema originale assumerà la seguente forma:

Sostituendo i valori ottenuti delle variabili di base nella funzione obiettivo, assumerà la seguente forma:

Come risultato della risoluzione del problema originale trasformato utilizzando il metodo del simplesso all'ultima iterazione, otteniamo la seguente tabella del simplesso:

Tabella 9.5

Tavola simplex della soluzione ottima del problema originale

Struttura e proprietà del problema duale

Qualsiasi problema di massimizzazione di LP da un punto di vista economico può essere considerato come un problema di distribuzione di risorse limitate b 1 ,b 2 ,…,b m tra diversi consumatori, ad esempio tra alcuni processi tecnologici, che sono rappresentati dalle colonne A 1 , A 2 ,…A n della matrice dei vincoli del problema . Qualsiasi soluzione fattibile al problema LPx 1 ,x 2 ,…x n fornisce una distribuzione specifica che indica la quota di ciascuna risorsa che dovrebbe essere utilizzata nell'implementazione del corrispondente processo tecnologico.

Diamo un'occhiata a un esempio. L'impianto produce tre tipologie di prodotti x 1, x 2 e x 3, ciascuno dei quali richiede tempo dedicato alla lavorazione su torni, fresatrici e trapani. La quantità di tempo macchina per ciascuna macchina è limitata. Letc 1,c 2,c 3 – profitto dalla vendita di un'unità del tipo di prodotto corrispondente. È necessario determinare quanto di ciascun tipo di prodotto deve essere prodotto durante la settimana per ottenere il massimo profitto.

Formalmente, questo compito è scritto come segue:

massimizza (c 1 x 1 +c 2 x 2 +c 3 x 3) (1)

sotto restrizioni

a 11 x 1 + a 12 x 2 + a 13 x 3 ≤ b 1 ;

a21x1 + a22x2 + a23x3 ≤ b2 ;

a31 x 1 +a 32 x 2 +a 33 x 3 ≤b 3 , (2)

dove a 1 j ,a 2 j ,a 3 j è il tempo necessario per lavorare un'unità del tipo jesimo di prodotto, rispettivamente, su tornio, fresatrice e trapano (j = 1, 2, 3 b 1 , b 2 , b 3 – risorsa settimanale di tempo macchina, rispettivamente, per torni, fresatrici e foratrici.

Indichiamo y 1 , y 2 e y 3 – il prezzo di un'unità di tempo di funzionamento su torni, fresatrici e trapani. Allora a 11 y 1 +a 21 y 2 +a 31 y 3 – può essere interpretato come il costo di produzione di un’unità di prodotto del primo tipo a 12 y 1 +a 22 y 2 +a 32 y 3 – il costo; di fabbricazione di un'unità di prodotto del secondo tipo, ecc. .d.

Supponiamo che i prezzi delle risorse y 1 ,y 2 ,…,y m siano scelti in modo tale che siano soddisfatte le seguenti relazioni:

a 11 y 1 + a 21 y 2 + a 31 y 3 ≥ c 1 ;

a 12 y 1 + a 22 y 2 + a 32 y 3 ≥ c 2 ;

a 13 y 1 +a 23 y 2 +a 33 y 3 ≥ c 3. (3)

Poiché b 1 , b 2 e b 3 sono le risorse di tempo macchina utilizzate per ciascuna delle macchine, allora b 1 y 1 + b 2 y 2 + b 3 y 3 sono i costi di produzione totali.

È necessario trovare tali y 1 , y 2 e y 3 che soddisfino le condizioni (3), sotto le quali i costi di produzione totali sono minimizzati:

minimizza g(y 1 ,y 2 ,y 3)=b 1 y 1 +b 2 y 2 +b 3 y 3 (4)

a condizioni

y1 ≥0;y2 ≥0;y3 ≥0.

Questo problema si chiama duplice compito in relazione al problema (1), detto diretto.

Scriviamo ora i problemi diretti e duali nel caso generale.

Compito diretto:

massimizzare

a condizioni

(7)

Doppio problema:

minimizzare

a condizioni

(10)

In forma matriciale, una coppia di problemi duali è scritta come segue:

massimizzare

a condizioni

minimizzare

a condizioni

A T y≥c;

(15)

Confrontando le forme di registrazione dei problemi diretti e duali, si possono stabilire tra loro le seguenti relazioni:

se il problema diretto è un problema di massimizzazione, allora il problema duale sarà un problema di minimizzazione, e viceversa; coefficienti della funzione obiettivo del problema diretto c1,c2,…,cn

termini liberi dai vincoli del problema diretto b1,b2,...,bm diventano coefficienti della funzione obiettivo del problema duale;

la matrice dei vincoli del problema duale si ottiene trasponendo la matrice dei vincoli del problema diretto;

i segnali di disuguaglianza nelle restrizioni sono invertiti;

il numero di vincoli del problema diretto è uguale al numero di variabili del problema duale, e il numero di vincoli del problema duale è uguale al numero di variabili del problema diretto.

Le variabili y 1 ,y 2 ,…,y m del problema duale sono talvolta chiamate prezzi ombra.

È più vantaggioso risolvere un problema duale rispetto alla linea retta originale se in linea retta

un problema con un numero limitato di variabili ha un numero elevato di vincoli (m n).

La connessione tra le soluzioni ottime dei problemi diretti e duali è stabilita attraverso i seguenti teoremi di dualità.

TEOREMA 1. Se - soluzioni ammissibili di problemi diretti e duali, cioè allora

quelli. i valori della funzione obiettivo del problema diretto non superano mai i valori della funzione obiettivo del problema duale.

TEOREMA 2 (teorema fondamentale della dualità).Se -soluzioni ammissibili ai problemi diretti e duali e se , Quello – soluzioni ottime ad una coppia di problemi duali.

TEOREMA 3.Se nella soluzione ottima del problema diretto(5) – (7) io-esimo vincolo è soddisfatto come disuguaglianza rigorosa, allora il valore ottimo della corrispondente variabile duale è uguale a zero, cioè

Dove - io-esima riga della matrice A.

Il significato del Teorema 3 è il seguente. Se una certa risorsa è disponibile in eccesso e il vincolo i-esimo nella soluzione ottima è soddisfatto come disuguaglianza rigorosa, allora diventa insignificante e il prezzo ottimale della risorsa corrispondente è pari a 0.

Il Teorema 3 è completato dal Teorema 4, che stabilisce la relazione tra la soluzione ottima del problema diretto e i vincoli di quello duale.

TEOREMA 4. Se nella soluzione ottima del problema duale il vincoloJè soddisfatta come disuguaglianza rigorosa, allora il valore ottimo della corrispondente variabile del problema diretto deve essere uguale a zero, cioè se Quello

Diamo un’interpretazione economica del Teorema 4.

Poiché le quantità rappresentano quindi i prezzi delle risorse corrispondenti

è il costo del jesimo processo tecnologico, il valore è il profitto derivante dalle vendite per unità di prodotto. Pertanto, da un punto di vista economico, il Teorema 2.7 significa quanto segue: se il j-esimo processo tecnologico risulta essere strettamente non redditizio dal punto di vista dei prezzi ottimali delle risorse, allora nella soluzione ottima del problema diretto l'intensità di questo processo tecnologico dovrebbe essere uguale a 0.

Così esprime il Teorema 4 principio di redditività produzione organizzata in modo ottimale.

Da ciò consegue anche che

(20)

Assumiamo che tra le variabili x 1 ,x 2 ,…,x n del problema diretto ci sia un insieme di mvariabili che hanno valore diverso da zero nella soluzione ottima. Lasciamo, ad esempio, che queste siano le prime variabili in ordine.

Quindi, in base all’equazione (22), si ottengono le condizioni di mredditività:

(21)

Presentiamo altri due importanti teoremi della teoria della dualità.

TEOREMA 5 (teorema dell'esistenza).I problemi diretti e duali hanno soluzioni ottime se e solo se entrambi hanno soluzioni ammissibili.

TEOREMA 6 (teorema della dualità).Vettore validoX 0 è ottimale se e solo se il problema duale ha una soluzione così ammissibilesì 0 , Che cosa

Esiste la seguente relazione tra le soluzioni ottime dei problemi diretti e duali e gli elementi delle righe dell'indice delle tavole del simplesso corrispondenti a queste soluzioni:

i=1, 2, …,m;j=1, 2, …,n,

dove n è il numero di variabili del problema diretto; m è il numero dei suoi vincoli; sono gli elementi corrispondenti della linea indice rispettivamente dei problemi diretti e duali. Inoltre, se n+i, dove 1 ≤i≤m è maggiore del numero di vettori colonna della matrice dei vincoli della forma estesa del problema corrispondente, allora gli elementi si trovano riordinando ciclicamente gli elementi della riga dell'indice, a partire da con l'elemento

Caso generale di dualità

Nella sezione precedente, sono state stabilite le relazioni di base per una coppia di problemi di PL duali soggetti a vincoli sotto forma di disuguaglianze. Generalizziamo ora questi risultati al caso di restrizioni arbitrarie.

Sia dato il problema LP diretto nella forma:

massimizzare

a condizioni

Allora il duplice problema rispetto a (24)-(26) (o coniugato ad esso) è minimizzare la forma lineare:

minimizzare

a condizioni

Pertanto, un problema associato a un problema con condizioni miste viene compilato secondo le seguenti regole:

Se si assume che la variabile x j del problema diretto non sia negativa, allora la condizione j-esima del sistema di vincoli (28) è una disuguaglianza.

Se nessun vincolo di questo tipo viene imposto a x j, allora il jesimo vincolo del problema duale sarà l'uguaglianza.

I segni delle variabili del problema duale y i e le corrispondenti restrizioni del problema diretto sono correlati in modo simile. Notiamo che se poniamo m 1 = min 1 = n, otteniamo un caso speciale di una coppia di problemi duali con vincoli sotto forma di disuguaglianze.

Va notato che i metodi per risolvere i problemi di programmazione lineare includono non all’economia, ma alla matematica e all’informatica. Allo stesso tempo, l'economista deve fornire le condizioni più confortevoli per il dialogo con il software appropriato. A loro volta, tali condizioni possono essere fornite solo da ambienti di sviluppo dinamici e interattivi che abbiano nel loro arsenale una serie di librerie necessarie per risolvere tali problemi. Uno di questi ambienti di sviluppo software è sicuramente Python.

Formulazione del problema

Le pubblicazioni hanno considerato soluzioni a problemi di ottimizzazione diretta utilizzando il metodo di programmazione lineare e hanno suggerito una scelta ragionevole del risolutore scipy. ottimizzare.

È noto però che ad ogni problema di programmazione lineare corrisponde un problema cosiddetto distinto (duale). In esso, rispetto al problema diretto, le righe diventano colonne, le disuguaglianze cambiano segno, invece del massimo si cerca il minimo (o viceversa, invece del minimo si cerca il massimo). Il compito duale al duale è il compito originario stesso.

Risolvere il duplice problema è molto importante per analizzare l’utilizzo delle risorse. In questa pubblicazione si dimostrerà che i valori ottimi delle funzioni obiettivo nel problema originale e in quello duale coincidono (cioè il massimo nel problema originale coincide con il minimo nel problema duale).

I valori ottimali dei costi dei materiali e della manodopera saranno valutati in base al loro contributo alla funzione obiettivo. Il risultato saranno “stime oggettivamente determinate” di materie prime e manodopera che non coincidono con i prezzi di mercato.

Soluzione del problema diretto del programma di produzione ottimale

Considerando l'alto livello di preparazione matematica della stragrande maggioranza degli utenti di questa risorsa, non presenterò equazioni di bilancio con restrizioni superiori e inferiori e l'introduzione di variabili aggiuntive per passare alle uguaglianze. Pertanto, fornirò immediatamente le designazioni delle variabili utilizzate nella soluzione:
N – numero di tipologie di prodotti realizzati;
m – numero di tipologie di materie prime utilizzate;
b_ub - vettore delle risorse disponibili di dimensione m;
A_ub è una matrice di dimensione m×N, ciascun elemento della quale è il consumo di una risorsa di tipo i per la produzione di un'unità di prodotto di tipo j;
c è il vettore del profitto derivante dalla produzione di un'unità di ciascun tipo di prodotto;
x – i volumi richiesti di prodotti fabbricati di ciascun tipo (piano di produzione ottimale) garantendo il massimo profitto.

Funzione obiettivo
maxF(x)=c×x

Restrizioni
A×x≤b

Valori numerici delle variabili:
N=5; m=4; b_ub = ; A_ub = [, , ,]; c = .

Compiti
1. Trova x per garantire il massimo profitto
2. Trova le risorse utilizzate durante l'esecuzione del passaggio 1
3. Trova le risorse rimanenti (se presenti) quando esegui il passaggio 1

Per determinare il massimo (per impostazione predefinita viene determinato il minimo), i coefficienti della funzione obiettivo devono essere scritti con un segno negativo c = [-25, -35,-25,-40,-30] e ignorare il segno meno in davanti al profitto.

Notazioni utilizzate per visualizzare i risultati:
X– un array di valori variabili che forniscono il minimo (massimo) della funzione target;
allentamento– valori di variabili aggiuntive. Ad ogni variabile corrisponde un vincolo di disuguaglianza. Un valore variabile pari a zero significa che il vincolo corrispondente è attivo;
successo– Vero, se la funzione è riuscita a trovare la soluzione ottimale;
stato– stato della decisione:
0 – la ricerca della soluzione ottimale è stata completata con successo;
1 – è stato raggiunto il limite sul numero di iterazioni;
2 – il problema non ha soluzioni;
3 – la funzione obiettivo non è limitata.
nit– numero di iterazioni eseguite.

Elencazione della soluzione al problema di ottimizzazione diretta

#!/usr/bin/python # -*- codifica: utf-8 -*- importa scipy da scipy.optimize importa linprog # caricamento della libreria LP c = [-25, -35,-25,-40,-30] # elenco dei coefficienti della funzione obiettivo b_ub = # elenco dei volumi delle risorse A_ub = [, # matrice dei valori specifici delle risorse, , ] d=linprog(c, A_ub, b_ub) # cerca una soluzione per key,val in d.items(): print(key ,val) # output della soluzione if key=="x": q=#risorse utilizzate print("A_ub*x",q) q1= scipy.array(b_ub)-scipy.array (q) #risorse rimanenti print(" b_ub-A_ub*x", q1)

Risultati della risoluzione del problema
nit 3
stato 0

successo Vero
x [ 0. 0. 18.18181818 22.72727273 150. ]
A_ub*x
b_ub-A_ub*x [0. 0. 0. 90.90909091]
divertimento -5863.63636364
gioco [0. 0. 0. 90.90909091]

conclusioni

È stato trovato il piano ottimale per i tipi di prodotto
Rilevato utilizzo effettivo delle risorse
È stato trovato il resto del quarto tipo di risorsa inutilizzato [ 0. 0 0.0 0.0 90.909]
Non sono necessari calcoli secondo il passaggio 3, poiché lo stesso risultato viene visualizzato nella variabile margine di flessibilità

Soluzione del duplice problema sul programma di produzione ottimo

Il quarto tipo di risorsa nell'attività diretta non è completamente utilizzata. Allora il valore di questa risorsa per l’impresa risulta essere inferiore rispetto alle risorse che limitano la produzione, e l’impresa è disposta a pagare un prezzo più alto per l’acquisizione di risorse che aumentano i profitti.

Introduciamo un nuovo scopo per la variabile desiderata x come un prezzo “ombra” che determina il valore di una data risorsa in relazione al profitto derivante dalla vendita di prodotti manifatturieri.

C – vettore delle risorse disponibili;
b_ub è il vettore del profitto derivante dalla produzione di un'unità di ciascuna tipologia di prodotto;
A_ub_T – matrice trasposta A_ub.

Funzione obiettivo
minF(x)=c×x

Restrizioni
A_ub_T ×x≥ b_ub

Valori numerici e relazioni per le variabili:
c = ; A_ub_T trasporre(A_ub); b_ub = .

Compito:
Trova x che indica il valore per il produttore di ciascun tipo di risorsa.

Caratteristiche della soluzione con la libreria scipy. ottimizzare
Per sostituire le restrizioni dall'alto con le restrizioni dal basso, è necessario moltiplicare entrambe le parti del vincolo per meno uno – A_ub_T ×x≥ b_ub... Per fare ciò, scrivere i dati originali nella forma: b_ub = [-25, -35,-25,-40,-30]; A_ub_T =- scipy.transpose(A_ub).

Elenco delle soluzioni al problema di ottimizzazione duale

#!/usr/bin/python # -*- codifica: utf-8 -*- importa scipy da scipy.optimize importa linprog A_ub = [, , , ] c= b_ub = [-25, -35,-25,- 40,-30] A_ub_T =-scipy.transpose(A_ub) d=linprog(c, A_ub_T, b_ub) for key,val in d.items(): print(key,val)

Risultati della risoluzione del problema
no 7
messaggio Ottimizzazione terminata con successo.
divertimento 5863.63636364
x [ 2,27272727 1,81818182 6,36363636 0. ]
gioco [5.45454545 2.27272727 0. 0. 0. ]
stato 0
successo Vero

conclusioni

Il terzo tipo di risorsa ha il valore maggiore per il produttore, quindi questo tipo di risorsa dovrebbe essere acquistato per primo, poi il primo e il secondo tipo. Il quarto tipo di risorsa ha valore zero per il produttore e viene acquistata per ultima.

Risultati del confronto tra problemi diretti e duali

Il duplice problema espande le capacità di pianificazione del prodotto, ma utilizzando scipy. l'ottimizzazione viene risolta nel doppio del numero di iterazioni dirette.
La variabile slack mostra informazioni sull'attività dei vincoli sotto forma di disuguaglianze, che possono essere utilizzate, ad esempio, per analizzare i bilanci delle materie prime.
Il problema diretto è un problema di massimizzazione, il problema duale è un problema di minimizzazione e viceversa.
I coefficienti della funzione obiettivo nel problema diretto sono vincoli nel problema duale.
I vincoli nel problema diretto diventano coefficienti della funzione obiettivo in quello duale.
I segnali di disuguaglianza nelle restrizioni sono invertiti.
La matrice del sistema di uguaglianze viene trasposta.

Collegamenti

Poiché ci sono tre vettori unitari, allora
potrai trascrivere subito il piano di riferimento
X=(0,0,0,360,192,180).
Creiamo una tabella simplex zero

Controlliamo il piano di riferimento risultante
per l'ottimalità.
Calcoliamo il valore della funzione obiettivo e
differenze di simplesso.
F0 c P0 0 360 0 192 0 180 0,
1 z1 c1 c P1 c1 9,
2 z2 c2 cP2 c2 10,...

Come si può vedere dalla tabella 0, diverso da zero
sono le variabili x4 , x5 , x6 e x , x , x
1
2
3
sono uguali a zero, perché Non sono basilari, ma gratuiti.
Variabili aggiuntive x4, x5, x6
prendere i loro valori in base
restrizioni.
Questi valori variabili corrispondono a questo
"piano" in base al quale non si produce nulla, materie prime
non viene utilizzato e il valore della funzione obiettivo lo è
zero, ovvero il costo dei prodotti fabbricati
assente.
Questo piano, ovviamente, non è ottimale.
Ciò può essere visto anche dalla 4a riga della tabella, in cui
ci sono tre punteggi negativi: -9, -16 e -10.

10.

I numeri negativi non sono solo
indicare la possibilità di aumento
costo totale dei prodotti fabbricati (in
colonne sopra le valutazioni negative
sono numeri positivi), ma anche
mostra quanto aumenterà questo importo
quando si introduce un'unità di questo o quello nel piano
tipo di prodotto.
Quindi, il numero -9 significa che quando incluso in
piano di produzione per un prodotto A
prevede un aumento dei costi
prodotti per 9 unità

11.

Se includi nel piano di produzione per
un prodotto B e C, quindi il costo totale
i prodotti manifatturieri aumenteranno
rispettivamente da 10 e 16 unità. Pertanto, con
economicamente fattibile
è l'inclusione dei prodotti C nel piano.
Da quel momento in poi si dovrà fare lo stesso
considerare che -16 è il più piccolo
valutazione negativa. Quindi, alla base
introduciamo il vettore P3.

12.

Troviamo il numero Q.
360 192 180
Qmin
;
;
minimo 30; 24;60
3
12 8
Inseriamolo nell'ultima colonna della tabella.
Il numero 24 corrisponde al vettore P5.
192/8=24 dal punto di vista economico
significa quanti prodotti C
l'impresa può produrre tenendo conto
tassi di consumo e volumi disponibili di materie prime
ogni tipo.

13.

Poiché sono disponibili materie prime di ogni tipo
rispettivamente 360, 192 e 180 kg, e per uno
il prodotto C richiede la spesa di materie prime per ciascuno
tipi 12, 8 e 3 kg, quindi il numero massimo
prodotti C che possono essere fabbricati
impresa è uguale
min(360/12.192/8.180/3)=192/8=24, cioè
fattore limitante per la produzione
prodotti C è il volume disponibile di materie prime
2° tipo. Tenendo conto della sua impresa può
produrre 24 prodotti C. In questo caso le materie prime del 2° tipo verranno utilizzate completamente e,
Ciò significa che il vettore deve essere escluso
P5
base.

14.

Creiamo la seguente tabella. Dentro
la seconda riga è permissiva,
e la colonna risolutiva è la terza. SU
la loro intersezione contiene l'elemento 8.
Dividi la seconda riga per 8 e poi
zero utilizzando il metodo Jordan-Gauss
oppure secondo le formule del triangolo terzo
colonna.

15.

16.

Calcoliamo le differenze del simplesso e riempiamo la 4a riga della tabella.
Con questo piano di produzione
24 articoli C vengono prodotti e rimangono
inutilizzati 72 kg di materie prime 1° e 108 kg
materie prime del 3o tipo. 2° tipo di materia prima utilizzata
completamente. Il costo di tutti i prodotti a
a questo proposito è CU 384. Specificato
i numeri sono scritti nella colonna Piano. È di nuovo
parametri del compito, ma hanno subito
i cambiamenti. Anche i dati degli altri sono cambiati
colonne. Il loro contenuto economico
è diventato ancora più complesso.

17.

C'è una valutazione negativa -2.
Il piano può essere migliorato. Introduciamo le basi
vettore P2. Calcoliamo
72 24 108
Qmin ;
;
minimo 8; 48;728.
9 1/ 2 3 / 2
.
Deriviamo dalla base P4.

18.

Le linee permissive saranno la prima e la seconda
colonna. Elemento permissivo 9.
Dividere la prima riga per 9, compilare
Quindi la prima riga della nuova tabella
Ripristiniamo la seconda colonna. Per questo
moltiplicare la prima riga per (-1/2) e
aggiungi al 2° e poi moltiplica il 1°
riga per (-3/2) e aggiungi alla terza riga.
Compiliamo la tabella 2.

19.

20.

Ne siamo convinti
calcolo delle differenze del simplesso
1 cP1 c1 10 1 16 0,25 9 5,
2 cP2 c2 10 1 16 0 10 0,
3 cP3 c3 10 0 16 1 0 0 16 0,
4 cP4 c4 10 1/ 9 16 1/ 8 0 (1/ 6) 2 / 9,
5 cP5 -c5 =10 (-1/6)+16 5/24+0(-1/2)=5/3,
6 0.

21.

Il piano di produzione ottimale non lo è
è prevista la produzione dei prodotti A. Introduzione a
piano di produzione per i prodotti di tipo A comporterebbe
riduzione del costo totale indicato.
Questo può essere visto dalla quarta riga della colonna, dove il numero è 5
dimostra che con questo piano l'inclusione
ad esso conduce la produzione di una unità del prodotto A
solo una diminuzione del valore totale
valore di 5 unità
Quindi, il piano prevede il rilascio di 8 prodotti
B e 20 prodotti C. Materie prime di tipo 1 e 2
viene utilizzato interamente e il tipo 3 rimane inutilizzato per 96 kg.

22. PROBLEMI DI PROGRAMMAZIONE LINEARE DOPPIA

Ogni ZLP può essere abbinato
problema chiamato duale rispetto a quello originale
compito.
Consideriamo il problema dell'utilizzo
risorse. Supponiamo che l'impresa A
produce n tipi di prodotti, valore
il cui rilascio è determinato da variabili
x1, x2, ..., xn
.
In produzione sono diversi
tipi di risorse, il cui volume è limitato
valori b1, b2, ..., bn.

23.

I tassi di costo di ciascuna risorsa per unità sono noti
ogni tipo di prodotto che forma una matrice,
a11
a21
UN
...
am1
a12
a22
...
sono le 2
...a1n
...a2n
... ...
...am
così come il costo per unità di produzione di ciascun tipo
c1, c2, ..., cn
È necessario organizzare la produzione in questo modo
all'impresa A è stato fornito il massimo
profitto.

24.

Il compito si riduce a trovare
variabili non negative
x1, x2, ..., xn,
in cui il consumo di risorse non lo è
supera il numero specificato e
il costo di tutti i prodotti raggiungerà
massimo.

25.

In forma matematica il problema
è scritto nella seguente forma:
F c1 x1 c2 x2 ... c j x j ... cn xn max
a condizioni
a11 x1 a12 x2 ... a1 j x j ... a1n xn b1 ,
a21 x2 a22 x2 ... a2 j x j ... a2 n xn b2 ,
.
...............................................................,
a x a x... a x... a x b
mj j
mn
M
m1 1 m2 2
xj0, j1, n.

26.

Sulla base degli stessi dati iniziali, potrebbe essere
è stato formulato un altro compito.
Supponiamo che l'impresa B decida di acquistare
tutte le risorse a disposizione dell’impresa A. B
In questo caso, l’impresa B deve stabilirsi
prezzi ottimali per queste risorse, basati su
seguenti condizioni:
costo totale delle risorse per l’impresa B
dovrebbe essere minimo;
per ogni tipo di risorsa di cui l'impresa A ha bisogno
pagare non meno dell'importo che esso
l'impresa può ricevere durante la lavorazione
di questo tipo di risorsa in prodotti finiti.

27.

Se indicato con y1 , y2 , ..., yn
prezzi ai quali l’impresa B
acquista quindi risorse dall’impresa A
il compito si riduce a quanto segue: trovare
tali valori delle variabili y1, y2, ..., yn,
al quale il costo delle risorse,
speso per unità di qualsiasi tipo
i prodotti non sono inferiori al profitto (prezzi)
per questa unità di produzione e il totale
il costo delle risorse raggiunge
minimo,

28.

cioè quale dovrebbe essere la valutazione dell'unità
ciascuna delle risorse y1, y2, ..., yn,
quindi per dati volumi
risorse disponibili bi , date
costa c j (j 1, n) unità
prodotti e standard di costo aij
minimizzare la stima dei costi complessivi
per tutti i prodotti.

29. Mat. modello a doppio problema

In forma matematica il problema
è scritto come:
*
F b1 y1 b2 y2 ... bm ym min
sotto restrizioni
a11 a1 a21 y2 ... am1 am c1 ,
sì sì sì... sì sì,
m2 m
2
12 1 22 2
..................................................
sì sì sì... sì sì,
mn m
N
1n1 2n2
sì 0, io 1, 2,..., m.

30. Significato economico delle variabili del problema duale

Variabili yi del problema duale in letteratura
possono avere nomi diversi: contabile, implicita,
ombra, valutazioni oggettivamente determinate,
duplici valutazioni o “prezzi” delle risorse.
Questi due problemi formano una coppia reciprocamente
doppi problemi, ognuno dei quali può
essere considerato originale. La soluzione a uno
le attività forniscono un piano di produzione ottimale
prodotti e la soluzione è diversa: ottimale
sistema di classificazione delle materie prime utilizzate
produzione di questi prodotti.

31.

Problemi duali di lineare
si chiama programmazione
simmetrici se soddisfano
le seguenti proprietà:
numero di variabili in un problema duale
è uguale al numero di vincoli del problema originale, e
numero di vincoli del problema duale
uguale al numero uguale al numero di variabili in
originale;
in un problema si cerca il massimo dell'obiettivo
funzioni, nell'altro – un minimo;
coefficienti per le variabili nell'obiettivo
le funzioni di un'attività sono gratuite
membri del sistema di vincoli di un altro problema;

32.

in ogni problema è specificato il sistema di vincoli
sotto forma di disuguaglianze e nel problema della ricerca
massimo, tutte le disuguaglianze della forma “≤”, e nel problema su
trovare il minimo, tutte le disuguaglianze della forma “≥”;
matrice dei coefficienti del sistema di vincoli
l'uno si ottiene dall'altro per trasposizione;
ogni vincolo di un problema corrisponde
variabile di un'altra attività, numero variabile
corrisponde al numero di restrizione;
Condizioni per variabili non negative
vengono salvati in entrambe le attività;

33. Risoluzione di problemi duali simmetrici

Primo teorema della dualità.
Se uno dei doppi problemi
ha una soluzione ottima, allora
un altro ha una soluzione ottima
compito, mentre i valori target
le funzioni dei compiti sono uguali tra loro.
Se la funzione di destinazione è una di
i compiti non sono limitati, quindi un altro compito
non ha alcuna soluzione

34. Contenuto economico del primo teorema della dualità

Se il problema di determinare il piano ottimale,
massimizzare la produzione è quindi risolvibile
Anche il problema di determinare le stime delle risorse è risolvibile.
Inoltre, il prezzo del prodotto ottenuto di conseguenza
l’attuazione del piano ottimale coincide con
valutazione complessiva delle risorse.
Coincidenza dei valori della funzione target per
soluzioni corrispondenti a una coppia di problemi duali
abbastanza perché queste decisioni siano
ottimale.
Risolviamo lo ZLP utilizzando il metodo del simplesso, simultaneamente
Risolviamo sia il problema originale che quello duale.

35. Metodo per la soluzione simultanea di una coppia di problemi duali

Problema originale: Doppio problema:
F c1x1 c2 x2 ... c j x j ... F * b1 y1 b2 y2 ...
cnxnmax
a11 x1 a12 x2 ... a1n xn xn 1 b1 ,
a21 x1 a22 x2 ... a2 n xn xn 2 b2 ,
..........................................................
a x a x ... a x x b ,
mn
n m
M
m1 1 m2 2
x j 0, j 1, 2,..., n m.
bm mmm min,
a11 y1 a21 y2 ... am1 ym ym 1 c1 ,
sì sì sì... sì sì sì,
m2 m
m2
2
12 1 22 2
.............................................................
sì sì sì... sì sì sì,
mn m
m n
N
1n1 2n2
sì 0, io 1, 2,..., m n.

36.

Il numero di variabili nei problemi è lo stesso
ed è uguale a m + n. Nel problema originale
le variabili di base sono

variabili xn 1 , xn 2 , ..., xn m
,
e nel duplice problema –
ausiliario non negativo
variabili yn 1, yn 2, ..., yn m.
Variabili fondamentali di un problema
corrispondono variabili libere
un altro compito e viceversa.

37.

38.

Quando si risolve lo ZLP utilizzando il metodo del simplesso tabulare, si risolve il duplice problema
contenuto nell'ultima riga della tabella.
Questo è j.
Inoltre, le principali variabili del duale

corrispondente aggiuntivo
variabili del problema originale, e
variabili aggiuntive del duale
le attività sono contenute in colonne,
corrispondente al principale
variabili iniziali (originarie).
compiti.

39. Esempio.

Formuliamo un modello del problema duale
al problema dell'esempio 2 (inizio della lezione):
Trovare il massimo di una funzione

40.

41.

Le variabili del problema originale x1, x2, x3 sono il numero di prodotti A, B e C. Introduciamo
variabili del problema duale y1, y2, y3
Trova il minimo di una funzione
F* 360 y1 192 y2 180 y3 min
sotto restrizioni
18 a1 6 a2 5 a3 9,
15 a1 4 a2 3 a3 10,
12 e 8 e 3 e 16,
2
3
1
y1, y2, y3 0.

42. Considera l'ultima tabella del problema originale

43.

Il valore di y1 nell'ultima riga della colonna P4,
quelli. y12;
9 anni 5
valore 2 3 nell'ultima riga della colonna P5,
il valore di y3 0 nell'ultima riga della colonna P6.
I restanti valori si trovano nelle colonne 1,2,3.
2 5
Sì (; ;0;5;0;0)
9 3
In cui
2
5
F 360 192 180 0 0 5 0 0 0 0 400
9
3
*
- Questo è il costo minimo per tutti i prodotti.
2/9 e 5/3 sono i prezzi ombra delle materie prime del 1° e 2°
specie rispettivamente.