UCM _Universidad Complutense de Madrid_ _ Grado en Matemáticas _ Investigación operativa _ Io_zip

Esta es una vista previa del archivo. Inicie sesión para ver el archivo original

Io/Programaci?n Entera/Alg_Dakin.pdf
ALGORITMO DE DAKIN (Problema de minimización)
Paso 1. Resolver la relajación lineal de (P ). Si es infactible, PARAR (el problema (P ) es
infactible). Si su solución óptima x verifica que xj es entero ∀j ∈ J , PARAR (x es
solución óptima de (P )). Poner z∗ = +∞ e incluir en la lista de subproblemas a analizar
a dicha relajación.
Paso 2. Seleccionar un subproblema (S) a analizar y eliminarlo de la lista.
Paso 3. Seleccionar una variable xBl tal que Bl ∈ J y fBl > 0, donde B es una base óptima de (S),
definir dos nuevos subproblemas (S1) y (S2) introduciendo respectivamente la restricción
xBl ≤ [xBl ] y la restricción xBl ≥ [xBl ] + 1 en la región factible de (S), y resolver ambos
subproblemas. Si (S1) es infactible o el valor óptimo de su función objetivo es mayor o
igual que z∗, ir al Paso 5.
Paso 4. Si (S1) posee solución óptima x tal que xj es entero ∀j ∈ J , poner x∗ = x, z∗ = ctx
y eliminar de la lista de subproblemas a analizar todos aquellos con valor óptimo de la
función objetivo mayor o igual que z∗. En otro caso, incluir en la lista de subproblemas a
analizar a (S1).
Paso 5. Si (S2) es infactible o el valor óptimo de su función objetivo es mayor o igual que z
∗, ir
al Paso 7.
Paso 6. Si (S2) posee solución óptima x tal que xj es entero ∀j ∈ J , poner x∗ = x, z∗ = ctx
y eliminar de la lista de subproblemas a analizar todos aquellos con valor óptimo de la
función objetivo mayor o igual que z∗. En otro caso, incluir en la lista de subproblemas a
analizar a (S2).
Paso 7. Si no queda ningún subproblema por analizar, PARAR (si z∗ = +∞, el problema (P ) es
infactible; en otro caso, x∗ es una solución óptima de (P ), y el valor óptimo de la función
objetivo es z∗). Ir al Paso 2.
ALGORITMO DE DAKIN (Problema de maximización)
Paso 1. Resolver la relajación lineal de (P ). Si es infactible, PARAR (el problema (P ) es
infactible). Si su solución óptima x verifica que xj es entero ∀j ∈ J , PARAR (x es
solución óptima de (P )). Poner z∗ = −∞ e incluir en la lista de subproblemas a analizar
a dicha relajación.
Paso 2. Seleccionar un subproblema (S) a analizar y eliminarlo de la lista.
Paso 3. Seleccionar una variable xBl tal que Bl ∈ J y fBl > 0, donde B es una base óptima de (S),
definir dos nuevos subproblemas (S1) y (S2) introduciendo respectivamente la restricción
xBl ≤ [xBl ] y la restricción xBl ≥ [xBl ] + 1 en la región factible de (S), y resolver ambos
subproblemas. Si (S1) es infactible o el valor óptimo de su función objetivo es menor o
igual que z∗, ir al Paso 5.
Paso 4. Si (S1) posee solución óptima x tal que xj es entero ∀j ∈ J , poner x∗ = x, z∗ = ctx
y eliminar de la lista de subproblemas a analizar todos aquellos con valor óptimo de la
función objetivo menor o igual que z∗. En otro caso, incluir en la lista de subproblemas
a analizar a (S1).
Paso 5. Si (S2) es infactible o el valor óptimo de su función objetivo es menor o igual que z
∗, ir
al Paso 7.
Paso 6. Si (S2) posee solución óptima x tal que xj es entero ∀j ∈ J , poner x∗ = x, z∗ = ctx
y eliminar de la lista de subproblemas a analizar todos aquellos con valor óptimo de la
función objetivo menor o igual que z∗. En otro caso, incluir en la lista de subproblemas
a analizar a (S2).
Paso 7. Si no queda ningún subproblema por analizar, PARAR (si z∗ = −∞, el problema (P ) es
infactible; en otro caso, x∗ es una solución óptima de (P ), y el valor óptimo de la función
objetivo es z∗). Ir al Paso 2.
Io/Programaci?n Entera/Alg_planos_corte.pdf
ALGORITMO DE LOS PLANOS DE CORTE FRACCIONALES
Paso 1. Resolver la relajación lineal de (P ). Si es infactible, PARAR (el problema (P ) es
infactible). Si su solución óptima x es entera, PARAR (x es solución óptima de (P )).
Paso 2. Seleccionar la fila fuente l, calcular la ecuación del plano de corte fraccional e introducirla
en el problema (P ). Ir al Paso 1.
Criterios de selección de la fila fuente
• l = mı́n {i ∈ {1, . . . ,m} | fBi > 0}
• l = argmáx {fBi | i ∈ {1, . . . ,m} con fBi > 0}
• l = argmáx
{
fBi∑n−m
j=1 fi,Nj
| i ∈ {1, . . . ,m} con fBi > 0
}
• l = argmáx {Pi | i ∈ {1, . . . ,m} con fBi > 0}, donde
Pi=

fBi mı́n
{
−
zNj − cNj
fi,Nj
| j ∈ {1, . . . , n−m} con fi,Nj > 0
}
si (P ) es de minimización
fBi mı́n
{
zNj − cNj
fi,Nj
| j ∈ {1, . . . , n−m} con fi,Nj > 0
}
si (P ) es de maximización
Plano de corte fraccional de Gomory:
n−m∑
j=1
fl,NjxNj ≥ fBl
ALGORITMO DE LOS PLANOS DE CORTE MIXTOS
Paso 1. Resolver la relajación lineal de (P ). Si es infactible, PARAR (el problema (P ) es
infactible). Si su solución óptima x verifica que xj es entero ∀j ∈ J , PARAR (x es
solución óptima de (P )).
Paso 2. Seleccionar la fila fuente l, calcular la ecuación del plano de corte mixto (fortalecido) e
introducirla en el problema (P ). Ir al Paso 1.
Criterios de selección de la fila fuente
Análogos a los del Algoritmo de planos de corte fraccionales.
Plano de corte mixto de Gomory:
∑
j∈J+
yl,NjxNj +
fBl
fBl − 1
∑
j∈J−
yl,NjxNj ≥ fBl
Plano de corte mixto fortalecido de Gomory:∑
j∈J+
Nj /∈J
yl,NjxNj +
fBl
fBl − 1
∑
j∈J−
Nj /∈J
yl,NjxNj +
n−m∑
j=1
Nj∈J
fBl≥fl,Nj
fl,NjxNj +
fBl
fBl − 1
n−m∑
j=1
Nj∈J
fBl<fl,Nj
(fl,Nj − 1)xNj ≥ fBl
Io/Programaci?n Entera/Hoja6.pdf
PROBLEMAS DE INVESTIGACIÓN OPERATIVA HOJA 6
1. Una persona desea invitar a una fiesta a sus compañeros de trabajo A,B,C,D, pero éstos le
han impuesto algunas condiciones para asistir: A y C no están dispuestos a coincidir en la
fiesta; B acepta coincidir con C o con D, pero no con ambos a la vez; D no está dispuesto
a coincidir con A a no ser que B asista a la fiesta. Formular el problema de programación
lineal entera a resolver para conseguir que asista el mayor número posible de personas.
2. En una localidad se ha realizado una campaña de recogida de ayuda humanitaria para
los damnificados en una catástrofe natural. Se ha introducido en cajas del mismo tamaño
todo el material recogido, obteniéndose 12 cajas de alimentos, 17 de medicamentos, 11 de
instrumental quirúrgico y 18 de ropa. Se dispone de cuatro camiones para transportar las
cajas hasta las zonas afectadas: dos de ellos poseen una capacidad máxima de diez cajas,
y los otros dos de nueve cajas. No se permite que ningún camión transporte más de cinco
cajas con el mismo tipo de material y, si algún camión transporta más de tres cajas con
instrumental quirúrgico, entonces debe transportar al menos cuatro cajas con medicamentos.
Formular el problema de programación lineal entera a resolver para conseguir transportar el
mayor número posible de cajas (cada camión únicamente realiza un viaje).
3. Dado un conjunto de objetos de m tipos distintos, para cada ı́ndice i ∈ {1, . . . ,m} se denota
por ai al peso de cada objeto de tipo i y por ui al número de objetos de tipo i. Formular el
problema de programación lineal a resolver para conseguir empaquetar todos los objetos en
el menor número posible de cajas, sabiendo que el peso máximo que soporta cada caja es b.
4. El problema de los cuatro colores consiste en colorear todos los páıses de un mapa utilizando
a lo sumo cuatro colores distintos, de forma que cada par de páıses vecinos (es decir, con una
parte de frontera en común) tengan distinto color. Formularlo mediante programación lineal
entera.
5. La región factible de un problema de programación no lineal viene dada por las restricciones
n−1∏
j=1
x
aj
j =xn y xj∈{0, 1} ∀j∈{1, . . . , n−1}, donde aj∈IN ∀j∈{1, . . . , n−1}. Transformarla
en la región factible de un problema de programación lineal entera.
6. Un agente comercial que viaja habitualmente por diez zonas Z1, . . . , Z10 ha de estar localizable
en todas ellas a través de un teléfono móvil. Para ello, podrá elegir entre seis teléfonos
T1, . . . , T6, cada uno
de ellos de una empresa distinta. La siguiente tabla contiene el coste de
adquisición (expresado en euros) de cada teléfono y las zonas en las que posee cobertura:
Coste Cobertura
T1 360 Z1, Z2, Z6, Z10
T2 300 Z3, Z4, Z5, Z9
T3 250 Z3, Z7, Z8, Z10
T4 195 Z1, Z5, Z6, Z8
T5 110 Z2, Z3, Z4, Z7, Z9
T6 60 Z5, Z6, Z7, Z8, Z10
Con objeto de prevenir posibles aveŕıas, el agente desea disponer de al menos dos teléfonos con
cobertura en la zona Z3. Además, se le exige que si T5 es el único teléfono que ha adquirido
con cobertura en la zona Z9, entonces debe disponer exactamente de un teléfono que posea
cobertura conjunta de las zonas Z1 y Z6.
Formular el problema de programación lineal a resolver para determinar qué teléfonos ha de
adquirir el agente de forma que el coste de los mismos sea lo menor posible.
7. El propietario de una boutique de pan utiliza, además de agua, tres ingredientes I1, I2 e I3,
cada uno de los cuales lo adquiere en paquetes de un kilogramo a un precio de 3, 2 y 4 euros por
paquete respectivamente. A partir de estos ingredientes elabora cuatro tipos de pan T1, T2, T3
y T4, y vende cada barra de cada uno de los tipos a 4, 2, 5 y 3 euros respectivamente.
La siguiente tabla contiene la cantidad, expresada en gramos, que se requiere de cada
ingrediente para elaborar una barra de cada uno de los tipos de pan:
T1 T2 T3 T4
I1 150 70 100 120
I2 20 110 50 90
I3 80 60 130 40
Cada d́ıa es posible elaborar a lo sumo 200 barras de cada tipo de pan, se dispone de un
presupuesto de 250 euros para la adquisición de los ingredientes y hay que desechar los
ingredientes no utilizados. Además, si no se elabora pan de tipo T2, entonces deben elaborarse
a lo sumo 150 barras de pan de tipo T3, y ha de elaborarse pan de al menos tres de los tipos.
Suponiendo que se vende todo el pan que se elabora, formular el problema de programación
lineal a resolver para determinar, para cada d́ıa, cuántos paquetes de cada uno de los
ingredientes deben adquirirse y cuántas barras de pan de cada uno de los tipos han de
elaborarse, de forma que el beneficio neto obtenido (sin considerar el coste del agua utilizada)
sea lo mayor posible.
8. Se desea organizar un concierto en el que actúen cuatro grupos musicales, en un local con aforo
para 500 personas, y el precio de cada entrada será de 20 euros. Hay siete grupos musicales
G1, . . . , G7 dispuestos a actuar. Para cada uno de los grupos, la siguiente tabla contiene su
número de fans, aśı como el coste de contratarlo para actuar en el concierto (expresado en
euros):
Grupo G1 G2 G3 G4 G5 G6 G7
No fans 120 90 130 110 150 80 140
Coste 1500 1000 1400 1200 1600 1100 1300
Los fans de cada grupo acudirán al concierto si y solo si actúa dicho grupo, y ningún par de
grupos tiene fans en común.
El propietario del local ha impuesto las siguientes condiciones:
• Si no se contrata al grupo G1 ni al G5, entonces debe contratarse al grupo G2.
• Si se contrata a los grupos G3 y G7, entonces debe contratarse también al grupo G6.
• Si no se contrata al grupo G3, entonces debe contratarse o bien al grupo G1 o bien al
grupo G4 (exactamente a uno de los dos).
Formular el problema de programación lineal a resolver para determinar qué grupos han de
contratarse de forma que el beneficio neto obtenido sea lo mayor posible.
9. Un empresario dispone de contrato de telefońıa móvil con cinco empresas E1, . . . , E5. Para
cada una de las empresas, la siguiente tabla contiene el coste por minuto expresado en céntimos
de euro de las llamadas nacionales e internacionales, aśı como el tiempo máximo total mensual
expresado en minutos que al empresario le está permitido hablar con el teléfono de dicha
empresa:
Empresa E1 E2 E3 E4 E5
Coste llamadas nacionales 4 3 5 6 2
Coste llamadas internacionales 55 65 25 30 95
Tiempo máximo 1800 2500 1400 2000 1500
Se supone que durante el próximo mes la duración total de las llamadas nacionales e
internacionales que realizará el empresario será de 3000 y 900 minutos respectivamente, y
que la duración de cada una de las llamadas expresada en minutos es un número entero.
Además, la duración total de las llamadas internacionales que realice con el teléfono de cada
empresa no puede ser superior a la de las llamadas nacionales que realice con dicho teléfono.
Si no se realiza ninguna llamada internacional con el teléfono de E1, entonces la duración
total de las llamadas nacionales que se realicen con el teléfono de E3 ha de coincidir con la
de las llamadas internacionales que se realicen con dicho teléfono.
Si no se realiza ninguna llamada con el teléfono de E2, entonces la duración total de las
llamadas nacionales que se realicen con el teléfono de E5 no puede ser superior a 50 minutos.
Formular el problema de programación lineal a resolver para determinar la duración total de
las llamadas nacionales e internacionales a realizar durante el próximo mes con el teléfono de
cada una de las cinco empresas con objeto de minimizar el coste total asociado.
10. Una fábrica de muebles ha recibido un pedido de tres sofás A, B y C. La fabricación de
los sofás se realiza en dos etapas: en primer lugar, un carpintero construye el armazón y,
posteriormente, un tapicero lo tapiza. La fábrica únicamente dispone de un carpintero y de
un tapicero, y se supone que cuando están trabajando en un sofá no pueden interrumpir su
trabajo para comenzar a trabajar en otro sofá.
La siguiente tabla contiene el número de d́ıas que el carpintero y el tapicero le tienen que
dedicar a cada sofá:
Carpintero Tapicero
A 4 9
B 2 4
C 5 3
Formular el problema de programación lineal a resolver para determinar en qué orden deben
trabajar el carpintero y el tapicero con objeto de finalizar los tres sofás en el menor tiempo
posible.
Io/Programaci?n Entera/Hoja7.pdf
PROBLEMAS DE INVESTIGACIÓN OPERATIVA HOJA 7
1. Resolver los siguientes problemas de programación lineal entera mediante métodos de planos
de corte:
(a) Max z = x1 − 3x2 + 3x3
s.a: 2x1 + x2 − x3 ≤ 4
4x1 − 3x2 ≤ 2
−3x1 + 2x2 + x3 ≤ 3
x1, x2, x3 ≥ 0 enteras
(b) Min z = 4x1 + 5x2
s.a: 3x1 + x2 ≥ 2
x1 + 4x2 ≥ 5
3x1 + 2x2 ≥ 7
x1, x2 ≥ 0 enteras
(c) Max z = x1 − 3x2 + 3x3
s.a: 2x1 + x2 − x3 ≤ 4
4x1 − 3x2 ≤ 2
−3x1 + 2x2 + x3 ≤ 3
x1, x2, x3 ≥ 0
x2, x3 enteras
2. Resolver los siguientes problemas de programación lineal entera mediante procedimientos de
ramificación y acotación:
(a) Min z = 3x1 + 2x2
s.a: 3x1 + x2 ≥ 6
x1 + x2 ≥ 3
x1, x2 ≥ 0 enteras
(b) Max z = 7x1 + 9x2
s.a: −x1 + 3x2 ≤ 6
7x1 + x2 ≤ 35
x1, x2 ≥ 0 enteras
(c) Max z = 2x1 − x2 − 4x4
s.a: 2x1 − 2x2 − 4x3 + 8x4 = −5
x1 + x3 − x4 = 3
x1, . . . , x4 ≥ 0
x1, x3 enteras
Io/Programaci?n Entera/Modeliz_var_bin.pdf
MODELIZACIÓN MEDIANTE VARIABLES BINARIAS
1) Implicaciones entre variables binarias
Sean x1 y x2 dos variables binarias.
x1 = 0 ⇒ x2 = 0 x2 ≤ x1
x1 = 0 ⇒ x2 = 1 1− x2 ≤ x1
x1 = 1 ⇒ x2 = 0 x2 ≤ 1− x1
x1 = 1 ⇒ x2 = 1 x1 ≤ x2
2) Restricciones disyuntivas
Sean S ⊆ IRn, f, g : S → IR, f y g cotas inferiores de f y g en S respectivamente,
g una cota superior de g en S y x ∈ S.
f(x) ≥ 0 o g(x) ≥ 0 f(x) ≥ f δ, g(x) ≥ g (1− δ), δ ∈ {0, 1}
f(x) ≥ 0 o g(x) = 0 f(x) ≥ f δ, g (1− δ) ≤ g(x) ≤ g (1− δ), δ ∈ {0, 1}
Sean S ⊆ IRn, f1, . . . , fm : S → IR, f1, . . . , fm cotas inferiores de f1, . . . , fm en S
respectivamente, y x ∈ S.
f1(x) ≥ 0 o f2(x) ≥ 0 o . . . o fm(x) ≥ 0
ppp
fj(x) ≥ fj (1− δj) ∀j ∈ {1, . . . ,m},
m∑
j=1
δj = 1, δj ∈ {0, 1} ∀j ∈ {1, . . . ,m}
3) Restricciones alternativas
Sean S ⊆ IRn, f1, . . . , fm : S → IR, f1, . . . , fm cotas inferiores de f1, . . . , fm en S
respectivamente, x ∈ S y k ∈ {2, . . . ,m− 1}.
“De las m restricciones fj(x) ≥ 0 ∀j ∈ {1, . . . ,m} deben cumplirse al menos k”
ppp
fj(x) ≥ fj (1− δj) ∀j ∈ {1, . . . ,m},
m∑
j=1
δj = k, δj ∈ {0, 1} ∀j ∈ {1, . . . ,m}
4) Restricciones condicionales
Sean S ⊆ IRn, f, g : S → IR y x ∈ S.
f(x) < 0 ⇒ g(x) ≥ 0
ppp
f(x) ≥ 0 o g(x) ≥ 0
Io/Programaci?n Entera/Prob_clasicos.pdf
PROBLEMAS CLÁSICOS DE PROGRAMACIÓN ENTERA
1. Problema de la mochila (Knapsack Problem)
Un excursionista dispone de una cantidad ilimitada de objetos de n tipos para
introducir en su mochila. Cada objeto de tipo j ∈ {1, . . . , n} tiene una utilidad cj
y un peso aj. Se desea maximizar la suma de las utilidades de los objetos elegidos
sabiendo que el peso máximo que soporta la mochila es b.
2. Problema del transporte (Transportation Problem)
Dados m oŕıgenes y n destinos, para cada par de ı́ndices i ∈ {1, . . . , m}, j ∈ {1, . . . , n}
se denota por cij al coste de transportar una unidad de un determinado producto
indivisible desde el origen i hasta el destino j.
Sabiendo que en cada origen i ∈ {1, . . . ,m} se dispone de ai unidades del producto y
que la demanda del mismo en cada destino j ∈ {1, . . . , n} es de bj unidades, se trata
de satisfacer dichas demandas minimizando el coste total del transporte.
3. Problema de asignación lineal pura (Pure Linear Assignment Problem)
Se dispone de n máquinas y de n tareas a realizar, de forma que cada máquina
ha de efectuar exactamente una tarea. Sabiendo que, para cada par de ı́ndices
i, j ∈ {1, . . . , n}, cij es el coste de asignar a la máquina i la tarea j, se desea obtener
una asignación de las máquinas a las tareas (o viceversa) que minimice el coste total.
4. Problema de asignación lineal generalizada (Generalized Linear Assignment Problem)
Dadas m máquinas y n tareas a realizar, para cada par de ı́ndices i ∈ {1, . . . ,m},
j ∈ {1, . . . , n} se denota por cij al coste de asignar a la máquina i la tarea j, y por aij
al tiempo que la máquina i requiere para efectuar la tarea j.
Sabiendo que, para cada i ∈ {1, . . . , m}, bi es el tiempo máximo que la máquina i
puede estar en funcionamiento, se trata de asignar cada tarea a una única máquina de
forma que se minimice el coste total.
5. Problema de asignación cuadrática (Quadratic Assignment Problem)
El fabricante de un determinado producto ha seleccionado n lugares para construir
una planta industrial en cada uno de ellos. Para cada par de ı́ndices i, i′ ∈ {1, . . . , n},
se denota por ai,i′ al número de unidades del producto que deben transportarse desde
la planta i hasta la planta i′ y, para cada par de ı́ndices j, j′ ∈ {1, . . . , n}, se denota
por cj,j′ al coste de transportar una unidad del producto desde el lugar j hasta el
lugar j′. Se desea determinar en qué lugar ha de construirse cada planta industrial
para minimizar el coste total del transporte.
6. Problema de cubrimiento (Set-Covering Problem) y problema de particionamiento
(Set-Partitioning Problem)
Sean I = {1, . . . , m} un conjunto de elementos, P = {P1, . . . , Pn} una familia
de subconjuntos de I, y cj el coste de seleccionar el subconjunto Pj, para cada
j ∈ {1, . . . , n}.
Dado F ⊆ {1, . . . , n}, se dice que {Pj}j∈F es un cubrimiento de I si
⋃
j∈F
Pj = I. Si,
además, Pj ∩ Pj′ = ∅ ∀j, j′ ∈ F con j 6= j′, se dice que {Pj}j∈F es una partición
de I.
Los problemas de cubrimiento y particionamiento consisten, respectivamente, en
obtener un cubrimiento y una partición de mı́nimo coste.
7. Problema del viajante (Traveling Salesman Problem)
Dadas n ciudades, para cada par de ı́ndices distintos i, j ∈ {1, . . . , n} se denota por cij
al tiempo requerido para ir directamente desde la ciudad i hasta la ciudad j.
Partiendo de la ciudad 1, un agente comercial debe visitar exactamente una vez las
ciudades 2, . . . , n y regresar a la ciudad 1. Se desea determinar una ruta que minimice
la duración total del viaje.
Si cij = cji ∀i, j ∈ {1, . . . , n} tales que i 6= j, se dice que el problema es simétrico;
en caso contrario, el problema es asimétrico.
Io/Programaci?n Lineal/Alg_dual_simplex.pdf
ALGORITMO DUAL DEL SÍMPLEX (Problema de minimización)
Paso 1. Determinar una base inicial B y su matriz no básica asociada N de forma que
ctB B
−1aNj − cNj ≤ 0 ∀j ∈ {1, . . . , n−m}.
Paso 2. Calcular xB = B
−1b y poner xN = 0, yNj = B
−1aNj y zNj − cNj = ctB yNj − cNj
∀j ∈ {1, . . . , n−m}.
Paso 3. Si xB ≥ 0, PARAR (la solución es óptima).
Paso 4. Si ∃l ∈ {1, . . . , m} tal que xBl < 0 y yl,Nj ≥ 0 ∀j ∈ {1, . . . , n −m}, PARAR (el
problema es infactible). En otro caso, calcular
l = argmı́n {xBi | i ∈ {1, . . . , m} con xBi < 0} y
k = argmı́n
{
zNj − cNj
yl,Nj
| j ∈ {1, . . . , n−m} con yl,Nj < 0
}
.
Paso 5. Intercambiar las columnas aBl y aNk de las matrices B y N . Ir al Paso 2.
Alternativa al Paso 4
Paso 4’. Calcular l = argmı́n {xBi | i ∈ {1, . . . , m} con xBi < 0}. Si yl,Nj ≥ 0
∀j ∈ {1, . . . , n −m}, PARAR (el problema es infactible). En otro caso, calcular
k = argmı́n
{
zNj − cNj
yl,Nj
| j ∈ {1, . . . , n−m} con yl,Nj < 0
}
.
ALGORITMO DUAL DEL SÍMPLEX (Problema de maximización)
Paso 1. Determinar una base inicial B y su matriz no básica asociada N de forma que
ctB B
−1aNj − cNj ≥ 0 ∀j ∈ {1, . . . , n−m}.
Paso 2. Calcular xB = B
−1b y poner xN = 0, yNj = B
−1aNj y zNj − cNj = ctB yNj − cNj
∀j ∈ {1, . . . , n−m}.
Paso 3. Si xB ≥ 0, PARAR (la solución es óptima).
Paso 4. Si ∃l ∈ {1, . . . , m} tal que xBl < 0 y yl,Nj ≥ 0 ∀j ∈ {1, . . . , n −m}, PARAR (el
problema es infactible). En otro caso, calcular
l = argmı́n {xBi | i ∈ {1, . . . , m} con xBi < 0} y
k = argmáx
{
zNj − cNj
yl,Nj
| j ∈ {1, . . . , n−m} con yl,Nj < 0
}
.
Paso 5. Intercambiar las columnas aBl y aNk de las matrices B y N . Ir al Paso 2.
Alternativa al Paso 4
Paso 4’. Calcular l = argmı́n {xBi | i ∈ {1, . . . , m} con xBi < 0}. Si yl,Nj ≥ 0
∀j ∈ {1, . . . , n −m}, PARAR (el problema es infactible). En otro caso, calcular
k = argmáx
{
zNj − cNj
yl,Nj
| j ∈ {1, . . . , n−m} con yl,Nj < 0
}
.
Io/Programaci?n Lineal/Alg_simplex.pdf
ALGORITMO (PRIMAL) DEL SÍMPLEX (Problema de minimización)
Paso 1. Determinar una base inicial B tal que B−1b ≥ 0, y su matriz no básica asociada N .
Paso 2. Poner xB = B
−1b y xN = 0. Calcular yNj = B
−1aNj y zNj − cNj = ctB yNj − cNj
∀j ∈ {1, . . . , n−m}.
Paso 3. Si zNj − cNj ≤ 0 ∀j ∈ {1, . . . , n − m}, PARAR (la solución es óptima: Si
∃ k ∈ {1, . . . , n − m} tal que zNk − cNk = 0 y xBl > 0 si yNk 6≤ 0, donde
l = argmı́n
{
xBi
yi,Nk
| i ∈ {1, . . . , m} con yi,Nk > 0
}
, existen infinitas soluciones
óptimas; si zNj − cNj < 0 ∀j ∈ {1, . . . , n−m}, la solución es única).
Paso 4. Si ∃ k ∈ {1, . . . , n − m} tal que zNk − cNk > 0 y yNk ≤ 0, PARAR (el valor
óptimo de la función objetivo no está acotado: decrece a lo largo del rayo

xB
xN

 + λ


−yNk
ek

 ∀λ ≥ 0). En otro caso, calcular
k = argmáx {zNj − cNj | j ∈ {1, . . . , n−m} con zNj − cNj > 0} y
l = argmı́n
{
xBi
yi,Nk
| i ∈ {1, . . . , m} con yi,Nk > 0
}
.
Paso 5. Intercambiar las columnas aBl y aNk de las matrices B y N . Ir al Paso 2.
Alternativa al Paso 4
Paso 4’. Calcular k = argmáx {zNj − cNj | j ∈ {1, . . . , n − m} con zNj − cNj > 0}. Si
yNk ≤ 0, PARAR (el valor óptimo de la función objetivo no está acotado: decrece
a lo largo del rayo


xB
xN

 + λ


−yNk
ek

 ∀λ ≥ 0). En otro caso, calcular
l = argmı́n
{
xBi
yi,Nk
| i ∈ {1, . . . ,m} con yi,Nk > 0
}
.
ALGORITMO (PRIMAL) DEL SÍMPLEX (Problema de maximización)
Paso 1. Determinar una base inicial B tal que B−1b ≥ 0, y su matriz no básica asociada N .
Paso 2. Poner xB = B
−1b y xN = 0. Calcular yNj = B
−1aNj y zNj − cNj = ctB yNj − cNj
∀j ∈ {1, . . . , n−m}.
Paso 3. Si zNj − cNj ≥ 0 ∀j ∈ {1, . . . , n − m}, PARAR (la solución es óptima: Si
∃ k ∈ {1, . . . , n − m} tal que zNk − cNk = 0 y xBl > 0 si yNk 6≤ 0, donde
l = argmı́n
{
xBi
yi,Nk
| i ∈ {1, . . . , m} con yi,Nk > 0
}
, existen infinitas soluciones
óptimas; si zNj − cNj > 0 ∀j ∈ {1, . . . , n−m}, la solución es única).
Paso 4. Si ∃ k ∈ {1, . . . , n − m} tal que zNk − cNk < 0 y yNk ≤ 0, PARAR (el valor
óptimo de la función objetivo no está acotado: crece a lo largo del rayo

xB
xN

 + λ


−yNk
ek

 ∀λ ≥ 0). En otro caso, calcular
k = argmı́n {zNj − cNj | j ∈ {1, . . . , n−m} con zNj − cNj < 0} y
l = argmı́n
{
xBi
yi,Nk
| i ∈ {1, . . . , m} con yi,Nk > 0
}
.
Paso 5. Intercambiar las columnas aBl y aNk de las matrices B y N . Ir al Paso 2.
Alternativa al Paso 4
Paso 4’. Calcular k = argmı́n {zNj − cNj | j ∈ {1, . . . , n − m} con zNj − cNj < 0}. Si
yNk ≤ 0, PARAR (el valor óptimo de la función objetivo no está acotado: crece
a lo largo del rayo


xB
xN

 + λ


−yNk
ek

 ∀λ ≥ 0). En otro caso, calcular
l = argmı́n
{
xBi
yi,Nk
| i ∈ {1, . . . ,m} con yi,Nk > 0
}
.
Io/Programaci?n Lineal/Ciclo_simplex.pdf
CICLO EN EL ALGORITMO DEL SÍMPLEX
El siguiente problema de programación lineal fue proporcionado por Beale para demostrar
que el algoritmo del śımplex puede realizar infinitas iteraciones:
Minimizar z = −3
4
x4 + 20x5 − 12x6 + 6x7
sujeto a: x1 +
1
4
x4 − 8x5 − x6 + 9x7 = 0
x2 +
1
2
x4 − 12x5 − 12x6 + 3x7 = 0
x3 + x6 = 1
x1, . . . , x7 ≥ 0
Criterio de entrada en la base:
Entra una variable xNk tal que k = argmáx{zNj−cNj | j ∈ {1, . . . , n−m} con zNj−cNj > 0}.
Criterio de salida de la base:
Sale la variable xBl∗ tal que l
∗ = mı́n
{
l | xBl
yl,Nk
= mı́n
{
xBi
yi,Nk
| i ∈ {1, . . . ,m} con yi,Nk > 0
}}
.
Tabla 1
x1 x2 x3 x4 x5 x6 x7
0 0 0 3
4
−20 1
2
−6 0
x1 1 0 0
1
4
−8 −1 9 0
x2 0 1 0
1
2
−12 −1
2
3 0
x3 0 0 1 0 0 1 0 1
→
Tabla 2
x1 x2 x3 x4 x5 x6 x7
−3 0 0 0 4 7
2
−33 0
x4 4 0 0 1 −32 −4 36 0
x2 −2 1 0 0 4 32 −15 0
x3 0 0 1 0 0 1 0 1
→
↑ ↑
Tabla 3
x1 x2 x3 x4 x5 x6 x7
−1 −1 0 0 0 2 −18 0
x4 −12 8 0 1 0 8 −84 0
x5 −12
1
4
0 0 1 3
8
−15
4
0
x3 0 0 1 0 0 1 0 1
→
Tabla 4
x1 x2 x3 x4 x5 x6 x7
2 −3 0 −1
4
0 0 3 0
x6 −32 1 0
1
8
0 1 −21
2
0
x5
1
16
−1
8
0 − 3
64
1 0 3
16
0
x3
3
2
−1 1 −1
8
0 0 21
2
1
→
↑ ↑
1
Tabla 5
x1 x2 x3 x4 x5 x6 x7
1 −1 0 1
2
−16 0 0 0
x6 2 −6 0 −52 56 1 0 0
x7
1
3
−2
3
0 −1
4
16
3
0 1 0
x3 −2 6 1 52 −56 0 0 1
→
Tabla 6
x1 x2 x3 x4 x5 x6 x7
0 2 0 7
4
−44 −1
2
0 0
x1 1 −3 0 −54 28
1
2
0 0
x7 0
1
3
0 1
6
−4 −1
6
1 0
x3 0 0 1 0 0 1 0 1
→
↑ ↑
Tabla 7
x1 x2 x3 x4 x5 x6 x7
0 0 0 3
4
−20 1
2
−6 0
x1 1 0 0
1
4
−8 −1 9 0
x2 0 1 0
1
2
−12 −1
2
3 0
x3 0 0 1 0 0 1 0 1
La tabla 7 es igual que la tabla 1, luego el algoritmo del śımplex ha entrado en un ciclo.
2
REGLA LEXICOGRÁFICA
Tabla 1
x1 x2 x3 x4 x5 x6 x7
0 0 0 3
4
−20 1
2
−6 0
x1 1 0 0
1
4
−8 −1 9 0
x2 0 1 0
1
2
−12 −1
2
3 0
x3 0 0 1 0 0 1 0 1
→
Tabla 2
x1 x2 x3 x4 x5 x6 x7
0 −3
2
0 0 −2 5
4
−21
2
0
x1 1 −12 0 0 −2 −
3
4
15
2
0
x4 0 2 0 1 −24 −1 6 0
x3 0 0 1 0 0 1 0 1 →
↑ ↑
Tabla 3
x1 x2 x3 x4 x5 x6 x7
0 −3
2
−5
4
0 −2 0 −21
2
−5
4
x1 1 −12
3
4
0 −2 0 15
2
3
4
x4 0 2 1 1 −24 0 6 1
x6 0 0 1 0 0 1 0 1
La única solución óptima es x∗ = (3
4
0 0 1 0 1 0)t, y el valor óptimo de la función
objetivo es z∗ = −5
4
.
3
REGLA DE BLAND
Se considera el siguiente orden para las variables: x1, . . . , x7
Las tablas 1, 2 y 3 no vaŕıan.
Tabla 4
x1 x2 x3 x4 x5 x6 x7
2 −3 0 −1
4
0 0 3 0
x6 −32 1 0
1
8
0 1 −21
2
0
x5
1
16
−1
8
0 − 3
64
1 0 3
16
0
x3
3
2
−1 1 −1
8
0 0 21
2
1
→
Tabla 5
x1 x2 x3 x4 x5 x6 x7
0 1 0 5
4
−32 0 −3 0
x6 0 −2 0 −1 24 1 −6 0
x1 1 −2 0 −34 16 0 3 0
x3 0 2 1 1 −24 0 6 1 →
↑ ↑
Tabla 6
x1 x2 x3 x4 x5 x6 x7
0 0 −1
2
3
4
−20 0 −6 −1
2
x6 0 0 1 0 0 1 0 1
x1 1 0 1
1
4
−8 0 9 1
x2 0 1
1
2
1
2
−12 0 3 1
2
→
Tabla 7
x1 x2 x3 x4 x5 x6 x7
0 −3
2
−5
4
0 −2 0 −21
2
−5
4
x6 0 0 1 0 0 1 0 1
x1 1 −12
3
4
0 −2 0 15
2
3
4
x4 0 2 1 1 −24 0 6 1
↑
La única solución óptima es x∗ = (3
4
0 0 1 0 1 0)t, y el valor óptimo de la función
objetivo es z∗ = −5
4
.
4
Io/Programaci?n Lineal/Hoja1.pdf
PROBLEMAS DE INVESTIGACIÓN OPERATIVA HOJA 1
1. Una refineŕıa de petróleo va a producir un nuevo tipo de gasolina mezclando cuatro
tipos de gasolina que están compuestos por tres aditivos A,B,C. La siguiente tabla
contiene el porcentaje de dichos aditivos en cada tipo de gasolina y el precio unitario
de cada tipo de gasolina:
Tipo de
gasolina
Porcentaje de A Porcentaje de B Porcentaje de C Precio
1 80 10 10 43
2 30 30 40 31
3 70 10 20 47
4 40 50 10 37
Debido a las exigencias del mercado, la nueva gasolina deberá estar compuesta por al
menos un 60% del aditivo A y a lo sumo un 30% del aditivo C. Determinar la mezcla
que producirá una gasolina de precio mı́nimo.
2. Una compañ́ıa textil posee tres tipos de máquinas procesadoras de tejidos. En la
siguiente tabla se recoge el número de máquinas de cada tipo del que se dispone, el
número de piezas que procesa una máquina en una hora, el porcentaje de dichas piezas
que son procesadas correctamente y el coste que supone para la compañ́ıa mantener
en funcionamiento una máquina durante una hora (expresado en una cierta unidad
monetaria):
Tipo de máquina
No de máquinas No de piezas Porcentaje Coste
1 8 20 95 2.00
2 10 15 80 1.75
3 20 10 100 1.50
Sabiendo que cada d́ıa se solicitan 3500 piezas de tejido y que las jornadas laborales
constan de ocho horas, determinar cuántas máquinas de cada tipo han de utilizarse
para minimizar los gastos de la compañ́ıa. ¿Cuántas deberán utilizarse si cada pieza
procesada incorrectamente supone para la compañ́ıa un coste de una unidad monetaria?
3. El propietario de un supermercado adquiere el aceite de oliva directamente del
fabricante el primer d́ıa de cada mes. En la siguiente tabla se indica el precio de
compra de cada litro de aceite y el precio de venta en el supermercado durante los
cuatro próximos meses (expresados en euros), aśı como la demanda de este producto
(expresada en litros):
Mes Precio de compra Precio de venta Demanda
1 1.7 2.3 400
2 1.5 2.4 300
3 1.8 2.5 300
4 1.4 2.6 800
El abastecimiento del supermercado tiene lugar el primer d́ıa de cada mes, y las
existencias de aceite han de coincidir con la cantidad que va a ser demandada
durante ese mes. Por este motivo, si la cantidad de aceite que posee el propietario
del supermercado es superior a la cantidad que va a ser demandada, deberá llevar el
resto del aceite a un almacén.
Suponiendo que inicialmente el almacén está vaćıo, que su capacidad es de 500 litros de
aceite y que al finalizar el cuarto mes ha de haber almacenados 100 litros, determinar
cuánto aceite deberá adquirir el propietario del supermercado durante los próximos
cuatro meses para maximizar sus beneficios netos. ¿Cuánto aceite habrá de adquirir
si el coste mensual de almacenamiento de cada litro de aceite es de 0.05 euros?
4. Una empresa produce cinco pesticidas A, B, C, D, E a partir de cuatro componentes
básicas I, II, III, IV que intervienen según unas proporciones pA,I , pA,II , . . . , pE,IV .
El beneficio que obtiene la empresa con cada kilogramo de pesticida producido es de
bA, bB, bC , bD, bE unidades monetarias.
Las autoridades regionales no permiten que se utilice en la fabricación de los pesticidas
más de cI , cII , cIII , cIV kilogramos diarios de las respectivas componentes. Las autori-
dades locales, conscientes del problema ecológico subyacente, han decidido premiar
a la empresa con aI , aII , aIII , aIV unidades monetarias por cada kilogramo de estas
componentes que no se utilice de los ĺımites impuestos por las autoridades regionales.
Modelizar el problema a resolver para que la empresa consiga
maximizar sus beneficios.
5. Una empresa construye tres tipos de muebles A,B, C de los que debe producir al menos
nA, nB, nC unidades cada mes. El número de empleados que se precisa mensualmente
para fabricar un mueble de tipo A,B, C es hA, hB, hC , y el número total de empleados
de la empresa es H. Si durante un mes hay empleados que no son requeridos para el
proceso de producción, éstos son enviados a trabajar a una fábrica escasa de personal,
la cual gratifica a la empresa con M unidades monetarias por cada empleado enviado.
Cada mueble fabricado de los tipos A,B, C supone para la empresa un coste de
dA, dB, dC unidades monetarias, y el presupuesto mensual del que dispone la empresa
para este tipo de gastos es de D unidades monetarias. Si algún mes no ha sido
necesario emplear la totalidad del presupuesto, la empresa invierte la cantidad no
gastada y recibe un interés del R%.
El beneficio que obtiene la empresa por cada mueble fabricado de los tipos A,B, C es
de bA, bB, bC unidades monetarias (se supone que se venden todos los muebles).
La producción ha de realizarse de forma que el número de muebles de tipo A no sea
mayor que el triple del número de muebles de tipo B ni mayor que el doble del número
de muebles de tipos B y C considerados conjuntamente.
Modelizar el problema a resolver para que la empresa consiga maximizar sus beneficios
netos.
Io/Programaci?n Lineal/Hoja2.pdf
PROBLEMAS DE INVESTIGACIÓN OPERATIVA HOJA 2
1. Resolver gráficamente los siguientes problemas de programación lineal:
(a) Max z = −2x1 + x2
s.a: −x1 + 2x2 ≤ 4
−7x1 + 2x2 ≤ 15
x1 + x2 ≤ 3
x2 ≥ 0
(b) Min z = 3x1 + x2
s.a: −x1 + 2x2 ≤ 4
7x1 + 2x2 ≥ 15
x1, x2 ≥ 0
(c) Max z = x1 + x2
s.a: −2x1 + x2 ≤ 1
x1 + x2 ≤ 3
x2 ≤ 2
x1, x2 ≥ 0
(d) Max z = 3x1 + 2x2
s.a: 2x1 − 3x2 ≤ 6
−4x1 + 5x2 ≤ 15
x1, x2 ≥ 0
(e) Min z = 3x1 + 4x2
s.a: 2x1 + 3x2 ≤ 6
−3x1 + 5x2 ≥ 15
x1, x2 ≥ 0
2. Resolver gráficamente los siguientes problemas de programación no lineal transformándolos
previamente en uno o varios problemas de programación lineal:
(a) Min z = máx {2x1 − x2,−3x1 + x2}
s.a: 4x1 + x2 ≤ 5
x1, x2 ≥ 0
(b) Max z = 2 |x1|+ x2
s.a: 3x1 + 2x2 ≤ 6
−3x1 + 7x2 ≤ 21
x2 ≥ 0
(c) Max z = |x1| − |x2|
s.a: −1 ≤ x1 + x2 ≤ 1
−1 ≤ −x1 + x2 ≤ 1
3. Demostrar que el conjunto S = {(x1, . . . , xn) ∈ IRn | x21 + . . . + x2n < 1} es convexo.
Io/Programaci?n Lineal/Hoja3.pdf
PROBLEMAS DE INVESTIGACIÓN OPERATIVA HOJA 3
1. Resolver los siguientes problemas de programación lineal aplicando el algoritmo del śımplex:
(a) Max z = 12x1 + 8x2
s.a: 5x1 + 2x2 ≤ 150
2x1 + 3x2 ≤ 100
4x1 + 2x2 ≤ 80
x1, x2 ≥ 0
(b) Max z = 3x1 + 2x2
s.a: 6x1 + 4x2 ≤ 24
10x1 + 3x2 ≤ 30
x1, x2 ≥ 0
(c) Min z = x1
s.a: x1 − x2 ≤ 2
2x1 + 2x2 ≥ 1
x1, x2 ≥ 0
(d) Min z = −3x1 − 2x2 − x3
s.a: 2x1 + 5x2 + x3 ≤ 12
6x1 + 8x2 ≤ 22
x2, x3 ≥ 0
(e) Max z = 5x1 + 3x2
s.a: 4x1 + 2x2 ≤ 12
4x1 + x2 ≤ 10
x1 + x2 ≤ 4
x1, x2 ≥ 0
(f) Min z = −2x1 − 3x2
s.a: x1 + x2 ≥ 3
−x1 + 2x2 ≥ −4
x1, x2 ≥ 0
(g) Min z = −x1 + 2x2 − 3x3
s.a: x1 + x2 + x3 = 6
−x1 + x2 + 2x3 = 4
2x2 + 3x3 = 10
x3 ≤ 2
x1, x2, x3 ≥ 0
(h) Max z = 3x1 + 2x2 + x3
s.a: 2x1 + 5x2 + x3 ≤ 12
6x1 + 8x2 ≤ 22
x1 + x2 ≥ 4
x1, x2, x3 ≥ 0
2. Responder razonadamente a las siguientes preguntas:
(a) Sea N la matriz no básica asociada a una solución básica óptima. ¿Pueden existir dos
ı́ndices j, j′ ∈ {1, . . . , n−m} tales que zNj − cNj > 0 y zNj′ − cNj′ < 0?
(b) ¿Una variable que ha salido de la base en una iteración del algoritmo del śımplex puede
volver a entrar en la siguiente iteración?
(c) ¿Una solución óptima de un problema con m restricciones puede tener más de m
componentes estrictamente positivas?
Io/Programaci?n Lineal/Hoja4.pdf
PROBLEMAS DE INVESTIGACIÓN OPERATIVA HOJA 4
1. Para cada uno de los siguientes problemas de programación lineal, se pide:
• Plantear su problema dual.
• En caso de que exista, identificar la solución óptima del problema dual en la tabla
óptima del problema primal y comprobar que se satisfacen las condiciones establecidas
en el Teorema de la holgura complementaria.
• Determinar cuál de las situaciones establecidas en el Teorema fundamental de la dualidad
se presenta.
• Formularlo de distintas formas (expresándolo como un problema de minimización en
lugar de maximización o viceversa, introduciendo variables de holgura, cambiando de
sentido las desigualdades, . . . ), plantear sus problemas duales asociados y comprobar
que todos ellos son equivalentes.
(a) Max z = −2x1 + x2
s.a: −x1 + 2x2 ≤ 4
−7x1 + 2x2 ≤ 15
x1 + x2 ≤ 3
x2 ≥ 0
(b) Min z = 3x1 + x2
s.a: −x1 + 2x2 ≤ 4
7x1 + 2x2 ≥ 15
x1, x2 ≥ 0
(c) Max z = x1 + x2
s.a: −2x1 + x2 ≤ 1
x1 + x2 ≤ 3
x2 ≤ 2
x1, x2 ≥ 0
(d) Max z = 3x1 + 2x2
s.a: 2x1 − 3x2 ≤ 6
−4x1 + 5x2 ≤ 15
x1, x2 ≥ 0
(e) Min z = 3x1 + 4x2
s.a: 2x1 + 3x2 ≤ 6
−3x1 + 5x2 ≥ 15
x1, x2 ≥ 0
2. Resolver el siguiente problema de programación lineal aplicando el algoritmo dual del śımplex:
Minimizar z = 3x1 + 4x2 + 5x3
sujeto a: x1 + 2x2 + 3x3 ≥ 5
2x1 + 2x2 + 3x3 ≥ 6
x1, x2, x3 ≥ 0
3. Resolver el siguiente problema de programación lineal aplicando el algoritmo dual del śımplex
y comprobar mediante algún resultado de dualidad que, en efecto, la solución que se obtiene
es óptima.
Maximizar z = 2x1 − 3x2
sujeto a: x1 + x2 ≥ 3
3x1 + x2 ≤ 6
x1, x2 ≥ 0
4. Demostrar que si la matriz de restricciones de un problema de minimización escrito en forma
estándar es simétrica y el vector de costes coincide con el vector del lado derecho, entonces
toda solución factible del problema es óptima.
5. Resolver los siguientes problemas de programación lineal mediante los algoritmos primal y
dual del śımplex:
(a) Max z = 2x1 + x2 + 4x3
s.a: 2x1 − x2 + x3 = 1
x1 − 3x3 ≥ −4
x1, x2, x3 ≥ 0
(b) Min z = −x1 − 34x2 + 4x3
s.a: x2 + 4x3 ≤ −2
2x1 + x2 − 4x3 = 10
x1, x2 ≥ 0
Io/Programaci?n Lineal/Hoja5.pdf
PROBLEMAS DE INVESTIGACIÓN OPERATIVA HOJA 5
1. Resolver el siguiente problema de programación lineal y los problemas que resultan al
realizar en él las modificaciones que se indican a continuación. Determinar el rango de
variación de los coeficientes c2 y b1 de forma que la base óptima del problema inicial
continúe siéndolo.
Maximizar z = −5x1 + 5x2 + 13x3
sujeto a: −x1 + x2 + 3x3 ≤ 20
12x1 + 4x2 + 10x3 ≤ 90
x1, x2, x3 ≥ 0
(a) Reemplazar el coeficiente c3 por c
′
3 = 8.
(b) Reemplazar el vector c por c′ = (−2 6 − 1)t.
(c) Reemplazar el vector b por b′ = (10 100)t.
(d) Reemplazar el vector b por b′ = (−3 4)t.
(e) Introducir una nueva variable x4 ∈ IR con c4 = 10 y a4 = (−2 1)t.
(f) Introducir la restricción 3x1 − x2 + 8x3 ≥ −30.
(g) Introducir la restricción 2x1 + 3x2 − 4x3 = −10.
2. Resolver el siguiente problema de programación lineal y los problemas que resultan al
realizar en él las modificaciones que se indican a continuación.
Maximizar z = 2x1 − x2 − 4x4
sujeto a: −x1 + x2 + 2x3 − 4x4 = 52
x1 + x3 − x4 = 3
x1, . . . , x4 ≥ 0
(a) Reemplazar el vector c por c′ = (9 0 6 − 1)t.
(b) Reemplazar el vector c por c′ = (1 − 1 − 4 4)t.
(c) Reemplazar el vector b por b′ = (1 − 2)t.
(d) Introducir una nueva variable x5 ≥ 0 con c5 = 1 y a5 = (12 1)
t.
(e) Introducir la restricción 4x1 + x3 + 7x4 ≤ 6.
(f) Introducir la restricción 6x1 − 2x2 − x3 + 6x4 = 8.
Io/Programaci?n Lineal/Pivotaje_simplex.pdf
PIVOTAJE SOBRE yl,Nk
− Dividir la fila l entre yl,Nk .
− Para cada i ∈ {1, . . . ,m} \ {l}, restarle a la fila i la nueva fila l multiplicada por yi,Nk .
− Restarle a la fila 0 la nueva fila l multiplicada por zNk − cNk .
x1 . . . xBl . . . xm xm+1 . . . xNk . . . xn
0 . . . −(zNk−cNk )
1
yl,Nk
. . . 0 (zm+1−cm+1)−(zNk−cNk)
yl,m+1
yl,Nk
. . . 0 . . . (zn−cn)−(zNk−cNk)
yl,n
yl,Nk
z−(zNk−cNk )
xBl
yl,Nk
x1 1 . . . −
y1,Nk
yl,Nk
. . . 0 y1,m+1−y1,Nk
yl,m+1
yl,Nk
. . . 0 . . . y1,n−y1,Nk
yl,n
yl,Nk
x1−y1,Nk
xBl
yl,Nk
...
...
...
...
...
...
...
...
xNk 0 . . .
1
yl,Nk
. . . 0
yl,m+1
yl,Nk
. . . 1 . . .
yl,n
yl,Nk
xBl
yl,Nk
...
...
...
...
...
...
...
...
xm 0 . . . −
ym,Nk
yl,Nk
. . . 1 ym,m+1−ym,Nk
yl,m+1
yl,Nk
. . . 0 . . . ym,n−ym,Nk
yl,n
yl,Nk
xm−ym,Nk
xBl
yl,Nk
Io/Programaci?n Lineal/Reglas_lexic_Bland.pdf
REGLA LEXICOGRÁFICA
Sea B0 = (aB01 . . .aB0m) = Im.
Criterio de entrada en la base: (El mismo que en el algoritmo del śımplex.)
Problema de minimización
Entra una variable xNk tal que k=argmáx{zNj−cNj | j∈{1, . . . , n−m} con zNj−cNj>0}.
Problema de maximización
Entra una variable xNk tal que k=argmı́n{zNj−cNj | j∈{1, . . . , n−m} con zNj−cNj<0}.
Criterio de salida de la base:
Sale la variable xBl∗ tal que Lj∗ = {l∗}, donde j∗ = mı́n{j ∈ {0, . . . ,m} | |Lj| = 1},
L0=
{
l | xBl
yl,Nk
=mı́n
{
xBi
yi,Nk
| i∈{1, . . . ,m} con yi,Nk >0
}}
y Lj=
{
l |
y
l,B0
j
yl,Nk
=mı́n
{ y
i,B0
j
yi,Nk
| i∈Lj−1
}}
∀j ∈ {1, . . . ,m}.
REGLA DE BLAND
Se establece un orden para las variables (por ejemplo, x1, . . . , xn).
Criterio de entrada en la base:
Problema de minimización
Entra la primera variable xNk del conjunto {xNj | j ∈ {1, . . . , n−m} con zNj−cNj > 0}
según el orden establecido.
Problema de maximización
Entra la primera variable xNk del conjunto {xNj | j ∈ {1, . . . , n−m} con zNj−cNj < 0}
según el orden establecido.
Criterio de salida de la base:
Sale la primera variable xBl∗ del conjunto
{
xBl |
xBl
yl,Nk
=mı́n
{
xBi
yi,Nk
| i∈{1, . . . ,m} con yi,Nk >0
}}
según el orden establecido.
Io/Programaci?n Lineal/Tabla_simplex.pdf
MÉTODO DEL SÍMPLEX EN FORMATO TABLA
Sin pérdida de generalidad, supóngase que B = (a1 . . . am).
x1 . . . xBl . . . xm xm+1 . . . xNk . . . xn
(Fila 0) 0 . . . 0 . . . 0 zm+1 − cm+1 . . . zNk − cNk . . . zn − cn z
(Fila 1) x1 1 . . . 0 . . . 0 y1,m+1 . . . y1,Nk . . . y1,n x1
...
...
...
...
...
...
...
...
...
(Fila l) xBl 0 . . . 1 . . . 0 yl,m+1 . . . yl,Nk . . . yl,n xBl
...
...
...
...
...
...
...
...
...
(Fila m) xm 0 . . . 0 . . . 1 ym,m+1 . . . ym,Nk . . . ym,n xm
↑
→
Actualización de la base: B′ = (a1 . . . al−1 aNk al+1 . . . am)
x1 . . . xBl . . . xm xm+1 . . . xNk . . . xn
0 . . . z′Bl − cBl . . . 0 z
′
m+1 − cm+1 . . . 0 . . . z′n − cn z′
x1 1 . . . y
′
1,Bl
. . . 0 y′1,m+1 . . . 0 . . . y
′
1,n x
′
1
...
...
...
...
...
...
...
...
xNk 0 . . . y
′
l,Bl
. . . 0 y′l,m+1 . . . 1 . . . y
′
l,n x
′
Nk
...
...
...
...
...
...
...
...
xm 0 . . . y
′
m,Bl
. . . 1 y′m,m+1 . . . 0 . . . y
′
m,n x
′
m
Io/Programaci?n Lineal/Tema2.pdf
Tema 2
Programación lineal
2.1. Introducción
La programación lineal estudia la optimización (es decir, minimización o maximización) de una
función lineal cuyas variables deben satisfacer un conjunto de restricciones lineales de igualdad y/o
desigualdad no estricta. Aśı, un problema de programación lineal (continua) puede expresarse
de la siguiente forma:
Minimizar o Maximizar c1x1 + c2x2 + . . .+ cnxn
sujeto a: a11x1 + a12x2 + . . .+ a1nxn ∼ b1
a21x1 + a22x2 + . . .+ a2nxn ∼ b2
...
am1x1 + am2x2 + . . .+ amnxn ∼ bm
xj ∈ IR ∀j ∈ {1, . . . , n},
donde n,m ∈ IN , {cj}j∈{1,...,n}, {aij}i∈{1,...,m}, j∈{1,...,n} y {bi}i∈{1,...,m} son números reales conocidos
y, para cada restricción, “∼” puede ser “=”, “≤” o “≥”.
La función c1x1 + c2x2 + . . . + cnxn se denomina función objetivo (o función criterio), y
suele denotarse por z, y x1, x2, . . . , xn son las variables de decisión (o variables, o variables
estructurales, o niveles de actividad).
Una restricción de la forma xj ≥ 0, donde j ∈ {1, . . . , n}, se llama restricción de no
negatividad.
1
TEMA 2. PROGRAMACIÓN LINEAL 2
Un conjunto de valores reales de las variables x1, . . . , xn que satisface todas las restricciones
se denomina solución factible del problema. El conjunto de todas las soluciones factibles es la
región factible del problema. Si la región factible es vaćıa, se dice que el problema es infactible;
en otro caso, se dice que el problema es factible.
Se dice que una solución factible
 x∗1...
x∗n
 es una solución óptima del problema si para toda
solución factible
 x1...
xn
 se verifica que n∑
j=1
cjx
∗
j ≤
n∑
j=1
cjxj si el problema es de minimización, o
que
n∑
j=1
cjx
∗
j ≥
n∑
j=1
cjxj si el problema es de maximización.
Un problema de programación lineal está escrito en forma estándar si está expresado de la
siguiente forma:
Minimizar o Maximizar
n∑
j=1
cjxj
sujeto a:
n∑
j=1
aijxj = bi ∀i ∈ {1, . . . ,m}
xj ≥ 0 ∀j ∈ {1, . . . , n}
Un problema de programación lineal está escrito en forma canónica si está expresado de una
de las dos siguientes formas:
Minimizar
n∑
j=1
cjxj
sujeto a:
n∑
j=1
aijxj ≥ bi ∀i ∈ {1, . . . ,m}
xj ≥ 0 ∀j ∈ {1, . . . , n}
Maximizar
n∑
j=1
cjxj
sujeto a:
n∑
j=1
aijxj ≤ bi ∀i ∈ {1, . . . ,m}
xj ≥ 0 ∀j ∈ {1, . . . , n}
2.2. Convexidad. Puntos extremos y direcciones extremas.
Soluciones básicas
2.2.1. Convexidad. Conceptos básicos
El concepto de convexidad es de gran importancia en el estudio de problemas de programación
matemática.
TEMA 2. PROGRAMACIÓN LINEAL 3
Definición 2.1. Un conjunto S ⊆ IRn es convexo si ∀x1,x2∈S se verifica que λx1+(1−λ)x2∈S
∀λ ∈ [0, 1].
Lema 2.1. Sean S1, S2 ⊆ IRn conjuntos convexos. Entonces S1 ∩ S2 es un conjunto convexo.
Definición 2.2. Dado un conjunto S ⊆ IRn, la envoltura convexa de S es el conjunto H(S) de
todas las combinaciones lineales convexas de puntos de S, es decir,
H(S) =

k∑
j=1
λj xj | k ∈ IN, x1, . . . ,xk ∈ S, λ1, . . . , λk ≥ 0,
k∑
j=1
λj = 1
 .
Lema 2.2. Sea S ⊆ IRn. Entonces H(S) es un conjunto convexo.
Definición 2.3. Un politopo en IRn es la envoltura convexa de un número finito de puntos
x1, . . . ,xk+1 ∈ IRn, donde k ∈ IN . Si los vectores x2 − x1, . . . ,xk+1 − x1 son linealmente
independientes, la envoltura convexa de {x1, . . . ,xk+1} se denomina śımplex en IRn de vértices
x1, . . . ,xk+1.
Se observa que un śımplex en IRn tiene a lo sumo n+ 1 vértices.
Definición 2.4. Un hiperplano en IRn es un conjunto de la forma H = {x ∈ IRn | ptx = α},
donde p ∈ IRn \ {0} y α ∈ IR. Un hiperplano H define dos semiespacios cerrados
H≥ = {x ∈ IRn | ptx ≥ α} y H≤ = {x ∈ IRn | ptx ≤ α}.
Lema 2.3. Sea H un hiperplano. Entonces H, H≥ y H≤ son conjuntos convexos.
Definición 2.5. Un poliedro en IRn es la intersección de un número finito de semiespacios
cerrados en IRn.
De los Lemas 2.1 y 2.3 se deduce que todo poliedro es un conjunto convexo.
2.2.2. Puntos extremos y direcciones extremas. Teorema de representación
Definición 2.6. Sea S ⊆ IRn un conjunto convexo no vaćıo. Un punto x ∈ S es un punto extremo
de S si x = λ x1 + (1− λ)x2 implica que x = x1 = x2, donde λ ∈ (0, 1) y x1,x2 ∈ S.
TEMA 2. PROGRAMACIÓN LINEAL 4
Definición 2.7. Sea S ⊆ IRn un conjunto convexo no vaćıo. Un vector d ∈ IRn \ {0} es una
dirección de S si ∀x ∈ S se verifica que x+ λ d ∈ S ∀λ ≥ 0.
Dos direcciones d1 y d2 de S son distintas si ̸ ∃α > 0 tal que d1 = α d2.
Una dirección d de S es una dirección extrema de S si d = λ1 d1+λ2 d2 implica que ∃α > 0
con d1 = α d2, donde λ1, λ2 > 0 y d1,d2 son direcciones de S.
Sea S = {x ∈ IRn | Ax = b,x ≥ 0}, donde A es una matriz real m× n, rg(A) = m y b ∈ IRm.
Teorema 2.1 (Caracterización de puntos extremos). Un punto x ∈ IRn es un punto extremo de S
si y solo si A y x pueden expresarse de la forma A = (B N) y x =
 xB
xN
, donde B es una
matriz m×m con rg(B) = m, N es una matriz m× (n−m), xB = B−1b ≥ 0 y xN = 0.
Corolario 2.1. El máximo número de puntos extremos de S es
 n
m
.
Teorema 2.2 (Existencia de puntos extremos). Si S ̸= ∅, entonces S
tiene al menos un punto
extremo.
Lema 2.4. Un vector d ∈ IRn es una dirección de S si y solo si Ad = 0, d ≥ 0 y d ̸= 0.
Teorema 2.3 (Caracterización de direcciones extremas). Sea m < n. Un vector d ∈ IRn es
una dirección extrema de S si y solo si A y d pueden expresarse de la forma A = (B N) y
d = α d, donde B es una matriz m ×m con rg(B) = m, N es una matriz m × (n −m), α > 0,
d =
 −B−1aNk
ek
, k ∈ {1, . . . , n−m}, aNk es la k-ésima columna de la matriz N , B−1aNk ≤ 0
y ek es el k-ésimo vector unitario de dimensión n−m.
Corolario 2.2. El máximo número de direcciones extremas de S distintas dos a dos es
(n−m)
 n
m
.
TEMA 2. PROGRAMACIÓN LINEAL 5
Teorema 2.4 (Representación). Sean S ̸= ∅, x1, . . . ,xp los puntos extremos de S y d1, . . . ,dq
las direcciones extremas de S. Entonces x ∈ S si y solo si puede expresarse de la forma
x =
p∑
j=1
λjxj +
q∑
j=1
µjdj, donde λj ≥ 0 ∀j ∈ {1, . . . , p},
p∑
j=1
λj = 1 y µj ≥ 0 ∀j ∈ {1, . . . , q}.
Teorema 2.5 (Existencia de direcciones extremas). El conjunto S tiene al menos una dirección
extrema si y solo si no está acotado.
Proposición 2.1. Sean (P ) un problema de programación lineal de minimización con vector de
costes c cuya región factible es S, y d1, . . . ,dq las direcciones extremas de S. Si ∃k ∈ {1, . . . , q} tal
que ctdk < 0, entonces el valor óptimo de la función objetivo de (P ) no está acotado.
Teorema 2.6. Sean S ̸= ∅, (P ) un problema de programación lineal de minimización con vector
de costes c cuya región factible es S, y d1, . . . ,dq las direcciones extremas de S. Si c
tdj ≥ 0
∀j ∈ {1, . . . , q}, entonces existe algún punto extremo de S que es solución óptima de (P ).
Corolario 2.3. Sean S ̸= ∅, (P ) un problema de programación lineal de minimización con vector
de costes c cuya región factible es S, y d1, . . . ,dq las direcciones extremas de S. Entonces (P ) tiene
solución óptima si y solo si ctdj ≥ 0 ∀j ∈ {1, . . . , q}.
Corolario 2.4. Sea (P ) un problema de programación lineal cuya región factible es S. Si (P ) tiene
solución óptima, entonces existe algún punto extremo de S que es solución óptima de (P ).
Teorema 2.7. Sea (P ) un problema de programación lineal con vector de costes c cuya
región factible es S y que tiene solución óptima, y sean x1, . . . ,xp los puntos extremos de S,
d1, . . . ,dq las direcciones extremas de S, z
∗ el valor óptimo de la función objetivo de (P ),
P∗ = {j ∈ {1, . . . , p} | ctxj = z∗} y Q∗ = {j ∈ {1, . . . , q} | ctdj = 0}. Entonces x∗ es solución
óptima de (P ) si y solo si puede expresarse de la forma x∗ =
∑
j∈P∗
λjxj +
∑
j∈Q∗
µjdj, donde
λj ≥ 0 ∀j ∈ P∗,
∑
j∈P∗
λj = 1 y µj ≥ 0 ∀j ∈ Q∗.
2.2.3. Soluciones básicas. Teorema fundamental de la programación lineal
Considérese el conjunto S y supóngase que la matrizA se ha expresado de la formaA = (B N),
donde B es una matriz m×m con rg(B) = m y N es una matriz m× (n−m).
TEMA 2. PROGRAMACIÓN LINEAL 6
Definición 2.8. La matriz B se denomina matriz básica o, simplemente, base, y la matriz N
se denomina matriz no básica.
Un vector n-dimensional de la forma x =
 xB
xN
, donde xB = B−1b y xN = 0, se llama
solución básica.
Las componentes de xB se denominan variables básicas, y las de xN variables no básicas.
Una solución básica tal que xB ≥ 0 se llama solución básica factible.
Se dice que una solución básica factible es degenerada si xB ̸> 0.
Por el Teorema 2.1 se tiene que las soluciones básicas factibles se corresponden con los puntos
extremos de S.
Teorema 2.8 (Fundamental de la programación lineal). Sea (P ) un problema de programación
lineal cuya región factible es S. Se verifican los siguientes resultados:
1) Si (P ) es factible, entonces existe al menos una solución básica factible.
2) Si (P ) tiene solución óptima, entonces existe al menos una solución básica óptima.
2.3. Algoritmo del śımplex
Se considera el siguiente problema de programación lineal escrito en forma estándar:
Minimizar z = ctx
sujeto a: Ax = b
x ≥ 0,
(P )
donde c ∈ IRn, x ∈ IRn, A es una matriz real m× n, rg(A) = m y b ∈ IRm.
Sean B una matriz básica y N su matriz no básica asociada.
Notación. A = (B N) = (aB1 . . .aBm aN1 . . .aNn−m)
ct = (ctB c
t
N ) = (cB1 . . . cBm cN1 . . . cNn−m)
x =
 xB
xN
 =

xB1
...
xBm
xN1
...
xNn−m

Para cada j ∈ {1, . . . , n−m}, sean yNj = B−1aNj y zNj = ctB yNj .
TEMA 2. PROGRAMACIÓN LINEAL 7
Lema 2.5. Sea d = α d, donde α > 0, d =
 −yNk
ek
, k ∈ {1, . . . , n − m}, yNk ≤ 0 y ek es
el k-ésimo vector unitario de dimensión n−m. Entonces d es una dirección extrema de la región
factible de (P ). Además, ctd = 0 si y solo si zNk − cNk = 0.
Teorema 2.9. Supóngase que (P ) tiene solución óptima, y sean x∗1, . . . ,x
∗
p∗ las soluciones básicas
óptimas de (P ), J ∗= {j ∈{1, . . . , n−m} | yNj ≤ 0, zNj−cNj = 0} y d
∗
j =
−yNj
ej
 ∀j ∈J ∗, donde
ej es el j-ésimo vector unitario de dimensión n−m ∀j∈J ∗. Entonces x∗ =
p∗∑
j=1
λjx
∗
j +
∑
j∈J ∗
µjd
∗
j
es solución óptima de (P ), donde λj ≥ 0 ∀j ∈ {1, . . . , p∗},
p∗∑
j=1
λj = 1 y µj ≥ 0 ∀j ∈ J ∗.
Lema 2.6. Sean x una solución factible de (P ) y x una solución básica factible de (P ). Entonces
ctx = ctx−
n−m∑
j=1
(zNj − cNj ) xNj .
Teorema 2.10. Sea x una solución básica factible de (P ). Si zNj − cNj ≤ 0 ∀j ∈ {1, . . . , n−m},
entonces x es una solución óptima de (P ).
Teorema 2.11. Sea x una solución básica factible de (P ). Si ∃k∈{1, . . . , n−m}tal que zNk−cNk > 0
e yNk ≤ 0, entonces el valor óptimo de la función objetivo de (P ) no está acotado.
Teorema 2.12. Sea x una solución básica factible de (P ). Si ∃k∈{1, . . . , n−m} tal que zNk−cNk >0
e yNk ̸≤0, entonces el vector x′= x+
xBl
yl,Nk
d, donde l= argmı́n
{
xBi
yi,Nk
| i∈{1, . . . ,m} con yi,Nk >0
}
,
d =
 −yNk
ek
 y ek es el k-ésimo vector unitario de dimensión n − m, es una solución básica
factible de (P ) tal que ctx′ ≤ ctx. Además, ctx′ < ctx si y solo si xBl > 0.
Proposición 2.2. Sea x una solución básica factible de (P ). Si zNj−cNj ≤ 0 ∀j ∈ {1, . . . , n−m},
∃ k ∈ {1, . . . , n − m} tal que zNk − cNk = 0 y se satisface una de las dos condiciones siguientes,
entonces (P ) tiene infinitas soluciones óptimas.
1) yNk ≤ 0.
2) yNk ̸≤ 0 y xBl > 0, donde l = argmı́n
{
xBi
yi,Nk
| i ∈ {1, . . . ,m} con yi,Nk > 0
}
.
Proposición 2.3. Sea x una solución básica factible de (P ). Si zNj−cNj < 0 ∀j ∈ {1, . . . , n−m},
entonces x es la única solución óptima de (P ).
TEMA 2. PROGRAMACIÓN LINEAL 8
2.4. Inicialización del algoritmo del śımplex. Método de las dos
fases y método de las penalizaciones
Se considera el siguiente problema de programación lineal escrito en forma estándar:
Minimizar z = ctx
sujeto a: Ax = b
x ≥ 0,
(P )
donde c ∈ IRn, x ∈ IRn, A es una matriz real m × n y b ∈ IRm. Sin pérdida de generalidad, se
supone que b ≥ 0 (si inicialmente ∃i ∈ {1, . . . ,m} tal que bi < 0, se multiplica por −1 la i-ésima
restricción).
El esfuerzo computacional necesario para determinar (en caso de que exista) una submatriz B0
de A a partir de la cual comenzar a aplicar el algoritmo del śımplex para resolver el problema (P ),
puede llegar a ser muy elevado. Por ello, siempre se va a tomar B0 = Im.
Si ∀i ∈ {1, . . . ,m} ∃j(i) ∈ {1, . . . , n} tal que ai,j(i) > 0 y ai′,j(i) = 0 ∀i′ ∈ {1 . . . ,m} \ {i},
dividiendo entre ai,j(i) la i-ésima restricción para cada i ∈ {1, . . . ,m}, será posible tomar B0 = Im
y comenzar a aplicar el algoritmo del śımplex. En otro caso, para cada i ∈ {1, . . . ,m} tal que
̸∃j(i) satisfaciendo las condiciones anteriores, se sumará al término de la izquierda de la i-ésima
restricción una variable artificial (que, por definición, será no negativa) y se aplicará el método
de las dos fases o el método de las penalizaciones.
Sean xn+1, . . . , xn+p las variables artificiales que se han introducido en (P ), donde p ∈ {1, . . . ,m},
y sea (Pa) el problema resultante (nótese que (Pa) es factible).
Se observa que (x1 . . . xn)
t es una solución factible de (P ) si y solo si (x1 . . . xn xn+1 . . . xn+p)
t
es una solución factible de (Pa) tal que xn+1 = . . . = xn+p = 0.
2.4.1. Método de las dos fases
Como su nombre indica, este procedimiento consta de dos fases: en la primera se determina si el
problema (P ) es factible o infactible, y, en caso de que sea factible, en la segunda fase se continúa
aplicando el algoritmo del śımplex para resolver (P ).
TEMA 2. PROGRAMACIÓN LINEAL 9
En la Fase I se aplica el algoritmo del śımplex para resolver el siguiente problema tomando
como base inicial B0 = Im:
Minimizar zF = xn+1 + . . .+ xn+p
sujeto a: (x1 . . . xn xn+1 . . . xn+p)
t solución factible de (Pa)
(PF )
Se observa que el problema (PF ) es factible y el valor óptimo de zF está acotado, luego
(PF ) tiene solución óptima.
Considérese la tabla óptima del algoritmo del śımplex. Pueden darse las siguientes situaciones:
1) z∗F > 0.
Entonces se verifica que el problema (P ) es infactible.
2) z∗F = 0 y no hay variables artificiales básicas.
Se pasa a la Fase II, esto es, a partir de la base actual se continúa aplicando el algoritmo del
śımplex para resolver el problema (P ) (para ello, basta con eliminar de la tabla las columnas
de las variables artificiales y actualizar la fila 0).
3) z∗F = 0 y hay variables artificiales básicas.
Para cada variable artificial básica tal que sea posible realizar un pivotaje sobre un pivote
no nulo de forma que salga de la base dicha variable y entre en su lugar una variable que
no sea artificial, se realiza este pivotaje. Si ha sido posible realizar el pivotaje para todas
las variables artificiales básicas, se pasa a la Fase II. Si no, se eliminan de la tabla las filas
de las variables artificiales que continúan siendo básicas y se pasa a la Fase II (se verifica
que las restricciones del problema (P ) correspondientes a las filas que se han eliminado son
redundantes).
2.4.2. Método de las penalizaciones
Se aplica el algoritmo del śımplex considerando el Paso 4’ para resolver el siguiente problema
tomando como base inicial B0 = Im:
Minimizar zM = c1x1 + . . .+ cnxn +Mxn+1 + . . .+Mxn+p
sujeto a: (x1 . . . xn xn+1 . . . xn+p)
t solución factible de (Pa),
(PM )
donde M es una constante positiva lo suficientemente grande.
TEMA 2. PROGRAMACIÓN LINEAL 10
Se observa que el problema (PM ) es factible, luego (PM ) tiene solución óptima o el valor óptimo
de zM no está acotado.
Considérese la última tabla del algoritmo del śımplex. Pueden darse las siguientes situaciones:
1) zNj − cNj ≤ 0 ∀j ∈ {1, . . . , n−m}.
Entonces el problema (PM ) tiene solución óptima.
Si xn+1 = . . . = xn+p = 0, se verifica que el problema (P ) tiene solución óptima y (x1 . . . xn)
t
es solución óptima de (P ); en otro caso, (P ) es infactible.
2) yNk ≤ 0, donde k = argmáx{zNj − cNj | j ∈ {1, . . . , n−m} con zNj − cNj > 0}.
Entonces el valor óptimo de zM no está acotado.
Si xn+1 = . . . = xn+p = 0, se verifica que el valor óptimo de z no está acotado; en otro caso,
el problema (P ) es infactible.
2.5. Dualidad
Todo problema de programación lineal continua tiene asociado otro problema de programación
lineal continua que posee importantes propiedades y puede utilizarse para resolver el problema
original. Al problema original se le denominará problema primal, y a su problema asociado
problema dual.
La propiedad involutiva de la dualidad establece que, dados un problema primal y su
problema dual, se verifica que el problema dual del problema dual es el problema primal.
La siguiente tabla muestra las relaciones entre los problemas primal y dual:
Criterio de optimización: Minimización Criterio de optimización: Maximización
Variable ≥ 0
Variable ≤ 0
Variable ∈IR
Restricción ≤
Restricción ≥
Restricción =
Restricción ≥
Restricción ≤
Restricción =
Variable ≥ 0
Variable ≤ 0
Variable ∈IR
Coeficientes de la función objetivo Términos independientes de las restricciones
Términos independientes de las restricciones Coeficientes de la función objetivo
Matriz de restricciones: A Matriz de restricciones: At
TEMA 2. PROGRAMACIÓN LINEAL 11
Se considera el siguiente problema de programación lineal escrito en forma canónica:
Minimizar ctx
sujeto a: Ax ≥ b
x ≥ 0,
(P )
donde c ∈ IRn, x ∈ IRn, A es una matriz real m× n y b ∈ IRm.
El problema dual de (P ) es el siguiente:
Maximizar btw
sujeto a: Atw ≤ c
w ≥ 0,
(D)
donde w ∈ IRm.
Lema 2.7. Sean x y w soluciones factibles de (P ) y (D) respectivamente. Entonces
ctx ≥ wtAx ≥ btw.
Corolario 2.5. Sean x y w soluciones factibles de (P ) y (D) respectivamente. Si ctx = btw,
entonces x y w son soluciones óptimas de (P ) y (D) respectivamente.
Corolario 2.6. Si uno de los problemas (P ) o (D) tiene valor óptimo de la función objetivo no
acotado, entonces el otro problema es infactible.
Lema 2.8. Si uno de los problemas (P ) o (D) tiene solución óptima, entonces ambos tienen
solución óptima y los valores óptimos de sus funciones objetivo coinciden.
Teorema 2.13 (Fundamental de la dualidad). Dados un problema primal y su problema dual
asociado, exactamente una de las siguientes afirmaciones es cierta:
1) Ambos problemas tienen solución óptima y los valores óptimos de sus funciones objetivo
coinciden.
2) Uno de los problemas tiene valor óptimo de la función objetivo no acotado y el otro problema
es infactible.
3) Ambos problemas son infactibles.
Teorema 2.14 (Holgura complementaria). Sean x y w soluciones factibles de (P ) y (D)
respectivamente. Entonces ambas soluciones son óptimas para sus problemas respectivos si y solo
si (cj −wtaj)xj = 0 ∀j ∈ {1, . . . , n} y wi(aix− bi) = 0 ∀i ∈ {1, . . . ,m}.
TEMA 2. PROGRAMACIÓN LINEAL 12
2.6. Algoritmo dual del śımplex
Se considera el siguiente problema de programación lineal escrito en forma estándar:
Minimizar z = ctx
sujeto a: Ax = b
x ≥ 0,
(P )
donde c ∈ IRn, x ∈ IRn, A es una matriz real m× n, rg(A) = m y b ∈ IRm.
El problema dual de (P ) es el siguiente:
Maximizar btw
sujeto a: Atw ≤ c
w ∈ IRm
(D)
Definición 2.9. Sea x una solución básica de (P ). Si zNj − cNj ≤ 0 ∀j ∈ {1, . . . , n−m}, se dice
que x es una solución dual factible de (P ).
Lema 2.9. Sean x una solución dual factible de (P ) y wt = ctBB
−1. Entonces w es una solución
factible de (D) y ctx = btw.
Lema 2.10. Sea x una solución dual factible de (P ). Si xB ≥ 0, entonces x es una solución
óptima de (P ).
Teorema 2.15. Sea x una solución dual factible de (P ). Si ∃ l ∈ {1, . . . ,m} tal que xBl < 0
e yl,Nj ≥ 0 ∀j ∈ {1, . . . , n − m}, entonces (P ) es infactible y el valor óptimo de la función
objetivo de (D) no está acotado.
Teorema 2.16. Sea x una solución dual factible de (P ). Si ∃ l ∈ {1, . . . ,m} tal que
xBl < 0 y ∃ j ∈ {1, . . . , n − m} tal que yl,Nj < 0, entonces al pivotar sobre yl,Nk , donde
k = argmı́n
{
zNj − cNj
yl,Nj
| j ∈ {1, . . . , n−m} con yl,Nj < 0
}
, se obtiene una solución x′ dual factible
de (P ) tal que ctx′ ≥ ctx. Además, ctx′ > ctx si y solo si zNk − cNk < 0.
TEMA 2. PROGRAMACIÓN LINEAL 13
2.7. Inicialización del algoritmo dual del śımplex. Método de la
restricción artificial
Se considera el siguiente problema de programación lineal escrito en forma estándar:
Minimizar z = ctx
sujeto a: Ax = b
x ≥ 0,
(P )
donde c ∈ IRn, x ∈ IRn, A es una matriz real m× n, Im es una submatriz de A y b ∈ IRm.
Siempre se va a tomar la matriz identidad como base inicial para resolver el problema (P ).
Sea B = Im. Si la solución básica asociada a B es una
solución dual factible de (P ), se aplica
el algoritmo dual del śımplex partiendo de B. En otro caso, se aplica el método de la restricción
artificial. Para ello, se considera la restricción artificial, esto es,
n−m∑
j=1
xNj ≤ M,
donde N es la matriz no básica asociada a B y M es una constante positiva lo suficientemente
grande, y se añade al conjunto de restricciones de (P ) transformándola previamente en una igualdad
introduciendo una variable de holgura xn+1, resultando aśı el siguiente problema:
Minimizar zR = c
tx
sujeto a: Ax = b
n−m∑
j=1
xNj + xn+1 = M
x ≥ 0, xn+1 ≥ 0
(PR)
(nótese que la región factible de (PR) está acotada, luego el valor óptimo de zR está acotado y, en
consecuencia, (PR) es infactible o tiene solución óptima; además, el problema (P ) es infactible si y
solo si (PR) es infactible).
A continuación, se construye la tabla del algoritmo del śımplex para (PR) tomando como
variables básicas a xB1 , . . . , xBm , xn+1 (nótese que la base asociada es Im+1), se pivota sobre
ym+1,Nk , donde k = argmáx{zNj − cNj | j ∈ {1, . . . , n − m} con zNj − cNj > 0} (se verifica que
al realizar este pivotaje se obtiene una solución dual factible de (PR)), y se continúa aplicando el
algoritmo dual del śımplex para resolver el problema (PR). Pueden darse las siguientes situaciones:
TEMA 2. PROGRAMACIÓN LINEAL 14
1) (PR) es infactible.
Entonces el problema (P ) es infactible.
2) (PR) tiene solución óptima.
Considérese la tabla óptima del algoritmo dual del śımplex.
Si x∗n+1 > 0, se verifica que el problema (P ) tiene solución óptima y (x
∗
1 . . . x
∗
n)
t es
solución óptima de (P ).
Si x∗n+1 = 0, hay dos posibilidades:
• Si zn+1−cn+1 = 0, se verifica que el problema (P ) tiene solución óptima y es posible
determinar una solución óptima de (P ) a partir de (x∗1 . . . x
∗
n)
t.
• Si zn+1 − cn+1 < 0, se verifica que el valor óptimo de z no está acotado.
2.8. Postoptimización y análisis de sensibilidad
Dado un problema de programación lineal continua que ya ha sido resuelto, la
postoptimización consiste en resolver de forma eficiente el problema que resulta al modificar los
valores de algunos de los parámetros del problema original. El análisis de sensibilidad consiste
en determinar el rango de variación de algunos de los parámetros del problema de forma que la
base óptima del problema original continúe siéndolo.
Se considera el siguiente problema de programación lineal escrito en forma estándar:
Minimizar z = ctx
sujeto a: Ax = b
x ≥ 0,
(P )
donde c ∈ IRn, x ∈ IRn, A es una matriz real m× n y b ∈ IRm.
Supóngase que el problema (P ) tiene solución óptima y que ha sido resuelto mediante el
algoritmo primal o dual del śımplex. Considérese la tabla óptima de dicho algoritmo, y sean B la
matriz básica óptima y N su matriz no básica asociada.
TEMA 2. PROGRAMACIÓN LINEAL 15
2.8.1. Postoptimización
1) Modificación del vector de costes
Se desea reemplazar el vector c por otro vector c′ ∈ IRn.
Hay que actualizar la fila 0 de la tabla. Sean z′Nj = c
′t
ByNj ∀j ∈{1, . . . , n−m} y z′= c′
t
BxB.
Si z′Nj − c
′
Nj
≤ 0 ∀j ∈ {1, . . . , n−m}, la solución básica actual es óptima. En otro caso, se
continúa aplicando el algoritmo (primal) del śımplex.
Se observa que si c′B = cB entonces z
′
Nj
= zNj ∀j ∈ {1, . . . , n−m} y z′ = z.
2) Modificación del vector de términos independientes
Se desea reemplazar el vector b por otro vector b′ ∈ IRm.
Hay que actualizar la última columna de la tabla. Sean x′B = B
−1b′ y z′ = ctB x
′
B.
Si x′B ≥ 0, la solución básica actual es óptima. En otro caso, se continúa aplicando el algoritmo
dual del śımplex.
Se observa que B−1 = (yB01 . . .yB0m), donde B
0 = (aB01 . . .aB0m) = Im es la base a partir
de la cual se comenzó a resolver el problema (P ).
3) Introducción de una nueva variable
Se desea introducir en (P ) una nueva variable xn+1 cuyo coeficiente en la función objetivo es
cn+1 ∈ IR y sus coeficientes en las restricciones vienen dados por el vector an+1 ∈ IRm. Sin
pérdida de generalidad, se supone que xn+1 ≥ 0.
Hay que añadir a la tabla la columna correspondiente a xn+1. Sean yn+1 = B
−1an+1 y
zn+1 = c
t
B yn+1.
Si zn+1 − cn+1 ≤ 0, la solución básica actual es óptima. En otro caso, se continúa aplicando
el algoritmo (primal) del śımplex.
4) Introducción de una nueva restricción
Se desea introducir en (P ) una nueva restricción con vector fila de coeficientes de las variables
am+1 ∈ IRn y término independiente bm+1 ∈ IR.
TEMA 2. PROGRAMACIÓN LINEAL 16
Restricción de desigualdad
Sin pérdida de generalidad, se supone que la restricción es una desigualdad “≤”.
• Si
m∑
i=1
am+1,Bi xBi ≤ bm+1, la solución básica actual es óptima.
• Si
m∑
i=1
am+1,Bi xBi > bm+1, hay que transformar la nueva restricción en una igualdad
introduciendo una variable de holgura xn+1, tomar como (m+1)-ésima variable básica
a xn+1, y añadir a la tabla la fila correspondiente a la restricción a
m+1x+xn+1=bm+1
y la columna correspondiente a xn+1. Sean ym+1,Nj = am+1,Nj −
m∑
i=1
am+1,Bi yi,Nj
∀j ∈ {1, . . . , n−m} y xn+1 = bm+1 −
m∑
i=1
am+1,Bi xBi . Como xn+1 < 0, se continúa
aplicando el algoritmo dual del śımplex.
Restricción de igualdad
• Si
m∑
i=1
am+1,Bi xBi = bm+1, la solución básica actual es óptima.
• Si
m∑
i=1
am+1,Bi xBi > bm+1, hay que introducir una variable artificial xn+1, tomar
como (m+1)-ésima variable básica a xn+1, y añadir a la tabla la fila correspondiente
a la restricción am+1x + xn+1 = bm+1 y la columna correspondiente a xn+1. Sean
ym+1,Nj=am+1,Nj−
m∑
i=1
am+1,Biyi,Nj ∀j∈{1, . . . , n−m} y xn+1=bm+1−
m∑
i=1
am+1,BixBi .
Como xn+1 < 0, se realiza una iteración del algoritmo dual del śımplex, se elimina
de la tabla la columna correspondiente a xn+1 y se continúa aplicando el algoritmo
dual del śımplex.
• Si
m∑
i=1
am+1,Bi xBi < bm+1, hay que multiplicar por −1 la restricción, introducir
una variable artificial xn+1, tomar como (m + 1)-ésima variable básica a xn+1, y
añadir a la tabla la fila correspondiente a la restricción −am+1x + xn+1 = −bm+1
y la columna correspondiente a xn+1. Sean ym+1,Nj = −am+1,Nj +
m∑
i=1
am+1,Bi yi,Nj
∀j ∈ {1, . . . , n−m} y xn+1 = −bm+1 +
m∑
i=1
am+1,Bi xBi . Como xn+1 < 0, se realiza
una iteración del algoritmo dual del śımplex, se elimina de la tabla la columna
correspondiente a xn+1 y se continúa aplicando el algoritmo dual del śımplex.
TEMA 2. PROGRAMACIÓN LINEAL 17
2.8.2. Análisis de sensibilidad
1) Determinación del rango de variación de los costes manteniendo la optimalidad
de B
Se deduce del apartado 1) de la Sección 2.8.1.
2) Determinación del rango de variación de los términos independientes manteniendo
la optimalidad de B
Se deduce del apartado 2) de la Sección 2.8.1.
Io/Programaci?n no Lineal/Hoja8.pdf
PROBLEMAS DE INVESTIGACIÓN OPERATIVA HOJA 8
1. Resolver los siguientes problemas de programación no lineal a partir de las condiciones de
optimalidad de Fritz John y de Karush-Kuhn-Tucker:
(a) Maximizar f(x1, x2) = x
2
1 − 2x2
sujeto a: −x1 + x2 ≥ −2
x1 + 2x2 ≤ 2
x1 ≥ 0
(b) Minimizar f(x1, x2) = 2x1 − x2
sujeto a: 3x21 − x2 ≥ 0
x21 − 5x2 ≤ 0
x2 ≤ 3
(c) Minimizar f(x1, x2) = 3x1 + x2
sujeto a: x21 + x2 ≥ 2
−3x1 + x22 ≤ −2
(d) Minimizar y Maximizar f(x1, x2) = x
2
1 + 4x1x2 + x
2
2
sujeto a: x21 + x
2
2 = 1
(e) Minimizar y Maximizar f(x1, x2, x3) = x1
sujeto a: x1 + x2 + x3 = 0
x21 + x
2
2 + x
2
3 = α,
donde α > 0.
Io/Programaci?n no Lineal/Tema4.pdf
Tema 4
Introducción a la programación no
lineal
4.1. Matrices semidefinidas positivas y definidas positivas
Definición 4.1. Sea A una matriz simétrica n× n.
A es semidefinida positiva si xtAx ≥ 0 ∀x ∈ IRn.
A es definida positiva si xtAx
> 0 ∀x ∈ IRn \ {0}.
Lema 4.1. Sea A =
 a b
b c
. Se verifican los siguientes resultados:
1) A es semidefinida positiva si y solo si a ≥ 0, c ≥ 0 y ac− b2 ≥ 0.
2) A es definida positiva si y solo si a > 0, c > 0 y ac− b2 > 0.
Teorema 4.1. Sea A una matriz simétrica. Entonces A es definida positiva si y solo si es
semidefinida positiva y no singular.
Teorema 4.2. Sea A una matriz simétrica con autovalores reales. Se verifican los siguientes
resultados:
1) A es semidefinida positiva si y solo si todos sus autovalores son no negativos.
2) A es definida positiva si y solo si todos sus autovalores son positivos.
1
TEMA 4. INTRODUCCIÓN A LA PROGRAMACIÓN NO LINEAL 2
4.2. Funciones convexas y cóncavas. Generalizaciones
4.2.1. Convexidad y concavidad en un conjunto
Definición 4.2. Sean S ⊆ IRn un conjunto convexo no vaćıo y f : S → IR.
f es convexa en S si f(λx1+(1−λ)x2) ≤ λf(x1)+(1−λ)f(x2) ∀x1,x2 ∈ S, ∀λ ∈ (0, 1).
f es estrictamente convexa en S si f(λx1+(1−λ)x2)<λf(x1)+(1−λ)f(x2) ∀x1,x2∈S
tales que x1 ̸= x2, ∀λ ∈ (0, 1).
f es cuasiconvexa en S si f(λx1+(1−λ)x2)≤máx{f(x1), f(x2)} ∀x1,x2∈S, ∀λ∈(0, 1).
f es estrictamente cuasiconvexa en S si f(λx1+(1−λ)x2)<máx{f(x1),f(x2)} ∀x1,x2∈S
tales que f(x1) ̸= f(x2), ∀λ ∈ (0, 1).
f es fuertemente cuasiconvexa en S si f(λx1+(1−λ)x2)<máx{f(x1), f(x2)} ∀x1,x2∈S
tales que x1 ̸= x2, ∀λ ∈ (0, 1).
Definición 4.3. Sean S ⊆ IRn un conjunto abierto no vaćıo y f : S → IR diferenciable en S.
f es pseudoconvexa en S si f(x2) ≥ f(x1) ∀x1,x2 ∈ S tales que ∇f(x1)t(x2 − x1) ≥ 0.
f es estrictamente pseudoconvexa en S si f(x2) > f(x1) ∀x1,x2 ∈ S tales que x1 ̸= x2
y ∇f(x1)t(x2 − x1) ≥ 0.
Definición 4.4. Sean S ⊆ IRn un conjunto convexo no vaćıo y f : S → IR.
f es cóncava en S si −f es convexa en S.
f es estrictamente cóncava en S si −f es estrictamente convexa en S.
f es cuasicóncava en S si −f es cuasiconvexa en S.
f es estrictamente cuasicóncava en S si −f es estrictamente cuasiconvexa en S.
f es fuertemente cuasicóncava en S si −f es fuertemente cuasiconvexa en S.
TEMA 4. INTRODUCCIÓN A LA PROGRAMACIÓN NO LINEAL 3
Definición 4.5. Sean S ⊆ IRn un conjunto abierto no vaćıo y f : S → IR diferenciable en S.
f es pseudocóncava en S si −f es pseudoconvexa en S.
f es estrictamente pseudocóncava en S si −f es estrictamente pseudoconvexa en S.
Los conceptos y resultados que se exponen de ahora en adelante están referidos a funciones
convexas y sus generalizaciones, aunque también podŕıan enunciarse de forma análoga para
funciones cóncavas y sus generalizaciones (véanse las definiciones 4.4 y 4.5).
4.2.2. Convexidad en un punto
Definición 4.6. Sean S ⊆ IRn un conjunto convexo, x ∈ S y f : S → IR.
f es convexa en x si f(λx+ (1− λ)x) ≤ λf(x) + (1− λ)f(x) ∀x ∈ S, ∀λ ∈ (0, 1).
f es estrictamente convexa en x si f(λx + (1 − λ)x) < λf(x) + (1 − λ)f(x) ∀x ∈ S
tal que x ̸= x, ∀λ ∈ (0, 1).
f es cuasiconvexa en x si f(λx+ (1− λ)x) ≤ máx {f(x), f(x)} ∀x ∈ S, ∀λ ∈ (0, 1).
f es estrictamente cuasiconvexa en x si f(λx+ (1− λ)x) < máx {f(x), f(x)} ∀x ∈ S
tal que f(x) ̸= f(x), ∀λ ∈ (0, 1).
f es fuertemente cuasiconvexa en x si f(λx + (1 − λ)x) < máx {f(x), f(x)} ∀x ∈ S
tal que x ̸= x, ∀λ ∈ (0, 1).
Definición 4.7. Sean S ⊆ IRn, x ∈ S̊ y f : S → IR diferenciable en x.
f es pseudoconvexa en x si f(x) ≥ f(x) ∀x ∈ S tal que ∇f(x)t(x − x) ≥ 0.
f es estrictamente pseudoconvexa en x si f(x) > f(x) ∀x ∈ S tal que x ̸= x y
∇f(x)t(x − x) ≥ 0.
4.2.3. Relaciones entre los distintos tipos de convexidad
Convexidad estricta ⇒ convexidad
Convexidad ⇒ cuasiconvexidad
TEMA 4. INTRODUCCIÓN A LA PROGRAMACIÓN NO LINEAL 4
Convexidad ⇒ cuasiconvexidad estricta
Convexidad estricta ⇒ cuasiconvexidad fuerte
Cuasiconvexidad estricta + semicontinuidad inferior ⇒ cuasiconvexidad
Cuasiconvexidad fuerte ⇒ cuasiconvexidad
Cuasiconvexidad fuerte ⇒ cuasiconvexidad estricta
Convexidad + diferenciabilidad ⇒ pseudoconvexidad
Convexidad estricta + diferenciabilidad ⇒ pseudoconvexidad estricta
Pseudoconvexidad ⇒ cuasiconvexidad
Pseudoconvexidad ⇒ cuasiconvexidad estricta
Pseudoconvexidad estricta ⇒ cuasiconvexidad fuerte
Pseudoconvexidad estricta ⇒ pseudoconvexidad
4.2.4. Propiedades de las funciones convexas, estrictamente convexas y
cuasiconvexas
Proposición 4.1. Sean S ⊆ IRn un conjunto convexo no vaćıo y f : S → IR. Entonces f es convexa
en S si y solo si f(
m∑
i=1
λixi) ≤
m∑
i=1
λif(xi) ∀m ∈ IN, ∀x1, . . . ,xm ∈ S, ∀λ1, . . . , λm ≥ 0 tales que
m∑
i=1
λi = 1.
Lema 4.2. Sean S ⊆ IRn un conjunto convexo no vaćıo y f1, . . . , fk : S → IR funciones convexas
en S, donde k ∈ IN . Se verifican los siguientes resultados:
1)
k∑
i=1
αifi es una función convexa en S ∀α1, . . . , αk > 0.
2) máx {f1, . . . , fk} es una función convexa en S.
Teorema 4.3. Sean S ⊆ IRn un conjunto convexo no vaćıo y f : S → IR una función convexa en S.
Entonces f es continua en S̊.
TEMA 4. INTRODUCCIÓN A LA PROGRAMACIÓN NO LINEAL 5
Teorema 4.4. Sea S ⊆ IRn un conjunto no vaćıo, convexo y abierto, y sea f : S → IR una función
diferenciable en S. Entonces se verifican los siguientes resultados:
1) f es convexa en S si y solo si (∇f(x2)−∇f(x1))t(x2 − x1) ≥ 0 ∀x1,x2 ∈ S.
2) f es estrictamente convexa en S si y solo si (∇f(x2)−∇f(x1))t(x2 − x1) > 0 ∀x1,x2 ∈ S
tales que x1 ̸= x2.
3) f es cuasiconvexa en S si y solo si ∇f(x2)t(x2 − x1) ≥ 0 ∀x1,x2 ∈ S tales que
f(x2) ≥ f(x1).
Teorema 4.5. Sea S ⊆ IRn un conjunto no vaćıo, convexo y abierto, y sea f : S → IR una función
dos veces diferenciable en S. Se verifican los siguientes resultados:
1) f es convexa en S si y solo si H(x) es semidefinida positiva ∀ x ∈ S.
2) Si f es estrictamente convexa en S, entonces H(x) es semidefinida positiva ∀ x ∈ S.
3) Si H(x) es definida positiva ∀ x ∈ S, entonces f es estrictamente convexa en S.
4.3. Condiciones de optimalidad en problemas de maximización
genéricos
Considérese el siguiente problema de programación matemática:
Maximizar f(x)
sujeto a: x ∈ S,
(P )
donde S ⊆ IRn es un conjunto no vaćıo y f : IRn → IR.
Definición 4.8. Sea x ∈ S.
x es un máximo global de (P ) si f(x) ≥ f(x) ∀x ∈ S.
x es un máximo local de (P ) si ∃ ε > 0 tal que f(x) ≥ f(x) ∀x ∈ S ∩B(x, ε).
x es un máximo local estricto de (P ) si ∃ ε > 0 tal que f(x) > f(x) ∀x ∈ S ∩ B(x, ε)
tal que x ̸= x.
TEMA 4. INTRODUCCIÓN A LA PROGRAMACIÓN NO LINEAL 6
Se observa que si un punto es un máximo global o un máximo local estricto, también es un
máximo local.
Teorema 4.6. Sean S convexo y f convexa y diferenciable en IRn. Si x es un máximo local de (P ),
entonces ∇f(x)t(x − x) ≤ 0 ∀x ∈ S.
Teorema 4.7. Sea S un politopo. Si f es convexa en IRn o f es cuasiconvexa y continua en S,
entonces existe algún punto extremo de S que es un máximo global de (P ).
4.4. Condiciones de optimalidad en problemas de minimización
genéricos
Considérese el siguiente problema de programación matemática:
Minimizar f(x)
sujeto a: x ∈ S,
(P )
donde S ⊆ IRn es un conjunto no vaćıo y f : IRn → IR.
Definición 4.9. Sea x ∈ S.
x es un mı́nimo global de (P ) si f(x) ≤ f(x) ∀x ∈ S.
x es un mı́nimo local de (P ) si ∃ ε > 0 tal que f(x) ≤ f(x) ∀x ∈ S ∩B(x, ε).
x es un mı́nimo local estricto de (P ) si ∃ ε > 0 tal que f(x) < f(x) ∀x ∈ S ∩ B(x, ε)
tal que x ̸= x.
Se observa que si un punto es un mı́nimo global o un mı́nimo local estricto, también es un
mı́nimo local.
Teorema 4.8. Sean S convexo, x ∈ S y f convexa y diferenciable en IRn. Se verifican los
siguientes resultados:
1) x es un mı́nimo global de (P ) si y solo si ∇f(x)t(x − x) ≥ 0 ∀x ∈ S.
2) Si S es abierto, entonces x es un mı́nimo global de (P ) si y solo si ∇f(x)= 0.
TEMA 4. INTRODUCCIÓN A LA PROGRAMACIÓN NO LINEAL 7
Teorema 4.9. Sean S convexo y x un mı́nimo local de (P ). Se verifican los siguientes resultados:
1) Si f es estrictamente