Método Simplex-1

Método Simplex
El Método Simplex es un método analítico de solución de problemas de programación

lineal, capaz de resolver modelos más complejos que los resueltos mediante el método
gráfico, sin restricción en el número de variables y con una mayor capacidad de análisis de
sensibilidad.
El Método Simplex es un método iterativo que permite ir mejorando la solución en cada

paso. La razón matemática de esta mejora radica en que el método consiste en caminar del
vértice de un poliedro a un vértice vecino de manera que aumente o disminuya (según el
contexto de la función objetivo, sea maximizar o minimizar). Dado que el número de vértices
que presenta un poliedro solución es finito, en la medida en que se pueda satisfacer el
conjunto de restricciones, siempre se hallará como mínimo una solución óptima.
La importancia de la teoría de matrices en el Método Simplex es fundamental, dado que el

algoritmo se basa en dicha teoría para la resolución de sus problemas. De tal manera que
veremos previamente, en qué consiste una matriz identidad.
¿Qué es una matriz identidad?
Una matriz puede definirse como una ordenación rectangular de elementos, (o listado finito
de elementos), los cuales pueden ser números reales o complejos, dispuestos en forma de
filas y de columnas.
La matriz idéntica o identidad es una matriz cuadrada (que posee el mismo número tanto
de columnas como de filas) de orden n que tiene todos los elementos diagonales iguales a
uno (1) y todos los demás componentes iguales a cero (0), se denomina matriz idéntica o
identidad de orden n, y se denota por:
Variables de holgura y exceso: El Método Simplex trabaja basándose en ecuaciones y las

restricciones iniciales que se modelan mediante programación lineal no lo son, para ello hay
que convertir estas inecuaciones en ecuaciones utilizando unas variables denominadas de
holgura y exceso relacionadas con el recurso al cual hace referencia la restricción y que en el
tabulado final representa el «Slack or surplus» al que hacen referencia los famosos
programas de resolución de investigación de operaciones, estas variables adquieren un gran
valor en el análisis de sensibilidad y juegan un rol fundamental en la creación de la matriz
identidad, base del Simplex.
Estas variables suelen estar representadas por la letra «S», se suman (del lado izquierdo de la
restricción) si la restricción es de signo «<= » y se restan (del lado izquierdo de la restricción)
si la restricción es de signo «>=».
Una consideración importante consiste en que el sistema de restricciones debe ser restrictivo,
y esto significa solo una cosa: El lado derecho de las restricciones no puede contener
variables, solo un número mayor o igual a 0.
En el caso en que, por ejemplo, tengamos la siguiente restricción:
2X1 + 1X2 + 1X3 + 2X4 <= -24
Procederemos, primero a convertir la desigualdad en igualdad añadiendo una variable de

holgura:
2X1 + 1X2 + 1X3 + 2X4 + 1S1 = -24
Segundo, a multiplicar ambos lados de la igualdad por (-1), de tal manera que el lado
derecho cumpla con la condición: positivos mayores o iguales a 0.
-2X1 – 1X2 – 1X3 – 2X4 – 1S1 = 24
De esta manera lograríamos estandarizar esta restricción para nuestro algoritmo Simplex.
Paso 1: Modelación mediante programación lineal

 Establecer las variables de decisión
 Establecer la función objetivo
 Encontrar las restricciones
Paso 2: Estandarizar el modelo
Este paso consiste en cumplir las consideraciones del modelo para que se ajuste al método
Simplex:
 Convertir inecuaciones en ecuaciones

 Pasar, de ser necesario, el lado derecho de las restricciones a números positivos.
 Verificar que todas nuestras variables sean de naturaleza no-negativa.
Convertir las inecuaciones en igualdades (Variables de Holgura y Exceso)
En este paso el objetivo es asignar a cada recurso una variable de Holgura, dado que todas
las restricciones son «<=».
Paso 3: Realizar las iteraciones a partir de la tabla Simplex
Paso 4: Realizar las iteraciones necesarias

1) Encontrar la columna pivote, fila pivote y elemento pivote
 Columna pivote: se elige la columna con mayor numero negativo

 Fila pivote: se elige la fila con menor resultado de la columna solución dividido
entre su correspondiente número de la columna pivote.
 Elemento pivote: Numero que resulta de la intersección de la columna pivote
con la fila pivote.
2) Hacer 1 el elemento pivote

