PROGRAMAÇÃO LINEAR 950 / 3

RESULTADOS DE APRENDIZAGEM
Quando você concluir este módulo, você deverá ser capaz de
(Formulação do problema)
. determine as restrições;
. encontrar uma função objetivo;
. declara um modelo de programação linear;
(Método gráfico)
. identificar uma região viável;
. determinar a solução ótima;
. identificar casos especiais: inviabilidade, soluções não limitadas e múltiplas soluções ótimas;
Método Simplex
. obtenha a forma padrão do simplex usando variáveis de folga e/ou excesso;
. construir tabelas simplex para um problema de maximização com no máximo três variáveis e
três restrições além das condições de não negatividade;
. determinar a solução otimizada.

Introdução

A Programação Linear é um ramo da matemática aplicada que lida com a resolução de otimização
problemas de uma forma particular. Um problema de programação linear envolve:
. maximizando ou minimizando uma função linear (conhecida como a função objetivo) consistindo
de um certo número de variáveis;
. um conjunto de restrições que pode ser representado por um sistema de desigualdades / equações lineares
das variáveis usadas na função objetivo.

Considere o seguinte problema enfrentado pelo homem:

Devo vender Ou devo vender

mais peras? mais maçãs?

Pêra Maçã
50 sen 70sen

Quais são os fatores que o homem deve considerar ao tomar sua decisão para fazer
lucro máximo?

Em um problema de programação linear, geralmente há infinitas soluções para o sistema de

restrições (chamadas de soluções viáveis). O objetivo é encontrar uma solução ótima que forneça o
valor máximo ou mínimo da função objetivo.

Existem duas abordagens para resolver um problema de programação linear:

. abordagem geométrica (o método gráfico) – limitado a 2 variáveis
. abordagem matricial (o método simplex) – pode ter mais de 2 variáveis

Compilado por: Goh PC 1

PROGRAMAÇÃO LINEAR 950 / 3
Formulação do Problema
A formulação do problema ou modelagem de um problema de programação linear consiste em indicar o
seguindo três características:

. variáveis – variáveis de decisão (ou independentes) e outras variáveis que dependem de

variáveis de decisão;
. restrições – escritas como um conjunto de desigualdades lineares e/ou equações em termos de decisão
variáveis com coeficientes apropriados;
. função objetivo - uma função linear em termos de variáveis de decisão com apropriado
coeficientes, que precisam ser maximizados ou minimizados.

Exemplo 1:
Uma fábrica produz tintas para interiores e exteriores para distribuição por atacado. Dois
matérias-primas básicas, A e B, são usadas para fabricar as tintas. A disponibilidade máxima de A
são 6 toneladas por dia; as de B são 8 toneladas por dia. As necessidades diárias de matérias-primas por tonelada de
as tintas de interior e exterior estão resumidas na tabela a seguir.

Toneladas de Matéria-Prima por Tonelada de Tinta Máximo

Interior Exterior Disponibilidade (toneladas)
Matéria-prima A 2 1 6
Matéria-prima B 1 2 8

Uma pesquisa de mercado estabeleceu que a demanda diária por tinta para interiores não pode exceder isso.
de tinta para exterior em mais de 1 tonelada. A pesquisa também mostra que a demanda máxima por
a tinta para interiores está limitada a 2 toneladas por dia.
The wholesale price per ton is RM2000 for interior paint and RM3000 for exterior paint.
Quantas tintas internas e externas a empresa deve produzir diariamente para maximizar o lucro bruto?
renda?

Uma breve descrição da situação acima é:

A empresa busca determinar as quantidades (em toneladas) de tintas internas e externas a serem
produzido para maximizar a receita bruta total, enquanto satisfaz as restrições de demanda e matéria-prima
uso de materiais.

Formulação do Problema
Variáveis:
a quantidade (em toneladas) de tinta para interiores a ser produzida diariamente
a quantidade (em toneladas) de tinta exterior a ser produzida diariamente
Restrições:
. Uso de matérias-primas máxima disponibilidade de matéria-prima
Matéria-prima A: 2x y 6
Matéria-prima B: x 2y 8
. A demanda por tinta para interiores supera a tinta para exteriores 1 tonelada
x y 1
. Demanda por tinta para interiores 2 toneladas
x 2
. Restrições de não negatividade: x 0 , y 0
Função objetivo:
Maximizez 2x 3y (em milhares de RM)

Compilado por: Goh PC 2

PROGRAMAÇÃO LINEAR 950 / 3
O problema de programação linear pode ser reformulado como

Maximizez 2x 3y
sujeito a
2x y 6
x 2y 8
x y 1
x 2
x 0
y 0

Exemplo 2:

Use o modelo do Exemplo 1, reescreva cada uma das restrições abaixo sob a estipulação
condições.
. A demanda diária por tinta para interiores excede a de tinta para exteriores em pelo menos 1 tonelada.

---------------------------------------------------------------------------------------------------
. O uso diário da matéria-prima A é de no máximo 6 toneladas e no mínimo 3 toneladas.

---------------------------------------------------------------------------------------------------
. A demanda por tinta interna não pode ser menor do que a demanda por tinta externa.

---------------------------------------------------------------------------------------------------

Exercício 1

1. Uma pequena fábrica de móveis fabrica mesas e cadeiras. Leva 2 horas para montar uma.
mesa e 30 minutos para montar uma cadeira. A montagem é realizada por quatro trabalhadores com base em
um único turno de 8 horas por dia. Os clientes normalmente compram pelo menos quatro cadeiras com cada mesa.
o preço de venda é RM150 por mesa e RM50 por cadeira.
Formule este problema como um problema de programação linear para maximizar o total diário
receita para a fábrica.

2. Uma empresa produz dois produtos, A e B. O volume de vendas do produto A é de pelo menos
60% das vendas totais dos dois produtos. Ambos os produtos utilizam a mesma matéria-prima, da qual o
a disponibilidade diária é limitada a 100 kg. Os produtos A e B utilizam esta matéria-prima nas taxas de 2 kg
por unidade e 4 kg por unidade, respectivamente. Os preços de venda dos produtos A e B são RM20 e
RM40 por unidade, respectivamente.
Formule este problema como um problema de programação linear para maximizar o total diário
renda.

Compilado por: Goh PC 3

PROGRAMAÇÃO LINEAR 950 / 3
3. Uma empresa farmacêutica realiza testes de novas pílulas em um rato. O rato recebe dois tipos
de pílulas, tipo I e tipo II, por dia. As pílulas contêm vitaminas A e B. A tabela abaixo mostra
as massas das vitaminas contidas em cada comprimido.

Tipo de ComprimidoMassa de vitamina A por cápsula Massa de vitamina B por comprimido

(mg) (mg)
Eu 6 3
II 11 1

O rato recebe pelo menos 10 pílulas por dia. O rato também requer pelo menos 66 mg de vitamina A e
pelo menos 12 mg de vitamina B por dia. O custo de cada tipo I de pílula é 50 sen e cada tipo II de pílula é 30
sen.
Formule este problema como um problema de programação linear para minimizar o custo de teste.

4. Uma empresa produz duas variedades de um produto. A Variedade A tem um lucro por unidade de RM2,00.
e a variedade B tem um lucro por unidade de RM3,00. A demanda pela variedade A é de no máximo quatro unidades por dia.
As restrições de produção são tais que no máximo 10 horas podem ser trabalhadas por dia. Uma unidade de variedade
A leva uma hora para produzir, mas uma unidade da variedade B leva duas horas para produzir. Dez metros quadrados
metros de espaço estão disponíveis para armazenar a produção de um dia e uma unidade da variedade A requer dois
metros quadrados enquanto uma unidade da variedade B requer um metro quadrado.
Formule este problema como um problema de programação linear para maximizar o lucro diário.

5. Um fabricante de cimento produz dois tipos de cimento, a saber, grânulos e pó.

não é possível fazer mais de 1600 bolsas por dia devido à falta de veículos para transportar o cimento.
do plantio. Um contrato de venda exige que ele produza pelo menos 500 sacos de cimento em pó
por dia. Ele está ainda mais restrito por uma falta de tempo - o cimento granulado requer o dobro de
muito tempo para fazer como o cimento em pó. Um saco de cimento em pó requer 0,24 minutos para
faz e a planta opera em um dia de 8 horas. Seu lucro é de RM4 por saco de cimento granulado e
RM3 por bolsa de cimento em pó.
Formule este problema como um problema de programação linear para maximizar o fabricante.
lucro.

Compilado por: Goh PC 4

PROGRAMAÇÃO LINEAR 950 / 3
Resolvendo um Problema de Programação Linear

( A) O Método Gráfico

O método gráfico pode ser usado para resolver um problema de programação linear com duas decisões
variáveis. Em um problema de programação linear, geralmente há infinitas soluções que
satisfaça todas as restrições simultaneamente.

O primeiro passo no método gráfico é traçar a região viável onde encontramos todas as viáveis.
soluções. Geometricamente, a região viável é o espaço de solução que consiste em todos os pontos que
satisfazer um sistema de desigualdades. Por uma solução para um problema de programação linear, entendemos encontrar
um ponto viável (x,y) juntamente com o valor da função objetivo naquele ponto, que
maximiza (ou minimiza) a função objetiva.

Encontrando a região viável:

1. As restrições de não negatividade 0andy 0confine todas as soluções viáveis para o

espaço acima ou no eixo x e à direita ou no eixo y.
2. A região viável é determinada substituindo primeiro o sinal de desigualdade por "=" para cada
restrição para produzir uma equação de linha reta. Cada linha reta é então plotada no cartesiano
plano, e a região na qual cada desigualdade se mantém é o espaço de solução resultante.

Exemplo 3:

Considere o modelo de programação linear no Exemplo 1.

As restrições são:
2x y 6
x 2y 8
x y 1
x 2
x 0
y 0
Reescreva cada restrição como uma equação linear e trace cada linha reta no plano cartesiano.
1 2x y 6 y
2 x 2y 8
3 x y 1 5
4 x 2 8

1
5 x 0(eixo y)
6 y 0(eixo-x) 6 6

4
5

4 4

3
3
2
2
1

x
0 1 2 3 8 6
-2 2 4 6 8 10 12 14

A direção de cada seta representa a desigualdade associada a cada linha reta.

o espaço de solução resultante é mostrado pela região sombreada. Ou seja, os pontos no interior e sobre
a borda da região sombreada é o conjunto de pontos que satisfazem todas as desigualdades de restrição.

Compilado por: Goh PC 5

PROGRAMAÇÃO LINEAR 950 / 3
Encontrando a solução ideal

O teorema fundamental da programação linear afirma que: O valor máximo (ou mínimo)
da função objetiva é alcançada em um dos vértices da região viável.

A solução ideal pode ser determinada observando a direção na qual o objetivo

função aumenta (para problema de maximização) ou a direção na qual a função objetivo
diminui (para problema de minimização).
Primeiro de tudo, uma linha de busca é traçada atribuindo um valor arbitrário à função objetivo. Para
determinar a solução ideal, obter uma família de linhas paralelas movendo a linha de busca
"para cima" para determinar a solução máxima, ou "para baixo" para determinar a solução mínima,
até o ponto em que qualquer movimento adicional sairia da região viável.

Exemplo 4: (Problema de maximização)

Considere a função objetivo no Exemplo 1:

Maximizar:z 2x 3y
2 z
Reescreva a equação como sy  x .
3 3
2
Escolha 6. Plote a linha reta 2x 3y 6ory  x 2 .
3
2 z 2
Alternativamente, obtenha o gradiente da linha y  x , que é  .
3 3 3
y interceptar
Compare o gradiente com a fórmula: gradiente =  .
x interceptar
Você pode traçar uma linha de busca com 2 e 3 como interceptos no eixo y e no eixo x, respectivamente.

y
2x y 6 8

Solução ideal
7

6 6

ocorre neste ponto

5

4 4
x y 1
3

2 2

1
x 2y 8
x
0 1 2 3 8
-2 2 4 6 8 10 12 quatorze

z 2x 3y
4 10
A solução ideal ocorre no ponto , .
3 3
1 1
Ou seja, a empresa deve produzir 1 toneladas de tinta para interiores, 3e toneladas de tinta exterior diariamente.
3 3
4 10
A renda bruta diária máxima da empresa = RM 2 3 × 1000
3 3
= RM12.666,67

Compilado por: Goh PC 6

PROGRAMAÇÃO LINEAR 950 / 3
Observe que a região viável de um problema de programação linear é um polígono convexo, se for
limitado. Assim, os valores máximo e mínimo de uma função objetivo ocorrem em
vértices, ou em todos os pontos de um segmento de linha delimitado da região viável.
Assim, uma maneira alternativa de encontrar uma solução ótima é avaliar a função objetivo em
cada um dos vértices da região viável, e então escolher um vértice no qual o valor do
a função é ótima.

Exemplo 5: (Problema de minimização)

Minimize a função objetivo

z x 5y
sujeito às restrições
x 4y 12
x 8
x y 2
x 0
y 0

3
x 4y 12 x 8
22

x
0 2 5 8 10 12
x y 2
z x 5y
Solução otimizada
ocorre neste ponto

A solução ótima é:
x = 2, y = 0 e z = 2.

Alternativamente, avalie a função objetivo em cada ponto de canto:

Ponto de esquina, (x,y) Valor de z x 5y

(0, 3) z 0  5(3) 15
(8, 1) z 8  5(1) 13
(8, 0) z 8  5(0) 8
(2, 0) z 2  5(0) 2
(0, 2) z 0  5(2) 10

O valor mínimo de z é 2 quando x = 2 e y = 0.

Compilado por: Goh PC 7

