TCC sobre Programação Linear

Prévia do material em texto

TCC LUCYAN
Matemática
Universidade Federal de Alagoas (UFAL)
45 pag.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
UNIVERSIDADE FEDERAL DE ALAGOAS
INSTITUTO DE MATEMÁTICA
O Problema de Programação Linear
Autor: José Lucyan Mendonça de Almeida
Orientador: Prof. Dimas Mart́ınez Morera
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
Programação Linear
José Lucyan Mendonça de Almeida
Trabalho de Conclusão de Curso
submetido ao Colegiado do Curso de
Graduação em Matemática da Universidade
Federal de Alagoas, como requisito parcial
para obtenção do t́ıtulo de Licenciado em
Matemática.
Banca Examinadora:
Prof. Dimas Mart́ınez Morera
Prof. Adán José Corcho Fernández
Profa. Luana Giarola Contiero
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
Agradecimentos
À minha mãe, pelo apoio incondicional em todos os momentos da minha vida.
Às minhas irmãs Luciana Mayara e Lucilayne Mendonça, pelos incentivos e momentos
de alegrias.
Ao professor Dimas, pela disposição, amizade, compreensão e paciência durante o
peŕıodo de orientação.
Aos meus amigos de graduação, pela convivência ao longo desses quatro anos.
A todos que, de alguma forma, contribúıram para minha formação acadêmica.
3
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
Sumário
1 Introdução 5
1.1 O Problema de Programação Linear . . . . . . . . . . . . . . . . . . . . . 6
1.2 Problemas Clássicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 O Problema do Caixeiro Viajante . . . . . . . . . . . . . . . . . . 6
1.2.2 O Problema da Dieta . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Modelagem 8
2.1 Modelo de Programação Linear . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Formulação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.1 O Problema da Dieta . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.2 O Problema do Fazendeiro . . . . . . . . . . . . . . . . . . . . . . 10
2.3.3 O Problema do Hospital . . . . . . . . . . . . . . . . . . . . . . . 12
3 O Método Gráfico 15
3.1 Interpretação Geométrica no R2: . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 Posśıveis Regiões Compat́ıveis . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3.1 O Problema do Fazendeiro . . . . . . . . . . . . . . . . . . . . . . 22
4 O Método Simplex 27
4.1 Teoremas Fundamentais . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2 O Que Faz o Método Simplex ? . . . . . . . . . . . . . . . . . . . . . . . 34
4.3 Problemas com Variáveis Irrestritas em Sinal . . . . . . . . . . . . . . . . 43
5 Conclusões 44
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
Caṕıtulo 1
Introdução
Acredita-se que o surgimento da Programação Linear ocorreu no peŕıodo da segunda
guerra mundial, onde diversos problemas táticos e estratégicos de origem militares foram
resolvidos. Nessa época, foram realizadas diversas pesquisas relacionadas à procura de
técnicas para usos administrativos no estabelecimento de programas ótimos e levanta-
mento de alternativas economicamente viáveis.
No entanto, o que havia de mais avançado dentro do campo de pesquisa, foram
os conceito formulados por Von Neumann em, 1928, sobre a aplicação do teorema do
mı́nimo-máximo aos jogos de estratégias. Posteriormente em 1941, Hitchcook desen-
volveu o problema do transporte, que também foi desenvolvido independentemente por
Koopmans em 1947. Por fim o problema de dieta formulado por Stigler em 1945 [1].
Em sua pesquisa em 1945, George Stigler formulou um problema de determinação de
uma dieta composta por 77 alimentos distintos contendo nove nutrientes com o menor
custo posśıvel. Descobriu que uma dieta perfeita seria composta apenas por farinha de
trigo, repolho e feijão branco seco com o mı́nimo de 39,93 dólares para o ano de 1939.
Já com os preços calculados em 1944, o feijão deve ser substitúıdo por f́ıgado de porco
para que a dieta custasse apenas 59,88 dólares naquele ano.
Estes problemas precursores tratavam sempre de otimizar uma função linear acom-
panhada por restrições lineares. Em 1947, um grupo de pesquisadores formado por
George B. Dantzig, Marshall Wood e colaboradores investigou técnicas matemáticas para
problemas militares de programação.
Percebeu-se que, de modo semelhante, diversos problemas do cotidiano poderiam ser
solucionados pelos métodos da programação linear. Inicialmente, grandes organizações
como companhias de petróleo adotaram o novo conjunto de metodologias para resolução
de seus problemas de decisão, avançando no planejamento da produção em larga escala
através da programação linear que, por sua vez, investiram em novos processos. Peque-
nas empresas que não podiam investir em pesquisa também se beneficiaram do uso da
programação linear.
5
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
6 CAPÍTULO 1. INTRODUÇÃO
Atualmente, vários pesquisadores apontam que o desenvolvimento da programação
linear é um dos avanços cient́ıficos mais importantes do século XX. Por ser uma ferra-
menta padrão bastante utilizada em grande parte de problemas de otimização, possibilita
enormes ganhos para grande parte da indústria e diversas aplicações que simplificam, de
forma fácil, problemas práticos da sociedade como: atribuição de tarefas, distribuições e
transporte, pesquisas de mercado, avaliações de cargos e salários, dosagem, movimentação
de materiais e planejamento da produção.
1.1 O Problema de Programação Linear
A programação linear fornece um método de resolução de problemas, baseado em con-
ceitos matemáticos, onde se apresenta um problema para o administrador e este escolhe
e realiza algum procedimento matemático para resolvê-lo. Todos os métodos conhecidos
procuram soluções que, em geral, possuem mais incógnitas do que equações lineares. Um
dos métodos mais adotados é o chamado método simplex.
Os problemas de programação linear tratam de um planejamento de atividades, com
a finalidade de atender a um determinado objetivo onde, em geral, pretende-se maxi-
mizar lucros e minimizar custos, sendo esse objetivo expresso por uma função linear
f : Rn → R que recebe o nome de função objetivo. Cada atividade do problema consome
uma quantidade espećıfica de cada recurso onde essas informações são dadas por equações
ou inequações lineares, uma para cada recurso. Chamamos essas equações e inequações
de restrições lineares do modelo.
Em outras palavras, resolver um problema de programação linear é determinar uma
solução que satisfaça às restrições do modelo e que otimize a função objetivo. Chamare-
mos essa solução de solução ótima. Assim, após formular o modelo linear e aplicar um
dos métodos de programação linear, será encontrada a solução ótima procurada.
1.2 Problemas Clássicos
Para termos uma idéia melhordo problema de programação linear, apresentamos
nesta seção, dois dos problemas clássicos que são frequentemente mencionados na litera-
tura de programação linear.
1.2.1 O Problema do Caixeiro Viajante
Este problema é um dos mais tradicionais e conhecidos de programação linear. Sua
origem vem de um jogo proposto por Willian Rowan Hamilton, em 1857, denominado
Around the World, feito sobre um dodecaedro em que cada vértice, estava associado a
uma cidade da época, onde o desafio era encontrar um percurso através dos vértices do
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
1.2. PROBLEMAS CLÁSSICOS 7
dodecaedro com inicio e fim numa dada cidade sem repetir uma visita [2].
A importância deste problema é caracterizada por uma grande aplicação prática com
inúmeras relações com outros modelos e pela dificuldade de se encontrar uma solução exa-
ta. Pela sua importância, ao longo da história, vários pesquisadores criaram formulações
para esse problema.
1.2.2 O Problema da Dieta
No ińıcio deste caṕıtulo, citamos o problema da dieta formulado por George Stigler.
Na época, Stigler descobriu quais seriam os alimentos para uma dieta perfeita a um custo
mı́nimo.
Este problema clássico pode ser associado a uma dieta para uma redução calórica, em
que, as quantidades de certos alimentos que devem ser ingeridos diariamente, de modo
que alguns requisitos nutricionais sejam rigorosamente obedecidos a um custo mı́nimo [3].
O objetivo deste problema é determinar a quantidade de cada alimento na dieta para
que o custo total das quantidades dos alimentos ingeridos seja mı́nimo, sabendo o custo
unitário e a quantidade mı́nima de vitamina que deve ser obtida de cada alimento.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
Caṕıtulo 2
Modelagem
Neste caṕıtulo, apresentamos como transformar problemas reais em modelos de pro-
gramação linear e, mostraremos alguns exemplos de modelagem.
2.1 Modelo de Programação Linear
Em geral, um problema de programação linear é disposto da seguinte maneira:
Maximizar ou minimizar uma função f(x) = c1x1 + c2x2 + · · ·+ cnxn, satisfazendo às
seguintes restrições:









