Programación lineal

Gustavo Alvarado Kinnell

Función objetivo

 Φ= Φ(x1,x2,x3,…, xn)
 Donde:
 Φ => funcion objetivo
 x1,x2,x3,…, xn => variables independientes
 Tiene un valor para un conjunto dado de variables independientes
 Puede ser maximizar ganancias, reducir los ciclos de efectivo, reducir el
costo de embarque, etc.
Restricciones

 Restricción de igualdad
 F1=f1((x1,x2,x3,…, xn)=0

 Restricción de desigualdad
 F2=f2((x1,x2,x3,…, xn)≤0
 Hay que pensar en las restricciones como las reglas del juego. (El numero
de empleados de una fabrica, el tiempo de limpieza y recarga de
combustible de un avión, etc)
Variables (x1,x2,x3,…, xn)

No deben ser necesariamente continuas

Pueden tener valores enteros
Es todo aquello en lo que tenemos control para
tomar una decisión
En una refinería:
El precio del petróleo ¿lo puedo fijar?
La cantidad de un petróleo a usar ¿la puedo
determinar?
El problema (modelo de optimización)

 Encontrar el conjunto de variables independientes, sujetas a las

condiciones aplicables (restricciones), que permiten tener el valor optimo
de la función objetivo.
 En muchos casos hay varias soluciones para un problema de optimización.
Solución

 Programar el modelo de optimización en una computadora e integrar el

uso de un programa solucionador y una interface de usuario para tener un
sistema de optimización.
 Si a este sistema le alimentamos buena información, se obtiene “ la mejor
Solución Posible”
Programación Lineal

 Planteamiento
 ¿Cómo reconocer las situaciones de toma de decisiones que pueden analizarse
con programación lineal?
 ¿Como formular los problemas en términos de programación lineal?
 Método grafico y otros métodos
 Solución
 ¿Cuál es el problemas?
 ¿Cuales son las alternativas?
 ¿Qué alternativa es la mejor?
Formulación de restricciones
(programación lineal)
 Para formular un problema en forma matemática, deben expresarse
afirmaciones lógicas en términos matemáticos
 A usa 3 horas por unidad y B usa 2 horas por unidad. Si deben usarse todas
las 100 horas disponibles, la restricción será:

 3A + 2B = 100 ó 3A + 2B ≤ 100

 Para que sea aceptable para PL, cada restricción debe ser una suma de
variables con exponente 1
Formulación de restricciones
(programación lineal)
 Si, por ejemplo, la restricción es que A debe ser por lo
menos el doble de B, esto puede escribirse como:
 A≥2B o A-2B ≥ 0
 si se quiere que A sea por lo menos tan grande como B
2, entonces:
 A≥B+2 o A-B≥ 2 por último B - A ≤ 2
 es sencillo convertir una desigualdad en una ecuación.
Todo lo que se tiene que hacer es agregar (o restar)
una variable extra
 B -A ≤ 2 es lo mismo que B- A + S = 2
Restricciones de no negatividad
(programación lineal)

 La metodología de PL requiere que todas las variables

sean positivas o cero, es decir, no negativas
LA FUNCIÓN OBJETIVO
(programación lineal)
 La metodología de PL requiere que todas las variables
sean positivas o cero, es decir, no negativas
 Mientras que no existe un límite en el número de
restricciones que puede tener un problema de PL, sólo
puede haber una función objetivo.
 Debe llevar consigo el maximizar o minimizar alguna
medida numérica
 Maximizar Z = 4A + 6B
 Ejemplo Programación Lineal
 Para simplificar este problema, se supone que existen sólo tres restricciones:
la cantidad diaria de tres vitaminas. También se supone que sólo
se están considerando dos tipos de alimento. Así, el problema consiste en
decidir cuánto comprar de cada alimento para satisfacer las tres restricciones
y minimizar el costo.
Supóngase que el alimento A y el alimento B son los dos tipos bajo
consideración. El alimento A cuesta 12 pesos/gramo y el alimento B 8
pesos/gramo. Se quiere minimizar el costo total de los alimentos al mismo
tiempo que satisfacer las tres restricciones vitamínicas. Se desean, por lo
menos, 30 unidades de la vitamina W, 50 unidades de la vitamina X y 60
unidades de la vitamina Y. Cada gramo del alimento A proporciona 2
unidades de la vitamina W, 4 unidades de la vitamina X y 7 unidades de
vitamina Y. El alimento B proporciona 3,3 y 6 unidades de W, X y Y, por gramo,
respectivamente. ¿Cuántas gramos de cada alimento deben comprarse?
Solución ejemplo 1

 Función objetivo

min z  12 A  8 B
 Restricciones

2 A  3B  30 Vitamina W

4 A  3B  50 Vitamina X

7 A  6 B  60 Vitamina Y
A0
B0
 Solución grafica

 Solución como igualdad

2 A  3 B  30 2 A  3B  30
A0 B0
B  10 A  15
4 A  3B  50 4 A  3B  50
A0 B0
B  50 / 3 A  50 / 4
7 A  6 B  60 7 A  6 B  60
A0 B0
B  10 A  60 / 7
 Programación Lineal
 Supóngase que una compañía que da servicio de limpieza
prepara sus propias soluciones mezclando dos ingredientes.
Hace esto para obtener una solución que tiene lo que considera
una combinación apropiada de fosfatos y cloruro. Un
ingrediente tiene 5% de fosfatos y 2% de cloruro y cuesta 25
centavos/onza. El otro ingrediente tiene 7% de fosfato y 1 % de
cloruro y cuesta 20 centavos/onza. La firma necesita que la
mezcla final tenga no más del 6% de fosfatos y 11.2% de cloruro.
 El objetivo es minimizar el costo total.
 Pero ¿cuáles son las variables de decisión? ¿El número de onzas
en cada ingrediente? Nótese que el problema no dice nada
sobre la cantidad total de solución que debe prepararse. No
obstante, puede encontrarse una fórmula para la mezcla
definiendo las variables como la proporción de cada
ingrediente en una onza de solución.
Planteamiento ejemplo 2
 Definir variables
 A onzas de ingrediente 1
 B onzas de ingrediente 2
 Función objetivo

 Restricciones
min z  25 A  20 B

5 A  7B  6 Fosfatos

2 A  1B  11.2 Cloruros
Solución gráfica

 Solucionar como igualdad

5 A  7B  6
5 A  7B  6
A0 A6/5
B0
B 6/7
2 A  1B  11.2 2 A  1B  11.2
A  5.6
A0
B  11.2 B0

min z  25 A  20 B 100  25 A  20 B
A0 A4
B5 B0
 Programación Lineal
 Ésta es otra forma del problema de mezclas. Supóngase que se
acaba de recibir una herencia de $10 000 de un tío lejano y que
se quiere invertir este dinero para maximizar el rendimiento sobre
la inversión. Se decide invertir tanto en acciones como en
bonos. Para estar seguros, se piensa que las acciones deben ser
no más del 25% del total y debe ser, por lo menos, el 10 %. Existe
un bono que resulta en particular interesante y se quiere invertir
en él por lo menos $4 000. Se estima que la tasa anual de
rendimiento en bonos es el 8 % y en acciones el 10 %. ¿Cuánto
debe invertirse en acciones y cuánto en bonos?
Solución

 A $ acciones
 B $ bonos
 Función objetivo

max 0.10 A  0.08 B

 Restricciones:

A  B  10000
A  2500
A  1000
B  4000
Método Simplex
Método Simplex

 Metodología que permite realizar toma de decisiones optimas en situaciones

complejas
 Tiene una metodología estándar de solución:
 Función Objetivo
 Minimizar

 Sujeto a:
En su forma matricial

 Minimizar Donde:

 X1   b1   c1 
X  b  c 
     
 Sujeto a: X   2 b   2 c   2
    
 X n  bn  cn 

 a11 a12  a1n 

a a22  a2 n 
a   21
    
 
 am1 am 2  amn 
LAs características de un problema de
programación lineal en su forma standard

La función objetivo es de tipo

minimización
Todas las restricciones son de tipo
igualdad
Todas las variables de decisión son no
negativas
Para pasar cualquier problema de LP
a su forma estándar
 Las funciones de maximización se representan como de minimización con
signo negativo

max f  c1 x1  c2 x2    cn xn
 Se sustituya por

min f '  c1 x1  c2 x2    cn xn

Para pasar cualquier problema de LP
a su forma estándar
 Las variables físicas de muchos problemas de ingeniería representan
dimensiones físicas, por lo que estas de manera natural, serán no negativas
(positivas)
 En algunos casos hay variables que deberán de ser sin restricción de signos
(negativas), en tales casos la variable original se deberá de sustituir por

x j  x j '  x j"

x j"  0 x j'  0
Para pasar cualquier problema de LP
a su forma estándar
 Si la función de restricción tiene la forma de menor igual que, se deberá
incluir una variable de holgura

ak1 x1  ak 2 x2    akn xn  bk

 Cambiar por

ak1 x1  ak 2 x2    akn xn  xn1  bk

Para pasar cualquier problema de LP
a su forma estándar
 Si la función de restricción tiene la forma de mayor igual que, se deberá
incluir una variable de holgura

ak1 x1  ak 2 x2    akn xn  bk

 Cambiar por

ak1 x1  ak 2 x2    akn xn  xn 1  bk
Para pasar cualquier problema de LP
a su forma estándar
 Se puede observar que se tienen m ecuaciones y n variables de decisión
en un problema de programación lineal.
 Podemos asumir que m<n
 En el caso de que m>n se van a tener m-n ecuaciones redundantes que
deberán de ser eliminadas.
 Cuando m=n solo se tiene una posible solución y no representa interés
como problema de optimización
Solución bajo método Simplex

 Una solución al problema de un sistema estándar es el método Simplex

que usa el método pivotal de solución
 Una manera de encontrar esta solución es encontrar todas las soluciones y
seleccionar una que sea viable, y corresponda al valor optimo de la
función objetivo.
 Si tenemos m ecuaciones de restricción con n variables y n>=m debemos
de inspeccionar las diversas soluciones haciendo las combinaciones
posibles

n n!
  
 m  (n  m)!m !
 Solución bajo método Simplex

 La primera parte del método simplex es construir un problema auxiliar introduciendo ciertas
variables conocidas como artificiales en la forma estándar del problema.
 Al resolver este sub-problema se calcula el valor de la función objetivo y si es sub-problema
es viable.
 El problema planteado es encontrar un vector X>0 que minimice f(x) y satisfaga las
ecuaciones:
Solución bajo método Simplex

 La solución se puede escribir de la siguiente forma:

 Para en forma posterior buscar una solución alternativa

Ejemplo

max f  x1  2 x2  x3

2 x1  x2  x3  2
2 x1  x2  5 x3  6
4 x1  x2  x3  6
xi  0 i  1, 2,3
Pasar a forma canónica

min f   x1  2 x2  x3

2 x1  x2  x3  2
2 x1  x2  5 x3  6
4 x1  x2  x3  6
xi  0 i  1, 2,3
 Introducir variables de holgura

min f   x1  2 x2  x3
2 x1  x2  x3  x4  2
2 x1  x2  5 x3  x5  6
4 x1  x2  x3  x6  6
 x1  2 x2  x3  f  0
xi  0 i  1, 2,3

 Las variables x4, x5 y x6 así como –f se pueden tratar como variables básicas y nos da el
resultados inicial de:
 X4=2 x5=6 x6=6 variables básicas
 X1=x2=x3=0  variables no básicas
 F=0
Verificar función de costos

 Debido a que los valores de C son negativos de debe buscar una solución
alternativa dentro de las combinaciones posibles.


c1'  1, c2'  2, c3'  1

 Definir elemento pivote como a’rs

 Aplicando elemento pivote

 La solución es:
 X2=2, x5=8, x6=4  variables básicas
 X1=x3=x4=0  variables no básicas
 F=-4
 Aplicando el pivote nuevamente

 La solución es:
 X2=4, x3=2, x6=0  variables básicas
 X1=x4=x5=0  variable son básicas
 F=-10
 Ejemplo 1

 C=[1; 2; 1]
max f  x1  2 x2  x3
 A=[
 2 1 -1
 -2 1 -5
2 x1  x2  x3  2  411
2 x1  x2  5 x3  6  ];
 B=[2;-6;6]
4 x1  x2  x3  6
 Lb=[0;0;0]
xi  0 i  1, 2, 3
 [xopt, fopt,
exitflag,iter,yopt]=karmarkar([],[],C,[],[],[],[],[],A,B,
Lb)
 ejemplo2

min f  2 x1  9 x2  3 x3
 c = [2;9;3];
 A=[
 2 -2 -1
2 x1  2 x2  x3  1  -1 -4 1
 ];
 x1  4 x2  x3  1  b = [-1;-1];
 lb = [0;0;0];
 [xopt,fopt,exitflag,iter,yopt]=karmarkar([],[],c,[],[],[],[],
[],A,b,lb)
xi  0 i  1, 2, 3  [Link]
 [Link]