Pesquisa Operacional - PEOP

AULA 13: 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- compreender o processo de modelagem matemática de problemas (Cp);

2-construir modelos matemáticos para problemas de otimização (Ap);

Roteiro da Aula

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

Revisão de conceitos

Escolha a alternativa correta

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

A produção total de uma fábrica é igual à soma das produções de cada setor.
O lucro total de uma empresa é igual à soma dos lucros de cada produto.
O custo total de um projeto é igual à soma dos custos de cada atividade.
A demanda total de um mercado é igual à soma das demandas de cada segmento.
O tempo total de uma viagem é igual à soma dos tempos de cada trecho.

Escolha a alternativa correta

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

Os parâmetros do modelo são estimados com base em dados históricos e podem variar de acordo com a situação.
Os coeficientes da função objetivo e das restrições são constantes e conhecidos com precisão.
Os recursos disponíveis para o problema são aleatórios e dependem de fatores externos como clima, demanda ou concorrência.
A demanda pelos produtos é desconhecida e varia de acordo com o preço, a qualidade e a propaganda.
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?

O tempo total de uma viagem é igual à soma dos tempos de cada trecho.

A alternativa correta é a letra e, pois o tempo total de uma viagem não é necessariamente igual à soma dos tempos de cada trecho, dependendo do trânsito, das paradas e das condições da estrada. As demais alternativas respeitam a hipótese de aditividade.

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

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?

$x_i$ = número de horas de mão de obra para o produto $i=A,B$
$x_i$ = lucro obtido pela venda do produto $i=A,B$
$x_i$ = número de unidades do produto $i=A,B$ produzidas por semana
$x_i$ = quantidade de matéria-prima para o produto $i=A,B$
$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?

max Z = 2x + 3y
min Z = 10x + 15y
min Z = 2x + 3y
max Z = x + y
max Z = 10x + 15y

Verifique seus acertos

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

$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?

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.

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

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

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$

Obtendo a resposta do modelo

Utilize o phpsimplex e veja o resultado. http://www.phpsimplex.com/simplex/simplex.htm?l=pt
Utilize o R e veja o resultado

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=c(paste0("x1",1:3),paste0("x2",1:3),paste0("x3",1:3))
knitr::kable(data.frame(x,y=solucao$solution))

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.