Optimización
• El método de asignación de recursos, se utiliza
cada vez más en la industria de los servicios. Sin
embargo, su fundamentación y aplicación se
concentran específicamente en un tema de
ingeniería que en ocasiones resulta complejo de
entender en las áreas de adiestramiento social.
Por tanto, se presenta en el siguiente ejercicio
una simplificación del método simplex para ser
comprendido y utilizado en la asignatura de
modelos matemáticos para el turismo.
• Durante la segunda guerra mundial se crean grupos
de expertos, con el propósito de resolver
problemas complejos (investigación de
operaciones). Estos conocimientos, fueron
posteriormente transferidos a las empresas para
ser utilizados en la toma de decisiones razonadas
(Thierauf, 2013).
• La imperante necesidad de registrar los
rendimiento de la materia prima y la utilización de
los medios de producción se reflejó en el
surgimiento de la administración científica, la cual
formaliza la técnica y la subordina a la
generación de beneficios económicos en las
organizaciones productivas.
El método simplex constituye un modelo
determinista, el cual utiliza datos
conocidos de las organizaciones
productivas, para desarrollar análisis de
optimización y facilitar. Lo anterior, con la
intención de fortalecer las decisiones que
se toman en una relación productiva.
• El método constituye un procedimiento
matricial, en que se desarrolla una
ampliación de variables a partir de un
sistema de ecuaciones.
• a11 +a12+a13=α
• a21+a22+a23=β
• a31+a32+a33=γ
• La aplicación de las variables se
desarrolla para poder dar respuesta
analítica a las ecuaciones, con base en
la siguiente tabla.
Aumento Simplex Maximizar
Minimizar
Signo
≤ +S +S
≥ -S -S +M
= ------------ +M
Solución Cj-Zj Sin valores positivos Sin valores negativos
Donde: S= variable de holgura
M= variable artificial
Las variables de holgura permiten determinar los
excedentes de las restricciones que podrían ser
empleados en otros fines sin que la solución óptima se
altere.
Las variables de holgura permiten convertir las
desigualdades de las restricciones en igualdades, lo
cual llega a representar el sobrante de las
disponibilidades de cada recurso; en el caso que se
desarrolla como ejemplo, es la capacidad de horas
máquina en cada proceso o departamento.
Las restricciones lineales de forma:
Agregando una nueva variable no negativa al lado izquierdo de la
desigualdad se pueden convertir en ecuaciones, ésta variable es
numéricamente igual a la diferencia entre el lado izquierdo y
derecho de la desigualdad. Por lo cual las desigualdades quedan
con vértices en las siguientes ecuaciones:
Las variables de holgura S1 y S2 muestran los excedentes de
tiempo en la capacidad no utilizada en los procesos I y II
respectivamente.
EJERCICIO DE CONSTRUCCIÓN
DE UN MODELO CON HOLGURAS
Max Z= 50X1 + 60X2 + 45X3
2X1 + 3X2 + X3 < 2500
3X1 + 4X3 < 3000
X1 + X2 + 3X3 < 1750
X1, X2, X3 > 0
Max Z= 50X1 + 60X2 + 45X3 + 0S1 + 0S2 + 0S3
2X1 + 3X2 + X3 + 1S1 + 0S2 + 0S3 = 2500
3X1 + 0X2 + 4X3 + 0S1 + 1S2 + 0S3 = 3000
X1 + X2 + 3X3 + 0S1 + 0S2 + 1S3 = 1750
Matriz identidad
PLANTEAMIENTO
Maximizar Z
Z=3X1+5X2
Restricciones:
X1<= 4
2X2<=12
3X1+2X2<=18
X1,X2>=0
FORMA AUMENTADA
Max Z=3X1 + 5X2 + 0S1+ 0S2 + 0S3
Restricciones
1 X1 + 0X2 + S1 + 0S2 + 0S3 =4
2 0X1 + 2X2 + 0S1 + S2 + 0S3 = 12
3 3X1 + 2X2 + 0S1 + 0S2 + S3 = 18
Se trata a Z como si fuera una de las restricciones
originales, como se encuentra en forma de igualdad
no necesita variables de holgura, pero se agrega Z con
la finalidad de obtener su valor.
Z- 3X1 - 5X2 + 0S1 + 0S2 +0S3 = 0
La solución BF ( solución básica factible) si y solo si
todos los coeficientes del renglón 0 son negativos
Paso inicial: Se introducen las variables de holgura, se
seleccionan las variables de decisión como no básicas
iníciales
Tabla inicial
Variable Coeficientes de: Resultados
básica X1 X2 S1 S2 S3
Z -3 -5 0 0 0 0
S1 1 0 1 0 0 4
S2 0 2 0 1 0 12
S3 3 2 0 0 1 18
Paso 1: Se determina la variable básica, con la selección
de la variable con el coeficiente negativo que tiene el
mayor valor absoluto de la ecuación 0
Variable Coeficientes de: Resultados
básica Z X1 X2 S1 S2 S3
Z 1 -3 -5 0 0 0 0
S1 0 1 0 1 0 0 4
S2 0 0 2 0 1 0 12
S3 0 3 2 0 0 1 18
columna pivote
Paso 2: Determinar la variable basica y la fila pivote
que sale con la prueba del cociente mínimo.
(Dividir resultados entre la columna pivote)
Variable Coeficientes de: Razón /
Resultados
básica X1 X2 S1 S2 S3
Z -3 -5 0 0 0 0
S1 1 0 1 0 0 4 (4/0)
S2 0 2 0 1 0 12
(12/2=6) Mínimo
S3 3 2 0 0 1 18
(18/2=9)
NOTA: La fila de Z nunca deberá ser elegible
1. Elija coeficientes estrictamente positivos (>0) en la
columna pivote
2. Divida cada coeficiente entre el elemento del lado
derecho del mismo renglón
3. Identifique el renglón que tiene el menor de estos
cocientes
4. La variable básica de ese renglón es la variable básica
que sale; sustitúyala por la variable básica entrante
en la columna de la variable básica de la tabla
siguiente.
Paso 3: Se despeja a nueva solución BF mediante
operaciones elementales con renglones.
1. Divida el renglón pivote entre el numero pivote. Use
este nuevo renglón pivote en los pasos 2 y 3
2. En los renglones (incluso renglón 0) que tienen un
coeficiente negativo en la columna pivote, se suma a
este renglón el producto del valor absoluto de este
coeficiente por el nuevo renglón pivote.
Nuevo Elemento del Valor absoluto Nuevo
elemento renglón que se elemento del
tiene. del Elemento
del renglón intersección. renglón
pivote
3. En caso de los renglones que tienen un cociente
positivo en la columna pivote, se resta el producto de
este coeficiente
Nuevo Elemento del Valor absoluto Nuevo
elemento renglón que se del Elemento elemento del
tiene.
del renglón intersección. renglón
pivote
Dividir toda la fila entre el valor pivote (El valor donde se cruzan la fila
y la columna pivote. Valor pivote
Variable Coeficientes de: Razon
básica X1 S2 S1 S2 S3
Z -3 -5 0 0 0 0
S1 1 0 1 0 0 4
S2 0 2 0 1 0 12 12/2=6
S3 3 2 0 0 1 18 18/2=9
Z
S1 1 – (0 x 0)=1 0 – (0 x1)= 0 1 – (0 x0) =1 0 – (0 x ½) 0 0 – (0 x 0)=0 4 – (0x6) =4
X2 0 1 0 ½ 0 6
S3 3 – (2 x 0)=3 2 – (2 x 1)=0 0 – (2 x0) =0 0- (2x1/2)=-1 1 – (2x0)= 1 18 – (2x6=6
(0/2) (2/2) (0/2) (1/2) (0/2) (12/2)
Dividir toda la fila entre el valor pivote (El valor donde se cruzan la fila
y la columna pivote. Valor pivote
Variable Coeficientes de: Razon
básica X1 S2 S1 S2 S3
Z -3 -5 0 0 0 0
Tabla Inicial
S1 1 0 1 0 0 4
S2 0 2 0 1 0 12 12/2=6
S3 3 2 0 0 1 18 18/2=9
Z -3 0 0 5/2 0 30
Tabla 1 Simplex
S1
x2 0 1 0 ½ 0 6
S3
(-3 - (-5 x 0)) (b) (c) (d) (e) (f)
Variable Coeficientes de: Razon
básica X1 S2 S1 S2 S3
Tabla 1 Simplex
Z -3 0 0 5/2 0 30
S1
x2 0 1 0 ½ 0 6
S3 Nueva fila
(a) (b) (c) (d) (e) (f)
a) -3 - (-5 x 0 ) = -3
b) -5 - (-5 x 1 ) = 0
c) 0 - (-5 x 0 ) = 0
d) 0 - (-5 x 1/2 ) = 5/2
e) 0 - (-5 x 0 ) = 0
f) 0 - (-5 x 0 ) = 30
-3 - (-5 x 0 ) = -3 1-(0x0)= 1
SEGUNDA FILA
PRIMERA FILA
-5 - (-5 x 1 ) = 0 0-(0x1 )= 0
0 - (-5 x 0 ) = 0 1-(0x0 )= 1
0 - (-5 x 1/2 ) = 5/2 0 - ( 0 x 1/2 ) = o
0 - (-5 x 0 ) = 0 0-(0x0 )= 0
0 - (-5 x 6 ) = 30 4-(0x6 )= 4
(0 /2)= 0 3-(2x0) = 3
FILA
TERCERA FILA
(2 /2)= 1 2-(2x1 ) = 0
(0 /2)= 0 0-(2x0 ) = 0
CUARTA
(1 /2)= 1/
2
0 - ( 2 x 1/2 ) = -1
(0 /2)= 0 1-(2x0 ) = 1
( 12 / 2 ) = 6 18 - ( 2 x 6 ) = 6
Variable Coeficientes de: Razon
básica X1 S2 X3 X4 X5
Z -3 0 0 5/2 0 30
Tabla 1 Simplex
S1 1 0 1 0 0 4
x2 0 1 0 ½ 0 6
S3 3 0 0 -1 1 6
Determinar de nuevo la variable basica y la fila pivote que sale con la
prueba del cociente mínimo.
(Dividir resultados entre la columna pivote)
.
Variable Coeficientes de: Razón /
básica Resultados
X1 S2 S1 S2 S3
Z -3 0 0 5/2 0 30
S1 1 0 1 0 0 4 4/1=4
x2 0 1 0 ½ 0 6 6/0=E
S2 3 0 0 -1 1 6 6/3 =2
-3 – (-3 x 1) = 0 1–(1x1)=0
PRIMERA FILA
SEGUNDA FILA
0 – (-3 x 0) = 0 0 – (1 x 0) = 0
0 – (-3 x 0) = 0 1 – ( 1 x 0) = 1
5/2 – (-3x -1/3) = 3/2 0 – (1 x -1/3) = 1/3
0 – (-3 x 1/3) = 1 0 – (1 x 1/3) = - 1/3
30 – (-3 x 2) = 36 4 – (1 x 2) = 2
0 – ( 0 x 1) = 0 (3 /3)= 1
TERCERA FILA
CUARTA FILA
1 – ( 0 x 0) = 1 (0 /3)= 0
0 – ( 0 x 0) = 0 (0 /3)= 0
½ - (0 x -1) = ½ ( -1 / 3 ) = -1/3
(1 /3 )= 1/
0 – (0 x 1/3) = 0 3
6 – (0 x 2) = 6 (6/3 )= 2
Variable Coeficientes de: Razon
básica X1 X2 X3 X4 X5
Tabla 1 Simplex
Z -3 0 0 5/2 0 30
S1 1 0 1 0 0 4 4/1=4
x2 0 1 0 ½ 0 6 6/1=6
S3 3 0 0 -1 1 6 6/3 =2
S3 X2 X3 X4 X5
Tabla 2 Simplex
Z 0 0 0 3/2 1 36
X3 0 0 1 1/3 -1/3 2
x2 0 1 0 ½ 0 6
x1 1 0 0 -1/3 1/3 2
Variable Coeficientes de: Razon
básica S3 X2 X3 X4 X5
Tabla 2 Simplex
Z 0 0 0 3/2 1 36
S1 0 0 1 1/3 -1/3 2
x2 0 1 0 ½ 0 6
x1 1 0 0 -1/3 1/3 2
Cuando los valores en Z son
todos positivos significa que ya
no puede optimizarse más por lo
tanto se llegó al resultado óptimo
Variable Coeficientes de: Razón/
básica S3 X2 X3 X4 X5 Resutados
Tabla 2 Simplex
Z 0 0 0 3/2 1 36
S1 0 0 1 1/3 -1/3 2
x2 0 1 0 ½ 0 6
x1 1 0 0 -1/3 1/3 2
Los números en esta columna
representan los valores de las
variables y holguras de la
columna de variable básica
Solución es X1=2 , X2=6 y hay una
holgura (S1=2) en la restricción 1, para
un valor óptimo de Z = 36
Función Objetivo
Z = 3 (2) + 5 (6) = 36 Holgura (S1 = 2)
Restricciones
(2)+ (2) = 4
2 (6) = 12
3 (2) + 2 (6) = 18
MINIMIZAR
MINIMIZAR
Para Minimizar se puede :
Cambiar los roles de los coeficientes negativos y
positivos en el renglón 0, tanto para la prueba de
optimalidad como para el paso de iteración 1
Convertir cualquier problema de minimización en uno
equivalente de maximización.
Minimizar
Z=0.4X1 + 0.5X2
Restricciones:
0.3X1 + 0.1X2 <= 2.7
0.5X1 + 0.5X2 = 6
0.6X1 + 0.4X2 >=6
Minimizar Z = 0.4X1 + 0.5X2
Maximizar Z = -0.4X1 + -0.5X2
Sistema de ecuaciones completo
(0) –Z + 0.4X1 + 0.5X2 + MA4 + MA6 = 0
(1) 0.3X1 + 0.1X2 + X3 = 2.7
(2) 0.5X1 + 0.5X2 + A4 =6
(3) 0.6X1 + 0.4X2 - X5 + A6 = 6
El sistema de ecuaciones todavía no esta en la forma
apropiada de eliminación gussiana para iniciar el
método simplex, puesto se deben eliminar las variables
básicas A4 y A6 de la ecuación 0 de manera algebraica.
Renglon 0:
[0.4, 0.5, 0, M, 0, M, 0]
-M[0.5, 0.5, 0, 1, 0, 0, 6]
-M[0.6, 0.4, 0, 0, -1, 1 , 6]
Nvo. Renglon 0 : [-1.1M + 0.4, -0.9M+0.5, 0, 0, M, 0, -12M]
Var. Coeficientes de: Razón
básica
X1 X2 X3 M4 X5 M6
Z -1.1M+0.4 -0.9M+0.5 0 0 M 0 -12M
X3 0.3 0.1 1 0 0 0 2.7
X4 0.5 0.5 0 1 0 0 6
X5 0.6 0.4 0 0 -1 1 6
Var. Coeficientes de: Razón
básica
Z X1 X2 X3 M X5 M6
4
Z -1 -1.1M+0.4 -0.9M+0.5 0 0 M 0 -12M
S3 0 0.3 0.1 1 0 0 0 2.7
S4 0 0.5 0.5 0 1 0 0 6
S6 0 0.6 0.4 0 0 -1 1 6
Z -1 0 - 11/3M- 0 M 0 -2.1M-3.6
16/30M+11/30 4/3
X1 0 1 1/3 10/3 0 0 0 9
X4 0 0 1/3 -5/3 1 0 0 1.5
X6 0 0 0.2 -2 0 -1 1 0.6
Var. Coeficientes de: Razón
básica
Z X1 X2 X3 M4 X5 X6
Z -1 0 -16/30M+11/30 11/3M- 0 M 0 -2.1M-3.6
4/3
X1 0 1 1/3 10/3 0 0 0 9
X4 0 0 1/3 -5/3 1 0 0 1.5
X6 0 0 0.2 -2 0 -1 1 0.6
Z -1 0 0 -5/3M+ 0 - 8/3M – -0.5M -
7/3 5/3M+ 11/6 4.7
11/6
X1 0 1 0 20/3 0 5/3 -5/3 8
X4 0 0 0 5/3 1 5/3 -5/3 0.5
X2 0 0 1 -10 0 -5 5 3
Var. Coeficientes de: Razón
básica
Z X1 X2 X3 M4 X5 M6
Z -1 0 0 -5/3M+ 0 - 8/3M – -0.5M -
7/3 5/3M+1 11/6 4.7
1/6
X1 0 1 0 20/3 0 5/3 -5/3 8
X4 0 0 0 5/3 1 5/3 -5/3 0.5
X2 0 0 1 -10 0 -5 5 3
Z -1 0 0 0.5 M- 0 M -5.25
1.1
X1 0 1 0 5 -1 0 0 7.5
X5 0 0 0 1 0.6 1 -1 0.3
X2 0 0 1 -5 3 0 0 4.5