Simplex Solver - Manual de Uso e Instalação

Simplex Solver - Manual de Uso e Instalação

(Parte 1 de 2)

Simplex Solver - Release 2015

Sinvaldo R. Moreno, MSc. Eng. sinvaldo.moreno@ufpr.br

24 de novembro de 2015

S.R.Moreno Sumário

5.1 Check Box - Opções de Saída dos Resultados6
5.2 Botão LER DADOS7
5.3 Botão Solve Simplex8
5.4 Botão Clear8
5.5 Botão Ver Resultados9

5 Interface Gráfica 5

6.1 Formato do Problema9
6.2 Formato do Arquivo de Entrada do Problema 110
6.3 Variáveis Livres1
6.4 Formato do Arquivo de Entrada do Problema com Variáveis Livre13
6.5 Iterações Modo Tutorial14
6.6 Modo Gerar Arquivo de Resultados16
6.7 Formato do Arquivo de Saída do Problema17

6 Resolvendo um Problema de Programação Linear 9 7 Problemas Ilimitado ou Sem Solução, Múltiplas Soluções, Degenerado 19 8 Uso Acadêmico 21

Simplex Solver

S.R.Moreno 1 Disclaimer

Simplex Solver - Linear Programming Application Copyright (C) 2015 S.R. Moreno This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT

ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/

2 Aviso Legal

Simplex Solver - Aplicação para Solução de Problemas de Programação Linear Copyright (C) 2015 S.R. Moreno

Este programa é software livre: você pode redistribuí-lo e / ou modificá–lo sob os termos da GNU General Public License como publicado pela a Free Software Foundation, tanto a versão 3 da licença, ou (a seu critério) qualquer versão posterior.

Este programa é distribuído na esperança que possa ser útil, mas SEM QUAL-

QUER GARANTIA; mesmo sem a garantia implícita de COMERCIALIZAÇÃO ou ADEQUAÇÃO A UM DETERMINADO FIM. veja a Licença Pública Geral GNU para obter mais detalhes.

Você deve ter recebido uma cópia da Licença Pública Geral GNU junto com este programa. Se não, veja http://www.gnu.org/licenses/

3 O que há de novo na Versão 1.1.1.6 ?

Esta versão recebeu atualização principalmente na interface que inclui a funcionalidade do usuário resolver um problema de Programação Linear através do Modo Tutorial, além de incluir a opção de abrir o arquivo de resultados na forma de Tableau na interface do programa.

O Modo Tutorial possibilita o perfeito entendimento dos passos que o método Simplex está seguindo para resolver o problema, seja através do Simplex Primal ou do Dual

Simplex Solver

S.R.Moreno

Simplex, onde a cada iteração, é mostrado ao usuário quem entrará na base e qual elemento é o pivô, onde serão realizadas as operações para obter a base atualizada.

A maneira de realizar o input do problema continua inalterada, bem como as funcionalidades de salvar as soluções de cada iteração em um arquivo. A inclusão de um botão com a opção de Ver Resultados, possibilita ao final das iterações ver o Tableau de cada iteração, facilitando a análise de resultado de cada iteração.

4 Instalação

O aplicativo Simplex Solver R© é disponibilizado para instalação através do link de instalação: https://drive.google.com/file/d/0B3dw398mYs0DQm92RFctWHZwRHM/view? usp=sharing , de CD/DVD ou flash-drive. A instalação é simples e haverá inclusão de informações e permissões no Registro do Microsoft Windows R© para que o mesmo possa ser instalado. Dessa forma se faz necessário ter privilégios de Administrador da máquina, para que se possa lograr exito na instalação. Para iniciar a instalação basta clicar no ícone Setup conforme Figura 1. :

Figura 1: Acessando o arquivo de Instalação

Ao clicar no arquivo Setup iniciará o processo de instalação da aplicação, que solicitará a confirmação se a fonte que disponibilizou o arquivo é confiável (Publisher),

Simplex Solver

S.R.Moreno conforme Figura 2, confirme a instalação, clicando em Install.

Figura 2: Confirmação de Instalação

Após a conclusão da instalação, será criado um atalho na área de trabalho, bem como uma pasta no menu iniciar do Microsoft Windows R©.

