poprogramacaolinear

Prévia do material em texto

�PAGE �
Pesquisa Operacional
Sistemas Produtivos
Programação Linear
Formulação de Problemas
Programação Linear é uma técnica adotada em situações onde existem vários produtos a fabricar, com auxílio de várias máquinas, necessitando-se de programa para decidir qual máquina utilizar para a fabricação de cada produto tendo-se em conta a produção máxima, o custo mínimo ou algum outro critério de eficácia. Também é muito utilizada em problemas de alocação de recursos limitados a atividades em competicão, bem como em outros problemas que tenham uma formulação matemática similar.
 
Os estudos de Programação Linear permitem responder as questões como:
Na vigência de certas condições de produção, qual quantidade de determinado produto, dentre vários, deve-se produzir para se obter o maior lucro possível?
Sendo impostas algumas especificações, qual é a composição da mistura que corresponde ao custo mínimo?
Conhecendo-se um certo número de condições de mercado (produtos, fornecedores, consumidores), como estabelecer os circuitos de distribuição de modo a minimizar o custo total?
Estando impostas as condições de trabalho, como repartir o contingente de mão-de-obra entre as diferentes tarefas e especialidades, com o objetivo de minimizar as despesas ou maximizar a eficiência?
A formulação do problema a ser resolvido por programação linear segue alguns passos básicos:
PASSO 1: determine a grandeza a ser otimizada e expresse-a como uma função matemática. Isto feito serve para definir as variáveis de entrada. 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.
PASSO 2: Identifique todas as exigências, restrições e limitações estipuladas e expresse-as matematicamente. Estas condições constituem as restriçõ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.
PASSO 3: Expresse todas as condições implícitas. Tais condições não são estipuladas explicitamente no problema, mas são evidentes a partir da situação física sendo modelada. Geralmente estas condições envolvem requisitos de serem não negativos ou de serem inteiros os valores das variáveis de entrada.
O problema geral de programação linear pode ser definido por:
Maximizar (ou minimizar) 
	Z = c1x1 + c2x2 + ... + cnxn
	Função Objetivo
sujeito a (s.a.)
	a11x1 + a12x2 + ... + a1nxn < b1 (ou >, ou =)
	Restrições técnicas
	a21x1 + a22x2 + ... + a2nxn < b2 (ou >, ou =)
	
	...
	
	am1x1 + am2x2 + ... + amnxn < bm (ou >, ou =)
	
	
	
	x1, x2,..., xn > 0
	Restrições de não negatividade
Exemplos:
Uma marcenaria deseja estabelecer uma programação diária de produção. Atualmente a oficina fabrica apenas dois produtos: mesa e armário, ambos de um só modelo. Para efeito de simplificação, será considerado 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.
	Recurso
	Disponibilidade
	Madeira
	12m2
	Mão-de-obra
	8h
