Programación Cuadrática-Entera y Análisis de Sensibilidad

PROGRAMACIÓN CUADRÁTICA

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 es debida a que un gran número de problemas aparecen de forma natural como cuadráticos (optimización por mínimos cuadrados, con restricciones lineales), pero además es importante porque aparece como un subproblema frecuentemente para resolver problemas no lineales más complicados. Las técnicas propuestas para solucionar los problemas cuadráticos tienen mucha similitud con la programación lineal.

Específicamente cada desigualdad debe ser satisfecha como igualdad. El problema se reduce entonces a una búsqueda de vértices exactamente igual que se hacía en programación lineal.

Donde c es un vector de coeficientes constantes; A es una matriz (m x n) y se asume, en general que Q es una matriz simétrica.

Dado que las restricciones son lineales y presumiblemente independientes la cualificación de las restricciones se satisface siempre, así pues, las condiciones de Karush-KuhnTucker son también condiciones suficientes para obtener un extremo, que será además un mínimo global si Q es definida positiva. Si Q no es definida positiva el problema podría no estar acotado o llevar a mínimos locales.

La Programación Cuadrática juega un papel muy relevante en la teoría de optimización lineal y no lineal pues guarda una relación muy estrecha con la Programación Lineal y es un paso intermedio esencial para resolver eficazmente problemas generales de Programación No Lineal.

¿Para qué se usa?

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

Problemas cuadráticos de minimización sin restricciones, requieren minimizar la función cuadrática f (x) sobre el espacio completo.

Problemas cuadráticos de minimización sujetos a restricciones de igualdad, requieren minimizar la función objetivo f (x) sujeta a restricciones lineales de igualdad Ax = b. 

Problemas cuadráticos de minimización sujetos a restricciones lineales de desigualdad. Requieren minimizar la función objetivo f (x) sujeta a restricciones lineales de desigualdad Ax = b, también puede contener restricciones de igualdad. 

Problemas de optimización de redes cuadráticas. Son problemas cuadráticos en los que las restricciones son restricciones de baja conservación sobre una red pura generalizada.

Problemas cuadráticos convexos. Son cualquiera de los mencionados arriba, en el cual la función objetivo a ser minimizada, f (x) es convexa.

Problemas cuadráticos no convexos. Son cualquiera de los mencionados arriba, en el cual la función objetivo a ser minimizada, f (x) es no convexa. 

Problemas de complementariedad lineal. Son problemas especiales con un sistema de ecuaciones en variables no negativas, en el cual las variables están formadas en varios pares llamados pares complementarios.

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. Para la programación cuadrática se pueden encontrar mínimos locales, mínimos globales, puntos estacionarios o de KKT, (son los que satisfacen las condiciones de KKT del problema).

PROGRAMACIÓN ENTERA

Un modelo de programación entera es aquel que contiene restricciones y una función objetivo idénticas a la formulada en programación lineal, la única diferencia en que una o más variables de decisión deben tomar valor entero en la solución final.

CLASIFICACIÓN:
Existen tres tipos de modelos por programación entera

• PURA : Son modelos similares a los de programación entera

Forma General:

Max (Min) = A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn

Sujeto a: A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn >= (<=)(=) Bi

No negatividad: Xi >= 0 y ENTERO

• BINARIA : Estos modelos lineales , las variables sólo toman valores 0 y 1, son usadas para uso probabilístico Donde 0 se rechaza la opción y 1 se acepta la opción

Forma General:

Max (Min) = A1Y1+A2Y2+A3Y3+A4Y4+A5Y5+..........+AnYn

Sujeto a: y1+y2+y3+y4+..........+yn >= (<=)(=) Bi

No negatividad: yi >= 0 v 1

• MIXTA : En estos tipos de modelos , integra las variables puras y las mixtas

Max (Min)=

A1X1+A2X2+A3X3+A4X4+A5X5+.....+AnXn+A1Y1+A2Y2+A3Y3+A4Y4+A5Y5+.....+AnYn

Sujeto a:

A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn >= (<=)(=) Bi

y1+y2+y3+y4+..........+yn >= (<=)(=) Bi

No negatividad:

Xi >= 0 y ENTERO

 Xi >= 0 v 1

