Tema 3

Algoritmo Simplex. Dualidad.

Análisis de Sensibilidad.
Programación Entera.

En los temas anteriores se ha visto la formulación de modelos de programación lineal y su

resolución gráfica cuando tenemos dos variables de decisión. En este tema vamos a desa-
rrollar el método Simplex que se utiliza para resolver cualquier problema de programación
lineal. También se verá unos de los conceptos más importantes de la programación lineal:
la dualidad. Finalmente se estudiará el efecto de cambios en la estructura del modelo
sobre la solución óptima, es por tanto de gran importancia y recibe el nombre de análisis
de sensibilidad.

3.1. Fundamentos del Simplex. Método del Simplex

en forma tabular

El problema fundamental de la programación lineal consiste en determinar una solución

para un sistema de ecuaciones lineales simultáneas que optimice una determinada función
objetivo. Tales sistemas se resuelven por el método de Gauss. Para tal resolución es
necesario manejar algunos conceptos.
Podemos establecer que la forma general de un problema de programación general es
la siguiente:
Determinar el valor de un conjunto de variables, x = (x1 , x2 , . . . , xn ) ∈ Rn que optimice

37
3.1. Fundamentos del Simplex. Método del Simplex en forma tabular

(maximice o minimice) una función objetivo sujeta a unas restricciones, esto es,

Opt z = c1 x1 + c2 x2 + · · · cn xn
s.a a11 x1 + a12 x2 + · · · + a1n xn (≤, =, ≥)b1
a21 x1 + a22 x2 + · · · + a2n xn (≤, =, ≥)b2
······························
am1 x1 + am2 x2 + · · · + amn xn (≤, =, ≥)bm

o matricialmente el problema se expresa como

Opt z = c′ x
s.a. Ax(≤, =, ≥)b
x≥0

siendo
 
a11 a12 ··· a1n
 a21 a22 ··· a2n 
A=
 ···
 , x = (x1 .x2 , . . . , xn )′ , b = (b1 , b2 , . . . , bm )′ , c = (c1 , c2 , . . . , cn )′
··· ··· ··· 
am1 am2 ··· amn

Hay dos formas especialmente importantes de presentar un problema lineal:

Forma estándar de un problema lineal. Se llama ası́ a la presentación de un

problema en la que:

1. El objetivo es de la forma maximización o minimización.

2. Todas las restricciones son de igualdad.
3. Todas las variables son no negativas.
4. Las constantes a la derecha de las restricciones son no negativas.

Por lo tanto, un problema de maximizar en forma estándar tiene la estructura

siguiente:

Opt z = c′ x
s.a. Ax = b
x≥0

donde cn×1 , xn×1 , bm×1 , Am×n con n > m. Se denota Aj la j-ésima columna de A.

38 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

Forma canónica de un problema lineal. Se llama ası́ a la presentación de un

problema en la que:

1. El objetivo es de la forma maximización.

2. Todas las restricciones son del tipo ≤.
3. Todas las variables son no negativas.

Por lo tanto, un problema de maximizar en forma canónica tiene la estructura

siguiente:

M ax z = c′ x
s.a. Ax ≤ b
x≥0

donde cn×1 , xn×1 , bm×1 , Am×n con n > m.

El método simplex se aplica a programas lineales en forma estándar. La mayorı́a de

los problemas no son inicialmente modelizados en esta forma, sino que tienen muchas
restricciones de desigualdad. Por ello es necesario dar la forma canónica de un problema
lineal. Para ello se utilizarán las transformaciones vistas en el tema 1.
El método simplex es un algoritmo, es decir, un procedimiento sistemático que se re-
pite una y otra vez hasta obtener un resultado deseado. Cada vez que se lleva a cabo
el procedimiento sistemático se realiza una iteración. En el procedimiento gráfico se lo-
calizaban los puntos extremos de la región factible, coincidiendo la solución óptima en
uno de esto puntos. Nuestro objetivo ahora es determinar algebraicamente estos puntos
extremos.
El primer paso será pasar el problema a forma estándar, de esta forma, el conjunto de
restricciones se convierte en un sistema de ecuaciones simultáneas. En estas condiciones,
existe un equivalente a los puntos extremos que utilizábamos en el procedimiento gráfico,
las soluciones básicas. De forma equivalente que en el método gráfico, la solución óptima
del problema será una de estas soluciones básicas. Pasamos a la definición del concepto
de solución básica.
La forma estándar de un problema de programación lineal incluye m ecuaciones lineales
simultáneas con n incógnitas o variables (m < n). Se dividen las n variables en dos series:

1. n − m variables a las cuales les asignamos el valor 0.

2. las restantes m variables, cuyos valores se determinan resolviendo las ecuaciones

resultantes.

Si las m ecuaciones producen una solución única, entonces las m variables asociadas
se llaman variables básicas y las n − m variables restantes se conocen como variables

Eva Ma Ramos Ábalos 39

3.1. Fundamentos del Simplex. Método del Simplex en forma tabular

no básicas. Las variables básicas son el equivalente a los puntos extremos en la resolución
gráfica de un problema de programación lineal.
Si todas las variables toman valores no negativos, entonces la solución es factible.
De lo contrario es no factible.

Ejemplo 12. Consideramos el siguiente problema en forma estándar:

M ax z = 2x1 + 3x2 + 4x3 + 5x4 + x5

s.a x1 + x2 + 4x3 + 2x4 + 3x5 = 8
4x1 + 2x2 + 2x3 + x4 + 6x5 = 4
x1 , x 2 , x 3 , x 4 , x 5 ≥ 0

En este caso m = 2 y n = 5. Se tiene entonces:

1. n − m = 3 variables no básicas a las que les asignamos el valor 0.

2. m = 2 variables básicas, que se le asigna el valor obtenido de resolver el sistema de

ecuaciones formado por las restricciones.

Las posibles combinaciones de variables no básicas que podemos tomar son:

x1 x2 x3 x1 x2 x4 x1 x2 x5 x1 x3 x4 x1 x3 x5
x1 x4 x5 x2 x3 x4 x2 x3 x 5 x2 x 4 x5 x3 x4 x5

Para algunos de estos casos, se va a comprobar si estas combinaciones de variables pro-

ducen una solución básica factible.

Caso 1: Solución básica factible:

Variables no básicas: x2 , x4 , x5 → se les asigna el valor 0.

Ecuaciones:

x1 + 4x3 = 8
4x1 + 2x3 = 4

Solución: Única con x1 = 0 y x3 = 2

Situación: Solución básica factible debido a que las variables básicas x1 y x3
son ≥ 0

40 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

Caso 2: Solución básica no factible:

Variables no básicas: x3 , x4 , x5 → se les asigna el valor 0.
Ecuaciones:
x1 + x2 = 8
4x1 + 2x2 = 4
Solución: Única con x1 = −6 y x2 = 14
Situación: Solución básica no factible debido a que x1 < 0.
Caso 3: Infinidad de soluciones:
Variables no básicas: x1 , x2 , x5 → se les asigna el valor 0.
Ecuaciones:
4x3 + 2x4 = 8
2x3 + x4 = 4
Solución: No hay solución única.
Situación: Infinidad de soluciones.
Caso 4: Solución inexistente:
Variables no básicas: x1 , x3 , x4 → se les asigna el valor 0.
Ecuaciones:
x2 + 3x5 = 8
2x2 + 6x5 = 4
Solución: No existe.
Situación: Solución inexistente.
En resumen, el problema fundamental de la programación lineal consiste en determi-
nar una solución para un sistema de ecuaciones lineales simultáneas que optimice una
determinada función objetivo. Tales sistemas se resuelven por el método de Gauss. Para
tal resolución es necesario manejar algunos conceptos como los de base y solución básica.
Planteemos lo anterior en términos matriciales. Sea el sistema de ecuaciones (si-
multáneas)
a11 x1 + a12 x2 + · · · a1n xn = b1
a21 x1 + a22 x2 + · · · a2n xn = b2
··················
am1 x1 + am2 x2 + · · · amn xn = bm

Eva Ma Ramos Ábalos 41

3.1. Fundamentos del Simplex. Método del Simplex en forma tabular

cuya matriz de coeficientes, A, es de rango m (rango máximo), se define una base como
el conjunto de vectores columna de cualquier submatriz B de rango m y por tanto no
singular. Al vector xB de variables asociadas a la submatriz B se le llama vector de
variables básicas y a la solución del sistema BxB = b dada por xB = B −1 b se denomina
solución básica. Realmente la solución básica es el vector x que tiene por valores de las
variables ceros salvo para las variables de xB . Cuando una o más variables básicas son cero
se denomina a la solución básica solución degenerada. A partir de la definición anterior se
puede observar que un sistema de ecuaciones simultáneas puede tener muchas soluciones
básicas distintas.

3.1.1. Variables artificiales.

En la fase inicial del método Simplex se necesita disponer de una solución básica factible
de manera rápida. Normalmente la introducción de las variables de holgura suele facilitar
dicha base, sin embargo hay ocasiones en que no es fácil encontrar esta primera solución.

Ejemplo 13. Consideremos el siguiente conjunto de restricciones

2x1 + x2 ≤ 8
4x1 + 3x2 ≥ 14

Al añadir las variables de holgura tenemos:

2x1 + x2 + s1 = 8
4x1 + 3x2 − s2 = 14

Tomando x1 = x2 = 0, es s1 = 8 y s2 = −14, que no constituye una solución básica

factible inicial, ya que todas las variables de un programa lineal en forma estándar deben
ser no negativas.
Para remediarlo se añaden a las restricciones del problema en forma estándar unas
variables artificiales ti ≥ 0 a aquellas restricciones que teniendo originalmente desigualdad
≥ se les añadió restando una variable de exceso más una variable artificial:
∑
n ∑
n
apj xj ≥ bp ⇔ apj xj − sp + tp = bp
j=1 j=1
∑
n ∑
n
aqj xj = bq ⇔ aqj xj + tq = bq
j=1 j=1

donde sp es la variable de exceso y tp la artificial. Estas variables no representan na-

da económicamente son meros artificios matemáticos. Generalmente la primera solución
básica del problema transformado no suele ser factible. Se puede demostrar que cualquier

42 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

solución básica factible del problema transformado en el que las variables artificiales tomen
el valor cero es una solución básica factible del sistema original. Será deseable llevar a cero
lo antes posible a las variables artificiales para que no aparezcan en la base. Una forma
de hacer esto consiste en asignarles en la función objetivo a tales variables un coeficiente
M que se considera un valor muy grande con signo negativo. Por contra las variables de
holgura o exceso suelen tener coeficientes nulos en la función objetivo.
Ejemplo 14.
M ax z = 2x1 + 4x2 − 5x3
s.a. 3x1 + x2 − x3 ≤ 8
2x1 − x2 + 4x3 ≥ 16
x1 + x3 = 7
x1 , x 2 , x 3 ≥ 0
En primer lugar se transforma en un problema de maximizar y después se añaden
variables de holgura y artificiales:
M ax z ′ = 2x1 + 4x2 − 5x3 + 0s1 + 0s2 − M t1 − M t2
s.a. 3x1 + x2 − x3 + s1 = 8
2x1 − x2 + 4x3 − s2 + t1 = 16
x1 + x3 + t2 = 7
x1 , x 2 , x 3 , s 1 , s 2 , t 1 , t 2 ≥ 0
con s1 y s2 variables de holgura y t1 , t2 variables artificiales. Las variables básicas iniciales
son s1 , t1 y t2 .

3.1.2. Principios del método Simplex

El método Simplex busca la solución del problema lineal partiendo de una solución
básica factible inicial y pasando a otra solución básica factible adyacente que mejore (o
al menos no empeore) el valor de la función objetivo. Los pasos generales son:
Paso 0. Iniciar la búsqueda de una solución básica factible inicial (punto extremo).
Paso 1. Determinar si el paso a una solución básica factible adyacente puede mejorar el
valor de la función objetivo. Si es ası́ ir al paso siguiente, en caso contrario se ha
alcanzado la solución óptima.
Paso 2. Determinar la solución básica factible adyacente con mayor mejora en el valor de
la función objetivo. Volver al paso 1 y repetir el proceso hasta alcanzar una solución
óptima o bien que se llegue a un problema infactible o no acotado.
La búsqueda de la solución adyacente se hace extrayendo de la base un vector (una
variable) y poniendo en su lugar otro, esto es, sacando una variable e incluyendo otra.

Eva Ma Ramos Ábalos 43

3.1. Fundamentos del Simplex. Método del Simplex en forma tabular

Determinación de la variable que entra en la base y regla de parada

Se define el coste reducido o relativo asociado a una columna de la matriz de restric-
ciones Aj como la cantidad que mide el efecto sobre el valor de la función objetivo debido
a la introducción de una nueva variable no básica en la base. La medida de dicho coste
reducido es el elemento zj − cj y entrará en la base aquella variable cuyo coste reducido
sea mayor (zj − cj más pequeño y negativo) en un problema de máximo, con
zj = cTB yj
A partir de los costes reducidos se puede obtener el criterio de optimalidad. La variable
de entrada en la base será aquella con el zj − cj más negativo. En caso de igualdad de
varios valores se puede escoger cualquiera de ellos.

Determinación de la variable que deja la base

Dada la solución básica factible xB = B −1 b, si el vector columna Aj de fuera de la
base tiene yij > 0 para algún i, entonces puede entrar en la base en lugar del vector Bk
que verifique que { }
xbk xBi
= min : yij > 0 .
ykj yij

3.1.3. Método Simplex tabular

La aplicación del método Simplex utilizando cálculo matricial resulta incómoda por
lo que se suele utilizar un método tabular que permite la iteración del método simplex
mediante el uso de operaciones elementales de fila (Gauss).
Existen diversas formulaciones, de la que nosotros escogeremos la siguiente:
c1 ··· cn
VB x1 ··· xn xB
cB1 xB1 y11 ··· y1n xB1
··· ··· ··· ··· ··· ···
cBm xBm ym1 ··· ymn xBm
zj − cj z1 − c1 ··· zn − cn z
donde

En la columna con VB se muestra cuáles son las variables básicas.

En la primera columna aparecen los coeficientes de las variables básicas en la función
objetivo.
En la segunda fila se muestran todas las variables del problema (incluidas las de
holgura, artificiales...).

44 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

En la primera fila se muestran los coeficientes de todas las variables en la función

objetivo.

En el interior de la tabla aparecen los valores yij .

En la última columna (de la derecha) se muestran los valores de las variables básicas.

En la última fila se incluyen los costes reducidos.

El último valor de la tabla es el valor de la función objetivo en cada iteración.

Cada iteración del método Simplex tiene asociada una tabla como la anterior. Tras una
tabla inicial en la que las variables básicas tienen como vectores básicos la base canónica
se determina la variable que ha de entrar en la base en función de los costes { reducidos
}
zj −cj y la variable que ha de salir de la base la que verifique que ykj = min yij : yij > 0
xbk xBi

para los yij de la variable que entra en la base. Finalmente se construye la nueva tabla
del Simplex con las nuevas variables básicas buscando la base canónica en los vectores
básicos mediante operaciones elementales de fila (Gauss).

Eva Ma Ramos Ábalos 45

3.1. Fundamentos del Simplex. Método del Simplex en forma tabular

Algoritmo:

Paso 0. Construir la tabla inicial.

Paso 1. Si hay algún valor zj − cj < 0 (POSIBILIDAD DE MEJORA),

