1

Unidad 2 Programación Lineal (Método Simplex) Competencia: el estudiante debe recordar la resolución de sistemas de inecuaciones de manera algebraica como gráfica, para aplicar correctamente en la resolución de modelos de programación lineal y en el análisis de sensibilidad de los mismos para posteriormente utilizar diferentes métodos de solución como el simples. Descripción general de la unidad.- La unidad comienza con un repaso sobre la solución de sistemas de inecuaciones de manera algebraica como gráfica posteriormente plantear, construir modelos de programación lineal con dos variables utilizando técnicas algebraicas como algoritmos como el método simplex. Introducción.La programación lineal se utiliza en modelos de optimización, donde tanto las funciones objetivos como las restricciones son lineales. Esta técnica tiene mucha aplicación en el campo de la industria, transporte, economía, salud, logística militar. La programación Lineal constituye la base fundamental para la formulación de algoritmos, programación entera, estocástica y no lineal.. Modelos de programación simples (con dos variables) Solución algebraica.Aunque en la práctica no se presenta con mucha asiduidad, nos permite tener una visión global sobre la solución de los modelos en forma completa y general. Ej. Una CIA. de pinturas para exteriores y para interiores(M1 y M2) de acuerdo a la siguiente información: Especificaciones Materia Prima

Ton de materia prima de Disponibilidad Diara Máxima (Ton) Pinturas ext. Pinturas int

Materia Prima M1

6

4

24

Materia Prima M2

1

2

6

Utilidad (miles/Ton.)

5

4

Una encuesta de mercado indica que la demanda diaria de pinturas para interiores no puede ser mayor que 1 ton. que la de pintura para exteriores. También que la demanda máxima diaria de pinturas para interiores es de 2 ton. La CIA. desea determinar la mezcla óptima (la mejor de productos para exteriores e interiores de manera de maximizar la UTILIDAD total diaria. De acuerdo a las etapas de la construcción del modelo tenemos: Sol.-Definición o planteamiento del problema 1) Alternativas y/o variables de decisión : X1 : Producción diaria de pinturas para exteriores en toneladas X2 : Producción diaria de pinturas para interiores en toneladas M2→ 2) Función Utilidad Z= 5 X1 + 4 X2 Función Objetivo :Maximizar la Utilidad Z* =5 X1 + 4 X2

2

3) Restricciones o limitaciones: a) De Disponibilidad: Explicativas

Materia Prima M1 → 6 X1 + 4X2 ≤ 24 (ton) Materia Prima M2 →

b) De mercado:

X1 +2X2 ≤ 6 (ton)

X2≤ X1 + 1→ - X1 + X2 ≤ 1 (ton) X2 ≤ 2 (ton)

Implícitas c) Condición de no negatividad: X1 , X2 ≥ 0

Construcción del modelo: Maximizar Z=5 X1 + 4 X2

→ Z* =5 X1 + 4 X2

Sujeto a las restricciones: 1)

→ 6 X1 + 4X2 ≤ 24

2)

→

X1 +2X2 ≤ 6

3)

→ - X1 + X2 ≤ 1

4)

→

5)

→

X2 ≤ 2 X1 , X2 ≥ 0.

El modelo tiene solución factible si para cualquier valor de X1 , X2 satisface todas las restricciones del modelo, y permitirá determinar la solución óptima. A partir de la estructura del modelo se podrá utilizar cualquier técnica de optimización como ser la gráfica, la algebraica, la simplex etc. Solución gráfica.- Se sugiere realizar dos pasos: 1) Determinación del espacio factible de soluciones: se deberá determinar la figura geométrica utilizando todas las restricciones, para ello se deberá determinar las líneas que determinen el espacio factible de solución:

3

Obteniendo las rectas de las restricciones: 1)→ 6 X1 + 4X2 ≤ 24 ; 2) → X1 +2X2 ≤ 6 ;3)→ - X1 + X2 ≤ 1 ; 4) → X2 ≤ 2

X2

5

0

6

0

3

0

1

4

0

6

0

-1

0

→

6 El espacio de soluciones está determinado 5

por la figura geométrica del trapecio deter-

1

↓

minado por los puntos ABCDEF dentro este

4

espacio existen una infinidad de soluciones 3 2

3

4

2

E

↓

D

→ 1 F

C ←

Espacio de soluciones

A 0

↓ ↑

1

↑ B

2

3

6

4

5

6

X1

2.-Determinación de la solución óptima.- Las soluciones óptimas están determinados por todas las esquinas o puntas, para determinar específicamente cual esquina es la adecuada se asignan valores arbitrarios crecientes al valor de Z por que la función objetivo es maximizar(,si se trata de minimizar se dan valores decrecientes),para determinar la dirección de la recta de la función objetivo de manera que toque uno de las esquinas o, puntas o vértices de la figura, en este caso se da dos valores Z= 10 y Z=15 por lo tanto se deben graficar las rectas de la función Z: =5 X1 + 4 X2 =10 Z= 5 X1 + 4 X2 =15

4

X2

6 5 4 3 2

E

↓

D

→

1.5 1 F

©

Espacio de soluciones

A 0

↓

←

↑ 1

B 2

3

4

→

5

6

X1

→

Z=10

Z= 15

Z= 21

Solución algebraica .Para determinar analíticamente el punto solución óptima se debe resolver el sistema de ecs. de las dos rectas de todas las puntas o intersecciones, en este caso en el punto C Se debe resolver el sistema de ecs de la 1ª restricción 2 restricción

6 X1 + 4X2 ≤ 24 → X1 = 3 X1 +2X2 ≤ 6

→ X2 = 1.5

Problema de minimización Al igual que en el caso de maximización, en los modelos de minimización se deben determinar las alternativas y/ o variables, la función objetivo y las restricciones, para determinar la recta de la solución óptima en forma gráfica se debe proponer valores decrecientes para determinar la dirección de la recta “z” Ejemplo.- En una granja se usa diariamente un mínimo de 800 lbs de un alimento especial que es una mezcla de maíz y soya con las siguientes características: Especificaciones

Libras /lb de alimento

Costo $ /lb

Alimento

Proteínas Fibras

Maíz

0.09

0.02

0.30

Soya

0.60

0.06

0.90

5

Las necesidades dietéticas del alimento especial son un mínimo de 30% de proteínas y un máximo de 5% de fibras. La granja desea determinar las proporciones de alimento que produzcan un costo diario MINIMO. Solución gráfica y algebraica.Solución.Determinación de las variables: X1 : lbs de maíz en la mezcla diaria X2 :lbs de soya en la mezcla diaria Determinación de la función costo Z= 0.30 X1 + 0.90 X2 Función objetivo Minimizar Z → Z* = 0.30 X1 + 0.90 X2 Determinación de las restricciones a)De disponibilidad

≥ 800

X1 + X2

b)De dieta o composición.0.09 X1 +0.60 X2 ≥ 0.30( X1 + X2) →0.21 X1 -0.30 X2 ≤ 0 0.02 X1 + 0.06 X2 ≤ 0.05 (X1 + X2) → 0.03 X1 -0.01 X2 ≥ 0 c) Implícitas:

X1, X2

≥ 0

Cuya solución gráfica está dado Por: X2 1500 →

B →

↓

←D

Mín Z = 0.3x1+0.9x2

Espacio de soluciòn 1000

factible ↑ A

500

↑©

