¿De dónde surge el modelo Dual?

...

Ejemplo:

x1+2x2≤4

Equivale a:

x1 + 2x2 + x3 = 4

Donde la variable x3≥0

Variable de exceso

La variable de exceso aparece en las restricciones ≥, aparece restando en la restricción para convertir la desigualdad en ecuación.

Ejemplo:

x1+2x2≥4

Equivale a:

x1 + 2x2 - x3 = 4

Donde la variable x3≥0

El lado derecho de una ecuación siempre se puede hacer no negativo, multiplicando la ecuación por -1, de ser necesario.

Variables básicas y no básicas.

Cuando el modelo de programación lineal esta expresado en su forma estándar hay m ecuaciones lineales por n incógnitas con (m

1. La n-m variable a las cuales se les asigna un valor de cero.

2. Las restantes m variables se determina su valor resolviendo las m ecuaciones resultantes.

Variables básicas.

Si las m ecuaciones producen una solución única, entonces las m variables asociadas se llaman variables básicas.

Ejemplo:

5

x1 + 4x2 = 8

4x1 + 2x2 = 4

Tiene solución única x1=0, x2=2. Tanto x1 como x2 son variables básicas.

Variables no básicas.

Las n-m restantes variables se conocen como variables no básicas.

Ejemplo:

x1+2x2≥4

Equivale a:

x1 + 2x2 - x3 = 4

Las n-m variables son x1,x2 por lo tanto se vuelven variables no básicas..

Variable de entrada

Una variable de entrada es una variable no básica en un punto extremo que en el siguiente punto extremo adyacente es variable básica

Variable de salida

Una variable de salida es una variable básica en un punto extremo que en el siguiente punto extremo adyacente es variable no básica.

Condición de optimalidad.

La variable de entrada en un problema de maximización es la variable que tiene el coeficiente más negativo en el renglón Zj-Cj y para el caso de minimización la variable de entrada corresponde al coeficiente más positivo del renglón Zj - Cj. La optimalidad se logra cuando en el renglón Zj-Cj ya no hay valores positivos (minimización) o negativos (maximización) según sea el caso.

6

OBJETIVO

El objetivo principal es el de resolver un problema de Programación Lineal llegando a una solución óptima.

EJERCICIO:

Una compañía produce y vende 2 tipos de máquinas de escribir: manual y eléctrica. Cada máquina de escribir manual es vendida por un ingreso de 40 dls. y cada máquina de escribir eléctrica produce un ingreso de 60 dls. Ambas máquinas tienen que ser procesadas (ensambladas y empacadas) a través de 2 operaciones diferentes (O1 y O2).

La compañía tiene una capacidad de 2000 hrs. Mensuales para la operación O1 y 1000 hrs. Mensuales de la operación O2.

El número de horas requeridas de O1 y O2 para producir un modelo terminado se da en la siguiente tabla.

HORAS

REQUERIDAS

CAPACIDAD

OPERACIÓN

MANUAL

ELECTRICA

(HRS MENSUALES)

O1

3

2

2000

O2

1

2

1000

Encuentre el número óptimo de unidades de cada tipo de máquina de escribir que se debe producir mensualmente para maximizar el ingreso.

7

OBJETIVO: Maximizar el ingreso total

RESTRICCIONES: horas mensuales de las operaciones

VARIABLE DE DECISION: número de máquinas de escribir a producir

X1 = número de máquinas de escribir manuales

X2 = número de máquinas de escribir eléctricas

Maximizar Z= 40 X1 + 60X2

Sujeto a:

[pic 1]

Minimizar Z=2000 W1 + 1000 W2

Sujeto a:

[pic 2]

V. Básica

Z

W1

W2

S1

S2

Solución

Z

1

0

0

5

25

35000