Investigación de Operaciones

UNIDAD 2
PROGRAMACIÓN LINEAL

EL MÉTODO SIMPLEX

Samuel Oporto Díaz

METODO DE GAUSS - JORDAN
 Gauss-Jordan
• Los métodos de eliminación de Gauss y de Gauss-Jordan nos permiten obtener las
soluciones (en caso de haberlas) de los sistemas de ecuaciones lineales (SEL).

• Estos métodos se basan en la idea de que las soluciones del SEL que se obtiene al realizar
operaciones elementales fila o columna son las mismas que las del SEL original.

Samuel Alonso, Oporto Díaz 3

 Matriz Ampliada
• Considerando un SEL con n incógnitas cuya forma matricial es , donde:

• A, es la matriz formada por los coeficientes de las ecuaciones.

• x, es el vector columna formado por todas las incógnitas del SEL ( )
• b, es la columna de los términos independientes de las ecuaciones.

• La matriz ampliada del SEL, que es la matriz que tiene la matriz A a la izquierda y el vector b
a la derecha, separados por una línea: (A | b).

• El sistema tiene la matriz ampliada

Samuel Alonso, Oporto Díaz 4

 Matriz Escalonada

Samuel Alonso, Oporto Díaz 5

 Gauss-Jordan
El método consiste en aplicar:
• operaciones elementales fila, es decir, cualquier fila se puede multiplicar por cualquier
número (distinto de cero) o se le puede sumar o restar cualquier otra fila multiplicada o no
por cualquier número.
• No se puede restar una fila a ella misma.
• Se puede intercambiar el orden de las filas (por ejemplo, intercambiar las dos primeras
filas).

• El proceso debe aplicarse hasta que se obtenga la matriz en forma escalonada (método de
Gauss) o en forma escalonada reducida (método Gauss-Jordan) de la matriz ampliada.

Samuel Alonso, Oporto Díaz 6

 Ejercicio 1

Samuel Alonso, Oporto Díaz 7

 Ejercicio 2

Samuel Alonso, Oporto Díaz 8

 Ejercio 3
Resolver el siguiente sistema:

Samuel Alonso, Oporto Díaz 9

 Ejercicio 4

Samuel Alonso, Oporto Díaz 10

SIMPLEX
 Simplex
El método simplex es un algoritmo iterativo para
resolver problemas de programación lineal, donde se
busca obtener la solución óptima de la función objetivo
que logre cumplir el conjunto de restricciones.

El Método Simplex hace uso de la propiedad de que la

solución óptima de un problema de PL se encuentra en
un vértice de la región de puntos factibles.

• Algoritmo: conjunto de reglas bien definidas,

La búsqueda secuencial del algoritmo se basa en la ordenadas y finitas que permite realizar una
evaluación progresiva de estos vértices hasta encontrar actividad mediante pasos sucesivos que no
generen dudas a quien deba realizar dicha
el óptimo. actividad.
• Iteración: acto de repetir un proceso con el
objetivo de alcanzar un resultado. Cada repetición
Este algoritmo fue desarrollado en el año 1947 por el es una "iteración", y los resultados de una
matemático norteamericano George Dantzig. iteración se utilizan como punto de partida para la
siguiente iteración.

Samuel Alonso, Oporto Díaz 12

 Procedimiento
Los pasos a seguir en el método simplex son:
1. Definir el problema en la forma estándar y generar nuestra matriz.
2. Determinar la solución básica inicial.
3. Seleccionar la variable de entrada utilizando la condición de optimalidad. Si no se puede
seleccionar una variable de entrada, quiere decir que estamos en la condición óptima y
finalizan las iteraciones. De otro modo se continúa con el siguiente paso.
4. Seleccionar la variable de salida utilizando la condición de factibilidad.
5. Actualizar nuestra matriz realizando las operaciones de Gauss-Jordan. Volver al paso
número 3.

El método Simplex “tradicional” o “básico” que abordaremos en esta entrada, se utiliza para
los problemas de programación lineal donde todas las restricciones son del tipo menor e igual
(≤).

Samuel Alonso, Oporto Díaz 13

FORMA ESTANDAR
 Forma Estándar
1. El lado derecho de las ecuaciones debe ser no-negativo.

2. Todas las restricciones deben de convertirse a ecuaciones.

3. Todas las variables deben ser no-negativas.

Samuel Alonso, Oporto Díaz 15

 Paso 1. Lado derecho, no negativo
• Sea la función de optimización

• Donde x1, x2 … xn son las variables del

problema.

• Verificar que todas las restricciones

tienen el lado derecho no negativo.

Es decir:
• b1, b2 … bm ≥ 0

Samuel Alonso, Oporto Díaz 16

 ¿Qué hago si el lado derecho de la restricción es negativo?
Cuando el término independiente de la restricción es negativo, se debe multiplicar por -1 a
toda la restricción para convertir el valor del lado derecho en positivo.

• Esta multiplicación también afectará al signo de la restricción de la siguiente forma:

– Si la restricción es del tipo mayor igual (≥), se deberá cambiar a menor igual (≤).
– En caso la restricción sea del tipo menor igual (≤), se deberá cambiar a mayor igual (≥).
– Si la restricción es una igualdad, el signo se mantiene.

• Un caso especial es cuando el término independiente de la restricción es 0 y el signo es

mayor igual (≥); en dicha situación, podemos multiplicar la restricción por (-1) para
convertirla en menor igual (≤).

• Esto nos servirá para no utilizar variables artificiales como veremos posteriormente.

Samuel Alonso, Oporto Díaz 17

 Paso 2. Convertir restricciones en igualdades
Para convertir las restricciones en igualdades va a depender de su signo:
restricción es menor igual (≤) restricción es mayor igual (≥) restricción es igual (=)
introducir una variable no negativa se debe restar una variable de agregar una variable artificial de la
llamada de holgura y que son exceso y así mismo agregar una siguiente forma
auxiliares para el problema variable artificial.

Samuel Alonso, Oporto Díaz 18

 Paso 3. Variables no negativas
• Para convertir una variable en no negativa.
• Crear una nueva variable, que sea el negativo de la otra.
-x’’
x = -x’’
• En caso de que la variable sea no restringida.
• Crea dos variables.
-x’’ x’

Samuel Alonso, Oporto Díaz 19

 Ejercicio 1
• Convertir a su forma estándar

Samuel Alonso, Oporto Díaz 20

 Ejercicio 1
1. Lado derecho, no negativo

Samuel Alonso, Oporto Díaz 21

 Ejercicio 1
2. Conversión a ecuaciones

Samuel Alonso, Oporto Díaz 22

 Ejercicio 1
3. No negativa

Samuel Alonso, Oporto Díaz 23

 Ejercicio 1
No restringida

Samuel Alonso, Oporto Díaz 24

 Ejercicio 2
Convertir a su forma básica

Samuel Alonso, Oporto Díaz 25

 Ejercicio 2

Samuel Alonso, Oporto Díaz 26

 Ejercicio 3
• Convertir a su forma estándar

Samuel Alonso, Oporto Díaz 27

 Ejercicio 3

Samuel Alonso, Oporto Díaz 28

SOLUCION BASICA INICIAL
 Matriz de trabajo

Samuel Alonso, Oporto Díaz 30

 Elementos de la matriz de trabajo
En nuestra matriz podemos identificar lo siguiente:
• Vector de Costes: Es el vector que contiene los coeficientes de todas las variables de la
función objetivo. En la parte inferior del vector se indican las variables en orden.
• Vector Solución: En esta columna se coloca la solución básica inicial y se va actualizando
conforme se realizan las iteraciones. En la columna Cb se indica el coeficiente que
corresponde a cada variable en el vector de costes. Así mismo siempre se iniciará con las
variables de holgura en la base cuando el problema no tenga variables artificiales.
• Coeficientes Restricciones: Se colocan los coeficientes de las restricciones en el mismo
orden en que fueron formuladas. La columna R contiene a los términos independientes
también conocido como vector de recursos.
• Vector de costes reducidos: También conocido como precios sombra. Este vector se calcula
multiplicando el vector solución por los coeficientes de las restricciones y se resta el vector
de costes.

• Al no existir variables artificiales, el vector de costes reducidos será igual al vector de costes
multiplicado por “-1”.

Samuel Alonso, Oporto Díaz 31

 Solución Básica Inicial
