Índice - Departamento de Matemática

Índice

pág.

Introdução 2

Nota histórica 3

Programação linear 5

Programação linear com duas variáveis 7

Problemas 9

Problema de maximização 9

Problema de minimização 15

Casos particulares 18

Método Simplex 22

Algoritmo do Simplex 23

Problema (Método Simplex) 26

Bibliografia 31

Fundamentos e Ensino da Álgebra – Programação Linear

2

Introdução

Neste trabalho trataremos um conteúdo que irá ser leccionado num futuro

próximo, que se denomina de “Programação Linear”.

Mas o que é a programação linear?

A programação linear consiste em optimizar (maximizar ou minimizar) uma

dada função linear, que se chama função objectivo, definida num dado conjunto

convexo, tendo em conta que as variáveis estão sujeitas a restrições.

Tentaremos dar uma ideia aos futuros professores de Matemática, sobre o que

futuramente irá leccionar. Para isso, a primeira parte deste trabalho trata apenas a

programação linear ao nível do ensino secundário (no 11º ano). Nesta parte

elaboraremos dois exemplos para uma melhor compreensão deste item. Posteriormente,

trabalharemos um pouco o “Método Simplex”, este conteúdo não é dado no ensino

secundário, pois é muito complexo e normalmente só é estudado na Matemática

Aplicada ou Computacional. Este método é muito importante, pois permite resolver

problemas com muitas variáveis.

Programação linear é muito importante para resolver problemas do dia a dia que

se possam exprimir por meio de uma função linear.

Esperamos portanto, que este trabalho ajude os estudantes de matemática,

futuros professores, a compreender ou ter uma ideia de um conteúdo que irá ensinar.


3

Nota histórica

Historicamente, tal como acontece com outros ramos científicos recentes, a

programação linear encontra as suas raízes na Antiguidade Clássica, ou talvez mesmo

na Antiguidade Oriental, já que a pesquisa do óptimo é um tema que sempre preocupou

o Homem. Assim, por exemplo, já Euclides (séc. III A.C.) no seu Livro III procurava

encontrar a maior e menor distâncias de um ponto para a circunferência e no seu Livro

IV descreveu uma forma de obter um paralelogramo de área máxima com um dado

perímetro.

Nos séculos XVII e XVIII desenvolveram-se métodos de cálculo que permitiram

resolver os problemas postos por Euclides e também as soluções óptimas de uma grande

variedade de problemas de optimização. São bem conhecidos os problemas de extremos

condicionados com restrições de igualdade e os contributos dados por Newton, Leibniz,

Lagrange e Bernoulli. Nestes primeiros tempos os problemas que preocuparam os

homens da ciência eram basicamente relacionados com a Geometria, a Dinâmica e a

Física.

Cournot com o seu estudo sobre a igualdade entre receita marginal e custo

marginal, logo implicitamente a determinação do ponto de equilíbrio que origina o lucro

máximo, pode considerar-se um dos percursores da programação matemática.

Em 1957 Quesnay publica o Tableau Economique que pode considerar-se a

primeira grande tentativa de modelizar a economia – é assim o primeiro marco no

caminho dos modelos de programação ao nível macroeconómico.

O Sistema de Equilíbrio Geral de Walras, publicado em 1874, representa, em

termos teóricos, um considerável avanço na procura da melhor forma de interpretar a

economia como um todo.

Na sequência dos trabalhos realizados sob a égide do governo dos EUA,

Leontief apresenta em 1936 o modelo «input-output» para a economia americana. Este

trabalho é sem dúvida o segundo marco.

Em 1937 Von Neumann publica A Model of General Economic Equilibrium

onde formula um modelo de programação linear dinâmica, em que admite métodos

alternativos de produção simples ou conjunta.


4

Em 19939 Kantorovich formulou de forma rigorosa um problema de

programação linear no trabalho Métodos Matemáticos de Organização e Planeamento

da Produção, mas não apresentou um algoritmo de resolução. Todavia, este trabalho

não teve então o reconhecimento que merece e só muitos anos mais tarde foi

efectivamente apreciado.

Mas é ligado à problemática militar, e em especial da logística em tempo de

guerra, que o grande salto se vai dar.

Georges Dantzig e outros, trabalhando no Projecto SCOOP (Scientific

Computation of Optimum Programs) no Departamento da Força Aérea Americana,

apresentaram em 1947 uma forma sistemática de resolução dos problemas de

programação linear que se designa por Método do Simplex e que se revelou duma

