35369-relfinal-reconsid-paulo

Prévia do material em texto

2017­5­9 Iniciação Científica
http://prope.unesp.br/pibic/orientador/form_avaliacao.php 1/1
 
Orientador 
DANIELA RENATA
CANTANE
 
Início
 
Trocar Senha
 
Editar dados
 
Meus Pedidos
 
Envio do relatório
final
 
Formulário de
Avaliação do
Relatório Parcial 
da Bolsa pelo
Orientador
 
Substituições
 
Cancelamentos /
Suspensões
 
Sair
 
 
 Programa Institucional de Bolsas de Iniciação Científica 
Orientador  Envio do relatório final dos projetos
 
Lista de pedidos
 
Não existe pedidos para entrega do Relatório.
 
Lista Pedidos Avaliados
 
35837 ­ Uma Abordagem da Otimização no Plano de Tratamento por Radiação com o Auxílio de
Imagem (JULIANA CAMPOS DE FREITAS) (17/05/2015 ­ Nova)
 
Status após análise do parecerista: Não Aprovado
­ Analise: Texto de dificil leitura, com frases desconexas e estrutura nao linear, alem de diversos erros
gramaticais. A Secao 1 apresenta alguns termos sem a devida explicacao (Gy, voxel, dose de deslize
quadratica/minima). A Secao 2 apresenta conceitos basicos de Programacao Linear. Entretanto, os
autores deveriam ser mais cuidadosos para nao cometerem erros que colocam em duvida o
conhecimento dos mesmos sobre os conceitos envolvidos. Como exemplo, o par primal­dual de um
problema de programacao linear sempre assume os problemas expressos na forma canonica: se o
problema primal e de minimizacao entao as restricoes apresentam desigualdades do tipo maior ou
igual; se as restricoes forem de igualdade, as variaveis correspondentes no problema dual serao
irrestritas. A Secao 3 poderia ser melhor organizada, com cada passo correspondendo a uma sub­
secao. O simbolo <> nao e adequado para representar valores medios. No inicio da Secao 4.2.1 os
autores apresentam uma variavel (w) que nao aparece em nenhuma das formulacoes apresentadas a
seguir. O Exemplo 4.1 apresenta conceitos equivocados. A Secao 6 apresenta os resultados obtidos
para 3 casos teste disponiveis no software CERR, apresentado na Secao 5. Nao ficou claro no trabalho
como os metodos propostos na Secao 4 foram adaptados para resolver o problema em questao,
parecendo que o proposito do estudo desviou para o uso de um software existente em vez de
demonstrar a aplicacao de tecnicas de Pesquisa Operacional a um importante problema da area da
Saude.
­ Verificação: Nao ficou claro no trabalho a forma como os metodos propostos foram adaptados para
resolver o problema em questao, parecendo que o proposito do estudo desviou para o uso de um
software existente em vez de demonstrar a aplicacao de tecnicas de Pesquisa Operacional a um
importante problema da area da Saude.
 
35369 ­ Métodos de Programação Linear para Resolução do Planejamento de Tratamento de Câncer por
Radiação (PAULO ZAGO LEONEL) (15/05/2015 ­ Nova)
 
Status após análise do parecerista: Não Aprovado
­ Analise: O projeto trata de um problema de grande interesse, tanto pela interdisciplinaridade quanto
pelo impacto social. O objetivo do projeto consistia na implementacao de metodos de resolucao para o
problema de planejamento do tratamento de cancer por radioterapia, por meio de tecnicas do ambito
da Pesquisa Operacional, como o Metodo Simplex, metodo de pontos interiores, entre outros. Tambem
seriam abordadas tecnicas que explorassem particularidades da estrutura matricial do problema. O
Relatorio Final, em suas 20 paginas, apresenta apenas uma linha mencionando o uso de Programacao
Linear para descrever modelos para o tratamento de cancer por radiacao. A maior parte do relatorio
consiste de uma extensa, desnecessaria e falha apresentacao de conceitos basicos de Programacao
Linear, deixando duvidas sobre o dominio do assunto por parte do orientador e/ou do aluno. Faltou
pelo menos um capitulo contendo um levantamento bibliografico sobre aplicacoes anteriores de
tecnicas de Pesquisa Operacional a problemas assemelhados ou relacionados. Ha apenas um breve
capitulo dedicado ao tema do projeto, cujo conteudo nao apresenta nenhuma evidencia dos objetivos
iniciais propostos. A secao Conclusao consiste de novos objetivos para um possivel prosseguimento do
projeto, mas os resultados alcancados no presente projeto deixam duvidas sobre o sucesso da
pesquisa futura.
­ Verificação: As atividades propostas no projeto consistiam em leitura de artigos e capitulos de livros
relacionados com o tema do projeto, visando aprofundar e ampliar os conhecimentos em relacao ao
tratamento de cancer por radioterapia; estudo aprofundado da resolucao de problemas de otimizacao
linear, e; investigacao e implementacao de metodos para resolucao do problema de tratamento de
cancer por radioterapia. Dos 7 capitulos do Relatorio Final apenas um aborda o assunto principal do
projeto, e ainda assim de forma muito superficial, mesmo para um projeto de iniciacao cientifica. Nao
ha indicios de que qualquer pesquisa bibliografica envolvendo o uso de modelos de otimizacao ­­
lineares ou nao ­­ no tratamento de cancer por radiacao, tenha sido realizado. Dessa forma, a
realizacao das atividades seguintes torna­se impraticavel.
 
