Lección 2

PROGRAMACIÓN
LINEAL

2.1. Introducción

Abordaremos ahora un caso particular de problemas de optimización: aque-

llos en los que tanto la función objetiva como las restricciones son lineales.

El caso lineal presenta una serie de propiedades y una geometrı́a particular

del problema, que nos permite encontrar formas eficientes de encontrar una
solución. Las formas particulares de estos problemas de optimización lineal
se agrupan bajo el nombre general de programación lineal. Los problemas de
programación lineal son un caso particular de los problemas de programación no
lineal, pero debido a su particular estrucura, son más sencillos en su resolución.

Además hay muchas situaciones de la realidad en las empresas de produc-

ción y de servicios que se pueden modelar con las herramientas de optimización
o programación lineal.

45
46 LECCIÓN 2. PROGRAMACIÓN LINEAL

2.2. Un primer ejemplo ilustrativo

Retomaremos la idea de los modelos, como representaciones formales de una

realidad empresarial o institucional que se desea abordar. Las variables, los
modelos y la función objetiva son los tres elementos esenciales que conforman
los problemas de investigación de operaciones. De hecho hemos comenzado estas
reflexiones sobre optimización e investigación de operaciones con una discusión
de un modelo de optimización del bien común y otro correspondiente al bien
mayor. Sin embargo conviene revisar la realización de modelos para el caso de
optimización lineal, ya que los mismos resultan muy frecuentes. Proveemos un
modelo de ejemplo, que nos servirá para ilustrar los modelos más generales y
el significado de algunos resultados.

Supongamos que tenemos una situación de producción que se encuentra

organizada en dos estaciones de trabajo. En la primera de ellas se manufac-
tura el producto A en cantidades x1 y en la segunda estación de trabajo se
manufactura el producto B en cantidades x2 .

De esta manera, hemos identificado los primeros elementos para la confor-

mación del modelo: las variables de decisión x1 y x2 .

Para manufacturar el producto A se requiere de mano de obra y de madera

(supongamos, por ejemplo, que se trata de fabricar mesas y sillas de madera).
Para manufacturar una mesa, por ejemplo, supongamos que se requieren de 10
kg de madera y para una silla 5 kg de madera. Entonces podemos definir los
coeficientes tecnológicos o productividades inversas para las mesas y las sillas
de la siguiente manera:

a11 = cantidad del recurso 1 (madera) para producir una mesa =

kg
= 10
mesa
a12 = cantidad del recurso 1 (madera) para producir una silla =

kg
=5
silla
2.2. UN PRIMER EJEMPLO ILUSTRATIVO 47

De igual forma podemos hacer con la cantidad de horas hombre requeridas, de

modo que tendremos, por ejemplo:

a21 = cantidad del recurso 2 (horas hombre) para producir una mesa =

hh.
=8
mesa
a22 = cantidad del recurso 2 (horas hombre) para producir una silla =
hh.
=6
silla

Supongamos que nuestro horizonte de planificación es de una semana, y

que en ese tiempo las personas que colaboran con este sistema de producción
pueden disponer un total b1 = 200 kg de madera para esta tarea. También
supongamos que el total de horas hombres disponibles para este trabajo es de
b2 = 100 hh. en el horizonte de planificación.

Los coeficientes aij entonces representan, para este caso:

cantidad necesaria del recurso i

aij = ,
para producir una unidad del producto j

i = 1, 2, . . . , m, j = 1, 2, . . . , n

Por su parte bi , i = 1, 2, . . . , m representa la disponibilidad total, sobre el

horizonte de planificación, del recurso i.

Modelo del sistema de producción

Para el caso que estamos analizando, podemos usar una desigualdad con-
ceptual básica:

La cantidad de recursos que empleamos debe ser menor o igual a la cantidad

de recursos que disponemos.

Por lo tanto, la cantidad de madera que usamos para producir mesas y

sillas debe ser menor o igual que la cantidad de madera que disponemos (en el
horizonte de planificación).
48 LECCIÓN 2. PROGRAMACIÓN LINEAL

Como a11 es la cantidad de madera que usamos para manufacturar una mesa
y x1 es la cantidad (aún desconocida) de mesas que construimos, la cantidad de
madera que empleamos para hacer x1 mesas será a11 x1 . Igualmente la cantidad
de madera que empleamos para hacer x2 sillas será a12 x2 . La cantidad total de
madera que empleamos para hacer mesas y sillas, será entonces:
[kg de madera] [kg de madera]
a11 x1 [mesas] + a12 x2 [sillas]
[mesa] [silla]

Hemos resaltado en paréntesis cuadrados las unidades para asegurarnos que

esta primera ecuación tiene unidad resultante en [kg de madera].

Conforme a la desigualdad conceptual, debemos emplear una cantidad me-

nor o igual a la madera disponible, de modo que:

a11 x1 [kg de madera] + a12 x2 [kg de madera] ≤ b1 [kg de madera]

Omitiendo ahora las unidades y representando las horas que nuestros cola-
boradores dedican a la producción (el lector puede verificar que las unidades del
lado izquierdo y derecho de la desigualdad correspondientes a las horas hom-
bre disponibles en el horizonte de planificación son iguales), y completando el
modelo, tendremos:
a11 x1 + a12 x2 ≤ b1
a21 x1 + a22 x2 ≤ b2

Sabemos que, por otro lado, tenemos la función objetiva, que nos permite
representar cuál es, precisamente, el objetivo que queremos cumplir: maximizar
las ganancias, reducir los costos, maximizar el bién común, lograr la mayor
producción total de bien posible, etc... Tı́picamente esta función objetiva se
representa, para el caso de dos variables que estamos considerando, como

y = c1 x1 + c2 x2

donde c1 y c2 son los denominados costos unitarios y pueden representar varias

cosas: a) el resultado económico de la comercialización de cada producto, por
unidad, b) el costo en el que se incurre en la producción, c) la cantidad de
bienes que se produce, etc.. Generalmente tienen una unidad económica, tales
como pesos por silla, o pesos por mesa, etc.
2.2. UN PRIMER EJEMPLO ILUSTRATIVO 49

El problema, para este caso, ahora puede representarse como:

máx y = c1 x1 + c2 x2
s. a
a11 x1 + a12 x2 ≤ b1
a21 x1 + a22 x2 ≤ b2

x1 ≥ 0, x2 ≥ 0
Formas Canónicas

Podemos extender esta formulación para obtener la forma canónica o ge-

neral de los problemas de optimización o programación lineal como:

máx y = c1 x1 + c2 x2 + · · · + cj xj + · · · + cn xn
s.a
a11 x1 + a12 x2 + · · · + a1j xj + . . . a1n xn ≤ b1
a21 x1 + a22 x2 + · · · + a2j xj + . . . a2n xn ≤ b2
...
ai1 x1 + ai2 x2 + · · · + aij xj + . . . ain xn ≤ bi
...
am1 x1 + am2 x2 + · · · + amj xj + . . . amn xn ≤ bm
con xi ≥ 0, i = 1, 2, . . . , n.

Conviente también usar una notación más compacta para representar este
sistema, dando lugar a otras formas canónicas que también usaremos ocasio-
nalmente.

n
X
máx y = ci x i
i=1
s.a
n
X
aij xj ≤ bi i = 1, 2, . . . , m
j=1

xi ≥ 0, i = 1, 2, . . . , n y donde ci son los beneficios unitarios (pesos ganados

por unidad de silla y por unidad de mesa, por ejemplo).
50 LECCIÓN 2. PROGRAMACIÓN LINEAL

También emplearemos una forma aún más sintética:

Definimos A ∈ Rm×n :

 
a11 a12 ... a1j ... a1n
 a21 a22 ... a2j ... a2n 
 
 ... 
A=
 ai1

 ai2 ... aij ... ain 

 ... 
am1 am2 ... amj ... amn

