Programao

Linear

Problema
1
Define o problema

2
Formula o
objectivo

3
Avalia
as vrias
alternativas

Escolhe a melhor via

Problemas simples
Problemas complexos

Recurso intuio e
experincia
Mtodos cientficos

Programao Linear

Afinal o que a Programao Linear?

A Programao Linear consiste em optimizar
(maximizar ou minimizar) uma dada funo linear, que se
chama funo objectivo, definida num dado conjunto
convexo, tendo em conta que as variveis esto sujeitas
a restries.

Nota Histrica
Sculo III a.C Euclides
Livro III ( Procurava encontrar a maior e a menor distncia
de um ponto a uma circunferncia)
Livro IV ( Descreveu uma forma de obter um Paralelogramo
de rea mxima e com um dado permetro)

1759 Quesnay (publica o Tableau Economique que pode

ser considerado a primeira grande tentativa de
modelizar a economia)

1838 - Cournot (incluiu no seu estudo a determinao

do ponto de equilbrio que origina o lucro mximo)

1874 Walras (publica o Sistema de Equilbrio

Geral onde procura a melhor forma de
interpretar a economia como um todo)

1937 Von Neumann (publica A Model of General

Economic Equilibrium onde formulado o modelo de
Programao Linear dinmica, em que admite mtodos
alternativos de produo simples ou conjunta.)

1939 Kantorovich (formulou rigorosamente um problema de

Programao Linear no trabalho Mtodos Matemticos de Organizao e
Planeamento da Produo, mas no apresentou um algoritmo de
resoluo)
O grande salto da Programao Linear dado atravs das aplicaes
em problemas de transportes na dcada de 40 (em particular, pelas Foras
Armadas durante a Segunda Guerra Mundial).

1947 Dantzig (trabalhou no Pentgono como

conselheiro
matemtico,
onde
era
frequentemente chamado para resolver
problemas de planeamento. Como a maioria
destes diziam respeito economia aconselhouse junto ao economista Koopmans)
No entanto, contrariamente ao que
Dantzig pensou, os economistas ainda no
tinham mtodos de resoluo de tais
problemas.
Foi ento que Dantzig props o
Mtodo Simplex que tornou possvel a soluo
de problemas de optimizao de vrios tipos.

Um ano mais tarde

Koopmans e Dantzig encontraram-se.

Porque no reduzir o
nome de Programao de
Estruturas Lineares para
Programao Linear?

isso! A
partir de
agora esse
o seu nome.

Nasceu assim a designao de

Programao Linear.
Desde ento, as aplicaes da
Programao Linear no cessaram.

Onde se aplica?
Os domnios de aplicao da Programao Linear so vastssimos.
Por exemplo:
Gesto de empresas;
Problemas de transportes;
Estrutura financeira dos bancos;
Obteno de misturas ptimas;

Planeamento agrcola;
Estratgias militares,

A Direco de Marketing do IKEA sugere o lanamento

de um novo modelo de secretria e de estante em
substituio dos modelos actuais.

Aquela Direco no v dificuldade de colocao

no mercado para as estantes enquanto que aconselha que
a produo mensal de secretrias no ultrapasse as 160
unidades.

Aps estudos levados a cabo pela Direco de

Produo, conclui-se que:
A disponibilidade mensal do Departamento de
Estampagem de 720 horas-mquina;
A disponibilidade mensal do Departamento de
Montagem e Acabamento de 880 horas-homem;
Cada secretria necessita de 2 horas-mquina de
Estampagem e 4 horas-homem de Montagem e Acabamento;
Cada estante necessita de 4 horas-mquina de
Estampagem e 4 horas-homem de Montagem e Acabamento.

As margens brutas unitrias estimadas so de

60 euros para as secretrias e 30 euros para as
estantes.

A empresa pretende determinar o

plano de produo mensal para estes
novos modelos que maximiza a margem
bruta.

Sejam:
x, o nmero de secretrias;
y, o nmero de estantes;

z, a margem bruta total.

Variveis de deciso

OBJECTIVO: determinar valores para estas variveis

que maximizem

z = 6x + 3y (em 10 euros)

Restries impostas pelas limitaes da capacidade produtiva

e do mercado.

Linguagem
corrente

Linguagem
Matemtica

Cada secretria
necessita de 2
horas-mquina

2x

Cada estante
necessita de 4
horas-mquina

4y

A disponibilidade
mensal de 720
horas-mquina

2x + 4y 720

Linguagem
corrente

Linguagem
Matemtica

Cada secretria
necessita de 4
horas-mquina

4x

Cada estante
necessita de 4
horas-mquina

4y

A disponibilidade
mensal de 880
horas-mquina

4x + 4y 880

Linguagem
corrente

Linguagem
Matemtica

A produo mensal
de secretrias no
pode ultrapassar as
160 unidades.

x 160

O nmero de
secretrias no pode
ser negativo

x0

O nmero de
estantes no pode
ser negativo

y0

As condies de no negatividade , indicam-nos que

os pares ordenados (x, y) se encontram no primeiro quadrante.

As variveis que entram na formulao

do problema no podem assumir valores
negativos. Por isso, em geral, a no
negatividade das variveis considerada
uma restrio natural, que acontece pelo
facto de muitas das actividades s
poderem ser executadas a nveis no
negativos.

O problema consiste em escolher x e y

por forma a
maximizar
z = 6x + 3y
sujeito a
2x + 4y 720
4x + 4y 880
x 160
x, y 0.

Conjunto das solues admissveis ou regio de validez

toda a soluo que satisfaz as

restries
do
problema
e
as
restries da no negatividade. Notese que uma soluo possvel no
precisa optimizar a funo objectivo,
e
frequentemente
h
infinitas
solues possveis.

Procure(m)-se o(s) ponto(s) situado(s) nesta regio que

maximiza(m) o valor de z = 6x + 3y.
Vai proceder-se por tentativas. O processo baseia-se na
representao grfica da recta 6x + 3y = k (com k constante).
k = 300

k = 600

Trace-se uma qualquer recta

de nvel e desloque-se paralelamente
a si prpria, no sentido do
crescimento de z at ao(s) ltimo(s)
ponto(s) de contacto com a regio
admissvel.

De acordo com esta regra, a soluo ptima x* = 160 e y* = 60,

valores que do, respectivamente, o nmero de secretrias e estantes a
produzir por ms pelo IKEA.

Deste programa
de
produo
resulta para a
empresa
uma
margem
bruta
mensal de 11400
euros.

Uma das tarefas propostas

para a Quinta das Celebridades
consiste em determinar as quantidades
de cada tipo de rao que devem ser
dadas diariamente a cada animal de
forma a conseguir uma certa qualidade
nutritiva a um custo mnimo.

Os dados relativos ao custo de cada tipo de rao, s

quantidades mnimas dirias de ingredientes nutritivos bsicos a
fornecer a cada animal, bem como s quantidades destes existentes
em cada tipo de rao (g/kg) constam no quadro seguinte:

Rao

Granulado

Farinha

Quantidade
mnima
requerida

Hidratos de
carbono

20

50

200

Vitaminas

50

10

150

Protenas

30

30

210

Custo
(cnts/kg)

10

Ing.
Nutritivos

Mas o que
isto???!!!

Vamos ajudar Jos Castelo Branco

a formalizar o problema

x , a quantidade em quilogramas de granulado a fornecer diariamente

a cada animal;
y, a quantidade em quilogramas de farinha a fornecer diariamente a
cada animal;

O custo total (em cntimos) a suportar diariamente com a

alimentao de cada animal

z = 10x+5y

Objectivo dos concorrentes: minimizar o custo total.

As possibilidades de escolha esto limitadas pelas seguintes

restries relativas ao regime alimentar de cada animal:
20x + 50y 200
O primeiro membro desta desigualdade exprime a quantidade (g) de
hidratos de carbono a fornecer diariamente. O segundo membro
exprime, por sua vez, a quantidade quotidiana mnima necessria
destes nutrientes.
Analogamente para as vitaminas:
50x + 10y 150

E para as protenas:
30x + 30y 210

Sabendo que a quantidade de cada rao a fornecer diariamente

no negativa, isto , x 0 e y 0, tem-se, finalmente, o modelo de
programao linear que permite estabelecer a dieta dos animais:
Minimizar
Sujeito a

z = 10x + 5y
20x + 50y 200
50x + 10y 150
30x + 30y 210
x 0, y 0

 fcil concluir que a soluo

pretendida x* = 2 e y*= 5,
valores que do, respectivamente,
as quantidades (em quilogramas)
de granulado e farinha a fornecer
diariamente a cada animal. Desta
dieta resulta para a quinta um
custo de alimentao dirio com
cada animal de 45 cntimos.

Considere-se o seguinte problema:

maximizar z = 2x + y
sujeito a

3x + 4y 12
4x + 2y 10
x, y 0.

Conclui-se que z = 5 o valor mximo da

Funo Objectivo.
uma funo linear, que
vamos
pretender
optimizar,
isto
,
maximizar ou minimizar;

Igualmente se conclui que quer o ponto extremo A quer o ponto

extremo B so solues ptimas do problema; por outras palavras, neste
caso, dois pontos extremos conduzem ao mesmo valor (mximo) para a
Funo Objectivo. Mais, qualquer ponto da aresta AB tambm soluo
ptima, dado que a recta de nvel z = 5 assenta sobre aquela aresta;
existe pois uma infinidade de solues ptimas.

