SISTEMAS DE INGENIERIA CIVIL CIV251

MÉTODO SIMPLEX

ANTECEDENTES

George Bernard Dantzig (8 de noviembre de 1914 - 13 de mayo de 2005) fue un

profesor, físico y matemático estadounidense reconocido por desarrollar el método
simplex y es considerado como el padre de la programación lineal.

El Método Simplex, publicado en 1947, consiste en un algoritmo iterativo que

secuencialmente a través de iteraciones se va aproximando al óptimo del problema
de Programación Lineal, dicha programación lineal se plantea como un modelo
matemático desarrollado durante la Segunda Guerra Mundial para planificar los
gastos y los retornos, con la única finalidad de llevar ventaja sobre el enemigo, se
mantuvo en secreto hasta 1947 y en la posguerra, muchas industrias lo usaron en
su planificación diaria.

Para poder tener un completo entendimiento del método simplex tenemos que
aclarar el concepto de la programación lineal.

PROGRAMACION LINEAL

La Programación Lineal es un campo concerniente a la optimización matemática

dedicado a maximizar o minimizar una función lineal, denominada función objetivo
y generalmente denotada por Z. Las variables de dicha función Z están sujetas a
una serie de restricciones, las cuales estarán expresadas mediante un sistema de
desigualdades también lineales.

A las etapas de planteamiento e interpretación, se les denominan usos de la

Programación Lineal y a las cuales se les debe dar un énfasis especial en el
desarrollo del presente trabajo. Para obtener una solución en un problema de
Programación Lineal se utilizan diferentes métodos de solución, pero el Método
Simplex es el más general.

En la mayoría de los casos, el camino para identificar una solución óptima para
resolver un método lineal será:

1) Plantear el problema

TODOS PARA UNA

 SISTEMAS DE INGENIERIA CIVIL CIV251

2) Traducirlo a un modo algebraico

3) Definir las restricciones

4) Buscar el óptimo dependiendo del método que se quiera aplicar. Este óptimo se
puede encontrar a través de diferentes métodos.

DEFINICION DE MÉTODO SIMPLEX

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.

Es un proceso repetitivo que permite mejorar la solución de la función objetivo, el

método concluye cuando están satisfechas todas las restricciones, es decir, cuando
se ha llegado a la solución óptima.

IMPORTANCIA DEL MÉTODO SIMPLEX

Este método es de gran importancia, porque nos permite dar solución a problemas
complejos de programación lineal, y así 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

TODOS PARA UNA

 SISTEMAS DE INGENIERIA CIVIL CIV251

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.

A modo de ejemplo se explica cómo se modelan algunos problemas típicos:

• Problema de la dieta

• Problema de transporte de tropas

• Problema de transporte de mercancías

• Problema de los árboles frutales

• Problema de asignación de personal

• Problema del camino mínimo

• Problema de localización

• Problema de inversión en bolsa

• Problemas de personal

Las ventajas de este método son:

 Es eficiente en tiempo operacional

 Es mecánico, se basa en formular matrices y operaciones elementales entre
filas y columnas de las mismas, similar a la eliminación gaussiana.
 No involucra la geometría, por lo que se pueden resolver problemas de
cualquier número de variables y restricciones.

TODOS PARA UNA

 SISTEMAS DE INGENIERIA CIVIL CIV251

VARIABLES DE HOLGURA Y EXCESO

El Método Simplex trabaja basándose en ecuaciones y las restricciones iniciales
que se modelan mediante programación lineal no lo son, para ello hay que convertir
estas inecuaciones en ecuaciones utilizando unas variables denominadas de
holgura y exceso relacionadas con el recurso al cual hace referencia la restricción y
que en el tabulado final representa el "Slack or surplus" al que hacen referencia los
famosos programas de resolución de investigación de operaciones, estas variables
adquieren un gran valor en el análisis de sensibilidad y juegan un rol fundamental
en la creación de la matriz identidad base del Simplex.
Estas variables suelen estar representadas por la letra "S", se suman si la restricción
es de signo "<= " y se restan si la restricción es de signo ">=".
Por ejemplo:

TODOS PARA UNA

 SISTEMAS DE INGENIERIA CIVIL CIV251

APLICACIÓN DEL METODO SIMPLEX

EJEMPLO DE MAXIMIZACION

Para la construcción de un edificio se encargo la elaboración de puertas y ventanas,

para ello cuentan con los siguientes recursos y procesos:

MADERA CRISTAL PINTURA

UTILIDAD
(m2) (m2) (latas)
PUERTA TIPO 1 1 1 3 11

PUERTA TIPO 2 2 2 1 15

VENTANA 3 1 1 9

DISPONIBLE 12 10 13

Determine la cantidad de cada tipo de puerta que deberá fabricar para alcanzar una
utilidad máxima.

Nuestras nuevas variables de decisión serán:

X1= PUERTA TIPO 1

X2 =PUERTA TIPO 2

X3=VENTANA

Objetivo: Maximizar Z=11 X1+ 15 X2+ 9 X3

Con las siguientes restricciones:

1 X1+ 2 X2+ 3 X3 ≤ 12 MADERA

1 X1+ 2 X2+ 1 X3 ≤ 10 CRISTAL

3 X1+ 1 X2+ 1 X3 ≤ 13 PINTURA

Y con las siguientes condiciones de negatividad:

X1, X2, X3 ≥ 0

TODOS PARA UNA

 SISTEMAS DE INGENIERIA CIVIL CIV251

1. Igualamos el objetivos a 0
Z - 11 X1 -15 X2 - 9 X3 = 0

2. Convertir las desigualdades en igualdades agregando coeficientes de

holgura.

1 X1+ 2 X2+ 3 X3 + S1 =12

1 X1+ 2 X2+ 1 X3 + S2 = 10

3 X1+ 1 X2+ 1 X3 + S3 =13

3. Construir nuestra tabla simplex

BASES Z X1 X2 X3 S1 S2 S3 CTE
S1 0 1 2 3 1 0 0 12
S2 0 1 2 1 0 1 0 10
S3 0 3 1 1 0 0 1 13
Z 1 -11 -15 -9 0 0 0 0

Donde:

BASES Z X1 X2 X3 S1 S2 S3 CTE
S1 0 1 2 3 1 0 0 12
S2 0 1 2 1 0 1 0 10
S3 0 3 1 1 0 0 1 13
Z 1 -11 -15 -9 0 0 0 0

La matriz formada en rosado es la matriz de decisión y la matriz amarilla es nuestra

matriz identidad.

4. Identificar columna pivote

La columna pivote se asume según el número más negativo en la función Z.

TODOS PARA UNA

 SISTEMAS DE INGENIERIA CIVIL CIV251

BASES Z X1 X2 X3 S1 S2 S3 CTE
S1 0 1 2 3 1 0 0 12
S2 0 1 2 1 0 1 0 10
S3 0 3 1 1 0 0 1 13
Z 1 -11 -15 -9 0 0 0 0

5. Identificar fila pivote

Para identificar la fila pivote tomamos la solucion de cada fila (en nuestro caso las
CTE) y la dividimos según su correspondiente de la columna pivote. El numero
positivo mas pequeño es el que determina la fila pivote. No se toman en cuenta
negativos, ceros, o divisiones de ceros.

BASES Z X1 X2 X3 S1 S2 S3 CTE
S1 0 1 2 3 1 0 0 12 12/2 6
menor
S2 0 1 2 1 0 1 0 10 10/2 5
positivo
S3 0 3 1 1 0 0 1 13 13/1 13
Z 1 -11 -15 -9 0 0 0 0

El elemento pivote será el elemento que se encuentra entre la fila y columna pivote,
en nuestro caso es el 2.

6. Convertir el elemento pivote a la unidad miltiplicando por su inverso, en

este caso por ½.

BASES Z X1 X2 X3 S1 S2 S3 CTE
S1 0 1 2 3 1 0 0 12
X2 0 1/2 1 1/2 0 1/2 0 5 (*1/2)
S3 0 3 1 1 0 0 1 13
Z 1 -11 -15 -9 0 0 0 0

De esta manera nuestro numero pivote que se encontraba en X2 es ahora la base

de la fila.

TODOS PARA UNA

 SISTEMAS DE INGENIERIA CIVIL CIV251

7. Ya que hemos hecho el elemento pivote unitario entonces el objetivo es

hacer “ceros” tanto arriba como abajo de dicho elemento pivote, según
sea el caso.

BASES Z X1 X2 X3 S1 S2 S3 CTE
S1 0 0 0 2 1 -1 0 2 *-2
X2 0 1/2 1 1/2 0 1/2 0 5
S3 0 2,5 0 0,5 0 -0,5 1 8 *-1
Z 1 -3,5 0 -1,5 0 7,5 0 75 *15

8. Al obtener los ceros en la columna del elemento pivote terminamos ese

ciclo y volvemos a buscar un nuevo elemento pivote y repetimos el
procedimiento hasta obtener que todos los valores de la fila de las Z sean
positivos.

(2DO ELEMENTO PIVOTE)

BASES Z X1 X2 X3 S1 S2 S3 CTE
S1 0 0 0 2 1 -1 0 2 2/0
X2 0 1/2 1 1/2 0 1/2 0 5 5/0,5= 10
S3 0 2,5 0 0,5 0 -0,5 1 8 8/2,5= 3,20
Z 1 -3,5 0 -1,5 0 7,5 0 75

BASES Z X1 X2 X3 S1 S2 S3 CTE
S1 0 0 0 2 1 -1 0 2
X2 0 1/2 1 1/2 0 1/2 0 5
X1 0 1 0 0,2 0 -0,2 0,4 3,2 *1/2,5
Z 1 -3,5 0 -1,5 0 7,5 0 75

BASES Z X1 X2 X3 S1 S2 S3 CTE
S1 0 0 0 2 1 -1 0 2
X2 0 0 1 2/5 0 3/5 - 1/5 3,4 *-1/2
X1 0 1 0 0,2 0 -0,2 0,4 3,2
Z 1 0 0 -0,8 0 6,8 1,4 86,2 *3,5

TODOS PARA UNA

 SISTEMAS DE INGENIERIA CIVIL CIV251

(3ER ELEMENTO PIVOTE)

BASES Z X1 X2 X3 S1 S2 S3 CTE
S1 0 0 0 2 1 -1 0 2 2/2= 1
X2 0 0 1 0,4 0 0,6 -0,2 3,4 3,4/0,4= 8,5
X1 0 1 0 0,2 0 -0,2 0,4 3,2 3,2/0,2= 16
Z 1 0 0 -0,8 0 6,8 1,4 86,2

BASES Z X1 X2 X3 S1 S2 S3 CTE
X3 0 0 0 1 0,5 -0,5 0 1 /2
X2 0 0 1 2/5 0 3/5 - 1/5 3,4
X1 0 1 0 0,2 0 -0,2 0,4 3,2
Z 1 0 0 -0,8 0 6,8 1,4 86,2

BASES Z X1 X2 X3 S1 S2 S3 CTE
X3 0 0 0 1 0,5 -0,5 0 1
X2 0 0 1 0 -0,2 0,8 -0,2 3 *-2/5
X1 0 1 0 0 -0,1 -0,1 0,4 3 *-0,2
Z 1 0 0 0 0,4 6,4 1,4 87 *0,8

Ahí es cuando termina el método ya que todos los valores de la fila Z son positivos.

Entonces tenemos:

X3=1 s3=0
X2=3 S2=0
X1=3 S1=0
Siendo esto porque X1, X2 y X3 entraron en la solucion como bases y S1, S2 y S3
salieron lo cual nos indica que serán 0.

Por lo tanto, estos son los valores para la mejor estrategia del constructor quien, a
su vez, obtendrá un beneficio máximo de:

Z=11(3) + 15(3) + 9(1) =87 que representa el número máximo de utilidad.

TODOS PARA UNA

 SISTEMAS DE INGENIERIA CIVIL CIV251

CONCLUSIONES

Como ve, la solución óptima a este sencillo ejemplo no es la intuitiva. Imagine ahora
este mismo problema si tuviéramos decenas de edificios donde nos encontramos
encargados de puertas y ventanas. La complejidad aumenta, pero con un ordenador
la solución se obtiene de forma rápida.

Este tipo de problemas son muy comunes en todo tipo de empresas y pueden
usarse para optimizar o repartir mejor todo tipo de recursos: recursos económicos
(reducir costos o aumentar beneficios), recursos naturales (materias primas),
recursos humanos (repartir horarios). De igual forma puede emplearse para
maximizar ventajas y minimizar inconvenientes (como contaminación). Por todo
esto, la programación lineal forma parte del temario de muchas titulaciones
universitarias.

En general, podemos decir que los problemas de programación lineal pretenden

buscar el valor óptimo de una función objetivo lineal (su valor máximo o mínimo) de
múltiples variables, de forma que dichas variables estén sujetas a una serie de
restricciones expresadas mediante un sistema de inecuaciones también lineales
(usando ≤ y ≥).

Finalmente, hay que comentar que se han ideado múltiples modificaciones a este
algoritmo, además de otros para los casos no lineales (cuando hay multiplicaciones
entre variables, potencias, raíces, funciones trigonométricas). Por otra parte, existen
multitud de programas informáticos que implementan estas técnicas de
optimización, tales como Lindo, GAMS o Matlab.

TODOS PARA UNA