CAPITULO 2

PROGRAMACION LINEAL

2.1 CONCEPTO DE PROGRAMACION LINEAL

La Programación Lineal utiliza un modelo matemático para describir el
problema. El adjetivo Lineal significa que todas las funciones matemáticas del
modelo deben ser funciones lineales. En este caso, la palabra Programación no
se refiere a programación en computadora; en esencia es un sinónimo de
planeación. Así, la programación lineal trata la Planeación de las Actividades
para obtener un resultado óptimo, esto es, el resultado que mejor alcance la meta
especificada (según el modelo) entre todas las opciones de solución. Existe cierto
objetivo a alcanzar, tal como un beneficio máximo, costo mínimo, o mínimo
periodo de tiempo, del sistema que se tiene. Existe un gran número de variables
que deben manejarse simultáneamente. Estas variables pueden ser productos,
horas máquinas, horas-hombre, dinero, superficie, u otros factores según sea el
problema.

De ésta forma, la Programación Lineal tiende a asociarse con situaciones

complejas, muchas variables que se interaccionan, y objetivos competitivos junto
con la optimización de algún criterio de efectividad del sistema. Las
interacciones de las variables y la rivalidad de objetivos son características de
muchas situaciones industriales. Desde luego, son características de todos los
sistemas económicos.

Es natural entonces, en la industria, que muchos de sus más importantes

problemas pueden resolverse con los métodos de la Programación Lineal. No
obstante, es incorrecto suponer que todos los problemas industriales que
impliquen éstos elementos de iteración y competencia pueden tratarse con los
métodos de Programación Lineal.

Muchas personas clasifican el desarrollo de la programación lineal, entre los

avances científicos más importantes de mediados del siglo XX, y estamos de
acuerdo con esta aceleración. En la actualidad es una herramienta de uso normal
que ha ahorrado miles o millones de dólares a muchas compañías o negocios,
incluso empresas medianas, en los distintos países industrializados del mundo; su
aplicación a otros sectores de la sociedad se ha empleado con rapidez.

¿Cuál es la naturaleza de esta notable herramienta y que tipo de problemas puede

manejar? El tipo más común de aplicación abarca el problema general de
asignar recursos limitados entre actividades competitivas de la mejor manera
posible (es decir, en forma óptima).

12
Con más precisión, este problema incluye elegir el nivel de ciertas actividades
que compiten por recursos escasos necesarios para realizarlos. Y la variedad de
situaciones a las que se pueden aplicar esta descripción es sin duda muy grande,
y va desde la asignación de instalaciones de producción a los productos, hasta la
asignación de los recursos nacionales a las necesidades de un país; desde la
selección de una cartera de inversiones, hasta la selección de los patrones de
envió; desde la plantación agrícola, hasta el diseño de una terapia de radiaciones,
etc.

2.2 MODELO DE PROGRAMACION LINEAL

Ejemplo clásicos de Programación Lineal

Un modelo de Programación Lineal proporciona un método eficiente para

determinar una decisión óptima, (o una estrategia óptima o un plan óptimo)
escogida de un gran número de decisiones posibles. La decisión óptima es la que
satisface un objetivo, sujeto a varias restricciones. Por ejemplo, una decisión
óptima podría ser la decisión que produzca el más alto o máxima utilidad o el
más bajo o mínimo costo.

Construcción de modelos de Programación lineal

Requerimientos para construir un modelo de Programación Lineal.

1. Función Objetivo: debe haber un objetivo (o meta) que desea alcanzar.

Por ejemplo, maximizar las utilidades, minimizar el costo, maximizar el
potencial de clientes esperados, minimizar el tiempo total, etc.
2. Restricciones y decisiones: debe haber cursos alternativos de acción o
decisiones, uno de los cuales permite alcanzar el objetivo.
3. La función objetivo y las restricciones son lineales: Debe estar en
capacidad de expresar las decisiones del problema, incorporándolas a la
función objetivo y a las restricciones sobre decisiones, usando solamente
ecuaciones lineales o desigualdades lineales.

13
EJEMPLO PROTOTIPO

La fábrica WYNDOR GLASS CO. Produce artículos de vidrio de alta calidad,

incluyendo ventanas y puertas de vidrio. Tiene tres plantas. Los marcos y
molduras de aluminio se hacen en la planta 1, los marcos de madera se fabrican
en la planta 2 y en la 3 se produce el vidrio y se ensamblan los productos. [ Hillier,
Lieberman]

Debido a que las ganancias se han reducido, la administración ha decidido

reorganizar la línea de producción en la compañía. Se descontinuarán varios
productos no rentables y se dejará libre una parte de la capacidad de producción
para emprender la fabricación de uno o dos productos nuevos que han tenido
gran demanda en el mercado.

Producto 1: es una puerta de vidrio con marco de aluminio.

Producto 2: es una ventana de vidrio, doble con marco de madera.

El producto 1 es producido por las plantas 1 y 3 y nada en la planta 2, el producto

2 solo utiliza las plantas 2 y 3 para su producción. Sin embargo como ambos
productos compiten por la misma capacidad de producción en la planta 3, no es
obvio qué mezcla de los dos productos sería la más rentable. Los requerimientos
y capacidades disponibles están resumidos en la tabla 2.1

Tiempo de producción por lote, horas

______________________ Tiempo de producción
Producto disponible a la semana,
Planta horas
1 2
1 1 0 4
2 0 2 12
3 3 2 18
Ganancia
Por lote $3000 $5000
Tabla 2.1 Datos para el problema de WYNDOR GLASS CO

Construcción del modelo de Programación Lineal para el ejemplo de

Wyndor Glass Co.

PASO 1. Construir el modelo de decisión, primero tenemos que definir las

variables de decisión de éste ejemplo, éstas son.
x1  la cantidad de productos del producto 1 (puerta de vidrio con marco de
aluminio)
x 2  la cantidad de productos del producto 2 (ventana de vidrio, doble con
marco de madera).

14
PASO 2. Tenemos que definir el objetivo o meta de la WYNDOR GLASS CO
en términos de sus variables de decisión. Para hacer esto introduciremos el
concepto de función objetivo. Esta función muestra la relación existente entre la
producción total x1 y x 2 , y la utilidad. Sea Z = utilidad, entonces:

$3x1 = utilidad (ganancia) total por la venta de las puertas de vidrio con marco
de aluminio.
$5 x 2 = utilidad (ganancia) total por la venta de ventanas de vidrio, doble con
marco de madera.

Por lo tanto Z= $3x1 + $5 x 2 (función objetivo).

La función objetivo en este caso es escoger un x1 y x 2 tal que maximice la
utilidad, es decir, el objetivo es elegir los valores que maximicen a la función
objetivo, sujeta a las restricciones impuestas sobre sus valores por las
capacidades disponibles limitadas en cada planta.

PASO 3. Definir las restricciones de capacidad usando x1 y x 2 , observando la

tabla 2.1 se tiene que cada unidad del producto 1 que se produce por minuto
usará 1% de la capacidad de la planta 1, y sólo se dispone de 4%.

Así el producto 1 tiene que ser menor o igual que, la capacidad disponible, es
decir, ésta restricción se expresa mediante x1  4 .

De igual manera, para la planta 2 se tiene la restricción 2 x 2  12 .

Y la restricción para la planta 3 queda de la siguiente manera 3x1  2 x2  18 .

PASO 4. Restricción de las variables para que sean no negativas. Esto implica
como las tasas de producción no pueden ser negativas, es necesario restringir las
variables de decisión a valores no negativos: x1  0 y x2  0 .

Por lo que el modelo matemático de Programación Lineal para éste ejemplo

quedaría de la siguiente forma:
Maximizar z  3x1  5 x2
sujeta a
x1  4
2 x 2  12
3 x1  2 x 2  18
x1 , x 2  0

15
2.2.1 METODO GRAFICO (problemas de
maximización)
Usualmente las gráficas no son el mejor método para resolver problemas de
programación lineal del mundo real, ya que no podemos dibujar en más de tres
dimensiones. No obstante, una solución gráfica para un problema de tres (o
menos) dimensiones es efectiva para entender mejor la estructura de los modelos
de programación lineal. Los gráficos sirven para el entendimiento de la solución
óptima de los modelos de programación lineal.

FUNDAMENTOS MATEMATICOS

DEFINICION
Sea S el conjunto de todas las soluciones factibles de un problema lineal en su
forma estándar (Ax = b), S es un conjunto convexo.

Como S es un conjunto convexo con un número finito de puntos extremos ya que

A será de orden mxn ( m  n entonces los extremos de S tienen al menos n-m
componentes cero)
Cada una de las igualdades
n

a
j 1
ij x j  bi i=1, 2, …, m

es un conjunto convexo y como la intersección de m conjuntos convexos es

también convexo

COROLARIO
Dado un programa lineal
CT x
Ax  b
x0

si el polítopo convexo k correspondiente a éste programa lineal es acotado,

entonces k es un poliedro convexo, es decir, k se compone de puntos que son
combinación convexas de un número finito de puntos.

TEOREMA
La función objetivo Z=f(x) tiene su óptimo en un punto extremo de S siempre y
cuando exista y S esté acotado.

16
DEMOSTRACION
Supongamos que el mínimo existe, digamos x 0 que pertenece a S, entonces
f ( x0 )  f ( x) para toda x que pertenece a S.

Si x 0 es extremo de S queda demostrado.

Supongamos que x 0 no es extremo entonces x0  x1  (1   ) x 2 entonces,
f ( x0 )  f (x1  (1   ) x 2 )  f ( x1 )  (1   ) f ( x 2 )
para todo x1 , x 2 extremos.
Ahora sean x m un extremo mínimo, esto es, f ( x m )  f ( xi ) para toda i.
Entonces
f ( x1 )  (1   ) f ( x 2 )  f ( x m )
por lo tanto f ( x0 )  f ( x m )
lo cual contradice que x 0 sea mínimo, por lo tanto, x 0 no se pueden escribir
como
x1  (1   ) x2
así podemos afirmar que x 0 es extremo.
Este teorema nos permite afirmar que dado un modelo
Optimizar Z  ci xi
Sujeta a Ax  b
y S su región factible con n puntos extremos, entonces la solución óptima es
uno de ellos.

SOLUCION GRAFICA
Con los fundamentos matemáticos anteriores podemos deducir que la solución
de un modelo de programación lineal se encuentra en cualquiera de los vértices
del poliedro, que forman las restricciones.

Resolvamos gráficamente el modelo dado en el ejemplo de la sección 2.2 de

WYNDOR GLASS CO, en el cual el se encontró el modelo matemático quedó
como:
Maximizar z  3x1  5 x2
sujeta a
x1  4
2 x 2  12
3 x1  2 x 2  18
x1 , x 2  0

17
Para resolver éste modelo sigamos paso a paso el procedimiento para llegar a la
solución.

PASO 1. Primeramente graficar las restricciones del modelo matemático

Las ecuaciones de las restricciones son:
1) x1  4
2) 2 x 2  12
3) 3x1  2 x2  18

Al momento de graficarlas se toma el signo igual, quedando como sigue

1) x1  4
2) 2 x 2  12
3) 3x1  2 x2  18

La figura 2.1 muestra el trazo de la ecuación (1) como solo tiene una variable la
recta que resulte es paralela al eje de x 2 y pasa en el eje x1 con valores de (4,0).

Figura 2.1 Trazo de la recta x1  4

El área sombreada en la figura 2.2 muestra todas las soluciones que satisfacen la
restricción 1 ( x1  4 ), ya que el signo de menor o igual (  ).

18
 Figura 2.2 Soluciones que satisfacen la restricción 1 ( x1  4 )

Para trazar la ecuación (2) se despeja la variable, es decir, x2  12  2  6 y la

recta resulta paralela al eje x1 con valores de (0,6). (Ver figura 2.3).

Figura 2.3 Trazo de la ecuación 2 x 2  12

El área sombreada en la figura 2.4 muestra todas las soluciones que satisfacen la
restricción 2 ( 2 x 2  12 ), ya que el signo de menor o igual (  ).

19
 Figura 2.4 Soluciones que satisfacen la restricción 2 ( 2 x 2  12 )

Para trazar la ecuación (3) podemos darle valores a una variable para conocer la
otra: por ejemplo si le damos el valor de cero a x1 , es decir: 3(0)  2 x 2  18 ,
18
quedaría 2 x 2  18 , que despejando la variable se tiene que x 2   9 , así el
2
punto que ubicaríamos en el plano será: (0, 9), ahora si le damos el valor de cero
a x 2 , es decir: 3x1  2(0)  18 , quedaría 3x1  18 , que despejando la variable se
18
tiene que x1   6 , así el punto que ubicaríamos en el plano será: (0, 6). (Ver
3
la figura 2.5).

Figura 2.5 Trazo de la ecuación 3x1  2 x 2  18

20
El área sombreada en la figura 2.6 muestra todas las soluciones que satisfacen la
restricción 3 ( 3x1  2 x2  18 ), ya que el signo de menor o igual (  ).

Figura 2.6 Soluciones que satisfacen la restricción 3 ( 3x1  2 x 2  18 )

Trazamos por separado cada una de las restricciones, pero debemos trazar todas
en un solo plano cartesiano. Ahora, las gráficas 2.2, 2.4 y 2.6 pueden
superponerse para obtener una gráfica con las tres restricciones.

PASO 2. Identificar la región factible

La figura 2.7 muestra la gráfica donde se superponen las tres restricciones. Las
líneas punteadas representan el área de cada una de las ecuaciones. Para
identificar la región factible de la figura 2.7, es la intersección de las áreas de las
3 rectas, (la intersección de las 3 rectas punteadas), la figura 2.8 presenta la
región sombreada la cual incluye todo punto de solución que satisface
simultáneamente todas las restricciones. Debido a que estas soluciones se
denominan soluciones factibles, la región sombreada se llama región de
soluciones factibles, o tan sólo región factible. Cualquier punto en el límite de la
región factible, o dentro de la región factible, es un punto de solución factible
para el problema, es decir, cada punto contenido o situado en la frontera del
espacio de soluciones ABCDE satisface todas las restricciones y por consiguiente
representa un punto factible.

21
 Figura 2.7 Grafica que presenta las tres rectas en un
mismo plano y la región de cada una de ellas.

Figura 2.8 Grafica que presenta la región factible

PASO 3. Conocer el punto óptimo

Una vez que se identifico la región factible, buscamos el punto óptimo el cual va
proporcionar el mejor valor posible de la función objetivo. Para encontrar dicho
punto se requiere conocer la dirección en la cual incrementa la función objetivo
(z).

La solución óptima para un problema de programación lineal es la solución

factible que proporciona el mejor valor posible de la función objetivo.

22
Para describir como localizar el punto óptimo el cual proporciona los valores
para la solución óptima, como mencionamos anteriormente se necesita conocer la
dirección en la cual incremente z (la función objetivo), darle valores a z, por
ejemplo si a z le damos el valor de 15; la función objetivo queda así
15  3x1  5 x2 y se traza la línea recta que pasa por los puntos (0, 3) y (5,0).
(Ver figura 2.9). Como la función objetivo, z es maximizar, si le damos un
valor más grande que 15, digamos 20, quedaría entonces como 20  3x1  5 x2 y
trazamos la recta (cambiando el valor de z todas las rectas son paralelas). (Ver
figura 2.10).

Figura 2.9 Trazo de la función objetivo con el valor de 15 ( 15  3 x1  5 x2 )

Figura 2.10 Trazo de la función objetivo con los valores de 15 y 20

23
Para identificar el punto de solución óptima (es cualquier punto de la frontera de
la región factible ABCDE), como la función objetivo es maximizar y las rectas
de ésta son paralelas (ver figura 2.10), siguiendo la trayectoria de esas paralelas,
usando una regla y moverla paralelamente a éstas rectas, el punto óptimo es el
último punto en la región factible (frontera ABCDE). Este punto identifica la
solución óptima. Los valores óptimos para las variables de decisión son los
valores de x1 y x 2 en ese punto. (Ver figura 2.11).

Figura 2.11 Identificación del punto óptimo

PASO 4 Encontrar la solución óptima

La solución óptima ocurre en el punto C. Como C es la intersección de las rectas

(2) y (3), los valores de x1 y x 2 se determinan al resolver las dos ecuaciones
asociadas con las líneas (2) y (3) en forma simultánea:
2 x 2  12
3x1  2 x2  18
12
Si despejamos de 2 x 2  12 a x 2 se tiene entonces que x 2   6 ; para
2
conocer el valor de la otra variable sustituimos éste en 3x1  2 x2  18 , es decir
3x1  26  18 , así despejando x1 nos queda 3x1  18  12  6 , se tiene que
6
x1   2 .
3

Encontrando así los valores de

x2  6 y x1  2

Estos valores se sustituyen en la función objetivo z  3x1  5 x2 , encontrando el

valor de z
z  3(2)  5(6)  6  30  36

24
Por lo tanto la solución óptima es
x2  6
x1  2
z  36

PASO 5 Interpretación del problema

El punto (2, 6) proporciona las cantidades de producción óptima para WYNDOR

GLASS CO, es decir la empresa debe de producir 2 puertas de vidrio con
marco de aluminio y 6 ventanas de vidrio, doble con marco de madera,
por semana respectivamente y produce una contribución a la ganancia de 36
(Miles de dólares semanales).

EJEMPLO

Una fábrica de pinturas produce colorantes para interiores y exteriores de casas

para su distribución al mayoreo. Se utilizan dos materiales básicos, I y II, para
producir las pinturas. La disponibilidad máxima de I es de 6 toneladas diarias; la
de II es de 8 toneladas por día. Los requisitos diarios de materias primas por
tonelada de pintura para interiores y exteriores se resumen en la siguiente tabla.

Toneladas de materia prima

por tonelada de pintura
_________________________ Disponibilidad
Exterior interior máxima (toneladas)
Materia prima I 1 2 6
Materia prima II 2 1 8

Tabla 2.2. Datos para el problema de la fábrica de pinturas

Un estudio del mercado ha establecido que la demanda diaria de pintura para

interiores no puede ser mayor que la de pintura para exteriores en más de una
tonelada. El estudio señala asimismo, que la demanda máxima de pintura para
interiores está limitada a dos toneladas diarias.

El precio al mayoreo por tonelada es $3000 para la pintura de exteriores y $2000

para la pintura de interiores. La pregunta sería ¿Cuánta pintura para exteriores e
interiores debe producir la compañía todos los días para maximizar el ingreso
bruto?

Para construir el modelo sigamos los siguientes pasos.

PASO 1. Construir el modelo de decisión, primero tenemos que definir las

variables de decisión de éste ejemplo, éstas son.

25
x E = toneladas de pintura para exteriores producidas diariamente
x I = toneladas de pintura para interiores producidas diariamente

PASO 2. Tenemos que definir el objetivo o meta del problema en términos de

sus variables de decisión. Para hacer esto introduciremos el concepto de función
objetivo. Esta función muestra la relación existente entre la producción total x E
y x I , y la utilidad. Sea Z = utilidad, entonces, como cada tonelada de pintura
para exteriores se vende en $3000, el ingreso bruto obtenido de la venta de x E
toneladas es 3 x E miles de unidades monetarias y el ingreso bruto que se obtiene
de vender x I toneladas de pintura para interiores es de 2 x I miles de unidades
monetarias.

Así el ingreso bruto total se convierte en la suma de los dos ingresos, si hacemos
que z represente el ingreso bruto total, la función objetivo se puede escribir
matemáticamente como z  3x E  2 x I La meta consiste en determinar los
valores (factibles) de x E y x I que maximizarán este criterio.

El objetivo es elegir los valores que maximicen a la función objetivo, sujeta a las
restricciones impuestas sobre sus valores por las capacidades disponibles
limitadas.

PASO 3. Definir las restricciones de capacidad usando x E y x I , observando la

tabla 2.2.

El problema que estamos analizando impone restricciones sobre el uso de

materias primas y sobre la demanda. La restricción del uso de materias primas se
puede expresar en forma verbal como:

 uso de materias primas   disponibilidad máxima de 

    
 en ambas p int uras   materias primas 

Esto nos lleva a las restricciones que siguen (utilizando los datos del problema
que estamos analizando)
x E  2 x I  6 (Materia prima X)
2 x E  x I  8 (Materia prima Y)

Las restricciones sobre la demanda se expresan en forma verbal como

 cantidades en exceso de p int uras para 

   1 tonelada por día
 int eriores sobre exteriores 

demanda de p int ura para int eriores   2 tonelada por día

26
Matemáticamente, se presenta como:

x I  x E  1 (Exceso de pintura para interiores sobre pintura para exteriores)

xI  2 (Demanda máxima de pintura para interiores)

PASO 4. Restricción de las variables para que sean no negativas. Esto implica
como las tasas de producción no pueden ser negativas, es necesario restringir las
variables de decisión a valores no negativos: x E  0 y x I  0 .

Por lo que el modelo matemático de Programación Lineal para éste ejemplo,

donde se debe determinar las toneladas de pinturas para interiores y exteriores
que se producirán para maximizar la función objetivo queda como:
Maximizar z  3x E  2 x I (función objetivo)
Sujeto a
xE  2xI  6
2xE  xI  8 (Restricciones)
 xE  xI  1
xI  2
xE  0 , xI  0

 Una vez que se tiene el modelo matemático, seguir los pasos del
método gráfico para encontrar la solución óptima, como sigue:

PASO 1. Primeramente graficar las restricciones del modelo matemático

Las ecuaciones de las restricciones son:
1) xE  2xI  6
2) 2 x E  x I  8
3)  x E  x I  1
4) xI  2

Al momento de graficarlas se toma el signo igual, quedando como sigue

1) xE  2xI  6
2) 2 x E  x I  8
3)  x E  x I  1
4) xI  2
La figura 2.12 muestra el trazo de la ecuación (1) que para trazarla puedes darle
cualquier valor a una variable y ves cuánto vale la otra, por ejemplo si le das el
valor de cero a x E , es decir x E  0 , por lo tanto x I  3 , así el punto que se ubica
en el plano será (0,3); para encontrar otro punto de ésa misma ecuación, por
ejemplo si le das el valor de cero a x I  0 , el valor de x E  6 y el segundo
punto que ubica en el plano será (6,0), la gráfica de la figura 2.12 muestra la
recta (1).

27
 Figura 2.12 Trazo de la recta x E  2 x I  6

El área sombreada de la gráfica (figura 2.13) muestra todas las soluciones que
satisfacen la restricción 1 ( x E  2 x I  6 ), ya que el signo de menor o igual (  ).

Figura 2.13 Soluciones que satisfacen la restricción 1 ( x E  2 x I  6 )

Para trazar la ecuación (2) si le das el valor de cero a x E , es decir x E  0 , por

lo tanto x I  8 , así el punto que se ubica en el plano será (0,8); para encontrar
otro punto de ésa misma ecuación, por ejemplo si le das el valor de cero a
x I  0 , el valor de x E  8  2  4 , por lo que el segundo punto que se ubica en
el plano será (4,0), la gráfica de la figura 2.14 muestra la recta (2).

28
 Figura 2.14 Trazo de la recta 2 x E  x I  8

El área sombreada de la gráfica (figura 2.15) muestra todas las soluciones que
satisfacen la restricción 2 ( 2 x E  x I  8 ), ya que el signo es menor o igual (  ).

Figura 2.15 Soluciones que satisfacen la restricción 1 ( 2 x E  x I  8 )

29
La figura 2.16 muestra el trazo de las cuatro ecuaciones en el plano.

Figura 2.16 Trazo de las 4 restricciones

En la figura 2.17 muestra la gráfica que representa la región de cada una de las
restricciones (ecuaciones), es como si colorearas de color rojo la región de la
ecuación 2, de color verde la región de la ecuación 3, de color amarillo la región
de la recta 1 y de color azul la región de la ecuación 4; donde se intersecan los
cuatro colores ésa es la región factible como lo muestra la figura 2.18.

Figura 2.17 Soluciones que satisfacen las restricciones

30
 Figura 2.18. Gráfica que muestra la región factible

El espacio de soluciones resultante es el área ABCDEF. Cada punto contenido o

situado en la frontera del espacio de soluciones ABCDEF satisface todas las
restricciones y por consiguiente, representa un punto factible. Cualquier punto
dentro o en el límite del espacio ABCDEF es un punto factible, en el sentido de
que satisface todas las restricciones. Debido a que el espacio factible ABCDEF
consiste en un número infinito de puntos, necesitamos un procedimiento que
identifique la solución óptima.

Por el teorema que se analizó en el punto 2.1.2, la solución de un modelo de

programación lineal se encuentra en cualquiera de los vértices del poliedro, que
forman las restricciones, así puede ser cualquier punto de señalado en la figura
2.7. Para determinar cuál de todos ellos es el punto óptimo se requiere identificar
la dirección en la cual incrementa la función objetivo, es decir la función
z  3x E  2 x I (estamos maximizando z). Asignarle valores arbitrarios crecientes
por ejemplo 6 y 9 y trazar las líneas:
3x E  2 x I  6
3x E  2 x I  9
La figura 2.19 muestra éstas dos líneas en el espacio de solución del modelo.
Con ésas dos rectas se puede observar la trayectoria ya que cualquier otra que se
trace va a ser paralela a éstas por ejemplo si igualamos a la recta igual a 12, es
decir 3x E  2 x I  12 (ver figura 2.20)

31
 Figura 2.19. Gráfica que muestra la dos rectas de Z=6 y Z=9

Figura 2.20. Gráfica que muestra la recta de Z=12

De esta manera, la utilidad z se incrementa en la dirección que se muestra en la

figura 2.19, hasta que lleguemos al punto en el espacio de la solución más allá
del cual cualquier incremento adicional nos dejará fuera de los límites de
ABCDEF, es decir si se recorriera la recta Z=12 paralelamente el último punto
que toca de la región factible es el punto óptimo, como se muestra en la figura
2.21.

32
 Figura 2.21. Gráfica que muestra el punto óptimo

Así la solución óptima ocurre en el punto C. Como C es la intersección de las

rectas (1) y (2), los valores de x E y x I se determinan al resolver las dos
ecuaciones asociadas con las líneas (1) y (2) en forma simultánea:
xE  2xI  6
2xE  xI  8
Utilizando el método de eliminación (suma y resta) para eliminar una variable
deben de tener el mismo coeficiente y signo contrario para poder sumar y
eliminar una y quedarte con la otra, es decir si a la primera ecuación se multiplica
por -2, éste afecta a todos los términos de la ecuación y queda como:
( x E  2 x I  6 )(-2)
2xE  xI  8
El signo negativo afecta a todos los términos de la ecuación. Una vez que se tiene
el mismo coeficiente en ambas ecuaciones de una variable y con signo contrario
se puede realizar la suma de las dos ecuaciones y se elimina una variable
sumando la que queda (o restando), es decir.
 2 x E  4 x I  12
2xE  xI  8
 3x I  4
Por lo que despejando x I se tiene que
4
xI 
3
4
Por lo tanto aplicando la ley de los signos queda como x I 
3
Al sustituir el valor de x I en cualquier ecuación antes de haber multiplicado (las
originales), podemos conocer el valor de la otra variable es decir:
4
x E  2   6
3

33
 8
Multiplicando el entero por la fracción se tiene que: x E  6
3
8 18  8 10
Despejando xE  6   
3 3 3
Por lo tanto a solución al sistema de ecuaciones es:
10 4
xE  y xI 
3 3
10
Así ésta solución indica que la producción diaria debe ser de toneladas de
3
4
pintura para exteriores y de toneladas de pintura para interiores. El ingreso
3
respectivo es
 10   4  38
z  3   2   (Miles de $).
 3  3 3

2.2.2 UN PROBLEMA DE MINIMIZACION

M&D Chemicals produce dos productos que se venden como materias primas a
compañías que fabrican jabones para baño y detergentes para ropa. Basado en un
análisis de los niveles de inventario actuales y la demanda potencial para el mes
siguiente, la gerencia de M&D ha especificado que la producción combinada
para los productos A y B debe ser en total al menos 350 galones. Por separado,
también debe satisfacerse un pedido de un cliente importante de 125 galones del
producto A. el producto A requiere dos horas de procesamiento por galón,
mientras el producto B requiere una hora de procesamiento por galón, y para el
siguiente mes se dispone de 600 horas de tiempo de procesamiento. El objetivo
de M&D es satisfacer estos requerimientos con un costo total de producción
mínimo. Los costos de producción son 2 dólares por galón para el producto A y 3
dólares por galón para el producto B.

Para encontrar el calendario de producción de costo mínimo, formularemos el

problema como un modelo matemático de programación lineal. Siguiendo un
procedimiento parecido al usado para el problema de WYNDOR GLASS CO,
primero definiremos las variables de decisión y la función objetivo para el
problema. Sea
x1  Cantidad de galones del producto A
x 2  Cantidad de galones del producto B
Debido a que los costos de producción son $2 por galón para el producto A y $3
por galón para el producto B, la función objetivo que corresponde a la
minimización del costo total de producción puede escribirse como
Minimizar z  2 x1  3x2

34
A continuación consideremos las restricciones impuestas al problema. Para
satisfacer la demanda del cliente importante de 125 galones del producto A,
sabemos que A debe ser al menos 125. Por lo tanto, la restricción queda como
x1  125
Debido a que la producción combinada para ambos productos debe ser en total al
menos 350 galones, por lo que la restricción es
x1  x 2  350

Por último, la limitación en el tiempo de procesamiento disponible de 600 horas

significa que necesitamos agregar la restricción
2 x1  x2  600

Por lo tanto el modelo matemático se expresa como

Minimizar z  2 x1  3x2
sujeta a
x1  125
x1  x 2  350
2 x1  x2  600
x1 , x2  0

El método gráfico para solucionar el modelo matemático de este problema, como

en el problema WYNDOR GLASS CO, requiere primero tracemos la gráfica de
las líneas de restricción para encontrar la región factible. Al trazar cada línea de
restricción por separado y luego verificar los puntos en cada lado de la línea,
pueden identificarse las soluciones que satisfacen cada restricción. Al combinar
las soluciones que satisfacen cada restricción en la misma gráfica obtenemos la
región factible que se muestra en la figura 2.22.

Figura 2.22 Región factible para el problema de M&D Chemicals

35
Para encontrar la solución de costo mínimo, ahora tracemos la línea de la función
objetivo (z) correspondiente a un valor de costo total particular. Por ejemplo,
podríamos comenzar trazando la línea dándole un valor a z=1100, la línea será
2 x1  3x2  1100 . Esta línea se la que se muestra en la figura 2.23.

Figura 2.23 Solución gráfica par el problema de M&D Chemicals

Para localizar el punto óptimo movemos la línea de la función objetivo hacia

abajo (porque es minimizar), el punto óptimo es el último punto de la región
factible. (Ver figura 2.23).
Una vez identificando el punto óptimo observamos cuáles rectas se cruzan en
éste punto y solucionándolas como un sistema de ecuaciones encontramos los
valores de x1 y x 2

( x1  x 2  350 )(-1)
2 x1  x2  600

-1 x1 - x 2 =-350
2 x1  x2  600
x1  250

Sustituyendo el valor de x1  250 en una ecuación se tendría 250  x 2  350

