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:
c) aqueles que saem de Jacinto e se dirigem para Turmalina.

Passo 1

O enunciado pede que a gente modele por programação linear a venda de passagens do voo que parte de Jacinto, faz escala em Itinga e segue para Turmalina, de modo a maximizar o lucro da empresa. Ele dá:
  • capacidade da aeronave: 30 passageiros por voo (a mesma aeronave faz os dois trechos: Jacinto→Itinga e Itinga→Turmalina).
  • três classes de passagem: Y (primeira), B (executiva), M (econômica).
  • preços (tarifa) por classe e por trecho — peguei estes valores da tabela do enunciado:
\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 (capacidade de demanda) por classe e por trecho — peguei estes valores da tabela do enunciado:
\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}
  • condição importante de operação: não há overbooking (não vender além dos limites) e a limitação física de 30 assentos por trecho deve ser respeitada.
    O objetivo é indicar quantos bilhetes vender de cada classe em cada trajeto para maximizar o lucro. A seguir vamos definir variáveis, função objetivo e todas as restrições.

Passo 2

Definição das variáveis de decisão (explicando o que cada uma representa, para você usar direto na prova):
  • Seja x_{Y,JI} o número de passagens vendidas na classe \mathrm{Y} para o trecho Jacinto→Itinga.
  • Seja x_{B,JI} o número de passagens vendidas na classe \mathrm{B} para o trecho Jacinto→Itinga.
  • Seja x_{M,JI} o número de passagens vendidas na classe \mathrm{M} para o trecho Jacinto→Itinga.
  • Seja x_{Y,IT} o número de passagens vendidas na classe \mathrm{Y} para o trecho Itinga→Turmalina.
  • Seja x_{B,IT} o número de passagens vendidas na classe \mathrm{B} para o trecho Itinga→Turmalina.
  • Seja x_{M,IT} o número de passagens vendidas na classe \mathrm{M} para o trecho Itinga→Turmalina.
  • Seja x_{Y,JT} o número de passagens vendidas na classe \mathrm{Y} para o trecho Jacinto→Turmalina (passageiros que embarcam em Jacinto e permanecem até Turmalina).
  • Seja x_{B,JT} o número de passagens vendidas na classe \mathrm{B} para o trecho Jacinto→Turmalina.
  • Seja x_{M,JT} o número de passagens vendidas na classe \mathrm{M} para o trecho Jacinto→Turmalina.
Observação didática: cada variável conta bilhetes vendidos por classe e origem-destino. Na prova, diga sempre em palavras o que a variável representa (vai te salvar na correção).

Passo 3

Construção da função objetivo (por que é essa forma):
Precisamos maximizar a receita total obtida com as vendas. Para cada variável multiplicamos pelo preço correspondente (peguei os preços da tabela). Então a função objetivo é a soma das receitas de todos os bilhetes vendidos:
\begin{aligned} \text{Maximize } Z =\;&300x_{Y,JI}+220x_{B,JI}+100x_{M,JI}\\\ &+160x_{Y,IT}+130x_{B,IT}+80x_{M,IT}\\\ &+360x_{Y,JT}+280x_{B,JT}+140x_{M,JT}. \end{aligned}
Explicando: cada termo é “preço × quantidade vendida”. Somando todos obtemos a receita total, que queremos maximizar.

Passo 4

Restrições de limite superior de venda (uso direto dos dados): para cada classe e cada trecho a gerência definiu um máximo que não pode ser ultrapassado. Então colocamos para cada variável:
\begin{aligned} &x_{Y,JI} \le 4, &\quad &x_{B,JI} \le 8, &\quad &x_{M,JI} \le 22,\\\ &x_{Y,IT} \le 8, &\quad &x_{B,IT} \le 13, &\quad &x_{M,IT} \le 20,\\\ &x_{Y,JT} \le 3, &\quad &x_{B,JT} \le 10, &\quad &x_{M,JT} \le 18. \end{aligned}
Explicação didática: esses são limites de demanda/empresa — não podemos vender mais que isso em cada categoria.

Passo 5

