JOB-INVESTIGAÇÃO OPERACIONAL

Prévia do material em texto

Escola Superior de Ciências Náuticas 
Departamento de Máquinas Marítimas
Engenharia Electromecânica
Investigação Operacional
Programação Linear Método Simplex
Nome: Houston Jerónimo Macaze 
Docente: Msc. Honório Cumbi
Maputo, Abril 2021
ÍNDICE
INTRODUÇÃO	3
Objectivo geral	3
Objectivos específicos	3
METODOLOGIA	4
ESTRUTURA DO TRABALHO	5
INVESTIGAÇÃO OPERACIONAL	6
Fundamentos Teóricos	6
Processo de modelagem matemática para resolução de um problema	6
PRINCÍPIO DE PROGRAMAÇÃO LINEAR	7
Fundamentos Teóricos	7
Formulação do Modelo de Programação Linear	7
Definição: Problema de Programação Linear (PPL)	8
Formulação do Modelo de Programação Linear	8
Pressupostos dos Problemas de Programação Linear	9
MÉTODO SIMPLEX	11
Fundamentação Teórica do Método Simplex	11
Procedimento do Simplex	13
Minimização com restrições da forma ≥	18
Método de duas fases	19
Algoritmo duas fases	19
Maximização e minimização com restrições do tipo 	23
a)	Problemas de Maximização	24
b)	Problemas de Minimização	26
CONCLUSÃO	30
REFERÊNCIAS BIBLIOGRÁFICAS	31
INTRODUÇÃO
A Investigação Operacional (IO) tem como objecto o estudo e a investigação de operações e sistemas mais ou menos complexos, que combinam simultaneamente elementos humanos e materiais, procurando através de técnicas quantitativas apoiar a tomada de decisões aos níveis macro e microeconómico. O analista ou técnico de IO trabalha os dados, obtendo elementos quantitativos que fundamentam a tomada de decisões. No entanto, são os gestores (ou outros agentes de decisão) que definem os objectivos e que tomam as decisões.
Os problemas, que a IO procura ajudar a resolver, podem ser estruturados e não estruturados, e de nível estratégico, ou. Os problemas estruturados resolvem-se de forma conhecida, estando tipificados e tendo mais a ver com elementos materiais.
O método simplex é um procedimento matricial que percorre os pontos extremos do conjunto das soluções viáveis em busca de uma solução óptima. O algoritmo utiliza um critério na busca de forma que a solução seguinte seja sempre “melhor” do que a anterior. Como o conjunto possui um número finito de pontos extremos isso garante que o algoritmo termina em algum ponto, que será uma solução óptima do problema. Será através do presente trabalho que debruçarei melhor acerca do método simplex.
Objectivo geral
· Desenvolver o Método Simplex. 
Objectivos específicos
· Debruçar de forma resumida conceitos introdutórios ao tema, tais como:
· Investigação operacional;
· Princípio de programação linear.
· Definir segundo algumas obras, conceitos relacionados ao método simplex;
· Caracterizar o método simplex:
· Particularidades do método;
· Algoritmos de resolução;
· Variedade do método segundo as restrições.
METODOLOGIA
Para a realização do presente trabalho sobre o Método Simplex realizaram-se pesquisas bibliográficas, que consistiram na busca minuciosa de informações em livros ou manuais, artigos, e relatórios.
Para além da ferramenta acima mencionada, deu-se o uso de um outro aplicativo para o desenho e recorte, Paint.
Para o caso de livros ou manuais, artigos, e relatórios de idiomas diferentes de português submeteu-se o auxílio de uma ferramenta de tradução para o idioma português. 
Tomou-se o cuidado de não se usar como exemplos neste trabalho, os exemplos pelo docente usado nas explicações das matérias. Sendo assim foram resolvidos exercícios e usados aqui neste trabalho como exemplos.
ESTRUTURA DO TRABALHO 
Sendo divido em seis (6) fases, este trabalho foi estruturado como a seguir: 
1. Introdução: apresentação do trabalho, objectivos e justificativa do trabalho;
2. Metodologia: apresentação da metodologia utilizada para o desenvolvimento do Método Simplex; 
3. Definições: situações diversas sobre conceitos importantes do trabalho. 
4. Desenvolvimento: apresentação de conteúdos investigados e seleccionados minuciosamente com extrema relevância para realização do trabalho;
5. Conclusão: conclusão acerca da realiza do trabalho (se foi ou não atingido o que foi previamente mencionado nos objectivos do trabalho, e um resumo do próprio trabalho);
6. Referências Bibliográficas: relação dos artigos, normas, documento, livros e demais fontes consultadas para elaboração deste trabalho. 
INVESTIGAÇÃO OPERACIONAL
Fundamentos Teóricos 
Definição: 
· Segundo MULENGA, ALBERTO (2010), De um modo geral, a investigação operacional tem em vista trabalhar com factores interrelacionados, aplicando sobre estes um conjunto de aspectos, diferentes técnicas quantitativas para permitir com um bom censo resolver problemas empresariais ao nível da administração.
· Segundo a IFORS (International Federation of Operational Research Societies), Investigação Operacional é uma disciplina que lida com a aplicação de métodos analíticos avançados a problemas complexos para o auxílio à tomada de melhores decisões”.
Processo de modelagem matemática para resolução de um problema
Fonte: Araneles et al (2007).
A abordagem da resolução de um problema por meio de IO envolve:
i) Definição do problema e colecta de dados;
ii) Construção do modelo;
iii) Solução do modelo;
iv) Validação do modelo;
v) Implementação da solução.
PRINCÍPIO DE PROGRAMAÇÃO LINEAR
Fundamentos Teóricos 
· É uma das técnicas de resolução de modelos matemáticos de IO;
· É mais popular, devido à eficiência e facilidade de implementação dos seus algoritmos de solução;
· No modelo de PL, as funções matemáticas são necessariamente funções lineares;
· Geralmente, a PL é destinada a problema de alocar da melhor maneira possível (isto é, de maneira óptima) recursos limitados para actividades que competem entre si;
Formulação do Modelo de Programação Linear
Todo modelo de PL tem três componentes básicos:
· Variáveis de Decisão: são decisões quantificáveis cujos valores o próprio modelo
deverá determinar; 
· Função Objectivo: é uma função matemática das variáveis de decisão que se deseja optimizar (maximizar ou minimizar);
· Restrições: são as limitações dos recursos, que podem ser expressas por meio de equações ou inequações;
Definição: Problema de Programação Linear (PPL)
· Segundo MULENGA, ALBERTO (2010), designa - se por programação linear (PL) um conjunto de técnicas que permitem resolver os problemas de optimização, num sistema de recursos limitados, sendo lineares, quer a função objectivo, quer as restrições.
· Segundo Caixeta Filho (2001), algebricamente, a Programação Linear é o aprimoramento de uma técnica de resolução de sistema de equações lineares, utilizando inversões sucessivas de matrizes, incorporando uma equação linear adicional representativa de um dado comportamento que deverá ser optimizado.
É um problema de optimização que consiste em achar os valores das variáveis de decisão de forma a minimizar (ou maximizar) a função objectivo sujeita às restrições especificadas.
Formulação do Modelo de Programação Linear
Formulação algébrica geral do PPL:
Optimizar: 
Sujeito a:
Onde:
� → nível de actividade da alternativa j a ser determinado pela solução do PPL;
�→ custo unitário associado à alternativa ;
� → custo total da quantidade do elemento ;
� → valor limitante referente à restrição ;
�→ contribuição unitária da alternativa à restrição ;
� → número de variáveis de decisão do PPL;
� → número de restrições do PPL.
Pressupostos dos Problemas de Programação Linear
· Proporcionalidade: A contribuição de uma actividade ao valor da função objectivo e do lado esquerdo de cada restrição é proporcional ao nível dessa actividade: ; ;
· Adictividade: Toda função em um modelo de PL é a soma das contribuições individuais das respectivas actividades: ; ;
· Não-negatividade e Divisibilidade: As variáveis de decisão devem ser não negativas e podem assumir valores fraccionários;
· Certeza ou Determinismo: O valor atribuído a cada parâmetro de um modelo de PL (, e ) é assumido como uma constante conhecida.
Exemplos de Modelagem de Problemas de PL
Exemplo1: Um alfaiate tem disponível 16 m2 de algodão, 11 m2 de seda e 15 m2 de lã.
A confecção de um fato necessita de 2m2 de algodão, 1 m2 de seda e 1 m2 de lã, e um
vestido gasta 1, 2 e 3 m2 dos mesmos tecidos, respectivamente. Se um fato é vendido à 30
u.m (unidades de medida) e um vestido por 50 u.m., quantas unidades de cada artigo fato
ou vestido deve o alfaiate confeccionar de modo a obter maior lucro?
Resolução
	Tecidos
	Artigos
	Disponível
	
	Fato
	Vestido
	
	Algodão
	2
	1
	16
	Seda
	1
	2
	11
	Lã
	1
	3
	15
	Preço de venda (u.m)
	30
	50
	
O modelo económico - matemático correspondente é:
Maximizar Z = 30 + 50 → função objectiva max 
Sujeito à → Conjunto de restrições incluindo as de não negatividade
Exemplo2: Um agricultor precisa de 100 kg de Azoto (N), 120 kg de Fósforo (P) e 120
kg de Potássio (K), para adubar a sua plantação. Ele tem duas possibilidades no mercado,
sendo uma na forma líquida em tambores que contém 50 kg de N, 20 kg de P e 10 kg de
K ao preço de 30 u.m cada; outra empresa fornece adubo em sacos, contendo 10, 20 e 40
kg de N, P e K, respectivamente, ao preço de 20 u.m cada saco. Quantas embalagens de
cada fonte deverá o agricultor comprar para suprir as suas necessidades pelo menor custo.
Resolução
	Composição
de adubo
	Possibilidades de Mercado
	Necessidade
mínima
	
	Tambor
	Sacos
	
	Azoto
Fósforo
Potássio
	50
20
10
	10
20
40
	100
120
120
	Custo (u.m) 
	30
	20
	
O modelo matemático correspondente é:
Minimizar W = 30 + 20
Sujeito à 
MÉTODO SIMPLEX
Fundamentação Teórica do Método Simplex
Definição: 
· Segundo CARVALHO (2014), O método Simplex concentra-se, exclusivamente, nas soluções de ponto extremo, que existirão se o conjunto de soluções for convexo. Consiste num algoritmo iterativo (procedimento sistemático para atingir uma solução e que repete uma série de passos).
Hipóteses:
· É um sistema consistente, possível, não havendo incompatibilidade entre as restrições;
· As restrições são linearmente independentes, não havendo equações redundantes, não havendo repetições da informação;
· O número de restrições é menor que o número de variáveis. O sistema é indeterminado;
· Se alguma destas hipóteses não se verificar, então não há problema.
Teoremas:
· O conjunto de soluções admissíveis num problema de PL é um conjunto convexo com um número finito de pontos extremos.
· Uma função linear, cujo domínio é um conjunto convexo, assume o seu valor óptimo em pelo menos um ponto extremo.
· A uma solução básica admissível de um modelo de PL corresponde um ponto extremo do conjunto convexo das soluções admissíveis.
Condições:
· A restrição de não negatividade é obrigatória;
· Não é possível aplicar o método a um problema na forma geral, terá que se passar para a forma padrão ou aumentada. Transforma-se o sistema de inequações e/ou equações, associadas às restrições, exclusivamente num sistema de equações. 
Recorre-se, para isso, às chamadas variáveis auxiliares, de desvio ou de folga, assim como a variáveis artificiais. Estes novos tipos de variáveis permitem obter uma matriz identidade no quadro Simplex, constituindo-se como a base inicial.
· Variável de Folga: Introduz-se uma variável de folga, para cada restrição do tipo no primeiro membro da inequação e transforma-se esta em equação.
· Variável de Excesso: Restrições do tipo normalmente referem-se a quantidade mínima necessária que deve ser utilizada na combinação de diferentes actividades. A introdução de uma variável de excesso numa inequação transforma esta em equação.
Algoritmo Simplex
· Segundo CARVALHO (2014), o algoritmo Simplex primal permite solucionar problemas de programação linear utilizando várias técnicas de operações com matrizes implícitas no chamado Quadro Simplex.
· Goldbarg e Luna (2000) explicam que o algoritmo simplex soluciona problemas de equações lineares através de uma sequência de passos, optimizando uma função objectivo. Além disso, Cormen (1999) define o simplex como o algoritmo que examina uma sequência de pontos dentro de uma região viável e encontra a solução óptima. 
· Para Bronson (1985) o método simplex é um procedimento matemático matricial para resolução de modelos de programação linear na forma normal.
1. Uma inequação do tipo () converte-se em uma equação se for adicionada a variável de folga (excesso) no primeiro membro.
2. Um modelo de programação linear está na forma padrão (standard) se:
· Todas as restrições (com excepção das restrições de não negatividade) forem equações, com os valores do segundo membro não negativos;
· Todas as variáveis são não negativas;
· A função objectiva é do tipo de maximização ou minimização.
3. Para tornar o valor do segundo membro de uma inequação não negativo, multiplica-se
ambos os membros desta por (-1);
4. Se existe uma variável não restrita, ao passar o problema da PL para a forma padrão, esta variável deverá ser substituída por duas variáveis não negativas;
5. A maximização de é equivalente a minimizar .
Procedimento do Simplex
1. Tabela simplex inicial. A tabela simplex inicial para um problema de maximização
de programação linear é como se segue.
	V.básicas
(base)
	 … 
	 ... 
	Recursos-Termos
Independentes
	… 
	 … 
 ... 
……………..............
 ... 
	1 0 … 0
0 1 … 0
……………........
0 0 … 1
	 …
	Z 
	 ... 
	0 0 0
	 0
· Da tabela inicial, nota-se que as variáveis básicas (base) são todas variáveis de folga
ou de excesso;
· Os coeficientes , são opostos da função objectivo e são importantes na indicação da coluna pivô, por isso são chamados indicadores da coluna pivô;
· O elemento no canto inferior direito é zero, ele corresponde ao valor da função objectivo inicial.
2. Determinação do elemento pivô. Um elemento pivô de uma tabela simplex é obtido da seguinte forma:
· Escolhe-se na linha dos coeficientes da função objectivo, o maior elemento negativo (max) ou o maior elemento positivo (min), e a coluna que contém este elemento chama-se coluna pivô;
· Divide-se cada termo independente pelo correspondente elemento positivo da coluna pivô. A linha que apresentar o menor quociente positivo é chamada linha pivô;
· O elemento que situa-se no cruzamento entre a linha pivô e a coluna pivô é chamado elemento pivô.
Se a tabela não tem nenhum indicador negativo (max) ou positivo (min), esta é uma
tabela terminal e não tem pivô.
3. Cálculo da nova tabela simplex. Seja a tabela simplex com linhas e colunas, cujo elemento pivô é da matriz A. Uma nova tabela é calculada a partir da tabela , usando operações elementares sobre as linhas da matriz A de tal forma que apareça um “1” na posição pivô e zeros “0” nas outras posições da coluna pivô,.é:
Divide-se cada elemento da linha pivô da tabela T1 pelo elemento pivô , obtendo-se a correspondente linha na tabela T2 ().
Se a coluna pivô de é denotada por xi, então a correspondente coluna de , será denotada também por ;
Cada uma das outras linhas da tabela é obtida subtraindo o múltiplo conveniente da linha à linha , onde .
4. Interpretação da tabela terminal. Depois de tantas repetições das etapas (2) e (3), chega-se a uma tabela terminal, a qual não tem nenhum indicador de pivô negativo (max) ou positivo (min).
	V.básicas
