Programación Lineal

Ing. MGI. Estuardo Godinez

Programación Lineal
► Programación Lineal es una técnica matemática
de optimización en donde las relaciones entre
variables son lineales y donde hay un solo
objetivo o medida de rendimiento.
► Esta técnica brinda la ventaja de que determina
la mejor decisión (óptima), sin importar la
cantidad de variables y relaciones existentes.
► En términos generales, ésta consiste en la
planificación de actividades que incluye la
aplicación de modelos matemáticos con
funciones lineales, con el propósito de obtener
un resultado óptimo.
► Los principales métodos de programación lineal,
son: el método gráfico, el método simplex y el
método de transporte o distribución. Cada uno
de los cuales tiene un tipo de aplicación
específico
Programación Lineal
► Formulación de Modelos
► La formulación de modelos consiste en el
proceso de definir las variables, ecuaciones
e inecuaciones que en términos generales
representan un problema empresarial.
► Durante este proceso deben seleccionarse
los elementos importantes del problema y
definir la forma en que éstos se relacionan
entre sí. Más que un procedimiento, consiste
en un arte debido a que en el caso de
problemas reales, la tarea resulta difícil y
requiere de pruebas, experiencia y juicio
común.
► Sin embargo, algunos consejos para la
formulación de modelos, son los siguientes:
Programación Lineal
► Formulación de Modelos
► 1. Defina claramente el objetivo que
pretende alcanzar, identificando únicamente
un objetivo. Generalmente estará
relacionado con "aumentar beneficios" o
"reducir costos".
► 2. Defina claramente las variables de
decisión. Es importante que incluya dentro
de su lista de variables, las especificaciones
de unidades de medida para cada una de
ellas.
► 3. Elabore una lista de los factores
restrictivos que afectan su objetivo y sus
probables decisiones. Algunos tipos de
restricciones son los siguientes:
Programación Lineal
► Formulación de Modelos
► · Restricciones de capacidad que se deben a la
cantidad de equipo, de tiempo, de espacio o de
mano de obra disponible.
► · Restricciones de mercado, identificados como
límites de la cantidad de producto que puede
venderse o usarse.
► · Restricciones de disponibilidad ocasionados por
la escasez de materias primas, fuerza de
trabajo, financiamiento u otros recursos.
► · Restricciones de calidad o de mezcla que
limitan la mezcla de ingredientes y que por lo
general definen la calidad de los productos
resultantes.
► · Restricciones de tecnología de producción o de
equilibrio de materiales que definen la salida de
un proceso como una función de las entradas,
muchas veces con una pérdida por desperdicios.
Programación Lineal
► Formulación de Modelos
► 4. Defina las restricciones con base a las
variables de decisión y a los factores
restrictivos establecidos. Al finalizar este
paso, usted tendrá un conjunto de
restricciones.
► 5. Defina su función objetivo como una
ecuación y revise que ésta, así como sus
restricciones y variables de decisión estén
planteadas únicamente en términos de
costos o beneficios que varíen con las
decisiones, es decir, que debe excluir los
costos fijos de la función objetivo.
► A continuación, se presentan algunos
ejemplos de formulación de modelos en
programación lineal.
Programación Lineal
► Ejemplo 1
► Cierta compañía utiliza dos distintas
máquinas para fabricar dos productos
diferentes identificados como A y B. La
fabricación del producto A, requiere utilizar
la máquina "X" media hora y la máquina "Y"
una hora. Mientras que el producto B, utiliza
cada máquina dos horas. Por
especificaciones técnicas, la máquina "X" no
debe operar más de ocho horas al día y la
máquina "Y", no debe operar más de doce
horas diarias. Las ganancias unitarias de los
productos A y B son de Q.20.00 y Q.50.00,
respectivamente. La empresa puede vender
todas las unidades que puede fabricar de los
dos productos y su objetivo consiste en
maximizar su ganancia diaria.
Programación Lineal
► Ejemplo 1
► 1. Objetivo: Maximizar la ganancia diaria.
► 2. Variables de decisión:
► La cantidad de unidades de los productos A y B
que deben producirse dentro de los límites de
capacidad. Por lo tanto,
► X1 = Número de unidades del producto A que se
fabricarán diariamente.
► X2 = Número de unidades del producto B que se
fabricarán diariamente.
► 3. Factores restrictivos: Horas disponibles al día
en máquinas "X" y "Y".
► 4. Restricciones: La primera restricción se
refiere a la disponibilidad de tiempo en la
primera máquina, la cual puede expresarse de
la siguiente manera
Programación Lineal
► 0.5x1 + 2x2 ≤ 8
► Cada unidad de A, utiliza media hora de esta
máquina, y cada unidad de B utiliza dos
horas esta misma máquina. Por lo tanto, el
total de horas utilizadas en la máquina "X",
se expresa mediante la suma total de
tiempos utilizados por ambos productos y
debe ser igual o menor al total de horas
disponibles en el día, que para este caso,
corresponde a ocho horas.
► La segunda restricción se refiere a la
disponibilidad de tiempo en la segunda
máquina, la cual puede expresarse de la
siguiente manera: 1x1 + 2x2 ≤ 12
Programación Lineal
► Cada unidad de A, utiliza una hora de esta
máquina, y cada unidad de B utiliza dos
horas esta misma máquina. Por lo tanto, el
total de horas utilizadas en la máquina "Y",
se expresa mediante la suma total de
tiempos utilizados por ambos productos y
debe ser igual o menor al total de horas
disponibles en el día, que para este caso,
corresponde a doce horas.
► A todo conjunto de restricciones en
programación lineal, se le debe especificar
la restricción de no negatividad de las
variables de decisión; es decir, que la
empresa sólo puede producir cantidades
positivas o cero. Para este caso, esta
restricción debe plantearse así: X1, X2 ≥ 0
Programación Lineal
► Función Objetivo: La función objetivo vista
como una ecuación lineal, en términos de su
ganancia diaria, queda así:
► Xo = 20X1 + 50X2
► Esta ecuación establece que la ganancia
total de la compañía se forma con el total
de ganancia que genera el producto A (al
multiplicar su ganancia unitaria por el total
de unidades a fabricar "X1") más el total de
ganancia que genera el producto B (al
multiplicar su ganancia unitaria por el total
de unidades a fabricar de "X2")
Programación Lineal
► La formulación final del problema, queda de
la siguiente manera:
► Maximizar: Xo = 20X1 + 50X2
► Sujeta a:
► 0.5X1 + 2X2 ≤ 8
► 1X1 + 2X2 ≤ 12
► X1, X2 ≥ 0
► Este problema, resulta sencillo y no requiere
de programación lineal para resolverlo. Sin
embargo, en la práctica suelen presentarse
problemas que implican docenas de
productos y variedad de restricciones que no
pueden resolverse en forma intuitiva y en
donde la programación lineal, ha resultado
una herramienta sumamente eficaz.
 Programación Lineal
► Ejemplo 1: Que datos que nos están dando?
► 1. Cuantos productos se desean hacer?
► Se desean fabricar dos productos (Identificados
como A y B.
► 2. Cuanto tiempo tienen de utilizan para crear cada
producto?
► Para realizar producto A necesita trabajar en una
maquina X Media Hora en una maquina Y una hora,
para hacer B necesitan 2 horas en Maquina X y 2
horas en Maquina Y
► 3. Existe alguna limitante
► Si, la maquina X no se puede usar mas de 8 horas al
día y la Y no se puede usar mas de 12 horas.
► 4. Cuanto Ganan al vender cada producto?
► 20.00 quetzales x vender un A y 50.00 por vender un
producto B.
► 5. La empresa comprando o Vendiendo y cual es su
objetivo?
► Vendiendo y el objetivo es Maximizar.
Programación Lineal
A B Maximo
X 0.5 2 8
Y 1 2 12
Ganancias 20 50
x1 x2
0.5x1 + 2x2 ≤ 8
1x1 +2x2 ≤ 12
Xo = 20x1 + 50 x2
Programación Lineal

► https://www.youtube.com/watch?v=LJt0Pp-c9EQ 19 minutos introducción a

programación lineal y un problema

► PARTE2 FORMULACIÓN DE MODELOS DE PROGRAMACIÓN LINEAL – YouTube

maximización 19.14 minutos muy bueno

► EJEMPLO2 DE FORMULACIÓN DE MODELO DE PL – YouTube 25 minutos

minimización muy bueno
Programación Lineal
► Ejemplo 2 (Decisiones sobre mezclas y
producción)
► Una compañía productora de nueces vende
dos mezclas diferentes en época navideña.
La primera mezcla está destinada a un
mercado de clientes de clase media, la cual
contiene un 80% de cacahuates y un 20% de
nueces. La segunda mezcla está elaborada
para un selecto grupo de clientes quienes
pagarán más por una mezcla que contiene
50% de cacahuates y 50% de nueces.
Semanalmente la compañía adquiere 1800
kilos de cacahuates y 1200 kilos de nueces.
Las ganancias unitarias son de Q.10.00 por
cada kilo de la mezcla barata y de Q.15.00
por cada kilo de mezcla más cara. ¿Cuántos
kilos de cada mezcla deberá de producir la
compañía, si desea maximizar su utilidad?.
Programación Lineal
► Formulación: ► Cada kilo de la mezcla I utiliza 80%
► 1. Objetivo: Maximizar la utilidad semanal. de cacahuates y cada kilo de la
mezcla II, utiliza 50% de cacahuates.
► 2. Variables de decisión: La cantidad de
kilos de las mezclas I y II que deben ► Por lo tanto, el total de kilos de
producirse dentro de los límites de cacahuate utilizados en la producción
capacidad. Por lo tanto, semanal de las mezclas I y II, se
► X1 = Cantidad de kilos de la mezcla I que se expresa mediante la suma total de
producirán semanalmente. kilos utilizados en cada mezcla y
► X2 = Cantidad de kilos de la mezcla II que se debe ser igual o menor al total de
producirán semanalmente. kilos disponibles en una semana, que
► 3. Factores restrictivos: Cantidad de kilos
para este caso, corresponde a 1800
de cacahuates y nueces suministrados kilos.
semanalmente. ► La segunda restricción se refiere a la
► 4. Restricciones: La primera restricción se disponibilidad de nueces
refiere a la disponibilidad de cacahuates suministrados semanalmente, la cual
suministrados semanalmente, utilizados en puede expresarse de la siguiente
la elaboración de mezclas I y II:
manera: 0.20X1 + 0.50X2 ≤ 1200
► 0.80X1 + 0.50X2 ≤ 1800
Programación Lineal
► Formulación: ► Xo = 10X1 + 15X2
► Cada kilo de la mezcla I utiliza 20% de ► Esta ecuación establece que la ganancia
nueces y cada kilo de la mezcla II, total de la compañía se forma con el
utiliza 50% de nueces. Por lo tanto, el total de ganancia que genera la mezcla I
total de kilos de nueces utilizados en la (al multiplicar su ganancia unitaria por
producción semanal de las mezclas I y II, el total de kilos a producir de "X1") más
se expresa mediante la suma total de el total de ganancia que genera la
kilos utilizados en cada mezcla y debe mezcla II (al multiplicar su ganancia
unitaria por el total de kilos a producir
ser igual o menor al total de kilos de "X2").
disponibles en una semana, que para
este caso, corresponde a 1200 kilos. ► La formulación final del problema,
queda de la siguiente manera:
► La restricción de no negatividad:
Maximizar: Xo = 10X1 + 15X2
► X1, X2 ≥ 0 ► Sujeta a:
► 5. Función Objetivo: 0.80X1 + 0.50X2 ≤ 1800
► La función objetivo vista como una 0.20X1 + 0.50X2 ≤ 1200
ecuación lineal, en términos de su
ganancia diaria, queda así: X1, X2 ≥ 0
 Programación Lineal
► Ejemplo 2: Que datos que nos están dando?
► 1. Cuantos productos se desean hacer?
► Se desean fabricar dos productos (Mezclas 1 y
Mezclas 2
► 2. Cuanto producto tienes para crear cada
mezcla?
► Para realizar la mezcla 1 tienes 80 % de
cacahuate y 20% de nueces y para hacer la
mezcla 2 tienes 50 % de nueces y 50 % de
cacahuate.
► 3. Existe alguna limitante
► Si, de cacahuate hay 1800 kilos y de nueces
1200 kilos.
► 4. Cuanto Ganan al vender cada mezcla?
► 10.00 quetzales x vender un mezcla 1 y 15.00
por vender mezcla 2.
► 5. La empresa comprando o Vendiendo y cual es
su objetivo?
► Vendiendo y el objetivo es Maximizar.
Programación Lineal

x1 x2

mezcla 1 mezcla 2 disponibilidad

cacahuates 0.8 0.5≤ 1800
nueces 0.2 0.5≤ 1200
Ganancia 10 15

Xo = 10x1 + 15 x2

08x1+ 0.5x2 ≤ 1800

0.2x1 +0.5x2 ≤ 1200

x1, x2 ≥ 0
Programación Lineal
► Ejemplo 3 (Decisiones sobre planeación
dietetica)
► La dietista de una prestigiosa clínica de
reducción de peso, debe encontrar la
combinación más barata de dos productos
alimenticios A y B que contienen al menos
0.5 miligramos de tiamina y al menos 600
calorías. Los estudios indican que cada onza
de A contiene 0.12 miligramos de tiamina y
100 calorías; mientras que cada onza de B
contiene 0.08 miligramos de tiamina y 150
calorías. Si el costo de cada alimento es de
Q.10.00 por onza, ¿cuántas onzas de cada
alimento deberán combinarse de tal manera
que se cumplan los requerimientos
dietéticos y el costo de alimentación sea
mínimo?.
Programación Lineal
► Formulación: ► 0.12X1 + 0.08X2 ≥ 0.50
► 1. Objetivo: Minimizar el costo de ► Cada onza del producto A contiene 0.12
alimentación por paciente. miligramos de tiamina y cada onza del
producto B contiene 0.08 miligramos de
► 2. Variables de decisión: La cantidad de tiamina. Por lo tanto, la suma total de
onzas de cada producto alimenticio A y tiamina de ambos productos debe ser igual
B que deberán combinarse. o mayor al requerimiento dietético mínimo
de tiamina que corresponde a 0.50.
► Por lo tanto, X1 = Cantidad de onzas del
producto A. X2 = Cantidad de onzas del ► La segunda restricción se refiere al
producto B. requerimiento mínimo de calorías que
deberá cubrir la combinación de productos:
► 3. Factores restrictivos: Requerimientos
► 100X1 + 150X2 ≥ 600
mínimos de tiamina y calorías.
► Cada onza del producto A contiene 100
► 4. Restricciones: La primera restricción calorías y cada onza del producto B
se refiere al requerimiento mínimo de contiene 150 calorías. Por lo tanto, la suma
tiamina que deberá cubrir la total de calorías de ambos productos debe
combinación de productos: ser igual o mayor al requerimiento dietético
mínimo de calorías que corresponde a 600.
► La restricción de no negatividad: X1, X2 ≥ 0
Programación Lineal
► Formulación: ► Minimizar:

► 5. Función Objetivo: ► Xo = 10X1 + 10X2

► La función objetivo vista como una ► Sujeta a:

ecuación lineal, en términos del ► 0.12X1 + 0.08X2 ≥ 0.5
costo de alimentación, queda así:
► 100X1 + 150X2 ≥ 600
► Xo = 10X1 + 10X2
► X1, X2 ≥ 0
► Esta ecuación establece que cada
onza del producto A y B tiene un
costo de Q.10.00.
 Programación Lineal
► Ejemplo 3: Que datos que nos están dando?
► 1. Combinación mas barata de productos que se
desean hacer?
► Se desean fabricar dos productos A y B
► 2. Que materia prima tiene para realizar los
productos
► Para cada onza del producto a contiene .12
miligramos de tiamina y 100 calorías y cada onza del
producto b contiene 0.08 miligramos de tiaminas y
150 calorías .
► 3. Existe alguna limitante
► Si al menos 0.5 miligramos de tiamina y 600
calorías
► 4. Cuanto es el costo de cada producto ?
► 10.00 quetzales x onza de cada uno
► 5. La empresa es una dietista de reducción de peso
que cumpla con los requerimientos dietéticos y el
costo sea el mínimo.
► Debe tener una mínima cantidad al mínimo costo.
Programación Lineal

A B minimo

Tiamina 0.12 ≥
0.08 0.5

Calorias 100 150≥ 600

Costo 10 10

Xo = 10 x1 + 10x2

0.12x1 +0.08 x2 ≥ 0.5

100x1+ 150 x2 ≥ 600
x1,x2 ≥ 0