494 CAPÍTULO9 PROGRAMACIÓNLINEAL

9.3 EL MÉTODO SIMPLEX: MAXIMIZACIÓN

Para problemas de programación lineal que involucran dos variables, el método de solución gráfica
introducido en la Sección 9.2 es conveniente. Sin embargo, para problemas que involucren más de dos
variables o problemas que involucran una gran cantidad de restricciones, es mejor usar solución
métodos que son adaptables a las computadoras. Uno de esos métodos se llama el método simplex,
desarrollado por George Dantzig en 1946. Nos proporciona una forma sistemática de examinar
los vértices de la región factible para determinar el valor óptimo de la función objetivo.
Presentamos este método con un ejemplo.
Supongamos que queremos encontrar el valor máximo de zϭ 4x1ϩ 6x2,dondex1Ն 0yxd2Ն 0
sujeto a las siguientes restricciones.
Ϫx1ϩ 5x2Յ 11
Ϫx1ϩ 5x2Յ 27
2x1ϩ 5x2Յ 90
Dado que el lado izquierdo de cada desigualdad es menor o igual que el lado derecho, hay
deben existir números no negativos s,s
1 2y3quesse puede agregar al lado izquierdo de cada ecuación
acción para producir el siguiente sistema de ecuaciones lineales.

Ϫx1ϩ 5x2ϩ s1ϩ s2ϩ s3ϭ 11

Ϫx1ϩ 5x2ϩ s1ϩ s2ϩ s3ϭ 27
2x1ϩ 5x2ϩ s1ϩ s2ϩ s3ϭ 90
Los números1,s2y3se llaman variables de holgura porque aprovechan la "holgura" en
cada desigualdad.

Forma estándar de un Un problema de programación lineal está en forma estándar si busca maximizar el objeto
funciones activasϭ c1x1ϩ c2 x2ϩ . . . ϩ cn xnsujeto a las restricciones
Programación Lineal
a11x1ϩ a12x2ϩ . . . ϩ a1nxnՅ b1
Problema
a21x1ϩ a22x2ϩ . . . ϩ a2nxnՅ b2
.
.
.
am1 x1ϩ am2 x2ϩ . . . ϩ amnxnՅ bm

dónde está xyoՆ

0andbyoՆ 0. Después de agregar variables de holgura, el sistema correspondiente de
ecuaciones de restricción
a11x1ϩ a12x2ϩ . . . ϩ a1nxnϩ s1 ϭ b1
a21x1ϩ a22x2ϩ . . . ϩ a2nxn ϩ s2 ϭ b2
.
.
.
am1x1ϩ am2x2ϩ . . . ϩ amnxn ϩ smϭ bm
dónde estáyoՆ 0.
 SECCIÓN9.3 ELMÉTODOSIMPLEX:MAXIMIZACIÓN 495

R E M A R C A: Tenga en cuenta que para un problema de programación lineal en forma estándar, el objetivo

la función debe ser maximizada, no minimizada. (Los problemas de minimización se discutirán en

Secciones 9.4 y 9.5.)

Una solución básica de un problema de programación lineal en forma estándar es una solución
͑x1,x2, . . . ,xn,s12, . . . ,sm͒ de las ecuaciones de restricción en las que hay como máximo m variables
no cero––las variables que no son cero se llaman variables básicas. Una solución básica para
cuales variables son no negativas se llama solución básica factible.

El Tableau Simplex
El método simplex se lleva a cabo realizando operaciones elementales de fila en una matriz.
que llamamos el tableau simplex. Este tableau consiste en la matriz aumentada correspondiente.
respondiendo a las ecuaciones de restricción junto con los coeficientes de la función objetivo
escrito en la forma
Ϫc1x1Ϫ c2x2Ϫ . . . Ϫ cnxnϩ ͑0s͒ 1ϩ ͑0s͒ 2ϩ . . . ϩ ͑0͒ smϩ zϭ 0.

En el tableau, es habitual omitir el coeficiente de z. Por ejemplo, el tableau simplex

para el problema de programación lineal

zϭ 4x1ϩ 6x2 Función objetivo

}
Ϫx1ϩ 5x2ϩ s1ϩ s2ϩ s3ϭ 11
Ϫx1ϩ 5x2ϩ s1ϩ s2ϩ s3ϭ 27 Restricciones
2x1ϩ 5x2ϩ s1ϩ s2ϩ s3ϭ 90
es como sigue.
Básico
x1 x2 s1 s2 s3 b Variables
Ϫ1 1 1 0 0 11 s1
1 1 0 1 0 27 s2
2 5 0 0 1 90 s3

Ϫ4Ϫ6 0 0 0 0
↑
Valor z actual

Para este tableau simplex inicial, las variables básicas son1,s2, tierras3, y luego en básico
variables (que tienen un valor de cero) sonx1y2Por lo tanto, de las dos columnas que son
más a la derecha, vemos que la solución actual es
x1ϭ 0,x2ϭ 0,s1ϭ 11,s2ϭ 27, y3ϭ 90.
Esta solución es una solución básica factible y a menudo se escribe como
͑x1,x2,s1,s2,s3͒ ϭ ͑0, 0, 11, 27, 90͒.
496 CAPÍTULO9 PROGRAMACIÓNLINEAL

La entrada en la esquina inferior derecha de la tabla simplex es el valor actual de z. Nota

que las entradas de la fila inferior bajo y x1 losx2 negativos de los coeficientes xde
son 1 y
x2en la función objetivo
zϭ 4x1ϩ 6x2.
Para realizar un chequeo de optimalidad para una solución representada por un tableau simplex, miramos
en las entradas de la fila inferior del tableau. Si alguna de estas entradas es negativa (como
arriba), entonces la solución actual no es óptima.

