Problema Dual

  • Published on
    08-Nov-2015

  • View
    6

  • Download
    1

Embed Size (px)

DESCRIPTION

PPT

Transcript

<p>Problema Dual DEFINICIN DEL PROBLEMA DUALEl problema dual es una programacin lineal definida en forma directa y sistemtica a partir del modelo original (o primal) de programacin lineal. Los dos problemas estn relacionados en forma tan estrecha que la resolucin ptima de un problema produce en forma automtica la resolucin ptima del otro.Pasos a Seguir1. Se define una variable dual por cada ecuacin primal (restriccin).2. Se define una restriccin dual por cada variable primal.3. Los coeficientes de restriccin (columna) de una variable primal definen los coeficientes en el lado izquierdo de la restriccin dual, y su coeficiente objetivo define el lado derecho.4. Los coeficientes objetivo del dual son iguales al lado derecho de las ecuaciones de restriccin primal.Construccin del Dual a Partir del Primal</p> <p>Ejemplo 1Forma Estndar y Variables Duales</p> <p>Problema DualEjemplo 2</p> <p>Problema Dual</p> <p>Ejercicio: Escriba el Dual de los siguientes problemas primales.</p> <p>Solucin Dual ptimaLas soluciones primal y dual se relacionan en forma tan estrecha que la solucin ptima del problema primal produce en forma directa (con unos pocos de clculos adicionales) la solucin ptima del dual. </p> <p>Mtodo 1:</p> <p>Solucin Dual ptimaMtodo 2:</p> <p>Ejemplo</p> <p>Para preparar el problema para su solucin con mtodo smplex se agrega una holgura en la primera restriccin, y una R artificial en la segunda. Los problemas primal y dual asociado resultantes se definen as:</p> <p>Tableau ptimo del Primal</p> <p>Solucin a las Variables del DualMtodo 1. Primero se observa que las variables primales ptimas aparecen en la tabla en orden del rengln, primero y despus . Eso quiere decir que los elementos de los coeficientes originales del objetivo para las dos variables deben aparecer en el mismo orden, que es:</p> <p>Solucin a las Variables del DualAs, los valores duales ptimos se calculan como sigue:</p> <p>Solucin a las Variables del DualMtodo 2. Como el problema dual tiene dos variables se necesitan dos ecuaciones para llegar a la solucin. Tomaremos las restricciones duales asociadas con las variables primales de inicio, x4 y R. Como se ve en la definicin de dual, las restricciones duales asociadas con las variables primales de inicio son:</p> <p>Solucin a las Variables del DualTambin, de acuerdo con el tableau ptimo:</p> <p>Entonces, de acuerdo con el mtodo 2,</p> <p>Ejercicio en ClaseUn carpintero modesto fabrica dos tipos de mesas de madera. Cada mesa del tipo 1 necesita 4 horas de mecanizado primario (preparacin de piezas) y 4 horas de mecanizado secundario (ensamblado y barnizado). Anlogamente, cada mesa del tipo 2 necesita 3 horas de mecanizado primario y 7 horas de mecanizado secundario.Las disponibilidades diarias de mecanizados primario y secundario son respectivamente de 40 y 56 horas-mquina. La venta de una mesa del tipo 1 reporta un beneficio de 70 dlares, mientras que la venta de una mesa del tipo 2 de 90 dlares. El objeto de este problema es determinar el nmero de mesas de cada tipo que han de producirse diariamente para maximizar el beneficio obtenido.SolucinPrimero ordenamos los datos en una tabla:</p> <p>FO</p> <p>Formulacin Estndar</p> <p>Tableau Inicial</p> <p>Tableau Iteraciones Siguientes</p> <p>Por lo tanto el carpintero de fabricar 7 mesas del tipo 1, 4 del tipo 2 y suganancia sera de $850.Problema DualPara escribir el dual, reescribamos el primal como:</p> <p>Problema DualSegn las reglas que ya se enunciaron resulta:</p> <p>Problema DualReordenando resulta</p> <p>Cmo obtenemos los valores del problema dual a partir del primal?Mtodo 1</p> <p>Soluciones Dual</p> <p>GRACIAS!</p>