También definimos x ∈ Rn , xi ≥ 0, i = 1, 2, . . . , n, y adicionalmente: c ∈ Rn

y b ∈ Rm , bi ≥ 0, i = 1, 2, . . . , m, todo de la siguiente manera:

el vector x de variables de decisión:

 
x1
 x2 
 
. . . 
x=
 xi 

 
. . . 
xn

el vector c de costos de la función objetiva:

 
c1
 c2 
 
. . .
c=
 ci 

 
. . .
cn

el vector b = P0 de disponibilidades (o lado derecho de las restricciones)

2.2. UN PRIMER EJEMPLO ILUSTRATIVO 51

 
b1
 b2 
 
. . .
b = P0 = 
 bi 

 
. . .
bm

los vectores columnas Pj de coeficientes tecnológicos de la matriz A:

 
a1j
 a2j 
 
 ... 
Pj = 
  j = 1, 2, ..., n
 aij 

 ... 
amj

Con estas definiciones, podemos escribir el problema de programación lineal

como o bien una función objetiva con las restricciones expresadas como:

una combinación lineal de las columnas de la matriz de coeficientes tec-

nológicos A:
máx cT x
Pn s.a
j=1 P j x j ≤ b = P0 , x ≥ 0
.

Presentaremos ahora un ejemplo que tomaremos de base para ilustrar al-

gunas de estas formas canónicas y al que volveremos para comprender mejor
algunos conceptos. Consideremos el problema:
máx y = 3x1 + 5x2
s.a
2x1 + x2 ≤ 2
x1 + 2x2 ≤ 2
El mismo problema, escrito en la forma canónica anterior, se escribe como:
 

x1
máx 2 1
x2
52 LECCIÓN 2. PROGRAMACIÓN LINEAL

s. a
     
2 1 2
x1 + x2 ≤ , x1 ≥ 0, x2 ≥ 0
1 2 2

o, más sucintamente como:

máx cT x
s.a
Ax ≤ b, x ≥ 0

. En el ejemplo anterior:  

x1
máx 2 1
x2
s. a
    
2 1 x1 2
≤ , x1 ≥ 0, x2 ≥ 0
1 2 x2 2

Alternaremos entre una y otra forma o introduciremos nuevas formas gene-

rales según convenga para facilitar la comprensión.

Variables de relleno

A los efectos de nuestro trabajo, necesitamos definir las denominadas va-

riables de relleno, que identificaremos con la designación si , i = 1, 2, . . . , m.
Conceptualmente representan las cantidades que le hacen falta al lado izquier-
do para ser igual al lado derecho de las desigualdades. También se pueden
pensar como la cantidad de recursos disponibles que no se emplean en la pro-
ducción. Como, lógicamente, la cantidad total de recursosP disponible es igual
n
a la cantidad de recursos que se usan (representados por j=1 aij xj) más la
cantidad de recursos disponibles, pero que no se usan (representados por si )
deben igualar a la cantidad de recursos disponibles totales: bi .

Ası́, empleando las variables de relleno, podemos escribir el problema en

forma canónica como:

n
X
máx y = ci xi
i=1
2.2. UN PRIMER EJEMPLO ILUSTRATIVO 53

s.a
n
X
aij xj + si = bi i = 1, 2, . . . , m
j=1
xi ≥ 0, i = 1, 2, . . . , n
si ≥ 0, i = 1, 2, . . . , m
Alternativamente, definamos el vector ampliado de decisión incorporando las
variables de relleno si , entonces

   
x1 x1
 x2   x2 
   
. . .  . . . 
   
 xi   xi 
   
. . .  . . . 
x= =
 xn   xn 

   
 s1   xn+1 
   
 s2   xn+2 
   
. . .  . . . 
sm xn+m
El vector de costos de la función objetiva, considerando que los coeficientes de
las variables de relleno no aparecen en la formulación original queda como:

 
c1
 c2 
 
. . .
 
 ci 
 
. . .
c=
 cn 

 
0
 
0
 
. . .
0
Usando notación matricial:
máx cT x
s.a
[A|I]x = b, x ≥ 0
54 LECCIÓN 2. PROGRAMACIÓN LINEAL

, donde I es la matriz identidad enRmxm .

Por ejemplo, en el caso en el que estamos trabajando:

máx y = 3x1 + 5x2

s.a
2x1 + x2 ≤ 2
x1 + 2x2 ≤ 2
Obtenemos, luego de agregar las variables de relleno:
máx y = 3x1 + 5x2 + 0s1 + 0s2
s.a
2x1 + x2 + s1 + 0s2 = 2
x1 + 2x2 + 0s1 + s2 = 2
Entonces:    
x1 x1
x2  x2 
x=  s1  = x3 
  

s2 x4
 
c1
c2 
c= 0


0
 
a11 a12 1 0
[A|I] =
a21 a22 0 1
Es decir, en nuestro ejemplo:
 
x1

x2 
máx 3 5 0 0  
 s1 
s2
s. a
 
  x1  
2 1 1 0 
x2  ≤ 2 , x1 ≥ 0, x2 ≥ 0

1 2 0 1  s1  2
s2
2.2. UN PRIMER EJEMPLO ILUSTRATIVO 55

Luego de haber revisado las distintas formas canónicas que se emplean inter-
cambiablemente para representar el problema, pasemos a realizar una interpre-
tación gráfica.

Interpretación gráfica

Siguiendo con el mismo ejemplo anterior, nos ayudamos con Maxima para
representar la situación. Cargamos la librerı́a para la representación de funcio-
nes implı́citas:

( % i1) load(implicit plot);

( % o1)

C:/maxima-5.44.0/share/maxima/5.44.0/share/contrib/implicit [Link]

Representamos ahora las restricciones:

( % i2) implicit plot ([2*x 1+3*x 2=5, 2*x 1+x 2-2,x 1+2*x 2=2],
[x 1, 0, 2], [x 2, 0, 2]);

done ( % o2)

Notamos que la región factible es la zona marcada en verde. También hemos

marcado en azul las curvas de nivel correspondientes a y = 4, y = 16/3, y = 6
e y = 7. Estos valores son arbitrarios y sirven como ejemplo para representar el
sentido de crecimiento de la función, que está también marcado por la dirección
y el sentido del gradiente, que es ortogonal a las curvas de nivel.

Primera observación: Solución en los vértices

Una primera observación importante que haremos es que, en el caso de

programación lineal, el problema no presenta soluciones posibles en la zona
estrictamente interior de la región factible. En efecto, recordemos que las curvas
de nivel de función objetiva son lı́neas paralelas, en el caso del ejemplo, a la
lı́nea azul. Siempre será posible desplazarse en el sentido de máximo crecimiento
(dirección del gradiente) mientras se permanezca en la zona interior de la región
factible.
56 LECCIÓN 2. PROGRAMACIÓN LINEAL

Figura 2.1: Región factible (sombreada, en verde) y curvas de nivel en las que
el gradiente indica el sentido de crecimiento de la función.

(Un caso extremo es cuando las curvas de nivel de la región factible son
paralelas a una de las restricciones, en cuyo caso todos los puntos de la frontera
que identifica la recta en cuestión son solución y se alcanza el mismo valor de
la función objetiva en cualquiera de los puntos. Pero ése es un caso particular.)

Esta observación, que extendemos inmediatamente a todos los problemas de

optimización o programación lineal, es de la mayor importancia, ya que pasamos
de enfrentar una búsqueda sobre infinitos puntos (todos los que están dentro de
la región factible), a una búsqueda finita: los puntos que son vértices de la región
factible, en nuestro ejemplo: sólo cuatro puntos. Ellos están representados en
la figura con cı́rculos azules. Por buenos motivos, que veremos más adelante,
2.2. UN PRIMER EJEMPLO ILUSTRATIVO 57

