Apostila Po

APOSTILA DO CURSO

PESQUISA OPERACIONAL

Organizador Professor Marcelo do Vale Neto

2

CAPÍTULO 1 INTRODUÇÃO À PESQUISA OPERACIONAL

1.1 O Desenvolvimento da Pesquisa Operacional O nome “Pesquisa Operacional” apareceu pela primeira vez durante a Segunda Grande Guerra Mundial, quando equipes de pesquisadores ingleses procuraram desenvolver métodos para resolver determinados problemas de operações militares. Devido ao sucesso dessas operações, o mundo acadêmico e empresarial procurou utilizar as técnicas criadas em problemas de administração. Os resultados positivos conseguidos pela equipe de pesquisa operacional inglesa motivaram os Estados Unidos a iniciarem atividades semelhantes. Apesar de ser creditada à Inglaterra a origem da Pesquisa Operacional, sua propagação deve-se principalmente à equipe de cientistas liderada por George B. Dantzig, dos Estados Unidos, convocada durante a Segunda Guerra Mundial. Ao resultado deste esforço de pesquisa, concluído em 1947, deu-se o nome de Método Simplex. Com o fim da guerra, a utilização de técnicas de pesquisa operacional atraiu o interesse de diversas outras áreas. A natureza dos problemas encontrados é bastante abrangente e complexa, exigindo portanto uma abordagem que permita reconhecer os múltiplos aspectos envolvidos. Uma característica importante da pesquisa operacional e que facilita o processo de análise e de decisão é a utilização de modelos. Eles permitem a experimentação da solução proposta. Isto significa que uma decisão pode ser mais bem avaliada e testada antes de ser efetivamente implementada. A economia obtida e a experiência adquirida pela experimentação justificam a utilização da Pesquisa Operacional. Com o aumento da velocidade de processamento e quantidade de memória dos computadores atuais, houve um grande progresso na Pesquisa Operacional. Este progresso é devido também à larga utilização de microcomputadores, que se tornaram unidades isoladas dentro de empresas. Isso faz com que os modelos desenvolvido pelos profissionais de Pesquisa Operacional sejam mais rápidos e versáteis, além de serem também interativos, possibilitando a participação do usuário ao longo do processo de cálculo. A Pesquisa operacional é um ramo da ciência administrativa que fornece instrumentos para a análise de decisões. Assim sendo, uma DECISÃO é o resultado de um processo que se desenvolve a partir do instante em que o problema foi detectado, o que se percebe através da percepção de sintomas. Então, o processo de decisão empresarial se inicia quando uma pessoa ou grupo percebe sintomas de que alguma coisa está saindo do estado normal ou planejado. 1.1.1 Característica da pesquisa operacional Característica multidisciplinar das suas aplicações; Técnicas e métodos qualitativos por equipes interdisciplinares; Procura determinar uma melhor utilização de recursos e otimizar as operações empresariais. Um novo enfoque sistêmico aos problemas de decisão das empresas (ou seja), ultrapassa as fronteiras das especialidades, assim, um profissional especialista precisa evitar uma tendência natural de enquadrar todos os problemas dentro dos limites de sua cultura, mas sim, por outro lado, este profissional necessita de uma abordagem mais complexa e abrangente, porque a natureza e o ambiente dos negócios exigem além do raciocínio do especialista, uma visão mais aberta que reconheça os múltiplos aspectos envolvidos nos problemas da análise de decisão. Utilização de “modelos” que permitem a “experimentação” ou seja, uma decisão pode ser bem mais avaliada e testada antes de ser efetivamente implementada. Vale-se identificar que, o imenso progresso da Pesquisa Operacional se deve também, ao desenvolvimento dos computadores digitais, devido à sua velocidade de processamento e capacidade de armazenamento e recuperação das informações. 1) o processo de decisão é seqüencial;

3

2) é um processo complexo; 3) é um processo que envolve valores subjetivos. 4) é um processo desenvolvido dentro de um ambiente institucional com regras mais ou menos definidas. 1.1.2 Classificação das Decisões De uma maneira geral as Decisões são classificadas em relação ao nível em que ocorrem dentro da empresa e pelo grau de complexidade apresentado. Apresenta-se abaixo dois critérios: 1) NÍVEL ESTRATÉGICO : Nível estratégico de uma decisão refere-se à sua importância e abrangência com relação à organização. 2) GRAU DE ESTRUTURAÇÃO: grau de estruturação refere-se à possibilidade de uma decisão ser acompanhada em seu processo de preparação e de conclusão, ou mesmo de ser reproduzida, por outras pessoas, em outras ocasiões, com os mesmos resultados. 1.2 Modelagem Um modelo é uma representação de um sistema real, que pode já existir ou ser um projeto aguardando execução. No primeiro caso, o modelo pretende reproduzir o funcionamento do sistema, de modo a aumentar sua produtividade. No segundo caso, o modelo é utilizado para definir a estrutura ideal do sistema. A confiabilidade da solução obtida através do modelo depende da validação do modelo na representação do sistema real. A validação do modelo é a confirmação de que ele realmente representa o sistema real. A diferença entre a solução real e a solução proposta pelo modelo depende diretamente da precisão do modelo em descrever o comportamento original do sistema. Um problema simples pode ser representado por modelos também simples e de fácil solução. Já problemas mais complexos requerem modelos mais elaborados, cuja solução pode vir a ser bastante complicada. 1.3 Estrutura de Modelos Matemáticos Em um modelo matemático, são incluídos três conjuntos principais de elementos: (1) variáveis de decisão e parâmetros: variáveis de decisão são as incógnitas a serem determinadas pela solução do modelo. Parâmetros são valores fixos no problema; (2) restrições: de modo a levar em conta as limitações físicas do sistema, o modelo deve incluir restrições que limitam as variáveis de decisão a seus valores possíveis (ou viáveis); (3) função objetivo: é uma função matemática que define a qualidade da solução em função das variáveis de decisão. Para melhor ilustrar ao conjuntos acima, considere o seguinte exemplo: 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. Neste problema as variáveis de decisão são as quantidades de ração de cada tipo a serem produzidas. Os parâmetros fornecidos são os preços unitários de compra e de venda, além das quantidades de carne e cereais utilizadas em cada tipo de ração. As restrições são os limites de carnes e cereais e a função objetivo é uma função matemática que determine o lucro em função das variáveis de decisão e que deve ser maximizada.

4

1.4 Técnicas Matemáticas em Pesquisa Operacional A formulação do modelo depende diretamente do sistema a ser representado. A função objetivo e as funções de restrições podem ser lineares ou não- lineares. As variáveis de decisão podem ser contínuas ou discretas (por exemplo, inteiras) e os parâmetros podem ser determinísticos ou probabilísticos. O resultado dessa diversidade de representações de sistemas é o desenvolvimento de diversas técnicas de otimização, de modo a resolver cada tipo de modelo existente. Estas técnicas incluem, principalmente: programação linear, programação inteira, programação dinâmica, programação estocástica e programação não- linear. Programação linear é utilizada para analisar modelos onde às restrições e a função objetivo são lineares; programação inteira se aplica a modelos que possuem variáveis inteiras (ou discretas); programação dinâmica é utilizada em modelos onde o problema completo pode ser decomposto em subproblemas menores; programação

estocástica é aplicada a uma classe especial de modelos onde os parâmetros são descritos por funções de probabilidade; finalmente, programação não-linear é utilizada em modelos contendo funções não- lineares. Uma característica presente em quase todas as técnicas de programação matemática é que a solução ótima do problema não pode ser obtida em um único passo, devendo ser obtida iterativamente. É escolhida uma solução inicial (que geralmente não é a solução ótima). Um algoritmo é especificado para determinar, a partir desta, uma nova solução, que geralmente é superior à anterior. Este passo é repetido até que a solução ótima seja alcançada (supondo que ela existe). 1.5 Fases do Estudo de Pesquisa Operacional Um estudo de pesquisa operacional geralmente envolve as seguintes fases: (1) definição do problema; (2) construção do modelo; (3) solução do modelo; (4) validação do modelo; (5) implementação da solução. Apesar da seqüência acima não ser rígida, ela indica as principais etapas a serem vencidas. A seguir, é apresentado um resumo da cada uma das fases. 1.5.1 Definição do problema A definição do problema baseia-se em três aspectos principais: � descrição exata dos objetivos do estudo; � identificação das alternativas de decisão existentes; � reconhecimento das limitações, restrições e exigências do sistema. A descrição dos objetivos é uma das atividades mais importantes em todo o processo do estudo, pois a partir dela é que o modelo é concebido. Da mesma forma, é essencial que as alternativas de decisão e as limitações existentes sejam todas explicitadas, para que as soluções obtidas ao final do processo sejam válidas e aceitáveis. 1.5.2 Construção do modelo A escolha apropriada do modelo é fundamental para a qualidade da solução fornecida. Se o modelo elaborado tem a forma de um modelo conhecido, a solução pode ser obtida através de métodos matemáticos convencionais. Por outro lado, se as relações matemáticas são muito complexas, talvez se faça necessária à utilização de combinações de metodologias. 1.5.3 Solução do modelo O objetivo desta fase é encontrar uma solução para o modelo proposto. Ao contrário das outras fases, que não possuem regras fixas, a solução do modelo é baseada geralmente em técnicas matemáticas existentes.

