PROFESOR

CRISTOBAL MILETICH SOUZA PEIXOTO

PROGRAMACION LINEAL

Programación Lineal

Es una técnica matemática que sirve para optimizar la

asignacción de recursos limitados (escasos) entre demandas en

competencia

Recursos escasos:

PersonalMaquinaria y equipoEl efectivo y los fondos de capitalMateriales y suministrosServicios públicosEspacios de plantaTiempoInsumos

3

Características de los problemas de Programación Lineal

1.-Debe existir un objetivo explícito

2.-Los recursos deben ser limitados

3.-Las relaciones deben ser lineales

4.-Debe haber homogeneidad

Formulación de un problema de programación lineal

1.-Definir el objetivo2.-Definir las variables de decisión3.-Escribir la función objetivo4.-Escribir cada una de las restricciones

(variables de decisión y sus respectivos coeficientes)

5.- Poner el símbolo >=,<= o =, para cada restricción

6.- Escriba el lado derecha de cada restriccción

Solución de problemas de Programación lineal

1.-Método Gráfico, cuando sólo hay dos variables de decisión.

2.-Método Simplex.-Fue desarrollado en 1947 por George Dantzig y marcó el inicio del campo actual de la programación matemática.

3.-Complemento Solver de Excel

4

Método Gráfico

1. Formule el problema en términos

matemáticos

2. Plotee las ecuaciones de restricción

3. Determine el área de factibilidad

4. Plotee la función objetivo

5. Encuentre el punto óptimo

EJEMPLO

Caso PROTRAC

Planteamiento

Max 5000E + 4000F Función objetivo

10E + 15F <= 150 Capacidad Dpto. A20E + 10F<= 160 Capacidad Dpto. BE – 3F <= 0 Balance posición mercado30E + 10F >= 135 Horas empleadas para

pruebasE +F >= 0 Requerimiento Mínimo

producción

E>=0 , F>=0

Solución Gráfica (PROTAC)

0 9 18 27 36 45 54 63 72 81 90 99 108 117 126 135 144 153 162 171 180

0

9

18

27

36

45

54

63

72

81

90

99

108

117

126

135

144

153

162

171

180F

E

: 10 E + 15 F = 150

: 20 E + 10 F = 160

: 30 E + 10 F = 135

: 1 E - 3 F = 0

: 1 E + 1 F = 5

Payoff: 5000 E + 4000 F = 50500

Optimal Decisions(E ,F): ( 5, 7)

: 10E + 15F <= 150

: 20E + 10F <= 160

: 30E + 10F >= 135

: 1E - 3F <= 0

: 1E + 1F >= 5

Forma Estandar

Max 5000E + 4000F

10E + 15F + S1 = 150 20E + 10F + S2 = 160E – 3F +S3 = 030E + 10F -S4 = 135E +F -S5 = 0

E>=0 , F>=0

S = Variable de holgura (Slack variable)

Variables de Holgura

Desde el punto de vista práctico, una variable de holgura es un recurso ocioso

Desde el punto de vista computacional es lo que le falta o le sobra a una inecualidad para convertirse en igualdad

Restricciones obligatorias o activas

Son las que ayudan a formar el vértice óptimo.

Si la restricción obligatoria se vuelve menos restrictiva, se puede encontrar una solución mejor

Esto se consigue variando el parámetro del lado derecho

Estrechamiento y relajamiento de una restricción

Estrechar una restricción de desigualdad es hacerla más difícil de satisfacer. Para una restricción > esto significa aumentar el lado derecho. Para una restricción < significa disminuir el L.D.

Relajar una restricción es hacerla más fácil de satisfacer. Para una restricción > esto significa disminuir el lado derecho. Para una restricción < significa aumentar el L.D.

Situaciones especiales

Restricción redundante.- Su eliminación no ocasiona cambios en la región factible

Restricciones no acotadas (unbounded).- Area de solución ilimitada. No hay solución

Modelos no factibles (infeasibility).- Area de solución sin puntos comunes. No tienen solución

Degeneración.-Es cuando una variable en la solución tiene el valor de cero

Utilización del SOLVER

Vamos a utilizar el mismo ejemplo de PROTRAC para mostrar el uso de este programa

RESPUESTA A LA PREGUNTA:

¿QUÉ PASA SI…?

ANÁLISIS DE SENSIBILIDAD

Análisis de sensibilidad

Rara vez se conocen con certeza los parámetros de la función objetivo y las restricciones

Se trabaja con estimaciones iniciales para resolver el problema

Luego se analiza lo qué pasaría si alguno de los parámetros varía

Análisis de sensibilidad

El análisis de sensibilidad es el proceso que sirve para analizar un modelo de optimización usando diferentes valores de los parámetros

Parámetros.- Son los coeficientes de la función objetivo y los valores del lado derecho

Cambio en los coeficientes de la función objetivo

La pendiente de la función objetivo puede variar (sin alterar la solución óptima) en un rango determinado por las pendientes de las restricciones que se encuentran más cercanas al punto óptimo

Solución caso Protac

0 9 18 27 36 45 54 63 72 81 90 99 108 117 126 135 144 153 162 171 180

0

9

18

