INSTITUTO TECNOLÓGICO SUPERIOR DE PÁNUCO
INGENIERÍA INDUSTRIAL
INVESTIGACION DE OPERACIONES I
INVESTIGACIÓN
404
FLORES GONZALEZ STEPHANIE ANAHI
ING. EDGAR JEARVAVI VÁZQUEZ MORENO
VIERNES 11 DE ABRIL DEL 2025
1
2
1. Introducción:
○ Breve descripción de la Programación Lineal (PL)
y su importancia.
○ Introducción al Método Simplex como algoritmo
fundamental para resolver problemas de PL.
○ Mención de la relevancia de los casos especiales
en la aplicación del Método Simplex.
3
2. El Método Simplex:
3.1 Definición y Conceptos Básicos del Método Simplex
El Método Simplex es un algoritmo iterativo fundamental en
la Programación Lineal (PL) que se utiliza para encontrar
la solución óptima de un problema de optimización, donde la
función objetivo y las restricciones son lineales. Fue
desarrollado por George Dantzig a finales de la década de
1940 y ha revolucionado la forma en que se resuelven
problemas de asignación de recursos, planificación de la
producción, logística y muchas otras áreas.
Para comprender el Método Simplex, es esencial definir
algunos conceptos básicos:
● Función Objetivo
La función objetivo es la expresión matemática que se desea
maximizar o minimizar. Representa el objetivo del problema,
que puede ser, por ejemplo, maximizar las ganancias,
minimizar los costos, o maximizar la producción. En
general, se expresa de la siguiente forma:
Z = c₁x₁ + c₂x₂ + ... + cₙxₙ
Donde:
● Z: El valor de la función objetivo.
● x₁, x₂, ..., xₙ: Las variables de decisión.
● c₁, c₂, ..., cₙ: Los coeficientes de la función
objetivo, que representan la contribución de cada
variable al valor de Z.
4
➢ Restricciones
Las restricciones son las limitaciones que deben cumplirse
en el problema. Representan las restricciones de recursos,
las limitaciones de capacidad, las demandas del mercado,
etc. Se expresan como desigualdades o igualdades lineales
que limitan los valores que pueden tomar las variables de
decisión. Toman la forma de:
a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤=≥ b₁ a₂₁x₁ + a₂₂x₂ + ... + a₂ ₙx ₙ ≤=≥ b₂ ... a ₘ₁x₁ + a ₘ₂x₂
+ ... + aₘₙxₙ ≤=≥ bₘ
Donde:
● aᵢⱼ: Los coeficientes de las restricciones.
● bᵢ: Los lados derechos de las restricciones, que
representan los valores límite.
● m: El número de restricciones.
➢ Variables de Decisión
Las variables de decisión (x₁, x₂, ..., xₙ) son las
incógnitas del problema. Representan las cantidades de los
diferentes productos, actividades o decisiones que se
pueden controlar. El objetivo del Método Simplex es
encontrar los valores de estas variables que optimizan la
función objetivo, satisfaciendo todas las restricciones.
➢ Forma Estándar y Forma Canónica
Para aplicar el Método Simplex, es necesario expresar el
problema de Programación Lineal en una forma específica:
● Forma Estándar: Un problema de PL está en forma
estándar si:
5
○ La función objetivo se va a maximizar.
○ Todas las restricciones son desigualdades de tipo "≤".
○ Todas las variables de decisión son no negativas (xᵢ ≥ 0).
○ Para convertir un problema a la forma estándar, se
pueden agregar variables de holgura a las restricciones
de tipo "≤" y restar variables de exceso a las restricciones
de tipo "≥". Las restricciones de igualdad se pueden
convertir en dos desigualdades.
● Forma Canónica: Un problema de PL está en forma
canónica si está en forma estándar y además, para cada
restricción, existe una variable básica que aparece en
esa restricción con coeficiente 1 y en todas las demás
restricciones con coeficiente 0.
● El Método Simplex trabaja iterativamente moviéndose de
una solución factible básica a otra, hasta que se
alcanza la solución óptima. La forma canónica facilita
la identificación de las variables básicas y no
básicas en cada iteración.
3.2 Algoritmo del Método Simplex:
El Método Simplex es un procedimiento iterativo que
comienza con una solución factible básica inicial y se
mueve sistemáticamente a otras soluciones factibles
básicas, mejorando el valor de la función objetivo en cada
iteración, hasta que se alcanza la solución óptima. A
continuación, se describen los pasos del algoritmo:
Paso 1: Convertir el Problema a la Forma Estándar
Si el problema no está en forma estándar, realizar las
siguientes transformaciones:
6
● Si una restricción es de tipo "≥", restará una variable de
exceso.
● Si una restricción es de tipo "≤", sumar una variable de holgura.
● Si la función objetivo es de minimizar, multiplicar
por -1 para convertirla en un problema de
maximización.
● Si alguna variable no es no negativa, sustituirla por
la diferencia de dos variables no negativas.
Paso 2: Obtener una Solución Factible Básica Inicial
Generalmente, se obtiene una solución factible básica inicial haciendo
cero las variables originales del problema y utilizando las variables de
holgura o exceso como variables básicas. Esto corresponde a la
solución donde todas las actividades son cero. Si el problema tiene
restricciones de igualdad o restricciones "≥", puede ser necesario
utilizar técnicas como el Método de la M grande o el Método de las
dos fases para encontrar una solución factible básica inicial.
Paso 3: Construir la Tabla Simplex Inicial
Organizar los coeficientes de la función objetivo, las
restricciones y las variables en una tabla llamada tabla
simplex. La tabla simplex inicial representa la solución
factible básica inicial.
Paso 4: Determinar la Variable de Entrada (Variable que
Entra a la Base)
Seleccionar la variable no básica que entrará a la base en
la siguiente iteración. Esto se hace utilizando el criterio
de entrada:
● Criterio de Entrada (para maximización): Elegir la
variable no básica con el coeficiente más negativo en
la fila de la función objetivo (fila Z). Esta variable
7
es la que tiene el mayor potencial para aumentar el
valor de la función objetivo.
● Criterio de Entrada (para minimización): Elegir la
variable no básica con el coeficiente más positivo en
la fila de la función objetivo (fila Z).
Si todos los coeficientes en la fila Z son no negativos
(para maximización) o no positivos (para minimización), la
solución actual es óptima y el algoritmo termina.
Paso 5: Determinar la Variable de Salida (Variable que Sale
de la Base)
Seleccionar la variable básica que saldrá de la base para
dar paso a la variable de entrada. Esto se hace utilizando
el criterio de salida:
● Criterio de Salida: Para cada restricción (fila) con
un coeficiente positivo en la columna de la variable
de entrada, calcular el cociente entre el lado derecho
de la restricción (bᵢ) y el coeficiente de la variable
de entrada (aᵢⱼ). Elegir la fila con el menor cociente
no negativo. La variable básica correspondiente a esa
fila es la variable de salida.
○ Mín {bᵢ / aᵢⱼ | aᵢⱼ > 0 }
● La fila con el menor cociente se llama fila pivote, y
el elemento en la intersección de la columna pivote y
la fila pivote se llama elemento pivote.
Si todos los coeficientes en la columna de la variable de
entrada son negativos o cero, el problema tiene una
solución no acotada y el algoritmo termina.
Paso 6: Realizar las Operaciones de Pivoteo
8
Realizar operaciones elementales de fila para convertir el
elemento pivote en 1 y todos los demás elementos en la
columna pivote en 0. Estas operaciones transforman la tabla
simplex actual en una nueva tabla simplex que representa
una nueva solución factible básica.
Paso 7: Actualizar la Tabla Simplex
Actualizar todos los valores en la tabla simplex,
incluyendo la fila de la función objetivo y los lados
derechos de las restricciones, utilizando las operaciones
de pivoteo.
Paso 8: Verificar el Criterio de Optimalidad
Verificar si la solución actual es óptima. Esto se hace
utilizando el criterio de optimalidad:
● Criterio de Optimalidad (para maximización): Si todos
los coeficientes en la fila Z son no negativos, la
solución actual es óptima.
● Criterio de Optimalidad (para minimización): Si todos
los coeficientes en la fila Z son no positivos, la
solución actual es óptima.
Si la solución actual no es óptima, regresar al Paso 4 y
repetir el proceso.
Paso 9: Interpretar la Solución Óptima
Una vez que se alcanza la solución óptima, leer los valores
de las variables de decisión y el valor óptimo de la
función objetivo de la tabla simplex final. Interpretar
estos valores en el contexto del problema original.
9
3.3 Ejemplo de Aplicación del Método Simplex:
A continuación, se presenta un ejemplo para ilustrar la
aplicación del Método Simplex.
Ejemplo
Una empresa fabrica dos productos, A y B. Cada producto
requiere ciertas cantidades de dos materias primas, M1 y
M2, como se muestra en la siguiente tabla:
Produc M1 M2 Ganancia por
to (Unidades) (Unidades) Unidad
A 1 2 $5
B 3 1 $4
La empresa tiene 10 unidades de M1 y 8 unidades de M2
disponibles. El objetivo es determinar la cantidad de cada
producto que debe fabricar para maximizar la ganancia
total.
Solución
Paso 1: Formular el Modelo de Programación Lineal
Función Objetivo: Maximizar Z = 5A + 4B
Restricciones:
A + 3B ≤ 10 (M1)
2A + B ≤ 8 (M2)
10
A, B ≥ 0
Paso 2: Convertir el Problema a la Forma Estándar
Agregar variables de holgura S1 y S2:
Maximizar Z = 5A + 4B + 0S1 + 0S2
A + 3B + S1 = 10
2A + B + S2 = 8
A, B, S1, S2 ≥ 0
Paso 3: Construir la Tabla Simplex Inicial
Variable A B S1 S2 Solución
Básica
S1 1 3 1 0 10
S2 2 1 0 1 8
Z -5 -4 0 0 0
Paso 4: Determinar la Variable de Entrada
La variable con el coeficiente más negativo en la fila Z es
A (-5), por lo tanto, A es la variable de entrada.
Paso 5: Determinar la Variable de Salida
Calcular los cocientes:
S1: 10 / 1 = 10
11
S2: 8 / 2 = 4
El menor cociente es 4, correspondiente a S2, por lo tanto,
S2 es la variable de salida. El elemento pivote es 2.
Paso 6: Realizar las Operaciones de Pivoteo
Dividir la fila pivote (S2) por el elemento pivote (2) para
convertir el elemento pivote en 1:
Nueva fila S2: 1 0.5 0 0.5 4
Restar 1 veces la nueva fila S2 de la fila S1:
Nueva fila S1: 0 2.5 1 -0.5 6
Sumar 5 veces la nueva fila S2 a la fila Z:
Nueva fila Z: 0 -1.5 0 2.5 20
Paso 7: Actualizar la Tabla Simplex
Variable A B S1 S2 Solución
Básica
S1 0 2.5 1 - 6
0.5
A 1 0.5 0 0.5 4
Z 0 - 0 2.5 20
1.5
Paso 8: Verificar el Criterio de Optimalidad
12
Todavía hay un coeficiente negativo en la fila Z (-1.5),
por lo que la solución no es óptima. Regresar al Paso 4.
Paso 4 (Repetido): Determinar la Variable de Entrada
La variable con el coeficiente más negativo en la fila Z es
B (-1.5), por lo tanto, B es la variable de entrada.
Paso 5 (Repetido): Determinar la Variable de Salida
Calcular los cocientes:
S1: 6 / 2.5 = 2.4
A: 4 / 0.5 = 8
El menor cociente es 2.4, correspondiente a S1, por lo
tanto, S1 es la variable de salida. El elemento pivote es
2.5.
Paso 6 (Repetido): Realizar las Operaciones de Pivoteo
Dividir la fila pivote (S1) por el elemento pivote (2.5)
para convertir el elemento pivote en 1:
Nueva fila S1: 0 1 0.4 -0.2 2.4
Restar 0.5 veces la nueva fila S1 de la fila A:
Nueva fila A: 1 0 -0.2 0.6 2.8
Sumar 1.5 veces la nueva fila S1 a la fila Z:
Nueva fila Z: 0 0 0.6 2.2 23.6
Paso 7 (Repetido): Actualizar la Tabla Simplex
13
Variable A B S1 S2 Solució
Básica n
B 0 1 0.4 - 2.4
0.2
A 1 0 - 0.6 2.8
0.2
Z 0 0 0.6 2.2 23.6
Paso 8 (Repetido): Verificar el Criterio de Optimalidad
Todos los coeficientes en la fila Z son no negativos, por
lo que la solución actual es óptima.
Paso 9: Interpretar la Solución Óptima
La solución óptima es:
A = 2.8
B = 2.4
Z = 23.6
Esto significa que la empresa debe fabricar 2.8 unidades
del producto A y 2.4 unidades del producto B para maximizar
la ganancia total en $23.6.
14
3.4 Casos Especiales de Programación Lineal:
● Definición y Características
La degeneración en Programación Lineal ocurre cuando una o
más de las variables básicas en una solución factible
básica tienen un valor de cero. Esto puede suceder cuando
una restricción es redundante o cuando hay una intersección
de tres o más restricciones en un punto.
Características de la degeneración:
● Ocurrencia de ceros en la columna de "Solución" de la
tabla Simplex.
● Posibilidad de que el Método Simplex se detenga o
cicle, aunque el valor de la función objetivo no
mejore.
● Dificultad para determinar la variable de salida, ya
que puede haber empates al calcular los cocientes
mínimos.
Cómo manejar la degeneración:
● Perturbación: Una forma de evitar el ciclo es
perturbar ligeramente los valores del lado derecho de
las restricciones (bᵢ) para eliminar los empates.
● Reglas de desempate: Utilizar reglas específicas para
desempatar al elegir la variable de salida, como la
regla lexicográfica o la regla de Bland.
● Revisar el modelo: Verificar si hay restricciones
redundantes que puedan eliminarse.
15
3. Conclusiones:
El Método Simplex es un algoritmo iterativo eficiente para
resolver problemas de Programación Lineal, encontrando la
solución óptima al moverse sistemáticamente entre
soluciones factibles básicas y mejorar el valor de la
función objetivo en cada paso.
El Método Simplex es de gran importancia en la Ingeniería
Industrial, ya que permite optimizar la asignación de
recursos, la planificación de la producción, la gestión de
inventarios, el diseño de rutas de transporte y muchas
otras áreas, lo que conduce a una mayor eficiencia,
reducción de costos y mejora en la toma de decisiones.
Es crucial comprender los casos especiales de la
Programación Lineal, como la degeneración, las soluciones
múltiples, las soluciones no acotadas y las soluciones
infactibles, para aplicar correctamente el Método Simplex y
evitar errores en la interpretación de los resultados. El
manejo adecuado de estos casos especiales garantiza la
obtención de soluciones válidas y útiles para la resolución
de problemas reales.
16
4. Referencias:
Hillier, F. S., & Lieberman, G. J. (2015).
Introducción a la investigación de operaciones (10a
ed.). McGraw-Hill Interamericana Editores, S.A.
6. Fuentes de Información:
https://www.questionpro.com/blog/es/metodo-simplex/
https://www.questionpro.com/blog/es/programacion-lineal/
17