PROGRAMAÇÃO LINEAR 950 / 3
Todo problema de programação linear se enquadra em uma das quatro categorias:
. Tem uma solução ótima - se a solução ótima for alcançada em apenas um ponto viável.
. Possui múltiplas soluções ótimas - se a solução ótima for alcançada em cada ponto do
linha limite unindo dois vértices da região viável.
. Inviável - se uma solução viável para o problema de programação linear não existir.
. Soluções não limitadas - se as restrições não restringirem suficientemente o objetivo
função de modo que, para qualquer solução viável dada, outra solução viável possa ser encontrada
isso faz uma melhoria adicional na função objetiva.

Exercício 2

1 Dado um problema de programação linear

Maximizez 3x 2y
sujeito às restrições
x 2y 10
2x y 8
x 0
y 0
(a) Traçar a região viável.
(b) O problema de programação linear tem uma solução? Explique.

2. Dado um problema de programação linear

Minimizez 8x 8y
sujeito às restrições
x y 5
x y 15
x 10
y 10
x 0
y 0
(a) Grafique a região viável.
(b) Determine a solução ótima.

3. Determine a solução ideal para cada um dos problemas de programação linear no Exercício 1.

Compilado por: Goh PC 8

PROGRAMAÇÃO LINEAR 950 / 3
( B) O Método Simplex

O método simples nos permite resolver problemas que não podem ser resolvidos geometricamente (quando o
o número de variáveis aumenta para três ou mais). O método simplex resolve a programação linear
problemas em iterações onde os mesmos passos computacionais são repetidos várias vezes antes
a solução ótima é alcançada.

Vantagens do método simplex:

. Completamente mecânico (use matrizes, operações elementares de linha e aritmética básica).
. Pode resolver problemas de programação linear com qualquer número de variáveis e restrições.

Para usar o método simplex, o problema de programação linear deve estar na forma padrão.
. Para um problema de maximização, todas as restrições (exceto as condições de não negatividade),
são do tipo com lado direito não negativo.
. Para problemas de minimização, todas as restrições são do tipo com direito não negativo-
lado direito.
. Todas as variáveis são não negativas.
. A função objetivada pode ser maximização ou minimização.

O método simplex requer que todas as restrições sejam escritas na forma de equações.
Uma restrição do tipo ) pode( ser convertido em uma equação adicionando uma variável de folga a
(subtraindo uma variável de excedente do) lado esquerdo da restrição.

Por exemplo, na restrição

x 2y 6
adicionamos uma variável de slack, s1,
para o lado esquerdo para obter a equação
x 2y s1 6 , s1 0
Considere a restrição
3x 2y 3z 5
subtraímos uma variável de excedente, s2, do lado esquerdo para obter a equação
3x 2y 3z s2 5s2 0,

Exemplo 6:

Considere o problema de programação linear

MaximizeP 3x y
sujeito às restrições
2x y 8
2x 3y 12
x 0
y 0

Reescreva as restrições e a função objetivo na forma padrão.

2x y r 8
2x 3y s 12
 3x y P 0
onde x 0 .

Compilado por: Goh PC 9

PROGRAMAÇÃO LINEAR 950 / 3
Siga os passos do algoritmo simplex:

1. Configure a tabela simplex inicial.

Básico x y r s P Solução
r 2 1 1 0 0 8
s 2 3 0 1 0 12
P -3 -1 0 0 1 0

Indicadores
Tomamos como a solução básica viável inicial x 0 , y 0 , r 8s, 12, e assim
P 0. As variáveis definidas como zero (xandy) são chamadas de variáveis não básicas; as restantes
uns (randes) são chamados de variáveis básicas.

2. Procure o indicador mais negativo (-3 neste caso). Soxis selecionado como uma variável de entrada.
(torna-se variável básica). A coluna x é chamada de coluna pivô.

3. Encontre a razão( ) 0

Básico x Solução (Proporção)

r 2 8 (8 2 = 4)
Escolha o menor (4)
s 2 12 (12 2 = 6)

Assim, r será a variável de saída (tornar-se variável não básica). A linha r é chamada de pivô
linha, e "2" é chamado de elemento pivô.

4. Use operações elementares de linha para transformar o tableau em um novo tableau equivalente que
hasa "1" onde o elemento pivô estava e "0" em outros lugares naquela coluna.

Básico x y r s P Solução
r 2 1 1 0 0 8
s 2 3 0 1 0 12
P -3 -1 0 0 1 0
1
2 R1

Básico x y r s P Solução
x 1 1
2
1
2
0 0 4
s 2 3 0 1 0 12
P -3 -1 0 0 1 0
 2R1 R2 , 3R1 R3

Básico x y r s P Solução
x 1 1
2
1
2
0 0 4
s 0 2 -1 1 0 4
P 0 1
2
3
2
0 1 12

Todos os indicadores 0
Repita o processo até que todos os indicadores sejam não negativos. Então, Pis é ótimo.
Portanto, o valor máximo de P é 12 quando x 4andy 0 .
Compilado por: Goh PC 10
PROGRAMAÇÃO LINEAR 950 / 3
Exercício 3
1. Construa o tableau simplex inicial para o problema de programação linear.
Maximizar a função objetivo,
P 24x 15 anos
sujeito às restrições
3x 2 y 40
20x 10 anos 240
x 0
y 0

2. Dada a tabela simplex inicial como:

Básico x y r s t P Solução
r 1 1 1 0 0 0 20
s 2 1 0 1 0 0 35
t -3 1 0 0 1 0 doze
P -5 -4 0 0 0 1 0

a) Declare a solução básica viável inicial.

