El método de las dos fases, paso a paso: Investigación de operaciones

En el método de dos fases, todo el procedimiento para resolver una programación lineal
El problema (LPP) que involucra variables artificiales se divide en dos fases.

En
Fase I, formamos una nueva función objetivo asignando cero a cada
variable original (incluidas variables flojas y excedentes) y -1 a
cada una de las variables artificiales. Luego tratamos de eliminar el artificial
Varibles de la base. La solución al final de la fase I sirve como
Una solución factible básica para la fase II. En la fase II, el objetivo original
se introduce la función y el algoritmo simplex habitual se utiliza para encontrar
una solución óptima. Los siguientes son ejemplos de método de dos fases.

Si la función objetivo está en forma de minimización, conviértala en forma de maximización.

Cualquier problema de minimización lineal se puede ver como un lineal equivalente
Problema de maximización y viceversa. Específicamente:

Si z es el valor óptimo de la expresión de la izquierda, entonces -z es el
valor óptimo de la expresión de la derecha.

x1 + 3×2 + x3 + x4 = 5
2×1 x2 + x3 x5 = 2
4×1 + 3×2 – 2×3 = 5

Dónde:
x4 es una variable floja
x5 es una variable excedente

La variable excedente x5 representa
las unidades adicionales.

Ahora, si dejamos que X1, X2 y X3 fuera igual
A cero en la solución inicial, tendremos x4 = 5 y
x5 = -2, que no es posible porque una variable excedente
no puede ser negativo. por lo tanto, nosotros
Necesita variables artificiales.

A2 sale y X2 entra.
Aquí, la fase 1 termina porque ambas variables artificiales tienen
ha sido eliminado de la base.

¿Cuándo se usa el metodo de las 2 fases?

Hemos visto en la sección Simplex Pivot Element Cómo pasar de un problema de programación lineal a su forma estándar por uso de variables flojas.

El problema es, como hemos visto, para encontrar una submatriz MXM de identidad de un algoritmo simplex para iniciar, lo que puede no ser fácil.

Para esto, aplicaremos el método de dos fases llamado que consiste en lo siguiente. Essentialy cuyos pasos están en currículum:

Fase 1

1) Buscamos una submatriz de identidad de Dimension MXN dentro de la matriz total A, una vez que se agregan las variables flojas, será necesario que sean necesarias nuevas variables artificiales artificiales para comenzar el algoritmo.

A pesar de ser un redunte, presentaremos m nuevas variables artificialesm, por lo que agregamos una matriz completa MXM a la matriz A. Con esto no alteramos el conjunto de puntos extremos del problema original, y a lo sumo agregamos cualquier nuevo paso a la primera fase. Lo que ganamos es eliminar la complejidad de distinguir entre variables originales, flojas y artificiales al momento de pasar de la primera a la segunda fase.

Lo más claro: b> En teoría, se deben agregar menos de las columas M ya que la matriz original junto con las variables flojas generalmente proporcionan suficientes columnas de la subatriz de identidad. Lo que hacemos aquí es que si tenemos que agregar una sola variable artificial, entonces agregamos la m completa. ¿Por qué? Debido a que creemos que aunque agrega algunas dimensiones más al problema, reduce su complejidad práctica.

2) Cambie la función objetivo original de uno que tenga todos los ceros, excepto los últimos componentes m que tienen el valor 1 (es decir, vector c = (0, .., n-Times…, 0, 1, .., m- veces…, 1)
3) Comience el algoritmo con este problema hasta tomar uno de estos casos:

3a) Llegamos a la solución óptima si cero: esto significa que las variables artificiales se han quedado de base, en este caso podemos pasar a la fase 2 del método.

¿Cuando el problema se convierte en método simplex dos fases?

• En la primera fase elabora el algoritmo en un problema artificial para identificar una base admisible (si existe). Pueden ocurrir dos casos:
• El problema admite soluciones. Si la excelente solución del problema artificial tiene un valor nulo (z = 0), el problema original admite una solución. Paso a la fase 2.
• El problema es inadmisible. Si la excelente solución del problema artificial no tiene un valor nulo (z ☎ 0), el problema original no permite soluciones. Así que no voy a la Fase 2. El algoritmo termina aquí.
• En la segunda fase, elabore el algoritmo de simplicidad sobre el problema construido en forma canónica sobre la base identificada en la primera fase.

La segunda fase (simplura) se realiza solo si se satisface la primera fase, es decir, si el problema artificial tiene una solución.

Uno de los problemas del algoritmo de simplicidad es la elección de las bases iniciales para construir la forma canónica, es decir, la inicialización del SB (solución básica elegible).

La elección de las variables básicas iniciales depende del número de pasos necesarios para alcanzar la resolución final del problema (excelente, ilimitado, inadmisible).

El algoritmo de SimpleSs en dos fases utiliza un algoritmo específico para identificar el mejor error inicial. Luego, reduce el número total de ciclos de procesamiento.

En la primera fase, creo un problema artificial de PA a partir del problema original P en forma estándar.

¿Cuándo se utilizan las variables artificiales?

Se introduce la variable artificial para cada restricción de igualdad y «≥ tipo» para obtener una solución factible básica inicial para el problema auxiliar. Estas variables no tienen significado físico y deben eliminarse del problema. Para eliminar las variables artificiales del problema, definimos una función de costo auxiliar llamada función de costo artificial y minimizamos sujeto a las limitaciones del problema y la no negatividad de todas las variables. La función de costo artificial es simplemente una suma de todas las variables artificiales y se designará como w:

Como ejemplo, la función de costo artificial en el ejemplo 8.12 se da como

donde E denota el vector All-One. Sin pérdida de generalidad, podemos suponer que b ≥ 0 en la ecuación. (1), porque de lo contrario multiplicamos las restricciones para las cuales la entrada correspondiente en B es negativa, por −1. Entonces x = 0, t = b es una solución factible para la ecuación. (15) y, obviamente, esta solución es básica. Por lo tanto, podemos resolver la ecuación. (15) con el método simplex. Desde la ecuación. (15) es un problema limitado, esto produce una solución factible básica (x¯, t¯) de la ecuación. (15). Ahora pueden ocurrir dos casos: ett¯> 0 o ett¯ = 0. En el primer caso, el problema debe ser inviable, porque cualquier solución factible de la ecuación. (1) produce una solución factible a la ecuación. (15) con t = 0. En el segundo caso, x¯ es una solución factible básica de la ecuación. (1).

Ahora está claro que podemos resolver la ecuación. (1) Con el método simplex en dos fases. En la fase I resolvemos la ecuación. (15); Si el problema es inviable, se detecta en esta fase, de lo contrario obtenemos una solución factible básica de la ecuación. (1) que se puede usar en la Fase II para resolver el problema. La fase II produce una solución básica óptima o detecta que el problema es (factible y) ilimitado.

¿Cuáles son las fases del metodo simplex?

Hasta ahora solo hemos discutido cómo resolver programas lineales (que están en
forma estándar y) para los cuales los lados de la mano derecha de las limitaciones
son todos no negativos. ¿Por qué teníamos esa restricción? Toma este LP,
por ejemplo:

La solución asociada a ese diccionario tiene, por ejemplo, (x_5 =
-5 ), que es negativo. Eso significa que la segunda restricción es
Violado y, de hecho, la solución asociada tiene (x_1 = x_2 = x_3 = 0 )
para que (2x_1 -3x_2 + x_3 = 0 no le -5 ).

Recuerde que el método simplex se realiza girando de factible
diccionario a diccionario factible hasta llegar a un diccionario desde
que no puede indicar que tiene una solución óptima
o el LP está ilimitado (en cuyo caso puede encontrar un 1 parámetro
Familia de soluciones con función objetiva que tiende al infinito). Asi que
No podemos usar este diccionario inviable.

Es posible que elija un conjunto diferente de variables (en lugar de
las variables flojas) ser las variables básicas y resolver para ellas
produciría un diccionario factible del que podemos comenzar el
Método simple. Pero, ¿cómo podemos encontrar qué conjunto de variables usar?