ir al paso 3. Si todo zj − cj ≥ 0, ir al paso 2.

Paso 2. Si todo zj − cj ≥ 0 y no hay variables artificiales en la base con valor

positivo, la actual solución es óptima (OPTIMALIDAD). Por el contrario, si
hay alguna variable artificial en la base con valor positivo, el problema es
infactible (INFACTIBILIDAD). Parar

Paso 3. Si para algún zj − cj < 0 es su vector asociado yj ≤ 0, el problema

es no acotado (NO ACOTACIÓN). En otro caso, la mejora es posible, ir a
paso 4.

Paso 4. (SELECCIÓN DE LAS VARIABLES DE ENTRADA Y DE

SALIDA). Seleccionar como variable de entrada aquella con el valor más
negativo de zj − cj y designarla como xk , columna pivote. Seleccionar como
variable de salida, la que haga mı́nimo el cociente xBi /yik (para yik > 0) para
cada fila. La notamos por r y esta será la fila pivote. El elemento yrk será el
elemento pivote.

Paso 5. (CÁLCULO DE LA NUEVA TABLA). Construir la nueva tabla

de valores, en la que se habrá sustituido la variable básica de salida por la nueva
variable básica de entrada. Sustituir también los coeficientes en la primera
columna. A continuación se divide por el elemento pivote, los elementos de la
fila pivote, con lo que el pivote pasa a valer uno, y haciendo ceros en todos los
elementos de la columna pivote (incluyendo la fila objetivo) por aplicación del
método de Gauss. Se repite el test de optimalidad. La iteración de este proceso
llevará a la solución del programa o a la conclusión de que el programa no tiene
solución.
Tipos de soluciones
Según esto, las posibilidades de que el sı́mplex termine son:

1. Una variable no básica xj puede entrar pero ninguna puede salir. El problema es no
acotado.

2. Ninguna variable puede entrar.

Esto significa que la función objetivo empeora (o se mantiene constante) nos mo-
vamos hacia donde nos movamos, luego estamos en una solución óptima. A su vez,
pueden darse los casos siguientes:

46 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

a) Todas las variables no básicas cumplen zj − cj ̸= 0.

La solución es única (solución de vértice).
b) Hay alguna variable no básica xj con zj − cj = 0.
Esto significa que si hiciéramos entrar a esta variable pasarı́amos a otras so-
luciones con el mismo valor de la función objetivo, es decir, otras soluciones
óptimas. A su vez hay dos posibilidades:
1) Alguna variable básica xi puede salir.
Estamos en una solución de arista.
2) Ninguna variable básica puede salir.
Estamos en una solución de arista infinita.

Ejemplo 15. Resolver aplicando el método simplex el siguiente problema:

M ax z = 3x1 + 2x2
s.a. 2x1 + 3x2 ≤ 12
2x1 + x2 ≤ 8
x1 , x 2 ≥ 0

En primer lugar se transforma el problema a forma estándar:

M ax z = 3x1 + 2x2 + 0s1 + 0s2

s.a. 2x1 + 3x2 + s1 = 12
2x1 + x2 + s2 = 8
x1 , x 2 , s 1 , s 2 ≥ 0

Paso 0. Se construye la tabla inicial.

3 2 0 0
VB x1 x2 s1 s2 xB
0 s1 2 3 1 0 12
0 s2 2 1 0 1 8
zj − cj -3 -2 0 0 0

Paso 1. Como hay valores zj − cj < 0 (-3 y -2 de la última fila), se va al paso 3

para decidir quien sale y quien entra en la base.

Paso 3. No hay vectores asociados yj con los zj − cj negativos (y1 = (2, 2), y2 =
(3, 1)), con todos sus elementos menores o iguales que cero, por lo que es posible
una mejora de la solución actual.

Eva Ma Ramos Ábalos 47

3.1. Fundamentos del Simplex. Método del Simplex en forma tabular

Paso 4. El zj − cj más negativo es z1 − c1 = −3, ası́ que x1 es la variable de entrada

x
con k = 1 la columna pivote. Calculamos los cocientes yBili :

xB1 12 xB2 8
= = 6, = =4
y11 2 y21 2
y el mı́nimo corresponde a la segunda fila, ası́ que r = 2 es la fila pivote con x4 la
variable de salida de la base. El elemento y21 = 2 es el pivote (marcado en la tabla
con un recuadro).

Paso 5. Construimos la nueva tabla en la que la variable x1 sustituye a s2 en la

columna VB y lo mismo para sus respectivos coeficientes. La fila 2 de la nueva
tabla se obtiene dividiendo la fila 2 de la tabla precedente por el pivote y21 = 2. La
columna 1 de la tabla está formada por el elemento ŷ11 = 0 (para ello se realiza la
operación F1 − 2F2 , con F2 la fila pivote) y ŷ21 = 1.

3 2 0 0
VB x1 x2 s1 s2 xB
0 s1 0 2 1 -1 4
3 x1 1 1/2 0 1/2 4
zj − cj 0 -1/2 0 3/2 12

Volvemos a paso 1.

Paso 1. En este caso, como z2 − c2 = −1/2 es negativo, vamos a paso 3.

Paso 3. Hay elementos positivos en la columna asociada (2, 1/2), por lo que hay
posibilidad de mejora. Ir a paso 4.

Paso 4. El zj − cj más negativo (y único) es el asociado a x2 que será la variable

de entrada. Se calculan los cocientes de los elementos de esa columna entre los de
la columna xB , y se elige el mı́nimo:
{ }
4 4
M in ; = M in{2; 8} = 2
2 1/2

por lo que la variable de salida es s1 . El elemento pivote es y12 = 2.

Paso 5. Se construye la nueva tabla en la que la variable x2 sustituye a s1 en la

columna VB y lo mismo para sus respectivos coeficientes. La fila 1 de la nueva
tabla se obtiene dividiendo la fila 1 de la tabla precedente por el pivote y12 = 2. La
columna 1 de la tabla está formada por el elemento ŷ21 = 0 (para ello se realiza la
operación F2 − F1 /2, con F1 la fila pivote) y ŷ12 = 1.

48 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

3 2 0 0
VB x1 x2 s1 s2 xB
2 x2 0 1 1/2 -1/2 2
3 x1 1 0 -1/4 3/4 3
zj − cj 0 0 1/4 5/4 13

Como todos los valores zj − cj son positivos la tabla nos da la solución óptima con:
x1 = 3, x2 = 2, s1 = 0, s2 = 0
con valor de la función objetivo z ∗ = 13.
Si este problema se hubiera resuelto de forma gráfica, podrı́a comprobarse que en
las iteraciones del algoritmo el movimiento ha sido de valor extremo a valor extremo
adyacente de la función objetivo.

3.2. Método de la M-grande y método de las dos fases

3.2.1. Método de la M-grande
Este método es la aplicación del método simplex a problemas con variables artificiales.
Para la resolución de problemas a mano, se puede utilizar como coeficientes de las variables
artificiales −M en las distintas iteraciones del algoritmo. Sin embargo, cuando se emplee
un programa informático, basta con introducir como coeficiente un número negativo muy
grande en comparación con los coeficientes de las variables de decisión de la función
objetivo.
Ejemplo 16. Consideremos el siguiente conjunto de restricciones
M ax z = x1 + 2x2
s.a. 4x1 + x2 ≤ 12
x1 + x 2 ≥ 2
x1 , x 2 ≥ 0

Se pasa a forma estándar el problema introduciendo variables de holgura y una artifi-

cial:

M ax z = x1 + 2x2 + 0s1 + 0s2 − M t1 1 2 0 0 -M

VB x1 x2 s1 s2 t1 xB
s.a. 4x1 + x2 + s1 = 12
0 s1 4 1 1 0 0 12
x1 + x2 − s2 + t1 = 2 -M t1 1 1 0 -1 1 2
x1 , x 2 , s 1 , s 2 , t 1 ≥ 0 zj − cj -1-M -2-M 0 M 0 -2M

Eva Ma Ramos Ábalos 49

3.2. Método de la M-grande y método de las dos fases

1 2 0 0 -M 1 2 0 0 -M
VB x1 x2 s1 s2 t1 xB VB x1 x2 s1 s2 t1 xB
0 s1 3 0 1 1 -1 10 0 s2 3 0 1 1 -1 10
2 x2 1 1 0 -1 1 2 2 x2 4 1 1 0 0 12
zj − cj 1 0 0 -2 2+M 4 zj − cj 7 0 2 0 M 24

La solución óptima es x∗1 = 0, x∗2 = 12, s∗1 = 0 s∗2 = 10 t∗1 = 0 con z ∗ = 24.
Observando las restricciones del problema, notemos que al ser s1 = 0, la primera
restricción no tiene holgura, es decir, se verifica como igualdad en la solución óptima,
mientras que como s2 = 10, la segunda restricción tiene un superávit o sobrante en la
solución óptima de 10 unidades.

3.2.2. Método de las dos fases

Este método surge como alternativa a la resolución con el método simplex de programas
con variables artificiales. En el método de la M-grande, se utiliza un coeficiente M para la
variable artificial en la función objetivo. Si el M se toma demasiado grande, puede tender
a dominar los valores de zj − cj y producir errores de redondeo que se verán reflejados
en la solución final. Si por el contrario, el M se toma pequeño, podrı́a no surtir su efecto
de sacar las variables artificiales de la base, obteniendo alguna un valor positivo en la
solución final, siendo ası́ el problema infactible cuando realmente podrı́a no serlo.
Este método resuelve el problema en dos fases, tal y como su nombre indica:

Fase 1: Se intenta determinar una solución básica factible a partir de la maximiza-

ción de la función objetivo artificial (con signo negativo de las variables artificiales).
Si el valor de este objetivo artificial es cero, tendremos una solución inicial para el
problema original y pasamos a la fase 2. En otro caso el problema es infactible.

Fase 2: Se aplica el método simplex al problema original (si no hay variables arti-
ficiales en la base final de la fase 1), utilizando la solución básica factible obtenida
antes, como solución de partida. Si por el contrario al final de la fase 1 hay variables
artificiales en la base (con valor cero), la función objetivo que se utiliza es la original
del problema más esas variables artificiales, a las que se les asigna un coeficiente
nulo. En ambos casos, al inicio de la fase 2 se prescinde de las columnas correspon-
dientes a las variables artificiales que no estuvieran en la base al final de la fase
anterior.

50 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

Algoritmo:

Inicialización

Paso 0. Poner el problema en la forma estándar de maximización añadiendo va-

riables artificiales.

Fase 1

Paso 1. Modificar el objetivo considerando la maximización de la función objeti-

vo artificial z 0 , de la siguiente forma: cambiar coeficientes de la función
objetivo del paso 0 poniéndoles -1 a las variables artificiales y 0 al resto.
Paso 2. Aplicar el método simplex al programa construido. El proceso termina
cuando la función objetivo artificial z 0 = 0 o todo zj − cj ≥ 0, y si no
hay variables artificiales en la base con valor positivo ir al paso 3. En
otro caso, el problema es infactible y parar.

Fase 2

Paso 3. Considerar la función objetivo original poniendo el coeficiente 0 a todas

aquellas variables artificiales que aparezcan en la base al final de la fase
1 y prescindiendo de las columnas asociadas variables artificiales en el
cuadro final de la fase 1.
Paso 4. La tabla inicial de la fase 2 es la final de la fase 1, salvo que se haya
prescindido de las columnas de las variables artificiales que no figuraban
en la función objetivo construida en el paso 3, y que además hay que
calcular de nuevo.
Paso 5. Si la función objetivo construida en el paso 3 no tiene variables artificia-
les, aplicar el método del simplex. En otro caso, ir a l paso 6.
Paso 6. Aplicar el método del simplex con la siguiente modificación en la regla
de la variable de salida: Si xk es la columna pivote (variable de entrada),
considerar los valores yik de las variables artificiales (de la base) y si
alguno de estos es negativo, tomar como variable de salida alguna de
las variables artificiales con yik < 0 (con esto se evita que las posibles
variables artificiales de la base tomen valores positivos durante la fase
2). En otro caso utilizar la regla de la variable de salida del método del
simplex.

Eva Ma Ramos Ábalos 51

3.2. Método de la M-grande y método de las dos fases

Ejemplo 17. Apliquemos el método de las dos fases al siguiente problema:

M in z = x1 + x2 + 4x3
s.a. x1 + 2x2 − x3 ≥ 20
3x1 + x3 = 14
x1 , x 2 , x 3 ≥ 0

Inicialización
Paso 0. Poner el problema en la forma estándar de maximización añadiendo variables
de holgura y artificiales.
M ax z ′ = −x1 − x2 − 4x3 + 0s1 − M t1 − M t2
s.a. x1 + 2x2 − x3 − s1 + t1 = 20
3x1 + x3 + t2 = 14
x1 , x 2 , x 3 , s 1 , t 1 , t 2 ≥ 0

Fase 1
Paso 1. La función objetivo artificial es
z 0 = 0x1 + 0x2 + 0x3 + 0s1 − t1 − t2
Paso 2. Aplicar el método simplex al programa construido.
0 0 0 0 -1 -1
VB x1 x2 x3 s1 t1 t2 xB
-1 t1 1 2 -1 -1 1 0 20
-1 t2 3 0 1 0 0 1 14
zj − cj -4 -2 0 1 0 0 -34

0 0 0 0 -1 -1
VB x1 x2 x3 s 1 t1 t2 xB
-1 t1 0 2 -4/3 -1 1 -1/3 46/3
0 x1 1 0 1/3 0 0 1/3 14/3
zj − cj 0 -2 4/3 1 0 4/3 -46/3

0 0 0 0 -1 -1
VB x1 x2 x3 s1 t1 t2 xB
0 x2 0 1 -2/3 -1/2 1/2 -1/6 23/3
0 x1 1 0 1/3 0 0 1/3 14/3
zj − cj 0 0 0 0 1 1 0

52 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

Hemos obtenido que z 0 = 0 por lo que termina el proceso. Como no hay

variables artificiales en la base con valor positivo, vamos al paso 3.

Fase 2

Paso 3. La función objetivo en esta fase es:

M ax z ′ = −x1 − x2 − 4x3 + 0s1

Paso 4. Se prescinde de las variables artificiales por no estar en la base, ası́ como de
sus columnas. Se forma la tabla inicial de la fase 2 en la que no aparecen las
columnas de t1 y t2 y están cambiados los coeficientes cB y cj . Se calcula por
tanto de nuevo los valores zj − cj y z.

-1 -1 -4 0
VB x1 x2 x3 s1 xB
-1 x2 0 1 -2/3 -1/2 23/3
-1 x1 1 0 1/3 0 14/3
zj − cj 0 0 13/3 1/2 -37/3

Paso 5. Como todo zj − cj ≥ 0, la solución óptima es:

x∗1 = 14/3 x∗2 = 23/3 x∗3 = s∗1 = 0

y el valor del objetivo es

z = −z ′ = 37/3

3.3. Formulación del problema Dual. Relaciones Primal-

Dual
Uno de los conceptos más importantes en programación lineal es el de dualidad. Este con-
cepto establece que cada programa lineal tiene un programa lineal asociado denominado
su dual.
Vamos a estudiar la relación entre un programa lineal y su dual, y la utilización de
este último para ver que es posible en determinados casos obtener importante información
económica sobre el programa lineal.
La idea fundamental de la dualidad en programación lineal es que cada programa
lleva asociado un programa dual, de forma que la resolución del programa lineal original,
permite obtener una solución para su dual.