(base)
	 … 
	 ... 
	Recursos-Termos
Independentes
	… 
	 … 
 ... 
……………..............
 ... 
	1 0 … 0
0 1 … 0
……………........
0 0 … 1
	 …
	Z 
	 ... 
	
	
· – é o valor óptimo da função objectivo;
· – tem uma raiz diferente de zero se estiver marcado por 1 numa única posição da coluna correspondente e zeros nas restantes linhas ( pertence a base);
· é igual a zero se não estiver na base, apresentando obviamente um .
Maximização com restrições da forma 
Os problemas de maximização com restrições da forma , são resolvidos aplicando-se o simpelx directo. Se houver alguma restrição da forma ou mesmo esta deverá ser transformada a forma canónica do problema de maximização.
Os passos gerais para os problemas de maximização são:
Passo 1. Escrevero problema na forma canónica ou na forma padrão;
Passo 2. Introduzir as variáveis de folga () e rescrever o sistema inicial na forma padrão;
Passo 3. Apresentar a tabela simplex inicial;
Passo 4. Se a tabela simplex inicial tiver algum valor negativo na linha da função objectivo e na coluna correspondente haver algum valor positivo, determinar o elemento pivô e realizar as operações necessárias para obter a nova tabela;
Passo 5. Repetir o processo do passo 4 até que todos os indicadores da linha sejam positivos. Assim chega-se à tabela terminal e deve-se interpretar a solução obtida.
Exemplo 3: Resolver o seguinte problema de programação linear pelo método simplex.
Maximizar 
Sujeito à 
Resolução
O problema já está na forma canónica, portanto, vai-se introduzir as variáveis de folga.
Maximizar 
Sujeito à 
Tabela simplex inicial
	Base 
	
	
	
	 1 1 1 1 0 0
 2 3 1 0 1 0
 1 3 2 0 0 1 
	11 ← 11/1 = 11
20 → 20/2 = 10 min
20 → 20/1 = 20
	
	-4 -2 -3 0 0
	0
