PHPSimplex

Otimizar os recursos com Programação Linear



Exemplo (parte 2): método Gráfico

Solução através do método gráfico o seguinte problema:

Maximizar Z = f(x,y) = 3x + 2y
sujeita às restrições: 2x + y ≤ 18
  2x + 3y ≤ 42
  3x + y ≤ 24
  x ≥ 0 , y ≥ 0
  1. Inicialmente, o sistema de coordenadas da associação de um eixo com variável "X" e o outro o "Y" é desenhado (geralmente associa-se "x" em relação ao eixo horizontal e o "y" ao vertical), como pode ser visto na figura.
  2. Nestes eixos, marca-se uma escala numérica apropriada aos valores que podem assumir as variáveis conforme as restrições do problema. Para isto, em cada restrição anulam-se todas as variáveis, exceto aquelas que correspondem a um eixo concreto, estabelecendo o valor adequado para este eixo. Este processo é repetido para cada um dos eixos.
  3. As restrições são representadas a seguir. Primeiramente, desenha-se a reta que é obtida ao considerar a restrição como uma igualdade. Ela é representada como o segmento que une A com B e região que delimita esta restrição é indicada pela cor AMARELA. O processo é repetido com as outras restrições, ficando delimitada a região de cor AZUL e VERMELHO para a segunda e terceira restrição respectivamente.
  4. A região viável é a interseção das regiões definidas tanto pelo conjunto de restrições, como pelas condições de não negatividade das variáveis, ou seja, ambos os eixos de coordenadas. Tal região viável é representada pelo polígono O-F-H-G-C, de cor VIOLETA.
    Gráficas y región factible
  5. Como existe uma região viável, passamos a determinar os seus pontos extremos, ou vértices do polígono que representa. Esses vértices são os pontos candidatos a soluções ótimas. Neste exemplo são os pontos O-F-H-G-C da figura.
  6. Finalmente, a função objetivo (3x + 2y) em cada um destes pontos (resultado determinado na tabela abaixo) é avaliada. Como o ponto G fornece o maior valor para a função Z e o objetivo é maximizar, este ponto é a solução ideal: Z = 33 con x = 3 e y = 12.
Ponto extremo Coordenadas (x,y) Valor objetivo (Z)
O (0,0) 0
C (0,14) 28
G (3,12) 33
H (6,6) 30
F (8,0) 24

Comparação do método Gráfico com o método Simplex

As tabelas construídas, sucessivamente, durante o método Simplex vão fornecendo o valor da função objetivo em diferentes vértices da região viável, ao mesmo tempo, ajustando os coeficientes das variáveis iniciais e de folga.

Na tabela inicial foi calculado o valor da função objetivo no vértice O, cujas coordenadas (0,0) se correspondem com o valor que têm as variáveis básicas e o resultado é 0.

Tabela I . Iteração 1
      3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P3 0 18 2 1 1 0 0
P4 0 42 2 3 0 1 0
P5 0 24 3 1 0 0 1
Z   0 -3 -2 0 0 0
Primeiro passo do método Gráfico

A variável que entra na base do método Simplex determina a que novo vértice será realizado o deslocamento. Neste exemplo, como entra P1 (correspondente ao 'x'), o deslocamento é realizado pela aresta OF até atingir o vértice F, onde é calculado o valor que assume a função Z. Este passo ocorre na segunda iteração do método Simplex, mostrado na Tabela II. Onde foi calculado o valor correspondente à vértice F, obtendo-se um valor Z = 24 para a função.

Tabela II . Iteração 2
      3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P3 0 2 0 1/3 1 0 -2/3
P4 0 26 0 7/3 0 1 -2/3
P1 3 8 1 1/3 0 0 1/3
Z   24 0 -1 0 0 1
Segundo passo do método Gráfico

Um novo deslocamento é realizado na aresta FH até chegar em H (dados na tabela III). Na terceira iteração, o valor da função no vértice H é calculado, obtendo-se Z = 30.

Tabela III . Iteração 3
      3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P2 2 6 0 1 3 0 -2
P4 0 12 0 0 -7 1 4
P1 3 6 1 0 -1 0 1
Z   30 0 0 3 0 -1
Terceiro passo do método Gráfico

O processo prossegue através da aresta HG, até o vértice G. Os dados obtidos são mostrados na Tabela IV. Neste ponto, o processo termina, e é possível verificar que a solução não é melhorada pela aresta GC até o vértice C (não excede o valor atual da função).

Tabela IV . Iteração 4
      3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P2 2 12 0 1 -1/2 1/2 0
P5 0 3 0 0 -7/4 1/4 1
P1 3 3 1 0 3/4 -1/4 0
Z   33 0 0 5/4 1/4 0
Quarto passo do método Gráfico

O valor máximo da função objetiva é 33, e corresponde aos valores x = 3 e y = 12 (coordenadas do vértice G).

Com o método gráfico é necessário calcular o valor da função objetivo em cada vértice da região viável, enquanto que o método simplex termina quando o valor ótimo é encontrado.

Resolver com PHPSimplex pelo método Simplex.

Resolver com PHPSimplex pelo método Gráfico.

Copyright ©2006-2017 PHPSimplex. Todos os direitos reservados. Termos e condições.
Siga-nos no Twitter
X

PHPSimplex
Versão 0.81

Copyright ©2006-2017. Todos os direitos reservados.

Desenvolvido por:
Daniel Izquierdo Granja
Juan José Ruiz Ruiz

Tradução para o Inglês por:
Luciano Miguel Tobaria

Tradução para o Francês por:
Ester Rute Ruiz

Tradução para o Português por:
Rosane Bujes