a11x1 + a12x2 + · · · + a1nxn ≤ b1
a21x1 + a22x2 + · · · + a2nxn ≤ b2
...
...
...
...
am1x1 + am2x2 + · · · + amnxn ≤ bm
Em diversos problemas, além destas restrições, é necessário que se tenha condições de
não-negatividade: x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, . . . , xn ≥ 0, devido à possibilidade do problema
admitir apenas variáveis não-negativas.
A função f(x) é demoninada função objetivo, ci, aij e bi são os parâmetros do modelo,
onde cj são os coeficientes da função objetivo, aij são os coeficiente das restrições. Com
isso temos a seguinte definição:
Definição 2.1 A função principal, que deve ser otimizada num problema de Programação
Linear, recebe o nome de Função Objetivo.
Assim o objetivo do problema consiste em encontrar x ∈ Rn que maximize ou mini-
mize a função objetivo.
8
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
2.2. FORMULAÇÃO 9
Podemos representar este modelo de forma mais compacta:
Maximizar ou minimizar f(x) =
n
∑
j=1
cjxj, satisfazendo às restrições:
n
∑
j=1
aijxj ≤ bi , (i = 1, 2, . . . ,m)
e
xj ≥ 0 , (j = 1, 2, . . . , n).
Ou ainda, na notação matricial:
Maximizar ou minimizar f(x) = cx sujeito a
Ax ≤ b e x ≥ 0, onde:
A =





a11 a12 · · · a1n
a21 a22 · · · a2n
...
...
. . .
...
am1 am2 · · · amn





, x =





x1
x2
...
xn





, b =





b1
b2
...
bn





e c =
[
c1 c2 · · · cn
]
.
Qualquer problema de maximização pode ser convertido num problema de mini-
mização, uma vez que maximizar f(x) é equivalente a minimizar −f(x).
2.2 Formulação
Apresentamos um modelo de organização para elaboração de modelos de programação
linear baseados nos seguintes passos:
1. Iniciamos com uma análise das atividades que criam o problema, escolhendo a
unidade de medida mais conveniente.
2. Definimos os recursos dispońıveis e produtivos de cada atividade, estabelecendo a
relação do recurso pela unidade de medida produzida por cada atividade.
3. Determinamos as quantidades de cada recurso dispońıvel, sabendo que tais recursos
são limitados. Em seguida, formularemos o modelo.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
10 CAPÍTULO 2. MODELAGEM
2.3 Exemplos
A seguir apresentaremos alguns exemplos de problemas reais com suas respectivas
modelagens.
2.3.1 O Problema da Dieta
Considere o problema da dieta, como apresentado na introdução em que quantidades
de certos alimentos devem ser ingeridos diariamente, satisfazendo requisitos nutricionais
mı́nimos, a um custo mı́nimo.
Vamos considerar, para cada i = 1, 2, . . . ,m e para cada j = 1, 2, . . . , n, as seguintes
variáveis:
• xj a quantidade do alimento j na dieta.
• cj o custo unitário do alimento j.
• bi a quantidade mı́nima da vitamina i que deve ser obtida dos n alimentos.
• aij a quantidade da vitamina i que deve ser obtida do alimento j.
O objetivo deste problema é determinar x1, x2, x3, . . . , xn que minimizem a função
objetivo f(x) = c1x1 + c2x2 + · · · + cnxn , de modo que x1, x2, x3, . . . , xn satisfaçam às
restrições:









a11x1 + a12x2 + · · · + a1nxn ≥ b1
a21x1 + a22x2 + · · · + a2nxn ≥ b2
...
...
...
...
am1x1 + am2x2 + · · · + amnxn ≥ bm
e às condições de não-negatividade:
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, . . . , xn ≥ 0.
Assim f(x) = c1x1 + c2x2 + · · · + cnxn representa o custo bruto, em Reais, da quan-
tidade do alimento consumido e as restrições lineares indicam que o total da vitamina i
obtida dos n alimentos deve ser maior ou igual à quantidade mı́nima bi desta vitamina.
2.3.2 O Problema do Fazendeiro
Um fazendeiro deseja aumentar seus lucros nas plantações de trigo e soja em sua
propriedade. Sabendo que o lucro, por unidade de área plantada de trigo é de 3 unidades
monetárias e que o lucro, por unidade de área plantada de soja é de 5 unidades monetárias
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
2.3. EXEMPLOS 11
e, por questões internas, as áreas plantadas de trigo e soja não podem ultrapassar 4
unidades de área, e 6 unidades de área, respectivamente. Além disso, para cada unidade
de área plantada de trigo, são necessários 3 homens e na outra cultura, são necessários 2
homens. O total de homens trabalhando em cada hora em ambas, plantações não pode
ser maior que 18 trabalhadores.
Apresentamos, a seguir, a modelagem de programação linear para que o lucro nas
plantações seja máximo. Isto reduz-se a encontrar as áreas de trigo e soja que devem ser
plantadas respectivamente.
Modelagem:
Escolha das variáveis:
x1 ≡ quantidade de unidades de área de trigo a serem plantadas e,
x2 ≡ quantidade de unidades de área de soja a serem plantadas.
Elaboração da função objetivo:
f(x) = 3x1 + 5x2.
Formulação das Restrições:
• Restrição associada à área plantada de trigo:
x1 ≤ 4;
• Restrição associada à área plantada de soja:
x2 ≤ 6;
• Restrição associada ao total de homens em cada hora:
3x1 + 2x2 ≤ 18;
• Restrição associada à não-negatividade.x1 ≥ 0, e x2 ≥ 0 .
Logo, para este exemplo o modelo ficará disposto da seguinte forma:
Maximizar f(x) = 3x1 + 5x2, sujeito a:











x1 ≤ 4
x2 ≤ 6
3x1 + 2x2 ≤ 18
x1 ≥ 0
x2 ≥ 0.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
12 CAPÍTULO 2. MODELAGEM
2.3.3 O Problema do Hospital
O diretor de um hospital deve escolher um esquema de designação de leitos e quartos
em um nova ala que será constrúıda∗. Existe três tipos de quartos posśıveis:
• Com um leito,
• Com dois leitos,
• Com três leitos.
O total de quartos a construir não pode ultrapassar 70. Por imposições de demanda,
deverão ser oferecidos mais de 120 leitos. A porcentagem de quartos de um leito deve ser
restrita entre 15 a 30% do total de quartos. A necessidade em área constrúıda é de:
• 10 m2 por quarto de um leito,
• 14 m2 por quarto de dois leitos,
• 17 m2 por quarto de três leitos.
Os pacientes dos quartos com dois e três leitos exigem apenas 80% da mão-de-obra
em apoio médico e administrativo do que os dos quartos individuais. O que o hospital
recebe por cada paciente internado é inversamente proporcional à capacidade do número
de pessoas do quarto em que ele está internado.
Vejamos uma modelagem de programação linear para os casos a seguir, considerando
o hospital sempre lotado:
1. Minimizar o esforço de mão-de-obra,
2. Maximizar a arrecadação global,
3. Maximizar o número de leitos,
4. Minimizar o espaço necessário para a nova ala.
Modelagem:
Escolha das variáveis:
xi ≡ quantidade de quartos com i leitos.
∗Este problema foi retirado do livro MIRSHAWKA, Victor. Programação Linear, 1.ed. São Paulo:
Nobel S.A. 1971
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
2.3. EXEMPLOS 13
Elaboração das funções objetivos:
• 1◦ Caso: Minimizar o esforço de mão-de-obra em apoio médico e administrativo.
Neste caso, temos que minimizar f(x) = x1 + 0, 8x2 + 0, 8x3;
• 2◦ Caso: Maximizar a arrecadação global.
Neste caso, temos que maximizar f(x) = 3(x1 + x2 + x3);
• 3◦ Caso: Maximizar o número de leitos.
Neste caso, temos que maximizar f(x) = x1 + 2x2 + 3x3;
• 4◦ Caso: Minimizar o espaço necessário para a nova ala.
Neste caso, temos que minimizar f(x) = 10x1 + 14x2 + 17x3.
Formulação das Restrições:
• Restrição associada ao total de quartos:
x1 + x2 + x3 ≤ 70;
• Restrição associada ao total de leitos:
x1 + 2x2 + 3x3 ≥ 120;
• Restrição associada à porcentagem de quartos com um leito:
Total ≡ T =
3
∑
i=1
xi. Logo,
xi ≥ 0, 15T ⇔ 100x1 ≥ 15(x1 + x2 + x3) ⇔ 85x1 − 15x2 − 15x3 ≥ 0
⇔ 17x1 − 3x2 − 3x3 ≥ 0;
E ainda,
xi ≤ 0, 30T ⇔ 100x1 ≤ 30(x1 + x2 + x3) ⇔ 70x1 − 15x2 − 15x3 ≤ 0
⇔ 14x1 − 3x2 − 3x3 ≤ 0;
• Resrição associada à não negatividade:
x1 ≥ 0, x2 ≥ 0 e x3 ≥ 0.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
14 CAPÍTULO 2. MODELAGEM
Com isso cada função objetivo ficará sujeita a:



















