CAPÍTULO 1

CONCEPTOS BÁSICOS DE PROGRAMACIÓN LINEAL

1.1 INTRODUCCIÓN
Un problema de programación lineal, también llamado Programa Lineal (PL), consiste en
un criterio lineal a optimizar (maximizar o minimizar), sujeto a un conjunto de restricciones
lineales del tipo ecuaciones o inecuaciones. Es decir
n
max. (o min.) z = ∑cj xj
j =1

sujeto a
( 1-1)
≤ 
n
 
∑=1 aij x j = bi i = 1, 2,  , m
j ≥ 
 
donde los coeficientes cj, aij y bi son números reales. Las variables reales xj son las
variables de decisión del problema. El criterio lineal a optimizar se llama función objetivo,
y, a veces, también función económica.
Usualmente se agrega a las variables la condición de ser no negativas:
xj ≥ 0 , j = 1, 2,  , n ( 1-2)

porque es la forma más conveniente para la resolución numérica, pero además estas
condiciones surgen naturalmente en la mayoría de los problemas de aplicación. De todas
maneras, todo problema que tenga variables no restringidas en signo puede ser fácilmente
transformado en uno con todas la variables no negativas, como veremos más adelante. Las
restricciones y las condiciones de no negatividad de las variables definen el conjunto Ω de
soluciones factibles del PL.
Así un programa lineal queda planteado en su forma general como
n
max. (o min.) z = ∑ cj x j
j =1

 ≤ 
n   ( 1-3)
∑ aij x j =  bi i = 1, 2,  , m
Ω  j =1 ≥ 
  
 xj ≥ 0 j = 1, 2,  , n


P. Lineal 1
 Definición. Llamamos Programación Lineal a las teorías, métodos y algoritmos de
optimización de programas lineales.1

Ejemplo 1-1
Un departamento de una empresa puede fabricar dos productos P1 y P2 que requieren la
utilización de una máquina M y de dos materias primas A y B. La Tabla 1-1 resume los
requerimientos de cada uno de los recursos para producir una unidad de cada tipo de producto,
así como las contribuciones marginales de los productos. Por ejemplo: la producción de una
unidad del producto P1 requiere 1 hora en la máquina M, 2 Kg. de la materia prima A, 9 Kg. de
la materia prima B y tiene una contribución marginal de $ 50. Análogamente para P2.

COSTOS CANTIDAD COSTO CANTIDAD COSTO

UNITARIOS REQUERIDA VARIABLE REQUERIDA VARIABLE
RECURSOS POR P1 DE P1 POR P2 DE P2
Máquina M 100 $/h (*)
1 h/u 100 $/u 2 h/u 200 $/u
Mat. Prima A 50 $/Kg 2 Kg/u 100 $/u 2 Kg/u 100 $/u
Mat. Prima B 10 $/Kg 9 Kg/u 90 $/u 4 Kg/u 40 $/u
COSTO VARIABLE 290 $/u 340 $/u
PRECIO DE VENTA 340 $/u 400 $/u
CONTRIBUCIÓN MARGINAL 50 $/u 60 $/u
(*)
Incluye todo ítem que contribuya al costo variable del producto: mano de obra directa, energía, lubricantes, etc.
Tabla 1-1
Las disponibilidades mensuales de los recursos son las siguientes
Máquina M: 160 h./mes
Materia prima A: 200 Kg./mes
Materia prima B: 720 Kg./mes
Se desean determinar las cantidades a producir mensualmente de los productos P1 y P2 de
manera de maximizar la contribución marginal total.
Si llamamos x1 y x2 a las cantidades a producir de P1 y P2 respectivamente, es fácil ver
que el problema puede plantearse como sigue (verificar la homogeneidad de las unidades).
Maximizar la contribución marginal total: max. z = 50 x1 + 60 x 2
Sujeta a
Restricción debida a la máquina M:  x1 + 2 x 2 ≤ 160
 2 x + 2 x ≤ 200
Restricción debida a la materia prima A:  1
Ω
2

Restricción debida a la materia prima B:  9 x1 + 4 x 2 ≤ 720

Porque no se pueden fabricar cantidades negativas:  x1 , x 2 ≥ 0
Dado que sólo tenemos dos variables podemos hacer una representación gráfica del
problema en el plano (Figura 1-1). La no negatividad de las variables limita las posibles
soluciones al primer cuadrante. Las inecuaciones definen semiplanos que (por ser de ≤)
contienen al origen de coordenadas. Luego el polígono ORSTUO es la región del plano cuyos

