11644_PROGRAMAÇÃO LINEAR

  • Published on
    14-Aug-2015

  • View
    39

  • Download
    4

Embed Size (px)

Transcript

PROGRAMAO LINEAR

EXEMPLO ORIENTATIVO: Uma fbrica produz CPUs de dois tamanhos diferentes, grande e pequena, que apresentam lucros unitrios de respectivamente $500 e $200. Ela deseja saber quantas unidades de cada um destes aparelhos dever fazer para que o lucro obtido pela operao seja mximo. As capacidades de produo da fbrica so as seguintes: 6 gabinetes grandes por hora 15 gabinetes pequenos por hora 24 placas-me por hora 20 placas de vdeo por hora Cada CPU grande composta por: 1 gabinete grande 3 placas me 2 placas de vdeo Cada CPU pequena composta por: 1 gabinete pequeno 1 placas me 1 placas de vdeo Podemos resumir estes dados na seguinte tabela:COMPONENTES CPU GRANDE CPU PEQUENA PRODUO HORRIA Gabinete Grande 1 6 Gabinete Pequeno 1 15 Placa me 3 1 24 Placa de video 2 1 20

Modelar o problema significa definir: 1. As variveis de entrada 2. A funo objetivo 3. As restries e a partir delas montar um sistema de equaes e inequaes. No nosso caso temos: 1. Variveis de entrada = o nmero de CPUs a serem produzidas, ou seja:

2. O objetivo maximizar o lucro, portanto a funo objetivo :

3. As restries so relativas capacidade produtiva de cada componente:

FE Peres/MM do Fanno

Evidentemente que o modelo de PL impe outra restrio lgica, no se pode produzir uma quantidade negativa de CPUs, portanto:

Os valores de x1 e x2 que maximizam o lucro desta operao sero obtidos pela resoluo deste sistema de equaes e inequaes, ou seja, os valores que atendem simultaneamente a todas elas. Existem alguns mtodos de soluo: Mtodo grfico, aplicvel a problemas com duas variveis de entrada. Mtodo Simplex, mtodo geral, aplicvel a problemas com qualquer quantidade de variveis de entrada. Mtodo de transporte, aplicvel a um tipo especfico de problema, mas com qualquer quantidade de variveis de entrada.

SOLUO GRFICA:Iremos colocar todas as restries em um nico diagrama ortogonal no qual o eixo horizontal representar as quantidades produzidas de CPUs grandes e o eixo vertical, as quantidades produzidas de CPUs pequenas:

Teoricamente qualquer ponto neste diagrama ortogonal seria soluo para o nosso problema, no entanto, veremos que devido s restries pouco a pouco iremos reduzir o resultados possveis. A primeira restrio a dos gabinetes grandes: no possvel a produo de mais do que seis gabinetes por hora nem a produo de uma quantidade negativa de gabinetes, ou seja: Graficamente teramos:2

FE Peres/MM do Fanno

Perceba que s podem ser aceitos como solues para este problema os pontos coordenados esquerda da reta desenhada. Restrio semelhante ocorre com os gabinetes pequenos:

Perceba que s podem ser aceitos como solues para este problema os pontos coordenados abaixo da reta desenhada. At esse momento as restries j reduziram as solues possveis aos pontos coordenados circunscritos pelos eixos e pelas duas retas desenhadas.3

FE Peres/MM do Fanno

Em sequencia temos as restries da quantidade de placas me produzidas, ou seja: Observe que se x1 for igual a zero x2 dever ser menor ou igual a 24 para manter a inequao e se x2 for igual a zero x1 dever ser menor ou igual a 8. Note as resolues abaixo:

Portanto a inequao tem dois pontos caractersticos pelos quais podemos traar a reta que caracteriza: (0;24) e (8;0). Graficamente temos:

Perceba que qualquer ponto coordenado direita desta reta no permitido, pois desobedeceria a inequao. Retiramos mais um pedao do campo de solues permitidas. A ltima restrio a da placa de vdeo. Seguindo o mesmo raciocnio das placas mes determinamos a reta caracterstica:

Os pontos caractersticos que definem a reta so (0;20) e (10;8), e graficamente:

4

FE Peres/MM do Fanno

Mais uma parte das solues possveis foi retirada restando um polgono de solues possveis. Veja a seguir:

Qualquer ponto desta rea sombreada soluo para o problema, existindo, portanto infinitas solues, mas somente uma delas apresenta lucro mximo. fcil entender qual a soluo tima. Cada lado do polgono h um recurso que utilizado ao mximo, mas num vrtice h dois recursos utilizados ao mximo simultaneamente, portanto a soluo tima estar num dos vrtices do polgono. Este o teorema fundamental da programao linear.5

FE Peres/MM do Fanno

Para ficar mais claro: no lado (aresta) definido pelos pontos BC estamos produzindo o mximo possvel de gabinetes possvel. J, no ponto C, alem de estarmos produzindo o mximo de gabinetes possveis estamos tambm produzindo o mximo possvel de placas de vdeo. Antes tnhamos infinitas solues possveis, agora com este teorema restaram apenas seis solues que podem ser timas e por tentativas podemos definir qual essa soluo tima. Veja a tabela a seguir:VRTICE CPU GRANDE CPU PEQUENA LUCRO x1 x2 500x1+200x2 A 0 0 0+0=0 B 0 15 0 + 3000=3000 C 2,5 15 1250+3000=4250 D 4 12 200+2400=4400 E 5 6 3000+1200=4200 F 5 0 3000+0=3000

