Método gráfico y Método

simplex
Programación lineal
Pamela Marissa Silva Díaz
 Table of contents

Método gráfico
01 Definición y metodología de aplicación

Método simplex
Definición y etapas
02 Soluciones
Casos especiales
Concepto Dualidad
Interpretación económica dual
Manejo de sensibilidad y aplicación de variables
COMPARATIVA ENTRE AMBOS MÉTODOS
El método gráfico consiste en trazar las restricciones del problema en un plano cartesiano
y encontrar la solución óptima.

El método simplex es un algoritmo que utiliza iteraciones para encontrar la solución

óptima.
01 Método gráfico
Definición
● Consiste en graficar las ecuaciones
correspondientes a las restricciones en
coordenadas, siendo cada variables
representada en uno de los ejes,
identificando así la zona factible de
solución.
● Sólo podrá manejarse problemas que
tengan como máximo 3 variables.
 ¿Para qué sirve?
El método gráfico se utiliza para resolver Las gráficas son útiles para:
problemas que involucran dos variables de ● Comparar cantidades o frecuencias
decisión. Se aplica en la investigación de entre grupos o categorías
operaciones y en la programación lineal. ● Identificar tendencias y relaciones entre
variables
En la vida cotidiana, las gráficas son una ● Representar la evolución de una o
herramienta que permite analizar, comparar y varias magnitudes en el tiempo
comprender datos de manera visual y rápida. ● Presentar información de manera clara
y precisa
● Destacar las diferencias entre datos
● Ilustrar el mensaje de un texto
● Contar historias a partir de datos
 Etapas o procedimiento
Representar cada
Plantear el problema variable del problema
en el eje cartesiano

Hallar solución del Trazar ecuaciones de

problema la función objetivo Z
 PROCEDIMIENTO

● ZONA FACTIBLE: espacio en el que se encuentra una de las soluciones posibles,

● CUADRANTE: espacio en el que se graficarán las ecuaciones.
PROCEDIMIENTO
PROCEDIMIENTO
GRAFICANDO
01 Método simplex
Definición
● Toma como posible solución un punto
correspondiente a uno de los vértices de la
región factible de solución, siendo la
primera aproximación el origen, de aquí, en
las siguientes iteraciones el simplex se irá
moviendo hacia otros vértices hasta que
alguno de ellos sea óptimo, siendo
entonces la solución del problema.
 ¿Para qué sirve?
El método simplex es un algoritmo que se utiliza para El método simplex es útil para resolver problemas
resolver problemas de programación lineal, y es útil de optimización, es decir, aquellos en los que se
para tomar decisiones informadas en diversos busca maximizar o minimizar algo.
campos.
Algunas de las ventajas del método simplex son:
El método simplex se aplica en la vida real en áreas ● Es eficaz para resolver problemas con
como: múltiples variables y restricciones
● Economía ● Es adaptable y puede utilizarse para
● Ingeniería problemas de maximización o minimización
● Investigación ● Permite identificar soluciones no factibles o
● Operaciones empresariales ilimitadas
● Gestión de operaciones ● Ayuda a tomar decisiones informadas
● Planificación de recursos empresariales
 Etapas
ETAPA INICIAL ETAPA ITERATIVA ETAPA DE PRUEBA DE
OPTIMALIDAD
Consiste en dar la primera Implica que el método busque una
solución factible en el vértice mejor solución a la anterior en Se logra cuando la solución de un
correspondiente al origen. otro vértice. vértice es mejor que la de los
vértices adyacentes
(3 primeros pasos del (4o. Paso del procedimiento)
procedimiento) (5o. Paso del procedimiento)
 Metodología simplex.
ETAPA 1
1. Convertir las desigualdades de las Tipo de Coeficiente de Coeficiente de
restricciones en igualdades mediante la restricción la variable de la variable
holgura artificial
incorporación de variables de holgura
(variables de excedente) y/o variables Menor o igual +1 0
artificiales (ficticias), las cuales se agregarán que
a las restricciones con un coeficiente cuyo
valor puede determinarse en la sig. Tabla: Mayor o igual -1 +1
que

VARIABLE DE HOLGURA: Es la cuantía de recursos (materias primas, financiación, Igualdad 0 +1

etc.) que está disponible, pero no se utiliza. Cuando tiene holgura positiva, y por
tanto existe un excedente de recursos, la restricción se denomina "inactiva": ese
recurso no se está consumiendo en su totalidad, por tanto no limita el programa de Aproximadam +1 y -1 0
producción.
ente

VARIABLE ARTIFICIAL. Una variable artificial es un truco matemático para convertir

inecuaciones «>=» en ecuaciones, o cuando aparecen igualdades en el problema original,
la característica principal de estas variables es que no deben formar parte de la solución,
dado que no representan recursos.
 Metodología simplex
2. Incluir las variables de holgura y
artificiales en la ecuación objetivo con un
coeficiente que será 0 en el caso de las
variables de holgura H y M para las
artificiales, donde se supone que M es un
valor muy grande.

A M se agrega con signo negativo por tratarse de un problema de maximización,

para casos de minimización M será positiva
 Metodología simplex
3. Formar la primera tabla:

a) Expresar las ecuaciones de las restricciones en función de

sus coeficientes.
b) Agregar el renglón objetivo arriba del renglón de
variables, el cual incluirá los coeficientes de las variables
en la función objetivo.
 Metodología simplex
c) Buscar la primera solución en función de las variables cuyos
coeficientes son +1 en la parte de identidad.

VARIABLES BÁSICAS. Variables que están en la zona de

solución.
VARIABLES NO BÁSICAS. Aquellas que no aparecen en la
zona de solución y valen 0.
Metodología simplex
● Creamos la tabla simplex.

● Se obtiene la primera solución

 Metodología simplex.
ETAPA 2

4. a) Determinar la columna clave o pivote, la cual es la que contiene el número índice más
negativo (en caso de empate seleccionar al azar)

b) Determinar la renglón clave o pivote, será aquel que tenga el menor cociente de los
obtenidos al dividir el elemento respectivo de la columna de las constantes entre el
elemento correspondiente de la columna clave. Sólo se toman en cuenta los renglones de
las restricciones.

c) Determinar el número clave o elemento pivote, que será aquel elemento que pertenece a
la vez (intersección) al renglón y la columna clave.
 Metodología simplex.
ETAPA 3

5. Repetir el paso 4 hasta encontrar un valor

óptimo (z con sólo valores positivos).
EJEMPLO:
EJEMPLO:
EJEMPLO:
EJEMPLO:
EJEMPLO:
EJEMPLO:
EJEMPLO:
EJEMPLO:
 MÉTODO SIMPLEX
CASOS ESPECIALES

EMPATE EN COLUMNA PIVOTE. En este caso seleccionar cualquier columna que se desee,
lo único que podría afectar es el número de iteraciones (veces) que se repetirá el proceso.

EMPATE EN RENGLÓN PIVOTE: Existen reglas para determinar cuál se elige, sin embargo se
recomienda tomarlo al azar, ya que es poco usual tener algún conflicto en los problemas
prácticos.

QUE NO HAYA VARIABLE BÁSICA DE SALIDA (Z NO ACOTADA): esto sucede cuando

todos los elementos de la columna clave (pivote) son menores o iguales a cero en alguna
tabla intermedia del desarollo de metodología simplex.
 MÉTODO SIMPLEX
CASOS ESPECIALES

TÉRMINOS NEGATIVOS EN EL SEGUNDO MIEMBRO DE LAS ECUACIONES: hasta ahora

únicamente se ha visto en el segundo miembro de las restricciones. Si pasa, todo se
multiplica por -1 y se invierte el sentido de las desigualdades.

PRECIOS SOMBRA: representan la relación de aumento que tendría la función objetivo por
el hecho de aumentar en una unidad la constante de una restricción dada, o sea el
incremento en el recurso correspondiente para esa restricción. Es decir, cuando al final de la
ecuación, queda algún coeficiente en las restricciones.
 CONCEPTO DE DUALIDAD

Para todo problema de maximización de programación lineal,

habrá otro problema asociado de minimización, y por otro parte,
para todo problema de minimización, habrá otro problema
asociado de maximización.
Al primer problema se le conoce como primario y al problema asociado se le conoce como
dual.
 IMPORTANCIA DE DUALIDAD

a) Puede ahorrar un número considerable de cálculos.

b) Tiene relación con el análisis de sensibilidad, ya que muestra cómo
puede cambiar la función objetivo en las diferentes condiciones del
problema.
c) Proporciona información sobre la manera óptima de aplicar los
recursos.
INTERPRETACIÓN ECONÓMICA
DEL DUAL

Proporciona una visión sobre

la manera óptima de utilizar
los recursos de que se
disponen.
EJEMPLO
INTERPRETACIÓN ECONÓMICA DEL DUAL
 ANÁLISIS DE SENSIBILIDAD

Consiste en estudiar los cambios que sufre la función

objetivo ante modificaciones en cualesquiera de los
parámetros del problema: coeficientes de las variables de
las restricciones, contribuciones de las variables en la
función objetivo, etc.