INVESTIGACIÓN OPERATIVA I

Programación Lineal – Método algebraico Maximización

Prof. MBA Ing. Luis Sandón

2024 - I

ESCUELA PROFESIONAL:
INGENIERÍA INDUSTRIAL
DEFINICIÓN

En la necesidad de desarrollar un método para resolver problemas de programación lineal de más de dos
variables, los matemáticos implementaron el método algebraico, el que más tarde se perfeccionaría en el
Método Simplex.

El método usa como su principal herramienta, el álgebra, que ligada a un proceso de lógica matemática, da como
resultado el método algebraico.

ESCUELA PROFESIONAL:
INGENIERÍA INDUSTRIAL
 Procedimiento

Paso Paso Paso Paso Paso

1 2 3 4 5

Hallar una solución

básica y factible
(Solución inicial):
Repetir los pasos 2, 3 y 4
Escoger la variable que Escoger la variable que Reorganizar el sistema
a) Expresar las hasta encontrar la
entra sale de ecuaciones
inecuaciones solución
(desigualdades) como
ecuaciones
(igualdades)

b) Hallar una variable

básica para cada ecuación

c) Organizar el sistema de
ecuaciones lineales

ESCUELA PROFESIONAL:
INGENIERÍA INDUSTRIAL
 CASO 1 FORMA ESTANDAR O NORMAL
X2
Max Z = X1 + X2

ST
5 -
2) 5X1 + 3X2 <= 15
3) 3X1 + 5X2 <= 15
4 - 5X1 + 3x2 = 15 Xi >= 0
(0,3)
3 -
B Todo problema de programación lineal
(1.875,1.875) que se formule de la forma Maximice,
2 - con todas sus restricciones <= y con la
C condición de no negatividad, se le llama
ZC Forma Estándar ó Forma Normal
1 - 3X1 + 5x2 = 15
(0,0) (3,0)
D
A X1
-

-
-

1 2 3 4 5
Z = X1 + X2
ESCUELA PROFESIONAL:
INGENIERÍA INDUSTRIAL
 1° ITERACIÓN

Paso 1: Hallar una solución básica factible

Expresar todas la inecuaciones como ecuaciones lineales, para ello se incorporan variables de complemento en las
restricciones 2) y 3) que llamaremos variables de holgura, que permitirán igualar el lado izquierdo al lado derecho de
la inecuación:

2) 5X1 + 3X2 <= 15 5X1 + 3X2 + X3 = 15

3) 3X1 + 5X2 <= 15 3X1 + 5X2 + X4= 15

X3 y X4 son las variables de holgura o relleno, que al adicionarlas al lado izquierdo, establecen la igualdad con el lado
derecho de la inecuación lineal. Las variables de holgura o de relleno, se suman o restan al lado izquierdo de la
inecuación, según convenga para establecer la igualdad.

X1 y X2 se denominan variables de decisión o variables reales.

ESCUELA PROFESIONAL:
INGENIERÍA INDUSTRIAL
Escoger en cada ecuación una variable que sirva como solución inicial al problema y que tome un valor positivo
(>=0). NO son elegibles las variables de decisión o variables reales.

Las variables de holgura o relleno (si las hay), son las primeras a ser escogidas como variables básicas y factibles, lo
que significa que deben tomar un valor mayor o igual a cero (>=0), es decir, las variables básicas factibles, deben
cumplir con la condición de no negatividad.

De no conseguirse una variable de holgura que sea factible, se utiliza el recurso de las variables de excedente. Para
este escenario se usará el método de la gran M.

Al ser X1 y X2 variables no básicas e iguales a cero (0), tanto X3 como X4 son las variables de holgura elegidas como
variables básicas factibles, pues ambas asumen valores positivos:

5X1 + 3X2 + X3 = 15 Hacemos X1 = X2 = 0 X3 = 15, valor >=0

3X1 + 5X2 + X4= 15 Hacemos X1 = X2 = 0 X4 = 15, valor >=0

ESCUELA PROFESIONAL:
INGENIERÍA INDUSTRIAL
Con la información anterior se organiza el sistema de ecuaciones como sigue:

(1) Z –X1 – X2 = 0 En la ecuación (1) Z es la variable básica.

(2) 5X1 + 3X2 + X3 = 15 En cada ecuación existe una y solo una variable básica con
(3) 3X1 + 5X2 + X4= 15
coeficiente 1