eficácia extraordinária.

A partir desta data pode afirmar-se que a programação linear é uma realidade.

Com a apresentação do método do simplex, a programação matemática em geral

vai sofrer um surto expansionista quase inacreditável.


5

Programação linear

Os problemas de optimização são problemas de extremos de funções de

variáveis (ou de funções) sobre um certo domínio normalmente definido por um

conjunto de restrições às variáveis (ou às funções).

Alguns destes problemas tiveram origem na Física e na Geometria, tendo sido

tratados na análise matemática clássica, nomeadamente no Cálculo Diferencial e no

Cálculo das Variações, a partir do século XVII. Muitos destes resultados foram

posteriormente aplicados com sucesso à Engenharia e à Teoria Económica, em

particular à Teoria da Produção e do Consumidor.

Na década de quarenta assiste-se ao surgimento duma classe particular de

problemas de optimização nos campos da organização e gestão económica. Esta classe

de problemas é designada por Programação Matemática e abrange a análise e estudo de

sistemas de forma a determinar o programa de acção mais adequado à prossecução de

certo objectivo, tendo em conta as restrições que limitam os seus comportamentos.

Matematicamente, o problema de Programação Matemática consiste em

determinar os valores de n variáveis, x1, x2, …, xn, que tornam máximo ou mínimo o

valor de uma função

f (x1, x2, …, xn)

dadas m restrições ou condições,

gi (x1, x2, …, xn) ≤ bi (i = 1, 2, …, m),

e estando as variáveis sujeitas às condições de não negatividade,

xj ≥ 0 (j = 1, 2, …, n).


6

Caso particular de grande importância é o da Programação Linear, em que as

funções f (x1, x2, …, xn) e gi (x1, x2, …, xn), (i = 1, 2, …, m), são lineares. Trata-se da

subclasse de problemas de Optimização mais largamente utilizados nos últimos trinta

anos em áreas tão diversas como a Física, Engenharia, Economia e sobretudo a

Economia da Empresa.

Os problemas que resolve são muito variados. Por exemplo:

• Distribuição de pessoal, com diversas aplicações, postos de trabalho, de

modo a obter o melhor rendimento.

• Planos de produção e armazenamento.

• Obtenção de misturas óptimas, por exemplo, para rações de animais.

• Composição de medicamentos.

• Rentabilização de aeroportos.

• Optimização do tráfego interno ou de comunicação de vários tipos.

• Planificação dos semáforos de circulação numa cidade.

• Programação de rádio ou televisão.

• Estratégias militares, etc.


7

Programação linear com duas variáveis

Ao nível do Ensino Secundário apenas é ensinado aos alunos programação linear

na sua forma mais simples, utilizando somente duas variáveis.

Por este motivo, iniciamos o nosso trabalho abordando essa versão.

Para uma melhor abordagem, recordemos que:

a) Uma expressão como ax+by define uma função linear a duas variáveis

também chamada «forma linear».

b) Igualando-a a uma constante obtemos a equação duma recta; se a constante

for zero, temos uma recta que passa na origem:

ax + by = 0 � y = - (a/b)x

cujo gráfico será

Em qualquer ponto P (x, y) desta recta, a expressão ax + by toma o valor 0.

Diz-se «recta de nível 0» da forma ax + by.

c) Igualando a expressão ax + by a uma constante diferente de 0, obtemos outra

recta que não passa na origem, mas é paralela à anterior visto que tem o

mesmo declive:

ax + by = c � by = -ax + c � y = - (a/b) + (c/b)

(c/b) = k (constante)

P (x, y)


8

Para uma melhor visualização de tal facto, concretizemos os valores a e b (a = 3,

b = 1) e fazendo variar o k obtém-se o gráfico seguinte:

A recta de equação 3x + y = k diz-se recta de nível k da forma linear 3x + y e em

qualquer dos seus pontos a expressão 3x + y toma o valor k.

Nota:

• As restrições do problema originam um polígono – polígono de soluções.

• Num problema de maximização:

- procura-se a recta de maior nível que toque pelo menos num ponto do

polígono de soluções.

• Num problema de minimização:

- procura-se a recta de menor nível que toque pelo menos num ponto

do polígono de soluções.


9

PROBLEMAS

PROBLEMA DE MAXIMIZAÇÃO

Uma empresa de telecomunicações pretende lançar no mercado uma rede móvel.

Precisa, para o efeito de definir o tarifário das suas chamadas. A tarifação será efectuada

ao minuto e as chamadas vão ser cobradas de acordo com o seu destino, havendo uma

tarifa para as chamadas efectuadas para a mesma rede e outra para as chamadas

efectuadas para as outras redes.

O instituto responsável pelas comunicações definiu que a soma do preço de um

minuto de chamada para a mesma rede com o preço de um minuto de chamada para

outra rede não pode ser superior a 0,40 €.

Estudos efectuados em operadoras já existentes mostram que em média cada

cliente fala para a mesma rede 100 minutos por mês, e para as outras redes 30 minutos

por mês.

Cada cliente terá que efectuar um pagamento de 15 € mensais, sendo esse o

saldo disponível para efectuar as chamadas, podendo no entanto pagar um valor mais

elevado no caso de querer dispor de um saldo maior.

Sobre tarifa cobrada a empresa obtém 70% de lucro nas chamadas efectuadas

para a mesma rede e 40% nas chamadas efectuadas para as outras redes.

Como deverá a empresa cobrar as tarifas de forma a obter o maior lucro

possível?


10

Resolução do problema:

Tabela referente aos dados do problema

Tarifa das

chamadas por

minuto

Média mensal dos

minutos de

conversação

Percentagem de

lucro ( % )

Mesma rede x 100 70

Outras redes y 30 40

A função linear a maximizar é o preço total por minuto das chamadas em euros:

0,7x + 0,4y

Restrições:

Tem que se definir os preços para as duas tarifas: x ≥ 0 e y ≥ 0

A soma por minuto das duas tarifas tem que ser inferior a 0,40€: x + y ≤ 0,40

O dinheiro gasto por mês não pode exceder 15€: 100x + 30y ≤ 15


11

Gráfico da região admissível

Qualquer ponto da região a verde satisfaz as várias restrições, logo é uma solução

possível.

• (0,07 ; 0,20) é uma solução para a qual o lucro seria

0,7 ×0,07 + 0,4 × 0,20 = 0,129€ por minuto

• (0,09 ; 0,18) é mais lucrativo, visto que

0,7 × 0,09 + 0,4 × 0,18 = 0,135€ por minuto.

Qual é então o ponto que dá maior lucro?

Para o calcular, representa-se a recta de nível 0 da função objectivo, que é o “

lucro” a maximizar, isto é,

0,7 x + 0,4 y = 0 <=> y = - 1,75 x.


12

Gráfico da recta de nível zero

Procura-se a recta de maior nível (isto é, a paralela mais para a direita) que toque

pelo menos num ponto da região admissível.


13

Gráfico das rectas de nível k

Gráfico da solução óptima


14

Vemos que a solução óptima corresponde ao ponto de intersecção de duas rectas,

o qual se obtém resolvendo o sistema:

x + y = 0,40 x = 0,043

100x + 30y = 15 y = 0,357

Para esta solução o lucro será de 0,7 × 0,043 + 0,4 × 0,357 = 0,173€

�


15

Problema de Minimização

Uma empresa de refrigerantes pretende produzir um novo sumo. Esse novo

sumo será uma mistura de sumo de laranja, sumo de maracujá e água. Cada litro de

sumo de laranja contém um grama de carbonatos, três gramas de proteínas e três gramas

de vitaminas; cada litro de sumo de maracujá contém três gramas de carbonatos, uma de

proteínas e quatro de vitaminas. O preço por litro de sumo de laranja é 1€ e de sumo de

maracujá é 0,75€ (o preço da água é desprezável).

Cada litro do novo sumo deverá conter a quantidade mínima de uma grama e

meia de carbonatos, uma e meia de proteínas e três de vitaminas.

Qual a forma mais económica da empresa misturar os dois sumos, garantindo os

mínimos exigidos?

Resolução do problema:


Tipo de

sumo

Quantidade

de sumo

(litros)

Carbonatos Vitaminas Proteínas Preço/ litro

( €)

Laranja x 1 3 3 1,00

Maracujá y 3 4 1 0,75

A função linear a minimizar é a despesa de fabrico do sumo:

x + 0,75 y


16

Restrições:

Carbonatos: x+3y ≥ 1,5

Vitaminas : 3x+4y ≥ 3

Proteínas: 3x+y ≥ 1,5

Para usar laranja e maracujá: x ≥ 0 e y ≥ 0

Gráfico da região admissível e recta de nível zero


17

Gráfico da solução óptima

Vemos que a solução óptima corresponde ao ponto de intersecção de duas rectas,

