INVESTIGAÇÃO OPERACIONAL

3ª Aula

Propriedades da Programação Linear

Proporcionalidade



A contribuição de cada actividade para o valor da função objectivo é proporcional ao nível de
actividade xj (representado pelo termo cjxj)
A contribuição de cada actividade, no lado esquerdo da equação das restrições, é proporcional
ao nível de actividade xj (representada pelo termo aixj)
Não pode haver expoentes superiores a um.
Exemplos de violação da propriedade da Proporcionalidade
Z
Z
Custo Inicial C0
3 x1
Aumento da taxa de
retorno marginal
3 x1
Z
Diminuição da taxa
de retorno marginal
3 x1
3 x1- C0
C0
Cecília Rocha # 1
x1
x1
x1
2001/2002
INVESTIGAÇÃO OPERACIONAL

3ª Aula (cont.)

Propriedades da Programação Linear (cont.)

Aditividade

Todas as funções, num modelo de programação linear (seja a função objectivo ou qualquer das
restrições), é a soma das contribuições individuais das respectivas actividades.
Exemplos de violação da propriedade da Aditividade
Valor de Z
(x1, x2)
Aditividade
satisfeita
Quantidade de Recursos Utilizados
Aditividade Violada
Caso 1
Caso 2
(x1, x2)
Aditividade
satisfeita
Aditividade Violada
Caso 3
Caso 4
(1,0)
3
3
3
(1,0)
3
3
3
(0,1)
5
5
5
(0,1)
5
5
5
(1,1)
8
9
7
(1,1)
8
9
7
3x1 + 5x2
3x1 + 5x2 + x1.x2
3x1 + 5x2 - x1.x2
3x1 + 5x2  18
3x1 + 5x2 + 0.5 x1.x2
3x1 + 5x2 – 0.1 x12.x2
aumento no lucro por
complementaridade
dos produtos
Cecília Rocha # 2
diminuição no lucro
por competitividade
entre produtos
Tempo de produção
perdido na transição
entre produtos
Existem tempos
de inactividade
2001/2002
INVESTIGAÇÃO OPERACIONAL

3ª Aula (cont.)

Propriedades da Programação Linear

Divisibilidade


Certeza


Cecília Rocha # 3
As variáveis de decisão, num modelo de programação linear, podem tomar qualquer valor maior ou
igual a zero, incluindo valores não inteiros. Estas variáveis não se restringem a valores inteiros.
Como cada variável de decisão representa um nível de actividade, assume-se que as actividades
possam decorrer em níveis parciais.
O valor atribuído a cada parâmetro de um modelo de programação linear é uma constante
conhecida.
Na realidade, esta propriedade raramente é satisfeita. Os valores dos parâmetros utilizados
baseiam-se em projecções para situações futuras, o que induz algum grau de incerteza. Por esta
razão, é muito importante a realização de uma análise de sensibilidade após a implementação do
novo sistema para avaliar a qualidade dos resultados.
2001/2002
INVESTIGAÇÃO OPERACIONAL

3ª Aula (cont.)

Exemplos de aplicação de modelos de Programação Linear

Definição de um Plano de Radioterapia


Este tratamento envolve a utilização de 2 feixes de radiação que terão de passar pelo corpo de um paciente de
forma a matar as células malignas. Devido à atenuação da propagação dos feixes no interior do corpo, cada feixe
liberta mais radiação próximo da entrada do feixe do que do lado de saída. A dispersão do feixe também implica
que seja afectado algum tecido fora do percurso do feixe. Assim, deverá ser estudada a intensidade do feixe de
forma a maximizar a sua capacidade destrutiva de células malignas mas sem ultrapassar os valores
estabelecidos como de segurança para evitar outros tipos de complicações.
O objectivo é definir a melhor combinação de feixes e a sua intensidade para gerar a melhor distribuição
possível das doses de radiação.
Área
Cecília Rocha # 4
Fracção da Dose de entrada
absorvida por Área
Restrições na dose
total média, krad
Feixe 1
Feixe 2
Tecidos saudáveis
0.4
0.5
Minimizar
Tecidos críticos
0.3
0.1
 2.7
