1-dual

Formulación del dual, Algoritmo

primal dual.

MODELO PRIMAL Y DUAL EN PL.

Como construir un Modelo Dual a partir del Modelo Primal, lo que

implica una ventaja de obtener modelo simplificado cuando se parte

por ejemplo; Primal 3 Variables de Decisión a 2 Variables de Decisión,

se podrá resolver por método gráfico.

Se pretende construir un modelo que de el mismo resultado y pueda

simplificarse.

El Modelo Dual es el reflejo opuesto del Modelo Primal.


• La teoría de dualidad parte de que asociado a todo problema de PL,

existe otro problema lineal llamado dual.

• Las relaciones entre el problema dual y el problema original o

(primal) son en extremos útiles en una gran variedad de situaciones.

• Uno de los aspectos más importantes de la teoría de dualidad es la

interpretación y realización del análisis de sensibilidad.

Teoría de dualidad:


Dada la forma estándar para el problema primal (izquierda), su problema

dual tiene la forma que se muestra a la derecha.

Esencia de la teoría de dualidad:

Max Z = Σ cj xj

s.a:

Σaijxj ≤ bi

xj ≥ 0

J=1

n

J=1

n

W = Σ bi yi

s.a:

Σaijyi ≥ cj

yi ≥ 0

i=1

n

J=1

n

Min

El problema dual usa exactamente los mismos parámetros que el

problema primal, pero en diferentes lugares.


Esencia de la teoría de dualidad:

El problema dual usa exactamente los mismos parámetros que el

problema primal, pero en diferentes lugares.

Dada la forma matricial del problema primal (izquierda), y del

problema dual.

Max Z = cX

s.a:

Ax ≤ b

x ≥ 0

W = yb

s.a:

yA ≥ b

x ≥ 0

Donde C y Y son vectores fila y b y x son vectores columna.

Min


Modelo Primal

Z =

Max.

- 5X1 -35X2 -20X3

X1 -X2 -X3 ≤ -2

-X1 -3X2 ≤ -3

X1, X2, X3 ≥ 0

Modelo Dual

W =

Min.

Y1 Y2-2 -3

Constantes de

las

restricciones

Y1 -Y2

-Y1 -3Y2

-Y1

≥

≥

≥

-5

-35

-20

Coeficientes de la

FO del Primal


Modelo Primal

Z =

Max.

- 5X1 -35X2 -20X3

X1 -X2 -X3 ≤ -2

-X1 -3X2 ≤ -3

X1, X2, X3 ≥ 0

Modelo Dual

W =

Min.

Y1 Y2-2 -3

Y1 -Y2

-Y1 -3Y2

-Y1

≥

≥

≥

-5

-35

-20


Modelo Primal

Modelo Dual Columnas del

Primal pasan a

filas del Dual


MAX Z = 3X1 + 4X2 – 2X3

S. a:

4X1 – 12X2 + 3X3 ≤ 12 Y1

–2X1 + 3X2 + X3 ≤ 6 Y2

–5X1 + X2 – 6X3 ≤ -40 Y3

3X1 – 4X2 – 2X3 ≤ 10 Y4

Variables duales

X1≥ 0, X2≤ 0, X3 no restringida en signo

Min W = 12Y1 + 6Y2 – 40Y3 + 10Y4 4Y1 – 2Y2 – 5Y3 + 3Y4 ≥ 3

–12Y1 + 3Y2 + Y3 - 4Y4 ≥ 4

3Y1 + Y2 – 6Y3 – 2Y4 ≥ -2

S. a:

Y1≥ 0, Y2≤ 0, Y3≥ 0, Y4 no restringida en signo

Ejercicio:


La empresa KZ se dedica a la fabricación de tres producto; A, B y C. El

procedimiento de producción involucra tres operaciones: formación,

acabado e inspección.

El departamento de ingeniería industrial, ha establecido los siguientes

estándares de producción en cada operación. Datos de producción para

la compañía (minutos por producto). El departamento de contabilidad por

su parte, pronostica los siguientes costos e ingresos para la compañía.

Datos de costo e ingreso para la compañía

Se desea saber el número de cada tipo de producto que deberán

producirse de tal manera que se optimice el beneficio por las 8 horas de

trabajo del día.

Ejemplo:


PRODUCTO FORMACIÓN INSPECCIÓN ACABADO

A 2 3 2

B 6 2 2

C 2 2 4

PRODUCTO COSTO DE

PRODUCCIÓN

COSTO DE

MATERIALES

COSTO

TOTAL

PRECIO DE

VENTA

A 18 12 30 50

B 50 15 65 100

C 25 20 45 50

Datos de Producción para la Compañía (Minutos x Producto)

Datos de Costos e Ingresos para la Compañía

Datos:


Considerando la información, se planteó el modelo de programación lineal:

Z = 20X1 + 35X2 + 45X3

Sujeto a:

2X1 + 6X2 + 2X3 ≥ 480 (Formación)

3X1 + 2X2 + 2X3 ≥ 480 (Inspección)

2X1 + 2X2 + 4X3 ≥ 480 (Acabado)

X1; X2; X3 No negatividad


Modelo Dual del problema

Min W = 480Y1 + 480Y2 + 480Y3

S. a: 2Y1 + 3Y2 + 2Y3 ≤ 20

6Y1 + 2Y2 + 2Y3 ≤ 35

2Y1 + 2Y2 + 4Y3 ≤ 45

Y1 ≥ 0, Y2 ≥ 0, Y3 ≥0

Z = 20X1 + 35X2 + 45X3

Sujeto a:

2X1 + 6X2 + 2X3 ≥ 480 (Formación)

3X1 + 2X2 + 2X3 ≥ 480 (Inspección)

2X1 + 2X2 + 4X3 ≥ 480 (Acabado)

1-dual

Documents