El método simplex , fue creado en el año de 1947 por el matemático George Dantzing, con el fin de resolver problemas de programación lineal, en los cuales intervienen tres o mas variables.

este procedimiento permite mejorar las respuestas paso a paso, con el fin de alcanzar la solución optima de un problema.

La primera aplicación importante de este método ocurrió poco después del verano de 1947, cuando J. Laderman resolvió, en la National Bureau of Standards, un programa lineal de plantación de una dieta con nueve restricciones y 27 variables. Usando calculadoras de escritorio, para resolver este problema se requirieron 120 días-hombre, y cuando con dificultad las hojas de datos fueron unidas entre sí, semejaban un "mantel". Actualmente, usando la computadora y un programa del método Simplex (TORA, MICROMANAGER, LINDO, PROLIN, QSB, otro) es fácil resolver problemas de PL con muchas variables y muchas restricciones.

HISTORIA DEL MÉTODO SIMPLEX

El problema de la resolución de un sistema lineal de inecuaciones se remonta, al menos, a Fourier, después de quien nace el método de eliminación de Fourier-Motzkin. La programación lineal se plantea como un modelo matemático desarrollado durante la Segunda Guerra Mundial para planificar los gastos y los retornos, a fin de reducir los costos al ejército y aumentar las pérdidas del enemigo. Se mantuvo en secreto hasta 1947. En la posguerra, muchas industrias lo usaron en su planificación diaria. Los fundadores de la técnica son George Dantzig, quien publicó el algoritmo simplex, en 1947, John von Neumann, que desarrolló la teoría de la dualidad en el mismo año, y Leonid Kantoróvich, un matemático ruso, que utiliza técnicas similares en la economía antes de Dantzig y ganó el premio Nobel en economía en1975. En 1979, otro matemático ruso, Leonid Khachiyan, demostró que el problema de la programación lineal era resoluble en tiempo polinomial. Más tarde, en 1984, Narendra Karmarkar introduce un nuevo método del punto interior para resolver problemas de programación lineal, lo que constituiría un enorme avance en los principios teóricos y prácticos en el área.

Es un proceso repetitivo que permite mejorar la solucion de la funcion objetivo, el metodo concluye cuando estan satisfechas todas las restricciones,es decir, cuando se ha llegado a la solucion optima. 

El Método Simplex es 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,La razón matemática de esta mejora radica en que el método consiste en caminar del vértice de un poliedro a un vértice vecino de manera que aumente o disminuya (según el contexto de la función objetivo, sea maximizar o minimizar), dado que el número de vértices que presenta un poliedro solución es finito siempre se hallará solución.

Importancia del método simple

Este metodo es de gran importancia, porque nos permite dar solución a problemas complejos de programacion lineal, y asi mismo sirve para maximizar ganancias y disminuir costos. Este método conforma la base de la programación lineal y es debido a que facilita  la toma de decisiones en casos complejos ya que  permite solucionar sistemas donde en número de variables supera el número de ecuaciones,  ha  resultado ser muy eficiente en la práctica.

Una gran parte de software para cálculos están estrictamente basados en el  método simplex, facilitándonos la interpretación.

Es muy importante en el área empresarial ya que lo utilizan para obtener solución  a los problemas de las empresas en cuanto a inventario, ganancias y pérdidas. Este método permite visualizar cuanto se debe vender, cuanto se debe producir o cuanto se debe comprar según sea el caso para que la empresa obtenga las  ganancias optimas y suficientes para competir en el mercado.

En Base a esta importancia el método simplex ha tenido diversas aplicaciones en  las industrias especialmente en el área de transporte, en la parte de inventarios y en lo empresarial en general.

El método simplex implica cálculos tediosos y voluminosos, lo que hace que la computadora sea una herramienta esencial para resolver los problemas de programación lineal. Por consiguiente, las reglas computacionales del método simplex se adaptan para facilitar el cálculo automático.

El método simplex emplea una forma tabular para simplificar su procedimiento, la forma se obtiene a partir del modelo matemático expresado en forma estándar e igualando a cero la función objetivo .Este proceso que se repite una y otra vez, siempre inicia en un punto extremo de la región factible que normalmente es el origen, en cada iteración se mueve a otro punto extremo adyacente hasta llegar a la solución óptima.

VENTAJAS Y DESVENTAJAS DEL MÉTODO SIMPLEX

                  

 VENTAJAS DEL MÉTODO SIMPLEX

Es un método que se basa en consideraciones geométricas y no  requiere el uso de derivadas de la función objetivo.

Es de gran eficacia incluso para ajustar gran número de parámetros.

Es fácil de implementar y usar, y sin embargo tiene una alta eficacia.

