Modelizaçãomac/ensino/docs/TMDMarco2005/... · 2005-03-01 · Slide 1 Modelização ... ou ser criticado por naõ fazer, aquilo para que naõ foi criado. ... Passo II —

Slide 1

Modelizacao

Tomar Melhores Decisoes usando metodos quantitativos e folhas de calculo

Versao 3

c©2005, 2000, 1998

Jose Fernando Oliveira, Maria Antonia Carravilla – FEUP

Modelizacao 1

Slide 2

ModelizacaoOs 10 princıpios

• Nao criar um modelo complicado quando um simples e suficiente.

• Nao moldar o problema a tecnica de resolucao que se pretende utilizar.

• Resolver rigorosamente o modelo encontrado. So assim se sabera se hipoteticas

inconsistencias das solucoes do modelo com a realidade tem origem no proprio

modelo ou nao.

• Validar os modelos antes de os implementar.

• O modelo nao deve ser tomado literalmente pois nunca e a realidade.

• O modelo nao deve ser forcado a fazer, ou ser criticado por nao fazer, aquilo para

que nao foi criado.

• Nao sobrestimar os modelos.

• Uma das principais vantagens da modelizacao e o processo de desenvolvimento do

modelo.

• Um modelo nao pode ser melhor do que a informacao usada na sua construcao.

• Os modelos nunca substituem os agentes de decisao.

Slide 3

Formulacao de modelos matematicos em Investigacao

Operacional

Algoritmo para construir um modelo matematico para um problema de

Investigacao Operacional:

Passo I — Determinar, no problema concreto, aquilo que e fixo e nao pode

ser alterado e aquilo que se pode decidir (variaveis de decisao).

Representar essas variaveis de uma forma algebrica.

Passo II — Identificar as restricoes do problema, isto e, aquilo que limita

as nossas decisoes, e representa-las como igualdades ou desigualdades

que sejam funcoes das variaveis de decisao.

Passo III — Identificar o(s) objectivo(s) do problema e representa-lo(s)

como uma funcao das variaveis de decisao, que deve ser minimizada ou

maximizada.

Nota: So existe problema quando ha mais do que uma solucao admissıvel.


Modelizacao 2

Slide 4

Problema de Mistura de Produtos

A companhia Electro & Domesticos pretende escalonar a producao de um

novo apetrecho de cozinha que requer dois recursos: mao-de-obra e

materia-prima. A companhia considera a hipotese de 3 modelos diferentes,

tendo o seu departamento de engenharia fornecido os seguintes dados:

Modelo A B C

Mao-de-obra (horas por unidade) 7 3 6

Materia-prima (quilos por unidade) 4 4 5

Lucro ($ por unidade) 4 2 3

O fornecimento de materia-prima esta limitado a 200 quilos/dia. Por dia

estao disponıveis 150 horas de trabalho. O objectivo e maximizar o lucro

total. Formule o modelo que permitiria resolver este problema.

Slide 5

Problema de Mistura de Produtos

Resolucao

Passo I — O que se desconhece, e que se pretende determinar na fase de

resolucao do modelo, sao as quantidades a produzir diariamente de cada

um dos modelos — as variaveis de decisao.

Representando-as algebricamente:

xA − producao diaria do modelo A (no de unidades)

xB − producao diaria do modelo B (no de unidades)

xC − producao diaria do modelo A (no de unidades)

Passo II — Restricoes do problema.

Nao podemos produzir quantidades infinitas de A, B e C (o que daria

um lucro infinito) porque estamos limitados pela materia-prima (200) e

mao-de-obra (150) disponıveis, valores que nao podemos exceder.

Entao, a mao-de-obra necessaria para produzir uma unidade do modelo

A (7 horas), vezes o numero de unidades do modelo A a produzir (xA),


Modelizacao 3

Slide 6

mais a mao-de-obra necessaria para produzir uma unidade do modelo B

(3 horas), vezes o numero de unidades do modelo B que se resolva

produzir (xB), mais a mao-de-obra necessaria para produzir uma

unidade do modelo C (6 horas), vezes o numero de unidades do modelo

C que se venha a produzir (xC), nao poderao exceder as 150 horas, isto

e:

7xA + 3xB + 6xC ≤ 150

Aplicando o mesmo raciocınio a materia-prima, obter-se-ia:

4xA + 4xB + 5xC ≤ 200

As restricoes que faltam ao problema dizem directamente respeito as

variaveis de decisao, e sao:

