Programação MatemáticaLicenciatura em Matemática

Marília Pires

Universidade do AlgarveDepartamento de Matemática

2005/06

Conteúdo

1 Modelos de Optimização 31.1 Programação Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2 Tópicos sobre convexidade . . . . . . . . . . . . . . . . . . . . . . . . 91.3 Programação Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.4 O Método Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191.5 Algoritmo Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.5.1 O método simplex em forma de quadro . . . . . . . . . . . . . 211.5.2 Exemplo de aplicação do método simplex . . . . . . . . . . . . 23

1.6 Dualidade em Programação Linear . . . . . . . . . . . . . . . . . . . 261.7 Análise de sensibilidade e análise post-optimal . . . . . . . . . . . . . 31

2 O Problema de Transportes 342.1 Formalização do problema: . . . . . . . . . . . . . . . . . . . . . . . . 36

2.1.1 Exemplo concreto . . . . . . . . . . . . . . . . . . . . . . . . . 362.2 Propriedades das matrizes dos problemas de transportes . . . . . . . 382.3 Obtenção da solução básica admissível inicial . . . . . . . . . . . . . . 412.4 Forma especial do método simplex para o problema de transportes . . 432.5 Soluções degeneradas . . . . . . . . . . . . . . . . . . . . . . . . . . . 452.6 Desequilíbrio entre oferta e procura . . . . . . . . . . . . . . . . . . . 46

3 Programação Linear Inteira 483.1 Algoritmo Branch-and-Bound . . . . . . . . . . . . . . . . . . . . . . 48

3.1.1 Resolução de um problema concreto . . . . . . . . . . . . . . . 49

4 Optimização sem restrições 574.1 Funções reais de variável real . . . . . . . . . . . . . . . . . . . . . . 574.2 Funções reais de variável vectorial . . . . . . . . . . . . . . . . . . . . 574.3 Gradiente, Hessiana e Jacobiano . . . . . . . . . . . . . . . . . . . . . 58

1

4.4 Gradiente e Hessiana de uma função quadrática . . . . . . . . . . . . 594.5 Derivada de um produto de funções . . . . . . . . . . . . . . . . . . . 604.6 Derivação de função composta (regra da cadeia) . . . . . . . . . . . . 60

5 Programação não Linear 625.1 (alguns) Tipos de Problemas não Lineares . . . . . . . . . . . . . . . 625.2 As condições de Karush-Kuhn-Tucher (KKT) para optimização com

restrições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645.2.1 Programação Quadrática . . . . . . . . . . . . . . . . . . . . . 65

2

Capítulo 1

Modelos de Optimização

Os modelos de optimização tentam expressar, em termos matemáticos, o objectivode resolver um problema da melhor maneira de acordo com certas limitações.Alguns exemplos:

- Projectar uma ponte de modo a:

maximizar a resistência e/ou

minimizar os materiais

- Gerir um negócio de modo a:

maximizar os lucros e/ou

minimizar os custos e/ou

minimizar o pessoal...

- Criar um motor de automóvel de modo a:

maximizar a velocidade e/ou

minimizar a poluição e/ou

minimizar o consumo e/ou

maximizar a segurança...

3

Os modelos podem ser determinísticos ou estocásticos. Nos modelos determinís-ticos conhecem-se, à partida, os valores de todos os parâmetros do problema. Nosmodelos estocásticos, normalmente, o que se conhece são as funções distribuição deprobabilidade dos valores dos parâmetros envolvidos.Iremos, neste curso, abordar só modelos determinísticos.Pode-se ainda considerar a divisão dos modelos em contínuos e discretos, con-

forme as variáveis envolvidas possam tomar valores reais ou inteiros. Na sua formamais geral, ummodelo de optimização determinístico contínuo pode ser representadodo seguinte modo:

Minimizar f(x)Sujeito a hi(x) = 0 i = 1; :::;mh

gj(x) � 0 j = 1; :::;mg

x 2 Rn

em que f; hi e gj : Rn ! R são funções contínuas.Os modelos que vamos estudar são casos muito particulares desta formulação

geral, em que se identi�cam perfeitamente certas propriedades das funções envolvi-das.

1.1 Programação Linear

Um modelo de programação linear envolve a optimização de uma função linearsujeita a restrições lineares nas variáveis.Seja, por exemplo:

Minimizar c1x1 + c2x2 + :::+ cnxn

sujeito a a11x1 + a12x2 + :::+ a1nxn � b1a21x1 + a22x2 + :::+ a2nxn � b2� � � � � � � � � � � �am1x1 + am2x2 + :::+ amnxn � bmx1; x2; :::; xn � 0

(1.1)

A c1x1 + c2x2 + � � � + cnxn chama-se função objectivo. É costume representaresta função por z. As valores c1; c2; :::; cn dá-se o nome de custos e x1; x2; � � � ; xn sãoas variáveis de decisão. As desigualdades representam a restrições. Os coe�cientesaij; i = 1; :::;m; j = 1; :::; n, são chamados coe�cientes tecnológicos e formam

4

uma matriz A =

26664a11 a12 � � � a1na21 a22 � � � a2n...

.... . .

...am1 am2 � � � amn

37775 chamada matriz das restrições. O vector

b =

26664b1b2...bm

37775 é chamado termo independente. As restrições x1; x2; :::; xn � 0 são

chamadas restrições de não negatividade. A um vector x = [x1; x2; :::; xn]T que

satisfaz todas as restrições chama-se solução admissível. Ao conjunto de soluçõesadmissíveis chama-se região admissível. Usando notação matricial, o problema (1.1)pode ser escrito abreviadamente:

Minimizar cTxSujeito a Ax � b

x � 0Usa-se a seguinte de�nição: x; y 2 Rn; x � y () xi � yi; i = 1; :::; nPara que um problema de optimização possa ser representado como um programa

linear é necessário que várias condições se veri�quem, sendo as principais:

I. Proporcionalidade: Dada uma variável xj a sua contribuição para o custoé cjxj e a sua contribuição para a restrição i é aijxj. Isto é, se o valor de xjpassa, por exemplo, para o dobro a sua contribuição também passará para odobro.

II. Aditividade: Isto é o custo total é a soma dos custos individuais e a con-tribuição total para a restrição i é a soma das contribuições individuais.

III. Divisibilidade: As variáveis de decisão podem tomar qualquer valor real.

IV. Determinismo: Os coe�cientes cj, aij, e bi são conhecidos sem qualquerfactor probabilistico

O problema seguinte é um exemplo clássico dum programa linear onde se podemconstatar estas condições.

5

O Problema da Mistura Óptima

Uma fábrica produz dois tipos de fertilizantes chamadosfosfatados e não-fosfatados.Para os produzir utiliza três tipos de matérias-primas do seguinte modo:

ton de matéria prima para uma ton ton/mêsmatéria-prima fosfatado não-fosfatado disponíveis

1 2 1 15002 1 1 12003 1 0 500

preço/ton 15 10

Quanto deve ser produzido de cada tipo de fertilizante de modo a maximizar asvendas?

Prepara-se uma lista das variáveis de decisão do problema. Esta lista deve ser talque, a partir da solução óptima, seja possível de�nir uma política que implementeessa solução. Neste caso temos:

� x1 $ toneladas de fertilizante fosfatado a serem fabricadas

� x2 $ toneladas de fertilizante não-fosfatado a serem fabricadas

Associada a cada variável do problema está uma actividade que deve ser execu-tada. Neste problema há duas actividades:

� Actividade 1: Fabricar uma tonelada de fertilizante fosfatado

� Actividade 2: Fabricar uma tonelada de fertilizante não-fosfatado

O valor das variáveis do problema de�nem o nível ao qual estas actividades devemser executadas.A formulação do programa linear exige que determinados pressupostos se veri-

�quem:

6

I. Proporcionalidade

São necessárias 2 toneladas de matéria-prima 1 para fabricar 1 tonelada de fertili-zante fosfatado. A proporcionalidade implica que 2x1 toneladas de matéria-prima1 são necessárias para fabricar x1 toneladas de fertilizante fosfatado para qualquerx1 � 0. De um modo geral aij unidades de matéria-prima i são consumidas aoefectuar a actividade j a nível 1, ou seja, aijxj unidades da matéria-prima i sãoconsumidas ao efectuar a actividade j ao nível xj com xj � 0. Também, pelaproporcionalidade, como vender uma tonelada de fertilizante fosfatado rende 15u.m., x1 toneladas do mesmo rendem 15x1 para qualquer x1 � 0.

II. Aditividade

São necessárias duas toneladas de matéria-prima 1 para fabricar uma toneladade fertillizante fosfatado e uma tonelada da mesma matéria prima para fabricar umatonelada de fertilizante não-fosfatado. A aditividade implica que 2x1+x2 toneladasde matéria prima 1 são necessárias para fabricar x1 toneladas de fertilizante fosfatadoe x2 toneladas de fertilizante não-fosfatado para quaisquer x1 � 0 e x2 � 0. Aaditividade garante que a função objectivo z(x) = z(x1; x2; :::; xn) pode ser escritacomo uma soma de n funções envolvendo cada qual só uma variável do modelo, istoé: z(x) = z1(x1)+ :::+zn(xn) em que zj(xj) mede a contribuição da variável xj paraa função objectivo.

III. Divisibilidade

Presume-se que cada variável pode tomar qualquer valor real no seu intervalo devariação.

IV. Determinismo

Todos os valores dos parâmetros são conhecidos sem ambiguidade.

Para formular o problema escrevem-se todas as restrições e a função objectivo.

� Restrições de não negatividade: as variáveis x1 e x2 não devem ser negativaspois não faria qualquer sentido:

x1 � 0;x2 � 0

7

� As disponibilidades de matéria prima também vão conduzir a restrições:

2x1 + x2 � 1500 (matéria-prima 1)

x1 + x2 � 1200 (matéria-prima 2)

x1 � 500 (matéria-prima 3)

� A função objectivo deve representar o objectivo a alcançar: maximizar as ven-das. Ou seja tem-se z1(x1) = 15x1 (total das vendas de fertilizante fosfatado)e z2(x2) = 10x2 (total das vendas de fertilizante não fosfatado) sendo o totaldas vendas dado por: z(x) = 15x1 + 10x2.

Temos assim o programa linear (LP) formulado na forma usual:

Minimizar z(x) = 15x1 + 10x2

sujeito a 2x1 + x2 � 1500x1 + x2 � 1200x1 � 500x1 � 0; x2 � 0

Como temos um problema com apenas duas variáveis de decisão, a região admis-sível pode ser representada gra�camente no plano. Trata-se de uma região convexasituada no primeiro quadrante.

8

Cada ponto desta região corresponde a uma solução admissível. A solução doproblema corresponde ao(s) ponto(s) desta região que torna(m) máxima a funçãoz. Note-se que z é uma função linear de domínio R2. Os conjuntos de nível destafunção representam-se geometricamente por rectas paralelas de declive �1:5. Asrectas desta família têm equações da forma 15x1+10x2 = k, com k 2 R. No grá�coseguinte apresentam-se alguns elementos dessa família de rectas, correspondentes ak = 10000, k = 12000 e k = 13500.

Vê-se que para valores de k superiores a 13500 as rectas desta família deixarãode intersectar a região admissível. É este o valor óptimo para a função z e o ponto

óptimo encontra-se resolvendo o sistema�2x1 + x2 = 1500x1 + x2 = 1200

É claro que este processo geométrico de resolução só é possível se o problemanão tiver mais do que 2 variáveis de decisão.Como se viu, a região admissível é uma região convexa e a função objectivo

também é uma função convexa (ver à frente as de�nições exactas). Então paraestarmos aptos a encontrar um processo de resolver o problema temos que sabermais qualquer coisa sobre regiões e funções convexas.

1.2 Tópicos sobre convexidade

Todos os resultados que se seguem são válidos num espaço euclidiano de dimensão n

De�nição 1.2.1 (Conjunto convexo): Um conjunto S diz-se convexo se o se-gmento de recta que une dois pontos distintos de S está contido em S.