Iniciação Científica Home Portal UNESP Acesso Restrito
Iniciação CientíficaIniciação Científica
UNIVERSIDADE ESTADUAL PAULISTA
"JÚLIO DE MESQUITA FILHO"
Sistema PIBIC
Início | Acesso Restrito
http://prope.unesp.br/pibic/orientador/index.php
http://prope.unesp.br/pibic/troca_senha.php
http://prope.unesp.br/pibic/orientador/editar_dados.php
http://prope.unesp.br/pibic/orientador/pedidos_de_bolsa.php
http://prope.unesp.br/pibic/orientador/form_avaliacao.php
http://prope.unesp.br/pibic/orientador/envio_relat_parcial.php
http://prope.unesp.br/pibic/orientador/substituicoes.php
http://prope.unesp.br/pibic/orientador/cancelamentos.php
http://prope.unesp.br/pibic/logoff.php
http://prope.unesp.br/pibic/orientador/form_avaliacao.php
http://prope.unesp.br/pibic/index.php
http://www.unesp.br/
http://prope.unesp.br/pibic/acesso_restrito.php
http://www.unesp.br/
http://prope.unesp.br/pibic/orientador/index.php
http://prope.unesp.br/pibic/orientador/acesso_restrito.php
PIBIC processo no. 35369
Métodos de Programação Linear para Resolução de
Planejamento de Tratamento de Câncer por Radiação
Aluno: Paulo Zago Leonel
Curso: F́ısica Médica
Orientadora: Profa Daniela Renata Cantane
Instituto de Biociências
Departamento de Bioestat́ıstica
IBB - UNESP - Botucatu
Conteúdo
1 Introdução 2
1.1 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 A Pesquisa Operacional - PO 2
2.1 Solução do modelo de PO . . . . . . . . . . . . . . . . . . . . 4
3 A Programação Linear - PL 4
3.1 Razões para o uso da Programação Linear . . . . . . . . . . . 5
3.2 A Modelagem com Programação Linear - PL . . . . . . . . . . 5
3.3 Passos para a resolução de um problema de Programação Li-
near - PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4 O Método Simplex 12
4.1 Transição da solução gráfica para a solução algébrica . . . . . 12
4.2 Determinação algébrica dos pontos extremos . . . . . . . . . . 13
4.3 Método Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.3.1 Passos para resolução de problemas pelo Método Simplex 13
5 Solução de problema de Programação Linear - SOLVER 14
6 Planejamento de Tratamento de Câncer por Radiação 17
6.1 O Modelo de Programação Linear para Radioterapia . . . . . 17
7 Conclusão 19
1
1 Introdução
Este relatório descreve as atividades realizadas pelo aluno, na categoria de
graduação em F́ısica Médica, no Instituto de Biociências, Departamento de
Bioest́ıstica da UNESP do Câmpus de Botucatu, através do programa de
Iniciação Cient́ıfica sem bolsa do PIBIC.
As Seções 2, que contém uma introdução sobre Pesquisa Operacional, 3,
que refere-se a Programação Linear, contendo um conjunto de problemas,
4, que apresenta o Método Simplex, sendo este a solução algébrica de um
problema de PL, e a seção 5, que mostra a solução de um problema de PL
pelo software computacional Excel Solver. As Seções 6 apresenta o motido
do estudo eo modelo de programação linear estudado e a 7 informa as con-
clusões, quais poderiam ser os próximos passos e como seria a implementação
do modelo analisado. Por último encontram-se as referências bibliográficas
usadas como base para esse relatório.
1.1 Objetivos
Do ponto de vista matemático, o desafio consiste em emitir uma alta do-
sagem de radiação no tumor, suficiente para sua eliminação e minimizar a
radiação nas regiões vizinhas compostas de tecido saudável, reduzindo ao
máximo as complicações nestas regiões que são muitas vezes cŕıticas. Dessa
forma, esse projeto tem como objetivo estudar um problema de otimização
através da modelagem matemática aplicado ao tratamento de câncer por
radioterapia.[11]
2 A Pesquisa Operacional - PO
A Pesquisa Operacional é uma ciência aplicada voltada para a resolução de
problemas reais. Tendo como foco a tomada de decisões, aplica conceitos e
métodos de várias áreas cient́ıficas na concepção, planejamento ou operação
de sistemas. A Pesquisa Operacional é usada para avaliar linhas de ação
alternativas e encontrar as soluções que melhor servem aos objetivos dos
indiv́ıduos ou organizações.
Através de desenvolvimentos de base quantitativa, a Pesquisa Operaci-
onal visa também introduzir elementos de objetividade e racionalidade nos
processos de tomada de decisão, sem descuidar, no entanto, dos elementos
subjetivos e de enquadramento organizacional que caracterizam os proble-
mas.
A Pesquisa Operacional surgiu durante a Segunda Guerra Mundial, da
2
necessidade de lidar com problemas de natureza loǵıstica, tática e de es-
tratégia militar de grande dimensão e complexidade. Para apoiar os coman-
dos operacionais na resolução desses problemas, foram então criados grupos
multidisciplinares de matemáticos, f́ısicos, engenheiros e cientistas sociais.
Esses cientistas não fizeram mais do que aplicar o método cient́ıfico, que tão
bem conheciam, aos problemas que lhes foram sendo colocados. Desenvolve-
ram então, a ideia de criar modelos matemáticos, apoiados em dados e fatos,
que lhes permitissem perceber os problemas em estudo e simular e avaliar o
resultado hipotético de estratégias ou decisões alternativas.
O sucesso e credibilidade ganhos durante a guerra foram tão grandes
que, terminado o conflito, esses grupos de cientistas e a sua nova metodo-
logia de abordagem dos problemas se transferiram para as empresas que,
com o avanço econômico que se seguiu, se viram também confrontados com
problemas de decisão de grande complexidade. Em alguns páıses, em que
prevaleceu a preocupação com os fundamentos teóricos, a Pesquisa Operaci-
onal se desenvolveu sob o nome de Ciência da Gestão ou Ciência da Decisão
e em outros, em que predominou a ênfase nas aplicações, tendo o nome de
Engenharia Industrial ou Engenharia de Produção.
Seguiram-se então grandes desenvolvimentos técnicos e metodológicos que
hoje, com o apoio de meios computacionais de crescente capacidade e disse-
minação, nos permitem trabalhar enormes volumes de dados sobre as ativida-
des, não apenas das empresas, mas, também de instituições do setor público
dentro e fora da área econômica. Tangente ao seu caráter multidisciplinar, a
Pesquisa Operacional é uma disciplina cient́ıfica de caracteŕısticas horizontais
com suas contribuições estendendo-se por praticamente todos os domı́nios da
atividade humana, da Engenharia a Medicina, passando pela Economia e a
Gestão Empresarial.
Portanto, modelos de Pesquisa Operacional são elaborados para otimizar
um critério objetivo espećıfico sujeito a um conjunto de restrições, mas a
qualidade da solução resultante depende do quanto o modelo reprenta um
sistema real.[1, 2].
Um estudo de pesquisa operacional envolve seis fases:
1. Formulação do problema;
2. Constrção do modelo do sistema;
3. Cálculo da solução através do modelo;
4. Teste do modelo e da solução;
5. Estabelecimento de controles da solução;
3
6. Implantação e acompanhamento.
2.1 Solução do modelo de PO
Em PO, não temos uma única técnica para resolver todos os modelos ma-
temáticos que podem surgir na prática. Em vez disso, o tipo e a complexidade
do modelo matemático é que determinam a natureza do método de solução.
Dentre os métodos utilizados para a solução de um modelo de PO e que
serão apresentados neste relatório temos a representação gráfica e o Método
Simplex, em que nesse último se encaixa o solução Excel Solver.
Entretanto, a técnica mais utilizada em PO é a programação linear, que
é aplicada a modelos cujas funções objetivo e restrição são lineares. Outras
técnicas são a programação inteira, a dinâmica, a não linear e a otimização
em redes. Mas para esse treinamento só trabalhamos com a programação
linear[1, 2]. Programação Linear e seus métodos de resolução serão discorri-
dos na seção a seguir.
3 A Programação Linear - PL
Como dito anteriormente, a Programação Linear é uma das técnicas da Pes-
quisa Operacional das mais utilizadas em se tratando de problemas de oti-
mização. Os problemas de Programação Linear (PL) buscam a distribuição
eficiente de recursos limitados para atender um determinado objetivo, em
geral, maximizar lucros ou minimizar custos. Em se tratando de PL, esse
objetivo é expresso através de uma função linear, denominada de função
objetivo.
É necessário também que se defina quais as atividades que consomem
recursos e em que proporções os mesmos são consumidos. Essas informações
são apresentadas em forma de equação e/ou inequações lineares, uma para
cada recurso. Ao conjunto dessas equações e/ou inequações, denomina-se
Restrições do Modelo (sujeito a - s.a.).
Normalmente se tem inúmeras maneiras de distribuir os recursos escassos
entre as diversas atividades em estudo, bastando para com isso que essas
distribuições estejam coerentes com as restrições do modelo. No entanto, o
que se busca, num problema PL é a função objetivo, isto é, a maximização do
lucro ou a minimização dos custos. A essa solução dá-se o nome de solução
ótima. Assim, a Programação linear se incube de achar a solução ótima de
um problema, uma vez definida o modelo linear, ou seja, a função objetivo
e as restrições lineares. Algumas razões para o uso de PL são descritas a
seguir[1, 2, 7].
4
3.1 Razões para o uso da Programação Linear
1. Grande variedade de situações podem ser aproximadas por modelos
lineares;
2. Existência de técnicas (algoritmos) eficientes para a solução de modelos
lineares;
3. Possibilidade de realização de análise de sensibilidade nos dados do
modelo;
4. Estágio de desenvolvimento da tecnologia computacional.
3.2 A Modelagem com Programação Linear - PL
Um problema de otimização linear é composto por variáveis de decisão ou
simplesmente variáveis xj, j = 1, . . . , n por uma função objetivo linear
φ(x) = c1x1 + c2x2 + . . . + cnxn que deve ser maximizada ou minimizada
em um conjunto de restrições lineares. Estas restrições constituem igualda-
des ou desigualdades formadas por combinações lineares entre as variáveis de
decisão:
a1x1 + a2x2 + . . .+ anxn = β
a1x1 + a2x2 + . . .+ anxn ≤ β
a1x1 + a2x2 + . . .+ anxn ≥ β
Temos que é fácil converter as restrições de uma forma para outra.
Considere a equação a1x1+a2x2+ . . .+anxx = β , podemos tranformá-la
em duas desigualdades:
a1x1 + a2x2 + . . .+ anxx ≤ β
a1x1 + a2x2 + . . .+ anxx ≥ β
Agora, vamos adotar a seguinte forma denominada forma padrão de um
problema de otimização linear:
max c1x1 + c2x2 + . . .+ cnxn
s.a. a11x1 + a12x2 + . . .+ a1nxn ≤ b1
a21x1 + a22x2 + . . .+ a2nxn ≤ b2
...
am1x1 + am2x2 + . . .+ amnxn ≤ bm
(x1, x2, . . . , xn) ≥ 0
,
5
em que m é o número de restrições e n é o número de variáveis.
As definições a seguir são importantes no entendimento de PL, de modo
que serão exsenciais na aplicaçãoem problemas reais e práticos, como nos
exemplos que serão apresentados.
Definição 3.1 (Variáveis) O modelo de programação linear, como qual-
quer modelo de pesquisa operacional, tem três componentes básicos:
1. Variáveis de decisão que procuramos determinar;
2. Objetivo (meta) que precisamos otimizar (maximizar ou minimizar);
3. Restrições que a solução deve satisfazer.
Definição 3.2 (Solução Fact́ıvel) Uma solução fact́ıvel para um problema
de programação linear é um vetor x pertencente aos reais que satisfaz as
restrições principais e não negatividades.
Definição 3.3 (Solução Básica) Uma solução básica é o único vetor de-
terminado pela escolha de uma matriz básica, fazendo as nxm variáveis asso-
ciadas as colunas que não estão na matriz básica iguais a zero, e resolvendo
o sistema (não singular) de equações para as m variáveis restantes.
Definição 3.4 (Solução Ilimitada) Uma solução ilimitada é aquela em
que a função objetivo pode crescer (caso da maximização) ou decrescer (caso
da minimização), indefinidamente, atendendo a todas as restrições do pro-
blema.
Definição 3.5 (Solução Infaćıvel) Uma solução infact́ıvel é uma solução
em que alguma das restrições de não-negatividade não são atendidas.
Definição 3.6 (Solução Ótima) Havendo solução posśıvel e não havendo
solução ilimitada, a solução ótima é a solução posśıvel que otimiza a função
objetivo. Nesse caso, poderá haver uma ou infinitas soluções ótimas, isto é,
havendo mais de uma solução ótima, haverá infinitas soluções ótimas.
3.3 Passos para a resolução de um problema de Pro-
gramação Linear - PL
Os passos para a resolução de um problema de Programação Linear são:
1. Organizar dados;
6
Tabela 1: Consumo de 1t por hora de cada uma das duas categorias de
carvão.
Carvão Descarga de S(ppm) Descarga fumaça(lb/h) Vapor gerado(lb/h)
C1 1800 2,1 12000
C2 2100 0,9 9000
2. Escolher as variáveis;
3. Definir a solução objetivo;
4. Escrever as restrições;
5. Encontrar a solução ótima.
Para demonstrar como são aplicados os passos para a resolução de um
problema de Programação Linear, seguem exemplos em que foram utilizados.
Exemplo 3.1 Uma usina produz energia através de turbinas de calor. Como
o Estado onde está localizada a usina é rico em depósito de carvão, ela uti-
liza desse recurso para a geração de vapor. No entanto, isso pode resultar
em emissões que não cumprem os padrões da Agência de Proteção Ambien-
tal. As regulamentações da agência limitam a descarga de dióxido de enxofre
a 2000 partes por milhão por tonelada de carvão queimado e a descarga de
fumaça pelas chaminés da usina a 20lb por hora. A usina recebe duas ca-
tegorias de carvão pulverizado, C1 e C2. As duas categorias costumam ser
misturadas antes da queima. Os dados da Tabela 1 são baseados no consumo
de 1t por hora de cada uma das duas categorias de carvão. Qual é o mix
ótimo para a mistura das duas categorias de carvão?
Resolução:
O primeiro passo é formular o problema a fim de identificar a função ob-
jetivo e as restrições. As quantidades em toneladas de dois tipos de carvão,
C1 e C2, podem ser representadas assim:
x1 = toneladas de C1 por hora;
x2 = toneladas de C2 por hora.
7
A função objetivo deve considerar a quantidade de vapor gerado por cada
tipo de carão e as taxas de descarga de fumaça e de enxofre. Assim, para
otimizar a função, isto é, maximizar o resultado, temos:
φ(x1, x2) = 12000x1 + 9000x2
Identificando as restrições que estão envolvendo o sistema:
1. Restrições:
Limite de descarga de enxofre: −200x1 + 100x2 ≤ 0
Descarga de fumaça de C1 e C2: 2, 1x1 + 0, 9x2 ≤ 20
2. Condições obrigatórias:
x1, x2 ≥ 0
Dessa forma, o problema geral será:
max φ(x1, x2) = 12000x1 + 9000x2
s.a. −200x1 + 100x2 ≤ 0
2, 1x1 + 0, 9x2 ≤ 20
x1, x2 ≥ 0
Exemplo 3.2 Uma empresa fabrica dois produtos, A e B. O volume de ven-
das de A é de no mı́nimo 80% do total de venda de ambos (A e B). Contudo,
a empresa não pode vender mais do que 100 unidades de A por dia. Ambos
os produtos usam um matéria prima cuja disponibilidade máxima diária é de
240 lb. As taxas de utilizaa̧ão de matéria prima são de 2 lb por unidade de
A e 4 lb por unidade de B. Os lucros unitários para A e B são $20 e $50,
respectivamente. Determine o mix de produto ótimo para a empresa.
Resolução:
O primeiro passo é formular o problema a fim de identificar a função
objetivo e as restrições. As quantidades dos produtos A e B podem ser repre-
sentadas assim:
x1 = número de unidades de A;
x2 = número de unidades de B.
8
Tabela 2: Preços, custos e despesas dos produtos.
Produto Preço de venda($) Custo e despesa variáveis($)
Produto Alfa 100 50
Produto Beta 200 100
Produto Delta 500 250
Produto Gama 1000 500
Produto Sigma 800 650
A função objetivo deve considerar os lucros unitários de cada produto e
as taxas de utilizaa̧ão de matéria prima. Assim, para otimizar a função, isto
é, maximizar o resultado, temos:
φ(x1, x2) = 20x1 + 50x2
Identificando as restrições que estão envolvendo o sistema:
1. Restrições:
Volume de venda do produto A: 0, 8x1 + 0, 8x2 = x1
Taxa de uso de matéria prima: −0, 2x1 + 0, 8x2 ≤ 2x1 + 4x2 ≤ 240
Venda por dia do produto A: x1 ≤ 100
2. Condições obrigatórias:
x1, x2 ≥ 0
Logo, o problema completo ficaria dessa maneira:
max φ(x1, x2) = 20x1 + 50x2
s.a. x1 = 0, 8x1 + 0, 8x2
−0, 2x1 + 0, 8x2 ≤ 2x1 + 4x2 ≤ 240
x1 ≤ 100
x1, x2 ≥ 0
Exemplo 3.3 Uma empresa produz e vende cinco produtos. Os preços, cus-
tos e despesas estão relacionados na Tabela 2:
A partir do mês de junho, a empresa formalizou um contrato de entrega
de 1.000 produtos Alfa, projetando a venda máxima de mais 4.000 unidades
9
Tabela 3: Preços, custos e despesas dos produtos.
Uso da máq. Uso da máq. Uso da máq.
Produto Dpto. A Dpto. B Dpto. C
Produto Alfa 1 2 1
Produto Beta 2 1 1
Produto Delta 4 2 3
Produto Gama 15 10 5
Produto Sigma 10 6 4
Hs. máq. dispońıvel 3000 3800 2700
do produto, para os meses seguintes. O produto Sigma é fabricado especial-
mente para atender o mercado exterior e é vendido para um cliente espećıfico,
numa quantidade fixa de 120 unidades por mês. Os outros três produtos
(Beta, Delta e Gama), têm grande procura, de modo que qualquer quanti-
dade produzida é absorvida pelo mercado. O processamento de fabricação
passa por três departamentos, cuja produçâo é limitada pela utilização de
horas-máquinas dispońıveis. Na Tabela 3, é apresentado os coeficientes de
utilização por unidade produzida de cada produto.
Os custos e despesas fixos para o mês de junho deve atingir $100.000. A
gerência administrativa da empresa quer conhecer qual deve ser a produção
desse mês, em termos de combinação dos cinco produtos que venham a apre-
sentar o melhor resultado operacional posśıvel (maior lucro), nas condições
de produção, custos, despesas e vendas programadas.
Resolução:
O primeiro passo é formular o problema a fim de identificar a função ob-
jetivo e as restrições. As quantidades produzidas e vendidas de cada produto
podem ser representadas assim:
X1 = Quantidade produzida e vendida dos produtos Alfa;
X2 = Quantidade produzida e vendida dos produtos Beta;
X3 = Quantidade produzida e vendida dos produtos Delta;
X4 = Quantidade produzida e vendida dos produtos Gama;
X5 = Quantidade produzida e vendida dos produtos Sigma.
A função objetivo deve considerar as margens de contribuição unitária
10
de cada produto e os custos de despesas variáveis. Assim, para otimizar a
função, isto é, maximizar o resultado, temos:
φ(x1, x2, x3, x4, x5) = 50x1 + 100x2 + 250x3 + 200x4 + 150x5
Identificando as restrições que estão envolvendo o sistema:
1. Restrições de demanda:
Qtde. a ser vendida em junho de Alfa: x1 ≥ 1000
Qtde. máx. a ser vendida nos próximos meses de Alfa: x1 ≤ 500
Qtde. fixa de vendade Sigma: x5 = 1200
2. Restrições de capacidade fabril:
Hs Máq. dispońıveis no Depto A: x1 + 2x2 + 4x3 + 15x4 + 10x5 ≤ 300
Hs Máq. dispońıveis no Depto B: 2x1 + x2 + 2x3 + 10x4 + 6x5 ≤ 3800
Hs Máq. dispońıveis no Depto C: x1 + x2 + 3x3 + 5x4 + 4x5 ≤ 2700
3. Condições obrigatórias:
x1, x2, x3, x4, x5 ≥ 0
Então, o problema completo seria:
max φ(x1, x2, x3, x4, x5) = 50x1 + 100x2 + 250x3 + 200x4 + 150x5
s.a. x1 + 2x2 + 4x3 + 15x4 + 10x5 ≤ 300
2x1 + x2 + 2x3 + 10x4 + 6x5 ≤ 3800
x1 + x2 + 3x3 + 5x4 + 4x5 ≤ 2700
x1 ≥ 1000
x1 ≤ 500
x5 = 1200
x1, x2, x3, x4, x5 ≥ 0
Para encontrar as soluções ótimas para os exemplos de problemas de Pro-
gramação Linear, 3.1, 3.2 e 3.3, pode-se utilizar um software computacional,
o Excel Solvel.
11
4 O Método Simplex
Nas formulações anteriores, problemas com mais de duas variáveis não po-
deriam ser solucionados com o método gráfico. Desta forma é necessário o
estudo de outro procedimento para a busca de soluções. Agora, será apre-
sentado mais um procedimento geral para resolução de problemas de Pro-
gramação Linear, denominado Método Simplex e que foi desenvolvido em
1947 por George B. Dantzig. O método simplex é um método interativo
(algoritmo) utilizado para achar, algebricamente, a solução ótima de um
problema de P.L.
Em vez de enumerar todas a soluções básicas (pontos extremos) do pro-
blema de programação linear, o método simplex investiga somente algumas
dessas soluções selecionadas. Portanto o método simplex tenta passar de
um ponto extremo na região de soluções para um ponto extremo melhor até
achar a solução ótima.
Para compreendermos o método simplex, é entendermos a representação
gráfica de um problema de otimização linear, pois usamos essa representação
para encontrarmos a solução ótima a partir dos vértices[1, 2].
4.1 Transição da solução gráfica para a solução algébrica
A transição da solução gráfica para a solução algébrica é realizada através
de 3 passos, tanto para o método gráfico quanto para o método algébrico[1, 2].
Método gráfico:
1. Represente todas as restrições em gráfico, entre elas as restrições de
não negatividade. Região de soluções consiste em um número infinito
de pontos viáveis.
2. Identifique os pontos extremos viáveis da região de soluções. Candida-
tos a solução ótima são dados por um número finito de pontos extremos.
3. Use a função objetivo para determinar o ponto extremo ótimo entre
todos os candidatos.
Método algébrico:
1. Represente a região de soluções por m equações em n variáveis e res-
trinja todas as variáveis a valores não negativos. O sistema tem um
número infinito de soluções viáveis.
12
2. Determine as soluções básicas viáveis das equações. Candidatas a
solução ótima são dados por um número finito de soluções básicas
viáveis.
3. Use a função objetivo para determinar a solução básica viável ótima
entre todas as candidatas.
4.2 Determinação algébrica dos pontos extremos
Em um conjunto de m,n equações, com m menor que n, se igualarmos as
n−m variáveis a zero, e depois resolvermos asm equações para asm variáveis
restantes, a solução resultante, se for única, é denominada solução básica e
deve corresponder a um ponto extremo (viável ou inviável) da região de
soluções.
4.3 Método Simplex
O método simplex encontra um vétice ótimo na representação gráfica pes-
quisando apenas um subconjunto (em geral pequeno) dos K vértices. Para
construir um método de resolução de um problema de otimização linear, de-
vemos responder a duas perguntas-chave: Dada uma solução básica fact́ıvel
(candidata a solução ótima) temos que fazer as seguintes indagações:
1. Essa solução é ótima?
2. Caso não seja ótima, como determinar uma outra solução básica fact́ıvel
melhor?
4.3.1 Passos para resolução de problemas pelo Método Simplex
Para iniciarmos o Método Simplex necessita-se de uma solução básica viável
inicial, a qual é, um dos pontos extremos. Este método verifica se a presente
solução é ótima. Se esta não for é porque um dos demais pontos extremos
adjacentes (vértice) fornecem valor menor para a função objetivo que a atual,
quando o problema considerado é de minimização. Ele então faz uma mu-
dança de vértice na direção que mais aumente a função objetivo e verifica se
este novo vértice é ótimo.
O processo termina quando estando num ponto extremo, todos os outros
pontos extremos adjacentes fornecem valores menores para a função objetivo.
Portanto, a troca de vértice, faz uma variável não básica diminuir(assumir
valor negativos) ao mesmo tempo em que zera uma variável básica (para
13
possibilitar a troca) conservando a factibilidade do Problema de Programação
Linear.
Para isso, escolhemos uma variável, cujo custo relativo é mais negativo
(não é regra geral), para entrar na base, e as trocas de vértices são feitas até
que não exista mais nenhum custo relativo negativo. A variável que sairá
da base é aquela que ao se anular garante que as demais continuem maiores
ou iguais a zero, quando aumentamos o valor da variável que entra na base
(respeitando a factibilidade)[1, 2].
O Método Simplex compreenderá, portanto, os seguintes passos:
1. Achar uma solução fact́ıvel básica inicial;
2. Verificar se a solução atual é ótima. Se for, pare. Caso contrário, siga
para o passo 3.
3. Determinar a variável não básica que deve entrar na base;
4. Determinar a variável básica que deve sair da base;
5. Atualizar o sistema a fim de determinar a nova solução fact́ıvel básica,
e voltar ao passo 2.
Para problemas em que não é posśıvel encontrar uma solução pelo método
agébrico existem softwares computacionais, estando relacionados com oMétodo
Simplex, pois trata-se de problemas lineares, que auxiliam na resolução des-
ses problemas, como por exemplo, a planilha eletrônica Solver que é re-
comendável para problemas considerados médios. Os detalhes sobre esse
método serão tratados a seguir, assim como as soluções dos Exemplos 3.1,
3.2 e 3.3, respectivamente.
5 Solução de problema de Programação Li-
near - SOLVER
Como já mencionado, para a solução de um problema de Programação Linear
de maior porte, em que muitas variáveis e restrições devem ser consideradas,
é recomendado o aux́ılio de um software computacional. Por isso, o desenvol-
vimento de algoritmos computacionais eficientes e precisos tem sido a maior
preocupação entre os pesquisadores. Programas adequados existem, virtual-
mente, para cada sistema computacional comercial desenvolvido nos últimos
20 anos.
14
Problemas de grande porte requerem sistemas computacionais potentes
e, portanto, sistemas paralelos tem sido utilizados nos últimos anos. Entre-
tanto, problemas menores podem ser resolvidos em um computador pessoal
utilizando um dos softwares desenvolvidos para resolução de problemas de
Programação Linear, como por exemplo a planilha Excel Solver.
Na prática, quando os modelos t́ıpicos de programação linear podem en-
volver milhares de variáveis e restrições, o único modo viável de resolver tais
modelos é usar o computador. Um software popular que pode ser utilizado
para esses tipos de problemas e para usuários de panilhas é o Excel Solver.
Com o Excel Solver, a planilha é o meio de entrada e sáıda para a pro-
gramação linear.
O processo de resolução de modelos matemáticos utlizando o Solver da
panilha Excel compreende, basicamente, em 3 fases:
1. Descrição do Modelo: inserção de todos os parâmetros do problema,
valores iniciais para as variáveis de decisão e os cálculos que relacio-
nam esses dados na planilha. Em particular, a planilha deve incluir
a fórmula que relaciona a função objetivo ás células que representam
as variáveis de decisão, de tal maneira que qualquer variação nestas
últimas provoque a variaçãocorrespondente na função objetivo;
2. Chamada do Solver: a chamada do Solver envolve a indicação das
células correspondentes as função objetivo, restrições e variáveis do
modelo; configuração dos parâmetros de otimização e da exibição das
soluções;
3. Análise de Sensibilidade: após a obtenção da solução ótima, é posśıvel
realizar anaĺıses das mudanças nessa solução em função de modificações
nos parâmetros do modelo. A anaĺıse de sensibilidade é realizada sem
a necessidade de novas execuções do Solver[3, 4].
Depois de seguir essas 3 fases é possíıvel encontrar as soluçõesdos Exem-
plos de problemas de Programação Linear analisados. As soluções no Solver
estã representadas a baixo:
Exemplo 5.1 De acordo com o exemplo 3.1, se utilizarmos o Solver para
encontrarmos sua solução temos o resultado na Tabela 4:
Portanto, utilizando o software Excel Solver encontamos a solução ótima
para o Exemplo 3.1, que será:
solução ótima (x1, x2) = (5, 13; 10, 26), φ(x1, x2) = 153.846lb
15
Tabela 4: Solução do exemplo 3.1 pelo modelo Excel Solver
x1 x2 Total Sinal Limite
Restrição 1 -200 100 0 (≤) 0
Restrição 2 2,1 0,9 20 (≤) 20
Lucro 12000 9000 153.846
Solução 5,13 10,26
Tabela 5: Solução do exemplo 3.2 pelo modelo Excel Solver
x1 x2 Total Sinal Limite
Restrição 1 -0,2 0,8 0 (≤) 0
Restrição 2 2 4 0 (≤) 0
Restrição 3 1 0 80 (≤) 100
Lucro 20 50 2600
Solução 20 80
Exemplo 5.2 De acordo com o exemplo 3.2, se utilizarmos o Solver para
encontrarmos sua solução temos o resultado na Tabela 5:
Portanto, utilizando o software Excel Solver encontamos a solução ótima
para o Exemplo 3.2, que será:
solução ótima (x1, x2) = (80, 20), φ(x1, x2) = $2600
Exemplo 5.3 De acordo com o exemplo 3.3, se utilizarmos o Solver para
encontrarmos sua solução temos o resultado na Tabela 6:
Portanto, utilizando o software Excel Solver encontamos a solução ótima
para o Exemplo 3.3, que será:
solução ótima (x1, x2, x3, x4, x5) = (1000, 0, 200, 0, 120), φ(x1, x2, x3, x4, x5) = $1320
Conclúı-se então, que, utilizando o modelo Excel Solver e seguindo seus
passos de utilização de acordo com as 3 fases, encontramos a solução ótima
para o exemplo 3.1, 3.2 e 3.3, conforme, respectivamente, mostram as Tabelas
4, 5 e 6.
16
Tabela 6: Solução do exemplo 3.3 pelo modelo Excel Solver
x1 x2 x3 x4 x5 Total Sinal Limite
Restrição 1 1 2 4 15 10 220 (≤) 3000
Restrição 2 2 1 2 10 6 270 (≤) 3800
Restrição 3 1 1 3 5 4 148 (≤) 2700
Restrição 4 1 100 (≤) 5000
Restrição 5 1 100 (≥) 1000
Restrição 6 1 120 (≤) 120
Lucro 50 100 250 200 150 1320
Solução 1000 0 200 0 120
6 Planejamento de Tratamento de Câncer por
Radiação
Modelos de programação linear tem sido usados extensivamente para encon-
trar bons planos de tratamento por radioterapia. A primeira formulação
proposta como um molelo de programação linear ocorreu em 1968.[10] A
radioterapia é uma das técnicas mais importantes atualmente para o trata-
mento de câncer e o objetivo do tratamento é eliminar as células do tumor
através de radiação ao mesmo tempo em que procura evitar a destruição de
células vizinhas saudáveis também afetadas pela radiação.
Existem, atualmente, máquinas inspiradas na tomografia computado-
rizada que emitem radiação ao longo de todo o corpo do paciente, por
um lado, ampliando as possibilidades de minimização destes efeitos cola-
terais e, por outro, aumentando a complexibilidade de obtenção de planos de
tratamento.[10]
6.1 O Modelo de Programação Linear para Radiotera-
pia
Primeiramente, na resolução de um planejamento radioterápico, é preciso de-
finir a localização das células canceŕıgenas e da região cŕıtica que a circunda,
onde há tecidos saudáveis. Em seguida, é esboçado com abordagem linear o
cálculo da intensidade de radiação, que esta, por sua vez, é de acordo com a
peculiaridade do caso.
O planejamento é feito para minimizar a dose total emitida para as áreas
que estão ao redor da área tumoral, onde esta radiação pode ser de efeito
17
contraditório trazendo malef́ıcios futuros. Uma das preocupações em se atin-
gir células sadias é devido a sua taxa de regeneração que é em longo prazo
e, consequentemente, o corpo humano é dificultado para a eliminação do vo-
lume extra de tecido morto produzido por altas doses de radiação. Portanto,
uma dose letal uniformemente distribúıda na região do tumor é crucial para
o sucesso no plano do tratamento.
O modelo proposto pode ser representado pela seguinte formulação:
max wlT t+ uTc c+ u
T
g g
s.a. lt − Lt ≤ ATx ≤ ut
ACx ≤ uc + UCc
AGx ≤ ug + UGg
0 ≤ Lt ≤ lt
−uc ≤ UCc
UGg ≥ 0
x ≥ 0
(1)
Em que, a função objetivo é representada pela soma ponderada de três
metas:
1. lT t, mede o quanto falta para que o plano consiga aplicar a dose mı́nima
na região do tumor;
2. uTc c mede a quantidade de radiação acima da prescrita recebida pela
região cŕıtica;
3. uTg g mede a quantidade de radiação acima da prescrita nos demais
tecidos saudáveis.
Temos ainda que:
- w é escalar positivo;
- x é a dose do sub-raio que entra na imagem para alcançar o pixel p;
- ut representa o vetor de limite superior para a radiação no tumor, uc na
estrutura cŕıtica e - ug no restante de tecido saudável;
- lt representa o vetor de limite inferior para rediação na estrutura cŕıtica;
- AT (tumor), AC (estrutura cŕıtica) e AG (restante de tecido saudável) são
sub-matrizes.
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 ve-
tores t, c e g, respectivamente. As matrizes L,UC e UG definem como medir a
elasticidade e l, uc e ug controlam a penalização ou recompensa com relação
a eslasticidade.
18
7 Conclusão
Promover resultados computacionais do modelo (1) seria uma próxima etapa
a ser realizada a partir da aplicação de um caso real. Como prox́ımos passos,
poderiam ser abordados pelo menos dois métodos de otimização linear com o
objetivo de realizar uma investigação e comparação, para que se possa chegar
a averiguar quais resultados seriam mais conclusivos e pertinentes para o
projeto e modelo propostos. A utilização do software livre, de código aberto,
GLPK, GNU Linear Programming Kit, usado para resolver problemas de
otimização linear, linear inteira e mista, que sua biblioteca implementa o
método simplex e o método de pontos interiores para a solução de problemas
lineares, seria uma ótima opção futura para encontrar a solução do modelo
(1).
Referências
[1] TAHA, H. A. Pesquisa Operacional: Uma visão geral. 8. ed. São Paulo:
Pearson Prentice Hall, 2008.
[2] ARENALES, M. N. Pesquisa Operacional. 6. ed. Rio de Janeiro: Else-
vier Editora Ltda., 2007. p. 15–98.
[3] MORETTI, A.C. Moretti. Programação Linear: Implementação e re-
solução de modelos matemáticos utilizando a planilha Excel. Campi-
nas: UNICAMP, 2008. Dispońıvel em: http://www.ime.unicamp.br/
~moretti/er500/TutorialExcel_
ms428.pdfȦcesso em: 05 mar. 2015.
[4] NOGUEIRA, F. Pesquisa Operacional - Tutorial sobre softwares. São
Paulo. 2010. Dispońıvel em: http://www.ufjf.br/epd015/files/
2010/06/tutorial.pdfȦcesso em: 12 abr. 2015.
[5] HAHN, J. Latex For Everyone - A Reference Guide and Tutorial for
Typesetting Documents Using a Computer. Rio de Janeiro: Prentice-
Hall do Brasil Ltda., 2011.
[6] SILVA, M. N. Curso de Introdução ao LaTex. Aracaju: Uni-
versidade Estadual Vale do Acaraú, 2011. Dispomı́vel em:
http://arquivoescolar.org/bitstream/arquivo-e/197/1/
apostila_latex_marcio_nascimento_da_silva_uva_ce_brasil.
pdf. Acesso em: 23 jun. 2015.
19
http://www.ime.unicamp.br/~moretti/er500/TutorialExcel_
http://www.ime.unicamp.br/~moretti/er500/TutorialExcel_
 ms428.pdf
