Pesquisa Operacional

Prévia do material em texto

Pesquisa Operacional
 
1- Uma fábrica produz um determinado produto e o distribui através de 3 fornecedores para 4 consumidores. A disponibilidade deste produto no fornecedor 1 é de 30, no 2 é de 50 e no 3 é de 40 unidades. A necessidade de cada consumidor é de, respectivamente, 40, 30, 20 e 30 unidades. O custo unitário para transportar este produto de um fornecedor para um consumidor é dado pela seguinte tabela (numa certa unidade monetária).
                                                        Consumidores
	 
	 
	1
	2
	3
	4
	Fornecedores
	1
	10
	12
	5
	8
	 
	2
	25
	7
	14
	30
	 
	3
	15
	20
	6
	40
    
Modele matematicamente o problema de modo que a quantidade a ser transportada de um fornecedor para um consumidor tenha um custo de transporte o mínimo possível.
Min Z = 10x11 + 12x12 + 5x13 + 8x14 + 25x21 + 7x22 +14x23 + 30x24 + 
                            +15x31 + 20x32 + 6x33+ 40x34
                              S.a.       x11 +   x12 +   x13   + x14 ≤ 30
                                 x21 +   x22 +  x23   +  x24  ≤ 50
                                 x31 +   x32 +  x33   +  x34  ≤ 40
                                 x11 +   x21 +   x31            =40
                                 x12 +   x22 + x32            = 30
                                 x13   +   x23 +  x33                 = 20
                                 x14   +   x24 +  x34                 = 30
                            xij ≥ 0, i = 1, 2 e 3   e j = 1, 2, 3 e 4.
2- A LCL bicicletas Ltda. é uma empresa fabricante de bicicletas que possui três fábricas localizadas no Rio, em São Paulo e em Belo Horizonte. A produção da empresa deve ser entregue em Recife, Fortaleza e Manaus. Considerando os custos de transporte unitários, a capacidade de produção das fábricas e a demanda dos centros consumidores ilustradas na tabela a seguir. Modele matematicamente o problema de forma a minimizar os custos de transportes na produção e entrega por fábricas em cada centro consumidor.
                                                               Consumidores
	 
	 
	Recife
(1)
	Fortaleza
(2)
	Manaus
(3)
	Capacidade
	Fornecedores
	Rio (1)
	25
	20
	30
	2000
	 
	São Paulo (2)
	30
	25
	25
	3000
	 
	B. Horizonte (3)
	20
	15
	23
	1500
	 
	Demanda
	2000
	2000
	1000
	 
Min Z = 25x11 + 20x12 + 30x13 + 30x21 + 25x22 + 25x23 + 20x31 + 15x32 +23x33
                              S.a.       x11 +   x12 +   x13 + x14 ≤ 2000
                                 x21 +   x22 +   x23 + x24 ≤ 3000
                                 x31 +   x32 +   x33+ x34  ≤ 1500
                                 x11 +   x21 + x31 = 2000
                                x12   +   x22 + x32   = 2000
                               x13   +   x23 + x33   = 1000
                                x14   +   x24 + x34   = 1500
                                     xij ≥ 0,   i = 1, 2, 3    e   j = 1, 2, 3, 4.
3- Seja a seguinte tabela de dados de um problema de transporte:
                                                                   Consumidores
	 
	 
	1
	2
	Oferta
	Fornecedores
	1
	6
	3
	50
	 
	2
	2
	8
	30
	 
	3
	4
	10
	40
	 
	Demanda
	40
	60
	 
 
Formule o problema de modo que o custo de transporte seja o mínimo possível.
 Min Z = 6x11 + 3x12 + 0x13 + 2x21 + 8x22 + 0x23 + 4x31 + 10x32 +0x33
                              S.a.       x11 +   x12 +   x13   ≤ 50
                                 x21 +   x22 +   x23   ≤ 30
                                 x31 +   x32 +   x33  ≤ 40
                                 x11 +   x21 + x31 = 40
                                x12   +   x22 + x32   = 60
                               x13   +   x23 + x33   = 20
                         x11, x12, x13, x21,x22, x23, x31, x32, x33 ≥ 0
