A- Transporte - Faculdade de Ciência e Tecnologia da Universidade de Coimbra Departamento de Matemática Programação...
B- Composição
min  cijxij
 xij  ai unidades
 xij = bj armazéns receptores
sendo i = 1, ..., m;
j = 1, ..., n;
ai a capacidade de fornecimento na unidade i e bj a quantidade requerida no armazém j,
cij o custo de transporte de uma unidade de produto da unidade i para o armazém j
min  cixi
om  aixi  u Nível calórico
 bixi  v Nível calórico
sendo ai e bi o conteúdo calórico e vitamínico unitário de cada alimento i, respectivamente, ci o custo unitário de i, e u e v os níveis mínimos exigidos.
max  cjxj
 aijxj  bi Recursos
sendo i = 1, ..., m; j = 1, ..., n;
cj o lucro obtido por cada unidade do produto j,
aij a quantidade de recurso i gasta na produção de cada unidade do produto j, bi a quantidade de recurso disponível.
2.4 REPRESENTAÇÃO GRÁFICA DE PROBLEMAS DE PROGRAMAÇÃO LINEAR
Quando se inicia o estudo da Programação Linear revela-se de grande utilidade a representação gráfica de problemas simples. Apesar desta representação só ser possível quando não estão envolvidas mais de três variáveis, e particularmente simples quando se trata de duas variáveis, estas permitem pôr em evidência propriedades importantes dos problemas de P.L., bem como a natureza das suas soluções.
2.4.1 SOLUÇÕES DE UM PROBLEMA DE P.L.
Qualquer problema de P.L., em geral, pode apresentar as diferentes formas de soluções:
uma única solução óptima
múltiplas soluções óptimas (uma infinidade)
não ter óptimo finito
não ter nenhuma solução (neste caso o problema é impossível)
A regra prática para a determinação das soluções de um problema de maximização (minimização) é a seguinte: Trace-se uma qualquer recta de nível e desloque-se paralelamente a si própria , no sentido de crescimento (decrescimento) de Z, até ao(s) último(s) ponto(s) de contacto com a região admissível.
2.5 INTRODUÇÃO AOS EXEMPLOS A ESTUDAR
Os exemplos que seguidamente iremos apresentar são problemas que ilustram alguns dos domínios da aplicação da Programação Linear.
O Primeiro Exemplo é um problema de planeamento da produção que, dada a sua estrutura particular, constitui um problema típico passível de individualização.
O problema consiste em escalonar a produção ao longo de vários períodos de tempo, conhecida a procura nesses períodos, conhecidas a capacidade de produção normal e extraordinária e conhecidos ainda os custos de produção e de armazenagem ao longo do tempo.
O segundo exemplo, é um problema de misturas (rações). Esta classe de problemas caracteriza-se essencialmente por se pretender obter, com custo mínimo ou lucro máximo, um ou vários produtos, a satisfazer certos requisitos técnicos, através de vários ingredientes possuidores em grau diferente dessas características técnicas.
2.5.1 EXEMPLO DE MAXIMIZAÇÃO
A empresa Nova Linha produz artigos de vidro de alta qualidade: janelas e portas, em três secções de produção:
Secção de Serralharia: para produzir as estruturas de alumínio.
Secção de Carpintaria: para produzir as estruturas de madeira.
Secção de Vidro e Montagem: para produzir o vidro e montar as portas e janelas.
Devido à diminuição dos lucros, o gerente decidiu reorganizar a produção, e propõe produzir só os dois produtos que têm maior aceitação entre os clientes.
Produto 1: Uma porta de vidro com estrutura de alumínio.
Produto 2 : Uma janela grande com estrutura de madeira.
O departamento de Marketing da empresa concluiu que a empresa pode vender tanto de qualquer dos dois produtos, tendo em conta a capacidade de produção disponível.
Como ambos os produtos partilham a capacidade de produção da secção 3, o gerente solicitou ao Departamento de Investigação Operacional da empresa a resolução deste problema.
O Departamento de I.O. formulou o problema, utilizando os seguintes dados:
A capacidade de produção por minuto de cada secção a ser utilizada na produção destes produtos.
A capacidade de produção por minuto de cada secção, a ser utilizada para produzir uma unidade de cada produto.
Os lucros unitários para cada produto em euros.
Estes dados estão resumidos na seguinte tabela:
Capacidade utilizada por unidade de produção
Lucros unitários (em euros)
A) Formulação Matemática do Problema
O problema, formulado como problema de Programação Linear, consiste em escolher x e y por forma a:
Maximizar Z = 3x + 5y,
2y 12
x , y representam o número de unidades do produto 1 e 2, respectivamente, produzidas por minuto
Z representa o lucro total por minuto
B) Representação Gráfica do Problema
1º Passo: Construir um sistema de eixos cartesianos x, y.
2º Passo: Identificar os valores de x e y que satisfaçam todas as restrições.
Condições de não negatividade:
x  0, y  0 os pontos (x,y) estão situados no 1º Quadrante;
x  4  (x,y) estão situados à esquerda ou sobre a recta x = 4;
2y  12  y  6  (x,y) estão situados abaixo ou sobre a recta y = 6;
3x + 2y  18  (x,y) estão situados abaixo ou sobre a recta
3x + 2y = 18.
O resultado final encontra-se na Fig. 2.5.1.1, onde a região sombreada indica o conjunto dos pontos que satisfazem todas as restrições (conjunto de admissibilidade).
Fig. 2.5.1.1 Conjunto de admissibilidade do exemplo
3º Passo: Determinar a solução.
A função objectivo Z = 3x + 5y define uma recta que pode ser deslocada paralelamente no sentido do seu gradiente (garantindo o crescimento de Z), até se tornar tangente à região admissível. Os pontos de tangência obtidos (um, nenhum, ou uma infinidade) correspondem aos pontos da região admissível que optimizam a função objectivo.
recta escolhida 36 = 3x + 5y, passa pelo ponto (2,6). Pelo que a solução pretendida é x = 2, y = 6.
Fig. 2.5.1.2 Solução óptima do exemplo
Esta solução corresponde ao seguinte plano de produção:
A empresa Nova Linha deve fabricar duas portas (produto 1) e seis janelas (produto 2) por minuto obtendo um lucro de 36 euros por minuto.
2.5.2 EXEMPLO DE MINIMIZAÇÃO
Um criador de cavalos pretende determinar as quantidades de cada tipo de ração que devem ser dadas diariamente a cada animal por forma a conseguir uma certa quantidade nutritiva a um custo mínimo.
Os dados relativos ao custo de cada tipo de ração, às quantidades mínimas diárias de ingredientes nutritivos básicos a fornecer a cada animal, bem como às quantidades destes existentes em cada tipo de ração (g/kg) constam no seguinte quadro:
Quantidade mínima requerida
Custos (euros/Kg)
Quadro 2.5.2 Dados técnico-económicos
Minimizar Z = 0.05x + 0.03y
Sujeito a 20x + 50y  200
50x + 10y 150
30x + 30y  210
onde x, y representam as quantidades (em Kg), de granulado e farinha, respectivamente, a fornecer diariamente a cada animal, e Z representa o custo total (em euros) a suportar diariamente com a alimentação de cada animal.
Representação Gráfica do Problema
x  0, y  0  os pontos (x,y) estão situados no 1º Quadrante;
20x + 50y  200  2x + 5y  20  (x,y) estão situados acima ou sobre a recta 2x + 5y = 20;
50x + 10y  150  5x + y  15  (x,y) estão situados acima ou sobre a recta 5x + y = 15;
30x + 30y  210  x + y  7  (x,y) estão situados acima ou sobre a recta x + y = 7;
resultado final encontra-se na Fig. 2.5.2.1 onde a região sombreado, tal como no exemplo anterior, indica o conjunto dos pontos que satisfazem todas as restrições.
Fig. 2.5.2.1 Conjunto de admissibilidade do exemplo
3º Passo: Determinar a solução:
A função objectivo Z = 0,05x + 0,03y define uma recta que pode ser deslocada paralelamente no sentido contrário do seu gradiente (garantindo o decréscimo de Z), até ao(s) último(s) ponto(s) de contacto com a região admissível. Ao pontos de tangência assim obtidos (um, nenhum, ou uma infinidade) correspondem, mais uma vez aos pontos que optimizam a função objectivo.
A recta escolhida, 0,25 = 0,05x + 0,03y, passa pelo ponto (2,5). Pelo que a solução pretendida é x = 2, y = 5.
Fig. 2.5.2.2 Solução óptima do exemplo
Assim, é fácil de concluir que a solução pretendida é x = 2 e y = 5, valores que representam, respectivamente, as quantidades (em kg) de granulado e farinha a fornecer diariamente a cada animal.
Desta "dieta" resulta para cada criador de cavalos um custo de alimentação diário, com cada animal, de 0,25€.