xA ≥ 0, xB ≥ 0, xc ≥ 0

ou seja, nao se podem produzir quantidades negativas.

Passo III — O objectivo do problema e maximizar o lucro total, isto e, o

lucro obtido com os 3 modelos. Como cada unidade do modelo A da um

Slide 7

lucro de 4, do modelo B da 2 e do modelo C da 3, a funcao objectivo

sera:

max LUCRO = 4xA + 2xB + 3xC

O modelo do nosso problema sera entao:

Encontrar os numeros xA, xB e xC tais que:

max LUCRO = 4xA + 2xB + 3xC

sujeito a:

7xA + 3xB + 6xC ≤ 150

4xA + 4xB + 5xC ≤ 200

xA, xB , xC ≥ 0


Modelizacao 4

Slide 8

Problema da refinaria de petroleo

Uma refinaria de petroleo pode misturar 3 tipos de crude para produzir

gasolina normal e super. Existem disponıveis duas unidades de mistura.

Para cada ciclo de producao a unidade mais antiga usa 5 barris de crude A,

7 barris de crude B e 2 barris de crude C para produzir 9 tanques de

gasolina normal e 7 de gasolina super. A unidade de mistura mais recente

usa 3 barris de crude A, 9 de B e 4 de C para produzir, num ciclo de

producao, 5 tanques de gasolina normal e 9 de super.

Devido a contratos ja assinados, a refinaria tem que produzir, pelo menos,

500 tanques de normal e 300 tanques de super. Existem disponıveis 1500

barris de crude A, 1900 de crude B e 1000 de crude C. Por cada tanque de

gasolina normal produzida a refinaria ganha 6 unidades monetarias e, por

tanque de super, 9 unidades monetarias.

O problema e saber como utilizar as reservas de crude e as duas unidades de

mistura, de forma a, respeitando os compromissos assumidos, maximizar o

lucro da refinaria.

Slide 9

Problema da refinaria de petroleo

Resolucao

Variaveis de decisao

x1 − no de ciclos de producao a realizar na unidade antiga

x2 − no de ciclos de producao a realizar na unidade nova


Modelizacao 5

Slide 10

Restricoes

Crude disponıvel:

Tipo A: 5x1︸︷︷︸

gasto na

unidade

antiga

+ 3x2︸︷︷︸

gasto na

unidade

nova

≤ 1500

Tipo B: 7x1 + 9x2 ≤ 1900

Tipo C: 2x1 + 4x2 ≤ 1000

Contratos assinados:

Gasolina normal: 9x1︸︷︷︸

produzido

na unidade

antiga

+ 5x2︸︷︷︸

produzido

na unidade

nova

≥ 500

Gasolina super: 7x1 + 9x2 ≥ 300

Slide 11

E ainda:

x1, x2 ≥ 0

Funcao objectivo

max LUCRO =

gasolina normal︷︸︸︷

6 × ( 9︸︷︷︸

no de

tanques

por ciclo

x1︸︷︷︸

no de

ciclos

︸︷︷︸

unidade antiga

+ 5x2︸︷︷︸

unidade nova

) +

gasolina super︷︸︸︷

9 × (7x1 + 9x2)


Modelizacao 6

Slide 12

Arrendamento de espaco num armazem

Uma empresa planeia arrendar espaco num armazem, sendo as suas

necessidades para os proximos 5 meses as seguintes:

Mes Necessidade de

espaco (m2)

1 1500

2 1000

3 2000

4 500

5 2500

Perıodo de arrendamento Custo por m2

(meses) ($)

1 2800

2 4500

3 6000

4 7300

5 8400

Construa um modelo que permita determinar o esquema de contratos a

assinar, por forma a satisfazer as necessidades de espaco o mais

economicamente possıvel.

Slide 13


Resolucao


xij − espaco a arrendar no inıcio do mes i por um perıodo de j meses

Restricoes

Que em cada mes esteja arrendado pelo menos o espaco necessario:

(mes 1)∑5

j=1 x1j ≥ 1500

(mes 2)∑5

j=2 x1j +∑4

j=1 x2j ≥ 1000

(mes 3)∑5

j=3 x1j +∑4

j=2 x2j +∑3

j=1 x3j ≥ 2000

(mes 4)∑5

j=4 x1j +∑4

j=3 x2j +∑3

j=2 x3j +∑2

j=1 x4j ≥ 500

(mes 5) x15 +x24 +x33 +x42 +x51 ≥ 2500

