Método Simplex
MGI Ing. Estuardo Godinez
Método Simplex
Es un algoritmo iterativo que converge a la solución óptima en un número
finito de iteraciones y que está diseñado para evitar ineficiencias tales
como resolver una combinación de "m" ecuaciones y "n" incógnitas donde
se origina un gran número de ecuaciones simultáneas a resolver y en
ocasiones con muchas de sus soluciones de tipo infactible o no existentes.
Dentro del procedimiento de solución, la función objetivo juega un papel
pasivo en el cálculo, utilizándose únicamente después de que todas las
soluciones básicas factibles han sido determinadas (puntos extremos).
Fue desarrollado alrededor de 1947 en los Estados Unidos por George
Dantzig. Para comprender el funcionamiento del método, es necesario
introducir y aclarar nuevos conceptos relacionados, los cuales son los
siguientes.
Método Simplex
a. Variables de Holgura.
Una variable de holgura es aquella que se introduce en las restricciones
identificadas en la formulación del modelo con el propósito de convertir
las desigualdades de la restricción, en igualdades o ecuaciones para el
correcto funcionamiento del método.
Suelen simbolizarse como "Sn" donde "n" corresponde al número de
variable de holgura.
Es importante saber que si la restricción que está transformando en una
igualdad es de tipo "≤", entonces es indispensable sumar una variable de
holgura "Sn" para compensar el valor que haga falta, en caso que el lado
izquierdo de la operación resulte "menor" que el lado derecho y, de esta
manera, asegurar que se convertirá en una igualdad.
Método Simplex
De manera similar, si la restricción es de tipo "≥", entonces es indispensable
restar una variable de holgura "Sn" para rebajar el valor excedente, en
caso que el lado izquierdo de la operación resulte "mayor" que el lado
derecho y, de esta manera, asegurar que se convertirá en una igualdad.
Método Simplex
b. Condición de Optimidad del Método Simplex
El método simplex asegura a través de cada iteración que realiza, que
nunca encontrará una solución inferior al punto de solución actual. Esta
propiedad es conocida como condición de optimidad.
Relacionada a esta condición se encuentra asociado el criterio de la
variable de entrada que consiste en elegir en maximización a la variable
que tiene el mayor coeficiente negativo de la ecuación "Xo" (función
objetivo). En minimización el criterio a elegir es el más positivo. Un empate
entre variables se rompe arbitrariamente. De acuerdo a esta condición, se
llega al óptimo cuando todos los coeficientes del lado izquierdo de la
ecuación "Xo" son no negativos en maximización o bien, no positivos en
minimización.
Método Simplex
c. Condición de Factibilidad del Método Simplex
El funcionamiento del método asegura que partiendo de una solución
básica factible, únicamente se encontrarán durante el cálculo, soluciones
básicas factibles. Esta propiedad es conocida como condición de
factibilidad.
Relacionada a esta condición se encuentra asociado el criterio de la
variable de salida que consiste en elegir la variable correspondiente al
cociente más pequeño positivo de los valores actuales de solución entre
los coeficientes positivos de las restricciones de la variable que entra. Un
empate se rompe arbitrariamente. El criterio para seleccionar la variable
de salida es el mismo independientemente si el objetivo es de tipo
maximización o minimización.
Método Simplex
Para ilustrar el funcionamiento del método, tomaremos como caso modelo
el ejemplo número uno de la sección de formulación de modelos. Es
importante que el estudiante compare los resultados de este método con
la solución gráfica. Recuerde que el método gráfico no es un método
práctico en situaciones complejas como suele ser la mayoría de casos de
la vida real. El hecho de que los resultados sean los mismos en ambos
métodos no significa que la solución gráfica sea mejor que el método
simplex. En todo caso, este último método es capaz de resolver cualquier
problema con cualquier cantidad de variables y restricciones.
Método Simplex
Ejemplo No. 1: (Decisiones de producción)
Véase el enunciado del ejemplo número uno de la sección de formulación
de modelos y método de solución gráfica.
Formulación:
Maximizar:
Xo = 20X1 + 50X2
Sujeta a: 0.5X1 + 2X2 ≤ 8
1X1 + 2X2 ≤ 12
X1, X2 ≥ 0
Método Simplex
Siga cuidadosamente los siguientes pasos:
1. Convierta la función objetivo en su forma estándar, igualándola a cero.
Xo - 20X1 - 50X2 = 0
2. Convierta las desigualdades de las restricciones, en igualdades,
introduciendo variables de holgura "Sn".
0.5X1 + 2X2 + S1 = 8
1X1 + 2X2 + S2 = 12
X1, X2, S1, S2 ≥ 0
Método Simplex
3. Prepare el tablero de inicio para el desarrollo del método, con los datos
obtenidos de los dos pasos anteriores.
Método Simplex
Note que para construir el tablero, se elabora una columna para cada
variable de decisión y cada variable de holgura, así como para la función
objetivo y una columna solución. Para elaborar las filas, se inicia siempre
con una fila para la función objetivo y tantas filas como variables de
holgura existan.
Para registrar los datos iniciales dentro del tablero, debe trasladar los
valores numéricos (considerando su signo) que anteceden a cada variable
de la función objetivo identificada en el paso uno, hacia la primera fila del
tablero. Posteriormente, debe trasladar los valores numéricos que
anteceden a cada variable de la primera restricción, hacia la segunda fila
y, finalmente, los valores correspondientes a la segunda restricción, hacia
la tercera fila del tablero.
Método Simplex
Aplique los criterios de variables de entrada y salida y realice tantas iteraciones
como sea necesario, hasta alcanzar la solución óptima.
En el tablero inicial debe seleccionar la variable de entrada identificándola
como la variable más negativa (en caso de aplicar criterio de maximización) de
la función objetivo (Xo). Para este ejemplo, es la variable X2 la variable que tiene
el valor más negativo, por lo que ésta se seleccionó como la variable de entrada
(V.E.).
Para identificar la variable de salida (V.S.), debe realizar la división entre los
valores de la columna solución entre los valores positivos de la columna donde se
encuentra la variable de entrada y donde encuentre el cociente menor positivo,
corresponderá a la variable ubicada en dicha fila, salir del ciclo de iteraciones.
Para este ejemplo, si usted divide los valores (8 / 2 = 4) de la fila S1 y (12 / 2 = 6)
de la fila S2, entonces se concluye que será la variable S1 la que saldrá del ciclo
de iteraciones.
Método Simplex
El elemento que se encuentra en la intersección de la columna donde
está la variable de entrada con la fila donde está la variable de salida, es
conocido como elemento pivote porque es alrededor de éste, que girarán
todos los demás cálculos de cada iteración.
Para realizar los cálculos para la primera iteración, debe construir una
tabla similar al tablero inicial, con los mismos encabezados de las columnas
que no variarán en ningún caso y con la diferencia que en las filas debe
sustituir el término de la variable de salida, por el término de la variable de
entrada y luego, para registrar los valores numéricos, debe seguir los
siguientes pasos:
Método Simplex
1. Como primer punto debe convertir el elemento pivote en valor uno (1),
para el efecto, divida cada elemento de la fila donde se encuentra la
variable de salida dentro del valor del elemento pivote y coloque los
resultados en el nuevo tablero.
2. Es indispensable convertir en elementos "cero" todo valor que se
encuentre arriba del elemento pivote y debajo de éste. Para lograrlo,
multiplique cada elemento de la fila donde está el elemento pivote ya
convertido en valor uno (1), por el número que desea volver "cero" con
signo cambiado y a este resultado, súmele cada valor de la fila donde se
encuentra el valor que desea convertir en "cero" del tablero anterior y
coloque los resultados en cada casilla del nuevo tablero.
Método Simplex
3. Identifique nueva variable de entrada, salida y elemento pivote y repita
tantas iteraciones como sea necesario hasta encontrar la optimización
buscada. El criterio de paro en la realización de ciclos o iteraciones se
identifica cuando ya no existen valores negativos en la función objetivo.
Método Simplex
El paso descrito en el numeral 1 anterior, se resume mediante la expresión
(Sale S1 ¸Entra X2) en el nuevo tablero de la iteración 1. Note que la punta
de flecha de la operación no señala ninguna celda en particular, sino más
bien indica, desde afuera, que dicha operación debe aplicarse para toda
casilla de la fila "X2".
El paso descrito en el numeral 2, lo identificamos de manera resumida
mediante la expresión (X2*50)+Xo, la cual debe aplicarse para toda casilla
de la fila Xo del nuevo tablero y mediante la expresión (X2*-2)+S2 que
debe aplicarse para toda casilla de la fila S2. Es importante que verifique
que la regla aplicable siempre es la misma, "multiplicar cada elemento de
la fila donde está el elemento pivote convertido en valor uno, por el valor
que se desea cambiar a cero con signo cambiado y sumar cada valor de
la fila donde está el elemento que se desea convertir en elemento cero".
Método Simplex
El paso descrito en el numeral 3, indica que debe seleccionarse ahora una
nueva variable de entrada. Al evaluar toda la fila de elementos de la
función objetivo, concluimos que el valor más negativo le corresponde a la
variable "X1". La nueva variable de salida la identificamos como S2 luego
de dividir los valores de la columna solución entre los valores positivos
donde está la nueva variable de entrada. Al operar (4 /0.25 = 16) y (4 / 0.5
= 8), encontramos la nueva variable de salida en el cociente menor
positivo.
Método Simplex
Ahora identificamos el nuevo elemento pivote y construimos un nuevo
tablero para registrar los valores de la segunda iteración.
Método Simplex
Note que en el nuevo tablero, la variable de entrada sustituyó la posición
de la variable de salida y el procedimiento de convertir el elemento pivote
en valor uno y los elementos arriba y debajo de éste en valores cero, se
aplica nuevamente mediante la regla que se resume en las operaciones
expresadas a un costado del tablero, para identificar la forma en que se
obtienen los valores finales.
Método Simplex
Luego de obtener este nuevo tablero, puede observarse que se ha llegado
al criterio de paro de ciclos o iteraciones debido a que ya no es posible
seleccionar una variable de entrada porque ya no existen valores
negativos en la función objetivo.
Por lo tanto, los resultados finales indican que la función objetivo se
maximiza con valor de 260, al producir 8 unidades del producto X1 y 2
unidades del producto X2.
Compare estos resultados con los obtenidos en el ejemplo uno del método
gráfico y concluya de acuerdo al enunciado original del problema.
Método Simplex
Enlaces de Videos de método simplex 15:34 minutos
Método SIMPLEX Facil y Divertido con Memes - Investigación Operativa –
YouTube
Otro video de explicación de método simplex con el debido cuidado que
cuando planteo el problema las restricciones las manejo verticalmente no
horizontalmente como lo hacemos pero es funcional. 18:25 minutos
Metodo simplex – YouTube
Tercer video explicando con tres variables muy bueno 34:58
MÉTODO SIMPLEX | EJERCICIO RESUELTO – YouTube
Método Simplex
Ejemplo de Minimización
La dietista de una prestigiosa clínica de reducción de peso, debe encontrar la
combinación más barata de dos productos alimenticios A y B que contienen al menos
0.5 miligramos de tiamina y al menos 600 calorías. Los estudios indican que cada onza
de A contiene 0.12 miligramos de tiamina y 100 calorías; mientras que cada onza de B
contiene 0.08 miligramos de tiamina y 150 calorías. Si el costo de cada alimento es de
Q.10.00 por onza, ¿cuántas onzas de cada alimento deberán combinarse de tal
manera que se cumplan los requerimientos dietéticos y el costo de alimentación sea
mínimo?.
Formulación:
Minimizar:
Xo = 10X1 + 10X2
Sujeta a: 0.12X1 + 0.08X2 ≥ 0.5 ==► 0.12x1 + 0.08x2 -S1 = 0.5
100X1 + 150X2 ≥ 600 ==► 100x1 + 150x2 -S2 = 600
X1, X2 ≥ 0
Método Simplex
Ejemplo de Minimización
Importante tomar en cuenta ciertas consideraciones:
La variable de entrada es la mas positiva de la función objetivo y la
variable de salida no sufre ningún cambio en su criterio (siempre valor
menor=
Las restricciones de tipo ≥ debe restarles las variables de holgura Sn ya que
al restarlas cumple con la igualación
Método Simplex
Ejemplo de Minimización
Dado que en la función objetivo las dos son -10 se puede partir con
cualquiera.
La fila de salida se escoge igual que en la maximización
Tomar nota que las variables de holgura se plantean negativas para quitar
la desigualdad
Método Simplex
Primera Iteración
Para quitar el 0.08 arriba del pivote original hay multiplicar todo x2 por -0.08 y sumárselo a
s1.
Para quitar el 10 negativo arriba del pivote hay que multiplicar todo x2 x 10 y se le suma a
Xo
En esta nueva tabla solo queda la otra variable que tiene valor aunque sea -3.33 esa entra
y sale la que tiene valor menor 2.7
Método Simplex
Primera Iteración
Para quitar el -3.3333 arriba del pivote original hay multiplicar todo x1 por 3.33333 y sumárselo a Xo.
Para quitar el 0.6666667 positivo abajo del pivote hay que multiplicar todo x1 x -0.66666666 y se le
suma a X2
En esta nueva tabla solo queda la otra variable que tiene valor -0.00000003 que se aproxima a 0 y
por talmotivo ya no hay variables de decisión positivas.
