Programacion lineal grafica

Vista previa del material en texto

Tema 1 - PROGRAMACION LINEAL
Es un programa matemático en donde todas las restricciones 
y la función objetivo son lineales
La forma general seria: 
• Maximizar una función del tipo Max z = cj xj
• Sujeto a un conjunto de restricciones del tipo s.a  aij xj≤ bi
• Siendo las variables no negativas xj ≥ 0
Un problema de maximización puede convertirse en uno de 
minimización (y viceversa) y las restricciones pueden ser de mayor e 
igual (y viceversa)
Forma Canónica
Los cj que afectan las variables de la FO, son los coeficientes 
de costos del funcional. 
Las aij que afectan a las variables en las restricciones, se 
denominan coeficientes tecnológicos 
Los parámetros bi son los términos independientes o RHS (Right
Hand Side)
Cada inecuación de ≤ puede transformarse en una ecuación sumando 
una variable no negativa.
Max z =  cj xj
s.a  aij xj + Xk+1 = bi
 xj ≥ 0
Forma estándar 
Ejemplo de PROGRAMACION LINEAL
Ejemplo- Una empresa produce pinturas para interiores y exteriores, a partir 
de dos materias primas: A y B. La disponibilidad máxima diaria de la materia 
prima A es 6 toneladas y la de B es 8 toneladas. 
•Los requisitos diarios de materias primas por tonelada de pintura para
interiores y exteriores son los siguientes:
Tn MP A/ton.PExt Tn MPB/ton P. Int.
MP A 1 2
MP B 2 1
Ut./ton. 3000 2000
Tn. Disp.max/Día
6
8
Un estudio de mercado ha establecido que la demanda diaria de pintura
para interiores no puede ser mayor que la de pintura para exteriores en
más de una tonelada.
El estudio indica además que la demanda máxima de pintura para
interiores está limitada a dos toneladas diarias.
La utilidad por tonelada es $3.000 para la pintura de exteriores y
$2.000 para la pintura de interiores por tonelada respectivamente.
La Empresa quiere determinar la mezcla de productos óptima de pintura
para exteriores e interiores que maximice la utilidad total diaria.
Modelo de PL – Definición del problema
Elementos
1- Variables de decisión a determinar
2- Objetivo a optimizar
3- Restricciones a satisfacer
Para el problema
1- Variables de decisión a determinar
xE = toneladas diarias de pintura para exteriores/día
xI = toneladas diarias de pintura para interiores/día
2- Función objetivo
Max z = 3000 $/Tn PE * xE Tn PE/dia + 2000 $/Tn PI * xI TnPI/dia
3 - Restricciones
xE + 2 xI  6 (1) 
1Tn MP A/tn.PE* Tn PE/dia + 2 Tn MPB/ton PI*TnPI/dia  6 Tn. Disp.MPA/Día
2xE + xI  8 (2) 
xI  xE + 1 (3) (definir unidades en cada restricción) 
xI  2 (4)
xE  0 (5) , xI  0 (6) Condiciones de no negatividad
⚫ Cualquier solución que satisface todas las restricciones del modelo es 
una solución factible. 
⚫ Nos interesa la solución factible óptima que produce la máxima utilidad total.
⚫ Tanto la función objetivo como las restricciones son todas lineales 
están intrínsecas las dos propiedades siguientes:
1. Proporcionalidad: La contribución de cada variable de decisión, tanto en la 
función objetivo como en las restricciones, es directamente proporcional al valor 
de la variable. 
2. Aditividad: La contribución total de todas las variables en la función objetivo y en 
las restricciones es la suma directa de la contribución individual de cada variable.
 
| 
1 
| 
2 
| 
3 
| 
4 
| 
5 
| 
6 
 1 _ 
 2 
 3 _ 
 4 _ 
 5 _ 
 6 _ 
 7 _ 
 8 _ 
xI 
 xE 0 