1
La Programación Lineal es una de las técnicas de optimización más importantes debido a que muchos
problemas pueden ser planteados como programas lineales, y además porque se dispone de algoritmos que
permiten resolver, con el software y las computadoras actuales, problemas con varios miles de variables y
restricciones. Por otra parte la inclusión de variables de decisión binarias (ver Programación Entera y Mixta)
permite extender su campo de aplicación a una gama muy amplia de problemas de decisión.

2 P. Lineal
puntos satisfacen todas las restricciones, es decir el conjunto de soluciones admisibles Ω. La
solución óptima estará dada por el o los puntos que hagan máxima la función objetivo
z = 50 x1 + 60 x2

Sabemos que para un valor de z fijado, por ejemplo z = z0, es la ecuación de una recta, y
que ese valor de z0 es proporcional a
x2 la distancia de la recta al origen. Para
distintos valores de z se tiene una
180
familia de rectas paralelas (llamadas
rectas de isobeneficio pues todos los
puntos de cada una de ellas dan el
mismo valor de la contribución
marginal total). Para determinar la
dirección de esta familia basta
c determinar la del vector normal a ellas,
100
que es la dirección del vector c de
c2 = 60
80 componentes c1 = 50 y c2 = 60, lo que
R
c1 = 50 facilita la determinación gráfica. El
60 máximo valor de z estará dado por la
S z = cte.
T recta de la familia que esté lo más
alejada del origen y que tenga
O U
intersección no vacía con el conjunto
0 40 80 100 160 x1 de soluciones factibles. Esta recta es
Figura 1-1 claramente la que pasa por el punto S,
luego sus coordenadas son la solución
óptima buscada:
x1* = 40 , x2* = 60
Es evidente que la solución óptima está dada por el vértice intersección de las rectas que
limitan los semiplanos correspondientes a las dos primeras restricciones, y por lo tanto se
puede hallar analíticamente resolviendo el sistema

 x1 + 2 x 2 = 160

 2 x1 + 2 x 2 = 200
Verificación de las restricciones:

40 + 2 × 60 = 160 (el recurso M es utilizado totalmente)

2 × 40 + 2 × 60 = 200 (el recurso A es utilizado totalmente)
9 × 40 + 4 × 60 = 600 < 720 (el recurso B no es utilizado totalmente)

La contribución marginal total en el óptimo es:

z* = 50 × 40 + 60 × 60 = 5.600
Observaciones.

P. Lineal 3
 Este ejemplo permite observar una serie de características de las soluciones del problema
que, como veremos más adelante, son propiedades completamente generales.
a) El conjunto Ω de soluciones admisibles es un polígono convexo.
b) Si Ω = ∅ no hay solución. Si Ω no está acotado en la dirección del vector c, resulta z = + ∞
(sería el caso, por ejemplo, de un problema de máximo con restricciones de mayor o igual),
y en este caso no hay solución óptima finita.
c) Si el problema tiene solución, la solución óptima puede ser:
c1) única y se produce en un vértice de Ω, o bien,
c2) pueden ser infinitas, pues para ciertos valores de la relación entre c1 y c2 la pendiente
de la recta de isobeneficio puede coincidir con la de alguno de los lados de Ω
(incluidos los vértices extremos).
Ambas situaciones se pueden resumir diciendo que "si el problema tiene solución, entonces
al menos un vértice es solución". Este hecho es la base del algoritmo Simplex.
d) Cada uno de los coeficientes de la función objetivo c1 y c2 pueden variar, por separado,
dentro de ciertos intervalos (varía la pendiente de la recta de isobeneficio) sin que cambie
la solución óptima. Fuera de ellos la solución cambia.
e) Hay recursos que son utilizados completamente y otros no, éstos tienen una holgura.

1.1.1 Definiciones y notación