Soluciòn òptima X1 = 470.6 lb. X2= 329.4lb Z= $437.64

↑ 0

500

1000

1500

X1

ANÀLISIS DE SENSIBILIDAD.En la etapa de la solución del modelo se sugiere realizar el análisis de sensibilidad que permita obtener información adicional sobre el comportamiento de la solución óptima como efecto de ciertos cambios en los valores de los parámetros del modelo, para aumentar la aplicación de la programación lineal en la práctica para hacerla más dinámica. El análisis de sensibilidad generalmente se lo hace en cambios en: a) Los coeficientes de la función objetivo ,b)Los valores de las restricciones. 6

1.-Cambios en los coeficientes de la función objetivo De manera general la función objetivo se la expresa: Maximizar o minimizar → Z = C1 X1 + C2 X2 ; donde los cambios en los coeficientes C1 , C2 lógicamente harán cambiar la valoración y la pendiente Z y posiblemente el punto solución .sin embargo hay un intervalo de variación tanto para C1 como C2 ,dentro el cual el punto óptimo permanece sin cambiar, por lo tanto se necesita determinar: Intervalos de optimabilidad

(IO) para C1 , C2

Para determinar dichos intervalos es necesario utilizar las relaciones: C1 / C2 para el coeficiente de la variable X1, dado el valor C2 =constante, C2 ≠0(para evitar que la pendiente Z no sea vertical) C2 / C1 para el coeficiente de la variable X2 dado el valor C1 =constante C1 ≠0(para evitar que la pendiente Z no sea horizontal). En forma general: el IO para Ci = Valor Mìn ≤ Ci / Cj ≤ Valor màx ; con Ci≠0 ; Cj ≠0 ,para evita que la pendiente Z sea paralela a uno de los ejes del sistema.,donde las condicionante Cj se mantienen constante mientras que el otro cambia. Siguiendo con la información del modelo de la Cìa de pinturas ,se pide hallar los IO . Sol.- De acuerdo a las restricciones del modelo tenemos: 1) 6 X1 + 4X2 ≤ 24 → 4 / 6 ≤ C2 / C1 ≤ 2 / 1; con C1 =5→ 10 / 3 ≤ C2 ≤ 10 con C1 ≠0 Significa que si C1 =5 el valor de X1 puede variar desde 2 hasta 6 sin cambiar la solución óptima 2)

X1 +2X2 ≤ 6 → 1 / 2 ≤ C1 / C2 ≤ 6 / 4; con C2 =4→2≤ C1. ≤6 con C2 ≠0

Significa que si C2 = 4 el valor de X2 puede variar desde 10/3 hasta 10 sin cambiar la solución óptima Nota.1.-Cuando Ci≠0 ; Cj ≠0 los IO deben dividirse en dos conjuntos en los que los denominadores no deben ser ceros 2.-Mientras que los valores de los parámetros de la función objetivo estén comprendidos en los IO la solución óptima se mantiene, en éste caso en el punto C 2.-Cambios en las restricciones Cuando se plantean las restricciones en los modelos se suponen que los recursos son limitados en forma explícita o implícita donde la parte derecha de las restricciones representan los límites de disponibilidad de los recursos, Por lo tanto el análisis de sensibilidad se hará también a través de la variación de los recursos disponibles, teniendo presente que se hará manteniendo los otros recursos constantes y obteniendo los: Intervalos de factibilidad (IF) para Mi.- los mismos que en forma general: IF Mi = Valor Mìn ≤ Mi / Mj ≤ Valor màx ; donde los Mj = constante, para ello se debe recurrir a la solución de las restricciones en función de las Mi. Siguiendo con la información de la Cìa de las pinturas y resolviendo el sistema de inecuaciones de las restricciones tenemos: El IF para M1→ 20 ≤ M1 ≤ 36 ; y el IF para M2→ 4≤ M2 ≤ 20 / 3 7

Valor por unidad de cambio.-Los modelos de programación lineal se pueden resumir como un modelo de entrada y salida(in-put-out put) es decir entrada de datos y salida de resultados mediante el proceso o actividades del modelo de programación lineal, cuya representación gráfica. Recursos del modelo

Proceso Actividades del modelo

Valor objetivo del modelo Z

De acuerdo a este esquema resulta determinar como los cambios de los datos o recursos pueden influir sobre el resultado, es decir determinar: El valor por unidad de un recurso el mismo que se define como la tasa de cambio en Z debido a los cambios en la cantidad de los recursos, el mismo que se calcula. yi = Δ Zi* / LIOi donde . yi= Valor de cada unidad del i-esimo recurso Δ Zi*= cambio en función objetivo LIOi =longitud del intervalo de optimalidad del i-èsimo recurso Siguiendo con nuestro ej, se pide determinar los cambios o tasas de los recursos M1 y M2 Para Z1 → 5(2) + 4(2) = 18( Miles de $us); Para Z2 → 5(6) + 4(0) = 30(Miles de $us) → Δ Y1 = (30-18)=12 ; LIO1 = (36-20) =16 → Y1= 12/ 16 = 0.75(miles de $us/ton de M1 ) Esto quiere decir que un cambio de 1 tonelada en M1 ,dentro el intervalo 20 ≤ M1≤ 36 harà cambiar el valor òptimo de Z en 0.75 $us ò 750 $us Para Z1 → 5(4) + 4(0) = 20( Miles de $us); Para Z2 → 5(8/3 + 4(2) = 64/3(Miles de $us) → Δ Y2 = (64/3-20)=4/3 ;LIO 2 =20/3 -4 = 8/3→ Y2 = (4/3) /(8/3)= 0.5(miles de $us/ton de M2 ) Esto quiere decir que un cambio de 1 tonelada en M2 ,dentro el intervalo 4 ≤ M2 ,≤ 20/3 harà cambiar el valor òptimo de Z en 0.5 $us ò 500 $us Análisis de modelos seleccionados de programación lineal.En la práctica los modelos analizados con dos variables son poco reales, por lo que ahora se extenderá a modelos más reales, donde la definición de las variables(màs de dos) y la construcción de los mismos no son tan directos como en los casos anteriores..Como ser: Modelos bancarios.El Banco Ganadero ésta desarrollando una política de préstamos por un máximo de $us 12 millones de acuerdo a distintos préstamos Tasas Tipo de préstamo

De interés %

De deuda %impagable

Personal

0.140

0.10

Automóvil

0.130

0.07

Casa

0.120

0.03

Agrícola

0.125

0.05

Comercial

0.100

0.02

8

Las deudas impagables no se recuperan por lo tanto no producen ingresos por intereses sino representan pérdidas. Para competir con otras instituciones, necesita que el banco asigne un mínimo del 40% de los fondos a préstamos agrícolas y comerciales. Para ayudar a la industria de la construcción de su región los préstamos familiares deben ser iguales cuando menos al 50 % de los préstamos personales para automóvil y para casa. También el banco tiene una política explícita que no permite que la relación gral. De préstamos impagables entre todos los préstamos sea mayor que el 4%.El objetivo del banco es maximizar su retorno neto que es la diferencia entre el retorno por intereses y por préstamos impagables. Solución.Determinación de las variables. Ingreso neto=(Ingreso-Egreso) X1 : préstamos personales

0.14(1-0.10)-0.1=0.026

X2 : préstamos para automóvil

0.13(1-0.07)-0.07=0.0509

X3 : préstamos para casa

0.12(1-0.03)-0.03=0.0864

X4 : préstamos para agricultura

0.125(1-0.05)-0.05=0.06875

X5 : préstamos comerciales

0.10(1-0.02)-0.02=0.078

Función Retorno neto Z = 0.026 X1 +0.0509X2 +0.0864X3 +0.06875X4 +0.078X5 Restricciones (millones de $) 1) Fondos totales