despejando x 2 queda
x2  350  250  100 , esto es, x 2  100

Por lo que las coordenadas del punto óptimo son (250, 100), éstos valores
proporcionan la solución de costo mínimo con un valor de función objetivo de
z  2(250)  3(100)  500  300  800

36
2.3 METODO SIMPLEX
INTRODUCCION

En la solución de modelos de programación lineal, en el procedimiento gráfico

observamos que la solución óptima está asociada siempre con un punto extremo
del espacio de soluciones. El método simplex está basado fundamentalmente en
este concepto.

Careciendo de la ventaja visual asociada con la representación gráfica del

espacio de soluciones, el método simplex emplea un proceso iterativo que
principia en un punto extremo factible, normalmente el origen y se desplaza
sistemáticamente de un punto extremo factible a otro, hasta que se llega por
último al punto óptimo.

Un problema de programación lineal es un programa matemático en el cual la

función objetivo es lineal en las incógnitas y las restricciones constan de
igualdades y desigualdades lineales. La forma exacta de estas restricciones puede
variar de unos problemas a otros, pero, cualquier programa lineal que se puede
convertir al problema general de programación lineal es el siguiente: dado un
sistema de m ecuaciones lineales en n variables,
a11 x1  a12 x 2    a1n x n  x n 1  b1
a21 x1  a22 x2    a2n xn  xn 2  b2
(1)
 
a m1 x1  a m 2 x 2    a mm x n  x n  m  bm

Y una función en una forma lineal en las mismas variables,

Z  c1 x1  c 2 x 2    c n x n

Hallar entre las soluciones del sistema (1), aquellas soluciones no negativas para
las cuales la forma Z toma su valor mínimo o máximo. Tal solución es una
solución óptima del sistema dado.
Donde las bi , ci y a ij son constantes reales fijas, y las x i son variables reales
a determinar.

37
2.3.1 FUNDAMENTO MATEMATICO
En el espacio de dos dimensiones, si se tienen dos vectores P1 y P2 que
parten del origen y que no se encuentran en la misma recta, es decir, dos vectores
linealmente independientes, entonces cualquier tercer vector P0 en este espacio
se puede expresar como una combinación lineal de ellos.

En el espacio de tres dimensiones, si se tienen tres vectores, todos partiendo del

origen y no todos en el mismo plano, es decir, tres vectores linealmente
independientes, entonces cualquier curto vector P0 en este espacio puede
expresarse como una combinación lineal de estos tres. En la figura 2.24 se ilustra
el caso donde el vector P0 se puede representar mediante la combinación lineal.
P0  P1  (1 / 2) P2  (2 / 3) P3
De los vectores linealmente independientes P1 , P2 y P3

Figura 2.24 Representación del vector P0 como una combinación lineal

En el espacio de dimensión dos, si tomamos a los dos vectores P1 (a11 , a 21 ) y

P2 (a12 , a22 ) en lugar de P1 (a11 , a12 ) y P2 (a21 , a22 ) se tiene el
determinante
a11 a12
a 21 a 22
Donde las componentes de los vectores forman las columnas del determinante.
Si P1 y P2 son linealmente independientes, este determinante no es cero.
Además el valor absoluto de este determinante es igual al área del paralelogramo
con los lados P1 y P2 como muestra la figura 2.25.

38
 Figura 2.25 Área del paralelogramo con los lados P1 y P2

En el espacio de dimensión 3, tres vectores linealmente independientes

P1 (a11 , a 21 , a31 ) , P2 (a12 , a 22 , a32 ) , P3 (a13 , a 23 , a33 )
Determinan un paralelepípedo (ver figura 2.26). En este caso, el valor absoluto
del determinante
a11 a12 a13
a 21 a 22 a 23
a 31 a 32 a 33
Es diferente de cero y es igual al volumen del paralelepípedo.

Figura 2.26 Tres vectores linealmente independientes

Análogamente, en el espacio de dimensión m si se dan m vectores linealmente

independientes, por ejemplo,

Pj (a1 j , a 2 j ,  , aij ,  a mj ) i=1,2,…,m,

Entonces el determinante

39
 a11 a12  a1 j  a1m
a21 a22  a2 j  a2 m
  
0
ai1 ai 2  aij  aim
  
am1 am 2  amj  amm

Ahora, supongamos que en el espacio de dimensión m se dan n vectores

arbitrarios
Pj ( a1 j , a 2 j , , aij ,  a mj ) i=1,2,…,m, j=1,2,…,n
Arreglando las componentes de los vectores Pi como las columnas de una
matriz mxn:
P1 P2 Pj Pn
a11 a12  a1 j  a1n 
 
a 21 a 22  a 2 j  a 2 n 
  
  (2)
ai1 ai 2  aij  ain 
 
  
a m1 a m 2  a mj  a mn 
 

Las columnas de esta matriz, consideradas como vectores de m componentes,

pueden, en general, ser linealmente dependientes.
El número máximo de columnas independientes de la matriz (2) se llama rango
de la matriz.
Consideremos el siguiente modelo
Maximizar Z  c T x
Sujeta a Ax  b (3)
x0

Donde A es una matriz de mxn, x es un vector columna de n componentes,

cT es un vector fila de n componentes y b es un vector columna de m
componentes. La desigualdad vectorial x  0 quiere decir que las componentes
de x son positivas.
En general, como es lógico, el problema lineal dado en (3) puede no tener
soluciones básicas. Sin embargo, se puede eliminar dificultades no esenciales
planteando ciertas hipótesis elementales sobre la estructura de la matriz A.

1. En primer lugar, suele suponerse que n>m, es decir, que el número de

variables x i es superior al número de restricciones de igualdades.

40
2. Segundo se suele dar por supuesto que las filas de A son linealmente
independientes, lo que corresponde a la independencia lineal de las m
ecuaciones. Una dependencia lineal entre las filas de A daría lugar a restricciones
contradictorias y, por tanto, no se produciría ninguna solución para (3), o
resultaría una redundancia que podría eliminarse. A si pues la hipótesis será que
la matriz A de mxn tiene m<n y las m filas de A son linealmente independientes.
Según ésta hipótesis el sistema (3) tendrá solución y de hecho, siempre tendrá
como mínimo una solución básica.

DEFINICION
Dado un programa lineal
Minimizar c T x
Sujeto a Ax=b (4)
x0
 Una solución factible de (4) es un punto X  ( x1 , x 2 , , x n ) que
satisface Ax=b y x  0 .
 Una solución factible básica es una solución factible que se obtiene al
hacer n-m variables igual a cero y resolver para las n restantes, siempre
que su determinante sea no cero.
 Una solución factible para las restricciones que alcance el valor mínimo
de la función objetivo sujeta a esas restricciones, se denomina solución
factible óptima. Si esta solución es básica, es una solución factible
básica óptima.

2.3.3 EL ALGORITMO SIMPLEX

PASO 1. Dado cualquier programa lineal se realiza una transformación.
PASO 2. Reescríbase la función objetivo de la siguiente manera:
Z  c1 x1  c 2 x 2    c n x n  0
PASO 3. Conviértanse todas las desigualdades en igualdades. Este paso requerirá
el uso de variables de Holgura. Que puede escribirse como:
a11 x1  a12 x 2    a1n x n  x n 1  b1
a21 x1  a22 x2    a2n xn  xn 2  b2
 
a m1 x1  a m 2 x 2    a mm x n  x n  m  bm
x1  0, x 2  0, , x n  0, x n 1  0,, xn  m  0

var iables de ho lg ura

La adición de las variables de holgura crea la primera base, que resulta ser la
matriz identidad.

41
 PASO 4. Constrúyase una tabla con los coeficientes del programa lineal. Esta
tabla tendrá la siguiente estructura.

Variables básicas
(Originales) Variables de Holgura
x1 x 2 ……… xn x n 1 x n  2 ……… xnm solución
Z x1 x 2 ……… xn x n 1 x n  2 ……… xnm
C C TERMINOS
x n 1 O O
E E
xn2 F F
I I
INDEPEN-
. DIENTES
C C
. I I
. E E
N N
xnm T T
E E
S S

