toto por nada

MATE 3012

Método Simplex – maximización
estándar

Programación Lineal - vocabulario
1. Función objetivo - una función que expresa la cantidad a
ser maximizada o minimizada en términos de las otras
variables.
2. Restricción - una condición o limitación que se aplica a la
elección de valores para las variables.
3. Problema de maximización estándar - un problema de
programación linealpara la cual la función objetiva
función debe ser maximizada y todas las restricciones son
desigualdades de la forma “menor-o-igual-a (≤)
4. Variable de holgura (slack variable) - una variable que se
utiliza para convertir un " menor-o-igual-a” en una
ecuación.
5. Matriz aumentada - una matriz que representa un
sistema de ecuaciones lineales.

Programación Lineal – vocabulario(continuación).
6. Solución óptima - el conjunto de variables con valores
distintos de cero que maximizan o minimizan la función
objetiva.
7. Variable básica - una variable que forma parte de la
solución óptima del problema .
8. Columna pivote - la columna de la tabla simplex que
representa una variable que entrará en la solución
óptima.
9. Fila pivote - la fila de una tabla simplex que representala
variable que sale de la solución óptima
10. elemento pivote o pivote- el elemento que se encuentra
en la intersección de la columna pivote y la fila pivote.

Problema de maximización estándar
Un problema de maximización de programación lineal
está en la forma estándar, si la función objetiva
𝑤 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + 𝑐3 𝑥3 + ⋯ + 𝑐 𝑛 𝑥 𝑛
debe ser minimizada, sujeto a las restricciones

Elprocedimiento básico utilizado para resolver este tipo
de problema es aplicar el método Simplex.

Problema de Programación Lineal
La empresa Cannon Hill produce muebles: sillas y
mesas.
• Cada mesa toma 4 horas de
mano de obra y 2 horas de acabado.
• Cada silla requiere 3horas de carpintería y 1
hora de terminaciones.
• Hasta ahora se tienen disponibles 240 horas de
tiempo decarpintería y 100 horas de tiempo de
acabado.
• Cada mesa producida da una ganancia de $70 y
cada silla una ganancia de $50.
• ¿Cuántas sillas y mesas debe hacer para
maximizar ganancias?

Construcción del Modelo
• Variables de decisión
• x: cantidad de mesas construidas en Cannon Hill
• y: cantidad de sillas construidas en Cannon Hill

• Función-objetiva
• El objetivo es maximizar elganancia.

P  70x  50y

• Conjunto de restricciones
4 x + 3 y ≤ 240
2 x + y ≤ 100

(restricción de mano de obra para carpintería)
(restricción de mano de obra para acabado)

x ≥ 0 , y ≥ 0 (restricción de mano de no-negatividad)

Procedimento de Método Simplex
Armar la tabla simplex
Paso 1: cada desigualdad (≤) se convierte en un ecuación
introduciendo una variable de holgura (slackvariable).
Las variables de holgura representan las horas que sobran para
carpintería y acabado sino se utilizan todas.

4𝑥 + 3𝑦 + 𝑠1 = 240
2𝑥 + 𝑦 + 𝑠2 = 100
𝑥 ≥ 0, 𝑦 ≥ 0, 𝑠1 ≥ 0, 𝑠2 ≥ 0

• Paso 2: Despejar la función objetiva(todas las
variables al lado izquierdo).

4𝑥 + 3𝑦 + 𝑠1 = 240
2𝑥 + 𝑦 + 𝑠2 = 100
𝑃 − 70𝑥 − 50𝑦 = 0
𝑥 ≥ 0, 𝑦 ≥ 0, 𝑠1 ≥ 0, 𝑠2 ≥ 0

• Paso 3: Tabla para cálculos.4𝑥 + 3𝑦 + 𝑠1 = 240
2𝑥 + 𝑦 + 𝑠2 = 100
𝑃 − 70𝑥 − 50𝑦 = 0

En las columnas aparecerán todas las variables del
problema y en las filas, los coeficientes de las
ecuaciones obtenidas.
Variables que
entran a
la
solución

x

y

s1

s2

s1

4

3

1

0

240

s2

2

1

0

1

100

P

-70

-50

0

0

0

constantes

1ra Iteración:
Paso 1: Deteminarcuál variable debe entrar a la solución
Para escoger la variable de decisión que entra a la solución óptima,
observamos la fila que muestra los coeficientes de la función objetiva
y escogemos la variable con el coeficiente más negativo.
(Esta es la variable que aporta más a las ganancias.)
columna pivote
Variables que
entran a
la
solución

x

y

s1

s2

s1

4

3

1

0...