Restrição de capacidade no primeiro trecho (Jacinto→Itinga): quem ocupa assento nesse trecho são todos os passageiros que embarcam em Jacinto, isto é: aqueles com bilhetes Jacinto→Itinga (que desembarcam em Itinga) mais aqueles com bilhetes Jacinto→Turmalina (que ficam no avião até Turmalina). Logo, a soma de todas as classes desses dois tipos não pode exceder 30:
x_{Y,JI}+x_{B,JI}+x_{M,JI}+x_{Y,JT}+x_{B,JT}+x_{M,JT} \le 30.
Explicando passo a passo: o avião parte de Jacinto com passageiros JI (descem em Itinga) e JT (continuam). Todos ocupam assentos no trecho inicial.

Passo 6

Restrição de capacidade no segundo trecho (Itinga→Turmalina): no segundo trecho viajam os passageiros que permaneceram desde Jacinto com destino Turmalina (variáveis x_{\cdot,JT}) mais os passageiros que embarcaram em Itinga com destino Turmalina (variáveis x_{\cdot,IT}). A soma desses dois grupos, em todas as classes, também não pode ultrapassar 30:
x_{Y,JT}+x_{B,JT}+x_{M,JT}+x_{Y,IT}+x_{B,IT}+x_{M,IT} \le 30.
Explicação: no pouso em Itinga alguns passageiros descem (os JI), e outros sobem (os IT); a capacidade no segundo trecho é novamente 30. Esse vínculo entre trechos é o coração do modelo.

Passo 7

Condições de não-negatividade e observação sobre integralidade: todas as quantidades de bilhetes são não negativas:
x_{c,r} \ge 0\quad\text{para todas as classes }c\in\{Y,B,M\}\text{ e trechos }r\in\{JI,IT,JT\}.
Na prática as vendas são inteiras (número inteiro de passagens), então poderíamos acrescentar x_{c,r}\in\mathbb{Z}_{\ge0}. Em muitos exercícios de programação linear para prova, aceita-se a versão contínua (relaxação) e depois você justifica que uma solução inteira existe ou que se exige integralidade. Se o enunciado exigir explicitamente inteiros, então declare as variáveis inteiras.

Passo 8

Por que o modelo é linear e por que é correto:
  • A função objetivo é uma soma linear de variáveis com coeficientes constantes (preços).
  • As restrições são somas lineares das variáveis limitadas por constantes (capacidade e limites de venda).
    Logo é um problema de programação linear clássico: decidir quantos bilhetes vender de cada tipo sujeito a capacidade e limites. Na prova, escreva as variáveis claramente, monte a função objetivo e escreva todas as restrições (como fiz acima); isso vale muitos pontos porque mostra entendimento do vínculo entre trechos.

Passo 9

Montagem final do modelo (forma compacta pronta para entregar na prova): abaixo juntei objetivo, restrições superiores por variável, restrições de capacidade por trecho e não-negatividade. Isto é o problema de otimização linear completo que você deve entregar.

Resposta

\begin{aligned} \text{Maximize } Z =\;&300x_{Y,JI}+220x_{B,JI}+100x_{M,JI}\\\ &+160x_{Y,IT}+130x_{B,IT}+80x_{M,IT}\\\ &+360x_{Y,JT}+280x_{B,JT}+140x_{M,JT} \end{aligned}
sujeito a
\begin{aligned} &x_{Y,JI} \le 4,\\\ &x_{B,JI} \le 8,\\\ &x_{M,JI} \le 22,\\\ &x_{Y,IT} \le 8,\\\ &x_{B,IT} \le 13,\\\ &x_{M,IT} \le 20,\\\ &x_{Y,JT} \le 3,\\\ &x_{B,JT} \le 10,\\\ &x_{M,JT} \le 18,\\[6pt] &x_{Y,JI}+x_{B,JI}+x_{M,JI}+x_{Y,JT}+x_{B,JT}+x_{M,JT} \le 30,\\[6pt] &x_{Y,JT}+x_{B,JT}+x_{M,JT}+x_{Y,IT}+x_{B,IT}+x_{M,IT} \le 30,\\[6pt] &x_{c,r} \ge 0\quad\text{para todos }c\in\{Y,B,M\},\;r\in\{JI,IT,JT\}. \end{aligned}]

Exercícios relacionados