Poligrafo PO UNIFRA 2011 e 2012

Prévia do material em texto

PESQUISA
OPERACIONAL
1. INTRODUÇÃO À PESQUISA OPERACIONAL
O Desenvolvimento da Pesquisa Operacional
Durante a Segunda Guerra Mundial, um grupo de cientistas foi convocado na Inglaterra para estudar problemas de estratégia e de tática associados com a defesa do país. O objetivo era decidir sobre a utilização mais eficaz de recursos militares limitados. A convocação deste grupo marcou a primeira atividade formal de pesquisa operacional.
Os resultados positivos conseguidos pela equipe de pesquisa operacional inglesa motivaram os Estados Unidos a iniciarem atividades semelhantes. Apesar de ser creditada à Inglaterra a origem da Pesquisa Operacional, sua propagação deve-se principalmente à equipe de cientistas liderada por George B. Dantzig, dos Estados Unidos, convocada durante a Segunda Guerra Mundial. Ao resultado deste esforço de pesquisa, concluído em 1947, deu-se o nome de Método Simplex.
Com o fim da guerra, a utilização de técnicas de pesquisa operacional atraiu o interesse de diversas outras áreas. A natureza dos problemas encontrados é bastante abrangente e complexa, exigindo, portanto uma abordagem que permita reconhecer os múltiplos aspectos envolvidos. Uma característica importante da pesquisa operacional e que facilita o processo de análise e de decisão é a utilização de modelos. Eles permitem a experimentação da solução proposta. Isto significa que uma decisão pode ser mais bem avaliada e testada antes de ser efetivamente implementada. A economia obtida e a experiência adquirida pela experimentação justificam a utilização da Pesquisa Operacional.
Com o aumento da velocidade de processamento e quantidade de memória dos computadores atuais, houve um grande progresso na Pesquisa Operacional. Este progresso é devido também à larga utilização de microcomputadores, que se tornaram unidades isoladas dentro de empresas. Isso faz com que os modelos desenvolvidos pelos profissionais de Pesquisa Operacional sejam mais rápidos e versáteis, além de serem também interativos, possibilitando a participação do usuário ao longo do processo de cálculo.
1.2 Modelagem
Um modelo é uma representação de um sistema real, que pode já existir ou ser um projeto aguardando execução. No primeiro caso, o modelo pretende reproduzir o funcionamento do sistema, de modo a aumentar sua produtividade. No segundo caso, o modelo é utilizado para definir a estrutura ideal do sistema.
A confiabilidade da solução obtida através do modelo depende da validação do modelo na representação do sistema real. A validação do modelo é a confirmação de que ele realmente representa o sistema real. A diferença entre a solução real e a solução proposta pelo modelo depende diretamente da precisão do modelo em descrever o comportamento original do sistema.
Um problema simples pode ser representado por modelos também simples e de fácil solução. Já problemas mais complexos requerem modelos mais elaborados, cuja solução pode vir a ser bastante complicada.
1.3 Estrutura de Modelos Matemáticos
Em um modelo matemático, são incluídos três conjuntos principais de elementos: 
a) variáveis de decisão e parâmetros: variáveis de decisão são as incógnitas a serem determinadas pela solução do modelo. Parâmetros são valores fixos no problema;
b) restrições: de modo a levar em conta as limitações físicas do sistema, o modelo deve incluir restrições que limitam as variáveis de decisão a seus valores possíveis (ou viáveis);
c) função objetivo: é uma função matemática que define a qualidade da solução em função das variáveis de decisão.
Para melhor ilustrar aos conjuntos acima, considere o seguinte exemplo:
“Uma empresa de comida canina produz dois tipos de rações: Tobi e Rex”. Para a manufatura das rações são utilizados cereais e carne. Sabe-se que:
a ração Tobi utiliza 5 kg de cereais e 1 kg de carne, e a ração Rex utiliza 4 kg de carne e 2 kg de cereais;
o pacote de ração Tobi custa $ 20 e o pacote de ração Rex custa $ 30;
o kg de carne custa $ 4 e o kg de cereais custa $ 1;
estão disponíveis por mês 10 000 kg de carne e 30 000 kg de cereais.
 Deseja-se saber qual a quantidade de cada ração a produzir de modo a maximizar o lucro."
Neste problema as variáveis de decisão são as quantidades de ração de cada tipo a serem produzidas. Os parâmetros fornecidos são os preços unitários de compra e venda, além das quantidades de carne e cereais utilizadas em cada tipo de ração. As restrições são os limites de carne e cereais e a função objetivo é uma função matemática que determine o lucro em função das variáveis de decisão e que deve ser maximizada.
1.4 Técnicas Matemáticas em Pesquisa Operacional
A formulação do modelo depende diretamente do sistema a ser representado. A função objetivo e as funções de restrições podem ser lineares ou não - lineares. As variáveis de decisão podem ser contínuas ou discretas (por exemplo, inteiras) e os parâmetros podem ser determinísticos ou probabilísticos.
O resultado dessa diversidade de representações de sistemas é o desenvolvimento de diversas técnicas de otimização, de modo a resolver cada tipo de modelo existente. Estas técnicas incluem, principalmente: programação linear, programação inteira, programação dinâmica, programação estocástica e programação não - linear. Programação linear é utilizada para analisar modelos onde às restrições e a função objetivo é linear; programação inteira se aplica a modelos que possuem variáveis inteiras (ou discretas); programação dinâmica é utilizada em modelos onde o problema completo pode ser decomposto em subproblemas menores; programação estocástica é aplicada a uma classe especial de modelos onde os parâmetros são descritos por funções de probabilidade; finalmente, programação não-linear é utilizada em modelos contendo funções não- lineares.
Uma característica presente em quase todas as técnicas de programação matemática é que a solução ótima do problema não pode ser obtida em um único passo, devendo ser obtida iterativamente. É escolhida uma solução inicial (que geralmente não é a solução ótima). Um algoritmo é especificado para determinar, a partir desta, uma nova solução, que geralmente é superior à anterior. Este passo é repetido até que a solução ótima seja alcançada (supondo que ela existe).
1.5 Fases do Estudo de Pesquisa Operacional
Um estudo de pesquisa operacional geralmente envolve as seguintes fases:
a) definição do problema;
b) construção do modelo;
c) solução do modelo;
d) validação do modelo;
e) implementação da solução.
Apesar da seqüência acima não ser rígida, ela indica as principais etapas a serem vencidas. A seguir, é apresentado um resumo da cada uma das fases.
1.5.1 Definição do problema
A definição do problema baseia-se em três aspectos principais:
descrição exata dos objetivos do estudo;
identificação das alternativas de decisão existentes;
reconhecimento das limitações, restrições e exigências do sistema.
A descrição dos objetivos é uma das atividades mais importantes em todo o processo do estudo, pois a partir dela é que o modelo é concebido. Da mesma forma, é essencial que as alternativas de decisão e as limitações existentes sejam todas explicitadas, para que as soluções obtidas ao final do processo sejam válidas e aceitáveis.
1.5.2 Construção do modelo
A escolha apropriada do modelo é fundamental para a qualidade da solução fornecida. Se o modelo elaborado tem a forma de um modelo conhecido, a solução pode ser obtida através de métodos matemáticos convencionais. Por outro lado, se as relações matemáticas são muito complexas, talvez se faça necessária a utilização de combinações de metodologias.
1.5.3 Solução do modelo
O objetivo desta fase é encontrar uma solução para o modelo proposto. Ao contrário das outras fases, que não possuem regras fixas, a solução do modelo é baseada geralmente em técnicas matemáticas existentes. No caso de um modelo matemático, a solução éobtida pelo algoritmo mais adequado, em termos de rapidez de processamento e precisão da resposta. Isto exige um conhecimento profundo das principais técnicas existentes. A solução obtido, neste caso, é dita "ótima".
1.5.4 Validação do modelo
Nessa altura do processo de solução do problema, é necessário verificar a validade do modelo. Um modelo é válido se, levando-se em conta sua inexatidão em representar o sistema, ele for capaz de fornecer uma previsão aceitável do comportamento do sistema. 
Um método comum para testar a validade do sistema é analisar seu desempenho com dados passados do sistema e verificar se ele consegue reproduzir o comportamento que o sistema apresenta um projeto. Nesse caso, a validação é feita pela verificação da correspondência entre os resultados obtidos e algum comportamento esperado do novo sistema.
1.5.5 Implementação da solução
Avaliadas as vantagens e a validação da solução obtida, esta deve ser convertida em regras operacionais. A implementação, por ser uma atividade que altera uma situação existente, é uma das etapas críticas do estudo. É conveniente que seja controlada pela equipe responsável, pois, eventualmente, os valores da nova solução, quando levados à prática, podem demonstrar a necessidade de correções nas relações funcionais do modelo conjunto dos possíveis cursos de ação, exigindo a reformulação do modelo em algumas de suas partes.
ÁLGEBRA LINEAR
2 Introdução
Ao longo do curso de pesquisa operacional, conceitos matemáticos como matrizes e vetores são largamente utilizados. Este capítulo tem como objetivo apresentar uma revisão desses fundamentos matemáticos, de modo que o curso possa ser compreendido.
2.1 Vetores
Um vetor é um conjunto de números, que pode ser escrito como p = (p1, p2, ... , pn).
O vetor p é um vetor de dimensão n, ou seja, possuem n elementos. Vetores são geralmente representadas por letras minúsculas em negrito, e seus elementos são geralmente representados por letras minúsculas com um subscrito. A letra usada para os elementos é normalmente a mesma letra utilizada para o vetor. O subscrito representa o índice do elemento no vetor. Por exemplo, p2 é o segundo elemento do vetor. A notação pi indica o i-ésimo elemento do vetor.
2.1.1 Soma e subtração de vetores
Dois vetores podem ser adicionados se e somente se eles tiverem a mesma dimensão. Para somar dois vetores, basta somar individualmente cada elemento deles. O vetor resultante será da mesma dimensão do vetores originais. 
Simbolicamente, temos que, se r = p + q, então ri= pi+ qi, para todo i.
Dados os vetores
p = (4, 5, 1, 7) q = (1, -2, 3, -4) r = (1, 5, 4) temos que:
p + q = (5, 3, 4, 3);
não é possível computar p + r, nem q + r, visto que p e q são de 4ª dimensão e r é de 3ª.
Um vetor pode ser multiplicado por um escalar, multiplicando-se cada elemento do vetor por este escalar.
 Por exemplo, 2(1, 3, -2) = (2, 6, -4)
