PROGRAMACIÓN LINEAL

MODELOS DE PROGRAMACIÓN MATEMÁTICA

PROGRAMACIÓN LINEAL

Temario:

II.1. Introducción y ejemplos de Modelamiento.

II.2. Resolución gráfica de problemas.

II.3. Análisis de Sensibilidad.

II.4. El Método Simplex.

II.1 Introducción y ejemplos de Modelamiento.

i) Problema de Transporte. El problema consiste en decidir cuántas unidades trasladar desde ciertos puntos de origen (plantas, ciudades, etc.) a ciertos puntos de destino (centros de distribución, ciudades, etc..) de modo de minimizar los costos de transporte, dada la oferta y demanda en dichos puntos.

Se suponen conocidos los costos unitarios de transporte, los requerimientos de demanda y la oferta disponible.

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

Diagrama:

Variables de decisión:

x_ij = Unidades transportadas desde la planta i (i=1,2), hasta el centro de distribución j (j=1,2,3)

Función Objetivo:

Minimizar el costo total de transporte dado por la función:

21x₁₁+25x₁₂+15x₁₃+28x₂₁+13x₂₂+19x₂₃

Restricciones del problema:

1) No Negatividad: x_ij ³ 0

2) Demanda:

CD₁ : x₁₁ +x₂₁ = 200

CD₂ : x₁₂ +x₂₂ = 200

CD₃ : x₁₃ + x₂₃ = 250

3) Oferta :

P₁ : x₁₁ + x₁₂ + x₁₃ £ 250

P₂ : x₂₁ + x₂₂ + x₂₃ £ 450

Las variables de decisión deben aceptar soluciones como números reales para tener un modelo de P.L.

ii) Problema de la dieta: este consiste en determinar una dieta de manera eficiente, a partir de un conjunto dado de alimentos, de modo de satisfacer ciertos requerimientos nutricionales.

Supongamos que se tiene la siguiente información:

	Leche (galon)	Legumbre (1 porción)	Naranjas (unidad)	Requerimientos Nutricionales
Niacina	3,2	4,9	0,8	13
Tianina	1,12	1,3	0,19	15
Vitamina C	32	0	93	45
Costo	2	0,2	0,25

Variables de decisión:

x₁ : galones de leche utilizados en la dieta.

x₂ : porciones de legumbre utilizadas en la dieta.

x₃ : unidades de naranja utilizadas en la dieta.

Función Objetivo:

Minimizar el costo total de la dieta, dado por:

2 x₁ + 0.2 x₂ + 0.25 x₃

Restricciones del problema:

Requerimientos mínimos de los nutrientes considerados:

3.2 x₁ + 4.9 x₂ + 0.8 x₃ ³ 13

1.12 x₁+ 1.3 x₂ + 0.19 x₃ ³ 15

32 x₁+ + 9 x₃ ³ 45

x₁ ³ 0 ; x₂ ³ 0 ; x₃ ³ 0

II.2. Resolución gráfica de problemas.

Consideremos el siguiente problema a resolver gráficamente:

Max z = 3x₁ + 5x₂

sa: x₁ £ 4

2x₂ £ 12

3x₁ + 2x₂ £ 18

x₁,x₂ ³ 0

En primer lugar, se debe obtener la región de puntos factibles en el plano, obtenida por medio de la intersección de todos los semi - espacios que determinan cada una de las inecuaciones presentes en las restricciones del problema.

Enseguida, con el desplazamiento de las curvas de nivel de la función objetivo en la dirección de crecimiento de la función (que corresponde a la dirección del vector gradiente de la función, Ñz(x₁,x₂) = (3,5)^T), se obtiene la solución óptima del problema en la intersección de las rectas: 2x₂ = 12 y 3x₁+2x₂ = 18 (restricciones activas). Esto es:

x₁^* = 2 x₂^* = 6

z^* = 3 x₁^* + 5 x₂^* = 36

Notar que se pueden dar otras situaciones en la búsqueda de una solución óptima para esta clase de problemas:

1) La solución óptima exista pero haya más de una. En el ejemplo, considere la nueva función objetivo: z = 6x₁+4x₂.

2) El problema no tenga solución, dada una región de puntos factibles no - acotada. En el ejemplo, reemplace cada desigualdad £ por una ³.

3) El problema no tenga solución, porque no existen puntos factibles. En el ejemplo, suponga que agregamos la restricción: x₁ ³ 5.

