Investigación sobre el Método Simplex

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

	Columna  entrada o trabajo

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

	Pivote viene a ser el Nº 4

 

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