Gauss-Jordan

Con el método Gauss-Jordan se efectúa un cimblo de base empleando raciones de cálculo:
1. Ecuación pivote:
nueva ecuación pivote = ecuación pivote ÷ elemento pivote

2. Las demás ecuaciones, incluyendo Z
nueva ecuación = (ecuación anterior)+ Coeficiente de la columna entrante *nueva ecuación pivote

Estos dos tipos de operaciones de cálculo necesariamente generan la nueva solución básica, al sustituir la variable entrante en todos los renglones, excepto en la ecuación pivote.

Al aplicar los cálculos del tipo 1 a a tabla anterior, dividimos la ecuación .5, entre el elemento pivote 2. Como x toma el lugar de y, en la columna básica, los cálculos del tipo 1 cambiarán la tabla inicial como se muestra a continuación.

Nótese que la columna “solucíón” da el nuevo valor de x5 (= 4), que es igual a la razón mínima de la condición de factibilidad.
Para completar la tabla, realizamos los siguientes cálculos de tipo 2.

Las siguientes operaciones de Gauss-jordan producirán la nueva tabla:
(i) Nueva ecuación pivote (s,) = ecuación s1 anterior ÷ (3/2).
(u) Nueva ecuación z = ecuación z anterior — (—1/2) y nueva ecuación pivote.
(iii) Nueva ec. - cc. x anterior — (1/2) y nueva ec. pivote.
(iv) Nueva cc. .y = cc s anterior — (3/2) y nueva cc. pivote.
(y) Nueva cc. s4 = cc. s anterior — (1) y nueva ec. pivote.

La solución da como resultado x6 34 y x, 14 (punto Gen la figura 3-2). El valor de ¿ha aumentado de 12 en la tabla anterior a 124. El incremento (124 — 12) = 2/3 es el resultado de que x1 aumente de 0 a 4/3, donde cada incremento de una unidad contribuye en 1/2 a la función objetivo. Por lo tanto, el incremento total en a es igual a (4/3) x (t/2) = 2/3.
La última tabla es óptima porque ninguna de tas variables no básicas tiene un coeficiente negativo en la función z. Esto completa tos cálculos del método símplex.

Metodo SIMPLEX primal

El método símplex primal parte de una solución básica factible (punto extremo) y se continúa iterando a través de soluciones básicas factibles sucesivas hasta alcanzar el óptimo. La figura 3-1 ilustra la aplicación de este proceso al modelo Reddy Mikks. El proceso comienza en el origen extremo (punto A) y se mueve a lo largo del borde AB del espacio de soluciones hasta el punto extremo adyacente B (iteración 1). De 5B se mueve a lo largo del borde BC hasta el punto extremo adyacente C (iteración
2), que es el óptimo. Obsérvese que el procedimiento no es capaz de cortar a través del espacio de soluciones (por ejemplo, de A a C) sino que siempre debe moverse a lo largo de bordes entre puntos extremos adyacentes.

¿Cómo se expresa algebraicamente el procedimiento iterativo indicado antes? Todo foque tenemos que hacer es mostrar cómo se identifican los puntos extremos, tales como el A, B y C, sin utilizar la gráfica de] espacio de soluciones. Consideremos el modelo Reddy Mikks dado enseguida en su forma estándar:
Maximizar Z= 3x5 + 2x1 + Os3 + 0.s + Os, + 054

sujeto a

El modelo tiene m = 4 ecuaciones y n = 6 variables. De esta manera, el número de variables no básicas (nulas) debe ser igual a 6 — 4 = 2. Si escogemos e, O y x, = O como las variables no básicas, inmediatamente, y sin ningún cálculo, obtenemos la solución básica factibles1 = 6, .s5 = 8, s3 = 1 54 = 2 (el punto origen A en la figura 3-1). Esta solución básica representa la solución inicial (o iteración) del método símplex. El valor objetivo correspondiente se determina expresando la función objetivo en la siguiente forma (a la que nos referiremos como la ecuación z):
8 — 3X — 2.r1 = O

Puesto que x5 y x1 en A son cero, el valor asociado de z lo da automáticamente el segundo miembro de la ecuación anterior (= O). La fácil determinación algebraica de la solución básica inicial en el modelo Reddy Mikks se debe a que:
1. Cada ecuación tiene una variable de holgura.
2. Los segundos miembros de las restricciones son no negativos.

La primera propiedad garantiza que el número de holguras es igual al número de ecuaciones. Así, las variables restantes pueden usarse como variables no básicas (cero). Como por la segunda propiedad los segundos miembros de las ecuaciones son no negativos, la solución básica resultante es automáticamente factible, como se necesita en el método simplex primal.

El siguiente paso lógico a la identificación de la solución inicial, es investigar el desplazamiento a una nueva solución básica. Desde el punto de vista de la optimización, nos interesa pasar a otra solución básica, sólo si podemos discernir mejoras en el valor de la función objetivo. Primero, téngase en cuenta que una nueva solución básica se asegura sólo al hacer básica, por lo menos, una de las variables actuales no básicas (cero). En el método símplex se hace el cambio de las variables no básicas, una a la vez, Intuitivamente, tal variable no básica puede llevarse a a solución sólo si mejora el valor de la función objetivo, En términos del modelo Reddy Mikks, .r y x son no básicas (= O) en A. Observando la ecuación z objetivo
z—3x—2x, O

constatamos que un incremento unitario de x aumentará a z en 3 y, un incremento unitario dex1, acrecentará a z en 2. Puesto que se trata de una maximización, cualquiera de las dos variables puede mejorar el valor objetivo. Sin embargo, para generar una regla no ambigua de cálculo, el método simplex utiliza un procedimiento heuristico; osca, en el caso de una maximización, la variable no básica seleccionada es aquella con el coeficiente más negativo en la ecuación z objetivo. Utilizando tal procedimiento heurístico, se espera (pero no se garantiza), que el método símplex produzca los ‘saltos” máximos en el valor objetivo al pasar de una iteración a otra, alcanzando así el óptimo en el menor número de iteraciones. La aplicación de esta condición al modelo Reddy Mikks da como resultado considerar a como la variable que entra, o variable entrante.

Condición de optimidad: La variable entrante en una maximización (en una minimización) es la variable no básica, con el coeficiente más negativo (más positivo) en la ecuación z objetivo. Un empate puede romperse arbitrariamente. El óptimo se alcanza cuando todos los coeficientes no básicos en a ecuación z son no negativos (no positivos).

Condición de factibilidad: tanto en problemas de maximización como de minimización, la variable saliente es la variable básica actual, con la menor intersección (razón mínima con denominador estrictamente positivo) en la dirección de la variable entrante. Un empate se rompe arbitrariamente.

Estamos listos para enunciar los pasos iterativos formales del método símplex primal:
Paso O: Usando la forma estándar (con los segundos miembros no negativos), determine una solución inicial básica factible.
Paso 1: Seleccione una variable entrante entre las variables actuales no básicas, usando la condición de optimidad.
Paso 2: Seleccione la variable saliente entre las variables actuales básicas, usando la condición de factibilidad.
Paso 3: Determine los valores de las nuevas variables básicas, haciendo a la variable entrante básica y a la variable saliente no básica. Vuelva al paso 1.

Ejemplo 3.3-1
Usaremos el modelo Reddy Mikks para explicar los detalles de cálculo del método simplex primal. Esto exigirá expresar el problema en la forma estándar Una manera conveniente de resumir las ecuaciones es por medio de la siguiente tabla:
Esta tabla corresponde a la solución básica inicial del modelo. La información en la

Tabla se lee de la siguiente manera. La columna “básica” identifica las variables básicas actuales y’, s,, y, y y4, cuyos valores se dan en la columna “solución”. Esto supone implícitamente que las variables no básicas y5 y y, (aquellas no presentes en la columna “básica”) tienen valor cero. El valor correspondiente de la función objetivo es Z = 3 x O + 2 x o + Ox 6 + Ox $ + Ox 1 + Ox 2 = O, como se muestra en la columna solución.
Al aplicar la condición de optimidad, tiene el coeficiente más negativo en la ecuación a y por ello, se escoge como la variable entrante. La condición de factibilidad muestra que .5 corresponde a la menor intersección, por lo que deberá salir de la solución.
Después de identificar las variables entrantes y salientes, necesitamos determinar la nueva solución básica que debe incluir ahora a y,, y5, y, y 54 Esto se logra aplicando el método de eliminación de Causs-1ordan. El método comienza identificando la columna debajo de la variable entrante y5 como la columna entrante o de entrada. El renglón asociado con la variable saliente se denominará ecuación pivote, y el elemento en la intersección de la columna de entrada y la ecuación pivote se denominará elemento pivote. La siguiente tabla resume estas definiciones:

Soluciones basicas

Consideremos el modelo estándar de PL con m ecuaciones y n incógnitas. Una solución básica asociada se determina haciendo n-m variables iguales a cero y luego, resolviendo las ni ecuaciones con las restantes ro variables, siempre que la solución resultante exista y sea única. Para ilustrar esto, consideremos el siguiente sistema de ecuaciones: /

2x + x2 + 4x, + x4 = 2
x1 + 2x, + 1V3 + x4 = 3

En este ejemplo tenemos ni = 2 y n = 4. Entonces, una solución básica está asociada con n — ni 4 — 2 2 variables nulas, Esto significa que el conjunto de ecuaciones dado tiene n!/Íni! (o — ni) = 4!/2!21 = 6 posibles soluciones básicas, Decimos soluciones básicas “posibles” porque algunas combinaciones pueden no conducir en absoluto a soluciones básicas. Por ejemplo, considérese la combinación donde x y x4 se hacen igual a cero. En este caso el sistema se reduce a

2x, + 4x, = 2
x1 + 2x, = 3

Las dos ecuaciones son inconsistentes y, por consiguiente, no existe una solución. 1_a conclusión es que x, y x, no pueden constituir una solución básica y por ello, no corresponden a un punto extremo.
En forma alternativa, consideremos el caso donde x3 y x4 se hacen igual a cero. Esto da las ecuaciones
2x + x, = 2
x1 + 2x, = 3


La solución única correspondiente (x 1/3, x2 4/3), junto con .r, O y x4 = O, define una solución básica y, por lo tanto, un punto extremo del espacio de soluciones de la PL.

En la PL, nos referimos a las n — m variables que se hacen iguales a cero como variables no básicas y, a las no variables restantes como variables básicas (por supuesto, siempre que exista una solución única). Se dice que una solución básica es factible si todos los valores de su solución son no negativos. Un ejemplo de este caso es la solución factible básica (x1 = 1/3, y5 = 4/3, x, O, a4 = O). Para ilustrar el caso de una solución básica infactible, consideremos la combinación donde las variables no básicas son x1 O y x3 = O. Las ecuaciones anteriores dan

4x, + x4 = 2
2x, + .v4 = 3

La solución básica correspondiente es (.r, — /2, a4 4), que es infactible porque x, es negativa.

En la resolución del problema de PL, nos interesarán las soluciones básicas, tanto factibles como infactibles. Específicamente veremos que todas las iteraciones del método símplex primal siempre están asociadas sólo con soluciones básicas factibles. Por otra parte,. el método símplex dual trata con soluciones básicas infactibles hasta la última iteración, donde la solución básica asociada debe ser factible. En esencia, el método símplex primal sólo trata con puntos extremos, en tanto que en el método símplex dual todas las iteraciones, excepto la última, están asociadas con puntos extremos infactibles. Al final, ambos métodos dan soluciones básicas factibles como lo estipula la condición de no negatividad del modelo de PL.

CREACION DEL METODO SIMPLEX

En esta sección presentamos los detalles del método símplex. Comenzamos con la elaboración de la forma estándar necesaria para representar el espacio de soluciones de la PL, por medio de un Sistema de ecuaciones simultáneas. El resto de la exposición muestra cómo se determinan selectivamente las soluciones básicas sucesivas, con el fin de alcanzar el punto de solución óptima en un número finito de iteraciones.

Conforme se estudie el resto de este capitulo, el lector se relacionará con dos variantes del método símplex: los algoritmos del método símplex primal y los del símplex dual. En apariencia los dos métodos parecen ser diferentes. Esto no es el caso y, de hecho, lo fundamental de los dos algoritmos se basa en la idea que los puntos extremos del espacio de soluciones son completamente identificables por las soluciones básicas del modelo de PL. Básicamente, los dos algoritmos parecen ser diferentes porque están diseñados para sacar ventaja de la estructuración inicial especial del modelo de PL. Este punto se enfatizará conforme presentemos los detalles de los dos procedimientos.

FORMA ESTANDAR DEL MODELO DE PL
Un modelo de PL puede incluir restricciones de los tipos <-, = y >- Además, las variables pueden ser no negativas o irrestrictas (no restringidas) en signo. Para desarrollar un método de solución general, el problema de programación lineal debe ponerse en un formato común, al que llamamos la forma estándar. Las propiedades de la forma de PL estándar son

1. Todas las restricciones son ecuaciones (con los segundos miembros no negativos, si el modelo se resuelve por medio del método símplex primal)
2. Todas las variables son no negativas.
3. La función objetivo puede ser la maximización o la minimización.

Como se explicará después, la segunda propiedad que exige que todas las variables sean no negativas, es crucial en el desarrollo de los métodos símplex (primal y dual).
Ahora demostremos cómo se puede poner cualquier modelo de PL en el formato estándar.

A. Restricciones
1. Una restricción del tipo <- (>-) puede convertirse en una ecuación mediante la suma de una variable de holgura a (o restando una variable de exceso de) el primer miembro de la restricción.
Por ejemplo, en la restricción
x1 + 2x2 <- 6

Metodo Simplex

El método gráfico demuestra que la PL óptima está siempre asociada con un punto extremo o de esquina, del espacio de soluciones. Esta idea conduce precisamente a la creación del método simplex. Básicamente, lo que hace el método simplex es trasladar la definición geométrica del punto extremo a una definición algebraica. Durante la presentación del método simplex, deberá tenerse en mente este detalle.

¿Cómo identifica el método simplex los puntos extremos en forma algebraica? Como paso inicial, el método simplex necesita que cada una de las restricciones esté en una forma estándar especial, en la que todas las restricciones se expresan como ecuaciones, mediante la adición de variables de holgura o de exceso, según sea necesario. Este tipo de conversión conduce normalmente a un conjunto de ecuaciones simultáneas donde el número de variables excede al número de ecuaciones, lo que generalmente significa que las ecuaciones dan un número infinito de puntos solución (compárese con el espacio de soluciones gráficas). Los puntos extremos de este espacio pueden identificarse algebraicamente por medio de las soluciones básicas del sistema de ecuaciones simultáneas. De acuerdo con la teoría del álgebra lineal, una solución básica se obtiene igualando a cero las variables necesarias con el fin de igualar el número total de variables y el número total de ecuaciones para que la solución sea única, y luego se resuelve el sistema con las variables restantes. Fundamentalmente, la transición del procedimiento gráfico al algebraico se basa en la validez de la siguiente relación importante:

puntos extremos = soluciones básicas

