Exercícios de Formulação (Material Extra)

1

Exercıcios de Formulacao

1.1 Problema da Mistura de Produtos . . . . . . . . . . . . . . . . 4

1.2 Publicacoes Polemicas . . . . . . . . . . . . . . . . . . . . . . . 6

1.3 Montagem duas pecas . . . . . . . . . . . . . . . . . . . . . . . . 10

1.4 A companhia de aviacao Benvoa . . . . . . . . . . . . . . . . . 12

1.5 Carga de navio . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.6 Producao e Distribuicao . . . . . . . . . . . . . . . . . . . . . . 17

1.7 Refinaria Petroleo . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.8 Arrendamento de Espaco num Armazem (5M) . . . . . . . . 22

1.9 Planeamento da Producao numa Fabrica de Papel . . . . . . 25

1.10 Distribuicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

1.11 Seleccao de Eventos na UPorto . . . . . . . . . . . . . . . . . . 30

1.12 Aeroporto ALETROP . . . . . . . . . . . . . . . . . . . . . . . . 32

1.13 Urbanizacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

1.14 Estaleiro do ShopShopping . . . . . . . . . . . . . . . . . . . . . 37

1.15 Escalonamento de recursos humanos . . . . . . . . . . . . . . . 43

1.16 SuperBoa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

Objectivos de Aprendizagem de Formulacao• Dado um enunciado com a descricao de um problema

– Formular esse problema atraves de uma funcao objectivo e de um conjunto derestricoes lineares, quer com variaveis contınuas, inteiras ou binarias.

– Utilizar variaveis binarias como variaveis auxiliares para formular situacoes dife-rentes da simples conjuncoes de restricoes, como por exemplo:

∗ disjuncao de restricoes

∗ implicacao de restricoes

∗ valores mınimos para variaveis (e.g. ou vale zero ou e maior que...)

– Descrever o que significam e fazem um conjunto de restricoes, no contexto de umproblema concreto.

3

1.1 Problema da Mistura de Produtos Exercıcios de Formulacao

1.1 Problema da Mistura de Produtos

1.1.1 Enunciado

A companhia Electro & Domesticos pretende escalonar a producao de um novoapetrecho de cozinha que requer dois recursos: mao-de-obra e materia-prima. Acompanhia considera a hipotese de produzir 3 modelos diferentes, tendo o seudepartamento de engenharia fornecido os dados representados na tabela 1

Modelo A B CMao-de-obra (horas por unidade) 7 3 6Materia-prima (quilos por unidade) 4 4 5Lucro (epor unidade) 4 2 3

Tabela 1: Dados fornecidos pelo departamento de engenharia

O fornecimento de materia-prima esta limitado a 200 quilos/dia. Por diaestao disponıveis 150 horas de trabalho. O objectivo e maximizar o lucro total.Formule o modelo que permitiria resolver este problema.

4

1.1 Problema da Mistura de Produtos Exercıcios de Formulacao

1.1.2 Resolucao

Passo I O que se desconhece, e que se pretende determinar na fase de resolucaodo 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 C (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 (7horas), vezes o numero de unidades do modelo A a produzir (xA), mais a mao-de-obra necessaria para produzir uma unidade do modelo B (3 horas), vezes onumero 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 onumero de unidades do modelo C que se venha a produzir (xC), nao poderaoexceder 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 variaveisde 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 lucroobtido com os 3 modelos. Como cada unidade do modelo A da um 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 ≤ 1504xA + 4xB + 5xC ≤ 200

xA, xB , xC ≥ 0

5

1.2 Publicacoes Polemicas Exercıcios de Formulacao

1.2 Publicacoes Polemicas

1.2.1 Enunciado

“Publicacoes Polemicas” e uma editora de grande divulgacao internacional quevai publicar proximamente uma autobiografia de um polıtico controverso. Dadasas caracterısticas do polıtico em causa, a editora admite que a 1a edicao vai servendida por completo, se nao houver atrasos. Seguindo a sua habitual linhaeditorial foi decidido fazer o lancamento em simultaneo das versoes de Luxo,com capa dura e Normal, com capa mole, mas a empresa desconhece o numerode exemplares de cada versao que deve ser produzido para obter o maximo lucropossıvel.

A empresa tem um conjunto de restricoes de producao e armazenamento quese apresentam a seguir:

Departamento de Impressao O departamento de impressao pode produzirno maximo 10 000 exemplares (incluindo versoes Luxo e Normal).

Departamento de Encadernacao O departamento de encadernacao pode-ria concluir 12 000 exemplares da versao Normal se encadernasse apenas essetipo de livros. Se encadernasse apenas livros da versao Luxo conseguiria enca-dernar ate 8 000 exemplares.

Armazem A capacidade maxima do armazem seria de 15 000 exemplares seso despachasse exemplares da versao Normal ou entao 9 000 exemplares se sodespachasse exemplares da versao Luxo.

Para alem das restricoes de producao e de armazenamento existem outrasrestricoes que se apresentam a seguir.

Pedidos Ja existem pedidos de 2 000 exemplares Normal e 1 000 exemplaresLuxo, que deverao ser satisfeitos na 1a edicao.

Mınimo Luxo Pelo menos 14 do total dos exemplares devera ser em versao

Luxo.

Lucro O lucro resultante da venda de um exemplar Normal e de 600UMs ede um exemplar Luxo e de 720UMs.

(a) Formule este problema como um Modelo de Programacao Linear.

(b) Resolva-o graficamente, ilustrando o conjunto das solucoes admissıveis.

(c) Resolva pelo metodo Simplex uma versao simplificada do problema, emque nao se consideram os Pedidos e o Mınimo Luxo.

Qual o significado que atribui ao valor das variaveis de folga?

A solucao obtida sera a solucao optima do problema inicial?

(d) Substitua a condicao Mınimo Luxo pela seguinte:

Se houver producao de copias na versao Luxo entao o seu numero deveraser superior a 2 000.

6


Como incluiria esta condicao no modelo formulado, mantendo a sua es-trutura linear (inteira)?

Justifique.

7


1.2.2 Resolucao

(a) Definam-se as seguintes variaveis de decisao:

xL quantidade de livros a produzir na versao Luxo;

xN quantidade de livros a produzir na versao Normal.

Com essas variaveis de decisao o modelo de Programacao Linear sera oseguinte:

Objectivo:

max Z = 600xN + 720xL (1.1)

Sujeito a:

xN + xL ≤ 10000 (1.2)xN

12000+

xL8000

≤ 1 (1.3)xN

15000+

xL9000

≤ 1 (1.4)

14

(xN + xL) ≤ xL (1.5)

xN ≥ 2000 (1.6)xL ≥ 1000 (1.7)

A equacao (1.2) corresponde a restricao de impressao. As equacoes (1.3)e (1.4) sao devidas as restricoes da encadernacao e do armazem. A equa-cao (1.5) e devida a restricao de mınimo de producao de exemplares deLuxo. Por ultimo, as equacoes (1.6) e (1.7) representam a restricao desatisfacao dos pedidos ja existentes.

O modelo apresentado e equivalente ao seguinte modelo:

max Z = 600xN + 720xL (1.8)

Sujeito a:

xN + xL ≤ 10000 (1.9)2xN + 3xL ≤ 24000 (1.10)3xN + 5xL ≤ 45000 (1.11)xN − 3xL ≤ 0 (1.12)

xN ≥ 2000 (1.13)xL ≥ 1000 (1.14)

(b) Representacao grafica:

8


xN

xL

(14)

(13)

(12)

(11)(10)(9)

(8)

Z crescente

Solução óptima

xN = 6000

xL = 4000

(c) Resolucao pelo Algoritmo Simplex

xN xL s1 s2 s3

s1 1 1 1 0 0 10s2 2 3 0 1 0 24 ⇒s3 3 5 0 0 1 45− Z

10 60 72 0 0 0 0�

xN xL s1 s2 s3

s113 0 1 − 1

3 0 2 ⇒

xL23 1 0 1

3 0 8s3 − 1

3 0 0 − 53 1 5

− Z10 12 0 0 −24 0 −576

�

xN xL s1 s2 s3

xN 1 0 3 −1 0 6xL 0 1 −2 1 0 4s3 0 0 1 −2 1 7− Z

10 0 0 −36 −12 0 −648

9

1.3 Montagem duas pecas Exercıcios de Formulacao

1.3 Montagem duas pecas

1.3.1 Enunciado

Um produto em fabrico resulta duma montagem constituıda por duas pecas,A e B. Para a producao dessas pecas recorre-se a uma maquina M1 e a cincomaquinas M2. A produtividade de cada maquina relativamente as duas pecase a indicada na tabela 2:

Peca M1 M2A 3 20B 5 15

Tabela 2: Tempo de producao das pecas (em minutos por peca) A e B nasmaquinas M1 e M2

A carga das maquinas M2 e repartida igualmente pelas 5 maquinas. Oobjectivo do problema e saber como se pode obter o maximo de montagenscompletas por dia. Considere que um dia corresponde a 8 horas de trabalho.

(a) Apresente um modelo matematico para este problema.

(b) Considere agora a situacao em que tambem se pretende manter uma uti-lizacao equilibrada entre as maquinas de modo que nenhuma delas sejautilizada mais 30 minutos por dia do que qualquer outra das maquinas.

Sera possıvel resolver este novo problema por Programacao Linear? Jus-tifique.

10

1.3 Montagem duas pecas Exercıcios de Formulacao

1.3.2 Resolucao

(a) • Variaveis de decisaoxA1 quantidade de pecas do tipo A a produzir na maquina M1;xA2 quantidade de pecas do tipo A a produzir na maquina M2;xB1 quantidade de pecas do tipo B a produzir na maquina M1;xB2 quantidade de pecas do tipo B a produzir na maquina M2.• Funcao objectivo

Pretende-se maximizar o numero de montagens completas:

max Z = min(xA1 + xA2, xB1 + xB2)

Esta funcao objectivo pode ser linearizada, acrescentando mais umavariavel auxiliar e duas restricoes:

max Z = Y

xA1 + xA2 ≥ YxB1 + xB2 ≥ Y

• Modelo

max Z = Y (1.15)

Sujeito a:

3xA1 + 5xB1 ≤ 8× 60 (minutos) (1.16)20xA2 + 15xB2 ≤ 8× 60× 5 (minutos) (1.17)xA1 + xA2 − Y ≥ 0 (1.18)xB1 + xB2 − Y ≥ 0 (1.19)

xA1, xA2, xB1, xB2 ≥ 0 (1.20)

Onde 1.16 e 1.17 correspondem as restricoes de capacidade das ma-quinas 1 e 2 respectivamente (ha 5 maquinas tipo 2). As restricoes1.18 e 1.19 sao as restricoes auxiliares para linearizacao da funcao ob-jectivo. Por ultimo, as restricoes 1.20 exigem que todas as variaveissejam maiores ou iguais a zero.

(b) A restricao (nao linear) que modeliza a situacao pretendida nesta alınea ea seguinte: ∣∣∣∣(3xA1 + 5xB1)− 20xA2 + 15xB2

5

∣∣∣∣ ≤ 30

Simplificando obtem-se:

|3xA1 + 5xB1 − 4xA2 − 3xB2| ≤ 30 (1.21)

Para obter um modelo de Programacao Linear, sera necessario transformara restricao 1.21 em duas restricoes lineares:

3xA1 + 5xB1 − 4xA2 − 3xB2 ≤ 30 (1.22)−3xA1 − 5xB1 + 4xA2 + 3xB2 ≤ 30 (1.23)

11

1.4 A companhia de aviacao Benvoa Exercıcios de Formulacao

1.4 A companhia de aviacao Benvoa

1.4.1 Enunciado

A companhia de aviacao Benvoa vai comprar avioes a jacto de passageiros, paraviagens longas, medias e curtas, denominados de Al, Am e Ac, respectivamente.

Os custos unitarios, em milhoes de euros sao, respectivamente, de 5 000, 3800 e 2 000. A administracao da companhia aprovou um orcamento maximo de112 000 milhoes de euros para esse efeito.

Admite-se que os lucros anuais com cada um dos tipos de aviao Al, Am eAc, sejam de 310, 230 e 200 milhoes de euros respectivamente.

Ha pilotos suficientes para pilotar, no maximo, 30 avioes novos.Se apenas fossem comprados avioes Ac, os servicos de manutencao seriam

capazes de garantir a manutencao de 40 avioes novos. Contudo, do ponto devista do esforco de manutencao, cada aviao Am equivale a 4/3 de um aviao Ace cada aviao Al a 5/3 de um aviao Ac.

A direccao tecnica e ainda de opiniao que, por cada aviao Ac que seja com-prado, se comprem tambem pelo menos um aviao Al ou um aviao Am.

Por outro lado, seleccionado um aviao Al para comprar, tambem deverao sercomprados pelo menos 8 avioes Ac ou Am.

Com estes dados, a gestao da empresa deve decidir a quantidade de avioesde cada tipo a comprar, de modo a maximizar o lucro.

Formule este problema com um modelo de programacao linear.

12

1.4 A companhia de aviacao Benvoa Exercıcios de Formulacao

1.4.2 Resolucao

Variaveis de decisao

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

Restricoes

Dinheiro disponıvel: 500xl + 3800xm + 2600xc ≤ 112000Pilotos disponıveis: xl + xm + xc ≤ 30Manutencao: 5

3xl +43xm + xc ≤ 40

Opiniao da direccao tecnica: xl + xm ≥ xcxc + xm ≥ 8xl

xc, xm, xl ≥ 0e inteiros

Funcao objectivo

max LUCRO = 310xl + 230xm + 200xc

13

1.5 Carga de navio Exercıcios de Formulacao

1.5 Carga de navio

1.5.1 Enunciado

'" .,,1

p

ElO ElO

Uma companhia de navegacao possui um navio com 3 poroes de carga (aproa, a re e ao centro) possuindo os limites de capacidade apresentados natabela 3:

Porao Tonelagem Volume(toneladas) (m3)

Proa 2000 100000Centro 3200 14000

Re 1800 80000

Tabela 3: Limites de capacidade (em tonelagem e em volume) de cada um dosporoes

A empresa sao oferecidas as cargas da tabela 4, cada uma das quais podeser aceite parcial ou totalmente:

Carga Peso Volume por tonelada Lucro

(toneladas) ( m3

tonelada) ( escudos

tonelada)

A 7000 60 20B 6500 50 24C 4000 25 16

Tabela 4: Peso, volume e lucro associados a cada carga

A fim de preservar o equilıbrio do navio, a proporcao entre o peso em cadaporao e o volume respectivo deve ser a mesma que entre os correspondenteslimites de capacidade. Admita que em cada porao podem ser transportadaspartes de cargas diferentes. Pretende-se maximizar o lucro da empresa, relativoa utilizacao deste navio.

Construa um modelo de Programacao Linear para o problema apresentado.

14


1.5.2 Resolucao

• Indices

i tipo de carga (A, B e C) i ∈ [1, 2, 3];

j tipo de porao (P, C, R) j ∈ [1, 2, 3].

• Variaveis de decisao

xij quantidade de carga i a transportar no porao j (em toneladas).

• Funcao objectivo

Pretende-se maximizar o lucro com o transporte das cargas i em todos osporoes j, o que corresponde a soma do lucro obtido com o transporte dacarga A, com o lucro com transporte da carga B e da carga C.

maxZ = 20∑j

x1j + 24∑j

x2j + 16∑j

x3j (1.24)

• Restricoes ∑j

x1j ≤ 7000 (1.25)

∑j

x2j ≤ 6500 (1.26)

∑j

x3j ≤ 4000 (1.27)

∑i

xi1 ≤ 2000 (1.28)∑i

xi2 ≤ 3200 (1.29)∑i

xi3 ≤ 1800 (1.30)

60x11 + 50x21 + 25x31 ≤ 100000 (1.31)60x12 + 50x22 + 25x32 ≤ 14000 (1.32)60x13 + 50x23 + 25x33 ≤ 80000 (1.33)

60x11+50x21+25x31∑i xi1

=1000002000

(1.34)

60x12+50x22+25x32∑i xi2

=140003200

(1.35)

60x13+50x23+25x33∑i xi3

=800001800

(1.36)

∀i,j xij ≥ 0 (1.37)

As restricoes 1.25, 1.26 e 1.27 garantem que nao se transporta mais cargado que a que existe de cada um dos tipos. As restricoes 1.28, 1.29 e 1.30garantem que nao se ultrapassa a tonelagem maxima permitida em cadaum dos poroes. As restricoes 1.31, 1.32 e 1.33 garantem que nao se ultra-passa a capacidade (volume) maxima permitida em cada um dos poroes.

15


As restricoes 1.34, 1.35 e 1.36 garantem que se mantem a proporcao entreo peso em cada porao e a respectiva capacidade. Por fim, as restricoes1.37 garantem que todas as variaveis de decisao sao maiores ou iguais azero.

• Modelo

O modelo apresentado (equacoes 1.24 a 1.37) pode ser reescrito da seguinteforma:

maxZ = 20∑j

x1j + 24∑j

x2j + 16∑j

x3j

∑j

x1j ≤ 7000

∑j

x2j ≤ 6500

∑j

x3j ≤ 4000

∑i

xi1 ≤ 2000∑i

xi2 ≤ 3200∑i

xi3 ≤ 1800

60x11 + 50x21 + 25x31 ≤ 10000060x12 + 50x22 + 25x32 ≤ 1400060x13 + 50x23 + 25x33 ≤ 80000

10x11 − 25x31 = 0178x12 + 146x22 + 66x32 = 028x13 + 10x23 − 35x33 = 0

∀i,j xij ≥ 0

16

1.6 Producao e Distribuicao Exercıcios de Formulacao

1.6 Producao e Distribuicao

1.6.1 Enunciado

Duas fabricas, A e B, situadas em locais diferentes produzem ambas os produtosP1 e P2. A fabrica A tem 3 maquinas e a fabrica B tem 2 maquinas. Todas asmaquinas fazem os produtos P1 e P2. Depois de fabricados, os produtos podemser transportados entre as fabricas de modo a satisfazer a procura. O numero deunidades produzidas por dia, os custos de producao e de transporte, a procurados produtos e o numero de dias em que cada maquina esta disponıvel por mesestao indicados nas tabelas 5 e 6.

(a) Apresente um modelo geral (usando variaveis indexadas e coeficientes con-venientes a definir) que permita determinar os esquemas de utilizacao dasmaquinas em cada fabrica e de distribuicao dos produtos entre as fabricas,a que corresponda um custo total mınimo.

(b) Concretize o modelo para o caso descrito.

(c) Refira-se a resolucao do problema em questao.

Fabrica A BMaquina M1 M2 M3 M1 M2

Disponibilidade (dias) 30 28 24 26 28Produto P1 P2 P1 P2 P1 P2 P1 P2 P1 P2

Producao por dia 40 35 42 38 40 37 41 37 42 40Custo por dia 100 102 104 106 98 104 102 105 103 106

Tabela 5: Capacidades de producao das fabricas

Produto P1 P2

Fabrica A B A BProcura 1200 800 1500 1100

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

Tabela 6: Procura e custos de transporte dos produtos

17


1.6.2 Resolucao

(a) • 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].


xijk numero de dias de producao durante um mes do produto k, nafabrica 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

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.

• ModeloObjectivo

minCusto =∑i,j,k

cijkxijk +∑i,k

sikyik +∑i,k

tikzik (1.38)

∀i,k∑j pijkxijk − yik + zik = dik (1.39)

∀i,j∑k xijk ≤ mij (1.40)

∀k z1k ≤∑j

p2jkx2jk (1.41)

∀k z2k ≤∑j

p1jkx1jk (1.42)

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

As restricoes 1.39 garantem que a procura do produto k na fabrica ie satisfeita. As restricoes 1.40 sao restricoes de capacidade (disponi-bilidade) das maquinas. As restricoes 1.41 e 1.42 garantem que so setransporta a partir de uma fabrica o que e produzido nessa fabrica.Finalmente as restricoes 1.43 garantem que todas as variaveis tomamvalores maiores ou iguais a zero.

(b) Concretize agora o modelo generico apresentado, de tal forma que corres-ponda a situacao descrita no enunciado.

(c) Ao resolver a alınea anterior, teve com certeza que tratar o caso das va-riaveis x231 e x232, dado que essas variaveis foram definidas no modelogenerico, mas na realidade nao existe nenhuma maquina 3 na fabrica 2.Ha varias formas de resolver esta questao:

18


• quando se ”concretiza”o modelo, pode-se nao definir as variaveis emcausa (ver resolucao do exercıcio 2);

• pode-se associar um valor nulo a producao nessa maquina nao exis-tente (p23k = 0) (sera que e suficiente?);

• pode-se associar um custo infinito (muito grande) a producao nessamaquina nao existente (c23k =∞), dado que se trata de um problemade minimizacao e nessa situacao as variaveis serao nulas na solucaofinal;

• podem-se acrescentar restricoes do tipo x23k = 0.

19

1.7 Refinaria Petroleo Exercıcios de Formulacao

1.7 Refinaria Petroleo

1.7.1 Enunciado

Uma refinaria de petroleo pode misturar 3 tipos de crude para produzir gasolinanormal e super.

A refinaria de petroleo tem duas unidades de mistura, uma unidade maisantiga e uma outra mais recente.

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 gasolinanormal e 7 de gasolina super. A unidade de mistura mais recente usa, para cadaciclo de producao, 3 barris de crude A, 9 de B e 4 de C para produzir 5 tanquesde gasolina normal e 9 de super.

Devido a contratos ja assinados, a refinaria tem que produzir, pelo menos,500 tanques de gasolina normal e 300 tanques de gasolina super.

Para essa producao existem em armazem 1500 barris de crude A, 1900 decrude B e 1000 de crude C.

Por cada tanque de gasolina normal produzida, a refinaria ganha 6 unidadesmonetarias e, por tanque de super, 9 unidades monetarias.

Pretende-se saber como utilizar as reservas de crude e as duas unidades demistura, de forma a maximizar o lucro da refinaria respeitando os compromissosassumidos.

20

1.7 Refinaria Petroleo Exercıcios de Formulacao

1.7.2 Resolucao


x1 − no de ciclos de producao a realizar na unidade antigax2 − no de ciclos de producao a realizar na unidade nova

Restricoes Crude disponıvel:

Tipo A: 5x1︸︷︷︸gasto na

unidade

antiga

+ 3x2︸︷︷︸gasto na

unidade

nova

≤ 1500

Tipo B: 7x1 + 9x2 ≤ 1900Tipo C: 2x1 + 4x2 ≤ 1000

Contratos assinados:

Gasolina normal: 9x1︸︷︷︸produzido

na unidade

antiga

+ 5x2︸︷︷︸produzido

na unidade

nova

≥ 500

Gasolina super: 7x1 + 9x2 ≥ 300

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)

21

1.8 Arrendamento de Espaco num Armazem (5M) Exercıcios de Formulacao

1.8 Arrendamento de Espaco num Armazem (5M)

1.8.1 Enunciado

Uma empresa planeia arrendar espaco num armazem. As necessidades de espacopara os proximos 3 meses estao representadas na tabela 7. Os custos de arrenda-mento por metro quadrado dependentes do numero de meses de arrendamentoestao representados na tabela 8.

Mes Necessidade deespaco (m2)

1 15002 10003 20004 5005 2500

Tabela 7: Necessidades de espaco os proximos 3 meses

Perıodo de arrendamento Custo por m2

(meses) ($)1 28002 45003 60004 73005 8400

Tabela 8: Custos de arrendamento

Construa um modelo que permita determinar o esquema de contratos a as-sinar, por forma a satisfazer as necessidades de espaco o mais economicamentepossıvel.

22


1.8.2 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)∑5j=1 x1j ≥ 1500

(mes 2)∑5j=2 x1j +

∑4j=1 x2j ≥ 1000

(mes 3)∑5j=3 x1j +

∑4j=2 x2j +

∑3j=1 x3j ≥ 2000

(mes 4)∑5j=4 x1j +

∑4j=3 x2j +

∑3j=2 x3j +

∑2j=1 x4j ≥ 500

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

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

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 + 45004∑i=1

xi2 + 60003∑i=1

xi3

+ 73002∑i=1

xi4 + 8400x15

Arrendamento de espaco num armazemResolucao mais compacta

Dados

Cj − custo de arrendar 1m2 por um perıodo de j mesesNi − necessidade de espaco no mes i




∀i∑6−ij=1 xij +

∑i−1k=1

∑6−kj=i+1−k xkj ≥ Ni

23


Funcao objectivo

5∑j=1

Cj ×6−j∑i=1

xij

Arrendamento de espaco num armazemResolucao mais compacta

Dados

Cj − custo de arrendar 1m2 por um perıodo de j mesesNi − necessidade de espaco no mes i




∀i∑6−ij=1 xij +

∑i−1k=1

∑6−kj=i+1−k xkj ≥ Ni

Funcao objectivo

5∑j=1

Cj ×6−j∑i=1

xij

24

1.9 Planeamento da Producao numa Fabrica de PapelExercıcios de Formulacao

1.9 Planeamento da Producao numa Fabrica dePapel

1.9.1 Enunciado

A maior fabrica de papel do mundo (vıdeo)Como se pode ver na figura, o papel e fabricado em rolos grandes (em lar-

gura e em diametro), que depois sao divididos em rolos mais pequenos. Essesrolos pequenos poderao ser vendidos directamente a clientes ou entao podem serusados para cortar em formatos.

Carretel n Bobinas

n Laminas

Consideremos uma empresa em que o papel e produzido em rolos com 6metros de largura.

A partir destes rolos de 6 metros e necessario produzir:

• 30 rolos com 280cm de largura,

• 60 rolos com 200cm de largura,

• 48 rolos com 150cm de largura.

Um rolo de 6 metros poderia, por exemplo, ser dividido em 2 rolos de 280cm,sobrando um “rolinho” de 40cm que e considerado desperdıcio.

Assumindo que existem rolos grandes em quantidade suficiente para satis-fazer esta encomenda, o problema consiste em determinar a forma de cortar osrolos grandes de forma a minimizar o desperdıcio.

Construa o modelo de Programacao Matematica para este problema.

25

http://www.youtube.com/watch?v=BXutjvFrjCI

1.9 Planeamento da Producao numa Fabrica de PapelExercıcios de Formulacao

1.9.2 Resolucao

O primeiro passo para a formulacao deste problema passa por determinar dequantas formas pode um rolo grande ser cortado. Para alem da forma sugeridano enunciado (2 rolos de 200cm, sobrando 40cm de desperdıcio) podem aindaser determinados 6 outros “padroes de corte” (ver tabela).

As variaveis de decisao (x1 a x7) correspondem ao numero de vezes quecada padrao de corte e aplicado no corte de um rolo grande. A tabela seguinteapresenta ainda as quantidades pedidas de cada rolo pequeno, assim como odesperdıcio gerado por cada padrao de corte.

Largura No de rolosdos rolos x1 x2 x3 x4 x5 x6 x7 pedidos

280 2 1 1 0 0 0 0 30200 0 1 0 3 2 1 0 60150 0 0 2 0 1 2 4 48

Desperdıcio 40 120 20 0 50 100 0

Exemplificando, x3 = 4 significa que se cortam 4 rolos grandes em 1 de280cm e 2 de 150cm, gerando um desperdıcio de 20cm. No total obtem-se 4rolos de 280cm e 8 de 150cm (e nenhum de 200cm).

As restricoes vao estar directamente relacionadas com as quantidades derolos pequenos que e necessario cortar, uma por cada rolo. Se a cada linhado sistema de inequacoes corresponde um tipo de rolo pequeno, a cada colunacorrespondera um padrao de corte:

2x1 + x2 + x3 ≥ 30x2 + 3x4 + 2x5 + x6 ≥ 60

2x3 + x5 + 2x6 + 4x7 ≥ 48xi ≥ 0 ∀1≤i≤7

O objectivo do problema e minimizar o desperdıcio. Assim, a funcao objec-tivo 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 naoforem admitidas sobreproducoes?

Nesse caso como e que o modelo deve ser alterado?

26

1.10 Distribuicao Exercıcios de Formulacao

1.10 Distribuicao

1.10.1 Enunciado

Uma empresa tem duas fabricas e quatro armazens e vende produtos a seisclientes que podem ser abastecidos a partir dos armazens ou directamente apartir das fabricas. A empresa suporta os custos de distribuicao apresentadosnas tabelas 9 e 10. Os tracos indicam que a entrega correspondente nao serealiza.

Origens

Destinos Braganca EvoraArmazens (fabrica) (fabrica)Coimbra 0.5 —

Faro 1.0 0.2Lisboa 0.8 0.6Porto 0.4 0.8

Tabela 9: Custos de distribuicao (em 1000$ por ton.)

Origens

Destinos Braganca Evora Coimbra Faro Lisboa PortoClientes (fabrica) (fabrica) (armazem) (armazem) (armazem) (armazem)

C1 1.0 2.0 — 1.0 — —C2 — — 1.5 0.5 1.5 —C3 1.5 — 0.5 0.5 2.0 0.2C4 2.0 — 1.5 1.0 — 1.5C5 — — — 0.5 0.5 0.5C6 1.0 — 1.0 — 1.5 1.5

Tabela 10: Custos de distribuicao (em 1000$ por ton.)

Nas tabelas 11 e 12 estao representadas as capacidades mensais maximasdas fabricas e dos armazens. Na tabela 13, apresenta-se a procura tıpica mensaldos clientes.

Fabrica Capacidade(toneladas)

Braganca 150 000

Evora 200 000

Tabela 11: Capacidade maxima mensal de producao das fabricas

O objectivo da empresa e a determinacao de uma estrategia optima de dis-tribuicao que satisfaca a procura respeitando as capacidades e limitacoes exis-tentes:

Construa um modelo de Programacao Linear para este problema.

27


Armazem Capacidade(toneladas)

Coimbra 70 000Faro 50 000Lisboa 100 000Porto 40 000

Tabela 12: Capacidade maxima mensal de fornecimento dos armazens

Cliente Procura mensal(toneladas)

C1 50 000C2 10 000C3 40 000C4 35 000C5 60 000C6 20 000

Tabela 13: Procura tıpica mensal dos clientes

1.10.2 Resolucao

• Indices

i fabricas i ∈ [1, 2];

j armazens j ∈ [1, . . . , 4];

k clientes k ∈ [1, . . . , 6].


xij quantidade a enviar da fabrica i para o armazem j;

yik quantidade a enviar da fabrica i para o cliente k;

zjk quantidade a enviar do armazem j para o cliente k.

Como algumas das entregas nao podem ser efectuadas (tracos nas tabe-las), as variaveis de decisao correspondentes nao serao definidas. Umaoutra solucao para o problema consistiria em definir as variaveis todas erestringir o valor dessas variaveis a zero.

As variaveis em causa sao entao:

x21, y12, y15, y22, y23, y24, y25, y26, z11, z15, z26, z31, z34, z41, z42

• Funcao objectivo

28


O objectivo pretendido e a minimizacao do custo Z, isto e:

min Z = 0.5x11 + 1.0x12 + 0.8x13 + 0.4x14

+0.2x22 + 0.6x23 + 0.8x24

+1.0y11 + 1.5y13 + 2.0y14 + 1.0y16

+2.0y21

+1.5z12 + 0.5z13 + 1.5z14 + 1.0z16

+1.0z21 + 0.5z22 + 0.5z23 + 1.0z24 + 0.5z25

+1.5z32 + 2.0z33 + 0.5z35 + 1.5z36

+0.2z43 + 1.5z44 + 0.5z45 + 1.5z46

• Restricoes

Cada fabrica tem uma capacidade maxima, o que quer dizer que a somade todos os xij com todos os yik para uma dada fabrica i nao pode excedera capacidade da fabrica i.

Dado que existem duas fabricas, esse limite de capacidade resulta em duasrestricoes.

Por exemplo para a fabrica de Braganca (i = 1):

x11 + x12 + x13 + x14 + y11 + y13 + y14 + y16 ≤ 150000 (1.44)

Tambem ha limites para a capacidade de fornecimento de um armazem ecomo ha quatro armazens, ha quatro restricoes do mesmo tipo.

Para o armazem de Coimbra (j = 1):

x11 ≤ 70000 (1.45)

Os pedidos dos clientes tambem devem ser satisfeitos e como ha 6 clientes,ha 6 restricoes do mesmo tipo.

Para o cliente C1 (k = 1):

y11 + y21 + z21 = 50000 (1.46)

E tambem necessario considerar as restricoes de continuidade para os ar-mazens, que obrigam a que nao saia mais mercadoria de um armazem doque a que entra. Como ha 4 armazens, ha quatro restricoes do mesmotipo.

Para o armazem de Coimbra (j = 1):

z12 + z13 + z14 + z16 ≤ x11 (1.47)

Por fim, e necessario garantir que todas as variaveis tem valores maiores ouiguais a zero:

x11, x12, x13, x14, x22, x23, x24, y11, y13, y14, y16, y21, z12, z13,

z14, z16, z21, z22, z23, z24, z25, z32, z33, z35, z36, z43, z44, z45, z46 ≥ 0 (1.48)

Complete agora o modelo!

29

1.11 Seleccao de Eventos na UPorto Exercıcios de Formulacao

1.11 Seleccao de Eventos na UPorto

1.11.1 Enunciado parte 1

Protocolo Universidade do Porto

Novo acordo de ~ com a Urivenlidade do POI to o ~nC<l SantaOOer l<>ltll • a UrWersiI!ode do Porto ...... rom urn .ooroo <Ie COOpoNa;ao, .,. otlf9o do _I 0 B.>neo ~_., ._ <Ie

ensno, ' weoti90;ao • ~~ culor.J do U~ do Porto com om v_ 0"".1 S"pooriof 0 om ml'>io <Ie toros, doront. 0' ~o""'" 5 aoos.

A UrW«s_ Porto, &d;.>!Iicou pot" CMCUrso 0 . rriooio 00 corti<> <Ie _tJflCO;ao """. ntMio ~" todo 0 "'" ool<c!r;o _ 29.000 ol>r>os, 3500 prof."",., • "",_os do

p<'Soool _istr&tm> • <los """""" lI<fois _ om . ,,,,. ,,,,", 0 pot" ""CO 0"'" 3<1 !!onco &Onto""'" lotto.

o Cortin U"".rsurio ntrill<nt. dispoolblzara 10M SOlJ.S thisr .. om C<W\jJnto .Ior~ <Ie

....m:;o. , 310m 00, ""ncirio' , corm . _tin <Ie errve.trro. no. _''''' , 0 eontr<>kl

<Ie 0= . <Iet~, ro_ • ~1JO""'"t .. <Ie _"'" """tont ...

o ~"'00010 .,.N<Io nWi t>rnt><m . at>ert"r. <Ie _. a~"". un",ersnn .. no. ;" I>Io~ <14 ;' '''">:;in aCO<lO~, 0 aindo 0 .~ 0 ootros prtI!<ctos <14 ~_, com:> "m ~09'amo <Ie boisa. <Ie __