II.3. Análisis de sensibilidad.

A partir de la resolución gráfica del problema se tiene:

Solución óptima : x₁^*= 2 ; x₂^*= 2

Valor óptimo : z = z(2,2) = 70

El análisis de sensibilidad permite responder, entre otras, las siguientes preguntas:

1) ¿Cuál es el intervalo de variación de algún coeficiente de la función objetivo, de modo que la actual solución siga siendo la óptima?

Sea z = c₁x₁+c₂x₂

La solución óptima de la nueva función, seguirá siendo: x₁^*= 2 ; x₂^*= 2 asi:

También podemos estudiar el intervalo de un sólo coeficiente, dejando el resto de los parámetros fijos:

2) ¿ Cuál es la variación del actual valor óptimo de la función objetivo, si cambamos en una unidad algún coeficiente del lado derecho de las restricciones ?

Estudiaremos por separado las variaciones de cada uno de los coeficientes del lado derecho de las restricciones, de modo preservar la geometría del problema, esto es, que se conserven las mismas restricciones activas de la solución óptima inicial.

Primera restricción.

La mayor variación del coeficiente del lado derecho se alcanza en x₁ = 0 y x₂ = 4, de donde se obtiene:

z(0,4) = 15 x 0 + 20 x 4 = 80 y b₁^* = 0 + 2 x 4 = 8

La menor variación del coeficiente del lado derecho se alcanza en: x₁ = 4 ; x₂ = 0, de donde se obtiene:

z(4,0) = 15 x 4 + 20 x 0 = 60 y b₁ = 4 + 2 x 0 = 4

De aquí, se calcula el precio sombra P₁, que indica la razón o tasa de cambio de la función objetivo con respecto al cambio en una unidad del lado derecho:

Segunda restricción.

La mayor variación del coeficiente del lado derecho se alcanza en x₁ = 6 y x₂ = 0, de donde se obtiene:

z(0,4) = 15 x 6 + 20 x 0 = 90 y b₁^*= 2 x 6 + 2x0 = 12

La menor variación del coeficiente del lado derecho se alcanza en: x₁= 0 ; x₂= 3, de donde se obtiene:

z(4,0) = 15 x 0 + 20 x 3 = 60 y b₁= 2 x 0 + 2 x 3 = 6

De aquí, se calcula el precio sombra P₂, que indica la razón o tasa de cambio de la función objetivo con respecto al cambio en una unidad del lado derecho:

II.4. El Método Simplex.

En lo que sigue consideremos el siguiente problema de programación lineal en su forma estándar.

Min c₁x₁ + c₂x₂ + ... + c_nx_n

sa a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n = b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n = b₂

... ... ...

a_m1x₁ + a_m2x₂ + ... + a_mnx_n = b_m

x_i ³ 0, i = 1, 2, ..., n y m £ n

Matricialmente escrito como:

Min c^Tx

sa Ax = b

x ³ 0

No existe pérdida de la generalidad al suponer que un problema viene dado en la forma estándar. En efecto, si tuviésemos el siguiente problema:

P) Max 9u + 2v + 5z

sa 4u + 3v + 6z £ 50

u + 2v + 3z ³ 8

2u – 4v + z = 5

u,v ³ 0

z Î IR

Es posible reformular de manera equivalente el problema anterior usando que:

1) Siempre es posible llevar un problema de maximización a uno de minimización. Si f(x) es la función objetivo a maximizar y x^* es la solución óptima:

f(x^*) ³ f(x) , " x factible

- f(x^*) £ - f(x) , " x factible

\ x^* es también mínimo de - f(x)

2) Cada restricción del tipo £ puede ser llevada a una ecuación de igualdad usando una (nueva) variable de holgura no negativa, con un coeficiente nulo en la función objetivo.

3) De igual modo, cada restricción del tipo ³ puede ser llevada a una ecuación de igualdad usando una variable de exceso no negativa.

4) Siempre es posible escribir una variable libre de signo como la diferencia de dos variables no negativas.

En resumen el problema P) puede ser escrito de manera equivalente como:

Min - 9x₁ - 2x₂ - 5x₃ + 5x₄ + 0x₅ + 0x₆

sa: 4x₁ + 3x₂ + 6x₃ - 6x₄ + x₅ =50

