AULA 13: MODELAGEM MATEMÁTICA DE PROBLEMAS LINEARES
Academia da Força Aérea
Verifique ao final desta aula se você é capaz de:
1- Definir a estrutura de um modelo de programação linear (Cn).
Determinístico: não considera as incertezas dos dados do modelo
– Contínuo: as variáveis podem assumir qualquer valor pertencente aos reais
– Inteira: as variáveis somente podem assumir valores inteiros
– Binária : as variáveis somente podem assumir valores 0 ou 1
Probabilístico: considera as incertezas dos dados do modelo
– Não faz parte do escopo da disciplina
De uma forma simples, resume-se à criação de um modelo matemático (um padrão ou fórmula matemática) para explicação ou compreensão de um fenômeno natural. Esse fenômeno pode ser de qualquer área do conhecimento, incluindo o cotidiano da vida militar. Os modelos, para alcançar utilidade prática, devem ser livres de detalhes pequenos, pouco significativos ou onerosos.
Em operações militares, é essencial otimizar a distribuição de recursos limitados, como tropas, suprimentos, equipamentos e veículos, para atender às necessidades estratégicas.
Por exemplo, considere um cenário em que há várias missões a serem realizadas e uma quantidade limitada de tropas disponíveis. O objetivo é determinar a alocação ideal de tropas para cada missão de forma a maximizar a eficiência ou minimizar os custos.
A programação linear pode ajudar a encontrar a solução ótima que atenda às restrições de recursos e objetivos estratégicos.
Em operações militares, o roteamento eficiente de veículos é fundamental para a logística e mobilidade das tropas.
A programação linear pode ser usada para resolver problemas de roteamento de veículos, determinando as rotas mais eficientes para entrega de suprimentos, evacuação médica, apoio logístico e outras operações.
O objetivo é minimizar os custos operacionais, como consumo de combustível ou tempo de viagem, ao mesmo tempo em que atende às restrições, como capacidade dos veículos, segurança das rotas e prioridades estratégicas.
Busca alguma vantagem por meio da representação simplificada dos elementos e fenômenos que o cérebro lida.
A atividade de modelagem procura o equilíbrio entre o benefício da simplificação e o ônus da redução do alcance da aplicação da representação realizada.
A capacidade de simplificação útil é a chave da construção de modelos operacionalmente factíveis e viáveis, não sua perfeita aderência à realidade.
No planejamento de uma operação de resgate em uma área montanhosa, o comandante militar enfrenta o desafio de criar um modelo que represente adequadamente a topografia do terreno.
Se o modelo for simplificado demais, perdem-se informações cruciais sobre a elevação e características do terreno, dificultando a tomada de decisões estratégicas. Por outro lado, se o modelo for detalhado em excesso, ele se torna complexo e difícil de gerenciar, resultando em sobrecarga de informações.
Portanto, é essencial encontrar um equilíbrio entre a simplificação necessária para tornar o modelo gerenciável e o detalhamento suficiente para refletir as características essenciais do terreno, permitindo que o comandante tenha um modelo útil e relevante para o planejamento da operação de resgate.
Critério de otimalidade: é o que desejamos com o modelo. É uma medida da eficiência da missão.
Variáveis de decisão: é um conjunto de variáveis manipuláveis no procedimento de busca pelo ótimo. Sua descrição deve ser precisa, indicando seu significado e e sua unidade de medida.
Função objetivo: é a transcrição do critério de otimalidade em termos das variáveis de decisão do problema. É uma função linear que deve ser maximizada ou minimizada.
Restrições lineares: expressões que representam as limitações impostas ao problema em função das variáveis de decisão, os valores assumidos pelas variáveis de decisão devem satisfazer todas as restrições definidas pelos parâmetros do sistema real.
Proporcionalidade: o valor das equações é proporcional ao nível de atividade de cada variável de decisão. Se uma unidade custa x, duas unidades custarão 2x e assim sucessivamente.
Aditividade: o todo é a soma das partes. As variáveis do modelo são entidades totalmente independentes não permitindo que haja interdependência entre as mesmas. Em outras palavras, o valor total da função objetivo e das restrições pode ser calculado somando os efeitos individuais das variáveis de decisão.
Certeza: Os coeficientes das variáveis de decisão, da função objetivo e das restrições devem ser conhecidos com certeza e devem ser constantes. Não pode haver incerteza. Isso significa que os valores dos coeficientes não dependem de incertezas, probabilidades ou variabilidade.
Fracionamento: As variáveis de decisão podem assumir valores contínuos em um intervalo real, permitindo que sejam fracionárias ou decimais. Isso implica que as soluções ótimas podem ter valores reais, não apenas valores inteiros. Arredondar valores pode invalidar o valor ótimo.
É importante levar em consideração essas hipóteses ao modelar um problema e aplicar a programação linear para garantir a validade e a precisão dos resultados obtidos.
Função objetivo: min ou max \(c_1x_1 + c_2x_2+...+c_nx_n\)
Sujeito a:
Restrições Estruturais
\[\begin{gather*} a_{11}x_1 + a_{12}x_2 + ... +a_{1n}x_n \space (=, \ge, \le) \space b_1\\ a_{21}x_1 + a_{22}x_2 + ... +a_{2n}x_n \space (=, \ge, \le) \space b_2\\ ...\\ a_{m1}x_1 + a_{m2}x_2 + ... +a_{mn}x_n \space (=, \ge, \le) \space b_m\\ \end{gather*}\]Restrições de Sinal
\(x_i \ge 0, \space \forall i=1,2,...,n\) ou
\(x_i \le 0, \space \forall i=1,2,...,n\) ou
\(x_i\) livre de sinal \(i=1,2,...,n\)
A FAB pode usar um software de otimização baseado em programação linear para resolver problemas dessa natureza.
Para efeitos do emprego na sua vida profissional sugerimos o uso do pacote lpSolve da linguagem R pois é gratuito e viável para problemas complexos.
Para efeitos de treinamento é possível além desse pacote lpSolve, utilizar o phpsimplex disponível online no endereço http://www.phpsimplex.com/simplex/simplex.htm?l=pt
Suponha que um comandante militar está responsável por planejar as operações em duas frentes de batalha diferentes. O objetivo é determinar o número de horas de operação militar (variáveis de decisão: \(x_1\) e \(x_2\)) a serem alocadas em cada frente, levando em consideração as restrições de recursos (a ser detalhada no próximo slide) e maximizando a eficácia da operação, ou seja, o número de alvos destruídos. Considere que cada hora na frente 1 destrói 2 alvos enquanto que na frente 2 cada hora destrói 3 alvos.
A formulação completa do problema de programação linear seria a seguinte…
Critério de otimalidade: Maximizar o número de alvos destruídos.
Variáveis de Decisão: \(x_i\) = quantidade de horas da operação militar na frente \(i=1(A),2(B)\)
Função Objetivo: Maximizar \(Z = 2x_1 + 3x_2\) (mede a eficácia da operação, ou seja, o número total de alvos destruídos)
Restrições:
\(x1 + x2 ≤ 24\) (restrição de tempo, a operação não pode ultrapassar 24h)
\(10x1+ 8x2 ≤ 200\) (restrição de recursos humanos, na frente A utiliza 10 militares por hora, na frente B utiliza 8 militares por hora e há no máximo 200 militares para esta operação)
\(5x_1 + 8x_2 ≤ 150\) (restrição de alimentos, cada hora em A gasta 5 kg de alimentos, cada hora em B gasta 8 kg de alimentos e há no máximo 150 kg de alimentos)
Restrição de sinal
\(x_i \ge 0, \space i=1,2\)
Utilize o phpsimplex e veja o resultado. http://www.phpsimplex.com/simplex/simplex.htm?l=pt
Utilize o R e veja o resultado
library(lpSolve) #precisa instalar o pacote caso não tenha
coef.objetivo = c(2, 3)
R1 = c(1, 1)
R2 = c(10, 8)
R3 = c(5, 8)
restricoes = rbind(R1,R2,R3)
b = c(24, 200, 150)
sinal = c("<=","<=","<=")
solucao = lpSolve::lp(direction = "max",
objective.in = coef.objetivo,
const.mat = restricoes, const.dir = sinal,
const.rhs = b, all.int = F)
solucaoSuccess: the objective function is 57.5 [1] 10.0 12.5A operação deve ser planejada para um total de 22.5 horas, sendo 10h para a frente A e 12.5h para a frente B. A eficácia desta operação atingirá um total de 57.5 alvos destruídos.
Desafio: Pense numa solução melhor do que esta. Caso encontre, mostre para a professora.
