ProgramacionLineal

CAPÍTULO 1. PROGRAMACIÓN
LINEAL Y TRANSPORTE.
1. INTRODUCCIÓN.
En 1947, el estadounidense George
B. Dantzing propuso el método del
simplex (proveniente de la palabra
simplejo) para modelizar
matemática y linealmente una
realidad.

Modelo Lineal
Max o Min Z = c1 x1 + c2 x2 + ....... + cn xn

(1.3)

donde Z está sujeta a una serie de restricciones:
a11 x1 + a12 x2 + ............. + a1n xn (≤ = ≥)b1
a21 x1 + a22 x2 + ............. + a2n xn (≤ = ≥) b2
.....................................................................
am1 x1 + am2 x2 + ............. + amn xn (≤ = ≥) bm

(1.4)

y además tenemos la restricción de no negatividad de las variables:
x1, x2, x3,.....xn ≥ 0

(1.5)

Modelo matricial y vectorial
(Max o Min) Z = cj * xj
sujeto a
A * xj (≤ = ≥) bi
xj ≥ 0
Donde:
xj (j = 1,....., n)Matriz A:(mxn)
ai,j
bi (i =1,....,m)
cj
Z

: vector de variables de acción.
: matriz tecnológica
: coeficientes técnicos de la matriz A.
: disponibilidad del recurso j.
: beneficio o coste por cada componente.
: función objetivo, función económica o de coste.

Modelo matricial:
⎛ a 11
⎜
⎜.
A = ⎜.
⎜
⎜.
⎜
⎝ a m1

.

.

.

.

.

.

a 1n ⎞
⎟
.
⎟
⎟
.
⎟
.
⎟
⎟
a mn ⎠

⎛ x1⎞
⎜
⎟
x
⎜ 2⎟
X = ⎜ . ⎟
⎜
⎟
.
⎜⎟
⎜
⎟
⎝xn⎠

Max o Min Z = Ct X
A*X (≤ = ≥) b
X≥0

⎛ c1⎞
⎜
⎟
c
⎜ 2⎟
C = ⎜ . ⎟
⎜
⎟
.
⎜
⎟
⎜
⎟
⎝cn⎠

⎛ b1⎞
⎜
⎟
b
⎜ 2⎟
b = ⎜ . ⎟
⎜
⎟
.
⎜
⎟
⎜
⎟
⎝bn⎠

EJEMPLO 1.
Una oficina de correos necesita un número diferente
de empleados de tiempo completo, para diferentes
días de la semana. El número de empleados de
tiempo completo requeridos para cada día se da en el
cuadro 1.1. Las reglas sindicales señalan quecada
empleado de tiempo completo, tiene que trabajar
durante cinco días consecutivos y, después descansar
dos días. Por ejemplo, un empleado que trabaja de
lunes a viernes, tiene que descansar el sábado y el
domingo. La oficina de correos quiere cumplir con
sus requerimientos diarios y utilizar solamente
empleados de tiempo completo. Formule un PL que
pueda utilizar la oficina de correos paraminimizar el
número de empleados de tiempo completo que hay
que contratar.

Día 1 = lunes
Día 2 = martes
Día 3 = miércoles
Día 4 = jueves
Día 5 = viernes
Día 6 = sábado
Día 7 = domingo

NÚMERO DE EMPLEADOS DE
TIEMPO COMPLETO REQUERIDOS
17
13
15
18
14
16
11

definimos xi como el número de empleados
que empiezan a trabajar el día i

Min Z = x1 + x2 + x3 + x4 + x5 + x6 + x7
x1 + x4 + x5 + x6 + x7 ≥ 17(Rest. del lunes)
x1 + x2 + x5 + x6 + x7 ≥ 13 (Rest. del martes)
x1 + x2 + x3 + x6 + x7 ≥ 15 (Rest. del miérc.)
x1 + x2 + x3 + x4 + x7 ≥ 19 (Rest. del jueves)
x1 + x2 + x3 + x4 + x5 ≥ 14 (Rest. del viern.)
x2 + x3 + x4 + x5 + x6 ≥ 16 (Rest. del sábado)
x3 + x4 + x5 + x6 + x7 ≥ 11 (Rest. del domin.)
xi ≥ 0 (i = 1,2, ,7)

EJEMPLO 3.
Una empresa produce cuatro modelos de armarios metálicos. En elCuadro 1.3 figuran las
horas útiles disponibles mensualmente en los 5 talleres de que consta la fábrica, así como los tiempos
que requiere en cada uno de estos talleres la obtención de una unidad de cada producto.
TIEMPO DE PRODUCCIÓN EN HORAS POR UNIDAD
TALLER
embutic
mecaniz.
montaje
acabado
embalaje

PRODUCTO 1
0,03
0,06
0,05
0,04
0,02

PRODUCTO 2
0,15
0,12
0,10
0,20
0,06

Cuadro 1.3

PRODUCTO 30,05
0,05
0,03
0,02

PRODUCTO 4
0,10
0,10
0,12
0,12
0,05

HORAS ÚTILES
DISPONIBLES
MENSUALMENTE
40
40
50
45
40

Por otra parte, para la fabricación de los armarios de tipo 2 y 4 se necesitan por unidad,
respectivamente, 2 metros cuadrados y 1,2 metros cuadrados de una chapa especial que escasea en el
mercado, siendo 2000 metros cuadrados la cantidad máxima disponible mensualmente. Por último, en
elcuadro 1.4 figuran los precios de venta y los costes variables unitarios correspondientes a los cuatro
productos, así como las cantidades máximas que puede absorber cada mes el mercado, tanto de
mayoristas como de minoristas, y las cantidades mínimas que es preciso entregar mensualmente para
cumplir los contratos de suministro existentes con ciertos clientes mayoristas.

PRODUCTO
1
2
3
4...