Faculdade de Ciência e Tecnologia da Universidade de Coimbra Departamento de Matemática Programação Linear 2002/2003



Baixar 204.3 Kb.
Página1/3
Encontro19.07.2016
Tamanho204.3 Kb.
  1   2   3

Fundamentos e Ensino da Álgebra Programação linear


Faculdade de Ciência e Tecnologia da Universidade de Coimbra

Departamento de Matemática

Programação Linear

2002/2003

Trabalho realizado no âmbito da cadeira de Fundamentos e Ensino da Álgebra por:


Carla Sofia Monteiro Freitas Henriques

Dina Jacinta Nunes Lopes

Márcio Nuno Loureiro Jesus

Sónia Patrícia Gomes dos Santos

ÍNDICE
1. Introdução à Programação Linear .................................................................................4

1.1 Origens e evolução...................................................................................................4

1.2 Introdução e primeiros conceitos..............................................................................5

1.3 O que é a Programação Linear ?...............................................................................6

1.4 Onde se aplica a Programação Linear ?....................................................................7

1.5 Conceitos fundamentais da Programação Linear ....................................................8

2. Formulação de problemas de Programação Linear.....................................................10

2.1 O modelo................................................................................................................10

2.2 Hipóteses do modelo de Programação Linear........................................................12

2.3 Formulação dos vários tipos de problemas de Programação Linear......................13

2.4 Representação gráfica de problemas de programação linear..................................14

2.4.1 Soluções de um problema de P.L...................................................................14

2.5 Introdução aos exemplos a estudar.........................................................................15

2.5.1 Exemplo de maximização...............................................................................15

A) Formulação matemática do problema.................................................17

B) Representação gráfica do problema....................................................17

2.5.2 Exemplo de minimização....... .......................................................................19

A) Formulação matemática do problema.................................................19

  1. Representação gráfica do problema...................................................20

2.5.3 Casos particulares...........................................................................................21

3. O Método Simplex.......................................................................................................25

3.1 Introdução...............................................................................................................25

3.2 Alguns conceitos fundamentais no Método Simplex.............................................25

3.3 Algoritmo do Método Simplex...............................................................................27

3.4 Exemplos de aplicação do Método Simplex...........................................................29

4. Conclusão....................................................................................................................35

Bibliografia



1. INTRODUÇÃO À PROGRAMAÇÃO LINEAR


    1. ORIGENS E EVOLUÇÃO

Desde a revolução industrial o mundo tem presenciado um grande crescimento no tamanho e complexidade das organizações e empreendimentos. Por outro lado, é cada vez mais difícil fazer a atribuição dos recursos disponíveis às diferentes actividades (envolvidas nessas organizações e empreendimentos) e tomar decisões de âmbito mais geral.

Este tipo de problemas e a necessidade de se encontrar um meio adequado para os resolver criaram o ambiente que viria a proporcionar o aparecimento da Investigação Operacional (I.O.).

As origens da I.O. podem ser encontradas há muitas décadas, sendo o início da actividade com esta designação atribuída aos Serviços Militares Aliados durante a 2ª Guerra Mundial. Contudo, é difícil definir I.O. de forma não controversa, sendo no entanto possível extrair da maior parte das definições as seguintes características básicas:



  • a aplicação de métodos científicos na gestão das organizações, mediante uma abordagem quantitativa e qualitativa na tomada de decisões;

  • orientação sistemática, através da qual o problema é analisado no contexto dum sistema que inclui diversas componentes interrelacionadas entre si; as soluções devem satisfazer toda a organização, ou seja, o sistema completo;

  • extensibilidade, que pode ser aplicada a um largo número de organizações, tais como: negócios, economia, indústria, indústria militar, governos, agências, hospitais, etc.

Os ramos mais importantes da I.O. são: Programação Matemática (P.M.), Análise Estatística, Teoria dos Jogos, Teoria das Filas, Simulação, Gestão de Stocks, etc.. A P.M. divide-se ainda em: Programação Linear (P.L.), Programação Não Linear, Programação Dinâmica, Programação Inteira e Optimização Global.

Neste contexto, a P.L. tem por objecto de estudo a actividade humana dirigida, na qual se pretende satisfazer da melhor forma determinado objectivo, em que existem limitações (restrições) ao funcionamento dessa actividade. Está-se na presença de um problema de P.M. quando o objectivo das restrições podem ser traduzidas por relações funcionais. Se estas forem lineares constituem um problema de P.L..

Neste trabalho, procede-se à apresentação de uma subclasse especial de problemas de P.M. designada por P.L.. Esta designação advém do facto de que, quer as condições, quer o objectivo deste tipo de problemas, poderem ser descritos através de relações lineares, nomeadamente equações e inequações lineares.


1.2 INTRODUÇÃO E PRIMEIROS CONCEITOS
À semelhança de outros ramos da Matemática, a P.L. teve a sua origem em aplicações. Dois mil anos antes de Cristo, exemplos especiais de equações lineares já tinham sido estudados por egípcios e babilónios (estes últimos já consideravam duas equações lineares em duas variáveis). Babilónios, gregos e chineses conheciam a ideia de eliminação de variáveis para resolver equações lineares (ou quadráticas).

Ao longo dos tempos, cientistas tais como Euclides, Newton e Lagrange fizeram a incursão à pesquisa do “óptimo”. Já no século passado destacamos as investigações feitas por Von Neumann na Teoria de Jogos, Wassily Leontief no Modelo “input-output” de Economia, entre outros. Até aos anos 30-40 do século passado foi muito reduzido o interesse dos matemáticos pelo estudo de sistemas de inequações, ao contrário do que se verificou com a resolução de sistemas de equações, descurando-se assim a procura de uma solução “óptima”. As aplicações em problemas de transporte na década de 40 (em particular, pelas Forças Armadas durante a 2ª Guerra Mundial) foi um primeiro passo na criação da P.L..

Entre os pioneiros que fizeram o desenvolvimento da área estão Leonid V. Kantorovich em Lenigrado (actualmente, S. Petersburg) e George B. Dantzig em Washington. Ambos ilustraram muito bem as fontes de aplicação da P.L..

Em 1939, o matemático e economista soviético L.V. Kantorovich formulou e resolveu problemas ligados à optimização na administração das organizações, mas o seu trabalho manteve-se desconhecido até 1959.

George Dantzig trabalhava como civil, no Pentágono, onde exercia funções de conselheiro matemático para a administração da Força Aérea Norte Americana, trabalhando no projecto SCOOP (Scientific Computation of Optimum Programs). Por inerência do respectivo serviço, Dantzig era frequentemente chamado para resolver problemas de planeamento que envolviam a distribuição de pessoal, dinheiros, aviões e outros recursos de custo efectivo. Foi no Pentágono que Dantzig recebeu dos seus colegas D. Hitchcock e M. Wood o desafio de tentar mecanizar o processo de planeamento. Como a maioria dos problemas diziam respeito a questões de Economia, de uma ou de outra forma, Dantzig procurou aconselhar-se com o economista Tjalling Koopmans para os resolver (admitindo que os economistas tivessem já desenvolvido técnicas de resolução). Porém, com grande surpresa sua, Koopmans confessou-lhe que os economistas também não tinham quaisquer procedimentos para encontrarem sistematicamente a solução de tais problemas.

No Verão de 1947, Dantzig propôs o Método Simplex que tornou possível a solução de problemas de optimização de vários tipos : transporte, produção, alocação de recursos e problemas de escalonamento. Um ano mais tarde, Dantzig e Koopmans encontraram-se na praia de Santa Monica e Koopmans disse : «”Why not shorten “Programming in a Linear Structure” to “Linear Programming”?”» ao que Dantzig respondeu : «”That’s it! From now on that will be its name.”». Nasceu assim a designação de Programação Linear.

Com a apresentação do Método Simplex a P.M., e em particular a P.L., teve um grande impulso. Foi a partir de então que as suas aplicações não cessaram, envolvendo valiosas contribuições de economistas e matemáticos. O desenvolvimento da Informática é outro dos factores que tem contribuído para a evolução acelerada desta ciência nas últimas décadas.
1.3 O QUE É A PROGRAMAÇÃO LINEAR ?
Programação  planeamento de actividades
Linear  o problema é representado matematicamente pelo modelo da P.M., onde todas as funções f(x1, ..., xn) (função objectivo), gi(x1, ..., xn) (restrições) são lineares e x1, ..., xn são as variáveis de decisão, com i = 1, ..., m
A P.L. é uma técnica de planeamento que se tem vindo a constituir como uma das mais poderosas em quase todo o ramo da actividade humana. É um método de maximizar (ou minimizar) uma função linear (designada função objectivo), definida num dado conjunto convexo, tendo em conta que as variáveis estão sujeitas a restrições lineares. Estas restrições podem ser do tipo , = ou  e as variáveis são reais não negativas.
1.4 ONDE SE APLICA A PROGRAMAÇÃO LINEAR ?
Uma vez que os problemas de P.L. determinam o planeamento óptimo de actividades, ou seja, um plano óptimo que representa a melhor solução entre todas as soluções possíveis, as suas principais áreas de aplicação são:


  • Económica e especialmente Economia de Empresas, onde se situam as aplicações mais férteis e os estímulos mais fortes para os desenvolvimentos teóricos da P.L.;

  • Matemática, onde a P.L. tem impulsionado a obtenção de importantes resultados teóricos e o aperfeiçoamento das técnicas de Análise Numérica;

  • Militar, onde as aplicações são numerosas mas normalmente pouco divulgadas por razões de segurança.