• El método simplex parte de un vértice de la
región factible, es decir, un punto extremo.
• Con cada iteración se avanza de vértice en
vértice hasta llegar a la solución óptima.
• En la matriz elaborada vemos que la solución
básica inicial que sería S1=35, S2=18 y S3=26
(cada variable del vector solución se iguala al
valor que se encuentra en la columna R.

• Estas variables se denominan variables básicas.

• El valor de Z inicial también se muestra en la
columna R que es.
• Las variables que no se encuentran en la base se
denominan variables no básicas y en este caso
serían X1 y X2. Ambas tienen un valor de 0.

Samuel Alonso, Oporto Díaz 32

SELECCIONAR LA VARIABLE DE ENTRADA
UTILIZANDO LA CONDICIÓN DE
OPTIMALIDAD
 Condición de Optimalidad
La condición de optimalidad consiste en verificar si la solución actual que tenemos en nuestra
matriz es la óptima o si se puede mejorar. Se verifica de la siguiente manera:
• En un problema de maximización si todos los coeficientes del vector de costes reducidos
son mayores o iguales que cero, quiere decir que estamos en el punto óptimo y finaliza el
problema.
• En un problema de minimización si todos los coeficientes del vector de costes reducidos
son menores o iguales que cero, quiere decir que estamos en el punto óptimo y finaliza el
problema.

• Siguiendo con el ejemplo, siendo el problema de maximización, podemos ver que en el

vector de costes reducidos existen valores negativos, lo que significa que no estamos en el
óptimo.
• Eso quiere decir que debemos iniciar las iteraciones seleccionando la variable de entrada.

Samuel Alonso, Oporto Díaz 34

 Variable de Entrada
• La variable de entrada hace referencia a una de las variables no básicas que ingresará a la
base y formará parte de la solución del problema.
• Los criterios para seleccionar la variable de entrada dependen si el problema es de
maximización o minimización:
– Para problemas de maximización, la variable de entrada será la variable no básica con el
coeficiente más negativo en el vector de costes reducidos.
– Para problemas de minimización, la variable de entrada será la variable no básica con el
coeficiente más positivo en el vector de costes reducidos.

• La columna donde está ubicada la variable se denomina columna pivote.

• En el ejemplo nuestra variable de entrada sería X1 dado que tiene el valor más negativo en
el vector de costes reducidos, es decir “-3”:

Samuel Alonso, Oporto Díaz 35

 Variable de Entrada

Samuel Alonso, Oporto Díaz 36

SELECCIONAR LA VARIABLE DE SALIDA CON
LA CONDICIÓN DE FACTIBILIDAD
 Condición de Factibilidad
• La condición de factibilidad, para cualquier problema ya sea de maximización o
minimización, se verifica evaluando los valores de los coeficientes de la matriz de
restricciones que se encuentran en la columna que corresponde a la variable de entrada.

• Se debe verificar que al menos uno de sus valores sea mayor que 0 para obtener nuestra
variable de salida.

• Si no se cumple esa condición significa que el problema tiene solución ilimitada no acotada.

Samuel Alonso, Oporto Díaz 38

 Variable de Salida
• Para determinar la variable que sale de la
base se debe dividir el valor
correspondiente a la columna R con su
respectivo coeficiente en la columna de la
variable de entrada (siempre y cuando
este coeficiente sea estrictamente
positivo).

• De los resultados obtenidos, el menor

valor corresponde a la fila que contiene a
la variable de salida.
• Esta fila la llamaremos fila pivote.

• La variable de salida sería S2.

Samuel Alonso, Oporto Díaz 39

 Elemento Pivote
• El número que se encuentra al
cruzar la fila pivote y la columna
pivote es el elemento pivote; en
nuestro caso sería 3:

Samuel Alonso, Oporto Díaz 40

ACTUALIZAR LA MATRIZ
 Actualizar la matriz
• Dado el elemento pivote, realizaremos las operaciones de Gauss-Jordan para formar
nuestra matriz identidad. El nuevo valor de cada fila se calculará de la siguiente manera:
• Para la fila pivote: El nuevo valor se obtendrá dividiendo el valor actual entre el elemento
pivote.
• Nuevo Valor Fila Pivote = Valor Actual Fila Pivote / Elemento Pivote
• Para las otras filas: El nuevo valor se calcula restando del valor actual, la multiplicación del
elemento de la fila que se encuentra en la columna pivote por el nuevo valor calculado en
la fila pivote.

• Nuevo Valor = Valor Actual – (Elemento Fila Columna Pivote*Nuevo Valor Fila Pivote).
• Para entenderlo mejor, continuaremos resolviendo el ejemplo. Iniciaremos con la fila
pivote:

Samuel Alonso, Oporto Díaz 42

 Actualizar la matriz

Samuel Alonso, Oporto Díaz 43

 Actualizar la matriz
fila de S1:

Samuel Alonso, Oporto Díaz 44

 Actualizar la matriz

Samuel Alonso, Oporto Díaz 45

 Actualizar la matriz
• fila S3

Samuel Alonso, Oporto Díaz 46

 Actualizar la matriz

Samuel Alonso, Oporto Díaz 47

 Actualizar la matriz
• Finalmente, en la fila Z tenemos:

Samuel Alonso, Oporto Díaz 48

 Actualizar la matriz

Samuel Alonso, Oporto Díaz 49

 Actualizar la matriz
• La matriz resultante sería:

• Cómo puedes ver la posición

donde se encontraba nuestro
elemento pivote ahora es 1 y los
elementos que lo acompañan en la
columna se convierten en 0. Es así
que empezamos a formar nuestra
matriz identidad.

Samuel Alonso, Oporto Díaz 50

PASO 3
 paso 3
• Cómo existen valores negativos en el vector de costes reducidos, podemos seguir
optimizando.

• El único valor negativo es -4, por lo que la variable que ingresará es X2.

• Para elegir la variable que va a salir, dividimos cada valor de la columna R por su
contraparte de la columna X2 (este último valor debe ser positivo)
• 23/(19/3) = 69/19 = 3.632
• El valor en la columna X2 es negativo por lo que no se toma en cuenta.
• 14/(16/3) = 21/8 = 2.625

• El menor valor se encuentra en la fila de S3, por lo que es la variable que saldrá de la base.
El elemento pivote es 16/3.
• Realizamos nuevamente las iteraciones obteniendo el siguiente resultado:

Samuel Alonso, Oporto Díaz 52

PREGUNTAS
soportod@uni.edu.pe