O Sistema Simplex

Sistema CSimplex 1.0 – Calculadora de Simplex

Andresa Cristina Alves Oliveira, Débora de Oliveira Damião, Guilherme Sanzio Menezes Zallio

Curso de Bacharelado em Sistemas de Informação – Pontifícia Universidade Católica de Minas Gerais (PUC Minas) – Campus Betim
32604-115 – Betim – MG– Brasil

[e-mail], [e-mail], [e-mail]

Resumo. Este meta-artigo descreve o trabalho desenvolvido que consiste em um software que efetua o cálculo de uma maximização ou minimização de uma função pelo método simplex. Também apresenta como utilizar o software e a complexidade do mesmo.

1. Introdução

Um problema pode ser maximizado ou minimizado para se obter aquilo que se deseja. Por exemplo, em um sistema computacional, pode se maximizar um cálculo para achar o máximo que um software pode processar, ou minimizar o problema para conseguir utilizar o mínimo de processamento possível.

Existem várias formas de se maximizar ou minimizar um problema. Um método, muito conhecido é o método gráfico, em que consiste em achar os pontos de máximo ou mínimo desenhando retas em um gráfico. Ao se passar de duas variáveis básicas, fica complicado desenhar um gráfico de mais de duas dimensões.

Portanto, existe um outro método muito utilizado, que se chama “Simplex”. Ele consiste na montagem de uma tabela com todas as variáveis, restrições e as variáveis de folga, e como um todo, fazer o cálculo iterativamente até que satisfaça a condição proposta.

Esse artigo descreve um software que faz o cálculo de maximização ou minimização de uma função, tendo as suas restrições, através do método simplex. Ensina a utilizar o software desenvolvido, e também fala da sua complexidade.

2. Complexidade

O software em questão, possui parte visual. Portanto, para montar os campos que aparecem na tela para o usuário digitar, são montados de acordo com as características da função. Então se utiliza das repetições a todo momento para a montagem dos dados em tela, e também para os cálculos. Serão desconsideradas algumas partes do código, onde não influenciam na realização dos cálculos.

Para montar a tela com todos os campos para que o usuário possa preenche-los, ela utiliza de várias estruturas PARA (for). Veja abaixo uma parte do código abaixo.

[pic 1]

Figura 1. Bloco de código do software

Fonte: CSimplex 1.0, 2017

Neste bloco, utiliza-se duas estruturas PARA (for), para montar uma tabela para os campos serem inseridos. Neste caso, a Complexidade desse bloco é O(n) + O(n).

[pic 2]

Figura 2. Bloco de código do software

Fonte: CSimplex 1.0, 2017

Neste bloco, a complexidade muda, já que possuímos duas estruturas PARA (for), uma delas interna a outra. Neste caso, contando as outras linhas que não estão aí representadas, a complexidade do bloco desse bloco de código é O{(n * 44)²}.

[pic 3]

Figura 3. Bloco de Código do Software

Fonte: CSimplex 1.0, 2017

Neste bloco, temos dois blocos na mesma estrutura do bloco anterior. Deste modo, a complexidade deste bloco é O(n²) + O{(n * 8)²}.

Agora, será mostrado a complexidade da parte do código que faz os cálculos da matriz do simplex.

[pic 4]

Figura 4. Bloco de Código do Software

Fonte: CSimplex 1.0, 2017

Nesta parte, temos varias estruturas PARA (for). Uma das sequencias a estrutura é representada interna à outra. Sendo assim, a complexidade do código acima é O(n²) + O(n) + O(n) + O(n).

O bloco que segue depois desse, é extenso e por isso não será colocado no artigo. Ele possui diversas estruturas PARA (for). Elas percorrem a matriz para atender os requisitos de cálculo do simplex. No bloco final do código, a matriz é percorrida por linhas e colunas, então utiliza-se de uma estrutura PARA (for) interna a outra, o que faz com que a complexidade final seja O(n) + O(n) + O(n) + O(n) + O(n²). Para apresentar o resultado a complexidade do código também é O(n²).

Juntando ao final, temos: O(n) + O(n) + O{(n * 44)²} + O(n²) + O{(n * 8)²} + O(n²) + O(n) + O(n) + O(n) + O(n) + O(n) + O(n) + O(n) + O(n²) + O(n²).

Sendo assim, a complexidade geral do software é O(n²), diminuindo e somando todas as complexidades do código do software.

3. Como utilizar o Software

Ao abrir o software, é reparado uma tela que se expande por toda a tela. Para começar a utilizar o software e montar o simplex, clique no menu “Simplex” e depois no item “Novo”.

[pic 5]

Figura 5. Tela inicial do software.

Fonte: CSimplex 1.0, 2017

[pic 6]

Figura 6. Menu de início do cálculo

Fonte: CSimplex 1.0, 2017

Ao clicar em “Novo”, o software irá mostrar uma janela com 2 campos. Um é o número de variáveis que o simplex terá, e o outro é o número de restrições. Os dois campos só aceitam números inteiros e maiores que zero (0). Caso não satisfaça as condições, é disparada uma mensagem.