Programación Lineal
Introducción a la
Programación Lineal
Material elaborado por:
Lic. Diego Bernardo Meza Bogado
Campus Universitario
San Lorenzo, Paraguay
Universidad Nacional de Asunción
Facultad de Ciencias Exactas y Naturales
Departamento de Educación a Distancia
Índice
1. Definición de Programación Lineal ..................................................................................................3
2. Historia de la Programación Lineal...................................................................................................3
3. Supuestos de la PL. ...........................................................................................................................4
3.1. Supuesto de proporción: ..................................................................................................5
3.2. Supuesto de aditividad: ....................................................................................................5
3.3. Suposición de ser Divisible: ..............................................................................................5
3.4. Supuesto de Certeza: .......................................................................................................5
4. Formulación de modelos de PL. .......................................................................................................5
5. Forma estándar de los modelos de PL .............................................................................................8
6. Problemas de aplicación para formular un modelo de PL ...............................................................9
6.1. Ejemplo 1: Maximización de producción .........................................................................9
6.2. Ejemplo 2: Proceso de producción. ............................................................................... 10
6.3. Ejemplo 3: Líneas de Producción. ................................................................................. 11
6.4. Ejemplo 4: Caso de toma de decisiones ........................................................................ 13
6.5. Ejemplo 5: Problema de mesclas. ................................................................................. 14
Bibliografía ............................................................................................................................................ 16
2 [Link]
Universidad Nacional de Asunción
Facultad de Ciencias Exactas y Naturales
Departamento de Educación a Distancia
1. Definición de Programación Lineal
Algunas de las definiciones dadas por ciertos autores sobre lo que es la Programación Lineal
(PL)1 y la optimización son citados a continuación:
La PL “es una clase de modelos de programación matemática destinados a la asignación
eficiente de los recursos limitados en actividades conocidas, con el objetivo de satisfacer las
metas deseadas (tal como maximizar beneficios o minimizar costos)” (Taha 1981).
La PL se define como la “planeación de las actividades”, pues, acotan que esta manera de
llamarlo obedece a que la palabra programación no se refiere a la programación de
computadoras, sino a la de planeación (Hillier 2002).
La Investigación de Operaciones (IO) es la aplicación del método científico al estudio de los
problemas de toma de decisión en situaciones determinísticas o probabilísticas al interior de
sistemas complejos, considerando la formulación de un modelo generalmente matemático
que permita estudiar el problema y desarrollar una solución que indique el mejor u óptimo
curso de acción posible, coherente con los objetivos globales del sistema” (Devoto R. & Ruiz
E., 2003).
A la hora de tomar decisiones importantes uno de los problemas fundamentales es elegir de
un conjunto de alternativas (soluciones factibles de un problema de interés), la mejor de
ellas, o mejor dicho “la decisión óptima”, según algún criterio previamente definido.
La optimización es una técnica que busca, con base en distintos modelos matemáticos, la
asignación eficiente de recursos, siempre escasos, requeridos en diversas actividades
productivas que compiten entre sí, con el propósito de satisfacer los objetivos deseados en
el sector productivo, financiero, agrícola, entre otros, y que suelen ser la maximización o
minimización de alguna cantidad tal como: costo, beneficio, tiempo, desperdicio, etc.
(González J., Salaz, A., 2000).
2. Historia de la Programación Lineal
La PL se plantea como un modelo matemático desarrollado durante la Segunda Guerra
Mundial para planificar los gastos y los retornos, a fin de reducir los costos al ejército y
aumentar las pérdidas del enemigo. Se mantuvo en secreto hasta 1947. En la posguerra,
muchas industrias lo usaron en su planificación diaria.
La fundación de las técnicas de PL se atribuye a varios científicos, entre ellos George Dantzig,
quien en 1947 publico el algoritmo simplex, y John von Neumann quien en 1947 desarrolló la
teoría de la dualidad. En 1979, un matemático Ruso, Leonid Khachiyan, demostró que el
1
De aquí en adelante utilizaremos PL como abreviatura de Programación Lineal.
3 [Link]
Universidad Nacional de Asunción
Facultad de Ciencias Exactas y Naturales
Departamento de Educación a Distancia
problema de la PL era resoluble en tiempo polinomial. Un importante aporte fue dado en
1984 por Narendra Karmarkar quien introduce un nuevo método del punto interior para
resolver problemas de PL, lo que constituiría un enorme avance en los principios teóricos y
prácticos en el área.
El ejemplo original de Dantzig de la búsqueda de la mejor asignación de 70 personas a 70
puestos de trabajo es un ejemplo de la utilidad de la PL. La potencia de computación
necesaria para examinar todas las permutaciones a fin de seleccionar la mejor asignación es
inmensa; el número de posibles configuraciones excede al número de partículas en el
universo. Sin embargo, toma sólo un momento encontrar la solución óptima mediante el
planteamiento del problema como una PL y la aplicación del algoritmo simplex. La teoría de
la PL reduce drásticamente el número de posibles soluciones óptimas que deberán ser
revisadas.
La PL constituye un importante campo de la optimización por varias razones, muchos
problemas prácticos de la investigación de operaciones pueden plantearse como problemas
de PL. Algunos casos especiales de PL, tales como los problemas de flujo de redes y
problemas de flujo de mercancías se consideraron en el desarrollo de las matemáticas lo
suficientemente importantes como para generar por sí mismos mucha investigación sobre
algoritmos especializados en su solución. Una serie de algoritmos diseñados para resolver
otros tipos de problemas de optimización constituyen casos particulares de la más amplia
técnica de la PL.
Históricamente, las ideas de PL han inspirado muchos de los conceptos centrales de la teoría
de optimización tales como la dualidad, la descomposición y la importancia de la convexidad
y sus generalizaciones. Del mismo modo, la PL es muy usada en la microeconomía y la
administración de empresas, ya sea para aumentar al máximo los ingresos o reducir al
mínimo los costos de un sistema de producción. Algunos ejemplos son la mezcla de
alimentos, la gestión de inventarios, la cartera y la gestión de las finanzas, la asignación de
recursos humanos y recursos de máquinas, la planificación de campañas de publicidad, etc.
3. Supuestos de la PL.
De acuerdo a Hillier (2002) desde un punto de vista matemático, los supuestos simplemente
son que el modelo debe tener una función objetivo lineal sujeta a restricciones lineales. Sin
embargo, desde el punto de vista de modelación, estas propiedades matemáticas de un
modelo de PL implican que se deben considerar ciertos supuestos acerca de las actividades y
datos del problema que será modelado, incluso algunos acerca del efecto de las variaciones
en el nivel de las actividades. Vale la pena hacer hincapié en ellas para que sea más sencillo
evaluar si esta técnica es adecuada para un problema dado.
4 [Link]
Universidad Nacional de Asunción
Facultad de Ciencias Exactas y Naturales
Departamento de Educación a Distancia
3.1. Supuesto de proporción:
La contribución de la función objetivo para cada variable de decisión, es proporcional al valor
de ésta. Por ejemplo, producir dos veces más de producto producirá dos veces más de
ganancia, contratando el doble de páginas en las revistas doblará el costo relacionado con
las revistas.
3.2. Supuesto de aditividad:
Cada función de un modelo de programación lineal (ya sea la función objetivo o el lado
izquierdo de las restricciones funcionales) es la suma de las contribuciones individuales de
las actividades respectivas.
3.3. Suposición de ser Divisible:
Esta suposición requiere que todas las variables de decisión puedan asumir valores
fraccionarios. Es decir, es posible tomar una fracción de cualquier variable. Por ejemplo, en
un problema de marketing, ¿qué significa comprar 2,67 avisos en la televisión?
3.4. Supuesto de Certeza:
Para esa suposición, se requiere conocer con certeza todos los parámetros (coeficientes de
la función objetivo, segundo miembro y coeficientes tecnológicos). Si hay incertidumbre en
la cantidad exacta de horas necesarias para manufacturar un producto, se incurrirá en una
violación a la suposición de certidumbre.
Será difícil que un problema cumpla con todas las suposiciones de manera exacta. Pero esto
no negará la factibilidad de uso del modelo. Un modelo puede ser aún útil aunque difiera de
la realidad, si se es consistente con los requerimientos más estrictos dentro del modelo y se
tiene claras sus limitaciones al interpretar los resultados.
4. Formulación de modelos de PL.
Aunque se ponga en duda, la parte más difícil de PL es reconocer cuándo ésta puede
aplicarse y formular el problema matemáticamente. Una vez hecha esa parte, resolver el
problema casi siempre es fácil.
Según la definición dada por Winston (2005), un modelo matemático es una representación
matemática de situaciones reales que se podrían usar para tomar mejores decisiones, o
bien, simplemente para entender mejor la situación real. Un modelo matemático en PL
consta de tres elementos o condiciones básicas: Las Variables de decisión, la Función
Objetivo y las Restricciones.
5 [Link]
Universidad Nacional de Asunción
Facultad de Ciencias Exactas y Naturales
Departamento de Educación a Distancia
Para formular un problema en forma matemática, debemos expresar las 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: 𝐴usa 3 horas por unidad y 𝐵 usa 2 horas
por unidad. Si deben usarse todas las 100 horas disponibles, la restricción será:
3𝐴 + 2𝐵 = 100
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:
3𝐴 + 2𝐵 ≤ 100
Las restricciones en un modelo de PL limitan el valor de las variables de decisión e indican
cómo se relacionan estas con los recursos disponibles.
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
𝐴debe ser por los menos el doble de𝐵, esto puede escribirse como:
𝐴 ≥ 2𝐵 ó 𝐴 − 2𝐵 ≥ 0
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𝐴sea por lo menos tan grande como
𝐵 − 2, entonces:
𝐴≥𝐵−2
ó 𝐴 − 𝐵 ≥ −2
por último 𝐵 − 𝐴 ≤ 2
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:
𝐵 − 𝐴 ≤ 2 es lo mismo que 𝐵 − 𝐴 + 𝑆 = 2
en donde 𝑆 representa la diferencia, o la holgura, entre 𝐵 − 𝐴 y 2. 𝑆 se llama variable de
holgura. Por otro lado, se restaría una variable de superávit en el caso siguiente:
6 [Link]
Universidad Nacional de Asunción
Facultad de Ciencias Exactas y Naturales
Departamento de Educación a Distancia
𝐴 − 2𝐵 ≥ 0 es lo mismo que 𝐴 − 2𝐵 − 𝑆 = 0
Algunos métodos de solución (como el Método Símplex) y la mayoría de los programas de
computadora requieren que todas las desigualdades se conviertan en igualdades.
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.
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.
En cualquier problema de PL, el que toma las decisiones desea maximizar (por lo general, los
ingresos o las utilidades) o reducir al mínimo (casi siempre, los costos) algunas funciones de
las variables de decisión. La función que se desea maximizar o minimizar recibe el nombre de
función objetivo. (Winston, W. (2005))
La función objetivo es una representación matemática de la meta total de optimización
establecida en términos de las variables de decisión (Devoto R. & Ruiz E., 2003).
Como el valor de la función objetivo no se conoce hasta que se resuelve el problema, se usa
la letra 𝑍 para representarlo. La función objetivo tendrá, entonces, la forma:
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑍 = 4𝐴 + 6𝐵 ó 𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟 𝑍 = 4𝑥1 + 5𝑥2
Modelo de Cuando se desea maximizar o incrementar las: Utilidades,
Maximización Producción, Ventas, Beneficios, Rentabilidad, Publicidad, etc.
Modelo de Cuando se desea minimizar o disminuir los: Costos, pérdidas,
Minimización paradas, desperdicios, distancias, tiempos, etc.
La solución óptima se obtiene cuando el valor de la Función Objetivo es óptimo (valor
máximo o mínimo), para un conjunto de valores factibles de las variables.
Por ejemplo, si el objetivo es minimizar los costos de operación, la función objetivo debe
expresar la relación entre el costo y las variables de decisión, siendo el resultado el menor
costo de las soluciones factibles obtenidas.
7 [Link]
Universidad Nacional de Asunción
Facultad de Ciencias Exactas y Naturales
Departamento de Educación a Distancia
A la hora de tomar decisiones importantes uno de los problemas fundamentales es elegir de
un conjunto de alternativas (soluciones factibles de un problema de interés), la mejor de
ellas, o mejor dicho “la decisión óptima”, según algún criterio previamente definido.
La optimización es una técnica que busca, con base en distintos modelos matemáticos, la
asignación eficiente de recursos, siempre escasos, requeridos en diversas actividades
productivas que compiten entre sí, con el propósito de satisfacer los objetivos deseados en
el sector productivo, financiero, agrícola, entre otros, y que suelen ser la maximización o
minimización de alguna cantidad tal como: costo, beneficio, tiempo, desperdicio, etc.
(González J., Salazar, A., 2000)
5. Forma estándar de los modelos de PL
Supongamos que existe cualquier número (digamos 𝑚) de recursos limitados de cualquier
tipo, que se pueden asignar entre cualquier número (digamos𝑛) de actividades competitivas
de cualquier clase. Llamamos a los recursos con números (1, 2, … , 𝑚) al igual que las
actividades (1, 2, … , 𝑛). Sea 𝑥𝑖 (una variable de decisión) el nivel de la actividad 𝑗, para 𝑗 =
1, 2, … , 𝑛, y sea 𝑍la medida de efectividad global seleccionada. Sea 𝑐𝑗 el incremento que
resulta en 𝑍 por cada incremento unitario en 𝑥𝑖 (para𝑗 = 1, 2, … , 𝑛). Ahora sea 𝑏𝑖 la cantidad
disponible del recurso 𝑖 (para𝑖 = 1, 2, … , 𝑚). Por último defínase 𝑎𝑖𝑗 como la cantidad de
recurso 𝑖 que consume cada unidad de la actividad 𝑗 (para 𝑖 = 1, 2, … , 𝑚 y 𝑗 = 1, 2, … , 𝑛). Se
puede formular el modelo matemático para el problema general de asignar recursos a
actividades. En particular, este modelo consiste en elegir valores de 𝑥1 , 𝑥2 , … , 𝑥𝑛 para:
Maximizar 𝑍 = 𝑐1 𝑥1 , 𝑐2 𝑥2 , … , 𝑐𝑛 𝑥𝑛
Sujeto a las restricciones:
𝑎11 𝑥1 , 𝑎12 𝑥2 , … , 𝑎1𝑛 𝑥𝑛 ≤ 𝑏1
𝑎21 𝑥1 , 𝑎22 𝑥2 , … , 𝑎2𝑛 𝑥𝑛 ≤ 𝑏2
𝑎31 𝑥1 , 𝑎32 𝑥2 , … , 𝑎3𝑛 𝑥𝑛 ≤ 𝑏3
𝑎𝑚1 𝑥1 , 𝑎𝑚2 𝑥2 , … , 𝑎𝑚𝑛 𝑥𝑛 ≤ 𝑏𝑚
𝑥1 ≥ 0, 𝑥2 ≥ 0, … , 𝑥𝑛 ≥ 0
Ésta se llamará nuestra forma estándar para el problema de PL. Cualquier situación cuya
formulación matemática se ajuste a este modelo es un problema de PL.
En este momento se puede resumir la terminología que usaremos para los modelos de PL. La
función que se desea maximizar, 𝑍 = 𝑐1 𝑥1 , 𝑐2 𝑥2 , … , 𝑐𝑛 𝑥𝑛 se llama función objetivo. Por lo
8 [Link]
Universidad Nacional de Asunción
Facultad de Ciencias Exactas y Naturales
Departamento de Educación a Distancia
general, se hace referencia a las limitaciones como restricciones. Las primeras 𝑚
restricciones (aquellas con una función del tipo 𝑎𝑖1 𝑥1 , 𝑎𝑖2 𝑥2 , … , 𝑎𝑖𝑛 𝑥𝑛 , que representa el
consumo total del recurso 𝑖) reciben el nombre de restricciones funcionales. De manera
parecida, las restricciones 𝑥𝑗 ≥ 0 se llaman restricciones de no negatividad. Las variables 𝑥𝑗
son las variables de decisión. Las constantes de entrada, 𝑎𝑖𝑗 , 𝑏𝑖 , 𝑐𝑗 reciben el nombre de
parámetros del modelo.
6. Problemas de aplicación para formular un modelo de PL
Los problemas de PL podemos presentarlos en la forma estándar, dando la función objetivo
y las restricciones para ello seguiremos el procedimiento que indicamos a continuación, con
los siguientes ejemplos.
6.1. Ejemplo 1: Maximización de producción
En un almacén se guarda aceite de girasol y de oliva. Para atender a los clientes se han de
tener almacenados un mínimo de 20 bidones de aceite de girasol y 40 de aceite de oliva y,
además, el número de bidones de aceite de oliva no debe ser inferior a la mitad del número
de bidones de aceite de girasol. La capacidad total del almacén es de 150 bidones. Sabiendo
que el gasto de almacenaje es el mismo para los dos tipos de aceite (1 unidad monetaria).
¿Cuántos bidones de cada tipo habrá que almacenar para que el gasto sea máximo?
Solución:
Paso 1º: Leer detenidamente el enunciado: determinar el objetivo, definir las variables y
escribir la función objetivo.
El objetivo es: halla cuántos bidones de cada tipo hay que almacenar para maximizar los
gastos
Suponemos que tal objetivo se consigue almacenado 𝒙 bidones de aceite de girasol e 𝒚 de
aceite de oliva
Cómo cada bidón de aceite de girasol cuesta almacenarlo 1 unidad monetaria y lo mismo
para uno de aceite, los gastos serán 𝑥 + 𝑦
Luego, la función objetivo es:
Maximizar 𝑍 = 𝑥 + 𝑦
Paso 2º: Reordenar los datos del problema y a partir de las cantidades decididas, 𝒙 e 𝒚,
escribir el sistema de inecuaciones que determinan las restricciones.
Un mínimo de 20 bidones de aceite de girasol: 𝑥 ≥ 20
Un mínimo de 40 bidones de aceite de oliva: 𝑦 ≥ 40
El número de bidones de aceite de oliva no debe ser inferior a la mitad del número de
bidones de aceite de girasol: 𝑦 ≥ 𝑥/2
La capacidad total del almacén es de 150 bidones: 𝑥 + 𝑦 ≤ 150
9 [Link]
Universidad Nacional de Asunción
Facultad de Ciencias Exactas y Naturales
Departamento de Educación a Distancia
Además, los números de bidones deben ser cantidades positivas: 𝑥 ≥ 0;𝑦 ≥ 0.
Paso 3º: Expresar el problema en la forma estándar.
Siguiendo con el ejemplo, sería:
Maximizar: 𝑍 =𝑥+𝑦
sujeto a las restricciones: 𝑥 + 𝑦 ≤ 150
𝑦 ≥ 𝑥/2
𝑥 ≥ 0;𝑦 ≥ 0
6.2. Ejemplo 2: Proceso de producción.
Una fábrica produce dos tipos de productos: M y N, los costos de producción de ambos
productos son $3 para el producto M y $5 para el producto N. El tiempo total de producción
está restringido a 500 horas; y los tiempos de producción son de 8 horas/unidad para el
producto M y de 4 horas/unidad para el producto N. Formule el Modelo matemático que
permita determinar la cantidad de productos M y N a producir, y que optimice el Costo total
de producción de los dos productos.
Solución:
Paso 1º: Definición de Variables y la Función Objetivo
Se desea formular un modelo matemático para determinar la cantidad que debe producirse
por cada producto (M y N), por lo tanto tendremos dos variables, representados por:𝑥1 , 𝑥2
Siendo: 𝑥1 = 𝐶𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑎 𝑝𝑟𝑜𝑑𝑢𝑐𝑖𝑟𝑠𝑒 𝑑𝑒𝑙 𝑝𝑟𝑜𝑑𝑢𝑐𝑡𝑜 𝑀,
𝑥2 = 𝐶𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑎 𝑝𝑟𝑜𝑑𝑢𝑐𝑖𝑟𝑠𝑒 𝑑𝑒𝑙 𝑝𝑟𝑜𝑑𝑢𝑐𝑡𝑜 𝑁
Como se tiene información de Costos de producción de los productos M y N, el objetivo será
minimizarlos:
Costo total de producción de M
𝑀 = (𝐶𝑜𝑠𝑡𝑜 𝑢𝑛𝑖𝑡𝑎𝑟𝑖𝑜 𝑑𝑒 𝑝𝑟𝑜𝑑𝑢𝑐𝑐𝑖ó𝑛 𝑀) ∗ (𝐶𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑎 𝑝𝑟𝑜𝑑𝑢𝑐𝑖𝑟 𝑑𝑒𝑙 𝑝𝑟𝑜𝑑𝑢𝑐𝑡𝑜 𝑀)
Costo total de producción de M
𝑀 = (3$/𝑢𝑛𝑖𝑑𝑎𝑑) ∗ (𝑥1 ) = 3𝑥1 $
Costo total de producción de N
𝑁 = (𝐶𝑜𝑠𝑡𝑜 𝑢𝑛𝑖𝑡𝑎𝑟𝑖𝑜 𝑑𝑒 𝑝𝑟𝑜𝑑𝑢𝑐𝑐𝑖ó𝑛 𝑁) ∗ (𝐶𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑎 𝑝𝑟𝑜𝑑𝑢𝑐𝑖𝑟 𝑑𝑒𝑙 𝑝𝑟𝑜𝑑𝑢𝑐𝑡𝑜 𝑁)
Costo total de producción de N
𝑁 = (5$/𝑢𝑛𝑖𝑑𝑎𝑑) ∗ (𝑥2 ) = 5𝑥2 $
Luego la Función Objetivo será Minimizar “C” igual al Costo total de producción del producto
𝑀 más el Costo total de producción del producto 𝑁.
10 [Link]
Universidad Nacional de Asunción
Facultad de Ciencias Exactas y Naturales
Departamento de Educación a Distancia
Matemáticamente la Función Objetivo es:
𝑀í𝑛𝑖𝑚𝑜 𝐶 = 3𝑥1 + 5𝑥2
Paso 2º: Definición de las Restricciones
El tipo de recurso en el problema es el tiempo (puede ser horas hombre u horas máquina).
Formulamos la restricción, colocando en el lado izquierdo de la inecuación el consumo
unitario de los productos 𝑀 y 𝑁, y en el lado derecho la cantidad disponible del recurso (500
horas).
(𝑡. 𝑢𝑛𝑖𝑡. 𝑝𝑟𝑜𝑑. 𝑀) ∗ (𝐶𝑎𝑛𝑡. 𝑝𝑟𝑜𝑑. 𝑀) + (𝑡. 𝑢𝑛𝑖𝑡. 𝑝𝑟𝑜𝑑. 𝑁) ∗ (𝐶𝑎𝑛𝑡. 𝑝𝑟𝑜𝑑. 𝑁) ≤ 500
(8 ℎ𝑠/𝑢𝑛𝑖𝑑) ∗ (𝑥1 ) + (4ℎ𝑠/𝑢𝑛𝑖𝑑) ∗ (𝑥2 ) ≤ 500
Matemáticamente la restricción queda:
8𝑥1 + 4𝑥2 ≤ 500
También debemos considerar la condición de no negatividad
𝑥1 ≥ 0, 𝑥2 ≥ 0 ó 𝑥𝑖 ≥ 0; 𝑐𝑜𝑛 𝑖 = 1,2
Resumiendo, tenemos el siguiente Modelo matemático de PL del Problema (un modelo con
dos variables y una restricción, estando listo para aplicar un método de solución:
Minimizar: 𝐶 = 3𝑥1 + 5𝑥2
Sujeto a las restricciones: 8𝑥1 + 4𝑥2 ≤ 500
𝑥1 ≥ 0, 𝑥2 ≥ 0
6.3. Ejemplo 3: Líneas de Producción.
Un empresario tiene 80 kg de acero y 120 kg de aluminio, y quiere fabricar dos modelos de
bicicletas: bicicletas de paseo y bicicletas de montaña, para venderlas en el mercado a S/.
200 y S/. 150 respectivamente cada modelo, a fin de obtener el máximo beneficio. Para la
bicicleta de paseo empleará 1 kg de acero y 3 kg de aluminio, y para la bicicleta de montaña
usará 2 kg de ambos metales. Formular el modelo matemático de PL, que permita
determinar la cantidad óptima de bicicletas a producir, para obtener el mayor beneficio
económico.
Solución:
Paso 1º: Definición de Variables y la Función Objetivo
Se desea determinar la cantidad de bicicletas a producir por cada modelo (paseo y
montaña), por lo tanto tendremos dos variables.
11 [Link]
Universidad Nacional de Asunción
Facultad de Ciencias Exactas y Naturales
Departamento de Educación a Distancia
Sean: 𝑥1 = 𝐶𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑑𝑒 𝑏𝑖𝑐𝑖𝑐𝑙𝑒𝑡𝑎𝑠 𝑑𝑒 𝑝𝑎𝑠𝑒𝑜 𝑎 𝑓𝑎𝑏𝑟𝑖𝑐𝑎𝑟,
𝑥2 = 𝐶𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑑𝑒 𝑏𝑖𝑐𝑖𝑐𝑙𝑒𝑡𝑎𝑠 𝑑𝑒 𝑚𝑜𝑛𝑡𝑎ñ𝑎 𝑎 𝑓𝑎𝑏𝑟𝑖𝑐𝑎𝑟
El objetivo del problema es maximizar los beneficios económicos totales (𝑍) de los modelos
de bicicletas que fabricará el empresario.
Precio de venta de la bicicleta de paseo = $200
Precio de venta de la bicicleta de montaña =$150
Beneficio económico = (Precio de venta unitario).(cantidad a fabricar)
Beneficio económico total de bicicleta de paseo = $200𝑥1
Beneficio económico total de bicicleta de montaña = $150𝑥2
Luego la Función objetivo será: 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑍 = 200𝑥1 + 150𝑥2
Paso 2º: Definición de las Restricciones
Elaboramos una tabla de materia prima consumida (Acero y Aluminio) por cada modelo de
bicicleta (paseo y montaña) y su disponibilidad:
Modelo de bicicleta Acero Aluminio
Paseo 1 kg. 3 kg.
Montaña 2 kg. 2 kg.
Disponibilidad de materia prima 80 kg. 120 kg.
Restricción del consumo de Acero en la fabricación de bicicletas:
1𝑥1 + 2𝑥2 ≤ 80
Restricción del consumo de Aluminio en la fabricación de bicicletas:
3𝑥1 + 2𝑥2 ≤ 120
Observación:
El lado derecho de las restricciones, 80 y 120 representa la disponibilidad en [Link] acero y
aluminio respectivamente (materia prima). El lado izquierdo en las restricciones indica el
consumo unitario de materia prima por cada modelo de bicicleta.
Condición de no negatividad: La producción de cada modelo de las bicicletas pueden ser
cero (0) o mayor que cero, o sea: 𝑥1 , 𝑥2 ≥ 0
Luego el Modelo matemático de PL (con dos variables y dos restricciones) será:
Maximizar: 𝑍 = 200𝑥1 + 150𝑥2
Sujeto a las restricciones: 𝑥1 + 2𝑥2 ≤ 80
3𝑥1 + 2𝑥2 ≤ 120
𝑥1 , 𝑥2 ≥ 0
12 [Link]
Universidad Nacional de Asunción
Facultad de Ciencias Exactas y Naturales
Departamento de Educación a Distancia
6.4. Ejemplo 4: Caso de toma de decisiones
Suponga con los datos del ejemplo 3, si el empresario por restricción económica decide
hacer solo un modelo de bicicleta. ¿Cuál modelo debe elegir? ¿Por qué? Las alternativas de
fabricación se desarrollan en las restricciones del Modelo matemático; y la toma de
decisiones se determina evaluando en la Función objetivo las alternativas obtenidas. La
decisión a tomar, por restricción económica, es producir un solo modelo de bicicleta que
genere mayor beneficio al empresario. Luego desarrollamos las alternativas evaluando en las
restricciones del modelo:
Solución:
Alternativa 1: Producir solo bicicletas de paseo y no producir bicicletas de montaña, significa
hallar𝑥1 haciendo𝑥2 = 0
Reemplazamos en la primera restricción:
𝑥1 +2𝑥2 ≤ 80; 𝑥1 + 2(0) ≤ 80; luego: 𝑥1 ≤ 80
Reemplazamos en la segunda restricción:
3𝑥1 + 2𝑥2 ≤ 120; 3𝑥1 + 2. (0) ≤ 120; luego: 3𝑥1 ≤ 120; ó 𝑥1 ≤ 40
Tomamos el valor de𝑥1 que cumple en ambas restricciones, y debe ser el mínimo de los
valores obtenidos: 𝑀𝑖𝑛(80; 40) = 40; o sea: 𝑥1 = 40
Alternativa 2: Producir solo bicicletas de montaña y no producir bicicletas de paseo, significa
hallar𝑥2 haciendo𝑥1 = 0.
Seguimos el mismo procedimiento realizado en el punto anterior, evaluando en las
restricciones del modelo y hallamos que 𝑥2 = 40.
La toma de decisiones se realiza evaluando en la Función objetivo las alternativas de
fabricación obtenidas por modelo de bicicleta. A continuación se muestra el procedimiento a
realizar.
Beneficio económico de fabricar solo bicicletas de paseo y no fabricar bicicletas de
montaña:
Alternativa 1: Para𝑥1 = 40 y𝑥2 = 0
Reemplazando en la Función Objetivo: 𝑍 = 200𝑥1 + 150𝑥2 , obtenemos:
𝑍 = $8000.
Beneficio económico de fabricar solo bicicletas de montaña y no fabricar bicicletas de
paseo:
Alternativa 2: Para 𝑥2 = 40 y 𝑥1 = 0
Reemplazando en la Función Objetivo: 𝑍 = 200𝑥1 + 150𝑥2 , obtenemos: 𝑍 = $6000.
13 [Link]
Universidad Nacional de Asunción
Facultad de Ciencias Exactas y Naturales
Departamento de Educación a Distancia
Como la Función objetivo es maximizar el beneficio económico, generado por las ventas,
tomamos la decisión de fabricar solo bicicletas de paseo, por ser el modelo que va generar
mayor ganancia, equivalente a $8.000.
Observación:
Hemos demostrado la importancia de formular un modelo matemático adecuado, ya que un
error en la formulación del Modelo, nos puede llevar a tomar una decisión equivocada que
puede generar graves consecuencias para la empresa u organización.
6.5. Ejemplo 5: Problema de mesclas.
Se quiere elaborar una dieta para ganado que satisfaga unas condiciones mínimas de
contenidos vitamínicos al día: 2 mg de vitamina A, 3 mg de vitamina B, 30 mg de la C y 2 mg
de la D. Para ello, se van a mezclar pastos de dos tipos, P y Q, cuyo precio por kilo es, para
ambos, de 0,3 € y cuyo contenido vitamínico en miligramos por kilo es el siguiente:
Vitaminas
Pastos A B C D
P 1 1 20 2
Q 1 3 7,5 0
¿Cómo deben mezclarse los pastos para que el gasto sea mínimo?
Paso 1º: Definición de Variables y la Función Objetivo
Llamamos 𝑥 al pasto de tipo P (en kg.) e 𝑦 al de tipo Q (en kg.). El objetivo del problema es
minimizar los costos totales (𝑍). Como el precio por kilo para ambos es de 0,3€. La Función
objetivo será:
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟 𝑍 = 0,3𝑥 + 0,3𝑦
Paso 2º: Definición de las Restricciones
Definiremos las restricciones para cada vitamina. De acuerdo al enunciado se necesitan
como mínimo 2mg de la vitamina A al día y según la tabla el contenido del mismo es de 1 mg
por kg en el pasto de tipo P y también 1mg por kg en el pasto de tipo Q, entonces tenemos la
1ra restricción:
1𝑥 + 1𝑦 ≥ 2, ó 𝑥 + 𝑦 ≥ 2
De igual manera obtenemos la restricción para la vitamina B,
𝑥 + 3𝑦 ≥ 3
Para la vitamina C, tenemos:
20𝑥 + 7,5𝑦 ≥ 30
14 [Link]
Universidad Nacional de Asunción
Facultad de Ciencias Exactas y Naturales
Departamento de Educación a Distancia
y también para la vitamina D
2𝑥 ≥ 2, que es lo mismo 𝑥 ≥ 1
También debemos agregar la restricción de no negatividad, en este caso ya está claro que x
no puede ser menor que 1, pero para la y no, por tanto:
𝑦 ≥ 0.
Luego el Modelo matemático de PL (con dos variables y todas las restricciones) será:
Minimizar: 𝑍 = 0,3𝑥 + 0,3𝑦
𝑥+𝑦 ≥2
𝑥 + 3𝑦 ≥ 3
20𝑥 + 7,5𝑦 ≥ 30
𝑥≥1
𝑦≥0
15 [Link]
Universidad Nacional de Asunción
Facultad de Ciencias Exactas y Naturales
Departamento de Educación a Distancia
Bibliografía
HILLIER, F. y LIEBERMAN, G.(1982).“Introducción a la Investigación Operativa”. Mc Graw Hill.
TAHA, A. (2004).“Investigación de operaciones”. 7a. edición. PEARSON
----------EDUCACIÓN. México. ISBN: 970-26-0498-2
WINSTON, L. (2005).“Investigación de operaciones: aplicaciones y algoritmos”. ---------
[Link]ón. THOMPSON. ISBN: 9706863621, 9789706863621
GONZÁLEZ, J. & SALAS A. (2000).“Introducción a la Programación Lineal”. 1a. ------------
edición. UNIVERSIDAD DE MANIZALEZ
DEVOTO, R. & RUIZ, E. (2003).“ Programación Lineal para Administración”. ----------------
CHILE. EDICIONES UNIVERSITARIAS DE VALPARAÍSO.
16 [Link]