1ª Iteração
	Base 
	
	
	
	 0 -1/2 1/2 1 -1/2 0
 1 3/2 1/2 0 1/2 0
 0 3/2 3/2 0 -1/2 1 
	1 ← 
10 → 
10 → 
	
	 0 4 -1 0 -2 0
	40 → 
2ª Iteração
	Base 
	
	
	
	 0 -1 1 2 -1 0
 1 2 0 -1 1 0
 0 3 0 -3 1 1
	2 → 
9 → 
7 → 
	
	 0 3 0 2 1 0
	42 → 
Solução: = 42, = 9, = 0, = 2, = 0, = 0, = 7 
Exemplo 4: Resolver o problema do alfaiate pelo método simplex.
Max 
Sujeito à 
Resolução
Max 
Sujeito à 
Tabela simplex inicial
	Base 
	
	
	
	 1 1 1 0 0
 1 2 0 1 0
 1 0 0 0 1 
	5 → 5/1 = 5
8 → 8/1 = 8
4 → 4/1 = 4 min
	
	-2 -1 0 0 0
	0
1ª Iteração 
	Base 
	
	
	
	 0 1 1 0 -1
 0 2 0 1 -1
 1 0 0 0 1 
	1 → 
4 → 
4 → 
	
	 0 -1 0 0 2
	8 →
2ª Iteração 
	Base 
	
	bi
	
	 0 1 1 0 -1
 0 0 -2 1 -1
 1 0 0 0 1 
	1→ 
2 → 
4 → 
	
	 0 0 1 1 2
	9→
Solução: = 9, = 4, = 1, = 0, = 2, = 0
Minimização com restrições da forma ≥
O processo iterativo do método simplex sempre exige uma solução básica inicial a partir da qual se busca uma solução óptima. Nos problemas de maximização esta solução básica inicial era formada pelas variáveis de folga, já que as restrições eram do tipo (). Quando as restrições são do tipo () ou (), não existe essa solução básica inicial.
NOTAS:
· Não é possível resolver estes problemas se apoiando do método simplex directo, pois poderia se dar o caso da violação da condição de não negatividade; 
· Para resolver este tipo de problemas são introduzidas algumas modificações nas equações
das restrições em seguida pode se usar o procedimento dual, os métodos de duas fases, de grande M e o Dual simplex, que são modificações do método simplex directo. 
Método de duas fases
Algoritmo duas fases
Para os problemas de minimização na forma canónica, o método simplex em duas fases
tem os seguintes passos:
Passo 1. Introduzir as variáveis de excesso () e artificiais () para cada restrição.
Passo 2. Criar uma nova função objectivo formada pela:
· Soma dos coeficientes das equações para a mesma variável tomados com o sinal negativo 
· Soma dos coeficientes das variáveis artificiais que é igual a zero;
· Nova função objectivo que é igual a soma dos termos independentes tomados com o sinal negativo )
Passo 3. Escreve-se a tabela inicial do simplex para a 1a fase do processo de resolução do
problema.
Passo 4. Aplica-se normalmente o procedimento do método simplex, tomando-se como função objectivo a última linha. Quando a solução óptima for atingida dois casos podem
ocorrer:
· : neste caso foi obtida uma solução básica do problema original e o processo de solução deve continuar, desprezando-se as variáveis artificiais e os elementos da
última linha. É o início da fase 2 do processo.
· : neste caso o problema original não tem solução viável. 
Exemplo 5. Resolva o seguinte problema pelo método de duas fases.
Uma companhia possuía, há 10 anos, duas minas: a mina A produzindo por dia 1 tonelada de minério de alto teor, 3 toneladas de minério de médio teor e 5 toneladas de minério de baixo teor; a mina B produzia por dia 2 toneladas de cada um dos teores. A companhia precisou de 80 toneladas de minério de alto teor, 160 de médio teor e 200 de baixo teor. Quantos dias cada mina funcionaram, se custava 200 u.m por dia para se fazer funcionar cada uma?
Resolução
	Teor
	Mina-A
	Mina-B
	Necessidade
	Alto
	1
	2
	80
	Médio
	3
	2
	160
	Baixo
	5
	2
	200
	Custo
	200
	200
	
Minimizar 
Sujeito à 
Minimizar 
Sujeito à 
Tabela inicial simplex
	Base 
	
	
	
	 1 2 -1 0 0 1 0 0
 3 2 0 -1 0 0 1 0
 5 2 0 0 -1 0 0 1
	20 →(80/1 = 80)
160 →(160/3 = 53.333…)
200 →(200/5 = 40)
	
	-200 -200 0 0 0 0 0 0
	0
	
	-9 -6 1 1 1 0 0 0
	-400
1a Fase (iteração 1)
	Base 
	
	
	
	 0 8/5 -1 0 1/5 1 0 -1/5
 0 4/5 0 -1 3/5 0 1 -1/2
 1 2/5 0 0 -1/5 0 0 1/4
	40 → = +
40 → = + 
40 → =
	
	 0 -120 0 0 -40 0 0 40
	8000 → = +
	
	 0 -12/5 1 1 -4/5 0 0 9/5
	-80 → = +
1a Fase (iteração 2)
	Base 
	
	
	
	 0 1 -5/8 0 1/8 5/8 0 -1/8
 0 0 1/2 -1 1/2 -1/2 1 -1/2
 1 0 1/4 0 -1/4 -1/4 0 1/4
	25 → =
20 → = + 
300 → = + 
	
	 0 0 -75 0 -25 75 0 25
	11000 → = + 
	
	 0 0 -1/2 1 -1/2 3/2 0 3/2
	-20 → = + 
1a Fase (iteração 3)
	Base 
	
	
	
	 0 1 -3/4 1/4 0 3/4 -1/4 0
 0 0 1 -2 1 2 2 -1
 1 0 1/2 -1/2 0 -1/2 1/2 0
	20 → =
40 → = 
40 → = + 
	
	 0 0 -50 -50 0 50 50 0
	12000 → = + 
	
	 0 0 0 1 0 1 1 1
	0 → = + 
Tabela inicial simplex (2a fase)
	Base 
	
	
	
	 0 0 -3/4 1/4 1
 0 1 1 -2 0
 1 0 1/2 -1/2 0
	20
40 
40
	
	 0 0 -50 -50 0 
	12000
Solução: = 12000, = 40, = 20, =0, = 0, = 40
Exemplo 6:. Resolver o problema pelo método de duas fases:
Minimizar 
Sujeito à 
Resolução
Sujeito à 
Tabela inicial simplex (1a fase)
	base 
	
	
	
	 3 1 -1 0 0 1 0 0
 4 3 0 -1 0 0 1 0
 1 2 0 0 -1 0 0 1
	3 →(1)
6 →(3/2)
3 →(3)
	
	-4 -1 0 0 0 0 0 0 
	0
	
	-8 -6 1 1 1 0 0 0 
	-121a Fase (Iteração 1)
	Base 
	
	
	
	 1 1/3 -1/3 0 0 1/3 0 0
 0 5/3 4/3 -1 0 -4/3 1 0
 0 5/3 1/3 0 -1 -1/3 0 1
	1→ = 1/3 (3)
2 → = -4 (6/5)
2 →  = - (6/5)
	
	 0 1/3 -4/3 0 0 4/3 0 0 
	4 →  = -4
	
	 0 -10/3 -5/3 1 1 8/3 0 0 
	-4→ = +8
1a Fase (Iteração 2)
	Base 
	
	
	
	 1 0 -3/5 1/5 0 3/5 -1/5 0
 0 1 4/5 -3/5 0 -4/5 3/5 0
 0 0 -1 1 -1 1 -1 1
	3/5→ = - 1/3 (3)
6/5 → = 3/5 (negativo)
0 → = - 5/3 (0)
	
	 0 0 -24/15 1/5 0 24/15 -1/5 0 
	18/5 → =- 1/3
	
	 0 0 1 -1 1 0 2 0 
	0 → = + 10/3
1a Fase (Iteração 3)
	base 
	
	
	
	 1 0 -2/5 0 1/5 -2/5 0 1/5
 0 1 1/5 0 -3/5 -1/5 0 3/5
 0 0 -1 1 -1 1 -1 1
	3/5 → = - 1/5
6/5→ = + 3/5
0 → =
	
	 0 0 -7/5 0 1/5 7/5 0 -1/5 
	18/5 → = - 1/5
	
	 0 0 0 0 0 1 1 1 
	0 → =+
Como na última linha o valor da função objectivo artificial é igual a zero, a fase 1 termina
e a solução encontrada é solução básica inicial para a fase 2.
Tabela inicial simplex (2a fase)
	base 
	
	
	
	 1 0 -2/5 0 1/5
 0 1 1/5 0 -3/5
 0 0 -1 1 -1
	3/5 → (3)
6/5 → (neg)
0 → (neg)
	
	 0 0 -7/5 0 1/5 
	18/5 
2a fase (iteração 1)
	base 
	
	
	
	 5 0 -2 0 1
 3 1 1 0 0
 5 0 -3 1 0
	3→ =5*
