• Author / Uploaded
• Ulises Tolentino

• Categories
• Ecuaciones
• Álgebra
• Análisis
• Conceptos matemáticos
• Física y matemáticas

Citation preview

INVESTIGACIÓN DE OPERACIONES I MÉTODO SÍMPLEX DE PROGRAMACIÓN LINEAL El método símplex se basa fundamentalmente en que la solución óptima de un problema de programación lineal está asociada siempre con un punto extremo del espacio de soluciones. 1. MÉTODO SÍMPLEX ESTÁNDAR (TRADICIONAL) A. DEFINICIONES GENERALES o Solución Factible: Es la solución que satisface todas las restricciones. o Solución optima: Es la solución factible que tiene el mejor valor en la función objetivo. o Variable Básica: Es una variable que tiene un valor diferente de cero en una determinada iteración. o Variable no Básica: Es una variable que tiene un valor igual a cero en una determinada iteración. Una variable básica puede convertirse en una variable no básica y viceversa. El número de variables no básicas se encuentra al hacer la diferencia de n-m (n>m); donde: m

= número de ecuaciones

n

= número de incógnitas

o Solución Básica Resulta de hacer n-m variables iguales a cero en una determinada iteración. o Variable de holgura Representa la cantidad no utilizada de un recurso.

B. FORMA CANÓNICA DE LA PROGRAMACIÓN LINEAL Max Z = C1X1 + C2X2 +… + Cn Xn S.A.:

(0)

a 11X1 + a 12X2 +…+ a 1nXn ≤ b1

(1)

a 21X1 + a 22X2 +…+ a 2nXn ≤ b2

(2)

a 31X1 + a 32X2 +…+ a 3nXn ≤ b3

(3)

a m1X1 + a m2X2 +…+ a mnXn ≤ bm

(m)

X1 , X2 ,…, Xn ≥ 0 A partir de la forma canónica obtenemos la forma estándar: C. FORMA ESTÁNDAR DEL MÉTODO SÍMPLEX: (0)

Z - C1X1 - C2X2 -…- Cn Xn

=0

(1)

a11X1 + a 12X2 +…+ a 1nXn + h1

= b1

(2)

a 21X1 + a 22X2 +…+ a 2nXn

(3)

a 31X1 + a 32X2 +…+ a 3nXn

(m)

a m1X1 + a m2X2 +…+ a mnXn

+ h2

= b2 + h3

= b3

+ h m = bm

X1, X2,…, Xn, h1, h2,…, hm ≥ 0 Donde:

X1, X2,…, Xn Son variables de decisión h1, h2,…, hm Son variables de holgura

Propiedades de la Forma Estándar 1.- Todas las restricciones son ecuaciones con segundo miembro no negativo 2.- Todas las variables son no negativas 3.- La función objetivo puede ser de maximización o de minimización.

D. FORMA TABULAR DEL MÉTODO SÍMPLEX Nº Iter. 0

V.B. h1 h2 h3

Nº Ec. 0 1 2 3

Z 1 0 0 0

X1 X2 -C1 -C2 a11 a12 a21 a22 a31 a32

hm

m

0

am1

… X n h1 … -Cn 0 … a1n 1 … a2n 0 … a3n 0

am2

… amn

0

h2

h3 0

0 1 0

0

…. hm 0 …. 0 0 …. 0 0 …. 0 1 …. 0

0

…. 1

L. D. 0 b1 b2 b3

bm

E. PROCESO DEL MÉTODO SÍMPLEX 1. INICIALIZACIÓN: Seleccionar el primer vértice de solución factible. Usando la forma estándar, determine una solución básica factible inicial. Para ello las variables de holgura se toman como variables básicas y su valor es igual al lado derecho (bi, i = 1,2,…, m) de cada ecuación y las variables de decisión se toman como variables no básicas. El proceso del método símplex consiste en sustituir variables básicas por variables no básicas que mejoren el valor de la solución básica inicial. 2. PROCESO ITERATIVO a. Criterio para la variable de entrada. En el caso de maximización se escoge la que tiene el valor más negativo en la ecuación Z. En el caso de minimización se escoge la que tiene el valor más positivo. Una coincidencia se anula en forma arbitraria. b. Criterio para la variable de salida. Aplicar la condición de factibilidad: Se escoge la variable que tenga la razón más pequeña con denominador positivo que resulte de dividir el lado derecho entre el coeficiente de la variable de entrada (bi /aij ). Una coincidencia se anula en forma arbitraria. c. Obtener el nuevo sistema de ecuaciones con el nuevo grupo de variables no básicas. Mediante el método de Gauss-Jordan se hace uno el coeficiente de la variable de entrada en la ecuación donde se intercepta la variable de entrada y la de salida (elemento pivote) y luego se elimina de las otras ecuaciones la variable de entrada, incluyendo la ecuación Z, es decir convertir en ceros los demás elementos de la columna pivote.

d. Verificar si se cumple la Condición de Optimidad. En caso contrario repetir los pasos a, b, c hasta que se satisfaga tal condición. 3. CONDICIÓN DE OPTIMIDAD Caso de Maximización: Si en la ecuación Z todos los coeficientes de las variables no básicas son no negativos, se ha llegado al óptimo. Caso de Minimización: Si en la ecuación Z todos los coeficientes de las variables no básicas son no positivos, se ha llegado al óptimo. 2. MÉTODO SÍMPLEX UTILIZANDO LA TÉCNICA DE VARIABLES ARTIFICIALES (MÉTODO DE LA “M”) Las variables artificiales se emplean cuando no se pueden utilizar las variables de holgura como la solución básica inicial. Esto se presenta cuando la restricción original es una igualdad o es del tipo “mayor o igual”. La variable artificial (Ai) es una variable no negativa que se suma al lado izquierdo de cada ecuación que no tenga variables iniciales factibles. Si la restricción original es una igualdad, se sumará la variable artificial A i. Si la restricción original es del tipo “mayor o igual”, se restará una variable de holgura hi y se sumará la variable artificial Ai. La variable artificial agregada desempeñará la misma función que una variable de holgura, al proporcionar una solución básica inicial. La utilizamos sólo para iniciar la solución y después debemos hacer que sea igual a cero en la solución final o de lo contrario la solución resultante será no factible. Una manera lógica de lograr que las variables artificiales sean igual a cero en la solución final consiste en penalizarlas en la función objetivo. Para ello se utilizará el “Método de la “M”. En el caso de maximización, la variable artificial se multiplica por “M” y el producto se resta en el lado derecho de de la función objetivo. En el caso de minimización, la variable artificial se multiplica por “M” y el producto se suma en el lado derecho de de la función objetivo. La constante “M” representa un valor positivo muy grande.