OTIMIZAÇAO MétodoGráfico

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
Otimização de Sistemas Computacionais 
Método Gráfico
Soraia Lúcia da Silva
Sistemas de Informação
PUC Minas São Gabriel
*
*
Gráfico do Conjunto de Soluções (inequações)
A representação gráfica de uma equação linear com duas variáveis
é uma reta. A representação gráfica de uma inequação linear com 
duas variáveis é um dos semiplanos definidos pela reta correspondente à equação.
 Ex.1: Representar graficamente a inequação: 
a) Construir a reta correspondente à equação: 
Precisamos de dois pontos:
Fazendo teremos (0,5)
Fazendo teremos (10,0)
 
Testar a inequação: 
Tomamos um ponto qualquer de uma das regiões limitadas pela reta, por exemplo o ponto ( , ).
 
*
*
Substituindo na inequação: ou ,
 o que é verdadeiro, portanto a região das soluções da inequação é aquela que contem o ponto testado.
Gráfico do Conjunto de Soluções (inequações)
*
*
Resolução gráfica de modelos de programação linear
Essa técnica consiste em representar num sistema de eixos ortogonais o conjunto das possíveis soluções do problema, isto é, o conjunto de pontos (x1, x2) que obedecem ao grupo de restrições impostas pelo sistema em estudo. O desempenho do modelo é avaliado através da representação gráfica da função objetivo. As soluções são classificadas de acordo com sua posição no gráfico.
Aplicável para modelos com 02 variáveis de decisão. É claro que, se existirem muitas restrições, o gráfico poderá ficar poluído, mas a solução, embora dificultada, é tecnicamente possível.
*
*
Resolução gráfica de modelos de programação linear
Exemplo.: Minimizar z = 40 x1 + 36 x2
 
Sujeito a:
*
1º . Passo: identificar a região viável do modelo, isto é, quais são os pares (x1, x2) que satisfazem a todas as restrições.
 No exemplo: x1 = 8, x2 = 10 corresponde a
 uma solução viável.
2º . Passo: achar a melhor solução viável, denominada solução ótima e denotada por (x1*, x2*), que leva ao valor ótimo da função-objetivo z*.
*
Etapas a serem seguidas na resolução gráfica
*
1º . Passo
Traçar eixos cartesianos, associando cada variável de decisão. No exemplo: x1 para o eixo das abscissas e x2 para o eixo das ordenadas.
Observar que as restrições de (1) a (3) correspondem a semiplanos associados, respectivamente, às retas suportes dadas por x1 = 8, x2 = 10, e 5x1 + 3x2 = 45. Notar que para cada reta suporte existem dois semiplanos, para identificar qual deles é de interesse no caso, basta testar se a origem (0, 0) pertence ou não ao semiplano associado à restrição em questão (ver figura).
As restrições de não-negatividade, x1  0 e x2  0, implicam que os pares (x1, x2) viáveis estão no 1o. Quadrante dos eixos considerados (ver figura).
*
Etapas a serem seguidas na resolução gráfica
*
2º . Passo
Observar que a função-objetivo, ao fixarmos um valor para z, representa uma reta. Alterações neste valor de z gera uma família de retas paralelas. 
No exemplo: considere a reta obtida fazendo z = 600, isto é, a reta dada por 40x1 + 36x2 = 600 (ver figura). Percebe-se que ao se traçar retas paralelas no sentido de ficar mais próximo da origem (0, 0), o valor de z diminui. De fato pode-se verificar que a reta paralela que contém algum ponto (no caso o ponto a = (8, 5/3)) da região viável, e está mais próxima da origem, corresponde a um valor de z = 380 (ver figura).
Assim o valor ótimo da função-objetivo (“custo da inspeção”) será dado por z* = 380, e o ponto a = (8, 5/3) será a solução ótima para o modelo em estudo, isto é x1* = 8 e x2* = 5/3 = 1,67. 
Importante: em geral, arredondar pode não levar a soluções inteiras ótimas.
*
Etapas a serem seguidas na resolução gráfica
*
*
Exemplo.: Minimizar z = 40 x1 + 36 x2
 
Sujeito a:
Associar ao eixo das abscissas a variável x1 e ao eixo das ordenadas a variável x2.
Observe que as restrições (1), (2), (3) correspondem a semiplanos; e a restrição (4) corresponde aos pontos do 1o. Quadrante.
 
Etapas a serem seguidas na resolução gráfica
*
*
Etapas a serem seguidas na resolução gráfica
*
Ocorrência de soluções ótimas alternativas
*
Considere o seguinte exemplo:
 			Maximizar z = x1 + 2x2
			Sujeito a: 
 
 
Observe que a reta z* = 10 = x1 + 2x2, associada ao valor ótimo da função-objetivo, coincide com o lado BC da região viável. Assim todos os pontos de coordenadas (x1, x2) no segmento de reta bc são soluções viáveis ótimas.
*
Ocorrência de solução ilimitada
Considere o exemplo anterior sem a restrição x1 + 2x2  10. A região viável correspondente a este novo problema está apresentada abaixo. 
Neste caso, ao traçar paralelas à reta z = 6 = x1 + 2x2 que se afastem da origem estaremos melhorando o valor da função-objetivo (pois o problema é de maximização). 
Como se percebe, na figura abaixo, não há limitação, na região viável, para o crescimento do valor da função-objetivo. Assim o valor ótimo de z tende a ser + . 
*
 
Observe que em situações reais isto não pode ocorrer! Geralmente significa que uma ou mais restrições foram omitidas na etapa de modelagem.
*
Visualização de situações possíveis
*
X1
*
*
Visualização de situações possíveis
*
*
Visualização de situações possíveis
*
Exemplo: Avaliação do Objetivo
Avaliar o desempenho da função objetivo: 
Maximizar L = na região de soluções do gráfico abaixo:
*
*
Solução: 
 
Escolhemos um valor arbitrário para L, por exemplo, o valor 10.
A equação: fornece o conjunto de pontos 
que dão para L o valor 10. Vamos representar esses pontos:
Fazendo teremos (0, 2)
Fazendo teremos 		 (5, 0)
 
Escolhemos um segundo valor para L, por exemplo, o valor 15, então: 
Fazendo teremos (0, 3)
Fazendo teremos 		 (7.5, 0)
 
*
*
*
Graficamente, teremos:
Verificamos do gráfico que:
 
À medida que atribuímos valores a L, obtemos retas paralelas.
À medida que o valor de L aumenta, a reta se afasta da origem do sistema de eixos.
Podemos concluir que pelo ponto P do gráfico teremos a paralela de maior valor que ainda apresenta um ponto na região de soluções. Portanto, o ponto P é a solução que maximiza L na região de soluções dadas.
 
Como P = (0,6) e L = , substituindo e teremos:
L = 2.0 + 5.6 ou L máximo = 30
*
Teoremas a respeito das soluções
Teorema I: O conjunto de todas as soluções viáveis de um 
 modelo de programação linear é um conjunto convexo.
Obs.: Conjunto convexo é um conjunto de pontos em que todos os segmentos de reta que unem dois de seus pontos são internos ao conjunto, isto é, todos os pontos de cada segmento também pertencem ao conjunto original.
Teorema II: Toda solução compatível básica (solução óbvia) do sistema de equações lineares de um modelo de programação linear é um ponto extremo do conjunto de soluções viáveis, isto é, do conjunto convexo de soluções.
Teorema III: Se uma função objetivo possui um único ponto ótimo finito, então esse é um ponto extremo do conjunto convexo de soluções viáveis.
Teorema IV: Se a função objetivo assume o valor ótimo em mais de um ponto do conjunto de soluções viáveis (soluções múltiplas), então ela assume esse valor para pelo menos dois pontos extremos do conjunto convexo e para qualquer combinação convexa desses pontos extremos, isto é, todos os pontos do segmento de reta que une esses dois extremos, ou seja, a aresta do polígono que os contém.
*
*
Exemplo
1) Um fazendeiro deseja otimizar as plantações de arroz e milho na sua fazenda. O fazendeiro quer saber
as áreas de arroz (x1) e milho (x2) que devem ser plantadas para que o seu lucro nas plantações sejam o máximo. O seu lucro por unidade de área plantada de arroz é 5 u.m., e por unidade de área plantada de milho é 2 u.m.
As áreas plantadas de arroz e milho não devem ser maiores que 3 e 4 respectivamente. Cada unidade de área plantada de arroz consome 1 homem-hora. Cada unidade de área plantada de milho consome 2 homens-hora. O consumo total de homens-hora nas duas plantações não deve ser maior que 9.
*
*
Solução:
 
Chamemos de x1 a área a ser plantada de arroz e x2 a de milho.
 
função objetivo: Max Z = 5x1 + 2x2
		 s.a:
				x1  3 (I)
				x2  4 (II) 
			 x1 + 2x2  9 (III)
			 x1 ≥ 0 , x2 ≥ 0
*
*
*
A Fig. 1 ao lado é o resultado do lançamento gráfico das retas (I), (II) e (III); Consequentemente determinamos os pontos vértices A(0,0), B(3,0), C(3,3), D(1,4) e E(0,4).
Como a função objetivo é Z = 5x1 + 2x2, que aplicada em cada vértice do polígno restritivo nos fornece os seguintes valores:
 
ZA(0,0) = 0
ZB (3,0) = 15
ZC(3,3) = 21 Verifica-se que o ponto “C” é o que fornece o maior
ZD(1,4) = 13 valor para a função objetivo (Zmáx = 21).
ZE(0,4) = 8
 
Concluímos que o lucro máximo do fazendeiro de 21 unidades monetárias, desde que plante 3 unidades de área de arroz e 3 unidades de área de milho.
 
*
Exercício
Uma empresa de comida canina produz dois tipos de rações: Tobi 
e Rex. Para a manufatura das rações são utilizados cereais e carne. Sabe-se que: 
a ração Tobi utiliza 5 kg de cereais e 1 kg de carne, e a ração Rex utiliza 4 kg de carne e 2 kg de cereais;
o pacote de ração Tobi custa $ 20 e o pacote de ração Rex custa $ 30;
o kg de carne custa $ 4 e o kg de cereais custa $ 1;
estão disponíveis por mês 10 000 kg de carne e 30 000 kg de cereais.
 
Deseja-se saber qual a quantidade de cada ração a produzir de modo a maximizar o lucro.
 
Nosso modelo deseja maximizar o lucro (Z) a partir da quantidade de ração Tobi (x1) e de ração Rex (x2). A Tabela 3.1 apresenta o cálculo do lucro unitário de cada ração.
*
*
*
A função objetivo pode ser escrita como:
 
Max Z = 11 x1 + 12 x2
sujeito a: 1 x1 + 4 x2  10000 	(restrição de carne)
 	5 x1 + 2 x2  30000 	(restrição de cereais)
 	 x1 , x2 ≥ 0 		(não negatividade)
*
*