5

No caso de um modelo matemático, a solução é obtida pelo algoritmo mais adequado, em termos de rapidez de processamento e precisão da resposta. Isto exige um conhecimento profundo das principais técnicas existentes. A solução obtida, neste caso, é dita "ótima". 1.5.4 Validação do modelo Nessa altura do processo de solução do problema, é necessário verificar a validade do modelo. Um modelo é válido se, levando-se em conta sua inexatidão em representar o sistema, ele for capaz de fornecer uma previsão aceitável do comportamento do sistema. Um método comum para testar a validade do sistema é analisar seu desempenho com dados passados do sistema e verificar se ele consegue reproduzir o comportamento que o sistema apresentou. É importante observar que este processo de validação não se aplica a sistemas inexistentes, ou seja, em projeto. Nesse caso, a validação é feita pela verificação da correspondência entre os resultados obtidos e algum comportamento esperado do novo sistema. 1.5.5 Implementação da solução Avaliadas as vantagens e a validação da solução obtida, esta deve ser convertida em regras operacionais. A implementação, por ser uma atividade que altera uma situação existente, é uma das etapas críticas do estudo. É conveniente que seja controlada pela equipe responsável, pois, eventualmente, os valores da nova solução, quando levados à prática, podem demonstrar a necessidade de correções nas relações funcionais do modelo conjunto dos possíveis cursos de ação, exigindo a reformulação do modelo em algumas de suas partes.

CAPÍTULO 2 ÁLGEBRA LINEAR

Ao longo do curso de pesquisa operacional, conceitos matemáticos como matrizes e vetores são largamente utilizados. Este capítulo tem como objetivo apresentar uma revisão desses fundamentos matemáticos, de modo que o curso possa ser compreendido. 2.1 Vetores Um vetor é um conjunto de números, que pode ser escrito como: p = (p1, p2, ... , pn). O vetor p é um vetor de dimensão n, ou seja, possui n elementos. Vetores são geralmente representadas por letras minúsculas em negrito, e seus elementos são geralmente representados por letras minúsculas com um subscrito. A letra usada para os elementos é normalmente a mesma letra utilizada para o vetor. O subscrito representa o índice do elemento no vetor. Por exemplo, p2 é o segundo elemento do vetor. A notação pi indica o i-ésimo elemento do vetor. 2.1.1 Soma e subtração de vetores Dois vetores podem ser adicionados se e somente se eles tiverem a mesma dimensão. Para somar dois vetores, basta somar individualmente cada elemento deles. O vetor resultante será da mesma dimensão do vetores originais. Simbolicamente, temos que, se r = p + q, então ri = pi + qi, para todo i. Dados os vetores: p = (4, 5, 1, 7) q = (1, -2, 3, -4) r = (1, 5, 4) temos que:

� p + q = (5, 3, 4, 3); � não é possível computar p + r, nem q + r, visto que p e q são de 4ª dimensão e r é de 3ª.

6

Um vetor pode ser multiplicado por um escalar, multiplicando-se cada elemento do vetor por este escalar. Por exemplo,

2 (1, 3, -2) = (2, 6, -4) Subtração entre dois vetores é equivalente a somar o primeiro com o produto do segundo pelo escalar -1. Então s - t = s + (-t). Por exemplo.

(1, 4, 3) - (0, 2, -1) = (1, 4, 3) + (0, -2, 1) = (1, 2, 4) 2.1.2 Vetores LD e LI Um conjunto de vetores p1, p2, ... , pn, é dito linearmente independente (LI) se e somente se, para todo q j real, n

∑θj P j = 0 j=l

implica que todo θ j = 0, onde θ j são quantidades escalares. Se para algum θ j ≠ 0, os vetores são ditos linearmente dependentes (LD). Por exemplo, os vetores,

p1 = (1, 2) p2 = (2, 4) são linearmente dependentes, já que existe θ 1 = 2 e θ 2 = -1 para os quais

θ 1 p1 + θ 2 p2 = 0. 2.2 Matrizes Uma matriz é um conjunto retangular de números que pode ser escrito como vemos abaixo.

A matriz A é uma matriz de ordem m x n, ou seja, possui m linha e n colunas. Matrizes são geralmente representadas por letras maiúsculas em negrito, e seus elementos são geralmente representados por letras minúsculas com dois subscritos. A letra usada para os elementos é normalmente a mesma letra utilizada para a matriz. Os subscritos representam respectivamente a linha e a coluna ocupadas pelo elemento na matriz. Por exemplo, a23 é o elemento localizado na segunda linha e na terceira coluna da matriz. A notação aij indica o elemento localizado na i-ésima linha e na j-ésima coluna da matriz. Duas matrizes A e B são iguais se aij = bij para qualquer i e j. Para isso, é necessário que as matrizes A e B sejam de mesma ordem, ou seja, tenham o mesmo número de linhas e o mesmo número de colunas. 2.2.1 Soma e subtração de matrizes Duas matrizes podem ser adicionadas se e somente se elas forem da mesma ordem. Para somar duas matrizes, basta somar individualmente cada elemento delas. A matriz resultante será da mesma ordem das matrizes originais. Simbolicamente, temos que, se C = A + B, então cij = aij + bij, para todo i e j. Dadas as matrizes

7

temos que: � as matrizes A e C são iguais;

� não é possível computar A + D, nem B + D, visto que A e B são 3 x 4 e D é 3 x 3. Uma matriz pode ser multiplicada por um escalar, multiplicando-se cada elemento da matriz por este escalar. Por exemplo,

Subtração entre duas matrizes é equivalente a somar a primeira com o produto da segunda pelo escalar -1. Então E - F = E + (-F). Por exemplo.

2.2.2 Produto de matrizes O produto de duas matrizes somente pode ser efetuado se o número de colunas da matriz à esquerda for igual ao número de linhas da matriz à direita. O produto de matrizes é, em geral, não comutativo, ou seja, dadas duas matrizes A e B e seu produto, AB, o produto BA pode não existir e, se existe, pode não ser igual à AB. O produto de duas matrizes tem o número de linhas da matriz à esquerda e o número de colunas da matriz à direita. Ou seja, sendo C = AB, se A é m x n e B é n x p, C é m x p. Os elementos da matriz resultante são calculados através do somatório dos produtos de elementos das duas matrizes. Especificamente, cij é calculado por ai1 b1j + ai2 b2j + ... + ain bnj, onde n é o número de colunas de A e de linhas de B. Exemplos:

8

Note que no primeiro exemplo existe apenas o produto AB, não sendo possível efetuar o produto BA. No segundo exemplo, apesar de ser possível efetuar os dois produtos, as matrizes resultantes não são iguais, não sendo sequer do mesmo tipo. 2.2.3 Matrizes especiais Matriz quadrada Uma matriz quadrada tem o mesmo número de linhas e de colunas. A ordem de uma matriz quadrada é o seu número de linhas (ou de colunas). Exemplos: matrizes 2 x 2 (2ª ordem), 3 x 3 (3ª ordem), n x n (n-ésima ordem). Matriz nula Uma matriz nula possui zeros em todos os seus elementos.

A matriz nula é equivalente ao zero para adição em álgebra escalar, ou seja, se B é uma matriz nula de mesmo tipo de A, então A + B = B + A = A. Matriz identidade Uma matriz identidade, denotada por I, é uma matriz quadrada onde sua diagonal principal é composta de 1's e todos os outros elementos são zero.

9

A matriz identidade é equivalente ao um para produto em álgebra escalar, ou seja, AI = A. Matriz transposta A transposta de uma matriz é a matriz obtida pela troca das linhas pelas colunas da matriz original, de modo que a coluna j da matriz original passe a ser a linha j da matriz transposta e a linha i da matriz original passe a ser a coluna i da matriz transposta. A transposta de uma matriz A é indicada pela notação AT ou A'.

A transposta de uma matriz m x n será sempre uma matriz n x m. Matriz simétrica Uma matriz é dita simétrica se ela for igual à sua transposta. Ou seja, uma matriz A, simétrica, é necessariamente quadrada e aij = aji.

Matriz anti-simétrica Uma matriz é dita anti-simétrica se ela for simétrica à sua transposta, isto é, A = - AT. Ou seja, uma matriz A, simétrica, é necessariamente quadrada e aij = - aji. Os elementos da diagonal principal de uma matriz antisimétrica são necessariamente nulos.

2.2.4 A inversa de uma matriz A operação de divisão não é definida em álgebra matricial. Entretanto, para certas matrizes quadradas existe outra (única) matriz quadrada de mesma ordem que o produto das duas matrizes é a matriz identidade. Esta matriz é chamada de matriz inversa da primeira matriz. A inversa de uma matriz é designada pelo expoente -1.

10

2.3 Sistemas de Equações Lineares Tanto as linhas quanto as colunas de uma matriz podem ser tratadas por vetores. Um vetor pode ser considerado uma matriz de uma única linha, ou uma única coluna. Quando um vetor é considerado uma matriz com uma única linha, é chamado vetor linha. Quando é uma matriz de uma única coluna, é chamado de vetor coluna. Um vetor coluna será representado da mesma forma que um vetor convencional, ou seja, uma letra minúscula em negrito (p, q, r). Quando for o caso de um vetor linha, ele será representado como um vetor transposto (pT, qT, rT). Suponha o seguinte sistema de equações lineares:

2 x1 - x2 = 7 - x1 + 4 x2 = 0

Este sistema pode ser representado na forma matricial por

O vetor coluna x é o vetor solução do sistema de equações e pode ser calculado por

x = A-1 b.

Para a solução de um sistema de equações lineares, são propostos alguns métodos. 2.3.1 Método algébrico por adição Pelo menos uma das equações deve ser multiplicada por um escalar real, de modo que, após a soma das equações, apenas uma das variáveis seja efetivamente a incógnita do problema. Por exemplo,

4 x1 + 8 x2 = 160 6 x1 + 4 x2 = 120

Multiplicando a segunda equação por (-2), temos 4 x1 + 8 x2 = 160

-12 x1 - 8 x2 = -240 Somando as duas equações, chega-se a:

4 x1 + 8 x2 = 160 -12 x1 - 8 x2 = -240

-------------------------------- -8 x1 + 0 x2 = -80

-8 x1 = -80 Daí calcula-se facilmente o valor de x1 e, substituindo este valor em qualquer uma das equações acima, calcula-se o valor de x2.

-8 x1 = -80 x1 = -80

--- = > x1 = 10 -8

11

4 x1 + 8 x2 = 160

4 (10) + 8 x2 = 160 8 x2 =160 – 40

120 x2 = -------- => x2 = 15

8 2.3.2 Método algébrico por substituição Isola-se uma das variáveis em uma das equações, substituindo-se a relação obtida na outra equação. Por exemplo,

4 x1 + 8 x2 = 160 6 x1 + 4 x2 = 120

Manipulando a primeira equação, temos que:

Substituindo x1 na segunda equação,

6 (40 - 2 x2) + 4 x2 = 120 Resolvendo a equação algebricamente, e aplicando o valor de x2 encontrado na primeira equação,

240 - 12 x2 + 4 x2 = 120 -8 x2 = -120

x2 = 15 x1 = 10

CAPÍTULO 3

PROGRAMAÇÃO LINEAR 3.1 Definição O problema geral de programação linear é utilizado para otimizar (maximizar ou minimizar) uma função linear de variáveis, chamada de "função objetivo", sujeita a uma série de equações ou inequações lineares, chamadas restrições. A formulação do problema a ser resolvido por programação linear segue alguns passos básicos.

� deve ser definido o objetivo básico do problema, ou seja, a otimização a ser alcançada. Por exemplo, maximização de lucros, ou de desempenhos, ou de bem-estar social; minimização de custos, de perdas, de tempo. Tal objetivo será representado por uma função objetivo, a ser maximizada ou minimizada;

� para que esta função objetivo seja matematicamente especificada, devem ser definidas as variáveis de decisão envolvidas. Por exemplo, número de máquinas, a área a ser explorada, as classes de investimento à disposição etc. Normalmente, assume-se que todas estas variáveis possam assumir somente valores positivos;

� estas variáveis normalmente estão sujeitas a uma série de restrições, normalmente representadas por inequações. Por exemplo, quantidade de equipamento disponível, tamanho da área a ser explorada, capacidade de um reservatório, exigências nutricionais para determinada dieta etc. Todas essas expressões, entretanto, devem estar de acordo com a hipótese principal da programação linear, ou seja, todas as relações entre as variáveis deve ser lineares. Isto implica proporcionalidade das quantidades envolvidas. Esta característica de linearidade pode ser interessante no tocante à simplificação da estrutura matemática envolvida, mas prejudicial na representação de fenômenos não lineares (por exemplo, funções de custo tipicamente quadráticas).

12

3.2 Formulação de Modelos O problema geral de programação linear pode ser definido por Maximizar (ou minimizar)

sujeito a

3.2.1 Variação do Modelo Geral a) A função objetivo pode ser de minimização: (MIN) Z = c1x1 + c2x2+ . . .+cnxn

b) Algumas restrições podem ser do tipo ≥: ai1x1 + ai2x2+ . . .+ainxn ≥ bi

c) Algumas restrições podem ter sinal =: ai1x1 + ai2x2+. . .+ainxn = bi

d) Algumas variáveis de decisão podem assumir qualquer valor, entre -∞ e +∞, e são chamadas de irrestritas em sinal. 3.2.2 Conceitos implícitos nos modelos a) Proporcionalidade Esta consideração implica em que o nível da contribuição de uma variável qualquer é sempre proporcional ao seu valor. Para exemplificar vejamos no nosso exemplo o caso da variável x1. O seu lucro unitário é igual a 20. Esta propriedade diz que a contribuição de x1 para o lucro total é 20x1 independentemente se x1 é igual a 10 ou igual a 100.000.000. Em um esquema produtivo este fato nem sempre é verdade pois existe, quase sempre, um fator de economia de escala. Os modelos de programação linear não levam isto em conta e ou se usa, se for o caso, uma aproximação ou se tem que usar programação não linear. Normalmente, a solução de modelos de programação não linear é muito mais complexa. b) Aditividade Esta consideração implica em que não há interação entre as diversas variáveis do modelo, ou seja, a contribuição do total de variáveis é a soma das contribuições individuais de cada uma das variáveis. Para exemplificar vamos considerar o nosso exemplo protótipo. A contribuição para o lucro total da variável x1 é 20x1 independentemente se x2 é igual a 1 ou 10.000. Por sua vez a contribuição de x2 para o lucro total é 60x2 seja qual for o valor assumido por x1. No mundo real isto, normalmente, também não acontece assim, ou seja, a quantidade de um produto pode infiuir na produção de outro independentemente das restrições tecnológicas.

13

Se em um modelo a consideração da aditividade modifica a essência do problema, deve-se usar programação não linear. c) Divisibilidade A partir da construção de um modelo de P.Linear nós transformamos um problema do mundo real para o “mundo matemático”. Para encontrarmos a solução que procuramos, temos que resolver o problema matematicamente. A solução gráfica, por exemplo, é um procedimento matemático. Assim sendo, é perfeitamente normal que a solução de um modelo de P.Linear dê, como solução ótima, valores fracionários. Assim sendo poderia ter acontecido que a resposta para o nosso exemplo fosse x*1 = 17,96 e x*2 = 14,88. Mas x1 e x2 representam unidades de produtos. Como fabricar “pedaços” de produtos? Será que a solução seria cortar a parte fracionária? Isto poderia nos tirar do ótimo pois nem sempre o ótimo inteiro é o ótimo fracionário com a parte fracionária cortada. Como se resolve na prática este tipo de problema? Se as variáveis de decisão representam bens cujo valor de mercado é reduzido (uma mesa, por exemplo) trabalhamos com programação linear e simplesmente cortamos a parte fracionária dos valores ótimos. Se no entanto as variáveis representam bens de alto valor (um avião, por exemplo), temos que trabalhar com Programação Linear Inteira acrescentando as restrições de que as variáveis tem de ser inteiras. Porque, para este tipo de modelo, não trabalhar sempre com P.Linear inteira ? Porque o processo de obtenção da solução ótima é muito mais lento que a P.Linear simples. d) Certeza Esta consideração implica em que todos parâmetros do sistema são constantes conhecidas não se aceitando nenhuma incerteza de qualquer tipo. Se alguns dos parâmetros tem qualquer nível de incerteza a formulação como um modelo de P.Linear poderá levar a resultados incorretos. 3.3 Exemplo Vamos reescrever aqui o exemplo da seção 1.3. 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.

