Trabalho realizado por:
João Pedro Cunha nº12
João Gentil nº11
Introdução
A programação linear é um ramo da matemática que estuda formas de
resolver problemas de optimização cujas condições podem se expressar por
inequações linear, isto é, inequações do 1ºgrau.Um problema de programação
linear que tenha só duas variações pode ser resolvida graficamente,
representado as soluções de cada uma das inequações por um semiplano e
procurando o ponto do polígono obtido que nos da a solução óptica.
São problemas em que se procura a melhor solução (a que dá menor
prejuízo, mais lucro, a que é mais eficiente, etc).
Alguns destes problemas resolvem-se procurando máximos ou mínimos de
uma função, outros processos.
Alguns desses processos fazem parte de uma área da matemática
chamada programação linear.
História da programação linear
É possível encontrar os primeiros passos da optimização em culturas
de povos antigos, citando-se por exemplo, no séc. IX a.C. o conhecido
episódio narrado por Virgílio, segundo o qual, a rainha Dido ao fundar a
cidade de Cartago determinou qual a figura geométrica para a qual seria
maximizada a área por ela delimitada para um dado perímetro constante; ou
ate no séc. VI-V a.C. os pensamentos de Confúcio que traduzem sabiamente
algumas das preocupações mais recentes da teoria da decisão.
No entanto, o desenvolvimento dos métodos de optimização só se
inicia a partir do séc. XVII, como resposta não só a desafios pertinentes
coco também porque os problemas de optimização se revelam essenciais ao
desenvolvimento das ciências experimentais. Um desafio pertinente foi a
disputa travada entre o matemático Huygens e o engenheiro chefe da
marinha de Luís XIV (Chevalier Renau), sobre o mais conveniente ângulo de
navegação para embarcações à vela, supondo conhecida a orientação do
vento, e que veio permitir que Johann Bernoulli “descobrisse” que o
anulamento da primeira derivada de uma função é condição
necessária de máximo e mínimo.
Apesar dos problemas de optimização já há muito
serem estudados estes mereceram pouca atenção até
meados do séc. XX.
Os principais desenvolvimentos teóricos da
programação linear são devidos a Kantorovich (que mais
tarde, em 1975, viria a ganhar o premio Nobel da
economia) e a um grande grupo de cientistas americanos. Já em 1939 este
matemático e economista Soviético tinha formulado e desenvolvido um
problema de programação linear para aplicação em planeamento da produção.
No entanto, o seu trabalho foi desconhecido durante vinte anos não tendo
tido impacto no desenvolvimento da programação linear após a segunda
guerra.
Os primeiros conceitos da programação linear
foram desenvolvidos entre 1947 e 1949 durante a
segunda guerra mundial, por George Dantzig, para
serem aplicados a programas militares desde a área
logística ate a estratégia. Foi após a guerra que ele foi
impulsionado para encontrar formas eficientes de
desenvolver esta metodologia. Foi dantzig o primeiro a
reconhecer que um programa de planeamento poderia
ser expresso por um sistema de inequações lineares
assim como foi o primeiro a apresentar, na forma de uma expressão
matemática explícita, um critério para selecção do melhor plano ao que hoje
chamamos função objectiva.
O pós-guerra foi considerado, pelo matemático Nemhauser, como uma
“Segunda Renascença” já que como nos séc. XV e XVII as ciências
experimentais proporcionaram desafios decisivos à matemática, dando lugar
às ciências organizadas do planeamento e da gestão que mais contribuírem
para o seu sucesso.
-A resolução de 1 problema de programação linear passa pelos
seguintes passos:
1. Cria-se 1 modelo matemático para resolver o problema:
-introduz-se as variáveis
-escreve-se a função objectivo
-escreve-se as restrições às variáveis
2. Representa-se graficamente o sistema de inequações e define-se
a região
3. Calcula-se o valor da função objectivo nos vértices da região e
indica-se a solução óptica.
Problema
Problema 14
Uma fábrica de moagem produz dois tipos de farinha a partir de diferentes misturas de
cereais:
Tipo A: 30% de milho, 65% de trigo e 5% de centeio
Tipo B: 20% de milho, 70% de trigo e 10% de centeio
A esta fábrica chegam todos os dias três camiões, vindos de diferentes fornecedores,
que transportam até ao máximo de 1200 kg de milho, 3800 kg de trigo e 500 kg de
centeio.
Sabendo que o lucro é de 0,50€ por cada quilograma de farinha do tipo A e de 0,70€
por cada quilograma de farinha do tipo B.
Quantos quilogramas de cada tipo de farinha devem ser produzidos por dia de forma
que o lucro obtido seja máximo?
Tabela síntese dos dados
Farinha A
Farinha B
Quantidade Quantidade de Quantidade
em kilos
milho
trigo
χ
0,30 χ
0,65 χ
γ
0,20 γ
0,70 γ
Método analítico
χ : farinha de tipo A que é moída todos os dias
γ:
farinha de tipo B que é moída todos os dias
Função objectivo
L=0,50 χ +0,70 γ
de Quantidade de
centeio
0,05 χ
0,10 γ
Restrições
⎧0,30 χ + 0,20γ ≤ 1200
⎪0,65 χ + 0,70γ ≤ 3800
⎪⎪
⇔
⎨0,05 χ + 0,10γ ≤ 500
⎪χ ≥ 0
⎪
⎪⎩γ ≥ 0
⎧γ ≤ 6000 − 1,5 χ
⎪
⎪γ ≤ 3800 − 0,65χ
0,70
0,70
⎪
⎪
⎨γ ≤ 5000 − 0,5χ
⎪χ ≥ 0
⎪
⎪γ ≥ 0
⎪
⎩
Método gráfico
⎧0,20γ ≤ 1200 − 0,30 χ
⎪0,70γ ≤ 3800 − 0,65 χ
⎪⎪
⎨0,10γ ≤ 500 − 0,05 χ
⎪χ ≥ 0
⎪
⎪⎩γ ≥ 0
⇔
1200 0,30 χ
⎧
⎪γ ≤ 0,20 − 0,20
⎪
3800 0,65χ
⎪
⎪γ ≤ 0,70 − 0,70
⎪
500 0,05χ
⎪
⇔
−
⎨γ ≤
0,10 0,10
⎪
⎪χ ≥ 0
⎪
⎪γ ≥ 0
⎪
⎪
⎩
Calculadora gráfica
Conclusão
χ
γ
L=0,50 χ +0,70 γ
4000
0
2000
0
5000
3500
1000
4500
3650
Bibliografia
-“Geometria Π -Maria Augusta Ferreira Neves
-Maquina gráfica