107
Santoro S, Velhote MCP, Malzoni CE, Mechenas ASG, Strassmann V, Scheinberg M
ARTIGO ORIGINAL
Programação linear aplicada a problemas da área de saúde*
Linear programming applied to healthcare problems
Frederico Rafael Moreira 1
ABSTRACT
Objective and Method: To present a mathematical modeling
technique by means of linear programming as an efficient tool to
solve problems related to optimization in healthcare. Two
applications are approached: formulation of a balanced diet at a
minimum cost and optimal allocation of resources for a set of
medical interventions that comply with cost and medical visit
restrictions. Results: The balanced diet proposed would comprise
1.4 glasses of skimmed milk/day and 100 g of salad/day (2/10 of a
500 g portion) at a total minimum cost of R$ 2.55/day. The optimal
solution for the allocation model among the five types of medical
intervention programs maximizing quality-adjusted life year was
established as follows: use of 100% of intervention type 4 and 50%
of intervention type 2, determining a maximum value of 20.5 QALY.
Conclusion: In a world with increasingly scarce resources and
every day more competitive, linear programming could be used to
search optimized solutions for healthcare problems.
Keywords: Resource allocation; Linear programming; Operations
research; Optimization
RESUMO
Objetivo e Método: Apresentar a técnica de modelagem
matemática via programação linear como eficiente ferramenta
para soluções de problemas que envolvam otimização para a área
de saúde. Duas aplicações foram tratadas: a formulação de uma
dieta balanceada a custo mínimo e a alocação ótima de recursos
para um conjunto de intervenções médicas satisfazendo restrições
de custo e visitas médicas. Resultados: A dieta balanceada
proposta seria composta por 1,4 copos de leite desnatado/dia e
100 g de salada/dia (2/10 de porção de 500 g) a um custo mínimo
total de R$ 2,55/dia. A solução ótima para o modelo de alocação
entre cinco tipos de programas de intervenção médica maximizando
os anos de vida ajustados para a qualidade foi assim determinada:
utilização de 100% da intervenção tipo 4 e 50% da intervenção tipo
2 determinando valor máximo de 20,5 AVAQ’s. Conclusão: Frente
a um mundo competitivo e com recursos cada vez mais escassos,
a programação linear pode ser utilizada na busca de soluções
otimizadas para problemas da área de saúde.
Descritores: Alocação de recursos; Programação linear; Pesquisa
operacional; Otimização
INTRODUÇÃO
A Pesquisa Operacional é uma ciência que objetiva
fornecer ferramentas quantitativas ao processo de
tomada de decisão. É constituída por um conjunto de
métodos e modelos matemáticos de otimização e
simulação, como: Programação Linear, Programação
Não-Linear, Otimização Combinatória, Teoria das
Filas, Programação Dinâmica, Teoria das Decisões, etc.
Atualmente, a implementação de soluções otimizadas
via programação linear tem reduzido custos, da ordem
de centenas ou até milhares de dólares em muitas
empresas de porte médio a grande em vários países
industrializados (1). Muitos pesquisadores apontam o
desenvolvimento do método de programação linear
como um dos mais importantes avanços científicos da
metade do século 20. Infelizmente, ainda é pequeno
o número de empresas brasileiras que utilizam em seus
processos, sejam eles produtivos ou não, alguma
técnica de otimização.
Programação linear tem-se mostrado uma solução
alternativa para planejamento de tratamentos por
braquiterapia, em substituição às soluções tradicionais
baseadas em tentativa e erro(2). A formulação de dietas
balanceadas a custo mínimo satisfazendo um conjunto
de restrições nutricionais tem sido efetuada com
programação linear (3,4).
O objetivo principal deste trabalho é divulgar e
apresentar o método programação linear, para
obtenção de soluções otimizadas de problemas da área
de saúde envolvendo economia e nutrição. Inicialmente, será apresentada a formulação de uma dieta
de custo mínimo utilizando somente duas restrições
nutricionais, com intuito maior de familiarizar os
* Centro de Pesquisa Clínica do Hospital Israelita Albert Einstein.
1
Estatístico do Centro de Pesquisa Clínica do Instituto de Ensino e Pesquisa .
Endereço para correspondência: Frederico Rafael Moreira - Hospital Israelita Albert Einstein - Av. Albert Einstein, 627/701 - Morumbi - Prédio Joseh Feher (Bloco A) - Piso Chinuch - CEP 05651-901 - São
Paulo (SP). Tel.: (11) 3747.0456 - Fax: (11) 3747.0302 - e-mail: [email protected]
Recebido em julho de 2003 – Aceito em 20 de novembro de 2003
einstein 2003; 1:99-104
einstein 2003; 1:105-9
108
Moreira FR
pesquisadores da área de saúde com os termos e
potencialidades do método abordado.
Em seguida será apresentada uma solução
otimizada para problemas de alocação de intervenções
médicas satisfazendo um conjunto de restrições
orçamentárias e visitas médicas. Árvores de decisão
têm sido aplicadas em análises econômicas do tipo
custo-efetividade para a escolha das melhores
estratégias de tratamento. Elas podem indicar quais
intervenções utilizam os menores recursos e representam maior qualidade de vida. Entretanto, estas técnicas
não mostram como alocar recursos de forma efetiva
entre vários programas de intervenção médica, pois
não são modelos de otimização. Desta forma, a
segunda aplicação pretende apresentar a modelagem
algébrica via programação linear como uma
fer-ramenta complementar aos tradicionais métodos
análise de econômica em saúde.
mação linear, a função objetivo é linear, ou seja,
definida como uma combinação linear das variáveis
de decisão e um conjunto de constantes, restritos a
um conjunto de equações lineares de igualdade ou
desigualdade. Teremos portanto modelo composto de:
função objetivo, restrições, variáveis de decisão e
parâmetros. O diagrama representado na figura 1
apresenta definições e interações entre estes
componentes.
A solução para o problema é dita ótima quando as
variáveis de decisão assumem valores que correspondem ao máximo ou mínimo da função objetivo,
satisfazendo a todas as restrições do modelo.
MÉTODOS
Descrição de método de programação linear
Modelos de otimização são definidos por uma
função objetivo composta de um conjunto de variáveis
de decisão, sujeitas a um conjunto de restrições na
forma de equações matemáticas. O objetivo da
otimização é encontrar um conjunto de variáveis de
decisão que geram um valor ótimo para a função
objetivo, valor máximo ou valor mínimo, dependendo
do problema, satisfazendo um conjunto de restrições
impostas pelo modelo. Estas restrições são condições
que limitam as variáveis de decisão e suas relações para
assumirem valores factíveis. Em modelos de progra-
Maximizar ou minimizar a função do objetivo:
Figura 1. Componentes do modelo de programação linear
Função objetivo
Medida de efetividade como uma função
matemática das variáveis de decisão. Maximiza
ou minimiza uma medida de performance.
Sujeito a
Restrições
Conjunto de equações lineares de igualdade ou
desigualdade que as variáveis de decisão devem
satisfazer.
Componentes
Variáveis de decisão
Variáveis desconhecidas que serão determinadas pela solução do modelo. São
variáveis contínuas e não-negativas.
einstein 2003; 1:105-9
Parâmetros
Constantes ou coeficientes previamente
conhecidos.
Uma representação algébrica da formulação
genérica de um modelo de programação linear pode
ser apresentada como segue:
Z = c1 x1 + c2 x2 +............ cn xn (a)
Sujeito às restrições:
a11 x1 + a12 x2 +.............. a1n x n ≤r1 (b)
a21 x1 + a22 x2 +.............. a2n xn ≤r2 (c)
.... .......
am1 x1 + am2 x2 +............. a m n x n ≤r m (d)
x j ≥ 0 (j = 1,2,............,n) (e)
onde:
(a) representa a função matemática que codifica o
objetivo do problema e é denominada função
objetivo(Z). Na programação linear esta função deve
ser linear.
(b)-(e) representam as funções matemáticas lineares
que codificam as principais restrições identificadas.
(e) restrição de não-negatividade, o que equivale a
dizer que as variáveis de decisão podem assumir
qualquer valor positivo ou zero.
“x j” são as variáveis decisórias que representam as
quantidades que se quer determinar para otimizar o
resultado global.
“c i” são os coeficientes de ganho ou custo que cada
variável é capaz de gerar.
“r j “ representa a quantidade disponível de cada
recurso.
“a i j” representa a quantidade de recursos que cada
variável decisória consome.
Programação linear aplicada a problemas da área de saúde
Problema da Dieta
Descrição
Para ilustrar a aplicação da programação linear na
formulação de dietas, suponha que, por motivos
justificáveis, uma dieta alimentar esteja restrita a leite
desnatado e uma salada de composição bem conhecida. Sabendo-se ainda que os requisitos nutricionais
serão expressos em termos de vitamina A e cálcio
controlados por suas quantidades mínimas (em
miligramas). A tabela 1 resume a quantidade de cada
nutriente em disponibilidade nos alimentos e sua
necessidade diária para a boa saúde de uma pessoa,
bem como o custo unitário dos alimentos. O objetivo
é minimizar o custo total da dieta de forma a satisfazer
as restrições nutricionais.
Tabela1. Custos, nutrientes e limitantes nutricionais previstos
Nutriente
Leite (copo)
Salada (500 mg)
Vit. A
Calcio
2 mg
50 mg
50 mg
10 mg
Custo/unidade
R$1.50
R$3.00
109
Descrição do problema de alocação de recursos na área
de assistência à saúde: Pesquisadores desejam alocar
recursos entre cinco tipos de programas de intervenção
médica para uma determinada população com o
objetivo de maximizar os anos de vida ajustados para a
qualidade (AVAQ). AVAQ é uma medida que leva em
conta quantidade e qualidade de vida devido a
intervenção médica aplicada. Estima-se que sejam gastas
no máximo 300.000 unidades monetárias e deseja-se
manter número de visitas médicas em no máximo 40.000.
Supõe-se ainda que cada paciente receba somente uma
única intervenção, e valores fracionários de AVAQs,
custos de intervenção e número de visitadas médicas
sejam permitidos. O objetivo é maximizar AVAQ total
acumulado pelas intervenções de forma a satisfazer
restrições orçamentárias e de visitas médicas descritas
na tabela 2.
Requisito Nutricional
Mínimo
11 mg
70 mg
Variáveis de decisão:
X1 = quantidade de leite (em copos) por dia
X2 = quantidade de salada (em porções de 500 g) por dia
Função objetivo (z): A função a ser minimizada, o custo
total para a dieta, é a função objetivo deste problema.
Está definida pela combinação dos alimentos X1 (leite)
e X2 (salada) e de seus custos unitários, R$1.5 (um
real e cinqüenta centavos) e R$3 (três reais), respectivamente. A função custo é uma função linear de X 1
e X2, ou seja: Z=1.5X1 + 3.0X 2
Tabela 2. Valores de AVAQ, custo intervenção e visitas médicas
Identificação de
programas de
intervenção
1
2
3
4
5
Valor Maximo
AVAQs
10
15
15
13
9
Custo de intervenção N. de visitas
(x 103 unid. monetárias) médicas (x 103)
100
50
50
40
120
300
40
50
50
15
30
40
Formulação de modelo matemático
• Variáveis de decisão
X i = fração de cada intervenção i a ser designada
pelo modelo.
Restrições: O total de vitamina A da dieta deve ser
maior ou igual a 11 mg. A formulação alimentar deve
contemplar no mínimo 70 mg de cálcio. Não podemos
considerar quantidades negativas de alimentos, desta
forma X 1 e X 2 devem ser quantidades não-negativas
(X 1>=0 ; X2>=0)
• Função objetivo
Maximizar a função Z definida como os anos de
vida totais ajustados para a qualidade devido às
intervenções: 10X1 + 15X2 + 15X3 + 13X4 + 9X5
Os parâmetros desta equação representam o
número de AVAQs adquiridos como resultado da
intervenção i.
Modelo matemático para o problema da dieta
Minimizar Z = 1.5X1 + 3X2
x1, x2
Sujeito a:
• Restrições
Orçamentárias: 100X 1 + 50X 2 + 50X 3 + 40X 4 +
120X 5 <= 300. O custo com todas as intervenções
não deve ultrapassar 300.000 unidades monetárias.
Visitas: 40X1 + 50X2 + 50X3 + 15X4 + 30X5 <= 40
Xi >=0; Xi <=1 i=1,2,3,4,5 Variáveis de decisão
podem assumir qualquer valor entre 0 e 1.
2X1 + 50X2 ≥ 11 (Restrição de Vitamina A)
50X1 + 10X2 ≥ 70 (Restrição de Cálcio)
X1 ≥ 0; X2 ≥ 0 (Restrição de Não-Negatividade)
einstein 2003; 1:105-9
110
Moreira FR
Modelo matemático
Maximizar
Z = 10X1 + 15X2 + 15X3 + 13X4 + 9X5
x1, x2, x3, x4, x5
Sujeito ao conjunto de restrições:
100X1 + 50X2 + 50X3 + 40X4 + 120X5 ≤300
40X1 + 50X2 + 50X3 + 15X4 + 30X5 ≤40
0 ≤ X 1 ≤ 1; 0 ≤ X 2 ≤ 1; 0 ≤ X 3 ≤ 1; 0 ≤ X 4 ≤ 1; 0 ≤ X 5 ≤ 1
RESULTADOS
Solução gráfica para problema da dieta
Quando lidamos com duas variáveis decisão (dois
alimentos), uma representação geométrica é possível
e conveniente do ponto de vista didático. Para explorar
a geometria do problema, primeiramente as restrições
foram representadas no plano cartesiano (figura 2),
localizando a região factível, região do plano cartesiano
que satisfaz o conjunto de restrições do modelo. Resta
agora minimizar o custo. Ora, o custo é uma constante
para cada uma das combinações da X 1 e X 2. Assim,
custos diferentes geram retas paralelas onde o custo é
constante em cada reta. Em seguida, foram traçadas
2
Solução analítica para o problema da dieta
O Método Simplex é um algoritmo criado para se obter
a solução algebricamente. Um algoritmo é um
conjunto de regras que devem ser seguidas passo a
passo para se obter, no final, o resultado desejado. O
Método Simplex foi criado por George Dantzig e
outros cientistas do Departamento da Força Aérea
Americana em 1947(5). O Microsoft Excel Solver utiliza
uma implementação básica do Método Simplex para
resolver problemas de programação linear. A solução
ótima obtida através do Microsoft Excel Solver para
este problema aponta para uma dieta composta por
1.4 copos de leite desnatado/dia e 100 gramas de salada/
dia (X 1 =1.4; X 2=0.2 de porção de 500g) correspondendo a um custo mínimo total de R$ 2,55.
Calcium
1.5
Salad
1
0.5
Vitamin A
a
0.2
Zx =2.55
0.5
1
1.5
2 Milk
Figura 2. A região factível é delimitada pelas retas 2X 1 + 50X2 =11 (Vitamina
A) e 50X1 + 10X 2 =70 (Cálcio) e identificada pelas setas em destaque. As
linhas retas em vermelho (linhas z) representam a ‘função objetivo’ a ser
minimizada para obter a dieta de custo mínimo. O ponto em preto (letra a)
determina a solução ótima X 1=1.4 X 2 =0.2 correspondendo a um custo
mínimo de R$ 2,55 (reta vermelha em negrito).
einstein 2003; 1:105-9
no gráfico as retas de custo e obtida a que corresponde
ao custo mínimo, satisfazendo as restrições nutricionais. Observe que o custo (z) diminui à medida que
move-se em direção à intersecção das retas que
identificam as restrições de cálcio e vitamina A. O
ponto exato em que custo é minimizado corresponde
a intersecção destas retas. Este ponto é encontrado
facilmente determinando a solução das equações
simultaneamente: 2X1 + 50X2 =11 e 50X1 + 10X2 =70.
Esta solução, X1=1.4 e X2=0.2 corresponde a um custo
mínimo total de Z= R$ 2.55. Ou seja, a solução ótima
corresponde a uma dieta de 1.4 copos de leite
desnatado/dia e 100 gramas de salada/dia (2/10 de
porção de 500g) a um custo mínimo de R$ 2.55.
Solução para problema de alocação de recursos
A solução otimizada para o modelo de alocação de
programas de intervenção médica calculada pelo
Microsoft Excel Solver corresponde à utilização
completa (100%) do programa intervenção número 4
e uma fração de utilização de 50% para o programa
de intervenção de número 2 não utilizar as intervenções de números 1,3 e 5 (X 1 =1; X 2 =0.5; X 3=0;
X4=1; X 5=0). Esta solução numérica fornece o valor
máximo de 20.5 AVAQs para a função objetivo deste
modelo.
A solução gráfica é facilmente obtida quando
temos duas variáveis de decisão (exemplo dieta
apresentado). Quando temos três variáveis de decisão,
ainda é possível solução gráfica, apesar da dificuldade
de localizar as intersecções entre os planos definidos
no espaço tridimensional. Para quatro ou mais
variáveis de decisão, a solução gráfica torna-se
impossível e a única alternativa é a solução analítica
via Método Simplex.
Programação linear aplicada a problemas da área de saúde
Discussão
A demanda por decisões eficientes na área de
assistência à saúde abre espaço para aplicação de
técnicas de otimização em problemas de alocação de
recursos apresentando–se como uma ferramenta
complementar aos modelos de avaliação econômica.
Os resultados numéricos apresentados na modelagem
para alocação de programas de intervenção médica
apontam para esta aplicabilidade potencial (X 1=0;
X2=50%; X 3=0; X 4=100%; X 5=0) .A dieta proposta
no segundo modelo contempla um número reduzido
de restrições, de variáveis de decisão (leite e salada), o
tipo de restrição utilizada, pois tem o objetivo didático
de exemplificar a eficiência deste tipo de modelagem
algébrica e divulgá-la para a área médica. Populações
de baixa renda poderiam ser beneficiadas com a
formulação de dietas balanceadas de custo mínimo
formuladas a partir dos alimentos disponíveis e/ou
acessíveis, satisfazendo dezenas ou até centenas de
restrições. Aplicações potenciais para métodos de
otimização podem incluir: avaliação do impacto
econômico em várias terapias através de vários estados
de doença, avaliação de preços de produtos. Por
exemplo, preços otimizados dos componentes do
produto poderiam ser avaliados considerando
restrições como gastos com pesquisa e desenvolvimento, custo de terapias alternativas, estratégias
de marketing e estimativas para projeções de vendas.
Modelagem matemática utilizando programação linear
tem aplicação em problemas de alocação otimizada
de recursos em saúde cujo objetivo seja, por exemplo,
maximizar AVAQs, anos de vida ou minimizar número
de indivíduos que desenvolvem complicação, custo de
tratamento, bem como definir componentes para
formulação de dietas, medicamentos. Informações
técnicas sobre a construção destes modelos podem
ser encontradas em Bazarra(6) e Hillier & Lieberman(7).
Modelos de grande porte envolvendo centenas de
restrições e variáveis podem ser resolvidos através de
softwares de modelagem algébrica como AIMMS
(Advanced Interactive Mathematical Modeling
111
System), GAMS (General Algebraic Modeling System),
AMPL (Algebraic Mathematical Programming
Language), LINDO( Linear Interactive and Discrete
Optimizer). Informações técnicas comparando estes
softwares podem ser encontradas na publicação OR/
MS Today edição Agosto 2001 (8) .
Conclusão
O tipo de modelagem algébrica abordado neste artigo,
conhecido como programação linear, pode ser
considerado um instrumento útil no suporte a tomada
de decisão na área de saúde. Diante de um mundo
com recursos cada vez mais escassos, e a cada dia mais
competitivo, a busca por soluções otimizadas em
substituição dos tradicionais métodos baseados em
bom senso e tentativa e erro, pode se transformar em
uma questão de sobrevivência para muitas unidades
empresariais.
REFERÊNCIAS
1. Lieberman G, Hillier F. Introduction to mathematical programming. New York:
McGraw-Hill; 1991.
2. D’Souza WD, Meyer RR, Thomadsen BR, Ferris MC. An iterative sequential
mixed-integer approach to automated prostate brachytherapy treatment plan
optimization. Phys Med Biol 2001; 46: 297-322.
3.Colavita, C & D’Orsi, R. Linear programming and pediatric dietetics . Br J Nutr.
1990;64:307-17.
4.Henson S. Linear programming analysis of constraints upon human diets. J
Agric Econ 1991;42:380–93.
5. Dantzig GB Origins of the simplex method In: Nash SG, editor. A history of
scientific computing. New York: ACM Press; 1990.
6. Bazaraa MS, Jarvis J, Sherali HD. Linear programming and network flows. 2nd
ed. New York: Wiley, 1990.
7. Hiller FS, Lieberman GJ. Introduction to operations research. New York: McGraw Hill, 2000.
8. Fourer R. 2001 Software Survey: linear programming. OR/MS Today 2001; 28:
58-68.
einstein 2003; 1:105-9