04 y 05 2016-04-20 y 27 metodo simplex - solución algebraica

8/17/2019 04 y 05 2016-04-20 y 27 Metodo Simplex - Solución Algebraica

1/38

Investigación de OperacionesIng. Juan Miguel DIAZ Mendo

1

“UNIVERSID D PRIV D S N PEDRO”

FACULTAD DE INGENIERIA

CURSO : INVESTIGACIÓN DE OPERACIONES

“MÉTODO SIMPLEX”

DOCENTE:

ING. JUAN MIGUEL DIAZ MENDO

2016

-

04

-

20


2/38

Método Simplex

Hasta ahora, la única forma que conocemos de resolver un

problema de programación lineal, es el método gráfico.

Este método es bastante engorroso cuando aumenta el número

de restricciones e impracticable en más de dos dimensiones.

Para resolver estos problemas, se aplica el método simplex. Estemétodo se puede aplicar a problemas de cualquier tamaño.


3/38

Solución de problemas de programación lineal

El método Simplex es un procedimiento general para resolver

problemas de programación lineal. Desarrollado por George

Dantzig en 1947, esta comprobada su extraordinaria eficiencia, y

se usa en forma rutinaria para resolver problemas grandes en

computadoras actuales.

También se usan extensiones y variaciones del método Simplex

para realizar análisis posóptimo (que incluye el análisis de

sensibilidad) sobre el modelo.

Método Simplex


4/38

• El método Simplex es un procedimiento iterativo que permite

ir mejorando la solución a cada paso. El proceso concluye

cuando no es posible seguir mejorando más dicha solución.

Método Simplex


5/38

• Deberá tenerse en cuenta que este método sólo trabaja para

restricciones que tengan un tipo de desigualdad "≤" ycoeficientes independientes mayores o iguales a 0, y habrá

que estandarizar las mismas para el algoritmo. En caso de que

después de éste proceso, aparezcan (o no varíen) restriccionesdel tipo "≥" o "=" habrá que emplear otros métodos, siendo el

más común el método de las Dos Fases.

Método Simplex


6/38

1. Esencia del Método Simplex.

El método Simplex es un procedimiento algebraico, Sinembargo, sus conceptos fundamentales son geométricos, por lo

que la comprensión de estos conceptos geométricos nos

proporciona una fuerte intuición sobre como opera el métodoSimplex y porque es tan eficiente.

Método Simplex


7/38

Figura 1

Método Geométrico

RegiónFactible

(0,0)

(0,9)

(4,0)

Max Z = 3x1 + 5x2

Sujeto a:

x1 ≤ 4

2x2 ≤ 12

3x1

+ 2x2

≤ 18

x1 ≥ 0 , x2 ≥ 0

x2

x1

x1 = 4

2x2 = 12

3x1 + 2x2 = 18

(4,6)

(0,6)

(6,0)


8/38

Método Simplex

Como pudo apreciarse en el ejemplo, el método Simplex es un algoritmoiterativo (procedimiento de solución sistemático que repite una serie de pasos

fija, llamada iteración, hasta que se obtiene el resultado deseado) con lasiguiente estructura:


9/38

Método Simplex

Traducimos el procedimiento geométrico acabado de describir en un procedimiento algebraico que se pueda usar.

El procedimiento algebraico se basa en resolver sistemas de ecuaciones.

Entonces el primer paso para preparar el método Simplex es convertir las

restricciones funcionales de desigualdad en restricciones de igualdad

equivalentes (las restricciones de no negatividad se dejan como

desigualdades porque se manejan por separado).

“La conversión en igualdades se logra con la introducción de variables de

holgura”.

3. Preparación para el método Simplex.


10/38

Método Simplex

Por ejemplo:

Para la siguiente restricción x1 ≤ 4, la variable de holgura se define

como x3 = 4 – x1, que es la holgura que queda en el lado izquierdo de la

desigualdad. Entonces: x1 + x3 = 4, con x3 ≥ 0.

x1 ≤ 4,

holgura

x3 = 4 – x1

x1 + x3 = 4 , con x3 ≥ 0.



11/38

Método Simplex

Introducimos las variables de holgura en nuestro ejemplo:

Maximizar Z = 3x1 + 5x2

S. a :

x1 + ≤ 42x2 + ≤ 12

3x1+ 2x2 + ≤ 18

x j ≥ 0, para j = 1,2,3,4,5

A esta forma se le da el nombre de forma aumentada del problema.


x3x4

x5

==

=


12/38

Método Simplex

