Aplicación de la Investigación de Operaciones y la Programación Matemática
Enviado por Ing.+Lic. Yunior Andrés Castillo S.
Orígenes
Enfoque Sistémico: A raíz de la revolución industrial las pequeñas empresas que evolucionaron crecieron en tamaño y complejidad, conllevando a una división del trabajo y la separación de las responsabilidades administrativas en las llamadas ahora organizaciones; esto genero grandes beneficios pero también problemas como lo la tendencia de muchos de sus componentes en convertirse en autónomos con sus propias metas inclusive valores, perdiendo la visión de que deben de estar al servicio de la propia organización. Así lo que es mejor para un componente puede ir en deterioro de otro y así afectar el objetivo común dentro de la organización.
Un problema adicional es que conforme crece la complejidad y la especialización, es más difícil asignar los recursos de manera eficiente dentro de los componentes de la organización sin perder de vista a esta como un todo.
Inicios: Sus inicios se atribuyen a los servicios militares en la segunda guerra mundial Gran Bretaña, donde era imperioso asignar recursos escasos a las diferentes operaciones militares y a las actividades dentro de cada operación en forma efectiva. Este tipo de problemas, y la necesidad de encontrar la mejor manera de resolverlos, proporcionaron el ambiente adecuado para el surgimiento de la IO, caracterizándose por el uso del conocimiento científico través del esfuerzo de equipos interdisciplinarios.
El origen de su nombre investigación de operaciones fue dado aparentemente porque el servicio Británico de inteligencia contrato unos grupos de científicos para investigar operaciones militares.
En particular, el proceso comienza por la observación cuidadosa y la formulación del problema incluyendo la recolección de datos. El siguiente paso es la construcción de un modelo científico (generalmente matemático) que intenta abstraer las partes más relevantes o esenciales del problema (real) en estudio. Aquí e supone (hipótesis) que el modelo copia el problema lo suficiente como para que las conclusiones (soluciones) que se obtengan sean también válidas para el problema real. Después es necesario llevar a cabo experimentos probar la hipótesis, modificarla y eventualmente verificarla
Modelado
Básicamente el estudio investigación de operaciones se basa en construir un modelo de la situación física, siendo un modelo de investigación de operaciones una representación idealizada (simplificada) de un sistema de la vida real (existente o no). La complejidad de un sistema real resulta de un gran número de elementos (variables) que controlan el comportamiento del sistema. Sin embargo solo una parte de las variables (afortunadamente) dictan o dominan el comportamiento del sistema. Entonces el modelar es concentrarse en identificar las variables y relaciones dominantes que lo gobiernan.
Ejemplo:
Un producto manufacturado típicamente lleva un número de operaciones desde que se concibe por el diseñador hasta que llega al consumidor.
Objetivo: Nivel de Producción en la planta.
Variables:
1. Departamento de producción: horas-máquina, horas-hombre, sucesión específica de operaciones en cada máquina, número de artículos defectuosos producidos, tasa de inspección.
2. Departamento de Materiales: Cantidad disponible de material, limitantes en el almacenamiento, tasa de entrega del material comprado.
3. Departamento de Mercadeo: Pronóstico de ventas, intensidad de la campaña publicitaria, capacidad de distribución, detección de productos competitivos en el mercado.
El primer nivel de abstracción pide definir el primer sistema real supuesto, para lo cual deberemos identificar las variables dominantes y representar esa primera aproximación en función de estas. Las variables dominantes serian entonces:
a. Tasa de producción del artículo
b. Tasa de consumo
La simplificación del sistema real al sistema real supuesto se hace agrupando variable del sistema real en variables del sistema real supuesto así, las variables de los departamentos de producción y materiales se deberán considerar para establecer una tasa de producción tan real como sea posible, de igual manera con la tasa de consumo se emplearán las variables del departamento de mercadeo.
De las tasas de producción y consumo se pueden establecer entonces medidas de escasez o exceso en el inventario para un nivel de producción dado, pudiéndose crear un modelo abstraído para balancear los costos de escasez y del exceso de inventarios, no siendo este el único, se puede por ejemplo desear construir un modelo que con determinado nivel de producción tal que el inventario en exceso permanezca bajo cierto nivel máximo.
Tipos de Modelos de IO
Simbólico o matemático. Todas las variables son cuantificables, entonces las variables, sus relaciones y sus soluciones son representadas empleando símbolos, funciones y manipulación matemática respectivamente.
Solución a modelos: Matemáticos, Heurísticos y de Simulación
Simulación: Estos imitan el comportamiento de un sistema o modelo en un período de tiempo.
Etapas usuales en un estudio de I.O.
1. Definición del problema y recolección de datos.
2. Formulación del modelo matemático que represente el problema.
3. Desarrollo de un procedimiento basado en computadora para derivar una solución al problema a partir del modelo.
4. Prueba y mejoramiento del modelo.
5. Aplicación del modelo y su solución.
6. Puesta en marcha.
Satisfazar (optimizar y satisfacer).
Optimizar ( Teoría – Ciencia de lo absoluto
Satisfazar ( Realidad – arte de lo factible
Programación Lineal
Es repartir recursos limitados entre actividades competitivas de la mejor manera posible.
El modelo matemático incluye tres elementos:
Variables de decisión y parámetros: Que no son otra cosa que las variables controlables del sistema.
Restricciones: Con elles se toma en cuenta las limitaciones físicas del sistema, es decir limita las variables a sus valores factibles.
Función Objetivo: Es la manera de medir la efectividad del sistema, en términos de una función matemática de las variables de decisión.
Entonces de manera general se pueden ver como: Determinar los valores de las variables
xj, con j=1,2,…,n,
los cuales Optimizarán (Satisfazarán)
x0=f(x1,…,x2)
sujetos a
g1(x1,…,xn)( bi, i=1,2,…,m ( o ()
xi(0 j=1,2,…,N
Ej.1 Una empresa produce artículos de vidrio de alta calidad, incluyendo ventanas y puertas, posee tres plantas. Los marcos y molduras de aluminio se hacen en la planta 1, los marcos de madera se fabrican en la planta 2 y en la 3 se produce el vidrio y se ensambla los productos. Suponga que la administración ha decidido discontinuar algunos productos poco rentable y la capacidad de producción liberada se empleará en producir dos nuevos productos, donde: El producto 1 requiere parte de la capacidad de producción en las plantas 1 y 3 pero nada en la planta 2. El producto 2 solo necesita trabajo en las plantas 2 y 3. La compañía esta en capacidad de vender todos los productos que se puedan fabricar.
Definición del problema:
Determinar las tasas de producción deben tener los productos tal que maximicen las unidades totales, teniendo en cuenta las restricciones de producción (cada producto se fabricará en lotes de 20, de manera que la tasa de producción está definida como el número de lotes que se producen a la semana). ¿Qué se necesita para esto?
a. El número de horas de producción disponibles por semana en cada planta para estos productos.
b. Números de horas de producción que cada lote producido de cada producto nuevo emplea en cada una de las plantas.
c. La ganancia.
Este problema se conoce como mezcla de productos, los datos necesarios recolectados se listan a continuación:
El modelo matemático:
Max Z=3×1+5×2
Sujeto a:
x1 ( 4
2×2( 12
3×1+2×2(18
y
x1(0 , x2(0.
Este es el tipo más usual de aplicación de la programación lineal que involucra las asignaciones de recursos a ciertas actividades, donde la determinación de esta asignación implica elegir los niveles de las actividades que lograrán el mayor valor posible de la medida global de efectividad.
Convención de términos.
Ciertos símbolos se emplean para denotar las distintas componentes del modelo de programación lineal:
Z | = | Valor de la medida global de efectividad función Objetivo | ||||||||||||||||||
xj | = | Nivel de la actividad j (j=1,2,3,…,n) variables de decisión | ||||||||||||||||||
cj | = | Incremento en Z que resulta al aumentar una unidad el nivel de la actividad j | ||||||||||||||||||
bi | = | Cantidad de recurso i disponible para asignar a las actividades (i=1,2,…,m) | ||||||||||||||||||
aij | = | Cantidad de recurso i consumido por cada unidad de actividad j |
Las constantes xj, cj, bi y aij son conocidas como parámetros o coeficientes tecnológicos.
Al formular matemáticamente el problema de asignación de recursos a actividades, consiste en elegir valores de
x1, x2, … ,xn para
maximizar Z= c1x1+ c2x2+ … ,cnxn
Sujeta a las restricciones
a11x1 + a12x2 … a1nxn ( b1
a21x1 + a22x2 … a2nxn ( b2
… … … …
am1x1 + am2x2 … amnxn ( bm
y x1(0, x2(0, … ,xn(0
La forma como esta información será expresada por comodidad y para preparar su solución a través del algoritmo SIMPLEX es:
Existen variaciones al modelo antes descrito como son:
1. La función objetivo es minimizar.
2. Restricciones del tipo mayor o igual (()
3. Restricciones del tipo ecuación (=)
4. Las variables de decisión son irrestrictas en signo para algún j.
Suposiciones del Modelo de Programación Lineal
Proporcionalidad: La contribución de cada actividad al valor de la función objetivo Z es proporcional al nivel de la actividad xj, como se representa a través del término cjxj en la función objetivo. De igual forma, la contribución de cada actividad al lado izquierdo de cada restricción es proporcional al nivel de la actividad xj, en la forma que lo representa el término aijxj en la restricción. Ej.
Aditividad: Cada función en un modelo de programación lineal (ya sea la función Objetivo o el lado izquierdo de las restricciones funcionales) es la suma de las contribuciones individuales de las actividades respectivas (elimina los productos cruzados).
(x1,x2) | Zej. | Zcaso1+x1x2 | Zcaso2 +x1x2 | |||
(1,0) | 3 | 3 | 3 | |||
(0,1) | 5 | 5 | 5 | |||
(1,1) | 8 | 9 | 7 |
Divisibilidad: Las variables de decisión en un modelo de programación lineal pueden tomar cualquier valor, incluyendo valores no enteros, que satisfagan las restricciones funcionales y las de no negatividad.
Ejemplos de aplicación de P.L.
Son tan amplios y disímiles entre si como los que se listan a continuación
a. Planeación de la producción
b. Mezcla de alimentos
c. Corte y ajuste de material
d. Control de Calidad del agua
e. Perforación de pozos y producción de petróleo
f. Balanceo en ensamble
g. Inventario
h. Terapias médicas.
Ej. 2 Mezcla de alimentos
Se supone la disponibilidad de ciertos ingredientes con los cuales se mezcla el alimento además se conoce el contenido nutritivo de cada ingrediente. La descripción del modelo incluye:
Requerimientos nutritivos diarios del animal
Limitaciones físicas o no nutritivas tales como abastecimiento, textura o consistencia y posibilidad de aglomeración.
El objetivo es minimizar el costo total de un tamaño de lote dado de la mezcla, de tal manera que se satisfagan las restricciones físicas y nutritivas.
Suponga ahora que se requieren un lote diario de 100 Libras, la dieta para pollos debe contener
1. Al menos 0.% pero no más de 1.2% de calcio.
2. Al menos 22% de proteínas.
3. A lo más 5% de fibras crudas.
Suponga además, que los principales ingredientes utilizados incluyen maíz, soya y caliza (carbonato de calcio). El contenido nutritivo de estos ingredientes se resumen a continuación [2]
Ej. 3 Problema de la pérdida por ajustes
Cierta fábrica de papel recibió tres pedidos de rollos de papel con los ancho y longitudes indicadas a continuación:
Pedido | Anchura | Longitud |
1 | 5 | 10000 |
2 | 7 | 30000 |
3 | 9 | 20000 |
Los rollos se producen con dos anchos estándar, 10 y 20 pies los cuales hay que cortar a los tamaños especificados por los pedidos. No existe límite para la longitud de los rollos estándar. El objetivo es determinar el esquema de producción (cortes) que minimice la pérdida por ajuste y satisfaga la demanda. [2]
Sean S1, S2, S3, las longitudes en exceso producidas de 5´, 7´ y 9´ respectivamente[2]
Ej. 4 Balanceo en el ensamble
Una unidad completa de un cierto producto consiste de 4 unidades del componente A y 3 unidades del componente B. Los dos componentes (A y B) se fabrican con dos materias primes diferentes de las cuales se tienen disponibles respectivamente 100 y 200 unidades. Tres departamentos están en el proceso de producción y cada departamento utiliza un método diferente para fabricar los componentes. La tabla que sigue muestra los requisitos de materia prima por corrida de producción y las unidades resultantes de cada componente. El Objetivo es determinar el número de corridas de producción para cada departamento que max, el # total de unidades completas del producto final. [2]
Ej. 5 Una compañía produce dos tipos de sombreros vaqueros. Cada sombreo del primer tipo requiere el doble de tiempo en mano de obra que el segundo. Si todos los sombreros son solamente del segundo tipo, la compañía puede producir 500 sombreros al día. El mercado limita las ventas diarias del primero y segundo a 150 y 200. Suponga que los beneficios son 8 para el 1 y 5 para el 2. Determine el número de sombreros que se deben producir de cada tipo a fin de maximizar el beneficio. [2]
Ej. 6 Para un cafetín que trabaja 24 hrs. Se requieren las siguientes meseras:
Horas | # Mínimo de Meseras | ||
2-6 | 4 | ||
6-10 | 8 | ||
10-14 | 10 | ||
14-18 | 7 | ||
18-22 | 12 | ||
22-2 | 4 |
Cada mesera trabaja 8 hrs. Consecutivas por día. El Objetivo es contratar el número más pequeño de requerido para cumplir los requisitos anteriores. [2]
Ej. 7 Suponga que el número mínimo de autobuses requerido en la i-ésima hora del día es bi, i=1,2,3,…,24. Cada autobús trabaja 6 horas consecutivas. Si el número de autobuses en el período i excede el mínimo requerido bi, se incurre en un costo por exceso, ci, por autobús-hora. Formule el problema como un problema de P.L. de tal manera que se minimice el exceso del costo total originado. [2]
Solución a problemas de Programación Lineal P.L.
Un procedimiento general algebraico para resolver problemas de P.L. es el conocido con el nombre de método Simples desarrollado por George Dantzig en 1947.
Método gráfico o geométrico (2 variables): Tómese como ejemplo inicial el Ej. 1 [1]
Una frontera de restricción es el límite permitido por una restricción, en el caso de dos variables es una recta, en tres un plano, etc. Una solución en vértice es la intercepción de dos fronteras de restricción, una solución en un vértice que pertenece al espacio de soluciones se llama solución factible en vértice (FVE), para un problema de P.L. con n variables de decisión, cada una de sus soluciones en los vértices se encuentra en la intercepción de por lo menos n fronteras de restricción. FEV adyacentes son aquellas que comparten n-1 fronteras de restricción. Dos soluciones FEV están conectadas por un segmento de recta (pertenecientes a las fronteras de restricción) llamado orilla o arista de la región factible. Del ejemplo tenemos las siguientes soluciones FEV y sus correspondientes soluciones FEV adyacentes:
Soluciones FEV | Soluciones FEV adyacentes | |
(0,0) | (0,6) y (4,0) | |
(0,6) | (2,6) y (0,0) | |
(2,6) | (4,3) y (0,6) | |
(4,3) | (4,0) y (2,6) | |
(4,0) | (0,0) y (4,3) |
Tabla 10, Soluciones FEV Ej. 1
Prueba de optimalidad: Si una solución FEV no tiene soluciones FEV adyacentes que sean mejores bajo la perspectiva de Z, entonces ésa debe ser una solución Optima.
Solución geométrica.
Inicialización: Elija (0,0) como SFEV inicial
Prueba de optimalidad: pruebe la existencia de soluciones adyacentes que mejoren el valor de Z.
En caso de existir una mejor solución itere
1. Muévase sobre la arista que más aumenta (disminuye) el valor de Z.
2. Deténgase en la frontera de restricción.
3. Tome ese nuevo punto como solución de inicio.
En caso contrario la Solución FEV es la solución optima.
Solución en el Método simplex: siempre es una solución FEV, entonces el método simple sólo toma en cuenta las soluciones FEV y consiste en encontrar la mejor.
Solución FEV de inicio: Generalmente es el origen, es decir, todas las variables de decisión igual a cero. Es posible en la mayoría de los casos ya que las restricciones de no negatividad sobre las variables de decisión generan como fronteras de restricción a los vértices dejando el origen como una solución FEV, salvo en el caso que viole una restricción funcional.
Ej. 8 resuelva de forma gráfica y geométrica el siguiente problema de P.L.
Obviando las restricciones de no negatividad y agregando variables tales que cada desigualdad se transforme en igualdad, el problema es un sistema de 4 ecuaciones con 6 incógnitas, y de la solución geométrica observamos que cada solución FEV es la solución del sistema descrito haciendo 2 de esas variables iguales a cero. En general para m ecuaciones y n incógnitas con n>m, al hacer n-m variables iguales a cero obtendremos lo que se denomina solución básica, denominándose a las variables iguales a cero variables no-básicas las restantes se denominan básicas y si además estas ultimas son todas no negativas a la solución se llama solución básica factible.
La solución optima para un sistema de m ecuaciones y n incógnitas se podrá entonces hallar resolviendo
Conjunto de ecuaciones simultaneas siendo totalmente ineficiente por cuanto:
El # de soluciones básicas es muy grande
Muchas soluciones son in factibles
La función Objetivo sería pasiva en el cálculo.
Consideraciones para la Solución Algebraica: Este se basa en la solución de sistemas de ecuaciones por consiguiente, el primer paso es convertir las inecuaciones en ecuaciones (restricciones funcionales de desigualdad en restricciones de igualdad), introduciendo las llamadas variables de holgura, que no es otra cosa que restar del lado derecho la holgura de recurso que convierta en una igualdad la restricción funcional respectiva, una observación obvia entonces es que por cada restricción funcional del tipo ( se tendrá una nueva variable, lo que convierte el problema de PL en un sistema de ecuaciones de m ecuaciones con m+n variables. Del Ej. 1 tendrá entonces la siguiente forma aumentada del problema de P.L.
Un valor de cero (0) en una variable de holgura significa que se encuentra en las fronteras de decisión, mientras que uno positivo significa que esta en el lado factible de la región factible y un valor negativo estará en el lado no factible, de esta forma una solución FEV tendrá ahora cinco valores es decir, tomemos la solución FEV (3,2) tendrá la siguiente solución aumentada (3,2,8,1,5), lo que no es otra cosa que una solución básica factible descrita en la sección anterior. Considere la solución (4,6), ¿qué conclusiones obtiene al aumentarla?. Ejercicio hallar todas las soluciones factibles o no, aumentadas para el Ej. 1.
Propiedades de la solución básica
1. Cada variable de la forma aumentada será designada como básica o no básica.
2. El número de variables básicas es igual al número de restricciones funcionales (ecuaciones) y el número de no-básicas será la diferencia entre el número total de variables y el número de restricciones funcionales (variables básicas), así del ejemplo serían 3 y 2 respectivamente las variables básicas y las no-básicas.
3. Las variables no básicas se hacen igual a cero.
4. Los valores de las variables básicas se obtienen de la solución simultánea del sistema de ecuaciones aumentado resultante de hacer cero las variables no-básicas.
5. Si las variables satisfacen las restricciones de no negatividad, la solución básica es una solución básica factible.
Considere la solución (0,6), ¿Cuál será la solución aumentada?. ¿Cuáles las variables básicas y no-básicas?. ¿Es una SBF?
Soluciones BF adyacentes: si todas menos una de sus variables no-básicas son las mismas, esto también implica que todas menos una de sus variables básicas serán las mismas pero no necesariamente con el mismo valor. En consecuencia trasladarse de una solución BF adyacente a otra implica hacer una variable no-básica, básica y viceversa, ajustando luego los valores de las demás variables básicas de tal manera que sigan satisfaciendo las restricciones.
Antes de emplear SÍMPLEX
Conviene expresar el problema de la siguiente manera:
Observe la manera que se ha incorporado la función objetivo al problema, dejando de ser pasiva en el cálculo, también es de hacer notar que se han numerado las ecuaciones por comodidad.
La solución básica inicial se obtiene de hacer cero las variables de decisión (0,0,4,12,18), la cual arroja como valor Z=0, luego si observamos los valores de los coeficientes de las variables no-básicas observamos que pueden mejorar el valor de Z, con lo cual se puede concluir que la solución actual no es optima. ¿Cuál variable cambiar de no-básica a básica?. ¿En que valor debe aumentar la variable que será básica?.
La idea es aumentar la variable que mejore a una tasa más grande el valor de Z sin dejar de la región factible y que todas las variables permanezcan no negativas.
Variable básica entrante: Variable no-básica que aumentará su valor de cero (mejorará el valor de Z) y será parte de la solución básica actual.
Variable básica que sale: variable básica que llega primero a cero, cuando se aumenta la variable que entra.
Note que el sistema las variables básicas poseen un coeficiente igual a uno, una forma muy adecuada cuando se emplea eliminación gaussiana para resolver sistemas de ecuaciones, siendo este el método en el cual se basa el SÍMPLEX, se deberá ahora operar sobre el sistema de ecuaciones de tal manera que:
La función objetivo este expresada solo en términos de variables no-básicas.
Las variables básicas tengan coeficiente la unidad en la ecuación donde se encontraba la antigua variable básica y cero en las demás.
Así podemos ver que en la ecuación (2) al dividir entre 2 toda la ecuación cumpliremos con la segunda exigencia, para la segunda se debe entonces operar algebraicamente sobre ellas, sumando o restando múltiplos de una ecuación a otra.
Símplex en forma tabular.
Para el Ej. 1 si solo tomamos en cuenta sus coeficientes y además consideramos el arreglo anterior donde la función objetivo será nuestra ecuación cero (0) y lo colocamos convenientemente en una tabla (tabla 11):
Ec. # | X1 | X2 | X3 | X4 | X5 | Lado Der. | ||||||
(0) | -3 | -5 | 0 | 0 | 0 | 0 | ||||||
(1) | 1 | 0 | 1 | 0 | 0 | 4 | ||||||
(2) | 0 | 2 | 0 | 1 | 0 | 12 | ||||||
(3) | 3 | 2 | 0 | 0 | 1 | 18 |
Tabla 11. Forma tabular Ej. 1
Algoritmo símplex
Solución Inicial: X3=4, X4=12, X5=18 para Z=0
Consideraciones en torno a las posibles soluciones
Empate en la variable que entra, esto es dos o más variables tienen el mismo valor (Coef. Negativo) más grande, en este caso se rompe el empate de manera arbitraria. Ej.:
Empate en la variable básica que sale, en este caso si es importante que variable se toma ya que pueden ocurrir una serie de consecuencias: a) Al iterar las demás variables empatadas se harán cero (0), llamando a esta situación degeneración (variable degenerada y solución básica degenerada.
b) Si cualquiera de las variables a nivel cero se elige como variable que sale, la variable que entra también deberá hacerlo a nivel cero pues no puede crecer sin la que sale disminuya, lo que implica que no hay mejora para Z existiendo la posibilidad de
c) entrar en un ciclo infinito.
No existe variable básica que sale, (Z es no acotada) esto se puede observar en la tabla cuando todos los valores bajo la variable que entra (valores de la columna pivote) son todos negativos o cero.
Soluciones óptimas múltiples Ej.: Max Z=3×1+2×2, esto se ve cuando al menos una variable tiene coeficiente cero (0) en la ecuación final, de forma que si se aumenta su valor Z no tiene incremento.
Otras Formas Del Modelo de P.L.
Forma estándar: Maximizar, restricciones de la forma menor o igual ((), restricciones de no negatividad y bi(0 para toda i=1,2,…,m. Para otras formas del modelo la dificultad adicional radica en poder identificar la solución básica factible inicial.
Técnica de las variables artificiales. Que de forma muy general construye un problema artificial a partir del original agregando convenientemente una variable ficticia llamada artificial con la intención de que sea parte de la solución básica inicial, debiendo modificar la F.O. para penalizar el hecho de que la variable nueva no es real.
Restricciones en forma de igualdad: Supongamos ahora el siguiente problema:
Fundamentos método Símplex
Frontera de la región factible consiste en aquellas soluciones factibles que satisfacen una o más de las ecuaciones de frontera de las restricciones.
Una solución factible en vértice (FEV) es aquella que no está sobre ningún segmento de recta que conecta a otras dos soluciones factibles.
Para un problema de P.L. con n variables de decisión, cada solución FEV se encuentra en la intersección de n fronteras de restricción; es decir se trata de la solución simultánea de un sistema de n ecuaciones de frontera; en este caso y dado que existen (n+m) ecuaciones de frontera no todo sistema de n ecuaciones conduce a una SFEV, pudiendo ocurrir que:
Violen una o más de las restantes m ecuaciones de restricciones, generando una solución no factible.
No tener solución si se eligen ecuaciones que definan hiperplanos paralelos.
Múltiples soluciones debido a ecuaciones redundantes.
Para el ejemplo tipo empleado hasta ahora [1]:
Tabla 12. Soluciones y ecuaciones de definición
Soluciones FEV adyacentes
Para un problema de PL con n variables de decisión y una región factible acotada, una solución FEV se encuentra en la intersección de n fronteras de restricción que satisface las restantes restricciones. Una arista de la región factible es un segmento de recta factible que se encuentra en la intersección de (n-1) fronteras de restricción. Dos soluciones FEV son adyacentes si el segmento de recta que las conecta es una arista de la región factible. De cada solución FEV parten n aristas, llevando cada una a las n soluciones factibles adyacentes.
Propiedades de las soluciones FEV
Propiedad 1: a) Si el problema tiene exactamente una solución optima, entonces esta debe ser una solución FEV
b) Si el problema tiene soluciones factibles optimas múltiples (y una región factible no acotada), entonces al menos 2 deben ser soluciones FEV adyacentes.
Propiedad 2: Solo existe un número finito de soluciones FEV, dado que una solución FEV es la solución simultanea de un sistema de n ecuaciones elegidas entre (n+m) ecuaciones de frontera de restricción esto es:
dado que es un número finito esta combinación no es mas que una cota superior para el número de soluciones FEV.
Propiedad 3: Si una solución FEV no tiene soluciones FEV adyacentes que mejoren la solución (Z), entonces es una solución optima.
Forma Aumentada del Problema de PL
Donde xn+1, xn+2,…, xn+m, son variables de holgura o artificiales faltando quizá algunas variables de superávit. Es bueno recordar que cada solución en un vértice es la solución simultánea de un sistema de n ecuaciones de frontera, a las que se llamó ecuaciones de definición entonces ¿cuáles de todas las ecuaciones de frontera son ecuaciones de definición?.
Cada restricción tiene una variable indicativa, que señala cuando la solución actual satisface la ecuación de frontera de esa restricción (tabla 13).
Página siguiente |