O algoritmo do simplex revisto

No texto O problema do transporte, apresentei uma ligação para a minha implementação do problema do transporte. Trata-se de uma forma especializada do algoritmo do simplex. Este último, consiste num processo de determinar o melhor valor, máximo ou mínimo, de uma função linear sujeita a uma série de restrições lineares.

Este algoritmo permite obter o máximo da função

z=6x+8y

no domínio definido pelas restrições

x+y\le 10
2x+3y\le 25
x+5y\le 35
x\ge 0
y\ge 0

Se introduzirmos, uma para cada uma das desigualdades anteriores, três variáveis u, v e w podemos descrever o problema anterior como: maximizar a função

z=6x+8y+0u+0v+0w

sujeita às condições

x+y+u=10
2x+3y+v=25
x+5y+w=35
x\ge 0
y\ge 0
u\ge 0
v\ge 0
w\ge 0

Daqui identificamos uma matriz das restrições

\left\lbrack  \begin{matrix}  1 & 1\\  2 & 3\\  1 & 5  \end{matrix}  \right\rbrack

associada ao vector de restrições

\left\lbrack  \begin{matrix}  10\\  25\\  35  \end{matrix}  \right\rbrack

Identificamos ainda o vector associado à função objectivo,

\lbrack  \begin{matrix}  6 & 8  \end{matrix}  \rbrack

As variáveis u, v e w são vulgarmente designadas por básicas ou variáveis de folga.

Cada iteração do algoritmo passa pela determinação da melhor troca de duas variáveis, uma básica e outra não básica. O algoritmo revisto consiste numa implementação adequada à realização num sistema computacional. O exemplo supracitado advém do vídeo:

Apesar de existir um pequeno erro nos cálculos intermédios, o vídeo é bem sucedido no que concerne a uma exposição interessante dos elementos que são relevantes no seio do processo.

Aponho, no skydrive (seguir ligação para o ficheiro) a minha implementação do algoritmo do simplex revisto em C#. Trata-se de uma classe, a qual poderá ser utilizada com base no seguinte código descritivo do exemplo supracitado:

double[] objectiveVector = new double[2] { 6, 8 };
double[] constraintsVector = new double[3] { 10, 25, 35 };
double[,] constraintsMatrix = new double[3, 2];
constraintsMatrix[0, 0] = 1; constraintsMatrix[0, 1] = 1;
constraintsMatrix[1, 0] = 2; constraintsMatrix[1, 1] = 3;
constraintsMatrix[2, 0] = 1; constraintsMatrix[2, 1] = 5;
RevisedSimplexUsingDoubles simplexAgorithm = new RevisedSimplexUsingDoubles(
objectiveVector,
constraintsVector,
constraintsMatrix);
simplexAgorithm.Run();
Console.WriteLine(simplexAlgorithm.BestCost);
// O valor óptimo do x
Console.WriteLine(simplexAlgorithm[0]);
// O valor óptimo do y
Console.WriteLine(simplexAlgorithm[1]);

Executando o algoritmo para este exemplo, obtemos o melhor custo igual a 70 com x=5 e y=5, diferindo um pouco do que é obtido no vídeo.

Sobre Sérgio O. Marques

Licenciado em Física/Matemática Aplicada (Astronomia) pela Faculdade de Ciências da Universidade do Porto e Mestre em Matemática Aplicada pela mesma instituição, desenvolvo trabalho no PTC (Porto Technical Centre) - Yazaki como Administrador de bases-de-dados. Dentro o meu leque de interesses encontram-se todos os temas afins às disciplinas de Matemática, Física e Astronomia. Porém, como entusiasta, interesso-me por temas relacionados com electrónica, poesia, música e fotografia.
Esta entrada foi publicada em Matemática com as etiquetas , , , . ligação permanente.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s