Programacion No lineal Fraccional
diego nicolas ramos zamudioApuntes15 de Abril de 2021
3.137 Palabras (13 Páginas)719 Visitas
PROGRAMACIÓN NO LINEAL FRACCIONAL
INTRODUCCIÓN
La programación no lineal fraccionaria(PNLF), también conocida como problemas hiperbólicos o de optimización de proporciones, es una caso especial de programación matemática no lineal, en la cual se encuentran proporciones entre las funciones de un conjunto convexo; cuando la función objetivo de un problema está compuesta por un cociente de dos funciones lineales y las restricciones generar un polígono convexo de factibilidad a este tipo de problemas se le conoce como programación lineal fraccional, es un método de optimización aplicado principalmente a problemas de corte de rollos, inversión de fondos, inventario, teoría de juegos, teoría de la información y problemas estocásticos.
PARTE I. CONTEXTUALIZACIÓN DE LA INVESTIGACIÓN
6.1. DESCRIPCIÓN DE LA INVESTIGACIÓN
6.1.1. OBJETIVOS DE LA INVESTIGACIÓN
6.1.1.1 Objetivo General
Presenta una descripción general de la programación no lineal fraccionaria, definiendo los tipos de problemas que trata y su aplicación en casos prácticos.
6.1.1.2 Objetivo Específicos
- Investigar problemas prácticos, en donde la solución óptima está dada por un planteamiento de programación no lineal fraccionaria.
- Brindar herramientas para el planteamiento de problemas de PNLF y ofrecer pautas para su desarrollo.
- Demostrar que la aplicación de la PNLF en diferentes áreas es una buena práctica para la resolución de problemas reales.
6.1.2 REVISIÓN TEÓRICA
6.1.2.1. Historia
La programación no lineal fraccional tiene sus inicios en trabajos publicados en la década del 50 con el trabajo publicado por Isbell y Marlow (1956) en que identificaron un problema de PNLF y lo resolvieron con una secuencia de problemas de programación lineal años más tarde; Charnes y Cooper (1962), proponen un método en el que se formula un nuevo problema lineal a partir de una transformación de variables del problema original. Otros aportes para resaltar son los de Gilmore and Gomory (1963), Martos (1964), Swarup (1965), Wagner and Yuan (1968), Pandey and Punnen (2007) and Sharma et al. (1980) quienes propusieron soluciones basadas en el método simplex. El método de Bitran y Novaes (1973), presenta como ventaja que no requiere la transformación de variables ni la introducción de nuevas variables y restricciones sino que se basa en la actualización de la función objetivo.
Tantawy (2007, 2008) hizo dos propuestas un enfoque sobre dirección factible un enfoque sobre dualidad en PLF, otros estudios de dualidad y sensibilidad fueron hechos por Bitran y MagnanteI (1976). Mojtaba Borza et al. (2012) propusieron soluciones a problemas de PLF con un intervalo de coeficientes en la función objetivo, todo basado en el método de Charnes y Cooper.
El caso de tener unas restricciones lineales y con una función objetivo es el cociente de una función convexa y una función cóncava es resuelta por Mangasarian (1969) utilizando el algoritmo de Frank and Wolfe (1956). Dinkelbach (1968) considera también el mismo objetivo sobre un conjunto factible convexo y su método de solución consistía en resolver este problema mediante la solución de una secuencia de problemas de programación no-lineal convexas
Entre los últimos estudios se encuentran los de de la programación no lineal fraccional de múltiples objetivos realizados por Gupta y Bhatia (2001), Guzel y Sivri (2005), Kornbluth y Steur (1981), Nikowski i Zolkiski (1985) Saad (2007).
6.1.2.2 Desarrollo
La mayoría de los problemas PNLF siguen una estructura básica como la siguiente:
[pic 1]
[pic 2]
[pic 3]
[pic 4]
El subconjunto S presenta unas características importantes de mencionar:
- Si f es no negativa y g es estrictamente positiva, entonces F=f/g es quasicóncava en S y debido a esto un máximo local es a su vez un máximo global.
- Si f y g son diferenciables, entonces F=f/g es pseudocóncava y debido a esto un punto que satisface las condiciones de optimalidad de Kuhn-Tucker es a su vez un máximo global.
- Para un problema de programación lineal fraccionaria, como la función objetivo es quasicóncava, si la región factible es cerrada, el máximo o mínimo se halla en uno de los puntos extremos de la región.
Para los problemas específicos de programación lineal fraccionaria desde hace un tiempo se han planteado varios métodos de solución, entre los que más destacan se pueden nombrar los propuestos por:
- Isbell and Marlow
- Gilmore and Gomory
- Martos
- Swarup
- Charnes and Cooper
- Jagannathan
- Dinkelbach
Por otra parte, entre algunos métodos de solución para programación no lineal fraccionaria están:
- Jagannathan
- Swarup
- Dinkelbach
- Bector
- Mangasarian
- Almogy and Levin
Dualidad en la Programación No Lineal Fraccionaria:
Los problemas de tipo dual de programación lineal fraccionaria presentan el inconveniente de que el dual de un problema de programación fraccionaria, no es necesariamente de tipo fraccionario, usualmente es más complicado que el problema primal y no ofrece ventajas computacionales, aunque si aporta en medir la sensibilidad el valor máximo de la función objetivo primal. Los estudios han concluido que el dual de un problema de programación lineal fraccionaria es un problema lineal.
Programación Fraccionaria Cuadrática:
Un problema de programación fraccionaria es denominado de tipo cuadrático si la función del numerador N(x) y la función del denominador D(x) son cuadráticas y el subconjuntos es un poliedro convexo.[pic 5]
Programación Fraccionaria Homogénea:
Considera los problemas de maximizar un cociente de funciones convexas y cóncava, ambas funciones son homogéneas de grado uno y tienen una constante adicional, están sujetas a restricciones lineales o no lineales.
Programación Fraccionaria Multiobjetivo:
Trata los problemas en el que se busca optimizar varios objetivos simultáneamente los cuales normalmente están en conflicto, en ellos se encuentran varias funciones objetivo. La forma general de los problemas de este tipo es la siguiente:[pic 6]
Figura 6.1 ecuación función multiobjetivo.
6.1.2.3. Conceptualización
Los problemas de programación no lineal fraccionaria, presentan las características generales de tener restricciones lineales, convexas y no negativas y la función objetivo es cóncava cuando el objetivo es maximizar y convexa cuando se pretende minimizar.
Algunos de los algoritmos más utilizados para solucionar este tipo de problemas son:
- Método de Charnes y Cooper:
En 1962 Charnes y Cooper proporcionaron un método de transformación lineal para la conversión de problemas de optimización caracterizados por una función fraccional, es decir ( ), con restricciones lineales, el propósito de este método es transformar la función objetivo fraccional a lineal para poder resolverla por método de programación lineal.[pic 7]
[pic 8]
S.A:
[pic 9]
[pic 10]
Para poder resolver un problema por este método se deben de seguir lo siguientes pasos:
Paso 1: dela función objetico identificar los vectores C y D que están conformador por los valores correspondientes en la función que multiplican a las variables X.
Paso 2: formar las matrices A y B por ejemplo, se utilizara las siguientes restricciones:
[pic 11][pic 12]
[pic 13]
[pic 14][pic 15]
Paso 3: se hace el cambio para convertirlo en un problema de programación lineal:
[pic 16][pic 17][pic 18]
Paso 4: la nueva función objetivo se forma de la siguiente manera:
[pic 19]
S.A:
[pic 20]
[pic 21]
[pic 22]
Por último se puede resolver por cualquier método de programación lineal, incluso utilizando un software para ello
- Algoritmo Dinkelbach' S
La programación fraccional general puede ser formulada como la siguiente problema:
[pic 23]
Donde X es un compacto no vacío de R n . Las funciones Φ ( x ) y Ψ ( x ) Son funciones continuas de valor real de x ∈ X. Además, las siguientes Se asume también:
...