Un PL se dice que está en la forma canónica si:
i) Es un problema de máximo.
ii) Las restricciones son todas inecuaciones de tipo ≤
iii) Las variables son todas no negativas.
Esta es la forma básica para los desarrollos teóricos. No implica ninguna pérdida de
generalidad pues, como veremos, todo PL puede ser transformado en un PL equivalente
canónico.
Un PL se dice que está en la forma estándar si:
i) Las restricciones son todas ecuaciones (con los bi ≥ 0, i = 1, 2, … , m).
ii) Las variables son todas no negativas.
Puede ser indistintamente de máximo o de mínimo. Esta forma es importante para la
resolución numérica.
Todo PL con restricciones del tipo inecuaciones puede ser transformado en uno estándar
equivalente agregando variables de holgura a las restricciones.
Llamando A a la matriz de los coeficientes aij, de orden m × n, Aj a sus vectores
columnas, y c, x∈ℜn, b∈ℜm, un PL en la forma canónica se puede expresar en forma más
compacta de la siguiente forma

4 P. Lineal
 n
max. z = ∑ c j x j
j =1

sujeta a ( 1-4)
 n


Ω
∑x j Aj ≤ b
j =1
 x≥0

o todavía
max. z = c T x
sujeta a
( 1-5)
 Ax ≤ b
Ω
 x≥0
y análogamente para la forma estándar.
Todo vector x que satisface las restricciones es una solución. Si además satisface las
condiciones de no negatividad, es decir si x∈Ω, es una solución factible (o posible o
admisible). Solución óptima es toda solución factible que optimiza la función objetivo.
Indicaremos con x* a la solución óptima y con z* al valor de la función objetivo en el
óptimo.
Cuando, para la solución óptima, en una restricción de tipo inecuación se verifica la
igualdad diremos que la restricción es activa, en caso contrario es no activa o inactiva. Si una
restricción es activa, el recurso correspondiente es utilizado totalmente y diremos que es un
recurso escaso. Si la restricción es no activa el recurso es no escaso.
Un PL asigna recursos disponibles a actividades de forma tal que optimiza una función
objetivo. Una actividad j queda completamente descripta por los coeficientes aij que forman
el vector Aj. Estos coeficientes indican la cantidad de recurso i que se emplea en una unidad
de la actividad j y se denominan consumos específicos o coeficientes tecnológicos, porque
su valor depende de la tecnología de los procesos de producción empleados. El valor que toma
la variable xj en el óptimo se suele llamar también el nivel de la actividad j.

1.1.2 Variables de holgura

Cualquier restricción del tipo inecuación puede ser transformada en ecuación agregando
una variable auxiliar, llamada variable de holgura, que también deberá satisfacer la
condición de no negatividad.
Para el ejemplo anterior tendríamos

 x1 + 2 x2 + x3 = 160
2 x + 2 x2 + x4 = 200
 1

9 x1 + 4 x2 + x5 = 720
 x1 , x 2 ,  , x 5 ≥ 0
La interpretación de estas variables es la siguiente: x3, por ejemplo, es la cantidad a
fabricar de un producto ficticio P3 que requiere sólo la utilización de una unidad del recurso
M; x4 es la cantidad de un producto ficticio P4 que requiere sólo una unidad del recurso A;

P. Lineal 5
etc. Resulta claro que, en el óptimo, estas variables indican la cantidad de unidades
sobrantes de cada recurso, que es lo que se llama holgura.
Para el ejemplo resultarían
x3* = x4* = 0 x5* = 120
Naturalmente que la contribución marginal de estos productos ficticios será nula, de
manera que las variables correspondientes se agregan en la función objetivo con coeficientes
0.
max. z = 50 x1 + 60 x2 + 0 x3 + 0 x4 + 0 x5
En general tendremos que si xj es la variable de holgura de la i-ésima restricción, en el
óptimo representa la holgura del i-ésimo recurso cuya disponibilidad es bi.
Entonces resulta que, en el óptimo, son equivalentes las expresiones holgura nula, recurso
escaso y restricción activa. Análogamente holgura positiva, recurso no escaso y restricción no
activa.
El problema queda así planteado en la forma estándar, necesaria para su resolución
analítica, y podemos despreocuparnos de qué variables son originales y cuáles de holgura
puesto que al buscar el óptimo el propio método hará que las variables de holgura tomen sus
valores mínimos.

1.1.3 PL en forma estándar

Consideremos ahora PL exclusivamente en la forma estándar, es decir en la forma
n
max. z = ∑ c j x j
j =1

sujeta a
( 1-6)
 n


Ω
∑x j Aj = b
j =1
 x≥0

o todavía, en forma más compacta
max. z = c T x
sujeta a
 Ax = b ( 1-7)
Ω
 x≥0
donde Am × n, x∈ℜn y b∈ℜm.
Observación. Notemos que si un problema está en la forma canónica y le agregamos
variables de holgura para llevarlo a la forma estándar, el número de variables sería n + m. Sin
embargo, para mantener simple la notación, llamaremos siempre m al número de
restricciones y n al de incógnitas, dentro de una misma forma de problemas. En la forma
estándar entonces supondremos que siempre es m < n.
Además supondremos que en la matriz A las filas son vectores linealmente
independientes, es decir que en el sistema de ecuaciones A x = b las m ecuaciones son

6 P. Lineal
linealmente independientes. La dependencia lineal entre las filas significaría que hay
restricciones contradictorias y el sistema no tendría solución, o bien que hay restricciones
redundantes que podrían ser eliminadas. Por lo tanto supondremos siempre que el rango de A
es m y en consecuencia hay al menos una base formada con m vectores columnas de A. Si
el rango de A es m, como m < n, el sistema tiene infinitas soluciones, pero no
necesariamente factibles del PL.

1.1.4 Soluciones básicas

Consideremos una base B de vectores de la matriz A y una solución x. Las m variables
componentes de x asociadas a los vectores de B se llaman variables básicas, y las n − m
variables componentes de x asociadas a los vectores que no pertenecen a B se llaman
variables no básicas. Si las variables no básicas son nulas, la solución x se llama solución
básica. Si además la solución x es factible, la solución se llama básica factible. En general
con la expresión "solución básica" nos referiremos a soluciones básicas factibles. Si una o más
de las m variables básicas son nulas, la solución se llama básica degenerada, si ninguna es
nula la solución es básica no degenerada.

1.2 PROPIEDADES DE LAS SOLUCIONES DE UN PROGRAMA LINEAL

Las siguientes propiedades son fundamentales para el desarrollo del algoritmo de
resolución.
Teorema 1-1. El conjunto Ω ⊂ ℜn de soluciones factibles de un PL es convexo cerrado.
Demostración. Si el problema está en la forma canónica el conjunto de soluciones

 Ax ≤ b
Ω ( 1-1)
 x≥0
es un polítopo por estar definido por restricciones de tipo inecuaciones, luego es convexo
cerrado.
Sea ahora un problema en la forma estándar cuyo conjunto de soluciones es

 Ax = b
K ( 1-2)
 x≥0
La proposición es verdadera, por supuesto, si K tiene un solo elemento. Supongamos
entonces que existen al menos dos soluciones x1, x2∈K y formemos una combinación
convexa x = α x1 + (1 − α ) x2 , 0 ≤ α ≤ 1 . Observemos que x tiene todos sus componentes no
negativos por serlo los de x1 y x2, y además satisface las restricciones
Ax = A [α x1 + (1 − α ) x2 ] = α Ax1 + (1 − α ) Ax2 = α b + (1 − α )b = b ( 1-3)
es decir x∈K, luego K es convexo cerrado. ■
Teorema 1-2. Sea un PL en forma estándar con K dado por ( 1-2), y sea A de rango m.
Entonces si hay solución factible (K ≠ ∅), hay una solución básica factible.
Demostración. Sea x1, x2, … , xn una solución factible y supongamos que p (p ≤ n)
variables son positivas (por conveniencia supondremos que son las p primeras). Entonces
x1 A1 + x2 A2 +  + x p Ap = b ( 1-4)

P. Lineal 7
a) Supongamos que los vectores Aj son linealmente independientes, luego debe ser p ≤ m.
a1) Si p = m la solución es básica y el teorema está demostrado.
a2) Si p < m, como A tiene rango m se pueden encontrar m − p vectores, dentro de
los n − p restantes, tales que agregados a los p dados formen una base de
dimensión m. Asignando valor cero a las correspondientes variables se tiene una
solución básica (degenerada).
b) Supongamos que los vectores Aj son linealmente dependientes. Entonces se puede formar
con ellos una combinación lineal
y1 A1 + y2 A2 +  + y p Ap = 0 ( 1-5)

donde algún yj ≠ 0. Supongamos que hay al menos un yj > 0. Multiplicando la ( 1-5) por
ε∈ℜ y restándola de la ( 1-4) obtenemos
( x1 − ε y1 ) A1 + ( x2 − ε y2 ) A2 +  + ( x p − ε y p ) Ap = b ( 1-6)

luego el vector
x−ε y ( 1-7)
es solución. Eligiendo

x 
ε = min  i , yi > 0 ( 1-8)
i
 yi 