ANÁLISIS DE SENSIBILIDAD

Análisis de Sensibilidad, llamado también Análisis de Post-optimización, es una de las partes más importantes en la programación lineal, es utilizada para tomar en consideración los cambios que pueden ocurrir en los elementos componentes del modelo que consiste en determinar qué tan sensible es la respuesta óptima del método simplex, al cambio de algunos datos como las ganancias o costos unitarios (coeficientes de la función objetivo) o la disponibilidad de los recursos (términos independientes de las restricciones), que se refieren a permutas en coeficientes, variables, restricciones y Función Objetivo.

Objetivo principal del análisis de sensibilidad:

• Establecer un intervalo de números reales en el cual el dato que se analiza puede estar contenido, de tal manera que la solución sigue siendo óptima siempre que el dato pertenezca a dicho intervalo

• Investigar el cambio en la solución óptima del problema, cuando se producen cambios en los parámetros del modelo

Ejemplo Para Resolver Mediante Método Simplex

Resolver mediante el método simplex el siguiente problema:

Maximizar	Z = f(x,y) = 3x + 2y
sujeto a:	2x + y ≤ 18
	2x + 3y ≤ 42
	3x + y ≤ 24
	x ≥ 0 , y ≥ 0

Se consideran las siguientes fases:

1. Convertir las desigualdades en igualdades

Se introduce una variable de holgura por cada una de las restricciones del tipo ≤, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:

2x + y + r = 18

2x + 3y + s = 42

3x +y + t = 24

2. Igualar la función objetivo a cero

- 3x - 2y + Z = 0

3. Escribir la tabla inicial simplex

En las columnas aparecerán todas las variables básicas del problema y las variables de holgura/exceso. En las filas se observan, para cada restricción las variables de holgura con sus coeficientes de las igualdades obtenidas, y la última fila con los valores resultantes de sustituir el valor de cada variable en la función objetivo, y de operar tal como se explicó en la teoría para obtener el resto de valores de la fila:

Tabla I . Iteración nº 1
			3	2	0	0	0
Base	Cb	P0	P1	P2	P3	P4	P5
P3	0	18	2	1	1	0	0
P4	0	42	2	3	0	1	0
P5	0	24	3	1	0	0	1
Z		0	-3	-2	0	0	0

4. Condición de parada

Cuando en la fila Z no existe ningún valor negativo, se ha alcanzado la solución óptima del problema. En tal caso, se ha llegado al final del algoritmo. De no ser así, se ejecutan los siguientes pasos.

5. Condición de entrada y salida de la base

1. Primero debemos saber la variable que entra en la base. Para ello escogemos la columna de aquel valor que en la fila Z sea el menor de los negativos. En este caso sería la variable x (P1) de coeficiente - 3. Si existiesen dos o más coeficientes iguales que cumplan la condición anterior (caso de empate), entonces se optará por aquella variable que sea básica.

La columna de la variable que entra en la base se llama columna pivote (En color verde).

2. Una vez obtenida la variable que entra en la base, estamos en condiciones de deducir cual será la variable que sale. Para ello se divide cada término independiente (P0) entre el elemento correspondiente de la columna pivote, siempre que el resultado sea mayor que cero, y se escoge el mínimo de ellos.

En nuestro caso: 18/2 [=9] , 42/2 [=21] y 24/3 [=8] Si hubiera algún elemento menor o igual a cero no se realiza dicho cociente, y caso de que todos los elementos de la columna pivote fueran de ésta condición tendríamos una solución no acotada y terminaríamos el problema.

El término de la columna pivote que en la división anterior dé lugar al menor cociente positivo, el 3, ya que 8 es el menor cociente, indica la fila de la variable de holgura que sale de la base, t (P5). Esta fila se llama fila pivote (En color verde).

Si al calcular los cocientes, dos o más son iguales (caso de empate), se escoge aquella que no sea variable básica (si es posible).

3. En la intersección de la fila pivote y columna pivote tenemos el elemento pivote, 3.

6. Encontrar los coeficientes de la nueva tabla.

Los nuevos coeficientes de la fila pivote, t (P5), se obtienen dividiendo todos los coeficientes de dicha fila entre el elemento pivote, 3, que es el que hay que convertir en 1.

