PRESENTACIÓN
Este
Blog, tiene como propósito suministrar información de investigaciones
realizadas de otros autores presentada de manera resumida relacionado al tema del
Método Simplex.
INTRODUCCIÓN
Este blog tiene como finalidad proporcionar ayuda
al estudiante, para una mejor comprensión y manejo efectivo del método simplex
de programación lineal. Aquí se proporcionará definiciones del método simplex,
matriz de identidad, como hacer la formulación del método simplex,
procedimiento de cálculo y la aplicación a situaciones de maximización y
minimización.
Este popular
método fue creado en el año de 1947 por el estadounidense George Bernard
Dantzig y el ruso Leonid Vitalievich Kantorovich, con el ánimo de crear un
algoritmo capaz de solucionar problemas de m
restricciones y n
variables.
ÍNDICE
Definición del Método Simplex
Matriz de Identidad (Ejemplo de Cálculo)
Formulación del Método Simplex
Proceso de Cálculo
Ejemplo de Maximización
Ejemplo de Minimización
Conclusiones
Bibliografía
DEFINICIÓN
DEL MÉTODO SIMPLEX
El método Simplex es un procedimiento iterativo
que permite mejorar la solución de la función objetivo en cada paso. El proceso
concluye cuando no es posible continuar mejorando dicho valor, es decir, se ha
alcanzado la solución óptima.
También es definido como un método analítico de
solución de problemas de programación lineal capaz de resolver modelos más
complejos que los resueltos mediante el método gráfico sin restricción en el
número de variables.
MATRIZ
DE IDENTIDAD (EJEMPLO DE CÁLCULO)
Una matriz puede definirse como una
ordenación rectangular de elementos, (o listado finito de elementos), los
cuales pueden ser números reales o complejos, dispuestos en forma de filas y de
columnas.
La matriz idéntica o identidad es una matriz cuadrada (que posee el
mismo número tanto de columnas como de filas) de orden n que tiene todos
los elementos diagonales iguales a uno (1) y todos los demás componentes
iguales a cero (0), se denomina matriz idéntica o identidad de orden n, y
se denota por:
La importancia de la teoría de
matrices en el Método Simplex es fundamental, dado que el algoritmo se basa en
dicha teoría para la resolución de sus problemas.
FORMULACIÓN
DEL MÉTODO SIMPLEX
Usar
un modelo matemático para la resolución de problemas es la base de la
programación lineal recordando que modelo se refiere a la representación
simplificada de la realidad; los modelos matemáticos en específico hacen uso de
símbolos matemáticos y presentan elementos como:
· Variables: representan las incógnitas
del problema.
· Restricciones: se contemplan las
limitaciones a las que se encuentra sujeta la resolución del problema
considerando la escasez de recursos en tiempo y espacio.
· Función objetivo: representa la meta
que se pretende alcanzar y en la cual se basan las decisiones principales para
maximizar los beneficios o bien para minimizar los costos (considere que en la
programación lineal el calificativo “lineal” hace referencia que las ecuaciones
usadas en el modelo serán siempre de primer grado, es decir, sin exponentes).
Sin embargo, los resultados no siempre
deberán tomarse literalmente pues es deber del interprete considerar que hay
factores externos como el cambio climático, la competencia, las condiciones de
seguridad, entre otros; por lo tanto los resultados del modelo deberán ser
usados como una base para el tomador de decisiones con el objetivo de conseguir
los mejores resultados en diferentes situaciones. Por lo tanto, es importante
señalar cuestiones que debe considerar la persona encargada del modelado
·
Entre más sencillo sea el modelo, mejor será el resultado. Un modelo complejo
no siempre será la mejor solución.
· El
modelo debe ser validado antes de ser implementado para saber si representa la
situación real y en caso de no ser así habrá que hacer los ajustes
correspondientes.
· Si
se hacen las cosas de manera apresurada, el modelo saldrá mal. Debe hacerse un
minucioso análisis de la información recabada para identificar que en verdad
será útil para el modelo.
· Los
modelos son un herramienta más el tomador de decisiones tendrá siempre la
última palabra.
Ejemplo:
La empresa “Kekos” se dedica a la producción
de 3 tipos de lámparas: de escritorio, manuales y colgantes. Para su uso se
destinan 3 materias primas básicas denominadas A, B y C de las cuales su uso
por día para cada lámpara y la disponibilidad máxima diaria se encuentra en la
siguiente tabla:
|
Materia
Prima
|
Uso por producto (piezas)
|
Disponibilidad máxima de (pieza)
|
||
|
Lámpara de Escritorio
|
Lámparas Manuales
|
Lámparas Colgantes
|
||
|
A
|
100
|
80
|
---
|
200
|
|
B
|
90
|
50
|
100
|
250
|
|
C
|
30
|
100
|
40
|
180
|
La utilidad ($) que obtiene diariamente es:
Lámparas de escritorio $1000.00
Lámparas manuales $500.00
Lámparas colgantes $2500.00
Para formular el modelo el primer paso será
identificar las variables y asignarles nombres, en este caso:
𝑋1 = 𝐿á𝑚𝑝𝑎𝑟𝑎𝑠 𝑑𝑒 𝑒𝑠𝑐𝑟𝑖𝑡𝑜𝑟𝑖𝑜
𝑋2 = 𝐿á𝑚𝑝𝑎𝑟𝑎𝑠 𝑚𝑎𝑛𝑢𝑎𝑙𝑒𝑠
𝑋3 = 𝐿á𝑚𝑝𝑎𝑟𝑎𝑠 𝑐𝑜𝑙𝑔𝑎𝑛𝑡𝑒𝑠
Una vez que se tiene el primer paso se puede
plantear la función objetivo, en este caso lo que se pretende es maximizar la
ganancia (utilidad) por la venta de cada producto (como los datos de ganancia
son diarios, así como el uso de materia prima no es necesario hacer ninguna
conversión dejando los datos tal y como se presentan), por lo tanto, la
ecuación resultante es:
𝑀𝑎𝑥 𝑍 = 1000𝑋1 + 500𝑋2 + 2500𝑋3
Las restricciones del modelo hacen referencia
a la disponibilidad máxima que tenemos de cada una de las materias primas que
se emplean en el proceso, de esta forma se obtiene:
100𝑋1 +
80𝑋2 ≤ 200
Es decir, la materia prima A sólo se emplea
para la fabricación de lámparas de escritorio y manuales en ciertas cantidades
(100 y 80 respectivamente), su uso no puede ser mayor a las 200 piezas diarias
(≤). Este procedimiento se hace con cuantas limitaciones se tenga, entonces:
90𝑋1 +
50𝑋2 + 100𝑋3 ≤ 250 30𝑋1 + 100𝑋2 + 40𝑋3 ≤ 180
Existe una restricción más llamada “de no
negatividad” en la que nos indica que no se pueden producir cantidades
negativas del bien X ¡no fabricamos menos 10 tazas o menos 5 lápices! 𝑋1, 𝑋2, 𝑋3 ≥ 0 Juntando la
función objetivo y las restricciones el modelo queda conformado de la siguiente
manera (s.a. significará que la función objetivo estará sujeta a):
𝑀𝑎𝑥 𝑍 = 1000𝑋1 + 500𝑋2 + 2500𝑋3
s.a
100𝑋1 +
80𝑋2 ≤ 200
90𝑋1 +
50𝑋2 + 100𝑋3 ≤ 250
30𝑋1 +
100𝑋2 + 40𝑋3 ≤ 180
𝑋1, 𝑋2, 𝑋3 ≥ 0
PROCESO
DE CÁLCULO
Considerando el modelo lineal como se conoció
en el paso anterior (forma original), el método simplex requiere que éste se
convierta a la forma estándar, es decir, cada restricción se convertirá en una
igualdad además de incorporar variables holgura que permiten expresar la
cantidad de recurso no utilizado durante las actividades Se plantea el
siguiente modelo en su forma original:
𝑀𝑎𝑥 𝑍 = 100𝑋1 + 125𝑋2
6𝑋1 +
4𝑋2 ≤ 24
𝑋1 + 𝑋2 ≥ 800
𝑋1, 𝑋2 ≥ 0
Paso
1. Cambiar el modelo a forma estándar
Las desigualdades del tipo ≤ implican la
cantidad no usada u holgura del recurso. Para convertirla en una igualdad y
hacer uso de ella en el método simplex, se adiciona una variable holgura al
lado izquierdo de la ecuación (𝑆𝑛),
de tal forma que:
6𝑋1 +
4𝑋2 ≤ 24
Se convertirá en:
6𝑋1 +
4𝑋2 + 𝑆1 = 24
Por su parte una restricción del tipo ≥
representará un límite inferior para las actividades a las que se encuentra
sujeta la función objetivo; por lo tanto, la cantidad por la que el lado
izquierdo de la ecuación es mayor al lado derecho o límite se considera un excedente
y para convertirla en una igualdad será necesario restar la variable de
excedencia
𝑋1 + 𝑋2 ≥ 800
Se convertirá en
𝑋1 + 𝑋2 − 𝑆2 = 800
Deberán ponerse tantas variables holgura como
restricciones existan.
Por su parte, la función objetivo deberá
cambiar de signo (de positivo a negativo y viceversa), de tal modo que:
𝑀𝑎𝑥 𝑍 = 100𝑋1 + 125𝑋2
Será:
𝑀𝑎𝑥 𝑍 = −100𝑋1 − 125𝑋2
De tal forma que el modelo estándar completo
se escribirá así:
𝑀𝑎𝑥 𝑍 = −100𝑋1 − 125𝑋2
6𝑋1 +
4𝑋2 + 𝑆1 = 24
𝑋1 + 𝑋2 − 𝑆2 = 800
𝑋1, 𝑋2, 𝑆1 𝑆2 ≥ 0
Observe que las variables holgura también se
consideraran positivas, mayor a cero.
Paso
2. Armar la tabla simplex
Los valores del modelo serán introducidos a
la tabla simplex
|
Var. Holgura
|
X1
|
X2
|
S1
|
S2
|
Solución
|
|
S1
|
6
|
4
|
1
|
0
|
24
|
|
S2
|
1
|
1
|
0
|
-1
|
800
|
|
Z
|
-100
|
-125
|
0
|
0
|
0
|
Observe que en la primer columna se han
colocado las variables holgura (𝑆𝑛) y
en las filas, de acuerdo a dicha variable, se coloca la restricción que
corresponde y en la última fila (ó llamado también renglón objetivo) los
valores de la función objetivo. Cuando las variables holgura no aparecen el valor
que tomará será cero.
Paso
3. Elegir el valor de Z más negativo
En la fila donde aparecen los datos de Z (la
función objetivo) habrá que localizar el valor más negativo excluyendo la
última columna. La columna en dónde se encuentre dicho valor se denominará
columna de entrada o columna de trabajo.
|
Var. Holgura
|
X1
|
X2
|
S1
|
S2
|
Solución
|
|
S1
|
6
|
4
|
1
|
0
|
24
|
|
S2
|
1
|
1
|
0
|
-1
|
800
|
|
Z
|
-100
|
-125
|
0
|
0
|
0
|
|
Paso
4. Determine la variable de salida y el pivote
Dividiendo cada número de la columna solución
entre los valores de la columna entrada (a excepción del renglón objetivo).
Entonces:
𝟐𝟒/𝟒 = 𝟔
800/1 = 800
Del resultado, se elige el valor positivo más
pequeño sin tomar en cuenta los valores negativos y a la intersección se le
denominará pivote.
|
Var. Holgura
|
X1
|
X2
|
S1
|
S2
|
Solución
|
|
S1
|
6
|
4
|
1
|
0
|
24
|
|
S2
|
1
|
1
|
0
|
-1
|
800
|
|
Z
|
-100
|
-125
|
0
|
0
|
0
|
|
Es muy importante que el pivote tome el valor
1; si no se tiene ese valor habrá que dividir el renglón objetivo entre el
valor del pivote.
6/4
= 1.5
1/4=
0.25
24/4
= 6
4/4
= 1
0/4 = 0
|
Var. Holgura
|
X1
|
X2
|
S1
|
S2
|
Solución
|
|
X2
|
1.5
|
1
|
0.25
|
0
|
6
|
|
S2
|
1
|
1
|
0
|
-1
|
800
|
|
Z
|
-100
|
-125
|
0
|
0
|
0
|
Los nuevos valores se colocarán en la tabla
simplex, en el renglón que corresponde; en este caso 𝑠1 retomará el valor
de la variable en donde se encontró la columna entrada 𝑋2
Paso
5. Hacer ceros los demás valores de la columna entrada.
Para el ejemplo los demás valores que deben
hacerse cero son 1 y – 125
|
X2
|
|
1
|
|
1
|
|
-125
|
Para eso habrá que multiplicar el renglón 𝑋2 por el inverso del
valor que se hará cero y a este resultado se le sumará al renglón que desea
convertirse (donde está el inverso), de manera más precisa:
|
Renglón X2
|
Inverso del valor que se hará cero
|
Resultado
|
Renglón que desea convertirse
|
Nuevo valor
|
|
1.5
|
-1
|
-1.5
|
1
|
-0.5
|
|
1
|
-1
|
-1
|
1
|
0
|
|
0.25
|
-1
|
-0.25
|
0
|
-0.25
|
|
0
|
-1
|
0
|
-1
|
-1
|
|
6
|
-1
|
6
|
800
|
794
|
|
Renglón X2
|
Inverso del valor que se hará cero
|
Resultado
|
Renglón que desea convertirse
|
Nuevo valor
|
|
1.5
|
125
|
187.5
|
-100
|
87.5
|
|
1
|
125
|
125
|
-125
|
0
|
|
0.25
|
125
|
31.25
|
0
|
31.25
|
|
0
|
125
|
0
|
0
|
0
|
|
6
|
125
|
750
|
0
|
750
|
El nuevo valor encontrado se asignará en el
renglón que corresponde:
|
Var. Holgura
|
X1
|
X2
|
S1
|
S2
|
Solución
|
|
X2
|
1.5
|
1
|
0.25
|
0
|
6
|
|
S2
|
-0.5
|
0
|
-0.25
|
-1
|
794
|
|
Z
|
87.5
|
0
|
31.25
|
0
|
750
|
Como usted puede apreciar, los valores junto
al pivote en la columna entrada se han convertido en ceros, señal de que hasta
este momento se han hecho los cálculos correctos.
|
X2
|
|
1
|
|
0
|
|
0
|
De la misma manera puede apreciar que en el
renglón de Z ya no ha quedado ningún valor negativo, por lo tanto ya ha
terminado el procedimiento
|
Z
|
87.5
|
0
|
31.25
|
0
|
750
|
**Nota: si
hubiese un valor negativo en Z, habría que repetir el procedimiento a partir
del paso 3.
Otra comprobación de que hemos llegado al
final del procedimiento es usar precisamente los datos encontrados en la tabla
simplex (específicamente los de la columna solución) y sustituirlos en la
función objetivo del modelo. Si recuerda en el procedimiento cambio el nombre
de la variable holgura 𝑆1
por 𝑋2 y en la tabla
simplex su solución ha sido de 6, mientras que Z ha tomado el valor de 750.
**Nota: En
este caso en la columna denominada Var. Holgura no se ha hecho sustitución en
ningún momento por 𝑋1,
por lo que ésta tomará el valor de cero.
|
Var. Holgura
|
X1
|
X2
|
S1
|
S2
|
Solución
|
|
X2
|
1.5
|
1
|
0.25
|
0
|
6
|
|
S2
|
-0.5
|
0
|
-0.25
|
-1
|
794
|
|
Z
|
87.5
|
0
|
31.25
|
0
|
750
|
De tal forma que haciendo la sustitución en Z
tenemos que:
𝑍 =
100(0) + 125(6) = 750
Por lo que se comprueba que la solución ha
sido la adecuada.
EJEMPLO
DE MAXIMIZACIÓN
Formulación
Inicial
Utilizando el siguiente ejemplo
estableceremos la formulación inicial símplex y demostrar la mecánica del
método y su interpretación.
El gerente de la Relojería la Torre desea
conocer la ganancia máxima que se puede obtener de la producción y venta de dos
clases de relojes económicos digitales de pulsera. La ganancia que se obtiene
por la producción y venta de un reloj de hombre es de $4 y de $6 para un reloj
de mujer. La empresa cuenta con 120 horas semanales para la producción de los
relojes y 100 horas para la inspección y empaque de estos. La fabricación de un
reloj de hombre requiere 2 horas de producción y 2 horas de inspección y
empaque. Mientras que un reloj de mujer requiere 4 horas de producción y 3
horas de inspección y empaque.
La formulación del problema para esta
situación es la siguiente:
Maximizar Z = $4X1 + $6X2
Sujeto a: 2X1 + 4X2 ≤ 120 (horas de
producción)
2X1 + 3X2 ≤ 100 (horas de inspección y
empaque)
(X1,
X2 ≥ 0)
Donde:
X1 =
cantidad de relojes de hombre que se producen semanalmente.
X2 = cantidad de relojes de mujer que se
producen semanalmente.
Luego de formular el problema se procede a
trabajar primero con las restricciones y luego con la función objetivo. Se comienza
cambiando los signos de las restricciones de desigualdades a igualdades. El
método símplex requiere la conversión de las restricciones con signos de
desiguales a igualdades estrictas. Esto se debe a que el método usa álgebra de
matrices en donde todas las relaciones matemáticas serán a base de ecuaciones
lineales y que a su vez deben contener todas las variables. Este procedimiento se
llama como aumento de las restricciones y de la función objetivo.
Aumento
de las Restricciones y de la Función Objetivo
El aumento de las restricciones y de la
función objetivo surge porque el método símplex comienza por definición en el
origen es decir en el punto (0,0) y de este punto al valor de las restricciones
existe una diferencia. Esta diferencia se conoce como holgura y por cada
restricción que tenga el problema tendremos una o más variables las cuales el
método tomará en consideración.
Se
comienza con la primera restricción: 2X1 + 4X2 ≤ 120 (horas de producción) Al
analizar la restricción hallamos que el lado izquierdo es menor que el lado
derecho. Para poder hacer el cambio de la desigualdad a igualdad tendremos que
añadir una variable que absorba la diferencia entre ambos lados. En este caso
la variable representa recursos no utilizados o recursos disponibles. Esta
variable se conoce como variable de holgura o "Slack".
La primera restricción se reformula
asignándole una variable de holgura positiva conocida como S1, la que aparecerá
de la siguiente forma: 2X1 + 4X2 + S1 = 120. La variable S1 se relaciona con la
primera restricción. De manera parecida se procede a reformular la segunda
restricción: 2X1 + 3X2 ≤ 100 (horas de inspección y empaque). Encontramos que
esta restricción también posee un signo de desigualdad que es menor o igual por
lo tanto el lado izquierdo es menor que el derecho. Para poder llevar la
ecuación a igualdad tendremos que también añadir una variable de holgura
positiva que absorba la desigualdad. De tal manera la segunda restricción se
reformula de la siguiente forma:
2X1 + 3X2 + S2 = 100 en donde S2 se relaciona
con la segunda restricción. Tenemos que ambas restricciones se presentan de la
siguiente forma:
2X1 +
4X2 + S1 = 120
2X1 + 3X2 + S2 = 100
La variable de holgura S1 representa las
horas de producción no utilizadas y la variable S2 representa las horas de
inspección y empaque no utilizadas.
Si por definición el método símplex comienza
en el origen (0,0) donde X1 = 0 y X2 = 0, entonces esto significa que por ahora
no hay producción de relojes de ninguna clase (X1 = relojes de hombre y X2 =
relojes de mujer). El no tener producción significa que los recursos
disponibles son 120 horas de producción y 100 horas de inspección y empaque.
Esta situación la representamos de la siguiente forma para la primera
restricción: 2X1 +4X2 + S1 = 120 donde X1 = 0 y X2 = 0. Al sustituir los
valores de X1 y X2 en la primera restricción tendremos el siguiente resultado:
2(0) + 4(0) + S1 = 120 por lo tanto S1 = 120 horas disponibles es decir tenemos
120 horas de producción disponibles porque no hay producción alguna.
Lo mismo sucederá con la segunda restricción:
2X1 + 3X2 + S2 = 100, al sustituir, X1 y X2 en la segunda restricción, se
obtendrá el siguiente resultado: 2(0) + 3(0) + S2 = 100 por lo tanto S2 = 100.
Esto representa 100 horas disponibles para inspección y empaque. ¿Por qué? Por
que no hay producción. Por lo tanto cuando X1 = 0 y X2 = 0, S1 = 120 horas y S2
= 100 horas.
2X1 + 4X2 + 1S1 + 0S2 = 120
2X1 + 3X2 + 0S1 + 1S2 = 100
Esto no afecta a las ecuaciones a las cuales
se les agregan los coeficientes. Por ejemplo en la primera restricción S2 posee
un coeficiente de 0 porque la variable S2 se refiere a la segunda restricción
en donde en el punto (0,0) existe un sobrante de 100 horas. Estas horas se
relacionan con la segunda restricción y no con la primera. De igual manera
sucede con la segunda restricción. La variable S1 se relaciona con la primera
restricción indicando que hay disponible 120 horas.
Estas variables de holgura no producen
ganancia alguna porque se relacionan con los recursos por lo tanto serán
añadidas a la función objetivo y sus coeficientes serán 0 porque estas no
aportan a la ganancia. Al reformular la función objetivo junto con las
restricciones tendremos que estas se expresan de la siguiente forma:
Maximizar Z
(ganancia) = $4X1 + $6X2 + $0S1 + $0S2
Sujeto a: 2X1 + 4X2 + 1S1 + 0S2 = 120
2X1
+ 3X2 + 0S1 + 1S2 = 100
(X1, X2, S1, S2 ≥ 0)
COMO
OBTENER UNA SOLUCIÓN INICIAL
Las
dos restricciones consideradas en la formulación del problema establecen dos
ecuaciones y cuatro variables (X1, X2, S1, S2). El uso del álgebra para
aquellos casos donde tenemos cuatro variables desconocidas y solo dos
ecuaciones, conlleva igualar dos de las variables a 0 y luego resolvemos para
las otras dos variables restantes. Es decir si X1 = X2 = 0 entonces S1 = 120 y
S2 = 100. Esto se conoce como una posible solución o solución básica factible.
El método símplex comienza con una solución inicial básica en donde todas las
variables reales Xj son cero. Esta solución siempre produce una ganancia de 0 y
valores de las variables de holgura iguales al valor de las constantes que
aparecen al lado derecho. Si se fija en la gráfica anterior la solución inicial
símplex será el punto de origen (0,0). Esta es una solución posible pero no es
la mejor solución. Como se indicó anteriormente el método símplex solo
considera soluciones que son factibles, es decir no toma en consideración
aquellas combinaciones de variables reales que violentan las restricciones ya
que el método siempre cumple con estas. El violentar una o más restricciones
conlleva la no existencia de una solución y algunos mencionan esta situación
como solución o soluciones no factibles.
EJEMPLO
DE MINIMIZACIÓN
Para resolver problemas de
minimización mediante el algoritmo simplex existen dos procedimientos que se
emplean con regularidad.
- El primero, que es el más recomendable se basa
en un artificio aplicable al algoritmo fundamentado en la lógica
matemática que dicta que "para cualquier función f(x), todo punto
que minimice a f(x) maximizará también a - f(x)". Por lo tanto el
procedimiento a aplicar es multiplicar por el factor negativo (-1) a toda
la función objetivo.
ZMIN = X1 - 3X2
Se reescribe
(-Z)MAX = X1 + 3X2
A continuación se
resuelve el algoritmo como un problema de maximización.
- El
segundo procedimiento, el cual pretende conservar la minimización consiste
en aplicar los criterios de decisión que hemos esbozado con anterioridad,
en los casos de la variable que entra, que sale y el caso en el que la
solución óptima es encontrada. Aquí recordamos los procedimientos según el
criterio dado el caso "minimizar".
|
Minimizar
|
|
|
Variable
que entra
|
La más
negativa de los (Cj - Zj)
|
|
Variable
que sale
|
Siendo "b"
los valores bajo la celda solución y "a" el valor
correspondiente a la intersección entre "b" y la variable
que entra. La más positiva de los "b/a".
|
|
Solución
Óptima
|
Cuando
todos los (Cj - Zj) sean >= 0.
|
La solución para un problema de minimización
se simplifica después de haber practicado un problema de maximización. La
diferencia en el procedimiento es mínima. Se tiene el siguiente ejemplo.
La empresa Que Lindo Perrito se dedica a la
producción y venta de comida seca para perros. La compañía produce y empaca dos
clases de comidas en bolsos de 20 libras, estos son a saber; comida seca para
perros en crecimiento y comida seca para perros adultos. El costo semanal de
fabricar un saco de comida para crecimiento es de $5 y para adultos de $7. A la
comida para crecimiento se le puede añadir un máximo de 200 unidades de
vitaminas mientras que la comida para perros adultos deberá tener un mínimo de
100 unidades. El total de unidades de vitaminas para la mezcla deberá ser
exactamente 800 unidades.
La formulación para este problema de
programación lineal es la siguiente.
Minimizar Z =$5X1 + $7X2
Sujeto a: 1X1 + ≤ 200 (unidades de vitaminas para
perros en crecimiento)
+ 1X2 ≥ 100
(unidades de vitaminas para perros adultos)
X1 + X2 = 800 (total de unidades de vitaminas)
(X1, X2 ≥ 0)
Donde:
X1 =
unidades de vitaminas para las bolsas de comida para crecimiento
X2 =
unidades de vitaminas para bolsas de comida perros adultos
Aumento
de las restricciones y de la función objetivo
Al igual que en el caso de maximización,
antes señalado, se comienza aumentando las restricciones y luego la función
objetivo.
La primera restricción, 1X1 + ≤ 200 (unidades
de vitaminas para perros en crecimiento) posee un signo de desigualdad por lo
tanto se le asigna una variable de holgura positiva.
1X1 + S1 = 200
La segunda restricción, 2X1 + 3X2 ≥ 100
(unidades de vitaminas para perros adultos) tiene un signo mayor e igual, es
decir el lado izquierdo es mayor que el lado derecho. Para poder igualar la
restricción habrá que restar una variable de holgura. Esta variable se conoce
como una variable de holgura negativa o de excedente o superflua.
0X1 + 1X2 -S2 = 100
Como el método simplex comienza en el origen,
esto significa desafortunadamente que en el punto de solución inicial (0,0) el
valor de la variable S2 será de -100.
Esto se debe a que se sustituyó el punto
(0,0) en la ecuación obteniendo el resultado antes mencionado.
1(0) -S2 = 100, S2 = -100
No es permitido un valor negativo para la
variable de holgura. Este valor negativo representa la falta de recurso. No se
puede asignar una cantidad negativa de vitaminas para las bolsas de comida de
perro. Para remediar esta situación se le asignará una variable artificial a la
restricción al lado izquierdo en adición a la variable de holgura negativa. La
variable artificial absorberá la negatividad de la variable de holgura.
1X2 -S2 + A2 = 100
La variable artificial posee un subíndice de
2 porque pertenece a la segunda restricción. Su interpretación, es de una
variable de holgura negativa que demuestra por cuántas unidades la solución
final violenta la segunda restricción. Cuando se encuentra una solución que no
violente la restricción, A2 será cero (0) y se quedará con ese valor. Su único
propósito es el proveer una solución inicial con valores no negativos. La tercera
restricción, X1 + X2 = 800 (total de unidades de vitaminas), se le añadirá una
variable artificial para no violentar la restricción. A menos que la
restricción pase por el origen, de lo contrario existirá una diferencia entre
el origen y la igualad de la restricción. La variable artificial absorberá esta
diferencia.
X1 + X2 + A2 = 800
Siempre que se incorpore una variable de
holgura o artificial a una restricción, habrá que agregarlas en las demás
restricciones y en la función objetivo. En una solución óptima, las variables
artificiales no pueden ser variables básicas. La razón para que estas se
excluyan en la solución óptima es que estas absorben la negatividad de la
variable de holgura. También representan por cuantas unidades no se ha cumplido
con la restricción. Para eliminar estas variables artificiales se le asigna un
costo extremadamente alto para los casos de minimización y una reducción grande
en las ganancias para los casos de maximización. En problemas de minimización
las variables con costos bajos son deseables y son las primeras en entrar a la
solución y las variables con costos altos serán rápidamente eliminadas. Para
lograr esto utilizaremos el método de la M grande. El método de la M grande
permite la eliminación de estas variables hasta donde sea posible. El método
utiliza la letra $M en vez de dólares para representar un número muy grande. Le
asigna un coeficiente de +$M, costo muy alto en casos de minimización y -$M,
reducción de ganancias para maximización. Las variables de holgura negativa
tienen un costo de cero.
Acomodamos
las restricciones y la función objetivo con sus nuevas variables de holgura y
artificiales.
Minimizar
Z (costo) = $5X1 + $7X2 + $0S1 + $0S2 + MA2 + MA3
Sujeto a: 1X1 +
0X2 + 1S1 + 0S2 + 0A2 + 0A3 = 200
0X1 + 1X2 + 0S1 - 1S2 + 1A2 + 0A3 = 100
1X1 + 1X2 + 0S1 + 0S2 + 0A2 + 1A3 = 800
(X1,
X2, S1, S2, A2, A3 ≥ 0)
Como
obtener una solución inicial
El tablón símplex inicial se construye de
manera parecida al anterior ejemplo de maximización. Las variables básicas en
la solución inicial son aquellas que poseen signos positivos en este caso son
las de holgura positivas (S1) y las artificiales (A2 y A3).
Ahora hay que ver cuales de las variables son
básicas a ser asignadas al tablón inicial.
·
La primera restricción, 1X1 ≤ 200; S1, se
asigna la variable S1 » Variable básica
·
La segunda restricción, 1X2 ≥ 100; -S2 + A2,
se asigna la variable A2 » Variable básica
·
La tercera restricción, X1 + X2 = 800; A3, se
asigna la variable A3 »Variable básica
Luego de trasladar las ecuaciones a la tabla
inicial procedemos a buscar los valores de Zj y los ∆Zj correspondientes y los
llevamos al tablón inicial.
Z1 = (0)(1) + (M)(0) + (M)(1) = M
Z2 = (0)(0) + (M)(1) + (M)(1) = 2M
Z3 = (0)(1) + (M)(0) + (M)(0) = 0
Z4 =
(0)(0) + (M)(-1) + (M)(0)= -M
Z5 = (0)(0) + (M)(1) + (M)(0)= M
Z6 = (0)(0) + (M)(0) + (M)(1)= M
Z = (0)(200) + (M)(100) + (M)(800) = 900M
∆Z1 = C1 - Z1 = 5 – M = 5-M
∆Z2 = C2 - Z2 = 7 – 2M = 7-2M
∆Z3 = C3 - Z3 = 0 – 0 = 0
∆Z4 = C4 - Z4 = 0 – M = M
∆Z5 = C5 - Z5 = M – M = 0
∆Z6 = C6 - Z6 = M – M = 0
Para
la tabla inicial buscamos las variables básicas, no básicas e interpretamos la solución.
Las variables básicas como se ha mencionado son aquellas que poseen ∆Zj = 0,
mientras que las variables no básicas tienen ∆Zj ≠ 0. Las variables: S1, A2 y
A3 son básicas, mientras que las variables: X1, X2 y S2 son variables no
básicas porque tienen cambios negativos y sus valores son cero. El valor de la
variable básica S1 es de 200 y significa, la existencia de 200 unidades
disponibles de vitaminas para perros en crecimiento. Las variables artificiales
significan que no se ha cumplido con la restricción. El valor de 100 para la
variable A2 indica el incumplimiento por la cantidad de 100 unidades de la
segunda restricción, 1X2 ≥ 100 (unidades de vitaminas para perros adultos).
Esta restricción exige que se agreguen por lo menos 100 unidades y su incumplimiento
se debe a que la solución inicial está en el punto (0,0). De igual manera
sucede con la variable A3. Está variable se refiere a la tercera restricción e
indica el incumplimiento de la restricción por 800 unidades. Al sustituir los
valores de X1 y X2 faltarán las 800 unidades para su cumplimiento.
Para la tercera restricción sustituimos los
valores de X1 = 0 y X2 = 0, entonces 0 + 0 + A3= 800 por lo tanto A3 = 800.
Cuando se cumpla con la tercera restricción
entonces la variable artificial dejará de ser básica y tendrá un valor de cero.
Siempre se violentarán las restricciones mientras una variable artificial se
mantenga como básica.
En conclusión no se asignan vitaminas para
alimentos de perros en crecimiento, (X1 = 0) ni vitaminas para perros adultos,
(X2 = 0), y se podrá agregar 200 unidades de vitaminas para perros en
crecimiento. Se incumple con la segunda restricción por 100 unidades y con la
tercera restricción por 100 unidades y el costo es alto.
CONCLUSIONES
El método constituye una forma sistemática y
de búsqueda intensiva a través de todas las posibles soluciones para obtener
una solución óptima. Ello resulta de gran utilidad debido a su eficiencia.
Además es fácil programarlo en una computadora. En contraste con el análisis
gráfico, este método permite el uso de muchas variables. También permite la
aplicación de cantidades de restricciones lineales con signos; mayores e igual,
menores e igual y de igualdad.
El método simplex tiene como punto de partida
el origen siendo este la solución inicial al problema. El método prueba todos
los puntos extremos gráficos aunque no necesariamente se detiene en todos los
vértices. Por otro lado utiliza el concepto de álgebra de matrices en una serie
de tablones.
BIBLIOGRAFÍA
IngenieriaIndustrialonline.com.
(s/f). Método Simplex. [Consulta en
línea] Disponible: https://www.ingenieriaindustrialonline.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/m%C3%A9todo-simplex/
Collazo Pedraja, A. R. (s/f). Apuntes sobre el método simplex de
programación lineal. [Consulta en
línea] Disponible: http://cicia.uprrp.edu/publicaciones/ docentes/metodosimplexdePL.pdf
Valencia Sandoval, K. (2015).
Introducción al Método Simplex: Forma tabular paso a paso. Universidad
Autónoma del Estado de México. Centro Universitario Valle de Chalco. [Consulta en línea] Disponible: http://ri.uaemex.mx/bitstream/handle/20.500.11799/33856/secme-16318.pdf?sequence=1
No hay comentarios.:
Publicar un comentario