8/10/2019 UPN IO-I S03

1/31

Investigacin de Operaciones ISesin 03

Ing. Pedro Pablo Rosales Lpez

8/10/2019 UPN IO-I S03

2/31

Contenido 3/7

Programacin Lineal

Solucin en Lindo e Interpretacin. Anlisis de sensibilidad.

Prctica Dirigida.

8/10/2019 UPN IO-I S03

3/31

INTERPRETACION DERESULTADOS DEL LINDO

Investigacin de Operaciones I

8/10/2019 UPN IO-I S03

4/31

Utilizacin de software

Cualquier modelo de programacin lineal se

puede resolver haciendo uso del LINDO Proceso iterativo.

Alrededor de los puntos crticos o vrtices de la reginfactible.

8/10/2019 UPN IO-I S03

5/31

Anlisis de Sensibilidad

El anlisis de sensibilidad se realiza con la finalidad deobservar el/los efectos que podra causar un cambio enalguno de los parmetros del modelo.

Este tipo de anlisis es muy importante para obtenerinformacin que nos pueda servir para cualquier procesode toma de decisiones.

La solucin de un problema de programacin lineal porcomputadora tiene, cuando ms, m variables positivas,siendo m el nmero de restricciones.

Cuando la solucin por computadora tiene menos de m

variables positivas, se llama degenerada y en este casoespecial se deber tener cuidado al interpretar algunosresultados.

8/10/2019 UPN IO-I S03

6/31

Tabla de Resultados

Tiene cuatro partes:

Resultados del Valor ptimo y solucin ptima. Resultados de las restricciones.

Resultados sobre rangos de los coeficientes de lafuncin objetivo.

Resultados sobre los rangos de los lados derechos delas restricciones.

8/10/2019 UPN IO-I S03

7/31

Modelo en el LINDO

Max 200X + 180Y + 190Z

st 12X+15Y + 10Z < 1200

5X+3Y+6Z > 500

end

8/10/2019 UPN IO-I S03

8/31

Valor y solucin ptimos

OBJECTIVE FUNCTION VALUE

1) 22800.00

VARIABLE VALUE REDUCED COSTX 0.000000 28.000000Y 0.000000 105.000000

Z 120.000000 0.000000

Valor Optimo

Solucin Optima

8/10/2019 UPN IO-I S03

9/31

Costo Reducido:

Definicin 1

El costo reducido es la tasa (por unidad de aumento)a la cual disminuye el valor objetivo cuando unavariable es forzada a entrar en una solucin ptima.

Definicin 2

Cantidad en la que debe cambiar el coeficiente deuna variable en la funcin objetivo para obtener unvalor ptimo positivo. Si la variable ya tiene un valorptimo positivo su costo reducido ser cero

8/10/2019 UPN IO-I S03

10/31

Resultados de las restricciones

ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 19.0000003) 220.000000 0.000000

Resultados de holguras y/o

excedentes

RESTRICCIONACTIVA

RESTRICCININACTIVA

8/10/2019 UPN IO-I S03

11/31

Holgura y/o excedente

Intuitivamente:

Sobrante, remanente, residuo, margen o resto. Matemticamente:

Es la diferencia que existe entre el lado izquierdo y ellado derecho de una restriccin o viceversa de

acuerdo al sentido que tenga la desigualdad. Lasvariables de holgura y/o excedente siempre tienencomo valor cero (0) positivo (+), al igual que lasvariables de decisin.

Administrativa: Hay que tomar en cuenta de qu trata la restriccin y

tambin el contexto del problema.

8/10/2019 UPN IO-I S03

12/31

El precio dual

El precio dual para una restriccin muestra la

mejora del valor ptimo cuando el lado derechode una restriccin aumenta una unidad, con losdems datos fijos.

Caso de degeneracin

Si la suma de variables positivas es mayor al nmerode restricciones del modelo entonces la solucin esdegenerada.

8/10/2019 UPN IO-I S03

13/31

Rangos de coeficientes de la F. O.

RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES

VARIABLE CURRENT ALLOWABLE ALLOWABLECOEF INCREASE DECREASEX 200.000000 28.000000 INFINITYY 180.000000 105.000000 INFINITYZ 190.000000 INFINITY 23.333332

8/10/2019 UPN IO-I S03

14/31

Sensibilidad con la Funcin Objetivo

El cambio en los coeficientes de la funcin

objetivo altera la pendiente de los contornos desta. Esto puede afectar o no a la solucinptima y al valor ptimo de la funcin objetivo

8/10/2019 UPN IO-I S03

15/31

Significado de rangos para la FO

Las columnas ALLOWABLE INCREASE yALLOWABLEDECREASE bajo el encabezado OBJ

COEFFICIENT RANGESdicen cuanto puede aumentaro disminuir sin alterar la solucin ptima, mientras losdems datos se conservan constantes. Por supuesto,como la reditualidad en este rango vara, los valores del

Valor Optimo varan. Cuando un coeficiente se modifica en menos de la

cantidad admisible, la solucin ptima actualpermanece como nica solucin ptima del modelo.

Cuando un coeficiente en particular es aumentado (odisminuido) en la cantidad admisible, habr una solucinptima alterna con un valor ptimo mayor (o menor)para la variable afectada.

8/10/2019 UPN IO-I S03

16/31

Clculo de los rangos de los coef. de la F.O.

Para calcular el rango del coeficiente de una

variable en la funcin objetivo: al valor actual sele resta la mxima disminucin permitida ( ladoizquierdo del intervalo), y al valor actual se lesuma el mximo aumento permitido ( lado

derecho del intervalo)

8/10/2019 UPN IO-I S03

17/31

Rangos del lado derecho de las restriciones

RIGHTHAND SIDE RANGESROW CURRENT ALLOWABLE ALLOWABLERHS INCREASE DECREASE

2 1200.000000 INFINITY 366.6666563 500.000000 220.000000 INFINITY

8/10/2019 UPN IO-I S03

18/31

Precio Dual

Representa el costo de oportunidad de una

unidad adicional en el lado derecho o trminoindependiente de la restriccin correspondiente.

Cunto se afecta la funcin objetivo, por cadaunidad adicional que se incremente el lado

derecho. Precio Dual Positivo (+)

Un aumento en el lado derecho MEJORAla funcinobjetivo.

Precio Dual Negativo (-) Un aumento en el lado derecho PERJUDICA la

funcin objetivo.

8/10/2019 UPN IO-I S03

19/31

El precio dual y el rango vlido

Precio Dual

La interpretacin del precio dual es vlida para un rango, el cual queda

especificado por las columnas ALLOWABLE INCREASE yALLOWABLEDECREASE

En este rango el precio dual es constante

Clculo del Rango del Lado Derecho

Para calcular el rango del lado derecho de una restriccin: al valoractual se le resta la mxima disminucin permitida ( lado izquierdo delintervalo), y al valor actual se le suma el mximo aumento permitido. (lado derecho del intervalo)

Restricciones Inactivas El precio dual de una restriccin inactiva ser siempre cero.

La informacin de sensibilidad no nos proporciona nada sobre losnuevos valores de las variables de decisin, slo trata de explicar elcomportamiento del valor objetivo.

8/10/2019 UPN IO-I S03

20/31

ANLISIS DE SENSIBILIDAD

Investigacin de Operaciones I

8/10/2019 UPN IO-I S03

21/31

3

4

64

y20x15Max

8y2x2:sa 8y2x

0y,x

Anlisis de sensibilidad

A partir de la resolucin grfica del problema se tiene:

Solucin ptima : x*= ; y*=

Valor ptimo : z = z(0,4) =

8/10/2019 UPN IO-I S03

22/31

El anlisis de sensibilidad permite responder, entre otras,las siguientes preguntas:

1)Cul es el intervalo de variacin de algn coeficientede la funcin objetivo, de modo que la actual solucin siga

siendo la ptima?Sea z = c1x + c2y

La solucin ptima de la nueva funcin, seguir siendo:x*= ; y*=

si:

Anlisis de sensibilidad.

8/10/2019 UPN IO-I S03

23/31

2) Cul es la variacin del actual valor ptimo de lafuncin objetivo, si cambIamos en una unidad algncoeficiente del lado derecho de las restricciones ?

Estudiaremos por separado las variaciones de cada unode los coeficientes del lado derecho de las restricciones,

de modo preservar la geometra del problema, esto es,que se conserven las mismas restricciones activas de lasolucin ptima inicial.

Anlisis de sensibilidad.

8/10/2019 UPN IO-I S03

24/31

Primera restriccin.

Segunda restriccin.

Anlisis de sensibilidad.

8/10/2019 UPN IO-I S03

25/31

SOFTWARE LINDO

Investigacin de Operaciones I

8/10/2019 UPN IO-I S03

26/31

Que es Lindo?

Es un software muy bsico que permite realizar

optimizacin de problemas de programacinlineal (PL) y cuadrtica, definidos sobrevariables reales y/o binarias.

Sintaxis La Sintaxis requerida para LINDO tiene 3 requisitos

mnimos.

Se deben diferenciar 3 partes:1. La funcin objetivo

2. Las variables de decisin

3. Las restricciones.

8/10/2019 UPN IO-I S03

27/31

Funcin Objetivo

La funcin objetivo debe estar siempre al comienzo delmodelo y debe comenzar con:

MAX para maximizar MIN para minimizar

Al finalizar de formular la funcin objetivo y antes decomenzar con la formulacin de las restricciones debecolocarse una de las siguientes sentencia: SUBJECT TO SUCH THAT S.T. ST.

Variables de Decisin LINDO tiene un lmite de 8 caracteres para nombrarlas. El nombre debe ser un carcter alfabtico (A-Z) seguido de

cualquier carcter excepto por: ! ) + - = < >

8/10/2019 UPN IO-I S03

28/31

Restricciones

Se les puede dar nombres a las restricciones lo que hacen mssencillo leer el reporte de solucin.

Para los nombres de las restricciones se sigue las mismas reglasque para las variables. Para hacerlo se debe comenzar la restriccin con su nombre,

seguido de un parntesis derecho, luego del mismo se comienzacon la formulacin de la restriccin.

Ejemplo: XBOUND) X < 10

Solo constantes pueden ser definidas del lado derecho de lasrestricciones.

LINDO solo reconoce 5 operadores: +, -, >,

8/10/2019 UPN IO-I S03

29/31

Sentencias Opcionales

Se incluyen en el texto del programa luego de lasentencia END.

FREE remueve todos los lmites en ,permitiendo a la tomar cualquier valor real positivo onegativo

GIN hace la una entera (restringida a unconjunto de enteros no negativos).

INT hace la binaria (restricta a 0 1)

SLB pone un lmite inferior en de

SUB pone un lmite superior en de

TITLE hace el ttulo del modelo

8/10/2019 UPN IO-I S03

30/31

Formulacin en LINDO

8/10/2019 UPN IO-I S03

31/31

Un silencio a tiempo es ms

elocuente que muchas palabras.

Martn Farquhar Tupper