Se puede usar con funciones objetivo muy sinuosas pues en las primeras iteraciones busca el mínimo más ampliamente y evita caer en mínimos locales fácilmente.

                                            

DESVENTAJAS DEL METODO SIMPLEX

Converge más lentamente que otros métodos pues requiere mayor número de iteraciones.

                             

FORMATO ESTANDAR

Otra de las condiciones del modelo estándar del problema es que todas las restricciones sean ecuaciones de igualdad (también llamadas restricciones de igualdad), por lo que hay que convertir las restricciones de desigualdad o inecuaciones en dichas identidades matemáticas.

La condición de no negatividad de las variables (x1,..., xn ≥ 0) es la única excepción y se mantiene tal cual.

• Restricción de tipo "≤"

Para normalizar una restricción con una desigualdad del tipo "≤", hay que añadir una nueva variable, llamada variable de holgura xs (con la condición de no negatividad: xs ≥ 0). Esta nueva variable aparece con coeficiente cero en la función objetivo, y sumando en la ecuación correspondiente (que ahora sí será una identidad matemática o ecuación de igualdad).

a11·x1 + a12·x2 ≤ b1   a11·x1 + a12·x2 + 1·xs = b1

• Restricción de tipo "≥"

En caso de una desigualdad del tipo "≥", también hay que añadir una nueva variable llamada variable de exceso xs (con la condición de no negatividad: xs ≥ 0). Esta nueva variable aparece con coeficiente cero en la función objetivo, y restando en la ecuación correspondiente.

Surge ahora un problema con la condición de no negatividad con esta nueva variable del problema. Las inecuaciones que contengan una desigualdad de tipo "≥" quedarían:

a11·x1 + a12·x2 ≥ b1   a11·x1 + a12·x2 - 1·xs = b1

Al realizar la primera iteración con el método Simplex, las variables básicas no estarán en la base y tomarán valor cero. En este caso la nueva variable xs, tras hacer cero a x1 y x2, tomará el valor -b1 y no cumpliría la condición de no negatividad. Es necesario añadir otra nueva variable xr, llamada variable artificial, que también aparecerá con coeficiente cero en la función objetivo y sumando en la restricción correspondiente. Quedando entonces de la siguiente manera:

a11·x1 + a12·x2 ≥ b1   a11·x1 + a12·x2 - 1·xs + 1·xr = b1

• Restricción de tipo "="

Al contrario de lo que cabría pensar, para las restricciones de tipo "=" (aunque ya son identidades) también es necesario agregar variables artificiales xr. Como en el caso anterior, su coeficiente será cero en la función objetivo y aparecerá sumando en la restricción correspondiente.

a11·x1 + a12·x2 = b1   a11·x1 + a12·x2 + 1·xr = b1

En el último caso se hace patente que las variables artificiales suponen una violación de las leyes del álgebra, por lo que será necesario asegurar que dichas variables artificiales tengan un valor 0 en la solución final. De esto se encarga el método de las Dos Fases y por ello siempre que aparezcan este tipo de variables habrá que realizarlo.

En la siguiente tabla se resume según la desigualdad el tipo de variable que aparece en la ecuación normalizada, así como su signo:

1- Utilizando la forma estándar, determinar una solución básica factible inicial igualando a las n-m variables igual a cero (el origen).

2- Seleccionar la variable de entrada de las variables no básicas que al incrementar su valor pueda mejorar el valor en la función objetivo. Cuando no exista esta situación, la solución actual es la óptima; si no, ir al siguiente paso.

3- Seleccionar la variable de salida de las variables básicas actuales.

4- Determinar la nueva solución al hacer la variable de entrada básica y la variable de salida no básica, ir al paso 2 (actualizar)

Aplicaciones del método simplex.

Este  método o procedimiento cuenta con un sin número de aplicaciones en  programación lineal, pero también usos en matemática y geometría. De entre las  aplicaciones más comunes del método simplex destacan:

- Es una técnica utilizada para dar soluciones numéricas a problemas de programación lineal ya que es comúnmente aplicado para encontrar una solución óptima en   problemas de maximización y minimización.

- Es útil para resolver problemas de gran tamaño y complejos.

- A partir del método simplex se han desarrollado variantes comúnmente utilizadas en programación lineal.

- Este método ha sido de suma utilidad para el desarrollo de software que  facilitan el proceso de cálculos un ejemplo de ello es el TORA.

- Este modelo sirve para la correcta interpretación de modelos de decisión basados en descripciones matemáticas con la finalidad de ayudar en la  toma de decisiones en situaciones de incertidumbre.

Importancia del método simple