xij ≥ 0

1≤i≤5, 1≤j≤6−i


Modelizacao 7

Slide 14

Funcao objectivo

min CUSTO =

custo de arrendar

1 m2 por 1 mes

︷︸︸︷

2800

espaco arrendado

por 1 mes

(no inıcio do mes

1, 2, 3, 4 ou 5)

︷︸︸︷

5∑

i=1

xi1 + 4500

4∑

i=1

xi2 + 6000

3∑

i=1

xi3

+ 7300

2∑

i=1

xi4 + 8400x15

Slide 15


Resolucao mais compacta

Dados

Cj − custo de arrendar 1m2 por um perıodo de j meses

Ni − necessidade de espaco no mes i


xij − espaco a arrendar no inıcio do mes i por um perıodo de j meses

Restricoes

Que em cada mes esteja arrendado pelo menos o espaco necessario:

∀i

∑6−i

j=1 xij +∑i−1

k=1

∑6−k

j=i+1−k xkj ≥ Ni


Modelizacao 8

Slide 16

Funcao objectivo

5∑

j=1

Cj ×

6−j∑

i=1

xij

Slide 17

A companhia de aviacao Benvoa

A companhia de aviacao Benvoa vai comprar avioes a jacto de passageiros, para viagens

longas, medias e curtas (tipos Al, Am e Ac, respectivamente). Os custos unitarios, em

milhoes de escudos sao, respectivamente, de 5000, 3800 e 2000. A administracao da

companhia autorizou a verba maxima de 112000 milhoes de escudos para esse efeito.

Admite-se que os lucros anuais sejam de 310, 230 e 200 milhoes de escudos com cada um

dos tipos de aviao Al, Am e Ac, respectivamente. Havera pilotos suficientes para pilotar,

no maximo, 30 avioes novos. Se apenas fossem comprados avioes Ac, os servicos de

manutencao suportariam 40 avioes novos. Contudo, cada aviao Am equivale a 4/3 de um

aviao Ac e cada aviao Al a 5/3 de um aviao Ac, no que diz respeito a manutencao. A

direccao tecnica e ainda de opiniao que, por cada aviao Ac que seja comprado, se

comprem tambem pelo menos um aviao Al ou um aviao Am. Por outro lado, seleccionado

um aviao Al para comprar, tambem deverao ser comprados pelo menos 8 avioes Ac ou

Am. Com estes dados, a gestao da empresa deve decidir a quantidade de avioes de cada

tipo a comprar, de modo a maximizar o lucro. Formule um modelo para este problema.


Modelizacao 9

Slide 18

A companhia de aviacao Benvoa

Resolucao


xc, xm, xl − no de avioes de cada tipo a comprar

Restricoes

Dinheiro disponıvel: 500xl + 3800xm + 2600xc ≤ 112000

Pilotos disponıveis: xl + xm + xc ≤ 30

Manutencao: 53xl +

43xm + xc ≤ 40

Opiniao da direccao tecnica: xl + xm ≥ xc

xc + xm ≥ 8xl

xc, xm, xl ≥ 0

e inteiros

Slide 19

Funcao objectivo

max LUCRO = 310xl + 230xm + 200xc


Modelizacao 10

Slide 20

Problema de planeamento integrado da producao de

duas fabricas

Duas fabricas, A e B, situadas em locais diferentes produzem ambas os

produtos P1 e P2. A fabrica A tem 3 maquinas e a fabrica B tem 2

maquinas. Todas as maquinas fazem os produtos P1 e P2. Depois de

fabricados, os produtos podem ser transportados entre as fabricas de modo a

satisfazer a procura. O numero de unidades produzidas por dia, os custos de

producao e de transporte, a procura dos produtos e o numero de dias em que

cada maquina esta disponıvel por mes estao indicados nas tabelas seguintes:

Fabrica A B

Maquina M1 M2 M3 M1 M2

Disponibilidade (dias) 30 28 24 26 28

Produto P1 P2 P1 P2 P1 P2 P1 P2 P1 P2

Producao por dia 40 35 42 38 40 37 41 37 42 40

Custo por dia 100 102 104 106 98 104 102 105 103 106

Capacidades de producao das fabricas

Slide 21

Produto P1 P2

Fabrica A B A B

Procura 1200 800 1500 1100

Custo de transporte A→ B = 4 B→ A = 4 A→ B = 3 B→ A = 4

por unidade

Procura e custos de transporte dos produtos

