Exemplos de Modelagem de Problemas de Programação Linear

Prévia do material em texto

Exemplos práticos sobre construção de do modelo de P.L 
Exemplo 1: ( problema de maximo ) 
Um alfaiate tem, disponivel os seguintes tecidos: 16𝑚2 de algodão, 11𝑚2 de sêda e 
15𝑚2 de lã. Para um terno são necessários 2𝑚2 de algodão e 1𝑚2 de sêda e 1𝑚2 de lã. 
Para um vestido, são necessários 1𝑚2 de algodão, 2𝑚2 de sêda e 3𝑚2 de lã. Se um terno 
um é vendido por 300kz e um vestido por 500kz, quantas peças de cada tipo o alfaiate 
deve fazer, de modo a obter lucro maximo? 
A tabela seguinte resume os fatos acima: 
 Terno Vestido Disponível 
Algodão 2 1 16 
Sêda 1 2 11 
Lã 1 3 15 
Preço 300kz 500kz 
Para a modelagem, precisamos responder três peguntas importantes: 
a)Quais são as variaveis de decisão? 
b)Qual é o objetivo? O que queremos maximizar (ou minimizar )? 
c)Quais são as restricões? 
Formulação do modelo matemático: 
a)X o número de ternos 
Y o número de vestidos que o alfaiate deve fazer 
Queremos maximizar 
b)𝑧 = 300𝑥 + 500𝑦 : função económica 
c) 
𝑆𝑢𝑗𝑒𝑖𝑡𝑎 𝑎
{
 
 
 
 
2𝑥 + 𝑦 ≤ 16
𝑥 + 2𝑦 ≤ 11
𝑥 + 3𝑦 ≤ 15
𝑥 ≥ 0
𝑦 ≥ 0
 
 
 
 
 
 
 
 
Restrições limitações 
Condição de não negatividade 
𝑥1 + 2𝑥2 = 9 
Exemplo 2: (Problema do mínimo) 
Uma pessoa precisa de 10, 12, e 12 unidades dos produtos químicos A, B e C, 
respetivamente, para o seu jardim. Um produtor liquido contem 5, 2 e 1 unidades de A, 
B e C, respetivamente, por vidro; um produto em pó contem 1, 2 e 4 unidades de A, B e 
C, respetivamente, por caixa. Se o produto liquido custar $3 por vidro e o produto em pó 
custar $2 por caixa; quantos vidros e quantas caixas ele deve comprar para minimizar o 
custo e satisfazer as necessidades? 
A seguinte tabela resume os fatos acima: 
 Unidade por vidro Unidade por caixa Unidade necessária 
Produto A 5 1 10 
Produto B 2 2 12 
Produto C 1 4 12 
Preço $3 $2 
Formulação do modelo matemático: 
a)X número minimo de vidros 
Y número de caixa. 
b)Queremos minimizar a função 
𝑍 = 3𝑥 + 2𝑦 
c)𝑆𝑢𝑗𝑒𝑖𝑡𝑎 𝑎 {
5𝑥 + 𝑦 ≥ 10
2𝑥 + 2𝑦 ≥ 12
𝑥 + 4𝑦 ≥ 12
𝑥 ≥ 0; 𝑦 ≥ 0
 
Resolução grafica de problemas de P.L 
 Os problemas de P.L relacionam-se com a determinação do maximo ou do mínimo de 
uma função lienear 𝑓(𝑥1, 𝑥2, … 𝑥𝑛) = 𝑐1𝑥1 + 𝑐2𝑥2 +⋯+ 𝑐𝑛𝑥𝑛 denominada função 
objectiva, sobre um conjunto convexo poliédro X, que inclui a condição de que as 
incógnitas (variáveis sejam não-negativas: 𝑥1 ≥ 0, 𝑥2 ≥ 0,..., 𝑥𝑛 ≥ 0. 
Cada ponto de X é denominado uma solução do problema e um ponto X no qual 𝑓 assume 
seu máximo (ou mínimo) é denominado uma solução óptima. 
Exemplo: 
a)Max 𝑧 = 5𝑥1 + 2𝑥2 
𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎: {
𝑥1 ≤ 3
𝑥2 ≤ 4
𝑥1 + 2𝑥2 ≤ 9
𝑥1 ≥ 0, 𝑥2 ≥ 0
 
 
 
Conjunto de solução viável. 
𝑥2 
𝑥1 = 3 
𝑥2 = 4 
𝑥1 
3 A 
Solução 
viável 
C 
D 
4 
21 = 5𝑥1 + 2𝑥2 
B 
E 
9 
Os vertices são: 
A(0,0) B(3,0) C(3,3) D(1,4) e E(0, 4) 
Assim, termos: 
(𝑥1, 𝑥2) 5𝑥1 + 2𝑥2 Z 
A(0,0) 5 × 0 + 2 × 0 0 
B(3,0) 5 × 3 + 2 × 0 15 
C(3,3) 5 × 3 + 2 × 3 21 
D(1,4) 5 × 1 + 2 × 4 13 
E(0, 4) 5 × 0 + 2 × 4 8 
Neste caso, o maximo valor de Z é igual a 21, numa solução óptima de 𝑥1 = 3 e 𝑥2 = 3. 
Para 𝑍 = 21, a função-objectivo 𝑧 = 5𝑥1 + 2𝑥2, é uma equação de reta que passa pela 
solução óptima. 
Exercícios propostos (trabalho em grupo ) 
1-A empresa DIRUP produz tintas interiores e exteriores apartir de duas matérias-primas 
MP1 e MP2. A tabela a seguir representa os dados do problema 
 Tabela de MP / Ton de Tintas Disponibilidade por dia Ton 
 Exterior Interior 
MP1 6 4 24 
MP2 1 2 6 
Lucro/ Ton 5 4 
A procura diária para a tinta interior não pode exceder a de tinta exterior em 1 tonelada. 
A procura diária máxima de tintas interior é de 2 toneladas. A DIRUP pretende determinar 
as quantidades de cada tipo de tintas a produzir, de modo a ter o maior lucro possivel. 
Determine a formulação matemática do problema. 
2-A GAP utiliza pelo menos 800kg de ração diariamente. A ração é uma mistura de 
Popcorn e Soja, com a seguinte composição: 
Ingredientes Kg de ingredientes Custos ( $ ) 
Proteinas Fibras 
Popcorn 0,09 0,02 0,3 
Soja 0,6 0,06 0,9 
A ração deve conter pelo menos 30% de proteínas e não mais de 5% de fibras. 
Preende-se determinar o custo diário mínimo para a obtenção de ração. 
Determine a formulação matemática do problema. 
3-Uma empresa quer utilizar anúcios para divulgar a sua nova linha de produtos, com o 
objetivo de atingir a maior quantidade de pessoas. Um anúncio na estação de rádio local 
custa 1.000.00kz o minuto e atinge 5mil pessoas. 
Um anúcio na estação de televisão local custa 5.000.00kz o minuto e atinge 30mil 
pessoas. A verba para propaganda é de 50.000.00kz. O diretor da empresa exigiu que a 
soma do tempo total dos anúncio (na radio e na televisão) seja de pelo menos 15minutos. 
Encontre o modelo de P.L do problema. 
4-Uma empresa fabrica dois tipos de produtos: 𝑃1 e 𝑃2 para realizar a fabricação esses 
produtos consimem tempo nos departamentos A e B. 
𝑃1 necessita de 1 hora no departamento A e 3 horas no departamento B. 𝑃2 necessita de 
1hora no departamento A e de 2horas no departamento B. A capacidade do departamento 
A é de 100 horas e a capacidade do departamento B é de 240 horas. A demanda por 𝑃1 é 
de 60 unidades e a demanda por 𝑃2 é de 80 unidades. Alem disso o preço de 𝑃1 é de 
600.00kz por unidade e opreço do 𝑃2 é de 800.00kz por unidade. O objetivo é maximizar 
receitas, Encontre o modelo de P.L do problema. 
 
 5-Seja o P.L seguintes, a sua resolução grafica é: 
a)Min 𝑍 = 7𝑥1 + 9𝑥2 
𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎
{
 
 
 
 
−𝑥1 + 𝑥2 ≤ 2
𝑥1 ≤ 5
𝑥2 ≤ 6
3𝑥1 + 5𝑥2 ≤ 15
5𝑥1 + 4𝑥2 ≥ 20
𝑥1 ≥ 0 , 𝑥2 ≥ 0
 
b)Min 𝑍 = 6𝑥1 + 10𝑥2 
𝑆𝑢𝑗𝑒𝑖𝑡𝑎 𝑎
{
 
 
 
 
−𝑥1 + 𝑥2 ≤ 2
𝑥1 + 2𝑥2 ≥ 1
𝑥1 ≤ 5
𝑥2 ≤ 6
3𝑥1 + 5𝑥2 ≤ 15
5𝑥1 + 4𝑥2 ≥ 20
𝑥1 ≥ 0 , 𝑥2 ≥ 0