Índice general

1. Planteamiento de problemas 1
1.1. Breve historia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2. Algunos problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2. Interpretación geométrica de un problema de programación lineal 17

2.1. Restricciones redundantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2. Soluciones óptimas múltiples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3. Región de soluciones factibles no acotada . . . . . . . . . . . . . . . . . . . . . . 20
2.4. Región de soluciones factibles consistente de un solo punto . . . . . . . . . . . . . 23
2.5. Región de soluciones factibles vacía . . . . . . . . . . . . . . . . . . . . . . . . . 24

3. Fundamentos del algoritmo simplex 29

3.1. Forma canónica y forma estándar . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2. Otras representaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3. Propiedades de las soluciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4. Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.5. Puntos extremos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.6. Relaciones entre bases y puntos extremos . . . . . . . . . . . . . . . . . . . . . . 40

4. Algoritmo simplex 47
4.1. Optimalidad y factibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2. Motivación: problema del inversionista . . . . . . . . . . . . . . . . . . . . . . . . 48
4.2.1. Sistemas de ecuaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.2.2. Tablas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3. Forma explícita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.3.1. Tablas en el caso general . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3.2. Formalización de las tablas . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.4. Análisis de la forma explícita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.4.1. Pivoteo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.4.2. Soluciones óptimas finitas . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.4.3. Soluciones óptimas no acotadas . . . . . . . . . . . . . . . . . . . . . . . 65

III
 4.4.4. Soluciones óptimas alternativas . . . . . . . . . . . . . . . . . . . . . . . 66
4.5. Algoritmo simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.6. Finitud del algoritmo simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

5. Método Simplex 74
5.1. Las dos fases del método simplex y el teorema fundamental . . . . . . . . . . . . . 74
5.1.1. Fase I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.1.2. Fase II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.1.3. El teorema fundamental de la programación lineal . . . . . . . . . . . . . 78
5.2. El procedimiento del método simplex . . . . . . . . . . . . . . . . . . . . . . . . 78
5.3. Método simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

6. Método simplex con multiplicadores (revisado) 92

6.1. Revisión del algoritmo simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
6.1.1. La inversa de la matriz asociada a la base . . . . . . . . . . . . . . . . . . 92
6.1.2. Los multiplicadores simplex . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.1.3. La matriz extendida asociada a la base y su inversa . . . . . . . . . . . . . 96
6.1.4. La idea central del algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.2. Descripción matricial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.3. El procedimiento del método simplex revisado . . . . . . . . . . . . . . . . . . . . 100
6.3.1. Tabla inicial para la memoria lenta . . . . . . . . . . . . . . . . . . . . . . 101
6.3.2. Datos para cada iteración para la memoria rápida . . . . . . . . . . . . . . 102

7. Dualidad 105
7.1. Relación entre los valores de las funciones objetivo de los problemas lineales duales 107
7.2. Holguras complementarias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
7.3. Condiciones de optimalidad de Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . 119

8. Algoritmo dual simplex 126

8.1. Justificación del algoritmo dual simplex . . . . . . . . . . . . . . . . . . . . . . . 126
8.2. Algoritmo dual simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

9. Análisis de sensibilidad 133

9.1. Cambios en el vector de costos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
9.1.1. xk es no básica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
9.1.2. xk es básica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
9.2. Cambio en el vector de términos independientes . . . . . . . . . . . . . . . . . . . 136
9.3. Cambio en la matriz de restricciones . . . . . . . . . . . . . . . . . . . . . . . . . 139
9.3.1. Cambios en vectores de actividades para columnas no-básicas . . . . . . . 139
9.3.2. Cambios en vectores de actividades para columnas básicas . . . . . . . . . 140
9.4. Adición de una nueva variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
9.5. Adición de una nueva restricción . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
Capítulo 1

Planteamiento de problemas

Los problemas de optimización son problemas que buscan maximizar o minimizar una función
numérica de un cierto número de variables sujeta a determinadas restricciones. Varios problemas
de optimización fueron planteados en un principio en las ciencias físicas y en la geometría.
En los años 1947 a 1952 muchos nuevos e importantes problemas de optimización surgieron
en diferentes campos, principalmente en la economía. Podemos clasificar a estos problemas como
problemas de programación. Fueron de gran interés debido a su aplicación en problemas prácticos
en operaciones militares, gubernamentales e industriales, así como en economía. En general, las
técnicas de optimización clásicas fueron de poca ayuda para resolver estos problemas de progra-
mación, de modo que se desarrollaron nuevos métodos.
En este curso trataremos sólo una clase especial pero muy importante de problemas de progra-
mación, conocidos como problemas de programación lineal. Veremos la teoría de la programación
lineal, técnicas numéricas para resolver tales problemas y algunas aplicaciones.
Hablando de una manera general, los problemas de programación consisten en determinar colo-
caciones óptimas de recursos limitados para obtener ciertos objetivos dados. Más específicamente,
conciernen situaciones donde un números de recursos tales como hombres, materiales, máquinas,
etc. están disponibles y deben combinarse para producir uno o más productos. Existen, sin em-
bargo, ciertas restricciones que caen en diversas categorías, como por ejemplo, la cantidad total
de cada recurso disponible, la cantidad de cada producto elaborado, la calidad de cada producto,
etc. Dentro de todas las posibilidades de colocación de recursos es deseable encontrar aquella o
aquellas que maximicen o minimicen alguna cantidad numérica, como por ejemplo: ganancia o
costo.
Un problema de programación lineal cae en la clase de problemas en la cual todas las relaciones
entre las variables son lineales. Las relaciones deben ser lineales en las restricciones y en la función
a optimizar.

1
1.1. Breve historia
Los problemas de programación surgieron en la economía donde la colocación óptima de re-
cursos ha sido de gran interés para los economistas. Más específicamente, los problemas de pro-
gramación surgieron alrededor de 1930. Un modelo teórico desarrollado entonces fue el modelo
lineal de Von Neumann (1932) de una economía expandida, que fue parte de los esfuerzos de eco-
nomistas y matemáticos austriacos y alemanes que estudiaron las generalizaciones de los modelos
de equilibrio Walrasianos de una economía. Un enfoque más práctico fue hecho por Leontief quien
desarrolló modelos económicos input-output. Su trabajo consistió en determinar qué tanto deberían
producir las industrias para satisfacer las demandas de los consumidores. Los modelos input-output
no involucran ninguna optimización, requieren de la resolución de un sistema de ecuaciones linea-
les simultáneas.
Durante la segunda guerra mundial un grupo bajo la dirección de Marshal K. Wood trabajó
un problema para la fuerza estadounidense. Se desarrollaron generalizaciones de modelos de tipo
Leontief para colocar recursos de tal manera de maximizar o minimizar una función lineal. George
B. Dantzig era un miembro del grupo de la fuerza aérea, él formuló el problema general de progra-
mación lineal y desarrolló el método simplex de solución en 1947. Su trabajo no estuvo disponible
sino hasta 1951 que fue cuando se publicó.
Después de 1957 el desarrollo teórico y las aplicaciones prácticas de la programación lineal se
dieron de una manera muy rápida y numerosa. Contribuciones teóricas importantes fueron hechas
por David Gale, H. W. Kuhn y A. W. Tucker que compartieron el desarrollo de la teoría de dualidad
en programación lineal. A. Charnes también realizó un trabajo teórico importante y W. W. Cooper
fue líder en incrementar las aplicaciones industriales de la programación lineal.
Problemas del tipo programación lineal fueron formulados y resueltos antes del primer trabajo
de Dantzig. En 1941 Hitchcok formuló y resolvió el problema de transporte que fue independien-
temente resuelto por Koopmans en 1947. En 1942 Kantorovitch también formuló el problema de
transporte pero no lo resolvió. El economista Stigler trabajó el problema de la dieta a costo mínimo
en 1945. Aunque este problema puede formularse como uno de programación lineal, Stigler no usó
esta técnica. No fue sino hasta el trabajo de Dantzig que el problema de programación lineal fue
formulado y fue entonces que se propuso un método para resolverlo.

1.2. Algunos problemas

Un problema lineal está constituido por:
Una función lineal, llamada función objetivo, la cual depende de una colección de variables,
a las cuales denominaremos variables de decisión.

Algunas restricciones lineales sobre los valores de las variables de decisión.

Veamos algunos planteamientos de problemas que nos permitirán proponer un modelo de pro-
gramación lineal para un problema dado.
Ejemplo 1.1 Un inversionista dispone de $100,000 y de dos tipos de inversión, a saber, A y B;
la inversión A produce 5 % y la tipo B 8 %. Se desea maximizar las ganancias obtenidas, pero se
tienen las siguientes condiciones:

(a) Debe invertir al menos 25 % en las inversiones tipo A.

(b) No más del 50 % de sus fondos deben colocarse en B.

(c) La cantidad invertida en B no debe ser mayor que una y media veces la cantidad invertida en A.

Para poder plantear el modelo matemático de un problema de programación lineal, distingui-

remos las variables (que llamaremos variables de decisión), el objetivo (lo que se pretende) y las
restricciones del problema.

Variables de decisión Denotaremos con x la cantidad a invertir en A (en miles de pesos) y con y
la cantidad a invertir en B (también en miles de pesos).

Función objetivo. Maximizar ganancias,

máx z = 50x + 80y.

Restricciones.

x ≥ 25, (a)
y ≤ 50, (b)
3
y≤ 2 x; (c)

además, puesto que el inversionista dispone únicamente de $100,000.00, tenemos la restric-

ción

x + y ≤ 100, (d)

y también las restricciones de no negatividad para x y y,

x, y ≥ 0.

El problema queda planteado como un problema de programación lineal de la siguiente manera:


máx z = 50x + 80y,
s.a.



≥ 25,




 x
y ≤ 50,

P


 − 23 x
+ y ≤ 0,
x+ y ≤ 100,






x, y ≥ 0.
Ejemplo 1.2 Un fabricante de gabinetes desea construir dos tipos de gabinetes para exportar (uno
moderno y uno provenzal). Suponemos que existe un mercado ilimitado donde puede vender cual-
quier cantidad de cada uno. El proceso de construcción requiere la utilización de cuatro talleres:
cortado, pulido, pintado y acabado. El fabricante puede utilizar: (a) 8 horas máximo el taller de cor-
tado, (b) 15 horas máximo el taller de pulido, (c) 8 horas máximo el taller de pintado y (d) 32 horas
máximo el taller de acabado, por periodo.
Para construir un gabinete moderno necesita: (a) 2/5 de hora en cortado, (b) 1 hora en pulido,
(c) 1/3 de hora en pintura y (d) 8/3 de hora en acabado. Para un provenzal utiliza: (a) 3/5 de hora
en cortado, (b) 3/2 de hora en pulido, (c) 1 hora en pintado y (d) 2 horas en acabado.
La ganancia neta que obtiene es de $150 en cualquier gabinete. Determinar qué cantidad de
cada tipo de gabinetes tiene que fabricar para obtener la ganancia máxima.

Variables de decisión. Sea x la cantidad de gabinetes de tipo moderno a fabricar y sea y la canti-
dad de gabinetes de tipo provenzal a fabricar.

Función objetivo. Maximizar ganancia,

máx z = 150x + 150y.

Restricciones.
2
5x + 35 y ≤ 8, (a)
x + 23 y ≤ 15, (b)
1
3x + y ≤ 8, (c)
8
3x + 2y ≤ 32, (d)
x, y ≥ 0.

El problema queda planteado como


máx z = 150x + 150y,
 s.a.


2 3
5 y ≤ 8,

5x +



3

x+ 2y ≤ 15,

P 1

 3x
+ y ≤ 8,
8

3x
+ 2y ≤ 32,






x, y ≥ 0.

Ejemplo 1.3 El complejo industrial de Ciudad Sahagun encargó a su departamento de producción

de lámina que minimice el desperdicio de sobrante de lámina que resulta del corte de ésta para la
fabricación de piezas de camión. Los tamaños necesarios para la carrocería son:

30 × 60 para puertas,
 30 × 70 para techo y cofre,

30 × 50 para salpicadera.

Las cantidades necesarias para cada tamaño de corte son (a) 10000, (b) 15000 y (c) 5000 por
mes, respectivamente. Considerando que se tienen placas de 30 × 180 cm los posibles cortes dan
distintos tamaños de sobrantes.
Deducimos que existe un número finito de tipos de corte para obtener las medidas requeridas
(figura 1.1).

60 60 60 70 70 40 70 50 50 10

(a) Corte tipo 1 (b) Corte tipo 2 (c) Corte tipo 3

60 50 70 50 50 50 30 50 50 60 20

(d) Corte tipo 4 (e) Corte tipo 5 (f) Corte tipo 6

60 60 50 10

(g) Corte tipo 7

Figura 1.1: Tipos de corte.

Variables de decisión. Sea xi el número de láminas a cortar del tipo i, para i = 1, . . . , 7.

Función objetivo. Minimizar desperdicio,

mı́n w = 0x1 + 40x2 + 10x3 + 0x4 + 30x5 + 20x6 + 10x7 .

Restricciones.

3x1 + x4 + x6 + 2x7 ≥ 10, 000, (a)

2x2 + x3 + x4 ≥ 15, 000, (b)
2x3 + x4 + 3x5 + 2x6 + x7 ≥ 5, 000, (c)
xi ≥ 0, i = 1, . . . , 7.
El problema queda planteado como un problema de programación lineal:

 mı́n w = 0x1 + 40x2 + 10x3 + 0x4 + 30x5 + 20x6 + 10x7 ,


s.a.


3x1 + x4 + x6 + 2x7 ≥ 10, 000,



P 2x2 + x3 x4 ≥ 15, 000,

2x3 + x4 + 3x5 + 2x6 + x7 ≥ 5, 000,




xi ≥ 0, i = 1, . . . , 7.


Ejemplo 1.4 (Problema de asignación) Se tienen m proyectos y m compañías; c ij es el costo de

el proyecto i desarrollado por la compañía j. Se desea asignar un solo proyecto a cada compañía a
costo mínimo.

Variables de decisión. La variable xij establece si el proyecto i fue asignado a la compañía j para
i, j = 1, . . . , m y tomará los valores:
(
0, si no se asigna el proyecto i a la compañía j,
xij =
1, si se asigna el proyecto i a la compañía j.

Función objetivo. Minimizar costo,

m X
X m
mı́n w = cij xij .
i=1 j=1

Restricciones. Para asignarle un proyecto a cada compañía:

m
X
xij = 1, ∀i = 1, . . . , m.
j=1

Para asignarle una compañía a cada proyecto:

m
X
xij = 1, ∀j = 1, . . . , m.
i=1

Por lo tanto el problema de asignación es el siguiente:

m P m

P

 mı́n w = cij xij
s.a.



 i=1 j=1

 m
∀i = 1, . . . , m
P
xij = 1,


P j=1

 m
∀j = 1, . . . , m
P
xij = 1,





 i=1
xij ≥ 0


Ejemplo 1.5 (Problema de transporte) Se tienen n bodegas, cada una con una disponibilidad d i
y m almacenes, cada uno con una demanda Dj . Se desea transportar el producto de las bodegas
a los almacenes con costo cij (costo del transporte de la bodega i al almacén j) mínimo. De tal
manera que cada bodega no mande más de lo que dispone y se satisfaga la demanda de cada uno
de los almacenes.

Variables de decisión. Sea xij la cantidad del producto a transportar de la bodega i al almacén j
para i = 1, . . . , n y j = 1, . . . , m.

Función objetivo. Minimizar el costo de envío,

m X
X n
mı́n z = cij xij .
i=1 j=1

Restricciones. (a) Disponibilidad de cada bodega y (b) demanda de cada almacén:

X
xij = di , i = 1, . . . , n, (a)
j
X
xij = Dj , j = 1, . . . , m, (b)
i
xij ≥ 0.

Entonces el problema de transporte queda planteado de la siguiente manera:

 m P n
cij xij ,
P

 mı́n z =


 s.a. i=1 j=1

∀i,
P
xij = di ,


P j
∀j,
P
xij = Dj ,




i



xij ≥ 0.


Ejemplo 1.6 (Problema de flujo máximo) Considérese una red de conductores (rutas, tubos, ca-
bles eléctricos) cada uno con una capacidad qij máxima (límite superior de la cantidad de flujo que
puede pasar por el conductor por unidad de tiempo), buscamos enviar la cantidad más grande de
flujo de un punto origen o a un punto destino d, sabiendo que el flujo es conservativo, es decir, la
cantidad de flujo que sale del origen es la misma que llega al destino, y la que entra en cada punto
intermedio es la misma que sale de él. La cantidad de flujo que pasa en cada arco debe ser menor o
igual que la capacidad de ese arco.

Variables de decisión. Denotemos por xij la cantidad de flujo que va de i a j con i = o, 1, 2, . . .,

n y j = 1, 2, . . ., n, d.
Función objetivo. Maximizar la cantidad de flujo que va de o a d,
X X
máx z = xoj = xid .
j i

Restricciones. La cantidad de flujo que llega a un punto intermedio es la misma que la que sale
de él:
X X
xik − xkj = 0.
i j

La cantidad de flujo en cada arco debe ser menor o igual que su capacidad y mayor o igual
que cero:

xij ≤ qij ,
xij ≥ 0.

El problema de flujo máximo se plantea entonces:

máx z = xoj = xid ,

 P P
s.a.

j i



xik − xkj = 0, ∀k 6= o, d,

 P P
P i j




 xij ≤ qij , ∀(i, j),
xij ≥ 0.


Ejemplo 1.7 Considérese el problema anterior para el caso en que se tiene la red de la figura 1.2
con o, d y cuatro vértices.

1m - 3m
4
µ
¡
5 ¡ @ @ 3
¡ @ @
om dm
¡ @ 4 @
R
@
@
@ @ µ
¡
¡
@ @ ¡
2 @ R ¡ 8
2m - 4m
R
@ @
@
4

Figura 1.2: Red de conductores.

 

 máx z = xo1 + xo2 ,
 s.a.




 xo1 − x13 − x14 = 0,
xo2 − x24 = 0,








 x 13 − x3d = 0,
x + x − x4d = 0,




 14 24
xo1 ≤ 5,



P xo2 ≤ 2,

x13 ≤ 4,




x14 ≤ 4,





x24 ≤ 4,




x3d ≤ 3,





x4d ≤ 8,




xij ≥ 0.



Ejercicios del capítulo 1

1. Una compañía de muebles manufactura cuatro modelos de escritorios. Cada escritorio es
construído primero en el departamento de carpintería y después en el departamento de aca-
bado, donde es barnizado, encerado y pulido. El número de horas hombre de labor que se
requiere en cada departamento está dado por:

Escritorio 1 Escritorio 2 Escritorio 3 Escritorio 4

Depto. de carpintería 4 9 7 10
Depto. de acabado 1 1 3 40

Por limitaciones en la capacidad de la planta, no más de 6000 horas-hombre pueden ser

utilizadas en la carpintería y 4000 en el de acabado en los siguientes seis meses.
Las utilidades (ingresos menos costos de labor) de la venta de cada escritorio son:

Escritorio 1 2 3 4
Utilidad $12 $20 $18 $40

Suponiendo que la materia prima y suministros están disponibles en provisiones adecuadas

y todos los escritorios producidos pueden ser vendidos. La compañía de muebles quiere
determinar la combinación óptima de productos, es decir, las cantidades de cada tipo de
producto que maximicen la utilidad. Formularlo como un problema lineal.

2. Una compañía constructora dispone de 100 lotes en los cuales va a construir diferentes tipos
de casas: económico, rústico, colonial, moderno y provenzal. Dispone de dos tipos de mano
 de obra: albañiles y carpinteros. Necesita de cierto número de días laborables de cada equipo
de trabajadores:

Tipo de casas Días de albañiles Días de carpinteros

Económico 1 4
Rústico 2 7
Colonial 2 6
Moderno 1 5
Provenzal 1 3

Las ganancias por cada tipo de casa son: 2000, 3000, 2500, 1700 y 2000 respectivamente.
Se quiere, además, que al menos se construyan 10 casas de cada tipo.
El constructor pidió prestado dinero a un bajo interés con un plazo de tres años; sabe que
necesita dos meses para vender las casas, por tanto, quiere que las casas estén terminadas a
más tardar dentro de 610 días laborables.

3. Una compañía desea comprar tres tipos de máquinas X, Y y Z. La cantidad disponible de

dinero y espacio es de $400,000 y 1500 m2 . También se sabe que el número de máquinas a
comprar no debe pasar de 30 por limitaciones de empleados. Dada la siguiente información:

Tipo de Costo área necesaria Tasa de

máquina $ m2 producción diaria
X 8,000 30 79
Y 13,000 60 90
Z 15,000 60 126

¿Cuántas máquinas de cada tipo deben comprarse para maximizar la producción diaria?

4. La división de televisores de la compañía Philips, S.A., desea maximizar sus utilidades por
la venta de televisores de color y blanco y negro. Cada aparato de color proporciona $2,000
de utilidad neta; el de blanco y negro $1,250 por unidad.
De acuerdo con el contrato firmado por el sindicato, para cada período de producción se
tienen disponibles 500 horas-hombre para producción de partes, 2500 horas-hombre para
ensamble y 600 horas-hombres para inspección.
Los proveedores de partes fijan una capacidad máxima de 4000 televisores blanco y negro y
1000 de color por cada unidad de tiempo. Cada aparato de color requiere: 4 horas-hombre
en producción de partes, 5 horas-hombre para ensamblaje y 3 horas-hombre para inspec-
ción. Los de blanco y negro 5 horas-hombre en producción de partes, 2 horas-hombre en
ensamblado y 1 hora-hombre en inspección.
Plantear como un problema de programación lineal.
5. Un ranchero está criando puercos y desea determinar la cantidad de cada tipo disponible de
alimento que puede servirle para cumplir los requerimientos nutritivos a un costo mínimo.
El número de cada tipo de ingredientes nutritivos básicos contenidos dentro de una libra de
cada alimento está dado en la siguiente tabla, junto con el requerimiento nutritivo mínimo
diario que requiere un puerco y el costo de cada alimento.

Ingredientes Libra de Libra de alimento Libra de Requerimiento

nutritivos maíz procesado alfalfa mínimo diario
Carbohidratos 9 2 4 20
Proteinas 3 8 6 18
Vitaminas 1 2 6 15
Costo (/c) 7 6 5

Formule el modelo de programación lineal para este problema.

6. Una ama de casa le pide al carnicero que le muela varios cortes de carne para hacer una
mezcla con igual parte de proteínas y grasas. El carnicero, siendo concienzudo, desea hacerlo
con el menor costo total. Formular este problema como un problema lineal para determinar
la mezcla para un kilogramo de carne.

Tipos de cortes
1 2 3 4 5 6 7
% Proteina 19 20 16 17 19 16 17
% Grasa 16 18 25 23 11 28 20
Costo por kilogramo 0.69 0.98 139 129 119 150 165

7. Una empresa fabrica dos productos A y B. El producto A está formado por 1 componente X
y 2 componentes Y. El producto B está formado por 3 componentes X y 1 componente Y.
Los tiempos estándar de fabricación son:

Componente Máquina 1 Máquina 2 Ensamble

X 2 horas/pieza 3 horas/pieza 4 horas/pieza
Y 2 horas/pieza 1 hora/pieza 5 horas/pieza
Tiempo
80 horas/semana 90 horas/semana 120 horas/semana
disponible

Las utilidades unitarias son: $150 para el producto A y $180 para el producto B. Determine
el programa de producción que maximiza las utilidades por semana de la empresa.
8. Un molino agrícola produce alimento para vacas, ovejas y pollos. Esto se hace mezclando los
siguientes ingredientes principales: Maíz, piedra caliza, frijol de soya y comida de pescado.
Estos ingredientes contienen los siguientes nutrientes: vitaminas, proteínas, calcio y grasa
cruda. A continuación se resumen el contenido de los nutrientes en cada kilogramo de los
ingredientes.

Nutriente
Ingrediente Vitaminas Proteína Calcio Grasa cruda
Maíz 8 10 6 8
Piedra caliza 6 5 10 6
Frijol de soya 10 12 6 6
Comida de pescado 4 8 6 9

Se hace un pedido al molino para que produzca 10, 6 y 8 toneladas (métricas) de alimento
para vacas, ovejas y pollos, respectivamente. Debido a la escasez de los ingredientes, sólo
se dispone de una cantidad limitada de ellos a saber, 6 toneladas de maíz, 10 toneladas de
piedra caliza, 4 toneladas de frijol de soya , y 5 toneladas de alimento de pescado. El precio
por kilogramo de estos ingredientes es $0.20, $0.12, $0.24, y $0.12, respectivamente. A
continuación se resumen las unidades mínima y máxima que se permiten de los distintos
nutrientes por cada kilogramo de alimento para vacas, ovejas y pollos.

Nutriente
Vitaminas Proteínas Calcio Grasa cruda
Producto mı́n máx mı́n máx mı́n máx mı́n máx
Alimento para vacas 6 8 6 ∞ 7 ∞ 4 8
Alimento para ovejas 6 ∞ 6 ∞ 6 ∞ 4 6
Alimento para pollos 4 6 6 ∞ 6 ∞ 4 6

Formule este problema de mezcla alimenticia de tal manera que el costo total sea mínimo.

9. El personal técnico de un hospital desea elaborar un sistema computarizado para planear me-
nús. Para empezar, deciden planear el menú del almuerzo. El menú se divide en tres grandes
categorías: vegetales, carne y postre. Se desea incluir en el menú al menos el equivalente a
una porción de cada categoría. A continuación se resumen el costo por ración de algunos
de los artículos sugeridos, así como su contenido de carbohidratos, vitaminas, proteínas y
grasas.
 Costo
Carbohidratos Vitaminas Proteinas Grasa
en $/ración
Vegetales
Chícharos 1 3 1 0 0.10
Ejotes 1 5 2 0 0.12
Quimbombó 1 5 1 0 0.13
Maíz 2 6 1 2 0.09
Macarrones 4 2 1 1 0.10
Arroz 5 1 1 1 0.07
Carnes
Pollo 2 1 3 1 0.70
Res 3 8 5 2 1.20
Pescado 3 6 6 1 0.63
Postres
Naranja 1 3 1 0 0.28
Manzana 1 2 0 0 0.42
Budín 1 0 0 0 0.15
Gelatina 1 0 0 0 0.12

Supóngase que los requerimientos mínimos por comida de carbohidratos, vitaminas, proteí-
nas y grasas son 5, 10, 10 y 2, respectivamente.

(a) Formule el problema de planeación de menú como un problema lineal.

(b) Muchos problemas prácticos se han omitido el menú anterior. Estos incluyen, por ejem-
plo, la planeación conjunta de los menús del desayuno, la comida y la cena, la planea-
ción semanal de tal manera que se puedan incluir distintas variedades de comida, y
menús especiales para pacientes en dietas particulares. Explicar con detalle cómo se
pueden incorporar estos aspectos de una manera comprensiva en un sistema de planifi-
cación de menús.

10. Una empresa que fabrica calcomanías redondas, obtiene las mismas hojas de plástico rectan-
gulares cuyas dimensiones son 30 cm × 15 cm. Dos tamaños de calcomanías son necesarios.
El diámetro de la calcomanía menor es de 5 cm y el de la mayor es de 15 cm. Diariamente
se necesitan 20,000 calcomanías chicas y 5,000 grandes. El problema de la empresa es cómo
cortar las hojas de plástico para minimizar el número de ellas para cumplir la demanda diaria,
sabiendo que cada hoja les cuesta $50.

11. En un salón de banquetes se tienen programados banquetes durante los siguientes 5 días. Los
requisitos de manteles por banquete son:
 Banquete 1 2 3 4 5
Número de manteles 80 60 100 130 200

El problema del administrador es que se requieren manteles diferentes a los que él usa, por
lo que tendrá que comprar ese tipo de mantel, el costo de cada uno es de $40 y el costo
de mandarlo a la lavandería bajo servicio urgente para tenerlo listo a los 2 días, es de $10
por mantel. ¿Cuál es el modelo que permitirá al administrador cumplir con sus requisitos y
además minimizarle el costo total?

12. La productora nacional de fertilizantes quiere programar su producción trimestral para el

próximo año. Supóngase que la demanda de fertilizantes pronosticada es:

Toneladas de
Periodo
fertilizante
1er trimestre 100,000
2do trimestre 120,000
3er trimestre 110,000
4to trimestre 90,000

La capacidad de producción es de 95,000 toneladas por trimestre. Sin embargo pueden pro-
ducirse 30,000 toneladas adicionales por trimestre si se pone a trabajar un tercer turno. Cuesta
$300 cada tonelada por trimestre más el producir el fertilizante en el turno extra que durante
los turnos normales. Eso se debe a que en los turnos extras los salarios son más altos. Al
fertilizante que no se puede vender hay que almacenarlo en bodegas a un costo de $500 cada
tonelada portrimestre. Las bodegas no pueden almacenar más de 20,000 toneladas por tri-
mestre. Bajo estas condiciones, ¿cuántas toneladas deben producirse por trimestre en turnos
normales y extras tal que la demanda se satisfaga y se abatan los costos extras de producción
y de almacenamiento? Supóngase que el costo normal de producción es de $700 por tonelada
por trimestre. Plantearlo como un problema de programación lineal.

13. Una pequeña ciudad de 15,000 habitantes requiere un promedio de 200,000 galones de agua
diariamente. La ciudad se satisface de una central en donde el agua es purificada por métodos
convencionales de filtración y clorhidratación. Además, dos compuestos químicos diferentes,
suavizador y purificador, son necesarios para tratar el agua con propósitos de salubridad. La
central de aguas planea comprar dos productos populares que contienen estos compuestos
químicos.
Una unidad del producto A da 3 libras de suavizador y 3 libras de purificador. Una unidad del
producto B contiene 4 y 9 libras respectivamente. Para mantener el agua a un nivel mínimo
de suavidad y una protección mínima de pureza, los expertos han decidido que 150 y 100
libras respectivamente de estos compuestos deben ser añadidos diariamente. El costo es de
$8 y $10 por unidad respectivamente para el producto A y para el producto B. ¿Cuál es
 la cantidad óptima de cada producto que debe ser usado para afrontar el nivel mínimo de
suavidad y pureza?
14. Supóngase que en el poblado de Tixtla, Gro., la Nacional Financiera pretende hacer inversio-
nes cuantiosas en el cultivo de aguacate, lima, mango y zapote. Se persiguen dos objetivos,
uno el de reducir el desempleo rural y el otro el de aumentar las exportaciones que vendrían
a equilibrar la balanza de pagos de la nación. Se sabe que la producción promedio de cada
árbol está dada por la siguiente tabla:

Producción promedio anual

Tipo de Arbol en unidades en Kg Observación
Aguacate 350 150 una vez al año
Lima 230 200 una vez al año
Mango 150 50 una vez al año
Zapote 400 150 una vez al año

El precio promedio en el mercado mundial a precios de 1974 fue de $10 por Kg de aguacate,
$4 por Kg de lima, $15 por Kg de mango y $7 por Kg de zapote. Existe una extensión
de 250,000 m2 de tierra de propiedad federal propicia para el cultivo de esos productos.
Supóngase que técnicos de la Secretaría de Agricultura han determinado que las siguientes
extensiones mínimas son necesarias para el cultivo de esos productos:

Extensión mínima
Tipo de Arbol
de cultivo por árbol
Aguacate 4 m2
Lima 5 m2
Mango 3 m2
Zapote 6 m2

Afortunadamente no existe problema de agua, pues hay varios manantiales dentro de la pro-
piedad, que aseguran la existencia de ese preciado líquido por los próximos 20 años. El costo
por sembrar un árbol de aguacate es de $2, $0.50 por árbol de lima, $1 de mango y $1.50
de zapote; estos costos ya están incluyendo la compra del árbol más su cuidado y manteni-
miento. Cada árbol empieza a ser productivo aproximadamente a los 3 años de ser plantado.
Cada árbol de aguacate requiere de cuidados equivalentes a 36 horas-hombre-año; 72 horas-
hombre-año por árbol de lima; 50 horas-hombre-año de mango y 100 horas-hombre-año por
zapote.
La Nacional Financiera pretende hacer una inversión de 20 millones de pesos, pensando
exportar toda su producción a partir del tercer año. El desempleo en Tixtla se ha calculado
en 500 personas y, el Gobierno Federal ha delineado que este proyecto emplee al menos 200
personas en forma contínua.
 Bajo estas circunstancias ¿Cuántos árboles de cada fruta deberán sembrarse con objeto de
maximizar el valor de la futura exportación anual?
Supóngase también que durante todo el año se deben trabajar jornadas de 8 horas (por día).

15. Una excursionista planea salir de campamento. Hay 5 artículos que desea llevar consigo,
pero entre todos sobrepasan las 60 libras que considera que puede cargar. Para auxiliarse en
la selección, ha asignado un valor a cada artículo en orden ascendente de importancia:

Artículo 1 2 3 4 5
Peso (lb) 52 23 35 15 7
Valor 100 60 70 15 15

¿Qué artículos deberá llevar para maximizar el valor total, sin sobrepasar la restricción de
peso? Plantear el problema de programación lineal.
Capítulo 2

Interpretación geométrica de un
problema de programación lineal

Los problemas de programación lineal que conciernen sólo dos variables pueden resolverse
gráficamente y este tipo de problemas nos permiten tener una idea de qué es lo que sucede en casos
más generales con cualquier número de incógnitas. El objetivo del presente capítulo es desarrollar
la intuición geométrica relativa a los problemas de programación lineal.

Ejemplo 2.1 Considérese el problema del inversionista visto en el ejemplo 1.1.


máx z = 50x + 80y,
s.a.



≥ 25,




 x
y ≤ 50,

P


 − 23 x+ y ≤ 0,
x+ y ≤ 100,






x, y ≥ 0.

Para encontrar los valores de x y y que maximizan la función z evaluamos en los puntos extre-
mos (véase la definición 3.9) de la región de soluciones factibles (véase la definición 3.4) como se
muestra en la tabla 2.1 (figura 2.1). Los valores que maximicen o minimicen (según sea el caso) a z
estarán siempre en los puntos extremos; esto lo demostraremos en el capítulo 3. Así pues, tenemos
que la solución óptima está dada por

zmáx = 6500 con x∗ = 50, y ∗ = 50.

En las siguientes secciones se presentan diferentes casos que pueden presentarse graficamente
en un problema de programación lineal.

17
 y
3
x = 25 2x +y =0

y = 50 D C

E
z = 50x + 80y = 6500

B x
A

x + y = 100

Figura 2.1: Interpretación geométrica del problema del inversionista del ejemplo 2.1.

2.1. Restricciones redundantes

Ejemplo 2.2 En el problema

máx z = 5x + 3y,

s.a.



3x + 5y ≤ 15,



P 5x + 2y ≤ 10,

y ≤ 4,




x, y ≥ 0,


la restricción y ≤ 4 es redundante, es decir, sin ella se tiene la misma región de soluciones factibles,
como se puede apreciar en la figura 2.2. En la tabla 2.2 se calculan los valores de z para cada punto
extremo. Así pues, la solución óptima está dada por

Punto extremo Valor de la función objetivo

A = (25, 0) z = 50(25) + 80(0) = 1250
B = (100, 0) z = 50(100) + 80(0) = 5000
C = (50, 50) z = 50(50) + 80(50) = 6500
D = ( 100
3 , 50) z = 50( 100
3 ) + 80(50) = 5666.67
E = (25, 75
2 ) z = 50(25) + 80( 752 ) = 4250

Tabla 2.1: Evaluación en los puntos extremos de la región de soluciones factibles del ejemplo 2.1.
 y

y=4

D
C

235
z = 5x + 3y = 19

x
A B

3x + 5y = 15

5x + 2y = 10

Figura 2.2: En el ejemplo 2.2 la restricción y ≤ 4 es redundante.

zmáx = 235
19 con x∗ = 20
19 , y∗ = 45
19 .

2.2. Soluciones óptimas múltiples

Ejemplo 2.3 Considérese ahora el problema

máx z = 25 x + y,

s.a.



3x + 5y ≤ 15,



P 5x + 2y ≤ 10,

y ≤ 4,




x, y ≥ 0,


de la figura 2.3. En la tabla 2.3 se calculan los valores de z en cada punto extremo. Se observa que

Punto extremo Valor de la función objetivo

A = (0, 0) z = 5(0) + 3(0) = 0
B = (2, 0) z = 5(2) + 3(0) = 10
C = ( 20 45
19 , 19 ) z = 5( 20 45 235
19 ) + 3( 19 ) = 19 ≈ 12.36
D = (0, 3) z = 5(0) + 3(3) = 9

Tabla 2.2: Evaluación en los puntos extremos de la región de soluciones factibles del ejemplo 2.2.
 y

y=4

D
C

3x + 5y = 15

x
A B

z = 5x + 2y = 10
z=0 z=3

Figura 2.3: En el ejemplo 2.3 todos los puntos de la recta 5x + 2y = 10 son soluciones óptimas.

todos los puntos de la recta 5x + 2y = 10 son soluciones óptimas de P , es decir, P tiene soluciones
óptimas múltiples.

2.3. Región de soluciones factibles no acotada

Ejemplo 2.4 En la tabla 2.4 se calculan los valores de z en algunos puntos factibles del problema

máx z = 2x + 2y,
 s.a.



P x − y ≥ −1,


 − 21 x+ y ≤ 2,
x, y ≥ 0,


y en la figura 2.4 se muestra la gráfica del mismo. La solución óptima no está acotada, es decir,
z → ∞. Las dos restricciones no acotan la región de soluciones factibles.

Punto extremo Valor de la función objetivo

A = (0, 0) z = 52 (0) + 0 = 0
B = (2, 0) z = 25 (2) + 0 = 5
20 45
C = ( 19 , 19 ) z = 25 ( 20 45
19 ) + 19 = 5
5
D = (0, 3) z = 2 (0) + 3 = 3

Tabla 2.3: Evaluación en los puntos extremos de la región de soluciones factibles del ejemplo 2.3.
 y

1
2x +y =2

C
D

x
A

x y= 1 z = 2x + 2y = 10

z=0 z=2

Figura 2.4: La solución óptima no está acotada.

Observación 2.1 Si la función objetivo se minimizara, la región de soluciones factibles sería la

misma y su solución óptima sí estaría acotada y sería

zmı́n = 0 con x∗ = 0, y ∗ = 0.

Ejemplo 2.5 Si se calcula z en cada punto extremo de la región de soluciones factibles del proble-
ma
 máx z = −x + 2y,

s.a.


x − y ≥ −1,

P


 − 12 x + y ≤ 2,
x, y ≥ 0,


que se ilustra en la figura 2.5 se obtiene la tabla 2.5. La región de soluciones factibles es no acotada,
pero la función objetivo sí está acotada y tiene una infinidad de soluciones.

Punto factible Valor de la función objetivo

A = (0, 0) z = 2(0) + 2(0) = 0
B = (0, 1) z = 2(0) + 2(1) = 2
C = (2, 3) z = 2(2) + 2(3) = 10
D = (4, 3) z = 2(4) + 2(3) = 14
E = (5, 4) z = 2(5) + 2(4) = 18

Tabla 2.4: Valores de z en algunos puntos factibles del problema del ejemplo 2.4.
 1
y 2x +y =2
x y= 1 z = x + 2y = 4

E
z=2

D
z=0
C

x
A

Figura 2.5: La solución óptima sí existe a pesar de que la región de soluciones factibles no es
acotada.

Punto factible Valor de la función objetivo

A = (0, 0) z = −0 + 2(0) = 0
B = (0, 1) z = −0 + 2(1) = 2
C = (2, 3) z = −2 + 2(3) = 4
D = (4, 4) z = −4 + 2(4) = 4
E = (6, 5) z = −6 + 2(5) = 4

Tabla 2.5: z en diferentes puntos factibles de la región de soluciones factibles del problema del
ejemplo 2.5.

Ejemplo 2.6 En el problema

z = −3x + 2y,

 máx
 s.a.


P x ≤ 3,


 x − y ≤ 0,
x, y ≥ 0,


que se muestra en la figura 2.6 la región de soluciones factibles y la función objetivo son no acota-
das.
 y
z=8 z= 3x + 2y = 0

z= 3

x y=0

x=3

Figura 2.6: Ni la región de soluciones factibles ni la función objetivo están acotadas.

2.4. Región de soluciones factibles consistente de un solo punto

Ejemplo 2.7 En el caso del problema (figura 2.7)


máx z = x,
 s.a.



P x + y = 3,


 x − y = 1,
x, y ≥ 0,


como la región de soluciones factibles consta de un solo punto, ese punto maximiza a la función z.
Entonces

zmáx = 2 con x∗ = 2, y ∗ = 1.

Observación 2.2 Para el caso en que z se minimizara, el óptimo sería el mismo punto (x ∗ , y ∗ ) =
(2, 1).
 y
x+y =3 x y=1

z=x=2

Figura 2.7: La región de soluciones factibles consta de un sólo punto

2.5. Región de soluciones factibles vacía

Ejemplo 2.8 Para el problema

máx z = x + y,
 s.a.



P x − y ≥ 0,


 3x − y ≤ −3,
x, y ≥ 0,


de la figura 2.8 la región de soluciones factibles es vacía, y por lo tanto no podemos hablar de un
máximo ni un mínimo para z.

Ejemplo 2.9 Para el problema

máx z = 3x − 2y,

 s.a.


x + y ≤ 1,

P


 2x + 2y ≥ 4,
x, y ≥ 0,


de la figura 2.9 la región de soluciones factibles es vacía. No hay solución óptima.

Ejercicios del capítulo 2

1. Representar geométricamente los siguientes sistemas de ecuaciones dados en forma matricial
(Ax ≤ b):
   
1 0 3
a) A =  0 1 , b =  2 .
   
