Teoria de Decisão I

AULA 2: MODELAGEM MATEMÁTICA DE PROBLEMAS LINEARES

Profa. Luciane Alcoforado

PPGEC/UFF

Objetivos

Verifique ao final desta aula se você é capaz de:

1- Identificar os modelos clássicos de programação linear (Cp).

2- Formular modelos de programação linear (Ap).

3- Gerar soluções para as situações problema apresentadas (Ap).

4- Validar os modelos elaborados por meio da análise das soluções obtidas (An).

Roteiro da Aula

  • Modelos clássicos de mistura.
  • Interpretando a solução.
  • Exercícios.
  • Modelos clássicos de transporte.
  • Interpretando a solução.
  • Exercícios.

Revisão de conceitos

Escolha a alternativa correta

1- O que é modelagem matemática?

  1. O uso de fórmulas matemáticas complexas para resolver problemas militares.

  2. O processo de criação de um modelo matemático para explicar fenômenos naturais.

  3. A representação exata da realidade em um modelo matemático.

  4. A aplicação de incertezas nos modelos matemáticos.

2- Quais são as hipóteses de linearidade na programação linear?

  1. Proporcionalidade, aditividade, certeza e fracionamento.

  2. Variabilidade, complexidade, certeza e fracionamento.

  3. Proporcionalidade, aditividade, incerteza e continuidade.

  4. Variabilidade, complexidade, certeza e continuidade.

Verifique seus acertos

1- O que é modelagem matemática?

  1. O processo de criação de um modelo matemático para explicar fenômenos naturais.

2- Quais são as hipóteses de linearidade na programação linear?

  1. Proporcionalidade, aditividade, certeza e fracionamento.

Escolha a alternativa correta

3- Quais são os elementos de um modelo completo de otimização linear?

  1. Função objetivo, variáveis aleatórias, incertezas e restrições de sinal.

  2. Variáveis de decisão, probabilidade, função objetivo e restrições estruturais.

  3. Critério de otimalidade, variáveis de decisão, função objetivo e restrições lineares.

  4. Restrições de sinal, incertezas, critério de otimalidade e função de custo.

4- Qual é a finalidade do equilíbrio na modelagem matemática?

  1. Alcançar a perfeita aderência à realidade.

  2. Reduzir o alcance de aplicação da representação realizada.

  3. Encontrar um ponto intermediário entre simplificação e representação detalhada.

  4. Evitar a necessidade de utilizar modelos matemáticos na tomada de decisões.

Verifique seus acertos

3- Quais são os elementos de um modelo completo de otimização linear?

  1. Critério de otimalidade, variáveis de decisão, função objetivo e restrições lineares.

4- Qual é a finalidade do equilíbrio na modelagem matemática?

  1. Encontrar um ponto intermediário entre simplificação e representação detalhada.

Exemplos aplicados a diversos contextos

Veremos nesta aula modelos relacionados ao problema clássico da mistura.

A lógica por trás do problema de modelagem clássica de mistura consiste em encontrar a combinação ideal de ingredientes ou componentes para criar uma mistura que atenda a determinados critérios ou restrições, através da formulação de um modelo matemático e utilização de técnicas de otimização para encontrar a solução ótima.

Formulação de uma ração:

Suponha que seja necessário criar 1 kg de ração que minimize seu custo total, utilizando uma mistura com alguns ingredientes disponíveis.

A ração produzida deve atender aos seguintes requisitos nutricionais mínimos em cada 1 kg:

  • Proteínas: no mínimo 250 gramas
  • Carboidratos: no mínimo 50 gramas
  • Gorduras: no mínimo 10 gramas
  • Vitaminas: no mínimo 500 unidades internacionais (UI)
  • Minerais: no mínimo 10 gramas

Os ingredientes disponíveis para a ração, bem como seus custos por kg e a composição nutricional para cada kg de produto são:

  • Farinha de carne (R$25,00/Kg): fornece 300 gramas de proteínas, 50 gramas de carboidratos, 150 gramas de gorduras, 5000 UI de vitaminas e 50 gramas de minerais por Kg.
  • Grãos de cereais (R$20,00/Kg): fornecem 100 gramas de proteínas, 400 gramas de carboidratos, 50 gramas de gorduras, 2000 UI de vitaminas e 20 grama de minerais por Kg.
  • Óleo vegetal (R$8,50/Kg): fornece 0 gramas de proteínas, 0 gramas de carboidratos, 200 gramas de gorduras, 0 UI de vitaminas e 0 gramas de minerais por Kg.