x₁ + 2x₂ - 3x₃ + 3x₄ - x₆ = 8

2x₁ - 4x₂ + x₃ - x₄ = 5

x_i ³ 0, i=1,2,3,4,5,6.

Con u = x₁

v = x₂

z = x₃ - x₄

s₁ = x_{5 (HOLGURA)}

s₂ = x_{6 (EXCESO)}

La búsqueda de la solución óptima se restringe a encontrar un vértice óptimo y cada vértice del conjunto de las restricciones del problema, llamado región de puntos factibles, corresponde a una solución básica factible del sistema Ax = b.

Esta solución básica factible, corresponde a su vez a aquellas soluciones que resultan de resolver el sistema para exactamente m variables, fijando las restantes n-m en cero, llamadas respectivamente variables básicas y no-básicas, que además deben satisfacer condiciones de no-negatividad.

Teorema Fundamental de la Programación Lineal:

Si un problema tiene solución óptima, tiene una solución básica factible óptima.

Dada una matriz B de m x m invertible, esta induce una partición de las variables y parámetros del modelo como lo muestra la siguiente diapositiva.

Criterio de Optimalidad:

La ecuación que define cada uno de los costos reducidos es:

Donde j es el índice de variable no-básica y A_j la respectiva columna en A de esa variable.

La actual solución básica factible es óptima ssi r_j ³ "j, existe una variable no básica x_p con costo reducido negativo, que entra a la nueva base.

Para decidir quién deja la base, es necesario calcular el mayor valor que puede tomar la variable entrante que garantiza la factibilidad de la nueva solución básica, con:

y se debe calcular:

Ejemplo.

Resolver el siguiente problema de P.L.

Max 40x + 60y

sa: 2x + y £ 70

x + y £ 40

x + 3y £ 90

x,y ³ 0

Se deben agregar 3 variables de holgura ( x₁ , x₂ , x₃ var.básicas), y llevar a forma estándar (x₄ = x y x₅ = y).

Min -40x₄ – 60x₅

sa: x₁ + 2x₄ + x₅ = 70

x₂ + x₄ + x₅ = 40

x₃ + x₄ + 3x₅ = 90

x_i ³ 0, i = 1, 2, 3, 4, 5

Tabla inicial:

x1	x2	x3	x4	x5
1	0	0	2	1	70
0	1	0	1	1	40
0	0	1	1	3	90
0	0	0	-40	-60	0

Usamos como variable entrante a la base x₅ (pues r₅<0).

x1	x2	x3	x4	x5
1	0	0	2	1	70
0	1	0	1	1	40
0	0	1	1	3	90
0	0	0	-40	-60	0

Se calcula Min { 70/1, 40/1, 90/3 } = 30, por lo tanto sale x₃.

Actualizando, queda la siguiente tabla (no óptima), donde la variable entrante a la base es x₄ (pues r₄<0).

x1	x2	x3	x4	x5
1	0	-1/3	5/3	0	40
0	1	-1/3	2/3	0	10
0	0	1/3	1/3	1	30
0	0	20	-20	0	1800

Se calcula Min { 40/(5/3), 10/(2/3), 30/(1/3) } = 15, por lo tanto x₂ deja la base actual.

Actualizando, queda la siguiente tabla final:

x1	x2	x3	x4	x5
1	-5/2	½	0	0	15
0	-1/3	-1/2	1	0	15
0	1/3	½	0	1	25
0	20	10	0	0	2100

Como todos los costos reducidos son mayores o iguales que cero nos encontramos en la solución óptima.

z* = - 40 x 15 - 60 x 25 = - 2100

En la formulación inicial, tenemos como solución óptima x^*=15, y ^*=25, con valor óptimo 2.100.

Resumen del Método Simplex:

Paso 0 : Escribir el problema de programación lineal en su forma estándar.

Paso 1 : Escoger una solución básica factible inicial.

Paso 2 : Escoger una variable no - básica con costo reducido negativo que determina la variable entrante y seguir al paso tres. Sin embargo, si todos los costos reducidos son mayores que cero , parar, ya que la actual solución es la óptima.

Paso 3 : Calcular el criterio de factibilidad que determina que variable deja la base. Si todos los cuocientes son negativos: problema no - acotado, parar.

Paso 4 :Actualizar la tabla de modo de despejar el valor de las nuevas variables básicas, los costos reducidos y el valor de la función objetivo. Volver al Paso 2.

