Uma ponte aérea
Programação linear: Infinito 11 A - Parte 1 Pág. 161 Ex. 73
Pretende-se organizar uma ponte aérea para transportar 1600 pessoas e 90 toneladas de bagagem.
Os aviões disponíveis são de dois tipos: 12 do tipo A e 9 do tipo B.
Com carga completa, um avião do tipo A pode transportar 200 pessoas e 6 toneladas de bagagem. Um avião do tipo B pode transportar 100 pessoas e 15 toneladas.
Quantos aviões de cada tipo devem ser contratados para que o custo do aluguer seja mínimo, sabendo que o aluguer do avião do tipo A custa 4 milhões de euros e o do tipo B custa 1 milhão de euros.
Para facilitar a análise do problema, comecemos por organizar parte dos dados numa tabela:
| Tipo de avião | Preço de aluguer (M €) | N.º de aviões disponíveis | Carga completa | |
| N.º de pessoas | Bagagem (t) | |||
| Tipo A | 4 | 12 | 200 | 6 |
| Tipo B | 1 | 9 | 100 | 15 |
As incógnitas do problema são:
- x, o número de aviões alugados do tipo A
- y, o número de aviões alugados do tipo B
Organizemos os dados numa tabela para podermos relacioná-los mais facilmente.
| Tipo de avião | N.º de aviões alugados | Carga transportada | Custo do aluguer (M €) | |
| N.º de pessoas | Bagagem (t) | |||
| Tipo A | $x$ | $200x$ | $6x$ | $4x$ |
| Tipo B | $y$ | $100y$ | $15y$ | $y$ |
| Total | $x+y$ | $200x+100y$ | $6x+15y$ | $4x+y$ |
O problema tem as seguintes restrições:
- $x\in {{\mathbb{N}}_{0}}$ e $y\in {{\mathbb{N}}_{0}}$
O número de aviões a alugar de cada tipo é inteiro não negativo;
- $x\le 12$
Só há 12 aviões disponíveis do tipo A;
- $y\le 9$
Só há 9 aviões disponíveis do tipo B;
- $x+y\le 21$ (irrelevante, pois a restrição está já contida nas duas anteriores)
O número máximo de aviões a alugar é 21;
- $200x+100y\ge 1600\Leftrightarrow 2x+y\ge 16$
O número de lugares a alugar terá de ser superior ou igual ao número de pessoas a transportar (1600).
- $6x+15y\ge 90\Leftrightarrow 2x+5y\ge 30$
A capacidade de carga a alugar terá de ser superior à bagagem a transportar (90 t).
Cada avião do tipo A é alugado por 4 M€ e cada do tipo B é alugado por 1 M€.
Portanto, a função objectivo é: $C=4x+y\Leftrightarrow y=-4x+C$.
Os pontos admissíveis, isto é, os pontos cujas coordenadas satisfazem as condições impostas, são os pontos de coordenadas inteiras pertencentes ao quadrilátero [GHIJ], no seu interior ou sobre os seus lados.
Validemos as coordenadas dos pontos G e H, assinalados no referencial apresentado:
$\begin{matrix}
\left\{ \begin{array}{*{35}{l}}
2x+y=16 \\
2x+5y=30 \\
\end{array} \right. & \Leftrightarrow & \left\{ \begin{array}{*{35}{l}}
2x+y=16 \\
4y=14 \\
\end{array} \right. & \Leftrightarrow & \left\{ \begin{array}{*{35}{l}}
x=\frac{25}{4} \\
y=\frac{7}{2} \\
\end{array} \right. & \to & H(\frac{25}{4},\frac{7}{2}) \\
\end{matrix}$
$\begin{matrix}
\left\{ \begin{array}{*{35}{l}}
2x+y=16 \\
y=9 \\
\end{array} \right. & \Leftrightarrow & \left\{ \begin{array}{*{35}{l}}
2x=7 \\
y=9 \\
\end{array} \right. & \Leftrightarrow & \left\{ \begin{array}{*{35}{l}}
x=\frac{7}{2} \\
y=9 \\
\end{array} \right. & \to & G(\frac{7}{2},9) \\
\end{matrix}$
A solução óptima encontra-se na periferia da região de validez, próxima do ponto $G(\frac{7}{2},9)$, o qual não é ponto admissível.
Os dois pontos admissíveis mais próximos de G são ${{G}_{1}}(4,8)$ e ${{G}_{2}}(4,9)$.
Graficamente, a solução óptima parece ser o par (4, 8), isto é, as coordenadas do ponto ${{G}_{1}}$.
Vamos, então, verificar analiticamente se essa suposição é verdadeira:
- ${{C}_{{{G}_{1}}}}=4\times 4+8=24$
- ${{C}_{{{G}_{2}}}}=4\times 4+9=25$
Confirma-se, portanto, que a solução óptima é o par ordenado (4, 8).
Assim, para tornar mínimo o custo da ponte aérea, devem ser alugados 4 aviões do tipo A e 8 do tipo B.