→ X1 +X2 +X3 +X4 +X5 ≤ 12 X4 +X5 ≥0.4(12)

2) Fondos agrícolas-comerciales→ 3) Fondos para la construcciòn →

X3

≥0.5(X1 +X2 +X3)

4) Límite de deudas impagables →(0.01X1 +0.07X2 +0.03X3 +0.05X4 +0.02X5) ≤ 0.04 X1 +X2 +X3 +X4 +X5 5) No negatividad

→ X1 ,X2,X3,X4,X5 ≥0

El modelo se construye bajo una hipótesis y es que todos los prèstamos se otorgan al mismo tiempo.La soluciòn del odelo de acuerdo al programa TORA recomienda sòlo prèstamos comerciales y para casa.Como tarea se pide ejecutar el programa y analizar los resultados Modelo de uso y desarrollo de bienes y raìces.Una Cìa de bienes y raìces posee 800 acres(1 acre= 0.4046 Hectàreas=4046 m²) de terreno en un lago escènico,debido a la carencia de servicios de alcantarillado existe muchos pozos sèpticos .ocasionando problemas de contaminación de agua.Para mitigar el degradamiento de la calidad del agua,las autoridades municipales aprobaron reglamentos estrictos para todos los desarrollo urbanìstico en el futuro: 1)Sòlo se pueden construir casa para una ,dos y tres familias y las casas uni8familiares deben ser al menos el 50% del total. 2)Para limitar la cantidad de fosas sèpticas se requieren tamaños mìnimos de lote de 2,3,4 acres para las casas con una ,dos y tres familias respectivamente. 3)Se deben establecer àreas de recreos de 1 acre c/u en un proporción de una por 200 fmilias. 4)Para preservar la ecologìa del lago,no se debe bombear agua subterrànea para usoi domèstico ni de riego.

9

El presidente de la Cìa estudia la posibilidad de desarrollar los 800 acres de la empresa,el mismo incluirà casa para una dos ,tres familias.Se estima que el 15 % de los acres se debe asignar a calles y servicios comunitarios.La Cìa estima que los ingresos por las diversas unidades de habitación seràn: Unidad de habitaciòn

Una(flia)

Rendimiento neto/unidad ($)

10 000

Dos(flia) 12 000

Tres(flia) 15 000

El costo de conectar el servicio del agua al àrea es proporcional a la cantidad de unidades construidas.Sinembargo,el municipio cobra un mìnimo de $ 100000 por el proyecto.Ademàs el aumento de la capacidad actual del sistema del abastecimiento de agua se limita 200000 galones por dìa durante las temporadas pico.Los datos siguientes resumen el costo de conectar el servicio de agus y tambièn el consumo de agua ,suponiendo familias de tamaño promedio: Unidad de habitación

Una

Dos

Tres Parques jardines

Gasto-Consumo Costo del servicio Agua($)/unidad Consumo de agua por unidad galòn/dìa

1000 400

1200 1400 800 600

840 450

La empresa desea maximizar el rendimiento total sobre la construcciòn de las diferentes casas y de las àreas de recreo Soluciòn.Variables; X1 : Cantidad de casas unifamiliares X2 : Cantidad de casas para dos familias X3 : Cantidad de casas para tres familias X4 : Cantidad de àreas de recreo Funciòn objetivo:Maximizar el rendimiento total: Màx Z = 10 000 X1 +12 000 X2 + 15 000 X3 Restricciones: 1) Uso del terreno 2 X1 +3 X2 + 4 X3 + 1X4 ≤ 680(=0.85x800) 2) Casas unifamiliares X1 / (X1 + X2 + X3) ≥ 0.5 → 0.5 X1 -0.5 X2- 0.5 X3 ≥ 0 3) Areas de recreo X4≥( X1 + 2X2 + 3 X3) / 200→200 X4- X1 -2 X2- 3 X3 ≥0 4) Costo del capital para el servicio del agua 1000 X1 +1200 X2 + 1400 X3 + 800X4 ≥ 100 000 5)Consumo de agua 400 X1 + 600 X2 + 840 X3 + 450X4 ≤ 200 000 6) No negatividad : X1 , X2 , X3,X4 ≥ 0 NOTA.- Cuando se construye modelos se sugiere tener cuidado con el redondeo y la proporcionalidad,asì por ej. Los coeficientes de las restricciones del costo de capital y consumo de agua (4 y 5) son comparativamente muy grandes con respecto a las demàs restricciones,en este caso es necesario homologar para ello es necesario reducir la escala 10

de èstas restricciones dividiendo entre mil por lo tanto dichas restricciones modificadas serìan: 4)Costo de capital para el servicio del agua: X1 +1.2 X2 + 1.4 X3 + 0. 8X4 ≥ 100 5) Consumo de agua: 0.4 X1 +0.6X2 + 0.840 X3 + 0.45X4 ≤ 0.200 MÈTODO SIMPLEX.Hasta ahora todos los modelos tratados y resueltos estaban construidos en base a dos variables, en la pràctica, los modelos de programación lineal tienen màs de dos variables ,por lo que el mètodo gràfico o algebraico ya no es fácil utilizar por lo que se debe recurrir a otros mètodos o tècnicas de soluciòn. Entre ellos tenemos el mètodo simples que està asociado con un punto esquina del espacio de soluciones. La transición de soluciòn hasta el mètodo simplex implica un procedimiento de còmputo (Iteraciones). Para ello se debe convertir todas las restricciones de desigualdad en ecuaciones para posteriormente manipular las ecuaciones de manera sistemàtica ESPACIO DE SOLUCIONES.Para determinar el espacio de soluciones de programación lineal en forma algebraica: 1)Se debe convertir las inecuaciones de las restricciones en ecuaciones con el lado derecho no negativo 2) Todas las variables son no negativas. CONVERSIÒN DE LAS DESIGUALDADES EN ECUACIONES.-

Las restricciones del tipo a lo mucho ( ≤ ) la parte derecha representa el lìmite de disponibilidad de los escasos recursos ,el lado izquierdo representa el uso de esos recursos limitados por parte de las actividades del modelo. VARIABLES DE HOLGURA (Si).-La diferencia entre el lado derecho y el lado izquierdo de èstas desigualdades representa la cantidad no usada ,la misma que se traduce en variables de holgura;por lo tanto para convertir en ecuación èstas desigualdades se deben agregar dichas variables al lado izquierdo de dichas restricciones. Ej. Se tiene la siguiente restricción del modelo de pinturas: 1) 6 X1 + 4X2 ≤ 24 → 6 X1 + 4X2 + S1 = 24 tal que S1 ≥0 - Las restricciones del tipo por lo menos (≥) donde la parte izquierda representa cantidad mayor que el lìmite mìnimo del lado derecho

una

VARIABLES EXCEDENTES (-Si).- La diferencia en tre lado izquierdo y el lado derecho de èstas desigualdades representa la cantidad excedente,traducièndose en variables excedentes ,por lo tanto para convertir en ecuación èstas desigualdades se deben restar la variable excedente en el lado izquierdo Ej. Se tiene la siguiente restricción del modelo de la dieta 2) X1 + X2