Figura 2.2: Identificación de los extremos factibles y no factibles

también hemos identificado dos puntos adicionales, marcados en rojo.

Ası́, una primera forma elemental de encontrar la solución, es hallar el valor

de función objetiva en cada punto y luego seleccionar el que se corresponda con
un mayor valor de la misma.

En efecto, hemos identificado los puntos como:

(1) Es el punto de intersección de las dos restricciones: nos ayudamos con

Maxima para encontrarlo:

( % i1) solve([x 1+2*x 2=2,2*x 1+x 2=2],[x 1,x 2]);

2 2
[[x1 = , x2 = ]] ( % o1)
3 3

Evaluamos la función objetiva en este punto:

58 LECCIÓN 2. PROGRAMACIÓN LINEAL

( % i2) at(3*x 1+5*x 2,[x 1=2/3,x 2=2/3]);

16
( % o2)
3

De este modo: x1 = (x11 , x12 ) = ( 32 , 23 ) y f (x1 ) = f ( 23 , 32 ) = 3. 32 + 5. 23 = 16

3

(3) x3 = (x31 , x32 ) = (1, 0) y f (x3 ) = f (1, 0) = 3 × 1 + 5 × 0 = 3

Hacemos los mismo con los puntos restantes y obtenemos:

(4) x4 = (x41 , x42 ) = (0, 1) y f (x4 ) = f (0, 1) = 3 × 0 + 5 × 1 = 5

(6) x6 = (x61 , x62 ) = (0, 0) y f (x6 ) = f (0, 0) = 3 × 0 + 5 × 0 = 0

Como f (x1 ) = 163 es el mayor valor de la función objetiva, hemos encontrado

la solución del problema en el punto x0 = x1 = ( 23 , 32 ).

(Los puntos (2) y (5), los veremos más adelante.)

Capitalizaremos esta simple idea para desarrollar un método de solución.

Segunda observación

El método anterior nos ofrece una forma de hallar la solución para un caso
simple en R2 . Sin embargo, en general, trabajaremos con muchas más dimen-
siones. Incluso en R3 la idea de un vértice es más compleja. Podemos darnos
cuenta tal vez en R3 en las que las aristas de la región factible serán planos y
los vértices los puntos de intersección de esos planos.

Sin embargo, necesitamos una alternativa analı́tica a la interpretación geométi-

ca para la localización de los vértices en Rn .

Para ello avanzaremos hacia el concepto de soluciones factibles básicas.

Volvamos a nuestro problema ejemplo:

2.2. UN PRIMER EJEMPLO ILUSTRATIVO 59

máx y = 3x1 + 5x2

s.a
2x1 + x2 ≤ 2
x1 + 2x2 ≤ 2

Trabajaremos con las restricciones, agregando primero las variables de re-

lleno o de slack.

2x1 + x2 + s1 + 0.s2 = 2
x1 + 2x2 + 0.s1 + s2 = 2

Ası́ escrito, se trata de un sistema de dos ecuaciones con cuatro incógnitas:

x1 , x2 , s1 y s2 .

Como hemos visto, también podemos escribirlo de la siguiente forma:

         
2 1 1 0 2
x + x + s + s =
1 1 2 2 0 1 1 2 2

Ahora tenemos esta nueva representación, en la que podemos interpretar que

el vector lado derecho se escribe como una combinación lineal de 4 vectores,
siendo x1 , x2 , s1 y s2 como coeficientes de la combinación lineal. En este caso
los vectores tienen dos dimensiones, es decir que ∈ R2 y estamos empleando
cuatro vectores de R2 para escribir otro vector de R2 . Sin embargo, sabemos
de álgebra, que para escribir cualquier vector de R2 bastan sólo dos vectores
 de

2
R2 linealmente independientes. Por lo tanto la representación del vector
2
no es una representación básica.
 
2
Si buscamos representaciones básicas del lado derecho , entonces ten-
2
dremos
   como opción
  emplear
 las diferentes combinaciones de los cuatro vectores
2 1 1 0
, , , .
1 2 0 1

Denominemos a los vectores en cuestión de la siguiente forma:

60 LECCIÓN 2. PROGRAMACIÓN LINEAL

         
2 1 1 0 2
P1 = , P2 = , P3 = , P4 = y P0 =
1 2 0 1 2

Entonces podemos escribir, con un poco más de generalidad:

P1 x1 + P2 x2 + P3 s1 + P4 s2 = P0

Nota: ocasionalmente identificaremos x3 = s1 y x4 = s2 .

Encontrando soluciones factibles básicas

Consideremos la combinación lineal no básica anterior, de cuatro vectores

de R2 cuya combinación lineal resulta en P0 .

Si pretendemos encontrar combinaciones lineales básicas de dos vectores

usando los cuatro vectores anteriores, tendemos seis posibilidades:

1) P1 y P2 , que equivale a hacer s1 = 0 y s2 = 0.

2) P1 y P3 , que equivale a hacer x2 = 0 y s2 = 0.

3) P1 y P4 , que equivale a hacer x2 = 0 y s1 = 0.

4) P2 y P3 , que equivale a hacer x1 = 0 y s2 = 0.

5) P2 y P4 , que equivale a hacer x1 = 0 y s1 = 0.

6) P3 y P4 , que equivale a hacer x1 = 0 y x2 = 0.

Analicemos las soluciones en cada caso:

1) P1 y P2 , que equivale a hacer s1 = 0 y s2 = 0.

     
2 1 2
x + x =
1 1 2 2 2

Esta solución básica identifica al punto x1 = ( 23 , 23 ), que es un vértice de

2.2. UN PRIMER EJEMPLO ILUSTRATIVO 61

la región factible, tal como lo vemos en la figura que identifica los extremos
factibles y no factibles. Esta solución es factible (cumple con las restricciones)
y es básica (utiliza sólo dos vectores linealmente independientes para escribir
un vector de R2 ). En este punto f (x1 ) = 16 3 .

2) P1 y P3 , que equivale a hacer x2 = 0 y s2 = 0.

     
2 1 2
x1 + s1 =
1 0 2

La solución en este caso es x1 = 2, s1 = −2, y además hemos forzado

x2 = 0 y s2 = 0 para que la solución sea básica. Identifica al punto 2 en la
figura. Notamos dos cosas: por un lado vemos que el punto (x1 = 2, x2 = 0) no
es un punto factible.

También notamos que tenemos una solución con valores negativos: s1 = −2.
Este valor negativo funciona como una tarjeta roja, que nos avisa que este punto
no debe ser considerado. Vemos en la figura que este punto de intersección entre
una recta de la región factible y el x1 , efectivamente no es factible. La solución
negativa es una señal de no factibilidad.

3) P1 y P4 , que equivale a hacer x2 = 0 y s1 = 0.

     
2 0 2
x1 + s2 =
1 1 2

La solución ahora es x1 = 1 y s1 = 1. Como hemos forzado x2 = 0 y

s1 = 0, estamos identificando al punto 3 de la figura que identifica los puntos
correspondientes, x3 = (1, 0). Vemos que la solución es factible y básica. En
este punto f (x3 ) = 3.

4) P2 y P3 , que equivale a hacer x1 = 0 y s2 = 0.

     
1 1 2
x + s =
2 2 0 1 2

La solución ahora es x2 = 1 y s1 = 1. Como hemos hecho x1 = 0 (y s2 = 0),

62 LECCIÓN 2. PROGRAMACIÓN LINEAL

vemos que identificamos el punto 4 de la figura 2. Esta solución es factible y es

básica. En este punto f (x4 ) = 5.

5) P2 y P4 , que equivale a hacer x1 = 0 y s1 = 0.

     
1 0 2
x2 + s2 =
2 1 2

La solución ahora es x2 = 2 y s2 = −1. Nuevamente una solución negativa

