ESPACIO DE SOLUCIONES EN FORMA DE ECUACIÓN

Para estandarizar, la representación algebraica del espacio de soluciones de programación

lineal se forma bajo dos condiciones:

1. Todas las restricciones (excepto las de no negatividad) son ecuaciones con lado
derecho no negativo.
2. Todas las variables son no negativas.
Conversión de desigualdades a ecuaciones

En las restricciones (≤), el lado derecho se puede imaginar como representando el límite de
disponibilidad de un recurso, y en ese caso el lado izquierdo representaría el uso de esos
recursos o limitado por parte de las actividades (variables) del modelo. La diferencia entre el
lado derecho y el lado izquierdo de la restricción (≤) representa, por consiguiente, la cantidad
no usada u holgura del recurso.

Para convertir una desigualdad (≤) en ecuación, se agrega una variable de holgura al lado
izquierdo de la restricción. Por ejemplo, en el modelo de Reddy Mikks.

Una restricción (≥) establece, normalmente, un límite inferior para las actividades del modelo
de programación lineal. Como tal, la cantidad por la que el lado izquierdo es mayor que el
límite mínimo (lado derecho) representa un excedente. La conversión de (≥) a (=) se logra
restando una variable de excedencia, del lado izquierdo de la desigualdad.

TRANSICIÓN DE SOLUCIÓN GRÁFICA A SOLUCIÓN ALGEBRAICA

Método gráfico

Grafica todas las restricciones, incluyendo las de no negatividad

El espacio de soluciones consiste en una infinidad de puntos esquina factibles

Identifica puntos factibles de esquina del espacio de soluciones

Los candidatos a la solución óptima corresponden a una cantidad finita de puntos de esquina

Se usa la función objetivo para determinar el punto esquina óptimo entre todos los candidatos
Método algebraico

Representa el espacio de soluciones con m ecuaciones con n variables, y restringe a todas las
variables a valores no negativos; m< n

El sistema tiene infinidad de soluciones factibles

Determina las soluciones básicas factibles de las ecuaciones

Las candidatas a solución óptima corresponden a una cantidad finita de soluciones básicas
factibles

Se usa la función objetivo para determinar la solución básica factible óptima entre todas las
candidatas

Que representan las restricciones, y en el método símplex, el espacio de soluciones se

representa con m ecuaciones lineales simultáneas y n variables no negativas. El lector
apreciará el sentido de la información de la figura 3.1 al avanzar en el resto de esta sección. Se
puede apreciar en forma visual por qué el espacio gráfico de soluciones tiene una cantidad
infinita de puntos de solución; pero, ¿cómo se puede deducir algo parecido a partir de la
representación algebraica del espacio de soluciones? La respuesta es que en la representación
algebraica, la cantidad m de ecuaciones siempre es menor o igual a la cantidad de variables n.

Para hacer una transición completa hacia la solución algebraica necesitamos indicar los puntos
esquina por sus nombres algebraicos. En forma específica, las n – m variables que se igualan a
cero se llaman variables no básicas. Si las m variables restantes tienen una solución única, se
llaman variables básicas y su solución (al resolver las m ecuaciones) se llama solución básica.

EL MÉTODO SÍMPLEX

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.

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 siempre se hallará solución.
¿Qué es una matriz identidad?
Una matriz puede definirse como una ordenación rectangular de elementos, (o listado finito de
elementos), los cuales pueden ser números reales o complejos, dispuestos en forma de filas y
de columnas.

La matriz idéntica o identidad es una matriz cuadrada (que posee el mismo número tanto de
columnas como de filas) de orden n que tiene todos los elementos diagonales iguales a uno (1)
y todos los demás componentes iguales a cero (0).

Las reglas para seleccionar las variables de entrada y de salida se llaman condiciones de
optimalidad y de factibilidad. Por comodidad se resumirán a continuación esas condiciones, y
los pasos del método símplex.

Condición de optimalidad. La variable de entrada en un problema de maximización

(minimización) es la variable no básica que tenga el coeficiente más negativo (positivo) en el
renglón de z. Los empates se rompen en forma arbitraria. Se llega al óptimo en la iteración en
la que todos los coeficientes de las variables no básicas en el renglón z son no negativos (no
positivos).

Condición de factibilidad. En los problemas de maximización y de minimización, la variable de

salida es la variable básica asociada con la mínima razón no negativa (con denominador
estrictamente positivo). Los empates se rompen en forma arbitraria.

SOLUCIÓN ARTIFICIAL DE INICIO

los programas lineales en los que todas las restricciones son (≤) con lados derechos no
negativos ofrecen una cómoda solución factible básica de inicio con todas las holguras. Los
modelos donde intervienen restricciones del tipo (=) o (≥) no poseen esta propiedad.

El procedimiento para iniciar programas lineales “de mal comportamiento” con restricciones
(=) y (≥) es permitir que variables artificiales desempeñen el trabajo de holguras en la primera
iteración, para después, en alguna iteración posterior, desecharlas en forma legítima. Aquí
presentaremos dos métodos muy relacionados: el método M y el método de dos fases.

Método M

El método M comienza con la programación lineal en forma de ecuación. Una ecuación i que
no tenga una holgura (o una variable que pueda hacer el papel de una holgura) se aumenta
con una variable artificial, Ri , para formar una solución de inicio parecida a la solución básica
con todas las holguras. Sin embargo, como las variables artificiales son ajenas al modelo de
programación lineal, se usa un mecanismo de retroalimentación en el que el proceso de
optimización trata en forma automática de hacer que esas variables tengan nivel cero. En otras
palabras, la solución final será como si las variables artificiales nunca hubieran existido en
primer lugar.
Método de dos fases

Debido al impacto potencial adverso del error de redondeo sobre la exactitud del método M,
donde se manipulan en forma simultánea coeficientes grandes y pequeños, el método de dos
fases reduce el problema eliminando por completo la constante M. Como su nombre indica, el
método resuelve la programación lineal en dos fases: la fase I trata de determinar una solución
básica factible de inicio y, si se encuentra, se invoca la fase II para resolver el problema
original.

Fase I. El problema se pone en forma de ecuación y se agregan a las restricciones las variables
artificiales necesarias (exactamente como en el método M) para asegurar una solución básica
de inicio. A continuación, se determina una solución básica de las ecuaciones resultantes, que
minimice la suma de las variables artificiales. Si el valor mínimo de la suma es positivo, el
problema de programación lineal no tiene solución factible, y termina el proceso (recuerde
que una variable artificial positiva significa que no se satisface una restricción original). En caso
contrario, se prosigue a la fase II.

Fase II. Se usa la solución factible de la fase I como solución básica factible de inicio para el
problema original.

CASOS ESPECIALES DE LA APLICACIÓN DEL MÉTODO SÍMPLEX

En esta sección se examinarán cuatro casos especiales que se presentan al aplicar el método
símplex.

1. Degeneración.
2. Óptimos alternativos.
3. Soluciones no acotadas.
4. Soluciones inexistentes (o no factibles).

El interés de estudiar esos casos especiales es doble: 1) presentar una explicación teórica de
esos casos, y 2) presentar una interpretación práctica de lo que pudieran significar esos
resultados especiales en un problema en la vida real.

Degeneración

Al aplicar la condición de factibilidad del método símplex, se puede romper un empate en la

razón mínima en forma arbitraria. Cuando se presenta un empate, al menos una variable
básica será cero en la siguiente iteración, y se dice que la nueva solución es degenerada.

No hay que alarmarse al manejar una solución degenerada, a excepción de una pequeña
incomodidad teórica de ciclado, que describiremos en breve. Desde el punto de vista práctico,
la condición indica que el modelo tiene al menos una restricción redundante. Para poder
presentar mejor perspectiva de los impactos prácticos y teóricos de la degeneración
presentaremos un ejemplo numérico, que resolveremos en forma algebraica y gráfica.
Óptimos alternativos

Cuando la función objetivo es paralela a una restricción obligatoria (es decir, una restricción
que se satisface como ecuación en la solución óptima), la función objetivo asumirá el mismo
valor óptimo, que se llama óptimos alternativos, en más de un punto de solución. El siguiente
ejemplo muestra que hay una cantidad infinita de esas soluciones. También demuestra un
significado práctico de encontrar óptimos alternativos.

Solución no acotada

En algunos modelos de programación lineal, los valores de las variables pueden aumentar en
forma indefinida sin violar alguna de las restricciones, y eso significa que el espacio de
soluciones es no acotado al menos en una dirección. El resultado es que el valor objetivo
puede aumentar (en caso de maximización) o disminuir (si se trata de minimización) en forma
indefinida. En ese caso, tanto el espacio de soluciones como el valor óptimo objetivo no están
acotados.