≥ 800→ X1 + X2 -S1 = 800 tal que S1 ≥ 0

Nota.- cuando el lado derecho es negativo se debe multiplicar por (-1) cambiando la direcciòn de la desigualdad Ej. Se tiene: - X1 + X2 ≤ -3 → X1 - X2 + S1 = -3 → S1≥ 0 *(-1) → X1 - X2 - S1 = 3 11

TRANSICIÒN DE LA SOLUCIÒN GRÀFICA A LA ALGEBRAICA SIMPLEX La soluciòn gràfica de un modelo de programación lineal constituye la base para desarrollar el mètodo algebraico y por ende el simplex ,el mismo que se puede apreciar en el siguiente esquema. Mètodo gràfico Graficar las restricciones ↓ Espacio de soluciones factibles

Mètodo algebraico Representar el espacio de *soluciones con m ecs. Con n variables ↓ Sistema con infinidad de soluciones

Identificar puntos factibles esquina del espacio de soluciones (corresponde a una cantidad finita de puntos de esquina)

Determina las soluciones bàsicas factibles de las ecs. (las soluciones òptimas corresponden a una cantidad finita de soluciones bàsicas factibles)

Utiliza la funciòn objetivo para determinar el punto esquina òptimo (entre todos los candidatos)

Utiliza la funciòn objetivo para determinar la soluciòn bàsica òptima

Nota.a)*Espacio de soluciones.- el espacio de soluciones se representa con m ecs. Lineales simultaneas y n variables no negativas,para delimitar el espacio de soluciones se debe recurrir a la realciòn m ≤ n de la siguiente manera: a) si m= n

siendo las ecs.consistentes →el sistema tiene una soluciòn

b) si m < n (mayor parte de los modelos de programación lineal) → el sistema de ecs. Produce una infinidad de soluciones. b)** Puntos soluciòn.-Para determinar los puntos soluciòn,se debe igualar n-m = 0 y luego despejando las n variables restantes de las m ecs.,la soluciòn resultante,si es ùnica corresponde aun punto esquina del espacio de soluciones c)***El nùmero de esquinas soluciòn se obtiene mediante n C m d) Variables no bàsicas.-Se llaman variables no bàsicas a las n-m = 0 e) Variables bàsicas .- son las m variables restantes que tienen una soluciòn ùnica y su soluciòn se llama soluciòn bàsica En resumen el mètodo simples se usa un procedimiento de bùsqueda diseñado para llegar al punto esquina òptimo en forma eficiente ,aunque el procedimiento es algo largo y tedioso,para ello se sugiere utilizar algún programa como el TORA o el Excel

12

Modelo programación de maximización Para corroborar el esquema de la transición se tiene el siguiente modelo de programcaciòn lineal. Maximizar: Z = 2X1 + 3X2 Sujeto:

determinar de manera gràfica y algebraica

1) 2X1 + X2 ≤ 4

a) los puntos de soluciòn factibles y no factibles

2) X1 +2 X2 ≤ 5

b) Los puntos òptimos de soluciòn,

X1, X2 ≥ 0

3)

c)Las variables no bàsicas como bàsicas d) Puntos esquina asociado su factibilidad y el valor de Z

Soluciòn gràfica: Determinación del espacio de soluciones utilizando las restricciones determinando las rectas. 1) 2X1 + X2 ≤ 4

2) X1 +2 X2 ≤ 5

2

0

5

0

0

4

0

2.5

X2≥ 0

que delimiten el espacio posible de soluciones

a) Puntos de soluciòn.factibles: A=(0,0) ,B=(2,0) ,C=(1,2),D=(0,2.5)

4 F

no factibles : E=(5,0), F=(0,4) Espacio de soluciòn factible; limitado por los puntos.

3

A,B,C,D

D 2

b)Punto òptimo de soluciòn C = (X1 =1, X2 =2) porque satisface ↓©

Punto òptimo de soluciòn

las tres restricciones

espacio 1 l→sol. A

↑

0

← B

1

2

E 3

4

5

X1≥ 0

Soluciòn algebraica: Convirtiendo el modelo original en modelo de programación lineal(igualando las inecuaciones en ecuaciones introduciendo las variables de holgura en cada restricción explìcita) Maximizar . : Z = 2X1 + 3X2 Sujeto:

1) 2X1 + X2 + S1 2) X1 +2 X2

=

4

+S2 = 5

3) X1, X2, S1, S2 ≥ 0 a)Determinando los puntos esquina como m= 2 ecs. y n= 4 variables entonces el nº de puntos esquina o soluciòn 4 C 2= 6 esquinas de acuerdo a la determinación de las variables no bàsicas 4-2= 2 ,resolvièndolas (igualando a cero) para hallar el valor de las demàs. Asì por ej. Si las dos primeras no bàsicas son X1, X2 es decir X1=0, X2=0 ,resolviendo las demàs ecs. con estos dos valores en las restricciones transformadas se tiene

13

1) 2(0) + (0) + S1 2) (0) +2 (0)

4 →

S1 = 4

+S2 = 5 →

S2 = 5

=

corresponde al Punto o esquina A=(X1 =0, X2=0)

Cuyo valor objetivo de Z=2X1 + 3X2 → Z=2(0) + 3(0)= 0 Y asì sucesivamente se procede resolviendo los sistemas de 2 ecs ,los mismos que se resumen en el siguiente cuadro:

Variables no

Variables

Soluciòn

Punto

Factibilidad

esquina asociado

Valor

Bàsicas(=cero)

Bàsicas(≠ cero) Bàsica

Objetivo de Z

( X1, X2 )

(S1, S2)

(4,5)

A

si

0

(X1, S1)

(X2, S2)

( 4,-3)

F

no

-

(X1, S2)

(X2, S1)

(2.5,1.5)

D

si

7.5

(X2, S1)

(X1, S2)

(2,3)

B

si

4

(X2, S2)

(X1, S1)

(5,-6)

E

no

-

( S1 S2)

(X1, X2)

(1,2)

C

si

8(òptimo)

Nota,- se pide alumno verificar la solución básica Condiciones para aplicar el algoritmo Simples.Para aplicar el mètodo simplex a un modelo de programación lineal es necesario tener presente algunos conceptos,para luego determinar si cumplen dos condiciones:1) la de factibilidad y 2) la de optimalidad Variable de entrada.- en un problema de maximización es aquella variable No bâsica que tenga el coeficiente màs negativo ,en uno de minimización ,màs positivo en el renglón de la Z,si existe empate se elige uno de ellos Variable de salida.-en un problema de maximización y de minimización es la variable bàsica relacionada con la razòn mìnima en la columna de las razones,si existe empate,se elige uno de ellos 1)Condiciòn de factibildad.- se dice que el modelo es factible si existe por lo menos una variable de salida 2)Condiciòn de optimalidad .-se llega a una optimalidad en la iteración respectiva cuando todos los coeficientes de las variables no bàsicas en el renglón Z son no negativos en el caso de una maximización o todos son no positivos en un acaso de minimización Procedimiento para efectuar el algoritmo simples en modelos de maximizaciòn con variables de holgura Para aplicar el algoritmo simplex a modelos de programación lineal con dos ò màs variables se sugiere seguir los siguientes pasos: 1.-Convertir las inecuaciones de las restricciones explìcitas en igualdades introduciendo variables de holgura(Si) si se desa maximizar y/o variables excedentes si se trata de minizar 2.-Igualar la funciòn objetivo a cero

