Pesquisa operacional

Prévia do material em texto

Trabalho de Conclusão de Curso
Métodos de Pontos Interiores e o
Planejamento de Tratamento de Câncer por
Radioterapia
Maelson do Nascimento Silva
Orientadora: Profa Dra Daniela R Cantane
Unesp - Campus Botucatu
Outubro de 2013
1
Índice
Resumo 3
1 Introdução 3
2 Otimização 4
2.1 Otimização Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Método de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.1 Método de Newton para uma Variável . . . . . . . . . . . . . . . . . 8
2.2.2 Método de Newton para várias variáveis . . . . . . . . . . . . . . . . 8
3 Métodos de Pontos Interiores 9
3.1 Conceitos iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Método Primal-Dual Afim-Escala . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Método Primal-Dual Clássico . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4 O Tratamento de Câncer Através da Radioterapia 13
4.1 Formulação do modelo matemático . . . . . . . . . . . . . . . . . . . . . . . 14
4.2 Modelo de programação linear . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3 Propriedades das Restrições Elásticas . . . . . . . . . . . . . . . . . . . . . . 17
4.3.1 Interpretação das Soluções . . . . . . . . . . . . . . . . . . . . . . . . 17
4.3.2 Análise Média . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.3.3 O Método Primal-Dual para Análise da Média . . . . . . . . . . . . 19
4.3.4 Eliminação de Variáveis . . . . . . . . . . . . . . . . . . . . . . . . . 21
5 Experimentos Computacionais 25
5.1 Resultado do Exemplo 2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.2 Resultados dos Problemas Gerais de Otimização . . . . . . . . . . . . . . . 26
6 Conclusão 27
2
Resumo
O câncer é uma doença que tem início quando ocorre uma mutação genética no DNA
da célula, onde o mecanismo de controle do crescimento normal do tecido celular é alte-
rado. O tratamento do câncer por radioterapia tem como objetivo a eliminação das células
cancerígenas ou alívio dos sintomas. Este trabalho visa estudar conceitos envolvidos no
planejamento do tratamento de câncer por radioterapia, o modelo de programação linear,
os métodos Primal-Dual-Afim-Escala e Primal-Dual-Clássico e apresentar uma aplicação
dos métodos para problemas gerais de otimização.
1 Introdução
O tratamento do câncer tem como finalidade a interrupção do crescimento e reprodu-
ção das células cancerosas. As modalidades de tratamento são a radioterapia, a cirurgia e
a quimioterapia. A radioterapia é um método capaz de destruir células tumorais, empre-
gando feixe de radiações ionizantes. Após a indicação para esse tipo de tratamento, uma
dose pré-calculada de radiação é aplicada no paciente, em um determinado tempo, a um
volume de tecido que engloba o tumor, buscando erradicar todas as células tumorais, com o
menor dano possível às células normais circunvizinhas. Um planejamento da radioterapia é
considerado ótimo quando todos os parâmetros envolvidos, sejam eles físicos ou biológicos,
foram investigados e adequados para cada paciente.
Do ponto de vista matemático, o desafio é emitir uma dosagem de radiação no tumor
suficiente para a sua eliminação e simultaneamente, minimizar a radiação nas regiões vizi-
nhas, que por muitas vezes são sensíveis a radiação devido a alta taxa de divisão celular,
denominadas regiões críticas, evitando assim complicações. A programação linear é a área
da matemática que estuda a modelagem matemática e as técnicas de resolução do problema
de programação linear (PPL). A modelagem matemática de um problema de otimização
parte do conhecimento de um problema real onde o objetivo é maximizar ou minimizar
um dado comportamento. Modelos de programação linear são usados frequentemente para
encontrar bons planos de tratamento por radioterapia. Os principais métodos existentes
para a resolução deste PPL são: o método simplex e o método de pontos interiores.
É sabido da literatura que o método de pontos interiores é bastante rápido para solução
de problemas de otimização, chegando rapidamente muito próximo ao vértice solução.
3
O método Simplex é também um método eficiente, que diferentemente do método de
pontos interiores, encontra a solução ótima, porém as variáveis não básicas estarão nos
seus respectivos limites [7], ou seja, para o problema em questão parte do tumor recebe a
dosagem mínima estabelecida para sua eliminação enquanto parte do tecido saudável pode
receber a dosagem máxima permitida. Assim, a solução obtida pelo método simplex para
estes modelos não corresponde ao tratamento mais adequado do ponto de vista clínico.
Os objetivos deste trabalho são estudar os métodos de pontos interiores [4], estudar o
modelo matemático para o planejamento ótimo em radioterapia [6] e aplicar os métodos
de pontos interiores para resolução do modelo do planejamento ótimo em radioterapia, que
segundo [6, 8] apresenta uma estrutura matricial bem definida, buscando a solução ótima
a partir de um ponto interior factível.
Na Seção 2 encontram-se os conceitos básicos de otimização linear. O desenvolvimento
dos Métodos de Pontos Interiores encontram-se na Seção 3. Na Seção 4, estuda -se o
problema do tratamento de Câncer através da radioterapia e aplicação do método de pontos
interiores específico para este problema. Os experimentos computacionais encontram-se na
Seção 5 e as conclusões na Seção 6.
2 Otimização
Os problemas de otimização derivam da construção de uma representação matemática
para um problema real em que se quer minimizar ou maximizar uma função objetivo, ao
mesmo tempo em que as variáveis estão sujeitas a determinadas restrições. Apresentamos
alguns conceitos de otimização linear e o método de Newton necessários para o desenvol-
vimento deste trabalho.
2.1 Otimização Linear
A otimização linear trata-se de uma técnica de otimização com aplicações amplas e diversi-
ficadas de problemas reais. Dentre suas aplicações estão problemas envolvendo economia,
logística, corte e empacotamento, radioterapia e muitos outros. O problema geral de oti-
4
mização é expresso em programação matemática como:
max f(x)
s.a. g(x) = 0;
x ∈ Rn
em que: f : Rn → R é chamada de função objetivo; g : Rn → Rm são chamadas restrições
e estas limitam o espaço de soluções do problema, chamadas de soluções factíveis e x é o
vetor com as variáveis de decisão. Dependendo da natureza do problema de otimizacão [7],
a função objetivo, bem como as restrições assumem diferentes características, necessitando
de diferentes técnicas para a sua resolução.
Considere um problema primal de otimização linear na forma padrão I e associado a
este problema, temos o problema dual:
max ctx
s.a. Ax ≤ b.
x ≥ 0, x ∈ Rn
←→
min bty
s.a. Aty ≥ c.
y ≥ 0, y ∈ Rm
Vamos encontrar o dual do problema dual, escrevemos o problema dual na forma padrão
I e encontramos o dual dele:
min −ctx ←→ max ctx
s.a. −Ax ≥ −b s.a. Ax ≤ b
x ≥ 0 x ≥ 0
Portanto, o dual do problema dual é o problema primal.
As regras de transformação que se aplicaram:
1. Cada variável do primal corresponde a uma restrição;
2. Cada restrição do primal corresponde uma variável do dual;
3. Os coeficientes da função objetivo do primal correspondem aos termos independentes
das restrições do dual;
4. Os termos independentes das restrições do primal correspondem aos coeficientes da
função objetivo do dual;
5. A transposta da matriz de restrições do primal, é a matriz de restrições do dual; e
6. Se o primal for um problema de maximização (minimização) na forma padrão, então o
problema dual será um problema de minimização (maximização).
5
Considere agora o problema primal na forma padrão II:
maxctx
s.a. Ax = b
x ≥ 0
Colocando na forma padrão I:
max ctx ←→ max ctx
s.a. Ax ≤ b s.a. Ax ≤ b
Ax ≥ b −Ax ≤ −b
x ≥ 0 x ≥ 0
O dual deste problema é dado por:
min bty+ − bty−
s.a. Aty+ − Aty− ≥ c
(y+, y−) ≥ 0, y = y+ − y−
←→
min bty
s.a. Aty ≥ c
y livre
As regras para obter o dual de um problema de otimização linear estão resumidas na
Tabela 1.
Tabela 1: Regras para obter o problema dual
Primal Dual
Restrição de igualdade Variável livre
Restrição de desigualdade (≤) Variável não-negativa
Variável livre Restrição de igualdade
Variável não-negativa Restrição de desigualdade (≤)
Teorema 2.1 (Teorema fraco da dualidade). Se x é uma solução primal factível e y é
uma solução dual factível, então: ctx ≤ bty. Demonstração ver[3]
Teorema 2.2 (Teorema forte da dualidade). Se o problema primal tem uma solução ótima
x∗, então o problema dual tem uma solução ótima y∗ tal que ctx∗ = bty∗. Demonstração
ver[3]
Observação 2.1. Temos que: 1. Se o problema primal é ilimitado, o dual é infactível. 2.
Se o dual é ilimitado, o primal é infactível. 3. Existe ainda a situação em que ambos são
infactíveis.
6
Teorema 2.3 (Condição de folga complementar–Complementaridade). Seja (x,w) primal
factível e (y, z) dual factível. Então (x,w) e (y, z) são ótimos para os problemas primal e
dual, respectivamente se, e somente se: xjzj = 0, j = 1, . . . , n; yiwi = 0, i = 1, . . . , n
No exemplo a seguir encontra-se um modelo matemático de otimização linear aplicado
no problema da mistura de ração apresentado em [1]:
Exemplo 2.1. Uma agroindústria deve produzir um tipo de ração para determinado ani-
mal. Essa ração é produzida pela mistura de farinhas de três ingredientes básicos: osso,
soja e resto de peixe. Cada um desses três ingredientes contém diferentes quantidades de
dois nutrientes necessários a uma dieta nutricional balanceada: proteína e cálcio. O nu-
tricionista especifica as necessidades mínimas desses nutrientes em 1Kg de ração. Cada
ingrediente é adquirido no mercado com um certo custo unitário $/Kg. Na Tabela 1, os
dados do problema são apresentados. Por exemplo, a farinha de osso é constituída de 20%
de proteína e 60% de cálcio; a ração deve ser composta de pelo menos 30% de proteína e
50% de cálcio; 1Kg de farinha de osso custa $0,56.
Observação 2.2. Os ingredientes podem ser constituídos por outros elementos, mas que
não são importantes para o problema em questão.
Deve-se determinar em que quantidades os ingredientes devem ser misturados de modo
a produzir uma ração que satisfaça às restrições nutricionais com o mínimo de custo.
Defina a variável de decisão xj como a quantidade (em Kg) do ingrediente j que deve ser
utilizada em uma unidade de (1Kg) da ração, j= osso, soja, peixe.
Tabela 2: Dados para o problema da ração
Nutrientes Ingredientes Ração
Osso Soja Peixe
Proteína 0.2 0.5 0.4 0.3
Cálcio 0.6 0.4 0.4 0.5
Custos $/Kg 0.56 0.81 0.46
7
O modelo matemático completo fica, então:
min f(xosso, xsoja, xpeixe) = 0.56xosso + 0.81xsoja + 0.46xpeixe
s.a 0.2xosso + 0.5xsoja + 0.4xpeixe ≥ 0.3
0.6xosso + 0.4xsoja + 0.4xpeixe ≥ 0.5 (1)
xosso + xsoja + xpeixe = 1
xosso ≥ 0, xsoja ≥ 0, xpeixe ≥ 0
2.2 Método de Newton
Os métodos de pontos interiores primais-duais podem ser desenvolvidos por meio da apli-
cação do método de Newton às condições de otimalidade partindo de um ponto interior
desconsiderando as desigualdades. Para mais detalhes do método de Newton, ver [3, 11].
2.2.1 Método de Newton para uma Variável
O método de Newton para uma variável busca zeros de uma função resolvendo equações
da forma,Φ(x) = 0. Este método pode ser deduzido aplicando a fórmula de Taylor a Φ(x)
em torno de x0, obtendo:
Φ(x) = Φ(x0) + Φ′(x0)(x− x0) + Φ
′′(x0)
2!
(x− x0)2 + ...
Aproximamos Φ(x) até o termo linear da série:
Φ(x0) + Φ′(x0)(x− x0) = 0 → −Φ(x
0)
Φ′(x0)
= (x− x0) → x = x0 − Φ(x
0)
Φ′(x0)
Este processo é repetido até que uma tolerância estabelecida seja satisfeita.
2.2.2 Método de Newton para várias variáveis
Seja x ∈ Rn tal que Φi(x) = 0 para i = 1, . . . , n. Para encontrar o valor de x, utilizando-se
aproximação sucessivas da função Φ(x) em torno dos pontos x0, . . . , xk até que o ponto xk
seja tal que Φi(xk) � 0.
Aplicando a fórmula de Taylor para várias variáveis em torno de x0.
Φi(x) = Φi(x
0) + [∇Φi(x0)]T (x− x0) + ..., para todo i = 1,...,n, onde
∇Φi(x0) =
⎛
⎜⎜⎝
∂Φi(x
0)/∂x1
...
∂Φi(x
0)/∂xn
⎞
⎟⎟⎠ .
8
Ignorando os termos de ordem superior temos:
∇Φi[(x0)]T (x− x0) = −Φi(x0).
Para i = 1, . . . , n, ou seja, −Φi(x0) = [∇Φi(x0)]t(x1 − x0)
Definimos agora o Jacobiano no ponto x0:
J(x0) =
⎛
⎜⎜⎝
∇Φ1(x0)t
...
∇Φn(x0)t
⎞
⎟⎟⎠ e F (x0) =
⎛
⎜⎜⎝
Φ1(x
0)
...
Φn(x
0)
⎞
⎟⎟⎠ .
3 Métodos de Pontos Interiores
Desde a introdução do algoritmo proposto por Karmarkar em 1984, o método de pontos
interiores tornou-se o método mais notável para resolver problemas de programação linear.
Estudamos os métodos de pontos interiores,primal-dual afim-escala e primal dual clássico
[5, 10].
3.1 Conceitos iniciais
Interior significa x > 0 e w > 0. Considere agora a “nova” forma padrão II:
min ctx
s.a. Ax = b.
x ≥ 0
O problema dual associado é dado por:
max bty ↔ max bty
s.a. Aty ≤ c s.a. Aty + z = c.
y livre y livre
z ≥ 0
Um ponto é interior se todas as variáveis estão estritamente dentro de seus limites.
As condições de otimalidade para os problemas primal e dual são:
1. Primal factível: Ax = b, x ≥ 0.
2. Dual factível: Aty + z = c, z ≥ 0.
3. Complementariedade: xizi = 0, i = 1, 2, . . . , n.
9
3.2 Método Primal-Dual Afim-Escala
Seja um problema com a formulação primal e dual definida por:
min ctx e min bt
s.a. Ax = b s.a. Aty + z = c.
x ≥ 0 z ≥ 0, y livre
A ideia para construir um método de pontos interiores consiste em aplicar o método de
Newton ao sistema F (x, y, z) = 0 formado pelas condições de otimalidade desconsiderando
(x, z) ≥ 0, resolvendo os problemas primal e dual simultaneamente.
Sejam x0, y0, z0, (x0, z0) > 0 um ponto interior. Temos que F (x0, y0, z0) é dado
por:
F (x0, y0, z0) =
⎛
⎜⎜⎝
Ax0 − b
Aty0 + z0 − c
X0Z0e
⎞
⎟⎟⎠ = −
⎛
⎜⎜⎝
r0p
r0d
r0a
⎞
⎟⎟⎠ .
Utilizando o método de Newton para várias variáveis:
(x1, y1, z1) = (x0, y0, z0)− [J(x0, y0, z0)]−1F (x0, y0, z0),
onde J(x0, y0, z0) =
⎛
⎜⎜⎝
A 0 0
0 At I
Z0 0 X0
⎞
⎟⎟⎠ .
Assim, d0 é dado por:
d0 =
⎛
⎜⎜⎝
A 0 0
0 At I
Z0 0 X0
⎞
⎟⎟⎠
−1⎛
⎜⎜⎝
r0p
r0d
r0a
⎞
⎟⎟⎠ =
⎛
⎜⎜⎝
dx0
dy0
dz0
⎞
⎟⎟⎠ .
Reescrevendo o sistema acima e ignorando o índice 0 por facilidade de notação:
⎛
⎜⎜⎝
A 0 0
0 At I
Z 0 X
⎞
⎟⎟⎠
⎛
⎜⎜⎝
dx
dy
dz
⎞
⎟⎟⎠ =
⎛
⎜⎜⎝
rp
rd
ra
⎞
⎟⎟⎠←→
⎧⎪⎪⎨
⎪⎪⎩
Adx = rp
Atdy + dz = rd
Zdx+ xdz = ra
Observação 3.1. Podemos observar que:
• Temos que AD−1At tem dimensão m, posto(A) = m, é simétrica e definida positiva.
Podemos escrever:
AD−1At = LLt, ou seja, podemos calcular a decomposição Cholesky AD−1At.
10
• A ordem de escolha dos pivôs da diagonal não altera a estabilidade numérica.
• A estrutura esparsa de AD−1At não varia com as iterações e é permutada uma única
vez antes de iniciar as iterações.
Método Primal-Dual Afim-Escala
Dados: (x0, y0, z0) interior e: τ�(0, 1) Para k = 0, 1, . . . faça
rkp = b−Axk
rkd = c−Atyk − zk
rka = −XkZke
dyk = [A(Dk)−1At]−1[rkp +A(Dk)−1rkd −A(Dk)−1(Xk)rka ]
dxk = (Dk)−1[Atdyk − rkd + (Xk)−1rka ]
dzk = (Xk)−1[rka − Zkdxk]
ρp = min
dxi<0
{−xi
dxi
}
ρd = min
dzi<0
{
− zi
dzi
}
αkp = min {1, τρp}
αkd = min {1, τρd}
xk+1 = xk + αkpdx
k (αkp é tal que xk+1 > 0)
yk+1 = yk + αkddy
k
zk+1 = zk + αkddz
k (αkd é tal que z
k+1 > 0)
Até convergir.Observação 3.2. Dados x0 e z0 interiores, o tamanho do passo α é calculado de forma
que xk+1 e zk+1 permaneçam interiores (y é livre). Este método não necessita de um ponto
inicial factível.
Definição 3.1 (Critério de convergência). O critério de convergência é dado por:
• Factibilidade primal: ||b−Ax||||b||+ 1 ≤ �
• Factibilidde dual: ||c−A
ty − z||
||c||+ 1 ≤ �
• Otimalidade gap relativo: |c
tx− bty|
1 + ctx+ bty
≤ � ou ∣∣ xtz
1 + ctx+ bty
∣∣ ≤ �
11
Definição 3.2 (Ponto inicial). Os pontos iniciais são dados por:
Para o problema primal [8]:
x¯ = At(AAt)−1b → Ax¯ = b
x0i = max{x¯i, �i}
�1 = max
{
−min x¯i, �2, ||b||1
�2||A||1
}
�2 = 100
Para o problema dual:
y0 = 0
z0i =
⎧⎪⎪⎨
⎪⎪⎩
ci + �3, se ci ≥ 0
−ci, se ci ≤ −�3
�3, se − �3 ≤ ci ≤ 0
�3 = 1 + ||c||1
3.3 Método Primal-Dual Clássico
O método primal-dual afim-escala não é um método eficiente porque permite que alguns
produtos xizi se aproximem de zero muito rapidamente [5, 10]. Consequentemente, as
direções calculadas nestas condições não são boas e o método progride lentamente, podendo
inclusive não convergir.
Para evitar essa dificuldade, é acrescentada uma perturbação μ as condições de com-
plementaridade. No lugar de xizi = 0, temos xizi = μ, i = 1, . . . , n.
No método primal-dual, resolvemos o sistema não-linear:⎧⎪⎪⎨
⎪⎪⎩
Ax = b, x ≥ 0
Aty + z = c, z ≥ 0.
XZe = μe
Aplicando o método de Newton temos o seguinte sistema linear:⎛
⎜⎜⎝
A 0 0
0 At I
Z 0 X
⎞
⎟⎟⎠
⎛
⎜⎜⎝
dx
dy
dz
⎞
⎟⎟⎠ =
⎛
⎜⎜⎝
rp
rd
rc
⎞
⎟⎟⎠ =
⎛
⎜⎜⎝
b−Ax
c−Aty − z
μe−XZe
⎞
⎟⎟⎠ .
Podemos calcular as direções exatamente como no método primal-dual afim-escala. Basta
substituir ra por rc. O Jacobiano é o mesmo apresentado na Seção 3.2.
12
Método Primal-Dual Clássico
Dados τ, θ � (0, 1) e (x0, y0, z0) interior ou (x0, z0) > 0.
Para k = 0, 1, . . . faça:
μk = θ
γk
η
rkp = b−Ax
rkd = c−Atyk − zk
rkcμe
k −XkZke
dyk = [A(Dk)−1At]−1[rkp +A(Dk)−1rkd −A(Zk)−1rkc ]
dxk = (Dk)−1[Atdyk − rkd + (Xk)−1rkc ]
dzk = (Xk)−1[rkc − zkdx]
γ = xtz
ρp = min
dxki
< 0
{
− x
k
i
dxki
}
ρd = min
dzki
< 0
{
− z
k
i
dzki
}
αkp = min{1, τρkp}
αkd = min{1, τρkd}
xk+1 = xk + αkpdx
k
yk+1 = yk + αkddy
k
zk+1 = zk + αkddz
k
Até convergir.
Observação 3.3. Se tomarmos μk = 0, temos o método primal-dual afim-escala.
4 O Tratamento de Câncer Através da Radioterapia
O câncer é uma doença que tem início quando ocorre uma mutação genética no DNA da
célula, onde o mecanismo de controle do crescimento normal do tecido celular é alterado. O
tratamento do câncer têm como objetivo a erradicação da doença, contenção do crescimento
das células, ou alívio dos sintomas.
Os raios-X foram descobertos em 1895 por Wilhelm Conrad Röntgen [2], quando estu-
dava o fenômeno da luminescência produzida por raios catódicos em um tubo de Crookes.
Percebeu-se então que a exposição dos tecidos aos raios-X, sem a devida proteção e por
13
tempo prolongado, causam irritações na pele, ulcerações, dermatites, sérias lesões na epi-
derme, morte celular, ou até a morte do indivíduo. A capacidade da radiação causar lesões
e morte à nível celular motivou estudos, visando pesquisar uma aplicação eficaz no combate
de doenças desse tipo. As pesquisas mostraram que a radiação provocava efeitos nocivos
tanto a células sadias quanto a células cancerígenas porém, as células cancerígenas são
mais radiossensíveis. A radiossensibilidade indica a regressão do tecido após a radiotera-
pia, sendo assim as células sadias se recuperam mais facilmente dos efeitos causados pela
radiação.
A maioria dos tratamentos realizados com radioterapia utilizam fótons de alta energia
gerados por um acelerador linear e aplicados em diferentes posições angulares ao redor
do paciente. O feixe de fótons incidentes pode ser conformado (colimado), de maneira
a irradiar apenas o perímetro tumoral, evitando um espalhamento dos raios no paciente.
Essa conformação do feixe pode ser feita com o uso de colimadores multileaf, sistema
automatizado acoplado a uma máquina logo na saída do feixe. Os colimadores são feitos
de material de alta densidade eletrônica a fim de atenuar porções específicas do feixe
principal.
4.1 Formulação do modelo matemático
Quando o câncer é diagnosticado e há a indicação médica pelo tratamento por radioterapia,
são realizados vários exames no paciente com a finalidade de conhecer a localização, forma
e volume do tumor, bem como os tecidos críticos presentes na região a ser tratada. Após
a obtenção das imagens a dose mínima a ser aplicada no tumor é, prescrita assim como as
doses máximas que os tecidos críticos e saudáveis podem receber. Suponha que cada órgão
esta dividido em pixels, onde cada pixel representará parte do tecido saudável ou do tumor
em um orgão doente. Seja, mT o número de pixels do tumor, mC o número de pixels da
estrutura crítica e mG o número de pixels restantes, ou seja, m = mG + mT + mC . A
Figura (1) é uma imagem de tomografia computadorizada, onde as estruturas de interesse
são devidamente selecionadas.
As metas listadas abaixo indicam que este problema tem uma grande quantidade de
parâmetros a considerar na decisão do que seria desejável para um plano de tratamento:
Transmitir uma dose uniformemente letal na região do tumor; Transmitir uma dose tão
baixa quanto possível na estrutura crítica; Obter uma dose total tão baixa quanto possível;
Reduzir a frequência de doses altas fora da região de tumor; Controlar o número de raios
14
Figura 1: Imagem de tomografia computadorizada com estruturas de interesse selecionadas
e geometria de uma imagem de pixel, 2× 2 com ângulos π4 , 3π4 , 5π4 , e 7π4 .
utilizados no plano de tratamento.
Uma formulação para programação linear consiste em minimizar a dose total emitida
sujeito a um limite inferior da dose na região tumoral. Os métodos de pontos interiores são
estudados e implementados em Matlab específicamente para a resolução do modelo (2).
min f =
m∑
i=1
m∑
j=1
Dij
s.a. Dij =
n∑
p=1
wpA
p
ij , ∀(i, j) (2)
l ≤ 0, ∀(i, j) ∈ Γ
w ≥ 0,
onde: a imagem de tomografia é dividida em pixels e estes são endereçados pela posição
(i, j) da matriz de pixels. Dij representa a dosagem total recebida pelo paciente na posição
(i, j); Aij representa a dosagem nominal emitida pelo raio p na posição (i, j); w representa
a ponderação da dosagem emitida pelos raios; l representa a dosagem mínima a ser re-
cebida pelo tumor; Γ representa o subconjunto de posições onde se encontra o tumor; n
representa o número de raios.
4.2 Modelo de programação linear
Um outro modelo de programação linear usado no plano de radioterapia foi introduzido em
[7]. Este modelo incorpora restrições elásticas e, quando resolvidas pelo método de pontos
interiores, produzem planos favoráveis. A função objetivo é representada pela soma pon-
15
derada de três metas: wlT t, que mede o quanto falta para que o plano encontrado consiga
aplicar a dose mínima na região do tumor; uTc c que mede a quantidade de radiação acima
da prescrita recebida pela região crítica; e uTg g que mede a quantidade de radiação acima
da prescrita nos demais tecidos saudáveis. O escalar positivo w pondera a importância da
formulação de um plano que obtenha a dose mínima na região do tumor, isto é, valores
grandes de w forçam lT t a ser tão pequeno quanto possível.
min wlT t+ uTc c+ u
T
g g
s.a. lt − Lt ≤ ATx ≤ ut
ACx ≤ uc + UCc
AGx ≤ ug + UGg (3)
0 ≤ Lt ≤ lt
−uc ≤ UCc
UGg ≥ 0
x ≥ 0,
onde: w: escalar positivo; x: dose do sub-raio que entra na imagem para alcançar o pixel
p, (x ∈ Rn); t: t ∈ RmT, t ≥ 0; c: c ∈ RmC; g: g ∈ RmG, g ≥ 0.
As restrições lt − Lt ≤ ATx, ACx ≤ uc + UCc,e AGx ≤ ug + UGg, são denominadas
elásticas, pois seus limites podem variar de acordo com os vetores t, c e g, respectivamente.
A prescrição é descrita por quatro limites: ut: representa o vetor de limite superior para
radiação no tumor; lt: representa o vetor de limite inferior para radiação no tumor; uc:
representa o vetor de limite superior para radiação na estrutura crítica; ug: representa o
vetor de limite superior para radiação no restante do tecido saudável.
Fazemos as suposições óbvias que 0 < lt ≤ ut, uc ≥ 0, e ug ≥ 0. Se uma dose letal
uniforme é transmitida ao tumor, o limite superior e inferior para os pixels do tumor
são obtidos através das metas estabelecidas. As linhas da matriz de propagação da dose
podem ser reordenadas considerando as linhas que correspondem ao tumor, as linhas que
correspondem à estrutura crítica, e as linhas que correspondem ao tecido saudável. Esta
reordenação é representada pelas sub-matrizes AT , AC e AG: A =
⎛
⎜⎜⎝
AT
AC
AG
⎞
⎟⎟⎠ , onde, AT :
tumor, AC : estrutura crítica e AG: restante de tecido saudável. As matrizes L,UC e
UG definem como medir a elasticidade, e l, uc e ug controlam a penalização com relação à
16
elasticidade. Valores fixos de l, uc, ug, L, UC e UG definem um conjunto de funções elásticas.
E estas são incorporadas pelas seguintes razões: a restrição elástica garante que algum
conjunto de funções elásticas, (3) é sempre estritamente factível e a diferença dos limites
inferiores nas funções elásticas nos permitem incorporar diferentes objetivos de tratamento.
Considerando que conjuntos de diferentes funções elásticas determinam diferentes filo-
sofia de tratamento a interpretação do modelo (3) depende da escolha deste conjunto. Em
[7] foi proposto a análise da média: l =
1
mT
e, onde l ∈ RmT ; uC = 1
mC
e, onde uC ∈
RmC ; uG =
1
mG
e, onde uG ∈ RmG ; L = I, onde L ∈ RmT×mT ; UC = I, onde UC ∈
RmC×mC ; UG = I, onde UG ∈ RmG×mG , sendo I a matriz identidade.
Esta escolha tem os seguintes objetivos:
1. minimizar a dosagem média recebida pelo tumor dentro do limite prescrito;
2. minimizar a dosagem média recebida da radiação que a estrutura crítica recebe, e
3. minimizar a dosagem média que o tecido saudável recebe.
4.3 Propriedades das Restrições Elásticas
Definição 4.1. A prescrição (ut, lt, uc, ug) admite a uniformidade do tratamento do tumor
se existe um plano, x ≥ 0, tal que lt ≤ ATx ≤ ut.
Teorema 4.1. Seja (x∗(w), t∗(w), g∗(w)) uma solução ótima de (5.2). Para qualquer
conjunto de funções elásticas temos que lT t∗(w) = O(
1
w
), desde que a prescrição admita a
uniformidade do tratamento do tumor. Demonstração em [7]
Este Teorema mostra que a prescrição do tratamento é viável, o déficit de radiação no
tumor é uniformemente limitada pelo inverso de w. Utilizando este resultado é possível,
resolvendo apenas um problema de programação linear, interpretar o resultado e concluir
se existe um tratamento que atende á prescrição violando ou não os limites ug e uc [7].
4.3.1 Interpretação das Soluções
Em [7] mostra que quando w =
k
�
e o valor ótimo de lT t é menor do que �, então a unifor-
midade na região do tumor é garantida, onde k é uma constante que depende dos dados
do problema. Portanto, dados w como definido acima e solução do problema linear corres-
pondente, podemos interpretar a solução para análises média e absoluta. Neste trabalho
consideremos somente a análise da média da seguinte forma:
17
Análise Média (l = e, uc = e, ug = e)
Caso 1: lT t ∗ (w) > �, concluímos que a prescrição não permite a uniformidade do
tumor.
Caso 2: lT t ∗ (w) ≤ �, concluímos que a prescrição permite a uniformidade do tumor.
Esta situação contém dois importantes subcasos:
Caso 2a: uTc c ∗ (w) + uTg g ∗ (w) > 0, a conclusão é que a uniformidade do tumor é
acessível, mas é cara, pois tecidos saudáveis estão recebendo mais radiação do que desejado.
Caso 2b: uTc c ∗ (w) + uTg g ∗ (w) ≤ 0, conclusão é que a uniformidade do tumor é
permitida, a soma média da radiação sobre o tecido saudável é no mínimo tão boa quanto
desejada.
4.3.2 Análise Média
Com esta escolha o problema (3) se reduz ao problema abaixo e introduzindo as variáveis
de folga e desconsiderando a constante etuc, obtemos o problema primal na forma padrão:
min w
1
mt
etmtt+
1
mc
etmcc+
1
mg
etmgg
s.a. lt − t ≤ ATx ≤ ut
Acx ≤ uc + c
Agx ≤ ug + g
0 ≤ t ≤ lt
−uc ≤ c
g ≥ 0
x ≥ 0,
min w
1
mt
etmtt+
1
mc
etmcc+
1
mg
etmgg
s.a. a+ su = ut
a+ t− sl = lt
ATx− a = 0
Acx+ sc − c = 0
Agx− g + sg = ug
t+ st = lt
(t, c, g, x, su, sl, sg, st) ≥ 0,
Em seguida, escrevemos a matriz de restrições de (4):
M =
⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝
I 0 0 0 0 I 0 0 0 0
I 0 I 0 0 0 −I 0 0 0
−I AT 0 0 0 0 0 0 0 0
0 AC 0− I 0 0 0 I 0 0
0 Ag 0 0 −I 0 0 0 I 0
0 0 I 0 0 0 0 0 0 I
⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠
18
Encontraremos agora o problema dual. Multiplicando a transposta de M , por y, o
vetor de variáveis duais temos:
M ty =
⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝
I I −I 0 0 0
0 0 AT AC Ag 0
0 I 0 0 0 I
0 0 0 −I 0 0
0 0 0 0 −I 0
I 0 0 0 0 0
0− I 0 0 0 0
0 0 0 I 0 0
0 0 0 0 I 0
0 0 0 0 0 I
⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠
⎛
⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝
yu
yl
ya
yc
yg
yt
⎞
⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠
, ou seja,
⎧⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨
⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎩
yu + yl − ya = 0
AtT ya +A
t
Cyc +A
t
Gyg ≤= 0
yl + yt ≤ w 1
mt
e
−yc ≤ 1
mc
e
−yg ≤ 1
mg
e
yu ≤ 0
−yl ≤ 0
yc ≤ 0
yg ≤ 0
yt ≤ 0
4.3.3 O Método Primal-Dual para Análise da Média
Seguindo os passos descritos na Seção 3, determinamos as direções do método primal-dual,
para os problemas, escrevendo o Jacobiano e multiplicando esta matriz pelas seguintes dire-
ções: dt = (da, dx, dt, dc, dg, dsu, dsl, dsc, dsg, dst, dyu, dyl, dya, dyc, dyg, dyt, dzx, dzt, dwc, dwg),
e igualando aos resíduos: r = (r1, r2, r3, ..., r20), temos:
19
X =
⎡
⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣
I 0 0 0 0 I 0 0 0 0 0 0 0 0 0 0 0 0 0 0
I 0 I 0 0 0 −I 0 0 0 0 0 0 0 0 0 0 0 0 0
−I AT 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 AC 0− I 0 0 0 I 0 0 0 0 0 0 0 0 0 0 0 0
0 Ag 0 0 −I 0 0 0 I 0 0 0 0 0 0 0 0 0 0 0
0 0 I 0 0 0 0 0 0 I 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 −I I −I 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 AtT −AtC −AtG 0 I 0 0 0
0 0 0 0 0 0 0 0 0 0 0 I 0 0 0 −I 0 I 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 I 0 0 0 0 I
0 0 0 0 0 Yu 0 0 0 0 Su 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 Yl 0 0 0 0 Sl 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 Yc 0 0 0 0 0 Sc 0 0 0 0 0 0
0 0 0 0 0 0 0 0 Yg 0 0 0 0 0 Sg 0 0 0 0 0
0 0 0 0 0 0 0 0 0 Yt 0 0 0 0 0 St 0 0 0 0
0 Zx 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 X 0 0
0 0 Zt 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 T 0
0 0 0 Wc 0 0 0 0 0 0 0 0 0 0 0 0 0 0 C 0
0 0 0 0 Wg 0 0 0 0 0 0 0 0 0 0 0 0 0 0 G
⎤
⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦
Obtemos assim o sistema linear, Jd = r:
20
r1 = da + dsu (4)
r2 = da + dt − dsl (5)
r3 = −da +ATdx (6)
r4 = ACdx − dc + dsc (7)
r5 = AGdx − dg + dsg (8)
r6 = dt + dst (9)
r7 = −dyu + dyl − dya (10)
r8 = A
t
Tdya −AtCdyc −AtGdyg + dzx (11)
r9 = dyl − dyt + dzt (12)
r10 = dyc + dwc (13)
r11 = dyg + dwg (14)
r12 = Yudsu + Sudyu (15)
r13 = Yldsl + Sldyl (16)
r14 = Ycdsc + Scdyc (17)
r15 = Ygdsg + Sgdyg (18)
r16 = Ytdst + Stdyt (19)
r17 = Zxdx +Xdzx (20)
r18 = Ztdt + Tdzt (21)
r19 = Wcdc + Cdwc (22)
r20 = Wgdg +Gdwg (23)
4.3.4 Eliminação de Variáveis
As equações de (4) a (23) definem o sistema linear que determina as direções dos métodos
de pontos interiores. Este sistema pode ser resolvido diretamente mas esta opção é muito
cara computacionalmente devido à sua grande dimensão. No entanto, este sistema pode
ser reduzido através da substituição de variáveis de forma similar à redução realizado para
o problema na forma padrão. Isolandoas variáveis duais de (15) a (23), temos:
21
dyu = S
−1
u (r12 − Yudsu)
dyl = S
−1
l (r13 − Yldsl)
dyc = S1c (r14 − Ycdsc)
dyg = S
−1
g (r15 − Ygdsg)
dyt = S
−1
t (r16 − Ytdst)
dzx = X
−1(r17 − Zxdx)
dzt = T
−1(r18 − Ztdt)
dwc = C
−1(r19 −Wcdc)
dwg = G
−1(r20 −Wgdg)
substituindo em (10) à (14):
r7 = −S−1u (r12 − Yudsu) + S−1l (r13 − Yldsl)− dya →
r21 = S
−1
u Yudsu − S−1l Yldsl − dya = r7 + S−1u r12 − S−1l r13
r8 = A
t
Tdya −AtCS−1c (r14 − Ycdsc)−AtGS−1g (r15 − Ygdsg) +X−1(r17 − Zxdx) →
r22 = A
t
Tdya +A
t
CS
−1
c Ycdsc +A
t
GS
−1
g Ygdsg −X−1Zxdx = r8 +AtCS−1c r14 +AtGS−1g r15 −X−1r17
r9 = S
−1
l (r13 − Yldsl)− S−1t (r16 − Ytdst) + T−1(r18 − Ztdt) →
r23 = −S−1l Yldsl + S−1t Ytdst − T−1Ztdt = r9 − S−1l r13 + S−1t r16 − T−1(r18
r10 = S
−1
c (r14 − Ycdsc) + C−1(r19 −Wcdc) →
r24 = −S−1c Ycdsc)− C−1Wcdc) = r10 − S−1c r14 − C−1r19
r11 = S
−1
g (r15 − Ygdsg) +G−1(r20 −Wgdg) →
r25 = −S−1g Ygdsg)−G−1Wgdg) = r11 − S−1g r15 −G−1r20.
O novo sistema linear é dado pelas equações de (4) à (9) em conjunto com:
r21 = S
−1
u Yudsu − S−1l Yldsl − dya
r22 = A
t
Tdya +A
t
CS
−1
c Ycdsc +A
t
GS
−1
g Ygdsg −X−1Zxdx
r23 = −S−1l Yldsl + S−1t Ytdst − T−1Ztdt
r24 = −S−1c Ycdsc − C−1Wcdc
r25 = −S−1g Ygdsg −G−1Wgdg.
(24)
22
Tomemos agora:
dsu = r1 − da
dsl = −r2 + da + dt
dsc = Y
−1
c Sc(−C−1Wcdc − r24)
dsg = Y
−1
g Sg(−G−1Wgdg − r25)
dst = r6 − dt
e substituindo as equações acima em (7), (8), e (24) temos:
r4 = ACdx − dc + Y −1c Sc(−C−1Wcdc − r24) →
r26 = ACdx − (I + Y −1c ScC−1Wc)dc = r4 + Y −1c Scr24
r5 = AGdx − dg + Y −1g Sg(−G−1Wgdg − r25) →
r27 = AGdx − (I + Y −1g SgG−1Wg)dg = r5 + Y −1g Sgr25
r21 = S
−1
u Yu(r1 − da)− S−1l Yl(−r2 + da + dt)− dya →
r28 = −(S−1u Yu + S−1l Yl)da − S−1l Yldt− dya = r21 − S−1u Yur1 − S−1l Ylr2
r22 = A
t
T dya +A
t
CS
−1
c Yc(Y
−1
c Sc(−C−1Wcdc − r24)) +AtGS−1g Yg(Y −1g Sg(−G−1Wgdg − r25))−X−1Zxdx →
r29 = A
t
T dya −AtCC−1Wcdc −AtGG−1Wgdg −X−1Zxdx = r22 +AtCr24 +AtGr25
r23 = −S−1l Yl(−r2 + da + dt) + S−1t Yt(r6 − dt)− T−1Ztdt →
r30 = −S−1l Ylda − (S−1l Yl + S−1t Yt + T−1Zt)dt = r23 − S−1l Ylr2 − S−1t Ytr6
.
Restando as seguintes equações:
r3 = −da +ATdx
r26 = Acdx − (I + Y −1c ScG−1Wc)dc
r27 = Agdx − (I + Y −1g SgG−1Wg)dg
r28 = −(S−1u Yu + S−1l Yl)da −−S−1l Yldt − dya (25)
r29 = A
t
Tdya −AtCC−1Wcdc −AtGG−1Wgdg −X−1Zxdx
r30 = −S−1l Ylda − (S−1l Yl + S−1t Yt + T−1Zt)dt.
Definimos agora as seguintes matrizes diagonais para sinplificar a notação:
23
D1 = I + Y
−1
c ScG
−1Wc
D2 = I + Y
−1
g SgG
−1Wg
D3 = S
−1
u Yu + S
−1
l Yl
D4 = S
−1
l Yl
D5 = C
−1Wc
D6 = G
−1Wg
D7 = X
−1Zx
D8 = S
−1
l Yl + S
−1
t Yt + T
−1Zt.
Substituindo no sistema (25), temos:
r3 = −da +ATdx (26)
r26 = Acdx −D1dc (27)
r27 = Agdx −D2dg (28)
r28 = −D3da −D4dt − dya (29)
r29 = A
t
Tdya −AtCD5dc −AtGD6dg −D7dx (30)
r30 = −D4da −D8dt. (31)
Isolando dya e dt das equações (29) e (31), teremos:
dya = −D3da −D4dt − r28 e dt = −D−18 (r30 +D4da).
Substituímos na Equação (30), obtemos:
AtT (−D3da −D4dt − r28)−AtCD5dc −AtGD6dg −D7dx = r29
−AtT (D3 +D4D−18 D4)da −AtCD5dc −AtGD6dg −D7dx = r31.
Logo, temos o seguinte sistema linear:⎧⎪⎪⎪⎪⎪⎨
⎪⎪⎪⎪⎪⎩
r3 = ATdx − da
r26 = Acdx −D1dc
r27 = Agdx −D2dg
r31 = A
t
TDada −AtCD5dc −AtGD6dg −D7dx,
onde, Da = (D3 −D4D−18 D4).
Definindo:
d =
⎡
⎢⎢⎣
da
dc
dg
⎤
⎥⎥⎦ , D =
⎡
⎢⎢⎣
I 0 0
0 D1 0
0 0 D2
⎤
⎥⎥⎦ , rp =
⎡
⎢⎢⎣
r3
r26
r27
⎤
⎥⎥⎦ e D˜ =
⎡
⎢⎢⎣
Da 0 0
0 D5 0
0 0 D6
⎤
⎥⎥⎦ .
24
Podemos reescrever o sistema da seguinte forma:
rp = Adx −Dd
r31 = −D7dx −AtD˜d.
(32)
Isolando d da equação (32), temos:
d = D−1(Adx − rp). (33)
Admitindo-se que a matriz A tem mais linhas (que estão representadas pelo número de
pixels) do que colunas (que são representadas pelo número de raios) e substituindo (33)
em (32) temos:
r31 = −D7dx −AtD˜D−1Adx +AtD˜D−1rp
r˜p = −(D7 +AtD˜D−1A)dx = r31 −AtD˜D−1rp.
Logo,
(D7 +A
tD˜D−1A)dx = r˜p. (34)
Este sistema é simétrico e definido positivo podendo ser resolvido pela decomposição de
Cholesky. Sua dimensão é muito menor que o sistema original representado pelas equações
(4) à (23).
5 Experimentos Computacionais
Os métodos de pontos interiores Primal-Dual Afim-Escala e Primal Dual-Clássico foram
implementados em Matlab R2012a utilizando computador com processador Intel Core
2quadCPU 2.66GB de RAM, sistema operacional 32 bits Windows 7 professional do labo-
ratório LCI do departamento de Bioestatística do Instituto de Biociências da UNESP de
Botucatu.
5.1 Resultado do Exemplo 2.1
O Exemplo 2.1 foi implementado em matlab considerando τ = 0, 99995, ψ = 10−3 e os
pontos iniciais:
x0 =
(
0 0 0
)t
, y0 =
(
1 1 0 0 0
)t
, z0 =
(
0.5 0 0.5
)t
com x =
(
0.5 0 0.5
)t
, y =
(
−32.8983 −32.3983 26.5786
)t
, z =
(
0.0001 3.6400 0.0001
)t
25
Tabela 3: Resultados obtidos pelo algoritmo Primal-Dual-Afim -Escala
Problema Tamanho (m× n) Função Objetivo Tempo (s) Iterações
Ração 3× 3 0.5100 0.0151 1
5.2 Resultados dos Problemas Gerais de Otimização
Os problemas gerais de otimização obtidos da biblioteca Netlib
http://www.netlib.org/ep/data foram resolvidos pelos métodos Primal-Dual-Afim-Escala
e Primal-Dual-Clássico estudados na Seção 3. Os resultados computacionais encontram-se
na Tabela 4.
Tabela 4: Resultados obtidos pelo método Primal-Dual-Afim-Escala
Problema Tamanho (m× n) Função objetivo Tempo (s) Iterações
adlittle 56× 138 5.6880 ∗ 1016 0.2496 5
blend 74× 114 —— —– —
share2b 96× 162 4.4381 ∗ 1015 0.9828 8
share1b 117× 253 —— —– —
scsd1 77× 760 1.5835 ∗ 1016 2.2932 7
beaconfd 173× 295 3.2141 ∗ 1012 0.6864 4
e226 223× 472 6.8518 ∗ 100 1.1388 4
agg2 516× 758 −1.1803 ∗ 1019 4.1184 6
agg3 516× 758 −4.3031 ∗ 1020 9.9840 14
scfxm1 330× 600 —— —– —
Na maioria dos casos os problemas convergem mais rapidamente, ou seja, com menor
número de iterações para o método Primal-Dual-Afim-Escala, porém o método Primal-
Dual-Clássico obtém menor função objetivo, sendo mais eficiente pois estamos trabalhando
com problemas de minimização. Isto ocorre devido ao fato do método Primal-Dual-Afim-
Escala poder convergir para mínimos locais, o que não ocorre no método Primal-Dual-
Clássico.
Podemos observar também que, apesar de realizar muitas iterações, elas são rápidas,
fazendo com que o método Primal-Dual-Clássico seja mais eficiente em comparação ao
método Primal-Dual-Afim-Escala. Portanto, o método Primal-Dual-Clássico apresenta um
26
Tabela 5: Resultados obtidos pelo método Primal-Dual-Clássico
Problema Tamanho (m× n) Função objetivo Tempo (s) Iterações
adlittle 56× 138 −9.7330 ∗ 106 1.46380 26
blend 74× 114 −2.1436 ∗ 101 0.1560 2
share2b 96× 162 6.2639 ∗ 103 0.6864 8
share1b 117× 253 4.8243 ∗ 105 1.0452 10
scsd1 77× 760 6.9789 ∗ 105 10.1088 20
beaconfd 173× 295 1.2377 ∗ 105 1.4040 8
e226 223× 472 −1.0619 ∗ 1018 5.2728 3
agg2 516× 758 −1.3600 ∗ 1023 199.5876 301
agg3 516× 758 −4.0019 ∗ 1015 17.1289 29
scfxm1 330× 600 1.0024 ∗ 105 1.0296 3
bom desempenho comparado com o método Primal-Dual- Afim-Escala. Podemos observar
ainda que, em certos casos da Tabela 4 o problema não convergiu para o método Primal-
Dual-Afim-Escala.
6 Conclusão
Neste trabalho foram estudados e apresentados os principais conceitos e os métodos envol-
vidos para resolução de problemas gerais de programação linear, dispostos nos capítulos
2 e 3 respectivamente. A formulação do modelo matemático proposto por Holder (Seção
4) também foi estudado, que verifica um plano de tratamento do câncer por radiotera-
pia, porém não foi implementado este método específico de pontos interiores aplicado ao
problema de câncer.Deu-se ênfase à técnica de otimização linear de pontos interiores, que foi desenvolvida
no Capítulo 3, discutindo-se os métodos Primal-Dual-Afim-Escala e Primal-Dual-Clássico,
os quais foram implementados em Matlab para problemas gerais de otimização.
Podemos observar que o método Primal-Dual-Clássico obteve melhor desempenho com-
parado ao método Primal-Dual-Afim-Escala, pois Primal-Dual-Afim-Escala pode convergir
para mínimos locais, o que não ocorre no Primal-Dual-Clássico.
Como trabalhos futuros pretendemos implementar métodos de pontos interiores apli-
cados ao planejamento de tratamento de câncer por radioterapia.
27
Referências
[1] ARENALES, Marcos, et al. Pesquisa Operacinal para Cursos de Engenharia. Rio de
Janeiro:Elsevier, 2007.
[2] Arruda, W. O.,100 anos da descoberta dos raios- X. SciELO Brasil, v.54, n.3, p.525-
531, 1996.
[3] M.S. Bazaraa,Linear Programming end NetWork Flows, 2nd ed.,John Wiley Sons,
1990.
[4] D.R. Cantane, Métodos de Pontos Interiores Aplicados ao Problema de Regressão pela
Norma Lp, Dissertação de Mestrado, ICMC/USP, 2004.
[5] Cantane, D. R., Contartheze, E. G., Oliveira A. R. L., Método de Pontos Interiores
Barreira Logarítmica Preditor - Corretor Especializado para o Problema de Regressão
pela Norma Lp, TEMA. Tendências em Matemática Aplicada e Computacional,13
(2012), 281-291.
[6] Cid, C.B.B.,Planejamento de tratamento por radioterapia através de métodos de pon-
tos interiores, dissertação de mestrado ICMC-USP, São Carlos, 2003.
[7] Holder, A., Designing radiotherapy plans with elastic constraints and interior point
methods, Health Care and management, 6(1), 2003.
[8] Martins, A.C.S.,O Método de pontos interiores no planejamento da radioterapia, dis-
sertaçãoo de mestrado IB-UNESP, Botucatu, 2011.
[9] Stoll, B.A. Princípios gerais de radioterapia. In: Radioterapia: Conhecimentos Gerais
para médicos e estudantes de medicina. São Paulo: Universidade de São Paulo, 1968.
p.01-16.
[10] S.J. Wright, “Primal-Dual Interior-Point Methods”, SIAM Publications, SIAM Phila-
delphia, PA, USA, 1996.
[11] RUGGIERO, MÁRCIA A. G.; LOPES, VERA L. R.: Cálculo Numérico: Aspectos
teóricos e computacionais. 2a ed., Makron Books, São Paulo, 1996.
28