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:
a) aqueles que saem de Jacinto e se dirigem para Itinga;

Passo 1

O que o problema pede: escrever um modelo de otimização linear que determine a melhor combinação de bilhetes a vender (por classe e por trajeto) para maximizar o lucro da companhia, respeitando limites de venda por classe/trecho e a capacidade da aeronave.
Informações dadas (retirei os números das duas tabelas do enunciado):
  • A aeronave tem capacidade total de \;30\; passageiros por trecho (cada perna do voo).
  • Classes de passagem: Y (primeira), B (executiva não-reembolsável), M (econômica não-reembolsável).
  • Preços (peguei da tabela de preços): \begin{array}{c|ccc} & \text{Jacinto-Itinga} & \text{Itinga-Turmalina} & \text{Jacinto-Turmalina} \\\ \hline Y & 300 & 160 & 360 \\\ B & 220 & 130 & 280 \\\ M & 100 & 80 & 140 \end{array}
  • Limites superiores de venda por classe e trecho (peguei da tabela de limites): \begin{array}{c|ccc} & \text{Jacinto-Itinga} & \text{Itinga-Turmalina} & \text{Jacinto-Turmalina} \\\ \hline Y & 4 & 8 & 3 \\\ B & 8 & 13 & 10 \\\ M & 22& 20 & 18 \end{array}
  • Tipos de passageiros relevantes (implícitos no enunciado):
    • os que viajam de Jacinto a Itinga (J→I);
    • os que viajam de Itinga a Turmalina (I→T);
    • os que viajam de Jacinto a Turmalina (J→T) — estes embarcam em Jacinto, param em Itinga e seguem para Turmalina, portanto ocupam assento em ambos os trechos.

Passo 2

Definição das variáveis de decisão (essas variáveis representam o número de bilhetes vendidos, por classe e trajeto). Vou usar a notação \,x_{AB}^C, para "número de bilhetes da classe C no trecho A\to B":
  • \;x_{JI}^Y,\;x_{JI}^B,\;x_{JI}^M: bilhetes vendidos Jacinto \to Itinga, nas classes Y,B,M.
  • \;x_{IT}^Y,\;x_{IT}^B,\;x_{IT}^M: bilhetes vendidos Itinga \to Turmalina, nas classes Y,B,M.
  • \;x_{JT}^Y,\;x_{JT}^B,\;x_{JT}^M: bilhetes vendidos Jacinto \to Turmalina, nas classes Y,B,M.
Explicando claramente: por exemplo, \;x_{JT}^M\; é o número de passagens classe M vendidas para passageiros que embarcam em Jacinto e vão até Turmalina (esses passageiros ocupam assento tanto no trecho Jacinto–Itinga quanto no trecho Itinga–Turmalina).

Passo 3

Construção da função objetivo (maximizar receita). Multiplicamos cada variável pelo preço correspondente (peguei os preços da tabela do enunciado) e somamos todas as receitas:
\begin{aligned} \text{Maximizar } Z =\; &300\,x_{JI}^Y + 220\,x_{JI}^B + 100\,x_{JI}^M \\\ &+ 160\,x_{IT}^Y + 130\,x_{IT}^B + 80\,x_{IT}^M \\\ &+ 360\,x_{JT}^Y + 280\,x_{JT}^B + 140\,x_{JT}^M. \end{aligned}
Comentário didático: cada termo tem a forma preço × quantidade. Isso transforma o problema comercial em um problema matemático linear — somamos receitas proporcionais às quantidades vendidas.

Passo 4

Restrições de capacidade por trecho (motivo: a aeronave tem \;30\; assentos por perna; passageiros J→T ocupam assentos em ambos os trechos):
  • No trecho Jacinto \to Itinga embarcam os passageiros J→I (todas as classes) e também os passageiros J→T (todos que partiram de Jacinto com destino final Turmalina). Portanto:
x_{JI}^Y + x_{JI}^B + x_{JI}^M \;+\; x_{JT}^Y + x_{JT}^B + x_{JT}^M \;\le\; 30.
  • No trecho Itinga \to Turmalina embarcam os passageiros I→T (todas as classes) e também os passageiros J→T (que continuam depois do pouso em Itinga). Portanto:
x_{IT}^Y + x_{IT}^B + x_{IT}^M \;+\; x_{JT}^Y + x_{JT}^B + x_{JT}^M \;\le\; 30.
Explicação didática: essas desigualdades asseguram que, em cada perna, o total de passageiros a bordo não ultrapasse a capacidade física do avião.

Passo 5

Restrições de limite máximo de vendas por classe e trecho (peguei esses limites da tabela de limites do enunciado). Para cada par (trecho, classe) impomos o teto indicado:
\begin{aligned} &x_{JI}^Y \le 4,&\quad &x_{JI}^B \le 8,&\quad &x_{JI}^M \le 22,\\\ &x_{IT}^Y \le 8,&\quad &x_{IT}^B \le 13,&\quad &x_{IT}^M \le 20,\\\ &x_{JT}^Y \le 3,&\quad &x_{JT}^B \le 10,&\quad &x_{JT}^M \le 18. \end{aligned}
Didática: essas restrições refletem limites comerciais e de demanda — são máximos que a companhia pretende vender em cada categoria.

Passo 6

Condição de não negatividade e observação sobre integridade:
  • Todas as variáveis representam números de bilhetes, logo devem satisfazer \;x_{AB}^C \ge 0\; para todos os pares (AB,C).
  • Na prática, os x_{AB}^C devem ser inteiros não-negativos (não faz sentido vender fração de passagem). Assim, se quiser o modelo fiel ao problema real, acrescentamos x_{AB}^C \in \mathbb{Z}_{\ge 0}. Se o objetivo for apenas obter uma solução contínua relaxada (LP), basta a condição de não negatividade; para decisões reais use um modelo inteiro (programação inteira).

Passo 7

Resumo do procedimento de solução (o que faria no dia da prova):
  • Escreva as variáveis claramente (como em Passo 2).
  • Escreva a função objetivo como soma de preço × quantidade (Passo 3).
  • Escreva as restrições de capacidade por trecho (Passo 4) e os limites de venda por classe/trecho (Passo 5).
  • Declare não negatividade; se necessário declare integridade inteira.
  • Para resolver numericament e: usar método simplex se for relaxação contínua, ou um solver de programação inteira (branch-and-bound) se exigir integridade.

Resposta

Variáveis: x_{JI}^Y,x_{JI}^B,x_{JI}^M,x_{IT}^Y,x_{IT}^B,x_{IT}^M,x_{JT}^Y,x_{JT}^B,x_{JT}^M, onde x_{AB}^C = número de bilhetes da classe C no trecho A\to B.
\begin{aligned} \text{Maximizar } Z =\; &300\,x_{JI}^Y + 220\,x_{JI}^B + 100\,x_{JI}^M \\\ &+ 160\,x_{IT}^Y + 130\,x_{IT}^B + 80\,x_{IT}^M \\\ &+ 360\,x_{JT}^Y + 280\,x_{JT}^B + 140\,x_{JT}^M \end{aligned}
sujeito a
x_{JI}^Y + x_{JI}^B + x_{JI}^M + x_{JT}^Y + x_{JT}^B + x_{JT}^M \le 30,
x_{IT}^Y + x_{IT}^B + x_{IT}^M + x_{JT}^Y + x_{JT}^B + x_{JT}^M \le 30,
\begin{aligned} &x_{JI}^Y \le 4,\quad x_{JI}^B \le 8,\quad x_{JI}^M \le 22,\\\ &x_{IT}^Y \le 8,\quad x_{IT}^B \le 13,\quad x_{IT}^M \le 20,\\\ &x_{JT}^Y \le 3,\quad x_{JT}^B \le 10,\quad x_{JT}^M \le 18, \end{aligned}
x_{AB}^C \ge 0\quad\text{para todos }(AB,C).
(Se desejar exigir indivisibilidade realista: acrescentar x_{AB}^C \in \mathbb{Z}_{\ge 0}.)

Exercícios relacionados