6.

PROGRAMACION LINEAL

La programación lineal se ha usado para resolver problemas de optimización en industrias

tan diversas como la banca, la educación, la silvicultura, el petróleo y el transporte. En una
encuesta de la revista Fortune, de 500 empresas, el 85% de las que contestaron dijeron que
habían utilizado la programación lineal.

6.1. QUE ES UN PROBLEMA DE PROGRAMACION LINEAL

Un problema de programación lineal es un problema de optimización, para el cual:

1. Tratamos de maximizar o minimizar una función lineal de variables de decisión. La

función que se pretende maximizar o minimizar se llama función objetivo

2. Los valores de las variables de decisión tienen que satisfacer un conjunto de

restricciones. Cada restricción tiene que ser una ecuación lineal o una desigualdad lineal.

3. Hay una restricción de signo para cada variable. Para cualquier variable X, la restricción
de signo especifica que X tiene que ser no negativo (X ¿ 0) o que X puede ser una
variable sin restricción de signo.

6.2. CARACTERISTICAS DE LOS PROBLEMAS DE

PROGRAMACION LINEAL

 Un solo objetivo. Este requerimiento indica que no necesitamos ocuparnos de más de un

objetivo a la vez. Esta consideración es razonable para un modelo de planeación a corto
plazo en el que se esté trabajando.

 Restricciones. La optimización de un objetivo sea en su efecto maximizar o minimizar,

esta sujeto a restricciones, la disponibilidad de recursos escasos limita por ejemplo una
producción a niveles que pueden alcanzarse con los recursos disponibles. Si no existiera
esta restricción sería posible fabricar una cantidad ilimitada de productos, lo cual por
supuesto es totalmente irreal. Estas limitaciones de los niveles de producción las
denominamos Restricciones.

 Proporcionalidad. La función objetivo y las restricciones deben ser proporcionales por

ejemplo al nivel de fabricación de diversos productos. Esta restricción de linealidad separa
este modelo de otros que buscan maximizar una función objetivo sujeta a un conjunto de
restricciones.
 Divisibilidad. La característica de divisibilidad significa que son posibles asignaciones
fraccionarias de productos. Esta es una consideración importante en los casos en que sé

trabaja con la producción o asignación de artículos discretos, dado que no es posible

garantizar que las soluciones de programación lineal sean enteras.

 Aditividad. Significa que el total es igual a la suma de las partes y que no hay efectos
de interacción entre los niveles de producción.

 No negatividad. Esta es la consideración más fácil de comprender, porque no

esperaríamos por ejemplo fabricar menos de cero unidades de un producto.

Además de estos requerimientos, por lo general también se considera que todos los
parámetros se conocen con certidumbre, es decir que las utilidades, la disponibilidad de
recursos escasos y las relaciones entre los niveles de producción y los usos de recursos no
están sujetas a ninguna incertidumbre.

La forma general del problema de programación lineal es la siguiente:

n
Optimizar Z =∑ C j X j
j =0

n
∑ aij X j ( ¿;=:≤ ) bi
Sujeto a: j=0

∀ j=1,...,n
X j≥0 ∀i=1,...,m

Se tiene que,
Cj , b i y
aij , son constantes y se determinan dependiendo de la
tecnología del problema y
X j son las variables de decisión.

En sentido real, las constantes y variables anteriores pueden interpretarse así: dadas n
actividades, las variables
X 1 , X 2 ,......., X n de decisión representan los niveles a que se
llevan a cabo las actividades. Z expresa la medida de efectividad escogida. Las j C
expresan el aumento en la medida de efectividad resultante de un aumento de una unidad de
X j . Además, bi representa la cantidad de recurso i disponible para usar en las n
actividades y
aij denota la cantidad del insumo o recurso i del que hace uso la
actividad j . Por lo tanto, el lado derecho de las restricciones significa el uso total de los
respectivos recursos.
Como se mencionó antes, las últimas restricciones sobre los signos de valores de las
variables evitan la posibilidad de que existan niveles de actividad negativos.

La forma general del modelo de programación lineal, también se podría expresar por:

Optimizar
Z =C1 X 1 +C 2 X 2 +. .. . ..+C n X n

Sujeto a: a11 X 1 +a12 X 2 +. . .. .. .+a1 n X n ( ¿;=;≤ ) b1

a21 X 1 +a22 X 2 +.. . .. ..+a2 n X n ( ¿;=;≤ ) b 2

. . . . .
. . . . .
. . . . .
am 1 X 1 +a m2 X 2 +. .. . .. ..+amn X n ( ¿ ;=;≤ ) bm

X 1 ≥0 , X 2 ≥0 , .. . .. .. . ., X n≥0

El término optimizar se refiere a Maximizar o Minimizar

6.3. PASOS PARA RESOLVER UN PROBLEMA DE

PROGRAMACION LINEAL

1. Reformular el problema. Es decir lo que nos pide el problema en forma más simple y
clara. Debe involucrar lo que va a optimizar, los recursos y las incógnitas o variables que
quiere determinar.

2. Definir el objetivo. Determinar que es lo que vamos a maximizar o minimizar. El

