Formulação do problema de optimização-investigação operacional

Prévia do material em texto

2. Formulação do problema de optimização 
2.1. Natureza de um problema 
Tomar decisões constitui uma tarefa básica da gestão. E, hoje em dia, coloca-se 
a permanente questão da definição do que é um problema de decisão. Para tal, 
começa-se por identificar quais as condições mínimas que tem que se reunir para que 
um problema tenha lugar: Estas são: 
 Deve existir um indivíduo (I), que ocupa um meio ambiente (A), a 
quem o problema pode ser atribuído; 
 Devem existir pelo menos duas linhas de acção (ou alternativas de 
decisão) que podem ser seguidas; 
 Devem existir pelo menos dois resultados possíveis associados às 
alternativas e pelo menos um dos resultados é o que se deseja, isto é, 
é um objectivo; 
 As linhas de acção disponíveis devem proporcionar uma certa 
probabilidade de atingir o objectivo. 
Resumindo, diz-se que existe um problema quando se pretende algo, dispõe-se 
de várias alternativas para alcança-lo, cada uma apresentando probabilidades 
diferentes de sucesso e está-se em dúvida quanto a linha de acção que se deve 
escolher. 
Na maior das vezes, os problemas de decisão têm uma "configuração" mais 
complexa do que a apresentada e em geral, é essa que se apresenta à Investigação 
Operacional. A complexidade pode decorrer de qualquer combinação das seguintes 
condições: 
 o problema é de um grupo, e não de um indivíduo; 
 o meio ambiente (A) modifica-se de tal maneira que afecta as 
probabilidades associadas às linhas de acção ou aos resultados; 
 o número de alternativas de acção pode ser muito grande; 
 o número de objectivos também pode ser muito grande e os mesmos 
podem não ser completamente coerentes; 
 as linhas de acção escolhidas por quem toma a decisão podem ter que 
ser executadas por outras pessoas; 
 as pessoas que não estão envolvidas na tomada de decisão, nem na 
sua execução podem ser afectadas por ela e reagirem favorável ou 
desfavoravelmente 
É precisamente nos problemas mais complexos de decisão que a necessidade da 
Investigação Operacional mais de faz sentir. 
 
2.2. Formulação do problema e construção de modelos 
Uma vez caracterizados os problemas de decisão é agora fácil reconhecer a 
estrutura dos modelos da Investigação Operacional. Assim, para formular um 
problema precisamos de examinar vários aspectos, sendo os primeiros os seguintes: 
 quem toma a decisão; e 
 quais são os seus objectivos; 
A partir destas informações e de outros dados estabelecemos a medida de 
desempenho U, para avaliar as alternativas de acção. 
Em seguida analisam-se os seguintes aspectos: 
 Quais os aspectos da situação estão sujeitos ao controle de quem 
toma a decisão - identificar as variáveis controladas; 
 Que outros do meio ambiente, envolvendo ou não seres humanos, 
podem afectar os resultados das escolhas disponíveis - identificar as 
variáveis não controladas; 
 Dentro de que limites as variáveis podem ser controladas - identificar 
as restrições; 
De salientar que precisamos de examinar todos os componentes do modelo de 
decisão. Isto significa que formular um problema consiste em: 
 escolha do critério de optimização; 
 selecção das variáveis à optimizar; 
 exame das restrições impostas ao processo; 
 elaboração da função objectiva. 
Destas etapas definidas resulta que a formulação do problema de optimização 
exige bons conhecimentos da essência do processo em estudo, que permitem exprimir, 
adequadamente, através da função objectivo os objectivos e os recursos de 
optimização, sob uma forma matemática padronizada. A formulação do problema de 
optimização faz-se com base na modelação dos processos tecnológicos ou gerênciais de 
formas a permitir a apresentação de um processo real através do seu modelo 
matemático idealizado. 
2.2.1. Escolha do critério de optimização 
O critério de optimização é o indício principal, segundo o qual se avalia o 
funcionamento do processo em estudo. Ele deve satisfazer três exigências principais, a 
saber: 
 Deve ser único; 
 Deve ser possível de exprimir-se por número; 
 Deve variar monotonamente. 
Geralmente, existem certas dificuldades para a satisfação da primeira 
exigência, pois qualquer sistema em estudo caracteriza-se, de um modo geral, por 
diversas variáveis de estudo e, é evidente que sempre se pretende organizar a 
ocorrência do processo de tal maneira que todas as variáveis em estudo sejam as 
melhores. 
No entanto, hoje em dia, as técnicas de optimização permitem, apenas, 
optimizar o processo por um único critério. Refira-se que continua em investigação a 
optimização de processos através de vários critérios, mas ainda não foi possível a 
generalização dos resultados. 
Deste modo, se usar como critério de optimização a selecção de uma variável 
entre as várias possíveis, sempre corre-se o risco de se escolher uma que não seja a 
melhor. Note-se que para um mesmo sistema optimizado por vários critérios, as 
condições óptimas podem não coincidir e, entre elas existirão as aceitáveis e as não 
aceitáveis. Assim, na formulação de um problema de optimização deve-se seleccionar 
um critério de optimização que leve aos melhores resultados. Na prática, seria 
preferível optimizar um processo através de vários critérios e, dos resultados obtidos, 
escolher o mais aceitável, isto é, aquele que dá as condições óptimas globais. 
Na optimização de processo, frequentemente distinguem-se dois tipos de 
critérios: 
 os critério económicos, tais como: o lucro, a rentabilidade, o 
rendimento relativo, os preços, os custos, as receitas, etc.; e 
 os critérios tecnológicos: a qualidade, o rendimento do produto, as 
características dos produtos, a produtividade, etc.. 
Refira-se que cada critério tecnológico é uma forma reduzida de um critério de 
um critério económico equivalente. E como regra, os critérios económicos usam-se 
para a optimização de processos à nível de empresa, enquanto que os critérios 
tecnológicos usam-se ao nível de elementos ou de algumas instalações. 
No que se refere à segunda exigência, o critério de optimização deve ser 
escolhido de tal modo que permita a sua expressão através de números. Esta 
exigência resulta da possibilidade de se fazer comparação entre números, sem 
qualquer margem de dúvidas. Caso contrário, a avaliação das variáveis tornar-se-ia 
extremamente difícil, senão impossível. 
A última exigência, a da variação monótona do critério de optimização em 
função das variáveis à optimizar, está relacionada tanto com a resolução do problema, 
como com a implementação dos resultados. 
2.2.2. Selecção das variáveis a optimizar 
Qualquer processo a ser optimizado deve dispor de recursos de optimização, 
isto é, deve possuir um certo número de variáveis de entrada que, através das suas 
variações, se torne possível determinar as condições óptimas. Assim, as variáveis de 
comando constituem as variáveis à optimizar. 
Na selecção das variáveis a optimizar é sempre conveniente o maior número 
possível das variáveis do processo, desde que se disponha de mais recursos para a 
optimização; 
Deste modo, há que estabelecer um compromisso entre o número das variáveis 
a optimizar seleccionadas, os métodos e os meios de realização da optimização. 
2.2.3. Exame das restrições impostas ao processo 
Na formulação de problemas de optimização, geralmente é pouco seguro 
considerar que as variáveis do sistema podem ser alteradas de qualquer modo e que o 
processo pode funcionar, independente mente de todas as influências exteriores. Por 
isso, é necessário as condições restritivas que são impostas ao processo. 
As restrições são as condições que é necessário respeitar, independentemente 
da forma como influem sobre o critério de optimização. E elas podem ter origem nos 
aspectos mais diversos dos problemas. As mais frequentes são: 
 Devidas à quantidade e qualidade do materiais; 
 Devidas à tecnologia usada; 
 Devidas às causas económicas e de conjuntura; 
 Devidas ao meio ambiente; 
 Outras restrições. 
2.2.4. Elaboração da funçãoobjectiva 
A função objectivo representa o critério de optimização apresentado em função 
das variáveis à optimizar, geralmente tem o seguinte aspecto: 
),,
2
,
1
(
n
xxxzz  
Com a definição da função objectiva, o problema da optimização torna-se 
completamente definido. Entretanto, optimizar um processo significa encontrar o valor 
extremo (máximo ou mínimo) da função objectivo. Assim, nos modelos a função 
objectivo deve ser sempre precedida pelo objectivo de optimização, que pode ser 
maximizar ou minimizar. 
2.3. Construção de modelos matemáticos 
A ideia principal que forma a base de construção de modelo matemáticos na 
formulação de problemas de optimização consiste em considerar o sistema como um 
conjunto de funções elementares que se designa processo. E, na prática, o processo é 
comparado a uma caixa negra onde decorres a transformação de elementos de entra 
em elementos de saídas. 
 
 
 
Figura 2.1. – Representação esquemática de formulação de problemas de optimização 
As entradas incluem um elemento ou um conjunto de elementos que 
caracterizam o estado inicial do processo. Isto é, as entradas representam os recursos 
consumidos, ou utilizados, pelo processo e podem ser matéria-prima, meios humanos 
ou materiais, tempo, máquinas, equipamentos, etc.. 
As saídas incluem um elemento ou um conjunto de elementos que caracterizam 
o estado final do processo e constituem os resultados finais do processo que podem 
ser quantidades de produtos acabados, de meios humanos ou materiais, decisões, etc. 
O processo representa um determinado meio de transformação dos elementos 
de entrada em elementos de saída. Por isso, os mecanismos internos do processo não 
são objecto de estudo de Investigação Operacional. Eles são objecto de estudo de 
diversas especialidades, tais como a Gestão, a Engenharia, a Medicina, etc.. 
Entretanto, para qualquer que seja a especialidade envolvida, o procedimento 
construção de modelos matemáticos baseia-se fundamentalmente em três suposições, 
a saber: 
 Proporcionalidade – Nos modelos matemáticos os valores dos elementos de 
entrada e de saída de qualquer processo geralmente são proporcionais à 
intensidade desse processo. Isto é, qualquer produto produzido (elemento de 
saída) é determinado pela intensidade que é uma norma técnica que equilibra o 
processo em função dos elementos de entrada. A proporcionalidade deve 
verificar-se entre a quantidade de elementos de saída determinada pela 
intensidade do processo. Isto significa que em caso de multiplicação da 
PROCESSO
(caixa negra)
Entradas Saídas
intensidade do processo multiplicam-se também os elementos de entrada e de 
saída. Por exemplo, o aumento de número de operários uma oficina implica o 
aumento do número de instrumentos de trabalho. Similarmente, o aumento da 
quantidade dos elementos de entrada para a produção, implica o aumento da 
quantidade dos elementos de saída. 
 Não negatividade – A intensidade do processo de ser sempre positiva, pois é 
difícil interpretar valores negativos em processos reais. Por exemplo, é 
impossível produzir-se um número negativo de artigos. Esta suposição chama-
se não negatividade. 
 Aditividade – A quantidade total de qualquer ingrediente determinado pelo 
sistema como sendo inteiro deve ser igual a soma das quantidades empregues 
no sistema. Deste modo. Cada elemento do sistema caracteriza-se através dum 
balanço material. Por exemplo, a quantidade de horas de trabalho consumidas 
em todos os processos, supondo que se produzem vários artigos, deve 
corresponder a existência de operários necessários em cada um dos processos 
considerados. 
Na construção de modelos devem ser observados os princípios de modelação. 
Estes são: 
a) Nunca se deve construir um modelo complicado quando um outro mais 
simples for satisfatório; 
b) A fase de dedução do modelo deve ser conduzida rigorosamente; 
c) modelo deve se adaptar à técnica de optimização adoptada; 
d) modelo deve ser válido antes da implementação; 
e) modelo não deve ser forçado a fazer nem deve ser criticado por não fazer 
o que ele não foi concebido para fazer; 
f) modelo não substitui a pessoa que toma as decisões. 
2.4. Exemplos de formulação de modelos simples 
Nesta secção, apresentam-se alguns exemplos de formulação de moedelos 
matemáticos de problemas de optimização. 
Exemplo 1 – Considere o seguinte problema 
Uma empresa produz três produtos P1, P2 e P3. A fabricação de uma unidade 
do produto P1 necessita de 8 homem–horas de trabalho, 8 kg da matéria-prima A e 5 
kg da matéria-prima B. Uma unidade do produto P2 necessita de 5 homem–horas, 7 
kg da matéria-prima A e 4 kg da matéria-prima B. E as necessidades para a fabricação 
de uma unidade do produto P3 são 4 homem–horas, 9 e 3 quilogramas, 
respectivamente, das matérias-primas A e B 
Os fornecimentos semanais das matérias-primas A e B à empresa são 
limitadas, respectivamente, em 3,23 e 1,7 toneladas, sendo 2400 homem–horas 
disponíveis. 
Sabe-se que não há dificuldade quanto ao manuseamento do produto P2, 
enquanto que, devidas as condições de conservação, não se pode produzir, no total, 
mais de 350 unidades dos produtos P1 e P3, por semana. 
Assumindo que as margens brutas, por unidade produzida, dos produtos P1, 
P2 e P3, são, respectivamente, de 90, 65 e 75 contos, estabeleça um óptimo plano 
semanal de produção para a empresa. 
 