Si tuviéramos un diccionario factible para comenzar a aplicar el método simplex,
La solución asociada sería una solución factible del LP, que
es, tendría valores para las variables de decisión que satisfacen todas
de las limitaciones en LP original. ¡Tales valores no siempre existen!
Ahora explicaremos cómo averiguar simultáneamente si hay o no
son soluciones factibles y, si lo hay, cómo elegir un
Diccionario inicial.

¿Cuáles son las fases del Método Simplex?

Un cuadro de optimización lineal se puede sistematizar en diferentes fases que deben tratarse antes de que se pueda usar el paso de optimización real, lo que se explica por el método de usar el algoritmo Simplex.

Las variables bloqueadas son identificables donde las ecuaciones se escriben como restricciones. Esto significa que la variable de estructura (variable floja) debe convertirse en 0 para resolver la ecuación (variable bloqueada). Esta variable de estructura no debe mantenerse en la base, por lo tanto, es urgente que abandone la base. La fila donde se puede encontrar esta variable bloqueada se convierte en la fila de pivote. Esa coulumna que no contienen variables bloqueadas como una variable no base se convierten en el coulumno de pivote.
Después de que se encuentra el elemento pivote, una iteración simple sigue por las reglas simples del algoritmo simplex.

Las variables libres son variables para las cuales las condiciones de no negatividad no son válidas respectivamente no están definidas. Tienen que ser transferidos a la base también. Mientras las variables libres se encuentren en el no básico, la coulumna en la que se paran se convierte en una coulumna pivote.
Si una variable libre se reubica a la base, se bloquea para el resto del procedimiento de optimización. Esto significa que la fila base en la que se encuentra después de la reubicación no puede convertirse nuevamente en una fila de pivote.
Nuevamente, una iteración simplex sigue la búsqueda del elemento pivote en esta fase.

x1 { displaystyle x_ {1}} y x2 { displaystyle x_ {2}} son las variables que deben optimizarse. En la última línea, eso representa las condiciones de no negatividad, en el cuadro contiguo solo se menciona x1 { displayStyle x_ {1}} y, por lo tanto, se restringe. Por lo tanto, x2 { displayStyle x_ {2}} es una variable gratuita.

¿Cuáles son las fases de la programación lineal?

Las partes principales de un problema de programación lineal se dan a continuación:

• Función objetiva
• Variables de decisión
• Datos

Las aplicaciones de la programación lineal están muy extendidas en muchas áreas. Se utiliza especialmente en matemáticas, telecomunicaciones, logística, economía, negocios y campos de fabricación. Los principales beneficios del uso de la programación lineal se dan a continuación:

• Función objetiva
• Variables de decisión
• Datos

En la siguiente sección, discutiremos los pasos involucrados en la resolución de problemas de programación lineal.

Debemos seguir los siguientes pasos al resolver un problema de programación lineal gráficamente.

El primer paso es discernir las variables de decisión que controlan el comportamiento de la función objetivo. La función objetivo es una función que requiere optimización.

Las variables de decisión que acaba de seleccionar deben emplearse para anotar una expresión algebraica que muestra la cantidad que estamos tratando de optimizar. En otras palabras, podemos decir que la función objetivo es una ecuación lineal que se compone de variables de decisión.

¿Cuáles son las fases de programación lineal en la resolucion de problemas?

En el cuestionario y la final, se le pedirá que formule un problema de programación lineal. Aquí está la interpretación del profesor Burgiel de las instrucciones de formulación del problema en las páginas 248-250 del libro de texto.

• Entender el problema.
  El objetivo de un problema de programación lineal es encontrar una manera de obtener la mayor cantidad o menos de cierta cantidad, a menudo ganancias o gastos. Esta cantidad se llama su objetivo.

La respuesta debe depender de la cantidad de algunas variables de decisión que elija. Sus opciones sobre cuánto estarán limitadas por las restricciones establecidas en el problema.

• Entender el problema.
  El objetivo de un problema de programación lineal es encontrar una manera de obtener la mayor cantidad o menos de cierta cantidad, a menudo ganancias o gastos. Esta cantidad se llama su objetivo.

