Simplex Solver - Manual de Uso e Instalação

7/23/2019 Simplex Solver - Manual de Uso e Instalao

1/21

Simplex Solver - Release 2015Sinvaldo R. Moreno, MSc. Eng.

[email protected]

24 de novembro de 2015

1


2/21

S.R.Moreno

Sumrio

1 Disclaimer 3

2 Aviso Legal 3

3 O que h de novo na Verso 1.1.1.6 ? 3

4 Instalao 4

5 Interface Grfica 5

5.1 Check Box - Opes de Sada dos Resultados. . . . . . . . . . . . . . . 6

5.2 Boto LER DADOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

5.3 Boto Solve Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

5.4 Boto Clear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85.5 Boto Ver Resultados. . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

6 Resolvendo um Problema de Programao Linear 9

6.1 Formato do Problema. . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

6.2 Formato do Arquivo de Entrada do Problema 1 . . . . . . . . . . . . . 10

6.3 Variveis Livres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

6.4 Formato do Arquivo de Entrada do Problema com Variveis Livre . . . 13

6.5 Iteraes Modo Tutorial . . . . . . . . . . . . . . . . . . . . . . . . . . 14

6.6 Modo Gerar Arquivo de Resultados . . . . . . . . . . . . . . . . . . . . 16

6.7 Formato do Arquivo de Sada do Problema . . . . . . . . . . . . . . . . 17

7 Problemas Ilimitado ou Sem Soluo, Mltiplas Solues, Degenerado 19

8 Uso Acadmico 21

Simplex Solver


3/21

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 - Aplicao para Soluo de Problemas de Programao Linear Copy-

right (C) 2015 S.R. Moreno

Este programa software livre: voc pode redistribu-lo e / ou modificlo sob os

termos da GNU General Public License como publicado pela a Free Software Founda-

tion, tanto a verso 3 da licena, ou (a seu critrio) qualquer verso posterior.

Este programa distribudo na esperana que possa ser til, mas SEM QUAL-

QUER GARANTIA; mesmo sem a garantia implcita de COMERCIALIZAO ouADEQUAO A UM DETERMINADO FIM. veja a Licena Pblica Geral GNU para

obter mais detalhes.

Voc deve ter recebido uma cpia da Licena Pblica Geral GNU junto com este

programa. Se no, veja http://www.gnu.org/licenses/.

3 O que h de novo na Verso 1.1.1.6 ?

Esta verso recebeu atualizao principalmente na interface que inclui a funcio-nalidade do usurio resolver um problema de Programao Linear atravs do Modo

Tutorial, alm de incluir a opo 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 mtodo Sim-

plexest seguindo para resolver o problema, seja atravs do Simplex Primal ou do Dual

Simplex Solver
http://www.gnu.org/licenses/http://www.gnu.org/licenses/http://www.gnu.org/licenses/http://www.gnu.org/licenses/http://www.gnu.org/licenses/


4/21

S.R.Moreno

Simplex, onde a cada iterao, mostrado ao usurio quem entrar na base e qual

elemento o piv, onde sero realizadas as operaes para obter a base atualizada.

A maneira de realizar o inputdo problema continua inalterada, bem como as fun-

cionalidades de salvar as solues de cada iterao em um arquivo. A incluso de um

boto com a opo de Ver Resultados, possibilita ao final das iteraes ver o Tableau

de cada iterao, facilitando a anlise de resultado de cada iterao.

4 Instalao

O aplicativo Simplex Solver R disponibilizado para instalao atravs do link de

instalao: https://drive.google.com/file/d/0B3dw398mYs0DQm92RFctWHZwRHM/view?

usp=sharing , de CD/DVD ou flash-drive. A instalao simples e haver incluso

de informaes e permisses no Registro do Microsoft Windows Rpara que o mesmopossa ser instalado. Dessa forma se faz necessrio ter privilgios de Administrador

da mquina, para que se possa lograr exito na instalao.

Para iniciar a instalao basta clicar no cone Setupconforme Figura1. :

Figura 1: Acessando o arquivo de Instalao

Ao clicar no arquivo Setup iniciar o processo de instalao da aplicao, que