obra como una tarjeta roja que nos dice que el punto no es factible. Como
hemos forzado x1 = 0 (junto con s1 = 0), vemos que identificamos al punto 5
de la figura 2, que no es factible.

6) P3 y P4 , que equivale a hacer x1 = 0 y x2 = 0.

     
1 0 2
s + s =
0 1 1 2 2

Finalmente la solución ahora es s1 = 2 y s2 = 2. Aparte hemos hecho x1 = 0

y x2 = 0. Vemos que la solución también es factible y básica. Además es la que
más usaremos, por su sencillez, para comenzar con el algoritmo de solución de
problemas lineales. Identifica al punto 6 en la figura 2. En este punto f (x6 ) = 0.

Cambio de base como cambio de vértice

Hemos visto que cada solución factible básica representa un vértice del
polı́gono de soluciones factibles y que, además, las soluciones básicas que no
son factibles, quedan identificadas por tener al menos una variable negativa (de
las variables principales o de las variables de relleno).

Un método posible para buscar la solución serı́a el siguiente:

a) Comenzar de una solución factible básica fácil de identificar: el punto

(6), el origen de coordenadas, es el mejor candidato. Conceptualmente equivale
a tomar una primera decisión en la que todo lo disponible no se usa: es decir
que las variables de relleno son iguales a las disponibilidades.

b) Movernos de ese primer vértice a otro vértice donde la solución mejore.

Por ejemplo, podemos movernos del punto (6) al punto (3) o al punto (4). En
2.2. UN PRIMER EJEMPLO ILUSTRATIVO 63

el punto (3), a función objetiva vale f (x3 ) = 3 y, en el punto (4), f (x4 ) = 5,

con lo cual lo natural serı́a moverse del punto (6) al punto (4). En la figura 3
se ilustra este movimiento.

Figura 2.3: Cambio de vértice en programación lineal

Ahora bien, el punto (6) se obtiene de la solución de:

P3 s1 + P4 s2 = P0

es decir:      
1 0 2
s + s =
0 1 1 2 2

Mientras que el punto (4) se obtiene de la solución de:

P3 s1 + P2 x2 = P0
64 LECCIÓN 2. PROGRAMACIÓN LINEAL

es decir:      
1 1 2
s1 + x2 =
0 2 2

Por lo tanto, para pasar del punto (6) al punto (4), debemos
  hacer un cambio
0
en la base: sacar de la solución factible básica a P4 = y hacer entrar en la
  1
1
misma a P2 = . Antes de ver los detalles de cómo se realiza el cambio de
2
base, veamos la siguiente notación:

Sea B el conjunto de subı́ndices de vectores que están en la base. Entonces,

para el punto (6), tendremos que B6 = {3, 4}, mientras que para el punto (4),
tendremos que B4 = {2, 3}.

Usando esta notación, también podemos escribir que la solución factible

básica correspondiente al punto (6) es:

X
Pi x i = P0
i∈B6

Acá xi+m = si , por ejemplo, en nuestro caso: m = 2 =⇒ x3 = s1 y

x4 = s2 .

Por su parte, el punto (4) queda identificado por:

X
Pi x i = P0
i∈B4

Y, en general, cualquier solución factible básica podrá representarse por

X
Pi x i = P0
i∈B

Hemos ilustrado entonces que cambiar el vértice correspondiente al punto

2.2. UN PRIMER EJEMPLO ILUSTRATIVO 65

(6) para llegar al punto (4) es equivalente a cambiar de base B6 → B4 , lo que

equivale a retirar a P4 de la base y hacer ingresar a P2 a la misma.

También hemos mostrado que podemos pasar del punto (6) al punto (4),
pero también podrı́amos haber pasado el punto (3). No lo hemos hecho, porque
la función objetiva mejora más al pasar de (6) a (4) que de (6) a (3).

También, siguiendo la dirección del cambio de (6) a (4), podrı́amos haber

avanzado hacia el punto (5), pero no lo hacemos ya que el punto (5) se muestra
como no factible.

Criterios para el cambio de base e introducción al Simplex

Podemos resumir ahora nuestra idea: comenzando de un punto inicial (gene-

ralamente el origen), necesitamos, a los efectos de mejorar la función objetiva,
cambiar de vértice, lo que es equivalente a cambiar de base. Para cambiar de
base necesitamos dos criterios:

a) Criterio para elegir el vector que entra en la base: aquel que produce el
mayor cambio en la función objetiva.

b) Criterio para elegir el vector que sale de la base: aquel que asegura que
el nuevo vértice es factible.

Desarrollaremos, en el punto que sigue, el Método Simplex , que no es más

que un algoritmo iterativo para encontrar una sucesión de soluciones factibles
(eligiendo adecuadamente el vector que sale de la base) y que produzcan, en
cada iteración, el mayor cambio en la función objetiva.

Antes de hacerlo, ilustraremos cómo realizamos un cambio de base en el

ejemplo anterior, para luego generalizarlo en el Simplex.

Ejemplo de cambio de base

La solución inicial se representa como:

P3 x 3 + P 4 x 4 = P0
66 LECCIÓN 2. PROGRAMACIÓN LINEAL

El cambio de base que produce la mayor mejora se produce con el ingreso

de P2 . En efecto, como y = 3x1 + 5x2 , incorporar a P2 en la base, hace que
x2 6= 0, con lo cual logramos un mayor cambio en la función objetiva que se
incorporáramos a P1 (y por lo tanto x1 6= 0, mientras que x2 = 0). Como
P3 y P4 forman una base para R2 , entonces, es posible encontrar un par de
coeficientes α32 y α42 , tales que

P2 = α32 P3 + α42 P4 ⇒ P2 − α32 P3 − α42 P4 = 0

⇒ θ(P2 − α32 P3 − α42 P4 ) = 0, con θ ≥ 0

Por su parte, como

P3 x3 + P4 x4 = P0
Entonces:
P3 x3 + P4 x4 + θ(P2 − α32 P3 − α42 P4 ) = P0
Es decir que:
P3 (x3 − θα32 ) + P4 (x4 − θα42 ) + θP2 = P0
   
1 0
Ahora bien, como P3 = y P4 = forman una base ortonormal
0 1
(ortogonales y de módulo unitario), entonces es evidente que de:
     
1 0 b
P3 x3 + P4 x4 = x + x = 1 = P0
0 3 1 4 b2
se desprende que x3 = b1 y x4 = b2 .

Además, también resulta que:

     
1 0 a12
α32 P3 + α42 P4 = α32 + α42 = P2 =
0 1 a22
de allı́ se desprende que α32 = a12 y α42 = a22 .

Reemplazando obtenemos:

P3 (b1 − θa12 ) + P4 (b2 − θa22 ) + θP2 = P0

2.2. UN PRIMER EJEMPLO ILUSTRATIVO 67

Esta es una combinación lineal de 3 vectores de R2 que da como resultado

otro vector de R2 , es decir es una combinación lineal no básica. Nuestra inten-
ción es hacer ingresar a P2 , porque hemos visto que esto da la mayor mejora a
la función objetiva, y sacar de la base a P4 , es decir, debemos hacer:
b2
b2 − θa22 = 0 ⇒ θ1 =
a22
con lo cual:
b2 b2
P3 (b1 − θ1 a12 ) + θ1 P2 = P3 (b1 − a12 ) + P2 = P0
a22 a22

En nuestro caso, como b1 = 2, b2 = 2, a12 = 1 y a22 = 2, obtenemos:

2 2
P3 (2 − ) + P2 = P3 + P2 = P0
2 2
concluimos que la nueva solución es:

x1 = 0, x2 = 1, x3 = s1 = 1 y x4 = s2 = 0

Que es precisamente el punto (4).

Nota

Si hubiéramos querido hacer salir de la base a P3 , entonces en la ecuación

P3 (b1 − θa12 ) + P4 (b2 − θa22 ) + θP2 = P0