No siempre es fácil obtener una solución básica factible inicial, en las variables originales del modelo. Para conseguir esto existen varios procedimientos como son:

• Método Simplex de dos fases.

• Método de la M – grande.

Método Simplex de dos Fases.

Fase 1: Se considera un problema auxiliar que resulta de agregar tantas variables auxiliares a las restricciones del problema, de modo de obtener una solución básica factible. Resolver por Simplex un nuevo problema que considera como función objetivo la suma de las variables auxiliares. Si el valor óptimo es cero ir a la Fase 2. En caso contrario, no existe solución factible.

Fase 2: Resolver por Simplex el problema original a partir de la solución básica factible hallada en la Fase1.

Ejemplo: Max 2x₁ + x₂

sa: 10x₁ + 10x₂ £ 9

10x₁ + 5x₂ ³ 1

x₁,x₂ ³ 0

Se debe agregar una variable de holgura (x₃) y una variable de exceso (x₄), y llevarlo a su forma estándar.

Min -2x₁ - x₂

sa: 10x₁ + 10x₂ +x₃ = 9

10x₁ + 5x₂ - x₄ = 1

x₁,x₂, x₃, x₄ ³ 0

Aplicamos Simplex de dos Fases :

Fase 1: Min x₅

sa: 10x₁ + 10x₂ +x₃ = 9

10x₁ + 5x₂ - x₄ + x₅ = 1

x₁,x₂, x₃, x₄, x₅³ 0

Quedando la siguiente tabla:

donde:

Luego se hace cero el costo reducido de la variable x₅ de la tabla anterior, y queda la siguiente tabla inicial.

x1	x2	x3	x4	x5
10	10	1	0	0	9
10	5	0	-1	1	1
-10	-5	0	1	0	-1

La variable entrante a la base es x₁ ( pues r₁ <>).

x1	x2	x3	x4	x5
10	10	1	0	0	9
10	5	0	-1	1	1
-10	-5	0	1	0	-1

Calculamos Min { 9/10, 1/10}= 1/10, por lo tanto sale x₅.

Obteniéndose la siguiente tabla final:

Donde, al anterior, corresponde a la solución óptima del problema en la Fase 1, con valor óptimo 0. De aquí entonces tomamos x₁ y x₃ como variables básicas.

Fase 2:

x1	x2	x3	x4
0	5	1	1	8
1	½	0	-1/10	1/10
-2	-1	0	0	0

En la tabla hacemos 0 los costos reducidos de variables básicas

x1	x2	x3	x4
0	5	1	1	8
1	½	0	-1/10	1/10
0	0	0	-1/5	1/5

Luego la variable entrante a la base es x₄ (pues r₄<0). Y calculando Min { 8/1, (-1/10)/(1/10) } = 8, se tiene que sale x₃.

Quedando:

x1	x2	x3	x4
0	5	1	1	8
1	1	0	1/10	9/10
0	1	1/5	0	9/5

donde la solución óptima del problema resulta ser:

Algunos casos especiales

1) Problema Infactible. Esta situación se detecta cuando el valor óptimo del problema de la Fase 1 da mayor que cero.

2) Múltiples soluciones óptimas. Esta situación se detecta cuando existen costos reducidos iguales a cero en una o más de las variables básicas óptimas.

3) Problema no acotado. Esta situación se detecta cuando al realizar el cálculo de la variable que deja la base, todos los elementos y_kj de la columna j en la tabla, son negativos para j el índice de una variable no básica con costo reducido negativo.

Bibliografía:

Investigacion-operaciones.ppt

http://www.ccee.edu.uy/ensenian/catmetad/material/practico%203.pdf

REVISEN LA DIAPOSITIVA QUE ESTA EN ESTA DIRECCION

http://www.investigacion-operaciones.com/operaciones.htm

O ELIJA LA OPCIÓN ----------->

TEMAS SOBRE INVESTIGACIÓN DE OPERACIONES, con información avanzada, en

formato "Power_Point" de Microsoft , pero como es un archivo muy grande (6,9 MB), se

recomienda bajarlo de la página WEB si dispone de un servicio de banda ancha.

<---------- Y se descargará esta diapositiva Investigacion_Operaciones.ppt

QUE CONTINE INFORMACION MUY IMPORTANTE SOBRE PROGRAMACION LINEAL