Fichas de Investigação Operacional1

Prévia do material em texto

Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios estudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mz Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Zicai Zicai Zicai Zicai FazendaFazendaFazendaFazenda 
Investigação Operacional - Programação Linear. Método Simplex. Análise de sensibilidade. Transportes e stocks 1 
 
CadernoCadernoCadernoCaderno de Exercícios de de Exercícios de de Exercícios de de Exercícios de 
 
Investigação OperacionalInvestigação OperacionalInvestigação OperacionalInvestigação Operacional 
 
2011 
 
 
 
 
 
 
 
 
 
 
 
Docentes: Rodrigues Zicai Fazenda 
Lionel Nhambe 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios estudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mz Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Zicai Zicai Zicai Zicai FazendaFazendaFazendaFazenda 
Investigação Operacional - Programação Linear. Método Simplex. Análise de sensibilidade. Transportes e stocks 2 
 
Programação Linear. Método SimplexProgramação Linear. Método SimplexProgramação Linear. Método SimplexProgramação Linear. Método Simplex 
 
1- A fábrica de gelados Derretem-se na Boca SARL fabrica duas qualidades de gelados: cassata 
de nozes (C) e pistachio de frutas (P). A loja encontra-se localizada numa animada área turística 
de modo que toda a produção é sempre vendida. Um cone de C custa 75,00Mtn enquanto um 
cone de P custa 60,00Mtn. Um cone de C necessita de 4 gr de mistura de frutas e de 2gr de noz 
moída. Um cone de P requer 6gr de mistura de frutas e 1gr de noz moída. Contudo, apenas 
podem ser produzidas por hora 96gr de mistura de frutas e 24gr de noz moída. Quantos cones de 
cada tipo devem ser fabricados de modo a maximizar a receita em cada hora? 
Represente graficamente a solução do problema. 
 
2- Uma empresa labora em dois processos produtivos fabricando dois produtos de grande 
consumo P1 e P2. No primeiro processo, 1 Kg de matéria-prima dá origem a 2 unidades de P1 e 
1 de P2, resultando 20 gramas de um resíduo altamente poluente. No segundo processo, gastando 
a mesma quantidade de matéria-prima obtém-se 1 unidade de P1 e 3 unidades de P2, gerando 10 
gramas do mesmo resíduo. A empresa dispõe de 3 toneladas de matéria-prima e deve satisfazer 
encomendas de 2000 unidades de P1 e 4000 unidades de P2. A empresa pretende minimizar a 
quantidade produzida de resíduo poluente. Formule matematicamente o problema e resolva-o 
graficamente. Quais as quantidades de P1 e P2 produzidas em cada processo? Qual a quantidade 
de matéria-prima não utilizada? Qual a quantidade total de resíduo poluente produzido? 
 
3- Um empresa de electrónica fabrica dois tipos de circuitos impressos A e B. Os do tipo A são 
vendidos por 4000 mil Meticais e os do tipo B por 5000 mil Meticais. No processo produtivo 
ambos os tipos de circuitos passam por duas máquinas. Na primeira máquina os circuitos são 
trabalhados durante 4 horas os do tipo A e 5 horas os do tipo B. Na outra máquina os circuitos 
passam 4 e 3 horas, respectivamente. A primeira máquina pode funcionar durante um máximo de 
32 horas, enquanto a outra máquina não pode exceder as 24 horas de funcionamento. A empresa 
pretende maximizar a receita. Formule matematicamente o problema e resolva-o graficamente. 
Qual a receita máxima que a empresa pode obter? 
 
4- Devido a alterações de mercado os preços dos produtos A e B referidos no problema anterior 
caíram para 4000 e 3000 mil Meticais respectivamente. Simultaneamente, modificações no 
processo produtivo, requeridas por um mais rigoroso controlo de qualidade, levaram à aquisição 
de uma nova máquina onde tanto o produto A como o produto B sofrem operações com a 
duração de 1 hora. No entanto, esta máquina não pode funcionar menos de 8 horas semanais. 
Reformule o problema com as novas condições representando graficamente a região admissível. 
 
5- Três produtos (1, 2, 3) são manufacturados passando por três operações diferentes (A, B, C). 
Os tempos (em minutos) requeridos por unidade de cada produto, a capacidade diária das 
operações de fabrico (em minutos/dia) e o lucro por unidade vendida de cada produto (numa 
dada unidade monetária) são os seguintes: 
Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios estudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mz Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Zicai Zicai Zicai Zicai FazendaFazendaFazendaFazenda 
Investigação Operacional - Programação Linear. Método Simplex. Análise de sensibilidade. Transportes e stocks 3 
 
 
Operação Tempo por unidade Capacidade 
 Produto 1 Produto 2 Produto 3 Operativa (min/dia) 
A 1 2 1 430 
B 3 0 2 460 
C 1 4 0 420 
Lucro unitário (u.m.) 3 2 5 max 
 
Supondo que toda a produção é vendida, formule o problema como um de programação linear de 
modo a obter um lucro máximo. 
 
6- Um agricultor pode usar dois tipos de cereais para alimentar as suas galinhas, de acordo com a 
tabela : 
 
Cereal Unidades nutritivas (Kg/cereal) Custo/Kg cereal 
 Vitamina A Vitamina B Vitamina C (esc.) 
1 5 4 2 60 
2 7 2 1 350 
 
O número mínimo de unidades nutritivas requeridas por dia é de 8, 15 e 3 para as vitaminas A, B 
e C, respectivamente. Sabendo que se pretende minimizar o custo da alimentação das galinhas, 
formule o problema como um de programação linear. 
 
7- Uma companhia produz dois tipos de fertilizantes: fosfato-HI e fosfato-LO. Para a sua 
produção são usados 3 materiais de base, do modo indicado no quadro : 
 
 
Material 
Ton. material 
produção de uma 
requeridas para a 
ton. de fosfato 
Quantidade max. 
disponível/mês (ton.) 
LO HI 
A 2 1 1500 
B 1 1 1200 
C 1 0 200 
 
Cada unidade (tonelada) dos fertilizantes é vendida por 15 u.m. (fosfato-HI) e 10 u.m. (fosfato-
LO). Apresente a formulação matemática deste problema por forma a maximizar a receita 
mensal. 
 
8- Uma empresa deseja realizar um "show" na televisão para publicitar os seus produtos. O 
"show" durará exactamente 30 minutos e nele actuarão um actor cómico e um grupo musical. A 
empresa deseja que sejam consagrados a anúncios pelo menos 4 minutos. A estação de TV exige 
que o tempo dedicado aos anúncios não exceda 8 minutos, não podendo, além disso, em caso 
algum ser superior ao tempo atribuído ao actor cómico. Este, por sua vez, não está disposto a 
actuar durante mais de 15 minutos. Ao grupo musical caberá o tempo restante. O custo de 
Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios estudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mz Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Zicai Zicai Zicai Zicai FazendaFazendaFazendaFazenda 
Investigação Operacional - Programação Linear. Método Simplex. Análise de sensibilidade. Transportes e stocks 4 
actuação do actor é de 200,00Mt./minuto e o do grupo musical é 1000,00Mt./minuto. Sondagens 
recentes mostram que: 
- por cada minuto em que o actor se exibe 4000 espectadoresligam o televisor para essa estação; 
- por cada minuto de actuação do grupo musical esperam-se 2000 novos espectadores; 
- por cada minuto de anúncios 1000 pessoas desligam o aparelho ou ligam para outra estação. 
De modo a tomar uma decisão fundamentada a empresa pretende dispor de programas que: 
 a) maximizem o número de espectadores 
 b) minimizem o custo dos "shows". 
Formule-os matematicamente ambos os problemas. 
Resolva-os usando o algoritmo simplex. 
 
9- A Companhia Vidreira (CV) fabrica em três centros de produção (CP) produtos de vidro de 
alta qualidade, incluindo janelas e portas de vidro. No CP1 são produzidos caixilhos de 
alumínio, no CP2 caixilhos de madeira e o CP3 é usado para produzir o vidro e fazer a 
montagem final dos produtos. Devido a uma diminuição das receitas, a administração resolveu 
introduzir algumas alterações na linha de produção. Alguns produtos que se revelaram não 
lucrativos deixam de ser fabricados, de modo a libertar capacidade de produção para fabricar 
outros produtos para os quais existe procura potencial. Um destes produtos (P1) é uma porta de 
vidro com caixilho de alumínio. O outro produto (P2) é uma janela com caixilho de madeira. O 
departamento de marketing concluíu que a CV conseguirá vender toda a produção que for 
possível realizar com a capacidade disponível. Os dados do problema estão agrupados na 
seguinte tabela: 
 
Centro de 
Produção 
Capacidade 
por 
usada 
unidade 
Capacidade 
disponível 
Produto 1 Produto 2 
CP1 1 0 4 
CP2 0 2 12 
CP3 3 2 18 
Lucro unitário (u.m.) 3 5 
 
a) Construa um modelo matemático par o problema de maximizar o lucro da CV. 
b) Resolva o problema graficamente. 
c) Resolva o problema usando o método simplex. Qual seria a melhoria do valor da função 
objectivo se fosse possível dispor de mais uma unidade de capacidade disponível no CP2? (E 
nos outros CPs?) 
d) A CV pretende introduzir um novo produto (P3) na sua linha de produção. Estudos 
preliminares indicam que uma unidade de P3 usará 2, 3 e 1 unidades de capacidade produtiva 
dos centros CP1, CP2 e CP3, respectivamente. O lucro unitário de P3 foi estimado em 4 u.m. 
Será vantajoso produzir P3? Em caso negativo, qual o valor mínimo do lucro unitário de P3 para 
que este produto passe a ser fabricado? 
e) Remodelações em curso no CP3 vão aumentar a respectiva capacidade disponível de 1 
unidade por mês. Face a esta alteração, durante quanto tempo se manterá óptimo o actual 
esquema de produção? 
Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios estudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mz Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Zicai Zicai Zicai Zicai FazendaFazendaFazendaFazenda 
Investigação Operacional - Programação Linear. Método Simplex. Análise de sensibilidade. Transportes e stocks 5 
f) A CV decidiu estender as remodelações aos 3 CP, que aumentarão a sua capacidade disponível 
ao ritmo de 1, 2 e 1 unidade por mês, respectivamente. Face a estas alterações conjuntas, durante 
quanto tempo se manterá óptimo o actual esquema de produção? 
g) Alterações de mercado indicam que os lucro unitários de P1 e P2 variarão a uma taxa mensal 
de +1 e -1 u.m. Face a estas alterações conjuntas, durante quanto tempo se manterá óptimo o 
actual esquema de produção? 
h) A entrada em vigor de nova legislação que impõe um maior controlo de qualidade obrigou à 
criação de um novo centro de produção (CP4) dedicado a esta tarefa. Cada unidade de P1 e P2 
usará 2 e 3 unidades de capacidade produtiva em CP4, respectivamente. A capacidade disponível 
em CP4 é 24. Quais as alterações que a introdução de CP4 obriga no esquema de produção 
óptimo? E se a capacidade disponível no CP4 for 18?. 
 
10- Uma empresa de "software" comercializa três programas: um compilador de Pascal, uma 
folha de cálculo e um sistema de gestão de base de dados, que vende ao público por 40, 30 e 60 
mil meticais, respectivamente. Para efectuar as demonstrações aos clientes a empresa tem 
disponíveis dois computadores (modelos A e B). Devido a outros compromissos da empresa os 
computadores só podem ser usados em demonstrações durante períodos semanais que não 
excedam as 30 horas no caso do modelo A e 40 horas no que se refere ao modelo B. 
Os tempos de demonstração de cada programa em cada um dos computadores, são os seguintes: 
 mod. A mod. B 
Compilador de Pascal 3 h 2 h 
Folha de Cálculo 1 h 2 h 
Sistema de Gestão de Base de Dados 3 h 3 h 
 
Supondo que os clientes só compram os programas após assistirem e ficarem satisfeitos com as 
demonstrações, formule matematicamente o problema de maximização da receita semanal da 
empresa. Construa o problema dual e resolva-o graficamente. 
 
11- Seja o problema primal 
 min z(x) = 5 x1 - 6 x2 + 7 x3 + x4 
 s. a x1 + 2 x2 - x3 - x4 = -7 
 6 x1 - 3 x2 + x3 + 7x4 ≥ 14 
 -2.8 x1 - 17 x2 + 4 x3 + 2 x4 ≤ -3 
 x1 ≥0 , x2 ≥0 , x3 e x4 não restritas em sinal. 
Formule o problema dual. Verifique que o dual do dual é o primal. 
 
12- Resolva pelo método simplex o problema 
 min z(x) = 3 x1 + 2 x2 - 3 x3 - 6 x4 + 10 x5 - 5 x6 
 s. a x1 + 2 x2 + x4 - 6 x6 = 11 
 x2 + x3 + 3 x4 - 2 x5 - x6 = 6 
 x1 + 2 x2 + x3 + 3 x4 - x5 - 5 x6 = 13 
 xi ≥0 , i=1,...,6. 
a) Considere uma nova variável x7 com A.7 = (1,2,-3)T e c7=-7. Qual o nível a que x7 deve ser 
produzida? 
Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios estudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mz Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Zicai Zicai Zicai Zicai FazendaFazendaFazendaFazenda 
Investigação Operacional - Programação Linear. Método Simplex. Análise de sensibilidade. Transportes e stocks 6 
b) Considere uma nova variável x7 com A.7 = (3,-1,1)T e c7=4. Qual o nível a que x7 deve ser 
produzida? 
c) Considere uma nova restrição x1 - x2 + 3 x3 ≤ -7. Obtenha a nova solução óptima. 
d) Qual a gama de variação de b1 para a qual a base óptima se mantem? 
e) Qual a gama de variação de c1 para a qual a base óptima se mantem? 
 
13- Um companhia controla um sistema constituído por duas albufeiras com uma central 
hidroeléctrica localizada em cada uma delas. Quando a albufeira atinge a capacidade máxima, a 
água que entra perde-se (não produzindo electricidade) por um canal de desvio. Este canal pode 
também ser usado para libertar água para protecção de inundações. O horizonte de planeamento 
é dividido em dois períodos. Em média, 1 “Kilo-acre-foot” (KAF) de água é convertido em 400 
MWh de electricidade pela central A, e em 200 MWh pela central B. As capacidades das centrais 
A e B são 60000 e 35000 MWh por período. Em cada período, um máximo de 50000 MWh de 
electricidade pode ser vendido a 20,00 Mtn/MWh. O excesso acima de 50000 MWh apenas 
consegue ser vendido a 14,00Mtn/MWh. A tabela seguinte fornece os dados relativos aos fluxos 
e níveis de água nas albufeiras: 
 
 Albufeira A Albufeira B 
Capacidade 2000 1500 
Fluxo previsto 
 Período 1 200 40 
 Período 2 130 15 
Nível mínimo permitido 1200 800 
Nível no início do período 1 1900 850 
 
Reservatório
A A BB
Reservatório Central Central
 
Construa um modelo de programação linear para determinar a política de operação óptima de 
modo a maximizar a receita total da venda de electricidade. 
 
14- Uma empresa possui duas categorias de inspectores (I1 e I2), que devem ser afectos a uma 
inspecção de controlo de qualidadeem que se requere que sejam inspeccionadas pelo menos 
1800 peças por dia de trabalho (8 horas). 
Os inspectores I1 ganham 4,00Mtn/hora e podem verificar 25 peças por hora com uma precisão 
de 98%. Os inspectores I2 ganham 3,00Mtn/hora e podem verificar 15 peças por hora com uma 
precisão de 95%. Cada vez que um inspector comete um erro o custo para a empresa é de 
2,00Mtn. A companhia tem disponíveis para este trabalho 8 I1 e 10 I2. Qual a afectação óptima 
de inspectores que minimiza o custo total da inspecção? 
 
Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios estudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mz Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Zicai Zicai Zicai Zicai FazendaFazendaFazendaFazenda 
Investigação Operacional - Programação Linear. Método Simplex. Análise de sensibilidade. Transportes e stocks 7 
15- Suponha que lhe saíu um prémio de 6000 contos no Totoloto e que pretende investir este 
dinheiro na totalidade ou apenas uma parte. Sabendo disto dois amigos seus (o Alberto e o 
Belmiro) ofereceram-lhe sociedade em dois negócios diferentes que pretendem realizar no 
próximo verão. Em ambos os casos a sua participação envolve quer disponibilizar dinheiro, quer 
colaborar com trabalho. Tornar-se sócio a parte inteira do Alberto implica um investimento de 
5000 contos e 400 h de trabalho, e o lucro esperado é de 4500 contos (sem levar em conta o 
valor do seu tempo). Os valores correspondentes relativos à participação (a parte inteira) no 
negócio do Belmiro são 4000 contos e 500h, e 4500 contos para o lucro esperado. Contudo, 
ambos os amigos são flexíveis e permitem-lhe participar com qualquer fracção de sócio a parte 
inteira; obviamente que a sua parte nos lucros será também proporcional a esta fracção. Dado 
que pretende também algum tempo livre no verão, não quer dedicar mais de 600h de trabalho. 
Cabe-lhe então decidir qual combinação de participação num ou em ambos os projectos dos seus 
amigos de modo a maximizar o seu lucro. 
a) Construa um modelo matemático de programação linear para o problema, explicitando as 
variáveis de decisão, restrições e função objectivo. 
b) Resolva o problema graficamente e utilizando o método simplex. 
c) Qual a gama dentro da qual pode variar o número de horas de trabalho de modo a que a 
solução actual se mantenha óptima. Qual a variação correspondente do lucro? 
 
16- Uma empresa possui 3 fábricas onde existe capacidade de produção em excesso. Todas as 
fábricas estão aptas a produzir um novo produto e a direcção decidiu usar desta forma alguma da 
capacidade disponível. Este novo produto pode ser fabricado em 3 tamanhos (grande [G], médio 
[M] e pequeno [P]), que dão um lucro unitário de 42, 36 e 30 contos, respectivamente. As 
fábricas 1, 2 e 3 têm capacidade em excesso para produzir diariamente 750, 900 e 450 unidades 
deste produto, respectivamente, independentemente dos tamanhos ou combinação de tamanhos. 
O espaço de armazenamento disponível impõe uma limitação na produção do novo produto. As 
fábricas 1, 2 e 3 têm 13000, 12000 e 5000 m2 de espaço de armazenamento disponível, 
respectivamente, para um dia de produção. Cada unidade dos produtos G, M e P produzida por 
dia necessita de 20, 15 e 12 m2, respectivamente. As previsões de vendas indicam que podem ser 
vendidas diariamente 900, 1200 e 750 unidades dos produtos G, M e P, respectivamente. Para 
manter uma força de trabalho uniforme nas fábricas e dispor de alguma flexibilidade, a direcção 
decidiu que as fábricas devem usar a mesma percentagem da sua capacidade em excesso para 
produzir o novo produto. A direcção pretende saber quanto de cada tamanho deve ser produzido 
em cada fábrica, de modo a maximizar o lucro total. Construa um modelo matemático de 
programação linear para o problema, explicitando o significado das variáveis de decisão, 
restrições e função objectivo. 
 
17- Uma família possui 500 mil metros quadrados de terra e tem 5 mil contos em fundos 
disponíveis para investimento. Os membros da família podem produzir um total de 3500 
pessoas-hora de trabalho durante os meses de inverno e 4000 pessoas-hora durante o verão. Se 
parte destas pessoas-hora não for necessária, os membros mais novos da família podem usá-la 
para trabalhar nas quintas vizinhas por 800,00Mtn/hora no inverno e 1000,00Mtn/hora no verão. 
As receitas em dinheiro podem ser obtidas através de 3 colheitas e da criação de 2 tipos de 
Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios estudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mz Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Zicai Zicai Zicai Zicai FazendaFazendaFazendaFazenda 
Investigação Operacional - Programação Linear. Método Simplex. Análise de sensibilidade. Transportes e stocks 8 
animais: vacas leiteiras e galinhas. Para as colheitas não são necessários investimentos. Cada 
vaca requer um investimento de 200,00Mtn e cada galinha custa 1,5,00Mtn. Cada vaca necessita 
de 6 mil metros quadrados de terra, 100 pessoas-hora de trabalho durante o inverno e 50 pessoas-
hora durante o verão. Cada galinha necessita de0.6 pessoas-hora de trabalho durante o inverno 
e0.3 pessoas-hora durante o verão, e não é necessário o uso de terra. Cada vaca produz uma 
receita anual líquida para a família de 165,00Mtn, enquanto cada galinha gera 85,00Mtn. O 
galinheiro pode albergar um máximo de 3000 galinhas, enquanto o tamanho do estábulo limita o 
número de vacas a 32. Os valores estimados de pessoas-hora e de receita por metro quadrado de 
terra plantado em cada uma das 3 colheitas são: 
 Soja Milho Aveia 
Pessoas-hora no inverno 20 35 10 
Pessoas-hora no verão 50 75 40 
Receita anual líquida (meticais) 1000 1500 750 
A família pretende determinar qual a superfície de terra que deve ser plantada em cada uma das 
colheitas, e quantas vacas e galinhas devem ser adquiridas para maximizar a receita líquida 
anual. Construa um modelo matemático de programação linear para o problema, explicitando o 
significado das variáveis de decisão, restrições e função objectivo. 
 
18- A Companhia Pintados de Fresco produz tinta para interiores e exteriores. A tinta é fabricada 
por meio da transformação de 2 tipos de matéria prima: A e B. A companhia tem acessíveis 
diariamente um máximo de 6 toneladas de A e 8 toneladas de B. Para produzir 1 ton. de tinta de 
exteriores são necessárias 1 ton. de A e 2 ton. de B, enquanto para produzir 1 ton. de tinta de 
interiores são necessárias 2 ton. de A e 1 ton. de B, em cada dia. Um estudo de mercado concluíu 
que a procura diária de tinta de interiores não pode exceder a da tinta de exteriores em mais de 1 
ton. Este estudo também mostrou que a procura diária de tinta de interiores está limitada a 2 ton. 
O preço de venda por tonelada é 3 u.m. para a tinta de exteriores e 2 u.m. para a tinta de 
interiores. Pretende-se determinar o esquema de produção a adoptar para maximizar a receita 
diária. 
a) Construa um modelo matemático de programação linear para o problema, explicitando as 
variáveis de decisão, restrições e função objectivo. 
b) Resolva o problema graficamente e utilizando o método simplex. 
c) Qual a gama dentro da qual pode variar a disponibilidade de matéria prima do tipo A de modo 
a que a solução actual se mantenha óptima. Qual a variação correspondente da receita diária? 
d) Estudos de mercado indicam que o preço da tinta de exteriores diminuirá a um ritmo de0.2 
u.m. por mês, enquanto o preço da tinta de interiores aumentará a um ritmo de0.4 u.m. por mês.Com esta tendência, quantos meses se manterá óptima a solução actual? 
 
19- Considere o seguinte problema de programação linear 
 max z = 3 x1 + 4 x2 + x4 
 s. a 3 x1 + 2 x2 + 4 x3 + 2 x4 ≤ 30 (recurso 1; slack s1) 
 2 x1 + 4 x2 + x3 + 2 x4 ≤ 30 (recurso 2; slack s2) 
 2 x1 + 2 x2 + 2 x3 + 4 x4 ≤ 40 (recurso 3, slack s3) 
 x1 ≥0 , x2 ≥0 , x3 ≥0 , x4 ≥0 
Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios estudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mz Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Zicai Zicai Zicai Zicai FazendaFazendaFazendaFazenda 
Investigação Operacional - Programação Linear. Método Simplex. Análise de sensibilidade. Transportes e stocks 9 
a) Em determinada iteração do algoritmo simplex foi obtido o seg. quadro, onde alguns valores 
não foram ainda calculados: 
xB x1 x2 x3 X4 s1 s2 s3 
x1 1 α1 β1 γ1 1/2 -1/4 0 δ1 
x2 0 α2 β2 γ2 -1/4 3/8 0 δ2 
s3 0 α3 β3 γ3 -1/2 -1/4 1 δ3 
zj-cj 0 α4 β4 γ4 1/2 ¾
 
0 δ3 
Determine os valores ainda não conhecidos e obtenha a solução óptima. 
b) Se os recursos variarem a uma taxa dada por d=(1,2,2) de acordo com o mesmo parâmetro de 
variação (i.e., b(t)=b+t d), qual a gama admissível para o parâmetro t em que a base óptima não 
se altera? Qual a variação correspondente do valor da função objectivo z(t)? 
c) Pretende-se avaliar a viabilidade da introdução de um novo produto, representado pela 
variável de decisão x5. Os coeficientes de x5 nas restrições são (a15,a25,a35) e o coeficiente de 
x5 na função objectivo é c5. Qual a gama admissível para c5, em função de (a15,a25,a35), em que 
é rentável iniciar a produção do novo produto? 
 
20- Uma administração municipal está a estudar a possibilidade de introduzir um sistema de 
transportes colectivos para reduzir a circulação de automóveis na cidade. O objectivo do estudo é 
determinar o número mínimo de autocarros, de modo a satisfazer as necessidades de transporte 
da população. Após recolher a informação necessária, o engº responsável pelo estudo verificou 
que o número mínimo de autocarros necessário para satisfazer a procura variava ao longo do dia, 
mas o número requerido de autocarros podia ser considerado constante ao longo de períodos 
sucessivos de 4 horas cada (de acordo com a fig.). De modo a efectuar os trabalhos de 
manutenção necessários, cada autocarro pode funcionar por dia apenas 2 períodos sucessivos de 
4 horas. 
4 8 12 16 20 240
Hora do dia
4
8
10
7
12
4
4
8
12
N
º
 
de
 
au
to
ca
rr
o
s
10
 
Construa um modelo de PL no qual a administração municipal se possa basear para determinar o 
número de autocarros em serviço em cada período, que satisfaça a procura, de modo a minimizar 
o número total de autocarros em serviço em cada dia. 
 
 
 
 
 
Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios estudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mz Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Zicai Zicai Zicai Zicai FazendaFazendaFazendaFazenda 
Investigação Operacional - Programação Linear. Método Simplex. Análise de sensibilidade. Transportes e stocks 10 
21- Considere o seguinte problema de programação linear 
 
 min z = 2 x1 + 2 x2 + 4 x3 
 s. a 2 x1 + 2 x2 + x3 ≤ 10 (slack x6) 
 -2 x1 + x2 + 2 x3 ≥ 4 (surplus x4, artificial x7) 
 x1 + 2 x2 - 2 x3 ≥ 4 (surplus x5, artificial x8) 
 xj ≥0 , j=1...,8 
 
Em determinada iteração do algoritmo simplex foi obtido o seg. quadro (onde foram omitidas as 
colunas das variáveis artificiais), no qual alguns valores não estão ainda calculados: 
xB x1 x2 X3 x4 x5 x6 
x6 α1 β1 γ1 1 1/2 δ1 η1 
x3 α2 β2 γ2 -1/3 1/6 δ2 η2 
x2 α3 β3 γ3 -1/3 -1/3 δ3 η3 
zj-cj µ1 µ2 µ3 µ4 µ5 µ6 φ 
 
a) Determine os valores ainda não conhecidos e obtenha a solução óptima. 
b) Esta solução tem óptimos alternativos? Em caso positivo indique as variáveis que fariam parte 
de uma base óptima alternativa. 
c) Qual a gama admissível para a variação de b2 em que a base óptima não se altera? 
d) Qual a gama admissível para a variação de c3 em que a base óptima não se altera? 
e) Se for introduzida uma nova variável x9, cujos coeficientes na matriz A são A.9=(2,1,3)T, qual 
a gama de valores do respectivo coeficiente na função objectivo (c9) para a qual não é vantajoso 
haver alteração da base óptima actual? 
 
22- Pretende-se planear a produção, armazenamento e venda de um produto cuja procura e preço 
de venda variam ao longo do ano. A tabela seg. dá os custos de produção (Mtn/ton), a 
capacidade de produção (ton.), a procura (ton.) e o preço de venda (Mtn/ton): 
 
Período custos de 
produção 
(Mtn/ton) 
capacidade de 
produção (ton.) 
procura (ton.) preço de venda 
(Mtn/ton) 
1 20 1500 1100 180 
2 25 2000 1500 180 
3 30 2200 1800 250 
4 40 3000 1600 270 
5 50 2700 2300 300 
6 60 2500 2500 320 
 
O custo de armazenamento de um período para o seguinte é 2,00Mtn/ton. 
As operações têm início no período 1 com um stock inicial de 500ton. do produto em armazém. 
A empresa pretende ficar com a mesma quantidade em armazém no fim do período 6. 
Construa um modelo de programação linear no qual a empresa se possa basear para planear a 
produção, as vendas e o stock ao longo dos 6 períodos, de modo a maximizar a receita total. 
Explicite o significado das variáveis de decisão, restrições e função objectivo. 
 
23 - Considere o seguinte problema de programação linear 
 
Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios estudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mz Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Zicai Zicai Zicai Zicai FazendaFazendaFazendaFazenda 
Investigação Operacional - Programação Linear. Método Simplex. Análise de sensibilidade. Transportes e stocks 11 
 min z = 2 x1 + 2 x2 + 4 x3 + x4 
 s. a 2 x1 + x2 + 2 x3 ≤ 10 (slack x7) 
 4 x1 + x3 + 2 x4 ≥ 12 (surplus x5, artificial x8) 
 x1 + 4 x2 + 4 x4 ≥ 10 (surplus x6, artificial x9) 
 xj ≥0 , j=1...,9 
 
a) Em determinada iteração do algoritmo simplex foi obtido o seg. quadro (onde não constam as 
colunas correspondentes às variáveis artificiais), onde apenas alguns valores estão calculados: 
xB x1 x2 x3 x4 x5 x6 x7 
x7 β1 γ1 ε1 δ1 4/7 -2/7 µ1 λ1 
x1 β2 γ2 ε2 δ2 -2/7 1/7 µ2 λ2 
x4 β3 γ3 ε3 δ3 1/14 -2/7 µ3 λ3 
zj-cj α1 α2 α3 α4 α5 α6 α7 θ 
Determine os valores ainda não conhecidos e obtenha a solução óptima. 
b) Qual a gama admissível para a variação de b3 em que a base óptima não se altera? Qual a 
variação do valor óptimo da função objectivo em função de b3 [z(b3)]? 
c) Qual a gama admissível para a variação de c2 em que a base óptima não se altera? Qual a 
variação do valor óptimo da função objectivo em função de c2 [z(c2)]? 
d) Há soluções óptimas alternativas? Em caso positivo, quais as variáveis da base óptima 
alternativa? 
 
24- Uma empresa prevê necessitar do seguinte número de computadores pessoais durante os 
primeiros 6 meses do póximo ano: Janeiro - 9, Fevereiro - 5, Março - 7, Abril - 9, Maio- 10, 
Junho - 5. Os computadores podem ser alugados por períodos de 1, 2 ou 3 meses aos custos 
unitários: 1 mês - 20 u.m., 2 meses - 35 u.m., 3 meses - 45 u.m. 
Se uma máquinafor alugada por um período de tempo para além de Junho o custo de aluguer a 
incluir no modelo deve ser apenas relativo ao tempo usado (por exemplo, se um computador for 
alugado por 3 meses no início de Maio, o custo de aluguer a considerar é 30 u.m). 
Construa um modelo de programação linear tendo em vista minimizar o custo de aluguer dos 
computadores necessários. Explicite o significado das variáveis de decisão, restrições e função 
objectivo. 
 
 
 
 
 
 
 
 
 
 
 
 
Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios estudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mz Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Zicai Zicai Zicai Zicai FazendaFazendaFazendaFazenda 
Investigação Operacional - Programação Linear. Método Simplex. Análise de sensibilidade. Transportes e stocks 12 
Análise de SensibilidadeAnálise de SensibilidadeAnálise de SensibilidadeAnálise de Sensibilidade 
1 – A direcção de marketing de uma empresa de mobiliário metálico de escritório sugere o 
lançamento de um novo modelo de secretária e de estante em substituição dos modelos actuais. 
Aquela direcção não vê dificuldade de colocação no mercado para as estantes, enquanto que 
aconselha que a produção mensal de secretárias não ultrapasse as 160 unidades. Após estudos 
levados a cabo pela direcção de produção, concluiu-se que: 
- A disponibilidade mensal do departamento de estampagem é de 720 horas-máquina; 
- A disponibilidade mensal do departamento de montagem e acabamento é de 880 horas-homem; 
- Cada secretária necessita de 2 H-M de estampagem 4 H-H de montagem e acabamento; 
- Cada estante necessita de 4 H-M de estampagem e 4 H-H de montagem e acabamento 
Por outro lado as margens brutas unitárias estimadas são de 6000,00Mtn para as secretárias e 
3000,00Mtn para as estantes. A empresa pretende determinar o plano de produção mensal para 
estes novos modelos que maximiza a margem bruta. 
a) Formalize o problema como um modelo de programação linear. 
b) Determine a solução óptima do problema usando o algoritmo simplex. 
c) Suponha que as margens brutas unitárias foram actualizadas e estimadas em 4 e 5 mil 
Meticais para as secretárias e estantes, respectivamente. Que alterações se poderão sentir face 
à solução anteriormente obtida? 
d) Suponha que o nº de horas –homem disponíveis pelo departamento de montagem e 
acabamento sofreu um acréscimo de 400 h. Que influencias terá na solução óptima? 
e) Suponha que diminuiu em0,8 o nº de H-H do departamento de montagem e acabamento 
necessários à produção de uma secretária. Actualize a solução. 
f) Suponha que diminuiu em0,8 o nº de H-H do departamento de estampagem necessários à 
produção de uma secretária. Actualize a solução. 
g) Em resposta à solicitação de alguns clientes a empresa decidiu analisar a implicação da 
produção de um novo produto – mesas de trabalho. 
O estudo das condições de produção permitiu concluir que a produção unitária deste novo 
produto requer 3 H-H de dep.de estampagem e 2 H-H do dep.de Mont. e Acab., não estando 
prevista qualquer limitação de mercado. A margem bruta unitária estimada é de 5000,00Mtn. 
 
2 – Considere o problema seguinte: 
Max F= 2X1-X2+X3 
s.a. 3X1-2X2+2 X3≤15 
 -X1+X2+ X3≤3 
X1-X2+X3≤4 X1, X2, X3≥0 
Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios estudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mz Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Zicai Zicai Zicai Zicai FazendaFazendaFazendaFazenda 
Investigação Operacional - Programação Linear. Método Simplex. Análise de sensibilidade. Transportes e stocks 13 
Considerando X4, X5 e X6 como variáveis de folga e utilizando o algoritmo Simplex obtêm-se as 
equações seguintes correspondentes à solução óptima: 
F= -2X3-X4-X5+18 
. X2+5X3+ X4+3X5=24 
 2X3+X5+ X6=7 
X1+4X3+X4+2X5=21 
Faça a análise de sensibilidade para as alterações indicadas a seguir verificando se as novas 
soluções são possíveis e/ou óptimas. Não é necessário calcular as novas soluções óptimas. 
a) Os termos independentes passam a ser 










=
2
4
20
b [Resposta:Cont. a ser solução optima e única 
X1=28, X2=32, X6=6] 
b) O coeficiente c3 passa a ter o valor 2. [Resposta: r´=[-1 –1 –1], a solução. É optima e única; 
a admissibilidade não é posta em causa] 
c) O coeficiente c1 passa a ser igual a 3. [Resposta: r´=[-6 –2 –3], a solução. É optima e única; 
a admissibilidade não é posta em causa] 
d) O valor de c3 passa a ser 4 e os coeficientes de X3 nas restrições passam a ser 










1
2
3
 
[Resposta: Mantêm-se optima, a admissível não é posta em causa] 
e) Os coeficientes de c1 e c2 passam a ser , respectivamente, 1 e –2, e os coeficientes de X1 e X2 
nas restrições passam a ser, respectivamente 










−
3
2
1
 e 









−
2
3
1
 [Resposta: r=[4 1 1 ] a solução 
não é optima e não admissível 
f) A função objectivo passa a ser F=5X1+X2+3X [Resposta: a solução continua a ser optima 
r´=[-22 –6 –13], a admissibilidade não é posta em causa] 
g) É introduzida uma nova restrição 2X1+X2+2X3≤60 [Resposta: Solução optima, mas não 
admissível] 
 
3 - A empresa N Lda produz três artigos. Para desenvolvimento da sua actividade produtiva a 
empresa dispõe de 8 operários, cada um podendo trabalhar 40 horas/semana, e de 400Kg de 
matéria prima por semana. Cada unidade de produto 1 necessita de 5 H-H e 6 Kg de matéria 
prima, sendo 8H-H e 8 Kg as necessidades para o produto 2 e de 6 H-H e 7 Kg para o produto 3. 
Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios estudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mz Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Zicai Zicai Zicai Zicai FazendaFazendaFazendaFazenda 
Investigação Operacional - Programação Linear. Método Simplex. Análise de sensibilidade. Transportes e stocks 14 
As previsões de vendas semanais para cada um dos produtos são de 30 25 e 40 Kg, 
respectivamente. Com a venda destes produtos a empresa consegue a margem unitária de 5, 10 e 
8 respectivamente. Para planeamento da sua produção a empresa serviu-se do modelo: 
Max Z= 5x1+10x2+8x3 
s.a 5x1+8x2+6x3≤320 
 6x1+8x2+7x3≤400 
 x1≤30 
 x2≤25 
 x3≤40 
 x1, x2, x3 ≥0 
 
a) Até quanto pode diminuir a margem bruta unitária do produto 2 sem que ele deixe de ser 
produzido? 
b) Analise as implicações de contratação de mais um operário. 
 cuja resolução resultou o quadro óptimo: 
x1 x2 x3 F1 F2 F3 F4 F5 Ti 
0 0 1 0 0 0 0 1 40 
1 0 0 -1 1 0 0 -1 40 
1 0 0 0 0 1 0 0 30 
5/8 1 0 1/8 0 0 0 -3/4 10 
-5/8 0 0 -1/8 0 0 1 ¾ 15 
-5/4 0 0 -5/4 0 0 0 -1/2 420 
Onde Fi – é variável de folga e Ti – Termo independente. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios estudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mz Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues ZicaiZicai Zicai Zicai FazendaFazendaFazendaFazenda 
Investigação Operacional - Programação Linear. Método Simplex. Análise de sensibilidade. Transportes e stocks 15 
Transportes, transexpedição e afectação Transportes, transexpedição e afectação Transportes, transexpedição e afectação Transportes, transexpedição e afectação 
1- Uma companhia de aço possui 2 minas e 3 fábricas transformadoras. Em cada mina (1 e 2) 
encontram-se disponíveis 103 e 197 toneladas de minério. A companhia transporta por mar o 
minério até às fábricas. O custo de transporte do minério para as fábricas é dado na tabela (em 
milhares de meticais por tonelada). 
 
 Fábrica 1 Fábrica 2 Fábrica 3 
Mina 1 9 16 28 
Mina 2 14 29 19 
As fábricas (1, 2 e 3) requerem a utilização de 71, 133 e 96 toneladas de minério. 
(a) Construa o modelo matemático que represente o problema de transportar minério das minas 
para as fábricas transformadoras, de modo a minimizar o custo total de transporte. 
(b) Formule o problema dual do precedente. 
(c) Obtenha uma solução básica admissível inicial utilizando o método 
 (i) do “canto noroeste”; 
 (ii) do “mínimo da matriz de custos”; 
 (iii) das “penalidades”. 
(d) Partindo de uma das soluções básicas admissíveis iniciais obtidas em (c), determine o plano 
óptimo de transporte. 
 
2- Uma companhia tem 3 fábricas a produzir um dado produto que deve ser depois transportado 
para 4 centros de distribuição. As fábricas (1, 2 e 3) produzem 12, 17 e 11 carregamentos por 
mês. Cada centro de distribuição necessita de receber 10 carregamentos por mês. As distâncias 
de cada fábrica para cada centro de distribuição (em Km) são dados na tabela. O custo do frete 
de cada carregamento é de 5000,00Mtn acrescido de 50,00Mtn por Km. 
 
 Centro 1 Centro 2 Centro 3 Centro 4 
Fábrica 1 80 130 40 70 
Fábrica 2 110 140 60 100 
Fábrica 3 60 120 80 90 
Formule o problema de modo a minimizar o custo total de transporte, construindo uma 
apropriada tabela de custos. Resolva o problema, determinando uma solução básica admissível 
inicial através do método do “canto noroeste”. 
 
3- Pretende-se transportar um produto de 2 armazéns (A1 e A2) para 3 destinos (D1, D2 e D3). 
Os armazéns A1 e A2 dispõem de 4 e 6 unidades do produto, respectivamente. Em D1, D2 e D3 
são requeridas 2, 3 e 5 unidades do produto, respectivamente. Os custos unitários de transporte 
são dados na tabela: 
 
 D 1 D 2 D 3 
A 1 4 4 5 
A 2 5 3 8 
Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios estudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mz Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Zicai Zicai Zicai Zicai FazendaFazendaFazendaFazenda 
Investigação Operacional - Programação Linear. Método Simplex. Análise de sensibilidade. Transportes e stocks 16 
 
(a) Formule o problema em termos de programação linear. 
(b) Formule o problema dual do precedente. 
(c) Resolva o problema, calculando a solução básica admissível inicial através do método 
 i) do “canto noroeste”; 
 ii) do “mínimo da matriz de custos”; 
 iii) das “penalidades”. 
 
4- Uma empresa tem 3 fábricas a produzir um dado produto que deve ser depois transportado 
para 3 centros de distribuição. As fábricas (1, 2 e 3) produzem 50, 60 e 30 unidades por mês, 
respectivamente. Os centros de distribuição (1, 2 e 3) necessitam de receber 10, 70 e 20 unidades 
por mês, respectivamente. Os custos unitários de transporte são dados no quadro: 
 
 Centro 1 Centro 2 Centro 3 
Fábrica 1 6 1 3 
Fábrica 2 3 5 2 
Fábrica 3 6 2 6 
Determinar o plano óptimo de transporte que a empresa deve adoptar. 
 
5- Uma empresa pretende determinar o plano óptimo de transporte da matéria-prima armazenada 
em 2 centros de distribuição que é transformada em 3 fábricas. Nos centros de distribuição 
existem 20 e 18 toneladas de matéria-prima. Nas fábricas são necessárias 12, 10 e 16 toneladas 
de matéria-prima. Os custos unitários de transporte são dados no quadro. O trajecto entre o 
centro 2 e a fábrica 2 não pode ser utilizado. Determinar o plano que a empresa deve adoptar. 
 
 Fábrica 1 Fábrica 2 Fábrica 3 
Centro 1 5 2 3 
Centro 2 4 xxx 2 
 
6- Duas fábricas abastecem 2 armazéns de venda a retalho. Na fábrica 1 existem 10 unidades do 
produto e na fábrica 2 existem 20 unidades. No armazem 1 são requeridas 14 unidades do 
produto e no armazem 2 são requeridas 16 unidades. O quadro seguinte contém a informação 
relativa a custos unitários de transporte. 
 Armazem 1 Armazem 2 
Fábrica 1 3 4 
Fábrica 2 6 5 
Admitindo que é possível utilizar qualquer ponto como entreposto, e que o custo unitário de 
transexpedição entre as fábricas é 1 e entre os armazéns é 2, determine o plano óptimo de 
distribuição. 
 
Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios estudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mz Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Zicai Zicai Zicai Zicai FazendaFazendaFazendaFazenda 
Investigação Operacional - Programação Linear. Método Simplex. Análise de sensibilidade. Transportes e stocks 17 
7- Numa secção de uma fábrica existem 4 máquinas. Um dado processo de produção consiste em 
4 tarefas que devem ser levadas a cabo nessas máquinas. Cada máquina só pode cumprir uma 
tarefa. Os custos de realizar a tarefa j (j=1,...,4) na máquina i (i=1,...,4) são dados na tabela. 
 
 J1 J2 J3 J4 
M1 10 9 7 8 
M2 5 8 7 7 
M3 5 4 6 5 
M4 2 3 4 5 
Como afectar as tarefas às máquinas de modo a minimizar o custo total? 
 
8- O treinador de uma equipa de natação necessita de seleccionar nadadores para a equipa de 
estafeta 4x100 metros estilos. Dado que os nadadores são muito rápidos em mais do que um 
estilo, o treinador sente alguma dificuldade em afectá-los a cada um dos 4 estilos. Os 5 melhores 
nadadores e os melhores tempos (em segundos) que obtiveram em cada um dos estilos (100 
metros) são dados na tabela: 
 Alberto Belmiro Carlos David Ernesto 
Costas 37.7 32.9 33.8 37.0 35.4 
Bruços 43.4 33.1 42.2 34.7 41.8 
Mariposa 33.3 28.5 38.9 30.4 33.6 
Livre 29.2 26.4 29.6 28.5 31.1 
O treinador pretende determinar como afectar um nadador a cada um dos estilos, de modo a 
minimizar a soma dos correspondentes melhores tempos. 
 
9- Uma empresa pretende determinar o plano óptimo de produção de um dado bem para as 
próximas 4 semanas. O custo de produção do bem é 10,00Mtn para as 2 primeiras semanas e 
15,00Mtn para as 2 últimas semanas. A procura semanal a satisfazer é 300, 700, 900 e 800 
unidades do bem para cada uma das 4 semanas (respectivamente). A empresa pode produzir 
apenas um máximo de 700 unidades do bem por semana, mas pode empregar mão-de-obra 
extraordinária durante a 2ª e 3ª semanas. Isto permite aumentar a produção semanal de 200 
unidades, mas os custos de produção aumentam 5,00Mtn por unidade do bem. A produção em 
excesso pode ser armazenada a um custo unitário de 3,00Mtn por semana. 
Construa um modelo de transportes para planear a produção de modo a minimizar o custo total. 
 
 
 
 
 
 
 
Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios estudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mz Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Zicai Zicai Zicai ZicaiFazendaFazendaFazendaFazenda 
Investigação Operacional - Programação Linear. Método Simplex. Análise de sensibilidade. Transportes e stocks 18 
Problemas de opProblemas de opProblemas de opProblemas de optimização emtimização emtimização emtimização em redesredesredesredes 
1- Uma companhia sediada na Beira pretende estabelecer o plano mais económico para as 
deslocações dos seus vendedores às cidades onde existem representantes dos seus produtos. A 
fig. mostra um mapa simplificado onde os nós representam as cidades e os arcos representam as 
ligações possíveis. 
 
1 
2 
3 
4 
5 
6 
7 
8 
Quelimane 
Nacala 
Pebane 
Nampula
Chimoio Dondo 
Beira 
Sena 
130 
250 
150 
200 
60 
120 
70 
100 
60 
200 
120 
 
A cada arco está associado um valor representando o custo que a empresa atribui a esse trajecto, 
em função da distância, das condições da estrada e da densidade do tráfego. 
Determine os percursos mais económicos que os vendedores da empresa deverão efectuar entre a 
sede e todas as cidades. 
 
2- Uma empresa pretende determinar a política óptima de substituição de um dado equipamento 
num período de planeamento de 5 anos. Os custos envolvidos são 
 Kj = custo de aquisição do equipamento no ano j 
 Sj = valor residual do equipamento após j anos de uso 
 cj = custos de operação e manutenção durante o ano j 
Formule este problema como um de caminho mais curto numa rede dirigida. 
 
3- Usando o algoritmo de Floyd determine os caminhos mais curtos entre todos os pares de 
nodos na rede da fig. 
2
5
5
3
4
1 2
6
1
2
2
6
6
 
 
4- Em todas as cidades da região em análise no prob. 1 estão sediadas empresas de diferentes 
ramos de actividade que têm necessidade de definir os trajectos mais económicos para as 
Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios estudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mz Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Zicai Zicai Zicai Zicai FazendaFazendaFazendaFazenda 
Investigação Operacional - Programação Linear. Método Simplex. Análise de sensibilidade. Transportes e stocks 19 
deslocações dos seus vendedores entre a sede e as restantes cidades. Adoptando o mesmo mapa 
simplificado do prob. 1, determine os percursos mais económicos para cada empresa. 
 
5- Uma empresa de telecomunicações pretende servir a mesma região do problema 1 com uma 
nova rede telefónica. Na fig. os nodos representam as localidades a servir e os arcos representam 
as ligações onde é tecnicamente possível o lançamento de cabos. A cada arco está associada a 
distância entre as localidades que liga. Quais as ligações a concretizar se a empresa quiser 
minimizar o comprimento de cabo a instalar? 
 
6- A rede da fig. representa uma parte do sistema rodoviário de uma cidade. O custo associado a 
cada arco representa o tempo médio (em minutos) que o tráfego demora nesse percurso. A cada 
mudança de direcção num cruzamento está associada uma penalização adicional de 3 minutos. 
Qual o caminho mais rápido entre o nodo 1 e o nodo 8 ? 
1 2
4
56 7
83
1 3 1
2
2
2 3
6
4
 
7- Na rede da fig., onde a cada arco está associada a respectiva capacidade, calcule o fluxo 
máximo que é possível enviar do nodo origem 1 para o nodo destino 7. 
 
4
1
2
3
4
6
7
3
4 5
4
9
1
6
1 2
2
3
4
 
Considere que inicialmente o fluxo a enviar é nulo. 
Assinale graficamente o corte mínimo e calcule a respectiva capacidade. 
 
Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios Fichas de Exercícios estudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mzestudantes@tdm.co.mz Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Docente: Rodrigues Zicai Zicai Zicai Zicai FazendaFazendaFazendaFazenda 
Investigação Operacional - Programação Linear. Método Simplex. Análise de sensibilidade. Transportes e stocks 20 
8- Dada a rede da fig., onde a cada arco está associada a sua capacidade, qual o fluxo máximo 
que pode ser enviado do nodo origem (1) para o nodo terminal (5) ? 
 
1
2 3
4
5
[2]
[2]
[2]
[1]
[1]
[3]
[3]
[4]
 
 
9- O Snack Bar Senta Baixo, Lda. é proprietário de um parque de diversões. Na fig. os nodos 
representam os pontos de diversão e os arcos as respectivas ligações, onde os visitantes são 
transportados por pequenos comboios a diesel. Dado que os caminhos são algo acidentados 
geograficamente e o material circulante apresenta sinais de envelhecimento, apenas podem ser 
realizadas diariamente as viagens assinaladas. Assumindo que os comboios andam sempre 
cheios, quais são os percursos e quantos comboios devem circular de modo a levar o máximo 
número de visitantes diários da entrada (nodo0) para a montanha russa (nodo 6). Considere a 
situação em que não há viagens como solução inicial. 
 
 
0 
1 
2 
3 
4 
6 
5 
5 
7 
4 
3 
4 
5 
4 
9 1 
6 1 2 
 
 
10- Determine o plano óptimo de envio de 10 unidades de fluxo ao custo mínimo do nodo 1 para 
o nodo 5 na rede da fig. bij representa a capacidade do arco e cij o custo de enviar uma unidade 
de fluxo através do arco. 
 
1
2
3
4
5
[4,5]
[6,9]
[4,5]
[5,6]
[2,3]
[2,4]
[8,6]
[bij,cij]