Pretende-se saber qual o esquema de utilizacao das maquinas em cada fabrica e de

distribuicao dos produtos entre as fabricas a que corresponde um custo total

mınimo.


Modelizacao 11

Slide 22

Problema de planeamento integrado da producao de

duas fabricas

Resolucao

• Indices

i fabricas (A e B) i ∈ [1, 2];

j maquinas (M1,M2,M3) j ∈ [1, 2, 3];

k produtos (P1 e P2) k ∈ [1, 2].

• Variaveis de decisao

xijk numero de dias de producao durante um mes do produto k, na

fabrica i, maquina j;

yik quantidade do produto k a transportar a partir da fabrica i;

zik quantidade do produto k a transportar para a fabrica i.

• Coeficientes

Slide 23

cijk custo diario de producao do produto k, na fabrica i, maquina j;

pijk producao diaria do produto k, na fabrica i, maquina j;

mij disponibilidade (em dias) da maquina j da fabrica i;

dik procura na fabrica i do produto k;

sik custo de transporte, a partir da fabrica i do produto k;

tik custo de transporte, para a fabrica i do produto k.

• Modelo

Objectivo

minCusto =∑

i,j,k

cijkxijk +∑

i,k

sikyik +∑

i,k

tikzik (1)

∀i,k

∑

j pijkxijk − yik + zik = dik (2)

∀i,j

∑

k xijk ≤ mij (3)

∀k z1k ≤∑

j

p2jkx2jk (4)


Modelizacao 12

Slide 24

∀k z2k ≤∑

j

p1jkx1jk (5)

∀i,j,k xijk, yik, zik ≥ 0 (6)

As restricoes 2 garantem que a procura do produto k na fabrica i e

satisfeita. As restricoes 3 sao restricoes de capacidade (disponibilidade)

das maquinas. As restricoes 4 e 5 garantem que so se transporta a partir

de uma fabrica o que e produzido nessa fabrica. Finalmente as restricoes

6 garantem que todas as variaveis tomam valores maiores ou iguais a

zero.

Slide 25

Fabrica de papel

O papel e normalmente fabricado em rolos grandes (em largura e em

diametro), que depois sao dividos em rolos mais pequenos, que por sua vez

poderao ser directamente para clientes ou para cortar em formatos.

Vejamos o seguinte exemplo. O papel e produzido em rolos com 6 metros de

largura. A partir deste rolos e necessario produzir 30 rolos mais pequenos

com 280cm, 60 rolos com 200cm e 48 rolos com 150cm. Assim sendo, um

rolo de 6 metros pode ser dividido, por exemplo, em 2 rolos de 280,

sobrando um “rolinho” de 40cm que e considerado desperdıcio. Assumindo

que existem rolos grandes em quantidade suficiente para satisfazer esta

encomenda, o problema consiste em determinar a forma de cortar os rolos

grandes de forma a minimizar o desperdıcio.


Modelizacao 13

Slide 26

Fabrica de papel — Bobinadora

Slide 27

Fabrica de papel

Resolucao

O primeiro passo para a formulacao deste problema e determinar de quantas

maneiras pode um rolo grande ser cortado. Para alem da forma sugerida no

enunciado (2 rolos de 200cm, sobrando 40cm de desperdıcio) podem ainda

ser determinados 6 outros “padroes de corte” (ver tabela). As variaveis de

decisao (x1 a x7) correspondem ao numero de vezes que cada padrao de

corte e aplicado no corte de um rolo grande. A tabela seguinte apresenta

ainda as quantidades pedidas de cada rolo pequeno, assim como o

desperdıcio gerado por cada padrao de corte.


Modelizacao 14

Slide 28

Largura No de rolos

dos rolos x1 x2 x3 x4 x5 x6 x7 pedidos

280 2 1 1 0 0 0 0 30

200 0 1 0 3 2 1 0 60

150 0 0 2 0 1 2 4 48

Desperdıcio 40 120 20 0 50 100 0

Exemplificando, x3 = 4 significa que se corta um rolo grande em 1 de 280cm

e 2 de 150cm, gerando um desperdıcio de 20cm, 4 vezes. No total obtem-se 4

rolos de 280cm e 8 de 150cm (e nenhum de 200cm).

As restricoes vao estar directamente relacionadas com as quantidades de

rolos pequenos que e necessario cortar, uma por cada rolo. Se a cada linha

do sistema de inequacoes corresponde um tipo de rolo pequeno, a cada

coluna correspondera um padrao de corte:

Slide 29

2x1 + x2 + x3 ≥ 30

x2 + 3x4 + 2x5 + x6 ≥ 60

2x3 + x5 + 2x6 + 4x7 ≥ 48

xi ≥ 0 ∀1≤i≤7

O objectivo do problema e minimizar o desperdıcio. Assim, a funcao

objectivo deste modelo tomara a forma:

min 40x1 + 120x2 + 20x3 + 50x5 + 100x6

E se as restricoes tiverem que ser satisfeitas como igualdades, isto e, e se nao

forem admitidas sobreproducoes? Como e que o modelo deve ser alterado?


Modelizacao 15

Slide 30

Aeroporto Aletrop - Manutencao

O aeroporto de Aletrop e a base dos avioes da companhia aerea PAT. Trata-se de um

aeroporto moderno, e de uma empresa de aviacao em expansao, que pretende manter a

sua competitividade num sector de actividade fortemente concorrencial. O aumento de

competitividade passa, nomeadamente, pela realizacao de dois objectivos, a melhoria da

qualidade de servico e a reducao dos custos de operacao. Por outro lado, a seguranca de

uma companhia aerea e um aspecto de primordial importancia, estando intimamente

ligado a manutencao. Para manter um aviao em boas condicoes tecnicas, procede-se a

manutencao preventiva aos aparelhos da PAT, atraves de pequenas inspeccoes entre

aterragem e posterior descolagem. A direccao da empresa esta tambem a considerar a

hipotese de oferecer estes servicos de manutencao a outras companhias de aviacao, mesmo

que para tal tenha que aumentar as equipas de manutencao. O elemento crucial nestas

equipas e o chefe de manutencao, tecnico altamente qualificado, que necessita de fazer

formacao especıfica para cada tipo de aviao e obter assim uma licenca imprescindıvel para

o desempenho dessas funcoes. A cada licenca corresponde uma categoria de avioes,

existindo 4 licencas diferentes:

Tipos de licencas Avioes

1 Boeing 717 (100 lugares)

2 Boeing 777 (300 a 500 lugares)

3 Airbus A319 (124 lugares)

4 Airbus A340 (350 lugares)

Slide 31

Cada tecnico pode ter no maximo 2 licencas. A primeira licenca demora varios anos a

obter, sendo portanto mais cara para a empresa, enquanto a segunda licenca demora

menos anos a obter, ficando naturalmente mais barata. O custo da segunda licenca

depende ainda da licenca anterior que o tecnico possui. Actualmente existem 9 equipas de

manutencao, cada uma chefiada por um tecnico licenciado, que funcionam em 3 turnos.

Custo (M$)

Licenca Licenca a tirar

anterior

1 2 3 4

0 2 4 2 4

1 - 1 2 3

2 1 - 2 3

3 1 3 - 2

4 1 2 1 -

Turno Chefe de equipa Tipo de licenca

1 1, 2

1 2 1

3 2

4 3, 4

2 5 2

6 3

7 4

3 8 3, 4

9 3

Para poder oferecer servicos a outras companhias de aviacao, a empresa pretende que

existam 4 licencas de cada tipo, no conjunto dos chefes de manutencao. Isto pode ser

conseguido enviando para formacao actuais chefes de equipa (portanto tecnicos que ja

possuem 1 licenca) ou outros tecnicos que ainda nao possuem nenhuma licenca. No

entanto, de cada turno so podera sair, no maximo, 1 chefe de equipa para formacao.

Escreva um modelo de programacao matematica que permita determinar a polıtica de

obtencao de licencas que minimiza os custos para a Aletrop.


Modelizacao 16

Slide 32

Aeroporto Aletrop - Manutencao

Resolucao


xij =

1 se tecnico i tira licenca j

0 se nao

A empresa pretende que existam 4 licencas de cada tipo, num total de 16

licencas. Como, no conjunto dos chefes de manutencao existentes, ja existem

12 licencas, sao necessarias mais 4 licencas, que no limite poderao ser todas

obtidas por tecnicos novos. Nesse caso o numero maximo de tecnicos, ındice

i na formulacao, sera igual a 13, 9 ja existentes e 4 novos.

Slide 33

Restricoes

A empresa pretende que existam 4 licencas de cada tipo, no conjunto dos

chefes de manutencao:∑13

i=1 xi1 = 2∑13

i=1 xi2 = 1∑13

i=1 xi3 = 0∑13

i=1 xi4 = 1