Tabela 3.1 - Cálculo do lucro unitário de cada ração

A função objetivo pode ser escrita como maximizar Z = 11 x1 + 12 x2

sujeito a:

14

1 x1 + 4 x2 ≤ 10000 (restrição de carne) 5 x1 + 2 x2 ≤ 30000 (restrição de cereais)

x1, x2 ≥ 0 (positividade das variáveis) Roteiro para definição do modelo a) Quais as variáveis de decisão? Aqui o trabalho consiste em explicar as decisões que devem ser tomadas e representar as possíveis decisões através de variáveis chamadas variáveis de decisão. Se o problema é de programação de produção, as variáveis de decisão são as quantidades de a produzir no período; se for um problema de programação de investimento, as variáveis vão representar aa decisões de investimento, isto é, quanto investir em cada oportunidade de investimento, e em que período. Nas descrições sumárias de sistemas, isso fica claro quando lemos a questão proposta, isto é, a pergunta do problema. b) Qual o objetivo? Aqui devemos identificar o objetivo da tomada decisão. Eles aparecem geralmente na forma da maximização de lucros ou receitas, minimização de custos, perdas etc.

A função objetivo é a expressão que calcula o valor do objetivo (lucro, custo, receita, perdas etc.), em função das variáveis de decisão. c) Quais as restrições?

Cada restrição imposta na descrição do sistema deve ser expressa como uma relação linear (igualdade ou desigualdade), montadas com as variáveis de decisão. EXEMPLOS RESOLVIDOS: Exemplo 01: Certa empresa fabrica dois produtos P1 e P2. O lucro unitário do produto P1 é de R$ 1.000,00 e o lucro unitário de P2 é R$ 1.800,00. A empresa precisa de 20 horas para fabricar uma unidade de P1 e de 30 horas para fabricar uma unidade de P2. O tempo anual de produção disponível para isso é de 1.200 horas. A demanda esperada para cada produto é de 40 unidades anuais para P1 e 30 unidades anuais para P2. Qual é o plano de produção para que a empresa maximize seu lucro nesses itens? Construa o modelo de programação linear para esse caso. SOLUÇÃO:

a) Quais as variáveis de decisão? O que deve ser decidido é o plano de produção, isto é, quais as quantidades anuais que devem ser produzidas de P1 e P2. Portanto, as variáveis de decisão serão x1 e x2. Sendo x1 => quantidade anual a produzir de P1 e x2 => quantidade a produzir de P2.

b) Qual o objetivo? O objetivo é maximizar o lucro, que pode ser calculado: Lucro devido a P1: 1000 . x1 (lucro por unidade de P1 x quantidade produzida de P1) Lucro devido a P2: 1800 . x2 (lucro por unidade de P2 x quantidade produzida de P2) Lucro Total: L = 1000x1 + 1800x2

c) Quais as restrições? As restrições impostas pelo sistema são:

• Disponibilidade de horas para a produção: 1200 horas. horas ocupadas com P1: 20x1 (uso por unidade x quantidade produzida) horas ocupadas com P2: 30x2 (uso por unidade x quantidade produzida) Total em horas ocupadas na produção: 20x1 + 30x2

15

Disponibilidade: 1200 horas. Restrição descritiva da situação: 20x1 + 30x2 ≤ 1200

• Disponibilidade de mercado para os produtos (demanda) Disponibilidade para P1: 40 unidades Quantidade a produzir de P1: x1 Restrição descritiva da situação: x1 ≤ 40 Disponibilidade para P2: 30 unidades Quantidade a produzir de P2: x2 Restrição descritiva da situação: x2 ≤ 30

Resumo do modelo: max L = 1000 x1 + 1800 x2 Sujeito a: 20 x1 + 30 x2 ≤ 1200 x1 ≤ 40 restrições técnicas x2 ≤ 30 x1, x2 ≥0

Exemplo 02: Para uma boa alimentação, o corpo necessita de vitaminas e proteínas. A necessidade mínima de vitaminas é de 32 unidades por dia e a de proteínas de 36 unidades por dia. Uma pessoa tem disponível carne e ovos para se alimentar. Cada unidade de carne contém 4 unidades de vitaminas e 6 de proteínas. Cada unidade de ovo contém 8 unidades de vitaminas e 6 unidades de proteínas. Qual a quantidade de carne e ovos que deve ser consumida para suprir as necessidades de vitaminas e proteínas com o menor custo possível? Cada unidade de carne custa R$ 3,00 e cada unidade de ovo custa R$ 2,50. SOLUÇÃO:

a) Quais as variáveis de decisão? Devemos decidir quais as quantidades de carne e ovos a pessoa deve consumir no dia. As variáveis de decisão serão, portanto:

x1 e x2. Sendo x1 => quantidade de carne a consumir no dia e x2 => quantidade de ovos a consumir no dia. b) Qual o Objetivo?

O objetivo é minimizar o custo, que pode ser calculado: Custo devido à carne: 3 . x1 (custo por unidade x quantidade a consumir de carne) Custo devido à carne: 2,5 . x2 (custo por unidade x quantidade a consumir de ovos) Custo Total: C = 3 . x1 + 2,5 . x2 � Objetivo: minimizar C = 3 . x1 + 2,5 . x2

c) Quais as restrições? As restrições impostas pelo sistema são:

• Necessidade mínima de vitamina: 32 unidades Vitamina de carne: 4 . x1 (quantidade por unidade x unidades de carne a consumir) Vitamina de ovos: 8 . x2 (quantidade por unidade x unidades de ovos a consumir) Total de vitaminas: 4x1 + 8x2 Necessidade mínima: 32 �� Restrições descrita da situação: 4x1 + 8x2 ≥ 32

• Necessidade mínima de proteínas: 36 unidades Proteína de carne: 6 . x1 (quantidade por unidade x unidades de carne a consumir) Proteínas de ovos: 6 . x2 (quantidade por unidade x unidades de ovos a consumir) Total de vitaminas: 6x1 + 6x2

• Necessidade mínima: 36 �� Restrições descrita da situação: 6x1 + 6x2 ≥ 36 Resumo do modelo: min C = 3 . x1 + 2,5 . x2

16

Sujeito a: restrições técnicas 4x1 + 8x2 ≥ 32 6x1 + 6x2 ≥ 36 x1, x2 ≥0

