INTRODUCCIÓN A LA PROGRAMACION LINEAL

CONTENIDO

 Introducción a la Programación Lineal

 Applicaciones de la Programación Lineal

Referencia: Cap 1 del libro BJS.

1
 Un Problema de Programación Lineal Tipico
Formulación de Programacion Lineal:

Minimizar c1x1 + c2x2 + c3x3 + …. + cnxn

Sujeto a
a11x1 + a12x2 + a13x3 + …. + a1nxn  b1
a21x1 + a22x2 + a23x3 + …. + a2nxn  b2
:
:
am1x1 + am2x2 + am3x3 + …. + amnxn  bm

x1, x2, x3 , …., xn  0

o,
Minimizar  j=1, n cjxj
Sujeto a
 j=1, n aijxj - xn+i = bi for all i = 1, …, m

xj  0 for all j =1, …, n

2
 Notación Matricial

Minimizar cx

Sujeto a

Ax = b
x0

donde
c1 x1

a11 a12 ….. a1n 1 b1 c2 x2

b2 : :
a21 a22 ….. a2n 1
: :
c= cn x= xn
A= : : : : b= :
:
: : : : 0 Xn+1
bm
am1 am2 amn 1
: :
: :
0 Xn+m

3
 1.5 Planificación de la producción. (Sixto Insua)
Una empresa produce filtros para monitores de computador formados por tres
capas, una intermedia de calidad A y otras dos exteriores de calidad B que
envuelven a la anterior.
Ambas calidades se consiguen con diferentes mezclas de fibra de vidrio y resina
de las que el fabricante dispone por semana de 700 y 900 t, respectivamente.
La empresa posee cuatro plantas de producción que utilizan procedimientos de
fabricación que difieren en las cantidades de materia prima que utilizan.
Las cantidades necesarias de materia prima por operación para cada planta que
se pueden llevar a cabo total o parcialmente, así como el número de capas
producidas de uno y otro tipo, se tienen en la tabla

Planta Ton requeridas Capas producidas por

por Operación operación
Vidrio Resina Tipo A Tipo B
1 15 19 2 5
2 14 20 3 7
3 16 15 5 4
4 12 18 4 4

Formular un modelo de programación lineal para determinar el número de

operaciones a realizar en cada planta de manera que sea máximo el número total
de filtros fabricados.

4
 1.10. ·Planificación de la fabricación y gestión de alimentos
(Sixto Insua).
Una empresa de alimentación produce cuatro productos
denominados panchos, congós, roscas y tunos. Las necesidades de
materia prima, tasas de producción, volúmenes y beneficios vienen
dados en la tabla
La cantidad de materia prima disponible para los cuatro productos
es de 60000 dag (decagramos), el volumen de almacenamiento es de
42 m3 y el tiempo de producción disponible es de 16 horas por día.

Un estudio de mercado establece unos límites superiores e

inferiores para la demanda, que se presentan en la tabla, donde la
raya significa que la consultora no ha sido capaz de proponer unas
demandas máximas y/o mínimas

Necesidades Panchos Congós Roscas Tunos

Materia prima (dag/u) 4 3 5 6
Tasas Produc. (u/minuto) 80 90 70 50
Volumen (cm3/ u) 100 200 100 200
Beneficio/pieza (ptas/v.) 70 93 85 110

5
 1.10. ·Planificación de la fabricación y gestión de alimentos
(Sixto Insua).

  Demanda
Mínima Máxima

Panchos 3000 500

Congas 2700 -
Roscas 3900 6400
Tunos - 4700

Se pide:
 
a)Formular un modelo de programación lineal que haga máximo el
beneficio si se admite la producción parcial de los productos.

b) Si la compañía se siente satisfecha con que el beneficio esté por

encima de 400000 ptas., formular un modelo en el que el objetivo sea
la utilización de la menor cantidad de materia prima posible.

c) Discutir el problema si se desea optimizar beneficio y materia

prima simultáneamente.

6
 Fondo de jubilación de empleados (Davis p.85)

 El comité financiero le ha pedido al Señor Pedro Pérez analista

financiero que prepare recomendaciones de inversión para $2
millones del fondo de jubilación.
 El comité ha sugerido diversificar las inversiones entre:
certificados de depósito, bonos de la tesorería, acciones con
buen historial, acciones especulativas, bonos de compañías y
bienes raíces.
 El señor Pérez ha estimado un rendimiento anual para cada