Eva Ma Ramos Ábalos 53

3.3. Formulación del problema Dual. Relaciones Primal- Dual

3.3.1. Problema primal-dual simétrico

Un programa de programación lineal simétrica (de maximización) es aquél en que:

1. El objetivo es de la forma de maximización.

2. Todas las restricciones son desigualdades del tipo ≤.

3. Las variables son no negativas.

Cualquier problema de forma lineal se puede expresar de forma simétrica.
Ejemplo 18. Expresar en forma simétrica el siguiente problema:
M ax z = 4x1 − 3x2
s.a. 2x1 + x2 ≤ 5
4x1 − 2x2 ≥ 7
2x1 + 3x2 = 9
x≥0
Para ello, vamos a multiplicar la segunda restricción por -1 cambiando de ésta manera
el sentido de la desigualdad:
4x1 − 2x2 ≥ 7 ⇒ −4x1 + 2x2 ≤ −7
Descomponemos la tercera restricción en dos, una de ≤ y otra de ≥. Esta última habrá
que multiplicarla por -1 para cambiar el sentido de la desigualdad.
{ {
2x1 + 3x2 ≤ 9 2x1 + 3x2 ≤ 9
2x1 + 3x2 = 9 ⇒ ⇒
2x1 + 3x2 ≥ 9 −2x1 − 3x2 ≤ −9
Se establece la relación primal-dual en forma simétrica como sigue:
M ax z = c′ x (3.1)
s.a. Ax ≤ b
x≥0
donde c es un vector n × 1, x es un vector m × n y b es un vector n × 1. Se considera
ahora el siguiente problema de programación lineal:
M in w = b′ y (3.2)
s.a. A′ y ≥ c
y≥0
donde y es un vector m × 1.
Cada uno de estos problemas es el dual del otro. Al problema (3.3) se le denomina
problema primal y a (3.2) se le denomina problema dual.

54 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

Ejemplo 19. Dado el siguiente problema de programación lineal, que llamamos primal,
obtener su problema dual
M ax z = 2x1 − x2 + 2x3 + x4
s.a. 2x1 + x2 + x3 + 2x4 ≤ 18
3x1 + 4x2 + 2x3 + x4 ≤ 24
x≥0
su problema dual es
M in w = 18y1 + 24y2
s.a. 2y1 + 3y2 ≥ 2
y1 + 4y2 ≥ −1
y1 + 2y2 ≥ 2
2y1 + y2 ≥ 1
y≥0
A las variables x1 , x2 , x3 , x4 se les denomina variables primales de decisión y a y1 , y2
variables duales de decisión.
Se tienen las siguientes relaciones estructurales entre ambos problemas:
1. El objetivo de un problema es de maximización y el del otro de minimización.
2. El el problema de maximización, todas las restricciones son desigualdades del tipo
≤ y en el de minimización del tipo ≥.
3. Todas las variables primales y duales son no negativas.
4. Los elementos a la derecha de las restricciones son los coeficientes de la función
objetivo en el otro.
5. Cada variable en un problema da lugar a una restricción en el otro y viceversa.
6. La matriz de los coeficientes de las restricciones en un problema es la traspuesta de
la matriz de coeficientes en el otro.

Relaciones en dualidad
1. El dual del problema dual es el primal.
2. Dualidad débil.
El valor de la función objetivo z del problema de maximización es siempre menor o
igual que el valor de la función objetivo w del problema de minimización, si ambos
son factibles.

Eva Ma Ramos Ábalos 55

3.3. Formulación del problema Dual. Relaciones Primal- Dual

3. Si el primal es factible pero no acotado, el dual es infactible.

4. Si el dual es factible pero no acotado, el primal es infactible.

5. Si el primal es infactible, el dual puede ser no acotado o infactible, y viceversa, si el

dual es infactible el primal puede ser no acotado o infactible.

6. Si existen soluciones factibles para los problemas primal y dual que dan igual valor
a los respectivos objetivos, tales soluciones son óptimas.

7. Los valores óptimos z ∗ y w∗ de los problemas primal y dual son iguales.

8. Condiciones de holgura complementaria.

Con estas condiciones se permite la determinación de la solución dual óptima a
partir de la solución primal óptima y viceversa.
Sean x∗ e y ∗ soluciones factibles para los problemas primal y dual, respectivamente.
La interpretación de este resultado es de gran interés. Sean s (m × 1) y v (n × 1)
vectores de variables de holgura de los problemas primal y dual respectivamente.
Por lo tanto se tiene que:

si yi∗ = 0 para i = 1, . . . , m
vj x∗j = 0 para j = 1, . . . , n

por lo que estas condiciones se pueden interpretar para que exista una solución
óptima como

a) Si una variable primal es positiva (x∗ > 0) la correspondiente restricción dual

es una igualdad, es decir, la restricción dual es una igualdad en el óptimo con
vj = 0.
b) Si una restricción primal es una desigualdad en el óptimo (si > 0), la corres-
pondiente variable dual es cero en el óptimo (yi∗ = 0).
c) Si una variable dual es positiva (yi∗ > 0), la correspondiente restricción primal
es una igualdad (si = 0).
d ) Si una restricción dual es una desigualdad (vj > 0) la correspondiente variable
primal es cero en el óptimo (x∗j = 0).

56 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

Ejemplo 20. Calculemos la solución óptima de un problema dual a partir de la solución

óptima del primal. Consideremos el problema primal al que se le ha añadido variables de
holgura s = (s1 , s2 ).

M ax z = 4x1 + 2x2 + x3 + 0s1 + 0s2

s.a. x1 + x2 + x3 + s1 = 12
4x1 + x2 + 2x3 + s2 = 18
x1 , x 2 , x 3 , s 1 s 2 ≥ 0

su problema dual añadiendo las variables de holgura v = (v1 , v2 , v3 ) es

M in w = 12y1 + 18y2 + 0v1 + 0v2 + 0v3

s.a. y1 + 4y2 − v1 = 4
y 1 + y 2 − v2 = 2
y1 + 2y2 − v3 = 1
y1 , y 2 , v 1 , v 2 , v 3 ≥ 0

Las condiciones de holgura complementaria en el óptimo x∗ , y ∗ , para cada respectivo

problema, son

si yi∗ = 0 para i = 1, 2
vj x∗j = 0 para j = 1, 2, 3

La solución óptima del problema primal es

x∗1 = 2, x∗2 = 10, x∗3 = 0 con z ∗ = 28

Aplicando las condiciones de holgura complementaria tenemos,

x∗1 = 2 > 0 implica que v1 = 0

x∗2 = 10 > 0 implica que v2 = 0

por lo tanto

y1∗ + 4y2∗ = 4
y1∗ + y2∗ = 2

Resolviendo este sistema se obtiene

y1∗ = 4/3, y2∗ = 2/3 con w∗ = 28

Eva Ma Ramos Ábalos 57

3.3. Formulación del problema Dual. Relaciones Primal- Dual

Lectura de la solución dual en la tabla óptima del problema primal

Se ha visto como se puede calcular la solución óptima del problema dual a partir de la
solución óptima del problema primal, utilizando las condiciones de holgura complemen-
taria. Veamos ahora una forma más sencilla y directa de obtener la solución dual óptima
a partir de la tabla óptima del simplex del problema primal. Para ello consideramos los
siguiente:

Si el problema de programación lineal [3.3] tiene una solución óptima correspondiente

a una base B, entonces y ∗ = cTB B −1 es una solución óptima para el problema dual
[3.2].
Dada la tabla óptima del simplex del problema primal, si zj − cj es el valor asociado
a una variable primal básica original en la j-ésima restricción primal, entonces el
valor óptimo de la j-ésima variable dual es decisión es |zj − cj |.

Ejemplo 21. Sea el problema de programación lineal

M ax z = 4x1 + 2x2 + x3
s.a. x1 + x2 + x3 ≤ 12
4x1 + x2 + 2x3 ≤ 18
x≥0

Pasamos al forma estándar

M ax z = 4x1 + 2x2 + x3 + 0s1 + 0s2

s.a. x1 + x2 + x3 + s1 = 12
4x1 + x2 + 2x3 + s2 = 18
x, s ≥ 0

Aplicamos el método simplex al programa construido.

4 2 1 0 0
VB x1 x2 x3 s1 s2 xB
0 s1 1 1 1 1 0 12
0 s2 4 1 2 0 1 18
zj − cj -4 -2 -1 1 0 0

4 2 1 0 0
VB x1 x2 x3 s 1 s2 xB
0 s1 0 3/4 1/2 1 -1/4 15/2
4 x1 1 1/4 1/2 0 1/4 9/2
zj − cj 0 -1 1 0 1 18

58 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

4 2 1 0 0
VB x1 x2 x3 s1 s2 xB
2 x2 0 1 2/3 4/3 -1/3 10
4 x1 1 0 1/3 -1/3 1/3 2
zj − cj 0 0 5/3 4/3 2/3 28

SOLUCIÓN ÓPTIMA:

x∗1 = 2, x∗2 = 10, x∗3 = 0, z ∗ = 28

El problema dual tendrá dos variables y1 e y2 ya que el problema primal tiene dos restric-
ciones. La solución del problema dual tiene valor z ∗ = w∗ = 28.
La variable básica original s1 estaba en la primera restricción:
 
4
y1 = |z4 − c4 | =  
3

La variable básica original s2 estaba en la segunda restricción:

 
2
y2 = |z5 − c5 | =  
3

Luego la solución óptima del problema dual es:

4 2
y1∗ = , y2∗ = , w∗ = 28
3 3

3.3.2. Problema primal-dual general

Un problema de programación lineal en forma general es aquel que:

1. El objetivo es de la forma de maximización o minimización.

2. Las restricciones son desigualdades ≤ o igualdades si el problema es de maxi-

mización y desigualdades ≥ o igualdades si es de minimización.

3. Las variables pueden estar o no restringidas.

Las relaciones primal-dual para la forma general es:

a) El objetivo de un problema es de la forma de maximización y el del otro de mini-

mización.

b) En el problema de maximización todas las restricciones son desigualdades del tipo

≤ o igualdades. En el de minimización son ≥ o igualdades.

Eva Ma Ramos Ábalos 59

3.3. Formulación del problema Dual. Relaciones Primal- Dual

c) Los elementos de la derecha de las restricciones en un problema son los coeficientes

de la función objetivo en el otro.

d) Cada variable en un problema da lugar a una restricción en el otro, y viceversa.

e) La matriz de coeficientes de las restricciones en un problema es la traspuesta de la

matriz de los coeficientes en el otro.

f) Si una variable en un problema es no restringida, su restricción asociada en el otro

es una igualdad y viceversa.

La siguiente tabla muestra de forma resumida como obtener el problema dual a partir del
primal:

PROBLEMA PRIMAL PROBLEMA DUAL

Maximización Minimización
Coeficientes de la función objetivo Términos independientes de las restricciones
Coeficientes de la ı́-ésima restricción Coeficientes de la ı́-ésima variable
Términos independientes de las restricciones Coeficientes de la función objetivo
La i-ésima restricción tiene un signo ≤ La i-ésima variable dual es no negativa
La i-ésima restricción tiene un signo = La i-ésima variable dual no está restringida en signo
La i-ésima variable no está restringida en signo La i-ésima restricción es una igualdad
La i-ésima variable es no negativa La i-ésima restricción es una desigualdad del tipo ≥
La i-ésima variable es no positiva La i-ésima restricción es una desigualdad del tipo ≤
Número de variables Número de restricciones

Ejemplo 22. Determinemos el dual del problema

M ax z = 2x1 + 3x2
s.a. x1 − x2 ≥ 0
x1 + x 2 = 8
−3x1 + 2x2 ≤ 4
x1 ≥ 0, x2 no restringida

Se expresa el problema en la forma general de maximización poniendo la primera

restricción en ≤:

M ax z = 2x1 + 3x2
s.a. −x1 + x2 ≤ 0
x1 + x2 = 8
−3x1 + 2x2 ≤ 4
x1 ≥ 0, x2 no restringida

60 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

El problema dual será:

M in w = 0y1 + 8y2 + 4y3

s.a. −y1 + y2 − 3y3 ≥ 2
y1 + y2 + 2y3 = 3
y1 , y3 ≥ 0, y2 no restringida

La segunda restricción dual es una igualdad ya que la segunda variable primal no está
restringida. La segunda variable dual no está restringida ya que la segunda restricción
primal es una igualdad.

Ejemplo 23. Determinemos el dual del problema

M in z = 2x1 + 3x2 − x3
s.a. 2x1 + x2 − x3 ≥ 2
x1 − 2x2 + 3x3 = 6
x1 + 3x2 + 4x3 ≤ 10
x1 , x2 ≥ 0, x3 no restringida

En primer lugar ponemos el problema en forma general y luego se obtiene el dual:

M in z = 2x1 + 3x2 − x3 M ax w = 2y1 + 6y2 − 10y3

s.a. 2x1 + x2 − x3 ≥ 2 s.a. 2y1 + y2 − y3 ≤ 2
Dual ⇒
x1 − 2x2 + 3x3 = 6 y1 − 2y2 − 3y3 ≤ 3
−x1 − 3x2 − 4x3 ≥ −10 −y1 + 3y2 − 4y3 = −1
x1 , x2 ≥ 0, x3 no restringida y1 , y3 ≥ 0, y2 no restringida

Método del simplex dual

Se ha visto que dado un problema de programación lineal, que llamamos primal, podemos
determinar su dual. Ya que resolver un problema equivale a resolver el otro, se seleccio-
nará aquel con apariencia más sencilla. Por otra parte, cada iteración de un problema
va asociado con una iteración del otro, por lo que al resolver uno se está obteniendo
simultáneamente la solución del otro. Estudiaremos el algoritmo del simplex dual que
aprovecha la ventaja descrita anteriormente. Tiene una aplicación restringida, ya que solo
se puede aplicar a problemas con primal infactible y dual factible (es decir, uno o más
xBi son negativos y todo zj − cj ≥ 0), pero es importante en el análisis de sensibilidad y
programación entera.
La tabla que utiliza el simplex dual es la misma que la del primal. El algoritmo, man-
teniendo la optimalidad o factibilidad dual (zj − cj ≥ 0), trata de alcanzar la optimalidad

Eva Ma Ramos Ábalos 61

3.3. Formulación del problema Dual. Relaciones Primal- Dual

primal (xBi ≥ 0), en cuyo caso la solución es primal y dual factible.

ALGORITMO

Paso 1. Dada xB solución básica factible, si xB ≥ 0, la solución es óptima y parar.

En otro caso, es decir, si uno o varios xBi < 0, ir a paso 2.

Paso 2. (SELECCIÓN DE LA VARIABLE DE SALIDA) Seleccionar como

variable de salida aquella variable básica con el xBi más negativo, y notar la fila
asociada (fila pivote) por r y la variable xr .

Paso 3. (SELECCIÓN DE LA VARIABLE DE ENTRADA) Determinar

para aquellas columnas no básicas con elemento yrj < 0, el cociente
zj − cj
yrj

seleccionando como variable de entrada aquella que tenga mayor cociente. La colum-
na pivote se nota por k y la variable asociada por xk . El elemento yrk es el elemento
pivote.
Si yrj ≥ 0 para todo j (todos los elementos de la fila pivote son no negativos) el
problema no tiene solución (el dual es no acotado y el primal es infactible)

