AO ESTUDO DE PESQUISA OPERACIOAL

Prévia do material em texto

APONTAMENTOS DE INTRODUÇÃO AO ESTUDO DE PESQUISA OPERACIOAL
SEBENTA COM PROBLEMAS E EXERCÍCIOS
PARTE UM PROGRAMAÇÃO LINEAR
Professor Doutor José António Fazenda
Luanda 2014
INDECE
1. INTRODUÇÃO A PESQUISA OPERACIONAL
1.1 Breve historial da Pesquisa Operacional
1.2 Modelo de IO
2. ÁLGEBRA LINEAR
2.1 Vectores
2.2 Matrizes
2.3 Sistemas de Equações lineares
3. PROGRAMAÇÃO LINEAR
3.1 Definição 
3.2 Fases de estudo de um problema de pesquisa operacional
3.3 Exemplos de problemas de P.L.
3.4 Resolução Gráfica de Problema de P.L.
3.5 Forma Padrão ou standard de um Problema de P.L.
4. O MÉTODO SIMPLEX
4.1 Exemplo de um Problema 
4.2 Método Simplex
4.3 Procedimento do Método Simplex (Problema de Maximização)
4.4 Outra forma do Método Simplex
4.5 Método Simplex em Duas Fases
4.6 Outra Forma do Método Simplex em Duas fases
4.7 Exercícios Modelados
4.8 Exercícios Resolvidos
4.9 Exercícios Proposto
5. PROBLEMA DE TRANSPORTE
5.1 Noções Gerais
5.2 Um Exemplo de Problema de Transporte
5.3 Formulação de um Problema de Transporte
5.4 Arranjos a forma genérica 
5.5 Propriedade do Modelo de Transporte
5.6 Método de stepping-Stone
5.6.1 O método do custo mínimo por linha
5.6.2 O método do custo mínimo por coluna
5.6.3 Desenvolvimento do método stepping-stone
5.7 Dificuldades do Problema de transporte
5.8 Exercícios para resolver
6. ANÁLISES DE REDE
6.1 Conceito Básico em Teoria de Grafos
6.2 O Problema da Árvore Geradora de Custo Mínimo 
6.2.1 O Algoritmo de Kruskal
6.2.2 O Algoritmo de Pri-
6.3 O problema do caminho mais curto
6.3.1 O algoritmo de DIJKSTRA
6.3.2 Outra forma de Resolver o Problema 
6.3.3 O algoritmo de Ford
6.3.4 O algoritmo de Floyd
6.3.5 O problema do Fluxo Máximo
6.3.6 Corte de uma Rede 
6.3.7 O algoritmo de Ford – Fukerson
6.3.8 Resolução de Problema
6.3.9 Casos especiais do Fluxo Máximo 
6.3.10 O Problema do Fluxo de Custo Mínimo 
6.3.11 Situação
6.3.12 Formulação do problema
6.3.13 O algoritmo de BUSACRER – GOWEN
6.3.14 Exercícios Proposto
7. TEORIA DOS JOGOS
7.1 Introdução 
7.2 Jogo de dois Jogadores e Soma Zero
8. RISCO E INCERTEZA
8.1 Conceito de Risco
8.2 Critério para decisão sob condições de incerteza
1. INTRODUÇÃO A PESQUISA OPERACIONAL
Muitos dos problemas actuais baseiam-se em escolher uma alternativa, a melhor entre, muitas ou seja, a tomada de decisão. A pesquisa operacional (PO) é um dos ramos da matemática que utiliza processos numéricos de chegar a melhor alternativa.
Pesquisa Operacional = Investigação das Operações.
Operação = Conjunto de actos necessários para obter determinados resultado. 
Investigação = Pesquisa que conduz o resultado que são imediatamente utilizáveis fora do domínio da ciência (na vida real); ou seja procura resolver um problema e alguns dos objectivo a atingir são de natureza não científica.
Objectivo de Ensino da P.O.
A P.O. é a ciência aplicada vocacionada na resolução de um problema da vida real, nos quais se procura trazer para o campo da tomada de decisão (sobre a concepção a planificação ou a operação de sistema) a altitude e os métodos próprios de outras áreas cientificas. 
Através de desenvolvimento de base quantitativa, a PO visa também introduzir elementos de objectividade e racionalidade nos processos de tomada de decisão sem descurar no entanto os elementos subjectivos e de enquadramentos organizacional que caracterizam os problemas.
Diz-se que um individuo (ou um grupo) tem um problema se e só se:
· Deseja atingir determinados objectivos,
· Possui modos alternativos de o alcançar
· Ignorar qual a melhor alternativa.
Suponhamos por exemplo, que uma empresa dispõe de diversos recursos (matéria – prima, mão – de – obra, etc.) que os pode combinar de diversos modos para produzir certo bem. Admitindo que o problema consiste em determinar a combinação produtiva que permite obter o bem a um certo custo mínimo, pode sugerir a questão de procurar a técnica matemática mais eficaz para minimizar certo tipo de função – custo.
1.1 Breve Historial da Pesquisa operacional
A utilização de métodos científicos na preparação de decisão, remota a data muito longínquas. Por exemplo, no século III A.C. HIERÃO (tirano de Siracusa) pediu a ARQUÍMES que indicasse a forma mais eficiente de utilizar as armas da época, a fim de romper os cercos da frota romana.
No entanto, o inicio da actividade dachamada Pesquisa Operacional é atribuída, normalmente aos serviços militares durante a II guerra mundial, quando os aliados se viram confrontados com problemas (de natureza logísticas, de táctica e estratégia militar) de grande dimensão e complexidade. Para apoiar os comandos operacionais na resolução desses problemas, foram então criados grupos multidisciplinares de cientistas em que se incluíam matemáticos, físicos e engenheiro, a par de outro oriundo das ciências sociais. Esses cientistas mas não fizeram do que aplicar o método científico, que tão bem conheciam aos problemas que lhes foram sendo colocados. Desenvolvem então a ideia de criar modelos matemáticos, apoiados em todos os factos que permitissem perceber os problemas em estudo e ensaiar e avaliar o resultado hipotético de estratégia ou decisões alternativas. Dos trabalhos realizados durante este período, destaca-se os seguintes: 
· Em 1939 na Inglaterra um pequeno grupo de técnico dedicado o PO começou a trabalhar nos métodos de emprego dos primeiros radares
· Grupo BLACKETT) para conseguir o aproveitamento óptimo do sistema defensivo britânico.
· Dois anos depois da guerra, os 3 ramos das forças armadas britânicas estavam dotados com o grupo de PO cujo efectivo não parou de aumentar ate ao final da guerra.
· Nos EUA, desde a sua entrada na guerra, grupo de PO, foram incumbidos pelo exército, marinha e força aérea de estudarem cientificamente os problemas de cada força armada, a partir dos quais se destacam resultados como a melhoria da eficiência dos ataques aéreos aos submarinos, nova disposição dos comboios marítimos, de forma a minimizar as perdas, organização dos bombardeamentos aéreos sobre Alemanha.
No fim da guerra, incentivados com o aparente sucesso da PO a nível militar os industriais começaram gradualmente a interessar-se por esse novo campo. Por outro lado, o grupo da PO gozava de merecido prestígio, uma vez que tinha ficado demonstrado, durante a guerra que as equipas da PO eram capazes de resolver problemas complexos, envolvendo muitas variáveis, e os métodos que tinham permitido obter maior eficiência das armas e valiosa economia em vidas humanas e materiais, eram susceptíveis de serem transferidas do sector militar para o sector civil.
Os problemas eram basicamente os mesmos que foram tratados pelos militares, mas em diferente contexto. Assim embora a PO militar não tenha parado de se desenvolver, assistiu-se no período pós – guerra ao rápido crescimento da PO civil (nas industrias nos negócios e no sector publico) no sentido de criarem métodos de gestão racionais.
Podem identificar-se pelo menos dois factores, que tiveram um papel essencial no rápido crescimento da PO durante esse período:
i. Substancial progresso das técnicas matemáticas disponível na PO.
Depois da guerra, vários cientistas sentiam-se motivados em procurar relevante investigação no campo, resultados aqui avançados importante na área. O primeiro caso é o método de simplex para resolver problemas de programação linear desenvolvido por George Dantzig em 1947.
ii. Evolução /revolução dos computadores. Normalmente é exigido uma grande quantidade de cálculos para tratar mais eficientemente, os problemas complexos considerados típicos pela PO.
No entanto, o desenvolvimento dos computadores com as capacidades para realizar cálculos aritméticos de milhares ou mesmo de milhões vezes mais rápido do que o homem e trabalhar enormes volumes de dados sobre as actividades das empresas, foi uma tremenda vantagem da PO. Hoje todo tipo de computador soa essenciais para resolver problemas de PO do mundo.
Perante um fenómeno, não é geralmente fácil prever qual das disciplinas científicas serão mais adequadaspara o seu estudo. Mas ainda é geralmente duvidoso que o estudo eficiente de um fenómeno que possa realizar no quadro restrito de um só disciplina. Como consequência esboça-se actualmente para se encararem os fenómenos da multiplicidade dos seus aspecto. Esta atitude não significa que se abandone a especialização, indispensável para o progresso em profundidade do conhecimento, mas sim que a investigação dos fenómenos reais tende progressivamente a assumir carácter multidisciplinar, sendo realizadas por equipas de cientistas com diferentes especializações – o carácter multidisciplinar permite encarar os problemas sob a multiplicidade dos seus aspectos.
Face ao seu carácter multidisciplinar, a PO é uma disciplina científica de características horizontais, estende os seus atributos por praticamente todos os domínios da actividade humana, desde a engenharia a medicina, passado pela economia e a gestão.
Uma outra característica é que a PO tenta encontrar a melhor solução (ou ótima) do problema; isto é, o objectivo de identificar a melhor acção possível – procura de otimização.
Resumindo a PO esta relacionada com a tomada de decisões óptimas e em modelação do sistema determinístico e probabilístico, que tem origem na vida real. Assim, a PO contribui para:
· Estruturar a situação da vida real em modelos matemáticos que obtêm os elementos essenciais de modo a que possa ser procurada uma solução relevante para os objectivos do decisor; isto implica examinar o problema no contexto do sistema total.
· Explorar a estrutura destas soluções e desenvolver procedimentos sistemático para os obter desenvolver uma solução que produz o melhor valor para a medida de satisfação do sistema (ou comando opções alternativas através do calculo da sua medida de satisfação)
1.2 MODELO DE PO
É suposto que um modelo seja uma representação suficientemente precisa de características essências da situação a analisar (da realidade) de modo que as conclusões (soluções) obtida a partir dele sejam também validas para o problema real.
O modelo é um esquema simplificado para a interpretação da realidade. Em consequência da complexidade do mundo real, é necessário formular modelos simplificados que levem a compreensão de certos fenómenos. A mera acumulação de observação não pode oferecer explicação satisfatória do fenómeno e, portanto, o investigador tem a necessidade de sistematizar e racionalizar os factos conhecidos, seleccionando os aspectos mais importantes e desprezando os que considera irrelevante. Existem 3 tipos de modelos:
· Icónicos: São representações reduzidas de estado, objectos ou acontecimentos. Representam o fenómeno real apenas com uma transformação de escala.
· Analógico: Em se entrega uma propriedade para representar outra. Por exemplo utiliza gráficos a cores e com legendas.
· Simbólicos: São aqueles em que as propriedades dos fenómenos reais são expressas simbolicamente como é o caso dos modelos matemáticos.
Os modelos matemáticos são também apresentadas idealizadas, mas expressas em termos de símbolos e expressões matemáticas. Este modelo consiste num sistema de equações e de expressões matemáticas relacionada, que descrevem os aspectos essenciais do problema.
Os modelos matemáticos utilizados na PO são técnicas quantitativas que formam a parte principal do que é conhecido acerca da PO no entanto, muitas vezes as análises matemáticas representam apenas uma parte relativamente pequena do esforço total exigido.
PROGRAMAÇÃO LINEAR
3.1. Definição
 A programação linear é uma técnica da PO. Esta denominação se atribui porque considera-se que as restrições e as condições impostas aos problemas tratados são expressas em termos Lineares.
Ela consiste em dispor os dados de um problema cujas incógnitas guardam relações lineares, sob a forma de um sistema de equações e/ou inequações composto de uma equação chamada funçãoobjectivo para qual deseja-se obter um resultado óptimo (máximo ou mínimo) sujeito a restrições ou condicionamentos, constituído por várias equações ou inequações.
Quando o número de incógnitas é igual a 2 ou 3 o sistema admite uma solução gráfica. Muito complicada no segundo caso por se tratar de um problema no espaço tridimensional. Os problemas com 4 ou mais incógnitas pertencendo a um espaço n-dimensional só admitem soluções algébricas através do cálculo matricial.
Os três principais grupos de problemas que podem ser resolvidos por Programação Linear são:
Misturas de ingredientes com composição e preços conhecidos para atenderem a determinadas especificações (de composição ou de estoque) a custo mínimo ou lucro máximo: Rações balanceadas para animais, refeições, abastecimento de comunidades ou tropas, combustíveis e lubrificantes, fertilizantes e correctivos, defensivos agrícolas, perfumes e cosméticos, ligas metálicas, Industria de alimentos, etc.
Transporte, distribuição ou alocação, em que se procura determinar as quantidades a transportar segundo as vias alternativas possíveis a frequência ou períodos de transporte e as especificações quanto a operação levando em conta os custos (fretes, riscos de capital empatado, prémios e multas, embalagem, armazenamento, capacidade dos meios, etc.…). A política de Transporte e o factor a maximizar ou minimizar (custos, quantidades, tempo, etc.…). Entre as áreas de utilização cita-se: abastecimento, distribuição de produtos, transporte de cargas ou pessoas, etc..
Programas de Produção ou limitação de recursos nos sectores agrícolas, industrial ou de serviços.
3.2. FASES DE ESTUDO EM PO (para a resolução de um problema)
1. Formulação do problema;
2. Construção do modelo matemático;
3. Cálculo da solução através do modelo;
4. Avaliação do modelo e da solução;
5. Tomada de decisão sobre a solução encontrada;
6. Implementação e acompanhamento:
Formulação do Problema:
 Nesta fase, o problema é analisado a partir de um sistema integrado, no sentido de coloca-lo de maneira clara e coerente, definindo os objectivos a alcançar e quais os possíveis caminhos alternativos para que isso ocorra.
Além disso, serão levantadas as limitações técnicas do sistema e as relações desse sistema com outros, com a finalidade de criticar a validade de possíveis soluções em face destes obstáculos.
Formulação de um problema de PL
Deve determinar os objectivos adequados, as restrições necessárias, as inter-relações entre as área a estudar e outras áreas afins, a possível acção alternativa, o tempo limite para produzir uma decisão, etc.
A formulação inicial deve ser continuamente reexaminada, à luz de novos conhecimentos obtidos durante as ultimas fases.
NOTA: É muito difícil procurar uma solução certa para um problema mal formulado
Construção do Modelo matemático 
Um modelo matemático de um problema de optimização é representado por um sistema de equação ou inequação.
Que represente os aspectos essenciais do problema. Os modelos, ou representações idealizadas, são uma parte integral, do dia-a-dia.
A estrutura modelo matemático é a seguinte:
· Variáveis de decisão – correspondem as quantidade de decisões a serem tomadas e cujo os valores são os que se pretendem determinar.
· Função objectiva - corresponde a medida de rendimento apropriado (por exemplo, custo) e é expressa por uma função matemática envolvendo as variáveis de decisão e os pesos atribuir a cada uma delas,
· Restrições – correspondem as limitações impostas nos valores das variáveis de decisão que irão ser determinados; são também expressas matematicamente (normalmente através de inadequações ou equações); os parâmetros são as constantes presentes nas restrições (coeficiente da parte direita das restrições).
 Um tipo importante de modelos matemáticos é o modelo de programação linear (PL), onde as funções matemáticas aparecem nas funções objectivo e nas restrições são lineares.
O modelo matemático constitui uma ponte para a utilização de técnicas matemáticas muito poderosa e da informática para analisar o problema. De facto, começaram a ser utilizadas muitas aplicações de “software” associadas a modelos matemáticos,como é o caso do “Solver” 	
Quando se desenvolve o modelo, deve-se começar com uma versão muito simples, para depois evoluir-se para modelos mais elaborados e que mais de perto reflicta a complexidade do problema real. Este processo de enriquecimento de modelo contínua apenas enquanto o modelo permanecer manejável. Desta forma, o compromisso base a considerar é a entre a precisão e o manejar do modelo.
NOTA: Um passo importante na formulação de modelo matemático é a construção da função objectivo, o que exige o desenvolvimento de uma medida quantitativa de rendimento, relativo a cada objectivo que foi formulado no estudo. Se existir vários objectivos, normalmente a respectiva medida é então transformada e combinada numa medida composta denominada por medida de rendimento total. Esta medida pode ser muitas vezes evidente (por exemplo, custo) correspondendo a uma grande meta, ou pode ser abstracta (por exemplo, “utilidade”). Neste ultimo caso, a tarefa para desenvolver esta medida tende a ser um certo complexo, exigindo uma comparação cuidadosa dos objectivos e da sua importância relativa. Exprimindo esta medida com uma função matemática das variáveis de decisão.
1. Cálculo de uma solução através do modelo.
Depois da construção do modelo matemático para o problema, a etapa seguinte consiste em obter uma solução a partir do modelo. Existem 2 métodos principais para obter uma solução óptima (ou vizinha da solução óptima):
O modelo analítico – consiste em obter a solução por via dedutiva, utilizando diversos ramos da matemática.
O modelo numérico – recorre ao emprego de técnicas de cálculos que permitem obter indutivamente a solução, quer ensaiando diversos valores nas variáveis de decisão quer adoptando processos iterativos.
A fase do processo apara obtenção de uma solução são as seguintes:
a) Procura de soluções óptimas
Tem sido desenvolvido muito procedimento para determina estas soluções para certo tipo de problema. No entanto, é necessário reconhecer que estas soluções são óptimas apenas relativamente ao modelo utilizando. Uma vem que o modelo é, necessariamente mais uma idealização do que uma representação exacta do problema real, não existe garantia de que a solução óptima do modelo seja o melhor possível que possa ser incompleta no problema real. No entanto, se o modelo estiver bem formulado e testado, a solução resultante tendera a ser uma boa aproximação da acção real.
 Combinada numa medida composta denominada por medida de rendimento total. Esta medida pode ser muitas vezes evidente (por exemplo, custo) correspondendo a uma grande meta da organização, ou pode ser abstracta (por exemplo, “utilidade”). Neste ultimo caso, a tarefa para desenvolver esta medida tende a ser um certo complexo, exigindo uma comparação cuidadosa dos objectivos e da sua importância relativa. Exprimindo esta medida com uma função matemática das variáveis de decisão.
b) Optimização vs. Satisfação 
Segundo Herbert Simon, a satisfação é muito mais dominante do que é a optimização nas acções reais. Criou-se o termo satisfação com uma combinação das palavras satisfatória e optimização a distinção entre optimização e satisfação reflecte a diferença entre as teoria e as realidades, normalmente tentando implementa aquela teoria na prática. Segundo Samuel Eilon, “optimização é a ciência do ultimato; satisfação é a arte do admissível.
c) Procedimentos heurísticos para obter boas soluções óptimas 
O objectivo de um estudo da PO será conduzir o estudo numa forma óptima. Alem de procurar a optimização deve-se considerar o custo do estudo, as desvantagens da demora na sua realização, e depois tentar maximizar os benefícios líquidos resultantes do estudo. No reconhecimento deste conhecimento, utilizam-se apenas, ocasionalmente, procedimentos heurísticos (i.e., procedimentos designados intuitivamente que não garantem uma solução óptima) para encontrar uma boa solução, sub – óptima, isto é muito frequente em casos em que o tempo, ou custo, para encontrar uma solução óptima de um modelo adequado do problema deve ser muito elevado.
d) Analise pós - óptimo: análise de sensibilidade para determinar quais os parâmetros do modelo que se revelam mais críticos
Ate aqui, a discussão tem implicado que, o estudo de um problema em PO procure encontrar apenas uma solução, que pode ou exigir-se que seja óptima. De facto, normalmente este não é o caso. Uma solução óptima do modelo original pode estar longe da ideal no problema real. Por isso, a análise pós - otimal implica é uma parte muito importante da maioria dos estudos de PO. Em parte, a análise pós - otimal implica conduzir a análise de sensibilidade para determinar que parâmetros do modelo são mais críticos (os “parâmetro sensíveis”) na determinação da solução. Geralmente, alguns, ou todos, os parâmetros são uma estimativa de alguma quantidade (por exemplo, unidade de custo) cujo valor exacto tornasse-a conhecido apenas depois de a solução ter sido implementada. 
 Por isso, depois de identificar os parâmetro sensíveis. Em alguns casos, certos parâmetros de modelo representam decisões interesse (por exemplo, atribuição de recursos). Existe, então, com frequência alguma flexibilidade nos valore associados àqueles parâmetros. Talvez alguns possam ser aumentados conforme a diminuição dos outros. A análise pós -óptima inclui a investigação de tais compromissos. 
Em conjunto com o estudo da fase seguinte, a análise pós - otimal também implica uma obtenção de uma sequência de soluções que incluem uma serie de melhoramentos que se aproximam da acção ideal. Assim, as aparente fraqueza da solução inicial são utilizadas para sugerir melhoramentos no modelo, nos seus dados de entrada e, talvez, o procedimento de obtenção de uma solução. Uma nova solução é então obtida, é o ciclo contínuo, até que o melhoramento nas sucessivas soluções torne-se demasiado pequeno para justificar a continuação.
4. Avaliação do modelo e da solução: 
Nesta fase, pretende-se avaliação quer do modelo escolhido, como da solução encontrada. Dependendo da conclusão desta avaliação, determina-se o passo a seguir.
a) Avaliação satisfatória: Proceder a tomada de decisão que prepara as condições para implementação da solução encontrada, uma situação real.
b) Avaliação não satisfatória: procede-se a reformulação, remodelação e construção do novo modelo a partir dos resultados encontrados no processo de avaliação e também na análise de sensibilidade e pós – optimização.
5º Passo - Tomada de decisão sobre a solução encontrada
Concluída a etapa da avaliação, é necessário elaborar um relatório bem documentado que possibilite a implementação da solução obtida na vida real. Este relatório deve incluir o modelo e um procedimento para a tomada de decisão, o que significa, que todas acções a serem realizadas para a implementação dos resultados, devem ser incluídas numa metodologia bem detalhada com todos os passos que sejam necessário seguir para sua implementação. 
 6º Passo- Implementação
Neste passo efectua-se a implementação das soluções obtidas usando a metodologia elaborada. Neste processo, é preciso envolver activamente todos os componentes que actuam no sistema em estudo.
Depois de se terem implementado as soluções, tal como se referiu no 2º passo, pode ser necessário avançar para uma etapa mais complexa, incluindo alguns elementos novos.
Neste caso, inicia-se um novo ciclo para a resolução do problema em causa, só que agora com um nível de complexidade superior.
Maximiza (minimizar) 
Sujeito a 
. .. .. .
Onde: são os coeficiente técnicos ou tecnológicos.
são termos independente (constante da restrição ou segundos membro)
coeficiente da função objectivo (coeficiente de custo)
variáveis de decisão (principais ou controláveis)
função objectivo (economia ou critério)
 Resolução (restrições funcionais) em que apenas
Existe formas diferentes de apresentar o modelo, conforme se pretende maximizar ou minimizar, que são as seguintes: 
Se verifica uma das relações.
condições de não negatividade.Entretanto o modelo e apresentado com frequência na seguinte forma típica: 
1.3 Exemplos de problemas de programação linear
Exemplo 1. Uma empresa KOMFOR, LDA produz mobiliária de escritório e pretende lançar um modelo de secretaria estantes. Pensa-se que o mercado pode observar toda a produção de estantes, mas aconselha-se que a produçãomensal de secretaria não ultrapasse 160 unidades. Ambos os produtos são produzidos nas unidades de estampagem (EU) e de montagem e acabamento (UMA). 
A disponibilidade mensal em cada uma destas unidades é de 720 horas – maquinas na EU e 880 horas maquina na UMA. Cada escritório necessita de 2h – m na EU e 4h – m na UMA. Cada estante necessita de 4h – m na EU e 4h-m na UMA.
A margem de lucros utilitário os estimado não de 6,00 cuanzas para a secretaria 3,00 cuanzas as estantes.
PROBLEMA: Qual o plano de produção mensal para as secretaria e estantes que maximiza a margem de lucros.
1. Formalização do problema:
- Quantidade de secretaria a produzir por mês 
- Quantidades de estantes a produzir por mês 
a) Função objectiva
- Maximizar a margem bruta total por mês: 
b) Restrições
- Disponibilidade mensal de TIE.
- Disponibilidade mensal de UMA.
- Produção mensal de secretarias.
	
	SECRETARIAS
	ESTANTES
	CAPACIDADE DIPONIVEL
	UE
	2 h
	4 h
	720 h
	UMA
	4 h
	4 h
	880 h
	MERCADO
	1
	0
	160
	LUCRO
	6
	6
	
Modelação matemática
- Cada secretaria necessita de 2h (UE) pelo que o numero de horas necessária na produção de secretarias é de .
- Cada estante necessita de 4 h (EU) pelo que o numero de horas necessárias na produção estantes é de .
A disponibilidade mensal é de 720 horas.
 (
Disponibilidade em horas
) (
Total de horas gastos nas estantes
) (
Total de horas gastos na secretaria
)Logo a restrição relativa a UE é: 
	
 Algebricamente se traduz na desigualdade linear:
OBS: Estas analise e análoga para as restantes restrições. Resumindo o problema consiste em determinar de forma a maximizar a margem de lucros, isto é:
Maximizar (lucro mensal em kz)
Sujeito a (EU)
 (UMA)
 (MERCADO)
 (não negatividade)
Ex.2 Um criador de porco, pretende determinar a quantidade de cada tipo de ração a dar diariamente a cada animal, para conseguir uma dada quantidade nutritiva a custo mínimo.
Os dados relativo ao custo de cada tipo de ração, as qualidades mínima diária de cada ingrediente nutritivo básico a fornecer a cada animal, bem como as quantidades destes existentes em cada tipo de ração (j/kg) constam no seguinte quadro:
	
	Granulado (gr/kg)
	Farinha (gr. /kg)
	Quantidade mínima requerida
	Hidratos de carbono
	20
	50
	200
	Vitaminas
	50
	10
	150
	Proteínas 
	30
	30
	210
	Custo (kz/kg)
	10
	5
	
1) Formalização do problema 
a) Variáveis de decisão 
- Quantidade (kg) de granulado existente na ração diária .
 - Quantidade de farinha existente na ração diária .
b. Função objectivo
Minimizar o custo da ração diária.
b) Restrições 
- Quantidade mínima diária de hidrato de carbono.
- Quantidade mínima diária de vitaminas.
- Quantidade mínima diária de proteínas.
1) Modelação matemática 
Minimizar (custo diário)
Sujeito a (hidrato de carbono)
 (vitaminas)
 (proteínas)
 (não negatividade)
Ex.3. As caravanas MARCO POLO,LDA, usam dromedários (1 bossa)e camelos (2 bossas) para transportar figos secos de Bagdade para Meca. Um camelo pode levar no máximo 100 kg e um dromedário 50 kg. Durante a viagem um camelo consome 3 fardos de feno e 100 galões de água. Um dromedário 4 fardos de feno e 80 galões de água.
As estações de MARCO POLO, situada em vário oásis ao longo do caminho, apenas têm disponíveis 1600 galões de água e 60 fardos de feno.
Os camelos e dromedários são alugados a um pastor de Bagdade a 11 pazuzas por camelo e 5 pazuzas por dromedário. Se as caravanas MARCO POLO, LDA tiveram uma carga de 1.000 kg de figos secos para transportar, quantos camelos e dromedários devem ser usados para minimizar a renda a pagar ao pastor?
1) Formulação do problema a) variáveis de decisão
 - Quantidade de camelos a usar 
 - Quantidade de dromedários a usar 
b) Função objectivo
- Minimizar a renda a pagar ao pastor
c) Restrições 
- Disponibilidade de caravana.
- Disponibilidade de feno. 
- Disponibilidade de água.
	
	Camelos 
	Dromedários 
	Capacidade disponível 
	Capacidade 
	100
	50
	1000
	Feno
	3
	4
	60
	Agua
	100
	80
	1600
	Renda a pagar
	11
	5
	
2) Modelação matemática
Minimizar (renda)
Sujeito a (capacidade)
 (feno)
 (água) 
 (não negatividade)
Exemplo.4. Certa empresa fabrica 2 produtos P1 e P2. O lucro por unidade de P1 é de 100 u.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 hora para fábrica uma unidade de P2. O tempo mensal disponível para essa actividade é 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 unidade de P2 por mês.
Construa o modelo de sistema de produção mensal com o objectivo de maximizar o lucro da empresa.
Resolução de exercício
Empresa produz 2 produtos (P1 e P2)
Com relação a P1
Lucro é 100 u.m.
Tempo para produzir é 2 hora
Produção máxima é 40 uni/mês 
Tempo disponível para a produção das duas unidades é de 120 horas
Definição das variáveis 
- Variável a ser optimizada 
Max. Lucro: lucro máximo a ser atingido por mês.
-variáveis básicas
X1: quantidade óptima de produção/mês de P1
X2: quantidade óptima de produção/mês de P2
Função objectivo
Max. Lucro 
Conjunto de restrições 
Exercício 5
Uma empresa de comida canina produz dois tipos de rações: Tobi e Rex.
Para a manufactura das rações são utilizados cerais e carne. Sabe-se que:
· A Tobi utiliza 5 kg de cereais e 1 kg de carne, 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. 
Nosso modelo deseja maximizar o lucro (Z) a partir da quantidade da ração Tobi e de ração Rex .
	
	Ração Tobi
	Ração Rex
	Custo de carnes 
	1 Kg × $ 4 = $ 4
	4 Kg × $ 4 = $ 16
	Custo de cereais
	5 Kg × $ 1 = $ 5
	2 Kg × $ 1 $ 2
	Custo total
	$ 9
	$ 18
	Preço
	$ 20
	$ 30
	Lucro
	$ 11
	$ 12
Função objectivo
Conjunto de restrições
3.4. RESOLUÇÃO GRÁFICA DE PROBLEMAS DE PL
A resolução gráfica de um problema de PL só é possível quando o problema tem duas ou três variáveis de decisão. Nós estudaremos apenas problemas com duas variáveis cujo gráfico ficará representado num plano.
Considera – se um sistema cartesiano com o eixo das abcissas associado a x1 e o eixo das ordenadas associado a x2.
Relaxando ou enfraquecendo a condição de desigualdade das restrições técnicas, estas passam a ser equações que definem rectas. Cada uma destas rectas divide o plano em duas regiões disjuntas verificando – se a relação de desigualdade apenas em pontos de uma das regiões (sub espaços).
Procedendo desta forma é possível, por interacção, definir o conjunto de pontos – solução do problema e neste determinar aquele ou aqueles onde a função objectivo tem o seu extremo (maximizar ou minimizar).
 Roteiro básico para resolução de problemas pelo método gráfico
1) Identificar as variáveis de decisão.
2) Montar a função-objectivo.
3) Montar as equações de restrição.
4) Determinar no mínimo 2 pontos para cada recta de restrição.
5) Marcar os pontos e traçar as rectas no plano cartesiano.
6) Seleccionar (marcar) a área viável.
Obs: Se a restrição for:
=, Sobre a recta
>=, Acima da recta e a direita
<=, Abaixo e a esquerda da recta
7) Verificar a área comum entre todasas restrições.
8) Achar o ponto óptimo do problema.
9) Formular a resposta.
O processo baseia – se na representação gráfica da recta Z = F (x1, x2) = const., para um conjunto de valores, ou seja, traçar rectas Z = constante, até que contenha pelo menos um ponto da região admissível e esteja o mais distante possível da recta Z = 0 (maximizar) ou o mais perto possível (minimizar).
Exemplo nº1: (problemas de maximização)
Nota: A região ou espaço de possibilidades (soluções admissíveis), é o conjunto de soluções possíveis do problema dado e é formado por todos os pares de valores (x1, x2) que satisfazem simultaneamente todas as condições ou restrições do problema.
a) Flexibilização das restrições: 
b) 
Rectas associadas a restrição: 
c) 
A inclinação da recta obtida é de . Este valor corresponde ao simétrico do quociente entre os coeficientes de x1 e x2. 
d) O conjunto de pontos possíveis que esta recta verifica, corresponde a todo o espaço de pontos a esquerda da recta e sobre ela, uma vez que traduz todas as combinações de x1 e x2 que multiplicadas por 3 e por 4 respectivamente, sejam menores ou iguais a 12. 
e) 
Recta associada a restrição:
(o processo é análogo ao anterior)
 Inclinação da recta: 
Nota: Sendo que, a região de soluções admissíveis corresponderá a uma região limitada pelas duas restrições e pelos dois eixos, limitando – se assim a uma figura do primeiro quadrante:
Representação gráfica da função objectivo
Ao contrário das restrições, na função objectivo não existe termo constante fixo com o qual possamos relacionar os coeficientes das variáveis. Assim sendo, escolhe – se um valor arbitrário para o lucro ou seja, Z = 0 e tenta – se representar a F.O. para esta situação.
Para calcular a inclinação da função objectivo, procura – se a sua forma reduzida, ou seja, transformar a equação por formas a encontrar a expressão da ordenada que é função da abcissa.
Atribuindo valores a x1, encontramos os valores de x2 que correspondem a pontos dessa recta.
OBS: O declive da recta da FO é que corresponde a razão entre os coeficientes das abcissas e das ordenadas.
Identificação do ponto óptimo. Solução óptima
A maximização da F.O efectua-se deslocando paralelamente a recta do F.O aumentando no máximo possível o valor do Z. O sentido da deslocação é definido pela própria F.O.: O aumento do Z consegue-se aumentando se, e X2, uma vez que cada uma dela esta associada a coeficientes positivos.
Ao logo do gradiente, ou ambos variáveis aumentam ou ambos diminuem conforme o sentido de deslocação. O sentido de deslocação da FO será escolhido por forma a garantir a max. Z. 
A max. Z será atingido no último ponto de contacto com a região de soluções admissíveis que corresponde a máxima deslocação da FO. A este ponto dá-se o nome de P.O. (ponto óptimo) e corresponde a um vértice.
 A solução óptima corresponde ao vértice da região de solução admissível formada pela intersecção das duas restrições e será dada pela solução do sistema de equações. 
Logo:
PROBLEMA DE MINIMIZAÇÃO
 Flexibilidade do sistema 
Recta associado a 
Recta associado a 4x1+2x2 = 3 
O conjunto de pontos possíveis (região de soluções possíveis) em cada uma das restrições corresponde aos pontos das próprias rectas e todos os pontos que encontra a direita da mesma uma vez que estamos perante inequações de tipo “maior ou igual”. 
A função objectivo
Inclinação: 
Graficamente:
PONTO ÓTIMO. SOLUÇÃO ÓTIMA
Uma vez representada a FO na origem do sistema, a minimização de Z exige a consideração de valores para x1 e x2, tão pequenos quanto possível. Assim a deslocação paralela da função em direcção a região de soluções admissíveis, deve limitar – se aquela posição em que toca a região num primeiro ponto.
Este ponto denomina – se ponto óptimo e corresponde ao par (x1, x2) de menor valor e traduz a solução óptima.
Uma vez identificada a solução óptima, bastará calcular os valores que a traduzem, considerando o vértice obtido pela intersecção das duas restrições.
Logo:
 O PROBLEMA DE MISTO
A representação gráfica conduz – nos ao seguinte esquema:
Recta associado a 
Recta associado a 5x1+5x2 = 75 
Inclinação: 
Obs: Este é um problema de minimização em que a FO tem declive> 0.
Minimização da PO 
Para diminuir Z, teremos que diminuir x1 e aumentar x2, isto é, deslocar paralelamente a reta que traduz a FO para a esquerda, até que esta atinja o ultimo ponto da região de soluções admissíveis.
Este último ponto em que a FO passa, será o ponto em que x1 é mínimo e x2 é máximo. Este ponto torna o valor de Z máximo, logo é o ponto óptimo.
Cálculo da solução óptima
O ponto óptimo corresponde a solução do sistema de equações que segue:
Substituindo na FO, teremos:
 O PROBLEMA DE SOLUÇÕES MÚLTIPLAS
Flexibilidade do sistema
Recta associado a 
Recta associado a x1=20 (recta vertical com abcissa igual a 20); a x2 = 40 (recta horizontal com ordenada igual a 40) 
 FO: p/ Z = 0; → x2 = x1
Solução óptima: Max Z
Para aumentar Z, teremos que aumentar x1 e diminuir x2 ou seja, deslocar paralelamente a recta que traduz a FO para a direita, até ao último ponto possível da região de soluções admissíveis. Graficamente teremos:
Aqui, a FO deverá ser deslocada até coincidir com a última restrição (2x1 – 2x2 = 80) pois é a posição que maximiza o lucro ainda dentro da região de soluções admissíveis.
Substituindo na FO, teremos: 
Nota: este tipo de solução denomina – se solução óptima múltipla e considera – se um caso especial.
3.6 FORMA PADRÃO OU STADARD DE UM PROBLEMA DE PL
3.6.1. Variáveis de folga e variáveis de excesso
Seja: 
Esta restrição pode ser convertida numa igualdade pela adição de uma nova variável não negativa ao primeiro membro da desigualdade. Tal variável será numericamente igual a diferença entre o segundo membro e o primeiro e designa – se por variável de folga.
A variável de folga, representa o desperdício associado ao recurso modelado pela restrição em causa.
Exemplo: 
Esta desigualdade é transformada na equação pela adição da variável de folga x5 ao primeiro membro da desigualdade.
Consideremos agora a restrição linear na forma 
Esta desigualdade pode ser convertida numa equação, bastando subtrair uma nova variável não negativa ao primeiro membro da desigualdade. Esta tal variável designada por variável por variável de excesso, representa numericamente a diferença entre o primeiro e o segundo membro da desigualdade.
Em relação ao recurso modelado pela restrição em questão, esta variável representa o consumo em excesso, além da disponibilidade.
Exemplo: 
Esta desigualdade transforma – se na equação 
pela subtracção da variável de excesso x4 ao primeiro membro.
Solução inicial admissível
Depois de transformadas todas as restrições lineares (com os segundos membros das desigualdades positivos) em igualdades, pela introdução de variáveis de folga e de excesso onde necessário, adiciona – se uma nova variável, designada variável artificial,aos primeiros membros das restrições que não contém a variável de folga.
Assim, todas as equações que representam restrições terão ou uma variável de folga ou uma variável artificial. Uma solução inicial não negativa para este novo conjunto de restrições, obtém – se igualando em cada restrição, a respectiva variável de folga ou artificial, ao correspondente termo independente e igualando – se a zero as restantes variáveis, incluindo as variáveis de excesso.
Exemplo:
Seja o conjunto de restrições:
Introduzindo as variáveis de folga e de excesso, transformando o sistema de desigualdades em equações, teremos:
Adicionemos em seguida variáveis artificiais nas restrições que não possuem variáveis de folga, ou seja:
Nota: Uma solução inicial não negativa para este sistema de equações, será:
Nota: não é uma solução que verifica o conjunto de restrições original. 
3.6.3. Custos e penalização
A introdução no sistema de restrições de variáveis de folga e de excesso, não altera a natureza da função objectivo nem das próprias restrições.Porém, as variáveis artificiais alteram a natureza das restrições. Tendo em conta que cada variável artificial é adicionada a um dos membros das restrições, o novo sistema de equações que representa as restrições e o sistema original coincidirão se e só se as variáveis artificiais tiverem o valor nulo.
Para garantir que isto aconteça na solução óptima (em contraste com a solução inicial), as variáveis artificiais são incorporadas na função objectivo com coeficientes positivos de valores muito elevados nos problemas de minimização, designados por M, e coeficientes negativos de valores muito elevados nos problemas de maximização, designados por – M. estes coeficientes (M e – M), representam uma penalidade muito severa em que se incorre se a respectiva variável artificial tomar valor igual a unidade.
3.6.4. Forma padrão
Um problema de PL, diz – se que está na forma padrão, se todas as restrições estiverem representadas põe equações e se for conhecida uma solução inicial admissível. Na notação matricial, a forma padrão tem as seguintes características:
Onde:
X→ È o vector coluna de incógnitas, incluindo todas as variáveis de folga, de excesso e artificiais.
A→ É a matriz dos coeficientes das equações das restrições
CT → É o vector linha dos custos correspondentes
B→ É o vector coluna dos termos independentes das restrições
Nota: doravante, os vectores serão normalmente representados por matrizes com uma única coluna e designados apenas por “vectores” , em vez de vector coluna. O expoente T, indica a transposição.
Se X0 representar um vector que inclui apenas variáveis de folga e variáveis artificiais, então a solução admissível inicial será dada por X0 = B.
3.5 Classificação das soluções
· Solução única óptima finita;
· Infinitas soluções óptimas finitas;
· Solução no infinito;
· Conjunto factível vazio;
3.5.1 Solução única óptima finita:
· Se a solução é única óptima finita, ela ocorre em ponto extremo
3.5.2 Solução única óptima finita:
· A região factível não precisa ser necessariamente limitada.
3.5.infinitas soluções óptimas finita
Os dois vértices esão soluções óptimas, bem como qualquer outro ponto sobre o segmento que se une.
3.5.4 Solução única óptima finita:
· Novamente a região factível precisa necessariamente limitada
3.5.5 Solução no infinito:
· Não é possível alcançar o ponto de óptimo, o mesmo encontra-se no infinito.
3.5.6 Conjunto factível vazio: 
· Ocorre quando o sistema de equações que define a região viável é inconsciente.
4. MÉTODO SIMPLEX
1.1 – Introdução 
O método simplex é a técnica utilizada para se determinar, numericamente, a solução óptima de um problema de programação linear, na forma padrão, mas com as seguintes características para o sistema linear de equações:
i) Todas as variáveis são não – negativas:
ii) Todos os são não – negativos;
iii) Todas as equações iniciais do sistema são do tipo “≤”. Assim, na forma padrão, só encontra-se variáveis de folga.
Se uma das características vista não ocorrer, então, casos especiais métodos devem ser considerado como método simplex de duas fases.
1.2 – Introdução e fundamentos teóricos para o método simplex
1.2.1 – Determinação de soluções básicas num sistema de equações lineares m × n, m ≤ n (sistema lineares)
Se ao resolver um sistema Ax= b, onde fosse uma matriz inversível então a solução seria facilmente determinada.
Porem, se dado um sistema Ax= b, onde: 
Tal que m ≤ n, ou seja, sistema é retaguarda, como determinar soluções de Ax= b?
O sistema acima sempre tem solução?
Teorema 4.2.1.1: 
Seja a matriz com m ≤ n. se a matriz A possui m colunas linearmente independentes (LI´s) então para qualquer o sistema Ax= b, tem ao menos uma solução em .
Definição 4.2.1.1:
 Seja Ax= b, A 
Se A possui uma submatrizB ondedetB ≠ 0 então diz-se que B é uma submatriz base de A, o que é equivalente a dizer:
Se A tem m colunas LI então a matriz B formada por estas colunas é uma base para.
Definição4.2.1.2 - variáveis básicas e não básicas:
Considerando-se o sistema Ax= b definido em (3.1) e uma submatriz base de A, então, as variáveis associadas a submatrizsao denominadas variáveis básicas.
Notação: variáveis básicas: .
Definida a submatriz base B restam em A (n – m) colunas que chamara-se de submatriz não base. As variáveis associadas a esta submatrizN são denominadas variáveis não básicas.
Notação: variáveis não básicas 
4.2.1.2 – Uma possível solução para Ax = b da definição acima
Seja o sistemaAx= b e suponha que extrai-se de A uma submatrizB.
Pela definições anteriores pode-se fazer o seguintes partições no sistemaAx= b:.
Logo pode se escrever:
Ax= b
Portanto o sistema Ax= b é equivalente ao sistema:
Isto define queé uma possível solução de Ax= b
Definição 4.2.1.3 – solução básica de Ax = b:
Seja o sistema Ax = bdefinido em (3.1) então uma solução de Ax = b ou seja A= b,é denominada solução básica, se e somente se, em (3.2), Xn = 0, então: 
Definição 4.2.1.4 – solução básica factível (viável):
é combinada a solução básica factível para Ax= b se, e somente se:
para(ou seja ).
1.3 – Definição e teorema fundamentais
X sera um ponto extremo de S se possuir n-mvariaveis nulas.
Teorema 4.3.1:
“O conjutoS de todas as soluções factíveis do modelo de programação linear, é um conjunto convexo”.
Prova : 
Seja 
Mostrara-se que: 
i) 
ii) 
Para se mostrar i) basta notar que,
SeA = b;
Assim, A (.
Logo, 
iii) Para se mostrar ii): 
Assim, ): .
:..
:. É convexo
Teorema 4.3.2: 
“Toda solução básica do sistema Ax= b é ponto extremo do conjunto de soluções factíveis S”.
Prova: 
Seja uma solução básica associada a uma submatriz base .
Então, sem perda de generalidade, suponha quecom.
Por contradição, suponha quenão seja ponto extremo ou vértice de S, então tal que:
.
Desde que 
Logo, 
como
.
Mase então , contradição, pois por hipose B é uma submatriz base e portanto não singular!
:. “todasolyução básica do sistema Ax= b é um ponto extremo do conjunto de soluções factíveis”.
Teorema 4.3.3
Seja ponto extremo do conjunto S e seja S limitado. 
Então, pode ser escrito como combinação convexa dos pontos extremo de S, ou seja 
Teorema 4.3.4
 Se um problema de programação linear admitir solução óptima, então pelo menos um ponto extremo(vértice) do conjunto de pontos viáveis é uma solução óptima do problema.
Mostrara-se este teorema admitindo-se que o conjunto S é limitado. 
Prova:
Seja pontos dos extremo do conjunto S limitado.
Então, pelo teorema 3.3.3, pode ser escrito como combinação convexa dos pontos extremo , ou seja, 
 Logo 
Seja um ponto extremo tal que 
Mas
Então 
:.é um vértice óptimo (solução óptima)do problema.
Corolário 4.3.1:
“ se a função objectivo possui um máximo (mínimo) finito, então pelo menos uma solução é óptima é um ponto extremo do conjunto convexo S”.
Teorema 4.3.5: 
Toda combinação convexa de soluções óptima de um P.P.L. é também uma solução óptima do problema.
Corolário 4.3.2:
se um P.P.L admitir mais uma solução óptima então admite infinitas soluções óptimas.
Corolário 4.3.3:
“ se uma função objectivo assume o máximo (mínimo) em mais de um ponto extremo, então ela toma o mesmo valor para qualquer combinação convexa desses pontos extremos”.
1.4 – os passos do método de simplex
O método simplex é um procedimento matricial para resolver problema de programação linear expressos na forma standard.
Optimizar: 
Sujeito a: 
Com: 
Onde B ≥ 0 e se conhece uma solução básica admissível .
M método simplex começa com a solução básica admissível e vai sucessivamente, localizando outras soluções básicas (sempre adimissiveis) correspondentes a melhores valores de funçaõ objectivo, ate que seja encontrada uma solução óptima 
Resumidamente, podemos dizer que o método simplex parte de uma solução básica admissível não óptima ate encontrar uma solução básica admissível óptima.
Nota: Para problemas de minimização o método utiliza o quadro que se apresenta em baixo, no qual designa o vector custo associado as variáveis em .
	
	
	
	
	
	B
	
	
	
Nota: Para problemas de maximizaçãoo método utiliza um quadro semelhante. A única diferença encontra-se na última linha do quadro.
	
	
	
	
	
	B
	
	
	
Uma vez obtida esta ultima linha do quadro, a segunda linha e a segunda coluna do quadro. Corresponde a , respectivamente, torna-se supérfluas e podem ser eliminadas
: vector dos custos correspondentes 
X: é o vector coluna de incógnita (incluindo variáveis de folga, excesso e artificiais)
A: é a matriz do coeficiente das operações de restrições.
B: é o vector coluna dos vectores a direita das equações representado as restrições.
: é o vector coluna de variáveis de folga e artificiais
: é o vector coluna de custo associado com as variáveis em.
Exemplo 1
Maximizar z= 80 x1 + 60x2
Sujeito a: 
com:x1 ex2 não negativos 
adicionando uma variável de folga é uma variável artificial , respectivamente, as primeira e segunda restrições.
Maximizar z= 80 x1 + 60x2 + 0x3+ Mx4
Sujeito a: 
 0,20 x1 + 0,32 x2 + x3 = 0,25
x1 + x2 + x4 = 1
 Com todas as variáveis não negativas
Passando para a forma normal matricial teremos:
Quadro simplex
	
	x1x2 x3 x4 
80 60 0 M
	
	
	0,2 0,32 1 0
1 1 0 1
	0,25
1
	
	80 -M60 -M0 0 
	-M
Exemplo: 2 
Maximizar z= x1 + 9x2 + x3
Sujeito a: 
Todas as variáveis não negativas 
Passando para forma matricial
Quadro simplex
Quadro 1 (quadro inicial completo)
	
	x1x2 x3 x4 x5
1 2 3 1 0
	
9
	
	3 2 2 0 1
-1 -9 -1 0 0
	15
0
Conjunto de passos que constituem o método simplex:
Passo 1: Localizenumero mais negativo na última linha do quadro simplex, excluída a ultima coluna, designando a coluna em que este número aparece como coluna de trabalho. Se existir mais do que um candidato a numero mais negativo, escolha um.
Passo 2: Para cada linha do quadro (exceptuando a ultima) como coeficiente positivo na coluna de trabalho, divida cada elemento da última coluna pelo correspondente coeficiente da coluna de trabalho. Designe o coeficiente de trabalho correspondente ao menor coeficiente por elemento pivot. Se mais de um coeficiente mínimo, escola um.
Se nenhum coeficiente da coluna de trabalho for positivo, o problema não terá solução.
Passo 4: Use operações elementares sobre as linhas para converter o elemento pivot em 1 e, em seguida, reduzir a zero todos os outro elementos da coluna de trabalho.
Passo 4: Na 1ª coluna, substitua a variável x existente na linha pivot, pela variável x correspondente a coluna de trabalho (indicada na 1ª linha). A nova 1ª coluna indica o novo conjunto de variáveis básicas.
Passo 5: Repetir os passos 1 a 4 até ate que não existam nºs negativos na última linha, excluindo destas apreciações a ultima coluna.
Passo 6: A solução óptima é obtida atribuindo-se a cada variável da 1ª coluna o valor da linha correspondente, na última coluna.
Todas as outras variáveis são nulas. O valor óptimo da função objectivo associado, é o valor indicado na última coluna, para problema de maximização, em problemas de minimização será o seu simétrico. 
 
 (
Encontrar a 1ª
solução admissível
)
 (
Teste de optimalidade:
Zj – cj< 0 ?
)
 (
Solução 
Óptima 
)
 (
Não
)
 (
Sim
)
 (
Seleccionar zj – cj< 0 Com maior valor absoluto 
)
 (
 Seleccionar o menor bj/yi e determinar elemento “pivot”
)
 (
Converter a coluna seleccionada num vector unitário “0…1…0” com 1 na posição do “pivot”
)
 (
Recalcular a linha zj - cj
)
1.5 
1.6 
 
1.7 Modificação para problemas com variáveis artificiais
 Modificação 1: A última linha do quadro 3 – 1 é decomposta em duas linhas, a primeira linhas, a primeira das quais envolve os termos que não contem M, e a segunda os coeficientes de M nos restantes termos
Exemplo: a linha
Seria transformada em duas linhas:
Modificação 2: o passo 1 do método simplex é alpicado a ultima linha criada em modificação 1 (seguida pelos passos 2, 3 e 4) ate que esta linha não contenha elementos negativos em seguida o passo 1 é aplicado aos elementos da penúltima linha posicionados sobre os zeros da ultima linha. 
Modificação 3: sempre que uma variavel artificial deixa de ser básica, isto é, deixa de figurar na 1ª coluna do quadro, em resultado do passo 4, a correspondente coluna(indentificada na linha superior do quadro por essa variavel ) deve ser removida.
Modificação 4: a ultima linha do quadro pode ser eliminada quando for constituída unicamente por zeros.
Modificação 5: se na solução básica final estiverem presentes variáveis artificiais não nulas, então o problema original não admitira solução. (pelo contrario, na solução básica afinal podem aparecer variáveis artificiais na base com valor zero, indicando que uma ou mais das equações que representam as restrições são redundantes.
Praticando no exercício em análise, teremos: 
 (
Coluna de trabalho
)Primeiro passo:
	
	x1x2 x3 x4 x5
	
	
	1 2 3 1 0
3 2 2 0 1
	9
15
	
	-1 -9 -1 0 0
	0
 (
O número mais negativo
)
 (
Coluna de trabalho
)
Segundo passo: 
	
	x1x2 x3 x4 x5
	
	
	1 2 3 1 0
3 2 2 0 1
	9
15
	
	 Pivô
-1 -9 1 0 0
	0
 (
Neste passo multiplica-se todos os elementos da linha do pivô pelo seu inverso. Recorde-se que o inverso de 2 é ½ 
)Terceiro passo (a)
	
	x1x2 x3 x4 x5
	
	
	 1 0
3 2 2 0 1
	
15
	
	-1 -9 -1 0 0
	0
 (
Neste passo, reduziu-se a zero o nº - 9, multiplicou-se por 9 a linha do pivô, seguidamente fez-se a soma algébrica com a li
n
ha que contem o elemento – 9.
)Terceiro passo (b)
	
	x1x2 x3 x4 x5
	
	
	 1 0
3 2 2 0 1
	
15
	
	 0 0
	
 (
Neste 
passo, reduziu-se o elemento2e multiplicou-se por -2
 a linha
 que contem 
o pivô,
 fazendo-se posteriormente a soma
 algébrica com a li
n
ha que contem o elemento 
2.
)
Terceiro passo (b)
	
	x1x2 x3 x4 x5
	
	
	 1 0
2 0 -1 -1 1
	
6
	
	 0 0
	
Quarto passo 
	
	x1x2 x3 x4 x5
	
	
	 1 0
2 0 -1 -1 1
	
6
	
	 0 0
	
Quinto passo
Não é necessário aplicar pois não existe números negativos na ultima linha.
Sexto passo
Exemplo 2 
a) Formulaçao do problema
b) Construção do modelo 
c) Resolver graficamente
d) Forma padrão
e) Método simplex
A) Formulação do problema:
Certa empresa fabrica 2 produtos P1 e P2. O lucro unitário do produto P1 é de 1000 unidades monetárias e o lucro unitário de P2 é de 1800 unidades monetárias. A empresa necessita de 20 horas para fabricar uma unidade de P1 e 30 hora para fábrica uma unidade de P2. O tempo anual de produção disponível para isso é de 1200 horas. As demandas esperadas para cada produto é de 40 unidades anuais para P1 e 30 unidades para P2. Qual é o plano da produção para que a empresa maximize seu lucro nesses itens?
Construa o modelo de programação linear para esse caso.
B) Construção do modelo:
C) Resolver graficamente
Calculando a inclinação para as rectas das restrições:
Recta associada a:
· Para
· Para
· Recta associada a (recta vertical com abcissa igual a 40)
· Recta associada a (recta horizontal com ordenadas igual a 30)
Calculando a inclinação da função objectivo:
Para 
Teremos: 
· Para
· Para
Para Z = 40000
Teremos: 
· Para
· Para
O ponto óptimo correspondente ao vértice da região admissível formada pela interacção das duas restrições, a solução é dada pela resolução do sistema de equações abaixo:
resolvendo teremos:
já temos o valor de X2 = 30, substituindo na 1ª equação temos: 
 ? 
? 
? 
? 
Terminados os cálculos, temos o conjunto de solução:
&
Logo:
D) Forma padrão 
Forma padrão: 
E) Método simplex
Realizadas as devidas transformações teremos: 
Construção do quadro simplex
1º Passo
 (
Coluna de Trabalho
)
	Base
	 x1 x2 x3 x4 x5 
	b
	X3 
X4 X5
	 20 30 1 0 0
 1 0 0 1 0
 0 1 0 0 1
	1200
40
30
	z
	-1000 -1800 0 0 0
	0
 (
O nº mais negativo
)
 (
Coluna de Trabalho
)2º Passo
	Base
	 x1 x2 x3 x4 x5 
	b
	X3 
X4 X5
	 20 30 1 0 0
 1 0 0 1 0
 0 0 0 1
	1200
40
30
	z
	-1000 -1800 0 0 0
	0
 (
Pivô
)
Calculo para transformar a coluna de trabalho, colocando 1 (um) no pivô e o 0 (zero) nos outros valores.
Obs: sendo que o pivô já é 1 (um), já não será necessário realizar nenhum cálculo para estalinha, bastando apenas realizar o cálculo para transformar em 0 (zero) as outras linhas.
	Base
	 x1 x2 x3 x4 x5 
	b
	X3 
X4 X5
	 20 30 1 0 0
 1 0 0 1 0
 0 1 0 0 1
	1200
40
30
	z
	-1000 -1800 0 0 0
	0
 (
Calculo para 1ª linha
)
	Base
	 x1 x2 x3 x4 x5 
	b
	X3 
X4 X5
	 20 30 1 0 -30
 1 0 0 1 0
 0 1 0 0 1
	300
40
30
	z
	-1000 -1800 0 0 0
	0
 (
OBS: não será realizado calculo algum para a linha 2 (dois) porque já contem 0 (zero)
)
 (
Calculo para 4ª linha
)
 (
Coluna de Trabalho
)
	Base
	 x1 x2 x3 x4 x5 
	b
	X3 
X4 X5
	 20 0 1 0 -30
 1 0 0 1 0
 0 1 0 0 1
	300
40
30
	z
	-1000 0 0 0 1800
	54000
 (
OBS: ainda não chegamos na solução óptima porque ainda existe um valor negativo, e a coluna em ele está será a nossa coluna de trabalho. 
)
 (
O número negativo
)
	Base
	 x1 x2 x3 x4 x5 
	b
	X3 
X4 X5
	 0 1 0 -30
 1 0 0 1 0
 0 1 0 0 1
	300
40
30
	z
	-1000 0 0 0 1800
	54000
 (
Pivô
)
Calculo para transformar a coluna de trabalho, colocando 1 (um) no pivô de 0 (zero) nos outros valores.
	Base
	 x1 x2 x3 x4 x5 
	b
	X3 
X4 X5
	 20 0 1 0 -30
 1 0 0 1 0
 0 1 0 0 1
	300
40
30
	z
	-1000 0 0 0 1800
	54000
 (
Calculo para 1ª linha
)
 (
Calculo para 4ª linha
)
	Base
	 x1 x2 x3 x4 x5 
	b
	X3 
X4 X5
	 20 0 0.5 0 -1.5
 1 0 0 1 0
 0 1 0 0 1
	15
40
30
	z
	-1000 0 0 0 1800
	54000
 (
OBS: não será realizado calculo algum para a linha 3 (três), porque já contem 0 (zero) 
)
	Base
	 x1 x2 x3 x4 x5 
	b
	X3 
X4 X5
	 20 0 0.5 0 -1.5
 1 0 0 1 0
 0 1 0 0 1
	15
40
30
	z
	-1000 0 0 0 1800
	54000
 (
Calculo para 4ª linha
)
	Base
	 x1 x2 x3 x4 x5 
	b
	X3 
X4 X5
	 20 0 0.5 0 -1.5
 1 0 0 1 0
 0 1 0 0 1
	15