Al no tener un espacio de soluciones gráficas que nos guie hacia el punto óptimo, necesitamos un procedimiento que identifique en forma inteligente las soluciones básicas promisorias. Lo que hace el método simplex, es identificar una solución inicial y luego moverse sistemáticamente a otras soluciones básicas que tengan el potencial de mejorar el valor de la función objetivo. Finalmente, la solución básica correspondiente a la óptima será identificada, con lo que termina el proceso de cálculo. En efecto, el método símplex es un procedimiento de cálculo iterativo donde cada iteración está asociada con una solución básica.
La determinación de una solución básica en el método símplex, implica detalles tediosos de cálculo. Tales detalles no deben distraernos de la idea fundamental del método: generar soluciones básicas sucesivas, de manera que nos conduzcan al punto
- extremo óptimo. Todos los detalles de cálculo son secundarios a esta idea básica, y así es como debemos tratarlos.

Naturaleza de la investigación de operaciones

¿Qué es la investigación de operaciones? Una manera de tratar de responder a esta pregunta es dar una definición. Por ejemplo, la investigación de operaciones puede describirse como un enfoque científico de la torna de decisiones que requiere la operación de sistemas organizacionales.

Sin embargo, esta descripción, al igual que los intentos anteriores de dar una definición, es tan general que se puede aplicar a muchos otros campos. Por lo tanto, tal vez la mejor forma de entender la naturaleza única de la investigación de operaciones sea examinar sus características sobresalientes.

Como su nombre lo dice, la investigación de operaciones significa ‘hacer investigación sobre las operaciones’. Esto dice algo tanto del enfoque como del área de aplicación. Entonces, la investigación de operaciones se aplica a problemas que se refieren a la conducción y coordinación de operaciones o actividades dentro de una organización. La naturaleza de la organización es esencialmente inmaterial y, de hecho, la investigación de operaciones se ha aplicado en los negocios, la industria, la milicia, el gobierno, los hospitales, etc. Así, la gama de aplicaciones es extraordinariamente amplia. El enfoque de la investigación de operaciones es el mismo del método científico. En particular, el proceso comienza por la observación cuidadosa y la formulación del problema y sigue con la construcción de un modelo científico (por lo general matemático) que intenta abstraer la esencia del problema real. En este punto se propone la hipótesis de que el modelo es una representación lo suficientemente precisa de las características esenciales de la situación como para que las conclusiones (soluciones) obtenidas sean salidas también para el problema real. Esta hipótesis se verifica y modifica mediante las pruebas adecuadas. Entonces, en cierto modo, la investigación de .operaciones incluye la investigación científica creativa de las propiedades fundamentales de las operaciones. Sin embargo, existe más que esto. En particular, la investigación de operaciones se ocupa también dela administración práctica de la organización. Así, para tener, éxito, deberá también proporcionar conclusiones positivas y claras, que pu.eda usar el tomador de decisiones cuando las necesite.

Influjo de la investigación (de operaciones)

La investigación de operaciones ha tenido un creciente influjo en la administración de las organizaciones. l5nto el número como la variedad de sus aplicaciones continúa creciendo con rapidez y no se ve que vaya a disminuir. De hecho, a excepción de las computadoras, parece que la extensión de este influjo no tiene rival con otros desarrollos recientes.

Después del éxito de la investigación de operaciones durante la Segunda Guerra Mundial, los servicios militares americano e inglés continuaron trabajando con grupos activos en este campo, muchas veces a diferentes niveles de mando. Como resultado, ahora existe un gran número de personas llamadas “investigadores de operaciones militares” que aplican estos enfoques a los problemas de defensa nacional. Por ejemplo, dedican sus esfuerzos a la planeación táctica de los requerimientos y uso de los sistemas de armamento, al igual que estudian los complejos problemas de la asignación
e integración del trabajo. Algunas de sus técnicas implican ideas bastante elaboradas dentro de las ciencias políticas, las matemáticas, la economía, la teoría de probabilidad y estadística.