Nestes domínios, podemos dividir os problemas de P.L. em três tipos:




  1. Problemas de Transporte

Consideremos uma aplicação clássica deste tipo de problema: suponha que um sistema de distribuição alimenta N armazéns a partir de M grandes unidades produtoras; conhecendo os custos de transporte, a procura prevista para cada armazém e as capacidades (máximas) de produção de cada unidade, determinar o programa de distribuição com menor custo.

Outras aplicações: - rentabilização de aeroportos;

- optimização de tráfego interno ou de comunicação de

vários tipos;

- planificação dos semáforos de circulação numa cidade.



  1. Problemas de Composição

Neste tipo de problema destaca-se o seguinte exemplo genérico: conhecendo os conteúdos calóricos e vitamínicos de diversos alimentos, bem como os seus preços, pretende-se optimizar a composição da dieta a adoptar, de modo a minimizar o seu custo e a satisfazer níveis mínimos de calorias e vitaminas.

Outras aplicações: - composição de medicamentos;

- blindagem de ligas metálicas e combustíveis;

- rações de animais e adubos;

- gelados e produtos alimentares.




  1. Problemas de Formação e Produção

Salienta-se a seguinte aplicação: suponha que uma fábrica é capaz de produzir N produtos distintos utilizando M recursos limitados, os quais podem ser horas de trabalho ou tempos de operação de várias máquinas, matérias primas, serviços, etc.; conhecendo-se o lucro unitário e as quantidades de recurso utilizadas para cada produto, e as quantidades de recursos disponíveis, determinar o plano óptimo de produção com maior lucro.

Outras aplicações: - corte de barras e chapas;

- designação de pessoas e tarefas (composição de tabelas

de horários);

- planeamento da produção de uma empresa têxtil.



1.5 CONCEITOS FUNDAMENTAIS DA PROGRAMAÇÃO LINEAR
Para uma melhor compreensão de um problema de P.L. enunciamos de seguida alguns conceitos e expressões que vão ser usados ao longo do trabalho:


  • Função objectivo (função económica ou função critério) – é uma função linear que vamos optimizar, maximizando ou minimizando;




  • Variáveis de decisão – são os valores de um número n de decisões a serem tomadas e designam-se por x1, ..., xn e que estão interrelacionadas pela função objectivo;




  • Variáveis de folga – são as variáveis que usamos para transformar as inequações em equações; de salientar que cada variável de folga está associada a uma restrição;




  • Restrições – são condições (representadas por equações ou inequações lineares) que se impõem ao modelo dado; existem dois tipos de restrições:

  • Restrições do problema – são restrições do tipo  , = ou  , que relacionam uma ou mais variáveis do problema;

  • Restrições de não negatividade – são desigualdades do tipo x1  0, ..., xn  0, em que x1, ..., xn são as variáveis de decisão;




  • Forma padrão (standard) – quando as restrições de um problema de P.L. são apresentadas na forma de equações;




  • Forma canónica – quando as restrições de um problema de P.L. são apresentadas na forma de inequações;




  • Solução – é qualquer conjunto de valores para as variáveis x1, ..., xn que satisfaça as restrições;




  • Solução admissível (solução possível) – é qualquer especificação de valores para as variáveis x1, ..., xn que satisfaça as restrições do problema e as condições de não negatividade;




  • Solução ilimitada (unbounded) – é aquela em que a função objectivo pode crescer (no caso da maximização) ou decrescer (no caso da minimização), indefinidamente, tendo em conta todas as restrições do problema;

  • Solução óptima – é aquela que maximiza ou minimiza a função objectivo sobre toda a região admissível;




  • Região admissível – é o conjunto de todas as soluções admissíveis.

  1. FORMULAÇÃO DE PROBLEMAS DE PROGRAMAÇÃO LINEAR