Si X1 = X2 = 0 , entonces Z = 0, X3 = 15 y X4 = 15. Esto es una solución básica factible.

En cada ecuación existe una y solo una variable básica con coeficiente 1, lo que permite leer su valor de manera
automática al lado derecho

X1 = 0 Variable de decisión ó variable real => Variable no básica

X2 = 0 Variable de decisión ó variable real => Variable no básica
X3 = 15 Variable de holgura ó relleno => Variable básica
X4 = 15 Variable de holgura ó relleno => Variable básica
Z=0 Variable de decisión ó variable real => Variable básica
ESCUELA PROFESIONAL:
INGENIERÍA INDUSTRIAL
Paso 2: Escoger la variable que entra
Se evalúa si existe una solución mejor que brinde un mejor resultado que la solución básica factible.

Para ello en la ecuación (1) del sistema de ecuaciones se despeja Z y evaluamos ¿cúal es la variable que al aumentar
hace que Z aumente más?

Como regla general, la variable que entra es aquella que al crecer hace que Z crezca más, ya que el objetivo es
Maximizar el valor de Z. En otras palabras, la variable que entra será aquella que tenga el coeficiente más positivo. Si
fuera un problema de minimización, se escoge la variable que haga que Z disminuya más, es decir, la que tenga el
coeficiente más negativo.

Si no hubiese variable que entra, significa que nos encontramos en la solución óptima.

En el caso descrito, la velocidad de crecimiento tanto de X1 como de X2 es 1 (coeficiente de las variables X1 y X2). En
esta situación de empate se escoge al azar. Se elige arbitrariamente como variable que entra a X1.

ESCUELA PROFESIONAL:
INGENIERÍA INDUSTRIAL
Paso 3: Escoger la variable que sale
Se despeja las variables básicas X3 y X4 en las ecuaciones (2) y (3) en función a las variables no básicas:

(2) X3 = 15 - 5X1 - 3X2

(3) X4= 15 - 3X1 + 5X2

Recordar que de las variables no básicas X1 y X2 ya fue escogida X1 como variable que entra a la base, entonces X2
seguirá siendo variable no básica e igual a cero:

(2) X3 = 15 - 5X1
(3) X4= 15 - 3X1

Para todos los casos, las variables básicas (X3, X4) siempre quedarán despejadas en función de la variable escogida
para entrar (X1).

Para continuar se debe evaluar ¿cuál es la variable básica (X3, X4) que restringe más el crecimiento de la variable
que entra (X1)?

ESCUELA PROFESIONAL:
INGENIERÍA INDUSTRIAL
Para ello hacemos que las variables básicas X3 y X4 asuman su menor valor factible, es decir cero, y se evalúa el valor
que asume la variable escogida para entrar (X1).

(2) X3 = 15 - 5X1
X3 deja crecer a X1 , como máximo hasta 3
15 – 5X1 = 0
X1 = 3

(3) X4= 15 - 3X1

X4 deja crecer a X1 , como máximo hasta 5
15 – 3X1 = 0
X1 = 5

La variable básica que sale es aquella que restringa más el crecimiento de la variable que entra, en este caso X3.

En caso de empate, se dirime arbitrariamente, cuidando la factibilidad de las variables, es decir, que todas sean
positivas ( >=0 ).

En el caso de ser un problema de minimización, esta regla de selección es igual.

ESCUELA PROFESIONAL:
INGENIERÍA INDUSTRIAL
Paso 4: Reorganizar el sistema de ecuaciones

Al entrar X1 y salir X3 , el sistema de ecuaciones ya no tendrá una sola variable básica en cada fila con coeficiente
uno, es decir:
(1) Z – X1 – X2 = 0 Variables básicas: Z y X1
(2) 5X1 + 3X2 + X3 = 15 Variable básica: X1
(3) 3X1 + 5X2 + X4 = 15 Variables básicas: X1 y X4

En la ecuación (2) se encuentra la variable que entra X1 y la variable que sale X3. En ésta fila solo queda como
variable básica X1 y se busca que tenga coeficiente igual a 1. Para ello, se multiplica toda la fila por el inverso del
coeficiente de X1, es decir por 1/5. A la ecuación resultante se le llama Fila Pivote, la cual se utiliza posteriormente
para eliminar a X1 de las ecuaciones (1) y (3) y así quedarnos con sólo una variable básica por fila.

