• Author / Uploaded
• adolfim

Citation preview

Excelencia en Educación y Entrenamiento

TEMA No. 2

PROGRAMACION LINEAL ENTERA, DUAL Y ANALISIS DE SENSIBILIDAD 1.- PROGRAMACION ENTERA 1.1.- Definición Un programa entero es un programa lineal con la condición oculta adicional de: QUE TODAS LAS VARIABLES SEAN ENTERAS Es decir, que las variables sean:

Xi ≥ 0 Y ENTERO 1.2.- Métodos de solución 1.2.1.- Algoritmo de Bifurcación Uno de los métodos para lograr la solución de programas lineales enteros es el Algoritmo de Bifurcación, que aplica el siguiente procedimiento: a) Haciendo la abstracción de la condición de entero, resuélvase el programa lineal a través del método simplex y hállese los valores óptimos de las variables. Esta solución constituirá la primera aproximación al resultado final de la optimización. b) De las variables obtenidas, elíjase aquella cuyo valor se aleje más de ser una unidad entera. Ejemplo: X1 = 3,4

- Entero más próximo es 3, y está a 4 décimas de este entero

X2 = 3,6

- Entero más próximo es 4, y está a 4 décimas de este entero Se elige cualquiera de las variables

Ejemplo: X1 = 2,3

- Entero más próximo es 2, y está a 3 décimas de este entero

X2 = 6,4

- Entero más próximo es 6, y está a 4 décimas de este entero

X3 = 1,5

- Entero más próximo es 1, y está a 5 décimas de este entero Se elige la variable X3

MSc Javier Ávila Vera

-

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

1

Excelencia en Educación y Entrenamiento

c) Una vez elegida la variable Xj, colóquese a éste en un intérvalo de dos números enteros (t1, t2) consecutivos más próximos, y proceda a expresar dicha variable como una restricción doble y permita que su condición sea menor a t1 y mayor a t2, es decir:

t1

t2

XXXXXXXXXX

XXXXXXXXXX Xj

Donde t1 y t2 son números enteros. Por tanto:

t2

≤ Xj

≤

t1

d) Establecer las nuevas restricciones, añadiendo cada una de ellas por separado al programa lineal original e inmediatamente proceda nuevamente a resolver por el método simplex. e) Repetir todo el procedimiento anterior las veces que sea necesario en todos los programas lineales que se generen, hasta encontrar la solución final. Ejemplo:

MSc Javier Ávila Vera

-

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

2

Excelencia en Educación y Entrenamiento

MSc Javier Ávila Vera

-

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

3

Excelencia en Educación y Entrenamiento

MSc Javier Ávila Vera

-

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

4

Excelencia en Educación y Entrenamiento

1.2.2.- Algoritmo de Corte Es otro de los métodos que nos permite eliminar los decimales y hallar la condición de entero. El procedimiento de aplicación es el siguiente: a) Encuéntrese la primera aproximación, haciéndose la abstracción de la condición entera. b) Selecciónese cualquiera de las filas de la matriz A de la solución básica final, expresando la misma como una igualdad. c) Re - escríbase cada coeficiente de las variables y la constante fraccionario de la ecuación seleccionada como la suma algebraica de un entero y una fracción positiva entre cero y uno. d) Escríbase en la izquierda de la igualdad todos los términos fraccionarios, y en la parte derecha todos los términos enteros. e) Deséchese la parte entera y hágase la parte fraccionaria en MAYOR O IGUAL a cero. f)

La inecuación encontrada constituye la nueva restricción que debe ser añadida al programa original.

g) Resuélvase el nuevo programa lineal definido. h) Aplicar todo el procedimiento anterior hasta encontrar solución optima final del programa lineal. Ejemplo:

MSc Javier Ávila Vera

-

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

5

Excelencia en Educación y Entrenamiento

MSc Javier Ávila Vera

-

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

6

Excelencia en Educación y Entrenamiento

2.- DUALIDAD 2.1.- Definición Una programación lineal está formado por variables X1, X2, X3, DDD, Xn, a este programa PRIMARIO le corresponde otro programa lineal llamado DUAL formado por las variables W 1, W2, W3, DDD, Wm.

2.2.- Tipos de dualidad 2.2.1.- Duales simétricos PROGRAMA PRIMARIO

PROGRAMA DUAL

t

t

MAX (Z) = C X

Si

MIN (Z) = B W t

A X ≤ B

A W ≥ C

Xi ≥ 0

Wj ≥ 0

NOTA.-

