Investigacion de Operaciones

ICM02246 Investigación de Operaciones (Audit.)Ingeniería en Auditoría y Contaduría Pública Autorizada

Periodo Académico 2016 - 1° Semestre

Instructor: Alfredo Armijos, PMP®, PMI-RMP®, M.Sc.

Agenda de Inducción

• Soluciones Óptimas Múltiples

• Método Símplex para Maximización

• Método Símplex para Minimización

• Solución Artificial de Inicio

• Próxima Semana

Soluciones Óptimas MúltiplesAlgunas veces una función objetivo alcanza su valor óptimo en más de un puntofactible, en cuyo caso se dice que existen soluciones óptimas múltiples.

Soluciones Óptimas Múltiples

Maximice Z = 2x + 4y sujeta a las siguientes restricciones:

x - 4y ≤ - 8x + 2y ≤ 16

x ≥ 0y ≥ 0

Solución:

La región factible aparece en la figuradetallada a continuación. Como la región noesta vacía y es acotada, Z tiene valor máximoen un vértice. Los vértices son:

A = (0,2) B = (8,4) C = (0,8)

Entonces se obtiene que:

Z (A) = 2(0) + 4(2) = 8Z (B) = 2(8) + 4(4) = 32Z (C) = 2(0) + 4(8) = 32

Soluciones Óptimas Múltiples

Maximice Z = 2x + 4y sujeta a las siguientes restricciones:

x - 4y ≤ - 8x + 2y ≤ 16

x ≥ 0y ≥ 0Solución:

Así el valor máximo de Z sobre la región es 32 yocurre en 2 vértices, B y C. De hecho, este valormáximo también ocurre en todos los puntossobre el segmento 𝐵𝐶 por la razón detallada acontinuación:

Cada miembro de la familia de rectas Z = 2X + 4ytiene pendiente de -1/2. Además la recta de larestricción X + 2y = 16, que contiene a B y Ctambién tiene pendiente de -1/2, y de aquí quesea paralela a cada miembro de Z = 2X + 4Y.

Soluciones Óptimas MúltiplesDe aquí que este problema de programación lineal tenga un número infinito desoluciones óptimas. De hecho, puede mostrarse que.

En este caso, si (x1,y1) = B = (8,4) y (x2,y2) = C = (0,8), entonces Z es máximo en cualquierpunto, donde:

x = (1-t)8 + t(0) = 8(1-t)

y = (1-t)4 + t(8) = 4(1-t)

para 0 ≤ t ≤ 1

Introducción al Método SímplexHasta ahora se han resuelto problemas de PL por un método geométrico; el cual no espráctico cuando el número de variables aumenta a tres y, desde luego, es imposibleusarlo si las variables son más de tres. Ahora se verá una técnica diferente, el MétodoSímplex, cuyo nombre está ligado, en estudios más avanzados, a un objeto geométricoal que se denomina simple (símplex).

El Método Símplex empieza con una solución factible y la pone a prueba para descubrirsi es óptima o no. Si no lo es, se procede a obtener una mejor solución. Se dice “mejor”en el sentido de que la nueva solución esté más cerca de la optimización de la funciónobjetivo. Si no es óptima, entonces se repite el procedimiento. En algún momento elMétodo Simplex conduce a una solución óptima, si es que existe.

Además de ser eficiente, el Método Símplex tiene otras ventajas:• Es completamente mecánico (se usan matrices, operaciones elementales con

renglones y aritmética básica).• No es necesario dibujar gráficas; lo que permite resolver problemas de programación

lineal con cualquier número de restricciones y variables.

Introducción al Método SímplexEn esta sección del curso se considerarán solo los llamados problemas estándar deprogramación lineal, que pueden expresarse en la siguiente forma:

Para estandarizar, la representación algebraica del espacio de soluciones de PL seforma bajo dos condiciones:• Todas las restricciones (excepto las de no negatividad) son ecuaciones con lado

derecho no negativo• Todas las variables de decisión son no negativas

Transición de Solución Gráfica a AlgebraicaLas ideas contenidas en la solución gráfica de un modelo de programación lineal son labase para desarrollar el método algebraico símplex. La figura detallada a continuaciónmarca el paralelismo entre los dos métodos: gráfico y algebraico (símplex)

Procedimiento del Método SimplexLos pasos del Método Simplex se detallan a continuación:

Paso 0. Determinar una solución básica factible de inicio (SBF)

Paso 1. Seleccionar la variable de entrada aplicando la condición de optimalidad.Detenerse si no hay variable de entrada; la última solución es la óptima

Paso 2. Seleccionar una variable de salida aplicando la condición de factibilidad

Paso 3. Determinar la nueva solución básica con los cálculos adecuados de Gauss-Jordan. Ir al Paso 1.