todos los paréntesis de ( 1-6) son no negativos y al menos uno se anula, con lo cual la solución
( 1-7) es factible y tiene a lo sumo p − 1 componentes positivos. Si los correspondientes p −
1 vectores son linealmente independientes se aplica el caso a) y la solución obtenida es
básica. Caso contrario, repitiendo el procedimiento podemos eliminar componentes positivos
en cada nueva solución obtenida, hasta llegar a una solución factible a la que le correspondan
vectores linealmente independientes. Se aplica entonces el caso a) y la solución obtenida es
básica.
Si no hubiera ningún yj > 0, en la ( 1-6) ε podría tomar valores positivos arbitrariamente
grandes y la solución sería no acotada. En este caso el PL no tiene solución óptima finita. ■
Teorema 1-3. Sea un PL en la forma estándar y sea K el conjunto convexo de las
soluciones factibles definido por ( 1-2). Entonces un punto x∈K es un punto extremo de K
si, y sólo si, x es una solución básica factible del problema.
Demostración. Condición suficiente. Supongamos que las columnas Ai, i = 1, 2, …, m
forman una base y el punto xT = (x1, x2, … , xm, 0, 0, … , 0) es una solución básica factible
(sin pérdida de generalidad podemos suponer por comodidad que las variables básicas son las
m primeras), luego
x1 A1 + x2 A2 +  + xm Am = b ( 1-9)
Supongamos que el punto x no sea extremo, luego se lo puede expresar como
combinación convexa de otros dos puntos y, z ∈ K, es decir x = α y + (1 − α) z, 0 ≤ α ≤ 1.
Dado que todos los componentes de x, y y z son no negativos y 0 ≤ α ≤ 1, es inmediato
que los últimos n − m componentes de y y z deben ser nulos. Reemplazando y y z en las
restricciones

8 P. Lineal
 y1 A1 + y2 A2 +  + ym Am = b
( 1-10)
z1 A1 + z2 A2 +  + zm Am = b
y restando miembro a miembro resulta
( y1 − z1 ) A1 + ( y2 − z2 ) A2 +  + ( ym − zm ) Am = 0 ( 1-11)
Puesto que y y z son distintos debe ser yi ≠ zi para algún i, y por lo tanto alguno de los
paréntesis es no nulo, con lo que los vectores Ai son linealmente dependientes, en contra de
la hipótesis. Luego x es punto extremo.
Condición necesaria. Sea x un punto extremo de K y supongamos que sus componentes
no nulos son los k primeros, entonces
x1 A1 + x2 A2 +  + xk Ak = b ( 1-12)
y debemos demostrar que los vectores Ai, i = 1, 2, … , k, son linealmente independientes.
Supongamos que no lo sean, entonces podemos formar una combinación lineal
β1 A1 + β2 A2 +  + βk Ak = 0 ( 1-13)
con al menos algún βι ≠ 0. Multiplicándola por un real d > 0 y restándola y sumándola
respectivamente a la ( 1-12)
( x1 − dβ1 ) A1 + ( x2 − dβ 2 ) A2 ++ ( xk − dβ k ) Ak = b
( 1-14)
( x1 + dβ1 ) A1 + ( x2 + dβ 2 ) A2 ++ ( xk + dβ k ) Ak = b
Como los xi son todos positivos, eligiendo

 x 
d < min  i , βi ≠ 0 ( 1-15)
i  βi 
todos los paréntesis de las dos ecuaciones son coeficientes positivos y por lo tanto tenemos
dos soluciones factibles del PL
y = x − dβ y z = x + dβ ( 1-16)
y sumándolas resulta y + z = 2 x, de donde
x = 21 y + 21 z ( 1-17)

Es decir que x resulta combinación convexa de otros dos puntos de K distintos y por lo
tanto no es punto extremo, en contra de la hipótesis. Luego los vectores Ai son linealmente
independientes.
Dado que no puede haber más que m vectores linealmente independientes, deberá ser k ≤
m. Si k < m, como el rango de A es m, siempre se pueden agregar m − k vectores tomados
de entre los n − k restantes, de manera que los m vectores formen una base. Los
componentes de x correspondientes a esos m − k vectores agregados serán obviamente
nulos. Así x es una solución básica factible. ■
Notemos que en una solución básica no degenerada las variables básicas son todas
positivas y por lo tanto toda variable nula es no básica. En cambio en el caso de solución
básica degenerada hay variables nulas tanto básicas como no básicas.