clase de inversión y así mismo, ha desarrollado un factor de
riesgo para cada una de ellas, que señala la probabilidad de que
el rendimiento real de las inversiones en esa clase sea inferior
al rendimiento esperado.
 Por último, ha elaborado un pronóstico del número promedio de
años en que se espera obtener el rendimiento esperado para la
clase respectiva de inversión ( Ver tabla.)

7
 Fondo de jubilación de empleados (Davis p.85 cont.)

Clase de inversión Rendimiento Factor de Plazo promedio de

esperado anual (%) riesgo la inversión
Certificados de depósito 8.5 0.02 8
Bonos de la tesorería 9.0 0.01 2
Acciones con buen historial 8.5 0.38 5
Acciones especulativas 14.3 0.45 6
Bonos de compañías 6.7 0.07 2
Bienes Raíces 13.0 0.35 4

 El comité ha indicado que le gustaría tener un promedio

ponderado de inversión de cuando menos cinco años.
 El comité ha señalado que el factor promedio ponderado de
riesgo no debe ser superior a 0.20.
 La ley prohíbe que se inviertan más del 25% de las
inversiones estatales en bienes raíces y acciones especulativas.
 Que recomendación debe hacer el Señor Pérez s i se pretende
maximizar el rendimiento.

8
 Periodos múltiples – Compañía Odessa (Davis p 105)

 La compañía Odessa fabrica un producto que tiene demanda que

aumenta y disminuye. La demanda pronosticada para los próximos
cuatro meses es 1800, 2200, 3400 y 2800, respectivamente.
 Debido a las variaciones en la demanda, los administradores de Odessa
han encontrado que en algunos meses existe producción en exceso, lo
cual ocasiona grandes costos de manejo y almacenamiento; en tanto
que en otros meses la compañía no está en posibilidades de cubrir la
demanda.
 La compañía puede fabricar 2400 artículos por mes en sus turnos
normales.
 Utilizando tiempo extra, es posible fabricar 800 artículos mensuales
adicionales. Debido a los mayores costos de mano de obra en tiempo
extra, se produce un aumento de $7 por cualquier artículo que no se
fabrique durante el turno normal.
 Los administradores han estimado que se incurre en un costo de
almacenamiento de $3 por mes por cualquier artículo.
 Odessa le gustaría determinar un programa optimo de producción que
minimice los costos totales de producción y almacenamiento.
 El programa debe satisfacer todas las demandas.

9
 Múltiples periodos Compañía de inversiones (Davis p108)

 La compañía de inversiones Santander dispone de $ 600.000

para colocarlos en un conjunto de alternativas de inversión

 La inversión tipo 1 esta disponible en cada uno de los

próximos seis años y se espera que produzca un rendimiento de
28% por cada dólar invertido, al momento de su vencimiento al
final de tres años.

 La inversión tipo 2 también está disponible en cada uno de los

próximos seis años. Esta inversión rendirá $1.16 por cada dólar
invertido y vence al final de dos años.

 La inversión tipo 3 está disponible sólo al principio del

segundo año y rinde $ 1.50 al final del cuarto año por cada dólar
invertido.

10
 Múltiples periodos Compañía de inversiones (Davis p108)

 La inversión tipo 4 está disponible en cualquier momento

después del tercer año y produce un rendimiento del 40 % al
final de dos años.

 La oportunidad final de inversión, la tipo 5, está disponible

solo una vez, al principio del año 1. Esta inversión rendiría $
1.45 por cada dólar invertido, pero no vence sino hasta
principios del año 5

 Cuando las inversiones vencen están disponibles para

reinversión. A la compañía le gustaría determinar la cartera de
inversión que maximice el rendimiento de la inversión total para
un periodo de seis años.

11
 Construcción de modelos de P.L. basado en análisis de
actividades
 Este análisis de actividades proporciona una base sistemática
para la construcción de Modelos.

 Sistema conjunto de maquinas, gente, instalaciones, medios de

transporte y suministro de materiales

 Actividades son las funciones o procesos elementales que

constituyen el sistema

 Elementos son las entradas (fuerza de trabajo, $, materia prima,

equipos) o las salidas (productos, ganancias, etc.) de las
actividades

 Nivel de actividad se refiere a la cantidad de una actividad

12
 Pasos en la formulación de modelos por análisis de
