Programacion lineall

Prévia do material em texto

Modelo Programación Lineal
Tipos. Forma Canónica y Estándar.
INVESTIGACIÓN OPERATIVA I
Objetivos
Definición de un Problema de PL.
Propiedades.
¿Cuánto
Producir para
Obtener mayores utilidades?
Mayores Beneficios
I. Problema de Programación Lineal
La forma más general de un problema de programación lineal (PPL) consiste en minimizar o maximizar
	Max z=C1X1+C2X2+…+CnXn 
	s.a.
		a11X1+a12X2+…+a1nXnb1
		a21X1+a22X2+…+a2nXnb2
				…
		am1X1+am2X2+…+amnXnbm
	end
		X1,X2,…,Xn≥0
… (1) 
… (2) 
… (3) 
MPL con n variables
Lo que distingue un problema de programación lineal de cualquier otro problema de optimización es que todas las funciones que en él intervienen son lineales.
Una única función no lineal hace que el problema no pueda clasificarse como problema de programación lineal.
Definición 1. (solución factible). 
Un punto x = (x1, x2, . . . , xn) que satisface todas las restricciones (2) se denomina solución factible. 
El conjunto de todas esas soluciones es la región de factibilidad.
Definición 2. (Solución óptima). Un punto factible , que mejora (1), tal que 
f()≤ f(x)
para cualquier otro punto factible x se denomina una solución óptima del problema.
II. Objetivo
El objetivo de los problemas de optimización es encontrar un óptimo global. Sin embargo, las condiciones de optimalidad sólo garantizan, en general, óptimos locales, si éstos existen. Sin embargo, los problemas lineales presentan propiedades que hacen posible garantizar el óptimo global:
III. Propiedades
Si la región factible está acotada, el problema siempre tiene una solución (ésta es una condición suficiente pero no necesaria para que exista una solución).
El óptimo de un problema de programación lineal es siempre un óptimo global.
Si x y y son soluciones óptimas de un problema de programación lineal, entonces cualquier combinación (lineal) convexa de lo mismos también es una solución óptima. Obsérvese que las combinaciones convexas de puntos con el mismo valor de la función de coste presentan el mismo valor de la función de coste.
Modelo PL con n variables
Un MPL de n variables presenta la siguiente forma general:
	Max z=C1X1+C2X2+…+CnXn 
	st
		a11X1+a12X2+…+a1nXnb1
		a21X1+a22X2+…+a2nXnb2
				…
		am1X1+am2X2+…+amnXnbm
	end
		X1,X2,…,Xn≥0
C1,C2,..,Cn son las Utilidades unitarias
X1,X2,..,Xm son las variables de decisión
Los a1, a2,…,am son los coeficientes tecnológicos
Representan las restricciones
FORMA CANONICA
FORMA CANONICA
Un MPL de n variables presenta la siguiente forma general:
	Min z=C1X1+C2X2+…+CnXn 
	st
		a11X1+a12X2+…+a1nXn≥b1
		a21X1+a22X2+…+a2nXn≥b2
				…
		am1X1+am2X2+…+amnXn≥bm
	end
		X1,X2,…,Xn≥0
Los a1, a2,…,am son los coeficientes tecnológicos
Representan las restricciones
C1,C2,..,Cn son las Costos unitarios
X1,X2,..,Xm son las variables de decisión
La solución óptima se alcanza siempre, al menos, en un punto extremo de la región factible. 
Estos problemas tienen:
Solución única
Soluciones múltiples
Solución no acotada
Solución infactible
Tipos MPL considerando su Región Factible o Conjunto Solución.
Región Factible No Acotada
Si es un prob. de Max NO tendría solución.
X1
X2
Ejemplo 1
		Max Z=3X+4Y
		 s.a.
			 x + y ≥ 14
2x +3y ≥ 36
4x + y ≥ 16
x − 3y ≥ 0
 end
¿Qué tipo de solución tiene el MPL?
b)	Región Factible Con Infinitas Soluciones
Se caracteriza porque al menos una de las restricciones es paralela a la F.O. por lo tanto tiene INFINITAS soluciones
FO
Ejemplo 2
		Min Z=3x + 3y
		 s.a.
			 x + y ≥ 5
y ≤ x +3
3y − x≥ −1
y +2x ≤ 16
4y − x ≤ 22 
			end
¿Que tipo de solución tiene el MPL?
c)	Región Factible Con Solución Única
A
B
C
Tiene solución única.
Ejemplo 3
		 Max Z= 2000x + 5000y
		 s.a.
			 2x +3y ≥ −3
2x − y − 9 ≤ 0
2x − 5y − 5 ≥ 0 
			end
¿Cuál es la solución?. Que tipo de solución tiene el MPL.
d)	Región Infactible. Se caracteriza porque no existe intersección entre todas las restricciones.
R1
R2
X1
X2
Tiene solución única.
No existe intersección entre todas las restricciones
Ejemplo 4: Min Z=3x + 3y
		 s.a.
			 x + y ≥ 5
y ≤ x +3
3y − x≥ −1
y +2x ≤ 16
4y − x ≤ 22
x + y ≤ 2
			end
¿Tiene solución?
Algebra del Método Simplex
INVESTIGACIÓN OPERATIVA I
Universidad Peruana 
de las Americas
Objetivos
Reconocer en forma teórica y practica un conjunto convexo
I. Combinación Lineal Convexa
Un punto se dice que es combinación lineal de n puntos , si dicho punto se puede expresar como:
Siendo 	 
		+…+ 
1.1. Conjuntos Convexos
Un conjunto es convexo si cumple que:
es decir, que dados dos puntos cualesquiera del conjunto, el segmento lineal cerrado que une los dos puntos está totalmente contenido en el conjunto.
1.2. Conjuntos Convexos. Propiedades
Un Conjuntos convexo tiene las siguientes propiedades:
La intersección de conjuntos convexos es un conjunto convexo
Si su suma se define 
	Así si y son convexos su suma también lo es.
Si es una aplicación lineal y es un conjunto convexo, el conjunto es convexo.
El conjunto S de las soluciones no negativas de un sistema lineal de ecuaciones (soluciones con todos los componentes no negativos), es convexo.
Figura. Representación de 5 los elementos en los cuerpos cósmicos, según Platón
¿Graficas de Conjuntos Convexos?
Intersección de Conjuntos Convexos?
A
B
 AB
Cuidemos la vida…