Problemi di programmazione lineare e metodo del simplesso (algoritmo di applicazione)

Il duale del Problema Lineare

min c^Tx

A.x ≥ b (ℤ)

-λ x ≤ -b (Q)

max b^Tu

A^Tu ≤ c (D.V.)

• u≥0

Proprietà:

• Il Duale di un problema di minimizzazione è un problema di massimizzazione e viceversa.
• Ad ogni vincolo di disuguaglianza del Primo è associato un vincolo nel Duale non vincolato, il segno che ha come coefficienti nella funzione obiettivo duale il segno mutato del vincolo primale associato.
• Ad ogni variabile non vincolata in segno del Primo è associato un vincolo in disuguaglianza del Duale, il cui primo noto è dato dal coefficiente della funzione obiettivo primale.

Dualità del Problema di Programmazione Lineare

min c^tx (1) ⇔ min c^ty (P)

A x ≥ b

-A x ≤ -b

max c_t u^t(A-b) ≥ 0 ⇒ max b^tu

-A^tu ≤ c,

u ≥ 0

ρ(u) = inf_{x, s ≥ 0} (c^tx - u^t(A x-b)) = inf_{y, s ≥ 0} (b^tu + (c-A^tu)_k) = -20 Il Duale del...

Proprietà

• Il Duale di un problema di minimizzazione...
• A ogni vincolo di disuguaglianza del Primo è associato...
• A ogni variabile associata a un vincolo di disuguaglianza...
• A ogni variabile non associata a un vincolo...

Metodo Diretto

Proprietà:

Se _(x,y) è un punto ammissibile tra il Primo e (c,0,1) è un punto ammissibile tra il Duale allora c* + d y* + f ≥ a v + b v*

Se esistono un punto (x,y) ammissibile tra il Primo ed un punto (z,0,1) ammissibile tra il Duale tale che:

c* x + d y* = W* + q v*

Allora (x,y,z) è uno soluzione ottima per il Primo e (0,z) è uno soluzione ottima per il Duale

Se il Primo è illimitato inferiormanete allo (z,0,1) è non ammissibile

Viceversa il Duale è illimitato superiornmanete allo (z,0,1) è non ammissibile

Metodo Forte

Se il Primo ammette una soluzione ottima (x,y) allora anche il Duale ammette una soluzione ottima (u,v) mantenendo due archi v uguali nell'altro l'arco della funzione obbiettivo che deve prevalebbe dell'ultimo sono uguali

c* x + d y* = a u + b v* = q v*

Possibilità grafiche e teoriche presentati

Schema

• Ottimo finito Sì No No No
• Primale illimitato inf No No Sì
• ineammissibile No S Ottimo finito illimit. sup. Sì ineammissibile

Condizioni di complementarità:

Sia (ŷ, ū) un vettore ammissibile del Primale e sia (v̂, q̂) un vettore ammissibile del Duale. Allora (ŷ, ū) e (v̂, q̂) sono soluzioni ottime del Primale e Duale se e solo se soddisfano la seguente condizione:

ŷ^T(ĉ - ŶZ + F̂T q̂ - â) = 0

v̂^T(ĉ - ĈL û - èT v̂) = 0

con

• a) min ĉx + dT y
• Cx + Dy = h
• x + Ey = q
• x ≥ 0
• b) Max hT u + qT v
• dT u + qT v ≤ c
• û + F̂T v̂ = d
• v ≥ 0

Criterio 1

Stesso degli di ↑

ŷ^T (ĉ - ŶZ + F̂T q̂ - â) = 0

x^T(ĈL û - èT v̂) ≥ 0

i = 1 ... p j = 1 ... m

Prova

Per il Teorema (ŷ, x̂), e (û, v̂) sono soluzioni ottime di a) e b) se:

ŷ^T(ĉ - ŶZ + F̂T q̂ - â) = 0

x^T(ĈL û - èT v̂) ≥ 0

sono nulli Poichè (ŷ, x̂) è l'ammissibilità di b) x̂ ≥ 0 ŷ ≥ 0 v ≥ 0 e (û, v̂) ammissibilità di b) e ĉx + dTy = 0 so che quindi area dei prodotti scalari deve essere nullo

Criterio 2

stesso del di ↑

Elenco:

1. ∀ i ŷi = 0 Vincolo Duale deve essere soddisfatto dell'inequaglianza
2. ∀ j ŷj = 0 Vincolo Primale deve essere soddisfatto dell'inequaglianza

Generalità di iperreale "M Y Q12"

Relazioni

Sia 0 in un iperreale di R^12 con numero reale L'insieme:

• 4 = { x Є R^12, 0^T x = 5 }
• è detto, insieme degli zeri, di 0^T x=b; gli insiemi:
• S ≤ = { x Є R^12, 0^T x ≤ b }
• S ≥ = { x Є R^12, 0^T x ≥ b }
• sono detti, semispazi chiusi: definiti dalla disequazione 0^T x ≤ b, e 0^T x ≥ b.

Un insieme P Є R^12 è un policadico se il riflesso dei, di un numero finito di semispazi chiusi e aperti, è un indicato convesso, detto nella forma.

Un sotto P Є R^12 è un policadico se esistono uno matrici A Є R^(m*m) ed un sotto b Є R^P tali che

• P = { x Є R^n } | A x ≤ b }

Un policadico si intende convesso(a)

Prove

Consideriamo due generi, vetori x ed y Є P. Vogliamo dimostrare che ogni vettor, z = β x + (1 - β) y as β ≤ 1 qualsiasi a P, avara soddisfa:

• A z ≥ b

Ricordiamo che 1 x ≥ b 1 y ≥ b se ha

A z = A (β x + (1 - β) y) = β A