Um tecnico pode ter no maximo 2 licencas e os tecnicos novos so poderao

obter nesta fase uma licenca:

(esta restricao nao vem referida explicitamente no enunciado, no entanto pode-se inferir

que nao havera disponibilidade de tempo para que um tecnico novo obtenha duas licencas)

∑4j=1 xij ≤ 1 ∀i∈{2,3,5,6,7,9,10,11,12,13}

∑4j=1 xij = 0 ∀i∈{1,4,8}


Modelizacao 17

Slide 34

De cada turno so podera sair, no maximo, 1 chefe de equipa para formacao:∑4

j=1

∑3i=1 xij ≤ 1

∑4j=1

∑6i=4 xij ≤ 1

∑4j=1

∑9i=7 xij ≤ 1

Cada tecnico so pode obter 1 vez a mesma licenca:

x21 = x32 = x52 = 0

x63 = x74 = x93 = 0

Funcao objectivo

ckj = custo de tirar licenca j dado que ja se tem licenca k

min

4∑

j=1

13∑

i=10

c0jxij +∑

i∈{6,9}

c3jxij +∑

i∈{3,5}

c2jxij + c1jx2j + c4jx7j

Slide 35

Escalonamento de recursos humanos

Parte I

Um posto de correios requer para funcionar um numero diferente de trabalhadores

a tempo inteiro em cada dia da semana:

No mınimo de funcionarios

Segunda 17

Terca 13

Quarta 16

Quinta 19

Sexta 14

Sabado 16

Domingo 11

As leis laborais impoem que cada funcionario trabalhe 5 dias consecutivos,

seguidos de 2 dias de folga. Por exemplo, um funcionario que trabalhe de Segunda

a Sexta tera que estar de folga no Sabado e no Domingo. O posto de correios

pretende pois satisfazer as necessidades diarias de trabalhadores recorrendo apenas


Modelizacao 18

Slide 36

a funcionarios a tempo inteiro. O objectivo e minimizar o numero de funcionarios

a tempo inteiro.

Parte II

Suponha agora que as necessidades de mao-de-obra podem ser satisfeitas quer por

funcionarios a tempo inteiro quer por funcionarios a tempo parcial. Um

funcionario a tempo inteiro trabalha 8 horas por dia, enquanto um funcionario a

tempo parcial trabalha 4 horas por dia, mantendo-se as restantes condicoes

laborais. No entanto, acordos com os sindicatos limitam a 25% do total a

percentagem de funcionarios a tempo parcial. Sabendo que o custo horario de um

funcionario a tempo inteiro e de 15 euros e o de um funcionario a tempo parcial e

de 10 euros, determine o escalonamento dos funcionarios que minimiza o custo

global com recursos humanos.

Parte III

Considere agora que cada funcionario pode fazer um dia de trabalho extraordinario

por semana. Por exemplo, a um funcionario cujo turno de trabalho seja de

Segunda a Sexta pode ser pedido que trabalhe ainda no Sabado. A remuneracao

por hora de trabalho extraordinario corresponde a 150% da remuneracao base.

Parte IV

Considere novamente a situacao inicial, das necessidades de mao-de-obra serem

Slide 37

satisfeitas unicamente por funcionarios a tempo inteiro. Considere ainda que o

posto de correios tem 25 funcionarios contratados. Determine o escalonamento que

maximiza o numero de folgas em dias de fim-de-semana (Sabado ou Domingo).

Parte V

Apesar de se ter minimizado o numero de trabalhadores com turnos de

fim-de-semana, esses turnos existem e tem que ser cobertos. Como resolveria o

problema de, ao longo do ano, garantir uma escala justa e equilibrada para todos

os trabalhadores em termos de dias de fim-de-semana ocupados?


Modelizacao 19

Slide 38

Escalonamento de recursos humanos

Resolucao

Parte I


xi – numero de trabalhadores que comecarao o seu perıodo de 5 dias de

trabalho no dia i, i = 1 . . . 7 (1=Segunda,. . .,7=Domingo)

Restricoes

Em cada dia tem que se ter o numero de funcionarios mınimo a trabalhar.

Note-se que, por exemplo, a Segunda-Feira estao a trabalhar nao so os

funcionarios que iniciam o seu perıodo de 5 dias a Segunda, mas tambem

todos os que iniciaram esse perıodo na semana anterior na Quinta-Feira ou

depois.

Slide 39

x1 + x4 + x5 + x6 + x7 ≥ 17

