08) PROGRAMACIÒN LINEAL
-
Upload
daniel-paniagua -
Category
Documents
-
view
37 -
download
0
Transcript of 08) PROGRAMACIÒN LINEAL
![Page 1: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/1.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 1/33
(08) PROGRAMACIÒN LINEALMETODO SIMPLEX
METODOS CUANTITATIVOS
PARA LA TOMA DEDECISIONES
![Page 2: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/2.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 2/33
METODO SIMPLEX Las relaciones en las restricciones de
un problema de PL forman
Un conjunto de ecuacionessimultaneas
Un sistema de ecuaciones linealessimultaneas tiene una solución únicasi
El numero de ecuaciones independientes es igual que el número de variables
![Page 3: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/3.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 3/33
METODO SIMPLEX Entonces , si se tienen , por ejemplo :
Tres ecuaciones con tres incógnitas , puede
encontrarse una solución única para cadavariable
![Page 4: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/4.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 4/33
METODO SIMPLEX ¿Qué pasa si hay más variables que
ecuaciones , por ejemplo , cuatro variables
y dos ecuaciones? Entonces es posible obtener muchas
soluciones ; en general un número infinitode soluciones
![Page 5: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/5.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 5/33
METODO SIMPLEX Este es el tipo de situación a la que se
aplica programación lineal
En 1947 , George Dantzig desarrollo elmétodo simplex.
Demostró que podía usarse una ecuacióncriterio ( la función objetivo) paraseleccionar de manera sistemática unasolución “optima” de entre muchas solucionesposibles
![Page 6: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/6.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 6/33
METODO SIMPLEX Además , este era un método general que
se podía aplicar a problemas de cualquier
tamaño . Las únicas limitaciones practicas son solo el
tiempo , costo y disponibilidad de unacomputadora
![Page 7: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/7.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 7/33
METODO SIMPLEX Este es un método general ; funciona
para cualquier problema de PL Para casos especiales , existen métodos
específicos de solución
![Page 8: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/8.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 8/33
METODO SIMPLEX
Restricciones aumentadas El método simplex utiliza una tabla , en la
cual hay una columna para cada variable y
un renglón para cada restricción. Además , cada restricción se debe expresar
en lo que algunas veces se llama
la forma estándar : como una igualdad
![Page 9: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/9.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 9/33
METODO SIMPLEX
Restricciones aumentadas Es decir , cada restricción en el problema PL
primero se debe de aumentar con variables
extra para convertirla en igualdad Se describirá como se aumentan las
restricciones y después se analiza en formabreve el método simplex
![Page 10: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/10.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 10/33
METODO SIMPLEX
Restricciones aumentadas Cualquier desigualdad puede convertirse en
una igualdad agregando ( o restando) solo
una variable extra . Entonces una restriccióndel tipo <= :
7 X 1 + 7 X 2 <= 49 Se convierte en
7 X 1 + 7 X2 + S 3 = 49
![Page 11: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/11.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 11/33
METODO SIMPLEX
Restricciones aumentadas Se ha agregado
UNA VARIABLE DE HOLGURA para que se absorba la holgura o la diferencia
en la que 7X1 + 7X2 puede ser menor que 49
El aumento de las restricciones del tipo <
siempre se debe de hacer de esta manera
![Page 12: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/12.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 12/33
METODO SIMPLEX
Restricciones aumentadas De igual forma , una restricción del tipo > :
X 2 > 2
se convierte en X 2 – S 4 = 2
Se ha restado una variable de excedente
para que se consuma el exceso de X 2 , o sealo que se pasa de 2
![Page 13: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/13.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 13/33
METODO SIMPLEX
Restricciones aumentadas No obstante , en este caso debe de agregarse
otra variable . Esta variable extra , llamada
VARIABLE ARTIFICIAL Se aumenta como sigue
X 2 > 2
Se convierte en X 2 – S 4 + A 5 = 2
![Page 14: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/14.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 14/33
METODO SIMPLEX
Restricciones aumentadas X 2 – S 4 + A 5 = 2
La razón de esto es que , si no se agrega
la variable artificial , Se violarían las restricciones de no
negatividad
Para comprenderlo , se dejara esta ecuaciónsin aumentar
![Page 15: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/15.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 15/33
METODO SIMPLEX
Restricciones aumentadas El método simplex comienza por hacer
todas las variables reales igual a cero.
Entonces , X 2 – S 4 = 2
Sea X 2 = 0
- S 4 = 2 S 4 = - 2
Esto , viola la regla de no negatividad
![Page 16: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/16.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 16/33
METODO SIMPLEX
Restricciones aumentadas No importa el hecho de que X 2 = 0 viola la
restricción original . En términos algebraicos
es legitimo La variable artificial opera para mantener
todas las variables no negativas cuando X 2
es menor que 2
Si X 2 = 0 , entonces S 4 = 0 y
X 2 – S 4 + A 5 = 2
![Page 17: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/17.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 17/33
METODO SIMPLEX
Restricciones aumentadas X 2 – S 4 + A 5 = 2
A 5 = 2
En resumen , se aumento una restricción deltipo > restando una variable de excedente ysumando una variable artificial ( - S + A )
¿Qué sucede con las restricciones que ya sonuna igualdad?
![Page 18: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/18.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 18/33
METODO SIMPLEX
Restricciones aumentadas La respuesta técnicamente correcta es que
no es necesario hacer nada si
una de las variables tiene coeficiente iguala uno y coeficiente 0 en todas las otrasrestricciones
De otra manera debe de agregarse unavariable artificial
![Page 19: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/19.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 19/33
METODO SIMPLEX
Restricciones aumentadas Se sugiere siempre agregar la variable
artificial y olvidar el caso especial de 1/0en los coeficientes
La razón para aumentar variables artificialesdespués será más clara
todas las variables que aparecen en
una restricción también deben deaparecer en la función objetivo
![Page 20: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/20.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 20/33
METODO SIMPLEX
Restricciones aumentadas Así , cada variable de holgura , de excedente
ò artificial que se aumenten también deben
de AGREGARSE A LA FUNCIÒN OBJETIVO ¿cuáles son sus coeficientes?
Para las variables de holgura o excedente larespuesta es fácil : SIEMPRE SERA CERO
![Page 21: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/21.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 21/33
METODO SIMPLEX
Restricciones aumentadas Esto significa que no importa si están en
la solución Ahora bien , las variables artificiales tienen
un problema diferente: no se desea que estén en la solución
final Recuérdese que solo se utilizan para evitar
que las variables de excedente violen lasreglas de no negatividad ( y para lasecuaciones)
![Page 22: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/22.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 22/33
METODO SIMPLEX
Restricciones aumentadas El que una variable artificial este en la
solución final significa que algo anda mal
Para mantenerlas fuera de la solución final ,se les asignara un coeficiente en la funciónobjetivo por lo menos 100 veces más grandeque cualquier otro coeficiente y con el signo
adecuado para garantizar que salgan
![Page 23: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/23.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 23/33
METODO SIMPLEX
Restricciones aumentadas Así , al maximizar se asignara
- MA En donde M es un numero muy grande Si se trata de minimizar , se seleccionara
+ MA Estas reglas para el aumento se resumen en
la tabla 8-1
![Page 24: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/24.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 24/33
Tipo de restricción Restricción Función objetivo
>= -S + A Max + 0 * S – MAMin + 0* S + MA
Agréguese a la :
TABLA 8.1
Reglas de aumento
![Page 25: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/25.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 25/33
METODO SIMPLEX
Restricciones aumentadas Nótese que :
Hay reglas fijas para cada tipo de
restricción y que Las variables de holgura y de excedente
siempre tienen coeficientes cero en lafunción objetivo
![Page 26: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/26.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 26/33
METODO SIMPLEX
Restricciones aumentadas Lo único que cambia es el signo para las
variables artificiales en la función objetivo
se seleccionan de manera que estas variablessalgan de la solución final
![Page 27: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/27.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 27/33
El Método Simplex en forma global El método simplex no es mas que
Un enfoque complicado de prueba y
error para resolver los problemas de PL Recuérdese que el método de prueba y error
que se describió en el capitulo anterior alresolver problemas en forma grafica
![Page 28: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/28.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 28/33
El Método Simplex en forma global Ahí se aprovecho el hecho de que por lo
menos un punto de intersección de la
frontera extrema es optimo Sencillamente se probaron estos puntos
usando la función objetivo
![Page 29: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/29.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 29/33
El Método Simplex en forma global El método simplex también emplea los puntos
de intersección , pero no prueba todos los
puntos Comienza en el origen y selecciona
los que dan mayor mejora en el valorde la función objetivo
![Page 30: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/30.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 30/33
El Método Simplex en forma global Así , al moverse de un punto de
intersección al otro , la función objetivo
siempre esta mejorando .Esto hace que el método simplex sea máseficaz que el método del capitulo anterior
En el diagrama de flujo de la figura 8-1 se
muestra el procedimiento completo
![Page 31: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/31.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 31/33
INICIO RELACIONES AUMENTADAS
CONSTRUCCIÒNDE TABLAINICIAL
¿ OPTIMO ?
FIN
IDENTIFICACIONDE VARIABLESENTRADA/SALIDA
DESARROLLODE LA TABLAREVISADA
![Page 32: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/32.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 32/33
El Método Simplex en forma global Se construye una tabla con una solución
inicial y se prueba si la solución es optima
Si no es optima ( la solución inicial nunca loes) se analiza la tabla y se prueba la nuevasolución
Este procedimiento se repite hasta que seencuentra una solución optima
![Page 33: 08) PROGRAMACIÒN LINEAL](https://reader030.fdocumento.com/reader030/viewer/2022020718/5572010d4979599169a0a7eb/html5/thumbnails/33.jpg)
5/17/2018 08) PROGRAMACIÒN LINEAL - slidepdf.com
http://slidepdf.com/reader/full/08-programacion-lineal 33/33
El Método Simplex en forma global Nótese que cada tabla representa una nueva
solución
En esta forma TABLA y SOLUCIÒN sonsinónimos
La función objetivo debe también mejoraren cada nueva tabla.