Resolução: 
Variáveis a optimizar 
x1 – Quantidade do produto P1 (unidades) 
x2 – Quantidade do produto P2 (unidades) 
x3 – Quantidade do produto P3 (unidades) 
Restrições 
8x1 + 5x2 + 4x3  2400 – Disponibilidade da mão-de-obra (homem – horas) 
8x1 + 7x2 + 9x3  3,23  1000 – Disponibilidade da matéria-prima A (Quilogramas) 
5x1 + 4x2 + 3x3  1,7  1000 – Disponibilidade da matéria-prima B (Quilogramas) 
 x1 + x3  350 – Limitação das condições de conservação (unidades) 
Função Objectiva 
Z = 90x1 + 65x2 + 75x3 – margem bruta total, por semanal (contos) 
Modelo Matemático 
0x,x,x
350xx
17003x4x5x
32309x7x8x
24004x5x8x:aSujeito
75x55x90xz:Maximizar
321
31
321
321
321
321






 
Exemplo 2 – Considere o seguinte problema 
A Direcção de Finanças das Linhas Aéreas de Moçambique (LAM), deve decidir 
sobre as quantidades de combustível, para os aviões daquela empresa, a adquirir de 
três possíveis fornecedores, a saber: a BP, a MOBIL e a SHELL. Na Região Centro de 
Moçambique, a LAM reabastece os seus aviões em três aeroportos servidos por ela, 
designadamente: Beira, Quelimane e Tete. 
As quantidades mínimas necessárias de combustível nos três aeroportos são de 
4,5 kl, 2,5 kl e 1,5 kl para os aeroportos da Beira, de Quelimane e de Tete, 
respectivamente. E as empresas fornecedoras comunicaram que, durante o próximo 
mês, podem fornecer até as seguintes quantidades de combustível: 6,5 kl, 5,5 kl e 
2,75 kl, respectivamente, para a BP, a MOBIL e a SHELL. 
Sabe-se que ao preço cotado por litro de combustível, quando forem 
acrescentados os custos de transporte, os custos combinados de cada litro de 
combustível fornecido por uma certa empresa a um determinado aeroporto são dados 
na tabela abaixo. 
 
AEROPORTOS 
EMPRESAS FORNECEDORAS 
BP MOBIL SHELL 
Beira 12 contos 13 contos 14 contos 
Quelimane 17 contos 16 contos 15 contos 
Tete 16 contos 15 contos 17 contos 
Formule o problema de decisão de aquisição de combustível. 
 
Resolução: 
Variáveis à optimizar: 
x11 – quantidade de combustível fornecido ao Aeroporto da Beira pela BP (l); 
x12 – quantidade de combustível fornecido ao Aeroporto da Beira pela MOBIL (l); 
x13 – quantidade de combustível fornecido ao Aeroporto da Beira pela SHELL (l); 
x21 – quantidade de combustível fornecido ao Aeroporto de Quelimane pela BP (l); 
x22 – quantidade de combustível fornecido ao Aeroporto de Quelimane pela MOBIL (l); 
x23 – quantidade de combustível fornecido ao Aeroporto de Quelimane pela SHELL (l); 
x31 – quantidade de combustível fornecido ao Aeroporto de Tetepela BP (l); 
x32 – quantidade de combustível fornecido ao Aeroporto de Tete pela MOBIL (l); 
x33 – quantidade de combustível fornecido ao Aeroporto de Tete pela SHELL (l); 
Restrições: 
x11 + x12 + x13  4,5  1000 – necessidades do aeroporto da Beira (l); 
x21 + x22 + x23  2,5  1000 – necessidades do aeroporto de Quelimane (l); 
x31 + x32 + x33  1,5  1000 – necessidades do aeroporto de Tete (l); 
x11 + x21 + x31  6,5  1000 – limitação da capacidade de fornecimento da BP (l); 
x12 + x22 + x32  5,5  1000 – limitação da capacidade de fornecimento da MOBIL (l); 
x13 + x23 + x33  2,75  1000 – limitação da capacidade de fornecimento da SHELL (l); 
Função Objectiva 
z = 12x11+13x12+14x13+17x21+16x22+15x23+16x31+15x32+17x33 – custo total (contos) 
Modelo Matemático 
0x,x,x,x,x,x,x,x,x
2750xxx
5500xxx
6500xxx
1500xxx
2500xxx
4500xxx:aSujeito
17x15x16x15x16x17x14x13x12xzMinimizar
333231232221131211
332313
322212
312111
333231
232221
131211
333231232221131211








 
Exemplo 3 – Considere o seguinte problema 
Uma empresa de produção de tomate enlatado opera duas fábricas e tem 
contrato com três agricultores, o senhor Salvador, a senhora Felizmina e o senhor 
Rachide que asseguram o fornecimento de tomate fresco às duas fábricas nas 
seguintes condições: 
 senhor Salvador: 200 toneladas a 10 contos por quilo; 
 senhora Felizmina: 300 toneladas a 9 contos por quilo; e 
 senhor Rachide: 400 toneladas a 8 contos por quilo. 
Os preços de transporte, em milhões de meticais, por tonelada de tomate são os 
seguintes: 
 
Da machamba: 
Para 
Fábrica I Fábrica II 
Do Sr. Salvador 2,0 3,0 
Da Sra. Felizmina 1,0 2,0 
Do Sr. Rachide 4,0 3,0 
As capacidades de produção das fábricas e os custos de produção, em milhões 
de meticais, por cada tonelada de tomate são dados na tabela abaixo. 
 
 Fábrica I Fábrica II 
Capacidade de Produção 450 toneladas 500 toneladas 
Custos de produção 25 30 
Sabendo que o tomate enlatado é vendido aos distribuidores a 60 milhões de 
meticais por tonelada e que a empresa tem a colocação assegurada para toda a 
produção das suas duas fábricas, formule o problema do plano de produção como um 
modelo de programação linear. 
Resolução 
Variáveis à optimizar: 
x11 – quantidade de tomate fornecido pelo senhor Salvador à Fábrica 1 (ton.); 
x12 – quantidade de tomate fornecido pelo senhor Salvador à Fábrica 2 (ton.); 
x21 – quantidade de tomate fornecido pela senhora Felizmina à Fábrica 1 (ton.); 
x22 – quantidade de tomate fornecido pela senhora Felizmina à Fábrica 2 (ton.); 
x31 – quantidade de tomate fornecido pelo senhor Rachide à Fábrica 1 (ton.); 
x32 – quantidade de tomate fornecido pelo senhor Rachide à Fábrica 2 (ton.). 
Restrições: 
x11 + x12 = 200 – limitação do fornecimento do senhor Salvador (ton.); 
x21 + x22 = 300 – limitação do fornecimento do senhor Salvador (ton.); 
x31 + x32 = 400 – limitação do fornecimento do senhor Salvador (ton.); 
x11 + x21 + x31  450 – limitação da capacidade de processamento da Fábrica 1(ton.); 
x12 + x22 + x32  500 – limitação da capacidade de processamento da Fábrica 2 (ton.). 
Função Objectivo 
Os coeficientes da Função Objectivo representam, neste caso, os lucros 
provenientes do venda de uma tonelada de tomate processado por uma certa Fábrica e 
fornecido por um certo agricultor. Sendo assim, tem-se: 
 para o tomate fornecido pelo senhor Salvador à Fábrica 1: 60–(10+2+25)=23; 
 para o tomate fornecido pelo senhor Salvador à Fábrica 2: 60–(10+3+30)=17; 
 para o tomate fornecido pela senhora Felizmina à Fábrica 1: 60–(9+1+25)=25; 
 para o tomate fornecido pela senhora Felizmina à Fábrica 2: 60–(9+2+30)=19; 
 para o tomate fornecido pelo senhor Rachide à Fábrica 1: 60–(8+5+25)=22; 
 para o tomate fornecido pelo senhor Rachide à Fábrica 2: 60 – (8+4+30)=18; 
Desta forma, a função objectivo fica com o seguinte aspecto: 
z = 23x11 + 17x12 + 25x21 + 19x22 + 22x31 + 18x32 – Lucro total (milhões de meticais) 
Modelo Matemático 
0x,x,x,x,x,x
450xxx
00xxx
450xx
300xx
00xx:aSujeito
18x22x19x25x17x23xzMaximizar
323122211211
322212
312111
3231
2221
1211
323122211211







4
2
 
 
Exemplo 4 – Considere o seguinte problema 
A Manhiça Contentores Metálicos SARL, pretende produzir um tanque 
cilíndrico, com a capacidade de cinquenta mil litros, para armazenagem de 
combustíveis líquidos. A direcção daquela empresa prevê que o futuro tanque tenha 
muita aceitação e, em princípio, deverá ser produzida em milhões de unidades. Por 
isso, é necessário assegurar a redução dos seus custos de fabricação, de modo que a 
empresa possa conseguir maiores proveitos. 
Sabendo que o custo de fabricação do tanque pode ser directamente 
relacionado com a área total da chapa metálica utilizada, formule o modelo 
matemático do projecto do novo tanque e determine as suas dimensões óptimas. 
Resolução 
Variáveis a optimizar: 
x1 – Raio do tanque (m) 
x2 – Altura do tanque (m) 
Restrição: Capacidade do contentor (m3) 
50xx 2
2
1  
Função Objectiva: 
21
2
1 22 xxxz   – Área total do tanque (m2) 
Modelo Matemático 
0,
50:
22:
21
2
2
1
21
2
1



xx
xxaSujeito
xxxZMinimizr


 
Exemplo 5 – Considere o seguinte problema 
Uma certa operação industrial requer um contentor fechado, em forma de 
paralelogramo, para o armazenamento de um certo tipo de fluído. A fabricação do 
contentor necessário, requer a construção de uma estrutura de reforço, conforme se 
apresenta na figura abaixo, pois espera-se que este venha sofrer uma elevada pressão 
interna. 
 
Os dados relativos aos custos de fabricação da estrutura de reforço são os 
seguintes: 
 membros horizontais – 20 contos por metro; e 
 membros verticais – 30 contos por metro. 
Sabendo que a capacidade do contentor deve ser exactamente de 60000 litros, 
determine as dimensões óptimas dos membros da estrutura necessária. 
Resolução 
Variáveis a optimizar: 
x1 – Comprimento da estrutura (m) 
x2 – largura da estrutura (m) 
x3 – Altura da estrutura (m)) 
Restrição: 
x1 x2 x3 = 60 – Capacidade do contentor (m3) 
Função Objectiva: 
z = 20(4x1 + 4x2) + 30 4x3 – Custo da estrutura (contos/m) 
Modelo Matemático 
0x,x,x
60xxx:aSujeito
120x80x80xz:Minimizar
32x
32x
321



 
Exemplo 6 – Considere o seguinte problema 
Imagine que, para a próxima quadra festiva, a Empresa de Transportes 
Públicos de Maputo (TPM) tenha que implementar um plano especial de 24 horas de 
serviço, e que tenha efectuado um estudo que apurou o seguinte: 
 
HORÁRIO Nº DE AUTOCARROS NECESSÁRIOS 
01 – 05 15 
05 – 09 30 
09 – 13 25 
13 – 17 35 
17 – 21 30 
21 – 01 20 
Sabendo que os turnos têm duração de 8 horas consecutivas, e que devem ser 
iniciados às 01, 05, 09, 13, 17 e 21 horas, formule o problema de decisão de alocação 
dos autocarros 
Resolução: 
Variáveis a optimizar 
x1 – Quantidade de viaturas a iniciar o turno à 01 hora (unidades) 
x2 – Quantidade de viaturas a iniciar o turno às 05 horas (unidades) 
x3– Quantidade de viaturas a iniciar o turno às 09 horas (unidades) 
x4 – Quantidade de viaturas a iniciar o turno às 13 horas (unidades) 
x5 – Quantidade de viaturas a iniciar o turno às 17 horas (unidades) 
x6– Quantidade de viaturas a iniciar o turno às 21 horas (unidades) 
Restrições 
Para facilitar a composição das restrições, conside-se o esquema abaixo que 
mostra o plano de distribuiçõa das viaturas, em função da hora do início do turno. 
 
Neste esquema pode-se observar que as viaturas que iniciam o turno à 1 hora, 
só terminam às 9 horas. No entanto, como às 5 horas começa o segundo turno, então 
no intervalo entre 5 e 9 horas circulam as viaturas de ambos os turnos. E esta 
situação de sobreposição, repete-se em todos os intervalos. Sendo assim, as restrições 
do problema, reflictem as necessidades de viaturas em cada intervalo de tempo e são 
as seguintes: 
x1 + x6  15 – necessidadede viaturas entre 01 e 05 horas (unidades); 
x1 + x2  30 – necessidade de viaturas entre 05 e 09 horas (unidades); 
x2 + x3 25 – necessidade de viaturas entre 09 e 13 horas (unidades); 
x3 + x4  35 – necessidade de viaturas entre 13 e 17 horas (unidades); 
x4 + x5  30 – necessidade de viaturas entre 17 e 21 horas (unidades); 
x5 + x6  20 – necessidade de viaturas entre 21 e 01 horas (unidades); 
Função Ojectivo 
z = x1 + x2 + x3 + x4 + x5 + x6 - número total de viaturas (unidades) 
 
Modelo Matemático 
01 05 09 13 17 21 01 Horas
x1
x2
x3
x5
x4
x6x6
0x,x,x,x,x,x
20xx
30xx
35xx
25xx
30xx
15xx:asujeito
xxxxxxz:Minimizar
654321
65
54
43
32
21
61
654321








 
Exemplo 7 – Considere o seguinte problema 
Uma empresa de comercialização de papel sediada em Maputo, distribui papel 
para jornal a partir de rolos de papel de 70 metros de comprimento e 1,5 metros de 
largura. E, para o próximo mês, a empresa recebeu as seguintes emcomedas: 
 70 rolos de 80 centimetros de largura, para o Jornal Fim de Semana; 
 100 rolos de 60 centímetros de largura, para o Jornal Zambeze; e 
 120 rolos de 50 centímetros de largura, para o Jornal Demos. 
Admitindo que todos os rolos fornecidos terão 70 metros de comprimento, 
estabeleça o óptimo plano de corte de rolos de modo a minimizar os desperdícios de 
papel. 
Resolução 
Para resolver este problema, considere-se que existem 5 maneiras de cortar 
rolos de 1,5 metros de largura respeitando as exigências de rolos com largura de 80, 
60 e 50 centímetros, conforme resumem as figuras abaixo: 
 
80 cm
60 cm
Desperdício10 cm
1
,5
 m
80 cm
50 cm
Desperdício20 cm
1
,5
 m
Maneira I Maneira II
 
 
 
 
Estas cinco maneiras de corte podem ser resumidas segundo o quadro abaixo. 
 
 MANEIRAS DE CORTES 
ENCOMENDAS I II III IV V 
Quantidades 
Necessárias 
I (largura 80 cm) 1 1 – – – 70 
II (largura 60 cm) 1 – 2 1 – 100 
III (largura 50 cm) – 1 – 1 3 120 
LARGURAS DOS 
DESPERDÍCIOS (cm) 
10 20 30 40 0 
 
60 cm
60 cm
Desperdício30 cm
1
,5
 m
60 cm
50 cm
Desperdício40 cm
1
,5
 m
Maneira III Maneira IV
50 cm
50 cm
50 cm
1
,5
 m
Maneira V
A partir deste quadro, torna-se fácil fazer a formulação do problema, que é feita 
da seguinte forma: 
 
Variáveis a optimizar: 
x1 – número de rolos a serem cortados segundo a maneira I; 
x2 – número de rolos a serem cortados segundo a maneira II; 
x3 – número de rolos a serem cortados segundo a maneira III; 
x4 – número de rolos a serem cortados segundo a maneira IV; e 
x5 – número de rolos a serem cortados segundo a maneira V. 
Restrições: 
x1 + x2 =70 – rolos necessários no Jornal Fim de Semana (unidades); 
x1 + 2x3 + x4 =100 – rolos necessários no Jornal Zambeze (unidades); e 
x2 + x4 + 3x5 =120 – rolos necessários no Demos (unidades). 
Função Objectivo: 
z =10x1 + 20x2 + 30x3 + 40x4 – Largura total do desperdício de papel. 
Modelo Matemático: 
0x,x,x,x,x
1203xxx
100x2xx
70xx:asujeito
0x40x30x20x10xz:Minimizar
54321
542
431
21
54321





 
Referências selecionadas 
TAHA, Handy (1997). “Operations Research. An Introduction”, 6th Edition. Prentice-
Hall, Upper Saddle River. 
GURREIRO, Jorge; MAGALHÃES, Alípio e RAMALHETE, Manuel (1985). “Programação 
Linear”. McGraw Hill de Portugal, Lisboa. 
BRONSON, Richard (1985). “Pesquisa Operacional”. McGraw Hill do Brasil, São Paulo. 
ANDRADE, Eduardo L. (2000). Introdução à Pesquisa Operacional”, 2ª Edição. Livro 
Técnicos e Científicos Editora, Rio de Janeiro.