Procedimiento del Método SimplexLas reglas para seleccionar las variables de entrada y salida se denominan condicionesde optimalidad y de factibilidad:

[Texto]Condición de Optimalidad: La variable de entrada en unproblema de maximización (minimización) es la variableno básica que tenga el coeficiente más negativo (positivo)en el renglón de Z. Los empates se rompen en formaarbitraria. Se llega al óptimo en la iteración en la que losdos coeficientes de las variables no básicas en el renglón Zson no negativos (no positivos).

Condición de Factibilidad: En los problemas demaximización y de minimización, la variable de salida es lavariable básica asociada con la mínima razón no negativa(con denominador estrictamente positivo). Los empates serompen de forma arbitraria

Ejercicio de Aplicación No.1La compañía Pinturas Condor produce pinturas para interiores y exteriores, M1 y M2. Lasiguiente tabla proporciona los datos básicos del problema.

Toneladas de Materia Prima

Elementos Pinturas Exteriores Pinturas Interiores Disp. Diaria Max.

Materia Prima, M1 6 4 24

Materia Prima, M2 1 2 6

Utilidad/Tonelada 5 4 (Miles de $)

Una encuesta de mercado indica que la demanda diaria de pintura para interiores nopuede ser mayor que 1 tonelada más que la de pintura para exteriores. También, que lademanda diaria de pintura para interiores es de 2 toneladas.

Pinturas Condor desea hallar la mezcla óptima (la mejor) de productos para exteriores ypara interiores con el propósito fundamental de maximizar la utilidad diaria total.Determine la función objetivo y restricciones a satisfacer en el problema.

Aplicación del Método Gráfico

Solución Gráfica:

Aplicación del Método Simplex

Solución:

Las variables s1, s2, s3 y s4 son las holguras asociadas con las restricciones respectivas. Acontinuación la función objetivo se la define como:

Aplicación del Método SimplexSolución:

De esta manera la tabla inicial del Método Simplex se representa como sigue:

El diseño de la tabla provee automáticamente la solución en la iteración inicial. Lasolución parte en el origen (x1,x2) = (0,0), por lo que (x1,x2) se definen como lasvariables no básicas y (s1,s2,s3,s4) como las variables básicas.

La variable objetivo Z y las variables básicas aparecen en la columna de la extremaizquierda (Básica). Los lados derechos de las ecuaciones del modelo dan sus valores,como se muestra en la columna de la extrema derecha (Solución) de la tabla.

Aplicación del Método SimplexIteración No.1:

Aplicación del Método SimplexIteración No.2:

Aplicación del Método SimplexResultados:

La solución también da el estado de los recursos. Un recurso se designa como escaso sila variable de holgura asociada es cero, es decir, las actividades (variables) del modeloconsumieron el recurso por completo. De lo contrario si la holgura es positiva, entoncesel recurso es abundante.

Ejercicio de Aplicación No.2Dos empresas mineras extraen dos tipos diferentes de minerales especiales, los cualesson sometidos a un proceso de trituración, con tres grados: alto, medio y bajo. Lasmineras han firmado un contrato en Ecuador para proveer de mineral a una planta defunción en Zaruma, cada semana, 12 toneladas de mineral de grado alto, 8 toneladas degrado medio y 24 toneladas de grado bajo, cada una de las empresas tiene diferentesprocesos de fabricación.

Empresas Mineras

Costo/Día (Miles de $)

Producción (Tonelada/Día)

Alto Medio Bajo

X 180 6 3 4

Y 160 1 1 6

¿Cuántos días a la semana debería operar cada empresa para cumplir el contrato con laplanta de función?

Ejercicio de Aplicación No.2Solución:

Minimizar 𝑧 = 180𝑥1 + 160𝑥1

6x1+ x2 ≥ 123x1+ x2 ≥ 8

4x1+ 6x2 ≥ 24x1,x2≥0

6x1+ x2 + 𝑠1 = 123x1+ x2 + 𝑠2 = 8

4x1+ 6x2 + 𝑠3 = 24x1,x2, 𝑠1, 𝑠2, 𝑠3 ≥ 0

Las variables s1, s2, y s3 son las holguras asociadas con las restricciones respectivas. Acontinuación la función objetivo se la define como:

Redefiniendo el problema en función de holguras tenemos que:

z − 180x1 − 160x2 = 0

Ejercicio de Aplicación No.2Solución:

Básica z 𝑥1 𝑥2 𝑠𝟏 𝑠𝟐 𝑠𝟑 Solución Filas

z 1 -180 -160 0 0 0 0 Fila z

𝑠𝟏 0 6 1 1 0 0 12 Fila 𝑠𝟏

𝑠𝟐 0 3 1 0 1 0 8 Fila 𝑠𝟐

𝑠𝟑 0 4 6 0 0 1 24 Fila 𝑠𝟑

