Scribd
Cargar
67 vistas2 páginas

Solución Artificial de Inicio

El documento describe métodos para encontrar soluciones básicas factibles en programación lineal cuando las restricciones son del tipo = o ≥. Se presentan dos enfoques: el Método de Penalización (M Grande), que utiliza variables artificiales penalizadas en la función objetivo, y el Método de las Dos Fases, que busca primero una solución básica factible antes de resolver el problema original. Ambos métodos son esenciales para aplicar el Método Simplex en situaciones donde las soluciones iniciales no son evidentes.

Cargado por

Raúl Colmenares
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
67 vistas2 páginas

Solución Artificial de Inicio

El documento describe métodos para encontrar soluciones básicas factibles en programación lineal cuando las restricciones son del tipo = o ≥. Se presentan dos enfoques: el Método de Penalización (M Grande), que utiliza variables artificiales penalizadas en la función objetivo, y el Método de las Dos Fases, que busca primero una solución básica factible antes de resolver el problema original. Ambos métodos son esenciales para aplicar el Método Simplex en situaciones donde las soluciones iniciales no son evidentes.

Cargado por

Raúl Colmenares
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

Solución Artificial de Inicio 1

Solución Artificial de Inicio


Investigación de Operaciones I
El Método Simplex

Los modelos de programación lineal en los que todas las restricciones son de la forma ≤ con lados derechos no negativos
ofrecen una cómoda solución básica factible de inicio con todas las holguras. Los modelos donde intervienen restricciones
del tipo = o bien ≥ no poseen esta propiedad.
El procedimiento para iniciar programas lineales con restricciones del tipo = o ≥ es permitir que variables artificiales
desempeñen el trabajo de las holguras en la primera iteración para después, en alguna iteración posterior, desecharlas de
manera legı́tima. Presentaremos dos métodos.

1. Método de Penalización (M Grande)


El método M comienza con la programación lineal en forma de ecuaciones. Una ecuación i que no contenga holgura
se aumenta con una variable artificial Ai , para formar una solución de inicio parecida a la solución básica con todas las
holguras. Sin embargo, como las variables artificiales son ajenas al MPL, se usa un mecanismo de retroalimentación en
el que el proceso de optimización trata en forma automática de hacer que esas variables tengan nivel cero. El resultado
deseado se obtiene penalizando las variables artificiales en la función objetivo.
Dado M , un valor positivo suficientemente grande (M → ∞), el coeficiente objetivo de una variable artificial representa
una penalización adecuada si
⎧
⎪
⎪−M, en maximización
Coeficiente objetivo de la variable artificial = ⎨
⎪
⎪
⎩M, en minimización

Al usar esta penalización el proceso de optimización forzará en forma automática a las variables artificiales para que sean
cero (siempre que el problema tenga solución factible).

Ejemplo 1. Resolver el siguiente MPL por el método de penalización.

mı́n z = −3x1 + 5x2


s.a.
x1 ≤4
x2 ≤6
3x1 +2x2 ≥18
x1 , x2 ≥0

Ejemplo 2. Resolver el siguiente MPL por el método de penalización.

mı́n z = 4x1 + x2
s.a.
3x1 +x2 = 4
4x1 +3x2 ≥ 6
x1 +2x2 ≤ 4
x1 , x2 ≥ 0

2. Método de las Dos Fases


El método resuelve la programación lineal en dos fases: la fase I trata de determinar una solución básica factible de
inicio y, si se encuentra, se invoca la fase II para resolver el MPL original.

Investigación de Operaciones I Prof. M.C. Jonathan Batres Romo


El Método Simplex 2

Fase I: El problema se pone en forma de ecuaciones (estándar) y se agregan a las restricciones las variables artificiales
necesarias para asegurar una solución básica de inicio. A continuación se determina una solución básica de las
ecuaciones resultantes que minimice la suma de las variables artificiales. Si el valor mı́nimo de la suma es positivo,
el MPL no tiene solución factible y termina el proceso. En caso contrario, se prosigue a la fase II.
Fase II: Se usa la solución factible de la fase I como solución básica factible de inicio para el problema original.
Ejemplo 3. Resolver el siguiente MPL por el método de las dos fases.

mı́n z = 2x1 − 4x2 + 3x3


s.a.
5x1 −6x2 +2x3 ≥ 5
−x1 +3x2 +5x3 ≥ 8
2x1 +5x2 −4x3 ≤ 9
x1 , x 2 , x 3 ≥ 0

Investigación de Operaciones I Prof. M.C. Jonathan Batres Romo

También podría gustarte