trabajo io finish

|

2012INVESTIGACION OPERATIVA I

AÑO DE LA CONSOLIDACIÓN NACIONAL Y EL RECONOCIMIENTO DE NUESTRA

DIVERSIDAD

INVESTIGACION OPERATIVA I

“AÑO DE LA CONSOLIDACION NACIONAL Y EL

RECONOCIMIENTO DE NUESTRA BIODIVERSIDAD”

FACULTAD DE INGENIERÍA

Escuela Académico Profesional Ingeniería Informática

HUACHO – PERU2012

|


TEMA:

MANUAL DE INVESTIGACION OPERATIVA

CURSO:

INVESTIGACION OPERATIVA I

PROFESOR:

MG. PEREZ RAMIREZ, José Luis

INTEGRANTES:

BLANCO DEL CASTILLO, Raúl Marlon

VEGA ESPICHAN, Paula Alicia

Índice

Dedicatoria…..…………………………………..…………………………………..…2

Introducción………………………………………………..………………………….3

CAPITULO 1: Definición Y Aplicación De Investigación de Operaciones

Investigación de operaciones……………………….…………………….…9

Toma de decisiones……………………………….………………………….9

CAPITULO 2: Introducción y Formulación de Modelos

Introducción de Modelos………………………………………………….11

Modelo de múltiples periodos………………………………………………14

Modelo Financieros de Múltiples Periodos………………….…………..16

Problema de Alimentación………………………………………..………..18

Problema de establecimiento horario……………………………………..22

Modelo de proceso de producción……………………………….………..25

Problema de Mezclas………………………………………………………..30

CAPITULO 3: Método Grafico

Método Grafico…………………………………………………….………..38

CAPITULO 4: Método Simplex

Método Simplex………………………………………………………………45

Maximización……………………………………………………….……….45

Minimización……………………………………………………….………..64

|


CAPITULO 5: Método Dos Fases

Método dos Fases……………………………………………………….…..71

CAPITULO 6: Método Dual Simplex

Método dual simplex…………………………………………………………87

CAPITULO 7: Análisis de Sensibilidad

Análisis de Sensibilidad……………………………………………………96

Inclusión de una nueva variable…………………………………………..96

Cambio De Un Coeficiente CJ, Cuando Una Variable Cj no Es Básica……97

Cambio De Un Coeficiente Cj Cuando Una Variable Xj Es Básica………….98

Cambios Que Afectan La Factibilidad……………………………..…….99

CAPITULO 8: Transporte y Transbordo

Problema de Transporte…………………………………………………102

Características de modelo de transporte…… …………….…102

aplicación de modelo de transporte…………………………….103

Algoritmo de modelo de transporte………………….…….…...106

Ejercicio de Aplicación……………………………………….…..107

Método de esquina noreste…………………………………....…110

Método de costo mínimo………………………………………....112

Método Vogel…………………………………………….….….....114

Método Russel………………………………………………….….116

Método de pasos secuenciales………………………….…..…..119

Método de Distribución modificado………………………..….124

Problema de Transbordo………………………………………….……..133

Definición…………………………………………………….……133

|


Características………………………………………….….…….134

Variantes de Problema de Transbordo………………………..134

Consideraciones………………………………………………..…135

Esquema de Transbordo…………………………………….….135

Ejercicio Aplicativo………………………………………….....136

CAPITULO 9: Asignación

Asignación…………………………………………………………….….…146

Situación……………………………………………………………….…….146

Descripción…………………………………………………………………146

Expresión matemática del modelo…………………………………….…147

Ejemplo de aplicación …………………………………………….…..….148

Método de solución…………………………………………………..….…149

Método Húngaro……………………………………………………….…..150

Modelo de asignación: otras consideraciones…………………..…….154

ofertas y demandas desiguales…………………………….……154

modelo de maximización………………………………..……..158

CAPITULO 10: Programación Lineal Entera Y Binaria

Programación entera……………………………………………………163

Algoritmo de ramificación y acotación……………………….…….…163

Algoritmo de Gomory………………………………………….………..167

Programación binaria…………………………………………………....171

Algoritmo de enumeración implícita cero-uno………………………...171

Problema binario (0_1) resuelto a través del algoritmo aditivo……..173

|


BIBLIOGRAFIA………………………………………………………………….174

|


DEDICATORIA:

|


Este trabajo se ha realizado con mucho esfuerzo al vez del agradecimiento por el apoyo que nos dan nuestros seres queridos que buscan que seamos grandes profesionales.

Introducción

Cuando una persona se enfrenta por vez primera con el término Investigación

de Operaciones, no suele ser conocedora de las características específicas de esta

ciencia ni de su objeto de estudio. Además, la Investigación Operativa puede tener

componentes muy diversos dependiendo de su área de aplicación concreta:

Administración de Empresas, Ingeniería u otras. El objeto de estudio de la Investigación

Operativa es la toma científica de decisiones mediante el empleo de técnicas

cuantitativas. Es importante tener esta definición clara y, de esta forma, nos daremos

cuenta de la amplitud de campo de la Investigación Operativa (IO).

Con demasiada frecuencia se ha hecho demasiado hincapié en los modelos de

Programación Lineal dentro de la Investigación Operativa, lo cual ha dificultado la

distinción entre ambos términos. Lo cierto es que la Programación Lineal es sólo una

parte de la Investigación Operativa aunque, sin duda, una de las más importantes.

Otras áreas o secciones habituales en el estudio de la IO son las siguientes (esta

relación no es exhaustiva, sino que sólo pretende dar una idea de la extensión de la IO):

Programación entera

Problemas de transporte

Análisis de grafos y de redes. PERT y CPM.

Programación dinámica

Teoría de juegos.

Programación no lineal.

Teoría de colas.

Teoría de inventarios

Procesos markovianos de decisión. Análisis de decisión.

Simulación

Fiabilidad

|


Existen, de este modo, otras áreas –además de la PL- en las que la Investigación

Operativa ejerce también su estudio. Es claro pues que la Investigación Operativa es

una ciencia multidisciplinar que aparece en muchos campos del ámbito industrial,

empresarial y de la administración pública. De hecho, con la aparición de la

Programación Lineal en los años 40, aparece el sentimiento de dar una cohesión o

visión de conjunto a todas las técnicas anteriormente enunciadas. Esa visión

cohesionada, junto con el concepto de sistema, permite la aparición de la Investigación

de Operaciones como ciencia.

Las subdivisiones en las que se establece la IO tienen los siguientes elementos en

común:

Son necesarios amplios conocimientos de matemáticas, es decir, del manejo de

muchas técnicas matemáticas, aunque con inmediata aplicación a la realidad.

Es necesario que, al final de cada problema definido, haya una decisión que

tomar.

Es preciso definir un modelo que dé cauce a la toma de decisiones.

En el estudio de la Investigación Operativa se puede hacer más énfasis en los

aspectos teóricos de los modelos matemáticos o bien en los aspectos prácticos.

Estudiar de forma exclusiva modelos matemáticos, aun siendo importante para la IO,

no constituye el principal ejercicio de la IO: es necesario verificar la aplicabilidad de los

resultados que se deriven de los modelos matemáticos.

|


La Investigación de Operaciones

Nos brinda herramientas cuantitativas para la toma de decisiones que resuelven los

problemas diarios de un negocio ó sirven para tomar decisiones en la planeación a corto o

largo plazo, sea el negocio de carácter gubernamental, de producción, de servicios, gremial ó

cooperativo. En la aplicación de la investigación de operaciones se aplican los siguientes seis

pasos metodológicos científicos a saber:

Análisis y definición del problema.

Desarrollo del modelo.

Selección de datos de entrada.

Obtención de una solución.

Limitaciones del modelo y la solución.

Utilización del modelo.

La investigación de operaciones se da con la finalidad de realizar de forma exhaustiva y

detallada un modelo para la toma de decisiones q debe tomar la empresa para ver si es

viable el proyecto de estudio.

La toma de decisiones

La toma de decisiones estratégicas para la vida de una empresa, es la principal

responsabilidad indelegable de un gerente. El inicio de la toma de una decisión,

generalmente empieza cuando se detecta un problema. Conocido el problema, el gerente

debe proceder a definirlo de manera clara y formular el objetivo, seguidamente identifica las

restricciones, evalúa las alternativas y seguramente el mejor curso de acción que lo llevará la

solución óptima. Este proceso lo realiza de manera cualitativa o cuantitativa. Si lo hace bajo

el enfoque cualitativo, el gerente está confiando en su juicio personal o en su experiencia

pasada en situaciones similares. Si lo hace bajo el enfoque cuantitativo, no necesariamente

debe tener experiencia en casos similares, pero si debe hacer un análisis exhaustivo,

especialmente si la decisión involucra una gran cantidad de dinero, un conjunto de variables

muy grande ó se trata de un problema altamente repetitivo, en cuyo caso, el desarrollo de un

procedimiento cuantitativo ahorrará tiempo valioso al gerente.

|


MODELOS

Para formular un problema de PL, recomiendo seguir los siguientes lineamientos generales después de leer con atención el enunciado del problema varias veces.

Todo programa lineal consta de cuatro partes: un conjunto de variables de decisión, los parámetros, la función objetivo y un conjunto de restricciones. Al formular un determinado problema de decisión en forma matemática, debe practicar la comprensión del problema (es decir, formular un Modelo Mental) leyendo detenidamente una y otra vez el enunciado del problema. Mientras trata de comprender el problema, formúlese las siguientes preguntas generales:

1. ¿Cuáles son las variables de decisión? Es decir, ¿cuáles con las entradas controlables? Defina las variables de decisión con precisión utilizando nombres descriptivos. Recuerde que las entradas controlables también se conocen como actividades controlables, variables de decisión y actividades de decisión.

|


2. Cuáles son los parámetros? Vale decir ¿cuáles son las entradas no controlables? Por lo general, son los valores numéricos constantes dados. Defina los parámetros con precisión utilizando nombres descriptivos.

3. ¿Cuál es el objetivo? ¿Cuál es la función objetivo? Es decir, ¿qué quiere el dueño del problema? ¿De qué manera se relaciona el objetivo con las variables de decisión del dueño del problema? ¿Es un problema de maximización o minimización? El objetivo debe representar la meta del decisor.

4. ¿Cuáles son las restricciones? Es decir, ¿qué requerimientos se deben cumplir? ¿Debería utilizar un tipo de restricción de desigualdad o igualdad? ¿Cuáles son las conexiones entre las variables? Escríbalas con palabras antes de volcarlas en forma matemática.

Recuerde que la región factible tiene poco o nada que ver con la función objetivo (minimizar o maximizar). Estas dos partes en cualquier formulación de PL generalmente provienen de dos fuentes distintas. La función objetivo se establece para cumplir con el deseo (objetivo) del decisor mientras que las restricciones que forman la región factible generalmente provienen del entorno del decisor que fija algunas limitaciones / condiciones para lograr su objetivo.

A continuación, se incluye un problema ilustrativo muy sencillo. Sin embargo, el abordaje del problema es igual para una gran variedad de problemas de toma de decisión, mientras que el tamaño o la complejidad pueden variar. El primer ejemplo es un problema de mix de productos y el segundo es un problema de mezcla.

El Problema del Carpintero

Durante un par de sesiones de tormenta de ideas con un carpintero (nuestro cliente), éste nos comunica que sólo fabrica mesas y sillas y que vende todas las mesas y las sillas que fabrica en un mercado. Sin embargo, no tiene un ingreso estable y desea optimizar esta situación.

El objetivo es determinar cuántas mesas y sillas debería fabricar para maximizar sus ingresos netos. Comenzamos concentrándonos en un horizonte de tiempo, es decir, un plazo de planificación, , para revisar nuestra solución semanalmente, si fuera necesario. Para saber más acerca de este problema, debemos ir al negocio del carpintero y observar lo que sucede y medir lo que necesitamos para para formular (para crear un modelo de) su problema. Debemos confirmar que su objetivo es maximizar sus ingresos netos. Debemos comunicarnos con el cliente.

El problema del carpintero se trata de determinar cuántas mesas y sillas debe fabricar por semana; pero primero se debe establecer una función objetivo La función objetivo es: 5X1 + 3X2, donde X1 y X2 representan la cantidad de mesas y sillas; y 5 y 3 representan los ingresos netos (por ejemplo, en dólares o décimas de dólares) de la venta de una mesa y una silla, respectivamente. Los factores limitantes, que normalmente provienen del exterior, son las limitaciones de la mano de obra (esta limitación proviene de la familia del carpintero) y los recursos de materia prima (esta limitación proviene de la entrega programada). Se miden los tiempos de producción requeridos para una mesa y una silla en distintos momentos del día y se calculan en 2 horas y 1 hora, respectivamente. Las horas

|


laborales totales por semana son sólo 40. La materia prima requerida para una mesa y una silla es de 1 y 2 unidades, respectivamente. El abastecimiento total de materia prima es de 50 unidades por semana. En consecuencia, la formulación de PL es la siguiente:

Maximizar 5 X1 + 3 X2

Sujeta a:

2 X1 + X2 40

restricción de mano de obra

X1 + 2 X2 50

restricción de materiales

tanto X1 como X2 son no negativas.

Este es un modelo matemático para el problema del carpintero. Las variables de decisión, es decir, las entradas controlables son X1, y X2. La salida o el resultado de este modelo son los ingresos netos totales 5 X1 + 3 X2. Todas las funciones empleadas en este modelo son lineales (las variables de decisión están elevadas a la primera potencia). El coeficiente de estas restricciones se denomina denomina Factores Tecnológicos (matriz). El período de revisión es de una semana, un período conveniente dentro del cual es menos probable que cambien (fluctúen) las entradas controlables (todos los parámetros tales como 5, 50, 2,..). Incluso en un plazo de planificación tan corto, debemos realizar el análisis what-if o de hipótesis para responder a cualquier cambio en estas entradas a los efectos de controlar el problema, es decir, actualizar la solución prescripta.

Nótese que dado que el Carpintero no va a ir a la quiebra al final del plazo de planificación, agregamos las condiciones que tanto X1 como X2 deben ser no negativas en lugar de los requerimientos que X1 y X2 deben ser números enteros positivos. Recuerde que las condiciones de no negatividad también se denominan "restricciones implícitas". Nuevamente, un Programa Lineal funcionaría bien para este problema si el Carpintero continúa fabricando estos productos. Los artículos parciales simplemente se contarían como trabajos en proceso y finalmente se transformarían en productos terminados, en la siguiente semana.

Podemos intentar resolver X1 y X2 enumerando posibles soluciones para cada una y seleccionado el par (X1, X2) que maximice 5X1 + 3X2 (los ingresos netos). Sin embargo, lleva mucho tiempo enumerar todas las alternativas posibles y si no se enumeran todas las alternativas, no podemos estar seguros de que el par seleccionado (como una solución) es la mejor de todas las alternativas. Otras metodologías preferidas (más eficientes y efectivas), conocidas como las Técnicas de Soluciones de Programación Lineal están disponibles en el mercado en más de 4000 paquetes de software de todo el mundo.

La solución óptima, es decir, la estrategia óptima, es establecer X1 = 10 mesas y X2 = 20 sillas. Programamos las actividades semanales del carpintero para que fabrique 10 mesas

|


y 20 sillas. Con esta estrategia (óptima), los ingresos netos son de US$110 Esta. Esta solución prescripta sorprendió al carpintero dado que debido a los mayores ingresos netos provenientes de la venta de una mesa (US$5), el solía fabricar más mesas que sillas.

¿Contratar o no contratar a un ayudante? Supóngase que el carpintero pudiera contratar a un ayudante a un costo de US$2 por hora (adicionales $2) ¿Le conviene al carpintero contratar a un ayudante? En caso afirmativo, ¿por cuántas horas?

X3 es la cantidad de horas extra, entonces el problema modificado es:

Maximizar 5 X1 + 3 X2 - 2 X3

Sujeta a:

2 X1 + X2 40 + X3 restricción de la mano de obra con horas adicionales desconocidas X1 + 2 X2 50 restricción de materiales

En esta nueva condición, veremos que la solución óptima es:

X1 = 50, X2 = 0, X3 = 60, con ingresos netos óptimos de US$130. Por lo tanto, el carpintero debería contratar a un ayudante por 60 horas. ¿Qué pasaría si sólo lo contrata por 40 horas? La respuesta a esta pregunta y a otros tipos de preguntas del estilo "qué pasaría si" (what-if) se estudia en la sección sobre análisis de sensibilidad en este sitio Web.

Un Problema de Mezcla

El taller LUBEOIL se especializa en cambios de aceite del motor y regulación del sistema eléctrico. El beneficio por cambio del aceite es $7 y de $15 por regulación Joe tiene un cliente fijo con cuya flota, le garantiza 30 cambios de aceite por semana. Cada cambio de aceite requiere de 20 minutos de trabajo y $8 de insumos. Una regulación toma una hora de trabajo y gasta $15 en insumos. LUBEOIL paga a los mecánicos $10 por hora de trabajo y emplea actualmente a dos de ellos, cada uno de los cuales labora 40 horas por semana. Las compras de insumos alcanzan un valor de $1.750 semanales. LUBEOIL desea maximizar el beneficio total. Formule el problema.

Esto es una pregunta de programación linear. Una porción de un cambio del aceite o del ajuste no es factible.

X1 = Cambios del aceite, ajuste

X2 = Ajuste

Maximizar 7X1 + 15X2

Sujeta a:

|


X1 30 Cuenta De la Flota

20X1 + 60X2 4800 De trabajo tiempo

8X1 + 15X2 1750 Primas Materias

X1 0, X2 0.

El coste de trabajo de $10 por hora no se requiere para formular el problema desde el beneficio por cambio del aceite y el ajuste toma en la consideración el coste de trabajo.

Método de Solución Gráfica

Dado que somos una especie visual, debido a un nuevo sistema educativo, muchas de las herramientas de enseñanza escolar utilizadas en la actualidad son de naturaleza gráfica. Les enseñan a leer mostrándoles figuras de las cosas. A contar mostrándoles el orden de los números. En consecuencia, nuestros receptores visuales se agudizan a expensas de otras funciones cognitivas. También he descubierto que las personas de negocios responden mejor a los gráficos y a los cuadros que a los números.

Procedimiento para el Método Gráfico de Solución de Problemas de PL:

1. ¿El problema es un problema de PL? La respuesta es afirmativa si y sólo si:

Todas las variables están elevadas a la primera potencia y son sumadas o restadas (no dividas ni multiplicadas). La restricción debe adoptar alguna de las siguientes formas (, , o =, es decir que las restricciones de PL siempre están cerradas), y el objetivo debe ser de maximización o minimización.

Por ejemplo, el siguiente problema no es un problema de PL: Max X, sujeta a . Este problema tan sencillo no tiene solución.

2. ¿Puedo utilizar el método gráfico? La respuesta es afirmativa si la cantidad de variables de decisión es 1 o 2.

3. Utilice papel milimetrado. Grafique cada restricción, una por una, como si fueran igualdades (como si todo y , es = ) y luego trace la línea.

4. A medida que se crea cada línea, divida la región en 3 partes con respecto a cada línea. Para identificar la región factible para esta restricción en particular, elija un punto en cualquier lado de la línea y coloque sus coordenadas en la restricción, si satisface la condición, este lado es factible, de lo contrario el otro lado es factible. En el caso de restricciones de igualdad, sólo los puntos sobre la línea son factibles.

5. Elimine los lados que no son factibles.

|


Una vez graficadas todas las restricciones, debe generarse una región factible no vacía (convexa), salvo que el problema sea no factible.

6. Cree (como mínimo) dos líneas de igual valor desde la función objetivo, fijando la función objetivo en dos números distintos cualquiera. Grafique las líneas resultantes. Al mover estas líneas paralelas, encontrará el vértice óptimo (punto extremo), si es que existe.

En general, si la región factible se encuentra dentro del primer cuadrante del sistema de coordenadas (es decir si X1 y X2 0), entonces, para los problemas de maximización, usted debe mover la función objetivo de igual valor (función) paralela a sí misma lejos del punto de origen (0, 0), como mínimo, teniendo a la vez un punto en común con la región factible. Sin embargo, para los problemas de minimización, debe realizar lo opuesto, es decir, mover la función objetivo de igual valor (función) paralela a sí misma acercándola al punto de origen, a su vez teniendo como mínimo un punto en común con la región factible. El punto común proporciona la solución óptima.

Recuerde que las restricciones de PL proporcionan los vértices y las esquinas. Un vértice es la intersección de 2 líneas o en general, n hiperplanos en problemas de PL con n variables de decisión. Una esquina es un vértice que además es factible.

Un Ejemplo Numérico: El Problema del Carpintero

Maximizar 5 X1 + 3 X2

Sujeta a:

2 X1 + X2 40

X1 + 2 X2 50

and both X1, X2 are non-negative.

|


Nota: Existe una alternativa del abordaje de la función objetivo de igual valor (función) con problemas que tienen pocas restricciones y una región factible acotada. Primero busque todas las esquinas, también llamadas puntos extremos. Luego, evalúe la función objetivo en los puntos extremos para llegar al valor óptimo y a la solución óptima.

Por ejemplo, en el problema del carpintero, la región factible convexa proporciona los puntos extremos con las coordenadas que figuran en la siguiente Tabla:

Valor de la Función Objetivo en cada Esquina o Punto Extremo

Elecciones del DecisorCoordenadas de los Puntos Extremos

Función de los Ingresos Netos

Cantidad de Mesas o Sillas X1, X2 5 X1 + 3 X2

No fabricar ninguna mesa ni silla

0, 0 0

Fabricar todas la mesas posibles

20, 0 100

Fabricar todas las sillas posibles

0, 25 75

Fabricar una combinación de productos

10, 20 110

|


Dado que el objetivo es maximizar, de la tabla anterior surge que el valor óptimo es 110, el cual se obtiene si el carpintero sigue la estrategia óptima de X1 = 10 y X2 = 20.

La principal deficiencia del método gráfico es que se limita a resolver problemas lineales que tengan sólo 1 o 2 variables de decisión. Sin embargo, la conclusión principal y útil a la que podemos arribar a partir del análisis de los métodos gráficos es la siguiente:

Si un programa lineal tiene una región factible acotada no vacía, la solución óptima es siempre uno de los puntos extremos. .

La prueba de esta afirmación surge de los resultados de los siguientes dos hechos:

Hecho N° 1: La región factible de cualquier programa lineal es siempre un conjunto convexo.

Debido a que todas las restricciones son lineales, la región factible (R.F.) es un polígono. Además, este polígono es un conjunto convexo. En cualquier problema de PL que tenga más de dos dimensiones, los límites de la región factible son partes de los hiperplanos, y la región factible en este caso se denomina poliedro y también es convexa. Un conjunto convexo es aquel en el cual si se eligen dos puntos factibles, todos los puntos en el segmento de la línea recta que une estos dos puntos también son factibles. La prueba de que la región factible de los programas lineales son siempre conjuntos convexos surge por contradicción. Las siguientes figuras ilustran ejemplos de los dos tipos de conjuntos: un conjunto no convexo y un conjunto convexo.

El conjunto de la región factible en cualquier programa lineal se denomina poliedro y si está acotado se denomina politopo.

Hecho N° 2: El valor iso de una función objetivo de un programa lineal es siempre una función lineal.

Este hecho surge de la naturaleza de la función objetivo de cualquier problema de PL. Las siguientes figuras ilustran las dos clases típicas de funciones objetivo de igual valor (función iso).

|


De la combinación de los dos hechos expresados arriba surge que si un programa lineal tiene una región factible acotada no vacía, la solución óptima es siempre uno de los puntos extremos.

Para superar la deficiencia del método gráfico, utilizaremos esta conclusión útil y práctica en el desarrollo de un método algebraico aplicable a problemas de PL multidimensionales.

La convexidad de la región factible de los programas lineales facilita la resolución de problemas de PL. Debido a esta propiedad y a la linealidad de la función objetivo, la solución es siempre uno de los vértices. Asimismo, dado que la cantidad de vértices es limitada, todo lo que debemos hacer es buscar todos los vértices factibles y luego evaluar la función objetivo en dichos vértices para encontrar el punto óptimo.

En el caso de programas no lineales, el problema es mucho más difícil de resolver porque la solución podría estar en cualquier parte dentro de la región factible, en el límite de la región factible o en un vértice.

Por suerte, la mayoría de los problemas de optimización empresarial son lineales y es por eso que la PL es tan popular. Hoy en día, existen más de 400 paquetes de software en el mercado para resolver problemas de PL. La mayoría se basa en la búsqueda de vértices. Esto equivale a pasar de un vértice a otro cercano en busca de un punto óptimo.

|


Introducción De Modelos

Ejemplo 1:

Maximizar variables = 12x1

+5x2 +15x3 + 10x4 Función Objetivo

S.a.

5x1 + x2 +9x3 + 12x4 ≤ 1500 Madera(A)

2x1 + 3x2 +4x3 + x4 ≤ 1000 Madera (B)

3x1 + 2x2 +5x3 + 10x4 ≤ 800 Hora- Hombre

X1≥40

X2≥130 RESTRICCIONES

X3≥30

X4≤10

|


No Negatividad x≥0 (i=1, 2, 3, 4)

Ejemplo 2:

Maximizar variables = 300x1 +250x2 Función Objetivo

