INVESTIGAÇÃO OPERACIONAL

2ª Aula

Cecília Rocha # 1
Programação Linear

A programação linear utiliza um modelo matemático para descrever o problema
em análise. Todas as funções que compõem esse modelo são funções
lineares. O seu principal objectivo é o planeamento de actividades para obter
um resultado óptimo, ou seja, que permita atingir os resultados pretendidos.

A aplicação mais comum da programação linear refere-se à distribuição de
recursos por diversas actividades, no entanto, muitas vezes também é utilizada
para resolver problemas de natureza diferente.
2001/2002
INVESTIGAÇÃO OPERACIONAL

2ª Aula (cont.)

Exercício Modelo


Cecília Rocha # 2
Uma empresa produz produtos em vidro de boa qualidade, incluindo portas e janelas em
vidro. As suas instalações têm 3 pisos. Os caixilhos de alumínio e as ferragens são
produzidas no piso 1, no piso 2 são feitas as caixilharias em madeira e no piso 3 é
produzido o vidro e feita a junção dos diferentes sub- componentes.
Como houve uma quebra nos lucros a administração decidiu reformular a linha de
produção. Os produtos que não traziam lucro deixaram de ser fabricados e a
capacidade produtiva libertada possibilita o lançamento de 2 novos produtos com boas
perspectivas de venda:
 Produto 1: Porta de vidro com caixilharia de alumínio e largura de 2.40m
 Produto 2: Janela de vidro com caixilharia de madeira de 1.20*1.80 m
O produto 1 necessita de capacidade produtiva nos pisos 1 e 3 e o produto 2 só requer
recursos dos pisos 2 e 3. A equipa de marketing concluiu que toda a produção possível
destes 2 produtos terá escoamento imediato no mercado. Contudo, devido à competição
interna, em termos de capacidade produtiva do piso 3, não está ainda decidido o número
de peças de cada produto a ser produzido para alcançar o máximo lucro.
Para este efeito (determinar o n.º de peças de cada produto) foram contratados
consultores de IO.
2001/2002
INVESTIGAÇÃO OPERACIONAL

2ª Aula (cont.)

Após encontro com a administração para esclarecer os objectivos finais do trabalho e a recolha
de dados referente a:



N.º de horas de produção semanal disponíveis em cada piso para os 2 novos produtos
N.º de horas de produção utilizadas em cada piso para a produção de cada elemento dos 2 novos
produtos
Lucro previsto com a venda de cada elemento dos 2 novos produtos (dado que não existem custos
significativos de início de produção e marketing, o lucro obtido será aproximadamente igual ao lucro por
elemento produzido * N.º elementos produzidos)
que se resumem no quadro seguinte:
Tempo de produção por elemento, horas
Cecília Rocha # 3
Piso
Produto 1
Produto 2
Tempo de produção
semanal disponível, horas
1
1
0
4
2
0
2
12
3
3
2
18
Lucro por elemento
3 000 u.m.
5 000 u.m.
2001/2002
INVESTIGAÇÃO OPERACIONAL

2ª Aula (cont.)

Formulação como um Problema de Programação Linear

Variáveis de decisão



x1 – N.º de elementos do produto 1 produzidos semanalmente
x2 – N.º de elementos do produto 2 produzidos semanalmente
Função Objectivo

Z – Lucro semanal total resultante da produção dos 2 novos produtos
Maximizar Z = 3000 x1 + 5000 x2, ou seja Max Z = 3 x1 + 5 x2

Restrições
x1
4
2 x2  12
3 x1 + 2 x2  18,
x1 0 e x2 0
Cecília Rocha # 4
2001/2002
INVESTIGAÇÃO OPERACIONAL

2ª Aula (cont.)

Resolução Gráfica

Problema Bidimensional (só duas variáveis de decisão)





x2
Gráfico em que os eixos de representação serão as variáveis x1 e x2
A primeira restrição a impor será a Não Negatividade das variáveis de decisão
A segunda restrição corresponderá ao máximo de 4 horas semanais, no piso 1, para produzir x1
A terceira restrição refere-se à restrição de 12 horas no piso 2 para produzir o produto 2
A última restrição relaciona-se com a restrição a 18 horas no piso 3 disponíveis para os 2 produtos
X1  0
X1  4
2x2  12
3x1 + 2x2  18
Cecília Rocha # 5
X2  0
x1
2001/2002
INVESTIGAÇÃO OPERACIONAL

2ª Aula (cont.)

Resolução Gráfica

Problema Bidimensional (só duas variáveis de decisão)


x2
A área sombreada corresponde à Região das Solução Admissíveis
A etapa final deste método consiste em encontrar o ponto da Região das Soluções Admissíveis que
maximiza o valor da função objectivo. Este ponto encontra-se por tentativas após atribuir um valor à
função objectivo e desenhar a recta correspondente a esse valor. Seguidamente, por observação
do gráfico e tentativas atinge(m)-se o(s) ponto(s) pretendido(s).

Z = 20
Z = 36 = 3x1 + 5x2
Neste caso a solução óptima corresponde a um lucro
de 36 000 u.m. distribuído por 2 elementos do
produto 1 e 6 elementos do produto 2.
Z = 10
x1
Cecília Rocha # 6
2001/2002
INVESTIGAÇÃO OPERACIONAL

2ª Aula (cont.)

Modelo de Programação Linear

Os termos chave deste modelo são os Recursos disponíveis e as Actividades a desenvolver, em que
m será o número de diferentes recursos que poderão ser utilizados e n o número de actividades a
considerar.

Exemplo de recursos:






Exemplo de actividades:




Cecília Rocha # 7
Dinheiro
Equipamentos
Máquinas
Veículos
Pessoal
Investimento em projectos
Operações de marketing
Transporte de bens
O tipo mais comum de problemas desta natureza (programação linear) corresponde a distribuir recursos
por actividades. A quantidade de recursos disponíveis é limitada, por isso, é importante fazer uma
distribuição de recursos cuidada, correspondente ao nível de actividade pretendido para atingir o melhor
desempenho possível
2001/2002
INVESTIGAÇÃO OPERACIONAL

2ª Aula (cont.)

Modelo de Programação Linear (cont.)

Neste modelo utilizam-se as seguintes variáveis:

Z – Valor da medida de desempenho
xj – nível de actividade pretendido
cj – aumento do desempenho resultante do aumento de uma unidade no nível de actividade
bi – quantidade de recurso i disponível para as diferentes actividades
aij – quantidade de recurso i utilizado por unidade de actividade j

xi são as variáveis de decisão




Recursos
1
2
...
m
Contribuição para Z por
unidade de actividade
Cecília Rocha # 8

cj, bi e aij são os parâmetros
Utilização de Recursos por unidade de actividade
Actividades
1
2
...
n
a11
a12
a1n
a21
a22
a2n
am1
am2
c1
c2
amn
...
Quantidade de recursos
disponível
b1
b2
...
bm
cn
2001/2002
INVESTIGAÇÃO OPERACIONAL

2ª Aula (cont.)

Modelo de Programação Linear (cont.)

Forma Standard

Função Objectivo


Restrições





Cecília Rocha # 9
Maximizar Z = c1 x1 + c2 x2 + ... + cn xn
a11 x1 + a12 x2 + ... + a1n xn  b1
a21 x1 + a22 x2 + ... + a2n xn  b2
...
am1 x1 + am2 x2 + ... + amn xn  bm
x1  0 ; x2  0 ; ... ; xn  0
2001/2002
INVESTIGAÇÃO OPERACIONAL

2ª Aula (cont.)

Modelo de Programação Linear (cont.)

Outras Formas

Minimizar a função objectivo

Algumas das restrições tomam a forma:


Algumas das restrições tomam a forma:


Cecília Rocha # 10
ai1 x1 + ai2 x2 + ... + ain xn  bi
ai1 x1 + ai2 x2 + ... + ain xn = bi
Algumas das variáveis não cumprem a restrição de não negatividade
2001/2002
INVESTIGAÇÃO OPERACIONAL

2ª Aula (cont.)

Modelo de Programação Linear (cont.)

Termos mais utilizados

Solução Admissível (todas as restrições são satisfeitas)

Solução Não Admissível (pelo menos uma restrição não é satisfeita)

Região Admissível (conjunto de todas as soluções admissíveis)

Solução Óptima (é a solução admissível que conduz ao maior valor possível no caso da maximização e ao
menor valor possível para a minimização)

Solução Admissível em Ponto de Quebra (solução num canto da região admissível)

Relação entre Soluções Óptimas e Soluções Admissíveis em Pontos de Quebra



Cecília Rocha # 11
Considerando um problema de programação linear com soluções admissíveis e uma região admissível
limitada, então, o problema tem soluções admissíveis em pontos de quebra e uma delas será a solução
óptima.
Se o problema tem uma solução óptima ela será um ponto de quebra
Se o problema tem soluções múltiplas pelo menos duas serão pontos de quebra
2001/2002
INVESTIGAÇÃO OPERACIONAL

2ª Aula (cont.)

Exercício
Uma indústria de fabrico de televisores tem de decidir o número de
aparelhos de TV de 20” e 27” a produzir nas suas instalações.
A pesquisa de mercado efectuada indica que, no máximo, podem ser vendidas 40 unidades
de 27” e 10 unidades de 20” por mês. O número máximo de horas disponíveis para a
produção é de 500 horas mensais. Um televisor de 27” demora 20 horas de trabalho e o de
20” requer 10 horas de trabalho. Cada televisor de 27” vendido permite obter um lucro de
120 u.m. e o de 20” um lucro de 80 u.m.. Um vendedor concordou em comprar todos os
televisores produzidos se o seu número não exceder o máximo indicado na pesquisa de
mercado.
a) Formular um modelo de programação linear para este problema.
b) Resolver este problema pelo método gráfico.
Cecília Rocha # 12
2001/2002
INVESTIGAÇÃO OPERACIONAL

2ª Aula (cont.)
Exercício
A direcção escolar de uma cidade tomou a decisão de fechar uma das suas escolas
secundárias (6º, 7º e 8º ano) no fim do ano escolar, distribuindo os seus alunos pelas outras
escolas. A direcção regional providenciará o transporte de todos os estudantes que tenham de
percorrer um trajecto superior a 1 milha, por isso, a direcção escolar pretende definir um plano de
distribuição dos alunos que minimize o custo total de transporte.
O custo anual do transporte por aluno de cada uma das 6 áreas residenciais para cada uma
das escolas é dado no quadro seguinte, em que 0 indica que não há necessidade de transporte e –
que não é possível efectuar o transporte.
Custo de Transporte por Aluno (u.m.)
Área
N.º Alunos
% no 6º Ano
% no 7º Ano
% no 8º Ano
Escola 1
Escola 2
Escola 3
1
450
32
38
30
300
0
700
2
600
37
28
35
-
400
500
3
550
30
32
38
600
300
200
4
350
28
40
32
200
500
-
5
500
39
34
27
0
-
400
6
450
34
28
38
500
300
0
900
1 100
1 000
Capacidade da Escola
Cecília Rocha # 13
2001/2002
INVESTIGAÇÃO OPERACIONAL

2ª Aula (cont.)

Exercício (cont.)
A direcção escolar também impôs restrições na percentagem de alunos que integram cada
ano escolar, devendo esta percentagem situar-se entre 30 e 35% do total de alunos de cada escola.
O quadro anterior indica as percentagens de alunos que frequentarão cada nível de escolaridade no
próximo ano lectivo. Os alunos de cada área poderão ser distribuídos por mais do que uma escola,
mantendo-se a proporcionalidade de alunos em cada ano.
a) Formule um modelo de programação linear para este problema
Cecília Rocha # 14
2001/2002