14

3.-Utilizar la tabla simples(tabla de entrada y de salida),donde las filas corresponden a las variables posibles de salida y las columnas a las variables de entrada posibles,llenando con sòlo sus coeficientes. 4.-Determinar el eje columna pivote y renglón pivote el que determina el elemento pivote(Intersecciòn de fila y columna pivote) En un modelo de Maximización: La variable de entrada serà aquel con mayor coeficiente de la funciòn objetivo Z original ò mayor valor negativo de la funciòn objetivo transformado. La variable de salida se obtiene determinando las razones de cada fila las mismas que se obtienen dividiendo los valores de cada soluciòn sobre los valores de cada columna de la variable de entrada,siendo la variable de salida aquella que tenga razòn mìnima En un modelo de minimización La variable de entrada,serà aquella variable no bàsica con el coeficiente objetivo màs positivo La variable de salida serà con mìnima razòn igual que en la de maximizar 5.-Iterar tantas veces el 4º paso,hasta que los valores de la funciòn objetivo Z en la tabla simples sean No negativos Ej.Del modelo de la Cìa de pinturas.resolver mediante el algoritmo simplex. Maximizar Z=5 X1 + 4 X2

Z-5X1 - 4X2 - 0S1 - 0S2-0S3-0S4 = 0

Sujeto a las restricciones: 1) → 6 X1 + 4X2 ≤ 24 2) →

X1 +2X2 ≤ 6

1) → 6 X1 + 4X2 + S1 1er paso

2) →

X1 +2X2

3) → - X1 + X2 ≤ 1

3) → - X1 + X2

4)→

4)→

5) →

X2 ≤ 2 X1 , X2 ≥ 0

X2

=

+ S2

24

=

+ S3

=

6 1

+ S4=2

X1, X2 ≥ 0

Nº de variables n= 6 . Nº de ecs. 4 → Nº de soluciones = 6C4= 15 soluciones posibles Confeccionando la tabla simples,donde se colocan las variables bàsicas y las nobàsicas en el primer renglón conjuntamente Z y en la primera columna las bàsicas ,en la parte interna del cuadro los coeficientes en la penùltima columna las soluciones y en la ùltima columna las razones de cada renglón, para determinar la columna pivote y renglón pivote y por ende el elemento pivote de la siguiente manera : la variable de entrada es aquella con mayor valor negativo de la funciòn objetivo(en este caso X1=5) y luego la variable de salida es aquella que tiene menor razòn (S1→ X1 = 24 / 6 = 4 (mìn)) y por ende el elemento pivote es 6

15

TABLA SIMPLEX ↓ Variables Z

X1

X2

S1

S2

S3

S4

Soluciòn

Razòn deXi= Col.Sol/Col.pivote

Z

1

-5

-4

0

0

0

0

0

←S1

0

6

4

1

0

0

0

24

S2

0

1

2

0

1

0

0

6

X1=

6/1= 6

S3

0

-1

1

0

0

1

0

1

X1=

1 /-1= -1(ignorer)

S4

0

0

1

0

0

0

1

2

X1=

2 / ∞ = ∞ (ignorar

X1 = 24 / 6 = 4 (mìn)

Para realizar la primera iteraciòn , es decir para obtener la nueva soluciòn se deben obtener los nuevos renglones de la tabla de la siguiente manera: 1.-Nuevo renglón(del renglòn pivote) = Coeficiente renglón pivote actual / Elemento pivote 2.-Los demàs nuevos renglones(inclusive el de Z) se obtienen : Coeficiente actual - coeficiente de la columna pivote * nuevo coeficiente renglón pivote Para el modelo en cuestión la obtención de los nuevos renglones son. Nuevo renglón del pivote (para X1 en reemplazo de S1) : 0/ 6 = 0 ; 6/6= 1; 4/6= 2/3 ; 1/6, 0/6=0, 0/6=0 ,0/6=0 Nuevos renglones Para Z

Para S2

Para S3

Para S4

1-(-5)(0) = 1

0-(1)(0) = 0

0-(-1)(0)

=0

0-(0)(0) = 0

-5-(-5)(1) = 0

1-(1)(1) = 0

-1-(-1)(1)

=0

0-(0)(1) = 0

- 4-(-5)(2/3)= -2/3

2-(1)(2/3) = 4/3

1-(-1)(2/3) = 5/3

1-(0)(2/3) = 1

0-(-5)(1/6)= 5/6

0-(1)(1/6) = -1/6

0-(-1)(1/6) = 1/6

0-(0)(1/6) = 0

0-(-5)(0) = 0

0-(1)(0)

= 0

0-(-1)(0)

=0

0-(0)(0) = 0

0-(-5)(0) = 0

0-(1)(0)

= 0

1-(1)(0)

=1

0-(0)(0) = 0

0-(-5)(0) = 0

0-(1)(0)

= 0

0-(-1)(0)

= 0

1-(0)(0) =1

Nueva Columna de soluciòn.Se obtienen teniendo presente las variables bàsicas(aquellos =0) en este caso X2 =0, S1 =0 Con estos valores resolver cada restricción transaformada hallando sus valores En este caso en la 1ª restricción 6 X1 +4(0) = 24 → X1= 24/6 = 4 en la 2ª restricción 4 + 2(0) + S2 = 6 → S2 =6-4 =-2 en la 3ª restricción -4 +(0)+ S3 =1 → S3 = 1+4= 5 en la 4ª restricción 0+ S4 =2 → S4= 2 Nueva Soluciòn Z 16

Reemplazando en la funciòn Z original los valores de X1= 4 : X2=0→ Z= 5(4)+4(0)= 20 Con los nuevos valores se debe construir una nueva tabla simples NUEVA TABLA SIMPLEX TRANSFORMADA Y MEJORADA Variables Z Z

1

X1 0

X2

S1

- 2/3

5/6

S2

S3

0

S4

0

Soluciòn

0

20

2/3

1/6

0

0

0

4

0

4/3

-1/6

0

0

0

2

0

0

5/3

1/6

0

1

0

5

0

0

1

0

0

0

1

2

X1

0

S2

0

S3 S4

1

Razòn de Xi

Como todavía existe un coeficiente negativo en el nuevo renglón Z (X2 = - 2/3) ,se debe realizar una nueva iteraciòn siguiendo el mismo procedimiento anterior La nueva variable de entrada X2 ( = - 2/3), y luego la variable de salida es aquella que tiene menor razòn (S2→ X2 = 2/ 4//3 =6/4=1.5 (mìn)) y por ende el elemento pivote es 4/3 ↓ Variables Z Z

1

X1 0

X2

S1

- 2/3

5/6

S2

S3

0

S4

0

Soluciòn

0

Razòn de X2

20

2/3

1/6

0

0

0

4

X 2= 4 / (2/3)= 6

0

4/3

-1/6

1

0

0

2

X 2 = 2 / (4/3)= 1.5( Min)

0

0

5/3

1/6

0

1

0

5

X 2= 5 / (5/3)=3

0

0

1

0

0

0

1

2

X 2= 2 / 1 = 2

X1

0

←S2

0

S3 S4

1

Nuevo renglón del pivote(paraX2 en reemplazo de S2: 0/ (4/3) = 0 ; 0/(4/3)= 0; (4/3)/(4/3)= 1 ;(-1/6)/( 4/3)= -1/8; 1/(4/3)=3/4; 0/(4/3)=0;0/(4/3)=0 Nuevos renglones Para Z

Para X1

Para S3

Para S4

1-(-2/3)(0)

= 1

0-(2/3)(0)

= 0

0-(5/3)(0)

=0

0-(1)(0)

=0

0-(-2/3)(0)

= 0

1-(2/3)(0)

= 1

0-(5/3)(0)

=0

0-(1)(0)

=0

-2/3-(-2/3)(1)

=0

2/3-(2/3)(1)

=0

5/3-(5/3)(1)

=0

1-(1)(1)

=0

5/6-(-2/3)(-1/8) = ¾

1/6-(2/3)(-1/8) = ¼

0-(-2/3)(3/4)

=½

0-(2/3)(3/4)

0-(-2/3)(0)

= 0

0-(2/3)(0)

= 0

1-(5/3)(0)

=1

0-(1)(0)

=0

0-(-2/3)(0)

= 0

0-(2/3)(0)

= 0

0-(5/3)(0)

= 0

1-(1)(0)

=1

= -1/2

1/6-(5/3)(-1/8) = 3/8 0-(1)(-1/8) = 1/8 0-(5/3)(3/4) = -5/4 0-(1)(3/4) = -3/4

17

Nueva Columna de soluciòn.Se obtienen teniendo presente las variables bàsicas (aquellos =0) en este caso S1 =0 ,S2=0 Con estos valores resolver cada restricción transformada hallando sus valores En este caso resolviendo el sistema 1ª restricción 6 X1 +4X2 + 0 = 24

→ X2 =12 / 8 = 1.5

2ª restricción X1 + 2X2 + 0 = 6

→ X1 =12 / 8 = 3

Y las siguientes : 3ª restricción - X1 +X2 + S3 = 1

→ -3+1.5+ S3 = 1→ S3 = 2.5

X2 + S4 =2

4ª restricción

→1.5 + S4 =2 → S4 = 0.5

Nueva soluciòn Z Reemplazando en la funciòn Z original los valores de X1= 3 : X2=1.5→Z=5(3)+4(1.5)= 21 NUEVA TABLA SIMPLEX TRANSFORMADA Y OPTIMIZADA Variables Z Z

1

X1

X2

0

0

S1 ¾

S2 ½

S3 0

S4

Soluciòn

0

21

X1

0

1

0

1/4

-1 / 2

0

0

3

X2

0

0

1

-1/ 8

3/4

0

0

1.5

S3

0

0

0

3/8

-5 / 4

1

0

2.5

S4

0

0

0

1/8

-3 / 4

0

1

0.5

Como todos los coeficientes de la funciòn objetivo Z son positivos ,entonces se ha optimizado la utilidad por lo tanto no es necesario realizar màs iteraciones.Es decir la nueva funciòn de utilizadad maximizada es Z=5(3)+4(1.5)= 21 En conclusión.Dado la soluciòn final se puede concluir que para obtener una utilidada diaria de $21 es necesario producir 3 toneladas diarias de pintura para exteriores y 1.5 toneladas diarias de pintura para interiores La tabla simplex optimizado tiene ademàs algunas ventajas como ser: a) Presenta la información sobre el estado de los recursos b) Presenta información sobre el valor unitario de los recursos c) Presenta información para efectuar un análisis de sensibilidad con la soluciòn òptima Respecto al estado de los recursos se considera escasa si las actividades(variables) del modelo se usan por completo es decir =0,se considera abundante si las actividades cuando es mayor que 0. De acuerdo al problema encuestiòn se puede deducir mediante el siguiente resumen:

18

Recurso

Variables de

Estado del

Holgura

recurso

Materia Prima M1

S1 = 0

Escaso

Materia Prima M2

S2 = 0

Escaso

Lìmite de demanda 1

S3 = 5 / 2

abundante

Lìmite de demanda 2

S4 = ½

abundante

Algoritmo simplex en modelos de maximización y /o minimización con variables artificiales Modelos de minimización.Cuando existen modelos de programciòn lineal con restricciones igualdades(=) o desigualdades (≥) ,para aplicar el algoritmo simplex es necesario utilizar variables artificiales (Ri),teniendo dos mètodos de soluciòn : El mètodo de penalizaciòn(M) y el de dos fases 1)Mètodo de penalizaciòn o M.Este mêtodo se aplica cuando el modelo tiene restricciones del tipo de igualdades(=) y/ o por lo menos(≥). Cuando tiene restricciones de igualdad (=),se deben añadir a èstas variables artficiales (Ri) Cuando tiene restricciones de por lo menos(≥) se deben añadir a èstas variables artificiales (Ri) y variables de excedencia(-Xi) Cuando tiene restricciones de a lo mucho (≤) se deben añadir a los mismos,sòlo variables de holgura (Xi) Como se estàn añadiendo variables artificiales (Ri) que no pertenecen al modelo a èstas variables se las debe penalizar con coeficientes M infinitamente grandes(M en problemas de minimización) o infinitamente pequeños(-M en problemas de maximización) en la funciòn objetivo. Procedimiento.Una vez transformado las restricciones en igualdades,se debe modificar la funciòn objetivo Z y el renglón Z de la siguiente manera: Nuevo renglón Z modificado= Renglón original +( ∑Ri M) Una vez modificada la funciòn objetivo se procede a iterar como en el caso de Mximizaciòn Ej.Se tiene el siguiente Modelo:

Soluciòn convirtiendo en igualdad las restricciones

Minimizar → Z = 4X1 + X2

Z= 4X1 + X2 +MR1 + MR2:

Sujeto a : 1)

3X1 + X2 = 3

1)

3X1 + X2

2)

4X1 +3 X2 ≥ 6

2)

4X1 +3 X2 – X3

3)

X1 + 2X2 ≤ 4

3)

X1 + 2X2

4)

X1, X2 ≥ 0

4)X1, X2 , X3 , X4,, R1, R2 ≥0

+R1

=3

+R2 = 6 + X4

=4

Igualando la funciòn objetivo a cero: Z - 4X1 - X2 - MR1 - MR2 = 0 Construyendo la nueva tabla inicial con las nuevas variables artificiales como de holgura y excedencia

19

NUEVA TABLA SIMPLEX(con variables artificiales) V.Bàsicas X1 Z

-4

X2

X3

-1

0

R1

R2

-M

X4

-M

Soluciòn

0

0

R1

3

1

0

1

0

0

3

R2

4

3

-1

0

1

0

6

X4

1

2

0

0

0

1

4

Ahora se debe modificar la funciòn objetivo penalizada la misma que debe ser ajustada de la siguiente manera: Nuevo renglón Z ajustado

Nueva columna soluciòn

Para X1 → -4+ ( 3M+4M)

= -4+7M

Para X2→ -1+ (1M+ 3M)

= -1+4M

Como X1 = X2= X3 = 0

R1 = 3 ; R2 = 6 → Z - 4X1 - X2 - MR1 - MR2

Para X3→ 0+ [0M + (-1M)] = -M Para R1→ -M +(1M + 0M)

.

Z = 4(0) + (0) + M(3)+ M(6)= 9M

