Metodo simplez

SIS 2209 INVESTIGACIÓN OPERATIVA I

FNI-SIS

Cap III EL MÉTODO SIMPLEX
III.1.- SUPOSICIONES DE LA PROGRAMACIÓN LINEAL. III.2.- FORMAS EQUIVALENTES DE LA PROGRAMACIÓN LINEAL III.3.- DEFINICIONES DE SOLUCIONES BÁSICAS FACTIBLES III.4.- ALGORITMO DEL MÉTODO SIMPLEX III.5.- PROBLEMAS DE MINIMIZACIÓN: III.6.- RESOLUCIÓN MÉTODO SIMPLEX POR MEDIO DEL TABLEAU (PIVOTAL) III.7.- METODO DE PENALIZACIONIII.8.- METODO DE LA DOBLE FASE III.9.- CASOS DE EMPATE III.10.- TÉCNICA DE LAS COTAS INFERIOR Y SUPERIOR III.11.- RESOLUCIÓN DE PROBLEMAS DE P.L. CON EL PAQUETE WINQSB

III.1.- SUPOSICIONES DE LA PROGRAMACIÓN LINEAL.
Para representar un problema de optimización como un programa lineal, existen varias suposiciones que están implícitas en la formulación de la programación. A continuación sonexplicadas brevemente. 1. Proporcionalidad Si se dobla el valor de la variable , entonces se dobla su contribución al costo total y a cada una de las restricciones. Ejemplo: La variable , su contribución al costo total es , tenemos . , y su contribución a

la i-ésima restricción Si Si

= 5, entonces el costo de la actividad es 5 = 10, entonces el costo es 10

, y así sucesivamente.Significa que no se logra algún ahorro (costo extra), usando más actividad j.

Ing. César Fernando Escalante Lunario

Pág. 35

SIS 2209 INVESTIGACIÓN OPERATIVA I Tampoco se obtiene ningún costo inicial por empezar la actividad.

FNI-SIS

2. Aditividad. Dice que el costo total es la suma de los costos individuales y que la contribución total a la i-ésima restricción es la suma de lascontribuciones individuales de cada actividad. 3. Divisibilidad. Las variables de decisión pueden dividirse en cualquier nivel fraccional de modo que se permiten valores no enteros para éstas. III.2.- FORMAS EQUIVALENTES DE LA PROGRAMACIÓN LINEAL Tomando la forma canónica de PL Opt Z = Cx AX b X ≥0 Regla 1. a) Max Z = C x es equivalente a Min – Z = - C x b) Min Z = C x es equivalente a Max - Z = - C x Regla2. a) A x b) A x Regla 3. A x = b, puede descomponerse como la intersección de dos desigualdades. y Regla 4. a). La desigualdad Ax < b puede convertirse en igualdad, con la adición del vector S, llamado de holgura. El vector S tiene m componentes, todas no – negativas. b es equivalente a - A x b es equivalente a - A x -b -b

Ing. César Fernando Escalante Lunario

Pág. 36

SIS 2209INVESTIGACIÓN OPERATIVA I Por ejemplo:

FNI-SIS

es equivalente a:

donde el vector holgura es:

b) Toda desigualdad de forma , puede convertirse en igualdad mediante la resta de un vector Y, llamado superfluo o de exceso. Y tiene m componentes, nonegativas. Por ejemplo:

es equivalente a

El vector de exceso o superfluo es:

Regla 5. Una variable no restringida, es aquella que puede tomartoda clase de valores positivos, ceros y negativos y que además pueda expresarse como la resta de dos variables no-negativas. Sea , una variable no-restringida, entonces Donde Se nota que: y

1 Prawda, Juan.. Métodos y Modelos de Investigación de Operaciones. Vol. I. Ed. Limusa. Pág 67, y 68.

Ing. César Fernando Escalante Lunario

Pág. 37

SIS 2209 INVESTIGACIÓN OPERATIVA I

FNI-SISIII.3 DEFINICIONES DE SOLUCIONES BÁSICAS FACTIBLES
Solución factible. Es aquella donde son satisfechas todas las restricciones a la que está sujeta la función objetivo, en otras palabras, el vector columna satisface las restricciones a las que está sometido. =

Solución básica. Es aquella solución factible con no más de m componentes positivas1. Solución básica no degenerada. Es una soluciónfactible básica donde exactamente m componentes del vector columna x, son positivas1. Solución básica degenerada. Es donde hay menos de m componentes positivos del vector x1. Región de factibilidad. Es el área del polígono de soluciones, formada por el conjunto de restricciones a las que se sujeta la función objetivo. Solución óptima. Es una solución, que, además de ser factible, es la que resulta...