A companhia de aviação Voe Comigo possui rotas entre três cidades: Jacinto, Itinga e Turmalina. Ela oferece vários horários de vôo, mas, para os interesses desse problema, vamos nos ater somente aos vôos que partem às sexta-feiras a tarde de Jacinto, param em Itinga e seguem para Turmalina. Os aviões utilizados nestes vôos são pequenas aeronaves que comportam 30 passageiros, divididos nas seguintes classes:
Classe Y: primeira classe;
Classe B: classe executiva, não-reembolsável;
Classe M: classe econômica, não-reembolsável, devendo ser adquiridos com 3 semanas de antecedência.
Os valores dos bilhetes, apesar de determinados também pela concorrência, foram definidos como sendo:
Jacinto-Itinga Itinga-Turmalina Jacinto-Turmalina
Y 300 160 360
B 220 130 280
M 100 80 140
Tendo por base o volume de vendas em períodos normais, a gerência da empresa determinou os seguintes limites superiores no número de passagens a serem vendidas em cada uma das classes e cada um dos destinos:
Jacinto-Itinga Itinga-Turmalina Jacinto-Turmalina
Y 4 8 3
B 8 13 10
M 22 20 18
A companhia, por respeito ao seu cliente e por pressão das agências de regulação da aviação civil, não permite a venda de passagens além do especificado para cada vôo, ou seja, em linguagem do ramo, não permite overbooking. Escreva o problema como um problema de otimização linear, de modo que se possa determinar qual a melhor combinação de bilhetes a serem vendidos para maximizar o lucro da empresa.
Os passageiros podem ser classificados na seguinte forma:
b) aqueles que saem de Itinga e se dirigem para Turmalina;

Passo 1

O enunciado pede que formulemos um problema de otimização linear que determine a melhor combinação de bilhetes a serem vendidos (por classe e por trajeto) para maximizar o lucro, respeitando: capacidade da aeronave (30 lugares) em cada trecho e os limites máximos de venda por classe e por destino (tabelas fornecidas). Os dados relevantes (retirados das tabelas do enunciado) são:
  • Preços dos bilhetes (em reais):
\begin{array}{c|ccc} & \text{Jacinto--Itinga (JI)} & \text{Itinga--Turmalina (IT)} & \text{Jacinto--Turmalina (JT)}\\hline Y & 300 & 160 & 360\\\ B & 220 & 130 & 280\\\ M & 100 & 80 & 140 \end{array}
  • Limites superiores de vendas (número máximo de bilhetes de cada classe por trajeto):
\begin{array}{c|ccc} & \text{JI} & \text{IT} & \text{JT} \\hline Y & 4 & 8 & 3\\\ B & 8 & 13 & 10\\\ M & 22 & 20 & 18 \end{array}
  • Capacidade do avião em cada trecho: \,30 passageiros.
A parte específica mencionada no enunciado (b) diz respeito aos passageiros que saem de Itinga e se dirigem para Turmalina — vamos identificar as variáveis correspondentes quando definirmos as variáveis de decisão.

Passo 2

Definimos as variáveis de decisão. Para cada classe C\in\{Y,B,M\} e cada trajeto r\in\{\text{JI},\text{IT},\text{JT}\} definimos:
x_{C,r} = \text{número de bilhetes vendidos da classe }C\text{ no trajeto }r.ú
Assim, por exemplo, \,x_{Y,\text{IT}} é o número de bilhetes de classe Y vendidos para o trecho Itinga–Turmalina. Note que a parte (b) do enunciado (“aqueles que saem de Itinga e se dirigem para Turmalina”) corresponde exatamente às variáveis
x_{Y,\text{IT}},\quad x_{B,\text{IT}},\quad x_{M,\text{IT}}.
Comentário breve sobre natureza das variáveis: cada x_{C,r} representa uma contagem de bilhetes (portanto um inteiro não negativo). Em muitos modelos praticáveis aceitamos solução contínua (relaxação) e depois arredondamos, mas o modelo exato é inteiro. Aqui formulamos como um problema linear com restrições de integridade implícitas (ou com relaxação, conforme a necessidade da prova).

Passo 3

Construímos a função objetivo: queremos maximizar a receita total, que é a soma do número de bilhetes vendidos em cada classe e trajeto multiplicado pelo preço correspondente. Usando os preços dados:
\begin{aligned} \text{Maximizar }Z=\;&300\,x_{Y,\text{JI}}+220\,x_{B,\text{JI}}+100\,x_{M,\text{JI}}\\\ &+160\,x_{Y,\text{IT}}+130\,x_{B,\text{IT}}+80\,x_{M,\text{IT}}\\\ &+360\,x_{Y,\text{JT}}+280\,x_{B,\text{JT}}+140\,x_{M,\text{JT}}. \end{aligned}
Aqui eu somei termo a termo: preço \times quantidade para cada uma das 9 variáveis.

Passo 4

Agora as restrições de capacidade nos dois trechos (explicando o porquê): o avião sai de Jacinto rumo a Itinga; nesse primeiro trecho (Jacinto→Itinga) estarão a bordo tanto os passageiros que compraram bilhetes JI (descem em Itinga) quanto os passageiros JT (vão até Turmalina e permanecem a bordo após Itinga). Logo a ocupação do primeiro trecho é:
\sum_{C\in\{Y,B,M\}}\bigl(x_{C,\text{JI}}+x_{C,\text{JT}}\bigr)\le 30.
No segundo trecho (Itinga→Turmalina) estarão a bordo os passageiros que embarcaram em Itinga (IT) mais os que vêm de Jacinto com destino Turmalina (JT). Assim:
\sum_{C\in\{Y,B,M\}}\bigl(x_{C,\text{IT}}+x_{C,\text{JT}}\bigr)\le 30.
Essas duas restrições garantem que não haja overbooking em nenhum trecho.

Passo 5

As restrições de limite máximo de vendas (retiradas da tabela de limites) são impostas para cada variável. Escrevemos todas elas:
Classe Y:
0\le x_{Y,\text{JI}}\le 4,\quad 0\le x_{Y,\text{IT}}\le 8,\quad 0\le x_{Y,\text{JT}}\le 3.
Classe B:
0\le x_{B,\text{JI}}\le 8,\quad 0\le x_{B,\text{IT}}\le 13,\quad 0\le x_{B,\text{JT}}\le 10.
Classe M:
0\le x_{M,\text{JI}}\le 22,\quad 0\le x_{M,\text{IT}}\le 20,\quad 0\le x_{M,\text{JT}}\le 18.
(Repetindo: os limites acima vieram diretamente da tabela de limites do enunciado.)

Passo 6

Condição de não negatividade e, se desejarmos o modelo inteiro:
x_{C,r}\ge 0\quad\text{para todos }C\in\{Y,B,M\},\\ r\in\{\text{JI},\text{IT},\text{JT}\}.
Opcionalmente, pode-se acrescentar a restrição de integridade
x_{C,r}\in\mathbb{Z}\quad\text{(inteiros)},
pois bilhetes são indivisíveis. Em muitos exercícios de formulação basta a não negatividade; se a prova pedir solução inteira, então tratar como problema inteiro.

Passo 7

Resumo do modelo completo (colocando tudo junto) — este é o problema de programação linear que se resolve para obter a melhor combinação de bilhetes vendida:
  • Variáveis: x_{C,r} para C\in\{Y,B,M\} e r\in\{\text{JI},\text{IT},\text{JT}\}.
  • Objetivo:
\begin{aligned} \text{Maximizar }Z=\;&300\,x_{Y,\text{JI}}+220\,x_{B,\text{JI}}+100\,x_{M,\text{JI}}\\\ &+160\,x_{Y,\text{IT}}+130\,x_{B,\text{IT}}+80\,x_{M,\text{IT}}\\\ &+360\,x_{Y,\text{JT}}+280\,x_{B,\text{JT}}+140\,x_{M,\text{JT}}. \end{aligned}
  • Restrições de capacidade:
\begin{aligned} &x_{Y,\text{JI}}+x_{B,\text{JI}}+x_{M,\text{JI}}+x_{Y,\text{JT}}+x_{B,\text{JT}}+x_{M,\text{JT}}\le 30,\\\ &x_{Y,\text{IT}}+x_{B,\text{IT}}+x_{M,\text{IT}}+x_{Y,\text{JT}}+x_{B,\text{JT}}+x_{M,\text{JT}}\le 30. \end{aligned}
  • Limites máximos por classe/trajeto (copiando as restrições do Passo 5).
  • Não negatividade (e inteiros se exigido).
Esse modelo é linear (objetivo e restrições lineares) e pode ser resolvido por métodos padrão (simplex ou solver inteiro se fizermos integridade).

Resposta

Maximizar
\begin{aligned} Z=\;&300\,x_{Y,\text{JI}}+220\,x_{B,\text{JI}}+100\,x_{M,\text{JI}}\\\ &+160\,x_{Y,\text{IT}}+130\,x_{B,\text{IT}}+80\,x_{M,\text{IT}}\\\ &+360\,x_{Y,\text{JT}}+280\,x_{B,\text{JT}}+140\,x_{M,\text{JT}} \end{aligned}
sujeito a
\begin{aligned} &x_{Y,\text{JI}}+x_{B,\text{JI}}+x_{M,\text{JI}}+x_{Y,\text{JT}}+x_{B,\text{JT}}+x_{M,\text{JT}}\le 30,\\[4pt] &x_{Y,\text{IT}}+x_{B,\text{IT}}+x_{M,\text{IT}}+x_{Y,\text{JT}}+x_{B,\text{JT}}+x_{M,\text{JT}}\le 30,\\[4pt] &0\le x_{Y,\text{JI}}\le 4,\quad 0\le x_{Y,\text{IT}}\le 8,\quad 0\le x_{Y,\text{JT}}\le 3,\\[4pt] &0\le x_{B,\text{JI}}\le 8,\quad 0\le x_{B,\text{IT}}\le 13,\quad 0\le x_{B,\text{JT}}\le 10,\\[4pt] &0\le x_{M,\text{JI}}\le 22,\quad 0\le x_{M,\text{IT}}\le 20,\quad 0\le x_{M,\text{JT}}\le 18,\\[4pt] &x_{C,r}\ge 0\quad\text{para todos }C\in\{Y,B,M\},\\ r\in\{\text{JI},\text{IT},\text{JT}\}. \end{aligned}
As variáveis que representam os passageiros da parte (b) — “aqueles que saem de Itinga e se dirigem para Turmalina” — são
x_{Y,\text{IT}},\quad x_{B,\text{IT}},\quad x_{M,\text{IT}}.]

Exercícios relacionados