Paso 4. Establecer una nueva tabla mediante el mismo procedimiento que con el
simplex primal. Volver a paso 1.

Ejemplo 24. Apliquemos el algoritmo del simplex dual al problema

M in z = 2x1 + x2 + 4x3
s.a. 2x1 − x2 + 3x3 ≥ 8
x1 + 3x2 + 2x3 ≥ 7
x1 , x 2 , x 3 ≥ 0

En primer lugar se pasa a la forma de maximización y se añaden las variables de

holgura

M ax z = −2x1 − x2 − 4x3 + 0s1 + 0s2

s.a. −2x1 + x2 − 3x3 + s1 = −8
−x1 − 3x2 − 2x3 + s2 = −7
x1 , x 2 , x 3 , s 1 , s 2 ≥ 0

62 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

Construimos la tabla inicial del simplex

-2 -1 -4 0 0
VB x1 x2 x3 s1 s2 xB
0 s1 -2 1 -3 1 0 -8
0 s2 -1 -3 -2 0 1 -7
zj − cj 2 1 4 0 0 0

Se puede aplicar el método del simplex dual ya que es primal infactible (xB1 = −8, xB2 =
−7) y dual factible (zj − cj ≥ 0)).
El xBi más negativo corresponde a la primera fila, ası́ que esta es la fila pivote (r = 1),
por lo que s1 sale de la base. Para determinar la variable de entrada, se calculan los
zj − cj
cocientes para las columnas con y1j < 0, y se elige aquella con mayor cociente:
y1j
z1 − c1 2 z3 − c3 4 −4
= = −1; = = = −1,33
y11 −2 y13 −3 3
En este caso, la columna pivote es la primera, k = 1, y el elemento pivote es y11 = −2.
Se construye la nueva tabla del simplex dual:
-2 -1 -4 0 0
VB x1 x2 x3 s1 s2 xB
-2 x1 1 -1/2 3/2 -1/2 0 4
0 s2 0 -7/2 -1/2 -1/2 1 -3
zj − cj 0 2 1 1 0 -8

Sigue habiendo un xBi negativo, por lo que volvemos al inicio del algoritmo. El xBi
más negativo corresponde a la segunda fila, ası́ que esta es la fila pivote (r = 2), por lo
que s2 sale de la base. Para determinar la variable de entrada, se calculan los cocientes
zj − cj
para las columnas con y2j < 0, y se elige aquella con mayor cociente:
y2j
z2 − c2 2 4 z3 − c3 1 z4 − c4 1
= =− ; = = −2; = = −2
y12 −7/2 3 y13 −1/2 y14 −1/2
En este caso, la columna pivote es la segunda, k = 2, y el elemento pivote es y22 = −7/2.
La tabla resultante es
-2 -1 -4 0 0
VB x1 x2 x3 s1 s2 xB
-2 x1 1 0 23/14 22/14 1/7 31/7
-1 x2 0 1 1/7 1/7 -2/7 6/7
zj − cj 0 0 5/7 5/7 4/7 -68/7

Eva Ma Ramos Ábalos 63

3.3. Formulación del problema Dual. Relaciones Primal- Dual

La nueva solución dual básica factible es xB = (31/7, 6/7) ≥ 0, luego es óptima. Por
tanto la solución es:
31 6
x∗1 = , x∗2 = , x∗3 = s∗1 = s∗2 = 0, z ∗ = −z ′∗ = 68/7
7 7

3.3.3. Interpretación económica del problema Dual

Veamos la interpretación económica de los valores óptimos de las variables duales, cuya
utilidad práctica es en muchas ocasiones de tanta importancia como lo es la solución
óptima. La solución óptima de un problema de programación lineal da respuesta por
ejemplo, a la asignación óptima de un conjunto de recursos en un momento determinado.
Las variables duales pueden dar información útil sobre la posible expansión y crecimiento
del beneficio.
Si suponemos xB ̸= 0 e introducimos pequeños cambios (△b) en el vector de recursos
b, la base continuará siendo óptima.
Si se resuelve nuevamente el problema lineal con b + △b en vez de b, la variación en el
valor óptimo del objetivo es y ∗T △b.
Se puede afirmar que:

La variable dual yi∗ indica la contribución por unidad del recurso i-ésimo bi a la
variación en el valor óptimo z ∗ actual del objetivo.
Los valores óptimos de las variables duales se denominan precios sombra y se
utilizan para ver si puede resultar ventajoso introducir determinadas cantidades de
recursos adicionales.

Ejemplo 25. Sea el problema

M ax z = 4x1 + 7x2 + 3x3

2x1 + x2 + 2x3 ≤ 30
x1 + 2x2 + 2x3 ≤ 45
x1 , x 2 , x 3 ≥ 0

donde x1 , x2 , x3 representan las producciones de cervezas N, R y B respectivamente.

La solución óptima de este problema es:

x∗1 = 5, x∗2 = 20, x∗3 = 0, z ∗ = 160

Los valores óptimos del problema dual son:

y1∗ = 1/3, y2∗ = 10/3, w∗ = 160

64 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

El precio sombra del recurso malta (b1 ) es y1∗ = 1/3 y representa el incremento del
valor z ∗ = 160 por unidad incrementada en la disponibilidad de malta. Análogamente,
y2∗ = 10/3, es el precio sombra del recurso levadura (b2 ).
Si por ejemplo b = (30, 45) se incrementa en △b = (△b1 , △b2 ) = (10, 15) unidades, el
valor del objetivo se incrementa en

△z ∗ = y ∗T △b = (1/3, 10/3)(10, 15)T = 160/3

y ası́ el nuevo valor óptimo del objetivo es

z ∗ = 160 + 160/3 = 213,33

3.4. Definición del análisis de sensibilidad

En esta sección se examinará la variación posible de los diversos parámetros que intervie-
nen en el modelo de programación lineal de forma que no haya cambios en las variables
de la base de la solución óptima. Se trata de dotar al modelo de programación lineal de
una cierta flexibilidad y no analizarlo, como se viene haciendo hasta ahora, desde una
perspectiva estática, ya que estos pueden estar sujetos a errores o fluctuaciones. Por ello
su conocimiento no siempre es preciso y pueden cambiar con el tiempo, ya que muchos
dependen de parámetros no controlables. Es de gran importancia analizar el efecto de
cambios en la estructura del modelo sobre la solución óptima. Esto recibe el nombre de
análisis de sensibilidad.
Considérese el problema de programación lineal

M ax z = c′ x (3.3)
s.a. Ax ≤ b
x≥0

y supóngase que se ha obtenido una solución óptima x∗ para él y además se dispone de
la tabla final del simplex. En estas condiciones se analizarán las siguientes cuestiones:

1. Variación en los coeficientes de la función objetivo, ci .

2. Variación en los coeficientes del lado derecho de las restricciones, bi .

3. Variación en los coeficientes de las restricciones, aij .

4. Incorporación de una nueva restricción.

5. Incorporación de una nueva variable de decisión.

Eva Ma Ramos Ábalos 65

3.5. Cambios discretos. Incorporación de restricciones. Incorporación de nuevas variables

3.5. Cambios discretos. Incorporación de restriccio-

nes. Incorporación de nuevas variables
3.5.1. Cambios discretos
Cambio en un coeficiente de coste no básico
Cuando el cj corresponde a una variable no básica su modificación sólo afectará al cálculo
de zj −cj . La solución seguirá siendo óptima para todos aquellos valores de cj que cumplan
que zj − cj ≥ 0.
Cuando no se verifique esta condición, la base actual dejará de ser óptima y habrı́a
que aplicar el método simplex hasta alcanzar nuevamente la optimalidad.
Ejemplo 26. Sea el problema
M ax z = 4x1 + 7x2 + 3x3
2x1 + x2 + 2x3 ≤ 30
x1 + 2x2 + 2x3 ≤ 45
x1 , x 2 , x 3 ≥ 0
donde x1 , x2 , x3 representan las producciones de cervezas N, R y B respectivamente.
La tabla óptima asociada al problema es:
4 7 3 0 0
VB x1 x2 x3 s1 s2 xB
4 x1 1 0 2/3 2/3 -1/3 5
7 x2 0 1 2/3 -1/3 2/3 20
zj − cj 0 0 13/3 1/3 10/3 160
La solución óptima de este problema es:

x∗1 = 5, x∗2 = 20, x∗3 = 0, z ∗ = 160

Esta tabla seguirá siendo óptima siempre que los valores zj − cj sean positivos. Apli-
cando esto, podemos determinar el recorrido de c3 para que esto siga siendo cierto:
( )
2/3
ẑ3 − ĉ3 = (4, 7) − ĉ3 = 22/3 − ĉ3 ≥ 0
2/3
De aquı́ se obtiene que siempre que ĉ3 ≤ 22/3, no será rentable la producción de cer-
veza B.

Supongamos ahora que el beneficio de B pasa a ser de 8 unidades por litro. En este
caso la solución dejará de ser óptima, ya que z3 − c3 serı́a negativo, por lo que x3 deberá
entrar en la base y x1 abandonarla. Para ello se utiliza la última tabla del simplex.

66 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

4 7 8 0 0
VB x1 x2x3 s1 s2 xB
4 x1 1 02/3 2/3 -1/3 5
7 x2 0 12/3 -1/3 2/3 20
zj − cj 0 0-2/3 1/3 10/3 160
4 7 8 0 0
VB x1 x 2 x3 s1 s2 xB
8 x3 3/2 0 1 1 -1/2 15/2
7 x2 -1 1 0 -1 1 15
zj − cj 1 0 0 1 3 165

La solución óptima de este problema es:

x∗1 = 0, x∗2 = 15, x∗3 = 15/2, z ∗ = 165

Cambio en un coeficiente de coste básico

Cuando el coeficiente que se cambia corresponde a una variable básica, se debe analizar la
repercusión en los zj − cj de las variables no básicas, debiendo estas mantener los zj − cj
correspondientes ≥ 0 para que la solución continúe siendo óptima, si bien el valor de la
función objetivo será distinto.
Ejemplo 27. Siguiendo el problema anterior, vemos que si deseamos determinar el efecto
debido al cambio producido al variar el beneficio por unidad de cerveza R, parece intuitivo
que si c2 aumenta o disminuye por encima o por debajo de unos ciertos niveles, puede
cambiar la actual solución óptima. Si por ejemplo R pasa a ser muy poco rentable, en la
nueva solución podrı́a no figurar la producción de la cerveza R.
Determinamos el recorrido de c2 , teniendo en cuenta que conllevará cambios en los
zj − cj correspondientes a variables no básicas.
Supongamos que el nuevo valor de c2 es ĉ2 , para que la solución siga siendo óptima se
tiene que verificar que:

( )
2/3 1 2
ẑ3 − c3 = (4, ĉ2 ) − 3 = − + ĉ2 ≥ 0 ⇐⇒ ĉ2 ≥ 1/2
2/3 3 3
( )
2/3 8 1
ẑ4 − c4 = (4, ĉ2 ) − 0 = − ĉ2 ≥ 0 ⇐⇒ ĉ2 ≤ 8
−1/3 3 3
( )
−1/3 4 2
ẑ5 − c5 = (4, ĉ2 ) − 0 = − + ĉ2 ≥ 0 ⇐⇒ ĉ2 ≥ 2
2/3 3 3

Por tanto, la tabla será óptima si c2 ∈ [2, 8].

Eva Ma Ramos Ábalos 67

3.5. Cambios discretos. Incorporación de restricciones. Incorporación de nuevas variables

Al cambiar un coeficiente básico, también cambia el valor de la función objetivo,

aunque puede no cambiar la solución óptima. Si por ejemplo, c2 pasa a valer 4, la solución
óptima es la misma, pero el nuevo valor del objetivo z es

ẑ = 4 · 5 + 4 · 20 = 100

Supongamos que c2 pasa a valer 9. Entonces tenemos:

( )
2/3 8 18 17
ẑ3 − c3 = (4, 9) −3= + −3= ≥0
2/3 3 3 3
( )
2/3 8 9 1
ẑ4 − c4 = (4, 9) −0= − =− ≤0
−1/3 3 3 3
( )
−1/3 4 18 14
ẑ5 − c5 = (4, 9) −0=− + = ≥0
2/3 3 3 3
Como ẑ4 − c4 ≤ 0, se tiene que aplicar de nuevo el método simplex hasta alcanzar la
optimalidad. Se parte de la siguiente tabla:

4 9 3 0 0
VB x1 x2 x3 s1 s2 xB
4 x1 1 0 2/3 2/3 -1/3 5
9 x2 0 1 2/3 -1/3 2/3 20
zj − cj 0 0 17/3 -1/3 14/3 200
4 9 3 0 0
VB x1 x2 x3 s1 s2 xB
0 s1 3/2 0 1 1 -1/2 15/2
9 x2 1/2 1 1 0 1/2 45/2
zj − cj 1/2 0 6 0 9/2 202,5

La solución óptima de este problema es:

x∗1 = 0, x∗2 = 45/2, x3∗ = 0, s∗1 = 15/2, z ∗ = 202, 5

Cambio en un recurso
En cualquier iteración del método simplex, hemos notado mediante yik al elemento interior
de la tabla que va asociado a la fila i y la columna k. Inicialmente tales elementos se
corresponden con los coeficientes aik de cada restricción, incluidos los de las variables de
holgura y/o artificiales.
Para llevar a cabo el análisis de sensibilidad de los recursos bi es necesario utilizar la
matriz de recursos B −1 que es la inversa de la actual matriz básica. Tal matriz es aquella

68 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

cuyos elementos son las columnas de la tabla inicial de las variables básicas actuales. Para
determinar B −1 vamos a utilizar las tablas del simplex.
Tal matriz inversa se obtiene a partir de las columnas correspondientes al conjunto
de variables básicas iniciales en el cuadro correspondiente a la iteración actual. Una vez
conocida la matriz B −1 podemos analizar el cambio que se produce sobre la solución
óptima cuando hay una variación en la disponibilidad de un recurso bi .
En la tabla del simplex, la columna de la derecha corresponde a los valores xB de las
variables básicas que se obtuvieron en cada iteración y que se corresponden con los valores
bi de los recursos en la tabla inicial. Una variación en un bi lleva consigo un cambio sobre
el vector xB y sobre el valor z del objetivo. Sin embargo, los valores zj − cj permanecen
iguales.
Si llamamos b̂ al nuevo vector de recursos, B −1 a la inversa de la actual matriz básica
y x̂B al nuevo vector correspondiente al lado derecho de la tabla actual se tiene que:

x̂B = B −1 b̂

ẑ = CBT x̂TB
Si x̂B ≥ 0, la tabla permanece óptima.
Ejemplo 28. Siguiendo el ejemplo anterior,

M ax z = 4x1 + 7x2 + 3x3

2x1 + x2 + 2x3 ≤ 30
x1 + 2x2 + 2x3 ≤ 45
x1 , x 2 , x 3 ≥ 0

y suponemos que la disponibilidad de malta aumenta en 9 unidades.

Partimos de la tabla inicial:
4 7 3 0 0
VB x1 x2 x3 s1 s2 xB
0 s1 2 1 2 1 0 30
0 s2 1 2 2 0 1 45
zj − cj -4 -7 -3 0 0 0
La tabla óptima asociada al problema es:

4 7 3 0 0
VB x1 x2 x3 s1 s2 xB
4 x1 1 0 2/3 2/3 -1/3 5
7 x2 0 1 2/3 -1/3 2/3 20
zj − cj 0 0 13/3 1/3 10/3 160

Eva Ma Ramos Ábalos 69

3.5. Cambios discretos. Incorporación de restricciones. Incorporación de nuevas variables

Como la disponibilidad de malta aumenta en 9 unidades, el vector de recursos b que ac-

tualmente es (30, 45) pasa a ser (39, 45).

La matriz B −1 teniendo en cuenta que las variables básicas iniciales son s1 y s2 será:
( )
2/3 −1/3
−1/3 2/3

Por lo tanto, ( )( ) ( )
−1 2/3 −1/3 39 11
x̂B = B b̂ = =
−1/3 2/3 45 17

( )
11
ẑ = CBT x̂TB = (4, 7) = 163
17
La solución sigue siendo óptima, aunque cambian los valores óptimos de las variables y
por supuesto de la función objetivo, que pasan a ser:

x∗1 = 11; x∗2 = 17; s1 = s2 = 0 z ∗ = 163

Calculemos el recorrido de variabilidad de los bj :

b1 : Sea b̂ = (b1 , 45) el nuevo vector de disponibilidades:



 2 45
( )( )  3 b1 − 15 ≥ 0 ⇒ b1 ≥ 2

2/3 −1/3 b1
x̂B = B −1 b̂ = ≥0⇒
−1/3 2/3 45 
 −1

 b1 + 30 ≥ 0 ⇒ b1 ≤ 90
3
[ ]
45
Si b1 ∈ , 90 entonces la solución permanece óptima.
2

b2 : Sea b̂ = (30, b2 ) el nuevo vector de disponibilidades:



 b2
( )( )  20 − 3 ≥ 0 ⇒ b2 ≤ 60

2/3 −1/3 30
x̂B = B −1 b̂ = ≥0⇒
−1/3 2/3 b2 

 2
 −10 + b2 ≥ 0 ⇒ b2 ≥ 15
3
Si b2 ∈ [15, 60] entonces la solución permanece óptima.

70 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

(b1 , b2 ) : Sea b̂ = (b1 , b2 ) el nuevo vector de disponibilidades:



 2 b2
( )( ) 
 b1 − ≥0
2/3 −1/3 b1 3 3
x̂B = B −1 b̂ = ≥0⇒
−1/3 2/3 b2 
 −1


2
b1 + b2 ≥ 0
3 3
Para cualquier b1 y b2 que verifiquen estas condiciones la solución permanecerá
óptima.

Cambio en un coeficiente tecnológico

Los elementos yik de la tabla del simplex, se corresponden inicialmente con los coeficientes
aik de las restricciones, incluidas las variables de holgura y/o artificiales. Un cambio en un
aik , que recibe el nombre de coeficiente tecnológico, tendrá posiblemente un efecto sobre
los yik resultantes.
Solo veremos el análisis cuando el cambio se produzca para un coeficiente aik no básico.
Este cambio afectará a su vector asociado yk y al valor de zj − cj . Si llamamos âk al nuevo
vector tecnológico bajo la variable no básica xk e ŷk al nuevo vector asociado a xk , se
tiene:
ŷk = B −1 âk
ẑk − ĉk = cTB ŷk − ck
Si en la tabla final el nuevo valor ẑk − ĉk es negativo, el problema deja de ser óptimo
y hay que aplicar el método simplex para alcanzar nuevamente la optimalidad.

Ejemplo 29. Siguiendo el ejemplo anterior,

M ax z = 4x1 + 7x2 + 3x3

2x1 + x2 + 2x3 ≤ 30
x1 + 2x2 + 2x3 ≤ 45
x1 , x 2 , x 3 ≥ 0

Partimos de la tabla inicial:

4 7 3 0 0
VB x1 x2 x3 s1 s2 xB
0 s1 a11 = 2 a12 = 1 a13 = 2 1 0 30
0 s2 a21 = 1 a22 = 2 a23 = 2 0 1 45
zj − cj -4 -7 -3 0 0 0

Eva Ma Ramos Ábalos 71

3.5. Cambios discretos. Incorporación de restricciones. Incorporación de nuevas variables

La tabla óptima asociada al problema es:

4 7 3 0 0
VB x1 x2 x3 s1 s2 xB
4 x1 1 0 2/3 2/3 -1/3 5
7 x2 0 1 2/3 -1/3 2/3 20
zj − cj 0 0 13/3 1/3 10/3 160

Supongamos que en nuestro problema hubiera que cambiar el coeficiente a23 = 2 a

â23 = 0
( )( ) ( )
−1 −1 2/3 −1/3 2 4/3
ŷk = B âk = ŷ3 = B â3 = =
−1/3 2/3 0 −2/3
Se tiene que ( )
4/3 7
zj − cj = (4, 7) −3=−
−2/3 3
Por lo tanto se tiene la siguiente tabla en la que hay que volver a aplicar el algoritmo del
simplex.

4 7 3 0 0
VB x1 x2 x3 s1 s2 xB
4 x1 1 0 4/3 2/3 -1/3 5
7 x2 0 1 -2/3 -1/3 2/3 20
zj − cj 0 0 -7/3 1/3 10/3 160
4 7 3 0 0
VB x1 x2 x3 s 1 s2 xB
3 x3 3/4 0 1 1/2 -1/4 15/4
7 x2 1/2 1 0 0 1/2 45/2
zj − cj 7/4 0 0 3/2 11/4 675/4

Siendo esta la nueva solución óptima.

3.5.2. Incorporación de restricciones

A veces es necesario considerar una nueva restricción. El efecto de añadirla a un problema
lineal es un proceso sencillo. Para evaluar su efecto basta verificar si la solución óptima
x∗ , satisface la nueva restricción. Si es ası́, se considera que no hay efecto y x∗ permanece
como solución óptima. Sin embargo, si x∗ no la verifica, hay que evaluar el efecto que
existe sobre la solución. Tal evaluación pasa inicialmente por la incorporación de la nueva
restricción a la tabla final, considerando además la nueva variable de holgura. Ahora bien,
no es posible introducir directamente los coeficientes de las restricciones en la tabla ya que

72 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

previamente hay que pasar a cero los coeficientes de las variables básicas que aparecen en
la restricción, lo que es posible mediante las operaciones matriciales de fila que consisten
en multiplicar cualquier fila de la matriz por un número y sumársela a otra fila.
Ejemplo 30. Siguiendo el ejemplo anterior, supongamos que se introduce en el plan de
producción una restricción relativa a la posibilidad de añadir lúpulo al proceso de produc-
ción de forma que la fabricación de un litro de cerveza N requiere 3 kilos, R requiere 1 y
B requiere 1 y su disponibilidad total es 35.
La nueva restricción es
3x1 + x2 + x3 ≤ 35
La solución óptima x∗ = (5, 20, 0) satisface esta restricción y ası́ esta solución y por tanto
la última tabla permanece óptima.

Supongamos ahora que la disponibilidad de lúpulo es 30, es decir la restricción es

3x1 + x2 + x3 ≤ 30

La solución óptima x∗ = (5, 20, 0) no satisface esta restricción y por tanto la última tabla
no es óptima. Para determinar la solución óptima, se añade una nueva variable de holgura,
que notamos por s3 , con coeficiente 0 en la función objetivo. La restricción es por tanto:

3x1 + x2 + x3 + s3 = 30

La siguiente tabla surge de modificar la tabla óptima del problema sin la nueva restricción,
con la nueva restricción.
4 7 3 0 0 0
VB x1 x2 x3 s1 s2 s3 xB
4 x1 1 0 2/3 2/3 -1/3 0 5
7 x2 0 1 2/3 -1/3 2/3 0 20
0 s3 3 1 1 0 0 1 30
zj − cj 0 0 13/3 1/3 10/3 0 160
Es necesario pasar a cero lo coeficientes de las variables básicas, x1 y x2 . Para ello multi-
plicamos la primera por -3, la segunda por -1 y se las sumamos a la tercer obteniendo la
siguiente tabla:
4 7 3 0 0 0
VB x1 x2 x3 s1 s2 s3 xB
4 x1 1 0 2/3 2/3 -1/3 0 5
7 x2 0 1 2/3 -1/3 2/3 0 20
0 s3 0 0 -5/3 -5/3 1/3 1 -5
zj − cj 0 0 13/3 1/3 10/3 0 160

Eva Ma Ramos Ábalos 73

3.5. Cambios discretos. Incorporación de restricciones. Incorporación de nuevas variables

Esta tabla no es factible y hay que aplicar el método simplex dual para alcanzar de
nuevo la factibilidad. Se saca de la base s3 y se introduce s1 llegando a la solución óptima

x∗1 = 3, x∗2 = 21, x∗3 = 0, s∗1 = 3 z ∗ = 159.

3.5.3. Incorporación de nuevas variables

Una vez resuelto un problema, puede ser interesante conocer el efecto que se puede pro-
ducir como consecuencia de la introducción de una nueva variable de decisión. Esta puede
ser una variable que no afecte a la optimalidad, en cuyo caso será una variable no básica,
o bien puede afectarla y esta nueva variable deberá entrar en la base.
El efecto producido por una nueva variable se puede analizar a partir de lo visto en el
apartado incorporación de restricciones, teniendo en cuenta que a cada variable primal le
corresponde una restricción dual (y viceversa). Si se quiere resolver a partir del problema
primal, se tendrá en cuenta el siguiente proceso:

Paso 1. Si el problema tiene k − 1 variables de decisión, sea xk la nueva

variable. Se modifica la función objetivo y las restricciones.

Paso 2. Construir la k-ésima restricción dual y comprobar si la verifica la

solución dual óptima. Si es ası́, la variable xk no afecta a la tabla óptima. En
otro caso, ir al siguiente paso.

Paso 3. Añadir una nueva columna a la tabla primal óptima cuyos elementos
son ŷk y ẑk − ĉk donde
ŷk = B −1 âk
ẑk − ĉk = cTb ŷk − ck

Paso 4. Aplicar el método simplex para determinar la nueva solución óptima.

Otra alternativa es incluir la columna correspondiente a la nueva variable en la tabla

final. Este cambio afectará a su vector asociado yk y al valor de zj − cj . Para ello, se tiene
que multipicar la nueva columna por la matriz B −1 y calcular el zj − cj asociado. Si en la
tabla final el nuevo valor ẑk − ĉk es negativo, el problema deja de ser óptimo y hay que
aplicar el método simplex para alcanzar nuevamente la optimalidad.

74 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

Ejemplo 31. Siguiendo con el problema anterior, suponemos que se pretende fabricar una
cerveza sin alcohol (S), que requiere 1 unidad de malta y 1 de levadura por litro producido
con un beneficio de 5 unidades monetarias. Se quiere comprobar si este nuevo producto
puede ser económicamente rentable.
Sea x4 la nueva variable primal de decisión, s1 y s2 las variables de holgura. El nuevo
problema primal es:

M ax z = 4x1 + 7x2 + 3x3 + 5x4 M ax z = 4x1 + 7x2 + 3x3 + 5x4 + 0s1 + 0s2
2x1 + x2 + 2x3 + x4 ≤ 30 2x1 + x2 + 2x3 + x4 + s1 = 30
x1 + 2x2 + 2x3 + x4 ≤ 45 x1 + 2x2 + 2x3 + x4 + s2 = 45
x1 , x 2 , x 3 x4 ≥ 0 x1 , x 2 , x 3 x4 , s 1 , s 2 ≥ 0

La cuarta restricción dual es por tanto:

y1 + y2 ≥ 5

La tabla óptima asociada al problema es:

4 7 3 0 0
VB x1 x2 x3 s1 s2 xB
4 x1 1 0 2/3 2/3 -1/3 5
7 x2 0 1 2/3 -1/3 2/3 20
zj − cj 0 0 13/3 1/3 10/3 160

De aquı́ se puede leer que la solución dual óptima es y ∗ = (1/3, 10/3). Esta solución no
verifica la cuarta restricción dual, por lo que añadimos en esta tabla óptima una nueva
columna con los elementos:
( )( ) ( )
−1 2/3 −1/3 1 1/3
ŷk = B âk = ŷ4 = =
−1/3 2/3 1 1/3
( )
1/3
ẑk − ĉk = ẑ4 − ĉ4 = cb ŷ4 − c4 = (4, 7)
T
− 5 = −4/3
1/3
La tabla queda como:
4 7 3 5 0 0
VB x1 x2 x3 x4 s1 s2 xB
4 x1 1 0 2/3 1/3 2/3 -1/3 5
7 x2 0 1 2/3 1/3 -1/3 2/3 20
zj − cj 0 0 13/3 -4/3 1/3 10/3 160
Como ẑ4 − ĉ4 < 0, la tabla no es óptima, por lo que se aplica el método del simplex:

Eva Ma Ramos Ábalos 75

3.6. Programación entera

4 7 3 5 0 0
VB x1 x2 x3 x4 s1 s2 xB
5 x4 3 0 2 1 2 -1 15
7 x2 -1 1 0 0 -1 1 15
zj − cj 4 0 7 0 3 2 180

que nos lleva a la solución óptima

x∗1 = 0, x∗2 = 15, x∗3 = 0, x∗4 = 15 z ∗ = 180.

Es decir, que el beneficio máximo se obtiene produciendo las cervezas R y S.

3.6. Programación entera

En muchos problemas de optimización, los valores sólo tienen sentido si son enteros, por
ejemplo, cuando se trata de asignar personas o máquinas a una cierta actividad. Si esta
es la única diferencia con los problemas de programación lineal, diremos que se trata de
un problema de programación entera y se denota por PE. Aunque la expresión correcta
es programación lineal entera, por lo general, se omite el adjetivo lineal, salvo cuando se
hacen comparaciones con problemas no lineales enteros.
En consecuencia, el modelo matemático del problema de programación entera es el
mismo que el de programación lineal, con la única restricción añadida de que las variables
deben tomar valores enteros. Si este último requisito no se exige a todas las variables
del problema se dice que es un problema de programación entera mixta, y se denota por
PEM.
Un caso particular importante dentro de la programación entera se plantea cuando
se requiere un cierto número de decisiones con dos resultados posibles y mutuamente
excluyentes. Por ejemplo, cuando se plantea hacer una inversión o no hacerla, o cuando
se trata de decidir si una instalación se debe localizar en un determinado lugar o no.
En ese caso, las decisiones posibles se pueden representar por medio de una variable con
dos valores posibles, por ejemplo, cero y uno, de modo que la variable de decisión xi
toma los valores cero si la decisión i-ésima es no y uno si esta decisión es si, o viceversa.
Los problemas que contengan sólo variables de este tipo, llamadas variables binarias, se
denominan problemas de programación entera binaria, se denotan por PEB.
Los primeros intentos para resolver un problema de programación lineal entera surgie-
ron de la metodologı́a utilizada en la resolución de problemas de programación lineal. El
primer algoritmo finito fue dado por R. Gomory y se denominó Método de los planos de
corte. Los avances teóricos en la resolución de programación lineal entera han sido impor-
tantes, si bien no se ha visto correspondido en la eficacia del cómputo. Esto es debido a
los errores de redondeo cometidos en las sucesivas iteraciones y acumulados en el cómputo
que realizan los ordenadores.

76 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

Un problema de programación entera es un problema de programación lineal en el cual

algunas de las variables, o todas, tienen que ser números enteros no negativos. Se define
un problema de programación entera lineal matricialmente como

Opt z = c′ x
s.a. Ax(≤, =, ≥)b
x ≥ 0, xj ∈ N

siendo
 
a11 a12 ··· a1n
 a21 a22 ··· a2n 
A=
 ···
 , x = (x1 .x2 , . . . , xn )′ , b = (b1 , b2 , . . . , bm )′ , c = (c1 , c2 , . . . , cn )′
··· ··· ··· 
am1 am2 ··· amn

En un problema de programación entera la función objetivo y las restricciones podrı́an

no ser lineales, sin embargo en este tema sólo abordaremos métodos de resolución para el
caso en que ambos elementos son lineales.
Cuando se nos presente la resolución de un problema de programación entera, lo
resolvemos como un problema de programación lineal. Si sus soluciones son enteras, ésta
es la solución para el problema de programación lineal entera.
En cualquier problema se verifica que la solución óptima

zopt (P L) ≥ zopt (P LE)

3.6.1. Resolución de problemas de programación entera

El primer método que surge para la resolución de este tipo de problemas consiste en resol-
ver el problema lineal que surge al prescindir de la condición de que las variables toman
valores enteros, que se conoce como problema relajado, y posteriormente aproximar las
soluciones mediante números enteros. Este método puede llevar a soluciones infactibles.
Sin embargo el análisis del problema relajado nos lleva a algunas propiedades interesantes
de gran utilidad para los métodos a aplicar con posterioridad.

Teorema 4. Si el problema relajado de un problema entero es infactible, también lo será

el problema entero propiamente dicho. De hecho la región factible del problema entero
está contenida en del problema relajado, ya que aquella contiene sólo los puntos enteros
de ésta.

Teorema 5. Para un problema entero de maximización el valor del óptimo del problema
relajado es siempre una cota superior del valor óptimo del problema entero: zP∗ E ≤ zP∗ R .
Para problemas de minimización el valor del óptimo del problema relajado es siempre una
cota inferior del valor óptimo del problema entero: zP∗ R ≤ zP∗ E .

Eva Ma Ramos Ábalos 77

3.6. Programación entera

Teorema 6. Si el problema relajado de un problema entero es no acotado, el problema

entero propiamente dicho será no acotado o infactible.

Un segundo método que se podrı́a utilizar para problemas cuya región factible es
finita siempre que ésta sea cerrada o acotada (contiene los enteros de la región factible
del problema relajado) consistirı́a en probar con todos los puntos de la región factible y
tomar aquel que optimice la función objetivo. Este método es intratable con un número
de variables no demasiado grande.
Como ya se ha indicado ninguno de los dos métodos anteriores es satisfactorio en
tanto en cuanto puede dar soluciones infactibles o ser intratable por su magnitud. Existen
fundamentalmente dos métodos de resolución de problemas de programación entera: el
algoritmo de ramificación y acotación (Branch and Bound) y el método de los planos
de corte de Gomory. Ambos métodos son algoritmos que van añadiendo restricciones al
problema relajado inicial con la intención de acotar la solución.

3.6.2. Método de ramificación y acotación.

En la práctica, la mayorı́a de los problemas de programación entera se resuelven mediante
el uso de la técnica de ramificar y acotar.
Los métodos de ramificar y acotar encuentran la solución óptima para un problema de
programación entera mediante la enumeración eficiente de los puntos en la región factible.
Antes de explicar cómo funciona la ramificación y el acotamiento, es necesario hacer
la siguiente observación: si se resuelve un problema de programación entera mediante la
relajación de un problema de programación lineal y se obtiene una solución en la cual
todas las variables son números enteros, entonces la solución óptima de la relajación de
programación lineal será también la solución óptima de programación entera.
Para darse cuenta de la validez de esta observación, considérese el siguiente problema
de programación entera:

M ax z = 3x1 + 2x2
s.a. 2x1 + x2 ≤ 6
x1 , x2 , ≥ 0; x1 , x2 entero

La solución óptima, considerándolo un problema de programación lineal para esta pro-

gramación entera, es:
x1 = 0, x2 = 6, z = 12
Esta solución da valores enteros a cada variable. La observación anterior implica que
también es la solución óptima para el problema de programación entera.
Obsérvese que la región factible para la programación entera es un subconjunto de
todos los puntos en la región factible de la relajación por programación lineal.

78 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

Ası́, el valor óptimo de z para la programación entera no puede ser mayor que el valor
óptimo de z para la relajación de programación lineal, es decir,

zopt (P L) ≥ zopt (P LE)

Esto significa que el valor óptimo de z para la programación entera debe ser z ≤ 12. Pero
el punto
x1 = 0, x2 = 6, z = 12
es factible para la programación entera y tiene z = 12. Por tanto, debe ser óptimo para
la programación entera.
En forma resumida, los pasos del algoritmo Ramificar y Acotar, para un problema de
maximización, son:

Algoritmo:
Paso 0. (Inicialización). Consiste en resolver el problema relajado asociado. Si la solu-
ción óptima es entera, dicha solución es la del problema entero. En caso contrario
determinar una cota inferior para el valor óptimo del objetivo bien tomando −∞
o, si es posible el valor de la función objetivo en algún punto factible del problema
entero.

Paso 1. (Ramificación). Mediante una regla de ramificación, seleccionar un subconjunto

(o subproblema) de soluciones factibles que quede sin sondear (inicialmente la del
problema relajado) y una componente no entera de la solución del subproblema en
cuestión. Hacer una partición en el subconjunto elegido en dos subconjuntos más
pequeños, obtenidos al añadir restricciones que excluyan los valores fraccionarios de
la componente elegida.

Paso 2. (Acotación). Para cada nuevo subconjunto, determinar una cota superior para
el valor del objetivo del problema entero.

Paso 3. (Sondeo). Analizar los subconjuntos que puedan contener la solución óptima y
considerar como terminales aquellos que:

1. El subconjunto es infactible
2. La cota superior es menor que la cota inferior
3. La cota superior se alcanza en un punto factible para el problema entero y la
cota superior es mayor que la inferior. En este caso hacemos la cota inferior
igual a la superior y volvemos al paso 3 para sondear otros subconjuntos.

Paso 4. (Convergencia). Si todos los subconjuntos son terminales, parar y la solución

viene dada por el óptimo del paso anterior. En otro caso ir al paso 1.

Eva Ma Ramos Ábalos 79

3.6. Programación entera

En el algoritmo hay dos puntos a tener en cuenta:

La selección de la variable entera sobre la que ramificar. Hay varias recomendaciones:

seleccionar la variable de menor ı́ndice con valor no entero, o bien seleccionar la
variable con mayor valor no entero o establecer una jerarquı́a de variables siguiendo
criterios económicos.

La elección de un subconjunto no sondeado para la ramificación. En este caso hay

dos posibilidades: la regla de la mejor cota y la regla de la cota más reciente. La
primera consiste en tomar el subconjunto con mayor valor de la función objetivo
(para problemas de maximización), es decir, la mayor cota superior. La segunda
selecciona el subconjunto surgido más recientemente y que no haya sido sondeado.

Ejemplo 32. Considere el siguiente problema de programación lineal entera:

M ax z = 5x1 + 4x2
s.a. x1 + x2 ≤ 5
10x1 + 6x2 ≤ 45
x1 , x2 , ≥ 0; x1 , x2 y enteras

El espacio de soluciones de PL asociado, SP0, se define por cancelación de las restricciones

enteras. La solución óptima SP0 da

x1 = 3, 75, x2 = 1, 25, z = 23, 75

El procedimiento ramificar y acotar se basa en tratar sólo con el problema PL. Como
la solución óptima no satisface la necesidad de valores enteros, el algoritmo de ramificar
y acotar exige modificar el espacio de soluciones PL de forma que nos permita identificar,
finalmente la solución óptima del problema de programación lineal entera. Primero, se-
leccionamos una de las variables cuyo valor corriente en la solución óptima SP0 infringe
el requisito de valor entero. Seleccionando x1 = 3, 75 arbitrariamente, observamos que
la región (3 < x1 < 4) del espacio de soluciones SP0 no puede, por definición, incluir
ninguna solución factible del problema de programación lineal entera. Entonces, pode-
mos modificar el espacio de soluciones de PL eliminando esta región no prometedora, lo
que, en realidad, equivale a reemplazar el espacio original SP0 por dos subproblemas de
programación lineal, los SP1 y SP2, definidos de la manera siguiente:

1. Espacio SP1 = espacio SP0 + (x1 ≤ 3)

2. Espacio SP2 = espacio SP0 + (x1 ≥ 4)

Los dos espacios contienen los mismos puntos enteros factibles del modelo programa-
ción lineal entera. Esto significa que, desde el punto de vista del problema original de

80 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

programación lineal entera, tratar con SP1 y SP2 es igual que tratar con el subproblema
original SP0. La diferencia principal es que la selección de las nuevas restricciones de
acotamiento (x1 ≤ 3 y x1 ≥ 4) mejorarán la oportunidad de forzar a los puntos extre-
mos óptimos de SP1 y SP2 hacia la satisfacción del requisito de valor entero. Además, el
hecho de que las restricciones de acotamiento estén en la vecindad inmediata del óptimo
continuo del SP0 incrementará las posibilidades de producir buenas soluciones enteras.
Las nuevas restricciones (x1 ≤ 3 y x1 ≥ 4) son mutuamente excluyentes; SP1 y SP2
deben tratarse como dos problemas de programación lineal separados. Esto da lugar al
método de ramificar y acotar. En efecto, ramificar significa subdividir un espacio de so-
luciones en subespacios mutuamente excluyentes. Las ramas asociadas se definen por las
restricciones (x1 ≤ 3 y x1 ≥ 4), donde x1 se denomina variable de ramificación. La so-
lución óptima de la programación lineal entera debe encontrarse en el SP1 o en el SP2.
Sin embargo, en ausencia del espacio gráfico de soluciones, no se sabe dónde puede en-
contrarse la solución óptima, por lo que la única opción es investigar ambos problemas.
Se hace esto trabajando con un problema SP1 o SP2. Escojamos arbitrariamente al SP1,
asociado x1 ≤ 3.
Ejemplo 33. En efecto, debemos resolver el siguiente problema:

M ax z = 5x1 + 4x2
s.a. x1 + x2 ≤ 5
10x1 + 6x2 ≤ 45
x1 ≤ 3
x1 , x 2 , ≥ 0

Como se indicó antes, el SP1 es el mismo que el SP0 con la restricción adicional de
acotamiento superior x1 ≤ 3. Ası́, podemos aplicar el método sı́mplex para resolver el
problema. Esto da la nueva solución óptima:

x1 = 3, x2 = 2, z = 23

Como esta solución satisface el requisito de valor entero, se dice que SP1 está agotado,
lo que significa que el SP1 no puede producir ninguna solución mejor de la programación
lineal entera y no necesita investigarse más a fondo. Determinar una solución factible
entera en una etapa temprana de los cálculos es crucial para incrementar la eficiencia del
algoritmo ramificar y acotar. Tal solución fija una cota inferior al valor objetivo óptimo
del problema programación lineal entera, que, a su vez, se puede utilizar para descartar
automáticamente cualesquiera subproblemas no explorados (como el SP2) que no dan una
mejor solución entera. En términos de nuestro ejemplo, el SP1 produce la cota inferior
z = 23. Esto significa que cualquier solución entera mejorada debe tener un valor de z
mayor que 23. Sin embargo, como la solución óptima del problema SP0 (original) tiene

Eva Ma Ramos Ábalos 81

3.6. Programación entera

z = 23, 75 y como todos los coeficientes de la función objetivo son enteros, se infiere que
ningún subproblema que proceda del SP0 puede producir un valor de z mejor que 23. En
consecuencia, sin ulterior investigación, podemos descartar al SP2. En este caso se dice
que el SP2 está agotado porque no puede dar una mejor solución entera.
Del análisis anterior vemos que un subproblema está agotado si se satisface una de las
siguientes condiciones:
i) El subproblema da una solución factible entera del problema programación lineal
entera.
ii) El subproblema no puede dar una mejor solución que la mejor cota inferior disponible
(valor de z) del problema programación lineal entera. (Un caso especial de esta
condición es que el subproblema no tendrá ninguna solución factible.)
Si la función objetivo ha de minimizarse, el procedimiento es el mismo, excepto que
se emplean cotas superiores. Ası́, el valor de la primera solución entera se vuelve una
cota superior para el problema y se eliminan los SPi cuando sus valores z de primera
aproximación son mayores que la cota superior actual.

Consideraciones para los cálculos

Siempre se realizan las bifurcaciones a partir de aquel programa que parece estar más cerca
del valor óptimo. Cuando existen varios candidatos para continuar las bifurcaciones, se
selecciona aquel que tenga el mayor valor z si se va a maximizar la función objetivo, o
aquel que tenga el menor valor z si se va a minimizar la función objetivo.
Las restricciones adicionales se agregan una a una. Si una primera aproximación incluye
a más de una variable no entera, las nuevas restricciones se imponen a aquella variable
que está más lejos de ser un entero; esto es, aquella variable cuya parte fraccionaria está
más cerca de 0.5. En caso de empate, se selecciona arbitrariamente una de las variables.
Finalmente, es posible que un programa entero o un programa lineal tengan más de
una solución óptima.
Ejemplo 34.
M ax z = 4x1 + 3x2 + 2x3
s.a. 5x1 − 2x2 + 3x3 ≤ 10
3x1 + 3x2 − 2x3 ≤ 7
−x1 + 2x2 − x3 ≤ 9
x1 , x2 , x3 ≥ 0 y enteras
Comenzamos por resolver el problema lineal relajado (PR) mediante el método sim-
plex, cuya solución óptima es:
x1 = 0, x2 = 8,2, x3 = 8,8 zP R = 42,2

82 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

Esta solución tiene componentes que no son enteras, por lo tanto no es solución óptima
para el PE y el proceso debe continuar. Se establece como cota inferior para el valor
objetivo z1 = −∞.

Comenzamos a ramificar, comenzando de forma arbitraria por x2 . Esto nos lleva a

añadir dos nuevas restricciones

x 2 ≤ 8 y x2 ≥ 9

formándose de esta manera dos subproblemas del PR, PL1 que surge del PR más las
restricción x2 ≤ 8 y PL2 que surge del PR más las restricción x2 ≥ 9. Tales problemas
con sus respectivas restricciones son:

PL2 PL3

M ax z = 4x1 + 3x2 + 2x3 M ax z = 4x1 + 3x2 + 2x3

s.a. 5x1 − 2x2 + 3x3 ≤ 10 s.a. 5x1 − 2x2 + 3x3 ≤ 10
3x1 + 3x2 − 2x3 ≤ 7 3x1 + 3x2 − 2x3 ≤ 7
−x1 + 2x2 − x3 ≤ 9 −x1 + 2x2 − x3 ≤ 9
x2 ≤ 8 x2 ≥ 9
x1 , x 2 , x 3 ≥ 0 x1 , x 2 , x 3 ≥ 0

SOLUCIÓN: SOLUCIÓN:
x1 = 0,05, x2 = 8, x3 = 8,58 Infactible
z = 41,37

Sondeamos estos subconjuntos para ver si puede continuar la ramificación o bien son
terminales. El problema PL3 es infactible, por lo que ya es terminal. Para el subproblema
PL2 se tiene: no es infactible, z = 41,37 > −∞ y la solución óptima no se alcanza en un
punto con valores enteros. Por tanto no es terminal, y hay que volver a ramificar. Vamos
a ramificar sobre la primera componente, añadiendo las restricciones x1 ≤ 0 y x1 ≥ 0
formándose de esta manera dos subproblemas del PL2, PL4 que surge del PL2 más las
restricción x1 ≤ 0 y PL5 que surge del PL2 más las restricción x1 ≥ 0. Tales problemas
con sus respectivas restricciones son:

Eva Ma Ramos Ábalos 83

3.6. Programación entera

PL4 PL5

M ax z = 4x1 + 3x2 + 2x3 M ax z = 4x1 + 3x2 + 2x3

s.a. 5x1 − 2x2 + 3x3 ≤ 10 s.a. 5x1 − 2x2 + 3x3 ≤ 10
3x1 + 3x2 − 2x3 ≤ 7 3x1 + 3x2 − 2x3 ≤ 7
−x1 + 2x2 − x3 ≤ 9 −x1 + 2x2 − x3 ≤ 9
x2 ≤ 8 x2 ≤ 8
x1 ≤ 0 x1 ≥ 1
x1 , x 2 , x 3 ≥ 0 x1 , x 2 , x 3 ≥ 0

SOLUCIÓN: SOLUCIÓN:

x1 = 0, x2 = 8, x3 = 8,67 x1 = 1, x2 = 4,4, x3 = 4,6

z = 41,33 z = 26,4

Estos problemas no son terminales ya que no son infactibles, su valor óptimo respec-
tivo no son valores enteros y en ambos casos el valor de z es mayor que −∞. Nuevamente
se ramifica. Tomando la regla de la mejor cota, se ramifica sobre el problema PL4, y
sobre la variable x3 (no hay otra elección), añadiendo las restricciones x3 ≤ 8 y x3 ≥ 9
formándose de esta manera dos subproblemas del PL4, PL6 que surge del PL4 más las
restricción x3 ≤ 8 y PL7 que surge del PL4 más las restricción x3 ≥ 9. Tales problemas
con sus respectivas restricciones son:

PL6 PL7

M ax z = 4x1 + 3x2 + 2x3 M ax z = 4x1 + 3x2 + 2x3

s.a. 5x1 − 2x2 + 3x3 ≤ 10 s.a. 5x1 − 2x2 + 3x3 ≤ 10
3x1 + 3x2 − 2x3 ≤ 7 3x1 + 3x2 − 2x3 ≤ 7
−x1 + 2x2 − x3 ≤ 9 −x1 + 2x2 − x3 ≤ 9
x2 ≤ 8 x2 ≤ 8
x1 ≤ 0 x1 ≤ 0
x3 ≤ 8 x3 ≥ 9
x1 , x 2 , x 3 ≥ 0 x1 , x 2 , x 3 ≥ 0

SOLUCIÓN: SOLUCIÓN:

x1 = 0, x2 = 7,67, x3 = 8 Infactible

z = 39

84 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

El problema PL7 es infactible y por lo tanto terminal. El subproblema PL6 no es

terminal, ya que no verifica ninguna de las condiciones anteriores. Se elige otro subpro-
blema para ramificar entre PL5 y PL6, eligiendo PL6 por la regla de la mejor cota (tiene
valor más alto su cota superior). Elegimos para ramificar la variable x2 , añadiendo las
restricciones x2 ≤ 7 y x2 ≥ 8 formándose de esta manera dos subproblemas del PL6, PL8
que surge del PL6 más las restricción x2 ≤ 7 y PL9 que surge del PL6 más las restricción
x2 ≥ 8. Tales problemas con sus respectivas restricciones son:

PL8 PL9

M ax z = 4x1 + 3x2 + 2x3 M ax z = 4x1 + 3x2 + 2x3

s.a. 5x1 − 2x2 + 3x3 ≤ 10 s.a. 5x1 − 2x2 + 3x3 ≤ 10
3x1 + 3x2 − 2x3 ≤ 7 3x1 + 3x2 − 2x3 ≤ 7
−x1 + 2x2 − x3 ≤ 9 −x1 + 2x2 − x3 ≤ 9
x2 ≤ 7 x2 ≤ 8
x1 ≤ 0 x2 ≥ 8 ⇒ x2 = 8
x3 ≤ 8 x1 ≤ 0
x1 , x 2 , x 3 ≥ 0 x3 ≤ 8
x1 , x 2 , x 3 ≥ 0
SOLUCIÓN:
SOLUCIÓN:
x1 = 0, x2 = 7, x3 = 8
Infactible
z = 37
Ambos problemas son terminales, el PL9 por ser infactible y PL8 ya que z = 37 se
alcanza en el punto x = (0, 7, 8) que es factible para el PE y además se verifica la condición
de que z = 37 > −∞. Se sondean los problemas que se habı́an dejado sin ramificar, en
este caso únicamente PL5, para el que se habı́a obtenido un z = 26,4 < 37, por lo tanto
PL5 es terminal.
Como todos los subproblemas han sido sondeados, se da la convergencia y el algoritmo
para, siendo la solución óptima del PE

x∗ = (0, 7, 8) con z = 37

Nota:
Cuando se trata de un problema de programación entera mixta, el algoritmo de ramifi-
cación y acotación es aplicable, salvo que en este caso no se ramifica sobre variables que
son reales. En todo caso la solución obtenida será óptima para el programa mixto, ya que
las variables reales aparecen en el problema lineal relajado y en todos los subproblemas
subsecuentes.

Eva Ma Ramos Ábalos 85

3.6. Programación entera

3.6.3. Programación 0-1

Un tipo de problema de programación entera de gran interés práctico es aquel en el que
las variables de decisión sólo pueden tomar valores 0 o 1. Para este tipo de problemas
el método de ramificación y acotación es válido pero se puede aplicar de manera más
eficiente.
Para la aplicación del algoritmo es necesario de los coeficientes de las variables de la
función objetivo estén ordenadas y sean positivos (0 ≤ c1 ≤, . . . , cn ). En caso de que el
problema no verifique este requerimiento, se puede efectuar un cambio de variable que lo
permita, que es el siguiente:

{
xj cj > 0
yi =
1 − x j cj < 0
tras ordenar las variables originales de manera creciente de sus coeficientes en valor ab-
soluto.
Ejemplo 35.
M ax z = 4x1 − 3x2 − 2x3 + x4
s.a x1 + x2 + 2x3 − 3x4 ≤ 4
2x1 − 4x2 + x3 + x4 ≤ −1
2x1 + x2 + x3 ≤ 3
xj ∈ {0, 1}∀j

Ordenamos los sumandos de la función objetivo de manera que los coeficientes queden
en orden creciente de magnitud (ignorando su signo):
z = x4 − 2x3 − 3x2 + 4x1
Se hace el cambio de variable
x4 = y 1 , x 3 = 1 − y2 , x2 = 1 − y3 , x1 = y4
Se hacen las sustituciones en la función objetivo y en las restricciones:
M ax z = y1 + 2y2 + 3y3 + 4y4 − 5
s.a −3y1 − 2y2 − y3 + y4 ≤ 1
y1 − y2 + 4y3 + 2y4 ≤ 2
−y2 − y3 + 2y4 ≤ 1
yj ∈ {0, 1}∀j

86 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

El algoritmo de ramificación y acotamiento para los problemas 0 − 1 (con coeficientes

de la función objetivo ordenados de manera creciente) se describe del siguiente modo:

Algoritmo:

Paso 0. (Inicialización). Probar si x = 1 = (1, . . . , 1)′ es factible para el problema entero.

En caso afirmativo ya se tiene la solución óptima. En caso contrario determinar una
cota inferior zl para el valor óptimo del objetivo tomando el valor de la función
objetivo en el vector cero (x = 0 = (0, . . . , 0)′ ) y una cota superior zs tomando el
valor de la función objetivo en el vector xs = (0, 1, . . . , 1)′ . Si este último vector es
factible, parar y ésta será la solución óptima, en otro caso hacer k = 1 e ir al paso
siguiente.

Paso 1. (Ramificación). Mediante una regla de ramificación, seleccionar un subconjunto

(o subproblema) de soluciones factibles que quede sin sondear (inicialmente la del
problema 0-1) y hacer una partición en el subconjunto elegido en dos subconjuntos
más pequeños, obtenidos al añadir las restricciones xk = 0 y xk = 1.

Paso 2. (Acotación). Para cada nuevo subconjunto hacer xs a la compleción que tiene
su k + 1 primera componente 0 y el resto 1. A partir de xs , determinar una cota
superior zs para el valor del objetivo sobre ese subconjunto.

Paso 3. (Sondeo). Analizar cada subconjunto comenzando por aquel que tenga mayor
cota superior y considerar como terminales aquellos que:

1. Hay al menos una restricción que no la verifica ninguna compleción del sub-
conjunto.
2. zs ≤ zl
3. xs es factible. En este caso hacemos la cota inferior igual a la superior zl = zs
y volvemos al paso 3 para sondear otros subconjuntos.

Paso 4. (Convergencia). Si todos los subconjuntos son terminales, parar y la solución

viene dada por el óptimo del paso anterior. En otro caso hacer k = k + 1 e ir al paso
1.
Ejemplo 36. Consideremos el siguiente problema

M ax z = 2x1 + 4x2 + 4x3

s.a 5x1 − 2x2 + 3x3 ≤ 5
3x1 + 4x2 − x3 ≤ 2
xj ∈ {0, 1}∀j

Eva Ma Ramos Ábalos 87

3.6. Programación entera

En primer lugar se considera el problema relajado, pero en este caso, en vez de pres-
cindir de las condiciones de que las variables sean enteras, se prescinde de todas las
restricciones del problema, excepto de las correspondientes a que las variables sean 0 o 1,
de forma que el conjunto factible para este problema es
M ax z = 2x1 + 4x2 + 4x3
s.a xj ∈ {0, 1}∀j

El problema es fácil de resolver ya que al ser todos los coeficientes no negativos el

máximo valor del objetivo se obtiene para el punto x = (1, 1, 1), con un valor z = 10.
Si tal punto es factible para el problema entero, es decir, satisface las restricciones del
problema original, tal punto será la solución óptima. En este caso no se verifican ninguna
de las restricciones, por lo que hay que aplicar el algoritmo. Se comienza determinando
una cota inferior para el objetivo, en este caso la cota será z = 0 que es la que se obtiene
con x1 = 0, x2 = 0 y x3 = 0.
Se comienza a ramificar, comenzando arbitrariamente por x1 y pasamos a determinar
una cota superior del valor del objetivo para los subproblemas obtenidos en la ramifica-
ción, que en nuestro ejemplo son:

PR1 PR2

M ax z = 2x1 + 4x2 + 4x3 M ax z = 2x1 + 4x2 + 4x3

s.a. 5x1 − 2x2 + 3x3 ≤ 10 s.a. 5x1 − 2x2 + 3x3 ≤ 10
x1 , x 2 , x 3 ≥ 0 x1 , x 2 , x 3 ≥ 0
x1 = 0 x1 = 1
Calculamos una cota superior para cada subproblema, considerando el valor que toma
la variable sobre la que se ha ramificado en la nueva restricción que se ha añadido y para
el resto de variables le asignamos el valor 1. De esta forma, tenemos:
P R1 ⇒ x = (0, 1, 1) ⇒ z = 4x2 + 4x3 ⇒ cota superior = 8
P R2 ⇒ x = (1, 1, 1) ⇒ z = 2x1 + 4x2 + 4x3 ⇒ cota superior = 10
A continuación se comprueba si los problemas son terminales (Paso 3).
1. Para ello vemos sin son infactibles. Empezamos con PR1, en el que tenemos x1 = 0
y las posibles soluciones son:
x1 x2 x3
0 0 0
0 1 0
0 0 1
0 1 1

88 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

Si se toma únicamente x1 = 0, la llamaremos solución parcial, ya que quedan sin

precisar los valores de las variables x2 y x3 . Cuando se especifiquen valores para estas
variables, decimos que se tiene una compleción de la solución parcial, y si además
ésta es factible, se dice compleción factible.
Tratamos ahora de ver si hay compleciones factibles para la solución parcial x1 = 0
en PR1. Para ello se comprueban si se verifican las restricciones con cada compleción.
PR1 no es infactible, ya que existen compleciones de la solución parcial x = (0, −, −)
que satisfacen las restricciones.
Para PR2 las posibles soluciones son:

x1 x2 x3
1 0 0
1 1 0
1 0 1
1 1 1

PR2 es infactible, ya que no existen compleciones de la solución parcial x = (1, −, −)

que verifiquen las restricciones, por lo tanto el subproblema PR2 es terminal. Com-
probamos las siguientes condiciones para PR1.
2. zs = 8 > zl = 0
3. Debemos comprobar si el punto x = (0, 1, 1) utilizado para calcular la cota superior
para PR1 es factible. En este caso no lo es, ya que no verifica la segunda restricción.
Por lo tanto podemos concluir que PR1 no es terminal. Pasamos a ramificar este problema
sobre la variable x2 (se elige arbitrariamente).

PR3 PR4

M ax z = 2x1 + 4x2 + 4x3 M ax z = 2x1 + 4x2 + 4x3

s.a. 5x1 − 2x2 + 3x3 ≤ 10 s.a. 5x1 − 2x2 + 3x3 ≤ 10
x1 , x 2 , x 3 ≥ 0 x1 , x 2 , x 3 ≥ 0
x1 = 0, x2 = 0 x1 = 0, x2 = 1
Calculamos una cota superior para cada subproblema, considerando el valor que toman
las variables sobre las que se han ramificado en la nueva restricción que se ha añadido y
para el resto de variables le asignamos el valor 1. De esta forma, tenemos:
P R3 ⇒ x = (0, 0, 1) ⇒ z = 4x3 ⇒ cota superior = 4
P R4 ⇒ x = (0, 1, 1) ⇒ z = 4x2 + 4x3 ⇒ cota superior = 8
A continuación se comprueba si los problemas son terminales (Paso 3).

Eva Ma Ramos Ábalos 89

3.6. Programación entera

1. Para ello vemos sin son infactibles. Empezamos con PR3, en el que tenemos x1 = 0
y x2 = 0 . Las posibles soluciones son:

x1 x2 x3
0 0 0
0 0 1

PR3 no es infactible, ya que las compleciones de la solución parcial x = (0, 0, −)

satisfacen las restricciones.
Para PR4 las posibles soluciones son:

x1 x2 x3
0 1 0
0 1 1

PR4 es infactible, ya que no existen compleciones de la solución parcial x = (0, 1, −)

que verifiquen las restricciones, por lo tanto el subproblema PR4 es terminal. Com-
probamos las siguientes condiciones para PR3.

2. zs = 4 > zl = 0

3. Debemos comprobar si el punto x = (0, 0, 1) utilizado para calcular la cota superior

para PR1 es factible. En este caso no lo es, ya que no verifica la segunda restricción.
Tal punto es factible para F y será una posible solución del PE y zl = 4 es la nueva
cota inferior.

Como ya todos los subproblemas han quedado sondeados y son terminales, la solución
óptima es la correspondiente a PR3, es decir

x∗ = (0, 0, 1) z ∗ = 4

Ejemplo 37. Apliquemos el algoritmo al siguiente problema:

M ax z = x1 + 2x2 + 3x3 + 4x4

s.a −3x1 − 2x2 − x3 + x4 ≤ 1
x1 − x2 + 4x3 + 2x4 ≤ 2
−x2 − x3 + 2x4 ≤ 1
xj ∈ {0, 1}∀j

90 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

Paso 0. Comprobamos que x = (1, 1, 1, 1) es infactible (no verifica la segunda restric-

ción). Se determina la cota inferior para el valor objetivo, dada por zl = z((0, 0, 0, 0)) = 0
y una cota superior dada por el valor de la función objetivo en xs = (0, 1, 1, 1), y ası́
zs = z((0, 1, 1, 1)) = 2 + 3 + 4 = 9. Como xs es infactible, hacemos k = 1 y vamos al paso
1.
Paso 1. Ramificación sobre x1 , obteniendo los subproblemas PR1 con x1 = 0 y PR2
con x1 = 1. Ambos no son terminales y ramificamos inicialmente sobre PR2 por tener
mayor cota superior, obteniendo los subproblemas PR3 con x2 = 0 y PR4 con x2 = 1. El
subproblema PR4 es terminal ya que el punto (1, 1, 0, 1) es factible, y ası́ la cota inferior
se actualiza y pasa a ser zl = 7. Se sondea el subproblema PR3 que es terminal ya que
zs = 5 < zl = 7.
Finalmente se vuelve a PR1 para ramificar sobre él. Sin embargo, como hemos ac-
tualizado la cota inferior, lo sondeamos nuevamente y vemos que ya es terminal ya que
zs = 7 ≤ zl = 7.
Por tanto la solución óptima es x∗ = (1, 1, 0, 1) con z ∗ = 7.

Figura 3.1: Soluciones múltiples

Eva Ma Ramos Ábalos 91

3.7. Ejercicios

3.7. Ejercicios
1. Expresa los problemas siguientes en forma estándar y canónica:

a)Max. x+y b)Max. 2x + 3y + z c)Min. x+y