Elementos da modelagem:

Critério de Otimalidade: Minimizar o custo da ração

Definição das variáveis de decisão:

x1: quantidade de farinha de carne na ração (em Kg)

x2: quantidade de grãos de cereais na ração (em Kg)

x3: quantidade de óleo vegetal na ração (em Kg)

Função Objetivo:

min \(25x_1 + 20x_2+ 8.5x_3\)

Restrições Lineares:

Sujeito a:

Restrições Estruturais

\[\begin{gather*} 300x_1 + 100x_2 + 0x_3 \space \ge \space 250 \space (R1:\space Restrição \space de \space proteína)\\ 50x_1 + 400x_2 + 0x_3 \space \ge \space 50 \space (R2:\space Restrição \space de \space carboidrato)\\ 150x_1 + 50x_2 + 200x_3 \space \ge \space 10 \space (R3:\space Restrição \space de \space gordura)\\ 5000x_1 + 2000x_2 + 0x_3 \space \ge \space 500 \space (R4:\space Restrição \space de \space vitaminas)\\ 50x_1 + 20x_2 + 0x_3 \space \ge \space 10 \space (R5:\space Restrição \space de \space minerais)\\ 1x_1 + 1x_2 + 1x_3 \space = \space 1 \space (R6:\space Restrição \space de \space quantidade \space de \space ração \space produzida)\\ \end{gather*}\]

Restrições de Sinal

\(x_i \ge 0, \space \forall i=1,2,3\)

Obtendo a resposta do modelo

library(lpSolve) #precisa instalar o pacote caso não tenha
coef.objetivo = c(25,20,8.5)
R1 = c(300, 100, 0)
R2 = c(50, 400, 0)
R3 = c(150, 50, 200)
R4 = c(5000, 2000, 0)
R5 = c(50, 20, 0)
R6 = c(1, 1, 1)
restricoes = rbind(R1,R2,R3,R4,R5, R6)
b = c(250, 50, 10, 500, 10, 1)
sinal = c(">=",">=",">=",">=",">=", "=")
solucao = lpSolve::lp(direction = "min",
                      objective.in = coef.objetivo,
                      const.mat = restricoes,
                      const.dir = sinal,
                      const.rhs = b,
                      all.int = F)
solucao
Success: the objective function is 22.38043 
solucao$solution
[1] 0.82608696 0.02173913 0.15217391

Interpretando a solução

O modelo indica que deve ser produzido 1 kg de ração a um custo de R$22.38 misturando 0.826 kg de farinha de carne, 0.022 kg de grãos de cereais e 0.152 kg de óleo vegetal.

Observe que a solução apresenta exatamente um kg de ração resultado da soma de 0.826+0.022+0.152. Observe que o custo de R$22.38 é obtido multiplicando-se \(25\cdot 0.826 + 20\cdot 0.022 + 8.5 \cdot 0.152\)

Verifique a quantidade de proteínas, carboidratos, gorduras, vitaminas e minerais presentes na ração produzida a partir desta solução. Certifique-se de que todas as restrições foram atendidas.

Desafio:

1- Mude o código em R no argumento all.int = F para all.int = T e compare o resultado obtido com fornecido nesta solução.

2- Elimine a restrição de produzir 1 kg de ração e rode novamente o modelo, qual a quantidade produzida de ração? O que aconteceu com o seu custo?

Resposta do Desafio 1 all.int = T

A solução antes da mudança era:

Success: the objective function is 22.38043 
[1] 0.82608696 0.02173913 0.15217391
solucao = lpSolve::lp(direction = "min",
                      objective.in = coef.objetivo,
                      const.mat = restricoes,
                      const.dir = sinal,
                      const.rhs = b,
                      all.int = T)
solucao
Success: the objective function is 25 
solucao$solution
[1] 1 0 0

Observamos que houve um aumento no custo da ração que agora contém 1 kg de farinha de carne. Ao mudarmos para all.int = T mudamos a hipótese de fracionamento, agora só podemos ter soluções inteiras, desse modo, o conjunto de soluções possíveis ficou mais restrito, aumentando o custo total.

Resposta do Desafio 2 - Eliminar R6

library(lpSolve) #precisa instalar o pacote caso não tenha
coef.objetivo = c(25,20,8.5)
R1 = c(300, 100, 0)
R2 = c(50, 400, 0)
R3 = c(150, 50, 200)
R4 = c(5000, 2000, 0)
R5 = c(50, 20, 0)
#R6 = c(1, 1, 1) eliminando esta restrição
restricoes = rbind(R1,R2,R3,R4,R5) #sem R6
b = c(250, 50, 10, 500, 10) #sem 1
sinal = c(">=",">=",">=",">=",">=") #sem =
solucao = lpSolve::lp(direction = "min",
                      objective.in = coef.objetivo,
                      const.mat = restricoes,
                      const.dir = sinal,
                      const.rhs = b,
                      all.int = F)
solucao
Success: the objective function is 21.08696 
solucao$solution
[1] 0.82608696 0.02173913 0.00000000

Agora reduzimos o custo para R$ 21.09, porém esta solução reduz a quantidade de ração produzida para 0.8478261 kg e não inclui o ingrediente 3 (óleo vegetal).

Revisão de conceitos

Escolha a alternativa correta

1- Qual das alternativas a seguir viola a hipótese de aditividade na programação linear?

  1. A produção total de uma fábrica é igual à soma das produções de cada setor.

  2. O lucro total de uma empresa é igual à soma dos lucros de cada produto.

  3. O custo total de um projeto é igual à soma dos custos de cada atividade.

  4. A demanda total de um mercado é igual à soma das demandas de cada segmento.

  5. O tempo total de um projeto é igual à soma dos tempos de cada atividade do projeto.

Escolha a alternativa correta

2- Qual das alternativas a seguir NÃO viola a hipótese de certeza na programação linear?

  1. Os parâmetros do modelo são estimados com base em dados históricos e podem variar de acordo com a situação.

  2. Os coeficientes da função objetivo e das restrições são constantes e conhecidos com precisão.

  3. Os recursos disponíveis para o problema são aleatórios e dependem de fatores externos como clima, demanda ou concorrência.

  4. A demanda pelos produtos é desconhecida e varia de acordo com o preço, a qualidade e a propaganda.

  5. O custo unitário de cada produto é aleatório e segue uma distribuição normal com média e desvio padrão conhecidos.

Verifique seus acertos

1- Qual das alternativas a seguir viola a hipótese de aditividade na programação linear?

  1. O tempo total de um projeto é igual à soma dos tempos de cada atividade do projeto.

A alternativa correta é a letra e, pois o tempo total de um projeto não é necessariamente igual à soma dos tempos de cada atividade, dependendo do projeto podem ocorrer atividades executadas em paralelo e portanto seu tempo não será somado.

2- Qual das alternativas a seguir NÃO viola a hipótese de certeza na programação linear?

  1. Os coeficientes da função objetivo e das restrições são constantes e conhecidos com precisão.

A alternativa b é a única que não viola a hipótese de certeza na programação linear, pois os coeficientes da função objetivo e das restrições são constantes e conhecidos com precisão, o que significa que não há incerteza ou aleatoriedade nos elementos do modelo. As demais alternativas violam a hipótese de certeza, pois os parâmetros do modelo, os recursos disponíveis, a demanda pelos produtos e o custo unitário de cada produto são estimados, aleatórios ou variáveis, o que significa que há incerteza ou aleatoriedade nos elementos do modelo.

Escolha a alternativa correta

3- Uma empresa produz dois tipos de produtos, A e B, que geram um lucro de R$ 10,00 e R$ 15,00 por unidade, respectivamente. A empresa dispõe de 200 horas de mão de obra e 300 kg de matéria-prima por semana. Cada unidade de A consome 2 horas de mão de obra e 3 kg de matéria-prima, enquanto cada unidade de B consome 3 horas de mão de obra e 4 kg de matéria-prima. A empresa deseja maximizar o seu lucro semanal com a produção dos produtos. O problema pode ser modelado como um problema de programação linear. Como deve ser definida a variável de decisão deste problema?

  1. \(x_i\) = número de horas de mão de obra para o produto \(i=A,B\)

  2. \(x_i\) = lucro obtido pela venda do produto \(i=A,B\)

  3. \(x_i\) = número de unidades do produto \(i=A,B\) produzidas por semana

  4. \(x_i\) = quantidade de matéria-prima para o produto \(i=A,B\)

  5. \(x_i\) = preço do produto \(i=A,B\) no mercado

Escolha a alternativa correta

4- Uma empresa produz dois tipos de produtos, A e B, que geram um lucro de R$ 10,00 e R$ 15,00 por unidade, respectivamente. A empresa dispõe de 200 horas de mão de obra e 300 kg de matéria-prima por semana. Cada unidade de A consome 2 horas de mão de obra e 3 kg de matéria-prima, enquanto cada unidade de B consome 3 horas de mão de obra e 4 kg de matéria-prima. A empresa deseja maximizar o seu lucro semanal com a produção dos produtos. O problema pode ser modelado como um problema de programação linear, onde x = número de unidades de A produzidas por semana e y = número de unidades de B produzidas por semana. Como deve ser escrita a função objetivo deste problema?

  1. max Z = 2x + 3y

  2. min Z = 10x + 15y

  3. min Z = 2x + 3y

  4. max Z = x + y

  5. max Z = 10x + 15y

Verifique seus acertos

3- Como deve ser definida a variável de decisão deste problema?

  1. \(x_i\) = número de unidades do produto \(i=A,B\) produzidas por semana

Pois é a variável que representa a decisão que a empresa deve tomar para maximizar o seu lucro, considerando as restrições do problema. As demais alternativas não são variáveis de decisão, mas sim dados, parâmetros ou resultados do problema.

4- Como deve ser escrita a função objetivo deste problema?

  1. max Z = 10x + 15y

Pois é a expressão que representa o valor máximo do lucro que a empresa pode obter com a produção dos produtos, considerando os lucros unitários de cada produto. As demais alternativas não são funções objetivo adequadas, pois ou têm o sinal errado (min em vez de max), ou têm os coeficientes errados (2 e 3 em vez de 10 e 15), ou não consideram os lucros unitários (x + y).

Exemplos aplicados a diversos contextos

Veremos nesta aula modelos relacionados ao problema clássico de transportes.

A lógica por trás do problema de modelagem clássica de transporte consiste em encontrar a alocação ideal de um produto ou recurso entre um conjunto de origens e um conjunto de destinos, de forma a minimizar o custo total do transporte, respeitando as capacidades das origens e as demandas dos destinos, através da formulação de um modelo matemático e utilização de técnicas de otimização para encontrar a solução ótima.

Rede:

A rede do problema de transporte é uma representação gráfica do problema, que facilita a visualização das origens, dos destinos, das quantidades transportadas e dos custos unitários.

G O1 O1 D1 D1 O1->D1 D2 D2 O1->D2 Dm Dm O1->Dm O2 O2 O2->D1 O2->D2 O2->Dm On On On->D1 On->D2 On->Dm

Formulação de um problema de transporte no contexto de engenharia:

Uma concreteira possui 8 caminhões betonera do Tipo 1, 15 caminhões do Tipo 2 e 11 caminhões do Tipo 3 disponíveis para envio de concreto. A capacidade de cada tipo de caminhão é de 10t, 7t e 5t, respectivamente.

O responsável pelas operações de envio do concretodeve enviar caminhões carregadas para as cidades A1, A2 e A3. A quantidade mínima que deve ser enviada para cada cidade é de 20t, 28t e 30t, respectivamente. Cada caminhão pode realizar somente uma viagem por dia.

Formule o modelo de otimização linear a fim de minimizar o custo do transporte de concreto.

Rede do problema

flowchart LR
T1(("T1
8, 10t")) ---> |c11=23|A1(("A1
20t"))
T1 ---> |c12=58| A2(("A2
28t"))
T1 ---> |c13=64|A3(("A3
30t"))
T2(("T2
15, 7t")) --> |c21=15| A1 
T2 ---> |c22=20|A2 
T2 ---> |c23=24|A3 
T3(("T3
11, 5t")) ---> |c31=1.4|A1 
T3 ---> |c32=3.8|A2
T3 ---> |c33=4.2|A3

O custo (em u.m.) de enviar um caminhão do tipo Ti a cada cidade Aj está representado na rede por \(c_{ij}\)

Elementos da modelagem:

Critério de Otimalidade: Minimizar o custo do transporte de concreto.

Definição das variáveis de decisão:

\(x_{ij}\): número de viagens do caminhão do tipo \(T_i\) enviado para a cidade \(A_j\), \(i=1,2,3\) e \(j=1,2,3\)

Função Objetivo:

min \(z=23x_{11} + 58x_{12} +64x_{13} + 15x_{21} + 20x_{22} +24x_{23} + 1.4x_{31} + 3.8x_{32} +4.2x_{33}\)

Elementos da modelagem…:

Hipótese simplificadora: os caminhões utilizam a totalidade da sua capacidade de carga, ou seja, T1, T2 e T3 carregam respectivamente 10 ton, 7 ton e 5 ton em cada viagem.

Restrições Estruturais

  • Oferta de viagens
\[\begin{gather*} x_{11} + x_{12} + x_{13} \space \le \space 8 \space (Oferta \space de \space viagem \space T1)\\ x_{21} + x_{22} + x_{23} \space \le \space 15 \space (Oferta \space de \space viagem \space T2)\\ x_{31} + x_{32} + x_{33} \space \le \space 11 \space (Oferta \space de \space viagem \space T3)\\ \end{gather*}\]

Elementos da modelagem…:

  • Necessidade das cidades
\[\begin{gather*} 10x_{11} + 7x_{21} + 5x_{31} \space \ge \space 20 \space (Demanda \space da \space cidade \space A1)\\ 10x_{12} + 7x_{22} + 5x_{32} \space \ge \space 28 \space (Demanda \space da \space cidade \space A2)\\ 10x_{13} + 7x_{23} + 5x_{33} \space \ge \space 30 \space (Demanda \space da \space cidade \space A3)\\ \end{gather*}\]

Restrições de Sinal

\(x_{ij} \ge 0, \space \forall i,j=1,2,3\)

O modelo completo

\(x_{ij}\): número de viagens do caminhão do tipo \(T_i\) enviado para a cidade \(A_j\), \(i=1,2,3\) e \(j=1,2,3\)

min \(z=23x_{11} + 58x_{12} +64x_{13} + 15x_{21} + 20x_{22} +24x_{23} + 1.4x_{31} + 3.8x_{32} +4.2x_{33}\)

sujeito a

\[\begin{gather*} x_{11} + x_{12} + x_{13} \space \le \space 8 \space (Oferta \space de \space viagem \space T1)\\ x_{21} + x_{22} + x_{23} \space \le \space 15 \space (Oferta \space de \space viagem \space T2)\\ x_{31} + x_{32} + x_{33} \space \le \space 11 \space (Oferta \space de \space viagem \space T3)\\ \end{gather*}\] \[\begin{gather*} 10x_{11} + 7x_{21} + 5x_{31} \space \ge \space 20 \space (Demanda \space da \space cidade \space A1)\\ 10x_{12} + 7x_{22} + 5x_{32} \space \ge \space 28 \space (Demanda \space da \space cidade \space A2)\\ 10x_{13} + 7x_{23} + 5x_{33} \space \ge \space 30 \space (Demanda \space da \space cidade \space A3)\\ \end{gather*}\]

\(x_{ij} \ge 0, \space \forall i,j=1,2,3\)

O modelo completo com todos os coeficientes

\(x_{ij}\): número de viagens do caminhão do tipo \(T_i\) enviado para a cidade \(A_j\), \(i=1,2,3\) e \(j=1,2,3\)

\[\begin{gather*} \small \textbf{min} \space z = 23x_{11} + 58x_{12} + 64x_{13} + 15x_{21} + 20x_{22} + 24x_{23}+ 1.4x_{31} + 3.8x_{32} + 4.2x_{33} \end{gather*}\]

sujeito a

\[\begin{gather*} \small 1x_{11} + 1x_{12} + 1x_{13} + 0x_{21} + 0x_{22} + 0x_{23} + 0x_{31} + 0x_{32} + 0x_{33} \space \le \space 8 \space (R1)\\ \small 0x_{11} + 0x_{12} + 0x_{13}+1x_{21} + 1x_{22} + 1x_{23} + 0x_{31} + 0x_{32} + 0x_{33} \space \le \space 15 \space (R2)\\ \small 0x_{11} + 0x_{12} + 0x_{13}+x_{21} + 0x_{22} + 0x_{23} +1x_{31} + 1x_{32} + 1x_{33} \space \le \space 11 \space (R3)\\ \end{gather*}\] \[\begin{gather*} \small 10x_{11} + 0x_{12} + 0x_{13}+ 7x_{21} + 0x_{22} + 0x_{23} + 5x_{31} + 0x_{32} + 0x_{33} \space \ge \space 20 \space (R4)\\ \small 0x_{11}+ 10x_{12} + 0x_{13}+ 0x_{21} + 7x_{22} + 0x_{23} + 0x_{31} + 5x_{32} + 0x_{33} \space \ge \space 28 \space (R5)\\ \small 0x_{11} +0x_{12} +10x_{13} + 0x_{21} + 0x_{22} + 7x_{23} + 0x_{31}+0x_{32} + 5x_{33} \space \ge \space 30 \space (R6)\\ \end{gather*}\]

\(x_{ij} \ge 0, \space \forall i,j=1,2,3\)

Obtendo a resposta do modelo

library(lpSolve) #precisa instalar o pacote caso não tenha
coef.objetivo = c(23,58, 64, 15, 20, 24, 1.4, 3.8, 4.2)
R1 = c(1,1,1,0,0,0,0,0,0)
R2 = c(0,0,0,1,1,1,0,0,0)
R3 = c(0,0,0,0,0,0,1,1,1)
R4 = c(10,0,0,7,0,0,5,0,0)
R5 = c(0,10,0,0,7,0,0,5,0)
R6 = c(0,0,10,0,0,7,0,0,5)
restricoes = rbind(R1,R2,R3,R4,R5, R6)
b = c(8, 15, 11, 20,28,30)
sinal = c("<=","<=","<=",">=",">=", ">=")
solucao = lpSolve::lp(direction = "min",
                      objective.in = coef.objetivo,
                      const.mat = restricoes, 
                      const.dir = sinal, 
                      const.rhs = b, all.int = T)
solucao
Success: the objective function is 102.4 
solucao$solution
[1] 1 0 0 0 2 0 2 3 6

Interpretando a solução

x y
x11 1
x12 0
x13 0
x21 0
x22 2
x23 0
x31 2
x32 3
x33 6

O modelo indica que deve ser realizado 14 viagens a um custo de R$102.40 da seguinte forma:

Interpretando a solução…

1 viagem contendo 10 ton no caminhão tipo 1 indo para a cidade A1; 2 viagens contendo 7 ton em cada caminhão tipo 2 indo para a cidade A2; 2 viagens contendo 5 ton em cada caminhão tipo 3 indo para a cidade A1; 3 viagens contendo 5 ton em cada caminhão tipo 3 indo para a cidade A2 e 6 viagens contendo 5 ton em cada caminhão tipo 3 indo para a cidade A3.

  • Verifique quanto de carga cada cidade recebeu com esta solução. A demanda foi atendida?

  • Todas os caminhões disponíveis foram utilizados? Caso não, quantos não foram e de que tipo?

Exercício Adicional

A refinaria de petróleo Petrisul utiliza três tipos de óleo bruto (óleo 1, óleo 2 e óleo 3) para produzir três tipos de gasolina: comum, super e extra. Para garantir a qualidade, cada tipo de gasolina exige determinadas especificações a partir da composição dos diversos tipos de óleo bruto, conforme mostra a Tabela 2.3. Para atender a demanda de seus clientes, a refinaria precisa produzir pelo menos 5.000 barris por dia da gasolina comum e 3.000 barris por dia da gasolina super e extra. A capacidade diária disponível é de 10.000 barris do óleo 1, 8.000 do óleo 2 e 7.000 do óleo 3. A refinaria pode produzir até 20.000 barris de gasolina por dia. A refinaria lucra $5 para cada barril de gasolina comum produzido, $7 por barril de gasolina super e $8 por barril de gasolina extra. Os custos de óleo bruto 1, 2 e 3 por barril são $2, $3 e $3, respectivamente. Formular o problema de programação linear de forma a maximizar o lucro diário.

Fonte: Belfiore & Favero, pag 31

Mestrado em Engenharia Civil/UFF