MODELAGEM E SIMULAÇÃO DE PROCESSOS - UNIDADE 2_ atual (1)

Prévia do material em texto

PROGRAMAÇÃO LINEAR
Modelagem e Simulação 
de Processos
(ENG39)
Tutora: Maraiza de Freitas
E-mail: 100106411@tutor.uniasselvi.com.br
Unidade 2: Modelos e métodos 
numéricos para a otimização 
dos processos industriais e 
recursos produtivos
TÓPICO 1
PROGRAMAÇÃO LINEAR
1 INTRODUÇÃO
Os Problemas de Programação Linear (PPL) são problemas
de otimização que têm como objetivo “maximizar ou
minimizar” uma função linear que apresenta diversas
variáveis.
Essa função comumente é denominada Função Objetivo
(FO), estando sujeita a algumas relações lineares de
igualdade ou desigualdade, conhecidas como restrições do
problema.
TÓPICO 1
PROGRAMAÇÃO LINEAR
2 ASPECTOS GERAIS SOBRE 
MODELAGEM MATEMÁTICA E
PROGRAMAÇÃO LINEAR
Segundo Carvalho (2014), o
desenvolvimento da Programação Linear,
aborda três tipos de problemas:
• Transporte;
• Composição;
• Formação e produção.
TÓPICO 1
PROGRAMAÇÃO LINEAR
2 ASPECTOS GERAIS SOBRE 
MODELAGEM MATEMÁTICA E
PROGRAMAÇÃO LINEAR
1) Transporte: otimização de sistemas de distribuição,
otimização dos custos de transporte, a demanda por
uma determinada loja e as quantidades máximas de
manufatura de uma empresa etc.
2) Composição: otimizar a estruturação de uma dieta,
minimização do custo e atendendo aos níveis mínimos
de calorias e vitaminas essenciais na alimentação.
3) Formação e produção: otimizar processos de
contratação e formação de funcionários, bem como de
produção e armazenagem, minimizando os custos e
maximizando os lucros de uma empresa.
TÓPICO 1
PROGRAMAÇÃO LINEAR
2 ASPECTOS GERAIS SOBRE 
MODELAGEM MATEMÁTICA E
PROGRAMAÇÃO LINEAR
2.1 DESENVOLVIMENTO DE 
MODELOS DE
PROGRAMAÇÃO LINEAR
De modo geral, a construção de um problema de
programação linear (PPL) abrange três partes:
1) Definição do objetivo do problema
(Max./Min);
2) Escolha das variáveis (FO);
3) Construção do sistema de restrições (limites
restritivos em relação às variáveis de
decisão)
não negatividade das variáveis de decisão.
TÓPICO 1
PROGRAMAÇÃO LINEAR
3 APLICAÇÕES PRÁTICAS
A multidisciplinaridade contribui, e muito, para
uma adequada construção do modelo,
proporcionando uma solução eficiente para o
problema.
Sobre a modelagem em programação linear,
serão apresentados alguns exemplos de
situações reais, que serão modeladas em
termos de PPL com sua função objetivo e suas
restrições.
PPL – PROBLEMA DE PROGRAMAÇÃO LINEAR.
TÓPICO 1
PROGRAMAÇÃO LINEAR
3 APLICAÇÕES PRÁTICAS
3.1 PROBLEMA DE 
TRANSPORTE
As empresas (A1 e A2) fabricantes de potes de
plástico precisam enviar sua produção para três
distribuidores (B1, B2 e B3). Os potes de
plástico são transportados em caixas fechadas,
em um número inteiro de caminhões. Os custos
de transporte de cada empresa (fonte) para
cada distribuidor (destino), as capacidades
produtivas das empresas e capacidades de
estoque dos distribuidores são apresentadas na
Tabela 1 a seguir:
A FO deverá minimizar os custos de
transporte das cargas em função da
quantidade transportada:
VARIÁVEIS DE DECISÃO
Problema de Transporte 
Balanceado
Custo A1 - B1 Qt. A1 - B1
As restrições do problema de transporte são de duas naturezas: quanto à PRODUÇÃO e quanto ao
ESTOQUE.
1) Restrições quanto à PRODUÇÃO:
A quantidade de unidades produzidas a ser transportada das empresas A1 e A2 para B1, B2 e B3
deve ser igual ao total de unidades produzidas por A1 e A2.
A1 
A2 
2) Restrições quanto à capacidade de ESTOQUE?:
A quantidade de unidades produzidas a ser transportada das empresas A1 e A2 para B1, B2 e
B3, deve ser igual à capacidade total de estoque de B1, B2 e B3.
A1 e A2>B1 
A1 e A2>B2 
A1 e A2>B3 
X11 + X21 = 80
X12 + X22 = 55
X13 + X23 = 65
1) Restrição de não negatividade e tipo da variável:
Não há como transportar quantidades negativas de cargas. Então, todas as variáveis devem ser
maiores ou iguais a zero.
80
TÓPICO 1
PROGRAMAÇÃO LINEAR
3 APLICAÇÕES PRÁTICAS
3.2 PROBLEMA DE 
COMPOSIÇÃO
Para determinar uma dieta que reduza o número de
calorias, é necessário definir as quantidades de
alguns alimentos a serem ingeridos diariamente, de
modo que alguns pré-requisitos nutricionais sejam
satisfeitos a um custo mínimo.
Será definida uma dieta alimentar que esteja restrita
a suco, contrafilé e salada predefinida.
Os requisitos nutricionais devem ser demonstrados
segundo o tipo de vitaminas B, F e G e as
quantidades mínimas (em mg).
TABELA 2 – quantidade de cada vitamina nos alimentos e necessidade diária.
O modelo deve minimizar o custo de uma alimentação que equilibre as
quantidades ingeridas de cada alimento e as quantidades de vitaminas,
respeitando os limites mínimos.
FO: custo mínimo total para
consumo dos alimentos.
VARIÁVEIS DE DECISÃO
As restrições do problema são determinadas pelos requisitos nutricionais mínimos de
vitaminas que devem ser incluídas na dieta. Portanto, para este problema, as
restrições definidas são:
1) Restrição quanto ao consumo de vitamina B;
2) Restrição quanto ao consumo de vitamina F;
3) Restrição quanto ao consumo de vitamina G;
4) Restrição de não negatividade.
VIT. B
VIT. F
VIT. G
NÃO NEGATIVIDADE
A programação linear é uma atividade multidisciplinar da matemática aplicada que faz
a aplicação de modelos matemáticos à tomada de decisão. É empregada para análise
de sistemas complexos do mundo real, com a finalidade de melhorar ou otimizar o
desempenho. Sobre os exemplos de aplicação da programação linear, analise as
sentenças a seguir:
I- Planejamento de alocação de uma carga a ser transportada.
II- Otimizar recursos (humanos e materiais) internos de uma indústria com o propósito
de se reduzir custos.
III- Auditar a qualidade dos produtos em processo.
IV- A determinação do melhor local (em termos de custos de transporte e
movimentações) da instalação de uma planta industrial.
Assinale a alternativa CORRETA:
a) ( ) As sentenças I, II e III estão corretas.
b) ( ) As sentenças I e III estão corretas.
c) ( ) As sentenças I, II e IV estão corretas.
d) ( ) Somente a sentença II está corre
As variáveis de decisão exercem a função de apoio ao gestor, para que ele tenha
informações de decisão, de acordo com as informações que são possíveis de se
alcançar. Com relação aos exemplos de variável de decisão, analise as sentenças a
seguir:
I- Índice de não conformidade de peças, em uma produção têxtil.
II- Para um coordenador de produção na área têxtil é a quantidade de peças entregues
em uma planta industrial no período de um ano.
III- Uma empresa de comida canina produz dois tipos de rações, as variáveis de
decisão são as quantidades de ração de cada tipo a serem produzidas.
IV- Quantidade de peças a serem retrabalhadas, em função de erro de operação.
Assinale a alternativa CORRETA:
a) ( ) As sentenças II e III estão corretas.
b) ( ) As sentenças II e IV estão corretas.
c) ( ) As sentenças I, III e IV estão corretas.
d) ( ) Somente a sentença IV está correta.
TÓPICO 2
PROGRAMAÇÃO LINEAR
GEOMÉTRICA
1 INTRODUÇÃO
A programação linear define que um objetivo seja
alcançado com a alocação ótima dos recursos, por
isso ela é conhecida como uma técnica de
otimização.
Este tópico aborda a resolução gráfica de um PPL.
Esse método não pode ser visto como ferramenta
prática, pois é adequado somente para problemas
simples com duas variáveis de decisão.
TÓPICO 2
PROGRAMAÇÃO LINEAR
GEOMÉTRICA
2 SOLUÇÃO GEOMÉTRICA PARA 
PROBLEMAS DE
PROGRAMAÇÃO LINEAR
Cada questão é um caso especial do seguinte
problema:
Encontrar valores de X1 e X2 que maximizam, ou
minimizam a função objetivo.
Z variável de maximização/minimização.
TÓPICO 2
PROGRAMAÇÃO LINEAR
GEOMÉTRICA
2 SOLUÇÃO GEOMÉTRICA PARA 
PROBLEMAS DE
PROGRAMAÇÃO LINEAR
Para examinar a região viável de um Problema de
Programação Linear:
1. Observa-se que cada restrição;
2. Define uma reta no plano X1 e X2;
3. Define um semiplano que inclui a reta de
fronteira;
Assim, a região viável é sempre uma intersecção de
um número finito de retas e semiplanos.
TÓPICO 2
PROGRAMAÇÃO LINEAR
GEOMÉTRICA
3 APLICAÇÃO PRÁTICADA SOLUÇÃO 
GEOMÉTRICA
3.1 PROBLEMA DE COMPOSIÇÃO
Custo mínimo para o consumo dos
alimentos.
Custo Suco Qt de Suco
VIT. A
VIT. B
VIT. D
NÃO NEGATIVIDADE
3.2 SOLUÇÃO GRÁFICA
1)Representar a 1ª restrição usando a equação da reta:
Os pontos abaixo dessa reta correspondem à desigualdade≥ da restrição do PPL.
X=0 ; Y=5,5
Y=0 ; X=1,1
Para X=0
10*0 + 2*Xc =11
2*Xc = 11
Xc = 5,5 Para Y=0
10*Xs + 2*0 =11
10*Xs = 11
Xs = 1,1
(0 ; 5,5)
(1,1 ; 0)
2)Representar a 2ª restrição usando a equação da reta:
X=0 ; Y=3,5
Y=0 ; X=1,4
3)Representar a 3ª restrição usando a equação da reta:
X=0 ; Y= 1,43
Y=0 ; X= 2,86
3.2.1 Vetor Gradiente
Uma ferramenta importante na
busca da solução ótima é o vetor
gradiente da função objetivo,
que indica a direção do mínimo
custo.
A reta definida pelo esquadro
determina um único ponto que
fornece o mínimo custo para a
função objetivo.
Esse ponto é determinado pelo
encontro das equações das retas das
restrições 2 e 3.
Para descobri-lo, basta calcular o sistema de equações lineares:
Xs = (70 – 20Xc)/ 50
35* (70 – 20Xc)/ 50 +70Xc = 100
(2450 – 700Xc)/ 50 +70Xc = 100
49 – 14Xc + +70Xc = 100
– 14Xc + +70Xc = 100 -49
56 Xc = 51
Xc = 0,91 
Xs = (70 – 20*0,91)/50
Xs = (70 – 18,21) / 50
Xs = 51,79 / 50
Xs = 1,03
TÓPICO 3
ANÁLISE DE REDES
1 INTRODUÇÃO
A teoria dos grafos surgiu a partir do problema das
sete pontes de Koningsberga na Alemanha. Na
cidade passava um rio que a dividia em quatro
partes:
“é possível (passando só uma
vez por cada ponte) fazer um
caminho que passe por todas
elas?”
TÓPICO 3
ANÁLISE DE REDES
1 INTRODUÇÃO
O Caminho Euleriano,
é considerado como problema 
inicial da teoria dos grafos.
Viu-se a impossibilidade de traçar um caminho que passe só uma
vez por cada ponte e ao final tenha atravessado todas elas.
Mas se o número de pontes for, digamos, seis, existe a possibilidade
de realizar tal caminho.
TÓPICO 3
ANÁLISE DE REDES
2 DEFINIÇÕES SOBRE A TEORIA DOS 
GRAFOS
GRAFO: conjunto de nós ligados ou não por arcos.
A Figura 9 apresenta um grafo com cinco nós: A, B, C, D e E
os arcos, AB, AD, AC, AE, BD, DC e CE.
TÓPICO 3
ANÁLISE DE REDES
2 DEFINIÇÕES SOBRE A TEORIA DOS 
GRAFOS
• Um grafo é dito direto quando o fluxo ao longo de um
arco pode ser feito apenas em um sentido(mão única);
• Se o arco representar uma rua de mão dupla o grafo não
é direto;
• Um caminho é um conjunto de arcos que conectam dois
nós através de nós intermediários. Por exemplo ABDC,
que conecta os nós A e C, passando por B e por D
TÓPICO 3
ANÁLISE DE REDES
2 DEFINIÇÕES SOBRE A TEORIA DOS 
GRAFOS
• Um laço é um caminho que conecta um nó a ele mesmo.
TÓPICO 3
ANÁLISE DE REDES
2 DEFINIÇÕES SOBRE A TEORIA DOS 
GRAFOS
• Uma árvore é um grafo sem laços. Uma árvore tem n
arcos e n+1 nós
TÓPICO 3
ANÁLISE DE REDES
2.1 PROBLEMA DO CAIXEIRO 
VIAJANTE (PCV)
PRINCÍPIO: um vendedor deve visitar seus clientes em
cidades distintas, sem visitar duas vezes a mesma
cidade e sem deixar de visitar nenhum cliente.
Deve-se também considerar que esse vendedor
precisa fazer todas as visitas no menor percurso
possível, assim ganha tempo e reduz o cansaço com
as viagens.
TÓPICO 3
ANÁLISE DE REDES
2.1 PROBLEMA DO CAIXEIRO 
VIAJANTE (PCV)
Para ilustrar a aplicação dos conceitos relacionados
com o PCV:
tem-se a possibilidade de seis caminhos, que são:
ABCD, ABDC, ACBD, ACDB, ADBC e ADCB.
TÓPICO 3
ANÁLISE DE REDES
2.1 PROBLEMA DO CAIXEIRO 
VIAJANTE (PCV)
Se for calculada a distância para todos os caminhos,
têm-se:
ABCD = 45 km + 42 km + 36 km = 123 km
ABDC = 45 km + 29 km + 36 km = 110 km
ACBD = 38 km + 42 km + 29 km = 109 km
ACDB = 38 km + 36 km + 29 km = 103 km
ADBC = 31 km + 29 km + 42 km = 102 km
ADCB = 31 km + 36 km + 42 km = 109 km
TÓPICO 3
ANÁLISE DE REDES
2.1 PROBLEMA DO CAIXEIRO 
VIAJANTE (PCV)
A aplicação prática do PCV fica restrita à quantidade
de possibilidades, isto é, caminhos possíveis para
poucos nós.
Se problema tivesse 20 cidades, a quantidade de
possíveis caminhos seria de
“60.000.000.000.000.000”, ou seja, até o computador
levaria anos para encontrar o melhor caminho a ser
percorrido.
TÓPICO 3
ANÁLISE DE REDES
2.1 PROBLEMA DO CAIXEIRO 
VIAJANTE (PCV)
Utiliza-se a técnica do vizinho mais próximo.
Tem-se o caminho ADBC, que é o mesmo caminho
calculado anteriormente como sendo o melhor caminho
(Figura 17).
TÓPICO 3
LEITURA COMPLEMENTAR
MÉTODO DO CAMINHO CRÍTICO 
(CPM/PERT)
O Método do Caminho Crítico (Critical Path Method,
CPM) pode ser utilizada para gerenciar qualquer tipo
de projeto e até mesmo linhas de produção.
É utilizado em conjunto com o diagrama de redes
PERT (Program Evaluation and Review Technique),
organizando em conjunto as etapas do projeto para
visualizar melhor as atividades e encontrar o tempo
total de duração do projeto ou atividade.
TÓPICO 3
LEITURA COMPLEMENTAR
MÉTODO DO CAMINHO CRÍTICO 
(CPM/PERT)
Representa a execução do projeto utilizando o
diagrama de redes para mostrar a ligação e
dependência das tarefas.
Para fazer isso, a metodologia utiliza os seguintes
símbolos:
Tarefas a serem executadas.
Atividade imaginária: mostra a
Dependência das atividades.
“nós” e simbolizam a transição
entre as tarefas
• 6 tarefas;
• 2 caminhos;
• Tarefa E depende da B e da C.
O QUE É CAMINHO CRÍTICO?
Sequência que leva mais tempo para ser finalizada, indicando o tempo máximo que
um projeto levará.
Caminho 1 = 16d
Caminho 2 = 14d
• 6 tarefas;
• 2 caminhos;
• Atividade E depende da B e
da C.
• FOLGA (C e E = 2d)
*Não deve haver atraso nas
atividades do CAMINHO
CRÍTICO.
Os Problemas de Programação Linear (PPL)
geralmente são problemas que visam à
maximização ou à minimização de uma função
linear, levando as variáveis em consideração. Assim
sendo, considere o caso da empresa BRAPP, em
que o objetivo é minimizar o custo de fabricação
dos produtos A e B, cuja receita da venda do
produto A é de R$ 12,00 e a receita com a venda
de B é R$ 18,00. Os custos de produção do produto
A é igual a R$ 9,00, e do produto B é igual a R$
14,00. Assim, qual é a função custo desse produto?
a) Min C = 9A + 14B.
b) Max L = 3A + 4B.
c) Min L = 12A + 14B.
d) Max R = 21A + 32
EXERCITANDO O CONHECIMENTO
Uma fábrica de móveis tem em estoque 500 m de tábuas, 300 m
de pranchas e 200 m de painéis de MDF. A fábrica disponibiliza
uma linha de móveis com os seguintes produtos: carteira escolar,
mesa, estante e prateleira. Cada móvel necessita de uma
quantidade de material. A carteira é vendida por R$ 110,00, a
mesa por R$ 90,00, a estante por R$ 100,00 e a prateleira por R$
30,00. Nesse caso, a fábrica tem como meta atingir o máximo de
lucro possível com a venda de seus produtos, pois o
mercado consome todo o produto que é colocado para venda.
Com relação às
restrições que podem ser desenvolvidas para esse problema,
analise as sentenças a
seguir:
I- Restrição quanto ao uso de tábuas.
II- Restrição quanto ao uso de pranchas.
III- Restrição quanto ao uso de carteiras.
Assinale a alternativa CORRETA:
a) As sentenças I e II estão corretas.
b) Somente a sentença I está correta.
c) As sentenças II e III estão corretas.
d) Somente a sentença II está correta
EXERCITANDO O CONHECIMENTO
EXERCITANDO O CONHECIMENTO
EXERCITANDO O CONHECIMENTO
A Carro S/A fabrica três modelos de automóveis: modelos 1.0, 1.6 e 2.0. Devido a
questões trabalhistas, é possível que ocorra uma greve na fábrica "A" em breve.
Considerando essa situação, a direção preparou um Plano Especial de Produção, no
qual se considera que não haverá produção na fábrica "A" durante o período.
Neste período, a capacidade da fábrica "B" será de 4.000 unidades de 1.0, ou 3.000
unidades de 1.6, ou 2.000 unidades de 2.0, ou qualquer combinação possível dos
três modelos. Uma combinação possível pode ser 2.000 unidades de 1.0, 900
unidades de 1.6 e 400 unidades de 2.0 (50%, 30% e 20% da capacidade, que
somam 100%). A fábrica "C" possui a capacidade: 3.000 unidades de 1.0, ou 8.000
unidades de 1.6, ou qualquer combinação possível destes modelos.O modelo 2.0
não é produzido pela fábrica "C". Cada automóvel 1.0 é vendido a 11.500 u.m.,
cada modelo 1.6 é vendido por 14.500 u.m. e cada modelo 2.0 é vendido a 18.000
u.m. O custo de produção da fábrica "B" para produzir os modelos 1.0, 1.6 e 2.0 é
de 8.750 u.m., 12.000 e 14.500, respectivamente. O custo de produção da fábrica
"C" é de 9.000 u.m. e 11.0000 u.m. para os modelos 1.0 e 1.6, respectivamente. A
empresa possui contratos que a obrigam a fornecer 1.000 unidades do modelo 2.0.
A empresa estima uma venda máxima dos modelos 1.0 e 1.6 em 1.000 e 2.500
unidades, respectivamente. O modelo 1.6 é atualmente o mais vendido, portanto,
não há limites para suas vendas. No início do período considerado, o estoque dos 3
modelos é de 200 unidades do modelo 1.0, 600 unidades do 1.6 e 200 unidades do
2.0. Adicionalmente, é possível que a empresa importe da Europa até 500 unidades
do modelo 1.0, sendo que cada unidade importada possui um custo de 10.000
u.m. Considerando o exposto, formule uma função objetivo para este problema,
considerando que o objetivo da empresa é maximizar lucros.
EXERCITANDO O CONHECIMENTO
Variáveis de decisão:
X1 - Unidades do modelo 1.0 produzidos na fábrica "B".
X2 - Unidades do modelo 1.6 produzidos na fábrica "B".
X3 - Unidades do modelo 2.0 produzidos na fábrica "B".
X4 - Unidades do modelo 1.0 produzidos na fábrica "C".
X5 - Unidades do modelo 1.6 produzidos na fábrica "C".
X6 - Unidades do modelo 1.0 importados da Europa.
Lucro = receitas – custos
MAX_Z = (11.500 - 8.750)X1 + (14.500 - 12.000)X2 + 
(18.000 - 14.500)X3 + (11.500 - 9.000)X4 + (14.500 -
11.000)X5 + (11.500 - 10.000)X6
MAX_Z = 2.750 X1 + 2.500 X2 + 3.500 X3 + 2.500 X4 + 
3.500 X5 + 1.500 X6
FIM DA 
UNIDADE 2
RESOLVENDO PPL 
NO EXCEL
Não Negatividade
FIM DA UNIDADE 2