Ou seja: 8x1; x2 2 S;8� 2 [0; 1]; z = �x1 + (1� �)x2 2 S

9

Exemplo de uma região convexa

Exemplo de uma região não convexa

De�nição 1.2.2 (Combinação linear convexa): Considere-se o conjunto de

pontos fx1; x2; :::; xkg � En e seja, z =kPi=1

�ixi tal quekPi=1

�i = 1 e �i � 0;

i = 1; :::; k: A z chama-se combinação linear convexa de fx1; x2; :::; xkg.

De�nição 1.2.3 (Combinação a�m): Considere-se o conjunto de pontos

S = fx1; x2; :::; xkg e seja z =kPi=1

�ixi tal quekPi=1

�i = 1. A z chama-se combinação

a�m de fx1; x2; :::; xkg.

Exemplos de conjuntos convexos:

1. S = f(x1; x2; x3) 2 E3 : x1 + 2x2 � x3 = 4g (geometricamente, S é um plano).De um modo geral, S = fx 2 En : pTx = ag, com p 2 En , p 6= 0, � 2 R é umhiperplano em En e é convexo

2. S = f(x1; x2; x3) 2 E3 : x1 + 2x2 � x3 � 4g (geometricamente, S é um semi-espaço). De um modo geral, S = fx 2 En : pTx � (�)�g, com p 2 En , p 6= 0,� 2 R é um semi-espaço em En e é convexo.

3. S = f(x1; x2; x3) 2 E3 : x1+2x2�x3 � 4^2x1�x2+x3 � 6g (geometricamente,S é a intersecção de dois semi-espaços)

10

De um modo geral, S = fx 2 En : Ax � (�)bg, com A uma matriz m � n e bum vector de m componentes, é um conjunto convexo, intersecção de semi-espaçosem En .

Lema 1.2.1 Sejam S1 e S2 conjuntos convexos. Então

1. S1 \ S2 é convexo

1. S1 � S2 = fx1 + x2 : x1 2 S1 ^ x2 2 S2g é convexo

2. S1 S2 = fx1 � x2 : x1 2 S1 ^ x2 2 S2g é convexo

De�nição 1.2.4 (Envólucro Convexo): Chama-se envólucro convexo de S, H(S),ao conjunto de todas as combinações lineares convexas de elementos de S.

Lema 1.2.2 H(S) é o menor conjunto convexo que contém S e é a intersecção detodos os conjuntos convexos que contêm S.

De�nição 1.2.5 (Envólucro A�m): Chama-se envólucro a�m de S ao conjuntode todas as combinações a�ns de elementos de S.

Exemplo 1.2.1 Envólucro a�m de dois pontos distintos: a recta que os contém.

Exemplo 1.2.2 Envólucro convexo de dois pontos distintos: o segmento que os une.

De�nição 1.2.6 (Politopo): Chama-se politopo ao envólucro convexo de um número�nito de pontos.

De�nição 1.2.7 (Simplex): Se fx1; x2; :::; xk+1g são pontos independentes do pontode vista a�m, isto é, se fxk+1�x1; xk+1�x2; :::; xk+1�xkg são linearmente indepen-dentes, então H(fx1; x2; :::; xk+1g) é chamado simplex, com vértices x1; x2; :::; xk+1.

Da de�nição resulta óbvio que em En não há qualquer simplex com mais de n+1vértices.

De�nição 1.2.8 (Poliedro): S é um poliedro se é a intersecção de um número�nito de semi-espaços fechados.

11

De�nição 1.2.9 (Ponto extremo): Seja S 6= � um convexo fechado. Chama-seponto extremo a um ponto x de S tal que

x = (�x1 + (1� �)x2) 2 S ^ � 2]0; 1[=) x = x1 = x2

De�nição 1.2.10 (Direcção): Seja S 6= � um convexo fechado. Chama-se di-recção de S a d 6= 0, tal que

8x 2 S;8� � 0; x+ �d 2 S:

Se d1 e d2 são direcções, d1 6= d2 , 8� > 0; d1 6= �d2

De�nição 1.2.11 (Direcção extrema): Seja S 6= � um convexo fechado. Chama-se direcção extrema a uma direcção d de S se

d = �1d1 + �2d2 2 S ^ �1; �2 > 0 =) d = d1 = d2

SejaT = fx 2 Rp : Dx � b; x � 0g;

com D 2 Rm�p e b2 Rm , sendo D uma matriz de característica completa. E seja

S = f(x; s) 2 Rp+m : Dx� Is = b; x � 0; s � 0g:

É possível construir uma bijecção entre S e T , pelo que se pode passar a trabalharcom conjuntos da forma

S = fx 2 Rn : Ax = b; x � 0g; (1.2)

sendo este último tipo de conjuntos de muito mais fácil tratamento.

Teorema 1.2.3 (Caracterização dos pontos extremos de regiões da forma1.2) Seja S = fx : Ax = b; x � 0g, em que A é uma matriz m � n (m < n) decaracterística completa.x é um ponto extremo de S se e só se pode ser encontradauma partição de A = [B N ] tal que e B�1b � 0. (diz-se que x é uma solução básicaadmissível)

Demonstração. (é preciso demonstrar uma equivalência, demonstra-se umaimplicação de cada vez)1a implicação:

12

Supor A = [B N ] e x =�xBxN

�=

�B�1b0

�com B�1b � 0. Como Ax = b