b) Identifique a coluna pivô, a linha pivô e, portanto, o elemento pivô.
c) Declare a variável de entrada e a variável de saída.

3. Use o seguinte tableau simplex inicial, encontre o valor máximo de P.

Básico x y r s P Solução
r 3 4 1 0 0 12
s 5 2 0 1 0 cinco
P -9 -12 0 0 1 0

4. Encontre a solução ótima para o problema de programação linear.

Maximizez 4x 1 x2 x3
sujeito às restrições
3x1 x 2 x3 4
x 1  x 2 x 3 2
x1 ,x2,x3 0

5. Uma empresa fabrica dois modelos do mesmo produto e a parte final do

o processo de fabricação consiste em operações de montagem e polimento. Para cada modelo, o tempo
(em horas) necessárias para cada operação estão mostradas abaixo, juntamente com o lucro por unidade vendida.

Montagem Polimento Lucro (RM)

Modelo 1 7 5 500
Modelo 2 4 2 250

Dada a situação atual da força de trabalho, a empresa estima que a cada mês eles têm
110 horas de tempo de montagem e 70 horas de tempo de polimento disponíveis.
Use o método simplex, determine o número de unidades de cada modelo que a empresa
deve fazer por mês para maximizar o lucro. Portanto, encontre o lucro máximo.

Compilado por: Goh PC 11

PROGRAMAÇÃO LINEAR 950 / 3
Problemas de Revisão

1 Resolva o seguinte problema de programação linear usando o método gráfico.

Minimizar: K 4x 5y
Sujeito a: 2x 3y 12
5x y 10
x y 5
x 0,y 0

2. Uma fábrica de grãos de café deseja embalar no máximo 1000 kg de grãos de café em pacotes de 1 kg.
e pacotes de 2 kg toda semana. O número de pacotes de 1 kg não deve ser mais do que o dobro do
número de pacotes de 2 kg e a fábrica deve produzir pelo menos 500 pacotes de grãos de café a cada
semana. O lucro de um pacote de 1 kg é RM2,00 e um pacote de 2 kg é RM3,50.
(a) Formule o problema como um modelo de programação linear para encontrar o número de 1 kg
pacotes e pacotes de 2 kg que a fábrica deve produzir para maximizar o lucro.
(b) Usando o método gráfico, mostre a região viável e resolva a programação linear
problema.

3. Um jardim requer pelo menos 6, 12 e 10 unidades de nutrientes A, B e C, respectivamente. Uma garrafa

do fertilizante líquido contém 1, 4 e 1 unidades de nutrientes A, B e C, respectivamente. Um saco de seco
o fertilizante contém 1, 1 e 5 unidades dos nutrientes A, B e C, respectivamente. Suponha que uma garrafa de
o fertilizante líquido custa RM20 e um saco de fertilizante seco custa RM15.
(a) Formule um problema de programação linear para minimizar custos dentro das restrições.
(b) Usando o método gráfico, determine o número de garrafas de fertilizante líquido e
o número de sacos de fertilizante seco que o jardineiro deve comprar para minimizar o custo e encontrar
este custo mínimo.

4. Um fabricante deseja maximizar o lucro de dois produtos. O Produto I gera um lucro de

RM1,50 por unidade, e o Produto II gera um lucro de RM2,00 por unidade. Testes de mercado e disponível
recursos indicaram as seguintes restrições.
(a) O nível de produção combinado não deve exceder 1200 unidades por semana.
A demanda pelo Produto II é menor ou igual a metade da demanda pelo Produto I.
(c) O nível de produção do Produto I deve exceder o do Produto II em mais de 200
unidades.
Usando o método gráfico, determine o número do Produto I e o número do Produto II.
II que oferece o máximo lucro dentro das restrições e encontra esse lucro máximo.

5. Use o método simplex para encontrar o valor máximo da função P 10x1 20x2
sujeito ao seguinte sistema de equações lineares:
3x1 3x2 x3 30
2x 1 4x 2 x4 48
4x 2 x5 40
x 2 x6 dezoito

Compilado por: Goh PC 12

