UNIVERSIDAD NACIONAL DEL CALLAO CURSO: METODOS CUNTITATVOS PARA LOS NEGOCIOS TEMA: METODO SIMPLEX DOCENTE: OSMAR BERMEO
Views 288 Downloads 4 File size 970KB
UNIVERSIDAD NACIONAL DEL CALLAO
CURSO: METODOS CUNTITATVOS PARA LOS NEGOCIOS TEMA: METODO SIMPLEX DOCENTE: OSMAR BERMEO CARRASCO
¿Qué es la Programación Lineal?
La Programación Lineal es un campo concerniente a la
optimización matemática dedicado a maximizar o minimizar una función lineal, denominada función objetivo y generalmente denotada por Z. Las variables de dicha función Z están sujetas a una serie de restricciones, las cuales estarán expresadas mediante un
sistema de desigualdades también lineales.
Formulación de un programación Lineal La formulación de un programa lineal implica el desarrollo de un modelo matemático que represente el problema administrativo o de otra area. Por lo tanto, para formular un programa lineal, es necesario entender cabalmente el problema administrativo al que se enfrenta. Una vez que se haya entendido, es posible comenzar a desarrollar la formulación matemática del problema. Los pasos en la formulación de un programa lineal son los siguientes: 1. Entender cabalmente el problema administrativo de otra area que se enfrenta. 2. Identificar el objetivo y las restricciones. 3. Definir las variables de decisión. 4. Utilizar las variables de decisión para escribir expresiones matemáticas de la función objetivo y de las restricciones.
Formulación de un programación Lineal
Definición del problema. Desarrollo de un modelo. Recolección de datos Datos. Desarrollo de una solución.
Pruebas de la solución. Análisis de los resultados.
Implementación de resultados.
A las etapas de planteamiento e interpretación, se les denominan usos de la Programación Lineal y a las cuales se les debe dar un énfasis especial en el desarrollo.
Para obtener una solución en un problema de Programación Lineal se utilizan diferentes métodos de solución, como el Método Simplex.
La Programación Lineal se plantea como un modelo matemático,
el
cual
se
desarrolla
durante
el
transcurso de la Segunda Guerra Mundial y donde su
objetivo primordial ganancias.
era planificar
los
gastos y
Las bases matemáticas de la Programación Lineal tienen su origen en los trabajos del matemático húngaro Janos Von Neuman (1903-1957), quien en
el año de 1928 publicó una famosa investigación sobre una nueva disciplina: la Teoría de Juegos.
La
Programación
Lineal
se
convirtió,
paulatinamente, en una herramienta fundamental de las matemáticas, tanto teóricas como aplicadas y que, sin lugar a dudas, al utilizar el álgebra y el álgebra de matrices se hizo muy popular en la Estadística pero, sobre todo, en la ya popular Teoría de Juegos.
¿Cómo resolver un Programación Lineal?
problema
de
En la mayoría de los casos, el camino para identificar una solución óptima será: 1) Plantear el problema; 2) Traducirlo a un modo algebráico; 3) Definir las restricciones y; 4) Buscar el óptimo dependiendo del método que se quiera aplicar. Este óptimo se puede encontrar a través de diferentes métodos.
El más general de ellos es el propuesto en 1947 por Dantzig, al cual se le conoce desde entonces como el
Método Simplex.
EL MÉTODO SIMPLEX. El Método Simplex es un algoritmo analítico que bien puede solucionar problemas de Programación Lineal. Además,
este
método
es
capaz
de
abordar
planteamientos más complejos que aquellos resueltos mediante el Método Gráfico, ya que no toma en cuenta restricción alguna para el número de variables.
El Método Simplex es un algoritmo iterativo que permite mejorar la solución a cada paso. La explicación matemática de esta mejora radica, principalmente, en que el algoritmo permite “trasladarse” de un vértice a otro del poliedro formado por las restricciones (conocido como el área posible de
resultados) de tal manera que el valor encontrado aumente o disminuya.
Por supuesto, este último procedimiento dependerá si la función objetivo se maximiza o minimiza. En todo caso, como el número de vértices que tiene un poliedro es finito entonces siempre se hallará una solución con el Método Simplex.
EJEMPLO El ejemplo original de George Dantzig se refería a la búsqueda de la mejor asignación de 70 personas a 70 puestos de trabajo. Este ejemplo fue el punto de partida para mostrar la utilidad de la Programación Lineal.
En este ejemplo histórico, la potencia de computación
necesaria para examinar todas las permutaciones, a fin de seleccionar la mejor asignación, es inmensa. Tan es así, que al calcularse el número de posibles configuraciones se encontró
que éste excedía al número de partículas en el universo.
Sin embargo, tan solo toma un momento encontrar la
solución óptima mediante el planteamiento del problema a través de la Programación Lineal y con la aplicación del Método Simplex.
Ventajas: La gran virtud del Método Simplex es su sencillez, es un método muy práctico, ya que tan solo trabaja con los coeficientes de la función objetivo (Z) y de las restricciones.
Es fácil de implementar y tiene una alta eficacia.
Limitaciones: Tal vez la mayor limitante de este método es que converge (se acerca) más lentamente hacia
el óptimo que otros métodos, ya que requiere un mayor número de iteraciones (tantas como
vértices tenga el poliedro).
APLICACIÓN DEL MÉTODO SIMPLEX. Un agricultor tiene una parcela de 1280 m² para dedicarla al cultivo de árboles frutales: naranjos, perales, manzanos y limoneros. Se pregunta de qué
manera debería repartir la superficie de su parcela, entre
las
variedades
antes
mencionadas,
para
conseguir el máximo beneficio sabiendo que cada naranjo necesita un mínimo de 32 m², cada peral 8 m², cada manzano 8 m² y cada limonero 24 m².
Dispone de 1800 horas de trabajo al año, de las
cuales cada naranjo necesita 30 horas al año, cada peral 5 horas, cada manzano 10 horas y, finalmente, cada limonero necesita 20 horas.
A causa de la sequía, el agricultor tiene restricciones
para el riego, ya que le han asignado 400 m³ de agua anuales. Las necesidades anuales son de 4 m³ por cada naranjo, 2 m³ por cada peral, 2 m³ por cada manzano y 4 m³ por cada limonero.
Finalmente,
los
beneficios
unitarios
para
el
agricultor son de $1000 por cada naranjo, $500 por cada peral, $400 por cada manzano y $600 por
cada limonero.
Si bien el planteamiento del problema es un poco extenso, los cáclulos realizados empíricamente serían aún más. Por ello, a continuación le
daremos solución utilizando el Método Simplex.
SOLUCIÓN. Lo primero que debe hacerse es determinar las denominadas “variables de decisión” y representarlas algebráicamente. En este caso: X1: Número de naranjos. X2: Número de perales. X3: Número de manzanos. X4: Número de limoneros. Posteriormente se determinan las restricciones y se
expresan como inecuaciones de las ya conocidas variables de decisión.
Estas restricciones se deducen de todas las necesidades que requiere cada árbol: terreno, horas
de trabajo anuales y riego. Para ello, se debe identificar lo siguiente:
Necesidades de terreno: 32X1 + 8X2 + 8X3 + 24X4 ≤ 1280 Necesidades de horas anuales: 30X1 + 5X2 + 10X3 + 20X4 ≤ 1800 Necesidades de riego: 4X1 + 2X2 + 2X3 + 4X4 ≤ 400
Una vez establecidas las restricciones, entonces se
expresan todas las condiciones implícitamente establecidas por la naturaleza de las variables: que
no sean negativas, que sean enteras, que sólo puedan tomar determinados valores.
En nuestro caso las restricciones son: a) El número
de árboles no puede ser negativo y; b) El total de árboles debe ser un número entero. Es decir:
Xi ≥ 0 y todo Xi es entero con i=1,2,3,…,n. Finalmente, se plantea la función objetivo: Maximizar Z(X1,X2,X3,X4)=1000X1+500X2+400X3+600X4
Por lo tanto, nuestro problema se reduce a resolver el
siguiente planteamiento: Max Z=1000X1+500X2+400X3+600X4 Sujeto a: 32X1 + 8X2 + 8X3 + 24X4 ≤ 1280 30X1 + 5X2 + 10X3 + 20X4 ≤ 1800 4X1 + 2X2 + 2X3 + 4X4 ≤ 400
con Xi ≥ 0 y todo Xi entero.
La solución de nuestro problema puede seguir una serie de pasos. PASO I) Igualar la función objetivo a cero. Z-1000X1-500X2-400X3-600X4=0 PASO II) Convertir todas las desigualdades en igualdades. 32X1 + 8X2 + 8X3 + 24X4=1280 30X1 + 5X2 + 10X3 + 20X4=1800 4X1 + 2X2 + 2X3 + 4X4=400
PASO III) Para cada nueva igualdad crear una variable ficticia llamada, generalmente, holgura. 32X1 + 8X2 + 8X3 + 24X4+H1=1280 30X1 + 5X2 + 10X3 + 20X4+H2=1800 4X1 + 2X2 + 2X3 + 4X4+H3=400
PASO IV) Construir la tabla inicial del Simplex y comezar su solución. ¿Cómo se construye? La tabla inicial del Simplex concentra toda la información de las igualdades así como también el punto de partida para la función objetivo Z.
Tabla inicial del Simplex. BASE
X1
X2
X3
X4
H1
H2
H3
SOL.
32
8
8
24
1
0
0
1280
H2
30
5
10
20
0
1
0
1800
H3
4
2
2
4
0
0
1
400
Z
-1000
-500
-400
-600
0
0
0
0
H1
Toda vez que la tabla inicial del Simplex se ha
creado, podemos observar que en dicha tabla se aprecian dos matrices. La formada por las variables
de decisión (roja) y la matriz formada por las holguras (azul). Esta última se conoce como la
matriz identidad. La idea, grosso modo, es “llevar” a la matriz en rojo a una matriz como la azul.
Para ello es necesario lo siguiente:
1) Identificar la columna pivote. 2) Identificar la fila pivote. 3) Hacer unitario el elemento pivote, que no es otra cosa más que el número donde se cruzan la columna pivote y la fila pivote.
¿Cómo identificar la columna pivote? Esta columna se define al seleccionar el número más negativo en la función Z. En nuestro caso es el -1000.
¿Cómo identificar la fila pivote? Una vez identificada la columna pivote entonces la solución de cada fila, sin tomar en cuenta la fila de la función objetivo Z, se
divide entre su correspondiente coeficiente de la columna pivote.
El
número
positivo
más
pequeño
de
estas
divisiones determinará a la fila pivote. Es importante mencionar que no se toman aquellas divisiones con
un resultado negativo y tampoco aquellas divisiones entre cero.
Fila pivote
Elemento pivote
BASE
X1
X2
X3
X4
H1
H2
H3
SOL.
Div.
32
8
8
24
1
0
0
1280
1280/32=40
H2
30
5
10
20
0
1
0
1800
1800/30=60
H3
4
2
2
4
0
0
1
400
400/4=100
Z
-1000
-500
-400
-600
0
0
0
0
H1
Columna pivote
Como el número positivo más pequeño de las tres divisiones es 40 entonces éste define a la fila pivote. Si existen resultado negativos o bien divisiones entre 0 entonces no se toman dichas divisiones. Por su parte, si existen dos divisiones con el mismo resultado entonces se toma cualquiera de ellos.
A la intersección de la “columna pivote” y la “fila pivote” se le conoce como “elemento pivote”. En nuestro caso es 32. Si continuamos con el Método Simplex entonces este último elemento ahora debe hacerse unitario.
Es decir, se debe buscar un número que al multiplicarlo por 32 nos de como resultado 1.
Es claro que el número es 1/32. Ello quiere decir que debemos multiplicar toda la fila pivote por
1/32. El resultado de ello es la siguiente tabla:
BASE
X1
X2
X3
X4
H1
H2
H3
SOL.
1
1/4
1/4
3/4
1/32
0
0
40
H2
30
5
10
20
0
1
0
1800
H3
4
2
2
4
0
0
1
400
Z
-1000
-500
-400
-600
0
0
0
0
H1
Al definir el elemento pivote entonces la variable de decisión X1 toma el lugar de la variable holgura H1 en la base. Se dice que X1 entra en la solución y H1 sale.
Ya que hemos hecho el elemento pivote unitario entonces el objetivo es hacer “ceros” tanto arriba como abajo de dicho elemento pivote, según sea el caso. BASE
X1
X2
X3
X4
H1
H2
H3
SOL.
1
1/4
1/4
3/4
1/32
0
0
40
H2
30
5
10
20
0
1
0
1800
H3
4
2
2
4
0
0
1
400
Z
-1000
-500
-400
-600
0
0
0
0
X1
Es decir, multiplicamos la fila pivote por -30 y se la sumamos (entrada por entrada) a la fila de H2,
posteriormente multiplicamos la fila pivote por -4 y se la sumamos a la fila de H3. Finalmente, multiplicamos la fila pivote por 1000 y se la sumamos a la fila de Z. Los resultados se pueden apreciar en la siguiente tabla.
Nueva fila pivote
Nuevo elemento pivote
BASE
X1
X2
X3
X4
H1
H2
H3
SOL.
Div.
1
1/4
1/4
3/4
1/32
0
0
40
160
H2
0
-5/2
5/2
-5/2
-15/16
1
0
600
-240
H3
0
1
1
1
-1/8
0
1
240
240
Z
0
-250
-150
150
125/4
0
0
40000
X1
Nueva columna pivote
Toda
vez
que
hemos
realizado
correctamente
las
operaciones anteriores entonces el procedimiento se repite desde el paso en que se identifica a la columna pivote.
Nuevamente al hacer el elemento pivote unitario entonces multiplicamos la nueva fila pivote por 5/2 y se la sumamos a la fila de H2. Posteriormente multiplicamos la nueva fila pivote por -1 y se la sumamos a la fila de H3.
Por último, multiplicamos la nueva fila pivote por 250 y se la sumamos a la fila de la función objetivo Z.
Los resultados que se presentan en la siguiente tabla implican que el algoritmo se ha terminado.
¿Por qué? El Método del Simplex concluye cuando en toda la fila de la función objetivo Z ya no tenemos ningún número negativo.
Como puede apreciarse en la tabla, ya no tenemos números negativos en la fila de Z. Es decir hemos encontrado una solución que optimiza (maximiza) nuestro problema. BASE
X1
X2
X3
X4
H1
H2
H3
SOL.
4
1
1
3
1/8
0
0
160
H2
10
0
5
5
-5/8
1
0
1000
H3
-4
0
0
-2
-1/4
0
1
80
Z
1000
0
100
900
125/2
0
0
80000
X2
Ya no hay números negativos !!!
La interpretación de los resultados, en la última tabla, es la siguiente:
Como la variable X2 entró en la solución eso quiere decir que tomará un valor y éste será de 160. Por su parte, como las variables X3 y X4 no entraron en la solución eso quiere decir que serán 0.
Además, también la variable X1 salió de la solución, lo cual implica que X1=0. Asimismo, como la variable de holgura H1 salió de la solución entonces ello implica que dicha variable será 0. Por último, en la última tabla se aprecia que la variable de holgura H2=1000 y H3=80.
Sustituyendo los valores encontrados en las restricciones, se obtiene lo siguiente: 32(0) + 8(160) + 8(0) + 24(0) + H1= 1280
30(0) + 5(160) + 10(0) + 20(0) + H2= 1800 4(0) + 2(160) + 2(0) + 4(0) + H3= 400
Donde:
1280=1280 entonces H1=0 800+H2=1800 entonces H2=1000 320+H3=400 entonces H3=80
Por lo tanto, estos son los valores para la mejor estrategia del agricultor quien, a su vez, obtendrá un beneficio máximo de Z=500(160)=80000.
RESÚMENES DE LOS MÉTODOS DE SOLUCIÓN GRÁFICA Metodo de la isoutilidad 1 Graficar todas las restricciones y encontrar la región factible. 2. Seleccionar una recta de utilidad (o de costo) específica(o) y trazar la gráfica para encontrar la pendiente. 3. Mover la recta de la función objetivo en la dirección de aumento de la utilidad (o de la disminución del costo), conservando la pendiente. El
último punto que se toca en la región factible es la solución óptima. 4. Determinar los valores de las variables de decisión en este último punto y calcular la utilidad (o el costo).
RESÚMENES DE LOS MÉTODOS DE SOLUCIÓN GRÁFICA Metodo punto esquina 1.-Graficar todas las restricciones y encontrar la región factible. 2. Encontrar los puntos esquina de la región factible. 3. Calcular la utilidad (o el costo) en cada uno de los puntos esquina factibles.
4. Seleccionar el punto esquina con el mejor valor de la función objetivo determinado en el paso 3. Esta es la solución óptima.
Resuelva el siguiente problema por el método simplex
Añadiendo al modelo las variables de holgura que corresponden
Siendo el coste reducido de las variables no básicas
Iteración 1 - Entra en la base X2 ya que tiene el costo reducido negativo, y de todos los negativos, el mayor en valor absoluto. Sale de la base: