INVESTIGACIÓN OPERATIVA I
APUNTES Y EJERCICIOS
Nadie nos arrebatará del paraíso que él creó
Club de Matemática EPN
Más que simple matemática
Alexander Constante
3
Cuadernos de Matemática
Club de Matemática EPN
Esta página ha sido dejada intencionalmente en blanco.
CUADERNOS DE MATEMÁTICA
CLUB DE MATEMÁTICA EPN
A. CONSTANTE
INVESTIGACIÓN OPERATIVA IAPUNTES Y EJERCICIOS
Nadie nos arrebatará del paraíso que él creó
Club de Matemática EPN
Más que simple matemática
Cuaderno de Matemática del Club de Matemática EPN No. 3
INVESTIGACIÓN OPERATIVA I: APUNTES Y EJERCICIOS
Alexander Constante
Revisión Académica: La obra no ha sido sometida a revisión por el momento
Registro de derecho autoral No. La obra no cuenta con registro por el momento
ISBN: La obra no cuenta con ISBN por el momento
Publicado en línea por el proyecto Alephsub0,Quito, Ecuador.
Primera edición: 2020
c© Club de Matemática EPN 2020
Se permite la distribución de la presente obra.
ÍNDICE GENERAL
CAP. 1 MODELOS DE PROGRAMACIÓN LINEAL 1
1.1 Tipos de Modelos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Esquema de un modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Modelos de Investigación Operativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Programación Lineal (PL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
CAP. 2 GEOMETRÍA DE LA PROGRAMACIÓN LINEAL 23
2.1 Conjuntos Convexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2 Repaso de la Topología en Rn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2.1 Bolas Abiertas y Cerradas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2.2 Conjuntos Abiertos y Cerrados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2.3 Hiperplano de apoyo de un convexo . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3 Punto Extremo de un Convexo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.4 Optimización de Funciones Convexas . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.5 Formulaciones de los problemas de PL . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.6 Posibles resultados de un problema de PL . . . . . . . . . . . . . . . . . . . . . . . . 39
2.7 Desigualdades y Lema de Farkas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.7.1 Interpretación geométrica del Lema de Farkas . . . . . . . . . . . . . . . . . . . . 45
CAP. 3 DUALIDAD DE LA PROGRAMACIÓN LINEAL 49
3.1 Teoremas de la dualidad débil y fuerte . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.2 Esquema de la dualidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.3 Modelos Dinámicos de PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
CAP. 4 MÉTODO DEL SIMPLEX 73
4.1 Propiedades fundamentales de la PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
III
IV Índice general
4.2 Repaso de Gauss-Jordan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.2.1 Tabla Condensada (ecuaciones) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.2.2 Reglas de Pivoteo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.2.3 Reglas de Pivoteo del SIMPLEX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.3 Regla Clásica del SIMPLEX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.3.1 Algoritmo particular del SIMPLEX . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.3.2 Explicación de la Optimalidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.3.3 Soluciones Degeneradas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.4 Algoritmo del SIMPLEX general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.4.1 Método de las dos fases del simplex general . . . . . . . . . . . . . . . . . . . . . . 98
4.4.2 Interpretación de las variables duales y costos reducidos . . . . . . . . . . . . . 106
4.4.3 Análisis de Sensibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
CAP. 5 PROGRAMACIÓN LINEAL ENTERA 109
5.1 Modelos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.1.1 Modelización de problemas PLE . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.1.2 Restricciones Adicionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
PREFACIO
La presente obra es una recopilación de apuntes y ejercicios basados en las clases de la mate-
ria “Investigación Operativa I”, dictada en la carrera de Ingeniería Matemática y Matemática de
la Escuela Politécnica Nacional por el profesor Polo Vaca durante el semestre 2018-B. La trans-
cripción de los apuntes y ejercicios fueron elaborados por Alexander Constante, alumno de esta
materia en el periodo antes mencionado.
Este compendio de apuntes y ejercicios tiene la finalidad de servir como una guía para aque-
llos estudiantes que tomen esta materia. En caso de que el lector encuentre errores puede diri-
girlos a [email protected].
“Investigación Opertiva I: Apuntes y Ejercicios” forma parte de la serie “Cuaderno de Ma-
temática del Club de Matemática EPN”; la cual recolecta apuntes de clase y ejercicios resueltos
generados por estudiantes de la Facultad de Ciencias. El Club de Matemática EPN, junto al
proyecto Alephsub0 y la Asociación de Estudiantes de Matemática e Ingeniería Matemática,
administra la generación y publicación en linea de estos trabajos e invita a la comunidad de
estudiantes que deseen apoyar a este proyecto a sumarse al mismo.
V
CAPÍTULO 1
MODELOS DE PROGRAMACIÓN LINEAL
Un modelo es una estructura que permite medir, establecer rasgos o características en forma
aproximada de un sistema o de un fenómeno físico, biológico, económico, etc. con el objeto de
obtener uno o varios objetivos.
P: ¿Para qué construir modelos?
• Para comprender mejor un fenómeno. Ciertos problemas tienen características ocultas que
permiten describirse en un modelo.
• Para la ayuda en la toma de decisiones.
• Experimentación; se pueden cambiar ciertos parámetros del modelo y estudiar la nueva
solución.
1.1 TIPOS DE MODELOS
a) Físicos o Concretos: tienen características comunes o idénticas con la realidad que se quie-
re modelar. Por ejemplo, la maqueta de un edificio, los dispositivos o procesos reales que
se comportan de igual forma al fenómeno del cual se tomó el modelo y del que se espera
aprender algo.
b) Modelos Abstractos: utilizan el simbolismo de la matemática (parámetros, variables, fun-
ciones, desigualdades) para establecer relaciones en las componentes de un sistema para
plantear un problema matemático que se resuelven en el computador.
Los modelos abstractos o matemáticos de subclasifican en
i. Determinísticos: tienen sus componentes (datos, parámetros) conocidos con certeza.
ii. Aleatorios o Estocásticos: tienen componentes aleatorias.
iii. Horizonte de Planificación: es el tiempo para el cual se realiza el modelo.
– Estratégicos: a largo plazo;
1
2 Modelos de Programación Lineal
– Tácticos: a mediano plazo;
– Operativas: a corto plazo (menor a un mes).
1.2 ESQUEMA DE UN MODELO
b
fenómenoreal
fenómeno
simplificado
Interacciones
Algoritmo
Reformulación(feedback)
ProblemaMatemático
¿Solución
factible?
fin
1.3 MODELOS DE INVESTIGACIÓN OPERATIVA
La Investigación Operativa es una rama de la matemática que usa modelos y algoritmos
para estudiar un fenómeno simplificado. Estos modelos, en general, buscan determinar la mejor
alternativa dentro de un conjunto de alternativas posibles, discretas o infinitas con respecto a un
criterio.
EJEMPLO 1.1. Una empresa, radicada en la ciudad A, debe realizar una consultoría en la ciudad
B con 10 consultorías que irán 5 semanas consecutivas a B; las condiciones son las siguientes:
• Los viajes deben ser en avión iniciando el lunes en la mañana y deben regresar el miércoles
por la tarde;
• Una empresa aeronáutica les propone 3 tarifas para los costos de los tickets de vuelo:
1.3 Modelos de Investigación Operativa 3
T1. El boleto ida y vuelta de A-B-A o B-A-B cuesta $200, 00 si es utilizado íntegramente
en una misma semana;
T2. El boleto ida y vuelta tiene un 25 % de descuento si su utilización completa se la hace
dejando pasar al menos un fin de semana;
T3. Viaje unidireccional A-B o B-A a $120, 00.
¿Cómo debe decidir la empresa la compra de los boletos para minimizar el costo total de tiempo
en las 5 semanas?.
Solución. Por Proporcionalidad, basta hacer el análisis para un solo consultorio; así, las alterna-
tivas que tenemos son las siguientes
A1 Comprar 10 boletos a la tarifa T3, así
costo : 240 × 5 = $1200, 00
costo total : $12000, 00
A2 Comprar 5 boletos a la tarifa T1, así
costo : 200 × 5 = $1000, 00
costo total : $10000, 00
A3 Comprar 2 boletos a la tarifa T3 y 4 boletos a la tarifa T2, así
costo : 240 + 600 = $840, 00
costo total : $8400, 00
A4 Comprar 5 boletos a la tarifa T2, así
costo : 150 × 5 = $750, 00
costo total : $7500, 00
Por tanto, la solución óptima es la de la alternativa 4. Con esto, tenemos que los errores
relativos respecto a las otras alternativas son
ERA1 =12000 − 7500
7500= 0, 6
ERA2 =10000 − 7500
7500= 0, 33
4 Modelos de Programación Lineal
ERA3 =8400 − 7500
7500= 0, 12.
Este ejemplo contiene los elementos de un modelo de Investigación Operativa, es decir,
• Objetivo: Minimizar los costos de transporte.
• Alternativas: Todas las formas factibles de comprar los boletos.
• Restricciones: Se deja pasar fin de semana para la tarifa T2 y viajar en avión.
Regla Empírica: los métodos de Investigación Operativa mejoran entre el 5 % y 12 % en la toma
de decisiones.
Ahora, recordemos las siguientes definiciones
1) Toda función lineal de Rn → R es de la forma
f (x1, x2, ..., xn) = α1x1 + α2x2 + · · · αnxn
con αi ∈ R conocidos para i ∈ {1, 2, ..., n}.
2) Una ecuación lineal de n variables se define como
L = {x ∈ Rn|a1x1 + a2x2 + · · · anxn = b}.
con ai, b ∈ R conocidos.
3) Una desigualdad es el conjunto de los x ∈ Rn que cumplen
a1x1 + a2x2 + · · ·+ anxn ≤ b.
Tipos de soluciones para un sistema de ecuaciones con dos incógnitas
Veamos los tipos de soluciones a través de ejemplos; así,
1.4 Programación Lineal (PL) 5
Sol. única Sol. Incompatible Sol. Infinita
2x1 + x2 = 3
x1 − x2 = 0
2x1 + x2 = 2
2x1 + x2 = 0
2x1 + x2 = 2
4x1 + 2x2 = 4
1 2−1−1
−2
1
2
x1
x2
b
1 2−1−1
−2
1
2
x1
x2
1 2−1−1
−2
1
2
x1
x2
EJEMPLO 1.2. Graficar la solución de los siguientes sistemas de inecuaciones
a)
x1 + x2 ≤ 4
2x1 − x2 = 1
x1 ≥ 0
x2 ∈ R
b)
3x1 − x2 ≥ −1
2x1 + x2 ≤ 0
x2 ≤ 0
x1 ∈ R
1 2−1−1
−2
1
2
3
x1
x2
l1
l2
1 2−1−1
−2
−3
−4
−5
1
x1
x2
l1 l2
1.4 PROGRAMACIÓN LINEAL (PL)
DEFINICIÓN 1.1DEFINICIÓN 1.1La programación lineal, consiste en optimizar (maximizar o minimizar) una función lineal
de n variables, x1, x2, ..., xn (variables de decisión), sometidas o sujetas a un conjunto de res-
tricciones o exigencias expresadas mediante un conjunto de ecuaciones y/o desigualdades
lineales. Se lo denota por
6 Modelos de Programación Lineal
Max z = f (x1, ..., xn) función objetivo
sar sujeto a las restricciones{F conjunto de soluciones factibles
Para construir un modelo de programación lineal se deben usar los siguientes supuestos
1) Proporcionalidad: el aporte de una variable es proporcional a una cantidad unitaria. Se dice
que dos magnitudes m1 y m2 son proporcionales si existe k ∈ R tal que m2 = k m1.
Por ejemplo, supongamos que el costo de transporte de una caja de la ciudad A a la ciudad B
es de p u.m. (unidades monetarias); por tanto, si se tienen x cajas a transportarse entonces
costo total = p · x
2) Aditividad: los efectos de una misma magnitud asociados a dos variables diferentes se su-
man.
3) Continuidad: las variables en un modelo de PL deben ser tomadas comom valores reales, es
decir, xi ∈ R. Usualmente se toman restricciones de positividad, es decir, xi ≥ 0.
4) Determinístico: los datos y desigualdades son conocidos con certeza.
A continuación, presentamos varios ejemplos de programación lineal,
MODELO 1.1: Planificación de la ProducciónMODELO 1.1: Planificación de la ProducciónEl dueño de un restaurante fabrica dos tipos de platos,
• Plato 1. El precio de venta es de 8 u.m. y su contenido es de 5 langostinos, 2 mejillones
y una ostra;
• Plato 2. El precio de venta es de 6 u.m. y su contenido es de 3 langostinos, 3 mejillones
y 3 ostras.
Diariamente un proveedor le entrega 30 langostinos, 24 mejillones y 18 ostras. ¿Cómo ela-
borar un plan de producción diario para maximizar las ventas o los ingresos diarios?
Solución. Horizonte de Planificación: diario (un día).
Decisión: cuántos platos del tipo 1 y del tipo 2 producir al día, sin sobrepasar las disponibilidades
de las materias primas.
1.4 Programación Lineal (PL) 7
Variables de Decisión:
x1 : cantidad de platos del tipo 1 a producirse en el día;
x2 : cantidad de platos del tipo 2 a producirse en el día.
función objetivo:
I(x1, x2) = 8x1 + 6x2
Restricciones:
5x1 + 3x2 ≤ 30 langostinos
2x1 + 3x2 ≤ 24 mejillones
x1 + 3x2 ≤ 18 ostras
x1 ≥ 0, x2 ≥ 0
P: ¿Cuál es el mejor plan de producción?
Usamos las curvas de nivel para la función objetivo, es decir,
Cα = {(x1, x2) | 8x1 + 6x2 = α}
las cuales son rectas de vector normal ∇z = (86) y, el último valor que topa en la región factible
es el mejor, es decir, el que maximizará a la función.
A continuación, procedemos a hallar la solución gráficamente
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19−1−1
−2
1
2
3
4
5
6
7
8
9
10
x1
x2l1
l2
l3∇z
C0 C36 C48 C54
b
b
b
b
8 Modelos de Programación Lineal
Las curvas de nivel se obtuvieron tomando α como el valor que toma z al evaluar en los
vértices de la región, es decir,
x1 x2 z
0 0 0
0 6 36
6 0 48
3 5 54
Por lo tanto, tenemos que x∗1 = 3 y x∗2 = 5 con z∗ = 54 u.m.
EJERCICIO 1.1. Hallar gráficamente el óptimo al siguiente problema
Min z = 2x1 − 3x2
sar
4x1 + 3x2 ≤ 12
x1 + 2x2 ≥ 2
x1 ≥ 0, x2 ≥ 0
Solución. Notemos que al minimizar la función, tenemos que
−∇z =
−2
3
Así, grafiquemos
1 2 3 4 5−1−2−1
−2
1
2
3
4
5l1
l2
−∇z
C−12
C−3
b
b
b b
donde, las curvas de nivel se tienen tomando los valores de α = z, es decir,
1.4 Programación Lineal (PL) 9
x1 x2 z
0 1 -3
0 4 -12
2 0 4
3 0 6
Con esto, vemos que lo óptimo es x∗1 = 0 y x∗2 = 4 con z∗ = −12.
MODELO 1.2MODELO 1.2La compañía ENGINOLA produce dos modelos de TV: Astros y Cosmos. Cada modelo se
fabrica en dos líneas de producción diferente
• La línea de producción de Astro tiene una capacidad diaria de 60 unidades y la del
cosmos de 50 unidades.
• Un aparato Astro requiere de una hora de trabajo y un cosmos de 2 horas de trabajo. Se
dispone diariamente de 120 horas de trabajo para que sean asignadas a la producción
en ambas líneas.
• Un aparato astro deja una utilidad de 20 u.m. y un cosmos una de 30 u.m.
Plantear un modelo de PL que permita elaborar un plan de producción diario de utilidad
máximo.
Solución. Horizonte de Planificación: un día.
Decisión: Determinar un plan de producción factible, es decir, cuántos TV de cada modelo pro-
ducir, con los recursos disponibles tal que maximice la utilidad.
Variables de Decisión:
A : cantidad de TV’s Astro que se producen diariamente
C : cantidad de TV’s Cosmos que se producen diariamente.
Así, el problema queda planteado como
Max z = 20A + 30C
sar
10 Modelos de Programación Lineal
A ≤ 60 unidades de A
C ≤ 50 unidades de C
A + 2C ≤ 120 horas de trabajo
A ≥ 0, C ≥ 0
Donde la solución de este problema es A∗ = 60 y C∗ = 30 con z∗ = 2100 u.m.
MODELO 1.3: Modelo de producciónMODELO 1.3: Modelo de producciónUna fábrica de cerámica produce 5 productos diferentes P1, P2, P3, P4, P5 usando tres pro-
cesos diferentes: molienda, horneados y acabados.
Luego de deducir los costos en la producción de cada unidad de productos se da la utilidad
unitaria y el uso de los procesos en la elaboración de cada unidad de producto, se da en la
siguiente tabla:
• La fábrica tiene 3 molinos y 2 hornos que trabajan semanalmente 6 días en 2 turnos de
8 horas cada uno.
• Tiene 8 trabajadores para los acabados que trabajan un turno de 8 horas, 6 días a la
semana.
Plantear un modelo de PL que permita obtener una utilidad semanal máxima.
Solución. Horizonte de Planificación: una semana.
Decisión: cuántos productos de cada tipo producir
Variables de Decisión:
xi : cantidad de Pi a producirse semanalmente, i ∈ {1, 2, 3, 4, 5}
Max z = 550x1 + 600x2 + 350x3 + 400x4 + 200x5
sar
12x1 + 20x2 + +25x4 + 15x5 ≤ 288 hrs molienda
10x1 + 8x2 + 16x3 ≤ 192 hrs horneado
20x1 + 20x2 + 20x3 + 20x4 + 20x5 ≤ 384 hrs acabado
xi ≥ 0, i ∈ {1, 2, 3, 4, 5}
1.4 Programación Lineal (PL) 11
MODELO 1.4: Modelo de una mezcla (blending)MODELO 1.4: Modelo de una mezcla (blending)Supongamos que se fabrica un aceite mediante dos procesos
i) Refinación conservativa de aceites crudos y
ii) Mezcla conservativa
Los aceites son de dos tipos: aceites vegetales (VEG1, VEG2) y aceites no vegetales (OIL1, OIL2,
OIL3).
• En un mes no se puede refinar más de 200 toneladas de aceites vegetales y no más de
250 toneladas de aceites no vegetales.
• Existe una restricción técnica sobre la densidad del aceite final y es que tenga una
densidad entre 3 y 6 en las unidades de densidad dadas y suponemos que la densidad
de los aceites se mezclan linealmente (o proporcionalmente).
• Una tonelada de aceite final se venderá a 150 u.m.
• Los costos de los aceites y sus densidades se dan en la siguiente tabla
VEG1 VEG2 OIL1 OIL2 OIL3
costo (um/ton) 110 120 130 110 115
densidad 8.8 6.1 2.0 4.2 5.0
Formular un modelo de PL que permita decidir cómo elaborar el producto final y en qué
cantidad, de manera que se maximice la utilidad mensual.
Solución. Horizonte de Planificación: un mes.
Decisión: qué cantidad de cada aceite ponemos para producir el producto final y qué cantidad
total elaborar.
Variables de decisión:
VEGi : cantidad de toneladas del i_ésimo aceite vegetal que va a la mezcla, i ∈ {1, 2}.
OILj : cantidad de toneladas del j_ésimo aceite no vegetal que va a la mezcla,
j ∈ {1, 2, 3}.
12 Modelos de Programación Lineal
Además, definamos la variable de estado
y = VEG1 + VEG2 + OIL1 + OIL2 + OIL3,
con lo cual, tenemos que la restricción de la densidad de la mezcla está dada por
3 ≤ 8,8δ1 + 6,1δ2 + 2,0δ3 + 4,2δ4 + 5,0δ5 ≤ 6
de donde,
3 ≤ 8,8VEG1
y+ 6,1
VEG2
y+ 2,0
OIL1
y+ 4,2
OIL2
y+ 5,0
OIL3
y≤ 6
con lo cual, obtenemos la restricción
3y ≤ 8,8VEG1 + 6,1VEG2 + 2,0OIL1 + 4,2OIL2 + 5,0OIL3 ≤ 6y
Así, tenemos el planteamiento del modelo de la siguiente manera
Max z = 150y − 110 VEG1 − 120 VEG2 − 130 OIL1 − 110 OIL2 − 115 OIL3
sar
VEG1 + VEG2 ≤ 200
OIL1 + OIL2 + OIL3 ≤ 250
y = VEG1 + VEG2 + OIL1 + OIL2 + OIL3
8,8VEG1 + 6,1VEG2 + 2,0OIL1 + 4,2OIL2 + 5,0OIL3 − 6y ≤ 0
8,8VEG1 + 6,1VEG2 + 2,0OIL1 + 4,2OIL2 + 5,0OIL3 − 3y ≥ 0
VEGi ≥ 0, OILj ≥ 0, i ∈ {1, 2}, j ∈ {1, 2, 3}
MODELO 1.5: Un problema no linealMODELO 1.5: Un problema no linealTransformar el siguiente problema no lineal a uno lineal,
Max z = |x1 − 2|+ |x2 + 3|
sar
1.4 Programación Lineal (PL) 13
2x1 − x2 ≥ −3
x1 ≤ 1
x2 ≥ 2
x1 ≥ 0, x2 ≥ 0
Solución. Recordemos que
|a| = max{0, a}+ max{0,−a} = A+ + A−,
de donde se tiene que
a ≤ A+, 0 ≤ A+ y 0 ≤ A−, −a ≤ A−.
Por tanto, llamemos
|x1 − 2| = max{0, x1 − 2}+ max{0, 2 − x1} = X+ + X−
y
|x2 + 3| = max{0, x2 + 3}+ max{0,−x2 − 3} = Y+ + Y−,
a lo cual, el problema lo podemos plantear de la siguiente forma
Max z = X+ + X− + Y+ + Y−
sar
2x1 − x2 ≥ −3
x1 ≤ 1
x2 ≥ 2
x1 − 2 ≤ X+, 0 ≤ X+
2 − x1 ≤ X−, 0 ≤ X−
x2 + 3 ≤ Y+, 0 ≤ Y+
−x2 − 3 ≤ Y−, 0 ≤ Y−
x1, x2 ≥ 0
14 Modelos de Programación Lineal
MODELO 1.6: Modelo de una mezclaMODELO 1.6: Modelo de una mezclaSupongamos que una compañía metalúrgica fabrica dos tipos de acero A1 y A2 usando tres
métodos M1, M2 y M3, la información se presenta en las siguientes tablas
Aceros Especificaciones Técnicas PVP (u.m./ton)
A1 No menos del 60 % de M1 y no más del 30 % de M2 20
A2 Exactamente 10 % de M3 y no más del 40 % de M2 15
Disponibilidad diaria (ton) Costo Unitario
M1 200 8
M2 150 6
M3 60 3
Formular un modelo PL que permita un plan de producción diario de utilidad máxima.
Solución. Horizonte de Planificación: un día.
Decisión: qué cantidad de cada metal Mi debo poner en el acero Aj, i ∈ {1, 2, 3}, j ∈ {1, 2}.
Variables de Decisión: Para definir las variables , podemos verlas a través de una matriz; así,
A1 A2
M1 x11 x12
M2 x21 x22
M3 x31 x32
xij : cantidad en toneladas de metal Mi en el acero Aj, i ∈ {1, 2, 3}, j ∈ {1, 2}.
Por otro lado, definamos las variables de estado
A1 : cantidad total del primer acero producidas en el día.
A2 : cantidad total del segundo acero producidas en el día.
Por tanto, el modelo queda planteado como
Max z = 20A1 + 15A2 − 8(x11 + x12)− 6(x21 + x22)− 3(x31 + x32)
sar
1.4 Programación Lineal (PL) 15
A1 = x11 + x21 + x31
A2 = x12 + x22 + x32
x11 + x12 ≤ 200 toneladas M1
x21 + x22 ≤ 150 toneladas M2
x31 + x32 ≤ 60 toneladas M3
x11 ≥ 0,6A1
x21 ≤ 0,3A1
x32 = 0,1A2
x22 ≤ 0,4A2
xij ≥ 0, i ∈ {1, 2, 3}, j ∈ {1, 2}
MODELO 1.7: Problema de TransporteMODELO 1.7: Problema de TransporteUn carguero eléctrico debe transportar cajas de materias primas (una a cada vez) desde una
zona de entrada a unas bodegas de materias primas S1, S2, ..., Sm. Luego, se desplaza a otras
bodegas diferentes B1, B2, ..., Bn que tiene cajas con productos elaborados, donde toma una
caja y se dirige a la zona de salida donde deja la caja y regresa a la zona de entrada. Se tiene
Hipótesis:
• {Si} ∩ {Bj} = ∅, para i ∈ {1, 2, ..., m}, j ∈ {1, 2, ..., n};
• ai : números de cajas que deben ser almacenadas a Si, i ∈ {1, ..., m};
• bj : números de cajas de productos elaborados que deben salir del almacén y que están
en la bodega Bj, j ∈ {1, ..., n};
•m
∑i=1
ai =n
∑j=1
bj.
Datos:
tei: tiempo en el que el carguero va de la entrada a la bodega
de materia prima Si;
tij : tiempo de desplazamiento del conjunto de Si a Bj;
16 Modelos de Programación Lineal
T =
t11 · · · t1n
t21 · · · t2n
.... . .
...
tm1 · · · tmn
tsj: tiempo de desplazamiento desde Bj a la salida;
tse : tiempo que toma el carguero en ir de la salida a la entrada.
Cómo organizar los movimientos del carguero de manera que en un tiempo mínimo intro-
duzca lasm
∑i=1
ai cajas y retire lasn
∑j=1
bj cajas de productos elaborados.
Solución. El presente problema no tiene horizonte de planificación, pues no tiene tiempo especí-
fico de traslado.
Decisión: Un trayecto va de Entrada − Si − Bj − Salida. Cuántos trayectos de Si a Bj se deben
hacer para cumplir con la tarea, para todo i ∈ {1, ..., m}, j ∈ {1, ..., n}.
Variables de Decisión:
xij : cantidad de veces que el carguero va de Si a Bj,
para todo i ∈ {1, ..., m}, j ∈ {1, ..., n}.
Así, el modelo es
Min t =m
∑i=1
teiai +
m
∑i=1
n
∑j=1
tijxij +n
∑j=1
tsjbj + tse
m
∑i=1
ai
sar
n
∑j=1
xij = ai, i ∈ {1, ..., m} ai veces en Si
m
∑i=1
xij = bj, j ∈ {1, ..., n} bj veces en Bj
xij ≥ 0, i ∈ {1, ..., m}, j ∈ {1, ..., n}
MODELO 1.8: Staffing: gestión de personalMODELO 1.8: Staffing: gestión de personalEl dueño de un almacén tiene el siguiente problema; desea saber cuántos trabajadores con-
tratar y a qué días de la semana asignarles para
1.4 Programación Lineal (PL) 17
• Minimizar los costos de contratación semanales;
• Satisfacer al menos la demanda diaria del personal,
bajo las siguientes condiciones
• Cada trabajador gana 300 u.m. si trabaja en días normales, una bonificación extra de
25 u.m. si trabaja el sábado y de 35 u.m. si trabaja el domingo.
• Su jornada semanal debe tener dos días libres consecutivos.
La demanda se da en la siguiente tabla
Días Lu Ma Mi Ju Vi Sa Do
Trabajadores 20 13 10 12 16 18 20
Plantear un modelo PL para solucionar este problema.
Solución. Horizonte de Planificación: una semana.
Decisión: determinar cuántos trabajadores contratar para cada turno semanal factible.
Pre-procesamiento: planteemos los turnos posibles en la semana
Turnos L Ma Mi J V S D Costo Unitario
1 1 1 1 1 1 0 0 300
2 0 1 1 1 1 1 0 325
3 0 0 1 1 1 1 1 360
4 1 0 0 1 1 1 1 360
5 1 1 0 0 1 1 1 360
6 1 1 1 0 0 1 1 360
7 1 1 1 1 0 0 1 335
Variables de Decisión:
xi : cantidad de trabajadores a contratar para que trabajen en el turno i, i ∈ {1, ..., 7}
El modelo planteado es
Min z = 300x1 + 325x2 + 360(x3 + x4 + x5 + x6) + 335x7
sar
18 Modelos de Programación Lineal
x1 + +x4 + x5 + x6 + x7 ≥ 20 demanda Lunes
x1 + x2 + +x5 + x6 + x7 ≥ 13 demanda Martes
x1 + x2 + x3 + +x6 + x7 ≥ 10 demanda Miércoles
x1 + x2 + x3 + x4 + +x7 ≥ 12 demanda Jueves
x1 + x2 + x3 + x4 + x5+ ≥ 16 demanda Viernes
x2 + x3 + x4 + x5 + x6 ≥ 18 demanda Sábado
x3 + x4 + x5 + x6 + x7 ≥ 20 demanda Domingo
xi ≥ 0, i ∈ {1, ..., 7}
MODELO 1.9: Problema General de TransporteMODELO 1.9: Problema General de TransporteSe consideran m orígenes Oi, i ∈ {1, ..., m} (fábricas, depósitos, reservorios, parada de bu-
ses, etc.) que tiene una oferta Oi de un producto (auto, caja, agua, buses, etc.) y, por otro
lado se consideran n destinos Dj, j ∈ {1, ..., n} (concesenarios, bodegas, ciudades, líneas de
servicios, etc.) cuya demanda es bj. Se conoce el costo unitario de transporte cij u.m.desde
Oi a Dj para todo i, j. Gráficamente se puede ver como
O1
...
Oi
...
Om
a1
ai
am
D1
...
Dj
...
Dn
b1
bj
bn
cij xij
xmn
xmj
x1j
x11
Como hipótesis se tiene quem
∑i=1
ai ≥n
∑j=1
bj y, se quiere determinar un plan de distribución
de costo total mínimo.
Solución. Tomemos las variables de decisión siguientes
xij : cantidad que se envía desde el origen Oi al cliente Dj
para todo i ∈ {1, ..., m}, j ∈ {1, ..., n}
Así, planteemos el modelo
1.4 Programación Lineal (PL) 19
Min z =m
∑i=1
n
∑j=1
cijxij
sar
n
∑j=1
xij ≤ ai, i ∈ {1, ..., m} Oferta
m
∑i=1
xij ≥ bj, j ∈ {1, ..., n} Demanda
xij ≥ 0, i ∈ {1, ..., m}, j ∈ {1, ...n}
MODELO 1.10: Modelo que no representa ninguno de los perceptos de la PLMODELO 1.10: Modelo que no representa ninguno de los perceptos de la PLUna empresa vende automóviles para segmentos de población medianas y altas. Esta em-
presa puede comprar "spots"de 20 segundos en programas de comedias y deportivos. Se
quiere llegar al menos a 28 u.p. (unidad poblacional) de mujeres y a 24 u.p. de hombres.
Comedias Deportivos
Audiencia Femenina (up/spots) 7 2
Audiencia Masculina (up/spots) 2 12
Costo por spots de 20 seg. 5 10
Solución. En principio, tomaríamos las siguientes variables de decisión
C : número de spots de 20 seg. que deben transmitirse en programa de comedia.
D : número de spots de 20 seg. que deben transmitirse en un programa deportivo.
y, plantearíamos el siguiente modelo
Min z = 5C + 10D
sar
7C + 2D ≥ 28 audiencia femenina
2C + 12D ≥ 24 audiencia masculina
C ≥ 0, D ≥ 0
Sin embargo, este problema no cumple con los supuestos para un problema de PL, pues
• No Proporcionalidad: La audiencia no es proporcional al número de spots que transmitan.
20 Modelos de Programación Lineal
Por ejemplo, si se pasa un spot con 200 personas y se manda otro entonces continuarán las
200 personas.
• No Aditividad: Los dos spots puede que se transmitan en el programa de comedias.
• No Continuidad: Necesita valores enteros.
• No Determinístico: La audiencia representa una variable aleatoria, es decir, puede depender
de la hora.
MODELO 1.11: Cutting Stock ProblemMODELO 1.11: Cutting Stock ProblemUn compañía produce electrodomésticos y usa para ello láminas de acero de longitud es-
tándar (stock), que vienen en rollos de 72 pulgs., 48 pulgs. o 36 pulgs. de ancho, aun costo
unitario de 28 u.m., 19 u.m. y 15 u.m., respectivamente. En el proceso de manufactura se
requiere láminas de ocho anchos diferentes y en un número determinado
Ancho 60” 56” 42” 38” 34” 24” 15” 10”
N◦ láminas 500 400 300 450 350 100 800 1000
Se disponen de 1600 rollos de 72”, 1000 rollos de 48” y 10000 rollos de 36” y, el corte es
unidimensional.
Formular un modelo de PL que permita determinar la forma de cortar los rollos para
satisfacer la demanda pero utilizando el menor número de rollos, es decir, minimizando los
cortes de material de stock.
Solución. Como pre-procesamiento generemos todos los patrones posibles de cortes para los
rollos de 72, 48 o 36 pulgadas, expresados en la siguiente matriz P
A1 A2 A3 · · · A27 B1 B2 B3 · · · B9 C1 C2 C3 · · · C9
60” 1 0 0 0 0 0 0 0 0 0 0 0
56” 0 1 1 0 0 0 0 0 0 0 0 0
42” 0 0 0 0 1 0 0 0 0 0 0 0
38” 0 0 0 0 0 1 0 0 0 0 0 0
34” 0 0 0 · · · 0 0 0 1 · · · 0 1 0 0 · · · 0
24” 0 0 0 0 0 0 0 0 0 1 0 0
15” 0 1 0 0 0 0 0 0 0 0 2 0
10” 1 0 1 7 0 1 1 4 0 1 0 3
r 2” 1” 6” · · · 2” 6” 0” 4” · · · 8” 2” 2” 6” · · · 6”
1.4 Programación Lineal (PL) 21
Con esto, se tienen las variables de decisión
Ai : número de veces que se debe cortar al patrón i, i ∈ {1, ..., 27}
Bj : número de veces que se debe cortar al patrón j, j ∈ {1, ..., 9}
Ck : número de veces que se debe cortar al patrón k, k ∈ {1, ..., 9}
Por otro lado, tomemos los siguientes vectores
xT =(
A1 · · · A27 B1 · · · B9 C1 · · · C9
)
bT =(
500 400 300 450 350 100 800 1000)
con lo cual, obtenemos el modelo
Min z = 2827
∑i=1
Ai + 199
∑j=1
Bj + 159
∑k=1
Ck
sar
P · x ≥ b
27
∑i=1
Ai ≤ 1600
9
∑j=1
Bj ≤ 1000
9
∑k=1
Ck ≤ 10000
Ai, Bj, Ck ≥ 0, i ∈ {1, ..., 27}, j, k ∈ {1, ..., 9}
22 Modelos de Programación Lineal
CAPÍTULO 2
GEOMETRÍA DE LA PROGRAMACIÓN LINEAL
2.1 CONJUNTOS CONVEXOS
Estudiaremos conjuntos convexos en Rn y tomaremos la norma euclidiana
‖x‖ =√
x21 + x2
2 + · · ·+ x2n.
DEFINICIÓN 2.1: Segmento CerradoDEFINICIÓN 2.1: Segmento CerradoSean a, b ∈ R
n, se llama segmento cerrado que une a y b al subconjunto de Rn notado por [a, b]
y definido por
[a, b] = {z ∈ Rn|z = a + λ(b − a) con 0 ≤ λ ≤ 1}
equivalentemente,
[a, b] = {(1 − λ)a + bλ ∈ Rn | 0 ≤ λ ≤ 1}
[a, b] = {λ1a + λ2b ∈ Rn | λ1 + λ2 = 1, λ1, λ2 ≥ 0}.
A a y b se los conocen como los extremos del segmento.
Observación: Se nota como (a, b) al segmento de Rn que no incluye a y b, es decir,
(a, b) =]a, b[= {λa + (1 − λ)b | 0 < λ < 1}.
DEFINICIÓN 2.2: Conjunto ConvexoDEFINICIÓN 2.2: Conjunto ConvexoSea C ⊆ R
n, se dice que C es un conjunto convexo si para todo x, y ∈ C y para todo λ ∈ [0, 1],
el vector λx + (1− λ)y ∈ C, es decir, C es convexo si para todo x, y ∈ C, el segmento cerrado
[x, y] está contenido en C.
23
24 Geometría de la Programación Lineal
x
yx y
Convexo No Convexo
b
bb b
Ejemplos:
• ∅ es convexo.
• Rn es convexo.
• Un punto es convexo.
• Un plano es convexo.
DEFINICIÓN 2.3DEFINICIÓN 2.3Sea C un conjunto convexo en R
n, se dice que C tiene una dimensión, notada por dim C, si
es igual a la dimensión de la menor variedad afín (subespacio vectorial + vector) que contiene
a C.
EJERCICIO 2.1. Sea a ∈ Rn, a 6= 0 y α ∈ R. Consideremos el conjunto
H = {x ∈ Rn | aTx = α},
que se lo conoce como el hiperplano del vector normal a. Demostrar que H es un conjunto
convexo.
Demostración. Sean x, y ∈ H, entonces
aTx = α y aTy = α.
Sea 0 ≤ λ < 1, vamos a probar que λx + (1 − λ)y ∈ H; en efecto, vemos que
aT(λx + (1 − λ)y) = λaTx + (1 − λ)aTy
= λα + (1 − λ)α
= λα + α − αλ
= α;
por lo tanto, H es un conjunto convexo.
2.1 Conjuntos Convexos 25
EJERCICIO 2.2. Sea a ∈ Rn, a 6= 0 y α ∈ R. Consideremos el semiespacio S definido por el
vector a
S = {x ∈ Rn | aTx ≤ α}.
Demostrar que S es un conjunto convexo.
Demostración. Sean x, y ∈ S, entonces
aTx ≤ α y aTy ≤ α.
Sea 0 ≤ λ < 1, vamos a probar que λx + (1 − λ)y ∈ S; en efecto, vemos que
aT(λx + (1 − λ)y) = λaTx + (1 − λ)aTy
≤ λα + (1 − λ)α
= α;
de donde, se concluye que S es un conjunto convexo.
TEOREMA 2.1TEOREMA 2.1La intersección arbitraria de conjuntos convexos es convexo.
Demostración. Sea {Ci|i ∈ I} una familia de conjuntos convexos de Rn, donde I es un conjunto
de índices; así,
• Si⋂
i∈I
Ci = ∅, entonces se tiene el resultado;
• Si⋂
i∈I
Ci 6= ∅; sean x, y ∈⋂
i∈I
Ci, entonces para todo i ∈ I se tiene que x, y ∈ Ci y, puesto que
Ci es convexo, colegimos que para todo i ∈ I
[x, y] ∈ Ci,
con lo cual,
[x, y] ∈⋂
i∈I
Ci
y, por tanto⋂
i∈I
Ci es un conjunto convexo.
EJEMPLO 2.1. Sean Hi = {x ∈ Rn|aT
i x = bi}, i ∈ {1, ..., m}, m hiperplanos de vector normal
26 Geometría de la Programación Lineal
ai 6= 0. Entonces por el teorema se tiene que
m⋂
i=1
Hi = {x ∈ Rn|aT
i x = bi, i ∈ {1, ..., m}}
= {x ∈ Rn|Ax = b}
el cual es un conjunto convexo y se lo conoce como el conjunto solución de un sistema lineal de m
ecuaciones en Rn.
EJEMPLO 2.2. Sean Si = {x ∈ Rn|aT
i x ≤ bi}, i ∈ {1, ..., m}, m semiespacios definidos por ai 6= 0.
Entonces por el teorema se tiene que
m⋂
i=1
Si = {x ∈ Rn|aT
i x ≤ bi, i ∈ {1, ..., m}}
= {x ∈ Rn|Ax ≤ b}
el cual es un conjunto convexo y se lo conoce como el conjunto solución de un sistema de m de-
sigualdades en Rn.
Propiedad. El conjunto factible F de un problema de PL siempre es convexo.
DEFINICIÓN 2.4DEFINICIÓN 2.4El conjunto solución de un sistema de m desigualdades lineales se dice un Poliedro.
DEFINICIÓN 2.5DEFINICIÓN 2.5Sean A ⊆ R
n, x1, ..., xp ∈ A y λ1, ..., λp ∈ R tales que λi ≥ 0 para todo i ∈ {1, ..., p} yp
∑i=1
λi = 1. Se dice que un punto de la forma y = λ1x1 + · · · + λpxp es una combinación
convexa (o baricentro) de los x1, ..., xp.
DEFINICIÓN 2.6DEFINICIÓN 2.6Sea A ⊆ R
n, se llama la envolvente convexa de A al conjunto de todas las combinaciones
lineales convexas de un número finito de puntos de A; así,
Env(A) =
{y ∈ R
n∣∣∣y = λ1x1 + · · ·+ λpxp, con xi ∈ A, λi ≥ 0, y
p
∑i=1
λi = 1
}
Resultados: Sean A, B ⊆ Rn
• Env(A) es un conjunto convexo.
• A = Env(A) si y solo si A es un conjunto convexo.
2.2 Repaso de la Topología en Rn 27
• Env(A) =⋂
A⊆Ci
Ci, es decir, la envolvente convexa es el menor conjunto convexo de Rn
que contiene a A.
• A + B = {α + β ∈ Rn|α ∈ A y β ∈ B} es un conjunto convexo.
• A × B = {〈α, β〉 |α ∈ A y β ∈ B} es un conjunto convexo.
• Sea γ ∈ R, γA = {γα ∈ Rn|γα ∈ A} es un conjunto convexo.
2.2 REPASO DE LA TOPOLOGÍA EN Rn
A continuación presentamos una teoría básica de lo que es la topología en Rn; se presentarán
definiciones importantes y ciertos resultados cuyas demostraciones se omitirán, pues toda esta
teoría se la puede abordar y extender de mejor forma en un curso de Análisis Real o Matemático
y utilizar más resultados para las demostraciones.
2.2.1 Bolas Abiertas y Cerradas
Consideremos en Rn con una norma ‖·‖; dados a ∈ R
n y r > 0, definimos
1. Bola abierta de centro a y radio r
B(a, r) = {x ∈ Rn| ‖x − a‖ < r}
2. Bola cerrada de centro a y radio r
B(a, r) = {x ∈ Rn| ‖x − a‖ ≤ r}
2.2.2 Conjuntos Abiertos y Cerrados
DEFINICIÓN 2.7DEFINICIÓN 2.7Sea A ∈ R
n, se dice que a ∈ A es un punto interior de A si para todo ε > 0
B(a, ε) ⊆ A.
Al conjunto de puntos interiores de A se lo denota como◦
A, por lo que
◦A = {a ∈ A|a es un punto interior}.
Se dice que A es un conjunto abierto de Rn si y solo si
◦A = A.
28 Geometría de la Programación Lineal
DEFINICIÓN 2.8DEFINICIÓN 2.8Se dice que a es un punto frontera de A si para todo ε > 0
B(a, ε) ∩ A 6= ∅ y B(a, ε) ∩ Ac 6= ∅.
Se lo denota como
Fr(A) = {x ∈ Rn|x es punto frontera de A}.
EJEMPLO 2.3. Sea A = (−1,5], entonces Fr(A) = {−1, 5}.
Por otro lado, se dice que A es un conjunto cerrado si Fr(A) ⊆ A.
EJEMPLO 2.4. El hiperplano H = {‘x ∈ Rn|aTx ≤ b} y el semiespacio S = {x ∈ R
n|aTx ≤ b}
son conjuntos cerrados.
TEOREMA 2.2TEOREMA 2.2Un conjunto A es abierto si y solo si Ac es cerrado.
TEOREMA 2.3TEOREMA 2.3Se dice que A es acotado si existe R > 0 tal que para todo x ∈ A, ‖x‖ ≤ R.
TEOREMA 2.4: Heine-BorelTEOREMA 2.4: Heine-BorelSe dice que A es compacto si y solo si A es un conjunto cerrado y acotado.
TEOREMA 2.5TEOREMA 2.5Todo poliedro es un conjunto cerrado.
A un poliedro acotado se lo conoce como Polítopo.
2.2.3 Hiperplano de apoyo de un convexo
TEOREMA 2.6: RieszTEOREMA 2.6: RieszSi C es un convexo no vacío; si y /∈ C entonces existe x0 ∈ C tal que
‖x0 − y‖ = mın{‖y − x‖ |x ∈ C}
= d(x0, C).
Demostración. Sea ε > 0 suficientemente grande tal que
B(y, ε) ∩ C = ∅,
2.2 Repaso de la Topología en Rn 29
luego, como B(y, ε) es cerrado y acotado, entonces es compacto, por lo que
B(y, ε) ∩ C es un compacto.
Por otro lado, se conoce que || · || : Rn → R es continua, pues para todo x, y ∈ R
n
| ‖x‖ − ‖y‖ | < ‖x − y‖
y, tomando δ = ε se tiene la continuidad ya que
‖x − y‖ < δ =⇒ | ‖x‖ − ‖y‖ | < ε.
Además, por el teorema de Weiestrass, si se minimiza una función continua sobre un conjunto
compacto de Rn entonces este mínimo existe, es decir, existe x0 ∈ B(y, ε) ∩ C tal que
‖x0 − y‖ = mın{‖x − y‖ |x ∈ B(y, ε) ∩ C};
es claro que si x ∈ B(y, ε), es decir, ‖x − y‖ > ε, se tiene que en cualquier caso
‖x0 − y‖ = mınx∈C
{‖x − y‖}.
TEOREMA 2.7: Separación de un convexo y un puntoTEOREMA 2.7: Separación de un convexo y un puntoSi C es un convexo, cerrado, no vacío y y /∈ C entonces existe a ∈ R
nr {0} tal que
aTy < ınfx∈C
aTx.
Demostración. Por el teorema de Riesz sabemos que existe x0 ∈ C tal que
d(y, C) = ‖x0 − y‖ = mınx∈C
{‖x − y‖}.
Sea x ∈ C, tomemos los puntos del segmento [x, x0], es decir, de la forma x0 + λ(x − x0), para
λ ∈ [0, 1], de donde, al ser C un conjunto convexo se tiene que
x0 + λ(x − x0) ∈ C
luego,
‖x0 + λ(x − x0)− y‖2 ≥ ‖x0 − y‖2
30 Geometría de la Programación Lineal
de donde
〈x0 + λ(x − x0)− y, x0 + λ(x − x0)− y〉 ≥ ‖x0 − y‖2
así
‖x0 − y‖2 + 2λ 〈x0 − y, x − x0〉+ λ2 ‖x − x0‖2 ≥ ‖x0 − y‖2 .
Tomando λ → 0, tenemos que para todo x ∈ C
〈x0 − y, x − x0〉 ≥ 0;
llamemos a = x0 − y, por tanto para todo x ∈ C
〈a, x〉 ≥ 〈a, x0〉
≤ 〈a, x0 − y + y〉
≤ 〈a, x0 − y〉+ 〈a, y〉
≤ ‖x0 − y‖2 + 〈a, y〉
a lo cual
〈a, y〉 = aTy ≤ 〈a, x〉 − ‖x0 − y‖2 ≤ 〈a, x〉
y, en consecuencia
aTy < ınfx∈C
aTx.
COROLARIO 2.8. Si C es un conjunto convexo, cerrado y no vacío, existe
H = {x ∈ Rn|aT(x − y) = 0}
que se separa C con {y}.
DEFINICIÓN 2.9DEFINICIÓN 2.9Sea C un convexo, no vacío y y ∈ C, se dice que H es un hiperplano de apoyo de C en y si C está
completamente contenido en uno de los semiespacios cerrados que define y pasa por y.
DEFINICIÓN 2.10DEFINICIÓN 2.10Sea C un convexo, no vacío y y ∈ C, se dice que H es un hiperplano de apoyo de C en y si C está
completamente contenido en uno de los semiespacios cerrados que define y pasa por y.
Se puede demostrar que y ∈ Fr(C).
2.3 Punto Extremo de un Convexo 31
TEOREMA 2.9TEOREMA 2.9Si C es un conjunto convexo, no vacío y y ∈ Fr(C) entonces existe un hiperplano de apoyo
de C en y.
Demostración. Supongamos que {yk}k∈N es una sucesión de vectores exteriores a C tal que
lımk→∞
= y;
por el teorema de separación de un convexo y un punto, existe ak = y − yk tal que ‖ak‖ = 1 para
todo k ∈ N, tal que para todo x ∈ C
aTy < ınfx∈C
aTx.
Como {ak}k∈N es acotada, por Bolzano-Weiestrass existe una subsucesión M ⊆ N tal que
lımk∈M
ak = a 6= 0
luego, notemos que para todo x ∈ C
lımk∈M
aTyk = aTy ≤ aTx = lımk∈M
aTk x
de donde,
H = {z ∈ Rn|aT(y − z) = 0}.
Adicionalmente, notemos que y ∈ H y, como para todo x ∈ C, aTy ≤ aTx, se tiene que C está
contenido en uno de los semiespacios que define a H.
2.3 PUNTO EXTREMO DE UN CONVEXO
DEFINICIÓN 2.11DEFINICIÓN 2.11Sea C un conjunto convexo no vacío, se dice que un punto x0 ∈ C es punto extremo de C si
no existen x1, x2 ∈ C, (x1 6= x2) tal que x0 ∈]x1, x2[. Equivalentemente, existe λ ∈]0, 1[ tal
que x0 = λx1 + (1 − λ)x2, es decir, x0 no puede ser ’atrapado’ con ningún segmento abierto
]x1, x2[.
– C no tiene puntos extremos; – C tiene como extremo a x0;
32 Geometría de la Programación Lineal
– C tiene infinito número de – El poliedro C tiene un número
puntos extremos; finito de puntos extremos.
TEOREMA 2.10TEOREMA 2.10Si C es un convexo, cerrado, no vacío y H es un hiperplano de apoyo de C, entonces se
cumple que todo punto extremo de T = H ∩ C es un punto extremo de C.
Demostración. Supongamos que x0 es un punto extremo de T = H ∩ C y, por reducción al absur-
do supongamos x0 no es punto extremo de C, entonces existen x1, x2 ∈ C tales que
x0 = λx1 + (1 − λ)x2 con 0 < λ < 1.
Ahora, supongamos que H = {x ∈ Rn|aTx = c} y que C esté completamente contenido en
C+ = {x ∈ R.|aTx ≥ c}.
Como x0 ∈ T, entonces x0 ∈ H y x0 ∈ C+; así,
c = aTx0 = λaTx1 + (1 − λ)aTx2 ≥ c
pero, para que se mantenga la igualdad debe ocurrir que aTx1 = c y aTx2 = c, es decir, no puede
darse que aTx1 > c o aTx2 > c; por lo tanto, x1, x2 ∈ H con lo cual x1, x2 ∈ T y, en consecuencia,
x0 no sería un punto extremo de T, y contradice al primer hecho; así, x0 es un punto extremo de
C.
DEFINICIÓN 2.12DEFINICIÓN 2.12Sea A ⊆ R
n no vacío, se dice que A es acotado inferiormente si existe M ∈ R tal que para todo
x = (x1, ..., xn) ∈ A se tiene que xi ≥ M para todo i ∈ {1, ..., n}.
Nuestro caso de interés es cuando M = 0.
TEOREMA 2.11: ***TEOREMA 2.11: ***Si C es conjunto convexo, cerrado, no vacío y acotado inferiormente entonces
i. C tiene al menos un punto extremo;
ii. Todo hiperplano de apoyo de C contiene al menos un punto extremo de C.
2.4 Optimización de Funciones Convexas 33
Demostración. Probemos por inducción sobre m = dim(C). Si m = 1, entonces se cumple, pues
se puede tomar una semirrecta el cual tendrá un punto extremo.
Ahora, supongamos que es verdadero para m− 1 = dim(Cm−1); sea Cm un convexo, cerrado,
no vacío y acotado inferiormente, entonces al ser cerrado se tiene que existe x0 ∈ Fr(C), de
donde, por teorema se tiene que existe un hiperplano de apoyo de C en x0.
Consideremos T = H ∩ C 6= ∅, el cual es un conjunto convexo, cerrado y acotado inferior-
mente; así, dim(T) ≤ m − 1 y por la hipótesis inductiva, el teorema se cumple para T, es decir,
T tiene un punto extremo x y por el teorema anterior este punto es extremo de C.
Además, como x ∈ H se colige ii.
2.4 OPTIMIZACIÓN DE FUNCIONES CONVEXAS
DEFINICIÓN 2.13DEFINICIÓN 2.13Sea S ⊆ R
n y f : S → R, se dice que
i. x∗ es un mínimo local de f si existe un ε > 0 tal que para todo x ∈ B(x∗, ε), se cumple que
f (x) ≥ f (x∗)
ii. x∗ es un mínimo global de f sobre S si para todo x ∈ S, f (x) ≥ f (x∗).
OBSERVACIÓN. Es indiferente maximizar o minimizar (búsqueda de extremos locales o globa-
les), pues
Max x∈S f (x) = −{Min x∈S − f (x)}
DEFINICIÓN 2.14DEFINICIÓN 2.14Sea C un conjunto convexo no vacío de R
n, se dice que f : C → R es un función convexa si
para todo λ ∈ [0, 1] y para todo x1, x2 ∈ C,
f (λx1 + (1 − λ)x2) ≤ λ f (x1) + (1 − λ) f (x2).
Equivalentemente, para todo x1, x2 ∈ C, f ([x1, x2]) están por debajo del segmento [(x1, f (x1)), (x2, f (x2))].
OBSERVACIÓN. se dice que f es cóncava si − f es convexa.
TEOREMA 2.12TEOREMA 2.12
Sean C ⊆ Rn convexo no vacío, x1, ..., xp ∈ C y λ1, ..., λp ≥ 0 tal que
p
∑i=1
λi = 1. Si f : C → R
34 Geometría de la Programación Lineal
es una función convexa entonces
f
(p
∑i=1
λixi
)≤
p
∑i=1
λi f (xi).
La demostración se sigue por inducción.
OBSERVACIÓN. Las funciones lineales y afines son convexas y cóncavas a la vez.
TEOREMA 2.13TEOREMA 2.13Sean C ⊆ R
n, fi : C → R, i ∈ {1, ..., m}, m funciones convexas, entonces
D = {x ∈ C| fi(x) ≤ 0, i ∈ {1, ..., m}}
es convexo.
Demostración. Probemos que para un i fijo, 1 ≤ i ≤ m
Di = {x ∈ C| fi(x) ≤ 0}
es convexo.
Sean x1, x2 ∈ Di y λ ∈ [0, 1], vemos que
fi(λx1 + (1 − λ)x2) ≤ λ fi(x1)︸ ︷︷ ︸≤0
+(1 − λ) f (x2)︸ ︷︷ ︸≤0
≤ 0,
es decir, λx1 + (1 − λ)x2 ∈ Di. Luego, como D =n⋂
i=1
Di, se tiene que D es convexo, pues es la
intersección finita de convexos.
TEOREMA 2.14: *TEOREMA 2.14: *Sea C ⊆ R
n convexo y f : C → R una función convexa. Entonces
1. El conjunto M de todos los mínimos globales de f es convexo;
2. x∗ es un mínimo local si y solo si x∗ es un mínimo global.
Demostración. Probemos que M es convexo. Si M = ∅, entonces se tiene el resultado. Si M 6= ∅;
sea c0 = mınx∈C f (x) el valor de los mínimos globales, entonces
M = {x ∈ C| f (x)− c0 ≤ 0}
a lo cual, por el teorema precedente se concluye que M es un conjunto convexo.
2.4 Optimización de Funciones Convexas 35
Ahora, probemos el literal (2) del teorema. Supongamos que x∗ es un mínimo global entonces
se tiene que es un mínimo local.
Supongamos que x∗ es un mínimo local y, por reducción al absurdo, supongamos que x∗ no
es mínimo global, es decir, existe y ∈ C tal que f (y) < f (x∗).
Consideremos el segmento de Rn, [y, x∗] = {λy + (1 − λ)x∗|λ ∈ [0, 1]}, entonces para todo
λ ∈ [0, 1]
f (λy + (1 − λ)x∗) ≤ λ f (y) + (1 − λ) f (x∗)
< λ f (x∗) + (1 − λ) f (x∗)
= f (x∗)
a lo cual, contradice el hecho de que x∗ es un mínimo local.
COROLARIO 2.15. Si una función convexa tiene dos mínimos globales diferentes entonces
tiene un infinito número de mínimos globales.
TEOREMA 2.16: ***TEOREMA 2.16: ***Sean C ⊆ R
n cerrado, acotado inferiormente, no vacío y f : C → R una función convexa. Se
considera el problema de optimización convexa
(P) Max x∈C f (x).
Si f tiene un máximo global sobre C entonces este valor siempre se obtendrá en un punto
extremo de C.
Demostración. Supongamos que el máximo global de x0 se obtiene en x0 ∈ Int(C), entonces como
el conjunto de puntos interiores es abierto, se tiene que existe ε > 0 tal que
B(x0, ε) ⊆ C.
Consideremos el punto
x′ = x0 + εx0 − y
‖x0 − y‖
donde y es un punto extremo de C (existe por el primer teorema [***], Teorema 2.11); así,
x′ =ε(x0 − y) + x0 ‖x0 − y‖
‖x0 − y‖=
x0(ε + ‖x − y0‖)− εy
ε + ‖x0 − y‖ − ε=
x0 −εy
ε+‖x0−y‖
1 − εε+‖x0+y‖
36 Geometría de la Programación Lineal
por tanto, despejando x0 tenemos
x0 =ε
ε + ‖x0 − y‖y +
(1 −
ε
ε + ‖x0 − y‖
)x′ = λy + (1 − λ)x′
con λ ∈]0, 1[. Luego, como f es convexa se tiene que
f (x0) ≤ λ f (y) + (1 − λ) f (x′),
entonces, si
λ → 0+ f (x0) ≤ f (x′)
λ → 1− f (x0) ≤ f (y)
⇒ f (x0) = f (x′) = f (y),
pues x0 es un máximo global.
Por lo tanto, el teorema se cumple porque el valor máximo se obtiene en f (y), siendo un
punto extremo de C.
OBSERVACIÓN. Si F = {x ∈ Rn|Ax = b, x ≥ 0} 6= ∅, F es convexo, cerrado, acotado inferior-
mente y tiene al menos un punto extremo. Entonces, por el teorema, si f (x) = cTx, es lineal, el
problema
Max z = cTx
sar
(PL)
{x ∈ F
tiene solución óptima f (x∗), y este valor se alcanzará en un punto extremo de F.
2.5 FORMULACIONES DE LOS PROBLEMAS DE PL
La PL es la optimización de una función lineal o afín de n variables x1, ..., xn sujetos a un
conjunto finito de restricciones expresadas mediante desigualdades y/o ecuaciones lineales.
Dados una matriz A ∈ Mm,n, un vector c ∈ Rn y un vector b ∈ R
m, diremos que un problema
de PL se expresa en la forma
1. General: si se escribe de la forma
Max z = cTx
sar
2.5 Formulaciones de los problemas de PL 37
(PG)
Ax ≤ b
x ∈ Rn
2. Canónica: si se escribe de la forma
Max z = cTx
sar
(PC)
Ax ≤ b
x ≥ 0
3. Estándar: si se escribe de la forma
Max z = cTx
sar
(PS)
Ax = b
x ≥ 0
PROPOSICIÓN 2.17. Se puede pasar de una forma a otra de manera equivalente, es decir, de
la solución óptima de un problema dedujo la solución óptima del otro y visceversa.
Demostración. La demostración de la proposición precedente es directa si consideramos las si-
guientes observaciones:
1. Si queremos minimizar
Min z = cTx −Max z = −cTx
sar ≡ sar{x ∈ F
{x ∈ F
2. Si tenemos una desigualdad lineal αTx ≤ β, entonces tomamos la variable de holgura s1
(slack variable) y obtenemos
αTx + s1 = β
s1 ≥ 0
Si tenemos la desigualdad de la forma αTx ≥ β, entonces tomamos la variable excedente
38 Geometría de la Programación Lineal
s2 (surplus variable) y obtenemos
αTx − s2 = β
s2 ≥ 0
3. Teniendo una ecuación lineal αTx = β, podemos reescribir de la forma
αTx ≤ β
−αTx ≤ −β
4. Si tenemos x ∈ R, variable libre, entonces reescribimos a la variable
x = x′ − x′′
x′ ≥ 0, x′′ ≥ 0
5. Si tenemos x ≥ 0, para obtener la variable en su forma libre, escribimos
x = x′ + x′′
x′ ∈ R, x′′ ∈ R
EJERCICIO 2.3. Escribir el siguiente problema de PL en su forma estándar
Min z = 2x1 + x3
sar
x1 + x2 + 3x3 ≤ 1
x1 − x2 − 4x3 ≥ 3
x1 + x2 = 5
x1 ≥ 0, x2 ∈ R, x3 ≥ 0
Solución. Notemos que el problema PL es de minimizar, entonces debemos transformar uno de
maximización; por otro lado, debemos tomar una slack variable s1 y una surplus variable s2 para
tranforma las desigualdades a igualdades y, reescribir a la variable x2. Por tanto, el problema en
su forma estándar es
2.6 Posibles resultados de un problema de PL 39
− Max z = −2x1 − x3
sar
x1 + x′2 − x′′2 + 3x3 + s1 = 1
x1 − x′2 + x′′2 − 4x3 − s2 = 3
x1 + x′2 − x′′2 = 5
x1, x′2, x′′2 , x3 ≥ 0
2.6 POSIBLES RESULTADOS DE UN PROBLEMA DE PL
Sea F = {x ∈ Rn|Ax ≤ b, x ≥ 0} el conjunto factible de un problema de PL en la forma
canónica. La PL busca un x∗ ∈ F tal que para todo x ∈ F
z∗ = cTx∗ ≥ cTx.
Al resolver un problema de PL, tres respuestas son posibles
i) Problema con solución finita: el problema tiene una única solución o un infinito número de
soluciones óptimas.
ii) Problema no factible: el conjunto F = ∅, se nota por
Max z = cTx = −∞
sar{
x ∈ F = ∅
iii) Problema no acotado: cuando F 6= ∅ pero z → ∞, se nota por
Max z = cTx = +∞
sar{
x ∈ F
EJEMPLO 2.5. El Modelo 1.1, Planificación de Producción, se encuentra en el caso i), es decir,
40 Geometría de la Programación Lineal
tiene solución única.
Ahora, veamos un problema donde se encuentre en el caso i) pero que tenga infinitas solu-
ciones óptimas.
EJERCICIO 2.4. Una compañía fabrica camiones y automóviles usando dos procesos, ensam-
blaje y pintura
Camión Automóviles
Ensamblaje 50 50
Pintura 40 60
Utilidad (um) 300 200
Plantear un modelo de PL para determinar un plan de producción óptima, de la utilidad
diaria máxima.
Solución. Tomemos las variables de decisión
x1 : cantidad de camiones a producirse al día.
x2 : cantidad de automóviles a producirse al día.
El modelo es
Max z = 300x1 + 200x2
sar
x150 + x2
50 ≤ 1
x140 + x2
60 ≤ 1
x1 ≥ 0, x2 ≥ 0
o visto de otro modo
Max z = 300x1 + 200x2
sar
x1 + x2 ≤ 50
3x1 + 2x2 ≤ 120
x1 ≥ 0, x2 ≥ 0
2.6 Posibles resultados de un problema de PL 41
Entonces, grafiquemos las restricciones y las curvas de nivel de la función a maximizar, es decir,
Cα = {(x1, x2)|300x1 + 200x2 = α},
los cuales tomaremos α =0,10000,12000, que vienen a representar los valores de z al tomar los
puntos extremos del poliedro obtenido, es decir,
x1 x2 z
40 0 12000
0 50 10000
20 30 12000
Así, el gráfico resultante es
0 10 20 30 40 50 60
10
20
30
40
50
60
x1
x2
l1
l2
C0
C10000
C12000
b
b
b
A
B
F
Con esto, podemos ver que el segmento [A, B] con
[A, B] =
{(x
y
)∈ R
2∣∣∣(
x
y
)= λ
(2030
)+ (1 − λ)
(400
)}
es solución del problema y, por ejemplo, para λ = 12 se tiene que x = (30
15), es una solución no
extrema del problema.
EJEMPLO 2.6. Si en el problema anterior tenemos la restricción de que x1 ≥ 30 y x2 ≥ 25, enton-
ces no habrá solución al problema, pues
F = ∅;
42 Geometría de la Programación Lineal
por tanto, es un problema infactible.
Finalmente, veamos otro problema que pertenezca al caso iii), es decir, que sea no acotado.
EJERCICIO 2.5. Considere el problema
Max z = 2x1 − x2
sar
x1 − x2 ≤ 1
2x1 + x2 ≥ 6
x1 ≥ 0, x2 ≥ 0
Grafique la solución de este problema.
Solución. Graficando las restricciones, obtenemos
1 2 3 4 5 6 7 8 9−1−2−1
−2
1
2
3
4
5
6
x1
x2
l1
l2
C0
b
Por tanto, se puede ver que este problema es no acotado y z → ∞.
OBSERVACIÓN. Una condición necesaria para que un problema de PL sea no acotado es que F
no sea acotado, aun así no es suficiente asegurarlo debido a que depende de la dirección de ∇z.
2.7 Desigualdades y Lema de Farkas 43
2.7 DESIGUALDADES Y LEMA DE FARKAS
LEMA 2.18 (Farkas (1902)). Sea A ∈ Rm×n, (Mm×n) y b ∈ R
m. Entonces el sistema Ax = b,
x ≥ 0 es compatible si y solo si para todo y ∈ Rm tal que ATy ≥ 0 se cumple que bTy ≥ 0,
es decir, un problema de PL en la forma estándar tiene un conjunto factible no nulo.
Demostración. Supongamos que el sistema restringido Ax = b, x ≥ 0 es compatible, es decir,
existe x0 ≥ 0 tal que
Ax0 = b.
Sea y ∈ Rm tal que ATy ≥ 0, vamos a demostrar que bTy ≥ 0; en efecto, se tiene que
bTy = (xT0 AT)y = xT
0︸︷︷︸≥0
ATy︸︷︷︸≥0
≥ 0.
Ahora, supongamos que para todo y ∈ Rm tal que ATy ≥ 0 se tiene que bTy ≥ 0 y, por
reducción al absurdo, supongamos que el sistema Ax = b, x ≥ 0 es incompatible. Sea
K = {y ∈ Rm|∃x ∈ R
n, x ≥ 0 tal que Ax = y}
Así, notemos que
• K es no vacío, pues y = 0 ∈ K;
• K es convexo. Sean y1, y2 ∈ K y λ ∈ [0, 1], entonces existen x1, x2 ∈ Rn con x1, x2 ≥ 0 tales
que
Ax1 = y1 y Ax2 = y2;
luego, como λx1 + (1 − λ)x2 ≥ 0 se tiene que
A(λx1 + (1 − λ)x2) = λy1 + (1 − λ)y2
y, en efecto, λy1 + (1 − λ)y2 ∈ K;
• K es cerrado. Sea (yn)n∈Nuna sucesión de K tal que
lımn→∞
yn = y,
entonces para todo n ∈ N, existe xn ∈ Rn con xn ≥ 0 tal que
Axn = yn
44 Geometría de la Programación Lineal
de donde,
lımn→∞
Axn = Ax = y = lımn→∞
yn
y, en consecuencia, y ∈ K, por lo que K es cerrado.
Así, por hipótesis se tiene que b /∈ K y, en conjunto con lo anterior, por el Teorema 2.7, se
tiene que existe a ∈ Rm tal que aTb < α y aTy ≥ α, para todo y ∈ K , pues α = ınf
y∈KaTy. En
particular, para y = 0 se tiene que
aTb < aTy = 0.
Ahora, tomando y = aj la j_ésima columna de A, j ∈ {1, ..., n} y λ > 0, tenemos que λaj ∈ K,
pues basta tomar x = λei, con ei =
1 i_ésima componente
0 otra componente; así,
A(λei) = λai
y, además aTb < λaTai. Ahora, dividimos ambos lados de la última desigualdad por λ y to-
mamos límite λ → ∞, para concluir que aTaj ≥ 0 y, como es verdad para cada j ∈ {1, ..., n},
obtenemos que
aT A = ATa ≥ 0,
lo cual genera una contradicción a la hipótesis, pues hemos encontrado a ∈ Rm tal que ATa ≥ 0
pero aTb = bTa < 0; por lo tanto, se concluye que el sistema Ax = b, x ≥ 0 es compatible
COROLARIO 2.19. El sistema de desigualdades Ax ≤ b, x ∈ Rn es compatible si y solo si
para todo y ∈ Rm tal que ATy = 0 con y ≥ 0 se tiene que yTb ≥ 0, es decir, el problema de
PL en la forma general tiene un conjunto factible no nulo.
Demostración. Supongamos que el sistema de desigualdades Ax ≤ b, x ∈ Rn es compatible,
transformemos a su forma estándar. Sean A∗ = (Im, A,−A)m×(m+2n) y xT = (z, x′, x′′) con
z ∈ Rm (vector de variables de holguras), x′, x′′ ∈ R
n y x′, x′′ ≥ 0; así,
A∗x =(
Im A −A)
z
x′
x′′
= z + A(x′ − x′′)
2.7 Desigualdades y Lema de Farkas 45
Por tanto, reescribimos el problema como
A∗x = b
x ≥ 0
el cual es compatibles si y solo si
A∗x ≤ b
x ∈ Rn
es compatible, por la Proposición 2.17. Entonces aplicando el Lema de Farkas decimos que es
compatible si, para todo y ∈ Rm tal que A∗Ty ≥ 0 se tiene que yTb ≥ 0; luego, notemos que
A∗Ty =
Im
AT
−AT
y =
y
ATy
−ATy
≥ 0
es decir,
y ≥ 0
ATy = 0
y, en consecuencia ,
Ax ≤ b
x ∈ Rn
es compatible si y solo si para todo y ∈ Rn tal que y ≥ 0 y
ATy = 0 se cumple que yTb ≥ 0.
2.7.1 Interpretación geométrica del Lema de Farkas
DEFINICIÓN 2.15DEFINICIÓN 2.15Sea C ⊆ R
n no vacío; se dice que C es un cono (con la punta en el origen) si para todo a, b ∈ C,
λ ≥ 0 y µ ≥ 0, se cumple que la combinación cónica está en C, es decir,
λa + µb ∈ C.
Gráficamente se ve
46 Geometría de la Programación Lineal
1 2 3 4 5 6 7−1−1
1
2
3
4
5
6
7
x1
x2
a
b
a+bλa
µb
λa + µb
C
DEFINICIÓN 2.16DEFINICIÓN 2.16
Sean a1, ..., ap ∈ Rn y λi ≥ 0, i ∈ {1, ..., p}; todo vector de la forma
p
∑i=1
λiai se dice una
combinación lineal cónica de los vectores a1, ..., ap.
DEFINICIÓN 2.17DEFINICIÓN 2.17Sea A ⊆ R
n, no vacío. Se llama Envolvente Cónica de A y se nota por EnvC(A) al conjunto
de todas las combinaciones cónicas se un subconjunto finito de vector de A.
OBSERVACIÓN. Si A ⊆ Rn no vacío , se cumple que
i) EnvC(A) es un cono.
ii) EnvC(A) = A si y solo si A es un cono con la punta en el origen.
iii) EnvC(A) =⋂
A⊆D
D.
iv) La intersección de conos es un cono.
DEFINICIÓN 2.18DEFINICIÓN 2.18Dado w ∈ R
m, w 6= 0. Diremos que
L = {x ∈ Rm|αTx ≥ 0}
es un semiespacio lineal de Rm.
OBSERVACIÓN. Se tiene que x ∈ L si wTx ≥ 0 y ‖w‖ ‖x‖ cos θ ≥ 0, con θ el ángulo que forma x
y w y 0 ≤ θ ≤ π2 .
2.7 Desigualdades y Lema de Farkas 47
Siguiendo el lema de Farkas podemos notar que
i) Si A = {a1, ..., an} ⊆ Rm el conjunto de las columnas de la matriz (A ∈ Mm×n), se tiene que
Ax = b
x ≥ 0es compatible si y si solo si b ∈ EnvC(A).
ii) Sea y ∈ Rm, y 6= 0 se define el semiespacio lineal
Dy = {x ∈ Rm|yTx ≥ 0}
48 Geometría de la Programación Lineal
CAPÍTULO 3
DUALIDAD DE LA PROGRAMACIÓN LINEAL
La dualidad es útil para
• Encontrar cotas superiores de un problema de maximización;
• Generar otros algoritmos para resolver un problema de PL (Método Dual);
• Hacer post-optimización (What if);
• Análisis de Sensibilidad, intervalos en los que la interpretación de las variables duales son
válidas.
Consideremos el siguiente ejercicio:
EJERCICIO 3.1. ECUACAFÉ produce cuatro mezclas de cafés B1, B2, B3 y B4 usando cafés
brasileño, colombiano y ecuatoriano. Los productos se elaboran en paquetes de 10 libras
Mezclas Brasileño Colombiano Ecuatoriano Utilidad
(lbr/paquete) (lbr/paquete) (lbr/paquete) (um/paquete)
B1 2 4 4 8
B2 4 5 1 6
B3 3 3 4 4
B4 7 2 1 5
Disp. (lbr) 8000 6400 6000
Plantear un modelo de PL para obtener un plan de producción diario de utilidad máxima
Solución. Tomemos las variables de decisión
xi : cantidad de paquetes de la mezcla Bi que deben elaborarse al día, i ∈ {1, 2, 3, 4}.
Entonces, el modelo (Problema PRIMAL) es
Max z = 8x1 + 6x2 + 4x3 + 5x4
49
50 Dualidad de la Programación Lineal
sar
(P)
2x1 + 4x2 + 3x3 + 7x4 ≤ 8000 lbrs. café brasileño
4x1 + 5x2 + 3x3 + 2x4 ≤ 6400 lbrs. café colombiano
4x1 + x2 + 4x3 + x4 ≤ 6000 lbrs. café ecuatoriano
xi ≥ 0, i ∈ {1, 2, 3, 4}
Resolviendo el problema en un paquete se tiene que la solución óptima es
x∗1 = 1200, x∗2 = x∗3 = 0, x∗4 = 800 =⇒ z∗ = 13600 um.
Transformando el problema a su forma estándar, debemos tomar las variables de holgura
s1, s2 y s3, de donde se tiene que
s∗1 = s∗2 = 0, s∗3 = 400
lo que significa que no hay sobrante de libras de café brasileño y colombiano, pero si hay una
sobra de 400 lbrs. de café ecuatoriano.
Problema Dual: Sin conocer la solución de (P) un empresario le propone a ECUACAFÉ
comprarle todas sus existencias de materias primas, de tal forma que
• Minimice el monto total de compra; y
• ECUACAFÉ haga el trato lo más justo posible, define un precio de equilibrio.
Solución. Bajo el razonamiento previo, para plantear este problema como uno de PL, debemos
fijar un sistema de precios unitarios; por ende, definamos las variables de decisión
λ1 : precio de venta del café brasileño (um/lbrs.)
λ2 : precio de venta del café colombiano (um/lbrs.)
λ3 : precio de venta del café ecuatoriano (um/lbrs.)
Por tanto, planteamos el modelo
Min ω = 8000λ1 + 6400λ2 + 6000λ3
sar
51
(D)
2λ1 + 4λ2 + 4λ3 ≥ 8
4λ1 + 5λ2 + λ3 ≥ 6
3λ1 + 3λ2 + 4λ3 ≥ 4
7λ1 + 2λ2 + λ3 ≥ 5
λ1, λ2, λ3 ≥ 0
Las restricciones planteadas en el problema son precios que ayudan a recuperar al menos la
utilidad unitaria de Bi, i ∈ {1, 2, 3, 4}; la solución de este problema es
λ∗1 =
16
, λ∗2 =
2312
, λ∗3 = 0 =⇒ ω∗ = 13600 um.
Estos valores se los conoce como los precios ocultos (shadow prices).
DEFINICIÓN 3.1DEFINICIÓN 3.1Dado un problema de PL en la forma canónica
Max z = cTx
sar
(P)
Ax ≤ b
x ∈ Rn, x ≥ 0
con A ∈ Rm×n y x un vector n variables. Se le asevera otro problema de PL
Min ω = bTλ
sar
(D)
ATλ ≥ c
λ ∈ Rm, λ ≥ 0
donde consta de m restricciones del problema (P), que es llamado el Problema Dual.
Terminología:
• (P) : se dice el problema Primal (primígeno), con xi, i ∈ {1, ..., n} variables primales.
• (D) : se dice el problema Dual de (P) con λj, j ∈ {1, ..., m} variables duales.
OBSERVACIÓN (Propiedad Involutiva.). El problema dual de (D) es (P).
52 Dualidad de la Programación Lineal
Demostración. Expresemos al problema dual (D) en su forma canónica; así,
− Max ω = −bTλ
sar
(DC)
(−AT)λ ≤ −c
λ ≥ 0
Entonces, el problema dual de (DC), tomando x′ como el vector de las variables duales, es
− Min z = −cTx′
sar
(DDC)
(−AT)Tx′ ≥ −b
x′ ≥ 0
por lo que se tiene el problema primal
Max z = cTx′
sar
(P)
Ax′ ≤ b
x′ ≥ 0
EJERCICIO 3.2. Sea (P) un problema PL en la forma estándar, hallar el dual de (P)
Solución. Recordemos que un problema de PL en su forma estándar se expresa de la forma
Max z = cTx
sar
(PE)
Ax = b
x ≥ 0
Expresándolo en su forma canónica, se tiene que
Max z = cTx
sar
53
(PC)
Ax ≤ b
−Ax ≤ −b
x ≥ 0
por tanto, tomando µ ∈ Rm y η ∈ R
m como las variables duales, tenemos que el dual de P es
Min ω = bTµ − bTη
sar
(PD)
ATµ − ATη ≥ c
µ, η ≥ 0
y, tomando λ = µ − η, obtenemos que
Min ω = bTλ
sar
(D)
ATλ ≥ c
λ ∈ Rm
EJERCICIO 3.3. Calcular el programa dual de un problema de PL en la forma general
Max z = cTx
sar
(P)
Ax ≤ b
x ∈ Rm
Solución. Expresemos el problema (P) en su forma canónica; así, tomemos x′, x′′ ∈ Rm con
x′, x′′ ≥ 0 tal que x = x′ − x′′, por ende el problema es
54 Dualidad de la Programación Lineal
Max z = cT(x′ − x′′) Max z =(
cT −cT) x′
x′′
sar ≡ sar
A(x′ − x′′) ≤ b
x′
x′′
≥ 0
(A −A
)
x′
x′′
≤ b
x′
x′′
≥ 0
Tomando λ ∈ Rm como las variables duales del problema, tenemos que
Min ω = bTλ Min ω = bTλ
sar ≡ sar
AT
−AT
λ ≥
c
−c
λ ≥ 0
ATλ = c
λ ≥ 0
Cálculo del dual de un problema general con restricciones de positividad
Consideremos el problema primal (P) y m1, m2, m3 ∈ N tales que m = m1 + m2 + m3
Max z = cTx
sar
(P)
A1x ≤ b1 b1 ∈ Rm1
A2x = b2 b2 ∈ Rm2
A3x ≥ b3 b3 ∈ Rm3
x ≥ 0
Ahora, por el tipo de restricciones del problema, tenemos los siguientes criteriores:
• Si la restricción es del tipo ≤, se toman variables de holgura tales que estas sean positivas.
• Si la restricción es del tipo =, se toman variables libres.
• Si la restricción es del tipo ≥, se toman las variables excedentes tales que estas sean nega-
tivas o, equivalentemente, se restan en la restricción del dual siendo estas positivas.
55
Bajo lo anterior, tomando las variables λ ∈ Rm1 , µ ∈ R
m2 y η ∈ Rm3 se tiene que el problema
dual de (P) es
Min ω = bT1 λ + bT
2 µ + bT3 η
sar
(D)
AT1 λ + AT
2 µ + AT3 η ≥ c
λ ≥ 0, µ ∈ Rm2 , η ≤ 0
EJERCICIO 3.4. Calcule y resuelva el problema dual del problema primal
Max z = 2x1 − x3 + x5
sar
(P)
2x1 + x2 − x3 + 4x4 + 2x5 ≤ 8
xi ≥ 0, i ∈ {1, ..., 5}
Solución. Puesto que el problema (P) tiene una restricción, tomamos la variable dual λ ∈ R, por
lo que el problema dual es
Min ω = 8λ Min ω = 8λ
sar ≡ sar
2
1
−1
4
2
λ ≥
2
0
−1
0
1
λ ≥ 0
2λ ≥ 2
λ ≥ 0
λ ≤ 1
2λ ≥ 1
λ ≥ 0
Entonces, es fácil ver que solo hay un punto en común entre todas las restricciones,
0 1 2 3 4 5 6−1−2−3−4λ
l2l1
l3l4
por tanto, se tiene que λ∗ = 1, de donde, w∗ = 8
56 Dualidad de la Programación Lineal
EJERCICIO 3.5. Calcule el dual de
Max z = 2x1 − 2x2 + x4 − x6
sar
(P)
2x1 − x2 ≤ −1
x1 + x3 + x4 + x5 ≤ 2
2x1 − x2 = 0
x1 − x2 + x3 − 6x4 − x6 ≥ 1
2x1 + x6 ≥ −4
xi ≥ 0, i ∈ {1, ..., 6}
Solución. Tomamos 5 variables duales, λi, i ∈ {1, ..., 5}, de donde se tiene que el dual de (P) es
Min ω = −λ1 + 2λ2 + λ4 − 4λ5
sar
(D)
2λ1 + λ2 + 2λ3 + λ4 + 2λ5 ≥ 2
−λ1 + −λ3 − λ4 ≥ −2
λ2 − λ4 ≥ 0
λ2 + −6λ4 ≥ 1
λ2 ≥ 0
−λ4 + λ5 ≥ −1
λ1, λ2 ≥ 0, λ3 ∈ R, λ4, λ5 ≤ 0
3.1 TEOREMAS DE LA DUALIDAD DÉBIL Y FUERTE
TEOREMA 3.1: Dualidad DébilTEOREMA 3.1: Dualidad DébilDado el problema primal (P) en la forma canónica y su dual (D)
3.1 Teoremas de la dualidad débil y fuerte 57
Max z = cTx Min ω = bTλ
sar y sar
(P)
Ax ≤ b
x ≥ 0(D)
ATλ ≥ c
λ ≥ 0
Para toda solución factible x de (P) y para toda solución factible λ de (D) se tiene que
z(x) = cTx ≤ bTλ = ω(λ)
Demostración. Supongamos que x y λ son soluciones factibles para los problemas (P) y (D),
respectivamente; así, puesto que x ≥ 0 y c ≤ ATλ tenemos que
cTx ≤ λT Ax
y, como Ax ≤ b obtenemos que
cTx ≤ λTb,
como se quería.
TEOREMA 3.2: Certificado de OptimalidadTEOREMA 3.2: Certificado de OptimalidadSi existen un x∗ ∈ F(P) y λ∗ ∈ F(D) tales que
cTx∗ = bTλ∗
entonces x∗ y λ∗ son óptimos para (P) y (D), respectivamente.
Demostración. Supongamos, por reducción al absurdo, que x∗ no es óptimo para (P), entonces
existe un valor que maximice mejor a la función, es decir, existe x ∈ F(P) tal que
cT x > cTx∗,
de donde, por la hipótesis se tiene que
cT x > bTλ∗,
el cual es una contradicción al Teorema 3.1; por tanto, x∗ es óptimo para (P). Análogamente, se
prueba que λ∗ es el óptimo de (D).
Al siguiente teorema, por su importancia, se lo conoce como Teorema Fundamental de la PL. En
58 Dualidad de la Programación Lineal
esta parte tomaremos los siguientes problemas en dualidad
Max z = cTx Min ω = bTλ
sar y sar
(P)
Ax ≤ b
x ∈ Rn
(D)
ATλ = c
λ ≥ 0
TEOREMA 3.3TEOREMA 3.3
Sean A ∈ Rm×n, b ∈ R
m y F(P) el poliedro de (P), es decir,
F(P) = {x ∈ Rn|Ax ≤ b} 6= ∅.
Supongamos que z está acotada superiormente en F(P) por d ∈ R, es decir, para todo x ∈
F(P), cTx ≤ d, entonces existe λ ∈ Rm, λ ≥ 0 tal que ATλ = c, es decir, existe un punto
factible del dual (D) tal que bTλ ≤ d.
Demostración. Para la demostración de este teorema, haremos uso del corolario del Lema de
Farkas (Corolario 2.19). Para esto es suficiente mostrar que el sistema
A′λ =
−Im
AT
−AT
bT
λ ≤
0m
c
−c
d
= b′
admite una solución λ ∈ Rm; pues así, el sistema de desigualdades precedente es factible si
existe y ∈ Rm+2n+1 con y ≥ 0,
yT =(
µ x′ x′′ z)
tal que
(−Im A −A b
)
µ
x′
x′′
z
= 0
entonces
(0 cT −cT d
)
µ
x′
x′′
z
≥ 0,
3.1 Teoremas de la dualidad débil y fuerte 59
es decir, el sistema de desigualdades es consistente si para todo µ ≥ 0, (µ ∈ Rm), para todo
x′, x′′ ≥ 0, (x′, x′′ ∈ Rn) y para todo z ≥ 0, z ∈ R tal que
−µ + A(x′ − x′′) + zb = 0
se tiene que
cT(x′ − x′′) + dz ≥ 0,
con lo cual, poniendo x = x′′ − x′ tenemos que
−µ − Ax + zb = 0 =⇒ −cTx + dz ≥ 0
Ax + µ = zb =⇒ cTx ≤ dz
Por tanto, considerando que µ es un vector de variables de holgura, vamos a demostrar que si
Ax ≤ zb entonces cTx ≤ dz, de donde, por el coroloario se tendría que el sistema es compatible.
Así,
a) Si z > 0, (z ∈ R); supongamos que
Ax ≤ zb,
es decir,
A
(1z
x
)≤ b
por lo tanto, 1z ∈ F(P), de donde, por la hipótesis del teorema se tiene que
cT
(1z
x
)≤ d
y, en consecuencia, cTx ≤ zd.
b) Si z = 0; supongamos que Ax ≤ 0 y probemos que cTx ≤ 0; para esto, supongamos que
existe x0 ∈ Rn tal que Ax0 ≤ 0 y, por el absurdo supongamos que cTx0 > 0. Luego como
F(P) 6= ∅, existe x1 ∈ F(P) tal que para todo α ≥ 0, x1 + αx0 ∈ F(P), pues
A(x1 + αx0) = Ax1 + αAx0 ≤ b,
y, por hipótesis del teorema se tiene que, para todo α ≥ 0
cT(x1 + αx0) ≤ d
60 Dualidad de la Programación Lineal
es decir,
cTx1 + αcTx0 ≤ d,
al tomar α → ∞ a1α
cTx1 + cTx0 ≤1α
d
se llega a una notoria contradicción, por tanto cTx ≤ 0.
OBSERVACIÓN. Se puede demostrar también que si
F(D) ={
λ ∈ Rm|ATλ = c, λ ≥ 0
}6= ∅
y ω está acotada inferiormente por un d ∈ R, es decir, para todo ω ∈ F(D) se cumple que
bTλ ≥ d, entonces existe x ∈ F(P), (x ∈ Rn) tal que cTx ≥ d.
TEOREMA 3.4: Dualidad FuerteTEOREMA 3.4: Dualidad Fuerte
Si A ∈ Rm×n, b ∈ R
m, c ∈ Rn se cumple que
max{
cTx|Ax ≤ b, x ∈ Rn}= mın
{bTλ|ATλ = c, λ ≥ 0
}
si y solo si F(P) y F(D) son conjuntos no vacíos.
Demostración. La primera implicación es evidente por la definición del máximo y mínimo, por
lo que los conjuntos
{cTx|Ax ≤ b, x ∈ R
n}
y{
bTλ|ATλ = c, λ ≥ 0}
son no vacíos.
Ahora, bajo el suspuesto de que F(P) y F(D) son no vacíos, vamos a probar la igualdad. Por
el teorema de la dualidad débil sabemos que para todo x ∈ F(P) y para todo λ ∈ F(D) se tiene
que cTx ≤ bTλ, de donde, podemos deducir que
cTx ≤ sup{
cTx|Ax ≤ b, x ∈ Rn}≤ ınf
{bTλ|ATλ = c, λ ≥ 0
}≤ bTλ (3.1)
Luego, como tenemos que para todo x ∈ F(P), cTx ≤ d con d = sup{
cTx|Ax ≤ b, x ∈ Rn}
, por
el Teorema 3.3, existe λ ∈ F(D) tal que bTλ ≤ d, por lo que ınf es un mın y, además
sup{
cTx|Ax ≤ b, x ∈ Rn}= mın
{bTλ|ATλ = c, λ ≥ 0
}
3.1 Teoremas de la dualidad débil y fuerte 61
Por otro lado, supongamos que el sup{cTx|x ∈ F(P)} no es un max , es decir, el sistema
Ax ≤ b l m
−cTx ≤ −d l 1
es incompatible, de donde, por el corolario del Lema de Farkas, existe y =
y
µ
∈ R
m+1 tal
que(
AT c) y
µ
= 0
pero(
bT −d) y
µ
< 0,
es decir, existe
y
µ
, con y ∈ R
m, y ≥ 0 y µ ≥ 0 tal que
ATy + cµ = 0 pero bTy < du;
así, vemos que
• Si µ = 0 , existe y ∈ Rm tal que ATy = 0 y bTy < 0, por lo que se tendría que F(P) = ∅. Con
esto, necesariamente se tiene que µ > 0.
• Tomando µ = 1 y y = 1µ y (y ∈ R
m), se tiene que AT y = c y, entonces bT y < d, es decir,
bT y < mın{
bTy | y ∈ F(D)}
,
el cual genera una contradicción a (3.1) y, en consecuencia, se concluye que el sup es un max,
por lo que
d = max{
cTx | Ax ≤ b, x ∈ Rn}= mın
{bTλ | ATλ = c, λ ≥ 0
}
OBSERVACIÓN. Si solamente uno de los conjuntos F(P) o F(D) es no vacío, entonces
sup{
cTx | Ax ≤ b, x ∈ Rn}= ınf
{bTλ | ATλ = c, λ ≥ 0
}
.
62 Dualidad de la Programación Lineal
3.2 ESQUEMA DE LA DUALIDAD
Para recordar en qué estados están simultáneamente (P) y (D) se constituye lo que se llama
Esquema de Dualidad.
(D) \ (P)Solución
Finita
No
Acotada
No
Factible
Solución
Finita
Caso I: Th.
dualidad fuerte
No es
posible
No es
posible
No
Acotada
No es
posible
No es
posible
Caso II:
Obs. 6
No
Factible
No es
posible
Caso II:
Obs. 6
Caso III:
posible
Los casos en los que no es posible, se debe al teorema de la dualidad débil. A continuación
presentamos un ejemplo
EJERCICIO 3.6 (Caso II:). Obtener las soluciones de (P) y (D) si
Max z = x1 + x2
sar
(P)
−x1 + x2 = 1
x1 + x2 = 0
x1 ≥ 0, x2 ≥ 0
Solución. Resolviendo el sistema de ecuaciones
−x1 + x2 = 1
x1 + x2
, se tiene que
x1 =12
y x1 = −12
el cual es punto que se encuentra en el tercer cuadrante y, como se tienen restricciones de positi-
vidad, se concluye que F(P) = ∅.
Ahora, notemos que el dual de (P) es
Min ω = λ1
sar
3.2 Esquema de la dualidad 63
(D)
−λ1 + λ2 ≥ 1
λ1 + λ2 ≥ 1
λ1 ∈ R, λ2 ∈ R
de donde, se tiene que el gradiente de la función a minimizar es ∇ω =
1
0
y, gráficamente
tenemos
1 2−1−2
−1
1
2
l1l2
−∇ω
C−1
Con esto. podemos ver que F(D) 6= ∅ pero no acotado y, además ınf ω = bTλ → −∞.
Un ejemplo que representa el Caso III, es decir, que F(P) y F(D) son conjuntos vacíos, es el
siguiente problema
Max z = x1 + x2
sar
(P)
−x1 + x2 = 1
x1 − x2 = 0
x1 ≥ 0, x2 ≥ 0
A continuación, consideremos los siguientes programas lineales en dualidad
Max z = cTx Min ω = bTλ
sar y sar
(P)
Ax ≤ b
x ≥ 0, x ∈ Rn
(D)
ATλ ≥ c
λ ≥ 0, λ ∈ Rm
TEOREMA 3.5: Holguras ComplementariasTEOREMA 3.5: Holguras Complementarias
x∗ es óptimo para (P) y λ∗ es óptimo para (D) si y solo si λ∗T(b − Ax∗) = 0 y (ATλ∗ −
c)Tx∗ = 0.
64 Dualidad de la Programación Lineal
Demostración. Sean x ∈ F(P) y λ ∈ F(D); notemos que
b − Ax ≥ 0 y ATλ − c ≥ 0
de donde, se tiene claramente que
f = λT(b − Ax) ≥ 0 y g = (ATλ − c)Tx ≥ 0
por lo que, para todo x ∈ F(P) y λ ∈ F(D)
f + g = λTb − λT Ax + λT(AT)Tx − cTx ≥ 0
= bTλ − cTx ≥ 0.
Así, supongamos que x∗ ∈ F(P) y λ∗ ∈ F(D) son óptimos, entonces por el Teorema de
la Dualidad Fuerte, ambos problemas al ser evaluados en sus respectivas soluciones óptimas
proveen idéntico valor óptimo, es decir,
cTx∗ = bTλ∗
por tanto, bTλ∗ − cTx∗ = 0, es decir, f + g = 0 y, como f y g son positivas, la única posibilidad
para que la suma sea cero es que f = 0 y g = 0, es decir,
λ∗T(b − Ax∗) = 0 y (ATλ∗ − c)Tx∗ = 0.
Para la otra implicaciòn, se usa el mismo argumento anterior y se concluye por el Certificado de
Optimalidad.
OBSERVACIÓN. Si consideramos los problemas
Max z = cTx Min ω = bTλ
sar y sar
(P)
Ax = b
x ≥ 0(D)
ATλ ≥ c
λ ∈ Rm
el teorema anterior se reduce a decir que x∗ ∈ F(P) y λ∗ ∈ F(D) son óptimos si y solo si
(ATλ∗ − c)x∗ = 0.
3.3 Modelos Dinámicos de PL 65
3.3 MODELOS DINÁMICOS DE PL
Hasta el momento se han construido modelos estáticos, porque se tomaban una o varias
decisiones al inicio del horizonte de planificación (hp) para optimizar en todo este horizonte un
criterio u objetivo.
utilidad
ganancia
hp
En un modo dinámico o multiperiódico se divide al horizonte de planificación en lapsos llama-
dos periodos (uniformes o no) y se toman decisiones al inicio de cada periodo, con el objetivo
de optimizar una función lineal en todo el hp. Ademàs, las decisiones son al inicio del periodo.
lapsos decisiones
Periodo
t − 2 t − 1 t
EcuacionesInterperiódicas
Estado delsistema
A continuación, presentamos algunos modelos que utilizan este esquema.
MODELO 3.1: Modelo multiperiódico de inventarios (Whitney - 1950)MODELO 3.1: Modelo multiperiódico de inventarios (Whitney - 1950)Supongamos que una empresa produce tractores y debe determinar al inicio de cada tri-
mestre de un año cuántas producir para satidfacer a tiempo una demanda conocida de an-
temano (predicción de la demanda)
t (trimestre) 1 2 3 4
Demanda dt 50 30 75 55
bajo la siguientes condiciones
• Al inicio del año (t = 0) se tienen 5 tractores y se quieren tener 5 tractores al final del
66 Dualidad de la Programación Lineal
año.
• Durante cada trimestre la fábrica tiene una capacidad de producción de 40 tractores en
horas normales a un costo de 400 um. por tractor y a un costo de 450 um. por tractor
en horas extras.
• Al final de cada trimestre todo tractor que no fue vendido debe pagar un costo de
20 um. por tractor y por trimestre y no se puede almacenar más de 5 tractores por
trimestre.
Hipótesis: Al inicio de cada trimestre se debe decidir cuántos tractores producir y, supondremos
que los tractores producidos en un trimestre pueden ser usados para satisfacer la demanda de tractores
en ese trimestre o en el trimestre posterior
La siguiente tabla muestra los precios trimestrales de renta
t 1 2 3 4
pt 800 900 700 850
ht (holding) 20 20 20 20
Plantear un modelo de producción multiperiódica que permita determinar una polìtica
de producción que maximice la uitilidad anual de la empresa, satisfaciéndoce a tiempo las
demandas.
Solución. El horizonte de planificación (periodo) es de un año, dividido en cuatro timestres, de
donde como parte de las decisiones es en conocer, cuántos tractores producir en horas normales
y en horas extras al inicio de cada periodo. Entonces, consideremos las siguientes variables, para
t ∈ {1, 2, 3, 4}
xt : cantidad de tractores producidos al inicio del periodo t, en horas normales.
yt : cantidad de tractores producidos trimestralmente en horas extras.
Además. consideremos las variables de estado
st : cantidad de tractores no vendidos al final del periodo t.
de donde, de las condiciones planteadas, se tiene que para el primer y último perido s0 = 5 y
s4 = 5, respectivamente.
3.3 Modelos Dinámicos de PL 67
t − 1 tst−1 st
xt yt
dt
Así, el modelo queda planteado de la siguiente manera
Max z =4
∑t=1
ptdt
︸ ︷︷ ︸Ingreso anual
−
(4
∑t=1
400xt + 450yt
)
︸ ︷︷ ︸Costos de producción
−4
∑t=1
20st
︸ ︷︷ ︸Costo de inventario
sar
st = st−1 + xt + yt − dt Ec. Interperiódica
s0 = 5, s4 = 5
xt ≤ 40 Límite hrs normales
st ≤ 5 No almacenar más de 5
xt ≥ 0, yt ≥ 0, st ≥ 0, t ∈ {1, 2, 3, 4}
MODELO 3.2: Manpower PlanningMODELO 3.2: Manpower PlanningSe considera una empresa que presta servicios computacionales prestados por sus expertos
por horas. Las demandas, en horas, proyectadas son
(hrs/experto) Enero Febrero Marzo Abril Mayo
Demanda dt 6000 7000 8000 9500 11000
• Al inicio del quimestre la empresa cuenta con 50 expertos que trabajan 160 horas al
mes y ganan $ 2000 al mes.
• Para satisfacer la demanda, la empresa debe capacitar a inexpertos. La capacitación de
cada inexperto toma un mes y requiere de 50 horas de un experto y el sueldo es de
$1000 dólares.
• Al final del mes abandonan la empresa el 5 % de los expertos.
Plantear un modelo de PL multiperiódico que permita determinar una política de contrata-
ción y capacitación de manera que se satisfaga loa demanda al costo laboral en el hp mínimo.
68 Dualidad de la Programación Lineal
Solución. Tomemos como variables de decisión
xinext: cantidad de inexpertos que se contraten al inicio del periodo t, t ∈ {1, ..., 5}
y, como variables de estado
xexpt : cantidad de expertos que trabajan en una empresa al mes t, t ∈ {1, ..., 5}.
El siguiente gráfico muestra la descripción de la ecuación interperiódica:
t
0,95 xexpt−1xexpt
xinext−1
Con esto, formulamos el modelo
Min z =5
∑t=1
200xexpt +5
∑t=1
1000xinext
sar
xexpt = 0, 95xexpt−1 + xinext−1
xexp0 = 50, xinex0 = 0
160xexpt − 50xinext≥ dt
xexpt ≥ 0, xinext≥ 0, t ∈ {1, ..., 5}
MODELO 3.3: Producción o inventariosMODELO 3.3: Producción o inventariosUna compañía que produce cierto artículo enfrenta una demanda que debe satisfacerse a
tiempo de
t (mes) 1 2 3
dt 20 10 15
ct 13 14 15
ht 2 2 2
donde ct es el costo unitario de producción (u.m./articulo), dt es la demanda de los artículos
y ht es el costo de almacenamiento (u.m./mes × art).
En estas situación de los bienes producidos en un mes t, solo la mitad puede ser usa-
da para satisfacer la demanda del mes t. Formular un modelo multiperiódico que defina
una política de producción óptima, satisfaciéndose las demandas y, suponiéndose que se
3.3 Modelos Dinámicos de PL 69
comienza el trimestre con 5 unidades.
Solución. Nuestro horizonte de planificación es un trimestre, con periodos de un mes. Las varia-
bles de decisión a considerar son
xt : cantidad de artículos que se producen al inicio del mes t, t ∈ {1, 2, 3}
y, las variables de estado
st : cantidad de artículos no vendidos en el periodo t.
Representemos cómo se describe la ecuación interperiódica
t
st−1 st
xt
dt
Así, el modelo es
Min z =3
∑t=1
(ctxt + htst)
= 13x1 + 14x2 + 15x3 + 2(s1 + s2 + s3)
sar
st = st−1 + xt − dt
s0 = 5
st−1 +12 xt ≥ dt
xt ≥ 0, st ≥ 0
MODELO 3.4: Modelo de inversionesMODELO 3.4: Modelo de inversionesUna compañía financiera desea determinar una política de inversiones para los próximos
tres años.
• A tiempos t = 0 dispone de $ 100000 para ser invertidos.
• Se tienen a disposición 5 inversiones (A, B, C, D, E) y en la tabla siguiente se da el flujo
efectivo (cash flow)
70 Dualidad de la Programación Lineal
0 1 2 3
A -1.0 0.5 1.0 0
B 0 -1.0 0.5 1.0
C -1.0 1.2 0 0
D -1.0 0 0 1.9
E 0 0 -1.0 1.5
donde, por ejemplo, −1,0 significa que la persona invierte $ 1 y, 0,5 significa que a la
persona le devuelven $ 0.5
Observación: todas estas inversiones se hacen solo una vez en el triaño.
• Se tiene la opción de invertir a un banco a una tasa de interés del 8 % anual.
• Para asegurar la diversificación, ninguna inversión debe ser superior a $ 75000.
• Los réditos obtenidos deben ser inmediatamente reinvertidos y la compañía no puede
hacer préstamos, ni gastos (sistema cerrado).
Formular un modelo multiperiódico que defina una polñitica de inversiones de manera que
al final del triaño se tenga un capital máximo.
Solución. Tomemos las variables de decisión
A : cantidad de dinero que se invierte en la opción A.
B : cantidad de dinero que se invierte en la opción B.
C : cantidad de dinero que se invierte en la opción C.
D : cantidad de dinero que se invierte en la opción D.
E : cantidad de dinero que se invierte en la opción E.
xt : cantidad de dinero que se pone en el banco al inicio del periodo t, t ∈ {0, 1, 2}.
Con esto y, tomando en cuenta que en la función a maximizarse se debe considerar los flujos y
la tasa de interés (8 %) del último periodo y además, que las restricciones siguen la siguiente ley
dinero en mano en el tiempo t = cantidad invertida en el tiempo t;
tenemos el siguiente modelo
Max z = B + 1,9D + 1,5E + 1,08x2
3.3 Modelos Dinámicos de PL 71
sar
A + C + D + x0 = 100000 balance a t = 0
B + x1 = 0,5A + 1,2C + 1,08x0 balance a t = 1
E + x2 = A + 0,5B + 1,08x1 balance a t = 2
A, B, C, D, E ≤ 75000
A, B, C, D, E ≥ 0, xt ≥ 0, t ∈ {0, 1, 2}
MODELO 3.5MODELO 3.5Una empresa quiere definir una política de inversiones para los próximos cinco años. Tiene
a su disposición tres opciones y porta de un capital inicial de $ 150000,
• Opción A : Ganancia anual del 10 %;
• Opción B : Ganancia del 30 % por una inversión por 2 años consecutivos;
• Opción C : Ganancia del 70 % por una inversión de 3 años consecutivos;
Cómo hacer las inversiones de manera que la final del quinto año se tenga un capital máxi-
mo con la restricción de que toda inversión en los dos primeros años sea menor a $ 70000.
Solución. Tomemos las variables de decisión, para cada t ∈ {1, 2, 3, 4, 5}
xtA : cantidad de dinero que se invierte en la opción A al inicio del periodo t,
t ∈ {1, 2, 3, 4, 5}
xtB : cantidad de dinero que se invierte en la opción B al inicio del periodo t,
t ∈ {1, 2, 3, 4}
xtC : cantidad de dinero que se invierte en la opción C al inicio del periodo t,
t ∈ {1, 2, 3}
Ahora, a través de un gráfico veamos cómo se distribuirían las opciones
0 1 2 3 4 5
t = 1x1A
x1B
x1C
x2A
x2B
x2C
x3A
x3B
x3C
x4A
x4Bx5A
72 Dualidad de la Programación Lineal
Así, tenemos el modelo
Max z = 1,1x5A + 1,3x4B + 1,7x3C
sar
x1A + x1B + x1C = 150000
x2A + x2B + x2C = 1,1x1A
x3A + x3B + x3C = 1,3x1B + 1,1x1A
x4A + x4B = 1,7x1C + 1,3x2B + 1,1x3A
x5A = 1,7x2C + 1,3x3B + 1,1x4A
x1A, x1B, x1C ≤ 70000
x2A, x2B, x2C ≤ 70000
xtA, xtB, xtC ≥ 0
CAPÍTULO 4
MÉTODO DEL SIMPLEX
DEFINICIÓN 4.1DEFINICIÓN 4.1
Dado un sistema de ecuaciones subdeterminado Ax = b, A ∈ Rm×n pero m ≤ n, se dice
que una submatriz de A, B ∈ Rm×m es una base de A si es inversible.
OBSERVACIÓN. La matriz A tiene por lo menos una base B si
• rang(A) = m;
• se pueden extraer m columnas linealmente independientes de A.
OBSERVACIÓN. Si conocemos una base B ∈ Rm×n, con m ≤ n, tenemos que
Ax = b ⇐⇒(
B N) xB
xN
= b
⇐⇒ BxB + NxN = b
⇐⇒ BxB = b − NxN
⇐⇒ B−1b − B−1Nxn
Así, en la última implicación se tiene que xB son las variables de base en función de las variables
fuera de la base (solución paramétrica del sistema).
Notación y Terminología: A las matrices B y N las notaremos como
B =(
aB(1) · · · aB(i) · · · aB(m))
y N =(
aN(1) · · · aN(j) · · · aN(n−m))
matriz de base matriz de columnas fuera de base
73
74 Método del Simplex
y, a las variables xB asociadas a las columnas de A que forman la base y a xN les notaremos como
xB(1)
xB(2)...
xB(m)
y
xN(1)...
xN(n−m)
.
DEFINICIÓN 4.2DEFINICIÓN 4.2
Dada A ∈ Rm×n, m ≤ n y B una base; la solución particular del sistema xB = B−1b −
B−1NxN con xN = 0, es decir, xB = B−1b, se dice una solución de base del sistema Ax = b.
EJEMPLO 4.1. Hallar las soluciones de base de
x1 + x2 + x3 = 2
2x1 + x2 + x4 = 3
Solución. Tenemos el sistema subdeterminado con m = 2 y n = 4; tomemos
B1 =(
a2 a1)=
1 1
1 2
de donde se tiene que B1 es invertible, pues det(B1) = 1 6= 0 y, así B1 es una base de A. Con esto
xB1 =
x2
x1
y xN =
x3
x4
Así, tomando los pivotes, considerando la matriz B1, en el sistema de ecuaciones, tenemos
1 1 1 0 2
2 1 0 1 3
−→
1 1 1 0 2
1 0 −1 1 1
−→
0 1 2 −1 1
1 0 −1 1 1
por tanto, el sistema es equivalente a
x2 = 1 − 2x3 + x4
x1 = 1 + x3 − x4
, que son las variables de la base en
función de las que no estàn en B1; así,
x1 = 1 + s − t
x2 = 1 − 2s + t, donde x3 = s y x4 = t con s, t ∈ R.
Así, por ejemplo, una solución de base asociada a B1 es x3 = 0, x4 = 0, x2 = 1 y x1 = 1
(solución particular).
EJEMPLO 4.2. Tomando el ejemplo anterior, encontrar la solución de base asociada a B2 =(a1 a4) =
1 0
2 1
.
75
Solución. Como det(B2) = 1, se tiene que B2 es una base de A, por lo que
xB2 =
x1
x4
y xN2 =
x2
x3
de donde tenemos que
1 1 1 0 2
2 1 0 1 3
−→
1 1 1 0 2
0 −1 −2 1 −1
Por tanto,
x1 = 2 − x2 − x3
x4 = −1 + x2 + 2x3
con lo que la solución de base asociada a la base B2 es
x2 = 0, x3 = 0, x1 = 2 x4 = −1.
DEFINICIÓN 4.3DEFINICIÓN 4.3Consideremos el sistema lineal subdeterminado y restringido
(∗)
Ax = b
x ≥ 0
con A ∈ Rm×n con m ≤ n. Se dice que la solución de base xB = B−1b y xN = 0 es una
solución de base factible si xB ≥ 0.
EJEMPLO 4.3. Considerando el sistema de ecuaciones del Ejemplo 4.1, vemos que
• La solución de base asociada a B1 (x1 = x2 = 1, x3 = x4 = 0) es una solución factible para
el sistema (∗), pues xB1 ≥ 0.
• De la base B2 (Ejemplo 10) nos da como solución de base x1 = 2, x4 = −1, x2 = x3 = 0;
por lo tanto, no es solución de base del sistema (∗).
OBSERVACIÓN. En una solución de base, al menos n − m variables toman el valor de cero y a lo
más m variables de base son no nulas.
DEFINICIÓN 4.4DEFINICIÓN 4.4Si más de n − m variables son nulas, es decir, al menos una varible de base toma el valor de
cero, la solución de base se dice degenerada.
P: En un sistema subdeterminado Ax = b, cuál es el número máximo de bases de A.
Se tendría el número de combinaciones de n columnas tomadas m columnas (combinación si
76 Método del Simplex
repetición), es decir, como máximo número de bases de A se tiene
Cnm =
(n
m
)=
n!(n − m)!m!
.
4.1 PROPIEDADES FUNDAMENTALES DE LA PL
Consideremos un poliedro de un problema de PL en la forma canónica en la forma siguiente
Ax ≤ b, incluidas las restricciones de positividad (−x ≤ 0, −Inx ≤ 0) con A ∈ Rm×n y m ≥ n.
OBSERVACIÓN.
A′x ≤ b
x ≥ 0≡
A′
−In
x ≤
b′
0
Notación: La i_ésima ecuación del sistema de desigualdades Ax ≤ b, le notaremos como
aTi x ≤ bi.
Sea K = {x ∈ Rn|Ax ≤ b}, podemos ver que
• K es convexo;
• K es cerrado y acotado inferiormente, pues contiene las restricciones x ≥ 0, K ⊆ R+
Ahora, supongamos que K 6= ∅ y x0 ∈ K, entonces notemos que
I(x0) ={
i ∈ {1, ..., m}|aTi x0 = bi
}
es el conjunto de índices de las restricciones activas y, el hiperplano de vector normal aTi
L(x0) ={
x ∈ Rn|aT
i x = bi, i ∈ I(x0)}
es una variedad lineal (solución de un sistema de ecuaciones con los índices en I(x0)), el cual
como x0 ∈ L(x0) se tiene que L(x0) 6= ∅.
• Propiedad 1: x0 es un punto extremo de K si y solo si dim(L(x0)) = 0.
• Propiedad 2: Como K es convexo, cerrado, no vacío y acotado inferiormente, entonces K tiene
al menos un punto extremo (último teorema de convexos).
• Propiedad 3: Una función lineal alcanza un máximo o mínimo sobre un extremo de K si el
problema tiene solución finita (último teorema de funciones convexas).
• Propiedad 4: Sea A ∈ Rm×n, m ≥ n y b ∈ R
m, entonces una condición necesaria y suficiente
par que un punto x ∈ K sea un extremo de K es que x sea la solución única de un sistema
Ax = b donde A ∈ Rn×n extraída de A y b es el lado derecho correspondiente.
4.1 Propiedades fundamentales de la PL 77
EJEMPLO 4.4. Supongamos que K ={(x1, x2) ∈ R
2|x1 + x2 ≤ 1, −x1 ≤ 0, −x2 ≤ 0}
Solución. Tenemos que A =
1 1
−1 0
0 −1
y b =
1
0
0
, por lo que
a)
1 1
−1 0
x1
x2
=
1
0
, entonces
1 1 1
−1 0 0
−→
1 1 1
0 1 1
−→
1 0 0
0 1 1
,
es decir, x1 = 0 y x2 = 1.
b) 1 1 1
0 −1 0
−→
1 1 1
0 1 0
−→
1 0 1
0 1 0
,
es decir, x1 = 1 y x2 = 0.
c) −x1 = 0 y −x2 = 0, equivalentemente x1 = 0 y x2 = 0.
Con esto, se tiene los tres puntos extremos del poliedro K. Así,
1−1
−1
1
x1
x2
K
• Propiedad 5 (Caraterística algebraica de los extremos de un poliedro): Sea K = {x ∈ Rn|Ax =
b, x ≥ 0} donde A ∈ Rm×n con m ≤ n y, supongamos que rang (A) = m. Entonces x ∈ R
n es
un punto extremo de K si y solo si x es una solución de base factible de
Ax = b
x ≥ 0.
EJEMPLO 4.5. Consideremos K = {x ∈ R3|2x1 + x2 + 3x3 = 6} con xi ≥ 0, i ∈ {1, 2, 3}.
Solución. Tenemos que m = 1 y n = 3, por tanto las soluciones de base de dicho sistema son
78 Método del Simplex
a) B1 = (a1) = (3), pues x1 = 3 − 12 x2 −
12 x3, de la cual se tiene que un extremo del poliedro
es cuando
x1 = 3, x2 = 0, x3 = 0.
b) B2 = (a2) = (1), pues x2 = 6− 2x1 − 3x3, , de la cual se tiene que otro extremo del poliedro
es
x1 = 0, x2 = 6, x3 = 0.
c) B3 = (a3) = (2), pues x3 = 2− 23 x1 −
13 x2, de la cual se tiene que otro extremo del poliedro
es
x1 = 0, x2 = 0, x3 = 2.
Así, todas las soluciones son factibles, ya que todas son mayores o iguales a cero.
OBSERVACIÓN. Si K = {x ∈ Rn|Ax = b, x ≥ 0} con rang(A) = m y m ≥ n; en este caso, un
punto es extremo de K si y solo si es una solución de base facible de Ax = b, x ≥ 0.
OBSERVACIÓN. Un mismo punto extremo de K puede ser la solución de base asociada a dos
bases distintas.
EJEMPLO 4.6.
x1 + x2 + x3 = 1
x2 + x4 = 1
Solución. Notemos que para B = (a3 a4) =
1 0
0 1
, es evidente que las soluciones de base son
x3 = x4 = 1 y x1 = x2 = 0.
Ahora, tomemos B1 = (a2 a3) =
1 1
1 0
, de donde se tiene
1 1 1 0 1
0 1 0 1 1
−→
1 1 1 0 1
−1 0 −1 1 0
−→
1 1 1 0 1
1 0 1 1 0
−→
0 1 0 1 1
1 0 1 −1 0
≡
x2 = 1 − x4
x3 = x4 − x1
de donde se tiene la solución degenerada x1 = 0 = x4, x2 = 1 y x3 = 0, con lo cual y = (0 1 0 0)
es un punto extremo asociado al sistema de ecuaciones.
Por otro lado, si consideramos B2 = (a2 a4) =
1 0
1 1
, se tiene el mismo punto extremo,
4.2 Repaso de Gauss-Jordan 79
pues
x2 = 1 − x1
x4 = x1 + x3
, de donde, x1 = 0 = x3, x2 = 1 y x4 = 0.
OBSERVACIÓN. El número de extremos de un poliedro K es menor o igual al número de bases
de A.
4.2 REPASO DE GAUSS-JORDAN
Consideremos un sistema subdeterminado Ax = b, A ∈ Rm×n y m ≤ n y B una base de A,
podemos reescribir el sistema como
Ax = b ⇐⇒ ImxB = B−1b − B−1NxN
el cual, es una escritura de un sistema que pone en evidencia la solución de base asociada a B.
x1 · · · xj · · · xk · · · xn b
a11 · · · a1j · · · a1k · · · a1n b1...
......
......
ai1 · · · aij · · · aik · · · ain bi...
......
......
ar1 · · · arj · · · ark · · · arn br...
......
......
am1 · · · amj · · · amk · · · amn bm
Fila delpivote
Columnadel pivote
Pivote
Tomemos ark 6= 0, que será llamado pivote y usemos la regla de Gauss-Jordan para con-
vertir la columna ak en la columna er en la matriz Im. Si aplicamos el método de Gauss-Jordan,
obtenemos un sistema equivalente;
80 Método del Simplex
x1 · · · xj · · · xk · · · xn b
a′11 · · · a′1j · · · 0 · · · a′1n b′1......
......
...a′i1 · · · a′ij · · · 0 · · · a′in b′i...
......
......
a′r1 · · · a′rj · · · 1 · · · a′rn b′r......
......
...a′m1 · · · a′mj · · · 0 · · · a′mn b′m
P: ¿Cómo se obtuvieron dichos valores?
• En la fila del pivote se obtuvieron, para cada j ∈ {1, ..., n}
a′rj =arj
arky b′r =
br
ark.
• Para el término de la i_ésima fila y la j_ésima columna se obtiene a través de la regla del
rectángulo
aij aik
arj ark
......
· · ·
· · ·
es decir, para i 6= r
a′ij = aij −aij arj
arky b′i = bi −
aik br
ark.
EJEMPLO 4.7.
2x1 + x2 − 2x3 = 4
3x1 − 2x2 + x3 = 1. Obtenga la matriz equivalente para r = 2 y k = 1.
Solución.
2 1 −2 4
3 −2 1 1
−→
0 1 + 4
3 −2 − 23 4 − 2
3
1 − 23
13
13
−→
0 7
3 − 83
103
1 − 23
13
13
EJEMPLO 4.8. Usando la regla del rectángulo ponga en evidencia la solución de la base asociada
4.2 Repaso de Gauss-Jordan 81
B = (a3 a1), dada
x1 + x2 + x3 = 3
2x1 + x2 + x4 = 3
Solución. 1 1 1 0 2
2 1 0 1 3
−→
0 1
2 1 − 12
12
1 12 0 1
232
de donde se tiene que x3 = 12 , x1 = 3
2 , x2 = x4 = 0.
DEFINICIÓN 4.5DEFINICIÓN 4.5
Se dicen que dos bases B y B′ de una matriz A ∈ Rm×n (m ≤ n) son vecinas si |B r B′| =
|B′r B| = 1, es decir, B y B′ se diferencian en una sola columna.
OBSERVACIÓN. Se dice que hacemos un pivotaje cuando a partir de una expresión que pone en
evidencia su solución de base asociada a B, es decir,
xB = B−1b − B−1NxN
se llega a otra expresión que pone en evidencia una solución de base asociada a B′ que es vecina
de B, es decir,
xB′ = B′−1b − B
′−1N′xN′
4.2.1 Tabla Condensada (ecuaciones)
Dado un sistema subdeterminado Ax = b, A ∈ Rm×n (m ≤ n) y rang(A) = m. Sabemos que
xB = B−1b − B−1NxN ⇐⇒ xB = B−1b + B−1N(−xN),
podemos poner en una tabla esta expresión
−xN
xB = B−1b B−1N
EJEMPLO 4.9.
x1 + x2 + x3 = 1
2x1 + 3x2 + x4 = 2
Solución. Si B = (a3 a4) = I2, tenemos que la expresión que pone en evidencia la solución de
base asociada a B es 1 1 1 1 1
2 3 0 1 2
82 Método del Simplex
de donde se obtiene que x3 = 1 − x1 − x2 y x4 = 2 − 2x1 − 3x2, escribiendo en la tabla
−x1 −x2
x3 = 1 1 1
x4 = 2 2 3
Un pivotaje será la expresión que pone en evidencia la solución de la base asociada B a la base
vecina B′ = (a3 a2), es decir,
13 0 1 − 1
313
23 1 0 1
323
tabulado es
−x1 −x4
x3 = 13
13 − 1
3
x2 = 23
23
13
de donde, la variable x4 sale de la base y, la variable x2 entra a la base.
Otro pivotaje es considerando la expresión que pone en evidencia la solución de la base
asociada B a la base vecina B′′ = (a1 a4), es decir,
1 1 1 0 1
0 1 −2 1 0
−x2 −x3
x1 = 1 1 1
x4 = 0 1 -2
4.2.2 Reglas de Pivoteo
1) Escogemos un pivote ark 6= 0.
2) Intercambiar las variables de la fila del pivote con la variable fuera de base de la columna del
pivote.
3) Donde esté el pivote en la nueva tabla condensada ponemos 1/ark.
4) La fila del pivote se divide para ark y cambiamos el signo, salvo en la posición del pivote.
5) Los otros términos se calculan por la regla del rectángulo
4.2 Repaso de Gauss-Jordan 83
EJEMPLO 4.10. Supongamos que tenemos B = (a2 a1 a4) y N = (a5 a3 a6) con la tabla conden-
sada (tomamos valores positivos para el pivote)
−x5 −x3 −x6
x2 = 1 2 1 2
x1 = 0 -3 0 1
x4 = 2 0 -1 -5
de donde, bajo las reglas dadas, se tiene que B′ = (a6 a1 a4) y
−x5 −x3 −x2
x6 = 12 1 1
212
x1 = − 12 -4 − 1
2 − 12
x4 = 92 5 3
252
con lo cual la solución no es factible porque tiene un número negativo.
4.2.3 Reglas de Pivoteo del SIMPLEX
Permiten pasar de un extremo de
Ax = b
x ≥ 0a otro extremo "mejor", donde la función obje-
tivo z = cTx toma un valor mayor o igual que en el extremo anterior.
Regla II: Permite pasar de un punto extremo a otro punto extremo mejor.
Supongamos que conocemos un sistema equivalente a Ax = b que pone en evidencia una
solución factible de base (Extremo del Poliedro)
xB = B−1b − B−1NxN con B−1b ≥ 0, xN = 0
−xN
xB = B−1b B−1N
esta tabla condensada la notaremos
84 Método del Simplex
−xN(1) · · · −xN(k) · · · −xN(n−m)
xB(1) =...
xB(i) =...
xB(r) =...
xB(m) =
y10...
yi0...
yr0...
ym0
y11...
yi1...
yr1...
ym1
· · ·
· · ·
· · ·
· · ·
y1k...
yik...
yrk...
ymk
· · ·
· · ·
· · ·
· · ·
y1(n−m)...
yi(n−m)...
yr(n−m)...
ym(n−m)
columna 0 B−1aN(k)
Solución debase factible
donde yi0 ≥ 0 para todo i ∈ {1, ..., m}.
OBSERVACIÓN. B−1N = B−1(
an(1) · · · aN(n−m))=(
B−1an(1) · · · B−1aN(n−m))
.
Hipótesis: supongamos que conocemos la columna k del futuro pivote. Sea yrk el pivote
• En particular, se tiene que y′r0 =yr0
yrk≥ 0, si yrk > 0.
• Si hay varios términos en la k_ésima columna de B−1N; debemos garantizar que el pivote
sea tal que para todo i ∈ {1, ..., m} (i 6= r), y′i0 ≥ 0, es decir,
y′i0 = yi0 −yi0 yik
yrk≥ 0,
de donde, comoyr0
yrk≥ 0,
– si yik ≤ 0, entonces y′i0 ≥ 0;
– si yik > 0, al ser yi0 −yi0 yik
yrk≥ 0, tenemos que
yi0
yik≥
yr0
yrk.
Así, se escoge, para k fijo, la fila del pivote tal que
yr0
yrk= mın
{yi0
yrk
∣∣∣yik > 0}
.
Del Ejemplo 4.10, tomemos k = 3, por lo que elegimos el pivote ubicado en xN(3) = −x6 y, por
la Regla II se tiene que mın{
12 , 0
1
}= 0; por tanto, elegimos la fila r = 2, es decir, la fila del
pivote xB(2) = x1
−x5 −x3 −x6
x2 = 1 2 1 2
x1 = 0 -3 0 1
x4 = 2 0 -1 -5
4.2 Repaso de Gauss-Jordan 85
con lo cual obtenemos
−x5 −x3 −x1
x2 = 1 8 1 2
x6 = 0 -3 0 1
x4 = 2 -15 -1 5
es decir, se tiene la base vecina B′ = (a2 a6 a4).
OBSERVACIÓN. B−1N = B−1(
aN(1) · · · aN(n−k))=(
B−1aN(1) · · · B−1aN(n−k))
, es decir, pa-
ra j ∈ {1, ..., n − m}
y·j = B−1aN(j).
Se puede ver que aB(r) ∈ B puede ser reemplazado por aN(k) ∈ N para obtener una base vecina
B′ = B r
{aB(r)
}∪{
aN(k)}
si y solo si yrk 6= 0.
Ahora, consideremos un problema de PL en la forma estándar
Max z = cTx
sar
Ax = b
x ≥ 0
con A ∈ Rm×n ,m ≤ n y rang(A) = m. Sea B una base factible de A, es decir, xB = B−1b ≥ 0,
xN = 0. Notemos que
z = cTx = cTBxB + cT
N xN .
Sabemos que la solución de base B es xB = B−1b − B−1NxN , sustituyendo
z = cTB
(B−1b − B−1NxN
)+ cT
N xN
= cTBB−1b −
(cT
BB−1N + cTN
)xN .
Llamemos z0 = cTBB−1b, valor de la función z objetivo en el punto extremo asociado a la base B
y, notemos que
z = z0 − ∑j: aN(j)∈N
(cT
BB−1aN(j) + cj
)xj;
86 Método del Simplex
llamemos zj = cTBB−1aN(j) para todo j tal que aN(j) ∈ N. Por tanto, se tiene la función z expresada
en función del valor fuera de la base xj,
z = z0 − ∑j: aN(j)∈N
(zj − cj)xj.
Regla I: para elegir una varible xk, aN(k) ∈ N solamente hay que elegir que zk − ck < 0.
4.3 REGLA CLÁSICA DEL SIMPLEX
Tomar la variable xk tal que zk − ck es el número más negativo.
Tabla condensada del SIMPLEX
−xN
z = z0 zj − cj
xB = B−1b B−1aN(j)
OBSERVACIÓN. La Regla I elige la columna del pivote
OBSERVACIÓN. La actualización de la tabla condensada del SIMPLEX se hace usando las mis-
mas reglas de actualización vistas. Esto debido a que la fila 0 puede considerarse como otra
ecuación
z − cTx = 0
Ax = b.
4.3.1 Algoritmo particular del SIMPLEX
Dado un problema de PL, tenemos
• Paso 0: Poner al problema de PL en la forma estándar, es decir,
Max z = cTx
sar
Ax = b
x ≥ 0
rang(A) = m, m ≤ n. Hipótesis: el sistema tiene una base B factible, es decir, existe un punto
extremo.
4.3 Regla Clásica del SIMPLEX 87
• Paso 1: construya la tabla condensada del simplex asociada a la base B.
• Paso 2 (Paso iterativo): Aplique las reglas I y I I de pivotaje del SIMPLEX
a) Si se puede encontrar un pivote yrk, actualizar la tabla de simplex;
b) Sino
– si no se puede aplicar la Regla I, quiere decir que zj − cj ≥ 0, para todo j tal que
aN(j) ∈ N.
FIN: el extremo corriente es óptimo.
– si pasa la Regla I, es decir, existe k tal que aN(k) ∈ N tal que zk − ck < 0, pero y·k ≤ 0.
FIN: el problema es NO acotado.
EJERCICIO 4.1 (Un ’buen’ ejemplo). Aplicar el algoritmo de simple al siguiente problema de
PL
Max z = 5x1 + 8x2
sar
(P)
x1 + x2 ≤ 2
x1 − 2x2 ≤ 0
−x1 + 4x2 ≤ 1
x1 ≥ 0, x2 ≥ 0
Solución. Notemos que el problema (P) está en la forma canónica, entonces
Paso 0: reescribimos el problema en su forma estándar
Max z = 5x1 + 8x2
sar
(PE)
x1 + x2 + s1 = 2
x1 − 2x2 + s2 = 0
−x1 + 4x2 + s3 = 1
x1 ≥ 0, x2 ≥ 0
s1 ≥ 0, s2 ≥ 0, s3 ≥ 0
Notemos que el sistema de restricciones Ax = b es tal que A ∈ R3×5.
88 Método del Simplex
Paso 1: como B0 = (a3 a4 a5) =
1 0 0
0 1 0
0 0 1
= I3; se tiene que B0 es factible, pues si x1 = 0 y
x2 = 0 entonces s1 = 2, s2 = 0 y s3 = 1, es decir, xT0 =
(0 0 2 0 1
)es una solución de base
factible del sistema, dicho de otro modo, es un punto extremo del poliedro en la forma estándar.
Por la Regla I, tomamos el pivote en la columna 2 (k = 2), es decir, xN(2) = −x2, pues, el más
negativo de zj − cj es -8; además, la tabla asociada a la base (tabla del simplex inicial) es
−x1 −x2
z = 0 -5 -8
s1 = 2 1 1
s2 = 0 1 -2
s3 = 1 -1 4
por otro lado, se toma la fila del pivote r = 3, es decir, xB(3) = s3 porque mın{
21 , 1
4
}= 1
4
(recordar que los negativos no se consideran para el mínimo, yik > 0). Así, actualizamos la tabla
−x1 −s3
z = 2 -7 2
s1 = 7/4 5/4 -1/4
s2 = 1/2 1/2 1/2
x2 = 1/4 -1/4 1/4
Se toma el nuevo pivote 12 , pues por la Regla I, el zj − cj más negativo es el −7 (k = 1, xN(1) =
−x1) y, por la Regla II se toma mın{
7/45/4 , 1/2
1/2
}= 1, (r = 2, xB(2) = s2).
Con esto, tenemos que z = 2+ 7x1 − 2s3, la nueva base es B1 = (a3 a4 a2) y xT1 =
(0 1
474
12 0
).
Nuevamente, actualizamos la tabla
−s2 −s3
z = 9 (14 9) > 0
s1 = 1/2 -5/2 -3/2
x1 = 1 2 1
x2 = 1/2 1/2 1/2
En consecuencia, como ya no se puede aplicar la Regla I, hemos encontrado la solucón óptima
de (P), es decir,
x∗1 = 1, x∗2 =12
, z∗ = 9 y s∗1 =12
, s∗2 = 0, s∗3 = 0.
4.3 Regla Clásica del SIMPLEX 89
4.3.2 Explicación de la Optimalidad
Sabemos que si B es una base factible de Ax = b, entonces
z = z0 − ∑j: aj∈N
(zj − cj)xj
si para todo j, se tiene que zj − cj ≥ 0.
Si cualquier variable fuera de base xj toma un valor positivo en una misma base vecina
z′0 ≤ z0, entonces el extremo corriente es un máximo local, por la convexidad de z y, entonces z0
es un máximo global.
EJERCICIO 4.2. Resolver por el método del SIMPLEX el Modelo 1.1, planteado como
Max z = 8x1 + 6x2
sar
(P)
5x1 + 3x2 ≤ 30
2x1 + 3x2 ≤ 24
x1 + 3x2 ≤ 18
x1 ≥ 0, x2 ≥ 0
Solución. Reescribiendo el problema (P) en su forma estándar, tenemos
Max z = 8x1 + 6x2
sar
(PE)
5x1 + 3x2 + s1 = 30
2x1 + 3x2 + s2 = 24
x1 + 3x2 + s3 = 18
x1 ≥ 0, x2 ≥ 0
s1, s2, s3 ≥ 0
Tomamos la base factible B0 = (a3 a4 a5) y, por la Regla I elegimos la columna k = 1 (xN(1) =
−x1) y por la Regla II tomamos la fila r = 1 (xB(1) = s1), pues mın{
305 , 24
2 , 181
}; con esto, partimos
de xT0 =
(0 0 30 24 18
)y, se tiene la tabla inicial
90 Método del Simplex
−x1 −x2
z = 0 -8 -6
s1 = 30 5 3
s2 = 24 2 3
s3 = 18 1 3
Actualizamos la tabla,
−s1 −x2
z = 48 8/5 -6/5
x1 = 6 1/5 3/5
s2 = 12 -2/5 9/5
s3 = 12 -1/5 12/5
el cual se obtuvo B1 = (a1 a4 a5) y xT1 =
(6 0 0 12 12
); además, dicho pivote se obtuvo
por la Regla I, k = 2 (xN(2) = −x2) y por la Regla II, mın{
63/5 , 12
9/5 , 1212/5
}= 5, tomamos r = 3,
(xB(3) = s3).
Finalmente, se tiene la última actualización
−s1 −s3
z = 54 3/2 1/2
x1 = 3 3/12 -1/4
s2 = 3 -3/12 -3/4
x2 = 5 -1/12 5/12
EJERCICIO 4.3 (Un problema no acotado). Consideremos el problema
Max z = x1 + 2x2
sar
(P)
−x1 + x2 ≤ 2
x2 ≤ 3
x1 ≥ 0, x2 ≥ 0
Solución. Reescribimos el problema
Max z = x1 + 2x2
4.3 Regla Clásica del SIMPLEX 91
sar
(PE)
−x1 + 2x2 + x3 = 2
x2 + x4 = 3
xi ≥ 0, i ∈ {1, 2, 3, 4}
Tenemos la tabla
−x1 −x2
z = 0 -1 -2
x3 = 2 -1 1
s4 = 3 0 1
de donde, se obtuvo dicho pivote tomando k = 2 (el más negativo), xN(2) = −x2 y r = 1(mın
{ 21 , 3
1
}= 2
), xB(1) = x3. Además, notemos que, en la Regla I, si hubiese salido k = 1 ya se
encontraría que no hay pivote. Actualizamos la tabla y tomamos el pivote en k = 1 (xN(1) = −x1)
y r = 2 (xB(2) = x4) (único positivo)
−x1 −x3
z = 4 -3 2
x1 = 2 -1 1
x4 = 1 1 -1
Una nueva actualización
−x4 −x3
z = 7 3 -1
x2 = 3 1 0 ≤ 0
x1 = 1 1 -1 ≤ 0
y, vemos que por la Regla I se toma k = 2, pero para seguir con la Regla II se tiene que y·2 ≤ 0.
Por tanto, el problema NO es acotado.
92 Método del Simplex
1 2−1−2−3
−1
1
2
3
x1
x2
b
b
b
Demostración. (Existencia del problema NO Acotado)
Supongamos que B es una base de A ∈ Rm×n en cuya tabla del simplex asociada exista
j : aN(j) ∈ N tal que zj − cj < 0 y y·j = B−1aN(j) ≤ 0,
• Notemos, por un lado, que como y·j = B−1aN(j) entonces By·j = aN(j), es decir,
m
∑i=1
yijaB(i) = aN(j) (Ax = x1a1 + · · ·+ xnan)
• Por otro lado, xB = B−1b, es decir, BxB = b,
m
∑i=1
xB(i)aB(i) = b
Sea d < 0, vemos quem
∑i=1
(xB(i)a
B(i) + daN(j))− daN(j) = b
y, sustituyendo aN(j) tenemos
m
∑i=1
(xB(i) + dyij
)aB(i) − daN(j) = b.
Así, tenemos las soluciones
xB(i) + dyij para las variables de base
−d positivo para aN(j)
0 para las variables fuera de base
.
4.3 Regla Clásica del SIMPLEX 93
Con esto, se tiene que las soluciones son factibles para todo d < 0 para el sistema
Ax = b
x ≥ 0.
Además, si calculamos el valor de z para estas soluciones obtenemos
z = cTB[xB(i) + dyij]− cjd
= cTBxB + d
[cT
Byij − cj
]
= cTBxB + d
[cT
BB−1aN(j) − cj
]
= cTBxB + d [zj − cj]︸ ︷︷ ︸
<0
Con esto, si d → −∞ se colige que z → +∞.
4.3.3 Soluciones Degeneradas
Si tenemos una tabla del simplex
z = z0 zk − ck
yr0 yrk
≤ 0
> 0
En la base vecina B′, la función objetivo toma el valor
z′0 = z0 −yr0(zk − ck)
yrk> z0
si yr0 6= 0.
a) SIMPLEX o terminación finita: Si el algoritmo del simplex nunca produce soluciones de
base degeneradas, entonces culmina en un número finito de iteraciones.
b) Ciclos: Hay ejemplos para los cuales el método del simplex es tal que yr0 = 0, es decir,
z′0 = z0 y en algún momento se regresa a una base ya visitada, es decir, como el algoritmo es
determinístico se produce un ciclo
Pivoteo lexicográfico de plano
Bland (1980) propuso las siguientes reglas de pivotaje
• R′1 : se escoge la columna k tal que
k = mın{
j | zj − cj < 0}
.
94 Método del Simplex
• R′2 : se escoge la fila del pivote r tal que
B(r) = mın{
i ∈ {1, ..., m}∣∣∣yi0
yik= mın
{yl0
ylk
∣∣∣yl0 > 0}}
.
EJEMPLO 4.11. Supongamos que tenemos la siguiente tabla
−x1 −x8 −x6 −x4
z = 38 2 -100 -50 -10
x5 = 6 1 2 0 3
x7 = 5 4 3 2 -1
x3 = 4 -1 -1 0 2
x2 = 2 0 1 0 1
Se toma dicho pivote pues, para la columna se tiene que k = mın {4, 6, 8} = 4 (el mínimo
índice j tal que zj − cj sea negativo), es decir, xN(4) = −x4; en cambio, para la fila, primero
buscamos mın{
63 , 4
2 , 21
}= 2 (r = 4), de donde se tomaría el mínimo subíndice tal que se tenga la
igualdad, es decir, mın{5, 3, 2} = 2 , de donde, xB(4) = x2; así, se tiene una solución degenerada
y, aplicando lo ya conocido se actualiza la tabla.
Con estas reglas se puede demostrar que NO se producen ciclos. Además, en la práctica se
aplican pivotajes çasiïgual al clásico y nunca se ha reportado un ciclo.
En la práctica, si se usa la regla de Bland, el método del simplex hace más iteraciones para
encontrar el otro.
EJERCICIO 4.4 (Problema con soluciones multiperiódicas).
Max z = x1 + 2x2
sar
x1 + 2x2 ≤ 4
x2 ≤ 1
x1 ≥ 0 x2 ≥ 0
Solución. La solución gráfica de este problema es
[A, B] =
{λ
(21
)+ (1 − λ)
(40
)∣∣∣0 ≤ λ ≤ 1}
4.3 Regla Clásica del SIMPLEX 95
1 2 3 4 5−1−1
1
2
x1
x2
b
b
A
BC0
C4
l1
l2
Aplicando el método del simplex tenemos
−x1 −x2
z = 0 -1 -2
s1 = 4 1 2
s2 = 1 0 1
actualizando
−x1 −s2
z = 2 -1 2
s1 = 2 1 -2
x2 = 1 0 1
Hacemos otra iteración
−s1 −s2
z = 4 1 0
x1 = 2 1 -2
x2 = 1 0 1
de donde, se tiene la solución óptima x∗1 = 2 y x∗2 = 1 con z∗ = 4.
Sin embargo, existen múltiples soluciones para este problema, ya que si hacemos el nuevo
pivotaje tomando la columna xN(2) = −s2 (pues zK − cK = 0) y la fila xB(2) = x2, y2k = 1 > 0,
nos lleva a otro punto extremo solución
−s1 −x2
z = 4 1 0
x1 = 4 1 1
s2 = 1 0 1
es decir, x∗1 = 4, x∗2 = 0, s∗1 = 0 y s∗2 = 1.
96 Método del Simplex
4.4 ALGORITMO DEL SIMPLEX GENERAL
OBSERVACIÓN. Dado un problema de PL cualquiera siempre se le puede expresar en la forma
Max z = cTx
sar
Ax = b
x ≥ 0
con b ∈ Rm tal que b ≥ 0 y A ∈ R
m×n con m y n cualesquiera.
EJEMPLO 4.12. Consideremos el problema
Max z = x1 − x2 + x3
sar
x1 − x2 + x3 ≥ −3
2x1 + x2 ≤ 5
x1 − x2 − x3 = 8
x2 + x3 ≤ −1
x1, x2, x3 ≥ 0
así, al problema se lo puede reescribir como
Max z = x1 − x2 + x3 Max z = x1 − x2 + x3
sar ≡ sar
x1 − x2 + x3 − x4 = −3
2x1 + x2 + x5 = 5
x1 − x2 − x3 = 8
x2 + x3 + x6 = −1
xi ≥ 0, i ∈ {1, ..., 6}
−x1 + x2 − x3 + x4 = 3
2x1 + x2 + x5 = 5
x1 − x2 − x3 = 8
−x2 − x3 − x6 = 1
xi ≥ 0, i ∈ {1, ..., 6}
OBSERVACIÓN. Dado un problema de PL en la forma
Max z = cTx
sar
4.4 Algoritmo del SIMPLEX general 97
(P)
Ax = b
x ≥ 0
Para saber si (P) es factible se resuelve el problema auxiliar
Min ω =m
∑i=1
yi
sar
(PA)
Ax + Imy = b
x ≥ 0, y ≥ 0
de donde, podemos aplicar el simplex particular para resolver este problema a partir de la base
inicial B0 = Im asociada a las variables artificiales yi, i ∈ {1, ..., m}
xB = y = b ≥ 0
xN = x = 0
Propiedad: si el óptimo del problema (PA) toma un valor óptimo de ω∗> 0 entonces (P) no
es factible.
Demostración. Supongamos que ω∗> 0 y que (P) es factible, es decir, existe x ∈ R
n tal que
Ax = b
x ≥ 0.
Además, se tiene (x, 0) es factible para el problema (PA) y ω en este punto vale 0, lo cual
genera una contradicción al hecho de que ω∗> 0.
OBSERVACIÓN. ¿Cómo se aplica el simplex para un problema de minimización? Si B es una base
factible de un sistema subdeterminado
Ax = b
x ≥ 0con A ∈ R
m×n (m ≤ n), sabemos que
z = z0 − ∑j: aN(j)∈N
(zj − cj)xj.
Si se quiere minimizar, se aplican las siguientes reglas
• R′1 : se escoge en la tabla del simplex asociada a la base B una columna k tal que zk − ck > 0
(método clásico, se toma el más positivo).
98 Método del Simplex
• R′2 : similar a R2; pues esta regla permite pasar de un extremo a otro.
Test de Optimalidad: zj − cj ≤ 0 para todo j : aN(j) ∈ N.
4.4.1 Método de las dos fases del simplex general
Dado un problema de PL en la forma
Max z = cTx
sar
(P)
Ax = b
x ≥ 0
con b ≥ 0 y A ∈ Rm×n, se tiene
• Fase I: encontrar un punto extremo de (P), si (P) es un problema factible
– Se resuelve el problema auxiliar (PA) asociada a (P). Si ω∗> 0.
FIN: problema (P) no factible.
– Si en alguna iteración ω = 0, es decir,m
∑i=1
yi = 0, es decir para todo i se tiene que
yi = 0, i ∈ {1, ..., m}
a) Si todas las yi están fuera de la base B.
FIN: pues se encuentran variables xB(i), i ∈ {1, ..., m}, de base asociada a las varia-
bles originales x.
ω = 0
−y1 −y2 −xj · · · −xk
xB(1)...
xB(m)
y10...
ym0
b) Por lo menos una de las variables artificiales yi está en la base, por lo que la solu-
ción de la base es degenerada y se puede tomar un pivote yrk 6= 0
ω = 0
−xk
ωk − ck
...yi
...0 yik
4.4 Algoritmo del SIMPLEX general 99
c) Existe una variable artificial yi en la base y no se le puede intercambiar con una
variable original xk porque yrk = 0.
En la tabla se puede ver que la i_ésima restricción o igualdad del sistema Ax = b
es redundante, luego la podemos eliminar y regresar a a).
ω = 0
−xk · · · −xj
...yi 0 · · · 0
• Fase II: Usar iterativamente el método del simplex simplificado. Con esto, se puede deter-
minar si (P)
– Tiene solución óptima finita; o
– Es NO acotado.
EJERCICIO 4.5. Aplicando el método anterior, resuelva el siguiente problema
Max z = 2x1 + x2
sar
(P)
x1 + 2x2 + x3 = 5
3x1 − 2x2 + 3x3 = 2
x1, x2, x3 ≥ 0
Solución. Fase I: resolvemos el problema auxiliar
Min ω = y1 + y2
sar
(PA)
x1 + 2x2 + x3 + y1 = 5
3x1 − 2x2 + 3x3 + y2 = 2
x1, x2, x3 ≥ 0 y1, y2 ≥ 0
Notando que
w = y1 + y2
= (5 − x1 − 2x2 − x3) + (2 − 3x1 + 2x2 − 3x3)
100 Método del Simplex
= 7 − 4x1 − 4x3
tenemos la tabla inicial
−x1 −x2 −x3
ω = 7 4 0 4
z = 0 -2 -1 0
y1 = 5 1 2 1
y2 = 2 3 -2 3
y, recordando que estamos minimizando, el pivote se obtuvo por la R′1, el más positivo de ωj − cj
(k = 1) y, por la R′2, mın
{ 51 , 2
3
}= 2
3 (r = 2). Así, actualizamos la tabla
−y1 −x2 −x3
ω = 13/3 -4/3 8/3 0
z = 4/3 2/3 -7/3 2
y1 = 13/3 -1/3 8/3 0
x1 = 2/3 1/3 -2/3 1
Realizamos la última iteración
−y1 −y2 −x3
ω = 0
z = 41/8 2
x2 = 13/8 0
x1 = 7/4 1
Terminamos la Fase I, pues hemos encontrado variables xB(i) de la base asociada a las variables
originales. Ahora, pasamos a la Fase II
−x3
z = 41/8 2
x2 = 13/8 0
x1 = 7/4 1
de donde, no se puede aplicar la Regla I del agoritmo del simplex simplificado, pues se tiene
z3 − c3 ≥ 0, por lo que el algoritmo termina y, hemos encotrado el extremo óptimo, es decir,
x∗1 =74
, x∗2 =138
, x∗3 = 0
4.4 Algoritmo del SIMPLEX general 101
asociada a B =(a2 a1).
EJERCICIO 4.6. Resolver el siguiente problema
Max z = −x1 + x2
sar
(P)
x1 − x2 = 1
2x1 + 3x2 = −3
x1 ≥ 0 x2 ≥ 0
Solución. Gráficamente vemos que el problema es infactible (F(P) = ∅)
1 2−1−2−3−1
−2
−3
1
x1
x2
l1l2
pues, no cumple con la restricción de positividad.
Amplicando el algoritmo, tenemos que el problema auxiliar es
Min ω = y1 + y2
sar
(PA)
x1 − x2 + y1 = 1
−2x1 − 3x2 + y2 = 3
x1, x2 ≥ 0 y1, y2 ≥ 0
de donde, realizando la tabla para minimizar ω tenemos
−x1 −x2
ω = 4 -1 -4
z = 0 1 -1
y1 = 1 1 -1
+ + +
y2 = 3 -2 -3
102 Método del Simplex
con lo cual, como todos los ωj − cj son negativos, se tiene que la solución es óptima con ω∗ =
4 > 0 y, en consecuencia, el algoritmo termina concluyendo que (P) no es factible.
EJERCICIO 4.7. Resolver
Max z = −x1 + x2
sar
(P)
12 x1 − x2 +
32 x3 = 1
x1 − 2x2 + 3x3 = 2
x1 ≥ 0 x2 ≥ 0, x3 ≥ 0
Solución. Fase I: problema auxiliar
Min ω = y1 + y2
sar
(P)
12 x1 − x2 +
32 x3 + y1 = 1
x1 − 2x2 + 3x3 + y2 = 2
x1, x2, x3 ≥ 0 y1, y2 ≥ 0
tabulamos y tomamos el pivote
−x1 −x2 −x3
ω = 3 3/2 -3 9/2
z = 0 1 -1 0
y1 = 1 1/2 -1 3/2
y2 = 2 1 -2 3
actualizamos y, tachamos la variable artificial y1 de la base, pues no se puede intercambiar con
alguna variable original xk
−x1 −x2 −y2
ω = 0 0 0 -3/2
z = 0 1 -1 0
y1 = 0 0 0 -1/2
x3 = 2/3 1/3 -2/3 1/3
4.4 Algoritmo del SIMPLEX general 103
esto quiere decir que la primera ecuación asociada y1 es redundante. Luego, pasamos a la Fase
II, teniendo
−x1 −x2
z = 0 1 -1
x3 = 2/3 1/3 -2/3
de donde, por la Regla I tenemos k = 2, pero y·2 ≤ 0; por tanto, el algoritmo termina concluyen-
do que el problema es NO acotado.
EJERCICIO 4.8. Considere el siguiente problema de PL
Max z = 3x1 + x2
sar
(P)
2x1 + x2 ≥ 2
x1 − x2 ≤ 0
x1 ≥ 0 x2 ≥ 0
a) Resuelva (P) por el método de las dos fases.
b) Describa gráficamente la primera y segunda etapa.
c) Calcule el dual de (P).
Solución. Primero, reescribimos el problema en su forma estándar, donde x3 y x4 representarán
las variables de holgura
Max z = 3x1 + x2
sar
(PE)
2x1 + x2 − x3 = 2
x1 − x2 + x4 = 0
xi ≥ 0 i ∈ {1, 2, 3, 4}
a) Fase I: escribimos el problema auxiliar
Max z = y1 + y2
sar
104 Método del Simplex
(PEA)
2x1 + x2 − x3 + y1 = 2
x1 − x2 + x4 + y2 = 0
xi ≥ 0 i ∈ {1, 2, 3, 4}
y1 ≥ 0, y2 ≥ 0
Con esto, construimos la tabla
−x1 −x2 −x3 −x4
ω = 2 3 0 -1 1
z = 0 -3 -1 0 0
y1 = 2 2 1 -1 0
y2 = 0 1 -1 0 1
Tomamos dicho pivote, pues el más positivo wj − cj es para k = 1 y, como mın{ 2
2 , 01
}= 0 se
tomó r = 2. Así, actualizamos la tabla y tomamos el nuevo pivote
−y2 −x2 −x3 −x4
ω = 2 -3 3 -1 -2
z = 0 3 -4 0 3
y1 = 2 -2 3 -1 -2
x1 = 0 1 -1 0 1
−y2 −y1 −x3 −x4
ω = 0
z = 8/3 -4/3 1/3
x2 = 2/3 -1/3 -2/3
x1 = 2/3 -1/3 1/3
Con esto, pasamos a la Fase II, teniendo la tabla
−x3 −x4
z = 1/3 -4/3 1/3
x2 = 2/3 -1/3 -2/3
x1 = 2/3 -1/3 1/3
y, como estamos maximizando z, tomamos el más negativo, en k = 1, pero al tener y·1 ≤ 0,
se termina el algoritmo, dándonos un problema NO acotado.
4.4 Algoritmo del SIMPLEX general 105
b) Lo que las dos fases terminan describendo, gráficamete es
1 2 3−1
−1
1
2
x1
x2
l1 l2
C0
C8/3
Fase I
Fase II
b
c) Puesto que tenemos dos restricciones, tomamos λ1 y λ2 como las variables duales; así, tene-
mos
Min ω = 2λ1
sar
(D)
2λ1 + λ2 ≥ 3
λ1 − λ2 ≥ 1
λ1 ≤ 0, λ2 ≥ 0
Llamando β1 = −λ1, reescribimos (D)
Min ω = −2β1
sar
(D)
−2β1 + λ2 ≥ 3
−β1 − λ2 ≥ 1
β1 ≥ 0, λ2 ≥ 0
Resolviendo dicho problema, tendríamos que expresarlo en su forma estándar
Min ω = −2β1
sar
(D)
−2β1 + λ2 − λ3 = 3
−β1 − λ2 − λ4 = 1
β1 ≥ 0, λ2, λ3, λ4 ≥ 0
106 Método del Simplex
y, partiríamos del problema auxiliar
Min ω = y1 + y2
sar
(DA)
−2β1 + λ2 − λ3 + y1 = 3
−β1 − λ2 − λ4 + y2 = 1
β1 ≥ 0, λ2, λ3, λ4 ≥ 0
y1 ≥ 0, y2 ≥ 0
Así, recordando el esquema de la dualidad, F(D) debe ser vacío, es decir, el conjunto factible
no debe estar en el primer cuadrante y, siguiendo el algoritmo de las dos fases se debe tener
que ω∗> 0.
4.4.2 Interpretación de las variables duales y costos reducidos
PROPOSICIÓN 4.1. Si B es una base óptima del problema de PL
Max z = cTx
sar
(P)
Ax = b
x ≥ 0
con rang(A) = m, entonces el vector λ∗TB = cT
BB−1 es el vector de las variables duales
óptimas
Demostración. Notemos que z∗ = cTBx∗B = (cT
BB−1)b = λ∗TB b = ω∗, es decir,
z∗ = ω∗.
Ahora, falta mostrar que λB es factible para el dual (D). Así, sabemos que el dual de (P) es
Min ω = λTb
sar
(D)
ATλ ≥ c ⇔ λT A ≥ cT
λ ∈ Rm
4.4 Algoritmo del SIMPLEX general 107
y, notemos que
λ∗T A − cT = λ∗T(
B N)−(
cTB cT
N
)
= cTBB−1
(B N
)−(
cTB cT
N
)
=(
cTB cT
BB−1N)−(
cTB cT
N
)
=(
0 cTBB−1N − cT
N
)
=(
0 z1 − c1 · · · zN(n−m) − cn−m
)
La última igualdad se tiene debido a que, como B es factible se verifica que zj − cj ≥ 0, para todo
j tal que aN(j) ∈ N, es decir,
zj − cj = cTBB−1aN(j) − cj ≥ 0
particularmente cTBB−1N − cT
N ≥ 0, lo que implica que λ∗AT − cT ≥ 0, es decir, λ es factible para
(D).
OBSERVACIÓN. Si B es una base admisible o factible para (P) se sabe que
z = z0 − ∑j: aN(j)∈N
(zj − cj)xj
de donde
∂z
∂xk=
−(zk − ck) si k : aN(k) ∈ N
0 si xk : a(k) ∈ B=
ck − zk si xk está fuera de la base
0 si xk está en la base
Los términos ck − zk se dicen costos reducidos, representan el cambio marginal de z con respecto
a la variable xk, es decir, el cambio de z cuando xk pasa a xk+1.
PROPOSICIÓN 4.2. Si B∗ es una base óptima para (P) y el lado derecho del sistema b ∈ Rm,
cambia a b + ∆b y suponemos que el nuevo problema
Max z = cTx
sar
(P′)
Ax = b + ∆b
x ≥ 0
la base óptima B∗ no cambia y, entonces ∆z = λ∗∆b.
108 Método del Simplex
Solución. Supongamos que la solución óptima de (P) es xB = B−1b y xN = 0 y, a la solución
óptima de (P′) llamémosla xB + ∆xB y cumple
B(xB + ∆xB) = b + ∆b
BxB + B∆xB = b + ∆b
B∆xB = ∆b
∆xB = B−1∆b.
Además,
z∗ + ∆z = cTB(xB + ∆xB) = cT
BxB + cTB∆xB = z∗ + (cT
BB−1)∆b,
de donde se tiene que
∆z = λ∗TB ∆b
= λ∗1(∆b)1 + · · ·+ λ∗
i (∆b)i + · · ·+ λ∗m(∆b)m
Así, cuando b → b + ∆b y la base óptima no cambia, el cambio de z es igual a ∆z que es una
combinación lineal de las variables duales óptimas por los cambios en b.
EJEMPLO 4.13. Supongamos que tenemos ∆b=(
0 0 · · · 1 0 · · · 0)
, entonces vemos que
∆z = λ∗i (unidad de z / unidad de la i_ésima restricción), es decir, la i_ésima variable dual del
problema óptimo mide el cambio de z cuando ∆bi = 1.
4.4.3 Análisis de Sensibilidad
Son técnicas matemáticas que se aplican a un problema de PL para determinar los intervalos
en que se puede modificar el lado derecho del sistema sin que la base cambie y se mantenga, por
tanto, la interpretación de las variables duales.
CAPÍTULO 5
PROGRAMACIÓN LINEAL ENTERA
DEFINICIÓN 5.1DEFINICIÓN 5.1Sabemos que un problema de PL es de
1. Programación Lineal Entera si todas las variables xi deben tomar valores enteros
xi ∈ Z+ = {0, 1, 2, ...}, i ∈ {1, ..., n}.
2. Programación Lineal Entera Mixta si un subconjunto de variables deben tomar valores
enteros y otro subconjunto de valores reales.
3. Programación Lineal Bivalente si las variables xi pueden tomar solo los valores 0 o 1,
xi ∈ {0, 1}.
Las variables bivalentes sirven para modelizar decisiones del tipo todo o nada, es decir
xi =
1 si se ejecuta una acción
0 si no
5.1 MODELOS
Consideremos el siguiente problema de PL
Max z = x1 + 2x2
sar
(P)
x1 + x2 ≤ 6,4
+(R)
donde R representan las restricciones del problema. Así, veamos los siguientes casos
109
110 Programación Lineal Entera
1. Si (R) : x1, x2 ∈ Z+, vemos que gráficamente tenemos
1 2 3 4 5 6−1−1
1
2
3
4
5
6
x1
x2
F: discreto(finito o numerable)
Con esto, podemos verificar que F es no convexo. Además, los problemas (PLE) son difíciles
de resolver por lo que se suele relajar al problema, por ejemplo, resolviendo (P) únicamente
con restricciones de positividad tenemos que x1∗ = 0 y x2
∗ = 6,4 con z∗ = 12,8, de donde se
intuye que x∗1 = 0 y x∗2 = 6 con z∗ = 12.
2. Si (R) : x1 ∈ Z+ y x2 ≥ 0, gráficamente tenemos
1 2 3 4 5 6−1−1
1
2
3
4
5
6
x1
x2
F
Con esto, notemos que F es no contable y no convexo y, la solución del problema es x∗1 = 0 y
x∗2 = 6,4 con z∗ = 12,8.
3. Si (R) : x1 ≥ 0 y x2 ∈ {1, 0} tenemos
5.1 Modelos 111
1 2 3 4 5 6−1−1
1
2
3
4
5
6
x1
x2
F
de donde, se tiene que la solución es x∗1 = 6,4 y x∗2 = 0 con z∗ = 6,4.
4. Si (R) : x1, x2 ∈ {0, 1}, tenemos
1 2 3 4 5 6−1−1
1
2
3
4
5
6
x1
x2
F
cuya solución es x∗1 = 1 y x∗2 = 1 con z∗ = 3.
OBSERVACIÓN. Si tenemos n variables bivalentes, el cubo unitario de Rn tiene 2n vértices.
DEFINICIÓN 5.2DEFINICIÓN 5.2Los métodos Heurísticos son métodos aproximados que tratan de buscar rápidamente una
solución factible "buena".
EJEMPLO 5.1. Resolver el siguiente problema
Max z = 21x1 + 11x2
sar
112 Programación Lineal Entera
(P)
7x1 + 4x2 ≤ 13
x1 ∈ Z+, x2 ∈ Z
+
Solución. Para resolver el problema aplicaremos la siguiente Heurística
1. Resolver el problema lineal relajado, es decir, con restricciones del tipo x1 ≥ 0 y x2 ≥ 0.
2. Redondear la solución obtenida por el PL.
Con esto, obtengamos primero la solución del problema relajado
1 2 3−1−1
1
2
3
x1
x2
C0
C39
Gráficamente, se tiene que la solución del problema relajado es
x∗1 =137
y x∗2 = 0 con z∗ = 39.
Así, una forma de redondear es
x1 = 2 y x2 = 0,
sin embargo, solución no es factible, pues está fuera del conjunto.
Otra forma de redondear es
¯x1 = 1 y ¯x2 = 0,
con ¯z∗ = 21. No obstante, la solución óptima del problema (P) es x∗1 = 0 y x∗2 = 3 con z∗ =
33.
5.1.1 Modelización de problemas PLE
MODELO 5.1: Problema de Knapsack (Mochila)MODELO 5.1: Problema de Knapsack (Mochila)Un andinista tiene una mochila que soporta a lo más W kg. Tiene a su disposición n objetos
diferentes, cada uno de los cuales tiene un peso wi > 0 y un valor ci > 0, i ∈ {1, ..., n}.
¿Cómo debe elegir el andinista sus objetos de manera que el peso total no sobrepase la
capacidad y que tenga este cargamento un valor máximo?
5.1 Modelos 113
Solución. Definimos las variables de decisión (variables bivalentes)
xi =
1 si el i_ésimo objeto va a la mochila
0 si no
por lo que el problema se plantea como
Max z =n
∑i=1
cixi
sar
(P)
n
∑i=1
wixi ≤ W capacidad
xi ∈ {0, 1}, i ∈ {1, ..., n}
MODELO 5.2: Problema de Knapsack generalMODELO 5.2: Problema de Knapsack generalSupongamos que tenemos n clases Ci, de peso wi y de valor ci, i ∈ {1, ..., n}, donde cada clase
tiene objetos iguales. ¿Cómo determinar un cargamento de valor máximo que no sobrepase
la capacidad de la mochila W kg.?
Solución. Tomamos las variables
xi : número de objetos de la i_ésima clase Ci que van a la mochila, i ∈ {1, ..., n}
Así, tenemos
Max z =n
∑i=1
cixi
sar
(P)
n
∑i=1
wixi ≤ W
xi ∈ Z+, i ∈ {1, ..., n}
MODELO 5.3MODELO 5.3Una empresa explora cuatro inversiones que se las debe hacer completamente y, dispone de
14000 u.m.
114 Programación Lineal Entera
INV 1 INV 2 INV 3 INV 4
Desembolso al 5000 7000 4000 3000
inicio del año
Rendimiento al 16000 22000 12000 8000
final del año
¿Cuál es el portafolio óptimo de inversiones?.
Solución. Nos planteamos una decisión de todo o nada, es decir, si invierto o no invierto; por
tanto, tomamos las variables, para cada i ∈ {1, 2, 3, 4}
xi =
1 si participamos en la inversión i
0 si no
de donde, se tiene el modelo
Max z = 16000x1 + 22000x2 + 12000x3 + 8000x4 rendimiento
sar
(P)
5000x1 + 7000x2 + 4000x3 + 3000x4 ≤ 14000 desembolso
xi ∈ {0, 1}, i ∈ {1, 2, 3, 4}
Por la Observación 24, tenemos 24 = 16 posibles soluciones. Así, bajo este ejemplo plantearemos
algunas Heurísticas
1. Tomar las inversiones por el mayor rendimiento
Ordenamos las inversiones de mayor a menor, es decir,
x2 ≻ x1 ≻ x3 ≻ x4
y vamos restando a nuestro monto actual; así,
x2 = 1, r1 = 14000 − 7000 = 7000
ahora, tomamos
x1 = 1, r2 = 7000 − 5000 = 2000
y, puesto que x3 requiere de 4000 u.m.ya no podemos seleccionarlo, por tanto x3 = 0 = x4.
5.1 Modelos 115
Con esto,
x1T =
(1 1 0 0
)con z1 = 38000 u.m.
2. Ordenar las inversiones en orden creciente de los desembolsos
x4 � x3 � x1 � x2
y, con la misma lógica anterior tenemos
x4 = 1, r1 = 14000 − 3000 = 11000
x3 = 1, r2 = 11000 − 4000 = 7000
x1 = 1, r3 = 7000 − 5000 = 2000
x2 = 0,
es decir,
x2T =
(1 0 1 1
)con z2 = 36000 u.m.
3. Ordenar decrecientemente las inversiones por redimiento/desembolso: esta regla es la que más se
emplea
x1 � x2 � x3 � x4.
Con esto,
x1 = 1, r1 = 14000 − 5000 = 9000
x2 = 1, r2 = 9000 − 7000 = 2000
x3 = 0
x4 = 0
es decir,
x3T =
(1 1 0 0
)con z3 = 38000 u.m.
Aun así, la solución óptima es
x∗1 = 0, x∗2 = x∗3 = x∗4 = 1 con z∗ = 42000.
116 Programación Lineal Entera
5.1.2 Restricciones Adicionales
a. No se hagan más de dos inversiones
x1 + x2 + x3 + x4 ≤ 2.
b. Que se haga solo una de las INV 3 e INV 4
x3 + x4 = 1.
c. Si se participa en la INV 2 no se debe participar en INV 1, es decir, si x2 = 1 entonces x1 = 0
x1 + x2 ≤ 1.
d. Si participa INV 3 entonces obligatoriamente participa en INV 4, es decir, si x3 = 1 entonces
x4 = 1
x4 − x3 ≥ 0 ⇐⇒ x4 ≥ x3.
MODELO 5.4: Localización de InstalacionesMODELO 5.4: Localización de InstalacionesSe quiere decidir en qué barrios B1, ..., B6 instalar estaciones de bomberos en el menor nú-
mero, de manera que si se produce un incidente en cualquier barrio se tenga una instalación
próxima que atienda al incidente en menos de 15 minutos. Se presenta la tabla de tiempos
de Bi a Bj en minutos
B2 B3 B4 B5 B5
B1 10 20 30 30 20
B2 0 25 35 20 10
B3 0 15 30 20
B4 0 15 20
B5 0 14
Supondremos que los tiempos son simétricos. Formular un modelo de PLE que permita
resolver este problema
Solución. Tomamos las variables de decisión, para cada i ∈ {1, 2, 3, 4, 5, 6}
xi =
1 si se instala una estación de bomberos en el barrio Bi;
0 si no.
5.1 Modelos 117
Además, para plantear las restricciones, debemos considerar los tiempos de Bi a Bj, i, j ∈ {1, ..., 6}
(i 6= j), menores o iguales a 15; así, tomamos un barrio i y vemos los tiempos menores o iguales
a 15 hacia otro barrio, recordando que los tiempos son simétricos, es decir, el tiempo en ir de Bi
a Bj es igual al tiempo de ir de Bj a Bi; por lo que tenemos
• B1 : a B2 se puede ir en un lapso de 10 minutos.
• B2 : a B1 en 10 min y a B6 en 10 min.
• B3 : a B4 en 15 min.
• B4 : a B3 en 15 min y a B5 en 15 min.
• B5 : a B4 en 14 min. y a B6 en 14 min.
• B6 : a B2 en 10 min y a B5 en 14 min.
Con esto, formulamos el modelo
Min z = x1 + x2 + x3 + x4 + x5 + x6
sar
(P)
x1 + x2 ≥ 1 seguridad para B1
x1 + x2 + x6 ≥ 1 seguridad para B2
x3 + x4 ≥ 1 seguridad para B3
x3 + x4 + x5 ≥ 1 seguridad para B4
x4 + x5 + x6 ≥ 1 seguridad para B5
x2 + x5 + x6 ≥ 1 seguridad para B6
xi ∈ {0, 1}, i ∈ {1, 2, 3, 4, 5, 6}
Para el siguiente modelo recordemos lo siguiente
Costo fijo (k): costo que no depende del número de productos elaborados.
Costo variable o costo unitario (v): costo que depende de cada unidad producida.
costo total = costo f ijo + x(costo variable)
= k + v x
costo total =
0 si x = 0
k + v x si x > 0
118 Programación Lineal Entera
MODELO 5.5: Producción con costo fijo o Modelo de cargaMODELO 5.5: Producción con costo fijo o Modelo de cargaUna empresa que elabora artículos deportivos puede producir: camisetas, pantalones y bu-
zos. La elaboración de cada uno de estos productos requiere de maquinaria especial que se
la puede alquilar a: 200 um/semana, 150 um/semana y 350 um/semana, respectivamente.
Los datos se presentan en la siguiente tabla
Mano de obra Tela PVP Costos unitarios
(hr/trabajo) (m2) (um/unidad) de producción
Camiseta 3 4 12 6
Pantaloneta 2 3 8 4
Buzos 6 4 15 8
Disponibilidad 150 160
semanal
Formular un modelo de PLEM que permita determinar un plan de producción de utilidad
semanal máxima.
Solución. Tomamos las siguientes variables
xi : cantidad del i_ésimo producto a elaborar en la semana, i ∈ {1, 2, 3}.
yi =
1 si se alquila la maquinaria para elaborar el i_ésimo producto;
0 si no
Ahora, para plantear las restricciones de capacidad se debe verificar que, por el ejemplo, el nú-
mero máximo de camisetas a producirse es lo mínimo de disponibilidad semanal respecto a
mano de obra o tela, es decir,
mın{
1503
,160
4
}= 40
y, a esto se debe verificar que
si y1 = 0 entonces x1 = 0 y si y1 = 1 entonces x1 ≤ 40.
Análogamente, se tiene las restricciones de capacidad para pantalones y buzos. Así, el modelo
es
Max z = (12 − 6)x1 + (8 − 4)x2 + (15 − 8)x3
− 200y1 − 150y2 − 350y3
sar
5.1 Modelos 119
(P)
3x1 + 2x2 + 6x3 ≤ 150
4x1 + 3x2 + 4x3 ≤ 160
x1 ≤ 40y1
x2 ≤1603
y2
x3 ≤ 25y3
xi ≥ 0, yi ∈ {0, 1}, i ∈ {1, 2, 3}
MODELO 5.6: Modelo de AsignaciónMODELO 5.6: Modelo de AsignaciónSe supone que se tienen que realizar m trabajos, T1, ..., Tm en n máquinas M1, ..., Mn, m ≤ n.
Se conoce la eficiencia cij de procesamiento del trabajp Ti si se lo realiza en la máquina Mj.
¿Cómo asignar cada trabajo a una y solo una máquina, de manera que la eficiencia total sea
máxima.
Solución. Al problema, gráficamente lo podemos representar de la siguiente manera
Tm
...
Ti
...
T1
Mn
...
Mj
...
M1
cij xij
x11
x1j
xmj
Así, tomemos las variables de decisión
xij =
1 si el trabajo Ti es asignado a la máquina Mj
0 si no
para i ∈ {1, ..., m} y j ∈ {1, ..., n}. Por tanto, considerando las dos restricciones
• Todo trabajo se asigna a una sola máquina, y
• Toda máquina procesa a lo más a uno de los trabajos
tenemos el modelo
Max z =m
∑i=1
n
∑j=1
cijxij
120 Programación Lineal Entera
sar
(P)
n
∑j=1
xij = 1 i ∈ {1, ..., m}
m
∑i=1
xij ≤ 1 j ∈ {1, ..., n}
xij ∈ {0, 1}, ∀i, ∀j
MODELO 5.7MODELO 5.7Se tienen que realizar cuatro trabajos en cuatro máquinas. En la tabla se muestra el costo de
arranque (set up costs) o de preparación (limpieza, calibración)
M1 M2 M3 M4
T1 14 2 7 2
T2 5 12 8 4
T3 8 6 3 6
T4 7 5 9 10
Formule un modelo de asignación que permita minimizar los costos totales de arranque.
Solución. Planteamos las variables
xij =
1 si el trabajo Ti va a la máquina Mj
0 si no
para todo i, j ∈ {1, 2, 3, 4} y, tomando en cuenta que todo trabajo va a una sola máquina, se tiene
el modelo
Max z = 14x11 + 2x12 + 7x13 + 2x14 + · · ·+ 10x44
sar
5.1 Modelos 121
(P)
x11 + x12 + x13 + x14 = 1
x21 + x22 + x23 + x24 = 1
x31 + x32 + x33 + x34 = 1
x41 + x42 + x43 + x44 = 1
x11 + x21 + x31 + x41 = 1
x12 + x22 + x32 + x42 = 1
x13 + x23 + x33 + x43 = 1
x14 + x24 + x34 + x44 = 1
xij ∈ {0, 1}, i, j ∈ {1, 2, 3, 4}
MODELO 5.8: Modelo de LocalizaciónMODELO 5.8: Modelo de LocalizaciónSe considera una zona geográfica para el estudio (país,provincias, ciudades); mediante tra-
bajos preliminares de prospección se han determinado m localizaciones posibles para cons-
truir bodegas, cada una de las bodegas tiene un costo de construcción ki y una capacidad de
almacenamiento de ci unidades de un producto. Por otro lado, se conoce que en esta región
hay n clientes del producto cuyas localizaciones son conocidas, con demanda de bj unida-
des, n >>> m; se conoce el costo unitario de transporte desde la bodega i hacia el cliente j,
notado por cij, es decir, se conoce Cm×n =(cij
).
¿Dónde se deben construir las bodegas para minimizar los costos de construcción y de
transporte que permita satisfacer la demanda de todos los clientes?.
j
2
13
4
n
i
1
2
m
ki
ci
xij
xi1
Solución. Formulamos las variables
xij : cantidad enviada desde la bodega i al cliente j
122 Programación Lineal Entera
yi =
1 si se construye la bodega i
0 si no
para todo i ∈ {1, ..., m} y todo j ∈ {1, ..., n}. Con esto, planteamos el modelo
Min z =m
∑i=1
kiyi +m
∑i=1
n
∑j=1
cijxij
sar
(P)
n
∑j=1
xij ≤ ciyi i ∈ {1, ..., m}
m
∑i=1
xij ≥ bj j ∈ {1, ..., n}
xij ≥ 0, ∀i, ∀j
yi ∈ {0, 1}, j ∈ {1, ..., n}
BIBLIOGRAFÍA
[1] Bertsimas, D. y Tsitsiklis, J. Introduction to Linear Optimization. Athena Scientific, Estados
Unidos, 1997.
[2] Winston, W. Investigación de Operaciones, Aplicaciones y Algoritmos. Thomson, México, 2005.
123