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
Vogone (discussão | contribs)
Reverted 1 edit by 189.35.255.122 (talk). (TW)
Abacaxi (discussão | contribs)
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:
2.1 MODELO MATEMÁTICO DE PROGRAMAÇÃO LINEAR
Usa-se programação matemática para a determinação da solução ótima
de problemas que exigem que se decida sobre a utilização eficaz de uma
quantidade limitada de recursos, para a obtenção de um determinado objetivo. Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
3
A programação linear é uma técnica de programação matemática e,
consiste na otimização (maximização ou minimização) de uma função linear,
denominada de Função Objetivo, respeitando-se um sistema linear de igualdades
ou desigualdades que recebem o nome de Restrições do modelo.
 
<math>5M + 10C \leq 113</math> (Restrição 2)
2.1 MODELO MATEMÁTICO DE PROGRAMAÇÃO LINEAR
Usa-se programação matemática para a determinação da solução ótima
de problemas que exigem que se decida sobre a utilização eficaz de uma
quantidade limitada de recursos, para a obtenção de um determinado objetivo. Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
3
A programação linear é uma técnica de programação matemática e,
consiste na otimização (maximização ou minimização) de uma função linear,
denominada de Função Objetivo, respeitando-se um sistema linear de igualdades
ou desigualdades que recebem o nome de Restrições do modelo.
 
Além disso, sabemos que não podemos fabricar uma quantidade negativa de cadeiras ou mesas:
2.1 MODELO MATEMÁTICO DE PROGRAMAÇÃO LINEAR
Usa-se programação matemática para a determinação da solução ótima
de problemas que exigem que se decida sobre a utilização eficaz de uma
quantidade limitada de recursos, para a obtenção de um determinado objetivo. Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
3
A programação linear é uma técnica de programação matemática e,
consiste na otimização (maximização ou minimização) de uma função linear,
denominada de Função Objetivo, respeitando-se um sistema linear de igualdades
ou desigualdades que recebem o nome de Restrições do modelo.
 
<math>M, C \geq 0</math>
2.1 MODELO MATEMÁTICO DE PROGRAMAÇÃO LINEAR
Usa-se programação matemática para a determinação da solução ótima
de problemas que exigem que se decida sobre a utilização eficaz de uma
quantidade limitada de recursos, para a obtenção de um determinado objetivo. Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
3
A programação linear é uma técnica de programação matemática e,
consiste na otimização (maximização ou minimização) de uma função linear,
denominada de Função Objetivo, respeitando-se um sistema linear de igualdades
ou desigualdades que recebem o nome de Restrições do modelo.
 
Pronto! Terminamos de construir o nosso modelo!
2.1 MODELO MATEMÁTICO DE PROGRAMAÇÃO LINEAR
Usa-se programação matemática para a determinação da solução ótima
de problemas que exigem que se decida sobre a utilização eficaz de uma
quantidade limitada de recursos, para a obtenção de um determinado objetivo. Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
3
A programação linear é uma técnica de programação matemática e,
consiste na otimização (maximização ou minimização) de uma função linear,
denominada de Função Objetivo, respeitando-se um sistema linear de igualdades
ou desigualdades que recebem o nome de Restrições do modelo.
 
==Solução Gráfica==