Pivotando
Una vez que hemos configurado el tableau simplex inicial para un problema de programación lineal, el sim-
el método plex consiste en verificar la optimalidad y luego, si la solución actual no es óptima
timal, mejorando la solución actual. (Una solución mejorada es aquella que tiene un valor z mayor)
que la solución actual.) Para mejorar la solución actual, traemos una nueva variable básica
en la solución––llamamos a esta variable la variable entrante. Esto implica que uno de los
las variables básicas actuales deben salir, de lo contrario tendríamos demasiadas variables para un básico
solución––llamamos a esta variable la variable de partida. Elegimos la variable que entra y
variables de partida como sigue.
La variable de entrada corresponde a la entrada más pequeña (la más negativa) en el
fila inferior del tableau.
2. La variable de partida corresponde a la razón no negativa más pequeña de byo͞aij, en el
columna determinada por la variable entrante.
3. La entrada en la tabla simplex en la columna de la variable entrante y la que sale
la fila de la variable se llama el pivote.
Finalmente, para formar la solución mejorada, aplicamos la eliminación de Gauss-Jordan a la columna.
que contiene el pivote, como se ilustra en el siguiente ejemplo. (Este proceso se llama
pivotando.)

E J E M P L O 1 Haciendo un cambio para encontrar una solución mejorada

Utiliza el método simplex para encontrar una solución mejorada para el problema de programación lineal
representado por el siguiente tableau.
Básico
x1 x2 s1 s2 s3 b Variables

Ϫ1 1 1 0 0 11 s1
1 1 0 1 0 27 s2
2 5 0 0 1 90 s3

Ϫ4Ϫ6 0 0 0 0

La función objetivo para este problema es zϭ 4x1ϩ 6x2.

 SECCIÓN9.3 ELMÉTODOSIMPLE:MAXIMIZACIÓN 497

Nota de solución que la solución ͑xϭ1 0,xϭ 0,sϭ

actual
2 11,sϭ1 27,sϭ 90͒
2 3 corresponde a
valor az de 0. Para mejorar esta solución, determinamos quex2 es la variable de entrada,
porqueϪ6 es la entrada más pequeña en la fila inferior.
Básico
x1 x2 s1 s2 s3 b Variables

Ϫ1 1 1 0 0 11 s1
1 1 0 1 0 27 s2
2 5 0 0 1 90 s3

Ϫ4Ϫ6 0 0 0 0
↑
Entrando

Paraverporquéelegimosx2como la variable de entrada, recuerda esoϭ 4x1ϩ 6x2Por lo tanto, esto

parece que un cambio de unidad en x2produce un cambio de 6 inz, mientras que un cambio unitario en x1
produce un cambio de solo 4 pulgadas.

Para encontrar la variable de partida, localizamos elbyoque tienen elementos positivos correspondientes
en la columna de variables de entrada y formar las siguientes relaciones.

11 27 90
ϭ 11, ϭ 27 ϭ 18
1 1 5
Aquí la proporción positiva más pequeña es 11, así que elegimos1como la variable de partida.
Básico
x1 x2 s1 s2 s3 b Variables

Ϫ1 1 1 0 0 11 s1 ← Saliendo
1 1 0 1 0 27 s2
2 5 0 0 1 90 s3

Ϫ4Ϫ6 0 0 0 0
↑
Entrando

Tenga en cuenta que el pivote es la entrada en la primera fila y segunda columna. Ahora, usamos Gauss-
Eliminación de Jordan para obtener la siguiente solución mejorada.
Antes de girar Después de girar

Ϫ1 1 1 0 0 11 Ϫ1 1 1 0 0 11

΄ 1
2
Ϫ4Ϫ6
1
5
0
0
0
1
0
0
0
1
0
27
90
0
΅ ΄ 2
7
Ϫ10
0
0
0
Ϫ1
Ϫ5
6
1
0
0
0
1
0
16
35
66
΅
El nuevo tableau ahora aparece de la siguiente manera.
498 CAPÍTULO9 PROGRAMACIÓNLINEAL

Básico
x1 x2 s1 s2 s3 b Variables

Ϫ1 1 1 0 0 11 x2
2 0 Ϫ1 1 0 16 s2
7 0 Ϫ5 0 1 35 s3

Ϫ10 0 6 0 0 66

Nota que2ha reemplazado1en la columna de base y la solución mejorada

͑x1,x2,s1,s2,s3͒ ϭ ͑0, 11, 0, 16, 35͒
tiene un valor de az

zϭ 4x1ϩ 6x2ϭ 4͑0͒ ϩ 6͑11͒ ϭ 66.

En el Ejemplo 1, la solución mejorada aún no es óptima ya que la fila inferior todavía tiene un
entrada negativa. Por lo tanto, podemos aplicar otra iteración del método simplex para continuar.
demostrar nuestra solución de la siguiente manera. Elegimos1comoxla
variable de entrada. Además, el pequeño-
es una relación no negativa de 11͞ ͑ Ϫ1͒, 16͞2ϭ 8,y35͞7ϭ 5 son 5, sos3está partiendo
la variable. La eliminación de Gauss-Jordan produce lo siguiente.

Ϫ1 1 1 0 0 11 Ϫ1 1 1 0 0 11