solicitar a confirmao se a fonte que disponibilizou o arquivo confivel (Publisher),

Simplex Solver
https://drive.google.com/file/d/0B3dw398mYs0DQm92RFctWHZwRHM/view?usp=sharinghttps://drive.google.com/file/d/0B3dw398mYs0DQm92RFctWHZwRHM/view?usp=sharinghttps://drive.google.com/file/d/0B3dw398mYs0DQm92RFctWHZwRHM/view?usp=sharinghttps://drive.google.com/file/d/0B3dw398mYs0DQm92RFctWHZwRHM/view?usp=sharing


5/21

S.R.Moreno

conforme Figura2, confirme a instalao, clicando em Install.

Figura 2: Confirmao de Instalao

Aps a concluso da instalao, ser criado um atalho na rea de trabalho, bem

como uma pasta no menu iniciar do Microsoft Windows R.

5 Interface Grfica

Para iniciar a aplicao basta um clique sobre o atalho, uma tela inicial de carrega-mento da aplicao surgir, conforme Figura3:

Figura 3: Tela Inicializao Simplex Solver R.

Aps alguns segundos, a Tela da Aplicao surgir, conforme Figura4:

Simplex Solver


6/21

S.R.Moreno

Figura 4: Tela Inicial Simplex SolverR.

Observe que a interface bem simples, h um check boxcom as opesVer Resul-

tados na Tela, Gerar Arquivo de Resultados e Modo Tutorial, alm dos botes

Ler Dados, Ver Resultados, Solve Simplex e Clear. A funo de cada item

detalhada a seguir.

5.1 Check Box - Opes de Sada dos Resultados

facultado ao usrio a escolha de ter os resultados mostrados em tempo de execuo,a cada iterao, na tela do computador, ou ainda salv-los em um arquivo de texto

(.txt), isso feito atravs da seleo no check box, conforme Figura4.

1. Ver Resultados na Tela: Ao selecionar esta opo , a cada iterao, a aplicao

mostrar o resultado na tela do Tableauatualizado;

2. Gerar Arquivo de Resultados: Nesta opo os resultados sero salvos em

arquivo .txt;

3. Modo Tutorial: Nesta opo a cada iterao destacado na cor dourada, alinha e coluna do elementos que entraro e sairo da base;

4. Ver Resultados na Tela E Gerar Arquivo de Resultados: A combinao

de ambas opes, proporciona ver os resultados a cada iterao, alm de salvar

em um arquivo de texto;

Simplex Solver


7/21

S.R.Moreno

5. Ver Resultados na Tela E Modo Tutorial: A combinao de ambas opes,

proporciona ver os resultados a cada iterao, alm de ter o detalhamento dos

passos do Simplex;

6. Modo Tutorial E Gerar Arquivo de Resultados: A combinao de ambasopes, proporciona ver os resultados a cada iterao com o detalhamento dos

passos do Simplex, alm de salvar em um arquivo de texto;

7. Ver Resultados na Tela E Modo Tutorial E Gerar Arquivo de Resulta-

dos: A combinao das trs opes possibilita ao usurio a mxima funcionali-

dade.

Caso no seja escolhido nenhuma opo de sada (nenhum item selecionado), por

defaulta aplicao mostrar os resultados na tela;

5.2 Boto LER DADOS

A entrada dos dados do problema feita atravs de um arquivo de texto (.txt).

Para selecionar o arquivo basta clicar no boto Ler Dados. Uma caixa de seleo

de arquivos se abrir para o usurio 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 boto Clear e o boto Solve Simplex. Caso nenhum arquivo seja

escolhido, o usurio poder Cancelarou Refazera escolha do arquivo. Ao pressionarCancelar, a aplicao ser encerrada;

Figura 5: Ao selecionar o arquivo de entrada, o boto Clear e Solve Simplex habilitado.

Simplex Solver


8/21

S.R.Moreno

Figura 6: Opes de Cancelar ou Refazer a Escolha do Arquivo.

Figura 7: Opo de Cancelar - Encerra a aplicao.

5.3 Boto Solve Simplex

