O Problema de Programação Linear

	[pic 1]	PONTIFÍCIA UNIVERSIDADE CATÓLICA DE CAMPINAS [pic 2] SISTEMAS DE INFORMAÇÃO FUNDAMENTOS DE PESQUISA OPERACIONAL E DE SIMULAÇÃO APLICADOS A SOFTWARE Profª Bia Leite

Avaliações	T1	P1	Trabalho	P2	Recuperação
05/09	19/09	07/11	21/11	05/12

1. INTRODUÇÃO        

A Pesquisa Operacional (PO) foi o nome dado ao conjunto de processos e métodos de análise desenvolvidos por um grupo de cientistas que assessoraram as forças militares inglesas na Segunda Guerra Mundial. A motivação foi tomar decisões com bases científicas sobre a melhor utilização de material de guerra, como: emprego eficiente do radar, uso de canhões antiaéreos, escolta naval, etc.

Após a guerra, as ideias propostas foram adaptadas para melhorar a eficiência e a produtividade do setor civil.

1. MODELOS DE PROGRAMAÇÃO LINEAR        

A Modelagem Matemática é um processo que, a partir de algumas etapas, busca representar um problema real por meio de um modelo matemático. Assim, podemos dizer que o modelo matemático é uma representação simplificada da realidade. Esse processo pode ser sintetizado a parir do seguinte esquema:[pic 3][pic 4][pic 5]

[pic 6] [pic 7] [pic 8] [pic 9] [pic 10]

[pic 11]        [pic 12] [pic 13]

Tema: escolha do tema (assunto) a ser trabalhado. Quanto mais amplo e abrangente, mais possibilidades são apresentadas e maior será a riqueza do trabalho.[pic 14]

---

Coleta de dados: Pesquisa sobre o assunto escolhido para que a pesquisa possa ser direcionada e defina-se o enfoque a ser dado.

Definição dos problemas: A medida que a pesquisa se desenvolve, aspectos interessantes vão se delineando e despertando a curiosidade em aprofundar a investigação. Nesta etapa definem-se quais problemas serão abordados na formulação dos modelos matemáticos. Esta fase também envolve a abstração da situação que leva à formulação dos modelos, incluindo a seleção de variáveis, a formulação das hipóteses e simplificações necessárias.

Modelos matemáticos: Resultado da substituição da linguagem natural da abstração feita anteriormente por uma linguagem matemática. Ou seja, aqui é feita a “tradução” do problema para uma linguagem matemática;

Resolução: Escolha e emprego de técnicas e procedimentos matemáticos apropriados que possibilitem a resolução do modelo matemático formulado.

Validação: Comparação da solução matemática obtida e sua viabilidade/ significado diante do problema real. Necessidade da interpretação da solução. A não aplicabilidade (rejeição) da mesma leva a modificação do modelo, que significa rever: as hipóteses formuladas, as simplificações feitas, a coerência/veracidade dos dados coletados, os procedimentos matemáticos utilizado, etc. A modificação também pode ser uma etapa no processo de aprimoramento do modelo.

A Modelagem Matemática utiliza a linguagem matemática como ferramenta para analisar/resolver situações reais.

A Programação Linear (PL) é uma das técnicas mais utilizadas na PO. A PL tem por objetivo encontrar a melhor solução para problemas que são traduzidos por relações funcionais lineares, o que se constitui na grande aplicabilidade e simplicidade que a caracterizam. A tarefa da Programação Linear consiste na otimização (maximização ou minimização) de uma função linear, chamada função objetivo, respeitando-se um sistemas de

igualdades ou desigualdades que representam as limitações do problema, recebendo o nome de restrições.

Dois passos são fundamentais para a resolução de um PPL (Problema de Programação Linear): a Modelagem (obtenção do modelo) e a resolução do modelo (obtenção da solução).

Um modelo de PL (assim como qualquer outro modelo de PO) possui três componentes básicos:

1. Variáveis de decisão
2. Função Objetivo – estabelece um critério objetivo de escolha das variáveis de decisão, descrito por uma função linear.
3. Restrições – descreve as relações de interdependência entre as variáveis de decisão, expressas por um conjunto de equações/inequações lineares.

Além disso, a linearidade significa que a PL satisfaz as seguintes propriedades:

• Proporcionalidade: essa propriedade requer que a contribuição de cada variável de decisão, tanto na função objetivo quanto nas restrições, seja diretamente proporcional ao valor da variável.

• Aditividade: essa propriedade requer que a contribuição total de todas as variáveis envolvidas na função objetivo e nas restrições seja a soma direta das contribuições individuais de cada variável.

• Certeza: os coeficientes da função objetivo e das restrições são determinísticos, isto é, são constantes conhecidas.

Um modelo geral de PL pode ser sintetizado por:

[pic 15]

Sujeito às

[pic 16]

1. – Formulação de modelos de Programação Linear Roteiro:

1. descrever o objetivo
2. descrever as limitações / exigências 3) identificar as variáveis

---

4) traduzir o objetivo e as restrições matematicamente usando as variáveis de decisão.

Comecemos com alguns exemplos:

1. A tabela abaixo apresenta as quantidades de couro, borracha e cola que são utilizados na fabricação de sapatos e bolsas, a disponibilidade semanal destas matérias-primas e o lucro unitário de cada produto. Como deve ser planejada a produção de sapato e bolsa para que se atinja o maior lucro possível? Uma empresa fabrica 5 produtos: A, B, C, D e E. Cada um deles requer 3 tipos de matérias-primas: M1, M2, M3. As quantidades utilizadas por cada produto, as disponibilidades das matérias primas e o lucro líquido de cada produto são dados na tabela abaixo:[pic 17]

Produtos Matéria-prima	sapato	bolsa	disponibilidade
Couro	2	1	8
borracha	1	1	3
Cola	1	2	7
Lucro unitário	30	20

1. Um criador de gado deseja determinar as quantidades de cada ingrediente que devem ser dadas aos animais para se conseguir uma ração bem balanceada e de custo mínimo. Na tabela abaixo são dados os custos de cada ingrediente, a quantidade de cada nutriente em 1 kg de cada ingrediente e os requisitos diários exigidos.

ingredientes nutrientes	1 kg milho	1 kg alfafa	1        kg cereais	Mínimo requerido
Carboidratos	90	40	20	200
Vitaminas	10	60	20	150
Proteínas	30	50	80	180
custo	2,5	2,00	2,3

1. Uma empresa fabrica 5 produtos: A, B, C, D e E. Cada um deles requer 3 matérias-primas: M1, M2 e M3. As quantidades utilizadas por cada produto, as disponibilidades das matérias primas e o lucro líquido unitário de cada produto estão na tabela abaixo:[pic 18]

Produto matéria-prima	A	B	C	D	E	matéria prima disponível
M1	2	5	3	2	1	100 unidades
M2	3	1	4	7	2	80 unidades

menos 5000 m2. Sabendo-se que o lucro de A é 10000 u.m., de B é 800 u.m. e de C é de 5000 u.m. por m2, formule o PPL de tal forma que o lucro seja o maior possível.