Terminología para la forma aumentada:

Una solución básica tiene las siguientes propiedades:1) Cada variable se designa ya sea como variable básica (x3, x4, x5) o variable NO

básica (x1, x2).

2) El numero de variables básicas (3) es igual al número de restricciones funcionales

(3). Por lo tanto, el número de variables no básicas (2) es igual al número total de

variables (5) menos el número de restricciones funcionales (3).

3) Las variables no básicas se igualan a cero.

4) Los valores de las variables básicas se obtienen como la solución simultanea del

sistema de ecuaciones.

5) Si las variables básicas satisfacen las restricciones de no negatividad, la solución

básica es una solución.


13/38

Método Simplex

4. Algebra del Método Simplex.

Paso inicial: Se eligen como var iabl es no básicas a x 1

y x 2

, por lo tanto se igualan a

cero ( x1 = 0 y x2 = 0). El sistema de ecuaciones es:

(1) x1 + x3 = 4

(2) 2x2 + x4 = 12

(3) 3x1 + 2x2 + x5 = 18

con x1 = 0 y x2 = 0

Entonces reemplazando éstos valores en las ecuaciones anteriores y resulta:

x3 = 4, x4 = 12, x5 = 18 (corresponde a la solución básica BF inicial) (0,0,4,12,18)

Prueba de optimalidad:

Z = 3x1 + 5x2, de manera que Z = 0 para la BF inicial.

No es óptima porque al aumentar el valor de cualquier variable no básica (x1 o x2), elvalor de Z aumenta.


14/38

Método Simplex

Iteración 1 (paso 1): Determinación de la dirección de movimiento: Se debe elegir

entre las variables no básicas, cual debe aumentar su valor.

Como la función objetivo es Z = 3x1+5x2, la tasa de mejoramiento de x2, es mayor, por lo que se elige a esta para aumentar su valor. Se la denomina var iable básica

entr ante, y l a otra vari able se iguala a cero (x 1 = 0) .

Iteración 1 (paso 2): Determinación de donde detenerse: esto nos dice cuanto

aumentar la variable básica entrante x2 antes de detenerse :

(1) x1 + x3 = 4

(2) 2x2 + x4 = 12

(3) 3x1+ 2x2 + x5 = 18

Con x1 = 0

Reemplazamos y obtenemos

x3 = 4 x4 = 12 – 2x2 x5 = 18 – 2x2


15/38

Método Simplex

Iteración 1 (paso 2):

Lo que buscamos es cuanto puede crecer x2 sin violar restricciones de no negatividad,

así: x3 = 4 ≥ 0; no hay cota superior sobre x2

x4 = 12 - 2x2 ≥ 0; x2 ≤ 12/2 = 6 (cociente mínimo)

x5 = 18 - 2x2 ≥ 0; x2 ≤ 18/2 = 9

Entonces x2 crece hasta 6, y en este punto x4 llega a cero (6,0).

Si x2 aumenta, x4 se vuelve negativa, lo que violaría la factibilidad. Este cálculo

recibe el nombre de prueba del cociente mínimo.

De esta manera x4 es la var iabl e básica que sale para la iteración 1.


16/38

Método SimplexIteración 1: Solución (paso3): Convertir el sistema de ecuaciones a una forma más

conveniente para llevar a cabo la prueba de optimalidad. El sistema de ecuaciones que

tenemos es:

(0) Z - 3x1 - 5x2 = 0

(1) x1 + x3 = 4

(2) 2x2 + x4 = 12

(3) 3x1 + 2x2 + x5 = 18

Para reproducir el patrón de coeficientes de x4 (0,0,1,0) como los nuevos coeficientes

de x2 (pasar los coeficientes de x2 (-5,0,2,2) a la forma de coeficientes de x4

(0,0,1,0)), se pueden realizar cualquiera de los dos tipos de operaciones algebraicaselementales:

1) Multiplicar (o dividir ) una ecuación por una constante distinta de cero.

2) Sumar (o restar) un múltiplo de una ecuación a (o de) otra ecuación.


17/38

Método Simplex

1

2

(0) Z - 3x1 - 5x2 = 0(1) x1 + x3 = 4(2) 2x2 + x4 = 12

(3) 3x1 + 2x2 + x5 = 18

En la ecuación (2), el coeficiente de x2 convertirlo de 2 a 1, dividiendo por 2

(2) 2x2 + x4 = 12

(2*) x2

+ 1/2 x4

= 6

Iteración 1: Solución (paso3):