PROGRAMAÇÃO LINEAR 950 / 3
Uma dona de casa tem 30 kg de nozes e 20 kg de passas para serem misturados e vendidos como dois diferentes
pacotes, A e B. Um pacote de A requer 2 kg de nozes e 1 kg de passas. Um pacote de B
requer 3 kg de nozes e 4 kg de passas. O lucro por um pacote de A é RM18 e o lucro por um
pacote de B é RM24.
Formule o problema como um problema de programação linear e use o método simplex para
encontrar o lucro máximo.

7. Uma empresa produz três tipos de forno: tipo I, tipo II e tipo III. Cada tipo de forno
precisa passar por três processos: montagem, teste e embalagem. Os lucros para um tipo I
o forno, um forno do tipo II e um forno do tipo III custam RM180, RM150 e RM100, respectivamente. A tabela
abaixo mostra o número de horas necessárias para produzir um forno tipo I, um forno tipo II e um forno tipo III
forno e o número de horas de homem disponíveis por semana.

Número de horas necessárias Número de horas-homem

Processo
Tipo I Tipo II Tipo III disponível por semana
Montagem 5 4 3 400
Testando 3 2 2 250
Embalagem 1 1 1 70

(a) Formule o problema como um problema de programação linear.

(b) Usando o método simplex, encontre o número de cada tipo de forno a ser produzido para
maximizar o lucro semanal e encontrar esse lucro máximo.

8. Uma empresa produz três produtos X, Y e Z. A tabela abaixo mostra os componentes

usado na fabricação dos produtos.

Massa (kg) necessária por unidade de produto

Produto
Alumínio Aliagem Zinco
X 2 2 2
Y 3 1 1
Z 1 2 1

A empresa possui 6500 kg de alumínio, 6000 kg de liga metálica e 5000 kg de zinco.

Os lucros para cada unidade dos produtos X, Y e Z são RM90, RM50 e RM70
respectivamente.
Formule o problema acima como um problema de programação linear e encontre o máximo
lucro usando o método simplex.

Compilado por: Goh PC 13

PROGRAMAÇÃO LINEAR 950 / 3
STPM 2012
Um investidor tem RM5 milhões para investir em títulos corporativos, depósitos a prazo e fundos de investimento.
a taxa de juros e o investimento máximo permitido são os seguintes.
Tipo de investimento Taxa de juros (%) Investimento máximo permitido (milhões de RM)
Título corporativo 7 1,0
Depósito fixo 3 2,5
fundo unitário 11 1.5
(a) Formular um problema de programação linear para maximizar o total de juros ganhos dentro do
restrições. 5
(b) Usando o método simplex, encontre a quantidade ótima para cada tipo de investimento e o
juros totais ganhos. [9]
(c) Declare se os 5 milhões de RM foram totalmente utilizados. Explique sua resposta.
[2]

STPM 2011
Uma empresa de alimentos produz um cereal a partir de vários ingredientes. O cereal é enriquecido com vitaminas.
A e B que são fornecidos por dois dos ingredientes, aveia e arroz. 1 g de aveia contribui
0,32 mg de vitamina A e 0,08 mg de vitamina B, enquanto 1 g de arroz contribui com 0,24 mg de
vitamina A e 0,12 mg de vitamina B. Cada caixa de cereais produzida deve atender ao mínimo
Exigências de 19,20 mg de vitamina A e 7,20 mg de vitamina B. O custo de 1 kg de aveia é
RM5 e o custo de 1 kg de arroz é RM4. A empresa quer determinar quantos gramas de
aveia e arroz devem ser incluídos em cada caixa de cereal para minimizar custos.
(a) Formule um modelo de programação linear para o problema de minimizar [5] o custo.
(b) Usando um método gráfico, determine quantos gramas de aveia e arroz estão incluídos em
cada caixa de cereal para minimizar o custo e encontrar esse custo mínimo. [8]