Iteración 1:


z 1 -180 -160 0 0 0 0 Fila z

𝑠𝟏 0 6 1 1 0 0 12 Fila 𝑠𝟏

𝑠𝟐 0 3 1 0 1 0 8 Fila 𝑠𝟐

𝑠𝟑 0 4 6 0 0 1 24 Fila 𝑠𝟑

Ejercicio de Aplicación No.2


z 1 0 -130 30 0 0 360 Fila z

𝑥1 0 1 1/6 1/6 0 0 2 Fila 𝑥𝟏

𝑠𝟐 0 0 1/2 -1/2 1 0 2 Fila 𝑠𝟐

𝑠𝟑 0 0 16/3 -2/3 0 1 16 Fila 𝑠𝟑

Resultados Iteración 1:

Resultados Iteración 2:


z 1 0 0 55/4 0 195/8 750 Fila z

𝑥1 0 1 0 3/16 0 -1/32 3/2 Fila 𝑥𝟏

𝑠𝟐 0 0 0 -7/16 1 -3/32 1/2 Fila 𝑠𝟐

𝑥2 0 0 1 -1/8 0 3/16 3 Fila 𝑥𝟐

Solución Artificial InicialComo se ha evidenciado en ejercicios anteriores, los problemas de PL en las que todaslas restricciones son (≤) con lados derechos no negativos ofrecen una convenientesolución factible básica inicial con todas las holguras. Los modelos que implicanrestricciones (=) o (≥) no lo hacen.

El procedimiento para dar resolución a problemas de PL de “mal comportamiento” conrestricciones (=) o (≥) consiste en adoptar variables artificiales que desempeñan el papelde holguras en la primera iteración, y que luego se desechan en una iteración posterior.Para ello, existen dos métodos estrechamente relacionados tales como:

Método MMétodo de Dos

Fases

Método MEl Método M se inicial con la programación lineal en forma de ecuación. Si dichaecuación i no posee holgura (o una variable que pueda desempeñar el papel de una), seagrega una variable artificial, Ri, para formar una solución inicial parecida a la soluciónbásica de total holgura.

Sin embargo, las variables artificiales no forman parte del problema original, y serequiere de un “artificio” de modelado para igualarlas a cero en el momento en que sealcance la iteración óptima (suponiendo que el problema tenga una solución factible).La meta deseada se logra penalizando estas variables en la función objetivo utilizando:

Aplicación del Método M

Si utilizamos 𝑥3 como variable de superávit en la segunda restricción y 𝑥4 como variablede holgura en la tercera restricción, el problema en forma de ecuación es

Aplicación del Método MLa tercera ecuación tiene sus variable de holgura, 𝑥4, pero la primera y segundaecuaciones no. Por lo tanto, agregamos las variables artificiales 𝑅1 y 𝑅2 en las primerasdos ecuaciones y las penalizamos en la función objetivo con 𝑀𝑅1+ 𝑀𝑅2 (porqueestamos minimizando). El problema de PL resultante se da como:

La solución básica inicial es (R1, R2, 𝑥4) = (3,6,4)

Aplicación del Método MUtilizando M = 100, la tabla Símplex de inicio se da como sigue (por comodidad, lacolumna z se elimina porque no cambia en todas las iteraciones)

Antes de proseguir con los cálculos del Método Símplex, el renglón z debe hacerseconsistente con el resto de la tabla. El lado derecho de la fila z en la tabla en estemomento muestra z = 0. Sin embargo, dada la solución no básica 𝑥1= 𝑥2= 𝑥3= 0, lasolución básica actual es 𝑅1=3, 𝑅2=6 y 𝑥4=4, la cual da como z = 100 x 3 + 100 x 6 + 4 x 0= 900. Esta inconsistencia se deriva del hecho de que los coeficientes de 𝑅1 y 𝑅2 no soncero (-100,-100) en la fila z.

Aplicación del Método MPara eliminar la inconsistencia, tenemos que sustituir 𝑅1 y 𝑅2 en la fila z por medio de lasiguiente operación de filas:

Nueva fila z = Anterior fila z + (100 x fila 𝑹𝟏 x fila 𝑹𝟐)

El resultado es que 𝑅1 y 𝑅2 ahora se sustituyen (tienen coeficientes cero) en fila z con z =900, como se deseaba. Por condición de factibilidad y optimalidad, la tabla modificada es:

Dado que la función objetivo se minimiza, la variable 𝑥1 que tiene el coeficiente máspositivo en la fila z (696) entra en la solución. La relación mínima de la condición defactibilidad declara a 𝑅1 como la variable de salida.

Aplicación del Método MEn la segunda iteración, dado que la función objetivo se minimiza, la variable 𝑥2 quecontiene el coeficiente más positivo en la fila z (167) entra en la solución. La relaciónmínima de la condición de factibilidad declara a 𝑅2 como la variable de salida, teniendocomo resultado la siguiente tabla.