−2 −3 0
 y
3x y= 3 x y=0

Figura 2.8: Existen soluciones pero no son factibles.

y
2x + 2y = 4

x+y =1

Figura 2.9: No existen soluciones en absoluto.

 Ã ! Ã !
−3 −2 −6
b) A = ,b= .
3 2 6
   
−3 −2 −6
 −2 −3   −6 
c) A =  , b =  .
   
 −1 0   0 
0 −1 0
   
1 1 4

 4 3 


 12 

d) A= 1 −1 , b =  −1 .
   
−1 0  0
   
  
0 −1 0
   
−2 −1 −7
e) A =  1 0 , b =  0 .
   
0 1 0

2. Sean U el plano completo, A el semiplano lugar geométrico de −2x 1 +x2 < 3, B el semipla-
no lugar geométrico de −2x1 + x2 > 3, C el semiplano lugar geométrico de −2x1 + x2 ≤ 3,
D el semiplano lugar geométrico de −2x1 + x2 ≥ 3 y L la recta lugar geométrico de
−2x1 + x2 = 3. Encontrar los conjuntos:

a) Ac .
b) B c .
c) Lc ∩ A.
d) C ∩ D.
e) A ∩ B.
f ) A ∩ C.
g) B ∩ D.
h) A ∪ D.
i) B ∪ C.
j) A ∪ C.
k) B ∪ D.
l) A ∪ L.
m) B ∪ L.

¿Se pueden hallar otras relaciones?

3. De los conjuntos convexos construídos en el ejercicio 2, ¿cuáles tienen un área finita y cuáles
una infinita?
4. Un revendedor trata de decidir cuántas unidades de los artículos A y B debe tener en exis-
tencia. Sea x el número de unidades de A y y el número de unidades de B. A cuesta $4 por
unidad y B cuesta $3 por unidad.

a) No puede guardar un número negativo de unidades de A y B. Escribir esta condición

como desigualdad y graficarla.
b) La máxima demanda sobre el periodo para el cual el revendedor piensa tener existen-
cias, no excederá de 600 unidades de A y 600 unidades de B. Modificar el conjunto
hallado en el inciso anterior para tomar esto en cuenta.
c) El revendedor no desea excederse de $2400 en el inventario total. Modificar el conjunto
hallado en el inciso anterior.
d) El revendedor decide invertir en el artículo B cuando menos el doble de las existencias
del artículo A. Modificar el conjunto del inciso anterior.
e) Finalmente, el revendedor decide invertir $900 en las compras del artículo B. ¿Qué
posibilidades se dejan?

5. Suponiendo que los requerimientos nutricionales mínimos de los seres humanos están dados
por la tabla

Fósforo Calcio
Adultos 0.02 0.01
Niños 0.03 0.03
Bebés 0.01 0.02

Marcar la cantidad de fósforo en el eje vertical y la cantidad de calcio en el eje horizontal.

Trazar los conjuntos convexos de los requerimientos dietéticos mínimos para adultos, niños
y bebés. Establecer si son ciertas o no las siguientes aserciones:

a) Si las necesidades de un niño están satisfechas, también lo están las de un adulto.

b) Las necesidades de un bebé están satisfechas sólo si lo están las de un niño.
c) Las necesidades de un adulto están satisfechas sólo si las de un bebé lo están.
d) Se satisfacen las necesidades de un adulto y de un bebé sólo si se satisfacen las de un
niño.
e) Es posible satisfacer las necesidades de un adulo sin satisfacer las de un bebé.

6. En los siguientes conjuntos de desigualdades cuando menos una es redundante. Hallar en

cada caso las redundantes.
 

 x1 + x2 ≤ 3,
−x1 − x2 ≥ 0,


a)
 x1
 ≥ −1,


− x2 ≤ 2.


 −1 ≤ x1 ≤ 1,
 −2 ≤ x ≤ 2,

2
b)

 x1 + x2 ≥ −10,


2x1 − x2 ≤ 2.

7. Resolver gráficamente el problema1

máx z = 5x1 + 6x2 ,

 s.a.



x1 − 2x2 ≥ 2,


 2x1 + 3x2 ≥ 2,
x1 , x2 s.r.s.


8. Considerar el problema
máx z = 6x1 − 2x2 ,

 s.a.



x1 − x2 ≤ 1,


 3x1 − x2 ≤ 6,
x1 , x2 ≥ 0.


Demostrar en forma gráfica que en la solución óptima las variables x 1 , x2 pueden aumentar
en forma indefinida en tanto que el valor de la función objetivo se mantiene constante.
9. Graficar y resolver el problema
máx y mı́n z = 5x1 + 3x2 ,

 s.a. s.a.


x1 + x2 ≤ 6,





x2 ≥ 3,



 x1 ≥ 3,
2x1 + 3x2 ≥ 3,






x1 , x2 ≥ 0.

En los siguientes casos indicar si la región de soluciones factibles consta de un punto, número
infinito de puntos o es vacía.

a) Las restricciones son las mismas dadas.

b) Cambiar la primera restricción por x1 + x2 ≤ 5.
c) Cambiar la primera restricción por x1 + x2 ≥ 7.

1
s.r.s. significa “sin restricción de signo.”
Capítulo 3

Fundamentos del algoritmo simplex

En este capítulo se revisarán algunos conceptos que serán esenciales para poder comprender el
algoritmo simplex. La aplicación de estos conceptos será crucial para el desarrollo posterior de la
teoría.
Las principales características de un problema de programación lineal son:

1. Las restricciones y la función objetivo son funciones lineales.

2. Las variables son continuas.

3.1. Forma canónica y forma estándar

Definición 3.1 Un problema de la forma

 máx z = cx,

P Ax ≤ b, (3.1)
x ≥ 0,



donde A es una matriz m × n, c es un vector renglón con n componentes, b es un vector columna

con m componentes y x es un vector columna con n componentes, se llamará problema en forma
canónica.

Proposición 3.1 Un problema lineal (3.1) dado en forma canónica, puede escribirse en la forma

0 0
 máx z = c x ,

P0 A0 x0 = b 0 , (3.2)
x0 ≥ 0,



llamada forma estándar.

29
Demostración. La idea consiste en introducir más variables en el problema lineal (3.1). Para este
fin, recordemos que afirmar que x ≤ y equivale a aseverar que existe p ≥ 0 tal que x + p = y;
obsérvese que el intervalo de variación de p es el mismo intervalo de variación de y − x. Basta con
tomar
A0 = ( A U ),
donde U es una matriz identidad m × m y
y1
 
à !
x  .. 
x0 = con y =  .  ,
y
ym
(esto introduce las nuevas variables y1 , . . ., ym que se usarán para reemplazar las desigualdades
por igualdades—una por desigualdad), y hacer b = b0 (los miembros derechos de las desigualda-
des permanecen invariantes) y c0 = ( c 0 ) (ya que las nuevas variables y1 , . . ., ym no deben
intervenir en la función objetivo).
A partir de ahora se denotará la forma estándar de un problema P como P 0 .

Definición 3.2 La operación que permitió escribir P en la forma P 0 consistió en reemplazar la

desigualdad Ai x ≤ bi por el sistema equivalente
(
Ai x + y i = bi ,
yi ≥ 0;

las nuevas variables yi se llamarán variables de holgura.

Ejemplo 3.1 Considérese el problema en forma canónica

 máx z = 3x1 + 2x2 ,



5x1 + 4x2 ≤ 8,




P 3x1 ≤ 7,
2x2 ≤ 7,





x1 , x2 ≥ 0.


Al introducir las variables de holgura y1 , y2 y y3 , el problema P se plantea en forma estándar como

 máx z = 3x1 + 2x2 ,



5x1 + 4x2 + y1 = 8,




0
P 3x1 + y2 = 7,
2x2 + y3 = 7,





x1 , x2 , y1 , y2 , y3 ≥ 0.


Como es de esperarse, la conversa de la proposición 3.1 es cierta, como lo establece la siguiente

proposición. Este resultado se incluye principalmente por su importancia teórica, aunque en la
práctica no se emplea en absoluto—es por formalidad.
Proposición 3.2 Un problema lineal (3.2) dado en forma estándar, puede escribirse en la forma
canónica (3.1).

Demostración. En esencia, para pasar de P 0 a P , la operación consiste en reemplazar la ecuación

A0i x = bi por el sistema de desigualdades
(
Ai x ≤ b i ,
−Ai x ≤ −bi ,

pues −Ai x ≤ −bi es equivalente a Ai x ≥ bi . Así pues, tomemos

à ! à !
A0 b0
A= , b= ,
−A0 −b0

y hagamos c = c0 y x = x0 .

Ejemplo 3.2 Considérese el problema en forma estándar

máx z = x1 + 3x2 + 2x3 ,




x1 + 2x3 = 6,




P0 3x1 − 5x2 + x3 = 7,
4x1 + x2 = 5,





x1 , x2 , x3 ≥ 0.


Por la proposición 3.2, el problema se plantea en forma canónica como

+ 3x2 + 2x3 ,

 máx z =
 x1
+ 2x3 ≤ 6,




 x1
3x1 − 5x2 + x3 ≤ 7,




≤ 5,

 4x1 + x2
P

 −x1 − 2x3 ≤ −6,




 −3x1 + 5x2 − x3 ≤ −7,
−4x1 − x2 ≤ −5,






x1 , x2 , x3 ≥ 0.

3.2. Otras representaciones

Las formas canónica y estándar no son las únicas maneras de expresar un problema lineal; de
hecho, por lo general, encontraremos que el problema no está descrito de ninguna de las dos formas
y debemos modificar la representación de un problema para poder trabajar con él.
Definición 3.3 Un problema lineal en forma mixta es un problema de la forma


 máx z = cx,
 Ax ≤ b,

P



A0 x = b 0 ,

x ≥ 0.

Una consecuencia inmediata de las proposiciones 3.1 y 3.2 es que todo problema lineal en
forma mixta también se puede escribir en forma canónica y en forma estándar.
Hasta ahora hemos trabajado únicamente con problemas lineales en los cuales exigimos x ≥ 0,
y en efecto, los métodos que desarrollaremos se enfocan únicamente a este tipo de problemas. ¿Qué
sucede si existe un conjunto de variables en el problema para las cuales no hay restricción de signo,
i.e., pueden ser positivas o negativas, o bien, que deben ser únicamente no positivas? La respuesta
es representar todo problema dado en forma canónica (y por ende, en forma estándar). La siguiente
proposición explica cómo hacerlo.

Proposición 3.3 Sean I , J ⊂ {1, 2, . . . , n} tales que I ∩ J = ∅ e I ∪ J = {1, 2, . . . , n} (es decir,

sea {I, J} una partición de {1, 2, . . . , n}). El problema lineal P 00 definido por

máx z = cx,



Ax ≤ b,


P 00

 x I ≤ 0,
xJ s.r.s.



(s.r.s. significa “sin restricción de signo”) es equivalente a un problema lineal P en forma canónica.
Demostración. La idea consiste en reemplazar xI por otro vector de variables con signo opuesto
y, para mantener la desigualdad sin cambio, también cambiar el signo de las entradas de A I . Las
modificaciones a las variables del problema para el caso de x J son ciertamente más artificiosas;
todo número real se puede expresar como la diferencia de otros dos números reales (no únicos), y
en particular como la diferencia de dos números reales no negativos. Así, podemos reemplazar x J
por la diferencia de dos vectores de variables no negativas. En resumen, basta con hacer en P 00 los
cambios de variable

xI = −x0I , x0I ≥ 0,
xJ = x0J − x00J , x0J , x00J ≥ 0

para obtener 
 máx z = −c xI + c xJ − c xJ ,
 0 I 0 J 0 J 00

P −AI x0I + AJ x0J − AJ x00J ≤ b,

x0I , x0J , x00J ≥ 0,



que es precisamente un problema lineal en forma canónica. Observemos que la función z depende
de las variables x mientras que la función z 0 depende de las variables x0I , x0J y x00J .
Ejemplo 3.3 Considérese el problema lineal




máx z = 3x1 + x2 + 7x3 + 4x4 ,
x1 + x2 + x3 + x4 ≤ 10,




x 1 + x2 + 2x4 ≤ 15,




P 00 2x1 + x2 + x3 ≤ 10,
3x1 + 2x3 + 7x4 ≤ 10,





x1 , x3 ≤ 0,




x2 , x4 s.r.s.



Tomando I = {1, 3} y J = {2, 4}, y haciendo el cambio de variable

xi = x0i , x0i ≥ 0, i ∈ I,
xj = x0j − x00j , x0j , x00j ≥ 0, j ∈ J,

el problema queda planteado como



 máx z = −3x01 + x02 − x002 − 7x03 + 4x04 − 4x004 ,
−x01 + x02 − x002 − x03 + x04 − x004 ≤ 10,





−x01 + x02 − x002 + 2x04 − 2x004 ≤ 15,




P 00 −2x01 + x02 − x002 − x03 ≤ 10,
−3x01 − 2x03 + 7x04 − 7x004 ≤ 10,




x01 , x03

≥ 0,




x2 , x4 s.r.s.



Observación 3.1 Los problemas de mı́n y de máx son equivalentes, pues mı́n z = − máx(−z).
Por ejemplo,
mı́n z = x, x ≥ 3, =⇒ zmı́n = 3,
máx(−z) = −x, −x ≤ −3, =⇒ (−z)máx = −3.

Observación 3.2 En los problemas lineales no se toman en cuenta restricciones del tipo de desi-
gualdad estricta, porque por un lado, el significado práctico de tales restricciones no es evidente,
y por otro lado, los problemas más sencillos con tales restricciones pueden ser irresolubles. Por
ejemplo (figura 3.1),

 mı́n z = x,

x > 3,
x ≥ 0,



no tiene solución.
 y

x=3

Figura 3.1: Minimizar z = x: un problema de optimización lineal simple pero irresoluble.

3.3. Propiedades de las soluciones

Definición 3.4 Dado un problema lineal

 máx z = cx,

P0 Ax = b, (3.3)
x ≥ 0,



en la forma estándar, se dice que el vector x ∈ Rm es

una solución de P 0 si satisface Ax = b.

una solución realizable o factible de P 0 si satisface Ax = b y x ≥ 0.
una solución óptima de P 0 si x es una solución factible y si dada cualquier otra solución
realizable x0 , se tiene que cx ≥ cx0 .

Al conjunto de soluciones factibles de P 0 usualmente se denomina región de soluciones factibles.

Proposición 3.4 El conjunto de soluciones factibles de un problema P 0 de la forma (3.3) es con-

vexo.
Demostración. Sean x1 y x2 soluciones factibles de P 0 y sea x = λx2 + (1 − λ)x1 con 0 ≤ λ ≤ 1.
Sabemos que Ax1 = b y Ax2 = b, de modo que

Ax = A[λx2 + (1 − λ)x1 ] = λAx2 + (1 − λ)Ax1 = λb + (1 − λ)b = b.

Además, x1 , x2 ≥ 0, de donde
x = λx2 + (1 − λ)x1 ≥ 0
ya que λ, 1 − λ ≥ 0.
Proposición 3.5 El conjunto de soluciones óptimas de un problema P 0 de la forma (3.3) es con-
vexo.
Demostración. Sean x1 y x2 soluciones óptimas de P 0 . Sea x0 = λx2 + (1 − λ)x1 con 0 ≤ λ ≤ 1.
Por la proposición 3.4, tenemos que Ax0 = b y x0 ≥ 0. Además,

cx0 = c[λx2 + (1 − λ)x1 ] = λcx2 + (1 − λ)cx1 ≥ λcx + (1 − λ)cx = cx

para cualquier solución factible x ∈ S.

3.4. Bases
Por conveniencia para la teoría que vamos a desarrollar, de ahora en adelante se hará la siguiente
suposición:

Hipótesis del rango completo El sistema de ecuaciones Ax = b es un sistema consistente (es

decir, tiene al menos una solución) con m < n y no es redundante, i.e., el rango de A es m
(es decir, los m renglones de A son linealmente independientes).

Definición 3.5 Sean I ⊂ {1, 2, . . . , n} con |I| = m y A una matriz de m × n. I es una base del
problema P 0 si las columnas de A asociadas a los índices de I forman una base del conjunto de
columnas de A, i.e., AI es no singular (det AI 6= 0).

Ejemplo 3.4 Considérese el problema

 máx z = 3x1 + 4x2 + 3x3 ,



2x1 + 5x2 + x3 = 7,




0
P x1 + x3 + x4 = 3,
7x2 + 3x4 = 2,





x1 , x2 , x3 , x4 ≥ 0.


Podemos constatar que I = {2, 3, 4} es una base de P 0 pues

 
5 1 0
det AI = det  0 1 1  = 22 6= 0,
 
7 0 3

i.e., AI no es singular. De hecho,

       
2 5 1 0
3  29  7 
 1 = 22  0  + 22  1  − 22  1  .
    
0 7 0 3
Observación 3.3 Dada una base I del problema P 0 , este puede reescribirse como

 máx z = c xI + c xJ ,
 I J

P0 AI xI + AJ xJ = b,
xI , xJ ≥ 0



con J = I c .

Definición 3.6 La solución de base (o solución básica) x̄ asociada a I, donde I es una base del
problema P 0 , se define tomando x̄I = (AI )−1 b y x̄J = 0.

Ejemplo 3.5 En el ejemplo 3.4, la solución de base asociada a I es

 
0
 7 
11
 
x=
 42


 11 
9
− 11

ya que x1 = 0 y
−1 3 3 1 7
x2 7 − 22 7
          
5 1 0 22 22 11
7 15 5
 x3  =  0 1 1   3  =  22 − 22   3  =  42
11  .
          
22
x4 7 0 3 2 7
− 22 7 5
2 9
− 11
22 22

Definición 3.7 Sea x̄I la solución de base asociada a I; x̄I es degenerada si existen una o más
componentes de x̄I iguales a cero y es no degenerada si todas sus componentes son positivas.

Ejemplo 3.6 La solución de base del ejemplo 3.5 es no degenerada pues

7 42 9
11 6= 0, 11 6= 0, − 11 6= 0.

Observación 3.4 A una base corresponde una solución de base única.

Definición 3.8 Una base I se llama realizable o factible si la solución de base correspondiente es
factible, es decir, si x̄I ≥ 0.

Ejemplo 3.7 La base del ejemplo 3.4 no es factible pues

9 9
− 11 < 0, i.e., − 11 ¤ 0.
Ejemplo 3.8 Al problema
 máx z = x1 + x2 ,


2x1 + x2 ≤ 8,




P x1 + 2x2 ≤ 7,
x2 ≤ 3,





x1 , x2 ≥ 0


dado en forma canónica, lo podemos escribir en forma estándar como

máx z = x1 + x2 ,



2x1 + x2 + x3 = 8,




0
P x1 + 2x2 + x4 = 7,
x2 + x5 = 3,





x1 , x2 , x3 , x4 , x5 ≥ 0.


En la correspondiente forma matricial de P 0 tenemos que

 
2 1 1 0 0
A= 1 2 0 1 0 
 
0 1 0 0 1

es una matriz de 3 × 5. Entonces I = {3, 4, 5} es una base factible ya que la solución de base
correspondiente está dada por x1 = x2 = 0 y x3 = 8, x4 = 7, x5 = 3.

3.5. Puntos extremos

Definición 3.9 x es un punto extremo del conjunto convexo S, si no existen x 1 , x2 ∈ S, x1 6= x2
y 0 < λ < 1 tales que x = λx2 + (1 − λ)x1 .

Ejemplo 3.9 La región de la figura 3.2(a) tiene únicamente 4 puntos extremos, mientras que en la
región de la figura 3.2(b) todos los puntos de la circunferencia (i.e., del perímetro del círculo) son
puntos extremos.

r r '$

r r &%

(a) Un rectángulo (b) Un círculo

Figura 3.2: Un subconjunto del espacio puede tener un número finito o infinito de puntos extremos.
Lema 3.1 Sean x1 , . . . , xk puntos de Rn . Cualquier conjunto convexo S que contiene a x1 , . . . , xk
también contiene todas las combinaciones lineales λ1 x1 + · · · + λk xk tales que 0 ≤ λi ≤ 1
para i = 1, . . . , k y λ1 + · · · + λk = 1.

Demostración. Si λk = 1, entonces λ1 x1 + · · · + λk xk = xk ∈ S. Si λk 6= 1, tenemos

λ1 λk−1
µ ¶
λ1 x1 + · · · + λk xk = (1 − λk ) x1 + · · · + xk−1 + λk xk ,
1 − λk 1 − λk

es decir, λ1 x1 + · · · + λk xk es combinación lineal de xk ∈ S y el punto

λ1 λk−1
x1 + · · · + xk−1 . (3.4)
1 − λk 1 − λk

Observemos que, en virtud de que λ1 + · · · + λk−1 = 1 − λk ,

λ1 λk−1 1 − λk
+ ··· + = = 1;
1 − λk 1 − λk 1 − λk

además, si i ∈ {1, . . . , k − 1}, tenemos 0 ≤ λi ≤ λ1 + · · · + λk−1 = 1 − λk , así que

λi
0≤ ≤ 1, i = 1, . . . , k − 1.
1 − λk

Repitiendo el mismo argumento para (3.4) se sigue, por el principio del buen orden, que λ 1 x1 +
· · · + λk xk está en S.

Lema 3.2 Sean x1 , . . ., xk puntos de Rn . El conjunto S formado por todas las combinaciones
lineales λ1 x1 + · · · + λk xk con 0 ≤ λi ≤ 1 y λ1 + · · · + λk = 1, es un conjunto convexo.

Demostración. Supóngase c1 x1 + · · · + ck xk y d1 x1 + · · · + dk xk son puntos de S, i.e., supóngase

0 ≤ ci ≤ 1, c1 + · · · + ck = 1, 0 ≤ di ≤ 1 y d1 + · · · + dk = 1. Entonces, si 0 ≤ λ ≤ 1, se tiene
que 0 ≤ 1 − λ y además

0 ≤ (1 − λ)ci ≤ 1 − λ, 0 ≤ λdi ≤ λ,

de modo que
0 ≤ (1 − λ)ci + λdi ≤ 1 − λ + λ = 1; (3.5)
más aún, se tiene

[(1 − λ)c1 + λd1 ] + · · · + [(1 − λ)ck + λdk ] = (1 − λ)(c1 + · · · + ck ) + λ(d1 + · · · + dk )

(3.6)
= (1 − λ) + λ = 1.
De 3.4 y (3.6) se sigue que,

(1 − λ)(c1 x1 + · · · + ck xk ) + λ(d1 x1 + · · · + dk xk )
= [(1 − λ)c1 + λd1 ]x1 + · · · + [(1 − λ)ck + λdk ]xk

también está en S.
Por el lema 3.1 se deduce que, si x1 , x2 , . . ., xk son los puntos extremos de un conjunto S,
entonces todo punto de S se puede expresar de la forma λ 1 x1 + · · · + λk xk con 0 ≤ λi ≤ 1
para i = 1, . . ., k, y λ1 + · · · + λk = 1 (para ver esto de manera sencilla no hay que olvidar la
definición de punto extremo); conversamente, por el lema 3.2, toda expresión de la forma λ 1 x1 +
· · · + λk xk se encuentra en S. Así pues, los puntos de S son aquellos que se pueden expresar como
λ1 x1 + · · · + λk xk con 0 ≤ λi ≤ 1 para i = 1, . . ., k, y λ1 + · · · + λk = 1.
Dado que el conjunto de soluciones óptimas es convexo, una consecuencia inmediata de la
proposición 3.5 es:

Proposición 3.6 Si la función objetivo de un problema de programación lineal alcanza su máximo

en más de un punto, entonces también alcanza su máximo en cualquier combinación convexa de
esos puntos.
La siguiente proposición nos permite conocer aún más sobre las soluciones óptimas de la fun-
ción objetivo.

Proposición 3.7 Si el problema de programación lineal P admite una solución óptima, entonces
existe al menos un punto extremo de la región de soluciones factibles S donde la función objetivo
alcanza su máximo.
Demostración. Sea zmáx el máximo de la función objetivo y sea x0 ∈ S tal que zmáx = cx0 . Si x0
es punto extremo, está demostrado. Así pues, supongamos que x 0 no es un punto extremo, y sean
x1 , . . ., xk los puntos extremos de S. Dado que a cualquier punto de un conjunto convexo podemos
escribirlo como combinación lineal de puntos extremos, existen constantes λ 1 , . . ., λk tales que
λ1 + · · · + λk = 1, 0 ≤ λi ≤ 1 para i = 1, . . ., k, y
k
X
x0 = λi x i .
i=1

Por consiguiente, si xh es un punto extremo de S tal que cxh = máxni=1 {cxi }, tenemos
k
X k
X k
X k
X
cx0 = c λi x i = λi cxi ≤ λi cxh = cxh λi = cxh ;
i=1 i=1 i=1 i=1

por tanto, zmáx ≤ cxh , de modo que necesariamente zmáx = cxh . Entonces, z alcanza su máximo
en un punto extremo xh .
3.6. Relaciones entre bases y puntos extremos
Antes de seguir adelante, hagamos un sumario de lo que sabemos hasta ahora. Hemos demos-
trado que todo problema P puede plantearse en forma estándar P 0 , y sabemos que el conjunto de
soluciones factibles de P 0 es convexo; más aún, también hemos probado que el conjunto de solu-
ciones óptimas de P 0 es convexo, y que si existe una solución óptima para P 0 entonces también
existe un punto extremo de la región de soluciones factibles donde la función objetivo alcanza su
máximo (o mínimo, en virtud de que los problemas de maximizar y minimizar son en esencia lo
mismo). Esto nos habilita para encontrar el óptimo de un problema lineal evaluando la función ob-
jetivo en los puntos extremos de la región de soluciones factibles, pero al mismo tiempo nos lleva
a preguntar la manera en que podemos encontrar los puntos extremos de la misma.
La importancia de las siguientes proposiciones reside en el hecho que nos proporcionan una
manera no geométrica y relativamente simple de encontrar los puntos extremos de cualquier región
de soluciones factibles, pues nos garantizan que los puntos factibles extremos de un problema lineal
están completamente determinados por las soluciones de base factibles de las ecuaciones que lo
definen.
Para simplificar la notación y los enunciados de las proposiciones siguientes, a menos que se
indique lo contrario, S denotará la región de soluciones factibles de un problema P 0 en la forma
estándar, I representará una base factible de P 0 y A será la matriz de m × n correspondiente a P 0 .

Proposición 3.8 Para toda base I existe un punto extremo x de S tal que x es la solución básica
asociada a I . En otras palabras, si existe un conjunto de m columnas de A linealmente indepen-
dientes (sin pérdida de generalidad y por simplicidad, supongamos que son las m primeras) y si
puede encontrarse un conjunto de valores x1 , . . ., xm ≥ 0 tales que x1 A1 + · · · + xm Am = b,
entonces el punto x = (x1 , x2 , . . . , xm , 0, . . . , 0) ∈ Rn es un punto extremo de S .

Demostración. Procedamos por reducción al absurdo. Supongamos que x no es punto extremo,

i.e., que existen dos puntos distintos entre sí

p = (p1 , . . . , pm , pm+1 , . . . , pn ),
q = (q1 , . . . , qm , qm+1 , . . . , qn )

en S tales que
x = λp + (1 − λ)q con 0 < λ < 1.

Si tuviésemos pi > 0 ó qi > 0 para alguna i ∈ {m + 1, . . . , n}, entonces tendríamos x i =

λpi + (1 − λ)qi > 0, lo cual es imposible por nuestras hipótesis. Entonces p y q deben ser de la
forma

p = (p1 , . . . , pm , 0, . . . , 0),
q = (q1 , . . . , qm , 0, . . . , 0).
Además, como p y q están en S, son soluciones del problema dado,

Ap = p1 A1 + · · · + pm Am = b,
Aq = q1 A1 + · · · + qm Am = b,

de modo que, por la independencia lineal de A1 , . . ., Am , tenemos que pi = qi para i = 1,

. . ., m. En consecuencia, p = q = x, una contradicción. Por tanto, x no puede ser escrito como
combinación convexa de dos puntos distintos, i.e., x es punto extremo.
Los siguientes resultados establecen la fundamentación necesaria para la proposición conversa
de la proposición 3.8, a saber, la proposición 3.10.

Lema 3.3 Si x1 , . . ., xk , a1 , . . ., ak ∈ R con x1 , . . ., xk > 0, entonces existe ε > 0 tal que

xi + εai > 0,
xi − εai > 0

para i = 1, . . ., k .
Demostración. Si ai = 0 para alguna i ∈ {1, . . . , k}, entonces

xi + εai = xi > 0,
xi − εai = xi > 0

para toda ε > 0. Sean an1 , . . ., anm las ai de {a1 , . . . , ak } que no son cero, y definamos
xnj
εj =
2|anj |
para j = 1, . . ., m; haciendo ε = mı́n{ε1 , . . . , εm } tenemos
xnj
xnj + εanj ≥ xnj − εj |anj | = xnj − |an | = 12 xnj > 0,
2|anj | j
xnj
xnj − εanj ≥ xnj − εj |anj | = xnj − |an | = 12 xnj > 0
2|anj | j

para j = 1, . . ., m.

Proposición 3.9 Sea x un punto extremo de S con k componentes estrictamente positivas; sin
pérdida de generalidad y por simplicidad, supongamos que son x 1 , . . . , xk > 0. Entonces las
columnas de A asociadas a dichas xi forman un conjunto linealmente independiente.
Demostración. Procedamos nuevamente por reducción al absurdo. Como x es un punto extremo
de S, en particular es una solución factible, así que
k
X
Ax = xi Ai = b. (3.7)
i=1
Supongamos que A1 , . . ., Ak son linealmente dependientes, o sea que existen constantes a 1 ,
. . ., ak ∈ R con al menos una ai 6= 0 tales que
k
X
ai Ai = 0. (3.8)
i=1

Así pues, de (3.7) y (3.8), se sigue que para toda β > 0,

k
X
(xi + βai )Ai = b,
i=1
Xk
(xi − βai )Ai = b.
i=1

En particular, por el lema 3.3, debe existir alguna ε > 0 tal que x i + εai > 0 y xi − εai > 0
para i = 1, . . ., k. Definamos

p = (x1 + εa1 , . . . , xk + εak , 0, . . . , 0),

q = (x1 − εa1 , . . . , xk − εak , 0, . . . , 0);

claramente p, q ∈ S y p 6= q. Además,

x = 12 p + 21 q,

una contradicción, pues x es punto extremo. Se sigue que A 1 , . . ., Ak son columnas linealmente
independientes.

Corolario 3.1 El número máximo de componentes estrictamente positivas de un punto extremo x

es m.
Demostración. Puesto que el máximo número de columnas linealmente independientes de A es m
(su rango), el resultado se sigue de la proposición anterior.

Observación 3.5 Si A es una matriz m × n, entonces

à !
n n!
=
m (n − m)! m!

es una cota superior para el número de conjuntos de m columnas linealmente independientes. Esto
sugiere una gran cantidad de posibilidades que se deben analizar para poder encontrar el punto
extremo donde la función objetivo alcanza su máximo, y por ende un gran cantidad de tiempo
computacional. Sin embargo, en la práctica se constata que el algoritmo simplex sólo necesitará un
número de iteraciones aproximadamente de 3(n + m) para alcanzar el máximo.
Proposición 3.10 Para todo punto extremo x de S existe una base I tal que x es la solución básica
asociada a I . En otras palabras, para todo punto extremo x = (x 1 , x2 , . . . , xm , 0, . . . , 0)T ∈ Rn
de S podemos encontrar m columnas linealmente independientes de A (sin pérdida de generalidad
y por simplicidad, supongamos que son las m primeras) tales que x 1 A1 + · · · + xm Am = b.

Demostración. Sea x un punto extremo de S. Sin pérdida de generalidad, supongamos que las
primeras k componentes de x son no nulas (i.e., positivas por las restricciones de no negatividad),
es decir, que x = (x1 , . . . , xk , 0, . . . , 0)T con x1 , . . ., xk > 0. Entonces, por la proposición 3.8,
A1 , . . ., Ak son linealmente independientes y, por el corolario 3.1, k ≤ m. Si k = m, está de-
mostrado. Si k < m, de álgebra lineal sabemos que podemos encontrar m − k columnas, digamos
por simplicidad y sin pérdida de generalidad, Ak+1 , . . ., Am tales que A1 , . . ., Am sean lineal-
mente independientes. Puesto que x es punto extremo de S, es solución factible así que satisface la
igualdad
x1 A1 + · · · + xk Ak + 0Ak+1 + · · · + 0Am + · · · + 0An = b,

de modo que en particular también cumple

x1 A1 + · · · + xk Ak + 0Ak+1 + · · · + 0Am = b. (3.9)

Por la independencia lineal de A1 , . . ., Am la combinación lineal (3.9) es única y, por ende, ha-
ciendo I = {1, . . . , m} tenemos xI = (AI )−1 b. Observemos que en este caso I no tiene que estar
determinada de manera única y que la solución x es degenerada.
De las proposiciones 3.8 y 3.10 podemos concluír que los puntos factibles extremos de un pro-
blema lineal están completamente determinados por las soluciones básicas factibles de las ecuacio-
nes que lo definen.

Definición 3.10 Una restricción de un conjunto de restricciones se llama redundante si es una

combinación lineal de las otras restricciones del conjunto.

Ejemplo 3.10 Cada una de las ecuaciones del sistema



 x1 + x 2 = 2,

 x2 + x3 = 3,



x1 + x3 = 7,

x1 + x 2 + x 3 = 6

es redundante.

Ejemplo 3.11 Consideremos un programa lineal en forma estándar tal que el rango de A sea igual
a su número de renglones m; entonces el sistema Ax = b no tiene restricciones redundantes.
Ejercicios del capítulo 3
1. Considerar el problema
máx z = x1 + 2x2 + 3x3 ,

 s.a.


x1 + 2x2 − 3x3 = 1,



P 2x1 − x2 − 5x3 ≤ 2,

x1 + 3x2 − x3 ≥ 1,




x1 , x2 , x3 ≥ 0.


a) Poner P en forma estándar y en forma canónica.

b) Considerar P en forma estándar; se tiene m = 3, n = 5. Escribir A 1 , A4 . Sean I =
{2, 3}, J = {3, 4, 5}; escribir bI , cJ , AI , AJ , AJI .

2. Considerar el problema de transporte

mı́n z = 5x1 + 6x2 + 3x3 + 3x4 + 5x5 + 4x6 ,

s.a.



x1 + x 2 + x 3 ≤ 550,





x4 + x5 + x6 ≤ 350,



 x1 + x4 ≥ 400,
x2 + x5 ≥ 300,




x3 + x6 ≥ 200,





xi ≥ 0, i = 1, . . . , 6.


a) Demostrar que en P las desigualdades pueden cambiarse por igualdades sin agregar
variables de holgura.
b) Si hay alguna restricción redundante, eliminarla.
c) Demostrar que {3, 4, 5, 6} es una base, pero no es factible. Demostrar que {1, 2, 5, 6}
es una base factible y que {1, 2, 3, 4} es una base óptima.
d) Demostrar que AI es triangular, donde I = {1, 2, 5, 6}. Mostrar que el sistema A I xI =
b puede ser resuelto directamente por sustitución.
e) Escribir P en forma explícita con respecto a I.

3. Poner en forma canónica el problema

máx z = cI xI + cJ xJ + cK xK ,

s.a.


AIL xI + AJL xJ + AK

L xK ≤ b L ,



AIM xI + AJM xJ + AK M xK ≥ b M ,
AIN xI + AJN xJ + AK

L xK = b N ,




xI ≥ 0, xJ ≤ 0, xK s.r.s.


donde c = ( cI cJ cK ), los conjuntos I, J, K son ajenos por pares, I ∪ J ∪ K =

{1, . . . , n}, los conjuntos L, M , N son ajenos por pares y L ∪ M ∪ N = {1, . . . , m}.
4. Demostrar que I = {1, 4, 5} es una base realizable del problema

máx z = x1 + 2x2 + 3x3 ,


s.a.



x1 + 2x2 − 3x3 + x4 = 1,



 2x1 − x2 − 5x3 + x5 = 2,
x1 + 3x2 − x3 − x6 = 1,




xi ≥ 0, i = 1, . . . , 6.


5. Escribir el problema
mı́n z = x1 − 2x2 − x3 ,

s.a.



x1 + 2x2 − 3x3 = 1,





2x1 − x2 − 5x3 ≤ 2,



 x1 + 3x2 − x3 ≥ 1,
x1 , x2 ≥ 0,




s.r.s.


x3
en forma canónica y estándar.

6. Verificar que I = {1, 4, 5} es una base realizable para el problema lineal

máx z = x1 + 2x2 + 3x3 ,


 s.a.


x1 + 2x2 − 3x3 ≤ 1,



 2x1 − x2 − 5x3 ≤ 2,
x1 + 3x2 − x3 ≥ 1.


7. Escribir el problema

máx z = 5x1 + 2x2 + x3 − x4 ,


s.a.



2x1 + x2 − x3 + x4 ≤ 5,




3x1 − x2 + 2x3 + x4 ≤ 2,





−x2 − x3 ≤ −3,



 x1 + x2 + x3 + x4 ≤ 4,
x1 s.r.s.,








 x2 , x4 ≥ 0,
x3 ≤0


en forma canónica.

8. En el problema
máx z = 2x1 + 3x2 ,

 s.a.



x1 + 2x2 + x3 = 7,


 x1 + x4 = 8,
x1 , x2 , x3 , x4 ≥ 0

verificar que I = {1, 3} es base, dar la solución básica sociada y decir si es una base dege-
nerada.
Capítulo 4

Algoritmo simplex

Ahora que ya hemos establecido las principales propiedades de las soluciones de un problema
de programación lineal y sus relaciones con las bases procederemos a desarrollar un algoritmo
que nos permita analizar las soluciones asociadas a las bases; con ayuda de la información que
nos proporciona la función objetivo seremos capaces de elegir una nueva base que la optimice y
sabremos en qué momento hemos obtenido una solución óptima.

4.1. Optimalidad y factibilidad

La solución óptima de un programa lineal con m ecuaciones y n incógnitas puede obtenerse
resolviendo à !
n n!
=
m m! (n − m)!
conjuntos de ecuaciones simultáneas. Este procedimiento es ineficiente. Primero, porque el número
de posibles
¡15¢
soluciones básicas puede ser muy grande. Por ejemplo, si m = 5 y n = 15, entonces se
tienen 10 = 3003 conjuntos de ecuaciones simultáneas que hay que resolver. Segundo, muchas
de estas soluciones pueden ser no factibles o no existentes. Tercero, la función objetivo juega un
papel pasivo en el cálculo, puesto que se usa únicamente después de haber determinado todas las
soluciones básicas factibles.
El algoritmo simplex está diseñado específicamente para evitar estas deficiencias.
Se empieza con una solución básica factible y nos movemos en una sucesión de soluciones
básicas factibles (no redundantes) de tal manera que cada nueva solución mejora el valor de la
función objetivo.
Las principales características del algoritmo simplex son dos fundamentalmente:
Optimalidad Garantiza que no se tomará una solución que desmejore el valor de la función obje-
tivo.
Factibilidad Garantiza que sólo soluciones factibles se encontrarán durante el cálculo.

47
4.2. Motivación: problema del inversionista

Antes de presentar formalmente el algoritmo simplex, y con objeto de explicarlo de una manera
clara, veamos un problema particular.
El problema

máx z = 50x + 80y,
s.a.



≥ 25,




 x
y ≤ 50,

P


 − 32 x + y ≤ 0,
x+ y ≤ 100,






x, y ≥0

(cuya representación geométrica se muestra en la figura 4.1) está en forma mixta. Transformando
y
3
2x +y =0

C D
y = 50
B

z = 50x + 80y = 6500

E x
A

x + y = 100
x = 25

Figura 4.1: Región de soluciones factibles del problema del inversionista.

el problema a forma estándar se tiene


máx z = 50x + 80y,
s.a.



− h1




 x = 25,
y + h2 = 50,

0
P (4.1)


 − 32 x + y + h3 = 0,
x+ y + h4 = 100,






x, y, h1 , h2 , h3 , h4 ≥ 0.
4.2.1. Sistemas de ecuaciones
Reescribamos el problema P 0 dado en forma estándar como

 máx

 s.a.
z
−z + 50x + 80y = 0,





x − h1 = 25,



y + h2 = 50,
− 32 x +

y + h3 = 0,




x+ y + h4 = 100,





x, y, h1 , h2 , h3 , h4 ≥ 0,


para simplificar las operaciones que realizaremos a continuación.

Supongamos que conocemos una solución correspondiente a un punto extremo de la región de
soluciones factibles del problema, digamos, el punto A, donde
75
x = 25, y = 0, h1 = 0, h2 = 50, h3 = 2 , h4 = 75, z = 1250;
esta solución se deduce inmediatamente a partir del sistema
−z + 80y + 50h1 = −1250,



x − h1 = 25,





 y + h2 = 50,

 y − 32 h1 + h3 = 75
2 ,




 y + h1 + h4 = 75,
x, y, h1 , h2 , h3 , h4 ≥ 0,


que es equivalente al sistema del problema (4.1) mediante una sucesión de operaciones elementales,
si hacemos y = 0 y h1 = 0; estas dos variables son las únicas que aparecen en la función objetivo.
Observemos que, en virtud de que y = 0 y h1 = 0, el punto A corresponde a la intersección de
los lugares geométricos x = 25 y y = 0, y ello nos permite determinar analíticamente el punto del
espacio de soluciones al cual corresponde la solución del sistema.
Ahora bien, el coeficiente de y en la función objetivo, a saber 80, es positivo. Si incrementamos
el valor de y a cualquier valor positivo (manteniendo h1 = 0), es evidente que el valor de z se
incrementaría porque el correspondiente valor de z estaría dado por
z = 1250 + 80y
(además, h2 , h3 y h4 disminuirían, y x y h1 quedarían igual). Así, el valor de la función objetivo
aumentaría en 80 por cada unidad de incremento para y.
Similarmente, el coeficiente de h1 en la función objetivo, a saber 50, es positivo. Si aumenta-
mos h1 a cualquier valor positivo (y dejamos y = 0), el valor de z también se incrementaría pues
tendríamos
z = 1250 + 50h1
(asimismo, x aumentaría, y h3 y h4 disminuirían).
Observación 4.1 El algoritmo simplex nos indica para dónde desplazarnos para llegar al punto
extremo óptimo. El algoritmo elige el camino que, bajo el criterio de los coeficientes de la fun-
ción objetivo, nos da un incremento de ésta. Sin embargo, este criterio no nos garantiza el mayor
incremento de la función objetivo.
Como ahora nos interesa maximizar z, elegimos incrementar la variable que nos dé un mayor
incremento por unidad, a saber, y. Es razonable, por consiguiente, tratar de hacer el valor de y
tan grande como sea posible, pues mientras mayor sea dicho incremento mayor será el incremento
de z. El valor de y no puede aumentar arbitrariamente mientras h 1 permanece igual a cero, pues
los correspondientes valores de las demás variables están dados por

x = 25,
h2 = 50 − y,
75
h3 = 2 − y,
h4 = 75 − y.

Se observa que el mayor valor que y puede tomar para seguir teniendo variables con valores posi-
tivos es y = 75
2 . Así, obtenemos la nueva solución factible
75 25 75
x = 25, y= 2 , h1 = 0, h2 = 2 , h3 = 0, h4 = 2 , z = 4250,

que corresponde al punto B. Como veremos posteriormente, hemos hecho una iteración del algo-
ritmo simplex. Nuevamente, esta solución se puede obtener de un sistema equivalente al anterior, a
saber, el sistema
−z − 80h3 = −4250,


 + 170h1
x − h1 = 25,




3
− = 25


2 h 1 + h 2 h 3 2 ,
3 75

 y − h
2 1 + h 3 = 2 ,
 5 75



 2 h1 − h3 + h4 = 2 ,
x, y, h1 , h2 , h3 , h4 ≥ 0,


haciendo h1 = 0 y h3 = 0. Observamos que (en este punto B) la función objetivo aumentó de

valor, como era de esperarse.
Si ahora incrementamos el valor de h3 (manteniendo fija h1 = 0) la función objetivo decrece
ya que tendríamos
z = 4250 − 80h3 .
Esto se debe a que el coeficiente de la variable h3 en la función objetivo, a saber −80, es negativo.
En contraste, si incrementamos h1 (y dejamos h3 = 0), se daría el caso que

z = 4250 + 170h1 ,

y por cada unidad que incrementásemos h1 la función objetivo aumentaría 170 unidades. Así pues,
puesto que estamos maximizando, habremos de incrementar h 1 tanto como sea posible. Tomando
h3 = 0, tenemos

x = 25 + h1 ,
25
h2 = 2 − 23 h1 ,
75
y= 2 + 23 h1 ,
75
h4 = 2 − 25 h1 ,
25
así que el máximo valor que h1 puede tomar para obtener una solución factible es h1 = 3 . De esta
manera obtenemos la solución factible
100 25 50 17000
x= 3 , y = 50, h1 = 3 , h2 = 0, h3 = 0, h4 = 3 , z= 3 ,

que determina al punto C. Como es de esperarse, esta solución también se puede obtener de un
sistema equivalente a los anteriores, a saber,
340 100
−z − = − 17000

 3 h2 + 3 h3 3 ,
2 2 100

x + 3 h2 − 3 h3 = 3 ,




2 2
− = 25

 h1 + 3 h2 3 h3 3 ,

 y + = 50,
− 53 h2 + 23 h3 + h4 = 50

3 ,




x, y, h1 , h2 , h3 , h4 ≥ 0,


si hacemos h2 = 0 y h3 = 0.
Podemos ahora incrementar la variable h3 , ya que su coeficiente es positivo. Manteniendo
h2 = 0, vemos que los nuevos valores de las variables están dados por
100 2
x= 3 + 3 h3 ,
25 2
h1 = 3 + 3 h3 ,
y = 50,
50
h4 = 3 − 32 h3 ,

de modo que el máximo valor que h3 puede tomar es h3 = 25, y en ese caso obtenemos la solución
factible

x = 50, y = 50, h1 = 25, h2 = 0, h3 = 25, h4 = 0, z = 6500,

que corresponde al punto D y que se desprende del sistema equivalente

−z − 30h2 − 50h4 = −6500,



x − h2 + h4 = 50,




h1 − h 2

 + h4 = 25,

 y + h2 = 50,
− 52 h2 + h3 + 32 h4




 = 25,
x, y, h1 , h2 , h3 , h4 ≥ 0,

Es imposible continuar mejorando la solución (de esta manera) debido a que todos los coeficientes
que aparecen asociados a las variables independientes en la función objetivo, a saber, −30 y −50,
son negativos. Pronto veremos que esto también implica que no podemos mejorar la solución de
ninguna otra manera (teorema 4.2). Como ya no podemos deplazarnos a ningún punto de tal manera
que aumente el valor de z, la solución óptima es zmáx = 6500.

4.2.2. Tablas
Todas las operaciones que hemos realizado hasta ahora en nuestro problema de maximización
se pueden llevar a cabo empleando únicamente los coeficientes de los sistemas de ecuaciones an-
teriores. Por ende, podemos simplificar las operaciones que hemos realizado representando cada
sistema de ecuaciones por una tabla que muestre los coeficientes correspondientes. Es usual escri-
bir los coeficientes de la función objetivo en la última línea de la tabla y así lo haremos nosotros
(este es un legado de los inicios de la programación lineal).
La tabla que asignaremos a la representación del problema en forma estándar es

x y h 1 h2 h3 h4
1 0 −1 0 0 0 25
0 1 0 1 0 0 50
− 32 1 0 0 1 0 0
1 1 0 0 0 1 100
50 80 0 0 0 0 0

Si ignoramos el primer renglón (es decir, los títulos de las columnas), esta tabla en realidad es la
matriz de los coeficientes del sistema. (Bueno, para ser más precisos hemos de observar que hemos
obviado el coeficiente de −z, pues siempre es el mismo.) Mediante operaciones elementales de
matrices obtenemos la tabla

x y h 1 h2 h3 h4
1 0 −1 0 0 0 25
0 1 0 1 0 0 50
0 1 − 32 0 1 0 75
2
0 1 1 0 0 1 75
0 80 50 0 0 0 −1250

Es inmediato notar que las columnas que corresponden a x, h 2 , h3 y h4 están formadas por un
único 1 y 0’s en las demás entradas, y sólo hay uno de tales 1’s en cada reglón. Además, el valor de
la variable asignada a cada una de tales columnas es el valor que se encuentra en el mismo renglón
de su 1 en la última columna. Para facilitar la detección de tales variables, reescribiremos la tabla
anexando una columna al inicio de la tabla que indique la variable correspondiente, y obtendremos
una tabla de la forma
x y h 1 h2 h3 h4
x 1 0 −1 0 0 0 25
h2 0 1 0 1 0 0 50
h3 0 1 − 32 0 1 0 75
2
h4 0 1 1 0 0 1 75
−z 0 80 50 0 0 0 −1250

En esta tabla el valor de las variables que se tienen en la primera columna es el que se muestra en la
última columna. Hemos incluido la variable −z aún cuando no tiene una columna asociada pues,
como ya se indicó, la obviamos anteriormente.
En base a los razonamientos ya hechos con los sistemas de ecuaciones, elegimos a la variable y
por tener el mayor de los coeficientes en la función objetivo. Para ver el máximo valor que y puede
tomar (para seguir teniendo soluciones factibles) consideramos el conjunto de coeficientes de la
columna de y que son estrictamente positivos; tomamos los valores de las variables asignadas al
correspondiente renglón y lo dividimos entre el coeficiente de la columna de y. El menor de tales
valores es el máximo valor posible para y. En otras palabras, el máximo valor para y está dado por

h2 h3 h4
½ ¾ n o
mı́n , , = mı́n 50, 75
2 , 75 =
75
2 .
1 1 1

Este valor corresponde al renglón de la variable h3 , y por ende haremos que la entrada de la matriz
que corresponde al renglón de h3 y a la columna de y contenga un 1 e igualaremos a cero las
demás entradas de dicha columna. Además, a la izquierda de la tabla el renglón etiquetado con la
variable h3 será reetiquetado con y. Esta forma de proceder puede interpretarse en términos de las
ecuaciones del sistema, en la misma manera en que ya lo hicimos anteriormente. Con respecto a la
primera columna, diremos que la variable h3 sale y que la variable y entra en su lugar. También es
usual denotar este paso del algoritmo señalando la columna de la variable que entra y el renglón de
la que sale:
x y h 1 h2 h3 h4
x 1 0 −1 0 0 0 25
h2 0 1 0 1 0 0 50
h3 0 1 − 32 0 1 0 75
2 ← sale
h4 0 1 1 0 0 1 75
−z 0 80 50 0 0 0 −1250
↑
entra
Siguiendo este orden de ideas, obtenemos la siguiente sucesión de tablas:

x y h 1 h2 h3 h4
x 1 0 −1 0 0 0 25
3 25
h2 0 0 2 1 −1 0 2 ← sale
y 0 1 − 32 0 1 0 75
2
5 75
h4 0 0 2 0 −1 1 2
−z 0 0 170 0 −80 0 −4250
↑
entra

x y h1 h2 h3 h4
2
x 1 0 0 3 − 32 0 100
3
2
h1 0 0 1 3 − 32 0 25
3
y 0 1 0 1 0 0 50
h4 0 0 0 − 53 2
3 1 50
3 ← sale
−z 0 0 0 − 340
3
100
3 0 − 17000
3
↑
entra

x y h1 h2 h3 h4
x 1 0 0 −1 0 1 50
h1 0 0 1 −1 0 1 25
y 0 1 0 1 0 0 50
h3 0 0 0 − 52 1 3
2 25
−z 0 0 0 −30 −50 0 −6500

Por lo tanto zmáx = 6500, pues ya tenemos únicamente valores menores o iguales que cero como
coeficientes de la función objetivo z.

4.3. Forma explícita

En esta sección veremos las mismas operaciones que hemos realizado sobre la tabla del ejem-
plo del problema del inversionista, pero en un contexto más general, para un problema arbitrario.
Estableceremos las estructuras algebraicas elementales para formalizar el algoritmo simplex.
4.3.1. Tablas en el caso general
Cualquier tabla formada por los coeficientes de un problema arbitrario siempre tiene la forma

x1 x2 ··· xm xm+1 ··· xn

xσ(1) y11 y12 ··· y1m y1,m+1 ··· y1n y10
xσ(2) y21 y22 ··· y2m y2,m+1 ··· y2n y20
.. .. .. .. .. .. .. .. ..
. . . . . . . . .
xσ(m) ym1 ym2 · · · ymm ym,m+1 · · · ymn ym0
−z r1 r2 ··· rm rm+1 ··· rn −z0
donde x1 , . . ., xn son las variables del problema planteado en forma estándar y la función
σ : {1, . . . , m} → {1, . . . , n}
es uno a uno. Si, sin pérdida de generalidad, suponemos que las variables x 1 , . . ., xm se encuentran
en la primera columna (i.e., suponemos que σ(i) = i para i = 1, . . ., m), entonces la tabla toma la
forma
x1 x2 · · · xm xm+1 · · · xn
x1 1 0 · · · 0 y1,m+1 · · · y1n y10
x2 0 1 · · · 0 y2,m+1 · · · y2n y20
.. .. .. . . .. .. .. .. ..
. . . . . . . . .
xm 0 0 ··· 1 ym,m+1 · · · ymn ym0
−z 0 0 ··· 0 rm+1 · · · rn −z0
Esta suposición es útil para simplificar las demostraciones de algunos enunciados que presentare-
mos a continuación.

