cap3 solucion del modelo de prog lin
TRANSCRIPT
CAPITULO III
SOLUCION DEL MODELO DE
PROGRAMACION LENEAL
Docente: Juan Carlos Vargas Reinaga
Existen varios métodos que permiten solucionar el problema de
programación lineal como son:
El método grafico
El algoritmo simplex
Los métodos penalizados
El método dual simplex
INTRODUCCION
3
Uno de los métodos mas simples de solución de un modelo de
programación lineal es el método grafico, este método tiene dos
características especiales:
Sirve para resolver problemas en una dos y tres dimensiones.
Se pueden consolidar importantes interpretaciones de tipo
geométrico y conceptual en relación a la teoría de programación
lineal.
METODO GRAFICO
4
DESVENTAJA
Este método gráfico tiene la desventaja que sólo permite la
solución de problemas que tengan dos variables de aquí que
la mayoría de los problemas de programación lineal se
resuelvan utilizando como base el método simplex.
5
ENFOQUE GRÁFICO DE SOLUCIÓN
Para obtener la solución al modelo utilizando el enfoque gráfico, se
debe:
Representar una región o área factible.
Calcular el valor máximo o mínimo de la función objetivo en la
región factible.
6
PROBLEMA
La fábrica de Hilados y Tejidos "SALAZAR" requiere fabricar dos
tejidos de calidad diferente T y T’; se dispone de 500 Kg de hilo a,
300 Kg de hilo b y 108 Kg de hilo c. Para obtener un metro de T
diariamente se necesitan 120 gr de a, 150 gr de b y 72 gr de c;
para producir un metro de T’ por día se necesitan 200 gr de a, 100
gr de b y 27 gr de c.
El T se vende a $ 4000 el metro y el T’ se vende a $ 5000 el metro.
Si se debe obtener el máximo beneficio, ¿cuántos metros de T y T’
se deben fabricar?
7
MODELIZACIÓN MEDIANTE PROGRAMACIÓN LINEAL
VARIABLES DE DECISION
XT: Cantidad de metros diarios de tejido tipo T a fabricar
XT’: Cantidad de metros diarios de tejido tipo T’ a fabricar
RESTRICCIONES
0,12XT + 0,2XT’ <= 500 Hilo “a”
0,15XT + 0,1XT’ <= 300 Hilo “b”
0,072XT + 0,027XT’ <= 108 Hilo “c”
Las restricciones de no negatividad no son necesarias en este
ejemplo dado que se trata de un ejercicio de maximización, cuando
el ejercicio sea de minimización lo más recomendado es incluirlas.
FUNCIÓN OBJETIVO
(fo) MAX Z = 4000XT + 5000XT’
8
SOLUCIÓN MEDIANTE MÉTODO GRÁFICO
PASO 1: GRAFICAR LAS RESTRICCIONES
Para iniciar con el trazado de las restricciones es indispensable
igualar las restricciones a 0, de esta manera podemos mediante
despeje de ecuaciones iniciar con la tabulación que nos otorgará
las coordenadas para elaborar cada una de las gráficas.
Además dado que se trabajará en el plano cartesiano sería
prudente renombrar las variables
XT = x
XT' = y
Igualamos las restricciones,
0,12x + 0,2y = 500
0,15x + 0,1y = 300
0,072x + 0,027y = 108
9
Si analizamos la primera restricción, hallamos las primeras dos
coordenadas. Para hallar las coordenadas regularmente
llevamos una de las variables a cero, para de esta manera
despejar más fácilmente la segunda.
Por ejemplo,
para un x = 0
0,12(0) + 0,2y = 500
0,2y = 500
500/0,2 = y
y = 2500
y para un y = 0
0,12x + 0,2(0) = 500
0,12x = 500
x = 500/0,12
x = 4167
10
11
12
13
En el siguiente gráfico se muestra el polígono solución de color gris
(región factible), en este conjunto es donde cada coordenada cumple
con todas las restricciones, las cuales se caracterizan por ser
restricciones de menor o igual y esta característica se representa con
una flecha hacía abajo.
14
Una vez se llega a este punto es indispensable saber que las
soluciones óptimas se alojan en los vértices del polígono
solución (color gris) y que identificar a la solución óptima es
cuestión de elegir la mejor alternativa dependiendo de las
herramientas disponibles (tecnológicas y conocimientos
matemáticos).
La primera opción es la geométrica, esta depende de trazar la
ecuación que representa a la función objetivo (este paso consiste
en realizar el mismo procedimiento de las restricciones).
Función objetivo
Max Z = 4000x + 5000y
igualamos a 0
4000x + 5000y = 0
15
Luego tabulamos para obtener las coordenadas necesarias para
elaborar la gráfica correspondiente a la ecuación (es
recomendable más de dos coordenadas, incluyendo la
coordenada (x = 0, y = 0).
16
17
Una vez se ha elaborado la función objetivo (línea negra)
sacamos replicas perpendiculares a esta que se encuentren con
cada vértice, y solo en el caso en que la línea imaginaria
perpendicular a la función objetivo no corte el polígono solución
se ha encontrado la solución óptima.
En otras palabras trasladamos la función objetivo por todo el
polígono conservando la perpendicularidad con la original, la
detenemos en los vértices y evaluamos si esta corta o no el
conjunto solución.
18
19
Claramente solo en el punto "B", es decir en el vértice formado por
la intersección de las ecuaciones 1 y 2, la línea imaginaria no
corta el polígono solución, entonces es este punto el
correspondiente a la coordenada óptima.
Para hallar el valor de esta coordenada es indispensable recurrir a
la resolución de ecuaciones lineales 2x2, y se pueden considerar
varios métodos de solución entre ellos:
Método por sustitución
Método por igualación
Método por reducción o Eliminación
Método por eliminación Gauss
Método por eliminación Gauss - Jordán
Método por determinantes
20
El método por reducción o eliminación consiste en igualar los
coeficientes de una de las variables multiplicando una o las dos
ecuaciones, teniendo en cuenta que estos coeficientes queden
iguales pero con signos contrarios.
Ecuación 1 0,12x + 0,2y = 500
Ecuación 2 0,15x + 0,1y = 300 multiplicamos por (-2)
-0,30x - 0,2y = -600
Sumando -0,18x = -100
x = 555,55
21
luego reemplazamos x = 555,55 en cualquiera de las dos
ecuaciones originales con el objetivo de despejar "y".
Ecuación 1 0,12x + 0,2y = 500
Reemplazamos 0,12(555,55) + 0,2y = 500
66,666 + 0,2y = 500
y = 2166,67
x = XT
y = XT'
XT = 555,55
XT' = 2166,67
22
reemplazando las variables en la función objetivo tenemos :
Zmax = 4000XT + 5000XT'
Zmax = 4000(555,55) + 5000(2166,67)
Zmax = 13.055.550
Ahora podemos cotejar los resultados con los obtenidos mediante
resolución por Solver - Excel, una herramienta muy útil al momento
de resolver ejercicios mediante el método gráfico es una calculadora
graficadora, como es el caso de la calculadora de encarta disponible.
23
ANALISIS E INTERPRETACION DEL METODO GRAFICO
El espacio achurado S se denomina REGION FACTIBLE y es
el conjunto que agrupa a los puntos que cumplen con todas
las restricciones y que corresponden a la intersección de los
hiperplanos dominio de cada una de las restricciones.
Los vértices de la región factible S, corresponde a la
intersección de dos o mas restricciones y se obtienen
resolviendo las ecuaciones que corresponden a estas
restricciones.
24
La solución optima del problema siempre será un vértice de la
región factible S.
Las restricciones que intervienen en el problema pueden ser de
tres tipos:
Restricciones ACTIVAS; que tienen dos características pasan
por el punto optimo y hacen uso total de los recursos.
Restricciones INACTIVAS, que son aquellas que no pasan
por el punto de análisis, en este caso el optimo; por tanto no
hacen uso total del recurso limitado y sus variables de
compensación toman valores diferentes de cero.
25
Restricciones REDUNDANTES, que son aquellas que
además de no pasar por el punto optimo en cuestión, no
limitan ni participan de la región factible, lo que significa
que la inclusión o no de esta restricción no modificara la
región factible tampoco la solución optima.
26
ALGORITMO SIMPLEX
El método simplex es un algoritmo que aplica un procedimiento
iterativo de solución.
En su forma sistémica el algoritmo simplex considera tres fases
fundamentales: Fase inicial, la fase de control del optimo y la
fase iterativa.
Cada una de estas fases consta de pasos importantes en su
desarrollo.
27
MECÁNICA DEL MÉTODO SIMPLEX
FASE INICIAL:
Paso 1 : Colocar el problema en su formulación estándar
Paso 2 : Plantear la tabla o solución inicial, precisando las variables
básicas y no básicas de inicio (iteración 0)
FASE DE CONTROL
Paso 3 : Verificar si todos los coeficientes de la fo son positivos (caso
MAX), si son positivos entonces se puede decir que ya se
encontró la solución optima, si no vaya al siguiente paso.
Paso 4 : Realizar un cambio de base
Aplicar la regla de entrada y la regla de salida de la base
Encontrar el pivote.
28
FASE ITERATIVA
Paso 5 : Aplicar operaciones elementales de fila y columna
Utilizar el método de Gauss Jordán y hallar la nueva
solución básica
Paso 6 : Volver a la fase de control.
29
Ejemplo del método Simplex:
Maximizar
Z = 3x1 + 2x2
Sujeto a:
2x1 + x2 ≤ 18
2x1 + 3x2 ≤ 42
3x1 + x2 ≤ 24
x1 ≥ 0 , x2 ≥ 0
30
1. CONVERTIR LAS DESIGUALDADES EN IGUALDADES
Se introduce una variable de holgura para cada una de las
restricciones, este caso s1, s2, s3 para convertirlas en igualdades
y formar el sistema de ecuaciones estándar.
Usando en simplex el siguiente criterio:
Signo : Introducir
≤ sn
FORMA ESTANDAR:
2x1 + x2 + s1 = 18
2x1 + 3x2 + s2 = 42
3x1 + x2 + s3 = 24
31
2. IGUALAR LA FUNCIÓN OBJETIVO A CERO Y DESPUÉS
AGREGAR LA VARIABLES DE HOLGURA DEL SISTEMA
ANTERIOR
Z - 3 x1 - 2 x2 = 0
Para este caso en particular la función objetivo ocupa la ultima
fila de la tabla a confeccionar, pero de preferencia siempre se
deberá de colocar como la primer fila.
Cuando minimizamos se toma el valor (+) positivo de fo para
convertirlo en negativo y cuando maximizamos tomamos el valor
(-) negativo de fo para convertirlo en positivo.
32
3. ESCRIBIMOS LA TABLA INICIAL DEL MÉTODO SIMPLEX
En las columnas aparecerán todas las variables del problema y
en las filas, los coeficientes de las igualdades obtenidas, una fila
para cada restricción y la última fila con los coeficientes de la
función objetivo:
33
Tabla Inicial
Base Variable de
decisión
Variable de holgura Solución
X1 X2 S1 S2 S3
S1 2 1 1 0 0 18
S2 2 3 0 1 0 42
S3 3 1 0 0 1 24
Z -3 -2 0 0 0 0
34
4. ENCONTRAR LA VARIABLE DE DECISIÓN QUE ENTRA EN
LA BASE Y LA VARIABLE DE HOLGURA QUE SALE DE LA
BASE
A. Para escoger la variable de decisión que entra en la base,
(FLECHA ROJA PARTE SUPERIOR), observamos la ultima fila, la cual
muestra los coeficientes de la función objetivo y escogemos la
variable con el coeficiente más negativo (en valor absoluto).
En este caso, la variable x1 de coeficiente - 3.
Si existiesen dos o más coeficientes iguales que cumplan
la condición anterior, entonces se elige cualquiera de ellos.
Si en la última fila no existiese ningún coeficiente negativo,
significa que se ha alcanzado la solución óptima.
35
Por tanto, lo que va a determinar el final del proceso de
aplicación del método del simplex, es que en la última fila no
haya elementos negativos.
La columna de la variable que entra en la base se llama
columna pivote (en color azulado).
B. Para encontrar la variable de holgura que tiene que salir de
la base, (FLECHA ROJA COSTADO IZQUIERDO) 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.
36
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 anterior dé lugar al
menor cociente positivo, el 3, ya 8 es el menor, indica la fila de la
variable de holgura que sale de la base, S3.
Esta fila se llama fila pivote (en color azulado).
37
Iteración No. 1
Base Variable de
decisión
Variable de holgura Solución Operación
X1 X2 S1 S2 S3
S1 2 1 1 0 0 18 18/2 = 9
S2 2 3 0 1 0 42 42/2 = 21
S3 3 1 0 0 1 24 24/3 = 8
Z -3 -2 0 0 0 0
38
Si al calcular los cocientes, dos o más son iguales, indica que
cualquiera de las variables correspondientes pueden salir de la base.
C. En la intersección de la fila pivote y columna pivote tenemos el
elemento pivote operacional, 3, este indica que la variable de decisión
x1 entra y la variable de holgura S3 sale.
39
5. ENCONTRAR LOS COEFICIENTES LA NUEVA TABLA
SIMPLEX.
Los nuevos coeficientes de la fila pivote se obtienen dividiendo
todos los coeficientes de la fila por el pivote operacional “3”, ya
que este se debe convertir en 1.
A continuación mediante la reducción gaussiana hacemos ceros
los restantes términos de la columna pivote, con lo que
obtenemos los nuevos coeficientes de las otras filas incluyendo
los de la función objetivo Z.
40
Resultado de Iteración No. 1
Base Variable de
decisión
Variable de holgura Solución Operación
X1 X2 S1 S2 S3
S1 0 1/3 1 0 -2/3 2 f(S1) – 2 f(X1)
S2 0 7/3 0 1 -2/3 26 f(S2) – 2 f(X1)
X1 1 1/3 0 0 -1/3 8 (1/3) X1
Z 0 -1 0 0 1 24 f(Z) + 3 f(X1)
41
Como en los elementos de la última fila hay un numero
negativo, -1, significa que no hemos llegado todavía a la solución
óptima. Hay que repetir el proceso:
A. La variable que entra en la base es x2, por ser la columna
pivote que corresponde al coeficiente -1
B. Para calcular la variable que sale o la fila pivote, dividimos los
términos de la columna solución entre los términos de la nueva
columna pivote y como el menor cociente positivo es 6, tenemos
que la fila pivote y la variable de holgura que sale es S1.
C. El elemento pivote, que ahora hay que hacer 1, es 1/3.
Y se opera de forma análoga a la anterior iteración
42
Iteración No. 2
Bas
e
Variable de
decisión
Variable de holgura Solució
n
Operación
X1 X2 S1 S2 S3
S1 0 1/3 1 0 -2/3 2 2/(1/3) = 6
S2 0 7/3 0 1 -2/3 26 26/(7/3) = 78/7
X1 1 1/3 0 0 -1/3 8 8/(1/3) = 24
Z 0 -1 0 0 1 24
43
Resultado de Iteración No. 2
Base Variable de
decisión
Variable de holgura Solución Operación
X1 X2 S1 S2 S3
X2 0 1 3 0 -2 6 3X2
S2 0 0 -7 0 4 12 f(S2) – (7/3) f(X2)
X1 1 0 -1 0 1 6 f(X1) – (1/3) f(X2)
Z 0 0 3 0 -1 30 f(Z) + f(X2)
44
Como en los elementos de la última fila hay uno negativo, -1,
significa que no hemos llegado todavía a la solución óptima. Hay
que repetir el proceso:
A. La variable que entra en la base es S3, por ser la variable que
corresponde al coeficiente -1
B. Para calcular la variable que sale, dividimos los términos de la
última columna entre los términos correspondientes de la nueva
columna pivote:
6/(-2) [=-3] , 12/4 [=3], y 6:1 [=6]
y como el menor cociente positivo es 3, tenemos que la variable
de holgura que sale es S2.
C. El elemento pivote, que ahora hay que hacer 1, es 4.
Obtenemos la tabla:
45
Iteración No. 3
Bas
e
Variable de
decisión
Variable de holgura Solució
n
Operación
X1 X2 S1 S2 S3
X2 0 1 3 0 -2 6 No se toma
por ser
negativo
S2 0 0 -7 0 4 12 12/4 = 3
X1 1 0 -1 0 1 6 6/1 = 6
Z 0 0 3 0 -1 30
46
Resultado de Iteración No. 3
Base Variable de
decisión
Variable de holgura Solución Operación
X1 X2 S1 S2 S3
X2 0 1 -1/2 0 0 12 f(X2) + 2 f(S3)
S3 0 0 -7/4 0 1 3 (1/4) S3
X1 1 0 -3/4 0 0 3 f(X1) – f(S3)
Z 0 0 5/4 0 0 33 f(Z) + f(S3)
47
Tabla Final
Base Variable de
decisión
Variable de holgura Solución
X1 X2 S1 S2 S3
X2 0 1 -1/2 0 0 12
S3 0 0 -7/4 0 1 3
X1 1 0 -3/4 0 0 3
Z 0 0 5/4 0 0 33
48
Como todos los coeficientes de la fila de la función objetivo son
positivos, hemos llegado a la solución óptima.
Los solución óptima viene dada por el valor de Z en la columna de
los valores solución, en nuestro caso: 33.
49
En algunas situaciones existen problemas de programación lineal
que no proporcionan una solución básica inicial.
En consecuencia este tipo de situación se presenta cuando al menos
una de las restricciones es del tipo (<=) o (=).
Para este propósito se desarrollan 2 métodos basados en el uso de
variables artificiales:
El método M o de penalización y la técnica de las dos fases.
50
METODO M O DE PENALIZACIÓN
1. Se debe expresar el problema en forma estándar transformando
las inecuaciones en ecuaciones introduciendo variables de holgura.
2. Agregue variables no negativas al lado izquierdo de cada una de
las ecuaciones correspondientes a las restricciones de tipo (>=) o (=).
Estas variables se denominan variables artificiales y su adición hace
que las restricciones correspondientes.
Esta dificultad se elimina asegurando que las variables sean 0 en la
solución final. Esto se logra asignando una penalización muy grande
por unidad a estas variables en la función objetivo.
Tal penalización se designará como – M para problemas de
maximización y + M para problemas de minimización.
51
3. Se utiliza las variables artificiales en la solución básica inicial; sin
embargo la función objetivo de la tabla inicial se prepara
adecuadamente para expresarse en términos de las variables no
básicas únicamente.
Esto significa que los coeficientes de las variables artificiales en la
función objetivo deben ser 0, esto puede lograrse sumando múltiplos
adecuados de las ecuaciones de restricción al renglón objetivo.
4. Proceda con los pasos regulares del método simplex.
52
FORMA AUMENTADA: = ≥
Toda restricción del tipo ≥ será aumentada con la substracción de
una variable de holgura y con la suma de una variable artificial.
5x1 + 3x2 ≥ 60
2x1 + 2x2 ≥ 30
Tienen como forma aumentada
5x1 + 3x2 - s3 + A1 = 60
2x1 + 2x2 - s4 + A2 = 30
53
Toda restricción del tipo = será aumentada con la suma de una
variable artificial.
7x1 + 9x2 = 126
Tiene como forma aumentada
7x1 + 9x2 + A3 = 126
Esta forma aumentada se explica en relación al algoritmo simplex.
Para la desigualdad ≥ si sólo se realiza la substracción de la
variable de holgura, y junto con la selección inicial de las variables
de decisión iguales a cero nos da un valor negativo para las
variables de holgura adicionadas; situación que no puede manejar el
algoritmo.
54
La variable Artificial solventa esta condición, pero tal como lo dice
es una variable ajena al problema y para poder dar una solución
al final todas ella deben ser iguales a cero.
MÉTODO DE PENALIZACIÓN LA GRAN “M”
El método de penalización o también llamado de la Gran “M”
realizará el siguiente tratamiento.
“M” significa: un coeficiente Muy grande o Mucho, Si todas las
variables artificiales tienen un valor de cero, la solución será
equivalente con la del problema original.
Si alguna de las variables artificiales tiene un valor distinto de
cero, el problema original es infactible.
55
Una vez aumentadas las variables artificiales a las restricciones
correspondientes, se aumentan las variables artificiales a la
función objetivo con un coeficiente de castigo o penalización MAi
para minimización y – MAi para maximización.
Nótese que es en el sentido opuesto de optimización, a
continuación se reduce a cero el coeficiente para las variables
básicas en el renglón de la función objetivo. (Columnas donde se
localiza la matriz identidad, en este método siempre habrá factores
de M).
Una vez establecidas las variables básicas en forma correcta, se
procede de manera habitual con el algoritmo Simplex
56
PROBLEMA DE MINIMIZACION:
min z = 60 x1 + 50 x2
sujeto a 5x1 + 3x2 ≥ 60
2x1 + 2x2 ≥ 30
7x1 + 9x2 = 126
donde x1 , x2 ≥ 0
Iniciamos con el método de la gran m es decir aumentando las
variables artificiales a la función objetivo:
min z = 60 x1 + 50 x2 + MA1 +MA2 +MA3
sujeta a 5x1 + 3x2 - x3 + A1 = 60
2x1 + 2x2 - x4 + A2 = 30
7x1 + 9x2 + A3 = 126
donde x1 , x2, x3, x4, A1, A2, A3, ≥ 0
57
Ahora para resolver como un problema de maximización:
max -z = - 60 x1 - 50 x2 - MA1 - MA2 - MA3
sujeto a 5x1 + 3x2 - x3 + A1 = 60
2x1 + 2x2 - x4 + A2 = 30
7x1 + 9x2 + A3 = 126
donde x1 , x2, x3, x4, A1, A2, A3, ≥ 0
Posteriormente establecemos la tabla simplex para el problema de
maximización:
58
Los coeficientes de las variables básicas en el renglón cero no son
correctos y se deben reducir a cero.
59
Los coeficientes de las variables básicas en el renglón cero no son
correctos y deben reducirse a cero.
Los coeficientes de las variables básicas en el renglón cero no son
correctos y deben reducirse a cero.
60
La tabla ya es correcta y con esta inicialización se resuelve por el
algoritmo Simplex.
Columna y renglón pivote
61
Pivote
Pivote
62
Actualización de tabla
El coeficiente más negativo y columna pivote
63
Pivote
Pivote
64
Actualización de la tabla
El coeficiente más negativo y columna pivote
65
Pivote
Pivote
66
Actualización de tabla y es óptima*
67
Como todo problema de minimización puede ser expresado como
uno de maximización, el algoritmo ya definido puede seguir siendo
utilizado sin modificar ningún criterio. Siempre que existan
restricciones de igualdad o del tipo mayor o igual que, se
aumentarán de forma adecuada las restricciones y puedan ser
manejadas por el algoritmo.
En el método de penalización o de la gran “M”, además de
aumentar el sistema; se aumentan las variables artificiales a la
función objetivo con un coeficiente de castigo en sentido opuesto al
de optimización. Se actualiza correctamente los coeficiente en el
renglón cero para la variables básicas. Una vez inicializado
correctamente se sigue el algoritmo Simplex de forma habitual
68
69
MÉTODO DE LAS 2 FASES
2. MÉTODO DE LAS 2 FASES
• El método de la M Grande incluye variables de apoyo con un
coeficiente muy grande (M) o muy pequeño (-M) en la función
objetivo.
• Esto da lugar a problemas numéricos que conducen a soluciones
erróneas. Esto es especialmente grave en problemas de cierto
tamaño.
• De ahí que los códigos comerciales utilizan una extensión del
algoritmo del Simplex conocida como el Método de las 2 Fases:
– 1ª Fase: Obtener una SBF inicial.
– 2ª Fase: Obtener una solución óptima.
70
• 1ª FASE
– La contribución de las variables básicas (cj) es =0 en la función
objetivo.
– Añadir variables de holgura en las restricciones, con contribución
a la función objetivo =0
– Añadir variables artificiales pero la contribución a la función
objetivo =1
Se minimiza la función objetivo anterior. Si la función objetivo (z) es 0
entonces se ha llegado a una solución factible del problema inicial.
– SBF Inicial hallada. Las variables artificiales se pueden eliminar
de la tabla y proceder con la fase 2ª. Ahora ya partimos de una
SBF.
– Solución infactible del problema original. Si al final de la 1ª fase
hay alguna variable artificial en la base.
DETERMINACIÓN DE UNA SBF INICIAL
71
• 2ª FASE
– Se eliminan de la tabla las variables artificiales.
– Se sustituyen los cj (contribuciones a la función objetivo) por
las del problema original.
– Se recalculan zj y cj-zj
Se comprueba si la solución es óptima analizando el valor de los
costes reducidos.
– Si es óptima hemos terminado.
– Si no lo es, se sigue iterando hasta alcanzar el óptimo.
72
APLICACIÓN DEL MÉTODO DE LAS 2 FASES
EJEMPLO 5.3.
MÉTODO DE LAS 2 FASES
• El PL es el siguiente:
Min (z) = 3x + 2,5y
sujeto a:
2x + 4y 40
3x + 2y 50
x, y 0
• El problema de apoyo, utilizando el método de las 2 Fases:
Min (z) = 0x + 0y + 0 s1 + 0 s2 + A1 + A2
sujeto a:
2x + 4y - s1 + A1 = 40
3x + 2y - s2 +A2 = 50
x, y, s1, s2, A1, A2 0
73
74
75
PLANTEAMIENTO FORMAL DEL SIMPLEX EN
FORMA DE TABLEAU
• Una manera más formal de ver la resolución de problemas de P.L.
mediante el Simplex es la siguiente :
• Sea un PL en forma estándar:
Max cx
sujeto a :
Ax =b
x ≥ 0
• Esta formulación equivale a:
Max cx
sujeto a :
z – cBxB – cNxN = 0 [1]
xB + B-1NxN = B-1b [2]
x ≥ 0
76
• Sustituyendo [2] en [1] y despejando se obtiene:
z= cB B-1b+(cN - cBB-1N)xN
• Por definición: z= cB B-1b, luego:
(cN - cBB-1N)xN = 0 [3]
• Formando una tabla en formato de “tableau”con [2] y [3] se obtiene:
donde:
cN - cBB-1N : Costes reducidos
B-1b: Valores de las variables básicas
B-1N: Matriz de los coeficientes
77
• La obtención de la inversa B-1 se realiza aplicando alguna de las
siguientes reglas de álgebra:
– Intercambiar dos filas
– Multiplicar una fila por un valor distinto de cero.
– Intercambiar dos filas
• De esta forma, el método simplex aplicado a problemas en forma de
tableau se reduce a aplicarle a la tabla estas operaciones de forma
que:
– El nuevo tableau representa una nueva solución básica factible.
– Salvo en el caso de soluciones degeneradas, el valor de la
función objetivo mejora en cada iteración.
78
• ¿Cómo reconocer todos los casos que pueden darse en la
resolución de un PL?
– Solución única: En el último tableau, los costes
reducidos de las variables no básicas son estrictamente
negativos (maximización) o estrictamente positivos
(minimización).
– Soluciones alternativas: En el último tableau, alguno de
los costes reducidos de las variables no básicas es igual
a cero.
– Solución no acotada: Si al efectuar el test de salida de
la base, todos los coeficientes de la columna
correspondiente a la variable entrante son no positivos.
– Problema infactible: Se reconoce porque alguna
variable artificial queda en la base en el tableau final.
79
• El método Simplex en forma de tableau es útil para los problemas
pequeños.
• Sin embargo, como proceso de cálculo resulta ineficiente y puede
tener problemas de inestabilidad numérica por las siguientes
razones:
– Los problemas reales suelen ser relativamente grandes y con
una densidad (número de posiciones ocupadas por un número
distinto de cero, dividido por el número total de posiciones)
baja. Si esta matriz se conserva en forma de tableau, se
ocupan m(m+n) posiciones de memoria. Si tan sólo se
conservan los valores distintos de cero junto con sus
coordenadas, la ocupación en memoria es muchísimo menor.
80
• Existe una forma implícita de almacenar la inversa, que ocupa un
espacio en memoria inferior a mxm
EJEMPLO:
– Un problema real de PL tiene densidades que oscilan
típicamente entre 0,5% y 2%.
– Supongamos un problema de PL de 200 restricciones, 500
variables y una densidad del 1%
– Si guardamos explícitamente todos los valores de la matriz A,
ocuparemos 200(200+500)= 140.000 posiciones de memoria.
– Si guardamos la misma matriz implícitamente (número de filas,
número de columna y valor del coeficiente no cero
correspondiente) entonces ocuparemos tan sólo
(200x500)x1% x 3= 3000 posiciones de memoria.
81
– La acumulación de errores de redondeo puede originar
problemas de cálculo importantes, hasta tal punto que la
solución obtenida puede resultar equivocada
• Por todos estos motivos, los códigos comerciales no utilizan la
versión del Simplex en forma de tableau.
• Lo más corriente es que utilicen una versión del método de las dos
fases y, dentro de cada una de ellas, alguna variante de un
algoritmo conocido como método simplex revisado.
82
83 . 4 , 3 , 2 , 1 , 0
1 4 2 5 1 10
9 3 2 10 1 10 . .
2 1 2
=
= - +
= + +
- -
i x i
x x x
x x x a s
x x Min
. .
2 1 2 +
. 2 , 1 , 0
1 2 5 1 10
9 2 10 1 10
=
+
+
i x i
x x
x x a s
x x Máx
Ejemplo:
Se debe agregar una variable de holgura y una variable de exceso
(x3 , x4 ), y llevarlo a su forma estándar.
84
Aplicamos Simplex de dos Fases :
Fase 1:
. 5 , 4 , 3 , 2 , 1 , 0
1 5 4 2 5 1 10
9 3 2 10 1 10 . .
5
=
= + - +
= + +
i xi
x x x x
x x x a s
x Min
Así queda la siguiente tabla:
x1 x2 x3 x4 x5
10 10 1 0 0 9
10 5 0 -1 1 1
0 0 0 0 1 0
85
=
=
=
=
0 0 0
4
2
1 ,
1 9
5
3
x x x
D
x x x
B
x
Luego se hace cero el costo reducido de la variable x5 de la tabla
anterior, y queda la siguiente tabla inicial.
x1 x2 x3 x4 x5
10 10 1 0 0 9
10 5 0 -1 1 1
-10 -5 0 1 0 -1
Luego la variable entrante a la base es x1 ( pues r1<0).
x1 x2 x3 x4 x5
10 10 1 0 0 9
10 5 0 -1 1 1
-10 -5 0 1 0 -1
86
Calculamos Min{ 9/10, 1/10}= 1/10, por lo tanto sale x5.
x1 x2 x3 x4 x5
0 5 1 1 -1 8
1 1/2 0 - 1/10 1/10 1/10
0 0 0 0 0 0
=
=
=
=
0
0
0
5
4
2
,
8
10 / 1
3
1
x
x
x
D x
x
x
B
x
Que corresponde a la solución óptima del problema en la Fase 1,
con valor óptimo 0. De aquí entonces tomamos x1 y x3 como
variables básicas para fase 2.
87
Fase 2:
x1 x2 x3 x4
0 5 1 1 8
1 1/2 0 - 1/10 1/10
-2 -1 0 0 0
En la tabla hacemos 0 los costos reducidos de var.básicas
x1 x2 x3 x4
0 5 1 1 8
1 1/2 0 - 1/10 1/10
0 0 0 - 1/5 1/5
Luego la variable entrante a la base es x4 ( pues r4<0).
88
calculamos Min{ 8/1, (-1/10)/(1/10)}= 8, por lo tanto sale x3.
x1 x2 x3 x4
0 5 1 1 8
1 1 0 1/10 9/10
0 1 1/5 0 1 4/5
=
=
=
=
0
0
3
2 ,
8
10 / 9
4
1
x
x
D x
x
x
B x
Que resulta ser la solución óptima del problema.
89
Algunos casos especiales
1.- Problema Infactible. Esta situación se detecta cuando el valor óptimo del problema de la fase 1 da mayor que cero.
2.- Múltiples soluciones óptimas. Esta situación se detecta cuando existen costos reducidos iguales a cero en una o más de las variables básicas óptima
3.- Problema no acotado. Esta situación se detecta cuando al realizar el cálculo de la variable que deja la base todos los elementos ykj de la columna j en la tabla son negativos, para j el índice de una variable no básica con costo reducido negativo.
90
91
92
93
94
95
96
97
98
99
100
101
FIN DE LA PRESENTACION
GRACIAS