a) Todas las restricciones deben ser ≤ o ≥. b) Cuando todas las restricciones son ≤ En el programa primario se puede leer los resultados de su programa dual, esto se realiza observando los datos en la fila Zj – Cj y de la siguiente manera:
Variables de decisión del dual por debajo de las VARIABLES DE HOLGURA del primario y de izquierda a derecha.
Variables superfluas del dual por debajo de las VARIABLES DE DECISION del primario y de izquierda a derecha. c) Cuando todas las restricciones son ≥. En el programa primario se puede leer los resultados de su programa dual, esto se realiza observando los datos en la fila Cj – Zj y de la siguiente manera:
Variables de decisión del dual por debajo de las VARIABLES SUPERFLUAS del primario y de izquierda a derecha.
Variables de holgura del dual por debajo de las VARIABLES DE DECISION del primario y de izquierda a derecha.

MSc Javier Ávila Vera

-

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

7

Excelencia en Educación y Entrenamiento

Ejemplo: Si tenemos el siguiente programa primario:

a) Determinar la función objetivo, requerimientos y condiciones ocultas de su programa dual. b) Resolver por el método simplex el programa primario y en él encontrar los resultados tanto del programa primario como del dual. c) Resolver por el método simplex el programa dual y en él encontrar los resultados tanto del programa dual como del primario.

MSc Javier Ávila Vera

-

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

8

Excelencia en Educación y Entrenamiento

MSc Javier Ávila Vera

-

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

9

Excelencia en Educación y Entrenamiento

2.2.2.- Duales asimétricos TIPO A PROGRAMA PRIMARIO

PROGRAMA DUAL

t

t

MAX (Z) = C X

Si

MIN (Z) = B W t

A X = B

A W ≥ C

Xi ≥ 0

Wj ≥ 0

TIPO B PROGRAMA PRIMARIO

PROGRAMA DUAL

t

t

MIN (Z) = C X

Si

MAX (Z) = B W t

A X = B

A W ≤ C

Xi ≥ 0

Wj ≥ 0

NOTA.a) Restricciones son “═” Cuando se resuelve un programa primario con restricción exclusivamente compuesto por el signo “═”, entonces para determinar los resultados de su dual se procede de la siguiente manera:
Variables de decisión del dual: Logrando los resultados de la matriz: t

-1

W = Co Ao
Variables de holgura del dual, se realiza observando los datos en la fila Cj – Zj y por debajo de las VARIABLES DE DECISION del programa primario. MSc Javier Ávila Vera

-

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

10

Excelencia en Educación y Entrenamiento

Ejemplo: Si tenemos el siguiente programa primario:

a) Determinar la función objetivo, restricciones y condiciones ocultas de su programa dual. b) Resolver por el método simplex el programa primario y en él encontrar los resultados tanto de su programa primario como del dual. c) Resolver por el método simplex el programa dual y en él encontrar los resultados tanto del de su programa dual como del primario.

MSc Javier Ávila Vera

-

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

11

Excelencia en Educación y Entrenamiento

MSc Javier Ávila Vera

-

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

12

Excelencia en Educación y Entrenamiento

2.3.- Interpretación económica de las variables duales Las variables Wj, representan el valor económico por unidad del recurso i (donde i ═ 1m en la programación lineal). Estas variables también son conocidas con el nombre técnico de precios duales o precios sombra, variable que se define como la ganancia que se obtiene debido al incremento de una unidad de dicho recurso. Ejemplo: Una empresa produce radios y televisores pequeños; cada radio se vende con una utilidad de Bs. 300 y cada televisor gana Bs. 500; ambos deben pasar secuencialmente por los departamentos de impresión de circuitos (A) y ensamble (B). Semanalmente se dispone de 200 y 140 HorasHombre en los departamentos A y B respectivamente. Cada radio requiere de 1 hora-hombre del departamento A y 1 hora-hombre del departamento B; y, cada televisor requiere 2 Horas-hombre del departamento A y 1 Hora-hombre del departamento B. Hallar la solución del programa lineal primal y dual e interpretar económicamente sus resultados. Solución:

MSc Javier Ávila Vera

-

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

13

Excelencia en Educación y Entrenamiento

3.- ANALISIS DE SENSIBILIDAD 3.1.- Definición El análisis de sensibilidad define como resolver la optimización frente a los cambios en la solución básica final de un Programa Lineal, debido a los cambios en los datos originales del problema, como ser los recursos disponibles, coeficientes de las variables de la función objetivo y/o la cantidad utilizada para producir una unidad de un producto dado. Es importante señalar que el análisis de sensibilidad convierte la solución estática del Programa Lineal en un instrumento dinámico que evalúa las condiciones cambiantes de un problema; por tanto, adquiere mayor utilidad como instrumento administrativo, pues, los negocios están sometidos a cambios permanentes. Dado que al final del curso utilizaremos el QSB como instrumento para la optimización de programas lineal, es que sólo nos limitaremos a analizar el caso de las variaciones de los recursos disponibles.

3.2.- Cambios que afectan los recursos disponibles Es el caso en el que se hacen cambios específicos discretos en uno o más de los elementos de la matriz "B", con éstos incrementos, el único cambio que tendrá lugar en la tabla simplex óptimo, es el lado derecho de las restricciones y el valor de la función objetivo. Para calcular los nuevos valores de la solución básica final y el valor óptimo de la función objetivo, con los cambios producidos en los recursos disponibles, se sigue los siguientes pasos: 1.- Introducimos los cambios en la Matriz B

B1 = Esta se genera con los cambios introducidos en los recursos que contiene la matriz B 2.- Calculamos los nuevos valores de la Solución Básica Final -1

XSBF

CSBF= A B1

3.- Determinamos el nuevo valor óptimo de la Función Objetivo -1

Optimización (Z) =

MSc Javier Ávila Vera

-

CSBFA B1

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

14

Excelencia en Educación y Entrenamiento

Ejemplo Si previamente está optimizado por el método Simplex el programa lineal siguiente:

Determinar los valores de las variables de la Solución básica final y la función objetivo, si se incrementan los valores de la matriz "B" en un 50%. Solución

MSc Javier Ávila Vera

-

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

15

Excelencia en Educación y Entrenamiento

Ejemplo Barbie S.r.l. ensambla tres tipos de juguetes: Trenes, camiones y automóviles, utilizando tres operaciones. Los límites diarios sobre los tiempos disponibles para las tres operaciones son 430, 460 y 420 minutos respectivamente y, las utilidades por cada tren, camión y automóvil son 3, 2, y 5 $ respectivamente. Los tiempos de ensamble por tren en las tres operaciones son de 1, 3 y 1 minuto respectivamente. Los tiempos correspondientes por camión y por automóvil son (2, 0,4) y (1, 2, 0) minutos. Determinar a) La solución óptima del programa lineal primario y dual. b) El costo unitario de los recursos y el costo total que la empresa deberá pagar si alquila las tres operaciones en una organización similar a ella. c) La nueva solución óptima del programa lineal si la empresa incrementa un 20% los tiempos disponibles diarios. Adicionalmente determinar el costo unitario de los recursos, el Costo Total que la empresa deberá pagar si alquila las tres operaciones en una organización similar a ella Solución

MSc Javier Ávila Vera

-

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

16

Excelencia en Educación y Entrenamiento

MSc Javier Ávila Vera

-

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

17

Excelencia en Educación y Entrenamiento

Ejemplo La empresa Rivera Ltda. fabrica bolsos, estuches para afeitar y mochilas. La fabricación de los tres productos requiere piel y material sintético, siendo la piel la materia prima limitante. El proceso de fabricación utiliza dos tipos de mano de obra calificada: costura y acabado. La siguiente tabla proporciona la disponibilidad de los recursos, su utilización en los tres productos y las utilidades por unidad. Requerimientos de recursos por unidad Bolso Mochila Estuche para afeitar

Recurso

Disponibilidad diaria

Piel (pies2)

2

1

3

42

Costura (horas)

2

1

2

40

Acabado (horas)

1

0.5

1

45

Precio de Venta (bolivianos)

24

22

45

a) b) c) d)

Formule el problema como un programa lineal y encuentre la solución óptima Encuentre la nueva solución óptima si la piel disponible se incrementa a 45 pies2 Encuentre la nueva solución si las horas de acabado disponibles se disminuyen en 10 horas. Se recomendaría la contratación de un trabajador adicional de costura.

Solución

MSc Javier Ávila Vera

-

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

18

Excelencia en Educación y Entrenamiento

MSc Javier Ávila Vera

-

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

19

Excelencia en Educación y Entrenamiento

Ejemplo Diplomat Ltda. fabrica camisas para caballeros y blusas para dama destinado al personal de la Empresa de Telecomunicaciones ENTEL S.A.; esta ultima aceptara toda la producción semanal que le proporcione la fábrica. El proceso de producción incluye el corte, costura y empacado. Diplomat Ltda. Emplea en el área operativa a 25 trabajadores en el Departamento de Corte, 35 en el Departamento de Costura y 5 en el Departamento de Empacado. La fábrica trabaja un turno de 8 hrs al día y 5 días a la semana. La siguiente tabla proporciona los requerimientos de tiempo y las utilidades por unidad para las dos prendas:

PRENDA

Minutos que se requieren por unidad CORTE COSTURA EMPACADO

UTILIDAD POR UNIDAD Bs/u

CAMISAS

20

70

12

12,5

B.LUSAS

60

60

4

13,2

a) Determinar el programa de producción semanal optimo para Diplomat Ltda. b) Determine el valor por hora de los procesos de corte, costura y empacado

MSc Javier Ávila Vera

-

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

20

Excelencia en Educación y Entrenamiento

MSc Javier Ávila Vera

-

Investigación Operativa

-

Administración de Empresas/U.M.S.A.

21