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;
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 |
| Jacinto-Itinga | Itinga-Turmalina | Jacinto-Turmalina | |
| Y | 4 | 8 | 3 |
| B | 8 | 13 | 10 |
| M | 22 | 20 | 18 |
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):
- Limites superiores de vendas (número máximo de bilhetes de cada classe por trajeto):
- Capacidade do avião em cada trecho:
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
e cada trajeto
definimos:
Assim, por exemplo,
é 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
Comentário breve sobre natureza das variáveis: cada
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:
Aqui eu somei termo a termo: preço
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 é:
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:
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:
Classe B:
Classe M:
(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:
Opcionalmente, pode-se acrescentar a restrição de integridade
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:
para e . -
Objetivo:
- Restrições de capacidade:
-
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
sujeito a
As variáveis que representam os passageiros da parte (b) — “aqueles que saem de Itinga e se dirigem para Turmalina” — são