MÉTODO SIMPLEX

En la última discusión, utilizamos el método gráfico para resolver problemas de programación lineal, pero
el enfoque gráfico no funcionará para problemas que tienen más de dos variables. En la vida real
las situaciones, los problemas de programación lineal consisten literalmente en miles de variables y se resuelven
por computadoras. Podemos resolver estos problemas algebraicamente, pero eso no será muy eficiente. Así que
necesitamos un método que tenga un algoritmo sistemático y que pueda ser programado para una computadora. El
el método tiene que ser lo suficientemente eficiente para que no tengamos que evaluar la función objetivo en cada caso
punto de esquina. Tenemos justo tal método, y se llama el método simplex.
El método simplex para la programación lineal desarrollado por Dantzig (1914-2005) a mediados de
el siglo veinte (1963) es el primer método prácticamente y computacionalmente viable para resolver
sistemas de desigualdades lineales. Esto ha llevado a los desarrollos de la programación lineal (PL), un
rama de las matemáticas desarrollada en el siglo XX como una extensión del álgebra lineal a
resolver sistemas de desigualdades lineales.
El desarrollo de la programación lineal es un evento histórico en la historia de las matemáticas y sus aplicaciones
que trajo nuestra capacidad para resolver sistemas generales de restricciones lineales (incluidas ecuaciones lineales,
desigualdades) a un estado de finalización. Dado que las aplicaciones más realistas de la programación lineal
involucran numerosas variables y muchas restricciones, hay una necesidad de un método diferente al
método gráfico. Un método utilizado con frecuencia es el método simplex.
El 'algoritmo simplex' es un procedimiento iterativo para encontrar, de manera sistemática, el óptimo
solución a un problema de programación lineal. El funcionamiento del método símplex avanza mediante
preparando una serie de tablas llamadas tablas simplex, la última de las cuales indica la solución óptima
del problema dado. Gráficamente, encontramos el procedimiento como la búsqueda de diferentes puntos de esquina de
la región factible. La solución encontrada en cada iteración del método simplex representa tal
puntos de esquina. Sin embargo, no se examinan todos los puntos de esquina. La búsqueda elige solo un subconjunto de
estos puntos extremos, seleccionando uno nuevo si y solo si la función objetivo es al menos tan buena como
el punto de esquina actual. El método es bastante simple y el primer paso requiere la determinación
de solución básica factible. Luego, con la ayuda de un número limitado de pasos, la solución óptima
se puede determinar.
Supongamos que no hay una función objetivo que optimizar, y solo una solución factible de un sistema de
se deben encontrar restricciones lineales. Cuando hay restricciones de desigualdad en el sistema, la única
Un método práctico para encontrar una solución factible es resolver una formulación de programación lineal.
de ello como un problema de programación lineal de Fase I. Dantzig desarrolló esta formulación de Fase I como
parte del método simplex para PL que desarrolló a mediados del siglo XX.

Nota. El conjunto de puntos extremos de la región factible corresponde al conjunto de soluciones básicas factibles.
soluciones. En otras palabras, los puntos extremos son soluciones factibles básicas, y viceversa.

Nota. Las soluciones factibles son infinitas en número (porque hay un número infinito de puntos en
la región factible, OABC). Entonces, es bastante imposible buscar la solución óptima
entre todas las soluciones factibles. Pero afortunadamente, el número de soluciones básicas factibles son

1
finito en números (que corresponden a los puntos extremos O, A, B, C, respectivamente). Incluso
entonces, se requiere un gran trabajo para encontrar todos los BFS y seleccionar aquel que optimiza el
función objetivo.
El método simplex proporciona un algoritmo sistemático que consiste en pasar de una BFS
(un vértice) a otro de una manera prescrita de modo que el valor de la función objetivo sea
mejorado. Este procedimiento de saltar de vértice a vértice se repite. Si la función objetivo
se mejora en cada salto, entonces no se puede repetir ninguna base y no hay necesidad de volver al vértice
ya cubierto. Dado que el número de vértices es finito, el proceso debe conducir al óptimo
vértice en un número finito de pasos.

C
B

O A

RESTRICCIONES VINCULANTES Y NO VINCULANTES

Una vez que se obtiene la solución óptima a un PLP, podemos clasificar las restricciones como
vinculante o no vinculante. Una restricción se denomina vinculante si el lado izquierdo (L.H.S) y el lado derecho (R.H.S) de ella son iguales

