Questão 1
A Viação Aérea Brasileira está estudando a compra de três tipos de aviões: Boeing 717 para as pontes aéreas de curta distância, Boeing 737-500 para vôos domésticos e internacionais de média distância e MD-11 para vôos internacionais de longa distância. Em um estudo preliminar, considerou-se que a capacidade máxima dos aviões a serem comprados será sempre preenchida para efeito de planejamento. Os dados de planejamento constam na tabela 1.
Table 1: Tabela 1: Dados operacionais dos aviões\captionsetup{labelformat=empty}
Tipo de aviões
Custo
US$
Receita
US$
Pilotos aptos
Boeing 717
5,1
330
30
Boeing 737-500
3,6
300
20
MD-11
6,8
420
10
A verba disponível para as compras é de US
220
3 / 4
5 / 3$ de um Boeing 717 .
Formule o modelo de programação linear para este problema, de forma a maximizar o lucro obtido com os aviões adquiridos.
Resolva o problema resultante computacionalmente (Excel, OpenOffice, Matlab ou Matlab + Gurobi).
Table 1: Tabela 1: Dados operacionais dos aviões
\captionsetup{labelformat=empty}
| Tipo de aviões | Custo
|
Receita
|
Pilotos aptos |
| Boeing 717 | 5,1 | 330 | 30 |
| Boeing 737-500 | 3,6 | 300 | 20 |
| MD-11 | 6,8 | 420 | 10 |
Passo 1
O enunciado pede duas coisas: formular um modelo de programação linear que maximize o lucro com a compra de aviões e resolver esse modelo numericamente. Dados relevantes extraídos do enunciado:
- Verba disponível:
milhões. - Dados por tipo de aeronave (valores já em milhões de US$ conforme a tabela):
- Boeing 717: custo
e receita ; pilotos aptos: . - Boeing 737-500: custo
e receita ; pilotos aptos: . - MD-11: custo
e receita ; pilotos aptos: .
- Boeing 717: custo
- Cada aeronave necessita de 2 pilotos para operar.
- Pilotos de MD-11 podem pilotar qualquer tipo de avião; pilotos dos outros dois tipos só pilotam o seu respectivo tipo.
- Capacidade de manutenção: equivalente a
Boeing 717. - Esforço de manutenção (em unidades de “1 Boeing 717”):
- Boeing 717:
. - Boeing 737-500:
. - MD-11:
.
- Boeing 717:
O que devemos retornar: (i) o modelo matemático (variáveis, função objetivo e restrições) e (ii) a solução numérica que maximiza o lucro.
Passo 2
Definição das variáveis de decisão (escolha natural e fácil de interpretar):
- Seja
o número de Boeing 717 a comprar/operar. - Seja
o número de Boeing 737-500 a comprar/operar. - Seja
o número de MD-11 a comprar/operar.
Para tratar a flexibilidade dos pilotos MD-11 (que podem ser alocados a qualquer tipo), introduzimos variáveis de alocação dos pilotos MD-11:
- Seja
o número de pilotos MD-11 alocados para pilotar Boeing 717. - Seja
o número de pilotos MD-11 alocados para pilotar Boeing 737-500. - Seja
o número de pilotos MD-11 alocados para pilotar MD-11.
Observações sobre domínio:
- Todas as variáveis são não-negativas:
, . - Na prática
e são inteiros (não se compram frações de aviões ou de pilotos), então o modelo será um MILP. Se for solicitado relaxar a integralidade, pode-se resolver o LP contínuo; aqui mantemos a ideia inteira por realismo (explicarei a solução inteira abaixo).
Passo 3
Função objetivo (maximizar lucro). Primeiro calculemos o lucro unitário de cada avião (receita menos custo), todos em milhões de US$:
- Lucro por Boeing 717:
- Lucro por Boeing 737-500:
- Lucro por MD-11:
A função objetivo (maximizar lucro total) é então:
Explicação didática: cada
multiplicado pelo lucro unitário dá a contribuição desse tipo ao lucro total; somando temos o lucro total a maximizar.
Passo 4
Restrição de orçamento (limite de gasto na compra das aeronaves). Os custos estão em milhões, a verba é
(milhões), portanto:
Interpretação: soma do custo das aeronaves compradas não pode exceder a verba disponível.
Passo 5
Restrição de capacidade de manutenção (em equivalentes de Boeing 717). Usando os fatores dados, a soma ponderada dos aviões não pode exceder
:
Explicação didática: cada Boeing 717 consome uma unidade de manutenção; um 737 consome
dessa unidade; um MD-11 consome
. A soma deve ficar dentro da capacidade.
Passo 6
Restrições de pilotos. Cada avião exige 2 pilotos. Há pilotos dedicados para 717 (
pilotos) e para 737 (
pilotos), e
pilotos MD-11 que podem ser alocados a qualquer tipo. O modelo com variáveis de alocação MD-11 fica linear:
- Pilotos para Boeing 717: os
pilotos 717 só podem pilotar 717; além disso pode-se usar pilotos MD-11 para ajudar. Assim:
- Pilotos para Boeing 737-500: os
pilotos 737 só pilotam 737; mais os MD-11 pilots alocados:
- Pilotos para MD-11: apenas pilotos MD-11 podem pilotar MD-11, logo o número de pilotos MD-11 alocados a MD-11 deve ser suficiente:
- Limite total de pilotos MD-11 disponíveis:
Todas essas desigualdades são lineares e explicam quem pode pilotar o quê. Valores
são contagens de pilotos MD-11 (inteiros).
Passo 7
Condições de não-negatividade e integralidade:
Comentário didático: se o professor exigir somente o modelo LP contínuo, as restrições de integralidade podem ser relaxadas; para solução realista (número de aviões e pilotos inteiros) devemos resolver o MILP.
Passo 8
Resumo compacto do modelo (MILP):
Explicação curta: objetivo maximiza lucro total; primeiras duas restrições controlam verba e manutenção; três próximas controlam requisito de pilotos tipo-a-tipo; última limita o número total de pilotos MD-11.
Passo 9
Resolução prática (raciocínio e cálculo que substituem a execução num solver; o mesmo raciocínio dá a solução que um MILP resolveria):
-
Observação prática: o número máximo de aviões que podem voar simultaneamente é limitado pelo total de pilotos disponíveis:
pilotos no total, ou seja, no máximo aeronaves ao mesmo tempo. Portanto (essa é uma consequência combinada das desigualdades de pilotos). -
Para decidir como alocar os pilotos MD-11 (as variáveis
), compare o ganho marginal por par de pilotos (já que cada avião usa 2 pilotos). Lucro por par de pilotos para cada tipo:
Isso mostra que, em termos de renda por par de pilotos, MD-11 é a mais lucrativa, seguida por 717 e por fim 737. Assim, pilotos escassos (os 10 pilotos MD-11) devem ser preferencialmente alocados para servir MD-11, porque cada dois pilotos MD-11 usados em um MD-11 geram mais lucro do que se estes mesmos pilotos fossem usados para pilotar 717 ou 737.
-
Alocando os
pilotos MD-11 todos para MD-11 resulta em , logo por temos . Então é natural testar (usar todos os pilotos MD-11 para voar MD-11), porque MD-11 tem maior lucro por par de pilotos. -
Se
, então os pilotos MD-11 foram usados integralmente em MD-11 ( , ). Então os pilotos dedicados restam:
- Pilotos 717:
disponíveis → máximo (cada avião usa 2 pilotos). - Pilotos 737:
disponíveis → máximo .
Com essas máximas naturais (sem realocar MD-11 pilots), podemos usar todos os pilotos de cada categoria para fabricar aviões do seu tipo.
- Verificar restrições de manutenção e orçamento para a escolha
.
- Manutenção:
Logo a manutenção está satisfatória.
- Orçamento:
Logo o orçamento está satisfatório.
- Lucro total para essa solução:
Cálculo:
- Argumento de optimalidade (intuitivo e suficiente para este problema):
- Todos os pilotos estão sendo utilizados:
pilotos 717 → Boeing 717; pilotos 737 → Boeing 737-500; pilotos MD-11 → MD-11. Como o total de pilotos é recurso estrangulante (limitando a aeronaves) e como alocar os pilotos MD-11 a MD-11 gera maior lucro por par de pilotos do que alocá-los a 717 ou 737, a distribuição que maximiza o uso dos pilotos em suas aeronaves preferidas é a melhor. Qualquer realocação de pilotos MD-11 de MD-11 para outro tipo reduziria o lucro total (comparação por par de pilotos mostra isto). - Manutenção e orçamento não estão saturadas, portanto não impõem trocas vantajosas entre tipos: não há ganho em reduzir número de um tipo para comprar outro se isso não libera pilotos (o verdadeiro gargalo).
- Assim a solução inteira
é ótima dentro das restrições inteiras.
Nota didática: um solver MILP (Excel Solver, Gurobi, etc.) confirmaria essa solução; aqui fiz a análise combinando a observação sobre o gargalo de pilotos com a comparação de lucro por par de pilotos para alocar os pilotos MD-11 de maneira ótima.
Resposta
Lucro máximo