x1 + x2 + x3 ≤ 70
x1 + 2x2 + 3x3 ≥ 120
17x1 − 3x2 − 3x3 ≥ 0
14x1 − 3x2 − 3x3 ≤ 0
x1 ≥ 0
x2 ≥ 0
x3 ≥ 0.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
Caṕıtulo 3
O Método Gráfico
Neste caṕıtulo, mostramos o método gráfico para resolução de problemas de pro-
gramação linear. Este método possui uma aplicação bastante restrita, pois só podemos
resolver problemas com, no máximo, três variáveis. Assim, este método torna-se im-
praticável, visto que diversos problemas do cotidiano possuem muitas variáveis. Por
outro lado, este método servirá para uma melhor compreensão do método simplex, usa-
do na resolução de problemas de programação linear, que será apresentado no caṕıtulo
seguinte.
3.1 Interpretação Geométrica no R2:
Suponha que desejamos maximizar a função f(x) = c1x1 + c2x2 sujeita às restrições:









a1,1x1 + a1,2x2 ≤ b1
a2,1x1 + a2,2x2 ≤ b2
...
...
ar,1x1 + ar,2x2 ≤ br
Definição 3.1 Dizemos que o conjunto de todas as soluções posśıveis do problema de
Programação Linear, ou seja, as soluções que obedecem todas Às restrições é a Região
Compat́ıvel do problema.
Nosso primeiro objetivo é construir a região compat́ıvel no sistema de coordenadas
x1ox2. Assim, para cada uma das desigualdades acima, traçamos a reta ai1x1+ai2x2 = bi,
onde i = 1, . . . , r no plano x1ox2.
Para sabermos em qual dos dois semi-planos estará a provável região compat́ıvel do
problema, procederemos da seguinte forma:
15
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
16 CAPÍTULO 3. O MÉTODO GRÁFICO
Inicialmente, traçamos no plano x1ox2 a reta ai1x1 + ai2x2 = ai0 que o divide em dois
semi-planos.
Considere P um ponto arbitrário do plano x1ox2. Podemos verificar, sem dificul-
dades, que qualquer ponto do semi-plano que o contém satisfaz ai1x1 + ai2x2 ≤ bi ou
ai1x1 + ai2x2 ≥ bi. A outra desigualdade é satisfeita por qualquer ponto Q do outro
semi-plano. Além disso, qualquer ponto desta reta satisfaz à equação ai1x1 + ai2x2 = bi.
Figura 3.1: O semi-plano selecionado é o que contém o ponto P .
Assim, para sabermos qual é o semiplano que satisfaz a cada desigualdade, escolhemos
arbitrariamente um ponto qualquer do plano x1ox2. Se tal ponto satisfizer à desigual-
dade, então o semi-plano ficará voltado para este ponto. Senão, ficará voltado para o
lado oposto. Neste trabalho, indicamos o semi-plano escolhido por setas direcionadas
para o mesmo, como mostrado na figura (3.1).
Agora, representamos graficamente a equação f(x) = c1x1 + c2x2. Considere esta
equação para um certo f0 ∈ R fixado. Logo, a equação f0 = c1x1 + c2x2 define uma reta
no plano x1ox2 e, fazendo f(x) variar no conjunto dos números reais, temos uma famı́lia
de retas paralelas a esta. A figura (3.2) ilustra um caso particular onde c1 > 0 e c2 > 0.
Observe que o vetor V = (c1, c2) é perpendicular a todas essas retas e indica o sentido
e a direção do crescimento de f(x). Além disso, todos os pontos situados numa mesma
reta possuem o mesmo valor. Por essa razão, tais retas são denominadas retas de ńıvel
da função f(x).
Então, para cada restrição do problema, desenhamos sua reta correspondente e iden-
tificamos o semi-plano que satisfaz à desigualdade. Dessa forma, podemos perceber qual
é a região do plano que corresponde à região compat́ıvel do problema.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
3.1. INTERPRETAÇÃO GEOMÉTRICA NO R2: 17
Figura 3.2: Duas de suas retas de ńıvel da função f(x).
Definição 3.2 Dizemos que qualquer atribuição de valores para as variáveis do modelo
é uma Solução.
Definição 3.3 A solução que satisfaz a todas as restrições do modelo considerado, ou
seja, pertence à região compat́ıvel do modelo, é definida como Solução Compat́ıvel.
É na região compat́ıvel que estão todos os pontos candidatos a serem o ponto ótimo,
ou seja, o ponto que satisfaz a todas as restrições lineares do modelo e que otimiza sua
função objetivo.
Definição 3.4 Dizemos que a solução pertencente à região compat́ıvel do modelo e que
otimiza o valorda função objetivo é a Solução Ótima.
Definição 3.5 A solução que não satisfaz a alguma das restrições do modelo considera-
do é definida como Solução Incompat́ıvel.
Como já foi observado, a equação da função objetivo f(x) = c1x1 + c2x2 representa,
graficamente, uma famı́lia de retas paralelas. Então, inicialmente, na região compat́ıvel
do problema, constrúımos a reta f0 = c1x1 + c2x2 para algum f0 ∈ R fixado. A figura
(3.3) ilustra a idéia desta tal construção numa região genérica e limitada.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
18 CAPÍTULO 3. O MÉTODO GRÁFICO
Figura 3.3: A reta f0 = c1x1 + c2x2 numa região genérica e limitada do plano x1ox2.
Como nossa pretensão é maximizar o valor da função objetivo, podemos observar no
gráfico que, para qualquer ponto (x1, x2) da reta f0 = c1x1 + c2x2, existem outros pontos
que ainda maximizam esta função.
Então, podemos escolher outro valor arbitrário fi ∈ R, e, de maneira análoga, traçar
a reta fi = c1x1 + c2x2.
Como o vetor V = (c1, c2) é perpendicular à famı́lia destas retas e indica a direção
do crescimento de f(x), procedendo dessa forma por um número finito de vezes, encon-
traremos um ponto S = (x1, x2) na região compat́ıvel no plano x1ox2 que maximiza a
função objetivo. Veja figura (3.4):
Figura 3.4: O ponto S maximiza a função objetivo.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
3.2. POSSÍVEIS REGIÕES COMPATÍVEIS 19
Observação 3.1 Veremos, a seguir, que encontrar este ponto S vai depender da região
das posśıveis soluções do conjunto de restrições lineares associado ao problema que pode
ser: vazia, ter apenas um ponto, ser um poĺıgono convexo, ou ainda, uma região poligonal
convexa ilimitada.
Observação 3.2 O ponto S, que maximiza a função objetivo, é um dos vértices da região
compat́ıvel do problema. No caṕıtulo seguinte, mostraremos que isto sempre acontece, ou
seja, que este ponto é sempre obtido em um dos vértices desta região, a não ser quando
o problema admite múltiplas soluções ótimas.
3.2 Posśıveis Regiões Compat́ıveis
Antes de apresentarmos um exemplo, destacaremos os posśıveis casos de regiões
compat́ıveis do sistema de desigualdade da restrição associada ao problema, que podem
ocorrer nos diversos problemas de programação linear.
Seja dado um problema de programação linear. Os seguintes casos mostram como
podem ser as suas regiões compat́ıveis.
1◦ Caso:
Suponha que a restrição associada a um determinado problema seja:







x1 + 2x2 ≤ 3
−3x1 + x2 ≥ 2
x1 ≥ 0
x2 ≥ 0.
Inicialmente, observamos que x1 ≥ 0 e x2 ≥ 0 , ou seja , se existir uma solução que
otimiza a função objetivo, deve pertencer ao primeiro quadrante do plano x1ox2. Em
seguida, constrúımos a região do plano que satisfaz as duas primeiras inequações. Veja
figura (3.5). Com essa construção, podemos concluir que a região compat́ıvel deste pro-
blema é vazia.
2◦ Caso:
Suponha que a restrição associada a um segundo problema seja:







x1 + x2 ≤ 3
−x1 + x2 ≥ 3
x1 ≥ 0
x2 ≥ 0.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
20 CAPÍTULO 3. O MÉTODO GRÁFICO
Como no caso anterior, x1 ≥ 0 e x2 ≥ 0. Logo, se existir uma solução que otimiza
a função objetivo, também deve pertencer ao primeiro quadrante do plano x1ox2. Em
seguida, constrúımos a região do plano que satisfaz às duas primeiras inequações. Veja
figura (3.6). Assim, conclúımos que a região compat́ıvel deste problema é constitúıda por
uma única solução, o ponto (3, 0).
Figura 3.5: Região compat́ıvel do 1o caso. Figura 3.6: Região compat́ıvel do 2o caso.
3◦ Caso:
Suponha que a restrição associada a um terceiro problema seja:



















x1 − 2x2 ≤ 4
x1 + 2x2 ≥ 3
x1 + 5x2 ≥ 5
2x1 − 3x2 ≤ 6
3x1 − x2 ≥ 0
x1 ≥ 0
x2 ≥ 0.
Como nos casos anteriores, x1 ≥ 0 e x2 ≥ 0. Logo, se existir uma solução que otimiza
a função objetivo, também deve pertencer ao primeiro quadrante do plano x1ox2. Cons-
trúımos, conforme a seção anterior, a região do plano que satisfaz a todas as inequações
do sistema acima. Veja figura (3.7).
Para este problema, o sistema de desigualdades corresponde a uma região limitada
do plano x1ox2. Logo, podemos concluir que a região compat́ıvel deste problema é um
poĺıgono convexo.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
3.2. POSSÍVEIS REGIÕES COMPATÍVEIS 21
Figura 3.7: Região compat́ıvel do 3o caso.
4◦ Caso:
Suponha que a restrição associada a um quarto problema seja:











x1 + x2 ≥ 2
x1 − x2 ≥ 0
x1 − 3x2 ≤ 3
x1 ≥ 0
x2 ≥ 0.
Como nos casos precedentes, x1 ≥ 0 e x2 ≥ 0. Então novamente, se existir uma
solução que otimiza o problema, também deve pertencer ao primeiro quadrante do plano
x1ox2. Análogo ao caso anterior, constrúımos a região deste plano que satisfaz às ine-
quações do sistema acima. Veja figura (3.8). Para este último problema, o sistema de
desigualdades corresponde a uma região ilimitada do plano x1ox2. Logo, a região com-
pat́ıvel deste problema é um conjunto ilimitado.
Em resumo, as posśıveis regiões compat́ıveis de um sistema de desigualdades podem
ser: vazia, possuir um ponto apenas, ser um poĺıgono convexo ou ainda uma região
poligonal convexa ilimitada. Nos dois últimos casos, dependendo da função objetivo, o
problema poderá admitir infinitas soluções.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
22 CAPÍTULO 3. O MÉTODO GRÁFICO
Figura 3.8: Região compat́ıvel do 4o caso.
3.3 Exemplo
Nesta seção, apresentamos um exemplo real de problema de programação linear que
pode ser resolvido graficamente.
3.3.1 O Problema do Fazendeiro
Retomemos ao problema do fazendeiro do caṕıtulo anterior, cujo objetivo é maximizar
f(x) = 3x1 + 5x2, sujeito às seguintes restrições lineares:











x1 ≤ 4
2x2 ≤ 12
3x1 + 2x2 ≤ 18
x1 ≥ 0
x2 ≥ 0.
Inicialmente, devemos observar que x1 ≥ 0 e x2 ≥ 0, ou seja, se existir um ponto que
maximiza a função objetivo, este ponto deve estar no primeiro quadrante do plano x1ox2.
Para construir a região que satisfaz a desigualdade x1 ≤ 4, traçamos a reta x1 = 4 no
plano x1ox2 e escolhemos um ponto arbitrário (a origem por exemplo). Como (0,0) está
à esquerda desta reta e 0 ≤ 4, o semi-plano escolhido é o que está à esquerda desta reta.
Veja figura (3.9):
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
3.3. EXEMPLO 23
Figura 3.9: Representação do semi-plano que satisfaz à desigualdade x1 ≤ 4.
De maneira análoga, encontramos a região que obedece à restrição 2x2 ≤ 12. A figura
(3.10) ilustra a região que satisfaz a ambas restrições.
Figura 3.10: Região que satisfaz às desigualdades x1 ≤ 4 e 2x2 ≤ 12.
Em seguida, construimos a região que satisfaz a desigualdade 3x1 + 2x2 ≤ 18. Ini-
cialmente, traçamos a reta 3x1 +2x2 = 18 e, novamente, escolhemos um ponto arbitrário
(novamente a origem). Como (0,0) está abaixo desta reta e 3 ·0+2 ·0 ≤ 18, o semi-plano
escolhidoé o que está abaixo desta reta.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
24 CAPÍTULO 3. O MÉTODO GRÁFICO
A figura (3.11) ilustra a região que satisfaz a todas as restrições do problema. Se
existir um ponto que maximiza a função objetivo, deve pertencer ao trapézio ABCDE.
Figura 3.11: Região que satisfaz a todas as restrições do problema.
Desejamos encontrar uma solução para maximizar f(x) = 3x1 + 5x2, donde sabemos
que graficamente representa uma famı́lia de retas paralelas. Então, escolhemos um valor
arbitrário para f(x). Por exemplo, f(x) = 9. Observe que, através dos pontos (3,0)
e (0,2.25), podemos traçar uma das retas pertencentes a esta famı́lia tal que f(x) = 9.
Analisando a figura (3.12), vemos que existem pontos do espaço solução, não pertencentes
a esta reta, que nos dão um maior valor para f(x). Logo, podemos escolher um valor
ainda maior para f(x).
Figura 3.12: A reta 3x1 + 5x2 = 9 na região compat́ıvel do problema.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
3.3. EXEMPLO 25
Observe que, através dos pontos (5,0) e (0,3), podemos traçar outra reta desta famı́lia
tal que f(x) = 15 que, como já sabemos, é paralela à anterior. Novamente, observamos
que ainda existem pontos do espaço solução que nos dão um maior valor para f(x). Veja
figura (3.13):
Figura 3.13: As retas 3x1 + 5x2 = 9 e 3x1 + 5x2 = 15 na região compat́ıvel do problema.
Procedendo desse modo por um número finito de vezes, encontraremos um ponto do
espaço solução que maximiza f(x). Veja figura (3.14):
Figura 3.14: O ponto C maximiza a função objetivo.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
26 CAPÍTULO 3. O MÉTODO GRÁFICO
Observe que o ponto que maximiza f(x) é o vértice C do trapézio, que forma a
região compat́ıvel do problema, e pertentence, simultaneamente, às retas 2x2 = 12 e
3x1 + 2x2 = 18. Logo, resolvendo o sistema destas equações encontramos C = (2, 6).
No caṕıtulo seguinte, mostraremos que isto sempre acontece, isto é, se existir um ponto
que maximiza a função objetivo, sempre estará num dos vértices da região compat́ıvel,
exceto quando f(x) = c1x1 + c2x2 for paralelo a um dos lados da região compat́ıvel do
problema onde, neste caso, teremos infinitas soluções.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
Caṕıtulo 4
O Método Simplex
Neste caṕıtulo, apresentamos um algoritmo mundialmente conhecido desenvolvido
para encontrar algebricamente a solução ótima de um problema de programação linear,
manualmente ou com o uso de programas computacionais. Tal algoritmo foi apresentado
pelo matemático americano George B. Dantizing em 1947 e é denominado Método Sim-
plex [4].
Mostramos que, se existir uma solução ótima para o problema de programação linear,
este algoritmo, com um número finito de operações sempre conseguirá encontrá-la.
4.1 Teoremas Fundamentais
Antes de apresentar o método simplex, mostramos alguns teoremas fundamentais
para o funcionamento deste algoritmo [3].
Definição 4.1 Sejam A1, A2, . . . , An pontos pertencentes ao R
m e α1, α2, . . . , αn ∈ R+,
tais que
n
∑
i=1
αi = 1. Dizemos que o ponto b = αiA1+α2A2+. . .+αnAn é uma Combinação
Convexa dos pontos A1, A2, . . . , An.
Um subconjunto C ∈ Rm é convexo se, e somente se, para todos os pontos A1 e A2
pertencentes a C, qualquer Combinação Convexa b = αiA1 + α2A2 também pertencer a
C.
Em outras palavras, se C é convexo então:
A1 ∈ C
A2 ∈ C
}
⇒
{
x = αA1 + (1 − α)A2 ∈ C
0 ≤ α ≤ 1
, onde A1 6= A2.
27
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
Exemplos:
Figura 4.1: Somente as duas primeiras figuras são convexas.
Lema 4.1 Sejam C1, C2, . . . , Cn conjuntos convexos, então C = ∩
n
i=1Ci é convexo.
Demonstração:
Se C = ∅ então C é convexo. Caso contrário, tomemos x1, x2 ∈ C arbitrários e
0 ≤ α ≤ 1.
Como x1, x2 ∈ Ci para todo i = 1, . . . , n e, por hipótese, C1, C2, . . . , Cn são conjuntos
convexos, temos:
x = α1x1 + α2x2 ∈ Ci para todo i = 1, . . . , n.
Logo, x ∈ C. E, como tomamos x1, x2 ∈ C arbitrários, temos que C é um conjunto
convexo.
Definição 4.2 Dados a1, a2, . . . , an, b ∈ R, chamamos de Semi-espaço a reunião dos pon-
tos pertencentes ao conjunto X = {(x1, x2, . . . , xn) ∈ R
n; a1x1 + a2x2 + · · · + anxn ≤ b}.
Lema 4.2 Todo Semi-espaço é um conjunto convexo.
Demonstração:
Considere y = (y1, y2, . . . , yn) e z = (z1, z2, . . . , zn) dois pontos distintos do conjunto
X definido acima.
Afirmação: (1 − α) y + αz ∈ X, onde 0 ≤ α ≤ 1, ou seja, a1 ((1 − α) y1 + αz1) +
a2 ((1 − α) y2 + αz2) + · · · + an ((1 − α) yn + αzn) ≤ b.
Com efeito, sendo y ∈ X e (1 − α) ≥ 0 temos que:
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
4.1. TEOREMAS FUNDAMENTAIS 29
a1y1+a2y2+· · ·+anyn ≤ b ⇒ (1 − α) ay1+(1 − α) a2y2+· · ·+(1 − α) anyn ≤ (1 − α) b.
Por outro lado, como z ∈ X e α ≥ 0, temos que:
a1z1 + a2z2 + · · · + anzn ≤ b ⇒ αa1z1 + αa2z2 + · · · + αanzn ≤ αb.
Assim,
a1 ((1 − α) y1 + αz1)+a2 ((1 − α) y2 + αz2)+ · · ·+an ((1 − α) yn + αzn) ≤ (1 − α) b+
αb = b.
Isto mostra que todo semi-espaço é um conjunto convexo.
Teorema 4.1 O conjunto de todas as soluções compat́ıveis do problema de programação
linear é um conjunto convexo.
Demonstração:
Segue imediatamente dos lemas 4.1 e 4.2.
Definição 4.3 Um ponto x de um conjunto convexo C é um Ponto Extremo se não exis-
tirem dois pontos distintos, x1 e x2 em C, tais que, para algum α (0 < α < 1), tivermos
x = αx1 + (1 − α)x2.
Exemplos:
Figura 4.2: Os pontos destacados das figuras são pontos extremos.
Definição 4.4 Chamamos de Solução Básica à solução obtida quando em um conjunto
com m equações linearmente independentes e n incógnitas, tal que n > m, consideramos
o conjunto de equações onde, n − m variáveis são anuladas e, as que sobraram são en-
contradas através da resolução do sistema de equações.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
30 CAPÍTULO 4. O MÉTODO SIMPLEX
Teorema 4.2 Toda solução compat́ıvel básica do sistema Ax = b é um ponto extremo
do conjunto das soluções compat́ıveis, ou seja, do conjunto convexo do teorema (4.1).
Demonstração:
Considere o conjunto convexo formado por
Ax = b e x ≥ 0, (4.1)
ou seja:




a11 · · · a1m a1m+1 · · · a1n
a21 · · · a2m a2m+1 · · · a2n
· · · · · · · · · · · · · · · · · ·
am1 · · · amm amm+1 · · · amn









x1
x2
...
xn





=





b1
b2
...
bn





. (4.2)
Considere a solução compat́ıvel básica formada pelo vetor x, de dimensão n:
x =









x1
...
xm
0
...
0









, com todos os xi ≥ 0.
Suponha que x não seja um ponto extremo do conjunto (4.1). Então, x pode ser obtido
como uma combinação convexa de outros dois pontos distintos do conjunto. Sendo y e z
dois pontos quaisquer desse conjunto, podemos ter:
x = αy + (1 − α)z;0 ≤ α ≤ 1. (4.3)
Além das seguintes relações:
Ay = b, Az = b, y ≥ 0 e z ≥ 0.
Caso x seja um ponto extremo do conjunto (4.1), não existem y e z, distintos de x
que satisfaçam à relação (4.3).
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
4.1. TEOREMAS FUNDAMENTAIS 31
Colocando esta relação em termos das coordenadas de cada um dos três vetores, te-
remos:
x1 = αy1 + (1 − α)z1
x2 = αy2 + (1 − α)z2
...
...
...
...
...
...
...
...
...
...
xm = αym + (1 − α)zm
0 = αym+1 + (1 − α)zm+1
...
...
...
...
...
...
...
...
...
...
0 = αyn + (1 − α)zn.
(4.4)
Devido às relações 0 ≤ α ≤ 1, y ≥ 0 e z ≥ 0, as últimas (n − m) relações de (4.4) só
podem ser satisfeitas num dos seguintes casos:
1. 0 < α < 1 e ym+i = zm+i = 0 para i = 1, . . . , n − m.
Neste caso, seria obrigatório ter x = y = z, pois as três soluções apresentam uma
coincidência nas variáveis não-básicas do sistema (4.2). Por consequência, os valo-
res das variáveis básicas serão os mesmos para essas três soluções;
2. α = 0 e zm+i = 0 para i = 1, . . . , n − m.
Pelas razões anteriores, teŕıamos x = z;
3. α = 1 e ym+i = 0 para i = 1, . . . , n − m.
Também, pelas razões anteriores, teriamos x = y.
Isto mostra que não existem soluções compat́ıveis y e z, distintas das soluções com-
pat́ıveis básicas x, que satisfaçam à relação (4.3). Então o ponto x é, de fato, um ponto
extremo do conjunto convexo (4.1).
Teorema 4.3 Se a função objetivo admitir um máximo (mı́nimo) finito, então ao menos
uma solução ótima é um ponto extremo do conjunto convexo do teorema (4.1).
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
32 CAPÍTULO 4. O MÉTODO SIMPLEX
Demonstração:
Considere o conjunto convexo C definido por (4.1). Seja f(x) a função objetivo que
assume o valor máximo M no ponto x0, ou seja:
f(x0) ≥ f(x), para todo x ∈ C.
Sejam x̄1, x̄2,. . . , x̄p os pontos extremos do conjunto C. Temos que provar que x0 é
um desses pontos extremos.
Suponha que x0 não seja um ponto extremo de C. Então, ele pode ser obtido pela
combinação convexa abaixo:
x0 =
p
∑
i=1
αix̄i (4.5)
onde
p
∑
i=1
αi = 1
e
αi ≥ 0 (i = 1, . . . , p).
Usando a relação (4.5), podemos obter:
f(x0) = f(
p
∑
i=1
αix̄i) = f(α1x̄1 + α2x̄2 + · · · + αpx̄p)
= α1f(x̄1) + α2f(x̄2) + · · · + αpf(x̄p) = M. (4.6)
Considere,agora, o ponto extremo x̄M definido pela equação abaixo:
f(x̄M) = max f(x̄i) (4.7)
com i = 1, . . . , p.
Devido às relações (4.5) e (4.7), podemos fazer na relação (4.6), as seguintes modi-
ficações:
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
4.1. TEOREMAS FUNDAMENTAIS 33
f(x0) ≤ α1f(x̄M) + α2f(x̄M) + · · · + αpf(x̄M),
ou seja,
f(x0) ≤ f(x̄M)
p
∑
i=1
αi,
isto é,
f(x0) ≤ f(x̄M),
mas t́ınhamos
f(x0) ≥ f(x) para todo x ∈ C.
Então, é necessário ter f(x0) = M = f(x̄M) o que mostra que a solução ótima xo é
um ponto extremo do conjunto convexo C.
Teorema 4.4 Se a função objetivo assumir o máximo (mı́nimo) em mais de um ponto
extremo, então assume o mesmo valor para qualquer combinação convexa desses pontos
extremos.
Demonstração:
Sejam x̄1, x̄2,. . . , x̄q os pontos extremos do conjunto C nos quais assume-se que
f(x̄1) = f(x̄2) = · · · = f(x̄q) = M. (4.8)
Considere, agora, a combinação convexa
x =
q
∑
i=1
αixi (4.9)
onde
q
∑
i=1
αi = 1
e
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
34 CAPÍTULO 4. O MÉTODO SIMPLEX
αi ≥ 0 (i = 1, . . . , q).
Temos que:
f(x) = f(
q
∑
i=1
αix̄i) = f(α1x̄1 + α2x̄2 + · · · + αqx̄q)
= α1f(x̄1) + α2f(x̄2) + · · · + αqf(x̄p) (4.10)
e, pelas equações (4.8) e (4.9), obtemos:
f(x) = M
q
∑
i=1
αi = M .
4.2 O Que Faz o Método Simplex ?
Retornemos ao problema do fazendeiro do segundo caṕıtulo, cujo objetivo é maximizar
f(x) = 3x1 + 5x2 sujeito às seguintes restrições lineares:











x1 ≤ 4
2x2 ≤ 12
3x1 + 2x2 ≤ 18
x1 ≥ 0
x2 ≥ 0.
(4.11)
Acrescentando as variáveis x3, x4 e x5 nas restrições do modelo, transformamos o
sistema de inequações acima no seguinte sistema de equações lineares formado por 3
equações e 5 variáveis:



x1 + x3 = 4
2x2 + x4 = 12
3x1 + 2x2 + x5 = 18.
(4.12)
Observe que as variáveis x3, x4 e x5 acrescentadas são não-negativas.
Definição 4.5 As variáveis acrescentadas em inequações para torná-las equações são
denominadas Variáveis de Folga.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
4.2. O QUE FAZ O MÉTODO SIMPLEX ? 35
No caṕıtulo anterior, mostramos graficamente que a solução ótima deste modelo é o
ponto C = (2, 6) do trapézio A, B, C, D, E, ou seja, uma solução compat́ıvel básica do
sistema de equações (4.11).
Figura 4.3: Região que satisfaz a todas as restrições do problema.
O objetivo desta seção é mostrar, através do método simplex, que este mesmo ponto
C = (2, 6) é o que maximiza a função objetivo.
Definição 4.6 Dizemos que são Variáveis Básicas as variáveis que não foram anuladas
para se obter uma solução básica.
Definição 4.7 As n−m variáveis anuladas para obter a solução básica serão chamadas
de Variáveis Não-básicas.
O Método Simplex pesquisa a solução ótima entre as soluções básicas compat́ıveis,
através de um processo iterativo, de modo que o valor da função objetivo decresça em
cada iteração para os problemas de minimização e cresça para os problemas de maxi-
mização. Considere um problema de programação linear na sua forma matricial:
Minimizar f(x) = cx sujeito a Ax = b e x ≥ 0.
Podemos transformar a função objetivo f(x) = c1x1 + c2x2 + . . . + cnxn na equação
f(x) − c1x1 − c2x2 − · · · − cnxn = 0 sendo, então, posśıvel escrever o problema na tabela
(4.1):
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
36 CAPÍTULO 4. O MÉTODO SIMPLEX
Equação f(x) x1 x2 · · · xn b
0 1 −c1 −c2 · · · −cn 0
1 0 a11 a12 · · · a1n b1
2 0 a21 a22 · · · a2n b2
...
...
...
...
. . .
...
...
n 0 am1 am2 · · · amn bm
Tabela 4.1:
O algoritmo requer uma solução compat́ıvel básica inicial. Sem perda de generalida-
de, supomos que tal solução esteja relacionada ao conjunto de ı́ndices J = {1, 2, . . . ,m}.
Usando o método da Eliminação de Gauss-Jordan, é posśıvel obter a tabela (4.2):
Eq. Base f(x) x1 x2 · · · xm xs · · · xn b
0 1 0 0 · · · 0 cs · · · cn f(x)
1 x1 0 1 0 · · · 0 a1s · · · a1n b1
2 x2 0 0 1 · · · 0 a2s · · · a2n b2
...
...
...
...
...
. . .
...
...
. . .
...
...
m xm 0 0 0 · · · 1 ams · · · amn bm
Tabela 4.2:
Como sabemos, as últimas n-m variáveis são anuladas para obtermos a solução básica
inicial. Analisando a tabela (4.2), vemos que esta solução é dada por:
xi = bi, se 1 ≤ i ≤ m e xi = 0, se m + 1 ≤ i ≤ n.
Da equação zero, cosntante na tabela (4.2), temos f(x) + csxs + . . . + cnxn = f(x).
Logo o valor da função objetivo é f(x) = f(x). Além disso, b ≥ 0 por se tratar de uma
solução compat́ıvel.
Se cj ≤ 0 para todo j /∈ J , então o valor da função objetivo em qualquer outra solução
compat́ıvel básica é maior ou igual a f(x). Portanto,a solução básica atual é a ótima e
o método termina.
Suponha que existe, pelo menos, uma componente cj > 0 e seja ck = max{cj; cj > 0}.
Então, a variável não básica xk terá seu valor aumentado, porque, é ela que promove
uma maior diminuição da função objetivo. Portanto, passará a ser uma das variáveis
básicas. No entanto, esse aumento não pode ser arbitrário, para não tornar negativa
nenhuma das atuais variáveis básicas.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
4.2. O QUE FAZ O MÉTODO SIMPLEX ? 37
Definição 4.8 A coluna abaixo do coeficiente da variável que está entrando na base é
denominada Coluna Pivô.
Assim, xk deverá assumi algum valor α ≥ 0 tal que









x1 = b1 − a1kα ≥ 0
x2 = b2 − a2kα ≥ 0
...
...
xm = bm − amkα ≥ 0.
(4.13)
Se aik ≤ 0, para todo 1 ≤ i ≤ m, então α pode aumentar indefinidamente e, dessa
maneira a solução do problema será ilimitada.
Se, pelo contrário, existir um i ∈ {1, . . . ,m} tal que aik > 0, então α tem que satis-
fazer à condição:
α ≤ bi
aik
,∀ i ∈ {1, . . . ,m} tal que aik > 0.
Seja br
ark
= min{ bi
aik
; ais > 0}.
Se xk assumir o valor
α = br
ark
, então xr = 0, tornando-se variável não básica no lugar de xk.
Na tabela de eliminação, troca-se xk por xr, obtendo-se uma nova solução compat́ıvel
básica, à qual está associado um valor da função objetivo dado por:
f(x) − ck
br
ark
≤ f(x).
O processo é repetido até que obtenhamos a solução ótima.
Definição 4.9 Dizemos que a linha correspondente à equação da variável que está saindo
da base é a Linha Pivô.
Definição 4.10 É definido como Número Pivô o coeficiente que está, tanto na linha,
como na coluna pivô.
As três definições precedentes são úteis nos cálculos quando passamos de uma tabela
para outra. Resumidamente, o Método Simplex é composto dos seguintes passos:
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
38 CAPÍTULO 4. O MÉTODO SIMPLEX
1. Seja x uma solução básica compat́ıvel inicial associada a um conjunto J ;
2. Se cj ≤ 0, para todo j /∈ J , finalize pois x é a solução ótima. Senão, determine ck
a partir de ck = min{cj; cj > 0};
3. Se aik ≤ 0, ∀ 1 ≤ i ≤ m, finalize pois o problema é ilimitado. Senão, calcule r a
partir de
br
ark
= min{ bi
aik
; ais > 0}.
Atualize o conjunto J para J → (J − {t})∪{k} sendo t a variável básica associada
à r-ésima linha na tabela. Lembrando que para a atualização da tabela usamos o
método da Eliminação de Gauss-Jordan e volte ao Passo 1.
Assim o método simplex para ser iniciado precisa conhecer pelo menos um solução
compat́ıvel básica do sistema de equações (4.12), ou seja, um dos ponto A, B, C, D, E do
trapézio. Chamaremos esta solução de solução básica inicial.
Suponha que se conheça uma solução inicial. Por simplicidade escolhemos o ponto
A = (0, 0) para ser a solução inicial. O método simplex verifica se esta tal solução é a
ótima. Em caso afirmativo, o processo é encerrado. Senão, é porque um de seus pontos
extremo adjacentes fornece um valor para a função objetivo maior do que o atual neste
ponto. Este ponto fornece para função objetivo o valor f(x) = 0.
O método simplex substitui o atual ponto para o ponto extremo adjacente que mais
aumente o valor da função objetivo, ou seja, ou o ponto B ou o ponto E do trapézio
acima. Como no ponto B = (0, 6) a função objetivo assume valor f(x) = 30 e no ponto
E = (4, 0) a mesma função assume valor f(x) = 12 o método simplex substitui o ponto
A = (0, 0) pelo ponto B = (0, 6).
Agora para este novo ponto o simplex faz o mesmo que foi feito no ponto anterior. O
processo termina quando num certo ponto extremo for verificado que todos seus pontos
extremos adjacentes fornecem valores menores para a função objetivo. É o que aconte-
cerá no próximo passo quando o ponto B = (0, 6) for substitúıdo pelo ponto C = (2, 6),
pois como já vimos o ponto A = (0, 0) fornece um valor menor para a função objetivo do
que o atual ponto que está sendo considerado e, no ponto C = (2, 6) a função objetivo
assume valor f(x) = 36.
Estando no ponto C = (2, 6) o simplex verifica o valor da função objetivo em seus
pontos extremos adjacentes. No ponto D = (4, 3) o valor da função objetivo é f(x) = 29
que é menor que o valor atual, e como já vimos anteriormente o ponto B = (0, 6) também
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
4.2. O QUE FAZ O MÉTODO SIMPLEX ? 39
fornece um valor menor do que o atual ponto considerado.
Então de fato é o ponto C = (2, 6) que maximiza a função objetivo fornecendo um
valor máximo f(x) = 36. Isto apenas confirma o que já sab́ıamos do caṕıtulo anterior.
Agora iremos resolver algebricamente o problema do fazendeiro que deseja maximizar
f(x) = 3x1 + 5x2 sujeito as restrições lineares:











x1 ≤ 4
2x2 ≤ 12
3x1 + 2x2 ≤ 18
x1 ≥ 0
x2 ≥ 0.
(4.14)
Já vimos que com o acréscimo das variáveis de folga x3, x4 e x5 em cada restrição do
modelo o sistema de inequações (4.14) foi transformado no sistema de equações lineares
(4.12) formado por 3 equações e 5 variáveis. Lembre-se que todas as variáveis de folga
acrescentadas são positivas.
Vamos utilizar as tabelas do método simplex em problemas de programação linear.
Inicialmente no sistema de equações (4.12) acrescentamos a equação da função objetivo
obtendo o seguinte sistema de equações:







f(x) − 3x1 − 5x2 = 0
x1 + x3 = 4
2x2 + x4 = 12
3x1 + 2x2 + x5 = 18.
(4.15)
Observe que para este sistema de equações cada solução básica terá 5 - 3 = 2 variáveis
não básicas iguais a zero. Neste algoritmo obtemos a solução básica inicial fazendo as
variáveis iniciais do modelo de variáveis não-básicas. Por conveniência colocamos o sis-
tema (4.15) de maneira esquemática na tabela (4.3):
Equação Base f(x) x1 x2 x3 x4 x5 b
0 1 -3 -5 0 0 0 0
1 x3 0 1 0 1 0 0 4
2 x4 0 0 2 0 1 0 12
3 x5 0 3 2 0 0 1 18
Tabela 4.3:
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
40 CAPÍTULO 4. O MÉTODO SIMPLEX
Esta tabela possui os coeficientes das variáveis, as constantes do lado direito e a
variável básica que aparece em cada equação.
Note que cada equação possui apenas uma variável básica com coeficiente diferen-
te de zero (e igual a 1). Com isso cada variável básica será igual à constante do
lado direito de sua equação. Dessa forma a solução básica inicial para este problema
é (x1, x2, x3, x4, x5) = (0, 0, 4, 12, 18).
Para sabermos se esta solução é a ótima analizaremos o critério de parada. Observe
que a atual solução compat́ıvel básica é ótima se e somente se cada coeficiente da primeira
equação for não-negativo. Como neste problema existem dois coeficientes negativos na
primeira equação a solução encontrada não é a ótima.
Também podeŕıamos ter notado que esta solução não é ótima observando que os
valores atuais de x1 e x2 fornecem f(x) = 0 e se alguma variável não-básica entrar na
base aumentará o valor da função objetivo pois tomarão algum valor positivo. Assim
temos que transformar uma variável não-básica numa variável básica e, transformar uma
variável básica numa variável não-básica.
Temos que escolher qual destas duas variáveis deve torna-se uma variável básica. Se
escolhemos x1 para ser a variávelbásica o valor da função objetivo irá aumentar em 3
unidades para cada unidade de x1. Por outro lado, se escolhemos x2 para ser a variável
básica o valor da função objetivo irá aumentar em 5 unidades para cada unidade de x2.
Seja qual for a nova solução básica teremos um maior valor para f(x) do que a solução
básica atual. Com isso escolhemos x2 para se tornar uma variável básica. Se tivéssemos
escolhido a variável x1 o simplex nos levaria ao mesmo resultado, possivelmente fazendo
mais cálculos.
Agora temos que escolher uma das atuais variáveis básicas para torná-la variável
não-básica. Para isto selecionamos cada coeficiente na coluna pivô que seja estritamente
positivo e calculamos a razão entre o valor lado direito de cada equação pelo coeficiente
correspondente. Sairá da base a variável que estiver na linha que possuir a menor razão.
Com isso é a variável x4 que sai da base. A variável x3 foi descartada porque possui valor
zero na coluna pivô.
Determinamos uma nova solução compat́ıvel básica construindo uma nova tabela
simplex abaixo da atual. Inicialmente nesta nova tabela constrúımos as três primeiras
colunas trocando apenas na segunda coluna a variável x4 que está saindo da base pela
variável básica x2 que está entrando na base. Lembre-se que temos que transformar o
coeficiente da nova variável básica para + 1. Para isto é suficiente dividir todos os coefi-
cientes da linha pivô pelo número pivô. Dessa forma a nova linha pivô é igual à antiga
linha pivô dividido pelo número pivô. Veja a tabela (4.4):
Para completar a nova tabela simplex temos que eliminar a nova variável básica das
outras equações. Para isto podemos utilizar a idéia usada no método da eliminação de
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
4.2. O QUE FAZ O MÉTODO SIMPLEX ? 41
Equação Base f(x) x1 x2 x3 x4 x5 b
0 f(x) 1 -3 -5 0 0 0 0
1 x3 0 1 0 1 0 0 4
2 x4 0 0 2 0 1 0 12
3 x5 0 3 2 0 0 1 18
0 f(x) 1
1 x3 0
2 x2 0 0 1 0
1
2
0 6
3 x5 0
Tabela 4.4:
Gauss-Jordan, ou seja:
Linha Nova = Linha Antiga - (Coeficiente da Coluna Pivô) × Linha Pivô Nova.
Veja tabela (4.5):
Equação Base f(x) x1 x2 x3 x4 x5 b
0 f(x) 1 -3 -5 0 0 0 0
1 x3 0 1 0 1 0 0 4
2 x4 0 0 2 0 1 0 12
3 x5 0 3 2 0 0 1 18
0 f(x) 1 -3 0 0 5
2
0 30
1 x3 0 1 0 1 0 0 4
2 x2 0 0 1 0
1
2
0 6
3 x5 0 3 0 0 -1 1 6
Tabela 4.5:
Como cada variável básica é igual ao lado direito de sua equação, a nova solução
compat́ıvel básica é dada por (x1, x2, x3, x4, x5) = (0, 6, 4, 0, 6), sendo f(x) = 30. Note
que na primeira equação ainda existe um coeficiente negativo. Assim a solução ótima não
foi encontrada ainda e devemos novamente transformar uma variável não-básica numa
variável básica uma variável básica numa variável não-básica. Observe na primeira linha
que apenas o coeficiente da variável x1 é negativo, logo esta deverá tornar-se uma das
variáveis básicas.
Novamente temos que escolher uma das atuais variáveis básicas para torná-la variável
não-básica. Procedendo como anteriormente selecionamos cada coeficiente da nova colu-
na pivô que seja estritamente positivo e calculamos a razão entre o valor lado direito de
cada equação pelo coeficiente correspondente. Após fazer isto conclúımos que a variável
x5 deve sair da base atual.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
42 CAPÍTULO 4. O MÉTODO SIMPLEX
Agora temos que determinar uma nova solução compat́ıvel básica. Como anterior-
mente constrúımos uma nova tabela simplex abaixo da atual sendo que nas três primeiras
colunas trocando apenas na segunda coluna a variável x5 que está saindo da base pela
variável básica x1 que está entrando na base. E além disto, temos que transformar o
coeficiente da nova variável básica para + 1 dividindo todos os coeficientes da nova linha
pivô pelo novo número pivô. Veja a tabela (4.6):
Equação Base f(x) x1 x2 x3 x4 x5 b
0 f(x) 1 -3 -5 0 0 0 0
1 x3 0 1 0 1 0 0 4
2 x4 0 0 2 0 1 0 12
3 x5 0 3 2 0 0 1 18
0 f(x) 1 -3 0 0 5
2
0 30
1 x3 0 1 0 1 0 0 4
2 x2 0 0 1 0
1
2
0 6
3 x5 0 3 0 0 -1 1 6
0 f(x) 1
1 x3 0
2 x2 0
3 x1 0 1 0 0 −
1
3
1
3
2
Tabela 4.6:
Procedendo como anteriormente eliminamos a nova variável básica das outras equações
e completamos a nova tabela simplex (4.7):
Equação Base f(x) x1 x2 x3 x4 x5 b
0 f(x) 1 -3 -5 0 0 0 0
1 x3 0 1 0 1 0 0 4
2 x4 0 0 2 0 1 0 12
3 x5 0 3 2 0 0 1 18
0 f(x) 1 -3 0 0 5
2
0 30
1 x3 0 1 0 1 0 0 4
2 x2 0 0 1 0
1
2
0 6
3 x5 0 3 0 0 -1 1 6
0 f(x) 1 0 0 0 3
2
1 36
1 x3 0 0 0 1
1
3
−1
3
2
2 x2 0 0 1 0
1
2
0 6
3 x1 0 1 0 0 −
1
3
1
3
2
Tabela 4.7:
Visto que cada variável básica é igual ao lado direito de sua equação, a nova solução
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
4.3. PROBLEMAS COM VARIÁVEIS IRRESTRITAS EM SINAL 43
compat́ıvel básica é dada por (x1, x2, x3, x4, x5) = (2, 6, 2, 0, 0), com f(x) = 36. Como
na primeira equação todos os coeficientes são não-negativo podemos concluir que encon-
tramos a solução ótima.
Então a solução ótima é de fato x1 = 2 e x2 = 6 ou seja o ponto C = (2, 6) do
trapézio da solução geométrica do caṕıtulo anterior. O valor da função objetivo neste
ponto é f(x) = 36.
4.3 Problemas com Variáveis Irrestritas em Sinal
Definição 4.11 São definidas como variáveis irrestritas em sinal as variáveis que podem
assumir qualquer valor.
Suponha que desejamos resolver o seguinte problema de programação linear:
Minimizar f(x) = x1 + 4x2 + 2x3 + x4 sujeito a:







x1 + 4x2 + 9x3 + x4 ≤ 8
2x1 + 5x2 + 2x3 + 6x4 ≤ 14
2x1 + 3x2 + 2x3 + 5x4 ≤ 26
x1, x2, x3 ≥ 0
, sendo x4 irrestrita em sinal.
Vimos que o método simplex não admite variáveis negativas e por isso é imposśıvel
resolver este problema através do método. Mas se lembrarmos que qual quantidade ne-
gativa pode ser representada com a diferença entre duas quantidades positivas, podemos
trocar convenientemente a variável x4 por x4 = x5 − x6.
Logo problema fica disposto da seguinte forma:
Minimizar f(x) = x1 + 4x2 + 2x3 + x5 − x6 sujeito a:







x1 + 4x2 + 9x3 + x5 − x6 ≤ 8
2x1 + 5x2 + 2x3 + 6x5 − 6x6 ≤ 14
2x1 + 3x2 + 2x3 + 5x5 − 5x6 ≤ 26
x1, x2, x3, x5, x6 ≥ 0.
Após obtermos a solução ótima pelo método simplex calculamos o valor ótimo de x4
através dos valores ótimos de x5 e x6 fazendo x2 = x5 − x6.
Existem ainda problemas de programação linear com restrições do tipo xi ≤ b, onde
b ≤ 0. Como esta variável pode assumir apenas alguns valores negativos não podemos
resolver o problema pelo simplex. Mas podemos intruduzir uma variável xj não existente
no problema tal que xj = xi + b. Substitúımos cada xi do problema por xj − b e consi-
derando xj ≥ 0, obtemos o valor ótimo de xi através do valor ótimo de xj.
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
Caṕıtulo 5
Conclusões
Por apresentar uma grande aplicabilidade no cotidiano, a programação linear está
presente em inúmeras situações de otimizações, principalmente na área econômica. Por
isso a importância de ter uma satisfatória familiaridade com tais problemas.
Nos problemas abordados, a programação linear possibilitou a realização de um plane-
jamento adequado para tomadas de decisões corretas, principalmente para a maximização
de receitas e minimização de custos.
Neste trabalho, usamoso método simplex para a resolução de problemas de pro-
gramação linear, assim como a resolução geométrica para os problemas que envolvem, no
máximo, três variáveis.
Além dessas perspectivas, a programação linear está envolvida em aplicações em que,
apenas a solução ótima é insuficiente, sendo necessário um estudo do efeito na solução
ótima, ao serem considerados alterações dos parâmetros do problema, a chamada análise
de sensibilidade.
Suas aplicações mais aprofundadas, juntamente com o método simplex, introduzem
novas aplicações, entre elas, podemos destacar o estudo do problema dual, resoluções de
problemas não-lineares e multi-objetivos, como também a operação de pivotação carac-
teŕıstica do algoritmo de Gauss-Jordan-Chio, que é denominado algoritmo Simplex-Chio.
44
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
Referências Bibliográficas
[1] MIRSHAWKA, Victor. Programação Linear , 1.ed. São Paulo: Nobel S.A. 1971
[2] GOLDBARG, Marcos Cesar.; LUNA, Henrique Pacca L. Otimização Combi-
natória e Programação Linear , 6.ed.Rio de Janeiro: Campus 2000.
[3] PUCCINI, Abelardo de Lima. Introdução à Programação Linear , 1.ed.Rio de
Janeiro: Livros técnicos e cient́ıficos Editora S.A. 1972
[4] SANTOS, Mauŕıcio Perreira dos.Programação Linear.
45
Document shared on www.docsity.com
Downloaded by: jose-lucyan-mendonca-de-almeida-4 (joselucyan@gmail.com)
https://www.docsity.com/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark