PROGRAMACIÓN NO LINEAL CUADRÁTICA

RESUMEN
La programación cuadrática (QP) es el nombre que se le da a un procedimiento que
minimiza una función cuadrática de n variables sujeta a m restricciones lineales de igualdad
o desigualdad. Un programa cuadrático es la forma más simple de problema no lineal con
restricciones de desigualdad.

La importancia de la programación cuadrática recae en que, como es un caso especial de la

programación no lineal, se utiliza como una función modelo para aproximar funciones no
lineales a través de modelos locales.

Existen diferentes tipos de problemas de programación cuadrática, los cuales se pueden

clasificar en: “De minimización sin restricciones”, “De minimización sujetos a restricciones
de igualdad”, “De minimización sujetos a restricciones lineales de desigualdad”, “de
optimización de redes cuadráticas”, cuadráticos convexos, cuadráticos no convexos,
complementariedad lineal.
 INTRODUCCIÓN
La investigación de operaciones es un área de estudio que implementa modelos
matemáticos, estadísticos y diversos algoritmos para solucionar problemas generalmente
involucrados con la toma de decisiones, generando resultados óptimos para determinadas
situaciones ya sea para establecer ganancias, reducir los costos de una determinada
producción o simplemente determinar si una decisión puede ser la más apropiada para el
curso de una compañía o de la vida cotidiana.

Es fundamental explorar los métodos de aproximación para resolver problemas de

optimización, así como la filosofía de operación, aplicación y funcionamiento en un
entorno de interconexión de sistemas, es por esto que se hace uso de la programación no
lineal. Existen muchas ramas dentro de la investigación de operaciones para tratar diversos
tipos de problemas, algunos más complejos que otros; Dentro de la investigación de
operaciones se encuentran la programación entera, programación no lineal, programación
dinámica y teoría de inventarios.

El enfoque principal que se quiere trabajar es lo referente a la programación no lineal, más

específicamente la programación no lineal cuadrática; formada por una función objetivo
cuadrática que cuenta con diferentes métodos de solución y es aplicada a varios campos.

PARTE I. CONTEXTUALIZACIÓN DE LA INVESTIGACIÓN

4.1 DESCRIPCIÓN DE LA INVESTIGACIÓN

En este capítulo se busca dar a conocer las razones sobre lo que se quiere investigar acerca
de la programación no lineal cuadrática, su definición, algunos antecedentes, áreas de
estudio, aplicaciones teóricas, aplicaciones reales, aportes históricos y conceptos básicos
del tema.

4.1.1 OBJETIVOS DE LA INVESTIGACIÓN

[Link] Objetivo General
El objetivo que se busca alcanzar con esta investigación es dar a conocer los conceptos
generales referenciados a la programación no lineal cuadrática, estudiando su historia,
herramientas utilizadas y las aplicaciones que tiene esta rama en la investigación de
operaciones aplicada en la vida real.

[Link] Objetivos Específicos.

 Realizar un repaso histórico de los acontecimientos más importantes que hicieron
posible el surgimiento de la programación no lineal cuadrática, su definición,
evolución y aplicaciones.
 Generar la capacidad de identificar cuáles son los tipos de problemas que
pertenecen a la rama de la programación no lineal cuadrática y los métodos más
importantes que permiten resolverlos.
 Presentar ejercicios de carácter clásico, académicos, investigativos y propuestos
sobre la programación no lineal cuadrática.

4.1.2 REVISIÓN TEÓRICA

[Link] Historia
La necesidad de planificación y organización aparece ya en el antiguo Egipto hacia
el año 4000 a. C. y se va desarrollando a través de toda la Antigüedad hasta el
advenimiento del Imperio Romano. En Israel y China también aparecen tímidos
escarceos de organización y dirección hacia el año 1000 a. C. Nabucodonosor establece
algunas ideas sobre control de la producción hacia el año 600 a. C. En Grecia, se
desarrollan en el 350 a. C. los primeros métodos de organización del trabajo y del tiempo.
Alrededor del año 30 a. C., Julio César establece diversas ideas de planificación, control
y unidad de mando, que luego pone en práctica en todo el Imperio Romano. Todos los
estudios y planteamientos organizacionales de la Antigüedad tienen su proyección, que no
su continuación, a lo largo de toda la Edad Media, en donde se aprovechan sin posteriores
desarrollos. Durante el siglo XV, en la Italia renacentista se vuelven a plantear de nuevo las
cuestiones organizativas y aparecen diversos estudios sobre costes y sobre control de
existencias.

Cuando los Estados Unidos entran en la guerra, son conscientes de la necesidad de tales
grupos operativos y de la constitución de secciones operacionales para el éxito de los
mismos. De esta manera, constituyen en 1942 un grupo operacional de lucha antisubmarina
(ASWORG - Anti-Submarine Warfare Operations Research Group) que recoge toda la
experiencia inglesa desarrollada por Blackett. De forma similar, la Fuerza Aérea Americana
estructura diversos grupos operacionales para llevar a cabo sus labores logísticas. Al final
de la guerra, la Armada americana disponía de un departamento de Investigación Operativa
compuesto por más de setenta científicos, y la Fuerza Aérea disponía de más de dos
docenas de secciones operacionales.

No puede decirse que las potencias del Eje hicieran uso de las técnicas operacionales
durante la II Guerra Mundial, mientras que el número de científicos e investigadores
involucrados en Investigación Operativa en la contienda por parte de ingleses, americanos y
canadienses superó los setecientos. Las aportaciones que hicieron todos estos
investigadores supusieron un giro copernicano en la manera de concebir la Ciencia de la
Gestión en los años siguientes. De alguna manera, todos estos estudiosos que trabajaban de
manera aislada en los años treinta se aglutinaron holísticamente con ocasión de la guerra, y
produjeron un conjunto de técnicas y teorías que ocasionaron el alumbramiento de la
Investigación de Operaciones como ciencia.

Una vez finalizó la contienda mundial y habida cuenta del éxito cosechado por las técnicas
operativas, éstas continuaron desarrollándose dentro del ámbito militar, puesto que era el
ejército quien poseía la mayor parte de los investigadores y quien estaba interesado en
proseguir dicha línea de trabajo. A mediados de los años cincuenta se desplazó el centro de
gravedad de interés de la Investigación Operativa, y alcanzó el terreno industrial y el
académico.

No obstante, la IO forma cada día más, una parte de las actividades de la empresa moderna,
y por tanto ya no se trata de una función especializada que deba llevarse a cabo en un
departamento separado, eran muy frecuentes las técnicas de análisis estadístico y por eso
nacen alternativas a distintos tipos de problemas emergentes como lo son la teoría de
inventarios, la programación dinámica y otras no tan usadas como lo son la programación
no lineal y la programación entera.
Históricamente, las funciones cuadráticas fueron prominentes porque proveían modelos
locales simples para funciones no lineales generales. Una función cuadrática, es la función
no lineal más simple, y cuando es usada como una aproximación para una función no lineal
general, esta puede capturar la información importante de la curvatura, lo que una
aproximación lineal no puede. El uso de aproximaciones cuadráticas para resolver
problemas con funciones no lineales generales se remonta mucho tiempo atrás. Entre los
métodos más destacados, tenemos al método de Newton y el método de gradiente
conjugado.

Se han desarrollado algoritmos y se han extendido otros, esto permite desarrollar el

problema, algunos de los algoritmos son: Condiciones Karush (1939)-Kuhn-Tucker (1951),
Newton – Raphson (1736), y el algoritmo de Frank and Wolfe (1956).

[Link] Desarrollo
A continuación se presentan algunos de los sucesos más relevantes que permitieron el
desarrollo de la programación no lineal cuadrática.

Año Autor/es Aporte

1736 Isaac Newton y Joseph Raphson Método de Newton-Raphson
1758 Joshep Louis Lagrange Multiplicadores de Lagrange.
1939 Estados Unidos Primer estudio de IO con el objetivo de encontrar
prácticas optimas en un sistema detecciones
militares.
1947 Proyecto Scoop (Scientific Algoritmo Simplex (Método para resolver
Computation Of Optima problemas de programación lineal).
Programs)
1951 Case institute of technology Primera conferencia sobre la IO en la industria.
Caracterización de condiciones de optimalidad
Karush-Kuhn-Tucker.
1956 Marguerite Frank y Philip Wolfe Algoritmo de Frank and Wolfe
1995 Hamdy A. Taha Método de las dos fases
Tabla 4.1 Desarrollo de la PNLC

[Link] Conceptualización
Existen varios métodos que permiten resolver problemas de programación no lineal
cuadrática, los algoritmos que se presentan en este trabajo son los más relevantes que se
encuentran en general en la programación no lineal y se pueden aplicar según el nivel de
complejidad del problema dado.

Un modelo de programación dinámica cuadrática se define como una función a maximizar

o minimizar representada por:

z=CX + X T DX

Sujeta a:

AX ≤ b , X ≥ 0

[Link].1 Multiplicadores de Lagrange

El método de los multiplicadores de Lagrange permite encontrar los máximos y mínimos de
funciones de múltiples variables sujetas a restricciones que consiste en adicionar
multiplicadores por cada variable del problema para así formar la función objetivo y de esta
forma, se obtienen resultados de las nuevas restricciones del problema lineal asociado.

La solución se puede encontrar mediante los siguientes pasos:

1. Escribir el problema en forma estándar.

2. Usando la formula:
m n
L=f ( x ) + ∑ μ i gi ( x )+ ∑ λi hi ( x)
i=1 j=1

Construir la función de Lagrange, donde n será la cantidad de restricciones y m la

de variables.
3. Hallar las derivadas parciales de las variables.
4. Se obtiene un nuevo problema con nuevas restricciones y las originales.
5. Finalmente se resuelve usando el método simplex.

[Link].2 Frank & Wolfe

El método de Frank & Wolfe Encuentra una solución factible a las restricciones lineales
reduciendo la función objetivo mediante el método simplex o el método grafico para
encontrar la solución óptima dando origen a una secuencia de problemas de programación
lineal, se tiene que considerar que no hay pivoteo sobre la variable de excedente si x1 es
básica y no hacer pivoteo que convierta la variable de holgura y lambda en básicas.

Los pasos son: Agregar una variable básica evidente, minimizar la suma de variables
artificiales y evaluar si satisface las variables de holgura complementarias

[Link].3 Método de las dos fases

Este método utiliza la primera parte del método de las dos fases para resolver PL, que
termina en una suma de variables artificiales y obtiene una solución.

El Método de las Dos Fases es una variante del Algoritmo simplex, que es usado como
alternativa al Método de la Gran M, donde se evita el uso de la constante M para las
variables artificiales y se puede resumir así:

Fase Uno: Maximizar la suma de 3 de las variables artificiales del modelo. Si el valor de la
Z óptima es cero, se puede proseguir a la Fase Dos, de lo contrario el problema no tiene
solución.

Fase Dos: Con base en la tabla reclinable de la fase uno, se elimina de las restricciones las
variables artificiales, y se reemplaza la función objetivo, por la función objetivo original y
se resuelve a partir de la resultante, con el método Simplex tradicional.

[Link].3 Método de Newton- Rapshon

Resuelve problemas de optimización restringida con múltiples variables, se basa en una
aproximación cuadrática de la función objetivo, obtenida al truncar la serie de Taylor
alrededor de la solución hipotética actual en donde se consigue la nueva función de prueba
optimizando la función anterior y se inicia la siguiente iteración.

[Link].4 Condiciones de Karush-Kuhn-Tucker (KKT)