27

36

45

54

63

72

81

90

99

108

117

126

135

144

153

162

171

180F

E

: 10 E + 15 F = 150

: 20 E + 10 F = 160

: 30 E + 10 F = 135

: 1 E - 3 F = 0

: 1 E + 1 F = 5

Payoff: 5000 E + 4000 F = 50500

Optimal Decisions(E ,F): ( 5, 7)

: 10E + 15F <= 150

: 20E + 10F <= 160

: 30E + 10F >= 135

: 1E - 3F <= 0

: 1E + 1F >= 5

Cambio en los coeficientes de la función objetivo

La función objetivo tiene la forma:C1X1 + C2X2 = Z

X2 = _ C1X1 + Z C2 C2

La pendiente de esta ecuación es –C1/C2Si C1 aumenta mientras C2 permanece

constante la pendiente se vuelve más negativa

Ejemplo

Max Z = 34x1 + 40x24x1 + 6x2 <= 48 (oblibatoria)

restricción 1

2x1 + 2x2 <= 18 (obligatoria) restricción 2

2x1 + x2 <=16 restricción 3

x1 , x2 >=0Solución: X1 = 3X2 = 6Z = 342

Análisis de sensibilidad del ejemplo:

Las restricciones obligatorias son:4x1 + 6x2 <= 48 (pendiente: -2/3) Restricción 1

2x1 + 2x2 <= 18 (pendiente: -1) Restricción 2

(Las pendientes se calculan usando la fórmula presentada anteriormente)

La pendiente de la función objetivo estará entre estos dos valores, luego:

-1 >= -c1/c2 <= -2/3

Rango de optimización

Para encontrar el rango en que puede variar c1, mantenemos constante c2=40, luego:

-1<=- c1/40 <=-2/326.67 <= c1 <= 40El coeficiente de la función objetivo para x1

fluctúa entre un límite inferior de 26.67 y un límite superior de 40, rango dentro del cual los valores óptimos de las variables de los valores óptimos de las variables de decisión permanecen sin cambiardecisión permanecen sin cambiar

Por supuesto que el valor de Z cambia si se modifica c1

Cambios simultáneos

Regla del 100%Si se hacen cambios simultáneos en los

coeficientes de la función objetivo, calcule para cada uno el porcentaje del cambio con respecto al porcentaje permitido.

Si la suma de los cambios porcentuales no excede el 100 %, la solución óptima original seguirá siendo la misma (si es más del 100% no podemos estar seguros de ello y habrá que plantear y resolver el problema de nuevo)

Parámetros del lado derecho

Un cambio en el parámetro del lado derecho de una restricción puede afectar el área factible y tal vez provocar un cambio en la solución óptima

Para ver si este cambio es conveniente se usa el concepto del Precio Sombra o valor dual

Precio sombra

Es el cambio que se origina en Z por cada unidad que varía el lado derecho de una restricción

En otras palabras, es la ganancia (o pérdida) marginal a causa de la variación de una restricción en una unidad

Si se incrementa en una unidad la capacidad disponible de un recurso, el valor óptimo se incrementara en un valor igual a su precio sombra

Precio sombra

En el ejemplo anterior tenemos que el valor optimo de Z era:

Z= 34 (3) + 40 (6) = 342 si aumentamos en una unidad el valor del lado derecho

de la restricción (2) tenemos:4x1 + 6x2 = 48 2x1 + 2x2 = 19 Después de resolver el problema , los valores óptimos

serán: x1 = 4.5, x2 = 5 luegoZ = 34 (4.5) + 40 (5) = 353Variación de Z: 353-342= 11 el valor de Z aumentará en 11, éste es el precio

sombra

Precio sombra

Esto significa que por cada unidad extra que se emplee de la restricción (2) se tendrá 11 dólares de ganancia adicional

Si lo que cuesta aumentar esa unidad extra es menor que 11 dólares es conveniente hacerlo

Se debe hacer este cálculo para todas las restricciones a fin de determinar en cual de ellas se hace la inversión extra primero.

El complemento Solver calcula todos los precios sombras automaticamente

Rangos de factibilidad

Es el intervalo en el cual el parámetro del lado derecho puede variar mientras su precio sombra sigue siendo válido, (en este caso entre 18 y (en este caso entre 18 y 20)20)

Cuando la variable de holgura de una restricción es mayor que cero, su precio sombra es cero

Precios sombra, rangos y sensibilidad en el SOLVER

En el cuadro análisis de sensibilidad de SOLVER se encuentra información valiosa sobre los recursos utilizados, el rango en que la decisión óptima no cambia y el rango en que los coeficientes de la función objetivo no cambian la solución óptima.

Específicamente permite responder preguntas como: le gustaría comprar/vender más de un recurso, qué precio pagaría, cuántas unidades debe comprar/vender a ese precio, etc.

Cambios simultáneos

Regla del 100%Si se hacen cambios simultáneos en los lados

derechos de las restricciones, el precio sombra sigue siendo válido si la suma de los porcentaje del cambio con respecto al porcentaje permitido no pasan del 100%.

Si es más del 100% no podemos estar seguros de ello y habrá que plantear y resolver el problema de nuevo