deberı́amos hacer hecho:

b1
b1 − θa12 = 0 ⇒ θ2 =
a12

Pero entonces:
68 LECCIÓN 2. PROGRAMACIÓN LINEAL

b1 b1
P4 (b2 − θ2 a22 ) + θ2 P2 = P4 (b2 − a22 ) + P2 = P0
a12 a12

Pero como b1 = 2, b2 = 2, a12 = 1 y a22 = 2, resulta:

b1 b1 2 2
P4 (b2 − a22 ) + P2 = P4 (2 − 2) + P2 = P4 (−2) + 2P2 = P0
a12 a12 1 1

Al tener un coeficiente negativo, esta solución debe descartarse. Por su

parte, notemos que:

b2 2 b1 2
θ1 = = = 1, θ2 = = = 2 ⇒ θ1 < θ2
a22 2 a12 1

Con lo cual, como regla general para la selección del vector que sale de la
base, se deberá elegir:

bi
θ = mı́n
aij
donde j es el subı́ndice del vector que entre en la base, j = 2 en nuestro caso.
Esta condición es el criterio para seleccionar el vector que sale de base.

Por su parte, el criterio para elegir el vector que entra en la base es selec-
cionar el que produce el mayor cambio en la función objetiva. Como
n
X
y= ci xi
i=0

y xi es el coeficiente del vector Pi en la combinación lineal básica, deberá

elegirse el vector Pj que se corresponda con el máximo coeficiente ci de xj en
la función objetiva.

Como regla general, entonces el criterio para la selección del vector que
entra en la base es seleccionar:
2.3. EL MÉTODO SIMPLEX 69

Pj | cj es el mayor coeficiente de xj en la función objetiva

Con estos elementos podemos pasar ahora a desarrollar la formalización de
estos resultados en el denominado Método Simplex, que nos permite, en forma
iterativa:

1) Seleccionar el vector que entra en la base (aquel que produce el máximo

cambio de la función objetiva).

2) Seleccionar el vector que sale de la base (aquel que hace que el movimiento
hacia el vértice elegido no nos produzca una solucción no factible).

3) Encontrar la solución que se corresponde con el nuevo vértice (los valores

de las variables primales xi y de las variables de relleno si ).

4) Saber si se ha alcanzado la solución o si se debe continuar.

2.3. El método Simplex

Con la comprensión intuitiva de los puntos principales en los que consis-

ten las ideas detrás del método Simplex, podemos generalizar lo discutido en
el punto anterior para dar una explicación un tanto más general, aunque lo
sustancial está ya establecido.

Consideremos el problema general de programación lineal:

máx y = c1 x1 + c2 x2 + · · · + cj xj + · · · + cn xn
s.a
a11 x1 + a12 x2 + · · · + a1j x1j + . . . a1n xn ≤ b1
a21 x1 + a22 x2 + · · · + a2j x2j + . . . a2n xn ≤ b2
...
ai1 x1 + ai2 x2 + · · · + aij xij + . . . ain xn ≤ bj
...
am1 x1 + am2 x2 + · · · + amj xmj + . . . amn xn ≤ bm
xi ≥ 0, i = 1,2. . . . , n
70 LECCIÓN 2. PROGRAMACIÓN LINEAL

Completemos el problema con variables de relleno:

máx y = c1 x1 + c2 x2 + · · · + cj xj + · · · + cn xn
s.a
a11 x1 + a12 x2 + · · · + a1j xij + . . . a1n xn + s1 + 0s2 + · · · + 0sm = b1
a21 x1 + a22 x2 + · · · + a2j x2j + . . . a2n xn + 0s1 + s2 + · · · + 0sm = b2
...
ai1 x1 + ai2 x2 + · · · + aij xij + . . . ain xn + 0s1 + 0s2 + · · · + sj + 0sm = bj
...
am1 x1 + am2 x2 + · · · + amj xmj + . . . amn xn + 0s1 + 0s2 + · · · + sm = bm
xi ≥ 0, si ≥ 0, i = 1,2. . . . , n
Definiendo los vectores Pj ∈ Rm j = 1, 2, . . . , n + m tales que.

 
a1j
 a2j 
 
 ... 
Pj = 
  , j = 1, 2, . . . n
 aij 

 ... 
amj

 
0
0
 
. . . 
Pj = 
 1k  , j = n + 1, n + 2, . . . , n + m

 
. . . 
0

(donde el 1k representa un 1 que se encuentra en la fila k del vector Pn+k ),

entonces el problema puede escribirse como:

n
X
máx y = ci xi
i=1
2.3. EL MÉTODO SIMPLEX 71

s.a
n+m
X
Pj xj = P0
j=1

Notemos que los últimos m vectores de la suma anterior forman una base
ortonormal.

Sabemos, de nuestra discusión anterior, que la solución del problema lineal

se encuentra en los vértices de la región factible y que los mismos se localizan
como combinaciones lineales factibles básicas de los vectores Pj que aparecen
en la ecuación anterior.

Base inicial

En el Método Simplex para el tipo de problemas que estamos planteando

(otros casos serán reducidos a esta forma general), comenzamos siempre toman-
do al origen como solución, es decir haciendo x1 = 0, x2 = 0. . . . , xn = 0. Esta
selección de variables produce una solución factible básica en forma inmediata,
ya que quedan en la base los m vectores Pj , j = n + 1, n + 2, . . . , n + m, y la
solución entonces es si = bi , i = 1, 2, . . . , m.

Expresado en forma matricial, para mayor claridad de cómo se obtiene la

solución, tendremos:

 
s1




 s2
Pn+1 | Pn+2 | . . . | Pn+m−1 | Pn+m 

 = P0
 ...
sm−1 
sm
    
1 0 ...0 0 s1 b1
 0 1 ...0 0
  s2   b2 
   

⇒
. . . ... ...0 0  . . .  =  . . . 
   

 0 0 ...1 0 sm−1  bm−1 
0 0 ...0 1 sm bm

De lo que se deduce que:

72 LECCIÓN 2. PROGRAMACIÓN LINEAL

     
s1 xn+1 b1

 s2 
  xn+2
 
 

 b2

 ...
=
 
=
 ...  = P0
 ...
sm−1  xn+m−1  bm−1 
sm xx+m bm

De lo anterior se desprende, como hemos dicho, que si = bi , i = 1, 2, . . . , m

para esta primer solución inicial, que, además es una solución factible básica, y
representa el origen del primer cuadrante generalizado (la región donde xi ≥ 0).
Como tal se puede representar como la solución de:

X
Pi x i = P0
i∈B

Donde B, como sabemos, es el conjunto de subı́ndices de los vectores que

forman la base de Rm de la solución factible básica.

Cambio de base

Recordemos que deseamos buscar otro vértice para mejorar la función ob-
jetiva. Cambiar de vértice será equivalente a cambiar de base. Para ello nece-
sitamos dos criterios, como hemos visto antes:

a) El criterio de selección del vector que entra en la base.

b) El criterio de selección del vector que sale de la base.

a) Selección del vector que entra en la base

En la solución inicial
Pse ha seleccionado: xi = 0, i = 1, 2, . . . , n. Como la
n
función objetiva es y = i=1 ci xi , resulta, evidentemente, que y = 0 para esta
primer solución factible básica.

Debemos ahora preocuparnos por mejorar la función objetiva.

Al elegir Pj , también haremos xj 6= 0. Resulta evidente entonces que con-

viene elegir el vector Pj tal que el coeficiente de xj sea el mayor en la función
2.3. EL MÉTODO SIMPLEX 73

Pn Pn
objetiva. Como y = i=1 ci xi se suele escribir y − i=1 ci xi = 0, el criterio de
selección del vector que entra en la base se suele indicar como:

Criterio de selección del vector que entra en la base: seleccionar el vector

Pj que
Pentra en la base, tal que se corresponda con el coeficiente más negativo
n
de − i=1 ci xi = 0.

b) Selección del vector que sale de base

Sea Pj el vector que entra en la base. Como Pj ∈ Rm , y como B identifica los

subı́ndices de los vectores que conforman una base para Rm , entonces existen
αij tales que:

X X
Pj = αij Pi ⇒ θ(Pj − αij Pi ) = 0, con θ > 0
i∈B i∈B

Por su parte, como

X
Pi x i = P0
i∈B

entonces:

X X
Pi xi + θ(Pj − αij Pi ) = P0
i∈B i∈B

es decir que:
X
Pi (xi − θαij ) + θPj = P0
i∈B

Ahora bien, como Pi |i ∈ B conforma una base ortonormal, entonces es

evidente que de:
74 LECCIÓN 2. PROGRAMACIÓN LINEAL

 
b1
X  b2 
 . . .  = P0
Pi x i =  
i∈B
bm

se desprende que xi = bi .

Además, también resulta de:


a1j
 a2j 
 
X  ... 
Pj = αij Pi = 
 
aij 
i∈B  
 ... 
amj

que, siendo la base de vectores ortonormales, αij = aij

Reemplazando obtenemos:

X
Pi (bi − θaij ) + θPj = P0
i∈B

Elegimos el vector que sale de base como aquel que tiene el menor cociente

bi br
θr = mı́n{ }=
aij arj

De esta manera tenemos la nueva solución factible básica:

X br
Pi (bi − θr aij ) + Pj = P0
arj
i∈{B−{r}}
2.3. EL MÉTODO SIMPLEX 75

La nueva colección de subı́ndices de vectores que están en la base, resulta

entonces:

B N = B V − {r} + {j}

Criterio de selección del vector que sale de la base (Resumen): seleccionar

el vector Pr que sale en la base, tal que se corresponda con el coeficiente que
tiene menor cociente bi /aij .

Una vez identificados Pr y Pj se emplea eliminación gaussiana para compo-

ner una nueva base ortonormal con los vectores de la solución factible básica y
el procedimiento se repite hasta que no sea posible encontrar otro coeficiente
−cj que tenga signo negativo, de modo que cualquier modificación (cambio de
vértice adicional) sólo empeorarı́a la función objetiva, de modo que el procedi-
miento termina allı́.

Formalización a la manera de una tabla (Tabla del Simplex)

A los efectos de formalizar la resolución del problema siguiente:

máx y = c1 x1 + c2 x2 + · · · + cj xj + · · · + cn xn
s.a
a11 x1 + a12 x2 + · · · + a1j xij + . . . a1n xn + s1 + 0s2 + · · · + 0sm = b1
a21 x1 + a22 x2 + · · · + a2j x2j + . . . a2n xn + 0s1 + s2 + · · · + 0sm = b2
...
ai1 x1 + ai2 x2 + · · · + aij xij + . . . ain xn + 0s1 + 0s2 + · · · + sj + 0sm = bj
...
am1 x1 + am2 x2 + · · · + amj xmj + . . . amn xn + 0s1 + 0s2 + · · · + sm = bm

Considerando que

y − c1 x1 − c2 x2 − · · · − cj xj − · · · − cn xn = 0

se anota en una tabla, tal como se muestra en el cuadro siguiente:

 76
bi
Ec. Bs. y x1 x2 ... xj ... xn s1 s2 ... sm LD aij
0 y 1 −c1 −c2 ... −cj ... −cn 0 0 ... 0 0 -
1 s1 0 a11 a12 ... a1j ... a1n 1 0 ... 0 b1 -
2 s2 0 a21 a22 ... a2j ... a2n 0 1 ... 0 b2 -
... ... ... ... ... ... ... ... ... ... ... ... ... ... -
i si 0 ai1 ai2 ... aij ... ain 0 0 ... 0 bi -
... ... ... ... ... ... ... ... ... ... ... ... ... ... -
m sm 0 am1 am2 ... amj ... amn 0 0 ... 1 bm -

Cuadro 2.1: Tabla inicial del Simplex

LECCIÓN 2. PROGRAMACIÓN LINEAL

2.3. EL MÉTODO SIMPLEX 77

Vemos que no se trata de otra cosa más que de la transcripción ordenada

del problema original, sólo que a la manera de una tabla.

El procedimiento ahora comienza con la selección del vector que entra en la

base. Para ello debemos elegir el coeficiente más negativo de la fila 0, donde se
representan los coeficientes de la función objetiva. Supongamos que el mismo
se corresponde con la columna j. Entonces Pj deberá entrar la base. Marcamos
esa columna.

Para saber cuál es el vector que debe salir en la base, una vez elegido Pj ,
buscamos el menor cociente de bi /aij , ya que, como hemos visto, eso nos asegura
la factibilidad de la nueva solución. Supongamos que se corresponde con la fila
i. Entonces el vector Pi debe entrar en la base. Marcamos esa fila. El elemento
en la fila i seleccionada y en la columna j identificada, se denomina el pivote
de la tabla como O aij .

La nueva solución se encuentra ahora por eliminación gaussiana y la nueva

base se hace ortogonal y normal, de modo que el procedimiento puede repetirse
exactamente igual en la nueva tabla.

Ilustraremos el procedimiento en el siguiente ejemplo.

Ejemplo
máx y = 3x1 + 5x2
s.a
2x1 + x2 ≤ 2
x1 + 2x2 ≤ 2

Que se puede escribir, completando con las variables de relleno, como el

problema de máx y, donde:

y − 3x1 − 5x2 − 0s1 − 0s2 = 0

2x1 + 1x2 + 1s1 + 0s2 = 2
1x1 + 2x2 + 0s1 + 1s2 = 2

Componemos la tabla del Simplex, que no es más que la transcripción del

problema anterior en forma tabular:
78 LECCIÓN 2. PROGRAMACIÓN LINEAL

Ec. Bs. y x1 x2 s1 s2 LD bi /aij

0 y 1 −3 −5 0 0 0 -
1 s1 0 2 1 1 0 2 -
2 s2 0 1 2 0 1 2 -

Cuadro 2.2: Paso 1

Selección de columna: seleccionamos la columna de x2 que tiene el coefi-

ciente más negativo de la función objetiva.

Selección de fila: evaluamos el cociente bi /aij para cada fila y elegimos la

fila con menor cociente:

Ec. Bs. y x1 O
x2 s1 s2 LD bi /aij
0 y 1 −3 −5 0 0 0 -
1 s1 0 2 1 1 0 2 2/1
2 x2 0 1 O2 0 1 2 O
2/2

Cuadro 2.3: Paso 2

Seleccionamos la fila 2 que tiene el menor coeficiente bi /aij y procedemos

ahora a realizar eliminación gaussiana para encontrar la solución. Para ello
hacemos las siguientes operaciones, denominadas de pivote.

1) Dividimos la fila del pivote por el pivote. 2) Encontramos todos los nuevos
valores de la tabla de la siguiente manera:

xk ... xj
A ... B
... ... ...
C ... O
P

Cuadro 2.4: Operación de pivote

0 AP − BC
A =
P
2.3. EL MÉTODO SIMPLEX 79

Realizamos las operaciones en la tabla, para obtener:

Ec. Bs. y x1 x2 s1 s2 LD bi /aij

0 y 1 −1/2 0 0 5/2 5
1 s1 0 3/2 0 1 −1/2 1
2 x2 0 1/2 1 0 1/2 1

Cuadro 2.5: Paso 3

Ahora bien, esta tabla representa el problema de programación lineal si-

guiente:
y − 1/2 x1 + 0x2 + 0s1 + 5/2 s2 = 5
3/2 x1 + 0x2 + 1s1 − 1/2 s2 = 1
1/2 x1 + x2 + 0s1 + 1/2 s2 = 1