4.3.2. Formalización de las tablas

Antes de poder seguir adelante debemos presentar la forma explícita de un problema de progra-
mación lineal. Para poder aplicar el algoritmo simplex a un problema lineal es necesario plantear
el problema en forma explícita. Veamos la transformación de un problema lineal en forma estándar
a un problema en forma explícita con respecto a una base. Consideremos el problema

 máx

s.a.
z = cx,
P0 Ax = b,

x ≥ 0.


Como ya vimos en la sección 3.4, dada una base I del problema P 0 , se puede reescribir P 0 como
z = c I xI + c J xJ ,

 máx

s.a.
P0 AI xI + AJ xJ = b,

xI , xJ ≥ 0

con J = {1, . . . , n} \ I. Observemos que la idea de escribir z = cx como

z = c I xI + c J xJ (4.2)

sugiere separar las variables asociadas a I, que de ahora en adelante denominaremos variables
básicas de (o de la base) I, de las demás variables del problema, que a partir de ahora llamaremos
variables no básicas (o que no pertenecen a la base). Observemos que no se debe confundir a la
solución de base x̄ correspondiente a la base I, definida por x̄ I = (AI )−1 b y x̄J = 0, con el vector
de las variables (básicas y no básicas) del problema x = x I + xJ .

Transformación de las restricciones Al multiplicar la restricción

AI xI + A J xJ = b

por (AI )−1 por la izquierda resulta

(AI )−1 AI xI + (AI )−1 AJ xJ = (AI )−1 b,

es decir,
xI + (AI )−1 AJ xJ = (AI )−1 b. (4.3)
Observemos que (AI )−1 b determina las componentes no nulas de la solución de base corres-
pondiente a la base I, i.e., x̄I = (AI )−1 b. Es usual denotar la entrada (i, j) de la matriz
(AI )−1 A como yij ; esta es la notación que nosotros emplearemos para las demostracio-
nes subsecuentes y es la que ya hemos usado en las tablas. Observemos que (A I )−1 A =
((AI )−1 A1 , . . . , (AI )−1 An ), es decir, los coeficientes asociados a la k-ésima variable x k
corresponden al vector (AI )−1 Ak ; también es usual denotar a dicho vector como y k , es de-
cir, se define y k = (AI )−1 Ak = (y1k , . . . , ymk ).

Transformación de la función objetivo Al multiplicar (4.3) por cI por la izquierda obtenemos

cI xI + cI (AI )−1 AJ xJ = cI (AI )−1 b. (4.4)

Al restar (4.4) de (4.2) tenemos

0xI + [cJ − cI (AI )−1 AJ ]xJ = z − cI (AI )−1 b.

Así, hemos escrito la función objetivo con los coeficientes de las variables básicas iguales a
cero, de tal forma que solamente las variables no básicas aparecen en la función objetivo.

Ahora bien, si definimos

z0 = cI (AI )−1 b
y
zj = cI (AI )−1 Aj , j ∈ J,
entonces la forma explícita de P 0 con respecto a I es

máx z,
 s.a.



0xI + (cJ − zJ )xJ = z − z0 , (4.5)


 xI + (AI )−1 AJ xJ = (AI )−1 b,
xI , xJ ≥ 0.


Veamos más detenidamente la expresión (4.5). El renglón que indica máx z se incluye sólo por
razones informativas ya que la función objetivo es en realidad

0xI + (cJ − zJ )xJ = z − z0 . (4.6)

Escribir la función objetivo de esta manera es conveniente debido a que posteriormente la expresión
z − z0 nos proporcionará información con respecto a la solución de base asociada a I, en particular
nos permitirá saber si dicha solución es óptima (teorema 4.2). Para las tablas es usual escribir la
ecuación equivalente
−z + 0xI + (cJ − zJ )xJ = −z0 ,
y considerar a −z como una variable más del problema (que nunca entra a los cálculos). A su vez,
la escritura de las restricciones en la forma

xI + (AI )−1 AJ xJ = (AI )−1 b (4.7)

nos habilitará a cambiar de base de manera relativamente sencilla mediante un proceso denominado
pivoteo (un pivote es una base giratoria de algún proceso mecánico, así que este nombre está dado
en sentido figurado).
Es inusual emplear la representación de P 0 en forma explícita directamente, sino que se utiliza
la correspondiente tabla
x
xI U (AI )−1 AJ (AI )−1 b (4.8)
−z cJ − zJ −z0
donde U es una matriz identidad de m × m, para los cálculos. A partir de esta tabla se obser-
va que las variables que aparecen en la primera columna son las variables básicas del problema
correspondientes a la base I.
Ciertamente, para cada posible base existe una correspondiente forma explícita (y por ende una
correspondiente tabla), así que para todo problema lineal hay igual número de soluciones básicas y
de formas explícitas (y de tablas). La idea esencial del método simplex es analizar los coeficientes
que se encuentran en la representación (4.5), es decir, los de la tabla 4.8, y en base a ellos decidir si
la solución de base correspondiente es óptima. Por último, hay que observar que es usual escribir las
bases como simples conjuntos, aunque en la práctica deben ser consideradas conjuntos ordenados.
Para efectos de la teoría de programación lineal habremos de diferenciar entre la base, digamos,
I = {1, 3, 4} y la base I = {3, 4, 1}, pues tienen tablas asociadas muy diferentes entre sí.
 xy2

z = 6x1 + 4x2 = 96

x1

2x1 + 4x2 = 48
3x1 = 36 4x1 + 2x2 = 60

Figura 4.2: Región de soluciones factibles del problema de los ejemplos 4.1 y 4.3; la solución
óptima es acotada como se muestra en el ejemplo 4.3.

Ejemplo 4.1 Pongamos el problema (figura 4.2)

máx z = 6x1 + 4x2 ,

s.a.



2x1 + 4x2 ≤ 48,



P 4x1 + 2x2 ≤ 60,

3x1 ≤ 36,




x1 , x2 ≥ 0,


cuya forma estándar está dada por

máx z = 6x1 + 4x2 ,

s.a.



2x1 + 4x2 + x3 = 48,



P0 4x1 + 2x2 + x4 = 60,

3x1 + x5 = 36,




x1 , x2 , x3 , x4 , x5 ≥ 0,


en forma explícita con respecto a I = {3, 4, 1}. Usando la misma notación de la sección 4.3,
tenemos que  
1 0 2
AI =  0 1 4  ,
 
0 0 3
de donde
1 0 − 23
 

(AI )−1 =  0 1 − 43  .
 
1
0 0 3
Para obtener (4.7), como J = {2, 5}, calculamos

1 0 − 23
    
4 4
I −1 2
(A ) A =  0 1 − 43   2  =  2  ,
    
1
0 0 3 0 0
1 0 − 23 −2
    
0
I −1 5 4    34 
(A ) A =  0 1 − 3   0  =  − 3 

1 1
0 0 3 1 3

1 0 − 32
    
48 24
I −1
(A ) b =  0 1 − 43   60  =  12  .
    
1
0 0 3 36 12

Así, las restricciones (sin incluir las de no negatividad) del problema se expresan como


 4x2 + x3 − 32 x5 = 24,
2x2 + x4 − 43 x5 = 12,
x + 13 x5 = 12.

1

Además, para obtener (4.6), vemos que

1 0 − 23
 
³ ´ ³ ´
cI (AI )−1 = 0 0 6  0 1 − 43  = 0 0 2 ,
 
1
0 0 3

y por consiguiente
 
³ ´ 48
z0 = cI (AI )−1 b = 0 0 2  60  = 72,
 
36
 
³ ´ 4
c2 − z2 = c2 − cI (AI )−1 A2 = 4 − 0 0 2  2  = 4 − 0 = 4,
 
0
 
³ ´ 0
c5 − z5 = c5 − cI (AI )−1 A5 = 0 − 0 0 2  0  = 0 − 2 = −2.
 
1

De aquí que la función objetivo del problema se escriba en forma explícita como

4x2 − 2x5 = z − 72.

Entonces la forma explícita del problema P 0 con respecto a la base I = {3, 4, 1} es
máx z

s.a.



4x2 − 2x5 = z − 72,



4x2 + x3 − 23 x5 = 24,
+ x4 − 43 x5 = 12,

2x2




x1 + 13 x5 = 12.


¿Puede el lector explicar la diferencia entre la representación con respecto a la base I = {3, 4, 1}
y con respecto a la base I = {1, 3, 4}?

4.4. Análisis de la forma explícita

Ahora que hemos presentado la forma explícita de un problema lineal con respecto a una base,
ya estamos en condiciones de formalizar las operaciones que ya hemos realizado con las tablas de
la sección 4.2, pero en un contexto general. Para tal efecto consideraremos la tabla (4.8), es decir,
una tabla de la forma
x1 x2 ··· xm xm+1 ··· xn
x1 1 0 ··· 0 y1,m+1 ··· y1n y10
x2 0 1 ··· 0 y2,m+1 ··· y2n y20
.. .. .. .. .. .. .. .. .. (4.9)
. . . . . . . . .
xm 0 0 ··· 1 ym,m+1 ··· ymn ym0
−z 0 0 ··· 0 cm+1 − zm+1 · · · cn − zn −z0
donde, sin pérdida de generalidad, estamos suponiendo que x 1 , . . ., xm son las variables básicas
del problema, i.e., I = {1, . . . , m}.

4.4.1. Pivoteo
Como ya vimos en la sección 4.2, hay manera de mejorar la solución factible de un problema
de programación lineal bajo ciertas condiciones de la tabla (4.9). El problema lineal P asociado a
la tabla (4.9) es, en la forma explícita correspondiente,

máx z
 s.a.


(cm+1 − zm+1 )xm+1 + · · · + (cn − zn )xn = z − z0 ,





x1 + y1,m+1 xm+1 + · · · + y1n xn = y10 ,

(4.10)


 x2 + y2,m+1 xm+1 + · · · + y2n xn = y20 ,
..........................................






xm + ym,m+1 xm+1 + · · · + ymn xn = ym0
Recordemos que la solución básica asociada se obtiene haciendo x̄ j = 0 para j ∈ J y resolviendo
para las demás variables según (4.10), de modo que x̄ 1 = y10 , x̄2 = y20 , . . ., x̄m = ym0 .
 Sean I una base factible y x̄ la solución básica asociada. Supongamos que existen k ∈ J tal que
k > 0 y al menos una s ∈ I tal que ysk > 0. Deduciremos una nueva solución factible x̄ cuyo
ck −z 0

valor para la función objetivo asociado z0 mejore el valor de la función objetivo z0 correspondiente
0

a x̄. Establezcamos x̄0j = 0 para j ∈ J \ {k}. Entonces, del sistema (4.10) obtenemos

z00 = z0 + (ck − zk )x̄0k ,

x̄01 = x̄1 − y1k x̄0k ,
x̄02 = x̄2 − y2k x̄0k ,
...
x̄0m = x̄m − ymk x̄0k .

Puesto que x̄0 debe ser factible, debemos tener x̄0k ≥ 0 y x̄0i ≥ 0 para i ∈ I, de modo que debemos
garantizar x̄0k ≥ 0 y
x̄s − ysk x̄0k ≥ 0. (4.11)
Si ysk ≤ 0, es claro que (4.11) se cumple pues x̄ es una solución factible de P y x̄ 0k ≥ 0. Así pues,
basta con considerar el problema de la no negatividad de x̄ 0s cuando ysk > 0, en cuyo caso tenemos
que (4.11) implica
x̄s
x̄0k ≤ , s ∈ {s | ysk > 0}.
ysk
De aquí que el máximo valor que x̄0k puede tomar es

x̄s
½ ¾
x̄0k = mı́n .
{s|ysk >0} ysk

Ahora bien, como para al menos una ` ∈ I se satisface

x̄` x̄s
½ ¾
= mı́n ,
y`k {s|ysk >0} ysk

tenemos
x̄`
x̄0` = x̄` − y`k x̄0k = x̄` − y`k = 0,
y`k
así que la variable x̄0` deja de ser una variable básica. Cuando esto sucede para más de una `,
obtenemos una solución básica degenerada (que no está únicamente determinada). Llamaremos al
elemento y`k elemento pivote.
El nuevo conjunto de índices I 0 = I ∪ {k} \ {`} es una base. En efecto, pues la solución x̄ 0 se
puede obtener mediante una sucesión de operaciones elementales en el sistema (4.10), y cada una
de dichas operaciones elementales se puede representar mediante una matriz elemental de m × m,
0
y cada matriz elemental es invertible. El producto de todas estas matrices elementales es (A I )−1
0
pues x̄0 = (AI )−1 b. Es usual decir en estos casos que la variable xk entra a la base y que la
variable x` sale de la misma.
 Más aún, la solución factible x̄0 mejora el valor de la función objetivo pues

z00 = z0 + (ck − zk )x̄0k ≥ z0 .

La igualdad se cumple cuando

x̄s
½ ¾
x̄0k = mı́n = 0,
{s|ysk >0} ysk

y eso sucede sólo si x̄s = 0 para alguna s ∈ {s | ysk > 0} ⊆ I, es decir, si x es una solución
factible degenerada. En teoría, este es un inconveniente que podría ciclar el algoritmo simplex.
Así, hemos probado el siguiente

Teorema 4.1 (Pivoteo) Sea I una base realizable de P y x̄ su solución factible asociada. Supon-
gamos que existe k ∈ J tal que ck − zk > 0 y que existe al menos una s ∈ I tal que ysk > 0.
Entonces existe una base I 0 = I ∪ {k} \ {`}, donde ` ∈ I satisface
x̄` x̄s
½ ¾
= mı́n ,
y`k {s|ysk >0} ysk

tal que la solución de base factible correspondiente a I 0 está asociada a un z00 ≥ z0 .

4.4.2. Soluciones óptimas finitas

Definición 4.1 El vector ĉ = (0, cJ −zJ ) se llama vector de costos (coeficientes de costo reducido)
relativo a la base I.

Teorema 4.2 (Criterio de optimalidad) Si ĉ ≤ 0, la solución de base correspondiente, en un

problema a maximizar, es óptima.
Demostración. Como x ≥ 0 para toda solución factible x, si ĉ ≤ 0, tenemos ĉx ≤ 0, es decir,

ĉx = (0, cJ − zJ )x = (cJ − zJ )xJ ≤ 0.

Por (4.6) y por la definición de z0 , esto es equivalente a afirmar

z − z0 = z − cI x̄I = z − cx̄ ≤ 0

para toda solución factible x, es decir,

z ≤ z0 .
Así pues, como estamos maximizando, z0 es un máximo para z y, por ende, el valor óptimo de z
se alcanza precisamente al evaluar en x̄.

Observación 4.2 Si la función objetivo es a minimizar en vez de maximizar, el teorema 4.2 debe
enunciarse “si el vector de costos relativo a la base I es no negativo, la solución de base es óptima.”
Ejemplo 4.2 Consideremos el problema
mı́n w = 50x1 + 80x2 ,



x1 ≥ 25,




≤ 50,

 x2
P

 − 32 x1 + x2 ≤ 0,




 x1 + x 2 ≤ 100,
x1 , x2 ≥ 0,


cuya forma estándar es



 mı́n w = 50x1 + 80x2 ,
−x1 + x3 = −25,





 x 2 + x4 = 50,
P0 3



− x
2 1 + x 2 + x5 = 0,



 x1 + x2 + x6 = 100,
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0.


Tenemos que (25, 0) es una solución óptima de P asociada a la base I = {1, 4, 5, 6}. En efecto, si
calculamos los cj − zj con j ∈ J = {2, 3},

c2 − z2 = c2 − cI (AI )−1 A2
  
1 0 0 0 0
³ ´ 0 1 0 0  1 
= 80 − 50 0 0 0
  
3
2 0 1 0 1
  
  
−1 0 0 1 1
 
0
³ ´ 1 
= 80 − 50 0 0 0  = 80 ≥ 0,
 
1

 
1
c3 − z3 = c3 − cI (AI )−1 A3
  
1 0 0 0 −1
³ ´ 0 1 0 0  0 
=0− 50 0 0 0
  
3
2 0 1 0 0
  
  
−1 0 0 1 0
 
−1
³ ´ 0 
=− 50 0 0 0  = 50 ≥ 0,
 
0

 
0

podemos constatar que cj − zj ≥ 0 para toda j ∈ J, de modo que la solución de base asociada es
óptima.
Ejemplo 4.3 Para utilizar el algoritmo simplex con el problema (figura 4.2)
máx z = 6x1 + 4x2 ,

s.a.



2x1 + 4x2 ≤ 48,



 4x1 + 2x2 ≤ 60,
3x1 ≤ 36,




x1 , x2 ≥ 0,


se reescribe en forma estándar

máx z = 6x1 + 4x2 ,

 s.a.


2x1 + 4x2 + h1 = 48,



 4x1 + 2x2 + h2 = 60,
3x1 + h3 = 36,




x1 , x2 , h1 , h2 , h3 ≥ 0.


Al pivotear para mejorar la solución del problema obtenemos la sucesión de tablas

x1 x2 h1 h2 h3
h1 2 4 1 0 0 48
h2 4 2 0 1 0 60
h3 3 0 0 0 1 36 ← sale
−z 6 4 0 0 0 0
↑
entra

x1 x2 h1 h2 h3
h1 0 4 1 0 − 23 24 ← sale
h2 0 2 0 1 − 34 12
1
x1 1 0 0 0 3 12
−z 0 4 0 0 −2 −72
↑
entra

x1 x2 h1 h2 h3
1
x2 0 1 4 0 − 16 6
h2 0 0 − 21 1 −1 0
1
x1 1 0 0 0 3 12
−z 0 0 −1 0 − 43 −96
Puesto que todas las entradas del vector de costos son no positivas, la solución óptima es z máx = 96
con x1 = 12 y x2 = 6.
4.4.3. Soluciones óptimas no acotadas
Retomemos la discusión de la subsección 4.4.1 a partir de la ecuación (4.11). ¿Qué sucedería
si y k = (AI )−1 Ak ≤ 0, es decir, si ysk ≤ 0 para s = 1, . . ., m. En ese caso el valor de x̄0k no
tendría cota alguna y podría tomar valores arbitrariamente grandes. Puesto que

z00 = z0 + (ck − zk )x̄0k ≥ z0 ,

podemos elegir el valor de x̄0k para obtener un valor de z00 tan grande como deseemos. Así, hemos
probado el siguiente

Teorema 4.3 Sea I una base realizable de P y supongamos que c k −zk > 0 y y k = (AI )−1 Ak ≤ 0
para algún k ∈ J . Entonces existe una clase de soluciones de P tal que z → ∞.

Ejemplo 4.4 (z → ∞) Consideremos el problema (figura 4.3)

máx z = 2x1 + x2 ,

 s.a.


x1 − x2 ≤ 1,



 3x1 − x2 ≤ 6,
x1 , x2 ≥ 0,


cuya forma estándar es

máx z = 2x1 + x2 ,

 s.a.


x1 − x 2 + x 3 = 1,



 3x1 − x2 + x4 = 6,
x1 , x2 , x3 , x4 ≥ 0.


Al pivotear obtenemos la sucesión de tablas

x1 x2 x3 x4
x3 1 −1 1 0 1 ← sale
x4 3 −1 0 1 6
−z 2 1 0 0 0
↑
entra

x1 x2 x3 x4
x1 1 −1 1 0 1
x4 0 2 −3 1 3 ← sale
−z 0 3 −2 0 −2
↑
entra
 xy2
3x1 x2 = 6

x1 x2 = 1

z=2

z=0

x1

13
z = 2x1 + x2 = 2

Figura 4.3: Región de soluciones factibles no acotada.

x1 x2 x3 x4
x1 1 0 − 21 1
2
5
2
x2 0 1 − 23 1
2
3
2
5
−z 0 0 2 − 32 − 13
2
↑
entra
correspondientes a los puntos A, B y C de la figura, respectivamente. Como en la última tabla la
columna asociada a x3 es menor o igual que cero y su coeficiente en la función objetivo es positivo,
se tiene que z → ∞.

4.4.4. Soluciones óptimas alternativas

La solución óptima de un problema de programación lineal no siempre es única. De hecho,
puede haber una infinidad de soluciones óptimas para un problema dado (teorema 4.4).

Ejemplo 4.5 Consideremos el problema

máx z = x1 + x2 + x3 + x4 ,

 s.a.



x1 + x 2 ≤ 2,


 x3 + x4 ≤ 5,
x1 , x2 , x3 , x4 ≥ 0.

Pasando a la forma standard el problema, tenemos
máx z = x1 + x2 + x3 + x4 ,

 s.a.



x1 + x 2 + x5 = 2,


 x3 + x 4 + x6 = 5,
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0.


Al aplicar el algoritmo simplex para resolver el problema obtenemos la sucesión de tablas

x1 x2 x3 x4 x5 x6
x5 1 1 0 0 1 0 2 ← sale
x6 0 0 1 1 0 1 5
−z 1 1 1 1 0 0 0
↑
entra

x1 x2 x3 x4 x5 x6
x1 1 1 0 0 1 0 2
x6 0 0 1 1 0 1 5 ← sale
−z 0 0 1 1 −1 0 −2
↑
entra
Así obtenemos la tabla
x1 x2 x3 x4 x5 x6
x1 1 1 0 0 1 0 2
x3 0 0 1 1 0 1 5
−z 0 0 0 0 −1 −1 −7
De manera análoga podríamos haber concluido con alguna de las tablas

x1 x2 x3 x4 x5 x6
x2 1 1 0 0 1 0 2
x3 0 0 1 1 0 1 5
−z 0 0 0 0 −1 −1 −7

x1 x2 x3 x4 x5 x6
x2 1 1 0 0 1 0 2
x4 0 0 1 1 0 1 5
−z 0 0 0 0 −1 −1 −7
 x1 x2 x3 x4 x5 x6
x1 1 1 0 0 1 0 2
x4 0 0 1 1 0 1 5
−z 0 0 0 0 −1 −1 −7
Así, se tienen cuatro soluciones básicas óptimas factibles, a saber,

x̄(1) = (2, 0, 5, 0),

x̄(2) = (0, 2, 5, 0),
x̄(3) = (0, 2, 0, 5),
x̄(4) = (2, 0, 0, 5),

para las cuales el valor óptimo es zmáx = 7. Por lo tanto, el conjunto de las x̄ tales que
4 4
λi x̄(i)
X X
x̄ = con λi = 1 y λ 1 , λ2 , λ3 , λ4 ≥ 0
i=1 i=1

son todas las soluciones factibles óptimas. Por ejemplo,

x̄ = 21 (2, 0, 5, 0) + 12 (0, 2, 5, 0) + 0(0, 2, 0, 5) + 0(2, 0, 0, 5)

= (1, 0, 25 , 0) + (0, 1, 52 , 0)
= (1, 1, 5, 0)

es también una solución factible óptima de P .

Teorema 4.4 Dado un problema lineal P en forma explícita con respecto a una base I , si existe k ∈
J tal que ck − zk = 0 y existe s ∈ I tal que ysk > 0 entonces existe una base I 0 = I ∪ {k} \ {`}
con ` tal que
x̄` x̄s
½ ¾
= mı́n y z00 = z0 .
y`k {s|ysk >0} ysk

Demostración. Sean x̄ la solución básica correspondiente a I y z 0 el valor de la función objeti-

vo en x̄. Definamos una nueva solución x̄0 del problema P , cuyo valor para la función objetivo
asociado sea z00 , por
x̄`
x̄0k = ,
y`k
x̄0s = x̄s − ysk x̄0k , s ∈ I,
x̄0j = 0, j ∈ J \ {k}

donde ` satisface
x̄` x̄s
½ ¾
= mı́n ;
y`k {s|ysk >0} ysk
el índice existe ya que existe s ∈ I tal que ysk > 0. Observemos que en particular
x̄`
x̄0` = x̄` − y`k x̄0k = x̄` − y`k = 0.
y`k
Es inmediato observar que x̄0 es una solución básica de P asociada a la base I 0 = I ∪ {k} \ {`}
(ver observaciones de la subsección 4.4.1). Además, el valor para la función objetivo z 00 asociado
a x̄0k es igual a z0 pues

z00 = z0 + (ck − zk )x̄0k = z0 + 0x̄0k = z0 .

4.5. Algoritmo simplex

Ahora que hemos formalizado las operaciones sobre las tablas mediante la forma explícita y
se han analizado todos los casos, procederemos a establecer formalmente el algoritmo simplex.
Para iniciar el algoritmo simplex es necesario conocer una base I del problema lineal y escribir el
problema lineal en forma explícita con respecto a dicha base; en el capítulo siguiente veremos la
forma de encontrar la base I de manera eficiente.
Como ya es usual en nuestra presentación, estableceremos el algoritmo para el caso de maxi-
mizar. El caso de minimizar es análogo.

1. [¿Es solución óptima?] Analizar los coeficientes de costo reducido:

Si cj − zj ≤ 0 para j ∈ J, entonces la solución básica actual es óptima y el algoritmo

termina,
sino, sea k tal que
ck − zk = máx{cj − zj }.
j∈J

2. [¿Es solución acotada?] Si y k = (AI )−1 Ak ≤ 0, el algoritmo termina; el problema no posee

solución acotada, i.e., z → ∞.

3. [Pivotear.] Encontrar ` tal que

x̄` x̄s
½ ¾
= mı́n ;
y`k {s|ysk >0} ysk

se tiene una nueva base I 0 = I ∪{k}\{`}. Poner el problema en forma explícita con respecto
a I 0 , es decir, pivotear, e ir de vuelta al paso 1.

Finalmente, cabe remarcar algunos hechos:

Observación 4.3 En un problema de programación lineal:

Cada restricción genera un hiperplano cerrado.

 La región factible es la intersección de todos los hiperplanos asociados a las restricciones de
un problema P .

Existen puntos extremos o vértices que están determinados por la intersección de al menos m
hiperplanos en Rm .

El número de puntos extremos del conjunto de soluciones factibles es finito.

El valor óptimo de z se alcanza (al menos) en un punto extremo del conjunto de soluciones
factibles, cuando el óptimo es finito.

4.6. Finitud del algoritmo simplex

Observación 4.4 De una iteración a la siguiente, el valor de la función objetivo crece en
x̄`
ĉk x̄0k = (ck − zk )x̄0k = (ck − zk ) .
y`k

Proposición 4.1 Si en cada iteración x̄` > 0 para ` ∈ I (y necesariamente si las soluciones de
base sucesivas no son degeneradas) el algoritmo simplex se termina en un número finito de etapas.