Subtração entre dois vetores é equivalente a somar o primeiro com o produto do segundo pelo escalar -1. Então s - t = s + (-t). Por exemplo.
(1, 4, 3) - (0, 2, -1) = (1, 4, 3) + (0, -2, 1) = (1, 2, 4)
2.1.2 Vetores LD e LI
Um conjunto de vetores p1, p2,... , pn, é dito linearmente independente (LI) se e somente se, para todo 
 real,
 
= 0
Implica que todo 
j = 0, onde 
 são quantidades escalares. Se 
=0 para algum 
j 0, os vetores são ditos linearmente dependentes (LD). 
Por exemplo, os vetores p1 = (1, 2) p2 = (2, 4) são linearmente dependentes, já que existe
 = 2 e 
= -1 para os quais 
 p1 + 
p2 = 0.
2.2 Matrizes
Uma matriz é um conjunto retangular de números, que pode ser escrito como:
 A= 
A matriz A é uma matriz de ordem m x n, ou seja, possui m linha e n colunas. Matrizes são geralmente representadas por letras maiúsculas em negrito, e seus elementos são geralmente representados por letras minúsculas com dois subscritos. A letra usada para os elementos é normalmente a mesma letra utilizada para a matriz. Os subscritos representam respectivamente a linha e a coluna ocupadas pelo elemento na matriz. Por exemplo, a23 é o elemento localizado na segunda linha e na terceira coluna da matriz. A notação aij indica o elemento localizado na i-ésima linha e na j-ésima coluna da matriz.
Duas matrizes A e B são iguais se aij= bij para qualquer i e j. Para isso, é necessário que as matrizes A e B sejam de mesma ordem, ou seja, tenham o mesmo número de linhas e o mesmo número de colunas.
2.2.1 Soma e subtração de matrizes
Duas matrizes podem ser adicionadas se e somente se elas forem da mesma ordem. Para somar duas matrizes, basta somar individualmente cada elemento delas. A matriz resultante será da mesma ordem das matrizes originais. Simbolicamente, temos que, se C = A + B, então cij= aij+ bij, para todo i e j.
Dadas as matrizes
A= 
 B= 
C =
 D= 
Temos que:
(As matrizes A e C são iguais;
(A + B = 
(Não é possível computar A + D, nem B + D, visto que A e B são 3 x 4 e D é 3 x 3.
Uma matriz pode ser multiplicada por um escalar, multiplicando-se cada elemento da matriz por este escalar. Por exemplo,
2 
 = 
 .
Subtração entre duas matrizes é equivalente a somar a primeira com o produto da segunda pelo escalar -1. Então E - F = E + (-F). Por exemplo.
 - 
 = 
 + 
 = 
2.2.2 Produto de matrizes
O produto de duas matrizes somente pode ser efetuado se o número de colunas da matriz à esquerda for igual ao número de linhas da matriz à direita. 
O produto de matrizes é, em geral, não comutativo, ou seja, dadas duas matrizes A e B e seu produto, AB, o produto BA pode não existir e, se existe, pode não ser igual à AB. O produto de duas matrizes tem o número de linhas da matriz à esquerda e o número de colunas da matriz à direita. Ou seja, sendo C = AB, se A é m x n e B é n x p, C é m x p.
Os elementos da matriz resultante são calculados através do somatório dos produtos de elementos das duas matrizes. Especificamente, cij é calculado por ai1 b1j + ai2 b2j + ... + ain bnj, onde n é o número de colunas de A e de linhas de B.
Exemplos:
1. A =
 B = 
 
A.B = 
 B. A= não existe
2. A = 
 B = 
 
A. B = 
 B. A = 
Note que no primeiro exemplo existe apenas o produto AB, não sendo possível efetuar o produto BA. No segundo exemplo, apesar de ser possível efetuar os dois produtos, as matrizes resultantes não são iguais, não sendo sequer do mesmo tipo.
2.2.3 Matrizes especiais
Matriz quadrada
Uma matriz quadrada tem o mesmo número de linhas e de colunas. A ordem de uma matriz quadrada é o seu número de linhas (ou de colunas).
Exemplos: matrizes 2 x 2 (2ª ordem), 3 x 3 (3ª ordem), n x n (n-ésima ordem).
Matriz nula
Uma matriz nula possui zeros em todos os seus elementos.
 , 
A matriz nula é equivalente ao zero para adição em álgebra escalar, ou seja, se B é uma matriz nula de mesmo tipo de A, então A + B = B + A = A.
Matriz identidade
Uma matriz identidade, denotada por I, é uma matriz quadrada onde sua diagonal principal é composta de 1's e todos os outros elementos são zero.
Exemplos: 
 , 
A matriz identidade é equivalente ao um para produto em álgebra escalar, ou seja, AI = A.
Matriz transposta
A transposta de uma matriz é a matriz obtida pela troca das linhas pelas colunas da matriz original, de modo que a coluna j da matriz original passe a ser a linha j da matriz transposta e a linha i da matriz original passe a ser a coluna i da matriz transposta. A transposta de uma matriz A é indicada pela notação AT ou A'.
Exemplos: A = 
 At = 
A transposta de uma matriz m x n será sempre uma matriz n x m.
(Matriz simétrica
Uma matriz é dita simétricase ela for igual à sua transposta. Ou seja, uma matriz A, simétrica, é necessariamente quadrada e aij= aji.
Exemplos: A = At = 
 B = Bt = 
 
(Matriz anti-simétrica
Uma matriz é dita anti-simétrica se ela for simétrica à sua transposta, isto é, A = - AT. Ou seja, uma matriz A, simétrica, é necessariamente quadrada e aij = - aji. Os elementos da diagonal principal de uma matriz anti-simétrica são necessariamente nulos.
Exemplos: A = - At = 
 B = - Bt = 
 
2.2.4 A inversa de uma matriz
A operação de divisão não é definida em álgebra matricial. Entretanto, para certas matrizes quadradas existe outra (única) matriz quadrada de mesma ordem que o produto das duas matrizes é a matriz identidade. Esta matriz é chamada de matriz inversa da primeira matriz. A inversa de uma matriz é designada pelo expoente -1.
Exemplo: A = 
 , A-1 = 
 = A A-1 = A-1 A = I
2.3 Sistemas de Equações Lineares
Tanto as linhas quanto as colunas de uma matriz podem ser tratadas por vetores. Um vetor pode ser considerado uma matriz de uma única linha, ou uma única coluna. Quando um vetor é considerado uma matriz com uma única linha, é chamado vetor linha. Quando é uma matriz de uma única coluna, é chamado de vetor coluna. Um vetor coluna será representado da mesma forma que um vetor convencional, ou seja, uma letra minúscula em negrito (p, q, r). Quando for o caso de um vetor linha, ele será representado como um vetor transposto (pT, qT, rT).
Suponha o seguinte sistema de equações lineares:
 2 x1 - x2 = 7
- x1 + 4 x2 = 0
Este sistema pode ser representado na forma matricial por:
 
 . 
 = 
 Ou Ax = B
onde A = 
 , B = 
 , C = 
O vetor coluna x é o vetor solução do sistema de equações e pode ser calculado por x = A-1 b. Para a solução de um sistema de equações lineares, são propostos alguns métodos.
2.3.1 Método algébrico por adição
Pelo menos uma das equações deve ser multiplicada por um escalar real, de modo que, após a soma das equações, apenas uma das variáveis seja efetivamente a incógnita do problema. Por exemplo, 
4 x1 + 8 x2 = 160
6 x1 + 4 x2 = 120
Multiplicando a segunda equação por (-2), temos.
4 x1 + 8 x2 = 160
-12 x1 - 8 x2 = -240
Somando as duas equações, chega-se a: -8 x1 = -80
Daí calcula-se facilmente o valor de x1 e, substituindo este valor em qualquer uma das equações acima, calcula-se o valor de x2.
x1 = 10
x2 = 15
2.3.2 Método algébrico por substituição
Isola-se uma das variáveis em uma das equações, substituindo-se a relação obtida na outra equação. Por exemplo,
4 x1 + 8 x2 = 160
6 x1 + 4 x2 = 120
Manipulando a primeira equação, temos que: x1 = 
Substituindo x1 na segunda equação, 6.(40 - 2 x2) + 4 x2 = 120
Resolvendo a equação algebricamente, e aplicando o valor de x2 encontrado na primeira equação 240 - 12 x2 + 4 x2 = 120 => -8 x2 = -120 = > x2 = 15 e x1 = 10
2.3.3 Método de Gauss-Jordan
Consiste da derivação de um sistema específico de equações lineares que tenha a mesma solução que o sistema original. Este novo sistema deverá ter o formato de uma matriz identidade, o que pode ser obtido através de combinações lineares das equações originais. Assim, pretende-se que:
 4 x1 + 8 x2 = 160 1 x1 + 0 x2 = a
 6 x1 + 4 x2 = 120  0 x1 + 1 x2 = b
 
São permitidas as seguintes transformações lineares:
Troca de linhas
Multiplicação da linha por um escalar
Soma de uma linha multiplicada por um escalar a uma outra linha
Notação:
L n L m troca das linhas n e m;
L n k L n multiplicação da linha n pelo escalar k;
L n L n+ k L m soma da linha m multiplicada pelo escalar k à linha n.
Para resolver o exemplo acima, são seguidos os seguintes passos:
1. L1 L1 / 4 (divisão da linha 1 por 4) - transformação do coeficiente de x1 na equação 1 para 1.
x1 + 2 x2 = 40
6 x1 + 4 x2 = 120
2. L2 L2 - 6 L1 (subtração da linha 2 pela linha 1 multiplicada por 6) - transformação do coeficiente de x1 na equação 2 para 0.
x1 + 2 x2 = 40
0 x1 - 8 x2 = -120
3. L2 - L2 / 8 (divisão da linha 2 por (-8)) - transformação do coeficiente de x2 na equação 2 para 1.
x1 + 2 x2 = 40
0 x1 + 1 x2 = 15
4. L1 L1 - 2 L2 (subtração da linha 1 pela linha 2 multiplicada por 2) - transformação do coeficiente de x2 na equação 1 para 0.
x1 + 0 x2 = 10
0 x1 + 1 x2 = 15
Solução x1 = 10 e x2 = 15
Exercícios:
Resolver o sistema:
 4x – 3y = -2
 2x +4y = 10
 x + 2y + 4z = 5
 2x – y + 2z = 8
 3x – 3y – z = 7 
 a + b + c = 12
 3a – b +2c =14
 2a -2b + c = -3
 4x – 3y + z = 3
 3x + y +4z = -1
 5x – 2y +3z =2
 x + 3y – z = 11/2
 2x – 2y + z = -3
 3x –y +z = -3/2
 3x + 2y – z = 5
 2x + y + z = 7
 x – 2y + 3z = 1
 
 x + 2y + 8z = 0
 x – 3y – 7z = 0 
 x – y – z = 0
 x + 3y + 2z = 2
 3x + 5y + 4z = 4
 5x + 3y + 4z = -10
 x + y + z = 1
 2x + y – z = 1
 x – y + z = 0
 
PROGRAMAÇÃO LINEAR
3.1 Definição
O problema geral de programação linear é utilizado para otimizar (maximizar ou minimizar) uma função linear de variáveis, chamada de "função objetivo", sujeita a uma série de equações ou inequações lineares, chamadas restrições. A formulação do problema a ser resolvido por programação linear segue alguns passos básicos.
Deve ser definido o objetivo básico do problema, ou seja, a otimização a ser alcançada. Por exemplo, maximização de lucros, ou de desempenhos, ou de bem-estar social; minimização de custos, de perdas, de tempo. Tal objetivo será representado por uma função objetivo, a ser maximizada ou minimizada;
Para que esta função objetivo seja matematicamente especificada, devem ser definidas as variáveis de decisão envolvidas. Por exemplo, número de máquinas, a área a ser explorada, as classes de investimento à disposição etc. Normalmente, assume-se que todas estas variáveis possam assumir somente valores positivos;
Estas variáveis normalmente estão sujeitas a uma série de restrições, normalmente representadas por inequações. Por exemplo, quantidade de equipamento disponível, tamanho da área a ser explorada, capacidade de um reservatório, exigências nutricionais para determinada dieta etc.
Todas essas expressões, entretanto, devem estar de acordo com a hipótese principal da programação linear, ou seja, todas as relações entre as variáveis devem ser lineares. Isto implica proporcionalidade das quantidades envolvidas. Esta característica de linearidade pode ser interessante no tocante à simplificação da estrutura matemática envolvida, mas prejudicial na representação de fenômenos não lineares (por exemplo, funções de custo tipicamente quadráticas).
3.2 Formulação de Modelos
O problema geral de programação linear pode ser definido por Maximizar (ou minimizar)
Z c1 x1 c2 x2 ...cn xn 
Sujeito a:
 a11 x1 a12 x2+ ...+ a1nxn b (ou , ou =)
a21 x1 a22 x2+ ... +a2n xn b (ou , ou =)
am1 x1 a m2x2 ...amn xn b m(ou , ou =)
x1, x2, ..... , xn
3.3 Exemplo
Vamos reescrever aqui o exemplo da seção 1.3.
"Uma empresa de comida canina produz dois tipos de rações: Tobi e Rex. Para a manufatura das rações são utilizados cereais e carne. Sabe-se que:
A ração Tobi utiliza 5 kg de cereais e 1 kg de carne, e a ração Rex utiliza 4 kg de carne e 2 kg de cereais;
O pacote de ração Tobi custa $ 20 e o pacote de ração Rex custa $ 30;
O kg de carne custa $ 4 e o kg de cereais custa $ 1;
estão disponíveis por mês 10 000 kgde carne e 30 000 kg de cereais.
Deseja-se saber qual a quantidade de cada ração a produzir de modo a maximizar o lucro.
Nosso modelo deseja maximizar o lucro (Z) a partir da quantidade de ração Tobi (x1) e de ração Rex (x2). A Tabela 1 apresenta o cálculo do lucro unitário de cada ração.
Tabela 1 - Cálculo do lucro unitário de cada ração
	
	Ração Tobi
	Ração Rex
	Custo de carne
	1 kg x $ 4 = $ 4
	4 kg x $ 4 = $ 16
	Custo de cereais
	5 kg x $ 1 = $ 5
	2 kg x $ 1 = $ 2
	Custo total
	$ 9
	$ 18
	Preço
	$ 20
	$ 30
	Lucro
	$ 11
	$ 12
A função objetivo pode ser escrita como maximizar Z = 11 x1 + 12 x2
sujeito a: 1 x1 + 4 x2 10000 (restrição de carne)
 5 x1 + 2 x2 30000 (restrição de cereais)
 x1, x2 0 (positividade das variáveis)
3.4 Solução Gráfica
Este problema com apenas duas variáveis pode ser resolvido graficamente. Traça-se um gráfico com os seus eixos sendo as duas variáveis x1 e x2. A partir daí, traçam-se as retas referentes às restrições do problema e delimita-se a região viável (Figura 1).
Encontrada a região viável, deve-se traçar uma reta com a inclinação da função objetivo. São então traçadas diversas paralelas a ela no sentido de Z crescente (maximização da função), como na Figura 2. O ponto ótimo é o ponto onde a reta de maior valor possível corta a região viável (normalmente num vértice).
Figura 1: Região viável para o problema das rações
Figura 2: Busca da solução ótima para o problema das rações
Exercícios
Certa empresa fabrica dois produtos P1 e P2. O lucro por unidade de P1 é de 100u.m. e o lucro unitário de P2 é de 150 u.m. A empresa necessita de 2 horas para fabricar uma unidade de P1 e 3 horas para fabricar uma unidade de P2. O tempo mensal disponível para essas atividades é de 120 horas. As demandas esperadas para os 2 produtos levaram a empresa a decidir que os montantes produzidos de P1 e P2 não devem ultrapassar 40 unidades de P1 e 30 unidades de P2 por mês. Construa o modelo do sistema de produção mensal com o objetivo de maximizar o lucro da empresa.
Um vendedor de frutas pode transportar 800 caixas de frutas para sua região de vendas. Ele necessita transportar 200 caixas de laranjas a 20 u.m. de lucro por caixa, pelo menos 100 caixas de pêssegos a 10 u.m de lucro por caixa, e no máximo 200 caixas de tangerinas a 30 u.m. de lucro por caixa. De que forma deverá ele carregar o caminhão para obter o lucro máximo? Construa o modelo do problema e seu gráfico.
Uma rede de televisão local tem o seguinte problema: foi descoberto que o programa “A” com 20 minutos de música e 1 minuto de propaganda cama a atenção de 30.000 telespectadores, enquanto o propaganda “B”, com 10 minutos de música e 1 minuto de propaganda chama a atenção de 10.000 telespectadores. No decorrer de uma semana, o patrocinador insiste no uso de no mínimo 5 minutos para sua propaganda e que não há verba para mais de 80 minutos de música. Quantas vezes por semana cada programa devem ser levadas ao ar para obter o número máximo de telespectadores? Construa o modelo e gráfico do problema.
Um sapateiro faz 6 sapatos por hora, se fizer somente sapatos, e 5 cintos por hora, se fizer somente cintos. Ele gasta 2 unidades de couro para fabricar 1 unidade de sapato e 1 unidade de couro para fabricar uma unidade de cinto. Sabendo-se que o total disponível de couro é de 6 unidades e que o lucro unitário por sapato é de 5 unidades monetárias e o do cinto é de 2 unidades monetárias, pede-se: o modelo do sistema de produção do sapateiro, se o objetivo é maximizar o lucro por hora.
Encontre a solução ótima da seguinte problema de programação linear testando o valor da função objetivo em cada um dos pontos abaixo descritos:
Max Z = 5x + 2y
 Restrições x + 2y ≤ 9 
 x ≤ 3 
 y ≤ 4
 x, y ≥ 0
b) Max Z = 80x + 75y
 Restrições: x + 3y ≤ 4
 2x + 5y ≤ 150
 x, y ≥ 0
As indústrias “Sara Cura Produtos Farmacêuticos” desejam produzir dois medicamentos, um analgésico e um antibiótico, que dependem de duas matérias-primas A e B, disponíveis em quantidades de 8 e 5 toneladas, respectivamente. Na fabricação de 1 ton de analgésico são empregadas 1 ton de matéria A e 1 ton de matéria B, e na fabricação de 1 ton de antibiótico são empregadas 4 ton de A e 1 ton de B. Sabendo que cada tonelada de antibiótico é vendida a R$8,00 e de analgésico a R$5,00, encontre, por meio de gráfico (soluções viáveis), a quantidade de toneladas de medicamentos a ser produzida pelas indústrias Sara Cura, de maneira a maximizar sua receita.
Uma empresa que monta computadores e equipamentos de computador está prestes a iniciar a produção de dois novos tipos de microcomputador. Cada tipo demandará tempo de montagem, tempo de inspeção e espaço para armazenamento. As quantidades de recursos que podem ser destinadas à produção dos microcomputadores são limitadas. O gerente pretende determinar o número de microcomputadores de cada tipo que a empresa deverá produzir, a fim de maximizar o lucro gerado pela venda dos microcomputadores. A fim de desenvolver um modelo adequado para o problema, o gerente manteve reuniões com o pessoal da área de projetos e fabricação. Como resultado dessas reuniões, o gerente obteve as seguintes informações:
	
	Tipo 1
	Tipo 2
	Disponibilidade
	Lucro unitário
	$ 60
	$ 50
	
	Tempo de montagem por unidade
	4 horas
	10 horas
	100 horas
	Tempo de inspeção por unidade
	2 horas
	1 hora
	22 horas
	Espaço de armazenamento por unidade
	0,1 m3
	0.1m3
	1,3 m3
 Determine as quantidades de microcomputador do tipo 1 e do tipo 2 que devem ser produzidas de forma a maximizar o lucro. Resolva pelo método gráfico.
Uma pequena oficina produz-se dois tipos de peças: A e B. Para tal, o artesão dispõe de uma única máquina que pode utilizar até 8 horas por dia. Para produzir uma peça A o artesão necessita de utilizar a máquina durante 1 hora, enquanto que para produzir uma peça de B o artesão ocupa a máquina durante duas horas.
Recentemente o artesão recebeu a visita de uma equipe de consultores da região de turismo que definiu:
As peças tipo A serão vendidos por 5 u.m. e as do tipo B por 10 u.m., respectivamente,
A produção de peças tipo A deve ser pelo menos dupla da produção de peças tipo B,
A máquina não deve ser ocupada em mais do que 50% do seu tempo disponível com cada um dos dois tipos de peça a produzir.
Determine o esquema de produção que permite maximizar o valor das receitas.
Recorrendo a um processo gráfico, determine a sua solução ótima.
Consideremos o caso da indústria de móveis FRESÃO, que ilustra um problema de composição de produto. A Fresão produz, entre outros artigos, dois tipos de conjunto para sala de jantar: o conjunto “Beatrice” e o conjunto “Anamaria”.
A Fresão está preparando sua programação semanal de produção para os dois conjuntos. Sabe-se que, embora não haja restrições no tocante à demanda do conjunto “Beatrice”, (dentro das limitações de produção atuais) para o conjunto “Anamaria” dificilmente a demanda semanal ultrapassará 8 unidades. A fabricação dos dois conjuntos é dividida em dois grandes blocos de operações: Preparação (consistindo do corte da madeira e preparação para montagem) e Acabamento (consistindo da montagem dos conjuntos e acabamento final).
Em fase dos outros produtos existentes, a Fresão não poderá alocar mais de 100 horas para preparação e 108 horas para acabamento durante a semana. O conjunto “Beatrice” exige 5 horas para a preparação e 9 horas para o acabamento, enquanto que para o conjunto “Anamaria” esses números são de 10 e 6 horas respectivamente.
A Fresão deve decidir quantas unidades de cada conjuntodevem ser fabricadas, levando em conta que o conjunto “Beatrice” fornece um lucro unitário de R$ 4000,00 enquanto que para o conjunto “Anamaria” o lucro é de R$ 5000,00.
O administrador de uma pequena empresa de móveis está pensando em otimizar a utilização dos recursos de seu estoque. Essa fábrica produz poltronas em dois modelos, “Albany” e “Bridget”, forradas em brim e lona.
Ele sabe que para forrar uma poltrona “Albany” são precisos 2 m2 de brim e 6 m2 de lona. Já para forrar uma poltrona “Bridgit” são precisos 4 m2 de brim e 4 m2 de lona. No estoque, a fábrica dispõe de 160 m2 de brim e 240m2 de lona. 
 Qualquer dos modelos de poltrona é vendido por R$ 160,00. Com essas informações, de que modo o administrador pode sugerir a produção da fábrica para obter a máxima renda? Em outras palavras, qual é o número de poltronas de cada modelo que devem ser forradas para otimizar a renda?
A indústria de confecções “Marimar” produz dois produtos, produto “x” bermuda e produto “y” camiseta.
O produto “x” bermuda para ser fabricado consome na agregação tecnológica (corte- costura- acabamento) 3 unidades de tempo (3 UT) no corte; 1,5 unidades de tempo na costura e 5 unidades de tempo no acabamento, totalizando 9,5 UT na linha de produção.
O produto “y” camiseta para ser fabricado consome na agregação tecnológica (corte- costura- acabamento) 3 UT de corte, 3 UT de costura e 3 UT de acabamento, totalizando 9 UT na linha de produção. O setor de corte tem uma capacidade de 210 UT. O setor de costura tem uma capacidade de 180 UT e o setor de acabamento tem uma capacidade de 330 UT. Totalizando, a capacidade de três setores tem-se 720 UT. A matéria prima necessária para a fabricação dos produtos encontra-se estoque e toda produção é vendida à vista no final da linha de produção. Que quantidades deverá ser produzida de bermudas e ou de camisetas para ter o máximo de lucro, sabendo que o lucro para cada bermuda produzida é de 2 UM e cada camiseta produzida é de 3 UM?
Considerando as mesmas informações do exercício 11, quanto devo fabricar de bermuda ou de camiseta para ter o máximo de lucro, sabendo que o lucro por cada bermuda é de 6 UM e de cada camiseta é de 4 UM?
Uma indústria produz determinado móvel em dois modelos, o luxo e o standard. O modelo luxo é produzido com um lucro de R$ 300,00 por unidade e o modelo standard com um lucro de 100,00. O modelo standard requer 2 horas de fabricação. Ocupa uma área de 4 m2 por unidade no armazenamento e não necessita de pintura. Já o modelo luxo requer 3 horas de fabricação, ocupa 3 m2 por unidade no armazenamento e 1 hora de pintura. O tempo disponível para fabricação encontra-se limitado em 24 horas e o espaço para armazenagem em 36 m2 e a seção de pintura dispõe de 6 horas. Quantas unidades de cada modelo de móvel devem ser fabricadas a fim de maximizar o lucro da empresa?
Uma fábrica produz dois produtos, A e B. Cada um deles deve ser processado por duas máquinas, M1 e M2. Devido à programação de outros produtos, que também utilizam essas máquinas, a máquina M1 tem 24 horas de tempo disponível para os produtos A e B, enquanto a máquina M2 tem 16 horas de tempo disponível. Para produzir uma unidade do produto A, gastam-se 4 horas em cada uma das máquinas M1 e M2. Para produzir uma unidade B, gastam-se 6 horas na máquina M1 e 2 horas na máquina M2. Cada unidade vendida do produto A geral um lucro de R$ 80,00 e cada unidade vendida do produto B, um lucro de R$ 60,00. Existe uma previsão máxima de demanda para o produto B de 3 unidades, não havendo restrições quanto a demanda do produto A. Deseja-se saber quantas unidades de a e B devem ser produzidas, de forma a maximizar o lucro e, ao mesmo tempo, obedecer a todas as restrições deste enunciado. 
Um fabricante deseja maximizar a receita bruta. A tabela abaixo ilustra as composições das ligas, seus preços e as limitações nas disponibilidades de matéria-prima.
	Itens / Composição
	Liga – Tipo A
	Liga – Tipo B
	Matéria-prima disponível
	Cobre 
	2
	1
	16
	Zinco
	1
	2
	11
	Chumbo
	1
	3
	15
	Preço unitário de venda
	R$30,00
	R$50,00
	-------
 O objetivo é maximizar o valor das vendas totais.
Uma pequena empresa fabrica dois produtos P1 eP2, que passa por três departamentos de fabricação, conforme mostram as tabelas abaixo
Tabela 1: Exigências de tipo de fabricação para se produzir uma unidade do produto por departamento:
	Produtos
	Tempo de fabricação em horas
	
	Depto A
	Depto B
	Depto C
	P1
	2
	1
	4
	P2
	2
	2
	2
 Tabela 2: Limites de capacidade de fabricação:
	Departamentos
	Homens/ hora/semana disponível
	Depto A
	160
	Depto B
	120
	Depto B
	280
Considerando que a produção é vendida em sua totalidade, com o lucro para P1 de 10 dólares e de P2 de 15 dólares. Determine:
Quanto fabricar de cada produto para se fazer o melhor uso possível das instalações produtivas?
Qual é o lucro máximo encontrado?
 
O MÉTODO SIMPLEX
O Método Simplex caminha pelos vértices da região viável até encontrar uma solução que não possua soluções vizinhas melhores que ela. Esta é a solução ótima. A solução ótima pode não existir em dois casos: quando não há nenhuma solução viável para o problema, devido a restrições incompatíveis; ou quando não há máximo (ou mínimo), isto é, uma ou mais variáveis podem tender a infinito e as restrições continuarem sendo satisfeitas, o que fornece um valor sem limites para a função objetivo.
4.1 Exemplo de um Problema
O modelo de programação linear pode ser resolvido por um método de solução de sistema de equações lineares. O processo que será apresentado no exemplo a seguir, retirado de ANDRADE (2000), é bastante intuitivo e tem por finalidade apresentar a metodologia utilizada pelo método Simplex.
a) Formulação do problema
“Uma marcenaria deseja estabelecer uma programação diária de produção”. Atualmente, a oficina faz apenas dois produtos: mesa e armário, ambos de um só modelo. Para efeito de simplificação, amos considerar que a marcenaria tem limitações em somente dois recursos: madeira e mão-de-obra, cujas disponibilidades diárias são mostradas na tabela a seguir.
	Recurso
	Disponibilidade
	Madeira
	12m2
	Mão-de-obra
	8 H.h
O processo de produção é tal que, para fazer uma mesa a fábrica gasta 2 m2 de madeira e 2 H.h de mão-de-obra. Para fazer um armário, a fábrica gasta 3 m2 de madeira e 1 H.h de mão de obra.
Além disso, o fabricante sabe que cada mesa dá uma margem de contribuição para o lucro de $ 4 e cada armário de $ 1. “O problema é encontrar o programa de produção que maximiza a margem de contribuição total para o lucro.”.
b) Montagem do modelo
As variáveis de decisão envolvidas no problema são:
x1: quantidade a produzir de mesas
x2: quantidade a produzir de armários
A função objetivo é:
 Lucro: z = 4 x1 + x2
Para as restrições, a relação lógica existente é:
Utilização de recurso =Disponibilidade
Assim temos
Madeira: 2 x1 + 3 x2 <12
Mão-de-obra: 2 x1 + x2 <8
x1, x2 <0
O modelo completo é:
Maximizar: z = 4 x1 + x2
Sujeito a 2 x1 + 3 x2 <12
2 x1 + x2 <8
x1, x2 <0
c) Solução do modelo
Já conhecemos o método de solução gráfica para problemas de programação linear de duas variáveis. Será agora apresentada a solução por sistemas de equações lineares.
De forma a transformar as restrições do problema de programação linear de inequações em equações, são introduzidas as variáveis de folga. Neste problema, as restrições têm a seguinte estrutura lógica:
Utilização de recurso =Disponibilidade.
Ao se introduzir o conceito de folga de recurso, a inequação pode ser escrita como: Utilização de recurso + Folga = Disponibilidade.
Isso significa que:
Utilização de recurso < Disponibilidade implica Folga > 0;
Utilização de recurso = Disponibilidade implica Folga = 0.
Deste modo, a folga de cada recurso pode ser representadapor uma variável de forma exatamente igual à produção de cada produto. Desse modo, vamos chamar:
f1: folga de madeira;
 f2: folga de mão-de-obra.
Introduzindo as variáveis de folga, o problema a ser resolvido passa a ser:
Maximizar: z = 4 x1 + x2
Sujeito a 2 x1 + 3 x2 + f1 = 12
2 x1 + x2 + f2 = 8
x1, x2, f1, f2 <0
O problema se transformou em encontrar a solução do sistema de equações lineares que maximiza o lucro. Como neste caso o número de variáveis (m = 4) é superior ao número de equações (n = 2), o sistema é indeterminado, apresentando infinitas soluções.
No entanto, todas as variáveis devem ser maiores ou iguais a zero. Atribuir zero a uma variável significa não produzir um dos produtos (se a variável for x1 ou x2) ou utilizar toda a disponibilidade de recursos (se a variável for f1 ou f2). 
Desta forma, podemos encontrar soluções para o sistema de equações zerando duas variáveis (n - m = 2) e encontrando o valor para as duas variáveis restantes. Teremos que resolver então:
�� EMBED Equation.3 = 
, sistemas de equações lineares.
Uma vez resolvido um sistema, serão aplicados na função objetivo os valores encontrados. As variáveis zeradas são chamadas variáveis não-básicas. As variáveis cujos valores são calculados pelo sistema de equações são chamadas variáveis básicas.
c.1) Variáveis não-básicas: x1 = 0 e x2 = 0
temos as variáveis básicas f1 = 12 e f2 = 8
dando o lucro z = 0
c.2) Variáveis não-básicas: x1 = 0 e f1 = 0
temos as variáveis básicas x2 = 4
f2 = 4
dando o lucro z = 4
c.3) Variáveis não-básicas: x1 = 0 e f2 = 0
temos as variáveis básicas x2 = 8
f1 = -12
como f1 < 0, a solução obtida é INVIÁVEL.
c.4) Variáveis não-básicas: x2 = 0 e f1 = 0
temos as variáveis básicas x1 = 6
f2 = -4
 como f2 < 0, a solução obtida é INVIÁVEL.
c.5) Variáveis não-básicas: x2 = 0 e f2 = 0
temos as variáveis básicas x1 = 4
f1 = 4
dando o lucro z = 16
c.6) Variáveis não-básicas: f1 = 0 e f2 = 0
temos as variáveis básicas x1 = 3
x2 = 2
dando o lucro z = 14
Comparando todas as soluções encontradas por este processo, achamos à solução ótima, ou seja,
x1 = 4, x2 = 0, f1 = 4, f2 = 0, dando um lucro z = 16.
4.2 Desenvolvimento do Método Simplex
Da forma como foi resolvido o problema anteriormente, é necessário que muitos sistemas de equações sejam resolvidos e suas soluções comparadas. Para problemas reais de programação linear, esta solução se torna inviável. Desta forma, para termos condições de resolver um problema de programação linear, precisamos de uma sistemática que nos diga:
Qual o sistema de equações que deve ser resolvido;
Que o próximo sistema a ser resolvido fornecerá uma solução melhor que os anteriores;
Como identificar um solução ótima, uma vez que a tenhamos encontrado.
Essa sistemática é o método Simplex, e as regras que o método utiliza para atender às três questões acima são, basicamente, os critérios que desenvolvemos nos itens anteriores. Vamos voltar ao nosso pequeno problema, já com as variáveis de folga:
maximizar z = 4 x1 + x2
sujeito a: 2 x1 + 3 x2 + f1 = 12
 2 x1 + x2 + f2 = 8
 x1, x2, f1, f2 <0
Vamos montar um quadro para ordenarmos as operações, colocando nele apenas os coeficientes das variáveis. No caso da função objetivo, vamos realizar a seguinte transformação: 
de: z = 4 x1 + x2 
para: z - 4 x1 - x2 = 0
Quadro 1
	Base
	x1
	x2
	f1
	f2
	b
	f1
	2
	3
	1
	0
	12
	f2
	2
	1
	0
	1
	8
	z
	-4
	-1
	0
	0
	0
A última coluna corresponde aos termos independentes das equações, e a última linha contém os coeficientes das variáveis na função objetivo. Nessa última linha teremos sempre a contribuição que cada variável dá para o lucro total z, por unidade, em cada iteração do processo de solução. Essa última linha será chamada de função objetivo transformada, ou função z-transformada.
a) Solução inicial
A solução inicial para o problema será sempre obtida fazendo as variáveis originais do modelo (no caso x1 e x2) iguais a zero e achando o valor das demais.
Assim, fazendo x1 = x2 = 0 (variáveis não básicas), obtemos do Quadro 1:
f1 = 12
f2 = 8 (variáveis básicas)
z = 0
As variáveis básicas estão indicadas no Quadro 1, para facilitar o acompanhamento das operações.
b) Segunda solução
Como a primeira solução claramente não é a melhor, vamos procurar outra que dê um valor maior para z. O problema é descobrir:
Das duas variáveis não básicas (nulas) na primeira solução, qual deve se tornar positiva?
Das duas variáveis básicas (positivas) na primeira solução, qual deverá ser anulada?
Qual variável deverá se tornar positiva?
Vamos observar que na última linha do Quadro 1 temos os coeficientes da função objetivo que mostram a contribuição para o lucro z de cada unidade produzida de mesa (x1) e de armário (x2).
Assim, aplicando o critério de que devemos produzir primeiro o produto que mais contribui para o lucro, vamos começar a produção pela variável x1, já que sua contribuição unitária para o lucro (4) é maior que a contribuição de x2, igual a 1.
Logo, a variável que deverá se tornar positiva é x1.
Qual variável deverá ser anulada?
Nota-se pelo Quadro 1 que, na primeira equação, o maior valor possível de x1 é 6, quando f1 for igual a zero (note que x2 vale zero por ser variável não básica). Qualquer valor maior de x1 fará com que o valor de f1 fique negativo, o que não é permitido. Na segunda equação, o maior valor permitido para x1 é 4, quando f2 for igual a zero. Analisando simultaneamente as duas equações, percebe-se que o maior valor possível para x1 é 4, já que atende às duas equações.
Observe que esta análise pode ser feita diretamente do Quadro 1, através da divisão dos elementos da coluna b pelos correspondentes elementos da coluna x1. O menor quociente indica, pela linha em que ocorreu, qual a variável básica que deve ser anulada. Assim, como o menor quociente é dado pela divisão 8 / 2 = 4, a variável básica a ser anulada é f2, que é a variável positiva na atual solução, cujo valor foi encontrado na segunda linha.
Assim temos:
x2 = 0
f2 = 0
e o sistema restante deve ser resolvido para acharmos o valor de x1 e f1. A solução desse sistema será feita usando o Quadro 1 com as equações completas e usando as operações válidas com as linhas da matriz.
1ª operação: Dividir a segunda linha por 2 (L2 =L2 / 2)
Quadro 1A
	Base
	x1
	x2
	f1
	f2
	b
	f1
	2
	3
	1
	0
	12
	x1
	1
	1/2
	0
	1/2
	4
	z
	-4
	-1
	0
	0
	0