Éste método está basado en el método de Lagrange, son necesarias para maximizar una
función cóncava con un área de factibilidad convexa y son condiciones necesarias para
determinar una solución óptima. Este método nos permite determinar un óptimo local
restringido a un intervalo y obtiene un óptimo global que comprende todo el dominio, en
donde Z estricta es cóncava o convexa; las iteraciones se realizan hasta llegar a un conjunto
de restricciones activas donde su solución también satisface las restricciones omitidas.
El diagrama de flujo para la solución de un problema por este método se presenta a
continuación.

Figura 4.1 Diagrama de flujo para las condiciones de Karush-Kuhn-Tucker

[Link] Trabajos de investigación realizados y futuros

Estos son algunos trabajos de investigación, desde la IEEE, se colocan en ingles porque es
más fácil encontrarlos así.
  A Quadratic Programming Formulation to Find the Maximum Independent
Set of Any Graph, Maher Heal, 2016 International Conference on Computational
Science and Computational Intelligence (CSCI)

Una formulación de programación cuadrática para encontrar el máximo

conjunto independiente de cualquier gráfico

Resumen:
Encontrar el máximo conjunto independiente (o conjunto estable) de cualquier
gráfico es un problema importante en la teoría de grafos que tiene muchas
aplicaciones como la visión por computadora / reconocimiento de patrones, la teoría
de la información / codificación, la biología molecular y la programación. En este
artículo proponemos una formulación de programación en cuadratura para encontrar
el máximo conjunto independiente de cualquier gráfico de las cliques máximas de la
gráfica. Está demostrado en la literatura de ciencia computacional, existen cerca de
algoritmos óptimos para enumerar las camarillas máximas de gráficos escasos.
Usando nuestra formulación, hemos sido capaces de encontrar el desconocido
independiente máximo set y número de independencia de algunos grafos conocidos
como gráfico Gardner, Balaban 11 gráfico de la jaula y grafo de Hoffman-
Singleton.

 Grouping singular spectrum analysis components via mixed

integer quadratic programming, Peiru Lin; Weichao Kuang; Chuqi Yang; Wing-
Kuen Ling, 2016 IEEE International Conference on Consumer Electronics-China
(ICCE-China)

Agrupación de componentes de análisis de espectro singulares mediante

programación cuadrática entera mixta

Resumen:
 SSA se ha convertido en una herramienta estándar en meteorología y climatología;
También es una técnica bien conocida en física no lineal y procesamiento de
señales. SSA es esencialmente una técnica libre de modelo; Es más una herramienta
exploratoria y de construcción de modelos que un procedimiento de confirmación.
Su objetivo es la descomposición de la serie original en una suma de un pequeño
número de componentes interpretables, como una tendencia de variación lenta,
componentes oscilatorios y un ruido "sin estructura". Las posibles áreas de
aplicación de la SSA son diversas: desde las matemáticas y la física hasta las
matemáticas económicas y financieras, desde la meteorología y la oceanología hasta
las ciencias sociales y las investigaciones de mercado. Cualquier serie
aparentemente compleja con una estructura potencial podría proporcionar otro
ejemplo de una aplicación exitosa de SSA

 Dynamic economic dispatch of hybrid microgrid with energy storage

usingquadratic programming, Rony Seto Wibowo; Kemas Robby Firmansyah; Ni
Ketut Aryani; Adi Soeprijanto, 2016 IEEE Region 10 Conference (TENCON)

Envío dinámico económico de microgrid híbrido con almacenamiento de

energía mediante programación cuadrática.

Resumen:

La demanda de energía eléctrica aumenta rápidamente debido al desarrollo de la

tecnología. Por el contrario, la disponibilidad de fuentes de energía no renovables
seguramente disminuye. Este problema tendrá un impacto en la seguridad
energética nacional. Para satisfacer la necesidad de una gran potencia eléctrica, se
requiere desarrollar una gran área de pequeñas escalas de generaciones distribuidas.
Las generaciones distribuidas utilizan fuentes de energía renovables, como la PV,
para minimizar el uso de fuentes de energía no renovables. Para maximizar la
 utilización de los recursos renovables, es necesario aplicar el almacenamiento de
energía. Este almacenamiento es necesario para almacenar el exceso de energía
generada por las centrales eléctricas basadas en energías renovables. Con las
generaciones distribuidas y el almacenamiento de energía que están conectados a la
red principal a través de la microgrid, es importante optimizar el funcionamiento del
sistema de potencia para satisfacer la carga diaria. En este artículo, el problema de
optimización se formula como envío dinámico económico que se aplica sobre
microgrid híbrido con almacenamiento de energía. El problema se resuelve
mediante la programación cuadrática basada en Matlab.

[Link] Mapa conceptual

Figura 4.2 Mapa conceptual PNLC parte 1

 Figura 4.3 Mapa conceptual PNLC parte 2

[Link] Mapa causal

Figura 9.4 Mapa Causal PNLC

 Figura 4. 1.

[Link] Mentefacto

Figura 4.5 Mentefacto PNLC

[Link] Software desarrollado

Existen tres programas que ayudan bastante con este tipo de problemas, son KNITRO, que
resuelve problemas de optimización matemática a gran escala, CPLEX, el cual es un
soporte de tomas de decisiones mediante el análisis para mejorar la eficacia, reducir los
costes y aumentar la rentabilidad, GAMS Utiliza un lenguaje de modelización buscando
formular y resolver un modelo, este sistema general de modelado algebraico está diseñado
para problemas lineales y no lineales, especializado en problemas grandes y complejos;
permite al usuario concentrarse en el problema a modelar haciendo que el planteamiento
sea simple, y el clásico Solver de Excel el cual busca el valor óptimo para una fórmula de
celda denominada celda objetivo, todos las aplicaciones anteriormente mostradas, resuelven
problemas de optimización lineales, la programación cuadrática, y unos que otros
problemas no lineales

Figura 4.6 Software desarrollado para la solución de problemas de PNLC

 PARTE II. DESARROLLO DE LA INVESTIGACIÓN
4.2 REVISIÓN PRÁCTICA
En este capítulo se mostrarán problemas clásicos resueltos, problemas académicos,
problemas de investigación y problemas propuestos sobre programación no lineal
cuadrática.

4.2.1 PROBLEMAS CLÁSICOS RESUELTOS

[Link] Problema 1

Enunciado:

Maximizar Z=4 x 1+ 6 x2−2 x 21−2 x 1 x 2−2 x22

S.A:3 x 1+2 x 2=2

Solución:

Paso 1 L ( x1 , x 2 , λ ) =4 x 1 +6 x 2−2 x21 −2 x 1 x 2−2 x 22+ λ(2−3 x 1−2 x 2)

Se reescribe el problema de la siguiente

manera

Paso 2 ∂L ∂L ∂ L
= = =0
∂ x1 ∂ x2 ∂ λ
Se establece que.
∂L
=4−4 x 1−2 x 2−3 λ=0
∂ x1
Paso 3

∂L
Se hallan las derivadas parciales con respecto =6−2 x 1−4 x 2−2 λ=0
∂ x2
a cada variable.

∂L
=2−3 x1 −2 x 2=0
∂λ
Paso 4 4 4 1 73
x 2= − λ x 1 = − λ
3 27 3 108
Se despejan x 1 y x 2.

Paso 5 ∂L
=2−3 x1 −2 x 2=0
∂λ

∂L
Sustituimos los valores de x 1 y de x 2 en y
∂λ 1 73 4 4
hallamos el valor de λ .
2−3 ( −
3 108) ( )
λ −2 − λ =0
3 27

180
λ=
251

Paso 6 73
∗180
1 108 32
x 1= − =
3 251 753

Se sustituye el valor de λ en x 1 y en x 2

4
∗180
4 27 308
x 2= − =
3 251 251

Paso 7
 El punto óptimo es: 32 308
f( , )
753 251

[Link] Problema 2

Enunciado:
MIN f(x) = – 8x1 – 16x2 + x12 + 4x22

S.A.: x1 + x2 ≤ 5
x1 ≤ 3
x1, x2 ≥ 0

PASOS PROCEDIMIENTO

1. Se hallan las matrices Q, CT, Las nuevas matrices son:

A y b. Tener en cuenta que
la matriz Q debe ser positiva
para que el resultado sea un
resultado global óptimo.
2. Aplicando las ecuaciones de La nuevas ecuaciones serán:
condiciones de KKT, se
obtienen unas nuevas
ecuaciones:

X1, x2, μ1,μ2, y1, y2, v1, v2 ≥ 0

3. Ahora para generar el El Nuevo problema es:

problema lineal más
MIN a1 + a2 + a3 + a4
adecuado, se deben agregar
S.A.:
variables adicionales a cada
 restricción y minimizar su
sumatoria

X1, x2, μ1,μ2, y1, y2, v1, v2 ≥ 0

4. Resultados de las cinco

Iteraciones del método
simplex modificado

5. Finalmente se resuelve Esta es la solución obtenida:

usando el método simplex
modificado y se obtiene una
X1=3,X2=2
solución.

[Link] Problema 3

Enunciado:
Max Z=25 X 1 +35 X 2−10 X 12−15 X 22

S . A X 1+ 2 X 2 ≤ 30

2 X 1 + X 2 ≤ 40

X 1 , X 2 ≥0

PASOS PROCEDIMIENTO
 1. Construir la función de
Lagrange. F ( X , λ , μ )=25 X 1+ 35 X 2−10 X 12−15 X 22− λ1 ( X 1+ 2 X 2 )−λ 2 ( 2 X 1 + X 2) + μ 1 (− X 1 )

2. Encontrar las derivadas ∂F

=25−20 X 1−λ1−2 λ 2−μ1=0
parciales de la función. ∂ X1

∂F
=35−30 X 2−2 λ1−λ 2−μ2=0
∂ X2

3. Reescribir el problema como MinW =R1 + R2

un problema de programación
S . A 20 X 1+ λ1+ 2 λ 2+ μ 1+ R 1=25
lineal.
30 X 2 +2 λ1 + λ2 + μ2 + R2 =35X 1 +2 X 2 + S1=302 X 1 + X 2 + S2=40
X 1 , X 2 , λ1 , λ 2 , μ1 , μ 2 ≥ 0

Iteracion 1

4. Resolver por el método de Cj 0 0 0 0 0 0 1 1 0 0  

las dos fases R R S

V.B X1 X2 λ1 λ2 μ1 μ2 S2 Bj
1 2 1
R 2
1 20 0 1 2 1 0 1 0 0 0
1 5
R 1
1 0 30 2 1 0 1 0 1 0 0
2 0
S 0 1 2 0 0 0 0 0 0 1 0 3
 1 0
S 4
0 2 1 0 0 0 0 0 1 0 1
2 0
Z - - - - - - - - 3
0 0
  20 30 3 3 1 1 1 1 5

Tablero final

Cj 0 0 0 0 0 0 1 1 0 0  
R R S
V.B X1 X2 λ1 λ2 μ1 μ2 S2 Bj
1 2 1
1 1 1 1
5
X / / / /
0 1 0 0 0 0 0 /
1 2 1 2 2
4
0 0 0 0
1 1 1 1
7
X / / / /
0 0 1 0 0 0 0 /
2 1 3 3 3
6
5 0 0 0
- 3
- - - -
1 - 1
1 1 1 1
S 1 1 7
0 0 0 / / / / 1 0
1 / / /
2 1 1 2
6 6 1
0 5 5 0
0 2
- - - - - 1
-
7 1 1 1 1 0
S 1
0 0 0 / / / / / 0 1 9
2 /
3 1 3 3 1 /
6
0 0 0 0 0 3
 Z
0 0 0 0 0 0 1 1 0 0 0
 
Se obtienen las siguientes soluciones:

5 7 317 109
X 1= ; X 2= ; S 1= ; S 2=
4 6 12 3

