PROGRAMACIÓN LINEAL

Investigación Operativa: 2º curso

Ingeniería de Organización Industrial (Semipresencial)

Begoña Álvarez Tena

Curso 2024-2025
Índice

1 Introducción

2 Formulación de un problema de programación lineal (PPL)

3 Resolución gráfica de un PPL de 2 variables

4 Resolución de un PPL. Algoritmo Simplex

5 Teoría de la Dualidad

6 Precios sombra

7 Análisis de sensibilidad
Índice

1 Introducción

2 Formulación de un problema de programación lineal (PPL)

3 Resolución gráfica de un PPL de 2 variables

4 Resolución de un PPL. Algoritmo Simplex

5 Teoría de la Dualidad

6 Precios sombra

7 Análisis de sensibilidad
Introducción. Programación Lineal
Un problema de programación lineal es un problema de optimización para el
que se verifica que:
Se trata de maximizar o minimizar una función lineal de las variables de
decisión.
Cada restricción puede expresarse como una ecuación o inecuación lineal.
Para que un modelo de optimización lineal pueda considerarse una
representación adecuada de un sistema, las variables de decisión deben
verificar:
Proporcionalidad: La contribución de cada variable a la función objetivo
y a las restricciones es directamente proporcional al valor de la variable.
Aditividad: No existen interacciones entre las variables, es decir, la
contribución de una variable a la función objetivo y a las restricciones es
independiente del valor de las otras variables.
Divisibilidad: Las variables de decisión pueden tomar cualquier valor no
negativo. Restricción de no negatividad
Certeza: Los parámetros que regulan el impacto en la función objetivo y
en las restricciones de cada variable son conocidos y exactos.
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 4 / 110
Introducción. Programación Lineal

Programación Lineal
La programación lineal es una técnica muy utilizada debido a varios factores:
1 Una gran cantidad de problemas pueden modelarse como un modelo
lineal: campo militar, económico, industrial, social, logística, etc.
2 Existen técnicas eficientes para la resolución de estos modelos.
3 Fácilmente se pueden realizar estudios de variación de los parámetros
del problema sin abandonar el ámbito lineal.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 5 / 110

Índice

1 Introducción

2 Formulación de un problema de programación lineal (PPL)

3 Resolución gráfica de un PPL de 2 variables

4 Resolución de un PPL. Algoritmo Simplex

5 Teoría de la Dualidad

6 Precios sombra

7 Análisis de sensibilidad
Formulación de un PPL. Ejemplo

Programación Lineal. Ejemplo

Un taller artesanal se dedica a la fabricación de sillas y mesas. Para su
elaboración se disponen de dos materias primas: roble y pino, además de un
departamento en el que se realiza el montaje.
Semanalmente se dispone de 150 unidades de roble y 100 unidades de pino,
y se puede trabajar a lo sumo 80 horas en la fabricación de las mesas y
sillas. Se sabe que cada mesa necesita 5 unidades de roble, 2 de pino y 4
horas de trabajo para ser fabricada. Cada silla necesita 2 unidades de roble,
3 de pino y 2 horas de trabajo para ser fabricada. Cada mesa que se vende
proporciona un beneficio neto de 12 unidades monetarias (um), mientras
que en el caso de las silla es de 8 um.
¿Cuántas mesas y sillas se deben elaborar para maximizar el beneficio
del taller?

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 7 / 110

VARIABLESDEDECISIO [Link]
de sillas a fabricar
de mesas
a fabricar
X2 N

LEFIFICE 5
2
150

2 100
CPino 3 1 2

4 80
Horas 2 1 2

20
20

FONCIÓNOBJETNON Max 8 1
12 2
Formulación de un PPL. Ejemplo
Se definen dos variables de decisión:

x1 : Número de mesas fabricadas

x2 : Número de sillas fabricadas

Se determina la función objetivo: maximizar el beneficio del taller por

la venta de las mesas y las sillas elaboradas

max f (x) = 12x1 + 8x2

Se determinan las restricciones que se deben satisfacer:

Disponibilidad de Roble: 5x1 + 2x2 Æ 150
Disponibilidad de Pino: 2x1 + 3x2 Æ 100
Disponibilidad de horas de trabajo: 4x1 + 2x2 Æ 80
Número de unidades no negativo: x1 Ø 0, x2 Ø 0

Solución: x1 = 5, x2 = 30
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 8 / 110
Formulación de un PPL. Forma general
max 8 1 12 2
5 2
8 ª 1
2 2 100
3 1
La forma general de un PPL es la siguiente: 2 1 4 2 80
20
Y
_
_
_min / max f (x) = c1 x1 + c2 x2 + . . . + cn xn tazones
_
_
_
_
_
_sujeto a: a11 x1 + a12 x2 + . . . + a1n xn (=, Æ, Ø) b1
_
_
] a21 x1 + a22 x2 + . . . + a2n xn (=, Æ, Ø) b2
..
_
_
_
_ .
_
_
_
_
_ am1 x1 + am2 x2 + . . . + amn xn (=, Æ, Ø) bm
_
_
[ xi Ø 0, ’i = 1, . . . , n

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 9 / 110

Formulación de un PPL. Forma estándar
La forma estándar de un PPL es la siguiente:
Y EEEE
_
_
_
_
max f (x) = c1 x1 + c2 x2 + . . . + cn xn 15 i
_
_
_ sujeto a: a11 x1 + a12 x2 + . . . + a1n xn = b1 m
_
_
] a21 x1 + a22 x2 + . . . + a2n xn = b2 C 18 12
..
_ .
AFE
_
_
_
_
_
_
_ am1 x1 + am2 x2 + . . . + amn xn = bm
_
[
xi Ø 0, ’i = 1, . . . , n
E
La formulación estándar se caracteriza porque todas las restricciones son igualdades
y todas las variables de decisión son mayores o iguales que cero.
Y 5 0 1
]max
_ f (x) = cx
Y su correspondiente forma matricial: sujeto a: Ax = b
_
[
xØ0
c: Vector de costos b: Vector de recursos
x: Variables de decisión A: Matriz de coeficientes
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 10 / 110
Transformación a forma estándar

Si el problema es de mínimo pasa a ser de máximo. min 3 2 2 1

max f(x) © min ≠ f(x)
Max 8 2 2 1

Si existe xj Æ 0, basta hacer un cambio de variable para cambiarla de signo.

xj se sustituye por yj = ≠xj , yj Ø 0

Si xj œ R, no restringida en signo, puede escribirse como la diferencia de dos

variables no negativas.
jt 1 5≠ 3.1
xj se sustituye por xj = xj+ ≠ xj≠ donde xj+ Ø 0, xj Ø 0

2.11 1 3 1

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 11 / 110

Transformación a forma estándar
EEE 21 4 2
Si la restricción es de la forma Æ, se suma en la parte izquierda de la
80
restricción una variable de holgura xn+1 Ø 0 60 20 80

aj1 x1 + aj2 x2 + . . . + ajn xn Æ bj æ aj1 x1 + aj2 x2 + . . . + ajn xn + xn+1 = bj

Si la restricción representa, por ejemplo, el consumo de un recurso, la variable
xn+1 representa el recurso disponible no consumido, es decir sobrante.
Si la restricción es de la forma Ø, se resta en la parte izquierda de la
restricción una variable de holgura xn+1 Ø 0
aj1 x1 + aj2 x2 + . . . + ajn xn Ø bj æ aj1 x1 + aj2 x2 + . . . + ajn xn ≠ xn+1 = bj
Si la restricción representa, por ejemplo, un nutriente que debe aportar una
dieta, la variable xn+1 representa el exceso de ese nutriente proporcionado por
la dieta.
En general, en la función objetivo se asocia a las variables de holgura un
coeficiente cero.
El valor de la variable de holgura proporciona información explícita sobre el
ajuste de la correspondiente restricción de desigualdad.
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 12 / 110
Transformación a forma estándar. Ejemplo

Transformación a forma estándar. Ejemplo

Transforma a forma estándar el problema de programación lineal planteado
en el ejemplo de sillas y mesas (diapositiva 7).

Y Y
_
_
_
max 12x1 + 8x2 _
_
_
max 12x1 + 8x2 + 0x3 + 0x4 + 0x5
_
_ _
_
]s.a 5x1 + 2x2 Æ 150 ]s.a 5x1 + 2x2 + x3 = 150
_
_ _
_
2x1 + 3x2 Æ 100 ∆ 2x1 + 3x2 + x4 = 100
_
_ _
_
_
_
_
_ 4x1 + 2x2 Æ 80 _
_
_
_ 4x1 + 2x2 + x5 = 80
_
[ _
[
x1 Ø 0, x2 Ø 0 xi Ø 0, i = 1, . . . , 5

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 13 / 110

Ejemplo. Circular y folleto publicitario

Una empresa dedicada a la edición digital tiene el siguiente problema. Ha

recibido el encargo de editar un folleto publicitario y una circular informativa
que una compañía desea distribuir entre sus clientes. Las condiciones de
encargo pueden resumirse del modo siguiente: La circular se editará en
tamaño DIN A4 (210x297mm), mientras que el folleto publicitario se editará
en tamaño DIN A3 (420x297mm).
Debido a los diferentes tipos de clientes que van dirigidos, unos recibirán
únicamente la circular, mientras que otros recibirán un ejemplar de la
circular acompañada de un ejemplar del folleto publicitario. Por tanto el
número de circulares debe ser necesariamente superior al número de folletos.
Además, puesto que no se desea que exista mucho material sobrante se
pretende, por una parte que el número total de folletos no supere los 4000
ejemplares y, por otra parte, que la diferencia entre el número de folletos y
la mitad del número de circulares sea como mínimo de 500 ejemplares.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 14 / 110

Ejemplo. Circular y folleto publicitario

Analizados estos requisitos y valoradas las necesidades de papel, mano de

obtra, etc, la empresa decide que tan solo es posible imprimir en el tiempo
disponible, a lo sumo 14000 ejemplares de tamaño A4 o, puesto que el
tamaño A3 es el doble del tamaño A4, 7000 ejemplares de tamaño A3, o
cualquier combinación de ejemplares A4-A3 que no supere dicha cantidad.
Con todas estas limitaciones, presenta a lo clientes la siguiente oferta
económica: zendo
Precio de cada circular informativa 0.1 euros
Precio de cada folleto informativo 0.3 euros 7127000

Plantea un problema de programación lineal que permita determinar

el número de folletos y circulares que hay que imprimir para obtener
el máximo beneficio. Formula el problema anterior en su
correspondiente forma estándar.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 15 / 110

Ejemplo. Circular y folleto publicitario
Se definen dos variables de decisión:
x1 : número de folletos publicitarios que hay que tirar
x2 : número de circulares publicitarias que hay que tirar

Se determina la función objetivo: maximizar el beneficio

max f (x) = 0.3x1 + 0.1x2

Se determinan las restricciones que se deben satisfacer:
Número de circulares mayor que el número de folletos publicitarios:
x2 Ø x1
Número de folletos publicitarios: x1 Æ 4000
Relación entre folletos y circulares: x1 ≠ 12 x2 Ø 500 æ 2x1 ≠ x2 Ø 1000
Disponibilidad de papel: 2x1 + x2 Æ 14000
No negatividad de las variables: x1 Ø 0, x2 Ø 0

Solución: x1 = 4000, x2 = 6000

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 16 / 110
Ejemplo. Circular y folleto publicitario
110 X2 X1 XyY O
2
X [Link] XXzaz 0_
_
_max 0.3x1 + 0.1x2
_
_ 20
_
_
_s.a x2 Ø x1 2
_
_
] x1 Æ 4000 X1 X2 0
Forma General :
_
_
_ 2x1 ≠ x2 Ø 1000
_
_
_
_
_
_
2x1 + x2 Æ 14000
_
[
x1 Ø 0, x2 Ø 0
Y
_
_
_max 0.3x1 + 0.1x2 + 0x3 + 0x4 + 0x5 + 0x6
_
_
_
_
_s.a x2 ≠ x 1 ≠ x3 = 0
_
_
] x1 + x4 = 4000
Forma Estándar :
_
_
_ 2x1 ≠ x2 ≠ x5 = 1000
_
_
_
_
_
_
2x1 + x2 + x6 = 14000
_
[
xi Ø 0, i = 1, . . . , 6
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 17 / 110
Índice

1 Introducción

2 Formulación de un problema de programación lineal (PPL)

3 Resolución gráfica de un PPL de 2 variables

4 Resolución de un PPL. Algoritmo Simplex

5 Teoría de la Dualidad

6 Precios sombra

7 Análisis de sensibilidad
un PPL
única
Solución óptima
Solución óptima múltiple
Problema no cazado
Problema
no factible
Resolución Gráfica. Problema no factible

x2

x1 Ø 4

Y x1 + x2 Æ 3
_
_
_ max 4x1 + 3x2
_
_
la
]sujeto a: x1 + x2 Æ 3
_
_
_ 2x1 ≠ x2 Æ 3 ½
_
_
[ x1 Ø 4, x2 Ø 0

x1

2x1 ≠ x2 Æ 3

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 19 / 110

Resolución Gráfica. Problema no acotado

x2

Y
_
_ max 2x1 + 3x2 x1 + x2 Ø 3
_
_
_
]sujeto a: x1 + x2 Ø 3
_
_
_ x1 ≠ 2x2 Æ 4
_
_
[ x1 Ø 0, x2 Ø 0 x1 ≠ 2x2 Æ 4
x1

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 20 / 110

Resolución Gráfica. Solución múltiple

x2

Y 10x1 + 3x2 Æ 30
_
_
_ max 3x1 + 2x2
_
_
]sujeto a: 6x1 + 4x2 Ø 24
_
_
_ 10x1 + 3x2 Æ 30
_
_
[ x1 Ø 0, x2 Ø 0
6x1 + 4x2 Ø 24
x1

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 21 / 110

 Resolución Gráfica. Solución óptima única

x2
5x1 + 2x2 Æ 150

Y
_
_
_
max 12x1 + 8x2
_
_
]sujeto a: 5x1 + 2x2 Æ 150
_
_
2x1 + 3x2 Æ 100
_
_ (5, 30)
_
_
_
_
_
[
4x1 + 2x2 Æ 80 I
x1 Ø 0, x2 Ø 0
2x1 + 3x2 Æ 100

x1
4x1 + 2x2 Æ 80

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 22 / 110

Curvas de nivel
Distintos
8 k valores del
12 1 2
E 1 VEZ
E 3 K 4
Definimos la familia de curvas de nivel Ck como el conjunto de curvas le 10
f(x1 , . . . , xn ) = k.
Función objetivo
Para los problemas de optimización de dos variables, se puede encontrar el
máximo o el mínimo de la función objetivo representando sus curvas de nivel
sobre la región factible. El máximo (o el mínimo) de la función objetivo se
alcanzará sobre al menos un vértice de la región factible, siempre que esta
sea cerrada y acotada.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 23 / 110

Ejemplo. Circular y folleto publicitario

Obtén la resolución gráfica del problema de los folletos y circulares

publicitarias.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 24 / 110

Ejemplo. Circular y folleto publicitario

Red

Gráficamente se puede comprobar que la solución se encuentra en el vértice

intersección de las rectas x1 = 4000 y 2x1 + x2 = 14000. Dicha intersección
se produce en el punto (4000, 6000).
El máximo se alcanza en dicho punto, y por lo tanto se deberán imprimir
4000 folletos y 6000 circulares para obtener un beneficio máximo de
0.3 · 4000 + 0.1 · 6000 = 1800 euros.
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 25 / 110
Índice

1 Introducción

2 Formulación de un problema de programación lineal (PPL)

3 Resolución gráfica de un PPL de 2 variables

4 Resolución de un PPL. Algoritmo Simplex

5 Teoría de la Dualidad

6 Precios sombra

7 Análisis de sensibilidad
Resolución de un PPL. Conceptos previos

Y
]max f (x) = cx
_
_
Sea el problema de programación lineal: sujeto a: Ax = b , donde la
_
_
[ xØ0
matriz A tiene dimension m ◊ n.
Región factible: S = {x œ Rn |Ax = b, x Ø 0}
Problema factible: Se dice que el problema es factible si la región de
factibilidad es no vacía. En otro caso, se dice que el problema es no
factible.
Solución factible: vector x œ Rn que verifica Ax = b, x Ø 0

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 27 / 110

Resolución de un PPL. Conceptos previos
Solución básica (SB): X es solución básica si y solo si AX = b y
existen al menos n ≠ m variables que toman valor cero. Dicho de otra
manera: X es solución básica si y solo si AX = b y existen índices
B1 , . . . , Bm tales que:
Las columnas AB1 , . . . , ABm son linealmente independientes.
Si i œ
/ {B1 , . . . , Bm }, entonces xi = 0
Si X es una solución básica, las variables xB1 , . . . , xBm reciben el
nombre de variables básicas y se denotan como xB . Las columnas
AB1 , . . . , ABm son las columnas básicas. Forman una base de Rm , y
denotaremos la matriz básica por B.
Las variables restantes son las variables no básicas y se denotan por xN .
Denotaremos por N a la submatriz de A cuyas columnas están
asociadas a las variables no básicas
Por lo tanto, el sistema lineal AX = b puede escribirse como:
BXB + NXN = b
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 28 / 110
Resolución de un PPL. Conceptos previos

Solución factible básica (SFB): Es una solución básica verificando las

condiciones de no negatividad. Es decir, una solución básica que
además es solución factible.
X es una solución básica degenerada, si son cero más de n ≠ m de las
componentes de X, es decir, al menos una variable básica es igual a
cero.
Una solución básica X es no degenerada, si tiene exactamente m
valores no nulos.
Dos soluciones básicas distintas son adyacentes si sus bases comparten
todas menos una de las columnas básicas, es decir, sus conjuntos de
variables básicas tienen m ≠ 1 variables básicas en común.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 29 / 110

Resolución de un PPL. Observaciones

La región factible de un problema de optimización es un poliedro y por

tanto es convexo.
Las soluciones básicas se corresponden a los vértices o extremos de la
región factible.
Si la región factible es no vacía, hay al menos una SFB.
Si la región factible es no vacía y acotada, el problema tiene solución
óptima finita.
Si el problema tiene solución óptima, hay una solución óptima que es
una SFB.
Si la región factible es no vacía y no acotada, hay dos posibilidades:
Existe una SFB que es solución óptima.
El problema es no acotado, es decir, la función objetivo es no acotada
superiormente si el problema es de máximo o no acotada inferiormente si
el problema es de mínimo.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 30 / 110

Algoritmo simplex

El algoritmo simplex proporciona un método sistemático para resolver un

problema factible de optimización lineal.

Inicialización. Encontrar una SFB

Prueba de optimalidad
Paso de una SFB a otra SFB
Selección de una nueva variable que entra a la base
Selección de una variable que abandona la base
Operación de cambio de base

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 31 / 110

Algoritmo simplex
Sea X̄ una SFB:
Q R Q R
··· ···
c d c d
c xB1 d c b̄1 d
A B c d c d
c · · · d A ≠1 B A B c· · ·d
X̄B c d B b b̄ c d
X̄ = = c xB r d =
c d = =c b̄r
dØ0
X̄N c···d 0 0 c d
c· · ·d
c d c d
c d c d
axBm b ab̄m b
··· ···

xB1 , xB2 , . . . , xBr , . . . , xBm son las variables básicas.

B = [AB1 , AB2 , . . . , ABr , . . . , ABm ] es la base, matriz m ◊ m, de rango m.
Por lo tanto A = [B, N]
El valor de la función
A Bobjetivo de la A
SFB X̄Bes:
1 2 x̄ 1 2 B ≠1 b
B
cx̄ = cB cN = cB cN = cB B ≠1 b
x̄N 0
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 32 / 110
Algoritmo simplex

Para iniciar el algoritmo es necesario tener el problema de optimización

lineal escrito en forma estándar.
En segundo lugar es necesario tener una SFB inicial. Dicha SFB debe
ser tal que su matriz B asociada sea la matriz identidad.
Sea el problema de optimización lineal:
Y Y
_
_
_max ≠x1 + 3x2 _
_
_max ≠x1 + 3x2 + 0x3 + 0x4
_
_ _
_
]s.a ≠x1 + 2x2 Æ 6 ]s.a ≠x1 + 2x2 + x3 = 6
∆
_
_
_ x1 + x2 Æ 5 _
_
_ x1 + x2 + x4 = 5
_
_ _
_
[ x1 Ø 0, x2 Ø 0 [ xi Ø 0, i = 1, . . . , 4
A B A B
≠1 2 1 0 6 1 2
A= b= c = ≠1 3 0 0
1 1 0 1 5

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 33 / 110

Algoritmo simplex. Ejemplo
Y A B
_
_max ≠x1 + 3x2 + 0x3 + 0x4 ≠1 2 1 0
_
_ A=
_
]s.a ≠x1 + 2x2 + x3 = 6 1 1 0 1
A B
_
_
_ x1 + x2 + x4 = 5 6 1 2
_
_ b= c = ≠1 3 0 0
[ xi Ø 0, i = 1, . . . , 4 5

Una SFB,
A Btal que su matriz B asociada
A B sea A la matriz
B identidad
A puede
B ser:
x3 x1 1 0 ≠1 2
xB = . Por lo tanto xN = ,B= ,N=
x4 x2 0 1 1 1
Q R
A B A B 6
x̄B B ≠1 b c5d
c d
Solución factible básica: x̄ = = = c d.
x̄N 0 a0b
0
Calculamos el valor de la función objetivo: VF 0 = cx̄ = cB B ≠1 b = 0
¿Es x̄ una solución óptima?
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 34 / 110
Algoritmo simplex

Una vez se ha inicializado el algoritmo se debe realizar una prueba de

optimalidad, para determinar si la SFB obtenida hasta el momento es
una solución óptima.
Sea x una solución factible cualquiera, el valor de la función objetivo en x es:
1 2
cx = cB xB + cN xN = · · · = cx̄ + cN ≠ cB B ≠1 N xN
1 2
Si el vector cN ≠ cB B ≠1 N Æ 0, entonces cN ≠ cB B ≠1 N x
N Æ 0.
¸ ˚˙ ˝ ¸˚˙˝
Ø0
Æ0
Por lo tanto, cx Æ cx̄ ’x œ S, es decir x̄ es una solución óptima, y el
algoritmo finaliza.
Si el vector cN ≠ cB B ≠1 N > 0, hay que tratar de pasar de una SFB a otra
SFB.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 35 / 110

Algoritmo simplex. Ejemplo

Y A B
_
_max ≠x1 + 3x2 + 0x3 + 0x4 ≠1 2 1 0
_
_ A=
_
]s.a ≠x1 + 2x2 + x3 = 6 1 1 0 1
A B
_
_
_ x1 + x2 + x4 = 5 6 1 2
_
_ b= c = ≠1 3 0 0
[ xi Ø 0, i = 1, . . . , 4 5

Calculamos cN ≠ cBAB ≠1 N:B A B

2 1 0 ≠1
1 2 1 ≠1 2 1 2 1 2
≠1 3 ≠ 0 0 = ≠1 3 ⇥ 0 0
0 1 1 1
No son ambos valores menores o iguales que cero, por lo tanto la SFB
actual, no se trata de la solución óptima.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 36 / 110

Algoritmo simplex
Si debemos pasar de una SFB a otra SFB porque el vector
cN ≠ cB B ≠1 N > 0. Tendremos que determinar que variable saldrá de la
base y que variable entrará a la nueva base.
El algoritmo simplex pasa de una SFB x̄ a otra SFB adyacente x, es decir
tendrán las mismas variables básicas excepto una. Para determinar que
variable entra a la base se escoge la variable situada en la componente
j-ésima del vector cN ≠ cB B ≠1 N, que tome un mayor valor:

máx cj ≠ cB B ≠1 Aj
j=j1 ,...,jr

Cada cantidad cj ≠ cB B ≠1 Aj recibe el nombre de costos marginales

asociados a las variables xj y representan la cantidad en la que la función
objetivo (FO) varía por cada unidad que tome la variable xj .
De aquí en adelante se denotará a la cantidad cB B ≠1 Aj por zj , de manera
que los costos marginales se calculan como cj ≠ zj .
Los costos marginales de las variables básicas son siempre cero.
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 37 / 110
Algoritmo simplex

Para
I -determinar
J que variable sale de la base, debemos calcular
b̄i --
-yij0 > 0 , siendo Yj0 = B ≠1 Aj0 y j0 hace referencia a la variable que
yij0 -
entre en la nueva base.
b̄
Saldrá de la base la variable situada en la componente i-ésima del vector ,
y
que tome un menor valor. Cabe recordar que b = B ≠1 b

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 38 / 110

Algoritmo simplex. Ejemplo
Y A B
_
_max ≠x1 + 3x2 + 0x3 + 0x4 ≠1 2 1 0
_
_ A=
_
]s.a ≠x1 + 2x2 + x3 = 6 1 1 0 1
A B
_
_
_ x1 + x2 + x4 = 5 6 1 2
_
_ b= c = ≠1 3 0 0
[ xi Ø 0, i = 1, . . . , 4 5

A B A B
x̄B B ≠1 b 1 2T
La SFB x̄ = = = 6 5 0 0 hemos visto que no es
x̄N 0
una solución óptima. Por ello debemos construir una nueva SFB adyacente a
la que ya tenemos. Para ello determinamos, en primer lugar, la variable que
entrará a la nueva base:
A
cN
B A
≠ cB B ≠1 N:
B
1 2 1 2 1 0 ≠1 ≠1 2 1 2
≠1 3 ≠ 0 0 = ≠1 3 la segunda
0 1 1 1
componente del vector toma un mayor valor, por lo tanto x2 será la variable
que entrará a la base.
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 39 / 110
Algoritmo simplex. Ejemplo
A B
2
Hemos visto que la variable que entrará a la base sera x2 , por ello A2 =
1
b
Para determinar la variable que sale de la base calculamos :
y
A BA B A B A B≠1 A B A B
1 0 6 6 1 0 2 2
b̄ = B ≠1 b = = y = B ≠1 A2 = =
0 1 5 5 0 1 1 1
; <
6 5
min , = 3, por lo tanto la variable que abandona la base es la que se
2 1
encuentra en la primera componente,
A B es decirA la B variableAx3 . B
x2 x1 2 0
De manera que tenemos: xB = , xN = ,B= ,
x4 x3 1 1
Q R
A B A B A B 3
≠1 1 x̄B B ≠1 b c2d
c d
N= Solución factible básica: x̄ = = = c d.
1 0 x̄N 0 a0b
0
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 40 / 110
Algoritmo simplex. Ejemplo

Calculamos el valor de la función objetivo: VF 0 = cx̄ = cB B ≠1 b = 3

¿Es x̄ una solución óptima?
Calculamos los costos A marginales:
BA c ≠
N B B c B ≠1 N =
1
1 2 1 2 0 ≠1 1 1 2 1 2
≠1 0 ≠ 3 0 2
1 = 12 ≠ 32 ⇥ 0 0
≠2 1 1 0
Por lo tanto no se trata de una solución óptima, y se debe repetir el proceso
anterior. Entra en la base la primera componente ya que toma un mayor
valor, es A
decir
B entra x1 a laAbase. B A B A B
1 1
3 0 ≠1 ≠2
B b=
≠1 y B A1 =
≠1 2
1 = 3
2 ≠2 1 1 2
; < ; <
3 2 4
min , = min ≠6, x2 no puede salir de la base ya que tiene
≠1/2 3/2 3
asociado un valor negativo, por lo tanto sale de la base x4 .

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 41 / 110

Algoritmo simplex. Ejemplo

A B A B A B A B
x2 x4 2 ≠1 1 0
xB = , xN = ,B= ,N=
x1 x3 1 1 0 1
Q R
QA 11/3
BR QA BR
A B A B 1/3 1/3 6
x̄B B ≠1 b c dc
c
d c 4/3 d
d
SFB: x̄ = = = a ≠1/3 2/3 b a 5 b = c d
x̄N 0 a 0 b
0 0 0
¿Es x̄ una solución óptima? Calculamos los costos marginales:
cN ≠ cB B ≠1 N = A BA B 3
2 1/3 1/3 4 1
1 2 1 1 0 4 1 2
0 0 ≠ 3 ≠1 = ≠ ≠ Æ 0 0
≠1/3 2/3 0 1 3 3
4 11 29
Por lo tanto x̄ es una solución óptima y el VFO es: ≠ + 3 = .
3 3 3

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 42 / 110

Tablas para el algoritmo simplex

Toda la información necesaria para realizar los cálculos anteriores se

almacena en:
c1 c 2 · · · c n
x1 x2 · · · xn
Qc R Qx R Qy R Q R
1 1 11 ··· y1n b1
c c2 d c x2 d c y21 · · · y2n d c b2 d
cB = a . b xB = a . b Y =B A=a
≠1
.. b b̄ = B b = c . d
≠1
.
. . . .
a .. b
cm xm ym1 · · · ymn bm
c ≠ cB B ≠1 A

El algoritmo simplex se presenta siempre en una tabla cuya característica es

que transforma el sistema de ecuaciones original con objeto de que en todas
las iteraciones las variables básicas tengan asociada en la tabla la matriz
identidad.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 43 / 110

Tablas para el algoritmo simplex. Ejemplo
Ejemplo: mesas y sillas
x1 : Número de mesas fabricadas x2 : Número de sillas fabricadas
Y Y
_
_
_
max 12x1 + 8x2 _
_
_
max 12x1 + 8x2 + 0x3 + 0x4 + 0x5
_
_ _
_
]s.a 5x1 + 2x2 Æ 150 ]s.a 5x1 + 2x2 + x3 = 150
_
_ _
_
2x1 + 3x2 Æ 100 ∆ 2x1 + 3x2 + x4 = 100
_
_ _
_
_
_
_
_ 4x1 + 2x2 Æ 80 _
_
_
_ 4x1 + 2x2 + x5 = 80
_
[ _
[
x1 Ø 0, x2 Ø 0 xi Ø 0, i = 1, . . . , 5

max 12 8 0 0 0
cB xB x1 x2 x3 x4 x5 b Es una tabla no
0 x3 5 2 1 0 0 150 óptima ya que los
0 x4 2 3 0 1 0 100 costos marginales no
0 x5 4 2 0 0 1 80 son Æ 0.
12 8 0 0 0 ⇥0
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 44 / 110
Tablas para el algoritmo simplex. Ejemplo
Entra a la base la variable
max 12 8 0 0 0 que tenga un costo
cB xB x1 x2 x3 x4 x5 b marginal de mayor valor,
0 x3 5 2 1 0 0 150 es decir x1 .
0 x4 2 3 0 1 0 100 Sale de la base la variable
0 x5 4 2 0 0 1 80 que tenga un menor valor
12 8 0 0 0 ⇥0 bi
; < yi1 , es decir x5 .
150 100 80
min , , = min {30, 50, 20}.
5 2 4
Las columnas de las variables básicas deben tener asociada la matriz
identidad, para ello:
max 12 8 0 0 0 1
cB xB x1 x2 x 3 x4 x5 b F3 æ F3
4
0 x3 0 -1/2 1 0 -5/4 50 F2 æ F2 ≠ 2 · F3
0 x4 0 2 0 1 -1/2 60 F1 æ F1 ≠ 5 · F3
12 x1 1 1/2 0 0 1/4 20 c ≠ z = (c ≠ z) ≠ 12 · F3
240 0 2 0 0 -3 ⇥0
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 45 / 110
Tablas para el algoritmo simplex. Ejemplo

Es una tabla no óptima ya

max 12 8 0 0 0
que los costos marginales
cB xB x1 x2 x3 x4 x5 b
no son Æ 0. Entra a la
0 x3 0 -1/2 1 0 -5/4 50 base x2 , sale de la base x4 .
0 x4 0 2 0 1 -1/2 60 ;
60 20
<
12 x1 1 1/2 0 0 1/4 20 min , = 30
2 1/2
240 0 2 0 0 -3 ⇥0
1
max 12 8 0 0 0 F2 æ F2
2
cB xB x1 x2 x3 x4 x5 b 1
F3 æ F3 ≠ · F2
0 x3 0 0 1 1/4 -11/8 65 2
8 x2 0 1 0 1/2 -1/4 30 1
F1 æ F1 + · F2
12 x1 1 0 0 -1/4 3/8 5 2
c ≠ z = (c ≠ z) ≠ 2 · F2
300 0 2 -1 0 -5/2 Æ0
Es una tabla óptima, por lo tanto se tendrán que elaborar 5 mesas y 30
sillas para obtener un beneficio máximo de 300 um.
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 46 / 110
Algoritmo simplex
Finalización del algoritmo simplex (problema de máximo)
Solución óptima única: ’j no básico, se cumple que cj ≠ zj < 0.
Solución no acotada: existe j no básico cumpliendo que cj ≠ zj > 0,
pero Yj Æ 0.
Múltiples soluciones: existe j no básico cumpliendo que cj ≠ zj = 0.

¿Y si el problema es de mínimo?
Será una solución factible si cj ≠ zj Ø 0
La variable que entrará a la nueva base será min {cj ≠ zj |cj ≠ zj < 0}
El criterio de la variable que sale de la base sigue siendo el mismo (es
un criterio de factibilidad)
El algoritmo finalizará:
Solución óptima única: ’j no básico, se cumple que cj ≠ zj > 0.
Solución no acotada: existe j no básico cumpliendo que cj ≠ zj < 0,
pero Yj Ø 0.
Múltiples soluciones: existe j no básico cumpliendo que cj ≠ zj = 0.
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 47 / 110
Algoritmo simplex. Ejemplo: escritorios
Ejemplo: escritorios
Una compañía produce diariamente escritorios, mesas y sillas. La fabricación de
cada unidad de uno de estos muebles precisa madera y dos tipos de mano de obra:
acabado y carpintería. La cantidad de cada recurso necesaria para fabricar una
unidad de cada mueble se da en la siguiente tabla:
Escritorios Mesas Sillas
Madera (unidades) 8 6 1
Acabado (horas) 4 2 3/2
Carpintería (horas) 2 3/2 1/2
La compañía ha estimado que podrá disponer cada día de 48 unidades de manera y
de mano de obra por valor de 20 horas de acabado y 8 horas de carpintería.
Además, se sabe que cada escritorio se vende por 60 u.m., cada mesa por 35 u.m. y
cada silla por 20 u.m. (La compañía cree también que la demanda de todos los
productos será ilimitada).
Formula un modelo matemático que permita conocer cómo debe organizar
la compañía la producción con objeto de maximizar los beneficios. Obtén la
solución óptima.
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 48 / 110
Algoritmo simplex. Ejemplo: escritorios
Sean las variables de decisión:
x1 : número de escritorios que fabrica la compañía
x2 : número de mesas que fabrica la compañía
x3 : número de sillas que fabrica la compañía
Se quiere maximizar los beneficios de la compañía, por ello la función
objetivo es la siguiente:
max 60x1 + 35x2 + 20x3
El problema de programación lineal queda formulado de la siguiente manera:
Y
_
_
_
max 60x1 + 35x2 + 20x3
_
_
]s.a. 8x1 + 6x2 + x3 Æ 48
_
_
4x1 + 2x2 + 32 x3 Æ 20
_
_
_
_
_
_ 2x1 + 32 x2 + 12 x3 Æ 8
_
[
x1 Ø 0, x2 Ø 0, x3 Ø 0
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 49 / 110
Algoritmo simplex. Ejemplo: escritorios
Y Y
_
_
_max 60x1 + 35x2 + 20x3 _
_
_max 60x1 + 35x2 + 20x3 +0x4 + 0x5 + 0x6
_ _
]s.a. 8x1 + 6x2 + x3 Æ 48 ]s.a. 8x1 + 6x2 + x3 +x4 =48
_
_ _
_
4x1 + 2x2 + 32 x3 Æ 20 ∆ 4x1 + 2x2 + 23 x3 +x5 =20
_
_ 3 1
_
_
_
_
_ 2x1 + 2 x2 + 2 x3 Æ 8 _
_
_ 2x1 + 32 x2 + 12 x3 +x6 =8
_
[ _
[
x1 Ø 0, x2 Ø 0, x3 Ø 0 xj Ø 0, j = 1, . . . 6

max 60 35 20 0 0 0
cB xB x1 x2 x3 x4 x5 x6 b
0 x4 8 6 1 1 0 0 48
0 x5 4 2 3/2 0 1 0 20
0 x6 2 3/2 1/2 0 0 1 8
60 35 20 0 0 0 ⇥0
Es una tabla no óptima ya que los ; costos marginales
< no son Æ 0. Entra a la
48 20 8
base x1 , sale de la base x6 . min , , =4
8 4 2
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 50 / 110
Algoritmo simplex. Ejemplo: escritorios
max 60 35 20 0 0 0
cB xB x1 x2 x3 x4 x5 x6 b 1
F3 æ F3
0 x4 0 0 -1 1 0 -4 16 2
F2 æ F2 ≠ 4 · F3
0 x5 0 -1 1/2 0 1 -2 4 F1 æ F1 ≠ 8 · F3
60 x1 1 3/4 1/4 0 0 1/2 4 V1 æ V1 ≠ 60 · F3
240 0 -10 5 0 0 -30 ⇥0
Es una tabla no óptima ya que los costos; marginales
< no son ⇥ 0. Entra en la
4 4
base x3 y sale de la base x5 ya que min , = 8.
1/2 1/4
max 60 35 20 0 0 0
cB xB x1 x2 x3 x4 x5 x6 b F2 æ 2 · F2
1
0 x4 0 -2 0 1 2 -8 24 F3 æ F3 ≠ · F2
4
20 x3 0 -2 1 0 2 -4 8 F1 æ F1 + F2
60 x1 1 5/4 0 0 -1/2 3/2 2 V2 æ V2 ≠ 5 · F2
280 0 0 0 0 -10 -10 ⇥0
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 51 / 110
Algoritmo simplex. Ejemplo: escritorios
max 60 35 20 0 0 0
cB xB x1 x2 x3 x4 x5 x6 b
0 x4 0 -2 0 1 2 -8 24
20 x3 0 -2 1 0 2 -4 8
60 x1 1 5/4 0 0 -1/2 3/2 2
280 0 0 0 0 -10 -10 ⇥0
Se trata de una tabla óptima ya que todos los costos marginales son Æ 0,
sin embargo existe una variable no básica con costo marginal igual a cero,
por lo tanto estamos frente a un problema con solución múltiple.
¿Cuáles son todas las posibles soluciones? Debe entrar en la base
aquella variable no básica con coste marginal igual a cero, en nuestro caso
x2 , y siguiendo el criterio para seleccionar que variable debe abandonar la
base lo hará x1 . Únicamente nos interesa saber cómo Q es el vector
R b, ya que
136/5
c d
éste nos proporciona el valor de otra solución: b = a 56/5 b
8/5
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 52 / 110
Algoritmo simplex. Ejemplo: escritorios

De manera
Q Rque, van Q a ser R
soluciones óptimas los puntos:
2 0
c0d c 8/5 d
c d c d
c d c d
x1 = c 8 d, x2 = c 56/5 d y todas las posibles combinaciones lineales
c d c d
a24b a136/5b
0 0
convexas de ellos, es decir:
Q R
2⁄
c 8/5 · (1 ≠ ⁄) d
c d
c d
x = ⁄x1 + (1 ≠ ⁄)x2 = c 8/5 · (7 ≠ 2⁄) d ’⁄ œ [0, 1].
c d
a8/5 · (17 ≠ 4⁄)b
0
El valor de la función objetivo en todos los casos es el mismo, y la compañía
tendrá unos beneficios de 280 u.m.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 53 / 110

Algoritmo simplex

Finitud del simplex

Si en cada iteración B ≠1 b > 0 (no existe degeneración) entonces el
valor de la función objetivo se mejora estrictamente y el nuevo punto
tiene que ser distinto del anterior, y como el número de puntos
extremos es finito el algoritmo del simplex finalizará.
Si existen SFB degeneradas (variables básicas con valor nulo) el
algoritmo puede funcionar peor (hacerse menos eficiente) e incluso no
converger.
Puede no converge debido a la existencia de ciclos, es decir, conforme
vamos iterando en el algoritmo en algún momento, volveremos a obtener
la tabla inicial del algoritmo.
Para evitar la existencia de ciclos, se puede utilizar la Regla de Bland. Se
selecciona para entrar la variable con un menor índice de entre las
posibles (es decir, de entre las que tienen un coste marginal positivo si el
problema es de máximo o negativo si es de mínimo). Si hay empate en el
criterio de salida, también se debe seleccionar la de menor índice.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 54 / 110

Algoritmo simplex

¿Y si no tengo una SFB inicial?

¿Qué debemos hacer cuando no podemos construir una matriz B = In de
forma automática? Si no existen variables cuyas columnas forman In las
creamos. Estas variables reciben el nombre de variables artificiales.
Los principales métodos para la construcción de SFB iniciales son:
Método de la Gran M: asigna a las variables artificiales un coeficiente
en la función objetivo muy malo. Si el problema es de máximo será
caj = ≠M, y si es de mínimo caj = M, donde M es una cantidad
positiva mayor que cualquier valor que aparezca en el proceso de
resolución (se dice que M es suficientemente grande).
Si la información de las columnas de las variables artificiales no se
necesitan, éstas pueden eliminarse de la tabla. Una vez que una variable
artificial deja la base, puede eliminarse dicha variable del problema.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 55 / 110

Algoritmo simplex

¿Y si no tengo una SFB inicial?

Método de las Dos Fases: Se resuelve un primer problema (aplicando el
algoritmo simplex) en el que se minimiza la suma de las variables artificiales.
Si el valor de la función objetivo de dicho problema es distinto de cero,
concluimos que el problema original es no factible. En caso contrario
disponemos de una solución factible del problema original.
Si no hay variables artificiales en la base óptima, se eliminan las variables
artificiales y las columnas correspondientes y se dispone de una SFB del
problema original. En otro caso, las variables artificiales se eliminan de la
actual SFB.
En una segunda fase, se resuelve el problema original considerando como SFB
inicial la obtenida al finalizar la primera fase.

En cualquiera de los dos métodos, si el algoritmo simplex detecta una solución

óptima en la que alguna de las variables artificiales es básica y toma un valor
estrictamente positivo, entonces el problema a resolver es no factible.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 56 / 110

Algoritmo simplex. Ejemplo

Ejemplo. Cajas
Una empresa de embalaje produce dos tipos de cajas, C 1 y C 2. Cada tipo
de caja requiere de un tiempo diferente de procesamiento en dos etapas:
corte y ensamblaje. Cada caja de tipo C 1 cuesta ensamblarla 5 horas, y las
cajas de tipo C 2 cuestan 4 horas. Cada caja de tipo C 1 cuesta cortarla 3
horas y las de tipo C 2, 2 horas. La empresa puede utilizar las máquinas de
corte y ensamblaje un máximo de 120 y 180 horas, respectivamente.
Por otro lado, la empresa se ha comprometido a producir al menos 20 cajas
del tipo C 1 y 30 cajas del tipo C 2. Producir una caja del tipo C 1 lleva un
costo asociado de 3 euros, mientras que las cajas de tipo C 2 tienen un costo
asociado de 2 euros.
Plantea y resuelve un problema de programación lineal que permita
determinar el número de cajas de cada tipo que hay que producir
para minimizar los costes de producción.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 57 / 110

Algoritmo simplex. Ejemplo: Cajas

I
x1 : número de cajas producidas del tipo C 1
Variables de decisión:
x2 : número de cajas producidas del tipo C 2
Función objetivo: minimizar los costes de producción min 3x1 + 2x2

Y Y
_
_
_min 3x1 + 2x2 _
_
_min 3x1 + 2x2 +0x3 + 0x4 ≠ 0x5 ≠ 0x6
_
_ _
_
_
_
_s.a 3x1 + 2x2 Æ 120 _
_
_s.a 3x1 + 2x2 +x3 =120
_
_ _
_
] 5x1 + 4x2 Æ 180 ] 5x1 + 4x2 +x4 =180
∆
_
_
_ x1 Ø 20 _
_
_ x1 ≠x5 =20
_
_ _
_
_
_
_
_
x2 Ø 30 _
_
_
_
x2 ≠x6 =30
_
[ _
[
x1 Ø 0, x2 Ø 0 xj Ø 0, j = 1, . . . , 6

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 58 / 110

Algoritmo simplex. Ejemplo: Cajas
Observamos que inicialmente no tenemos la matriz identidad, por lo tanto debemos
añadir variables artificiales para conseguirla:
Y
_
_ min 3x1 + 2x2 + 0x3 + 0x4 + 0x5 + 0x6 +Ma1 + Ma2
_
_
_
_
_ s.a 3x1 + 2x2 + x3 = 120
_
] 5x1 + 4x2 + x4 = 180
_
_
_ x1 ≠ x5 +a1 = 20
_
_
_
_ x2 ≠ x6 +a2 = 30
_
[
xj Ø 0, j = 1, . . . , 6
De manera que la tabla inicial del simplex queda de la siguiente manera:
min 3 2 0 0 0 0 M M
cB xB x1 x2 x3 x4 x5 x6 a1 a2 b
0 x3 3 2 1 0 0 0 0 0 120
0 x4 5 4 0 1 0 0 0 0 180
M a1 1 0 0 0 -1 0 1 0 20
M a2 0 1 0 0 0 -1 0 1 30
50M 3-M 2-M 0 0 M M 0 0 ⇤0
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 59 / 110
Algoritmo simplex. Ejemplo: Cajas

min 3 2 0 0 0 0 M M
cB xB x1 x2 x3 x4 x5 x6 a1 a2 b
0 x3 3 2 1 0 0 0 0 0 120
0 x4 5 4 0 1 0 0 0 0 180
M a1 1 0 0 0 -1 0 1 0 20
M a2 0 1 0 0 0 -1 0 1 30
50M 3-M 2-M 0 0 M M 0 0 ⇤0
Es una tabla no óptima ya que los costos marginales no son Ø 0. Entra a la
base la variable que tenga un costo
; marginal <
de menor valor, es decir x2 .
120 180 30
Sale de la base a2 ya que min , , = 30
2 4 1

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 60 / 110

Algoritmo simplex. Ejemplo: Cajas

min 3 2 0 0 0 0 M
cB xB x1 x2 x3 x4 x5 x6 a1 b
0 x3 3 0 1 0 0 2 0 60
0 x4 5 0 0 1 0 4 0 60
M a1 1 0 0 0 -1 0 1 20
2 x2 0 1 0 0 0 -1 0 30
60 + 20M 3-M 0 0 0 M 2 0 ⇤0

F4 æ F4 Es una tabla no óptima ya que los costos

F3 æ F3 marginales no son Ø 0. Entra a la base la
F2 æ F2 ≠ 4 · F4 variable que tenga un costo marginal de
F1 æ F1 ≠ 2 · F4 menor valor,
; es decir <x1 . Sale de la base x4 ya
60 60 20
V1 æ V1 ≠ (2 ≠ M) · F4 que min , , = 12
3 5 1

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 61 / 110

Algoritmo simplex. Ejemplo: Cajas

min 3 2 0 0 0 0 M
cB xB x1 x2 x3 x4 x5 x6 a1 b
0 x3 0 0 1 -0.6 0 -0.4 0 24
3 x1 1 0 0 0.2 0 0.8 0 12
M a1 0 0 0 -0.2 -1 -0.8 1 8
2 x2 0 1 0 0 0 -1 0 30
96 + 8M 0 0 0 0.2M M 0.8M 0 Ø0
-0.6 - 0.4
1
F2 æ · F2 Es una tabla óptima ya que todos los costos
5 marginales son Ø 0, sin embargo una variable
F3 æ F3 ≠ F2
F4 æ F4 artificial forma parte de la base y toma un
F1 æ F1 ≠ 3 · F2 valor estrictamente positivo, por lo tanto se
V2 æ V2 ≠ (3 ≠ M) · F2 trata de un problema no factible.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 62 / 110

Algoritmo simplex. Ejemplo. Método de las dos fases

Ejemplo: circular y folleto publicitario

Resuelve el problema planteado en las diapositivas 14 y 15, sobre
circulares y folletos publicitarios, aplicando el método de las dos fases.

Y Y
_
_
_max 0.3x1 + 0.1x2 _
_
_max 0.3x1 + 0.1x2 + 0x3 + 0x4 + 0x5 + 0x6
_
_ _
_
_
_
_s.a x2 Ø x 1 _
_
_s.a x1 ≠ x2 + x 3 = 0
_
_ _
_
] x1 Æ 4000 ] x1 + x4 = 4000
∆
_
_
_ 2x1 ≠ x2 Ø 1000 _
_
_ 2x1 ≠ x2 ≠ x5 = 1000
_
_ _
_
_
_
_
_
2x1 + x2 Æ 14000 _
_
_
_
2x1 + x2 + x6 = 14000
_
[ _
[
x1 Ø 0, x2 Ø 0 xi Ø 0, i = 1, . . . , 6

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 63 / 110

Algoritmo simplex. Ejemplo. Método de las dos fases
Observamos que inicialmente no tenemos la matriz identidad, por lo tanto debemos
añadir variables artificiales para conseguirla:
Y
_
_ min a1
_
_
_
_
_ s.a x1 ≠ x 2 + x 3 = 0
_
] x1 + x4 = 4000
1ª fase :
_
_
_ 2x1 ≠ x2 ≠ x5 +a1 = 1000
_
_
_
_ 2x1 + x2 + x6 = 14000
_
[
xi Ø 0, i = 1, . . . , 6; a1 Ø 0
De manera que la tabla inicial del simplex queda de la siguiente manera:
min 0 0 0 0 0 0 1
cB xB x1 x2 x3 x4 x5 x6 a1 b
0 x3 1 -1 1 0 0 0 0 0
0 x4 1 0 0 1 0 0 0 4000
1 a1 2 -1 0 0 -1 0 1 1000
0 x6 2 1 0 0 0 1 0 14000
-2 1 0 0 1 0 0 ⇤0
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 64 / 110
Algoritmo simplex. Ejemplo. Método de las dos fases

min 0 0 0 0 0 0 1
cB xB x1 x2 x3 x4 x5 x6 a1 b
0 x3 1 -1 1 0 0 0 0 0
0 x4 1 0 0 1 0 0 0 4000
1 a1 2 -1 0 0 -1 0 1 1000
0 x6 2 1 0 0 0 1 0 14000
1000 -2 1 0 0 1 0 0 ⇤0
Es una tabla no óptima ya que los costos marginales no son Ø 0. Entra a la
base la variable que ;
tenga un menor costo marginal,
< es decir x1 . Sale de la
0 4000 1000 14000
base x3 , ya que min , , , =0
1 1 2 2

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 65 / 110

Algoritmo simplex. Ejemplo. Método de las dos fases

min 0 0 0 0 0 0 1
cB xB x1 x2 x3 x4 x5 x6 a1 b
0 x1 1 -1 1 0 0 0 0 0
0 x4 0 1 -1 1 0 0 0 4000
1 a1 0 1 -2 0 -1 0 1 1000
0 x6 0 3 -2 0 0 1 0 14000
1000 0 -1 2 0 1 0 0 ⇤0
Es una tabla no óptima ya que los costos
F1 æ F1
marginales no son Ø 0. Entra a la base la
F2 æ F2 ≠ F1
variable que tenga un menor costo marginal,
F3 æ F3 ≠ 2 · F1
es decir
; x2 . Sale de la base
< a1 ya que
F4 æ F4 ≠ 2 · F1 4000 1000 14000
V1 æ V1 + 2 · F1 min , , = 1000
1 1 3

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 66 / 110

Algoritmo simplex. Ejemplo. Método de las dos fases

min 0 0 0 0 0 0 1
cB xB x1 x2 x3 x4 x5 x6 a1 b
0 x1 1 0 -1 0 -1 0 1 1000
0 x4 0 0 1 1 1 0 -1 3000
0 x2 0 1 -2 0 -1 0 1 1000
0 x6 0 0 4 0 3 1 -3 11000
0 0 0 0 0 0 0 1 ⇤0
Es una tabla óptima ya que todos los costos
F3 æ F3 marginales son Ø 0. Ahora resolvemos la 2ª
F2 æ F2 ≠ F3 fase, aplicando el algoritmo simplex al
F1 æ F1 + F3 problema original, como SFB la que
F4 æ F4 ≠ 3 · F1 acabamos de obtener en la primera fase, y
V2 æ V2 + F3 eliminando las variables artificiales. Además,
se deben recalcular los costos marginales.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 67 / 110

Algoritmo simplex. Ejemplo. Método de las dos fases

max 0.3 0.1 0 0 0 0

cB xB x1 x2 x3 x4 x5 x6 b
0.3 x1 1 0 -1 0 -1 0 1000
0 x4 0 0 1 1 1 0 3000
0.1 x2 0 1 -2 0 -1 0 1000
0 x6 0 0 4 0 3 1 11000
400 0 0 0.5 0 0.4 0 ⇥0
Es una tabla no óptima ya que los costos marginales no son Æ 0. Entra a la
base la variable que tenga un costo
; marginal <de mayor valor, es decir x3 , y
3000 11000
sale de la base x6 , ya que min , = 2750.
1 4

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 68 / 110

Algoritmo simplex. Ejemplo. Método de las dos fases

max 0.3 0.1 0 0 0 0

cB xB x1 x2 x3 x4 x5 x6 b
0.3 x1 1 0 0 0 -1/4 1/4 3750
0 x4 0 0 0 1 1/4 -1/4 250
0.1 x2 0 1 0 0 1/2 1/2 6500
0 x3 0 0 1 0 3/4 1/4 2750
1775 0 0 0 0 0.025 -0.125 ⇥0
1
F4 æ · F4 Es una tabla no óptima ya que los costos
4
F3 æ F3 + 2 · F4 marginales no son Æ 0. Entra a la base x5 y
F2 æ F2 ≠ F4 sale ;
de la base x4 , ya que:
<
F1 æ F1 + F4 250 6500 2750
1 min , , = 1000
V1 æ V1 ≠ · F4 1/4 1/2 3/4
2

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 69 / 110

Algoritmo simplex. Ejemplo. Método de las dos fases

max 0.3 0.1 0 0 0 0

cB xB x1 x2 x3 x4 x5 x6 b
0.3 x1 1 0 0 1 0 0 4000
0 x5 0 0 0 4 1 -1 1000
0.1 x2 0 1 0 -2 0 1 6000
0 x3 0 0 1 -3 0 1 2000
1800 0 0 0 -0.1 0 -0.1 Æ0
F2 æ 4 · F2
1 Es una tabla óptima ya que todos los costos
F3 æ F3 ≠ · F2
2 marginales son Æ 0. Por lo tanto se tendrán
3
F4 æ F2 ≠ · F2 que imprimir 4000 folletos publicitarios y
4
1 6000 circulares publicitarias, para obtener un
F1 æ F1 + · F2 beneficio máximo de 1800 euros.
4
V2 æ V2 ≠ 0.025 · F2

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 70 / 110

Índice

1 Introducción

2 Formulación de un problema de programación lineal (PPL)

3 Resolución gráfica de un PPL de 2 variables

4 Resolución de un PPL. Algoritmo Simplex

5 Teoría de la Dualidad

6 Precios sombra

7 Análisis de sensibilidad
El problema dual

Ejemplo: drones
Una empresa elabora dos tipos de drones: 4MX500 y 4MX800. En su
producción destacan dos procesos: el de ensamblado final (P1 ) y el de su
comprobación (P2 ). Mensualmente se disponen de 2000 horas para P1 y
1000 para P2 . Los tiempos requeridos por cada tipo de dron en los procesos
son:
Horas requeridas Disponibilidad
Proceso 4MX500 4MX800 Mensual
P1 6 4 2000 h.
P2 2 4 1000 h.
Además, el beneficio por vender un dron 4MX500 es de 400 u.m y un dron
4MX800 600 u.m.
Con la información de la que dispones, plantea y resuelve un
problema de programación lineal que determine el plan de producción
que maximice el beneficio total.
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 72 / 110
El problema dual
El problema quedaría planteado de la siguiente manera:
x1 : número de drones de tipo 4MX500
x2 : número de drones de Y
tipo 4MX800.
_
_
_ max 400x1 + 600x2
_
_
]s.a. 6x + 4x Æ 2000
1 2
_
_
_ 2x1 + 4x2 Æ 1000
_
_
[ x1 Ø 0, x2 Ø 0

La solución óptima es x1 = 250, x2 = 125 y un beneficio de 175000 u.m.

Cambiamos el enfoque
Hacemos un cambio de enfoque en el problema. Ahora el negocio es vuestro
y os lo quiero alquilar. Os voy a pagar por cada hora de proceso, y1 u.m. por
cada una de las 2000 horas de P1 e y2 u.m. por cada una de las 1000 de P2 .
Además, vamos a actuar sensatamente: vosotros no queréis perder dinero y
yo no me dejo engañar. ¿Cuál es el valor de y1 e y2 ?
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 73 / 110
El problema dual

Se pueden definir las siguientes variables de decisión:

y1 : coste por hora de alquilar un dron del tipo 4MX500
y2 : coste por hora de alquilar un dron del tipo 4MX800
En este caso, lo que se quiere es minimizar el coste por el alquiler de los
drones, por lo tanto la función objetivo será:
min 2000y1 + 1000y2

Por otro lado, lo que os pague por el alquiler del dron debe ser al menos
igual al beneficio que obtendríais al venderlos, es decir:

6y1 + 2y2 Ø 400

4y1 + 4y2 Ø 600

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 74 / 110

El problema dual

El problema de programación lineal que tendríais con este segundo enfoque

sería: Y
_
_
_ min 2000y1 + 1000y2
_
_
]s.a. 6y + 2y Ø 400
1 2
_
_
_ 4y1 + 4y2 Ø 600
_
_
[ y1 Ø 0, y2 Ø 0

La solución óptima es y1 = 25, y2 = 125 y unos costes de 175000 u.m.

¿Qué relación hay entre los dos problemas que hemos planteado?
Y Y
_
_
_max 400x1 + 600x2 _
_
_min 2000y1 + 1000y2
_
_ _
_
]s.a. 6x1 + 4x2 Æ 2000 ]s.a. 6y1 + 2y2 Ø 400
[P] : [D] :
_
_
_ 2x1 + 4x2 Æ 1000 _
_
_ 4y1 + 4y2 Ø 600
_
_ _
_
[ x1 Ø 0, x2 Ø 0 [ y1 Ø 0, y2 Ø 0

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 75 / 110

El problema dual

Asociado a un problema de programación lineal aparece otro problema de

programación lineal denominado problema dual (asociado al primero). En
general nos referiremos al primero como problema primal, denotado
mediante [P], y al segundo como problema dual denotado con [D].
Y Y
]max f (x) = cx ]min g(y) = bÕ y
_
_ _
_
[P] : s.a. Ax Æ b [D] : s.a. AÕ y Ø cÕ
_
_ _
_
[ xØ0 [ yØ0
El problema dual de uno dado se puede definir para cualquier problema de
programación lineal.
El problema dual del problema dual es el problema primal.
Cada variable dual proporcionará información sobre cuánto variará la función
objetivo del modelo original por cada unidad que se incremente el vector de
recursos a la que se refiere esa variable dual.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 76 / 110

El problema dual

Construcción del problema dual

1 Si el problema primal es de máximo el dual es de mínimo y,
recíprocamente, si el problema primal es de mínimo su dual es de
máximo.
2 La matriz de coeficientes del problema dual es la traspuesta de la
matriz de coeficientes del problema original.
3 El vector de costos del problema dual es el vector de recurso del
problema primal.
4 El vector de recursos del problema dual es el vector de costos del
problema primal.
5 Cada restricción del problema primal da lugar a una variable en el
problema dual y, cada variable en el problema primal da lugar a una
restricción del problema dual.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 77 / 110

El problema dual

Reglas de dualización
Primal Dual
(Dual) (Primal)
max min
Restricción Æ Variable Ø 0
Restricción = Variable no restringida
Restricción Ø Variable Æ 0
Variable Ø 0 Restricción Ø
Variable no restringida Restricción =
Variable Æ 0 Restricción Æ
Matriz A Matriz A’
Si el problema primal es de máximo se lee de izquierda a derecha y, si el
problema primal es de mínimo de derecha a izquierda.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 78 / 110

El problema dual. Ejemplo

Ejemplo 1
Y
Y _
_min 7y1 + 8y2
_
_
_max 3x1 + 2x2 + 4x3 _
_
_
]s.a. y1 + y2 Ø 3
_
_ _
_
]s.a. x1 + 2x2 ≠ x3 Æ 7
[P] : [D] : 2y1 + y2 Ø 2
_
_ x1 + x 2 + x3 Æ 8 _
_
_
_
_
_
_
_ ≠y1 + y2 Æ 4
[ x1 Ø 0, x2 Ø 0, x3 Æ 0 _
_
[
y1 Ø 0, y2 Ø 0

Ejemplo 2
Y Y
_
_
_
min 3x1 + 7x2 + x3 _
_
_
max 7y1 + 8y2 + 5y3
_
_ _
_
]s.a. x1 + 2x2 + x3 Æ 7 ]s.a. y1 + 2y2 + 3y3 Ø 3
_
_ _
_
[P] : 2x1 + 3x2 ≠ x3 Ø 8 [D] : 2y1 + 3y2 + y3 = 7
_
_ _
_
_
_
_
_ 3x1 + x2 + 2x3 = 5 _
_
_
_ y1 ≠ y2 + 2y3 Æ 1
_
[ _
[
x1 Æ 0, x2 œ R, x3 Ø 0 y1 Æ 0, y2 Ø 0, y3 œ R

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 79 / 110

El problema dual

Teorema de la dualidad débil

Si x e y son soluciones factibles de un par de problemas primal (máximo) y
dual (mínimo), respectivamente, entonces se verifica:
f (x) = cx Æ bÕ y = g(y)

Es decir, para cualquier par de soluciones factibles de un problema primal y

su dual, el valor de la función objetivo del problema de máximo es menor o
igual que el valor de la función objetivo del problema de mínimo.

Criterio de optimalidad
Si existen x e y soluciones factibles del [P] y [D], respectivamente, tales que
los valores de las funciones objetivos coinciden, f (x) = g(y), entonces
dichas soluciones son óptimas para sus respectivos problemas.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 80 / 110

El problema dual

Teorema fundamental de la dualidad

Dado un problema primal y su dual solo una de las siguientes afirmaciones
es cierta:
[P] tiene solución óptima (finita) … [D] tiene solución óptima (finita).
[P] es no factible ∆ [D] es no factible o [D] tiene solución no acotada.
[D] es no factible ∆ [P] es no factible o [P] tiene solución no acotada.
[P] tiene solución no acotada ∆ [D] es no factible.
[D] tiene solución no acotada ∆ [P] es no factible.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 81 / 110

El problema dual
Teorema de la Holgura Complementaria
Sean x e y soluciones factibles del [P] y [D], respectivamente, entonces x e y
son soluciones óptimas para sus problemas respectivos si y solo si se verifica:
! Õ "
y A ≠ c x + yÕ (b ≠ Ax) = 0

Condiciones de la holgura complementaria

Sean u y v los valores de las variables de holgura del problema primal y dual,
respectivamente.
Como x e y son soluciones factibles ∆ x Ø 0, y Ø 0, u Ø 0 y v Ø 0
Además, de ! Õ "
0 = y A ≠ c x + yÕ (b ≠ Ax) = yÕ u + vÕ x
se obtiene que yÕ u = 0 y vÕ x = 0, que se puede expresar de forma
equivalente como:
xj vj = 0, ’j = 1, . . . , n
yi ui = 0, ’i = 1, . . . , m
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 82 / 110
El problema dual. Ejemplo
Una empresa ha decidido comenzar a fabricar dos productos nuevos (P1 y P2).
Cada producto se fabricará en lotes de 20 unidades, de manera que la tasa de
producción queda definida como el número de lotes que se producen a la semana.
La planta tiene tres plantas de producción, y cada producto necesita una horas de
fabricación en cada una de las plantas, como se muestra en la tabla. La sección de
comercialización ha concluido que la compañía puede vender todos los productos
que se puedan fabricar en las plantas. Por otro lado, cada planta de producción,
tiene un tiempo de producción disponible a la semana, en horas, que no se puede
superar.
Tiempo de producción por lote
Planta P1 P2 Disponibilidad
1 1 0 4
2 0 2 12
3 3 2 18
Ganancia por lote 3.000 Ä 5.000 Ä
Plantea un problema de programación lineal que permita determinar
cuántos lotes de cada producto se tienen que fabricar por semana para
maximizar los beneficios de la empresa.
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 83 / 110
El problema dual. Ejemplo
Definimos las variables de decisión:
x1 : número de lotes del producto P1 que se fabrican en una semana
x2 : número de lotes del producto P2 que se fabrican en una semana

Y
_
_
_
max 3000x1 + 5000x2
_
_
]s.a. x1 Æ 4
_
_
2x2 Æ 12
_
_
_
_
_
_ 3x1 + 2x2 Æ 18
_
[
x1 Ø 0, x2 Ø 0

La solución óptima que se obtiene es: x1 = 2 y x2 = 6, con un beneficio de

36.000 Ä.
¿Podrías formular el problema dual asociado y obtener su solución sin
necesidad de resolverlo gráficamente ni aplicando el algoritmo
simplex? SÍ
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 84 / 110
El problema dual. Ejemplo

Y
_
_max 3000x1 + 5000x2 Y
_
_
_
_
_
_min 4y1 + 12y2 + 18y3
]s.a. x1 Æ 4
_
_ _
_
]s.a. y1 + 3y3 Ø 3000
[P] : 2x2 Æ 12 [D] :
_
_ _
_ 2y3 + 2y3 Ø 5000
_
_
_ 3x1 + 2x2 Æ 18 _
_
_
_
_
[
[ y1 Ø 0, y2 Ø 0, y3 Ø 0
x1 Ø 0, x2 Ø 0
Los problemas en forma estándar quedan de la siguiente manera:
Y
_
_max 3000x1 + 5000x2 Y
_
_
_ _
_min 4y1 + 12y2 + 18y3
_
_
_s.a. x1 + u1 = 4 _
_
_
]s.a. y1 + 3y3 ≠ v1 = 3000
_
_ _
_
] 2x2 + u2 = 12
[P] : [D] : 2y2 + 2y3 ≠ v2 = 5000
_
_ 3x1 + 2x2 + u3 = 18 _
_
_
_
_
_
_
_ y1 Ø 0, y2 Ø 0, y3 Ø 0
_
_
_ x1 Ø 0, x2 Ø 0 _
_
[
_
_
[ v1 Ø 0, v2 Ø 0
u1 Ø 0, u2 Ø 0, u3 Ø 0
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 85 / 110
El problema dual. Ejemplo
Sabemos que x1 = 2 y x2 = 6, y tenemos el siguiente conjunto de
ecuaciones obtenidas de los problemas dual y primal, y de las condiciones de
holgura
Y complementarias. Y
_
_
_ x1 + u1 = 4 _
_
_2 + u1 = 4 æ u1 = 2
_
_ _
_
_
_
_ 2x2 + u2 = 12 _
_
_12 + u2 = 12 æ u2 = 0
_
_ _
_
_
_
_
_ 3x 1 + 2x 2 + u 3 = 18 _
_
_
_6 + 12 + u3 = 18 æ u3 = 0
_
_ _
_
_
_
_ y 1 + 3y 3 ≠ v 1 = 3000 _
_
_y1 + 3y3 ≠ v1 = 3000 æ y3 = 1000
_
_ _
_
]2y + 2y ≠ v = 5000 ]2y + 2y ≠ v = 5000 æ y = 1500
2 3 2 2 3 2 2
=∆
_
_
_ x1 · v1 = 0 _
_
_2 · v1 = 0 æ v1 = 0
_
_ _
_
_
_
_
_
x 2 · v 2 = 0 _
_
_
_
6 · v2 = 0 æ v2 = 0
_
_ _
_
_
_
_ y 1 · u 1 = 0 _
_
_y1 · 2 = 0 æ y1 = 0
_
_ _
_
_
_
_ y2 · u2 = 0 _
_
_y2 · u2 = 0 æ y2 Ø 0
_
_ _
_
[y · u = 0 [y · u = 0 æ y Ø 0
3 3 3 3 3
De manera que la solución al problema primal es: y = (0, 1500, 1000).
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 86 / 110
Índice

1 Introducción

2 Formulación de un problema de programación lineal (PPL)

3 Resolución gráfica de un PPL de 2 variables

4 Resolución de un PPL. Algoritmo Simplex

5 Teoría de la Dualidad

6 Precios sombra

7 Análisis de sensibilidad
Precios sombra

Precios sobra para el recurso i (bi ): Miden el valor marginal del recurso, es
decir la tasa a la que la función objetivo puede aumentar si se incrementa
(un poco) la cantidad que se proporciona de ese recurso bi .

Restricción de atadura: son aquellas restricciones para las que se cumple la

igualdad para la solución óptima. Los precios sombra de estos recursos son
positivos, y se denominan bienes escasos.

Por el contrario, los recursos que corresponden a precios sombra cero, se

dicen bienes libres, y su incremento no produce beneficio en ningún caso.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 88 / 110

Precios sombra. Ejemplo
Un empresario pretende fabricar dos tipos diferentes de congeladores denominados
A y B. Cada uno de ellos debe pasar por tres operaciones antes de su
comercialización: ensamblaje, pintado y control de calidad. Los congeladores
requiere, respectivamente, 2.5 y 3 horas de ensamblaje, 3 y 0.6 kg de esmalte para
su pintado y 14 y 10 horas de control de calidad. Los costes totales de fabricación
por unidad son: 300 y 280, respectivamente, y los precios de venta 520 y 480, todos
ellos en euros. El empresario dispone semanalmente de 4500 horas para ensamblaje,
de 3400 kg de esmalte y de 20000 horas para control de calidad. Los estudios de
mercado muestran que la demanda semanal de congeladores no supera las 1700
unidades y que, en particular, la de tipo A es de, al menos 600 unidades. Se desea:
1 Formular un modelo de programación lineal que indique cuántos congeladores
deben fabricarse de cada tipo para que el beneficio sea máximo, teniendo en
cuenta el estudio de demanda.
2 Resolverlo mediante el algoritmo simplex.
3 Determinar los precios sombra de las horas de ensamblaje y control de calidad.
Al fabricante le ofrecen disponer de 200 horas para ensamblaje con un coste
adicional de 7500 euros. ¿Debería aceptar la oferta?
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 89 / 110
Precios sombra. Ejemplo

Sean las variables de decisión:

x1 : número de congeladores de tipo A a fabricar
x2 : número de congeladores de tipo B a fabricar

Y
_
_
_max (520 ≠ 300)x1 + (480 ≠ 280)x2
_
_
_
_
_
_
s.a 2.5x1 + 3x2 Æ 4500
_
_
_
_
] 3x1 + 0.6x2 Æ 3400
14x1 + 10x2 Æ 20000
_
_
_
_
_
_ x1 + x2 Æ 1700
_
_
_
_
_ x1 Ø 600
_
_
[ x1 Ø 0, x2 Ø 0

La solución que se obtiene es: x1 = 882.3529 y x2 = 764.7059.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 90 / 110

Precios sombra. Ejemplo
Analizamos ahora las variables de holgura y su interpretación, obviando que
algunas de ellas deberían ser enteras:
opt
x1 882.3529
x2 764.7059
s2 294.1176
s4 52.9412
s5 282.3529
Observamos que no sobran horas disponibles para ensamblaje, ya que la
variable de holgura toma el valor s1 = 0.
Hay 294.1176 kg de esmalte que no se consumen del total de 3400 kg,
ya que s2 = 294.1176.
Las horas de control de calidad se consumen todas, s3 = 0.
Hay 52.9412 congeladores que se podrían fabricar de más hasta
alcanzar el máximo de 1700, s4 = 52.9412.
Se fabrican 282.3529 congeladores de tipo A por encima del mínimo
estipulado de 600, ya que s5 = 282.3529.
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 91 / 110
Precios sombra. Ejemplo

Ahora vamos a analizar el problema dual:

Tenemos tres bienes libres correspondientes a los kg de esmalte, número de

congeladores que se pueden fabricar sin alcanzar el máximo permitido y
exceso de fabricación de congeladores de tipo A.
Por otro lado, tenemos dos bienes escasos correspondientes a las horas de
ensamblaje y a las horas de control de calidad. Es decir, el aumento de la
disponibilidad de horas de ensamblaje y horas de control de calidad puede
repercutir en una mejorar del beneficio, ya que sus precios sobra y1 = 35.29
e y2 = 9.4 son positivos.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 92 / 110

Precios sombra. Ejemplo

Nos plantean aumentar hasta 200 horas el tiempo disponible de ensamblaje

a un coste de 7500 euros.
A través del precio sombra y1 , podemos averiguar si obtenemos un aumento
en el beneficio, ya que aumenta el valor del recurso (b1 ).

FO = 200 · 35.3 ≠ 7500 = ≠441.176

No se produce un aumento en el beneficio, por lo tanto a ese coste no
merece la pena incrementar las horas de ensamblaje. Se debería intentar de
reducir el coste adicional para poder aumentar el beneficio.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 93 / 110

Índice

1 Introducción

2 Formulación de un problema de programación lineal (PPL)

3 Resolución gráfica de un PPL de 2 variables

4 Resolución de un PPL. Algoritmo Simplex

5 Teoría de la Dualidad

6 Precios sombra

7 Análisis de sensibilidad
Análisis de sensibilidad

En los modelos de programación lineal los coeficientes de la función

objetivo, así como de las restricciones, se dan como datos de entrada
fijos del modelo.
En los problemas reales, los valores de estos coeficientes no están, en
general, perfectamente fijados, debido a que dependen de parámetros
no controlables: fluctuaciones en las demandas y/o costes de materias
primas y/o costes de energia, etc, y no pueden ser predichas con
exactitud antes de que el problema sea resuelto. También podemos
estar interesados en estudiar como varía la solución del problema si
cambiamos algún parámetro intencionadamente: ¿qué ocurriría si los
costos aumentan un 10 %?
Cada variación en los valores de los datos el problema generará un
nuevo problema de programación lineal que se resolverá a partir de la
solución del original.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 95 / 110

Análisis de sensibilidad
Cambio en el vector de costes
Sea ĉ = c + c, el nuevo vector de costes.
Para que la solución obtenida a través del algoritmo simplex continue siendo
óptima, hay que comprobar cómo son los costos marginales.
Si se modifica un costo marginal del vector de costes, de una variable
no básica, solo cambiará su costo marginal asociado.
CMnuevo = CMviejo + cj
Si se modifica un costo marginal del vector de costes, de una variable
básica, todos los costos marginales se modifican.
CMnuevo = CMviejo ≠ cB B ≠1 Aj

Cambio en el vector de recursos

Sea ^b = b+ b, el nuevo vector de recursos.
En el desarrollo del algoritmo simplex, hemos visto que b = B ≠1 b Ø 0, por
lo tanto si incrementamos el vector de recursos, para conservar la solución
óptima se deberá cumplir: B ≠1 ^b Ø 0.
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 96 / 110
Análisis de sensibilidad

Incorporación de una nueva variable de decisión

Sea xn+1 Ø 0 una nueva variable de decisión con coeficiente cn+1 en la
función objetivo y con vector columna An+1 en A.
Actualizamos su información:
Yn+1 = B ≠1 An+1
cn+1 ≠ zn+1 = cn+1 ≠ cB B ≠1 An+1
Se incorpora la información a la tabla óptima del problema original y se
aplica el algoritmo simplex.

Incorporación de una nueva restricción

Se comprueba la nueva si restricción:
si la SFB actual la verifica, entonces sigue siendo la solución óptima.
en caso contrario, lo vemos a través de un ejemplo.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 97 / 110

Análisis de sensibilidad. Ejemplo
Planificación de la producción de tres tipos de cerveza:
x1 x2 x3 Disponibilidad
Malta 2 1 2 30
Levadura 1 2 2 45
Beneficio 4 7 3
Y
_
_max 4x1 + 7x2 + 3x3
_
]s.a 2x1 + x2 + 2x3 Æ 30
_
_
_ x1 + 2x2 + 2x3 Æ 45
[
x1 Ø 0, x2 Ø 0, x3 Ø 0
La tabla óptima después de aplicar el algoritmo simplex es la siguiente:
max 4 7 3 0 0
cB xB x1 x2 x3 x4 x5 b
4 x1 1 0 2/3 2/3 -1/3 5
7 x2 0 1 2/3 -1/3 2/3 20
160 0 0 -13/3 -1/3 -10/3 Æ0
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 98 / 110
Análisis de sensibilidad. Ejemplo
1. ¿Cuál es la solución si la disponibilidad de la malta aumenta en 9 u.?
2. ¿Cuál es la solución si la disponibilidad de la levadura es de 66 u.?
3. ¿Cuántas unidades podría aumenta la disponibilidad de la malta para
que la solución continuase siendo óptima? ¿Y la disponibilidad de la
levadura?
4. Si el beneficio de la cerveza 3 aumenta a 6 u., ¿cuál es la solución
óptima del problema?
5. ¿Cuál es el mínimo beneficio de x3 para que sea rentable su producción?
6. Si el beneficio de la cerveza 3 es de 8 u., ¿cuál es la solución óptima del
problema?
7. Si el beneficio de la cerveza 1 es de 3 u.m., ¿cuál es la nueva solución
óptima?
8. Se esta considerando la elaboración de un cuarto tipo de cerveza, una
cerveza sin alcohol, que requiere de una unidad de malta y una unidad
de levadura por unidad de cerveza, y cuyo beneficio de venta es de 5
u.m. ¿Merecerá la pena su elaboración? ¿En qué cantidad?
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 99 / 110
1. ¿Cuál es la solución si la disponibilidad de la malta aumenta en 9
unidades? A B A B
^ 30 9
b=b+ b= +
45 0
A BA B A B
2/3 ≠1/3 39 11
B ≠1 b̂ = =
≠1/3 2/3 45 17
De manera que la base, sigue siendo óptima con x1 = 11 y x2 = 17. Además
se tiene un beneficio de 163 u.m.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 100 / 110

2. ¿Cuál es la solución si la disponibilidad de la levadura es de 66
unidades? A B A B A B
^ 30 0 30
b=b+ b= + =
45 21 66
A BA B A B
2/3 ≠1/3 30 ≠2
B ≠1 b̂ = =
≠1/3 2/3 66 34
En este caso llegamos a una base no óptima, y determinamos que con la
nueva disponibilidad de levadura se trata de un problema no factible.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 101 / 110

3. ¿Cuántas unidades podría aumenta la disponibilidad de la malta
para que la solución continuase siendo óptima? ¿Y la disponibilidad
de la A
levadura?
B A B A B A B A B A B
^ 30 ” 30 + ” ^ 30 0 30
bm = + = bl = + =
45 0 45 45 ” 45 + ”
Q R
A BA B 15 + 2” I
2/3 ≠1/3 30 + ” c 3 d ” Ø ≠7.5
B b̂ =
≠1 = a 60 ≠ ” b Ø 0 ∆
≠1/3 2/3 45 60 Ø ”
3
Por lo tanto la disponibilidad de la malta podría aumentar en hasta 60
unidades para que la solución continuase siendo óptima.
Q R
A BA B 15 ≠ ” I
2/3 ≠1/3 30 c 3 d 15 Ø ”
B b̂ =
≠1 = a 60 + 2” b Ø 0 ∆
≠1/3 2/3 45 + ” ” Ø ≠30
3
Por lo tanto la disponibilidad de la levadura podría aumentar en hasta 15
unidades para que la solución continuase siendo óptima.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 102 / 110

4. Si el beneficio de la cerveza 3 aumenta a 6 u., ¿cuál es la solución
óptima del problema?
Como la variable x3 no es una variable básica, el único costo marginal que
va a cambiar es el asociado a dicha variable. En la solución actual este coste
es de ≠13/3.
13 4
CMnuevo = CMviejo + cj = ≠ + 3 = ≠ Æ 0
3 3
Por lo tanto, la solución se mantiene óptima, sin modificarse ninguna
variable básica ni sus valores, ni el valor de la función objetivo.
5. ¿Cuál es el mínimo beneficio de x3 para que sea rentable su
producción
Para que sea rentable su producción x3 debe entrar en la base, y esto ocurre
13
cuando CMnuevo = CMviejo + cj = ≠ + cj > 0.
3
13
Es decir el precio de x3 debe incrementarse en al menos u.m.
3

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 103 / 110

6. Si el beneficio de la cerveza 3 es de 8 u., ¿cuál es la solución óptima del
problema?
13 2
CMnuevo = CMviejo + cj = ≠ + 2 = ⇥ 0
3 3
En este caso la solución no se mantiene óptima, y por lo tanto dicha modificación
implica continuar con la resolución del problema a través del algoritmo simplex.
Tras realizar el cambio en el vector de costos la tabla que tenemos es la siguiente:
max 4 7 3 0 0
cB xB x1 x2 x3 x4 x5 b
4 x1 1 0 2/3 2/3 -1/3 5
7 x2 0 1 2/3 -1/3 2/3 20
160 0 0 2/3 -1/3 -10/3 Æ0
Tras aplicar el algoritmo simplex, obtenemos:
max 4 7 8 0 0
cB xB x1 x2 x3 x4 x5 b
8 x3 3/2 0 1 2/3 -1/2 15/2
7 x2 -1 1 0 -1/3 1 15
160 -1 0 0 -1 -3 Æ0
Nueva solución óptima: x1 = 0, x2 = 15, x3 = 7.5, y un beneficio de 165 u.m.
Begoña Álvarez Tena Programación Lineal Curso 2024-2025 104 / 110
7. Si el beneficio de la cerveza 1 es de 3 u.m., ¿cuál es la nueva
solución óptima?
Como la variable x1 es una variable básica, debemos calcular nuevamente
todos los costos marginales de las variables no básicas.

CMnuevo = CMviejo ≠ cB B ≠1 Aj
A BA B
13 1 2 2/3 ≠1/3 2 13 2 11
x3 æ CMnuevo = ≠ ≠ ≠1 0 =≠ + =≠
3 ≠1/3 2/3 2 3 3 3
A BA B
1 1 2 2/3 ≠1/3 1 1 2 1
x4 æ CMnuevo = ≠ ≠ ≠1 0 =≠ + =
3 ≠1/3 2/3 0 3 3 3
A BA B
10 1 2 2/3 ≠1/3 0 10 1 11
x5 æ CMnuevo = ≠ ≠ ≠1 0 =≠ ≠ =≠
3 ≠1/3 2/3 1 3 3 3
De
3 manera que el vector4de costos marginales es el siguiente:
11 1 11
0 0 ≠ ≠ ⇥ 0, por lo tanto no se trata de una solución
3 3 3
óptima y debemos aplicar el algoritmo simplex.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 105 / 110

7. Si el beneficio de la cerveza 1 es de 3 u.m., ¿cuál es la nueva
solución óptima?
max 3 7 3 0 0
cB xB x1 x2 x3 x4 x5 b
3 x1 1 0 2/3 2/3 -1/3 5
7 x2 0 1 2/3 -1/3 2/3 20
160 0 0 -11/3 1/3 -11/3 Æ0
Tras aplicar el algoritmo simplex, obtenemos:
max 3 7 3 0 0
cB xB x1 x2 x3 x4 x5 b
0 x4 3/2 0 1 1 -1/2 15/2
7 x2 1/2 1 1 0 1/2 45/2
157.5 -1/2 0 -4 0 -7/2 Æ0
Nueva solución óptima: x1 = 0, x2 = 22.5, x3 = 0, y se obtendrá un
beneficio de 157.5 u.m.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 106 / 110

8. Se esta considerando la elaboración de un cuarto tipo de cerveza, una
cerveza sin alcohol, que requiere de una unidad de malta y una unidad de
levadura por unidad de cerveza, y cuyo beneficio de venta es de 5 u.m.
¿Merecerá la pena su elaboración? ¿En qué cantidad?
Creamos una nueva variable de decisión x6 que indica
3 4 la cantidad de cerveza a
1
elaborar del cuarto tipo de cerveza. c6 = 5 y A6 =
1
3 43 4 3 4
2/3 ≠1/3 1 1/3
Calculamos Y6 = B A6 =
≠1
=
≠1/3 2/3 1 1/3
y el costo marginal 3 43 4
! " 2/3 ≠1/3 1 11 4
c6 ≠ z6 = c6 ≠ cB B A6 = 5 ≠
≠1
4 7 =5≠ =
≠1/3 2/3 1 3 3
Añadiendo esta información a la óptima del problema original, observamos que se
trata de una tabla no óptima.
max 4 7 3 0 0 5
cB xB x1 x2 x3 x4 x5 x6 b
4 x1 1 0 2/3 2/3 -1/3 1/3 5
7 x2 0 1 2/3 -1/3 2/3 1/3 20
160 0 0 -13/3 -1/3 -10/3 4/3 ⇥0

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 107 / 110

8. Se esta considerando la elaboración de un cuarto tipo de cerveza,
una cerveza sin alcohol, que requiere de una unidad de malta y una
unidad de levadura por unidad de cerveza, y cuyo beneficio de venta
es de 5 u.m. ¿Merecerá la pena su elaboración? ¿En qué cantidad?
Aplicando el algoritmo simplex obtenemos la siguiente tabla, que si se trata
de una tabla óptima.
max 4 7 3 0 0 5
cB xB x1 x2 x3 x4 x5 x6 b
4 x6 3 0 2 2 -1 1 15
7 x2 0 1 0 -1 1 0 15
180 -4 0 -7 -3 -2 0 Æ0
Por lo tanto si que merecerá la pena su elaboración (la variable ha entrado a
la base). Se elaboraran 15 unidades de la nueva cerveza y 15 unidades de la
cerveza tipo 2. El beneficio que se obtendrá será de 180 u.m.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 108 / 110

9. Problemas de abastecimiento obligan a incluir un tercer
ingrediente, el lúpulo. Se pueden conseguir 30 unidades de lúpulo y se
necesitan 3, 1 y 1 unidades de lúpulo para la cerveza de tipo 1, 2 y 3,
respectivamente.
La restricción que se debe incluir es: 3x1 + x2 + x3 Æ 30
¿La solución actual satisface la nueva restricción? No, 3 · 5 + 20 + 0 ⇥ 30
El procedimiento que se debe seguir es el siguiente:
Despejar de la tabla óptima las variables básicas que aparecen en la
nueva restricción.
Sustituirlas en la restricción.
Añadir la restricción obtenida en la tabla original.
Las ecuaciones relacionadas con las variables básicas que tenemos son:
2 2 1 2 2 1
x1 + x3 + x4 ≠ x5 = 5 ≠æ x1 = ≠ x3 ≠ x4 + x5 + 5
3 3 3 3 3 3
2 1 2 2 1 2
x2 + x3 ≠ x4 + x5 = 20 ≠æ x2 = ≠ x3 + x4 ≠ x5 + 20
3 3 3 3 3 3

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 109 / 110

9. Problemas de abastecimiento obligan a incluir un tercer
ingrediente, el lúpulo. Se pueden conseguir 30 unidades de lúpulo y se
necesitan 3, 1 y 1 unidades de lúpulo para la cerveza de tipo 1, 2 y 3,
respectivamente.
Sustituimos en la nueva 3
restricción que se debe incluir:
4
2 2 1
3x1 + x2 + x3 Æ 30 … 3 ≠ x3 ≠ x4 + x5 + 5 +
3 43 3 3
2 1 2 5 5 1
≠ x3 + x4 ≠ x5 + 20 + x3 Æ 30 … ≠ x3 ≠ x4 + x5 Æ ≠5
3 3 3 3 3 3
La restricción que debemos incorporar a la tabla óptima es:
5 5 1
x3 + x4 ≠ x5 Ø 5. Para incorporarla deberemos añadir una variable de
3 3 3
holgura x6 , además de una variable artificial a1 con ca1 = ≠M. Una vez
añadida la fila a la tabla, deberemos recalcular los costos marginales.
La solución que obtendremos finalmente es: x1 = 3, x2 = 21 y x4 = 3, con
un valor de la función objetivo de 159 u.m.

Begoña Álvarez Tena Programación Lineal Curso 2024-2025 110 / 110