Universidad Técnica de Manabí
Facultad De Ciencias Matemáticas Físicas y Químicas
Escuela de Ingeniería Industrial
CÁTEDRA:
INVESTIGACIÓN OPERATIVA
PARALELO:
“A”
DOCENTE:
ING. WILTER ENRIQUE RUIZ PARRAGA
RESPONSABLE:
GOROZABEL VELIZ DAVID
PERIODO:
ABRIL 2019 – AGOSTO 2019
OBJETIVO DE MINIMIZACIÓN
Condición de parada: cuando en la fila Z no aparece ningún valor positivo.
Condición de entrada a la base: el mayor valor positivo en la fila Z indica la variable
Pj que entra a la base.
Condición de salida de la base: una vez obtenida la variable entrante, la variable que
sale se determina mediante el menor cociente P0/Pj de los estrictamente negativos.
No obstante, es posible normalizar el objetivo del problema con el fin de aplicar siempre los
mismos criterios en lo referente a la condición de parada del algoritmo y a las condiciones
de entrada y salida de las variables de la base. De esta forma, si el objetivo es minimizar la
solución, se puede cambiar el problema a otro equivalente de maximización simplemente
multiplicando la función objetivo por "-1". Es decir, el problema de minimizar Z es
equivalente al problema de maximizar (-1)·Z. Una vez obtenida la solución será necesario
multiplicarla también por (-1).
Ventajas: No hay que preocuparse por nuevos criterios de parada, condición de entrada y
salida de la base ya que se mantienen.
Inconvenientes: En el caso de que la función tenga todos los coeficientes de sus variables
básicas positivos, y además las restricciones sean del tipo de desigualdad "≤", al hacer el
cambio dichos coeficientes quedan negativos cumpliéndose la condición de parada en la
primera iteración (en la fila del valor de la función objetivo todos los valores son positivos o
cero). Obteniéndose en este caso por defecto un valor óptimo para la función igual a 0.
Solución: Realmente no existe este problema dado que para que la solución sea superior a 0
es necesario que alguna restricción tenga impuesta la condición "≥" (y se trataría de un
modelo para el método de las Dos Fases). En el caso planteado, la solución real debe ser cero.
Cambio de signo de los términos independientes
También se ha dicho que los términos independientes (bi) de cada ecuación deben ser no
negativos para poder emplear el método Simplex. A tal fin, si alguna de las restricciones
presenta un término independiente menor que 0 habrá que multiplicar por "-1" ambos lados
de la inecuación (teniendo en cuenta que esta operación también afecta al tipo de restricción).
Ventajas: Con ésta simple modificación de signos en las restricciones correspondientes se
posibilita la aplicación del método Simplex al problema modelado.
Inconvenientes: Puede resultar que en las restricciones donde tengamos que modificar los
signos de las constantes, los tipos de desigualdad fueran "≤" (quedando tras la operación del
tipo "≥") siendo necesario desarrollar el método de las Dos Fases. Este inconveniente no es
controlable, aunque podría ocurrir el caso contrario y resultar beneficioso si los términos
independientes negativos se presentan en todas aquellas restricciones con desigualdad de tipo
"≥". Si existe alguna restricción del tipo "=" no supondría ninguna ventaja ni desventaja
puesto que siempre sería de necesaria aplicación el método de las Dos Fases.
Normalización de las restricciones
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:
Tipo de desigualdad Tipo de variable que aparece
≥ - exceso + artificial
= + artificial
≤ + holgura
