Monografias.com > Ingeniería
Descargar Imprimir Comentar Ver trabajos relacionados

Aplicación de la Investigación de Operaciones y la Programación Matemática



Partes: 1, 2

  1. Orígenes
  2. Modelado
  3. El
    problema Dual y el análisis de
    Sensibilidad
  4. Referencias
    Bibliográficas

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

Monografias.com

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.

Monografias.com

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íaCiencia 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:

Monografias.com

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 + a12x2a1nxn (
b1

a21x1 + a22x2a2nxn (
b2

… … … …

am1x1 + am2x2amnxn (
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:

Monografias.com

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.

Monografias.com

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]

Monografias.com

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]

Monografias.com

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]

Monografias.com

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]

Monografias.com

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]

Monografias.com

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.

Monografias.com

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

Monografias.com

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.

Monografias.com

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:

Monografias.com

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?.

Monografias.com

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.:

Monografias.com

  • 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:

Monografias.com

Fundamentos método
Símplex

Monografias.com

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:

Monografias.com

  • 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]:

Monografias.com

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:

Monografias.com

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?.

Monografias.com

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).

Partes: 1, 2

Página siguiente 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter