exercícios pl

Capítulo 1

Exercícios de Programação linear

1.1 Resolução geométrica de problemas lineares

Exercício 1.1.1 Para cada um dos casos a seguir indicados represente a regiãoadmissível e determine os valores máximo e mínimo da função z:

a)

z = 2x1 + 3x2 + 2

x1 + x2 � 1

x1 � 2

2x1 � x2 � 5

�x1 + x2 � 2

�x2 � 4

b)

z = 2x1 � x2 + 5

x1 � 0

x2 � 0

�x1 � x2 � 1

�x1 + 2x2 � 4

�x1 + 2x2 � �5

1

Exercícios de Programação Matemática 2

c)

z = x1 + x2

2x1 � x2 � 0

x1 + x2 � 140

3x1 + x2 � 300

x1 � 0

x2 � 0

Exercício 1.1.2 Resolva gra�camente os seguintes problemas de programação linear

a)

Min z = �9x1 + 6x2�x1 + x2 � 3

x1 + x2 � 7

3x1 � 2x2 � 15

x1 � 0

x2 � 0

b)

Max z = 2x1 + x2

10x1 + 10x2 � 9

10x1 + 5x2 � 1

x1 � 0

x2 � 0

x1 e x2 inteiros


c)

Max z = �2x1 � 3x2x1 + x2 � 4

6x1 + 2x2 � 8

x1 + 5x2 � 4

x1 � 3

x2 � 3

x1 � 0

x2 � 0

d)

Max z = x1

x1 + 4x2 � 41

2x1 +

1

2x2 = 1

�x1 + x2 � �2

x1 � 0

x2 � 0

e)

Max z = �4x1 + 5x2�x1 + x2 � 0

x1 � 0

x1 � 0

x2 � 0


f)

Min z = �x1 + x22x1 + 3x2 � 7

�4x1 � 6x2 � �14

x2 � 1

2

x1 + x2 � 2

x1 � 0

x2 � 0

Exercício 1.1.3 Para a região admissível de�nida por

8>>>>>>>>><>>>>>>>>>:

�x1 + x2 � 1

6x1 + 4x2 � 24

x2 � 2

x1 � 0

x2 � 0obtenha a solução óptima para cada um dos seguintes objectivos:

a) Max z = x1

b) Min z = x1 + x2

c) Min z = x2

d) Max z = x2

e) Min z = x1 � x2

f) Min z = x1

g) Min z = �x1 + x2

h) Min z = 3x1 + 2x2

Exercício 1.1.4 Uma empresa produz dois tipos de cintos, A e B. Os lucros unitáriosrespectivos são de 80 cêntimos e 35 cêntimos. Cada cinto do tipo A exige o dobro


do tempo necessário à fabricação de um cinto do tipo B. A empresa pode fabricardiariamente 1000 cintos tipo B. A quantidade de cabedal fornecido à empresa é ape-nas su�ciente para fabricar diariamente 800 cintos. O cinto de tipo A necessita deuma �vela de luxo e só se dispõe diariamente de 400 dessas �velas. Para o cinto detipo B pode-se dispor diariamente de 700 �velas.

a) Formalize e resolva gra�camente o problema.

b) Haverá alteração da solução óptima no caso do lucro unitário para os cintosde tipo A ser de um euro?

c) Suponha que era imposta uma produção de pelo menos 300 cintos de tipo B.Obtenha a nova solução óptima.

1.2 Problemas sobre convexidade

Exercício 1.2.1 Mostre que os seguintes conjuntos são convexos

a) S = f(x1; x2; x3) 2 R3 : x1 + 2x2 � x3 = 4g

b) S = f(x1; x2; x3) 2 R3 : x1 + 2x2 � x3 � 4g

c) S = f(x1; x2; x3) 2 R3 : x1 + 2x2 � x3 � 4 ^ 2x1 � x2 + x3 � 6g

d) S = f(x1; x2) 2 R2 : x2 � jx1jg

e) S = f(x1; x2) 2 R2 : x21 + x22 � 4g

Exercício 1.2.2 Mostre que se S1 e S2 são conjuntos convexos então:

a) S1 \ S2 é convexo

b) S1 � S2 = fx+ y : x 2 S1 ^ y 2 S2g é convexo

c) S1 S2 = fx� y : x 2 S1 ^ y 2 S2g é convexo

Exercício 1.2.3 Determine gra�camente os pontos extremos e as direcções (se ashouver) e direcções extremas dos seguintes conjuntos:

a) S = f(x1; x2) 2 R2 : x21 + x22 � 1g


