Programacion No lineal Fraccional

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:

1. 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.
2. 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.
3. 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.  

...