Havendo um domnio
de solues possveis e no
havendo soluo ilimitada,
soluo ptima a soluo
possvel que optimiza a
funo objectivo. Nesse
caso, poder haver uma,
vrias ou infinitas solues
ptimas.

Em qualquer dos problemas anteriores pode afirmar-se

que se est perante problemas de Programao Linear bem
comportados. Existe contudo a possibilidade de situaes
anmalas.
Considere-se ento o seguinte problema:
maximizar z = 2x + 3y

sujeito a

2x + 2y 6
-x + y 1
y3
x, y 0.

Nesta situao conclui-se que a Funo Objectivo pode

assumir valores arbitrariamente grandes e, consequentemente, no
existe um valor mximo finito para z. Sempre que se verifica esta
situao, diz-se que se est em presena de soluo no limitada.

Deve contudo salientar-se que o facto do conjunto das

solues admissveis ser no limitado no implica necessariamente
que a soluo seja no limitada.

Est nesta situao o exemplo 2 e o seguinte problema:

maximizar z = -x + 3y
sujeito a

2x + 2y 6
-x + y 1
y3
x, y 0.

Pode ainda acontecer que o conjunto das solues seja no

limitado e o valor ptimo de z seja finito com variveis a poderem
assumir valores arbitrariamente grandes na soluo ptima. Neste
caso, existem solues ptimas alternativas, como se ilustra atravs do
seguinte problema:
maximizar z = -2x + 4y
sujeito a
-x + y 1
x - 2y -4
x, y 0.
O valor mximo da
Funo Objectivo 8. Mais,
qualquer ponto (x, y) da aresta
do
conjunto
das
solues
admissveis que se prolonga at
infinito conduz a z = 8 e
portanto soluo ptima do
problema. evidente que embora
a Funo Objectivo no possa
exceder o valor 8, as variveis x
e y podem assumir valores
arbitrariamente grandes.

Outra situao anmala que pode surgir, normalmente

derivada de erros de formalizao, a no existncia de qualquer
soluo admissvel. Isto pode acontecer por no existirem valores das
variveis a satisfazerem as restries do problema ou as condies de
no negatividade, ou ambas simultaneamente.
Neste caso o problema diz-se impossvel. O exemplo seguinte
ilustra esta situao:
minimizar z = x + 2y
sujeito a
x+y3
2x + y 2
x, y 0

Para angariarem fundos para o Carro da Queima das Fitas, os

alunos do 3ano de Matemtica optaram por vender 300 t-shirts e 600
esferogrficas.
Para tal, decidiram fazer dois tipos de lotes:
tipo A: uma t-shirt e uma esferogrfica;
tipo B: duas t-shirts e cinco esferogrficas.
Os lotes do tipo A foram vendidos a 8 e os do tipo B a 18.

Quantos lotes de cada tipo convm formar para

obter o lucro mximo com a sua venda?

H 300 t-shirts e 600 esferogrficas.

Comecemos por identificar as incgnitas do problema que so:
x, nmero de lotes de tipo A
y, nmero de lotes de tipo B
Graficamente, x e y podem ser tomados, respectivamente, como
coordenadas de um ponto.

Nmero de
lotes

Nmero de
t-shirts

Nmero de
esferogrfi
cas

Lucro

Tipo A

8x

Tipo B

2y

5y

18y

Total

x+y

x + 2y

x + 5y

8x + 18y

Restries:
O nmero de lotes de cada tipo no negativo, ou seja, x 0 e y 0,
com x e y inteiros.
O nmero de t-shirts no pode ser superior a 300, isto , x + 2y
300 y 150 1/2x.
O nmero de esferogrficas no pode ser superior a 600, isto , x +
5y 600 y 120 1/5x.

Desta regio de validez fazem parte os vrtices do polgono

que a limita. Esses vrtices vo ser determinados algebricamente:
x + 2y = 300
x + 5y = 600
x = -2y + 300
3y = 300

x = -2y + 300

x + 5y = 600

x = -2y + 300

-2y + 300 + 5y = 600

x = 100
y = 100

Os vrtices do polgono so ento os pontos de coordenadas:

(0, 120), (100, 100), (300, 0) e (0, 0).

Qual a funo objectivo?

O lucro.
Como cada lote do tipo A custa 8 e do tipo B custa 18, a
funo linear (L) expressa-se por
L = 8x + 18y

(1)

Pretende-se maximizar esta expresso.

A igualdade (1) pode ainda ser expressa por:

y = - 8/ 18x + L/18.
Tracemos uma recta dessa famlia, por exemplo, fazendo L =
680 obtm-se ento a recta de equao y = - 8/18x + 40.

Todas as outras rectas da famlia so paralelas a esta e o

