Dualità nei problemi di programmazione lineare
Dualità nei problemi di programmazione lineare!
Per ogni problema di programmazione lineare, esiste un problema univoco corrispondente che coinvolge gli stessi dati e descrive anche il problema originale. Il problema originale è chiamato programma principale e il corrispondente problema univoco si chiama Dual program. I due programmi sono strettamente correlati e la soluzione ottimale del doppio fornisce informazioni complete sulla soluzione ottimale del primitivo e viceversa.
Diversi aspetti utili di questa proprietà sono:
(a) Se il primale ha un numero elevato di gruppi di continuità e un piccolo numero di variabili, il calcolo può essere considerevolmente ridotto convertendo il problema in Dual e poi risolvendolo.
(b) La dualità nella programmazione lineare ha alcune conseguenze di vasta portata di natura economica. Questo può aiutare i manager a rispondere a domande su corsi d'azione alternativi e i loro valori relativi.
(c) Il calcolo del doppio verifica l'accuratezza della soluzione primaria.
(d) La dualità nella programmazione lineare mostra che ciascun programma lineare è equivalente a un gioco a somma zero di due persone. Ciò indica che esistono relazioni abbastanza strette tra la programmazione lineare e la teoria dei giochi.
1. Formando Dual quando Primal è in forma canonica:
Dai due programmi precedenti, i seguenti punti sono chiari:
(i) Il problema di massimizzazione nel primale diventa il problema di minimizzazione nel duale e viceversa.
(ii) Il problema della massimizzazione ha () vincoli.
(iii) Se il primale contiene n variabili e m vincoli, il doppio conterrà m variabili e n vincoli.
(iv) Le costanti b 1 b 2, b 3 ......... b m nei vincoli del primale appaiono nella funzione obiettivo del duale.
(v) Le costanti c 1, c 2, c 3 c n nella funzione obiettivo del primale appaiono nei vincoli del duale.
(vi) Le variabili in entrambi i problemi sono non negative.
Le relazioni di vincolo del primitivo e del duale sono rappresentate di seguito.
Esempio 1:
Costruisci il duale al problema principale
Soluzione:
Innanzitutto, il vincolo ≥ viene convertito in ≤ vincolo moltiplicando entrambi i lati per -1.
Esempio 2:
Costruisci il duale al problema principale
Soluzione:
Sia Y 1, Y 2, V 3 e V 4 siano le corrispondenti due variabili, quindi il doppio problema è dato da
Poiché il doppio problema ha un numero minore di vincoli rispetto al primo (2 anziché 4), richiede un lavoro e uno sforzo minori per risolverlo. Ciò deriva dal fatto che la difficoltà computazionale nel problema di programmazione lineare è principalmente associata al numero di vincoli piuttosto che al numero di variabili.
Esempio 3:
Costruisci il doppio del problema
Soluzione:
Poiché il problema dato è di minimizzazione, tutti i vincoli dovrebbero essere di> tipo. Moltiplicando il terzo vincolo di -1 su entrambi i lati otteniamo.
-8x 1 + 2x 2 + 2x 3 ≥ -10
Il doppio del problema dato sarà
dove y 1, y 2, y 3, y 4 e y 5 sono le due variabili associate rispettivamente al primo, al secondo terzo, al quarto e al quinto vincolo.