La investigación de operaciones también se usa ampliamente en otro tipo de organizaciones incluyendo la industria y el comercio. Casi todas las organizaciones más grandes del mundo (alrededor de una docena) y una buena proporción de las industrias más pequeñas cuentan con grupos bien establecidos de investigación de operaciones. Muchas industrias, incluyendo la aérea y de proyectiles, la automotriz, la de comunicaciones, computación, energía eléctrica, electrónica, alimenticia, metalúrgica, minera, del papel, del petróleo y del transporte, han empleado la investigación de operaciones. Las instituciones financieras, gubernamentales y de salud están incluyendo cada vez más estas técnicas.

Origen de la investigaciòn de operaciones

Desde el advenimiento de la Revolución Industrial, el mundo ha sido testigo de un crecimiento sin precedentes en el tamaño y la complejidad de las organizaciones. Los pequeños talleres artesanales se convirtieron en las actuales corporaciones de miles de millones de dólares. Una parle integral de este cambio revolucionario fue el gran aumento en a división del trabajo yen la separación de las responsabilidades administrativas en estas organizaciones. Los resultados han sido espectaculares. Sin embargo, junio con los beneficios, el aumento en el grado de especialización creó nuevos problemas que ocurren hasta la fecha en muchas empresas Uno de estos problemas es la tendencia de muchos de los componentes de una organización a convenirse en imperios relativamente autónomos, con sus propias metas y sistemas de valores, perdiendo con esto la visión de cómo sus actividades y objetivos encajan con los de toda la organización. Lo que es mejor para un componente, puede ir en detrimento de otro, de manera que pueden terminar trabajando con objetivos opuestos. Un problema relacionado con esto es que, conforme la complejidad y la especialización crecen, se vuelve más difícil asignar los recursos disponibles a las diferentes actividades de la manera más eficaz para la organización como un todo. Este tipo de problemas, y la necesidad de encontrar la mejor forma de resolverlos, proporcionaron el ambiente adecuado para el surgimiento de la investigación de operaciones.

Las raíces de la investigación de operaciones se remontan a muchas décadas, cuando se hicieron los primeros intentos para emplear el enfoque científico en la administración de una empresa. Sin embargo, el inicio de la actividad llamada investigación de operaciones, casi siempre se atribuye a los servicios militares prestados a principios de la Segunda Guerra Mundial. Debido a los esfuerzos bélicos, existía una necesidad urgente de asignar recursos escasos a las distintas operaciones militares ya las actividades dentro de cada operación, en la forma más efectiva. Por lodo esto, las administraciones militares americana e inglesa hicieron un llamado a un gran número de científicos para que aplicaran el enfoque científico a éste y a otros problemas de estrategia y táctica. De hecho, se les pidió que hicieran investigación sobre operaciones (militares). Estos equipos de científicos fueron los primeros equipos de investigación de operaciones. Sus esfuerzos contribuyeron de una manera definitiva al triunfo del combate aéreo inglés en la isla de Campaña en el Pacífico, de la batalla del Atlántico Norte y de muchas otras.

Estimulados por el evidente éxito de la investigación de operaciones en lo militar, los industriales comenzaron a interesarse en este nuevo campo. Como la explosión industrial seguía su curso al terminarla guerra, los problemas causados por el aumento de la complejidad y especialización dentro de las organizaciones pasaron a primer plano. Comenzó a ser evidente para un gran número de personas, incluyendo a los consultores industriales que habían trabajado con o para los equipos de investigación de operaciones durante la guerra, que estos problemas eran básicamente los mismos que los enfrentados por la milicia, pero en un contexto diferente.
De esta forma, la investigación de operaciones comenzó a introducirse en la industria, los negocios y el gobierno. Para 1951, ya se había introducido por completo en Gran Bretaña y estaba Estados Unidos en proceso de hacerlo. Desde entonces, se ha desarrollo todo con rapidez