A continuación mediante la reducción gaussiana hacemos ceros los restantes términos de su columna, con lo que obtenemos los nuevos coeficientes de las otras filas incluyendo los de la función objetivo Z.

También se puede hacer de la siguiente manera:

Fila del pivote: Nueva fila del pivote = (Vieja fila del pivote) / (Pivote) Resto de las filas: Nueva fila = (Vieja fila) -(Coeficiente de la vieja fila en la columna de la variable entrante) x (Nueva fila del pivote) Veámoslo con un ejemplo una vez calculada la fila del pivote (fila de x (P1) en la Tabla II): Vieja fila de P4 42 2 3 0 1 0 - - - - - - Coeficiente 2 2 2 2 2 2 x x x x x x Nueva fila pivote 8 1 1/3 0 0 1/3 = = = = = = Nueva fila de P4 26 0 7/3 0 1 -2/3

Tabla II . Iteración nº 2
			3	2	0	0	0
Base	Cb	P0	P1	P2	P3	P4	P5
P3	0	2	0	1/3	1	0	-2/3
P4	0	26	0	7/3	0	1	-2/3
P1	3	8	1	1/3	0	0	1/3
Z		24	0	-1	0	0	1

Se puede observar que no hemos alcanzado la condición de parada ya que en los elementos de la última fila, Z, hay uno negativo, -1. Hay que repetir el proceso:

1. La variable que entra en la base es y (P2), por ser la variable que corresponde a la columna donde se encuentra el coeficiente -1.
2. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote: 2 / 1/3 [=6] , 26 / 7/3 [=78/7] y 8 / 1/3 [=24] y como el menor cociente positivo es 6, tenemos que la variable que sale es r (P3).
3. El elemento pivote, que ahora hay que hacer 1, es 1/3.

Operando de forma análoga a la anterior obtenemos la tabla:

Tabla III . Iteración nº 3
			3	2	0	0	0
Base	Cb	P0	P1	P2	P3	P4	P5
P2	2	6	0	1	3	0	-2
P4	0	12	0	0	-7	1	4
P1	3	6	1	0	-1	0	1
Z		30	0	0	3	0	-1

Como en los elementos de la fila Z hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:

1. La variable que entra en la base es t (P5), por ser la variable que corresponde al coeficiente -1.
2. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote: 6/(-2) [=-3] , 12/4 [=3], y 6/1 [=6] y como el menor cociente positivo es 3, tenemos que la variable que sale es s (P4).
3. El elemento pivote, que ahora hay que hacer 1, es 4.

Obtenemos la tabla:

Tabla IV . Iteración nº 4
			3	2	0	0	0
Base	Cb	P0	P1	P2	P3	P4	P5
P2	2	12	0	1	-1/2	1/2	0
P5	0	3	0	0	-7/4	1/4	1
P1	3	3	1	0	3/4	-1/4	0
Z		33	0	0	5/4	1/4	0

Se observa que en la última fila todos los coeficientes son positivos, por lo tanto se cumple la condición de parada, obteniendo la solución óptima.

La solución óptima viene dada por el valor de Z en la columna de los valores solución, en nuestro caso: 33. En la misma columna se puede observar el punto donde se alcanza, observando las filas correspondientes a las variables de decisión que han entrado en la base: (x,y) = (3,12)

CONCLUSIÓN

Programación cuadrática y entera:

Consiste en maximizar o minimizar una función a través de un modelo matemático extraído de un problema real que posea cualquier organización. 

La función que se va a minimizar o maximizar esto quiere decir la manera óptima en que un problema puede ser resuelto y esto a su vez minimiza costos y maximiza las ganancias. Estos problemas vienen dados por funciones objetivo que son las que vamos a maximizar o minimizar y por algunas restricciones dadas por el contexto del problema, las restricciones pueden ser con o sin potencia, es decir, con exponente o sin el 

Las que poseen exponente se llaman PROGRAMACIÓN CUADRÁTICA y las que no poseen exponente se llaman PROGRAMACIÓN ENTERA, cada una de estas tiene su forma particular de resolver

Algunos Link de Interes

http://www.phpsimplex.com/simplex/simplex.htm

http://ingenierosindustriales.jimdo.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/problemas-de-asignaci%C3%B3n/