x1 + x2 + x5 + x6 + x7 ≥ 13

x1 + x2 + x3 + x6 + x7 ≥ 16

x1 + x2 + x3 + x4 + x7 ≥ 19

x1 + x2 + x3 + x4 + x5 ≥ 14

x2 + x3 + x4 + x5 + x6 ≥ 16

x3 + x4 + x5 + x6 + x7 ≥ 11

x1 , x2 , x3 , x4 , x5 , x6 , x7 ≥ 0 e inteiros

Funcao objectivo

minx1 + x2 + x3 + x4 + x5 + x6 + x7


Modelizacao 20

Slide 40

Parte II


Teremos agora que considerar tambem os funcionarios a tempo parcial:

xi – numero de trabalhadores a tempo inteiro que comecarao o seu perıodo

de 5 dias de trabalho no dia i, i = 1 . . . 7 (1=Segunda,. . .,7=Domingo)

yi – numero de trabalhadores a tempo parcial que comecarao o seu perıodo

de 5 dias de trabalho no dia i, i = 1 . . . 7 (1=Segunda,. . .,7=Domingo)

Restricoes

As necessidades de mao-de-obra terao agora que ser expressas em termos de

horas de trabalho e nao de numero de funcionarios.

8x1 + 8

7∑

i=4

xi + 4y1 + 4

7∑

i=4

yi ≥ 136

8

2∑

i=1

xi + 8

7∑

i=5

xi + 4

2∑

i=1

yi + 4

7∑

i=5

yi ≥ 104

Slide 41

8

3∑

i=1

xi + 8

7∑

i=6

xi + 4

3∑

i=1

yi + 4

7∑

i=6

yi ≥ 128

8

4∑

i=1

xi + 8x7 + 4

4∑

i=1

yi + 4y7 ≥ 152

8

5∑

i=1

xi + 4

5∑

i=1

yi ≥ 112

8

6∑

i=2

xi + 4

6∑

i=2

yi ≥ 128

8

7∑

i=3

xi + 4

7∑

i=3

yi ≥ 88

7∑

i=1

yi − 0.25

7∑

i=1

(xi + yi) ≤ 0

∀ixi, yi ≥ 0 e inteiros


Modelizacao 21

Slide 42

Funcao objectivo

min 15 ∗ 8 ∗

7∑

i=1

xi + 10 ∗ 4 ∗

7∑

i=1

yi

Parte III


Teremos que juntar agora novas variaveis correspondentes ao numero de

funcionarios que fazem um dia de trabalho extra.

zi – numero de trabalhadores a tempo inteiro que comecarao no dia i,

i = 1 . . . 7 (1=Segunda,. . .,7=Domingo), o seu perıodo de 5 dias de trabalho

mais um dia de trabalho extra.

wi – numero de trabalhadores a tempo parcial que comecarao no dia i,

i = 1 . . . 7 (1=Segunda,. . .,7=Domingo), o seu perıodo de 5 dias de trabalho

mais um dia de trabalho extra.

Slide 43

Restricoes

8(x1 + z1) + 8z3 + 8

7∑

i=4

(xi + zi) + 4(y1 + w1) + 4w3 + 4

7∑

i=4

(yi + wi) ≥ 136

8

2∑

i=1

(xi + zi) + 8z4 + 8

7∑

i=5

(xi + zi) + 4

2∑

i=1

(yi + wi) + 4w4 + 4

7∑

i=5

(yi + wi) ≥ 104

8

3∑

i=1

(xi + zi) + 8z5 + 8

7∑

i=6

(xi + +zi)4

3∑

i=1

(yi + wi) + 4w5 + 4

7∑

i=6

(yi + wi) ≥ 128

8

4∑

i=1

(xi + zi) + 8z6 + 8x7 + 4

4∑

i=1

(yi + wi) + 4w6 + 4y7 ≥ 152

8

5∑

i=1

(xi + zi) + 8z7 + 4

5∑

i=1

(yi + wi) + 4w7 ≥ 112

8z1 + 8

6∑

i=2

(xi + zi) + 4w1 + 4

6∑

i=2

(yi + wi) ≥ 128

8z2 + 8

7∑

i=3

(xi + zi) + 4w2 + 4

7∑

i=3

(yi + wi) ≥ 88


Modelizacao 22

Slide 44

7∑

i=1

yi − 0.25

7∑

i=1

(xi + yi) ≤ 0

∀ixi, yi, zi, wi ≥ 0 e inteiros