Es posible que tenga limitaciones como «No puede gastar más de $ 1000» o «Usted no envía al menos 50 toneladas de productos de productos». Estos son límites, pero no necesariamente reflejan las principales prioridades de su empleador; No confíe esto con sugerencias de que minimice los costos o maximice la producción.

• Entender el problema.
  El objetivo de un problema de programación lineal es encontrar una manera de obtener la mayor cantidad o menos de cierta cantidad, a menudo ganancias o gastos. Esta cantidad se llama su objetivo.

¿Cuáles son los elementos de un problema de programación lineal?

La programación lineal se ve como un desarrollo revolucionario que da al hombre la capacidad de establecer objetivos generales y encontrar, por medio del método simple, decisiones de política óptimas para una amplia clase de problemas de decisión práctica de gran complejidad. En el mundo real, la planificación tiende a ser ad hoc debido a los muchos grupos de intereses especiales con sus múltiples objetivos. ~ George Dantzig

La técnica LPP fue introducida por primera vez en 1930 por el matemático ruso Leonid Kantorovich en el campo de los horarios de fabricación y por el economista estadounidense Wassily Leontief en el campo de la economía. Después de una década durante la Segunda Guerra Mundial, estas técnicas se adoptaron en gran medida para resolver problemas relacionados con el transporte, la programación, la asignación de recursos, etc. En 1950, el primer algoritmo de método simple para LPP fue creado por el matemático estadounidense George Dantzig.

Variables de decisión: Estas son las cantidades desconocidas que se espera que se estimen como una salida de la solución LPP.

Función objetivo: todos los problemas de programación lineal tienen como objetivo maximizar o minimizar algún valor numérico que represente ganancias, costo, cantidad de producción, etc. Evalúa la cantidad por la cual cada variable de decisión contribuiría al valor presente neto de un proyecto o una actividad.

Coeficiente de función objetivo: la cantidad por la cual el valor de la función objetivo cambiaría cuando se altere una unidad de una variable de decisión, el coeficiente de función objetivo correspondiente.

¿Cuántos métodos conoce para resolver problemas de programación lineal?

Hay dos métodos principales disponibles para resolver un problema de programación lineal. Estos son el método simple y el método gráfico. A continuación se muestran los pasos para resolver un problema de programación lineal utilizando ambos métodos.

El método Simplex en LPP se puede aplicar a problemas con dos o más variables de decisión. Suponga que la función objetivo Z = 40 (x_ {1} ) + 30 (x_ {2} ) debe maximizarse y las restricciones se dan de la siguiente manera:

Paso 1: Agregue otra variable, conocida como variable floja, para convertir las desigualdades en ecuaciones. Además, reescribe la función objetivo como una ecuación.

Paso 3: Identifique la columna con la entrada negativa más alta. Esto se llama la columna Pivot. AS -40 es la entrada negativa más alta, por lo tanto, la columna 1 será la columna Pivot.

Paso 4: Divida las entradas en la columna más a la derecha por las entradas en la columna Pivot. Excluyimos las entradas en la fila más inferior.

La fila que contiene el cociente más pequeño se identifica para obtener la fila de pivote. Como 8 es el cociente más pequeño en comparación con 12 Por lo tanto, la fila 2 se convierte en la fila de pivote. La intersección de la fila de pivote y la columna dinámica le da el elemento pivote.

Paso 5: con la ayuda del elemento pivote realizar la pivote, utilizando propiedades de matriz, para hacer todas las demás entradas en la columna de pivote 0.

Paso 6: Verifique si la fila más inferior tiene entradas negativas. Si no, entonces se ha determinado la solución óptima. En caso afirmativo, vuelva al paso 3 y repita el proceso. -10 es una entrada negativa en la matriz, por lo tanto, el proceso debe repetirse. Obtenemos la siguiente matriz.

Artículos Relacionados:

• Fases de investigación de operaciones: conoce las fases clave para mejorar tus procesos
• Guía completa de las fases de estudio de investigación de operaciones
• La fase 1 de la investigación es crucial para el éxito del proyecto
• Las 5 etapas de la investigación-acción que todo investigador debería conocer