cuando se sustituyen los valores óptimos de las variables de decisión en la restricción. Por otro lado
mano, si la sustitución de las variables de decisión no conduce a la igualdad entre la izquierda y
los lados derechos de la restricción, se dice que no son vinculantes.
Por ejemplo, considera el LPP como
Max Z = 40x + 35y
Sujeto a 2x + 3y 60≤
≤
4x + 3y 96
Y, x, y 0 ≥
Los valores óptimos de las variables de decisión son: x = 18 e y = 8. Sustituyendo estos valores en el
dos restricciones que obtenemos
2x + 3y o 2 x 18 + 3 x 8 = 60 = R.H.S, y
4x + 3y o 4 x 18 + 3 x 8 = 96 = R.H.S.
Por lo tanto, ambas restricciones son de naturaleza vinculante.

Por otro lado, si consideramos el siguiente ejemplo como

Min Z = 40x + 24y

2
 ≥
Sujeto a 20x + 50y 4800
≥
80x + 50y 7200
Y, x, y 0 ≥
Los valores óptimos de las variables de decisión son: x = 0 e y = 144. Sustituyendo estos valores en el
dos restricciones que obtenemos
20x + 50y o 20 x 0 + 50 x 144 = 7200 4800≠ (R.H.S), y
80x + 50y o 80 x 0 + 50 x 144 = 7200 = R.H.S.
En consecuencia, la primera de las restricciones no es vinculante y la segunda es una vinculante.

RESTRICCIÓN(ES) REDUNDANTE(S)
Como hemos observado, la representación de cada una de las restricciones en el gráfico sirve para determinar el
región factible de un problema dado. Si y cuando una restricción, al ser graficada, no forma parte de
el límite que marca la región factible del problema se dice que es redundante. La inclusión
la exclusión de una restricción redundante, evidentemente, no afecta la solución óptima del
problema. En otras palabras, una restricción, que no afecta la región factible, se llama un
restricción redundante. Tal restricción no es necesaria para la solución del problema. Puede
por lo tanto, se omitirá al formular el problema. Esto ahorrará tiempo de computación.

ALGUNAS DEFINICIONES IMPORTANTES

A continuación se definen algunos términos importantes para el LPP estándar que son necesarios para entender.
más discusión.
1. Solución Básica (SB): Para un sistema de m ecuaciones lineales simultáneas en n incógnitas (n
m), una solución obtenida al igualar cualquier n-m variables a cero y resolver para
variables restantes, siempre que el determinante de los coeficientes de estas variables
se llama solución básica. Tales variables (por supuesto, algunas de ellas pueden ser
cero) se llaman variables básicas y las restantes n-m variables de valor cero cuyas valores
no aparecieron en la solución se llaman variables no básicas.
El número de soluciones básicas así obtenidas será como máximon C.m= n! / ((n-m)! m!)
cuál es el número de combinaciones de nthings tomadas de m a la vez.
[Link]: El conjunto de variables básicas que no están restringidas a cero en la solución básica y
están listados en la columna de solución.
[Link]ón Factible Básica (BFS): Una solución factible básica es una solución básica que también
satisface las restricciones de no negatividad, es decir, todas las variables básicas son no negativas.
Las soluciones básicas factibles son de dos tipos:
(a)Búsqueda en anchura no degenerada: Una solución básica factible no degenerada es la solución básica factible
solución que tiene exactamente mpositivo xyo(i= 1, 2, … , m). En otras palabras, todos los básicos
las variables son positivas, y las restantes serán todas cero.
(b)BFS degenerado: Una solución básica factible se llama degenerada, si uno o más básicos
las variables tienen un valor cero.

3
 La importancia del BFS se deriva del hecho de que para cualquier LPP, hay un extremo único.
punto de la región factible correspondiente a cada BFS y también hay al menos un BFS
correspondiente a cada punto extremo de la región factible.
[Link]ón Básica Factible Óptima: Se dice que una solución básica factible es óptima, si
también optimiza (maximiza o minimiza) la función objetivo.
[Link]ón Sin Límite: Si el valor de la función objetivo z puede ser aumentado o
disminuyó indefinidamente, tales soluciones se llaman soluciones no acotadas. Si la factible
la región (área sombreada) es infinita, es decir, no tiene un límite confinado. Entonces, esto puede ser
es posible que la LPP no tenga solución finita, y por lo tanto la solución sea ilimitada.
[Link]ón: es una secuencia de pasos dados para pasar de una solución básica factible a
otra solución factible básica.
[Link] una fila en la tabla simplex que contiene los coeficientes de las variables
en la función objetivo.
[Link] una fila en la tabla simplex cuyos elementos representan el aumento
(disminución) del valor de la función objetivo si se trae una unidad de la j-ésima variable
en la solución.
[Link]- CjEs una fila cuyos elementos representan la contribución neta por unidad del jésimo
variable en la función objetivo, si la variable se introduce en la nueva solución básica.
[Link] clave: Es la columna con el Z más negativo (positivo)jCjy esto indica
qué variable entrará en la siguiente solución en un caso de maximización (minimización).
[Link] clave: Es la fila con el valor positivo más pequeño de la relación de reemplazo del
filas de restricción. La tasa de reemplazo se obtiene dividiendo elementos en la solución
columna por los elementos correspondientes en la columna clave. La fila clave indica el
variable que dejará la base para hacer espacio para la nueva variable de entrada.
[Link] clave (pivote): Es el elemento en la intersección de la fila clave y la columna clave.
Nota. A menos que se indique lo contrario, solución significa una solución factible. Sin embargo, una óptima
la solución a un problema de programación lineal implica que z tiene un máximo finito o finito
valor mínimo.
Además de estos términos en un tableau simplex, tenemos los siguientes términos que son necesarios
hacer que un problema de programación lineal se ajuste para ser resuelto por el método simplex.
≤
. Variable de holgura: Una variable utilizada para convertir una restricción de menor o igual que ( ) en
restricción de igualdad. Se añade al lado izquierdo de la restricción. En economía
En terminología, la variable de holgura representa la capacidad no utilizada.
≥ o igual que ( )
. Variable de excedente: Una variable utilizada para convertir una restricción de mayor
en una restricción de igualdad. Se resta del lado izquierdo de la restricción.
. Variable artificial: Es una variable añadida para igualar a (=) y mayor o igual que ( ≥
)
restricción de tipo. Estas variables se utilizan para obtener una solución inicial factible en simplex
método. Estas variables se reducen a cero en la optimalidad. Las variables artificiales son temporales
variables de retención que se utilizan para fines de cálculo y se eliminan más tarde.
Las variables anteriores se utilizan para convertir las desigualdades en ecuaciones de igualdad.

4
FORMA ESTÁNDAR DE UN PLP
El uso del método simplex para resolver un problema de programación lineal requiere que el problema sea
convertido en su forma estándar. La forma estándar del problema de LP debe tener lo siguiente
características
[Link] las restricciones deben convertirse en ecuaciones, excepto la no negatividad.
restricciones que permanecen como desigualdades (≥ 0). Las restricciones del tipo '≤' pueden convertirse en
tipo de igualdad, agregando variables que son conocidas como variables de holgura. El tipo ‘≥’
Las restricciones pueden convertirse en igualdades al restar variables que se llaman excedentes.
variables.
Considera las ecuaciones,
ejemplo: a11x1+ a12x2≤ b1
a21x1+ a22x2≥ b 2
Al convertir estas ecuaciones en igualdad, obtenemos:
a11x1+ a12x2+ xs1= b1
a21x1+ a22x2x−s2= b2
Aquí xs2sería variable de holgura y xs2sería variable sobrante.
En cada ecuación se añadiría solo una variable de holgura o solo un excedente.
se restaría la variable.
Asignamos un costo cero a cada una de las variables de holgura y excedente.
[Link] elemento del lado derecho de cada restricción debe hacerse no negativo (si no lo es).
el lado derecho siempre se puede hacer positivo al multiplicar ambos lados de la ecuación resultante
por−1 siempre que sea necesario.
Por ejemplo, considere la restricción como 3x – 4y ≥ − 4 que se puede expresar en la forma de
ecuación 3x – 4y – w = 4 al− introducir la variable de excedente w ≥ 0. Nuevamente, multiplicando
ambos lados por− 1, obtenemos − 3x + 4y + w = 4, que es la ecuación de restricción en estándar
forma.
[Link] las variables deben tener valores no negativos. A veces, un problema puede tener un
variable que es 'sin restricciones en el signo' o 'libre', de modo que puede asumir valores negativos como
bien como no negativo. Esta situación se maneja tratando tal variable como la
diferencia de dos variables que son ambas no negativas, porque tal diferencia puede
ser positivo, negativo o cero.
Considera el siguiente ejemplo:

Maximizar Z = 5x + 7y +−2w
Sujeto a 2x + 5y + 3w ≤ 80
5x + 2y – 2w ≤ 30
y + 6w ≤ 42
5
 Y, x, y ≥ 0, w no tiene restricciones de signo
Dado que w no está restringido en signo, podemos representarlo como la diferencia de dos no negativos.
variables, decirw ' y w' . Sustituyendo w= w w
–'anterior y simplificando, nosotros
en' lo
obtener
Maximizar Z = 5x + 7y - 2w ' + 2 w'
Sujeto a 2x + 5y + 3 w ' – 3 ≤ 80
5x + 2y - 2 +w2' w' ≤30
y + 6 w - 6 w' ≤ 42
Y, x, y, , w ' w '' ≥ 0
Después de obtener la solución, sustituiremos la diferencia de los valores de w' y
w' como el valor de w.

CONDICIONES PARA APLICACIONES DEL MÉTODO SIMPLEX

[Link] lado derecho de cada una de las restricciones byodebe ser no negativo. (Consultar el Punto 2 arriba)
2. Cada una de las variables de decisión del problema debe ser no negativa. (Consultar punto 3)
arriba)

PROCEDIMIENTO PARA RESOLVER UN PROBLEMA A TRAVÉS DEL MÉTODO SIMPLEX

El método para resolver un problema a través del método simplex implica los siguientes pasos:-
Paso 1: Formulación de LPP.
Paso 2: Convertir restricciones en forma de igualdad utilizando las reglas dadas en la forma estándar de un
LPP.
Paso 3: Construir la tabla simplex inicial.
Paso 4. Para establecer la Solución Básica Inicial Factible. El cuarto paso es encontrar la solución básica factible.
solución. Para esto podemos tomar las m variables de holgura o variables artificiales s1, s2, …, smo un1, un2,
... ,amo una mezcla de ellos (algunas variables de holgura y algunas variables artificiales) como las variables básicas. Nosotros

pueden determinar sus valores directamente, porque las variables restantes x1, x2, …, xnno son básicos
y por lo tanto cada uno tiene el valor cero. Así s1=b1, s2=b2, …, sm=bmo (a1=b1, a2=b2, …., am=bm)
o (s1= b1, a1= b2, …, am= bmo cualquier otra combinación de este tipo).
Cada uno de los márgenes (s1, s2, …, sm)o superávit (sl1, sl2, …, slm) la variable tendrá un coeficiente cero en
la función objetivo, mientras que cada uno de los artificiales (a1, un2, …, am) las variables tendrán un
coeficiente +M en caso de maximización o -M en caso de minimización en la función objetivo,
M siendo un número muy grande. Esto es solo para mantenerlos fuera de la solución final.
El método simplex luego procede a resolver el problema anterior diseñando y rediseñando
soluciones básicas factibles sucesivamente mejores hasta que se obtiene una solución óptima.
Paso 5. Para establecer la Tabla Simplex Inicial. Una vez que se ha establecido la tabla simplex, el siguiente paso es
localiza la matriz identidad y las variables involucradas en ella. La identidad contiene todos ceros excepto
los elementos diagonales como 1. La identidad debe tener esta forma cuadrada con todos ceros y una diagonal
de (más) unos. El tamaño de esta matriz cuadrada se determinaría por el número de restricciones
en el sistema. Localizar la identidad es de suma importancia ya que la solución se identifica en
6
la referencia a esto. Las variables correspondientes a la matriz identidad se llaman variables básicas y
los restantes se llaman variables no básicas.
Por eficiencia computacional y simplicidad, el algoritmo simplex se realiza generalmente en un
tabla llamada tableau asimplex. Las variables básicas iniciales son las variables de holgura o artificiales
asociado a cada restricción (todas las variables de decisión son cero). El tableau simplex inicial es
mostrado en Tableau 1.
La interpretación de los datos en la Tabla 1 se da después de la tabla. Otras tablas simplex tendrán
interpretaciones similares.
Tabla Simplex 1
Tabla 1 c1c2… cn 0 0 … 0Mo 0oMo…0oM
−M −M o −M
xB cB x1x2... xn sl1sl3… slja1 s2o un2 … smo unmbyo
a1 0oM a11a12… a1n -1 0 … 01 0 ... 0 b1
o M−
s2o 0 o M aveintiunoa22… a2n 0 0 … 00 1 ... 0 b2
a2 o M−
a3 0oM a31a32… a3n0-1 … 0 0 0 … 0 b
o M−
M M M M M M M M M M M M M M M
aj 0oM aj1aj2… ajn… -1 0 0 0 0 … 0
o −M
M M M M M M M M M M M M M M M
sm 0oM am1am2... amn 0 0 … 00 0 ... 1 bm
o o −M
am
ZjC−j -c1-c2… -cn 0 0 … 0 −M 0oM − … 0o −
oM oM MoM