2.1 O MODELO
Os problemas de Programação Linear são problemas de maximização ou de minimização de funções lineares (função objectivo), num determinado domínio, normalmente definido por um conjunto de restrições nas variáveis. Estes problemas são representados matematicamente por modelos que podem ser apresentados na forma padrão ou na forma canónica (já definidas anteriormente).

Algebricamente tem-se:


max (min) Z = c1x1 ++ cnxn
sujeito a
a11x1 + a12x2 + … + a1jxj + … + a1nxn {  , = ,  } b1
a21x1 + a22x2 + … + a2jxj + … + a2nxn {  , = ,  } b2

...


ai1x1 + ai2x2 + … + ainxn + … + ainxn {  , = ,  } bi

...


am1x1 + am2x2 + … + amjxj + … + amnxn {  , = ,  } bm
com :

x1  0 , x2  0 , ... , xn  0

i = 1 , ... , m

j = 1 , ... , n


xj – incógnitas, são as variáveis de decisão

aij – coeficientes

bitermos independentes

cj – coeficientes da função objectivo

É também frequente o modelo de Programação Linear ser apresentado utilizando as notações cartesiana, matricial e vectorial.

As duas formas apresentadas (padrão e canónica) são equivalentes. Com efeito, mediante as operações a seguir indicadas, é sempre possível dar a qualquer problema uma destas formas, sem que o conjunto de soluções se altere.


1. Qualquer problema de maximização pode converter-se num problema de minimização, pois:

máximo Z = - mínimo (- Z)


2. Qualquer restrição de desigualdade do tipo “  ” pode ser convertida numa restrição do tipo “  ” multiplicando por (-1) ambos os seus membros :
ai1x1 + ai2x2 + ... + ainxn  bi  - ai1x1 - ai2x2 - ... - ainxn  - bi
3. Qualquer restrição de igualdade pode ser convertida em duas restrições de desigualdades “  ” equivalentes àquela :


ai1x1 + ... + ainxn  bi

ai1x1 + ... + ainxn  bi

ai1x1 + ... + ainxn  bi

ai1x1 + ... + ainxn  - bi

a




i1x1 + ... + ainxn = bi    


4. Qualquer restrição de desigualdade pode ser convertida numa restrição de igualdade, através da introdução duma nova variável (variável de folga) xn+1, de valor não negativo:

ai1x1 + ... + ainxn  bi  bi - ai1x1 - ... - ainxn  0 

 xn+1 = bi - ai1x1 - ... - ainxn  0
acrescentando-se a variável de folga xn+1, obtém-se :
ai1x1 + ... + ainxn + xn+1 = bi com xn+1  0

5. Qualquer variável livre (não restringida pela condição de não negatividade) xj, pode ser substituída por um par de variáveis não negativas xj’  0 e xj’’  0, fazendo xj = xj’ - xj’’ formulando, deste modo, de novo o problema em função destas duas novas variáveis.
2.2 HIPÓTESES DO MODELO DE PROGRAMAÇÃO LINEAR
Qualquer modelo de P.L. deve cumprir as seguintes hipóteses que garantam a linearidade da função objectivo e das restrições do problema. Estas hipóteses são :
PROPORCIONALIDADE : em cada actividade a quantidade de bens que entram e saem são sempre proporcionais ao nível da mesma, estando assim na presença de um modelo linear;
ADITIVIDADE : o resultado do emprego conjunto de N actividades é a sua adição;
DIVISIBILIDADE E NÃO NEGATIVIDADE : o nível de uma actividade pode assumir qualquer valor positivo de um dado intervalo, que equivale a supor que os bens são perfeitamente divisíveis, isto é, susceptíveis de variar em quantidades infinitesimais;
LINEARIDADE DA FUNÇÃO OBJECTIVO : cada actividade contribui para o objectivo global perseguido pelo sistema ( por exemplo, cada actividade normalmente tem associado um certo lucro ou um certo custo ). Esta hipótese indica que essa contribuição para a função económica é proporcional ao nível de actividade. A contribuição total é a soma das contribuições de todas as actividades.

2.3 FORMULAÇÃO DOS VÁRIOS TIPOS DE PROBLEMAS DE PROGRAMAÇÃO LINEAR
Formulação:

  1   2   3


©principo.org 2016
enviar mensagem

    Página principal