1. No category

MODELIZACIÓN
Eduardo Ramos Méndez
Catedrático de Universidad
ÍNDICE
PRÓLOGO
1
IX
El modelo de programación no lineal
1
1.1 El modelo de programación no lineal . . . . . . .
1.2 Funciones convexas y generalizaciones . . . . . .
1.3 Condiciones de óptimo en programación no lineal . .
1.4 Algoritmos de programación no lineal . . . . . .
1.5 Algoritmos de optimización sin restricciones . . . .
1.6 Algoritmos de optimización con restricciones . . . .
P ROBLEMAS DE AUTOEVALUACI ÓN . . . . . . . .
S OLUCIONES DE LOS PROBLEMAS DE AUTOEVALUACI ÓN
2
Modelos de optimización en redes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 7
. 25
. 69
. 95
111
140
193
195
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
203
234
262
288
343
345
197
2.1 Grafos . . . . . . . . . . . . . . . . . .
2.2 Árboles y arborescencias . . . . . . . . . . .
2.3 Caminos . . . . . . . . . . . . . . . . .
2.4 Flujos . . . . . . . . . . . . . . . . . .
P ROBLEMAS DE AUTOEVALUACI ÓN . . . . . . . .
S OLUCIONES DE LOS PROBLEMAS DE AUTOEVALUACI ÓN
BIBLIOGRAFÍA
349
ÍNDICE ALFABÉTICO
351
PRÓLOGO
Audiencia
Este libro tiene como objetivo principal servir de texto base para la asignatura Modelización del grado de Matemáticas que se imparte en la Universidad
Nacional de Educación a Distancia (UNED) de España. Está dirigido también
al lector interesado en una introducción a los modelos de programación no
lineal y de optimización en redes.
El planteamiento del texto tiene principalmente carácter matemático, haciendo especial énfasis en los desarrollos teóricos y su base formal. Se supone una formación matemática propia de quienes están cursando el grado de
Matemáticas. En concreto, son precisos los conocimientos de Álgebra lineal,
Geometrı́a analı́tica y Análisis matemático obtenidos en los primeros semestres del grado. También es preciso tener un buen conocimiento del modelo de
Programación lineal estudiado en el curso precedente del grado.
Contenidos
La asignatura Modelización forma parte de la materia Investigación Operativa del grado de Matemáticas que se imparte en la UNED de España, y
completa el estudio de los modelos de optimización iniciado con la asignatura
Programación lineal y entera. El programa de estudio se divide en dos unidades didácticas: una dedicada a los modelos de optimización determinista no
lineales y otra dedicada a los modelos de optimización en redes.
El modelo matemático general de optimización estática determinista se conoce habitualmente como modelo de programación no lineal. Este modelo
consiste, esencialmente, en buscar el óptimo de una función numérica de n
variables condicionado a la satisfacción de un conjunto de condiciones de restricción que tienen también, en general, la forma de funciones no lineales de
n variables con valores reales. La consideración de este tipo de funciones abre
paso a la posibilidad de representar de manera adecuada numerosas situaciones reales que surgen en las aplicaciones de los más diversos campos: fı́sica,
ingenierı́a, economı́a, etc. En los primeros apartados se presentan varios ejemplos de dichas aplicaciones, que sirven de motivación para el estudio del objeto
matemático denominado problema de programación no lineal.
La exposición de la programación no lineal se divide en dos grandes bloques. En primer lugar, se aborda el problema desde una perspectiva teórica, a
fin de identificar qué condiciones deben cumplir, de un modo general, las soIX
luciones del problema de optimización. Este estudio no sólo tiene interés por
sı́ mismo, sino que es también la base para fundamentar la búsqueda de métodos prácticos para la resolución del problema. En el estudio de las condiciones
de óptimo desempeña un papel primordial la noción de convexidad de las funciones, y sus generalizaciones, que se analizan con detenimiento. El objetivo
principal del apartado teórico consiste en establecer las denominadas condiciones de Karush, Kuhn y Tucker que constituyen un teorema fundamental que
enlaza con el procedimiento clásico de los multiplicadores de Lagrange.
El segundo bloque se dedica a exponer el fundamento teórico y funcionamiento práctico de diferentes familias de algoritmos, que permiten encontrar
numéricamente la solución del problema de programación no lineal. Este estudio se divide, a su vez, en dos grandes grupos. El primero se limita al caso de
problemas sin restricciones, no tanto por sus posibles aplicaciones prácticas,
sino, principalmente, porque se utilizan como subrutinas en problemas con restricciones. Dentro de este grupo, se estudian distintos algoritmos aplicables a
diferentes tipos de funciones de acuerdo con sus caracterı́sticas y propiedades.
El segundo grupo de métodos está integrado por procedimientos destinados a
resolver el problema general con restricciones. Este grupo también está subdividido en dos conjuntos, según la manera básica de actuar del procedimiento algorı́tmico: los métodos directos, que trabajan con el problema tal como
está formulado y responden a la idea de explorar direcciones de búsqueda que
cumplan las condiciones de restricción, y los métodos indirectos, que transforman el problema original en otro problema cuya resolución es, en principio,
más simple y que se agrupan bajo la familia de los métodos de penalización.
La segunda unidad didáctica se dedica al estudio de los modelos de optimización en redes. Sin lugar a dudas, los problemas de redes son uno de los
ámbitos de aplicación en el que los modelos de optimización han alcanzado los
más notables éxitos. La elegancia de los planteamientos, la solidez de los algoritmos numéricos y la sencilla interpretación de las soluciones obtenidas son
algunas de las principales razones por las cuales los modelos de redes deben
constituir un capı́tulo fundamental de la modelización matemática.
El soporte formal de una red de optimización es el objeto matemático denominado grafo, cuyo estudio constituye el apartado teórico de partida sobre el
cual fundamentar los modelos que se estudian a continuación. Estos modelos
son tres: los modelos de árbol y arborescencias, los modelos de caminos y los
modelos de flujo. La exposición que se hace de todos ellos es muy similar. Se
comienza por presentar algunos ejemplos caracterı́sticos de la situación que se
quiere modelar; a continuación, se analizan los correspondientes algoritmos de
solución; finalmente, se ilustran con un ejemplo de su puesta en práctica.
Método de estudio
El texto está concebido para el estudio individual, según la metodologı́a
propia de la enseñanza a distancia. Cada tema se desarrolla de manera autoX
suficiente, motivando los conceptos y resultados introducidos y presentando
ejemplos de los mismos. Las demostraciones y ejemplos se exponen con detalle, deteniéndose incluso en aspectos elementales, con objeto de facilitar lo
más posible la comprensión del texto en las primeras lecturas. Es aconsejable
leer el texto de manera activa, reflexionando sobre los problemas planteados
y tratando de adelantarse a la solución de los mismos. Esta recomendación
es especialmente útil para la lectura de los ejemplos. Al finalizar cada unidad
didáctica se incluye un breve conjunto de problemas de autoevaluación que
permiten comprobar tanto el grado de asimilación de los conocimientos como el nivel de desarrollo de las habilidades prácticas que persigue el estudio
de la asignatura. Aunque se presentan unas indicaciones sucintas de la solución de los mismos, es recomendable realizar un detenido análisis de dichos
problemas.
Agradecimientos
La composición técnica del libro se ha realizado mediante el software TEX,
utilizando el formato LATEXy diversos comandos desarrollados por el autor.
En la preparación del original ha sido inestimable la colaboración de Eugenio
Tranchero. Con la atenta lectura del borrador, Rafael Sanmartı́n ha contribuido a la cuidadosa depuración de las erratas e incorporación de diversas sugerencias que han enriquecido el texto final. Queremos hacer constar nuestro
agradecimiento a ambos.
Madrid, Diciembre de 2012.
XI
UNIDAD DIDÁCTICA I
El modelo de programación
no lineal
Introducción
3
INTRODUCCIÓN
La formulación más general del modelo de optimización estática y determinista es el modelo de programación no lineal. Esta unidad didáctica se dedica
al estudio de este modelo y puede dividirse en dos grandes partes: la primera
dedicada a la búsqueda y formulación de condiciones teóricas de optimalidad
y la segunda que se ocupa del diseño de algoritmos para la obtención de la
solución numérica.
Tras introducir los conceptos básicos y presentar algunos ejemplos de aplicación del modelo, se desarrollan algunas condiciones teóricas de optimalidad
para el problema de programación no lineal. Este estudio es interesante no sólo
desde el punto de vista teórico sino porque a partir de dichas condiciones es
posible idear algoritmos de solución.
Una de las condiciones de existencia de óptimo más conocidas es el teorema
de Weierstrass, que garantiza que cualquier función continua definida en un
conjunto compacto alcanza en él su máximo y su mı́nimo. Esta condición es no
computable, en el sentido que de ella no es posible extraer criterios numéricos
susceptibles de ser programados en un computador.
Las condiciones de óptimo que estudiaremos aquı́ son, en su mayor parte, condiciones de las que pueden seguirse criterios numéricos de óptimo. Para
ello es necesario suponer hipótesis de diferenciabilidad y convexidad a las funciones del problema. La convexidad es una hipótesis clave para la obtención
de las condiciones de óptimo más relevantes. Por ello es preciso hacer un detenido estudio de las propiedades de las funciones convexas y de sus extensiones
como la cuasiconvexidad y la pseudoconvexidad. Luego se expondrán diversas
condiciones, necesarias y suficientes, que debe cumplir el óptimo del problema
de programación no lineal.
El apartado dedicado a la exposición de algoritmos para la resolución numérica de los problemas de programación no lineal está dividido en dos bloques. Inicialmente, se estudiarán algunos métodos para la optimización de una
función sin presencia de condiciones de restricción y posteriormente se analizará el caso general en el que se considerarán problemas con restricciones.
Si bien es cierto que la mayorı́a de las aplicaciones prácticas de los modelos de optimización incluye restricciones, el estudio de las técnicas de optimización sin restricciones es importante por varias razones. En primer lugar,
muchos algoritmos de optimización con restricciones resuelven el problema
transformándolo en una sucesión de problemas sin restricciones, utilizando para ello, por ejemplo, multiplicadores de Lagrange, funciones de penalización
o funciones barrera. En segundo lugar, otros algoritmos de optimización con
restricciones actúan de la manera siguiente: parten de un punto y, a continua-
4
C AP ÍTULO 1 El modelo de programación no lineal
ción, buscan una dirección a lo largo de la cual optimizan la función criterio.
Este problema de búsqueda del óptimo a lo largo de una dirección de mejora
de la función objetivo es un problema sin restricciones, o bien, con frecuencia,
con simples restricciones de acotación. Finalmente, varias de las técnicas de
optimización sin restricciones pueden extenderse de una manera natural para
incluir restricciones, por lo que pueden servir para idear y motivar procedimientos de solución para problemas con restricciones.
Presentaremos diversos algoritmos para la minimización de una función de
una y varias variables; unos aplicables a cualquier función, incluso aunque no
sea diferenciable, y otros más fuertes basados en la utilización de derivadas.
En el último apartado de la unidad didáctica se aborda el estudio de los
métodos numéricos para resolver el modelo más general, es decir, el problema
de programación no lineal con restricciones. Este estudio de los algoritmos de
optimización con restricciones incluirá dos grandes familias: los métodos de
direcciones factibles y los métodos de penalización.
O BJETIVOS
Conocer el modelo de programación no lineal.
Determinar las condiciones teóricas que deben verificar las soluciones
óptimas del problema de programación no lineal.
Saber resolver teóricamente el problema de programación no lineal.
Conocer el concepto de algoritmo para resolver numéricamente el problema de programación no lineal.
Conocer y saber aplicar diversos algoritmos para la optimización sin
restricciones de una función numérica.
Conocer las principales familias de algoritmos para la resolución numérica de un problema de programación no lineal general.
Saber aplicar los métodos numéricos para resolver prácticamente un modelo de programación no lienal.
C ONTENIDOS
1.1 El modelo de programación no lineal
1.1.1 Definiciones
1.1.2 Solución gráfica de un problema de programación no lineal
1.1.3 Ejemplos de problemas de programación no lineal
1.1.3.1 Diseño de prototipos
1.1.3.2 Localización de equipos
1.1.3.3 Modelo de producción-inventario
1.1.3.4 Modelo de construcción de una autopista
Introducción
1.1.3.5 Un modelo para la administración óptima de recursos hidráulicos
1.1.3.6 Ajuste de curvas
1.1.3.7 Estimación de modelos de correlación para tablas
de contingencia
1.2 Funciones convexas y generalizaciones
1.2.1 Definiciones y propiedades básicas
1.2.1.1 Continuidad de las funciones convexas
1.2.1.2 Derivada direccional de una función convexa
1.2.1.3 Subgradiente de una función convexa
1.2.2 Funciones convexas diferenciables
1.2.2.1 Funciones convexas una vez diferenciables
1.2.2.2 Funciones convexas dos veces diferenciables
1.2.3 Máximos y mı́nimos de funciones convexas
1.2.3.1 Minimización de una función convexa
1.2.3.2 Maximización de una función convexa
1.2.4 Generalización de funciones convexas
1.2.4.1 Funciones cuasiconvexas
1.2.4.2 Funciones cuasiconvexas diferenciables
1.2.4.3 Funciones estrictamente cuasiconvexas
1.2.4.4 Funciones fuertemente cuasiconvexas
1.2.4.5 Funciones pseudoconvexas
1.2.5 Convexidad en un punto
1.3 Condiciones de óptimo en programación no lineal
1.3.1 Problemas sin restricciones
1.3.1.1 Condiciones necesarias de óptimo
1.3.1.2 Condiciones suficientes de óptimo
1.3.2 Problemas con restricciones de desigualdad
1.3.2.1 Condiciones de óptimo de tipo geómetrico
1.3.2.2 Condiciones de óptimo de Fritz John
1.3.2.3 Condiciones de óptimo de Karush, Kuhn y Tucker
1.3.3 Problemas con restricciones de igualdad y desigualdad
1.3.3.1 Condiciones de óptimo de tipo geométrico
1.3.3.2 Condiciones de óptimo de Fritz John
1.3.3.3 Condiciones de óptimo de Karush, Kuhn y Tucker
1.4 Algoritmos de programación no lineal
1.4.1 Algoritmos y convergencia
1.4.1.1 Conceptos básicos
1.4.1.2 Convergencia de algoritmos
1.4.1.3 Composición de aplicaciones algorı́tmicas
5
6
UNIDAD DID ÁCTICA 1 El modelo de programación no lineal
1.4.1.4 Minimización a lo largo de direcciones independientes
1.4.2 Comparación entre algoritmos
1.4.2.1 Orden de convergencia de un algoritmo
1.5 Algoritmos de optimización sin restricciones
1.5.1 Minimización unidimensional sin usar derivadas
1.5.1.1 Búsqueda Uniforme
1.5.1.2 Método de la sección áurea
1.5.1.3 Método de búsqueda de Fibonacci
1.5.2 Minimización unidimensional con derivadas
1.5.2.1 Método de Newton unidimensional
1.5.3 Carácter cerrado de la aplicación algorı́tmica de búsqueda
lineal
1.5.4 Minimización multidimensional sin usar derivadas
1.5.4.1 El método de Hooke y Jeeves
1.5.5 Minimización multidimensional con derivadas
1.5.5.1 El método del descenso más pronunciado
1.5.5.2 Método de Newton
1.5.6 Métodos de direcciones conjugadas
1.5.6.1 El método de Davidon, Fletcher y Powell
1.6 Algoritmos de optimización con restricciones
1.6.1 Métodos de direcciones factibles
1.6.1.1 Método de Zoutendijk para problemas con restricciones lineales
1.6.1.2 Método de Zoutendijk para problemas con restricciones no lineales de desigualdad
1.6.1.3 Método de Zoutendijk para restricciones no lineales
de igualdad
1.6.1.4 Convergencia del método de Zoutendijk
1.6.1.5 El algoritmo de Topkis-Veinott
1.6.1.6 Convergencia del método de Topkis y Veinott
1.6.1.7 El método del gradiente reducido de Wolfe
1.6.2 Métodos de penalización
1.6.2.1 Métodos de penalización exterior
1.6.2.2 Métodos de la función barrera
El modelo de programación no lineal
1.1
7
El modelo de programación no lineal
1.1.1
Definiciones
El problema general de programación matemática puede formularse de la
manera siguiente.
PROBLEMA DE
PROGRAMACIÓN
MATEMÁTICA
Definición 1.1.
Optimizar
f ( x)
sujeto a
x∈S
siendo x = (x1 , x2 , . . . , xn ) un vector de En , f : En −→ E1 y S ⊂ En un
subconjunto cualquiera.
La función f se denomina función objetivo, función criterio o función
económica y es la función que se quiere optimizar, término que engloba dos
posibilidades: maximizar o minimizar. El conjunto S es la región factible. Si S
es vacı́o, el problema se dice no factible. Los puntos x ∈ S son las soluciones
factibles o solución realizables.
Según sea el conjunto S se tienen dos grandes grupos de problemas:
Problemas sin restricciones:
S = En
Es poco frecuente que una situación real pueda modelarse de manera
precisa mediante un problema sin restricciones. Sin embargo es importante el estudio de este tipo de problemas porque se utilizan como subrutinas en la resolución de problemas con restricciones.
Problemas con restricciones:
S = {x ∈ X ⊂ En | gi (x) ≤ 0, i = 1, . . . , m;
hi (x) = 0, i = 1, . . . , ℓ}
donde X es un subconjunto de En , gi : En −→ E1 , i = 1, . . . , m, se llaman restricciones de desigualdad y hi : En −→ E1 , i = 1, . . . , ℓ son las
restricciones de igualdad.
Según las caracterı́sticas de las funciones del problema y de las variables se
tienen diferentes tipos de problemas de programación matemática. Si todas las
funciones del problema, objetivo y restricciones, son funciones lineales entonces se trata de un problema de programación lineal. Si la función del objetivo
es una función cuadrática y las restricciones son lineales se habla de un problema de programación cuadrática. Si en el planteamiento del problema entran
consideraciones de probabilidad el problema es de programación estocástica;
si se incluye el tiempo en la formulación del problema, se trata de un problema de programación dinámica. Como puede verse hay varios modelos de
8
UNIDAD DID ÁCTICA 1 El modelo de programación no lineal
programación matemática. En esta unidad didáctica estudiaremos los problemas de programación no lineal cuya forma general se presenta en la siguiente
definición.
PROBLEMA DE
Definición 1.2.
PROGRAMACIÓN
Minimizar
NO LINEAL
f ( x)
sujeto a
gi (x) ≤ 0
hi (x) = 0
x ∈ X
i = 1, . . . , m
i = 1, . . . , ℓ
siendo f , g1 , . . . , gm , h1 , . . . , hℓ funciones definidas en En con valores en E1 ,
X un subconjunto de En y x un vector de n componentes (x1 , . . . xn ).
En la definición 1.2 la expresión minimizar puede sustituirse por maximizar. Ambos términos pueden considerarse equivalentes para el desarrollo
teórico, puesto que si se tiene un problema de minimización es posible formular otro equivalente de maximización, y recı́procamente, sin más que tener en
cuenta la igualdad
Min f = −Max − f
Asimismo, es obvio decir que el problema podrı́a haberse formulado con
restricciones de desigualdad del tipo ’mayor o igual’, g(x) ≥ 0, sin más que
tener en cuenta que la condición g(x) ≥ 0 es equivalente a −g(x) ≤ 0.
Como se sigue de la formulación anterior, el problema de programación no
lineal consiste en encontrar, si existen, valores de las variables x1 , . . . , xn que
satisfacen todas las restricciones y minimizan la función f . Se puede considerar entonces la siguiente formulación alternativa.
PROBLEMA DE
PROGRAMACIÓN
Definición 1.3. Hallar, si existe, x = (x1 , . . . , xn ) perteneciente a la región
factible
NO LINEAL:
FORMULACIÓN
ALTERNATIVA
S = {x ∈ X ⊂ En | gi (x) ≤ 0, i = 1, . . . , m;
hi (x) = 0, i = 1, . . . , ℓ}
tal que
f ( x) ≥ f ( x ) ,
para todo x ∈ S
En general, dadas las caracterı́sticas de las funciones no lineales, la condición f (x) ≥ f (x) para cualquier punto factible, que caracteriza a la solución
óptima del problema, es de difı́cil comprobación práctica. Por ello, es habitual
considerar otras alternativas en el concepto de solución óptima del problema
de programación no lineal.
Al respecto debemos notar dos hechos: en primer lugar, sólo los puntos
factibles pueden ser óptimos; en segundo lugar, la optimalidad de un punto x
viene dada por su relación con otros puntos factibles pertenecientes a un en-
El modelo de programación no lineal
Mı́nimo
global
Mı́nimo local
débil
9
Mı́nimo local
fuerte
Figura 1.1: Mı́nimo global y mı́nimos locales (débil y fuerte).
torno del punto considerado, es decir, a los puntos pertenecientes a un conjunto
de la forma Nε (x) = {x ∈ En | ||x − x|| < ε }, siendo ε > 0 un escalar. Esto
nos conduce a definir diversos conceptos de solución óptima del problema de
minimización.
MÍNIMO LOCAL
FUERTE DEL
PROBLEMA DE
PROGRAMACIÓN
NO LINEAL
Definición 1.4. Un punto x es un mı́nimo local fuerte del problema de
programación no lineal si existe un entorno de x, Nε (x) con ε > 0, tal que
i) f (x) está definida en Nε (x).
ii) f (x) < f (x) para todo x ∈ S ∩ Nε (x), x 6= x.
En el caso en que x sea el único punto factible también se considera un
mı́nimo local fuerte.
MÍNIMO LOCAL
DÉBIL DEL
PROBLEMA DE
PROGRAMACIÓN
NO LINEAL
Definición 1.5. Un punto x es un mı́nimo local débil del problema de
programación no lineal si existe un entorno de x, Nε (x) con ε > 0, tal que
i) f (x) está definida en Nε (x).
ii) f (x) ≤ f (x) para todo x ∈ S ∩ Nε (x), x 6= x.
iii) x no es un mı́nimo local fuerte.
Las definiciones anteriores implican que un punto x no es un mı́nimo local
cuando existe un entorno del punto con al menos otro punto con valor menor
de la función objetivo. La mayor parte de los resultados que pueden obtenerse
en programación no lineal son resultados que caracterizan mı́nimos locales.
En las aplicaciones prácticas estas caracterizaciones proporcionan resultados
suficientemente satisfactorios. No obstante en algunos casos es posible caracterizar el mı́nimo global que, como se ha indicado en la definición 1.2, viene
caracterizado de la manera siguiente.
10
UNIDAD DID ÁCTICA 1 El modelo de programación no lineal
MÍNIMO GLOBAL
Definición 1.6. Un punto x es un mı́nimo global si
DEL PROBLEMA
f ( x) ≤ f ( x)
DE
PROGRAMACIÓN
para todo x ∈ S
NO LINEAL
Figura 1.2: La función y = x3 .
Figura 1.3: La función y = ex .
La figura 1.1 representa diversos tipos de mı́nimo de una función.
No todos los problemas de programación no lineal, incluso aunque su región factible sea no vacı́a, tienen que tener solución óptima, ni siquiera en el
caso de que la función objetivo esté acotada. Por ejemplo, la función f (x) = x3
no tiene mı́nimo finito, figura 1.2, y la función f (x) = ex , aun siendo acotada
inferiormente, no alcanza su mı́nimo, figura 1.3.
Las definiciones que se han dado de mı́nimo local fuerte y débil no son
computables. Exigen el cálculo del valor de la función en un entorno con infinitos puntos, lo cual no es viable desde el punto de vista computacional, ni
siquiera admitiendo la posibilidad de evaluar la función en un conjunto finito
de puntos representativos. Por tanto, hay que buscar otra manera de comprobar la optimalidad de una solución dada. Si las funciones del problema poseen
ciertas propiedades, tales como la diferenciabilidad, es posible encontrar condiciones que se pueden calcular. Éstas van a ser el tipo de condiciones que se
van a estudiar en esta unidad didáctica.
1.1.2
Solución gráfica de un problema de programación no
lineal
Algunos problemas de programación no lineal con dos o tres variables pueden admitir una representación gráfica en el plano o en el espacio, a partir de
la cual puede razonarse el modo de encontrar la solución óptima del mismo.
Veamos un ejemplo.
EJEMPLO 1.1
Consideremos el siguiente problema de programación no lineal
Minimizar f (x1 , x2 ) ≡ (x1 − 3)2 + (x2 − 2)2
sujeto a
g 1 ( x1 , x2 ) ≡
x21 −x2 −3 ≤ 0
g 2 ( x1 , x2 ) ≡
x2 −1 ≤ 0
g3 (x1 , x2 ) ≡ −x1
≤0
La representación del problema en el plano cartesiano (x1 , x2 ) se encuentra en la figura 1.4. Para determinar la región factible, representamos en el plano cada una de las
tres restricciones g1 , g2 y g3 . La curva gi = 0, i = 1, 2, 3, divide al plano en dos regiones, una formada por los puntos (x1 , x2 ) en los cuales gi (x1 , x2 ) ≤ 0 y otra en los que
se verifica la desigualdad gi (x1 , x2 ) ≥ 0. Es sencillo averiguar cuál es la región correspondiente a cada desigualdad sin más que observar el valor que toma gi en un punto
cualquiera, por ejemplo en el origen. La región factible será la intersección de las tres
regiones correspondiente a las tres restricciones. En la figura 1.4 viene representada
en color oscuro.
El modelo de programación no lineal
g1 ≤ 0
x2
f = f = 2 = mı́nimo
3
•
2
•
1
g2 ≤ 0
−2
11
x2 − 1 = 0
x1
−1
1
3
4
5
Solución
óptima
−1
Región
factible
−2
−3
2
g3 ≤ 0
Figura 1.4: Representación gráfica de un problema de programación no lineal
Para determinar la solución óptima, representamos las curvas de nivel de la función
objetivo, es decir, las curvas de la forma f (x1 , x2 ) = k, donde k es una constante. En
la figura 1.4
√ se ve que dichas curvas son circunferencias centradas en el punto (3, 2)
con radio k y se representan con lı́neas de puntos. La solución óptima del problema
será un punto de la región factible tal que la circunferencia de nivel que pase por él sea
la de menor radio, entre todas las que tienen puntos en común con la región factible.
Dicho de otra manera, el punto óptimo será el ‘primer’ punto de la región factible al
cual alcancen las curvas de nivel de la función objetivo al hacer crecer a la constante
k. En la figura 1.4 se aprecia que dicho punto es el punto del cuadrante x1 ≥ 0, x2 ≥ 0
en el que se cortan las restricciones g1 y g2 , es decir, es la solución, con valores no
negativos, del sistema de ecuaciones x21 − x2 − 3 = 0 y x2 − 1 = 0, que corresponde
al punto x1 = 2, x2 = 1. En este punto la función objetivo vale f (2, 1) = 2 que es el
valor mı́nimo buscado.
Podemos observar que el mı́nimo sin restricciones de la función objetivo es precisamente el punto (3, 2), en el cual f (3, 2) = 0. Éste es el menor valor que puede tomar
f . De hecho, el valor de la función objetivo en el punto (x1 , x2 ) no es más que el cuadrado de la distancia euclı́dea desde el punto (x1 , x2 ) al punto (3, 2). Este problema
tiene una interpretación sencilla: se trata de encontrar el punto de la región factible
que está a menor distancia del punto (3, 2).
1.1.3
Ejemplos de problemas de programación no lineal
1.1.3.1 Diseño de prototipos
Supongamos que se quiere diseñar un contenedor, cerrado en el fondo y
abierto por la parte superior, para transportar M metros cúbicos de un árido
12
UNIDAD DID ÁCTICA 1 El modelo de programación no lineal
desde un punto A a otro punto B. El costo del fondo y de las partes laterales es
de a euros por metro cuadrado, mientras que el costo de las extremos es de b
euros por metro cuadrado. La caja no tiene precio de reventa y cada viaje de
ida y vuelta entre A y B cuesta c euros. Se desea saber qué dimensiones debe
tener el contenedor para que el coste conjunto de fabricación y transporte sea
lo menor posible.
El modelo matemático
Variables:
El contenedor queda determinado al conocer sus dimensiones. Por tanto,
podemos considerar las siguientes variables:
• x1 = metros de largo,
• x2 = metros de ancho,
• x3 = metros de alto.
Restricciones:
• Condiciones naturales de no negatividad de las dimensiones:
x1 , x2 , x3 ≥ 0
Función objetivo:
Hay que considerar el coste total de la operación, es decir, el coste de
fabricar el contenedor más el coste de los viajes necesarios para transportar los M metros cúbicos del árido.
• Fabricación:
• Transporte:
Coste
fabricación
Coste
viajes
=
=
=
=
=
Coste
fondo
a x1 x2
+
+
Coste de
cada viaje
c
c
Coste
laterales
×
2a x1 x3
+
+
Viajes
necesarios
Coste
extremos
2b x2 x3
cúbicos mercancı́a
× Metros
Capacidad contenedor
M
×
x1 x2 x3
En sı́ntesis, el modelo de programación no lineal para el problema del diseño
de un contenedor es el siguiente:
Minimizar f (x1 , x2 , x3 ) = a x1 x2 + 2a x1 x3 + 2b x2 x3 + c
sujeto a
x1 , x2 , x3 ≥ 0
M
x1 x2 x3
El modelo de programación no lineal
13
1.1.3.2 Localización de equipos
Muchas empresas de servicios se enfrentan, con frecuencia, con el problema de determinar la ubicación óptima de sus centros de actividades. Situaciones caracterı́sticas son la colocación de máquinas en una factorı́a, la ubicación
de los distintos departamentos dentro una fábrica, la propia localización de las
fábricas o almacenes en un región geográfica a fin de servir una red de clientes, la localización de los equipos de emergencia en un área urbana, como la
policı́a, bomberos, etc., los servicios sociales como las escuelas, centros sanitarios y otros varios.
Plantearemos a continuación un modelo sencillo relativo a este tipo de problemas. Sea un conjunto de mercados cuyas localizaciones geográficas son
fijas y conocidas, y cuyas demandas de un determinado producto son también
conocidas. Se pretenden satisfacer dichas demandas mediante una red de almacenes cuyas capacidades son asimismo conocidas. Se trata de determinar
en dónde han de ubicarse dichos almacenes, de forma que la distancia total
recorrida al enviar los productos desde los almacenes a los puntos de demanda
sea lo menor posible. Para fijar ideas, supongamos que el número de mercados es n, con demandas conocidas r j , j = 1, . . . , n, y situados en los puntos de
coordenadas (a j , b j ), j = 1, . . . , n. Supongamos, asimismo, que se ha decidido
satisfacer dicha demanda mediante un conjunto de m almacenes, cada uno de
ellos con capacidad ci , i = 1, . . . , m. El problema es determinar en qué lugares hay que situar los almacenes para que el coste de transportar la mercancı́a
desde dichos almacenes a los mercados sea lo menor posible, supuesto que se
satisfacen las necesidades de cada mercado y no se supera la disponibilidad de
cada almacén.
El modelo matemático
Variables:
Llamemos (xi , yi ) a la localización desconocida del almacén i. Sea di j
la distancia desde el almacén i al mercado j, i = 1, . . . , m; j = 1, . . . , n.
Podemos considerar diferentes medidas de distancia.
di j = |xi − a j | + |yi − b j |
di j = [(xi − a j )2 + (yi − b j )2 ]1/2
Para cada una de ellas tendremos un modelo diferente.
Por otra parte, llamemos wi j al número de unidades del producto enviadas desde el almacén i al mercado j, i = 1, . . . , m; j = 1, . . . , n.
Restricciones:
14
UNIDAD DID ÁCTICA 1 El modelo de programación no lineal
• Demanda de los mercados:
m
∑ wi j ≥ r j
j = 1, . . . , n
i= 1
• Disponibilidad de los almacenes:
n
∑ wi j ≤ ci
i = 1, . . . , m
j =1
Función objetivo:
m
n
∑ ∑ wi j di j
i= 1 j = 1
En resumen, el problema de localizar los almacenes y determinar el patrón de
envı́o puede establecerse de la manera siguiente:
m
Minimizar
n
∑ ∑ wi j di j
i= 1 j = 1
sujeto a
m
∑ wi j
≥ rj
j = 1, . . . , n
∑ wi j
≤ ci
i = 1, . . . , m
i= 1
n
j =1
wi j ≥ 0 i = 1, . . . , m; j = 1, . . . , n
Como hay que determinar wi j y di j se tiene un problema de programación
no lineal. Si en lugar de di j se introduce en el modelo su expresión en función de (xi , yi ) y (a j , b j ) se tiene un problema de programación no lineal en las
variables x1 , . . . , xm ; y1 , . . . , ym y w11 , . . . , wmn . Podemos observar que si la localización de los almacenes es fija, entonces las di j son conocidas y el problema
anterior no es otro que el conocido problema del transporte1 .
1.1.3.3 Modelo de producción-inventario
Consideremos una compañı́a que fabrica un determinado producto con la
finalidad de satisfacer una demanda conocida y que precisa hacer una planificación de la producción para un total de K perı́odos de tiempo. Se admite que
durante cualquier perı́odo la demanda puede satisfacerse mediante las unidades disponibles en inventario al comienzo del perı́odo y la producción durante
dicho perı́odo. La demanda es conocida y resulta ser dk unidades de producto
en el perı́odo k = 1, . . . , K. Cada trabajador tiene capacidad para producir p
unidades de producto en cada perı́odo, si bien la máxima cantidad de producto
que se puede fabricar durante un determinado perı́odo está restringida por la
1 Ver
Ramos, E. (2012): Programación lineal y entera, Ediciones Académicas, pg. 331.
El modelo de programación no lineal
15
capacidad de producción del equipo de que se dispone, por lo que no puede exceder de b unidades. Se supone que es posible contratar temporalmente mano
de obra cuando se necesita y despedirla cuando es superflua. Sin embargo para
desalentar grandes fluctuaciones en la cantidad de personal contratado, existe
un coste de contratación que es proporcional al cuadrado de la diferencia entre
la mano de obra contratada al final de un perı́odo y el comienzo del siguiente,
con constante de proporcionalidad igual a c1 . Por otra parte, se supone que se
incurre en un coste de almacenamiento que es proporcional al inventario que
pasa de un perı́odo al siguiente, cuya constante de proporcionalidad es c2 . El
modelo pretende determinar la fuerza laboral de que debe disponer la empresa
y el correspondiente inventario durante los periodos 1, . . . , K, de forma que se
satisfaga la demanda de los clientes y se minimice el coste total de operación
de la fábrica. Como datos iniciales se sabe que el inventario y la fuerza laboral
existente al comienzo de las operaciones es respectivamente I0 y L0 .
El modelo matemático
Variables:
Las variables que definen el modelo son:
Ik = nivel del inventario al finalizar el perı́odo k = 1, . . . , K.
Lk = fuerza laboral existente al finalizar el perı́odo k = 1, . . . , K.
Podemos considerar la variable auxiliar:
uk = fuerza laboral adquirida al comienzo del periodo k = 1, . . . , K.
Observemos que si uk < 0 se entiende que la fuerza laboral se ha reducido en el perı́odo k una cantidad uk .
Restricciones:
• Equilibrio de la fuerza laboral:
Lk = Lk−1 + uk
k = 1, . . . , K
• Equilibrio del inventario:
Ik = Ik−1 + p Lk−1 − dk
k = 1, . . . , K
• Limitaciones de producción:
0 ≤ Lk ≤
b
p
k = 1, . . . , K
• No negatividad del nivel de inventario:
Ik ≥ 0 k = 1, . . . , K
16
UNIDAD DID ÁCTICA 1 El modelo de programación no lineal
Función objetivo: El coste de operación incluye los costes de estabilidad
de la plantilla y el coste de almacenamiento:
K
∑ (c1 u2k + c2 Ik )
k=1
El problema de producción-inventario puede establecerse como sigue:
K
∑ (c1 u2k + c2 Ik )
Minimizar
k=1
sujeto a
Lk = Lk−1 + uk
Ik = Ik−1 + p Lk−1 − dk
b
0 ≤ Lk ≤
p
Ik ≥ 0
k = 1, . . . , K
k = 1, . . . , K
k = 1, . . . , K
k = 1, . . . , K
1.1.3.4 Modelo de construcción de una autopista
Supongamos que se quiere construir una carretera sobre un terreno desigual. Se supone que el costo de construcción es proporcional a la cantidad de
escombro que hay que añadir o remover. Sea T la longitud de la carretera y sea
c(t ) la altura conocida del terreno para t ∈ [0, T ]. El modelo tiene como objetivo encontrar la ecuación y(t ) que describe la altura óptima de la carretera para
t ∈ [0, T ]. Las restricciones que se pueden considerar son varias. En concreto,
para evitar que la pendiente de la carretera sea excesiva se puede exigir que la
pendiente máxima no debe exceder de b1 , es decir,
|ẏ(t )| ≤ b1
Además, para reducir los inconvenientes de la conducción, la razón de cambio
de la pendiente de la carretera no debe exceder de b2 , es decir,
|ÿ(t )| ≤ b2
Además como condiciones inicial y final se ha de cumplir que y(0) = a,
y(T ) = b.
El modelo matemático
El problema puede establecerse de la forma siguiente:
Minimizar
Z T
0
sujeto a
|ẏ(t )|
|ÿ(t )|
y( 0)
y( T )
|y(t ) − c(t )| dt
≤
≤
=
=
b1 t ∈ [0, T ]
b2 t ∈ [0, T ]
a
b
El modelo de programación no lineal
17
Tal como está formulado se trata del problema de control óptimo continuo, en
el cual la variable de control es u(t ) = |y(t ) − c(t )| que es la cantidad de tierra
que hay que remover.
Podemos plantear el problema anterior de manera aproximada mediante un
problema de programación no lineal. Para ello, pongamos y1 = y; y2 = ẏ y dividamos la carretera en K intervalos, suponiendo por simplicidad que cada uno
de ellos tiene longitud 1. Denotemos c(k), y1 (k), y2 (k) respectivamente por ck ,
y1,k e y2,k . Aproximaremos ẏ e ÿ por diferencias finitas, teniendo presente que
hemos supuesto que la longitud del intervalo es igual a 1. El problema se puede
plantear de la forma siguiente:
K
Minimizar
∑ |y1,k − ck |
k=1
sujeto a
y1,k − y1,k−1
−b1
−b2
y1,0
y1,K
=
≤
≤
=
=
y2,k−1
k = 1, . . . , K
y2,k ≤ b1
k = 0, . . . , K − 1
y2,k − y2,k−1 ≤ b2 k = 1, . . . , K − 1
a
b
1.1.3.5 Un modelo para la administración óptima de recursos hidráulicos
Consideremos el esquema de la figura 1.5 que representa una presa hidráulica que cierra un rı́o y embalsa el agua para uso agrı́cola y generación de corriente eléctrica. Se supone que la central eléctrica está cercana al rı́o. Parte del
agua destinada al uso agrı́cola llega directamente desde la presa, mientras que
la otra parte alcanza su destino después de haber pasado por la central eléctrica. Vamos a desarrollar un modelo de optimización para la administración de
los recursos hidráulicos tanto para la generación de energı́a como para el uso
agrı́cola.
El modelo matemático
Para construir el modelo adoptaremos un horizonte de planificación de N
perı́odos de tiempo, correspondientes al tiempo de vida previsto para las principales inversiones, tales como la construcción de la presa, las canalizaciones,
etc.
Variables:
En este problema podemos considerar dos tipos de variables:
1. Variables de diseño:
18
UNIDAD DID ÁCTICA 1 El modelo de programación no lineal
yj
Presa
xM
j
xAj
Central
Eléctrica
Rı́o
xPA
j
Zona
Agrı́cola
Canal Principal
xPM
j
Figura 1.5: Esquema de un sistema de utilización de recursos de agua.
S
U
=
=
E
=
Capacidad de la presa.
Capacidad del canal que suministra agua a la agricultura.
Capacidad de la planta eléctrica.
2. Variables operativas:
En la figura pueden identificarse fácilmente las siguientes variables
para j = 1, . . . , N.
yj
xAj
=
=
xPA
j
=
xPM
j
=
xMj
=
Cantidad de agua que recibe la presa.
Cantidad de agua liberada desde la presa a la agricultura.
Cantidad de agua liberada para potencia eléctrica y
luego para la agricultura.
Cantidad de agua liberada para potencia eléctrica y
luego devuelta al rı́o.
Cantidad de agua liberada desde la presa directamente en el rı́o.
Consideramos también las siguientes variables auxiliares para j =
1, . . . , N:
El modelo de programación no lineal
sj
fj
δ
=
=
=
19
Cantidad de agua existente en la reserva.
Cantidad de energı́a producida.
0,1 variable binaria utilizada en la función objetivo.
Restricciones:
1. Restricciones de generación de potencia.
• La potencia generada no puede exceder a la energı́a potencial
del agua suministrada, de forma que:
PA
f j ≤ xPM
ψ (s j ) γ ℓ
j + xj
en donde ψ (s j ) es una función conocida proporcionada por
los técnicos de ingenierı́a eléctrica que depende del agua s j
almacenada en la reserva en el periodo j, γ es un factor conocido de conversión de potencia y ℓ es la eficiencia conocida
del sistema de potencia.
• La potencia generada no puede exceder de la capacidad de
generación de la planta eléctrica, por lo que:
f j ≤ αj E ℓHj
en donde α j es un factor de carga conocido y H j número de
horas de operación, que se supone dado en el modelo.
• La capacidad de la planta ha de estar dentro de lı́mites aceptables dados, es decir,
E ′ ≤ E ≤ E ′′
2. Restricciones de reserva.
• Si se desprecian las pérdidas por evaporación, entonces la cantidad de agua y j que recibe la presa debe ser igual al cambio
en la cantidad almacenada en la presa y al agua liberada para
diferentes propósitos. Esto puede expresarse como:
PA
s j+1 − s j + xAj + xMj + xPM
j + xj = yj
• Un segundo conjunto de restricciones establece que el agua
almacenada en la reserva deberı́a ser adecuada y estar dentro
de los lı́mites aceptables, es decir
S′ ≤ s j ≤ S′′
3. Restricción acerca del agua que hay que liberar obligatoriamente.
Inicialmente es necesario especificar que una cierta cantidad de
agua conocida M j debe liberarse corriente abajo para satisfacer las
necesidades del rio. Esto puede escribirse como
xMj + xPM
j ≥ Mj
20
UNIDAD DID ÁCTICA 1 El modelo de programación no lineal
4. Capacidad del canal.
Finalmente necesitamos especificar que la capacidad del canal U
deberı́a ser adecuada para manejar las necesidades agrı́colas. Por
tanto:
xAj + xPA
j ≤U
Función objetivo:
El objetivo es minimizar el coste total descontado asociado con la reserva, planta de potencia y canal de la agricultura, menos las ganancias
derivadas de la generación de potencia y la agricultura. Vamos a discutir
estos costes.
1. Planta de energı́a
Asociada con la planta de energı́a tenemos el coste:
N
C (E ) + ∑ β j Ĝe (E )
j =1
δ
(
N
en donde C (E ) es el coste de la planta de energı́a, estructuras asociadas y equipos de transmisión en función de la capacidad de la
planta E, Ĝe (E ) es el coste anual de operación, mantenimiento y
costes de reemplazamiento de los equipos de energı́a en función de
E y β j es el factor de descuento para dar el valor presente del coste
en el perı́odo j.
Las ganancias descontadas asociadas con la venta de electricidad
pueden expresarse como:
)
)
(
∑ β j [ p j Fj + pd ( f j − Fj ) ] + (1− δ )
j =1
n
∑ β j [ p j f j + ps (Fj − f j ) ]
j =1
en donde Fj es la demanda de energı́a de la firma conocida que
puede venderse a un precio conocido p f . La expresión anterior se
completa con la condición δ = 1 si f j > Fj y δ = 0, si f j < Fj .
Si δ = 1 el exceso de energı́a f j − Fj puede venderse a precio de
saldo conocido pd , mientras que si δ = 0 se incurre en una penalidad de ps (Fj − f j ) puesto que es necesario comprar electricidad
de otras empresas.
2. Reserva y canal
• Los costes de capital descontados vienen dados por
Cr (S) + α Cℓ (U )
en donde Cr (S) es la función que da el coste de la presa cuando su capacidad es S, Cℓ (U ) es la función de coste del canal
El modelo de programación no lineal
21
principal cuando su capacidad es U y α es un escalar para tener en cuenta el menor tiempo de vida del canal comparado
con la presa.
• Los costes de operación descontados vienen dados por
N
∑ βj
j =1
h
Cbr (S) + Cbℓ (U )
i
3. Beneficios del riego
La cosecha producida por el riego puede expresarse como una función R del agua usada para riego durante el perı́odo j. Entonces los
beneficios de la agricultura vienen dados por
N
∑ βj R
j =1
xAl + xPA
j
Aquı́ se ha despreciado el agua suministrada por la lluvia.
En resumen, el problema consistirá en minimizar los costes netos sometidos
a todo el conjunto de restricciones.
1.1.3.6 Ajuste de curvas
En una investigación cientı́fica, en campos tales como la biologı́a, quı́mica, economı́a, etc. suele interesar el observar una variable y que depende del
tiempo t, según una relación que el investigador supone tiene una cierta forma
funcional, por ejemplo, lineal, cuadrática, logarı́tmica, exponencial, etc. Dicha
relación depende de unos parámetros que la caracterizan, y el objetivo de la
investigación es estimar dichos parámetros a partir de una muestra de observaciones. Un criterio de estimación clásico es el criterio de mı́nimos cuadrados.
Con este criterio el problema de estimación es un problema de programación
no lineal.
Por ejemplo, supongamos que la hipótesis del investigador es que una variable económica Y depende del tiempo t según una relación de tipo exponencial
de la forma
Y = a + bect
donde a, b, c son parámetros del modelo que hay que estimar. Supongamos que
se dispone de una muestra y1 , y2 , . . . , ym de valores de la variable Y , correspondientes a los valores del tiempo t1 ,t2 , . . . ,tm . Según el criterio de mı́nimos
cuadrados, los valores de a, b, c que mejor ajustan la curva se obtienen resolviendo el siguiente problema de minimización:
m
Minimizar F (a, b, c) =
∑ (yi − (a + bect ))2
i
i= 1
22
UNIDAD DID ÁCTICA 1 El modelo de programación no lineal
En ocasiones pueden introducirse en el problema restricciones en los parámetros, del tipo
a, b ≥ 0, c ≤ 0
u otras que permiten al investigador añadir condiciones al modelo.
1.1.3.7 Estimación de modelos de correlación para tablas de contingencia
La prensa publica frecuentemente tablas que recogen la opinión de los ciudadanos sobre diversas cuestiones de interés social. Supongamos, por ejemplo,
que interesa conocer el grado de acuerdo de la población con respecto a cierta
decisión del gobierno. Para ello se puede realizar una encuesta a una determinada muestra de la población y, si se clasifica a los individuos de acuerdo con
su opción polı́tica, los resultados pueden venir tabulados de la forma siguiente:
Opción polı́tica Mucho Suficiente Poco Algo Nada NS / NC TOTAL
A
B
C
D
10
5
5
0
41
27
24
2
94
76
38
8
94
80
18
8
81
29
15
1
17
6
0
1
337
223
100
20
TOTAL
20
94
216 200
126
24
680
Una tabla como la anterior recibe el nombre de tabla de contingencia. En una
investigación como ésta, puede interesar estimar cual es la distribución de probabilidad subyacente en la tabla, dadas las frecuencias observadas. El método
usual en estadı́stica para hacerlo es suponer que dicha distribución sigue un
modelo dependiente de una serie de parámetros que hay que estimar mediante
algún criterio.
Los modelos de asociación y correlación para la tabla se basan en la idea de
convertir las variables cualitativas que se están observando en variables cuantitativas, asignando para ello valores numéricos a las filas y columnas. Dicho
valores se denominan usualmente puntuaciones canónicas, y forman parte de
los parámetros del modelo. Esto permite tratar la tabla con herramientas del
análisis estadı́stico de variables cuantitativas.
Por ejemplo, un modelo de correlación que explica la distribución de probabilidad de la tabla puede ser de la forma siguiente:
pi j = pi. p. j (1 + λ xi y j )
i = 1, . . . , I; j = 1, . . . , J
en donde pi j es la probabilidad de la casilla i, j, pi. , p. j son parámetros pertenecientes respectivamente a las filas y a las columnas, con el significado de
probabilidades marginales, λ es un parámetro con el significado de una medida
de correlación y xi , y j son parámetros pertenecientes a las filas y a las columnas
con el significado de las puntuaciones canónicas mencionadas anteriormente.
El modelo de programación no lineal
23
En este modelo se supone que la probabilidad de la casilla i, j depende
de cinco parámetros: pi. , parámetro que tiene el significado de probabilidad
total de la fila, p. j parámetro que tiene el significado de probabilidad total
de la columna, xi parámetro que significa el valor de la fila i en la variable
canónica (cuantitativa) que recorre las filas, de modo similar a como la variable
cualitativa “opción polı́tica” las recorrı́a, y j parámetro que significa el valor de
la columna j en la variable canónica (cuantitativa) que recorre las columnas,
de modo análogo a como lo hacı́a la variable (cualitativa) “grado de acuerdo”,
y λ parámetro que hace referencia al nivel de correlación existente entre las
filas y las columnas.
En el modelo pueden introducirse condiciones que deban cumplir los parámetros. De manera natural
∑ pi j = 1
ij
que implica la restricción en los parámetros
∑ pi. p. j (1 + λ xi y j ) = 1
i = 1, . . . , I; j = 1, . . . , J
ij
Por otra parte, dado que los parámetros pi. , p. j tienen el significado de
probabilidades totales marginales son naturales las condiciones
∑ pi j = pi.
i = 1, . . . , I
∑ pi j = p. j
j = 1, . . . , J
j
i
lo cual conduce a las siguientes restricciones en los parámetros:
∑ p. j (1 + λ xiy j ) = 1
i = 1, . . . , I
∑ pi. (1 + λ xi y j ) = 1
j = 1, . . . , J
j
i
También es usual incluir condiciones que fijen el origen y la escala en las
puntuaciones canónicas:
∑ xi pi. = 0
∑ x2i pi. = 1
∑ y j p. j = 0
∑ y2j p. j = 1
i
j
i
j
Otro tipo de restricciones en las puntuaciones canónicas que permiten recoger la ordenación (mucho – suficiente – poco – algo – nada – ns/nc) que existe
en la variable “grado de acuerdo” son las siguientes:
y j ≤ y j +1
j = 1, . . . , J − 1
24
UNIDAD DID ÁCTICA 1 El modelo de programación no lineal
Restricciones naturales son
pi. ≥ 0
i = 1, . . . , I
p. j ≥ 0
j = 1, . . . , J
Como criterio de estimación se pueden emplear varios. Utilizando el criterio de máxima verosimilitud la función que hay que minimizar es
− ∑ pˆi j ln( pi. p. j (1 + λ xi y j ))
ij
en donde pˆi j representa la frecuencia relativa observada.
En resumen, el problema de estimación de la distribución de probabilidad
subyacente en la tabla, cuando se supone un modelo de correlación es el siguiente problema de programación no lineal.
Minimizar − ∑ pˆi j ln( pi. p. j (1 + λ xi y j ))
ij
sujeto a
∑ pi. p. j (1 + λ xi y j ) = 1
i = 1, . . . , I; j = 1, . . . , J
ij
∑ p. j (1 + λ xiy j ) = 1
i = 1, . . . , I
∑ pi. (1 + λ xi y j ) = 1
j = 1, . . . , J
j
i
∑ xi pi. = 0
i
∑ x2i pi. = 1
i
∑ y j p. j = 0
j
∑ y2j p. j = 1
j
y j ≤ y j +1
j = 1, . . . , J − 1
pi. ≥ 0
i = 1, . . . , I
p. j ≥ 0
j = 1, . . . , J