a. En la primera fila, escribimos los coeficientes de las variables en la función objetivo. Estos
los valores permanecerán iguales en la tabla siguiente.
[Link] segunda fila muestra los principales encabezados de columna. Estos encabezados permanecen iguales en
la tabla subsiguiente y aplicarla a los valores enumerados en las primeras filas.
[Link] la primera columna etiquetada como “xB(también llamada columna de mezcla de productos) se enumeran los básicos
variables. Así, en la tabla simplex inicial, estas variables son las variables de holgura o
variables artificiales.
[Link] la segunda columna etiquetada como "cB”, escribimos los coeficientes (en la función objetivo)
de las variables básicas incluidas en la tabla específica. Así, los coeficientes de holgura o
las variables artificiales que se incluyen en la primera tabla están escritas en el cBcolumna.
[Link] Matriz del Cuerpo (bajo variables no básicas) en la tabla simplex inicial consiste en el
coeficientes de las variables de decisión en el conjunto de restricciones.

7
 f. La matriz identidad (bajo variables de holgura o artificiales) en el tableau simplex inicial
representa los coeficientes de las variables de holgura o artificiales en el conjunto de restricciones. Cada
La tabla simplex contiene una matriz identidad bajo las variables básicas.
[Link] la columna etiquetada como "byo(también llamada columna de Cantidad), escribimos los valores de solución de
las variables básicas. Dado que los valores de nuestra solución básica factible inicial están representados
por los lados derechos de las restricciones, estos valores se enumeran en el simplex inicial
mesa.
[Link] obtener una entrada para la Zjmultiplicamos las entradas en las respectivas columnas por el
entradas correspondientes de Cjcolumna y agregar los productos. El Zjlas entradas serán todas iguales
a cero en la tabla simplex inicial. El otro Zjlas entradas representan la disminución en el
función objetivo que resultaría si una de las variables no se incluye en la solución
fueron incorporados a la solución.
[Link] última fila etiquetada como “Zj– Cj, llamada la fila de índice o fila de evaluación neta, y se utiliza para
determinar si la solución actual es óptima o no. El cálculo de Zj– Cjfila
simplemente implica restar cada Cjvalor del correspondiente Zjvalor para eso
columna. Observamos que Zj– Cjlos valores son significativos solo para las variables no básicas.
Esto se debe a que para una variable básica Zj(valor de la jthvariable de holgura o variable artificial es decir 1) x
Cj= Cjpara que Zj– Cj= Cj– Cj= 0.
Los números en la Zj– Cjla fila representa la contribución neta a la función objetivo que
resultados al introducir una unidad de cada una de las respectivas variables de columna. Un valor positivo indica
que se puede hacer una mayor contribución al llevar la variable de esa columna a la solución.
Un valor negativo indica la cantidad por la cual disminuiría la contribución si una unidad de la
se trajo una variable para esa columna en la solución.
Paso 6. Prueba la solución para optimalidad. Examina las entradas Zj– Cjfila. En caso de maximización
problema, si todas las entradas en Zj– Cjlas filas son positivas o cero, la solución óptima ha sido
obtenido, de lo contrario la presencia de cualquier entrada negativa indica que la solución puede ser aún
mejorado.
Y, en caso de problema de minimización, si todas las entradas en Zj– CjLa fila es negativa o cero, el
se ha obtenido una solución óptima, de lo contrario, la presencia de cualquier entrada positiva indica que
la solución se puede mejorar aún más.
Paso 7. Revisión de la tabla simplex actual. En cada iteración, el método simplex se mueve de
el BFS actual por un mejor BFS. Esto implica reemplazar una variable básica actual (llamada la
variable de salida) por una nueva variable no básica (llamada variable de entrada).
Determinando la variable de entrada. En caso de un problema de maximización, la columna con la mayor
entrada negativa en el Zj– Cjla fila se llama la columna clave (o columna pivote) (indicado por Este
↑
localiza la variable que se va a introducir en la base. Así, la variable no básica que se
reemplazar una variable básica es la que se encuentra en la columna clave.
Y, en caso de un problema de minimización, la columna con la entrada más positiva en el Zj– Cjfila
se llama la columna clave (o pivote) (indicada por ). ↑Esto localiza la variable que debe ser introducida

8
en la base. Así, la variable no básica que reemplazará a una variable básica es la que se encuentra en
la columna clave.
Determinando la variable que sale. La decisión de qué variable básica reemplazar se toma por
enfocándose en la columna clave y la columna de solución. Divida cada entrada de la columna de solución
por la entrada positiva correspondiente en la columna clave. Estos cocientes se escriben en el último
columna etiquetada "Ratio" de la tabla simplex a ser reemplazada. La fila que corresponde a la
el cociente no negativo más pequeño se llama la fila clave (o pivote) (indicado por ←
). Los que se van
la variable es la variable correspondiente en esta fila. El número que se encuentra en la intersección de la
La columna clave y la fila clave de una tabla dada se llama el número clave (o pivote). Colocamos un
dibuja un círculo alrededor de este número.

Derivación de la nueva tabla. Después de identificar la variable de entrada y la variable de salida, solo queda
para encontrar el nuevo BFS construyendo una nueva tabla simplex a partir de la actual. Esto es
logrado mediante el uso de operaciones elementales de fila de modo que el número clave se reduzca a 1 y
otras entradas en la columna de clave se transforman en cero. Para cambiar la fila clave de modo que la clave
el número es 1. Podemos usar la siguiente fórmula:
Nueva fila clave = fila clave antigua / número clave (elemento pivote)
Para cambiar las filas no clave, podemos usar la fórmula:
Filas no clave nuevas = fila no clave antigua - (entrada de columna clave) x fila clave nueva, donde columna clave
la entrada es la entrada en esta fila es decir, en la columna clave.
Paso 8. Prueba de optimalidad. Nuevamente, aplicamos la prueba de optimalidad para determinar si el nuevo
la solución es óptima. En el caso de un problema de maximización, si no hay Z negativoj– Cjentradas, nosotros
tiene una solución óptima y ha terminado el problema. De lo contrario, vuelva al paso 7.
De manera similar, en el caso de un problema de minimización, si no hay Z positivosj– Cjentradas, tenemos un
solución óptima y haber terminado el problema. De lo contrario, regrese al paso 7.

Observación
El vector que se elimina de la base en una iteración del método simplex no puede
vuelve a entrar en la base en la siguiente iteración.
•La existencia de una variable de holgura en la tabla final del simplex indica que el recurso ha
no se ha utilizado completamente. La no existencia de variables de holgura indica la plena utilización de
los recursos existentes. Así que, si la empresa planea ampliar los recursos, puede buscar
solo aquellos recursos que están completamente utilizados. Para evaluar el valor de recursos adicionales,
podemos considerar qué diferencia haría si pudiéramos proporcionar una unidad extra de cada uno
de los recursos totalmente utilizados. El aumento en las ganancias como resultado de la unidad adicional de
el recurso se considera el valor marginal del recurso y se refiere como la sombra
precio de ese recurso. El precio sombra para cada recurso se muestra en la Zj– Cjfila de
la tabla simplex final bajo la variable de holgura correspondiente.
•Si no hay x1, x2variables en la tabla de iteración final, los valores de x1y x2son cero.

P1. Resuelve el siguiente problema utilizando el método simplex.

9
 Maximizar Z = 40x + 35y (Beneficio)
Sujeto a 2x + 3y ≤ 60 (Restricción de Materia Prima)
4x + 3y ≤ 96 (Restricción de Horas de Trabajo)
Y x, y ≥ 0 (Resp. x = 18, y = 8 y Z = 1000)

LA TÉCNICA M DE CHARNES PARA PROBLEMAS CON SOBRANTE Y

VARIABLES ARTIFICIALES
Hasta ahora, hemos visto las restricciones de programación lineal de tipo menor que. Nos encontramos con
problemas con el tipo ‘mayor que’ y ‘igual a’ también. Cada uno de estos tipos debe ser convertido como
Ecuaciones. En el caso de tipo 'mayor que', las restricciones se reescriben con un superávit negativo.
variable y añadiendo una variable artificial. Las variables artificiales se utilizan simplemente para encontrar el
soluciones básicas iniciales y son luego eliminadas. En caso de una restricción de 'igual a', simplemente añade
la variable artificial a la restricción.
Los coeficientes de las variables artificiales a1, a2,..... están representados por un valor muy alto -M o M.
y de ahí que el método se conozca como el Método BIG-M.
Se añade una variable artificial a cualquier restricción de igualdad para introducir una columna para el
matriz básica estándar. La variable artificial se introduce solo cuando hay una necesidad. Si el
la columna correspondiente de la base estándar ya está disponible por cualquier variable original, necesitamos
no introducir la variable artificial correspondiente. El valor de la variable artificial es cero, si
el LPP dado es consistente. Por lo tanto, si el LPP es consistente, la variable artificial debe ser o bien
ser no básico o aparecer en un nivel cero en la tabla óptima final. Como tiene que convertirse en no básico en
la tabla óptima final del problema resuelto por el método simplex, una vez que se ha eliminado una variable artificial
deja la base, no la consideramos para las iteraciones restantes para deshacernos de ellas, lo cual
eventualmente sucederá, si el problema es factible.
En el método del gran M de Charnes, asignamos un costo de '-M' a la variable artificial en un problema de maximización.
y el costo ‘+M’ en un problema de minimización, donde M es muy grande.
El gran costo M impide que la variable artificial vuelva a entrar en la base, una vez que ha salido. Porque si lo hace
entra habrá un aumento en el valor de la función objetivo en un problema de minimización. Pero
el método simplex se encarga de reducir el valor de la función objetivo en cada iteración en un
problema de minimización. Mientras que en un problema de maximización, ‘-M’ es el costo correspondiente
variable artificial, si entra en cualquier etapa después de haber sido eliminada, habrá una fuerte caída en el
valor de la función objetivo, contrario al procedimiento del método simplex, ya que en cada iteración
aumenta el valor de la función objetivo.
Si todas las variables artificiales son iguales a cero en la solución óptima, hemos encontrado la óptima
solución al problema original. En cualquier PPL, si la variable artificial permanece en el nivel positivo
en la tabla óptima final, entonces el problema se vuelve inconsistente y declaramos el problema a
ser inviable.

Pregunta1¿

10
La entrada más negativa (positiva) en la fila inferior representa el mayor (menor)
coeficiente en la función objetivo - el coeficiente cuya entrada aumentará (disminuirá) el
valor de la función objetivo muy rápidamente.

Pregunta2¿Por qué identificamos el elemento pivote?

Como mencionamos anteriormente, el método simplex comienza con un punto extremo y luego
se mueve al siguiente punto de esquina siempre mejorando el valor de la función objetivo. El valor
la función objetivo se mejora al cambiar el número de unidades de las variables. Podemos
agregar el número de unidades de una variable, mientras se desechan las unidades de otra. Pivotando
nos permite hacer exactamente eso.

Problema con restricciones mixtas

Q2. (i) Maximizar Z = 2x1+ 4x2 (ii) Maximizar Z = 2x1+ x2+3x3
Sujeto a 2x1+ x2≤ 18 Sujeto a x1+ x2+ 2x3≤ 5
3x1+2 x2≥ 30 2x1+ 3x2+ 4x3= 12
x1+2 x2= 26 Y, x1, x2, x3≥ 0
Y, x1, x2≥ 0
(iii) Minimizar Z = 5x + 8y (iv) Maximizar Z = 8x1- 4x2
Sujeto a x + y = 5 Sujeto a 4x1+ 5x220 ≤
x≤4 –x1+ 3x2-23 ≥
y≥2 Y, x10, x2≥sin restricciones en la firma.
Y x, y ≥ 0
Resp. (i) La solución óptima es (2, 12) y el valor de la función objetivo es 52.
(ii) La solución óptima es (3, 2, 0) y el valor de la función objetivo es 8.
(iii) La solución óptima es (3, 2) y el valor de la función objetivo es 31.
(iv) La solución óptima es (175/17, -72/17) y el valor de la función objetivo es 1688/17.

EMPATE POR LA VARIABLE DE ENTRADA

En una tabla simplex, suponga que dos o más variables no básicas están empatadas por tener la más alta.
negativo (positivo) Zj- Cjentrada. En tal caso, elegimos cualquiera de estos para encontrar la entrada
variable. La solución óptima se alcanzará eventualmente, independientemente de la variable atada elegida.

MÚLTIPLES SOLUCIONES ÓPTIMAS

En cada tabla simplex, las variables básicas tienen todo Zj– Cj≥ 0, pero no los que no son básicos. Cuando
se indica que una solución es óptima y el Zj– Cjel valor para ninguno de las variables no básicas es
cero, la solución es única en el sentido de que no existe otra solución al problema dado, que
daría el valor idéntico de la función objetivo. Cuando una variable no básica en un
la solución óptima tiene un valor cero para Zj– Cjentonces la solución no es única y hay múltiples óptimas
existen soluciones. Las otras soluciones óptimas se obtienen generalmente realizando adiciones

11
iteraciones del método simplex, eligiendo cada vez una variable no básica con un Z igual a ceroj– Cj
entrada como la variable de entrada.
Q3. (i) Maximizar Z = 8x1+ 16x2 (ii) Maximizar Z = x1+ 2x2+3x3
Sujeto a x1+ x2≤ 200 Sujeto a x1+ 2x2+ 3x3≤ 10
x2≤ 125 x1+ x2≤ 5
3x1+6 x2≤ 900 x1≤ 1
y, x1, x2≥ 0 y, x1, x2, x3≥ 0
(i) Las soluciones básicas óptimas son (50, 125) y (100, 100) que tienen un objetivo óptimo.
valor de la función 2400.
10 1
(ii) Las soluciones básicas óptimas son (0, 0, ), (1, 0, 3), (0, 5, 0) y (1, 4, ) teniendo
3 3
valor óptimo de la función objetivo 10.

INVIABILIDAD
Cuando en la solución final, una variable artificial está en la base con un valor positivo, entonces no hay
solución viable al problema.
Q4. (i) Maximize Z = 20x1+ 30x2 (ii) Maximizar Z = x1+ 4x2+3x3
Sujeto a 2x1+ 3x2≤ 40 Sujeto a 2x1– x2+ 5x3= 40
4x1– x2≤ 20 x1+ 2x2– 3x3>= 22
x1≥ 30 3x1+ x2+ 2xtres= 30
y, x1, x2≥ 0 y, x1, x2, x3≥ 0
Respuesta. (i) y (ii) el problema es inviable.

SOLUCIÓN SIN LÍMITES

Se dice que un PLP tiene una solución no acotada si el valor de su función objetivo puede ser aumentado (en
caso es un problema de maximización) o disminuyó (si es un problema de minimización) sin límite.
Si en una cierta situación no hay tasas de reemplazo no negativas o cuando todos los valores de
las columnas clave son negativas es decir, todas ellas son negativas o son iguales a∞ (por la razón del)
denominador igual a cero), entonces el algoritmo termina. Esto indica que el problema bajo
la consideración tiene solución ilimitada.
Si nos encontramos con la no acotación al resolver problemas reales, entonces el problema no está correctamente
formulado. Dado que ninguna situación real permite que ninguna gestión tenga una producción infinita de bienes
y beneficios infinitos, resultados de solución ilimitada si en un problema de maximización todas las restricciones son
de tipo mayor o igual que. En tal situación no hay un límite superior en la región factible.
De manera similar, una solución no acotada ocurre en un problema de minimización si todas las restricciones son de menor
menor o igual que tipo.
Q5. (i) Maximizar Z = 10x1+ 20x2 (ii) Maximizar Z = 5x1+ 2x2+2x3
Sujeto a 2x1+ 4x2≥ 16 Sujeto a 3x1-2x2-2x3= -8
x1+ 5x2≥ 15 3x1- 4x2– x3=-7
y, x1, x2≥ 0 y, x1, x2, x3≥ 0
12
Respuesta. (i) y (ii) la solución es ilimitada.