5 Interface Gráfica

Para iniciar a aplicação basta um clique sobre o atalho, uma tela inicial de carregamento da aplicação surgirá, conforme Figura 3:

Figura 3: Tela Inicialização Simplex Solver R©.

Após alguns segundos, a Tela da Aplicação surgirá, conforme Figura 4: Simplex Solver

S.R.Moreno

Figura 4: Tela Inicial Simplex Solver R©.

Observe que a interface é bem simples, há um check box com as opções Ver Resultados na Tela, Gerar Arquivo de Resultados e Modo Tutorial, além dos botões Ler Dados, Ver Resultados, Solve Simplex e Clear. A função de cada item é detalhada a seguir.

5.1 Check Box - Opções de Saída dos Resultados

É facultado ao usário a escolha de ter os resultados mostrados em tempo de execução, a cada iteração, na tela do computador, ou ainda salvá-los em um arquivo de texto (.txt), isso é feito através da seleção no check box, conforme Figura 4.

1. Ver Resultados na Tela: Ao selecionar esta opção , a cada iteração, a aplicação mostrará o resultado na tela do Tableau atualizado;

2. Gerar Arquivo de Resultados: Nesta opção os resultados serão salvos em arquivo .txt;

3. Modo Tutorial: Nesta opção a cada iteração é destacado na cor dourada, a linha e coluna do elementos que entrarão e sairão da base;

4. Ver Resultados na Tela E Gerar Arquivo de Resultados: A combinação de ambas opções, proporciona ver os resultados a cada iteração, além de salvar em um arquivo de texto;

Simplex Solver

S.R.Moreno

5. Ver Resultados na Tela E Modo Tutorial: A combinação de ambas opções, proporciona ver os resultados a cada iteração, além de ter o detalhamento dos passos do Simplex;

6. Modo Tutorial E Gerar Arquivo de Resultados: A combinação de ambas opções, proporciona ver os resultados a cada iteração com o detalhamento dos passos do Simplex, além de salvar em um arquivo de texto;

7. Ver Resultados na Tela E Modo Tutorial E Gerar Arquivo de Resultados: A combinação das três opções possibilita ao usuário a máxima funcionalidade.

Caso não seja escolhido nenhuma opção de saída (nenhum item selecionado), por default a aplicação mostrará os resultados na tela;

5.2 Botão LER DADOS

A entrada dos dados do problema é feita através de um arquivo de texto (.txt).

Para selecionar o arquivo basta clicar no botão Ler Dados. Uma caixa de seleção de arquivos se abrirá para o usuário indicar o caminho do arquivo com o problema a ser resolvido. Ao selecionar um arquivo com o problema a ser resolvido, é habilitado na interface o botão Clear e o botão Solve Simplex. Caso nenhum arquivo seja escolhido, o usuário poderá Cancelar ou Refazer a escolha do arquivo. Ao pressionar Cancelar, a aplicação será encerrada;

Figura 5: Ao selecionar o arquivo de entrada, o botão Clear e Solve Simplex é habilitado. Simplex Solver

S.R.Moreno Figura 6: Opções de Cancelar ou Refazer a Escolha do Arquivo.

Figura 7: Opção de Cancelar - Encerra a aplicação.

5.3 Botão Solve Simplex

Após a entrada dos dados do problema, via arquivo .txt, para iniciar a solução de um problema, basta clicar no botão Solve Simplex, que é habilitado somente após o carregamento dos dados na interface gráfica.

5.4 Botão Clear

Após a solução de um problema, caso o usuário deseje realizar a solução de outros problemas, sem a necessidade de fechar a aplicação e inicializar novamente, basta clicar no botão Clear que a aplicação estará disponível para uso; Este botão só é habilitado após o carregamento dos dados na interface gráfica.

Simplex Solver

S.R.Moreno 5.5 Botão Ver Resultados

Após a solução do problema, tendo inicialmente escolhido a opção de Gerar Arquivos de Resultados, o botão Ver Resultados possibilita abrir o arquivo de resultados utilizando a interface gráfica do solver, facilitando desta forma a leitura dos resultados de cada iteração. Este botão só é habilitado ao final da solução do problema, com a opção de Gerar Arquivos de Resultados previamente selecionada.