PASO 5. Selecciónese como vector de entrada o variable que entra a la base el

coeficiente de la función objetivo el valor más grande en valor absoluto. En caso
de que exista un empate entre varios vectores que puedan ser candidatos,
rómpase el empate arbitrariamente, es decir, selecciónese a cualquiera de los
candidatos.

PASO 6. Una vez seleccionada la columna que entra a la nueva base, se

selecciona el vector de salida (variable de holgura que sale) utilizando el criterio
de que se divide la solución entre el vector que entra y se elige el mínimo.

PASO 7. La intersección en la tabla de la columna que entre y la que sale

determina el elemento pivote.

42
2.4 ILUSTRACION DEL METODO SIMPLEX
Este procedimiento algebraico se basa en la solución de sistemas de ecuaciones
lineales. Así, el primer paso para preparar el método simplex es convertir las
restricciones de desigualdad en restricciones de igualdad equivalentes. Esta
conversión se logra con la introducción de variables de holgura. Es decir cuando
una restricción se tenga el signo  , éste se convierte en igualdad sumando una
variable positiva que recibe el nombre de variable de holgura.

Para ejemplificar este método, utilizamos el problema de la Wyndor Glass Co.

Presentado en el capitulo 2. El modelo matemático es el siguiente.

Maximizar z  3x1  5 x2
sujeta a
x1  4
2 x 2  12
3 x1  2 x 2  18
x1 , x 2  0

Cuyo espacio de soluciones está representado en la figura 2.27. Se observa que la

solución óptima está asociada siempre con un punto extremo del espacio de
soluciones.

Careciendo de la ventaja visual asociada con la representación gráfica del

espacio de soluciones, el método simplex emplea un proceso iterativo que
principia en un punto extremo factible, normalmente el origen, y se desplaza
sistemáticamente de un punto extremo factible a otro, hasta que se llega por
último al punto óptimo. Frederick S. Hiller, Gerald J. Lieberman/ 2002

Figura 2.27 Se observa que la solución óptima está asociada siempre

43
 con un punto extremo del espacio de soluciones
La idea general del método lo ilustraremos con el espacio de soluciones
representado en la figura 2.26.
El algoritmo simplex da inicio en el origen (punto E de la figura 2.26, que suele
denominarse solución inicial. Después se desplaza a un punto extremo
adyacente, que pudiera ser A o D). La elección específica de uno u otro punto
depende de los coeficientes de la función objetivo. Como se realiza un proceso
de maximización, la solución se desplazará en la dirección en la cual crezca x1
hasta que se llegue al punto extremo A. En A, el proceso se repite para ver si hay
otro punto extremo que pueda mejorar el valor de la función objetivo. Una vez
más, mediante el uso de la información de la función objetivo podemos decir si
existe o no este punto. Finalmente, la solución se detendrá en B, el punto
extremo óptimo.

Existen dos reglas que rigen la selección del siguiente punto extremo del método
simplex:
1. el siguiente punto extremo debe ser adyacente al actual. Por ejemplo en
la figura 2.26 la solución no se puede desplazar de E a A en forma
directa. En cambio, debe seguir los bordes del espacio de soluciones: E
a A y después A a B.
2. la solución no puede regresar nunca a un punto extremo considerado con
anterioridad. Por ejemplo, en la figura 2.20 la solución no puede regresar
de A a E.

2.4.1 SOLUCION DE UN EJEMPLO

SIGUIENDO LOS PASOS DEL METODO
Maximizar z  3x1  5 x2
Sujeta a
x1  4
2 x 2  12
3 x1  2 x 2  18
x1 , x 2  0

Primeramente la función objetivo con las variables de holgura se convierte

Z  3x1  5 x1  0s1  0 s 2  0 s3  0
Donde S1 , S 2 y S 3 son las variables de holgura.

Ahora convirtamos las desigualdades en igualdades por medio de las variables de

holgura.
x1  S1  4 , donde S1  0

44
Así, se aumentan variables de holgura en todas las restricciones del modelo
matemático que tengan el signo  pero distinguiéndolas entre sí, es decir, que
no sea la misma variable de holgura que se agregue a cada una de las
restricciones del modelo. Al introducir variables de holgura en las otras
restricciones, el modelo de programación lineal original para este ejemplo queda
de la siguiente manera.

x1  S1 4
2 x 2  S 2  12
3x1  2 x 2  S 3  18
x1 , x 2 , S1, S 2 , S 3  0

Así el modelo listo para llevarlo a la tabla del método sipmlex es:

Maximiza Z  3x1  5 x1  0s1  0 s 2  0 s3  0

Sujeta a
x1  S1 4
2 x 2  S 2  12
3x1  2 x 2  S 3  18
x1 , x 2 , S1, S 2 , S 3  0

Como se mencionó anteriormente el método simplex, principia siempre en un

punto extremo factible y se desplaza siempre a un punto extremo factible
adyacente verificando el optimizado de cada punto antes de pasar a uno nuevo.

El modelo de nuestro ejemplo tiene tres ecuaciones y cinco incógnitas que

definen esencialmente todos los puntos del espacio de soluciones. En general el
modelo estándar tiene m ecuaciones y n incógnitas (m<n).

La forma tabular del método simplex utiliza una tabla simplex para desplegar de
manera compacta el sistema de ecuaciones que lleva a la solución.
 
var iables originales var iables de ho lg ura
x1 x2 S1 S2 S3 Solución
Z -3 -5 0 0 0 0
S1 1 0 1 0 0 4
S2 0 2 0 1 0 12
3 2 0 0 1 18
S3

Tabla 2.3 Tabla inicial del método simplex para el problema de la Wyndor
Glass Co.

45
La adición de las variables de holgura ha generado el primer punto extremo de la
región factibilidad, o sea la primera base formada por las columnas S 1 , S 2 y
S 3 . Este punto extremo está identificado por las siguientes coordenadas en el
espacio de 5 dimensiones:

x1  0 , x2  0 , S1  4 , S 2  12 , S 3  18

En éste punto extremo, es factible porque satisface las restricciones AX≤b, X≥0.

El objetivo a encontrar es que un punto extremo en la región de factibilidad

donde el valor de la función objetivo sea mejor que el actual.

Ahora del renglón de Z seleccionamos el mayor en valor absoluto, es decir de

 3  3 y  5  5 , elegimos -5. Por lo que la columna a entrar a la nueva base
es x 2 .

Para elegir o determinar la variable que sale se debe tomar en cuenta los
siguientes pasos:
 Elija los coeficientes de la columna que entra que son estrictamente
positivos (>0)
 Divida la solución entre los coeficientes de la columna que sale
 Identifique el renglón de menor valor de estas razones
 La variable básica es la que sale de ese renglón, y sustitúyala por la
variable básica es entrante de la columna en la tabla 2.4

Tabla 2.4 Aplicación de la prueba para elegir la variable que entra en el

problema Wyndor Glass Co

46
 Siguiendo los pasos para elegir la variable que va a salir se divide la
solución entre los coeficientes de la columna que sale y se elige la del valor
menor, como lo muestra la tabla 2.5.

Tabla 2.5 Ilustración para elegir la variable que sale

Señalamos la variable que sale y la que entra como lo muestra la tabla 2.6

Tabla 2.6 Variable que entra y la que sale

Sabiendo que el vector x 2 es que debe entrar y S 2 el que va a salir, el pivote

queda determinado. El pivote en este caso es 2 (que es el valor de la intersección
de la variable que entra y la que sale). El paso siguiente es construir el renglón
pivote que va a ser la variable que entra y se va a formar dividiendo todo el
renglón que sale entre el valor pivote (el valor 2), así que para construir la
segunda tabla primero se encuentra el renglón pivote como lo muestra la tabla
2.7.

47
 Tabla 2.7 Tabla simplex que muestra el renglón pivote