http://www.ufjf.br/epd015/files/2010/06/tutorial.pdf
http://www.ufjf.br/epd015/files/2010/06/tutorial.pdf
http://arquivoescolar.org/bitstream/arquivo-e/197/1/apostilahttp://arquivoescolar.org/bitstream/arquivo-e/197/1/apostila
_latex_marcio_nascimento_da_silva_uva_ce_brasil.pdf
_latex_marcio_nascimento_da_silva_uva_ce_brasil.pdf
[7] FROSSARD, A. C. P. Programação Linear: Maximização de
Lucro e Minimização de Custos. Fortaleza: Revista CientÃ-
fica da Faculdade Lourenço Filho - v.6, n.1, set 2009. Dis-
pońıvel em: https://unoeste.br/site/biblioteca/documentos/
Manual-Normalizacao.pdfȦcesso em: 28 jun. 2015.
[8] GOMES, F. A. M. Interpretação geométrica e resolução gráfica. Cam-
pinas: UNICAMP, 2009. Dispońıvel em: http://www.ime.unicamp.
br/~chico/mt503/repgrafica.pdfȦcesso em: 17 de mai. 2015.
[9] GARCIA, E. A. R. Programação Linear: uma aplicação a contabilidade
de custos no processo de tomada de decisão. São Paulo: Universidade
de São Paulo, 2007. Dispońıvel em: http://www.intercostos.org/
documentos/Trabajo066.pdfȦcesso em: 21 de jun. 2015.
[10] C. B. B. Cid, ”Planejamento do tratamento por radioterapia através de
métodos de pontos interiores”, Dissertação de Mestrado, ICMC-USP,
2003.
[11] R. Viana, ”Planejamento otimizado para o tratamento de câncer por
radioterapia”, Dissertação de Mestrado , IBB-UNESP, 2010.
20
https://unoeste.br/site/biblioteca/documentos/Manual-Normalizacao.pdf
https://unoeste.br/site/biblioteca/documentos/Manual-Normalizacao.pdf
http://www.ime.unicamp.br/~chico/mt503/repgrafica.pdf
http://www.ime.unicamp.br/~chico/mt503/repgrafica.pdf
http://www.intercostos.org/documentos/Trabajo066.pdf
http://www.intercostos.org/documentos/Trabajo066.pdf
	Introdução
	Objetivos
	A Pesquisa Operacional - PO
	Solução do modelo de PO
	A Programação Linear - PL
	Razões para o uso da Programação Linear
	A Modelagem com Programação Linear - PL
	Passos para a resolução de um problema de Programação Linear - PL
	O Método Simplex
	Transição da solução gráfica para a solução algébrica
	Determinação algébrica dos pontos extremos
	Método Simplex
	Passos para resolução de problemas pelo Método Simplex
	Solução de problema de Programação Linear - SOLVER
	Planejamento de Tratamento de Câncer por Radiação
	O Modelo de Programação Linear para Radioterapia
	Conclusão