4- Considere 3 fábricas produzindo o mesmo produto e 4 depósitos onde estes produtos são estocados para posterior venda. As produções nas fábricas são: a1 = 40, a2 = 80, a3 = 110. Nos depósitos devem ser atendidas as seguintes demandas: b1 = 20, b2 = 30, b3 = 100, b4 = 80. Os custos unitários de transporte do produto são dados por:
	 
	D1
	D2
	D3
	D4
	O1
	10
	5
	12
	4
	O2
	2
	0
	1
	9
	O3
	13
	11
	14
	6
 
Achar um modelo matemático para determinar o programa de entregas do produto com mínimo custo de transporte.
Min Z = 10x11 + 5x12 + 12x13 + 4x14 + 2x21 + 0x22 + 1x23 + 9x24 + 13x31 +
           + 11x32 + 41x33 + 6x34
                              S.a.       x11 +   x12 +   x13 +   x14   ≤ 40
                                 x21 +   x22 +   x23   +   x24   ≤ 80
                                 x31 +   x32 +   x33  +   x34   ≤ 110
                                 x11 +   x21 + x31 = 20
                                 x12   +   x22 + x32   = 30
                                x13   +   x23 + x33   = 100
                                 x14   +   x24 + x34 = 80
                                      xij ≥ 0, i = 1, 2, 3  e   j = 1, 2, 3, 4.
Dado o seguinte quadro de custos de um problema de transporte, formule-o matematicamente.
	 
	 
	 (1)
	 (2)
	 (3)
	 (4)
	Oferta
	Fornecedores
	 (1)
	2
	2
	2
	1
	3
	 
	 (2)
	10
	8
	5
	4
	7
	 
	(3)
	7
	6
	6
	8
	5
	 
	Demanda
	4
	3
	4
	1
	 
 
                                                                   Consumidores
Min Z = 2x11 + 2x12 + 2x13 + x14 + 0x15 + 10x21 + 8x22 + 5x23 + 4x24 + 0x25+
              7x31 +6x32 + 6x33 + 8x34 + 0x35
                              S.a.       x11 +   x12 +   x13 +   x14 +   x15   ≤ 3
                                 x21 +   x22 +   x23  +   x24 +   x25 ≤ 7
                                 x31 +   x32 +   x33 +   x34 +   x35 ≤ 5
                                 x11 +   x21 + x31 = 4
                                 x12   +   x22 + x32   = 3
                                x13   +   x23 + x33   = 4
                                 x14   +   x24 + x34 = 1
                                 x15   +   x25 + x35 = 3
                      x11, x12, x13, x14, x15, x21,x22, x23, x24, x25, x31, x32, x33, x34, x35 ≥ 0
5- Certa empresa fabrica dois produtos P1 e P2. O lucro unitário do produto P1 é de R$ 
1.000,00 e o lucro unitário de P2 é R$ 1.800. A empresa precisa de 20 horas para 
fabricar uma unidade de P1 e de 30 horas para fabricar uma unidade de P2. O tempo 
anual de produção disponível para isso é de 1200horas. A demanda esperada para 
cada produto é de 40 unidades para P1 e 30 unidades para P2. Construa o modelo de 
programação linear que objetiva Maximizar o lucro. 
Max Z = 1000x + 1.800y 
Restrições: 
20x + 30y ≤ 1.200 
x ≤ 40 
y ≤ 30 
x , y ≤ 0
6- A necessidade mínima de vitaminas na alimentação é de 32 unidades por dia e a de 
proteínas de 36 unidades por dia. Uma pessoa tem disponível carne e ovo para se 
alimentar. Cada unidade de carne contém 4 unidades de vitaminas e 6 unidades de 
proteínas. Cada unidade de ovo contém 8 unidades de vitaminas e 6 unidades de 
proteínas. Construa o modelo de que objetiva Minimizar o custo. Cada unidade de carne custa 
R$ 3,00 e cada unidade de ovo custa R$ 2,5
Min Z = 3x + 2,5y 
Restrições: 
4x + 8y ≥ 32 
6x + 6y ≥ 36 
x, y ≥ 0 
7- Um sapateiro faz 6 sapatos por hora, se fizer somente sapatos e 5 cintos por hora, se fizer somente cintos. Ele gasta 2 unidades de couro para fabricar 1 unidade de sapato e 1 unidade de couro para fabricar 1 unidade de cinto. Sabendo-se que o total disponível de couro é de 6 unidades e que o lucro unitário por sapato é de 5 reais e o de cinto é de 4 reais, pede-se: o modelo do sistema de produção do sapateiro, se o objetivo é maximizar seu lucro por hora. 
Max Z = 5x + 4y 
Restrições: 
x/6 + y/5 ≤ 1
2x + y ≤ 6 
x ≤ 6
y  ≤  5 
x , y ≤ 0 
8- Considere uma Companhia distribuidora de bebidas supondo que ela dispõe de dois depósitos para abastecer os mercados consumidores. Para evitar ambigüidade, enumera-se cada localidade distintamente – os centros de produção: Araraquara(1), S. J. dos Campos(2); os depósitos: Campinas(3), Barra Mansa(4); e os mercados consumidores: São Paulo(5), Belo Horizonte(6) e Rio de Janeiro(7). Suponha que os mercados sejam abastecidos somente a partirdos depósitos. Os custos unitários de se transportar uma unidade do produto de cada centro de produção para cada depósito e de cada depósito para cada mercado consumidor são dados nas tabelas (1) e (2) a seguirem. Represente o modelo matemático do problema.
 Tabela 1: Custos unitários de transporte de centros de suprimento aos depósitos.
	 
	Depósitos
	Suprimentos
disponíveis
	 
	Campinas(3)
	Barra Mansa(4)
	
	Araraquara(1)
	1
	3
	800
	S. J. Campos(2)
	1
	2
	1000
 Tabela 2: Custos unitários dos depósitos aos mercados consumidores.
	Depósitos
	Mercados Consumidores
	
	São Paulo(5)
	Belo Horizonte(6)
	Rio de Janeiro(7)
	Campinas(3)
	1
	3
	3
	Barra Mansa(4)
	3
	4
	1
	Demanda
	500
	400
	900
Min Z = x13 + 3x14 + x23 + 2x24 + x35 +3x36 + 3x37 + 3x45 + 4x46 + x47
                              S.a.       x13 +   x14 ≤ 800
                                 X23 +   x24 ≤ 1000
                                 x35 +   x45 = 500
                                 x36 +   x46  = 400
                                x37   +   x47 = 900
                               x13   +   x23 = x35   + x36   +   x37
                              x14 +  x24 = x45   + x46   +   x47  
                          x13, x14, x23, x24,x35, x36, x37, x45, x46, x47 ≥ 0
9- Um hospital necessita comprar 3 bombonas de insumos para manipular soros quimioterápicos para serem consumidos durante o corrente mês e 4 bombonas para o mês subseqüente. O insumo é perecível e só pode ser utilizado no mês da compra. Dois laboratórios (X e Y) fornecem os medicamentos. O hospital está limitado a comprar 5 bombonas de cada laboratório e os preços de venda de cada laboratório estão descritos na tabela a seguir. Determine o custo mínimo de compra das quantidades requeridas dos medicamentos, utilizando o método de transporte.
	 
	Mês 1
	Mês 2
	X
	R$ 800
	R$ 720
	Y
	R$ 710
	R$ 750
 R$ 5070,00
10- Considere uma companhia distribuidora de bebidas que tem os centros de produção e suponha que ela dispõe de dois depósitos para abastecer os mercados consumidores. Para evitar ambigüidade, enumera-se cada localidade distintamente – os centros de produção: Fab(1), Fab(2), Fab(3) e Fab(4) ; os depósitos: CD(1), CD(2); e os mercados consumidores: Cliente(1), Cliente(2) e Cliente(3). Suponha que os mercados sejam abastecidos somente a partir dos depósitos. Os custos unitários de se transportar uma unidade do produto de cada centro de produção para cada depósito e de cada depósito para cada mercado consumidor ao menor custo possível são apresentados na tabela a seguir. Represente o modelo matemático do problema.
Tabela 1: Custos unitários de transporte de uma unidade do produto de cada centro de produção para cada depósito.
	 
	Depósitos
	disponibilidade
	 
	CD(1)
	CD(2)
	
	Fab(1)
	$7,5
	$9,3
	540
	Fab(2)
	$8
	$10
	720
	Fab(3)
	$5
	$7
	830
	Fab(4)
	$6
	$8
	1010
Tabela 2: Custos unitários dos depósitos para cada mercado consumidor.
	Depósitos
	Mercados Consumidores
	
	Cliente(5)
	Cliente(6)
	Cliente(7)
	CD(1)
	$8
	$7
	$10
	CD(2)
	$9
	$4,5
	$5,6
	Demanda
	980
	1250
	870
Min Z = 7,5x11 + 9,3x12 +8 x21 + 10x22 + 5x31 +7x32 + 6x41 + 8x42 +
              + 8x15 + 7x16 +10 x17 + 9x25 + 4,5x26 +5,6x27
                   S.a.       x11 +   x12 ≤ 540
                                 X21 +   x22 ≤ 720
                                 x31 +   x32 ≤ 830
                                 x41 +   x42  ≤ 1010
                                x15   +   x25 = 980
                                                       x16 +   x26 = 1250
                                                        x17   +   x27 = 870
           x11 +   x21 + x31 +   x41 = x15   + x16   +   x17
          x12 +   x22  + x32  +   x42 = x25   + x26   +   x27
           x11, x12, x15, , x16, , x17, x21, x22, , x25, , x26, x27,  x31, x32, x41, x42 ≥ 0
11- O problema de transportes consiste em determinar as quantidades de um determinado produto que deverão ser transportados de m origens para n destinos, dadas as restrições de oferta máxima associadas a cada origem e as restrições de demanda associadas a cada destino. De acordo com a tabela a seguir, determine o custo mínimo para o transporte de produtos, utilizando Método de Vogel.
	 
	D1
	D2
	D3
	Oferta
	01
	5,00
	6,00
	8,00
	120
	
	
	
	
	
	02
	4,00
	7,00
	9,00
	80
	03
	6,00
	8,00
	7,00
	90
	Demanda
	90
	110
	70
	 
 
 
 
  
1520,00
Uma companhia locadora de automóveis se defronta com um problema de alocação resultante dos contratos de locação que permitem sejam os automóveis devolvidos em localidades outras que aquelas onde foram originalmente alugados. No presente momento há duas agências de locação com, respectivamente, 15 e 13 carros excedentes e quatro outras agências necessitando de 9, 6, 7 e 9 carros, respectivamente. Os custos unitários de transportes, em dólares, entre as locadoras são os seguintes:
	 
	Destino 1
	Destino 2
	Destino 3
	Destino 4
	Origem 1
	45
	17
	21
	30
	Origem 2
	14
	18
	19
	31
Utilize o método de Vogel para obter a alocação de carros a um custo total mínimo.
$547
Obtenha o custo total mínimo do seguinte problema através do método de Vogel:
	 
	A
	B
	C
	Oferta
	1
	8
	5
	6
	120
	2
	15
	10
	12
	80
	3
	3
	9
	10
	80
	Demanda
	150
	70
	60
	 
 
 
  
1920 u.m
12- Use o método de Vogel para resolver o problema a seguir de forma que o custo total seja mínimo.
	 
	1
	2
	3
	4
	5
	Disponibilidade
	 A
	2
	3
	1
	2
	3
	20
	B
	2
	5
	1
	1
	4
	30
	C
	2
	1
	1
	3
	2
	40
	D
	1
	4
	4
	3
	1
	10
	Demanda
	25
	15
	10
	10
	40
	 
185 m
13- Determine o menor custo possível do seguinte problema utilizando o método de Vogel.
	 
	1
	2
	3
	Origem
	1
	5
	3
	2
	100
	2
	4
	2
	1
	50
	Demanda
	80
	30
	40
	 
520 m
Determine pelo método Vogel, a solução ótima para o problema de transporte do quadro:
	 
	D1
	D2
	D3
	D4
	D5
	Disponibilidade
	O1
	16
	14
	12
	12
	16
	170
	O2
	12
	4
	14
	8
	8
	60
	O3
	8
	6
	4
	14
	10
	90
	Demanda
	15
	69
	36
	18
	42
	 
 
1446
Suponha que Inglaterra, França e Espanha produzem todo o trigo, cevada e aveia disponível no mundo.  A demanda mundial de trigo corresponde à produção de 50 milhões de hectares de solo. Também são necessários 24 milhões de hectares para cevada e 30 milhões para aveia. O total de solo agrícola disponível para este propósito, em Inglaterra, França e Espanha é de, respectivamente, 28 milhões, 44 milhões e 32 milhões de hectares, respestivamente. O número de horas de trabalho necessárias para produzir 1 hectare de trigo é de 45h em Inglaterra, 32h30min em França e 40h em Espanha. No caso do cevada são necessárias 37h30min em Inglaterra e 30h em França e em Espanha. Para o aveia são precisas 30h em Inglaterra, 25 em França e 40 em Espanha. O custo da hora de trabalho para produção de trigo é de 3 u.m., 2.4 u.m. e 3.3 u.m., respectivamente em Inglaterra, França e Espanha. Para a produção de cevada o custo da hora de trabalho será de 2.7 u.m., 3.0 u.m. e 2.8 u.m. em Inglaterra, França e Espanha. No caso da aveia haverá um custo da hora de trabalho de 2.3 u.m. em Inglaterra, 2.5 u.m. em França e 2.1 u.m. em Espanha. O problema é definir a melhor distribuição da produção em cada país, de forma a satisfazer as necessidades mundiais de trigo, cevada e aveia mas minimizando o custo de produção total. Assinale o valor ótimo da função objetivo que esta minimização:
8340
14- A prefeitura de uma cidade está fazendo obras em três bairros. O material para essas obras é 
transportado de três depósitos O1, O2 e O3 de onde são retiradas 57, 76 e 93 toneladas de material, 
respectivamente. As obras são destinadas para os bairros D1, D2 e D3, que necessitam diariamente de 
41, 80 e 105 toneladas, respectivamente. Os custos unitários para o transporte desse material estão na 
tabela a seguir.  
 
Tabela 01 - Custos Unitários dos Transportes (R$/unidade) 
               Destino 01 Destino 03 Destino 03 
Depósito 01         7         8          4 
Depósito 02         5         6          3 
Depósito 03         6         54 
 
Determine o custo de transportea partir do Método de Aproximação de Vogel. 
R$ 990,00 
15- Uma empresa com 3 centros de produção, A, B e C estão situados em diferentes localidades, com capacidades de produção, respectivamente, de 100, 120 e 120 unidades de um determinado produto e abastece 5 centros de distribuição, D, E, F, G e H também situados em diferentes locais, que movimentam, respectivamente, 40, 50, 70, 90 e 90 unidades. Determine a solução básica inicial do problema pela regra do canto noroeste para encontrar o plano mais econômico entre os centros de produção e distribuidores. Os custos unitários são apresentados na tabela a seguir:
 
	 
	D
	E
	F
	G
	H
	A
	4
	1
	2
	6
	9
	B
	6
	4
	3
	5
	7
	C
	5
	2
	6
	4
	8
1550 u.m
16-  Maximizar o problema de transporte a seguir utilizando o método do canto noroeste:
	 
	A
	B
	C
	D
	Disponibilidade
	1
	80
	70
	60
	60
	8
	2
	50
	70
	80
	70
	10
	3
	70
	50
	80
	60
	5
	Demanda
	5
	4
	6
	4
	 
 
1440 
Determine as quantidades de um determinado produto que deverão ser transportadas de m origens para n destinos por um custo mínimo utilizando o método do Canto Noroeste. Os custos unitários, as ofertas e as demandas são dadas na tabela a seguir.
	 
	D1
	D2
	D3
	Oferta
	01
	5,00
	6,00
	8,00
	120
	02
	4,00
	7,00
	9,00
	80
	03
	6,00
	8,00
	7,00
	90
	Demanda
	90
	110
	70
	
1680,00
17- Use o método do canto noroeste para minimizar o problema de transporte a seguir:
 
	Origem
	Destinos
	Capacidade
	
	A
	B
	C
	D
	
	1
	45
	17
	21
	30
	15
	2
	14
	18
	19
	31
	13
	Demanda
	9
	6
	7
	9
	 
826 u.m
 
18- Uma empresa distribuidora tem três depósitos que estocam respectivamente 160, 200 e 100 unidades de um produto, e deve abastecer quatro clientes cujos pedidos são de 100,80 120 e 80 unidades, respectivamente. Os custos unitários de transporte dos depósitos para os clientes estão na tabela:
 
	 
	C1
	C2
	C3
	C4
	D1
	2,1
	1,8
	1,8
	1,8
	D2
	1,5
	2,4
	1,8
	2,1
	D3
	2,4
	1,5
	2,4
	1,8
 
A solução ótima para o problema é: 630
19- A empresa Dalai Lama deseja planejar a produção de incenso. Os incensos requerem dois tipos de recursos: mão de obra e materiais. A empresa fabrica três tipos de incenso, cada qual com diferentes necessidades de mão de obra e materiais, conforme tabela abaixo:
  
	   
 
   
	   
Modelo
   
	
	   
A
   
	   
B
   
	   
C
   
	   
Mão   de Obra (horas/unidade)
   
	   
7
   
	   
3
   
	   
6
   
	   
Materiais   ( g/unidade)
   
	   
4
   
	   
4
   
	   
5
   
	   
Lucro   (R$/unidade)
   
	   
4
   
	   
2
   
	   
3
   
 
                                                                          
A disponibilidade de materiais é de 200 g/dia. A mão de obra disponível por dia é de 150 h.
 
Formule um problema para determinar  quanto deve ser produzido de cada tipo de incenso, tal que o lucro seja maximizado.
Max L = 4x + 2y + 3z 
Restrições: 
7x + 3y + 6z ≤ 150
4x + 4y + 5z ≤ 200
x , y , z ≤ 0 
Dada a seguinte tabela inicial abaixo com os dados do problema, encontre uma tabela de solução utilizando o método do "canto noroeste".
 
RESP:
20- Uma companhia de transportes possui 5 caminhões disponíveis localizados nas cidades A, B, C, D e E. Necessita-se de um caminhão nas cidades 1, 2, 3,4 5 e 6. Qual a designação dos caminhões que minimize a quilometragem percorrida por todos os caminhões, dado a quilometragem entre as cidades abaixo?
	Origem 
	Destinos
	 
	1
	2
	3
	4
	5
	6
	 A
	20
	15
	26
	40
	32
	12
	B
	15
	32
	46
	26
	28
	20
	 C
	18
	15
	2
	12
	6
	14
	D
	8
	24
	12
	22
	22
	20
	E
	12
	20
	18
	10
	22
	15
55 km
21- Resolva o problema de designação a seguir de forma a minimizar o custo total:
	 
	A
	B
	C
	D
	1
	10
	23
	8
	9
	2
	4
	5
	6
	7
	3
	12
	10
	10
	8
	4
	6
	4
	9
	7
24
22- Resolva o problema de designação, onde o símbolo X indica a impossibilidade da designação da origem para o destino correspondente:
	 
	1
	2
	3
	1
	6
	X
	8
	2
	4
	9
	3
	3
	5
	6
	4
	4
	8
	10
	12
 
15 
 
 
 
 
	
23- Em uma empresa quatro operários são designados para realizar quatro tarefas de maneira que o tempo total para o término de todas as tarefas seja o menor possível. Resolva o problema sabendo que o tempo que cada operário gasta para desempenhar cada uma das 4 tarefas é dado na tabela a seguir:
 
	 
	I
	II
	III
	IV
	A
	5
	24
	13
	7
	B
	10
	25
	3
	23
	C
	28
	9
	8
	5
	D
	10
	17
	15
	3
 20
 
24- Considerando os dados de custos da tabela a seguir, faça a alocação dos caminhões às rotas de entrega, de modo que o custo total seja o menor possível. Qual o valor do custo total?
	 
	Rota
	Caminhões
	A
	B
	C
	D
	E
	1
	4
	5
	9
	8
	7
	2
	6
	4
	8
	3
	5
	3
	7
	3
	10
	4
	6
	4
	5
	2
	5
	5
	8
	5
	6
	5
	3
	4
	9
18
25- A tabela a seguir contém informações sobre o custo da execução de três tarefas em
quatro máquinas disponíveis. Uma alocação de tarefas que minimize os custos é:
	 
	Máquinas
	Tarefas
	A
	B
	C
	D
	1
	12
	16
	14
	10
	2
	9
	8
	13
	7
	3
	15
	12
	9
	11
27
26- O quadro representa os custos de transporte de uma máquina dos locais de depósito para as fábricas onde deverão ser instaladas.
 Designar uma máquina para cada fábrica com o menor custo total possível:
 
total custo 50
27- O quadro representa os custos de transporte de uma máquina dos locais de depósito para as fábricas onde deverão ser instaladas.
Qual a melhor solução de designação visando o menor custo total possível:
 
 
L1 para F1
L2 para F2
L3 para F4
L4 para F3
28- Maximize o seguinte problema utilizando o algoritmo da designação:
	 
	A
	B
	C
	D
	1
	8
	6
	2
	4
	2
	6
	7
	11
	10
	3
	3
	5
	7
	6
	4
	5
	10
	12
	9
35
Uma empresa vende produtos em quatro regiões e possui quatro vendedores que devem atender quatro regiões diferentes, sendo um vendedor para cada região. As regiões não são igualmente ricas e apresentam o seguinte potencial de venda (em $):
Região 1: 60.000
Região 2: 50.000
Região 3: 40.000
Região 4: 30.000
Os vendedores não são igualmente hábeis e as suas eficiências, que refletem a capacidade de atingir o mercado potencial da região, são dados pelo quadro a seguir:
 
	 
	Regiões
	Vendedores
	I
	II
	III
	IV
	 1
	0,7
	0,7
	0,7
	1,0
	2
	0,8
	0,8
	0,8
	1,0
	3
	0,5
	0,5
	0,5
	1,0
	4
	1,0
	0,4
	1,0
	0,4
 R$ 158.000,00
 Determine pelo algoritmo da designação como enviar os vendedores às regiões para que o volume de vendas total das quatro regiões seja o maior possível.
  
29-  Encontre a solução do problema de designação de forma a maximizar os lucros desejados:
 
	 
	A
	B
	C
	I
	6
	10
	5
	 II
	5
	8
	7
	III
	X
	10
	8
	IV
	7
	9
	9
25 
Quatro locais, L1, L2, L3, L4 necessitam de um equipamento. Existem
quatro equipamentos disponíveis, um em cada um dos depósitos
D1, D2, D3, D4. A quilometragem entre os locais necessitados e os
depósitos estão no quadro:
 
 
Determine um programa de expedição de quilometragem mínima.
D1 para L1
D2 para L2
D3 para L3
D4 para L4
O caso de maximização em um problema de designação deve ser resolvido através:  
da substituíção por outro de minimização.
30- Qual dos passos abaixo não faz parte do algoritmo de designação?
I - Subtrair o elemento mínimo de cada linha de todos os elementos daquela linha.
II - Subtrair o elemento mínimo de cada coluna de todos os elementos daquela coluna.
III - Somar o elemento mínimo de cada linha de todos os elementos daquela linha. 
III - Somar o elemento mínimo de cada linha de todos os elementos daquela linha. 
31- O quadro abaixo representa os ganhos unitários devido à venda de mercadorias compradas nas origens e comercializadas nos destinos. O objetivo é maximizar
o retorno na distribuição das mercadorias das origens para os destinos.
 
720
32- Marque a alternativa que representa simplificadamente o algoritmo para a solução de um caso de maximização em um problema de designação.
Multiplicar todos os elementos da matriz C por (-1)
 Identificar o elemento de maior valor em módulo
Somar o elemento de maior módulo a todos os elementos da nova matriz de custos (já multiplicada por (-1))Resolver como se fosse de minimização
33- De que modo o algoritmo  de Ford-Fulkerson impede a formação de ciclos?
 Considerando somente as arestas com uma extremidade rotulada e a outra não.
42-Em que caso pode uma aresta (i,j) ser usada como progressiva bem como regressiva de uma trajetória em uma rede com um fluxo dado?
Se o fluxo fij < cij , bem como  fij >0.
34- Considere um sistema viário de uma zona urbana entre os pontos X e P. A tabela 1 apresenta a capacidade de tráfego em viaturas/horas nos pontos A, B e C. Deve-se obedecer um sentido obrigatório de trânsito que são entre os pontos A, B e C e os pontos D, E e F e as capacidade de tráfego são indicados na tabela 2. Em seguida, a capacidade de tráfego em viaturas/horas nos pontos D, E e F são apresentadas na tabela 3. 
	Pontos
	Capacidade de Tráfego
	A
	70
	B
	80
	C
	60
  
Tabela 1: Capacidade de tráfego em viaturas/horas nos pontos A, B e C.
 
	Pontos de origem 
	Pontos de destino
	
	D
	E
	F
	A
	30
	40
	0
	B
	30
	30
	60
	C
	0
	30
	20
  Tabela 2: Capacidade de tráfego em viaturas/horas entre os pontos A, B e C e os pontos D, E e F.
 
	Pontos
	Capacidade de Tráfego
	D
	70
	E
	70
	F
	70
               Tabela 3: Capacidade de tráfego em viaturas/horas nos pontos D, E e F.
 O número de viaturas/hora, no máximo, que podem atingir o ponto P é:
200
35- Uma empresa de consultoria pretende reorganizar uma industria de maneira a dimimnuir o tempo de fabricação de um dos seus produtos, ou seja, cadeira de espaltar alto. PAra isto, fez um levantamento de todas necessárias para a produção da cadeira. Esse levantamento é apresentado na tabela e gráficos seguintes:
A - B - D - F - H; 17 dias
Você precisa fazer uma viagem de carro para outra cidade que jamais havia estado anteriormente. Portanto, você está estudando um mapa para determinar a rota mais curta para seu destino. Dependendo de qual rota você escolher, há cinco outras cidades (chamemos estas A, B, C, D, E) que talvez você passe durante o caminho. O mapa mostra a milhagem ao longo de cada estrada que conecta diretamente duas cidades sem qualquer cidade entre elas. Esses números são sintetizados na tabela a seguir, na qual um traço indica que não há nenhuma estrada conectando diretamente essas duas cidades sem passar por alguma outra cidade.
Selecione a alternativa que representa o caminho mais curto: 
160 MILHAS
	
Num projeto de lançamento de um novo produto foi programado, com base na rede acima, o tempo necessário para a sua execução. Na qualidade de gestor do projeto, a qual seqüência de atividades você dispensaria maior atenção, objetivando não atrasar o lançamento do produto 
(caminho crítico)? 
 
BCH
 
Encontre a trilha mais curta entre os nós 1 e 6 da figura abaixo:
 
6 - 5- 4 - 1
Uma fábrica de artigos de decoração, localizada em Lambari, deve entregar uma grande quantidade de peças na cidade de Baependi.
A empresa quer saber qual a menor distância que seu caminhão pode percorrer para chegar a seu destino.
 
54
A rede do shopping Dom Perso necessita interligar todos os postos de guarda por uma linha telefônica.
Quais caminhos deverão ser escolhidos de forma a utilizar a menor quantidade possível de cabos?
OA, AB, CB, BE, ED, DT	
Seja o seguinte diagrama de redes:
 
 
Assinale a alternativa correta: A atividade F é representada pelo conjunto de nós 3, 5.