Baixe o app para aproveitar ainda mais
Prévia do material em texto
60 Unidade III Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Unidade III 7 Problemas envolvendo minimização da Função objetivo 7.1 algoritmo simplex O problema de minimização, ao contrário do problema de maximização, tem pelo menos umas de suas restrições do tipo ≥. Assim sendo, se no problema de maximização é necessário utilizarem‑se variáveis de folga, nos casos de minimização devemos introduzir variáveis de excesso nas restrições do tipo ≥. Como foi mencionado anteriormente, variável de excesso é uma variável não negativa, subtraída do lado esquerdo da desigualdade, e é numericamente igual à diferença entre o valor do termo independente e o valor das variáveis que estão à esquerda da desigualdade. Por outro lado, variável artificial é uma variável adicionada à esquerda em todas as restrições que não contenham uma variável de folga, sendo utilizada nas restrições que têm originalmente o sinal ≥. Em um problema de minimização, sempre aparecerão algumas variáveis artificiais. Como a solução básica inicial do Simplex é obtida igualando a zero todas as variáveis de entrada, a variável artificial torna‑se necessária para que a solução básica inicial não seja constituída pelas variáveis de excesso, que, como é subtraída na equação, acarretaria solução básica de valores negativos, o que contraria a lógica do Simplex. Esse procedimento corresponde a fazer, na solução básica inicial, as variáveis de entrada e de excesso iguais a zero e, consequentemente, as variáveis de folga e as artificiais iguais ao valor do termo independente da equação. Observe, no entanto, que, na solução ótima, as variáveis artificiais devem ser iguais a zero. Para que isso ocorra, atribui‑se, na Função Objetivo, um coeficiente M. Esse valor é altíssimo em relação a essas variáveis (por exemplo, um custo altíssimo), e dessa forma o Simplex irá, na solução ótima, imputar zero às variáveis artificiais. Contador (1998) relaciona as alterações necessárias no algoritmo Simplex de maximização para se resolver um problema de minimização. São elas: • introduzir as variáveis de excesso e artificial; • transformar a Função Objetivo de minimizar para maximizar e trocar o seu sinal, pois minimizar uma função equivale a maximizar sua simétrica; • mudar a maneira de calcular a linha de controle da primeira solução básica (isso será explicado no próximo exemplo); 61 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal • a variável que entrará na base seguinte é aquela da coluna que apresentar maior valor positivo na linha de controle (perceba que é o procedimento oposto ao problema de maximização); • a variável que sairá da base é aquela que apresentar o menor valor não negativo na coluna termo independente dividido pela coluna de trabalho (outra alteração em relação ao problema de maximização). Explicaremos esse cálculo utilizando um exemplo apresentado pelo professor José Celso Contador (1998): Um fabricante de ração deseja produzir um determinado tipo de ração, conforme especificação do Ministério da Agricultura, e pelo mínimo custo. O Ministério especifica apenas quatro nutrientes A, B, C e D, exigindo que um quilo de ração contenha: • no mínimo, 120g do nutriente A; • no mínimo, 360g do nutriente B; • no máximo, 360g do nutriente C; • exatamente 180g do nutriente D. O fabricante dispõe de três alimentos: milho, alfafa e silagem. E cada quilo desses alimentos contém os seguintes pesos em quilos dos nutrientes: Tabela 21 Nutriente Milho Alfafa Silagem A 0,1 0,2 0,1 B 0,4 0,4 0,3 C 0,2 0,2 0,1 D 0,1 0,2 0,1 Outros 0,2 0,4 Total 1,0 1,0 1,0 Sabendo‑se que o quilo do milho custa $ 0,50, o da alfafa $ 0,20 e o da silagem $ 0,10, determinar qual a mistura que proporciona mínimo custo da ração especificada. a) Modelagem do problema Representaremos as quantidades num quilo de ração de milho, alfafa e silagem, respectivamente, pelas letras x, y e z. A Função Objetivo, portanto, será: Custo da ração = 0,5x + 0,2y + 0,1z 62 Unidade III Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 É evidente que nosso objetivo é minimizar o valor do custo da ração; portanto, devemos determinar os valores de x, y e z que resultem no menor custo possível (a solução ótima). Esse cálculo, no entanto, só tem sentido à luz das restrições, que são as seguintes: Para o nutriente A: 0,1x + 0,2y + 0,1z ≥ 0,12 kg Para o nutriente B: 0,4x + 0,4y + 0,3z ≥ 0,36 kg Para o nutriente C: 0,2x + 0,2y + 0,1z ≤ 0,36 kg Para o nutriente D: 0,1x + 0,2y + 0,1z = 0,18 kg Os nutrientes que não são especificados não constituem restrição física, mas precisam ser mostrados numa equação para manter a lógica do sistema matemático. São as restrições lógicas: Outros nutrientes: 0,2x + 0y + 0,4z ≥ 0 kg Por último, é necessário que os três alimentos juntos (milho, alfafa e silagem) perfaçam um quilo: x + y + z = 1kg Nesse ponto, precisamos fazer uma consideração. Trabalhar no Simplex com números fracionários não é recomendável. Por isso, vamos fazer um artifício matemático: multiplicar as inequações por 10 (o que não as altera) e posteriormente os termos independentes e a Função Objetivo por 10 também. Esse último artifício afeta o resultado final, ou seja, quando chegarmos ao resultado, deveremos dividi‑lo por 10, voltando à situação original. Portanto, as inequações ficarão com os seguintes formatos: Para o nutriente A: 1x + 2y + 1z ≥ 12 kg Para o nutriente B: 4x + 4y + 3z ≥ 36 kg Para o nutriente C: 2x + 2y + 1z ≤ 36 kg Para o nutriente D: 1x + 2y + 1z = 18 kg Outros nutrientes: 2x + 0y + 4z ≥ 0 kg x + y + z = 10kg Perceba que existem algumas redundâncias que permitem eliminar inequações, o que é muito bom, porque simplificará os cálculos. As inequações para o nutriente A e para o nutriente D são redundantes. 63 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal Ficaremos com a mais restritiva, ou seja, a inequação do nutriente D (se a inequação for igual a 18 será automaticamente maior do que 12, daí a redundância). Outra redundância é a inequação para outros nutrientes. Também pode ser eliminada, pois se os valores de x, y e z têm que ser positivos, a inequação será automaticamente positiva. Ficamos, assim, com quatro inequações: Para o nutriente B: 4x + 4y + 3z ≥ 36 kg Para o nutriente C: 2x + 2y + 1z ≤ 36 kg Para o nutriente D: 1x + 2y + 1z = 18 kg x + y + z = 10kg b) Modelo formal Lembre‑se de que para transformar uma inequação do tipo ≤ em equações, é necessário introduzir uma variável de folga. Como já definido anteriormente, variável de folga ou residual é uma variável não negativa somada ao lado esquerdo da desigualdade e numericamente igual à diferença entre o termo independente e os valores à esquerda da desigualdade. Corresponde, numa determinada solução, à parcela não aproveitada dos recursos. Simbolizaremos essas variáveis como Ri. Já para transformar as inequações do tipo ≥ em equações, é necessário introduzir uma variável de excesso. Como já definido anteriormente, variável de excesso é uma variável não negativa, subtraída do lado esquerdo da desigualdade e numericamente igual à diferença entre o valor do termo independente e o valor das variáveis que estão à esquerda da desigualdade. Simbolizaremos essas variáveis como Ei. Além dessas duas variáveis, é necessário introduzir variáveis artificiais, que são variáveis adicionadas à esquerda em todas as restrições que não contenham uma variável de folga, sendo utilizadas,portanto, nas restrições que têm originalmente o sinal ≥ ou =. Como vimos, a variável artificial é necessária porque, na solução inicial do Simplex, são igualadas a zero todas as variáveis de entrada e de excesso, o que corresponde a fazer as variáveis de folga e as artificiais iguais ao termo independente, em cada uma das equações na qual a variável aparece. Simbolizaremos as variáveis artificiais como Ai. Feitas essas considerações, teremos as seguintes equações para serem trabalhadas no Simplex: Para o nutriente B: 4x + 4y+ 3 z –E1 + A1 = 36 kg Para o nutriente C: 2x + 2y + 1z + R2 = 36 kg Para o nutriente D: 1x + 2y + 1z + A3 = 18 kg x + y + z + A4 = 10kg 64 Unidade III Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Usando o problema, vamos tentar entender o significado da variável de excesso. A especificação da ração estabelece que ela deve conter no mínimo 360 gramas do nutriente B por quilo. Como o fabricante pode oferecer um valor maior, a variável de excesso representa a quantidade de nutriente B que exceder os 360 gramas. A Função Objetivo passa a ter a seguinte forma, considerando a multiplicação por 10, como orientado anteriormente: min(5x + 2y + 1z + 0R2 + 0E1 + MA1 + MA2 + MA3) Da forma como foi apresentado, o Simplex é um algoritmo de maximização. Como o exemplo é de minimização, utilizaremos o mesmo procedimento, mas trocaremos o sinal da Função Objetivo, pois minimizar uma função corresponde a maximizar a função simétrica dela: max(– 5x – 2y – 1z – 0R2 – 0E1 – MA1 – MA2 – MA3) Resumindo, o modelo formal desse problema de ração é: max(– 5x – 2y – 1z – 0R2 – 0E1 – MA1 – MA2 – MA3) Submetido às restrições: 4x + 4y + 3z – 1E1 + 0R2 + 1A1 + 0A3 + 0A4 = 36 kg 2x + 2y + 1z + 0E1 + 1R2 + 0A1 + 0A3 + 0A4 = 36 kg 1x + 2y + 1z + 0E1 + 0R2 + 0A1 + 1A3 + 0A4 = 18 kg 1x + 1y + 1z + 0E1 + 0R2 + 0A1 + 0A3 + 1A4 = 10 kg Vemos, então, que todas as variáveis são não negativas (positivas ou zero). c) Montagem do Simplex Estabelecidas as equações, podemos montar o Simplex passo a passo: O simplex terá as seguintes colunas: Tabela 22 Base Função objetivo Variável de entrada Variável Residual/ Excesso Variável artificial Termo independente Controle Termo indepen- dente dividido pela coluna de trabalho Variável a incluir ou a excluir –5 –2 –1 0 0 –M –M –M Coeficiente da função objetivo Valor da função objetivox y z E1 R2 A1 A2 A4 b 65 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal 1º passo: variáveis da primeira base A primeira base (primeira tentativa) é constituída pelas variáveis residuais e pelas artificiais, e seu valor é igual ao respectivo termo independente. Os coeficientes das equações são colocados nos locais adequados, conforme já fizemos anteriormente. Tabela 23 Base Função objetivo Variável de entrada Variável Residual/ Excesso Variável artificial Termo independente Controle Termo indepen- dente dividido pela coluna de trabalho Variável a incluir ou a excluir –5 –2 –1 0 0 –M –M –M Coeficiente da função objetivo Valor da função objetivox y z E1 R2 A1 A2 A4 b A1 4 4 3 –1 0 1 0 0 36 –M R2 2 2 1 0 1 0 0 0 36 –O A3 1 2 1 0 0 0 1 0 18 –M A4 1 1 1 0 0 0 0 1 10 –M Controle 2º passo: linha de controle A linha de controle da primeira base é obtida pela soma dos produtos dos coeficientes da respectiva coluna pelos valores da coluna Função Objetivo, menos o valor do coeficiente da variável da coluna na Função Objetivo (isso é um produto matricial, cujos detalhes matemáticos não fazem parte do nosso programa). Veja a seguir: na coluna da variável x: [4(– M) + 2(0) + 1(– M) + 1(– M)] – (– 5) = (5 – 6M) na coluna da variável y: [4(– M) + 2(0) + 2(– M) + 1(– M)] – (– 2) = (2 – 7M) na coluna da variável z: [3(– M) + 1(0) + 1(– M) + 1(– M)] – (– 1) = (1 – 5M) na coluna da variável E1: [ – 1(– M) + 0(0) + 0(– M) + 0(– M)] – (0) = (M) Nas demais colunas, esses cálculos resultarão zero. Veja a seguir: 66 Unidade III Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Tabela 24 Base Função objetivo Variável de entrada Variável Residual/ Excesso Variável artificial Termo indepen- dente Controle Termo indepen- dente dividido pela coluna de trabalho Variável a incluir ou a excluir –5 –2 –1 0 0 –M –M –M Coeficiente da função objetivo Valor da função objetivox y z E1 R2 A1 A2 A4 b A1 4 4 3 –1 0 1 0 0 36 –M R2 2 2 1 0 1 0 0 0 36 –O A3 1 2 1 0 0 0 1 0 18 –M A4 1 1 1 0 0 0 0 1 10 –M Controle 5‑6M 2‑7M 1‑5M M 0 0 0 0 A coluna Valor da FO (Função Objetivo) é obtida pela multiplicação da coluna Termo Independente pela coluna Coeficiente da Função Objetivo. O valor na linha de controle é a soma desses produtos. 36(–M) + 36(0) + 18(–M) + 10(–M)= – 64M Em outras palavras, esse valor é aquele da primeira solução básica, obtida diretamente na Função Objetivo. Como, numa solução básica, as variáveis que não estão na base são iguais a zero e as outras são iguais aos respectivos termos independentes, a Função Objetivo acaba reduzida à expressão anterior. Veja a seguir se fizéssemos pela Função Objetivo, como o resultado seria idêntico: – 5(0) – 2(0) – 1(0) – 0RA – 0E1 – 36M – 18M – 10M= –64M Nesse momento do cálculo, a planilha do Simplex estará assim: Tabela 25 Base Função objetivo Variável de entrada Variável Residual/ Excesso Variável artificial Termo indepen- dente Controle Termo indepen- dente dividido pela coluna de trabalho Variável a incluir ou a excluir –5 –2 –1 0 0 –M –M –M Coeficiente da função objetivo Valor da função objetivox y z E1 R2 A1 A2 A4 b A1 4 4 3 –1 0 1 0 0 36 –M –36M Entra R2 2 2 1 0 1 0 0 0 36 –O –0 A3 1 2 1 0 0 0 1 0 18 –M –18M Sai A4 1 1 1 0 0 0 0 1 10 –M –10M Controle 5‑6M 2‑7M 1‑5M M 0 0 0 0 –64M –64M 67 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal 3º passo: variável que entrará na base seguinte É aquela da coluna que apresentar o maior valor negativo na linha de controle. No nosso exemplo, será a variável Y. Tabela 26 Base Função objetivo Variável de entrada Variável Residual/ Excesso Variável artificial Termo indepen- dente Controle Termo indepen- dente dividido pela coluna de trabalho Variável a incluir ou a excluir –5 –2 –1 0 0 –M –M –M Coeficiente da função objetivo Valor da função objetivox y z E1 R2 A1 A2 A4 b A1 4 4 3 –1 0 1 0 0 36 –M –36M Entra R2 2 2 1 0 1 0 0 0 36 –O –0 y A3 1 2 1 0 0 0 1 0 18 –M –18M Sai A4 1 1 1 0 0 0 0 1 10 –M –10M Controle 5‑6M 2‑7M 1‑5M M 0 0 0 0 –64M –64M 4º passo: variável que vai sair da base Será a que apresentar o menor valor não negativo na coluna termo independente dividido pela coluna de trabalho. Vale lembrar que é necessário calcular a coluna de trabalho, que é aquela coluna de divisão correspondente à variável que entrará. Tabela 27 Base Função objetivo Variável de entrada Variável Residual/ Excesso Variável artificial Termo indepen- dente Controle Termo indepen- dente dividido pela coluna de trabalho Variável a incluir ou a excluir –5 –2 –1 0 0 –M –M –M Coeficiente da função objetivo Valor da função objetivox y z E1 R2 A1 A2 A4 b A1 4 4 3 –1 0 1 0 0 36 –M–36M Entra R2 2 2 1 0 1 0 0 0 36 –O –0 y A3 1 2 1 0 0 0 1 0 18 –M –18M Sai A4 1 1 1 0 0 0 0 1 10 –M –10M Controle 5‑6M 2‑7M 1‑5M M 0 0 0 0 –64M –64M Está encerrada a primeira base. Como fizemos no exercício das CPUs, repetiremos as tentativas (bases) até que só restem números não negativos na linha de controle. Veja como ficaram os cálculos nesse exemplo: 68 Unidade III Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Tabela 28 Base Função objetivo Variável de entrada Variável Residual/ Excesso Variável artificial Termo inde- pen- dente Controle Termo indepen- dente dividido pela coluna de trabalho Variável a incluir ou a excluir –5 –2 –1 0 0 –M –M –M Coeficiente da função objetivo Valor da função objetivox y z E1 R2 A1 A2 A4 b A1 4 4 3 –1 0 1 0 0 36 –M –36M Entra R2 2 2 1 0 1 0 0 0 36 –0 –0 y A3 1 2 1 0 0 0 1 0 18 –M –18M Sai A4 1 1 1 0 0 0 0 1 10 –M –10M Controle 5‑6M 2‑7M 1‑5M M 0 0 0 0 –64M –64M Y 1 1 3/4 –1/4 0 1/4 0 0 9 –2 –18 –36 Entra R2 0 0 –1/2 –1/2 1 –1/2 0 0 18 –0 0 36 E1 A3 –1 0 –1/2 1/2 0 –1/2 1 0 0 –M 0 0 Sai A4 0 0 1/4 1/4 0 –1/4 0 1 1 –M –M 4 A3 Controle 3+M 0 (M‑2)/4 (2‑3M)/4 0 (7M–2)/4 0 0 –18–M Y 1/2 1 1/2 0 0 0 1/2 0 9 –2 –18 18 Entra R2 1 0 0 0 1 0 –1 0 18 0 0 ∞ Z E1 –2 0 –1 1 0 –1 2 0 0 0 0 –0 Sai A4 0 0 1/2 0 0 0 –1/2 1 1 –M –M 2 A3 Controle (8+M)+2 0 –M/2 0 0 M –1+1,5M 0 –18–M –18–M Y 0 1 0 0 0 0 1 –1 8 –2 –16 R2 1 0 0 0 1 0 –1 0 18 0 0 E1 –1 0 0 1 0 –1 1 2 2 0 0 A4 1 0 1 0 0 0 –1 2 2 –1 –2 Controle 4 0 0 0 0 M M–1 M –18 –18 Dessa forma, a solução do problema é a seguinte: FO = 18 (custo mínimo = 5 x 0 + 2 x 8 +1 x 2 =18), considerando que x = 0; y = 8 e z = 2. A variável de folga E1 será igual a 2 (sobra 2); a variável de excesso, igual a 18, e as artificiais, logicamente iguais a zero. Observe, no entanto, que a solução anterior é matemática. Para trabalharmos com números inteiros, multiplicamos os termos independentes e a Função Objetivo por 10; agora, para voltarmos ao original, devemos dividir por 10: 69 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal A ração será, por quilo, composta de: x = 0 kg de milho; y = 0,8 kg de alfafa; z = 0,2 kg de silagem. E o custo da ração será de: (0,8 kg de alfafa a $ 0,20 por kg) = (0,2 kg de silagem a $0,10 por kg) = 1,8 por kg de ração. 7.2 solução computacional No exemplo das CPUs, vimos a resolução computacional de um problema de maximização da Função Objetivo. Muitos casos práticos envolvem um problema de minimização, ou seja, uma situação em que queremos que a Função Objetivo assuma o menor valor possível. Nesses casos, pelo menos uma das restrições é do tipo ≥. Como anteriormente, vamos usar um exemplo para explicar os cálculos envolvidos, mas desta vez vamos nos concentrar na solução computacional, hoje em dia muito mais adequada e amplamente utilizada. Vamos imaginar a seguinte situação: Um investidor tem R$ 850.000,00 para aplicar no mercado financeiro, podendo escolher entre duas opções: um fundo de ações e um fundo de renda fixa. Cada quota do fundo de ações custa R$ 160,00 e proporciona uma taxa de retorno de 9%. Por outro ladro, cada quota do fundo de renda fixa custa R$ 215,00 e proporciona uma taxa de retorno de 5%. O objetivo do cliente é minimizar o risco, mas pretende obter o retorno de pelo menos R$ 48.000,00. Para aquisição de uma quota, o fundo de ações apresenta um índice de risco igual a 5, enquanto uma quota do fundo de renda fixa apresenta um índice de risco igual a 2. O último desejo do cliente é que pelo menos 650 quotas do fundo de renda fixa sejam adquiridas. O que se deseja é determinar quantas quotas de cada um dos investimentos disponíveis devem ser adquiridas, para que se atinja o objetivo de minimizar o índice de risco total da carteira desse investidor. Perceba que o processo de cálculo é semelhante aos casos de maximização. A grande diferença está no equacionamento matemático de uma e da outra situação. Quando utilizamos os recursos computacionais, essa diferença fica muito mais minimizada. 70 Unidade III Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 As variáveis de entrada ou variáveis de decisão são: x1 = quantidade de quotas do fundo de ações; x2 = quantidade de quotas do fundo de renda fixa. Desse modo, a Função Objetivo fica sendo: Risco total da carteira = 5x1 + 2x2 Essa Função Objetivo deve ser evidentemente minimizada. As restrições são as seguintes: Os recursos disponíveis para aplicação são de R$ 850.000,00. Considerando o valor das quotas de, respectivamente, R$ 160,00 e R$ 215,00, a primeira restrição do problema será: 160x1 + 215x2 = 850.000 O cliente espera um retorno de no mínimo R$ 48.000,00. Como as taxas de retorno são 9% e 5%, sobre cotas de valor, respectivamente, de R$ 160,00 e R$ 215,00, a segunda restrição do problema será: (0,09×160)x1 + (0,05×215)x2 ≥ 25.000 O cliente deseja que sejam adquiridas no mínimo 650 quotas de renda fixa. Isso define mais uma restrição: x2 ≥ 650 Estabelecido o equacionamento matemático, podemos montar no Excel a planilha com os dados necessários para utilizar o Solver. A planilha ficaria com o seguinte aspecto: Figura 24 71 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal As fórmulas são as seguintes: Tabela 29 Células Fórmulas B6 =B4*B5 C6 =C4*C5 D6 =SOMA(B6:C6) B10 =B5*B9 C10 =C5*C9 D10 =SOMA(B10:C10) B12 =B5*B9*B11 C12 =C5*C9*C11 D12 =SOMA(B12:C12) C13 =C5 Observe que as células B5 a C5, que receberão as quantidades a serem adquiridas de quotas, são inicialmente preenchidas com zeros. Montada a planilha com as informações de entrada e as restrições, podemos acessar o Solver, informando os dados necessários. Observe que, nesse caso, no parâmetro Igual a: optamos pela opção Mín, mostrada no quadro Parâmetros do Solver. Não nos esqueçamos também de, em Opções, selecionarmos: Presumir modelo linear, Presumir não negativos e Usar escala automática. As figuras a seguir mostram as seleções feitas: Figura 25 72 Unidade III Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Figura 26 Clicando OK na tela de Opções do Solver e em seguida Resolver na tela de Parâmetros do Solver, obteremos a solução proposta pela ferramenta: Figura 27 Ao aceitar a solução do Solver clicando OK, teremos os três relatórios já conhecidos: Microsoft Excel 12.0 – Relatório de Resposta: 73 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal Figura 28 Microsoft Excel 12.0 – Relatório de Sensibilidade: Figura 29 Microsoft Excel 12.0 – Relatório de Limites: Figura 30 74 Unidade III Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 8 aPlicações tíPicas Segundo Contador (1998), as aplicações da PL são diversas em todos os campos da Administração. Ele mostra, na lista a seguir, as principais aplicações descrevendo‑as em termos gerais: • Planejamento da produção: determinar o plano de produção de mínimo custo ou de máximo lucro, partindo da previsão de vendas, da capacidade produtiva e de fatores reais de custos ou de lucro. É o caso do problema das CPUs. Importante mencionar que a PL só é aplicada nos casos emque a capacidade produtiva é menor que a demanda: se uma fábrica pode aumentar sua capacidade produtiva rapidamente, obviamente atenderá toda a demanda, e daí não precisará lançar mão da PL. saiba mais Veja o valor do planejamento em logística, transporte e deslocamentos assistindo ao filme O Resgate do Soldado Ryan, que apresenta aspectos práticos interessantes desse processo. • Dosagem; mistura e dieta: aplicada à preparação de produtos a partir da mistura de ingredientes, objetivando minimizar o custo para uma demanda específica do produto final. É célebre o estudo feito nos Estados Unidos sobre mistura de diversos componentes para obter, ao mínimo custo, gasolina com determinada especificação. É o caso também da fabricação de ligas metálicas a partir de minérios, levando em consideração, além dos custos, certas restrições relativas ao percentual de impurezas. Problema de dieta de mínimo custo para seres humanos e animais é outra aplicação: conhecendo as quantidades necessárias de nutriente, a composição nutritiva de cada alimento e os custos respectivos, determina‑se a dieta de menor custo. • Alocação de recursos: como organizar a distribuição de recursos (materiais, mão de obra, equipamentos, capitais) para maximizar a produção ou o lucro. Aplicação característica é a da produção agrícola: em quais tipos de cultura (milho, soja, cana‑de‑açúcar) aplicar os recursos limitados de terra, máquinas agrícolas, homens, dinheiro para obter máximo lucro, podendo levar em consideração limitações na capacidade de comercializar safras e incluir rotações de cultura durante o ano. • Armazenamento: para produto de demanda sazonal (cerveja, por exemplo); quanto produzir para estocar em armazém de capacidade limitada durante o período de baixa demanda e quanto produzir em horas extras no período de alta demanda, para minimizar o custo ou maximizar o lucro. • Análise posicional: é possível determinar a melhor dentre as várias localizações possíveis para depósitos, fábricas ou distribuidores, com base nos vários fatores relativos a cada localização. 75 Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 Pesquisa OPeraciOnal • Avaliação de cargos e salários: pode‑se utilizar a programação linear em substituição à análise de regressão múltipla para determinar os pesos relativos dos fatores considerados na avaliação de salários e de cargos. Análise semelhante pode ser aplicada a qualquer situação experimental para obter melhor avaliação em suas linhas gerais. • Transporte: foi o problema que primeiro motivou o desenvolvimento da PL. Conhecida a demanda de certo produto distribuído em vários locais e conhecidas a disponibilidade de vários depósitos, a capacidade e os custos dos diversos modais de transporte (trem, navio, caminhão, avião), é possível determinar qual depósito deverá atender cada um dos destinos e qual a quantidade a ser transportada, de modo a minimizar custos. Aplicam‑se também nos casos de transbordos em armazéns intermediários, abastecidos por meios de transporte de longa distância e que abastecem lojas ou armazéns urbanos por meio de caminhões leves. Esse problema, apesar de poder ser resolvido pelo Simplex, possui métodos especiais de solução conhecidos por métodos de transporte. • Designação e atribuição de tarefas: nas situações em que um grande número de tarefas precisa ser executado por um grupo de máquinas ou pessoas diferentes, é possível determinar qual a melhor atribuição de tarefas entre as máquinas e/ou pessoas, de modo a minimizar o tempo total para produzir uma mesma quantidade. resumo Um estudo de PO consiste em construir um modelo da situação física. Um modelo de PO é definido como uma representação idealizada de um sistema organizacional. Esse sistema pode já ser existente ou ainda ser uma ideia à espera de execução. No primeiro caso, o objetivo do modelo é analisar as operações do sistema para verificar sua performance. No segundo, o objetivo é identificar a melhor estrutura do futuro sistema. A complexidade de um sistema real resulta do grande número de variáveis que comandam as operações do sistema, embora um sistema real possa envolver um número substancial de variáveis, geralmente uma pequena fração dessas variáveis domina as operações do sistema. Então, a simplificação do sistema real, em termos de um modelo condensado, identificando apenas as variáveis dominantes e as relações entre elas, é o empregado. exercícios Questão 1. O modelo matemático utilizado na programação linear é um sistema de equações e inequações. As inequações podem ser transformadas em equações por meio da introdução de variáveis diversas. Sobre isso, foram feitas as afirmações: 76 Unidade III Re vi sã o: C ris tin a - Di ag ra m aç ão : M ár ci o - 02 -0 5- 20 13 I – Um sistema de equações só é determinado quando a quantidade de incógnitas é igual à quantidade de equações. II – Uma variável de folga ou residual é utilizada quando a desigualdade for do tipo ≤; é uma variável não negativa somada ao lado esquerdo da desigualdade; é numericamente igual à diferença entre o termo independente e os valores à esquerda da desigualdade. III – A solução de um sistema indeterminado é obtida atribuindo‑se valor zero para (n‑m) incógnitas sendo m o número de equações e n o de incógnitas, em sucessivas tentativas de obter a solução ótima. IV – No Simplex, a primeira solução básica é obtida igualando a zero todas as variáveis de entrada. São corretas as afirmativas: A) I, II e III. B) I, II e IV. C) I, III e IV. D) II, III e IV. E) Todas são corretas. Resposta correta: alternativa A. Análise da alternativa Justificativa: no Simplex, a primeira solução básica é obtida igualando a zero não somente as variáveis de entrada, mas, sim, a quantidade de variáveis decorrentes da subtração do número de incógnitas pelo número de equações. 77 REFERêNCiAS BiBliogRáFiCAS Audiovisuais GÊNIO indomável. Dir. Gus Van Sant. USA: Miramax Films, 1997. 126 minutos. NÁUFRAGO. Dir. Robert Zemeckis. USA: Twentieth Century Fox Film Corporation, 2000. 143 minutos. O RESGATE do soldado Ryan. Dir. Steven Spielberg. USA: DreamWorks SKG, 1998. 169 minutos. Textuais ANDRADE, E. L. Introdução à pesquisa operacional: métodos e modelos para análise de decisões. São Paulo: LTC, 2009. BARBOSA, M. A.; ZANARDINI, R. A. D. Iniciação à pesquisa operacional no ambiente de gestão. Curitiba: IBPEX, 2010. BRONSON, R. Pesquisa operacional e estatística. São Paulo: McGraw‑Hill, 1995. CONTADOR, J. C. Alguns modelos da pesquisa operacional. São Paulo: UNIP, 1998. CORRAR, L. J.; THEÓPHILO, C. R. Pesquisa operacional para decisão em contabilidade e administração. São Paulo: Atlas, 2011. EHRLICH, P. J. Pesquisa operacional: curso introdutório. 7. ed. São Paulo: Atlas, 1991. HILLIER, F. S.; LIEBERMAN, G. J. Introdução à pesquisa operacional. Porto Alegre: AMGB, 2013. LACHTERMACHER, G. Pesquisa operacional na tomada de decisões. São Paulo: Pearson Prentice Hall, 2009. MENDES, H. Modelagem e formas de representação de problemas. 2013. Disponível em: <http://prezi. com/71sowsklb6gp/modelagem‑e‑formas‑de‑representacao‑de‑problemas/>. Acesso em: 2 abr. 2013. SILVA, E. M. et al. Pesquisa operacional para os cursos de administração e engenharia. 4. ed. São Paulo: Atlas, 2010. SOCIEDADE BRASILEIRA DE PESQUISA OPERACIONAL. Pesquisa operacional. 2010. Disponível em: <http://www.sobrapo.org.br/o_que_e_po.php>. Acesso em: 2 abr. 2013. TAHA, H. A. Pesquisa operacional. 8. ed. São Paulo: Pearson Prentice Hall, 2008. 78 79 80 Informações: www.sepi.unip.br ou 0800 010 9000
Compartilhar