Vamos a outro modelo: Uma empresa produz 2 produtos em uma de suas fábricas. Na fabricação dos 2 produtos, 3 insumos são críticos em termos de restringir o número de unidades dos 2 produtos que podem ser produzidas: as quantidades de matéria prima (tipos A e B) disponíveis e a mão de obra disponível para a produção dos 2 produtos. Assim, o Departamento de Produção já sabe que, para o próximo mês, a fábrica terá disponível, para a fabricação dos 2 produtos, 4900 kilos da matéria prima A e 4500 kilos da matéria prima B. Cada unidade do produto tipo I, para ser produzida consome 70 kilos da matéria prima A e 90 kilos da matéria prima B. Por sua vez, cada unidade do produto tipo II para ser produzida, utiliza 70 kilos da matéria prima tipo A e 50 kilos da matéria prima tipo B. Como a produção dos 2 produtos utiliza processos diferentes, a mão de obra é especializada e diferente para cada tipo de produto, ou seja não se pode utilizar a mão de obra disponível para a fabricação de um dos produtos para produzir o outro. Assim, para a produção do produto tipo I a empresa terá disponível, no próximo mês, 80 homens-hora. Já para o produto tipo II terá 180 homens-hora. Cada unidade do produto tipo I, para ser produzida, utiliza 2 homens-hora enquanto que cada unidade do produto tipo II utiliza 3 homens-hora. Reduzindo do preço unitário de venda todos os custos, chega-se a conclusão de que cada unidade do produto tipo I dá um lucro de $20 e cada unidade do produto tipo II dá um lucro de $60. Dada a grande procura, estima-se que todas as unidades a serem produzidas, dos 2 produtos, poderão ser vendidas. O objetivo da empresa é obter o maior lucro possível com a produção e a venda das unidades dos produtos tipo I e II. Antes de qualquer coisa vamos conhecer o problema. Qual é o problema desta empresa ? O problema é que eles não sabem quantas unidades de cada tipo de produto (I e II) devem ser produzidas, de maneira que o lucro seja o maior possível. Para construir um modelo de P.Linear temos que começar identificando o que se deseja saber ou conhecer no problema. A isto dá-se o nome de variável de decisão. No nosso problema temos 2 variáveis de decisão que são: x1 )no de unidades do produto tipo I a serem produzidas no próximo mês. x2 )no de unidades do produto tipo II a serem produzidas no próximo mês 1. Temos que identificar o objetivo que se deseja alcançar e traduzí-lo por uma função matemática linear contendo as variáveis de decisão. Assim, no nosso exemplo, o objetivo é maximizar o lucro total obtido com a produção dos 2 produtos. Cada unidade, a ser produzida, do produto tipo I dá um lucro de $20. Como vamos produzir x1 unidades, teremos um lucro de 20x1. Da mesma forma, cada unidade do produto tipo II dá um lucro de $60, ou seja, pelo produto tipo II teremos um lucro de 60x2. Desta forma a função de lucro total, que queremos maximizar, será uma função da forma: 20x1 + 60x2. Esta função é chamada de função objetivo e é representada, pela maioria dos autores, como uma função de uma variável Z representando o sentido da otimização que, no nosso caso, é de maximização. Assim, podemos escrever: (MAX)Z = 20x1 + 60x2 )função objetivo. 1Chamamos de x1 e x2 mas poderíamos usar qualquer nome para rotular as variáveis de decisão Evidentemente que o nosso modelo não se restringe a função objetivo pois se assim fosse, a solução seria simplesmente x1 = x2 = 1 , o que, sem muita análise, percebemos que é impossível bastando observar a quantidade disponível de qualquer uma das matérias primas. Desta forma os valores que x1 e x2 podem assumir estão condicionados pelas restrições do modelo que, no nosso exemplo, são as as quantidades das 2 matérias

17

primas e a quantidade de mão de obra disponível. Temos que representar cada restrição física por uma função matemática linear contendo as variáveis de decisão do modelo. A 1a restrição que temos diz que a quantidade disponível de matéria prima tipo A, no próximo mês é de 4900 kilos. Cada unidade a ser produzida do produto I vai consumir 70 kilos desta matéria prima. Por sua vez, cada unidade a ser produzida do produto II também vai consumir 70 kilos desta mesma matéria prima. Logo 70x1 + 70x2 vai nos dar toda a matéria prima tipo A a ser utilizada. Esta quantidade não pode ser maior do que a empresa vai ter disponível, ou seja 4900 kilos. Podemos escrever então: 70x1 + 70x2 fi 4900 Fazendo-se o mesmo tipo de raciocínio para a matéria prima tipo B, podemos escrever: 90x1 + 50x2 fi 4500. Temos ainda que representar a restrição relativa a mão de obra. Para a produção do produto tipo I, temos 80 homens-hora disponíveis. Cada unidade, para ser produzida, utiliza 2 homens-hora. Logo, 2x1 indica todo o consumo de mão de obra, apta para produzir o produto I, no próximo mês. Como temos disponíveis 80 homens-hora, a restrição fica: 2x1 fi 80. Podemos escrever uma restrição semelhante para o produto tipo II, ou seja: 3x2 ≤ 180. A primeira vista poderá parecer que formulamos todas as restrições. No entanto, há um tipo de restrição não tão evidente. Como visto anteriormente, x1 e x2 representam as unidades dos 2 tipos de produto a serem fabricadas. Ora não podemos produzir, por exemplo, .10 unidades do produto tipo I ou do produto tipo II, ou seja, x1 e x2 não podem ser negativos. Matematicamente temos: x1,x2 ≥ 0. Podemos agora escrever todo o modelo de programação linear para o nosso exemplo: (MAX) Z = 20x1 + 60x2) Função Objetivo s.a 70x1 + 70x2 ≤ 4900 90x1 + 50x2 ≤ 4500 Restrições do modelo 2x1 ≤ 80 3x2 ≤ 180 x1,x2 ≥ 0 Restrição de não negatividade Exercício (Lista 01) Construir o modelo matemático de programação linear dos sistemas descritos a seguir: 01) Um sapateiro faz 6 sapatos por hora, se fizer somente sapatos, e 5 cintos por hora, se fizer somente cintos. Ele gasta 2 unidades de couro para fabricar 1 unidade de sapato e 1 unidade couro para fabricar uma unidade de cinto. Sabendo-se que o total disponível de couro é de 6 unidades e que o lucro unitário por sapato é de 5 unidade monetárias e o do cinto é de 2 unidades monetárias, pede-se: o modelo do sistema de produção do sapateiro, se o objetivo é maximizar seu lucro por hora. 02) Certa empresa fabrica 2 produtos P1 e P2. O lucro por unidade de P1 é de R$ 100 e o lucro unitário de P2 é de R$ 150. A empresa necessita de 2 horas para fabricar uma unidade de P1 e 3 horas para fabricar uma unidade de P2. O tempo mensal disponível para essas atividades é de 120horas. As demandas esperadas para os 2 produtos levaram a empresa a decidir que os montantes produzidos de P1 e P2 não devem ultrapassar 40 unidades de P1 e 30 unidades de P2 por mês. Construa o modelo do sistema de produção mensal como objetivo de maximizar o lucro da empresa. 03) Um vendedor de frutas pode transportar 800 caixas de frutas para sua região de vendas. Ele necessita transportar 200 caixas de laranjas a R$ 20 de lucro por caixa, pelo menos 100 caixas de pêssego a R$ 10 de lucro por caixa, e no máximo 200 caixas de tangerinas a R$ 30 de lucro por caixa. De que forma deverá ele carregar o caminhão para obter o lucro máximo? Construa o modelo do problema.

18

04) Uma rede de televisão local tem o seguinte problema: foi descoberto que o programa “A” com 20 minutos de música e 1 minuto de propaganda chama a atenção de 30.000 telespectadores, enquanto o programa “B” com 10 minutos de música e 1 minuto de propaganda chama a atenção de 10.000 telespectadores. No decorrer de uma semana, o patrocinador insiste no uso de no mínimo, 5 minutos para sua propaganda e que na há verba para mais de 80 minutos de música. Quantas vezes por semana cada programa deve ser levado ao ar para obter o número máximo de telespectadores ? Construa o modelo do sistema. 05) Uma empresa fabrica 2 modelos de cinto de couro. O modelo M1, de melhor qualidade, requer o dobro do tempo de fabricação em relação ao modelo M2. Se todos os cintos fossem do modelo M2, a empresa poderia produzir 1.000 unidades por dia. A disponibilidade de couro permite fabricar 800 cintos de ambos os modelos por dia. Os cintos empregam fivelas diferentes, cuja disponibilidade diária é de 400 para o modelo M1 e 700 para o modelo M2. Os lucros unitários são de R$ 4 para M1 e R$ 3 para M2. Qual o programa ótimo de produção que maximiza o lucro total diário da empresa? Construa o modelo do sistema descrito. 06) Uma empresa, após um processo de racionalização de produção, ficou com disponibilidade de 3 recursos produtivos, R1, R2 e R3. Um estudo sobre o uso destes recursos indicou a possibilidade de se fabricar 2 produtos P1 e P2. Levantando os custos e consultando o departamento de vendas sobre o preço de colocação no mercado, verificou-se que P1 daria um lucro de $ 120,00 por unidade e P2, $ 150,00 por unidade. O departamento de produção forneceu a seguinte tabela de uso de recursos. Que produção mensal de P1 e P2 traz o maior lucro para a empresa ? Construa o modelo do sistema.

Produto Recurso R1 por unidade Recurso R2 por unidade Recurso R3 por unidade

P1 2 3 5 P2 4 2 3

Disponibilidade de recursos no mês 100 90 120