6 Resolvendo um Problema de Programação Linear

6.1 Formato do Problema

O padrão utilizado no Simplex Solver R© para a função objetivo é de Minimização, ou seja, caso o problema a ser resolvido esteja no padrão de Maximização, o mesmo deve ser transformado para Minimização, bastando para isso multiplicar a função objetivo por (-1).

Ainda seguindo o padrão de Minimização, as restrições do problema devem estar na forma de igualdade, ou seja, o problema já deve estar transformado na forma de Tableau, também referido como Forma Preparada, ou Formato Padrão. Para maiores detalhes sobre mudanças e transformações de desigualdade, consulte bibliografia especializada [1, 2].

Exemplo de transformação de um problema para o formato de entrada do Simplex Solver R©.

Colocando na forma padrão: Problema de Minimização e restrições ≤ transformadas em =.

Simplex Solver

S.R.Moreno

Tableau do Simplex: Sendo este o formato preparado;

Tabela 1: Tableau já na forma preparada do problema exemplo 1

O problema na forma de Tableau é o formato adotado para o arquivo de entrada de dados no Simplex Solver R©.

6.2 Formato do Arquivo de Entrada do Problema 1

O arquivo a ser lido pelo Simplex Solver R© é um arquivo de texto, sendo o Tableau 1 o formato a ser transferido para o arquivo txt, apenas com uma mudança na coluna onde aparece Z, que deve ser substituído por 0, além das variáveis de folga s1,s2 e s3 serem renomeadas para xi onde o indice i é a continuação do índice das variáveis do problema. Para clarificar o padrão, um exemplo é apresentado na Figura 8, onde as variáveis s1 deve ser renomeada para x3, s2 para x4 e assim por diante:

Simplex Solver

S.R.Moreno

Figura 8: Modelo de Arquivo de Entrada

Após carregar o arquivo no Simplex Solver R©, o problema é apresentado conforme

Figura 9. Observe que após carregar o arquivo, o botão Solve Simplex é mostrado do lado direito do check box na aplicação:

Figura 9: Problema Exemplo

6.3 Variáveis Livres

Quando existe variáveis livres, ou transformações de problemas linear por partes, as variáveis que correlacionam o intervalo onde existe a linearidade por partes, ou as variáveis de transformação da variável livre (ex. x1 livre é equivalente a x1 = x′1 − x′′1, sendo x′1 ≥ 0 and x′′1 ≥ 0). Um exemplo de transformação de um problema que contém variável livre para o formato utilizado pelo Simplex Solver R© é mostrada a seguir. Seja o problema de maximização dado abaixo, com x1 sendo livre:

Simplex Solver

S.R.Moreno

Colocando na forma padrão: Problema de Minimização e variáveis xi ≥ 0.

Colocando as restrições na forma preparada: Ou seja, transformar as restrições em igualdade através de variáveis de folga ou excesso:

Tableau do Simplex: Sendo este o formato preparado;

Simplex Solver

S.R.Moreno

Apenas para não causar erro de interpretação ao ler solução mostrada da aplicação, devido ao padrão de entrada ser a continuação do índice do numero de variáveis do problema, para as variáveis x′i, quando estas estiverem no problema transformado, recomenda-se ao usuário que renomeie-as para xi, além de o fazê-lo também para as variáveis de folga, ou seja, si para xi; Desta forma o problema será inserido na aplicação, da seguinte forma:

Tabela 2: Tableau a ser utilizado

Lembrando que esse é um caso particular, ou seja, quando existem variáveis livres, tais como x1 neste exemplo, que ao serem transformadas através da igualdade x1 =

variáveis que não possuem o x′i. E para manter coerência com o resultado apresentado, as variáveis de folga (slacks si) são renomeadas para xi, seguindo a ordem de evolução dos índices das variáveis;

6.4 Formato do Arquivo de Entrada do Problema com Variáveis Livre