b) S = f(x1; x2) 2 R2 : x1 + x2 � 2 ^ �x1 + 2x2 � 2 ^ x1 � 0 ^ x2 � 0g

c) S = f(x1; x2) 2 R2 : x2 � jx1jg

Exercício 1.2.4 Seja S um convexo em En, A uma matriz m�n e � 2 R. Mostreque os seguintes conjuntos são convexos

a) AS = fy 2 Em : y = Ax; x 2 Sg

b) �S = fy 2 En : y = �x; x 2 Sg

Exercício 1.2.5 Determine os pontos extremos de

S =�(x1; x2) 2 R2 : �x1 + 2x2 � 6 ^ x1 + x2 � 5 ^ x1 � 0 ^ x2 � 0

inspeccionando todas as soluções básicas admissíveis

1.3 Formalização de problemas

Exercício 1.3.1 Uma gelataria confecciona e vende três tipos de gelados (1, 2 e3) à base de ananás (A), morango (M) e chocolate (C). Cada gelado requer umadeterminada quantidade dos sabores disponíveis, de acordo com a tabela:

A M C

1 3 4 -

2 2 - 1

3 - 1 2

As quantidades de ananás, morango e chocolate estão limitadas a 120, 60 e 30bolas de cada, respectivamente. A procura é tal que todos os gelados são vendidos.Sabendo que o preço de venda é de 50, 40 e 20 u.m., respectivamente para os geladostipo 1, 2 e 3, formule o problema de modo a determinar o programa de produção quemaximize a facturação

Exercício 1.3.2 Dispondo apenas de fígado e salsichas e sabendo que 1 kg de fígadocusta 1 euro, fornece 300 calorias e 28 unidades de gordura; e que 1 kg de salsichascusta 1,5 euros, fornece 400 calorias e 8 unidades de gordura; pretende-se determinara dieta mais económica para um animal, sabendo que as suas necessidades diáriassão de pelo menos 400 calorias e não mais de 28 unidades de gordura. Formalize oproblema.


Exercício 1.3.3 Uma empresa de refrigerantes tem que planear a sua produçãopara o próximo mês. Na composição do refrigerante a fabricar a empresa utilizatrês variedades diferentes de fruta - Tipo I, II e III - com custos por kg de 12, 20 e30 cêntimos, respectivamente. Da fruta Tipo I extrai-se 0.35 litros de sumo por kg,enquanto que das frutas Tipo II e III se extraem, respectivamente, 0.4 e 0.6 litrospor kg. Cada litro de refrigerante tem que apresentar pelo menos 90% de sumo defruta e 1 mg de vitamina C. A fruta do Tipo I contém 0.5 mg dessa vitamina porkg, enquanto que a Tipo II contém 0.75 mg, e a Tipo III 1 mg também por Kg. Paramanter o sabor agradável, em cada 10 litros de sumo não pode haver mais de 8 Kgde fruta de Tipos I e II. Formalize um problema que permita à empresa determinara quantidade de fruta de cada tipo a utilizar para cada 10 litros de sumo fabricado,de modo a minimizar os custos.

Exercício 1.3.4 Uma moeda deve ser cunhada numa liga contendo pelo menos 40%de prata e pelo menos 50% de cobre. Para o fabrico dessa liga estão disponíveisquatro tipos diferentes de outras ligas com as seguintes composições e custos (emeuros por kg):

A B C D

%prata 30 35 50 40

%cobre 60 35 50 45

custo 3000 3200 4000 3500

Construa um modelo que permita obter a mistura das ligas A, B, C e D quecorresponda ao custo mínimo.

Exercício 1.3.5 Uma fábrica de tintas fabrica tintas para interior e para exteriorusando dois tipos diferentes de matéria prima A e B.

toneladas de matéria prima por tonelada de tinta

exterior interior máximo disponível

Matéria prima A 1 2 6

Matéria Prima B 2 1 8

Além disso, uma pesquisa de mercado estabeleceu que por dia a procura de tintainterior não excede em mais do que 1 unidade a procura de tinta exterior e que não


são gastas mais do que 2 toneladas de tinta interior. A tonelada de tinta interiorcusta 2000 euros e a tonelada de tinta exterior custa 3000 euros. Sendo o objectivomaximizar o volume de vendas, qual deverá ser a produção diária de cada tipo detinta?

Exercício 1.3.6 Uma empresa produz dois produtos: comida para pássaros e co-mida para cães. A empresa tem dois departamentos: mistura e empacotamento.Os requisitos em cada departamento para produzir uma tonelada de qualquer dosprodutos são os seguintes:

Tempo por tonelada em horas

Mistura Empacotamento

Comida de pássaro 0.25 0.10

Comida de cão 0.15 0.30

Cada departamento dispõe de 8 horas por dia de trabalho. A comida de cão éfeita de três ingredientes: carne, pasta de peixe e cereais. A comida de pássaro éfeita de três ingredientes: sementes, pequenos seixos e cereais. A composição destes5 materiais é a seguinte:

Descrição dos materiais em percentagens

Proteínas Carbohidratos Minerais Abrasivos Custo por ton.

Carne 12 10 1 0 600

Pasta de peixe 20 8 2 2 900

Cereais 3 30 0 0 200

Sementes 10 10 2 1 700

Pedras 0 0 3 100 100

Os requisitos mínimos da composição dos dois produtos são os seguintes (empercentagem do peso total):

Proteínas Carbohidratos Minerais Abrasivos Sementes

C. de pássaro 5 18 1 2 10

C. de cão 11 15 1 0 0


A comida de pássaro vende-se a 750 u.m. por tonelada, enquanto que a comidade cão se vende a 980 u.m. por tonelada.Admitindo que não há problemas de escoamento da produção, formalize um

problema que permita determinar a composição de cada tipo de comida e a quanti-dade de cada uma a produzir, de modo a maximizar o lucro.

Exercício 1.3.7 Uma empresa de construção civil foi encarregada da realizaçãode uma importante obra de remoção de terras e pretende renovar o seu parquede camiões. Existem no mercado dois tipos de veículos, A e B, cujos preços ecaracterísticas técnicas se indicam no quadro abaixo. A empresa possui actualmente20 camiões de tipo C (cujas características se indicam também no quadro) que podevender (no todo ou em parte) por 1 500 euros cada. A empresa dispõe de 200 000euros para a aquisição de veículos, não contando com as receitas de eventuais vendasdos camiões que possui. Os camiões trabalharão num sistema de dois turnos diários,perfazendo um total de 340 horas de operação por mês em média. Cada camião éoperado por um condutor por turno, mas não se considera possível contratar mais de100 condutores. Todos os veículos necessitam de manutenções periódicas de que �-carão encarregados dois mecânicos, cada um dos quais com um horário de 170 horaspor mês.

Preço Velocidade média, incluindo Tempos médios de

Veículos (euros) tempos de carga e descarga manutenção por cada 1 000 km

(km/hora) (horas)

A 6 500 20 5

B 4 000 13 5

C - 10 10

Formule um modelo de programação linear que permita determinar o número decamiões a comprar e vender e que maximize a capacidade de transporte em toneladaskm.

Exercício 1.3.8 O dono de um grande restaurante tem o problema de plani�cara existência de toalhas lavadas disponíveis para os sete dias da semana. Podemcomprar-se toalhas novas no início da semana ao preço de 5 euros cada. Depois deusadas podem ser lavadas numa lavandaria com dois tipos de serviço: um serviço


rápido, em que uma toalha é lavada em 1 dia (o que quer dizer que uma toalha usadana segunda se encontra disponível novamente para uso na quarta) e um serviço lento,em que uma toalha é lavada em 2 dias. Cada toalha lavada no serviço rápido temum custo de 1,5 euros, enquanto que no serviço lento tem um custo de 0,5 euros.De segunda a domingo são necessárias, respectivamente, 110, 100, 160, 120, 180,200 e 120 toalhas. No �m de cada semana todas as toalhas são vendidas por 1 eurocada. Formule o problema de determinar a forma de se satisfazer as necessidadesem toalhas, com um custo mínimo.

Exercício 1.3.9 Um armazenista, que comercializa um determinado produto ali-mentar, deseja programar as suas compras para os primeiros 4 meses do ano: Janeiro,Fevereiro, Março e Abril. O preço praticado pelo seu fornecedor habitual é de 100u.m. por cada unidade de produto comprada nos 3 primeiros meses e de 150 u.m.por cada unidade comprada em Abril. O fornecedor habitual pode fornecer no má-ximo 3500 unidades de produto por mês. Caso o armazenista deseje comprar maisdo que esta quantidade, num determinado mês, poderá adquirir até ao máximo de1000 unidades a um outro fornecedor cujos preços são 25% mais elevados do queos praticados pelo fornecedor habitual. O armazenista pode criar stock do produto,sendo o custo de armazenagem por unidade e por mês de 40 u.m.. A procura asatisfazer pelo armazenista nos 4 meses é a seguinte: 1500, 3500, 4500, 4000. Ostock em armazém no início de Janeiro é de 100 unidades. Sabendo que no �nal deAbril não deve existir qualquer stock de produto, construa um modelo de programaçãolinear que permita de�nir o plano de compras óptimo.

1.4 Resolução algorítmica de Problemas

Exercício 1.4.1 Considere as seguintes restrições de um problema de programaçãolinear:

x1 + x2 + x3 = 1

x1 � x2 + x4 = 0xi � 0; i = 1; � � � ; 4

Determine todas as soluções básicas do problema, indicando se são ou não admis-síveis e, em caso a�rmativo, se são ou não degeneradas.


Exercício 1.4.2 Considere o seguinte problema de programação linear:

Max z = 5x1 � 3x2x1 � x2 � 22x1 + 3x2 � 4�x1 + 6x2 = 10

x1 � 0

Escreva o problema na forma standard.

Exercício 1.4.3 Resolva os seguintes problemas de programação linear através doalgoritmo simplex:

a)

Max z = 4x1 + 3x2

�x1 + x2 � 34x1 + x2 � 8x1 � 0;x2 � 0

b)

Min z = �6x1 � 3x22x1 + 4x2 � 7204x1 + 4x2 � 880

x1 � 160x1 � 0;x2 � 0

c)

Max z = 2x1 + 3x2

�4x1 + 2x2 � 1�x1 + 2x2 � 6x1 � 0;x2 � 0


d)

Min z = �4x1 + x2 + 30x3 � 11x4 � 2x5 + 3x6�2x1 + 6x3 + 2x4 � 3x6 + x7 = 20�4x1 + x2 + 7x3 + x4 � x6 = 10�5x3 + 3x4 + x5 � x6 = 60

xi � 0; i = 1; � � � ; 7

e)

Max z = 5x1 + x2 + 3x3 + 4x4

x1 � 2x2 + 4x3 + 3x4 � 20�4x1 + 6x2 + 5x3 � 4x4 � 402x1 � 3x2 + 3x3 + 8x4 � 50

xi � 0; i = 1; � � � ; 4

Exercício 1.4.4 Na resolução, pelo método simplex, de um problema de progra-mação linear de maximização, obteve-se o seguinte quadro:

x1 x2 x3 x4 x5

2 1 0 0 � 1

3 0 1 0 0 3

� 0 0 1 4

0 0 0 � -5

Indique, justi�cando, a que condições devem obedecer �; �; � e , para serem ver-dadeiras as seguintes a�rmações:

a) Encontrou-se uma solução óptima não degenerada

b) Existem soluções óptimas alternativas

c) A solução é não limitada

d) A solução é degenerada


e) Ainda não foi encontrada solução óptima

Exercício 1.4.5 Aplicando o método das duas fases, resolva os seguintes problemas:

a)

Max z = 8x1 + 10x2

x1 + 2x2 � 21 � x1 � 3

4x1 + 5x2 � 20x1 � 0; x2 � 0

b)

Min z = x1 + x2 � x44x1 + x2 + x3 + 4x4 = 8

x1 � 3x2 + x3 + 2x4 = 16xi � 0; i = 1; � � � ; 4

c)

Max z = 3x1 � 2x2 � 2x3 + 2x4�x1 + 3x2 � x3 + 2x4 = 1�2x1 + 4x3 � x4 = 8

2x1 � 2x2 + 2x3 + x4 = 2xi � 0; i = 1; � � � ; 4

d)

Min z = x1 + 2x2 � 4x4x1 � x2 + 3x3 = 1x2 � 2x3 + x4 = 1

3x1 + x2 + x3 + 4x4 = 7

xi � 0; i = 1; � � � ; 4


e)

Min z = x1 + x2

3x1 + 2x2 � 4x1 + 2x2 � 6x1 � 2x2 � 4x1 � 0

Exercício 1.4.6 Suponha que tem dois pontos extremos soluções óptimas de umprograma linear: X e Y. Demonstre que qualquer ponto da aresta que une X e Ytambém é solução óptima.

Exercício 1.4.7 Considere o seguinte quadro do simplex, correspondente a umasolução intermédia na resolução de um problema de maximização:

v. básicas x1 x2 x3 x4 x5 x6

x1 4 1 2=3 0 0 4=3 0

x4 2 0 �7=3 3 1 �2=3 0

x6 2 0 �2=3 �2 0 2=3 1

z � 8 0 �8=3 11 0 �4=3 0

Sabendo que a inversa da matriz dos coe�cientes das variáveis básicas a que esta

solução corresponde é B�1 =

266641=3 1=3 �1=3

1=3 �2=3 2=3

�1=3 2=3 1=3

37775 e que cTB = h1 3 �1

i,

formule o problema original.

1.5 Dualidade

Exercício 1.5.1 Considere o problema

Min z = 3x1 + 2x2

x1 � x2 � 1x1 + x2 � 3x1 � 0;x2 � 0


a) Escreva o seu dual

b) Resolva o dual gra�camente

c) Resolva o primal pelo método simplex

d) Veri�que as relações de complementaridade ente o primal e o dual.

Exercício 1.5.2 Resolva os seguintes problemas através da solução óptima dorespectivo dual:

a)

Min z = 2x1 + x2

3x1 + x2 � 34x1 + 3x2 � 6x1 + 2x2 � 2x1 � 0;x2 � 0

b)

Max z = 8x1 + 8x2

2x1 + 2x2 � 122x1 + x2 � 9x1 + 3x2 � 16x1 � 0;x2 � 0

c)

Max z = 2x1 + 7x2 + 4x3

x1 + 2x2 + x3 � 103x1 + 3x2 + 2x3 � 10x1 � 0;x2 � 0;x3 � 0

d)

Min z = 6x1 + x2 + 2x3

3x1 + x2 + 2x3 � 22x1 � x2 + 2x3 � 3

x1 � 0x2 e x3 livres


Exercício 1.5.3 Resolva os seguintes problemas através do algoritmo simplex-dual

a)

Min z = x1 + 3x2

x2 � 1x1 + 2x2 � 8x1 + x2 � 5x1 � 0;x2 � 0

b)

Min z = x1 + x2

2x1 � 2x2 � x3 = 2�x1 + x2 � x4 = 1x1 + x2 � 5

xi � 0; i = 1; � � � ; 4

c)

Min z = 2x1 + 10x2

x1 + 4x2 � 1004x1 + 20x2 � 480x1 � 0;x2 � 0

d)

Max z = �x1 � x2x1 + x2 � 8x2 � 3

�x1 + x2 � 2x1 � 0;x2 � 0


e)

Min z = 7x1 + 2x2 + 5x3 + 4x4

2x1 + 4x2 + 7x3 + x4 � 58x1 + 4x2 + 6x3 + 4x4 � 83x1 + 8x2 + x3 + 4x4 � 4x1 � 0; i = 1; � � � ; 4

Exercício 1.5.4 Considere um problema de programação linear em que o objectivo

é: Min z = 16x1 + 10x2 + 4x3: Seja A =

266641 1 1

2 0 1

4 2 0

37775 a matriz dos coe�cientesdas suas restrições. Quanto ao respectivo problema dual sabe-se que o vector dos

coe�cientes das variáveis na função objectivo éh4 2 2

i, que a primeira variável

de decisão não tem restrição de sinal e que a segunda variável de decisão é positivaou quando muito nula. Além disso, sabe-se que na solução óptima a terceira restriçãodo primal é veri�cada 8 unidades acima do limite mínimo, a terceira restrição dodual é veri�cada 9 unidades acima do limite mínimo, e as restantes restrições doprimal e do dual são veri�cadas em igualdade. Deve determinar os valores de todasas variáveis do primal e do dual (decisão e afastamento), sem utilizar o algoritmosimplex para a resolução do problema. Justi�que teoricamente as suas conclusões.

Exercício 1.5.5 Ao resolver o problema de programação linear

Min z = �6x1 � 5x20:2x1 + 0:1x2 � 90:3x1 + 0:1x2 � 60:3x1 + 0:6x2 � 180:2x1 + 0:2x2 � 14x1 � 0;x2 � 0


obteve-se o quadro

x1 x2 x3 x4 x5 x6

x4 5 0 0 2 1 0 �1=2

x1 20 1 0 10 0 0 �5

x2 50 0 1 �10 0 0 10

x5 18 0 0 �3 0 1 9=2

z + 370 0 0 10 0 0 20

Determine a solução óptima do problema dual

Exercício 1.5.6 Considere o seguinte quadro �nal do simplex aplicado a um prob-lema de programação linear em que x3 e x4 são variáveis de afastamento das suasduas restrições. Sabe-se que a primeira restrição é do tipo � e que a segunda é dotipo � :

x1 x2 x3 x4

8 1 1 0 1

8 0 2 1 1

z + 8 0 1=2 0 1

a) Indique as soluções óptimas deste problema e do seu dual.

b) Escreva ambos os problemas.

Exercício 1.5.7 O quadro seguinte foi o terceiro e último a ser obtido na resoluçãode um problema de programação linear em que as restrições são todas do tipo �

x1 x2 x3 x4 x5

1 0 0 1 �1 1

6 1 0 0 1 �1

5 0 1 0 0 �1

0 0 0 2 1


a) Estabeleça o problema linear original.

b) Escreva o problema dual.

c) Escreva as soluções óptimas do primal e do dual.

Exercício 1.5.8 Considere o seguinte programa linear:

Min z = 3x1 + 4x2

x1 + 2x2 � 142x1 + x2 � 97x1 + 6x2 � 14

0 � x1 � 6; 0 � x2 � 6

a) Resolva-o gra�camente, indicando com clareza quais os limites da regiãoadmissível.

b) Escreva o problema dual e, a partir do resultado da alínea anterior, diga quaisas variáveis que serão nulas na solução óptima do problema dual.

c) Resolva o problema inicial usando a versão do método simplex que achar maisconveniente e indique no grá�co que desenhou em a) o percurso efectuado pelométodo.

1.6 Análise de sensibilidade e pós-optimização

Exercício 1.6.1 Resolveu-se o problema de programação linear

Maximizar z = x1 + x2

sujeito a 2x1 � x2 � 0

x1 + x2 � 140

3x1 + x2 � 300

x1 � 0;x2 � 0


e obteve-se a solução óptima x1 = 60; x2 = 120 e z = 180. Entretanto pretende-se

fazer as seguintes alterações: alterar o termo independente para b(t) =

26664t

140 + t

300� t

37775e o custo de x1 para c1(t) = 1� 4t.Para que valores de t a presente solução continua a ser óptima?

Exercício 1.6.2 Ao resolver o problema de programação linear

Maximizar z = 2x1 + x2 � x3sujeito a x1 + 2x2 + x3 � 8

�x1 + x2 � 2x3 � 4

x1 � 0;x2 � 0;x3 � 0

a) Se for proposta uma nova actividade associada à coluna a6 =h1 2

iTe com

lucro c6 = 4, será essa actividade atractiva? Em caso a�rmativo determine anova solução óptima.

b) Determine a nova solução óptima no caso do coe�ciente de x3 na segundarestrição mudar de �2 para 1.

c) Determine a nova solução óptima no caso do coe�ciente de ser acrescentadaa restrição x2 + x3 � 2:

Exercício 1.6.3 Para o seguinte problema

Maximizar z = x1 +32x2 + 2x3

sujeito a x1 + x2 + x3 � 20

x1 +12x2 +

32x3 � 15

x1 � 0;x2 � 0;x3 � 0


sabe-se que o quadro óptimo é o seguinte:

x1 x2 x3 x4 x5

x2 151

21 0

3

2�1

x3 51

20 1 �1

21

z � 652

�34

0 0 �54

�12

a) Faça uma análise de sensibilidade ao coe�ciente de x3 na função objectivo.

b) Determine a nova solução óptima no caso do termo independente da segundarestrição passar a ser 8.

c) Determine a nova solução óptima no caso de ser acrescentada a restriçãox1 + x3 � 10:

d) Determine a nova solução óptima no caso de ser acrescentada uma variável

com coe�ciente na função objectivo5

4e coluna

24 10

35 :Exercício 1.6.4 Considere o problema de programação linear

Maximizar z = cTx

sujeito a Ax = b

x � 0

a) Se x� for uma solução óptima deste problema será também uma solução óptimapara o problema em que os custos são �c, com � > 0?

b) E para o problema em que esse vector é c + �e, com e =h1 1 � � � 1

iTe

� 6= 0? Em que condições continua a ser óptima?


1.7 Problemas de transportes

Exercício 1.7.1 Uma empresa responsável pelo abastecimento semanal de certobem às cidades de Lisboa e Porto pretende estabelecer um plano de distribuiçãodesse bem a partir dos centros produtores situados em Peniche, Viseu e Évora.As quantidades semanalmente disponíveis em Peniche, Viseu e Évora são 70,

130 e 120 toneladas, respectivamente. O consumo semanal previsto desse bem éde 180 toneladas em Lisboa e de 140 no Porto. Os custos unitários de transporte(u.m./ton.) de cada centro produtor para cada centro consumidor são os seguintes:

Lisboa Porto

Peniche 13 25

Viseu 25 16

Évora 15 40

Formule um problema de programação linear que lhe permita encontrar o planode distribuição que minimize os custos de transporte.

Exercício 1.7.2 Uma cooperativa de lavradores tem dois armazéns centrais quefornecem sementes de cereal a três armazéns regionais que as distribuem aos lavradores.Mensalmente cada armazem central dispõe de 1000 a 2000 toneladas de sementes.A procura nos armazéns regionais é de 1500, 750 e 750 toneladas. O custo detransportar cada tonelada é dado por:

Armazéns locais

Armazéns

centrais

1 2 3

1 50 100 60

2 30 20 35

Sendo o objectivo satisfazer a procura ao menor custo, estudar qual a política detransportes a adoptar.

Exercício 1.7.3 Três re�narias com capacidades máximas diárias de 6 milhões,5 milhões e 8 milhões de galões de gasolina abastecem três áreas de distribuiçãocom necessidades diárias de 4 milhões, 8 milhões e 7 milhões de galões. A gasolina é


transportada através de uma rede de pipelines. O custo de transportar é directamenteproporcional à distância percorrida pela gasolina. A re�naria 1 não está ligada coma área de distribuição 3. O quadro seguinte dá as distâncias, em milhas, entre cadare�naria e cada área de distribuição:

Áreas de distribuição

Re�narias

1 2 3

1 120 180 -

2 300 100 80

3 200 250 120

Pretendendo-se minimizar os custos de transporte, formule o problema seguindo omodelo de transportes e resolva-o.

Exercício 1.7.4 Resolva o seguinte problema de transportes:

Minimizar z = 5x11+ 3x12+ 2x13+ 4x21+ 2x22+ x23

sujeito a x11+ x12+ x13 = 100

x21+ x22+ x23 = 50

x11+ x21 = 80

x12+ x22 = 30

x13+ x23 = 40

x11 � 0; x12 � 0; x13 � 0; x21 � 0; x22 � 0; x23 � 0

Exercício 1.7.5 Resolva os seguintes problemas de transportes:

a)

1 2 3 4 Oferta

1 8 3 5 9 20

2 1 7 4 6 70

3 3 8 2 4 10

Procura 25 35 20 20


b)

1 2 3 Disponível

1 8 9 7 20

2 9 8 6 30

3 5 8 3 40

4 4 9 6 40

Necessário 10 70 10

c)

1 2 3 4 5 Oferta

1 8 6 3 7 5 20

2 5 * 8 4 7 30

3 6 3 9 6 8 30

Procura 25 25 20 10 20

� � Percurso impossível

d)

1 2 3 Disponível

1 6 7 8 12

2 4 6 7 15

3 5 7 6 21

Necessário 15 48 33

Exercício 1.7.6 Uma companhia fabrica e transporta cimento para os seus ar-mazéns. As fábricas são F1, F2 e F3 e os armazéns são A1, A2, A3 e A4. Os custosunitários de transporte bem como as disponibilidades nas fábricas e as necessidades


nos armazéns são dadas na seguinte tabela:

A1 A2 A3 A4 Produção

F1 8 3 5 9 40

F2 1 7 4 6 40

F3 3 8 2 4 25

Necessidades 30 20 35 10

a) Qual a solução óptima deste problema?

b) Suponha que a produção nas fábricas que não possa ir para os armazéns dacompanhia, tenha que ir para armazéns alugados de forma que cada unidadenão enviada para os armazéns da companhia custe 8, 4 e 3 respectivamentepara F1, F2 e F3. Determine a nova solução óptima.

Exercício 1.7.7 Suponha que num problema de transportes se adiciona uma con-stante k a cada um dos custos da matriz cij. Qual a alteração na solução óptima eno respectivo valor da função objectivo?

Exercício 1.7.8 6A companhia japonesa Kayoto tem 3 fábricas em países do 3o

Mundo que produzem um determinado componente electrónico que vai ser usado em4 unidades de montagem no Japão. As fábricas têm capacidade semanal de produzir32 000, 27 000 e 18 000 componentes respectivamente, enquanto que as unidades demontagem usam 20 000 componentes por semana cada uma. O custo de transportarcada mil componentes de cada fábrica para cada unidade de montagem é dado, emdólares, no seguinte quadro:

Unidades de montagem

Fábricas

1 2 3 3

1 80 130 40 70

2 110 140 60 110

3 60 120 80 90

Se uma unidade de montagem não receber todas as componentes de que necessita,a Kayoto tem que lhe pagar uma multa. Essa multa é de 5 dólares por cada 500


componentes para a unidade 1, 8 dólares por cada 1000 componentes para a unidade2 e de 4 dólares por cada 1000 componentes para a unidade de montagem 3, enquantoque a unidade de montagem 4 não estabelece multas. Pretende-se determinar quala política de transportes a adoptar de modo a minimizar o custo total da operação.

Capítulo 2

Programação inteira

2.1 Branch-and-bound

Exercício 2.1.1 Resolva os seguintes problemas através do algoritmo branch-and-bound:

a)

Maximizar z = 2x1 + x2

sujeito a 4x1 + 5x2 � 20

x1 � x2 � 1

x1 � 0;x2 � 0

x1 e x2 inteiros

b)

Maximizar z = x1 + x2


6x1 + 5x2 � 30

x1 � 0;x2 � 0

x1 e x2 inteiros

27


c)

Maximizar z = x1 + 3x2


2x1 + 7x2 � 14

x1 � 0;x2 � 0

x1 e x2 inteiros

d)

Minimizar z = 2x1 + 3x2

sujeito a x1 + x2 � 3

x1 + 3x2 � 6

x1 � 0;x2 � 0

x1 e x2 inteiros

Exercício 2.1.2 Ao resolver-se um problema linear inteiro, cujo objectivo era aminimização de uma função de 4 variáveis inteiras pelo método de branch-and-bound, obteve-se no nó inicial a seguinte solução: x1 = 0; x2 = 0:75; x3 = 10:25; x4 =3, ao que corresponde para a função objectivo o valor 17. Diga, justi�cando, se asseguintes situações são ou não possíveis:

a) Obter solução ilimitada num dos subproblemas.

b) Obter z = 16:5 num dos subproblemas.

c) Obter solução impossível num dos subproblemas.

d) Obter a solução x1 = 10:5; x2 = 0; x3 = 0; x4 = 5:5 num dos subproblemas.

Exercício 2.1.3 Na resolução de um problema de programação inteira, em que oobjectivo é minimizar uma função z de�nida em R25, obteve-se no nó inicial umasolução não inteira com z = 100. Escolheu-se a variável x10 para começar a construira árvore do algoritmo de branch-and-bound. No lado esquerdo obteve-se uma soluçãointeira com z = 120. No lado direito obteve-se uma solução em que todas as variáveissão inteiras excepto x9 que tem o valor 4:7 e a que corresponde z = 130. O que sedeve fazer a seguir? Porquê?


Exercício 2.1.4 Considere o seguinte problema de programação linear inteira

Maximizar z = 5x1 + x2

sujeito a �x1 + 2x2 � 4

x1 � x2 � 1

4x1 + x2 � 12

x1 � 0;x2 � 0

x1 e x2 inteiros

a) Resolva o problema linear associado gra�camente

b) Arredonde a solução obtida para a solução inteira mais próxima e veri�que seé admissível

c) Enumere todas as soluções inteiras que podem ser obtidas por arredondamento(por excesso e por defeito) e veri�que quais as admissíveis.

d) Resolva o problema gra�camente por recurso ao branch-and-bound.

e) Pode concluir alguma coisa?

2.2 Inteiros Mistos

Exercício 2.2.1 Considere o seguinte modelo matemático:Minimizar Z = f1(x1) + f2(x2) com as restrições:

� Ou x1 � 3 ou x2 � 3;

� Pelo menos uma das seguintes desigualdades deve ser verdadeira:2x1 + x2 � 7;x1 + x2 � 5;x1 + 2x2 � 7

� jx1 � x2j = 0 ou 3 ou 6;

� x1 � 0 e x2 � 0;

Sendo f1(x1) =

8<: 7 + 5x1 se x1 > 0

0 se x1 = 0e f2(x2) =

8<: 5 + 6x2 se x2 > 0

0 se x1 = 0

Formule o problema como um problema de programação linear inteira misto.

Capítulo 3

Programação não linear

3.1 Condições de Karush-Kuhn-Tucker

Exercício 3.1.1 Escreva as condições KKT para o seguinte problema não linear:

Maximizar f(x1; x2) = 15x1 + 30x2 + 4x1x2 � 2x21 � 4x22sujeito a x1 + 2x2 � 30

x1 � 0;x2 � 0

Exercício 3.1.2 Escreva as condições KKT para o seguinte problema não linear:

Maximizar f(x1; x2) = 3x1 + 5x2

sujeito a 9x21 + 5x22 � 216

x1 � 4

x1 � 0;x2 � 0

Resolva o problema gra�camente e veri�que que o ponto encontrado obedece àscondições escritas.

30

Documents

exercícios pl