3→ = + 3/5
3→ =+
	
	 -1 0 -1 0 0 
	3 → = - 1/5
Solução: = 3, = 0, = 3, =0, = 3, = 3
Maximização e minimização com restrições do tipo 
De um modo geral, para problemas que contêm vários tipos de desigualdade deve-se:
Algoritmo geral (Mim = Maior igual menor)
Passo 1. Introduzir uma variável de folga () para cada restrição da forma ;
Passo 2. Introduzir uma variável de excesso () e uma variável artificial () para cada restrição da forma ;
Passo 3. Introduzir uma variável artificial () para cada restrição da forma . Atenção uma restrição do tipo () dá lugar a duas restrições da forma e , equivalendo a duas inequações uma com () outra com () caso seja necessário;
Passo 4. Para cada variável de folga e excesso adicionar e para cada variável artificial adicionar na função objectivo, onde M é um grande número positivo.
a) Problemas de Maximização
Geralmente problemas de maximização com restrições da forma são resolvidos pelo método de grande M. Este método não é um novo método, mas uma modificação do simplex directo
Algoritmo
Passo 1. Realizar o procedimento geral Mim e escrever o sistema na forma padrão
incluindo a função objectivo;
Passo 2. Na tabela preliminar simplex, passar para básicas as variáveis artificiais, i.é, procurar eliminar a constante M nas colunas ai até chegar a tabela simplex inicial com uma solução básica inicial viável.
Passo 3. Escolher um pivô e resolver o simplex, até que todos ci sejam positivos, ter-se-á uma tabela terminal.
Exemplo 7: Resolver o problema de maximização pelo método de grande M.
Maximizar 
Sujeito à 
Resolução
Maximizar 
Sujeito à 
Tabela preliminar simplex
	Base 
	
	
	-
	 1 2 0 0 0
 1 0 2 0 1
	4
5
	
	 -1 -2 -3 0 M 
	0
Tabela simplex inicial
	Base 
	
	
	
	 1 2 0 0 0
 1 0 2 0 1
	4→ =
5→ =
	
	 -M-1 -2 -2M-3 0 0
	-5M→ = – M*
1a Iteração
	Base 
	
	
	
	 1 2 0 1 0
 1/2 0 1 0 1/2
	4→ =
5/2→ =
	
	 1/2 -2 0 0 
	-5→ = – M*
2a Iteração
	Base 
	
	
	
	 1/2 1 0 1/2 0
 1/2 0 1 0 1/2
	4→ =1/2
5/2→ =
	
	 3/2 -2 0 1 
	23/2→ = +2
Solução: = 23/2, = 0, = 2, = 5/2, = 0
Observação: Como as variáveis artificiais não têm significado nenhum para o problema, e são iguais a zero na tabela terminal simplex, elas podem não figurar na solução.
b) Problemas de Minimização
Algoritmo 
Para os problemas de minimização com restrições da forma o método de grande M tem os seguintes passos:
Passo1. Dado um problema de PL com a função objectivo Min , deve-se converter a função objectivo em Max Z = - Min W = -i;
Passo 2. Escrever o sistema composto pela função Max Z = - e o conjunto das restrições originais;
Passo 3. Realizar o procedimento geral Mim e escrever o problema de maximização na forma padrão;
Passo 4. Realizar os passos p2 e p3 do caso de maximização. Chegada a tabela terminal simplex o valor da função objectivo será negativo, basta fazer W = -Z para obter o valor mínimo procurado .
Exemplo 8. Resolver o seguinte problema pelo método de Grande M.
Min 
Sujeito à 
Resolução
Max = - Min 
Sujeito à 
Tabela preliminar “1” simplex
	Base 
	
	
	
	 2 2 1 0 0 0 0
 3 0 0 -1 0 1 0
 0 1 0 0 -1 0 1
	8
3
2
	
	 2 1 0 0 0 M M
	0
Tabela preliminar “2” simplex
	Base 
	
	
	
	 2 2 1 0 0 0 0
 3 0 0 -1 0 1 0
 0 1 0 0 -1 0 1
	8→ =
3→ =
2→ =
	
	-3M+2 1 0 M 0 0 M
	-3M → = – M*
Tabela simplex inicial
	Base 
	
	
	
	 2 2 1 0 0 0 0
 3 0 0 -1 0 1 0
 0 1 0 0 -1 0 1
	8→ =
3→ =
2→ =
	
	-3M+2 -M 0 M M 0 M
	-5M → = – M*