07) Um fazendeiro está estudando a divisão de sua propriedade nas seguintes atividades produtivas: A (Arrendamento) – Destinar certa quantidade de alqueires para a plantação de cana-de-açúcar, a uma usina local, que se encarrega da atividade e paga aluguel da terra $ 300,00 por alqueire por ano. P (Pecuária) – Usar outra parte para a criação de gado de corte. A recuperação das pastagens requer adubação (100 kg/Alq) e irrigação (100.000 litros de água/Alq) por ano. O lucro estimado nessa atividade é de $ 400,00 por alqueire no ano. S (Plantio de Soja) – Usar uma terça parte para o plantio de soja. Essa cultura requer 200 kg por alqueire de adubos e 200.000 litros de água/Alq para irrigação por ano. O lucro estimado nessa atividade é de $ 500,00 / Alqueire no ano. Disponibilidade de recursos por ano:

12.750.000 litros de água 14.000 kg de adubo 100 alqueires de terra.

Quantos alqueires deverá destinar a cada atividade para proporcionar o melhor retorno? Construa o modelo de decisão. 08) Uma rede de depósitos de material de construção tem 4 lojas que devem ser abastecidas com 50 m3 (loja 1), 80 m3 (loja 2), 40 m3 (loja 3) e 100 m3 (loja 4) de areia grossa. Essa areia pode ser carregada em 3 pontos P1, P2 e P3, cujas distâncias estão no quadro (em km):

L1 L2 L3 L4

19

P1 30 20 24 18 P2 12 36 30 24 P3 8 15 25 20

O caminhão pode transportar 10 m3 por viagem. Os pontos têm areia para suprir qualquer demanda. Estabelecer um plano de transporte que minimize a distância total percorrida entre os pontos e as lojas e supra as necessidades das lojas. Construa o modelo linear do problema. 09) Uma liga especial constituída de ferro, carvão, silício e níquel pode ser obtida usando a mistura desses minerais puros além de 2 tipos de materiais recuperados: Material recuperado 1 – MR1 – Composição: Ferro – 60% Custo por Kg: $ 0,20 Carvão – 20% Silício – 20% Material recuperado 2 – MR2 – Composição: Ferro – 70% Custo por Kg: $ 0,25 Carvão – 20% Silício – 5% Níquel – 5% A liga deve ter a seguinte composição final: Matéria - Prima % mínima % máxima ferro 60 65 carvão 15 20 silício 15 20 níquel 5 8 O custo dos materiais puros são (por kg): ferro: $ 0,30; carvão $ 0,20; silício $ 0,28; níquel $ 0,50. Qual deverá ser a composição da mistura em termos dos materiais disponíveis, com menor custo por Kg? Construa o modelo de decisão. 10) Um confeiteiro fabrica dois tipos de bolo: chocolate e baunilha. Cada bolo de chocolate é vendido a R$ 50,00 e cada um de baunilha a R$ 30,00. Cada bolo de chocolate requer 20 minutos para bater, 50 minutos para assar e gasta 4 ovos. Cada bolo de baunilha leva 10 minutos para bater, 50 minutos para assar e gasta 12 ovos. O confeiteiro dispõe de 140 minutos para bater, 400 minutos de forno e de 72 ovos. Ele deseja saber quantos bolos de cada tipo deve produzir para aumentar sua receita. 11) A industria Super Móveis fabrica dois tipos de produtos: cadeira e mesas. Os produtos apresentam as seguintes margens de contribuição por unidade: Produto Margem de Contribuição por unidade (R$) Cadeiras 10 Mesas 8 Os produtos são processados por dois departamentos: montagem e acabamento. Ao passar Poe esses por esses departamentos, cada unidade do produto consome determinado número de horas, conforme indicado abaixo: Departamentos Consumo de horas pelos produtos (em un.)

20

Cadeiras Mesas Montagem 3 3 Acabamento 6 3 Os departamentos apresentam, contudo, limitação em sua capacidade produtiva, sendo 30 horas para Montagem e 48 horas para Acabamento. Qual é a melhor combinação possível de cadeiras e mesas para se obter a maior margem de contribuição total. 12) Na qualidade de assessor de investimento da FUNIPAC, apresente a melhor forma de aplicar os recursos disponíveis conforme apresentado abaixo: Investimento Símbolo Taxa de

retorno (%) Ações da CVRD – Minério COMG 4,3 Ações da Cesp – Energia CESP 3,7 Ações da CFLCL – Energia CFLCL 1,8 Ações da Nestlé – Preferencial NES 2,8 Títulos públicos federais TPF 1,5 Títulos públicos estaduais TPM 2,4 O montante disponível para aplicação está limitado a R$ 100.000,00. De acordo com a legislação atual devemos observar as seguintes situações: a) TPF e TPM não podem representar, juntos, menos de que R$ 30.000,00 dos investimentos; b) Ações preferenciais estão limitadas a R$ 25.000,00 dos investimentos; c) Ações de companhias de utilidades públicas estão estipuladas a no mínimo R$ 30.000,00 d) Os Investimentos em empresas de minério, empresas de utilidade pública e nas ações preferenciais são maiores de R$ 50.000,00. Definir o modelo de decisão que represente a maximização do valor de retorno das ações. 13) A industria Barbieri fabrica os Produtos P1 e P2. esses produtos tem uma ótima relação de vendas o que garante a absorção total do mercado consumidor pelos dois produtos. Cada produto passa por três departamentos e os tempos de fabricação requeridos encontram-se na tabela abaixo: Departamento

A Departamento B

Departamento C

P1 2 1 4 P2 2 2 2 Cada Departamento, entretanto, tem uma capacidade fixa de homens-hora Por mês conforme dados abaixo: Departamento Capacidade máxima em homens-

hora A 160 B 120 C 280 A margem de contribuição do P1 é de R$ 1,00 por unidade e a do P2 é de R$ 1,50 por unidade. Construa o modelo que maximize a margem de contribuição. 14) Um fabricante produz dois tipos de bicicletas, a A e a B, cada uma delas devendo ser processada em duas oficinas. A oficina 1 tem um máximo de 120 horas disponíveis e a oficina 2 tem no máximo 180 horas disponível. A fabricação de uma bicicleta A requer 6 horas na oficina 1 e 3 horas na oficina 2; a fabricação da bicicleta B

21

requer 4 horas na oficina 1 e 10 horas na oficina 2. Se o lucro é de R$ 45,00 para a bicicleta A e de R$ 55,00 para a bicicleta B, determine o modelo para decisão para maximização da produção. 15) Uma companhia produz dois modelos de lanchas de corrida. Seu lucro é R$ 520,00 para o modelo 1 e de R$ 450,00 para o Modelo 2. O Modelo 1 re quer 40 horas para corte e montagem e 24 horas para acabamento. O Modelo 2 requer 25 horas para o corte e montagem, e 30 horas para o acabamento. Dispõe-se de 400 horas para corte e montagem, e 360 horas para o acabamento. Determine o modelo para maximizar lucro. 16) Uma fabrica pode fabricar três tipos de escadas; o lucro é de r$ 3,00 para a escada do tipo A, R$ 7,00 para as do tipo B e de R$ 8,00 para a escada do tipo C. cada uma das escadas deve ser processada através de três seções, de acordo com as seguintes condições: Seção 1 Seção 2 Seção 3 Tipo A 4 5 6 Tipo B 5 7 9 Tipo C 6 7 7 Total disponível 80 100 120 17) Um empresário deseja abrir uma franquia, que enviou a ele um tabela com o número mínimo de funcionários por dia da semana. O empresário deseja definir o número mínimo de funcionários de horário integral que deve contratar para iniciar suas atividades. Há um acordo com o sindicato que determina que cada empregado deva trabalhar cinco dias consecutivos e folgar os dois dias seguintes, e que as franquias devem contratar funcionários apenas para período integral.

Número mínimo de trabalhadores por dia da semana Dia da semana Número de Funcionários

Domingo 7 Segunda-feira 15 Terça-feira 10 Quarta-feira 12 Quinta-feira 16 Sexta-feira 11 Sábado 13 Defina o número mínimo de funcionários para funcionamento da Franquia. 18) A companhia X produz quatro artigos numerados de 1 a 4. As exigências de matéria-prima, espaço para estocagem, taxa de produção, assim sendo o lucro proveniente de cada artigo estão disponíveis na tabela abaixo.

Características da Companhia X Características Artigo 1 Artigo 2 Artigo 3 Artigo 4 Matéria-prima (kg/artigo) 2 2 1,5 4 Espaço (m3/artigo) 2 2,5 2 1,54 Taxa de Produção (artigos/h)

15 30 10 15

Lucro (R$/artigo) 5 6,5 5 5,5 O total de matéria-prima disponível diariamente é de 180 kg. O espaço máximo é de 230 m3 e 7h:30min por dia para a produção. Pede-se minimizar o uso de matéria prima garantindo um lucro mínimo de R$ 400,00.