2ª operação: Multiplicar a segunda linha do Quadro 1A por (-2) e somar com a primeira linha do mesmo quadro, colocando o resultado na primeira linha (L1 L1 - 2 L2)
Quadro 1B
	Base
	x1
	x2
	f1
	f2
	b
	f1
	0
	2
	1
	-1
	4
	x1
	1
	1/2
	0
	1/2
	4
	z
	-4
	-1
	0
	0
	0
3ª operação: Multiplicar a segunda linha do Quadro 1B por (4) e somar com a terceira linha do mesmo quadro, colocando o resultado na terceira linha (L3 =L3 + 4 L2)
Quadro 2
	Base
	x1
	x2
	f1
	f2
	b
	f1
	0
	2
	1
	-1
	4
	x1
	1
	1/2
	0
	1/2
	4
	z
	0
	1
	0
	2
	16
Como a última linha (função z-transformada) mostra as contribuições líquidas para o lucro, caso as variáveis x1 e f2 venha a ter seus valores aumentados de 0 para 1 e como estas contribuições têm seus valores trocados com relação ao quadro original, concluímos que a solução encontrada é ótima.
x1 = 4,
x2 = 0,
f1 = 4,
f2 = 0 e
z = 16
4.3 Procedimento do Método Simplex (Problemas de Maximização)
Passo 1: Introduzir as variáveis de folga; uma para cada desigualdade.
Passo 2: Montar um quadro para os cálculos, colocando os coeficientes de todas as variáveis com os respectivos sinais e, na última linha, incluir os coeficientesda função objetivo transformada.
Passo 3: Estabelecer uma solução básica inicial, usualmente atribuindo valor zero às variáveis originais e achando valores positivos para as variáveis de folga.
Passo 4: Como próxima variável a entrar na base, escolher a variável não básica que oferece, na última linha, a maior contribuição para o aumento da função objetivo (ou seja, tem o maior valor negativo). Se todas as variáveis que estão fora da base tiverem coeficientes nulos ou positivos nesta linha, a solução atual é ótima. Se alguma dessas variáveis tiver coeficiente nulo, isto significa que ela pode ser introduzida na base sem aumentar o valor da função objetivo. Isso quer dizer que temos uma solução ótima, com o mesmo valor da função objetivo.
Passo 5: Para escolher a variável que deve deixar a base, deve-se realizar o seguinte procedimento:
a) Dividir os elementos da última coluna pelos correspondentes elementos positivos da coluna da variável que vai entrar na base. Caso não haja elemento algum positivo nesta coluna, o processo deve parar, já que a solução seria ilimitada.
b) O menor quociente indica a equação cuja respectiva variável básica deverá ser anulada, tornando-se variável não básica.
Passo 6: Usando operações válidas com as linhas da matriz, transformar o quadro de cálculos de forma a encontrar a nova solução básica. A coluna da nova variável básica deverá se tornar um vetor identidade, onde o elemento 1 aparece na linha correspondente à variável que está sendo anulada.
Passo 7: Retornar ao passo 4 para iniciar outra iteração.
4.4 Outro Exemplo
Vamos resolver pelo método Simplex o problema das rações proposto no Capítulo 1, cujo modelo foi apresentado no Capítulo 3.
Maximizar Z = 11 x1 + 12 x2
Sujeito a: x1 + 4 x2 <10000
 5 x1 + 2 x2 <30000
 x1, x2 <0
a) Inclusão das variáveis de folga
Com a inclusão das variáveis de folga, o problema torna-se:
Maximizar Z = 11 x1 + 12 x2
Sujeito a: x1 + 4 x2 + f1 <10000
 5 x1 + 2 x2 + f2 < 30000
 x1, x2, f1, f2 < 0
b) Solução inicial
	Base
	x1
	x2
	f1
	f2
	b
	f1
	1
	4
	1
	0
	10000
	f2
	5
	2
	0
	1
	30000
	z
	-11
	-12
	0
	0
	0
c) Primeira iteração
Variável a entrar na base: x2 (coluna com maior valor negativo na última linha)
Variável a sair da base: f1 (o quociente 10000/4 é o menor quociente entre a última coluna e a coluna da variável x2, que vai entrar na base).
L1 =L1 / 4
L2 =L2 - 2 L1
L3 =L3 + 12 L1
	Base
	x1
	x2
	f1
	f2
	b
	x2
	1/4
	1
	1/4
	0
	250
	f2
	4,5
	0
	-1/2
	1
	25000
	z
	-8
	0
	3
	0
	30000
d) Segunda iteração
Variável a entrar na base: x1 (coluna com maior valor negativo na última linha)
Variável a sair da base: f2 (o quociente 25000/ 4,5 é o menor quociente entre a última coluna e a coluna da variável x1, que vai entrar na base)
L2 =L2 / 4,5
L1 =L1 - L2 / 4
L3 =L3 + 8 L2
	Base
	x1
	x2
	f1
	f2
	b
	x2
	0
	1
	0,2778
	-0,0556
	111,11
	x1
	1
	0
	-0,1111
	0,2222
	5555,56
	z
	0
	0
	2,1111
	1,7778
	74444,44
e) Solução ótima encontrada
Como todos os valores da última linha (função z-transformada) são positivos ou nulos, concluímos que a solução encontrada é ótima, ou seja:
x1 = 5555,55
x2 = 1111,11
z = 74444,44
Exercícios sobre Método Simplex:
Um empregado decidiu comercializar barcos. Depois de empregar alguns trabalhadores e de descobrir os preços aos quais venderia nos modelos, chegou às seguintes observações. Cada modelo comum rende um lucro de R$ 520,00 e cada modelo rápido rende um lucro de R$ 450,00. Um modelo rápido requer 40 horas para ser construído e 24 horas para o acabamento. Cada modelo rápido requer 25 horas para ser construído e 30 horas para o acabamento. Este empregador dispõe de 400 horas de trabalho por minuto para construção e 360 horas por mês para acabamento. Quanto deve produzir de cada modelo de maneira a maximizar o lucro?
2) Encontre a solução ótima da seguinte problema de programação linear testando o valor da função objetivo em cada um dos pontos abaixo descritos:
 	a) Max Z = 20 x1 + 40 x2
Restrições: x1 + x2 ≤3
 2x + x2 ≤5
 4x 1 + x2 ≤12
 x1, x2 ≥0
Max => Z = 12x + 4y
Restrições: x + 2y <800
 x + 3y <600
	 2x +3y <200	
 x, y ≥0
Uma marcenaria deseja estabelecer uma programação diária de produção. Atualmente, a oficina faz apenas dois produtos: mesa e armário, ambos de um só modelo. Para efeito de simplificação, vamos considerar que a marcenaria tem limitações em somente dois recursos: madeira e mão de obra, cuja disponibilidade diária é mostrada na tabela a seguir:
	Recurso
	Disponibilidade
	Madeira
	12 m2
	Mão de obra
	8 H.h (homens /hora)
 O processo de produção é tal que, para fazer uma mesa e fabrica gasta 2 m2 de madeira e 2 H. h de mão de obra. Para fazer o armário, a fábrica gasta 3 m2 de madeira e 1 H.h de mão de obra. Além disso, o fabricante sabe que cada mesa dá uma margem de contribuição para o lucro de $4 e cada armário de $1. Encontre a margem que maximinize o lucro.
A Óleos Unidos S.A. é uma empresa do ramo de derivados de petróleo que manufatura três combustíveis especiais com base na mistura de dois insumos: um extrato mineral e um solvente. No processo de produção não existe perda do material, de forma que a quantidade de litros de extrato mineral somada a quantidade de litros de solvente utilizada para a fabricação de um tipo de combustível resulta no total de litros daquele combustível. A proporção da mistura está descrita na tabela a seguir:
	
	Combustível A
	Combustível B
	Combustível C
	Extrato Mineral
	8 litros
	5 litros
	4 litros
	Solvente
	5 litros
	4 litros
	 2 litros
Suponha que a Óleos Unidos S.A. tenha disponíveis 120 litros de extrato mineral e 200 litros de solvente, e que os lucros líquidos esperados para os três combustíveis sejam de R$ 20,00, R$ 22,00 e R$ 18,00, respectivamente. Responda:
Estabeleça um modelo de programação linear que determine a quantidade de cada combustível a ser fabricada, dadas as restrições de matéria primas.
Quanto de cada produto deve ser manufaturado de modo a maximizar o lucro da companhia? De quanto é esse lucro? (Utilize o método simplex)
5) Um pequeno entregador pode transportar madeira ou frutas em seu carrinho de mão, mas cobra R$ 20,00 para cada fardo de madeira e R$ 35,00 por saco de frutas. Os fardos pesam 1 kg e ocupam 2 dm3 de espaço. Os fados de frutas pesam 1 kg e ocupam 3 dm3 de espaço. O carrinho tem capacidade para transportar 12 kg e 10 dm3, e o entregador pode levar quantos sacos e fardos desejar. Resolva o problema pelo método simplex e determine qual será o lucro do entregador e como ele deve preencher o seu carrinho. 
Uma pequena malharia produz dois tipos de camisas: de manga curta e de manga comprida. Toda a produção feita é vendida para um distribuidor, que compra tudo o que é produzido. A confecção de cada camisa passa por três seções de trabalho: corte, costura e acabamento. A tabela 1 mostra os tempos necessários em cada seção:
Tabela 1
	Tempo de fabricação de uma camisa em cada seção
	Produto
	Tempo de fabricação (em horas)
	
	Corte
	Costura
	Acabamento
	Manga Curta
	3
	1,5
	5
	Manga Comprida
	3
	3
	3
A tabela 2 mostra a quantidade de horas por semana em cada seção de trabalho.
	Limites de capacidade de fabricação
	Seção de trabalho
	Homens/ horas por semana
	Corte
	210
	Costura 
	160
	Acabamento
	330
 Tabela 2
 
Determine a quantidade de cada tipo de camisa que deve ser fabricada de forma a maximizar o lucro da empresa sabendo que o lucrounitário proporcionado pela camisa de manga curta é de R$ 2,00 e o proporcionado pela de manga comprida é de R$ 3,00. Faça através do método simplex.
7) Uma empresa de móveis de cozinha fabrica três tipos de meses de fórmica: quadrada, retangular e redonda. Cada mesa passa por dois processos: de produção e de acabamento. A tabela a seguir resume o número e horas requeridas por mesa em cada um dos processos, bem como o lucro unitário de cada mesa. A partir desses dados utilize o método simplex para achar a solução ótima a fim de maximizar os lucros da produção. 
	Modelo de mesa
	Produção
	Acabamento
	Lucro unitário
	Quadrada
	2 horas
	2 horas
	30
	Retangular
	3 horas
	2 horas
	60
	Redonda
	4 horas
	2 horas
	80
	Total semanal disponível
	1.000 horas
	600 horas
	-
 
8) Considere uma fábrica de rádios que possui duas linhas de produção: 
Rádios Standard (RS); Rádios Luxo (RL). A tabela de produtividade fornece as seguintes informações: 
	
	Máximo de funcionários na linha de produção
	Mão-de-obra empregada na produção (homem/dia/unidade)
	Lucro unitário (R$)
	RS
	24
	1
	30,00
	RL
	32
	2
	40,00
A fábrica possui um total de 40 funcionários a serem alocados nas duas linhas de produção. Maximize os lucros diários através do método simplex. 
9) A SugarCo S.A. produz três tipos de barras de chocolate industriais, todas consistindo exclusivamente de açúcar e chocolate. A composição e lucro relacionado a cada uma desses produtos, bem como a disponibilidade de matérias-primas vêm dados abaixo. Formule o problema de forma a maximizar os lucros da empresa. 
	
	Quantidade de açúcar (Kg)
	Quantidade de Chocolate (Kg)
	Lucro ($)
	Produto 1
	1
	2
	3
	Produto 2
	1
	3
	7
	Produto 3
	1
	1
	5
	Disponibilidade
	50
	100
	
10) A Brinquedos S.A. fabrica dois tipos de brinquedos de madeira: soldados e trens. Um soldado é vendido por R$27 e usa R$10 de matéria-prima. Cada soldado fabricado aumenta os custos diretos de mão-de-obra e custos indiretos em R$14. Um trem é vendido a R$21 e utiliza R$9 de matéria-prima. Cada trem aumenta os de mão-de-obra e indiretos em R$10. A fabricação requer dois tipos de mão-de-obra: carpinteiro e pintor. A fabricação de um soldado requer 2h de um pintor e 1 h de carpinteiro. Um trem demanda 1hora de pintura e 1h de carpintaria. Para cada semana, a Brinquedos pode conseguir toda a matéria-prima necessária, mas apenas 100h de pintura e 80h de carpintaria. A demanda para os trens é ilimitada, mas a de soldados é de no máximo 40 por semana. Resolva pelo método simplex.
MÉTODO DE TRANSPORTE
Um problema bastante comum que muitas vezes pode ser modelado como um 
problema de programação linear é o problema de transporte. Este problema 
envolve o transporte de alguma carga de diversas fontes a diversos pontos de 
destino. Dados o custo da distribuição entre cada fonte e destino, as produções das 
fontes e as capacidades dos destinos, pretendem-se minimizar o custo total do 
transporte. A estrutura geral de um problema de transporte pode ser vista da seguinte maneira: suponhamos três fontes de um determinado produto e três destinos para os quais ele deve ser transportado, conforme figura abaixo, devemos programar o transporte em cada uma das rotas indicadas de forma a minimizar o custo total calculado sobre todas as rotas. 
Uma das situações que caracterizam um problema de transporte é encontrada por uma empresa que tem fábricas localizadas em algumas cidades e depósitos em outra e deve determinar um programa de transporte de forma a satisfazer a demanda por seus produtos, respeitar a capacidade das fábricas e dos depósitos e minimizar seus gastos com transporte. Resumidamente, uma rede de transporte liga origens aos destinos e o objetivo principal é procurar o carregamento das rotas que minimiza o custo total. 
Um Exemplo de Problema de Transporte 
Seja o processo de produção, transporte e depósito 
Exemplo de um problema de transporte, com 3 fontes e 3 destinos 
Os custos de transporte Cij, da fonte i para o destino j são apresentados na Tabela 
	Custos unitários de transporte para o exemplo de problema de transporte 
 
Formulando o problema por programação linear, define-se como objetivo a minimização do custo total de transporte, ou seja: 
Como se trata de um problema típico de programação linear, ele pode ser resolvido pelo método Simplex. Entretanto, técnicas específicas para este tipo de problema podem resolvê-lo de forma mais rápida que o Simplex. 
Método de Stepping-Stone
O método de stepping-stone chega à solução ótima partindo se uma solução inicial e pesquisando se alguma solução melhor pode ser obtida. Como o método parte de uma solução inicial, devemos encontrar uma solução viável qualquer para poder utilizar o método. 
A solução do problema se torna mais cômoda se os dados forem representados em um quadro 
 
Solução básica inicial - Método do mínimo custo Este método consiste nos seguintes passos: 
Atribuir o máximo possível à variável com menor custo unitário e preenche com zeros a linha ou coluna satisfeita. 
No exemplo, faz-se x31 = 80 já que c31 = 3, utilizando completamente o fornecimento da Fonte 3. Desta forma, x32 e x33 devem ser iguais a 0. Ajustar os elementos da linha ou coluna não ajustada a partir da variável com menor custo. 
No exemplo, na primeira coluna temos que fazer x11 = 70 (menor custo unitário), de forma a atender a capacidade do Destino 1. Logo, x21 deve ser igual a 0. O processo é repetido para as variáveis com outros custos, em ordem crescente. Dessa forma, devemos fazer x12 = 50, de forma a completar o fornecimento da Fonte 1, 
zerando assim a variável x13. Para completar o quadro, devemos definir x22 = 20 (capacidade do Destino 2) e x23 = 60. 
 
Obs: O número de variáveis básicas (células preenchidas) tem que ser m + n -1, do 
	contrario o processo trava. Onde “m” é o numero de origem (fábrica) e “n” é o destino (depósito) 
m = 3 e n = 3, 	3 + 3 -1 = 5 que é igual a quantidade de variáveis básicas 
Sabendo que z = 8 x11 + 5 x12 + 6 x13 + 15 x21 + 10 x22 + 12 x23 + 3 x31 + 9 x32 + 10 x33 
Custo total do transporte é: 
C1= 8x70 + 5x50 + 6x0 + 15x0 + 10x20 + 12x60 + 3x80 + 9x0 + 10x0 = 1970 
Processo Iterativo
Cada célula vazia representa uma variável não básica que poderia entra na base. 
Para entrar, a contribuição da variável não básica deve implicar a redução do custo 
total. Calculando essas contribuições 
Aloque 1 unidade em uma célula não básica. 
Calculando a contribuição para célula x13. Assim, não são mais 60, mas 61 o total de unidades na coluna 3. 
Não se deve violar as restrições das colunas nem das linhas. 
Para não violar a restrição da coluna 3, uma unidade deverá ser subtraída de x23, que passa a ter 59 unidades, e a coluna 3 com um total de 60 novamente. 
Agora a linha 2 totaliza 79 e não 80, o que pode ser corrigido com a adição de uma unidade a x22 (20 ->21). 
A coluna 2 fica então com um total de 71, o que pode ser corrigido com a subtração de uma unidade de x12. 
A linha 1 é automaticamente corrigida em função do passo anterior. 
Para cada variável zerada, devemos determinar um caminho fechado de forma a calcular a sua contribuição na função objetivo. Estes caminhos são definidos por linhas verticais ou horizontais, delimitando um polígono fechado. Apenas em um vértice deste polígono deve haver uma variável zerada, que é a própria variável não básica que será incluída na base. Só é possível formar um único caminho com essas características para cada variável zerada. 
Encontrado o caminho mínimo da variável, sua contribuição é calculada alternando soma e subtração dos custos unitários dos vértices, começando da variável a ser incluída na base. 
Vamos agora calcular a contribuição de cada variável não básica na função objetivoComo é um problema de minimização, a variável a entrar na base será aquela que contribui com a maior redução no valor da função objetivo, que é a variável x13. 
O valor a ser alocado a esta célula deve ser o máximo, de modo que nenhuma das variáveis fique com valor negativo. Este valor é o menor valor das variáveis que estão nos vértices do caminho mínimo com sinal negativo. No caso, as variáveis com sinal negativo são x12 e x23. Logo, o valor a ser alocado é 50. 
As demais variáveis vão adicionar ou subtrair 50, conforme o sinal do vértice correspondente à variável seja positivo ou negativo. Ou seja, as variáveis passarão a ter os seguintes valores: 
 x13 =0 + 50 = 50;
x23 = 60 - 50 = 10;
x22 = 20 + 50 = 70;
x12 = 50 - 50 =0.
 Logo, a variável que sai da base é x12.
O quadro após a primeira iteração: 
 
Custo total do transporte é: 
C2= 8x70 + 5x0 + 6x50 + 15x0 + 10x70 + 12x10 + 3x80 + 9x0 + 10x0 = 1920 
Recalculando as contribuições de cada variável não básica na função objetivo, temos que:
Como todas as variáveis têm contribuição positiva, isto indica que a inclusão de qualquer uma delas fará aumentar o valor da função objetivo, portanto a solução encontrada é ótima. 
Outro exemplo: 
Procedimentos de solução através do Método de stepping-stone
A solução se torna mais cômoda se os dados forem representativos em um quadro, como mostra a figura abaixo: 
Um dos métodos usados para proceder a solução é chamado de stepping-stone. Esse método chega à solução ótima partindo se uma solução inicial e pesquisando se alguma solução melhor pode ser obtida. Como o método parte de uma solução inicial, devemos encontrar uma solução viável qualquer para poder utilizar o método. 
Passo 2: Teste de otimalidade e determinação da variável que entra na base
Para verificarmos se essa solução é ótima, podemos realizar uma análise da variação do custo total causada por variações unitárias nas variáveis que estão fora da base, ou seja, x11 e x22.
Para a variável x11, o procedimento é o seguinte:
Dar um aumento unitário à variável x11, ou seja, fazer x11 passar de 0 para 1;
Para manter o ajustamento da solução, diminuir x12 de 1, aumentar x22 de 1 e diminuir x21 também em 1. A figura y a seguir mostra essas variações.
Em função dessas variações, calcular a variação no custo total do transporte. 
 
 
Figura y
Logo, como a variação no custo total causada pela variação unitária em x11 foi positiva, não será compensador transportar o produto por essa rota, já que o custo final aumentaria. Para a variável x22, teríamos a seguinte situação, conforme a figura x.
 
Figura x: Ajuste da solução para variação em x22.
Conclusão: Nesse caso, a variação no custo total foi nula, o que significaria que a solução obtida é ótima, já que tínhamos obtido uma variação em Z positiva em x11. No entanto, como a variação para x22 é igual a zero, temos outra solução básica com x22 na base. 
Dificuldades do Problema de Transporte
Não balanceamento entre oferta e demanda. Caso isso ocorra, o problema não pode ser resolvido da maneira apresentada. Deve-se então criar uma origem ou destino fictício para que o problema esteja balanceado. 
Para o problema inicial, se a produção total for maior que a capacidade total, criar um depósito fictício com capacidade = produção total - capacidade total, com custos de distribuição nulos. Se a produção total for menor que a capacidade total, criar uma fábrica fictícia. 
Problemas Propostos de Método de Transporte
Uma companhia locadora de automóveis se defronta com um problema de alocação resultante das contratas de locação que permitem sejam automóveis devolvidos em localidades outras que aquelas onde foram originalmente alugados. No presente momento há duas agencias de locação (origens) com respectivamente, 15 e 13 carros excedentes e quatro outras agencias (destinos) necessitando de 9, 6, 7 e 9 carros, respectivamente. Os custos unitários de transportes (em dólares) entre as locadoras são as seguintes:
2) Uma companhia aérea regional pode comprar seu combustível para jato a partir de qualquer um dentre três fornecedores. As necessidades da companhia aérea para o mês entrante em cada um dos três aeroportos em que ela opera são: 100.000 galões no aeroporto 1; 180.000 galões no aeroporto 2 e 300.000 galões no aeroporto 3. Cada fornecedor pode abastecer cada um dos aeroportos de acordo com os preços (em cents por galão) dados na seguinte tabela a seguir: 
 
Cada fornecedor, contudo, está limitado pelo número total de galões que ele pode abastecer por mês. Estas capacidades são 320.000 galões para o fornecedor 1; 270.000 galões para o fornecedor 2 e 150.000 galões para o fornecedor 3. Determine a política de aquisição que suprirá as necessidades da companhia em cada aeroporto a um custo total mínimo. 
3) Resolva por Transporte
4) Resolva por Método de Transporte:
Professora: Adriane Guarienti
emails: adrig.sm@terra.com.br
adriane@unifra.br
_1341565691.unknown
_1341566488.unknown
_1341568053.unknown
_1341568617.unknown
_1341568944.unknown
_1341569191.unknown
_1341569599.unknown
_1341572159.unknown
_1382186593.unknown
_1341572151.unknown
_1341569192.unknown
_1341569169.unknown
_1341568804.unknown
_1341568914.unknown
_1341568762.unknown
_1341568365.unknown
_1341568512.unknown
_1341568337.unknown
_1341567735.unknown
_1341567940.unknown
_1341568020.unknown
_1341567939.unknown
_1341567579.unknown
_1341567673.unknown
_1341567470.unknown
_1341566046.unknown
_1341566096.unknown
_1341566413.unknown
_1341566075.unknown
_1341565857.unknown
_1341565935.unknown
_1341565734.unknown
_1341564652.unknown
_1341565103.unknown
_1341565383.unknown
_1341565564.unknown
_1341565205.unknown
_1341564668.unknown
_1341564753.unknown
_1341564660.unknown
_1341564443.unknown
_1341564527.unknown
_1341564584.unknown
_1341564647.unknown
_1341564516.unknown
_1341564422.unknown