Texto: Simulación de Procesos (CBAS4105) - Luis Blanco C.
Unidad de Aprendizaje V:
PROGRAMACIÓN LINEAL Y SOLUCIÓN GRÁFICA
Objetivos de la unidad:
• Conceptualizar la programación lineal y la utilidad en modelos lineales.
• Ejemplificar casos prácticos de programación lineal con solución gráfica.
1. Generalidades
La programación lineal es una de las técnicas matemática más utilizadas en el campo de la
investigación de operaciones con un campo aplicativo que se extiende desde las industrias y
fuerzas militares hasta la descripción de patrones de conducta social; Esta herramienta
proporciona la optimización (maximizar o minimizar) combinatoria de una serie de variables
de decisión y variables restrictivas (correspondientes a disponibilidad de recursos,
especificaciones técnicas, u otras condicionantes) que generan el mejor escenario de
operación dada una función-objetivo establecida. El término programación se refiere al uso de
ciertas técnicas matemáticas para obtener la mejor solución posible a un problema que
involucra recursos limitados. De lo anterior, se puede precisar su amplio rango de acción a
nivel operativo, táctico y estratégico de una organización; evento que se hace posible gracias
a la adopción de un modelo matemático que incluye un conjunto de ecuaciones lineales que
representan las condiciones reales del problema y una función lineal que expresa el propósito
del mismo y que se denomina función objetivo (Ortíz, 2013, p. 22).
En cualquier empresa, muchas de las decisiones que se toman tienen por objeto hacer el mejor
uso posible (optimización) de los recursos de la misma. Por recursos de una empresa
entendemos la maquinaria que ésta posea, sus trabajadores, capital financiero, instalaciones,
y las materias primas de que disponga. Tales recursos pueden ser usados para fabricar
productos (electrodomésticos, muebles, comida, ropa, etc.) o servicios (horarios de
producción, planes de marketing y publicidad, decisiones financieras, etc.). 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 los recursos.
Como ejemplos de problemas donde la PL desarrolla un papel fundamental, podríamos citar:
1. A partir de los recursos disponibles, determinar las unidades a producir de cada bien de
forma que se maximice el beneficio de la empresa.
2. Elegir materias primas en procesos de alimentación, para obtener mezclas con unas
determinadas propiedades al mínimo coste.
34
Texto: Simulación de Procesos (CBAS4105) - Luis Blanco C.
3. Determinar el sistema de distribución que minimice el coste total de transporte, desde
diversos almacenes a varios puntos de distribución.
4. Desarrollar un plan de producción que, satisfaciendo las demandas futuras de los
productos de una empresa, minimice al mismo tiempo los costes totales de producción e
inventario.
2. Características de un problema de PL
Las técnicas de PL han sido ampliamente utilizadas en ámbitos tan diferentes como el militar,
industrial, financiero, de marketing, e incluso agrícola. A pesar de tal diversidad de
aplicaciones, todos los problemas de PL tienen cuatro propiedades comunes:
1. 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 costes de los
envíos.
2. Habrá que tener en cuenta las restricciones que limitan el grado en el cual es posible
modificar las variables que afectan a nuestra función objetivo. Así, a la hora de decidir
cuántas unidades de cada bien se han de producir, deberemos considerar, entre otras, las
limitaciones de personal y maquinaria de que disponemos.
3. El problema debe presentar distintas alternativas posibles: si una compañía produce
cuatro bienes diferentes, la dirección puede usar PL para determinar las cantidades de
recursos que asigna a la producción de cada uno de ellos (podría optar por hacer una
asignación ponderada, dedicar todos los recursos a la producción de un único bien
abandonando la producción del resto, etc.).
4. En PL, la función objetivo debe ser una función lineal, y las restricciones deben ser
expresables como ecuaciones o inecuaciones lineales.
3. Planteamiento de un problema de PL
Para la construcción del modelo de programación lineal (PL) es necesario seguir una serie de
pasos que involucra la determinación de variables de decisión, definición de restricciones y
formulación de la función objetivo tal como se explica a continuación:
1. Determinación de las variables de decisión: Las variables de decisión representan los
elementos del sistema que pueden ser controlados por el ente decisor. En los modelos
lineales continuos, estas variables toman valores reales y se representan por letras con
subíndices X1, X2, etc.
2. Formulación de la función objetivo: Consiste en una función que mide la calidad de una
solución que hay que optimizar a través de maximización o minimización según sea el caso.
Z = c1X1 + c2X2 + ... + cnXn
35
Texto: Simulación de Procesos (CBAS4105) - Luis Blanco C.
3. Determinación de las restricciones: Las restricciones representan limitaciones en la
disponibilidad de determinados recursos, así como ciertas imposiciones físicas de la
realidad. Se expresan como ecuaciones y/o inecuaciones lineales que se escriben en
función de las variables de decisión. Matemáticamente, pueden ser definidas de las
siguientes formas:
a11X1 + a12X2 + ..... + a1nXn <= b1
............................................. <= ..
am1X1 + am2X2 + ..... + amnXn <= bm
Donde cada uno, son una función lineal.
Por todo lo anterior, la programación lineal tiende a proyectarse como una técnica de
optimización utilizada para la resolución de problemas complejos, variables que interactúan
entre sí, objetivos competitivos y criterios de efectividad; condiciones que rigen el mundo
productivo actual.
Ejemplo: Una empresa fabrica dos modelos de mesas para ordenador, M1 y M2. Para su
producción se necesita un trabajo manual de 20 minutos para el modelo M1 y de 30 minutos
para el M2; y un trabajo de máquina de 20 minutos para M1 y de 10 minutos para M2. Se
dispone de 100 horas al mes de trabajo manual y de 80 horas al mes de máquina. Sabiendo
que el beneficio por unidad es de 1,5 y 1 Bs para M1 y M2 respectivamente, planificar la
producción para obtener el máximo beneficio.
Nos limitaremos ahora a plantear formalmente el problema (ya lo resolveremos más
adelante):
Llamando: X = “nº unidades producidas al mes de M1”, e Y = “nº unidades producidas al mes
de M2”,
nuestra función objetivo sería: Maximizar: Z(X,Y) = 1,5X + Y
y las restricciones vendrán dadas por:
Sujeto a: 20X + 30Y <= 100*60
20X + 10Y <= 80*60
X >= 0
Y >= 0
Las dos últimas restricciones, si bien no constan de forma explícita en el enunciado, sí figuran
de forma implícita, pues el número de mesas a producir no puede ser inferior a 0.
36
Texto: Simulación de Procesos (CBAS4105) - Luis Blanco C.
4. Supuestos básicos de la PL
Desde un punto de vista técnico, hay cinco supuestos que debe cumplir todo problema de
programación lineal:
1. Tanto en la función objetivo como en las restricciones hay proporcionalidad, es decir,
implica que en la función objetivo (z), la utilización de los coeficientes, son directamente
proporcionales al valor de la actividad determinada. Por ejemplo, si para la producción de
un bien empleamos 5 horas de un determinado recurso (mano de obra, maquinaria, etc.),
para producir diez unidades de dicho bien serán necesarias 50 horas del mismo recurso.
2. Aditividad de actividades: tanto en la función objetivo como en las restricciones, la
contribución de cada variable es independiente de los valores del resto de las variables,
siendo el total de todas las actividades igual a la suma de cada actividad individual. Así, por
ejemplo, si producimos dos tipos de bienes, uno que nos reporte un beneficio de 20
Bs./unidad, y otro que nos reporte un beneficio de 10 Bs/unidad, la producción de un bien
de cada tipo supondrá un beneficio total de 30 Bs.
3. Las soluciones del problema serán, en general, números reales no necesariamente enteros
(supuesto de divisibilidad). Entonces, para aquellos problemas en los cuales sólo tenga
sentido obtener soluciones reales (cuando las soluciones se refieran a objetos indivisibles),
se usarán técnicas de Programación Lineal Entera (PLE).
4. Los coeficientes, tanto de la función objetivo como de las restricciones, son conocidos con
exactitud y además no varían durante el período de tiempo en que se realiza el estudio
(supuesto de certidumbre).
5. Las variables de nuestro modelo tomarán siempre valores positivos (supuesto de no
negatividad), dado que no tiene sentido hablar de cantidades negativas de objetos físicos.
Es decir, el resultado de cada una de las variables de decisión en la solución óptima debe
ser positivo.
5. Procesos de Optimización
La Optimización es la búsqueda de la mejor forma de hacer las cosas considerando las
restricciones funcionales, técnicas y económicas de nuestros procesos. La optimización de los
procesos productivos permite a una empresa seguir siendo competitiva. ¿Por qué no hacer de
la optimización un proceso constante, una práctica habitual en las empresas? La tecnología
actual permite que sea posible, con un esfuerzo mínimo, obtener resultados óptimos.
Los cuellos de botella en la producción provocan grandes problemas y retrasos en la entrega
de los productos. Fácilmente se nos olvida que los cuellos de botella son el efecto más que la
causa. Las técnicas de simulación permiten, fácilmente, descubrir la causa de las demoras en
manejo de materiales, la producción, en la información o en cualquier proceso. Optimización
entonces, es el análisis automático de diferentes escenarios a partir de los modelos de
simulación creados, teniendo en cuenta las distintas condiciones, restricciones y variables
clave que afectan al sistema para encontrar la Solución Óptima.
37
Texto: Simulación de Procesos (CBAS4105) - Luis Blanco C.
6. Solución gráfica de un problema de PL
El método gráfico de resolución tan sólo es aplicable a problemas con dos variables (X e Y).
Para aquellos casos en que el número de variables del problema sea superior a dos, no será
posible encontrar la solución a partir de un gráfico bidimensional y, por tanto, tendremos que
usar métodos de resolución más complejos. Aun así, el método gráfico es de un gran valor
pedagógico dado que nos permite vislumbrar de una forma intuitiva las ideas básicas de la PL.
Volviendo al ejemplo de las mesas de ordenador, dado que en él tenemos sólo dos variables,
podremos representar cada una de las restricciones en el plano real. Estas restricciones son
semiespacios (por ser lineales), la intersección de los cuales se denomina región factible (área
de color verde en la figura):
La teoría matemática establece que, dado un problema de PL que tenga solución, ésta vendrá
dada por uno de los vértices (o puntos extremos) del polígono que configura la región factible.
Por tanto, será suficiente hallar las coordenadas de dichos vértices (intersecciones de rectas)
y determinar (sustituyendo en la función objetivo) cuál de ellos es la solución óptima. En
nuestro ejemplo, tendríamos sólo cuatro puntos candidatos a ser solución del problema (los
cuatro vértices del polígono), sustituyendo sus coordenadas en la función objetivo obtenemos:
Z(0,0) = 0; Z(0,200) = 200; Z(210,60) = 375; y Z(240,0) = 360
Como en este caso buscábamos maximizar Z(X,Y), concluiremos que el punto óptimo es el (210,
60), dado que con él obtenemos el valor máximo de la función objetivo. Así pues, la solución a
nuestro dilema será fabricar 210 mesas de tipo M1 y sólo 60 de tipo M2, con ello
conseguiremos unos beneficios de 375 Bs.
38
Texto: Simulación de Procesos (CBAS4105) - Luis Blanco C.
6.1. Casos especiales – Modelos sin solución
A la hora de resolver un problema de PL, nos podríamos encontrar con cualquiera de estas
cuatro situaciones especiales que conviene conocer:
• No Factibilidad: Podría ocurrir que el problema propuesto no tuviese solución. Éste sería el
caso en que las restricciones fuesen incompatibles, i.e., que ningún punto del plano (o, en
general, del espacio real n-dimensional) puede cumplir simultáneamente todas las
limitaciones a las que estamos sometidos, es decir, la región factible es un conjunto vacío o es
un problema con restricciones incompatibles.
• No Acotación: En ocasiones, podemos encontrarnos con problemas que no tengan una
solución finita; así, por ejemplo, en un problema de maximización podríamos tener alguna
variable que pudiese incrementarse indefinidamente sin violar ninguna de las restricciones,
permitiendo a la función objetivo tomar valores tan grandes como se desee. Gráficamente,
tendríamos una región factible no acotada. Una de las probables causas, es la falta de incluir
alguna restricción esencial o se introdujo algún coeficiente con signo equivocado.
• Redundancia: Algunas restricciones pueden “estar demás” por no aportar nada nuevo a la
“forma” de la región factible, ya que hay otras que resultan ser más restrictivas (esto suele
ocurrir en problemas extensos, donde resulta difícil reconocer restricciones redundantes).
• Soluciones Múltiples: Un problema de PL puede tener más de una solución óptima (e incluso
infinita). En el caso gráfico de dos variables, si dos vértices consecutivos de la región factible
son solución óptima del problema, entonces todos los puntos del segmento comprendido
entre ellos también serán óptimos.
39
Texto: Simulación de Procesos (CBAS4105) - Luis Blanco C.
6.2. Ejemplos de resolución gráfica
Ejemplo 1:
La tabla adjunta muestra las unidades de nitrógeno (N) y de fósforo (P) que contiene cada kilo
de los abonos A y B. Se desea obtener un abono que, como mínimo, contenga 9 unidades de
N y 9 unidades de P. El precio de A es de 10 Bs/kg. y el de B es de 20 Bs/kg. Calcular las
cantidades que deben comprarse de A y de B para satisfacer las necesidades minimizando el
coste. Resolver el mismo ejercicio suponiendo que el precio de B es de 30 Bs/kg.
Abono Unidades de N Unidades de P
A 3 1
B 1 3
Llamando X = “nº kilos de A”, e Y = “nº kilos de B”,
La función objetivo es Minimizar: Z(X,Y) = 10X + 20Y
Las restricciones (Sujeto a): 3X + Y >= 9
X + 3Y >= 9
X >= 0
Y >= 0
Graficando:
Evaluando Z(X,Y) en cada uno de los vértices:
Z(0,9) = 180; Z(9/4,9/4) = 67,5; Z(9,0) = 90
Por tanto, la solución óptima es utilizar 9/4 kilos de A y 9/4 kilos de B, lo que supone un costo
(mínimo) de 67,5 Bs. Si ahora consideramos la nueva función objetivo Z(X,Y) = 10X + 30Y,
al evaluar en los vértices (las restricciones no han cambiado), obtenemos: Z(0,9) = 270;
Z(9/4,9/4) = 90; Z(9,0) = 90 → tendremos infinitas soluciones ya que cualquier punto
del segmento que une los dos últimos vértices (éstos incluidos) será un óptimo, obteniéndose
en ellos un costo (mínimo) de Bs 90.
40
Texto: Simulación de Procesos (CBAS4105) - Luis Blanco C.
Ejemplo 2:
Unos grandes almacenes desean liquidar 200 camisas y 100 pantalones de la temporada
anterior. Para ello lanzan dos ofertas, A y B: la oferta A consiste en un lote de una camisa y un
pantalón, que se vende a Bs 30; y la oferta B consiste en un lote de tres camisas y un pantalón,
que se vende a Bs 50. No se desea ofrecer menos de 20 lotes de la oferta A ni menos de 10 de
la B. ¿Cuántos lotes ha de vender de cada tipo para maximizar la ganancia?
Sean: X = “nº lotes tipo A”
Y = “nº lotes tipo B”
La función objetivo es Maximizar: Z(X,Y) = 30X + 50Y
Las restricciones (Sujeto a):
3X + Y <= 200
X + Y <= 100
X >= 20
Y >= 10
Graficando:
Evaluando en los vértices:
Z(20,80) = 4.600; Z(50,50) = 4.000; y Z(190/3,10) = 2.400
Observar que, en este caso, se hace innecesario calcular Z(20,10), pues es claro que su valor
será inferior al de Z(20,80) y al de Z(190/3,10). En definitiva, pues, el resultado es que la
empresa debe vender 20 lotes de tipo A y 80 de tipo B, con lo que tendrá una ganancia
(máxima) de 4.600 Bs.
41
Texto: Simulación de Procesos (CBAS4105) - Luis Blanco C.
Ejemplo 3:
Función objetivo igual a maximización de 5x + 6y
Sujeto a los supuestos de que: x +y ≤ 4
X + 2y ≤ 6
La representación gráfica sería:
Dando valores a la función objetivo vamos obteniendo sucesivas rectas paralelas, de forma
que según aumenta la función objetivo, la recta se separa del origen. Por tanto, puede suceder
que nuestra función objetivo de valor óptimo coincida con una arista o con un vértice del
polígono que delimite nuestro dominio. En nuestro caso, el vértice A(2,2) será la solución
óptima. Luego el valor óptimo de nuestra función objetivo será: 5*2 + 6*2 = 22
Si por el contrario nuestro problema hubiese sido:
Función objetivo igual a maximización de 5x + 6y
Sujeto a los supuestos de que: x+y≥4
x + 2y ≥ 6
La representación gráfica es:
En este caso nuestra solución no está acotada, entonces nuestro problema no tendrá solución.
42