Portanto o ponto de mximo lucro o ponto D. Consequentemente, deve-se montar 4 CPUs grandes por hora e 12 CPUs pequenas por hora, o que gerar um lucro de $4400,00 por hora. Para se atingir esse lucro mximo sero produzidos: 4 gabinetes grandes por hora 12 gabinetes pequenos por hora 24 placas me por hora 20 placas de vdeo por hora. Observao: Iro sobrar dois gabinetes grandes por hora e trs gabinetes pequenos por hora. No haver sobras de placas me e placas de vdeo. SOLUO PELO ALGORITMO SIMPLEX Perceba que esse processo grfico tem muitas limitaes, a comear pelo fato que s pode ser usado para duas variveis de entrada. Foi necessrio o desenvolvimento de mtodo mais completo para realizar esses clculos. Esse mtodo conhecido como SIMPLEX. O mtodo simplex, ao contrrio do mtodo grfico, trabalha com equaes e no com inequaes. Deste modo as inequaes devem ser transformadas em equaes e isso feito com a adio de variveis. Vamos, portanto determinar as variveis que podem ser aparecer em um problema deste tipo. Utilizaremos as definies estabelecidas por Contador: Varivel de entrada a varivel que deve ser otimizada e surge naturalmente do enunciado do problema. No caso do exerccio das CPUs, que continuaremos usar como exemplo, as variveis de entrada so o nmero de CPUs grandes (x 1) e o nmero de CPUs pequenas (x2). Termo independente o valor numrico de uma restrio e, por conveno, colocado direita do sinal da inequao. No nosso exemplo, so as quantidade limitantes produzidas para cada componente.6

FE Peres/MM do Fanno

Varivel de folga ou residual, utilizada quando a desigualdade for do tip o , uma varivel no negativa, somado ao lado esquerdo da desigualdade, e numericamente igual diferena entre o termo independente e os valores esquerda da desigualdade. Corresponde numa determinada soluo parcela no aproveitada de recursos. No nosso exemplo so as eventuais sobras de componentes (gabinetes ou placas) Varivel de excesso, utilizada quando a desigualdade for do tipo , uma varivel negativa, subtrada do lado esquerdo da desigualdade, e numericamente igual diferena entre o valor do termo independente e o valor das variveis que esto esquerda da desigualdade. No nosso no existiro valores deste tipo, pois um problema de maximizao. Varivel artificial uma varivel adicionada esquerda em todas as restries que no contenham uma varivel de folga, sendo utilizada, portanto nas restries que so originalmente com sinal ou =. A varivel artificial necessria porque a soluo inicial do Simplex obtida igualando a zero todas as variveis de entrada e todas as de excesso, o que corresponde a fazer cada varivel de folga e cada varivel artificial igual ao valor do termo independente da equao da qual a varivel em questo aparece. No nosso exemplo no existem variveis deste tipo, visto serem inequaes do tipo .

Desta forma, no nosso exemplo as inequaes seriam transformadas em equaes, da seguinte forma: Inequaes:

Equaes:

Importante notar que na frente de cada varivel colocamos seu coeficiente correspondente, mesmo quando no teria necessidade, por ser zero ou um. Fizemos isso, para evidenciar os coeficientes que sero utilizados no algoritmo Simplex. Esse equacionamento tem seis valores desconhecido (as incgnitas x1; x2; x3; x4; x5; x6) e apenas quatro equaes (as relacionadas acima), logo o sistema de equaes indeterminado, tem infinitas solues viveis e no apenas uma. Lembre-se que em matemtica s conseguimos resolver um sistema de equaes quando o nmero delas for igual ao nmero de incgnitas.7

FE Peres/MM do Fanno

Nesse caso, portanto, temos infinitas solues viveis (as solues mostradas na rea hachurada do grfico mostrado anteriormente). A soluo tima ser pesquisada atribuindo valores arbitrrios a um nmero de incgnitas igual ao nmero total delas menos o nmero de equaes. No nosso exemplo, atribuiremos valores arbitrrios a duas incgnitas (resultado da subtrao seis incgnitas menos duas equaes). Essa resoluo exige conhecimentos matemticos que de modo geral no so do domnio de alunos de graduao de Administrao, por conseguinte iremos apresent-la de forma descritiva, utilizando o problema das CPUs como ilustrao e apresentando o mtodo passo a passo. 1 passo: Estabelecer a planilha do algoritmo: uma planilha de diversas linhas e colunas, na qual reservada uma coluna para cada varivel e mais quatro colunas de clculos. Acompanhe a planilha para o nosso exemplo e o significado de cada coluna:

A coluna base contm as variveis que esto sendo consideradas numa determinada tentativa. No nosso caso teremos quatro variveis em cada tentativa. Para as outras duas ser atribudo o valor zero. As seis colunas seguintes so reservadas para cada uma das variveis envolvidas. No nosso caso as duas variveis de entrada (x1 e x2) e as quatro variveis residuais (x3; x4; x5 e x6). A antepenltima coluna reservada para os termos independentes das equaes (no nosso exerccio as restries de produo). A penltima coluna destinada a receber uma diviso entre