Universidad Tecnológica de Panamá

Trabajo en clase
Introducción a la Investigación de operaciones
Integrantes: Apolayo, Yohairys
Arcia, Patricia
Escobar, Anaĺs
Jaramillo, Aldo
Franco, Alexia
Guerra, Kristin

1. ¿Qué es el método simplex?

R/
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 y con una mayor capacidad de análisis de sensibilidad.
El Método Simplex es un método iterativo que permite ir mejorando la solución en cada paso. 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, en
la medida en que se pueda satisfacer el conjunto de restricciones, siempre se hallará como mínimo una
solución óptima.

2. ¿ Por qué y cuándo se utiliza este método?

R/
El método simplex es un algoritmo utilizado en la programación lineal para resolver problemas de
optimización. En términos simples, busca encontrar la mejor solución posible a un problema dado,
considerando ciertas restricciones y maximizando o minimizando una función objetivo.
SIMPLEX se resume a un proceso general aplicado en la resolución de problemas relacionados con la
programación lineal. Fue creado en 1947 por Feroge Dantzing y tiempo después, fue comprobada su
inigualable eficacia. Como resultado, se aplicaron de manera rutinaria con el fin de resolver problemas
de gran magnitud presentes en los ordenadores.
A pesar de ser un método que cuenta con un procedimiento algebraico, los conceptos de SIMPLEX
originalmente son geométricos. Por lo tanto, al comprender las definiciones geométricas que nos brinda,
se puede generar una acertada intuición de la manera en que este método trabaja tan eficientemente.
Para ello, se implementa con un procedimiento interactivo; es decir, se aplica de manera sucesiva la
misma rutina de cálculo, lo que genera por resultado una amplia variedad de soluciones sucesivas. Esto
hasta que se encuentre el mejor resultado.
De hecho, una característica elemental de SIMPLEX es que el último resultado obtenido genera una
aportación tan grande que permite dar seguridad a las compañías de que han obtenido una respuesta
óptima, finalmente.

3. ¿Cuáles son los pasos a seguir para su aplicación?

R/
Resolver mediante el método simplex el siguiente problema:

Maximizar Z = f(x,y) = 3x + 2y
Sujeto a: 2x + y ≤ 18
2x + 3y ≤ 42
 3x + y ≤ 24
X≥0,y≥0
Se consideran las siguientes fases:

Realizar un cambio de variables y normalizar el signo de los términos independientes.

Se realiza un cambio en la nomenclatura de las variables. Estableciéndose la correspondencia
siguiente:

X pasa a ser X1
Y pasa a ser X2
Como los términos independientes de todas las restricciones son positivos no es necesario hacer
nada. En caso contrario habría que multiplicar por “-1” en ambos lados de la inecuación (teniendo en
cuenta que esta operación también afecta al tipo de restricción).

Normalizar las restricciones.

Se convierten las inecuaciones en ecuaciones agregando variables de holgura, exceso y artificiales
según la tabla siguiente:

Tipo de desigualdad Tipo de variable que aparece

≥ - exceso + artificial
= + artificial
≤ + holgura
En este caso se introduce una variable de holgura (X3, X4 y X5) en cada una de las restricciones del
tipo ≤, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:

2·X1 + X2 + X3 = 18
2·X1 + 3·X2 + X4 = 42
3·X1 + X2 + X5 = 24
Igualar la función objetivo a cero.
Z – 3·X1 – 2·X2 – 0·X3 – 0·X4 – 0·X5 = 0
Escribir la tabla inicial del método Simplex.
La tabla inicial del método Simplex está compuesta por todos los coeficientes de las variables de
decisión del problema original y las de holgura, exceso y artificiales agregadas en el paso 2 (en las
columnas, siendo P0 el término independiente y el resto de variables Pi coinciden con Xi), y las
restricciones (en las filas). La columna Cb contiene los coeficientes de las variables que se
encuentran en la base.

La primera fila está formada por los coeficientes de la función objetivo, mientras que la última fila
contiene el valor la función objetivo y los costes reducidos Zj – Cj.

La última fila se calcula como sigue: Zj = Σ(Cbi·Pj) para i = 1..m, donde si j = 0, P0 = bi y C0 = 0, y en

caso contrario Pj = aij. Aunque al tratarse de la primera tabla del método Simplex y ser todos los Cb
nulos se puede simplificar el cálculo, y por esta vez disponer Zj = -Cj.

Tabla I . Iteración nº 1
3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P3 0 18 2 1 1 0 0
P4 0 42 2 3 0 1 0
P5 0 24 3 1 0 0 1
Z 0 -3 -2 0 0 0

Condición de parada.
Si el objetivo es la maximización, cuando en la última fila (fila indicadora) no existe ningún valor
negativo entre los costes reducidos (columnas P1 en adelante) se alcanza la condición de parada.

En tal caso se llega al final del algoritmo ya que no existe posibilidad de mejora. El valor de Z
(columna P0) es la solución óptima del problema.

Otro caso posible es que en la columna de la variable entrante a la base todos los valores son
negativos o nulos. Esto indica que el problema no se encuentra acotado y su solución siempre
resultará mejorable. Ante esta situación no es necesario continuar iterando indefinidamente y
también se puede dar por finalizado el algoritmo.

De no ser así, se ejecutan los siguientes pasos de forma iterativa.

Elección de la variable entrante y saliente de la base.

Se determina en primer lugar la variable que entra en la base. Para ello se escoge la columna cuyo
valor en la fila Z sea el menor de entre todos los negativos. En este caso sería la variable X1 (P1) de
coeficiente -3.

Si existiesen dos o más coeficientes iguales que cumplan la condición anterior (caso de empate),
entonces se optará por aquella variable que sea básica.

La columna de la variable que entra en la base se llama columna pivote (en color verde).

Una vez obtenida la variable que entra en la base, se procede a determina cual será la variable que
sale de la misma. La decisión se toma en base a un sencillo cálculo: dividir cada término
independiente (columna P0) entre el elemento correspondiente de la columna pivote, siempre que
ambos elementos sean estrictamente positivos (mayores que cero). Se escoge la fila cuyo resultado
haya resultado mínimo.

Si hubiera algún elemento menor o igual a cero no se realiza dicho cociente. En caso de que todos
los elementos de la columna pivote fueran de ésta condición se habría cumplido la condición de
parada y el problema tendría una solución no acotada (ver teoría del método Simplex).

En este ejemplo: 18/2 [=9] , 42/2 [=21] y 24/3 [=8]

El término de la columna pivote que en la división anterior dio lugar al menor cociente positivo indica
la fila de la variable de holgura que sale de la base. En este caso resulta ser X5 (P5), de coeficiente 3.
Esta fila se llama fila pivote (en color verde).

Si al calcular los cocientes, dos o más resultados cumplen la condición para elegir el elemento
saliente de la base (caso de empate), se escoge aquella que no sea variable básica (siempre que sea
es posible).

La intersección de la fila pivote y columna pivote marca el elemento pivote, en este caso el 3.
Actualizar la tabla.
Los nuevos coeficientes de la tabla se calculan de la siguiente manera:

En la fila del elemento pivote cada nuevo elemento se calcula como:

Nuevo Elemento Fila Pivote = Anterior Elemento Fila Pivote / Pivote
En el resto de las filas cada elemento se calcula:
Nuevo Elemento Fila = Anterior Elemento Fila – (Anterior Elemento Fila en Columna Pivote * Nuevo
Elemento Fila Pivote)
Con esto se normaliza el elemento pivote y su valor pasa a ser 1, mientras que el resto de elementos
de la columna pivote se anulan (análogo al método de Gauss-Jordan).

Se muestran a continuación los cálculos para la fila P4:

Anterior fila P4 42 2 3 0 1 0
- - - - - -
Anterior Elemento Fila en Columna Pivote 2 2 2 2 2 2
X x x x x x
Nueva fila pivote 8 1 1/3 0 0 1/3
= = = = = =
Nueva fila P4 26 0 7/3 0 1 -2/3
La tabla correspondiente a esta segunda iteración es:

Tabla II . Iteración nº 2
3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P3 0 2 0 1/3 1 0 -2/3
P4 0 26 0 7/3 0 1 -2/3
P1 3 8 1 1/3 0 0 1/3
Z 24 0 -1 0 0 1
Al comprobar la condición de parada se observa que no se cumple ya que entre los elementos de la
última fila hay uno negativo, -1. Se continúa iterando nuevamente los pasos 6 y 7.
6.1. La variable que entra en la base es X2 (P2), por ser la variable que corresponde a la columna
donde se encuentra el coeficiente -1.
6.2. Para calcular la variable que sale, se dividen los términos de la columna P0 entre los términos
correspondientes de la nueva columna pivote: 2 / 1/3 [=6] , 26 / 7/3 [=78/7] y 8 / 1/3 [=24]. Como el
menor cociente positivo es 6, la variable que sale de la base es X3 (P3).
6.3. El elemento pivote es 1/3.
7. Actualizando nuevamente los valores de la tabla se obtiene:

Tabla III . Iteración nº 3

3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P2 2 6 0 1 3 0 -2
P4 0 12 0 0 -7 1 4
P1 3 6 1 0 -1 0 1
Z 30 0 0 3 0 -1
Una nueva comprobación de la condición de parada revela que entre los elementos de la fila
indicadora vuelve a haber uno negativo, -1. Significa que aun no se ha llegado a la solución óptima y
hay que seguir iterando (pasos 6 y 7):
 6.1. La variable que entra en la base es X5 (P5), por ser la variable que corresponde al coeficiente -1.
6.2. Se escoge la variable que sale calculando el cociente entre los términos de la columna de
términos independientes y los términos correspondientes de la nueva columna pivote: 6/(-2) [=-3] ,
12/4 [=3], y 6/1 [=6]. En esta ocasión es X4 (P4).
6.3. El elemento pivote es 4.
7. Después de actualizar todas las filas, se obtiene la tabla siguiente:

Tabla IV . Iteración nº 4
3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P2 2 12 0 1 -1/2 ½ 0
P5 0 3 0 0 -7/4 ¼ 1
P1 3 3 1 0 ¾ -1/4 0
Z 33 0 0 5/4 ¼ 0
Fin del algoritmo.
Se observa que en la última fila todos los coeficientes son positivos cumpliéndose, por tanto la
condición de parada.

La solución óptima viene dada por el valor de Z en la columna de los términos independientes (P0),
en este ejemplo: 33. En la misma columna se puede ver el punto donde se alcanza, observando las
filas correspondientes a las variables de decisión que han entrado en la base: X1 = 3 y X2 = 12.

Deshaciendo el cambio de variable.

4. ¿Cuándo sabemos que se ha obtenido la respuesta correcta?

R/

Básicamente cuando se genera una nueva base se debe satisfacer la condición de optimización. Si
se cumple esta condición el algoritmo se termina. Recuerde que esta condición depende de si la
función objetivo es de maximizar o minimizar. Con esta condición se determina la variable básica
que sale de la base.

5. ¿Cuál es el máximo de variables que se puede utilizar en este método?

R/
El método simplex es una técnica utilizada en la optimización lineal para resolver problemas de
programación lineal. El número máximo de variables que se pueden utilizar en el método simplex
está limitado por el tamaño de la computadora o sistema en el que se está ejecutando, y también
por las características específicas del software de optimización utilizado.
En la teoría, no hay un límite máximo fijo en el número de variables que se pueden utilizar en un
problema de programación lineal, ya que el método simplex puede aplicarse a problemas con
cualquier número de variables y restricciones. Sin embargo, en la práctica, el tamaño del problema
que se puede manejar depende de factores como:
• Capacidad de memoria: Un problema con muchas variables y restricciones requerirá más
memoria, y el método simplex necesitará trabajar con matrices grandes

• Tiempo de ejecución: A medida que el número de variables y restricciones aumenta, el tiempo

necesario para ejecutar el método simplex también aumenta.
 • Software de optimización: Los distintos programas de optimización pueden tener diferentes límites
de tamaño para las matrices y problemas que pueden manejar de manera eficiente.

6. ¿Qué programas de computadoras se pueden utilizar para resolver problemas con este
método?
R/
Existen varios programas de software que se pueden utilizar para resolver problemas de
programación lineal con el método simplex. Estos programas de optimización lineal proporcionan
implementaciones eficientes del método simplex y otros algoritmos de optimización. Algunos de los
programas más populares son:

•Gurobi: Es uno de los solvers de programación lineal y mixta más conocidos. Ofrece una
implementación eficiente del método simplex, así como otros algoritmos avanzados. Proporciona
interfaces para varios lenguajes de programación, como Python, Java, C++, entre otros.

•IBM CPLEX: Es otro solver líder en optimización que admite programación lineal, entera y
cuadrática. CPLEX también ofrece una implementación sólida del método simplex y es compatible
con varios lenguajes de programación.

•MATLAB: MATLAB es una plataforma de cálculo numérico ampliamente utilizada que incluye
funciones de optimización, entre ellas una función para resolver problemas de programación lineal
con el método simplex.

•SciPy: Es una biblioteca de Python que incluye una función ([Link]) para resolver
problemas de programación lineal utilizando el método simplex y otros algoritmos.

•OR-Tools: Es una biblioteca de Google que ofrece una variedad de herramientas para la
optimización, incluida la programación lineal. Proporciona soporte para varios algoritmos, incluido el
método simplex.

•COIN-OR: El Proyecto COIN-OR es una colección de bibliotecas de software de código abierto para
optimización. Incluye solvers como CLP (COIN-OR Linear Programming), que implementan el
método simplex.

7. ¿Qué se entiende por tablón inicial en el método simple?

R/
Se entiende por el método en el que se construye una tabla qué muestre las variables y las
restricciones, en la cual se realiza una serie de iteraciones para encontrar una solución óptima al
problema, esta compuesta por todos los coeficientes de las variables de decisión del problema
original y las de holgura.
8. Describa cada una de las variables que se utilizan con este método y explique cuando se deben
utilizar.
R/
Variables de entrada
Estas suelen encontrarse en un criterio que se conoce como “Condición de optimalidad”, en un
modelo, ya sea de maximización o minimización, y se refiere a la variable no básica en el renglón “z”
con el coeficiente más negativo, si se trata de una maximización, o el coeficiente más positivo, si se
trata de una minimización, la cual, en la tabla de solución anterior, a excepción de la primera tabla,
esta variable era una variable básica.
Variables de salida
Esta variable es un punto extremo que se encuentra en un criterio conocido como “condición de
factibilidad”, en un modelo, ya sea de optimización o minimización, y se refiere a la variable básica
asociada con la mínima razón no negativa con el coeficiente más negativo, si se trata de una
maximización, o el coeficiente más positivo, si se trata de una minimización, la cual, en la tabla de
solución siguiente, pasará a ser variable no básica.

Variable degenerada
Una variable degenerada es una variable básica que vale cero. Gráficamente esto puede ocurrir
cuando más de dos rectas tocan una sola intersección en el mismo punto.
Base
Conjunto de variables básicas. En el ejemplo anterior, la base es {X3, X4, X5, X6}

Variable no restringida
 Variable artificial
Se usa una variable artificial cuando las restricciones son = y ≥ y sucede cuando el origen no se
encuentra dentro de la región factible, tratando de llevar el modelo a otra dimensión en la cual el
origen si exista en la región.
Es aquella que puede tomar toda clase de valores positivos, cero y negativos puede escribirse
como la diferencia de dos variables no-negativas.

9. Explique con sus palabras un problema resuelto aplicando este método.

R/
Problema del transporte
El problema del transporte es un planteamiento clásico de las técnicas de programación lineal. En
este problema se pretende elegir el camino óptimo de envío de una mercancía desde varios orígenes
(por ejemplo, plantas de producción) a diferentes destinos (centros de almacenamiento o
consumo), de forma que el coste sea mínimo.

Como en todo problema de programación lineal, han de cumplirse las siguientes etapas:

Definir las variables del problema (por ejemplo, las cantidades de partida solicitadas en cada
destino, el coste de envío de una unidad de mercancía a cada destino).
Escribir conceptualmente el sistema de inecuaciones asociado a las restricciones del problema (por
ejemplo, el número de unidades máximas producidas en cada origen y las requeridas en cada
destino).
Definir conceptualmente la función objetivo, que determina el coste.
Resolución del problema del transporte
Una vez planteado el problema, se construye una tabla de distribución, de la que se obtienen las
expresiones matemáticas de las inecuaciones del sistema y la función objetivo. Para resolverla se
usan los métodos gráficos o algebraicos comunes de la programación lineal.