actividades
 Paso 1. Definir el conjunto de actividades a nivel unitario y
su unidad de medida

 Paso 2. Definir el conjunto de elementos y su unidad de

medida

 Paso 3. Determinar los coeficientes de entrada salida

 Paso 4. Determinar los flujos externos

 Paso 5. Asignar niveles desconocidos a las actividades y

determinar las ecuaciones de balance..

Actividad a
+ nivel unitario -

Elementos de entrada Elementos de salida

13
 Problema de transporte

Por ejemplo, suponga que una empresa posee dos plantas que elaboran un
determinado producto en cantidades de 250 y 450 unidades diarias,
respectivamente. Dichas unidades deben ser trasladadas a tres centros de
distribución con demandas diarias de 200, 200 y 250 unidades,
respectivamente. Los costos de transporte (en $/unidad) son:

C.Dist. 1 C.Dist.2 C.Dist.3

Planta 1 21 25 15

Planta 2 28 13 19

14
 Problema de Transporte.

Diagrama:
C.D.1
X11

Planta 1
X12

X21 X22 C.D.2

Planta 2

X13
X23
C.D.3

Orígenes Destinos

15
 Problema de Transporte.

Pasos a seguir:

P1. Definir el conjunto de actividades a nivel unitario

1. Transportar una unidad de mercancía de la ith planta al
jth centro de distribución i = 1, 2 y j =1, 2, 3
2.Almacenar una unidad de mercancía en la ith planta

P2. Definir el conjunto de elementos que entran o salen a las actividades

- Mercancía en la ith planta
- Mercancía en el jth centro de distribución
- Costo
P3. Determinar los coeficientes de entrada – salida a las actividades

1 unidad de mercancía
en la planta 1 1 unidad de mercancía
Transportar una unidad en el centro de distribución 1
de mercancía de la planta 1
Costo unitario de al centro de distribución1
transporte (21)

16
 Planeamiento de Producción
 Una empresa de artículos electrónicos produce tres líneas de
productos : transistores, micromódulos y circuitos armados.
 Tiene cuatro áreas de proceso donde se fabrican los
productos: producción de transistores; armaduría de circuitos;
control de transistores y módulos, y prueba de circuitos; y
embalaje.
 La producción de un transistor requiere:
0.1 horas de trabajo en producción de transistores (A1)
0.5 horas de trabajo en control de transistores (A3)
 La producción de un micromódulo requiere:
0.4 horas de trabajo en armaduría de circuitos (A2)
0.5 horas de trabajo en control de transistores y módulos
(A3) y 3 transistores
 La producción de un circuito requiere:
0.1 horas de trabajo de armaduría de circuitos (A2)
0.5 horas de trabajo en control de transistores y
micromódulos (A3)
1.0 horas de trabajo prueba de circuitos (A4), 1 transistor y
micromódulos.

17
 Planeamiento de Producción (cont.)

 Cualquiera de los tres productos, se puede vender en cantidades

ilimitadas a los precios de 2, 8 y 30 respectivamente.

 Hay 200 horas de trabajo disponibles en producción de

transistores y embalaje y 400 en armaduría y control.

 Los costos en materia prima directa son de 0.1; 0.3 y 1 para

transistores, micromódulos y circuitos armados respectivamente

 Los salarios semanales (40 horas) son de 80, 40, 40 y 120 en los
departamentos de producción, armado, control y embalaje
respectivamente

 Se desea determinar las cantidades óptimas a fabricar de cada

producto, de tal forma que se maximice los excedentes.

18
 Asignación de trabajadores

 Un taller ha seleccionado a cuatro trabajadores (A,B,C,D) para

operar cuatro maquinas (1,2,3,4) que se utilizan en la producción
de partes para repuestos automotores. Los trabajadores se
asignan a las maquinas de tal forma que un trabajador se asocie a
cada maquina y una maquina a cada trabajador. Se quiere
maximizar el desempeño total de la asignación de los trabajadores
a las maquinas.
 El cuadro adjunto indica el desempeño individual de cada
trabajador en cada maquina.

trabajador Maquinas
1 2 3 4
A 130 100 120 110
B 100 50 130 20
C 50 70 100 40
D 50 100 150 60

19
 Problema de mezclas

 Un fabricante desea producir una aleación la cual es 30% de