valor de L cresce quando se desloca a recta paralelamente a si
prpria, da esquerda para a direita.
Achar a soluo ptima equivale a determinar a recta com
maior ordenada na origem que intersecta o polgono.
A soluo (x, y) procurada um dos vrtices do polgono.

Como a soluo (0, 0) eliminada desde o incio, decide-se

analiticamente qual dos outros a soluo procurada:

8 x 0 + 18 x 120 = 2160
8 x 100 + 18 x 100 = 2600
8 x 300 + 18 x 0 = 2400

Verificamos ento que (100, 100) a soluo ptima.

Para resolvermos o problema graficamente, devemos

deslocar a recta paralelamente a si prpria, de modo a passar por
cada um dos vrtices do polgono _ regio de validez _ verificando
em qual deles a recta adquire maior ordenada na origem.

Neste caso, isso acontece quando a recta passa em (100, 100).

Os elementos do Carro concluram, que devem ser feitos

100 lotes do tipo A e 100 lotes do tipo B, obtendo-se, assim, um
lucro de 2600 euros.
Est encontrada a soluo do problema.

E se os preos dos lotes fossem outros?

A Tesoureira argumentou que se

poderiam mudar os preos dos lotes sendo o
lote do tipo A vendido a 4 e o lote do tipo B
a 20.
Todas as restries anteriores se
mantm, mudando apenas a funo objectivo
que passa a ser
L = 4x + 20y.

Qual ser agora a soluo ptima?

Ora, y = -1/5x + L/20.

Faa-se, por exemplo, L = 2000.
Obtm-se ento, y = - 1/5x + 100

Faamo-la deslocar-se paralelamente a si prpria de

baixo para cima, procurando a paralela em que L mximo.

Verifica-se que vai

coincidir com a recta de equao
x + 5y = 600 j traada. A, a
recta tem a maior ordenada na
origem o que corresponde ao
valor mximo de lucro.

L mximo em:
(5, 119), (10, 118), (15, 117), (20, 116), , (100, 100).
O conjunto destes pontos a soluo ptima. Obtendo-se
sempre 600 euros de lucro.

E se cada lote A for vendido a 10 e

cada lote B a 20 ?

A funo objectivo neste caso:

L = 10x + 20y
Tracemos, por exemplo, a recta de equao
10x + 20y = 4000
que corresponde recta
y = 200 1/2x.
Procedendo analogamente, verificamos que as solues
so:
(100, 100), (102, 99), , (300, 0).
O lucro conseguido
seria de 3000.

Durante a reunio, foram analisadas as diferentes

hipteses que foram propostas e as solues encontradas,
ficando decidido que a 3 situao a que dar maior lucro,
estando postas de parte a 1 e a 2 hipteses.

Ficou decidido em acta que se iriam fazer 100 lotes

do tipo A e 100 do tipo B.

O fundamental da resoluo do problema consiste em:

_ Identificar as incgnitas x e y;
_ Exprimir as vrias restries por equaes ou inequaes lineares em
funo de x e y, (graficamente, essas condies representam rectas ou
semiplanos);
_ Efectuar a sua conjuno, o que significa determinar graficamente a
interseco dos conjuntos por elas definidos e delimitar uma regio de
validez onde se situam os pontos admissveis;
_ Algebricamente, devemos utilizar as equaes definidas pelas
restries para determinar as coordenadas dos pontos de interseco
das rectas duas a duas e, assim, obter os vrtices do polgono ( regio
de validez );
_ Identificar a funo objectivo, linear em x e y, e determinar um
elemento da famlia de rectas que lhe corresponde, para a partir dela,
encontrar a soluo ptima.

Funo objectivo P = 3x + 2y

Evidencimos que o seu surgimento veio de necessidades

concretas da Sociedade Militar e que o seu desenvolvimento
actual e permanente fruto de problemas colocados pelas mais
diversas reas (Economia, Indstria, ).

Tem como finalidade, desenvolver a capacidade de usar a

Matemtica como instrumento de interpretao e interveno
no real. (Salientamos a dificuldade que muitas vezes h na
prpria formalizao dos problemas que advm da complexidade
dos enunciados e suas interpretaes.)

No abordmos, geometricamente, situaes que envolvessem

trs variveis, apesar de termos conscincia de que, casos destes
constituiriam generalizao dos estudados (rectas e polgonos no
espao bidimensional corresponderiam, respectivamente, a planos e
poliedros no espao a trs dimenses).

O mtodo simplex um mtodo usado na Programao Linear,

sobretudo em problemas que envolvam mais que duas variveis e da
a sua utilizao em termos computacionais.

Fim

Trabalho realizado por:

Cati Matos;
Daniela Santos;
Diana Salgado;
Maria Alice Martins.