(2) (5X1 + 3X2 + X3) *(1/5) = 15 *(1/5)

(2) X1 + 3/5X2 + 1/5X3 = 3 Fila Pivote

ESCUELA PROFESIONAL:
INGENIERÍA INDUSTRIAL
Para encontrar el nuevo sistema de ecuaciones en el que en cada fila figure una y solo una variable básica con
coeficiente uno, de tal forma que se pueda leer automáticamente su valor en el término independiente de cada
ecuación (1) y (3), multiplicamos la fila pivote por el valor necesario para eliminar X1 (la variable que entra) de cada
una de las otras ecuaciones. De esta manera se obtienen las nuevas ecuaciones.

(1) Z – X1 – X2 = 0 (3) 3X1 + 5X2 + X4 = 15

(2) (X1 + 3/5X2 + 1/5X3) *(1) = 3 *(1) (2) (X1 + 3/5X2 + 1/5X3) *(-3) = 3 *(-3)

(1) Z – 2/5 X2 + 1/5X3 = 3 (3) 3X1 + 5X2 + X4 = 15

(2) -3X1 - 9/5X2 - 3/5X3 = -9

(3) 16/5X2 -3/5X3 + X4 = 6

Con la información anterior se reorganiza el sistema de ecuaciones como sigue:

(1) Z – 2/5 X2 + 1/5X3 = 3
Si X2 = X3 = 0 , entonces Z = 3, X1 = 3 y X4 = 6
(2) X1 + 3/5X2 + 1/5X3 = 3

(3) 16/5X2 - 3/5X3 + X4 = 6

ESCUELA PROFESIONAL:
INGENIERÍA INDUSTRIAL
En cada ecuación existe una y solo una variable básica con coeficiente 1, lo que permite leer su valor de manera
automática al lado derecho

X1 = 3 Variable de decisión ó variable real => Variable básica

X2 = 0 Variable de decisión ó variable real => Variable no básica
X3 = 0 Variable de holgura ó relleno => Variable no básica
X4 = 6 Variable de holgura ó relleno => Variable básica
Z=3 Variable de decisión ó variable real => Variable básica

Características del sistema de ecuaciones a tener en cuenta:

• En cada fila hay una y solo una variable básica con coeficiente uno.
• En la función objetivo (ecuación (1)), la variable básica siempre es Z y estará acompañada por las variables no
básicas.
• Los términos independientes (lado derecho), siempre serán los valores de las variables básicas para cada
ecuación.

ESCUELA PROFESIONAL:
INGENIERÍA INDUSTRIAL
 FORMA ESTANDAR O NORMAL

X2
Solución básica: (0,0) y Z = 0 (Punto A)

1° Iteración: (3,0) y Z = 3 (Punto D)

Max Z = X1 + X2
5 -
¿es la solución óptima?
ST 4 - 5X1 + 3x2 = 15
Si encontramos una variable que al entrar
hace que la función objetivo crezca más, debe
2) 5X1 + 3X2 <= 15
(0,3) repetirse los pasos 2, 3 y 4 hasta que no se
3) 3X1 + 5X2 <= 15 3 - encuentre una variable que haga que Z
B crezca, cuando ello ocurra estamos en el
Xi >= 0
(1.875,1.875) óptimo.
2 -
C
ZC
1 - 3X1 + 5x2 = 15
(0,0) (3,0)
D
A X1
-

-
-

-
1 2 3 4 5
Z = X1 + X2 ESCUELA PROFESIONAL:
INGENIERÍA INDUSTRIAL
 2° ITERACIÓN

Paso 2: Escoger la variable que entra

(1) Z – 2/5 X2 + 1/5X3 = 3 (1) Z = 2/5 X2 – 1/5X3 + 3 Variable que entra: X2

(2) X1 + 3/5X2 + 1/5X3 = 3 (2) X1 + 3/5X2 + 1/5X3 = 3

(3) 16/5X2 -3/5X3 + X4 = 6 (3) 16/5X2 - 3/5X3 + X4 = 6

Paso 3: Escoger la variable que sale

Se despeja las variables básicas X1 y X4 en las ecuaciones (2) y (3) en función a las variables no básicas (X2 y X3):