=0

Para R2 → -M +(0M + 1M) = 0 Para X4 →

0+(0M+0M)

=0

NUEVA TABLA SIMPLEX(con funciòn objetivo modificado) V.Bàsicas X1 Z

X2

(- 4 +7M) (- 1+4M)

X3

R1

-M

0

R2

X4

0

0

Soluciòn 9M

R1

3

1

0

1

0

0

3

R2

4

3

-1

0

1

0

6

X4

1

2

0

0

0

1

4

Procediendo a iterar para ello se deben determinar las variables de entrada y de salida y por ende el elemento pivote Determinando la variable de entrada como se està minimizando es elige aquella variable con coeficiente mayor positivo del renglòn Z ,en este caso corresponde a la variable X1 y la de salida la variable R1 por tener mìnima razòn de acuerdo al siguiente cuadro: Primera iteración ↓ V.Bàsicas X1 Z

X2

(- 4 +7M) (- 1+4M)

X3

R1

-M

0

R2

X4

0

0

Soluciòn

Razòn Xi

9M

←R1

3

1

0

1

0

0

3

X1

R2

4

3

-1

0

1

0

6

X1 =6/4=1.5

X4

1

2

0

0

0

1

4

X1 = 4/1=4

= 3/3= 1

20

Nuevo renglón del pivote(paraX1 en reemplazo de R1 ( dividir todo el renglòn entre 3): 3 / 3= 1

1/3

0 / 3=0

1/3

0/3=0

0 / 3=0

Nuevos renglones Para Z

Para R2

Para X4

(-4+7M) - (-4+7M) (1)=0

4-4(1)= 0

1-1(1) = 0

(-1+4M)- (-4+7M)( 1 / 3)=(1+5M)/3

3-4(1/3) = 5/3

2-1(1/3)= 5/3

-M - (-4+7M)(0) = -M

-1-4(0) = 0

0-1(0) = 0

0-(-4+7M)(1/3)= (4-7M)/3

0-4(1/3)= 0

0-1(1/3) =-1/3

0-(-4+7M)(0)= 0

1-4(0) = 1

0-1(0) = 0

0-(-4+7M)(0)= 0

0-4(0) = 0

1-1(0) = 1

Nueva Columna de soluciòn Sabiendo que X2=0

X3 =0 +R1

R1 =0

1)

3X1 + X2

= 3→3X1

+ 0 +0

2)

4X1 +3 X2 – X3

+R2 = 6→ 4(1) +3 (0) –0 +R2 = 6 → R2 = 6 -4= 2

3)

X1 + 2X2 + X4

=4

→ 1 + 2(0) + X4

= 3→

X1 = 3/3 =1

=4→

X4

= 4-1=

3

Nueva soluciòn para Z = 4(1) +0+M(0) +M2 → Z = 4 +2M Tabla Iterada V.Bàsicas X1 Z

0

X2 ( 1+5M)/3

X3

R1

-M

R2

X4

(4-7M)/3 0

Soluciòn

0

X1

1

1/ 3

0

1/3

0

R2

0

5/ 3

-1

- 4 /3

1

X4

0

5/ 3

0

- 1/3

0

Razòn Xi

4 +2M 1

X1

0

2

X1 =6/4=1.5

1

3

X1 = 4/1=4

0

= 3/3= 1

Como todavía existen coeficientes positivos en el renglòn Z se debe volver ha realizar una nueva iteración determinando las variables de entrada (X2) y salida( R2) siendo el elemento pivote 5 / 3 Nueva iteración

↓

V.Bàsicas X1

X2

Z

0

( 1+5M)/3

X3

R1

-M

R2

X4

(4-7M)/3 0

0

X1

1

1/ 3

0

1/3

0

←R2

0

5/ 3

-1

- 4 /3

1

X4

0

5/ 3

0

- 1/3

0

Soluciòn

Razòn Xi

4 +2M

X2

1

1/(1/3)=3

0

2

2/(5/3)= 6/5

1

3

3/(5/3)=9/5

0

Nuevo renglón del pivote(paraX2 en reemplazo de R2 ( dividir todo el renglòn entre 5/3): 21

0/ (5/3)=0; (5/3)/(5/3) =1 ; -1/(5/3) = -3/5; (- 4/3)/(5/3)= - 4/5; 1/(5/3)=3/5; 0/(5/3)=0 Nuevos renglones Para Z

Para X1

Para X4

0-( 1+5M)/3 (0) = 0

1- (1/3)(0)= 1

0-(5/3)(0)=0

( 1+5M)/3 - ( 1+5M)/3 (1)=0

1/3-(1/3)(1)=0

5/3-(5/3)(1)=0

-M - ( 1+5M)/3(-3/5)= 1/5

0-(1/3)((-3/5)=1/5

0-(5/3)(-3/5)=1

(4-7M)/3 - ( 1+5M)/3(-4/5)=(8-5M )/5

1/3-(1/3)(-4/5)=3/5

-1/3-(5/3)(-4/5)=1

0- ( 1+5M)/3(3/5)= -(1+5M)/5

0-(1/3)(3/5)= -1/5

0-(5/3)(3/5)= -1

0-( 1+5M)/3(0) =0

0-(1/3)(0)= 0

1-(5/3)(0)= 1

Nueva Columna de soluciòn.Sabiendo que : X3 = 0 ; R1= 0 ; R2 =0 ,resolviendo el sistema de ecs. +R1

=3

→ X1= 0.6

1)

3X1 + X2

2)

4X1 +3 X2 – X3

+R2 = 6 → X2 = 1.2 Luego reemplazando en la restricciòn3)

3)

X1 + 2X2 + X4

=4

→ 0.6 +2(1.2) + X4 = 4 → X4 =1

Nueva soluciòn para Z = 4(0.6) +1.2+M(0) +M(0) → Z = 3.6 Tabla Iterada V.Bàsicas X1 Z X1

0

0

X3

R1

R2

X4

Soluciòn

1/5 (8 - 5M )/5 - (1+5M)/5 0

3.6

1

0

1/5

3/5

-1/5

0

0.6

0

1

-3/5

-4/5

3/5

0

1.2

0

1

1

1

1

X2 X4

X2

0

-1

Como todavía existen coeficientes positivos en el renglòn Z se deberà realizar una nueva iteración determinando las variables de entrada(X3) y de salida (X4) por tener razòn mìnima Siendo elemento pivote 1 Nueva iteración V.Bàsicas X1 Z

0

↓ X2 0

X3

R1

R2

X4

1/5 (8 - 5M )/5 - (1+5M)/5 0

Soluciòn

Razòn

3.6

X3

X1

1

0

1/5

3/5

-1/5

0

3/5= 0.6

0.6/0.2=3

X2

0

1

-3/5

-4/5

3/5

0

6/5= 1.2

1.2/(-3/5)=-2

0

0

1

1

←X4

-1

1

1

1/1= 1(Mìn)

