Pesquisa Operacional - PEOP

AULA 15: MODELAGEM MATEMÁTICA - Problemas de Transporte

Profa. Luciane Alcoforado / Profa. Renata

Academia da Força Aérea

Objetivos

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

1- Desenvolver modelos matemáticos de otimização linear para as situações problema apresentadas (Si).

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

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

Roteiro da Aula

  • Resposta do Desafio
  • Revisão de conceitos das aulas anteriores
  • Modelos clássicos de transporte.
  • Interpretando a solução.
  • Exercícios.

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 ao meio militar

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 militar:

Uma base militar da aeronáutica possui em dotação 8 aeronaves do Tipo 1, 15 aeronaves do Tipo 2 e 11 aeronaves do Tipo 3 disponíveis para os voos de hoje. A capacidade de cada tipo de aeronave é de 10t, 7t e 5t, respectivamente.

O responsável pelas operações da base deve enviar aeronaves 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 avião pode voar somente uma vez por dia.

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

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 uma aeronave 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 das cargas.

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

\(x_{ij}\): número de viagens da aeronave do tipo \(T_i\) enviada 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: as aeronaves 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 da aeronave do tipo \(T_i\) enviada 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 da aeronave do tipo \(T_i\) enviada 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 10x_{12}+ 0x_{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 na aeronave tipo 1 indo para a cidade A1; 2 viagens contendo 7 ton em cada aeronave tipo 2 indo para a cidade A2; 2 viagens contendo 5 ton em cada aeronave tipo 3 indo para a cidade A1; 3 viagens contendo 5 ton em cada aeronave tipo 3 indo para a cidade A2 e 6 viagens contendo 5 ton em cada aeronave tipo 3 indo para a cidade A3.

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

  • Todas as aeronaves disponíveis foram utilizadas? Caso não, quantas não foram e de que tipo?

  • Terminou? Realize os exercícios do caderno de modelagem disponível no moodle.

https://rpubs.com/LucianeA/Aula13_PEOP