Unidad 1 Programación Lineal


¿Qué hacer con toda esta información?



Descargar 2,86 Mb.
Página5/22
Fecha de conversión21.06.2017
Tamaño2,86 Mb.
1   2   3   4   5   6   7   8   9   ...   22

¿Qué hacer con toda esta información?

  • Procurar que la solución siga siendo factible
  • Esto significa que las variables básicas no deben ser negativas. Mantener la no negatividad
  • 1) X2 = 4/3 +2/3 D1  0
  • 2) X1 = 10/3 -1/3 D1  0
  • 3) X5 = 3 - D1  0
  • 4) X6 = 2/3 -2/3 D1  0

Se consideran dos casos:

  • Caso 1: D1 >0
  • 1) Se satisface con cualquier valor
  • 2) D1  10
  • 3) D1  3
  • 4) D1  1
  • En consecuencia D1 debe ser a lo más 1

Caso 2: D1 < 0

  • Caso 2: D1 < 0
  • 2), 3) y 4) se satisfacen siempre
  • 1) D1 -2
  • en este caso D1 -2
  • Resumen: -2  D1  1
  • 6 - 2 Materia prima A 6+1
  • 4 Materia prima A 7

Haciendo el mismo análisis para la materia prima B se tiene:

  • Haciendo el mismo análisis para la materia prima B se tiene:
  • -2  D2  4
  • 8 - 2 Materia prima B 8+4
  • 6 Materia prima B 12

2. Cambio máximo en la relación Utilidad/Costo marginal

  • 2. Cambio máximo en la relación Utilidad/Costo marginal
  • La FO nunca se utiliza como ecuación pivote, por lo tanto cualquier cambio en sus coeficientes la afectarán sólo a ella en la tabla óptima.
  • Pueden ocurrir dos casos: que las variables sean básicas o no en tabla óptima.

Caso 1: Variables básicas

  • Caso 1: Variables básicas
  • Cambiar la ganancia marginal de X1 de 3 a 3 + D1
  • D1 puede ser positivo o negativo
  • La FO tendrá la forma
  • Z = (3+D1)X1 + 2X2
  • Utilizando este nuevo coeficiente se llega a la siguiente tabla óptima:
  • Los únicos cambios en los coeficientes no básicos X3 y X4 de la ecuación de Z

Estos cambios pueden determinarse de la tabla original, multiplicando los coeficientes no básicos y el segundo miembro de la fila de X1 por D1, y luego sumandolo a la fila Z óptimo.

  • Estos cambios pueden determinarse de la tabla original, multiplicando los coeficientes no básicos y el segundo miembro de la fila de X1 por D1, y luego sumandolo a la fila Z óptimo.

Para el caso de maximización:

  • Para el caso de maximización:
  • 1/3 - 1/3 D1  0 y
  • 4/3 + 2/3 D1  0
  • de la primera D1  1
  • y de la segunda D1  -2
  • -2  D1  1
  • Finalmente:
  • 3-2  C1  3 + 1
  • 1  C1  4
  • ¡¡¡¡¡ Inténtelo para C2 !!!!!

Caso 2: Variables no básicas

  • Caso 2: Variables no básicas
  • Un cambio en los coeficientes objetivos pueden afectar sólo a los coeficientes de la ecuación de Z (la columna correspondiente no se utiliza como pivote).
  • El caso en estudio no sirve porque X1 y X2 son básicas en la tabla óptima.

Ejemplo:

  • Ejemplo:
  • Sea Z = 5X1 + 2X2
  • para las mismas restricciones del ejemplo en estudio.
  • La tabla resultante es:

X2 es ahora no básica

  • X2 es ahora no básica
  • El objetivo es cambiar su coeficiente C2 = 2 a C2 + D2 y luego encontrar el intervalo.
  • Al aplicar el nuevo coeficiente habrá un cambio en el coeficiente de 0,5 a 0,5 - D2
  • En general, el cambio D del coeficiente objetivo original de una variable no básica conduce SIEMPRE al decremento en la misma cantidad del coeficiente objetivo en la tabla óptima.
  • La tabla permanecerá óptima en tanto que 0,5 -D2  0
  • esto es, D2  0,5

El intervalo es

  • El intervalo es
  • -infinito  D2  0,5 +2
  • -infinito  D2  2,5

Ejemplo:

  • Ejemplo:
  • Resolver el siguiente PL empleando simplex y realizar un análisis de sensibilidad.
  • MAX Z = 3X1 + 2X2 +5X3
  • sa
  • X1 + 2X2 + X3 ≤ 500
  • 3X1 + 2X3 ≤ 460
  • X1 + 4X2 ≤ 420
  • X1 ,X2 , X3 ≥ 0

1.5 Método Simplex Dual

  • 1.5 Método Simplex Dual
  • Cuando los problemas de PL no tienen una solución factible básica inicial con sólo holguras, se pueden resolver sin utilizar variables artificiales, entregando la misma información.
  • DEFINICIÓN DEL PROBLEMA DUAL
  • El dual es un problema de PL que se obtiene matemáticamente de un modelo primal de PL dado. Los problemas primal y dual están relacionados a tal grado que la solución de uno de ellos conduce en forma automática a la solución del otro.

