FACULTAD DE INGENIERÍA DE SISTEMAS E INFORMÁTICA

UNIVERSIDAD NACIONAL MAYOR DE

SAN MARCOS Universidad del Perú, DECANA DE AMÉRICA

FACULTAD DE INGENIERÍA DE SISTEMAS E INFORMÁTICA

INVESTIGACIÓN DE OPERACIONES 1 Lic. Lucio Malásquez Ruiz

Cardenas Gonzales, Gabriela Stephanie LIBRO DE AYUDA RECOPILACIÓN DE INFORMACIÓN Edición 2 – Año 2016

ÍNDICE INTRODUCCIÓN A LA INVESTIGACIÓN DE OPERACIONES 1.1 Introducción………………………………………………………………………………3 1.2 ¿Qué es la Investigación de Operaciones? ……………………………………….………6 1.3 Clasificación de la Metodología de IO………………………………………….………..8 1.4 Metodología de la IO…………………………………………………………………….9 1.5 Modelo Matemático……………………………………………………………………..11 PROGRAMACIÓN LINEAL: MODELO 2.1 Programación Lineal…………………………………………………….…….…….…….15 2.2 Presentación del Modelo de PL……………………………………………….…….…….17 2.3 Suposición del Modelo de PL………………………………………………….…..……...18 2.4 Interpretación Económico del Modelo de PL………………………………….…….……18 2.5 Propiedades del Modelo de PL……………………………………………..……..………19 2.6 Formas de mostrar el Modelo de PL………………………..……………….……….……21 2.7 Transformaciones en el Modelo de PL……………………………………….……………23 2.8 Formulación de Problemas………………………………………………………….……..25 MÉTODOS DE SOLUCIÓN GRÁFICA 3.1 Introducción………………………………………….……..………………………………35 3.2 Conjuntos Convexos…………………………………….……….…………………………36 3.3 Método Gráfico…………………………………………………………………………….37 3.4 Tipos de problemas lineales…………………………………………….………………….40 3.5 Ejemplos………………………………………….…………………………….…………..40 3.6 Ejercicios…………………………………………………………..……………………….45 MÉTODO SIMPLEX 4.1 Introducción………………………………………………………..…………………..….46 4.2 Definiciones Previas………………………………………………….…………………….47 4.3 Método Simplex……………………………………………………..……………………..48 4.4 Casos en la resolución de un PL…………………………………..……………………….53 4.5 Ejemplos………………………………………………….………...………………………54 4.6 Ejercicios…………………………………………………………...………………………58 MÉTODO DE VARIABLES ARTIFICIALES 5.1 Idea Conceptual……………………………………………………………………………59 5.2 ¿Variable Artificial? ……………………………………………………….………………60 5.3 Método de la M……………………………………….…………………………….……..60 5.4 Ejercicios…………………………………………………………………………….…….63 5.5 Método de Dos Fases………………………………………………………………..…….64 5.6 Ejercicios…………………………………………………………………………….…….69 DUALIDAD DE UN PPL 6.1 Introducción……………………………………………..…………………………………70 6.2 Relación entre Primal y Dual………………………………………………………………71 6.3 Formulación del Dual…………………………………….………….……………………..72 6.4 Teorema de la Dualidad…………………………………………………………………….73 6.5 Ejemplo…………………………………………………………………………..…………77 6.6 Ejercicios……………………………………………………………..…………………….80

1

MÉTODO DUAL SIMPLEX 7.1 Introducción………………………………………………………..……………………81 7.2 Método Dual Simplex………………………………………………..…………………..82 7.3 Ejercicios………………………………………………………………………….……..85 PROGRAMACIÓN LINEAL CON LINDO 8.1 Introducción………………………………………………….……………………..……86 8.2 ¿Cómo usar LINDO? ………………………………………..…………………………..87 8.3 Interpretación de los resultados en LINDO………………..…………………………….88 8.4 Análisis de Sensibilidad en LINDO……………………………………..………………89 8.5 Costo Reducido……………………………………………………………….………….92 8.6 Precio Dual…………………………………………………………………….…………94 PROPIEDAD DE LA TABLA SIMPLEX 9.1 Introducción…………………………………………………………….………………..96 9.2 Propiedades de una Tabla Simplex……………………………………..………………..97 9.3 Ejemplos…………………………………………………..….…………...………….…..100 9.4 Ejercicios…………………………………………………………..……………………..103 OPTMIZACIÓN: Método Transporte 10.1 Definición………………………………………………………………………………..105 10.2 Propiedades……………………………………………………………………………....107 10.3 Sbi: Método Esquina N-O……………………………………………………...………..108 10.4 Solución Óptima: Método UV…………………………………………………………..108 10.5 Caso: Oferta ≠ Demanda……………………………………………………….………..117 10.6 Sbi: Métodos Costos Mínimos…………………………………………………………..121 10.7 Sbi: Método de Voguel…………………………………………………………………..122 10.8 Ejercicios…………………………………………………………………………….…..126

2

INTRODUCCIÓN A LA INVESTIGACIÓN DE OPERACIONES

1.1 Introducción El objetivo del curso es que el estudiante aprenda a reconocer los problemas tipo de la Investigación de Operaciones de modo que sepa a qué técnica recurrir en cada caso, para un adecuado estudio y solución del mismo. Como su nombre lo indica, la Investigación de Operaciones (IO), o Investigación Operativa, es la investigación de las operaciones a realizar para el logro óptimo de los objetivos de un sistema o la mejora del mismo. Esta disciplina brinda y utiliza la metodología científica en la búsqueda de soluciones óptimas, como apoyo en los procesos de decisión, en cuanto a lo que se refiere a la toma de decisiones óptimas y en sistemas que se originan en la vida real.

3

Antecedentes Históricos

4

Antecedentes Históricos El término IO se utiliza por primera vez en el año 1939 durante la Segunda Guerra Mundial, específicamente cuando surge la necesidad de investigar las operaciones tácticas y estratégicas de la defensa aérea, ante la incorporación de un nuevo radar, en oportunidad de los ataques alemanes a Gran Bretaña. El avance acelerado de la tecnología militar hace que los ejecutivos y administradores militares británicos deban recurrir a los científicos, en pos de apoyo y orientación en la planificación de su defensa. El éxito de un pequeño grupo de científicos que trabajaron en conjunto con el ejecutivo militar a cargo de las operaciones en la “línea”, derivó en una mayor demanda de sus servicios y la extensión del uso de la metodología a USA, Canadá y Francia entre otros. Sin embargo, el origen de la Investigación Operativa puede considerarse como anterior a la Revolución Industrial, aunque fue durante este período que comienzan a originarse los problemas tipo que la Investigación Operativa trata de resolver. A partir de la Revolución Industrial y a través de los años se origina una segmentación funcional y geográfica de la administración, lo que da origen a la función ejecutiva o de integración de la administración para servir a los intereses del sistema como un todo. La Investigación Operativa tarda en desarrollarse en el campo de la administración industrial. El uso de la metodología científica en la industria se incorpora al principiar los años 50, a partir de la 2da Revolución Industrial, propiciada por los avances de las Comunicaciones, y la Computación, que sientan las bases para la automatización, y por sobre todo por el florecimiento y bienestar económico de ese período. Los primeros desarrollos de esta disciplina (IO) se refirieron a problemas de ordenamiento de tareas, reparto de cargas de trabajo, planificación y asignación de recursos en el ámbito militar en sus inicios, diversificándose luego, y extendiéndose finalmente a organizaciones industriales, académicas y gubernamentales. Existen varias asociaciones en todo el mundo, que agrupan a personas (estudiantes, científicos y profesionales) interesados por el estudio y aplicación de la Investigación Operativa. La más grande de todas es INFORMS, de Estados Unidos de Norteamérica asociación que nace de la unión de la ORSA = Operation Research Society of America, con 8 000 miembros y la TIMS = Institute of Managment Science con 6 000 miembros. También existen Asociaciones Canadienses, europeas, Latinoamericanas y asiáticas federadas en la IFORS, International Federation of Operation Research Societies. La Asociación Latinoamericana de Investigación de Operaciones, ALIO, conglomera a la mayor parte de las Asociaciones de América Central y Sur. Se publican decenas de revistas diferentes en todo el mundo. Existen programas de Posgrado (maestría y doctorado) en la especialidad, en América y Europa.

5

1.2. ¿Qué es la Investigación de Operaciones? Es la ciencia aplicada que estudia a las organizaciones en forma sistémica a fin de hacer de estas más eficientes. Se enfoca en la resolución de problemas reales y en la toma de decisiones. Aplicando conceptos y métodos de varias áreas científicas en la concepción, planeamiento u operación de sistemas. En esta disciplina se destacan las siguientes características esenciales:  Una fuerte orientación a Teoría de Sistemas,  La participación de equipos interdisciplinarios,  La aplicación del método científico en apoyo a la toma de decisiones. En base a estas propiedades, una posible definición es: la Investigación Operativa es la aplicación del método científico por equipos interdisciplinarios a problemas que comprenden el control y gestión de sistemas organizados (hombre- máquina); con el objetivo de encontrar soluciones que sirvan mejor a los propósitos del sistema (u organización) como un todo, enmarcados en procesos de toma de decisiones. Una definición completa: “Es un enfoque científico para la toma de decisiones ejecutivas, que consiste en: a) el arte de modelar situaciones complejas; b) la ciencia de desarrollar técnicas de solución para resolver dichos modelos c) la capacidad de comunicar efectivamente los resultados.” Según texto (Lawrence y Pasternak, 1998) A la que en mi opinión solo le faltaría incluir el objetivo general de la IO: estudiar la asignación óptima de recursos escasos a determinada actividad.

Resumiendo los puntos más importantes a denotar:  Es un arte-ciencia.  Determina el óptimo curso de acción.  Resultados cuantitativos.  Ayuda en el proceso de toma de decisiones.  Resolver un problema  Uso de modelos matemáticos  Se debe construir un modelo y resolverlo para la posterior toma de decisiones  Se debe ser creativo para la concepción del modelo

6

Fig2. Efecto de la Aplicación de la IO

Sistema ineficiente

EJEMPLO

Sistema eficiente

Un proceso de decisión respecto a la política de inventarios en una organización. Existen 4 funciones administrativas que han dado lugar a departamentos cuyos objetivos son: Función

Objetivo Maximizar la cantidad de bienes (servicios) producidos Producción y minimizar el costo unitario de la producción. Maximizar la cantidad vendida y minimizar el costo Comercialización unitario de las ventas. Minimizar el capital requerido para mantener cierto Finanzas nivel del negocio. Mantener la moral y la alta productividad entre los Personal empleados. Con respecto al INVENTARIO y según estos OBJETIVOS: El departamento de producción necesita producir tanto como sea posible a un costo mínimo, lo que se logra fabricando un solo producto en forma continua, pues se logra mayor eficiencia y se minimiza el tiempo perdido por cambio de equipo, al cambiar de artículo. Con este procedimiento se logra un gran inventario con una línea de productos pequeña. El departamento de mercado también necesita un gran inventario, pero para vender tanto como sea posible, debe surtir de la más amplia variedad de productos. Motivos de desencuentro con el departamento de producción. Para minimizar el capital necesario para que el negocio marche, el departamento de Finanzas debe reducir la cantidad de dinero "comprometido", lo más directo es reducir los inventarios. Se propone que los inventarios deben aumentar o disminuir en proporción a la fluctuación de las ventas.

7

En contraposición, cuando las ventas son bajas, ni producción ni personal requieren disminuir la producción, ni reducir personal. Personal le interesa mantener la producción a un nivel tan constante como sea posible, ya que el despido implica repercusiones en la moral del personal, pérdida de personal calificado, nuevos costos de formación de nuevo personal cuando así se requiera. Esto se traduce en producir hasta el nivel del inventario cuando las ventas son bajas y agotarlo cuando éstas son altas. Los objetivos enumerados y definidos de esta manera son difíciles de llevar a la práctica por su inconsistencia desde el punto de vista de la organización y del sistema en su conjunto. Es tarea y responsabilidad del ejecutivo (gerente) determinar una política de inventario que convenga a los intereses de toda la compañía y no de una sola de las funciones subordinadas. La tarea de organización y gerenciamiento requiere que se considere al SISTEMA en su conjunto y ésta es la esencia del trabajo gerencial. El ejecutivo debe decidir y para ello recurrirá a algún método. Le convendrá recurrir a un Investigador de Operaciones, dado que supuestamente éste estará apto para utilizar la investigación científica en apoyo a las decisiones que el ejecutivo deba tomar. Este apoyo se hace especialmente necesario cuando se trata de la búsqueda de soluciones “óptimas” a problemas que se originan en las organizaciones y servicios en general.

1.3. Clasificación de problemas de IO Los problemas en Investigación de Operaciones se clasifican de acuerdo a: a) Atendiendo al objetivo del problema. Problema de Secuenciación.Trata de colocar los objetos en cierto orden Problema de Localización.Trata de asignación de recursos. Problemas de Ruta.Encontrar la ruta optima de entre varias alternativas. Problemas de Búsqueda.Buscar información para tomar una decisión. Se usa la Teoría de Decisión Estadística.

Modelos de Optimización

Cuyo objetivo es maximizar cierta cantidad (beneficio, eficiencia) o minimizar cierta medida (costo, tiempo), quizás teniendo en cuenta una serie de limitaciones o requisitos que restringen la decisión (disponibilidad de capital, personal, material, requisitos para cumplir fechas límite, etc.) Ejemplos: Problemas de secuenciación, Problemas de localización, Problemas de rutas y Problemas de búsqueda.

Modelos de Predicción

Cuyo objetivo es describir o predecir sucesos (nivel de ventas, fechas de terminación de proyectos, número de clientes, etc.) dadas ciertas condiciones. Ejemplos: Problemas de reemplazamiento, Problemas inventario, Problemas de colas y Problemas de competencia.

de

8

b) Por el grado de certidumbre de los datos. Modelos de Investigación Operativa Modelo Determinístico.Todos los datos del problema se consideran conocidos.

Determinísticos

Híbridos

Estocásticos

Optimización Lineal

Optimización No Lineal

Planificación de proyectos

Análisis de Decisión

Programación Lineal

Métodos Clásicos

Programación Dinámica

Procesos Estocásticos

Transporte y Asignación

Métodos de Búsqueda

Modelos de Inventario

Teoría de colas

Programación Entera y Binaria

Programación No Lineal

Simulación

Problema de redes

Programación Multicriterio Características importantes de la IO: -

Orientación del estudio hacia el sistema y no hacia un problema en particular. Utilización de equipos mixtos. Adopción del método científico.

Una vez clasificados los problemas de Investigación Operativa, pasamos a describir la resolución de los mismos.

1.4. Metodología de la IO SISTEMA REAL SISTEMA REAL SUPUESTO

MODELO

Fig3. Modelo de la Investigación Operativa

9 Fig4. Niveles de abstracción en el desarrollo de un modelo

Investigación de Operaciones: Aplicación del Método Científico para la Toma de decisiones.

Representaremos el sistema o el fenómeno del mundo real o el problema a resolver en un lenguaje matemático. Paso 1 Definición del problema Paso 2 Modelado Matemático Paso 3 Solución del modelo Paso 4 Presentación/Implementación resultados

Fig5. Metodología de la Investigación Operativa

Paso 1. Definición del problema, se debe tener en cuenta un buen plan de trabajo: - Observar. - Ser consciente de las realidades políticas. - Decidir qué se quiere realmente. - Identificar las restricciones. - Buscar información de modo continuo. Paso 2. Modelado matemático, es procedimiento que reconoce y verbaliza un problema para posteriormente cuantificarlo transformando las expresiones verbales en expresiones matemáticas. Etapas: 1. Identificar las variables de decisión: puede ser útil hacerse las siguientes preguntas: ¿qué es lo que hay que decidir? O ¿sobre qué elementos tenemos control? O ¿cuál sería una respuesta válida para este caso? 2. Identificar la función objetivo: ¿Qué es lo que queremos conseguir? o Si yo fuera el jefe de esta empresa, ¿qué me interesaría más? 3. Identificar las restricciones. 4. Traducir todos los elementos básicos a un modelo matemático. Paso 3. Resolución del modelo. Etapas: 1. Elegir la técnica de resolución adecuada. 2. Generar las soluciones del modelo. 3. Comprobar/validar los resultados. 4. Si los resultados son inaceptables, revisar el modelo matemático. 5. Realizar análisis de sensibilidad. Paso 4. Presentación/Implementación de los resultados Etapas: 1. Preparar informes y/o presentaciones. 2. Vigilar el proceso de implementación.

Ahora veamos las fases de un estudio de la Investigación de Operaciones.

10

Modelo: Representación simplificada e idealizada de la realidad

Modelos Matemáticos o Físicos Estáticos o Dinámicos Determinísticos o Estocásticos

Fig6. Método de Investigación Operativa

Los pasos a seguir en la aplicación del método científico (coincidentes con los de la Teoría General de Sistemas) son, en su expresión más simple: 1.- Planteo y Análisis del problema 2.- Construcción de un modelo 3.- Deducción de la(s) solución(es) 4.- Prueba del modelo y evaluación de la(s) solución(es) 5.- Ejecución y Control de la(s) solución(es) Observar que el problema es UNO SOLO, sin embargo existen maneras distintas de observar un mismo problema, dependiendo de los objetivos que se planteen para resolverlo.

1.5. Modelo Matemático Partamos conociendo un poco de la Programación Matemática: La programación matemática es un área de la matemática que se preocupa, con la generación de modelos matemáticos, de representar situaciones reales en las cuales se tiene como principal objetivo la optimización de un recurso escaso. Entonces, un modelo matemático es una representación idealizada y simplificada de un sistema, expresada en términos de símbolos y expresiones matemáticas. Ejemplo: F=m.a Y queda definido por: Fig7. Programación Matemática

Variables de Decisión

Función Objetivo (F.O.)

𝑍 = 𝑓 (𝒙𝟏 , 𝒙𝟐 , … , 𝒙𝒏 )

Medida de desempeño conjunto

𝑍 = 3𝑥1 + 5𝑥2 Restricciones ecuaciones y desigualdades

𝑥1 + 2𝑥2 ≥ 8

11

Imagine que tiene un compromiso de negocios que requiere 5 semanas de traslado continuo entre Lima y Arequipa. Sale de Lima los lunes y regresa los miércoles. Un boleto regular de viaje redondo cuesta $400, pero se ofrece 20% de descuento si el viaje redondo comprende un fin de semana. Un boleto sencillo en cualquier dirección cuesta 75% del precio regular. ¿Cómo debe comprar los boletos para reducir el costo del traslado durante las 5 semanas?

EJEMPLO

Podemos considerar la situación como un problema de toma de decisiones, cuya solución requiere responder tres preguntas: ¿Cuáles son las alternativas de decisión?

¿Conforme a qué restricciones se toma la decisión?

¿Cuál es el criterio objetivo apropiado para evaluar las alternativas?

Analicemos y respondamos las preguntas:

Semana 1

2

Boleto L

A

L

L

A

L

L

A

L

L

A

L

L M M J V S D

L

A

L

L M M J V S D

L

A

L M M J V S D

A

L

A

A

L

A

A

L

A

A

L

L M M J V S D

3

L M M J V S D

L M M J V S D

    

L

A

L

A

L

A

A

L

A

A

L

A

A

L

A

Se consideran tres alternativas razonables: 1

Comprar cinco boletos normales L-A-L para salir el lunes y regresar el miércoles de la misma semana.

2

Comprar un boleto L-A, cuatro A-L-A que abarquen fines de semana, y uno A-L.

3

Fig8. Representación de las alternativas

L

Duración de Viaje : 5 semanas Salir los lunes y regresar Miércoles Costo de boleto normal (ida y vuelta) : $400.00 Costo de boleto normal con fin de semana: 80% del costo normal. Costo de boleto sencillo (ida): 75% del costo normal.

A

Comprar un boleto L-A-L para el lunes de la primera semana y el miércoles de la última semana, y cuatro A-L-A para los viajes restantes. Todos los boletos en esta alternativa cubren por lo menos un fin de semana.

La restricción en estas opciones es que pueda salir de Lima el lunes y regresar el miércoles de la misma semana. Un criterio objetivo obvio para evaluar la alternativa propuesta es el precio de los boletos. La alternativa que dé el costo mínimo será la mejor.

12

Específicamente, tenemos: 

Costo de la alternativa 1 : 5 boletos *400 ($ boleto ida y vuelta) = $2000



Costo de la alternativa 2 :

1 boleto* 0.75 (% boleto sencillo)* 400 ($ boleto ida y vuelta) + 4 boletos * (0.8 (% boleto + fin de semana) * 400 ($ boleto ida y vuelta)) 1 boleto* 0.75 (% de boleto sencillo)* 400 ($ boleto ida y vuelta) $ 1880



Costo de la alternativa 3: 5 boletos* (0.8 (%boleto fin de semana)*400 ($ boleto ida y vuelta)) = $1600

La alternativa 3 es la mejor porque es la más económica.  Aunque el ejemplo anterior ilustra los tres componentes principales de un modelo de IO, los cuales son: alternativas, criterio objetivo y restricciones, las situaciones difieren por los detalles de la construcción de cada componente y la solución del modelo resultante. Para ilustrar este punto veamos otro ejemplo:

EJEMPLO

Considere la formación de un rectángulo de área máxima con un trozo de alambre de “L” pulgadas de longitud. ¿Cuál será el mejor ancho y altura del rectángulo? En contraste con el ejemplo de los boletos, el número de alternativas en este ejemplo no es finito; es decir, el ancho y la altura del rectángulo pueden asumir una cantidad infinita de valores porque son variables continuas. Para formalizar esta observación, las alternativas del problema se identifican definiendo el ancho y la altura como variables algebraicas w = ancho del rectángulo en pulgadas, h = altura del rectángulo en pulgadas. Con base en estas definiciones, las restricciones de la situación pueden expresarse verbalmente como 1. Ancho del rectángulo + altura del rectángulo = longitud del alambre. 2. El ancho y la altura no pueden ser negativos.

la mitad de la

Estas restricciones se traducen de manera algebraica como sigue 1. 2(w + h) = L 2. w≥0 , h≥0

13

Ahora el único componente restante es el objetivo del problema; es decir, maximizar el área del rectángulo.

Si Z se define como el área del rectángulo, el modelo completo es: Maximizar Z = w * h sujeto a 2(w + h) = L w , h ≥0 Utilizando cálculo diferencial, la mejor solución de este modelo es 𝐿 𝑤 = ℎ = 4 , la cual requiere la construcción de una forma cuadrada. Con los datos de los dos ejemplos anteriores, el modelo general de IO se organiza en el siguiente formato general:

Maximizar o minimizar Función Objetivo Sujeto a Restricciones

Una solución del modelo es factible si satisface todas las restricciones; es óptima si, además de ser factible, produce el mejor valor (máximo o mínimo) de la función objetivo. En el ejemplo de los boletos, el problema considera tres alternativas factibles, y la tercera es la que produce la solución óptima. Aunque los modelos de IO están diseñados para “optimizar” un criterio objetivo específico sujeto a un conjunto de restricciones, la calidad de la solución resultante depende de la exactitud con que el modelo representa el sistema real. Considere, por ejemplo, el modelo de los boletos. Si no se identifican todas las alternativas dominantes para comprar los boletos, entonces la solución resultante es óptima sólo en relación con las opciones representadas en el modelo. Específicamente, si se omite la alternativa 3 en el modelo, entonces la solución “optima” requeriría que se compraran los boletos en $1880, la cual es una solución subóptima. La conclusión es que “la” solución óptima de un modelo es mejor sólo para ese modelo. Si el modelo es una representación razonablemente buena del sistema real, entonces su solución también es óptima para la situación real.

14

PROGRAMACIÓN LINEAL: MODELO

2.1 Programación Lineal La programación lineal (PL) es un medio matemático que permite asignar una cantidad fija de recursos, a la satisfacción de varias demandas de tal forma que mientras se optimiza algún objetivo se satisface otras condiciones definidas. Utilizando modelos matemáticos como un recurso primario, la metodología de la IO está diseñada para cuantificar y acotar estos problemas dentro de un marco de restricciones específico, medido, objetivo y variable, de tal forma que se busquen controles óptimos de operación, decisiones, niveles y soluciones. Los problemas de asignación surgen en el momento en que un cierto número de mercancías o de tareas deben ser distribuidos de la mejor manera posible, teniendo en cuenta las limitaciones que existen.

15

16

2.2 Presentación del modelo de PL La PL es un conjunto de modelos de programación matemática destinados a la asignación eficiente de los recursos limitados en actividades conocidas, con el objeto de satisfacer metas (objetivos) deseadas (maximizar utilidades o minimizar costos).

Función Objetivo: La función representativa de la medida de eficiencia (FUNCION OBJETIVO Z) debe ser igual a la suma algebraica del producto de cada nivel de actividad (VARIABLE DE CONTROL Xi) por la contribución positiva o negativa de dicha actividad (Ci) a la medida de eficiencia del sistema.

Un modelo de PL consta de: 2.1.1. Función Objetivo (F.O.) .- Define la medida de efectividad del sistema de manera ideal, el valor de la F.O. es influenciado por las variables controlables y no controlables. 𝑂𝑝𝑡𝑖𝑚𝑖𝑧𝑎𝑟 𝒁 = 𝒇(𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = 𝑐1 𝑥1 + 𝑐1 𝑥1 + ⋯ + 𝑐1 𝑥1 Donde Z es de Maximizar/Minimizar. 2.1.2. Una serie de Restricciones.- El sistema tiene limitaciones; tecnológicos, económicos y otros, éstos los representamos mediante relaciones de igualdad y desigualdad.

≤ 𝑔𝑖 (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = 𝑏𝑖 ≥ Donde:

𝑖 = 1,2, … , 𝑚 𝒏

𝒈𝒊 (𝒙𝟏 , 𝒙𝟐 , … , 𝒙𝒏 ) = 𝒂𝒊𝟏 𝒙𝟏 + 𝒂𝒊𝟐 𝒙𝟏 + ⋯ + 𝒂𝒊𝒎 𝒙𝒏 = ∑ 𝒂𝒊𝒋 𝒙𝒋

𝑗 = 1,2, … , 𝑚

𝒊=𝟏

2.1.3. Variables.- Factores mensurables que dan sustentación al problema. Ejemplo: Los rangos de existencia de las variables pueden ser: 𝒙𝒋 ≥ 𝟎 , 𝒙𝒋 ≤ 𝟎 , 𝑥𝑗 𝑒𝑠 𝑐𝑢𝑎𝑙𝑞𝑢𝑖𝑒𝑟 𝑣𝑎𝑙𝑜𝑟 2.1.4. Parámetros.- Condiciones mensurables, inherentes a la estructura del modelo, valores conocidos y que relacionan las variables de decisión con las restricciones y la F.O. Resumiendo: Parámetros Variables Recordemos:

𝑂𝑝𝑡𝑖𝑚𝑖𝑧𝑎𝑟 𝒁 = ∑ 𝑪𝒋 𝒙𝒋 𝑠. 𝑎. ∶

𝑀𝑎𝑥 𝑍 = 𝟑𝑥1 + 𝟓𝑥2 F.O.

ecuaciones y desigualdades

𝑥1 + 𝟐𝑥2 ≥ 𝟖 𝑥1 , 𝑥2 ≥ 𝟎

≥ ∑ 𝒂𝒊𝒋 𝒙𝒋 = 𝒃𝒊 ≤ 𝒙𝒋 ≥ 𝟎

𝑖 = 1,2, … , 𝑚 𝑗 = 1,2, … , 𝑛

Restricciones

17

Un problema de P.L. consiste en hallar valores para las variables de decisión x1, x2, x3,…, xn tales que maximicen o minimicen el valor de la medida de eficiencia (función objetivo) y que satisfagan un conjunto de funciones llamadas restricciones.

2.3 Suposición del modelo de PL Para desarrollar problemas y ser resueltos por la PL se deben dar las siguientes suposiciones:  La F.O. debe expresar el objetivo del problema.  Se deben conocer las cantidades: Cj, aij y bi.  La F.O. y las restricciones son lineales.  Las restricciones deben expresar limitaciones del sistema en estudio.

F.O.= objetivo del problema

Cj

Ejemplo:

𝑀𝑎𝑥 𝑍 = 𝟑𝑥1 + 𝟓𝑥2 Lineales sujeto a

𝑥1 + 𝟐𝑥2 ≥ 𝟖 𝑥1 , 𝑥2 ≥ 𝟎

aij bi

Restricciones = limitaciones del sistema

2.4 Interpretación económica del modelo de PL Cj

Utilidad / Costo unitario debido a la actividad j.

aij

Cantidad del recurso i consumida por cada unidad de la actividad j.

bi

Cantidad disponible del recurso i.

Z

Utilidad / Costo total debido a todas las actividades.

Xj

Nivel de actividad j (variables).

18

2.5 Propiedades del Modelo de PL La linealidad implica que la programación lineal deba satisfacer dos propiedades: la proporcionalidad y la aditividad.  La proporcionalidad significa que los indicadores de Costo/Utilidad en la F.O. y la cantidad de cada recurso usado tienen que ser proporcionales, al valor de cada variable de decisión del modelo. Las cantidades Cj, aij deben ser proporcionales al valor de cada variable. Por ejemplo: 𝐸𝑙 𝑡é𝑟𝑚𝑖𝑛𝑜 𝟒𝑥1 𝑒𝑛 ∶ Divisibilidad. Significa que las variables de decisión son continuas y por lo tanto son aceptados valores no enteros para ellas. La hipótesis de divisibilidad más la restricción de no negatividad, significa que las variables de decisión pueden tener cualquier valor que sea positivo o por lo menos igual a cero.

Z = 𝟒𝑥1 𝟒(𝟏) = 𝟒 𝟒(𝟐) = 𝟖 𝟒(𝟑) = 𝟏𝟐

Lineal

𝐸𝑙 𝑡é𝑟𝑚𝑖𝑛𝑜 𝟒𝑥1 2 𝑒𝑛 ∶ Z = 𝟒𝑥1 2 𝟒( 𝟏 ) 𝟐 = 𝟒 𝟒(𝟐)𝟐 = 𝟏𝟔 𝟒(𝟑)𝟐 = 𝟑𝟔

Aumento constante y proporcional de 4

No Lineal

Aumento no constante y no presenta proporcionalid ad

 La aditividad significa que cada variable de decisión debe ser aditiva respecto al costo/utilidad y a la cantidad de recursos usados. Es decir, se puede valorar la función objetivo Z, así como también los recursos utilizados, sumando las contribuciones de cada uno de los términos que intervienen en la función Z y en las restricciones. Por ejemplo: 𝑍 = 𝟒𝑥1 + 𝟐𝑥2  Divisibilidad: El modelo da valores reales de las variables de decisión.  Optimalidad: La solución del modelo PL de maximizar utilidad o minimizar costos ocurre en uno de los vértices del conjunto convexo (Fig. 9).

Fig9. Ejemplos de conjunto Convexo.

EJEMPLO

PLANEACIÓN DE LA PRODUCCIÓN

Una fábrica produce los productos 1, 2 y 3. Se tiene las restricciones para su elaboración: Tiempo Disponible por Máquina Tipo de Máquina Torno Fresa Lisa

Horas Máquina por cada unidad de Producto

Horas/Semana

Producto 1

Producto 2

Producto 3

4,200 4,100 650

8 4 2

3 2 -

3 1

19

El Dpto. de ventas predice que el producto 3 se venderá a lo máximo 20 unidades. Las ganancias por unidad son $30, $10, $15 respectivamente de cada uno de los productos. ¿Qué cantidad de cada producto se debe fabricar?

SOLUCIÓN Analicemos los datos y lo plasmamos en una tabla general. Tiempo Disponible por Máquina Tipo de Máquina Torno Fresa Lisa

Horas/Semana 4,200 4,100 650 Ganancia Disponibilidad

Horas Máquina por cada unidad de Producto Producto 1

Producto 2

Producto 3

8 4 2 $ 30

3 2 $ 10

3 1 $ 15 20 unidades

Variable de decisión.Xj : Número de unidades a fabricar del producto j = 1,2,3. Función Objetivo.Trabajamos con beneficios, entonces debemos maximizar las ganancias. Max Z = 30X1 + 10X2 + 15X3 Restricciones.1. El uso de las máquinas no debe exceder su disponibilidad: 8X1 + 3X2 + 3X3 ≤ 4,200 4X1 + 2X2 ≤ 4,100 2X1 + X3 ≤ 650 2. La producción del producto 3 no debe exceder de 20 X3 ≤ 20 3. Restricciones de no negatividad: X1, X2, X3 ≥ 0. Resumen: El PPL es

Max Z = 30X1 + 10X2 + 15X3 sujeto a: 8X1 + 3X2 + 3X3 ≤ 4,200 4X1 + 2X2 ≤ 4,100 2X1 + X3 ≤ 650 X3 ≤ 20 X1, X2, X3 ≥ 0

20

2.6 Formas de mostrar el Modelo de PL 2.6.1. Forma Canónica. La forma canónica para un problema de maximizar / minimizar se caracteriza por tener sus restricciones expresados por “menor o igual” / “mayor o igual”, rangos no negativos y ningún término independiente. 𝑴𝒂𝒙 𝑍 = ∑ 𝐶𝑗 𝑋𝑗

𝑴𝒊𝒏 𝑍 = ∑ 𝐶𝑗 𝑋𝑗

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

∑ 𝑎𝑖𝑗 𝑥𝑗 ≤ 𝑏𝑖 𝑖 = 1,2, … , 𝑚 𝑥𝑗 ≥ 0

∑ 𝑎𝑖𝑗 𝑥𝑗 ≥ 𝑏𝑖 𝑖 = 1,2, … , 𝑚

𝑗 = 1,2, … , 𝑛

𝑥𝑗 ≥ 0

𝑗 = 1,2, … , 𝑛

2.6.2. Forma Mixta. Un problema maximizar / minimizar se caracteriza por tener todas sus restricciones expresados en ≤, = (≥, =), rangos no negativos y ningún término independiente en la función. 𝑴𝒂𝒙 𝑍 = ∑ 𝐶𝑗 𝑋𝑗 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 ∑ 𝑎𝑖𝑗 𝑥𝑗 ≤ 𝑏𝑖 𝑖 = 1,2, … , 𝑝 ∑ 𝑎𝑖𝑗 𝑥𝑗 = 𝑏𝑖 𝑖 = (𝑝 + 1),2, … , 𝑚 𝑥𝑗 ≥ 0

𝑗 = 1,2, … , 𝑛

2.6.3. Forma Genérica. Cuando un problema de PL no está expresado siguiendo una cierta norma (Canónica, Mixta, Estándar). Normalmente contienen restricciones y rangos de varios tipos, así como término independiente en la F.O. 𝑴𝒂𝒙 𝑍 = ∑ 𝐶𝑗 𝑋𝑗 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 ∑ 𝑎𝑖𝑗 𝑥𝑗 ≤ 𝑏𝑖 𝑖 = 1,2, … , 𝑝 ∑ 𝑎𝑖𝑗 𝑥𝑗 = 𝑏𝑖 𝑖 = (𝑝 + 1), 2, … , 𝑞 ∑ 𝑎𝑖𝑗 𝑥𝑗 ≥ 𝑏𝑖 𝑖 = (𝑞 + 1),2, … , 𝑚 𝑥𝑗 ≥ 0

𝑥𝑗 𝑙𝑖𝑏𝑟𝑒,

𝑗 = 1,2, … , 𝑛

21

2.6.4. Forma Estándar (Normal) A partir de esta formulación, se aplican todos los métodos de resolución. Características:  La F.O. no debe tener término independiente.  Todas las restricciones deben ser de igualdad.  Todas las variables deben ser no negativas. 𝑴𝒂𝒙 𝑍 = ∑ 𝐶𝑗 𝑋𝑗 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 ∑ 𝑎𝑖𝑗 𝑥𝑗 + 𝑆𝑖 = 𝑏𝑖 𝑖 = 1,2, … , 𝑚 𝑥𝑗 ≥ 0

𝑗 = 1,2, … , 𝑛

VARIABLE DE HOGURA Una variable de holgura se interpreta como la cantidad de productos imaginarios que se deben producir o dejar de producir. Cada producto de este tipo imaginario requiere una unidad de un recurso y su costo o beneficio es cero. 𝑈𝑛𝑎 𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖ó𝑛 𝑑𝑒𝑙 𝑡𝑖𝑝𝑜:

1

∑ 𝑎𝑖𝑗 𝑥𝑗 ≤ 𝑏𝑖 𝑠𝑒 𝑝𝑢𝑒𝑑𝑒 𝑒𝑥𝑝𝑟𝑒𝑠𝑎𝑟:

2

∑ 𝑎𝑖𝑗 𝑥𝑗 + 𝑆𝑖 = 𝑏𝑖

𝑈𝑛𝑎 𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖ó𝑛 𝑑𝑒𝑙 𝑡𝑖𝑝𝑜:

3

∑ 𝑎𝑖𝑗 𝑥𝑗 ≥ 𝑏𝑖

𝑠𝑒 𝑝𝑢𝑒𝑑𝑒 𝑒𝑥𝑝𝑟𝑒𝑠𝑎𝑟: ∑ 𝑎𝑖𝑗 𝑥𝑗 − 𝑆𝑖 = 𝑏𝑖

En la restricción 1, la desigualdad es de menor o igual, si cumple la igualdad, entonces la variable de holgura 𝑆𝑖 tomará el valor de 0 en 2. Si en 1 se cumple estrictamente la desigualdad, la variable de holgura 𝑆𝑖 en 2 tomará un valor estrictamente positivo. En este caso, la variable de holgura representa la cantidad de productos que deben producir (+). Veamos que en la restricción 3, la desigualdad es de mayor o igual, es decir, la variable de holgura representa la cantidad de productos imaginarios que deben dejar de producir (-). Ejemplo: Se sabe que 3X1 + X2 es un valor menor o igual a 4, entonces debemos aumentarle un valor S1 que represente el valor agregado para lograr la igualdad a 4. En el caso del ≥ se deberá disminuir un S2 para lograr la igualdad a 5.

𝑴𝒊𝒏 𝑍 = 2𝑋1 + 5𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 3𝑋1 + 𝑋2 ≤ 4 2𝑋1 + 3𝑋2 ≥ 5 𝑋1 , 𝑋2 , ≥ 0

𝑴𝒊𝒏 𝑍 = 2𝑋1 + 5𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 3𝑋1 + 𝑋2 + 𝑆1 = 4 2𝑋1 + 3𝑋2 − 𝑆2 = 5 𝑋1 , 𝑋2 , 𝑆1 , 𝑆2 ≥ 0

22

2.7 Transformaciones en el modelo de PL Algunas formas de expresar un modelo de PL son más convenientes que otras para ciertos propósitos. Por esta razón es útil conocer los procedimientos de transformación a saber.

1

Cuando el problema es de minimizar, y se desea expresarlo como máximo. Dado

Min Z = Σ CjXj Min Z = - Min (-Z) = Max (-Z) Entonces Max G = Σ (-Cj)Xj Donde Z=-G

3

Cuando hay variables de rango no-positivo. Dado

Xj ≤ 0 Basta con efectuar le cambio Xj’= - Xj ≥0 Se resuelve el problema con Xj’

5

Puede haber restricciones: |ai1X1 + ai2X2 +… + ainXn| ≤ b

Que es equivalente a ambas restricciones: ai1X1 + ai2X2 +… + ainXn ≤ b ai1X1 + ai2X2 +… + ainXn ≥ -b

EJEMPLO

2

Cuando la F.O. tiene término independiente. Dado

Max Z = C0 + Σ CjXj Definiendo G = Z- C0 = Σ (Cj)Xj Se resuelve: Max G = Σ (Cj)Xj Luego de calcular: Z óptimo = Z = G + CO

4

Cuando existen variables de rango libre (irrestricto). Sea Xj variable libre: Xj = Xj’- Xj’’ Con Xj’, Xj’’ ≥0 El programa se resuelve con Xj’y Xj’’

6 Cuando hay restricciones de desigualdad, se introduce variables de holgura, tal como se indicó.

Dado el PPL: Min Z = 10 – 35X1 – 20X2 + X3 sujeto a: 4x1 + X2 – 2X3 ≤ 8 X1 + X3 = 10 6X1 + X2 ≥ 5 X1 ≤ 0, X2 ≥ 0, X3 irrestricto

23

Hacer las siguientes transformaciones: 1. La F.O. no debe tener el término independiente. 2. La F.O. debe ser maximizar. 3. Escribir el modelo, con las restricciones de no negatividad.

SOLUCIÓN 1. La F.O. no debe tener el término independiente Función Objetivo Original: Min Z = 10 – 35X1 – 20X2 + X3

Operando: Z – 10 = – 35X1 – 20X2 + X3 Min G = – 35X1 – 20X2 + X3 Donde G = Z – 10 entonces Z = G + 10 La FO transformada: Min G = – 35X1 – 20X2 + X3

2. La F.O. debe ser maximizar (partiremos del a FO obtenida en 1). Tenemos la FO: Min G = – 35X1 – 20X2 + X3

Escribiendo: Min G = – Min (-G) = Max (-G) Max (-G) = – (– 35X1 – 20X2 + X3) Max H = 35X1 + 20X2 – X3 Donde G = – H Luego H = – G = – (Z – 10) – (Z – 10) = – Z + 10 Entonces Z = – H + 10 La FO transformada: Max H = 35X1 + 20X2 - X3

3. Escribir el modelo, con las restricciones de no negatividad (partiremos del a FO obtenida en 2). Hacer: X3 = X3’ – X3’’ y X1 = – X1’ Tenemos el PPL: Max H = 35X1 + 20X2 - X3 sujeto a: 4x1 + X2 – 2X3 ≤ 8 X1 + X3 = 10 6X1 + X2 ≥ 5

Entonces: Max H = – 35X1’ + 20X2 – (X3’ – X3’’) Sujeto a: – 4 X1’ + X2 – 2 (X3’ – X3’’) ≤ 8 – X1’ + (X3’ – X3’’) = 10 – 6X1’ + X2 ≥ 5

Transformando: Max H = – 35X1’ + 20X2 – X3’ + X3’’ Sujeto a: – 4 X1’ + X2 – 2 X3’ + 2 X3’’ + S1 =8 – X1’ + X3’ – X3’’ = 10 – 6X1’ + X2 – S3 = 5 X1’, X2, X3’, X3’’, S1, S3 ≥ 0

24

2.8 Formulación de Problemas 1

PLANEAMIENTO DE LA PRODUCCIÓN Un artesano se dedica a fabricar mesas y sillas. Se tiene la siguiente información: REQUERIMIENTOS/ACTIVIDADES

PLANCHA DE MADERA

HORAS DE TRABAJO

MESAS

2

1

SILLAS

1

2

DISPONIBILIDAD DE RECURSOS

40

40

El Artesano quiere hacer un máximo de 15 mesas y entre 10 y 12 sillas. El precio de una plancha de madera es de $1 y el costo de una hora de trabajo es de $10. ¿Cuántas mesas y sillas deben fabricarse?

a. Los costos b. Las utilidades c. Tiempo de Trabajo ¿Cuál es el objetivo del problema? Es importante definir el objetivo del problema a la hora de plantear el problema.

¿Cuál es el objetivo? ¿Bajar el costo? ¿Aumentar las utilidades? ¿Disminuir el tiempo de trabajo?

El problema no indica en base a qué debemos elaborar nuestro planteamiento, por ello desarrollaremos para los tres casos, pero seremos más específicos atendiendo a los costos. Entonces, si nos basamos en los costos, el artesano tendrá como objetivo bajar el costo total de producir sillas y mesas. Y la pregunta sería: ¿Cuántas mesas y sillas deben fabricarse si el artesano desea disminuir los costos?

SOLUCIÓN Variables de Decisión: X1 = Número de mesas a fabricar. X2 = Número de sillas a fabricar.

25

Función Objetivo: Para la Función Objetivo debemos conocer el costo por mesas fabricadas y el costo por sillas fabricadas, ya que al sumar dichos valores, tendremos el costo total por fabricar mesas y sillas que será nuestro Z. Recordemos algunos datos que nos brinda el problema: REQUERIMIENTOS

COSTO

PLANCHA DE MADERA

HORAS DE TRABAJO

2

1

1

2

1$

10$

COSTO TOTAL POR FABRICAR 𝑋1 MESAS: 1$ 10 $ 2 𝑝𝑙𝑎𝑛𝑐ℎ𝑎𝑠 ( ) 𝑋1 + 1 ℎ𝑜𝑟𝑎 𝑑𝑒 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 ( ) 𝑋1 = 𝟏𝟐𝑿𝟏 𝑝𝑙𝑎𝑛𝑐ℎ𝑎 ℎ𝑜𝑟𝑎 𝑑𝑒 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 COSTO TOTAL POR FABRICAR 𝑋2 SILLAS: 1$ 10 $ 1 𝑝𝑙𝑎𝑛𝑐ℎ𝑎𝑠 ( ) 𝑋2 + 2 ℎ𝑜𝑟𝑎 𝑑𝑒 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 ( ) 𝑋2 = 𝟐𝟏𝑿𝟐 𝑝𝑙𝑎𝑛𝑐ℎ𝑎 ℎ𝑜𝑟𝑎 𝑑𝑒 𝑡𝑟𝑎𝑏𝑎𝑗𝑜

El costo total por producir mesas y sillas será 12 X1+21 X2 , entonces nuestra función objetivo será: Minimizar Z = 12 X1+21 X2 Restricciones: Disponibilidad de planchas de madera. 2X1 + X2 ≤ 40 Disponibilidad de horas de trabajo. X1 + 2X2 ≤ 40 Requerimientos de fabricación. X1≤ 15 10≤ X2 ≤ 12 No negatividad. X1, X2 ≥ 0

Recordamos los datos del problema: REQUERIMIENTOS

DISPONIBILIDAD DE RECURSOS

PLANCHA DE MADERA

HORAS DE TRABAJO

2

1

1

2

40

40

El problema indicaba: “El Artesano quiere hacer un máximo de 15 mesas y entre 10 y 12 sillas.”

Entonces nuestro PPL es: 𝑴𝒊𝒏 𝑍 = 12𝑋1 + 21𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 3𝑋1 + 2𝑋2 ≤ 40 𝑋1 + 2𝑋2 ≤ 40 𝑋1 ≤ 15 10 ≤ 𝑋2 ≤ 12 𝑋1 , 𝑋2 ≥ 0

26

¡Listo! Ahora plantearemos y compararemos las tres Funciones Objetivo de los tres casos.

Como la utilidad = ganancia entonces la ganancia la obtenemos con el costo de las horas de trabajo únicamente.

Función Objetivo: Minimizar Z = 12 X1+21 X2

Atendiendo a las Utilidades:

Función Objetivo: Maximizar Z = 10 X1 + 20 X2

Atendiendo a las Función Objetivo: Horas de trabajo: Minimizar Z = X1 + 2 X2

En este caso queremos que las horas de trabajo sean las más bajas pero que cumpla las restricciones impuestas por el problema.

2

Atendiendo a los Costos:

CORTE DE ROLLOS DE PAPEL Se hacen pedidos a una papelera de 800 rollos de papel corrugado de 30 pulgadas de ancho, 500 rollos de 45 pulgadas y 1000 de 50 pulgadas. La papelera tiene solo rollos de 108 pulgadas de ancho. ¿Cómo deben cortarse los rollos parar surtir el pedido con el mínimo desperdicio de papel, sabiendo que el máximo desperdicio aceptable de papel por rollo es de 22 pulgadas?

SOLUCIÓN El problema dice que la papelera tiene solo rollos de 108 pulgadas, y que debe sobrar al cortar un máximo de 22 pulgadas (desperdicio aceptable) al cortar 30’, 45’ y 50’, entonces las posibles formas de corte serán: Desperdicio ≤ 22

Modelo 1 30

30

30

18

Modelo 2 30

30

3

45

Modelo 3 45

45

18

Modelo 4 45

50

13

Modelo 5 50

50

8

27

¡Ya podemos plantear el problema! Tenemos 5 modelos de cortes que la papelera deberá realizar, pero no sabemos cuántos de cada modelo, por eso definiremos nuestro planteamiento de esta manera: Variables de decisión: Xk : Cantidad de rollos de 108 pulgadas de ancho, cuyo corte se aplicará el modelo k =1, 2, 3, 4, 5 Plasmemos los datos en una tabla para plantear nuestra Función Objetivo y restricciones:

Restricciones F.O.

30’ 45’ 50’ Desperdicio (sobre 108’)

X1 3 0 0

X2 2 1 0

Modelos X3 0 2 0

18

3

18

X4 0 1 1

X5 0 0 2

13

8

Disponibilidad 800 500 1000

Función Objetivo: Debemos minimizar el desperdicio de papel en pulgadas, por lo que la F.O. será: Min Z = 18X1 + 3X2 + 18X3 + 13X4 + 8X5

Restricciones: Primer pedido (pedido de rollos de 30’) 3 X1 + 2 X2 = 800 Segundo pedido (pedido de rollos de 45’) X2 + 2X3 + X4 = 500 Tercer pedido (pedido de rollos de 50’) Restricciones X4 + 2X5 = 1000 F.O. No negatividad X1, X2, X3, X4, X5 ≥ 0

Observemos la tabla y veremos que por cada rollo de 30’, 45’ y 50’ hay cierta cantidad por cada modelo, por ejemplo: De los rollos de 30’ (primer pedido) hay 3 en el modelo X1 y hay 2 en el modelo X2 y su disponibilidad es de 800’. Así para cada restricción.

30’ 45’ 50’ Desperdicio (sobre 108’)

X1 3 0 0

X2 2 1 0

Modelos X3 0 2 0

X4 0 1 1

X5 0 0 2

Disponibilidad

18

3

18

13

8

800 500 1000

Entonces nuestro PPL es: 𝑴𝒊𝒏 𝑍 = 18𝑋1 + 3𝑋2 + 18𝑋3 + 13𝑋4 + 8𝑋5 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 3𝑋1 + 2𝑋2 = 800 𝑋1 + 2𝑋2 + 𝑋4 = 500 𝑋4 + 2𝑋5 = 1000 𝑋1 , 𝑋2 , 𝑋3 , 𝑋4 , 𝑋5 ≥ 0

28

3

PROBLEMA DE EMPAQUETAMIENTO Un distribuidor de pollos desea vender paquetes de menudencia: cuello, pata y molleja. Cada paquete debe estar compuesto por las tres menudencias y a lo más debe pesar 1 kilo, se desea vender un lote de 400 paquetes. Al distribuidor le cuesta la porción de cuello S/. 80, molleja S/.75 y pata S/. 50. Además: a. El peso combinado de molleja y pata debe ser por lo menos la mitad del paquete. b. El peso de cuello y pata no debe exceder los 500 gramos. c. Cualquier tipo de menudencia debe ser al menos 20% del paquete. d. Una porción equivale a 10 gramos. ¿Cuál debe ser la composición del paquete?

SOLUCIÓN Planteamos el problema en un cuadro para definir nuestro planteamiento.

Menudencias Cuello Pata Molleja

¿Y el dato de que se desea vender 400 paquetes? Es un dato que no necesitamos para el planteamiento. Con los datos ya planteados tendríamos una respuesta óptima. Sin embargo si deseamos utilizarlo, deberemos multiplicar a la FO por 400 y tendremos el costo total por empaquetar 400 paquetes. Es un dato del que podemos prescindir, y no afectará nuestra solución.

Costo

c/porción

S/. 80 S/. 75 S/. 50

Paquete Peso Cantidad máximo por vender 1 kilo

400

(1000 grs.)

Variables de Decisión: Me piden hallar la composición del paquete, por ello: X1: Cantidad de Gramos de cuello en un paquete. X2: Cantidad de Gramos de pata en un paquete. X3: Cantidad de Gramos de molleja en un paquete. Función Objetivo: Deseamos minimizar los costos del empaquetamiento: Min Z = 𝟖𝑿𝟏 + 𝟕, 𝟓𝑿𝟐 + 𝟓𝑿𝟑 Para el costo por paquete de X1 tenemos:

Restricciones:

80 soles 1 𝑝𝑜𝑟𝑐𝑖ó𝑛 𝑋1 𝑔𝑟𝑎𝑚𝑜𝑠 𝑠𝑜𝑙𝑒𝑠 × × = 𝟖𝑋1 𝑝𝑜𝑟𝑐𝑖ó𝑛 10 𝑔𝑟𝑎𝑚𝑜𝑠 𝑝𝑎𝑞𝑢𝑒𝑡𝑒 𝑝𝑎𝑞𝑢𝑒𝑡𝑒

Peso máximo del paquete:

X1 + X2 + X3 ≤ 1000 Peso combinado de molleja y pata: 𝑋1 + 𝑋2 + 𝑋3 X2 + X3 ≥ 2 Peso combinado de cuello y pata X1 + X2 ≤ 500 % Peso de cada menudencia. X1 ≥ 0.2 (X1 + X2 + X3) X2 ≥ 0.2 (X1 + X2 + X3) X3 ≥ 0.2 (X1 + X2 + X3) No negatividad X1, X2, X3 ≥ 0

El paquete pesa a lo más 1 kilo. El peso combinado de molleja y pata debe ser por lo menos la mitad del paquete. El peso de cuello y pata no debe exceder los 500 gramos.

Cualquier menudencia debe ser al menos 20 % del paquete.

29

Entonces nuestro PPL es: 𝑴𝒊𝒏 𝑍 = 8𝑋1 + 7,5𝑋2 + 5𝑋3 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 𝑋2 + 𝑋3 ≤ 1000 𝑋1 + 𝑋2 + 𝑋3 𝑋2 + 𝑋3 ≥ 2 𝑋1 + 𝑋2 ≤ 500 𝑋1 ≥ 0.2 (𝑋1 + 𝑋2 + 𝑋3 ) 𝑋2 ≥ 0.2 (𝑋1 + 𝑋2 + 𝑋3 ) 𝑋3 ≥ 0.2 (𝑋1 + 𝑋2 + 𝑋3 ) 𝑋1 , 𝑋2 , 𝑋3 ≥ 0

4

CRIANZA DE GANADO Un Granjero puede criar ovejas, cerdos y ganado vacuno. Tiene espacio para 30 ovejas, ó 50 cerdos, ó 20 cabezas de ganado vacuno, o cualquier combinación. Considerando la siguiente relación; 3 ovejas ocupan el mismo espacio de 5 cerdos y 3 ovejas ocupan el mismo espacio de 2 vacas. El Granjero debe criar, por ley al menos una cantidad de cerdo como ovejas y vacas juntas. Los beneficios por cada animal son; $50, $40 y $100 para ovejas, cerdos y vacas respectivamente.

SOLUCIÓN Ya que nuestro objetivo será maximizar las utilidades, plantearemos nuestro problema para esta pregunta: ¿Cuántas ovejas, cerdos y vacas debe criar el granjero para aumentar sus beneficios? Variables de Decisión:

X1: Cantidad de ovejas X2: Cantidad de cerdos X3: Cantidad de vacas

Función Objetivo: Deseamos maximizar las utilidades: Max Z = 𝟓𝟎𝑿𝟏 + 𝟒𝟎𝑿𝟐 + 𝟏𝟎𝟎𝑿𝟑 Ahora analicemos algunos datos del problema para definir nuestras restricciones. ¿Por qué me interesa saber el espacio límite? Es un dato que necesitamos para el planteamiento. Sin él, tendríamos una restricción “incompleta”, en el sentido de no aprovechar los datos que el problema nos brinda.

Primero, el problema nos dice que tiene espacio para 30 ovejas, ó 50 cerdos ó 20 vacas, es decir hay un espacio límite de área. ¿Y de qué tamaño es el espacio límite? ¿Podemos medirlo? Si. 30 ovejas

50 cerdos

20 vacas

¿? (espacio)

30

Otra forma de encontrar la equivalencia: Utilizando los datos del problema. 3 𝑋1 3 𝑋1 = 𝑦 = 5 𝑋2 2 𝑋3 Todo en función de ovejas: 3 3 𝑋 = 𝑋1 𝑦 𝑋3 = 𝑋1 5 2 2 Y como no puede haber más de 30 ovejas: 3 3 𝑋1 + 𝑋2 + 𝑋3 ≤ 30 5 2 10X1+ 6X2 +15X3 ≤ 300

Apliquemos Mínimo Común Múltiplo para conocer una equivalencia con el espacio de la granja: MCM (30, 50, 20) = 300 ue Entonces: 30 ovejas 50 cerdos 20 vacas 300 ue (espacio) Esta equivalencia nos describe que 30 ovejas, ó 50 cerdos ó 20 vacas ocupan 300 unidades de área de la granja. ¿Y cuánto ocupa una oveja? ¿Cuánto un cerdo? ¿Cuánto una vaca? Respondamos a estas preguntas con las equivalencias que ya tenemos. Si 30 ovejas ocupan 300 ue entonces:

1 oveja

1 cerdo Si 50 cerdos ocupan 300 ue entonces:

ocupa

ocupa

1 vaca Si 20 vacas ocupan 300 ue entonces:

10 ue

6 ue

15 ue ocupa

Ahora planteamos el problema en una tabla con los datos hallados y los que nos brinda el problema. Animales Oveja Cerdo Vaca Disponibilidad

Ocupa 10 6 15 300

Utilidad $ 50 $ 40 $ 100 Por ejemplo: 10 ue × 𝑋1 𝑜𝑣𝑒𝑗𝑎𝑠 = 𝟏𝟎𝑋1 𝑢𝑒 1 𝑜𝑣𝑒𝑗𝑎

Este valor es el espacio que Restricciones: ocuparan todas las ovejas que Combinación de los tres tipos de ganado. criará el granjero, y al tener el valor del espacio que ocuparán 10 X1 + 6 X2 + 15 X3 ≤ 300 los tres ganados juntos, sabemos Cantidad mínima de cerdos. que deberá ser no más que 300. X2 ≥ X1 + X 3 Se debe criar por ley al Limitaciones por capacidad. menos una cantidad de cerdo como ovejas y X1 ≤ 30 vacas juntas. X2 ≤ 50 Tiene espacio para 30 X3 ≤ 20 ovejas, ó 50 cerdos, ó No negatividad 20 cabezas de ganado X1, X2, X3 ≥ 0 vacuno.

31

Entonces nuestro PPL es: 𝑴𝒂𝒙 𝑍 = 50𝑋1 + 40𝑋2 + 100𝑋3 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 10𝑋1 + 6𝑋2 + 15𝑋3 ≤ 300 𝑋2 ≥ 𝑋1 + 𝑋3 𝑋1 ≤ 30 𝑋2 ≤ 20 𝑋3 ≤ 50 𝑋1 , 𝑋2 , 𝑋3 ≥ 0

5

PLANIFICACIÓN DE SIEMBRA Tres cooperativas agrarias cultivan remolacha, algodón y sorgo. El rendimiento agrícola de cada cooperativa está limitado por la cantidad de tierra irrigable, como por la cantidad de agua designada. Datos de los recursos de las cooperativas. COOP. 1 2 3

Tierra Irrigable

Asignación de agua

(acres)

(Acre/pie)

400 600 300

600 800 375

Estos cultivos difieren en su ganancia por acre y el consumo de agua. Se ha establecido una cuota máxima para el número total de acres que pueden dedicarse a cada uno de estos cultivos en las cooperativas. Cuota Máxima

Consumo de agua

Ganancia Neta

(Acres)

(pies / acres)

($ / acre)

Remolacha

600

3

400

Algodón

500

2

300

Sorgo

325

-

100

Cultivo

Variables de Decisión F.O .

Las tres cooperativas han convenido en sembrar la misma proporción de su tierra irrigable. La tarea que tiene la Oficina Técnica, es planear cuántos acres se ha de dedicar cada cultivo para cada cooperativa. El objetivo es maximizar la ganancia total de las cooperativas en su conjunto.

SOLUCIÓN

Xij

Cooperativa 1

Remolacha

Cooperativa 2

Algodón

Cooperativa 3

Sorgo

32

Como el problema indica, tendremos una variable que me indicará cuantos acres de cierta cooperativa está destina a cierto cultivo. Ejemplo: X1R = Cantidad de acres de la cooperativa 1 destinado al cultivo Remolacha.

Variables de Decisión: Xij: # Acres de la cooperativa i=1, 2, 3 destinados al cultivo j= R, A, S Función Objetivo: Deseamos maximizar la ganancia total por la venta de los 3 cultivos: Max Z = 400 (X1R + X2R + X3R) + 300 (X1A + X2A + X3A) + 100 (X1S + X2S + X3S) Venta en las 3 cooperativas

Restricciones: Disponibilidad de la tierra irrigable COOP1: X1R + X1A + X1S ≤ 400 COOP2: X2R + X2A + X2S ≤ 600 COOP3: X3R + X3A + X3S ≤ 300 Asignación de acres por cultivo: Remolacha : X1R + X2R + X3R ≤ 600 Algodón : X1A + X2A + X3A ≤ 500 Sorgo : X1S + X2S + X3S ≤ 325

Pacto social: Sembrar en la misma proporción de su tierra disponible. 𝑋1𝑅 + 𝑋1𝐴 + 𝑋1𝑆 400

=

𝑋2𝑅 + 𝑋2𝐴 + 𝑋2𝑆 600

=

𝑋3𝑅 + 𝑋3𝐴 + 𝑋3𝑆

𝑋1𝑗

300

400

9

5 2 5

=

𝑋2𝑗 600

=

𝑋3𝑗 300

La siembra (acres) será proporcional a la tierra disponible de cada uno.

Asignación de agua: COOP1: 2X1R +

Es decir:

X1A ≤ 600

COOP2: 3X2R + 3X2A ≤ 800 COOP3: 6X3R + No negatividad

10 3

X3A ≤ 375

XA1, XA2, XA3, XB1, XB2 ≥ 0 Para esta última restricción hemos usado: Cultivo

Cuota Máxima

Consumo de agua

(Acres)

(pies / acres)

Remolacha

600

3

Algodón

500

2

Sorgo

325

-

COOP. 1 2 3

Tierra Irrigable

Asignación de agua

(acres)

(Acre/pie)

400 600 300

600 800 375

Por ejemplo, el cultivo destinado a la cooperativa 1 deberá cumplir con el consumo de agua del cultivo y la asignación de agua. Para ello: Primero vemos la cantidad de pies que usará la remolacha: 600*3 = 1800 pies, luego debemos saber qué parte pertenece a dicha cooperativa, por eso dividimos entre 400: 1800/400= 9/2 acre/pie. En el caso del algodón será 5/2 y en el caso de sorgo 0. Entonces, al sumar estas cantidades deberá ser no más de 600 acre/pie (asignación de agua) para la cooperativa 1.

33

6

DISTRIBUCIÓN DE JORNADAS DE TRABAJO En un establecimiento comercial se desea encontrar el menor número de empleados para una jornada de 12 horas de trabajo y donde los empleados deben trabajar jornadas de 6 horas consecutivas, cumpliendo los siguientes requerimientos: Tiempo Número Turno del Día Mínimo de (horas) Empleados 1 17-20 4 2 20-23 8 3 23-02 10 4 02-05 6

SOLUCIÓN4

Analicemos, por ejemplo, si en el primer turno se tiene a 4 empleados, entonces: Tiempo 17 4 4 empleados ya cumplieron las 3 horas.

3 horas

20

3 horas

23

3 horas

02

3 horas

empleados

TURNO 1

05 ¿Quiénes van cumpliendo la jornada 6hrs?

4+4 TURNO 2

4+6 Esos 4 empleados ya 6 horas cumplieron las 6 horas, y 4 empleados nuevos TURNO 3 cumplen 3 horas. 6 horas Esos 4 empleados ya cumplieron las 6 horas, y 6 empleados nuevos Esos 6 empleados ya cumplen 3 horas. cumplieron las 6 horas y n empleados cumplen 3 horas.

6+n TURNO 4

Variables de Decisión: Xk: Cantidad de empleados requeridos al inicio de turno k= 1, 2, 3, 4 Función Objetivo: Deseamos maximizar las utilidades: Min Z = X1 + X2 + X3 + X4 Restricciones: Limitaciones del número de empleados por turno: Turno 1: X1 ≥ 4 Turno 2: X1 + X2 ≥ 8 Turno 3: X2 + X3 ≥ 10 Turno 4: X3 + X4 ≥ 6 No negatividad X1, X2, X3, X4 ≥ 0

X4 probablemente sea 0, pero eso no interesa, por ahora solo queremos plantear el problema, no hallar el valor de las variables.

34

MÉTODOS DE SOLUCIÓN GRÁFICO

3.1

Introducción Un problema general de programación lineal, puede ser resuelto por:  Método Gráfico  Método Analítico (pe: Simplex, Algebraico)  Computacionales (pe: LINDO) El método gráfico no es recomendable para dimensiones mayores a 2, es decir R2. Los métodos analíticos utilizan los conceptos del algebra lineal entre ellos el Simplex, Simplex dual. También se cuenta con una amplia variedad de software computacional para hallar la solución del PL. El método gráfico utiliza la geometría plana, es fácilmente comprensible y brinda una idea clara de lo que sucede al resolver un

35

problema lineal. Nos permite visualizar algunas propiedades de la programación lineal. El método gráfico tiene una metodología:  Gráfica de la Región Factible  Diseño del a Función Objetivo  Desplazamiento de la Función Objetivo en dirección del incremento (ó decremento) del valor de la Función Objetivo. Para conocer el cómo aplicar el método gráfico, primero debemos conocer algunos conceptos básicos que se explicarán a continuación.

3.2

Conjuntos Convexos

Un subconjunto S de puntos es un conjunto convexo si todos los puntos del segmento de recta que une a cualquier par de puntos del conjunto también pertenecen al conjunto S. Para comprender mejor la definición del conjunto convexo debe tenerse en cuenta que dado dos puntos x1 y x2, los puntos 𝛌𝐗 + (𝟏 − 𝛌)𝐘 con 𝟎 ≤ 𝛌 ≤ 𝟏 corresponden justamente con los puntos del segmento que une x1 y x2. Ejemplos de conjuntos convexos: B

A

B

A

Los que no son conjuntos convexos sería: A

B

A

A B

B

B

La línea completa no está dentro del conjunto.

A B

A

Definición Formal.EL conjunto S ⊂ Rn es convexo si: ∀ x1, x2 ∈ S ∀ λ ∈ ℝ, 0 ≤ λ ≤ 1 Los puntos 𝑥 = λx1 + (1 − λ)x2 Pertenecen a S.

Obsérvese que:  Cuando λ = 1 entonces x=x1  Cuando λ = 0 entonces x=x2 Para valores de λ comprendidos entre 0 y 1 el punto x se sitúa entre x1 y x2.

Vértices o Puntos extremos de un conjunto convexo.Un punto x de un conjunto convexo S es un vértice o punto extremo si no es posible encontrar dos puntos x1, x2 en S tales que:

𝑥 = λx1 + (1 − λ)x2 0≤ λ≤1

Punto extremo

36

Para cualquier conjunto convexo S ⊂ Rn. Un punto X de S es un punto extremo si para cada segmento rectilíneo que se encuentra completamente en S y que pasa por el punto X, X es un extremo del segmento rectilíneo. En un programa lineal con conjunto factible S, se verifica que X ∈ S es un punto extremo de S si y solo si es una solución básica factible del programa lineal expresado en forma estándar.

3.3

Método Gráfico

Para aplicar el Método Gráfico debemos seguir algunos pasos que describiremos a continuación, partiendo de un ejemplo: 𝑴𝒂𝒙 𝑍 = 4𝑋1 + 6𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 𝑋2 ≤ 70 𝑋1 + 𝑋2 ≤ 40 𝑋1 + 3𝑋2 ≤ 90 𝑋1 , 𝑋2 , ≥ 0 Paso 1.- Definimos a cada restricción como la recta L1, L2, L3. 2𝑋1 + 𝑋2 ≤ 70 …L1 𝑋1 + 𝑋2 ≤ 40 …L2 𝑋1 + 3𝑋2 ≤ 90 …L3 Paso 2.- Tabularemos, para ello la ecuación “≥” ó “≤” serán ahora “=” Para 2𝑋1 + 𝑋2 = 70 de L1

X1 0 35

X2 70 0

𝑋1 + 𝑋2 = 40 de L2

X1 0 40

X2 40 0

Para 𝑋1 + 3𝑋2 = 90 de L3

X1 0 90

X2 30 0

Para

Una manera de saber qué área sombrear, es evaluando algún punto en la restricción. En L1, por ejemplo, si evaluamos el punto (0,0) vemos que sí cumple la restricción 2𝑋1 + 𝑋2 ≤ 70 ya que 0 ≤ 70, entonces esa área sea la sombreada.

Si X1 = 0  X2 = 70 Si X2 = 0  X1 = 35 Entonces, la recta L1 tiene los puntos (0,70) y (35,0)

Paso 3.- Graficamos, donde las variables de decisión serán los ejes del plano. (A fines educativos los graficamos por separado.) ¿Siempre será el área encerrada la que se sombree? No, depende de si la restricción de la recta es ≤ ó ≥ ó =

37

Ahora, intersectaremos estas área en un gráfico y veamos cual es el área que originan las inecuaciones.

Recuerda: El gráfico siempre se ubicará en el primer cuadrante, donde ambas variables son > o = a cero. A excepción de que el el PPL indique tener una variable irrestricta.

2𝑋1 + 𝑋2 ≤ 70 …L1 𝑋1 + 𝑋2 ≤ 40 …L2 𝑋1 + 3𝑋2 ≤ 90 …L3

El área sombreada es la REGIÓN FACTIBLE.

Paso 4.- Vemos en el gráfico que no tenemos los puntos de P y Q, así que debemos hallarlos. Sabemos que: Resolvemos el sistema de ecuaciones



Punto P = L ∩ L 2

3

𝑋1 + 𝑋2 = 40 𝑋1 + 3𝑋2 = 90 𝑋1 = 15 𝑋2 = 25



Punto Q = L ∩ L 1

2

2𝑋1 + 𝑋2 = 70 𝑋1 + 𝑋2 = 40 𝑋1 = 30 𝑋2 = 10

Paso 5.- Evaluamos cada punto de la Región Factible en la función Objetivo: 𝑴𝒂𝒙 𝑍 = 4𝑋1 + 6𝑋2 PUNTOS

Z

A = (0,0)

0

B = (0,30)

180

P = (15,25)

210

La F.O. es de 𝑴𝒂𝒙𝒊𝒎𝒊𝒛𝒂𝒓 entonces elegimos el Z máximo.

Q = (30,10) 180 R = (35,0)

140

Paso 6.- Solución. ¿Variables básicas? ¿Variables no básicas? Por ahora debemos saber que las variables básicas son nuestras variables de decisión, las no básicas son aquellas que tendrán valor igual a cero. Ver pag. XXX para aclarar la definición.

𝑴𝒂𝒙 𝑍 = 4𝑋1 + 6𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 𝑋2 ≤ 70 𝑋1 + 𝑋2 ≤ 40 𝑋1 + 3𝑋2 ≤ 90 𝑋1 , 𝑋2 , ≥ 0

La solución óptima es Z*= 210 porque 4(15) + 6(25) = 210

], 𝑋𝐵 = [𝑋𝑋1 ] = [15 25 2

𝑆1

0

𝑆3

0

XB = Variables básicas XN = Variables no básicas

𝑋𝑁 = [𝑆2 ] = [0] Si el problema fuese de recursos y utilidades, entonces podrá interpretarse a que debe usarse 15 recursos tipo 1 y 25 recursos tipo 2 38 para tener la máxima utilidad de 210.

Observemos la gráfica para conocer algunas definiciones (en color puntos que cumplen cada definición):

los

(0,0), (0,30), (0,40), (0,70), (35,0), (40,0), (90,0) (15,25), (30,10)

Son los puntos de la región que se encuentran en la intersección de rectas o hiperplanos o en la intersección con los ejes coordenados. Solución Básica (15,25)

Solución básica factible que maximiza o minimiza la FO. Solución Óptima

Región que cumple con todas las restricciones del problema y las condiciones de no negatividad. Se caracteriza por ser convexa. Región Factible Solución Básica Factible Degenerada Solución factible en que una o más variables básicas factibles toman el valor cero. (0,0), (0,30), (35,0)

Soluciones Factibles

Solución Básica Factible

Es cualquier punto del plano situado en la región factible.

Aquella solución Básica donde se cumplen todas las restricciones, que vienen a ser los puntos extremos. (0,0), (0,30), (35,0), (15,25), (30,10)

Solución PL Factible

No factible

Solución Óptima Solución No óptima

POSIBLES SOLUCIONES Un problema de Programación Lineal no siempre presenta una única solución óptima, existen otras posibles soluciones según la región factible:

Región Acotada / Limitada PL Solución Única

PL Óptimas Alternativas

PL Solución Única

Región No Acotada / Ilimitada

Región vacía

PL Óptimas Alternativas

PL Inviable

PL Ilimitado

39

3.4

Tipos de problemas lineales 1. Problemas que admiten una única solución. Se presenta cuando la región es limitada y la solución cae en un vértice de la región. 2. Problemas que admiten múltiples soluciones (óptimas alternativas). Se presenta cuando la solución cae en un extremo (lado o rayo) de la región, esto es, todos los puntos (infinitos) que se encuentran en el extremo óptimo hacen máximo (o mínimo) el valor de la función. Se presenta cuando la línea de la F.O. es paralela a una de las restricciones. 3. Problemas que no tienen solución (problemas inviables). Se presenta cuando la región que describe el problema es vacío. Esta clase de problemas se presenta cuando existe incongruencia en los datos y/o especificaciones; o cuando el problema no está bien formulado. 4. Problemas con solución ilimitada. Se presenta cuando la región es ilimitada y la solución no cae en ningún extremo de la región. Esto es posible encontrar puntos en la región factible con valores de la función objetivo muy grandes (∞ en caso de problema de máx.) o muy pequeños (-∞ en caso de problemas de min). Se presenta en caso de que la formulación del problema no es correcta.

3.5

Ejemplos 1

Dado el modelo lineal:

𝑴𝒊𝒏 𝑍 = 2𝑋1 + 5𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 3𝑋1 + 𝑋2 ≥ 4 …L1 2𝑋1 + 3𝑋2 ≥ 5 …L2 𝑋1 , 𝑋2 , ≥ 0

SOLUCIÓN: L1: 3𝑋1 + 𝑋2 = 4 SOLUCIÓN ÓPTIMA Y REGIÓN NO ACOTADA

L2: 2𝑋1 + 3𝑋2 = 5

X1 0 4/3

X2 4 0

X1 0 5/2

X2 5/3 0

PUNTOS

Z

P = (0,4)

20

Q = (1,1)

7

X1 X2 0 70 R = (2.5,0) Región 35 Factible 0No Acotada

5

El PPL es de Minimizar, entonces, Z* = 5

Solución.] = [2,5 ] 𝑋𝐵 = [X1 X2 0 ] = [00] 𝑋𝑁 = [S1 S2 La solución óptima es Z* = 5 si la FO: Min Z=2(2,5)+5(0)=5

40

2

Dado el modelo lineal:

𝑴𝒂𝒙 𝑍 = 2𝑋1 + 2𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 − 𝑋2 ≥ 1 …L1 −𝑋1 + 2𝑋2 ≤ 4 …L2 𝑋1 , 𝑋2 , ≥ 0

SOLUCIÓN: L1:

𝑋1 − 𝑋2 = 1 NO TIENE SOLUCIÓN Y REGIÓN NO ACOTADA

L2:

−𝑋1 + 2𝑋2 = 4

X1 0 1

X2 -1 0

X1 0 -4

X2 2 0

El PPL es de Maximizar, proyectamos la FO de abajo hacia arriba, donde Z crece y continúa al infinito sin tener un punto máximo extremo. Región Factible No Acotada

Solución.El PPL no tiene solución óptima

¿Cómo graficar la F.O.? Dale el valor que quieras al Z y tabula los valores de X1 y X2, en este caso le asigné el valor creciente arbitrario Z=8, donde tendré X1=2 y X2=2. Busco saber para donde crece el Z, entonces ahora evalúo en el punto P (6,5), y será Z=22. El Z ha crecido de 8 a 22, entonces ya conocemos su dirección. Podemos ir proyectando la FO en la dirección en la que crece hasta llegar al punto óptimo. En este caso no hay punto máximo extremo, porque la región es no acotada(infinita).

3

SOLUCIÓN ÓPTIMA

Observemos que cuando una restricción es de igualdad, es muy probable que la región factible sea representada en una línea dependiendo de que el PPL sea Max ó Min. En este caso el PPL es de Max y L2=0

Dado el modelo lineal:

𝑴𝒂𝒙 𝑍 = 2𝑋1 + 3𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 3𝑋2 ≤ 10 …L1 6𝑋1 + 2𝑋2 = 8 …L2 𝑋1 + 5𝑋2 ≥ 4 …L3 𝑋1 , 𝑋2 , ≥ 0

SOLUCIÓN: X1 0 5

X2 10/3 0

L2: 6𝑋1 + 2𝑋2 = 8

X1 0 4/3

X2 4 0

L3: 𝑋1 + 5𝑋2 = 4

X1 0 4

X2 4/5 0

L1: 2𝑋1 + 3 𝑋2 = 10

La Región Factible es el segmento de recta sombreada

PUNTOS

Z

P = (0.29,3.14)

10

Q = (1.15,0.57) 4.01

X1 0 35

X2 70 0

El PPL es de Maximizar, entonces, Z* = 10

Solución.] = [0.29 ] 𝑋𝐵 = [X1 X2 3.14 ] = [00] 𝑋𝑁 = [S1 S2 La solución óptima es Z* = 10 si la FO: Z=2(0.29)+3(3.14)=10

41

4

Dado el modelo lineal:

𝑴𝒂𝒙 𝑍 = 𝑋1 + 𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 𝑋2 ≤ 4 …L1 6𝑋1 + 𝑋2 ≤ 12 …L2 𝑋1 , 𝑋2 , ≥ 0

SOLUCIÓN: L1: 𝑋1 + 𝑋2 = 4 SOLUCIÓN MÚLTIPLE INIFINITA EN REGIÓN ACOTADA

Observemos que cuando una restricción es paralela a la FO, es muy probable que presente una solución representada en una línea dependiendo de que el PPL sea Max ó Min. En este caso el PPL es de Max y L1 //FO

L2: 6𝑋1 + 𝑋2 = 12

X1 0 4 X1 0 2

X2 4 0 X2 12 0

Z

A = (0,4)

4

P = (1.6,2.4)

4

Solución.La solución óptima es Z* = 4 Y TIENE INFINITAS SOLUCIONES ÓPTIMAS. Una de ellas es: ] = [04] 𝑋𝐵 = [X1 X2 ] = [00] 𝑋𝑁 = [S1 S2

El segmento de recta sombreada son todos los puntos infinitos óptimos del PPL. Y podemos expresarlo de esta manera: 𝜆(0,4) + (1 − 𝜆)(1.6,2.4) con 0 ≤ 𝜆 ≤ 1 Esta ecuación proporciona todos los puntos óptimos del PPL siempre y cuando 0 ≤ 𝜆 ≤ 1. Cuando reemplazamos 𝜆 = 1 por ejemplo, la ecuación te dará el punto (0,4).

5

Dado el modelo lineal:

SOLUCIÓN: L1: 𝑋1 + 𝑋2 = 10 NO EXISTE REGIÓN FACTIBLE Y NO TIENE SOLUCIÓN

PUNTOS

El PPL es de Maximizar, entonces, Z* = 4

L2: 𝑋1 + 𝑋2 = 5

X1 0 10

X2 10 0

X1 0 5

X2 5 0

𝑴𝒂𝒙 𝑍 = 2𝑋1 + 3𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 𝑋2 ≥ 10 …L1 𝑋1 + 𝑋2 ≤ 5 …L2 𝑋1 , 𝑋2 , ≥ 0 No existe Región Factible (región que cumpla las inecuaciones)

Solución.EL PPL NO TIENE SOLUCIÓN

42

6

Dado el modelo lineal:

𝑴𝒂𝒙 𝑍 = 5𝑋1 + 4𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 6𝑋1 + 4𝑋2 ≤ 24 …L1 𝑋1 + 2𝑋2 ≤ 6 …L2 −𝑋1 + 𝑋2 ≤ 1 …L3 𝑋2 ≤ 2 …L4 𝑋1 , 𝑋2 , ≥ 0

SOLUCIÓN: Si graficamos la FO, veremos que el punto C (3,1.5) es el punto óptimo. Y ya no hallaríamos las coordenadas del resto de puntos ni evaluaríamos el Z en cada uno.

L1: 6𝑋1 + 4𝑋2 = 24 L2: 𝑋1 + 2𝑋2 = 6 L3: −𝑋1 + 𝑋2 = 1 L4: 𝑋2 = 2

El PPL es de Maximizar, entonces, Z* = 21 X1 0 4

X2 6 0

X1 0 6

PUNTOS

X2 3 0

X1 0 -1

X2 1 0

Z

A = (0,0)

0

B = (4,0)

20

C = (3,1.5)

21

D = (2,2)

18

E = (1,2)

13

F = (0,1)

4

REGIÓN FACTIBLE

La solución óptima es Z* = 21 ya que FO: Z=5(3)+4(1.5)=21 S1

0

S4

0

3 0 ] = [1.5 ] , 𝑋𝑁 = [S2 𝑋𝐵 = [X1 S3] = [0] X2

7

Dado el modelo lineal:

𝑴𝒊𝒏 𝑍 = 0.3𝑋1 + 0.9𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 𝑋2 ≥ 800 …L1 0.21𝑋1 − 0.3𝑋2 ≤ 0 …L2 0.03𝑋1 − 0.01𝑋2 ≥ 0 …L3 𝑋1 , 𝑋2 , ≥ 0

SOLUCIÓN: L1: 𝑋1 + 𝑋2 = 800 L2: 0.21𝑋1 − 0.3𝑋2 = 0 L3: 0.03𝑋1 − 0.01𝑋2 = 0

X1 0 800

X2 800 0

X1 0 470.6

X2 0 329.4

X1 0 198.5

X2 0 601.5

El PPL es de Minimizar, entonces, Q ES EL PUNTO ÓPTIMO REGIÓN FACTIBLE

La solución óptima es Z* = 437.64 ya que FO: Z = 0.3 (470.6)+ 0.9 (329.4) = 437.64 S1

0

S3

0

] = [470.6 ] , 𝑋𝑁 = [S2] = [0] 𝑋𝐵 = [X1 X2 329.4

43

8

Caso: PRODUCCIÓN DE SOMBREROS Una Compañía produce dos tipos de sombrero vaquero, cada sombrero del tipo 1 requiere el doble de tiempo en mano de obra que el tipo II. Si todos los sombreros son solo del tipo II, la Compañía puede producir un total de 500 sombreros al día. El mercado limita las ventas diarias del tipo I y II a 150 y 250 sombreros respectivamente. Los beneficios por sombrero son $8 para el tipo I y $5 para el tipo II. Determinar el número de sombreros que deben producirse de cada tipo.

SOLUCIÓN.Variable de decisión.Xj : Cantidad de sombreros a producir del tipo = I y II. Función Objetivo.Beneficio total de la producción de sombreros, maximizar las ganancias. Max Z = 8X1 + 5X2 Restricciones.1. Proporcionalidad en la producción de sombreros: 𝑋1 1 = → 𝑋2 = 2𝑋1 → 2𝑋1 + 𝑋2 ≤ 500 X2 2 2. Ventas del sombrero tipo I X1 ≤ 150 3. Ventas del sombrero tipo II X2 ≤ 250 4. No Negatividad X1, X2 ≥ 0. El PPL es de Maximizar, entonces, Q ES EL PUNTO ÓPTIMO

𝑴𝒂𝒙 𝑍 = 8𝑋1 + 5𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 𝑋2 ≤ 500 …L1 𝑋1 ≤ 150 …L2 𝑋2 ≤ 250 …L3 𝑋1 , 𝑋2 , ≥ 0

PUNTOS

Z

A = (0,0)

0

B = (150,0)

1200

Q = (125,250) 2250 R = (150,200) 2200

La solución óptima es Z* = 2250 ya que Z* = 8(125)+ 5 (200) = 2250

] = [125 ] 𝑋𝐵 = [X1 X2 250 S1

0

S3

0

P = (0,250)

1250

REGIÓN FACTIBLE

𝑋𝑁 = [S2] = [0] La compañía tiene que producir 125 sombreros tipo I y 250 sombreros tipo II para lograr el beneficio máximo de 2250.

44

3.6

Ejercicios 𝑴𝒂𝒙 𝑍 = 𝑋1 + 𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 𝑋2 ≤ 23 𝑋1 + 2𝑋2 ≥ 25 𝑋1 , 𝑋2 , ≥ 0 𝑴𝒊𝒏 𝑍 = 8𝑋1 + 3𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 9𝑋1 − 2𝑋2 ≤ 20 10𝑋1 + 3𝑋2 ≤ 32 𝑋1 , 𝑋2 , ≥ 0 𝑴𝒊𝒏 𝑍 = 3𝑋1 + 4𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 3𝑋2 ≥ 6 𝑋1 + 𝑋2 ≥ 4 𝑋1 , 𝑋2 , ≥ 0 𝑴𝒂𝒙 𝑍 = 5𝑋1 + 3𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 4𝑋2 ≤ 23 𝑋1 + 2𝑋2 ≤ 25 𝑋1 , 𝑋2 , ≥ 0 𝑴𝒂𝒙 𝑍 = 5𝑋1 + 6𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 3𝑋1 + 5𝑋2 ≤ 30 2𝑋1 + 3𝑋2 ≤ 1 𝑋1 + 5𝑋2 ≥ 1 4𝑋1 + 𝑋2 ≤ 8 𝑋1 , 𝑋2 , ≥ 0 𝑴𝒂𝒙 𝑍 = 12𝑋1 + 10𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 6𝑋1 + 𝑋2 ≤ 6 9𝑋1 + 4𝑋2 ≤ 18 2𝑋1 + 5𝑋2 ≤ 20 𝑋1 + 𝑋2 ≤ 1 𝑋1 , 𝑋2 , ≥ 0

𝑴𝒊𝒏 𝑍 = 𝑋1 + 𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 −𝑋1 + 𝑋2 ≤ 2 𝑋1 + 𝑋2 ≤ 5 𝑋1 ≤ 3 𝑋1 , 𝑋2 , ≥ 0 𝑴𝒂𝒙 𝑍 = 6𝑋1 + 5𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 3𝑋1 + 2𝑋2 ≤ 60 3𝑋1 + 4𝑋2 ≤ 48 𝑋1 , 𝑋2 , ≥ 0 𝑴𝒂𝒙 𝑍 = 10𝑋1 + 8𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 7𝑋1 + 4𝑋2 ≥ 35 3𝑋1 − 2𝑋2 ≤ 3 𝑋1 , 𝑋2 , ≥ 0 𝑴𝒂𝒙 𝑍 = 2𝑋1 + 3𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 𝑋2 ≤ 48 𝑋1 + 2𝑋2 ≥ 30 9𝑋1 + 5𝑋2 ≤ 32 𝑋1 , 𝑋2 , ≥ 0 𝑴𝒂𝒙 𝑍 = 3𝑋1 + 7𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 6𝑋1 + 11𝑋2 ≤ 66 2𝑋1 + 𝑋2 ≤ 10 0.5𝑋1 + 0.4𝑋2 ≥ 6 𝑋1 + 𝑋2 ≥ 4 𝑋1 , 𝑋2 , ≥ 0 𝑴𝒂𝒙 𝑍 = 5000𝑋1 + 3000𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 3𝑋1 + 5𝑋2 ≤ 1 50𝑋1 + 200𝑋2 ≤ 10 𝑋1 , 𝑋2 , ≥ 0

𝑴𝒂𝒙 𝑍 = 4𝑋1 + 4𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 −2𝑋1 + 2𝑋2 ≤ 2 −1𝑋1 + 2𝑋2 ≤ 4 𝑋1 , 𝑋2 , ≥ 0 𝑴𝒂𝒙 𝑍 = 2𝑋1 + 2𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 − 𝑋2 ≤ 2 𝑋1 + 𝑋2 ≥ 4 𝑋1 , 𝑋2 , ≥ 0 𝑴𝒂𝒙 𝑍 = 8𝑋1 + 10𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 4𝑋1 + 3𝑋2 ≤ 10 𝑋1 + 2𝑋2 ≤ 5 𝑋1 , 𝑋2 , ≥ 0 𝑴𝒊𝒏 𝑍 = 8𝑋1 + 5𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 𝑋2 ≤ 500 𝑋1 ≤ 150 𝑋2 ≤ 250 2𝑋1 = 𝑋2 𝑋1 , 𝑋2 , ≥ 0 𝑴𝒂𝒙 𝑍 = 100𝑋1 + 120𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 5𝑋1 + 6𝑋2 ≥ 30 8𝑋1 + 4𝑋2 ≤ 64 𝑋1 , 𝑋2 , ≥ 0 𝑴𝒊𝒏 𝑍 = 3𝑋1 + 5𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 3𝑋1 + 3𝑋2 ≤ 18 𝑋1 ≤ 4 𝑋2 ≤ 6 𝑋1 + 4𝑋2 ≤ 10 𝑋1 , 𝑋2 , ≥ 0

45

MÉTODO SIMPLEX

4.1

Introducción Es un procedimiento algebraico creado por George Dantzig en 1947 para hallar la solución óptima a un problema de Programación Lineal. Desde que las soluciones que optimizan la F.O. se encuentran en la frontera de la región Factible y en particular en los vértices de esta. El simplex localiza un vértice de la región y salta para el siguiente vértice adyacente de forma que mejore el valor de la F.O. Con este método, en vez de probar con cada punto extremo de la región de factibilidad, se inicia con cualquier punto extremo de la región de factibilidad y mediante transformaciones elementales se llega a puntos extremos más eficientes.

46

4.2

Definiciones Previas ESTANDARIZACIÓN.- Es el proceso por el cual se eliminan las inecuaciones del sistema añadiendo variables de holgura o de excedencia obteniendo así un sistema de ecuaciones. Modelo General:

Forma Estándar: 𝑛

𝑴𝒂𝒙 ( 𝒐 𝑴𝒊𝒏) 𝑍 = ∑ 𝐶𝑗 𝑋𝑗

𝑛

𝑴𝒂𝒙 ( 𝒐 𝑴𝒊𝒏)𝑍 − ∑ 𝐶𝑗 𝑋𝑗 ± 0 ∑ 𝑆𝑗 = 0

𝑖=1

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑚

𝑖=1

𝑖=1

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 ≤ 𝑏 𝑖 = 1,2, … , 𝑛 ≥ 𝑖

∑ 𝑎𝑖𝑗 𝑥𝑗 𝑥𝑗 ≥ 0

𝑗 = 1,2, … , 𝑚

∑ 𝑎𝑖𝑗 𝑥𝑖 ± 𝑆𝑗 = 𝑏𝑗 𝑖 = 1,2, … , 𝑛 𝑥𝑗 , 𝑆𝑗 ≥ 0

𝑗 = 1,2, … , 𝑚

Variables de Holgura

 En las restricciones (≤) el lado derecho representa el límite sobre la disponibilidad de un recurso y el lado izquierdo el uso de ese recurso limitado.  Una holgura representa la cantidad del recurso que no se utiliza.  Las variables positivas Sj introducidas para convertir las desigualdades ≤ en igualdades (=), y se llaman variables de holgura. El problema Modelo General:

Forma Estándar:

𝑴𝒂𝒙 𝑍 = 3𝑋1 + 4𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑴𝒂𝒙 𝑍 − 3𝑋1 − 4𝑋2 = 0

adopta la forma estándar con n + m= 4 incógnitas.

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 3𝑋1 + 4𝑋2 ≤ 16

3𝑋1 + 4𝑋2 + 𝑺𝟏

2𝑋1 + 3𝑋2 ≤ 9

2𝑋1 + 3𝑋2

𝑋𝑖 ≥ 0

𝑖 = 1,2

Variables de Exceso o Superávit

= 16

+ 𝑺𝟐 = 9

𝑋𝑖 ≥ 0 𝑆𝑗 ≥ 0

𝑖 = 1,2 𝑗 = 1,2

𝑋 ≥0

𝑖 = 1,2

 Las restricciones (≥) determinan requerimientos 𝐼mínimos de especificaciones.  Un superávit representa el exceso del lado izquierdo sobre el requerimiento mínimo.  Las variables positivas Sj introducidas para convertir las desigualdades ≥ en igualdades (=), se llaman variables de exceso.

47

Modelo General:

Forma Estándar:

𝑴𝒂𝒙 𝑍 = 5𝑋1 + 𝑋2

𝑴𝒂𝒙 𝑍 − 5𝑋1 − 𝑋2 = 0

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 4𝑋2 ≥ 16

2𝑋1 + 4𝑋2 − 𝑺𝟏

𝑋1 − 6𝑋2 ≥ 9 𝑋𝑖 ≥ 0

4.3 El MÉTODO SIMPLEX se aplica en sólo problemas con restricciones ≤, entonces solo deberás añadir variables de holgura.

Forma Estándar: 𝑛

𝑚

𝑍 − ∑ 𝐶𝑗 𝑋𝑗 ± 0 ∑ 𝑆𝑗 = 0 𝑖=1

El problema adopta la forma estándar con n + m= 4 incógnitas.

𝑋1 − 6𝑋2

𝑖 = 1,2

Método Simplex

= 16

− 𝑺𝟐 = 9

𝑋𝑖 ≥ 0 𝑆𝑗 ≥ 0

𝑖 = 1,2 𝑗 = 1,2

𝑋𝐼 ≥ 0

𝑖 = 1,2

El simplex inicia con una solución factible y cuando las restricciones son ≤, una solución factible ocurre en el origen de coordenadas. PROCEDIMIENTO.1. Se estandarizan la función objetivo y el sistema de inecuaciones que determina al problema. 2. Se expresa el problema en forma de tabla. 3. Se escoge la solución básica inicial y empieza la iteración. 4. Generar una nueva solución factible usando las condiciones de optimalidad y factibilidad hasta que dicha solución óptima sea obtenida, siempre que exista y sea finito.

𝑖=1

FORMA DE TABLA.Sol. Básica Inicial Coef. F.O.

Después de varias iteraciones la tabla tiene la forma:

Var. NO Básicas

Valor Objetivo

Z 1 0 0 … 0

Z S1 S1 … Sn

Var. Básicas

Var. De Decisión

x1 -C1 a11 a21 … am1

x2 -C2 a12 A22 … am2

… … … … … …

xn -Cn a1n a2n … amn

Z aB1 aB2 … aBm

Z 1 0 0 … 0

S1 0 1 0 … 0

S2 0 0 1 … 0

… … … … … …

Sn 0 0 0 … 1

Sol. 0 b1 b2 … bm

Sol. Z0 XB1 XB2 … XBm

Matriz Identidad

Coeficientes en las restricciones Base

bj

Var. De Holgura/Exceso

x1

x2

…

xn

Xn+1

Xn+2

…

Xn+m

Z1-C1

Z2-C2

…

Zn-Cn

Zn+1-Cn+1

Zn+2-Cn+2

…

Zn+m-Cn+m

Y11 Y21 … Ym1

Y12 Y22 … Ym2

… … … …

Y1n Y2n … Ymn

Y1n+1 Y1n+2 Y2n+1 Y2n+2 … … Ymn+1 Ymn+2

… … … …

Y1n+m Y2m+n … Ymm+n

48

Ahora veamos un ejemplo para entender el método simplex y algunas propiedades importantes.

EJEMPLO

Un carpintero fabrica sillas y mesas, su producción está limitada por lo siguiente: Él dispone por semana 36 listones. - Para cada silla requiere 4 listones de madera. - Para cada mesa requiere 4 listones de madera. Él dispone por semana 48 horas de mano de obra. - Para cada silla dispone 3 horas de mano de obra. - Para cada mesa dispone 6 horas de mano de obra. Determine el plan de producción óptima, si: - La utilidad por silla es s/200 - La utilidad por mesa es s/300 SOLUCIÓN.Variables de decisión: X1: cantidad de sillas a producir X2: cantidad de mesas a producir

Función Objetivo: Maximizar ganancias (beneficios) Max Z = 200 X1 + 300 X2 Restricciones: Según limitación de madera: 4X1 + 4X2 ≤ 36 Según mano de obra: X1 + 6X2 ≤ 48 Restricción de No negatividad X1, X2 ≥ 0

SIMPLEX

1. Estandarizando: Convertir las desigualdades en igualdades. Se introduce una variable de holgura por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales: 𝑴𝒂𝒙 𝑍 − 200𝑋1 − 300𝑋2 − 0𝑆1 − 0𝑆2 = 0 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 4𝑋1 + 4𝑋2 + 𝑺𝟏 3𝑋1 + 6𝑋2

= 36

+ 𝑺𝟐 = 48

𝑋𝑖 ≥ 0 𝑆𝑗 ≥ 0

Solución Básica Inicial

𝑖 = 1,2 𝑗 = 1,2

2. Escribir el problema en forma de Tabla. 𝑋𝐼 ≥ 0 Var. NO Básicas

𝑖 = 1,2

Var. De Decisión

Z S1 S2

Z 1 0 0

x1 -200 4 3

x2 -300 4 6

Var. Básicas

Var. De Holgura/Exceso

S1 0 1 0

S2 0 0 1

Sol. 0 36 48

49

3. Se escoge la Solución Básica Inicial (Sbi) y se empieza la iteración. Z 1 0 0

Z S1 S2

X1 X2 -200 -300 4 4 3 6

S1 0 1 0

S2 0 0 1

Sol. 0 36 48 Solución Básica Inicial

Base

4. Encontrar la variable No Básica que entra a la base y la Variable básica que sale de la base. ¿Cómo encontrar la Var. que entra y la que sale? *Elijo el más negativo en la fila de Z. En este caso es -300 entonces la Var. Entrada = X2 *Divido última columna entre columna pivote y elijo el menor cociente positivo. 36/4=9 y 48/6 = 8, el menor es 8, que corresponde a S2, entonces la Var. Salida = S2 *Mi elemento pivote es 6

1 iteración: (Llenar tabla) *El elemento pivote ahora debe ser UNO. El número 6 debe convertirse a 1 → divido toda la fila S2 entre 6. La fila X2 = Fila S2/6 *Los números restantes de la columna pivote deben ser Ceros. Vemos que para que 4 se haga 0, se le debe restar 4: Nuevo S1 = 4 + (-4)*1 =0 Aplico a toda la fila: Nuevo S1 = S1antiguo+ (-4)*X2 Y para la nueva fila de Z debemos sumar 300 parar que se haga cero: Nuevo z = -300 + (300)*1 = 0 Aplicando a toda la fila: Nuevo Z = Z antiguo + 300*X2 Y así completamos la tabla. Ahora vuelve a repetir el proceso, a elegir tu VE y tu VS. Hasta que la fila de Z sean ceros o positivos (Condición de Optimalidad).

Z 1 0 0

Z S1 S2

X1 X2 -200 -300 4 4 3 6

S1 0 1 0

S2 0 0 1

Sol. 0 36 48

+ negativo 36/4 =9 48/6 =8

VE=X2 VS=S2 Menor Cociente Positivo, no ceros ni negativos

Elemento pivote

En la base aparecen S1 y S2, pero la VE es X2 y la VS es S2, entonces en la base aparecerá X2 en lugar de S2. Esto ocasiona que el contenido de la tabla cambie y que cumpla con lo siguiente: El pivote ahora debe ser uno y los otros valores de la misma columna deben ser ceros, ¿Cómo? Veamos la tabla de la 1era iteración: Z 1 0 0

X1 -50 2 1/2

X2 0 0 1

S1 0 1 0

S2 50 -2/3 1/6

S1 antiguo+ (-4)*X2 Nuevo S1

4+ (-4)*1/2 2

4+ (-4)*1 0

1+ (-4)*0 1

0+ (-4)*1/6 -2/3

36+ (-4)*8 4

Z antiguo+ 300*X2 Nuevo Z

-200+ 300*1/2 -50

-300+ 300*1 0

0+ 300*0 0

0+ 300*1/6 50

0+ 300*8 2400

1 iter.

S1 X2

Sol. 2400 4 8

+ negativo 4/2 =2

VE=X2 VS=S2

8/1/2 =16

Ya completa la tabla, verificamos que la fila de Z aun no es positiva o cero, entonces seguimos iterando, definimos el elemento pivote = 2, mi Var. Entrada =X1, Var. Salida = S1 y elaboramos la siguiente tabla que corresponde a la 2da iteración:

Condición de Optimalidad para el problema de maximización: El Proceso termina cuando todos los coeficientes de las variables NO básicas son cero o positivos. Zj – Cj ≥ 0

2 iter.

X1 X2

Z 1 0 0

X1 0 1 0

X2 0 0 1

S1 25 1/2 -1/4

S2 -50/3 -1/3 1/3

Sol. 2500 2 7

Solución Básica Factible Óptima

Z*=2500 X1=2 X2=7 S1=0 S2=0

La solución óptima es Z* = 2500 ya que Z* = 200(2)+ 300 (7) = 2500

] = [27], 𝑋𝑁 = [S1 ] = [00] 𝑋𝐵 = [X1 X2 S2

50

La solución óptima es: 2500. En la misma columna se puede observar el vértice donde se alcanza, observando las filas correspondientes a las variables de decisión que han entrado a la base: (X1, X2) = (2,7). El carpintero debe producir 2 sillas y 7 mesas por semana para tener un beneficio máximo de s/ 2500

GRÁFICO

A

B

C

Z*=2500 X1=2 X2=7 S1=0 S2=0

Z*=2400 X1=0 X2=8 S1=4 S2=0

2DA ITERACIÓN

1ERA ITERACIÓN

𝑴𝒂𝒙 𝑍 = 200𝑋1 + 300𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 4𝑋1 + 4𝑋2 ≤ 36 …L1 3𝑋1 + 6𝑋2 ≤ 48 … L2 𝑋𝑖 ≥ 0

𝑖 = 1,2

El valor máximo de la función objetivo es 2500, y corresponde a x1 = 2 y x2 = 7 (vértice C).

REGIÓN FACTIBLE

En este gráfico vemos como, el método simplex, salta de punto a punto hasta encontrar la sol. Óptima.

Z*=0 X1=0 X2=0 S1=36 S2=48

Z*=1800 X1=0 X2=9

Simplex en un PPL de Maximizar: ¿Por qué hacemos cada proceso? Y recordemos como lo hicimos. Por la Condición de Optimalidad: Para escoger la variable No básica que entra en la base, nos fijamos en los coeficientes de las variables No básicas en la función objetivo y escogemos la variable con el coeficiente más negativo. Lo que va a determinar el final del proceso de aplicación del método del simplex es que los coeficientes de las variables No básicas en la función objetivo sean ceros o positivos.

Por la Condición de factibilidad: Para encontrar la variable básica que tiene que salir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero. Si hubiese algún elemento menor o igual que cero no se hace dicho cociente. En el caso de que todos los elementos fuesen menores o iguales a cero, entonces tendríamos una solución no acotada y no se puede seguir. El término de la columna pivote que en la división dé lugar al menor cociente positivo, indica la fila de la variable básica que sale de la base. Si al calcular los cocientes, dos o más son iguales, indica que cualquiera de las variables correspondientes puede salir de la base, es arbitrario.

51

Veamos ahora un PPL de Minimización:

EJEMPLO

Tenemos el PPL: Forma Estándar:

Forma Canónica:

𝑴𝒊𝒏 𝑍 − 𝑋1 + 2𝑋2 − 0𝑆1 − 0𝑆2 = 0

𝑴𝒊𝒏 𝑍 = 𝑋1 − 2𝑋2

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

−𝑋1 + 𝑋2 + 𝑺𝟏 =2 𝑋1 + 𝑋2 + 𝑺𝟐 = 5

−𝑋1 + 𝑋2 ≤ 2 𝑋1 + 𝑋2 ≤ 5 𝑋𝑖 ≥ 0

𝑋𝑖 ≥ 0 𝑆𝑗 ≥ 0

𝑖 = 1,2

𝑖 = 1,2 𝑗 = 1,2

Aplicamos Simplex: Z 1 0 0 1 0 0 1 0 0

Z S1 S2 Z X2 S2 Z X2 X1

X2 ←S1 S2 ←S2 antiguo+ (-1)*X2 Z ←Z antiguo+ (-2)*X2

X1 ←S2/2 X2 ←X2 antiguo+ (1)*X1 Z ←Z antiguo+ (-1)*X1

X1 -1 -1 1 1 -1 2 0 0 1

X2 2 1 1 0 1 0 0 1 0

S1 0 1 0 -2 1 -1 -1.5 0.5 -0.5

S2 0 0 1 0 0 1 -0.5 0.5 0.5

Sol. 0 2 5 -4 2 4 -5.5 3.5 1.5

+ positivo 2/1 =2

VE=X2 VS=S1

5/1 =5 + positivo

VE=X1 VS=S2

2/-1 =-2 4/2 =2

Condición de Optimalidad para el problema de minimización: El Proceso termina cuando todos los coeficientes de las variables NO básicas son cero o negativos. Zj – Cj ≤ 0

La solución óptima es Z* = -5.5 ya que Z* = 1.5 - 2 (3.5) = -5.5

] = [1.5 ], 𝑋𝑁 = [S1 ] = [00] 𝑋𝐵 = [X1 X2 3.5 S2

GRÁFICO 2DA ITERACIÓN

A

B

P

Z*=-4 X1=0 X2=2 S1=0 S2=4 1ERA ITERACIÓN

REGIÓN FACTIBLE

Z*=-5.5 X1=1.5 X2=3.5 S1=0 S2=0

𝑴𝒊𝒏 𝑍 = 𝑋1 − 2𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 −𝑋1 + 𝑋2 ≤ 2 …L1 𝑋1 + 𝑋2 ≤ 5 … L2 𝑋𝑖 ≥ 0

𝑖 = 1,2

El valor mínimo de la función objetivo es -5,5, y corresponde a X1 = 1,5 y X2 = 3,5 (vértice P).

Z*=0 X1=0 X2=0 S1=2 S2=5

52

En términos generales, en un PPL de Maximizar o Minimizar sucede: Condición de Optimalidad  Problema de Maximización: * La variable entrante es seleccionada como la variable NO básica que tiene el coeficiente más negativo en la ecuación de la función objetivo. * El Proceso termina cuando todos los coeficientes de las variables NO básicas son cero o positivos.  Problema de Minimización: * La variable NO básica que entra a la base es la que tiene el coeficiente más positivo en la ecuación de la función objetivo. * El proceso termina cuando todos los coeficientes son negativos o cero.

Condición de Factibilidad  Se verifica en las restricciones.  El objetivo es encontrar la variable básica que saldrá de la base.  La variable que sale de la base es la variable básica correspondiente al más pequeño cociente positivo obtenido de dividir los valores de la solución y los coeficientes positivos de la restricción de la variable entrante, tanto en PPL de Max. y Min.

4.4

Casos en la resolución de un PL Solución Única

Alguno de los costos reducidos de las variables no básicas es igual a cero

Soluciones alternativas

Solución No Acotada Se reconoce porque alguna variable artificial queda en la base en la tabla final.

Los costos reducidos de las variables no básicas son estrictamente negativos (maximización) o estrictamente positivos (minimización).

Si al efectuar el test de salida de la base, todos los coeficientes de la columna correspondiente a la variable entrante son no positivos.

Solución Infactible

53

4.5

Ejemplos 1

Tenemos el PPL: Forma Estándar:

Forma Canónica:

𝑴𝒂𝒙 𝑍 − 3𝑋1 − 2𝑋2 − 5𝑋3 + 0𝑆1 + 0𝑆2 + 0𝑆3 = 0

𝑴𝒂𝒙 𝑍 = 3𝑋1 + 2𝑋2 + 5𝑋3

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑋1 + 2𝑋2 + 𝑋3 + 𝑺𝟏 = 430 3𝑋1 + 2𝑋3 + 𝑺𝟐 = 460 𝑋1 + 4𝑋2 + 𝑺𝟑 = 420

𝑋1 + 2𝑋2 + 𝑋3 ≤ 430 3𝑋1 + 2𝑋3 ≤ 460 𝑋1 + 4𝑋2 ≤ 420 𝑋𝑖 ≥ 0

𝑋𝑖 ≥ 0 𝑆𝑗 ≥ 0

𝑖 = 1,2,3

𝑖 = 1,2,3 𝑗 = 1,2,3

Aplicamos Simplex: Z 1 0 0 0 1 0 0 0 1 0 0 0

Z S1 S2 S3 1ERA ITER.

S1 X3 S3 Condición de Optimalidad para el problema de maximización: El Proceso termina cuando todos los coeficientes de las variables NO básicas son cero o positivos. Zj – Cj ≥ 0

2DA ITER.

X2 X3 S3

X1 -3 1 3 1 4.5 -0.5 1.5 1 4 -0.25 1.5 2

X2 -2 2 0 4 -2 2 0 4 0 1 0 0

X3 -5 1 2 0 0 0 1 0 0 0 1 0

S1 0 1 0 0 0 1 0 0 1 0.5 0 -2

S2 0 0 1 0 2.5 -0.5 0.5 0 2 -0.25 0.5 1

S3 0 0 0 1 0 0 0 1 0 0 0 1

Sol. 0 430 460 420 1150 200 230 420 1350 100 230 20

+ negativo 430/1 =430

VE=X3 VS=S2

460/2 =230 420/0 =∄ + negativo 200/2 =100

VE=X2 VS=S1

230/0 =∄ 420/4 =105

La solución óptima es Z* = 1350 ya que Z* = 3(0) + 2 (100) + 5(230)= 1350 X2

100

X1

0

𝑆1 ] = [0] 𝑋𝐵 = [X3] = [230 ], 𝑋𝑁 = [S2 20 0 S3

2

Tenemos el PPL: Forma Estándar:

Forma Canónica:

𝑴𝒂𝒙 𝑍 = 𝑋1 + 2𝑋2

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 −2𝑋1 + 𝑋2 ≤ 7 𝑋1 − 𝑋2 ≤ 2 𝑋𝑖 ≥ 0

𝑴𝒂𝒙 𝑍 − 𝑋1 − 2𝑋2 − 0𝑆1 − 0𝑆2 = 0

𝑖 = 1,2

−2𝑋1 + 𝑋2 + 𝑺𝟏 =7 𝑋1 − 𝑋2 + 𝑺𝟐 = 2 𝑋𝑖 ≥ 0 𝑆𝑗 ≥ 0

𝑖 = 1,2 𝑗 = 1,2

54

Aplicamos simplex:

Z S1 S2 1ERA ITER.

X2 ←S1 S2 ←S2 antiguo+ X2 Z ←Z antiguo+ (2)*X2

X2 S2

Z 1 0 0 1 0 0

X1 -1 -2 1 -5 -2 -1

X2 -2 1 -1 0 1 0

S1 0 1 0 2 1 1

S2 0 0 1 0 0 1

Sol. 0 7 2 14 7 9

+ negativo

VE=X2 VS=S1

7/1 =7 2/-1 =-2 + negativo 7/-2=-7/2 9/-1 =-9

Solución INFINITA NO ACOTADA porque la columna pivote tiene elementos NO positivos.

La solución óptima es infinita con Región Factible NO ACOTADA

GRÁFICO

Z*=14 X1=0 X2=7 S1=0 S2=9

𝑴𝒂𝒙 𝑍 = 𝑋1 + 2𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 −2𝑋1 + 𝑋2 ≤ 7 …L1 𝑋1 − 𝑋2 ≤ 2 … L2 𝑋𝑖 ≥ 0

REGIÓN FACTIBLE

1ERA ITERACIÓN

𝑖 = 1,2

El valor máximo de la función objetivo es infinito. Z*=0 X1=0 X2=0 S1=7 S2=2

3

Tenemos el PPL: Forma Estándar:

Forma Canónica:

𝑴𝒂𝒙 𝑍 − 15𝑋1 − 30𝑋2 − 0𝑆1 − 0𝑆2 = 0

𝑴𝒂𝒙 𝑍 = 15𝑋1 + 30𝑋2

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

4𝑋1 + 𝑋2 + 𝑺𝟏 = 36 𝑋1 + 2𝑋2 + 𝑺𝟐 = 30

4𝑋1 + 𝑋2 ≤ 36 𝑋1 + 2𝑋2 ≤ 30 𝑋𝑖 ≥ 0

𝑋𝑖 ≥ 0 𝑆𝑗 ≥ 0

𝑖 = 1,2

𝑖 = 1,2 𝑗 = 1,2

Aplicamos Simplex:

Z S1 S2 X2 ←S2/2 S1 ←S1 antiguo+ (-1) X2 Z ←Z antiguo+ (30)*X2

1ERA ITER.

S1 X2

Z 1 0 0 1 0 0

X1 -15 4 1 0 7/2 1/2

X2 -30 1 2 0 0 1

S1 0 1 0 0 1 0

S2 0 0 1 15 -1/2 1/2

Sol. 0 36 30 450 21 15

Soluciones alternativas porque Costo Reducido de una VNB =0

+ negativo 36/1 =36

VE=X2 VS=S2

30/2 =15

Condición de Optimalidad para el problema de maximización: El Proceso termina cuando todos los coeficientes de las variables NO básicas son cero o positivos. Zj – Cj ≥ 0

55

Una solución alternativa la hallaríamos eligiendo la Variable de Entrada = X1, veamos la 2da iteración:

1ERA ITER.

S1 X2 2DA ITER.

X1 ←S1*2/7 X2 ←X2 antiguo+ (-1/2) X1 Z ←Z antiguo

X1 X2

Z 1 0 0 1 0 0

X1 0 7/2 1/2 0 1 0

X2 0 0 1 0 0 1

S1 0 1 0 0 2/7 -1/7

S2 15 -1/2 1/2 15 -1/7 4/7

Sol. 450 21 15 450 6 12

+ negativo

VE=X1 VS=S1

21/7/2 =6 15/1/2 =30

Otra solución óptima

La solución óptima es Z* = 450 y presenta infinitas soluciones alternativas. Uno de los puntos óptimos alternativos es: Z* = 15(0) + 30 (15) = 450 Otro punto óptimo alternativo es el resultado de la 2DA ITERACIÓN.

0 ] = [15 ], 𝑋𝑁 = [S1 ] = [21 ] 𝑋𝐵 = [X1 X2 S2 0

GRÁFICO Z*=450 X1=0 X2=15 S1=21 S2=0

2DA ITERACIÓN

1ERA ITERACIÓN

𝑴𝒂𝒙 𝑍 = 15𝑋1 + 30𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 4𝑋1 + 𝑋2 ≤ 36 …L1 𝑋1 + 2𝑋2 ≤ 30 … L2 𝑋𝑖 ≥ 0

Z*=450 X1=6 X2=12 S1=0 S2=0

La recta BC representa todos los puntos óptimos infinitos alternativos para Z*=450 Cuando una restricción es paralela a la F.O. es probable que suceda → L2//F.O.

Z*=0 X1=0 X2=0 S1=36 S2=30

4

𝑖 = 1,2

Tenemos el PPL: Forma Estándar:

Forma Canónica:

𝑴𝒂𝒙 𝑍 = 6𝑋1 − 2𝑋2

𝑴𝒂𝒙 𝑍 − 6𝑋1 + 2𝑋2 − 0𝑆1 − 0𝑆2 = 0 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 − 𝑋2 ≤ 1 3𝑋1 − 𝑋2 ≤ 6 𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑋1 − 𝑋2 + 𝑺𝟏 =1 3𝑋1 − 𝑋2 + 𝑺𝟐 = 6 𝑋𝑖 ≥ 0 𝑆𝑗 ≥ 0

𝑖 = 1,2 𝑗 = 1,2

56

Aplicamos Simplex: Z 1 0 0 1 0 0 1 0 0

Z S1 S2 1ERA ITER.

X1 ←S1 S2 ←S2 antiguo+ (-3) X1 Z ←Z antiguo+ (6)*X1

X1 S2 2DA ITER.

X2 ←S2/2 X1 ←X1 antiguo+ X2 Z ←Z antiguo+ (4)*X2

X1 X2

X1 -6 1 3 0 1 0 0 1 0

X2 2 -1 -1 -4 -1 2 0 0 1

S1 0 1 0 6 1 -3 0 -1/2 -3/2

S2 0 0 1 0 0 1 2 1/2 1/2

Sol. 0 1 6 6 1 3 12 5/2 3/2

La solución óptima es Z* = 12 ya que: Z* = 6(5/2) – 2(3/2) = 12

𝑋𝐵 =

5

[X1 ] X2

+ negativo

VE=X1 VS=S1

1/1 =1 6/3 =2 + negativo 1/-1 =-1

VE=X2 VS=S2

3/2 =1.5

Condición de Optimalidad para el problema de maximización: El Proceso termina cuando todos los coeficientes de las variables NO básicas son cero o positivos. Zj – Cj ≥ 0

5 2 3 2

] = [00] = [ ], 𝑋𝑁 = [S1 S2

Tenemos el PPL: Forma Estándar:

Forma Canónica:

𝑴𝒂𝒙 𝑍 − 6𝑋1 + 𝑋2 − 0𝑆1 − 0𝑆2 = 0

𝑴𝒂𝒙 𝑍 = 6𝑋1 − 𝑋2

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

2𝑋1 − 𝑋2 + 𝑺𝟏 =2 𝑋1 + 𝑺𝟐 = 3

2𝑋1 − 𝑋2 ≤ 2 𝑋1 ≤ 3 𝑋𝑖 ≥ 0

𝑋𝑖 ≥ 0 𝑆𝑗 ≥ 0

𝑖 = 1,2

𝑖 = 1,2 𝑗 = 1,2

Aplicamos Simplex:

Z S1 S2 X1 ←S1 S2 ←S2 antiguo+ (-2) X1 Z ←Z antiguo+ (6)*X1

X2 ←S2*2 X1 ←X1 antiguo+ (1/2) X2 Z ←Z antiguo+ (2)*X2

1ERA ITER.

X1 S2 2DA ITER.

X1 X2

Z 1 0 0 1 0 0 1 0 0

X1 -6 2 1 0 1 0 0 1 0

X2 1 -1 0 -2 -1/2 1/2 0 0 1

S1 0 1 0 3 1/2 -1/2 1 0 -1

S2 0 0 1 0 0 1 4 1 2

Sol. 0 2 3 6 1 2 14 3 4

La solución óptima es Z* = 14 ya que: Z* = 6(3) – 1(4) = 14

+ negativo 2/2 =1

VE=X1 VS=S1

3/1 =3 + negativo 1/-1/2 =-2

VE=X2 VS=S2

2/1/2 =4

Condición de Optimalidad para el problema de maximización: El Proceso termina cuando todos los coeficientes de las variables NO básicas son cero o positivos. Zj – Cj ≥ 0

] = [34], 𝑋𝑁 = [S1 ] = [00] 𝑋𝐵 = [X1 X2 S2

57

4.6

Ejercicios 𝑴𝒊𝒏 𝑍 = 6𝑋1 + 3𝑋2 + 4𝑋3

𝑴𝒂𝒙 𝑍 = 2𝑋1 − 4𝑋2 + 5𝑋3 − 6𝑋4

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑋1 + 6𝑋2 + 𝑋3 = 10 2𝑋1 + 3𝑋2 ≤ 15

𝑋1 + 4𝑋2 − 2𝑋3 + 8𝑋4 ≤ 2 −1𝑋1 + 2𝑋2 + 3𝑋3 + 4𝑋4 ≤ 1 𝑋𝑖 ≥ 0

𝑋𝑖 ≥ 0

𝑖 = 1,2,3,4

𝑴𝒂𝒙 𝑍 = 2𝑋1 + 7𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑴𝒂𝒙 𝑍 = 10𝑋1 + 11𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

3𝑋1 + 4𝑋2 ≤ 12 𝑋1 + 8𝑋2 ≤ 8 6𝑋1 + 𝑋2 ≤ 15

𝑖 = 1,2,3

𝑴𝒊𝒏 𝑍 = 2𝑋1 − 3𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑋1 + 2𝑋2 ≤ 150 3𝑋1 + 4𝑋2 ≤ 200 6𝑋1 + 𝑋2 ≤ 175

𝑋1 + 𝑋2 ≤ 4 𝑋1 − 𝑋2 ≤ 6 𝑋𝑖 ≥ 0

𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑴𝒂𝒙 𝑍 = −3𝑋1 + 6𝑋2

5𝑋1 + 7𝑋2 ≤ 35 −𝑋1 + 2𝑋2 ≤ 2 𝑖 = 1,2

𝑴𝒊𝒏 𝑍 = −𝑋1 − 11𝑋2

𝑴𝒂𝒙 𝑍 = 𝑋1 + 9𝑋2 + 𝑋3

𝑖 = 1,2

𝑴𝒊𝒏 𝑍 = 80𝑋1 + 60𝑋2

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑋1 + 2𝑋2 + 3𝑋3 ≤ 9 3𝑋1 + 2𝑋2 + 2𝑋3 ≤ 15

0.20𝑋1 + 0.32𝑋2 ≤ 0.25 𝑋1 + 𝑋2 = 1

𝑋𝑖 ≥ 0

𝑖 = 1,2,3

𝑴𝒂𝒙 𝑍 = 𝑋1 + 𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 5𝑋1 + 3𝑋2 ≤ 15 3𝑋1 + 5𝑋2 ≤ 15 𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑴𝒊𝒏 𝑍 = 6𝑋1 + 4𝑋2 + 2𝑋3 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 6𝑋1 + 2𝑋2 + 6𝑋3 ≤ 6 6𝑋1 + 4𝑋2 = 12 2𝑋1 − 2𝑋2 ≤2 𝑋𝑖 ≥ 0

𝑴𝒊𝒏 𝑍 = −3𝑋1 + 8𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑋1 − 𝑋2 ≤ 1 𝑋1 + 𝑋2 ≤ 2 𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑖 = 1,2

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑋𝑖 ≥ 0

𝑋𝑖 ≥ 0

𝑖 = 1,2,3

4𝑋1 + 2𝑋2 ≤ 12 2𝑋1 + 3𝑋2 ≤ 6 𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑴𝒂𝒙 𝑍 = 3𝑋1 + 2𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 𝑋2 ≤ 18 2𝑋1 + 3𝑋2 ≤ 42 3𝑋1 + 𝑋2 ≤ 24 𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑴𝒂𝒙 𝑍 = 𝑋1 + 2𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 3𝑋2 ≤ 18 𝑋1 + 𝑋2 ≤ 8 2𝑋1 + 𝑋2 ≤ 14 𝑋𝑖 ≥ 0

𝑖 = 1,2

58

MÉTODO DE VARIABLES ARTIFICIALES

5.1

Idea conceptual Sabemos que el simplex inicia cuando se tiene una solución factible y las restricciones son ≤. Además, una solución factible ocurre en el origen de coordenadas. ¿Qué sucede cuando el origen no es solución factible? Cuando las restricciones son “≥”, “=” y/o bi=) ó (=), estas variables Ri se llaman variables artificiales. 3. Los costos asociados (coeficientes de Ri))a estas variables serán –M para problemas de Maximización y +M para problemas de Minimización. (En F.O.) 4. Se usa las variables artificiales para la solución básica inicial y se procede a aplicar el simplex hasta obtener la solución óptima.

EJEMPLO

Tenemos el PPL Maximización:

③ Forma Estándar:

Forma Canónica:

𝑴𝒂𝒙 𝑍 = 3𝑋1 + 2𝑋2 + 0𝑆1 + 0𝑆2 − 𝑀𝑅1 − 𝑀𝑅2 𝑑𝑒𝑠𝑝𝑒𝑗𝑜: 𝑍 − 3𝑋1 − 2𝑋2 − 0𝑆1 − 0𝑆2 + 𝑀𝑅1 + 𝑀𝑅2 = 0 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑴𝒂𝒙 𝑍 = 3𝑋1 + 2𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 𝑋2 ≤ 6 2𝑋1 − 𝑋2 ≥ 0 𝑋1 = 2 𝑋𝑖 ≥ 0

𝑋1 + 𝑋2 + 𝑺𝟏 =6 2𝑋1 − 𝑋2 − 𝑺𝟐 + 𝑹𝟏 =0 𝑋1 + 𝑹𝟐 = 2

𝑖 = 1,2

①

Para que M sea 0: Z ←R1*(-M)+R2*(-M)+Z

SIMPLEX

④

X1 ←R1/2 S1 ←S1 antiguo+ (-1)*X1 R2 ←R2 antiguo+ (-1)*X1 Z ←Z antiguo+ (3M+3)*X1

X2 ←R2*2 X1 ←X1 antiguo+ (1/2)*X2 S1 ←S1 antiguo+ (-3/2)*X2 Z ←Z antiguo+ (M/2+7/2)*X2

Z S1 R1 R2 1ERA ITER.

S1 R1 R2 2DA ITER.

S1 X1 R2 3CERA ITER.

S1 X1 X2

Z 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0

X1 -3 1 2 1

𝑋1 , 𝑋2 , 𝑆1 , 𝑆2 , 𝑅1 , 𝑅2 ≥ 0

Agregar variables de holgura (≤) o exceso (≥) donde corresponda.

Plasmamos el Problema en una tabla: ¿Qué variables colocamos aquí? Las variables que conforman una matriz identidad.

Coeficiente de Ri será –M por ser PPL Max.

X2 -2 1 -1 0

S1 0 1 0 0 -3M-3 M-2 0 1 1 1 -1 2 0 1 0 0 0 -M/2-7/2 0 0 3/2 1 1 -1/2 0 0 1/2 0 0 0 0 0 0 1 1 0 0 0 1 0

S2 0 0 -1 0 M 0 -1 0

②

Para aplicar simplex, M deberá convertirse a 0, ya que S1, R1 y R2 deben vectores unitarios.

R1 M 0 1 0 0 0 1 0 -1/2 ½ -1/2

R2 M 0 0 1 0 0 0 1 0 0 0 1

M-2

M+7

1 0 -1

-3 1 2

-M/2-3/2 3M/2+3/2

½ -1/2 1/2 2 -1 0 1

Agregar variables artificiales (Ri) en restricciones de ≥ o =

Sol. 0 6 1 2 -2M 6 1 2 -2M 6 1 2 14 0 2 4

+ negativo 6/1 =6

VE=X1 VS=R1

½=0.5 2/1=2 + negativo 6/3/2 =4

VE=X2 VS=R2

1/-½=-2 2/½=2

Verifico que Zj – Cj ≥ 0 y paramos.

La solución óptima es Z* = 14 ya que Z* = 3(2) + 2(4) = 14 S1

0

S2

0

𝑋𝐵 = [X1 ] = [24], 𝑋𝑁 = [R1 ] = [00] X2 R2

61

Tenemos el PPL Minimización:

EJEMPLO

③ Forma Estándar:

Forma Canónica:

𝑴𝒊𝒏 𝑍 = −𝑋1 + 𝑋2 + 0𝑆1 + 0𝑆2 + 𝑀𝑅1 𝑑𝑒𝑠𝑝𝑒𝑗𝑜: 𝑍 + 𝑋1 − 𝑋2 − 0𝑆1 − 0𝑆2 − 𝑀𝑅1 = 0 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑴𝒊𝒏 𝑍 = 𝑋2 − 𝑋1 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 − 𝑋2 ≤ 1 −𝑋1 + 𝑋2 ≥ 1 𝑋𝑖 ≥ 0

Coeficiente de Ri será +M por ser PPL Min.

𝑋1 − 𝑋2 + 𝑺𝟏 =6 −𝑋1 + 𝑋2 − 𝑺𝟐 + 𝑹𝟏 = 0

𝑖 = 1,2

𝑋1 , 𝑋2 , 𝑆1 , 𝑆2 , 𝑅1 ≥ 0

①

Agregar variables de holgura (≤) o exceso (≥) donde corresponda.

Plasmamos el Problema en una tabla:

Agregar variables artificiales (Ri) en restricciones de ≥ o =

②

Para aplicar simplex, M deberá convertirse a 0, ya que S1 y R1 deben vectores unitarios.

¿Qué variables colocamos aquí? Las variables que conforman una matriz identidad. Para que M sea 0: Z ←R1*(M)+Z

SIMPLEX

+ positivo

④

1/-1 =-1

VE=X2 VS=R1

1/1=1

X2 ←R1 S1 ←S1 antiguo+ X2 Z ←Z antiguo+ (1+M)*X2

Verifico que Zj – Cj ≤ 0 y paramos.

La solución óptima es Z* = 1 ya que Z* = 1 - 0 = 1 S1 ] = [21], 𝑋𝑁 = [X1 ] = [00] 𝑋𝐵 = [X2 S2

GRÁFICO

REGIÓN FACTIBLE

𝑴𝒊𝒏 𝑍 = 𝑋2 − 𝑋1 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 − 𝑋2 ≤ 1 …L1 −𝑋1 + 𝑋2 ≥ 1 … L2 𝑋𝑖 ≥ 0

𝑖 = 1,2

El valor mínimo de la función objetivo es 1, y corresponde a x1 = 0 y x2 = 1 El problema presenta Solución Óptima con Región Factible No acotada.

62

En resumen, el método de la M consiste en:

Estandarizo (Agrego Variables)

Plasmar el PL en la tabla

Convertir a Vector Unitario

Agrego Var. Artificial si Identificar las variables la restricción es tipo ≥ o que van a la base. =. Agregar variables de Buscar la matriz exceso (≥) o de holgura identidad. (≤) y agregar el coef. M (Max) o +M (Min) a los Ri en la F.O.

5.4

Aplicar Simplex

Las variables que están en la base deben ser vectores unitarios antes de aplicar simplex.

Ejercicios 𝑴𝒂𝒙 𝑍 = 3𝑋1 + 𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 𝑋2 ≥ 3 2𝑋1 + 𝑋2 ≤ 4 𝑋1 + 𝑋2 = 3 𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑴𝒊𝒏 𝑍 = 0,4𝑋1 + 0,5𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 0,6𝑋1 + 0,4𝑋2 ≥ 6 0,3𝑋1 + 0,1𝑋2 ≤ 2.7 0,5𝑋1 + 0,5𝑋2 = 6 𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑴𝒊𝒏 𝑍 = 4𝑋1 + 4𝑋2 + 𝑋3 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 𝑋2 + 𝑋3 ≥ 2 2𝑋1 + 𝑋2 ≤3 2𝑋1 + 𝑋2 + 3𝑋3 ≥ 3 𝑋𝑖 ≥ 0

𝑖 = 1,2,3

𝑴𝒂𝒙 𝑍 = 3𝑋1 + 5𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1

≤4 2𝑋2 ≤ 12 3𝑋1 + 2𝑋2 = 18 𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑴𝒂𝒙 𝑍 = 2𝑋1 + 3𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 𝑋2 ≥ 4 2𝑋1 + 𝑋2 ≥ −1 𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑴𝒊𝒏 𝑍 = 4𝑋1 + 𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 3𝑋1 + 𝑋2 = 3 4𝑋1 + 3𝑋2 ≥ 6 𝑋1 + 2𝑋2 ≤ 4 𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑴𝒂𝒙 𝑍 = 3𝑋1 + 8𝑋2

𝑴𝒂𝒙 𝑍 = −8𝑋1 + 3𝑋2 − 6𝑋3

𝑴𝒂𝒙 𝑍 = 6𝑋1 + 3𝑋2 − 4𝑋3

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 4𝑋2 ≤ 4 𝑋1 + 2𝑋2 ≥ 2

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 3𝑋2 + 5𝑋3 = 4 5𝑋1 + 3𝑋2 − 4𝑋3 ≥ 6

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 6𝑋2 + 𝑋3 = 10 2𝑋1 + 3𝑋2 ≤ 15

𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑋𝑖 ≥ 0

𝑖 = 1,2,3

𝑋𝑖 ≥ 0

𝑖 = 1,2,3

63

5.5

Método de Dos Fases

La desventaja del método M es el posible error de cómputo que podría resultar de asignar un valor muy grande a la constante M. Esta situación podría presentar errores de redondeo en las operaciones de la computadora digital. Para evitar esta dificultad el problema se puede resolver aplicando el método de las 2 fases, que como menciona su nombre, se resuelve en dos fases:

1ERA FASE

PLL ORIGINAL 𝑴𝒂𝒙 𝑍 = 𝐶𝑥 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 ≤ 𝐴𝑥 = 𝑏 ≥

2DA FASE 𝑭. 𝑶. 𝑶𝒓𝒊𝒈𝒊𝒏𝒂𝒍 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑴𝒊𝒏 𝑍 = ∑ 𝑅𝑖 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑥≥0 Ó

𝑆𝑂𝐿𝑈𝐶𝐼Ó𝑁 1𝐸𝑅𝐴 𝐹𝐴𝑆𝐸 sin 𝑐𝑜𝑛𝑠𝑖𝑑𝑒𝑟𝑎𝑟 𝑉𝐴

𝐴𝑥 + 𝑆𝑖 + 𝑅𝑖 = 𝑏

𝑴𝒊𝒏 𝑍 = 𝐶𝑥 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 ≤ 𝐴𝑥 = 𝑏 ≥

𝑥≥0 Consiste en Minimizar las F.O. formada por la suma de las variables artificiales (el resto tiene coeficientes =0). Esta fase termina si todas las Var. Artificiales (VA) salen de la base y Z*=0.

𝑥≥0

Consiste en resolver utilizando como base inicial la obtenida en la 1era Fase sin considerar las columnas de las Variables Artificiales. La Solución óptima de a 2da Fase es la solución óptima del Problema original.

SOLUCIÓN ÓPTIMA 1ERA FASE ∃ Ri ≠0

∀ Ri =0

Z*>0

Z*=0

V.A. no salen de la Base. No hay Solución Factible para el PPL Original.

V.A. no salen de la Base. Hay Solución Básica Degenerada. Debe entre una Xj. El valor de la F.O. no cambiará

V.A. si salen de la Base. Si hay Solución Factible para el PPL Original. Servirá de base la 2da Fase.

Termina 1ERA FASE.



OBJETIVO

PRIMERA FASE

SEGUNDA FASE

MAXIMIZAR

MINIMIZAR

MAXIMIZAR

MINIMIZAR

MINIMIZAR

MINIMIZAR

64

Tenemos el PPL Maximización:

EJEMPLO

Forma Canónica:

𝑴𝒂𝒙 𝑍 = 3𝑋1 + 2𝑋2 +4𝑋3 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 3𝑋1 + 3𝑋2 +5𝑋3 ≤ 120 2𝑋1 + 𝑋2 +3𝑋3 = 60 𝑋𝑖 ≥ 0

1ERA FASE

𝑖 = 1,2,3

Formulo el problema para aplicar la 1era Fase. 1ERA FASE: Minimizar Var. Artificiales

𝑴𝒊𝒏 𝑍 = 0𝑋1 + 0𝑋2 +0𝑋3 + 0𝑆1 + 1𝑹𝟏 𝑑𝑒𝑠𝑝𝑒𝑗𝑜: 𝑍−0𝑋1 − 0𝑋2 −0𝑋3 − 0𝑆1 − 1𝑹𝟏 = 0 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

El coeficiente de Ri será 1 y del resto será 0

3𝑋1 + 3𝑋2 +5𝑋3 + 𝑺𝟏 = 120 2𝑋1 + 𝑋2 +3𝑋3 + 𝑹𝟏 = 60 𝑋1 , 𝑋2 , 𝑆1 , 𝑅1 ≥ 0

Plasmamos el Problema en una tabla: Para aplicar simplex, S1 y R1 deben vectores unitarios. ¿Qué variables colocamos aquí? Las variables que conforman una matriz identidad. Para que R1 sea Vector Unitario: Z ←R1+Z

SIMPLEX

Z S1 R1 Z S1 R1 1ERA ITER.

X3 ←R1 /3 S1 ←S1 antiguo+ X3*(-5) Z ←Z antiguo+ X3*(-3)

S1 X3

Se eliminaron las Variables Artificiales de la base

Z 1 0 0 1 0 0 1 0 0

X1 0 3 2 2 3 2 0 -1/3 2/3

X2 0 3 1 1 3 8 -7 -31/3 8/3

X3 0 5 3 3 5 3 0 0 1

S1 0 1 0 0 1 0 0 1 0

R1 -1 0 1 0 0 1 -1 -5/3 1/3

Sol. 0 120 60 60 120 60 0 20 20

+ positivo

VE=X3 VS=R1

120/5 =60 60/3=20

Z*= 0

Verifico que Zj – Cj ≤ 0 y paramos.

FIN 1ERA FASE

65

2DA FASE

Formulo el problema para aplicar la 2da Fase. Forma Canónica:

𝑴𝒂𝒙 𝑍 = 3𝑋1 + 2𝑋2 +4𝑋3 +0𝑆1 𝑑𝑒𝑠𝑝𝑒𝑗𝑜 𝑍−3𝑋1 − 2𝑋2 −4𝑋3 −0𝑆1 = 0

Usando el resultado de la 1era Fase, sin considerar la columna de la Variable artificiales y considerando la F.O. del problema original. Para aplicar simplex, S1 y X3 deben vectores unitarios.

Para que X3 sea Vector Unitario: X3 ←X3*4+Z

SIMPLEX X1 ←X3*(3/2) S1 ←S1 antiguo + X1*(1/3) Z ←Z antiguo + X1*(1/3)

Z S1 X3 Z S1 X3 1ERA ITER.

S1 X1

Z 1 0 0 1 0 0 1 0 0

X1 -3 -1/3 2/3 -1/3 -1/3 2/3 0 0 1

X2 -2 -31/3 8/3 26/3 -31/3 8/3 10 -9 4

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

S1 0 1 0 0 1 0 0 1 0

La solución óptima es Z* = 90 ya que Z* = 3(30) + 2(0) +4(0) = 90 X1

Sol. 0 20 20 80 20 20 90 30 30

+ negativo

VE=X1 VS=X1

120/5 =60 60/3=20

Verifico que Zj – Cj ≥0 y paramos.

FIN 2DA FASE

30

S1 ] = [00] 𝑋𝐵 = [X2 ] = [ 00 ], 𝑋𝑁 = [R1 X3

EJEMPLO

Tenemos el PPL Minimización: Forma Canónica:

𝑴𝒊𝒏 𝑍 = 2000𝑋1 + 500𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 3𝑋2 ≥ 36 3𝑋1 + 6𝑋2 ≥ 60 𝑋𝑖 ≥ 0

𝑖 = 1,2

66

1ERA FASE

Formulo el problema para aplicar la 1era Fase.

1ERA FASE: Minimizar Var. Artificiales

𝑴𝒊𝒏 𝑍 = 0𝑋1 + 0𝑋2 + 0𝑆1 + 0𝑆2 + 1𝑹𝟏 + 1𝑹𝟐 𝑑𝑒𝑠𝑝𝑒𝑗𝑜: 𝑍−0𝑋1 − 0𝑋2 − 0𝑆1 − 0𝑆2 − 1𝑹𝟏 − 1𝑹𝟐 = 0 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

El coeficiente de Ri será 1 y del resto será 0

3𝑋1 + 3𝑋2 +5𝑋3 − 𝑺𝟏 + 𝑹𝟏 = 36 2𝑋1 + 𝑋2 +3𝑋3 − 𝑺𝟐 + 𝑹𝟐 = 60 𝑋1 , 𝑋2 , 𝑆1 , 𝑆2 , 𝑅1 , 𝑅2 ≥ 0

Plasmamos el Problema en una tabla:

Para que R1 y R2 sea Vector Unitario: Z ←R1+R2+Z

SIMPLEX X2 ←R2/6 R1 ←R1 antiguo+ X2*(-3) Z ←Z antiguo+ X2*(-9)

X1 ←R1*2 X2 ←X2 antiguo+ X1*(-1/2) Z ←Z antiguo+ X1*(-1/2)

Z R1 R2 Z R1 R2 1ERA ITER.

R1 X2 2DA ITER.

X1 X2

Z 1 0 0 1 0 0 1 0 0 1 0 0

X1 0 2 3 5 2 3 1/2 1/2 1/2 0 1 0

X2 0 3 6 9 3 6 0 0 1 0 0 1

S1 0 -1 0 -1 -1 0 -1 -1 0 0 -2 1

Para aplicar simplex, R1 y R2 deben vectores unitarios.

S2 0 0 -1 -1 0 -1 1/2 1/2 -1/6 0 1 -2/3

R1 -1 1 0 0 1 0 0 1 0 -1 2 -1

R2 -1 0 1 0 0 1 -3/2 -1/2 1/6 -1 -1 2/3

Se eliminaron las Variables Artificiales de la base

2DA FASE

Sol. 0 36 60 96 36 60 6 6 10 0 12 4

+ positivo 36/3=12

VE=X2 VS=R2

60/6=10 + positivo 6/1/2=12

VE=X1 VS=R1

10/1/2=20

Z*= 0

FIN 1ERA FASE

Formulo el problema para aplicar la 2da Fase.

Forma Canónica:

𝑴𝒊𝒏 𝑍 = 2000𝑋1 + 500𝑋2 + 0𝑆1 + 0𝑆2 𝑑𝑒𝑠𝑝𝑒𝑗𝑜 𝑍−2000𝑋1 − 500𝑋2 − 0𝑆1 − 0𝑆2 = 0

67

Usando el resultado de la 1era Fase, sin considerar la columna de la Variable artificiales y considerando la F.O. del problema original. Para aplicar simplex, X1 y X2 deben vectores unitarios.

Para que X1 y X2 sea vector Unitario: Z ←X1*2000+X2*500+Z

SIMPLEX S2 ←X1 X2 ←X2 antiguo+S2*(2/3) Z ←Z antiguo+ S2*(-5000/3)

Z X1 X2 1ERA ITER.

X1 X2 2DA ITER.

S2 X2

Z 1 0 0 1 0 0 1 0 0

X1 -2000 1 0 0 1 0 -5000/3 1 2/3

X2 -500 0 1 0 0 1 0 0 1

S1 0 -2 1 -3500 -2 1 -500/3 -2 -1/3

S2 Sol. 0 0 1 12 -2/3 4 5000/3 26000 1 12 -2/3 4 0 6000 1 12 0 12

La solución óptima es Z* = 6000 ya que Z* = 2000(0)+500(12)=6000

+ positivo 12/1=12

VE=S2 VS=X2

4/-2/3=10

Verifico que Zj – Cj ≤0 y paramos.

FIN 2DA FASE

S2 ] = [12 ], 𝑋𝑁 = [X1 ] = [00] 𝑋𝐵 = [X2 12 S1

GRÁFICO Punto Óptimo

𝑴𝒊𝒏 𝑍 = 2000𝑋1 + 500𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 3𝑋2 ≥ 36 …L1 3𝑋1 + 6𝑋2 ≥ 60 … L2 𝑋𝑖 ≥ 0

𝑖 = 1,2

El valor mínimo de la función objetivo es 6000, y corresponde a x1 = 0 y x2 = 12 (Punto A) El problema presenta Solución Óptima con Región Factible No acotada.

68

5.6

Ejercicios 𝑴𝒂𝒙 𝑍 = 3𝑋1 + 𝑋2

𝑴𝒊𝒏 𝑍 = 4𝑋1 + 4𝑋2 + 𝑋3

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 𝑋2 ≥ 3 2𝑋1 + 𝑋2 ≤ 4 𝑋1 + 𝑋2 = 3 𝑋𝑖 ≥ 0

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 𝑋2 + 𝑋3 ≥ 2 2𝑋1 + 𝑋2 ≤3 2𝑋1 + 𝑋2 + 3𝑋3 ≥ 3

𝑖 = 1,2

𝑋𝑖 ≥ 0

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 𝑋2 ≥ 4 2𝑋1 + 𝑋2 ≥ −1 𝑋𝑖 ≥ 0

𝑖 = 1,2,3

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 3𝑋1 + 𝑋2 = 3 4𝑋1 + 3𝑋2 ≥ 6 𝑋1 + 2𝑋2 ≤ 4

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 0,6𝑋1 + 0,4𝑋2 ≥ 6 0,3𝑋1 + 0,1𝑋2 ≤ 2.7 0,5𝑋1 + 0,5𝑋2 = 6

≤4 2𝑋2 ≤ 12 3𝑋1 + 2𝑋2 = 18 𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑖 = 1,2

𝑴𝒊𝒏 𝑍 = 4𝑋1 + 𝑋2

𝑴𝒂𝒙 𝑍 = 3𝑋1 + 5𝑋2

𝑴𝒊𝒏 𝑍 = 0,4𝑋1 + 0,5𝑋2

𝑋𝑖 ≥ 0

𝑴𝒂𝒙 𝑍 = 2𝑋1 + 3𝑋2

𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑖 = 1,2

𝑴𝒂𝒙 𝑍 = 3𝑋1 + 8𝑋2

𝑴𝒂𝒙 𝑍 = −8𝑋1 + 3𝑋2 − 6𝑋3

𝑴𝒂𝒙 𝑍 = 6𝑋1 + 3𝑋2 − 4𝑋3

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 4𝑋2 ≤ 4 𝑋1 + 2𝑋2 ≥ 2

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 3𝑋2 + 5𝑋3 = 4 5𝑋1 + 3𝑋2 − 4𝑋3 ≥ 6

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 6𝑋2 + 𝑋3 = 10 2𝑋1 + 3𝑋2 ≤ 15

𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑋𝑖 ≥ 0

𝑋𝑖 ≥ 0

𝑖 = 1,2,3

𝑴𝒊𝒏 𝑍 = 160𝑋1 + 120𝑋2 − 280𝑋3

𝑴𝒂𝒙 𝑍 = 3𝑋1 + 2𝑋2

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 𝑋2 + 4𝑋3 ≥ 1 2𝑋1 + 2𝑋2 + 2𝑋3 ≥ 3/2

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 2𝑋2 ≤ 12 2𝑋1 + 3𝑋2 = 12 2𝑋1 + 𝑋2 ≥ 8

𝑋𝑖 ≥ 0

𝑖 = 1,2,3

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 3𝑋1 + 𝑋2 ≥ 3 4𝑋1 + 3𝑋2 ≥ 6 𝑋𝑖 ≥ 0

𝑴𝒂𝒙 𝑍 = 2𝑋1 + 𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 10𝑋1 + 10𝑋2 ≤ 9 10𝑋1 + 5𝑋2 ≥ 1 𝑋𝑖 ≥ 0

𝑋𝑖 ≥ 0

𝑴𝒂𝒙 𝑍 = 𝑋1 + 2𝑋2

𝑖 = 1,2,3

𝑴𝒂𝒙 𝑍 = 3𝑋1 + 2𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 − 𝑋2 ≥ 0 𝑋1 + 𝑋2 ≤ 6 𝑋1 = 2

𝑖 = 1,2 𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑖 = 1,2

𝑖 = 1,2

𝑴𝒊𝒏 𝑍 = 3𝑋1 + 2𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 𝑋2 ≥ 4 𝑋1 ≤3 𝑋2 = 3 𝑋1 − 3𝑋2 ≤ 0 𝑋𝑖 ≥ 0

𝑖 = 1,2

69

DUALIDAD DE UN PPL

6.1

Introducción Hemos visto como la programación lineal puede ser usada para resolver una extensa variedad de problemas propios de los negocios, ya sea para maximizar utilidades o minimizar costos. Las variables de decisión en tales problemas fueron, por ejemplo, el número de productos a producir, la cantidad de pesos a emplear, etc. En cada caso la solución óptima no explicó cómo podrían ser asignados los recursos (ejemplo: materia prima, capacidad de las máquinas, el dinero, etc.) para obtener un objetivo establecido. La teoría de dualidad es una propiedad matemática. Este concepto se aplica a la teoría de optimización. Todo problema de programación lineal se le asocia otro problema de programación lineal, llamado el problema de

70

programación dual. En particular, todo problema lineal (primal) tiene su correspondiente dual. La solución óptima del problema de programación dual, proporciona la siguiente información respecto del problema de programación original: 1. La solución óptima del problema dual proporciona los precios en el mercado o los beneficios de los recursos escasos asignados en el problema original. 2. La solución óptima del problema dual aporta la solución óptima del problema original y viceversa. Normalmente llamamos al problema de programación lineal original el problema de programación primal. El problema dual es un problema de PL auxiliar que se define directa y sistemáticamente a partir del modelo de PL original o primal. PPL Primal:

PPL Dual:

𝑴𝒂𝒙 𝑍 = 𝑪𝑋 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑨𝑋 ≥ 𝑏

Su dual asociado es el problema de PL dado por:

𝑴𝒊𝒏 𝑄 = 𝑏𝑌 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑨𝒕 𝑌 ≥ 𝑪

𝑋≥0

6.2

Relación Dual

𝑌≥0

entre

Primal

y

6.3 FO: MIN

FO: MAX

b

C

M Restricc.

A

b

N Restricc.

At

N Variables

M Variables

X es Var. Primal

Y es Var. Dual

C

71



La relación principal entre un PPL Primal y su PPL Dual es que tanto el problema primal como el dual buscan el valor óptimo del sistema.



En relación a la variaciones en las desigualdades: PPL MIN VARIABLES

RESTRICCIONES

PPL MAX

≥ ≤

↔ ↔

≤ ≥ irrestricto ↔ = ≥ ↔ ≥ ≤ ↔ ≤ = ↔ irrestricto

RESTRICCIONES

VARIABLES

Si el PPL Primal es de Minimizar, nos ubicamos en la columna de PPL MIN, donde la tabla indica, por ejemplo: - Si el PPL Primal es de Minimizar, su Dual será de Maximizar. - Si el PPL Primal presenta una variable con desigualdad ≥, entonces en el PPL Dual, la restricción será de ≤. - Si el PPL Primal presenta una restricción con desigualdad ≥, entonces en el PPL Dual, la variable será de ≥. Y si fuera el PPL Primal de Maximizar, nos ubicamos en la columna de PPL Max y ubicamos la desigualdad según corresponda.

6.3

Formulación del Dual Veamos un ejemplo: PPL Primal:

𝑴𝒂𝒙 𝑍 = 𝟑𝑋1 + 𝟔𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 −𝑋1 + 𝟗𝑋2 ≤ 𝟏𝟎 −𝟓𝑋1 + 𝟐𝑋2 = 𝟐 𝑋1 𝑐𝑢𝑎𝑙𝑞𝑢𝑖𝑒𝑟𝑎 , 𝑋2 ≥ 0

PPL Dual: Su dual asociado es el problema de PL dado por:

𝑴𝒊𝒏 𝑄 = 𝟏𝟎𝑌1 + 𝟐𝑌2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 −𝑌1 − 𝟓𝑌2 = 𝟑 𝟗𝑌1 + 𝟐𝑌2 ≥ 𝟔 𝑌1 ≥ 0, 𝑌2 𝑐𝑢𝑎𝑙𝑞𝑢𝑖𝑒𝑟𝑎

72

Veamos paso a paso: 1. Los coeficientes se ordenarán de esta manera: PPL Primal:

PPL Dual:

𝑴𝒂𝒙 𝑍 = 𝟑𝑋1 + 𝟔𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 −1𝑋1 + 𝟗𝑋2 ≤ 𝟏𝟎 −𝟓𝑋1 + 𝟐𝑋2 = 𝟐

𝑴𝒊𝒏 𝑄 = 𝟏𝟎𝑌1 + 𝟐𝑌2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 −𝟏𝑌1 − 𝟓𝑌2 = 𝟑 +𝟗𝑌1 + 𝟐𝑌2 ≥ 𝟔 𝑌1 ≥ 0, 𝑌2

𝑋1 𝑐𝑢𝑎𝑙𝑞𝑢𝑖𝑒𝑟𝑎 , 𝑋2 ≥ 0

Hay una forma práctica de formular la dualidad. Podrás verla en la Preg. 5 de los Ejemplos de este tema.

2. Las desigualdades se asignarán según la tabla. PPL Primal:

PPL Dual:

𝑴𝒂𝒙 𝑍 = 𝟑𝑋1 + 𝟔𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 −1𝑋1 + 𝟗𝑋2 ≤ 𝟏𝟎 −𝟓𝑋1 + 𝟐𝑋2 = 𝟐

𝑴𝒊𝒏 𝑄 = 𝟏𝟎𝑌1 + 𝟐𝑌2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 −𝟏𝑌1 − 𝟓𝑌2 = 𝟑 +𝟗𝑌1 + 𝟐𝑌2 ≥ 𝟔

𝑋1 𝑐𝑢𝑎𝑙𝑞𝑢𝑖𝑒𝑟𝑎 , 𝑋2 ≥ 0

𝑌1 ≥ 0, 𝑌2 𝑖𝑟𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑡𝑜 Rest. ≤ →Var. Y1 ≥. Rest. = →Var. Y2 cualquiera. Var. X2 ≥ corresponde Restricción con ≥. Var. X1 cualquiera corresponde Restricción con =.

PPL MIN VARIABLES

RESTRICCIONES

6.4

PPL MAX ≥ ↔ ≤ ≤ ↔ ≥ irrestricto ↔ = ≥ ↔ ≥ ≤ ↔ ≤ = ↔irrestricto

RESTRICCIONES

VARIABLES

Teorema de Dualidad

Dado un par de problema (primal y su dual) uno y solamente uno de las tres afirmaciones es verdadero. - Los dos problemas son vacíos. - Uno es vacío y el otro ilimitado. - Ambos admiten soluciones óptimas finitas (sus funciones objetivo en el punto óptimo asumen igual valor) PROPIEDAD

El Dual del Dual es el primal

73

EJEMPLO

Tenemos el PPL Minimización: PPL Dual:

PPL Primal:

𝑴𝒊𝒏 𝑍 = 3𝑋1 + 5𝑋2

𝑴𝒂𝒙 𝑍 = 4𝑌1 + 6𝑌2 + 18𝑌3

Su dual asociado es el problema de PL dado por:

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑌1 + 3𝑌3 ≤ 3 𝑌2 + 2𝑌3 ≤ 5

𝑋1 ≤ 4 𝑋2 ≤ 6 3𝑋1 + 2𝑋2 ≥ 18 𝑋𝑖 ≥ 0

𝑌1 ≤ 0 , 𝑌2 ≤ 0, 𝑌3 ≥ 0

𝑖 = 1,2 Estandarizamos

PPL Primal:

PPL Dual:

𝑴𝒊𝒏 𝑍 = 3𝑋1 + 5𝑋2 + 0𝑆1 + 0𝑆2 + 0𝑆3 + 𝑴𝑅1

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑴𝒂𝒙 𝑍 = −4𝑌′1 + −6𝑌′2 + 18𝑌3 + 0𝑆1 + 0𝑆2

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑋1

+ 𝑆1

𝑋2 3𝑋1 + 2𝑋2

=4 + 𝑆2 =6 − 𝑆3 + 𝑅1 = 18

𝑌1 + 3𝑌3 + 𝑆1 =3 𝑌2 + 2𝑌3 + 𝑆2 = 5 −𝑌1 ≥ 0 , −𝑌2 ≥ 0, 𝑌3 ≥ 0 𝑆𝑖 ≥ 0 𝑖 = 1,2 ′ −𝑌1 = 𝒀 𝟏 , − 𝑌2 = 𝒀′𝟐 Var. Positivas

𝑋1 , 𝑋2 , 𝑆1 , 𝑆2 , 𝑆3 , 𝑅1 ≥ 0

Resolvemos QXS X X222SSS2322 SS S Sol. Sol. X22 X2Z ZQQZ XXX Z S231 X S111 SS1112 S S R SS121R1Sol. SS R1 2 Sol. 111X1 XX 1 3Sol. 13 31 R 3Sol. 6 -511-5 Z 0 0 -M 00 00 0-M0 QQ Z111Z 1 -3414 -3 -3-5 6Z 0 -3 0 -M Q 4 00 0-5 6 00 000 0-M 010 1-1 -1 1 1S 1 33 S 0 S 0011 000 01 0 -1 10 01 10 0 010 001 0 0 01 0 40 04 4 03 10S S1S 1 1S0 0 0 -1 0 1 5 S S 0 S 0 0 0 0 0 S 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 00 0 61 16 6 05 2 2 2 2 S2S 0 0 -1 0 1 5 S 0 0 -1 0 2 2 1ERA 1ERA R R011R 0 R 3 -10 02 00 0-118 0 1 10 1 18 0 18 181 110 3-2 -2 3 31ERA 6 -1 ITER. 1 6261 201 2-1 6 ITER. -2 6 6 18 0 18 ITER. ZY3Z1 0Z 13M-3 13M-3 3M-3 2M-5 Z 2M-5 2M-5 11/3 -M3M-3 -M -M 0 2M-5 0 0 0-M 0 0 00 0 18M 0 18M18M0 -1/3 0 1 Y3 0 -1/3 Y03 01/3-1/3 0 0 1/3 1 0 1 0 0 12/3 -1 30 01 0 40 4 4 0 S1S2S0 S 0 1 1S 01 00-2/3 00 10 01 10 10 00 0 S22DA 10 1 2/3 -1 -2/32/3 1 -2/33 S 0 -1 1 3 2 S2DA2ITER.S0 S 132 10 14 0 00 00 01 31 0 10 27 1 0 00 0 61 6 6 0 120 000 0 02DA 2 S 1 0 300 3 3ITER. 32 201 2-1 4 -1 3 0-1 27 ITER. 0 3 4 3 27 R1X1R01 R R 3 -1 0 0 2 0 0 1 1 0 1 18 0 18 18 1 1 01 0 -1/2 0 1/2 5/2 1ERA 1ERA01ERA 1ERA XY’ -1/2 0 -M 1/2 5/2 1 ITER. XITER. -1/2 09/3 5/2 0-3/2 2M-5 10 -M 00-3M-3 -M-3M-3 2M-5 -3M-3 0 0-M 0 0 -3M-3 0 06M+12 6M+12 01/26M+12 0 12M-5 ITER. 0 1 0011 0 2M-5 -1 3/2 1 1 ITER. Y’ 0 1 -3/2 -1 3/2 1 Y’ 1 01 -3/2 X1 X0 X 011 000 00 10 10 0 1 0-1 0 9/3 0 0 01 0 403/2 4 4 9/3 0 1 X10 10 1 1 S2 S0 02 00 00 00 00 00 1 0 10 1 0 00 0 61 6 6 0 2 S20 00 0 0S R1 R01 R10 00 0 0R 2 1 20 2-1 -1 0 -1 -3 -3 2 -3 0 0-1 0 1 1 -3 1 60 6 6 1 2DA 2DA 2DA 1 ITER.1 01 0 0ITER. 02DA 01-5/2 0 -5/2 0 -5/2 -9/2-9/2 0-9/2 0 -5/2 0 -M+5/2 0 -M+5/2 -9/2 -M+5/2 27 0 27 -M+5/2 27 ITER. ITER. X1 X0 01 00 00 10 01 10 0 1 00 0 0 01 0 40 4 4 0 1 X10 10 1 1X S2 S0 02 00 1/2 0 1/2 0 1/2 3/2 3/2 0 3/2 1 11/2-1/2 1 -1/2 3/2-1/2 31 3 3-1/2 2 S20 00 0 0S X2 X0 12 10-1/2 1 -1/2 0 -1/2 -3/2-3/2 1-3/2 0 -1/2 0 01/2 1/2 -3/21/2 30 3 31/2 2 X20 00 0 0X

Sol. 0 Q 4 S1 6 S2 18 1ERA ITER. 18M Y 43 S2 6 2DA ITER. 18 X1 6M+12 Y’ 41 6 6 27La 4 3 3

Q Y’1 1 4 0 -1 0 0 1 -2 0 -1/3 0 2/3 1 0 0 0 0 1

X1

4

S1

0

Y3 -18 3 2 0 1 0 0 1 0

S1 0 1 0 6 1/3 -2/3 4 0 -1

S2 0 0 1 0 0 1 3 1/2 3/2

Sol. 0 3 5 18 1 3 27 5/2 9/3

solución óptima del PPL DUAL es Q* = 27 ya que Q* = 4(-9/2)+6(0)+18(5/2) =27 Y1

La solución óptima del PPL PRIMAL es Z* = 27 ya que Z* = 3(4)+5(3) =27

Y’2 6 0 -1 6 0 -1 3 -1/2 -3/2

−9/2 0 ], 5/2