o qual se obtém resolvendo o sistema:

Para esta solução a despesa por litro de sumo é de:

0,33 + 0,75 × 0,5 = 0,71€

3x + y = 1,5

3x + 4y = 3

�

x = 0,33

y = 0,5


18

Casos particulares

1º Caso: Solução não limitada

Maximizar z = 2x + 3y

Sujeito a 2x + 2y ≥ 6

- x + y ≤ 1

y ≤ 3

x, y ≥ 0


19

2º Caso: Solução óptima com conjunto das soluções admissíveis não

limitado

Maximizar z = -x + 3y

Sujeito a 2x + 2y ≥ 6

- x + y ≤ 1

y ≤ 3

x, y ≥ 0


20

3º Caso: valor óptimo da FO finito com variáveis podendo

assumir valores arbitrariamente grandes

Maximizar z = -2x + 4y

Sujeito a x - 2y ≥ -4

- x + y ≤ 1

x, y ≥ 0


21

4º Caso: problema impossível

Maximizar z = x + 2y

Sujeito a x + y ≥ 3

2 x + y ≤ 2

x, y ≥ 0


22

Método Simplex

Não se dispondo de uma fórmula resolvente para os problemas, sendo

impraticável a análise exaustiva de todas as soluções básicas admissíveis e sabendo que

as técnicas mais eficientes de resolução de sistemas de equações lineares são iterativas,

é natural que o processo de resolução mais generalizado seja um método iterativo que

procura examinar o menor número de soluções básicas admissíveis. Este procedimento

sistemático, designado por método do simplex, devido a Dantzig (utilizou a equação ∑

xi = 1 como restrição numa interpretação geométrica do método), permite resolver este

tipo de problemas.

O Método Simplex é um processo algébrico que permite resolver problemas de

programação linear, isto é, determina uma solução óptima finita quando esta existe ou

conclui que o problema de optimização é impossível ou ilimitado. Caso a solução

óptima exista, o Método Simplex localiza-a após pesquisar um número finito de

soluções. O Método Simplex é um algoritmo iterativo que começa com uma solução

básica (isto é, um ponto extremo) admissível de partida, movimentando-se

sucessivamente através de uma sucessão de soluções básicas admissíveis, tal que cada

nova solução melhora o valor da função objectivo. Quando o problema tem todas as

restrições do tipo ( ≤ ) (com o termo independente não negativo) a solução básica

admissível (SBA) de partida é o ponto 0 (a origem dos eixos). Se não for este o caso,

então, na maior parte dos problemas, é necessário começar por determinar a SBA de

partida. Utilizam-se para isso duas variantes do Método Simplex: o método do M e o

método das duas fases. Iremos considerar apenas o caso em que o problema tem todas

as restrições do tipo ( ≤ ) (com o termo independente não negativo). Neste caso o

problema possui uma matriz identidade de dimensão igual ao número de restrições,

inscrita nas restrições técnicas. Isto permite determinar facilmente a primeira SBA: as

variáveis básicas são aquelas que correspondem às colunas do quadro que constituem a

matriz identidade.


23

Algoritmo do Simplex

1. Forma padrão

O problema é escrito na forma padrão. As características desta forma são

as seguintes:

• As variáveis são todas não negativas;

• Todas as restrições são equações lineares, com excepção das que

dizem respeito à não negatividade das variáveis;

• Os termos independentes de cada uma das restrições

propriamente ditas são constantes reais não negativas;

• Pode considerar-se, indiferentemente, a maximização ou a

minimização.

Temos então o problema escrito na forma padrão:

(Pressupondo que o problema é a maximizar)

max z = c1 x1 + c2 x2 + … + cn xn

a11 x1 + a12 x2 + ... +a1n xn + xn+1 = b1

a21 x1 + a22 x2 + ... + a2n xn + xn+2 = b2

am1 x1 + am2 x2 + ... +amn xn + xn+m = bm

xj ≥ 0; j = 1, 2, ..., n+m

onde xn+1, ..., xn+m representam as variáveis de folga ou “slack”

adicionada na conversão das restrições do tipo ( ≤ ) para o tipo ( = ).

2. Quadro Simplex

Na primeira solução básica admissível, as variáveis básicas são as de

folga e todas as outras são não básicas. Isto é: X1 = X2 = … = Xn = 0 (pois

são não básicas). Do que resulta que Xn+1 = b1, Xn+2 = b2, …, Xn+m = bm,

constrói-se agora o quadro simplex associado a esta primeira solução:


24

Quadro Simplex

X1 Xm Xn Xn+1 Xn+m b

Xn+1 a11 a1i a1n 1 0 b1

… … … … … … …

Xn+m am1 ami amn 0 1 bm

z -c1 -cm -cn 0 0 0

Em qualquer quadro simplex, e em particular neste, que representa a

primeira solução básica admissível, a primeira coluna designa o vector das

variáveis básicas cujos valores figuram na última coluna do quadro ( b ); a

última linha do quadro ( Z ) é designada por linha dos custos reduzidos e é

constituída pelo simétrico do valor dos coeficientes das variáveis da função

objectivo.

3. Condição de optimalidade

Se num problema a maximizar, todos os custos reduzidos (-cj) são não

negativos ( ≥ 0) então a solução que o quadro representa é óptima e o quadro

designa-se por quadro óptimo. Se o problema for a minimizar, a solução é

óptima quando todos os custos reduzidos são não positivos ( ≤ 0).

4. Determinação da variável a entrar na base

Caso não se verifique a condição de optimalidade, modifica-se a base

actual procurando uma outra, cuja solução associada esteja mais próxima da

solução óptima. A base modifica-se substituindo uma variável básica por

outra que o não seja. Assim inicia-se o processo seleccionando entre as

variáveis não básica, aquela cujo valor (-cj) é o menor (repare-se que este

valor é negativo, pois o problema é a maximizar). Se problema for a

minimizar a variável escolhida corresponde ao maior valor de (-cj). Em caso

de “empate” escolhe-se a variável de menor índice.

Xk : (-ck) = min {-cj: -cj <0}.


25

5. Determinação da variável da saída da base

Para determinar a variável que sai da base é necessário ter em conta a

condição de admissibilidade que nos indica que para uma solução ser

admissível, todos os elementos da coluna b têm que ser não negativos. Seja

xk a variável não básica, seleccionada em 4, para entrar na base. Calcula-se θ

= b1/a’lk = min {bi/a’lk: a’lk> 0} onde a’lk é o elemento da linha i e da coluna

Xk no quadro simplex. A variável que sai da base corresponde à linha 1. θ

dá-nos o valor da variável Xk na nova base. Ao elemento a’lk chama-se pivot.

6. Actualização do quadro simplex

Obtida a nova base é necessário actualizar o quadro simplex para o

associar à nova base:

a) divide-se toda a linha 1 (pivotal) pelo valor do pivot;

b) aplica-se o método da eliminação de Gauss segundo o elemento do pivot.

A coluna onde se encontra o elemento pivot ficará com um elemento de

valor unitário (na posição do pivot), e todos os outros elementos nulos.

7. Regresso ao ponto 3

Se a condição de optimalidade se verificar o método simplex termina.


26

Exemplo:

Ao exemplo dado de maximização separa-se a rede fixa das outras redes.

Reestruturando o problema vem:

Uma empresa de telecomunicações pretende lançar no mercado uma rede móvel.

Precisa, para o efeito de definir o tarifário das suas chamadas. A tarifação será efectuada

ao minuto e as chamadas vão ser cobradas de acordo com o seu destino, havendo uma

tarifa para as chamadas efectuadas para a mesma rede, outra para as chamadas

efectuadas para as outras redes móveis e rede fixa.

O instituto responsável pelas comunicações definiu que a soma do preço de um

minuto de chamada para a mesma rede com o preço de um minuto de chamada para

outras redes móveis não pode ser superior a 0,40€, e que a soma do preço de um minuto

de chamada para a mesma rede com o preço de um minuto de chamada para outras

redes móveis e com o preço de um minuto de chamadas para a rede fixa não pode ser

superior a 0,55€.

Estudos efectuados em operadoras já existentes mostram que em média cada

cliente fala para a mesma rede 100 minutos por mês, para as outras redes móveis 30

minutos por mês, e para a rede fixa 20 minutos por mês.

Cada cliente terá que efectuar um pagamento de 15€ mensais, sendo esse o saldo

disponível para efectuar as chamadas, podendo no entanto pagar um valor mais elevado

no caso de querer dispor de um saldo maior.

Sobre tarifa cobrada a empresa obtém 70% de lucro nas chamadas efectuadas

para a mesma rede, 40% nas chamadas efectuadas para as outras redes móveis e 0,45%

nas chamadas para a rede fixa.

Como deverá a empresa cobrar as tarifas de forma a obter o maior lucro

possível?


