INVESTIGACAO OPERACIONAL

CAPÍTULO 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 :

Maximizar (Minimizar)

Z = c 1 x 1 + c 2 x 2 +L+ c n x n

(1.1)

Sujeito a

a 11 x 1 + a 12 x 2 +L+ a 1n x n

{ ≤, =, ≥ }

b1

a 21 x 1 + a 22 x 2 +L+ a 2n x n

{ ≤, =, ≥ }

b2

(1.2)

... a m1 x 1 + a m2 x 2 +L+ a mn x n

{ ≤, =, ≥ }

bm

x 1 , x 2 , L, x n ≥ 0

(1.3)

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 (Minimizar)

Z = c 1 x 1 + c 2 x 2 +L+ c n x n

(2.1)

Sujeito a

a 11 x 1 + a 12 x 2 +L+ a 1n x n ≤ ( ≥ ) b 1 a 21 x 1 + a 22 x 2 +L+ a 2n x n ≤ ( ≥ ) b 2

(2.2)

... a m1 x 1 + a m2 x 2 +L+ a mn x n ≤ ( ≥ ) b m x 1 , x 2 ,L, x n ≥ 0

(2.3)

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