programacion lineal

Programación Lineal
Ing. León Colina

Programación lineal

Objetivos
• Aplicar las técnicas de resolución de
sistemas de ecuaciones e inecuaciones
lineales.
• Saber representar regiones factibles y
determinar gráficamente los puntos donde
puede darse la solución óptima.

Objetivos
• Saber
plantear
un
problema
de
programación lineal partiendo de su
enunciado en términos generales.
• Aplicar lastécnicas de resolución de
sistemas de ecuaciones e inecuaciones
lineales..
• Saber representar regiones factibles y
determinar gráficamente los puntos donde
puede darse la solución óptima.
• Saber encontrar esa solución óptima.

Qué es la programación lineal
Se
refiere
a
varias
técnicas
matemáticas relacionadas que se
utilizan para asignar recursos limitados
entre demandas en competencias de
unamanera óptima.

Qué es la programación lineal
• Se llama programación lineal al conjunto
de técnicas matemáticas que pretenden
resolver la situación siguiente:
Optimizar (maximizar o minimizar) una
función objetivo, función lineal de varias
variables, sujeta a:
una serie de restricciones, expresadas por
inecuaciones lineales.

Dónde se aplica
En infinidad de aplicaciones de la industria,
laeconomía, la estrategia militar, etc.. se
presentan situaciones en las que se exige
maximizar o minimizar algunas funciones
que se encuentran sujetas a determinadas
limitaciones, que llamaremos restricciones.

Formulación de la PL

Función objetivo
 La función f(x,y) = ax + by + c es la
llamada función objetivo a optimizar.
 En la expresión x e y son las variables de
decisión, mientras que a, b yc son
constantes.
Máximo (o Mínimo) Z = C1X1 + C2X2 + ... + CnXn

Las restricciones
• Las restricciones son inecuaciones lineales.
• Su número depende del problema en cuestión.
• La desigualdad viene impuesto por las
limitaciones, disponibilidades o necesidades,
que son:
- inferiores a (menores: < o );
- como mínimo de (mayores: > o ) .

Conjunto (o región) factible
• Es el conjunto de valoresde x e y que verifican
todas y cada una de las restricciones.

Solución óptima
• Es un par de valores (x0, y0) del conjunto
factible que haga que f(x,y) tome el valor
máximo o mínimo.
• Al conjunto de valores de x e y que
verifican todas y cada una de las
restricciones se lo denomina conjunto (o
región) factible

Conjunto convexo
Un conjunto de puntos S es un conjunto
convexo si el segmentorectilíneo que une
cualquier par de puntos de f(x,y) se
encuentra completamente en S.
y

y
x1

S

x1
x2

Conjunto convexo x

S

x2

Conjunto no convexo x

Punto extremo
Es aquel punto en el conjunto convexo, que
no puede ser expresado como un
combinación convexa de otros dos puntos, o
que no está en ninguna recta que una a dos
puntos del conjunto.
y

A

B

Z1
Z2

C

x

Determinación de la regiónfactible
• La solución de un problema de
programación lineal, en el supuesto de que
exista, debe estar en la región determinada
por las distintas desigualdades.
• Puede se acotada y no acotada

Determinación de la región
factible

Región factible acotada

Región factible no acotada

Casos especiales de regiones
Z(max)=3X1+9X2
S.A.

x2

X1+4X2≤8 (1)
X1+2X2 ≤4(2)
X1,X2≥0

Solución degenerada
2

x1
1Casos especiales de regiones
Z(max)=4X1+14X2
S.A.
2X1+7X2≤21(1)
X1+2X2 ≤21(2)
X1,X2≥0
Solución múltiple
La función objetivo tiene
el mismo valor óptimo en
mas de una solución

1

2

Casos especiales de regiones
Z(max)= 4X1+X2
S.A.
X1+7X2≥10(1)
2X1+X2 ≥ 40(2)
X1,X2≥0
Solución múltiple
El espacio de soluciones
no está limitado. El valor
de la función objetivo es
indefinido

x2

x1
1

2

Casosespeciales de regiones
Z(max)=3X1+2X2

x2

S.A. 2X1+ X2≤2 (1)
3X1+4X2 ≤12(2)
X1,X2≥0
Solución no factible
Ningún punto satisface
todas las restricciones

x1
1

2

Ejemplo de región
x+y≥4
y≤4
y≥x

Método gráfico
1. Formular el problema en términos matemáticos.
2. Definir las ecuaciones de restricciones.
3. Determinar el área de factibilidad.
4. Definir la función objetivo.
5. Encontrar el punto...