΄ 2
7
Ϫ10
0
0
0
Ϫ1
Ϫ5
6
1
0
0
0
1
0
16
35
66
΅ ΄ 2
1
Ϫ10
0
0
0
Ϫ1
Ϫ57
6
1
0
0
0
1
7
0
16
5
66
΅
2 1
0 1 0 16

΄ ΅
7 7
3
0 0 7 1 Ϫ27 6
1
1 0 Ϫ57 0 7 5
10
0 0 Ϫ87 0 7 116

Así, el nuevo tableau simplex es el siguiente.

Básico
x1 x2 s1 s2 s3 b Variables
2 1
0 1 7 0 7 16 x2
3
0 0 7 1 Ϫ27 6 s2
1
1 0 Ϫ57 0 7 5 x1
10
0 0 Ϫ87 0 7 116

En este tableau, todavía hay una entrada negativa en la fila inferior. Así que elegimos1como el
ingresando variables y2como la variable que se va, como se muestra en el siguiente tableau.
 SECCIÓN9.3 ELMÉTODOSIMPLEX:MAXIMIZACIÓN 499

Básico
x1 x2 s1 s2 s3 b Variables
2 1
0 1 7 0 7 16 x2
3
0 0 7 1 Ϫ27 6 s2 ← Partiendo
1
1 0 Ϫ57 0 7 5 x1
10
0 0 Ϫ87 0 7 116
↑
Entrando

Al realizar una iteración más del método simplex, obtenemos el siguiente tableau.
(Intenta verificar esto.)
Básico
x1 x2 s1 s2 s3 b Variables
1
0 1 0 Ϫ23 3 12 x2
7
0 0 1 3 Ϫ23 14 s1
5
1 0 0 3 Ϫ13 15 x1
8 2
0 0 0 3 3 132 ←Valor z máximo
En este tableau, no hay elementos negativos en la fila inferior. Por lo tanto, hemos determinado que
mined la solución óptima para ser

͑x1,x2,s1,s2,s3͒ ϭ ͑15, 12, 14, 0, 0͒

con

zϭ 4x1ϩ 6x2ϭ 4͑15͒ ϩ 6͑12͒ ϭ 132.

OBSERVACIÓN: Pueden ocurrir empates al elegir variables de entrada y/o salida. Debería esto
suceder, se puede hacer cualquier elección entre las variables empatadas.

Porque el problema de programación lineal en el Ejemplo 1 involucró solo dos variables de decisión.
Figura 9.18 Mesas, podríamos haber utilizado una técnica de solución gráfica, como hicimos en el Ejemplo 2, Sección
x2 9.2. Observe en la Figura 9.18 que cada iteración en el método símplex corresponde a moverse
desde un vértice dado a un vértice adyacente con un valor z mejorado.
25

20
(5, 16) ͑0, 0͒ ͑0, 11͒ ͑5, 16͒ ͑15, 12͒
15 (15, 12) zϭ 0 zϭ 66 zϭ 116 zϭ 132
10 (0, 11)
5
(0, 0) (27, 0)
El Método Simplex
x1
5 10 15 20 25 30 Resumimos los pasos involucrados en el método simplex de la siguiente manera.
500 CAPÍTULO9 PROGRAMACIÓNLINEAL

El Método Simplex Para resolver un problema de programación lineal en forma estándar, utiliza los siguientes pasos.
1. Convierte cada desigualdad en el conjunto de restricciones a una ecuación añadiendo holgura.
(Forma Estándar) variables.
2. Crea el tableau simplex inicial.
3. Localiza la entrada más negativa en la fila inferior. La columna para esta entrada se llama
la columna de entrada. (Si ocurren empates, cualquiera de las entradas empatadas puede ser utilizada para determinar
la columna de entrada.)
4. Forma las proporciones de las entradas en la "columna-b" con sus correspondientes positivas.
entradas en la columna de entrada. La fila de salida corresponde al menor no-
relación negativayo͞ayoj Si todas las entradas en la columna de entrada son 0 o negativas, entonces
no hay solución máxima. Para empates, elige cualquiera de las entradas.) La entrada en la fila de salida
y la columna de entrada se llama elpivote.
5. Utiliza operaciones elementales de fila para que el pivote sea 1, y todas las demás entradas en el
las columnas de entrada son 0. Este proceso se llama pivoteo.
6. Si todas las entradas en la fila inferior son cero o positivas, este es el tableau final. Si no, vaya
regresar al Paso 3.
7. Si obtienes un tableau final, entonces el problema de programación lineal tiene un máximo
solución, que se da por la entrada en la esquina inferior derecha del tableau.

Tenga en cuenta que la solución básica factible de una tabla simplex inicial es

͑x1,x2, . . . ,xn,s1,s2, . . . ,sm ͒ ϭ ͑0, 0, . . . , 0,b1,b2, . . . ,bm .͒

Esta solución es básica porque en su mayoría las variables son no cero (a saber, las variables de holgura).
Es viable porque cada variable es no negativa.
En los siguientes dos ejemplos, ilustramos el uso del método simplex para resolver un
problema que involucra tres variables de decisión.

E J E M P L O 2 El Método Simplex con Tres Variables de Decisión

Utiliza el método simplex para encontrar el valor máximo de
zϭ 2x1Ϫ x2ϩ 2x3 Función objetivo

sujeto a las restricciones

2x1ϩ 2x2Ϫ 2x3Յ 10
2x1ϩ 2x2Ϫ 2x3Յ 20
2x1ϩ 2x2ϩ 2x3Յ 25

dónde está x1Ն 0,x2Ն 0,y3Ն 0.

Solución usando la solución básica factible

