Programação linear
Hugo Alonso
Universidade Lusófona – Centro Universitário do Porto
2024/2025
Hugo Alonso, UL 1 / 10
Programação linear
Introdução
Programação Linear (PL): base da Investigação Operacional (IO)
A IO surgiu durante a Segunda Guerra Mundial
Objetivo: tomar decisões com base na melhor utilização dos
recursos disponíveis
Áreas de aplicação:
I gestão da produção
I gestão dos transportes
I gestão dos recursos humanos (afetação de pessoal)
I etc.
Hugo Alonso, UL 2 / 10
Programação linear
Etapas num processo de tomada de decisão
1 Estudo e formulação do problema
1 Definição do objetivo com base no qual se pretende tomar a decisão
2 Identificação das variáveis de decisão (controláveis pelo decisor) e
das restrições existentes
3 Formulação matemática do problema
2 Obtenção da solução do problema por aplicação de um algoritmo
3 Análise dos resultados obtidos
4 Tomada de decisão
Hugo Alonso, UL 3 / 10
Programação linear
Caso prático: a empresa Sr. Alcatifas
A empresa Sr. Alcatifas produz e vende dois tipos de alcatifa:
angorá −→ lucro de 4 euros por cada 10 m2
caxemira −→ lucro de 3 euros por cada 10 m2
São utilizadas duas máquinas:
máquina 1 −→ trabalha até 12 horas por dia
máquina 2 −→ trabalha até 14 horas por dia
Para produzir 10 m2 de alcatifa:
angorá −→ 3 horas da máquina 1 e 7 horas da máquina 2
caxemira −→ 4 horas da máquina 1 e 2 horas da máquina 2
Problema: qual é a produção diária dos dois tipos de alcatifa que ma-
ximiza o lucro global?
Hugo Alonso, UL 4 / 10
Programação linear
Caso prático: a empresa Sr. Alcatifas
Objetivo: maximizar o lucro global
Ora, o lucro depende da produção. De facto, sendo
x1 : quantidade de angorá a produzir por dia (em dezenas de m2 )
x2 : quantidade de caxemira a produzir por dia (em dezenas de m2 )
z: lucro diário global (em euros)
tem-se que
z = 4 x1 + 3 x2
Esta expressão representa a chamada função objetivo.
Como o gestor pode decidir sobre a produção, ou seja, sobre x1 e x2 ,
estas são as variáveis de decisão (controláveis).
Hugo Alonso, UL 5 / 10
Programação linear
Caso prático: a empresa Sr. Alcatifas
Há, no entanto, restrições ao nível da utilização das máquinas:
máquina 1: o tempo de produção diária está limitado a 12 horas:
3 x1 + 4 x2 ≤ 12
máquina 2: o tempo de produção diária está limitado a 14 horas:
7 x1 + 2 x2 ≤ 14
Além disso, note-se que não existem produções negativas:
x1 , x2 ≥ 0
Hugo Alonso, UL 6 / 10
Programação linear
Caso prático: a empresa Sr. Alcatifas
Em suma, a formulação matemática do problema é:
maximizar z = 4 x1 + 3 x2 (euros)
sujeito a : 3 x1 + 4 x2 ≤ 12 (horas-máquina)
7 x1 + 2 x2 ≤ 14 (horas-máquina)
x1 , x2 ≥ 0
Hugo Alonso, UL 7 / 10
Programação linear
Caso geral: problema standard do tipo máximo
max z = c1 x1 + c2 x2 + . . . + cn xn
s. a : a11 x1 + a12 x2 + . . . + a1n xn ≤ b1
a21 x1 + a22 x2 + . . . + a2n xn ≤ b2
..
.
am1 x1 + am2 x2 + . . . + amn xn ≤ bm
x1 , x2 , . . . , xn ≥ 0
z é a função objetivo
x1 , x2 , . . . , xn são as n variáveis de decisão
cj , aij e bi são os parâmetros do problema
há m + n restrições (n das quais de não negatividade)
Hugo Alonso, UL 8 / 10
Programação linear
Caso geral: problema standard do tipo mínimo
min z = c1 x1 + c2 x2 + . . . + cn xn
s. a : a11 x1 + a12 x2 + . . . + a1n xn ≥ b1
a21 x1 + a22 x2 + . . . + a2n xn ≥ b2
..
.
am1 x1 + am2 x2 + . . . + amn xn ≥ bm
x1 , x2 , . . . , xn ≥ 0
z é a função objetivo
x1 , x2 , . . . , xn são as n variáveis de decisão
cj , aij e bi são os parâmetros do problema
há m + n restrições (n das quais de não negatividade)
Hugo Alonso, UL 9 / 10
Programação linear
Hipóteses em programação linear
Função objetivo e restrições lineares
Variáveis de decisão divisíveis e não negativas
Nota: sempre que necessário, serão realizadas simplificações ou alterações de
modo que estas hipóteses se verifiquem. Quando assim for, é necessário ter
cuidados extra, principalmente na interpretação da solução.
Hugo Alonso, UL 10 / 10