3) Hay que hacer 0 todos los números arriba y debajo del elemento pivote
Vemos que en la fila z existe un valor de las variables de decisión que aún es negativo, estas
variables de decisión tienen que tener un valor de mayor o igual a 0.
Se Procede de nuevo a realizar toda la iteración desde el punto 1 al 3
EJEMPLO 1.- Una empresa vitivinícola ha adquirido recientemente un terreno de 110

hectáreas. Debido a la calidad del sol y el excelente clima de la región, se puede vender toda
la producción de uvas Sauvignon Blanc y Chardonay. Se desea conocer cuánto plantar de
cada variedad en las 110 hectáreas, dado los costos, beneficios netos y requerimientos de
mano de obra según los datos que se muestran a continuación:
Suponga que se posee un presupuesto de US$10.000 y una disponibilidad de 1.200 días

hombre durante el horizonte de planificación. Formule y resuelva gráficamente un modelo
de Programación Lineal para este problema. Detalle claramente el dominio de soluciones
factibles y el procedimiento utilizado para encontrar la solución óptima y valor óptimo.
Paso 1.- Modelación mediante programación lineal
Variables de Decisión:
 : Hectáreas destinadas al cultivo de de Sauvignon Blanc

 : Hectáreas destinadas al cultivo de Chardonay
Función Objetivo:
Maximizar 𝑍𝑚𝑎𝑥 = 50𝑥1 + 120𝑥2
Restricciones:
1. 𝑥1 + 𝑥2 ≤ 110
2. 100𝑥1 + 200𝑥2 ≤ 10.000
3. 10𝑥1 + 30𝑥2 ≤ 1.200
Restricción de no negatividad:
𝑥1 , 𝑥2 ≥ 0
Donde las restricciones están asociadas a la disponibilidad máxima de hectáreas para la plantación, presupuesto
disponible, horas hombre en el período de planificación y no negatividad, respectivamente.
Paso 2: Estandarizar el modelo
𝑍 = 50𝑥1 + 120𝑥2 𝑧 = 50𝑥1 + 120𝑥2 + 𝑆1 + 𝑆2 + 𝑆3
Sujeto a:
𝑥1 + 𝑥2 ≤ 110 𝑥1 + 𝑥2 + 𝑆1 = 110
100𝑥1 + 200𝑥2 ≤ 10.000 100𝑥1 + 200𝑥2 + 𝑆2 = 10.000
10𝑥1 + 30𝑥2 ≤ 1.200 10𝑥1 + 30𝑥2 + 𝑆3 = 1200
La variable objetivo la escribimos como: 𝑧 − 50𝑥1 − 120𝑥2 = 0
Paso 3: Realizar la tabla simplex
Basicas Z X Y S1 S2 S3 Solución
z 1 -50 -120 0 0 0 0 fila z
S1 0 1 1 1 0 0 110 fila S1
S2 0 100 200 0 1 0 10000 Fila S2
S3 0 10 30 0 0 1 1200 Fila S3
Paso 4: Realizar las iteraciones necesarias
1) Encontrar la columna pivote, fila pivote y elemento pivote
Basicas z x y s1 s2 s3 Resultado para elegir fila pivote

z 1 -50 -120 0 0 0 0
s1 0 1 1 1 0 0 110 110/1 110
s2 0 100 200 0 1 0 10000 10000/200 50
s3 0 10 30 0 0 1 1200 1200/30 40 menor valor positivo
renglon
pivote 30 es el elemento pivote
2) Hacer 1 el elemento pivote, en este caso hay que dividir entre 30 toda la fila pivote
Basicas z x y s1 s2 s3 Resultado
z 1 -50 -120 0 0 0 0
s1 0 1 1 1 0 0 110
s2 0 100 200 0 1 0 10000
s3 0 1/3 1 0 0 1/30 40 renglon pivote
0*1/30 10*1/30 30*(1/30) 0*(1/30) 0*(1/30) 1*(1/30) 1200*(1/30)