O arquivo a ser lido pelo Simplex Solver R© é um arquivo de texto, sendo o Tableau 2 o formato a ser transferido para o arquivo txt, apenas com uma mudança na coluna onde aparece Z, que deve ser substituído por 0, conforme figura abaixo:

Simplex Solver

S.R.Moreno

Figura 10: Modelo de Arquivo de Entrada

Após carregar o arquivo no Simplex Solver R©, o problema é apresentado conforme figura abaixo. Observe que após carregar o arquivo, o botão Solve Simplex é mostrado do lado direito do check box na aplicação:

Figura 1: Problema Exemplo

6.5 Iterações Modo Tutorial

Após carregar o arquivo, para realizar as iterações, basta clicar no botão Solve

Simplex. Lembrando que a saída deve estar selecionada, caso a mesma não esteja, a saída padrão será a tela do computador.

Para o exemplo 1 em questão, ao clicar no botão Solve Simplex, a aplicação fará uma análise do problema para verificar se o mesmo esta no formato padrão, além de indicar por qual método se dará a solução, se pelo Simplex ou pelo Dual Simplex:

Simplex Solver

S.R.Moreno Figura 12: Método de Solução do Problema Exemplo 1 através do Simplex

Figura 13: Método de Solução através do Dual Simplex

Ao clicar no botão Solve Simplex no Modo Tutorial, a cada iteração é mostrado em um Message Box qual variável entrará na base e qual variável será o pivô, além de ser destacada na cor dourada a linha e coluna relativa a tais variáveis, conforme a Figura 14.

Simplex Solver

S.R.Moreno

Figura 14: Informação de alteração da base e elemento pivô na Iteração 1.

A solução final é apresentada na tela, sem arredondamento ou truncamento, além de informar se o ótimo foi encontrado ou não.

Figura 15: Solução Ótima Encontrada

6.6 Modo Gerar Arquivo de Resultados

Após carregar o arquivo, com a opção Gerar Arquivo de Resultados selecionada, para realizar as iterações basta clicar no botão Solve Simplex. Para o exemplo 1 em questão, ao clicar no botão Solve Simplex, a aplicação fará uma análise do problema para verificar se o mesmo esta no formato padrão, além de indicar por qual método se dará a solução, se pelo Simplex ou pelo Dual Simplex, conforme já exemplificado.

Simplex Solver

S.R.Moreno

Ao realizar a primeira iteração o Simplex Solver R© solicitará um caminho e nome do arquivo onde serão gravadas as iterações.

Figura 16: Solicitação de path para a geração do arquivo com as respostas

Ao finalizar a gravação, um Message Box informará que o arquivo com as soluções foi gerado, além de habilitar o botão Ver Resultados.

Figura 17: Geração do arquivo com as respostas concluída

6.7 Formato do Arquivo de Saída do Problema

Ao selecionar a saída para ser gravada em um arquivo .txt, todas as iterações serão salvas e identificadas, conforme exemplo abaixo:

Simplex Solver

S.R.Moreno

Figura 18: Formato do Arquivo de Saída para o Problema Exemplo 1

O arquivo é salvo em local informado pelo usuário. Caso o usuário deseje utilizar o mesmo arquivo para salvar todas as soluções de vários problemas, o arquivo atual não é sobre-escrito, ou seja, ele é continuado, podendo ser utilizado como um log de soluções de todos os problemas. A identificação se dá pelo numero de iterações. Exemplo de soluções de dois problemas distintos salvos no mesmo arquivo de saída:

Figura 19: Formato do Arquivo de Saída para dois Problemas Distintos Simplex Solver

S.R.Moreno 7 Problemas Ilimitado ou Sem Solução, Múltiplas

Soluções, Degenerado

O Simplex Solver R© informa apenas algumas possíveis situações que podem ocorrer ao tentar solucionar um problema de Programação Linear. Exemplos são mostrados a seguir: Solução Ilimitada ou Sem Solução: O solver Identifica.

Figura 20: Problema Ilimitado ou sem Solução Ótima

Soluções Múltiplas: O solver NÃO Identifica. Neste exemplo x4 é VNB e possui custo nulo, podendo entrar na Base, ou seja, pode-se tornar VB sem alterar a solução.

(Parte 1 de 2)

Comentários