STPM 2010
Uma empresa química produz dois tipos de fertilizantes orgânicos em sua fábrica. Três tipos de matérias-primas
materiais P, Q e R são misturados para produzir fertilizantes Tipo X e Tipo Y. Cada tonelada de Tipo X
o fertilizante é uma mistura de 0,4 tonelada de P e 0,6 tonelada de R, enquanto cada tonelada de fertilizante do Tipo Y é um
mistura de 0,5 tonelada de P, 0,2 tonelada de Q e 0,3 tonelada de R. Os rendimentos de lucro para cada tonelada de Tipo X
e os fertilizantes Tipo Y custam RM400 e RM300, respectivamente. As quantidades de matérias-primas
utilizável por semana estão mostrados na tabela a seguir.
Matéria-prima Quantidade de material utilizável por semana (toneladas)
P 20
Q 5
R 21
(a) Se x e y representam as quantidades, em toneladas, dos fertilizantes Tipo X e Tipo Y produzidos
toda semana, formule um modelo de programação linear que possa ser utilizado para maximizar o total
lucro por semana. [4]
(b) Construa o tableau inicial para o modelo de programação linear. [2]
(c) Com base na tabela final a seguir, declare a quantidade de cada tipo de fertilizante que
deve ser produzido por semana para maximizar o lucro total e calcular o lucro total.
Básico x y s1 2 s3 Solução
y 0 1 10
3 0  9
20
20
s2 0 0  23 1 4
9 1
x 1 0  53 0 25
9 25
[2]
Compilado por: Goh PC 14
PROGRAMAÇÃO LINEAR 950 / 3
STPM 2009
Uma empresa de eletrônicos fabrica televisores LCD dos modelos P e Q. Cada unidade de
O modelo requer 3,5 horas de tempo de produção, 1 hora de tempo de montagem e 1 hora de embalagem.
tempo. Cada unidade do modelQ requer 8 horas de tempo de produção, 1,5 horas de tempo de montagem e
1 hora de tempo de embalagem. Os recursos máximos disponíveis para cada processo em um dia são os seguintes
segue:
Processo Recurso disponível por dia
(horas)
Produção 280
Assembléia 60
Embalagem 50
O gerente da empresa deseja maximizar o lucro. Cada unidade de Y gera um lucro de
RM400 enquanto cada unidade de Q gera um lucro de RM800. Devido à alta demanda, a empresa tem que
produzir pelo menos 10 unidades de cada modelo por dia.
(a) Se x e y representam as quantidades dos modelos P e Q produzidos a cada dia, respectivamente,
formule o problema como um problema de programação linear. [5]
(b) Trace um gráfico para o problema acima e sombreie a região factível.[7]
(c) Usando o gráfico que você plotou em (b),
(i) determinar a quantidade da produção diária para cada modelo que dá o
lucro máximo [1]
(ii) encontre o lucro máximo diário. [2]

STPM 2008
Uma fábrica monta três modelos de cadeiras usando seis componentes. A tabela a seguir mostra
o número de unidades de componentes necessárias para cada modelo e o total de unidades de componentes
disponível por semana.
Número de unidades de componentes Total de unidades de componentes
Componente disponível por semana
Modelo P Modelo Q Modelo R
Tipo 1 assento 1 0 0 500
Banco tipo 2 0 1 1 1000
Estrutura da cadeira 1 1 1 1000
Pé da cadeira 4 4 4 4000
Encosto tipo 1 1 1 0 1000
Encosto tipo 2 0 0 1 500
Os lucros para os modelos P, Q e R são de RM35, RM40 e RM50 por unidade, respectivamente.
o gerente da fábrica deseja determinar o número de cadeiras de cada modelo a ser produzido
por semana a fim de maximizar o lucro total.
(a) Se x, 1 x 2e3representar os números de cadeiras dos modelos P, Q e R, respectivamente,
formule um modelo de programação linear para determinar o número de cadeiras de cada modelo que
deve ser produzido por semana para maximizar o lucro total. [5]
(b) Construa o tableau inicial para o problema de programação linear. [4]
(c) Com base na tabela final apresentada abaixo, informe o número de cadeiras de cada modelo que
deve ser produzido por semana a fim de maximizar o lucro total e calcular o máximo
lucro total. [4]

Compilado por: Goh PC 15

PROGRAMAÇÃO LINEAR 950 / 3

Basicx1 x2 x3 s1 s2 s3 s4 s5 s6 Solução
s1 0 0 0 1 1 1 0 0 0 500
x2 0 1 0 0 1 0 0 0 1 500
x1 1 0 0 0 1 1 0 0 0 0
s4 0 0 0 0 0 4 1 0 0 0
s5 0 0 0 0 0 1 0 1 1 500
x3 0 0 1 0 0 0 0 0 1 500

STPM 2007
Uma fábrica produz dois tipos de baterias A e B. Cada unidade da bateria A requer 2 horas de
montar e 1 hora de testes, enquanto cada unidade da bateriaB requer 2,5 horas de montagem
e 1,5 horas de teste. A fábrica tem no máximo 500 horas de montagem por semana e no máximo
300 horas de teste por semana. Está especificado que o número de baterias B produzidas por semana
excede o número de bateriaA produzidas por semana e que o número de bateriaA produzidas
por semana ultrapassa 50 unidades. Os lucros para bateriaA e bateriaB são de RM80 e RM90 por unidade
respectivamente.
(a) Formule o problema acima como um problema de programação linear para maximizar o lucro.
[6]
(b) Usando o método gráfico, determine o número da bateria A e o número de
bateria que deve ser produzida por semana e encontrar o lucro máximo por semana. [10]

