Funções e Otimização Linear

Funções Lineares

• Uma função f é linear se, para vetores x e y e um número a, é válida a propriedade: f(x + y) = f(x) + f(y) e f(a · x) = a · f(x).
• Exemplos de funções lineares:
  • f(x) = 2x
  • f(x1, x2) = 2x1 + 3x2
  • f(x1, x2, x3) = x1 − x2 + 5x3
• Exemplos de funções que não são lineares:
  • f(x) = x + 5
  • f(x1, x2) = x1 x2
  • f(x1, x2, x3) = x21 + x3

Otimização Linear

• A otimização de uma função linear (determinar seu máximo ou mínimo) é inicialmente uma tarefa simples.
• A dificuldade surge quando há várias variáveis e restrições que as variáveis devem satisfazer.
• As restrições nesses casos são lineares, mas ainda assim os problemas podem ser complexos.

Introdução à Programação Linear (PL)

• PL é um modelo de programação matemática que visa encontrar o máximo ou mínimo de uma função linear sujeita a um número finito de restrições lineares.
• A PL possui diversas aplicações práticas em áreas como logística, mercado financeiro, ciências sociais e naturais.
• Leonid Kantorovich e George Dantzig tiveram papel fundamental no desenvolvimento da PL.
  • Kantorovich utilizou a PL para modelar a economia da União Soviética.
  • Dantzig desenvolveu o algoritmo simplex, que ainda hoje é utilizado para resolver problemas de PL.
• Os computadores modernos permitem resolver problemas de PL com centenas de milhares de variáveis.

Componentes de um Problema de PL

• Variáveis de decisão: Representam as decisões que devem ser tomadas no problema.
• Função objetivo: Representa o benefício ou custo associado às decisões em um valor numérico.
• Restrições: Limitam os recursos do mundo real, impondo regras que a solução deve obedecer.

Exemplo de PL

• Encontrar o máximo da função f(x1, x2) = x1 + x2, sendo x1 e x2 sujeitos às seguintes restrições:
  • x1 ≥ 0
  • x2 ≥ 0
  • 2x1 + x2 ≤ 4
  • x1 + 2x2 ≤ 3

Formalização de PL

• Uma PL é definida como um problema de maximizar ou minimizar uma função linear (ou afim), sujeita a restrições lineares.
• Exemplo:
  • max 3x1 + 2x2 − x3 + 5
  • sujeito a:
    • x1 + x2 ≤ 9
    • x3 ≤ 3
    • x1, x2, x3 ≥ 0

Soluções e Viabilidade

• Uma solução para uma PL é a atribuição de valores às variáveis.
• Uma solução é viável quando satisfaz todas as restrições.

Programação Inteira (PI)

• PI é uma PL com a restrição de que as variáveis de decisão devem ser inteiras.
• A solução ótima de uma PI não está necessariamente na fronteira do poliedro.
• O ótimo da PL é sempre maior ou igual que o ótimo da PI, em problemas de maximização.
• Se todos os vértices do poliedro são pontos de coordenadas inteiras, o ótimo da PL e da PI coincidem.
• A maioria das PIs não possui estrutura para serem resolvidas por algoritmos polinomiais.
• Os algoritmos para resolução de PIs possuem complexidade exponencial, mas funcionam bem na prática em muitos casos.

Modelagem de PIs

• Muitos problemas do mundo real podem ser modelados como PIs, como a otimização de produção e planejamento de dietas.
• Exemplo: uma empresa possui N projetos nos quais pode investir, sendo que cada projeto i ∈ N possui um retorno esperado positivo ci (em reais). A empresa deseja maximizar o retorno total, investindo no máximo k projetos.

Algoritmo Simplex

• O algoritmo simplex é um método para resolver PLs.
• Ele é baseado na ideia de mover-se de um vértice viável do poliedro para outro, sempre buscando melhorar o valor da função objetivo.
• Se houver um custo reduzido positivo, a solução pode ser melhorada adicionando a variável correspondente à base.