Este metodo es de gran importancia,porque nos permite dar solucion a problemas complejos de programacion lineal, y asi mismo sirve para maximizar ganancias y disminuir costos. Este método conforma la base de la programación lineal y es debido a que facilita  la toma de decisiones en casos complejos ya que  permite solucionar sistemas donde en número de variables supera el número de ecuaciones,  ha  resultado ser muy eficiente en la práctica.

Una gran parte de software para cálculos están estrictamente basados en el  método simplex, facilitándonos la interpretación.

Es muy importante en el área empresarial ya que lo utilizan para obtener solución  a los problemas de las empresas en cuanto a inventario, ganancias y pérdidas. Este método permite visualizar cuanto se debe vender, cuanto se debe producir o cuanto se debe comprar según sea el caso para que la empresa obtenga las  ganancias optimas y suficientes para competir en el mercado.

En Base a esta importancia el método simplex ha tenido diversas aplicaciones en  las industrias especialmente en el área de transporte, en la parte de inventarios y en lo empresarial en general.

El método simplex implica cálculos tediosos y voluminosos, lo que hace que la computadora sea una herramienta esencial para resolver los problemas de programación lineal. Por consiguiente, las reglas computacionales del método simplex se adaptan para facilitar el cálculo automático.




Ejercicios 

MinZ= 5X₁+4X₂

·        2X₁+2X₂≤14

·        6X₁+3X₂≥36

·        5X₁+10X₂≥60

·        2X₁+2X₂+S₁=14

·        6X₁+3X₂-S₂+A₁=36

·        5X₁+10X₂-S₃+A₂=60

Z= 5X₁+4X₂+OS₁-OS₂-OS₃+MA₁+MA₂

Z= -5X₁-4X₂-OS₁+OS₂+OS₃-MA₁-MA₂=0

BASE	Z	X1	X2	S1	S2	S3	A1	A2	SOLUCIONES
Z	1	-5	-4	0	0	0	-M	-M	0
S1	0	2	2	1	0	0	0	0	14
(M)A1	0	6	3	0	-1	0	1	0	36
(M)A2	0	5	10	0	0	-1	0	1	60

0	6M	3M	0	-M	0	M	0	36M
0	5M	10M	0	0	-M	0	M	60M
0	11M	13M	0	-M	-M	M	M	96M
1	-5	-4	0	0	0	-M	-M	0
1	-5+11M	-4+13M	0	-M	-M	0	0	96M

BASE	Z	X1	X2	S1	S2	S3	A1	A2	SOLUCION
Z	1	-5+11M	-4+13M	M	-M	-M	0	0	96M
S1	0	2	2	1	0	0	0	0	14/2=7
A1	0	6	3	1	-1	0	1	0	36/3=12
A2	0	5	10	0	0	-1	0	1	60/10=6

X₁= -5+11(1000)=10995

X₂= -4+13(1000)=12996

FILA NUEVA ---

0/10	5/10	10/10	0/10	0/10	-1/10	0/10	1/10	60/10
0	0,5	1	0	0	-0.1	0	0.1	6

FV - (CP.FN)

Z

FV=	1	-5+11M	-4+13M	M	-M	-M	0	0	96M
CP=				-4+13M
FN=	0	0,5	1	0	0	-0,1	0	0,1	6
	1	-3+4.5M	0	M	-M	-0.4+0,3M	0	0,4-1.3M	24+18M

S₁             

FV=	0	2	2	1	0	0	0	0	14
CP=	2	2	2	2	2	2	2	2	2
FN=	0	0,5	1	0	0	-0,1	0	0,1	6
	0	1	0	1	0	0,2	0	-0,2	2

A₁             

FV=	0	6	3	1	-1	0	1	0	36
CP=	3	3	3	3	3	3	3	3	3
FN=	0	0,5	1	0	0	-0,1	0	0,1	6
	0	4,5	0	1	-1	0,3	1	-0,3	18

BASE	Z	X1	X2	S1	S2	S3	A1	A2	SOLUCION
Z	1	-3+4,5M	0	M	-M	-0,4+0,3M	0	0,4-1,3M	24+18M
S1	0	1	0	1	0	0,2	0	-0,2	2
A1	0	4,5	0	1	-1	0,3	1	-0,3	18
X2	0	0,5	1	0	0	-0,1	0	0,1	6

   TABLA FINAL

BASE	Z	X1	X2	S1	S2	S3	A1	A2	SOLUCION
Z	1	0	0	3-4.5M	-M	0.2-06M	0	0.2-04M	30-9M
X1	0	1	0	1	0	0.2	0	-0.2	2
A1	0	0	0	-4.5	-1	-0.6	0	0.6	9
X2	0	0	1	-0.5	0	-0.2	0	0.2	5