5 7 5 2 7 2
Z=25( )+35( )−10( ) −15( )
5. Reemplazar en la función 4 6 4 6
original los valores de X1 y X2
Z=36.042

6. La solución final es Z=36.042

5
X 1=
4

7
X 2=
6

[Link] Problema 4

Enunciado:

Min Z= X 12+ X 22−2 X 1−3 X 2 + X 1 X 2

Sujeto a : X 1 +2 X 2=2

X 1 , X 2 ≥0

Solución:
Paso 1

Se toma la función objetivo del

problema de minimización y la
restricción se toma como otra
función multiplicada por una nueva Z ( x 1 , x 2 )= λW ( x 1 , x 2)
variable (λ) en donde hallaremos los
valores de las variables en las dos
funciones obteniendo así el valor x 12+ x 22−2 x 1−3 x2 + x 1 x 2=λ ( x 1+ 2 x 2−2)
mínimo de la función objetivo.

Paso 2

Aplicamos derivación parcial a ambos

lados e igualamos sus resultados

∂Z ∂W
=2 x1 + x 2−2 =λ
∂Z ∂W ∂ x1 ∂ x1
=λ
∂ x1 ∂ x1

∂Z ∂W
=2 x 2+ x 1−3 =2 λ
∂Z ∂W ∂ x2 ∂ x2
=λ
∂ x2 ∂ x2

Paso 3 Multiplicando la ecuación 1 por 2 y restándole ésta a la

ecuación 2
A partir de las derivadas parciales
procederemos a hallar los valores de
2 x2 + x 1−3=2 λ
x1 y x2
−4 x1 −2 x 2 +4=−2 λ

−3 x 1+1=0
1. 2 x1 + x 2−2=λ
2. 2 x2 + x 1−3=2 λ

1
x 1=
3

Reemplazamos el valor de x 1en W ( x 1 , x 2 )

( 13 )+2 x −2=0
2

5
x 2=
6

Paso 4

1 2 5 2
Reemplazamos los valores de x 1 y x 2
en la función objetivo y hallamos el
Z ( ) ( ) ( ) ( ) ( ) ( )( 56 )
1 5
, =
3 6 3
+
6
−2
1
3
−3
5
6
+
1
3

valor mínimo de la función y con este

la resolución de problema de
1 5 25
programación no lineal cuadrática. Z ( )
, =
3 6 12
[Link] Problema 5

Enunciado:

Minimizar la función:

Z=(x 1−2)2 +( x 2−2)2

Sujeto a :
x 1+ 2 x 2 ≤ 3
8 x 1+ 5 x 2 ≤10
xi ≥ 0

Solución:

Pasos Procedimiento

1. Dado que la función objetivo

es una circunferencias, se x 1+ 2 x 2=3
observa el valor de interés
gráficamente, obteniendo
que:

8 x 1+ 5 x 2 ≥10
2. De las restricciones:
 3. Gráficamente se observa de la
siguiente forma:

4. De la Perpendicular:
x 2=m x 1 +c , con m=2

5. En el punto (2,2)
x 2−2=2( x1−2)

6. De tal forma que:

x 1+ 2 x 2=3 y 2 x 1−x 2=2

7 4
x 1= , x 2 =
5 5

9
Z min=
5

[Link] Problema 6

Fórmulas utilizadas:

Calculo de varianza

Calculo de covarianza
Enunciado:

Entre tres empresas invierten en acciones por medio de capital: 10´000.000, esto es
cotizado en la bolsa de valores, se tienen dividendos por acción. Rentabilidad esperada: 8%.

2000 2001 2002 2003 2004

Empresa A 2 1 2 3 2

Empresa B 1 2 3 4 2
Empresa C 2 2 3 2 2

SOLUCIÓN:

Pasos Procedimiento
1. Hallamos las 1 1
A2= ( 22+12 +22 +32 +22 ) − (2+1+2+3+2)2
varianzas 5 25

correspondiente 1 1
B2= ( 12 +22 +32 +4 2 +22 )− (1+ 2+ 3+4 +2)2
s 5 25

1 1
C 2= ( 22 +22+ 32 +22+ 22) − (2+ 2+ 3+2+2)2
5 25

A2=0.4

B2=1.04

C 2=0.16
2. Usar la fórmula 1 1
A 12= ( 2∗1+ 1∗2+2∗3+3∗4+ 2∗2 )− ¿
para las 5 25

covarianzas 1 1
A 13= (2∗2+1∗2+2∗3+3∗2+2∗2 ) − ¿
5 25

1 1
A 23= (1∗2+2∗2+3∗3+ 4∗2+2∗2 )− ¿
5 25
 A12=0.4

A13=0

A23=0.12

A21=0.4

A31=0

A32=0.12
3. Hacemos una
matriz con los
valores que no 0.4 0.4 0
M=0.4 1.04 0.12
dieron las dos 0 0.12 0.16
anteriores
formulas
4. Establecemos el (2+1+2+3+2)
R 1= =2
rendimiento 5

con respecto al ( 1+2+3+4 +2 )

R 2= =2.4
8% 5

(2+ 2+ 3+2+2)
R 3= =2.2
5

2x1+2.4x2+2.2x3 >= 800000

4.2.2 PROBLEMAS ACADÉMICOS RESUELTOS
[Link] Problema 1
Un inversionista posee 10000 dólares que desea invertir en un conjunto de dos acciones
y desea saber cuánto le conviene invertir en cada acción, sabiendo que la acción 1 tiene
un rendimiento anual de 0,06 mientras que la acción 2 es de 0,02, la acción 1 posee un
límite superior de la inversión de 0,75 mientras que la acción 2 es de 0,9, la varianza de
la acción 1 e de 0,09 y de la acción 2 es de 0,06, y tienen una covarianza de 0,02
también posee un límite inferior de 0,03.

Para este problema se busca minimizar la varianza del rendimiento de la cartera de