A 
B 
C 
D 
E 
F 
G 
H 
1 
4 
2 
5 
3 
6 
xE + 2xI = 6 
2 xE + xI = 8
xI = 1.33
xE = 3.33
Z = 3 x 3.33 + 2x 1.33 = 12.66
Restricciones
xE + 2 xI  6 (1)
2 xE + xI  8 (2)
xI  xE + 1 (3)
xI  2 (4)
xE  0 (5) 
xI  0 (6)
Sacar pendiente de z; buscar el máximo valor del 
recinto PUNTO C
(1)
(2)
Función Objetivo: Max z = 3 xE + 2 xI
Representación Grafica
EL METODO SIMPLEX
Método algebraico, iterativo, basado en la identificación de los puntos extremos.
Convertir a la forma estándar, esto es transformar desigualdades en igualdades 
utilizando variables de holgura o superávit
Condiciones de la forma estándar
•Todas las restricciones son ecuaciones con segundo miembro no negativo.
•Todas las variables son no negativas.
•La función objetivo puede ser de maximización o de minimización. 
Max Z = 3xE + 2 xI (Función Objetivo en miles)
sujeto a: 1. xE + 2 xI  6
2. 2xE + xI  8
3. - xE+ xI  1 (Restricciones- Condiciones de vínculo )
4. xI  2
xE  0 , xI  0 (CNN) Condiciones de no negatividad
Forma estándar Max Z = 3xE + 2 xI + 0s1 + 0 s2 + 0 s3 + 0 s4 ;
Max : Z - 3xE - 2 xI - 0s1 - 0 s2 - 0 s3 - 0 s4 = 0 
sujeto a : 
xE + 2 xI + s1 = 6
2xE + xI + s2 = 8
- xE + xI + s3 = 1
xI + s4 = 2
xE , xI , s1 , s2 , s3 , s4  0
Agregamos variables de holgura
Para restricciones de 
Espacio de soluciones en la forma estándar:
⚫ n : incógnitas En nuestro ejemplo son 6
⚫ m : ecuaciones En nuestro ejemplo son 4
n > m  n-m variables iguales a 0,  hay resolución de las restantes . 
Soluciones no básicas: Son variables iguales a 0 (n-m)
Si cumplen las restricciones serán básicas factibles. 
Comienza en un punto extremo, factible y se desplaza de un punto a 
otro hasta llegar al óptimo.
Reglas:
1- El siguiente extremo debe ser adyacente al actual.
2- La solución no debe regresar a un punto ya considerado.
Reglas de selección de la variables de entrada y salida
• Condición de optimalidad : en problemas de max (min) la variable de entrada es 
la variable no básica que tiene el coeficiente más negativo (positivo) en el 
renglón z.
• Condición de factibilidad: la variable que sale de la base es la variable básica 
asociada con la razón no negativa más pequeña.
Detalle de cálculo
• Paso 0 :determinar solución básica factible inicial 
(determinar n - m variables no básicas) 
• Paso 1 : determinar variable entrante, de manera que mejore la función 
objetivo. Si no existe detenerse; si no:
• Paso 2 : Seleccionar variable que sale
• Paso 3 : determinar nueva solución básica factible empleando el método de 
Gauss-Jordan
• Paso 4: volver al paso 1. 
Cada solución básica está asociada con una iteración
Punto extremo Variables no básicas /Variables básicas
A (0,0) S1; S2; S3; S4 distintas de 0 /XI; XE = 0
B …
Básica z xE xI s1 s2 s3 s4 Solución
z 1 -3 -2 0 0 0 0 0 Razón
s1 0 1 2 1 0 0 0 6 6
s2 0 (2) 1 0 1 0 0 8 4
s3 0 -1 1 0 0 1 0 1
s4 0 0 1 0 0 0 1 2
Básica z xE xI s1 s2 s3 s4 Solución 
z 1 0 -1/2 0 3/2 0 0 12 Razón 
s1 0 0 (3/2) 1 -1/2 0 0 2 4 / 3 
xE 0 1 1/2 0 1/2 0 0 4 8 
s3 0 0 3/2 0 1/2 1 0 5 10 / 3 
s4 0 0 1 0 0 0 1 2 2 
 
Básica z xE xI s1 s2 s3 s4 Solución
z 1 0 0 1/3 4/3 0 0 12,66
xI 0 0 1 2/3 -1/3 0 0 4 / 3
xE 0 1 0 -1/3 2/3 0 0 10 /3
s3 0 0 0 -1 1 1 0 3
s4 0 0 0 -2/3 1/3 0 1 2 / 3
Solución optima
Se expresa en forma completa
xE = producir 10/3 = 3,33 Tn de pintura para exteriores por día
xI = producir 4/3 = 1,33 Tn de pintura para interiores por día
s1 = 0 sobrante de materia prima A
s2 = 0 sobrante de materia prima B
S3= 3 Tn para la holgura de la restricción de la relación entre las pinturas
s4 = 2/3 Tn de pintura de interiores para que se cumpla la demanda máxima de 2
Utilidad máxima : Z = 12.666 $ /día