o Rei", <14 U~O:I_ <10 P<>rto, Prof"...,.. OootOf Jose Mar_, <los Santos, nicio" • SL>O ~terv~ no """""'~ 011'"""""""" 0 ~tere .... do !!onoo ~ re~cioMm<nto oom. ~ott">:;in o~ _ dI'9<. Oeotocoo .... t. sen!oo _ a ooabo<o;ao _ <Xist. iii 49um tefr4Ml • • ofn_

q"" so foi oonoItuI><Io ""tre5O "'I"ip" <1M _ NtM:;ii .. foram fsc!o< .. IT4><>rt>nt.,. ~. a "rWers_ "" """"""to <Ie es.coJ\<f 0 &ontor.der

lolt4 """" ""_ ._. <10 corti<> "rWersurio.

o Pres_'e do C<J.T·u i O fxecW;o 00 !!onoo Santo"""r lot:.. Or. N""" _ t""'*"'" • S,," ~t<fV<1\"" Oil'"""""""" • ~ <14 re' orio 0

CMf,.n~ _ <Ie~,tor.m "" """co •• 1011'>_ 0 f.c!o <14 UrWersiI!ode do Porto ter q<>eIIfo<lo . tr&01i<;io, ""..". piooe" . m i>icior prolooolo' <Ie colo"",.,.., rom ~.tt">:;3es priv-' ~r. octi'liM<!es corm ",to: "po<Iem oontor "",,,,[,.00, _ oM tomt><m _torm, <Ie "" pione ..... q<>eIIfor

com 0' """t""""

http://www.santandertotta.pt/pagina/content/0,1564,1042_29502_1_1_1041_6_0,00.html

No ambito do acordo de cooperacao com o Santander Totta foi decidido in-vestir 200 000 Euros em eventos culturais e desportivos a organizar nos proximos5 anos, com o objectivo de reforcar os lacos no seio da Universidade e a marcaUPorto na Cidade do Porto e no Paıs. A equipa da UPorto que preparou osdados para decisao pelo Reitor foi pedido que, para cada evento proposto, indi-cassem o orcamento previsto e o numero estimado de pessoas que participariam.

Na data prevista foram apresentados ao Reitor os resultados do trabalho daequipa:

Evento Orcamento previsto Participantes“N’UPorto tudo e teatro” 80 000 Euros 100 000“A Ciencia n’UPorto” 40 000 Euros 10 000“Correr pel’UPorto” 30 000 Euros 10 000“Com UPorto amanhecemos com livros” 15 000 Euros 5 000“UPorto por dentro” 10 000 Euros 20 000“Festival de Tunas d’UPorto” 30 000 Euros 10 000“Depois das seis, UPorto e Jazz” 40 000 Euros 30 000“UPorto sao so Coros” 20 000 Euros 25 000“UPorto nos caminhos do Porto” 25 000 Euros 50 000“UPorto sim UPorto nao” 20 000 Euros 30 000

Construa o modelo de programacao Linear que permitiria encontrar a melhorconjunto de eventos a organizar, considerando que o Reitor da UPorto pretendiamaximizar o numero total de participantes.

30



1.11 Seleccao de Eventos na UPorto Exercıcios de Formulacao


Depois de analisar a solucao encontrada para o investimento a 5 anos, o Reitorpediu a mesma equipa que classificasse os diversos eventos nas categorias: ArtesPerformativas, Musica, Filosofia, Arquitectura, Literatura, Desporto e Ciencia,pois pretendia acrescentar ao modelo construıdo um conjunto de restricoes quelhe permitissem garantir que seria organizado pelo menos um evento de cadatipo.

De entre os eventos classificados como de Desporto e de Ciencia seria neces-sario apenas garantir que era organizado um.

Evento Artes perf. Musica Filosofia Arq. Lit. Desporto CienciaN’UPorto tudo e teatro XA Ciencia n’UPorto XCorrer pel’UPorto XCom UPorto amanhecemos com livros XUPorto por dentro XFestival de Tunas d’UPorto X XDepois das seis, UPorto e Jazz X XUPorto sao so Coros X XUPorto nos caminhos do Porto XUPorto sim UPorto nao X

31

1.12 Aeroporto ALETROP Exercıcios de Formulacao

1.12 Aeroporto ALETROP

1.12.1 Enunciado

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, quepretende manter a sua competitividade num sector de actividade fortementeconcorrencial. O aumento de competitividade passa, nomeadamente, pela rea-lizacao de dois objectivos, a melhoria da qualidade de servico e a reducao doscustos de operacao. Por outro lado, a seguranca de uma companhia aerea e umaspecto de primordial importancia, estando intimamente ligado a manutencao.Para manter um aviao em boas condicoes tecnicas, procede-se a manutencaopreventiva aos aparelhos da PAT, atraves de pequenas inspeccoes entre aterra-gem e posterior descolagem. A direccao da empresa esta tambem a considerara hipotese de oferecer estes servicos de manutencao a outras companhias deaviacao, mesmo que para tal tenha que aumentar as equipas de manutencao.O elemento crucial nestas equipas e o chefe de manutencao, tecnico altamentequalificado, que necessita de fazer formacao especıfica para cada tipo de aviaoe obter assim uma licenca imprescindıvel para o desempenho dessas funcoes. Acada licenca corresponde uma categoria de avioes, existindo 4 licencas diferentes:

Tipos de licencas Avioes1 Boeing 717 (100 lugares)2 Boeing 777 (300 a 500 lugares)3 Airbus A319 (124 lugares)4 Airbus A340 (350 lugares)

Cada tecnico pode ter no maximo 2 licencas. A primeira licenca demoravarios anos a obter, sendo portanto mais cara para a empresa, enquanto asegunda licenca demora menos anos a obter, ficando naturalmente mais barata.O custo da segunda licenca depende ainda da licenca anterior que o tecnicopossui. Actualmente existem 9 equipas de manutencao, cada uma chefiada porum tecnico licenciado, que funcionam em 3 turnos.

Custo (M$)Licenca Licenca a tiraranterior

1 2 3 40 2 4 2 41 - 1 2 32 1 - 2 33 1 3 - 24 1 2 1 -

Turno Chefe de equipa Tipo de licenca1 1, 2

1 2 13 24 3, 4

2 5 26 37 4

3 8 3, 49 3

Para poder oferecer servicos a outras companhias de aviacao, a empresapretende que existam 4 licencas de cada tipo, no conjunto dos chefes de ma-nutencao. Isto pode ser conseguido enviando para formacao actuais chefes deequipa (portanto tecnicos que ja possuem 1 licenca) ou outros tecnicos que aindanao possuem nenhuma licenca. No entanto, de cada turno so podera sair, nomaximo, 1 chefe de equipa para formacao. Escreva um modelo de programa-cao matematica que permita determinar a polıtica de obtencao de licencas queminimiza os custos para a Aletrop.

32

1.12 Aeroporto ALETROP Exercıcios de Formulacao

1.12.2 Resolucao


xij ={

1 se tecnico i tira licenca j0 se nao

A empresa pretende que existam 4 licencas de cada tipo, num total de 16licencas. Como, no conjunto dos chefes de manutencao existentes, ja existem12 licencas, sao necessarias mais 4 licencas, que no limite poderao ser todasobtidas por tecnicos novos. Nesse caso o numero maximo de tecnicos, ındice ina formulacao, sera igual a 13, 9 ja existentes e 4 novos.

Restricoes A empresa pretende que existam 4 licencas de cada tipo, no con-junto dos chefes de manutencao:∑13

i=1 xi1 = 2∑13i=1 xi2 = 1∑13i=1 xi3 = 0∑13i=1 xi4 = 1

Um tecnico pode ter no maximo 2 licencas e os tecnicos novos so poderaoobter nesta fase uma licenca1:∑4

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

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

∑3i=1 xij ≤ 1∑4

j=1

∑6i=4 xij ≤ 1∑4

j=1

∑9i=7 xij ≤ 1

Cada tecnico so pode obter 1 vez a mesma licenca:

x21 = x32 = x52 = 0x63 = x74 = x93 = 0

Funcao objectivo

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

min4∑j=1

13∑i=10

c0jxij +∑

i∈{6,9}

c3jxij +∑

i∈{3,5}

c2jxij + c1jx2j + c4jx7j

1Esta 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.

33

1.13 Urbanizacao Exercıcios de Formulacao

1.13 Urbanizacao

1.13.1 Enunciado

A empresa Latifundios e Companhia pretende urbanizar uma das suas grandespropriedades. A propriedade divide-se em 3 zonas, Z1, Z2 e Z3, com caracterıs-ticas bastante diferentes em termos de relevo, localizacao e tipo de subsolo, talcomo se pode verificar nas fotografias apresentadas a seguir.

A urbanizacao devera incluir areas para fins residenciais, R, areas verdes, Ve areas para equipamentos sociais, E. Pretende-se conhecer as areas a atribuira R, V , e E nas zonas Z1, Z2 e Z3.

Custos O custo da construcao de cada tipo de area (R, V ou E) em cada umadas zonas Z1, Z2 ou Z3, e proporcional a respectiva area de construcao, sendoas constantes de proporcionalidade diferentes entre si e conhecidas.

Areas mınimas de construcao E necessario construir pelo menos K hecta-res de Ar.

Proporcionalidade entre tipos de areas E necessario garantir que o quo-ciente areaE

areaRseja ≥ l e que o quociente areaV

areaRseja ≥ m.

(a) Formule o problema nas seguintes condicoes (sera um modelo de Progra-macao Linear?):

(i) As condicoes relativas a l e m devem ser satisfeitas em cada zona.

(ii) As condicoes relativas a l e m devem ser satisfeitas para o conjunto deZ1, Z2 e Z3.

(b) Qual a relacao de ordem existente entre o custo total da solucao optimacalculavel em (i) e em (ii)? Justifique.

(c) Formule o problema como em (ii) mas admitindo que, se as areas paraE forem maiores que p, entao as areas para V serao maiores que q (p e qconhecidos).

34


1.13.2 Resolucao

(a)


ARi − no de hectares da zona i para fins residenciaisAV i − no de hectares da zona i para areas verdesAEi − no de hectares da zona i para equipamentos sociais

Restricoes -(i)

∑3i=1ARi ≥ K (1.49)

∀i∈1,2,3AEi

ARi≥ l (1.50)

∀i∈1,2,3AV i

ARi≥ m (1.51)

∀i∈1,2,3 ARi, AV i, AEi ≥ 0 (1.52)

(ii)

∑3i=1ARi ≥ K (1.53)

∀i∈1,2,3

∑3i=1 AEi∑3i=1 ARi

≥ l (1.54)

∀i∈1,2,3

∑3i=1 AV i∑3i=1 ARi

≥ m (1.55)

∀i∈1,2,3 ARi, AV i, AEi ≥ 0 (1.56)

Nota:Poder-se-ia ainda introduzir uma restricao referente ao espaco total dispo-

nıvel em cada zona i, AZi, e que nao pode ser ultrapassado. Embora nao

mencionada explicitamente no enunciado ela e inerente ao problema:

∀i∈1,2,3 ARi +AEi +AV i ≤ AZi (1.57)

Funcao objectivo

min∑3i=1(KRi ARi +KV i AV i +KEi AEi) (1.58)

35


(b)O custo da solucao optima em (i) sera sempre maior ou igual do que o custo

da solucao optima em (ii) pois a formulacao em (i) e mais restritiva do que aformulacao em (ii).

(c)Num Modelo de Programacao Linear a regiao das solucoes admissıveis e ob-

tida pela conjuncao das restricoes formuladas no modelo. Nesta alınea pretende-se modelizar a seguinte implicacao de condicoes:

3∑i=1

AEi > p ⇒3∑i=1

AV i ≥ q

A implicacao de condicoes e modelizada com o auxılio de uma variavel dedecisao suplementar e de um majorante para os valores que as condicoes possamtomar.

Consideremos entao que A = AZ1 +AZ2 +AZ3 e a area total disponıvel nas 3zonas. SendoA a area total e evidente que

∑3i=1AEi ≤ A e que

∑3i=1AV i ≤ A,

ou seja, A e um majorante destes somatorios.Tomando entao uma variavel auxiliar inteira binaria δ ∈ {0, 1}, a implicacao

pode ser formulada do seguinte modo:

3∑i=1

AEi − p− δA ≤ 0 (1.59)

q −3∑i=1

AV i − (1− δ)A ≤ 0 (1.60)

δ ∈ {0, 1} (1.61)

Para verificarmos que as inequacoes 1.59 a 1.61 modelizam a implicacao decondicoes devemos relembrar que para que uma implicacao a⇒ b seja verdadeirae preciso que se a for verdadeira entao b tambem o seja e que se b for falsa entaoa tambem o seja.

De facto, se∑3i=1AEi > p entao para que a restricao 1.59 se verifique e

forcoso que δ = 1. Ora δ = 1 transforma 1.60 em∑3i=1AV i ≥ q, como se

pretendia.Se, por outro lado,

∑3i=1AV i < q entao, para que 1.60 se verifique e forcoso

que δ = 0. Com δ = 0 a restricao 1.59 fica∑3i=1AEi ≤ p, como se queria

demonstrar.

36

1.14 Estaleiro do ShopShopping Exercıcios de Formulacao

1.14 Estaleiro do ShopShopping


Antes de dar inıcio a construcao do ShopShopping, Feimiro necessita de definira localizacao dos estaleiros da obra. Para tal comecou por dividir a area deconstrucao em sectores, tal como se representa na figura seguinte:

AB

C

DE

F

G

H

I

Sabe-se que e possıvel montar no maximo um estaleiro em cada sector e aempresa de Feimiro, a unica que esta habilitada a montar estaleiros em plata-formas marıtimas, monta estaleiros de dois tipos:

• Est α – estaleiro simples, com uma capacidade de movimentacao e arma-zenamento de 1 000 toneladas de materiais durante toda a obra. Este tipode estaleiro so pode fornecer o sector onde esta instalado.

• Est β – grande estaleiro, com uma capacidade de movimentacao e arma-zenamento de 5 000 toneladas de materiais durante toda a obra. Este tipode estaleiro pode fornecer qualquer sector.

Por imposicao das empresas de construcao envolvidas, se for montado 1estaleiro α no sector B, entao e necessario montar um estaleiro β no sector Aou um estaleiro α no sector C.

Por imposicoes regulamentares, o numero mınimo de estaleiros a montarnuma obra desta natureza e com esta area de construcao e 7.

Os custos de montagem de um estaleiro num determinado sector estao re-presentados na tabela seguinte (em 103 e).

Sector A B C D E F G H IEst α 100 100 100 100 100 200 100 50 100Est β 300 300 300 400 200 300 200 100 300

Os custos de funcionamento dos estaleiros tambem foram determinados, esao independentes do tipo de estaleiro. Por cada tonelada de material deslocadade um estaleiro para o sector onde o estaleiro se encontra, o custo fixo e 100 e.A deslocacao de materiais de um estaleiro para um outro sector custa 200 eportonelada.

Preve-se que as necessidades de materiais em cada sector durante toda aobra sejam as seguintes:

Sector A B C D E F G H INec. materiais(em ton) 1000 2000 8000 5000 1000 1500 2000 3000 4000

Construa o modelo de programacao linear para este problema.

37



20 minutos depois de Feimiro ter apresentado o problema completo, ja lhe vaientregar o modelo pedido, pensando que pode ir descansado para casa. No en-tanto, Feimiro esteve entretanto a pensar e quer acrescentar mais uma restricaoao problema.

“Pensei que podera custar menos dinheiro se se obrigar que cada sector sejaalimentado por 1 e 1 so estaleiro. Deve ser facil alterar o modelo, e ja que fezgrande parte do trabalho em tao pouco tempo, ira gastar com esta pequenaalteracao no maximo 2 minutos.”

(a) Sera que Feimiro vai gastar menos dinheiro neste caso? Porque?

(b) Esta nova ideia de Feimiro ira implicar uma alteracao realmente pequena?

(c) Construa o novo modelo.

38


1.14.3 Resolucao parte 1

• Indices

tipo de estaleiro – e ∈ {α, β}sector onde esta o estaleiro– s ∈ {A,B,C,D,E, F,G,H, I}

• Dados

Cape – capacidade total durante a obra (em toneladas) do estaleiro tipoe.

Necs – necessidade total de materiais durante a obra (em toneladas) dosector s.

ces – custo de montagem (em 106 escudos) de um estaleiro tipo e no sectors.


xes

{1 se estaleiro tipo e e montado no sector s0 se nao (1.62)

δ ∈ {0, 1} (variavel auxiliar) (1.63)

• Funcao Objectivo

Pretende-se minimizar a soma dos custos de montagem dos estaleiros comos custos de movimentacao de materiais.

Custos de montagem dos estaleiros:

106 ×∑e,s

ces × xes (1.64)

Custos de movimentacao de materiais (soma do custo de movimen-tacao dos materiais do estaleiro para o sector onde esta montado com ocusto da movimentacao dos materiais do estaleiro para outros sectores):

Custo de movimentacao dos materiais do estaleiro para o sector onde estamontado:

104 ×∑e,s

xes ×minimo(Cape,Necs) (1.65)

Custo de movimentacao dos materiais do estaleiro para outros sectores:

2× 104 × (∑s

Necs −∑e,s

xes ×minimo(Cape,Necs)) (1.66)

• Restricoes

39


∀s∑e xes ≤ 1 (1.67)∑

s xαs ×minimo(Capα,Necs) +∑s xβs ×Capβ ≥

∑s Necs(1.68)∑

e,s xes ≥ 7 (1.69)xαB − δ × 3 ≤ 0 (1.70)

1− (xβA + xαC)− (1− δ)× 3 ≤ 0 (1.71)

As restricoes (1.67)indicam que so se pode montar no maximo um estaleiroem cada sector.

A restricao (1.68) assegura que ha capacidade disponıvel para alimentartodos os estaleiros. Como um estaleiro tipo α so pode alimentar o sectoronde esta montado, a capacidade disponıvel nesse estaleiro sera igual amınimo(Capα,Necs). Os estaleiros β terao que satisfazer as restantesnecessidades.

As restricoes (1.69) impoem um numero mınimo de estaleiros a montar (7neste caso).

As restricoes (1.70) e (1.71) impoem que seja montado um estaleiro β nosector A ou um estaleiro α no sector C se for montado 1 estaleiro α nosector B. Se xαB = 1 entao xβA = 1 ou xαC = 1 ⇔ Se xαB > 0 entaoxβA + xαC ≥ 1 (majorante = 3).


(a) Feimiro esta a introduzir mais restricoes ao problema, por isso o custo dasolucao optima obtida depois de acrescentadas as restricoes so pode terum valor maior ou igual ao custo da solucao optima anterior (ou entao eleesta a pensar noutros custos que nao referiu na alınea (a)).

(b) A alteracao ao modelo inicial e bastante grande, dado que vai ser neces-sario que as variaveis de decisao passem a ter informacao sobre quais osestaleiros que alimentam um determinado sector.

(c) • Indicestipo de estaleiro – e ∈ {α, β}sector onde esta o estaleiro– s ∈ {A,B,C,D,E, F,G,H, I}sector alimentado por estaleiro– k ∈ {A,B,C,D,E, F,G,H, I}

• DadosCape – capacidade total durante a obra (em toneladas) do estaleirotipo e.Neck – necessidade total de materiais durante a obra (em toneladas)do sector k.ces – custo de montagem (em 106 escudos) de um estaleiro tipo e nosector s.


40


xes

{1 se estaleiro tipo e e montado no sector s0 se nao (1.72)

ysk

{1 se estaleiro montado no sector s alimenta o sector k0 se nao (1.73)

δ ∈ {0, 1} (variavel auxiliar) (1.74)

• Funcao ObjectivoPretende-se minimizar a soma dos custos de montagem dos estaleiroscom os custos de movimentacao de materiais.Custos de montagem dos estaleiros:

106 ×∑e,s

ces × xes (1.75)

Custos de movimentacao de materiais (soma do custo de movi-mentacao dos materiais do estaleiro para o sector onde esta montadocom o custo da movimentacao dos materiais do estaleiro para outrossectores):Custo de movimentacao dos materiais do estaleiro para o sector ondeesta montado:

104 ×∑e,s

xes ×Necs (1.76)

Custo de movimentacao dos materiais dos estaleiros para outros sec-tores:

2× 104 × (∑s

Necs −∑e,s

xes ×Necs) (1.77)

• Restricoes

∀s∑e xes ≤ 1 (1.78)

∀k∑s ysk ≤ 1 (1.79)

∀s xαs ×Capα ≥ yss ×Necs (1.80)∀s xβs ×Capβ ≥

∑k (ysk ×Neck) (1.81)∑

e,s xes ≥ 7 (1.82)xαB − δ × 3 ≤ 0 (1.83)

1− (xβA + xαC)− (1− δ)× 3 ≤ 0 (1.84)

As restricoes (1.78) indicam que so se pode montar no maximo umestaleiro em cada sector.As restricoes (1.79) asseguram que cada sector so pode ser alimentadopor um estaleiro.

41


As restricoes (1.80) e (1.81) garantem que um estaleiro so pode ali-mentar um conjunto de sectores, se existir e se tiver capacidade paraalimentar completamente todos esses sectores. Os estaleiros α sopodem alimentar o sector em que se encontram.As restricoes (1.82) impoem um numero mınimo de estaleiros a mon-tar (7 neste caso).As restricoes (1.83) e (1.84) impoem que seja montado um estaleiro βno sector A ou um estaleiro α no sector C se for montado 1 estaleiroα no sector B. Se xαB = 1 entao xβA = 1 ou xαC = 1⇔ Se xαB > 0entao xβA + xαC ≥ 1 (majorante = 3).

42

1.15 Escalonamento de recursos humanos Exercıcios de Formulacao

1.15 Escalonamento de recursos humanos


Um posto de correios requer para funcionar um numero diferente de trabalha-dores a tempo inteiro em cada dia da semana:

No mınimo de funcionarios

Segunda 17Terca 13Quarta 16Quinta 19Sexta 14Sabado 16Domingo 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 Se-gunda a Sexta tera que estar de folga no Sabado e no Domingo. O posto decorreios pretende pois satisfazer as necessidades diarias de trabalhadores recor-rendo apenas a funcionarios a tempo inteiro. O objectivo e minimizar o numerode funcionarios a tempo inteiro.


Suponha agora que as necessidades de mao-de-obra podem ser satisfeitas querpor funcionarios a tempo inteiro quer por funcionarios a tempo parcial. Umfuncionario a tempo inteiro trabalha 8 horas por dia, enquanto um funcionarioa tempo parcial trabalha 4 horas por dia, mantendo-se as restantes condicoeslaborais. No entanto, acordos com os sindicatos limitam a 25% do total apercentagem de funcionarios a tempo parcial. Sabendo que o custo horario deum funcionario a tempo inteiro e de 15 euros e o de um funcionario a tempoparcial e de 10 euros, determine o escalonamento dos funcionarios que minimizao custo global com recursos humanos.


Considere agora que cada funcionario pode fazer um dia de trabalho extraordi-nario por semana. Por exemplo, a um funcionario cujo turno de trabalho seja deSegunda a Sexta pode ser pedido que trabalhe ainda no Sabado. A remuneracaopor hora de trabalho extraordinario corresponde a 150% da remuneracao base.


Considere novamente a situacao inicial, das necessidades de mao-de-obra seremsatisfeitas unicamente por funcionarios a tempo inteiro. Considere ainda queo posto de correios tem 25 funcionarios contratados. Determine o escalona-mento que maximiza o numero de folgas em dias de fim-de-semana (Sabado ouDomingo).

43



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 oproblema de, ao longo do ano, garantir uma escala justa e equilibrada paratodos os trabalhadores em termos de dias de fim-de-semana ocupados?

44



Variaveis de decisao xi – numero de trabalhadores que comecarao o seuperı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 atrabalhar. Note-se que, por exemplo, a Segunda-Feira estao a trabalhar nao so osfuncionarios que iniciam o seu perıodo de 5 dias a Segunda, mas tambem todosos que iniciaram esse perıodo na semana anterior na Quinta-Feira ou depois.

x1 + x4 + x5 + x6 + x7 ≥ 17x1 + x2 + x5 + x6 + x7 ≥ 13x1 + x2 + x3 + x6 + x7 ≥ 16x1 + x2 + x3 + x4 + x7 ≥ 19x1 + x2 + x3 + x4 + x5 ≥ 14

x2 + x3 + x4 + x5 + x6 ≥ 16x3 + x4 + x5 + x6 + x7 ≥ 11

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

Funcao objectivo

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


Variaveis de decisao Teremos agora que considerar tambem os funcionariosa tempo parcial:

xi – numero de trabalhadores a tempo inteiro que comecarao o seu perıodode 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ıodode 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 emtermos de horas de trabalho e nao de numero de funcionarios.

45


8x1 + 87∑i=4

xi + 4y1 + 47∑i=4

yi ≥ 136

82∑i=1

xi + 87∑i=5

xi + 42∑i=1

yi + 47∑i=5

yi ≥ 104

83∑i=1

xi + 87∑i=6

xi + 43∑i=1

yi + 47∑i=6

yi ≥ 128

84∑i=1

xi + 8x7 + 44∑i=1

yi + 4y7 ≥ 152

85∑i=1

xi + 45∑i=1

yi ≥ 112

86∑i=2

xi + 46∑i=2

yi ≥ 128

87∑i=3

xi + 47∑i=3

yi ≥ 88

7∑i=1

yi − 0.257∑i=1

(xi + yi) ≤ 0

∀ixi, yi ≥ 0 e inteiros

Funcao objectivo

min 15 ∗ 8 ∗7∑i=1

xi + 10 ∗ 4 ∗7∑i=1

yi


Variaveis de decisao Teremos que juntar agora novas variaveis correspon-dentes 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 maisum 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 trabalhomais um dia de trabalho extra.

46


Restricoes

8(x1 + z1) + 8z3 + 87∑i=4

(xi + zi) + 4(y1 + w1) + 4w3 + 47∑i=4

(yi + wi) ≥ 136

82∑i=1

(xi + zi) + 8z4 + 87∑i=5

(xi + zi) + 42∑i=1

(yi + wi) + 4w4 + 47∑i=5

(yi + wi) ≥ 104

83∑i=1

(xi + zi) + 8z5 + 87∑i=6

(xi + +zi)43∑i=1

(yi + wi) + 4w5 + 47∑i=6

(yi + wi) ≥ 128

84∑i=1

(xi + zi) + 8z6 + 8x7 + 44∑i=1

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

85∑i=1

(xi + zi) + 8z7 + 45∑i=1

(yi + wi) + 4w7 ≥ 112

8z1 + 86∑i=2

(xi + zi) + 4w1 + 46∑i=2

(yi + wi) ≥ 128

8z2 + 87∑i=3

(xi + zi) + 4w2 + 47∑i=3

(yi + wi) ≥ 88

7∑i=1

yi − 0.257∑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


Variaveis de decisao xi – numero de trabalhadores que comecarao o seuperı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 funcionariosa trabalhar e nao se pode ter mais que 25 funcionarios a trabalhar. No seuconjunto as escalas tem que incorporar 25 funcionarios.

47


x1 + x4 + x5 + x6 + x7 ≥ 17x1 + x2 + x5 + x6 + x7 ≥ 13x1 + x2 + x3 + x6 + x7 ≥ 16x1 + x2 + x3 + x4 + x7 ≥ 19x1 + x2 + x3 + x4 + x5 ≥ 14

x2 + x3 + x4 + x5 + x6 ≥ 16x3 + x4 + x5 + x6 + x7 ≥ 11

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

x2 + x3 + x4 + x5 + x6 ≤ 25x3 + x4 + x5 + x6 + x7 ≤ 25

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

Funcao objectivo A funcao objectivo e agora minimizar o numero de tra-balhadores que pertencem a turnos que trabalhem ao Sabado (dia 6) ou aoDomingo (dia 7), tendo em atencao que alguns turnos sao particularmente pe-nalizantes por ocuparem simultaneamente o Sabado e o Domingo.

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


O problema de escalonamento de recursos humanos aqui resolvido e do tipoestatico porque assume que o posto de correios enfrenta a mesma situacao se-mana apos semana. No entanto, afectar um funcionario permanentemente auma escala traduz-se numa situacao de injustica e desiquilıbrio potenciadora deinstabilidade laboral e de atritos entre funcionarios que em nada contribuempara uma harmoniosa gestao de recursos humanos. A solucao passa portantopor fazer os funcionarios rodar pelas varias escalas.

Suponha entao a seguinte solucao para o problema de escalonamento sema-nal:

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 SegundaSemana 9–14 Inıcio a TercaSemana 15–21 Inıcio a QuintaSemana 22–25 Inıcio ao Sabado

Seguindo esta escala, o funcionario 1 comecaria na semana 1 da escala, ofuncionario 2 comecaria na semana 2 e assim sucessivamente. Por exemplo, ofuncionario 5 faria 4 semanas o turno que se inicia a Segunda, depois faria 6semanas o turno que se inicia a Terca, 7 semanas o turno que se inicia a Quinta,

48


4 semanas o turno que se inicia ao Sabado e, finalmente, 4 semanas o turno quese inicia a Segunda, fechando o ciclo de 25 semanas e recomecando de novo.

Desta forma todos os funcionarios passariam de uma forma equilibrada ejusta por todos os turnos.

49

1.16 SuperBoa Exercıcios de Formulacao

1.16 SuperBoa

1.16.1 Enunciado

A SUPERBOA e uma cerveja produzida em 3 fabricas e e distribuıda a partirde 10 armazens principais.

Recentemente pediram-nos para construir um modelo matematico para oproblema da determinacao da estrategia optima mensal de producao, transportee venda da SUPERBOA. Para tal foi necessario fazer o levantamento de umconjunto alargado de informacoes necessarias para construir o modelo.

Informacoes relativas as fabricas

• Em cada mes a fabrica i, i = 1, 2, 3, produz no maximo ai quilolitros decerveja em regime normal, com um custo ri e por quilolitro.

• Qualquer fabrica tambem pode trabalhar em regime extraordinario, pro-duzindo nessa situacao um maximo de bi quilolitros com um custo si e porquilolitro. (si > ri).

Informacoes relativas ao transporte

• O custo de transporte da fabrica i para o armazem j, j = 1, . . . , 10, e decij e por quilolitro.

• Toda a cerveja produzida num dado mes pode ser transportada, no mesmomes, para os postos de distribuicao.

Informacoes relativas a distribuicao e venda

• No posto j a procura e de dj quilolitros.

• A procura podera nao ser satisfeita, contudo:

– cada kl distribuıdo no armazem j rende αje;

– cada kl que fique por distribuir penaliza a empresa em βje.

• Se a quantidade de cerveja transportada para o armazem j exceder aprocura nesse armazem, o excesso pode ser vendido, em quantidades ili-mitadas, para um armazem de revenda ao preco de γj e por quilolitro,com γj < αj .

Construa o modelo de programacao linear para o problema da determina-cao da estrategia optima mensal de producao, transporte e venda da cervejaSUPERBOA.

50


1.16.2 Resolucao

Indices

i fabricas i ∈ [1, . . . , 3];

j armazens j ∈ [1, . . . 10].


y1i quantidade de kl de cerveja a produzir na fabrica i, em regime normal;

y2i quantidade de kl de cerveja a produzir na fabrica i, em regime extraordinario;

qij quantidade de kl de cerveja a transportar da fabrica i para o armazem j.

Variaveis auxiliares E necessario criar uma variavel auxiliar para cada ar-mazem que possa representar o excesso ou a escassez de cerveja no armazem j.Como as variaveis nos modelos de programacao linear nao podem tomar valoresnegativos, vai ser necessario substituir cada uma pela diferenca de duas variaveisauxiliares que tomem valores maiores ou iguais a zero (uj - vj) onde:

uj excesso de cerveja no armazem j (em kl);

vj escassez de cerveja no armazem j (em kl).

Coeficientes

ai quantidade maxima de cerveja a produzir em regime normal na fabrica i (emkl);

ri custo de producao de cerveja em regime normal (em kl);

bi quantidade maxima de cerveja a produzir em regime extraordinario na fabricai (em kl);

si custo de producao de 1 kl de cerveja em regime extraordinario (em e);

cij custo de transporte de 1 kl de cerveja da fabrica i para o armazem j (em e);

dj procura no armazem j (em kl);

αj preco de venda de 1 kl de cerveja no armazem j (em e);

βj custo por perda de venda de cada kl de cerveja no armazem j (em e);

γj preco de venda a um armazem de revenda de cada kl de cerveja em excessono armazem j (em e).

51


Funcao objectivo Pretende-se com a funcao objectivo encontrar o valor ma-ximo para o lucro, satisfazendo as restricoes impostas. O valor do lucro obtem-se(obviamente) subtraindo as despesas das receitas.

Receitas Venda de cerveja directamente no armazem ((procura no armazemj - escassez no armazem j) × preco de venda no armazem j)∑

j

(dj − vj)αj (1.85)

Venda de cerveja ao armazem de revenda (excesso de cerveja no armazem j ×preco de venda do armazem j ao armazem de revenda)∑

j

ujγj (1.86)

Despesas Despesa com a producao de cerveja em regime normal e com aproducao de cerveja em regime extraordinario.∑

i

(riy1i + siy2i) (1.87)

Despesa com transporte de cerveja da fabrica i para o armazem j.∑i,j

cijqij (1.88)

Despesa com perda de venda de cerveja no armazem j.∑j

vjβj (1.89)

A funcao objectivo sera entao:

max∑j

((dj − vj)αj + ujγj − vjβj)−∑i

(riy1i + siy2i)−∑i,j

cijqij (1.90)

Restricoes

∀i y1i ≤ ai (1.91)∀i y2i ≤ bi (1.92)∀i

∑j qij ≤ y1i + y2i (1.93)

∀j∑i qij − dj = uj − vj (1.94)

∀i,j qij ≥ 0 (1.95)∀j uj , vj ≥ 0 (1.96)∀i y1i, y2i ≥ 0 (1.97)

Considerando que, tal como e afirmado no enunciado, o custo de producaode cerveja em regime normal e inferior ao custo de producao de cerveja emregime extraordinario (ri < si), e dado que o problema e de maximizacao de

52


lucros (minimizacao de custos), nao sera necessario impor restricoes adicionaispara garantir que so se comeca a produzir em regime extraordinario depois dese ter produzido toda a quantidade possıvel em regime normal. Nesse casoas restricoes 1.91 e 1.92 sao suficientes para garantir as restricoes impostas noenunciado.

As restricoes 1.93 garantem que, qualquer que seja a fabrica, a quantidadetransportada dessa fabrica para todos os armazens nao excede a quantidadeproduzida nessa fabrica.

As restricoes 1.95 e 1.97 garantem que as variaveis sao maiores ou iguais azero.

As restricoes 1.94 e 1.96 sao devidas as variaveis auxiliares criadas. Repare-seque assim uma quantidade de cerveja num armazem que seja positiva, negativaou nula, sera representada pela diferenca de duas variaveis ≥ 0.

53

Documents

Exercícios de Formulação (Material Extra)