22

19) Um fabricante de eletrodoméstico possui duas fabricas, uma localizada em Porto Alegre e outra em Refice. Os centros de distribuição ficam em Manaus e Rio de Janeiro. A tabela a seguir contém os custos de transporte unitário, a capacidade de produção de cada fabrica e a demanda dos centros de distribuição:

Dados do Fabricante de Eletrodomésticos

Distribuidor Fábrica

Manaus Rio de Janeiro Capacidade

Porto Alegre 25 15 30.000 Recife 10 13 20.000 Demanda 15.000 35.000 Como modelar esse problema de forma que os custos de transporte sejam minimizados. 20) Uma fabrica produz panelas pequenas e médias. Em sua linha de produção há quatro tipos de matrizes para corte de quatro tipos de chapas de metal. As características das matrizes são exibidas na tabela abaixo. Matriz Número de panelas

pequenas Número de panelas médias

Custo da Chapa de metal usada

1 8 0 2 2 4 1 3 3 2 2 3,5 4 0 3 5

Sabendo-se que a produção diária mínima de panelas pequenas e médias de ser, respectivamente, 600 e 400 panelas, formule um modelo para minimizar o custo de uso das chapas. 3.4 Solução Gráfica Este problema com apenas duas variáveis pode ser resolvido graficamente. Traça-se um gráfico com os seus eixos sendo as duas variáveis x1 e x2. A partir daí, traçam-se às retas referentes às restrições do problema e delimita-se a região viável (Figura 3.1). Encontrada a região viável, deve-se traçar uma reta com a inclinação da função objetivo. São então traçadas diversas paralelas a ela no sentido de Z crescente (maximização da função), como na Figura 3.2. O ponto ótimo é o ponto onde a reta de maior valor possível corta a região viável (normalmente num vértice).

23

EXERCÍCIO RESOLVIDO

SOLUÇÃO GRÁFICA: PROBLEMA DE MAXIMIZAÇÃO De posse do modelo abaixo: Maximizar 4000 x + 5000 y Sujeito a 5x + 10 y < 100 9 x + 6 y < 108 1 y < 8 x > 0 , y > 0 a solução gráfica exige que tomemos dois eixos ortogonais, cada um dos quais irá representar os valores de uma das variáveis, no caso tomaremos o eixo horizontal para a variável x e o eixo vertical para a variável y.

24

A seguir todas as restrições devem ser representadas no plano xy. Vejamos a primeira restrição A expressão 5 x + 10 y representa o número total de horas de preparação que os dois conjuntos irão ocupar. É obrigatório que essa não ultrapasse a 100 horas, que é o máximo disponível. Suponha por um momento que a soma 5 x + 10 y ocupasse exatamente as 100 horas disponíveis, ou seja, 5 x + 10 y = 100 essa igualdade é apenas a equação de uma reta, que pode ser determinada no plano se soubermos as coordenadas de dois dos seus pontos. Tradicionalmente, escolhem-se os pontos (0,y) e (0,x) ou seja, os pontos onde a reta encontra os eixos x e y . Se x = 0 então 5 (0) + 10 y = 100 e y = 10. Se y = o então 5 x + 10 (0) = 100 e x = 20. A reta resultante encontra-se na figura abaixo: (restrição de horas de preparação)

Número de conjuntos Anamaria (y)

Número de conjuntos Beatrice (x)

Ao longo da reta, teremos todas as combinações possíveis de valores de x e de y tal que 5 x + 10 y = 100 assim, por exemplo se x = 6 teremos 5 (6) + 10 y = 100 ou y = 7. A região compreendida entre a reta e os eixos também obedece à restrição 5 x + 10 y < 100, logo a restrição pode ser representada pela área compreendida entre a reta e os eixos, incluída a própria reta para o caso de igualdade 5 x + 10 y = 100. A essa área que aparece no gráfico, denominamos de zona permissível pela restrição do número de horas disponíveis de preparação . A área é limitada pelos eixos porque valem as condições de não negatividade. Qualquer ponto fora da zona permissível (como por exemplo o ponto onde x = 10 e y = 14) não será uma solução possível para o problema. A restrição seguinte diz respeito ao número máximo disponível de horas para acabamento 9 x + 6 y < 108 tomando novamente a igualdade, a reta resultante cortará os eixos nos pontos (0,8) e (12,0) como é mostrado no gráfico. A região admissível novamente está compreendida entre a reta e os dois eixos, sendo a própria reta o limite, valendo pela igualdade citada.

(Restrição de horas de acabamento)

Número de conjuntos Anamaria (y)

25


Finalmente a última restrição estabelece que o número máximo de conjuntos Anamaria que pode ser fabricado é igual a 8 , ou seja: 1 y < 8 O gráfico a seguir mostrará a reta que responde pela igualdade. Ela é paralela ao eixo, delimitando uma região permissível que não tem limites para a direita, indicando que para qualquer número de conjuntos Beatrice que se queira, o número de conjuntos Anamaria jamais ultrapassa a 8.

(Restrição : conjuntos Anamaria) Número de conjuntos Anamaria (y)


Os pontos A, B, C, e D são chamados PONTOS EXTREMOS da região possível, que nesse caso é finita e delimitada pelas arestas do polígono ABCDE. Não é difícil determinar as coordenas desses pontos extremos. Os pontos A, B, e E, por sua localização especial, têm coordenadas imediatas.

26

A ( x = 0, y = 0 ) ( origem dos eixos )

B ( x = 12, y = 0 )

E ( x = 0,y = 8 )

Os pontos C e D podem ser determinados diretamente por inspeção visual no gráfico, se ele estiver suficientemente claro, no caso em pauta, distingue-se que as coordenadas desses pontos são: C = ( X = 8,Y = 6 )

D ( X = 4, Y = 8 )

Se o gráfico não estiver traçado em perfeita escala ou se a leitura indica números fracionários, é conveniente determinar-se as coordenadas por meio analíticos. Vejamos como isso é feito com os pontos C e D. Para determinar o ponto C, nota-se que ele é o ponto de intersecção das retas limite das restrições referentes às horas de preparação e de acabamento, ou seja, é a intersecção de 5 x + 10 y = 100 (I)

9 x + 6 y = 108 (II)

Uma combinação linear adequada entre as duas equações permitirá obter uma das variáveis, cujo valor poderá ser então, substituído em qualquer uma das equações originais para dar o valor da outra variável restante. Multiplicando-se a equação (I) por 3, a equação (II) pó 5 e subtraindo a (II) da (I) vem que 15 x + 30 y = 300 ( - ) 45 x + 30 y = 540 fififififififififififififififififi - 30 x + 0 = - 240 de onde se conclui que x =8 que substituído na equação (I) fornece 5 (8) + 10 y = 100 10 y = 100 – 40 = 60 y = 6 semelhantemente, o ponto D é o encontro das retas limite das restrições do número máximo de horas disponíveis de preparação e do número máximo de conjuntos Anamaria. 5 x + 10 y = 100 1 y = 8

27

o que fornece imediatamente x = 4 embora tenhamos no momento uma região permissível para a solução do problema e conheçamos as coordenadas dos pontos limites dessa região, ainda não temos a solução propriamente dita. Acontece que os pontos extremos da região permissível guardam uma importantíssima propriedade: “A solução ótima encontra-se em um dos pontos extremos” para descobrir qual é o ponto que nos fornece a solução ótima, basta substituirmos as coordenadas de todos os pontos extremos na função objetivo, como mostrado em seguida:

A solução ótima encontra-se, portanto, no ponto C , fornecendo um valor de R$ 62.000,00 para a FUNÇÃO OBJETIVO. Corresponde a fabricar 8 conjuntos Beatrice e 6 conjuntos Anamaria. Há uma outra forma de se determinar o ponto C como SOLUÇÃO ÓTIMA. A função objetivo 4000 x + 5000 y define uma família de retas no plano xy. Atribuindo um valor arbitrário à função poderemos encontrar a reta correspondente, analogamente ao que fizemos com as restrições. Atribuindo a 4000 x + 5000 y, por exemplo, o valor 20.000 (múltiplo de 4000 e 5000, para facilitar os cálculos) define-se a reta que passa pelos pontos ( 0,4) e (5,0) , como se mostra no gráfico:

Se a reta for movida paralelamente a si mesma, para a direita, o último ponto da região permissível que ela tangenciará será o ponto C. O gráfico também mostra um movimento intermediário, correspondente a um valor

28

40.000 para a função objetivo. Observe que ao mover a reta para a direita, paralelamente a si mesma, significa atribuir valores cada vez maiores à função objetivo. Como o ponto C é o último ponto da tangência da região possível, a ele corresponderá a solução (x = 8 e y = 6 ) que maximiza a função objetivo. SOLUÇÃO GRÁFICA: PROBLEMA DE MINIMIZAÇÃO O tratamento é análogo ao caso de problemas de maximização: as restrições são delimitadas por retas, definindo-se as regiões permissíveis. A combinação dessas regiões dará a região final, comum a todas as restrições. A solução estará então, em um dos pontos extremos. Como se recorda, o problema da ABC Química Industrial Ltda. Tinha 4 variáveis, de forma que não podemos tomá-lo como exemplo. Consideremos então, o modelo abaixo. Minimizar 4 x + 4 y Sujeito a 2 x + 1 y > 10

1 x + 2 y > 8 1 y < 6

transformando as desigualdades em igualdades, delimita-se a região comum mostrada no gráfico abaixo:

As regiões permissíveis ficam a gora à direita das retas limite traçadas para as restrições 2x +1y>10 e 1x + 2y > 8, em quanto que a região permissível para a restrição 1y <6 localiza-se entre a reta 1y = 6 e o eixo da variável x, limitando-se à esquerda pelo eixo da variável y. A região comum permissível é limitada à direita e os pontos extremos resumem-se a A, B e C, cujas coordenadas, são as seguintes: A ( x = 8 y = 0)

B ( x = 4 y = 2 )

C ( x = 2 y = 6 )

29

A tabela abaixo, semelhante à que construímos de maximização, mostra que a solução ótimo encontra-se no ponto B, com a função objetivo assumindo seu valor mínimo de 24.

Podemos também determinar a solução ótima construindo as retas derivadas da função objetivo dando valores à expressão 4 x + 4 y, como mostra o gráfico abaixo:

no gráfico foram dados os valores 40, 32 e 24, este último corresponde ao valor mínimo da função objetivo e portanto, tangenciando o ponto B. Repare que agora devemos mover as retas derivadas da função objetivo para a esquerda, até encontrar o ponto extremo. EXERCICIOS: 01) Resolva graficamente o modelo abaixo: (MAX) Z = 3x1 + 5x2 s.a (1) x1 ≤ 4 (2) 2x2 ≤ 12 (3) 3x1 + 2x2 ≤18 (4) x1 ≥ 0 (5) x2 ≥ 0 02) Resolva graficamente o modelo abaixo: (MAX) Z = 2x1 + x2 s.a (1) x2 ≤ 10

30

(2) 2x1 + 5x2 ≤ 60 (3) x1 + x2 ≤ 18 (4) 3x1 + x2 ≤ 44 (5) x1 ≥ 0 (6) x2 ≥ 0 03) Exercícios da lista 01

CAPÍTULO 4 O MÉTODO SIMPLEX

O Método Simplex caminha pelos vértices da região viável até encontrar uma solução que não possua soluções vizinhas melhores que ela. Esta é a solução ótima. A solução ótima pode não existir em dois casos: quando não há nenhuma solução viável para o problema, devido a restrições incompatíveis; ou quando não há máximo (ou mínimo), isto é, uma ou mais variáveis podem tender a infinito e as restrições continuarem sendo satisfeitas, o que fornece um valor sem limites para a função objetivo. 4.1 Exemplo de um Problema O modelo de programação linear pode ser resolvido por um método de solução de sistema de equações lineares. O processo que será apresentado no exemplo a seguir, retirado de ANDRADE (2000), é bastante intuitivo e tem por finalidade apresentar a metodologia utilizada pelo método Simplex. a) Formulação do problema Uma marcenaria deseja estabelecer uma programação diária de produção. Atualmente, a oficina faz apenas dois tipos de produtos: mesa e armário, ambos de um só modelo. Para efeito de simplificação, vamos considerar que a marcenaria tem limitações em somente dois recursos: madeira e mão-de-obra, cujas disponibilidades diárias são mostradas na tabela a seguir:

O processo de produção é tal que, para fazer uma mesa a fábrica gasta 2 m2 de madeira e 2 H.h de mão-de-obra. Para fazer um armário, a fábrica gasta 3 m2 de madeira e 1 H.h de mão de obra. Além disso, o fabricante sabe que cada mesa dá uma margem de contribuição para o lucro de $ 4 e cada armário de $ 1. O problema é encontrar o programa de produção que maximiza a margem de contribuição total para o lucro. b) Montagem do modelo As variáveis de decisão envolvidas no problema são: x1: quantidade a produzir de mesas x2: quantidade a produzir de armários A função objetivo é: Lucro: z = 4 x1 + x2

Para as restrições, a relação lógica existente é: Utilização de recurso ≤ Disponibilidade Assim temos Madeira: 2 x1 + 3 x2 ≤ 12

31

Mão-de-obra: 2 x1 + x2 ≤ 8 x1, x2 ≥ 0

O modelo completo é: Maximizar: z = 4 x1 + x2

Sujeito a 2 x1 + 3 x2 ≤ 12 2 x1 + x2 ≤ 8 x1, x2 ≥ 0

c) Solução do modelo Já conhecemos o método de solução gráfica para problemas de programação linear de duas variáveis. Será agora apresentada a solução por sistemas de equações lineares. De forma a transformar as restrições do problema de programação linear de inequações em equações, são introduzidas as variáveis de folga. Neste problema, as restrições têm a seguinte estrutura lógica: Utilização de recurso ≤ Disponibilidade. Ao se introduzir o conceito de folga de recurso, a inequação pode ser escrita como: Utilização de recurso + Folga = Disponibilidade. Isso significa que Utilização de recurso < Disponibilidade implica Folga > 0; Utilização de recurso = Disponibilidade implica Folga = 0. Deste modo, a folga de cada recurso pode ser representada por uma variável de forma exatamente igual à produção de cada produto. Desse modo, vamos chamar: f1: folga de madeira; f2: folga de mão-de-obra. Introduzindo as variáveis de folga, o problema a ser resolvido passa a ser: Maximizar: z = 4 x1 + x2

Sujeito a 2 x1 + 3 x2 + f1 = 12

2 x1 + x2 + f2 = 8 x1, x2, f1, f2 ≥ 0

O problema se transformou em encontrar a solução do sistema de equações lineares que maximiza o lucro. Como neste caso o número de variáveis (m = 4) é superior ao número de equações (n = 2), o sistema é indeterminado, apresentando infinitas soluções. No entanto, todas as variáveis devem ser maiores ou iguais a zero. Atribuir zero a uma variável significa não produzir um dos produtos (se a variável for x1 ou x2) ou utilizar toda a 4 - O Método Simplex Pesquisa Operacional disponibilidade de recursos (se a variável for f1 ou f2). Desta forma, podemos encontrar soluções para o sistema de equações zerando duas variáveis (n - m = 2) e encontrando o valor para as duas variáveis restantes. Teremos que resolver então

sistemas de equações lineares. Uma vez resolvido um sistema, serão aplicados na função objetivo os valores encontrados. As variáveis zeradas são chamadas variáveis não-básicas. As variáveis cujos valores são calculados pelo sistema de equações são chamadas variáveis básicas. c.1) Variáveis não-básicas: x1 = 0

x2 = 0 temos as variáveis básicas f1 = 12

f2 = 8

32

dando o lucro z = 0 c.2) Variáveis não-básicas: x1 = 0

f1 = 0 temos as variáveis básicas x2 = 4

f2 = 4 dando o lucro z = 4 c.3) Variáveis não-básicas: x1 = 0


f1 = -12 como f1 < 0, a solução obtida é INVIÁVEL. c.4) Variáveis não-básicas: x2 = 0


f2 = -4 como f2 < 0, a solução obtida é INVIÁVEL. c.5) Variáveis não-básicas: x2 = 0


f1 = 4 dando o lucro z = 16 c.6) Variáveis não-básicas: f1 = 0


x2 = 2 dando o lucro z = 14 Comparando todas as soluções encontradas por este processo, achamos a solução ótima, ou seja, x1 = 4, x2 = 0, f1 = 4, f2 = 0, dando um lucro z = 16. EXERCICIOS: Solucione os exercícios da LISTA DE EXERCÍCIO (POSSÍVEIS).

Documents

Apostila Po