Pesquisa operacional/Introdução à Programação Linear: diferenças entre revisões

[edição não verificada][edição não verificada]
Conteúdo apagado Conteúdo adicionado
He7d3r.bot (discussão | contribs)
Trocando categorização manual por AutoCat (o indexador da categoria estava incorreto) [ usando AWB ]
He7d3r.bot (discussão | contribs)
Correção de typos e formatação geral, typos fixed: analizar → analisar (2), anti-a → antia utilizando AWB
Linha 27:
O desenvolvimento de técnicas algébricas para se lidar com inequações lineares é algo bastante antigo. Durante o século XVIII, o matemático e físico Jean-Baptiste Joseph Fourier desenvolveu vários métodos inovadores para se resolver sistemas de ineqüações. Um dos principais algoritmos desenvolvido por Fourier foi o Método de Eliminação de Fourier–Motzkin.
 
Durante a Segunda Guerra Mundial, novas tecnologias bélicas levaram à criação de grupos acadêmicos com o objetivo de resolver problemas como o uso eficiente de radares, canhões anti-aéreosantiaéreos, escoltas navais, etc. O objetivo era sempre reduzir custos militares e buscar maximizar as baixas inimigas. Para resolver estes problemas, a Programação Linear mostrou-se extremamente útil. Os grupos acadêmicos que a utilizavam eram sempre mantidos secretos até o ano de 1947, após o término da guerra. Foi quando a Programação Linear passou a ser muito usada em empresas com o objetivo de reduzir despesas e maximizar lucros.
 
Também no ano de 1947, o matemático George Dantzig desenvolveu o '''Algoritmo Simplex''', a maneira mais eficiente conhecida de se resolver modelos de Programação Linear. No mesmo ano, John von Neumann desenvolveu a teoria da dualidade e Leonid Kantorovich foi a primeira pessoa a aplicar a Programação Linear à Economia.
Linha 34:
 
Em 1984, surge mais um método de se resolver problemas de pesquisa operacional: o Algoritmo do Ponto Interior, criado por Narendra Karmarkar. Assim como o Algoritmo Elipsóide, ele era polinomial. A diferença é que ele era bem mais rápido e conseguia competir com o Algoritmo Simplex.
 
 
==A Criação de Modelos==
Linha 70 ⟶ 69:
Máx <math>Z = 6M + 8C</math> (Função-Objetivo)
 
Agora precisamos analizaranalisar 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)
Linha 86 ⟶ 85:
==Solução Gráfica==
 
Muito bem! Já sabemos como criar os modelos de Programação Linear. Mas... Como podemos resolvê-los? Como usar todos aqueles algoritmos comentados na seção sobre a história da Programação Linear? Bem, vamos com calma. Vamos ver primeiro uma das formas mais simples de se resolver este problema (embora não seja computacionalmente eficiente). Vamos fazer um gráfico analizandoanalisando o Domínio da função-objetivo mostrada no exempo acima:
 
[[Imagem:Grafico_programacao_linearGrafico programacao linear.png]]
 
As linhas mais finas representam o eixo X e Y, os quais representam respectivamente o número de mesas (M) e cadeiras (C). Todos os pontos dentro ou abaixo àquela reta grossa mais inclinada verticalmente representam pontos que satisfazem a Restrição 2. Todos os pontos deitro ou abaixo àquela reta grossa inclinada mais horizontalmente satisfazem a Restrição 1. Pontos à direita da reta Y e àcima do eixo X satisfazem a exigência de que não podemos fabricar um número negativo de objetos. Quanto mais restrições um ponto no gráfico acima satisfaz, mais escuro ele aparece. A única região onde todas as restrições são satisfeitas é aquele triângulo escuro localizado próximo ao centro do gráfico. Os vértices do triângulo são os pontos (0,0), (0,10) e (5,0).
Linha 130 ⟶ 129:
O gráfico do Domínio é:
 
[[Imagem:Grafico_programacao_linear2Grafico programacao linear2.png]]
 
O polígono mais escuro que representa os pontos que atendem à todas as restrições possui como vértices os pontos (0,0), (3,0), (3,3) e (1,4). O lucro em (0,0) é 0$. Em (3,0) é 3$. Em (3,3) é 9$. Em (1,4) é 9$. Neste exemplo, não existe apenas um único ponto que representa o máximo da função - existem infinitos pontos. Todos aqueles que pertencem ao Domínio e estão na reta que liga (3,3) e (1,4) são o máximo da função e representam a quantidade ideal de produção de pastéis e cachorros-quentes para o vendedor ambulante. Como o vendedor ambulante não pode fazer um número fracionário de pastéis e cachorros, quentes, a resposta é: 3 pastéis e 3 cachorros-quentes ou então 1 pastel e 4 cachorros-quente.
 
 
----
 
 
'''2.''' Temos que resolver o modelo:
Linha 149 ⟶ 146:
 
Perceba que não é possível resolver este modelo. Não existe nenhuma informação que limite superiormente o número de bombardeiros que temos disponíveis. Logo, podemos simplesmente dizer que o melhor é atacar com infinitos bombardeiros. Isso é um absurdo. É uma solução inconcebível. Modelos com solução infinita costumam ocorrer quando algum tipo de restrição é omitida do modelo.
 
 
----
 
 
'''3.''' Isso acrescenta uma nova restrição ao modelo:
Linha 159 ⟶ 154:
 
Agora sim podemos resolver o modelo. Tente desenhar o gráfico do Domínio desta função-objetivo. Ele gera um triângulo com três vértices. A resposta é que devemos enviar 4 tanques e 5 bombardeiros para que causemos em média 330 baixas no inimigo.
 
 
 
<!-- CATGORIAS -->