40
30
	z
	-1000 0 0 0 1800
	54000
 (
OBS: os valores que já não existem valores negativos na última linha, concluímos que a nossa solução óptima foi encontrada. 
)
Sendo assim teremos:
A solução paraapresenta pelo método gráfico, bem como o valor Z = 69000, coincidem com a solução apresentada pelo método simplex, reforçando assim a resposta para o exercício.
Exercício nº 3 
Um fabricante de fantasia tem em stock 32m de brim, 22m de seda e 30m de cetim que pretende fabricar dois tipos de fantasia. O primeiro modelo (M1) consome 4m de brim, 2m de seda e 2m de cetim. O segundo modelo (M2) consome 2m de brim, 4m de seda e 6m de cetim. Se M1 é vendido a 6.000 u.m e M2 a 10.000 u.m quantas peças de cada tipo o fabricante deve fazer para obter a receita máxima? Elabore o modelo.
- Formulação do problema
Dados 
	Peças
	Modelo 1
	Modelo 2
	Stock
	Brim
	4m
	2m
	32m
	Seda
	2m
	4m
	22m
	Cetim
	2m
	6m
	30m
	Venda
	6.000 u.m
	10.000 u.m
	
- Objectivo
Determinar as quantidades de cada peça ser produzido no modelo 1 e no modelo 2 de modo a obter a receita máxima.
- Variáveis de decisão 
 – Quantidade de cada peça a ser produzido no modelo 1
 – Quantidadede cada peça a ser produzido no modelo 2
- Função objectivo
Max 
- Restrições
- Construção do modelo
Max 
- Restrições
 - Flexibilização das restrições
Max 
- Restrições
- Recta associada a restrição 
p/
p/
A inclinação da recta obtida é de
- Recta associada a restrição 
p/
p/
A inclinação da recta obtida é de
- Recta associada a restrição 
p/
p/
A inclinação da recta obtida é de
Para função objectivo
Max 
p/Z = 0
p/
p/
O declive da recta da FO é 
)
Substituindo na F.O, teremos:
- Calculo simplex
Max 
Max 
Max 
Quadro simplex
	
	
	
	
	A
	
	
	
	
X=[ X1 X2 X3 X4 X5 X6 X7 X8 ]t	
C=[6000 10000 0 0 0 0 ]T
= - [6000 10000 0 0 0 0 ]+ [0 0 0 ].
= - [6000 10000 0 0 0 0 ]
= [6000 10000 0 0 0 0 ]
= - [ 0 0 0 ].
	
	 6000 10000 0 0 0
	
	X3
 X4
X5
	 4 4 1 0 0
 2 4 0 0 0 
 2 ❻ 0 0 1
	32
22
30
	
	-6000 -10000 0 0 0 
	0
	
	
	
	
	X3
 X4
X5
	 4 2 1 0 0
 2 4 0 1 0 
 2 ❻ 0 0 1
	32
22
 30 
	
	-6000 -10000 0 0 0 
	0
	
	
	
	X3
 X4
X5
	 4 2 1 0 0
 2 4 0 1 0 
1 0 0 
	32 
22
 5 
	
	-6000 -10000 0 0 0 
	0
	
	
	
	X3
 X4
X5
	 0 1 0 
 4 0 1 0 
1 0 0 
	22
22
5 
	
	-6000 -10000 0 0 0 
	0
	
	
	
	X3
 X4
 X5
	 0 1 0 
 4 0 1 
1 0 0 
	22
22
5 
	
	 0 0 0 
	0
	
	
	
	X3
 X4
 X5
	 0 1 0 
 4 0 1 
1 0 0 
	22
2
5 
	
	 0 0 0 
	50.000
	
	
	
	X3
 X4
 X2
	 0 1 0 
 4 0 1 
1 0 0 
	22
2
5 
	
	 0 0 0 
	50.000
	
	
	
	X3
 X4
 X2
	 0 1 0 
 1 0 0 - 1
1 0 0 
	22
3
5 
	
	 0 0 0 
	50.000
	
	
	
	X3
 X4
 X2
	 0 0 1 - 5 3
 1 0 0 - 1
1 0 0 
	12
3
5 
	
	 0 0 0 
	50.000
	
	
	
	X3
 X4
 X2
	 0 0 1 - 5 3
 1 0 0 - 1
 0 1 0 
	12
3
4 
	
	 0 0 0 
	50.000
	
	
	
	X3
 X4
 X2
	 0 0 1 - 5 3
 1 0 0 - 1
 0 1 0 
	12
3
4 
	
	0 0 0 0 4000 - 1000 
	58.000
	
	
	
	X3
 X4
 X2
	 0 0 1 - 5 3
 1 0 0 - 1
 0 1 0 
	12
3
4 
	
	0 0 0 0 4000 - 1000 
	58.000
	
	
	
	X3
 X4
 X2
	 0 0 1 - 5 ❸
 1 0 0 - 1
 0 1 0 
	12
3
4 
	
	0 0 0 0 4000 - 1000 
	58.000
	
	
	
	X3
 X4
 X2
	 0 0 - 1
 1 0 0 - 1
 0 1 0 
	4
3
4 
	
	0 0 0 0 4000 - 1000 
	58.000
	
	
	
	X3
 X4
 X2
	 0 0 - 1
 1 0 - 0
 0 1 0 
	4
7
4 
	
	0 0 0 0 4000 - 1000 
	58.000
	
	
	
	X3
	 0 0 - 1
	4
	 X1
	 1 0 - 0
	7
	 X2
	 0 1 0 
	4 
	
	0 0 0 0 4000 - 1000 
	58.000
	
	
	
	
 X1
 X2
	
 1 0 - 0
 0 1 0
	
7
2 
	
	 0 0 0 
	62.000
	
	
	
	
 X5
X1
 X2
	
 0 0 - 1
 1 0 - 0
 0 1 0
	
4
7
2 
	
	 0 0 0 
	62.000
Conclusão:
Para obter a receita máxima o fabricante deve fabricar para o MODELO 1, 7m de cada peça e para o modelo 2, 2m de cada peça.
1.7.1 OUTRA FORMA DO MÉTODO SIMPLEX
4.5.2 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. Actualmente, 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, 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 lucro de $4.00 e cada armário de $1.00. 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 objectivo é: maximizar o 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: Restrições de não negatividade
O modelo completo é:
Maximizar: z = 4 x1 + x2
Sujeito a: 
 2 x1 + 3 x2 ≤ 12
 2 x1 + x2 ≤ 8
x1, x2 ≥0
c) Custos e penalidades. Solução inicial admissível 
d) 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 representada por uma variável de forma exactamente 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 aser:
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 igualando a zero duas variáveis (n - m = 2) e encontrando o valor para as duas variáveis restantes. Teremos que resolver então
sistemas de equações lineares.
Uma vez resolvido um sistema, serão aplicados na função objectivo os valores encontrados. As variáveis zeradas são chamadas variáveis não-básicas. Asvariáveis cujos valores são calculados pelo sistema de equações são chamadas variáveis básicas.
Variáveis não-básicas: x1 = 0 e x2 = 0
Variáveis básicas f1 = 12 e f2 = 8
Dando o lucro z = 0
Variáveis não-básicas: x1 = 0 e f1 = 0
Teremos as variáveis básicas x2 = 4 e f2 = 4
Dando o lucro z = 4
 3) Variáveis não – básicas: x1 = 0 e f2 = 0
Temos as variáveis básicas x2 = 8 e f1= -12
Como f1< 0, a solução obtida é INVIÁVEL.
 4) Variáveis não – básicas: x2 = 0 e f1 = 0
Temos as variáveis básicas x1 = 6 e f2 = -4
Como f2< 0, a solução obtida é INVIÁVEL.
 5) Variáveis não – básicas: x2 = 0 e f2 = 0
Temos as variáveis básicas x1 = 4 e f1 = 4 dando o lucro z = 16
6) Variáveis não – básicas: f1 = 0 e f2 = 0
Temos as variáveis básicas x1 = 3 e x2 = 2 dando o lucro z = 14
Comparando todas as soluções encontradas por este processo, achamos a solução ótima, ou seja, x1 = 4, x2 = 0, f1 = 4, f2 = 0, dando um lucro z = 16.
4.6 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 uma solução óptima, 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 objectivo, vamos realizar a seguinte transformação:
de: z= 4 x1+ x2
Quadro
	Base
	x1x2 f1 f2 
	b
	f1
f2
	2 3 1 0
2 1 0 1
	17
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 objectivo. 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 objectivo 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 objectivo 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 directamente 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 actual 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, como apresentado no Capítulo 2.
1ª Operação:
 Dividir a segunda linha por 2 (L2 L2 / 2)
Quadro 1A
	Base
	 x1 x2 f1 f2 
	b
	f1 
x1
	 2 3 1 0 
 1 1/2 0 1/2 
	12
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 x1
	 0 2 1 -1 
 1 1/2 0 1/2 
	4
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 x1
	 0 2 1 -1 
 1 1/2 0 1/2 
	4
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 é óptima.
x1 = 4, 
x1 = 4
f1 = 4, 
f2 = 0 e,
z = 16,
4.6.1 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 coeficientes da função objectivo 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 objectivo (ou seja, tem o maior valor negativo).