Investigacion Operativa

Tema 1 Modelos lineales y soluci´ n gr´ fica o a
La programaci´ n lineal es una importante rama de la Investigaci´ n Operativa. o o Esta t´ cnica matem´ tica consiste en una serie de m´ todos que permiten obtener e a e la mejor soluci´ n en problemas de optimizaci´ n lineal con restricciones. Este o o tipo de problemas surgen en la pr´ ctica en diferentes contextos cuando se trata a de asignarrecursos limitados a actividades que los necesitan para ser realizadas. La importancia de esta t´ cnica radica en la variedad de sistemas que se pueden e representar utilizando un modelo lineal, as´ como su aplicaci´ n a otras areas de la ı o ´ optimizaci´ n. Algunos ejemplos son la asignaci´ n de recursos a necesidadas, plao o nificaci´ n de la producci´ n, organizar el transporte de un productodesde or´genes o o ı a destinos, problemas de mezclas, etc. La programaci´ n lineal utiliza un modelo matem´ tico para describir el probleo a ma. El adjetivo lineal se refiere a que todas las funciones del modelo son lineales.

1.1 El modelo lineal
Un modelo lineal es el que trata de optimizar (maximizar o minimizar) una funci´ n o lineal sujeta a que las variables verifiquen un sistema deinecuaciones lineales opt z = cT x sujeto a Ax > b x≥0 1
≤

(1.1)

(1.2) (1.3)

2

Tema 1. Modelos lineales y soluci´ n gr´ fica o a

(1.1) es la funci´ n a optimizar y se llama funci´ n objetivo, (1.2) son las deo o sigualdades que deben verificar las variables y se llaman restricciones y (1.3) son las restricciones de no negatividad. Los elementos que aparecen en el modelo planteado son lossiguientes: • x, vector de variables de decisi´ n, con n componentes. o • cT , vector de precios o vector de costes unitarios, con n componentes. • b, vector de recursos, con m componentes. • La matriz A, con m filas y n columnas se llama matriz de coeficientes tecnol´ gicos. Cada elemento aij de la matriz A representa la cantidad de reo curso i, i = 1, . . . , m, que se necesita para realizar unaunidad de actividad j, j = 1, . . . , n. En el modelo lineal, cT , b y A son par´ metros conocidos; el vector x es el veca tor de variables cuyo valor hay que determinar con el objetivo de que los recursos del vector b sean asignados de forma optima. ´

1.2 Formas de escribir el modelo
1. Teniendo en cuenta el tama˜ o de los vectores y de la matriz de coeficientes. n

opt z = c1 x1 + c2 x2 + · · ·+ cn xn sujeto a a11 x1 + a12 x2 + · · · + a1n xn > b1 a21 x1 + a22 x2 + · · · + a2n xn > b2 . . . .. . . . . . . . . . . am1 x1 + am2 x2 + · · · + amn xn > bm x1 , x2 . . . xn ≥ 0
≤ ≤ ≤

OpenCourseWare, UPV/EHU

1.3. Construcci´ n de modelos o

3

2. Forma matricial.  x1    .  opt z = (c1 , . . . , cn )  .  .   xn sujeto a  a a12  11   a21 a22  .  . .  . . .  am1 am2 .. . a1n . . . a2n . .. . . . . . . amn         x1 x2 . . . xn  b  ≤  1      b2     =  .  .    .     ≥  bm   

(x1 , x2 , · · · , xn )T ≥ (0, 0, · · · , 0)T

3. Si a1 , a2 , . . . , an son las columnas de la matriz A. opt z = c1 x1 + c2 x2 + · · · + cn xn sujeto a a1 x1 + a2 x2 + · · · + an xn > b xj ≥ 0 , j = 1, . . . , n
≤

1.3 Construcci´ n demodelos o
Cuando se quiere analizar un sistema real por medio de la programaci´ n lineal el o primer paso es construir un modelo matem´ tico que represente el problema. Este a primer paso es el m´ s dif´cil en el an´ lisis y, es importante porque la soluci´ n a ı a o que se obtiene para el sistema depende del modelo planteado. Para construir un modelo no existen reglas, por eso algunos ejemplos pr´cticos pueden ser de ayuda a para desarrollar cierta habilidad.

Investigaci´ n Operativa. Programaci´ n Lineal o o

4

Tema 1. Modelos lineales y soluci´ n gr´ fica o a

Ejemplo 1. Problema de transporte. Una empresa produce bicicletas en tres sucursales que tiene en las ciudades C1 , C2 y C3 . La capacidad de producci´ n mensual en cada una de las ciudades o es 1000, 2100 y 1500,...