S.a.

x 125000

+ x 2

350000 ≤ 1

Donde:X1: Automóviles

X2: Camiones

x 133333

+ x 2

16667 ≤ 1

X1≤225000

X3≤15000

X1,x2≥0

Ejemplo 3:

X1 X2 X3 X4 X5

30 3 0 0 0 2 800

45 0 2 0 1 1 500

50 0 0 2 1 0 1000

Residuo 18 18 8 13 3

Ejemplo 4:

1 2 3

1 X11 X12 X13 100

|


8

11

12

97

10

2 X21 X22 X23 200

Potencia de Ventas 150 200 350

Precio de Ventas 12 14 15

Maximizar variables = 4x11 +4x12 +3x13 + 5x21 +5x22 +4x23 Función Objetivo

S.a.

Ejemplo 5:

Bodega/Articulo Pro Centro Popa Peso(TBN) Pies3(TBN) Precio(TBN)

A 3 0 0 6000 60 6

B 0 2 0 4000 500 8

C 150 200 350 2000 25 9

Peso(TBN) 12 14 15

Vol(Pres) 10000 135000 30000

Maximizar variables = 6(x1 +x2 +x3) + 8(x4+x5 +x6) + 9(x7 +x8 +x9) Función Objetivo

S.a.

a) Restricción de acuerdo al trabajo de la bodega

x1 + x4 +x7 ≤ 20000

x2 + x5 +x8 ≤ 3000

x3 + x6 +x9 ≤ 1500

b) Restricción respecto al volumen de la bodega

60x1 +50x4+25x7 ≤ 100000

60X2 + 50x5 +25x8 ≤ 135000

|


x11 + x12 +x13 ≤ 100 x21

+ x22 +x23 ≤ 200

x11 + x21 ≤ 150

x12 + x22 ≤ 200

60X3 +50x6+25x9 ≤ 30000

c) Restricción respecto a la oferta

x1 +x2+x3 ≤ 6000

X4 + x5 +x6 ≤ 4000

X7 +x8+x9 ≤ 2000

d) Restricción para mantenerse en equilibrio

x1+x 4+x 72000

+ x2+x5+ x8

3000 +

x3+x 6+x 91500

MODELOS DE MULTIPLES PERIODOS

CSL, es una cadena de tiendas de servicio para computadoras, el número de horas de reparación especializada que requiere CSL durante los próximos cinco meses se da a continuación:

T=1, 2, 3, 4,5

Mes enero= 6000 horas

Mes de febrero= 7000 horas

Mes de marzo= 8000 horas

Mes de abril = 9500 horas x

Mes de mayo = 11000 horas

Al principio de enero se tiene 50 técnicos, cada técnico especializado puede trabajar hasta 160 horas al mes, y este técnico experimentado supervisa al aprendiz durante 50 horas al mes.

A cada técnico aprendiz le pagan mensualmente $ 1000, y al técnico experimentado le pagan mensualmente $ 2000. Y al final de cada mes el 5% de técnicos especializados cambian de trabajo para irse con PLUM COMPUTER.

Formule una programación lineal, cuya solución permita a CSL, minimizar los costos de trabajo que se presentan al cumplir con los requerimientos de servicios durante los próximos 5 meses.

Técnico Técnicos Técnicos Aprendiz Horas total de trabajo

|


Meses Experimentados mensual

Enero y1 x1 6000 h

Febrero y2 x2 7000 h

Marzo y3 x3 8000 h

Abril y4 x4 9500 h

Mayo y5 x5 11000 h

Pago mensual de los técnicos 2000 1000

Número de horas trabajadas en el mes

160 50

La función objeto de CSL es:

Min z= 2000 y1+ 2000y2 + 2000y3+ 2000y4 + 2000y5 + 1000x1 + 1000x2+ 1000x3+ 1000x4

+ 1000x5

Restricciones:

1. Restricción: “Saber el número de horas técnico disponible durante el mes”.

160y1 – 50x1 6000 (Mes de enero)

160y2 – 50x2 7000 (Mes de febrero)

160y3 – 50x3 8000 (Mes de marzo)

160y4 – 50x4 9500 (Mes de abril)

160y5 – 50x5 11000 (Mes de mayo)

MODELOS FINANCIEROS DE MULTIPLES PERIODOS

Flujo de Efectivo en el tiempo (Dólares)

0 1 2 3

|


De la inversión A -1 +0.50 +1 0

De la inversión B 0 -1 +0.50 +1

De la inversión C -1 +1.2 0 0

De la inversión D -1 0 0 +1.9

De la inversión E 0 0 -1 +1.5

Nota: tiempo 0=tiempo actual: tiempo 1=después de un año: tiempo2=después de 2 años: tiempo3=después de 3 años (todos a punto de abrir).

FORMULE UN POGRAMACION LINEAL QUE MAXIMIZE EL EFECTIVO EN CAJA EN EL TIEMPO 3.

Solución:

1. Definiendo variables de decisiónA=dólares invertidos en AB=dólares invertidos en BC=dólares invertidos en CD=dólares invertidos en DA=dólares invertidos en ES1=dólares invertidos en fondos de mercado de valores en el tiempo t (t=0, 1,2)Efectivo en caja en el tiempo 3

B+1.9D+1.5E+1.08S2

2. Función ObjetivoMax. Z= B+1.9D+1.5E+1.08S2…. (1)

3. Definiendo restriccionesDinero disponible en el tiempo t= dinero invertido en el tiempo t+ dinero no invertido en el tiempo t, que se transfiere al tiempo t+1

100000=A+C+D+S0 …..(3)0.5ª+1.2C+1.08S0=B+S1 ….(4)A+0.5B+1.08S1=E+S2 ……(5)Otras restrictions:A≤75000,B≤75000,C≤75000,D≤75000,E≤75000A, B, C, D, E, S0, S1, S2≥0Haciendo las combinaciones de (1) y (2) – (6), obtenemos el modelo de PL siguiente:

Max Z=B+1.9D+1.5E+1.08S2

S.A.

|


Dinero disponible en el tiempo t= dinero invertido en el tiempo t

A+C+D+S0=1000000.5ª+1.2C+1.08S0=B+S1

A+0.5B+1.08S1=E+S1

A≤75000B≤75000C≤75000D≤75000E≤75000

A, B, C, D, E, S0, S1, S2≥0

Finalmente:Encontramos como0 solución optima Z=218500, A=60000, B=30000, D=40000, E=75000, C=S0=S1=S2=0.Asi Finco no tiene que invertir en fondos del mercado de valores. En el tiempo 0, Finco tiene que invertir 60000 dólares en A y 40000 dólares en D. Después en el tiempo 1, hay que invertir los 30000 dólares de intereses de la inversión A en B.Finalmente en el tiempo 2, hay que invertir los 60000 dólares de réditos de A y los 15000 dólares de réditos de B en E. En el tiempo 3, los 100000 dólares de Finco se habrán convertido en 218500

Problema De Alimentación

Mi alimentación requiere que todo de lo que coma pertenezca a uno de los cuatro “grupos básicos de alimentos” (pastel de chocolate, helado, refrescos y pastel de queso). Actualmente, se dispone de los siguientes alimentos para el consumo: biscochos de chocolate y nueces, helado de chocolate, cola, y pastel de queso con piña. Cada bizcocho cuesta 50centavos; cada bola de helado de chocolate, 20centavos; cada botella de refresco cola, 30centavos; y cada pieza de pastel de queso con piña, 80 centavos. Cada día tengo que ingerir por lo menos 500 calorías, 6 onzas de chocolate, 10 onzas de azúcar y 8 onzas de grasas. El contenido nutritivo por unidad de cada elemento se muestra en la Tabla 1. Formule un modelo lineal que se puede utilizar para satisfacer mis requerimientos alimenticios diarios a un costo mínimo

Tabla1:

Valores nutritivos para el ejemplo de la dieta

CALORIAS CHOCOLATE

(onzas)

AZUCAR

(onzas)

GRASA

(onzas)

Bizcochos 400 3 2 2

Helado de Chocolate (1bola) 200 2 2 4

Refresco de Cola (1 botella) 150 0 4 1

Pastel de queso con piña 500 0 4 5

|


SOLUCION:

Como siempre se empieza por determinar las decisiones que se tienen que tomar ¿Cuánto hay que comer diariamente de cada alimento? Por lo tanto, definimos las variables de decisión.

X1=numerode bizcochos ingeridos diariamente

X2=numerode bolas dehelado dec hocolate ingeridos diariamente

X3=botellas derefresco decolatomadas diariamente

X 4=piezasde pastel dequeso con pi ña ingeridos diariamente

El objetivo es minimizar el costo de mi alimentación. Se puede determinar el costo total de cualquier dieta a partir de la siguiente relación: (costo total de la dieta)= (costo de los bizcochos)+ (costo del helado)+ (costo de la cola)+ (costo del pastel de queso). Para evaluar el costo total de una dieta, obsérvese que, por ejemplo.

Costo de lacola=( costobotellade cola )=(botellas tomadas decola )=30 X3

Aplicar esto a los otros tres alimentos, obtenemos (en centavos)

Costototal de la dieta=50 X 1+20 X2+30 X3+80 X4

Así la función objetivo es:

min Z=¿50 X1+20 X2+30 X3+80 X 4 ¿

Las variables de decisión tienen que satisfacer las siguientes cuatro restricciones:

Restriccion1: El consumo diario de calorías tiene que ser por lo menos 500 calorías

Restriccion2: El consumo diario de chocolate tiene que ser de por lo menos 6 onzas

Restriccion3: El consumo diario de azúcar tiene que ser de por lo menos 10 onzas

Restriccion4: El consumo diario de grasa tiene que ser de por lo menos 8 onzas

Para expresar la Restricción 1 en términos de las variables de decisión, obsérvese que (el consumo diario de chocolates)= (las calorías de los bizcochos)+ (las calorías en el helado de chocolate)+ (las calorías en la cola)+ (las calorías en el pastel de piña con queso).

Se pueden determinar las calorías en los bizcochos consumidos a partir de:

calorias en los bizcochos=( caloriasbizcoc hos )=(bizcoc hoscomidos )=400 X1

Aplicando un razonamiento similar para los otros alimentos, se llega a:

Consumo diariodecalorias=400 X1+200 X2+150 X3+500 X 4

|


Se puede usar la restricción 1 por:

400 X1+200 X2+150 X3+500 X4≥500(calorias ) (Restricción del calorias) (21)


3 X1+2 X2≥6 (Restricción del chocolate)(22)


2 X1+2 X2+4 X3+¿ 4 X 4≥10 ¿ (Restricción del azucar)

(23)


2 X1+4 X2+X3+¿5 X4≥ 8¿ (Restricción de la grasa) (24)

Finalmente hay que cumplir con las restricciones de signo X i≥0(i=1,2,3,4 ). Si se

convinaran la funcion objetivo, las restricciones (21)-(24), y las restricciones de signo, tenemos lo siguiente.

min Z=¿50 X1+20 X2+30 X3+80 X 4 ¿

s.a

400 X1+200 X2+150 X3+500 X4≥500 (rest. del calorias)

3 X1+2 X2≥6 (rest. del chocolate)

2 X1+2 X2+4 X3+¿ 4 X 4≥10 ¿ (rest. Del azucar)

2 X1+4 X2+X3+¿5 X4≥ 8¿(rest. De la grasa)

X i≥0(i=1,2,3,4 )

La solución óptima para este programa lineal es X1=X4=0 , X2=3 , X3=1, Z=90. Por lo

tanto, la dietade minimo costo diario es de 90 centavos, consiste en comer 3 bolas de helado de chocolate y tomar una botella de refresco de cola. Se puede obtener el valor optimo de Z al sutituir los valores optimos de las variables de decision en la función objetivo. Esto produce un costo total de Z=3 (20 )+1 (30 )=90centavos

La dieta óptima proporciona:

200 (3 )+150 (1 )=750calorias

2 (3 )=6 onzasde chocolate

(3 )+4 (1 )=7 ozde azucar

|


4 (3 )+1 (1 )=13oz de grasa

Así las restricciones del chocolate y del azúcar son obligatorias, pero las restricciones de las calorías y de la grasa no son obligatorias.

Star Oil Company considera cinco diferentes oportunidades de inversión en la tabla 5 se le dan los desembolsos de caja y los valores actuales netos.

Star Oil dispone de 40 millones de dólares para invertir en el momento actual (tiempo 0); estima que en un año (tiempo 1) dispondrá de 20 millones de dólares para invertir. Star Oil puede comprar cualquier fracción de cualquier inversión. En este caso, las salidas de caja y los VAN se ajustan en forma correspondiente. Star Oil quiere maximizar el VAN que se puede obtener mediante las inversiones 1 a 5. Formule un PL que ayude a alcanzar esta meta. Supóngase que los fondos usados en el tiempo cero no se pueden usar en el tiempo 1.

TABLA 5

Inv. 1 Inv. 2 Inv. 3 Inv. 4 Inv. 5

Salida de caja al tiempo 0 11 53 5 5 29

Salida de caja al tiempo 1 3 6 5 1 34

VAN 13 16 16 14 39

SOLUCION:

La meta de Star Oil es maximizar el VAN ganado por las inversiones.

VAN de la inv. 1 = (VAN de la inv. 1) (fracción inv. 1)

VAN de la inv. 1 =13 X1

Al aplicar un razonamiento similar a las inv. 2 al 5, vemos que Star Oil quiere maximizar.

Z=13X1 +16X2 + 16X3 +14X4 + 39X5

La restricciones de Star Oil son:

Restricción 1: Star no puede invertir más de 40 millones de dólares en el tiempo 0.

11X1 + 53X2 + 5X3 +5X4 + 29X5 <= 40

Restricción 2: Star no puede invertir más de 20 millones de dólares en el tiempo 1.

3X1 + 6X2 + 5X3 +X4 + 34X5 <= 20

Restricción 3: Star no puede comprar más del 100% de la inversión i (i=1, 2, 3, 4,5).

Xi <= 1 (i=1, 2, 3, 4,5).

|


Por lo tanto el P.L seria:

Z=13X1 +16X2 + 16X3 +14X4 + 39X5

s.a

11X1 + 53X2 + 5X3 +5X4 + 29X5 <= 40

3X1 + 6X2 + 5X3 +X4 + 34X5 <= 20

X1 <= 1

X2 <= 1

X3 <= 1

X4 <= 1

X5 <= 1

Xi <= 0

Problema de establecimiento de horario de trabajo

Para muchas aplicaciones de la Programación lineal es necesario determinar el método de mínimo costo para satisfacer requerimientos de la fuerza de trabajo. El ejemplo siguiente ilustra las características básicas, comunes para muchas de estas aplicaciones.

EJEMPLO: Una oficina de correos necesita un número diferente de empleados de tiempo completo, para diferentes días de la semana. El número de empleados de tiempo completo requeridos para cada día, se da en la Tabla 3.Las reglas sindicales señalan que cada empleado, de tiempo completo, tiene que trabajar durante 5 días consecutivos y, después descansar 2 días. Por ejemplo, un empleado que trabaja de lunes a viernes, tiene que descansar el sábado y el domingo. La oficina de correos quiere cumplir con sus requerimientos diarios y utilizar solamente empleados de tiempo completo. Formule un PL que pueda utilizar la oficina de correos para minimizar el número de empleados de tiempo completo que hay que contratar.

DIAS NUMERO DE EMPLEADOS DE TIEMPO COMPLETO REQUERIDOS

Día 1 = lunes 17

Día 2 = martes 13

Día 3 = miércoles 15

Día 4 = jueves 19

Día 5 = viernes 14

|


Día 6 = sábado 16

Día 7 = domingo 11

SOLUCIÓN:

La clave para formular correctamente este problema es darse cuenta de que la decisión principal de la oficina de correos no es cuantas personas trabajan cada día, sino cuantas personas empiezan a trabajar cada día de la semana. Tomando esto en cuenta, definimos:

Xi= número de empleados que empiezan a trabajar el día i.

Por ejemplo xi es el número de personas empiezan a trabajar el lunes (estas personas trabajan del lunes a viernes).

Con la definición adecuada de las variables es fácil determinar correctamente la función objetivo, obsérvese que:

Número de empleados de tiempo completo= número de empleados que empiezan a trabajar el día lunes + número de empleados que empiezan a trabajar el día el martes + número de empleados que empiezan a trabajar el día miércoles.....+ número de empleados que empiezan a trabajar el día domingo. Ya que cada empleado comienza a trabajar exactamente un día de la semana, esta expresión no cuenta 2 veces a los empleados. Por lo tanto con la definición correcta de las variables, la función objetivo es:

Min z= X1 + X2 + X3 + X4 + X5 + X6 + X7

La oficina de correos tiene que asegurar que hay suficientes empleados trabajando cada día de la semana. Por ejemplo: Por lo menos 17 empleados tienen que trabajar el lunes. y ¿Quién está empezando a trabajar el lunes? Todos, menos los empleados que empiezan a trabajar el martes o el miércoles (ellos descansan el domingo y el lunes Y el lunes y el martes respectivamente).Esto significa que el número de empleados que trabajan el día lunes está dada por: X1 + X4 + X5 + X6 + X7 >=17

Al añadir las restricciones similares para los otros 6 días de la semana y las restricciones de signo Xi >=0(i=1, 2,3...7), se obtiene la siguiente formulación del problema de la oficina de correos:

Min z= X1 + X2 + X3 + X4 + X5 + X6 + X7

S.a:

X1 +X4 + X5 + X6 + X7 >=17 (Restricción del lunes)

X1 + X2 + X5 + X6 + X7 >=13 (Restricción del martes)

X1 + X2 + X3 + X6 + X7 >=15 (Restricción del miércoles)

X1 + X2 + X3 + X4 + X7 >=19 (Restricción del jueves)

|


X1 + X2 + X3 + X4 + X5 >=15 (Restricción del viernes)

X2 + X3 + X4 + X5+ X6 >=16 (Restricción del sábado)

X3 + X4 + X5+ X6 + X7 >=11 (Restricción del domingo)

Xi >=0 (i=1, 2,3...7) (Restricción del signo)

La solución óptima para este PL es

Z=673

X1=43

X2=103

X3=2

X4=223

X5=0

X6=103

X7=5

Sin embargo ya que solamente se admite empleados de tiempo completo, las variables tienes que ser números enteros, con lo que la suposición de la divisibilidad no se satisface. Al intentar obtener una respuesta razonable, solamente con variables enteras, podríamos tratar de redondear las variables, lo que produciría la solución factible:

Z=25

X1=2, X2=4, X3 =2, X4=8, X5 =0 + X6 = 4, X7=5.

Resulta sin embargo, que la solución optima para el problema de la oficina de correos, mediant5e la programación entera es:

Z=23

X1=4, X2=4, X3 =2, X4=6, X5 =0 + X6 = 4, X7=3.

Obsérvese que no hubiera sido posible obtener la solución óptima con puros enteros mediante el redondeo de la solución óptima de la programación lineal.

Modelo de proceso de producción

Ahora se explica cómo formular un modelo de programación lineal para un proceso de producción sencillo. El paso clave es determinar como la producción en una etapa posterior del proceso se relaciona con la producción en una etapa anterior.

|


Ejemplo

Rylon corporation fabrica los perfumes Brutte y Chanelle. Se puede comprar materia prima que se necesita para producir cada tipo de perfume a 3 dólares/lb. Para procesar 1 lb de materia prima, se necesita 1 hora de trabajo en el laboratorio. Cada libra de materia prima procesada produce 3 oz de Perfume Brute Regular, y 4 oz de perfume Chanelle Regular. Se pude vender Brute Regular a 7 dólares/oz, y Chanelle Regular a 6 dólares/oz. Rylon tiene también la opción de seguir procesando Brute Regular y Chanelle Regular para producir Brute Luxury, vendido a 18 dólares/oz, y Chanelle Luxury, vendido a 14 dólares/oz. Cada onza de Brute Regular necesita 3 horas adicionales de laboratorio y causa 4 dólares extra de costo de producción, para producir 1 oz de Brute Luxury. Cada onza de Chanelle Regular necesita 2 horas adicionales de laboratorio y 4 dólares extra de costos de producción para producir 1 oz de Chanelle Luxury. Cada año, Rylon dispone de 6000 horas de laboratorio y pude comprar hasta 4000 lb de materia prima. Formule un PL que se puede utilizar para determinar cómo puede maximizar Rylon sus ganancias. Supóngase que los costos de laboratorio son fijos.

Solución Rylon tiene que determinar cuanta materia prima hay que comprar y cuanto se tiene que producir de cada tipo de perfume. Por lo tanto, definimos nuestras variables de decisión como

X1 = onzas de Brute Regular vendidas anualmente

X2 = onzas de Brute Luxury vendidas anualmente

X3 = onzas de Chanelle Regular vendidas anualmente

X4 = onzas de Chanelle Luxury vendidas anualmente

X5 = libras de materia prima compradas anualmente

Rylon quiere maximizar

Contribución a la ganancia = ingresos por la venta de los perfumes

– costos de fabricación

– costos de la compra de materia prima

= 7X1 + 18X2 + 6X3 + 14X4 – (4X2 + 4X4) – 3X5

= 7X1 + 14X2 + 6X3 + 10X4 – 3X5

Así, se puede escribir la función objetivo de Rylon como

Max z = 7X1 + 14X2 + 6X3 + 10X4 – 3X5

Rylon se encuentra con las siguientes restricciones:

Restricción 1 No se puede comprar más de 4000 lb de materia prima anualmente

|


Restricción 2 No se dispone de más de 6000 horas de laboratorio anualmente

La restricción 1 se expresa mediante

X5 ≤ 4000

Para expresar la restricción 2, observe que

Tiempo total anual del uso del laboratorio = tiempo usado anualmente para procesar la materia prima

+ Tiempo empleado anualmente para producir Brute Luxury

+ Tiempo usado al año para producir chanelle Luxury

= X5 + 3X2 + 2X4

Entonces la Restricción 2 se escribe como

3X2 + 2X4 + X5 ≤ 6000

Entonces las restricciones de signo Xi ≥ 0 (i = 1, 2, 3, 4,5), muchos estudiantes indican que Rylon tendría que resolver un PL siguiente:

Max z = 7X1 + 14X2 + 6X3 + 10X4 – 3X5

s.a

X5 ≤ 4000

3X2 + 2X4 + X5 ≤ 6000

Xi ≥ 0 (i = 1, 2, 3, 4,5)

Esta formulación es incorrecta. Obsérvese que las variables X1 y X3 no aparecen en las dos primeras restricciones. Esto significa que cualquier punto, con X2 = X4 = X5 = 0 y X1 y X3 muy grandes, se encuentra en la región factible. Los puntos X1 y X3 arbitrariamente grandes, pueden producir ganancias arbitrariamente grande. De esta manera, el PL es no acotado. Nuestro error es que la formulación actual no indica que cantidad de materia prima comprada, determina la cantidad de Brute y de chanelle disponible para la venta o para un proceso adicional. Mas especifico, de la Fig.8 (y del hecho que 1 oz de Brute procesado produce exactamente 1 oz de Brute Luxury), se concluye que

Onzas de Brute Regular vendidas + onzas de Brute Luxury vendidas

¿( onzasde Brute producidaslb demateria prima )+(lb dematerias primascompradas)

|


= 3X5

X1 oz Reg. Brute vendidas

X2 oz de Brute Reg.

Transformadas en Brute Lux

X3 oz de Chanelle Reg. Vendidas

X4 oz de Chanelle Reg.

Transformadas en Chanelle Lux

Proceso de producción para el ejemplo Brute-Chanelle

Esta relación se ve reflejada en la restricción

X1 + X2 = 3X5 o bien, X1 + X2 – 3X5 = 0

Similarmente, de la Fig. 8, es obvio que

Onzas de Chanelle Regular vendidas + onzas de Chanelle Luxury vendidas = 4X5

Esta relación proporciona la restricción

X3 + X4 = 4X5 o bien, X3 + X4 – 4X5 = 0

Las restricciones (57) y (58) relacionan varias variables de decisión. Los estudiantes olvidan muchas veces las restricciones de este tipo. Como se muestra este problema, la omisión de incluir una restricción puede llevar a una respuesta inaceptable (como un PL no acotado). Si combinamos (53) – (58) con las restricciones usuales de signo, obtenemos la formulación correcta del PL:

Max z = 7X1 + 14X2 + 6X3 + 10X4 – 3X5

S.a

X5 ≤ 4000

3X2 + 2X4 + X5 ≤ 6000

|


X5 lb de material prima

3X5 oz de Brute

4X5 oz Chanelle

X1 + X2 – 3X5 = 0

X3 + X4 – 4X5 = 0

Xi ≥ 0 (i = 1, 2, 3, 4, 5)

La solución optima es z = 172666.667, X1 = 11333.333 oz, X2 = 666.667 oz, X3 = 16000 oz, X4 = 0, y X5 = 4000 lb. Por lo tanto, Rylon tiene que comprar las 4000 lb disponibles de materia prima y producir 11333.333 oz de Brute Regular, 666.667 oz de Brute Luxury, y 16000 oz de Chanelle Regular. Este plan de producción contribuirá en 172666.667 dólares a la utilidad de Rylon. En este problema, parece razonable permitir valores fraccionarios de las onzas, y entonces se cumple con la suposición de divisibilidad.

Terminamos el análisis del problema de Rylon, exponiendo un error que muchos estudiantes cometen. Razonan de la manera siguiente:

1 lb de materia prima = 3 oz de Brute + 4 oz de Chanelle

Como X1 + X2 = cantidad total de onzas de Brute producidas, y X3 + X4 = la cantidad total de onzas de chanelle producidas, los estudiantes concluyen que

X5 = 3(X1 + X2) + 4(X3 + X4)

Esta ecuación podría tener sentido como un planteamiento para un programa de la computadora; en cierto sentido, la variable X5 se sustituye por el segundo miembro y de la Ec. (59). Como una restricción de PL, sin embargo, (59) carece de sentido. Para ver esto, obsérvese que el primer miembro de (59) tiene como unidades “libras de materia”, y el término 3X1 en el lado derecho de (59) tiene como unidades

¿( Onzasde BruteLibras de materia prima )(onzas de Brute)

Como algunos términos de (59) no tienen las mismas unidades, la Ec. (59) no puede ser correcta. Si hay dudas acerca de una restricción, asegurase de que todos los términos en las restricciones estén en las mismas unidades. Esto evitara muchos errores de formulación. (Naturalmente, una restricción puede estar equivocada, aunque las unidades en ambos lados de la restricción sean iguales)

Problema De Mezcla

Sunco Oil produce tres tipos de gasolina (1,2y3). Cada tipo de gasolina se produce mezclando tres tipos de petróleo crudo (1,2 y 3). La tabla 9 da los precios de venta por barril de las gasolinas y los precios de compra, por barril, del petróleo crudo. Sunco puede comprar hasta 5000 barriles de cada tipo de petróleo crudo diariamente.

Tabla 9: Precios de la gasolina y del petróleo crudo para ejemplo de mezclas.

PRECIOS DE VENTA PORBARRIL (dólares)

PRECIOS DE COMPRA POR BARRIL (dólares)

Gasolina 1 70Gasolina 2 60

Crudo 1 45Crudo 2 35 Crudo

|


Gasolina 3 50 3 25

Los tres tipos de gasolina difieren en su índice de octano y en su contenido de azufre. La mezcla de petróleo crudo que se utiliza para obtener la gasolina 1 tiene que tener un índice de octano promedio de por lo menos 10 y a lo más 1% de azufre. La mezcla de petróleo crudo que se utiliza para obtener la gasolina 2 tiene que tener un índice de octano promedio de por lo menos 8 y a lo más 2% de azufre. La mezcla de petróleo crudo que se utiliza para obtener la gasolina 3 tiene que tener un índice de octano promedio de por lo menos 6 y a lo más 1% de azufre. El índice de octano y el contenido de azufre de los tres tipos de petróleo se dan en la tabla 10. La transformación de un barril de petróleo en un barril de gasolina cuesta 4 dólares, ya la refinería de Sunco puede producir diariamente hasta 14 000 barriles de gasolina.

Tabla 10: índice de octano y requerimientos de azufre para el ejemplo de mezclas.

Índice de octano Contenido de azufre

Crudo 1 12 0.5%

Crudo 2 6 2.0%

Crudo 3 8 3.0%

Los clientes de Sunco necesitan diariamente las siguientes cantidades de cada tipo de gasolina: gasolina 1, 3000 barriles, gasolina 2, 2000 barriles, gasolina 3, 1000 barriles. La compañía se siente comprometida a cumplir con estas demandas. Sunco tiene la posibilidad de estimular la demanda de sus productos mediante la publicidad. Cada dólar invertido diariamente en la publicidad para cierto tipo de gasolina, aumenta la demanda diaria de este tipo de gasolina en 10 barriles. Por ejemplo, si Sunco decide gastar diariamente 20 dólares para promover la gasolina 2, la demanda diaria de la gasolina 2 se incrementara en 20(10)=200 barriles.

Formule un PL que permita a Sunco a maximizar sus ganancias diarias (ganancias= ingresos-costos).

SOLUCION:

Sunco tiene que tomar dos decisiones: primero, cuanto habría que invertir en la publicidad para cada tipo de gasolina, y segundo, como mezclar los tres tipos de petróleo crudo disponible para obtener cada tipo de gasolina. Por ejemplo, Sunco tiene que decidir cuántos barriles del crudo 1 habría que utilizar para producir la gasolina 1. Definimos las variables de decisión

a¡ = dólares gastados en la publicidad para la gasolina ¡(¡=1,2,3)

|


X¡¡ = barriles del petróleo crudo ¡ que se utiliza diariamente para producir la gasolina J(i = 1,2,3; j = 1,2,3)

Por ejemplo, X21 es el número de barriles de crudo 2 que se utiliza diariamente para producir la gasolina 1.

El conocimiento de estas variables es suficiente para determinar la función objetivo de Sunco y las restricciones, pero, antes de hacerlo, observamos que la definición de estas variables de decisión significa que

X11 + X12 + X13 = Barriles de crudo 1 usados diariamente X 21 + X22 + X23 = Barriles de crudo 2 usados diariamente X31 + X32 + X33 = Barriles de crudo 3 usados diariamente X 11 + X21 + X31 = Barriles de gasolina 1 usados diariamente X 12 + X22 + X32 = Barriles de gasolina 2 usados diariamente X 13 + X23 + X33

= Barriles de gasolina 3 usados diariamente

Para simplificar las cosas, supongamos que no se puede almacenar la gasolina, lo que significa que hay que venderla el mismo día de su producción. Esto quiere decir que para ¡ = 1,2,3, la cantidad de gasolina ¡ producida diariamente tiene que ser igual a la demanda diaria de la gasolina ¡. Supóngase que la cantidad de la gasolina ¡producida diariamente, es mayor que la demanda diaria. Entonces incurrimos en costos innecesarios de compra y de producción. Por lo contrario, si la cantidad de gasolina ¡producida diariamente es menor que la demanda diaria, no cumplimos con las demandas obligatorias, o incurrimos en costos de publicidad innecesarios.

Estamos listos ahora, para determinar la función objetivo y las restricciones de Sunco. Empezamos con la función objetivo de Sunco.

Ingresos diarios por la venta de gasolina =

70(X11 + X21 + X31) + 60(X12 + X22 + X32) + 50(X13 + X23 + X33)

Costos diarios de la compra de petróleo crudo =

45(X11 + X12 + X13) + 35(X21 + X22 + X23) + 25(X31 + X32 + X33)

Costos diarios de publicidad =

A1 + A2 + A3

Costos diarios de la producción =

4(X11 + X12 + X13 + X21 + X22 + X23 + X31 + X32 + X33)

Entonces,

Ganancia diaria = ingresos diarios por la venta de gasolina -- costo diario de la compra de petróleo crudo -- costos diarios de la publicidad -- costos diarios de la producción

|


= (70 – 45 – 4) X11 + (60 – 45 – 4) X12 + (50 – 45 – 4) X13 + (70 – 35 – 4) X21 + (60 – 35 – 4) X22 + (50 – 35 – 4) X23 + (70 – 25 – 4) X31 + (60 – 25 – 4) X32 + (50 – 25 – 4) X33 -- A1 -- A2 -- A3

De esta manera, la meta de Sunco es maximizar

Z = 21 X11 + 11 X12 + X13 + 31 X21 + 21 X22 + 11 X23 + 41 X31

+ 31 X32 + 21 X33 -- A1 -- A2 -- A3

Con respeta a las restricciones de Sunco, vemos que se tiene que satisfacer las siguientes trece 13 restricciones:

Restricción 1. La producción diaria de gasolina 1 tiene que ser igual a la demanda diaria de gasolina 1.



Restricción 4. Se puede comprar a lo más 5 000 barriles de crudo 1 diariamente.



Restricción 7. Se puede producir a lo más 14 000 barriles de gasolina diariamente, debido a la capacidad limitada de la refinería.

Restricción 8. El petróleo crudo que se usa para obtener la gasolina 1, tiene que tener un índice de octano medio de por lo menos 10.



Restricción 11. El petróleo que se usa para obtener la gasolina 1, tiene que tener a lo más 1% de azufre.



Para expresar la restricción 1 en términos de las variables de decisión con esto vamos que

Demanda diaria de gasolina 1 = 3 000 + demanda de gasolina 1 generada por publicidad

|


Demanda de gasolina 1 generada por publicidad = (demanda de gasolina / dólar gastado) (dólares gastados) = 10 A1

De esta manera, la demanda diaria de gasolina es 1 = 3 000 + 10 A1. Se puede escribir ahora la restricción 1 como

X11 + X21 + X31 = 3 000 + 10 A1

Que se puede volver a escribir como

X11 + X21 + X31 - 10 A1 = 3 000

La restricción 2 se puede expresar como

X12 + X22 + X32 - 10 A2 = 2 000

La restricción 3 se puede expresar como

X13 + X23 + X33 - 10 A3 = 1 000

La restricción 4 se reduce a

X11 + X12 + X13 ≤ 5000


X21 + X22 + X23 ≤ 5000


X31 + X32 + X33 ≤ 5000

Obsérvese que

Producción total de la gasolina = gasolina 1 producida + gasolina 2 producida + gasolina 3 producida

= (X11 + X21 + X31) + (X12 + X22 + X32) + (X13 + X23 + X33)

La restricción 7 esta dado por

X11 + X21 + X31 + X12 + X22 + X32 + X13 + X23 + X33 ≤ 14 000

Para expresar las restricciones 8 a 10, tenemos que determinar el índice de octano “promedio” de una mezcla de diferentes tipos de petróleo crudo.

|


Índice octànico total en la mezcla =

Barriles en la mezcla

12(2) + 6(3) + 8(1) =

2 + 3 + 1

8 1

3

Suponemos que los índices de octano de diferentes crudos se mezclan linealmente. Por ejemplo, si mezclamos dos barriles de crudo 1, 3 barriles de será

Generalizando, podemos expresar la restricción 8 mediante

Desafortunadamente, no es una desigualdad lineal. Para transformar en una desigualdad lineal, solamente tenemos que multiplicar ambos miembros y simplificarlo lo que resulta

2 X11 - 4 X21 - 2 X31 ≥ 0

La restricción 9 da

Al multiplicar y simplificar

4 X12 - 2X22 ≥ 0

Ya que cada tipo de petróleo crudo tiene un índice de octano de 6 o más, cualquier mezcla que hagamos para obtener la gasolina 3, tendrá un índice de por lo menos 6. Esto significa que cualquier valor de las variables satisfará la restricción 10. Para verificarlo, podemos expresar la restricción 10 mediante

La restricción 10 da

6X13 + 2X33 ≥ 0

Ya que satisface siempre X13 ≥ 0 y X33 ≥ 0, automáticamente se satisface por lo tanto, no es necesita incluir en el modelo. Una restricción como esta que está implícita en otras restricciones del modelo se llama restricción redundante no se necesita incluirla en la formulación. Escogimos omitirla de nuestra formulación final.

La restricción 11 puede escribirse como

|


Índice octànico total en la gasolina =

Gasolina 1 en la mezcla

12 X11 + 6 X21 + 8 X31 ≥ 10

X11 + X21 + X31

12 X12 + 6 X22 + 8 X32 ≥ 8

X12 + X22 + X32

12 X13 + 6 X23 + 8 X33 ≥ 8

X13 + X23 + X33

Total de azufre en la mezcla de la gasolina ≤ 0.01

Barriles en la mezcla de la gasolina

Entonces, utilizando los porcentajes de azufre en cada tipo de petróleo, vamos que

Total de azufre en la mezcla de gasolina = azufre en el crudo 1, usado para la gasolina 1 + azufre en el crudo 2, usado para la gasolina + azufre en el crudo 3, usado para la gasolina 1

= 0.005 X11 + 0.02 X21 + 0.03 X31

la restricción 11 puede escribirse ahora como

una vez más, no se trata de una desigualdad lineal, pero podemos multiplicar ambos miembros y simplificar lo que nos da

-0.005 X11 + 0.01 X21 + 0.02 X31 ≤ 0

De igual manera la restricción 12 es equivalente a

Al multiplicar ambos lados de la desigualdad y simplificar obtenemos

-0.015 X12 + 0.01 X32 ≤ 0

Por último la restricción 13 es equivalente a

Al multiplicar ambos miembros y simplificar obtenemos

-0.005 X13 + 0.01 X23 + 0.02 X33 ≤ 0

Z = 21 X11 + 11 X12 + X13 + 31 X21 + 21 X22 + 11 X23 + 41 X31

+ 31 X32 + 21 X33 -- A1 -- A2 -- A3

s.a : X11 + X21 + X31 - 10 A1 = 3 000

X12 + X22 + X32 - 10 A2 = 2 000

X13 + X23 + X33 - 10 A3 = 1 000

X11 + X12 + X13 ≤ 5000

X21 + X22 + X23 ≤ 5000

X31 + X32 + X33 ≤ 5000

X11 + X21 + X31 + X12 + X22 + X32 + X13 + X23 + X33 ≤ 14 000

|


0.005 X11 + 0.02 X21 + 0.03 X31 ≤ 0.01

X11 + X21 + X31

0.005 X12 + 0.02 X22 + 0.03 X32 ≤ 0.02

X12 + X22 + X32

0.005 X13 + 0.02 X23 + 0.03 X33 ≤ 0.01

X13 + X23 + X33

2 X11 - 4 X21 - 2 X31 ≥ 0

4 X12 - 2X22 ≥ 0

-0.005 X11 + 0.01 X21 + 0.02 X31 ≤ 0

-0.015 X12 + 0.01 X32 ≤ 0

-0.005 X13 + 0.01 X23 + 0.02 X33 ≤ 0

X¡¡ ≥ 0 y A¡ ≥ 0 así obtenemos el programa lineal.

|


Max Z=5x1 + 4x2

S:a:

6x1 + 4x2 ≤ 24

x1 + 2x2 ≤ 6

-x1 + x2 ≤ 1

x2 ≤ 2

x1,x2 ≥ 0

SOLUCION

.- Primero igualamos las restricciones y obtenemos las ecuaciones respecticas.

1. 6x1 +4x2 ¿ 24 2. x1+2 x2 =6

X1 0 4

X2 6 0

3 . –x1+x2=1 4. X2=2

|


X1 0 6

X2 3 0

X1 0 -1

X2 1 0

GRAFICA DE LAS RESTRICIONES

|


E. 4

E. 3E.2

E. 1

a f

d

e

c

b

Esta grafica nos muestra los puntos en los vertices, de las rectricciones, la cual nos orientaran a la solucion por este metodo, y para encontrarla se tiene que ubicar los puntos en la grafica y asi obtener los puntos que mostraran la solucion optima.

A continuacion el siguiente grafico mostrara los puntos de la funcion objeto

Una ves realizado la grafica, trazamos la ecuacion de la funcion objeto:

Ecuacion es:

5x1+4x2=k

5x1+4x2=20

|


E.F.O

E. 4

E. 3E.2

E. 1

a f

d

e

c

b

X1 0 4

X2 5 0

Dentro de la solucion me interesa maximizar, la funcion objeto por lo tanto el punto mas lejano es el vertice del punto “E”, resolvemos la ecuacion y obtendremos los puntos.

6x1+4x2=24 x1+2x2=6

6(6-2x2)+4x2=24 x1=6-2x2

12=8x2 x1=6-2(1,5)

X2=1,5 x1=3

Los puntos son: E(3,1,5), y si cumple con las rectricciones, por lo tanto es una solucion optima.

Max Z= 3x1 + x2

S:a:

6x1 + 4x2 ≤ 24

x1 + 2x2 ≤ 6

-x1 + x2 ≤ 1

x2 ≤ 2

x1,x2 ≥ 0

|


SOLUCION

.- Primero igualamos las restricciones y obtenemos las ecuaciones respectivas.

1. 6x1 +4x2 ¿ 24 2. x1+2 x2 =6

X1 0 4

X2 6 0

3 . –x1+x2=1 4. X2=2

X1 0 -1

X2 1 0

GRAFICA DE LAS RECTRICCIONES

|


E. 4

E. 3E.2

E. 1

a f

d

e

c

b

X1 0 6

X2 3 0


A continuacion el siguiente grafico mostrara los puntos de la funcion objeto.

GRAFICA DE LAS RECTRICCIONES CON LA FUNCION OBJETO

3x1 +x2=k

3x1+x2=3

|


E.F.O

E. 4

E. 3E.2

E. 1

a f

d

e

c

b

X1 0 1

X2 3 0

Dentro de la solucion me interesa maximizar, la funcion objeto por lo tanto el punto mas lejano es el vertice del punto “F”, resolvemos la ecuacion y obtendremos los puntos.

6x1+4x2=24 x1=4

6(4)+4x2=24

4x2=0

X2=0 x1=4

Los puntos son: F(4,0), y si cumple con las rectricciones, por lo tanto es una solucion optima.

Max Z=3x1+x2

Max Z=12

Max Z= x1 +3 x2

S:a:

6x1 + 4x2 ≤ 24

x1 + 2x2 ≤ 6

-x1 + x2 ≤ 1

x2 ≤ 2

x1,x2 ≥ 0

|


SOLUCION


1. 6x1 +4x2 ¿ 24 2. x1+2 x2 =6

X1 0 4

X2 6 0

3 . –x1+x2=1 4. X2=2

X1 0 -1

X2 1 0


|


E. 4

E. 3E.2

E. 1

a f

d

e

c

b

X1 0 6

X2 3 0




x1 +3x2=k

x1+3x2=3

|


E.F.O

E. 4

E. 3E.2

E. 1

a f

d

e

c

b

X1 0 3

X2 1 0

Dentro de la solucion me interesa maximizar, la funcion objeto por lo tanto el punto mas lejano es el vertice del punto “D”, resolvemos la ecuacion y obtendremos los puntos.

x1+2x2=6 x2=2

x1+4=6

x1=6-2

X1=2 x2=2

Los puntos son: D(2,2), y si cumple con las rectricciones, por lo tanto es una solucion optima.

Max Z= x1+3x2

Max Z=8

Max Z= 6x1 +4x2

S:a:

6x1 + 4x2 ≤ 24

x1 + 2x2 ≤ 6

-x1 + x2 ≤ 1

x2 ≤ 2

x1,x2 ≥ 0

|


SOLUCION


1. 6x1 +4x2 ¿ 24 2. x1+2 x2 =6

X1 0 4

X2 6 0

3 . –x1+x2=1 4. X2=2

X1 0 -1

X2 1 0


|


E. 4

E. 3E.2

E. 1

a f

d

e

c

b

X1 0 6

X2 3 0




6x1 +4x2=k

6x1+4x2=24

|


E. 4

E. 3E.2

E. 1

a f

d

e

c

b

X1 4 0

X2 0 6

Dentro de la solucion me interesa maximizar, la funcion objeto por lo tanto el punto mas lejano es el vertice del punto “D”, resolvemos la ecuacion y obtendremos los puntos.

x1+2x2=6 x2=2

x1+4=6

x1=6-2

X1=2 x2=2

Los puntos son: D(2,2), y si cumple con las rectricciones, por lo tanto es una solucion optima.

Min Z= 0,31x1 +0,9x2

S:a:

x1 + x2 ≥ 800

0,21x1 – 0,30x2 ≤ 0

0,03x1 – 0,01x2 ≥ 0

x1,x2 ≥ 0

SOLUCION

|



1. x1 +x2 ¿ 800 2. 0,21 x1- 0,30 x2 =0

X1 0 800

X2 800 0

3 . 0,03x1-0,01x2=0

X1 1 2

X2 3 6


|


E.2

E.3

E.1

X1 5 10

X2 3,5 7

Para saber la posicion de los signos:

1. –x1+x2≥800

0+1000≥800 si cumple

2. 0,2x1- 0,30x2≤0

0-0.6≤0

-0,6≤0 si cumple

3. 0,03x1-0,01x2≥0

0,06≥0 si cumple




0,3x1 +0,9x2=k

0,3x1+0,9x2=9

|


B

A E

E

E

E.

X1 0 3

X2 1 0

Dentro de la solucion me interesa minimizar, la funcion objeto por lo tanto el punto mas lejano es el vertice del punto “A”, resolvemos la ecuacion y obtendremos los puntos.

X1 +x2=800 (100)*0,21x1-0,30=0

x1=800-x2 21(800-x2)+30x2=0

x1=800-329,41 16800-21x2-30x2=0

16800=51x2

X1=470,59 x2=329,41

Los puntos son: A(470,59; 329,41), y si cumple con las rectricciones, por lo tanto es una solucion optima.

Min Z= 0,30(470,59) + 0,90(329,41)

Minz=937,646

|


PROBLEMAS

EJERCICIO Nº 1:

Max z =200x1 + 150x2

X1 +2 x2 ≤ 80

3 x1 + 2 x2 ≤ 120

X1 , x2 ≥ 0

|


A) METODO SIMPLEX

Max = 200x1 + 150x2 +0S1 +0S2

s.a

X1 +2 x2 +S1 = 80

3 x1 + 2 x2 +S2= 120

V.Basicas

Z X1 X2 S1 S2 SOLUCIÓN

Z 1 -200

-150 0 0 0

S1 0 1 2 1 0 80S2 0 3 2 0 1 120

V.Basicas Z X1 X2 S1 S2 SOLUCIÓNZ 1 0 -50/3 0 200/3 8000S1 0 1 4/3 1 -1/3 40X1 0 1 2/3 0 1/3 40

Nueva Ecuación Z:

Ecuación Z Anterior 1 -200 -150 0 0 0-(-200)(N.Ec.Pivote) 0 200 400/3 0 200/3 8000

1 0 -50/3 0 200/3 8000

Nueva Ecuación S1:

Ecuación X1 Anterior 0 1 2 0 0 80

|


V.E.

Ecuación pivote

Elemento pivote

V.S.

80÷1=80

120÷3 =40

V.E.Ecuación

pivote

Elemento pivote

n.e.p.

V.S. 40÷4/3=3040÷2/3=60

-(1)(N.Ec.Pivote) 0 -1 -2/3 0 -1/3 -40

0 0 4/3 0 -1/3 40

V.Basicas

Z X1 X2 S1 S2 SOLUCIÓN

Z 1 0 25/3 25/2

425/6 8500

S1 0 0 3/2 3/4 -1/4 30X2 0 1 -1/3 -1/2 1/3 20

Nueva Ecuación Z:

Ecuación Z Anterior 1 0 -50/3 25/2 200/3 8000-(-50/3)(N.Ec.Pivote) 0 0 25 0 -25/6 500

1 0 25/3 25/2 425/6 8500

Nueva Ecuación S2:

Ecuación X1 Anterior 0 2 1/3 0 -1/3 40-(2/3)(N.Ec.Pivote) 0 -1 -2/3 0 -1/3 -40

0 1 1/3 0 -1/3 40

B) METODO GRAFICO

Max Z=200x1 + 150x2

(1)…………………………….. X1 +2 x2 ≤ 80

|


n.e.p.

x1 0 80 (0,40)x2 40 0 (80,0)

(2)…………………………….. 3 x1 + 2 x2 ≤ 120

x1, x2 ≥ 0

100

90

80

70

60

50

40 B

30 C

20

10

A D

10 20 30 40 50 60 70 80 90 100

Evaluación:

Vértice Z= 200x1 + 150x2

A(0,0) Z=0B(0,40) Z=8000C(20,30) Z=8500D(40,0) Z=8000

EJERCICIO Nº 2:

MAX. Z = 3X1 + 4 X2

X1 + 2 X2 ≤ 1000

3 X1 + 2 X2 ≤ 1800

|


Función Objetiva:

Z= 200x1 + 150x2

200x1 + 150x2=K

4x1 + 3x2=K

x1 0 3x2 4 0

x1 0 40 (0,60)x2 60 0 (40,0)

X2 ≤ 400

X1 , X2 ≥ 0

A) MÉTODO SIMPLEX

MAX. Z = 3X1 + 4 X2 + 0S1 + 0S2 + 0S3

S. a:

X1 + 2 X2 + S1 + 0 + 0 = 1000

3 X1 + 2 X2 + 0 + S2 + 0 = 1800

X2 + 0 + 0 + S3 = 400

V.Basicas Z X1 X2 S1 S2 S3 SOLUCIÓNZ 1 -3 -4 0 0 0 0S1 0 1 2 1 0 0 1000S2 0 3 2 0 1 0 1800S3 0 0 1 1 0 1 400

V.Basicas

Z X1 X2 S1 S2 S3 SOLUCIÓN

Z 1 0 -2 0 1 0 1800S1 0 0 4/3 1 -

1/30 400

X1 0 1 2/3 0 1/3 0 600S3 0 0 1 1 0 1 400

Nueva Ecuación Z:

Ecuación Z Anterior 1 -3 -4 0 0 0 0

-(-3)(N.Ec.Pivote) 0 0 2 0 1 0 1800

1 0 -2 0 1 0 1800

Nueva Ecuación S1:

|


V.S. 400÷4/3=300600÷2/3=900

400÷1=400

V.E.Ecuación

pivote

Elemento pivote n.e.p.

V.E.

V.S.

Ecuación pivote

Elemento pivote

1000÷1=10001000÷3=600

400÷0=Э

Ecuación S1 Anterior 0 1 2 1 0 0 1000

-(1)(N.Ec.Pivote) 0 -1 -2/3 0 -1/3 0 -600

1 0 4/3 1 -1/3 0 400

Nueva Ecuación S3:


-(0)(N.Ec.Pivote) 0 0 0 0 0 0 0

0 0 1 0 0 1 400

V.Basicas

Z X1 X2 S1 S2 S3 SOLUCIÓN

Z 1 0 0 3/2 -1/2

0 2400

X2 0 0 1 3/4 -1/4

0 300

X1 0 1 0 -1/2 1/2 0 400S3 0 0 0 -3/4 1/4 1 100

Nueva Ecuación Z:

Ecuación S1 Anterior 1 1 -2 0 1 0 1800

-(-2)(N.Ec.Pivote) 0 -1 2 3/2 -1/2 0 600

1 0 0 3/2 1/2 0 2400

Nueva Ecuación x1:

Ecuación x1 Anterior 0 1 2/3 0 1/3 0 600

-(2/3)(N.Ec.Pivote) 0 0 -2/3 -1/2 1/6 0 -200

0 1 0 -1/2 1/2 0 400

Nueva Ecuación S3:


-(1)(N.Ec.Pivote) 0 0 -1 -3/4 1/4 0 -300

0 0 0 -3/4 1/4 1 100

B) METODO GRAFICO

MAX. Z = 3X1 + 4 X2

|


n.e.p.

X1 0 1000X2 50

00

(1)……………………X1 + 2 X2 ≤ 1000

(2)…………………. 3 X1 + 2 X2 ≤ 1800

(3)………………… X2 ≤ 400

X1 , X2 ≥ 0

Evaluando:

|


300

100

200

400

500

600

700

800

900

1000

100 200 300 400 500 600 700 800 900 1000

B

A

C

D

X2

X1

X1 0 600X2 90

00

Vértice Z = 3X1 + 4 X2

A(0,0) Z=0B(0,500) Z=2000C(400,300) Z=2400D(400,0) Z=1200

Función Objetiva:

Z = 3X1 + 4 X2

3X1 + 4 X2 =k

3X1 + 4 X2 =12

|


X1 0 4X2 3 0

Los pasos básicos del método M son los siguientes:

1. Exprese el problema en forma estándar transformando las inecuaciones en ecuaciones introduciendo variables de holgura.

2. Agregue variables no negativas al lado izquierdo de cada una de las ecuaciones correspondientes a las restricciones de tipo (>=) o (=). Estas variables se denominan variables artificiales y su adición hace que las restricciones correspondientes.

Esta dificultad se elimina asegurando que las variables sean 0 en la solución final. Esto se logra asignando una penalización muy grande por unidad a estas variables en la función objetivo. Tal penalización se designará como –M para problemas de maximización y +M para problemas de minimización.

3. Utiliza las variables artificiales en la solución básica inicial; sin embargo la función objetivo de la tabla inicial se prepara adecuadamente para expresarse en términos de las variables no básicas únicamente. Esto significa que los coeficientes de las variables artificiales en la función objetivo deben ser 0 un resultado que puede lograrse sumando múltiplos adecuados de las ecuaciones de restricción al renglón objetivo.

4. Proceda con los pasos regulares del método simplex.

EJEMPLO:

Minimizar

|


Sujeto a:

Minimizar

Sujeto a:

Minimizar

Sujeto a:

Minimizar

Sujeto a:

V.B. Z X1 X2 X3 S1 S2 R1 SoluciónZ 1 -3 -2 -4 0 0 -M 0R1 0 2 2 3 -1 0 1 15S2 0 2 3 1 0 1 0 12

V.B. Z X1 X2 X3 S1 S2 R1 Solución

|


Z 1 -3+2M -2+2M -4+3M -M 0 0 15MR1 0 2 2 3 -1 0 1 15S2 0 2 3 1 0 1 0 12

Criterio para seleccionar la variable entrante:

Maximización : El valor mayor negativo del renglón Z.

Minimización : El valor mayor positivo del renglón Z.

V.B. Z X1 X2 X3 S1 S2 R1 SoluciónZ 1 -1/3 2/3 0 -4/3 0 4/3-M 20X3 0 2/3 2/3 1 -1/3 0 1/3 5S2 0 4/3 7/3 0 1/3 1 -1/3 7

V.B. Z X1 X2 X3 S1 S2 R1 SoluciónZ 1 -5/7 0 0 -10/7 -2/7 10/7-M 18X3 0 2/7 0 1 -3/7 -2/7 3/7 3X2 0 4/7 1 0 1/7 3/7 -1/7 3

EJEMPLO:

Maximizar

Sujeto a:

|


Maximizar

Sujeto a:

Maximizar

Sujeto a:

Maximizar

Sujeto a:

V.B. Z X1 X2 S1 S2 R1 R2 SoluciónZ 1 -4 -1 0 0 M M 0R1 0 3 1 0 0 0 0 3R2 0 4 3 -1 0 1 1 6S2 0 1 2 0 1 0 0 3

V.B. Z X1 X2 S1 S2 R1 R2 SoluciónZ 1 -4-7M -1-4M M 0 0 0 -9M

|


R1 0 3 1 0 0 0 0 3R2 0 4 3 -1 0 1 1 6S2 0 1 2 0 1 0 0 3

V.B. Z X1 X2 S1 S2 R1 R2 SoluciónZ 1 0 1/3-

5/3MM 0 4/3+7/3M 0 4-2M

X1 0 1 1/3 0 0 1/3 0 1R2 0 0 5/3 -1 0 -4/3 0 2S2 0 0 5/3 0 1 -1/3 1 2

V.B. Z X1 X2 S1 S2 R1 R2 SoluciónZ 1 0 0 1/5 0 8/5+M -1/5+M 18/5X1 0 1 0 1/5 0 3/5 3/5R2 0 0 1 -3/5 0 -4/5 3/5 6/5S2 0 0 0 1 1 1 -1 1

|


Éste método difiere del Simplex en que primero hay que resolver un problema auxiliar que trata de minimizar la suma de las variables artificiales. Una vez resuelto este primer problema y reorganizar la tabla final, pasamos a la segunda fase, que consiste en realizar el método Simplex normal.

FASE I: Se realiza la minimización de una función que está compuesta por la suma de los

valores de las variables artificiales; para el sistema aumentado del problema original. (Independientemente de qué función objetivo tenga el problema original).

Si en la solución óptima de la FASE I, el valor de las variables artificiales es de cero, se procede con la FASE II tomando la solución básica factible resultante.

Si alguna de las variables artificiales tiene un valor distinto a cero, el problema original es infactible.

FASE II: Utilizando la solución básica factible final de la FASE I, se resuelve el problema

original, esto es, se resuelve para la función objetivo del problema original; si se desea, se pueden eliminar las columnas artificiales.

Nótese que primeramente debe actualizarse correctamente el renglón cero para el conjunto de variables básicas que definió la FASE I.

Con la tabla en forma correcta se procede a optimizar de forma habitual siguiendo el algoritmo Simplex.

Nota: Si el valor mínimo de la función objetivo óptima es mayor que cero, el problema no tiene solución y termina anotándose que no existen soluciones factibles.

A modo resumen podemos dejar esta tabla, según la desigualdad que aparezca, y con el valor que deben estar las nuevas variables.

Tipo de desigualdad Tipo de variable que aparece

≥ - exceso + artificial

= + artificial

≤ + holgura

PROBLEMA 1:

Minimizar Z = 2000X1 + 500X2

|


Sujeto a:

SOLUCIÓN:

Minimizar Z = 2000X1 + 500X2

Sujeto a:

2X1 + 3X2 - S1 + 0S2 + R1 + 0R2 = 36 3X1 + 6X2 - 0S1 + S2 + 0R1 + R2 = 60

X1, X2, S1, S2, R1, R2 ≥ 0

FASE I:

Ahora para resolver como un problema de minimización:

Minimizar Z = 0X1 + 0X2 - 0S1 - 0S2 - R1 - R2 = 0

Sujeto a:

2X1 + 3X2 - S1 + 0S2 + R1 + 0R2 = 36 3X1 + 6X2 - 0S1 + S2 + 0R1 + R2 = 60

X1, X2, S1, S2, R1, R2 ≥ 0

TABLA 01:

Los coeficientes de las variables básicas en el segundo reglón no son correctos, de debe reducir a cero.

|


V.B. Z X1 X2 S1 S2 R1 R2 SoluciónZ 1 0 0 0 0 -1 -1 0R1 0 2 3 -1 0 1 0 36R2 0 3 6 0 -1 0 1 60

La nueva ecuación Z:

Ec. Z anterior: 1 0 0 0 0 -1 -1 0 -(-1)*(n.e.p): 0 2 3 -1 0 1 0 36

1 2 3 -1 0 0 -1 36

TABLA 02:


Ec. Z anterior: 1 2 3 -1 0 0 -1 36 -(-1)*(n.e.p): 0 3 6 0 -1 0 1 60

1 5 9 -1 -1 0 0 96

TABLA 03:

La tabla ya es correcta y con esta se resuelve por algoritmo simplex.

TABLA 04:

|


Coeficiente de mayor valor positivo de las variables no básicas

Menor valor positivo 60/6=10

Elemento pivote

V.B. Z X1 X2 S1 S2 R1 R2 SoluciónZ 1 2 3 -1 0 0 -1 36R1 0 2 3 -1 0 1 0 36R2 0 3 6 0 -1 0 1 60

V.B. Z X1 X2 S1 S2 R1 R2 SoluciónZ 1 5 9 -1 -1 0 0 96R1 0 2 3 -1 0 1 0 36R2 0 3 6 0 -1 0 1 60

V.B. Z X1 X2 S1 S2 R1 R2 SoluciónZ 1 5 9 -1 -1 0 0 96R1 0 2 3 -1 0 1 0 36R2 0 3 6 0 -1 0 1 60

Nueva ecuación pivote (n.e.p):


Ec. Z anterior: 1 5 9 -1 -1 0 0 96 -(9)*(n.e.p): 0 -

9/2-9 0 3/

20 -3/2 -

901 1/2 0 -1 1/

20 -3/2 6

La nueva ecuación R 1:

Ec. R1 anterior: 0 2 3 -1 0 1 0 36 -(3)*(n.e.p): 0 -

3/2-3 0 1/

20 -1/2 -

300 1/2 0 -1 1/

21 -1/2 6

TABLA 05: Primera iteración



Ec. Z anterior: 1 1/2 0 -1 1/2 0 -3/2 6 -(1/2)*(n.e.p): 0 -

1/20 1 -1/2 -1 1/2 -6

1 0 0 0 0 -1 -1 0

La nueva ecuación X 2:

Ec. X2 anterior: 0 1/2 1 0 -1/6 0 1/6 10 -(1/2)*(n.e.p): 0 -

1/20 1 -1/2 -1 1/2 -6

0 0 1 1 -2/3 -1 2/3 4

|


0 1/2 1 0 -1/6 0 1/6

10

V.B. Z X1 X2 S1 S2 R1 R2 SoluciónZ 1 1/2 0 -1 1/2 0 -3/2 6R1 0 1/2 0 -1 1/2 1 -1/2 6X2 0 1/2 1 0 -1/6 0 1/6 10

0 1 0 -2 1 2 -1 12

TABLA 06: Segunda iteración

Actualizando, la tabla es óptima, por lo tanto finaliza la FASE I y se tiene una solución básica factible.

FASE II:

Minimizar Z = 2000X1 +500X2 + 0S1 + 0S2

Z - 2000X1 -500X2 - 0S1 - 0S2 = 0

Se toma la solución básica factible de la FASE I como la solución inicial, se eliminan las columnas artificiales.

TABLA 01:

V. B. Z X1 X2 S1 S2 Solución

Z 1 -2000 -500 0 0 0

X1 0 1 0 -2 1 12

X2 0 0 1 1 -2/3 4

Se reduce a cero el coeficiente de las variables básicas para tener la tabla correcta.

TABLA 02:


Z 1 -2000 -500 0 0 0

X1 0 1 0 -2 1 12

X2 0 0 1 1 -2/3 4


Ec. Z anterior: 1 -2000 -500 0 0 0 -(-2000)*(n.e.p): 0 2000 0 -4000 2000 24000

1 0 -500 -4000 2000 24000

TABLA 03:

|


Columnas artificiales

V.B. Z X1 X2 S1 S2 R1 R2 SoluciónZ 1 0 0 0 0 -1 -1 0X1 0 1 0 -2 1 2 -1 12X2 0 0 1 1 -2/3 -1 2/3 4


Z 1 0 -500 -4000 2000 24000

X1 0 1 0 -2 1 12

X2 0 0 1 1 -2/3 4


Ec. Z anterior: 1 0 -500 -4000 2000 24000 -(-500)*(n.e.p): 0 0 500 500 -

1000/32000

1 0 0 -3500 5000/3 26000

TABLA 04:


Z 1 0 0 -3500 5000/3 26000

X1 0 1 0 -2 1 12

X2 0 0 1 1 -2/3 4

Actualizamos la tabla para verificar si es óptima.



Ec. Z anterior: 1 0 0 -3500 5000/3 26000 -(5000/3)*(n.e.p): 0 -

5000/30 -10000/3 -

5000/3-60000/3

1 -5000/3

0 -500/3 0 6000

La nueva ecuación X 2:

Ec. X2 anterior: 0 0 1 1 -2/3 4 -(-2/3)*(n.e.p): 0 2/3 0 -4/3 2/3 8

0 2/3 1 -1/3 0 12

TABLA 05: Primera iteración

|


Variables no básicas

Coeficiente de mayor valor positivo de las variables no básicas

Menor valor positivo 60/6=10

Elemento pivote

0 1 0 -2 1 12


Z 1 -5000/3 0 -500/3 0 6000

S2 0 1 0 -2 1 12

X2 0 2/3 1 -1/3 0 12

Solución óptima:

X1 = 0

X2 = 12

Z = 6000

PROBLEMA 2:

Maximizar

Sujeto a:

FASE I.

En la FASE I siempre es un problema de minimización.

Minimizar

Sujeto a:

TABLA 1:

V. Básica Z X1 X2 X3 S1 R1 SoluciónZ 1 0 0 0 0 -1 0S1 0 3 6 1 1 0 20R1 0 3 1 2 0 1 15

TABLA 2:

|


V. Básica Z X1 X2 X3 S1 R1 SoluciónZ 1 3 1 2 0 -1 15S1 0 3 6 1 1 0 20R1 0 3 1 2 0 1 15

TABLA 3:

V. Básica Z X1 X2 X3 S1 R1 SoluciónZ 1 0 0 0 0 -1 0S1 0 0 5 -1 1 -1 5X1 0 1 1/3 2/3 0 1/3 5

FASE II.

Maximizar

TABLA 1:

V. Básica Z X1 X2 X3 S1 SoluciónZ 1 -6 -4 -4 0 0S1 0 0 5 -1 1 5X1 0 1 1/3 2/3 0 5

TABLA 2:

V. Básica Z X1 X2 X3 S1 SoluciónZ 1 0 -2 0 0 30S1 0 0 5 -1 1 5X1 0 1 1/3 2/3 0 5

TABLA 3:

V. Básica Z X1 X2 X3 S1 SoluciónZ 1 0 0 -2/5 2/5 32X2 0 0 1 -1/5 1/5 1X1 0 1 0 11/15 -1/15 14/3

TABLA 4:

|


V. Básica Z X1 X2 X3 S1 SoluciónZ 1 6/11 0 0 4/11 380/11X2 0 3/11 1 0 2/11 25/11X1 0 15/11 0 1 -5/11 70/11

|


Éste método difiere del Simplex en que primero hay que resolver un problema auxiliar que trata de minimizar la suma de las variables artificiales. Una vez resuelto este primer problema y reorganizar la tabla final, pasamos a la segunda fase, que consiste en realizar el método Simplex normal.

Cada problema de programación lineal tiene un segundo problema asociado con él. Uno se denomina primal y el otro dual. Los 2 poseen propiedades muy relacionadas, de tal manera que la solución óptima a un problema proporciona información completa sobre la solución óptima para el otro.

Las relaciones entre el primal y el dual se utilizan para reducir el esfuerzo de cómputo en ciertos problemas y para obtener información adicional sobre las variaciones en la solución óptima debidas a ciertos cambios en los coeficientes y en la formulación del problema. Esto se conoce como análisis de sensibilidad o post-optimidad.

Definición del problema dual.

Para poder elaborar el problema dual a partir del primal, este se debe presentar en su forma canónica de la siguiente forma:

Maximizar

Sujeto a:

El problema dual se puede obtener a partir del problema primal y viceversa de la siguiente manera:

Cada restricción de un problema corresponde a una variable en el otro.

|


Los elementos del lado derecho de las restricciones en un problema son iguales a los coeficientes respectivos de la función objetivo en el otro.Un problema busca maximizar y el otro minimizar.

El problema de maximización tiene restricciones que y el problema de

minimización tiene restricciones que.Las variables en ambos casos son no negativas.

EJEMPLO:

Considere el problema primal siguiente:

Maximizar

Sujeto a:

Elaborar el dual a partir del primal.

Minimizar

Sujeto a:

Cuando el problema primal no está en forma canónica, es necesario hacer ajustes para poder presentarlo así. Los cambios más frecuentes son:

Si la función objetivo es minimizar, se puede transformar a una función objetivo de maximizar de la siguiente forma:

Minimizar

|


Maximizar

Una restricción mayor o igual que se transforma en una restricción menor o igual que de la siguiente manera:

Una restricción de igualdad se transforma en 2 inecuaciones.

Ejemplo: (Primal).

Maximizar

Sujeto a:

|


Maximizar

Sujeto a:

Dual

Minimizar

Sujeto a:

DESARROLLO DEL MÉTODO DUAL SIMPLEX.

Este método se aplica a problemas óptimos pero infactibles. En este caso, las restricciones

se expresan en forma canónica (restricciones ).

La función objetivo puede estar en la forma de maximización o de minimización. Después de agregar las variables de holgura y de poner el problema en la tabla, si algún elemento de la parte derecha es negativo y si la condición de optimidad está satisfecha, el problema puede resolverse por el método dual simplex. Note que un elemento negativo en el lado derecho significa que el problema comienza óptimo pero infactible como se requiere en el método dual simplex. En la iteración donde la solución básica llega a ser factible esta será la solución óptima del problema.

Condición de factibilidad.

La variable que sale es la variable básica que tiene el valor más negativo (los empates se rompen arbitrariamente si todas las variables básicas son negativas, el proceso termina y esta última tabla es la solución óptima factible).

Condición de optimidad.

La variable que entra se elige entre las variables no básicas como sigue. Tome los cocientes de los coeficientes de la función objetivo entre los coeficientes correspondientes a la ecuación asociada a la variable que sale.

Ignore los cocientes asociados a denominadores positivos o cero.

La variable que entra es aquella con el cociente más pequeño si el problema es de minimizar o el valor absoluto más pequeño si el problema es de maximización (rompa los

|


empates arbitrariamente). Si los denominadores son ceros o positivos el problema no tiene ninguna solución factible.

PROBLEMA:

Minimizar

Sujeto a:

Minimizar

Sujeto a:

TABLA 01:

V. Básica Z X1 X2 S1 S2 SoluciónZ 1 -2000 -1000 0 0 0S1 0 -3 -1 1 1 -40

S2 0 -2 -2 0 0 -60

TABLA 02:

V. Básica Z X1 X2 S1 S2 SoluciónZ 1 -1000 0 0 -500 30000S1 0 -2 0 1 -1/2 -10X2 0 1 1 0 -1/2 30

TABLA 03:

V. Básica Z X1 X2 S1 S2 SoluciónZ 1 0 -1000 -500 -250 35000

S1 0 1 -1 -1/2 1/ 4 5S2 0 0 -2 1/ 2 -5/4 25

|


|


PROBLEMA PRIMAL Y PROBLEMA DUAL

Cada problema de programación lineal lleva asociado un problema “dual” con el que prácticamente está muy relacionado.Para calcular el problema dual, partimos del problema de programación lineal expresado de la forma siguiente (habitual en todos nuestros problemas):

Maximizar la función objetivo: Z = c1x1 + c2x2 + …+ cnxn Poner las restricciones en la forma siguiente:

a11x1 + a12x2 + … + a1nxn <= b1a21x1 + a22x2 + … + a2nxn <= b2

…am1x1 + am2x2 + … + amnxn <= bm

El problema dual va a definirse de la siguiente forma:

Minimizar una función Z’ con unas variables distintas a Z y con los coeficientes derechos de las restricciones como coeficientes. Quedaría como sigue:

Z = b1y1 + b2y2 + …+ bnyno El problema dual tiene tantas variables como inecuaciones el sistema de

restricciones del problema primal.o Los coeficientes de la función objetivo del dual son los términos independientes

de las restricciones del primal.

Las restricciones quedarían de la forma siguiente:

a11y1 + a21y2 + … + am1yn >= c1a22y1 + a22y2 + … + am2yn >= c2…a1my1 + a2my2 + … + amnyn >= cn

o El sistema de restricciones del dual tiene tantas inecuaciones ligadas por el signo “>=” como variables tiene el primal.

|


o Los coeficientes de las inecuaciones del sistema de restricciones del problema dual son los mismos que los del sistema de restricciones del problema primal cambiando filas por columnas.

o Los términos independientes de las inecuaciones del sistema de restricciones del dual son los términos de la función objetivo del primal.

Un ejemplo de transformación primal/dual sería el que sigue:

Para hallar la correspondencia entre ambos problemas se suele utilizar la tabla primal dual o de Tucker. En ella se puede observar el problema primal por filas, es decir verticalmente. Por columnas, es decir horizontalmente, se observa el problema dual.

|


Para el ejemplo anterior tendríamos lo siguiente:

Como conclusión la transformación del problema primal en el dual (y viceversa) sería como sigue:

Mecánicamente el dual es formulado partiendo del problema primal en la siguiente forma:

Si el primal es un problema de Maximización, el dual es un problema de Minimización y viceversa.

1. Los coeficientes de la función objetivo del primal se convierten en las restricciones constantes de las ecuaciones del dual.

2. Las restricciones de las ecuaciones del primo se convierten en los coeficientes de la función objetivo del dual.

|


3. Los coeficientes de las variables del dual en las ecuaciones restrictivas son obtenidas sacando la transpuesta de la matriz de coeficientes del primo (los arreglos de los coeficientes en las columnas del primo se convierten en los coeficientes de las filas en el dual y viceversa).

4. Los signos de la desigualdad son invertidos.

5. Las Xn variables del primo son remplazadas por Wm variables en el dual.

Notación matemática

Primal Contiene m ecuaciones y n variables.Dual Contiene n ecuaciones y m variables.

La notación matricial del Primal es:Max Z = CX

Sujeto a :AX ≤ bX ≥ 0

La notación matricial del Dual es:Min G=bt W

Sujeto a :At W ≥ Ct

W ≥ 0

RELACION DE LOS PROBLEMAS PRIMO Y DUAL

|


METODOS PARA DETERMINAR LOS VALORES DUALES OPTIMOS

METODO I:

Valores óptimos de las variables duales

=Coeficiente

objetivos originalesX

Inversa primal optima

METODO II:

Coeficientes primal optimo

=Lado izquierdo de las

restricciones-

Lado derecho de las restricciones

EJERCICIO Nº 1:

Maximizar:

Z=5 x1+12 x2+4 x3

S.a:

x1+2 x 2+x 3≤10

2 x1 –2 x2+3 x3=8

x1 , x2 , x3≥0

Estandarizando, Ordenando y formado la diagonal:

Maximizar: Z=5 x1+12 x2+4 x3+0 x 4 – MR1

S.a:

x1+2 x 2+x 3+x 4≤10

2 x1 – x 2+3x 3+R1=8

|


x1 , x2 , x3 , x 4 , R1≥0

Despejando R1:

R1=8−2 x1+x2−3 x3

Reemplazando R1 en Z:


Maximizar :Z=5x 1+12x 2+4 x 3+0 x 4 – M (8−2 x1+x 2−3 x3)

Maximizar :Z=5x 1+12x 2+4 x 3+0 x 4 – 8M+2Mx 1−Mx 2+3Mx3

Maximizar :Z=(5+2M ) x1+(12−M ) x 2+(4+3M ) x3+0 x4 –8M

Por lo tanto tenemos:Maximizar :Z=(5+2M ) x1+(12−M ) x 2+(4+3M ) x3+0 x4 –8M

S.a:

x1+2 x 2+x 3+x 4≤10

2 x1 – x 2+3x 3+R1=8

x1 , x2 , x3 , x 4 , R1≥0

Construimos nuestra tabla:

V. BASICA Z X1 X2 X3 X4 R1 SOLUCION

Z 1 -5-2M -12+M -4-3M 0 0 -8M

X4 0 1 2 1 1 0 10

R1 0 2 -1 3 0 1 8

|


V.E.

Ecuación pivote

V.S.Elemento

pivote

Elemento Pivote 3

Ecuación Pivote 0 2 -1 3 0 1 8

N.E.P 0 2/3 -1/3 1 0 1/3 8/3

Hallando valores de z:

Ec. Z Ant. 1 -5-2M -12+2M -4-3M 0 0 -8M

-(-5-2M)(NEP)

0 2/3(4+3M) -1/3(4+3M) 4+3M 0 1/3(4+3M) 8/3(4+3M)

Nueva Ec. Z 1 -7/3 -40/3 0 0 4/3+M 32/3

Hallando valores de X4:

Ec. X4 Ant 0 1 2 1 1 0 10

-(1)(NEP) 0 -2/3 1/3 -1 0 -1/3 -8/3

Nueva Ec. X4 0 1/3 7/3 0 1 -1/3 22/3


Z 1 -7/3 -40/3 0 0 4/3+M 32/3

X4 0 1/3 7/3 0 1 -1/3 22/3

X3 0 2/3 -1/3 1 0 1/3 8/3


Z 1 -3/7 0 0 40/7 -4/7+M 368/7

|



Z 1 -7/3 -40/3 0 0 4/3+M 32/3

X4 0 1/3 7/3 0 1 -1/3 22/3

X3 0 2/3 -1/3 1 0 1/3 8/3

Elemento Pivote 7/3

Ecuación Pivote 0 1/3 7/3 0 1 -1/3 22/3

N.E.P 0 1/7 1 0 3/7 -1/7 22/7

X2 0 1/7 1 0 3/7 -1/7 22/7

X3 0 5/7 0 1 1/7 2/7 26/7


Ec. Ant de Z 1 -7/3 -40/3 0 0 4/3+M 32/3

-(-40/3)(NEP)

0 40/21 40/3 0 40/7 -40/21 880/21

Nueva Ec. Z 1 -3/7 0 0 40/7 -4/7+M 368/7


Ec. Ant de X3 0 2/3 -1/3 1 0 1/3 8/3

-(-1/3)(NEP) 0 1/21 1/6 0 1/7 -1/21 22/21

Nueva Ec. X3 0 5/7 0 1 1/7 2/7 26/7


Z 1 0 0 3/5 29/5 -2/5+M 274/5

X2 0 0 1 -1/5 2/5 -1/5 12/5

X1 0 1 0 7/5 1/5 2/5 26/5


Ec. Ant de Z 1 -3/7 0 0 40/7 -4/7+M 368/7

-(1/7)(NEP) 0 3/7 0 3/5 3/35 6/35 78/35

Nueva Ec. Z 1 0 0 3/5 29/5 -2/5+M 274/5


|


Elemento Pivote 5/3

Ecuación Pivote 0 5/7 0 1 1/7 2/7 26/7

N.E.P 0 1 0 7/5 1/5 2/5 26/5

Ec. Ant de X2 0 1/7 1 0 3/7 -1/7 22/7

-(1/7)(NEP) 0 -1/7 0 -1/5 -1/35 -2/35 -26/35

Nueva Ec. X2 0 0 1 -1/5 2/5 -1/5 12/5


S.a:

x1+2 x 2+x 3+x 4≤10Y 1

2 x1 – x 2+3x 3+R1=8Y 2

x1 , x2 , x3 , x 4 , R1≥0

Minimizar: Z=10Y 1+8Y 2

S.a:

Y 1+2Y 2≥5

2Y 1−Y 2≥12

Y 1+3Y 2≥4

Y 1≥0

Y 2≥−M

Y 1 ,Y 2≥0

TABLA PRIMAL ÓPTIMA

|



Z 1 0 0 3/5 29/5 -2/5+M 274/5

X2 0 0 1 -1/5 2/5 -1/5 12/5

X1 0 1 0 7/5 1/5 2/5 26/5

RESULTADO DUAL SIN DESARROLLAR EL DUAL

Valores óptimos de las variables duales

=Coeficiente

objetivos originalesX

Inversa primal optima

|


Matriz Inversa

= X

−15

25

25

15

12,5

= 12 x25+5 x

15;12 x

−15

+5x25

295;−25=

Resultado Desarrollando DUAL

Coeficientes primal optimo

=Lado izquierdo de las restricciones

-Lado derecho de las restricciones

Teniendo en cuenta las variables X4 y R1 de la Ec. DUAL

Restricciones X4: Y 1≥0

Restricciones R1: Y 2≥−M

Y de acuerdo a la tabla de X4 y R1 (Matriz Inversa Óptima) Valores de Z:

Coeficiente Z de X4 = 295

Coeficiente Z de R1 = −25

+M

Usamos La Formula:

PARA X4:295

=Y 1−O295

=Y 1

PARA R1:−25

+M=Y 2−(−M ) −25

=Y 2

|


ANEXOWinQSB

|


|


En aplicaciones prácticas a menudo ocurre que no solamente interesa la solución del problema propuesto sino también se desea saber cómo cambia esta solución si las condiciones iníciales del problema se modifican (por ejemplo si cambian los coeficientes de la función objetivo (cj), los recursos disponibles(bj) y la cantidad de recursos (aij) utilizada para producir una unidad de un producto.las investigaciones que tratan los cambios en la solución optima debido a cambios en los datos son llamadas análisis de sensibilidad . en cierto sentido el análisis de sensibilidad convierte la solución estática de programación lineal en un instrumento dinámico que evalúa las condiciones cambiantes. Por tanto adquiere mayor utilidad como instrumento administrativo ya que los negocios y las industrias están sometidos a cambios continuos y a una subsiguiente revaluación.Finalmente diremos que en el presente capitulo trataremos del análisis de sensibilidad que determina los rangos de variación de los (cj, bj, aij) para el cual la solución tal como se enuncio originalmente, permanece optima.

|


Un modelo de programación lineal es una foto instantánea de una situación real en la que los parámetros del modelo (coeficientes de la función objetivo y de las restricciones) asumen valores estáticos. Para aumentar la aplicación de la programación lineal en la práctica, se necesita agregar una dimensión dinámica que investigue el impacto que tiene hacer cambios en los parámetros del modelo (coeficientes de la función objetivo y de las restricciones) sobre la solución óptima. A este proceso se le llama análisis de sensibilidad, porque estudia la sensibilidad de la solución óptima respecto a los cambios que se hagan en el modelo.Trataremos sobre la investigación de dos casos de análisis de sensibilidad basados en la solución grafica de la programación lineal:

Los análisis más importantes son:1. Los coeficientes de la función objetivo; y 2. Los términos independientes de las restricciones y se pueden abordar por medio del Método Gráfico o del Método Simplex.

La función objetivo en general en un problema de programación lineal con dos variables se puede escribir como sigue:

Maximizaci ónoMinimizaci ó n z=c1 x1+c2 x2

Los cambios de c1 y c2 harán cambiar la pendiente de z y en consecuencia, posiblemente el

punto de esquina optima. Sin embargo hay un intervalo de variación tanto para c1 como

para c2, dentro del cual el óptimo del momento permanece sin cambio. En forma específica

nos interesa determinar el intervalo de optimalidad de la relación c1

c2

(o de c2

c1

) donde se

mantenga sin cambio la solución óptima del momento.

|


Gráficamente se mostrara en el siguiente ejemplo los efectos de cambiar los coeficientes de la función objetivo.

EJEMPLO 1.

Una fábrica de artículos para el hogar manufactura dos artefactos A y B.

Ambos sufren 3 procesos en el mismo orden que son:

Maquinado Armado Montaje

La disponibilidad de minutos diarios de cada proceso son 480, 600 y 450 respectivamente.

El artefacto A deja un beneficio de S/. 100/unidad en tanto que el B proporciona S/. 120/unidad

El cuadro de coeficientes de transformación es el que se indica a continuación:

Cuantos artefactos de A y B deben producir para obtener el máximo de beneficio?

SOLUCION:

Max Z=100 x1 +120x2

Sujeta a:

4 x1 +8 x2 ≤ 480

5 x1 +6 x2 ≤00

12 x1 +8 x2 ≤540

x1 , x2 ≥0

Gráficamente se tiene:

|


A B DISPONIBILIDAD

Maquinado 4 8 480

Armado 5 6 600

Montaje 12 8 540

Beneficio 100 120

100

100 x1 +120x2 =7500

56.25

40

20

20 40 60 120

7.5

Recordemos que las variables estructurales son aquellas con las que se planteo originalmente el problema de programación lineal, en nuestro caso: x1, x2 y x3; pero, dentro de las variables estructurales podemos distinguir variables básicas (x2 y x3) (aparecen en la primera columna de la tabla simplex final y definen la solución óptima)y variables no básicas (x1); entonces, el análisis de sensibilidad para los coeficientes de la función objetivo de estas variables depende de si la variable es básica o no.}

Este es el análisis más sencillo ya que si la variable es no básica, entonces tiene un coeficiente distinto de cero en la última fila de la tabla simplex final, este coeficiente es el máximo valor que el coeficiente de la función objetivo de dicha variable puede aumentar manteniendo la solución óptima.

Procedimiento:

a) Se lee de la tabla simplex final, el término que pertenece a la columna de la variable no básica en la última fila y se le resta una variable cualquiera.

|


3

1

2

b) Se plantea la condición de optimalidad; es decir, que este nuevo término debe ser positivo (mayor que cero) para que la solución siga siendo óptima.

c) Se resuelve la desigualdad.

d) Se suma a ambos lados de la desigualdad el coeficiente de la función objetivo que acompaña a la variable y este resultado es el intervalo de sensibilidad del coeficiente.

Análisis para la variable no básica x1:

Cuando las variables son básicas, el procedimiento para el análisis de sensibilidad varía un poco, pero conserva su lógica.

Procedimiento:

|


a) Se reemplaza el cero en la última fila de la columna de la variable por el negativo de la variable∆ (-∆) .

b) Ahora la tabla ya no es óptima, pues existe un elemento negativo en la última fila, por tanto normaliza la columna de la variable, es decir se debe generar un cero en la posición donde esta -∆ .

c) Se plantea la condición de Optimalidad; es decir, que todos los términos de la última fila de la tabal simplex deben ser positivos (mayor que cero) para que la solución siga siendo óptima .

d) Se resuelven las desigualdades individualmente y se interceptan los conjuntos soluciones.

e) Se suma a todos los lados de la desigualdad el coeficiente de la función objetivo que acompaña a la variable y este resultado es el intervalo de sensibilidad del coeficiente.

|


|


El problema relativo a encontrar el rango de sensibilidad de los términos independientes de las restricciones (recursos) se reduce al problema anterior sin mayor esfuerzo adicional recordando que en el dual los términos independientes del primal son precisamente los coeficientes de la función objetivo. Por lo tanto para analizar los efectos que originan variaciones en los valores de los recursos o restricciones procederemos del siguiente modo.

Al llegar a la solución optima del problema primal construimos la última tabla (optima) del problema dual planteado haciendo uso de la correspondencia entre dichas tablas.

En esta tabla optima del dual ensayaremos las variaciones de los coeficientes de la función objetivo de este problema con la técnica usada en el punto anterior (Sensibilidad de los Coeficientes de la función objetivo (cj)).

Para ilustrar estos conceptos utilizaremos el ejemplo anterior el dual de este ejemplo es:

Max Z=100 x1 +120x2

Sujeta a:

4 x1 +8 x2 ≤ 480 PRIMAL

5 x1 +6 x2 ≤00

12 x1 +8 x2 ≤540

x1 , x2 ≥0

Min w=480y1 +600 y2 +540 y3

Sujeto a: DUAL

4 y1 +5 y2 + 12 y3 ≥100

8 y1+ 6 y2 + 8 y3 ≥120

A partir de la solución óptima del problema primal se construye la última tabla (optima) del dual como se muestra a continuación:

|


SENSIBILIDAD DE b1

Para el rango superior de b1, en la tabla anterior se busca en la fila2 los a’ij >0ya que se trata de un problema de minimización y así ubicamos ½ y 1/8 también Z2-C2=225 y Z4-C4=15/2 .

Luego aplicamos:

b ' j=b j+[ ZJ−C J

|a ' ij| ]Debido a que existen dos a’ij >0; tenemos que encontrar 2 cocientes y de ellos escoger el mínimo esto es:

[ Z2−C2

|a 'ij| ]=2251/2

=450

[ Z4−C4

|a' ij| ]=15 /21/8

=60

Luego el rango superior es:

b’1 =480+60=540

para el rango inferior de b1

Se busca la fila 2 de la tabla anterior los a ' ij<0 y asi hallamos -3/16

Luego:

b’’1 =480 -225/43/16

=180

el rango de sensibilidad de b1 resulta:

180 < b1 <540

|


V. BASICA Y1 Y2 Y3 Y4 SOLUCION

Z 1 -225 0 -15/2 -225/4 7500

Y3 0 ¼ 1 -1/8 1/16 5

Y1 0 ½ 0 1/8 -3/16 10

SENSIBILIDAD DE b2

Debido a que y2 es una variable no básica utilizamos el concepto visto en la Sensibilidad de los Coeficientes de la Función Objetivo y de la tabla anterior se tiene:

Para el rango inferior:

b’’2 =b1-b2 =600-255=375

Límite superior no tiene, luego:

El rango de sensibilidad de b2 resulta:

375≤ b2 ≤ ∞

SENSIBILIDAD DE b3

El rango de sensibilidad de b3 resulta:

480≤ b3 ≤ 1440

|


El Problema de Trasporte se presenta frecuentemente a planear la distribución de bienes y servicios desde varias localizaciones de suministro hacia varias localizaciones de demanda.

|


La cantidad de bienes disponibles en cada localización de suministro (origen) es limitada.

La cantidad de bienes necesarios en cada una de las localizaciones de demanda (destino) es conocida.

E objetivo generalmente de minimizar costos de traslado de los bienes desde los orígenes hasta los destinos.

El modelo de transporte busca determinar un plan de transporte de una mercancía de varias fuentes a varios destinos. Los datos del modelo son:

1. Nivel de oferta en cada fuente y la cantidad de demanda en cada destino.

2. El costo de transporte unitario de la mercancía a cada destino.

Como solo hay una mercancía un destino puede recibir su demanda de una o más fuentes. El objetivo del modelo es el de determinar la cantidad que se enviará de cada fuente a cada destino, tal que se minimice el costo del transporte total.

La suposición básica del modelo es que el costo del transporte en una ruta es directamente proporcional al número de unidades transportadas. La definición de “unidad de transporte” variará dependiendo de la “mercancía” que se transporte.

El esquema siguiente representa el modelo de transporte como una red con m fuentes y n destinos. Una fuente o un destino está representado por un nodo, el arco que une fuente y un destino representan la ruta por la cual se transporta la mercancía. La cantidad de la oferta

|


Xij

en la fuente i es ai, y la demanda en el destino j es bj. El costo de transporte unitario entre la fuente i y el destino j es Cij.

Si Xij representa la cantidad transportada desde la fuente i al destino j, entonces, el modelo general de PL que representa el modelo de transporte es:

Minimiza Z= i=1 m j=1 n C i j X i j

Sujeta a:

j=1 n X i j <= ai , i=1,2,…, m

i=1 m X I j >= bj , j=1,2,…, n

X i j >=0 para todas las i y j

El primer conjunto de restricciones estipula que la suma de los envíos desde una fuente no puede ser mayor que su oferta; en forma análoga, el segundo conjunto requiere que la suma de los envíos a un destino satisfaga su demanda.

El modelo que se acaba de escribir implica que la oferta total i=1 m ai debe ser cuando menos igual a la demanda total j=1 n bj. Cuando la oferta total es igual a la demanda total, la formulación resultante recibe el nombre de modelo de transporte equilibrado. Este difiere del modelo solo en el hecho de que todas las restricciones son ecuaciones, es decir:

X i j = ai, i=1,2,..., m

X i j = bj, j=1,2,..., n

|


bn

b2

b1

an

a2

a1

.

.

.

.

Unidades

de

Oferta

Unidades

de

Demanda

N

2

1

N

2

1

DESTINOFUENTES

En el mundo real, no necesariamente la oferta debe ser igual a la demanda o mayor que ella. Sin embargo, un modelo de transporte siempre puede equilibrarse. El equilibrio, además de su utilidad en la representación a través de modelos de ciertas situaciones prácticas, es importante para el desarrollo del método de solución que explote completamente la estructura especial del modelo de transporte. Los dos ejemplos que siguen presentan la idea del equilibrio y también sus implicaciones prácticas.

Aunque la solución óptima de estos problemas y de cualquier problema de PL puede ser encontrada por el Método Simplex, el modelo de transporte tiene una estructura especial que permite resolverlos mucho más eficientemente.

El modelo de transporte en forma estándar se trabaja en una tabla similar a la que se presenta para un problema con tres bodegas y cuatro mercados

El algoritmo de transporte sigue exactamente los mismos pasos que el método simplex. Sin embargo, en lugar de usar la tabla simplex normal, se aprovecha la ventaja de la estructura especial del modelo de transporte para organizar los cálculos en una forma más cómoda.

Se debe agregar que el algoritmo especial de transporte fue desarrollado por primera vez cuando la norma eran los cálculos a mano, y se necesitaba soluciones”con método abreviado”. Hoy contamos con poderosos programas de cómputo que pueden resolver un modelo de transporte de cualquier tamaño en forma de programación lineal.

|


Los pasos del algoritmo de transporte son exactamente iguales a los del algoritmo simplex:

Paso 1: determinar una solución básica factible de inicio y seguir con el paso 2.

Paso 2: usar la condición de optimalidad del método simplex para determinar la variable de entrada entre todas las variables no básicas. Si se satisface la condición de optimalidad, detenerse. En caso contrario seguir en el paso 3.

Paso 3: usar la condición de factibilidad del método simplex para determinar la variable de salida entre todas las variables básicas en ese momento, y determinar la nueva solución básica. Regresar al paso 2.

La estructura especial del modelo de transporte permite asegurar que haya una solución básica no artificial de inicio, obtenida con uno de los cuatro métodos siguientes:

1.- Método de la Esquina Noreste (superior, izquierda).

2.- Método del Costo Mínimo.

3.- Método de Aproximación de Vogel.

4.- Método de Russell

|


La Compañía Minera Fernández S. A. debe abastecer mineral a 4 plantas procesadoras ubicadas en Piura (1), Trujillo (2), Lima (3), y Arequipa (4); las minas donde se extrae material están ubicadas en Cajamarca (A), Huaraz (B), Cerro de Pasco (C). Para el próximo año las plantas procesadoras requieren las cantidades del mineral que se presenta en el cuadro 1 ; así mismo los datos e capacidad de abastecimiento que las minas ofrecen a las

|


procesadoras se muestran en el cuadro (2) y en el cuadro (3) se presenta el costo de transporte por cada tonelada.

La compañía tiene como objetivo incurrir en el menor nivel de costo en el transporte de todo el mineral.

|


PLANTAMINERAL

TN

PIURA(1) 700

TRUJILLO(2) 300

LIMA(3) 800

AREQUIPA(4) 1200

MINATN

MINERALTN

CAJAMARCA(A) 1500

HUARAZ(B) 900

CERRO DE PASCO(C) 600

Todo problema de transporte se pueden resolver a través de un programa Lineal o mediante los algoritmos de transporte.

# Rutas = m + n – 1

m # de orígenesn # de destino

Además se debe de cumplir la de la Oferta = de la Demanda 3000 = 3000

1° Solución mediante un programa lineal.

|


MINADESTINO

1 2 3 4

A 11 18 15 14

B 17 8 20 12

C 15 16 13 22

ORIGEN DESTINO

700

1500

300 900

800 600

1200

Minimización z = XA1 + CA1 + XA2 + CA2 + XA3 + CA3 + XA4 + CA4

XB1 + CB1 + XB2 + CB2 + XB3 + CB3+ XB4 + CB4

XC1 + CC1 + XC2 + CC2 + XC3 + CC3 + XC4 +CC4

1) Demanda: Debe satisfacerse la demanda de cada planta

Restricciones en el Destino

XA1 + XB1 + XC1 ≥ 700

XA2 + XB2 + XC2 ≥ 300

XA3 + XB3 + XC3 ≥ 800

XA4 + XB4 + XC4 ≥ 1200

2) Oferta: La cantidad de elementos enviados no puede exceder la cantidad disponible

|


4

3

2

1

C

B

A

Restricciones en el Origen

XA1 + XA2 + XA3 + XA4

XB1 + XB2 + XB3 + XB4

XC2 + XC1 + XC3 + XC4

Sencillo y fácil de hacer. No tiene en cuenta los costos para hacer las asignaciones. Generalmente nos deja lejos del óptimo.

1. Construya una tabla de ofertas (disponibilidades) y demandas (requerimientos).

2. Empiece por la esquina noroeste.

3. Asigne lo máximo posible (Lo menor entre la oferta y la demanda, respectivamente)

4. Actualice la oferta y la demanda y rellene con ceros el resto de casillas (Filas ó Columnas) en donde la oferta ó la demanda haya quedado satisfecha.

5. Muévase a la derecha o hacia abajo, según haya quedado disponibilidad para asignar.

6. Repita los pasos del 3 al 5 sucesivamente hasta llegar a la esquina inferior derecha en la que se elimina fila y columna al mismo tiempo.

|


Se empieza en A1 y se trata de agotar el origen A, para luego continuar el origen B.

EVALUACION ECONOMICA

RUTAS CARGA COSTO TRANSPORTE

COSTO TOTAL

A1 700 11 7700

A2 300 18 5400

A3 500 15 7500

B3 300 20 6000

B4 600 12 7200

C4 600 22 13200

47000

|


VARIABLES BASICAS

XA1 700

XA2 300

XA3 500

XB3 300

XB4 600

XC4 600

VARIABLES NO BASICAS

XA4 0

XB1 0

XB2 0

XC1 0

XC2 0

XC3 0

Consiste en asignar tanto como sea posible a la celda que posea el costo mínimo o más pequeño. Una vez saturada la fila o columna correspondiente se saca del análisis y se continúa de la misma manera hasta completar la totalidad de la tabla. En caso de que haya uno o más costos iguales se escoge arbitrariamente cualquiera.

Es más elaborado que el método de la esquina noroeste

Tiene en cuenta los costos para hacer las asignaciones

Generalmente nos deja alejados del óptimo

1. Construya una tabla de disponibilidades, requerimientos y costos

2. Empiece en la casilla que tenga el menor costo de toda la tabla, si hay empate, escoja arbitrariamente (Cualquiera de los empatados).

3. Asigne lo máximo posible entre la disponibilidad y el requerimiento (El menor de los dos).

4. Rellene con ceros (0) la fila o columna satisfecha y actualice la disponibilidad y el requerimiento, restándoles lo asignado.

5. Recuerde que no debe eliminar ó satisfacer fila y columna al mismo tiempo, caso en que la oferta sea igual a la demanda, en tal caso recuerde usar la ε (Épsilon).

6. Muévase a la casilla con el costo mínimo de la tabla resultante (Sin tener en cuenta la fila o columna satisfecha).

7. Regrese a los puntos 3,4,5 sucesivamente, hasta que todas las casillas queden asignadas.

|




COSTO TOTAL

A1 700 11 7700

A3 200 15 3000

A4 600 14 8400

B2 300 8 2400

B4 600 12 7200

C3 600 13 7800

36500

|


VARIABLES BASICAS

XA1 700

XA3 200

XA4 600

XB2 300

XB4 600

XC3 600


XA2 0

XB1 0

XB3 0

XC1 0

XC2 0

XC4 0

Este método es heurístico y suele producir una mejor solución inicial que los métodos anteriores. De hecho, suele producir una solución inicial óptima, o próxima al nivel óptimo.

Es más elaborado que los anteriores, más técnico y dispendioso.

Tiene en cuenta los costos, las ofertas y las demandas para hacer las asignaciones.

Generalmente nos deja cerca al óptimo.

1. Construir una tabla de disponibilidades (ofertas), requerimientos (demanda) y costos.

2. Calcular la diferencia entre el costo más pequeño y el segundo costo más pequeño, para cada fila y para cada columna.

3. Escoger entre las filas y columnas, la que tenga la mayor diferencia (en caso de empate, decida arbitrariamente).

4. Asigne lo máximo posible en la casilla con menor costo en la fila o columna escogida en el punto 3.

5. Asigne cero (0) a las otras casillas de la fila o columna donde la disponibilidad ó el requerimiento quede satisfecho.

6. Repita los pasos del 2 al 5, sin tener en cuenta la(s) fila(s) y/o columna(s) satisfechas, hasta que todas las casillas queden asignadas.

|




COSTO TOTAL

A1 700 11 7700

A3 200 15 3000

A4 600 14 8400

B2 300 18 5400

B4 600 12 7200

C3 600 13 7800

39500

|


VARIABLES BASICAS

XA1 700

XA3 200

XA4 600

XB2 300

XB4 600

XC3 600


XA2 0

XB1 0

XB3 0

XC1 0

XC2 0

XC4 0

1. Construya una tabla de ofertas (disponibilidades) y demandas (requerimientos).

2. Por cada fila elegible determinar el mayor costo unitario de la fila.

3. Por cada columna elegible determinar el mayor costo unitario de la columna.

4. Calcular el evaluador:

Calcular (Mayor Costo Fila +Mayor Costo Columna - CIJ)

5.- Luego ver el mayor costo.

6.- Introducir las bases.

|


Se busca el mayor costo de fila y columna.

Calcular (Mayor Costo Fila +Mayor Costo Columna - CIJ); para los nuevos costos de las plantas y destinos, se tiene:

18 + 17 – 11 = 24 18 + 18 – 18 = 18 18 + 20– 15 = 23 18 + 22 – 14 = 26 20+ 17 – 17 = 20 20 + 18 – 8 = 30 20 + 20– 20 = 20 20 + 22 – 12 = 30 22 + 17 – 15 = 24 22 + 18 – 16 = 24 22 + 10 – 13 = 29 22 + 22 – 22 = 22 22 + 18 – 16 = 24

|


Introducimos la base X2,4(900,1200) = 900




Introducimos la base X1,3(500, 200) = 200


La solución por lo tanto es:

|




COSTO TOTAL

A1 700 11 7700

A2 300 18 5400

A3 200 15 3000

A4 300 14 4200

B4 900 12 10800

C3 600 13 7800

38900

|


VARIABLES BASICAS

XA1 700

XA2 300

XA3 200

X A4 300

XB4 900

XC3 600


X B1 0

XB2 0

XB3 0

XC1 0

XC2 0

XC4 0

|


Se inicia con la solución obtenida en la primera fase, se evalúa las rutas no utilizadas para determinar la conveniencia para incorporarla en el plan de transporte, sumando los costos de ruta positiva y restando los costos de la ruta negativa.

En cada cambio de ruta debe cumplirse que:1. La solución siga siendo factible y2. Que mejore el valor de la función objetivo

El procedimiento termina cuando no hay cambio de rutas que mejoren el valor de la función.Pasos a seguir:

Usar la solución actual (MEN, MAV o MCM) para crear una trayectoria única del paso secuencial. Usar estas trayectorias para calcular el costo marginal de introducir a la solución cada ruta no usada.

Si todos los costos marginales son iguales o mayores que cero, terminar; se tendrá la solución óptima. Si no, elegir la celda que tenga el costo marginal más negativo (empates se resuelven arbitrariamente)

Usando la trayectoria del paso secuencial, determine el máximo número de artículos que se pueden asignar a la ruta elegida en el punto 2 y ajustar la distribución adecuadamente.

Regrese al paso 1:a) Ponga un signo + en la celda de interés no ocupadab) Ponga un signo - en una celda usada de la misma filac) Ponga un + en una celda usada de la misma columna

El proceso continúa alternando los signos + y - tanto en las filas como en las columnas hasta que se obtenga una sucesión de celdas (trayectoria) que satisfagan dos condiciones1. Hay un signo + en la celda desocupada original de interés, y 2. Cualquier fila o columna que tenga un signo + debe tener también un signo - y viceversa.

O D1 2 3 4 OFERTA

|


A - -

700

-

- 300

+ + + +

- 500 + +7

1500

B

+ +1 + -15

- - - - -

+ 300

+ + +

- 600

900

C

+ -11 + -17 + -17

- - -

600

600

DEMANDA0 700 0 300 0 300 800 0 600 1200

3000

+14 - 15 + 20 – 12 = +7 +8 - 15 + 20 – 12 = -15+17 – 11 + 15 – 20 = +1+13 – 20 + 12 – 22 = -17+16 – 18 + 12 - 20 + 15 – 22 = -17+15 – 22 + 12 - 20 + 15 – 11 = -11

O D1 2 3 4 OFERTA

A + -10 1500

|


11 18

17 8

15 16

- - 700 - 300- + + + 500

B

+ +18 + +2 + -17 - - - 900

900

C

+ +6 + +0- + - - - 300 - + + 300

600

DEMANDA 0 700 0 300 0 300 800

0 600 1200

3000

+13 + 14 – 15 - 22=-10+20 + 22 – 13 - 12=+17+16 + 15 – 18 - 13=+0+15 – 13 + 15 - 11=+16+17 – 12 + 22 - 13 + 15 - 11=+18+8 – 12 + 22 – 13 + 15 - 18=+2

O D1 2 3 4 OFERTA

A + 300 1500

|


11 18

17 8

15 16

700 300- 500 200

B

+18 +2 +17 900

900

C

+6 +0

+ 300 600

- 300 0

600

DEMANDA 0 700 0 300 0 300 800

0 600 1200 3000

+ 20 + 14 - 15 - 12 = +7+ 8 - 12 + 14 - 18 = -8+17 – 12 + 14 – 11 = +8+ 16 – 13 +15 – 18 = +0+ 15 – 13 + 15 - 11 = +6+ 22 – 13 + 15 – 14 = +10+ 20 - 12 + 14 -15 = +7+ 22 - 13 + 15 – 14 = +10+ 16 – 8 + 12 – 14 = +6 + 15 – 11 + 15 – 13 = +6+ 17 – 12 + 14 – 11= +8

O D1 2 3 4 OFERTA

A

700 +8 200 600

1500

B +8 300 900

|


11 18

17 8

15 16

15 14

20 12

13 22

+7 600

C

+6 +6 600 +10

600

DEMANDA 0 700 0 300 0 300 800

0 600 1200 3000

O D1 2 3 4 OFERTA

A

700

-

300 0 200

+ 300 600

1500

B + -8 300 900

|


11 18

17 8

15 16

15 14

20 12

13 22

- 900 600

C

600

600

DEMANDA 0 700 0 300 0 300 800

0 600 1200

3000

+ 8 -18 + 14 -12 = 8

Prueba de OptimidadNo hay costos negativos por lo tanto es óptima



COSTO TOTAL

A1 700 11 7700

A3 200 15 3000

A4 600 14 8400

|


B2 300 8 2400

B4 600 12 7200

C3 600 13 7800

36500

1. Usar la solución actual (NE, MAV o MCM) y las siguientes operaciones (a) y (b) para determinar el costo marginal de enviar material para cada una de las rutas no usadas.

2. Asociar a cada fila un índice ui y a cada columna un índice vj

|


VARIABLES BASICAS

XA1 700

XA3 200

XA4 600

X B2 300

XB4 600

XC3 600


X A2 0

XB1 0

XB3 0

XC1 0

XC2 0

XC4 0

3. a) Hacer u1 = 0. Encuéntrese los índices de las filas u2, ..., um y los índices de las columnas v1, ...., vn tales que cij = ui + vj para cada celda usada.

4. b) Sea eij = cij - (ui+vj) para cada celda no usada; eij será el costo marginal de introducir la celda (ruta) i, j a la solución.Los pasos 2 a 4 son los mismos que en el método secuencial.

O D1 2 3 4 OFERTA

A

700 300 500

1500

B

300 600

900

C

600

600

DEMANDA 0 700 0 300 0 300 800

0 600 1200 3000

Paso 0: Asociar Índices

Rutas Costo Transporte Ecuación11 11 U1+V1=11

12 18 U1+V2=1813 15 U1+V3=1523 20 U2+V3=2024 12 U2+V4=1234 22 U3+V4=22

Paso 1.a) Solucionar la EcuaciónExisten 6 ecuaciones y siete variables entonces se hace U1 = 0 (puede ser cualquiera) y se determina el resto de los índices

|


11 18

17 8

15 16

15 14

20 12

13 22

V1 = 11 V2 = 18 U2 = 5 U3 = 15 V3 = 15 V4 = 7

Paso 1.b) Calcular los costos marginales para cada celda no usada.eij = cij - (ui + vj)

1) e14 = c14 - (u1 + v4)= 14 - (0 + 7) = 72) e21 = c21 - (u2 + v1)= 17 - (5 + 11) = 13) e22 = c22 - (u2 + v2)= 8 - (5 + 18) = -154) e31 = c31 - (u3 + v1)= 15 - (15+ 11) = -115) e32 = c32 - (u3 + v2)= 16 - (15+ 18) = -176) e33 = c33 - (u3 + v3)= 13 - (15 + 15) = -17

O D1 2 3 4 OFERTA

A

700 300 500 +7

1500

800 500 0

B+1 -15 - 300 + 600

900

600 0

C-11 -17 -17 + - 600

600

0

DEMANDA0 700 0 300 0 300 800 0 600 1200

3000

Paso 2: Prueba de Optimidad. Hay costos negativos por lo tanto no es óptimaLa ruta de reasignación es: +C33 –C23 +C24 –C34 (más negativo, -17)

Paso 3: Asignación de unidades a la ruta elegida.Disminuir 300 en la celda C34 y en la celda C33 aumentamos 300.Disminuir 300 en la celda C23 y en la celda C23 aumentamos 300.

O D1 2 3 4 OFERTA

A 1500

800 500 0

|


11 18

17 8

15 16

15 14

20 12

13 22

11 18

17 8

15 16

15 14

20 12

13 22

700 300 500

B0 900

900

600 0

C300 300

600

0

DEMANDA 0 700 0 300 0 300 800

0 600 1200 3000

Vuelva al Paso 1 Asociar Índices

Rutas Costo Transporte Ecuación 11 11 U1+V1=11

12 18 U1+V2=1813 15 U1+V3=1524 12 U2+V4=1233 13 U3+V3=1334 22 U3+V4=22

Paso 1.a) Solucionar la EcuaciónExisten 6 ecuaciones y siete variables entonces se hace U1 = 0 (puede ser cualquiera) y se determina el resto de los índicesV1 = 11 V2 = 18 U2 = -12 U3 = -2 V3 = 15 V4 = 24


1) e14 = c14 - (u1 + v4)= 14 - (0 + 24) = -102) e21 = c21 - (u2 + v1)= 17 - (-12 + 11) = 183) e22 = c22 - (u2 + v2)= 8 - (-12 + 18) = 24) e23 = c23 - (u2 + v3)= 20 - (-12+ 15) = 175) e31 = c31 - (u3 + v1)= 15 - (-2 + 11) = 66) e32 = c32 - (u3 + v2)= 16 - (-2 + 18) = 0

O D1 2 3 4 OFERTA

A + -10 1500

|


11 18

17 8

15 16

700 300 - 500800 500 0

B+18 +2 + +17 - 900

900

600 0

C+6 0 300 300

600

0

DEMANDA0 700 0 300 0 300 800 0 600 1200

3000



O D1 2 3 4 OFERTA

A

700 300 200 300

1500

800 500 0

B900

900

600 0

C 600 0 600

|


11 18

17 8

15 16

15 14

20 12

13 22

0

DEMANDA0 700 0 300 0 300 800 0 600 1200

3000



12 18 U1+V2=1813 15 U1+V3=1514 14 U1+V4=1424 12 U2+V3=1233 13 U3+V3=13

Paso 1.a) Solucionar la EcuaciónExisten 6 ecuaciones y siete variables entonces se hace U1 = 0 (puede ser cualquiera) y se determina el resto de los índicesV1 = 11 V2 = 18 U2 = -2 U3 = -2 V3 = 15 V4 = 14


1) e21 = c21 - (u1 + v4)= 17 - (-2 + 11) = -102) e22 = c22 - (u2 + v2)= 8 - (-2 + 18) = 183) e23 = c23 - (u2 + v3)= 20 - (-2 + 15) = 74) e31 = c31 - (u3 + v1)= 15 - (-2 + 11) = 65) e32 = c32 - (u3 + v2)= 16 - (-2 + 18) = 06) e34 = c34 - (u3 + v4)= 13 - (-2 + 14) = 1

O D1 2 3 4 OFERTA

A

700 - 300 200 + 300

1500

800 500 0

B+8 + -8 7 - 900

900

600 0

|


11 18

17 8

15 16

15 14

20 12

13 22

C+6 0 600 1

600

0

DEMANDA 0 700 0 300 0 300 800

0 600 1200 3000



O D1 2 3 4 OFERTA

A

700 200 600

1500

800 500 0

B300 600

900

600 0

C600

600

0

DEMANDA 0 700 0 300 0 300 800

0 600 1200 3000



13 15 U1+V3=1514 14 U1+V4=14

22 8 U2+V2= 824 12 U2+V4=1233 13 U3+V3=13

Paso 1.a) Solucionar la Ecuación

|


11 18

17 8

15 16

15 14

20 12

13 22

Existen 6 ecuaciones y siete variables entonces se hace U1 = 0 (puede ser cualquiera) y se determina el resto de los índicesV1 = 11 V2 = 10 U2 = -2 U3 = -12 V3 = 15 V4 = 14


1) e12 = c12 - (u1 + v2)= 18 - (0 + 10) = 82) e21 = c22 - (u2 + v1)= 17 - (-2 + 11) = 83) e23 = c23 - (u2 + v3)= 20 - (-2 + 15) = 74) e31 = c31 - (u3 + v1)= 15 - (-12 + 11) = 165) e32 = c32 - (u3 + v2)= 16 - (-12 + 10) = 186) e34 = c34 - (u3 + v4)= 22 - (-12 + 14) = 20

Paso 2: Prueba de OptimidadNo hay costos negativos por lo tanto es óptima



COSTO TOTAL

A1 700 11 7700

A3 200 15 3000

A4 600 14 8400

B2 300 8 2400

B4 600 12 7200

C3 600 13 7800

36500

|


VARIABLES BASICAS

XA1 700

XA3 200

XA4 600

X B2 300

XB4 600

XC3 600


X A2 0

XB1 0

XB3 0

XC1 0

XC2 0

XC4 0

Se resolvió el ejercicio planteado mediante WinQSB utilizando el Network Modeling.

|


|


INTRODUCCION

Se ha analizado la solución de los problemas de programación lineal por medio de los métodos simplex y del transporte. Existen sin embargo algunos casos especiales de problemas de programación lineal que pueden resolverse aplicando ciertas técnicas especiales que reducen enormemente los pesados cálculos que habrá que hacer aplicando los dos métodos anteriores. En este capítulo consideraremos uno de los tales casos el problema de la asignación que tiene muchas aplicaciones en los campos de la planificación y asignación de recursos.

EL PROBLEMA DE ASIGNACION

Los problemas de asignación presentan una estructura similar a los de transporte, pero con dos diferencias: asocian igual número de orígenes con igual número de demandas y las ofertas en cada origen es de valor uno, como lo es la demanda en cada destino.

El problema de asignación debe su nombre a la aplicación particular de asignar hombres a trabajos ( o trabajos a máquinas), con la condición de que cada hombre puede ser asignado a un trabajo y que cada trabajo tendrá asignada una persona.

La condición necesaria y suficiente para que este tipo de problemas tenga solución, es que se encuentre balanceado, es decir, que los recursos totales sean iguales a las demandas totales.

El modelo de asignación tiene sus principales aplicaciones en: Trabajadores, Oficinas al personal, Vehículos a rutas, Máquinas, Vendedores a regiones, productos a fabricar, etc.

SITUACION

Asignar m trabajos (o trabajadores) a n máquinas.

Un trabajo i (=1, 2, 3 ,...,m) cuando se asigna a la máquina j (=1,2,....,n) incurre en un costo cij.

El objetivo es asignar los trabajos a las máquinas uno a uno al menor costo.

La formulación de este problema puede considerarse como un caso especial del modelo de transporte.

DESCRIPCION

|


Los trabajos representan las “fuentes” y las máquinas los “destinos”.

La oferta disponible en cada fuente es 1 como también lo es la demanda en cada destino.

cij es el costo de transportar (asignar) el trabajo i a la máquina j .

El costo puede representar también características de competencia de cada trabajador.

En el caso que un trabajo no deba ser asignado (porque no cumple con los requisitos) a una máquina (actividad) en particular, este costo debe tener un valor alto (M)

En el caso de existir desequilibrio, esto es, más trabajos que máquinas o más máquinas que trabajos, hay que equilibrar con máquinas o trabajos figurados (ficticios), logrando de esta forma que m = n

EXPRESION MATEMATICA DEL MODELO

Xij = 0, si el i-ésimo trabajo no se asigna a la j-ésima máquina

1, si el i-ésimo trabajo se asigna a la j-ésima máquina

Máquina

1 2 …. n

1

Trabajo 2

……

n

Por lo tanto el modelo está dado por:

Minimizar z =

|


C11 C12 ….. C1n

C21 C22 ….. C2n

….. ….. ….. …..

Cn1 Cn2 ….. Cnn

∑i=1

n

∑j=1

n

c ij xij

Sujeto a i=1,2, ...,n

j=1,2,..n

xij = 0 ó bien 1

EJEMPLO DE APLICACIÓN

La gerencia general de RPG (ejemplo de transporte) con sede en Bruselas, este año, como parte de su auditoría anual, decidió que cada uno de sus cuatro vicepresidentes visite e inspeccione cada una de sus plantas de ensamblaje durante las primeras dos semanas de junio. Las plantas están ubicadas en Leipzig (Alemania), Nancy (Francia, Lieja (Bélgica) y Tilburgo (Holanda).

Para decidir a que vicepresidente enviar a una planta determinada, se asignaron puntos (costos) a cada uno de ellos de acuerdo a su experiencia, habilidades lingüísticas, tiempo que durará la inspección y otros. Estos datos se muestran en la siguiente tabla:

Plantear el modelo de PL

Ejemplo: Modelo de PL

MIN Z = 24 X11 + 10 X12 +... + 14 X43 + 13 X44

Sujeto a:

a) Oferta X11 + X12 + X13 + X14 = 1

|


∑j=1

n

x ij=1

∑i=1

n

x ij=1

X21 + X22 + X23 + X24 = 1

X31 + X32 + X33 + X34 = 1

X41 + X42 + X43 + X44 = 1

b) Demanda

X11 + X21 + X31 + X41 = 1

X12 + X22 + X32 + X42 = 1

X13 + X23 + X33 + X43 = 1

X14 + X24 + X34 + X44 = 1

c) No negatividad Xij >= 0 i=1,...,4, j=1,....,4

MÉTODOS DE SOLUCIÓN

Existen varias formas de obtener la solución:

a) Listar todas las alternativas posibles con sus costos y seleccionar la de menor costo (algoritmo exhaustivo)

b) Método Húngaro: método iterativo

Listar todas las alternativas

¿Cuántas alternativas posibles existen?

- El primer trabajo se puede asignar de n formas posibles

- El segundo de n-1 formas

- El último sólo de 1 forma

En total existen n! formas de hacer la asignación completa

MÉTODO HÚNGARO

Este algoritmo se usa para resolver problemas de minimización

Paso 0:

|


Construir la matriz de asignación

Para obtener la solución óptima cada nueva matriz de asignación debe satisfacer:

Propiedad 1: Todos los números son no negativos

Propiedad 2: Cada fila y cada columna tiene al menos una celda con un valor cero

Paso 1:

a) Reducción de filas: Restar el costo menor de cada fila a la fila correspondiente y/o

b) Reducción de columnas: Restar el costo menor de cada columna a la columna correspondiente

Con esto se crea una nueva matriz con las propiedades 1 y 2

Paso 2:

Determinar si la matriz es reducida (Prueba de Optimalidad).

Trazar el menor número de líneas rectas sobre las filas y columnas para cubrir todos los ceros.

Si el número de rectas es igual al número de filas o columnas se dice que esta matriz es reducida.

Si la matriz no es reducida pasar al paso 3, sino pasar al paso 4.

Paso 3: Movimiento

De todas las celdas no cruzadas identifique una con el menor valor y haga lo siguiente:

a) Restar el valor a cada celda no cruzada

b) Sumar el valor a cada celda de intersección de rectas

Volver al paso 2.

Paso 4: Solución óptima (Asignación)

Primero se asigna a las que tengan sólo una alternativa, se van marcando y así sucesivamente

Determinar el costo: Se suman todos los costos correspondientes a las asignaciones (o sumar todos los pi y qj).

¿Qué valor se obtiene al sumar todos los valores que se restaron en las reducciones de filas y columnas?

|


APLICANDO EL MÉTODO HÚNGARO AL EJEMPLO

Paso 0: Matriz de Asignación

Nota: En rojita los menores de cada fila

Paso 1: Reducción de filas y columnas

|


Filas

Paso 2: Determinar si la matriz es reducida

No es reducida: sólo tres rectas (para ser reducida deben ser 4)

Ir al paso 3

Paso 3: Movimiento (Seleccionar el menor: restar a las no tachadas, sumar a las intersecciones)

|


Columnas

Volver al paso 2!!

Iteración paso 2:

Se tachan todos los ceros con cuatro rectas, por tanto es óptima

Ir al paso 4!!

|


Paso 4: Asignación

Costo = c12 + c23 + c31 +c44

= 10+10+15+13 = 48

=10 + 10 + 15 + 11 + 1 + 1 = 48

MODELO DE ASIGNACIÓN: OTRAS CONSIDERACIONES

El modelo de asignación de RPG es un modelo de minimización en el cual el número de vicepresidentes es igual al número de plantas, y todas las asignaciones posibles son aceptables.

Consideremos ahora modelos tipo asignación donde no todas las condiciones anteriores se cumplen. En particular se considerarán situaciones en las que:

1 Hay una desigualdad entre el número de “personas” por asignar y el número de “destinos” que requieren personas asignadas.

2 Hay un modelo de maximización

3 Existen asignaciones inaceptables

OFERTAS Y DEMANDAS DESIGUALES

Cuando la oferta y la demanda son desiguales, se asigna una actividad ficticia con un costo de cero para mantener la condición de método que deben ser igual número de ofertas y demandas.

|


Costo=∑ pi+∑ q j

a) Oferta mayor que la demanda

b) Demanda mayor que la oferta

a.- Matriz de n x m (m<n). Algunas veces, el problema de la asignación se presenta en una forma en la que la matriz no es cuadrada. En tal caso es fácil convertir esta matriz en una cuadrada, como se hace en el siguiente ejemplo:

EJEMPLO

Una compañía dedicada al transporte de mercaderías mantiene flotas separadas de camiones para el transporte urbano y el interurbano. Los primeros realizan los servicios locales hasta las estaciones terminales de la cuidad, donde las cargas se distribuyen y se transfieren a los camiones interurbanos. La estación terminal tiene capacidad para acomodar a 6 camiones urbanos simultáneamente.

El situar cada camión en uno de los seis lugares implica un costo (de distribución y transferencia de cargas).

En un determinado día hay que situar simultáneamente cuatro camiones urbanos (numerados del 1 al 4 en el terminal), el cuadro 1 muestra la matriz de costos c que puede convertirse en una matriz cuadrada C, introduciendo dos camiones ficticios 5 y 6 como se ve en el cuadrado (2).

Como el situar estos camiones en cualquiera de los puntos no cuesta nada, los costos correspondientes son todos ceros.

CUADRO 1

Costo de la asignación de cada camión. (En dólares).

1 2 3 4

7

8

9

10

11

12

3

7

3

6

5

5

6

1

8

4

2

7

2

4

5

3

4

6

6

4

8

7

3

2

|


Lugar Camión

CUADRO 2.

1 2 3 4 5 6

7

8

9

10

11

12

3

7

3

6

5

5

6

1

8

4

2

7

2

4

5

3

4

6

6

4

8

7

3

2

0

0

0

0

0

0

0

0

0

0

0

0

CUADRO 3

Se escoge el menor costo de cada columna (camión) y este pase a restar a cada lugar de esa misma columna.

1 2 3 4 5 6

7

8

9

10

11

12

3-3=0

7-3=4

3-3=0

6-3=3

5-3=2

5-3=2

6-1=5

1-1=0

8-1=7

4-1=3

2-1=1

7-1=6

2-2=0

4-2=2

5-2=3

3-2=1

4-2=2

6-2=4

6-2=4

4-2=2

8-2=6

7-2=5

3-2=1

2-2=0

0

0

0

0

0

0

0

0

0

0

0

0

qi 3 1 2 2 0 0

CUADRO 4

Se obtiene los resultados calculados de la tabla anterior, y para llegar a la asignación optima se trazaran cuatro rectas pasadas por los ceros, siempre teniendo el menor costo de trazado

|


Lugar Camión

Lugar Camión

1 2 3 4 5 6

7

8

9

10

11

12

0

4

0

3

2

2

5

0

7

3

1

6

0

2

3

1

2

4

4

2

6

5

1

0

0

0

0

0

0

0

0

0

0

0

0

0

qi 3 1 2 2 0 0

La solución debe interpretarse de la siguiente forma:

El camión 1 es asignado al punto 9




Los puntos 10 y 11 se dejan vacantes.

El costo correspondiente a esta asignación es:

Z = 3 + 1 + 2 + 2 = 8

Z = 8 dólares

1. HAY UN MODELO DE MAXIMIZACIÓN

Considere un problema de asignación en el que la respuesta a cada asignación es una utilidad en vez de un costo. Considere la matriz de utilidades del problema como la característica nueva la cual consiste en que el número que aparece en cada celdilla representa un beneficio en lugar de un costo.

Para resolver este problema por el MÉTODO HÚNGARO solo tenemos que convertir la matriz C en la matriz Co de la siguiente manera:

Buscamos máx. Cij en la matriz C, construimos después la matriz Co mediante la siguiente transformación:

|


Lugar Camión

Cij (0 )=(maxCij )−Cij

La matriz Co tendrá al menos, un elemento nulo. Seguimos después el mismo procedimiento que para los problemas de minimización.

EJEMPLO:

Supongamos que la sociedad “MANPOWER”, se encarga de proporcionar trabajo femenino en una pequeña ciudad comercial.

Mantiene un personal asalariado de 4 mujeres (enumeradas de 1 al 4) que a demás de saber realizar muchos tipos de trabajos corrientes son expertas en sus propios campos de actividad. La sociedad mantiene una serie de jóvenes amas de casa que conocen diversos trabajos y que están dispuestas a trabajar sobre una base temporal de días en que hay que hacer más de 4 trabajos. A los clientes se les cobran los servicios según la actividad producida por las mujeres que las realizan (por ejemplo numero de cartas copiadas, numero de facturas preparadas, numero de pedidos enviados, etc.). En un determinado día, la compañía recibe encargo de sus clientes para la realización de 4 servicios (enumeradas de 5 a 8), conociéndose por la experiencia anterior, la productividad esperada de cada joven en los trabajos. Puede construirse una matriz C de beneficios que nos dé el beneficio esperado del día al asignar a la muchacha i (i=1, 2, 3, 4) al trabajo j (J=5, 6, 7, 8).

Cuadro Matriz de beneficios C en $.

Tarea5 6 7 8

Empleados

1 1 8 4 1

2 5 7 6 5

3 3 5 4 2

4 3 1 6 3

Aplicamos el procedimiento establecido:

Buscamos máx. Cij = 8

Cij (0 )=(maxCij )−Cij

Del Cual Tomaremos el menor costo de cada fila.

Tarea 5 6 7 8

|


Empleados

1 7 0 4 7

2 3 1 2 3

3 5 3 4 6

4 5 7 2 5

Después Seguimos con el Método Húngaro o Minimización pero con la variante del problema de la asignación:

De la tabla anterior tomamos el menor costo de la columna:

Tarea5 6 7 8

Empleados

1 7 0 4 7

2 3 1 2 3

3 5 3 4 6

4 5 7 2 5

Menor Costo 3 0 2 3

Del Cual obtendremos una Nueva tabla que sería este:

Tarea5 6 7 8

Empleados

1 4 0 2 4

2 0 1 0 0

3 2 3 2 3

4 2 7 0 2

|


De la tabla anterior tomamos el menor costo de la fila:

Tarea5 6 7 8

Menor Costo

Empleados

1 4 0 2 4 0

2 0 1 0 0 0

3 2 3 2 3 2

4 2 7 0 2 0

Del Cual obtendremos una Nueva tabla que sería este:

Tarea 56 7 8

Empleados

1 4 0 2 4

2 0 1 0 0

3 0 1 0 1

4 2 7 0 2

Y vemos que la tabla está completamente óptima para la solución del problema.

Tarea5 6 7 8

Empleados

1 4 0 2 4

2 0 1 0 0

3 0 1 0 1

4 2 7 0 2

|


La asignación óptima es:

La Empleada 1 es asignada a la tarea 6




El Beneficio esperado del día para esta asignación es:

z=C12+C 21+C34+C 42

z=8+5+2+7

z=$22

ANEXO

Utilizando el WinQSB

|


La oferta o suministro disponible en cada origen es limitada. En cada destino la demanda esta definida o especificada. El objetivo en el problema de transbordo es de determinar cuantas unidades deberán

embarcarse por cada uno de los barcos de la red, de manera que todas las demandas – destino se satisfagan al costo de transporte mínimo posible.

|


Igual que en los problemas de transporte se pueden formular problemas de transbordo con varias variantes.

Suministro total no igual a la demanda total. Maximización de la función objetivo. Rutas con capacidad limitada. Rutas inaceptables. Las modificaciones a los modelos de programación lineal requeridas para aceptar

esta variaciones son idénticas a las que se mencionaron para el problema de transporte.

Se trata de enviar bienes (cantidades) desde un punto i, a únicamente destinos finales j. El envío no se produce entre orígenes (oferta) o entre destinos (demanda), tampoco entre destinos a orígenes. El modelo de transbordo nos demuestra que resulta mas económico (minimizar costos) enviar a través de nodos intermedios o transitorios antes de llegare al punto de destino final.

Restricción en cada nodo transitorio:

Se construye una malla con orientación desde las fuentes (nodos de inicio) hacia los destinos (nodos de llegada), utilizando amortiguadores (nodos transitorios) que permiten recibir y transferir recursos. Las flechas que unen los nodos de la malla representan los eventuales flujos de recursos en la secuencia de distribución.

Luego, la malla permite convertir un modelo de transbordo en un modelo de transporte regular y resolverse como tal, utilizando los amortiguadores

Así, la malla reconoce tres tipos de nodos:

• Nodos puros de Oferta: Solo transfieren recursos.

• Nodos de Transbordo: Entregan y reciben recursos.

|


suma flujos entrantes = suma flujos saliente

• Nodos puros de Demanda: Sólo reciben recursos.

El amortiguador debe ser suficientemente grande para permitir que los recursos se transfieran desde las fuentes hacia los destinos.

Inicialización: Encuentre un plan de embarque factible que satisfaga todas las restricciones de suministro y demanda, al mismo tiempo que mantiene un equilibrio en todos los nodos de transbordo.

Prueba de Optimalidad: Pruebe el plan de embarque actual para ver si es óptimo, es decir, si es el plan que incurre en los costos totales mínimos. Si es así, deténgase con la solución óptima, sino vaya al paso 3.

Movimientos: Use el hecho de que el plan de embarque actual no es óptimo para crear un nuevo plan de embarque factible con menos costo total que el actual. Vaya al paso 2.

Los pasos del algoritmo son análogos a los del algoritmo de pasos sucesivos (escalón).• Tanto los nodos origen como los destinos pueden ser a su vez nodos de transbordo.• Al igual que el modelo de transporte, puede haber desequilibrio, en ese caso se agregan

fuentes o destinos ficticios con costo cero.• El número total del sistema está dado por el total de la oferta o de la demanda.• A cada nodo de transbordo se asigna un suministro (demanda) igual a su suministro

(demanda) original (cero, si no coincide originalmente con un destino) más el total de unidades del sistema. Esto permite que todas las unidades puedan pasar por un empalme dado.

Un esquema simple del modelo de transbordo se expresa como una red de modelo de asignación:

|


|

F3

F2

F1

Nodos de Transbordo

A2

A1

Nodos puros de Demanda

Nodos puros de Oferta


1) Con Los datos que se muestra en el siguiente cuadro tendremos que desarrollar el método de transbordo.

Igualamos la oferta y la demanda mediante la creación de una planta de producción ficticia.

A continuación aplicamos el método de Vogel

|


Z = 20(36) + 60(36) + 60(34) + 30(0) + 20(0) = 4.920

Solución Optima:

X12 = 20X13=60X23= 60X31=30X33=20X34=40Z=4.290

De acuerdo a la matriz de costos y al gráfico presentado en el problema 6 del capítulo de formulación, las unidades deberán ser despachadas así:

Desde la planta de producción P1 , enviar 20 monitores de alta resolución al centro de ventas V2 , a través del centro de control de calidad C1.

Desde la planta de producción P1, enviar 60 unidades al centro de ventas V3, a través del centro de control de calidad C2..

|


Desde la planta de producción P2, enviar 60 unidades al centro de ventas V3, a través del centro de control de calidad C2 .

Costos totales : 20 * 12 +20 * 4 +20 * 20 = 720

60 * 11 + 60 * 6 + 60 * 19 = 2160 60 * 9 + 60 * 6 + 60 *19 = 2040

$4920

2) Una fábrica posee dos plantas de manufactura, una en Memphis y otra en Denver.La planta de Memphis puede producir hasta 150unidades al día, la de Denver hasta 200 unidades al día. Los productos son enviados por avión a Los Ángeles y Boston. En ambas ciudades, se requieren 130 unidades diarias. Existe una posibilidad de reducir costos enviando algunos productos en primer lugar a New York o a Chicago y luego a sus destinos finales. Los costos unitarios de cada tramo factible se ilustran en la siguiente tabla:

DESTINO

|


ORIGEN

La fábrica desea satisfacer la demanda, minimizando el costo total de envío. En este problemas, Memphis y Denver son puntos de oferta de 150 y 200 unidades respectivamente. New York y Chicago son puntos de transbordo. Los Ángeles y Boston son puntos de demanda de 130 unidades cada uno.

A continuación construiremos un problema de transporte balanceado a partir del problema de transbordo. Para ello podemos seguirlos siguientes pasos(suponiendo que la oferta excede a la demanda):

|


Paso1. Si es necesario, se debe agregar un punto de demanda ficticio (con oferta 0 y demanda igual al excedente) para balancear el problema. Los costos de envío al punto ficticio deben ser cero. Sea S la oferta total disponible.

Paso2.Construir una tabla de transporte siguiendo las siguientes reglas:

Incluir una fila por cada punto de oferta y de transbordo. Incluir una columna por cada punto de demanda y de transbordo. Cada punto i de oferta debe poseer una oferta igual a su oferta original si. Cada

punto de demanda j debe poseer una demanda igual a su demanda original dj. Cada punto de transbordo debe tener una oferta igual a su oferta original +S y una

demanda igual a su demanda original + S. Como de antemano no se conoce la cantidad que transitaría por cada punto de transbordo, la idea es asegurar que no se exceda su capacidad. Se agrega S a la oferta y a la demanda del punto de transbordo para no des balancear la tabla.

En el ejemplo, S= 150 +200 = 350.La demanda total es 130+130=260.Luego,el punto ficticio debe tener una demanda=90.

Como en el ejemplo los puntos de transbordo no tienen ni demanda ni oferta por sí mismos, la oferta y demanda en la tabla deber ser iguales.

Una vez planteado la tabla, se pueden emplear los métodos vistos anteriormente para obtener una solución inicial factible y obtener la solución óptima.

|


3) Teniendo el siguiente esquema de trasbordo, los nodos 1 y 3 envían (origen) y los nodos 4 y 5 reciben (destino). Hallar la solución óptima usando el modelo de trasbordo.

|


F.O. Min z= 8X15 +5X13 +3X12 +4X23 +3X24 +2X35+2X34 +4X45

Clases de nodos:

Origen puro : Nodo 1

Destino puro : Nodo 5

Intermedio : Nodos 2, 3 y 4

En el tablero se eliminan: la columna 1 por ser de origen puro; y la fila 5 por ser destino puro, reduciéndose en una matriz de 4 x 4.

40+20 = 50 +10

B = 60 (Suma de orígenes o suma de destinos)

En el tablero colocamos los costos de cada origen a cada destino, según se indica en la red inicial.

|

OFERTA

3 5 8

0 4 3

0 2 2

4

DEMANDA 10 50

DESTINO

ORIGEN

40

203

4

2 3 4 5

1

2


Las x significan que no se asigna ningún costo; quedando el tablero para ser resuelto como un modelo de transporte.

Luego agregamos B a los nodos intermedios, de la fila y columna, Siendo B =60.

Resolviendo el tablero (MÉTODO DE VOGEL) queda de la siguiente manera:

OFERTA P1 P2 P3 P4

3 5 x 8

0 4 3 x

x 0 2 2

x x 0 4

DEMANDAP1P2P3P4

60 10 0 60 30 0 70 10 0 50 0

33

41

13

3 4 2 26143

2

3

2

2

3

4

2

3

2 2

3

2

DESTINO

ORIGEN

40 30 0

60 50 0

80 30 0

60 0

3

4

2 3 4 5

30 50

60

1 10 30

50 102

La red de distribución del transbordo o esquema óptimo de transbordo, se muestra a continuación:

|


Z= 3 * 10 + 5 * 30 + 2 * 50 + 3 * 10 = 310

El costo total del modelo de trasborde es: Z = 310

Colocamos el nombre del ejercicio e insertamos cuantos nodos vamos a utilizar.

|


Solución de la tabla de los nodos o rutas utilizadas.

|


Trabajando con la tabla del Método de VOGEL

Solución de la Grafica del ejercicio aplicado.

|


Muchos de los problemas de la vida real exigen soluciones con númerosentero, por lo tanto las variables de dicho problema deben ser definidas como variables enteras. Los métodos de solución que contemplaremos en éste capitulo son: Método de los planos cortantes de Gomory, Método de Bifurcación y Acotación (Branch AndBound), el Método de Egon Balas en donde las variables son de carácter binario (0,1). Por último se ilustra el uso del software WinQsb para atender éste tipo de problema.

|


Un enfoque primitivo de resolución consiste en evaluar cada una de las combinaciones de valores enteros para las variables del problema. Pero en este caso, analizar diez variables y diez valores en un problema tendríamos un número grande (diez mil millones) de posibles soluciones, lo que hace necesario planteamientos de solución inteligentes.

Estos se han dirigido por una parte hacia los "métodos exactos", es decir, aquellos que conducen a una solución óptima exacta para el problema combinatorio empleando técnicas que reduzcan la búsqueda de soluciones.

Los modelos de programación entera son una extensión de los modelos lineales en los que algunas variables toman valores enteros. Con frecuencia las variables enteras solo toman valores en 0-1 ya que este tipo de variables permiten representar condiciones lógicas.

Este tipo de modelos permite representar modelos mucho más complejos, aunque la resolución de los mismos se complica excesivamente. No se puede utilizar la suavidad de las funciones para inferir el comportamiento de las mismas cerca del óptimo. Siendo así que problemas con una sola decenas de variables pueden ser casi imposibles de resolver.

Si se requiere que todas las variables sean enteras, se dice que se habla de Programación Lineal Entera Pura; si se necesita que algunas de las variables de decisión sean números enteros, se tiene un problema de Programación Lineal Entera Mixta. En algunas aplicaciones, sólo se permite que todas las variables tomen valores de cero o uno, hablamos en estos casos de Programación Lineal Entera Binaria (Digital).

Programación entera es programación lineal con la restricción adicional de que los valores de las variables de decisión sean enteros.Un modelo de Programación Entera (PE) permite abordar aplicaciones donde la solución tiene sentido si una parte o todas las decisiones toman valores restringidos a números enteros.Un problema de PLE puede describirse de la siguiente forma:

|


Donde: x - variable entera.c - coeficientes de la función objetivo.A - coeficiente de la restricción.b - término independiente.

Si se requiere de todas las variables sean enteras, se dice que se habla de Programación Lineal Entera Pura; si se necesita que algunas de las variables de decisión sean números enteros, se tiene un problema de Programación Lineal Entera Mixta.

En algunas aplicaciones, solo se permite que todas las variables tomen valores de cero o uno, hablamos en estos casos de Programación Lineal Entera Binaria (Digital).

Si consideramos que estamos en un modelo de Programación Entera (puro o mixto) y resolvemos el modelo de Programación Lineal asociado (esto es, admitiendo valores continuos para las variables), estaremos obtenido la solución de la Relajación Continua del modelo entero. Para un modelo de maximización, la relajación continua nos proporciona una cota superior del valor óptimo del modelo de Programación Entera asociado.

En el caso particular que la Relajación Continua nos proporcione una solución entera, entonces ésta será también la solución del modelo de Programación Entera asociado. En caso contrario deberemos utilizar alguna estrategia o algoritmo para obtener la solución del modelo de PE.

A pesar del impresionante avance en nuestra capacidad para resolver problemas de programación entera, la tecnología aun dista mucho de la que hay disponible para manejar problemas en los que no es necesario que las variables de decisión sean enteras. Muchos problemas que se resuelven fácilmente como problemas de programación lineal llegan a ser irresolubles para propósitos prácticos cuando se exige que las variables de decisión sean enteras (es decir, que el tiempo y el costo necesario para los cálculos resultan demasiado grandes).

|


Programación Entera es un término general para los modelos de programación matemática que presentan condiciones de integridad (condiciones que estipulan que algunas o todas las variables de decisión deben tener valores enteros). Ya hemos apuntado que los modelos de programación lineal entera son modelos de programación lineal que tienen la característica adicional de que algunas de las variables de decisión deben tener valores enteros. Existen diversas clasificaciones de esta categoría de modelos.

1. Programas Enteros Puros

Un modelo entero puro (PLE) es, como su nombre lo indica, un problema en el que se exige que todas las variables de decisión tengan valores enteros. Por ejemplo

Min z = 6x1 + 5x2 + 4x3 s.a.

108x1 + 92x2 + 58x3 ≥5767x1 + 18x2 + 22x3 ≥ 83x1, x2, x3 ><0 y enteros

Es un modelo entero puro. Sin las restricciones adicionales de que x1, x2, x3 sean enteras (o sea las condiciones de integralidad) sería un problema de programación lineal.

2. Programas Enteros Mixtos

Un problema en el que solo se requieren que algunas variables tengan valores enteros mientras que otras pueden asumir cualquier numero no negativo (es decir, cualquier valor continuo) se llama programación lineal entera mixta (PLEM). Por ejemplo, supóngase que en el problema anterior solo x1 y x2 deben ser enteros y x3 no. El problema resultante es:

Min z = 6x1 + 5x2 + 4x3

s.a. 108x1 + 92x2 + 58x3 ≥ 576

7x1 - 18x2 + 22x3 ≥ 83x1, x2, x3 ≥0; x1 y x2 enteros

3. Programas Enteros 0-1 O Binaria

|


En algunos problemas se restringe el valor de las variables a 0 o 1. Dichos problemas se llaman binarios o programas lineales enteros 0-1. Son de particular interés debido a que se pueden usar las variables 0-1 para representar decisiones dicotómicas (sí o no). Diversos problemas de asignación, ubicación de plantas, planes de producción y elaboración de cartera, son de programación lineal entera 0-1.

Min z = 6x1 + 5x2 + 4x3

s.a. 108x1 + 92x2 + 58x3 ≥ 576

7x1 - 18x2 + 22x3 ≥ 83x1, x2, x3 = 0, 1; x1, x2 , x3 enteros

Los algoritmos de programación lineal entera se basan en el aprovechamiento del gran éxito computacional de la programación lineal. Es la estrategia de esos algoritmos intervienen tres pasos.

Paso 1.- Relajar el espacio de soluciones del programa lineal entero omitiendo la restricción entera en todas las variables enteras, y sustituyéndola con cualquier variable binaria y que tenga el intervalo continuo 0 ≤ y ≤ 1 . El resultado de relajamiento es un programa lineal normal.

Paso 2.- Resolver el programa lineal e identificar su optimo continuo.

Paso 3.- Iniciar en el punto optimo continuo e ir agregando restricciones especiales que modifiquen en forma iterativa el espacio de soluciones del programa lineal, en una forma que al final produzca un punto extremo que satisfaga los requisitos enteros.

Se han desarrollado dos métodos generales para obtener las restricciones especiales del Paso 3.

1. Método de Ramificación y Acotamiento ( B & B, de Branch – and – Bound).2. Método del plano cortante.

|


El primer algoritmo B & B fue desarrollado por A. Land y G. Doig en 1960, para el problema general de programación lineal entera mixta y pura. Después, en 1965, E. Balas desarrolló el algoritmo aditivo para resolver problemas de programa lineal entero con variables binarias (cero o uno) puras. Los cálculos del algoritmo aditivo eran tan sencillos (principalmente suma y resta) que se le aclamó como un gran avance en la solución del programa lineal entero. Desafortunadamente, el algoritmo no pudo materializar las ventajas computacionales. Además se demostró que el algoritmo, que al principio pareció no estar relacionado con la técnica B & B , no es más que un caso especial del algoritmo general de Land y Doig.

Se presentará sólo el algoritmo general B & B de Land y Doig; seguidamente se explicará detalladamente el ejercicio.

EJERCICIO 1.-

Maximizar z= 5x1 + 4x2

x1 + x2 ≤ 5 10 x1 + 6x2 ≤ 45 x1 , x2 es entero no negativo

Los puntos de red de la Figura 1 definen el espacio de soluciones del programa lineal entero, el problema lineal asociado, el “0 “, se define eliminando las restricciones enteras. Su solución óptima es:

x1 = 3.75 x2 =1.25 z = 23.75Como la solución optima del programa lineal 0 no satisface los requisitos de valores enteros, el algoritmo de ramificación y acotamiento modifica el espacio de soluciones de tal manera que al final se identifica el programa lineal entero óptimo.

Figura 1.- Espacio de soluciones de programa lineal entero del ejemplo.

|


Primero seleccionaremos una de las variables cuyo valor corriente en la solución óptima no cumple el requisito de valor entero. Si se selecciona x1 =3.75 en forma arbitraria, observamos que la región 3 < x1 < 4 del espacio de soluciones del programa 0 no contiene valores enteros de x1 y podemos modificar el espacio de soluciones lineales eliminando esta región no prometedora. Esto equivale a reemplazar el programa lineal 0 original con dos nuevos programas lineales o espacios, PL1 y PL2, definidos de la manera siguiente:

1. Espacio PL1 = espacio PLO + (x1 ≤ 3)2. Espacio PL2 = espacio PLO + (x1 ≥ 4)

Esta figura muestra los espacios PL1 y PL2 en forma grafica. Se ve que los dos espacios contienen los mismos puntos enteros factibles del modelo PLE. Esto significa que, desde el punto de vista del problema original de PLE, tratar con PL1 y PL2 es igual que tratar con el original PLO. La diferencia principal es que la selección de las nuevas restricciones e acotamiento ( x1 ≥ 3 y x1 ≤ 4 ) mejoraran la oportunidad de forzar a los puntos extremos óptimos de PL1 y PL2 hacia la satisfacción del requisito de valor entero. Además el hecho que las restricciones de acotamiento están en la “vecindad inmediata” del optimo continuo del PLO, incrementara las posibilidades de producir “buenas” soluciones enteras.

|


Las nuevas restricciones x1 ≤ 3 y x1 ≥ 4 son mutuamente excluyentes, PL1 y PL2 deben tratarse como dos programas lineales separados. Esta dicotomía da lugar al concepto de ramificación en el algoritmo de Ramificación y Acotamiento, como se ve en la figura 2. En efecto, ramificar significa subdividir un espacio de soluciones corrientes en subespacios mutuamente excluyentes.

Aquí vemos las ramas PL1 y PL2 y x1 llamada variable de ramificación

Sabemos que la solución óptima entera debe encontrarse en PL1 o PL2. Sin embargo, en ausencia del espacio grafico de soluciones, no tenemos manera de determinar donde puede encontrarse la solución óptima, por lo que nuestra única opción es investigar ambos problemas. Hacemos esto trabajando con un problema a la vez (PL1 o PL2). Supongamos que escogemos a PL1 asociado con x1 ≤ 3. En efecto, debemos resolver el siguiente problema: Max z = 5x1 + 4x2

Sujeto a : x1 + x2 ≤5 10x1 + 6x2 ≤45 x1 ≤3 x1 , x2 ≥ 0Como se indico antes PL1 es el mismo que el PLO con la restricción adicional de acotamiento superior, x1 ≤3. Así podemos aplicar el algoritmo primal de acotamiento superior para resolver el problema. Esto da la nueva solución óptima.

x1 = 3, x2 = 2 y z = 23

Como esta solución satisface el requisito de valor entero, se dice que el PL1 esta agotado, vació, lo que significa que el PL1 no puede producir ninguna solución mejor y no necesita investigarse más a fondo.

|


Figura 2

3

PL2x1 = 4 x2 =0.83 z = 23.33

2

PL1x1 = 3 x2 =2 z = 23Cota inferior (óptima)

1

PL0x1 = 3.75 x2 =1.25 z = 23.75

X1≥ 4X1≤ 3

Determinar una solución factible entera en una etapa temprana de los cálculos es crucial para incrementar la eficiencia del algoritmo R y A. Tal solución fija una cota inferior al valor objetivo optimo, que a su vez se puede usar para descartar automáticamente cualquier subproblema no explorado (como el PL2) que no dan mejor solución entera. En este ejemplo el PL1 produce la cota inferior z = 23. Esto significa que cualquier solución entera mejorada debe tener el valor de z mayor 23. Sin embargo, como la solución óptima del problema PLO tiene z = 23,75 y como todos los coeficientes de la función objetivo son enteros, se infiere que ningún subproblema que proceda del PLO puede producir un valor de z mejor que 23. En consecuencia, podemos descartar al PL2 porque no puede dar una mejor solución entera.

Del análisis anterior vemos que un subproblema esta agotado si no satisface una de las siguientes condiciones:

1. El subproblema da una solución factible entera.2. El subproblema no puede dar una mejor solución que la mejor cota inferior disponible (valor z) del problema (Un caso especial de esta condición es que el subproblema no tendrá ninguna solución factible en absoluto)

Pero si en nuestro ejemplo decidimos investigar PL2 primero la solución resultante será: x1 = 4, x2 = 0,8333, z = 23,3333. Como x2 no es entero el PL2 debe investigarse mas a fondo creándose el PL3 y PL4 y usando las respectivas ramas x2 ≥0 y x2 ≤ 1. Esto significa que

Espacio PL3 = espacio PLO + (x1 ≥ 4) + (x2 ≥0) Espacio PL4 = espacio PLO + (x1 ≥ 4) + (x2 ≤1)

En este momento para escoger tres subproblemas, el PL1, PL3 y PL4. (Observe nuevamente que estos tres subproblemas incluyen todas las soluciones enteras factibles del problema original PLE.) Si seleccionamos arbitrariamente el PL4, descubrimos que no tiene solución factible y por ello esta agotado. A continuación seleccionamos el PL3 para investigarlo. Su solución la da x1 = 4,5,x2 = 0 y z = 22,5. Como x1 = 4,5 no es entero, creamos dos subproblemas, el PL5 y PL6 del PL4, usando las restricciones x1 ≤4 y x1 ≥ 5 respectivamente.

Obtenemos entonces:

Espacio PL5 = espacio PLO + (x1 ≥ 4) + (x2 ≤0) + (x1 ≤ 4)Espacio PL6 = espacio PLO + (x1 ≥ 4) + (x2 ≤0) + (x1 ≥ 5)

