FORMULACIÓN DE
MODELOS EN PL
Expositor: Dr. Ezzard Omar Alvarez Díaz
Formulación de modelos en PL
Un programa lineal puede formularse
de muy diferentes formas, pero
dentro de la Programación Lineal se
adopta como estándar la siguiente:
Max z cx
sa :
Ax b
x 0
Ezzard Omar Alvarez Díaz
Etapas en la Formulación
de modelos en PL
Definición de Variables
Coeficientes de costos (o de utilidades)
Función Objetivo (F.O)
Término independiente o del lado
derecho (recursos o requerimientos)
Coeficientes tecnológicos
Restricciones funcionales
Restricciones de signo de las variables
Ezzard Omar Alvarez Díaz
Formulación de modelos de
Programación Lineal.
Para formular un problema en forma matemática, deben
expresarse afirmaciones lógicas en términos matemáticos.
Esto se realiza cuando se resuelven “problemas hablados”
al estudiar un curso de álgebra.
Algo muy parecido sucede aquí al formular las
restricciones
Por ejemplo, considérese la siguiente afirmación:
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
Formulación de modelos de
Programación Lineal
Sin embargo, en la mayoría de las situaciones de
negocios, no es obligatorio que se usen todos los
recursos (en este caso, horas de mano de obra).
Más bien la limitación es que se use, cuando mucho,
lo que se tiene disponible.
Para este caso, la afirmación anterior puede
escribirse como una desigualdad:
3A + 2B ≤ 100
Formulación de modelos de
Programación Lineal
Para que sea aceptable para PL, cada restricción debe ser una
suma de variables con exponente 1.
Los cuadrados, las raíces cuadradas, etc. no son aceptables,
ni tampoco los productos de variables.
Además, la forma estándar para una restricción pone a todas
las variables del lado izquierdo y sólo una constante positiva
o cero del lado derecho.
Esto puede requerir algún reacomodo de los términos. Si,
por ejemplo, la restricción es que A debe ser por los menos
el doble de B, esto puede escribirse como:
A ≥ 2B o A - 2B ≥ 0
Formulación de modelos de
Programación Lineal
Nótese que pueden moverse términos de un lado a otro
de las desigualdades como si fuera un signo de igualdad.
Pero al multiplicar una desigualdad por -1, el sentido de
esta desigualdad se invierte.
Puede ser necesario hacer esto para que los coeficientes
del lado derecho sean positivos.
Por ejemplo, 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
Formulación de modelos de
Programación Lineal
Una nota final sobre desigualdades: es sencillo convertir una
desigualdad en una ecuación.
Todo lo que se tiene que hacer es agregar (o restar) una variable extra.
Por ejemplo:
B - A ≤ 2 es lo mismo que B-A+S=2
En donde S representa la diferencia, o la holgura, entre B - A y 2.
S se llama variable de holgura.
Por otro lado, se restaría una variable de superávit en el caso
siguiente:
A - 2B ≥ 0 es lo mismo que A - 2B - S = 0
La metodología de PL requiere que todas las variables sean positivas o
cero, es decir, no negativas.
Para la mayoría de los problemas esto es real, no se querría una solución
que diga: prodúzcanse menos dos cajas o contrátense menos cuatro
personas.
Formulación de modelos de
Programación Lineal
Mientras que no existe un límite en el número de restricciones que
puede tener un problema de PL, sólo puede haber un objetivo.
La forma matemática del objetivo se llama función objetivo.
Debe llevar consigo el maximizar o minimizar alguna medida numérica.
Podría ser maximizar el rendimiento, la ganancia, la contribución
marginal o los contactos con los clientes.
Podría ser minimizar el costo, el número de empleados o el material de
desperdicio.
Con frecuencia el objetivo es evidente al observar el problema.
Como el valor de la función objetivo no se conoce hasta que se
resuelve el problema, se usa la letra Z para representarlo.
La función objetivo tendrá, entonces, la forma:
Maximizar Z = 4A + 6B o también,
Minimizar Z = 2x1 + 5x2
Consejos para formular modelos de
programación lineal.
1. Lea el planteamiento del problema con cuidado.
2. Identifique las variables de decisión.
Éstas son las decisiones que se necesita realizar.
Una vez identificadas estas decisiones, clasifíquelas al
proporcionar una definición matemática (por ejemplo,
x1 = número de unidades producidas y vendidas por
semana del producto 1, x2 = números de unidades
producidas y vendidas por semana del producto 2).
3. Identifique el objetivo. ¿Qué es lo que se debe maximizar
o minimizar (por ejemplo, maximizar la utilidad semanal
total de fabricar los productos 1 y 2)?
Consejos para formular modelos de
programación lineal.
4. Identifique las restricciones estructurales. ¿Qué condiciones se
deben satisfacer cuando asignamos valores a las variables de
decisión?
Tal vez necesite escribir una descripción verbal de la restricción
antes de escribir la representación matemática (por ejemplo, la
producción total del producto 1 ≥ 100 unidades; entonces x1 ≥
100).
También, siéntase cómodo con el hecho de que las restricciones
estructurales para un problema de programación lineal dado
pueden expresar una gran variedad de unidades.
Es decir, dado el conjunto de variable xj, es posible formular
restricciones estructurales que expresen condiciones medidas
en dólares, horas, unidades producidas, etc. Simplemente debe
estar seguro de que la dimensión para cualquier restricción dada
es consistente en ambos lados de la restricción.
5. Formule el modelo matemático. Dependiendo del problema,
podría empezar por definir la función objetivo o las restricciones
estructurales.
¡No olvide incluir la restricción no negativa!
Usos de los PL
Alguno de los tipos de problemas que se
pueden formular son:
Planeación de la producción e inventarios
Mezcla de Alimentos
Transporte y asignación
Planeación financiera
Mercadotecnia
Asignación de recursos
Ezzard Omar Alvarez Díaz
Mezcla de productos...
Considere la producción de 3 artículos; cada uno
produciendo una ganancia unidades monetarias
por unidad. Los artículos hacen uso de los
recursos de dos departamentos; siendo los
tiempos estándares consumidos por cada artículo
por departamento:
Artículo Ganancia Dpto. 1 Dpto. 2
1 c1 a11 a21
2 c2 a12 a22
3 c3 a13 a23
Ezzard Omar Alvarez Díaz
...Mezcla de productos
Si existen un total de tiempos disponibles
de b1 y b2, respectivamente por los
departamentos 1 y 2. ¿Cuál es la mejor
decisión, con la finalidad de optimizar la
ganancia total?
Artículo Ganancia Dpto. 1 Dpto. 2
1 c1 a11 a21
2 c2 a12 a22
3 c3 a13 a23
Ezzard Omar Alvarez Díaz
Solución
Analizando:
¿Cuál es el objetivo de la modelación?
¿Como queremos maximizar la ganancia
total ?
Mediante el producto de la cantidad de
unidades por cada artículo
Entonces nuestras variables de decisión,
corresponden al número de unidades a
producir por cada artículo.
Ezzard Omar Alvarez Díaz
Solución
Sea; xj la cantida de unidades a producir
para el articulo j entonces la FO (función
objetivo), expresará la maximización de la
ganancia total; producto de la contribución de
cada uno de los artículos, de la sgte manera:
Max z c1 x1 c2 x2 c3 x3
Ezzard Omar Alvarez Díaz
Solución
Para la producción de las unidades
expresadas en las variables de decisiones;
se hace necesario, balancear el uso de los
recursos de cada Dpto., con su
disponibilidad; así se tiene que para cada
departamento :
Departamento 1: a11 x1 a12 x2 a13 x3 b1
Departamento 2: a21 x1 a22 x2 a23 x3 b2
x j 0, j 1,2,3
Ezzard Omar Alvarez Díaz
Solución
El modelo de PL, completo se presenta a
continuación:
Max z c1 x1 c2 x2 c3 x3
sa :
a11 x1 a12 x2 a13 x3 b1
a21 x1 a22 x2 a23 x3 b2
x j , j 1,2,3
Ezzard Omar Alvarez Díaz
Modelo de Inventario-
Producción
La demanda de un artículo ha sido
pronosticada, para los siguientes 4 periodos
en las siguientes cantidades: D1, D.2 , D 3, D 4 .
Se sabe que los costos variables de
producción son: C 1, C 2 , C 3, C 4. Asumiendo que
se puede utilizar inventarios, a un costo de
h/unidad . Formular un programa lineal para
minimizar los costos totales, combinación de
costos de producción mas costos por llevar
inventario.
Ezzard Omar Alvarez Díaz
Solución
De lo siguiente:
Inv. final = Inv. inicial + Producción – Demanda
Definiendo :
x Cantidad a producir por periodo.
I0 Como el inventario Inicial.
I Como el inventario Final.
Ezzard Omar Alvarez Díaz
Solución
Período 1:
I 1 I 0 x 1 D1
Período 2:
I 2 I 1 x2 D2
Período 3:
I 3 I 2 x3 D3
Período 4:
I 4 I 3 x4 D4
Ezzard Omar Alvarez Díaz
Solución
Luego el costo total viene dado por la
z = c1x1 + c2x2 + c3x3 + c4x4 + h(I1+I2+I3+I4)
Generalizando para un horizonte de planeación a
n periodos:
Ezzard Omar Alvarez Díaz
Solución
Generalizando para un horizonte de planeación a
n periodos:
n xi n
Min z = hIi
i
i 1 i 1
sa :
Ii Ii 1 xi Di , i 1,2,, n
xi 0
Ii 0 , i 1,2,, n
Ezzard Omar Alvarez Díaz
El Problema del Almacén
Una persona compra y vende artículos. Su
depósito posee una capacidad de B
unidades. Cada mes puede vender
cualquier cantidad sin sobrepasarse el
inventario a principios del mes.
Sean ci y pi, el valor de compra y el precio
respectivo para cada mes. ¿Cuál deberá
ser la política óptima para n períodos, si el
inventario inicial es Io?
Ezzard Omar Alvarez Díaz
Solución
Sea:
yi = cantidad a vender.
xi = cantidad a comprar.
La función objetivo:
n
Max z ( p y c x )
i i i i
i 1
Ezzard Omar Alvarez Díaz
Solución
La función objetivo:
n
Max z ( p y c x )
i i i i
Restricciones: i 1
yi Inventario a inicio de mes i
i 1
yi I 0 x
k 1
k yk
equivalent e a :
i i 1
y
k 1
k xk I 0
k 1
, i 1, 2, , n
Inventario final en i B
i
I0 x
k 1
k yk B , i 1,2, , n
xi , yi 0 , i 1,2, , n
Ezzard Omar Alvarez Díaz
Ejemplo
El granjero Lopez tiene 480 hectáreas de tierra en la
que se puede sembrar ya sea trigo o maíz. El calcula
que tiene 800 horas de trabajo disponible durante la
estación crucial del verano. ¿Cuántas hectáreas de
cada uno debe plantar para maximizar su utilidad?
¿Cuál es ésta utilidad máxima? Si se tiene la
siguiente información de utilidad y requerimiento
de madno de obra:
Utilidad $. Cant. Trabajo Hr
Maíz: 40 2
Trigo: 30 1
Ezzard Omar Alvarez Díaz
Solucion.
Como primer paso para la formulación matemática
de este problema, se tabula la información dada.
Elementos
Maíz Trigo
disponibles
Horas 2 1 800
Hectáreas 1 1 480
Utilidad por unidad $ 40 30
Ezzard Omar Alvarez Díaz
Solución.
Si llamamos x a las hectáreas de maíz e y a las
hectáreas de trigo. Entonces la ganancia total Z, en
dólares, está dada por:
Z=40x+30y
Que viene a ser la función objetivo por maximizar.
Ezzard Omar Alvarez Díaz
Solución.
Elementos
Maíz Trigo
disponibles
Horas 2 1 800
La cantidad total de tiempo por hectáreas para
sembrar maíz y trigo está dada por:
2x+y
Haciendo la restricción por disponibilidad
2x+y < 800
Ezzard Omar Alvarez Díaz
Solución.
Elementos
Maíz Trigo
disponibles
Hectáreas 1 1 480
La cantidad de hectáreas para sembrar maíz y trigo
está dada por:
x+y
Haciendo la restricción por disponibilidad
x+y < 480
Ezzard Omar Alvarez Díaz
Solución.
En resumen, el problema en cuestión queda de la
siguiente manera:
Maximizar Z=40x+30y
Sujeto a:
2x+y <= 800 Hora disp.
x+y < =480 Terreno disp.
x > =0 Positiva
y > =0 Positiva
Ezzard Omar Alvarez Díaz
Ejemplo
Un granjero tiene 100 hectáreas en los cuales puede
sembrar dos cultivos. Dispone de $ 3000 a fin de
cubrir el costo del sembrado. El granjero puede
confiar en un total de 1350 horas-hombre destinadas
a la recolección de los dos cultivos y en el cuadro se
muestra los siguientes datos por hectárea:
Demanda
Tipo de cultivo Costo de plantar horas-hombre Utilidad
pimiento $20 5 $ 100
tomate $40 20 $ 300
Solución
Variables de decisión:
x1 = Cantidad de hectáreas de trigo
x2 = Cantidad de hectáreas de cebada
Función Objetivo: se multiplica el rendimiento por su precio y le
restamos el costo
Utilidad = [30(4,5) – 30] x1 + [25(6) – 40] x2
U= 105 x1+ 110 x2
Restricciones
Limitaciones de tierra: x1 + x2 ≤ 70
Disponibilidad de capital: 30x1 + 40x2 ≤ 2500
Disponibilidad de agua (Octubre): 900 x1 + 650 x2 ≤ 57900
Disponibilidad de agua (Noviembre): 1200 x1 + 850 x2 ≤ 115200
Lógicas o de signos: x1, x2 ≥ 0
Ejemplo
Una familia de granjeros posee 100 hectáreas de tierra y tiene $30000 en fondos
disponibles para inversión. Sus miembros pueden producir un total de 3500 horas-
hombre de mano de obra durante los meses de invierno (de mediados de
Septiembre a mediados de Mayo), 4000 horas-hombre durante el verano. Si no se
necesitan cualesquiera de estas horas-hombre, los miembros más jóvenes de la
familia usarán para trabajar en una granja vecina por $4.00/hora, durante los
meses de invierno, y $4.50/hora, durante el verano.
El ingreso de efectivo puede obtenerse a partir de tres cultivos y dos tipos de
animales: vacas lecheras y gallinas ponedoras. No se necesita invertir en los
cultivos. Sin embargo, cada vaca requerirá un desembolso de $900 y cada gallina
requerirá de $7. Cada vaca requerirá 1.5 hectáreas de tierra, 100 horas-hombre
de trabajo durante los meses de invierno, y otras 50 horas-hombre durante el
verano. Cada vaca producirá un ingreso anual neto en efectivo de $800 para la
familia. Los valores correspondientes para las gallinas son: nada de tierra, 0,6
horas hombre durante el verano y un ingreso anual neto en efectivo de $5. El
gallinero puede acomodar un máximo de 300 gallinas y el tamaño del granero
limita el rebaño a un máximo de 32 vacas. Las horas hombres y los ingresos
estimados por acre plantado en cada uno de los tres cultivos se muestran en la
siguiente tabla.
Solución
Solución: Primero Definimos las variables.
x1 = número de hectáreas de pimiento.
x2 = número de hectáreas de pimiento.
Luego, determinamos la función objetivo:
Maximizar la Utilidad = 100x1 + 300x2
Y por último establecemos las restricciones:
x1 + x2 ≤ 100, Número máximo de hectáreas de tierra.
5x1 + 20x2 ≤ 1350, Número máximo de horas-hombre.
20x1 + 40x2 ≤ 3000, Presupuesto que se dispone para el sembrado.
x1, x2 > 0, No negatividad
(No tiene sentido que estos valores sean negativos).
Ejemplo
Un nutricionista asesora a un individuo que sufre una
deficiencia de hierro y vitamina B, y le indica que
debe ingerir al menos 2400 mg de hierro, 2100 de
vitamina B-1 (tiamina) y 1500 mg de vitamina B-2
(riboflavina) durante cierto período de tiempo.
Existen dos píldoras de vitaminas disponibles, la
marca A y la marca B. Cada píldora de la marca A
contiene 40 mg de hierro, 10 mg de vitamina B-1, 5
mg de vitamina B-2 y cuesta 6 centavos. Cada píldora
de la marca B contiene 10 mg de hierro, 15 mg de
vitamina B-1 y de vitamina B-2, y cuesta 8 centavos
(tabla).
Ezzard Omar Alvarez Díaz
Ejemplo
¿Cuáles combinaciones de píldoras debe comprar
el paciente para cubrir sus requerimientos de
hierro y vitamina al menor costo?
Marca A Marca B Req. mínimos
Hierro 40 mg 10 mg 2400 mg
Vitamina B-1 10 mg 15 mg 2100 mg
Vitamina B-2 5 mg 15 mg 1500 mg
Cost *píldora(US$) 0,06 0,08
Ezzard Omar Alvarez Díaz
Solución.
¿Cual es el objetivo?
Sea “x” el número de píldoras de la marca A; “y” el
número de píldoras de la marca B por comprar. El
costo Z, medido en centavos, está dado por
Z = 0.06x+ 0.08y
Que viene a ser la función objetivo por minimizar.
Ezzard Omar Alvarez Díaz
Solución.
Marca A Marca B Req. mínimos
Hierro 40 mg 10 mg 2400 mg
La cantidad de hierro contenida en x píldoras de la
marca A e y el número de píldoras de la marca B
está dada por:
40x+10y
Haciendo la restricción por cantidad mínima
requerida.
40x+10y < 2400
Ezzard Omar Alvarez Díaz
Solución.
Marca A Marca B Req. mínimos
Vitamina B-1 10 mg 15 mg 2100 mg
La cantidad de Vitamina B-1 contenida en x
píldoras de la marca A e y el número de píldoras de
la marca B está dada por:
10x+15y
Haciendo la restricción por cantidad mínima
requerida.
10x+15y < 2100
Ezzard Omar Alvarez Díaz
Solución.
Marca A Marca B Req. mínimos
Vitamina B-2 5 mg 15 mg 1500 mg
La cantidad de Vitamina B-2 contenida en x
píldoras de la marca A e y el número de píldoras de
la marca B está dada por:
5x+15y
Haciendo la restricción por cantidad mínima
requerida.
5x+15y < 1500
Ezzard Omar Alvarez Díaz
Solución.
En resumen, el problema en cuestión queda de la
siguiente manera:
Minimizar Z = 0.06x+ 0.08y
Sujeto a:
40x+10y < 2400 Hierro.
10x+15y < 2100 Vitamina B-1
5x+15y < 1500 Vitamina B-2
y > 0 Positiva
x > 0 Positiva
Ezzard Omar Alvarez Díaz