Funcao objectivo

min 15∗8∗5∗7∑

i=1

xi+10∗4∗57∑

i=1

yi+15∗8∗(5+1.5)7∑

i=1

zi+10∗4∗(5+1.5)7∑

i=1

wi

Parte IV


xi – numero de trabalhadores que comecarao o seu perıodo de 5 dias de

trabalho no dia i, i = 1 . . . 7 (1=Segunda,. . .,7=Domingo)

Restricoes

Em cada dia tem que se ter o numero mınimo de funcionarios a trabalhar e

nao se pode ter mais que 25 funcionarios a trabalhar. No seu conjunto as

escalas tem que incorporar 25 funcionarios.

Slide 45

x1 + x4 + x5 + x6 + x7 ≥ 17

x1 + x2 + x5 + x6 + x7 ≥ 13

x1 + x2 + x3 + x6 + x7 ≥ 16

x1 + x2 + x3 + x4 + x7 ≥ 19

x1 + x2 + x3 + x4 + x5 ≥ 14

x2 + x3 + x4 + x5 + x6 ≥ 16

x3 + x4 + x5 + x6 + x7 ≥ 11

x1 + x4 + x5 + x6 + x7 ≤ 25

x1 + x2 + x5 + x6 + x7 ≤ 25

x1 + x2 + x3 + x6 + x7 ≤ 25

x1 + x2 + x3 + x4 + x7 ≤ 25

x1 + x2 + x3 + x4 + x5 ≤ 25

x2 + x3 + x4 + x5 + x6 ≤ 25

x3 + x4 + x5 + x6 + x7 ≤ 25

x1 + x2 + x3 + x4 + x5 + x6 + x7 = 25

x1 , x2 , x3 , x4 , x5 , x6 , x7 ≥ 0 e inteiros


Modelizacao 23

Slide 46

Funcao objectivo

A funcao objectivo e agora minimizar o numero de trabalhadores que

pertencem a turnos que trabalhem ao Sabado (dia 6) ou ao Domingo (dia

7), tendo em atencao que alguns turnos sao particularmente penalizantes

por ocuparem simultaneamente o Sabado e o Domingo.

minx2 + 2x3 + 2x4 + 2x5 + 2x6 + x7

Parte V

O problema de escalonamento de recursos humanos aqui resolvido e do tipo

estatico porque assume que o posto de correios enfrenta a mesma situacao

semana apos semana. No entanto, afectar um funcionario permanentemente

a uma escala traduz-se numa situacao de injustica e desiquilıbrio

potenciadora de instabilidade laboral e de atritos entre funcionarios que em

nada contribuem para uma harmoniosa gestao de recursos humanos. A

solucao passa portanto por fazer os funcionarios rodar pelas varias escalas.

Suponha entao a seguinte solucao para o problema de escalonamento

semanal:

Slide 47

x1 x2 x3 x4 x5 x6 x7

8 6 0 7 0 4 0

Poderıamos agora criar um ciclo de 25 semanas com a seguinte escala:

Semana 1–8 Inıcio a Segunda

Semana 9–14 Inıcio a Terca

Semana 15–21 Inıcio a Quinta

Semana 22–25 Inıcio ao Sabado

Seguindo esta escala, o funcionario 1 comecaria na semana 1 da escala, o

funcionario 2 comecaria na semana 2 e assim sucessivamente. Por exemplo,

o funcionario 5 faria 4 semanas o turno que se inicia a Segunda, depois faria

6 semanas o turno que se inicia a Terca, 7 semanas o turno que se inicia a

Quinta, 4 semanas o turno que se inicia ao Sabado e, finalmente, 4 semanas

o turno que se inicia a Segunda, fechando o ciclo de 25 semanas e

recomecando de novo.

Desta forma todos os funcionarios passariam de uma forma equilibrada e

justa por todos os turnos.


Modelizacao 24

Slide 56

Bibliografia

• Hillier, Fraderick S. e Lieberman, Gerald (1995). Introduction to

Operations Research, Mc Graw-Hill.

• Oliveira, Jose Fernando (1996). Apontamentos de Investigacao

Operacional 1. FEUP.

• Winston, Wayne e Albright, Christian (2001). Practical Management

Science, Duxbury.


Documents

Modelizaçãomac/ensino/docs/TMDMarco2005/... · 2005-03-01 · Slide 1 Modelização ... ou ser criticado por naõ fazer, aquilo para que naõ foi criado. ... Passo II —