Vemos entonces que tenemos otro problema de programación lineal con una
función objetiva cuyo mayor coeficiente es 1/2, de modo que podemos proceder
nuevamente de la misma manera que antes.

Si observamos la tabla, vemos que en la fila 0 correspondiente a la función

objetiva encontramos ese coeficiente negativo en la columna de x1 , que es el
coefciente de P1 . Por lo tanto la función objetiva puede mejorarse, para lo
cual debemos incorporar a P1 (el vector cuyo coeficiente es x1 ) a la base.
Identificamos a la fila 1 como la de menor coeficiente bi /aij y elegimos el pivote.

En el Cuadro 5, correspondiente al Paso 3, también podemos leer que la

solución intermedia es x1 = 0 (ya que no se encuentra entre los coeficientes
de los vectores que están en la base en la columna marcada como Bs.), que
x2 = 1, es decir que se trata del punto cuyas coordenadas son (0, 1), que es,
efectivamente un vértice de la región factible (marcado como el punto (4)) en
el gráfico anterior. En este punto, además, la función objetiva toma el valor
y = 5, cosa que es natural ya que y = 3 × x1 + 5 × x2 = 3 × 0 + 5 × 1 = 5.

En el Cuadro 6, correspondiente al Paso 4, volvemos a seleccionar el pivote,

eligiendo la columna de x1 y la fila correspondiente a s1 . Ahora entra en la
base el vector P1 y sale de la misma el vector P3 (cuyo coeficiente es s1 = x3 ).
El pivote (que hemos marcado en un cı́rculo), es el elemento correspondiente a
la columna de x1 y la fila de s1 .
80 LECCIÓN 2. PROGRAMACIÓN LINEAL

Ec. Bs. y O
x1 x2 s1 s2 LD bi /aij
0 y 1 −1/2 0 0 5/2 5
1 s1 0 O
3/2 0 1 0 1 O
2/3
2 x2 0 1/2 1 0 1/2 1 2

Cuadro 2.6: Paso 4

Volvemos a realizar las operaciones de pivote y ortogonalizar y normalizar

la tabla, como se muestra en el Cuadro 7. Vemos que no hay más coeficientes

Ec. Bs. y x1 x2 s1 s2 LD bi /aij

0 y 1 0 0 1/3 7/3 16/3
1 x1 0 1 0 2/3 −1/3 2/3
2 x2 0 0 1 −1/3 2/3 2/3

Cuadro 2.7: Paso 5

negativos en la fila 0, con lo cual las iteraciones concluyen.

Ahora podemos ver que x1 = 2/3, x2 = 2/3 y que y ∗ = 16/3. Por su

parte s1 = 0 y s2 = 0, de modo que podemos leer toda la solución en la tabla
correspondiente al Cuadro 7. Evidentemente el valor de la función objetiva es
y = 3 × 2/3 + 5 × 2/3 = 6/3 + 10/3 = 16/3.

En realidad las operaciones se hacen en tablas sucesivas, que llevan para

este caso, sólo 3 pasos, como se muestra en el Cuadro 8.

Esto concluye el ejemplo de la manera en que se trabaja con el método

Simplex.

2.4. Empleando LINDO

Hemos visto en los puntos anteriores cómo se pueden resolver los problemas
de programación no lineal usando LINGO. Conviene ahora revisar la aplicación
de un paquete de software que nos ayuda en resolver problemas lineales, cual
2.4. EMPLEANDO LINDO 81

Ec. Bs. y x1 O
x2 s1 s2 LD bi /aij
0 y 1 −3 −5 0 0 0 -
1 s1 0 2 1 1 0 2 2/1
2 x2 0 1 O2 0 1 2 O
2/2
0 y 1 O
−1/2 0 0 5/2 5
1 s1 0 O
3/2 0 1 0 1 O
2/3
2 x2 0 1/2 1 0 1/2 1 2
0 y 1 0 0 1/3 7/3 16/3
1 x1 0 1 0 2/3 −1/3 2/3
2 x2 0 0 1 −1/3 2/3 2/3

Cuadro 2.8: En tres pasos

es LINDO. Si bien LINGO también puede emplearse para problemas lineales,

LINDO proporciona una gran simplicidad en la carga de los problemas y una
fácil interpretación de los resultados.

Lo haremos revisando el ejemplo tratado en los puntos anteriores:

máx y = 3x1 + 5x2

s.a
2x1 + x2 ≤ 2
x1 + 2x2 ≤ 2

El problema se puede cargar en LINDO de la siguiente forma:

max 3 x1 + 5x2
st
2 x1 + x2 < 2
x1 + 2 x2 < 2

En el menú de LINDO, se puede emplear el comando REPORTS > FOR-

MULATION para verificar cómo está interpretando LINDO el problema:

MAX 3 X1 + 5 X2
82 LECCIÓN 2. PROGRAMACIÓN LINEAL

SUBJECT TO
2) 2 X1 + X2 <= 2
3) X1 + 2 X2 <= 2
END

La tabla inicial del Simplex puede verificarse con el comando REPORTS >
TABLEAU:

THE TABLEAU

ROW (BASIS) X1 X2 SLK 2 SLK 3

1 ART -3.000 -5.000 0.000 0.000 0.000
2 SLK 2 2.000 1.000 1.000 0.000 2.000
3 SLK 3 1.000 2.000 0.000 1.000 2.000
ART ART -3.000 -5.000 0.000 0.000 0.000

Podemos compararla con nuestra tabla inicial del Simplex:

Ec. Bs. y x1 x2 s1 s2 LD bi /aij

0 y 1 −3 −5 0 0 0 -
1 s1 0 2 1 1 0 2 -
2 s2 0 1 2 0 1 2 -

Cuadro 2.9: Tabla inicial del Simplex

Si bien LINDO puede resolver el problema directamente, también tenemos

la opción de ir realizando una selección de pivote a la vez y ver cómo evolucionan
los vectores que entran y salen de la base. Con el comando SOLVE > PIVOT,
podemos avanzar un paso en la tabla, para obtener:

X2 ENTERS AT VALUE 1.0000 IN ROW 3 OBJ. VALUE= 5.0000

THE TABLEAU
2.4. EMPLEANDO LINDO 83

ROW (BASIS) X1 X2 SLK 2 SLK 3

1 ART -0.500 0.000 0.000 2.500 5.000
2 SLK 2 1.500 0.000 1.000 -0.500 1.000
3 X2 0.500 1.000 0.000 0.500 1.000

Que comparamos con nuestra tabla luego de la primera selección de pivote:

Ec. Bs. y x1 x2 s1 s2 LD bi /aij

0 y 1 −1/2 0 0 5/2 5
1 s1 0 3/2 0 1 −1/2 1
2 x2 0 1/2 1 0 1/2 1

Cuadro 2.10: Primera iteración

Avanzamos ahora a la segunda iteración, nuevamente con el comando SOL-

VE > PIVOT, para obtener:

X1 ENTERS AT VALUE 0.66667 IN ROW 2 OBJ. VALUE= 5.3333

THE TABLEAU

ROW (BASIS) X1 X2 SLK 2 SLK 3

1 ART 0.000 0.000 0.333 2.333 5.333
2 X1 1.000 0.000 0.667 -0.333 0.667
3 X2 0.000 1.000 -0.333 0.667 0.667

Que comparamos con nuestra propia resolución:

Que encontramos también en total correspondencia con muestro cálculo.

El informe final de LINDO, que se obtiene del comando SOLVE, indica:

LP OPTIMUM FOUND AT STEP 2

84 LECCIÓN 2. PROGRAMACIÓN LINEAL

Ec. Bs. y x1 x2 s1 s2 LD bi /aij

0 y 1 0 0 1/3 7/3 16/3
1 x1 0 1 0 2/3 −1/3 2/3
2 x2 0 0 1 −1/3 2/3 2/3