Aps a entrada dos dados do problema, via arquivo .txt, para iniciar a soluo de

um problema, basta clicar no boto Solve Simplex, que habilitado somente aps o

carregamento dos dados na interface grfica.

5.4 Boto Clear

Aps a soluo de um problema, caso o usurio deseje realizar a soluo de outros

problemas, sem a necessidade de fechar a aplicao e inicializar novamente, basta clicar

no boto Clearque a aplicao estar disponvel para uso; Este boto s habilitado

aps o carregamento dos dados na interface grfica.

Simplex Solver


9/21

S.R.Moreno

5.5 Boto Ver Resultados

Aps a soluo do problema, tendo inicialmente escolhido a opo deGerar Arqui-

vos de Resultados, o botoVer Resultadospossibilita abrir o arquivo de resultados

utilizando a interface grfica do solver, facilitando desta forma a leitura dos resultadosde cada iterao. Este boto s habilitado ao final da soluo do problema, com a

opo de Gerar Arquivos de Resultadospreviamente selecionada.

6 Resolvendo um Problema de Programao Linear

6.1 Formato do Problema

O padro utilizado no Simplex SolverR para a funo objetivo de Minimizao,

ou seja, caso o problema a ser resolvido esteja no padro de Maximizao, o mesmodeve ser transformado para Minimizao, bastando para isso multiplicar a funo

objetivo por (-1).

Ainda seguindo o padro de Minimizao, as restries do problema devem estar na

forma de igualdade, ou seja, o problema j deve estar transformado na forma de Tableau,

tambm referido como Forma Preparada, ou Formato Padro. Para maiores detalhes

sobre mudanas e transformaes de desigualdade, consulte bibliografia especializada[1,

2].

Exemplo de transformao de um problema para o formato de entrada do SimplexSolverR.

Max Z= 3x1+ 5x2 (1)

Sujeito a:

x1 4 (2)

2x2 12

3x1+ 2x2 18

x1 and x2 0;

Colocando na forma padro: Problema de Minimizao e restries transforma-

das em =.

Simplex Solver


10/21

S.R.Moreno

Min Z= 3x1+ 5x2 (3)

Sujeito a:

x1+ s1 = 4 (4)

2x2+ s2 = 12

3x1+ 2x2+ s3 = 18

x1 and x2 0;

Tableaudo Simplex: Sendo este o formato preparado;

x1 x2 s1 s2 s3 RHS

Base -3 -5 0 0 0 Zs1 1 0 1 0 0 4s2 0 2 0 1 0 12s3 3 2 0 0 1 18

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 SolverR.

6.2 Formato do Arquivo de Entrada do Problema 1

O arquivo a ser lido pelo Simplex SolverR um arquivo de texto, sendo o Tableau1

o formato a ser transferido para o arquivo txt, apenas com uma mudana na coluna

onde aparece Z, que deve ser substitudo por 0, alm das variveis de folga s1, s2 e s3serem renomeadas para xi onde o indice i a continuao do ndice das variveis do

problema. Para clarificar o padro, um exemplo apresentado na Figura8, onde as

variveiss1deve ser renomeada para x3, s2para x4e assim por diante:

Simplex Solver


11/21

S.R.Moreno

Figura 8: Modelo de Arquivo de Entrada

Aps carregar o arquivo no Simplex SolverR, o problema apresentado conforme

Figura9. Observe que aps carregar o arquivo, o boto Solve Simplex mostrado do

lado direito do check boxna aplicao:

Figura 9: Problema Exemplo

6.3 Variveis Livres

Quando existe variveis livres, ou transformaes de problemas linear por partes,

as variveis que correlacionam o intervalo onde existe a linearidade por partes, ou as

variveis de transformao da varivel livre (ex. x1 livre equivalente a x1 =x1 x

1,

sendo x1 0and x

1 0). Um exemplo de transformao de um problema que contm

varivel livre para o formato utilizado pelo Simplex SolverR mostrada a seguir. Seja

o problema de maximizao dado abaixo, com x1sendo livre:

Simplex Solver


12/21

S.R.Moreno

Max Z = x1+ 4x2 (5)

Sujeito a:

3x1+ x2 6 (6)

x1+ 2x2 4

x2 3

x1 Livre ; x2 0;

Colocando na forma padro: Problema de Minimizao e variveis xi 0.

M in Z=x1

+x1 4x2 (7)

Sujeito a:

3x1

+ 3x1

+ x2 6 (8)

x1 x

1+ 2x2 4

x2 3

x1

; x1

; x2 0;

Colocando as restries na forma preparada: Ou seja, transformar as restriesem igualdade atravs de variveis de folga ou excesso:

M in Z=x1

+x1 4x2 (9)

Sujeito a:

3x1

+ 3x1

+ x2+ s1 = 6 (10)

x

1 x

1+ 2x2+ s2 = 4

x2+ s3 = 3

x1

; x1

; x2; s1; s2; s3 0;

Tableaudo Simplex: Sendo este o formato preparado;

Simplex Solver


13/21

S.R.Moreno

x1

x1

x2 s1 s2 s3 RHSBase 1 -1 -4 0 0 0 Z

s1 -3 3 1 1 0 0 6s2 1 -1 2 0 1 0 4

s3 0 0 -1 0 0 1 3

Apenas para no causar erro de interpretao ao ler soluo mostrada da aplicao,

devido ao padro de entrada ser a continuao do ndice do numero de variveis do

problema, para as variveis xi, quando estas estiverem no problema transformado,

recomenda-se ao usurio que renomeie-as para xi, alm de o faz-lo tambm para as

variveis de folga, ou seja, siparaxi; Desta forma o problema ser inserido na aplicao,

da seguinte forma:

x1 x2 x3 x4 x5 x6 RHSBase 1 -1 -4 0 0 0 Z

x4 -3 3 1 1 0 0 6x5 1 -1 2 0 1 0 4x6 0 0 -1 0 0 1 3

Tabela 2: Tableau a ser utilizado

Lembrando que esse um caso particular, ou seja, quando existem variveis livres,tais como x1 neste exemplo, que ao serem transformadas atravs da igualdade x1 =

x1x1, ondex1 0e x

1 0, a mesma deve ser renomeada aps a transformao para

variveis que no possuem o xi. E para manter coerncia com o resultado apresentado,

as variveis de folga (slackssi)so renomeadas para xi, seguindo a ordem de evoluo

dos ndices das variveis;

6.4 Formato do Arquivo de Entrada do Problema com Vari-

veis LivreO arquivo a ser lido pelo Simplex SolverR um arquivo de texto, sendo o Tableau2

o formato a ser transferido para o arquivo txt, apenas com uma mudana na coluna

onde apareceZ, que deve ser substitudo por 0, conforme figura abaixo:

Simplex Solver


14/21

S.R.Moreno

Figura 10: Modelo de Arquivo de Entrada

Aps carregar o arquivo no Simplex SolverR, o problema apresentado conforme

figura abaixo. Observe que aps carregar o arquivo, o boto Solve Simplex mostrado

do lado direito do check boxna aplicao:

Figura 11: Problema Exemplo

6.5 Iteraes Modo Tutorial

Aps carregar o arquivo, para realizar as iteraes, basta clicar no boto SolveSimplex. Lembrando que a sada deve estar selecionada, caso a mesma no esteja, a

sada padro ser a tela do computador.

Para o exemplo 1 em questo, ao clicar no boto Solve Simplex, a aplicao far

uma anlise do problema para verificar se o mesmo esta no formato padro, alm de

indicar por qual mtodo se dar a soluo, se pelo Simplex ou pelo Dual Simplex:

Simplex Solver


15/21

S.R.Moreno

Figura 12: Mtodo de Soluo do Problema Exemplo 1 atravs do Simplex

Figura 13: Mtodo de Soluo atravs do Dual Simplex

Ao clicar no boto Solve Simplexno Modo Tutorial, a cada iterao mostrado

em um Message Boxqual varivel entrar na base e qual varivel ser o piv, alm

de ser destacada na cor dourada a linha e coluna relativa a tais variveis, conforme aFigura14.

Simplex Solver


16/21

S.R.Moreno

Figura 14: Informao de alterao da base e elemento piv na Iterao 1.

A soluo final apresentada na tela, sem arredondamento ou truncamento, alm

de informar se o timo foi encontrado ou no.

Figura 15: Soluo tima Encontrada

6.6 Modo Gerar Arquivo de Resultados

Aps carregar o arquivo, com a opo Gerar Arquivo de Resultadosselecionada,

para realizar as iteraes basta clicar no botoSolve Simplex. Para o exemplo 1 em

questo, ao clicar no botoSolve Simplex, a aplicao far uma anlise do problema

para verificar se o mesmo esta no formato padro, alm de indicar por qual mtodo

se dar a soluo, se pelo Simplex ou pelo Dual Simplex, conforme j exemplificado.

Simplex Solver


17/21

S.R.Moreno

Ao realizar a primeira iterao o Simplex SolverR solicitar um caminho e nome do

arquivo onde sero gravadas as iteraes.

Figura 16: Solicitao de pathpara a gerao do arquivo com as respostas

Ao finalizar a gravao, um Message Boxinformar que o arquivo com as solues

foi gerado, alm de habilitar o boto Ver Resultados.

Figura 17: Gerao do arquivo com as respostas concluda

6.7 Formato do Arquivo de Sada do Problema

Ao selecionar a sada para ser gravada em um arquivo .txt, todas as iteraes sero

salvas e identificadas, conforme exemplo abaixo:

Simplex Solver


18/21


19/21

S.R.Moreno

7 Problemas Ilimitado ou Sem Soluo, Mltiplas

Solues, Degenerado

OSimplex SolverR

informa apenas algumas possveis situaes que podem ocorrerao tentar solucionar um problema de Programao Linear. Exemplos so mostrados a

seguir:

Soluo Ilimitada ou Sem Soluo: O solver Identifica.

Figura 20: Problema Ilimitado ou sem Soluo tima

Solues Mltiplas: O solver NO Identifica. Neste exemplo x4 VNB e possui

custo nulo, podendo entrar na Base, ou seja, pode-se tornar VB sem alterar a soluo.

Simplex Solver


20/21

S.R.Moreno

Figura 21: Problema com Mltiplas Solues No Identificado pelo Solver

Solues Degenerada: O solver NO Identifica. Neste exemplo x1assumiu valor

nulo (RHS), sendo portanto, uma soluo degenerada.

Figura 22: Problema com Soluo Degenerada No Identificado pelo Solver

Simplex Solver


21/21

S.R.Moreno

8 Uso Acadmico

A utilizao do Simplex SolverRpara fins acadmicos pode facilitar a explanao

e entendimento dos conceitos envolvidos no uso do Mtodo Simplex. Porm devido

a certos tipos de respostas e comportamentos do problema no serem identificadospelo Simplex SolverR, uma anlise atenda dos resultados deve ser precedida para um

entendimento completo das solues apresentadas.

Sobre o Autor

Sinvaldo R. Moreno graduado em Engenharia Eltrica pela UFPR. Possui Mes-

trado em Engenharia de Recursos Hdricos e Ambiental pela UFPR. Atualmente aluno

de Doutorado no Programa de Ps Graduao em Engenharia Eltrica da UFPR. Omesmo atua no Setor Eltrico desde 2006, com trabalhos voltado para rea de Operao

de Usinas Hidreltricas, Otimizao da Operao de Reservatrios, Estudos Impactos

de Cheias, Anlise de Projetos Hidroenergticos, entre outras.

Tem interesse em Inteligncia Computacional, Inteligncia de Enxames, Otimizao,

Mtodos de Simulao. Contatos: [email protected].

Referncias

[1] Katta G. Murty - Linear PorgrammingJohn Willey and Sons - United States

of America - 1983.

[2] Frederick Hillier and Gerald Lieberman - Introduction to Operations Research

McGraw-Hill Science Engineering Math; 9 edition (February 9, 2009)

Simplex Solver
mailto:%[email protected]:%[email protected]

Documents

Simplex Solver - Manual de Uso e Instalação