Los coeficientes de x2 en el sistema de ecuaciones anterior son (-5, 0, 2, 2) y se

intenta convertirlos en (0, 0, 1, 0).

é


18/38

Método Simplex

Ecuación (0). Multiplicar a (2*) por 5 y sumar a (0)

(0) Z - 3x1 – 5x2 = 0

(2*) x2 + 1/2 x4 = 65

(0) Z - 3x1 – 5x2 = 0(2*) 5x2 + 5/2 x4 = 30

(0*) Z - 3x1 + 5/2 x4 = 30

Ecuación (1). Se mantiene por lo que no contiene x2(1*) x1 + x3 = 4

(2*) x2 + 1/2 x4 = 6-2


(3) 3x1 + 2x2 + x5 = 18

(3) 3x1 + 2x2 + x5 = 18(2*) - 2x2 - x4 = - 12

(3*) 3x1 - x4 + x5 = 6

é d i l


19/38

Método SimplexLas nuevas ecuaciones serían:

(0*) Z - 3x1 + 5/2x4 = 30

(1) x1 + x3 = 4(2*) x2 + 1 /2 x4 = 6

(3*) 3x1 + - x4 + x5 = 6

Como x1 y x4 son iguales a cero, las ecuaciones en esta forma llevan a

la nueva solución BF (0,6,4,0,6), lo que da Z = 30.

Lo que hemos utilizado para resolver las ecuaciones se conoce como

método de eliminación de Gauss-Jordan.

é d Si l


20/38

Método SimplexPrueba de optimalidad para la nueva solución BF:

La ecuación (0) actual Z = 30 + 3x1 - 5/2 x4

No es óptima porque al aumentar el valor de una variable no básica (x1), el valor deZ aumenta.

Iteración 2: solución óptima que resulta:

Como la función Z = 30 + 3x1 - 5/2 x4, se pude aumentar si aumenta el valor de x1,pero no el de x4, se elige como primer paso a x1 como la variable básica entrante.

El segundo paso nos dice cuanto se puede aumentar x1 (con x4 = 0), las ecuaciones

nos dan:x3 = 4 - x1 ≥ 0; x1 ≤ 4/1 = 4

x2 = 6 ≥ 0; no hay cota superior sobre x1

x5 = 6 - 3x1 ≥ 0; x1 ≤ 6/3 = 2 (mínimo)

Por lo tanto la prueba del cociente mínimo indica que x5 es la variable básica que

sale.

Mé d Si l


21/38

Método SimplexPrueba de optimalidad para la nueva solución BF:

El tercer paso es sustituir a x5 por x1 como variable básica, se realizan operaciones

algebraicas en el sistema de ecuaciones actual para reproducir el patrón decoeficientes de x5 (0,0,0,1) como los nuevos coeficientes de x1.

(0*) Z - 3x1 + 5/2x4 = 30

(1*) x1 + x3 = 4

(2*) x2 +1/2 x4 = 6

(3*) 3x1 + - x4 + x5 = 6

En la ecuación (3*), el coeficiente de x1 convertirlo de 3 a 1, dividiendo por 3

(3*) 3x1 - x4 + x5 = 6

(3**) x1 - 1/3 x4 + 1/3 x5 = 2

1

3

Mé d Si l


22/38

Método Simplex


(0*) Z - 3x1 + 5/2 x4 = 30

(3**) x1 - 1/3 x4 + 1/3 x5 = 23

(0*) Z - 3x1 + 5/2 x4 = 30

(3**) 3x1 - x4 + x5 = 6

(0**) Z + 3/2 x4 + x5 = 36

Ecuación (1). Multiplicar a (3**) por -1 y sumar a (1*)

(1*) x1 + x3 = 4(3**) x1 - 1/3 x4 + 1/3 x5 = 2

(2**) x2 + 1/2 x4 = 6

-1

(1**) + x3 + 1/3 x4 - 1/3 x5 = 2

Ecuación (2*). Se mantiene por lo que no contiene x1

Mét d Si l


23/38

Método SimplexEsto lleva al siguiente sistema de ecuaciones:

(0**) Z + 3/2 x4 + x5 = 36

(1**) x3 + 1 /3 x4 - 1/3x5 = 2(2**) x2 + 1 /2 x4 = 6

(3**) x1 - 1/3 x4 + 1/3x5 = 2

Por lo tanto, la siguiente solución BF es (2,6,2,0,0), lo que da Z = 36. Para aplicar la

prueba de optimalidad a esta nueva solución BF, se usa la ecuación (0):