O processo de produção é tal que, para fazer 1 mesa, a fábrica gasta 2m2 de madeira e 2 horas de mão-de-obra. Para fazer um armário, a fábrica gasta 3m2 de madeira e 1 hora 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 dá uma margem de $1. O problema do fabricante é encontrar o programa de produção que maximiza a margem de contribuição total para o lucro.
Como variáveis de decisão, serão considerados os seguintes dados:
x1 ( quantidade a produzir de mesa; e
x2 ( quantidade a produzir de armário.
Com essa definição de variáveis pode-se escrever as relações matemáticas que formam o modelo. Assim, para a função objetivo tem-se: 
Margem de Contribuição Total: Z = 4.x1 + 1.x2
Para as restrições, a relação lógica existente é:
Utilização de recurso < disponibilidade do recurso
Assim, tem-se:
	Para madeira:
	2.x1 + 3.x2
	< 12
	
	(
	 (
	
	Utilização de madeira para os dois produtos
	Disponibilidade de madeira
	
	
	
	Para mão-de-obra
	2.x1 + 1.x2
	< 8
	
	(
	 (
	
	Utilização de mão-de-obra para os dois produtos
	Disponibilidade de mão-de-obra
O modelo completo é:
Achar x1 e x2, de modo a:
Maximizar Z = 4.x1 + 1.x2
s.a.
	2.x1 + 3.x2 < 12
	Restrições técnicas
	2.x1 + 1.x2 < 8
	
	
	
	 x1 > 0
	Restrições de não negatividade
	 x2 > 0
	
�
Certa empresa fabrica dois produtos P1 e P2. O lucro unitário do produto P1 é 1.000 unidades monetárias e o lucro unitário de P2 é de 1.800 unidades monetárias. 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 de 30 unidades anuais para P2. Qual é o plano de produção para que a empresa maximize seu lucro nesses itens?
Como variáveis de decisão, serão considerados os seguintes dados:
x1 ( quantidade anual a produzir de P1 e x2 ( quantidade anual a produzir de P2.
Com essa definição de variáveis pode-se escrever as relações matemáticas que formam o modelo. O objetivo é maximizar o lucro, que pode ser calculado:
Lucro devido a P1: 1.000 . x1 (lucro por unidade de P1 x quantidade produzida de P1)
Lucro devido a P2: 1.800 . x2 (lucro por unidade de P2 x quantidade produzida de P2)
Lucro toral: Z = 1.000.x1 + 1.800.x2
Assim, para a função objetivo tem-se: Maximizar: Z = 1.000.x1 + 1.800.x2
Para as restrições, a relação lógica existente é: 
Utilização de recurso < disponibilidade do recurso. As restrições impostas pelo sistema são:
Disponibilidade de horas para a produção: 1.200 horas
Horas ocupadas com P1: 20.x1 (uso por unidade x quantidade produzida)
Horas ocupadas com P2: 30.x2 (uso por unidade x quantidade produzida)
Total em horas ocupadas na produção: 20.x1 + 30.x2
Assim, temos:
	Para horas para a produção:
	20.x1 + 30.x2
	< 1.200
	
	(
	(
	
	Total em horas ocupadas na produção
	Disponibilidade de horas para a produção
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
O modelo completo é:
Achar x1 e x2, de modo a:
Maximizar Z = 1.000.x1 + 1.800.x2
s.a.
	20.x1 + 30.x2 < 1.200
	
Restrições técnicas
	x1 < 40
	
	x2 < 30
	
	
	
	 x1 > 0
	Restrições de não negatividade
	 x2 > 0
	
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 de couro para fabricar uma unidade de cinto. Sabendo-se que o total disponível de couro é de 6 unidade e que o lucro unitário por sapato é de 5 unidades 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.
Certa empresa fabrica 2 produtos P1 e P2. O lucro por unidade de P1 é de 100 unidades monetárias e o lucro unitário de P2 é de 150 unidades monetárias. A empresa necessita de 2 horas para fabricar uma unidade de P1 e de 3 horas para fabricar uma unidade de P2. O tempo mensal disponível para essas atividades é de 120 horas. 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 30unidades de P2 por mês. Construa o modelo do sistema de produção mensal com o objetivo de maximizar o lucro da empresa.
Um vendedor de frutas pode transportar 800 caixas de frutas para sua região de vendas. Ele necessita transportar 200 caixas de laranja a 20 unidades monetárias de lucro por caixa, pelo menos 100 caixas de pêssegos a 10 unidades monetárias de lucro por caixa, e no máximo 200 caixas de tangerina a 30 unidades monetárias de lucro por caixa. De que forma deverá ele carregar o caminhão para obter o lucro máximo? Construa o modelo do problema.
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 não 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.
Uma empresa fabrica 2 modelos de cintos de couro. O modelo M1, de melhor qualidade, requer o dobro de 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 M1 e 700 para M2. Os lucros unitários são de $4,00 para M1 e $3,00 para M2. Qual o programa ótimo de produção que maximiza o lucro total diário da empresa? Construa, o modelo do sistema descrito.
�
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 desses recursos indicou a possibilidade de se fabricar 2 produtos P1 e P2. Levantando os custos e consultando o departamento de vendas sobre o peç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.
	Produto
	Recurso R1 por unidade
	Recurso R2 por unidade
	Recurso R3 por unidade
	P1
P2
	2
4
	3
2
	5
3
	Disponibilidade de recurso por mês
	100
	90
	120
Que produção mensal de P1 e P2 traz o maior lucro para a empresa? Construa o modelo do sistema.
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 pelo aluguel da terra $300,00 por alqueire por ano.
P (pecuária) – usar outras parte para a criação de gado de corte. A recuperação das pastagens requer adubação (100 kg/alqueire) e irrigação (100.000 l de água/alqueire) por ano. O lucro estimado nessa atividade é de $400,00 por alqueire por ano.
S (plantio de soja) – usar uma terceira parte para o plantio de soja. Essa cultura requer 200 kg por alqueire de adubos e 200.00 l de água/alqueire para irrigação por ano. O lucro estimado nessa atividade é de $ 500,00/alqueire no ano.
Disponibilidade de recursos por ano:
12.750.000 l 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.
O departamento de marketing de uma empresa estuda a forma mais econômica de aumentar em 30% as vendas de seus dois produtos P1 e P2. As alternativas são:
Investir em um programa institucional com outras empresas do mesmo ramo. Esse programa requer um investimento mínimo de $ 3.000,00 e deve proporcionar um aumento de 3% nas vendas de cada produto, para cada $ 1.000,00 investidos.
Investir diretamente na divulgação dos produtos. Cada $ 1.000,00 investidos em P1 retornam um aumento de 4% nas vendas, enquanto que para P2 o retorno é de 10%.
A empresa dispõe de $ 10.000,00 para esse empreendimento. Quanto deverá destinar a cada atividade? Construa o modelo do sistema descrito.
�
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 é (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.
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 portos P1, P2 e P3, cujas distâncias às lojas estão no quadro (em km):
	
	L1
	L2
	L3
	L4
	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 portos têm areia para suprir qualquer demanda. Estabelecer um plano de transporte que minimize a distância total percorrida entre os portos e as lojas e supra as necessidades das lojas. Construa o modelo linear do problema.
Referências bibliográficas
ANDRADE, Eduardo Leopoldino de. (2004). Introdução à Pesquisa Operacional: métodos e modelos para análise de decisões. 3ª ed. Editora LTC, Rio de Janeiro, RJ.
BRONSON, Richard. (1985). Pesquisa Operacional. Editora McGraw-Hill, São Paulo, SP.
LISBOA, Érico. (2002). Pesquisa Operacional. http://www.ericolisboa.eng.br
SILVA, Ermes Medeiros da; et al. (1996). Pesquisa Operacional. 2ª Ed. Editora Atlas, São Paulo, SP.
�
Programação Linear
Solução para Modelos de com Duas Variáveis de Decisão (x1 e x2)
Método Gráfico
Essa técnica consiste em representar num sistema de eixos ortogonais o conjunto das possíveis soluções do problema, isto é, o conjunto de pontos (x1, x2) que obedecem ao grupo de restrições impostas pelo sistema em estudo. O desempenho do modelo é avaliado através da representação gráfica da função objetivo. As soluções são classificadas de acordo com sua posição no gráfico. A função objetivo também pode ser avaliada calculando-se o seu valor para os pontos que pertencem ao contorno da região viável.
Gráfico do conjunto de soluções
A representação gráfica de uma equação linear com duas variáveis (x1, x2) é uma reta. A representação gráfica de uma inequação linear com duas variáveis (x1, x2) é uma área do gráfico limitada pela reta correspondente à equação. Vejamos alguns exemplos.
Exemplo 1: Representar graficamente a inequação: x1 + 2x2 > 10
Construir a reta correspondente à equação: x1 + 2x2 = 10 (acompanhe no gráfico a seguir)
Para traçarmos a reta, precisamos de dois pontos. Determinar os pontos de interseção da reta com cada um dos eixos, é mais fácil:
Fazendo x1 = 0, teremos:
0 + 2x2 = 10 (substituímos x1 por 0)
2x2 = 10 (equação a ser resolvida)
x2 = 10/2 (2 que estava multiplicando x2, passa para o outro lado dividindo – operação inversa)
Assim,
x2 = 5
Um dos pontos da reta será: x1 = 0 e x2 = 5, ou seja, o ponto (0, 5).
Procedemos da mesma maneira, agora fazendo x2 = 0. Então teremos:
x1 + 2.0 = 10 (substituímos x2 por 0)
x1 + 0 = 10 (como 2 vezes 0 é igual a 0, temos esta equação a ser resolvida)
Assim,
x1 = 10
O outro ponto da reta será: x1 = 10 e x2 = 0, ou seja, o ponto (10, 0).
A reta é então traçada, conformeo gráfico a seguir. Podemos observar que há uma região sombreada no gráfico, que corresponde à região viável (região de soluções) limitada pela inequação x1 + 2x2 > 10. A região viável, então, é aquela que se encontra na região superior da reta, pois a inequação define que x1 + 2x2 deve ser maior ou igual a 10. No próximo item vamos verificar esta constatação.
Testar a inequação: x1 + 2x2 > 10
Tomamos um ponto qualquer de uma das regiões limitadas pela reta. Consideremos o ponto x1 = 10 e x2 = 5 (conforme mostrado no gráfico anterior).
Substituindo na inequação (x1 + 2x2 > 10), teremos:
10 + 2.5 > 10 ou 20 > 10, o que é verdadeiro. Portanto, a região das soluções da inequação é aquela que contém o ponto testado.
Vamos ainda testar um ponto que não esteja na região sombreada, como o ponto de origem, ou seja, x1 = 0 e x2 = 0.
Substituindo na inequação (x1 + 2x2 > 10), teremos:
0 + 2.0 > 10 ou 0 > 10, o que NÃO é verdadeiro. Portanto, este ponto e os outros que se encontram abaixo da reta não pertencem à região das soluções.
Exemplo 2: Representar graficamente a solução do sistema:
x1 + 3x2 < 12
2x1 + x2 > 16
x1 > 0
x2 > 0
Solução:
Vamos representar cada uma das retas correspondentes:
x1 + 3x2 = 12	se x1 = 0, então 0 + 3 . x2 = 12. Portanto, x2 = 12/3 ou x2 = 4.
se x2 = 0, então x1 + 3 . 0 = 12. Portanto, x1 = 12.
Assim, os pontos que utilizamos para traçar esta reta são: (0, 4) e (12, 0). A região viável limitada por esta reta é aquela que está abaixo da reta, conforme o gráfico abaixo, pois a inequação define que x1 + 3x2 deve ser menor ou igual a 12.
2x1 + x2 = 16	se x1 = 0, então 2.0 + x2 = 16. Portanto, x2 = 16.
se x2 = 0, então 2.x1 + 0 = 16. Portanto, x1 = 16/2 ou x1 = 8.
Os pontos que utilizamos para traçar esta reta são: (0, 16) e (8, 0). A região viável limitada por esta reta é aquela que está acima da reta, conforme o gráfico abaixo, pois a inequação define que 2x1 + x2 deve ser maior ou igual a 16.
As restrições de não negatividade x1 > 0 e x2 > 0 representam o primeiro quadrante do gráfico de soluções.
Vamos testar para cada reta qual a região que corresponde à solução da inequação. Para isso escolhemos um ponto fora das retas, por exemplo, o ponto (8, 16).
x1 + 3x2 < 12; substituindo x1 = 8, x2 = 16, obtém-se:
8 + 3 . 16 < 12 ou 56 < 12; a desigualdade é falsa.
Solução: região oposta (veja a flecha indicativa).
2x1 + x2 > 16; substituindo x1 = 8, x2 = 16, obtém-se:
2 . 8 + 16 > 16 ou 32 > 16; a desigualdade é verdadeira. (Flecha indicativa da solução na região do ponto testado.)
A região de soluções aparece sombreada no gráfico. Esta é a região que contém todas as possíveis soluções para o sistema e onde todas as restrições são respeitadas.
Método gráfico
Para encontrarmos a solução de um problema de programação linear com duas variáveis de decisão através do método gráfico, podemos adotar os seguintes passos:
traçar as retas correspondentes a cada restrição, num sistema de eixos x1 e x2;
determinar a região viável (região onde se encontram todas as possíveis soluções para o problema em questão);
determinar os pontos que delimitam a região viável;
calcular o valor da função objetivo para cada um dos pontos da região viável;
a partir dos cálculos realizados para Z, determinar o ponto que corresponde à otimização pretendida (maximizar ou minimizar) e então determinar o ponto ótimo.
�
Exemplos:
1) Certa empresa de alimentos congelados processa batatas em embalagens de batatinha frita, picadinho de batata e flocos para purê. As batatas podem ser compradas de duas fontes, cada uma fornecendo lucros distintos. A empresa necessita determinar a quantidade de batata a ser comprada de cada fonte (x1 e x2), de forma a obter o maior lucro. Embora uma das fontes apresente o maior lucro, o aproveitamento das batatas de cada fonte se dá de forma diversa. Além disso, a empresa deve considerar o seu potencial de vendas, para cada um dos produtos.
O problema de programação linear a ser resolvido é:
Maximizar Z = 5x1 + 6x2
s.a.
		2x1 + 3x2 < 18 (restrição para batatinha frita)
		2x1 + x2 < 12 (restrição para picadinho)
		3x1 + 3x2 < 24 (restrição para flocos)
		x1 > 0, x2 > 0 (restrições de não-negatividade)
Para resolver este problema de programação linear, seguiremos os passos citados anteriormente:
I) Traçar as retas correspondentes a cada restrição, num sistema de eixos x1 e x2.
a) Reta relativa à restrição da batatinha frita:
2x1 + 3x2 = 18
Se x1 = 0, então 2 . 0 + 3 . x2 = 18. Portanto, x2 = 18/3 ou x2 = 6.
Se x2 = 0, então 2 . x1 + 3 . 0 = 18. Portanto, x1 = 18/2 ou x1 = 9.
Assim, os pontos que utilizamos para traçar esta reta são: (0, 6) e (9, 0). A região viável limitada por esta reta é aquela que está abaixo da reta, conforme o gráfico abaixo, pois a inequação define que 2x1 + 3x2 deve ser menor ou igual a 18.
�
b) Reta relativa à restrição do picadinho:
2x1 + x2 = 12
Se x1 = 0, então 2 . 0 + x2 = 12. Portanto, x2 = 12.
Se x2 = 0, então 2 . x1 + 0 = 12. Portanto, x1 = 12/2 ou x1 = 6.
Assim, os pontos que utilizamos para traçar esta reta são: (0, 12) e (6, 0). A região viável limitada por esta reta é aquela que está abaixo da reta, conforme o gráfico abaixo, pois a inequação define que 2x1 + x2 deve ser menor ou igual a 12.
c) Reta relativa à restrição dos flocos:
3x1 + 3x2 = 24
Se x1 = 0, então 3 . 0 + 3 . x2 = 24. Portanto, x2 = 24/3 ou x2 = 8.
Se x2 = 0, então 3 . x1 + 3 . 0 = 24. Portanto, x1 = 24/3 ou x1 = 8.
Assim, os pontos que utilizamos para traçar esta reta são: (0, 8) e (8, 0). A região viável limitada por esta reta é aquela que está abaixo da reta, conforme o gráfico abaixo, pois a inequação define que 3x1 + 3x2 deve ser menor ou igual a 24.
�
II) Determinar a região viável (região onde se encontram todas as possíveis soluções para o problema em questão).
A região viável é a região que contém todas as possíveis soluções para o sistema e onde todas as restrições (batatinha frita, picadinho,flocos) são respeitadas. Pode ser definida como a região comum a todas as restrições. Esta região é demonstrada na figura a seguir.
Podemos observar que a restrição referente aos flocos não influencia a região de soluções. Esta região ficou delimitada pelas restrições da batatinha frita e do picadinho.
III) Determinar os pontos que delimitam a região viável.
Pelo gráfico acima podemos constatar que a região viável é delimitada por quatro linhas que se encontram em quatro pontos. Três destes pontos podem ser facilmente verificados, e são: (0, 0), (6, 0) e (0, 6). O quarto ponto é aquele em que as retas correspondentes às restrições, da batatinha frita e do picadinho, se encontram. Sendo este ponto comum às duas retas, ele pode ser determinado resolvendo o sistema correspondente às duas retas.
2x1 + 3x2 = 18 (restrição para batatinha frita)
2x1 + x2 = 12 (restrição para picadinho)
Se subtrairmos uma reta da outra, podemos eliminar uma das variáveis das equações, e então determinar a outra.
Assim:
2x1 + 3x2 = 18
- 	(2x1 + x2 = 12)
0.x1 + 2x2 = 6
x2 = 6/2
x2 = 3
Substituindo x2 = 3 em qualquer uma das equações acima, obtemos x1.
�
Então:
2x1 + 3 . 3 = 18
2x1 + 9 = 18
2x1 = 18 – 9
2x1 = 9
x1 = 9/2
x1 = 4,5
O ponto comum é x1 = 4,5 e x2 = 3.
IV) Calcular o valor da função objetivo para cada um dos pontos da região viável.
A partir dos pontos da região viável, definidos anteriormente, podemos calcular o valor da função objetivo para cada ponto.
A função objetivo é dada pela equação Z = 5x1 + 6x2
Função objetivo para o ponto (0, 0) ( Z (0, 0) = 5 . 0 + 6 . 0 = 0
Função objetivo para o ponto (6, 0) ( Z (6, 0) = 5 . 6 + 6 . 0 = 30 + 0 = 30
Função objetivo para o ponto (0, 6) ( Z (0, 6) = 5 . 0 + 6 . 6 = 0 + 36 = 36
Função objetivo para o ponto (4,5 , 3) ( Z (4,5, 3) = 5 . 4,5 + 6 . 3 = 22,5 + 18 = 40,5
V) A partir dos cálculos realizados para Z, determinar o ponto que corresponde à otimização pretendida (maximizar ou minimizar) e então determinar o ponto ótimo.
Através dos cálculos para Z, realizados no passo anterior, podemos obter o ponto ótimo do problema. A otimização desejada no problema é maximizar. Assim, aquela função objetivo que apresentar o maior valor (problema de maximização), nos fornecerá a solução do problema. Ou seja, as quantidades a serem compradas de cada uma das fontes.
O maior valor para a função objetivo foi 40,5 e corresponde ao ponto x1 = 4,5 e x2 = 3, que é considerado o ponto ótimo do problema e é demonstrado na figura a seguir.
	Portanto, a fim de obter o maior lucro, a quantidade de batata a ser comprada pela empresa de cada fonte é 4,5 e 3 (em unidades de peso). 
�
2) A empresa Nova Linha produz artigos de vidro de alta qualidade: janelas e portas, em três seções de produção: 
Seção de Serralharia: 		para produzir as estruturas de alumínio
Seção de Carpintaria:			para produzir as estruturas de madeira
Seção de Vidro e Montagem: 	para produzir vidro e montar as portas e janelas
Devido à diminuição dos lucros, o gerente geral decidiu reorganizar a produção, e propõe produzir só 2 produtos que têm uma melhor aceitação entre os clientes. Estes produtos são:
Produto 1: 	uma porta de vidro com estrutura de alumínio
Produto 2: 	uma janela grande com estrutura de madeira.
O Departamento de Marketing concluiu que a empresa pode vender tanto de qualquer dos dois produtos, tendo em conta a capacidade de produção disponível. Como ambos os produtos partilham a capacidade de produção da seção Nº3, o gerente solicitou ao Departamento de Pesquisa Operacional da empresa a resolução deste problema.
O Departamento de PO para realizar a formulação do problema, procurou os seguintes dados:
a capacidade de produção por minuto de cada seção a ser utilizada na produção de ambos os produtos
a capacidade de produção por minuto de cada seção, a ser utilizada para produzir uma unidade de cada produto
os lucros unitários para cada produto
Estes dados estão resumidos na seguinte tabela:
	
	Capacidade utilizada por unidade de produção
	
	Secção Nº
	Produto 1
	Produto 2
	Capacidade disponível
	1
	1
	0
	4
	2
	0
	2
	12
	3
	3
	2
	18
	Lucro unitário
(em reais)
	3
	5
	
Então, o problema de programação linear a ser resolvido é:
Maximizar		 Z = 3x1 + 5x2, 
 sujeito a
 		 x1 ( 4
 		 	 2x2 ( 12
 3x1+ 2x2 ( 18
x1 ( 0, x2 ( 0
Primeiramente vamos identificar os valores de (x1, x2) que satisfaçam todas as restrições (região de admissibilidade)
1º) x1 ( 0, x2 ( 0 ( (x1 , x2) estão no 1º Quadrante
2º) x 1 ( 4 ( (x1 , x2) estão situados à esquerda ou sobre a reta x1 = 4
3º) 2x2 ( 12 ( x 2 ( 6 ( (x1 , x2) estão situados abaixo ou sobre a reta x2 = 6
4º) 3x1 + 2x2 ( 18 ( (x1 , x2) estão situados abaixo ou sobre a reta 3x1 + 2x2 =18 
�
	Para determinar a solução ótima consideramos que a função objetivo Z = 3x1 + 5x2 define uma reta que pode ser deslocada paralelamente no sentido do seu gradiente (garantindo o crescimento de Z), até se tornar tangente à região admissível. 
Neste caso o ponto de tangência (2,6) otimiza a função objetivo, pelo que a solução pretendida é x1 = 2, x2 = 6. O valor ótimo é 36. 
Portanto, Nova Linha deve fabricar duas portas (produto 1) e seis janelas (produto 2) por minuto obtendo um lucro de 36 reais por minuto. 
�PAGE �
�PAGE �1