Demostración. Tenemos siempre x̄` > 0, de modo que el valor de z crece efectivamente en cada
iteración. A cada base I corresponde una sola solución de base y un solo valor de z, así que, por
consecuencia, la misma base I no puede volver a presentarse. Como el número de bases es finito,
el algoritmo es también finito.

Observación 4.5 La experiencia muestra que la degeneración es extremadamente frecuente, pero

no ha habido un solo programa lineal que cicle, a menos de haberse construido ex profeso, por
ejemplo,
3 1
 máx z = 4 x1 − 150x2 + 50 x3 − 6x4 ,

s.a.

1 1

4 x1 − 60x2 − 25 x3 + 9x4 + x5 = 0,



1 1
 2 x1 − 90x2 − 50 x3 + 3x4 + x6 = 0,
x3 + x7 = 1,




x1 , x2 , x3 , x4 , x5 , x6 , x7 ≥ 0.


Ejercicios del capítulo 4

1. Un fabricante de chocolates desea encontrar la mezcla óptima para una caja de chocolates;
dispone de dos clases de chocolates para llenarla, las características que él considera impor-
tantes son:

a) Las cajas deberán tener al menos 35 chocolates cada una.

 b) El contenido de cada caja no debe exceder de un costo de 60 /c.
c) El peso de cada caja no deberá ser inferior a 35 gramos.
d) Colocando contenedores, el espacio que puede ocupar varía entre 40 y 56 cm 2 .
e) Los primeros chocolates pesan 1.5 gramos cada uno, los otros 0.5 gramos.
f) El espacio que ocupan es 2 cm2 y 1 cm2 respectivamente.
g) El costo unitario es de 2/cy 1/crespectivamente.

El fabricante desea saber cómo llenar sus cajas de manera que satisfaga los requisistos a
costo mínimo.
Plantearlo como un problema de programación lineal y dar graficamente su solución como
el problema visto en clase.

2. Dado el siguiente problema lineal:

mı́n z = x2 −3x3 +2x5

s.a.



x1 +3x2 −x3 +2x5 =7



 −2x2 +4x3 +x4 = 12
−4x2 +3x3 +8x5 +x6 = 10




xi ≥0


¿I = {1, 2, 3} es base realizable? En caso afirmativo, iniciar el algoritmo simplex para

obtener la solución óptima.
¿Puede iniciarse con alguna otra base, con respecto a la cual ya se tenga la forma explícita?
¿Cuál es?

3. Aplica el algoritmo simplex a

máx z = x1 +x2

s.a.



x1 −x2 ≥ −3



(P) x2 ≤5

2x1 +x2 ≤ 14




x1 , x2 ≥0


4. Resuelve con I = {1, 4} como base realizable inicial:


mı́n z = x1 +x2 +x3 +x4
 s.a.



x1 +2x2 −x3 =4


 3x2 +x3 +5x4 = 5
xi ≥ 0 i = 1, 4


5. Resuelve utilizando el algoritmo simplex:

 máx z = 3x1 +2x2

s.a.



x1 −x2 ≤1



 x1 +x2 ≤3
x1 ≤1




x1 , x2 ≥0


6. Dado el siguiente problema de programación lineal:

máx z = 28x1 +x3 +2x5

s.a.



14x1 +x3 +3x4 −x5 =7



 16x1 + 21 x3 −2x5 +x6 =5
3x1 +x2 =0




xi ≥0


Dar una base tal que la solución básica asociada a dicha base esté en una clase de soluciones
factibles tales que z → ∞.

7. Da la solución óptima del problema de programación lineal:


mı́n w = 4x1 +8x2 +3x3
 s.a.



x1 +x2 ≥2


 2x1 +x3 ≥5
xi ≥ 0 i = 1, 3


8. Resuelve con el algoritmo simplex y comenta los resutados.

mı́n w = −x1 +2x2

s.a.



x1 −x2 ≤4



 x1 +2x2 ≤3
x1 +x2 ≤2




x1 , x2 ≥0


9. Resuelve con el algoritmo simplex:

5


 máx z = 2 x1 +x2
+5x2 ≤ 15

 3x1



5x1 +2x2 ≤ 10

x1 , x2 ≥ 0

10. Resuelve con el algoritmo simplex:



 máx z = 6x1 +4x2
2x1 +4x2 +x3 = 48




4x1 +2x2 +x4 = 60
3x1 +x5 = 36





xi ≥0

11. Resuelve los ejercicios 1., 3., 4. y 7. del capítulo I con el algoritmo simplex.
Capítulo 5

Método Simplex

Supongamos que deseamos resolver el problema lineal

máx z = 2x1 + x2 ,

 s.a.


x1 + 2x2 ≥ 3,



 x1 + x2 ≤ 3,
3x1 + x2 ≥ 3,




x1 , x2 ≥ 0,


o bien el problema de programación lineal

x1 + x2 + x3 + x4 + x5 ,

mı́n z =
 s.a.



x1 + x2 − x3 + x4 − x5 = 1,


 −x1 + x2 + 3x3 − 2x4 + x5 = 2,
x1 , x2 , x3 , x4 , x5 ≥ 0.


Para cualquiera de estos problemas no es inmediato encontrar una solución básica factible con
la herramienta matemática hasta ahora conocida de manera eficiente. Veamos, pues, el método
simplex que nos ayuda a encontrar de una manera segura una primera solución básica factible.

5.1. Las dos fases del método simplex y el teorema fundamental

Consideremos el programa lineal en forma estándar

 máx

s.a.
z = cx,
P Ax = b, (5.1)

x ≥ 0.


En la primera fase del método simplex encontraremos una base factible para el problema (5.1) y en
la segunda aprovecharemos dicha base para resolver el problema.

74
5.1.1. Fase I
Sin pérdida de generalidad podemos suponer que todas las componentes del vector b son posi-
tivas o nulas (si alguna es negativa, basta con invertir los signos de la restricción correspondiente).
Asociemos a P el problema lineal auxiliar
m

P
 mı́n ϕ = ai ,


 s.a.

 i=1
PA Ax + U a = b, (5.2)
cx + (−z) = 0,




x, a ≥ 0.



donde U es una matriz unitaria de m × m, las variables ai se denominan variables artificiales y −z

es una variable sin restricción de signo; son variables artificiales porque no tienen interpretación
económica directa en términos del problema original. No necesariamente deberán ser m variables
artificiales, pues se pueden emplear menos si la estructura del problema lo permite. Las variables
artificiales junto con la variable −z nos proporcionarán una base inicial factible para el proble-
ma (5.2); la base es factible debido a que b ≥ 0.
El hecho de agregar variables artificiales viola las restricciones del problema original P , pero
este inconveniente se supera asegurando que las variables artificiales serán iguales a cero en la
solución óptima de PA. Si el problema original no tiene solución, al menos una artificial estará en
la solución óptima del problema auxiliar con valor positivo.
La variable −z no tiene restricción de signo, así que la “restricción” cx + (−z) = 0 en realidad
no es una restricción. Sin embargo al incluirla entre las restricciones de la fase I obtendremos la
función objetivo z = cx del problema original con respecto a la base factible que encontremos.
El problema (5.2) no está en forma explícita con respecto a las variables artificiales debido a
que las mismas forman parte de la nueva función objetivo ϕ. Nuestra primera tarea es poner el
problema con respecto a las variables artificiales; esto no representa ninguna dificultad. Sea e el
vector renglón de dimensión m cuyas componentes son iguales a 1. Al poner PA en forma explícita
con respecto a una base formada por las variables artificiales y −z, obtenemos

 mı́n ϕ,

s.a.


−eAx = ϕ − eb,



PA Ax + U a = b,

cx + (−z) = 0,




x, a ≥ 0.


Podemos ahora aplicar el algoritmo simplex; obtendremos en un número finito de iteraciones una
solución óptima de base. En efecto, puesto que
ϕ = a1 + a2 + · · · + a m , ai ≥ 0,
necesariamente ϕ ≥ 0 así que es imposible que ϕ → −∞, de modo que la única forma de terminar
el algoritmo es con una base óptima para PA.
Pueden suceder así, tres posibilidades con respecto al valor óptimo mínimo ϕ mı́n de ϕ, a saber:
i) ϕmı́n = 0 y ninguna variable artificial está en la base óptima final; así obtenemos una solución
factible para el problema P ; en este caso procedemos con la fase II del método.

ii) ϕmı́n = 0 y existen ciertas variables artificiales en la base final; entonces aquí, o bien elimi-
namos algunas ecuaciones por ser redundantes, o pivoteamos para introducir variables no
artificiales en la base en lugar de las variables artificiales.

iii) ϕmı́n > 0; en este caso no existe solución realizable para el problema P .

Las proposiciones 5.1–5.3 justifican las dos primeras afirmaciones y la proposición 5.4 justifica
la última.

Proposición 5.1 Si (x̄∗ , ā∗ ) es una solución óptima de PA tal que ϕmı́n = 0, entonces x̄∗ es una
solución factible para P .

Demostración. Puesto que (x̄∗ , ā∗ ) es óptima para PA, en particular es factible, i.e.,

Ax̄∗ + U ā∗ = b, x̄∗ , ā∗ ≥ 0.

Por hipótesis ϕmı́n = 0, de modo que ā∗ = 0. De aquí que

b = Ax̄∗ + U ā∗ = Ax̄∗ + U (0) = Ax̄∗ .

Por tanto, Ax̄∗ = b y x̄∗ ≥ 0 de donde x̄∗ es factible para P .

Una consecuencia inmediata de la proposición 5.1 es que si ninguna de las a i está en la base
óptima de PA, esta base no contiene mas que las variables x y −z. Entonces, al eliminar las
variables artificiales, la forma explícita con respecto a esta base óptima para PA es una forma
explícita con respecto a una base realizable para P y el algoritmo simplex puede aplicarse a P .

Proposición 5.2 Si al final de la aplicación del algoritmo simplex al problema lineal PA, la r-
ésima ecuación contiene sólo variables artificiales, la restricción correspondiente de P es redun-
dante.

Demostración. La forma explícita con respecto a la base óptima I de PA se obtuvo por una serie
de operaciones de pivoteo, es decir, por una serie de operaciones elementales. Entonces la r-ésima
ecuación de la forma explícita con respecto a I de PA es una combinación lineal de las ecuaciones
del sistema lineal
Ax + U a = b,

combinación lineal en la cual al menos un coeficiente de alguna a i es no nulo. Como, por hipótesis,
esta misma combinación lineal aplicada al sistema Ax = b da la ecuación 0x = 0, entonces esta
r-ésima ecuación era redundante en el sistema original P .
Proposición 5.3 Si al final de la aplicación del algoritmo simplex al problema lineal PA, la r-
ésima ecuación contiene una variable artificial básica y también variables no artificiales no básicas,
podemos encontrar una nueva base en la cual la r-ésima ecuación tenga una variable no artificial
básica.

Demostración. Sea I una base óptima del problema PA y (x̄, ā) la solución correspondiente básica
asociada. La variable básica de la r-ésima ecuación es una variable artificial a i = 0, de modo que el
lado derecho de la r-ésima restricción es igual a 0 y la solución óptima es degenerada. Puesto que
la dicha ecuación contiene al menos una variable artificial no básica, existe k ∈ J tal que y rk 6= 0.
Sin pérdida de generalidad podemos suponer que yrk > 0 (si todos los coeficientes son negativos,
basta con multiplicar la restricción por −1, lo cual deja invariantes los puntos que satisfacen la
r-ésima restricción). Al pivotear para introducir xk a la base en lugar de ai obtenemos una nueva
base (degenerada) para la cual xk = 0 es una variable básica y ai = 0 se convierte en una variable
no básica (véanse las observaciones sobre soluciones factibles degeneradas en la página 62), y las
demás variables del problema no modifican su valor. Así, tampoco se altera el valor de la función
objetivo ϕ.
En vez de aplicar directamente el algoritmo simplex al problema PA podemos aplicar una
variante del algoritmo en la cual una variable artificial que sale de la base ya no se considera más.
No tendría ningún sentido introducir de nuevo una variable artificial en la base. El objetivo de la
fase I es, en efecto, eliminarlas de la base si es posible.

Proposición 5.4 Sea (x∗ , a∗ ) una solución óptima de PA. Si ϕmı́n > 0 entonces P no admite
solución realizable.

Demostración. Si P tuviera una solución realizable x̄, entonces (x̄, 0) sería una solución realizable
de PA con
m
X
ϕ= ai = 0 < ϕmı́n ,
i=1

una contradicción.

5.1.2. Fase II
Podemos iniciar la fase II después de haber examinado todas las variables artificiales que es-
tán en la base final, haberlas eliminado y si es posible haber suprimido la ecuación redundante
correspondiente.
En caso de no tener variables artificiales en la base óptima de PA y satisfacer ϕ mı́n = 0, al
eliminar las variables artificiales tendremos una base que puede servir para inicializar el algoritmo
simplex para el problema P . Este conjunto de operaciones constituye la fase I del método simplex.
La aplicación del algoritmo simplex al problema lineal escrito en forma explícita con respecto
a una base realizable, constituye la fase II del método simplex.
5.1.3. El teorema fundamental de la programación lineal
De los resultados teóricos presentados para las dos fases del método simplex se desprende el
teorema fundamental de la programación lineal.

Teorema 5.1 (fundamental de la programación lineal) Dado un problema lineal P :

(i) Si tiene solución factible, tiene una solución factible básica.

(ii) Si tiene una solución óptima finita, tiene una solución óptima finita básica.

Demostración.

(i) Si P tiene una solución factible, por la proposición 5.4, necesariamente al final de la fase I
tenemos ϕmı́n = 0. Por consiguiente, la fase I pone a P en forma explícita con respecto a
alguna base factible, i.e., existe una solución básica factible.

(ii) Si P tiene una solución óptima finita (que en particular es una solución factible) entonces,
por (i), la fase I nos permite iniciar la fase II. Más aún, durante la fase II no es posible
encontrar una clase de soluciones no acotada pues de lo contrario P no podría tener una
solución óptima finita. En consecuencia, la fase II termina con una solución óptima finita
básica.

5.2. El procedimiento del método simplex

Supongamos que se desea encontrar una solución óptima del problema en forma mixta (inter-
cambiando las ecuaciones si es necesario)

máx z = c 1 x1 + c 2 x2 + · · · + c k xk ,



a 11 x1 + a12 x2 + · · · + a1k xk ≤ b1 ,



.. .. .. ..



. . . .





a x + ap2 x2 + · · · + apk xk ≤ bp ,

p1 1



a x1 + ap+1,2 x2 + · · · + ap+1,k xk = bp+1 ,


 p+1,1
.. .. .. ..


P . . . .

aq1 x1 + aq2 x2 + · · · + aqk xk = bq ,





aq+1,1 x1 + aq+1,2 x2 + · · · + aq+1,k xk ≥ bq+1 ,



.. .. .. ..



. . . .





am1 x1 + am2 x2 + · · · + amk xk ≥ bm ,




xi ≥ 0, i = 1, . . . , k.


1. [Escribir P en forma estándar] Para i = 1, . . . , m,

 si la i-ésima ecuación es de la forma

ai1 x1 + ai2 x2 + · · · + aik xk ≤ bi ,

introducimos una nueva variable xk+i ≥ 0 y reemplazamos la ecuación por

ai1 x1 + ai2 x2 + · · · + aik xk + xk+1 = bi ;

si la i-ésima ecuación es de la forma

ai1 x1 + ai2 x2 + · · · + aik xk ≥ bi ,

introducimos una nueva variable xk+p+i ≥ 0 y reemplazamos la ecuación por

ai1 x1 + ai2 x2 + · · · + aik xk − xk+p+i = bi .

El problema entonces será de la forma

máx z = c1 x1 + c2 x2 + · · · + cn xn ,



a11 x1 + a12 x2 + · · · + a1n xn = b1 ,






 a21 x1 + a22 x2 + · · · + a2n xn = b2 ,
P .. .. .. ..


 . . . .
am1 x1 + am2 x2 + · · · + amn xn = bm ,





xi ≥ 0, i = 1, . . . , n,


donde n = m − (q − p).

2. [Hacer los términos constantes bi ≥ 0] Para i = 1, . . . , m, si bi < 0, entonces reemplazamos

la ecuación
ai1 x1 + ai2 x2 + · · · + ain xn = bi
por la ecuación
−ai1 x1 − ai2 x2 − · · · − ain xn = −bi .

3. [Introducir variables artificiales] Se aumenta el sistema para incluir un conjunto de variables

artificiales básicas xn+1 ≥ 0, xn+2 ≥ 0, . . . , xn+m ≥ 0; para i = 1, . . . , m, se reemplaza
la i-ésima ecuación
ai1 x1 + ai2 x2 + · · · + ain xn = bi
por la ecuación
ai1 x1 + ai2 x2 + · · · + ain xn + xn+i = bi .
Estas nuevas variables, junto con la variable −z, formarán la base inicial factible del proble-
ma auxiliar.
4. [Introducir función objetivo auxiliar] Se introduce la función objetivo auxiliar

ϕ = xn+1 + xn+2 + · · · + xn+m

a minimizar. Para escribirla en forma explícita con respecto a las variables básicas calculamos

dj = −(a1j + a2j + · · · + amj ), j = 1, 2, . . . , n,

−ϕ0 = −(b1 + b2 + · · · + bm )

y escribimos el problema auxiliar en forma explícita como



 mı́n ϕ
d1 x1 + d 2 x2 + · · · + d n xn = ϕ − ϕ0





−z + c1 x1 + c2 x2 + · · · + cn xn = 0,






 a11 x1 + a12 x2 + · · · + a1n xn + xn+1 = b1 ,
PA a21 x1 + a22 x2 + · · · + a2n xn + xn+2 = b2 ,
.. .. .. ..

..


. . . . .





am1 x1 + am2 x2 + · · · + amn xn + xn+m = bm ,






xi ≥ 0, i = 1, . . . , n + m,

o equivalentemente


 mı́n ϕ
−ϕ d 1 x1 + d 2 x2 + · · · + d n xn = −ϕ0





−z + c1 x1 + c2 x2 + · · · + cn xn = 0,






 a11 x1 + a12 x2 + · · · + a2n xn + xn+1 = b1 ,
PA a21 x1 + a22 x2 + · · · + a1n xn + xn+2 = b2 ,
.. .. .. ..

..


. . . . .





am1 x1 + am2 x2 + · · · + amn xn + xn+m = bm ,






xi ≥ 0, i = 1, . . . , n + m.

5. [Aplicar el algoritmo simplex a P A] Aplicamos el algoritmo simplex a P A; podemos elimi-

nar las variables artificiales conforme salen de la base.

6. [¿Existe una solución factible para P ?] Si el mínimo de la función objetivo de P A es positi-

vo, terminar; el conjunto de restricciones es inconsistente, no hay solución factible.

7. [Obtener una base factible para P ] Analizar la base:

Si una variable artificial xn+i está en la base:

• Si todos los coeficientes del i-ésimo renglón, excepto el de x n+i , son cero, se
elimina el i-ésimo renglón de la tabla (i.e., la i-ésima ecuación).
 • Si existe al menos un coeficiente del i-ésimo renglón distinto del de x n+i no cero,
se pivotea para introducir su variable en la base en lugar de x n+i y se elimina la
columna de xn+i de la tabla.
Se regresa a 7.
Si no hay variables artificiales en la base, se inicia la fase II; una solución básica factible
para P se ha encontrado.

5.3. Método simplex

El método simplex se define mediante el algoritmo siguiente:

Fase I Encontrar una base factible para P :

I.1 [Escribir P en forma estándar.] El problema P se escribe en forma estándar; multipli-

cando por −1 las ecuaciones para las cuales bi < 0, obteniendo así un programa lineal
con sus términos independientes no negativos.
I.2 [Definir el problema auxiliar PA.] El problema auxiliar PA se define añadiendo tantas
variables artificiales como sea necesario (a lo más m). Tenemos entonces una solución
factible para este problema auxiliar.
I.3 [Escribir PA en forma explícita.] PA se escribe en forma explícita con respecto a esta
base realizable.
I.4 [Aplicar el algoritmo simplex a PA.] Aplicamos el algoritmo simplex; podemos elimi-
nar las variables artificiales conforme salen de la base.
I.5 [¿Existe una solución factible para P ?] Si el mínimo de la función objetivo de PA es
positivo, terminar; el conjunto de restricciones es inconsistente, no hay solución facti-
ble.
I.6 [Obtener una base factible para P .] Analizar la base:
Si no hay variables artificiales en la base, ir a la Fase II; una solución básica factible
para P se ha encontrado.
Si una variable artificial ai está en la base, esta variable se elimina de la base
pivoteando y una varible no artificial entra en la base. Si esta operación de pivoteo
no es posible, la ecuación que contiene ai es redundante en el problema original y
se elimina. Ir a I.6.

Fase II Se ha encontrado una base factible para el problema P . Más aún, P está en forma explícita
con respecto a esta base. Se aplica el algoritmo simplex a P .
 xy2

x1 + x 2 = 1

1
z= x1 + 2x2 = 7

3x1 3x2 = 2

x1

3x1 + x2 = 3 5x1 2x2 = 3

Figura 5.1: Región de soluciones factibles del problema del ejemplo 5.1.

Ejemplo 5.1 El problema (figura 5.1)

mı́n z = −x1 + 2x2 ,


s.a.



5x1 − 2x2 ≤ 3,





x1 + x2 ≥ 1,

P


 −3x1 + x2 ≤ 3,
−3x1 − 3x2 ≤ 2,






x1 , x2 ≥ 0,

se escribe en forma estándar como

mı́n z = −x1 + 2x2 ,


 s.a.


5x1 − 2x2 + x3




 = 3,
x1 + x 2 − x4 = 1,



 −3x1 + x2 + x5 = 3,
−3x1 − 3x2 + x6 = 2,






x1 , x2 , x3 , x4 , x5 , x6 ≥ 0.

Para asociarle un problema auxiliar observamos que únicamente es necesario introducir una varia-
ble artificial a1 para la segunda restricción. Así, definimos PA como

a1 ,

mı́n ϕ =
s.a.



−x1 + 2x2 + (−z) = 0,





5x1 − 2x2 + x3 = 3,



PA x1 + x 2 − x4 + a1 = 1,

−3x1 + x2 + x5 = 3,




−3x1 − 3x2 + x6 = 2,





x1 , x2 , x3 , x4 , x5 , x6 , a1 ≥ 0.


Al poner en forma explícita este problema con respecto a las variables x 3 , a1 , x5 , x6 y −z (en ese
orden), obtenemos

mı́n ϕ,

s.a.



−x1 − x2 + x4 = ϕ − 1,




−x

1 + 2x2 + (−z) = 0,




5x1 − 2x2 + x3 = 3,

PA


 x1 + x2 − x4 + a1 = 1,
−3x1 + x2 + x5 = 3,








 −3x1 − 3x2 + x6 = 2,
x1 , x2 , x3 , x4 , x5 , x6 , a1 ≥ 0.


Ahora resolvemos el problema PA con la ayuda de tablas para deducir una base factible para P :

x1 x2 x3 x4 x5 x6 a1
x3 5 −2 1 0 0 0 0 3 ← sale
a1 1 1 0 −1 0 0 1 1
x5 −3 1 0 0 1 0 0 3
x6 −3 −3 0 0 0 1 0 2
−z −1 2 0 0 0 0 0 0
−ϕ −1 −1 0 1 0 0 0 −1
↑
entra
 x1 x2 x3 x4 x5 x6 a1
x1 1 − 25 1
5 0 0 0 0 3
5
7
a1 0 5 − 15 −1 0 0 1 2
5 ← sale
x5 0 − 15 3
5 0 1 0 0 24
5
x6 0 − 21
5 − 35 0 0 1 0 19
5
8 1 3
−z 0 5 5 0 0 0 0 5
−ϕ 0 − 57 1
5 1 0 0 0 − 25
↑
entra

x1 x2 x3 x4 x5 x6 a1
1
x1 1 0 7 − 27 0 0 2
7
5
7
x2 0 1 − 71 − 57 0 0 5
7
2
7
4
x5 0 0 7 − 17 1 0 1
7
34
7
x6 0 0 0 −3 0 1 3 5
3 8
−z 0 0 7 7 0 0 − 87 1
7
−ϕ 0 0 0 0 0 0 1 0
Por tanto, las variables x1 , x2 , x5 y x6 forman un conjunto de variables básicas factibles para P y
podemos eliminar la variable artificial a1 de la tabla para obtener

x1 x2 x3 x4 x5 x6
1
x1 1 0 7 − 27 0 0 5
7
x2 0 1 − 17 − 57 0 0 2
7
4
x5 0 0 7 − 17 1 0 34
7
x6 0 0 0 −3 0 1 5
3 8 1
−z 0 0 7 7 0 0 7

Como los coeficientes de costo reducido de z son todos mayores o iguales que cero, tenemos el
óptimo para P . Por tanto, zmı́n = − 17 con x1 = 57 y x2 = 27 .

Ejemplo 5.2 El problema (figura 5.2)

máx z = 2x1 + x2 ,

 s.a.



P x1 + 2x2 ≥ 4,


 x1 + x2 ≤ 2,
x1 , x2 ≥ 0,


tiene asociado el problema auxiliar

 xy2

x1

z = 2x1 + x2 = 2 x1 + x2 = 2 x1 + 2x2 = 4

Figura 5.2: Región de soluciones factibles del problema del ejemplo 5.2.

mı́n ϕ = a1 ,

s.a.



2x1 + x2 + (−z) = 0,



PA x1 + 2x2 − x3 + a1 = 4,

x1 + x 2 + x4 = 2,




x1 , x2 , x3 , x4 , a1 ≥ 0,


o bien, en forma explícita con respecto a las variables a 1 , x4 y −z (en ese orden),


mı́n ϕ,
s.a.



−x1 − 2x2 + x3 = ϕ − 4,





2x1 + x2 + (−z) = 0,

PA


 x1 + 2x2 − x3 + a1 = 4,
x1 + x 2 + x4 = 2,






x1 , x2 , x3 , x4 , a1 ≥ 0,

Aplicando el algoritmo simplex obtenemos la sucesión de tablas

x1 x2 x3 x4 a1
a1 1 2 −1 0 1 4
x4 1 1 0 1 0 2 ← sale
−z 2 1 0 0 0 0
−ϕ −1 −2 1 0 0 −4
↑
entra
 x1 x2 x3 x4 a1
a1 −1 0 −1 −2 1 0
x2 1 1 0 1 0 2
−z 1 0 0 −1 0 −2
−ϕ 1 0 1 2 0 0

Como ϕ = 0 y la variable artificial a1 = 0 está en la base, la eliminamos pivoteando, metiendo en

la base una variable no artificial, digamos, x1 (no importa que el pivote sea negativo, pues a1 = 0).
Así obtenemos la tabla
x1 x2 x3 x4 a1
x1 1 0 1 2 −1 0
x2 0 1 −1 −1 1 2
−z 0 0 −1 −3 1 −2
−ϕ 0 0 0 0 1 0

Por ende, las variables x1 y x2 forman un conjunto de variables básicas para P y podemos eliminar
la variable artificial a1 de la tabla para obtener

x1 x2 x3 x4
x1 1 0 1 2 0
x2 0 1 −1 −1 2
−z 0 0 −1 −3 −2

De aquí que, zmáx = 2 con x1 = 0 y x2 = 2.

Ejemplo 5.3 El problema

− x4 ,

mı́n z = x1 + 2x2
 s.a.



P 2x2 − 4x3 = 3,


 x1 + x2 + 3x3 + x4 = 1,
x1 , x2 , x3 , x4 ≥ 0,


tiene asociado el problema auxiliar

 mı́n ϕ= a1 ,

s.a.


x1 + 2x2 − x4 + (−z) = 0,



PA 2x2 − 4x3 + a1 = 3,

x1 + x2 + 3x3 + x4 = 1,




x1 , x2 , x3 , x4 , a1 ≥ 0,

o bien en forma explícita,

mı́n ϕ,
s.a.



−2x2 + 4x3 = ϕ − 3,





x1 + 2x2 − x4 + (−z) = 0,

PA


 2x2 − 4x3 + a1 = 3,
x1 + x2 + 3x3 + x4 = 1,






x1 , x2 , x3 , x4 , a1 ≥ 0.

Así obtenemos la sucesión de tablas

x1 x2 x3 x4 a1
a1 0 2 −4 0 1 3
x1 1 1 3 1 0 1 ← sale
−z 1 2 0 −1 0 0
−ϕ 0 −2 4 0 0 −3
↑
entra

x1 x2 x3 x4 a1
a1 −2 0 −10 −2 1 1
x2 1 1 3 1 0 1
−z −1 0 −6 −3 0 −2
−ϕ 2 0 10 2 0 −1

De la última tabla se sigue que el problema es inconsistente, i.e., no hay solución factible para P .

Ejercicios del capítulo 5

1. Resuelve.
máx z = 2x1 +x2

s.a.



x1 +2x2 ≥4



(P) x1 +x2 ≤2

2x1 +4x2 ≥8




x1 , x2 ≥0


2. Resuelve
 mı́n z = 4x1 +2x2 +3x3

s.a.



2x1 +4x2 −3x3 ≥1



(P) x1 −3x2 +2x3 ≥ −3

x1 −7x2 +5x3 ≥ −4




xi ≥0


3. Resuelve por método simplex: dos fases y por penalizaciones.

mı́n z = 3x1 +2x2

s.a.



x1 −x2 +x3 =1



(P) x1 +x2 −x4 = 3
2 4 1 8

3 x1 + 3 x2 − 3 x3 −x4 = 3




xi ≥ 0


4. Encuentra una solución óptima del problema lineal, introduciendo un número mínimo de
variables artificiales.
 mı́n z = 4x1 +2x2 +3x3

s.a.


2x1 +4x2 −3x3 ≥1



(P) x1 −3x2 +2x3 ≥ −3

−x1 +x3 ≥3




xi ≥0


5. Encuentra una solución óptima del problema lineal.

máx z = −x1 +3x2 −3x3

s.a.



2x1 +x2 −x3 ≥4



(P) 4x1 −3x2 ≥2

−3x1 +2x2 +x3 ≥3




xi ≥0


6. Considera el problema lineal:


mı́n z = x1 +x2
 s.a.



(P) x1 −x2 ≥ 1


 2x1 −x2 ≥ 6
x1 , x2 ≥ 0


y el problema asociado:

mı́n z = x1 +x2 +M x5 +M x6
 s.a.



(PA) x1 −x2 −x3 +x5 =1


 2x1 −x2 −x4 +x6 =6
xi ≥0


donde M es un número muy grande.

 (a) Explica qué significan x3 , x4 , x5 , x6 y M. Muestra que si M es suficientemente grande,
la resolución de (PA) es equivalente a la resolución sucesiva de las fases I y II del
método simplex.
(b) Resuelve con M = 100 utilizando el algoritmo simplex.

7. Encuentra una solución no negativa del sistema:

(
x1 +2x2 −2x3 +x5 = 0
−x1 +2x2 +x3 +x4 +2x5 = 21

8. Resuelve:
 máx z = 5x1 +3x2

s.a.


4x1 +5x2 ≤ 10



(P) −5x1 −2x2 ≤ −10

−3x1 −8x2 ≤ −12




x1 , x2 ≥0


9. Considera el siguiente problema lineal:

mı́n z = −x1 +3x2 −2x3



x1 +x2 +x3 =1





 2x1 +3x2 =1

 3x1 +2x2 +5x3 =4




 x2 +2x3 = −1
xi ≥0


(a) Aplica el método simplex de dos fases para resolverlo.

(b) ¿Hay ecuaciones redundantes? En caso afirmativo, da los coeficientes de la combina-
ción lineal que producen las ecuaciones redundantes, utilizando la tabla final.
(c) ¿Es base A1 , A2 ? En caso afirmativo, ¿Cuál es la solución básica asociada?
¡ ¢

En los ejercicios del 10 - 17 obtén una solución óptima del problema lineal por el método
simplex:



 mı́n z = 3x1 +2x2
x1 −x2 +x3 =1




10. x1 +x2 −x4 =3
2 4 1
x + x − x −x =8


3 1 3 2 3 3 4



xi ≥0

 

 mı́n z = x1 +2x2 +x4 +x5 −5x6
6x1 −2x2 +3x3 −x4 +x5 +2x6 =4




11. 2x1 − 31 x2 −x3 +x4 1
2 x5 =3
3x1 −x2 +2x3 +4x4 + 21 x5 +x6 =2





xi ≥0



 máx z = x1 +2x2
3x1 +x2 −x3

 =6
12.

 x1 +3x2 −x4 = 10


xi ≥ 0 i = 1, 4


 máx z = 5x1 +3x2
4x1 +5x2 ≤ 10




13. −5x1 −2x2 ≤ −10
−3x1 −8x2 ≤ −12





x1 , x2 ≥0




 máx z = x1 +2x2 +3x4 −x4
x1 +2x2 +3x3 = 15




14. 2x1 +x2 +5x3 = 20
x1 +2x2 +x3 +x4 = 10





xi ≥0




 mı́n z = 4x1 +2x2 +3x3
2x1 +4x2 −3x3 ≥1




15. x1 −3x2 +2x3 ≥ −3
−x1 +x3 ≥3





xi ≥0




 máx z = 5x1 +3x2
−4x1 −5x2 ≤ −10




16. −5x1 −2x2 ≤ −10
−3x1 −8x2 ≤ −12





x1 , x2 ≥0




 máx z = 2x1 +x2
x1 +2x2 ≥4




17. x1 +x2 ≤2
2x1 +4x2 ≥8





x1 , x2 ≥0


En los ejercicios 18 - 20 da una solución óptima del problema lineal con el método de las
penalizaciones.
 

 mı́n z = 8y1 +15y2 +8y3 +32y4
2
+y2 + 13 y3 + 38 y4 ≥ 15

5 y1

18. 3

 5 y1 + 32 y2 +y3 +2y4 ≥ 15


yi ≥0


 máx z = 3x1 −x2
−2x1 −x2 ≤ −2




19. x1 +3x2 ≤3
x2 ≤4





x1 , x2 ≥0


−x1


 mı́n z = +2x2
5x1 −2x2 ≤3




≥1

 x1 +x2
20.



−3x1 +x2 ≤3



 −3x1 −3x2 ≤2
x1 , x2 ≥0


21. Resuelve con el método simplex los ejercicios 5., 10., 11.,12. y 13. del capítulo I.
Capítulo 6

Método simplex con multiplicadores

(revisado)

El método simplex tal como se expuso en los capítulos 4 y 5 (a partir de ahora llamado método
simplex original) es un procedimiento algebraico bien definido que es efectivo. Sin embargo, esta
forma de ejecutar el algoritmo (ya sea de forma algebraica o con tablas) no es lo más apropiado
computacionalmente hablando debido a que realiza muchas operaciones innecesarias y almacena
información inútil para la toma de decisiones. El objetivo de este capítulo es presentar el método
simplex con multiplicadores que mejora el desempeño computacional del método simplex pues
reduce los requerimientos computacionales y de almacenamiento en memoria rápida de los coefi-
cientes del algoritmo y, en consecuencia, mejora el desempeño del mismo.

6.1. Revisión del algoritmo simplex

6.1.1. La inversa de la matriz asociada a la base

Como vimos en la subsección 4.3, la tabla formada por los coeficientes de un problema


 máx z = cx,

P0 Ax = b,
x ≥ 0,



92
arbitrario siempre tiene la forma

x1 x2 ··· xm xm+1 ··· xn−m xn−m+1 xn−m+2 ··· xn

xσ(1) y11 y12 ··· y1m y1,m+1 ··· y1,n−m y1,n−m+1 y1,n−m+2 ··· y1n y10
xσ(2) y21 y22 ··· y2m y2,m+1 ··· y2,n−m y2,n−m+1 y2,n−m+2 ··· y2n y20
.. .. .. .. .. .. .. .. .. .. .. .. ..
. . . . . . . . . . . . .
xσ(m) ym1 ym2 · · · ymm ym,m+1 · · · ym,n−m ym,n−m+1 ym,n−m+2 · · · ymn ym0
−z r1 r2 ··· rm rm+1 ··· rn−m rn−m+1 rn−m+2 ··· rn −z0

Para poder resolver el problema por medio del algoritmo simplex es necesario partir de una solución
básica factible inicial. Supongamos, por simplicidad y sin pérdida de generalidad (de ser necesario
se pueden intercambiar los índices de las variables), que las variables básicas para esta solución
inicial son x1 , x2 , . . . , xm ; entonces la tabla asociada a la solución básica factible inicial es de la
forma

x1 x2 · · · xm xm+1 ··· xn−m xn−m+1 xn−m+2 ··· xn

x1 1 0 ··· 0 a1,m+1 ··· a1,n−m a1,n−m+1 a1,n−m+2 ··· a1n b1
x2 0 1 ··· 0 a2,m+1 ··· a2,n−m a2,n−m+1 a2,n−m+2 ··· a2n b2
.. .. .. .. .. .. .. .. .. .. .. .. ..
. . . . . . . . . . . . .
xm 0 0 ··· 1 am,m+1 · · · am,n−m am,n−m+1 am,n−m+2 · · · amn bm
−z 0 0 ··· 0 cm+1 ··· cn−m cn−m+1 cn−m+2 ··· cn −z0
(6.1)
es decir,
 
1 0 ··· 0 a1,m+1 ··· a1,n−m a1,n−m+1 a1,n−m+2 ··· a1n

 0 1 ··· 0 a2,m+1 ··· a2,n−m a2,n−m+1 a2,n−m+2 ··· a2n 

A= .. .. . . .. .. .. .. .. .. .. .. ,

 . . . . . . . . . . .


0 0 ··· 1 am,m+1 · · · am,n−m am,n−m+1 am,n−m+2 · · · amn
 
b1

 b2 

b= .. , c = [ 0 0 ··· 0 cm+1 · · · cn−m cn−m+1 cn−m+2 · · · cn ].
.
 
 
bm

Después de, digamos, k iteraciones del algoritmo simplex (que equivalen a operaciones elementales
sobre el sistema de ecuaciones correspondiente), la tabla de coeficientes del problema corresponde
a un nuevo conjunto de variables básicas, digamos, sin pérdida de generalidad, x n−m+1 , xn−m+2 ,
. . . , xn , y es de la forma

x1 x2 ··· xm xm+1 ··· xn−m xn−m+1 xn−m+2 · · · xn

xn−m+1 â11 â12 ··· â1m â1,m+1 ··· â1,n−m 1 0 ··· 0 b̂1
xn−m+2 â21 â22 ··· â2m â2,m+1 ··· â2,n−m 0 1 ··· 0 b̂2
.. .. .. .. .. .. .. .. .. .. .. .. ..
. . . . . . . . . . . . .
xn âm1 âm2 · · · âmm âm,m+1 · · · âm,n−m 0 0 ··· 1 b̂m
−z ĉ1 ĉ2 ··· ĉm ĉm+1 ··· ĉn−m 0 0 ··· 0 −z00
(6.2)
donde
 
â11 â12 ··· â1m â1,m+1 ··· â1,n−m 1 0 ··· 0

 â21 â22 ··· â2m â2,m+1 ··· â2,n−m 0 1 ··· 0 

 =  .. .. .. .. .. .. .. .. .. . . .. ,

 . . . . . . . . . . .


âm1 âm2 · · · âmm âm,m+1 · · · âm,n−m 0 0 ··· 1
 
b̂1
b̂2
 
 
b̂ =  .. , ĉ = [ ĉ1 ĉ2 · · · ĉm ĉm+1 · · · ĉn−m 0 0 · · · 0 ].
.
 
 
b̂m

La matriz B asociada a la base del ciclo k es el arreglo formado por las columnas de coeficientes
del sistema original (6.1) asociadas con las variables básicas de (6.2), es decir,
 
a1,n−m+1 a1,n−m+2 ··· a1n

 a2,n−m+1 a2,n−m+2 ··· a2n 

B= .. .. .. .. ,

 . . . .


am,n−m+1 am,n−m+2 · · · amn

donde la i-ésima columna de B corresponde a la variable básica con coeficiente unitario en el i-

ésimo renglón. La inversa B −1 de esta matriz es el arreglo arreglo formado por las columnas de
coeficientes de (6.2) asociadas con las variables básicas del sistema original (6.1), a saber, x 1 , x2 ,
. . . , xm ; en otras palabras,
 
â11 â12 ··· â1m
−1

 â21 â22 ··· â2m 

B = .. .. .. .. .

 . . . .


âm1 âm2 · · · âmm
Para justificar esta afirmación, consideremos la matriz
 
1 0 ··· 0 a1,n−m+1 a1,n−m+2 ··· a1n

 0 1 ··· 0 a2,n−m+1 a2,n−m+2 ··· a2n 

C= .. .. . . .. .. .. .. .. 

 . . . . . . . .


0 0 ··· 1 am,n−m+1 am,n−m+2 · · · amn
formada por los coeficientes de las variables de (6.1) después de eliminar las variables que no
son básicas ni en la tabla inicial ni en el ciclo k, a saber, xm+1 , . . . , xn−m (en ambos casos su
valor se iguala a cero para determinar la solución correspondiente). Después de una sucesión de k
operaciones elementales {Ei } sobre la tabla (6.1) se obtiene la tabla (6.2); denotemos por P i a la
matriz elemental asociada con la operación (elemental) de pivoteo E i . Entonces
 
â11 â12 ··· â1m 1 0 ··· 0

 â21 â22 ··· â2m 0 1 ··· 0 

Pk Pk−1 . . . P2 P1 C =  .. .. .. .. .. .. . . .. ,

 . . . . . . . .


âm1 âm2 · · · âmm 0 0 ··· 1
así que
   
1 0 ··· 0 â11 â12 ··· â1m

 0 1 ··· 0  
  â21 â22 ··· â2m 

P = Pk Pk−1 . . . P2 P1  .. .. . . .. = .. .. .. .. ,

 . . . .
 
  . . . .


0 0 ··· 1 âm1 âm2 · · · âmm
de donde
P = Pk Pk−1 . . . P2 P1 . (6.3)
Ahora bien, es claro que si partimos de P C y efectuamos las operaciones de pivoteo en orden
inverso obtendremos nuevamente C; esto siempre es posible ya que toda operación (elemental) de
pivoteo Ei con matriz asociada Pi siempre se puede deshacer al multiplicar por Pi−1 . En conse-
cuencia,
 
1 0 ··· 0 a1,n−m+1 a1,n−m+2 ··· a1n

0 1 ··· 0 a2,n−m+1 a2,n−m+2 ··· a2n 
P1−1 P2−1 . . . Pk−1
−1
Pk−1 (P C)
 
C= = .. .. . . .. .. .. .. .. ;

 . . . . . . . .


0 0 ··· 1 am,n−m+1 am,n−m+2 · · · amn
en particular
   
1 0 ··· 0 a1,n−m+1 a1,n−m+2 ··· a1n

0 1 ··· 0  
a2,n−m+1 a2,n−m+2 ··· a2n 
−1
P1−1 P2−1 . . . Pk−1 Pk−1 
   
.. .. . . .. = .. .. .. ..  = B,

 . . . .
 
  . . . .


0 0 ··· 1 am,n−m+1 am,n−m+2 · · · amn
de donde
B = P1−1 P2−1 . . . Pk−1
−1
Pk−1 = (Pk Pk−1 . . . P2 P1 )−1 = P −1 ,
y por consiguiente P = B −1 . La ecuación (6.3) se denomina forma producto de la inversa. Con-
cluimos que la inversa de la matriz B asociada a la base del ciclo k es el conjunto de coeficientes
en la tabla del ciclo k de las variables que eran básicas en el ciclo 0. Como consecuencia, tenemos
que

 = B −1 A, (6.4)
−1
b̂ = B b; (6.5)

de hecho para cualquier columna Âj de  se tiene

Âj = B −1 Aj . (6.6)

Esta operación no sería útil si hubiese que realizarla por cada columna de A pues sería demasiado
costoso numéricamente. Los multiplicadores simplex nos permiten realizar esta operación para una
sola columna.

6.1.2. Los multiplicadores simplex

Puesto que los sistemas (6.1) y (6.2) son equivalentes, las ecuaciones de (6.2) son combina-
ciones lineales de las ecuaciones de (6.1). Los multiplicadores simplex o precios se definen como
los números π1 , π2 , . . . , πm tales que la suma formada al multiplicar la i-ésima ecuación de (6.1)
por πi y después sumar las ecuaciones resultantes, darán como resultado, cuando se reste dicha
suma de la función objetivo de (6.1), la función objetivo de (6.2). En particular es obvio, en virtud
de que el único coeficiente no cero de x1 en (6.1) es la unidad (de la primera ecuaciòn), que el
coeficiente ĉ1 de x1 en la función objetivo de (6.2) es −π1 . Análogamente, los correspondientes
coeficientes ĉ2 , ĉ3 , . . . , ĉm de x2 , x3 , . . . , xm deben ser −π2 , −π3 , . . . , −πm . Por lo tanto, los
multiplicadores simplex π1 , π2 , . . . , πm se pueden usar para calcular los coeficientes de la función
objetivo ĉj en (6.2) a partir de la columna Aj correspondiente del sistema original (6.1) por medio
de la fórmula
ĉj = cj − (π1 a1j + π2 a2j + · · · + πm amj ). (6.7)

6.1.3. La matriz extendida asociada a la base y su inversa

La expresión (6.7) se puede reescribir en la forma
" #
Aj
ĉj = [ −π1 −π2 · · · −πm 1 ] , (6.8)
cj

en analogía con la ecuación (6.6). Esto sugiere que es posible realizar el cálulo con los multiplica-
dores (6.7) en la forma (6.6); la idea consiste en incorporar dentro de la matriz B a los coeficientes
cj de las columnas correspondientes para obtener una nueva matriz B ∗ cuya inversa respete el
producto (6.6) al mismo tiempo que su último renglón nos provee del producto (6.8).
La variable −z se puede considerar, desde el punto de vista de la discusión anterior, simplemen-
te una variable básica que permanece en la base desde el inicio del algoritmo hasta su terminación;
es por su invariancia que su columna se ignora durante el proceso de pivoteo. Si ahora inclui-
mos dentro de nuestra discusión a la variable básica −z y a su ecuación (la función objetivo), la
matriz B ∗ correspondiente a las variables básicas tiene la forma
 
a1,n−m a1,n−m+1 a1,n−m+2 ··· a1n 0
 a2,n−m a2,n−m+1 a2,n−m+2 ··· a2n 0 
.. .. .. .. ..
 
∗
 .. 
B =
 . . . . . .


 am,n−m am,n−m+1 am,n−m+2 · · · amn 0 
 

cn−m cn−m+1 cn−m+2 · · · cn 1

y su inversa es la matriz
 
â11 â12 ··· â1m 0
 â21 â22 ··· â2m 0 
.. .. ..
 
[B ∗ ]−1
 .. 
=
 . . . . 0 ,

 âm1 âm2 · · · âmm 0 
 

−π1 −π2 · · · −πm 1

y además, de manera análoga a (6.4) y (6.5), tenemos

" # " #
 ∗ −1 A
= [B ] , (6.9)
ĉ c
" # " #
b̂ ∗ −1 b
= [B ] . (6.10)
−z00 −z0

Las ecuaciones anteriores son de suma importancia para el algoritmo simplex con multiplicadores
pues nos permiten conocer cualquier coeficiente de la tabla (6.2) a partir de los coeficientes de la
tabla (6.1) y de [B ∗ ]−1 (aunque en realidad, de las dos ecuaciones, la primera es más empleada en
el algoritmo como veremos a continuación).

6.1.4. La idea central del algoritmo

En virtud de estas ecuaciones, con el método simplex con multiplicadores, únicamente se re-
quiere conocer ciertas columnas de  al inicio de un ciclo, a saber:

1. La inversa de la matriz extendida asociada a la base B ∗ para el ciclo k, que numéricamente

es lo mismo que las columnas del ciclo k asociadas a las variables básicas del ciclo 0 (de la
tabla inicial).
 2. La solución básica factible para el ciclo k, que se expresa como los valores constantes b̂i y
−z00 .y la base I a que corresponden; los valores de las variables no básicas se hacen cero.

Todos los demás datos necesarios para ejecutar los pasos del algoritmo simplex (original) se
calculan directamente de la tabla inicial (6.1) por medio de (6.9) y (6.10) conforme sean requeridos:
La ecuación (6.9) nos permite determinar los coeficientes ĉ j para elegir la columna del pivote y
después únicamente calcular Âj para elegir el pivote. Después se pivotea como si se hiciera con Â,
b̂ y ĉ, pero únicamente con las columnas de B ∗ y b̂, para evitar cálculos innecesarios, pues son los
únicos datos que necesitamos actualizar.

6.2. Descripción matricial del algoritmo simplex con multiplicadores

Ahora presentaremos el algoritmo simplex con multiplicadores con notación matricial para
seguir la notación empleada a lo largo del libro y para describir el algoritmo grosso modo de
manera apropiada. Como en la subsección 4.3, dado un problema

 máx z = cx,

P0 Ax = b,
x ≥ 0,



en forma estándar y dada una base I del mismo, se puede reescribir P 0 como

I J
 máx z = c xI + c xJ ,

P0 AI xI + AJ xJ = b,
xI , xJ ≥ 0,



donde J = {1, . . . , n} \ I. De aquí se dedujo que el mismo problema se puede escribir en la

llamada forma explícita con respecto a I como


 máx z,
0xI + (cJ − cI (AI )−1 AJ )xJ = z − cI (AI )−1 b,



 xI + (AI )−1 AJ xJ = (AI )−1 b,


xI , xJ ≥ 0.
La tabla de coeficientes correspondientes es

x
xI U (AI )−1 AJ (AI )−1 b
−z 0 cJ − cI (AI )−1 AJ −cI (AI )−1 b

donde U es una matriz identidad de m × m; esta tabla es la tabla de coeficientes empleada para
cada paso, i.e., pivoteo, del método simplex original. A partir de (partes de) esta tabla se extrae la
información necesaria para mejorar la solución disponible.
 Observemos que

( U (AI )−1 AJ ) = ( (AI )−1 AI (AI )−1 AJ ) = (AI )−1 A,

( 0 cJ − cI (AI )−1 AJ ) = ( cI − cI (AI )−1 AI cJ − cI (AI )−1 AJ )

= ( cI cJ ) − cI (AI )−1 ( AI AJ ) = c − cI (AI )−1 A.

Así, podemos reescribir la tabla como

x
xI (AI )−1 A (AI )−1 b
−z c − cI (AI )−1 A −cI (AI )−1 b

Como lo hicimos en la sección anterior, llamemos B a la matriz asociada a la base (es decir, a A I )
y π al vector cI (AI )−1 . Entonces esta tabla se puede reescribir como

x
xI B −1 A B −1 b (6.11)
−z c − πA −πb

En consecuencia, nuevamente vemos que la tabla correspondiente a cada pivoteo del algoritmo
simplex se puede obtener de la tabla del problema original si conocemos la matriz B y el vector π
para la correspondiente base I. Recordemos, sin embargo, que la idea esencial del método simplex
con multiplicadores (revisado) no es calcular la matriz B −1 y el vector de multiplicadores π para
cada iteración del algoritmo pues eso sería demasiado costoso computacionalmente hablando.
Para encontrar una manera más eficiente de aprovechar esta última tabla observamos que
" # " #" #
B −1 A B −1 b B −1 0 A b
=
c − πA −πb −π 1 c 0

y además " #" # " # " #

B 0 B −1 0 BB −1 0 U 0
= = ,
cI 1 −π 1 c B −1 − π 1
I 0 1
donde U es una matriz identidad de m × m. Por consiguiente, la inversa de la matriz
" #
∗ B 0
B =
cI 1
es " #
B −1 0
[B ∗ ]−1 = ,
−π 1
y el producto del i-ésimo renglón de esta última matriz por la j-ésima columna de la tabla inicial
nos permite encontrar la entrada (i, j) de la matriz
" #
B −1 A B −1 b
,
c − πA −πb

y por ende determinar para cualquier paso del algoritmo los coeficientes de la tabla (6.11). En
particular, el producto del último renglón de [B ∗ ]−1 por las columnas de
" #
A
c

nos da (6.7), y el producto de cada uno de los primeros m renglones de [B ∗ ]−1 por la j-ésima
columna de " #
A
c
nos da (6.6).

6.3. El procedimiento del método simplex revisado

Supongamos que se desea encontrar una solución óptima del problema en forma mixta (inter-
cambiando las ecuaciones si es necesario)

máx z = c 1 x1 + c 2 x2 + · · · + c k xk ,



a 11 x1 + a12 x2 + · · · + a1k xk ≤ b1 ,



.. .. .. ..



. . . .





a x + ap2 x2 + · · · + apk xk ≤ bp ,

p1 1



a x1 + ap+1,2 x2 + · · · + ap+1,k xk = bp+1 ,


 p+1,1
.. .. .. ..


P . . . .

aq1 x1 + aq2 x2 + · · · + aqk xk = bq ,





aq+1,1 x1 + aq+1,2 x2 + · · · + aq+1,k xk ≥ bq+1 ,



.. .. .. ..



. . . .





am1 x1 + am2 x2 + · · · + amk xk ≥ bm ,




xi ≥ 0, i = 1, . . . , k.


El objetivo del método simplex revisado es hacer única y exclusivamente los cálculos que sean
necesarios para cada pivoteo del algoritmo simplex, y ninguno más. Además, en la práctica, se
tiene un segundo objetivo que siempre está presente cuando se trabaja con problemas lineales de
gran magnitud en una computadora: economizar lo más posible el uso de la memoria rápida (de
acceso aleatorio) del sistema.
6.3.1. Tabla inicial para la memoria lenta
La tabla inicial para el método simplex siempre se almacena en memoria lenta y se mantienen
en memoria rápida únicamente los datos necesarios para la iteración que se está efectuando. No
discutiremos aquí los detalles sobre la administración de memoria, sino que nos enfocaremos a los
aspectos operativos del método simplex revisado. Supongamos que después de escribir P en forma
estándar y de hacer los términos constantes bi ≥ 0 hemos obtenido un problema en forma estándar

máx z = c1 x1 + c2 x2 + · · · + cn xn ,



a11 x1 + a12 x2 + · · · + a1n xn = b1 ,






 a21 x1 + a22 x2 + · · · + a2n xn = b2 ,
P .. .. ..
..


 . . .
.
am1 x1 + am2 x2 + · · · + amn xn = bm ,





xi ≥ 0, i = 1, . . . , n,


Para poder aplicar el algoritmo simplex en el problema P debemos introducir variables artificiales
básicas xn+1 ≥ 0, xn+2 ≥ 0, . . . , xn+m ≥ 0 e introducir la función objetivo auxiliar ϕ para formar
el problema auxiliar


 mı́n ϕ
−ϕ d 1 x1 + d 2 x2 + · · · + d n xn = −ϕ0





−z + c 1 x1 + c 2 x2 + · · · + c n xn = 0,






 a11 x1 + a12 x2 + · · · + a2n xn + xn+1 = b1 ,
PA a21 x1 + a22 x2 + · · · + a1n xn + xn+2 = b2 ,
.. .. .. ..

..


. . . . .





am1 x1 + am2 x2 + · · · + amn xn + xn+m = bm ,






xi ≥ 0, i = 1, . . . , n + m.

La tabla inicial para el método simplex está formada por los coeficientes de P A y es de la forma

x1 x2 ··· xn xn+1 xn+2 · · · xn+m

xn+1 a11 a12 ··· a1n 1 0 ··· 0 b1
xn+2 a21 a22 ··· a2n 0 1 ··· 0 b2
.. .. .. .. .. .. .. .. .. ..
. . . . . . . . . .
xn+m am1 am2 · · · amn 0 0 ··· 1 bm
−z c1 c2 ··· cn 0 0 ··· 0 0
−ϕ d1 d2 ··· dn 0 0 ··· 0 −ϕ0

y se almacena en memoria lenta.

6.3.2. Datos para cada iteración para la memoria rápida
En la memoria rápida se almacenan únicamente los datos necesarios para realizar la siguiente
iteración.

El algoritmo simplex revisado para P A

Primero debemos resolver el problema auxiliar P A (fase I) para encontrar una base factible
para iniciar el algoritmo simplex para resolver P (fase II). Se inicia con una solución factible
cuyas variables básicas son xn+1 , xn+2 , . . . , xn+m . Para formar la matriz [B ∗ ]−1 se copian las m
columnas de coeficientes de las variables básicas a un arreglo de (m + 2) × (m + 2) en la forma

1 0 ··· 0 0 0
 
 0 1 ··· 0 0 0 
.. .. . . .. .. .. 
 

[B ∗ ]−1

= . . . . . .  .
0 0 ··· 1 0 0 
 

0 0 ···
 
 0 1 0 
0 0 ··· 0 0 1

Los términos constantes se almacenan en el vector

b1
 
 b2 
..
 
 

b̂ =  . 
;
 bm
 

 
 0 
−ϕ0

aunque el vector b̂ se podría obtener a partir de la tabla inicial y de [B ∗ ]−1 , usualmente se mantiene
en memoria rápida para agilizar las operaciones (es lo que los programadores denominarían “un
caché”). También es necesario almacenar la base I como conjunto ordenado para saber cuáles son
las variables básicas en cada paso del algoritmo.
Después de, digamos, k iteraciones del algoritmo simplex revisado, la matriz [B ∗ ]−1 tendrá la
forma
â1,n+1 â1,n+2 · · · â1,n+m 0 0
 
 â2,n+1 â2,n+2 · · · â2,n+m 0 0 
.. .. .. .. .. .. 
 
.

[B ∗ ]−1 = 
 . . . . .  .
 âm,n+1 âm,n+2 · · · âm,n+m 0 0 
 
 ĉn+1 ĉn+2 · · · ĉn+m 1 0 
 

dˆn+1 dˆn+2 · · · dˆn+m 0 1

Para determinar la solución básica factible para la iteración k + 1 debemos determinar la variable
que entrará la base. Calculamos dˆj para j = 1, . . . , n + m por medio de la fórmula
 
Aj
dˆj = [ dˆn+1 dˆn+2 · · · dˆn+m 0 1 ]  cj  .
 
dj

Una vez que hemos determinado la columna de la variable que entrará a la base, calculamos sus
coeficientes por medio de la fórmula
   
Âj Aj
∗ −1 
 ĉj  = [B ]  cj  .
  

dˆj dj

Con esta información se pivotea sobre el arreglo

â1j â1,n+1 â1,n+2 ··· â1,n+m 0 0

 

   â2j â2,n+1 â2,n+2 ··· â2,n+m 0 0 

Âj .. .. .. .. .. .. .. 
 
.


ĉ
 j [B ∗ −1 
] =
 
 . . . . . . 
 âmj âm,n+1 âm,n+2 · · · âm,n+m 0 0 
 
dˆj
 ĉj ĉn+1 ĉn+2 · · · ĉn+m 1 0 
 

dˆj ˆ
dn+1 dˆn+2 · · · dˆn+m 0 1

y se almacenan los cambios en [B ∗ ]−1 .

El algoritmo simplex revisado para P

Cuando ya se tiene una solución básica factible para P se eliminan el último renglón y la última
columna de [B ∗ ]−1 para obtener
 
â1,n+1 â1,n+2 ··· â1,n+m 0
 â2,n+1 â2,n+2 ··· â2,n+m 0 
.. .. .. ..
 
[B ∗ ]−1
 .. 
=
 . . . . .
.

 âm,n+1 âm,n+2 · · · âm,n+m 0 
 

ĉn+1 ĉn+2 · · · ĉn+m 1

Nuevamente, para determinar la solución básica factible para la siguiente iteración determinamos
la variable que entrará la base. Calculamos ĉj para j = 1, . . . , n + m por medio de la fórmula
" #
Aj
ĉj = [ ĉn+1 ĉn+2 · · · ĉn+m 1 ] .
cj
Una vez elegida la variable a entrar a la base se calcula la columna de la misma por medio de
" # " #
Âj ∗ −1 Aj
= [B ] .
ĉj cj

A continuación se pivotea sobre el arreglo

 
â1j â1,n+1 â1,n+2 ··· â1,n+m 0
" #  â2j â2,n+1 â2,n+2 ··· â2,n+m 0 
Âj .. .. .. .. ..
 
[B ∗ ]−1 = 
 .. 
ĉj  . . . . . .
.

 âmj âm,n+1 âm,n+2 · · · âm,n+m 0 
 

ĉj ĉn+1 ĉn+2 · · · ĉn+m 1

El proceso termina cuando se ha encontrado una solución óptima para P .

Ejercicios del capítulo 6

1. Indícale a la doctora Rebeca del Rocío Peniche que este capítulo no tiene ejercicios.

2. Busca un culpable.
Capítulo 7

Dualidad

La dualidad es una herramienta muy útil en la programación lineal. Nos permite desarrollar un
método más eficiente para encontrar la solución de un problema lineal y es bastante interesante en
sí por los resultados teóricos que proporciona.
La siguiente definición se debe a Von Neumann.

Definición 7.1 Dado un problema lineal en forma canónica


 máx

s.a.
z = cx,
P Ax ≤ b,

x ≥ 0,


el problema dual D del problema primal P es

z = bT y,

 mı́n

s.a.
D AT y ≥ cT ,

y ≥ 0,


el cual también es un problema lineal.

Ejemplo 7.1 El problema dual del problema lineal

máx z = 3x1 + 5x2 ,

s.a.



x1 + 3x2 ≤ 7,



P 2x1 ≤ 8,

x1 + 5x2 ≤ 4,




x1 , x2 ≥ 0,


es 
mı́n w = 7y1 + 8y2 + 4y3 ,
 s.a.



D y1 + 2y2 + y3 ≥ 3,


 3y1 + 5y3 ≥ 5,
y1 , y2 , y3 ≥ 0.


105
Proposición 7.1 El dual del dual es el primal.
Demostración. Podemos escribir D de manera equivalente como
−w = −bT y,

 − máx

s.a.
D0 −AT y ≤ −cT

y ≥ 0.


El dual de D 0 es, por definición,

z 0 = −cx,

 − mı́n

s.a.
P0 −Ax ≥ −b,

x ≥ 0,


o equivalentemente,
−z 0 = cx,

 máx

s.a.
P0 Ax ≤ b,

x ≥ 0.


Si hacemos z = −z 0 , entonces P 0 es idéntico a P .

Observación 7.1 El dual del problema en forma estándar


 máx

s.a.
z = cx,
P Ax = b,

x ≥ 0,


es
w = bT y,

 mı́n

s.a.
D AT y ≥ cT
y s.r.s.



En efecto, P es equivalente a 
máx z = cx,
 s.a.



P Ax ≤ b,


 −Ax ≤ −b,
x ≥ 0,


cuyo dual es, por definición,

w = bT y 0 − bT y 00 ,

 mı́n

s.a.
D0 AT y 0 − AT y 00 ≥ cT ,
y 0 , y 00 ≥ 0.



Si hacemos y = y 0 − y 00 , entonces D 0 es equivalente a D.

Esta observación la generalizamos en la tabla 7.1.
 Primal (Dual) Dual (Primal)
maximizar función objetivo minimizar función objetivo
i-ésima restricción ≥ i-ésima variable ≤ 0
i-ésima restricción ≤ i-ésima variable ≥ 0
i-ésima restricción = i-ésima variable s.r.s.
j-ésima variable ≥ 0 j-ésima restricción ≥
j-ésima variable ≤ 0 j-ésima restricción ≤
j-ésima variable s.r.s. j-ésima restricción =

Tabla 7.1: Correspondencia entre las restricciones y variables de un problema primal y su dual.

Ejemplo 7.2 El dual del problema


mı́n w = 3x1 + 4x2 + x3 ,
s.a.



x1 + x2 + 2x3 ≥ 1,





2x + x3 ≤ 2,

1


P x2 = −3,

x1 ≥ 0,




x2 ≤ 0,




x3 s.r.s.,



es

máx z = y1 + 2y2 − 3y3 ,
s.a.



y1 + 2y2 ≤ 3,





y1 + y3 ≥ 4,



D 2y1 + y2 = 1,

y1 ≥ 0,




y2 ≤ 0,




y3 s.r.s.



7.1. Relación entre los valores de las funciones objetivo de los proble-
mas lineales duales
Para las demostraciones siguientes, consideremos un problema lineal

 máx

s.a.
z = cx,
P Ax ≤ b,

x ≥ 0,

y su dual
w = bT y,

 mı́n

s.a.
D AT y ≥ cT ,

y ≥ 0.


Teorema 7.1 (Forma débil de dualidad) Para todo par de soluciones realizables x̄, ȳ de P y D,
respectivamente, tenemos
z̄ = cx̄ ≤ bT ȳ = w̄.

Demostración. Al multiplicar cada restricción Ai x̄ ≤ bi de P por ȳ i , como ȳ i ≥ 0, la desigualdad

se conserva y resulta
ȳ i Ai x̄ ≤ ȳ i bi .

Al sumar las m desigualdades, obtenemos

m
X m
X
ȳ i Ai x̄ ≤ ȳ i bi ,
i=1 i=1

es decir,
ȳ T Ax̄ ≤ bT ȳ.

Análogamente, multiplicando cada restricción (Aj )T ȳ ≥ cj de D por x̄j , como x̄j ≥ 0, la desi-
gualdad también se conserva y resulta

x̄j (Aj )T ȳ ≥ x̄j cj .

Al sumar las n desigualdades, obtenemos

n
X n
X
x̄j (Aj )T ȳ ≥ x̄j cj ,
j=1 j=1

o bien,
x̄T AT ȳ ≥ x̄T cT ;

puesto que
(ȳ T Ax̄)T = x̄T AT ȳ ≥ x̄T cT = (cx̄)T ,

vemos que
ȳ T Ax̄ ≥ cx̄,

Por consiguiente,
z̄ = cx̄ ≤ ȳ T Ax̄ ≤ bT ȳ = w̄.
Ejemplo 7.3 Dada la solución factible x̄ = (2, 0) del problema

máx z = 4x1 + 7x2 ,
 s.a.



P 3x1 + 5x2 ≤ 6,


 x1 + 2x2 ≤ 8,
x1 , x2 ≥ 0,


y la solución factible ȳ = ( 75 , 0) de su dual


mı́n w = 6y1 + 8y2 ,
 s.a.



D 3y1 + y2 ≥ 4,


 5y1 + 2y2 ≥ 7,
y1 , y2 ≥ 0,


tenemos

z = cx̄ = 8,
w = bT ȳ = 8.4.

Por lo tanto, la solución óptima para ambos tiene un valor entre 8 y 8.4, ya que cx ≤ b T y. Estos
datos nos permiten en un momento dado detener el proceso de solución con una solución “casi
óptima.”

Corolario 7.1 Sean x̄ una solución factible de P y ȳ una solución factible de D. Si cx̄ = b T ȳ ,
entonces x̄ y ȳ son soluciones óptimas de P y D, respectivamente.
Demostración. Supongamos que existe una solución factible x̄ 0 de P tal que cx̄0 > cx̄. Como
cx̄ = bT ȳ, vemos que cx̄0 > bT ȳ, lo cual contradice la forma débil del teorema de dualidad
(teorema 7.1).
Similarmente, si existiese una solución factible ȳ 0 de P tal que bT ȳ 0 < bT ȳ, tendríamos bT ȳ 0 <
cx̄, otra contradicción con la forma débil del teorema de dualidad.

Ejemplo 7.4 Consideremos el problema


máx z = x1 + 3x2 ,
 s.a.



P x1 + x2 ≤ 5,


 −x1 + x2 ≤ 2,
x1 , x2 ≥ 0,


y su problema dual 
mı́n w = 5y1 + 2y2 ,
 s.a.



D y1 − y2 ≥ 1,


 y1 + y2 ≥ 3,
y1 , y2 ≥ 0.

Tenemos que x̄ = ( 23 , 72 ) es una solución factible para P y ȳ = (2, 1) es una solución factible
paraa D, y además
3
cx̄ = 2 + (3)( 27 ) = 12,
bT ȳ = (5)(2) + (2)(1) = 12,

es decir, cx̄ = bT ȳ. Por ende, x̄ y ȳ son soluciones óptimas de P y D, respectivamente.

Teorema 7.2 Si P tiene una solución óptima, entonces D también tiene una solución óptima, y
además zmáx = wmı́n .
Demostración. Podemos reescribir el problema P en forma estándar como

 máx

s.a.
z = cx,
P0 Ax + U h ≤ b,

x, h ≥ 0,


donde U es una matriz identidad (de m × m) y h es un vector de variables de holgura. Haciendo

à !
x
c0 = ( c 0 ), x0 = , B = ( A U ),
h

obtenemos
z = c 0 x0 ,

 máx

s.a.
P0 Bx0 = b,
x0 ≥ 0.



Por hipótesis, el problema P tiene una solución óptima (finita), de donde, por las proposiciones 3.7
y 3.10, existe una solución óptima básica x̄∗ de P 0 asociada a una base I. Así pues, podemos
escribir el problema en forma explícita con respecto a I como

máx z,
 s.a.


0x0I + [(c0 )J − zJ ]x0J = z − z0 ,




 x0I + (B I )−1 B J x0J = (AI )−1 b,
x0I , x0J ≥ 0,


donde

z0 = (c0 )I (B I )−1 b,
zj = (c0 )I (B I )−1 B j , j ∈ J.

La solución básica es, como es usual, x̄∗I = (B I )−1 b y x̄∗J = 0. Podemos reescribir la función
objetivo como

z = (c0 )I (B I )−1 b + [(c0 )I − (c0 )I (B I )−1 B I ]x0I + [(c0 )J − (c0 )I (B I )−1 B J ]x0J
(donde 0 = (c0 )I − (c0 )I (B I )−1 B I ). Puesto que x̄∗ es una solución óptima, sabemos que
(c0 )J − (c0 )I (B I )−1 B J ≤ 0,
(c0 )I − (c0 )I (B I )−1 B I ≤ 0.
Al reescribir estas desigualdades obtenemos
(c0 )I (B I )−1 B J ≥ (c0 )J ,
(c0 )I (B I )−1 B I ≥ (c0 )I ,
o bien
(c0 )I (B I )−1 ( B I B J ) ≥ ( (c0 )I (c0 )J ).
La matriz ( B I B J ) no es más que la matriz B = ( A U ) pero con diferente arreglo; de igual
forma, el vector ( (c0 )I (c0 )J ) es igual al vector c0 = ( c 0 ), excepto por su disposición. Por
consiguiente, podemos escribir la desigualdad anterior como
(c0 )I (B I )−1 ( A U ) ≥ ( c 0 ).
La desigualdad se conserva si reemplazamos por las respectivas transpuestas, i.e.,
AT [(c0 )I (B I )−1 ]T ≥ cT ,
(7.1)
U T [(c0 )I (B I )−1 ]T ≥ 0.

Definamos ȳ ∗ = [(c0 )I (B I )−1 ]T . Entonces ȳ ∗ es una solución factible del problema dual D,
pues (7.1) indica que ȳ ∗ satisface las restricciones duales. Más aún, al evaluar en la solución ȳ ∗
la función objetivo dual vemos que
bT ȳ ∗ = bT [(c0 )I (B I )−1 ]T = [(c0 )I (B I )−1 b]T = (c0 )I (B I )−1 b = (c0 )I x̄∗I ,
es decir, bT ȳ ∗ también es el valor óptimo para la función objetivo de P . En consecuencia, por el
corolario 7.1, ȳ ∗ es una solución óptima para D.

Ejemplo 7.5 Consideremos el problema


mı́n w = x1 + x2
 s.a.



x1 − x2 ≤ 5,


 2x1 + x2 ≥ 3,
x1 , x2 ≥ 0,


cuyo problema dual es

 máx z = 5y1 + 3y2

s.a.


y1 + 2y2 ≤ 1,



 −y1 + y2 ≤ 1,
y1 ≤ 0,




y2 ≥ 0.

 3
Una solución óptima para P es x1 = 2 y x2 = 0, es decir, wmı́n = 32 . Entonces D también admite
una solución óptima, a saber,
y1 = 0, y2 = 12 ,
es decir,
3
zmáx = 2 = wmı́n .

Teorema 7.3 (Fundamental de dualidad) Dados dos problemas lineales duales P y D:

(i) Si los dos problemas admiten una solución realizable, admiten ambos una solución realizable
óptima y zmáx = wmı́n .
(ii) Si uno de los problemas posee una clase de soluciones para la cual el valor de la función
objetivo no está acotado (z → ∞ ó w → −∞), el otro no posee solución realizable.
(iii) Si P (respectivamente D) posee una solución realizable pero no D (respectivamente P ), en-
tonces P (respectivamente D) posee una clase de soluciones tal que la función objetivo no
está acotada.
(iv) Puede suceder que ni P ni D admitan una solución realizable.

Demostración.

(i) Si P y D tienen soluciones realizables x̄ y ȳ respectivamente, por la forma débil de dualidad

(teorema 7.1), tenemos z̄ = cx̄ ≤ bT ȳ = w̄. Por consiguiente, el algoritmo simplex garantiza
la existencia de una solución óptima para P , así que, por el teorema 7.2, D también tiene
una solución óptima y zmáx = wmı́n .

(ii) Supongamos, sin pérdida de generalidad, que P tiene una clase de soluciones para la cual z →
∞ y que y es una solución factible para D. Como z → ∞ podemos encontrar una solución x
de P para la cual bT y < cx, lo cual es absurdo ya que contradice la forma débil de dualidad
(teorema 7.1).

(iii) Supongamos, sin pérdida de generalidad, que P posee una solución realizable pero no D. En-
tonces, por el teorema fundamental de la programación lineal (teorema 5.1), posee una solu-
ción realizable básica y por consiguiente se puede iniciar el algoritmo simplex. Si P tuviese
una solución óptima finita entonces, también por el teorema fundamental de la programación
lineal, tendría una solución óptima básica. Por lo tanto, por el teorema 7.2 el problema D
también tendría una solución óptima (realizable), una contradicción con nuestras hipótesis.
Así pues, P ño puede tener un óptimo finito.

(iv) Esto se ilustra en el ejemplo 7.6 inciso (iv).

Los resultados del teorema 7.3 se resumen en la tabla 7.2. En el ejemplo 7.6 se muestran las
cuatro posibilidades que se enumeran en el mismo teorema.
 P ño tiene solu-
P tiene solución realizable
ción realizable
P tiene solución P ño tiene solu-
óptima ción óptima
D tiene solución Imposible por (i) Imposible por (iii)
(i) zmáx = wmı́n
D tiene solución óptima
realizable Dño tiene solu- Imposible por (i) Imposible por (i)
(ii) w → −∞
ción óptima
Dño tiene solu- Imposible por (iii)
(ii) z → ∞ Posible por (iv)
ción realizable

Tabla 7.2: Esquema de las opciones que ofrece el teorema fundamental de dualidad (teorema 7.3).

Ejemplo 7.6 Los siguientes pares de problemas ejemplifican las correspondientes opciones esta-
blecidas en el teorema 7.3.

 
 máx

s.a.
z = 2x1 ,  mı́n

s.a.
w = 3y1 ,
(i) P x1 ≤ 3, D y1 ≥ 2,
 
x1 ≥ 0. y2 ≥ 0.
 

[ ] - [ [ -
0 3 0 2

zmáx = 6 con x1 = 3. wmı́n = 6 con y1 = 2.

 
 máx z = 2x1 ,  mı́n w = −3y1 ,
s.a. s.a.
 
(ii) P x1 ≥ −3, D y1 ≥ 2,
 
x1 ≥ 0. y1 ≤ 0.
 

[ [- ] [ -
−3 0 0 2

z → ∞. No existe solución realizable para D.

  
 máx z = 2x1 ,  mı́n w = −3y1 ,
s.a. s.a.
 
(iii) P x1 ≤ −3, D y1 ≥ 2,
 
x1 ≥ 0. y1 ≥ 0.
 

] [- [ [ -
−3 0 0 2

No existe solución realizable para P . w → −∞.

y1 − y2
 
 máx z = x1 + x2 ,  mı́n w=
 s.a.  s.a.
 
 
(iv) P x1 − x2 = 1, D y1 + y2 ≥ 1,


 x1 − x2 = −1, 

 −y1 − y2 ≥ 1,
x1 , x2 ≥ 0. y1 , y2 s.r.s.
 

xy2 yy2
x1 x2 = 1 y1 + y2 = 1

x1 yx1

x1 x2 = 1 y1 y2 = 1

No existe solución realizable ni para P ni para D.

7.2. Holguras complementarias

Definición 7.2 Decimos que la i-ésima restricción de un problema lineal P es activa para una
solución x si
Ai x = b i .
En caso contrario, si
Ai x + h i = bi con hi 6= 0,
decimos que la i-ésima restricción es no activa.

Teorema 7.4 (Débil de holguras complementarias) Una condición necesaria y suficiente para
que un par de soluciones realizables de problemas lineales duales P y D sean óptimas es que:
(i) Si una restricción de uno de los problemas lineales se satisface como desigualdad estricta (es
no activa), la variable correspondiente del dual es nula.

(ii) Si una variable de uno de los problemas es positiva, la restricción correspondiente del dual se
satisface como ecuación (es activa).

Demostración. Agregando variables de holgura, los problemas P y D pueden escribirse en la

forma 
 máx

s.a.
z = cx,
P Ax + β = b, (7.2)

x, β ≥ 0,


y
w = y T b,

 mı́n

s.a.
D y T A − γ T = c, (7.3)

y, γ ≥ 0.


Sea (x̄, β̄) una solución realizable de P y (ȳ, γ̄) una solución realizable de D. Entonces

β̄ = b − Ax̄,
γ̄ T = −c + ȳ T A,

de donde

ȳ T β̄ = ȳ T b − ȳ T Ax̄,
γ̄ T x̄ = −cx̄ + ȳ T Ax̄;

al sumar ambas igualdades resulta

ȳ T β̄ + γ̄ T x̄ = ȳ T b − cx̄. (7.4)

Necesidad. Si las soluciones son óptimas, tenemos ȳ T b = cx̄. La condición necesaria se deduce
entonces del hecho que x̄, β̄, ȳ T , γ̄ ≥ 0 y ȳ T β̄ + γ̄ T x̄ = 0 (es decir, ȳ T β̄ = 0 y γ̄ T x̄ = 0) pues

γ̄ > 0 implica x̄ = 0,
β̄ > 0 implica ȳ = 0,
x̄ > 0 implica γ̄ = 0,
ȳ > 0 implica β̄ = 0.

Suficiencia. Si las condiciones del teorema se satisfacen, tenemos ȳ T β̄ = 0 y γ̄ T x̄ = 0, y en

consecuencia ȳ T b = cx̄, lo que garantiza, por el corolario 7.1, que x̄ y ȳ son soluciones óptimas
de P y D, respectivamente.
Observación 7.2 El teorema 7.4 nos indica lo que sucede cuando x̄ es una solución óptima, pero
no nos indica lo que pasa cuando no lo es. Supongamos que x̄ es una solución factible no óptima
de P y se satisfacen las condiciones del teorema débil de holguras complementarias, i.e., ȳ T β̄ +
γ̄ T x̄ = 0. En este caso, en virtud de (7.4), se tiene que ȳ T b = cx̄. Puesto que es imposible
(forma débil de dualidad) que una solución factible ȳ de D satisfaga ȳ T b = cx̄ ≤ zmáx = wmı́n ,
necesariamente, ȳ debe ser no factible. Así pues, si partimos de una solución no óptima x̄ del
problema P , y aplicamos holguras complementarias para obtener una solución ȳ de D, la solución ȳ
no es factible.

Ejemplo 7.7 Demostremos que x̄ = (4, 0) (con z = 4) es solución óptima de

mı́n z = −x1 + 2x2 ,

s.a.



x1 − x2 ≤ 4,



P x1 + 2x2 ≥ 3,

x1 + x2 ≥ 2,




x1 , x2 ≥ 0,


por medio del teorema débil de holguras complementarias. El correspondiente problema dual es
máx w = 4y1 + 3y2 + 2y3 ,

s.a.



y1 + y2 + y3 ≤ −1,



D −y1 + 2y2 + y3 ≤ 2,

y1 ≤ 0,




y2 , y3 ≥ 0.


Para obtener la correspondiente solución para D procedemos como sigue:

Como la segunda y la tercera restricciones de P se satisfacen como desigualdades, por (i),
hacemos ȳ2 = 0 y ȳ3 = 0.
Como la primera variable x̄1 = 4 de P es positiva, por (ii), la primera restricción de D se
debe satisfacer como igualdad, es decir, ȳ1 + ȳ2 + ȳ3 = −1, de donde ȳ1 = −1.
Entonces la correspondiente solución para D es ȳ = (−1, 0, 0). Puesto que esta solución es factible
para D, se sigue que x̄ es solución óptima para P . (Además, para ȳ tenemos w = −4, como era de
esperarse.)
¿Qué sucedería si no partiésemos de una solución óptima para P , digamos x̄ = (1, 1) (para la
cual z = 1)? Procedamos de manera análoga a como lo hicimos en la sección anterior:
Como la primera restricción de P se satisface como desigualdad, por (i), hacemos ȳ 1 = 0.
Como la primera y la segunda variables x̄1 = 1 y x̄2 = 1 de P son positivas, por (ii), la
primera y la segunda restricciones de D se deben satisfacer como igualdad, es decir,
ȳ1 + ȳ2 + ȳ3 = −1,
−ȳ1 + 2ȳ2 + ȳ3 = 2,
 o equivalentemente,

ȳ2 + ȳ3 = −1,

2ȳ2 + ȳ3 = 2,

de donde ȳ2 = 3 y ȳ3 = −4. Entonces la correspondiente solución para D es ȳ = (0, 3, −4),
la cual no es factible para D. (Lo cual es consecuencia de lo establecido en la observa-
ción 7.2.)

Ejemplo 7.8 Consideremos el problema


mı́n z = 2x1 + 3x2 + 5x3 + 2x4 + 3x5 ,
 s.a.



P x1 + x2 + 2x3 + x4 + 3x5 ≥ 4,


 2x1 − 2x2 + 3x3 + x4 + x5 ≥ 3,
x1 , x2 , x3 , x4 , x5 ≥ 0.


Su problema dual 
máx w = 4y1 + 3y2 ,
s.a.



y1 + 2y2 ≤ 2,





y1 − 2y2 ≤ 3,



D 2y1 + 3y2 ≤ 5,

y1 + y 2 ≤ 2,




3y1 + y2 ≤ 3,





y1 , y 2 ≥ 0.


se puede resolver gráficamente (figura 7.1). La intersección de la primera y la quinta restricciones

satisfechas como igualdad de D satisface

y1 + 2y2 = 2,
3y1 + y2 = 3,

de donde ȳ = ( 45 , 35 ) es una solución óptima de D, y por consiguiente wmáx = 5. Ahora podemos

encontrar una solución óptima de P por medio de holguras complementarias:

Como la segunda, la tercera y la cuarta restricciones de D se satisfacen como desigualdades

estrictas, debemos tener x̄2 = 0, x̄3 = 0 y x̄4 = 0.
4
Como ȳ1 = 5 y ȳ2 = 35 , ambas restricciones deben satisfacerse como igualdad, es decir,

x̄1 + x̄2 + 2x̄3 + x̄4 + 3x̄5 = 4,

2x̄1 − 2x̄2 + 3x̄3 + x̄4 + x̄5 = 3,
 3y1 + y2 = 3

yy2

y1 + y2 = 2

2y1 + 3y2 = 5

y1 + 2y2 = 2

yx1

y1 2y2 = 3 z = 4y1 + 3y2 = 5

Figura 7.1: Región de soluciones factibles del problema dual D del ejemplo 7.8.

o equivalentemente,

x̄1 + 3x̄5 = 4,
2x̄1 + x̄5 = 3,

de donde x̄1 = 1 y x̄5 = 1.

Por consiguiente, x̄ = (1, 0, 0, 0, 1) es una solución óptima de P tal que z mı́n = 5.

Como es de esperarse, también existe un teorema fuerte de holguras complementarias. Lo enun-

ciamos aquí para el conocimiento del lector pero omitimos su demostración en virtud de que no
empleamos este resultado.

Teorema 7.5 (Fuerte de holguras complementarias) Si los problemas lineales duales P y D tie-
nen una solución realizable, entonces existe una pareja de soluciones óptimas de P y D tales que

(i) Si una restricción de uno de los problemas lineales es igualdad, entonces la variable correspon-
diente del otro problema es positiva.

(ii) Si una variable de uno de los problemas es nula, entonces la restricción correspondiente del
otro es desigualdad estricta.
7.3. Condiciones de optimalidad de Kuhn-Tucker
Consideremos un problema P en la forma (7.2) y su correspondiente dual D en la forma (7.3).
Si el problema P tiene una solución óptima (x̄∗ , β̄ ∗ ), entonces, en particular, x̄∗ satisface las res-
tricciones originales de P , a saber, Ax̄∗ ≤ b con x̄∗ ≥ 0 y además β̄ ∗ = b − Ax̄∗ . Si (ȳ ∗ , γ̄ ∗ )
es una solución óptima de D, entonces, en particular, es una solución factible de D, y por ende
(ȳ ∗ )T A − (γ̄ ∗ )T = c, o bien, c − (ȳ ∗ )T A + (γ̄ ∗ )T = 0. Entonces, por el teorema débil de holguras
complementarias, una condición necesaria y suficiente para que x̄ ∗ sea solución óptima de P es
que
(ȳ ∗ )T β̄ ∗ = 0,
(γ̄ ∗ )T x̄∗ = 0,
o equivalentemente
(ȳ ∗ )T (b − Ax̄∗ ) = 0,
(γ̄ ∗ )T x̄∗ = 0.
De esta breve discusión se desprenden las siguientes tres condiciones para determinar la optimali-
dad de una solución x̄ del problema primal P , conocidas como las condiciones de optimalidad de
Kuhn-Tucker:

1. Ax̄ ≤ b con x̄ ≥ 0 (factibilidad del primal),

2. c − y T A + γ T = 0 con y, γ ≥ 0 (factibilidad del dual),
3. y T (−Ax̄ + b) = 0 y γ T x̄ = 0 (holgura complementaria).

Ejemplo 7.9 En el problema


máx z = x1 + 2x2 ,
 s.a.



P x1 + x2 ≤ 5,


 −x1 + 2x2 ≤ 4,
x1 , x2 ≥ 0,


verificar las condiciones de optimalidad de Kuhn-Tucker para x̄ = (0, 0) y x̄ = (2, 3).

Para x̄ = (0, 0):

1. Ax̄ ≤ b con x̄ ≥ 0. Se sigue del hecho que

à !
0
x̄ = ≥ 0,
0
à !à ! à ! à !
1 1 0 0 5
Ax̄ = = ≤ = b.
−1 2 0 0 4
 2. c − y T A + γ T = 0 con y, γ ≥ 0. Necesitamos proponer un vector y = (y 1 , y2 ) y un
vector γ = (γ1 , γ2 ) tales que c − y T A + γ T = 0, es decir, tales que
à !
1 1
( 1 2 ) − ( y1 y2 ) + ( γ1 γ2 ) = ( 0 0 ).
−1 2

Por lo tanto tenemos que resolver el sistema

1 − y1 + y2 + γ1 = 0,
2 − y1 − 2y2 + γ2 = 0,

o el sistema equivalente,

y1 − y2 − γ1 = 1,
y1 − 2y2 − γ2 = 2.

Como necesitamos una solución no negativa del sistema, podemos resolverlo utilizan-
do el algoritmo simplex (para ser más precisos, la primera fase del método simplex,
empleando variables artificiales para obtener una solución factible) para minimizar ϕ
con la tabla inicial

y1 y2 γ1 γ 2 a1 a2
a1 1 −1 −1 0 1 0 1
a2 1 2 0 −1 0 1 2
−ϕ −2 −1 1 1 0 0 −3

Se deja al lector suplir los pasos necesarios que nos llevan a la solución y = ( 43 , 13 ) y
γ = (0, 0). Así pues, hemos encontrado y y γ que satisfacen la segunda condición.
3. y T (−Ax̄ + b) = 0 y γ T x̄ = 0. Tenemos que
"Ã !Ã ! Ã !#
4 1 −1 −1 0 5
y T (−Ax̄ + b) = ( 3 3 ) +
1 −2 0 4
à !
4 1 5
=( 3 3 ) = 8 6= 0,
4
à !
0
γ T x̄ = ( 0 0 ) = 0,
0

así que x̄ = (0, 0) no es solución óptima de P .

Para x̄ = (2, 3):

 1. Ax̄ ≤ b con x̄ ≥ 0. Se sigue del hecho que
à !
2
x̄ = ≥ 0,
3
à !à ! à ! à !
1 1 2 5 5
Ax̄ = = ≤ = b.
−1 2 3 4 4

2. c − y T A + γ T = 0 con y, γ ≥ 0. Tomamos los mismos valores de y y de γ que

obtuvimos para la solución (0, 0), pues tenemos el mismo sistema sin que x̄ intervenga.
3. y T (−Ax̄ + b) = 0 y γ T x̄ = 0. Tenemos que
"Ã !Ã ! Ã !#
T 4 1 −1 −1 2 5
y (−Ax̄ + b) = ( 3 3 ) +
1 −2 3 4
"Ã ! Ã !# Ã !
4 1 −5 5 4 1 0
=( 3 3 ) + =( 3 3 ) = 0,
−4 4 0
à !
T 2
γ x̄ = ( 0 0 ) = 0,
3

y por ende, x̄ = (2, 3) sí es solución óptima de P .

Ejemplo 7.10 En el problema

mı́n z = −x1 − 3x2 ,


 s.a.



P x1 − 2x2 ≥ −4,


 −x1 − x2 ≥ −4,
x1 , x2 ≥ 0,


verificar las condiciones de optimalidad de Kuhn-Tucker para x̄ = (0, 0) y x̄ = ( 43 , 38 ).

Para (0, 0):

1. Ax̄ ≤ b con x̄ ≥ 0. En este caso x̄ satisface la factibilidad de P si Ax̄ ≥ b con x̄ ≥ 0,

y es fácil ver que sí se satisface pues
à !
0
x̄ = ≥ 0,
0
à !à ! à ! à !
1 −2 0 0 −4
Ax̄ = = ≥ =b
−1 −1 0 0 −4
 2. c − y T A + γ T = 0 con y, γ ≥ 0. Se buscan y = (y1 , y2 ) y γ = (γ1 , γ2 ) ≥ 0 tales que
c − yA + γ = 0, es decir,
à !
1 −2
( −1 −3 ) − ( y1 y2 ) + ( γ1 γ2 ) = ( 0 0 ),
−1 −1
o bien
( −1 −3 ) − ( y1 − y2 −2y1 − y2 ) + ( γ1 γ2 ) = ( 0 0 ).
Tenemos el sistema
−y1 + y2 + γ1 = 1,
2y1 + y2 + γ2 = 3.
Nuevamente, con el método simplex podemos obtener una solución no negativa del
sistema; la tabla inicial es
y1 y2 γ1 γ 2 a1 a2
a1 −1 1 1 0 1 0 1
a2 2 1 0 1 0 1 3
−ϕ −1 −2 −1 −1 0 0 −4

Obtenemos y = ( 32 , 53 ) y γ = (0, 0), así que la segunda condición se satisface.

3. y T (−Ax̄ + b) = 0 y γ T x̄ = 0. Tenemos que
"Ã !Ã ! Ã !#
2 5 −1 2 0 −4
y T (−Ax̄ + b) = ( 3 3 ) +
1 1 0 −4
à !
2 5 −4 28
=( 3 3 ) = 3 6= 0,
−4
à !
0
γ T x̄ = ( 0 0 ) = 0,
0

y por lo tanto, x̄ = (0, 0) no es solución óptima de P .

Para ( 43 , 83 ):

1. Ax̄ ≤ b con x̄ ≥ 0. Se sigue del hecho que

à !
4
x̄ = 3 ≥ 0,
8
3
à !à ! à ! à !
4
1 −2 3 −4 −4
Ax̄ = 8 = ≥ = b.
−1 −1 3 −4 −4
 2. c − y T A + γ T = 0 con y, γ ≥ 0. Podemos utilizar los mismos valores de y y de γ
obtenidos para x̄ = (0, 0), pues tenemos el mismo sistema y x̄ no interviene.
3. y T (−Ax̄ + b) = 0 y γ T x̄ = 0. Tenemos que
"Ã !Ã ! Ã !#
4
T 2 5 −1 2 3 −4
y (−Ax̄ + b) = ( 3 3 ) 8 +
1 1 3 −4
"Ã ! Ã !# Ã !
2 5 4 −4 2 5 0
=( 3 3 ) + =( 3 3 ) = 0,
4 −4 0
à !
4
T 3
γ x̄ = ( 0 0 ) 8 = 0,
3

de modo que x̄ = ( 43 , 83 ) sí es solución óptima de P .

Ejercicios del capítulo 7

1. Plantea el problema dual de:

 mı́n z = 4x1 +7x2

 s.a.
+7x2 ≤ 3




 x1
3x1 ≥4



 x1 +x2 = 7
x1 ≥0






x2 ≤0

2. Plantea el problema dual de (P)


 mı́n z = 2x1 −x2 +x3

 s.a.
≥5




 x1 +x2 +x3
x1 −2x2 −x3 ≤ −2

(P)


 x1 −x3 =3
x1 , x3 ≥0






x2 s.r.s

3. Escribir el dual de (P).


 máx

s.a.
z= cx
(P) Ax = b

α≤x≤β


4. Plantea el dual de (P)

 máx z = c I xI +cK xK +cL xL

s.a.


AIJ xI +AK +AL

J xK J xL ≤ bJ



(P) AIM xI K
+AM xK L
+AM xL ≥ bM
AIN xI +AK +AL

N xK N xL = bN




xI ≥ 0 xK ≤ 0 xL s.r.s.


con I + K + L = {1, ..., n}, J + M + N = {1, ..., m}.

5. Resolver por holguras complementarias.


máx z = 2x1 +3x2
 s.a.



(P) 3x1 ≤2


 2x1 +3x2 ≤8
x1 , x2 ≥0


6. Demostrar que x1 = 1, x2 = 2, x3 = 0, x4 = 4, x5 = 0 es solución óptima de (P).


 máx z = x1 −10x3 +4x4 +5x5

 s.a.
−4x4 +5x5 ≤ 0




 x1 +2x2 +3x3
−2x3 +x4 +3x5 ≤ 4

(P)


 3x1 +4x3 +x5 ≤ 3
x2 −x3 +2x5 ≤ 13






xi ≥0

7. Verificar las condiciones de optimalidad de Kuhn - Tucker.

−x1 −3x2

mı́n w =
 s.a.



(P) −x1 +2x2 ≤ 4


 x1 +x2 ≤ 4
x1 , x2 ≥ 0

³ ´
4 8
para (0, 0) y 3, 3 .

8. Considera el siguiente problema lineal:

mı́n w = y1 −5y2 +6y3

s.a.



2y1 +4y3 ≥ 50



(P) y1 +2y2 ≥ 30

y1 , y 2 s.r.s.




y3 ≥0


Demostrar que la solución a este problema es no acotada mostrando que la solución a su

problema dual correspondiente es no factible.

9. Considerar el problema lineal

 
mı́n z = x1 +x2 +x3 +x4 +x5
 s.a.



(P) 2x1 +x2 −x3 +x4 −x5 = 2


 −x1 +x2 +3x3 −2x4 +x5 = 2
xi ≥ 0


que tiene como solución realizable x1 = x2 = x3 = x4 = x5 = 1. Mostrar sin hacer

cálculos que (P) tiene una solución óptima finita.

10. Plantear el dual del problema de flujo máximo. ¿Cuántas variables tiene el dual? ¿Cuántas
restricciones tiene?

11. Considera el siguiente problema lineal

máx z = x1 +x2

s.a.



2x1 +x2 ≤8



(P) x1 +2x2 ≤7

x2 ≤3




x1 , x2 ≥0


Verifica que y1 = y2 = 31 , y3 = 0 es una solución realizable del problema dual de (P) ¿Es
solución óptima?

12. Por holguras complementarias verifica que (4, 0, 0, 1, 2) es una solución factible de (P) ¿Es
solución óptima?


 mı́n z = −x1 +2x2
x1 −x2 +x3 =4




x1 +2x2 −x4 =3
x1 +x2 −x5 =2





xi ≥ 0 i = 1, 5

Capítulo 8

Algoritmo dual simplex

Nótese que dado un problema lineal, los cj − zj son completamente independientes del vector
de requerimientos b. Así, el conjunto de soluciones básicas de Ax = b con c j − zj ≤ 0 para
todo j depende sólo de aj y cj pero no de b. En general, no toda solución básica con todos los
cj − zj ≤ 0 será factible. Sin embargo, cualquier solución básica factible con todos c j − zj ≤ 0
será una solución óptima.
La observación anterior presenta una interesante posibilidad, si podemos empezar con alguna
solución básica no factible de un problema lineal que tenga todos sus c j −zj ≤ 0 y movernos de esta
solución básica a otra cambiando sólo un vector de tal manera de mantener todos los c j − zj ≤ 0,
entonces, suponiendo que no se repiten bases, se obtendrá una solución óptima en un número finito
de pasos. Esto es precisamente lo que el algoritmo dual simplex hace.

8.1. Justificación del algoritmo dual simplex

Consideremos el problema lineal

 máx z = cx,

P Ax ≤ b,
x ≥ 0.



cuya forma estándar es 

 máx z = cx,

P Ax + u = b,
x, u ≥ 0.



Si c ≤ 0, el problema lineal P se llama dual realizable y una solución del mismo que satisface
cj − zj ≤ 0 para [alguna] j ∈ J se llamará dual realizable. En efecto, el dual de P se escribe

 mı́n w = yb

D yA ≥ c
y ≥0



126
o bien 
 mı́n w = yb

D v − yA = −c
y, v ≥ 0



problema que está en forma explícita con respecto a una base realizable (−c ≥ 0).
Supongamos que conocemos una solución básica de P que satisface el criterio de optimalidad
pero que existen unas variables xi tales que xi < 0 (no realizable). El método dual simplex hace
progresivamente realizable un problema lineal dual realizable, es decir, se trata de efectuar una
serie de operaciones de pivoteo al final de las cuales (si es posible) b será ≥ 0, mientras que c se
conservará siempre ≤ 0.
Está claro que si b ≥ 0 y P es dual realizable, la solución x = 0, y = b es óptima.
Para efectuar un paso del algoritmo dual simplex escogeremos un índice j tal que b j < 0 (por
ejemplo, tomaremos bp = mı́n{bj : bj < 0}) y efectuaremos una operación de pivoteo sobre
un elemento ypl de tal manera que después del pivoteo el problema lineal obtenido sea aún dual
realizable, es decir, que (cJ − zJ ) el vector de costos relativo a la nueva base sea ≤ 0.
La columna pivote se determina mediante:
( )
cl − z l cj − z j
= mı́n : ypj <0 (8.1)
ypl ypj

En efecto, nótese que los nuevos elementos después del pivoteo están dados por

ypj l
(cj − zj )0 = (cj − zj ) − (c − zl )
ypl

ypj l
Caso 1. Si ypj ≥ 0, puesto que (cl − zl ) ≤ 0 y ypl < 0, entonces (c − zl ) ≥ 0, y por lo tanto
ypl
(cj − zj )0 ≤ (cj − zj ). Como la solución anterior era dual factible (cj − zj ) ≤ 0, por lo tanto
(cj − zj )0 ≤ 0. Lo que significa que la nueva solución sigue siendo dual realizable (factible),
no hay problema en seleccionar el cociente min o max.

ypj l
Caso 2. Si ypj < 0, puesto que (cl − zl ) ≤ 0 y ypl < 0, entonces (c − zl ) ≤ 0 y por lo tanto aqu
ypl
cl − z l
hay problema, no podemos asegurar que (cj − zj )0 ≤ 0, a menos que se elija como
ypl
( )
cl − z l cj − z j
indicamos en (8.1). Si = mı́n entonces
ypl ypj <0 ypj

cl − z l cj − z j
≤ ∀ j,
ypl ypj
 ypj (cj − zj )
ypj l yj
j − z ) − p (cl − z ) ≤ 0 lo que significa
tal que ypj < 0 ⇒ ≤
(c − z l ) ⇒ (c j l
ypj ypl ypl
que la nueva solución sigue siendo dual factible.

8.2. Algoritmo dual simplex

1. Se considera una solución básica de P que sea dual realizable.

2. Calcular x̄l = mı́n{x̄j }. Si el mínimo es ≥ 0 ya obtuvimos la solución óptima.

j∈I

3. Si los elementos del renglón correspondiente a la variable x l son ≥ 0 entonces existe una clase
de soluciones del dual tal que w → −∞. Si no, calcular
( )
ck − z k cj − z j
= mı́n
ylk ylj <0 ylj

(si P es max, pero si P es min elegimos el max).

4. Considerar el elemento ylk como elemento pivote y se obtiene una nueva base con x k en lugar
de xl (que sale de la base). Ir a 2.

Ejemplo 8.1 Consideremos el problema



 máx z = x1 + 3x2 ,
x1 + x2 ≤ 5,


P

 −x1 + x2 ≤ 2,


x1 , x2 ≥ 0.

Definamos I = {2, 4} y J = {1, 3}. Tenemos que

¯ ¯
¯ 1 0 ¯
det(AI ) = ¯ ¯ = 1,
¯ ¯
¯ 1 1 ¯

y por tanto I es base. Además,

à !
1 0
(AI )−1 = .
−1 1
Analicemos los cJ − zJ :
à !à !
1
³ ´ 1 0 1
c − z1 = 1 − 3 0
−1 1 −1
à !
³ ´ 1
= 1− 3 0 = 1 − 3 = −2 < 0,
−1
à !à !
3
³ ´ 1 0 1
c − z3 = 0 − 3 0
−1 1 0
à !
³ ´ 1
= −3 0 = −3 < 0
0
à !à ! à !
1 0 5 5
Las variables básicas: x̄I = (AI )−1 b = = . Tenemos, pues, una
−1 1 2 −3
solución dual realizable:
x2 1 1 1 0 5
x4 -2 0 −1 1 −3 ← sale
z = 15
−z −2 0 −3 0 −15
↑
entra
1 1 7
x2 0 1 2 2 2
1
x1 1 0 2 − 12 3
2
z = 12
−z 0 0 −2 −1 −12
3 7
Por lo tanto, el valor óptimo de la función es, zmáx = 12 con x1 = 2 y x2 = 2 como solución
óptima.

Ejemplo 8.2 Resolver el problema



 mı́n z = 2x1 + x2 ,
3x1 + x2 ≥ 3,




P 4x1 + 3x2 ≥ 6,
x1 + 2x2 ≥ 3,





x1 , x2 ≥ 0.


Se reescribe en forma estándar como



 mı́n z = 2x1 + x2 ,
3x1 + x2 − x3 = 3,




4x1 + 3x2 − x4 = 6,
x1 + 2x2 − x5 = 3,





xi ≥ 0.

Si multiplicamos por −1 las restricciones, observamos que podemos resolverlo por dual simplex:

x3 −3 −1 1 0 0 −3
x4 −4 -3 0 1 0 −6 ← sale
x5 −1 −2 0 0 1 −3
−z 2 1 0 0 0 0
↑
entra

5
x3 − 3 0 1 − 13 0 −1 ← sale
4
x2 3 1 0 − 13 0 2
5
x5 3 0 0 − 23 1 1
2 1
−z 3 0 0 3 0 −2
↑
entra

x1 1 0 − 35 1
5 0 3
5
4
x2 0 1 5 − 35 0 6
5
x5 0 0 1 −1 1 0
2 1
−z 0 0 5 5 0 − 12
5
12 3 6
Por tanto, zmı́n = 5 con x1 = 5 y x2 = 5 como solución óptima.

Observación 8.1 La ventaja del algoritmo dual simplex sobre el método de 2 fases es que no se
requieren variables artificiales, y en general, se efectúan muchas menos iteraciones. La desventaja
es que es necesario tener la factibilidad dual.

Ejercicios del capítulo 8

1. Resuelve por el método dual simplex.

 mı́n z = 2x1 +3x2

 s.a.
≤ 60




 4x1 +6x2
x1 +4x2 ≥5

(P)


 x1 −x2 ≥0
x1 ≥5






x2 ≥0

2. Resuelve por el método dual simplex. Verlo gráficamente.

 
mı́n z = x1 +x2
 s.a.



(P) x1 −x2 ≥ 1


 2x1 −x2 ≥ 6
x1 , x2 ≥ 0


3. Resuelve el ejercicio anterior utilizando dos fases y compara el número de iteraciones en

ambos casos.

4. ¿I = {2, 4} es base dual realizable? En caso afirmativo resuelve utilizando dual simplex.
Plantearlo graficamente.
−3x2

máx z = x1
 s.a.



x1 −x2 ≤ −5


 x1 +x2 ≤ 2
x1 , x2 ≥ 0


5. Resuelve el problema dual del ejercicio anterior.

6. Resuelve con dual simplex:


mı́n z = x1 +x2
 s.a.


1

2 x1 +x2 ≥ 1


 2x1 +x2 ≥ 2
x1 , x2 ≥ 0


7. Obtén una solución óptima de (P).


mı́n z = x3 +x4 +x5
 s.a.



(P) x1 −x3 +x4 −x5 = −2


 x2 −x3 −x4 +x5 = 1
xi ≥ 0


8. Aplica el método dual simplex a (P) con I = {2, 4} como base dual realizable y verifica
graficamente.

máx z = x1 +3x2
 s.a.



(P) x1 +x2 ≤ 5


 −x1 +x2 ≤ 2
x1 , x2 ≥ 0


9. Resuelve utilizando el algoritmo dual simplex y método de dos fases.



 mı́n z = x1 +x2
+x2 ≥ 4

 2x1
(a)

 x1 +7x2 ≥ 7


x1 , x2 ≥ 0
10. Resuelve los ejercicios 5., 10. y 11. del capítulo I con el método dual simplex.

11. Demuestra el siguiente teorema: El proceso operatorio del método dual simplex es exacta-
mente el que obtenemos aplicando el algoritmo simplex al problema dual (D).
Capítulo 9

Análisis de sensibilidad

En este capítulo, se analizarán algunos métodos para actualizar la solución óptima bajo dife-
rentes variaciones en el problema original.
Consideremos el problema lineal

 mı́n z = cx,

Ax = b,
x ≥ 0.



Pueden ocurrir las siguientes variaciones en un problema de programación lineal:

1. Cambios en el vector de costos c.

2. Cambios en el vector de términos independientes b.

3. Cambios en la matriz de restricciones A.

4. Adición de una nueva variable.

5. Adición de una nueva restricción.

9.1. Cambios en el vector de costos

Dada una solución básica factible óptima, supóngase que el coeficiente de costo de una (o más)
de las variables se cambia de ck a ck0 . El efecto de este cambio sobre la tabla óptima ocurrirá en
el vector de coeficientes de costo reducido, y por consiguiente puede perderse la factibilidad dual.
Consideraremos los dos casos posibles:

133
9.1.1. xk es no básica
En este caso cI no es afectado y en consecuencia zj = cI (AI )−1 Aj no cambia para ningún j,
por lo tanto ck − zk se reemplaza por ck0 − zk . Nótese que ck0 − zk ≥ 0, pues se tenía una solución
óptima. Si ck0 − zk es negativa entonces xk debe entrar a la base y el algoritmo simplex se continúa
como es usual. En caso contrario la solución anterior sigue siendo óptima con respecto al nuevo
problema.

9.1.2. xk es básica
En este caso ck se reemplaza por c0k . Sea zj0 el nuevo valor de zj entonces
0
cj − zj0 = cj − cI (AI )−1 Aj

para todo j. Por supuesto también se obtiene el nuevo valor de

0
z0 = cI (AI )−1 b → z00 = cI (AI )−1 b.

Ejemplo 9.1 Consideremos el problema



 mı́n w = −2x1 + x2 − x3
x3 ≤ 6

 x1 + x 2 +

 −x1 + 2x2 ≤4


x1 , x2 , x3 ≥ 0

cuya tabla óptima es

x1 1 1 1 1 0 6
x5 0 3 1 1 1 10
−w 0 3 1 2 0 12
Supongamos que c2 = 1 se reemplaza por −3. Puesto que x2 es no básica entonces sólo calculamos
à !à !
20
³ ´ 1 0 1
c − z2 = −3 − −2 0
1 1 2
à !
³ ´ 1
= −3 − −2 0 = −3 + 2 = −1.
2

Todos los demás cj − zj no son afectados, por lo tanto x2 entra a la base.

x1 1 1 1 1 0 6
x5 0 3 1 1 1 10
−w 0 −1 1 2 0 12
↑
entra
Se pivotea normalmente hasta obtener el óptimo.
Supóngase ahora que c1 = −2 se reemplaza por c01 = 0. Puesto que x1 es básica entonces el
nuevo vector de costos se obtiene:

à !à !
10
³ ´ 1 0 1
c − z1 = 0 − 0 0 =0
1 1 −1
à !à !
2
³ ´ 1 0 1
c − z20 =1− 0 0 =1
1 1 1
à !à !
3
³ ´ 1 0 1
c − z30 = −1 − 0 0 = −1
1 1 0
à !à !
4
³ ´ 1 0 1
c − z40 =0− 0 0 =0
1 1 0
à !à !
³ ´ 1 0 0
c5 − z50 = 0 − 0 0 =0
1 1 1
z00 = 0

x1 1 1 1 1 0 6
x5 0 3 1 1 1 10
−w 0 1 −1 0 0 0
↑
entra

Se pivotea normalmente hasta obtener el óptimo.

Ejemplo 9.2 En el ejemplo anterior, supóngase que el precio del producto químico B se reduce de
3 a 1. El nuevo problema es



 máx z = 5x1 + x2 ,
5x2 ≤ 15,

 3x1 +

 5x 1 + 2x2 ≤ 10,


x1 , x2 ≥ 0.
Como x2 es básica, calculamos
à !à ! à !
5 3
1
³ ´ − 19 3 ³ ´ 3
c − z10 = 5− 1 5 19
2 5 =5− 5
− 19 22
19 =5−5=0
− 19 19 5 5
à !à ! à !
5 3
20
³ ´
19 − 19 5 ³
5 22
´ 5
c − z2 = 1 − 1 5 2 5 =1− − 19 19 =1−1=0
− 19 19 2 2
à !à ! à !
5 3
3
³ ´ − 19 1 ³ ´ 1
c − z30 = 0− 1 5 19
2 5 =0− 5
− 19 22
19 = 5
19
− 19 19 0 0
à !à ! à !
5 3
4
³ ´ − 19 0 ³ ´ 0
c − z40 = 0− 1 5 19
2 5 =0− 5
− 19 22
19 = − 22
19
− 19 19 1 1
à !à ! à !
5 3
³ ´ − 19 15 ³ ´ 15
z00 I
= c (A )I −1
b= 1 5 19
2 5 = 5
− 19 22
19 = 145
19
− 19 19 10 10

3 5 45
x2 0 1 19 − 19 19 ← sale
2 5 20
x1 1 0 − 19 19 19
−z 0 0 19 − 22
5
19 − 145
19
↑
entra
19 −3
x3 0 5 1 5 9
2 1
x1 1 5 0 5 2
−z 0 1 0 1 −10

óptimo.

9.2. Cambio en el vector de términos independientes

Si el vector b se reemplaza por b0 entonces (AI )−1 b será reemplazado por (AI )−1 b0 . Si (AI )−1 b0 ≥
0 entonces dado que el vector de costos no se ve alterado, la misma base es una base óptima para
el nuevo problema; si alguna(s) componente(s) de (A I )−1 b0 son negativas aplicamos dual simplex
para obtener una nueva solución óptima factible.

Ejemplo 9.3 Supongamos en el problema anterior que

à !
3
b0 = .
4

Nótese que à !
1 0
(AI )−1 = ,
1 1
y por lo tanto à !à ! à !
1 0 3 3
(AI )−1 b0 = = ≥ 0.
1 1 4 7
En consecuencia la nueva solución óptima es x1 = 3, x2 = 7, x3 = x4 = x5 = 0 con
à !à ! à !
³ ´ 1 0 3 ³ ´ 3
z00 I I −1 0
= c (A ) b = −2 0 = −2 0 = −6
1 1 4 7

Ahora supóngase que à !

0 −3
b = .
4
Entonces à !à ! à !
I −1 0 1 0 −3 −3
(A ) b = = ,
1 1 4 1
de modo que resulta la tabla
x1 1 1 1 1 0 −3
x5 0 3 1 1 1 1
−w 0 3 1 2 0 −6
Aplicamos dual simplex y concluímos que con esta modificación w → ∞.

Ejemplo 9.4 Supongamos que el problema original consiste en producir un volumen de un pro-
ducto químico A que se vende a $5 por litro y otro volumen de un producto químico B que se
vende a $3 por litro. Se tiene una restricción de personal, máximo 15 personas y otra de una costo
de producción, máximo $10 por hora. Se tiene la tabla:
Producto químico
A B
Personal 3 5
Costo de
5 2
producción
Sean x1 y x2 los números de litros de los productos A y B a producir por hora, respectivamente.
Entonces debemos resolver el problema


 máx z = 5x1 + 3x2
3x1 + 5x2 ≤ 15





5x1 + 2x2 ≤ 10

x1 , x2 ≥ 0

La tabla inicial es
x3 3 5 1 0 15
x4 5 2 0 1 10
−z 5 3 0 0 0
La tabla óptima es
5 3 45
x2 0 1 19 − 19 19
2 5 20
x1 1 0 − 19 19 19
5 16 235
−z 0 0 − 19 − 19 − 19
de modo que à !
5 3
I −1 19 − 19
(A ) = 2 5 .
− 19 19

Supongamos que por una depresión económica el número de empleados debe reducirse a 5 y el
costo máximo de producción a $5 por hora, el nuevo vector b es
à !
0 5
b =
5

El nuevo problema será 


 máx z = 5x1 + 3x2 ,
3x1 + 5x2 ≤ 5,





5x1 + 2x2 ≤ 5,

x1 , x2 ≥ 0.
No es necesario aplicar el algoritmo simplex desde el principio nuevamente, aplicamos análisis de
sensibilidad y obtenemos:
à !à ! à !
5 3 10
I −1 0 19 − 19 5 19
x̄I = (A ) b = 2 5 = 15 ≥ 0.
− 19 19 5 19

Sigue siendo factible y

à !à ! à !
5 3 10
I I −1 0
³ ´
19 − 19 5 ³ ´
19 105
zmáx = c (A ) b = 3 5 2 5 = 3 5 15 = 19 = 5.53
− 19 19 5 19

El valor de zmáx se ha reducido.

Volviendo al ejemplo original: Supongamos que el personal se reduce a 10 personas, pero el
costo máximo por hora de producción aumenta a $20. El nuevo problema será:


 máx z = 5x1 + 3x2 ,
5x2 ≤ 10,

 3x1 +

 5x 1 + 2x2 ≤ 20,


x1 , x2 ≥ 0.

Con análisis de sensibilidad:

à !à ! à !
5 3 10
− 19 10 − 19
x̄I = (AI )−1 b0 = 19
2 5 = 80
− 19 19 20 19
utilizando la tabla óptima, aplicamos dual simplex:
3
x2 0 1 5 − 19 − 10
19 19
2 5 80
x1 1 0 − 19 19 19
5 16 370
−z 0 0 − 19 − 19 − 19
x4 0 − 19
3
5
−3 1 10
3
x1 1 − 35 1
3 0
10
3
−z 0 − 16
3
80
− 57 0 − 50
3
50 10
Por lo tanto, zmáx = 3 con x1 = 3 y x2 = 0.

9.3. Cambio en la matriz de restricciones

Hay dos casos posibles, cambios que incluyen columnas no-básicas y cambios que incluyen
columnas básicas.

9.3.1. Cambios en vectores de actividades para columnas no-básicas

Supóngase que la columna no-básica Aj se modifica porAj0 . Entonces la nueva columna actua-
lizada es (AI )−1 Aj0 y cj − zj0 = cj − cI (AI )−1 Aj0 .
Si cj − zj0 ≥ 0, la solución anterior es óptima, en caso contrario se continua aplicando el
algoritmo simplex después de actualizar la columna j de la tabla, introduciendo la variable x j a la
base.

Ejemplo 9.5 Consideremos el problema lineal



 máx z = 3x1 + 5x2 ,
≤ 4,

 x1



3x 1 + 2x2 ≤ 18,

x1 , x2 ≥ 0,
cuya tabla óptima es
x3 1 0 1 0 4
3 1
x2 2 1 0 2 9
−z − 29 0 0 − 52 −45
à !
2
1. Supongamos que A10 = . Calculamos
2
à !à !
1
³ ´ 1 0 2
c − z10 = 3− 0 5
0 21 2
à !
³
5
´ 2
= 3− 0 2 = 3 − 5 = −2 < 0
2
 Entonces la solución sigue siendo óptima, la nueva tabla óptima es:

x3 2 0 1 0 4
1
x2 1 1 0 2 9
−z −2 0 0 − 25 −45

à !
10
2. Supongamos que A10 = . Calculamos
1
à !à !
1
³ ´ 1 0 10
c − z10 = 3− 0 5
0 21 1
à !
³
5
´ 10 5 1
= 3− 0 2 =3− = >0
1 2 2

Entonces hay que aplicar simplex:

x3 10 0 1 0 4 ← sale
x2 12 1 0 1
2 9
1 5
−z 2 0 0 − 2 −45
↑
entra
1 2
x1 1 0 10 0 5
1 1 44
x2 0 1 − 20 2 5
1
−z 0 0 − 20 − 52 − 226
5

9.3.2. Cambios en vectores de actividades para columnas básicas

Si la columna modificada es de base, la nueva matriz AI0 obtenida sustituyendo la nueva co-
lumna en AI puede no ser ya una base.
Si AI0 es todavía una base, la solución de base correspondiente puede ya no ser factible; si x̄ I0
es una solución factible puede ya no ser óptima.

1. AI0 es base y x̄I0 ≥ 0 y cumple las condiciones de optimalidad cJ − zJ ≤ 0 (≥ 0), x̄I0 es

una solución factible óptima y sólo se pivotea para hacer la columna básica unitaria.

2. AI0 es base y x̄I0 es una solución factible no óptima, aplicamos el algoritmo simplex trans-
formando la antigua tabla óptima con ayuda de (AI0 )−1 tomando x̄I0 como solución factible
inicial.

3. AI0 es base y x̄I0 cumple las condiciones de optimalidad pero no es factible, aplicamos el
algoritmo dual simplex, actualizando la tabla.
 Si no estamos en ninguno de los tres casos anteriores, revisando las bases utilizadas en el curso
de la optimización del problema primitivo puede que el vector A i haya entrado “tardíamente” en la
base, por ejemplo, en la p-ésima iteración. En este caso es ventajoso volver a aplicar el algoritmo
al final de la (p − 1)-ésima iteración, una vez que hayamos reemplazado la columna j de la tabla
(AI )−1 Aj por (AI )−1 Aj0 .
Calcúlese y j0 = (AI )−1 Aj0 en donde (AI )−1 es la inversa de la base actual. Si yjj0 = 0 el
conjunto actual de vectores básicos ya no forma una base (por un resultado de álgebra lineal que
dice: “Una condición necesaria y suficiente para que A I sea no singular es que y j0 = (AI )−1 Aj0
o de manera equivalente Aj0 = ys As se tenga yjj0 6= 0), en este caso se añade una variable
P j
s∈I
artificial que tome el lugar de xj en la base y se recurre al método de dos fases.

Ejemplo 9.6 Sea 


 mı́n w = −2x1 + x2 − x3 ,
x1 + x2 + x3 ≤ 6,





−x 1 + 2x2 ≤ 4,

xi ≥ 0,
cuya tabla óptima es
x1 1 1 1 1 0 6
x5 0 3 1 1 1 10
−w 0 3 1 2 0 12
à !
2
1. Supongamos que A1 se modifica por A10 = . Entonces
−1
à !à ! à !
10 1 0 2 2
y = = 6= 0,
1 1 −1 1
Sigue siendo básica.
à !à !
³ ´ 1 0 2
(c1 − z1 )0 = −2 − −2 0
1 1 −1
à !
³ ´ 2
= −2 − −2 0 = −2 + 4 = 2
−1

x1 2 1 1 1 0 6
x5 1 3 1 1 1 10
−w 2 3 1 2 0 12
pivoteando para que la columna sea unitaria (básica):
1 1 1
x1 1 2 2 2 0 3
5 1 1
x5 0 2 2 2 1 7
−w 0 2 0 1 0 6
 óptimo.
à !
4
2. Supongamos que A1 se modifica por A10 = . Entonces
5
à !à ! à !
10 1 0 4 4
y = = 6= 0
1 1 5 9
Sigue siendo básica.
à !à !
1 0
³ ´ 1 0 4
(c − z1 ) = −2 − −2 0
1 1 5
à !
³ ´ 4
= −2 − −2 0 = −2 − (−8) = 6
9

x1 4 1 1 1 0 6
x5 5 3 1 1 1 10
−w 6 3 1 2 0 12
pivoteando para que la columna sea unitaria:
1 1 1 3
x1 1 4 4 4 0 2 ← sale
7
x5 0 4 − 14 1
−4 1 5
2
3
−w 0 2 − 12 1
2 0 3
↑
entra
Y tenemos una solución básica factible no óptima, por lo tanto, aplicamos simplex:
x3 4 1 1 1 0 6
x5 1 2 0 0 1 4
−w 2 2 0 1 0 6
óptimo.
à !
1
3. Supongamos que A1 se modifica por A10 = . Entonces
5
à !à ! à !
1 0 1 1
y 10 = = 6= 0.
1 1 5 6
Sigue siendo básica.
à !à !
1 0
³ ´ 1 0 1
(c − z1 ) = −2 − −2 0
1 1 5
à !
³ ´ 1
= −2 − −2 0 = −2 + 2 = 0
6
 x1 1 1 1 1 0 6
x5 6 3 1 1 1 10
−w 0 3 1 2 0 12
Pivoteando para que la columna sea unitaria:
x1 1 1 1 1 0 6
x5 0 −3 -5 −5 1 −26 ← sale
−w 0 3 1 2 0 12
↑
entra
Y tenemos una solución básica óptima no factible, por lo tanto, aplicamos dual simplex:
2 1 4
x1 1 5 0 0 5 5
3 1 26
x3 0 5 1 1 −5 5
12 1 34
−w 0 5 0 1 5 5
óptimo.
à !
0
4. Veámos el último caso: Supongamos que la columna A1 cambia a A10 = entonces
−1
à !à ! à !
10 I −1 10 1 0 0 0
y = (A ) A = =
1 1 −1 −1
à !
³ ´ 0
c1 − cI (AI )−1 A10 = −2 − −2 0 = −2
−1
Aquí el elemento en el renglón x1 de y 10 es cero y en consecuencia,  las columnas
 básicas
0
actuales ya no generan el espacio. Reemplazar la columna x 1 por  −1 , introducir la
 
−2
variable artificial x6 para reemplazar a x1 en la base y se obtiene la tabla:
x6 0 1 1 1 0 1 6
x5 −1 3 1 1 1 0 10
−w −2 3 1 2 0 0 12
ϕ 0 −1 −1 −1 0 0 −6
x3 0 1 1 1 0 1 6
x5 −1 2 0 0 1 −1 4
−w −2 2 0 1 0 −1 6
ϕ 0 0 0 0 0 1 0
x3 0 1 1 1 0 6
x5 −1 2 0 0 1 4
−w −2 2 0 1 0 6
↑
 Concluímos que w → −∞. En efecto,


 mı́n w = −2x1 + x2 − x3 ,
x1 + x2 + x3 ≤ 6,



 −x1 + 2x2 ≤ 4,


xi ≥ 0.

h1 0 1 1 1 0 6 ← sale
h2 −1 2 0 0 1 4
−w −2 1 −1 0 0 0
↑
entra
x3 0 1 1 1 0 6
h2 −1 2 0 0 1 4
−w −2 2 0 1 0 6
↑

Concluímos que, w → −∞.

9.4. Adición de una nueva variable

Supóngase que una nueva varible xn+1 con costo cn+1 y columna de consumo An+1 es con-
siderada para posible producción. Sin resolver totalmente el nuevo problema puede determinarse
fácilmente si conviene producir xn+1 .
Primero se calcula cn+1 − zn+1 ; Si cn+1 − zn+1 ≥ 0 (para el caso de minimizar) entonces
x∗n+1 = 0 y la solución actual es óptima.
Si cn+1 − zn+1 < 0 entonces se introduce en la base y se continúa el algoritmo simplex para
encontrar la nueva solución óptima.

Ejemplo 9.7 Consideremos el problema lineal



 mı́n w = −2x1 + x2 − x3
x1 + x 2 + x 3 ≤ 6





−x 1 + 2x2 ≤4

xi ≥ 0

cuya forma estándar es



 mı́n w = −2x1 + x2 − x3 ,

 x1 + x 2 + x 3 + x 4 = 6,

 −x 1 + 2x 2 + x 5 = 4,


xi ≥ 0.
La tabla óptima es
x1 1 1 1 1 0 6
x5 0 3 1 1 1 10
−w 0 3 1 2 0 12
à !
−1
Sea x6 ≥ 0 con c6 =1y A6 = . Calculemos
2
à !à !
6
³ ´ 1 0 −1
c − z6 = 1 − −2 0
1 1 2
à !
³ ´ −1
= 1− −2 0 = 1 − 2 = −1
2

Entonces calculamos
à !à ! à !
1 0 −1 −1
y 6 = (AI )−1 A6 = =
1 1 2 1

x1 1 1 1 1 0 −1 6
x5 0 3 1 1 1 1 10
−w 0 3 1 2 0 −1 12
y se pivotea hasta obtener el óptimo.

x1 1 4 2 2 1 0 16
x5 0 3 1 1 1 1 10
−w 0 6 2 3 1 0 22

óptimo.

9.5. Adición de una nueva restricción

Supóngase que se añade una nueva restricción al problema.

Si la solución óptima del problema original satisface la nueva restricción, entonces ésta so-
lución sigue siendo óptima para el nuevo problema.

Si la solución óptima del problema original no satisface la nueva restricción, es decir, la

nueva restricción elimina al punto óptimo, entonces puede usarse dual simplex para encontrar
la nueva solución óptima.
Ejemplo 9.8 Considérese el ejemplo anterior con la restricción adicional

−x1 + 2x3 ≥ 2.
³ ´
El punto óptimo 6 0 0 no satisface la restricción, entonces

x1 − 2x3 + x6 = −2.
x1 1 1 1 1 1 0 6
x5 0 3 1 1 1 1 10
x6 1 0 −2 0 0 1 −2
−w 0 3 1 2 0 0 12
pivoteando para que la primera columna sea unitaria.

x1 1 1 1 1 1 0 6
x5 0 3 1 1 1 1 10
x6 0 −1 -3 −1 0 1 −8 ← sale
−w 0 3 1 2 0 0 12
↑
entra

se pivotea hasta obtener la solución óptima.

2 2 1 10
x1 1 3 0 3 0 3 3
8 2 1 22
x5 0 3 0 3 1 3 3
1 1 1 8
x3 0 3 1 3 0 −3 3
8 5 1 28
−w 0 3 0 3 0 3 3

óptimo.

Ejemplo 9.9 Consideremos 

 mı́n w = 5y1 + 2y2 ,

y1 − y2 ≥ 1,
y1 , y2 ≥ 0,



cuya tabla óptima es

y1 1 −1 −1 1
−w 0 7 5 −5
³ ´
y supongamos que se añade la resticción y1 − y2 ≥ 3. El punto óptimo 1 0 no satisface la
restricción. 

 mı́n w = 5y1 + 2y2 ,
y1 − y 2 − y 3

 = 1,

 −y 1 − y 2 + y 4 = −3,


yi ≥ 0.
 y1 1 −1 −1 0 1
y4 −1 −1 0 1 −3
−w 0 7 5 0 −5
y1 1 −1 −1 0 1
y4 0 -2 −1 1 −2
−w 0 7 5 0 −5
Aplicamos dual simplex:
y1 1 0 − 12 − 12 2
1
y2 0 1 2 − 12 1
3 7
−w 0 0 2 2 −12
óptimo.
Ahora, supongamos que al problema original se añade la restricción: y 1 − y2 ≥ 0. El punto
óptimo (1, 0) satisface la restricción. Por lo tanto, la solución sigue siendo óptima.

Observación 9.1 No puede suceder que al agregar una nueva restricción, la región de soluciones
factibles se agrande.

Ejercicios del capítulo 9

1. Considera el siguiente problema de programación lineal y su tabla óptima final que se mues-
tra a continuación.
−x3

 máx z = 2x1 +x2

 s.a.
x1 +2x2 +x3 ≤ 8

(P)


 −x1 +x2 −2x3 ≤ 4
xi ≥0


tabla final:
x1 1 2 1 1 0 8
x5 0 3 −1 1 1 12
−z 0 −3 −3 −2 0 −16

(a) Encontrar la nueva solución óptima si el coeficiente de x 2 en la función objetivo se

cambia de 1 a 5.
(b) Supóngase que el coeficiente de x3 en la segunda restricción se cambia de 2 a 1, en-
contrar la nueva solución óptima.
(c) Supóngase que se añade al problema la siguiente restricción x 2 + x3 ≥ 2. Encontrar la
nueva solución óptima.
(d) Si se tuviera que escoger entre incrementar el lado derecho de la primera restricción o
de la segunda ¿cuál escogerías? ¿por qué? ¿cuál es el efecto de este incremento sobre
el valor óptimo de la función objetivo?
 (e) Supóngase que se propone una nueva actividad x 6 con ganancia unitaria 4 y vector de
³ ´t
consumo A6 = 1 2 . Encontrar la nueva solución óptima.

2. Considérese la siguiente tabla óptima de un problema de maximización en el que las restric-

ciones son del tipo ≤ . Supongamos que se añade al problema la restricción x 1 − x2 + 2x3 ≤
10 ¿sigue siendo óptima la solución? En caso negativo encontrar la nueva solución óptima.
1 1
x1 1 0 0 −1 0 2 5 −1 3
1
x2 0 1 0 2 1 −1 0 2 1
3
x3 0 0 1 −1 −2 5 − 10 2 7
1
−z 0 0 0 −2 0 −2 − 10 −2 −17
3. Analizar geométricamente el caso de la modificación al vector de términos independientes.

4. Considera el siguiente problema de programación lineal.

mı́n z = −x1 +2x2

s.a.



x1 −x2 ≤4



(P) x1 −2x2 ≤3

x1 +x2 ≤2




x1 , x2 ≥0


Cuya tabla final es:

x3 0 −2 1 0 −1 2
x4 0 −3 0 1 −1 1
x1 1 1 0 0 1 2
−z 0 3 0 0 1 2
 
2
(a) Supóngase que A1 se cambia por A10 =  3  , obtén la nueva solución óptima.
 
1
 
2
(b) Supóngase que A se cambia por A =  1  , obtén la nueva solución óptima.
1 10  
3

5. Suponer que al siguiente problema de programación lineal



 máx z = −8x1 −4x2 −3x3
−x2 +x3 +x4 ≥ 1

 2x 1
(P)



x1 +x2 −x4 ≥ 2

xi ≥ 0
se le agrega la restricción 3x1 − 3x2 ≤ −2. Da la nueva solución óptima.