P. Lineal 9
 Corolario 1-1. Si K es no vacío, tiene al menos un punto extremo.
En efecto, por el Teorema 1-2 hay una solución básica y por el Teorema 1-3 es un punto
extremo. ■
Corolario 1-2. El conjunto K tiene un número finito de puntos extremos.
En efecto, el conjunto de soluciones básicas es finito, pues es un subconjunto del conjunto
de las distintas m-uplas de vectores que se pueden formar con los n vectores de A, cuyo
número está dado por

 n n!
N = Cn , m =   = ( 1-18)
 m m!(n − m)!
y como el conjunto de puntos extremos es un subconjunto del de soluciones básicas, es
también finito. ■
Resulta así que N es una cota superior del número de puntos extremos (N contiene
también las m-uplas que no forman bases y las correspondientes a soluciones no factibles).
Observación. Si el conjunto de soluciones admisibles es no vacío y acotado, es un
hiperpoliedro. Si el PL tiene solución óptima finita y el conjunto de soluciones factibles es no
acotado, siempre se lo puede formular en forma equivalente como un PL con conjunto de
soluciones factibles acotado, agregando cotas apropiadas a las variables, sin que cambie la
solución óptima. Por lo tanto en todo lo que sigue consideraremos que el conjunto de
soluciones factibles de un PL, si no es vacío, es un hiperpoliedro.
Corolario 1-3. Si K es no vacío y acotado, es decir es un hiperpoliedro, sus puntos no
extremos se pueden expresar como combinaciones convexas de un número finito de puntos
extremos.
En efecto, sabemos que todo punto no extremo de un hiperpoliedro se puede expresar
como combinación convexa de sus puntos extremos, y éstos existen en número finito por el
Corolario 1-2. ■
Teorema 1-4. La solución óptima de un PL se produce siempre en al menos un punto
extremo del conjunto de soluciones factibles Ω. Si el óptimo se produce en más de un punto
extremo, entonces también es óptimo todo punto que sea combinación convexa de ellos.
Demostración. Sea un PL en forma canónica y sean x1, x2, … , xp los puntos extremos de
Ω. Entonces un punto cualquiera x se puede expresar como combinación convexa de ellos
p p

x = ∑ αi xi con αi ≥ 0 , ∑α i =1 ( 1-19)
i =1 i =1

y la función objetivo resulta

 p  p p

z = c x = c ∑ αi xi  = ∑ αi c xi = ∑ αi zi
T T T
( 1-20)
 i =1  i =1 i =1

donde zi es el valor que toma la función objetivo en xi, i = 1, 2, … , p.

Llamando z0 = max {zi } y reemplazando en ( 1-20) resulta
i

10 P. Lineal
 p p

z ≤ ∑ αi z 0 = z 0 ∑ αi = z 0 ( 1-21)
i =1 i =1

con lo que el óptimo es z0 que se produce en al menos uno de los puntos extremos.
Si el óptimo se produce en k puntos extremos x1, x2, … , xk se tiene
z * = c T x1 =  = c T xi =  = c T xk ( 1-22)

y si x es una combinación convexa de ellos

k k
x = ∑ αi xi con αi ≥ 0 , ∑α i =1 ( 1-23)
i =1 i =1

entonces la función objetivo resulta

k k k k
z = c T x = c T ∑ αi xi = ∑ αi c T xi = ∑ αi z * = z * ∑ αi = z * ( 1-24)
i =1 i =1 i =1 i =1

es decir x es también óptimo. ■

1.3 EJERCICIOS
1 - Sean los siguientes conjuntos de restricciones
2 x1 + 3x 2 ≤6 2 x1 + 3x 2 ≤6
a)  b) 
 x1 + 4 x2 =4 2 x1 + 3x 2 =4

Agregar las variables de holgura y analizar los pares de vectores de las matrices de los
coeficientes. Determinar si corresponden a soluciones básicas factibles, básicas no factibles o
a ninguna solución.
2 - Sean los siguientes PL
a) max. z = 3x1 + 9 x 2 b) max. z = 2 x1 + x 2
2 x1 + 3x 2 ≤6 4 x1 + 3x2 ≤ 12
 4 x
 x1 + 4 x2 =4  1 + x2 ≤8
 
 x1 , x 2 ≥0 4 x1 − x2 ≤8
 x1 , x 2 ≥0

Analizar las soluciones básicas y determinar si son degeneradas o no.

P. Lineal 11