Cuadro 2.11: Tabla final del Simplex

OBJECTIVE FUNCTION VALUE

1) 5.333333

VARIABLE VALUE REDUCED COST

X1 0.666667 0.000000
X2 0.666667 0.000000

ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 0.333333
3) 0.000000 2.333333

NO. ITERATIONS= 2

Leemos que se requirieron dos iteraciones para resolver el problema, que el

valor óptimo de la función objetiva es y = 5, 333333 = 16/3, que los valores
óptimos de las variables son x1 = 0, 666667 = 2/3, x2 = 0, 666667 = 2/3, que
los valores de las variables de relleno son s1 = 0 y s2 = 0, todo en correspon-
dencia con nuestro cálculo.

El costo reducido (REDUCED COST) nos indica en cuánto se deben au-

mentar los coeficiente de x1 y de x2 para que los vectores P1 y P2 , cuyos
coeficientes son x1 y x2 entren en la base. Como tanto P1 como P2 ya están en
la base, el costo reducido es cero.

Los precios duales (DUAL PRICES) son las variables de sensibilidad de la

2.5. CONCLUSIONES 85

función objetiva a cambios en las disponibilidades y los veremos en el capı́tulo

que sigue.

2.5. Conclusiones

En el presente capı́tulo hemos abordado el importante tema de la opti-

mización lineal bajo la forma especı́fica que los identifica como problemas de
programación lineal y el método Simplex para su resolución. La introducción
se ha llevado adelante a partir de un ejemplo ilustrativo, de modo de poder
comprender las peculiaridades del método. Hemos también mostrado las posi-
bilidades de LINDO para la resolución del problema y avanzar desde allı́ a una
formulación general simplificada. Muchos temas complementarios, pero aún ası́
principales de la programación lineal, no han sido tratados en esta presentación,
en particular los detalles que hacen a los problemas no acotados, por ejemplo,
la resolución de casos con restricciones tipo igualdad y con restricciones mixtas.
Parte de estos aspectos son generalmente abordados en una práctica comple-
mentaria.

En el capı́tulo siguiente estudiaremos dos resultados de la mayor impor-

tancia, de los que ya hemos esbozado sus posibilidades en el caso no lineal: la
dualidad y la sensibilidad en los problemas de optimización que tienen la forma
de la programación lineal.

2.6. Problemas

Problema 1

Hallar la solución en forma gráfica:

86 LECCIÓN 2. PROGRAMACIÓN LINEAL

a)

máx y = x1 + x2
s.a
x1 + 2x2 ≤ 6
2x1 + x2 ≤ 8

b)

máx y = 5x1 + 6x2

s.a
5x1 + 2x2 ≥ 20
3x1 + 8x2 ≥ 24

c)

máx y = 2x1 + 5x2

s.a
x1 − x2 ≥ 3
x1 + x2 ≤ 6
x1 ≤ 2

d)

máx y = 8x1 + 30x2

s.a
10x1 + 12x2 ≥ 60
3x1 − 4x2 ≤ 12
− 3x1 + 2x2 ≤ 30
2.6. PROBLEMAS 87

Problema 2

Dado el siguiente problema:

máx y = x1 + 2x2
s.a
x1 − x2 ≤ 5
3x1 + 4x2 ≤ 12
2x1 + 7x2 ≤ 14

a) Expresar el problema en forma canónica.

b) Encontrar una solución factible básica por el método Simplex.

c) Realizar un cambio de vector de base.

d) Encontrar la solución óptima por el método Simplex.

Problema 3

Resolver por el método Simplex el problema 1 a)

Problema 4

máx y = 5x1 + 3x2

s.a
x1 + x2 ≤ 7
3x1 − 2x2 ≤ 3

Resolver por el método Simple y representar gráficamente.

88 LECCIÓN 2. PROGRAMACIÓN LINEAL

Problema 5

Resolver por el método Simplex:

máx y = x1 + 2x2 + 3x3

s.a
x1 + x3 ≤ 10
x2 + x3 ≤ 10
x1 + x2 ≤ 12

Problema 6

Minimizar gráficamente la función objetivo planteada en el problema 4)

sujeta a idénticas restricciones.

Problema 7

Resolver por el método Simplex:

máx y = −2x1 + 3x2

s.a
2x1 + 3x2 ≤ 2
x1 + 2x2 ≤ 4

Representar gráficamente la región factible, las curvas de nivel de la función

objetivo y la solución del problema.

Problema 8
2.6. PROBLEMAS 89

máx y = 4x1 + 4x2

s.a
− 2x1 + 2x2 ≤ 2
− x1 + 2x2 ≤ 4

Problema 9

máx y = 5x1 + 2x2

s.a
6x1 + 10x2 ≤ 30
10x1 + 4x2 ≤ 20

Problema 10

Resuelva usando Simplex

máx y = 5x
s.a
x≤3

Problema 11

Considere el problema de programación lineal siguiente:

90 LECCIÓN 2. PROGRAMACIÓN LINEAL

máx y = 2x1 + x2
s.a
ax1 + bx2 ≤ 10
a, b ≥ 0
a ≥ 2b

Resuelva usando Simplex.

Problema 12

Una empresa fabrica mesas y sillas, con una capacidad semanal de 100
mesas y 400 sillas. Para hacer una mesa se requieren de 20 kg de madera, 2
kg de caños y 10 piezas de plástico. Para hacer una silla, por su parte, son
necesarios 5 kg de madera, 1 kg de caños y 5 piezas de plástico. El costo de la
madera es de 40 UEC/kg (UEC es la Unidad Económica de Costo que emplea
la empresa), el de los caños de 50 UEC/kg y cada pieza de plástico tiene un
costo de 5 UEC. El precio de venta de las mesas es de 990 UEC y el de las
sillas de 310 UEC. La mano de obra representa un costo fijo y por lo tanto no
se tiene en cuenta en el problema (se dice que el costo está hundido.

1) Encontrar el beneficio unitario neto (precio de venta - costo) de fabricar

mesas y sillas.

2) Representar el problema como uno de programación lineal.

3) Encontrar la cantidad de mesas y sillas a fabricar para maximizar el

beneficio, por medio de la solución gráfica.

4) Corroborar el resultado por Simplex.

Problema 13

Una empresa manufactura puertas y ventanas. Su capacidad está limitada

a que el total de las puertas y ventanas que puede fabricar por semana es de
40. En ese tiempo dispone de 150 hh y 120 kg de material para las puertas y
las ventanas.
2.6. PROBLEMAS 91

Para hacer una puerta hacen falta 5 hh y 1 kg de material, mientras que

para hacer una ventana hacen falta 1 hh y 4 kg de material. Se paga 40 UEC
la hora hombre y el kg de material sale 10 UEC.

1) Calcular el costo de manufacturar 1 puerta y una ventana.

2) Considerando que el precio de venta de la puerta es de 810 UEC y el de

una venta es de 180 UEC, calcular el beneficio que se obtiene por puerta y por
ventana.

3) Plantear un problema de programación lineal para maximizar el beneficio

que se obtiene de producir puertas y ventanas.

4) Resolver gráficamente.

5) Resolver el Simplex y corroborar los resultados obtenidos gráficamente.

Problema 14

Una empresa manufactura camas de una y de dos plazas. El beneficio neto

de las camas de una plaza es de 300 UEC de 40 UEC para las dos plazas.

Para realizar una cama de una plaza, se requieren de 1 hora hombre y tres
horas hombre para las de dos plazas. Para las camas de una plaza se requiere
de 3 kg de madera, pero para las de dos plazas (debido a un diseño especial),
se necesita 1 kg de madera. Se disponen en total de 60 horas hombre y 60 kg
de material por dı́a.

1) Plantear el problema de maximizar el beneficio.

2) Encontrar la solución gráfica.

3) Resolver por Simplex y corroborar el resultado.