Z = 36 - 3/2 x4 - x5, al incrementar ya sea x4, o x5, el valor de Z disminuirá, de manera

que ninguna solución BF adyacente es tan buena como la actual.

Entonces esta solución es óptima.

Mét d Si l


24/38

• Maximizar Z = 300 x + 500 y

• Sujeto a:

x ≤ 42y ≤ 12

3x + 2y ≤ 18

x ≥ 0

y ≥ 0

Método Simplex

EJERCICIO

Mét d Si l


25/38

Método Simplex

Maximizar Z = 30x1 + 50x2

x1 + 3x2 ≤ 200x1 + x2 ≤ 100x1 ≥ 20

x2 ≥ 10

EJERCICIO

Mét d Si l


26/38

Método Simplex

EJERCICIOLo llevamos a la forma aumentada

Forma NormalZ = 30x1 + 50x2

x1 + 3x2 ≤ 200x

1+ x

2≤ 100

x1 ≥ 20x2 ≥ 10

Forma aumentada

Z = 30x1 + 50x2x1 + 3x2 + x3 = 200x1 + x2 + x4 = 100

- x1 + x5 = - 20

- x2 + x6 = - 10

Variables No Básicas x1 y x2Variables Básicas: x3, x4, x5 y x6ó Variables de Holgura

- x1 ≤ - 20- x2 ≤ - 10

Método Simple


27/38

Método Simplex


Primer Paso igualamos las variables No Básicas a cero, x 1

= 0 y x 2

= 0

x3 = 200 x4 = 100 x5 = - 20 x6 = -10

BF ( 0,0,200,100,-20,-10)

Z = 30x1 + 50x2Z = 30 (0) + 50 (0)Z = 0 No es óptimo, ya que al dar valores a x1 y x2, Z aumenta

Método Simplex


28/38

Método Simplex


Iteración: Primer Paso en Z buscamos el mayor cociente, que es 50 del x 2, que será la

Variables Entrante, para determinar la Variable Saliente

x3 = 200 - 3x2 ≥ 0 x2 ≤ 200/3

x4 = 100 - x2 ≥ 0 x2 ≤ 100x5 = - 20x6 = - 10 + x2 ≥ 0 x2 ≥ 10

x1 = 0

Entonces la variable entrante es x2 y la variable saliente es x3

x3 menor cociente

La BF ( 0 , 200/3 , 0 , 100/3 , -20 , 170/3 )

Método Simplex


29/38

1

3

Método SimplexEntonces la variable entrante es x2 (-50,3,1,0,-1) y la variable saliente es x3, (0,1,0,0,0)y la debemos llevar a esa forma.

(0) Z - 30x1

- 50x2

= 0(1) x1 + 3x2 + x3 = 200(2) x1 + x2 + x4 = 100(3) - x1 + x5 = - 20(4) - x2 + x6 = - 10

En la ecuación (1), el coeficiente de x2 convertirlo de 3 a 1, dividiendo por 3

(1) x1 + 3x2 + x3 = 200

(1*) 1/3 x1 + x2 + 1/3 x3 = 200/3


(0) Z - 30x1 - 50x2 = 0(1*) 1/3 x1 + x2 + 1/3 x3 = 200/350

(0*) Z - 40/3x1

+ 50/3x3

= 10 000/3

(0*) 3 Z - 40 x1 + 50 x3 = 10 000

Método Simplex


30/38

Método SimplexEcuación (2), multiplicar a (1*) por -1 y sumar a (2)

(2) x1 + x2 + x4 = 100(1*) 1/3 x1 + x2 + 1/3 x3 = 200/3-1

(2*) 2/3x1 - 1/3 x3 + x4 = 100/3

La ecuación (3), se mantiene

(3*) - x1 + x5 = - 20

Ecuación (4), sumar a (1*)

(4) - x2 + x6 = - 10(1*) 1/3 x1 + x2 + 1/3 x3 = 200/3+

(4*) 1/3 x1 + 1/3 x3 + x6 = 170/3

(0*) Z = 10 000/3 + 40/3 x1 - 50/3 x3El nuevo Z es:

Si damos un valor a x1, el valor de Z aumentará, existe un mayor valor óptimo.

(2*) 2 x1 - 1 x3 + 3 x4 = 100

(4*) 1 x1 + 1 x3 + 3 x6 = 170

Método Simplex


31/38

Método SimplexLas nuevas ecuaciones son:

(0*) Z - 40/3 x1 + 50/3 x3 = 10 000/3(1*) 1/3 x1 + x2 + 1/3 x3 = 200/3(2*) 2/3 x1 - 1/3 x3 + x4 = 100/3(3*) - x1 + x5 = - 20(4*) 1/3 x1 + 1/3 x3 + x6 = 170/3

Entonces la variable entrante es x1

(1*) x2 = 200/3 - 1/3x1 ≥ 0 -1/3 x1 ≥ -200/3 x1 ≤ 200(2*) x4 = 100/3 - 2/3x1 ≥ 0 -2/3 x1 ≥ -100/3 x1 ≤ 50(3*) x5 = - 20 + x1 ≥ 0 x1 ≥ 20 x1 ≥ 20

(4*) x6 = 170/3 - 1/3 x1 ≥ 0

-1/3x1 ≥ - 170/3 x1 ≤ 170

x3 = 0

menor cociente

Entonces la variable entrante es x1 (-40/3 , 1/3 , 2/3 , -1, 1/3) y la variable saliente esx4, (0,0,1,0,0) y la debemos llevar a esa forma.

La BF ( 50 , 50 , 0 , 0 , 30 , 40 )

Método Simplex


32/38


3

2

Ecuación (2*), el coeficiente de x1 convertirlo de 2/3 a 1, multiplicando por 3/2

(2*) 2/3 x1 - 1/3x3 + x4 = 100/3

(2**) x1 - 1/2x3 + 3/2x4 = 50

Ecuación (0*). Multiplicar por 40/3 a (2**) y sumar a (0*)

(0*) Z - 40/3x1 + 50/3x3 = 10 000/3(2**) x1 - 1/2x3 + 3/2x4 = 50

(0**) Z + 10 x3 + 20x4 = 4 000

40

3

(0*) Z - 40/3 x1 + 50/3 x3 = 10 000/3(1*) 1/3 x1 + x2 + 1/3 x3 = 200/3(2*) 2/3 x1 - 1/3 x3 + x4 = 100/3(3*) - x1 + x5 = - 20(4*) 1/3 x1 + 1/3 x3 + x6 = 170/3

Método Simplex


33/38


Ecuación (1*). Multiplicar por -1/3 a (2**) y sumar a (1*)

(1*) 1/3 x1 + x2 + 1/3 x3 = 200/3(2**) x1 - 1/2x3 + 3/2x4 = 50

(1**) + x2 + 1/2 x3 - 1/2 x4 = 50

- 1

3

(0*) Z - 40/3 x1 + 50/3 x3 = 10 000/3(1*) 1/3 x1 + x2 + 1/3 x3 = 200/3(2*) 2/3 x1 - 1/3 x3 + x4 = 100/3(3*) - x1 + x5 = - 20(4*) 1/3 x1 + 1/3 x3 + x6 = 170/3

Ecuación (3*). Sumar (3*) + (2**)

(3*) - x1 + x5 = - 20(2**) x1 - 1/2x3 + 3/2x4 = 50

(3**) - 1/2 x3 + 3/2 x4 + x5 = 30

Método Simplex


34/38


Ecuación (4*). Multiplicar por -1/3 a (2**) y sumar a (4*)

(4*) 1/3 x1 + 1/3 x3 + x6 = 170/3(2**) x1 - 1/2x3 + 3/2x4 = 50

(4**) 1/2 x3 - 1/2 x4 + x6 = 40

- 1

3

(0*) Z - 40/3 x1 + 50/3 x3 = 10 000/3(1*) 1/3 x1 + x2 + 1/3 x3 = 200/3(2*) 2/3 x1 - 1/3 x3 + x4 = 100/3(3*) - x1 + x5 = - 20(4*) 1/3 x1 + 1/3 x3 + x6 = 170/3

El nuevo Z es:

Si damos un valor a x3 o x4 el valor de Z disminuirá, Ya no existe un mayor valoróptimo.

(0**) Z = 4 000 - 10 x3 - 20x4

Método Simplex


35/38


(0**) Z + 10 x3 + 20 x4 = 4 000(1**) + x2 + 1/2 x3 - 1/2 x4 = 50(2**) x1 - 1/2 x3 + 3/2 x4 = 50(3**) - 1/2 x3 + 3/2 x4 + x5 = 30(4**) + 1/2 x3 - 1/2 x4 + x6 = 40


36/38

MUCHAS GRACIAS POR SU ATENCION

Construcción de un Modelo


37/38




38/38


04 y 05 2016-04-20 y 27 metodo simplex - solución algebraica

Documents