Programação Linear

Origem: Wikilivros, livros abertos por um mundo aberto.

Nuvola apps edu miscellaneous.png Esta página é um monomódulo, ou seja, não está inserida em nenhum livro.
Ajude o Wikilivros inserindo-a em um livro existente ou por criar.
Rekopis chopin.jpg Esta página é somente um esboço.
Ampliando-a você ajudará a melhorar o Wikilivros.

O problema geral de programação linear é utilizado para otimizar (maximizar ou minimizar) uma função linear de variáveis, chamada de função objetivo, sujeita a uma série de equações (ou inequações) lineares, chamadas restrições.

A formulação do problema a ser resolvido segue três pontos básicos:

  • Definição do objetivo do problema
  • Definição das variáveis de decisão envolvidas
  • Conhecimento das restrições a que está sujeito o problema

[editar] Formulação de Modelos

O problema geral de programação linear pode ser definido por

Maximizar (ou minimizar) a função objetivo

Z = c_1 \cdot x_1 + c_2 \cdot x_2 + ... + c_n \cdot x_n \,\!

sujeita as restrições

a_{11} \cdot x_1 + a_{12} \cdot x_2 + ... + a_{1n} \cdot x_n \le b_1 \,\!
a_{21} \cdot x_1 + a_{22} \cdot x_2 + ... + a_{2n} \cdot x_n \le b_2 \,\!
a_{31} \cdot x_1 + a_{32} \cdot x_2 + ... + a_{3n} \cdot x_n \le b_3 \,\!
a
a_{m1} \cdot x_1 + a_{m2} \cdot x_2 + ... + a_{mn} \cdot x_n \le b_m \,\!

considerando que as variáveis de decisão assumem valores positivos, i.e.,

 x_1, x_2, x_n \ge 0 \,\!

[editar] Solução Gráfica

Um problema que contenha duas variáveis pode ser resolvido graficamente.

Traça-se um gráfico com os seus eixos sendo as variáveis x_1\,\! e x_2\,\!.

A partir deste gráfico traçam-se as restrições do problema e delimita-se a região viável.

Após isso, traça-se uma reta com a inclinação da função objetivo, buscando retas paralelas a ela que forneçam a solução para o problema.

Exemplo
Obtido em "http://pt.wikibooks.org/wiki/Programa%C3%A7%C3%A3o_Linear"