plomo, 30% de Zinc y 40% de estaño
 Suponga que en el mercado existen aleaciones A,B,C,D…..I con
composiciones y precios dados en la tabla.
 Por lb de aleación producida, cuanto de cada tipo de aleación
debe adquirirse en orden a minimizar costos?

Aleación A B C D E F G H I Mezcla deseada

%Pb 10 10 40 60 30 30 30 50 20 30
%Zn 10 30 50 30 30 40 20 40 30 30
%Sn 80 60 10 10 40 30 50 10 50 40
Costo (lb) 4.1 4.3 5.8 6.0 7.6 7.5 7.3 6.9 7.3 Z(min)

20
 Planta de Fundición

 Una planta de fundición produce aleaciones especiales de

acuerdo a las especificaciones de los clientes. Uno de tales
clientes encarga una aleación de 4 metales y especifica la
siguiente composición:
Metal Requisito (% sin impurezas)
A Por lo menos 35%
B No más del 20%
C No más del 5%
D Entre 45 y 65 %

 Se puede utilizar varios minerales del cual extraer los

diferentes metales. Los minerales contienen algo de
impurezas

21
 Planta de Fundición

Metal Mineral
1 2 3 4 5 6
A% 45 15 10 10 10 5
B% 46 0 30 20 25 15
C% 20 25 20 30 25 9
D% 6 15 0 0 10 20
Costo($/ton) 2500 2600 4000 3000 4600 3000

 Cuanto obtener de cada mineral para producir la aleación

requerida ?

22
 Problema de almacenamiento

 Consideremos el problema de almacenar una mercancía

para venta en una fecha posterior.
 La bodega puede almacenar únicamente 100 unidades
 Los costos de almacenamiento son de $1 por periodo y por
unidad.
 En cada periodo el precio de compra es igual al precio de
venta.
 Este precio varía de periodo en periodo según:

Periodo (t) Precio unitario

1 10
2 12
3 8
4 9

23
 Problema de almacenamiento

 Esto implica que un beneficio se puede lograr por comprar

cuando el precio es bajo y vender cuando el precio es alto.
 El problema es determinar el programa optimo de compra,
venta y almacenamiento para un periodo de 1 año en
trimestres.

24
 Granja

 Suponga que 1 gallina gasta 3 semanas en poner 15

huevos para la venta o empollar 8. Cuál es el mejor
programa de postura y cría si al final de un cuarto periodo
todas las gallinas y pollos acumulados durante esos 4
periodos se venden a $150 c/u y los huevos a $ 2.
 Asuma
a) Un inventario inicial de 100 gallinas y 100 huevos
b) Un inventario inicial de 100 gallinas y cero huevos
c) Un inventario inicial de 100 gallinas y cero huevos y un
inventario final de 100 gallinas y cero huevos.

Formular el modelo para cada caso

25
 Capacitación de trabajadores
 Una planta manufacturera tiene un contrato para producir 1200 unidades de mercancía, según el plan de entregas así:

 Que programa de contratación, producción, despido y almacenamiento debe adoptar el fabricante en orden a minimizar los costos de su contrato regido por las siguientes condiciones:

Fin de semana 1 2 3 4 5

Nro. de unidades 100 200 300 400 200

26
 Capacitación de trabajadores

a) Cada unidad de producción no entregada según la

programación involucra una penalización de $p por
semana hasta que se realice la entrega.
b) Cualquier producción en avance requiere almacenamiento
a un costo de $S.
c) Todos los compromisos deben satisfacerse al final de la 5ª
semana
d) Inicialmente hay g (=20) trabajadores y h = 10 unidades de
mercancía.
e) Cada trabajador utilizado en producción durante una
semana puede entregar k unidades de mercancía
f) Cada trabajador utilizado para capacitar nuevos
trabajadores puede entrenar L – 1 trabajadores.
g) Los salarios de un trabajador son $m por semana bien sea
que este en producción o este libre.
h) El costo del programa de capacitar L-1 trabajadores en una
semana es de $n.
i) El costo de despedir un trabajador es de $f.

27
 Que debe conocer de la Programación Lineal

 Cuales son las componentes de un problema

 Como formular un problema
 Que suposiciones se encuentran en un PL
 Como encontrar una solución gráficamente a un problema
bi-dimensional
 Soluciones Posibles
 Como resolver un problema con las incorporaciones en
Excel (Solver)

28

28