INVIABILIDAD VS SIN LÍMITES

Tanto la inviabilidad como la ilimitación tienen una similitud en que no hay una solución óptima en
cualquiera de los casos. Pero hay una diferencia notable entre los dos: mientras que en la inviabilidad no hay un
solución factible única, en la no acotación hay infinitas soluciones factibles pero ninguna de ellas
puede ser denominado como el óptimo.

EMPATE POR LA VARIABLE SALIENTE - DEGENERACIÓN

La degeneración en la PPL ocurre cuando una o más de las variables básicas asumen un valor de cero. A medida que
como ya se mencionó, para un problema de n variables y m restricciones, habría m básicas y n-m no básicas
variables, y las variables básicas asumirían valores positivos. Sin embargo, en caso de que una básica
la variable asume un valor igual a cero, entonces la variable y la solución se etiquetan como degeneradas.
Así, en condiciones de degeneración, la solución contendría un número menor de elementos no cero.
variables que el número de restricciones, m.
Siempre que haya un empate en las tasas de reemplazo para determinar la variable de salida, la siguiente tabla
daría una solución degenerada. Además, podemos elegir cualquiera de estos cocientes para encontrar
variable de salida.
Q6. Maximizar Z = 28x1+ 30x2 (Beneficio)
Sujeto a 6x1+ 3x2≤ 18 (Restricción de Materia Prima)
3x1+ x2≤ 8 (Restricción de Horas de Trabajo)
4x1+5 x2≤ 30
y, x1, x2≥ 0
La solución óptima es (0, 6) y el valor de la función objetivo es 180.

Nota
•Sabemos que las tablas simplex sucesivas representan mejoras en el valor del
la función objetivo – se observan aumentos para la maximización y disminuciones para el
mínimos problemas. Sin embargo, cuando la variable de salida resulta ser una degenerada
variable, el valor de la función objetivo en la siguiente tabla no cambia. El valor de Z para un
La tabla ‘no óptima’ no es diferente del valor Z obtenido de la siguiente tabla.
•Si no hay mejora en la solución en términos de la función objetivo, entonces ¿por qué?
¿No deberíamos detenernos en la iteración donde aparece una solución degenerada? La respuesta a
esto es que uno no puede estar seguro de que la primera aparición de una solución degenerada ocurrirá
coincide con la solución óptima. En otras palabras, el problema puede estar temporalmente
degenerado. Podemos considerar la siguiente pregunta donde una solución degenerada es
encontrado pero más tarde la degeneración desaparece.
Q7. Maximizar Z = 5x + 2y
Sujeto a 4x + 2y ≤ 16
3x + y ≤ 9
13
 3x - y ≤ 9
y, x, y ≥ 0
La solución óptima es (1, 6) y el valor de la función objetivo es 17.

14