PROGRAMACION LINEAL
ING. MICAELA MIRANDA
INTRODUCCION A LA PROGRAMACION LINEAL
El objetivo de un modelo matemático es reproducir la realidad de la forma más fiel posible a fin de
entender cómo se comporta y poder obtener respuestas a determinadas acciones.
La programación lineal es un tipo de modelo matemático que se desarrolló a partir de la Segunda
Guerra Mundial para resolver cierto tipo de problemas de asignación de recursos entre distintas
actividades. Después de la guerra las aplicaciones de la programación lineal se extendieron a una
amplia variedad de problemas, de manera que hoy se utiliza en campos como la ingeniería, la
economía, la gestión, y muchas otras áreas de la ciencia, la técnica y la industria.
La programación lineal fue formulada por George B. Dantzig alrededor de 1947,
El término programación lineal fue acuñado por el economista y matemático T.C. Koopmans en el
verano de 1948 cuando colaboraba con el propio Dantzig. En 1949, Dantzig publicó el método del
simplex para resolver programas lineales, método que fue ampliamente aceptado por su capacidad
de producir soluciones en un tiempo razonable.
La programación lineal estudia la optimización (minimización o maximización) de una función lineal
que satisface un conjunto de restricciones lineales de igualdad y/o desigualdad.
FORMULACION DE UN MODELO DE
PROGRAMACION LINEAL
En el proceso de formulación de un modelo de programación lineal hay que dar
los siguientes pasos:
Primer Paso
Identificación de las variables Tercer Paso
Segundo Paso
de decisión Formulación de la función
Determinación de las
Representan los elementos del objetivo.
Restricciones.
sistema a modelar que son Se trata de la función que mide la
Representan las limitaciones
controlables por el decisor. En calidad de la solución y que hay
prácticas de determinados
los modelos lineales continuos que optimizar
recursos o imposiciones físicas
estas variables toman como • Maximizar un beneficio o
de la realidad. Se expresan
valores números reales y se • Minimizar un coste)
como ecuaciones e
representan por letras con También es una función lineal de
inecuaciones lineales de las
subíndices como se acostumbra todas o parte de las variables de
variables de decisión.
a hacer con las variables decisión.
Matemáticamente adoptan
matemáticas, o literales
una de las siguientes formas:
alusivos a su significado: peso,
valor, etc.
EJEMPLO DE PROGRAMACION LINEAL
En una fábrica de cerveza se producen tres tipos distintos de cerveza: Rubia,
Negra y de Malta, y para ello se utilizan dos materias primas: malta y levadura. En
la siguiente tabla se especifican:
Materia Prima Rubia Negra Malta Disponibilidad
Malta 1 2 2 30
Levadura 2 1 2 45
Precio de 14 Bs. 10 Bs. 7 Bs.
venta
a) La cantidad de materias primas consumidas para producir una unidad de cada
tipo de cerveza.
b) Las cantidades disponibles de cada materia prima.
c) El precio unitario de venta de cada tipo de cerveza.
Se trata de conocer la cantidad a fabricar de cada tipo de cerveza de manera
que se obtenga el Máximo beneficio.
Identificar los pasos a seguir en el proceso de
formulación de un modelo de programación lineal
Primer Paso: Identificación de las variables de decisión
Del enunciado del problema se desprende que las variables de decisión son las
incógnitas que presentan o que se desconoce, que vendrían a ser la cantidad de
producir en la fabrica de cada tipo de cerveza:
x1 = Cantidad de producción de cerveza rubia
x2= Cantidad de producción de cerveza negra
x3 = Cantidad de producción de cerveza de Malta
Identificar los pasos a seguir en el proceso de
formulación de un modelo de programación lineal
Segundo Paso : Determinación de las Restricciones.
Las restricciones en este caso se identifican como las limitaciones que encontramos en la formulación del problema
que son las materias primas utilizadas en la fabricación de los tres tipos de cerveza los cuales no deben sobrepasar
las cantidades disponibles:
Materia Prima Rubia Negra Malta Disponibilidad
Restricciones (x1) (x2) (x3) (Limitaciones)
Malta (Restricción 1) 1 2 2 30
Levadura (Restricción 2) 2 1 2 45
Cada restricción se convierte en una ecuación de nuestro Modelo Matemático
Siendo un Modelo Matemático un conjunto de Restricciones
mas su función Objetivo
x1 + 2x2 + 2x3 ≤ 30
2x1 + x2 + 2x3 ≤ 45
Identificar los pasos a seguir en el proceso de
formulación de un modelo de programación lineal
Tercer Paso: Formulación de la función objetivo.
En este caso el objetivo es maximizar el beneficio, que viene dado por la suma de los precios de venta
Función Objetivo Rubia de la producción:Negra Malta
(x1) (x2) (x3)
Precio de venta 14 Bs. 10 Bs. 7 Bs.
Primero recordamos que en el enunciado nos decía:
Se trata de conocer la cantidad a fabricar de cada tipo de cerveza de manera
que se obtenga el Máximo beneficio.
Maximizar z = 14 x1 + 10 x2 + 7 x3
Identificar los pasos a seguir en el proceso de
formulación de un modelo de programación lineal
Siendo un Modelo Matemático un conjunto de Restricciones mas su función Objetivo
Maximizar z = 14 x1 + 10 x2 + 7 x3 FUNCION OBJETIVO
x1 + 2x2 + 2x3 ≤ 30 RESTRICCIONES DIRECTAS
Puesto que salieron del enunciado
2x1 + x2 + 2x3 ≤ 45
RESTRICCIONES INDIRECTAS
x1 , x2 , x3 ≥ 0 Puesto que no esta establecida en el
enunciado pero se la evalúa en función de las
variables de decisión que se identifico en un
inicio