MODELOS DE DECISIÓN
Programación
lineal
OBJETIVOS
• Explicar que entiende por programación lineal.
• Exponer los pasos para plantear un problema dado.
• Explicar como se forman las restricciones y la funcion
objetivo.
• Mencionar la estructura general de un modelo de
programación lineal.
• Resolver e interpretar problemas mediante el empleo del
concepto de método grafico.
• Resolver e interpretar problemas mediante el empleo del
concepto de método simplex. 2
Concepto de programación lineal
La programación lineal, es un procedimiento
matemático que ayuda a asignar de manera optima
los recursos escasos, consta de una o mas funciones
objetivo, un conjunto de restricciones y una restricción
de no negatividad.
Esta herramienta es una técnica de modelado
matemático diseñada para optimizar el empleo de los
recursos limitados.
Se aplica con éxito en el ejercito, la agricultura, la
industria, el transporte, la economía, los sistemas de
salud e, incluso, en las ciencias conductuales y
sociales. 3
■ La característica distintiva de los modelos de
programación lineal es que las funciones que
representan el objetivo y las restricciones son
lineales.
■ En cualquier empresa, muchas de las decisiones
que se toman tienen por objeto hacer el mejor uso
posible (optimización) de los recursos.
■ Recursos de una empresa : Maquinaria, empleados,
capital financiero, instalaciones, materia prima.
■ La Programación Lineal (PL) es una técnica
matemática diseñada para ayudar a los directivos en
la planificación y toma de decisiones referentes a la
asignación de recursos. 4
Características de un problema de PL
Todos los problemas de PL tienen propiedades comunes
Pretenden optimizar (maximizar o minimizar) alguna
cantidad (función objetivo). Así, por ejemplo, el principal
objetivo de un banquero sería maximizar beneficios,
mientras que el principal objetivo de una empresa
transportista podría ser minimizar los costos de envíos.
Habrá que tener en cuenta las restricciones que afectan a
nuestra función objetivo. Para determinar cuántas
unidades de cada bien se han de producir, considerando
las limitaciones de personal y maquinaria que se dispone.
En PL, la función objetivo debe ser una función lineal, y
las restricciones deben ser inecuaciones lineales para
luego convertirse también en ecuaciones lineales. 5
Ejemplos de problemas donde la PL desarrolla
un papel fundamental
■ A partir de los recursos disponibles, determinar las
unidades a producir de forma que se maximice el
beneficio de la empresa , elegir materias primas en
procesos de alimentación, para obtener mezclas con
unas determinadas propiedades al mínimo costo.
■ Determinar el sistema de distribución que minimice el
costo total de transporte, desde diversos almacenes a
varios puntos de distribución.
■ Desarrollar un plan de producción que, satisfaga
demandas futuras de productos minimizando costos
totales de producción e inventario. 6
Planteamiento de problemas en términos
de programación lineal
Los modelos de programación lineal son
normativos y poseen tres conjuntos básicos
de elementos, a saber:
• Variables de decisión y parámetros.
• Conjunto de restricciones.
• Una o mas funciones objetivos.
7
Los pasos básicos que se deben dar para plantear
un problema en términos de un modelo de
programación lineal (MPL) son los siguientes:
1. Identificar las variables importantes del problema
(variables de decisión) y seleccionar una
notación adecuada para ellas.
2. Plantear la función objetivo en términos de las
variables de decisión.
3. Identificar los recursos limitantes para, de esta
manera, plantear cada una de las restricciones.
4. Formular el modelo de acuerdo con la estructura
general.
8
En su proceso de producción, una pequeña empresa que
elabora diversos productos químicos utiliza 3 materiales para
elaborar 2 productos, un aditivo y un disolvente.
El aditivo se vende a empresas petroleras y se emplea en la
producción de diésel y otros combustibles similares. El
disolvente se vende a empresas químicas para elaborar
productos de limpieza industrial y para el hogar. Para formar
el aditivo y el disolvente se mezclan las tres materias primas
en forma específica.
La tabla 1 muestra que una tonelada de aditivo se obtiene
mezclando 3/7 de 1 000 kg de la materia prima 1; y 4/7 de
1,000 kg de la materia prima 3; una tonelada de disolvente se
logra con la mezcla de 1/4 de 1 000 kg de la materia prima 1,
2/5 de 1 000 kg de la materia prima 2 y 7/20 de 1 000 kg de
9
la materia prima 3.
Debido al deterioro y a la naturaleza del proceso de
producción, cualquier materia prima que no se use
para la producción actual debe desecharse. La utilidad
asciende a $4 000.00 por cada tonelada de aditivo y a
$3 000.00 por cada tonelada de disolvente. Después
de un análisis de la demanda potencial, la
administración de la empresa ha concluido que cuenta
con las siguientes cantidades de materia prima:
Tabla 1 Cantidad de kilogramos disponibles de cada materia prima
10
Plantee el modelo de programación lineal correspondiente.
Solución:
Antes que nada, se extraen los datos del problema para tener
la información de una forma clara y concisa, con la cual se
puede generar la tabla 2
Tabla 2. Extracción de información importante del problema
Una vez elaborada la tabla 2 se deben definir las variables
de decisión que se utilizaran:
Sea: = 1,000 kg de aditivo que se producirán.
= 1,000 kg de disolvente que se producirán. 11
Proceso de restricciones:
En el caso de la materia prima 1, la restricción es:
En el de la materia prima 2 existe la siguiente restricción:
La materia prima 3, padece la siguiente restricción:
El propósito de la empresa es maximizar las utilidades. Por
ello, obtiene la función objetivo siguiente:
Por ultimo, agregamos la restricción de no negatividad:
12
MODELOS DE DECISIÓN
Método gráfico
DEFINICIÓN
El método gráfico se utiliza para solucionar problemas de
programación lineal mediante la representación geométrica
de las restricciones, condiciones técnicas y objetivos.
El modelo puede resolverse en forma gráfica si sólo posee
dos variables; en el caso de modelos con tres o más
variables, resulta impráctico o imposible de aplicar.
Cuando los ejes se relacionan con las variables del
problema, el método se conoce como método gráfico en
actividad. Cuando lo hacen con las restricciones
tecnológicas se denomina método gráfico en recursos. 14
Se recomienda el empleo del método gráfico sólo en
el caso de modelos que incluyan dos variables de
decisión; sin embargo, este método muestra los
conceptos fundamentales que se emplean para
desarrollar las técnicas algebraicas necesarias para
resolver modelos de programación lineal.
El propósito del método gráfico no es proporcionar un
método práctico para resolver problemas lineales,
pues la mayoría de éstos incluyen un gran número de
variables.
Para entender la forma de operar de los modelos de
programación lineal en su forma general, es necesario
conocer los siguientes conceptos: 15
Solución factible
Es aquella con mas de m componentes positivos donde m es
el rango o numero de restricciones. Si una solución básica
factible tiene exactamente m componentes positivos, se dice
que es no degenerada; por el contrario, si tiene menos de m
componentes positivos, es una solución factible
degenerada.
Puede decirse que una solución factible con más de m
componentes positivos es no básica.
Al conjunto de todas las soluciones factibles se le denomina
espacio de soluciones factibles, pero también es conocido
como región factible.
Cabe señalar que existe la posibilidad de que un problema
no tenga soluciones factibles. 16
Los pasos básicos que se deben seguir para resolver un
problema lineal por medio del método grafico son los
siguientes:
1. Después de elaborar el modelo correspondiente, el
siguiente paso consiste en determinar el conjunto de
soluciones de cada una de las restricciones, propósito
que se logra mediante la traficación de cada una en el
plano cartesiano.
2. Identificar la región factible, esto es, la intersección del
conjunto solución de cada una de las restricciones.
3. Marcar los puntos que intersecan en la frontera de la
región factible.
4. Ubicar el o los puntos factibles que den el mejor valor de
la función objetivo. A este punto se le conoce como punto
17
óptimo.
EJEMPLO
Suponga que es el numero de sillas tipo 1 que se
van a producir y que es el numero de sillas tipo 2
que se elaboraran.
Sea el modelo lineal:
Max Z = 4 + 3
Sujeto a: 2+3≤6
–3 + 2 ≤ 3
– 2+ ≤4
–2 , ≥0
Como primer paso, es necesario determinar el
conjunto de soluciones de cada una de las
restricciones. 18
Para obtener el conjunto de soluciones de una desigualdad
en el plano cartesiano, primero debemos considerarlo como
una ecuación con objeto de graficar la recta que limitara al
semiplano correspondiente a la solución de la desigualdad.
Para la primera restricción ----- 2 + 3 ≤ 6
Al quitar la desigualdad --------- 2 + 3 = 6
• Despejamos a sin tomar en cuenta el valor de :
2 = 6 --------- =
Expresión de la cual se obtiene que = 3
• Ahora, despejamos sin tomar en cuenta el valor de :
3 = 6 ------ , que significa que = 2
19
La grafica de la restricción quedaría como se muestra en la
figura 3.
Figura 3. Primera restricción
20