Clase 3
1. Introducción
Luego de haber aprendido como resolver problemas de programación lineal con dos variables. es
posible que te preguntes ¿Cómo se resuelven problemas en mayor dimensión, es decir cómo se
procede si las variables son tres o más?
En este tramo, analizarás en método SIMPLEX, que consiste en un procedimiento que permite hallar
la solución óptima para este tipo de problemas a partir de iterar por los vértices de la región factible.
También, te propongo abordar el método SOLVER, que permite resolver problemas de maximización
o minimización utilizando una herramienta de Excel.
2. Desarrollo de los contenidos
2.1 ¿En qué consiste el Método SIMPLEX para problemas en más de dos
dimensiones?
A diferencia del método grafico que has visto hasta ahora, el método SIMPLEX fue desarrollado en
1947 por George Dantizg, con el fin de resolver problemas de programación lineal de más de dos
variables.
El propósito del método es encontrar valores para un grupo de variables que optimicen una
función objetivo (que forma parte del modelo matemático que representa el problema), sujeta a
una serie de restricciones que actúan como limitaciones o condicionantes que deben cumplir las
variables, expresadas matemáticamente como igualdades (ecuaciones) o desigualdades
lineales (inecuaciones).
Analiza sus características a partir su aplicación en un ejemplo:
Situación problemática
La fábrica de juguetes A utiliza 3 operaciones para armar 3 tipos de juguetes: trenes, camiones y
autos. Los tiempos diarios disponibles para las 3 operaciones son 430, 460 y 420 minutos
respectivamente y, los ingresos por unidad de tren, camión y auto de juguete son de U$D3, U$D2 y
U$D5. Los tiempos de ensamble por tren en las tres operaciones son de 1, 3 y 1 minuto. Los tiempos
correspondientes por camión son de 2, 0 y 4 minutos y; por auto son de 1, 2 y 0 minutos (un tiempo
0 indica que la operación no se utiliza). Sean 𝑥1 , 𝑥2 𝑦 𝑥3 las cantidades diarias de unidades
ensambladas, se desea saber la cantidad de unidades que se deben ensamblar de cada producto para
obtener la máxima ganancia posible.
Se debe considerar que el tiempo disponible son recursos que deben ser utilizados de manera
eficiente para hallar la combinación óptima de productos fabricados, que impliquen una
ganancia máxima.
A) Resumir la información en una tabla, y determinar las variables de decisión, función objetivo
y restricciones.
Operaciones Tiempo de ensamble en minutos Tiempo disponible en minutos
Tren Camión Auto
1 1 2 1 430
2 3 0 2 460
3 1 4 0 420
Ingresos 3 2 5
1
Variables de decisión:
𝑥1: producir tren.
𝑥2: producir camión.
𝑥3: producir auto.
Función objetivo: Llamaremos Z a los ingresos y como se pide obtener el mayor ingreso
posible estamos ante un problema de maximización.
Z: Ingresos
Máx. Z= 3 𝑥1 + 2 𝑥2 + 5 𝑥3
Ya que el ingreso total obtenido depende del margen unitario de utilidad de cada
producto multiplicado por la cantidad de unidades fabricadas.
Al plantearlas, debemos recordar que las restricciones son los recursos limitados. En este
caso, los recursos están representadas por las operaciones que tienen un límite estipulado
de tiempo. De este modo, tomando en cuenta los datos de la tabla podemos establecer el
siguiente sistema de inecuaciones:
𝑹𝟏 = 𝒙𝟏 + 𝟐 𝒙𝟐 + 𝒙𝟑 ≤ 𝟒𝟑𝟎
{𝑹2 = 3𝒙𝟏 + 𝟎 𝒙𝟐 + 𝟐𝒙𝟑 ≤ 𝟒𝟔𝟎
𝑹3 = 𝒙𝟏 + 𝟒 𝒙𝟐 + 𝟎𝒙𝟑 ≤ 𝟒𝟐𝟎
Sintetizando el modelo algebraico queda como sigue:
𝑴𝑨𝑿 𝒁 = 𝟑𝒙𝟏 + 𝟐𝒙𝟐 + 𝟓𝒙𝟑
S. a
𝑹𝟏 = 𝒙𝟏 + 𝟐 𝒙𝟐 + 𝒙𝟑 ≤ 𝟒𝟑𝟎
𝑹2 = 3𝒙𝟏 + 𝟎 𝒙𝟐 + 𝟐𝒙𝟑 ≤ 𝟒𝟔𝟎
{
𝑹3 = 𝒙𝟏 + 𝟒 𝒙𝟐 + 𝟎𝒙𝟑 ≤ 𝟒𝟐𝟎
𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 ≥ 𝟎
S. a implica sujeto a, y se han agregado restricciones de no negatividad, que indican que
las variables no pueden ser negativas, ya que no es posible producir una cantidad negativa
de producto. Estas últimas restricciones son únicamente indicativas.
B) Igualar a 0 la función objetivo: para ello debes pasar toda la ecuación a un solo miembro,
tomando en cuenta que el hacerlo cambian los signos.
𝑴Ä𝑿 𝒁 − 𝟑𝒙𝟏 − 𝟐𝒙𝟐 − 𝟓𝒙𝟑 =𝟎
C) Para resolver este problema aplicando el método SIMPLEX, se convierten las desigualdades
en ecuaciones agregando variables de holgura. Para ello deberás igualar las restricciones,
sumando esta nueva variable que se denota con la letra 𝑺 (variable de holgura). De este modo
se obtiene:
𝑴Ä𝑿 𝒁 − 𝟑𝒙𝟏 − 𝟐𝒙𝟐 − 𝟓𝒙𝟑 =𝟎
𝒙𝟏 + 𝟐𝒙𝟐 + 𝒙𝟑 + 𝑺𝟏 = 𝟒𝟑𝟎
𝟑𝒙𝟏 + 𝟎𝒙𝟐 + 𝟐𝒙𝟑 + 𝑺𝟐 = 𝟒𝟔𝟎
2
𝒙𝟏 + 𝟒𝒙𝟐 + 𝟎𝒙𝟑 + 𝑺𝟑 = 𝟒𝟐𝟎
Las variables de holgura representan la cantidad de recurso no utilizado en una
restricción y debe cumplir s≥0.
D) Dibujar la tabla SIMPLEX: Se vacía la información anterior en una tabla, donde se indican
las cantidades correspondientes a cada letra. Los valores después de la igualdad se anotan
en la columna solución (Sol.):
Z x1 x2 x3 S1 S2 S3 Sol
F1 Z 1 -3 -2 -5 0 0 0 0
F2 S1 0 1 2 1 1 0 0 430
F3 S2 0 3 0 2 0 1 0 460
F4 S3 0 1 4 0 0 0 1 420
E) Encontrar la columna pivote.
Previamente debes tomar en cuenta que en cada iteración del método SIMPLEX, algunas
variables son básicas y otras no básicas.
Las variables no básicas son aquellas que no están en la base del sistema de ecuaciones
cuando se usa el método. En el caso que estás analizando 𝑺𝟏 , 𝑺𝟐 𝒚 𝑺𝟑 son las variables de
holgura. Al realizar una iteración del método SIMPLEX, la base está formada por ellas, por
lo tanto, 𝒙𝟏 , 𝒙𝟐 𝒚 𝒙𝟑 son las variables no básicas.
Por lo tanto, para encontrar la columna pivote, vas a buscar la variable no básica con el
coeficiente más negativo en la función objetivo.
En iteraciones posteriores, algunas variables no básicas pueden entrar a la base y
convertirse en variables básicas, mientras que otras variables básicas pueden salir de la base
y volverse no básicas.
La variable no básica seleccionada es la variable que entra.
Variable que entra Columna pivote
Z x1 x2 x3 S1 S2 S3 Sol
F1 Z 1 -3 -2 -5 0 0 0 0
F2 S1 0 1 2 1 1 0 0 430
F3 S2 0 3 0 2 0 1 0 460
F4 S3 0 1 4 0 0 0 1 420
F) Encontrar la fila pivote.
Esto implica calcular los valores de la columna solución dividiendo por los coeficientes de
restricción estrictamente positivos que se encuentran en la columna pivote (recordar que
no se puede dividir por 0 o por un número negativo) y seleccionar el resultado de menor
valor. La variable básica seleccionada es la variable que sale.
3
Z x1 x2 x3 S1 S2 S3 Sol
F1 Z 1 -3 -2 -5 0 0 0 0
F2 S1 0 1 2 1 1 0 0 430 430/1=430
F3 S2 0 3 0 2 0 1 0 460 460/2=230
F4 S3 0 1 4 0 0 0 1 420
Variable que sale Fila Pivote
S2 es la variable que sale y que será reemplazada por x3 que es la variable que entra.
El número que intersecta la fila pivote con la columna pivote recibe el nombre de elemento
pivote. En este caso es el número 2.
G) Se debe convertir en 1 el elemento pivote y en 0 (cero) los números que se encuentren
por encima y por debajo de él.
Para convertir en 1 el elemento pivote, en este caso podemos dividirlo por sí mismo o
multiplicarlo por ½. Se debe recordar que, para no alterar la ecuación, se debe operar sobre
todos los valores de la fila pivote, no solamente sobre el elemento pivote.
Dibujaremos una nueva tabla, dónde si bien el encabezado no cambia, la 1° columna de la
izquierda se verá modificada, ya que sale la variable S2 y en su lugar, entra la variable x3.
Realizamos las operaciones que permiten calcular los nuevos valores de la fila pivote que
permiten transformar en 1 al elemento pivote:
Z x1 x2 x3 S1 S2 S3 Sol
F1 Z 1 -3 -2 -5 0 0 0 0 ½ (3) =3/2
F2 S1 0 1 2 1 1 0 0 430 ½*(2) = 1
½*F3 X3 0 3/2 0 1 0 1/2 0 230 ½* 460=230
F4 S3 0 1 4 0 0 0 1 420
Ahora, resta transformar en 0 (cero) los números que se encuentren por encima y por debajo
del elemento pivote. Nuevamente, para no alterar la ecuación, se debe operar sobre todos
los valores de la fila. Para realizarlo, se toma el número a transformar cambiado de signo, se
lo multiplica por el coeficiente correspondiente de la fila pivote y se le suma el coeficiente de
la fila sobre la que se está operando. Veamos las operaciones:
Para la fila 1:
3 15 𝟗
5∗0+1 =𝟏 5 ∗ 2 + (−3) = 2
−3 = 𝟐 5 ∗ 0 + (−2) = −𝟐 5 ∗ 1 + (−5) = 𝟎
5∗0+0 =𝟎 5 ∗ 1/2 + 0 = 𝟓/𝟐 5∗0+0= 𝟎 5 ∗ 230 + 0 = 𝟏𝟏𝟓𝟎
Para la fila 2:
(−1) ∗ 0 + 0 = 0 (− 1) ∗ 3/2 + 1 = −𝟏/𝟐 (−1) ∗ 0 + 2 = 𝟐 (−1) ∗ 1 + 1 = 𝟎
(−1) ∗ 0 + 1 = 𝟏 (−1) ∗ 1/2 + 0 = −𝟏/𝟐 (−1) ∗ 0 + 0 = 𝟎 (−1) ∗ 230 + 430 = 𝟐𝟎𝟎
4
Para la fila 4 no es necesario realizar ninguna operación ya que el coeficiente debajo del
elemento pivote, ya es 0. Volcamos los valores en una nueva tabla:
Z x1 x2 x3 S1 S2 S3 Sol
5 (F3) +F1 Z 1 9/2 -2 0 0 5/2 0 1150
-1 (F3) +F2 S1 0 -1/2 2 0 1 -1/2 0 200
½*F3 X3 0 3/2 0 1 0 1/2 0 230
0 (F3) +F4 S3 0 1 4 0 0 0 1 420
H) Verificar si en las variables no básicas de la función objetivo, existen números
negativos. En nuestro caso, existe 𝑥2 = −2. Para las variables de decisión existe una
restricción de no negatividad, esto implica que sus coeficientes no pueden tomar valores
negativos.
Para poder finalizar el ejercicio, debemos repetir nuevamente los pasos E), F) y G).
E´) Para encontrar la nueva columna pivote, debemos buscar la variable no básica más
negativa, en este caso − 2. Es decir, la columna pivote es la correspondiente a 𝑥2.
Z x1 x2 x3 S1 S2 S3 Sol
Z 1 9/2 -2 0 0 5/2 0 1150
S1 0 -1/2 2 0 1 -1/2 0 200
X3 0 3/2 0 1 0 1/2 0 230
S3 0 1 4 0 0 0 1 420
F´) Se debe encontrar la fila pivote, para ello se deben dividir las soluciones
correspondientes a las restricciones por los coeficientes de la columna pivote (se debe
recordar que está prohibida la división por 0 o por un número negativo). A continuación,
buscamos el resultado más pequeño que nos indica dónde se encuentra la fila pivote.
En el ejemplo, corresponde a la fila 2, y el elemento pivote, es el coeficiente 2.
Variable que entra
Z x1 x2 x3 S1 S2 S3 Sol
Z 1 9/2 -2 0 0 5/2 0 1150
S1 0 -1/2 2 0 1 -1/2 0 200 200/2=100
x3 0 3/2 0 1 0 1/2 0 230
S3 0 1 4 0 0 0 1 420 420/4=105
Variable que sale
G´) Se debe convertir en 1 el elemento pivote y en 0 (cero) los números que se
encuentren por encima y por debajo de él.
Para convertir en 1 el elemento pivote, en este caso podemos dividirlo por sí mismo o
multiplicarlo por ½. Se debe recordar que, para no alterar la ecuación, se debe operar sobre
todos los valores de la fila pivote, no solamente sobre el elemento pivote.
Luego de realizar las operaciones correspondientes, se debe volcar los resultados en una
nueva tabla dónde se reemplaza la variable S1 por la variable que entra x2:
1 1
½∗0 =0 ½ (− ) = − ½∗2 = 1 ½∗0 = 0
2 4
1
½∗1 = ½ (−1/2) = −1/4 ½∗0 =0 ½ ∗ 200 = 100
2
5
Z x1 x2 x3 S1 S2 S3 Sol
Z 1 9/2 -2 0 0 5/2 0 1150
½ * F2 X2 0 -1/4 1 0 1/2 -1/4 0 100
x3 0 3/2 0 1 0 1/2 0 230
S3 0 1 4 0 0 0 1 420
Haremos los cálculos para convertir en 0 los números por encima y por debajo del elemento
pivote.
Para la fila 1:
2∗0+1 = 𝟏 2 ∗ (−1/4) + 9/2 = 8/2 = 𝟒 2 ∗ 1 + (−2) = 𝟎
2∗0+0 = 𝟎 2 ∗ (1/2) + 0 = 𝟏 2 ∗ (−1/4) + 5/2 = 4/2 = 𝟐
2∗0+0 = 𝟎 2 ∗ 100 + 1150 = 𝟏𝟑𝟓𝟎
Para la fila 3, no es necesario realizar ninguna operación, ya que el coeficiente debajo del
elemento pivote, ya es 0.
Para la fila 4:
(−4) 0 + 0 = 𝟎 (−4) (−1/4) + 1 = 𝟐 (−4)1 + 4 = 𝟎
(−4)0 + 0 = 𝟎 (-4)(1/2) + 0 = −𝟐 (−4)(−1/4) + 0 = 𝟏
(−4)0 + 1 = 𝟏 (−4)100 + 420 = 𝟐𝟎
Volca la información en una nueva tabla:
Z x1 x2 x3 S1 S2 S3 Sol
2*F2+F1 Z 1 4 0 0 1 2 0 1350
½ * F2 X2 0 -1/4 1 0 1/2 -1/4 0 100
F3 x3 0 3/2 0 1 0 1/2 0 230
-4* F2+F4 S3 0 2 0 0 -2 1 1 20
Es posible observar que en las variables de la función objetivo (1° fila), ya no quedan
coeficientes negativos, por lo tanto, queda cumplida la restricción de no negatividad y se ha
llegado a la última tabla.
I) Interpretación de los resultados:
Recuerda que las variables de decisión son:
𝑥1: producir tren.
𝑥2: producir camión.
𝑥3: producir auto.
Para determinar cuantas unidades se deben producir de cada una, se debe verificar si
aparecen en la columna de la izquierda.
Z x1 x2 x3 S1 S2 S3 Sol
Z 1 4 0 0 1 2 0 1350
X2 0 -1/4 1 0 1/2 -1/4 0 100
6
x3 0 3/2 0 1 0 1/2 0 230
S3 0 2 0 0 -2 1 1 20
𝑥1: producir tren. No aparece = 0 unidades diarias
𝑥2: producir camión. Aparece = 100 unidades diarias
𝑥3: producir auto. Aparece = 230 unidades diarias
Z: ingresos U$D1350
S3 (restricción 3) Sobran 20 minutos en la operación 3
Los ingresos están determinados por la función objetivo Z ubicada en la fila 1. Es decir, por
día se deben fabricar 100 camiones y 230 autos para obtener una ganancia máxima de
U$D 1350.
También puedes ver que, en la columna izquierda de la tabla, aparece la variable de holgura
S3 correspondiente a la restricción 3, con un resultado igual a 20. Esto indica que han
sobrado 20 minutos del tiempo máximo estipulado para esta operación.
2.2 ¿Cómo utilizar el método SOLVER?
A continuación, te voy a detallar una serie de instrucciones que te permitirán aplicar la herramienta
SOLVER disponible en Excel para resolver problemas de optimización en más de dos dimensiones.
Para ello, te propongo utilizar como ejemplo de aplicación la misma situación problemática que
trabajamos en el método SIMPLEX. Los pasos a seguir son:
A. Definir las variables principales: Para nuestro problema, como se ha visto, el modelo
matemático resultante es:
𝑴𝑨𝑿 𝒁 = 𝟑𝒙𝟏 + 𝟐𝒙𝟐 + 𝟓𝒙𝟑
S. a
𝑹𝟏 = 𝒙𝟏 + 𝟐 𝒙𝟐 + 𝒙𝟑 ≤ 𝟒𝟑𝟎
𝑹 = 3𝒙𝟏 + 𝟎 𝒙𝟐 + 𝟐𝒙𝟑 ≤ 𝟒𝟔𝟎
{ 2
𝑹3 = 𝒙𝟏 + 𝟒 𝒙𝟐 + 𝟎𝒙𝟑 ≤ 𝟒𝟐𝟎
𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 ≥ 𝟎
B. Debes plantear la tabla en Excel marcando con color las celdas que arrojarán los resultados
de las variables principales:
x1 x2 x3 LIR LDR
Valor Signo Holgura
C. En la columna a la derecha (LDR) se colocan los resultados de las restricciones y en signo
si les corresponde mayor o igual, igual o menor o igual. En la columna izquierda se colocan
las restricciones y Z:
x1 x2 x3 LIR LDR
Valor Signo Holgura
R1 <= 430
R2 <= 460
R3 <= 420
7
D. A continuación, se completan los coeficientes correspondientes a las variables de cada
restricción y de la función objetivo:
x1 x2 x3 LIR LDR
Valor Signo Holgura
R1 1 2 1 <= 430
R2 3 0 2 <= 460
R3 1 4 0 <= 420
Z 3 2 5
E. SOLVER requiere que las celdas dónde va a arrojar el valor final, sea una fórmula que será la
suma del producto de las matrices. Se utiliza la formula sumaproducto seleccionando las
celdas en blanco de x1, x2, y x3, luego punto y coma y la fila de los coeficientes
correspondientes a cada restricción y la fórmula objetivo respectivamente.
F. Una vez escritas las fórmulas en la columna valor, obtendremos 0 cómo resultado, ya que x1,
x2 y x3 están momentáneamente vacías.
8
G. Para determinar las variables de holgura, al máximo disponible (LDR) le restamos los
recursos utilizados (LIR). En este caso, H4 -F4; H5 - F5; y H6-F6. Como en esta instancia LIR
vale 0, las variables de holgura coincidirán momentáneamente con los valores de LDR.
H. A continuación, vas a la pestaña “Datos” y pulsas SOLVER. Se abre una ventana de diálogo y
en el borde superior derecho se indica la celda de valor que corresponde a la función
objetivo.
9
I. En "cambiando las celdas de variables" se tildan las celdas vacías correspondientes a 𝑥1, 𝑥2,
y 𝑥3.
J. En "Sujeto a restricciones" se debe clickear agregar, se abre una nueva ventana.
10
K. Se pone el cursor en "Referencia de Celda" y se selecciona la celda correspondiente a valor
de la 1° restricción, en "Restricción" se selecciona el resultado correspondiente a esa
restricción. Entre ambas celdas se agrega el signo correspondiente a la restricción, en este
caso menor o igual (<=). Luego clickeas en agregar y se repite la operación con cada
restricción.
L. Completadas todas las restricciones, se selecciona SIMPLEX LP en método de resolución, y a
continuación "Resolver":
11
M. Se abre otra ventana de dialogo, tildas "Conservar Solución de SOLVER" y aceptas. También
se puede tildar “Sensibilidad” para obtener ese informe y el precio sombra.
N. SOLVER arroja la solución óptima que, como puedes ver coincide con lo obtenido a partir del
método SIMPLEX. Es decir, por día se deben fabricar 100 camiones y 230 autos para
obtener una ganancia máxima de U$D 1350.
12
3. Conclusión
En este tramo has analizado como el método SIMPLEX permite resolver problemas de programación
lineal en mayor dimensión a través de explorar de forma sistemática los vértices de la región factible
hasta poder hallar una solución óptima.
Por otra parte, has visto que SOLVER es un complemento de Excel que permite resolver problemas
de optimización complejos a partir de conocimientos básicos de matemática, lo que facilita a los
tomadores de decisión una implementación práctica y accesible del método.
13