objetivo que debe lograrse esta sujeto a disponibilidad y uso de recursos escasos: como
económico, redistribución del ingreso o no económicos.

3. Definir las variables de decisión. En cualquier problema de programación lineal, las

variables de decisión deben de representar completamente las decisiones que se van a
tomar, me expresan que es lo que se quiere determinar.

4. Definir las limitaciones. Expresar con palabras las restricciones o limitaciones. Por
ejemplo: No se cuenta con más de $ 10 000.000 para llevar a cabo una producción
determinada.

5. y 6. Relaciones y Modelo. En cualquier problema de programación lineal, la persona

que toma la decisión debe maximizar (por lo general el ingreso o las ganancias) o
minimizar (por lo general los costos) alguna función de las variables de decisión. La
función que hay que maximizar o minimizar la llamamos función objetivo. Los coeficientes
de las variables de la función objetivo se denominan coeficientes de la función objetivo. El
modelo es la representación matemática de lo que queremos optimizar, ya sea en su efecto
maximizar o minimizar, y consiste en combinar las variables de decisión que se definieron
antes y las relaciones físicas inherentes al problema. Estas relaciones físicas varían de un
problema a otro y es necesario tener cuidado de asegurar que el modelo matemático
represente en forma precisa estas relaciones.

En el modelo se incluyen todas las restricciones (restricciones explícitas). Para que una
restricción sea razonable, todos los términos tienen que tener las mismas unidades. Las
restricciones se escriben dependiendo de los datos que nos proporcione el problema, pero
una
restricción general es la restricción de signo o de no negatividad (restricción implícita).

Para completar la formulación de un problema debemos preguntarnos ¿ Puede la variable

de decisión tomar valores negativos?. Como en los problemas de programación lineal
tratamos de optimizar, tiempo, costos, ingresos, las variables de decisión no pueden tomar
valores negativos, porque o si no el problema sería inconsistente.

7. Supuestos. Hace referencia a los condicionamientos bajo los cuales el modelo es

aplicable.

6.3.1. MODELOS

CASO 1.

La cía. “ Acero Derretido “ debe decidir cuántas lbs. de acero y cuántas de chatarra utilizar
en la preparación de una aleación para un cliente. El costo por lb. de acero es de $ 30 y el
de la chatarra $ 60. La demanda del cliente es de por lo menos 50 lbs. y él aceptaría más si
así se requiere. La disponibilidad de acero es de 40 lbs. y la de chatarra 70 lbs.. La relación
entre chatarra y acero puro no puede exceder de 7/8. La fábrica tiene 180 horas disponibles
para derretir y fundir. Una lb. de acero puro requiere 3 horas, mientras que la chatarra sólo
2 horas.

SOLUCIÓN:

1. Reformulación del problema

Determinar cuántas lbs. de acero puro y cuántas de chatarra se deben utilizar en la

preparación de una aleación para un cliente, con el fin de minimizar costos, de tal manera
que se cumplan con todos los requerimientos según la tabla # 1
TABLA DE REQUERIMIENTOS

Costo Disponibilidad Tiempo requerido

Materiales Derretir – Fundir
( $/lb ) ( lbs ) ( Horas/lb )
Acero puro 30 40 3

Chatarra 60 70 2

TABLA # 1

2. Objetivo

Minimizar costos

3. Variables de decisión

X i : Cantidad en lbs. de cada componente i a utilizar en la preparación de la aleación,

donde i = 1,2 (1 = acero; 2 = chatarra)

4. Limitaciones

- El tiempo total disponible para derretir y fundir debe ser máximo de 180 lbs.
- La demanda del cliente es de por lo menos 50 lbs.
- La disponibilidad total de chatarra es de 70 lbs.
- La relación entre chatarra y acero no puede exceder a 7/8

6. Relaciones

Función objetivo: Z =30 X 1 +60 X 2

Restricciones: 3 X 1 +2 X 2 ≤180
X1 + X 2≥ 50
X1 ¿ 40
X 2≤ 70
X2 7
≤
X1 8
7. Modelo
MIN Z =30 X 1 +60 X 2

Sujeto a: 3 X 1 +2 X 2 ≤180
X1 + X 2≥ 50
X1 ¿ 40
X 2≤ 70
X2 7
≤
X1 8
X i ≥0 ∀ i=1,2
8. Supuestos

- La información general sobre costos ($/lb), disponibilidad (lbs) y tiempo (horas/lb) no

cambia

CASO 2.

Una Cía. Manufacturera ha discontinuado la producción de una cierta línea del producto la
cual no era rentable. El hecho crea un exceso de capacidad que debe emplearse. La gerencia
ha decidido que la capacidad extra se dedique a uno o más de los productos que aparecen
bajo las referencias A-1, Z-3, B-7. La capacidad extra disponible de las diferentes máquinas
usadas en el procesamiento de los productos es la siguiente:

Máquina Tiempo disponible (horas máquina/semana)

Torno 200
Fresa 100
Lija 50

Además el número de horas/máquina requeridas por cada unidad del producto respectivo
son:

Máquina A-1 Z-3 B-7