STPM 2006
Uma empresa de fabricação de computadores produz três tipos de computadores: desktop para casa,
desktop e notebook para negócios. Cada tipo de computador precisa passar por três processos:
montagem, teste e embalagem. Os lucros de um desktop doméstico, um desktop para negócios e um
os notebooks custam RM200, RM350 e RM450, respectivamente. A tabela abaixo mostra o número de
horas necessárias para produzir um desktop para casa, um desktop para negócios e um notebook e o número de
horas-homem disponíveis por semana.
Processo Número de horas necessárias Número de horas trabalhadas

Caderno
Desktop inicial Área de trabalho empresarialdisponível por semana
Montagem 5 6 8 400
Testando 10 12 12 648
Embalagem 2 4 2 60
(a) Formule o problema como um problema de programação linear [4]
(b) Usando o método simplex, encontre o número de cada tipo de computador a ser produzido para
maximizar o lucro semanal e encontrar este lucro máximo. [9]

Compilado por: Goh PC 16

PROGRAMAÇÃO LINEAR 950 / 3
STPM 2005
Uma empresa produz dois tipos de lâmpadas, A e B, que são feitas de três tipos de
estrado de ferro, componente elétrico e componente plástico. Cada lâmpada A requer 1 unidade
de estrutura de ferro, 2 unidades de componentes elétricos e 3 unidades de componentes plásticos, enquanto cada
A lâmpada B requer 3 unidades de estruturas de ferro, 2 unidades de componentes elétricos e 1 unidade de plástico
componentes. A empresa tem 300000 unidades de estruturas de ferro, 300000 unidades de elétricos
componentes e 400000 unidades de componentes plásticos em estoque. Os lucros obtidos com cada lâmpada
A e a lâmpada B custam RM15,00 e RM20,00, respectivamente.
(a) Formule um problema de programação linear para maximizar o lucro dentro das restrições. [4]
(b) Usando o método gráfico, determine o número da lâmpada A e o número da lâmpada B.
que proporciona o máximo lucro e encontre esse lucro máximo. [8]

STPM 2004
Uma fabricante de chocolate produz dois tipos de barrinhas de chocolate: laranja e morango.
sabores. Custa RM0,22 produzir um chocolate de 10 g com sabor a laranja, que é vendido a
RM0,35, enquanto custa RM0,40 produzir um chocolate sabor morango de 15 g que é
vendido a RM0,55. O fabricante tem 426 kg de chocolate em estoque. Um mínimo de 10000
barras de chocolate com sabor de laranja e 12000 barras de chocolate com sabor de morango têm que ser
produzido. O número de barras de chocolate com sabor a morango produzido deve ser maior do que isso
de barras de chocolate com sabor a laranja.
(a) Formule um modelo de programação linear que possa ser usado para determinar o número de
barras de chocolate de cada sabor que devem ser produzidas para maximizar o lucro total. [6]
(b) Mostre a região factível e, portanto, resolva o problema de programação linear usando o
método gráfico. [9]

STPM 2003
Um fabricante de móveis de madeira produz dois tipos de móveis: cadeiras e mesas. Dois
máquinas são utilizadas na produção: uma serra tico-tico e um torno. Cada cadeira requer 1 hora na
serra tico-tico e 1 hora na torno, enquanto cada mesa requer 1 hora na serra tico-tico e 2 horas na
o tornos. A serra tico-tico e o torno podem operar 10 horas e 12 horas por dia, respectivamente. O
o lucro obtido é de RM27,00 em uma cadeira e RM48,00 em uma mesa. O lucro diário deve ser maximizado.
(a) Formule o problema como um problema de programação linear. [4]
(b) Usando o método simplex, encontre o lucro diário máximo e o número de cadeiras e
mesas feitas que dão esse lucro. [9]

STPM 2002
Uma fábrica produz dois tipos de produtos, A e B. Cada unidade do produto A requer 2 trabalhadores.
horas e 1 hora de máquina, enquanto cada unidade do produto B requer 2 horas de trabalho e 4 de máquina
horas. Não há mais de 120 horas de trabalho e não há mais de 96 horas de máquina disponíveis
na fábrica a cada dia. A fábrica também decidiu que o número de unidades do produto B produzidas
cada dia não deve ser mais do que 60% do total da produção diária dos produtos A e B.
O lucro para cada unidade de A é RM120 e cada unidade de B é RM200. A fábrica pretende
maximizar o lucro total a cada dia.
Formule o problema como um problema de programação linear. [6]
Usando o método gráfico, determine o número de unidades do produto A e do produto B que
deve ser produzido diariamente para maximizar o lucro total e encontrar o lucro total diário máximo
lucro. [9]

Compilado por: Goh PC 17