Nuevo renglón del pivote(paraX3 en reemplazo de X4 ( dividir todo el renglòn entre 1 0/1= 0 ; 0/1= 0 ,

1/1=1 ; 1/1= 1 ; -1/1=-1 ; 1/1= 1

Nuevos renglones 22

Para Z

Para X1

0 -(1/5) (0)=0

1-(1/5)(0)= 1

0-(-3/5)(0)=0

0 – (1/5)(0)= 0

0-(1/5)(0)=0

1-(-3/5)(0)=1

1/5-(1/5)(1) =0

1/5-(1/5)(1)=0

-3/5-(-3/5)(1)=0

( 8 - 5M )/5 –(1/5)(1)=(7-5M)/5

3/5-(1/5)(1)=2/5

-4/5-(-3/5)(1)=-1/5

- (1+5M)/5 -(1/5)(-1)= -M 0- (1/5)(1)= -1/5

Para X2

-1/5-(1/5)(-1)=0

3/5-(-3/5)(-1)=0

0-(1/5)(1)= -1/5

0-(-3/5)(1)=3/5

Nueva Columna de soluciòn.Sabiendo que X4=0 R1=0 R2=0 y resolviendo el sietamde ecs. 1)

3X1 + X2

+R1

3)

X1 + 2X2 + X4

=3 =4

→ X2= 9/5

→ X1 = 2/5

Nueva soluciòn para Z = 4(2/5)+ 9/5→ Z= 17/5= 3.4 Tabla Iterada Final.-Porque no existe ningún coeficente positivo en el renglònZ V.Bàsicas X1 Z

0

X2

X3

0

0

R1

R2

X4

(7 - 5M )/5 -M

Soluciòn

- 1/5

17/5=3.6

X1

1

0

0

2/5

0

-1/5

2/5=0.4

X2

0

1

0

--1/5

0

3/5

9/5=1.8

X3

0

0

1

1

-1

1

1

Desventajas del mètodo M Este mêtodo adolece de dos desventajas 1.-Que las correspondientes iteraciones puede que no logren minimizarlo hasta cero o negativo(esto ocurre cuando el problema de programación no tiene soluciòn factible) 2.-Como M →(lo màs grande ò lo màs pequeño) principalmente al usar el programa no se tiene definida el tamaño el que puede afectar en las decisiones. Para solucionar esta desventaja surge el mètodo de dos fases: 2)Mètodo dos fases.1ª Fase.- se transforman las inecuaciones en ecuaciones agregando las variables correspondientes de acuerdo al tipo de restricción Luego se plantea la soluciòn bàsica con las ecs. resultantes de modo que: Minimice la suma de las variables artificiales (Ri) → r = R1 + R2+ R3+…+Rk Si Min r = ∑ Ri > 0 C El modelo no tiene soluciòn es decir no es factible se para el proceso Si Min r = ∑ Ri ≤ 0 → El modelo si tiene soluciòn es decir es factible se pasa a la 2ª fase. 2ª Fase.La soluciòn factible de la 1ª fase ,se usa como soluciòn bàsica de inicio para el problema original. Ej Siguiendo con el modelo anterior 23

Minimizar → Z = 4X1 + X2 Sujeto a : 1)

Min r= R1 + R2:r→ r - R1 - R2=0

3X1 + X2 = 3

1)

3X1 + X2

+R1

=3

2)

4X1 +3 X2 ≥ 6

2)

4X1 +3 X2 – X3

3)

X1 + 2X2 ≤ 4

3)

X1 + 2X2

4)

X1, X2 ≥ 0

4)

X1, X2 , X3 , X4,, R1, R2 ≥0

+R2 = 6 + X4

=4

NUEVA TABLA SIMPLEX(con funciòn objetivo Min r - R1 - R2=0 ) V.Bàsicas X1 r

0

X2

X3

0

R1

0

R2

-1

X4

-1

Soluciòn

0

0

R1

3

1

0

1

0

0

3

R2

4

3

-1

0

1

0

6

X4

1

2

0

0

0

1

4

Nuevo renglòn r = renglón r anterior + (1xRenglòn R1 + 1xRenglònR2) .despuès de utilizar el nuevo renglòn para resolver la fase I del problemas con el que se obtiene la siguiente tabla que corresponde a la penultima iteraciòn: Tabla iterada en tèrminos de r V.Bàsicas X1 r

0

X2

X3

R1

R2

0

0

-1

-1

X4

Soluciòn

0

0

X1

1

0

1/5

3/5

-1/5

0

3/5= 0.6

X2

0

1

-3/5

-4/5

3/5

0

6/5= 1.2

0

0

1

1

←X4

-1

1

1

Como r = 0 → ,la fase produce la soluciòn bàsica con X1 = 3/5= 0.6 ;X2= 6/5 = 1.2; X4=1 Las variables artificiales cumplieron su misiòn por lo tanto se pueden eliminar de la tabla de las columnas por completo y se puede pasar a la : 2ªFase El problema origibnal se puede escribir Minimizar Sujeto a

Z = 4 X1 + X2 : X1

+

1/5X3

X2 - 3/5 X3

=3

/5

= 6/5

X3 + X4 = 1

Soluciòn factible de inicio para el problema y la 2ª Fase ,cuya tabla transformada es

X1, X2 ,X3 , X4 ≥ 0

24

Nueva tabla para la 2ª fase V.Bàsicas X1

X2

X3

-4

-1

0

X1

1

0

1/5

0

3/5=0.6

X2

0

1

-3/5

0

6/5= 1.2

1

1

1

Z

X4

0

0

X4

Soluciòn

0

0

Nuevo Z ajustada

Nueva soluciòn

-4+ (4x1 + 1x0)= 0

Con X3 = 0 ¸ X1= 3/5 X2 = 6/5; X4 = 1

-1+(4x0 +1x1)= 0

Z= 4(3/5) + 6/5 = 18/5

0+(4x1/5+1x-3/5)=1/5 0+(4x0+1x0) = 0 Ahora se debe iterar ,determinando la variable de entrada(X3 ) en este caso elegimos X3 (por tener un valor positivo)y la variable de salida X4 por tener mìnima razòn cuyo elemento pivote es 1,de la siguiente manera: ↓ V.Bàsicas X1 Z

X2

0

0

X3 1/5

X4

Soluciòn 18/5

0

Razòn de X3

X1

1

0

1/5

0

3/5=0.6

(3/5)/(1/5)= 3

X2

0

1

-3/5

0

6/5= 1.2

(6/5)/(-3/5)=-2

0

0

1

1

1

←X4

1/1= 1 (mìn)

Nuevo renglón del pivote(paraX3 en reemplazo de X4 ( dividir todo el renglòn entre 1 0/1= 0 ; 0/1 = 0, 1/1= 1 /1=1 Nuevos renglones Para Z

Para X1

Para X2

0-(1/5)(0)= 0

1-(1/5)(0)=1

0-(-3/5)(0)=0

0-(1/5)(0) = 0

0-(1/5)(0)= 0

1-(-3/5)(0)=1

1/5-(1/5)(1)=0

1/5-(1/5)(1)=0

( -3/5)-(-3/5)(1)=0

0-(1/5)(1)= -1/5

0-(1/5)(1) =-1/5

0-(-3/5)(1)= 3/5

Nueva soluciôn Si X4 = 0 → X3 +0 = 1 X1+ 1(1/5) = 3/5 → X1= 2/5 X2 -3/5(1) = 6/5 → X2= 9/5 → Z = 4(2/5) +9/5= 8/5+ 9/5 = 17/5 25

Tabla final V.Bàsicas X1 Z

0

X2

X3

0

0

Soluciòn 17/5

-1/5

X1

1

0

0

X2

0

1

0

0

0

1

X3

X4

-1/5 3/5 1

2/5=0.4 9/5= 1.8 1

26