3) Hay que hacer 0 todos los números arriba y debajo del elemento pivote
z 1 -10 0 0 0 4 4800 R1 =120*R4+R1
s1 0 2/3 0 1 0 -0 70 R2 =(-1)R4+R2
s2 0 100/3 0 0 1 (-20/3) 2000 R3 =(-200)*R4+R3
s3 0 1/3 1 0 0 1/30 40 R4 se copia igual
Vemos que en la fila z existe un valor de las variables de decisión que aún es negativo (-10),
estas variables de decisión tienen que tener un valor de mayor o igual a 0.
Se Procede de nuevo a realizar toda la iteración desde el punto 1 al 3
1) Columna, fila y elemento pivote
z 1 -10 0 0 0 4 4800
s1 0 2/3 0 1 0 - 1/30 70 =70/(2/3) 105
s2 0 100/3 0 0 1 (-20/3) 2000 =2000/(100/3) 60 menor valor
s3 0 1/3 1 0 0 1/30 40 =40/(1/3) 120
2) Hacer 1 el elemento pivote, esta vez multiplicando por (3/100)
z 1 -10 0 0 0 4 4800
s1 0 2/3 0 1 0 - 1/30 70
s2 0 1 0 0 3/100 - 1/5 60
s3 0 1/3 1 0 0 1/30 40
3) Hacer 0 todos los elementos arriba y abajo del elemento pivote
z 1 0 0 0 3/10 2 5400 R1 =10*R3+R1
s1 0 0 0 1 -1/50 1/10 30 R2 =(-2/3)*R3+R2
s2 0 1 0 0 3/100 - 1/5 60 R3
s3 0 0 1 0 -1/100 1/10 20 R4 =(-1/3)*R3+R4
La condición de optimabilidad se cumple cuando ninguno de los coeficientes de la

fila z son negativos. De ahí que la última tabla sea la óptima.
Entonces la solución se toman las filas donde dicha variable es igual a 1, es decir
Z= 5400 ; x =60 ; y=20

Método Simplex-1

Cargado por

Copyright:

Formatos disponibles

Método Simplex-1

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Método Simplex-1

Cargado por

Copyright:

Formatos disponibles

Método Simplex

El Método Simplex es un método analítico de solución de problemas de programación

El Método Simplex es un método iterativo que permite ir mejorando la solución en cada

La importancia de la teoría de matrices en el Método Simplex es fundamental, dado que el

¿Qué es una matriz identidad?

Variables de holgura y exceso: El Método Simplex trabaja basándose en ecuaciones y las

En el caso en que, por ejemplo, tengamos la siguiente restricción:

2X1 + 1X2 + 1X3 + 2X4 <= -24

Procederemos, primero a convertir la desigualdad en igualdad añadiendo una variable de

2X1 + 1X2 + 1X3 + 2X4 + 1S1 = -24

-2X1 – 1X2 – 1X3 – 2X4 – 1S1 = 24

Paso 1: Modelación mediante programación lineal

Paso 2: Estandarizar el modelo

 Convertir inecuaciones en ecuaciones

Convertir las inecuaciones en igualdades (Variables de Holgura y Exceso)

Paso 3: Realizar las iteraciones a partir de la tabla Simplex

Paso 4: Realizar las iteraciones necesarias

 Columna pivote: se elige la columna con mayor numero negativo

2) Hacer 1 el elemento pivote

Se Procede de nuevo a realizar toda la iteración desde el punto 1 al 3

EJEMPLO 1.- Una empresa vitivinícola ha adquirido recientemente un terreno de 110

Suponga que se posee un presupuesto de US$10.000 y una disponibilidad de 1.200 días

Paso 1.- Modelación mediante programación lineal

 : Hectáreas destinadas al cultivo de de Sauvignon Blanc

Paso 2: Estandarizar el modelo

𝑍 = 50𝑥1 + 120𝑥2 𝑧 = 50𝑥1 + 120𝑥2 + 𝑆1 + 𝑆2 + 𝑆3

La variable objetivo la escribimos como: 𝑧 − 50𝑥1 − 120𝑥2 = 0

Paso 3: Realizar la tabla simplex

Paso 4: Realizar las iteraciones necesarias

1) Encontrar la columna pivote, fila pivote y elemento pivote

Basicas z x y s1 s2 s3 Resultado para elegir fila pivote

0*1/30 10*1/30 30*(1/30) 0*(1/30) 0*(1/30) 1*(1/30) 1200*(1/30)

Se Procede de nuevo a realizar toda la iteración desde el punto 1 al 3

1) Columna, fila y elemento pivote

2) Hacer 1 el elemento pivote, esta vez multiplicando por (3/100)

3) Hacer 0 todos los elementos arriba y abajo del elemento pivote

La condición de optimabilidad se cumple cuando ninguno de los coeficientes de la

Z= 5400 ; x =60 ; y=20

También podría gustarte

01/30 101/30 30(1/30) 0(1/30) 0(1/30) 1(1/30) 1200*(1/30)