e x � 0, então x é um elemento de S. Supor x = �x1 + (1 � �)x2, com x1 e x2elementos de S e � 2]0; 1[. Considere-se para x1 e x2 a mesma partição que se

considerou para x: x1 =�x1Bx1N

�x2 =

�x2Bx2N

�:

x = �x1 + (1� �)x2 ,�B�1b0

�= �

�x1Bx1N

�+ (1� �)

�x2Bx2N

�,

, 0 = �x1N + (1� �)x2N ^B�1b = �x1B + (1� �)x2BComo é � > 0, (1� �) > 0, x1N � 0 e x2N � 0, então terá que ser x1N = x2N = 0

x1 é elemento de S, por isso Ax1 = b. Ou seja, [B N ]

�x1B0

�= b. O que é o

mesmo que dizer que x1B = B�1b. Do mesmo modo se conclui que x2B = B�1b. Ouseja que x = x1 = x2. Conclui-se assim que x é um ponto extremo.

2a implicaçãoSeja x um ponto extremo de S. Sem perda de generalidade escreva-se

x = (x1; x2; :::; xk; 0; 0; :::; 0)T ; com x1; x2; :::; xk > 0:

Começa-se por demonstrar que as k colunas da matriz A; a1; a2; :::; ak, correspon-dentes, são linearmente independentes. Por absurdo, supor a existência de �1; �2; :::; �k,

não todos nulos, tais quekPi=0

�iai = 0. Considere-se o vector

� = (�1; �2; :::; �k; 0; 0; :::; 0)T

e os vectoresx1 = x+ �� e x2 = x� ��;

sendo � um real positivo convenientemente escolhido de modo a que ambos os vec-tores sejam não negativos.

Ax1 = Ax+ �A� = b+ �

kXi=0

�iai = b

e

13

Ax2 = Ax� �A� = b� �kXi=0

�iai = b:

Então x1 e x2 são elementos de S. Além disso, x1 6= x2, pois � > 0 e � 6= 0.Masx = 1

2x1 +

12x2. Então x não seria ponto extremo. Conclui-se assim que as colunas

da matriz A a1; a2; :::; ak são linearmente independentes. Como A á uma matriz decaracterística completa, é possível juntar m � k colunas às k primeiras de modo aobter uma matriz B, de dimensão m, não singular e A = [B N ] e x =

�xBxN

�=�

B�1b0

�com B�1b � 0

Corolário 1.2.4 O número de pontos extremos de S é �nito.

O número de pontos extremos é limitado pelo número máximo de maneiras de

escolher m colunas das n da matriz, ou sejan!

m!(n�m)!

Teorema 1.2.5 (existência de pontos extremos nas regiões da forma 1.2):Seja S = fx : Ax = b; x � 0g, em que A é uma matriz m � n (m < n) decaracterística completa e S 6= �, então S tem pelo menos um ponto extremo.

Demonstração. Escolha-se um ponto x de S. Sem perda de generalidadesuponha-se x = (x1; x2; :::; xk; 0; 0; :::; 0)T , com x1; x2; :::; xk > 0. Se a1; a2; :::; ak sãolinearmente independentes, então k < m e x é um ponto extremo. Caso contrário,

há escalares �1; �2; :::; �k não todos nulos tais quekPi=0

�iai = 0. Determine-se

� = min1�j�k

�xj�j: �j > 0

�=xr�r:

E de�na-se x0 do seguinte modo:

xj0 =�xj � ��j; j = 1; � � � ; k0; j = k + 1; � � � ; n

Do modo como se de�niu � é óbvio que x0 � 0 e que a componente de ordem r � ké nula. Isto é, x0 tem, no máximo, k � 1 componentes positivas.Além disso Ax0 = bEntão x0 é um elemento de S que tem, no máximo, k� 1 componentes positivas. O

14

processo pode-se repetir até que as componentes positivas correspondam a colunaslinearmente independentes, obtendo-se assim um ponto extremo.Considere-se novamente S = fx : Ax = b; x � 0g, em que A é uma matriz

m� n(m < n) de característica completa e S 6= �. Se d é uma direcção de S, pelade�nição, 8x 2 S;8� � 0; x+ �d 2 S. Então A(x+ �d) = b. Mas,

A(x+ �d) = Ax+ �Ad = b+ �Ad = b

e, portanto, Ad = 0. Sabemos assim que, para este conjunto S, d 6= 0 é uma direcçãose d � 0 e Ad = 0.

Teorema 1.2.6 (Caracterização das direcções extremas de conjuntos daforma 1.2): Seja S = fx : Ax = b; x � 0g, em que A é uma matriz m�n (m < n)de característica completa e S 6= �. é uma direcção extrema de S se e só se A puderser decomposto em A = [B N ] tal que B�1aj � 0 para alguma coluna aj 2 N e

d é um múltiplo positivo de d =��B�1ajej

�, em que ej é um vector de dimensão

(n�m) cujas componentes são nulas, excepto a de ordem j que é igual a 1.

Demonstração. Se B�1aj � 0 então d � 0 e d 6= 0 (pois tem pelo menos umacomponente não nula). Além disso

Ad =�B N

� � �B�1ajej

�= �aj + aj = 0:

Então d é uma direcção. Para mostrar que d é uma direcção extrema, supord = �1d1 + �2d2 com �1; �2 > 0 e d1 e d2 direcções de S. Note-se que d tem(n�m� 1) componentes nulas, por isso d1 e d2 também as devem ter. Seja

d1 = �1

�d1Bej

�e d2 = �2

�d2Bej

�:

Como tem que ser Ad1 = 0 e Ad2 = 0, então d1B = d2B = �B�1aj.Então d1 e d2não são distintos e, por isso, d é uma direcção extrema. Como d é múltiplo de dtambém o é.Inversamente:Supor d uma direcção extrema de S. Sem perda de generalidade suponha-se

d = (d1; :::; dk; 0; :::; dj; :::; 0)T , com di > 0, i = 1; :::; k e i = j. Tal como no teorema

anterior, pode-se mostrar que a1; :::; ak são linearmente independentes, pois, caso

15

não o fossem, existiriam escalares �1; �2; :::; �k não todos nulos tais quekPi=0

�iai = 0.

Seja � = (�1; �2; :::; �k; 0; 0; :::; 0)T e de�na-se d1 = d + �� e d2 = d � ��, sendo �um real positivo convenientemente escolhido de modo a que d1 e d2 sejam positivos.É claro que Ad1 = Ad2 = 0, logo d1 e d2 são direcções e, além disso, d = 1

2d1 +

12d2

e então não seria uma direcção extrema.É claro que k � m. Então existem m � kcolunas em A que se podem juntar a estas k de modo a formar um conjunto de mcolunas linearmente independente. Sem perda de generalidade suponha-se que sejunta ak+1; :::; am. Seja B = [a1; :::; am]. B é invertível. 0 = Ad = B bd + ajdj, emque bd é o vector das primeiras m componentes de d. Então bd = �djB�1aj. Isto

é, o vector d é da forma d = dj

��B�1ajej

�. Note-se que d � 0 e dj > 0, então

B�1aj � 0:

Teorema 1.2.7 (da Representação): Seja S = fx : Ax = b; x � 0g 6= �, em queA é uma matriz m � n(m < n) de característica completa. Seja fx1; x2; :::; xkg oconjunto de todos os pontos extremos de S e fd1; d2; :::; dpg o conjunto de todas asdirecções extremas de S. Então x 2 S se e só se x pode ser escrito do seguinte modo

x =kPj=1

�jxj +pPj=1

�jdj, com ,kPj=1

�j = 1; �j � 0; j = 1; :::; k e �j � 0; j = 1; :::; p.

Demonstração. Começa-se por construir o conjunto T do seguinte modo:

T = fx 2 En : x =kXj=1

�jxj+

pXj=1

�jdj;kXj=1

�j = 1; �j � 0; j = 1; :::; k e �j � 0; j = 1; :::; pg:

T é um conjunto convexo e fechado.Então tem pelo menos um ponto extremo. LogoT 6= �. É óbvio que T � S. Para mostrar que T = S é então necessário mostrarque S � T . Por absurdo, suponha-se que existe z 2 S, tal que z =2 T .Seja qTx = �, o plano que separa T e z (existe, porque T é convexo e fechado e

z =2 T ). Suponhamos que este plano é tal que qT z > � e qTy � �, para todo o y deT . Ou seja

qT (kXj=1

�jxj +

pXj=1

�jdj) � a:

Fazendo, nesta expressão, �j = 0, para todo o j e �j = 0 para j 6= i e �i =1, vem qTxj � �, para j = 1; :::; k. Além disso, como �j pode ser feito crescer

16

arbitrariamente, para que a condição qT (kPj=1

�jxj +pPj=1

�jdj) � � se veri�que, terá

que ser qTdj � 0: De�ne-se x tal que qTx = max1�j�k

qTxj. Então x é um ponto extremo

de T e qTx � a. Então pode-se encontrar uma partição de A, A = [ B N ], tal

que x =�B�1b0

�e B�1b � 0. Como z 2 S, então Az = b e z � 0. Considerando

z =

�zBzN

�; virá zB = B

�1b�B�1NzN . Então

qT z = qTB�B�1b�B�1NzN

�+ qTNzN :

Mas, sabe-se queqT z > a � qTy; 8y 2 T;

ou seja, qT z � qTx > 0. Por outro lado:

qT z � qTx = qTB�B�1b�B�1NzN

�+ qTNzN � qTNB�1b = (qTN � qTBB�1N)zN > 0:

Como zN � 0, então, há pelo menos um j � m+ 1, tal que qj � qTBB�1aj > 0. Sejayj = B

�1aj.

Supor yj � 0. Considere-se o vector dj =��yjej

�, em que ej é um vector de

dimensão n�m, com todas as componentes nulas, à excepção da de ordem j, que éigual a 1. Mas, então, dj é uma direcção extrema de S e, por isso, qTdj � 0. MasqTdj = qj � qTBB�1aj > 0 . Então yj não é não positivo (isto é, tem pelo menos umacomponente positiva). Construa-se o vector

x =

�b0

�+ �

��yjej

�;

sendo b = B�1b e � escolhido de acordo com � = min

�biyij: yij > 0

�=bryrj. Deste

modo x � 0 e x tem no máximo m componentes positivas. Por outro lado,

Ax = Bb+ �B(�yj) + �aj = BB�1b� �BB�1aj + �aj = b:

Logo, x 2 S e, como yrj 6= 0, os vectores a1; :::; ar�1; ar+1; :::; am; aj são linearmenteindependentes (ver demonstração anterior). Logo x é um ponto extremo.

qTx =�qTB qTN

��� b0

�+ �

��yjej

��= qTBb��qTByj+�qTNej = qTx+�(qj�qTBB�1aj);

17

como � > 0 e qj � qTBB�1aj < 0; então qTx > qTx. Isto é, x é um ponto extremo eqTx > qTx! Mas, tinha-se de�nido x de modo a que qTx fosse o maior valor entreos pontos extremos. Então z 2 T e T = S.

Corolário 1.2.8 S = fx : Ax = b; x � 0g, em que A é uma matriz m� n (m < n)de característica completa e S 6= �. S tem pelo menos uma direcção extrema se e sóse S é ilimitado.

Demonstração. Qualquer x de S escreve-se na forma

x =

kXj=1

�jxj +

pXj=1

�jdj; com,kXj=1

�j = 1; �j � 0; j = 1; :::; k e �j � 0; j = 1; :::; p:

Se não há direcções extremas: jjxjj �kPj=1

�jjjxjjj �kPj=1

jjxjjj, então S é limitado.

Reciprocamente, se houver direcções extremas jjxjj não será limitada pois �j podeser arbitrariamente grande e, então, S não seria limitado.

1.3 Programação Linear

Um problema de programação linear é da forma:

Min cTxs:a x 2 S (1.3)

em que S é um poliedro em En:

Teorema 1.3.1 (existência de solução para um programa linear): Con-sidere-se um problema da forma (1.3) em que S = fx2En : Ax = b^x�0g, sendoA uma matriz m�n de característica completa. Seja fx1; x2; :::; xkg o conjunto detodos os pontos extremos de S e fd1; d2; :::; dpg o conjunto de todas as direcções ex-tremas de S. Uma condição necessária e su�ciente para existir uma solução óptima�nita é que cTdj�0; j = 1; :::; p. Se esta condição se veri�car, então há um pontoextremo xi que resolve o problema.

Demonstração. x2S () x =kPj=1

�jxj +pPj=1

�jdj; com,kPj=1

�j = 1; �j � 0; j =

1; :::; k e�j � 0; j = 1; :::; p:

18

Como: cTx = cT

kPj=1

�jxj +pPj=1

�jdj

!, então a seguinte equivalência é válida:

Min cTxs.a Ax = b

x � 0 ()

Min cT

kPj=1

�jxj +pPj=1

�jdj

!s.a

kPj=1

�j = 1

�j � 0; j = 1; :::; k�j � 0; j = 1; :::; p

Note-se que, se para algum j, cTdj < 0, então �j pode crescer sem limite e afunção objectivo não será limitada. Então, é óbvio que, para a solução ser �nitatem que ser cTdj�0; j = 1; :::; p. Neste caso, para minimizar a função objectivo, énecessário escolher �j = 0, para j = 1; :::; p:

1.4 O Método Simplex

Foi o primeiro método a ser proposto para a resolução de problemas lineares e baseia-se nas propriedades dos conjuntos convexos em geral e dos poliedros em particular.O seu funcionamento e convergência são óbvios tendo em atenção os resultadosdemonstrados nas páginas anteriores.Considere-se o problema

Min cTxs:a Ax = b

x � 0

E seja x o ponto extremo correspondente à partição A = [ B N ], ou sejaxB = B

�1b e xN = 0, correspondendo-lhe para a função objectivo o valorcTx = cTBB

�1b:Considere-se x que satisfaçaAx = b e x�0 e considere-se para x a mesma partição

do que para x: BxB +NxN = b=) xB = B�1b�B�1NxN :

Calculando o valor da função objectivo em x, usando esta mesma partição parac, virá:cTx = cTBxB + c

TNxN = c

TB(B

�1b�B�1NxN) + cTNxN =cTBB

�1b+ (cTN � cTBB�1N)xN = cTxB + (cTN � cTBB�1N)xN

19

Então, se (cTN � cTBB�1N)�0, como xN�0, será cTx�cTx e, por isso, x é umponto extremo óptimo.Caso contrário, isto é, se para algum j > m for cj�cTBB�1aj < 0, x não é óptimo,

pois é possível construir um outro elemento de S, onde o valor da função objectivoé menor do que em x, do seguinte modo:

x = x+ �dj, com dj =

��B�1ajej

�e � > 0:

Calculemos o valor da função objectivo neste novo ponto x:

cTx = cTx+ �(cj � cTBB�1aj):

Como cj � cTBB�1aj < 0 e � > 0 , então cTx � cTx .Duas situações podem ocorrer:

Caso 1 yj = B�1aj � 0

Neste caso é Adj = 0 e dj > 0. Então x = x+�dj2S. Portanto, dj é uma direcçãoextrema e o problema é ilimitado.

Caso 2 9i : yij > 0

Seja b = B�1b e de�na-se � do seguinte modo:

� = minf biyij: yij > 0; i = 1; :::;mg:

Seja r o indíce correspondente a esse mínimo. Então x = x + �dj tem, nomáximo, m componentes positivas (pois a componente de ordem r é nula e ade ordem j passa a ser positiva). Nestas condições é fácil demonstrar que ascolunas de A correspondentes são linearmente independentes e x é um pontoextremo com um melhor valor para a função objectivo.

1.5 Algoritmo Simplex

Passo inicial: Encontrar um ponto extremo x a que corresponde a base B.

Passo principal: Calcular cTN � cTBB�1N . Se este vector for não negativo oprocesso termina pois x é um extremo óptimo.

Caso contrário, toma-se j tal que cj � cTBB�1aj < 0. Se yj = B�1aj � 0, oprocesso termina pois encontrou-se uma aresta, x + �dj, ao longo da qual a

20

função objectivo é ilimitada. Se alguma componente de yj for positiva de�ne-se� como o mínimo do conjunto

f biyij: yij > 0; i = 1; :::;mg =

bryrj

� 0

e forma-se a nova base trocando em B a coluna ar por aj. Repete-se atéterminar.

Como, em cada iteração, o valor da função objectivo decresce, há a garantia denão repetir extremos e, como há um número �nito de extremos, o processo descritotermina num número �nito de iterações.Se br = 0 (solução degenerada), então � = 0 e a função mantém o mesmo valor

em iterações consecutivas, mantendo o mesmo extremo mas mudando de base. Nestecaso há possibilidade de entrar em ciclo, mas essas situações são raras.

1.5.1 O método simplex em forma de quadro

xTB xTNb B Nz cTB cTN

Se o traço jj for interpretado como um sinal de =, este quadro representa Ax = be z = cTx.Multiplicando a segunda linha por B�1 e depois, multiplicando-a por -cTB e so-

mando à terceira linha obtém-se o seguinte quadro:

xTB xTNB�1b I B�1N

z � cTBB�1b 0 cTN � cTBB�1N

Deste modo lê-se directamente na primeira coluna os valores das variáveis básicase na última linha os valores de z e de cj � cTBB�1aj necessários para avaliar se asolução é ou não óptima. De notar que a coluna do quadro correspondente à variávelxj contém o vector yj = B�1aj:Se, inicialmente, for B = I este quadro é exactamente igual ao anterior (com a

possível excepção da última linha, que poderá ter que ser ajustada de modo a queos custos das variáveis básicas sejam todos nulos) e tudo se torna mais simples. Istosigni�ca que na matriz A há m colunas que produzem a matriz identidade e, por-tanto, que há um ponto extremo a que corresponde como base a matriz identidade.

21

Muitas vezes não existem na matriz A colunas su�cientes para fazer inicialmenteB = I. Nesses casos, é costume recorrer ao método das duas fases que tem comoobjectivo encontrar um ponto extremo do conjunto admissível. Começa-se por intro-duzir no problema variáveis arti�ciais (que têm que ser não negativas) em númerosu�ciente para que nas colunas de A apareça uma matriz identidade. É claro queo problema obtido tem uma outra região admissível e só será equivalente ao prob-lema proposto desde que as variáveis arti�ciais sejam todas nulas. Tal consegue-secomeçando por resolver o problema que consiste em minimizar uma funçãoW que éa soma das variáveis arti�ciais nessa nova região. Quando se obtém o mínimo desseproblema, dois casos podem acontecer:

I) W > 0

II) W = 0

No primeiro caso, há variáveis arti�ciais básicas com valor positivo. Isto querdizer que não é possível escrever uma base admissível só com colunas de A e que,por isso, o problema não tem qualquer solução admissível (isto é, o conjunto S évazio)No segundo caso ainda duas situações podem acontecer:

a) não há variáveis arti�ciais na base, isto é, obteve-se um ponto extremo daregião admissível do problema inicial e pode-se começar a procurar o óptimoda função cTx

b) ainda há variáveis arti�ciais na base, que têm obviamente o valor nulo. Nestecaso ainda há duas hipóteses diferentes:

i) as linhas correspondentes às variáveis arti�ciais são nulas (isto é, essasequações são combinação linear das outras) e podem ser retiradas pas-sando a resolver-se um problema de dimensão inferior. Neste caso oproblema inicial teria uma restrições redundantes.

ii) as linhas não são completamente nulas e as variáveis arti�ciais podem serretiradas da base por troca com variáveis não arti�ciais obtendo-se assimuma solução degenerada.

O algoritmo que foi descrito aplica-se a programas lineares na chamada formastandard:

22

Min cTxs.a Ax = b

x � 0Mas qualquer outro tipo de programa linear pode facilmente ser transformado neste,por exemplo:

- restrições de � ou de � podem ser transformadas em igualdades acrescentandovariáveis de afastamento com o sinal adequado;

- variáveis sem restrição de sinal, xi2 R, podem ser tratadas como a diferença deduas variáveis não negativas xi = x+i � x�i . Note-se que as colunas destasduas variáveis vão ser simétricas uma da outra e que, portanto, não podem seras duas simultaneamente básicas.

- variáveis com limite inferior 6= 0, neste caso, se for xi�a, basta fazer a mudançade variável x

0i = xi � a�0.

1.5.2 Exemplo de aplicação do método simplex

DeterminarMax �x1 � 2x2 + x3s.a x1 + 3x2 + x3 � 4

x1 + 2x2 � x3 � 6x1 + x3 � 12x1; x2; x3 � 0

Comecemos por escrever o problema na forma standard:

Min x1 + 2x2 � x3s.a x1 + 3x2 + x3 � x4 = 4

x1 + 2x2 � x3 � x5 = 6x1 + x3 + x6 = 12x1; x2; x3 � 0

ou seja:

A =

24 1 3 1 �1 0 01 2 �1 0 �1 01 0 1 0 0 1

35 :

23

Como nas colunas da matriz A não se encontram todas as colunas necessárias paracomeçar com B = I, é necessário acrescentar duas variáveis arti�ciais, x7 e x8, a quecorrespondem as colunas a7 = [ 1 0 0 ]T e a8 = [ 0 1 0 ]T : A função objectivoda primeira fase escreve-se, então, w = x7 + x8 e o objectivo da primeira fase éminimizar w.Quadro inicial:

B�1b x1 x2 x3 x4 x5 x6 x7 x8x7 4 1 3 1 �1 0 0 1 0x8 6 1 2 �1 0 �1 0 0 1x9 12 1 0 1 0 0 1 0 0

w 0 0 0 0 0 0 1 1

Para começar é necessário ter a função objectivo escrita só à custa das variáveis nãobásicas, isto é, na linha dos custos devem aparecer zeros nas colunas correspondentesàs variáveis básicas. Para esse efeito subtraem-se as duas primeiras linhas à última.

B�1b x1 x2 x3 x4 x5 x6 x7 x8 bi=yijx7 4 1 3 1 �1 0 0 1 0 4=3x8 6 1 2 �1 0 �1 0 0 1 6=2x6 12 1 0 1 0 0 1 0 0

w � 10 �2 �5 0 1 1 0 0 0

"

B�1b x1 x2 x3 x4 x5 x6 x7 x8 bi=yijx2 4=3 1=3 1 1=3 �1=3 0 0 1=3 0

x8 10=3 1=3 0 �5=3 2=3 �1 0 �2=3 1 10=3=2=3

x6 12 1 0 1 0 0 1 0 0

w � 10=3 �1=3 0 5=3 �1=3 1 0 5=3 0

"

B�1b x1 x2 x3 x4 x5 x6 x7 x8x2 3 1=2 1 1=2 0 �1=2 0 0 1=2x4 5 1=2 0 �5=2 1 �3=2 0 �1 3=2x6 12 1 0 1 0 0 1 0 0

w 0 0 0 0 0 0 1 1

24

Chegou-se assim ao �m da primeira fase com a indicação de óptimo para w e w = 0.Além disso, não há variáveis arti�ciais na base pelo que se pode começar de imediatoa segunda fase passando a trabalhar com a função objectivo do problema inicial.

B�1b x1 x2 x3 x4 x5 x6x2 3 1=2 1 1=2 0 �1=2 0x4 5 1=2 0 �5=2 1 �3=2 0x6 12 1 0 1 0 0 1

z 1 2 �1 0 0 0

Antes de começar é necessário anular os custos das variáveis básicas:

B�1b x1 x2 x3 x4 x5 x6

x2 3 1=2 1 1=2 0 �1=2 0

x4 5 1=2 0 �5=2 1 �3=2 0x6 12 1 0 1 0 0 1

z � 6 0 0 0 0 1 0

Temos assim também um óptimo para a função z. Pois cTN � cTBB�1N�0.De notar ainda que, do facto de c1�cTBB�1a1 = 0 pode-se concluir que a variável

x1 pode ser tornada básica sem que o valor de z seja alterado:

B�1b x1 x2 x3 x4 x5 x6x1 6 1 2 1=2 0 �1=2 0x4 2 0 �1 �5=2 1 �3=2 0x6 6 0 �2 1 0 0 1

z � 6 0 0 0 0 1 0

Então temos 2 pontos extremos que são óptimos, obviamente com o mesmo valormínimo de z, que é 6: (x1; x2; x3) = (0; 3; 0) e (x1; x2; x3) = (6; 0; 0). O segmento queune estes dois vértices é uma aresta do poliedro admissível e em todos os seus pontosa função z tem o mesmo valor, isto é, todos os pontos sobre aresta correspondem aoóptimo.(x1; x2; x3) = �(0; 3; 0) + (1� �)(6; 0; 0) = (6� 6�; 3�; 0)(1; 2;�1)T (6� 6�; 3�; 0) = 6� 6�+ 6� = 6Como a função objectivo foi multiplicada por �1, para passar do máximo para

o mínimo, então o valor óptimo de z é �6.

25

1.6 Dualidade em Programação Linear

Considerem-se os problemas

P: Min cTxs.a Ax = b

x � 0

D: Max bTys.a ATy � c

y sem restrição

Teorema 1.6.1 Para o par de problemas P e D são válidos os seguintes resultados:a) cTx�bTy , para qualquer x solução admissível de P e qualquer y solução

admissível de D.b) Se P é ilimitado então D não tem solução e se D é ilimitado então P não tem

solução.c) Se P e D têm solução, então ambos têm soluções óptimas e o valor da função

objectivo é igual para ambos.

Demonstração. a) Seja x solução admissível de P , então Ax = b e x�0. Sejay solução admissível de D, então ATy�c.ATy�c=)c�ATy=)cT�yTA e, além disso,

�cT�yTA ^ x�0

�=)cTx�yTAx=)

cTx�yT bb) Decorre imediatamente de a): Se P é ilimitado, D não pode ter qualquer

solução admissível, pois, caso contrário, haveria um limite para a função objectivo deP . E, do mesmo modo,se D é ilimitado, P não pode ter qualquer solução admissível,pois, caso contrário, haveria um limite para a função objectivo de D.

c) Seja x solução óptima de P . Então x = [ xTB xTN ] e xB = B�1b , xN = 0.

Considere-se yT = cTBB�1.

Então yTA = cTBB�1A = cTBB

�1 � B N�=�cTB cTBB

�1N�

ATy�c=)cT�yTA=)�cTB cTN

���cTB cTBB

�1N�

Como x é óptimo, então cTN � cTBB�1N�0, ou seja cTBB�1N � cTN , donde seconclui que y é solução de D.Além disso yT b = cTBB

�1b = cTx Como, por a), 8y solução de D é bTy�cTx ,então 8y solução de D é bTy�bTy e y é óptimo.

Corolário 1.6.2 Se D não tem solução, então P é ilimitado ou não tem solução.Se P não tem solução então D ou é ilimitado ou não tem solução.

26

Demonstração. Se D não tem solução, não tem também uma solução óptimae P não poderá ter uma solução óptima, pois se a tivesse seria possível encontraruma solução óptima de D a partir dela. Então P ou é ilimitado ou não tem solução.De modo análogo se pode argumentar a segunda parte.

Corolário 1.6.3 Seja A uma matriz m � n e c um vector com n componentes.Então exactamente um dos dois sistemas tem solução:Sistema 1: Ax�0 e cTx > 0; x 2 RnSistema 2: ATy = c e y�0; y 2 Rm

Demonstração.

Considere-seP: Min 0Tx

s.a ATy = cy � 0 o dual é

D: Max cTys.a Ax � 0

Dizer que o sistema 2 não tem solução é o mesmo que dizer que o problemaP não tem solução. Como o problema D tem pelo menos uma solução (x = 0 ésolução) então D é ilimitado, isto é, o sistema 1 tem solução. Se o sistema 1 temsolução, então o valor óptimo da função objectivo do problema D é positivo. Mas,o valor da função objectivo do problema P é sempre zero o que não é compatívelcom o facto de o valor óptimo de D ser positivo. Então P não pode ter solução e Dtendo solução, será ilimitado.

Corolário 1.6.4 (condição de complementaridade e caracterização do óp-timo)Considerem-se os problemas

P : Min cTxs.a Ax = b

x � 0e

D : Max bTys.a ATy � c

y sem restrição

Seja x uma solução admissível de P e y uma solução admissível de D. Entãox e y são óptimos para P e D, respectivamente, se e só se v = c � ATy é tal quevixi = 0 para i = 1; :::; n:

Demonstração. x e y são admissíveis =) Ax = b; x�0 e v = c� ATy � 0v = c� ATy =) c = v + ATy

cTx =�v + ATy

�Tx = vTx+ yTAx = vTx+ yT b =) vTx = cTx� bTy

Ora se as soluções são óptimas então os valores das funções objectivo são iguaise, por isso, é vTx = 0. Mas, como x�0 e v�0, então tem que ser vixi = 0 para

27

i = 1; :::; n: Reciprocamente, se vixi = 0 para i = 1; :::; n:, então vTx = 0 ecTx = bTy, o que implica que as soluções são óptimas.

Foram estudadas as relações entre os problemas P e D na forma

P : Min cTx D : Max bTys.a Ax = b s.a ATy � c

x � 0 y sem restrição

Estas relações podem ser generalizadas a outro tipo de problemas que se podemconverter nestes.SejaP : Min cTx

s.a Ax � bx � 0

qual será o problema D que lhe corresponde?

Este problema pode ser reduzido à forma standard fazendo:

P : Min cTx+ 0T ss.a Ax� Is = b

x � 0; s � 0

e então temos o problema D dado por:D : Max bTy

s.a ATy � c�Is � 0

ou sejaD : Max bTy

s.a ATy � cy � 0

28

De modo análogo se podem estabelecer outras relações entre problemas P e D.Seguem-se alguns exemplos:

P : Min cTxs.a Ax = b

x � 0

D : Max bTys.a ATy � c

y sem restrição

P : Min cTxs.a Ax � b

x � 0

D : Max bTys.a ATy � c

y � 0

P : Max cTxs.a Ax � b

x � 0

D : Min bTys.a ATy � c

y � 0

P : Max cTxs.a Ax � b

x sem restrição

D : Min bTys.a ATy = c

y � 0

Para todos os pares de problemas, que se dizem duais, são válidos todos osresultados que foram estabelecidos para a forma standard.Um problema pode não aparecer em nenhuma destas formas, podendo, num

mesmo problema, coexistirem restrições em forma de igualdade e desigualdade, umascom� e outras com�, variáveis com e sem restrição de sinal e funções cujo objectivoseja maximizar ou minimizar.Para escrever o dual de um problema deste tipo há que começar por escrevê-lo

numa das formas estudadas e depois escrever o dual seguindo as regras.Da observação de problemas duais pode-se concluir que:

Primal Dualrestrição de igualdade variável sem restriçãovariável sem restrição restrição de igualdade

29

As relações de complementaridade (Corolário 1.6.4) podem ser generalizadas nocaso em que haja variáveis de afastamento nos dois problemas.

Exemplo 1.6.1P : Max cTx

s.a Ax � bx � 0

D : Min bTys.a ATy � c

y � 0De�nindo u = b � Ax e v = ATy � c, pode-se concluir, a partir do Corolário

1.6.4, que, se x é uma solução admissível para o primal e y é uma solução admissívelpara o dual, então:

x e y são óptimos ()xTv = uTy = 0

Seja P : Min cTxs.a Ax = b

x � 0. Se x é solução óptima de P, então existe uma

partição para a matriz A = [ B N ], tal que: x =�xBxN

�=

�B�1b0

�� 0 e, além

disso, cTN = cTN � cTBB�1N � 0.

Por outro lado, considerando o problema dual deste,D : Max bTy

s.a ATy � ce de�nindo yT = cTBB

�1 já sabemos que se obém também uma solução óptima parao problema D.ATy � c, cTBB

�1[ B N ] ��cTB cTN

�,�cTB cTN � cTBB�1N

���cTB cTN

�e, desta última inequação, facilmente se conclui que os valores das variáveis de afas-tamento do dual correspondentes às variáveis básicas do primal são nulos, enquantoque os valores das variáveis de afastamento do dual correspondentes às variáveis nãobásicas do primal podem ser obtidos a partir dos custos actualizados dessas variáveise reciprocamente.Tendo este resultado em conta é possível desenvolver um algoritmo que resolva

um problema primal, usando o quadro do primal, mas garantindo a convergênciado algoritmo em termos de resolução do problema dual. Se um determinado quadrocorresponder a uma base que não é admissível para o primal mas sim para o dual(alguns termos independentes negativos mas todos os custos não negativos), é pos-sível, mesmo assim, trabalhar com esta base, pois ela corresponde a uma soluçãoadmissível, mas não óptima para o dual. Com base neste resultado desenvolve-se oAlgoritmo Simplex-Dual que se descreve seguidamente:

Seja B uma base para o primal tal que�xBxN

�=

�B�1b0

�� 0 mas

30

cTN = cTN � cTBB�1N � 0 e seja b = B�1b:

Passo 1: Escolher r tal que br = minfbig. Se br � 0, a solução é óptima e termina

Passo 2: Escolher yrs < 0 tal quecs�yrs

= min

�cj�yrj

: yrj < 0

�: Caso todos os

yrj � 0 o problema não tem solução.

Passo 3: Trocar ar com as em B

Repetir até parar.

Este método é de extrema utilidade, principalmente quando, depois de se terresolvido um problema se chega à conclusão de que é necessário alterar algum oualguns parâmetros e que essa alteração vá fazer com que alguma ou algumas com-ponentes do termo independente se tornem negativas.

1.7 Análise de sensibilidade e análise post-optimal

Considere-se o problema

8<:min z = cTx

Ax = bx � 0

e, suponha-se que por aplicação do

método simplex, se obteve a base B, correspondente à solução básica admissívelóptima. Sabe-se que os valores do vector x correspondente ao óptimo, da função ze dos custos actualizados são dados por:

x =

�xBxN

�=

�B�1b0

�� 0; z = cTBxB; cTN = cTN � cTBB�1N � 0

Depois de resolvido o problema pode-se constatar que, por erro de recolha dedados ou por erro de formalização ou por alteração das condições, é necessário alteraralgum ou alguns dos parâmetros. Vejamos como resolver o problema sem ter quevoltar ao princípio. As alterações que se podem fazer inserem-se num dos seguintescasos:

(i) mudança no vector c

(ii) mudança no termo independente

(iii) mudança na matriz A

(iv) adição de uma variável

31

(v) adição de uma restrição

(i) Altera-se o valor de uma das componentes de c: ck passa a ser c0k. Duas coisas

podem acontecer: ou a variável xk é básica ou não é básica.

1o caso xk não é básica

Só é necessário recalcular o valor de ck : c0k = c

0k � cTBB�1ak = ck +

�c0k � ck

�Se c

0k � 0 a solução continua óptima. Caso contrário há que continuar com oalgoritmo simplex.

2o caso xk é básica: Seja xk = xBiÉ necessário recalcular todos os valores de cj, para j 2 N .c0j = cj � c0TBB�1aj = c

0j �

�c0Bi� cBi

�yij; j 2 N

Se c0j � 0 a solução continua óptima e só é necessário recalcular o valor dez, visto que se alterou o custo de uma variável básica. Caso contrário háque continuar com o algoritmo simplex.

(i) mudança no termo independente

Substituindo b por b0então x

0B = B

�1b0:

Se x0B � 0, o extremo continua a ser óptimo e só é necessário recalcular o valor dez.

Caso contrário usa-se o simplex-dual, pois a solução deixou de ser admissível parao primal, mas continua admissível para o dual.

(iii) mudança na matriz A: altera-se a coluna ajpara a

0j

1o caso aj não é básico, recalcula-se y0j = B

�1a0j e c

0j = cj � cTBy

0j

Se c0j � 0, a solução continua óptima. Caso contrário, deve-se continuar como método simplex.

2o caso aj é básico

Neste caso altera-se a matriz B e todo o quadro tem que ser recalculado.Pode mesmo acontecer que a nova matriz B seja singular. Nesse casoterá que se juntar variáveis arti�ciais. Pode também acontecer que nonovo quadro se obtenha uma solução que não é admissível nem para o

32

primal nem para o dual. Neste caso, não se pode aplicar nem o simpex,nem o simplex-dual. Pode-se tentar, retirar primeiro aj da base, mesmopiorando a solução, alterar aj e continuar a resolução a partir daí. Outrahipótese a encarar é voltar ao início. A decisão deve ser tomada em cadacaso, conforme o trabalho que cada alternativa representar.

(iv) Acrescentar uma restrição

Se se acrescentar uma restrição a região admissível passa de S para S 0 e S 0 � S.Se o vértice óptimo for um elemento de S 0 (isto é, se o vector correspondenteao vértice óptimo satis�zer a nova restrição), ele continuará a ser óptimo, casocontrário há que acrescentar uma linha e uma coluna ao quadro e continuar aresolução através do simplex-dual, tendo o cuidado de obter a inversa da novamatriz B (que tem mais uma linha e uma coluna que a anterior). Na práticaisso corresponde a obter a matriz identidade nas colunas correspondentes àsvariáveis básicas.

(v) Acrescentar uma variável

Acrescentar a variável xn+1, com coluna an+1 e custo cn+1:

Calcula-se yn+1 = B�1an+1 e calcula-se. Se cn+1 = cn+1 � cTByn+1.

Se cn+1 � 0 a solução continua óptima. Caso contrário a variável xn+1 entra nabase e continua-se com o método simplex.

33

Capítulo 2

O Problema de Transportes

Considerem-se m origens e n destinos. Na origem i há ai unidades de uma mer-cadoria e no destino j são necessárias bj unidades dessa mercadoria. Supõe-se quede cada origem é possível chegar a cada um dos destinos através de uma aresta(i; j). Associado a essa aresta existe um custo cij correspondente a transportar umaunidade da mercadoria da origem i para o destino j.

34

A resolução do problema consiste em determinar o plano de distribuição que mi-nimize os custos de transporte. Para simpli�car a resolução do problema pressupõe-se que o total da mercadoria que existe nas origens é igual ao total da mercadoria

necessária nos destinos, isto é quemPi=1

ai =nPj=1

bj. Isto é, que no �nal todas as origens

�carão sem mercadoria e os destinos terão toda a sua procura satisfeita.

35

2.1 Formalização do problema:

minnPj=1

mPi=1

cijxij

s.anPj=1

xij = ai i = 1; � � � ;mmPi=1

xij = bj j = 1; � � � ; n

xij � 0 i = 1; � � � ;m; j = 1; � � � ; nem que xij representa a quantidade de mercadoria a transportar da origem i para

o destino j.Fazendo xT = [x11; x12; :::; x1n; x21; :::; x2n; :::; xm1; :::; xmn]bT = [a1; a2; :::; am; b1; :::; bn]e ordenando A e c do mesmo modo, pode-se escrever este problema com a forma:

Min cTxs.a Ax = b

x � 0

A matriz A tem dimensão (m + n) � (mn) e tem uma forma muito especial quepermite simpli�car bastante a resolução do problema.

2.1.1 Exemplo concreto

Vejamos um exemplo concreto: Pretende-se transportar uma determinada mercado-ria de 2 armazéns (armazém 1 e armazém 2) para 3 destinos (1, 2 e 3). No armazém 1existem 30 unidades da mercadoria, enquanto que no armazém 2 existem 20 unidadesda mercadoria. Por sua vez o destino 1 precisa de 15 unidades da mercadoria, o des-tino 2 de 10 unidades e o destino 3 de 25 unidades. Os preços unitários de transportede cada origem para cada destino são dados no seguinte quadro:

destinos

origens

1 2 3 ai1 c11 = 4 c12 = 7 c13 = 5 302 c21 = 2 c22 = 4 c23 = 3 20bj 15 10 25

36

A formalização do problema na forma de um problema de programação linear éa seguinte:

Min z = 4x11 + 7x12 + 5x13 + 2x21 + 4x22 + 3x23s.a x11 + x12 + x13 = 30

x21 + x22 + x23 = 20x11 + x21 = 15x12 + x22 = 10x13 + x23 = 25x11; x12; x13; x21; x22; x23 � 0

A matriz deste problema é:

A =

2666641 1 1 0 0 00 0 0 1 1 11 0 0 1 0 00 1 0 0 1 00 0 1 0 0 1

377775Repare-se que é uma matriz cujos elementos ou são 0 ou são 1 e que há exacta-

mente dois elementos iguais a 1 em cada coluna. Não é di�cil generalizar e concluirque a matriz de qualquer problema de transportes tem estas duas propriedades sejaqual for a sua dimensão.

Teorema 2.1.1 O problema de transportes tem solução desde quemPi=1

ai =nPj=1

bj = d

Demonstração. (por construção)

Basta fazer xij =aibjd, para i = 1; :::;m e j = 1; :::; n. É óbvio que xij � 0, para

i = 1; :::;m e j = 1; :::; n. Por outro lado,mPi=1

xij =mPi=1

aibjd=bjd

mPi=1

ai =bjdd = bj,

para j = 1; :::; n enPj=1

xij =nPj=1

aibjd=aid

nPj=1

ai =aidd = ai para i = 1; :::;m.

37

Propriedades da matriz A

Característica de A: Somando as m primeiras linhas obtém-semPi=1

nPj=1

xij =

mPi=1

ai. Somando as n linhas seguintes obtém-senPj=1

mPi=1

xij =nPj=1

bj. Como se está a

considerar quemPi=1

ai =nPj=1

bj, então as duas somas são iguais. Conclui-se assim que

as linhas da matriz A são linearmente dependentes.A dimensão da matriz A é (m + n) � (mn). Desde que m � 2 e n � 2, é claro

que mn � m+ n. Então car(A) � m+ n� 1.Retirando a última linha à matriz A, obtém-se uma matriz A0 que pode ser

posta na forma triangular superior mediante uma troca de colunas. No exemplodado antes, as colunas de A devem ser ordenadas do seguinte modo:

A0 =

2666641 0 1 10 1 0 00 0 1 00 0 0 1| {z }

����������0 01 11 00 1| {z }

377775B N

o que corresponde à ordenação x13; x23; x11; x12; x21; x22.

Note-se que detB = 1 6= 0, sendo portanto car(A) = 2 + 3� 1 = 4

2.2 Propriedades das matrizes dos problemas detransportes

De�nição 2.2.1 Diz-se que uma matriz é totalmente unimodular se e só se qualqueruma das suas submatrizes quadradas tem determinante nulo ou �1.

Teorema 2.2.1 A matriz do problema de transportes é totalmente unimodular.