Una vez que se han determinado las variables de entrada y salida, la nueva tabla se calculautilizando las conocidas operaciones de Gauss Jordan. El objetivo principal es que dentrodel renglón z las variables no básicas queden en cero y el resto de variables en estadonegativo (dado que es un problema de minimización)

Aplicación del Método MLa tabla demuestra que 𝑥1 y 𝑅2 son las variables de entrada y salida, respectivamente.Continuando con los cálculos del Método Simplex, se requieren 2 iteracionesadicionales para alcanzar el óptimo 𝑥1= 2/5, 𝑥2= 9/5, z = 17/5

Método de Dos FasesEn el Método M, el uso de la penalización, M, puede conducir a un error de redondeo. ElMétodo de Dos Fases elimina el uso de la constante M. Como su nombre lo indica, elmétodo resuelve el problema de PL en dos fases; en la fase I, se trata de encontrar lasolución factible básica inicial y, si se halla una, se invoca la fase II para resolver elproblema original.

Fase No.1

• Ponga el problema en forma de ecuación y agregue las variables artificiales necesarias a lasrestricciones (exactamente como en el método M), para tener la certeza de una solución básica. Acontinuación, determine una solución básica de la ecuación resultante que siempre minimice lasuma de las variables artificiales, independientemente de si la PL es un problema de maximizacióno minimización. Si el valor mínimo de la suma es positivo, el problema de PL no tiene una soluciónfactible. De lo contrario, si el valor mínimo es cero, prosiga con la fase II.

Fase No.2

• Use la solución factible de la Fase I como una solución factible básica inicial para el problemaoriginal.

Aplicación del Método de Dos Fases

Si utilizamos 𝑥3 como variable de superávit en la segunda restricción y 𝑥4 como variablede holgura en la tercera restricción, el problema en forma de ecuación es:

Fase No. 1:

Aplicación del Método de Dos FasesLa tabla asociada para posterior ejecución del Método Simplex es:

Como en el Método M, 𝑅1 y 𝑅2 se sustituyen en la fila r mediante las siguientesoperaciones de filas

Nueva fila r = Anterior fila r + (1 x fila 𝑹𝟏 x fila 𝑹𝟐)

Aplicación del Método de Dos Fases

Aplicación del Método de Dos FasesComo el mínimo r = 0, la Fase No. 1 produce la solución factible básica 𝑥1= 3/5, 𝑥2= 6/5 y𝑥4= 1. En este punto, las variables artificiales ya completaron su misión, y podemoseliminar sus columnas de la tabla y continuar con la Fase No. 2.

Fase No.2:

Después de eliminar las columnas artificiales, escribimos el problema original como:

Aplicación del Método de Dos FasesEn esencia, la Fase No.1 ha transformado las ecuaciones de restricciones originales detal forma que proporciona una solución básica inicial para el problema, si es que existeuna. La tabla asociada con la Fase No.2 del problema es por consiguiente:

Una vez más, como las variables básicas 𝑥1 y 𝑥2 tienen coeficientes diferentes a cero enla fila z, deben ser sustituidas mediante las siguientes operaciones:

Nueva fila z = Anterior fila z + (4 x fila 𝒙𝟏 + 1 x fila 𝒙𝟐)

Aplicación del Método de Dos FasesLa tabla inicial de la Fase No.2 es por consiguiente:

Como estamos minimizando, 𝑥3 debe entrar en la solución. La aplicación del MétodoSimplex producirá el óptimo en una iteración.

Taller de Solución ArtificialLa compañía Pronaca consume de forma diaria un mínimo de 800 lb de un alimentoespecial, el cual es una mezcla de maíz y soya con las siguientes composiciones.

Libras por Libras de Forraje

Forraje Proteína Fibra Costo ($/Libra)

Maíz 6 4 24

Soya 1 2 6

Las necesidades dietéticas del alimento especial son un mínimo de 30% de proteína yun máximo de 5% de fibra. El objetivo es determinar la mezcla diaria de alimento a uncosto mínimo.

Determinar la función objetivo, restricciones y hallar la mezcla diaria óptima mediante:

• Método Gráfico• Método Simplex - Dos Fases


Solución Gráfica:



Aplicación del Método Símplex







Todo por hoy futuros

IACPA!

Próxima Clase:

1. Casos Especiales en el Método Símplex• Degeneración• Óptimos Alternativos• Soluciones No Acotadas• Soluciones No Factibles

Un Excelente Fin de Semana!!!

“En un mundo que cambia muy rápido, la única estrategia que garantiza fallar es no correr riesgos.”

Mark Zuckerberg, 2011

Documents

Investigacion de Operaciones