Este nuevo renglón que se muestra en la tabla 2.7, va a ser el pivote para
completar toda la tabla, para esto se realizan las siguientes operaciones:
1. Para llenar el renglón de Z 1 , al coeficiente de Z 0 de la variable que entró
se le antepone un signo negativo y se multiplica por el renglón pivote (de
la misma columna) y se suma con el valor de Z 0 (de la misma columna),
es decir:
-(-5)(0)+ (-3)=0-3=-3 (es el primer valor del renglón de Z 1 )
-(-5)(1)+ (-5)=+5-5=0 (es el segundo valor del renglón de Z 1 )
-(-5)(0)+ (0)=0 (es el tercer valor del renglón de Z 1 )
1 5
-(-5)   + (0)= (es el cuarto valor del renglón de Z 1 )
2 2
-(-5)(0) + (0)= 0 (es el quinto valor del renglón de Z 1 )
-(-5)(6) + (0)= 30 (es el valor de la solución del renglón de Z 1 )
Ahora se puede llenar el renglón de Z 1 , como lo muestra la tabla 2.8

48
 Tabla 2.8 Presentando los valores del renglón de Z1

2. Para llenar el renglón de S 1 (de la segunda tabla), al coeficiente de S 1 de

la variable que entró se le antepone un signo negativo y se multiplica por
el renglón pivote (de la misma columna) y se suma con el valor de S 1 (de
la misma columna), es decir:

-(0)(0)+ (1)=0+1=1 (es el primer valor del renglón de S 1 de la 2ª. tabla)

-(0)(1)+ (0)=0 (es el segundo valor del renglón de S 1 de la 2ª. tabla)
-(0)(0)+ (1)=1 (es el tercer valor del renglón de S 1 de la 2ª. tabla)
1
-(0)   + (0)=0 (es el cuarto valor del renglón de S 1 de la 2ª. tabla)
2
-(0)(0) + (0)= 0 (es el quinto valor del renglón de S 1 de la 2ª. tabla)
-(0)(6) + (4)= 4 (es el valor de solución de S 1 de la 2ª. tabla)

Ahora se puede llenar el renglón de Z 1 y de S 1 como lo muestra la tabla 2.9

49
 Tabla 2.9 Presentando los valores del renglón de Z 1 y de S 1

3. Para llenar el renglón de S 3 (de la segunda tabla), al coeficiente de S 3 de

la variable que entró se le antepone un signo negativo y se multiplica por
el renglón pivote (de la misma columna) y se suma con el valor de S 3 (de
la misma columna), es decir:
-(2)(0)+ (3)=0+3=3 (es el primer valor del renglón de S 3 de la 2ª. tabla)
-(2)(1)+ (2)=0 (es el segundo valor del renglón de S 3 de la 2ª. tabla)
-(2)(0)+ (0)=0 (es el tercer valor del renglón de S 3 de la 2ª. tabla)
1
-(2)   + (0)=-1 (es el cuarto valor del renglón de S 3 de la 2ª. tabla)
2
-(2)(0) + (1)= 1 (es el quinto valor del renglón de S 3 de la 2ª. tabla)
-(2)(6) + (18)= -12+18=6 (es el valor de solución de S 3 de la 2ª. tabla)

Ahora se puede llenar todos los renglones de la segunda tabla, tal como lo
muestra la tabla 2.10.

50
 Tabla 2.10 Primera iteración completa del método simplex.

Se ha terminado una iteración completa del Método Simplex. En esta iteración, el

proceso se ha movido de un punto extremo con componentes
x1  0 , x2  0 , S1  4 , S 2  12 , S 3  18
Correspondiente a la base ( S 1 , S 2 , S 3 ) y en donde la función objetivo es igual
a cero, a otro punto extremo con componentes
x1  0 , x2  6 , S1  4 , S2  0 , S3  6
Correspondiente a una nueva base ( S 1 , x 2 , S 3 ) y un nuevo valor de la
función objetivo de 30.

Sin embargo, falta una variable original que entre a la base y como el valor del
renglón Z 1 es negativo (-3), el valor de la función objetivo puede aún mejorar.
Repitiendo otra iteración del método simplex, se tiene que x1 entra a la nueva
base y la que sale es S 1 y realizando las operaciones correspondientes se realiza
el llenado de la última iteración (la ultima tabla que correspondiente a Z 2 ) como
lo muestra la tabla 2.11.

51
 Tabla 2.11 Tabla simplex completa para el problema de Wyndor Glass Co.

La nueva solución o punto extremo correspondiente a la nueva base ( S 1 x 2 x1 ),

es óptimo porque todos los coeficientes de Z 2 son positivos y además ya
entraron a la base las variables básicas.

Por lo tanto la solución óptima es:

x1  2 , x2  6 , Z=36

52
2.5 VARIABLES ARTIFICIALES
En la presentación del método simplex hemos utilizado las variables de holgura
como la solución básica inicial. Sin embargo, si la restricción original es una
ecuación o es del tipo (≥), ya no tenemos una solución factible básica inicial
preparada.

Ilustremos este aspecto a través de un ejemplo:

Minimizar z  4 x1  x 2
Sujeta a
3 x1  x 2  3
4 x1  3 x 2  6
x1  2 x 2  4
x1 , x 2  0

La forma estándar se obtiene aumentando una variable de exceso x 3 y sumando

una variable de holgura S 1 a los primeros miembros de las restricciones 2 y 3
respectivamente, para convertir en igualdades las desigualdades. Por lo tanto, el
modelo matemático adicionando la variable de exceso y la de holgura es el
siguiente.

Minimizar z  4 x1  x 2
Sujeta a
3 x1  x 2 3
4 x1  3 x 2  x3 6
x1  2 x 2  S1  4
x1 , x 2 , x3 , S1  0

La idea de utilizar variables artificiales es que se sume una variable no negativa

al primer miembro de cada ecuación que no tenga variables básicas iniciales
evidentes. La variable agregada desempeñara la misma función que una variable
de holgura, al proporcionar una variable básica inicial. Sin embargo, como estas
variables artificiales no tienen significado físico desde el punto de vista del
problema original el procedimiento será válido sólo si hacemos que estas
variables sean cero cuando se llegue al óptimo.
En otras palabras, las utilizamos sólo para iniciar la solución y después debemos
hacer que sean cero en la solución final; de lo contrario la solución resultante
será no factible. Existen dos métodos para lograr esa solución: la técnica M
(método de penalización) y la técnica de dos fases.

53
2.6 LA TECNICA DE LA GRAN M
Consideremos la forma estándar del ejemplo anterior
Minimizar z  4 x1  x 2
Sujeta a
3 x1  x 2 3
4 x1  3 x 2  x3 6
x1  2 x 2  S1  4
x1 , x 2 , x3 , S1  0

La primera y segunda ecuación no tiene variables que desempeñen el papel de

una variable de holgura. Por lo tanto, aumentamos las dos variables artificiales
R1 y R2 en estas dos ecuaciones de la manera siguiente:

3x1  x2  R1 3
4 x1  3x2  x3  R2  6

Podemos penalizar a R1 y R2 en la función objetivo asignándoles coeficientes

positivos muy grandes en la función objetivo. Sea M>0 una constante muy
grande. Entonces el modelo con las variables artificiales se transforma en:

Minimizar z  4 x1  x2  MR1  MR2

Sujeta a
3 x1  x 2  R1 3
4 x1  3 x 2  x3  R2 6
x1  2 x 2  S1  4
x1 , x 2 , x3 , R1 , R2 , S1  0

Para resolver el modelo anterior es necesario aumentar las variables artificiales

según se necesite para asegurar una solución inicial. Formando una nueva
función objetivo que busque la minimización de la suma de las variables
artificiales.

Como realizamos un proceso de minimización asignando M a R1 y R2 en la

función objetivo, el proceso de optimización que busca el valor mínimo de z
asignará por último valores de cero a R1 y R2 en la solución óptima.

