Guia Completo do Método Simplex
Traduzido por
ScribdTranslationsGuia Completo do Método Simplex
Traduzido por
ScribdTranslationsMétodo Simplex
O Método Simplex é um método analítico de solução de problemas deprogramação linear,capaz
de resolver modelos mais complexos do que os resolvidos por meio dométodo gráfico sem restrição no
número de variáveis.
O Método Simplex é um método iterativo que permite melhorar a solução a cada passo.
A razão matemática dessa melhoria reside no fato de que o método consiste em caminhar do vértice de um poliedro
a um vértice vizinho de maneira que aumente ou diminua (de acordo com o contexto da função objetivo, seja
maximizar o minimizar), dado que el número de vértices que presenta un poliedro solución es finito
sempre haverá solução.
¿Qué es una matriz identidad?
Uma matriz pode ser definida como uma ordenação retangular de elementos, (ou lista finita de
elementos), los cuales pueden ser números reales o complejos, dispuestos en forma de filas y de
colunas.
A matriz identidade ou identidade é uma matriz quadrada (que possui o mesmo número de
colunas como de linhas) de ordem que tem todos os elementos diagonais iguais a um (1) e todos
os demais componentes iguais a zero (0), é denominado matriz idêntica ou identidade de ordem n, e se
denota por:
A importância da teoria das matrizes no Método Simplex é fundamental, uma vez que o algoritmo se
baseia-se nessa teoria para a resolução de seus problemas.
Considerações importantes ao utilizar o Método Simplex
Variáveis de folga e excesso
O Método Simplex trabalha com base em equações e nas restrições iniciais que são modeladas
mediante programação linear não o são, para isso é necessário converter essas inequações em equações
utilizando umas variáveis denominadas de folga e excesso relacionadas com o recurso ao qual faz
refere-se à restrição e que no tabulado final representa o «Slack ou superávit» ao qual fazem
referencia los famosos programas de resolución de investigación de operaciones, estas variables
adquirem um grande valor na análise de sensibilidade e desempenham um papel fundamental na criação da
matriz identidad base del Simplex.
Estas variáveis geralmente são representadas pela letra «S», somam-se se a restrição for de sinal «<= ».
e se subtraem se a restrição for de sinal '>='.
Por exemplo:
Variável artificial / Método da "M"
Uma variável artificial é um truque matemático para converter iniquações ">=" em equações, ou
quando aparecem igualdades no problema original, a característica principal dessas variáveis é que
não devem fazer parte da solução, uma vez que não representam recursos. O objetivo fundamental de
essas variáveis são a formação da matriz identidade.
Estas variables se representa por la letra«A»,siempre se suman a las restricciones, su coeficiente es M
(por esto se le denomina Método de la M grande, donde M significa un número demasiado grande muy
pouco atraente para a função objetivo), e o sinal na função objetivo vai contra o sentido da
mesma, ou seja, em problemas de Maximização seu signo é menos (-) e em problemas de Minimização
seu signo é (+), repetimos com o objetivo de que seu valor na solução seja zero (0).
Método Simplex passo a passo
O problema
Paso 1: Modelación mediante programación lineal
Variáveis:
X1 = Cantidad de mesas a producir (unidades)
X2 = Cantidad de sillas a producir (unidades)
X3 = Cantidad de camas a producir (unidades)
X4 = Cantidad de bibliotecas a producir (unidades)
Restricciones:
2X1+ 1X +2 1X +32X <=424
2X1+ 2X +2 1X <=
3 20
2X3+ 2X <=
4 20
4X4<= 16
Função Objetivo:
ZMÁXIMO
=20000X +
1 20000X +220000X + 320000X 4
Paso 2: Convertir las inecuaciones en ecuaciones
Neste passo, o objetivo é atribuir a cada recurso uma variável de Folga, dado que todos os
restrições são "<=".
2X1+ 1X +2 1X +32X + 1S
4 + 0S
1 + 0S2+ 0S =
3 24 4
2X1+ 2X +2 1X +30X + 0S
4 + 1S
1 + 0S2+ 0S =
3 20 4
0X1+ 0X +2 2X +32X + 0S
4 + 0S
1 + 1S2+ 0S =
3 20 4
0X1+ 0X +2 0X +34X + 0S
4 + 0S
1 + 0S2+ 1S =
3 16 4
Desta forma, podemos apreciar uma matriz identidade (n = 4), formada pelas variáveis de folga.
cuales solo tienen coeficiente 1 en su respectivo recurso, por el ejemplo la variable de holgura «S1»
somente tem coeficiente 1 na restrição correspondente ao recurso 1.
A função objetivo não sofre variações:
ZMÁX =20000X +
1 20000X +220000X + 320000X 4
Paso 3: Definir la solución básica inicial
O Método Simplex parte de uma solução básica inicial para realizar todas as suas iterações, esta solução
a básica inicial se forma com as variáveis de coeficiente diferente de zero (0) na matriz identidade.
1S=
1 24
1S=
2 20
1S3= 20
1S4= 16
Solução: (segundo termo)= Nesta linha se registra o segundo termo da solução, ou seja, as
variáveis, o mais adequado é que estas sejam registradas de maneira ordenada, assim como foram escritas
na definição de restrições.
Cj= A linha «Cj» refere-se ao coeficiente que cada uma das variáveis na linha «solução» possui.
na função objetivo.
Variável Solução= Nesta coluna é registrado a solução básica inicial, e a partir dela em cada
na iteração, são incluídas as variáveis que farão parte da solução final.
Cb= Nesta linha é registrado o valor que a variável à sua direita possui «Variável
solução" na função objetivo.
Zj= Nesta linha é registrada a contribuição total, ou seja, a soma dos produtos entre o termo e Cb.
Cj – Zj= Nesta linha é feita a diferença entre a linha Cj e a linha Zj, seu significado é um «Shadow
preço", ou seja, a utilidade que se deixa de receber por cada unidade da variável correspondente que não
faça parte da solução.
Solução inicial:
Paso 5: Realizar las iteraciones necesarias
Este é o passo definitivo na resolução pelo Método Simplex, consiste em realizar tentativas
enquanto o modelo vai de um vértice do poliedro objetivo a outro.
O procedimento a seguir é o seguinte:
1. Avaliar qual variável entrará e qual sairá da solução ótima:
2.O fato de que uma variável distinta faça parte das variáveis solução implica uma série de
mudanças no tabulado Simplex, mudanças que serão explicadas a seguir.
• O primeiro é não esquecer o valor do «a» correspondente às variáveis a entrar, neste caso o
a=4
• O seguinte é começar a preencher o resto da tabela, linha por linha.
• Repete-se este procedimento com as duas linhas restantes, agora serão feitos os cálculos.
correspondentes no resto das células.
Uma vez estabelecidos os valores da matriz, você pode calcular até preencher a tabela correspondente à
primeira iteração.
Desta forma, culmina-se a primeira iteração, este passo se repetirá quantas vezes for necessário e apenas
será dado por terminado o método de acordo com os seguintes critérios.
Continuamos com as iterações para o qual temos que repetir os passos anteriores.
Nesta última iteração, podemos observar que a condição Cj – Zj <= 0 é atendida para os exercícios.
cuja função objetivo seja «Maximizar», portanto chegamos à resposta ótima.
X1 = 3
X2 = 4
X3 = 6
X4 = 4
Con una utilidad de: $ 340000
No entanto, uma vez finalizado o Método Simplex, deve-se observar uma matriz identidade na
retângulo determinado pelas variáveis de decisão, o fato de que neste caso não se mostra a
matriz identidade significa que existe uma solução ótima alternativa.
A maneira de chegar à outra solução consiste em alterar a ordem em que cada uma das variáveis entrou
à solução básica, lembremos que o processo foi decidido ao acaso devido à igualdade em Cj - Zj
do tabelado inicial. Aqui apresentamos uma das maneiras de chegar à outra solução.
Podemos observar como existe uma solução ótima alternativa na qual a combinação de variáveis
é distinta e existe um menor consumo de recursos, dado que o fato de estar a variável
«S1» na solução ótima com um coeficiente de «3» significa que há uma folga de 3
unidades do recurso (peça retangular de 8 pinos).
X1 = 0 (Cantidad de mesas a producir = 0)
X 2 = 7 (Quantidade de cadeiras a produzir = 7)
X3 = 6 (Cantidad de camas a producir = 6)
X4 = 4 (Quantidade de bibliotecas a produzir = 4)
S1 = 3 (Cantidad de piezas rectangulares de 8 pines sin utilizar =3)
Com um lucro de: R$ 340000
Problemas de minimização com o Método Simplex
Para resolver problemas de minimização através do algoritmo simplex existem dois procedimentos
que são empregados com regularidade.
• O primeiro, que na minha opinião é o mais recomendável, baseia-se em um artifício aplicável ao algoritmo
fundamentado na lógica matemática que dita que "para qualquer função f(x), todo ponto
que minimiza f(x) também maximizará -f(x). Portanto, o procedimento a ser aplicado é
multiplicar por el factor negativo (-1) a toda la función objetivo.
A seguir, resolve-se o algoritmo como um problema de maximização.
• O segundo procedimento, que pretende conservar a minimização, consiste em aplicar os
criterios de decisión que hemos esbozado con anterioridad, en los casos de la variable que entra,
que sai e o caso em que a solução ótima é encontrada. Aqui lembramos os
procedimentos segundo o critério dado o caso «minimizar».