͑x1,x2,x3,s1,s2,s3͒ ϭ ͑0, 0, 0, 10, 20, 5͒
el tableau simplex inicial para este problema es el siguiente. (Intenta verificar estos cálculos,
y note el "empate" que ocurre al elegir la primera variable de entrada.
 SECCIÓN9.3 MÉTODOSIMPLE:MAXIMIZACIÓN 501

Básico
x1 x2 x3 s1 s2 s3 b Variables

2 1 0 1 0 0 10 s1
1 2 Ϫ2 0 1 0 20 s2
0 1 2 0 0 1 5 s3 ← Saliendo
Ϫ2 1 Ϫ2 0 0 0 0
↑
Entrando

Básico
x1 x2 x3 s1 s2 s3 b Variables

2 1 0 1 0 0 10 s1 ← Saliendo
1 3 0 0 1 1 25 s2
1 1 5
0 2 1 0 0 2 2 x3

Ϫ2 2 0 0 0 1 5
↑
Entrando

Básico
x1 x2 x3 s1 s2 s3 b Variables
1 1
1 2 0 2 0 0 5 x1
5
0 2 0 Ϫ12 1 1 20 s2
1 1 5
0 2 1 0 0 2 2 x3

0 3 0 1 0 1 15

Esto implica que la solución óptima es

͑x1,x2,x3,s1,s2,s3͒ ϭ ͑5, 052 , 0, 20, 0͒

y el valor máximo de z es 15.

Ocasionalmente, las restricciones en un problema de programación lineal incluirán una ecuación.

En tales casos, todavía agregamos una "variable de holgura" llamada variable artificial para formar el ini-
tabla simplex trivial. Técnicamente, esta nueva variable no es una variable de holgura (porque hay
no se debe aflojar). Una vez que haya determinado una solución óptima en un problema así,
debes verificar que se cumplan las ecuaciones dadas en las restricciones originales.
El ejemplo 3 ilustra tal caso.

E J E M P L O 3 El Método Simplex con Tres Variables de Decisión

Utiliza el método simplex para encontrar el valor máximo de

zϭ 3x1ϩ 2x2ϩ x3 Función objetivo

502 CAPÍTULO9 PROGRAMACIÓNLINEAL

sujeto a las restricciones

4x1ϩ 3x2ϩ 3x3ϭ 30
2x1ϩ 3x2ϩ 3x3Յ 60
2x1ϩ 2x2ϩ 3x3Յ 40

dónde está x1Ն 0,x2Ն 0,yx3Ն 0.

Solución Usando la solución factible básica

͑x1,x2,x31,s2,s3͒ ϭ ͑0, 0, 0, 30, 60, 40͒
el tableau simplex inicial para este problema es el siguiente. (Nota que1es un vari artificial-
capaz, en lugar de una variable de holgura.)
Básico
x1 x2 x3 s1 s2 s3 b Variables

4 1 1 1 0 0 30 s1 ← Partiendo
2 3 1 0 1 0 60 s2
1 2 3 0 0 1 40 s3

Ϫ3Ϫ2Ϫ1 0 0 0 0
↑
Entrando

Básico
x1 x2 x3 s1 s2 s3 b Variables
1 1 1 15
1 4 4 4 0 0 2 x1
5 1
0 2 2 Ϫ12 1 0 45 s2 ← Saliendo
7 11 65
0 4 4 Ϫ14 0 1 2 s3
3 45
0 Ϫ54Ϫ14 4 0 0 2
↑
Entrando

Básico
x1 x2 x3 s1 s2 s3 b Variables
1 3
1 0 5 10 Ϫ110 0 3 x1
1 2
0 1 5 Ϫ15 5 0 18 x2
12 1
0 0 5 10 Ϫ170 1 1 s3
1 1
0 0 0 2 2 0 45
Esto implica que la solución óptima es
͑x1,x2,x3,s1,s2,s3͒ ϭ ͑3, 18, 0, 0, 0, 1͒
y el valor máximo de z es 45. (Esta solución satisface la ecuación dada en el con-
restricciones porque4͑ 3͒ ϩ 1͑ 18͒ ϩ 1͑ 0͒ ϭ 30.͒
 SECCIÓN9.3 ELMÉTODOSIMPLE:MAXIMIZACIÓN 503

Aplicaciones

E J E M P L O 4A Aplicación Empresarial: Máximo Beneficio

Un fabricante produce tres tipos de accesorios de plástico. El tiempo requerido para el moldeo,
el recorte y el empaquetado se dan en la Tabla 9.1. (Los tiempos se dan en horas por docena
accesorios.)
TABLA9.1

Proceso TipoA Tipo B Tipo C Tiempo total disponible

3
Molienda 1 2 2 12,000
2 2
Recorte 3 3 1 4,600
1 1 1
Embalaje 2 3 2 2,400

Beneficio $11 $16 $15 —

¿Cuántas docenas de cada tipo de accesorio se deben producir para obtener un máximo beneficio?

Solución Dejando x1,x2,y3representar el número de docenas de unidades de los Tipos A, B y C, en respeto a

tivamente, la función objetivo está dada por
Beneficioϭ Pϭ 11x1ϩ 16x2ϩ 15x3.
Además, utilizando la información de la tabla, construimos las siguientes restricciones.
2
3 x1ϩ 2x2ϩ 32 x3Յ 12,000
2 2 3
3 x1ϩ 3 x2ϩ 2 x3Յ 14,600
1 1 1
2 x1ϩ 3 x2ϩ 2 x3Յ 12,400
(También asumimos que x1Ն 0,x2Ն 0,y otro3Ն 0.) Ahora, aplicando el método simplex con
la solución básica factible
͑x1,x2,x3,s1,s2,s3͒ ϭ ͑0, 0, 0, 12,000, 4,600, 2,400͒
obtenemos los siguientes tableros.
Básico
x1 x2 x3 s1 s2 s3 b Variables
3
1 2 2 1 0 0 12,000 s1 ← Partiendo
2 2
3 3 1 0 1 0 4,600 s2
1 1 1
2 3 2 0 0 1 2,400 s3

Ϫ11Ϫ16Ϫ15 0 0 0 0
↑
Entrando
504 CAPÍTULO9 PROGRAMACIÓNLINEAL

Básico
x1 x2 x3 s1 s2 s3 b Variables
1 3 1
2 1 4 2 0 0 6,000 x2
1 1 1
3 0 2 Ϫ3 1 0 600 s2
1 1
3 0 4 Ϫ16 0 1 400 s3 ← Saliendo
Ϫ3 0 -3 8 0 0 96,000
↑
Entrando

Básico
x1 x2 x3 s1 s2 s3 b Variables
3 3
0 1 8 4 0 Ϫ32 5,400 x2
1
0 0 4 Ϫ16 1 Ϫ1 200 s2 ← Partiendo
3
1 0 4 Ϫ12 0 3 1,200 x1
13
0 0 Ϫ34 2 0 9 99,600
↑
Entrando

Básico
x1 x2 x3 s1 s2 s3 b Variables

0 1 0 1 Ϫ32 0 5,100 x2
0 0 1 Ϫ23 4 Ϫ4 800 x3
1 0 0 0Ϫ3 6 600 x1

0 0 0 6 3 6 100,200
De este tabla simplex final, vemos que la ganancia máxima es $100,200, y esto es
obtenido por los siguientes niveles de producción.

TipoA: 600 docenas de unidades

Tipo B: 5,100 docenas de unidades

Tipo C: 800 docenas de unidades

Observación: En el Ejemplo 4, note que el segundo tableau simplex contiene un “empate” para el
entrada mínima en la fila inferior. (Tanto la primera como la tercera entrada en la fila inferior son
Ϫ3.) Aunque elegimos la primera columna para representar la variable de salida, podríamos haber
elegido la tercera columna. Intenta reformular el problema con esta elección para ver qué obtienes
la misma solución.

E J E M P L O 5A Aplicación Empresarial: Selección de Medios

Las alternativas publicitarias para una empresa incluyen televisión, radio y periódico.
anuncios. Los costos y estimaciones para la cobertura de la audiencia se presentan en la Tabla 9.2
 SECCIÓN9.3 ELMÉTODOSIMPLE:MAXIMIZACIÓN 505

TABLA9.2

Televisión Periódico Radio

Costo por anuncio $ 2,000 $ 600 $300

Audiencia por anuncio 100,000 40,000 18,000

El periódico local limita el número de anuncios semanales de una sola empresa a

diez. Además, para equilibrar la publicidad entre los tres tipos de medios, no más
más de la mitad del número total de anuncios debería aparecer en la radio, y al menos el 10%
debería ocurrir en televisión. El presupuesto publicitario semanal es de $18,200. ¿Cuántos anuncios-
¿Se deberían ejecutar anuncios en cada uno de los tres tipos de medios para maximizar la audiencia total?

SoluciónPara comenzar, dejamos x1,x2,y3representar el número de anuncios en televisión, noticias-

papel y radio, respectivamente. La función objetivo (que debe ser maximizada) es, por lo tanto,

zϭ 100,000x1ϩ 40,000x2ϩ 18,000x3 Función objetivo

dónde está x1Ն 0,x2Ն 0,y otro3Ն 0.Las restricciones para este problema son las siguientes.
2000x1ϩ 600x2ϩ 300x3Յ 18,200
2000x1ϩ 600x2ϩ 300x3Յ 10
2000x1ϩ 600x2ϩ 300x3 Յ 0.5͑x1ϩ x2ϩ x3͒
2000x1ϩ 600x2ϩ 300x3Ն 0.1͑x1ϩ x2ϩ x3͒

Una forma más manejable de este sistema de restricciones es la siguiente.

}
20x1ϩ 6x2ϩ 3x3Յ 182
20x1ϩ 6x2ϩ 3x3Յ 110
Ϫx1Ϫ 6x2ϩ 3x3Յ 180 Restricciones
Ϫ9x1ϩ 6x2ϩ 3x3Յ 180

Así, el tableau simplex inicial es el siguiente.

Básico
x1 x2 x3 s1 s2 s3 s4 b Variables

20 6 3 1 0 0 0 182 s1 ← Partiendo
0 1 0 0 1 0 0 10 s2
Ϫ1 Ϫ1 1 0 0 1 0 0 s3
Ϫ9 1 1 0 0 0 1 0 s4

Ϫ100,000Ϫ40,000Ϫ18,000 0 0 0 0 0
↑
Entrando
506 CAPÍTULO9 PROGRAMACIÓNLINEAL

Ahora, a este tableau inicial, aplicamos el método simplex de la siguiente manera.

Básico
x1 x2 x3 s1 s2 s3 s4 b Variables
3 3 1 91
1 10 20 20 0 0 0 10 x1
0 1 0 0 1 0 0 10 s2 ← Partiendo
veintitrés 1 91
0 Ϫ170 20 20 0 1 0 10 s3
37 47 9 819
0 10 20 20 0 0 1 10 s4

0 Ϫ10,000Ϫ3,0005,000 0 0 0 910,000
↑
Entrando

Básico
x1 x2 x3 s1 s2 s3 s4 b Variables
3 1 61
1 0 20 20 Ϫ130 0 0 10 x1
0 1 0 0 1 0 0 10 x2
23 1 7 161
0 0 20 20 10 1 0 10 s3 ← Partiendo
47 9 37 449
0 0 20 20 Ϫ 10 0 1 10 s4

0 0 Ϫ3,000 5,000 0 0 1.010.000

↑
Entrando

Básico
x1 x2 x3 s1 s2 s3 s4 b Variables
1
1 0 0 23 Ϫ293 Ϫ233 0 4 x1
0 1 0 0 1 0 0 10 x2
1 14 20
0 0 1 23 veintitrés 23 0 14 x3
8 118 47
0 0 0 23 Ϫ 23 Ϫ 23 1 12 s4
118,000 272,000 60,000
0 0 0 23 23 23 0 1,052,000
De este tableau, vemos que la audiencia semanal máxima para un presupuesto publicitario de
$18,200 es
zϭ 1.052.000 Audiencia máxima semanal

y esto ocurre cuando1ϭ 4,x2ϭ 10,y3ϭ 14. Resumimos los resultados aquí.

Número de
Medios Anuncios Costo Público
Televisión 4 $ 8,000 400,000
Periódico 10 $ 6,000 400,000
Radio 14 $ 4,200 252,000
Total 28 $18,200 1.052.000
 SECCIÓN9.3 EJERCICIOS 507

SECCIÓN 9.3❑ EJERCICIOS

En los Ejercicios 1–4, escribe la tabla simplex para el problema lineal dado. 11. Función objetivo: 12. Función objetivo:
problema de programación. No necesitas resolver el problema. (En cada zϭ 5x1ϩ 2x2ϩ 8x3 zϭ x1Ϫ x2ϩ 2x3
el caso de que la función objetivo deba ser maximizada. Restricciones: Restricciones:
1. Función objetivo: 2.Función objetivo: 2x1Ϫ 4x2ϩ 3x3Յ 42 2x1ϩ 2x2Յ 8
zϭ x1ϩ 2x2 zϭ x1ϩ 3x2 2x1ϩ 3x2Ϫ 3x3Յ 42 2x1ϩ 2x3Յ 5
Restricciones: Restricciones: 6x1Ϫ 3x2ϩ 3x3Յ 42 x1,x2,x3Ն 0
2x1ϩ x2Յ 8 x1ϩ x2Յ 4 x1,x2,x3Ն 40
2x1ϩ x2Յ 5 x1Ϫ x2Յ 1 13. Función objetivo: 14. Función objetivo:
2x1,x2Ն 0 x1,x2Ն 0 zϭ 4x1ϩ 5x2 zϭ x1ϩ 2x2
3. Función objetivo: 4. Función objetivo: Restricciones: Restricciones:
zϭ 2x1ϩ 3x2ϩ 4x3 zϭ 6x1Ϫ 9x2 3x1ϩ 7x2Յ 10 2x1ϩ 3x2Յ 15
Restricciones: Restricciones: 3x1ϩ 7x2Յ 42 2x1Ϫ 3x2Յ 12
x1ϩ 2x2ϩ x3Յ 12 2x1Ϫ 3x2Յ 26 x1,x2Ն 40 x1,x2Ն diez
x1ϩ 2x2ϩ x3Յ 18 2x1ϩ 3x2Յ 20 15. Función objetivo: 16. Función objetivo:
x1,x2,x3Ն 10 x1,x2Ն veinte zϭ 3x1ϩ 4x2ϩ x3ϩ 7x4 zϭ x1
Restricciones: Limitaciones:
En los ejercicios 5-8, explica por qué el problema de programación lineal es
8x1ϩ 3x2ϩ 4xtresϩ 5x4Յ 7 3x1ϩ 2x2Յ 60
no está en la forma estándar como se dio.
2x1ϩ 6x2ϩ 4x3ϩ 5x4Յ 3 3x1ϩ 2x2Յ 28
5. (Minimizar) 6.(Maximizar)
2x1ϩ 4x2ϩ 5x3ϩ 2x4Յ 8 3x1ϩ 4x2Յ 48
Función objetivo: Función objetivo:
x1,x2,x3,x4Ն 0 x1,x2Ն 40
zϭ x1ϩ x2 zϭ x1ϩ x2
Restricciones: Restricciones: 17. Función objetivo: 18.Función objetivo:
zϭ x1Ϫ x2ϩ x3 zϭ 2x1ϩ x2ϩ 3x3
x1ϩ 2x2Յ 4 2x1ϩ 2x2Յ Ϫ6
x12Ն 0 2x1Ϫ 2x2Յ Ϫ1 Restricciones: Restricciones:
x1,x2Ն Ϫ0 2x1ϩ 2x2Ϫ 3x3Յ 40 2x1ϩ x2ϩ 3x3Յ 59
2x1ϩ 2x2ϩ 3x3Յ 25 2x1ϩ x2ϩ 3x3Յ 75
7.(Maximizar) 8.(Maximizar)
2x1ϩ 2x2ϩ 3x3Յ 32 2x1ϩ x2ϩ 6x3Յ 54
Función objetivo: Función objetivo:
x1,x2,x3Ն 30 x1,x2,x3Ն 50
zϭ x1ϩ x2 zϭ x1ϩ x2
Restricciones: Restricciones: 19. Función objetivo:
zϭ x1ϩ 2x2Ϫ x4
2x1ϩ x2ϩ 3x3Յ 5 x1ϩ x2Ն 4
Restricciones:
2x1ϩ x2Ϫ 2x3Ն 1 2x1ϩ x2Ն 6
x1ϩ 2x2ϩ 3x3ϩ x4Յ 24
2x1ϩ x2ϩ 3x3Յ 0 x1,x2Ն 0
x1ϩ 3x2ϩ 7x3ϩ x4Յ 42
x1,x2,x3 Ն 0
x1,x2,x3,x4Ն 40
En los ejercicios 9-20, utiliza el método simplex para resolver lo dado.
20. Función objetivo:
problema de programación lineal. (En cada caso, la función objetivo
zϭ x1ϩ 2x2ϩ x3Ϫ x4
se debe maximizar.)
Restricciones:
9. Función objetivo: 10. Función objetivo:
2x1ϩ 3x2ϩ 3x3ϩ 4x4Յ 60
zϭ x1ϩ 2x2 zϭ x1ϩ x2
2x1ϩ 3x2ϩ 2x3ϩ 5x4Յ 50
Restricciones: Restricciones: 2x1ϩ 3x2ϩ 2x3ϩ 6x4Յ 72
x1ϩ 4x2Յ 18 3x1ϩ 2x2Յ 16 x1,x2,x3,x4Ն 70
x1ϩ 4x2Յ 12 3x1ϩ 2x2Յ 12
x1,x2Ն 10 x1,x2Ն 10
508 CAPÍTULO9 PROGRAMACIÓNLINEAL

21. Un comerciante planea vender dos modelos de computadoras para el hogar en 26. Supongamos en el Ejercicio 25 que el tiempo total disponible para el ensamblaje...
costos de $250 y $400, respectivamente. El modelo de $250 produce un bling, painting, and packaging is 4000 hours, 2500 hours, and
una ganancia de $45 y el modelo de $400 genera una ganancia de $50. El 1500 horas, respectivamente, y que el beneficio por unidad es de $48
el comerciante estima que la demanda total mensual no será (Modelo A), $50 (Modelo B) y $52 (Modelo C). ¿Cuántos
exceder 250 unidades. Encuentra el número de unidades de cada modelo que ¿de cada tipo debería producirse para obtener un máximo beneficio?
debe ser almacenado para maximizar el beneficio. Suponga que 27. Una empresa ha presupuestado un máximo de $600,000 para publicidad.
el comerciante no quiere invertir más de $70,000 en publicitando un cierto producto a nivel nacional. Cada minuto de televisión
inventario de computadoras. (Ver el ejercicio 21 en la sección 9.2.) el tiempo cuesta $60,000 y cada anuncio de una página en el periódico cuesta
22. Un cultivador de frutas tiene 150 acres de terreno disponibles para cultivar dos $15,000. Se espera que cada anuncio televisivo sea visto por 15
cultivos, A y B. Se necesita un día para cortar una hectárea del cultivo A y un millón de espectadores, y se espera que cada anuncio en el periódico sea
dos días para cosechar una hectárea del cultivo B, y hay 240 días por visto por 3 millones de lectores. La investigación de mercado de la empresa
año disponible para recortar. Toma 0.3 días recoger una acre de el departamento aconseja a la empresa que use como máximo el 90% del
cosecha A y 0.1 días para cosechar una acre de cosecha B, y hay 30 presupuesto publicitario en anuncios de televisión. ¿Cómo debería el
días por año disponibles para la cosecha. Encuentra el número de acres el presupuesto de publicidad debe asignarse para maximizar el total de audiencias
de cada fruta que debería ser plantada para maximizar el beneficio, como- ¿qué?
suponiendo que la ganancia es de 140 dólares por acre para el cultivo A y 235 dólares 28. Rehacer el ejercicio 27 asumiendo que cada periódico de una página
por acre para B. (Vea el Ejercicio 22 en la Sección 9.2.) el costo del anuncio es de $30,000.

23. Una cultivadora tiene 50 acres de tierra para la cual planea criar 29. Un inversor tiene hasta $250,000 para invertir en tres tipos de
tres cultivos. Cuesta 200 dólares producir un acre de zanahorias y las inversiones. El Tipo A paga un 8% anualmente y tiene un factor de riesgo de
la ganancia es de $60 por acre. Cuesta $80 producir un acre de El tipo B paga un 10% anualmente y tiene un factor de riesgo de 0.06.
el apio y la ganancia es de $20 por acre. Finalmente, cuesta $140 para El tipo C paga un 14% anual y tiene un factor de riesgo de 0.10. Para
produzca un acre de lechuga y la ganancia es de $30 por acre. tener una cartera bien equilibrada, el inversor impone el fol-
el método simplex para encontrar el número de acres de cada cultivo las condiciones siguientes. El factor de riesgo promedio no debe ser
ella debería plantar para maximizar su beneficio. Suponga que mayor que 0.05. Además, al menos una cuarta parte del total
su costo no puede exceder de $10,000. el portafolio debe ser asignado a inversiones Tipo A y al menos
Una empresa de jugos de frutas elabora dos bebidas especiales mezclando una cuarta parte del portafolio se destinará a inversiones de Tipo B
jugos de manzana y piña. La primera bebida usa 30% de manzana ¿Cuánto debería asignarse a cada tipo de inversión?
jugo y 70% piña, mientras que la segunda bebida utiliza 60% ¿Qué inversión se debe hacer para obtener un máximo rendimiento?

manzana y 40% piña. Hay 1000 litros de manzana y 30. Un inversor tiene hasta $450,000 para invertir en tres tipos de
1500 litros de jugo de piña disponibles. Si la ganancia por el las inversiones. El Tipo A paga un 6% anual y tiene un factor de riesgo
la primera bebida cuesta $0.60 por litro y la segunda bebida es de 0. Tipo B paga un 10% anual y tiene un factor de riesgo de 0.06.
$0.50, use el método simplex para encontrar el número de litros de El Tipo C paga un 12% anual y tiene un factor de riesgo de 0.08. Para
cada bebida que debería ser producida para maximizar el tener un portafolio bien equilibrado, el inversionista impone el
ganancia. las siguientes condiciones. El factor de riesgo promedio no debería ser
25. Un fabricante produce tres modelos de bicicletas. El tiempo mayor que 0.05. Además, al menos la mitad del total
(en horas) requeridas para ensamblar, pintar y empaquetar el portafolio debe ser asignado a inversiones de Tipo A y al menos
cada modelo es el siguiente. un cuarto de la cartera se asignará a inversiones del Tipo B
¿Cuánto debería asignarse a cada tipo de?
Modelo A Modelo B Modelo C inversión para obtener un retorno máximo?
31. Una firma de contabilidad tiene 900 horas de tiempo de personal y 100 horas
Montaje 2 2.5 3
de revisar el tiempo disponible cada semana. La firma cobra
Pintura 1.5 2 1 $2000 por una Auditoría y $300 por una declaración de impuestos. Cada auditoría
requiere 100 horas de tiempo del personal y 10 horas de tiempo de revisión,
Embalaje 1 0.75 1.25
y cada declaración de impuestos requiere 12.5 horas de tiempo del personal y 2.5
horas de tiempo de revisión. ¿Qué número de auditorías y declaraciones de impuestos?
El tiempo total disponible para ensamblar, pintar y empaquetar
son 4006 horas, 2495 horas y 1500 horas, respectivamente. generará un ingreso máximo?
La ganancia por unidad para cada modelo es de $45 (Modelo A), $50
(Modelo B), y $55 (Modelo C). Cuántos de cada tipo
¿debería producirse para obtener un máximo beneficio?
 SECCIÓN9.4 ELMÉTODOSIMPLEXO:MINIMIZACIÓN 509

32. La firma de contabilidad en el Ejercicio 31 aumenta su cargo por un 35.(Maximizar) 36. (Maximizar)
auditoría a $2500. ¿Cuántas auditorías y declaraciones de impuestos serán? Función objetivo: Función objetivo:
generar un máximo de ingresos? zϭ 2.5x1ϩ x2 zϭ x1ϩ 12x2
En el método simplex, puede suceder que al seleccionar el que sale Restricciones: Restricciones:
variable todos los ratios calculados son negativos. Esto indica un 3x1ϩ 5x2Յ 15 2x1ϩ 3x2Յ 20
solución acotada. Demuestra esto en los Ejercicios 33 y 34. 5x1ϩ 2x2Յ 10 2x1ϩ 3x2Յ 35
x1,x2Ն 10 x1,x2Ն 30
33. (Maximizar) 34.(Maximizar)
C 37. Utilice una computadora para maximizar la función objetivo
Función objetivo: Función objetivo:
zϭ x1ϩ 2x2 zϭ x1ϩ 3x2 zϭ 2x1ϩ 7x2ϩ 6x3ϩ 4x4
Restricciones: Restricciones: sujeto a las restricciones
Ϫx1Ϫ 3x2Յ 1 Ϫx1ϩ x2Յ 20 1.2x1ϩ 0.7x2ϩ 0.83x3ϩ 0.5x4Յ 65
Ϫx1ϩ 2x2Յ 4 Ϫ2x1ϩ x2Յ 50 1.2x1ϩ 0.7x2ϩ 0.83x3ϩ 1.2x4Յ noventa y seis
x1,x2Ն 0 x1,x2Ն 50 0.5x1ϩ 0.7x2ϩ 01.2x3ϩ 0.4x4Յ 80
dónde x1,x2,x3x4Ն 0.
Si el método simplex termina y una o más variables no están en C 38. Utiliza una computadora para maximizar la función objetivo
la base final tiene entradas en la fila inferior de cero, trayendo estos
las variables en la base determinarán otras soluciones óptimas. zϭ 1.2x1ϩ x2ϩ x3ϩ x4
Demuestra esto en los Ejercicios 35 y 36. sujeto al mismo conjunto de restricciones dadas en el Ejercicio 37.

9.4 EL MÉTODO SIMPLEX: MINIMIZACIÓN

En la Sección 9.3, aplicamos el método simplex solo a problemas de programación lineal en
forma estándar donde la función objetivo debía ser maximizada. En esta sección, ampliamos
este procedimiento para problemas de programación lineal en el que la función objetivo es ser
imizado.
Un problema de minimización está en forma estándar si la función objetivo wϭ c1x1ϩ c2x2
ϩ . . . ϩ cn xnse debe minimizar, sujeto a las restricciones

a11x1ϩ a12x2ϩ . . . ϩ a1nxnՆ b1

a21x1ϩ a22x2ϩ . . . ϩ a2nxnՆ b2

..
.
am1x1ϩ am2x2ϩ . . . ϩ amnxnՆ bm

dónde estáyoՆ 0 ybyoՆ 0.El procedimiento básico utilizado para resolver un problema así es convertirlo
a un problema de maximización en forma estándar, y luego aplicar el método simplex como dis-
maldijo en la Sección 9.3.
En el Ejemplo 5 de la Sección 9.2, utilizamos métodos geométricos para resolver lo siguiente
problema de minimización.