Progra Cuadratica

T´
ecnicas Cl´
asicas de Optimizaci´
on.
Parte I: Programaci´on Lineal y No Lineal
Mar´ıa Merino Maestre

Facultad de Ciencia y Tecnolog´ıa
Departamento de Matem´atica Aplicada y
Estad´ıstica e Investigaci´on Operativa
UPV/EHU

´Indice general
Pr´
ologo

3

I

Programaci´
on Lineal y No Lineal

5

1 Programaci´
on Lineal
1.1 Introducci´on a la Investigaci´on Operativa . .
1.1.1 Definiciones . .. . . . . . . . . . . .
1.1.2 Clasificaci´on . . . . . . . . . . . . . .
1.1.3 Metodolog´ıa . . . . . . . . . . . . . .
1.2 Introducci´on a la Programaci´on Lineal . . .
1.2.1 Formulaci´on matem´atica . . . . . . .
1.2.2 Transformaciones . . . . . . . . . . .
1.2.3 Clasificaci´on . . . . . . . . . . . . . .
1.2.4 Resoluci´on gr´afica . . . . . . . . . . .
1.3 El m´etodo S´ımplex . . . . . . . . .. . . . .
1.3.1 Resoluci´on algebraica . . . . . . . . .
1.3.2 Resoluci´on tabular . . . . . . . . . .
1.3.3 Casos especiales . . . . . . . . . . . .
1.3.4 Identificaci´on de SBF iniciales . . . .
1.3.5 Teor´ıa del M´etodo S´ımplex . . . . . .
1.4 Teor´ıa de dualidad y an´alisis de sensibilidad
1.4.1 Propiedades de la Teor´ıa de Dualidad
1.4.2 Interpretaci´on econ´omica . . . . . . .
1.4.3An´alisis de sensibilidad . . . . . . . .

7
7
7
8
10
11
12
13
16
16
20
21
27
30
34
36
48
49
51
53

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

2 Programaci´
on No Lineal
57
2.1 Introducci´on a la Programaci´on No Lineal . . . . . . . . . . . . 57
2.2 Tipos de problemas de PNL . . . . . . . . . . . . . . . . . . . . 62
i

´INDICE GENERAL
2.3 Optimizaci´on no restringida . . . . . . . . .
2.4 Optimizaci´on restringida:condiciones KKT
2.5 Programaci´on cuadr´atica . . . . . . . . . . .
2.5.1 Formulaci´on cuadr´atica . . . . . . . .
2.5.2 Condiciones KKT para programaci´on
2.5.3 M´etodo S´ımplex Modificado . . . . .

1
. . . . . .
. . . . . .
. . . . . .
. . . . . .
cuadr´atica
. . . . . .

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

67
72
73
73
75
77

2

´INDICE GENERAL

Pr´
ologo
Laasignatura T´
ecnicas Cl´
asicas de Optimizaci´
on forma parte del M´aster
en Modelizaci´on e Investigaci´on Matem´atica, Estad´ıstica y Computaci´on, ve´ase
http://riemann.unizar.es/matg5/.
Esta asignatura pretende introducir al alumnado en metodolog´ıas modernas
que contribuyen a resolver problemas de decisi´on donde hay que optimizar el
uso de recursos limitados en contextos aplicados (industriales,econ´omicos, ...).
La asignatura est´a dividida en tres partes:
Parte I: Programaci´on Continua (Lineal y No Lineal).
Parte II: Programaci´on Entera.
Parte III: Programaci´on Estoc´astica.
Se recomienda consultar la siguiente bibliograf´ıa y enlaces: para Optimizaci´on los libros [1, 2, 3, 4, 5], para Optimizaci´on No Lineal [6, 7], para
Optimizaci´on Estoc´astica [8, 9, 10].
Sobre software deOptimizaci´on pueden consultarse las siguientes referencias:
COIN-OR: el c´odigo abierto de la Comunidad de Investigaci´on Operativa
COmputational INfrastructure for Operations Research se puede consultar en [11] y una gu´ıa en [12].
CPLEX: el optimizador de IBM ILOG CPLEX se puede consultar en [13],
as´ı como una gu´ıa en [14].
XPRESS: la edici´on de estudiante del sofware FICO Xpress Optimizationsuite est´a disponible en la web [15].
GUSEK: el GLPK Under Scite Extended Kit est´a disponible en la p´agina
[16].

3

4

´INDICE GENERAL

Parte I
Programaci´
on Lineal y No
Lineal

5

Cap´ıtulo 1
Programaci´
on Lineal
1.1
1.1.1

Introducci´
on a la Investigaci´
on Operativa
Definiciones

¿En qu´e consiste la Investigaci´on Operativa? Veamos algunas de las definiciones dadas:
• Un m´etodo...