Neste trabalho é apresentada uma proposta para a otimização no serviço de saúde no estado do Paraná com relação ao fluxo de pacientes dentro do estado e a regionalização (divisão) do estado, obtendo novas configurações hierárquicas para o mesmo. Quanto à regionalização, a proposta consiste em dividir o estado em regiões menores, formadas por várias cidades, vinculadas a uma cidade sede, principal responsável pelo atendimento no seu nível de resolutividade. Com relação ao fluxo de pacientes, é proposto um algoritmo que, ao mesmo tempo em que organiza as informações, otimiza o fluxo. Já para a regionalização, fez-se uso do algoritmo branch and price, que utiliza o algoritmo de geração de colunas em cada nó de uma árvore branch and bound. A técnica proposta apresentada para otimizar o fluxo de pacientes mostrou-se eficaz e útil, pois além de fazer o controle dos procedimentos médicos realizados em cada cidade, também define para qual cidade o paciente deve ser encaminhado, respeitando a divisão hierárquica do estado. Já o algoritmo branch and price, utilizado para a otimização na regionalização do estado, é bastante interessante, pois tenta melhorar a referida divisão hierárquica do estado, levando em consideração o número de habitantes e o número de procedimentos médicos de cada município do estado. Os resultados obtidos têm atendido às expectativas da SESA-PR.