Demonstração. (por indução)Como todos os elementos da matriz do problema de transportes são iguais a

0 ou 1, então o determinante de qualquer submatriz 1 � 1 ou é nulo ou é igual a1. Por outro lado, como car(A) = m + n � 1, qualquer submatriz de dimensão

38

(m+n)�(m+n) tem determinante nulo. Seja Ak uma submatriz de A de dimensãok com 1 < k < m + n. Já se viu que determinante de A1 é igual a 0 ou a 1.Suponha-se, como hipótese de indução, que qualquer submatriz de dimensão k � 1tem determinante nulo ou �1. A matriz Ak tem que obedecer a uma das seguintescondições:i) Existe pelo menos uma coluna de zeros;ii) Existe pelo menos uma coluna com um único elemento igual a 1 e os outros

todos nulosiii) Todas as colunas têm 2 elementos iguais a 1 e os outros todos nulos.No primeiro caso o determinante da matriz é, obviamente, nulo.No segundo caso, o determinante pode ser calculado por aplicação do desen-

volvimento de Laplace a essa coluna, obtendo-se � detAk�1, que, por hipótese deindução, ou é nulo ou é �1.No terceiro caso, em cada coluna, um dos elementos iguais a 1 corresponde a uma

origem e o outro a um destino. Como todas as colunas têm exactamente 2 elementosiguais a 1, somando todas as linhas correspondentes às origens e somando todas aslinhas correspondentes aos destinos vai-se obter exactamente a mesma coisa, o quemostra que as linhas são dependentes e, portanto, o determinante da matriz é nulo.

Teorema 2.2.2 Qualquer base B do espaço das colunas da matriz A pode ser trans-formada numa matriz triangular por reordenação de linhas e colunas.

Demonstração. Seja B uma matriz (m+n�1)�(m+n�1), tal que detB 6= 0.Como foi visto na demonstração do teorema anterior, em B tem que existir pelomenos uma coluna com um único elemento igual a 1 e os outros todos nulos. Reor-denando as linhas e as colunas de B de modo a que esse 1 ocupe a primeira linha e

primeira coluna obtém-se:�10

���� qTBm+n�2�: A matriz Bm+n�2 também tem que ser

não singular e, portanto, tem que ter pelo menos uma coluna com um único elementoigual a 1 e os outros iguais a zero. Reordena-se agora as linhas e colunas de modo aque esse 1 vá ocupar a posição da primeira linha e primeira coluna da matriz Bm+n�2,

obtendo-se

24 100

������q110

������qT2pBm+n�3

35 com Bm+n�3 não singular. Repetindo o processo

acaba-se por obter uma matriz triangular superior com os elementos diagonais todosiguais a 1.

Quer isto dizer que para resolver o sistema BxB = b (equivalente a calcularxB = B

�1b) basta proceder por substituição para trás.

39

No exemplo anterior:2666641 0 1 10 1 0 00 0 1 00 0 0 1| {z }

3777752664x13x23x11x12

3775 =266430201510

3775 =)8>><>>:x12 = 10x11 = 15x23 = 20x13 = 30� 15� 10 = 5

É fácil concluir, devido ao facto da matriz B só ter elementos iguais a 0 ou 1 epoder ser posta na forma triangular, que, desde que os valores de ai e bj sejam todosinteiros, então as soluções básicas são todas inteiras.Vejamos qual o aspecto das colunas do quadro do simplex em cada iteração.

yij = B�1aij ou Byij = aij

Se se resolver este sistema pela regra de Cramer teremos (designamos por yijk a

componente k do vector yij): yijk =detBkdetB

, em que Bk é a matriz que se obtém de

B substituindo a coluna k pela coluna aij. Como detB = �1 e detBk = 0 ou �1,então yijk = 0 ou �1. Vê-se assim que qualquer quadro do simplex só tem elementosiguais a 0 ou a �1:Se pensarmos que o vector yij fornece as coordenadas do vector aij na base B,

pode-se concluir que qualquer vector aij pode ser obtido somando e subtraindo osvectores coluna de B. Comecemos por constatar que aij = ei + em+j, em que eirepresenta um vector da base canónica que tem a componente de ordem i igual a1. Então, para que todos os vectores não básicos possam ser escritos somando esubtraindo vectores da base, é necessário que o conjunto de vectores que estão nabase tenham certas características. Repare-se que, por exemplo:aij = aik � alk + als � aus + auj =(ei + em+k)� (el + em+k) + (el + em+s)� (eu + em+s) + (eu + em+j) = ei + em+jSe representarmos as origens e destinos num quadro, em que cada linha repre-

senta uma origem e cada coluna um destino, a sucessão de vectores descrita cor-responde a um circuito fechado nas células do quadro, em que � representa umcoe�ciente igual a 1 e um coe�ciente igual a �1:

40

j � � � k � � � s � � � � � �u auj� aus...l alk als�...i aij aik�

É fácil concluir que as colunas básicas não podem corresponder a um circuitofechado de células visto que, se assim fosse, seria possível escrever uma delas comocombinação linear das outras e não seria uma base. Por outro lado, também seconclui facilmente que é necessário que as colunas da base correspondam a pelomenos uma célula em cada linha e em cada coluna pois só assim há garantia dese poder escrever qualquer célula não básica como combinação linear das célulasbásicas. Com base nestas observações, aparece naturalmente ummétodo que permiteencontrar uma solução básica admissível inicial sem ter que recorrer ao método dasduas fases.

2.3 Obtenção da solução básica admissível inicial

Vamos descrever esse processo com recurso a um exemplo:Uma empresa siderúrgica produz, anualmente, 4 200 000 toneladas de aço, em

três localidades (A1; A2; A3) que deve ser entregue em quatro outras localidades(B1; B2; B3; B4). As quantidades produzidas e requeridas são indicadas a seguir.

1 800 000 ton em A1 600 000 ton em B1900 000 ton em A2 1 500 000 ton em B2

1 500 000 ton em A3 1 200 000 ton em B3900 000 ton em B4

Os custos de transporte, por tonelada, da origem i para o destino j, são dados noquadro que se segue.

B1 B2 B3 B4A1 20 14 26 30A2 22 24 40 42A3 32 36 52 56

A este quadro costuma dar-se o nome de matriz de custos.

41

Os dados do problema podem ser organizados no seguinte quadro:

B1 B2 B3 B4A1 20 14 26 30 1 800 000A2 22 24 40 42 900 000A3 32 36 52 56 1 500 000

600 000 1 500 000 1 200 000 900 000

Comecemos por observar que 1 800 000+900 000+1 500 000 = 600 000+1 500 000+1 200 000 + 900 000 = 4 200 000. Além disso, como todas estas quantidades sãomúltiplas de 105, é possível simpli�car os cálculos dividindo tudo por esse valor.Para obter uma solução básica inicial pode-se começar por atribuir o máximo

valor possível à variável x11 (canto superior esquerdo ou canto noroeste). Com esteprocedimento há uma origem que �ca vazia ou um destino que �ca cheio. Retira-sea linha ou a coluna correspondente do quadro e repete-se o procedimento. Repare-seque, como de cada vez se retira uma linha ou coluna, no �nal teremos m + n � 1variáveis com valor positivo, o que corresponde ao número necessário para ter umasolução básica. Teremos, também, pelo menos uma variável básica em cada linha eem cada coluna.

B1 B2 B3 B4A1 6 20 12 14 26 30 18A2

22 3 24 6 40 42 9A3

32 36 6 52 9 56 156 15 12 9

Obteve-se assim uma solução inicial com 4 + 3 � 1 = 6 variáveis básicas, à qualcorresponde o valor 1416�105 = (20�6+14�12+24�3+40�6+52�6+56�9)�105para a função objectivo. É agora necessário encontrar um processo de saber se asolução é óptima ou não e, caso não seja, qual a variável a sair da base e qual avariável a entrar na base.

42

2.4 Forma especial do método simplex para o pro-blema de transportes

Sendo o problema de transportes da forma

Min cTxs.a Ax = b

x � 0

o seu dual é da formaMax bTys.a ATy � c

Como na matriz A só há 2 elementos não nulos em cada coluna, então na matrizAT só há dois elementos não nulos em cada linha. Assim, a restrição do dualcorrespondente à variável xij do primal é:

yi + ym+j � cijPara simpli�car a notação, considere-se o vector y com o seguinte aspecto:

y =

�uv

�;

em que as variáveis u correspondem às restrições nas origens e as variáveis v àsrestrições nos destinos. O dual pode então escrever-se:

Max w =mPi=1

aiui +nPj=1

bjvj

s.a ui + vj � ciji = 1; � � � ;m;j = 1; � � � ; n

Da teoria da dualidade, sabe-se que as restrições respeitantes às variáveis básicasdo primal devem ser satisfeitas em forma de igualdade (pois as variáveis de afas-tamento têm que ser nulas). Escrevendo essas igualdades obtém-se um sistema dem+n�1 equações com m+n incógnitas. O sistema é indeterminado, consequênciado facto de o problema primal ter uma equação redundante, e a solução pode serescrita à custa de uma das variáveis. Pode-se decidir atribuir a essa variável o valornulo e assim obter uma solução para o sistema, conseguindo-se, assim, a solução

43

do dual correspondente. Se esta solução for admissível, será óptima. Deve-se en-tão, seguidamente calcular os valores das variáveis de afastamento do dual, ou sejacij = cij � (ui + vj). Estes valores são, também, os custos actualizados do primal.Assim, se estes custos forem não negativos as soluções serão óptimas para o primale para o dual.Vejamos o que se passa neste exemplo. O sistema de igualdades do dual corres-

pondente às variáveis básicas do primal é:8>>>>>><>>>>>>:

u1 + v1 = 20u1 + v2 = 14u2 + v2 = 24u2 + v3 = 40u3 + v3 = 52u3 + v4 = 56

Fazendo v4 = 0, virá u3 = 56 e por substituição para trás obtém-se, sucessiva-mente, v3 = �4; u2 = 44; v2 = �20; u1 = 34 e v1 = �14.Agora, calculam-se no dual os valores das variáveis de afastamento das restrições

correspondentes às variáveis não básicas do primal:c13 = c13 � u1 � v3 = 26� 34� (�4) = �4c14 = c14 � u1 � v4 = 30� 34� 0 = �4c21 = c21 � u2 � v1 = 22� 44� (�14) = �8c24 = c24 � u2 � v4 = 42� 44� 0 = �2c31 = c31 � u3 � v1 = 32� 56� (�14) = �10c32 = c32 � u3 � v2 = 36� 56� (�20) = 0Observa-se assim que a variável x31, à qual corresponde um custo mais negativo,

deve ser tornada básica. Para encontrar a variável que vai sair da base, segue-se umprocesso semelhante ao usado no método simplex, isto é, será a primeira a anular-sequando x31 é incrementado. Para simpli�car, atribui-se a x31 o valor �, adicionandoe subtraindo às restantes variáveis básicas de modo que a soma em cada linha ecoluna não se altere. Assim virá:

v1 = �14 v2 = �20 v3 = �4 v4 = 0

u1 = 34 6� � 20 12 + � 14 26�4

30�4 18

u2 = 4422�8 3� � 24 6 + � 40 42

�2 9u3 = 56 � 32

�10360 6� � 52 9 56 15

6 15 12 9

44

Conclui-se, assim, que o maior valor que � pode tomar é 3, isto é a variávelx31 vai-se tornar básica com o valor 3 por troca com a variável x22 que se anula.Obtém-se assim a nova solução admissível:

3 20 15 14 26 30

22 24 9 40 42

3 32 36 3 52 9 56

à qual corresponde o valor 1386� 105 para a função objectivo. Todo o processo serepetirá até que a solução óptima seja encontrada, o que acontece quando todos oscustos actualizados forem positivos, ou seja, quando o dual também for admissível.

2.5 Soluções degeneradas

Um aspecto a referir é a possibilidade de ocorrência de soluções degeneradas, nasquais o número de variáveis não nulas é inferior a m+n�1. Considere-se o seguinteexemplo:

B1 B2 B3A1 2 1 0:5 2A2 1 0:5 2 2.5

1 1 2.5

Usando a regra do canto noroeste para obter a solução inicial vem:

B1 B2 B3A1 1 2 1 1 0:5 2A2

1 0:5 2.5 2 2.51 1 2.5

Ora, deveriamos ter 2+3�1 variáveis básicas e só obtivemos 3, isto signi�ca quea solução é degenerada, isto é, há uma variável básica que é nula. Utiliza-se aquio chamado método das perturbações que consiste em acrescentar à disponibilidadede uma ou mais origens um valor in�nitesimal � e usar essa perturbação para criarvariáveis adicionais com valor igual a � até perfazer m+ n� 1 variáveis básicas. Noexemplo referido virá:

B1 B2 B3A1 1 2 1 1 � 0:5 2+�A2

1 0:5 2.5 2 2.51 1 2.5+�

45

Agora já temos 4 variáveis básicas e o algoritmo de transportes pode ser usadonormalmente. Assim que obtivermos uma solução com 4 variáveis básicas positivaspode-se fazer � = 0. Vejamos o que acontece neste exemplo:

v1 = 2 v2 = 1 v3 = 0:5

u1 = 0 1-� 2 1 1 �+ � 0:5 2+�u2 = 1:5 � 1

�2:50:5�2 2.5-� 2 2.5

1 1 2.5+�

Vemos que deve ser � = 1 e virá o novo quadro:

2 1 1 1 + � 0:5 2+�1 1 0:5 1.5 2 2.5

1 1 2.5+�

Como obtivemos uma solução não degenerada, pode-se neste momento fazer � = 0e continuar o processo normalmente:

2 1 1 1 0:5 21 1 0:5 1.5 2 2.5

1 1 2.5

Em tudo o que foi feito partiu-se do princípio de que todas as rotas são possíveis,mas pode acontecer que haja trajectos impossíveis entre alguma ou algumas das ori-gens e algum ou alguns dos destinos. Para resolver esse problema deve-se consideraros custos correspondentes aos trajectos impossíveis iguais a +1.

2.6 Desequilíbrio entre oferta e procura

É também importante resolver o problema quando a oferta não é igual à procura.

1o caso oferta superior à procura:

Nesta caso cria-se um destino arti�cial n + 1, de�ne-se bn+1 =mPi=1

ai �nPj=1

bj e

cin+1 = 0, i = 1; :::;m. Quando se obtiver a solução do novo problema asvariáveis xin+1 que tiverem valor positivo corresponderão a quantidades demercadoria que não chegam a sair da origem i.

46

2o caso procura superior à oferta:

Nesta caso cria-se uma origem arti�cial m + 1, de�ne-se am+1 =nPj=1

bj �mPi=1

ai

e cm+1j = 0, j = 1; :::; n Quando se obtiver a solução do novo problema asvariáveis xm+1j que tiverem valor positivo corresponderão a quantidades demercadoria que não são entregues no destino j, que assim não verá as suasnecessidades totalmente satisfeitas.

De notar que os custos correspondentes às origens e destinos arti�ciais podem nãoser todos nulos, dependendo de haver custos de armazenagem ou multas associadasao não cumprimento de todas as entregas envolvidos no processo.

47

Capítulo 3

Programação Linear Inteira

Considere-se o seguinte programa linear inteiro (PLI):

Max z =nPj=1

cjxj

s.aPaijxj = bi; i = 1; � � � ;m

xj � 0xj inteiro j = 1; � � � ; n

Para resolver este problema começa-se por considerar o problema linear que se obtémignorando a última restrição. A este novo problema chama-se programa relaxado(PR). A resolução do PLI passa pela resolução de vários programas lineares relaxa-dos. O método mais conhecido é o Branch-and-Bound também designado nalgunslivros como método de pesquisa em árvore.

3.1 Algoritmo Branch-and-Bound

Passo 1 Resolver o Programa Relaxado (PR) associado. Um dos 3 casos seguintesacontece:

1. O PR é impossível =) O PLI é impossível

2. A solução óptima do PR é inteira =) A solução óptima do PLI é a do PR

3. A solução óptima do PR não é inteira. Faz z = z�pr e z = �1 A soluçãoóptima do PLI, z�, é um valor do intervalo ]z; z[ . Vai para o passo 2

48

Passo 2 Seja xk uma qualquer variável cujo valor é não inteiro. Seja xk o seu valor.Procede-se à rami�cação em dois novos problemas. Num deles às restriçõesanteriores acrescenta-se a restrição xk � [xk] e no outro acrescenta-se a re-strição xk � [xk] + 1. Acrescentam-se estes problemas à lista com todos osproblemas a analisar e passa-se ao passo 3.

Passo 3 Retirar o último problema que se acrescentou à lista e resolver o PR asso-ciado. Um dos 3 casos acontece:

1. O PR é impossível. Corta-se esse ramo e recomeça o passo 3.

2. O PR tem solução inteira. Actualiza-se os valores de z e z e repete-se o passo3.

3. O PR tem solução não inteira. Se z�pr < z volta-se ao ínicio do passo 3. Sez�pr � z volta-se ao passo 2.

Quando não houver mais problemas para analisar a solução do PLI é a melhorsolução inteira encontrada cujo valor da função objectivo é z. Como se vê, o queo método faz é pesquisar a região admissível por subregiões, eliminando, em cadapasso, zonas onde é garantido que ou não há pontos com coordenadas inteiras ou égarantido que a função objectivo não vai ter um valor melhor do que alguma soluçãointeira já conhecida.

3.1.1 Resolução de um problema concreto

Exemplo 3.1.1 Encontrar a(s) solução(ões) óptima(s) inteira(s) de

Max z = 5x1 + 8x2s.a x1 + x2 � 6

5x1 + 9x2 � 45x1; x2 � 0

Começa-se por resolver o PR associado usando o método simplex. A sua solução

é x1 =9

4e x2 =

15

4obtendo-se para z�pr o valor

165

4. Neste momento sabe-se que o

valor óptimo está compreendido entre �1 e165

4:

Como são ambas as variáveis não inteiras escolhe-se uma delas para rami�car.Seja por exemplo x2. Obtêm-se assim dois novos problemas num deles acrescentando

49

a restrição x2 � 3 e no outro a restrição x2 � 4. Resolvendo o primeiro obtém-seuma solução inteira: x1 = x2 = 3 e z = 39. Este será o novo limite inferior para a

função objectivo: z� 2 [39; 1654[. Resolvendo o segundo problema obtém-se x1 =

9

5;

x2 = 4 e z = 41. Como este valor de z é maior que o limite inferior deve-se continuara rami�car. Obtêm-se dois novos problemas juntando às restrições anteriores, paraum deles a restrição x1 � 1 e para o outro a restrição x1 � 2. Resolvendo o primeiroobtém-se a solução x1 = 1 , x2 =

40

9e z =

365

9. O segundo problema é impossível.

Como o valor de z,365

9, é maior que o actual limite inferior deve-se continuar a

rami�car. Obtêm-se dois novos problemas adicionando a um a restrição x2 � 4 eao outro a restrição x2 � 5. Obtem-se para o primeiro a solução x1 = 1 , x2 = 4 ez = 37. Como 37 < 39 este ramo é abandonado. Para o segundo problema obtém-sea solução x1 = 0, x2 = 5 e z = 40. O valor mínimo de z passa a ser 40. Como nãohá mais ramos para analisar esta é a solução do PLI.Apresenta-se seguidamente a árvore binária representativa do algoritmo execu-

tado:

50

No caso de haver variáveis inteiras e variáveis reais, o algoritmo continua a seraplicável, desde que só se considerem para rami�cação da árvore as variáveis que sópodem assumir valores inteiros.Para uma melhor visualização do funcionamento do algoritmo, apresentam-se em

seguida as regiões admissíveis de cada um dos problemas resolvidos em cada vérticeda árvore.

51

S0 = f(x1; x2) 2 R2 : x1 + x2 � 6^5x1 + 9x2 � 45^x1 � 0^x2 � 0g

S11 = f(x1; x2) 2 R2 : x1 + x2 � 6^5x1 + 9x2 � 45^x1 � 0^x2 � 0^x2�3g

52

S12 = f(x1; x2) 2 R2 : x1 + x2 � 6^5x1 + 9x2 � 45^x1 � 0^x2 � 0^x2�4g

S21 = f(x1; x2) 2 R2 : x1 + x2 � 6^5x1 + 9x2 � 45^x1 � 0^x2 � 0^x2�4^x1�1g

53

S22 = f(x1; x2) 2 R2 : x1 + x2 � 6^5x1 + 9x2 � 45^x1 � 0^x2 � 0^x2�4^x1�2g

S22 = �

S31 = f(x1; x2) 2 R2 : x1 + x2 � 6^5x1 + 9x2 � 45^^x1 � 0^x2 � 0^x2�4^x1�1^x2�4g

54

S32 = f(x1; x2) 2 R2 : x1 + x2 � 6^5x1 + 9x2 � 45^^x1 � 0^x2 � 0^x2�4^x1�1^x2�5g

Na resolução numérica de problemas, utilizando o algoritmo de branch-and-bound, a solução de cada subproblema pode ser feita partindo do quadro obtidona solução do anterior acrescentando uma linha e coluna ao quadro do simplex eaplicando seguidamente o algoritmo simplex dual. No exemplo anterior, a soluçãodo problema no nó inicial conduz ao quadro:

x1 x2 x3 x4x1 9=4 1 0 9=4 �1=4x2 15=4 0 1 �5=4 1=4

z + 165=4 0 0 5=4 3=4

Acrescentar a restrição x2�3 é equivalente a acrescentar a equação x2 + x5 = 3,com x5�0. Ou seja deve-se acrescentar uma linha e uma coluna ao quadro:

x1 x2 x3 x4 x5x1 9=4 1 0 9=4 �1=4 0x2 15=4 0 1 �5=4 1=4 0

x5 3 0 1 0 0 1z + 165=4 0 0 5=4 3=4 0

Mas, deste modo, deixamos de ter a matriz identidade nas colunas da base. Paraa repor basta fazer as operações adequadas com as linhas do quadro:

x1 x2 x3 x4 x5x1 9=4 1 0 9=4 �1=4 0x2 15=4 0 1 �5=4 1=4 0x5 �3=4 0 0 5=4 �1=4 1

z + 165=4 0 0 5=4 3=4 0

55

Pode-se agora aplicar o método simplex dual para acabar a resolução:

x1 x2 x3 x4 x5x1 3 1 0 1 0 �1x2 3 0 1 0 0 1x4 3 0 0 �5 1 �4

z + 39 0 0 5 0 3

E do mesmo modo se procederia para os outros subproblemas.

56

Capítulo 4

Optimização sem restrições

4.1 Funções reais de variável real

Teorema 4.1.1 Seja a um ponto estacionário da função f : I � R �! R , interiora I, e m > 1 a mais baixa ordem das derivadas de f que não se anula em a. Então:

1. Se m é par e f (m)(a) > 0 , f(a) é um mínimo local.

2. Se m é par e f (m)(a) < 0 , f(a) é um máximo local.

3. Se m é impar e f (m)(a) > 0 , f é crescente em a.

4. Se m é impar e f (m)(a) < 0 , f é decrescente em a.

4.2 Funções reais de variável vectorial

Teorema 4.2.1 Seja a um ponto estacionário da função f : D � Rn ! R , interiora D, e m > 1 a mais baixa ordem das derivadas de f que não se anula em a. Istoé, para k < m todas as derivadas parciais de ordem k são nulas. Então:

Se m é par e f (m)(a) é de�nida positiva , f(a) é um mínimo local.Se m é par e f (m)(a) é de�nida negativa , f(a) é um máximo local.Se m é impar não há extremo.Se m é par e f (m)(a) é inde�nida não há extremo.

De�nição 4.2.1 Seja M 2 Rn�n. M é de�nida positiva sse xTMx > 0 , 8x 6= 0.M é de�nida negativa sse xTMx < 0 , 8x 6= 0:

57

De�nição 4.2.2 Seja M 2 Rn�n. M é semi-de�nida positiva sse xTMx � 0 ,8x 2 Rn. M é semi-de�nida negativa sse xTMx � 0 , 8x 2 Rn:

De�nição 4.2.3 Seja M 2 Rn�n. M é inde�nida se não for nem semi-de�nidapositiva nem semi-de�nida negativa.

4.3 Gradiente, Hessiana e Jacobiano

Seja f : Rn ! R, f(x) = f(x1; x2; � � � ; xn)Ao vector das derivadas parciais de primeira ordem de f chama-se gradiente.

rf(x) =�@f(x)

@x1

@f(x)

@x2� � � @f(x)

@xn

�TÀ matriz das segundas derivadas de f chama-se matriz Hessiana.

r2f(x) =

26666666664

@2f(x)

@x21

@2f(x)

@x1@x2� � � @2f(x)

@x1@xn@2f(x)

@x2@x1

@2f(x)

@x22� � � @2f(x)

@x2@xn...

......

...@2f(x)

@xn@x1

@2f(x)

@xn@x2� � � @2f(x)

@x2n

37777777775Se as primeiras e segundas derivadas da função forem contínuas esta matriz é

simétrica. (Este é um conhecido teorema de Análise)

Seja f : Rn ! Rm, f(x1; x2; � � � ; xn) =

2664f1(x1; x2; � � � ; xn)f2(x1; x2; � � � ; xn)

� � �fm(x1; x2; � � � ; xn)

3775O Jacobiano de f é uma função matricial em que a coluna j é o gradiente da

função fj.

Exemplo 4.3.1 Seja f(x1; x2) = 2x41 + 3x21x2 + 2x1x

32 + 4x

22

O gradiente desta função é rf(x) =�8x31 + 6x1x2 + 2x

32

3x21 + 6x1x22 + 8x2

�A matriz Hessiana é r2f(x) =

�24x21 + 6x2 6x1 + 6x

22

6x1 + 6x22 12x1x2 + 8

�58

No ponto x0 =

��23

�o vector gradiente e a matriz Hessiana são

rf(x0) =��46�72

�e r2f(x0) =

�114 4242 �64

�

Se a matriz Hessiana de uma função é de�nida positiva então a função é convexae se é de�nida negativa é côncava.

Exemplo 4.3.2 Seja f(x1; x2) =

24 sin x1 + cosx2e3x1+x22

4x31 + 7x1x22

35. O Jacobiano desta função éJf (x) =

24 cosx1 � sin x23e3x1+x

22 2x2e

3x1+x22

12x21 + 7x22 14x1x2

35T

No ponto x0 =�12

�a matriz Jacobiana é Jf (x0) =

�cos 1 3e7 40� sin 2 4e7 28

�

4.4 Gradiente e Hessiana de uma função quadrática

Uma função f diz-se quadrática se é da forma f(x) =1

2xTQx + bTx, com

x =�x1 x2 � � � xn

�T, com Q uma matriz quadrada de dimensão n e b um

vector com n componentes.Sem perda de generalidade pode-se supor que a matrizQ é simétrica. Com efeito,

como xTQx =�xTQx

�T= xTQTx então, de�nindo a matriz M =

1

2

�Q+QT

�,

teremos1

2xTMx =

1

4xT�Q+QT

�x =

1

4

�xTQx+ xTQTx

�=1

2xTQx e, então

f(x) =1

2xTMx+ bTx e M é uma matriz simétrica.

Neste caso as fórmulas para o gradiente e a Hessiana são particularmente simples.A função f pode ser escrita na forma:

f(x) =1

2

nXj=1

nXk=1

Qjkxjxk +nXj=1

bjxj

Para determinar@f

@xié necessário isolar as parcelas desta expressão que contêm a

59

variável xi e que são1

2Qiix

2i +

1

2

nPj=1j 6=i

Qjixjxi +1

2

nPk=1k 6=i

Qikxixk + bixi . Temos então

@f

@xi= Qiixi +

1

2

nPj=1j 6=i

Qjixj +1

2

nPk=1k 6=i

Qkixk + bi. Como a matriz é simétrica Qki = Qik,

vindo, �nalmente,@f

@xi=

nPj=1

Qjixj + bi = (Qx+ b)i. Então o gradiente da função

quadrática com matriz simétrica é rf(x) = Qx+ b.De um modo análogo se pode mostrar que a hessiana é constante e igual a Q.

4.5 Derivada de um produto de funções

Sejam f : Rn ! R, f(x) = f(x1; x2; :::; xn) e g : Rn ! R, g(x) = g(x1; x2; :::; xn).Pode-se de�nir uma função h : Rn ! R, h(x) = f(x)g(x). O gradiente de h pode-seobter facilmente de

rh(x) = rf(x)g(x) +rg(x)f(x)e a Hessiana de

r2h(x) = r2f(x)g(x) +r2g(x)f(x) +rg(x)rf(x)T +rg(x)rf(x)T

Exemplo 4.5.1 h(x) = (aTx)(bTx), com a, b e x vectores com n componentes.rh(x) = a((bTx) + b(aTx)r2h(x) = abT + baT

4.6 Derivação de função composta (regra da cadeia)

Seja f : Rn ! R, f(x) = f(x1; x2; :::; xn) e cada xi é uma função de m variáveist1; :::; tm.Pode-se então de�nir a função h : Rm ! R, h(t) = f(x1(t); x2(t); :::; xn(t)),

sendo o seu gradiente dado por rh(t) = rx(t)rf(x(t)):

Exemplo 4.6.1 f(x) = (x21 � x1x2;�x41 + 2x22), com x1 = t1 + 2t2 � 3t3 e x2 =t21 + t2.

Então rx(t) =

24 1 2t12 1

�3 0

35 e60

rf(x(t)) =�2x1 �4x31�x1 4x2

�=

�2 (t1 + 2t2 � 3t3) �4 (t1 + 2t2 � 3t3)3� (t1 + 2t2 � 3t3) 4 (t21 + t2)

�e, �nalmente: rh(t) =

24 1 2t12 1

�3 0

35� 2 (t1 + 2t2 � 3t3) �4 (t1 + 2t2 � 3t3)3� (t1 + 2t2 � 3t3) 4 (t21 + t2)

�.A regra da cadeia pode também ser utilizada para calcular segundas derivadas.

61

Capítulo 5

Programação não Linear

Na sua forma mais geral um problema de programação não linear pode ser descritocomo:Determinar x� = (x�1; x

�2; :::; x

�n) tal que

Maximize f(x)sujeito a gi(x) � bi; i = 1; :::;m

x � 0

em que f e gi são funções de�nidas em Rn. Para simpli�cação, vamos supor queestas funções são diferenciáveis em todo o seu domínio.Não há qualquer algoritmo geral que resolva este tipo de problemas. Contudo,

há algumas subclasses de problemas deste tipo que podem ser resolvidos de formamais ou menos e�ciente por algoritmos surgidos recentemente.

5.1 (alguns) Tipos de Problemas não Lineares

1. Optimização sem restrições

São problemas do tipoMaximize f(x)sujeito a x 2 Rn

Neste caso, é condição necessária de existência de óptimo em x� que rf(x�) =0. Se a função for côncava esta condição é também su�ciente. Nesse caso oproblema reduz-se à resolução de um sistema de n equações não lineares. Esteproblema também não é de fácil resolução: na maior parte das vezes o que seconsegue encontrar é uma sucessão eventualmente convergente para x�.

62

Quando uma variável xj tem uma restrição de sinal, a condição necessária

anterior transforma-se em

8>><>>:@f

@xj� 0, se x�j = 0

@f

@xj= 0, se x�j > 0

.

2. Optimização com restrições lineares

As funções gi são lineares mas a função f é não linear. Este problema érelativamente simples de resolver. Existem inúmeros algoritmos, baseados nométodo simplex, para o resolver. Um dos casos particulares deste tipo deproblemas é aquele em que a função f é quadrática.

3. Programação quadrática

É um problema em que as restrições são lineares e a função f é da formaf(x) = xTQx + cTx em que Q é uma matriz n � n e b é um vector comn componentes. Muitos algoritmos foram desenvolvidos para este caso, quefuncionam muito bem se a função f for côncava. Alguns deles são extensõesdirectas do método simplex.

4. Programação com variáveis separáveis

É um caso particular em que a função f é côncava, as funções gi são convexase todas as funções envolvidas são de variáveis separáveis.

Diz-se que uma função é de variáveis separáveis se for possível escrevê-la comoa soma de várias parcelas tais que cada uma dessas parcelas apenas contémuma única variável.

5. Programação Fraccionária

A função objectivo é da forma f(x) =f1(x)

f2(x):O caso mais simples é o da

programação linear fraccionária, quando f é da forma f(x) =cTx+ c0dTx+ d0

e em

que as restrições são lineares da forma Ax � b e x � 0. Este problema podeser transformado num problema de programação linear fazendo: y =

x

dTx+ d0

e t =1

dTx+ d0. Deste modo é x =

y

t. Fazendo as substituições adequadas

63

obtéms-e o programa linear

Maximizar cTy + c0tsujeito a Ay � bt � 0

dTy + d0t = 1y � 0; t � 0

(Note-se que (dTx+ do)t = 1 e x =y

t, donde resulta dTy + d0t = 1)

5.2 As condições de Karush-Kuhn-Tucher (KKT)para optimização com restrições

Como reconhecer se uma solução é óptima num problema não linear?A seguinte tabela apresenta um resumo das principais condições necessárias para

a optimalidade:

ProblemaCondições necessáriasde optimalidade

também su�cientesquando

sem restriçõesuma variável

f 0(x) = 0 f é côncava

sem restriçõesn variáveis

@f

@xj(x) = 0; j = 1; � � � ; n f é côncava

Restrições de não negatividade

@f

@xj(x) � 0; j = 1; � � � ; n

xj@f

@xj(x) = 0; j = 1; � � � ; n

f é côncava

Problema com restrições gerais KKTf é côncavagi é convexa, i = 1; � � � ; n

Teorema 5.2.1 Sejam f e gi; i = 1; :::;m funções contínuas e diferenciáveis. Oponto x� = (x�1; x

�2; � � � ; x�n) pode ser uma solução óptima para o problema de op-

timização não linear Maximizar f(x), com x 2 K e K = fx 2 Rn : gi(x) � bie x � 0g, se existirem m números reais �1; �2; :::; �m que satisfaçam as seguintes

64

condições:@f

@xj(x�)�

mPi=1

�i@gi@xj

(x�) � 0; j = 1; � � � ; n

x�j

�@f

@xj(x�)�

mPi=1

�i@gi@xj

(x�)

�= 0; j = 1; � � � ; n

gi(x�)� bi � 0; i = 1; � � � ;m

�i (gi(x�)� bi) = 0; i = 1; � � � ;mx�j � 0; j = 1; � � � ; n�i � 0; i = 1; � � � ;m

Exemplo 5.2.1Maximizar f(x) = ln(x1 + 1) + x2sujeito a 2x1 + x2 � 3

x1 � 0; x2 � 0

Aplicando o teorema a este exemplo, teremos o seguinte sistema:8>>>>>>>>>>>>><>>>>>>>>>>>>>:

1

x1 + 1� 2�1 � 0

1� �1 � 0

x1

�1

x1 + 1� 2�1

�= 0

x2 (1� �1) = 02x1 + x2 � 3�1 (2x1 + x2 � 3) = 0x1 � 0; x2 � 0�1 � 0

É fácil constatar que a função f é côncava e que a função g é convexa, pelo queas soluções deste sistema são pontos óptimos. O problema agora é encontrar essassoluções. Após uma análise cuidadosa constata-se que x� = (0; 3) é a única solução.

5.2.1 Programação Quadrática

A aplicação das condições KKT ao problema

Maximizar f(x) = xTQx+ cTxsujeito a Ax � b

x � 0

65

conduz ao seguinte sistema de equações:

Qx+ ATu� y = cAx+ v = b

x � 0; y � 0; u � 0; v � 0xTy + uTv = 0

66