s.a. −x + y = 2 s.a. 4x + 3y + z ≤ 20 s.a. −x + y ≤ 2
x + 2y ≤ 6 x + y ≤ 20
2x + y ≥ 6 x ≥ 0, y ≤ 0
x ≥ 0, y ≤ 0

2. Resuelve mediante el método sı́mplex el siguiente problema.

Max. −x + y
s.a. −2x + y ≤ 4
x+y ≤1
y≥0

3. Resuelve el problema siguiente. Indica las soluciones óptimas y el valor de la función

objetivo en cada una de ellas.

Opt. x − 2y + 3z
s.a. x + 2y + z ≤ 4
2x + y − z ≤ 2
x, y, z ≥ 0

4. Resolver:
a) Max. 3x + 2y + z b) Max. 3x + y + 4z
s.a. 2x − 3y + 2z ≤ 3 s.a. 6x + 3y + 5z ≤ 25
−x + y + z ≤ 5 3x + 4y + 5z ≤ 20
x, y, z ≥ 0 x, y, z ≥ 0

5. Cierto fabricante produce sillas y mesas para lo que requiere la utilización de dos
secciones de producción, la sección de montaje y la sección de pintura. La producción
de una silla requiere una hora de trabajo en la sección de montaje y dos horas en
la de pintura. Por su parte, la fabricación de una mesa precisa de tres horas en la
sección de montaje y una hora en la de pintura.
La sección de montaje solo puede estar nueve horas diarias en funcionamiento, mien-
tras que la de pintura solo ocho horas. El beneficio que se obtiene produciendo mesas
es el doble que produciendo sillas.
¿Cuál debe ser la producción diaria de mesas y sillas que maximice el beneficio?

92 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

6. Un agricultor posee una parcela de 640 m2 para dedicarla al cultivo de árboles fru-
tales: naranjos, perales y manzanos. Se pregunta de que forma repartirá la superficie
de la parcela entre las tres variedades para conseguir el máximo beneficio sabiendo
que:

Cada naranjo precisa como mı́nimo de 16 m2 , cada peral de 4 m2 y cada

manzano 8 m2 .
Dispone de un total de 900 horas de trabajo por año (150 jornales), precisando
cada naranjo de 30 horas por año, cada peral de 5 horas por año y cada manzano
de 10 horas por año.
Los beneficios unitarios son de 50, 25, 20 unidades monetarias por cada naranjo,
peral y manzano respectivamente

7. La empresa A se dedica al montaje de motocicletas de 500, 250, 125 y 50 c.c. Posee

una planta que está estructurada en cuatro departamentos: fabricación de los chasis,
pintura, montaje y el departamento de calidad.
Las horas de mano de obra que necesita cada uno de los modelos de motocicletas
en los diferentes departamentos son las siguientes:

Chasis Pintura Montaje Control calidad

500 c.c. 8 6 8 4
250 c.c. 6 3 8 2
125 c.c. 4 2 6 2
50 2 1 4 2

La distribución de los trabajadores es la siguiente: para la fabricación de chasis se

dispone de 25 trabajadores, en el departamento de pintura de 18, el de montaje de
30 y el de control de calidad de 10. Todos los trabajadores realizan una jornada
laboral de 8 horas.
Si el margen de beneficio de cada uno de los modelos es de 200000, 140000, 80000 y
de 40000 pesetas respectivamente, ¿cuál ha de ser la combinación óptima de moto-
cicletas a producir para que el beneficio sea máximo?

8. Resolver los siguientes problemas utilizando el método de la M-grande:

a) Max. 3x1 + 6x2 b) Max. 4,5x1 + 3x2 + 1,5x3 c) Min. x1 + x2

s.a. x1 + 4x2 ≤ 5 s.a. x1 + 2x2 − x3 ≤ 4 s.a. x1 + x2 ≤ 1
−x1 + 3x2 ≤ −2 2x1 − x2 + x3 = 8 4x1 + 2x2 ≥ 6
x1 − 5x2 ≥ −2 x 1 − x2 ≤ 6 x1 , x 2 ≥ 0
x1 , x 2 ≥ 0 x1 , x 2 , x 3 ≥ 0

Eva Ma Ramos Ábalos 93

3.7. Ejercicios

9. Resolver utilizando el método de las dos fases:

a) Min. 20x1 + 25x2 b) Max. 4x1 + 3x2
c) Max. x1 − 2x2 + 3x3
s.a. 2x1 + 3x2 ≥ 18 s.a. 3x1 + 4x2 ≤ 12
s.a. x1 + x2 + x3 = 6
x1 + 3x2 ≥ 12 x1 + x2 ≥ 4
x3 ≤ 2
4x1 + 3x2 ≥ 24 4x1 + 2x2 ≤ 8
x1 , x 2 , x 3 ≥ 0
x1 , x 2 ≥ 0 x1 , x 2 ≥ 0

e) Max. x1 + 2x2
d) Max. x1 + x2 + 10x3
s.a. x1 + x2 = 4
s.a. x2 + 4x3 = 2
2x1 − 3x2 = 3
−2x1 + x2 − 6x3 = 2
3x1 − x2 = 8
x1 , x 2 , x 3 ≥ 0
x1 , x 2 ≥ 0

10. Dados los siguientes problemas primales, encontrar sus problemas duales asociados:
a) Max. 6x1 + 4x2 b) Max. 4,5x1 + 3x2 + 1,5x3 c) Min. 6x1 + 4x2
s.a. x1 ≤ 700 s.a. x1 + 2x2 − x3 ≤ 4 s.a. x1 ≤ 700
3x1 + x2 ≤ 2400 2x1 − x2 + x3 = 8 3x1 + x2 ≥ 2400
x1 + 2x2 ≤ 1600 x 1 − x2 ≤ 6 x1 + 2x2 ≤ 1600
x1 , x 2 ≥ 0 x1 , x 2 , x 3 ≥ 0 x1 , x 2 ≥ 0

d) Max. 4,5x1 + 3x2 + 1,5x3 e) Min. 6x1 + 4x2

s.a. x1 + 2x2 − x3 ≤ 4 s.a. x1 ≤ 700
2x1 − x2 + x3 ≤ 8 3x1 + x2 ≥ 2400
x1 − x2 ≤ 6 x1 + 2x2 = 1600
x1 , x3 ≥ 0, x2 sin restricciones x1 ≥ 0, x2 sin restricciones

11. Dados los siguientes problemas de programación lineal

a) Max. 4x1 + 2x2 + 3x3 b) Max. x1 + x2 + x3 + x4
s.a. 2x1 + 3x2 + x3 ≤ 12 s.a. x1 + 2x2 − x3 + 3x4 ≤ 12
x1 + 4x2 + 2x3 ≤ 10 x1 + 3x2 + x3 + 2x4 ≤ 8
3x1 + 2x2 + x3 ≤ 10 2x1 − 3x2 − x3 + 2x4 ≤ 7
x1 , x 2 , x 3 ≥ 0 x1 , x 2 , x 3 , x 4 ≥ 0

c) Max. 2x1 + x2 + 3x3

s.a. 2x1 − x2 + 3x3 ≤ 6
x1 + 3x2 + 5x3 ≤ 10
2x1 + x3 ≤ 7
x1 , x 2 , x 3 ≥ 0
Encontrar la solución dual utilizando el principio de holgura complementaria.

94 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

12. Utilizar el algoritmo dual del simplex para resolver los siguientes problemas:

a) Min. x1 + 2x2 b) Min. x1 + x2 + x 3 + x4

s.a. x1 + x2 ≥ 4 s.a. 2x1 + x4 ≥ 250
2x1 + x2 ≥ 6 3x2 ≥ 1000
x1 , x 2 ≥ 0 3x2 + 10x3 + 6x4 ≥ 750
x1 , x 2 , x 3 , x 4 ≥ 0

c) Max. −4x1 − 6x2 d) Min. 6x1 + 7x2 + 4x3 + 5x4

s.a. 3x1 + x2 ≥ 2400 s.a. 6x1 − 5x2 + 4x3 + x4 ≥ −5
x1 + 2x2 ≥ 1600 −x2 + 6x3 ≤ −7
x1 , x 2 ≥ 0 −4x1 + 2x3 ≥ 3
x1 , x 2 , x 3 , x 4 ≥ 0

13. Obtener la solución del los problemas duales asociados a partir de la tabla final del
simplex:
a) Max. x1 + x2
b) Max. 600x1 + 300x2
s.a. x1 + x2 ≤ 4
s.a. 2x1 + 1,5x2 ≤ 1200
2x1 + x2 ≤ 6
x1 + 0,25x2 ≤ 375
x1 , x 2 ≥ 0
x1 , x 2 ≥ 0

14. Dado el siguiente problema y su tabla final del Simplex,

Max. x1 + 2x2 1 2 0 0
s.a. x1 + x2 ≤ 4 VB x1 x2 s1 s2 xB
2x1 + x2 ≤ 6 2 x2 1 1 1 0 4
x1 , x 2 ≥ 0 0 s2 1 0 -1 1 2
zj − cj 1 0 2 0 8

Realizar el análisis de sensibilidad:

a) Respecto a los coeficientes de las variables no básicas.

b) Respecto a los coeficientes de las variables básicas.
c) Respecto a los recursos.
d ) Respecto a los coeficientes tecnológicos no básicos.
e) Incluyendo la restricción 4x1 + x2 ≤ 5.
f ) Incluyendo la restricción x1 + 4x2 ≤ 3.

Eva Ma Ramos Ábalos 95

3.7. Ejercicios

15. Dado el siguiente problema y su tabla final del Simplex,

Max. 20x1 + 30x2 + 16x3 20 30 16 0 0

s.a. 5x1 + 3x2 + x3 ≤ 3 VB x1 x2 x3 s 1 s2 xB
x1 + 3x2 + 2x3 ≤ 4 30 x2 3 1 0 2/3 -1/3 2/3
x1 , x 2 , x 3 ≥ 0 16 x3 -4 0 1 -1 1 1
zj − cj 6 0 0 4 6 36

Realizar el análisis de sensibilidad:

a) Respecto a los coeficientes de las variables no básicas.

b) Respecto a los coeficientes de las variables básicas.
c) Respecto a los recursos.
d ) Respecto al coeficiente tecnológico a11 .

16. Dado el siguiente problema y su tabla final del Simplex,

Max. x1 + 3x3 1 0 3 0 0
s.a. x1 + 2x2 + 7x3 ≤ 4 VB x1 x2 x3 s1 s2 xB
x1 + 3x2 + x3 ≤ 5 1 x1 1 2 7 1 0 4
x1 , x 2 , x 3 ≥ 0 0 s2 0 1 -6 -1 1 1
zj − cj 0 2 4 1 0 4

Realizar el análisis de sensibilidad:

a) Respecto a los coeficientes de las variables no básicas.

b) Respecto a los coeficientes de las variables básicas.
c) Respecto al recurso b1 .
d ) Respecto al coeficiente tecnológico a22 .
e) Incorporando la nueva restricción 3x1 + 7x2 + x3 ≤ 14.
f ) Incorporando la nueva restricción 3x1 + 7x2 + x3 ≤ 7.
g) Incorporando la nueva variable x4 , de la siguiente forma:

Max. x1 + 3x3 + 4x4

s.a. x1 + 2x2 + 7x3 + x4 ≤ 4
x1 + 3x2 + x3 + 0,5x4 ≤ 5
x1 , x 2 , x 3 , x 4 ≥ 0

96 Eva Ma Ramos Ábalos

 Tema 3. Algoritmo Simplex. Dualidad. Análisis de Sensibilidad. Programación Entera.

17. Dado el siguiente problema y su tabla final del Simplex,

600 300 0 0
Max. 600x1 + 300x2
VB x1 x2 s1 s2 xB
s.a. 2x1 + 1,5x2 ≤ 1200
300 x2 0 1 1 -2 450
x1 + 0,25x2 ≤ 375
600 x1 1 0 -1/4 3/2 262.5
x1 , x 2 ≥ 0
zj − cj 0 0 150 300 292500

a) Analizar el problema incorporando la nueva variable x3 , de la siguiente forma:

Max. 600x1 + 300x2 + 200x3

s.a. 2x1 + 1,5x2 + 2x3 ≤ 1200
x1 + 0,25x2 + 0,25x3 ≤ 375
x1 , x 2 , x 3 ≥ 0

b) Analizar el problema incorporando la nueva variable x3 , de la siguiente forma:

Max. 600x1 + 300x2 + 200x3

s.a. 2x1 + 1,5x2 + x3 ≤ 1200
x1 + 0,25x2 + 0,15x3 ≤ 375
x1 , x 2 , x 3 ≥ 0

18. Resolver el siguiente problema:

Max. 5x1 + 6x2

s.a. 10x1 + 3x2 ≤ 52
2x1 + 3x2 ≤ 18
x1 , x2 ≥ 0 y enteras

19. Resolver el siguiente problema:

Max. 3x1 + x2
s.a. 5x1 + x2 ≤ 12
2x1 + x2 ≤ 8
x1 , x2 ≥ 0 y enteras

Eva Ma Ramos Ábalos 97

3.7. Ejercicios

20. Un excursionista debe determinar que objetos debe llevar consigo en la mochila para
realizar una excursión de un dı́a. Cada uno de los objetos tiene asociado un peso y
una utilidad personal para el excursionista. Los objetos que puede llevar, ası́ como
su peso y utilidad son los que se recogen en la tabla siguiente:

Objeto Peso Utilidad

Linterna 40 40
Saco 50 80
Cocina 30 10
Manta 10 10
Comida 10 4
Ropa 40 20
Varios 30 60

Sabiendo que el peso máximo que puede llevar en la mochila es de 100. Determinar
que objetos debe llevar nuestro excursionista en la mochila para que la utilidad de
los objetos sea máxima.

98 Eva Ma Ramos Ábalos