𝑋𝐵 = [Y2 ]=[ Y3

] = [00] 𝑋𝑁 = [S1 S2

𝒀′ 𝟏 = 9/2 → 𝑌1 = −9/2 𝒀′𝟐 = 𝟎 → 𝑌2 = 0

S2 ] = [0] 𝑋𝐵 = [X2 ] = [33], 𝑋𝑁 = [R1 0 S2

La solución óptima es 27. En ambos casos nos da el mismo resultado. Siempre la solución será la misma.

74

EJEMPLO

Tenemos el PPL Maximización: PPL Dual:

PPL Primal:

𝑴𝒂𝒙 𝑍 = 4𝑋1 + 3𝑋2

𝑴𝒊𝒏 𝐺 = 18𝑌1 + 10𝑌2

Su dual asociado es el problema de PL dado por:

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑌1 + 4𝑌2 ≥ 4 2𝑌1 + 2𝑌2 ≥ 3

2𝑋1 + 3𝑋2 ≤ 18 4𝑋1 + 2𝑋2 ≤ 10 𝑋𝑖 ≥ 0

𝑌1 ≥ 0 𝑖 = 1,2

𝑖 = 1,2

¿Es posible hallar el valor de las Var. Duales hallando la solución del primal? Estandarizo mi PPL Primal y aplico Simplex:

Q S1 S2 1ERA ITER.

S1 X1 2DA ITER.

Tabla Óptima

S1 X2

Q 1 0 0 1 0 0 1 0 0

X1 -4 2 4 0 0 1 2 -4 2

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

S1 0 1 0 0 1 0 0 1 0

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

Sol. 0 18 10 10 13 5/2 15 3 5

Sol. Dual

La solución óptima del PPL PRIMAL es Z* = 15 ya que Z* = 4(0)+3(5)=15

La solución óptima del PPL DUAL es Q* = 15 ya que Q* = 18(0)+10(3/2)=15

S1 3 X1 0 𝑋𝐵 = [ ] = [ ], 𝑋𝑁 = [ ] = [ ] X2 5 S2 0

0 Y1 𝑌𝐵 = [ ] = [ ] 3/2 Y2

GRÁFICO

Punto Óptimo

𝑴𝒂𝒙 𝑍 = 4𝑋1 + 3𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 3𝑋2 ≤ 18 …L1 4𝑋1 + 2𝑋2 ≤ 10 … L2 𝑋𝑖 ≥ 0

𝑖 = 1,2

El valor máximo de la función objetivo es 15, y corresponde a x1 = 0 y x2 = 5 (Punto A) El problema presenta Solución Óptima con Región Factible Acotada.

75

Nos permite resolver problemas lineales donde el número de restricciones es mayor que el número de variables. La solución de unos de los problemas (primal o dual) nos proporciona de forma automática la solución del otro PPL. Otra de las ventajas de la dualidad, es la posibilidad de resolver gráficamente algunos problemas.

EJEMPLO

Tenemos el PPL Minimización: PPL Dual:

PPL Primal:

𝑴𝒊𝒏 𝑍 = 2𝑋1 + 3𝑋2 + 5𝑋3 + 2𝑋4 + 3𝑋5

𝑴𝒂𝒙 𝐺 = 4𝑌1 + 3𝑌2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 𝑋2 + 2𝑋3 + 𝑋4 + 3𝑋5 ≥ 4 2𝑋1 − 𝑋2 + 3𝑋3 + 𝑋4 + 𝑋5 ≥ 3 𝑋𝑖 ≥ 0

𝑖 = 1,2,3,4,5

𝑌1 + 2𝑌2 ≤ 2 𝑌1 − 𝑌2 ≤ 3 2𝑌1 + 3𝑌2 ≤ 5 𝑌1 + 𝑌2 ≤ 2 3𝑌1 + 𝑌2 ≤ 3 𝑌1 ≥ 0 𝑖 = 1,2

El PPL Primal presenta 5 variables, su Dual presenta 2 variables. Entonces es conveniente resolver el PPL Dual: 𝑴𝒂𝒙 𝐺 = 4𝑌1 + 3𝑌2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑌1 + 2𝑌2 ≤ 2 … L1 𝑌1 − 𝑌2 ≤ 3 … L2 2𝑌1 + 3𝑌2 ≤ 5 … L3 𝑌1 + 𝑌2 ≤ 2 … L4 3𝑌1 + 𝑌2 ≤ 3 … L5

GRÁFICO

𝑌1 ≥ 0 𝑖 = 1,2

Punto Óptimo B (4/5,3/5)

El valor máximo de la función objetivo es 5, y corresponde a Y1 = 4/5 y Y2 = 3/5 (Punto B) El problema presenta Solución Óptima con Región Factible Acotada.

76

6.5

Ejemplo Un fabricante de muebles tiene 6 unidades de madera y 28 horas disponibles, para fabricar biombos decorativos. EL modelo 1 requiere 2 unidades de madera y 7 horas del tiempo disponible; mientras que el modelo 2 requiere 1 unidad de madera y 8 horas. Los precios de los modelos 1 y 2 son $120 y $80, respectivamente. ¿Cuántos biombos de cada modelo debe fabricar si desea maximizar su ingreso en la venta? Determine el planteamiento del problema. El valor máximo de la función objetivo es 3520/9, y corresponde a X1 = 20/9 y X2 = 14/9 (Punto Q) El problema presenta Solución Óptima con Región Factible Acotada.

PPL Canónica:

𝑴𝒂𝒙 𝑍 = 120𝑋1 + 80𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 𝑋2 ≤ 6 7𝑋1 + 8𝑋2 ≤ 28

Punto Óptimo

𝑋𝑖 ≥ 0

1

𝑖 = 1,2

Resolvemos usando Simplex: BASE

Z S1 S2

PPL Estandarizado: 𝑴𝒂𝒙 𝑍 = 120𝑋1 + 80𝑋2 + 0𝑆1 + 0𝑆2

1ERA ITER.

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

X1 S2

2𝑋1 + 𝑋2 + 𝑆1 =6 7𝑋1 + 8𝑋2 + 𝑆2 = 28 𝑋𝑖 , 𝑆𝑖 ≥ 0

2

2DA ITER.

X1 X2

𝑖 = 1,2

Z X1 1 -120 0 2 0 7 1 0 0 1 0 0 1 0 0 1 0 0

PPL Dual Estandarizando: 𝑴𝒊𝒏 𝑄 = 6𝑌1 + 28𝑌2 + 0𝑆1 + 0𝑆2 + 𝑀𝑅1 + 𝑀𝑅2

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

Q R1 R2 Q R1 R2 1ERA ITER..

2𝑌1 + 7𝑌2 − 𝑆1 + 𝑅1 = 120 𝑌1 + 8𝑌2 − 𝑆2 + 𝑅2 = 80 𝑌𝑖 ≥ 0

𝑖 = 1,2

R1 Y2 2DA ITER

Y1 Y2

Q 1 0 0 1 0 0 1 0 0 1 0 0

Y1 -6 2 7

Y2 -28 7 8

-6+3M

-28+15M

2 1

7 8 0 0 1 0 0 1

-20/8+9M/8

9/8 1/8 0 1 0

S1 S2 Sol. 0 0 0 1 0 6 0 1 28 60 0 360 1/2 0 3 -7/2 1 7 400/9 40/9 3520/9 8/9 -1/9 20/9 -7/9 2/9 14/9

El valor máximo de la función objetivo es 3520/9, y corresponde a 20/9 S1 0 X1 𝑋𝐵 = [ ] = [ ], 𝑋𝑁 = [ ] = [ ] 14/9 S2 0 X2

Resolvemos EL Dual por Método de la M: BASE

X2 -80 1 8 -20 1/2 9/2 0 0 1

S1 S2 R1 R2 0 0 -M -M -1 0 1 0 0 -1 0 1 -M -M 0 0 -1 0 1 0 0 -1 0 1 -28/8+7M/8 7/2-15M/8 -M 0 -1 7/8 1 -7/8 0 -1/8 0 1/8 20/9-M 14/9-M -20/9 -14/9 -8/9 7/9 8/9 -7/9 máximo de la función2/9 1/9El valor-2/9 -1/9 objetivo es 3520/9, y corresponde a

𝑋𝐵 = [

S1

0

R2

0

Sol. 0 120 80 200M 120 80 280+50M

50 10 3520/9 400/9 40/9

400/9 Y1 ]=[ ], 𝑋𝑁 = [ S2 ] = [0] R1 0 40/9 Y2

77

3

Dado el PPL Primal de la pregunta 1 y su tabla óptima. Hallar la solución Óptima del Dual sin resolverlo. Conocemos al PPL Dual: PPL Primal:

PPL Dual: 𝑴𝒊𝒏 𝑄 = 6𝑌1 + 28𝑌2

𝑴𝒂𝒙 𝑍 = 120𝑋1 + 80𝑋2

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

4

2𝑌1 + 7𝑌2 ≥ 120 2𝑋1 + 𝑋2 ≤ 6 𝑌1 + 8𝑌2 ≥ 80 7𝑋 + 8𝑋 ≤ 28 BASE Z X11 X22 S1 S2 Sol. Z 1 -120 0 0 𝑌𝑖 ≥ 0 𝑖 = 1,2 𝑋𝑖 ≥ 0 -80𝑖 = 1,20 S1 0 2 1 1 0 6 S2 0 7 8 0 1 28 1ERA En la Pregunta tabla óptima del 1 10hallamos -20 la 60 0 360PPL Primal. ITER. X1 0 1 1/2 1/2 0 3 BASE S2 Z 0 X01 9/2 -7/2 7 X2 S1 S12 Sol. El valor máximo de la función 2DA objetivo es 3520/9, y corresponde a 0 0 400/9 40/9 3520/9 Z 1 -120 -80 0 0 0 ITER. Y1 = 400/9 →S1 y Y2 = 40/9 →S2 S1 0 2 1 1 0 6 X 1 0 8/9 -1/9 20/9 Verificando: Q*= 6 Y1 + 28 Y2 S2 0 7 8 0 1 28 X 0 1 -7/9 2/9 14/9 Q*= 6(400/9)+28(40/9) = 3520/9 1ERA 1 0 -20 60 0 360 ITER. X1 0 1 1/2 1/2 0 3 0 Dual 0 de9/2 -7/2 Dado Sel2 PPL la pregunta 21 y su 7tabla óptima. Hallar la solución 2DA 0 sin resolverlo. 0 400/9 40/9 3520/9 ITER. Óptima del1Primal X1 0 1 0 8/9 -1/9 20/9 X2 0 0 1 -7/9 2/9 14/9

Conocemos al PPL Dual y su Primal: PPL Primal:

PPL Dual: 𝑴𝒊𝒏 𝑄 = 6𝑌1 + 28𝑌2

𝑴𝒂𝒙 𝑍 = 120𝑋1 + 80𝑋2

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

2𝑌1 + 7𝑌2 ≥ 120 𝑌1 + 8𝑌2 ≥ 80

2𝑋1 + 𝑋2 ≤ 6 7𝑋1 + 8𝑋2 ≤ 28 𝑋𝑖 ≥ 0

𝑌𝑖 ≥ 0

𝑖 = 1,2

𝑖 = 1,2

En la Pregunta 2 hallamos la tabla óptima del PPL Dual.

2DA ITER

Y1 Y2

Q 1 0 0

Y1 0 1 0

Y2 0 0 1

S1 -20/9 -8/9 1/9

S2 -14/9 7/9 -2/9

R1

R2

20/9-M

14/9-M

8/9 -1/9

-7/9 2/9

Sol. 3520/9 400/9 40/9

El valor máximo de la función objetivo es 3520/9, y corresponde a X1 = 400/9→R1 y X2 = 40/9→R2 Verificando: Z*= 120 X1 + 80 X2 Z*= 120 (20/9)+80(14/9) = 3520/9

78

5

Observemos la Pregunta 3. Sólo debes organizar correctamente la manera en la que formulas tu PPL Dual. Primero, estandarizamos el PPL Primal. PPL Estandarizado:

PPL Canónica:

𝑴𝒂𝒙 𝑍 = 120𝑋1 + 80𝑋2 + 0𝑆1 + 0𝑆2

𝑴𝒂𝒙 𝑍 = 120𝑋1 + 80𝑋2

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

2𝑋1 + 𝑋2 + 𝑆1 =6 7𝑋1 + 8𝑋2 + 𝑆2 = 28

2𝑋1 + 𝑋2 ≤ 6 7𝑋1 + 8𝑋2 ≤ 28 𝑋𝑖 ≥ 0

𝑋𝑖 , 𝑆𝑖 ≥ 0

𝑖 = 1,2

𝑖 = 1,2

Segundo, formulemos su PPL Dual (Forma Práctica). PPL MIN VARIABLES

RESTRICCIONES

PPL MAX ≥ ↔ ≤ ≤ ↔ ≥ irrestricto ↔ = ≥ ↔ ≥ ≤ ↔ ≤ = ↔irrestricto

PPL Primal:

RESTRICCIONES

① Identifico Variables Duales. Le “asigno” una variable dual a cada restricción.

VARIABLES

𝑴𝒂𝒙 𝑍 = 120𝑋1 + 80𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 ③ Identifico las desigualdades que tendrán las restricciones en el PPL Dual. Le “asigno” una desigualdad en cada columna (futura restricción dual) de la variable según corresponda.

≥

≥

2𝑋1 + 𝑋2 ≤ 6 Y1 ≥0 7𝑋1 + 8𝑋2 ≤ 28 Y2 ≥0 𝑋1 ≥ 0, 𝑋2 ≥ 0

Ejemplo: X1 es ≥ 0, entonces asignaré una desigualdad ≥ a la columna de X1.

② Identifico desigualdad de Variables Duales. Le “asigno” una desigualdad a la variable dual, según corresponda. Ejemplo: La restricción 1 es ≤ 6, entonces asignaré una desigualdad ≥ a la variable Y1.

Ahora formulemos el Dual. PPL Primal:

𝑴𝒂𝒙 𝑍 = 120𝑋1 + 80𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

≥

≥

2𝑋1 + 𝑋2 ≤ 6 Y1 ≥0 7𝑋1 + 8𝑋2 ≤ 28 Y2 ≥0 𝑋1 ≥ 0, 𝑋2 ≥ 0

PPL Dual: 𝑴𝒊𝒏 𝑄 = 6𝑌1 + 28𝑌2

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑌1 + 7𝑌2 ≥ 120 𝑌1 + 8𝑌2 ≥ 80 𝑌1 ≥ 0, 𝑌2 ≥ 0

Z X1 X2 S1 S2 Sol. Z 1 -120 -80 0 0 0 Veamos que al formular el PPL Dual asignamos Y1 a la primera restricción S1 0 2 1 1 0 6 del Primal. Dicha restricción, al estandarizar, tiene 28 la variable S1. Entonces en S2 0 7 8 0 1 1ERA la tabla ubicaremos que su valor en los Zj – Cj será el valor de 1 S10y sabremos -20 60 0 360 ITER. Y1. X1 0 1 1/2 1/2 0 3 BASE El valor máximo de la S 0 0 9/2 -7/2 1 7 Z X1 X2 S1 S2 Sol. 2 función objetivo es 2DA 0 0 400/9 40/9 3520/9 Z 1 -120 -80 0 0 0 ITER. 3520/9, y corresponde a Y1 = 400/9 →S1 y S1 0 2 1 1 0 6 X 1 0 8/9 -1/9 20/9 Y2 = 40/9 →S2 S2 0 7 8 0 1 28 X 0 1 -7/9 2/9 14/9 1ERA 1 0 -20 60 0 360 ITER. X1 0 1 1/2 1/2 0 3 BASE

79

Tabla resumen de las Reglas de paso del Primal al Dual Primal

Dual

Maximizar Función Objetivo Fila i-ésima de Coef. Columna j-ésima de Coef. Relación i-ésima de ≤ Relación i-ésima de = Variable j-ésima no restringida Variable j-ésima no negativa

6.6

Minimizar Término Independiente Columna i-ésima de Coef. Fila j-ésima de Coef. Variable i-ésima no negativa Variable i-ésima no restringida Restricción de = Restricción de ≥

Ejercicios 𝑴𝒂𝒙 𝑍 = 15000𝑋1 + 12000𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑴𝒂𝒙 𝑍 = 200𝑋1 + 300𝑋2

𝑴𝒂𝒙 𝑍 = 3𝑋1 + 𝑋2

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 𝑋2 ≥ 3 2𝑋1 + 𝑋2 ≤ 4 𝑋1 + 𝑋2 = 3

3𝑋1 ≤ 180 5𝑋2 ≤ 200 4𝑋1 + 6𝑋2 ≤ 360 8𝑋1 + 8𝑋2 ≤ 800 𝑋𝑖 ≥ 0

4𝑋1 + 4𝑋2 ≤ 36 3𝑋1 + 6𝑋2 ≤ 48 𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑋𝑖 ≥ 0

𝑴𝒂𝒙 𝑍 = 5𝑋1 + 12𝑋2 + 14𝑋3 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 2𝑋2 + 𝑋3 ≤ 5 2𝑋1 − 𝑋2 + 3𝑋3 = 2 𝑋𝑖 ≥ 0

𝑖 = 1,2,3

𝑴𝒊𝒏 𝑍 = 4𝑋1 + 4𝑋2 + 𝑋3 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 𝑋2 + 𝑋3 ≥ 2 2𝑋1 + 𝑋2 ≤3 2𝑋1 + 𝑋2 + 3𝑋3 ≥ 3 𝑋𝑖 ≥ 0

𝑴𝒊𝒏 𝑍 = 0,4𝑋1 + 0,5𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 0,6𝑋1 + 0,4𝑋2 ≥ 6 0,3𝑋1 + 0,1𝑋2 ≤ 2.7 0,5𝑋1 + 0,5𝑋2 = 6 𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑴𝒂𝒙 𝑍 = 3𝑋1 + 8𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 4𝑋2 ≤ 4 𝑋1 + 2𝑋2 ≥ 2 𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑖 = 1,2

𝑖 = 1,2,3

𝑴𝒂𝒙 𝑍 = 3𝑋1 + 5𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1

≤4 2𝑋2 ≤ 12 3𝑋1 + 2𝑋2 = 18 𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑖 = 1,2

𝑴𝒂𝒙 𝑍 = 2𝑋1 + 3𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 𝑋2 ≥ 4 2𝑋1 + 𝑋2 ≥ −1 𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑴𝒊𝒏 𝑍 = 4𝑋1 + 𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 3𝑋1 + 𝑋2 = 3 4𝑋1 + 3𝑋2 ≥ 6 𝑋1 + 2𝑋2 ≤ 4 𝑋𝑖 ≥ 0

𝑖 = 1,2

𝑴𝒂𝒙 𝑍 = −8𝑋1 + 3𝑋2 − 6𝑋3

𝑴𝒂𝒙 𝑍 = 6𝑋1 + 3𝑋2 − 4𝑋3

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 3𝑋2 + 5𝑋3 = 4 5𝑋1 + 3𝑋2 − 4𝑋3 ≥ 6

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑋1 + 6𝑋2 + 𝑋3 = 10 2𝑋1 + 3𝑋2 ≤ 15

𝑋𝑖 ≥ 0

𝑖 = 1,2,3

𝑋𝑖 ≥ 0

𝑖 = 1,2,3

80

MÉTODO DUAL SIMPLEX

7.1

Introducción Recordemos, en el Método Simplex se cumple:

SIMPLEX Condición de Optimalidad

Condición de Factibilidad

Cj-Zj ≥0

XB≥0 81

El algoritmo simplex-dual el problema empieza optimo y no factible. Las iteraciones sucesivas están diseñadas para avanzar hacia la factibilidad sin violar la Optimalidad. Cuando se restaura la factibilidad, el algoritmo termina.

CarltonE. Lemke

7.2

Este método fue elaborado por CarltonE. Lemke en 1954, se utiliza para hallar la solución de un PPL, que es óptimo pero no factible. En la actualidad todos los software comerciales utilizan éste método.

Método Dual Simplex PPL Primal:

PPL Dual: Su dual asociado es el problema de PL dado por:

𝑴𝒂𝒙 𝑍 = 𝑪𝑋 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑨𝑋 ≥ 𝑏 𝑋≥0

El Método Dual Simplex inicia y termina siendo óptimo. Pero inicia siendo no factible y termina siendo factible.

EJEMPLO

𝑴𝒊𝒏 𝑄 = 𝑏𝑌 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑨𝒕 𝑌 ≥ 𝑪 𝑌≥0

Se aplica para resolver problemas que tienen factibilidad dual, es decir son óptimos, pero no factibles. Se aplica de manera general en modelos de minimización. La limitación de este método es que no siempre es posible obtener una solución óptima. Se aplica cuando las restricciones son “≥“y los costos son negativos. Veamos el procedimiento con un ejemplo:

Tenemos el PPL Minimización: PPL Estandarizado

𝑴𝒊𝒏 𝑍 = 5𝑋1 + 4𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 𝑋2 ≤ 4 𝑋1 + 𝑋2 ≥ 3 𝑋1 , 𝑋2 ≥ 0

𝑴𝒊𝒏 𝑍 − 5𝑋1 − 4𝑋2 = 0

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 𝑋2 ≤ 4 −𝑋1 − 𝑋2 ≤ −3 𝑋1 , 𝑋2 ≥ 0

① Convertir las desigualdades de las restricciones en ≤ multiplicando por (-1)

𝑴𝒊𝒏 𝑍 − 5𝑋1 − 4𝑋2 − 0𝑆1 − 0𝑆2 = 0

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 + 𝑋2 + 𝑆1 =4 −𝑋1 − 𝑋2 + 𝑆2 = −3 𝑋1 , 𝑋2 , 𝑆1 , 𝑆2 ≥ 0

② Estandarizar el PPL

82

Si se intenta expresar este problema como una tabla simplex inicial, se observará que las variables de holgura (S1, S2) no ofrecen una solución inicial factible. Como este es un problema de minimización y todos los coeficientes de la ecuación objetivo son ≤ 0, la solución básica inicial S1 = 4 y S2 = -3 es óptima pero no factible. Este problema es del tipo común que ③ Elaborar la tabla se puede manejar a través del método simplex dual. inicial con los Zj-Cj≥0. Aplico el Método Simplex Dual: ⑥ Hacemos las transformaciones para que la columna del pivote se convierta a su forma canónica.

Z S1 S2

X2 ←S2/2 S1 ←S1 antiguo+ (-1)*X2 Z ←Z antiguo+ (-4)*X2

1ERA ITER

S1 X2

Z 1 0 0 1 0 0

X1 -5 2 -1 -1 1 1

X2 -4 1 -1 0 0 1

S1 0 1 0 0 1 0

⑦ Paramos cuando XB≥0, sino regresamos al paso 4.

Recuerda: En el Método SIMPLEX se elige primero, la VE y luego la VS. En el Método Simplex DUAL primero eliges la VS y luego la VE.

S2 0 0 1 -4 1 -1

Sol. 0 4 -3 12 1 3

④Variable de Salida. VS=min {b, bCR

Sol. Óptima Alternas.

∀ Solución con Xi VB

Ǝ Solución con Xi VB

Ǝ Solución con Xi VNB

El CR para Xi es la cantidad que le sobra o le falta a Xi para estar en la base óptima. PPL MAX

Falta CR

Debo aumentar

PPL MIN

Sobra CR

Debo disminuir

92

EJEMPLO

¿Y si el valor de un Ci de una Variable NO Básica se aumenta en más que su CR, cómo actúa la solución Óptima y el valor de la F.O.? 𝑴𝒂𝒙 𝑍 = 4𝑋1 + 6𝑋2 + 7𝑋3 + 8𝑋4 VNB  X1 VB  X2 VB  X3 VB  X4

=0 = 400 = 150 = 400

VNB  X1=0CR=1

Z* = 6650

De C1 = 4 a C1’ = 6 ΔC1 = C1’ – C1 = 6 – 4 = 2 ¿ΔC1= 2 es mayor que 1=CR? SI  Ya que C1 pertenece a Var. NO Básicas.  X1 VNB → VB cambia.  Z*→Z’ cambia. Z’ = Z* + ΔC1(X1) no se puede usar.

Verifiquemos en LINDO. Z’ = X1 = X2 = X3 = X4 =

EJEMPLO

¿Y si el valor de un Ci de una Variable NO Básica se aumenta en su CR, cómo actúa la solución Óptima y el valor de la F.O.? 𝑴𝒂𝒙 𝑍 = 4𝑋1 + 6𝑋2 + 7𝑋3 + 8𝑋4 VNB  X1 VB  X2 VB  X3 VB  X4

Recuerda que por ser este ejemplo un PPL MAX, debemos aumentar, igual o más que su CR. Si fuese de MIN debemos disminuir, igual o más que su CR.

←VB

=0 = 400 = 150 = 400

VNB  X1=0CR=1

Z* = 6650

De C1 = 4 a C1’ = 5 ΔC1 = C1’ – C1 = 5 – 4 = 1 ¿ΔC1= 2 es igual que 1=CR? SI  Ya que C1 pertenece a Var. NO Básicas.  Ǝ Sol. X1 VB.  Z* no cambia →Sol. Óptimas Alternas. Z’ = Z* + ΔC1(X1) no se puede usar.

Verifiquemos en LINDO. ←Sol. Óptima Alternativa

Z’ = X1 = X2 = X3 = X4 =

←VB

93

8.6

Precio Dual

Al inicio de este capítulo se brindó una breve interpretación de Precio Dual:

El precio Dual (PD), conocido también como Precio Sombra (PS), de la iésima restricción de un PL es la cantidad en que mejora el valor Z óptimo del PL si el Lado derecho (LD) aumenta una unidad. Si después de un cambio en el Lado Derecho de una restricción la base actual ya no es óptima, entonces podrán modificarse los PD de todas las restricciones.

EJEMPLO

Vamos a variar el lado derecho de una restricción y veremos cómo afecta la solución óptima y el valor de la FO. X1 X2 X3 X4

= = = =

0 400 150 400

Z* = 6650

De B1 = 950 a B1’ = 951 ΔB1 = B1’ – B1 = 951 – 950 = 1 ¿ΔB1= 1 pertenece al intervalo? SI 

-100 ≤ ΔB1 ≤ 50 -125 ≤ ΔB2 ≤ 37.5 -150 ≤ ΔB3 ≤ 250 -250 ≤ ΔB4 ≤ ꝏ Rest. Activa →B1→ Y1 Rest. Activa → B2→ Y2 Rest. Activa → B3→ Y3 Rest. NO Activa → B4→ Y4

Ya que B1 pertenece a Var. NO Básicas.  BASE ÓPTIMA no cambia.  Z* cambia

=3 =-2 =1 =0

Z’ = Z* + ΔB1 (Y1) Z’ =6650+1(3)=6653

Vemos que si aumenta B1 de 950 a 951 (en 1), la FO aumenta en 3. ¿Y si aumento en 2 o más? Y1 =3 +3

+3

Z’ =

Z’ =

Al decir Base Óptima no cambia, se refiere a que X2, X3 y X4 seguirán siendo VB y que X1 seguirá siendo VNB. No hace referencia al valor de Xi.

X1 = X2 = X3 = X4 =

B1 = B2 = B3 = B4 =

+3

← Base óptima +1

Z’ =

← Base óptima

B1 = B2 = B3 = B4 =

+1 B1 = B2 = B3 = B4 =

Z’ =

← Base óptima +1

← Base óptima

B1 = B2 = B3 = B4 =

94

Esto se cumple, siempre que la ΔB1 pertenezca al intervalo permitido (-100 ≤ ΔB1 ≤ 50) para mantener la base óptima. De lo contrario, el nuevo valor de Z no podría ser hallado mediante Z’ = Z* + ΔBi (Yi).

PPL MAX

PD 0

Bi disminuir en 1

Z↑

Z↓

Bi aumentar en 1

Z↓

Z↑

Recuerda que este ejemplo es un PL de Maximización, en un PL de Minimización el nuevo valor de Z será hallado mediante Z’ = Z* - ΔBi (Yi), es decir, el Z* variará también, de acuerdo a su precio Dual (Yi) de modificar algún valor de Bi.

PPL MIN

PD 0

Bi disminuir en 1

Z↓

Z↑

Bi aumentar en 1

Z↑

Z↓

Recuerda: Esto sucede siempre y cuando ΔBi pertenezca al intervalo permisible.

95

PROPIEDADES DE LA TABLA SIMPLEX

9.1

Introducción En este capítulo conoceremos la relación que posee la tabla óptima entre sus valores. Y las posibles formas de encontrar el PL original a partir de la tabla óptima, o completar la tabla únicamente como datos el PL Original y una matriz.

96

9.2

Propiedades de una Tabla Simplex Para un PPL de la forma:

𝑴𝒂𝒙 𝑍 = 𝑪𝑋 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑨𝑋 ≤ 𝑏 𝑋≥0

A partir de la 1era iteración (No la Sbi) hasta la última tabla (óptima), cada tabla presenta la siguiente propiedad: Var. Holgura

Base Z

Z 1

X1 X2 … Xn T1=CBB-1A-C

S1 S2 … Sm T2=CBB-1

Solución T3=CBB-1b

XB

0

T4=B-1A

T5=B-1

T6=B-1b

Veamos claramente la tabla: T1=CBT1-C T1=T2A-C

EJEMPLO

Base Z

Z 1

X1 X2 … Xn T1=CBB-1A-C

S1 S2 … Sm T2=CBB-1

Solución T3=CBB-1b

XB

0

T4=B-1A

T5=B-1

T6=B-1b

Tenemos el PPL Canónico 𝑴𝒂𝒙 𝑍 = 6𝑋1 − 𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 − 𝑋2 ≤ 2 𝑋1 ≤ 3 𝑋1 , 𝑋2 ≥ 0

¿Es posible completar la tabla óptima? BASE

Z X1 S2

Z 1 0 0

X1

X2

S1

S2

1/2 -1/2

0 1

Sol.

97

La tabla nos dice que la base

a) Completaremos la tabla por propiedades.

XB = (𝑋𝑆1 ) → CB= (CX1, CS2) BASE

Z X1 S2

C=[6 −1] 𝑴𝒂𝒙 𝑍 = 𝑪𝑋 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑨𝑋 ≤ 𝒃

2

X1

2 −1 ] 1 0

X2

S1

S2

1/2 -1/2

0 1

Sol.

CB=[6 0]

𝑴𝒂𝒙 𝑍 = 6𝑋1 − 1𝑋2 +0𝑆1 + 0𝑆2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 − 𝑋2 + 𝑺𝟏 =2 𝑋1 +𝑺𝟐 = 3

𝑋≥0

A=[

Z 1 0 0

2 b=[ ] 3

𝑋1 , 𝑋2 , 𝑺𝟏 , 𝑺𝟐 ≥ 0

Dato del Problema: * De la tabla → T5=B-1=[ 𝟐 * Del PPL → A=[ 𝟏

𝟏/𝟐 −𝟏/𝟐

𝟎 ] 𝟏

−𝟏 ], C=[𝟔 𝟎

2 −𝟏], b=[ ] , CB=[𝟔 3

𝟎]

Reemplazando los datos en los T4, T3, T2, T1 y T6. 1/2 0 2 1 T6= B-1b = [ ] × [ ] → T6= [ ] −1/2 1 3 2 1/2 0 1 2 −1 T4= B-1A = [ ]×[ ]→ T4= [ −1/2 1 0 1 0 T2= CBB-1= [6 0] × [

1/2 −1/2

T3= CBB-1b = T2b = [3

0 ] → T2=[3 1

−1/2 ] 1/2

0]

2 0] × [ ]→ T3=6 3

2 −1 T1= CBB-1A-C = T2 A - C=[3 0] × [ ] − [6 −1] → T1=[0 1 0

−2]

Completamos la tabla y verificamos que sea óptima: BASE

Z X1 S2

Z 1 0 0

X1 0 1 0

X2 -2 -1/2 1/2

S1 3 1/2 -1/2

S2 0 0 1

Sol. 6 1 2

Ǝ Zj-Cj ≤ 0 No es óptimo

b) Resolvemos la tabla hasta hallar la tabla óptima. ITER.

X1 S2 ITER.

X1 X2

Z 1 0 0 1 0 0

X1 0 1 0 0 1 0

X2 -2 -1/2 1/2 0 0 1

S1 3 1/2 -1/2 1 0 -1

S2 0 0 1 4 1 2

Sol. 6 1 2 14 3 4

Zj-Cj ≥ 0 Es óptimo

Z*=14 𝑋 3 XB=[ 1 ] = [ ] 𝑋2 4 𝑆1 0 XN=[ ] = [ ] 𝑆2 0

98

EJEMPLO

¿Y si fuese al revés? Tenemos tabla óptima completa y deseamos conocer el PPL.

Z 1 0 0

Z X1 S2

X1 0 1 0

X2 0 0 1

S1 1 0 -1

S2 4 1 2

Zj-Cj ≥ 0 Entonces el PPL tiene la forma:

Sol. 14 3 4

𝑴𝒂𝒙 𝑍 = 𝑪𝑋 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑨𝑋 ≤ 𝒃 𝑋≥0 Debemos hallar A, b y C

Veamos la tabla con sus propiedades y veamos cuales son los datos que nos brinda el problema. Base Z

Z 1

X1 X2 … Xn T1=CBB-1A-C

S1 S2 … Sm T2=CBB-1

Solución T3=CBB-1b

XB

0

T4=B-1A

T5=B-1

T6=B-1b

Z X1 S2

Z 1 0 0

X1 0 T4 1 0

T1

X2 0 0 1

①Datos de la tabla: T1 =[0 0] T2 =[1 4]

T3 =14

1 T4=[ 0

3 T6=[ ] 4

0 ] 1

0 T5=[ −1

1 ] 2

S1 1 T5 0 -1

T2

S2 4 1 2

Sol. 14 T6 3 4

T3

Sabemos que un factor en común entre T1, T2, T3, T4, T5 y T6 es B-1, que de desaparecer nos daría los valores que deseamos hallar. ¿Cómo desaparecer el B-1? Sabemos que BxB-1=1 entonces hallaremos B para hallar los valores de A, b y C. -1

②Sabemos que B =T5=[ porque (B-1)-1=B B

-1

𝟎 −𝟏

𝟏 ] , hallando la matriz inversa de B-1 𝟐

Matriz identidad

0 0 −1 2

1 0

0 1

Aplicaré –F2+F1→F1

1 −1 1 −1 −1 2 0 1 Aplicaré F1+F2→F2

1 −1 0 1

1 −1 1 1 Aplicaré F2+F1→F1

1 0 0 1 Matriz identidad

2 1

−1 1 B

-1 -1

Entonces: (B ) = B

𝟐 𝟏

=[

−𝟏 ] 𝟐

99

③ Hallando A, b y C: Si T4= B-1A entonces BT4= BB-1A = A BT4= A

Si T6=B-1b entonces BT6=BB-1b = b BT6= b

BT4= [

2 −1 𝟏 ]× [ 1 2 𝟎

𝟎 ]= [2 −1] = A 1 0 𝟏

BT6= [

2 −1 ] × [𝟑]= [2] = b 𝟒 3 1 2

Si T1=CBB-1A-C entonces T1=T2A-C, despejo C= T2A- T1 T2=CBB-1 2 −1 ] − [𝟎 𝟎] = C T2A- T1= [1 4] × [ 1 2 [6 −1] = C

④Entonces con los valores hallados el PPL será:

A = [𝟐𝟏

−𝟏 2 ] , b = [ ] , C = [6 𝟎 3

−1]

→

𝑴𝒂𝒙 𝑍 = 𝑪𝑋 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑨𝑋 ≤ 𝒃 𝑋≥0

𝑴𝒂𝒙 𝑍 = 6𝑋1 − 1𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 2𝑋1 − 1𝑋2 ≤ 2 1𝑋1 ≤3 𝑋1 , 𝑋2 ≥ 0

9.3

Ejemplos 1

Dada la siguiente tabla óptima, hallar el PPL. Zj-Cj ≥ 0 Entonces el PPL tiene la forma: T1

T2

T3

T4

T5

T6

𝑴𝒂𝒙 𝑍 = 𝑪𝑋 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑨𝑋 ≤ 𝒃 𝑋≥0 Debemos hallar A, b y C

Veamos la tabla con sus propiedades y veamos cuales son los datos que nos brinda el problema. Datos de la tabla: T1 =[4 0 0]

T2 =[1 2

−0.25 T4=[ 1.5 2

0.5 −0.25 T5=[ 0 0.5 −2 1

1 0 0 1] 0 0

T3 =1350

0] 0 0] 1

100 T6=[230] 20

100

Sabemos que un factor en común entre T1, T2, T3, T4, T5 y T6 es B-1, que de desaparecer nos daría los valores que deseamos hallar. ¿Cómo desaparecer el B-1? Sabemos que BxB-1=1 entonces hallaremos B para hallar los valores de A, b y C. 0.5

-1

Sabemos que B =T5=[ 0

−2

porque (B-1)-1=B -1

B

−0.25 0.5 1

0 -1 0], hallando la matriz inversa de B 1

matriz identidad

1/2 −1/4 0 0 1/2 0 −2 1 1

1 0 0

Aplicaré (2)*F2 → F2

Aplicaré (2)*F1 → F1

1 −1/2 0 0 1/2 0 −2 1 1

2 0 0 1 0 0

1 0 0

0 0 1

Aplicaré F3 + (2)*F1 → F3

1 0 0

−1/2 1/2 0

0 0 1

2 0 0 0 2 0 4 0 1

1 −1/2 0 0 1 0 0 0 1

0 0 1 0 0 1

2 0 0 0 1 0 4 0 1

0 1 0

2 1 0 0 2 0 4 0 1

0 0 1

matriz identidad

B

𝟐 Entonces: (B ) = B = [𝟎 𝟒 -1 -1

𝟏 𝟐 𝟎

𝟎 𝟎] 𝟏

Hallando A, b y C: Si T4= B-1A entonces BT4= BB-1A = A BT4= A

2 1 0 1 2 1 −0.25 1 0 ] × [ ]= [ 2 0 1.5 0 1 3 0 2] = A 1 4 0 2 0 0 4 0 1

BT4= [0

Si T6=B-1b entonces BT6=BB-1b = b BT6= b

2 1 0 100 430 2 0] × [230]= [460] = b 20 420 4 0 1

BT6= [0

Si T1=CBB-1A-C entonces T1=T2A-C, despejo C= T2A- T1 T2=CBB-1

1 2

1

1 4

0

T2A- T1= [𝟏 𝟐 𝟎] × [3 0 2] − [𝟒 𝟎 𝟎] = C [3

2 5] = C

101

Entonces con los valores hallados el PPL será:

A=

𝟏 [𝟑𝟏

𝟐 𝟎 𝟒

𝟏 430 𝟐] , b = [460] , C = [𝟑 𝟐 𝟓] 𝟎 420

𝑴𝒂𝒙 𝑍 = 𝑪𝑋 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑨𝑋 ≤ 𝒃

→

𝑋≥0

𝑴𝒂𝒙 𝑍 = 3𝑋1 + 2𝑋2 + 5𝑋3 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 1𝑋1 + 2𝑋2 + 1𝑋3 ≤ 430 3𝑋1 + 2𝑋3 ≤ 460 1𝑋1 + 4𝑋2 ≤ 420 𝑋1 , 𝑋2 , 𝑋3 ≥ 0

2

Dada el PPL de Maximización. 𝑴𝒂𝒙 𝑍 = 3𝑋1 + 2𝑋2 + 5𝑋3 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 1𝑋1 + 2𝑋2 + 1𝑋3 ≤ 430 3𝑋1 + 2𝑋3 ≤ 460 1𝑋1 + 4𝑋2 ≤ 420 𝑋1 , 𝑋2 , 𝑋3 ≥ 0

Y se obtiene la siguiente tabla óptima

a) Completaremos la tabla por propiedades. La tabla nos dice que la base

C=[3 2 𝑴𝒂𝒙 𝑍 = 𝑪𝑋 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑨𝑋 ≤ 𝒃 𝑋≥0

1 2 1 A=[3 0 2] 1 4 0

5]

𝑋1

XB = (𝑋3) → CB= (CX1, CX3, 𝑆3

CS3)

𝑴𝒂𝒙 𝑍 = 3𝑋1 + 2𝑋2 + 5𝑋3 + 0𝑆1 + 0𝑆2 + 0𝑆3 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 1𝑋1 + 2𝑋2 + 1𝑋3 + 0𝑆1 = 430 3𝑋1 + 2𝑋3 +0𝑆2 = 460 1𝑋1 + 4𝑋2 +0𝑆3 = 420

CB=[3

5

0]

430 b=[460] 420

𝑋1 , 𝑋2 , 𝑋3 ≥ 0

102

Dato del Problema: 𝟏/𝟐 * De la tabla → T5=B-1=[ 𝟎 −𝟐

−𝟏/𝟒 𝟏/𝟐 𝟏

𝟎 𝟎] 𝟏

1 2 1 430 2], C=[3 2 5], b=[460] , CB=[3 5 0] 1 4 0 420

* Del PPL → A=[3 0

Reemplazando los datos en los T4, T3, T2, T1 y T6. 1/2 −1/4 0 430 100 T6= B-1b = [ 0 1/2 0] × [460] → T6= [230] 420 20 −2 1 1 1/2 −1/4 0 1 T 4= B A = [ 0 1/2 0] × [3 1 −2 1 1 -1

T2= CBB-1= [6 5

−1/2 2 1 0 2]→ T4= [ 1/2 4 0 2

1/2 −1/4 0 0] × [ 0 1/2 0] → T2=[1 2 −2 1 1

T3= CBB-1b = T2b = [1

1 0 0 10] 0 0

0]

430 2 0] × [460]→ T3=1350 420

T1= CBB-1A-C = T2 A - C=[1 2

1 2 0] × [3 0 1 4

1 2] − [3 0

2 5] → T1=[4

0 0]

Completamos la tabla y verificamos que sea óptima: ∀ Zj-Cj ≥ 0 Es óptimo

Z*=1350 𝑋1 3 XB=[𝑋3 ] = [ ] 4 𝑋3 𝑋2 0 XN=[ 𝑆1 ] = [ ] 0 𝑆2

9.4

Ejercicios PPL Canónico

𝑴𝒂𝒙 𝑍 − 200𝑋1 − 300𝑋2 = 0 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 4𝑋1 + 4𝑋2 ≤ 36 3𝑋1 + 6𝑋2 ≤ 48 𝑋𝑖 ≥ 0

𝑖 = 1,2

Cuya Sol. Óptima origina la siguiente tabla: 2 iter.

X1 X2

Z 1 0 0

X1

X2

S1

S2

1/2 -1/4

-1/3 1/3

Sol.

Se pide completar la tabla por propiedades.

103

Forma Canónica:

Cuya Sol. Óptima origina la siguiente tabla:

𝑴𝒊𝒏 𝑍 = 𝑋1 − 2𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 −𝑋1 + 𝑋2 ≤ 2 𝑋1 + 𝑋2 ≤ 5 𝑋𝑖 ≥ 0

Se pide completar la tabla por propiedades.

𝑖 = 1,2

Forma Canónica:

Cuya Sol. Óptima origina la siguiente tabla: Z X1 X2 S1 S2 Sol. 1ERA 1 ITER. X2 0 1 0 S2 0 1 1

𝑴𝒂𝒙 𝑍 = 𝑋1 + 2𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 −2𝑋1 + 𝑋2 ≤ 7 𝑋1 − 𝑋2 ≤ 2 𝑋𝑖 ≥ 0

Se pide completar la tabla por propiedades.

𝑖 = 1,2

Forma Canónica:

Cuya Sol. Óptima origina la siguiente tabla:

𝑴𝒂𝒙 𝑍 = 15𝑋1 + 30𝑋2 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 4𝑋1 + 𝑋2 ≤ 36 𝑋1 + 2𝑋2 ≤ 30 𝑋𝑖 ≥ 0

1ERA ITER.

S1 X2

Z 1 0 0

X1

X2

S1

S2

1 0

-1/2 1/2

Sol.

Se pide completar la tabla por propiedades.

𝑖 = 1,2

Dada la siguiente Tabla Óptima, hallar el PPL original. 2DA ITER.

X1 X2

Z 1 0 0

X1 0 1 0

X2 0 0 1

S1 0 -1/2 -3/2

S2 2 1/2 1/2

Sol. 12 5/2 3/2

Dada la siguiente Tabla Óptima, hallar el PPL original. 2DA ITER.

X1 X2

Z 1 0 0

X1 0 1 0

X2 0 0 1

S1 1 0 -1

S2 4 1 2

Sol. 14 3 4

Dada la siguiente Tabla Óptima, hallar el PPL original. 2DA ITER.

X1 X2

Z 1 0 0

X1 0 1 0

X2 0 0 1

S1 0 2/7 -1/7

S2 15 -1/7 4/7

Sol. 450 6 12

104

OPTIMIZACIÓN: MÉTODO TRANSPORTE

10.1 Definición El problema clásico de transporte se presenta cuando se debe determinar un programa óptimo de envíos que: a) Se originan en fuentes (centros de distribución) donde se tienen disponibilidades de un bien. b) Son enviados directamente a sus destinos finales (centros de demanda) donde se requieren varias cantidades fijas. c) Cumplen que la demanda total sea igual a la oferta total d) El costo satisface una función objetivo lineal. O sea, el costo de cada embarque es proporcional a la cantidad embarcada y el costo total es la suma de los costos individuales

105

El modelo de transporte puede ser usado en otras áreas, por ejemplo el control de inventarios u horario de empleos, etc. Costo de enviar una unidad desde el i-ésimo origen hasta el j-ésimo destino.

Cantidad que deben ser enviadas del origen i al destino j

Destino

Origen Cantidad disponible en el origen 1.

1

a2

2

ai

i

C11X11

a1

CijXij

1

b1

2

b2

j

bi

Cantidad requerida en el destino 1.

Número de orígenes.

Número de destinos.

am

n

m

Oferta Disponibilidad

bm

Demanda Requerimiento

Para contemplar todos los elementos involucrados en el problema, se acostumbra hacer una tabla llamada TABLA DE TRANSPORTE, en la siguiente forma: DESTINO

1 1 Cantidad que deben ser enviadas del origen i al destino j

ORIGEN

2 … i m

DEMANDA

2

C11

C12

X11

X12

C21

C22

X21

X22

…

…

…

…

Ci1

Ci2

Xi1

Xi2

Cm1

Cm2

…

j

…

n

C1j

…

X1j

…

C2j

…

X2j

…

…

…

…

…

Cij

…

Xij

…

Cmj

C1n X1n C2n X2n … … Cin Xin Cmn

Xm1

Xm2

…

Xmj

Xmn

b1

b2

…

bj

bn

OFERTA a1 a2 …

Costo de enviar una unidad desde el i-ésimo origen hasta el j-ésimo destino.

ai am ∑ 𝑏𝑖 ∑ 𝑎𝑗 ∑ 𝑏𝑖 ∑ 𝑎𝑗

Por tanto el modelo matemático del problema de transporte es: Encontrar Xij tales que: 𝑚 𝑛

𝑴𝒊𝒏 𝑍 = ∑ ∑ 𝐶𝑖𝑗 𝑋𝑖𝑗 𝑖=1 𝑗=1

𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑛

Por disponibilidades/Oferta

∑ 𝑋𝑖𝑗 = 𝑎𝑖 𝑖 = 1,2, … , 𝑚 … ① 𝑗=1 𝑚

Por requerimientos/Demanda

∑ 𝑋𝑖𝑗 = 𝑏𝑗 𝑗 = 1,2, … , 𝑛… ② 𝑖=1

𝑋𝑖𝑗 ≥ 0 ∀ 𝑖, 𝑗

106

Según el sistema de restricciones, para que el problema tenga solución factible se tiene que la suma de las ecuaciones ① debe ser igual a la suma de las ecuaciones ②: ∑ 𝑎𝑖 = ∑ 𝑏𝑗 𝑖

𝑗

Oferta = Demanda El problema de transporte también se puede resolver por el Simplex, por su forma tiene su propio método solución. PROCEDIMIENTO INICIAL Antes de aplicar algún método de Transporte, se halla la Solución Básica Inicial (lo que en el Simplex es la 1ra tabla llamada también Sbi). Para esto hay varios métodos de solución: ֍ Método de la esquina nor-oeste (N – O) ֍ Método de la Costos Mínimos. ֍ Método de Vogel. ֍ Método de Russell. Después de hallar la Solución Básica Inicial (Sbi) ya podemos aplicar el método propio de transporte (Método UV).

10.2 Propiedades Teorema 1.- El problema de transporte tiene una solución posible. Teorema 2.- Una base para el problema de transporte consiste de m+n-1 vectores linealmente independientes (#origen + #destinos -1 restricciones). ¿Teorema 2? El departamento de transporte de una compañía tiene el problema de distribuir su producto de sus dos plantas de producción a sus tres almacenes, las producciones mensuales de las plantas son conocidas, al igual que los requerimientos de los almacenes, además se conoce el costo unitario de embarque de cada planta a cada almacén. El problema es determinar qué plantas deben abastecer a qué almacenes de manera que se minimicen los costos totales de transporte.

Debe observarse en este sistema que cualquiera de las restricciones se puede expresar como una combinación de las otras, Por ejemplo la restricción 2 es igual a la suma de las restricciones 3, 4 y 5, menos la restricción 1, esto es:

Por lo tanto, al resolver el problema de programación lineal sólo se considerarán 4 restricciones de las 5, eliminando cualquiera de ellas. El problema corresponde a uno de Programación Lineal. Sea Xij el número de unidades de producto que se envíande la planta i al almacén j. Dado que para este problema el total de disponibilidades es igual al total de requerimientos, aparecerán igualdades en las restricciones. El problema consiste en:

El problema de transporte con m puntos de origen y n puntos de destino tiene m + n ecuaciones de restricción. Pero, dado que siempre está equilibrado (suma de la oferta es igual a la suma de la demanda), una de las ecuaciones debe ser redundante. Así, el modelo tiene m + n - 1 ecuaciones de restricción independientes, lo que significa que la solución básica inicial tiene m + n – 1 variables básicas.

107

10.3 Sbi: Método Esquina N-O 1. Comenzando desde la esquina noroeste de las celdas disponibles (al inicio, la celda correspondiente a X11). Realizar la mayor asignación posible dentro de los límites de la oferta y demanda: X11 = min (a1, b1) 2. Ajuste las cantidades asociadas de Oferta y Demanda restando la cantidad asignada. 3. Marcar la columna o fila cuya oferta o demanda haya sido satisfecha, y volver al paso 1 hasta que todas las asignaciones hayan sido realizadas. Puede haber dos casos: i) a1b1 → a’1 = a1–b1 (nos movemos horizontalmente)

X11 = b1 y pasamos a la celda (1,2) donde X12 = min (a’1, b2)

Así se continúa hasta obtener la solución factible básica inicial. RESUMEN ֍ Chequear oferta = demanda ֍ Asignar lo máximo posible (unidades) a la esquina nor-oeste del cuadro de envíos que quede.

Habiendo halla la Solución Básica Inicial (Sbi), ya podemos hallar la solución óptima mediante el Método UV.

10.4 Sol. Óptima: Método UV

También llamado Método de Distribución Modificada (MODI). El método consiste en asignar a cada una de las restricciones su variable dual, correspondiendo una variable dual a cada columna y a cada fila en la tabla de transporte, teniendo un conjunto de m+n variables duales, de las cuales m+n-1 son independientes y una es redundante. Los pasos a seguir son: 1.-Determinación de una solución inicial básica factible (Método N-O) 2.-Prueba de la solución respecto de la condición de optimalidad. 3.-Mejora de la solución cuando no es óptima. 4.-Repetir los pasos 2 y 3 hasta obtener solución óptima

108

Veamos un ejemplo el procedimiento con un ejemplo. Partiremos hallando la Sbi para luego aplicar el Método UV.

EJEMPLO

Una empresa distribuidora desea establecer un plano de distribución de una misma clase de productos desde sus 3 almacenes para sus 4 clientes. Los datos sobre costos de transporte por unidad de producto, las demandas y las ofertas son dados en la siguiente tabla.

Formulando el problema de otro modo: Cantidad por enviar

Costo de envío.

Cliente

Almacén 700

1

800 400 Oferta

10X11

1

500

2

2

300

3

3 4

500 600 Demanda

PASO 1

Aplicamos el Método Nor-Oeste. Obtendremos la Matriz Cij Solución Básica Inicial

109

PASO 2

Considerando la Solución Inicial hallada por el método N-O Aplicamos el Método UV (o MODI) para hallar la solución óptima.

Iniciamos la 1era iteración.Planteamos la Matriz de Costos (Zij), vemos si es óptima, y de acuerdo a ello iteramos. ①Planteamos la Matriz de Costos Zij

Para construir el conjunto ui y vj. Se construye un conjunto de número ui y vj tal que la suma será igual a los valores de la matriz Zij (del paso 1).

Iniciamos arbitrariamente con V1=0. (Ó se podría iniciar con U1 = 0)

Primero, las celdas básicas (sombreadas): V1 = 0 y Z11=10, como V1 + U1 = 10 entonces U1=10 y Z12=11, como U1 + V2 = 11 entonces V2=1 y Z22=9 , como U2 + V2 = 9 entonces U2 = 8 y Z23=12, como U2 + V3 = 12 entonces V3 =4 y Z24=10, como U2 + V4 = 10 entonces V4 =2 y Z33=12, como U3 + V4 = 13 entonces

U1=10 V2=1 U2 = 8 V3 =4 V4 =2 U3 =11

Dato del paso 1

Ya hallados todos los valores de ui y vj se completa las celdas vacías con la suma de los ui y vj en la matriz Zij que contiene los costos de la variable solución. Iniciamos con V1=0 y solo trabajo en los recuadros sombreados. Luego completamos con Zij = ui + vj

La Base Posible (Inicial) se verifica que no es óptima.

②Hallo F.O.: Z = Cij - Zij

En toda base posible las VB deben tener coeficiente cero en la F.O. CONDICIÓN DE OPTIMALIDAD.- Cij – Zij>0 Verifico que no haya valores < 0 ¡SI LO HAY!  → Habrá que iterar.

110

①Variable de Entrada: VE=Min {(Cij-Zij)/ CijZij0 Verifico que no haya valores < 0 ¡SI LO HAY!  → Habrá otra iteración.

111

③Nueva base posible. Ubico la Variable de Entrada y Salida:

¿Y si la oferta ≠ Demanda? Iniciamos la 3cera iteración.- Repito los pasos 1,2 y3 Planteamos la Matriz de Costos (Zij), evaluamos su Optimalidad y de acuerdo a ello iteramos. ①Planteamos la Matriz de Costos Zij y construyo los ui y vj.

②Hallo F.O.: Z = Cij - Zij

CONDICIÓN DE OPTIMALIDAD.- Cij – Zij>0 Verifico que no haya valores < 0 ¡SI LO HAY!  → Habrá otra iteración.

③Nueva base posible. Ubico la Variable de Entrada y Salida:

112

Iniciamos la 4ta iteración.- Repito los pasos 1,2 y3 Planteamos la Matriz de Costos (Zij), evaluamos su optimalidad y de acuerdo a ello iteramos. ①Planteamos la Matriz de Costos Zij y construyo los ui y vj.

LA BASE POSIBLE SE VERIFICA QUE SÍ ES ÓPTIMA. 

②Hallo F.O.: Z = Cij - Zij

CONDICIÓN DE OPTIMALIDAD.- Cij – Zij>0 ¡TODOS SON POSITIVOS! 

Encontramos la Sol. Óptima.

Ya no desarrollo el paso 3 porque ya es óptima la base. Entonces la Solución Óptima será la nueva base posible de la iteración 3.

Entonces la cantidad a distribuir desde un almacén a un cliente será:

113

Con el costo mínimo de: CT = 500*10+200*11+200*9+600*10+300*11+100*10 CT = 19300

EJEMPLO

Supongamos que una empresa productora de barras de pan tiene dos almacenes A1 y A2 desde los cuales debe enviar pan a tres panaderías P1, P2 y P3. Las ofertas, las demandas y los costes de envío se dan en el siguiente grafo.

P1

1500

P2

2000

P3

1000

8 2000

A1

6 10 10

2500

A2

4 9

Formulando el problema de otro modo:

PASO 1

Aplicamos el Método Nor-Oeste. Obtendremos la Matriz Cij

114

PASO 2

Considerando la Solución Inicial hallada por el método N-O Aplicamos el Método UV (o MODI) para hallar la solución óptima.

Iniciamos la 1era iteración.①Planteamos la Matriz de Costos Zij y construyo los ui y vj. Iniciamos con V1=0 y solo trabajo en los recuadros sombreados.

Luego completamos con Zij = ui + vj

②Hallo F.O.: Z = Cij - Zij

CONDICIÓN DE OPTIMALIDAD.- Cij – Zij>0 Verifico que no haya valores < 0 ¡SI LO HAY!  → Habrá otra iteración.

③Nueva base posible. Ubico la Variable de Entrada y Salida:

Iniciamos la 2da iteración.①Planteamos la Matriz de Costos Zij y construyo los ui y vj.

115

②Hallo F.O.: Z = Cij - Zij

CONDICIÓN DE OPTIMALIDAD.- Cij – Zij>0 ¡TODOS SON POSITIVOS! 

Encontramos la Sol. Óptima.

Ya no desarrollo el paso 3 porque ya es óptima la base. Entonces la Solución Óptima será la nueva base posible de la iteración 1.

Entonces la cantidad a distribuir desde un almacén a un cliente será:

Con el costo mínimo de: CT = 500*8+500*10+2000*4+500*9 CT = 21500

116

10.5 Caso: Oferta ≠ Demanda

Hasta ahora hemos tratado casos en los que el problema está balanceado, es decir, la Oferta es igual a la Demanda. ¿Pero si no lo fuese? Existen dos casos: Oferta > Demanda

Agregar Destino ficticio n+1

Costo Ci, n+1=Más Alto

Oferta < Demanda

Agregar Origen ficticio m+1

Costo Cm+1,j=Más alto

Veamos algunos casos de planteamiento: ¡Siempre aumentar!

50

45

Cuando la oferta es mayor a la demanda

50 Agrego Destino ficticio n+1=4+1=5 para igualar Oferta = Demanda.

50

40

50

40

50

Cuando la oferta es menor a la demanda

Agrego Origen ficticio n+1=3+1=4 para igualar Oferta = Demanda.

Recuerda: Al hallar la solución Óptima y tener una cantidad a enviar al destino ficticio 5, estás no serán enviadas. Equivalen a dejarlas en el almacén.

Al hallar la solución Óptima y tener una cantidad a enviar por parte del almacén ficticio 4, estás no serán enviadas.

117

EJEMPLO

Tenemos el siguiente planteamiento:

Verifiquemos si esta balanceado. ¡Costo de envío arbitrario ALTO!

90

La oferta es mayor a la demanda

80 90

90 Agrego Destino ficticio n+1=3+1=4 para igualar Oferta = Demanda.

Ya podemos resolver el problema:

PASO 1

Aplicamos el Método Nor-Oeste. Obtendremos la Matriz Cij

CT = 20*10+10*12+20*8+10*12+20*10+10*10 = 900

118

PASO 2

Considerando la Solución Inicial hallada por el método N-O Aplicamos el Método UV (o MODI) para hallar la solución óptima.

Iniciamos la 1era iteración. ①Planteamos la Matriz de Costos Zij y construyo los ui y vj.

②Hallo F.O.: Z = Cij - Zij

CONDICIÓN DE OPTIMALIDAD. - Cij – Zij>0 Verifico que no haya valores < 0 ¡SI LO HAY!  → Habrá otra iteración.

③Nueva base posible. Ubico la Variable de Entrada y Salida:

Iniciamos la 2da iteración. ①Planteamos la Matriz de Costos Zij y construyo los ui y vj.

119

②Hallo F.O.: Z = Cij - Zij

CONDICIÓN DE OPTIMALIDAD.- Cij – Zij>0 Verifico que no haya valores < 0 ¡SI LO HAY!  → Habrá otra iteración.

③Nueva base posible. Ubico la Variable de Entrada y Salida:

Iniciamos la 3cera iteración. ①Planteamos la Matriz de Costos Zij y construyo los ui y vj.

②Hallo F.O.: Z = Cij - Zij

CONDICIÓN DE OPTIMALIDAD. - Cij – Zij>0 ¡TODOS SON POSITIVOS! 

Encontramos la Sol. Óptima.

120

Ya no desarrollo el paso 3 porque ya es óptima la base. Entonces la Solución Óptima será la nueva base posible de la iteración 2.

F es un destino Ficticio, por ende, la cantidad 10 que supuestamente deberá ser enviada al destino F del almacén C, no será enviada. Equivale decir, que 10 productos de dejarán en el almacén C.

Entonces la cantidad a distribuir desde un almacén a un cliente será:

Dejando 10 productos en el almacén C sin enviar. Con el costo mínimo de: CT = 30*8+30*8+20*8 CT = 640

10.6 Sbi: Método Costos Mínimos.

Procedimiento: 1. Elija la celda disponible con el menor costo de toda la tabla, y realice la asignación máxima permitida por las restricciones de oferta y demanda. 2. Ajuste las cantidades asociadas de Oferta y Demanda restando la cantidad asignada. 3. Marcar la columna o fila cuya oferta o demanda haya sido satisfecha, y volver al paso 1 hasta que todas las asignaciones hayan sido realizadas.

EJEMPLO

Halla la Solución Básica Inicial del siguiente problema:

∑ 𝑎𝑖 = ∑ 𝑏𝑗 =275

121

Situando la solución en la tabla: ¡Siempre actualizar oferta y demanda! ④Las celdas que quedan se llenan automáticamente: Min (50,90) =50, Min (40,25) = 25, Min (15,15) =15

②Elegimos el siguiente menor costo (14) y hallamos la asignación máxima: min (115, 60) = 60

①Elegimos el menor costo (12) y hallamos la asignación máxima: min (70, 95) = 70

③Elegimos el siguiente menor costo (15) y hallamos la asignación máxima. En este caso elegimos arbitrariamente entre las 3 opciones. Min (55,70) =55

El costo de esta solución es: CT = 12x70 + 15x50 + 26x15 + 25x25 +14x60 + 15x55 CT = 4270 La solución encontrada por el método del Costo Mínimo está más cerca al óptimo que la solución que puede ser encontrada por el Método Esquina Nor-Oeste.

10.7 Sbi: Método de Aproximación de Voguel. Existe otro método para lograr hallar una Sbi, es el método de Aproximación de Voguel, cuyo procedimiento es el siguiente: 1. Para cada fila. Ubique las celdas con los dos menores costos de entre las disponibles. Halle la diferencia entre estos costos (penalidad) y escriba el resultado al lado del valor de Suministros para esa fila.

122

2. Para cada columna. Realice la misma operación, la penalidad irá al lado del valor de Requisitos para la columna. 3. Elija la fila ó columna que tenga la mayor penalidad asociada. 4. De la fila ó columna elegida, elija la celda con el menor costo y realice la asignación máxima permitida por las restricciones de oferta y demanda. 5. Ajuste las cantidades asociadas de Oferta y Demanda restando la cantidad asignada. 6. Marcar la columna o fila cuya oferta o demanda haya sido satisfecha, y volver al paso 1 hasta que todas las asignaciones hayan sido realizadas.

¿Penalización? El valor de penalización refleja el costo extra (ó ganancia perdida) que resultaría el realizar una asignación en la casilla de costo superior a la actualmente disponible para la fila o columna. Penalización

Penalización Por ejemplo, en la tabla. Para la fila 2, la celda de costo menor corresponde a (2,1) y la celda de costo inmediato superior es (2,2). La penalización de la fila 2 = 40 nos dice que por cada unidad que no es asignada a (2,1) sino a (2,2) tendremos un costo extra de 40. Al ser la mayor penalización para la tabla, estamos seguros que es la que menos conviene pagar, y por lo tanto se realiza la asignación en la celda de menor costo para esa fila/columna.

EJEMPLO

Halla la Solución Básica Inicial del siguiente problema:

∑ 𝑎𝑖 = ∑ 𝑏𝑗 =275

Situando la solución en la tabla: ①Hallo la Penalidad: Ubico los dos menores costos por fila y columna, y resto. 𝑃𝑒𝑛𝑎𝑙𝑖𝑑𝑎𝑑

123 𝑃𝑒𝑛𝑎𝑙𝑖𝑑𝑎𝑑

②Entre todos los valores de las penalidades, comparo y elijo la MAYOR, de esta fila o columna elegida, elijo el MENOR costo. Observamos que existen dos penalidades iguales de la fila 2 y columna2. Elegimos la columna 2 y elegimos la celda que contiene el menor costo (14); luego introducimos la base.

Elegimos la mayor penalidad arbitrariamente (6-columna 2) y asignamos al menor costo (14): Min (115,60) = 60

Se elimina la columna 2 (Ya no trabajamos con dicha columna). ③Hallo la nueva penalidad:

¡Siempre actualizar oferta y demanda!

④Elijo la mayor penalidad y asigno al menor costo:

Elegimos la mayor penalidad (10 -fila 2) y asignamos al menor costo (15): Min (90,50) = 50

⑤Hallo la nueva penalidad:

124

Como 5 es la mayor penalidad y está en la columna 4, buscamos en esta columna el menor costo (12) y hacemos la asignación.

⑦Hallo la nueva penalidad:

⑥Elijo la mayor penalidad y asigno al menor costo:

Elegimos la mayor penalidad (5 -columna 4) y asignamos al menor costo (15): Min (70,95) = 70

⑧Elijo la mayor penalidad y asigno al menor costo:

⑨Hallo la nueva penalidad:

Elegimos la mayor penalidad (11 -columna 3) y asignamos al menor costo (15): Min (70,55) = 55

⑩Elijo la mayor penalidad y asigno al menor costo:

Finalmente asigno el Min (40,1) = 15 y el Min (25,25) =25.

125

Entonces, tenemos lo siguiente:

El costo de esta solución básica inicial es: CT= 12x70 + 15x50 +26x15+25x25+14x60+15x55 CT= 840 + 750 + 390 + 625 + 840 + 825 CT = 4270

10.8 Ejercicios

Ejercicio 3

Ejercicio 4

126

Ejercicio 5

Ejercicio 6

Ejercicio 7

Ejercicio 8

Ejercicio 9

Ejercicio 10

127