(2) X1 = 3 - 3/5X2 - 1/5X3 Como X2 ya fue escogida como variable (2) X1 = 3 - 3/5X2
que entra a la base, entonces X3 seguirá
(3) X4 = 6 - 16/5X2 - 3/5X3 siendo variable no básica e igual a 0 (3) X4 = 6 - 16/5X2

Se calcula que variable X1 o X4 limita más el crecimiento de X2 igualándolos a 0

(2) X1 = 0 = 3 - 3/5X2 X2 = 5

(3) X4 = 0 = 6 - 16/5X2 X2 = 15/8 Variable que sale: X4

ESCUELA PROFESIONAL:
INGENIERÍA INDUSTRIAL
 Paso 4: Reorganizar el sistema de ecuaciones
En la ecuación (3) se encuentra la variable que entra X2 y la variable que sale X4. En ésta fila solo queda como variable básica X2 y
se busca que tenga coeficiente igual a 1.

(1) Z – 2/5 X2 + 1/5X3 = 3

(2) X1 + 3/5X2 + 1/5X3 = 3

(3) 16/5X2 -3/5X3 + X4 = 6 (3) (16/5X2 -3/5X3 + X4 = 6) *(5/16) = 6 *(5/16)

(3) X2 - 3/16X3 + 5/16X4 = 15/8 Fila Pivote

En la ecuación (1) y (2), multiplicamos la fila pivote por el valor necesario para eliminar X2 (la variable que entra)

(1) Z – 2/5 X2 + 1/5X3 = 3 (2) X1 + 3/5X2 + 1/5X3 = 3

(3) (X2 - 3/16X3 + 5/16X4) *(2/5) = 15/8 *(2/5) (3) (X2 - 3/16X3 + 5/16X4) *(-3/5) = 15/8 *(-3/5)

(1) Z – 2/5 X2 + 1/5X3 = 3 (2) X1 + 3/5X2 + 1/5X3 = 3

(3) 2/5X2 - 3/40X3 + 1/8X4 = 3/4 (3) - 3/5X2 + 9/80X3 - 3/16X4 = -9/8
(1) Z + 1/8X3 + 1/8X4 = 15/4 (2) X1 + 5/16X3 - 3/16X4 = 15/8
ESCUELA PROFESIONAL:
INGENIERÍA INDUSTRIAL
Con la información anterior se reorganiza el sistema de ecuaciones como sigue:
X2
(1) Z + 1/8X3 + 1/8X4 = 15/4

(2) X1 + 5/16X3 - 3/16X4 = 15/8

Max Z = X1 + X2
5 - (3) X2 - 3/16X3 + 5/16X4 = 15/8

ST 4 - 5X1 + 3x2 = 15
Si X3 = X4 = 0 , entonces Z = 15/4, X1 = 15/8 y X2 = 15/8
2) 5X1 + 3X2 <= 15
3) 3X1 + 5X2 <= 15 (0,3)
3 - ¿es la solución óptima?
Xi >= 0
B
(1.875,1.875)
2 -
C
ZC
1 - 3X1 + 5x2 = 15
(0,0) (3,0)
D
A X1
-

-
-

-
1 2 3 4 5
Z = X1 + X2 ESCUELA PROFESIONAL:
INGENIERÍA INDUSTRIAL
 3° ITERACIÓN

Paso 2: Escoger la variable que entra

(1) Z + 1/8X3 + 1/8X4 = 15/4 (1) Z = 15/4 - 1/8X3 - 1/8X4

(2) X1 + 5/16X3 - 3/16X4 = 15/8 (2) X1 + 5/16X3 - 3/16X4 = 15/8

(3) X2 - 3/16X3 + 5/16X4 = 15/8 (3) X2 - 3/16X3 + 5/16X4 = 15/8

Ninguna variable al crecer hace que Z crezca, por lo tanto estamos en la solución óptima.

Solución óptima
Variables de decisión ó reales Variables de holgura o relleno
X1 = 15/8 = 1.875 X3 = X4 = 0
X2 = 15/8 = 1.875
X3 y X4 representa la holgura del recurso disponible para las
Z = 15/4 = 3.75 restricciones (2) y (3).

Al ser X3 = X4 = 0 significa que los recursos se utilizan en su totalidad,

por lo tanto, ambas restricciones se les llama activas o vinculantes.
ESCUELA PROFESIONAL:
INGENIERÍA INDUSTRIAL
 ESCUELA PROFESIONAL:
INGENIERÍA INDUSTRIAL