Pesquisa operacional/Introdução à Programação Linear: diferenças entre revisões
[edição não verificada] | [edição verificada] |
Conteúdo apagado Conteúdo adicionado
Reverted 1 edit by 189.35.255.122 (talk). (TW) |
Sem resumo de edição |
||
Linha 1:
O problema geral de programação linear é utilizado para '''otimizar''' (maximizar ou minimizar) uma [[w:função linear|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
==O que é Programação Linear?==
Linha 22 ⟶ 29:
O que temos acima é um modelo de Programação Linear. Ele é formado sempre por uma função linear (que é a função objetivo) e por um conjunto de ineqüações lineares (restrições do problema). No exemplo acima, desejamos obter o maior lucro possível (maior valor de Z). O objetivo da programação linear é justamente fornecer ferramentas para resolver o desafio de encontrar o maior ou o menor valor possível em uma função linear cujas variáveis possuem restrições.
Assim, o problema geral de programação linear pode ser definido por:
Maximizar (ou minimizar) a função objetivo
<math>Z = c_1 \cdot x_1 + c_2 \cdot x_2 + ... + c_n \cdot x_n \,\!</math>
sujeita as restrições
<math>a_{11} \cdot x_1 + a_{12} \cdot x_2 + ... + a_{1n} \cdot x_n \le b_1 \,\!</math>
<math>a_{21} \cdot x_1 + a_{22} \cdot x_2 + ... + a_{2n} \cdot x_n \le b_2 \,\!</math>
<math>a_{31} \cdot x_1 + a_{32} \cdot x_2 + ... + a_{3n} \cdot x_n \le b_3 \,\!</math>
a
<math>a_{m1} \cdot x_1 + a_{m2} \cdot x_2 + ... + a_{mn} \cdot x_n \le b_m \,\!</math>
considerando que as variáveis de decisão assumem valores positivos, i.e.,
<math>x_1, x_2, x_n \ge 0 \,\!</math>
== 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 <math>x_1\,\!</math> e <math>x_2\,\!</math>.
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.
==A História da Programação Linear==
Linha 37 ⟶ 72:
==A Criação de Modelos==
O conceito de modelos é de importância fundamental ao estudarmos pesquisa operacional. Um modelo é uma representação simplificada da realidade. Para criarmos um modelo de programação linear, precisamos identificar em um problema qual é a '''função objetivo''', as '''restrições''' e o tipo de '''otimização''' que desejamos (queremos achar o máximo ou o mínimo da função-objetivo?). Veja o exemplo abaixo:
Uma empresa fabrica mesas e cadeiras. O quadro abaixo mostra os recursos consumidos por unidade de cada produto e os seus lucros.Quantas mesas e cadeiras podem ser fabricados para se maximizar o lucro?
{| border=2
|+ Unidades Necessárias
|-
| Recurso
| Mesa
| Cadeira
| Quantidade Disponível
|-
| Madeira
| 30
| 20
| 310
|-
| Metal
| 5
| 10
| 113
|-
| Lucro
| 6
| 8
| -
|}
A nossa função objetivo é o total de lucro da venda de mesas (M) e cadeiras (C). Queremos descobrir qual o valor máximo possível de lucro que podemos obter. Logo, nossa função objetivo é:
Máx <math>Z = 6M + 8C</math> (Função-Objetivo)
Agora precisamos analisar as restrições. Temos uma quantidade máxima de madeira disponível (310) e cada mesa e cada cadeira gastam uma certa quantidade deste material (30 e 20). Logo, temos uma restrição:
<math>30M + 20C \leq 310</math> (Restrição 1)
Da mesma forma, existe uma quantidade limitada de metais, o que nos dá a segunda restrição:
<math>5M + 10C \leq 113</math> (Restrição 2)
Além disso, sabemos que não podemos fabricar uma quantidade negativa de cadeiras ou mesas:
<math>M, C \geq 0</math>
Pronto! Terminamos de construir o nosso modelo!
==Solução Gráfica==
|