1a Iteração
	Base 
	
	
	
	 2 2 1 0 0 0 0
 3 0 0 -1/3 0 1/3 0
 0 1 0 0 -1 0 1
	6→ =
1→ =1/3
2→ =
	
	 0 -M 0 2/3 M M-2/3 0
	-2M-2 → = + (3M-2)
2a Iteração
	Base 
	
	
	
	 0 0 1 2/3 2 -2/3 -2
 1 0 0 -1/3 0 1/3 0
 0 1 0 0 -1 0 1
	2→ =
1→ =1/3
2→ =
	
	 0 0 0 2/3 0 M-2/3 M
	-2 → = + M
Solução: = - = 2, = 1, = 2, =2, = 0,=0
Exemplo 9: Resolva o problema pelo método de Grande M
Maximizar Z = x1 - x2 + 3x3
Sujeito à 
Resolução
Sujeito à 
Tabela preliminar 1 simplex
	Base 
	
	
	-
-
	 1 1 0 1 0 0 0
 1 0 1 0 0 1 0
 0 1 1 0 -1 0 1
	20
5
10
	
	 -1 1 -3 0 0 M M 
	0
Tabela preliminar 2 simplex
	Base 
	
	
	-
	 1 1 0 1 0 0 0
 1 0 1 0 0 1 0
 0 1 1 0 -1 0 1
	20 → =
5 → =
10 → =
	
	-M-1 1 -M-3 0 0 0 M 
	-5M → = -M 
Tabela simplex inicial
	Base 
	
	
	
	 1 1 0 1 00 0
 1 0 1 0 0 1 0
 0 1 1 0 -1 0 1
	20 → =
5 → =
10 → =
	
	-M-1 -M+1 -2M-3 0 M 0 0 
	-15M → = -M 
Agora que tem-se a solução básica, pode-se procurar o pivô e optimizar a solução.
1a Iteração
	Base 
	
	
	
	 1 1 0 1 0 0 0
 1 0 1 0 0 1 0
 -1 1 0 0 -1 -1 1
	20 → =
5 → =
5 → =-
	
	M+2 -M+1 0 0 M 2M+3 0 
	15-5M → = +(2M-3)
2a Iteração
	Base 
	
	
	
	 2 0 0 1 1 1 -1
 1 0 1 0 0 1 0
 –1 1 0 0 -1 -1 1
	15 → =-
5 → =
5 → =
	
	 3 0 0 0 1 M+4 M-1 
	10 → = +(M-1)
Solução: = 10, = 0, = 5, =5, = 15, = 5 
CONCLUSÃO
O desenvolvimento do método simplex trouxe grande avanço para a programação linear. Como apresentou-se, o método simplex percorre as soluções básicas de um problema de PL, indo de um vértice a outro, definindo uma sequência de vértices com valores que se aproximam do óptimo. Esse método ainda é muito utilizado actualmente sendo sobrepujado por algoritmos de pontos interiores quando problema e de grande porte.
Apesar do bom desempenho do simplex, para problemas cuja dimensão é muito grande, esse algoritmo tem um custo operacional alto, pois levará muito tempo para a obtenção de uma solução óptima, o que, na prática, o torna inviável. Desse modo, é possível estudar-se novas “versões” do método de forma a obter uma solução em menos tempo computacional. O método simplex revisado, por exemplo, é um esquema que ordena os cálculos evitando operações desnecessárias, de forma a minimizar o tempo da computação. 
Foi também possível através deste trabalho ir ao encontro ou responder as espectativas estabelecidas nos objectivos, geral e específicos.
REFERÊNCIAS BIBLIOGRÁFICAS
ASSANE, Cachimo. Investigação Operacional. UEM-2018
BRONSON, R. - Pesquisa operacional. São Paulo: McGraw-Hill do Brasil, 1985.
CAIXETA-FILHO, José Vicente. Pesquisa Operacional. São Paulo: Atlas, 2001.
CARVALHO, João M. S. Introdução à Investigação Operacional. Bubok Publishing S.L., 2014
CORMEN, Thomas H. Introduction to algorithm. 23. ed. MIT: McGraw-Hill, 1999.
GOLDBARG, M. C.; LUNA, H. P. L. Optimização Combinatória e Programação Linear. 2 Ed. Editora Campus, 2000.
MULENGA, Alberto. Investigação Operacional- uma abordagem introdutória. Maputo, 2010.
PUCCINI, Abelardo de Lima. Introdução à programação linear. Rio de Janeiro: livros técnicos e científicos editora S.A, 1980.
2