PROGRAMAÇÃO MATEMÁTICA - PESQUISA SOBRE MÉTODO DUAL

[pic 1]

Centro Universitário Anhanguera de Santo André – Unia Campus II

Curso superior em Engenharia de Produção

Atividade Prática Supervisionada

PROGRAMAÇÃO MATEMÁTICA - PESQUISA SOBRE MÉTODO DUAL

Período: 7º semestre – Turno: Noturno – Sala 322

Professor: Valmir

ESTEVAM AGUIRRE DE ARRUDA – RA: 8075833004

Santo André,

2017

Sumário

1. Introdução        3

2. Método Dual        4

3. Resumo do Método        6

4. Referência Bibliográfica        7

1. Introdução

Veremos o método primal-dual clássico e uma generalização dele para ser usada no projeto de algoritmos de aproximação: o método de aproximação primal-dual. Usando as condições de folgas complementares, o método primal-dual reduz um problema de programação linear a uma sequencia de problemas de viabilidade, potencialmente mais simples.

Nas aplicações do método em otimização combinatória, esses problemas de viabilidade são muitas vezes outros problemas de otimização combinatória para os quais são conhecidos algoritmos eficientes (muitas vezes puramente combinatórios, ou seja, que não usam explicitamente alguns algoritmos de programação linear). Veremos adiante os algoritmos obtidos da aplicação do método de aproximação primal-dual ao problema da transversal mínima e ao problema da floresta de Steiner.

2. Método Dual

A ideia geral do método primal-dual e a seguinte. O método e iterativo e no início de cada iteração tem-se um vetor y viável no programa dual. Cada iteração consiste em procurar um vetor x viável no programa primal que tenha folgas complementares as de y. Se tal vetor x é encontrado, o método para, pois x e y são soluções ótimas dos programas primal e dual, respectivamente. Se tal vetor x não é encontrado, o método modifica y para obter um novo vetor z viável no programa dual e começa uma nova iteração com z no papel de y.

O método primal-dual recebe um sistema (A, b, c) tal que Y (A, c) não é vazio e devolve: 1 vetores x em X(A, b) e y em Y (A, c) tais que cx = yb, ou 2 um vetor y 0 em Y (A, 0) tal que y 0b > 0.

Cada iteração do método começa com um vetor y em Y (A, c). No início da primeira iteração, y é um elemento qualquer de Y (A, c). Cada iteração consiste no seguinte: sejam I(y) := {i ∈ M : yi = 0} e J(y) := {j ∈ N : (yA)j = cj}. Considere o problema restrito primal a seguir, denotado por RP(A, b, y): encontrar um vetor x indexado por N tal que (Ax)i ≥ bi , para cada i em I(y), (Ax)i = bi , para cada i em M \ I(y), xj ≥ 0, para cada j em J(y), xj = 0, para cada j em N \ J(y).

Este é um problema de viabilidade: trata-se de encontrar x que satisfaz todas as restrições em (3). Suponha que o problema RP(A, b, y) é viável e seja x uma de suas soluções. Este vetor x está em X(A, b) e tem folgas complementares ás de y. Portanto, cx = yb. Nesta situação o m´método para após devolver os vetores x e y que, de acordo com o teorema fraco da dualidade, são soluções ótimas dos problemas P(A, b, c) e D(A, c, b), respectivamente.

Se o problema RP(A, b, y) ´e inviável então, pelo lema de Farkas, o seguinte problema de viabilidade tem solução: encontrar um vetor y 0 indexado por M tal que y 0b > 0, (y 0A)j ≤ 0, para cada j em J(y), y 0 i ≥ 0, para cada i em I(y). (4) Esse problema é chamado de problema restrito dual e será denotado por RD(A, b, y).

Seja y 0 uma solução do problema RD(A, b, y). Se, para todo número positivo θ, o vetor y + θy 0 está em Y (A, c), então o programa linear D(A, c, b) ´e ilimitado e o método para após devolver y 0 , vetor de inviabilidade para P(A, b, c). Caso contrário, o método começa uma nova iteração com y + θy 0 no papel de y, com θ o maior número tal que y + θy 0 está em Y (A, c).

Método Primal-Dual(A, b, c): 1 seja y um vetor em Y (A, c); 2 enquanto RP(A, b, y) não tem solução, faça: 3 seja y 0 uma solução de RD(A, b, y); 4 se y + θy 0 ∈ Y (A, c) para todo θ positivo, 5 então devolva y 0 ; 6 senão seja θ o maior número tal que y + θy 0 ∈ Y (A, c); 7 faça y ← y + θy 0 . 8 Seja x uma solução de RP(A, b, y); 9 devolva x e y.