Região do tumor
0.5
0.5
=6
Centro do tumor
0.6
0.4
6
Minimizar Z = 0.4 x1 + 0.5 x2
s.a.:
0.3 x1 + 0.1 x2  2.7
0.5 x1 + 0.5 x2 = 6
0.6 x1 + 0.4 x2  6
xi  0
2001/2002
INVESTIGAÇÃO OPERACIONAL

3ª Aula (cont.)
Cecília Rocha # 5

Planeamento Regional

Controlo da Poluição do Ar

Deposição de Resíduos Sólidos

Distribuição de Pessoal

Rede de Distribuição de Produtos
2001/2002
INVESTIGAÇÃO OPERACIONAL

3ª Aula (cont.)

Exercício 3.4.5
Considere o seguinte problema onde o valor de c1 ainda não foi determinado.
Maximizar Z = c1 x1 + 2 x2
s.a.:
4 x1 + x2  12
x1 – x2  2
xi  0
Utilize o método gráfico para determinar as soluções óptimas (x1, x2) para os vários valores de c( possíveis
Cecília Rocha # 6
2001/2002
INVESTIGAÇÃO OPERACIONAL

3ª Aula (cont.)

Exercício 3.4.20
Joyce e Mary dirigem uma instituição de ensino pré- escolar e estão a tentar decidir a melhor escolha em
termos de alimentação das crianças. Como gostavam de manter os seus custos baixos mas, ao mesmo tempo,
gostavam de satisfazer as necessidades nutricionais das crianças, tendo seleccionado os seguintes alimentos:
manteiga de amendoim e sandes com compota ou uma combinação de bolachas, leite e sumo de laranja. O
conteúdo nutricional de cada tipo de alimento e o seu custo estão indicados na tabela seguinte:
Alimento
Cecília Rocha # 7
Calorias(Gordura)
Total de calorias
Vitamina C (mg)
Proteínas (g)
Custo ($)
Pão (1 fatia)
10
70
0
3
5
Manteiga de Amendoim
75
100
0
4
4
Compota Morango
0
50
3
0
7
Bolacha
20
60
0
1
8
Leite (1 copo)
70
150
2
8
15
Sumo de Laranja
0
100
120
1
35
2001/2002
INVESTIGAÇÃO OPERACIONAL

3ª 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 # 8
2001/2002
INVESTIGAÇÃO OPERACIONAL

3ª 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
b) Para cada uma das 4 propriedades do modelo de programação linear, analise a sua
aplicabilidade




Cecília Rocha # 9
Proporcionalidade
Aditividade
Divisibilidade
Certeza
2001/2002
INVESTIGAÇÃO OPERACIONAL

3ª Aula (cont.)

Exercício (cont.)
c) Utilize o programa SOLVER – Excel, para resolver o problema formulado na alínea a)
Após a análise dos resultados obtidos anteriormente, a direcção escolar exprimiu alguma
preocupação na divisão por várias escolas de estudantes provenientes da mesma área de
residência. Assim, solicitou uma nova avaliação da situação, na tentativa de manter “os vizinhos
todos juntos”.
d) Ajuste os resultados obtidas na alínea c) às novas condicionantes impostas.
Quanto iria aumentar o custo do transporte?
A direcção escolar está a considerar a eliminação de algumas linhas de transporte para
reduzir os custos. A 1ª opção é eliminar o transporte para os estudantes que têm de viajar entre 1.6
km e 2.4 km, cujo custo por aluno é de $200. A 2ª opção é também eliminar o transporte dos alunos
que têm de viajar entre 2.4 km e 3.2 km, para os quais se estima um custo de $300.
Cecília Rocha # 10
2001/2002