tal modo que el inversionista, invierta una cierta cantidad de dinero sin el riesgo de
perderlo.
Se hace el modelo de este problema el cual queda así:

Min z =0.09 x 12 +4 x 1 x2 +0.06 x 22

S . A . : x 1+ x2 =1
0.06 x 1+ 0.02 x 2 ≥0.03
x 1 ≤ 0.75
x 2 ≤ 0.9
x1 , x2 ≥ 0

Procedemos a resolverlo por el método gráfico con lo cual tenemos:

 Figura 4.7 Método grafico para la solución de PNLC

Tenemos como solución que x 1=0.36 y x 2=0.64 .

Entonces multiplicamos el valor que tiene el inversionista para cada acción para así
saber cuánto debe invertir en cada acción:
x 1=10000∗0.36=3600 x 2=10000∗0.64=6400
Por lo tanto el inversionista debe invertir 3600 dólares en la acción 1 y 6400 en la
acción 2.
[Link] Problema 2
Una compañía planifica gastar 10000 euros en publicidad. Cuesta 3000 euros un minuto
de publicidad en la televisión y 1000 euros un minuto de publicidad en la radio. Si la
empresa compra x minutos de publicidad en la televisión e y minutos de publicidad en
la radio, su ingreso, en miles de euros, está dado por f ( x , y )=−2 x2 − y 2+ xy + 8 x +3 y
Plantear y resolver el problema de manera que la empresa maximice sus ingresos.

Para este problema se utilizara multiplicadores de Lagrange, teniendo como

resultado:
Max z=−2 x2− y 2+ xy + 8 x +3 y
S . A . :3 x+ y=10
x , y ≥0

L ( x , y , λ )=¿−2 x 2− y2 + xy +8 x +3 y + λ ( 10−3 x− y )

∂l
=−4 x + y +8−3 λ=0 y =4 x−8+3 λ
∂x
∂l
=−2 y + x +3−λ=0 x =2 y −3+ λ
∂y
∂l
=10−3 x− y=0
∂λ

y=4 ( 2 y−3+ λ )−8+ 3 λ x=2 ( 4 x −8+3 λ ) −3+ λ

7 y=20−7 λ 7 x=19−7 λ
20 19
y= −λ x= −λ
7 7

10−3 ( 207 −λ )−( 207 −λ )=0 1=4 λ λ= 14

 20 1 19 1
y= − x= −
7 4 7 4
73 69
y= x=
28 28

4.2.3 PROBLEMAS DE INVESTIGACIÓN

[Link] Problema de investigación 1
Quadratic Programming for Nonlinear Regression - Programación cuadrática para la regresión no
lineal

Métodos recientes de la programación cuadrática son capaces de optimizar una amplia

clase de valores cuadráticos dentro de las restricciones de desigualdad lineal. En general,
puede haber un número infinito de soluciones o un número ilimitado de solución o una
matriz numéricamente singular. La no negatividad suele imponerse a la solución, en
Además de otras limitaciones. Sin embargo, hay algunas aplicaciones, en particular la
regresión no lineal, en que se puede garantizar una solución única.
 Figura 4.8 Planteamiento de problema de investigación 1

Figura 4.9 Representación gráfica problema de investigación 1

[Link] Problema de investigación 2
Efficient Secure Outsourcing of Large-scale Quadratic Programs - Outsourcing Seguro y Eficaz de
programación cuadratica a Gran Escala

La enorme cantidad de datos que está siendo La sociedad tiene el potencial de promover el
conocimiento científico e impulsar las innovaciones. Sin embargo, a menudo la gente
carece de suficiente recursos computacionales para analizar sus datos a gran escala de
manera rentable y oportuna. Ofertas de cloud computing acceso a vastos recursos de
computación en una base de pago por uso, que es una forma práctica para analizar sus
enormes conjuntos de datos. Sin embargo, dado que sus datos información confidencial que
debe mantenerse en secreto para fines éticos, seguridad, o razones legales, muchas personas
son renuentes a adoptar el cloud computing. Por primera vez en la literatura, proponemos
un algoritmo de outsourcing seguro para grandes programas cuadráticos (QPs), que es uno
de los más fundamentales problemas en el análisis de datos. Específicamente, basado en
operaciones de álgebra lineal simple.

4.2.4 PROBLEMAS PROPUESTOS

[Link] Problema propuesto 1
Objetivos:
 Identificar los componentes básicos en el planteamiento de un problema de
programación no lineal cuadrática.
 Resolver un ejercicio típico de programación no lineal cuadrática con la
ayuda de un software especializado.

Enunciado:

Se desea realizar un análisis de portafolio de las tres firmas de abogados en Colombia

mejor ubicadas con respecto al valor contable y sus dividendos por sus acciones comunes
durante los últimos tres años.
La información se resume en la siguiente tabla:

Firma de Abogados 2014 2015 2016

 Lloreda Camacho & Co 0.81 0.60 0.18
Brigard & Urrutia 0.42 0.29 0.27
Cavelier Abogados 0.11 0.10 0.12
Tabla 4.2 Análisis de portafolio Ejercicio propuesto 1

Se debe tomar en cuenta la fórmula para el cálculo de la varianza y la covarianza.

Cálculo de la varianza:

Cálculo de la covarianza

Solución:

1
Paso 1 2
σ 11 =
3
[ (0.81)2 +(0.60)2( 0.18)2 ] − 19 [ 0.81+0.60+0.18 ]2

Se Calculan las varianzas.

2
σ 11 =0.0686

1 1 2
σ 222= [ (0.42)2+(0.29)2 (0.27)2 ]− [ 0.42+0.29+ 0.27 ]
3 9

σ 222=¿0.00442
 1
2
σ 33 =
3
[(0.11)2 +(0.10)2 ( 0.12)2 ]− 19 [ 0.11 +0.10+0.12 ] 2

2
σ 33 =0.000066

Paso 2

1 1
σ 12= [ ( 0.81∗0.42 ) + ( 0.60∗0.29 ) +(0.18∗0.27) ]− [ 0.81+0.60+0.18 ][ 0.42+ 0.
3 9
Se calculan las covarianzas.

σ 12=¿0.014466

1 1
σ 13 = [ ( 0.81∗0.11 )+ ( 0.60∗0.10 )+(0.18∗0.12) ]− [ 0.81+0.60+0.18 ][ 0.11+0.1
3 9

σ 13 =−0.0014

1 1
σ 23= [ ( 0.42∗0.11 )+ ( 0.29∗0.10 )+(0.27∗0.12) ]− [ 0.42+0.29+0.27 ] [ 0.11+ 0.1
3 9

σ 23=−000066
Paso 3

σ 211 σ 12 σ 13
Realizar la matriz de varianzas
y covarianzas
(
M 3= σ 21 σ 222 σ 23
σ 31 σ 32 σ 233 )
0.0686 0.014466 −0.0014
(
M 3= 0.014466 0.00442 −000066
−0.0014 −000066 0.000066 )
Paso 4 Lloreda Camacho & Co

0.81+0.60+0.18
=0.53
3
Se realizan los cálculos de la
rentabilidad de los
dividendos. Brigard & Urrutia

0.42+0.29+0.27
=0.3266
3

Cavelier Abogados

0.11+0.10+ 0.12
=0.11
3
Paso 5

Min:

Determinar el sistema de
ecuaciones. z=(0.0686∗Lloreda)2 +(0.00442∗Brigard)2 +( 0.000066∗Cavelier )2+ ( 0.01446

SA:

0.53∗Lloreda+0.3266∗Brigard +0.11∗Caveliar ≥ 30000

Lloreda+ Brigard+Caveliar =30000

Paso 6

Resolver el problema por

medio del software GAMS
 Figura 4.10 Código en GAMS para el desarrollo del problema propuesto 1

Figura 4.11 Desarrollo en GAMS para el problema propuesto 1

Resultado análisis de portafolio

La mayor varianza es 0.0686, corresponde a Lloreda Camacho & Co, es decir los
dividendos por sus acciones que pagaron los últimos años son dispersos y generan mayor
riesgo.
La menor varianza es 0.000066, corresponde a Cavelier Abogados, es decir los dividendos
por sus acciones que pagaron los últimos años poseen una menor dispersión y generan
menor riesgo.

Si los dividendos de Lloreda Camacho & Co suben o bajan, los dividendos de Brigard &
Urrutia también suben o bajan.

Si los dividendos de Lloreda Camacho & Co suben, los dividendos de Cavelier Abogados
bajan o si los dividendos de Lloreda Camacho & Co bajan, los dividendos de Cavelier
Abogados suben.

Si los dividendos de Brigard & Urrutia suben, los dividendos de Cavelier Abogados bajan o
si los dividendos de Brigard & Urrutia bajan, los dividendos de Cavelier Abogados suben.

En este portafolio donde participan las tres firmas de abogados con respecto al valor
contable, la empresa que ofreció el mejor dividendo fue Lloreda Camacho & Co con 0.53,
lo siguen Brigard & Urrutia con 0.3266 y por ultimo Cavelier Abogados con 0.11.

[Link] Problema propuesto 2

Una compañía produce artículos de vidrio de alta calidad que incluyen ventanas x1 y
puertas x2, debido a costos de producción, factores externos y otros, las utilidades se dan de
una forma no lineal, asi que la función a maximizar es:

Sujeto a:
Utilizando los multiplicadores de Lagrange

Y finalmente linealizando el problema

La solución correspondiente, acomodando todo:

[Link] Problema propuesto 3

Se busca realizar un análisis de cartera de inversión para la empresa textil Ónix Industry
para realizar inversiones de manera estable, en base a las empresas de distribución que sean
más rentables para realizar inversiones, teniendo como capital base 30’000.000 de pesos, y
una rentabilidad esperada del 14%.

En la siguiente tabla se tiene los dividendos por acción (DPA) de cada una de las empresas
en los últimos cuatro años:

Empresa\Año (DPA) 2013 2014 2015 2016

[Link] Tex SAS 1.6 1.4 1.8 2.2
Comercializadora T y M 2.3 1.5 2.0 1.8
Daccach Hermanos 1.3 2.1 1.6 2.3
(Agencia)
Manufacturas Fulef SAS 2.0 1.8 2.4 2.2

Tabla 4. 1. Análisis de portafolio Ejercicio propuesto 3

Formula de Covarianza:

p p p
1 1
2
σ = ∑ X i X j− 2
ij
p k =1 p (∑ )(∑ )
k=1
Xi
k=1
Xj

[Link] de Varianzas:

p p 2
1
σ ii2= ∑ X 2− 1
p k=1 i p 2 ( )
∑ Xi
k =1

2 1 1
σ 11 = ( 1.62 +1.4 2+1.8 2+ 2.22) − ( 1.6+1.4 +1.8+2.2 )2=0.0875
4 16

1 1
σ 222= ( 2.32+1.5 2+2.0 2+1.8 2 )− ( 2.3+1.5+2.0+ 1.8 )2=0.0850
4 16

2 1 1
σ 33 = ( 1.32+ 2.12+1.6 2+2.3 2 )− ( 1.3+2.1+1.6+2.3 )2=0.1569
4 16

1 1
σ 244= ( 2.02 +1.82 +2.4 2+ 2.22) − ( 2.0+1.8+2.4 +2.2 )2=0.05
4 16

2. Calculo de Covarianzas:
 1 1
σ❑
12 = ( 1.6∗2.3+1.4∗1.5+1.8∗2.0+2.2∗1.8 ) − ( 1.6+1.4 +1.8+2.2 ) ( 2.3+1.5+2.0+1.8 ) =0.010
4 16

σ❑
12 =0.010 σ ❑21=0.0100 σ❑
31 =0.0463

σ ❑41=0.0450

σ❑
13 =0.0463 σ ❑23=−0.0975 σ❑
32 =−0.0975

σ ❑42=0.0250

σ❑
14 =0.0450 σ ❑24=0.0250 σ❑
34 =−0.0125

σ ❑43=−0.0125

3. Matriz de Varianza y Covarianza:

0.0875 0.0100 0.0463 0.0450

M=
[
0.0100 0.0850 −0.0975
0.0463 −0.0975 0.1569
0.0450 0.0250 −0.0125
0.0250
−0.0125
0.0500
]
[Link] Objetivo:

Z=
2
σ 11 X 211 +σ 12 X 1 X 2+ σ 13 X 1 X 3+ σ 14 X 1 X 4 +σ 21 X 2 X 1 +σ 222 X 222+ σ 23 X 2 X 3+ σ 24 X 2 X 4 +σ 31 X 3 X 1 +σ 32 X 3 X 2 +σ 233 X 233+

Z=

0.0875 X 211 + 0.0100 X 1 X 2+ 0.0463 X 1 X 3+ 0.0450 X 1 X 4 +0.0100 X 2 X 1 +0.0850 X 222−0.0975 X 2 X 3 +0.0250 X 2 X

[Link]:

- Ŕ1 X 1 + Ŕ2 X 2+ Ŕ 3 X 3+ Ŕ 4 X 4 ≥ R p

( 1.6+1.4+ 1.8+2.2 )
Ŕ1= =1.75
4
 ( 2.3+1.5+2.0+1.8 )
Ŕ2= =1.9
4

( 1.3+2.1+1.6+2.3 )
Ŕ3= =1.825
4

( 2.0+1.8+2.4+ 2.2 )
Ŕ4 = =2.1
4

R p =30' 000.000∗0.09=4 ' 200.000

 1.75 X 1 +1.9 X 2 +1.825 X 3 +2.1 X 4 ≥ 4 ´ 200.000

 X 1 + X 2+ X 3 + X 4 =30 ´ 000.000

6. Problema Final:

min Z=

0.0875 X 211 + 0.0100 X 1 X 2+ 0.0463 X 1 X 3+ 0.0450 X 1 X 4 +0.0100 X 2 X 1 +0.0850 X 222−0.0975 X 2 X 3 +0.0250 X 2 X

S.A: 1.55 X 1 +1.9 X 2 +1.82 X 3+ 2.1 X 4 ≥ 4 ´ 200.000

X 1 + X 2+ X 3 + X 4 =30 ´ 000.000

Xi ≥ 0

7. Solución por AMPL:

Por tanto, las inversiones a ser realizadas son:

 1ra: 0 = 0 pesos = 0%
 2da: 1.74685 = 17’468.500 pesos = 58.228%
 3ra: 1.25315=12’531.500 pesos= 41.772%
 4ta: 0 = 0 pesos = 0%
 Con un riesgo de 7.89 %

Con lo que se alcanzan las expectativas, junto con un riesgo bajo.

PARTE III. CIERRE DE LA INVESTIGACIÓN

4.3 RESULTADOS Y DISCUSIÓN

Se consiguió obtener el conocimiento, tanto de manera general como especifica de la
programación no lineal, más específicamente de la programación no lineal cuadrática,
tomando desde los acontecimientos históricos, los cuales nos dan una idea de dónde y cómo
surgen esta rama de la investigación de operaciones, y los algoritmos los cuales son usados
para la solución de problemas de este tipo, viendo como la evolución de la industria crea la
necesidad del surgimiento de este tipo de algoritmos.

Cada algoritmo fue estudiado y profundizado con ejemplos y ejercicios, tanto clásicos
encontrados en la literatura, como ejercicios propuestos enfocados en una aplicación
específica, utilizando los conocimientos obtenidos en clase y lo investigado para su
solución, junto a diferentes softwares disponibles para la solución de problemas de
investigación de operaciones, como los ya vistos anteriormente, los cuales facilitan en gran
medida el desarrollo de cada problema cuando la complejidad de este es relativamente alta.

Se aprendió como realizar el modelamiento de un problema de programación no lineal

cuadrática dependiendo del escenario, ya sea de análisis de portafolio, oferta pública o
cualquiera de las posibilidades.

4.4 CONCLUSIONES

4.4.1 Verificación, contraste y evaluación de los objetivos

La programación no lineal cuadrática nos permite resolver problemas que se salen de la
linealidad y se deben modelar mediante una función objetivo de tipo cuadrático que se
adaptan más a algunas situaciones del mundo industrial como pueden ser en ámbitos de
producción o económicos cuya representación matemática debe ser de este tipo.

La necesidad de avanzar y suplir sus necesidades ha hecho que el hombre realice

importantes avances científicos y la guerra ha acelerado estos, de aquí surge la
investigación de operaciones y posteriormente con los avances industriales y la
complejidad de los modelos y situaciones también la programación no lineal,
específicamente la programación no lineal cuadrática.

Existen diversos algoritmos de solución para una gran cantidad de modelos que pueden
presentarse en la PNLC que varían según su complejidad y pueden generar una solución
rápidamente o algunos requiere una sucesión de pasos más compleja o tediosa pero
permiten llegar a la solución óptima que requiere el problema.

4.4.2 Aportes originales

Vimos cómo funciona la programación cuadrática, que busca una linealizacion en forma
matricial, pero que pasaría donde se aumentara el exponente máximo, se requerirían más
dimensiones, se usarían los llamados tensores (matriz de n dimensiones), lo mismo en la
forma de solución, no se llamaría matriz ampliada sino tensor ampliado, puede que un
matemático haya desarrollado la teoría, pero no conocemos ningún ingeniero que lo haya
aplicado, esto generalizaría el concepto de programación cuadrática a un nuevo tipo de
programación no lineal, y aumentamos la apuesta, deben existir equivalencias para las
multiplicaciones con valores exponenciales y valores logarítmicos, sabemos que hay un
campo por explotar.