Ficha 03- solucao grafica de Programacao Linear (1)

Prévia do material em texto

Instituto Superior Politécnico de Tete Investigação Operacional 
 
 
Docente: António Onofre 1/6 
 
 
SOLUÇÃO GRÁFICA EM PROGRAMAÇÃO LINEAR O método gráfico pode ser aplicado para resolver os problemas de programação linear de forma eficiente, apenas quando a função objectivo e o conjunto das restrições tiver duas variáveis de decisão. A resolução de problemas de Programação Linear pelo Método Gráfico, inclui duas etapas: 1. Determinação gráfica de soluções veiáveis, 2. Determinação da solução óptima entre todos os pontos viáveis a região de soluções. 
 
Etapa 1. Determinação da região de soluções viáveis 
 
Problema: A Reddy Mikks produz tintas para interiores e exteriores com base em duas matérias-primas, M1 e M2. A tabela seguinte apresenta os dados básicos do problema: Toneladas de matéria-prima por tonelada de Disponibilidade máxima diária (ton) Tinta para exteriores Tinta para interiores Matéria-prima M1 6 4 24 Matéria-prima M2 1 2 6 Lucro por tonelada (1.000 u.m.) 5 4 Uma pesquisa do mercado indica qua a demanda diária de tintas para interiores não pode ultrapassar a de tintas para exteriores por mais de 1 tonelada. Além disso, a demanda máxima diária de tinta para interiores é de 2 toneladas. A Reddy Mikks quer determinar o mix óptimo (melhor) de produtos de tintas para interiores e exteriores que maximize o lucro total diário. 
Resolução: Definição de variáveis: 
1x -toneladas de tinta para exteriores produzidas diariamente 
2x -toneladas de tinta para interiores produzidas diariamente 
Instituto Superior Politécnico de Tete Investigação Operacional 
 
 
Docente: António Onofre 2/6 
 
 
Modelo de Pl da Reddy Mikks é: 








≥
≤
≤+−
≤+
≤+
+=
0,
2
1
62
2446
45
21
2
21
21
21
21
xx
x
xx
xx
xx
xxMaxZ
 
 Em primeiro lugar, levamos em conta as restrições de não-negatividade 00 21 ≥≥ xexNa Figura 1, o eixo horizontal x1 e o eixo vertical x2, representam as variáveis tinta para exteriores e tinta para interiores respectivamente. Assim, a não-negatividade das variáveis restringe a área da região de soluções ao primeiro quadrante que se encontra acima do eixo x1 e a direita do eixo x2. Para levar em conta as quatro restrições restantes, em primeiro lugar substituir cada desigualdade por uma equação e depois representar em gráfico a linha recta resultante localizando dois pontos distintos nela. Por exemplo, apos substituir 2446 21 ≤+ xx pela linha recta 2446 21 =+ xx , podemos determinar dois pontos distintos, primeiro ao fazer 01 =x para obter 64242 ==x , e, após, ao fazer 02 =x para obter 46241 ==x . Assim, a recta passa pelos dois pontos, (0,6) e (4,0), como mostra a figura 1. Em seguida, considere o efeito da desigualdade. Tudo que ela faz é dividir o plano ( 21, xx) em dois meios-espaços, um de cada lado da recta representa no grafico. Só uma dessas duas metades satisfaz a desigualdade. Para determinar o lado correcto, tome (0,0) como um ponto de referência. Se ele satisfazer a desigualdade, o lado no qual ele se encontra é a meia-região viável; caso contrario, o viável é o outro lado. A utilização do ponto de referência (0,0) é ilustrada com a restrição 2446 21 ≤+ xx . Como 00406 =+ xx é menor do que 24, a meia-região que representa a desigualdade inclui a origem. Em termos de cálculo, é conveniente selecionar (0,0) como o ponto de referência, a menos que, por acaso, a recta passe pela origem, quando então qualquer ponto pode ser usado. 
Instituto Superior Politécnico de Tete Investigação Operacional 
 
 
Docente: António Onofre 3/6 
 
 
 Figura 1. Determinação da região de soluções viáveis A aplicação do procedimento do ponto de referência a todas as restrições do modelo produz as restrições mostradas na figura 1. A região de soluções viáveis do problema representa a área do primeiro quadrante na qual todas as restrições são satisfeitas simultaneamente. Na figura, qualquer ponto que esteja dentro ou sobre o contorno da área ABCDEF é parte da região de soluções viáveis. Todos os pontos fora dessa área são inviáveis. 
 
Etapa 2. Determinação da solução óptima 
 
Primeira Possibilidade A região viável do grafico da figura 1 é delimitada pelos segmentos de recta que unem os pontos A,B,C,D,E e F. Qualquer ponto dentro ou sobre o contorno do espaco ABCDEF é viável. Como a regiao viavel ABCDEF consiste em um número infinito de pontos, precisamos de um procedimento sistemático para identificar a solução óptima. A determinação da solução óptima requer identificar a direção na qual a função lucro 
21 45 xxz += aumenta (lembre-se de que estamos a maximizar z), Podemos fazer isso designando valor crescentes arbitrário a z. Podemos, usar z=10 e z=15equivaleria a representar em gráfico as duas rectas, 1045 21 =+ xx e 1545 21 =+ xx . Assim, a direcção do aumento de z é mostrada na figura 2. A solução óptima ocorre em C, que é o ponto na região de soluções além do qual qualquer aumento adicional levara z para fora dos contornos ABCDEF. 
Instituto Superior Politécnico de Tete Investigação Operacional 
 
 
Docente: António Onofre 4/6 
 
 
Os valores de 1x e 2x relacionados com o ponto óptimo C são determinados pela resolução das equações relacionadas com as rectas (1) e (2), isto é, 
62 21 =+ xx A solução é 31 =x e 5,12 =x , com z=5x3+4x1,5=21. Isso representa um mix de produto diário de 3t de tinta para exterior e 1,5t de tinta para interiores. O lucro diário associado é de 21.000 u.m. 
 Figura 2. Determinação da solução óptima Uma característica importante da solução óptima de PL é que ela sempre esta relacionada com um ponto extremo da região de soluções (em que duas rectas se cruzam). Isso é valido ate se, por acaso, a função objectivo for 21 46 xxz += , que é paralela a restrição 1, sempre podemos dizer que a solução óptima ocorre no ponto B ou no ponto extremo C. Na verdade, qualquer ponto sobre o segmento de recta BC será uma alternativa óptima, mas a observação importante aqui é que o segmento de recta BC é totalmente definido pelos pontos extremos B e C. 
Ou, em alternativa em designar valores crescentes arbitrários a Z, pode optar por um procedimento mais pratico: 1. Igualar a função objectivo a zero, o que significa que o valor minino de Z é igual a zero em seguida expressar 2x em função de 1x ou vice-versa, 
2446 21 =+ xx
Instituto Superior Politécnico de Tete Investigação Operacional 
 
 
Docente: António Onofre 5/6 
 
 
2. Traçar a recta Z no mesmo sistema cartesiano onde estão todas as restrições anteriores (figura 1). A recta Z deve fazer pelos pontos (0,0) e por ouro qualquer 
),( 211 xxP . 3. Deslocar ou traçar uma família de rectas paralelas a função objectivo no sentido desejado, ate atingir o primeiro ponto (min) ou o ultimo ponto (max). Este é o ponto óptimo. As coordenadas desde ponto definem as quantidades a combinar na função objectivo. 
Segunda Possibilidade 1. Calcular as coordenadas de todos os pontos que estão nas extremidades da área de soluções viáveis ABCDEF. 2. Calcular o valor da função objectivo para cada ponto. O valor máximo é a solução óptima para o problema de maximização e o mínimo é a solução óptima para o problema de minimização. Da figura 1, temos os seguintes pontos: A(0,0); B(4,0); C(3,1.5); D(2,2); E(1,2) e F(0,1). Substituindo na função objectivo temos: 
00.40.5)0,0( =+=AZ 
200.44.5)0,4( =+=BZ 
215.1.43.5)5,1,3( =+=CZ - corresponde ao valor máximo da função objectivo 
182.42.5)2,2( =+=DZ 
132.41.5)2,1( =+=EZ 
41.40.5)1,0( =+=FZ O valor obtidos da função objectivo, pode concluir que o ponto óptimo para a maximização de Z é o C(3,1.5). 
Instituto Superior Politécnico de Tete Investigação Operacional 
 
 
Docente: António Onofre 6/6 
 
 
Bibliografia 
 Handy, A. Taha. (2008)Pesquisa Operacional: uma visão geral, Practice Hill International. 8 Edição, São Paulo. Mulenga, Alberto (2006), Investigação Operacional uma abordagem introdutória, Maputo.