Introdução a Programação Linear

C A P Í T U L O 2

Introdução à Programação Linear

1. Definição

Um problema de PL consiste em determinar valores não negativos para as variáveis de decisão,

de forma que satisfaçam as restrições impostas e que optimizem (minimizem ou maximizem) uma

função (real) linear dessas variáveis.

2. Formalização e modelação matemática de problemas de PL

Existem 2 formas diferentes de apresentar o modelo, conforme se pretenda maximizar ou

minimizar, que são as seguintes :

nn2211 xcxcxcZ)(MinimizarMaximizar +++= L (1.1)

Sujeito a

{ }

{ }

{ } mnmn2m21m1

2n2n222121

1n1n212111

b,,xaxaxa

. . .

b,,xaxaxa

b,,xaxaxa

≥=≤+++

≥=≤+++

≥=≤+++

L

L

L

(1.2)

(1.3) 0x,,x,x n21 ≥L

onde,

aij (i = 1, ...,m; j = 1, ...,n) → coeficientes técnicos ou tecnológicos,

b1, b2, ..., bm → termos independentes (constantes de restrição ou segundos membros),

c1 , c2, . . . , cn → coeficientes da função objectivo (coeficientes de custo),

14 Formalização e modelação matemática de problemas de PL

x1 , x2, . . . , xn → variáveis de decisão (principais ou controláveis),

(1.1) → função objectivo (económica ou critério),

(1.2) → restrições (restrições funcionais), em que apenas se verifica uma das relações,

(1.3) → condições de não negatividade.

No entanto, o modelo é frequentemente apresentado nas seguintes formas típicas :

Maximizar nn2211 xcxcxcZ)(Minimizar +++= L (2.1)

Sujeito a

mnmn2m21m1

2n2n222121

1n1n212111

b)(xaxaxa

. . .

b)(xaxaxa

b)(xaxaxa

≥≤+++

≥≤+++

≥≤+++

L

L

L

(2.2)

(2.3) 0x,,x,x n21 ≥L

Estas duas formas são tão gerais quanto (1.1), (1.2) e (1.3), pois, mediante operações

convenientes, é sempre possível dar a qualquer problema uma daquelas formas. Com efeito, qualquer

problema pode ser reduzido a uma destas formas, da seguinte maneira :

qualquer problema de minimização pode converter-se num de maximização, pois

Minimizar Z = − Maximizar (− Z)

restrições do tipo (≥) pode ser convertida em restrições do tipo (≤), mediante a multiplicação por (-

1) de ambos os membros,

⇔ inin2i21i1 bxaxaxa ≥+++ L inin2i21i1 bxaxaxa −≤−−−− L

restrições do tipo (=) pode ser convertida em 2 do tipo (≤) equivalentes, em conjunto, àquela,

⇔ ⇔ inin2i21i1 bxaxaxa =+++ L

≥+++

≤+++

inin2i21i1

inin2i21i1

bxaxaxa

bxaxaxa

L

L

⇔

−≤−−−−

≤+++

inin2i21i1

inin2i21i1

bxaxaxa

bxaxaxa

L

L

variável livre (sem restrição de sinal) pode ser substituída pela diferença de variáveis não

negativas1 ( x ), formulando-se de novo o problema em termos

destas variáveis.

0x,xcomxx ''j

'j

''j

'jj ≥= −

1 Qualquer número pode ser obtido como a diferença de dois números não negativos.


Formalização e modelação de alguns problemas de PL 15

3. Formalização e modelação de alguns problemas de PL

Problema 1 :

Uma empresa de mobiliário de escritório pretende lançar um modelo de secretárias e estantes.

Pensa-se que o mercado pode absorver toda a produção de estantes, mas aconselha-se que a

produção mensal de secretárias não ultrapasse as 160 unidades.

Ambos os produtos são processados nas unidades de estampagem (UE) e de montagem e

acabamento (UMA).

A disponibilidade mensal em cada uma destas unidades é de 720 horas−máquina (h−m) na UE

e 880 horas−homem (h−h) na UMA.

Cada secretária necessita de 2h−m na UE e de 4 h−h na UMA.

Cada estante necessita de 4 h−m na UE e de 4 h−h na UMA.

As margens de lucro unitárias estimadas são de 6 contos para as secretárias e de 3 contos para

as estantes.

Qual o plano de produção mensal para as secretárias e estantes que maximiza a margem de

lucro.

Formalização do problema :

Variáveis de decisão :

quantidade de secretárias a produzir por mês (x1) •

•

•

•

•

•

quantidade de estantes a produzir por mês (x2)

Função objectivo :

maximizar a margem bruta total por mês (Z = 6 x1 + 3 x2)

Restrições :

disponibilidade mensal na unidade de estampagem

disponibilidade mensal na unidade de montagem e acabamento

produção mensal de secretárias

Secretárias Estantes Capacidade disponível

UE 2 4 720

UMA 4 4 880

Mercado 1 0 160

Lucro 6 3


16 Formalização e modelação de alguns problemas de PL

Modelação matemática :

Relativamente ao Departamento de Estampagem, sabe-se que :

cada secretária necessita de 2 h−m, pelo que o nº total de h−m necessárias à produção de

x1 secretárias é de 2 x1;

•

•

•

cada estante necessita de 4 h−m, pelo que o nº total de h−m necessárias à produção de x2

secretárias é de 4 x2;

a disponibilidade mensal é de 720 h−m.

Logo, a restrição relativa a este Departamento é :

Total de h−m gasto nas secretárias

+ Total de h−m gasto nas estantes

≤ Disponibilidade em h−m

que se traduz algebricamente na desigualdade linear : 2 x1 + 4 x2 ≤ 720

Da mesma forma se determinam as restantes restrições.

Resumindo, o problema consiste em determinar x1 e x2 por forma a

Maximizar Z = 6 x1 + 3 x2 (lucro mensal em contos)

sujeito a 2 x1 + 4 x2 ≤ 720 (UE)

4 x1 + 4 x2 ≤ 880 (UMA)

x1 ≤ 160 (mercado)

x1, x2 ≥ 0 (não negatividade)

Problema 2 :

Um criador de porcos, pretende determinar a quantidade de cada tipo de ração a dar

diariamente a cada animal, para conseguir uma dada qualidade nutritiva a custo mínimo.

Os dados relativos ao custo de cada tipo de ração, às quantidades mínimas diárias de

ingredientes nutritivos básicos a fornecer a cada animal, bem como às quantidades destes existentes

em cada tipo de ração (g/kg) constam do quadro em baixo.

Granulado (gr/Kg)

Farinha (gr/Kg)

Quantidade mínima requerida

Hidratos de carbono 20 50 200

Vitaminas 50 10 150

Proteínas 30 30 210

Custo (esc./Kg) 10 5


Formalização e modelação de alguns problemas de PL 17



quantidade (Kg) de granulado existente na ração diária (x1) •

•

•

•

•

•

quantidade (Kg) de farinha existente na ração diária (x2)


minimizar o custo da ração diária (Z = 10 x1 + 5 x2)

Restrições :

quantidade mínima diária de hidratos de carbono

quantidade mínima diária de vitaminas

quantidade mínima diária de proteínas


Pretende-se determinar x1 e x2 de modo a

minimizar Z = 10 x1 + 5 x2 (custo diário)

sujeito a 20 x1 + 50 x2 ≥ 200 (hidratos de carbono)

quantidade a fornecerdiariamente

quantidade mínima necessária por dia

50 x1 + 10 x2 ≥ 150 (vitaminas)

30 x1 + 30 x2 ≥ 210 (proteínas)


Problema 3 :

As Caravanas Marco Polo L.da. usam dromedários (1 bossa) e camelos (2 bossas) para

transportar figos secos de Bagdade para Meca. Um camelo pode levar no máximo 1000 lbs e um

dromedário 500 lbs. Durante a viagem um camelo consome 3 fardos de feno e 100 galões de água. Um

dromedário consome 4 fardos de feno e 80 galões de água. As estações da Marco Polo, situadas em

vários oásis ao longo do caminho, apenas têm disponíveis 1600 galões de água e 60 fardos de feno.

Os camelos e os dromedários são alugados a um pastor perto de Bagdade a 11 pazuzas por

camelo e 5 pazuzas por dromedário. Se as Caravanas Marco Polo L.da. tiverem uma carga de 10000

lbs de figos para transportar, quantos camelos e dromedários devem ser usados para minimizar a

renda a pagar ao pastor ?



quantidade de camelos a usar (x1) •

• quantidade de dromedários a usar (x2)



18 Representação e resolução gráfica de problemas de PL

minimizar a renda a pagar ao pastor (Z = 11 x1 + 5 x2) •

•

•

•

Restrições :

capacidade da caravana

disponibilidade de feno

disponibilidade de água

Camelos Dromedários Capacidade disponível

Capacidade 1 000 500 10 000

Feno 3 4 60

Água 100 80 1 600

Renda a pagar 11 5


Pretende-se determinar x1 e x2 de modo a

Minimizar Z = 11 x1 + 5 x2 (renda)

sujeito a

1 000 x1 + 500 x2 ≥ 10 000 (capacidade)

3 x1 + 4 x2 ≤ 60 (feno)

100 x1 + 80 x2 ≤ 1 600 (água)


4. Representação e resolução gráfica de problemas de PL

A representação gráfica de problemas de PL só é possível, quando os problemas têm 2 ou 3

variáveis de decisão. No entanto, aqui, apenas serão analisados os problemas com 2 variáveis, os

quais são representados através de um gráfico a 2D.

Para representar graficamente um problema de PL, começa-se por construir um sistema de

eixos cartesianos x1 e x2.

O passo seguinte consiste em identificar os valores de x1 e x2 que satisfaçam todas as restrições

construção do espaço das soluções.

Por último, procuram-se os pontos situados nesta região que maximizem (minimizem) o valor

de Z. Esta fase vai proceder-se por tentativas (mais adiante será enunciada uma regra prática que

permite resolver esta questão de uma forma quase automática).

O processo baseia-se na representação gráfica da recta Z = F (x1, x2) = constante para um

conjunto de valores. A ideia é traçar rectas Z = constante, até que contenha pelo menos um ponto da


Representação e resolução gráfica de problemas de PL 19

região admissível e esteja o mais distante possível da recta Z = 0 (maximizar) ou o mais perto possível

(minimizar).

Resolução gráfica do Problema 1 :

Solução óptima do problema : xopt = (160, 60) ⇔ Zopt = 1140.


20 Representação e resolução gráfica de problemas de PL


Solução óptima do problema : xopt = (2, 5) ⇔ Zopt = 45


Forma padrão ou “standard” de um problema de PL 21


Solução óptima do problema : xopt = (4, 12) ⇔ Zopt = 104.

5. Forma padrão ou “standard” de um problema de PL

Um PL diz-se estar na forma padrão, se todas as restrições propriamente ditas (não incluindo as

de não negatividade) são equações. Todo o PL pode escrever-se na sua forma padrão, por introdução

de variáveis folga (“slack”) nas restrições que são inequações, da seguinte forma :

f(x) ≤ b ⇒ f(x) + x = b, x ≥ 0 (x variável “slack”)

f(x) ≥ b ⇒ f(x) − x = b, x ≥ 0 (x variável “slack”)

A forma padrão apresenta a seguinte estrutura :

Maximizar Z nn2211 xcxcxc +++ L= (3.1)

Sujeito a

mnmn2m21m1

2n2n222121

1n1n212111

bxaxaxa

bxaxaxa

bxaxaxa

=+++

=+++

=+++

L

L

L

... (3.2)

(3.3) 0x,,x,x n21 ≥L


22 Terminologia associada às soluções do PL

A redução à forma padrão do problema de PL

Maximizar Z nn2211 xcxcxc +++= L

Sujeito a

2n2n222121

1n1n212111

bxaxaxa

bxaxaxa

≤+++

≤+++

L

L

. . .

mnmn2m21m1 bxaxaxa ≤+++ L

0x,,x,x n21 ≥L

conduz ao seguinte problema equivalente :

Maximizar Z mn2n1nnn2211 x0x0x0xcxcxc +++ +++++++= LL

Sujeito a

22nn2n222121

11nn1n212111

bxxaxaxa

bxxaxaxa

=++++

=++++

+

+

L

L

. . .

mmnnmn2m21m1 bxxaxaxa =++++ +L

0x,,x,x,x,,x,x mn2n1nn21 ≥+++ LL

em que,

são as variáveis de decisão (principais) n21 x,,x,x L

são as variáveis folga (“slack”) mn2n1n x,,x,x +++ L

Também é frequente o modelo de PL ser apresentado em forma matricial :

Maximizar Z = C X

Sujeito a A X = b

X ≥ 0 em que,

C = [ c1 c2 . . . cn ] é a matriz dos custos

A = [ aij ] (m×n) é a matriz das restrições

X = [ x1 x2 . . . xn ]T é a matriz das variáveis

b = [ b1 b2 . . . bm ]T é a matriz dos termos independentes

0 = [ 0 0 . . . 0 ]T (1×m) é a matriz nula

6. Terminologia associada às soluções do PL

Solução qualquer conjunto de valores assumidos pelas variáveis de decisão satisfazendo as

restrições funcionais (3.2).

Solução admissível solução que satisfaz as condições de não negatividade (3.3).

Região admissível é o conjunto de todas as soluções admissíveis.


Tipos de soluções 23

Solução óptima é a solução admissível que tem o melhor valor da função objectivo.

Solução não limitada não existe um valor máximo (mínimo) para a função objectivo.

7. Tipos de soluções

óptima única : problema tem apenas uma solução (Problemas 1, 2 e 3).

óptimas alternativas : o valor óptimo da função objectivo pode ser obtido através de

infinitas combinações de recursos.

não limitada : não existe um valor máximo finito para a função objectivo (Z → ∞).


24 Tipos de soluções

óptima (com região admissível não limitada) : facto do conjunto das soluções admissíveis ser não

limitado, não implica necessariamente que a solução seja não limitada (Z → ∞).

valor óptimo da FO finito (variáveis podem assumir valores arbitrariamente grandes) : conjunto

das soluções é não limitado e o valor óptimo de Z é finito, com as variáveis de decisão a

poderem assumir valores arbitrariamente grandes na solução óptima.


Análise convexa 25

inexistente (problema impossível) : esta situação, normalmente deriva de erros de formalização.

Isto pode acontece por não existirem valores das variáveis a satisfazerem as restrições do

problema ou as condições de não negatividade, ou ambas simultaneamente.

8. Análise convexa

Chama-se combinação linear convexa de um nº finito de pontos x1, ..., xn ao ponto

λ1 x1 + λ2 x2 + . . . + λn xn

com os escalares λi ≥ 0 e λ1 + λ2 + . . . + λn = 1.

O segmento de recta que une 2 pontos do espaço, é o conjunto de todas as combinações

convexas desses pontos.

Conjunto convexo X, é um conjunto tal que o segmento de recta que une dois quaisquer dos

seus pontos, está contido no conjunto. Por outras palavras, X é um conjunto convexo, se quaisquer

que sejam x1 e x2, ∈ X e 0 ≤ λ ≤ 1, se tem

λ x1 + (1 - λ) x2 ∈ X

Um conjunto convexo é fechado se compreende a sua fronteira.

Conjunto convexo Conjunto não convexo

Resultado : A intersecção finita de conjuntos convexos é um conjunto convexo.


26 Propriedades fundamentais

Ponto extremo de um conjunto convexo X, é um ponto que não pertence ao segmento de recta a

unir dois outros pontos quaisquer de X. Por outras palavras, um ponto extremo de X não pode ser

obtido por combinação linear convexa positiva de pontos de X.

Algebricamente : x = λ x1 + (1-λ) x2 , com λ ∈ ]0, 1[ e x1, x2 ∈ X ⇒ x = x1 = x2

Um conjunto convexo da forma

X = { x : A x = b, x ≥ 0 } (X é o conjunto de soluções admissíveis do PL)

chama-se um politopo convexo.

Um politopo convexo limitado, chama-se poliedro convexo. Em R2, um poliedro convexo

chama-se polígono convexo.

Chama-se vértice (ou ponto extremo) dum politopo ou poliedro convexo X, a um qualquer

ponto x ∈ X que não possa ser expresso como combinação linear de outros pontos y ∈ X (y ≠ x).

9. Propriedades fundamentais

O conjunto convexo (politopo ou poliedro) X, tem um nº finito de vértices v(X) ( ≤ . nmC )

Todo o ponto dum poliedro convexo X ⊂ Rn é combinação convexa dos vértices de X.

O conjunto das soluções admissíveis, X, de um problema de PL é um conjunto convexo fechado

(compreende a sua fronteira).

Optimalidade num vértice :

• O óptimo duma função linear num poliedro convexo X ⊂ Rn é obtido em, pelo menos, um

vértice de X;

• Se ele for obtido em mais que um vértice, então será obtido em todo o ponto que é uma

combinação linear convexa desses vértices.

• Se X é um politopo convexo, então existe pelo menos um ponto extremo de X que

optimiza a função objectivo.


Documents

Introdução a Programação Linear