Horas-máquina/ud Horas-máquina/ud Horas-máquina/ud
Torno 8 2 3
Fresa 4 3 0
Lija 2 0 1

El Dpto. de ventas estima que las ventas de A-1 y Z-3 superarán la máxima tasa de
producción, sin embargo B-7 se venderá como máximo a una tasa de 20 uds/semana. Las
ganancias unitarias son de $ 20. $ 6 y $ 8 respectivamente. Cuántas uds. se deben fabricar
de cada referencia para maximizar las utilidades?

SOLUCIÓN:

1. Reformulación del problema

Determinar qué cantidad de producto de cada referencia se debe fabricar semanalmente con el propósito de
maximizar ganancias y cumplir con todos los requerimientos, ver cuadros # 1 y # 2

2. Objetivo

Maximizar utilidades totales

3. Variables de decisión

X i : Cantidad de uds. del producto a fabricar semanalmente de cada referencia i ,

donde i =1,2,3 (1 = A-1; 2 = Z-3; 3 = B-7)

4. Limitaciones

- Total de horas/semana disponibles en el torno, 200

- Total de horas/semana disponibles en la fresa, 100

- Total de horas/semana disponibles en la lijadora, 50
- La referencia del producto B-7 se venderá como máximo a una tasa de 20 uds/semana

5. y 6. Relaciones y Modelo

MAX
Z =20 X 1 +6 X 2 +8 X 3
Sujeto a:
8 X 1 +2 X 2 +3 X 3 ≤ 200
4 X 1 +3 X 2 ¿ 100
2X 1 +
X 3≤ 50
X 3≤ 20
X i ≥0 ∀i=1,2,3
7. Supuestos

- Todo lo producido se vende

- La información en general no cambia

CASO 3.
Una empresa fabricante de muebles de oficina, produce dos tipos de escritorio: ejecutivos y
tipo secretaria. La empresa tiene dos plantas en las que fabrica los escritorios. La planta 1
que es una planta antigua, opera con doble turno 80 horas por semana. La planta 2 es una
planta más nueva y no opera a su capacidad total. Sin embargo, y debido a que los
administradores planean operar la segunda planta con un turno doble como el de la planta 1,
se han encontrado operarios para que laboren los dos turnos. En estos momentos cada turno
de la planta 2 trabaja 25 horas/semana, no se paga ninguna prima adicional a los
trabajadores del segundo turno. El tiempo de producción (horas/ud) y los costos estándar
($/ud) en cada planta se describen en la tabla. La compañía a competido con éxito en el
pasado asignando un precio de $ 350.000 a los escritorios ejecutivos, sin embargo, parece
que la Cía. Tendrá que reducir el precio de los escritorios secretariales a $ 275.000 con el
objeto de estar en posición competitiva. La empresa ha estado manifestando exceso de
costos en las últimas 8 a 10 semanas, por lo tanto los administradores han fijado una
restricción presupuestaría semanal sobre los costos de producción semanal. El presupuesto
semanal para la producción total de los escritorios ejecutivos es de $ 2.000.000, y para los
escritorios secretariales es de $ 2.200.000. se pretende diseñar el programa de producción
que optimice las utilidades.

Tiempo Producción Costo estándar Precio Presupuesto

(horas/semana) (miles $/ud) (miles $/ud) (miles $/ud)
Escritorio Planta 1 Planta 2 Planta 1 Planta 2

Ejecutivo 7 6 250 260 350 2000

Secretaria 4 5 200 180 275 2200

Total 80 50

SOLUCIÓN:

1. Reformulación del problema

Determinar la cantidad de escritorios de cada tipo a producir semanalmente en cada planta, de tal manera que
se cumplan con todos los requerimientos establecidos con el objetivo de maximizar las utilidades.

2. Objetivo

Maximizar las utilidades totales

3. Variables de decisión

X ij : Cantidad de escritorios a producir semanalmente de cada tipo i en la planta j ,

donde i =E, S (E = Ejecutivo; S = Secretaria) y j = 1,2
4. Limitaciones

- El presupuesto semanal para la producción de escritorios ejecutivos en las plantas 1 y 2

no deben exceder los $ 2.000.000
- El presupuesto semanal para la producción de escritorios secretariales en las plantas 1 y
2 no deben exceder los $ 2.200.000
- El tiempo de producción de los escritorios tipo ejecutivo y secretarial en la planta 1 no
debe exceder las 80 horas/semana
- El tiempo de producción de los escritorios tipo ejecutivo y secretarial en la planta 2 no
debe exceder las 50 horas/semana

5. y 6. Relaciones y Modelo

MAX
Z =350 ( X E 1 +X E 2 ) +275 ( X S1 + X S2 )−250 X E 1 −260 X E 2 −200 X S !−180 X s} } } { ¿¿ ¿

Sujeto a: 7
X E! +4
X S! ¿ 80
6 X E2 +5
X S2 ¿ 50
250 X E 1 + 260 X E 2 ¿ 2000
200
X S! +180 X S2 ¿ 2200
X ij ≥0 ∀ i=E , S
∀ j=1,2

7. Supuestos

- Todo lo producido se vende

- La información no sufre variaciones