Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
vuoi
o PayPal
tutte le volte che vuoi
Dimostrazione che il problema duale del duale è il problema primale
Dim.
Dimostriamo il risultato per un problema di PL in forma generale. La generalizzazione a un generico problema di PL deriva dal fatto che un problema di Programmazione Lineare può essere sempre scritto nella sua forma generale.
Consideriamo un problema di PL in forma generale:
Tmin c x(P ) Ax >= b s x >= 0 n
Dim. Nella coppia primale-duale il problema duale è:
Tmax b uT(D ) A u <= c s u >= 0 m
Riducendo il problema duale D alla forma canonica si ottiene:
T-min - b uT(D ) - A u >= -c s u
>= 0 mCalcolando il problema duale del problema D otteniamosT-max – c vT TD(D ) – (A ) = v <= -bsv >= 0 n T TNotiamo che (A ) = AIl problema D(D ) si può riscrivere comesTmin c v T TD(D ) – (A ) = v <= -bsv >= 0 nMoltiplicando per – 1tutte le righe del sistema di disequazionipossiamo riscrivere il problema come segueTMin c vD(D ) Av >= bsV >= 0 nDunque D(D ) = P onde la tesis s’08. Spiegare le possibili relazioni che legano due problemidi PL che siano l'uno il duale dell'altroLe due tabelle sono uguali basta invertire il titolo e le scritteMassimizzazione con MinimizzazioneConclusioneIn questa attività abbiamo dimostrato che per ogni coppiaprimale/duale1. Il duale del duale è il primale2. Ogni soluzione ammissibile di un problema primale diminimizzazione [massimizzazione] ha valore non inferiore [nonsuperiore] a quello di ogni soluzione ammissibile del relativoproblema duale.La proprietà 2. vieneanche detta dualità debole09. Dimostrare che se il problema primale di massimizzazione è illimitato superiormente allora il problema duale è inammissibile. Se il problema primale di massimizzazione è illimitato superiormente, allora il problema duale è inammissibile. Dim. Dimostriamo il risultato per un problema di PL di massimizzazione in forma generale. Supponiamo che il problema primale sia illimitato superiormente e che il problema duale ammetta una soluzione ammissibile y trattino sopra. Per la proprietà 2., per ogni soluzione ammissibile x trattino sopra del problema primale risulta T * C x trattino sopra >= b * y trattino sopra Dim. T Quindi esiste un valore L = b * y trattino sopra tale che ogni soluzione ammissibile del problema P abbia valore non inferiore a L. Pertanto il problema primale non è illimitato superiormente, contraddicendo l'ipotesi. Quindi il problema duale non può ammettere soluzioni ammissibili, ovvero è inammissibile.LEZ 1808. Dimostrare che se il problema primale è inammissibile allora il problema duale è illimitato o inammissibile
Se il problema è inammissibile allora il problema duale è limitato o inammissibile
Se il problema primale è inammissibile, allora il suo duale non può ammettere soluzione ottima
Infatti, se il duale ammette una soluzione ottimale, per la proprietà 5 anche il primale ammette soluzione ottima
Quindi il problema duale non può ammettere soluzione ottima e quindi può essere illimitato oppure inammissibile
09. Enunciare e dimostrare il teorema della dualità forte
Se uno dei due problemi di una coppia primale/duale ammette soluzione ottima x*, allora anche l'altro ammette una soluzione ottima y* e i valori delle due soluzioni sono uguali
T Tc x* = b y*
Senza perdita di generalità, dimostriamo il risultato per un problema di PL di minimizzazione in forma standard. La generalizzazione deriva dal fatto
che un problema di Programmazione Lineare può essere sempre scritto nella sua forma standard. Per simmetria, possiamo dimostrare il solo caso che sia il primale a ammettere soluzione ottima. Supponiamo che il problema primale di minimizzazione ammetta soluzione ottima. Notiamo che il problema duale non può essere illimitato superiormente. Se infatti lo fosse, per la proprietà 4 il suo duale sarebbe inammissibile. Per la proprietà 1 tale duale è il problema primale, che quindi risulterebbe inammissibile contraddicendo l'ipotesi di ammettere una soluzione ottima. Dimostriamo che il problema duale non può essere inammissibile e che ammetta una soluzione ammissibile y (trattino sopra). Se il problema primale di minimizzazione in forma standard ammette soluzione ottima, allora esiste una soluzione di base ottima T^-1 * Tx* = (x* x*) = (B b 0)B N n-m T. Consideriamo i costi in forma canonica c = (c c)B N TN TB^-1. Per l'ottimalità di x* abbiamo che i...costi ridotti y = c - c B N sononon negativi TN TB -1 TN TB -1c - c B N >= 0 -> c >= c B NT TB -1 TN TPonendo beta = c B abbiamo c >= beta NPre-moltiplicando il vettore beta per la matrice A otteniamoT T T Tbeta A = beta [B N] = [beta B beta N]T TB -1 TBDal momento che beta B = c B B = cPossiamo scrivere T T TB TB -1 TB TN TbetaTA = [beta B beta N] = [c c B N] <= [c c ] = cTDa cui risulta A beta <= cQuindi y(trattino sopra) = beta è una soluzione ammissibile per ilproblema duale, che per tanto è non vuoto.Il valore della soluzione duale y(trattino sopra) èT T TB -1 TB Tb beta = beta b = c B b = c x* = c x*BChe è pari al valore della soluzione ottima primale x(trattino sopra)T Tb y(trattino sopra) = c x*Quindi y* = y(trattino sopra) è una soluzione ottima duale, da cui latesiLEZ 1901. Enunciare e dimostrare le condizioni dicomplementarietà per la coppia primale/duale simmetricaSi consideri la coppia primale/duale
simmetricaT Tmin c x max b xT(P ) Ax>=b (D ) A y<=cs sx>=0 y>=0n m
Date due soluzioni ammissibili x(trattino sopra) e y(trattino sopra) per il primale e il duale, x(trattino sopra) e y(trattino sopra) sono ottime per i rispettivi problemi se e solo se soddisfano le seguenti condizioni di complementarietà:
T Tx(trattino sopra) (c-A y(trattino sopra))=0
Ty(trattino sopra) (Ax(trattino sopra) -b)=0
Dimostriamo che se x(trattino sopra) e y(trattino sopra) soddisfano le condizioni di complementarietà allora sono ottime per i rispettivi problemi.
Siano dunque x(trattino sopra) e y(trattino sopra) t.c.
T Tx(trattino sopra) (c-A y(trattino sopra))=0
Ty(trattino sopra) (Ax(trattino sopra) -b)=0
e quindi
N.B. le x e y sono tutte con il trattino sopra fino alla fine
T T T T T T T Tx (c-A y) = x c – x A y = 0 -> x c = x A y
T T T T Ty (Ax-b) = y Ax-y b = 0 -> y Ax = y b
T T T Ricordando che (x A y)T = y Ax possiamo scrivere
T T T T T Tx c = x A y -> c x = y Ax = y b
Da cui
risulta che x e y sono soluzione ammissibile con uguali valori della funzione obiettivo: per la proprietà 3, questo implica che x e y sono ottime. Dimostriamo che se x e y sono ottime per i rispettivi problemi allora soddisfano le condizioni di complementarietà. Se sono ottime, per la proprietà 3 hanno pari valore della funzione obiettivo c^T x = b^T y. Inoltre sono soluzioni ammissibili e quindi risulta A x >= b, x >= 0, A^T y <= c, y >= 0. Per la non negatività di x e y, pre-moltiplicando ambo i termini dei vincoli primali e duali il segno delle disequazioni non cambia: A x >= b, y >= 0 A^T y <= c, x >= 0 ovvero: A x >= y b, A^T y <= x c Dal momento che c^T x = b^T y abbiamo necessariamente che: y^T b = y^T A x = x^T A^T y = x^T c da cui risulta: y^T b = y^T A x -> y^T (b - A x) = 0 x^T A^T y = x^T c -> x^T (A^T y - c) = 0 LEZ 2107. Descrivere quali sono le principali differenze tra la Programmazione Lineare Intera e la Programmazione Lineare {0,1}. Un problema di Programmazione Lineare Intera permette che le variabili decisionali siano intere, mentre un problema di Programmazione Lineare {0,1} permette che le variabili decisionali siano solo 0 o 1.Programmazione Lineare Intera
Programmazione Lineare Intera è un problema di PL in cui le variabili sono vincolate ad assumere valori interi (nell'insieme Z). Se la restrizione riguarda un sottoinsieme proprio delle variabili il problema si dice di Programmazione Lineare Intera Mista.
I problemi di PLI e MILP sono tipicamente caratterizzati da:
- indivisibilità delle risorse
- necessità di scegliere da un numero finito di possibili alternative
Un problema di Programmazione Lineare {0,1} PL01 è un problema di PLI in cui le variabili sono vincolate ad assumere valori binari nell'insieme {0,1} e rappresentano la possibilità che un evento si verifichi oppure no.
Definizione del processo di formulazione di un problema di Programmazione Lineare Intera
Il processo di associazione di un modello matematico a un problema reale viene detto formulazione del problema. Il processo di formulazione consiste nell'identificare il sistema di equazioni e/o disequazioni lineari che, congiuntamente
Le restrizioni di interezza sulle variabili di decisione, definiscono la regione ammissibile.
L'obiettivo del processo di formulazione è identificare un problema di PLI, vale a dire un problema di ottimizzazione nella forma:
Tmin c x
Ax<=bn
x € Z
Dati due formulazioni di un problema, definire l'equivalenza tra le due formulazioni.
Dato un problema, è possibile in linea di principio definire diverse formulazioni.
Due formulazioni si definiscono equivalenti se entrambe identificano lo stesso insieme delle soluzioni ammissibili S.
Dati due problemi di PL, definire l'equivalenza tra i due problemi.
Due problemi (P1) e (P2) di PL, con regioni ammissibili X1 e X2 rispettivamente, si definiscono equivalenti se:
- Sono entrambi inammissibili
- Sono entrambi illimitati
- Ammettono entrambi soluzioni ottime finite ed esistono due trasformazioni f: X1 -> X2 e g: X2 -> X1 t.c.
- Per ogni soluzione ottima x* di P1 il vettore f(x*) è soluzione di P2
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