27

Resolução:

Agora a função a maximizar é Z=0,7X1+0,4X2+0,45X3

X1: chamadas para a mesma rede.

X2: chamadas para outras redes móveis.

X3: chamadas para a rede fixa.

Sujeito a:

X1+ X2 ≤ 0,4

X1+ X2+ X3 ≤ 0,55

100 X1+30 X2+20 X3 ≤ 15

Xj ≥ 0 , j = 1, 2, 3


Preço/min

Tempo em média de

conversação % de lucro

Mesma rede X1 100 70

Outras redes

móveis X2 30 40

Rede fixa X3 20 45


28

1º Quadro simplex

X1 X2 X3 X4 X5 X6 b

X4 1 1 1 1 0 0 0,55

X5 100 * 30 20 0 1 0 15

X6 1 1 0 0 0 1 0,4

Z -0,7 -0,4 -0,45 0 0 0 0

A primeira solução básica admissível é X1 = 0, X2 = 0, X3 = 0, X4 = 0,55, X5 =

15, X6 = 0,4 onde X1, X2, X3 são as variáveis não básicas e X4, X5, X6 são as variáveis

básicas. Verificamos que esta solução não é óptima, visto que existem custos reduzidos

negativos, -0,7; -0,4 e -0,45.

A variável a entrar na base é X1, porque entre as variáveis não básicas com custo

reduzido negativo, X1 é a que tem menor valor.

A variável de saída é X5, o min {0,55/1; 15/100; 0,4/1} corresponde à linha

definida pela variável básica X5. O pivot neste caso é 100.

1ª actualização do quadro simplex

L1 → L1 – (1/100) L2

L2 → (1/100) L2

L3 → L3 – (1/100) L2

L4 → L4 + (7/1000) L2

X1 X2 X3 X4 X5 X6 b

X4 0 0,7 0,8 * 1 0 0 0,4

X1 1 0,3 0,2 0 0,01 0 0,15

X6 0 0,7 -0,2 0 -0,01 1 0,25

Z 0 -0,19 -0,31 0 0,007 0 0,105


29

Obtemos uma nova solução básica admissível, X1 = 0,15; X2 = 0; X3 = 0; X4 =

0,4; X5 = 0; X6 = 0,25, esta solução não é óptima porque existem custos reduzidos

negativos.

A variável a entrar na nova base é X3. A variável de saída é X4, porque o min

{0,4/0,8; 0,15/0,2} corresponde à linha definida pela variável X4. O novo pivot é 0,8.

Nova actualização do quadro simplex

L1 → (5/4) L1

L2 → L2 – (1/4) L1

L3 → L3 + (1/4) L1

L4 → L4 + (31/80) L1

X1 X2 X3 X4 X5 X6 b

X3 0 0,875 1 1,25 -0,0125 0 0,5

X1 1 0,125 0 -0,25 0,0125 0 0,05

X6 0 0,875 0 0,25 -0,0125 1 0,35

Z 0 0,08125 0 0,3875 0,003125 0 0,26

A nova solução básica admissível é X1 = 0,05; X2 = 0; X3 = 0,5; X4 = 0; X5 = 0;

X6 = 0,35, uma vez que neste último quadro não existem custos reduzidos negativos,

esta solução é óptima. Sendo o valor máximo da função objectivo 0,26€.

Notas:

1. No caso de, na solução anterior, os custos reduzidos e o valor máximo da

função objectivo serem todos nulos, a solução seria indeterminada. Se os

custos reduzidos fossem todos nulos e o valor máximo da função objectivo

diferente de zero, o problema era impossível.


30

2. Se fosse um caso de minimização o processo seria análogo, a diferença

consiste na paragem do processo quando não existirem custos reduzidos

positivos.


31

Bibliografia

• Lima, Yolanda e Gomes, Francelino, XEQ-MAT, Matemática 11º ano,

Editorial O Livro, Lisboa, 1997.

• Paulos, John Allen, O Circo da Matemática, Para além do enumerismo,

Publicações Europa América.

• Ramalhete, Manuel; Guerreiro, Jorge e Magalhães, Alípio, Programação

Linear, volume 1, McGraw-Hill, Torres Vedras, 1997.

• Ribeiro, Adília; Branco, Ana Paula; Pona, Fátima; Sousa, Helena Isabel e

Dias, Isabel, A Solução, Matemática 11, Texto Editora, 2ª edição, Lisboa,

1999.

Documents

Índice - Departamento de Matemática