Programmazione lineare - significati dual simplex variabili?

Question

Ho appena appreso il metodo simplex per la risoluzione di programmi lineari e sto cercando di capire qual è il duplice problema.

Capisco i meccanismi per risolvere un duplice problema: non ho bisogno di aiuto. Quello che non riesco a ottenere (anche dopo averlo letto su Wikipedia) è il significato effettivo delle variabili e nel doppio.

Vorrei fare un esempio tutti insieme di significati variabili nel problema primordiale, e quello che ho capito del doppio, e sarebbe chiedere a chiunque così gentile da spiegare il significato del duplice:

Primal:

max z = 3*x1 + 5*x2 

subject to: 
      x1   <= 4 
       2*x2 <= 12 
     3*x1 + 2*x2 <= 18 

     x1, x2 >= 0 

Nel problema primordiale, x1 e x2 sono quantitativi di prodotti a e B da produrre. e sono rispettivamente i loro prezzi di vendita unitari. I prodotti sono prodotti su 3 macchine, M1-M3. Per produrre un primo prodotto, sono necessari un'ora di lavoro su M1 e 3 ore su M3. Per produrre il secondo, sono necessarie due ore di lavoro su entrambi M2 e M3. Macchine M1, M2, M3 possono funzionare per un massimo di 4, 12 e ore, rispettivamente. Infine, non posso produrre una quantità negativa di nessuno dei prodotti.

Ora, ho impostato il duplice problema:

min z = 4*y1 + 12*y2 + 18*y3 

subject to: 
      y1   + 3*y3 >= 3 
        y2 + 2*y3 >= 5 

      y1, y2, y3 >= 0 

Ora, l'unica cosa che penso di poter capire è che i vincoli significa: - per un'ora di lavoro su M1 e 3 ore su M3, dovrei avere pagato almeno 3 unità monetarie - per due ore di lavoro su M2 e 2 ore su M3, dovrei avere pagato almeno 5 unità monetarie

Tuttavia, non riesco a comprendere i significati delle variabili y1 e y2. Quando finalmente eseguo la minimizzazione, il risultato in z è lo stesso nel primale (anche se il primale nell'aumentare il limite inferiore del risultato mentre il doppio sta diminuendo il limite superiore), ma cosa fa la funzione obiettivo del doppio il problema consiste?

Answer 1

La funzione Obiettivo del Dual è ridurre al minimo il costo/ora delle 3 macchine (risorse).

Quindi, la funzione obiettivo del doppio (4*y1 + 12*y2+ 18*y3) può essere letto come:

Minimize 4*(cost/hour of Machine1) + 12*(cost/hour of M2) + 18*(cost/hr of M3) 

Dal momento che l'Primal affrontato massimizzare il profitto della produzione, il doppio può essere pensato come Minimizzare la produzione costi per l'azienda.

(A volte aiuta a pensare alla società "affittare" le macchine M1, M2 e M3.) Se hanno intenzione di affittarla, qual è il massimo che essi dovrebbero pagare [$/ora] per ogni macchina e produce ancora x1 e x2 con profitto?

Il significato delle vostre variabili doppie y1, y2, and y3 corrisponde al costo di possesso/affitto per ora.

Le variabili del doppio problema sono spesso denominate "prezzi ombra" delle risorse.

Dal momento che sono alla ricerca di spaccato duali comprensione:

1. Un trucco è quello di ridurre la dimensione del doppio. (Immagina che ci fosse solo una macchina M1.) Ora, formula il doppio e cerca di capire la funzione obiettivo ei vincoli.
2. È utile pensare in termini di costi di opportunità "". Se la ditta di produzione ha dovuto noleggiare macchine (risorse), quale prezzo/ora dovrebbe pagare? In alternativa, se ci fossero molti altri prodotti (redditizi), a quale costo/ora verranno assegnate le macchine a X1 e X2 invece di produrre questi altri prodotti.
3. Si noti che non tutti i duali possono essere "compresi" facilmente. Tuttavia, è possibile ottenere un senso di molti vincoli duali guardando la variabile corrispondente nel primale. Allo stesso modo, è possibile ottenere intuizioni in una doppia variabile studiando il vincolo principale corrispondente.