Material de Investigação Operacional

TEMA: II Programação Linear

UNIDADE 2: PROGRAMAÇÃO LINEAR

2.1. Introdução

Vários ramos da sociedade, como a agricultura, a indústria, os transportes, os

sistemas de saúde, as ciências sociais, etc., têm problemas de afectação de
recursos limitados de que dispõem. A programação linear (PL) desenvolve
soluções matemáticas desse tipo de problemas, cujos modelos são formados por
funções lineares.

2.2. Formulação

EXEMPLO 1

A fábrica GTM está vocacionada para a produção de quatro (4) produtos I, II, III
e IV. O processo produtivo utilizando para a produção desses produtos requer
que os passem por três tipos de máquinas A, B e C.

Sendo assim assumiremos que a produção é contínua e que cada produto deve
passar pela máquina A, em seguida pela máquina B e por último pela máquina
C.

Consideremos, no entanto, ser insignificante o tempo requerido para o juste de

cada máquina, para a produção de cada produto.

A tabela abaixo apresentada mostra o seguinte:

 As horas requeridas em cada tipo de máquina por unidade de cada

produto;
 O total de horas mensais disponíveis por cada tipo de máquina;
 O lucro que se obtém por unidade de produto, supondo-se que o lucro é
directamente proporcional ao número de unidades que se vendem.
Prof. Eng.º MBUTA DOMPETELO Página 1
Material de Investigação Operacional
TEMA: II Programação Linear

Tabela nº 1
Tipo de máquinas Produtos Total de horas
I II III IV disponíveis/mês
A 3 2 5 2 3.500
B 1 8 2 7 10.000
C 3 6 7 2 6.000
Lucro unitário 6,00 8,50 9,80 5,10

Pretende-se determinar qual deve ser a produção mensal de cada produto para
que a GTM maximize o seu lucro.

Considerações

Com os dados apresentados na tabela nº1 constata-se o seguinte:

 O objectivo da fábrica é alcançar o lucro máximo;

 Para se poder alcançar esse objectivo, a GTM tem que produzir I, II, III e
IV;
 A produção tem que ter em conta as seguintes restrições ou limitações:
A disponibilidade, em horas, que vai determinar quanto tempo as
máquinas vão funcionar e consequentemente, a qualidade de produto que
se vai produzir.

A partir desta constatação pode-se deduzir as funções matemáticas que

representam a situação a resolver. Tratemos, pois de resolver esta situação da
seguinte maneira:

1. Passo: Definição das variáveis de decisão

Suponhamos que representamos por Xj o número de unidades do produto j a

produzir mensalmente. Para a GTM é necessário determinar as quantidades
mensais a produzir de produtos I, II, III e IV Assim, estabelecemos:

X1: Quantidades do produto I a produzir mensalmente;

Prof. Eng.º MBUTA DOMPETELO Página 2

Material de Investigação Operacional
TEMA: II Programação Linear

X2: Quantidades do produto II a produzir mensalmente;

X3: Quantidades do produto III a produzir mensalmente;

X4: Quantidades do produto IV a produzir mensalmente;

Uma vez definidas as variáveis de decisão, o passo a seguir será:

2. Passo: Condição de Não Negatividade

Como não é possível ter produções negativas, estabelece-se a seguinte condição.

X1≥0; X2≥0; X3≥0; X4≥0 ou simplesmente Xj≥0 com j=1, 2, 3, 4

3. Passo: Sistema de Restrições

No sistema de restrições consideremos primeiro as restrições impostas pela

disponibilidade do tempo/máquina.

O total de horas utilizado para a máquina do tipo A será.

3X1 + 2X2 + 5X3 + 2X4

Dado que 3 é o tempo requerido por unidade de produto I (X1), e assim por
diante. Será no entanto, importante anotar que a quantidade total de horas
utilizadas não poderá ultrapassar as 3.500 horas disponíveis para máquina A.

3X1 + 2X2 + 5X3 + 2X4 ≤ 3.500

Para máquinas B e C podemos escrever:

X1 + 8X2 + 2X3 + 7X4 ≤ 10.000

3X1 + 6X2 + 7X3 + 2X4 ≤ 6.000

Prof. Eng.º MBUTA DOMPETELO Página 3

Material de Investigação Operacional
TEMA: II Programação Linear

4. Passo: Definição da Função Objectiva

Para se determinar a função objectiva interessa-nos determinar os valores que

tomarão X1, X2, X3 e X4 de tal forma que se maximize o lucro. Como o
tempo/máquina disponível é limitado, não podemos incrementar arbitrariamente
a produção de cada produto. A produção deverá substituir-se entre os produtos I,
II, III e IV de forma a maximizar o lucro, mas sem exceder o tempo de horas/
máquina mês disponível. Se Z é o lucro mensal por unidade de produto
produzido, a função objectiva poderá escrever-se da seguinte forma:

MaxZ= 6X1 + 8.50X2 + 9.80X3 + 5.10X4

EXEMPLO 2

Uma fábrica produz dois produtos P1 e P2 em 3 máquinas M1, M2 e M3, indicou-

se a abaixo os tempos de processamento (em horas) bem como as receitas
líquidas (em dinheiro) obtidas com a venda dos artigos por unidade.

Tabela nº 2
Artigos Máquinas Receitas Líquidas
M1 M2 M3
P1 0,25 0,40 0,00 2

P2 0,50 0,20 0,80 3

Para um tempo de elaboração de 40 horas semanais, formule um modelo de

programação linear que lhe permita definir quais as quantidades de P 1 e P2 a
produzir de modo a maximizar a receita líquida.

Prof. Eng.º MBUTA DOMPETELO Página 4

Material de Investigação Operacional
TEMA: II Programação Linear

EXEMPLO 3

Uma empresa electrónica fabrica dois tipos de circuitos impressos: A e B.

Os circuitos do tipo A são vendidas por 4000 u.m. e do tipo B por 5000 u.m. no
processo produtivo, os dois tipos de circuitos passam por duas máquinas.

Na primeira, os circuitos do tipo A são trabalhados durante 4 horas e o tipo B

durante 5 horas. Na segunda 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 pode exceder as 24 horas de funcionamento.

Sabendo-se que a empresa pretende maximizar a receita, formule

matematicamente o problema.

EXEMPLO 4

Devido a alteração de mercado, os preços dos produtos A e B, referidos no

problema anterior do Exemplo (3), caíram para 4 e 3 mil dólares,
respectivamente.

Em simultâneo, modificam no processo produtivo, requeridos por um mais

rigoroso controlo de qualidade, levaram à aquisição de uma nova máquina, onde
tanto o produto A como o B sofrem alterações durante 1 hora. No entanto, esta
máquina não pode funcionar menos de 8 horas semanais.

Reformule o problema com novas condições.

1.1.1. Formulação do Problema de Programação Linear

O problema de programação linear pode ser escrito da seguinte forma:

Prof. Eng.º MBUTA DOMPETELO Página 5

Material de Investigação Operacional
TEMA: II Programação Linear

Dada uma função linear de várias variáveis, pretende-se determinar os valores

não negativos para essas variáveis que maximizem ou minimizem o valor da
função linear, sujeita a um certo número de limitações, que assume a forma de
um sistema de equações ou inequações lineares.

Seja F (X1, X2, ….Xr) uma função linear.

Suponhamos r o número de variáveis e que o nosso sistema de restrições ou

limitações têm m equações ou inequações, onde m <r. O enunciado pode ser
escrito da seguinte maneira, em formulação matemática:

 Temos que encontrar os valores das variáveis Xj que maximizem ou

minimizem o valor da função linear.

Z = C1X1 + C2X2 +…...+ CrXr (1.1)

E satisfaz as seguintes condições:

Xj≥0 com j=1 ……r (1.2)

≥
ai1X1 + ai2X2 +…...+ airXr = bj com i=1…..m (1.3)
≤
Onde para cada restrição só é valido um dos sinais ≤, =, ≥ .

Assume-se que aij, Cj e bj são constantes conhecidas.

 A expressão 1.1 é a Função Objectiva a optimizar, que pode ser

maximizar lucro ou minimizar custos.
 A expressão 1.2 requer as variáveis Xj não sejam negativas e denomina-
se Condição de Não Negatividade.
 O sistema de equações ou inequações 1.3 denomina-se Sistema de
Restrições Lineares.

Prof. Eng.º MBUTA DOMPETELO Página 6

Material de Investigação Operacional
TEMA: II Programação Linear

Combinações

 A expressão 1.3 representa um sistema de equações ou inequações

lineares. Uma solução do problema de programação linear é constituída
por qualquer conjunto de valores de Xj que satisfazem 1.3.
 Se a solução 1.3 satisfaz a condição de não negatividade 1.2, denomina-se
solução possível.
 Se 1.3, 1.2 e 1.1 então temos uma solução possível óptima, que
proporciona o valor óptimo para a Função Objectiva.
 As expressões representadas por 1.1, 1.2 e 1.3 são designadas por Modelo
de Programação Linear.

As variáveis Xj são chamadas variáveis de decisão e representam as actividades

principais do problema.

1.2. Propriedade do Modelo de Programação Linear

Considerando que a Função Objectiva e as restrições são lineares, elas devem

satisfazer duas propriedades.

1.2.1. Proporcionalidade

Requer que a contribuição de cada variável na função objectiva e nas restrições

deve ser directamente proporcional ao nível da variável ou da actividade.

Exemplo. Suponha que a produção de uma unidade de produto j tem um custo

de 200$ e necessita de 15kg de matéria-prima. Na produção de Xj unidade deste
produto, o custo será de 200Xj e o consumo de matéria-prima será 15Xj.

6X1 + 4X2 ≤ 24 ………….6 Representa a produção.

Prof. Eng.º MBUTA DOMPETELO Página 7

Material de Investigação Operacional
TEMA: II Programação Linear

1.2.2. Auditividade

Indica que a contribuição total de todas as variáveis na função objectiva e as

suas necessidades nas restrições, são a soma das contribuições individuais e
necessidades de cada variável.

Exemplo. Se produzir uma unidade do produto A na máquina 1 requer 2 horas e

produzir uma unidade do produto B na mesma máquina requer 3 horas,
considerando X1 = quantidade total de A produzido e X2 =quantidade total de B.

Quando escrevemos 2X1 + 3X2 isto significa que o total de horas /máquina a
utilizar é a soma das horas utilizadas para o produto A, mais as horas utilizadas
para o produto B.

A mesma análise pode ser feita para a Função Objectiva. A expressão

MaxZ = ∑CjXj indica implicitamente que o lucro total obtém-se da soma dos
lucros proporcionais por cada produto.

Esta proporcionalidade implica também que só podemos somar elementos que

têm a mesma unidade de medida.

Depois de termos a noção do que são variáveis de decisão, sistema de restrições,

função objectiva e as propriedades do modelo de programação linear o ponto a
seguir é como se constrói o modelo de Programação Linear.

1.3. Construção do Modelo de Programação Linear

Para exprimir matematicamente a situação analisada no modelo de programação

linear, o procedimento a seguir para a construção de modelo, resume-se às
seguintes fases.

1. Definição das variáveis de decisão;

2. Construção do sistema de restrições;
Prof. Eng.º MBUTA DOMPETELO Página 8
Material de Investigação Operacional
TEMA: II Programação Linear

Construção da função objectiva.

1.3.1. Definição das Variáveis de Decisão

Cada variável de decisão identifica-se como sendo cada uma das actividades do
problema, ou seja elementos através dos quais se atinge objectivos que se
persegue com a solução do problema.

A definição da variável de decisão tem duas etapas: a definição conceptual e a

definição dimensional.

[Link]. Definição Conceptual

É aquela que se refere é determinação das variáveis, i e, considera o significado

da variável no contexto do problema. Na definição conceptual temos que
considerar os chamados princípios de unicidade.

a) Unidade de origem: um mesmo produto pode ser adquirido fabricado ou

ter proveniência diferente, podendo ter como implicação, o consumo de
recursos diferentes, custos ou lucros diferentes, etc. No entanto, todas as
variáveis de uma origem são consideradas como ‘único’.

Exemplo 1:Se para Angola, o cimento é um bem de exportação, o cimento

fabricado em Luanda e o cimento no Lobito serão considerados como sendo um
único produto, cuja origem é Angola.

Exemplo 2: Se o nosso problema tratar do comércio externo de Angola, o

petróleo poderá ser a única variável na balança comercial de produtos
angolanos. A nossa variável Xj = petróleo exportado de Angola.
Se no problema do comércio externo considerarmos o petróleo como podendo
ser exportado para países africanos e exportado para países de outros

Prof. Eng.º MBUTA DOMPETELO Página 9

Material de Investigação Operacional
TEMA: II Programação Linear

continentes, haveria a necessidade de definirmos duas variáveis, da seguinte

maneira:

X1: petróleo angolano exportado para países africanos;

X1: petróleo angolano exportado para países de outros continentes.

Aqui não poderíamos definir Xj como variável única pois teríamos violado o
princípio da unicidade destino.

a) Unicidade de destino: pois não poderíamos distinguir que quantidade de

petróleo seria exportado para países africanos e qual a que iria para os
países não africanos. O mesmo produto pode ser transportado para
destinos diferentes.
Se neste mesmo problema se estabelecer o pressuposto de que o petróleo
pode ser exportado a partir de dois pontos: Cabinda e Soyo, mantendo-se
os mesmos destinos, haveria a necessidade de definirmos quatro variáveis.

X1: petróleo angolano exportado para países africanos a partir de Cabinda;

X2: petróleo angolano exportado para países africanos a partir do Soyo;

X3: petróleo angolano exportado para países de outros continentes a partir de

Cabinda;

X4: petróleo angolano exportado para países de outros continentes a partir do

Soyo.

Se tivéssemos definido apenas duas variáveis, teríamos violado o princípio da

unicidade de origem, pois não podemos distinguir que quantidade de petróleo
seria exportada a partir de Cabinda e qual a quantidade exportada a partir do
Soyo.

Prof. Eng.º MBUTA DOMPETELO Página 10

Material de Investigação Operacional
TEMA: II Programação Linear

Se o nosso modelo de exportação de petróleo contemplasse a exportação de

petróleo bruto e petróleo refinado, com as mesmas origens e destinos, já
teríamos que definir oito variáveis.

X1: petróleo angolano bruto exportado para países africanos a partir de Cabinda;

X2: petróleo angolano bruto exportado para países africanos a partir do Soyo;

X3: petróleo angolano refinado exportado para países africanos a partir de

Cabinda;

X4: petróleo angolano refinado exportado para países africanos a partir do Soyo;

X5: petróleo angolano bruto exportado para países de outros continentes a partir
de Cabinda;

X6: petróleo angolano bruto exportado para países de outros continentes a partir
do Soyo;

X7: petróleo angolano refinado exportado para países de outros continentes a

partir de Cabinda;

X8: petróleo angolano refinado exportado para países de outros continentes a

partir do Soyo.

Se tivéssemos definido apenas quatro variáveis, teríamos violado o princípio da

unicidade da estrutura tecnológica.

a) Unicidade da estrutura tecnológica: o mesmo produto pode ser

produzido através de duas tecnologias diferentes.

Unicidade do coeficiente económico: é resultado das anteriores, já que é muito

provável que o produto, ao mudar de origem ou destino ou ainda estrutura
tecnológica, muda o seu coeficiente económico (custo ou lucro).

Prof. Eng.º MBUTA DOMPETELO Página 11

Material de Investigação Operacional
TEMA: II Programação Linear

b) Isso não significa necessariamente que o coeficiente económico tem que

ser diferente.

Conclusão: com está análise concluímos que toda a variável deve ter uma
origem única e um coeficiente económico único, em função do problema
que se pretende resolver.

[Link]. Definição Dimensional

Uma vez feita a definição conceptual de uma variável, é necessário ver o aspecto
quantitativo dessa definição, que é decidir as unidades de medidas que vão ser
utilizadas. Trata-se da definição dimensional.

A quantidade tem que ser expressa em toneladas, unidades, etc.

Exemplo: Xj: Barris de petróleo exportado de Angola, Xj: kg de produto A

produzido na fábrica NC.

1.3.2. Construção do Sistema de Restrições

≥
ai1X1 + ai2X2 +…...+ airXr = bj com i=1…..m (1.4)
≤
Xj≥0 com j=1 ……r (1.5)

O sistema de equações ou inequações (1.4) e a condição de não-negatividade

(1.2) constitui os limites do problema que representa o conjunto possível de
decisão a tomar.

Para construir uma restrição é preciso seguir os seguintes passos:

1. Determinar o caracter limitado da dita restrição e definir, caso ela se possa

efectivamente classificar como tal, a dimensão física e temporal da constante
que colocou no termo independente bi, assim como o sinal da restrição,
determinada da seguinte forma:
Prof. Eng.º MBUTA DOMPETELO Página 12
Material de Investigação Operacional
TEMA: II Programação Linear

≤ Quando temos a disponibilidade máxima;

≥ Quando temos a disponibilidade mínima;

= Quando temos a satisfação total exacta.

2. Analisar que variável ou variáveis estão na restrição;

3. Uma vez determinadas as variáveis correspondentes, com vista a cumprir
com a condição de aditividade é necessário definir os coeficientes de
conversão aij que permitem adaptar a dimensão da restrição.

Na prática, o coeficiente aij é geralmente uma medida de consumo por

unidade de produto.

1.3.3. Construção da Função Objectiva

A função objectiva exprime directamente o objectivo do problema: lucro

máximo ou custo mínimo.

O conjunto de restrições (equações ou inequações) admite um conjunto de

infinito de soluções possíveis, mas é a função objectiva que permite escolher de
entre essas soluções possíveis, qual a óptima.

Max (Min) Z = C1X1 + C2X2 +…...+ CrXr

Max (Min) Z = CjXj

Na construção da função objectiva, deve ter-se sempre presente a propriedade

aditiva, implícita em toda a expressão linear, bem como a análise dimensional.

Na função objectiva aparecem as variáveis de decisão do problema assim como

os coeficientes económicos correspondentes.

Prof. Eng.º MBUTA DOMPETELO Página 13

Material de Investigação Operacional
TEMA: II Programação Linear

1.3.4. Condição de Não-Negatividade

Nunca devemos esquecer que a condição de não-negatividade é uma condição

do modelo que é sempre necessário escrevê-la quando se constrói o modelo.

Xj ≥ 0 com j = 1….r (1.2)

Modelo de programação linear

Xj ≥ 0 com j = 1….r (1.2)

Max (Min) Z = CjXj

s.a

≥
ai1X1 + ai2X2 +…...+ airXr = bj com i=1…..m (1.3)
≤
Xj≥0 com j=1 ……r (1.4)

1.3.5. Alguns problemas – tipo de programação linear

[Link]. Distribuição de produtos de um conjunto de origens para um conjunto

de destinos de modo a satisfazer a procura de cada destino e as ofertas
disponíveis nas origens, minimizando o custo total de transporte.

[Link]. Distribuição de produtos de fábricas para armazéns. O problemas é

similar ao anterior ([Link]), mas com a minimização de custos
combinados de produção e distribuição, ou maximização de uma
função de ingresso menos os custos de produção / distribuição.

[Link]. Estudos de localização de fábricas.

[Link]. Distribuição da produção entre fábricas.

Prof. Eng.º MBUTA DOMPETELO Página 14

Material de Investigação Operacional
TEMA: II Programação Linear

[Link]. Afectação de matérias-primas limitadas, utilizadas numa variedade de

produtos, de modo a maximizar o lucro total, com vista a satisfazer
uma procura mínima.

[Link]. Problemas de misturas, como por exemplo, um fabricante de tinta que

pode precisar de preparar uma determinada tinta resultante da mistura
de duas ou mais.

1.4. Exemplos práticos sobre construção do modelo de Programação Linear

1.4.1. DIRUP-Empresa de fabricação de tintas

A DIRUP produz tintas interiores e exteriores de duas matérias-primas MP1 e

MP2. A tabela a seguir representa os dados do problema.

Artigos Toneladas de MP/Ton. Tinta Disponibilidade por Dia

Exterior Interior (Ton.)
MP1 6 4 24
MP2 1 2 6
Lucro/Ton. 5 4

A procura diária para tinta interior não pode exceder a de tinta exterior em 1
tonelada.

A procura diária máxima de tinta interior é de duas toneladas. A DIRUP

pretende determinar as quantidades de cada tipo de tinta a produzir, de modo a
ter o maior lucro possível.

Podem ser feitas as seguintes constatações:

a) O objectivo da empresa é atingir o maior lucro;

b) Para atingir este objectivo, ela tem de produzir tinta interior e tinta
exterior;
c) A produção deve ter em conta as seguintes restrições ou limitações:

Prof. Eng.º MBUTA DOMPETELO Página 15

Material de Investigação Operacional
TEMA: II Programação Linear

d) Limitações na disponibilidade de matéria-prima por dia;

e) A proporção para cada tinta;
f) A limitação do mercado.

A partir destas constatações podem ser deduzidas as funções matemáticas que

representam a situação a resolver.

Para a DIRUP, é necessário determinar as quantidades diárias a produzir de tinta

interior e de tinta exterior e isto pode ser:

X1: Toneladas de tinta exterior a produzir por dia

X2: Toneladas de tinta interior a produzir por dia

O objectivo é aumentar o lucro o mais possível. Se Z é o lucro diário, podemos

escrever:

Max Z = 5X1 + 4X2

A satisfação das limitações será:

Quanto às matérias-primas, podemos expressar o seguinte:

MP1/Dia: 6X1 + 4X2 Toneladas

MP2/Dia: 1X1 + 2X2 Toneladas

Como MP1 e MP2 estão limitadas, respectivamente, a 24 e 6 toneladas, teremos:

6X1 + 4X2 ≤ 24

1X1 + 2X2 ≤ 6

Relativamente à procura, o problema diz que a diferença entre a produção diária

de tinta exterior e de tinta interior não pode ultrapassar 1 tonelada.

X1 - X2 ≤ 1

Prof. Eng.º MBUTA DOMPETELO Página 16

Material de Investigação Operacional
TEMA: II Programação Linear

A procura diária máxima de tinta interior é de 2 toneladas.

X2 ≤ 2

Implicitamente, a produção só pode ser positiva ou nula, isto é:

X1 ≥ 0; X2 ≥ 0

Assim sendo, todo o problema da DIRUP pode ser apresentado pelo seguinte
modelo:

Max Z = 5X1 + 4X2

6X1 + 4X2 ≤ 24

1X1 + 2X2 ≤ 6

-X1 + X2 ≤ 1

X2 ≤ 2

X1 ≥ 0; X2 ≥ 0

Constatamos que tanto o objectivo como as restrições são funções lineares.

1.4.2. A GAP utiliza pelo menos 800 kg de ração diariamente. A ração é

uma mistura de popcorn e soja com a seguinte composição:

Ingredientes Kg de Ingredientes Custos ($)

Proteínas Fibras
Popcorn 0.09 0.02 0.3

Soja 0.6 0.06 0.9

A ração deve conter pelo nemos 30% de proteínas e não mais de 5% de fibra.

Pretende-se determinar o custo diário mínimo para a obtenção de ração.

Prof. Eng.º MBUTA DOMPETELO Página 17

Material de Investigação Operacional
TEMA: II Programação Linear

Como a ração consiste na mistura de Popcorn e Soja, o problema depende das

seguintes variáveis:

X1: Kg diário de Popcorn na mistura

X2: Kg diário de Soja na mistura

O objectivo é determinar o custo diário na obtenção da ração:

Min Z = 0.3X1 + 0.9X2

A necessidade diária é de pelo menos 800 kg, isto é:

X1 + X2 ≥ 800

Considerando as quantidades de proteínas e de fibras que deve conter a ração

teremos:

A quantidade de proteína provenientes de Popcorn e Soja é igual a:

(0.09X1 + 0.6X2) kg

Esta quantidade deve ser igual a pelo menos 30% da mistura, isto é.

0.09X1 + 0.6X2 ≤ 0.05 (X1 + X2)

O mesmo raciocínio pode ser feito quanto a fibra:

0.02X1 + 0.06X2 ≤ 0.05 (X1 + X2)

Finalmente, o modelo do problema é escrito sob a seguinte forma:

Minimizar Z (Custo) = 0.3X1 + 0.9X2

X1 + X2 ≥ 800

-0.21X1 + 0.3X2 ≥ 0

-0.03X1 + 0.01X2 ≤ 0

X1; X2 ≥ 0

Prof. Eng.º MBUTA DOMPETELO Página 18

Material de Investigação Operacional
TEMA: II Programação Linear

EXERCÍCIOS RESOLVIDOS

1.7 Exercícios sobre construção do modelo de PL

EXERCÍCIO 1

1.7.1. Uma fábrica produz 2 produtos A e B. o consumo de H/M por unidade de

produto e o consumo de matérias-primas por unidade de produto é o seguinte:

Produto H/Máquina Unidade de Matéria-prima

A 2 3
B 1,5 2

As disponibilidades mensais são de 200 H/Máq e 300 unidade de matérias-

primas. Se o lucro por unidade de A for de 5kz e B de 4kz, quantas unidades de
A e B teremos de produzir para que o lucro total seja o máximo?

Solução

1º Definição das variáveis de decisão

A fábrica produz dois produtos, na mesma máquina e consome o mesmo tempo

de recurso, então temos como variáveis de decisão:

 X1: Unidade do produto A produzido mensalmente

 X2: Unidade do produto B produzido mensalmente

OBS: é importante observar que as disponibilidades dos recursos são dadas

mensalmente.

2º Condição de não negatividade

 X1; X2 ≥ 0 ou Xj ≥ 0 onde j=1,…2

Prof. Eng.º MBUTA DOMPETELO Página 19

Material de Investigação Operacional
TEMA: II Programação Linear

3º Construção do sistema de restrições

Deve-se considerar que o caracter limitado dos recursos H/Máquinas e Matérias-

primas, visto que temos um limite máximo de recursos disponível, então o sinal
das restrições será de sentido ≤

Depois devemos considerar as variáveis que consomem estes recursos e seus

respectivos coeficientes de consumo.

Recurso H/Máquina

Disponibilidade máxima 200H/Máquina

Variáveis que necessitam X1 e X2

Coeficientes de consumo 2 e 1,5

Então a restrição será:

2X1 + 1,5X2 ≤ 200

Recurso Matéria-prima

Disponibilidade máxima 300 Unidades de M-.P

Variáveis que necessitam X1 e X2

Coeficientes de consumo 3e2

Então a restrição será:

3X1 + 2X2 ≤ 300

4º Construção da função objectiva

É a soma dos lucros possíveis por cada actividade:

Prof. Eng.º MBUTA DOMPETELO Página 20

Material de Investigação Operacional
TEMA: II Programação Linear

 Produção do produto A proporciona um total de 5X1, onde 5 é o lucro

unitário de X1
 Produção do produto B proporciona um total de 4X2, onde 4 é o lucro
unitário de X2

O lucro total da empresa é a soma dos lucros totais da produção de X 1 e X2,

sendo o lucro a Função Objectiva de Maximização.

Max Z = 5X1 + 4X2

Finalmente o modelo matemático do problema será:

 X1: Unidade do produto A produzido mensalmente

 X2: Unidade do produto B produzido mensalmente

 Xj ≥ 0 onde j=1,…2

2X1 + 1,5X2 ≤ 200

3X1 + 2X2 ≤ 300

Max Z = 5X1 + 4X2

EXERCÍCIO 2

A MUCABA UEE fabrica 2 tipos de cintos; o cinto A, de alta qualidade, e o B

de baixa qualidade. O lucro respectivo por cinto é de 40 U.M. e 30 U.M., cada
cinto do tipo A necessita do dobro do tempo que o tipo B necessita e se todos os
cintos fossem do tipo B, a fábrica produziria 1000 unidades por dia.

O abastecimento em couro é apenas suficiente para 800 cintos diários (A e B

combinados). O cinto do tipo A exige uma fivela elegante cuja disponibilidade é
de 400 por dia.

Construa o modelo do problema.

Prof. Eng.º MBUTA DOMPETELO Página 21

Material de Investigação Operacional
TEMA: II Programação Linear

Solução

1º Definição das variáveis de decisão

A MUCABA produz dois tipos de cintos e as disponibilidades dos recursos são

diários.

 X1: Unidade de cinto do tipo A produzido diariamente

 X2: Unidade de cinto do tipo B produzido diariamente

2º Condição de não negatividade

 X1; X2 ≥ 0 ou Xj ≥ 0 onde j=1,…2

3º Construção do sistema de restrições

a) Disponibilidade em tempo para produção dos dois tipos de cintos:

 Se só se produzir cinto do tipo B:
X2 ≤ 1000

 Se só se produzir cintos do tipo A; como ele necessita o dobro do tempo

de B, isto significa que por dia só podemos produzir 500 cintos do tipo A.
X1 ≤ 500

Como por dia se deve produzir uma certa proporção dos dois tipos de cintos e
respeitando os custos de produção;

Quando X1 =0 ^ X2 =1000 e X1 =500 ^ X2 =0

Temos a restrição:

2X1 + X2 ≤ 1000

b) Disponibilidade em couro:

X1 + X2 ≤ 800

Prof. Eng.º MBUTA DOMPETELO Página 22

Material de Investigação Operacional
TEMA: II Programação Linear

c) Disponibilidade em fivelas:
X1 ≤ 400

X2 ≤ 700

4º Construção da função objectiva

A função objectiva é de maximizar o lucro total, que é a soma dos lucros

parciais (40X1 e 30X2)

Max Z = 40X1 + 30X2

O modelo matemático será:

Max Z = 40X1 + 30X2

2X1 + X2 ≤ 1000

X1 + X2 ≤ 800

X1 ≤ 400

X2 ≤ 700

X1; X2 ≥ 0 ou Xj ≥ 0 onde j=1,…2

EXERCÍCIO 3

Um fabricante de móveis deseja determinar quantas mesas, cadeiras, secretárias

e estantes deve fabricar com o objectivo de optimizar os recursos disponíveis. O
seu programa de vendas é de acordo com a procura interior, implica a
necessidade de produzir pelo menos 40 mesas, 130 cadeiras, 30 secretárias e não
mais de 10 estantes. Nestes produtos utilizam-se necessariamente dois tipos
diferentes de madeiras, cuja disponibilidade é de 1500m3 de madeira do tipo 1 e
250 m3 de madeira do tipo 2.

Prof. Eng.º MBUTA DOMPETELO Página 23

Material de Investigação Operacional
TEMA: II Programação Linear

Relativamente à madeira do tipo 1, cada artigo requer respectivamente 5, 1, 9 e

12m3. Em relação ao segundo tipo, cada metro cubico permite produzir 2 mesas
ou 3 cadeiras ou 4 secretárias ou 1 estante. Uma mesa requer 3H-H para ser
fabricada, uma cadeira 2 H-H, uma secretária 5H-H e uma estante 10H-H. Para
todo o trabalho conta-se com uma disponibilidade de 800H-H.

O fabricante obtém como lucro o seguinte: 12U.M. por cada mesa, 5U.M. por
cada cadeira, 15U.M. por cada secretária e 10U.M. por cada estante.

Encontre o modelo do problema sabendo que o objectivo é maximizar o lucro.

Solução

1º Definição das variáveis de decisão

Na definição das variáveis de decisão é importante determinar as actividades da

empresa. Estas actividades devem ser definidas conceptualmente e dimensional
mente.

Quando o problema presume um certo grau dificuldade na definição das

variáveis de decisão é importante observar como está definida a função
objectivo ou a partir das quais actividades da empresa atinge o seu objectivo que
pode ser de maximização ou minimização.

Assim será:

 X1: Unidade de mesas a produzir;

 X2: Unidade de cadeiras a produzir;
 X3: Unidade de secretárias a produzir;
 X4: Unidade de estantes a produzir.

Prof. Eng.º MBUTA DOMPETELO Página 24

Material de Investigação Operacional
TEMA: II Programação Linear

Neste exercício como na produção não tem diversidade de origens, de estrutura

tecnológica nem de coeficiente económico. Assim só podemos definir uma
variável por cada actividade.

2º Condição de não negatividade

 Xj ≥ 0 onde j=1,…4

3º Construção do sistema de restrições

Pode-se constatar que existe restrições ligados a procura, matérias-primas e

Horas-Homem (H-H).

a) Restrições de Procura
X1 ≥ 40 mesas (procura mínima)
X2 ≥ 130 cadeiras ( ll )
X3 ≥ 30 secretárias ( ll )
X4 ≤ 10estantes ( Procura máxima)

b) Restrição de matéria-prima

As disponibilidades de matéria-prima, têm de ser utilizadas em todos os

produtos e as disponibilidades cada uma separada, madeira do tipo 1 e madeira
do tipo 2; será necessárias duas restrições.

Para a madeira do tipo 1 a restrição será:

5X1 + X2 + 9X3 + 12X4 ≤ 1500m2- madeira do tipo 1

 A dimensão de b1 é a madeira do tipo 1 que é a limitação

 O sentido da restrição é ≤, se trata de uma disponibilidade máxima.

Quando se especifica uma disponibilidade que deve ser utilizada na totalidade, o

seu sinal será de igual (=).
Prof. Eng.º MBUTA DOMPETELO Página 25
Material de Investigação Operacional
TEMA: II Programação Linear

 Quais as actividades que utilizam este recurso? São todas as variáveis. Os

coeficientes de consumo aij são definidos como:
Madeira do tipo 1→ unidade de produto

Para a madeira do tipo 2 temos os seguintes requisitos:

 2 Mesas tipo m3 de madeira tipo 2, isto implicam que uma mesa será
1/2m3 de madeira do tipo 2.
Com o mesmo raciocínio temos:
 3 Cadeiras será 1/3m3
 4 Secretárias será 1/4m3
 1 Estante será 1m3

Com relação a este recurso temos a restrição:

X1/2 + X2 /3 + X3/4 + X4 ≤ 250

Restrições de Homem-Hora

A restrição é do mesmo tipo que a restrição da madeira do tipo 1.

3X1 + 2X2 + 5X3 + 10X4 ≤ 800

4º Construção da função objectiva

O objectivo é maximizar o lucro total que será a soma dos lucros de cada
actividade:

Max Z = 12X1 +5 X2 + 15X3 + 10X4

Finalmente o modelo matemático será:

 X1: Unidade de mesas a produzir;

 X2: Unidade de cadeiras a produzir;
 X3: Unidade de secretárias a produzir;
 X4: Unidade de estantes a produzir.

Prof. Eng.º MBUTA DOMPETELO Página 26

Material de Investigação Operacional
TEMA: II Programação Linear

 Xj ≥ 0 onde j=1,…4

5X1 + X2 + 9X3 + 12X4 ≤ 1500m2

X1/2 + X2 /3 + X3/4 + X4 ≤ 250
3X1 + 2X2 + 5X3 + 10X4 ≤ 800

Max Z = 12X1 +5X2 + 15X3 + 10X4

EXERCÍCIO 4

Uma fabricante está a planear a última semana de produção de consolas de

madeiras para televisores (I, II, III e IV). A fabricação de cada consola começa
com a montagem, a que se segue o acabamento. Cada unidade dos referidos
modelos requer, respectivamente, 4, 5, 3 e 5 horas para montagem e 2, 1,5 e 3
horas para o acabamento.
Os lucros unitários associados a cada um dos modelos são, respectivamente
iguais a 7, 7. 6 e 9 u.m. O fabricante dispõe de 750 trabalhadores na linha de
montagem, a trabalharem 40 horas por semana e 500 trabalhadores na linha de
acabamento, também com 40 horas de trabalho por semana. Para atender um
certo número de clientes, interessados em televisores de potência maior, as
consolas II e III podem ser enviadas à África do Sul, para o acabamento o que
reduz o lucro obtido nesses modelos em 20% para o modelo II e 15% para o
modelo III.
Para evitar desperdícios de matéria-prima e maximizar o trabalho de
acabamento, o fabricante deve produzir no mínimo 475 consolas do modelo I,
560 do modelo II, 680 do modelo III e 876 do modelo IV. Por causa dos custos
de transportação para Angola e a partir da África do Sul, não podem ser
produzidos mais de 500 consolas do modelo II e 750 do modelo III. O fabricante
pretende saber quantas unidades de cada modelo deverá fabricar durante a

Prof. Eng.º MBUTA DOMPETELO Página 27

Material de Investigação Operacional
TEMA: II Programação Linear

última semana de produção, de modo a maximizar os seus lucros, assumindo

que todas as unidades fabricandas serão vendidas.
Ajude o fabricante a construir o modelo de PL que lhe permita maximizar os
seus lucros.

Solução

1º Definição das variáveis de decisão

É importante reparar que durante o declinar do problema, que o processo passa

pela montagem e acabamento, este último pode ser feito em Angola ou África
do Sul. Isto implica diversidade do processo tecnológico. Da mesma forma a
leitura da forma como os lucros são especificados, implica a diversidade de
coeficientes económicos. Dai é importante distinguir os produtos acabados em
Angola e os produtos acabados na África do Sul.

X1: Consolas do modelo I produzidos na última semana;

X2: Consolas do modelo II produzidos na última semana acabada em Angola;
X3: Consolas do modelo II produzidos na última semana acabadas na África
do Sul;
X4: Consolas do modelo III produzidos na última semana acabadas em
Angola;
X5: Consolas do modelo I produzidos na última semana acabadas na África do
Sul;
X6: Consolas do modelo IV produzidos na última semana.

2º Condição de não negatividade

 Xj ≥ 0 onde j=1,…6

Prof. Eng.º MBUTA DOMPETELO Página 28

Material de Investigação Operacional
TEMA: II Programação Linear

3º Construção do sistema de restrições

a) Limitação de horas disponíveis para montagem.

4X1 + 5 (X2 + X3) + 3 (X4 + X5) + 5X6 ≤ 40

b) Limitação de horas disponíveis para acabamento

2X1 + X2 + 5X4 + 3X6 ≤ 40

c) Minimização de desperdícios

X1 ≥ 475
X1 + X3 ≥ 560
X4 + X5 ≥ 680
X6 ≥ 876
X3 ≤ 500
X5 ≤ 750

4º Construção da função objectiva

Max Z = 7X1 + 7X2 + (7 - 1,4) X3 + 6X4 + (6 - 0,9) X5 + 9X6

EXERCÍCIO 5

A empresa MOTORES ANGOLA, Lda. Fabrica dois tipos diferentes de motores

eléctricos para vender sob contrato à FRIANGOLA, fabricante de equipamentos
de cozinha. O modelo GM3A é utilizado em vários equipamentos de preparação
de alimentos, enquanto o modelo GM3B, é utilizado nos misturadores.

Três vezes ao ano, o serviço de compras da FRIANGOLA contactam a

MOTORES ANGOLA para fazer a encomenda mensal relativa aos 4 meses

Prof. Eng.º MBUTA DOMPETELO Página 29

Material de Investigação Operacional
TEMA: II Programação Linear

seguintes. As encomendas mensais variam todos os meses, em função das suas

vendas planificadas, da capacidade se produção e da situação financeira. A
MOTORES ANGOLA, Lda. Acaba de receber a encomenda de Janeiro-Abril e
deve iniciar o seu plano de produção para esses quatros meses. A procura dos
motores é dada na tabela seguinte:

Modelo Janeiro Fevereiro Março Abril

GM3A 800 700 1000 1100

GM3B 1000 1200 1400 1400

A planificação da produção na MOTORES ANGOLA, Lda. Deve considerar os

seguintes factores:

 A necessidade de produzir todos os meses o mesmo número de cada tipo

de motor, para simplificar a planificação dos trabalhadores e das
máquinas.
 A necessidade de manter mais baixo o custo das existências (sem
armazenagem), o que pressupõe produzir mensalmente apenas o
solicitado.
 A limitação de espaço no armazém que pode provocar custos adicionais
de stockgem.
 Os custos de produção que são geralmente da ordem dos 10$ por cada
motor GM3A produzido e 6$ por cada unidade de GM3B. Devido à
situação geral do mercado, esses custos aumentam em 10%, a partir do
mês de Março.
 Cada motor não vendido acarreta o custo seguinte 0,18$ para o GM3A e
0,13$ para o GM3B.
 Admite-se que a empresa inicia a sua produção em Janeiro, sem produção
antiga no stock e que no fim do mês de Abril fica com um stock de 450 e
300 motores, respectivamente, de GM3A e GM3B.

Prof. Eng.º MBUTA DOMPETELO Página 30

Material de Investigação Operacional
TEMA: II Programação Linear

 A capacidade de armazenagem permite armazenar no máximo 3300

motores dos dois modelos.
 A empresa dispõe de 2240 horas por mês e caso a necessidade o
justifique, ela pode utilizar dois trabalhadores reformados, elevando a
2560 a disponibilidade em horas.
 Cada motor do tipo GM3A produzido necessita de 1,3 horas e cada motor
GM3B de 0,9 horas.

Encontre o modelo que representa a situação da MOTORES ANGOLA, Lda.

Solução

1º Definição das variáveis de decisão

O problema diz que a empresa por cada tipo de motor tem a produção mensal a
considerar.
Por outro lado temos os estoques existentes no armazém no fim da venda de
cada mês.

 XAi: Unidade de motor modelo GM3A produzido no mês i (i=1, 2,..,4

=Janeiro……….. Abril);
 XBi: Unidade de motor modelo GM3B produzido no mês i (i=1, 2,..,4
=Janeiro………..Abril).
(XA1, XA2, XA3, XA4; XB1, XB2, XB3, XB4)

Estoque existente no fim do mês

(SA1, SA2, SA3, SA4; SB1, SB2, SB3, SB4)

Unidades de motores dos tipos A e B existentes no armazém no final de Janeiro-

fim de Abril.

Prof. Eng.º MBUTA DOMPETELO Página 31

Material de Investigação Operacional
TEMA: II Programação Linear

2º Condição de não negatividade

 Xj ≥ 0 onde j=1,…16

3º Construção do sistema de restrições

a) Relação que existe entre a produção do mês, o resto do mês passado, a

venda do mês e o resto do mês pode ser escrito na forma seguinte:

Estoque fim do mês = (estoque fim do mês anterior) + (produção do mês) –

(venda do mês)

Janeiro:

 A→ SA1= 0 + XA1 – 800 → XA1 - SA1 = 800

 B→ SB1= 0 + XB1 – 1000 → XB1 – SB1 = 1000

Fevereiro:

 A→ SA2= 0 + XA2 – 700 → XA2 - SA2 = 700

 B→ SB2= 0 + XB2 – 1200 → XB2 – SB2 = 1200

Março:

 A→ SA3= 0 + XA3 – 1000 → XA3 - SA3 = 1000

 B→ SB3= 0 + XB3 – 1400 → XB3 – SB3 = 1400

Abril:

 A→ SA4= 0 + XA4 – 1100 → XA4 - SA4 = 1100

 B→ SB4= 0 + XB4 – 1400 → XB4 – SB4 = 1400

No fim de Abril: estoque restante

 SA4 = 450
 SB4 = 300
Prof. Eng.º MBUTA DOMPETELO Página 32
Material de Investigação Operacional
TEMA: II Programação Linear

Estas restrições são ligadas a procura.

Disponibilidades do armazém

 SA1 + SB1 ≤ 3300

 SA2 + SB2 ≤ 3300

 SA3 + SB3 ≤ 3300

 SA4 + SB4 ≤ 3300

Capacidade de armazenagem dos produtos não vendidos no fim do mês.

Disponibilidade de tempo de trabalho por mês:

Janeiro:

 1,3XA1 + 0,9XB1 ≥ 2240

 1,3XA1 + 0,9XB1 ≤ 2560

Fevereiro:

 1,3XA2 + 0,9XB2 ≥ 2240

 1,3XA2 + 0,9XB2 ≤ 2560

Março:

 1,3XA3 + 0,9XB3 ≥ 2240

 1,3XA3 + 0,9XB3 ≤ 2560

Abril:

 1,3XA4 + 0,9XB4 ≥ 2240

 1,3XA4 + 0,9XB4 ≤ 2560

Prof. Eng.º MBUTA DOMPETELO Página 33

Material de Investigação Operacional
TEMA: II Programação Linear

4º Função objectiva

A função objectiva tem dois componentes, custo de produção dos motores e

custo de armazenamento no fim de cada mês dos motores não vendidos.

Max Z = 10XA1 +10XA2 + 11XA3 + 11XA4 + 6XB1 + 6XB2 + 6,6XB3 + 6,6XB4 +

0,18SA1 + 0,18SA2 + 0,18SA3 + 0,18SA4 +0,13SB1 + 0,13SB2 + 0,13SA3 + 0,13SB4

EXERCÍCIO 6

Um fabricante de automóveis miniaturas produz três tipos de automóveis A, B e

C que requerem, como acabamento final uma pintura especial, para o que possui
duas máquinas (com produtividades diferentes), cada uma com uma capacidade
semestral de 120 horas de trabalho. O número de automóveis de cada tipo que
pode ser processado por hora em cada uma dessas máquinas é dado no quadro
seguinte:

Unidade/hora Máquina 1 Máquina 2

Modelo A 40 36
Modelo B 42 30
Modelo C 24 15

Os custos por horas de processamento são de 4,2$ para a máquina 1 é de 3,60$

para máquina.

Por seu turno, os custos da matéria-prima por cada automóvel A e B produzidos

são de 0,40$, e de 0,80$ para o C; os preços de venda de cada unidade A, B e C
são, respectivamente, 1,1$, 1,00$ e 1,50$.

Por razões comerciais, foram impostos limites inferiores e superiores de

produção semanal para cada tipo de carro: A – entre 2150 á 2800; B – entre 700
á 950; e C – entre 350 á 450.

Formule o problema de PL que permite maximizar os lucros do fabricante.

Prof. Eng.º MBUTA DOMPETELO Página 34

Material de Investigação Operacional
TEMA: II Programação Linear

Solução

1º Definição das variáveis de decisão

Na definição das variáveis de decisão é importante considerar a diversidade de

tecnologia devido ao facto de que o acabamento final é feito em duas máquinas
diferentes com qualidades diferentes. Isto implica que teremos 6 variáveis e não
3.

 X1: Produção de modelo A acabada na máquina I

 X2: Produção de modelo A acabada na máquina II
 X3: Produção de modelo B acabada na máquina I
 X4: Produção de modelo B acabada na máquina II
 X5: Produção de modelo C acabada na máquina I
 X6: Produção de modelo C acabada na máquina II

2º Condição de não negatividade

 Xj ≥ 0 onde j=1,…16

3º Construção do sistema de restrições

a) Limitação da hora disponível por cada máquina

X1/40 + X3 /42 + X5/24 ≤ 120 Máquina I

X2/36 + X4 /30 + X6/15 ≤ 120 Máquina II

b) Limitação do mercado

2150 ≤ X1 + X2 ≤ 2800

Prof. Eng.º MBUTA DOMPETELO Página 35

Material de Investigação Operacional
TEMA: II Programação Linear

700 ≤ X3 + X4 ≤ 950

350 ≤ X5 + X6 ≤ 450

4º Função objectiva

Max Z = Receita - Custo

Receitas:

1,1X1 + 1,1X2 + 1 (X3 + X4) + 1,5 (X5 + X5)

Custos de processamento:

Método de cálculo:

Ex. Modelo A→ Máquina I

40 Unidades → 1 hora
1 Unidade → 1/ 40 hora
X1 unidades → X1/ 40 horas

Custo total:

 X1 → 4,2* X1 /40
 X2 → 3,6* X2 /36
 X3 → 4,2* X3 /30
 X4 → 3,6* X4 /24
 X5 → 4,2* X5 /24
 X6 → 3,6* X6 /15

Custo total de processamento

(4,2/40* X1 + 3,6/36* X2 +4,2/42* X3 + 3,6/30* X4 + 4,2/24* X5 + 3,6/15* X6)

0,11X1 + 0,1X2 + 0,1X3 + 0,12X4 + 0,18X5 + 0,24X6

Prof. Eng.º MBUTA DOMPETELO Página 36

Material de Investigação Operacional
TEMA: II Programação Linear

Custo de matérias-primas

0,4X1 + 0,4X2 + 0,4X3 + 0,4X4 + 0,8X5 + 0,8X6

Custo total de fabricação

0,51X1 + 0,5X2 + 0,5X3 + 0,52X4 + 0,98X5 + 1,04X6

Logo temos:

Max Z = 0,59X1 + 0,6X2 + 0,5X3 + 0,48X4 + 0,52X5 + 0,46X6

EXERCÍCIO 7

Uma fábrica de Auto ligeiros e Auto pesados, com os seguintes departamentos:

I. Montagem de motores
II. Estampagem de chaparia
III. Montagem de Auto ligeiros
IV. Montagem de auto pesados.

O departamento I pode montar 33.300 motores de auto ligeiros ou 16.700

motores de auto pesados ou as correspondentes combinações de motores entre
os dois veículos, sempre e quando não excede a sua capacidade.
Cada A.L leva 2 chapas e cada A.P leva 3 chapas.
O departamento III monta 22.500 A.L e o departamento IV 15 A.P.
Cada A.L proporciona um lucro de 300$ e cada A.P 250$.
Qual é o número de A.L e A.P a produzir de modo a maximizar o lucro.

Solução

1º Definição das variáveis de decisão

Neste caso só existem duas variáveis de decisão, A.L e A.P.

 X1: A.L Produzido

Prof. Eng.º MBUTA DOMPETELO Página 37

Material de Investigação Operacional
TEMA: II Programação Linear

 X2: A.P Produzido

2º Condição de não negatividade

 Xj ≥ 0 onde j=1…2

3º Construção do sistema de restrições

Departamento I:

A capacidade não esta dada em quantidade de recurso, somente em unidades de

produtos. Neste departamento serão montados motores de A.L e A.P. é
necessário encontrar uma unidade comum que permita adicionar A.L c/ A.P.

Neste caso o único factor presente em ambos é que eles utilizam parte da
capacidade.

A.L + A.P ≤ Capacidade de motores

Os aij são definidos:

[Capacidade em motores/A.L] e [Capacidade em motores/A.P]

Assumimos que a capacidade é igual a unidade, podemos encontrar a parte que

se utiliza para A.L e a parte A.P.

Se a capacidade total for dedicada a A.L, a quantidade a produzir será de 3.300,

cada motor de A.L consumida 1/33.300, partes de cada capacidade e o mesmo
para A.P.

Assim a restrição será:

1/33.300X1 + 1/16.700X2 ≤ 1

Departamento II:

A restrição tem a mesma analogia que o Departamento I, mas tem que ter em
conta a quantidade de chapas que cada produto consome:
Prof. Eng.º MBUTA DOMPETELO Página 38
Material de Investigação Operacional
TEMA: II Programação Linear

[Capacidade em motores/A.L] (A.L) + [Capacidade em motores/A.P] (A.P)

≤ Capacidade de chapas

2/25.000X1 + 3/30.000X2 ≤ 1

Departamento III e IV:

A capacidade é dada em unidades de produtos, mas em cada departamento

intervém só uma unidade:

X1 ≤ 22.500

X2 ≤ 15.000

4º Função objectiva

Max Z = 300X1 + 250X2

Prof. Eng.º MBUTA DOMPETELO Página 39

 Material de Investigação Operacional
TEMA: II Programação Linear

EXERCÍCIOS PROPOSTOS

1. Uma empresa tem três fábricas que produzem um mesmo tipo de produto cujas
capacidades mensais excedem as 320, 120 e 200 toneladas métricas.

Este produto serve, por sua vez, como matéria-prima em quatro centros
produtivos onde as necessidades mensais são 200, 100, 120 e 170 T.M.

Os custos unitários de transporte de cada fábrica a cada centro produtivo são os

seguintes:

Fab/C. Prod. A B C D
L 5 7 6 5
LI 5 2 3 4
LII 3 4 8 3

Sabe-se que:

a) A fábrica II tem que distribuir totalmente a sua produção.

b) A fábrica III tem que distribuir necessariamente um mínimo de 120 T.M.
Construa o modelo matemático do referido problema.

2. Uma empresa fabrica três produtos A, B e C, cujas procuras nacionais e anuais

devem ser satisfeitas e atinge o seguinte nível: 150.000, 230.000 e 80.000 latas,
respectivamente.

Para fabricar estes produtos pode-se utilizar dois tipos de matérias-primas (I e

II), sendo a primeira de produção nacional e a segunda importada. A produção
nacional anual de matéria-prima I é de 130.000 kgs. A matéria-prima importada
não esta limitada em qualidade e quantidade e tem um custo em divisa de
2USD/kg.

A tabela seguinte mostra o consumo em kg de matéria-prima I e II, para a

produção de uma lata de cada produto.

Prof. Eng.º MBUTA DOMPETELO Página 40

Material de Investigação Operacional
TEMA: II Programação Linear

Matéria-prima Produtos
A B C
I 1/3 1/2 1
II 1/2 1 1/3

A capacidade máxima de enlatar desta empresa é de 300.000 latas/ano, a

procura não satisfeita pela produção nacional deve sê-lo pela importação, sendo
os preços de importação em divisas de 1, 1.5, 2.5 U$ por lata de A, B e C,
respectivamente.

Encontre o modelo do problema sabendo que o nosso objectivo é minimizar o

custo total em divisas para a satisfação da procura nacional.

3. Uma fábrica produz dois tipos de produtos, a partir de duas matérias-primas

principais, disponíveis em quantidades limitadas. O produto 1 é vendido a 0.70$
por unidade e o produto 2 é vendido a 0.60$ também por unidade, sendo os
encargos variáveis (unitários) iguais, respectivamente, a 0.14$ e 0.18$. por
exigência do mercado a produção máxima do produto 1, não deve exceder
110.000 unidades anuais. As quantidades de matérias-primas disponíveis
anualmente são respectivamente de 240.000 e 180.000, e o quadro tecnológico
de transformação das matérias-primas é o seguinte:

Matéria-prima Produto I Produto II

MPI 1 2
MPII 1,5 1

Sendo o objectivo da fábrica maximizar os lucros obtidos num ano, elabore um

modelo linear que corresponde a este objectivo, atendendo as restrições
existentes.

Prof. Eng.º MBUTA DOMPETELO Página 41

 Material de Investigação Operacional
TEMA: II Programação Linear

a) Represente o problema graficamente e determine o número de

unidades de cada um dos produtos a serem vendidos, respeitando os
pressupostos da alinha a).

Sugestão: utilizar para b), papel milimétrico e ensaiar diversas soluções básicas
possíveis obtendo os correspondentes valores da função objectiva.

4. O Jumbo dedica-se ao comércio de bens de consumo e tendo em conta as

limitações abaixo indicadas, deve determinar o volume óptimo de importação de
camisas para o próximo período de modo a responder às necessidades
planificadas com uma gestão de gastos mínimos.

De acordo com o histórico de mercado, a mercadoria a importar deve ser

originária de França e U.S.A.

As camisas para rapazes e raparigas podem ser compradas em qualquer dos

países, mas as camisas para adultos apenas poderão ser adquiridas nos U.S.A.

Nos contratos celebrados pelos dois países estabelece que tanto a embalagem
como os gastos de transportação é responsabilidade do Jumbo.

O Jumbo dispõe de 55 toneladas de cartão para embalagem e o consomo deste

material por unidade de camisa é de 0.2, 0.19, 0.15 kg para camisa de rapazes,
raparigas e adultos, respectivamente.

O Jumbo imputa no seu orçamento 5.000 unidades para gastos de transportação

e o custo de transportação é de 5; 3 e 2 unidades monetárias por lotes de 100
unidades, para camisas de rapazes, raparigas e adultos, respectivamente.

A compra de camisas para rapazes deve ser pelo menos 15.000 unidades e para
satisfazer as necessidades mínimas, a quantidade de camisas para adultos não
deve ser superior a terça parte da quantidade de camisas adquiridas para
raparigas.

Prof. Eng.º MBUTA DOMPETELO Página 42

 Material de Investigação Operacional
TEMA: II Programação Linear

Para o período que se planifica a entrega, o Jumbo dispõe de um armazém que

permite a recepção de 25.000 camisas para rapazes ou 40.000 para raparigas ou
50.000 para adultos.

Os custos são os seguintes:

Camisas França U.S.A

Rapazes 15 20
Raparigas 10 8
Adultos 5 5

Encontre o modelo de gestão do Jumbo.

5. A Moveis, Lda. Produz mesas e cadeiras populares (a preço do povo). O

processo de produção é similar para mesas como cadeiras e re querem um certo
número de horas de carpintaria e um certo número de horas de trabalho no
departamento de pintura e vernizagem. Por enquanto cada cadeira requer 3 horas
na carpintaria e 1 hora na pintura e vernizagem. Durante este período de
produção, 240 horas de carpintaria e 100 horas, são as disponibilidades,
respectivamente.

Cada mesa vendida tem um lucro de 70$, cada cadeira vendida tem um lucro de
50$.

O problema da Moveis, Lda. É de determinar a melhor combinação de mesas e

cadeiras a fabricar, de modo a atingir o máximo de lucro.

6. A Direcção de Marketing de uma empresa mobiliaria 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 que aconselha que a produção mensal de secretárias não
ultrapasse 160 unidades.

Após estudos levados a cabo pela Direcção de Produção, conclui-se que:

Prof. Eng.º MBUTA DOMPETELO Página 43
 Material de Investigação Operacional
TEMA: II Programação Linear

- 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 e 4 H-H de acabamento.

Por outro lado, as margens brutas unitárias estimadas são de 3.000$ para as
secretárias e 2.000$ para as estantes.

A empresa pretende determinar o plano de produção mensal para estes novos

modelos que maximiza a margem bruta.

7. Uma empresa se dedica na elaboração de três tipos de produtos: A, B e C, e

deseja elaborar a sua estrutura de produção para o próximo período de forma a
maximizar o seu lucro total, tomando em consideração as limitações seguintes:

Para a elaboração do plano de produção a empresa deve tomar em conta a

procura nacional destes produtos que são de pelo menos 50 unidades de produto
A, pelo menos 350 unidades do produto B e com o máximo de 300 unidades de
C.

A demais deve considerar a possibilidade de exportação dos produtos A e B.

Neste caso a produção dos produtos exportados não deve ultrapassar a terça
parte da produção total destes produtos.

Para a elaboração destes produtos utiliza-se mensalmente uma matéria-prima

cuja disponibilidade para este período é de 50 toneladas, que deve ser utilizada
totalmente.

Com 1kg desta matéria-prima pode-se elaborar 1/3 unidade de A, ou ¼ unidade

de B, ou 1/2 unidade de C.

A partir da produção de C, obtém-se sem gasto adicional um produto D a razão

de 2 unidades de subprodutos por cada unidade elaborada de C. tanto o

Prof. Eng.º MBUTA DOMPETELO Página 44

 Material de Investigação Operacional
TEMA: II Programação Linear

subproduto D como o produto C requer um certo adicionamento de

armazenagem. Este armazém dispõe de uma capacidade que permite conservar
350 unidade de C ou 350 unidades de D ou correspondente a combinação destes
dois produtos.

O lucro unitário associado a estes produtos é de 6, 7, 4 e 1, respectivamente,

para A, B, C e D.

Se os lucros destes produtos aumentam a 50% no caso da exportação, pode-se

construir o modelo que optimiza a gestão da empresa.

8. Uma fábrica de automóveis que produz dois tipos de viaturas, automóveis de

turismo e carrinhas utilitárias, e está organizada em quatro departamentos:
Carroçarias, Motores de automóveis de turismo e Montagem de carrinhas
utilitárias.
O Departamento de fabrico de carroçarias pode produzir 7.500 carroçarias para
automóveis ou 10.500 carroçarias para carrinhas por mês, ou uma «Combinação
equivalente». Uma «Combinação equivalente» pode ser, por exemplo, 4.500
carroçarias para automóveis (60% da capacidade) e 4.200 carroçarias (40% de
capacidade), para carrinhas.
Analogamente, o Departamento de fabrico de motores pode produzir 10.000
motores para automóveis ou 5.000 para carrinhas por mês, ou uma
«Combinação equivalente» (combinação que não exceda 100% de sua
capacidade). O Departamento de montagem tem a capacidade para dar saída a
6.750 e 4.500 viaturas mês, de automóveis de turismo e carrinhas utilitárias,
respectivamente.
O problema que a Direcção da fábrica pretende ver resolvido consiste em
determinar quantos automóveis de turismo e quantas carrinhas utilitárias deve
produzir por mês, não excedendo a sua capacidade produtiva.

Prof. Eng.º MBUTA DOMPETELO Página 45

Material de Investigação Operacional
TEMA: II Programação Linear

Para esse efeito, suponha-se ser de 150x10 U.M. a margem bruta unitária para os
automóveis de turismo (diferença entre o valor de venda de um automóvel de
turismo e o custo total das matérias-primas, trabalho e mais factores
directamente imputáveis) e de 200x10 U.M. a margem bruta unitária
relativamente as carrinhas utilitárias.

Quadro
Percentagem da capacidade dos vários departamentos necessários para produzir uma
unidade em cada actividade

Departamento ACTIVIDADES
Prod. Automóveis Prod. Carrinhas Utilitárias
Carroçarias .01333 .00952
Motores .01 .0
Montagem Automóveis 01481 -
Montagem Carrinhas - .02222

Prof. Eng.º MBUTA DOMPETELO Página 46