Escogemos ahora el PL6, para investigarlo. Como el PL6 no tiene solución factible, esta agotado. A continuación escogemos el PL5 cuya solución óptima (x1 = 4, x2 = 0, z = 20) satisface el requisito de valor entero. Finalmente, hemos encontrado una solución entera que fija una cota inferior (z = 20) a la solución entra óptima.

|


Desafortunadamente, esta cota inferior es “muy débil” y “muy tardía” para ser útil. El único nodo restante, PL1, queda agotado a continuación con z = 23, lo que fija una nueva cota inferior. Como no quedan ya subproblemas por investigar, la última cota inferior asocia la solución óptima del PLE con PL1.

La secuencia posible de solución, mostrada en al figura siguiente, se ha escogido intencionalmente para evidenciar una de las principales debilidades del algoritmo de R y A. Esto es, un subproblema especifico, ¿cómo seleccionamos a la variable de ramificación? Y, de entre todos los subproblemas no explorados, ¿Cuál debe investigarse a continuación? Observe que en la figura, encontramos una buena solución en el primer subproblema PL1, lo que nos permitió declarar agotado al PL2 sin ninguna investigación posterior. Básicamente, el problema PLE se resolvió investigando solo un subproblema. En el siguiente caso tuvimos que resolver seis subproblemas antes de alcanzar la optimidad. Este caso no es raro y puede encontrarse situaciones reales. Aunque existen muchos métodos para aumentar la habilidad del algoritmo de R y A de “ver adelante” y hacer una buena “conjetura”, respecto a sí una rama dada conducirá a una solución mejorada del PLE, no existe una teoría consistente que produzca resultados concretos uniformes para la solución del problema general de PLE.

|


PL2x1 = 4 x2 =0.83 z = 23.33

7

PL1x1 = 3 x2 =2 z = 23Cota inferior (óptima)

1

PL0x1 = 3.75 x2 =1.25 z = 23.75

x1 ≥ x1 ≤

2

Resumiremos ahora los pasos del algoritmo de R y A. Suponiendo un problema de maximización, definiremos z como la cota inferior de la solución entera óptima del problema. Hacemos inicialmente

z = - ¥ e i = 0

Paso 1: Agotamiento y ramificación. Seleccione PLi como el próximo subproblema por investigarse. Resolvemos el PLi y trataremos de agotarlo usando las condiciones apropiadas.

(a) Si el PLi se declara agotado (solución inferior, infactible o entera), ponga al día la cota inferior z si se encuentra una mejor solución del PLE; si no es así, seleccione un nuevo subproblema i y repita el paso 1. Si todos los subproblemas se han investigado, la solución óptima del PLE está asociada con la ultima cota inferior z en caso de que exista, si no es así

(b) Si el PLi no está agotado, siga con el paso 2 para efectuar la ramificación del PLi.

Paso 2: Ramificación. Seleccione una de las variables xj cuyo valor óptimo en la solución del PLi no satisfaga la restricción del valor entero. Elimine la región creando dos subproblemas PL que correspondan a las dos siguientes restricciones mutuamente excluyentes, vuelva al paso 1.

EJERCICIO 2.-

|


Max = 21x1 + 11 x2

s.a. 7x1 + 4 x2 ≤ 13

x1 ≥ 0 x2 ≥ 0 x1, x2 enteros

Gráficamente corresponde a:

El dominio de puntos factibles para el modelo de Programación Lineal asociado es el área demarcada con verde. Dicho modelo tiene valor óptimo igual a 39, con x1=1,9 y x2=0. Esto corresponde a la relajación continua del PLE y nos proporciona una cota superior del valor óptimo de dicho problema. Además, claramente la solución de la relación continua no satisface la condición de integralidad del modelo de PLE. Finalmente, en el gráfico anterior se han marcado con azul todas aquellas combinaciones que satisfacen las restricciones del modelo de PLE. Claramente esto corresponde a un subdominio del problema lineal asociado lo que justifica que la relajación continua nos entrega una cota superior del valor óptimo del PLE. Al aplicar el algoritmo de Branch & Bound, el nodo inicial corresponde a la relajación continua y se van agregando las ramas o nodos necesarios hasta alcanzar la(s) soluciones que satisfacen las condiciones de integralidad.

|


P0: Corresponde a la relajación continua del PLE.P1: Po + x1<=1. (Solución inicial x1=1,9 aproximada al entero inferior)P2: Po + x1>=2 (solución inicial x1=1,9 aproximada al entero superior). Infactible. P11: P1 + x2<=1 (solución óptima x1=1 y x2=1. Valor Óptimo z=33. Debido a que la solución

satisface las restricciones de integralidad, se termina este nodo).P12: P1 + x2>=2 (solución x1=5/7 y x2=2. No es solución óptima de PLE debido a que x1 es aún

fraccionario. Se continua el método debido a que el Valor Óptimo z=37 es mayor que el Valor Óptimo de P11, en caso contrario se detiene el método y P11 sería la solución óptima de PLE).

P121: P12 + x1<=0 (x1=0 y x2=13/4. z=35,75. Se continua siguiendo el mismo razonamiento anterior)

P122: P12 + x1>=1 Infactible.P1211: P121 + x2<=3 (x1=0 y x2=3. z=33 el Valor Óptimo más alto obtenido para los nodos

con soluciones enteras). Se agota este nodo.P1212: P121 + x2>=4 Infactible.

Luego la Solución Óptima del PLE) es x1=0 y x2=3 con Valor Óptimo z=33.

|


Como en el algoritmo de ramificación y acotamiento, el del plano cortante también se inicia en la solución optima del programa lineal continuo. Al espacio de soluciones se agregan restricciones especiales, llamadas cortes, en una forma que produzca un punto extremo entero. En el siguiente ejemplo se demostrará como se usan los cortes en forma grafica para producir una solución entera.Considere el problema de programación lineal entera:

EJERCICIO 3

Maximizar z = 7x1 + 10x2

Sujeto a: -x1 + 3x2 <=6 7x1 + x2 <=35x1, x2 ≥ 0 ,enteros no negativos

El algoritmo del plano de corte modifica el espacio de soluciones agregando cortes que producen un punto extremo entero óptimo. La figura muestra un ejemplo de dos cortes de esos. Se parte del optimo del programa lineal continuo, z= 66 ½ , x1 = 4 ½, x2=3 ½

A continuación se agrega el corte I, que produce la solución lineal óptima continua z= 62, x1

=447

, x2 = 3.

|


A continuación se agrega el corte II, que junto con el corte I y las restricciones originales, llega a la solución óptima del programa lineal z = 58, x1 =4, x2 = 3. La última solución es entera, que era lo que se buscaba.

Los cortes agregados no eliminan alguno de los puntos enteros factibles, originales, pero deben pasar por al menos un punto entero, factible o no factible. Estos son los requisitos básicos de cualquier corte.

|


• En un problema de Programación Entera con frecuencia hay un número finito de soluciones factibles posibles. Entonces, es posible (teóricamente) enumerar y evaluar cada una de las soluciones enteras factibles con el fin de encontrar el óptimo.

• Lo más frecuente es el uso del Método De Ramificación y Acote en el que solamente es necesario una enumeración parcial, si se aplica sistemáticamente, en el hallazgo de una solución óptima entera. El método de Ramificación y Acote es una técnica para el logro de esto, ya que va eliminado conjuntos de soluciones bajo consideración

EJEMPLO:

max Z = 5 X1 + 3 X2 + X3

s.a. : X1 + X2 + X3 ≤ 6

3 X1 + X2 + 4 X3 ≤ 9

X1 ≤ 1

X2 ≤ 1

X3 ≤ 4

X1 + X2 + X3 ≥ 0 y enteros

|


MINIMIZACIÓN

• Considere el siguiente problema de minimización de costos:

Minimizar Z=X1+ 3X2+5X3

Sujeto a: X1+X2+X3 ³ 6.5

3X1+X2+4X3 ³ 9.5

X1 £ 1

X2 £ 2

X3 £ 4

X1, X2, X3 ³ 0

|

X3 = 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4

X2 = 1X2 = 0X2 = 1X2 = 0

X1 = 1X1 = 0


1.- Resolver el problema como uno de programación lineal ignorando la restricción entera. Si la solución satisface la restricción entera, tenemos una solución optima para el problema de programación entera. La solución por programación lineal es:

x1 = 1,

x2 = 2,

x3 = 3.5

Z = 24.5

Como no es un solución entera necesitamos particionar el conjunto de soluciones.

|


|

Paso 4: Terminación

No

Paso 3:Comparación Y Eliminación

Paso 2: Acote

Paso 1:Ramificación

Iteración 0

La solución entera de costo mínimo es la solución entera factible asociada con la cota superior más actual.

¿Todas las ramas han sido

investigadas?

Compare la Cota inferior del Paso 2 con la actual cota superior del costo mínimo (el más bajo costo obtenido por una solución entera) para las ramas hasta aquí investigadas.

(a) Si la cota inferior excede a la actual superior, entonces elimine esta rama de las demás consideraciones.

(b) Si la cota inferior es menor que la cota superior actual y además es solución entera, entonces se convierte en la nueva o actual cota superior.

A

A

El costo de la solución obtenida en el paso Uno se convierte en la nueva cota inferior del costo Para todas las Soluciones de la rama que está siendo Investigada.

Determinar una solución entera Factible. Esta solución da una Cota superior inicial para el Costo mínimo

Seleccione una variable para Ramificar. Esta divide el conjunto de soluciones posibles en dos conjuntos. Seleccione una de las ramas (seleccionar Uno de los subconjuntos) para Nuevo análisis. resolver el problema Programación apropiado.


|

65 4


Maximización

Max: Z=X1+5X2+7X3+3X4

Sujeto a

7x1+3x2+2x3+4x4 <=15

8x1+2x2+3x3+5x4 <=17

1x1 <=4

1x2 <=4

1x3 <=1

1x4 <=1

x1, x2, x3, x4 Todos Enteros.

|


|

SoluciónEnteraOptima

X4=1X4=0

1<= x1 <=4X1 =0

Solucion PL

X1 = 0.14, x2 = 4, X3 = 1

x4 = 0

Utilidad Z = 27.14

Solución entera

Solucion PL

X1 = 0, X2 = 4, X3 = 1

X4 =0

Utilidad Z = 27.00

Solución entera

Solucion PL

X1 = 0, x2 = 3, X3 = 1

x4 = 1

Utilidad Z = 25.00

Solución entera

Solucion PL

X1 = 1, X2 = 2, X3 = 1

X4 = 0

Utilidad Z = 18

Solución entera

Solucion por PL

X1 = 0, x2 = 4, X3 = 1

x4 = 0.25

Utilidad Z = 27.75

Solución no entera: Rama


Igual que en el algoritmo de Ramificación y Acotamiento, el algoritmo de plano cortante también empieza en la solución óptima de la Programación Lineal.

Sin embargo, en vez de utilizar la Ramificación y Acotamiento, modifica el espacio de la solución añadiendo sucesivamente restricciones especialmente construidas (llamadas cortes).

EJEMPLO:

Maximizar Z = 7x1 + 10x2

Sujeto a: -x1 + 3x2 ≤ 6

7x1 + x2 ≤ 35

x1, x2 ≥ 0 y entero

DESARROLLO ALGEBRAICO

Paso 1

Resolver el problema primal, si la solución es entera, corresponde a la óptima para el problema de Programación Lineal Entera.

Paso 2

Seleccionar decimales y escoger aquel que tenga la mayor parte fraccionaria tomando las ecuaciones completas.

Paso 3

Se separan la parte entera, es decir, quedarse solamente con la parte

fraccionaria.

Nota:

Luego de encontrar una solución óptima para el primal, por Simplex y después de agregarle la primera nueva ecuación al sistema se pasa a Dual – Simplex, para quitarle la infactibilidad al sistema.

EJEMPLO

Maximizar Z = 8 X1+ 5 X2

|


X1 + X2 ≤ 6

9 X1 + 5X2 ≤ 45

X1, X2≥ 0

X1, X2 ZЄ

Resolución:

Estandarización:

MAXZ = 8 X1+ 5 X2 + 0S1 + 0S2

X1 + X2 +S1 = 6

9 X1 + 5X2 +S2= 45

TABLA 1: SIMPLEX

V.BASICAS Z X1 X2 S1 S2 SOLUCION

Z 1 -8 -5 0 0 0

S1 0 1 1 1 0 6

S2 0 9 5 0 1 45

Variable que entra a la base: X1, Variable que sale de la base: S2

TABLA2: SIMPLEX


Z 1 0 -5/9 0 8/9 40

S1 0 0 4/9 1 -1/9 1

X1 0 1 5/9 0 1/9 5

Variable que entra a la base: X2, Variable que sale de la base: S1

|


6 ÷1 = 6

45 ÷9 = 5

1 ÷4/9 = 2.25

5 ÷5/9 = 9n.e.p

Nueva Ecuación Z:

Ecuación Z Anterior : 1 -8 -5 0 0 0

-(-8)(n.e.p) : 0 8 40/9 0 8/9 40

1 2 -5/9 0 8/9 40

Nueva Ecuación S1:

Ecuación S1 Anterior : 0 1 1 1 0 6

-(1)(n.e.p) : 0 -1 -5/9 0 -1/9 -5

0 0 4/9 1 -1/9 1

TABLA 3: SIMPLEX


Z 1 0 0 5/4 3/4 165/4

X2 0 0 1 9/4 -1/4 9/4

X1 0 1 0 -5/4 1/4 15/4

Nueva Ecuación Z:

Ecuación Z Anterior : 1 0 -5/9 0 8/9 40

-(-5/9)(n.e.p) : 0 0 5/9 5/4 -5/36 5/4

1 0 0 5/4 3/4 165/4

Nueva Ecuación X1:

Ecuación X1 Anterior : 0 1 5/9 0 1/9 5

-(5/9)(n.e.p) : 0 0 -5/9 -5/4 5/36 -5/4

0 1 0 -5/4 1/4 15/4

Solución Óptima Única para el problema primal:

|


X1 = 15/4; X2 = 9/4; S1= 0; S2 =0; Z = 165/4, pero para el problema de Programación Lineal Entera no nos sirve la respuesta, ya que las variables de decisión tienen valores fraccionarios. Para resolver este problema, aplicamos un refinamiento de la Programación Lineal, el cual corresponde al algoritmo de Gomory:

X1- 5/4 S1+ 1/4 S2= 15/4(1 + 0) X1 + (– 2 + 3/4) S1 + (0 + 1/4) S2 = (3 + 3/4)3/4 S1+ 1/4 S2 = 3/4Nueva ecuación3/4 S1+ 1/4S2≥ 3/4Nueva restricción– 3/4 S1– 1/4 S2 + S3 = – 3/4Ecuación a introducir al sistema

A continuación se aplica el dual – simplex, con el objetivo de quitarle la infactibilidad al sistema.

TABLA4: DUAL SIMPLEX

V.BASICAS Z X1 X2 S1 S2 S3 SOLUCION

Z 1 0 0 5/4 3/4 0 165/4

X2 0 0 1 9/4 -1/4 0 9/4

X1 0 1 0 -5/4 1/4 0 15/4

S3 0 0 0 -3/4 -1/4 1 -3/4

RAZÓN:

÷ FUNCIÓN Z: 0 0 5/4 3/4 0

ECUACIÓN S3: 0 0 -3/4

-1/4 1

0 0 -5/3

-3 0

|


Coeficiente más pequeño

TABLA 5: DUAL SIMPLEX

V.BASICAS Z X1 X2 S1 S2 S3 SOLUCION

Z 1 0 0 0 1/3 5/3 40

X2 0 0 1 0 -1 3 0

X1 0 1 0 0 2/3 -5/3 5

S1 0 0 0 1 1/3 -4/3 1

Nueva Ecuación Z:

Ecuación Z Anterior : 1 0 0 5/4 3/4 0 165/4

-(5/4)(n.e.p) : 0 0 0 -5/4 -5/12 5/3 -5/4

1 0 0 0 1/3 5/3 40

Nueva Ecuación X2:

Ecuación X2 Anterior : 0 0 1 9/4 -1/4 0 9/4

-(9/4)(n.e.p) : 0 0 0 -9/4 -3/4 3 -9/4

0 0 1 0 -1 3 0

Nueva Ecuación X1:

Ecuación X1 Anterior : 0 1 0 -5/4 1/4 0 15/4

-(-5/4)(n.e.p) : 0 0 0 5/4 5/12 -5/3 5/4

0 1 0 0 2/3 -5/3 5

Solución Óptima al problema de Programación Lineal Entera:

X1= 5X2=0 S1= 1S2= 0S3= 0 Z = 40

|


Las situaciones en las que las decisiones aparecen como alternativas son las más frecuentes con las que nos enfrentamos.

La noción de tipo binario la utilizamos en nuestros razonamientos y en nuestras acciones: todo o nada, blanco o negro, abierto o cerrado, existe o no existe, 0 o 1, verdadero o falso, prendido o apagado, muerto o vivo, entre otros.

Los dos métodos más usuales para solucionar problemas de Programación Lineal Entera Binaria son

Enumeración Implícita Cero – Uno Método Aditivo de Egon Balas.

El primer algoritmo especial 0_1,llamado el algoritmo aditivo fue desarrollado en 1965,unos años después del desarrollo del de R y A.

El diseño del método heurística de sondeo en el algoritmo aditivo requiere la presentación del problema [0_1] en una forma conveniente que satisfaga las siguientes requerimientos:

1. La función objetivo es de tipo de minimización, con todos los coeficientes no negativos.

2. todas las restricciones deben ser del tipo (<=), con todas los lados derechos negativos , de ser necesario. Después, estas ecuaciones se convierten en inecuaciones, utilizando variables de holgura .

EJEMPLO

Convertir el problema 0_1 para satisfacer los requerimientos iniciales del algoritmo aditivo.

Maximice z = 3X1-5X2

Sujeto A: X1+ X2 = 5

4X1 + 6X2 >=4

X1,X2 >=0

|


Primero convertimos el problema a uno de minimización con todas las restricciones (<=)como sigue.

(a) Multiplique Z por -1 para obtener la minimización de W = -3X1+ 5X2

(b) Convierte las ecuaciones de restricciones del tipo (<=)para obtener

X1+ X2<=5 y –X1-X2<=-5.

(c) Multiplique la segunda restricción por -1 para obtener -4X1-6X2<=-4

• Utilizando las holguras S1,S2,S3para las tres restricciones, el el problema se escribe como.

Minimice W = - 3X1 + 5X2

X1+ X2 +S1 = 5

- X1 - X2 + S2 = - 5

- 4X1 - 6X2 + S3 = - 4

X1,X2 =(0 ,1)

S1 ,S2 ,S3 >=0

• Para asegurarse de que los coeficientes de la funcion objetivo son no negativo, sustituya Xj = 1 – Xj* para cualquier Xj con coeficiente negativo en la funcion objetivo. Por consiguiente , sustituimos X1= 1-X1*y ajustamos el lado derecho de las restriccionesconforme a ello . Ahora el algoritmo aditivo trata con X1* y X2.

PROBLEMA BINARIO(0_1) RESUELTO A TRAVÉS DEL DEL ALGORITMO ADITIVO

Maximice W =3Y1+ 2Y2-5Y3 -2Y4+3Y5

Sujeto a

Y1 + Y2 + Y3 + Y4 + Y5 <=4

7Y1 + 3Y3 - 4Y4 + 3Y5 <=8

11Y1 - 6Y2 + 3Y4 - 3Y5 >=3

Y1,Y3,Y2,Y4,Y5 = (0,1)

1.- Multiplique la función objetivo por -1

|


2.- Multiplique la tercera restriccion por -1

3.- añade las variables de holgura S1,S2,S3 para convertir las tres en ecuaciones

4.- Sustituya Y1=1-X1, Y2= 1- X2 , Y5= 1- X5, Y3= X3, Y4= X4 para obtener todos los coeficientes objetivos en positivos.

• Ahora tenemos:

Minimice

Z*= 3X1+ 2X2+ 5X3+ 2X4+ 3X5- 8

Ignoremos la constante -8 y remplazemos Z*+8 con Z, de manera que :

Minimice Z= 3X1+ 2X2+ 5X3+ 2X4+ 3X5

Sujeto a

-X1-X2+X3+2X4-X5+S1=1

-7X1+3X3-4X4-3X5+S2=-2

11X1-6X2-3X4-3X5+S3=-1

X1, X2, X3, X4, X5=(0,1)

Solución Básica

factible X1 X2 X3 X4 X5 S1 S2 S3 Solución

S1 -1 -1 1 2 -1 1 0 0 1

S2 -7 0 3 -4 -3 0 1 0 -2

S3 11 -6 0 -3 -3 0 0 1 -1

Coeficientes

Objetivos 3 2 5 2 3

|


A lo largo de esta investigación se llegó a la conclusión de que los manuales de operaciones

resultan indispensables para cualquier organización, gracias a ellos se logra la mayor

eficiencia de los recursos tanto, humanos como financieros, ya que facilitan la

estandarización de los procesos y preservación del conocimiento adquirido por la misma

organización.

Por otra parte puede concluir que sin una estructura organizacional adecuada el personal

difícilmente podrá contribuir al logro de los objetivos de la empresa. Una organización será

eficiente si su estructura está diseñada para cubrir sus necesidades.

Mientras más clara sea la definición de un puesto, las actividades a realizar y la comprensión

de las relaciones de autoridad y las relaciones informales con otros puestos se evitar conflicto

y la productividad de las personas aumentará.

|


http://jrvargas.files.wordpress.com/2008/11/problema-transbordo_jrva.pdfhttp://www.monografias.com/trabajos59/modelo-transbordo/modelo-transbordo.shtmlhttp://www.monografias.com/trabajos59/modelo-transbordo/modelo-transbordo2.shtmlhttp://148.204.211.134/polilibros/portal/Polilibros/P_Terminados/Investigacion_de_Operaciones_Careaga/Common/IO-modulo4-transbordo.htmINVESTIGACION DE OPERACIONES 7a. Edición - TAHA HANDYhttp://antiguo.itson.mx/dii/elagarda/apagina2001/PM/asignacion.html http://www.arquimedex.com/index.php?option=com_content&task=view&id=54&Itemid=1 http://es.scribd.com/doc/57925720/EJEMPLOS-METODO-HUNGARO http://webcache.googleusercontent.com/search?q=cache:HGEPDyePNDoJ:www.elprisma.com/apuntes/matematicas/analisisdesensibilidad/default4.asp+sensibilidad+de+los+coeficientes+de+la+funcion+objetiva&cd=1&hl=es&ct=clnk&gl=pe&source=www.google.com.pe

http://www.youtube.com/watch?v=v68wFcVl4Cs

http://www.youtube.com/watch?v=r1EaXmWXUDMhttp://www.investigacion-operaciones.com/modelo_de_transporte.htmhttp://www.investigacion-operaciones.com/material%20didactico/TRANSPORTE.pdf http://www.slideshare.net/josekh89/problema-del-transporte

o Libro:Investigación Operativa – TAHA http://www.investigacion-operaciones.com/Dualidad.htmhttp://www.andrew.cmu.edu/user/mgoic/files/documents/optimization/dualidad.pdfProgramación Lineal: Análisis de Dualidad y de Sensibilidad Investigación Operativa – TAHA

|


http://www.andrew.cmu.edu/user/mgoic/files/documents/optimization/dualidad.pdf

http://www.andrew.cmu.edu/user/mgoic/files/documents/optimization/dualidad.pdf

http://www.investigacion-operaciones.com/Dualidad.htm

http://www.slideshare.net/josekh89/problema-del-transporte

http://www.investigacion-operaciones.com/material%20didactico/TRANSPORTE.pdf

http://www.investigacion-operaciones.com/material%20didactico/TRANSPORTE.pdf

http://www.investigacion-operaciones.com/modelo_de_transporte.htm

http://www.youtube.com/watch?v=v68wFcVl4Cs

http://webcache.googleusercontent.com/search?q=cache:HGEPDyePNDoJ:www.elprisma.com/apuntes/matematicas/analisisdesensibilidad/default4.asp+sensibilidad+de+los+coeficientes+de+la+funcion+objetiva&cd=1&hl=es&ct=clnk&gl=pe&source=www.google.com.pe



http://es.scribd.com/doc/57925720/EJEMPLOS-METODO-HUNGARO

http://www.arquimedex.com/index.php?option=com_content&task=view&id=54&Itemid=1

http://www.arquimedex.com/index.php?option=com_content&task=view&id=54&Itemid=1

http://antiguo.itson.mx/dii/elagarda/apagina2001/PM/asignacion.html

http://148.204.211.134/polilibros/portal/Polilibros/P_Terminados/Investigacion_de_Operaciones_Careaga/Common/IO-modulo4-transbordo.htm

http://148.204.211.134/polilibros/portal/Polilibros/P_Terminados/Investigacion_de_Operaciones_Careaga/Common/IO-modulo4-transbordo.htm

http://www.monografias.com/trabajos59/modelo-transbordo/modelo-transbordo2.shtml

http://www.monografias.com/trabajos59/modelo-transbordo/modelo-transbordo2.shtml

http://www.monografias.com/trabajos59/modelo-transbordo/modelo-transbordo.shtml

http://www.monografias.com/trabajos59/modelo-transbordo/modelo-transbordo.shtml

http://jrvargas.files.wordpress.com/2008/11/problema-transbordo_jrva.pdf

|


trabajo io finish

Documents