En la mayoría de los procedimientos de PL, el dual se define para varias formas del primal, dependiendo de los tipos de restricciones, de los signos de las variables y del sentido de la optimización.

  • En la mayoría de los procedimientos de PL, el dual se define para varias formas del primal, dependiendo de los tipos de restricciones, de los signos de las variables y del sentido de la optimización.
  • Se incluirá una definición única del problema dual que incluye automáticamente a todas las formas del primal. Se basa en el hecho de que el problema de PL debe calcularse en forma estándar antes de resolverlo mediante el método simplex o simplex dual, de esta manera al definir el problema dual mediante la forma estándar, los resultados serán consistentes con la información contenida en la tabla simplex..
  • La forma estándar general del primal se define como:
  • maximizar o minimizar
  • sujeto a
  • i = 1, 2, ....., m
  • j = 1, 2, ..., n
  • xj 0
  • Notar que las n variables xj, incluyen los excesos y las holguras. El esquema se muestra en el siguiente diagrama:
  • El diagrama muestra que el dual se obtiene simétricamente del primal de acuerdo con las siguientes reglas:
  • Para toda restricción primal hay una variable dual
  • Para toda variable primal hay una restricción dual
  • Los coeficientes de las restricciones de una variable primal forman los coeficientes del primer miembro de la restricción dual correspondiente, el coeficiente objetivo de la misma variable se convierte en el segundo miembro de las restricción dual; y el segundo miembro de la restricción primal se convierte en el coeficiente objetivo de la respectiva variable dual
  • Estas reglas indican que el problema dual tendrá m variables (y1, y2, ..., ym) y n restricciones, (correspondientes a x1, x2 ,...., xn).
  • En la tabla siguiente se muestra como determinar los elementos restantes del problema dual: sentido de la optimización, tipo de restricciones y el signo de las variables duales.
  • Función Objetivo Dual
  • Estándar del primal Función objetivo Restricciones Variables
  • Maximización Minimización  Irrestrictas
  • Minimización Maximización  Irrestrictas
  • Todas las restricciones primales son ecuaciones y todas las variables son no negativas.
  • Ejemplo 1:
  • Primal
  • Maximizar Z = 5 X1 + 12 X2 + 4 X3
  • sujeto a X1 + 2 X2 + X3  10
  • 2 X1 - X2 + 3 X3 = 8
  • X1, X2, X3  0
  • Primal estándar
  • Maximizar Z = 5 X1 + 12 X2 + 4 X3 + 0 X4
  • sujeto a X1 + 2 X2 + X3 + X4 = 10
  • 2 X1 - X2 + 3 X3 +0 X4 = 8
  • X1, X2, X3  0
  • Dual
  • Minimizar w = 10 y1 + 8 y2
  • sujeto a X1: y1 + 2 y2  5
  • X2: 2 y1 - y2  12
  • X3: y1 + 3 y2  4
  • X4: y1 + 0 y2  0
  • y1, y2 irrestricta
  • y1 es irrestricta, pero además está “dominada por y1  0, la restricción dual asociada con X4, entonces al eliminar la redundancia el modelo es:
  • Minimizar w = 10 y1 + 8 y2
  • sujeto a: y1 + 2 y2  5
  • 2 y1 - y2  12
  • y1 + 3 y2  4
  • y1  0, y2 irrestricta
  • Dual Final
  • Unidad 2
  • Programación Lineal Aplicaciones
  • El objetivo general es encontrar el mejor plan de distribución, es decir, la cantidad que se debe enviar por cada una de las rutas desde los puntos de suministro hasta los puntos de demanda.
  • El “mejor plan” es aquel que minimiza los costos totales de envío, produzca la mayor ganancia u optimice algún objetivo corporativo.
  • Se debe contar con:
  • Nivel de oferta en cada fuente y la cantidad de demanda en cada destino.
  • ii) Costo de transporte unitario de mercadería desde cada fuente a cada destino.
  • También es necesario satisfacer ciertas restricciones:
  • 1. No enviar más de la capacidad especificada desde cada punto de suministro (oferta).
  • 2. Enviar bienes solamente por las rutas válidas.
  • 3. Cumplir (o exceder) los requerimientos de bienes en los puntos de demanda.
  • 2.1 Modelo de Transporte
  • 2.1 Modelo de Transporte
  • Esquemáticamente se podría ver como se muestra en la siguiente figura
  • Destinos
  • Fuentes
  • 1
  • 1
  • 2
  • 2
  • n
  • m
  • Unidades de demanda
  • Unidades de oferta
  • s2
  • sm
  • d2
  • s1
  • d1
  • dn
  • .
  • .
  • .
  • .
  • .
  • .
  • C11, X11
  • Cmn, Xmn
  • Cij: Costo del transporte unitario desde la fuente i al destino j
  • donde
  • Gráficamente: Para m fuentes y n destinos



Compartir con tus amigos:
1   2   3   4   5   6   7   8   9   ...   22


La base de datos está protegida por derechos de autor ©absta.info 2019
enviar mensaje

    Página principal