54
Habiendo construido una solución factible inicial, se debe condicionar el
problema de modo que cuando lo pongamos en forma tabular, la columna del
lado derecho producirá la solución inicial en forma directa. Esto se hace
mediante el uso de las ecuaciones de restricciones para sustituir R1 y R2 en la
función objetivo. De manera que
R1  3  3x1  x2
R2  6  4 x1  3x2  x3

Por lo tanto la función objetivo se convierte en

z  4 x1  x2  M (3  3x1  x2 )  M (6  4 x1  3x2  x3 ) 
 (4  7M ) x1  (1  4M ) x2  Mx3  9M

Y la ecuación z ahora figura en la tabla como:

z  (4  7 M ) x1  (1  4M ) x 2  Mx 3  9M

Este es un problema de minimización, de manera que la variable que entra debe

tener el coeficiente más positivo en la ecuación z. Se llega al óptimo cuando
todas las variables no básicas tienen coeficientes z no positivos. (Recordando que
M es una constante positiva muy grande).

Ahora del renglón de Z seleccionamos el mayor en valor absoluto, como M es

positiva muy grande, se tiene que -4+7M > -1+4M; es decir de la columna o
variable que entra a la nueva base es x1 . La tabla inicial del método simplex es
la siguiente.

Tabla 2.12 Tabla inicial del método simplex (técnica M)

55
 Para elegir la variable que va a salir se divide la solución entre los
coeficientes de la columna que sale y se elige la del valor menor, como lo
muestra la tabla 2.13.

Tabla 2.13 Ilustración para elegir la variable que sale

Siguiendo el mismo procedimiento utilizado en el punto 3.5.1 se encuentra el

renglón pivote.

La tabla 2.14 muestra la variable que entra y la que sale

Tabla 2.14 Ilustración de la variable que entra y la que sale

56
 Tabla 2.15 Ilustración del renglón pivote en la primer iteración

Para llenar el renglón de Z 1 , al coeficiente de Z 0 de la variable que entró se le

antepone un signo negativo y se multiplica por el renglón pivote (de la misma
columna) y se suma con el valor de Z 0 (de la misma columna), es decir:
-(-4+7M)(1)+ (-4+7M)=4-7M-4+7M=0 (es el primer valor del renglón de Z 1 )
1 4  7M 4  7 M  3  12M 1  5M
-(-4+7M)   + (-1+4M)=  1  4M  
3 3 3 3
(es el segundo valor del renglón de Z 1 )

-(-4+7M)(0)+ (-M)=-M (es el tercer valor del renglón de Z 1 )

1 4  7M
-(-4+7M)   + (0)= (es el cuarto valor del renglón de Z 1 )
3 3
Los valores quinto y sexto son cero ya que multiplican a cero y al sumar cero el
resultado es cero también, así el valor de la solución del renglón de Z 1 será:
-(-4+7M)(1)+ (9M)=4-7M+9M=4+2M

La tabla 2.16 Muestra el renglón de Z 1 . Para llenar los renglones restantes de

la primera iteración el procedimiento es el mismo realizado en el punto 3.5.1, las
iteraciones terminan hasta que las variables x1 , x 2 y x 3 , entren a la base, así
la tabla completa del método simplex utilizando la técnica M es la que se muestra
en la tabla 2.17.

57
Tabla 2.16 Ilustración del renglón de Z1

58
 Tabla 2.17 Tabla final del método simplex utilizando la técnica M

2 9 17
La solución óptima es x1  , x2  y z
5 5 5

59
2.7 LA TECNICA DE DOS FASES
Una desventaja de la técnica M es el posible error de cálculo que pudiera
generarse de la asignación de un valor muy grande a la constante M. Para ilustrar
esto, supóngase que M=100000 en el ejemplo de la técnica M del ejemplo
anterior. Después en la tabla inicial, los coeficientes de x1 y x2 en la función z se
transforman en (-4+700000) y (-1+400000). El efecto de los coeficientes
originales (4 y 1) es ahora demasiado pequeño en relación con los números
grandes generados por los múltiplos de M. El resultado peligroso es que x 1 y x2
puede tratarse como variables con coeficientes cero en la función objetivo.

El método de dos fases está diseñado para remediar esta dificultad. Aunque las
variables artificiales se suman en la misma forma que se emplea en la técnica M,
se elimina el uso de la constante M mediante la solución del problema en dos
fases.

FASE I
Auméntese las variables artificiales según se necesite para asegurar una solución
inicial. Fórmese una nueva función objetivo que busque la minimización de la
suma de las variables artificiales sujeta a las restricciones del problema original
modificado por las variables artificiales. Si el valor mínimo de la nueva función
objetivo es cero (lo que quiere decir que todas las artificiales son cero), el
problema tiene un espacio de soluciones factible. Pase a la fase II de lo contrario,
si el mínimo es positivo, el problema no tiene solución factible. Deténgase.

FASE II
Utilícese la solución básica óptima de la fase I como solución inicial para el
problema original.

Ilustrando el procedimiento mediante el uso del ejemplo de la técnica M. Fase I:

como necesitamos las variables artificiales R1 y R2 en la primera y segunda
ecuaciones, el problema de la fase I quedaría como:

Minimizar r  R1  R2
Sujeta a
3 x1  x 2  R1 3
4 x1  3 x 2  x3  R2 6
x1  2 x 2  S1  4
x1 , x 2 , x3 , R1 , R2 , S1  0

60
Como R1 y R2 están en la solución inicial, deben sustituirse en la función
objetivo, esto es:

r  R1  R2  (3  3x1  x 2 )  (6  4 x1  3x 2  x3 )  7 x1  4 x 2  x3  9

Por consiguiente la tabla inicial se convierte en

Básica x1 x2 x3 R1 R2 S1 Solución
R 7 4 -1 0 0 0 9
R1 3 1 0 1 0 0 3
R2 4 3 -1 0 1 0 6
S1 1 2 0 0 0 1 4

La tabla óptima se obtiene en dos iteraciones y está dada por

Básica x1 x2 x3 R1 R2 S1 Solución
R 0 0 0 -1 -1 0 0
x1 1 0 1/5 3/5 -1/5 0 3/5
x2 0 1 -3/5 -4/5 3/5 0 6/5
S1 0 0 1 1 -1 1 1

Como el mínimo es r=0, el problema tiene una solución factible y pasamos a la

fase II: las variables artificiales han servido ahora a su propósito y deben
eliminarse en todos los cálculos subsiguientes. Esto quiere decir que las
ecuaciones de la tabla óptima en la fase I se pueden escribir como:
1 3
x1  x3 
5 5
3 6
x 2  x3 
5 5
x 3  S1  1

Estas ecuaciones son exactamente equivalentes a las de la forma estándar del

problema original (antes de que se sumen las variables artificiales). Por lo tanto,
el problema original se puede escribir como:
Minimizar z  4 x1  x 2
sujeto a
1 3
x1  x3 
5 5
3 6
x 2  x3 
5 5
x 3  S1  1
x1 , x 2 , x3 , S1  0

61
Para resolver el problema, necesitamos sustituir las variables básicas x1 y x2 en la
función objetivo como se hizo en la técnica M. Usando las ecuaciones de las
restricciones entonces resulta:
3 1 6 3 1 18
z  4 x1  x2  4(  x3 )  (  x3 )   x3 
5 5 5 5 5 5

Por lo tanto, la tabla inicial para la fase II se convierte en

Básica x1 x2 x3 S1 Solución
Z 0 0 1/5 0 18/5
x1 1 0 1/5 0 3/5
x2 0 1 -3/5 0 6/5
S1 0 0 1 1 1

La tabla no es óptima ya que x3 debe entrar en la solución. Así la tabla óptima se

obtiene en otra iteración y está dada por.

Básica x1 x2 x3 S1 Solución
z 0 0 0 -1/5 17/5
x1 1 0 0 -1/5 2/5
x2 0 1 0 3/5 9/5
x3 0 0 1 1 1

Por lo que la solución óptima es:

2 9 17
x1  , x2  y z
5 5 5

62