DESCRIÇÃO

O método simplex para a solução de modelos de programação linear e a utilização do solver na solução de problemas de

programação linear.

PROPÓSITO

Dominar a solução de problemas de programação linear, seja por meio do método simplex, ou pela utilização de

softwares, permitirá que você aplique a técnica de modelagem no processo de decisão de problemas complexos de

diversas origens, em especial em sua atuação profissional.

PREPARAÇÃO

Para o conteúdo deste tema, são necessários uma calculadora e um software editor de planilhas eletrônicas com o add-in

do solver habilitado.

OBJETIVOS

MÓDULO 1
Processing math: 100%
 Empregar o método simplex para a solução de problemas de programação linear

MÓDULO 2

Aplicar o solver para solução de problemas de programação linear

INTRODUÇÃO

A modelagem matemática nos permite representar, de forma simplificada, um problema complexo por meio de linguagem

matemática. Com isso, conseguimos analisar diferentes cenários de forma mais rápida e barata do que se a situação

fosse avaliada na realidade, auxiliando-nos, assim, no processo de tomada de decisão.

No contexto da programação linear, que se aplica, por exemplo, no planejamento de redes logísticas, há métodos, como o

método gráfico, que se restringem à solução de problemas com apenas duas ou no máximo três variáveis de decisão.

Como solucionar, então, problemas mais complexos, com maior número de variáveis de decisão? Este é o assunto a ser

tratado neste tema. A seguir, abordaremos o método simplex para a solução de problemas de programação linear e

aprenderemos a utilizar o solver do Excel para a solução desse tipo de problema!

MÓDULO 1

 Empregar o método simplex para a solução de problemas de programação linear

APRESENTAÇÃO DO TEMA
Processing math: 100%
 O vídeo aborda o método simplex e sua importância para a resolução de problemas.

O MÉTODO SIMPLEX PARA A SOLUÇÃO DE MODELOS DE

PROGRAMAÇÃO LINEAR

Podemos resolver, de forma simples, problemas de programação linear com duas variáveis de decisão por meio do

método gráfico. Entretanto, são poucos os problemas de programação linear no mundo real que envolvem apenas duas

variáveis de decisão, de modo que a aplicação do método gráfico é bastante limitada.

ENTÃO, COMO FAZEMOS PARA SOLUCIONAR PROBLEMAS MAIS

COMPLEXOS, COM UM MAIOR NÚMERO DE VARIÁVEIS DE
DECISÃO?

Existe uma série de técnicas matemáticas para resolver problemas de programação linear com qualquer número de

variáveis sem a necessidade de visualizar em gráficos as regiões viáveis. Dentre tais técnicas, destaca-se o algoritmo

simplex, que foi o primeiro método desenvolvido para resolver problemas de programação linear.

O algoritmo simplex foi desenvolvido por George B. Dantzig, em 1947, enquanto trabalhava como consultor em

matemática para o controle da Força Aérea norte-americana. O método simplex é específico para a solução de problemas

de otimização linear (equações ou inequações lineares). Trata-se de um algoritmo eficiente que se baseia na solução

sucessiva de sistemas de equações indeterminados, em que sistemas adjacentes são avaliados de forma iterativa, sendo,

assim, adaptável ao cálculo computacional. Na época, os computadores estavam começando a surgir, e a resolução

desse tipo de problema se tornava importante na prática!

O simplex é considerado uma das grandes contribuições à programação matemática.

Antes de estudarmos o algoritmo simplex, é importante entendermos o conceito do simplex e recordarmos alguns pontos

sobre a solução de problemas de programação linear com duas variáveis de decisão por meio do método gráfico.

O QUE É UM SIMPLEX?
Processing math: 100%
 Um simplex é um polígono convexo, ou seja, com propriedade especial: uma reta que passe por quaisquer dois pontos

pertencentes a um simplex deve estar contida inteiramente dentro do simplex. Logo, na figura a seguir, observa-se que o

polígono representado em (a) não é convexo, enquanto o ilustrado em (b) é um simplex.

Fogliato (2006, p. 33) adaptado por Renata Albergaria de Mello Bandeira.

 Polígono não convexo e polígono simplex.

As restrições de um problema de programação linear sempre definem hiperespaços convexos. Esta é a premissa do

algoritmo simplex e de boa parte da teoria de otimização convexa. Assim, o espaço de soluções de um problema de

programação linear, ou seja, a área formada pela intersecção das restrições do problema, é uma forma geométrica

simplex.

MÉTODO GRÁFICO

Para encontrar a solução ótima pelo método gráfico, precisamos seguir os seguintes passos:

Desenhe as retas correspondentes às restrições do problema e encontre o espaço de soluções.


Desenhe o vetor z (função objetivo).


Desenhe linhas ortogonais ao vetor z. Essas são as linhas de isocusto, isto é, são as retas que têm o mesmo valor de z.


Calcule o valor de z no ponto ótimo, ou seja, a linha de isocusto com maior z que ainda pertence ao espaço de soluções.

Em um caso bidimensional, o espaço de soluções viáveis é um plano, e a função objetivo é representada por um vetor.

Assim, por meio do método gráfico, buscamos a reta (x2 = z - ax1) perpendicular ao vetor da função objetivo com o maior

(ou menor) z possível dentro do espaço de soluções. Como o espaço de soluções é simplex, a reta x2 = z - ax1 para z ótimo

que corta o plano, obrigatoriamente, corta as retas de restrições. Ainda, como nos pontos de interseção (vértices) temos

mudança de inclinação (retas diferentes), garante-se que a solução ótima se dá na interseção entre retas de restrições

(nos vértices), de modo que o algoritmo simplex analisa apenas os pontos de interseção do espaço de soluções.

Processing math: 100%

 Na verdade, esta foi a grande ideia de Dantzig para o desenvolvimento do algoritmo simplex: dado que a solução ótima

está em um vértice do espaço de soluções viáveis, por que não percorrê-los em busca da melhor solução possível?

MÉTODO SIMPLEX

Conforme verificamos, a chave do algoritmo simplex está no formato da região limitada pelas restrições. Portanto, apesar

de ser um procedimento algébrico, os conceitos subjacentes ao método simplex são geométricos.

O simplex é um algoritmo iterativo, que se utiliza de um ferramental baseado em álgebra linear para a resolução sucessiva

de sistemas de equações, embora as restrições de problemas de programação matemática sejam tipicamente

inequações. Desse modo, a primeira etapa do método simplex consiste em converter as restrições de desigualdade em

restrições de igualdade equivalente. O algoritmo simplex só pode ser rodado se o problema estiver escrito na forma

canônica, que é a forma de se representar programas matemáticos por meio de equações. Para isso, precisamos criar as

chamadas variáveis de folga ou de excesso.

VARIÁVEIS DE FOLGA (F)

Exemplo (forma canônica):

𝑥1 ≤ 10 → 𝑥1 + 𝑓1 = 10

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

𝑓1 = Variável de folga

Assim, se 𝑥1 = 8, então teríamos que a variável de folga 𝑓1 seria igual a 2. Se 𝑥1 = 3, então teríamos que a variável de folga

𝑓1 seria igual a 7.

VARIÁVEIS DE EXCESSO (E)

Exemplo (forma canônica):

𝑥1 ≥ 10 → 𝑥1 - 𝑒1 = 10

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

𝑒1 = Variável de excesso

Assim, se 𝑥1 = 12, então teríamos que a variável de excesso e1 seria igual a 2. Se 𝑥1 = 15, então teríamos que a variável de

excesso 𝑒1 seria igual a 5.

Veja o caso do problema da Fitwear, apresentado a seguir. Será que conseguimos escrevê-lo em sua forma canônica?

Caso Fitwear S/A

A Fitwear S/A é uma confecção de roupas esportivas, tendo uma linha fitness feminina, na qual produz roupas de

ginástica exclusivas para mulheres, como tops e calças de lycra.

Processing math: 100%
 Cada top de ginástica é vendido por R$80,00 e utiliza R$20,00 de matéria-prima, como tecido e alinhamentos, e R$32,00

de mão de obra. Trinta minutos de corte e 15 minutos de costura são demandados para a confecção de um top de

ginástica.

Cada calça de ginástica é vendida por R$120,00 e utiliza R$35,00 de matéria-prima, como tecido e alinhamentos, e

R$40,00 de mão de obra. Quinze minutos de corte e 30 minutos de costura são demandados para a confecção de uma

calça de ginástica.

A Fitwear só pode contar com 100 horas de corte por semana e 160 horas de costura. A confecção não tem problemas no

fornecimento de matérias-primas, de modo que seu suprimento pode ser considerado ilimitado, bem como a demanda

semanal de seus produtos.

A Fitwear deseja planejar sua produção semanal de modo a maximizar seus lucros.

Quando modelamos o problema, consideramos as seguintes variáveis de decisão:

𝑥1

Número de tops de ginástica confeccionados a cada semana.

𝑥2

Número de calças de ginástica confeccionadas a cada semana.

Assim, chegamos à seguinte formulação matemática em sua forma-padrão.

𝑀á𝑥 𝑍 = 28 𝑥1 + 40𝑥2

SUJEITO A (FORMA-PADRÃO):

0, 5𝑥1 + 0, 25𝑥2 ≤ 100 → RESTRIÇÃO DE HORAS DE CORTE

0, 25𝑥1 + 0, 5𝑥2 ≤ 160 → RESTRIÇÃO DE HORAS DE COSTURA

Processing math: 100%

 𝑥1 , 𝑥2 ≥ 0 → RESTRIÇÃO DE NÃO NEGATIVIDADE DAS VARIÁVEIS
DE DECISÃO

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

Observe que tanto a restrição referente às horas de corte quanto a restrição referente às horas de costura são do tipo ≤.

Logo, precisaremos de duas variáveis de folga, 𝑓1 e 𝑓2 , para passar o problema para sua forma canônica.

𝑀á𝑥 𝑍 = 28 𝑥1 + 40𝑥2

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

Sujeito à (forma canônica):

0, 5𝑥1 + 0, 25𝑥2 + 𝑓1 = 100

0, 25𝑥1 + 0, 5𝑥2 + 𝑓2 = 160

𝑥1 , 𝑥2 ≥ 0

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

Uma vez adicionadas as variáveis de folga, o problema da Fitwear é dito no formato canônico e pronto para ser resolvido

pelo método simplex!

Para resolver o problema de programação linear, o algoritmo simplex se baseia na solução sucessiva de sistemas de

equações, utilizando-se do conceito de variáveis básicas e não básicas:

VARIÁVEIS BÁSICAS
São aquelas para as quais o sistema de equações é resolvido.

VARIÁVEIS NÃO BÁSICAS

São aquelas que são zeradas para que o sistema de equações apresente uma solução, ou seja, para que o número de

equações seja igual ao número de variáveis, permitindo, assim, a solução do sistema de equações.

Processing math: 100%

 No problema da Fitwear, por exemplo, temos quatro variáveis (𝑥1, 𝑥2, 𝑓1 e 𝑓2) e apenas duas equações (restrições).

Entretanto, para que um sistema de equações lineares seja resolvido, é necessário que o número de equações seja igual

ao número de variáveis. De tal modo, para resolver o problema da Fitwear, devemos considerar duas variáveis como nulas

(não básicas) e resolver o problema para outras duas (variáveis básicas), e assim fazemos por iterações sucessivas, até

que encontremos o par de variáveis básicas que nos dá a solução ótima.

Em linhas gerais, o algoritmo simplex parte de uma solução viável do sistema de equações que constituem as restrições

do problema de programação linear, solução essa normalmente extrema (vértice). A partir dessa solução inicial, o

algoritmo adota um critério de escolhas para encontrar novos e melhores vértices da envoltória convexa do problema, e

outro critério para determinar se o vértice escolhido (solução básica) é ou não um vértice ótimo (GOLDBARG; LUNA,

2005). Assim, pelo método simplex, devemos:

Transformar o modelo em sua forma canônica, ou seja, transformar o sistema de inequações em sistema de equações.

Determinar uma solução básica inicial, que será iterativamente melhorada.

Realizar o teste da otimalidade, ou seja, verificar se a iteração atual é ótima ou se outras variáveis não base (ou seja, que

estão zeradas) devem entrar na base, pois têm potencial para contribuir para melhorar a solução.

Realizar o teste da mínima razão, que determinará qual variável básica deve sair da base, ou seja, verificará quais das

variáveis devem passar a ser nulas para que a nova variável entre na base.

Calcular a nova solução básica e voltar ao passo 3.

Processing math: 100%

 Arenales et al. (2007) descrevem o algoritmo simplex em duas fases. A fase 1 traz o procedimento de como determinar

uma solução inicial, enquanto o método simplex propriamente dito é apresentado na fase 2.

PASSO 1
Escreva o problema na forma canônica

𝑇
Minimizar 𝑓(𝑥) = 𝑐 𝑥

𝐴𝑥 = 𝑏, sendo A uma matriz mxn

𝑥≥0

PASSO 2
Determine inicialmente uma partição básica factível 𝐴 = [𝐵 . 𝑁], ou seja, com dois vetores de índices básicos e não

básicos: 𝐵1, 𝐵2, …, 𝐵𝑚 e 𝑁1, 𝑁2, …, 𝑁𝑛 - 𝑚.

Faça iteração=1.

Fase 2: {início da iteração simplex}

PASSO 1: {CÁLCULO DA SOLUÇÃO BÁSICA}

-1
𝑥^𝑏 = 𝐵 𝑏 (equivalentemente, resolva o sistema 𝐵𝑥𝑏 = 𝑏)

𝑥^𝑛 = 0

PASSO 2: {CÁLCULO DOS CUSTOS RELATIVOS}

{vetor multiplicador simplex}

𝑇 𝑇 -1 𝑇
ƛ = 𝑐𝐵 𝐵 (EQUIVALENTEMENTE, RESOLVA O SISTEMA 𝐵 ƛ = 𝑐𝑏 )

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

{custos relativos}

𝑇
𝑐𝑁^ 𝑗 = 𝑐𝑁𝑗 - ƛ 𝑎𝑁𝑗 , 𝑗 = 1, 2, … , 𝑛 - 𝑚

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

{determinação da variável a entrar na base}

𝑐𝑁^ 𝑗 = MÍNIMO 𝑐𝑁^ 𝑗 , 𝑗 = 1, 2, …, 𝑛 - 𝑚 (A VARIÁVEL 𝑥𝑁𝑘 ENTRA NA

BASE)

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

Processing math: 100%

 PASSO 3: {TESTE DA OTIMALIDADE}

SE 𝑐𝑁^ ≥ 0, ENTÃO PARE {SOLUÇÃO NA ITERAÇÃO ATUAL É ÓTIMA}

𝑗

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

PASSO 4: {CÁLCULO DA DIREÇÃO SIMPLEX}

-1
𝑦 = 𝐵 𝑎𝑁𝑘 (EQUIVALENTEMENTE, RESOLVA O SISTEMA 𝐵𝑦 = 𝑎𝑁𝑘 )

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

PASSO 5: {DETERMINAÇÃO DO PASSO E VARIÁVEL A SAIR DA BASE}

Se 𝑦 ≤ 0, então: pare {problema não tem solução ótima finita: 𝑓(𝑥) → - ∞ }

Caso contrário, determine a variável a sair da base pela razão mínima:

𝑥𝐵𝑙
^
𝑥^
𝜀^ = 𝑦𝑙 = MÍNIMO { 𝑦𝐵𝑖 , TAL QUE 𝑦𝑖 > 0, 𝑦𝑖 > 0, 𝑖 = 1, 2, . . . 𝑚} (A VARIÁVEL 𝑥𝐵𝑙
𝑖

SAI DA BASE)

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

PASSO 6: {ATUALIZAÇÃO: NOVA VARIÁVEL BÁSICA, TROQUE A L-ÉSIMA

COLUNA DE B PELA K-ÉSIMA COLUNA DE N}
Matriz básica nova:

𝐵 = [𝑎𝐵1 … 𝑎𝐵𝑙 - 𝑘 𝑎𝑁𝑘 𝑎𝐵𝑙 + 1 … 𝑎𝐵𝑚 ]

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

Matriz não básica nova:

𝑁 = [𝑎𝑁1 … 𝑎𝑁𝑘 - 1 𝑎𝐵𝑙 𝑎𝑁𝑘 + 1 … 𝑎𝑁𝑛 - 𝑚 ]

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

Iteração = iteração +1

Retorne
Processing ao passo
math: 100% 1
 {fim da iteração simplex}

Na forma de algoritmo, como apresentado por Arenales et al. (2007), o método simplex pode parecer difícil, mas vamos

entender o que Dantzig propôs por meio de um exemplo.

Caso da empresa Glass Co.

A empresa Glass Co., que possui três fábricas, produz janelas e portas de vidro. As esquadrias e ferragens em aço são

feitas na fábrica 1, as esquadrias de madeira são produzidas na fábrica 2 e a fábrica 3 produz o vidro e monta os

produtos.

A direção da empresa decidiu modernizar sua linha de produtos e propôs o lançamento de dois novos produtos:

Produto 1: porta de vidro de 2,5m com esquadria de alumínio.

Produto 2: janela adornada com esquadria de madeira 1,2m x 1,8m.

O produto 1 requer capacidade produtiva das fábricas 1 e 3. O produto 2 precisa das fábricas 2 e 3. A divisão de marketing

concluiu que a empresa poderia vender tanto quanto fosse possível produzir desses produtos por essas fábricas. Porém,

ambos os produtos competem por capacidade produtiva da fábrica 3, não estando claro qual mix dos dois seria mais

lucrativo. Determine quais devem ser as taxas de produção para maximizar o lucro total, sujeitas às restrições impostas

pela capacidade produtiva:

Tempo de produção por lote (em

horas)

Tempo de produção disponível por semana

Fábrica
Produtos (horas)

1 2

1 1 0 4

2 0 2 12

3 3 2 18

Lucro por
R$3.000,00 R$5.000,00
lote

 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal

 Produção empresa Glass Co. Extraída de Hillier e Lieberman, 2013, pág. 21

Inicialmente, devemos escrever o modelo matemático para o problema da Glass Co., seguindo os passos do

procedimento para construção do modelo de programação linear:

Identificação das variáveis de decisão

Processing math: 100%
 
Identificação da função objetivo


Identificação do conjunto de restrições

A seguir, vamos seguir cada um dos passos indicados.

IDENTIFICAÇÃO DAS VARIÁVEIS DE DECISÃO

No caso da Glass Co., a empresa deve decidir os produtos a serem fabricados. Logo, a definição da variável de decisão

seria:

𝑥𝑖 — quantidade de produto i confeccionada

Assim, temos:

𝑥1 - Quantidade de lotes produtos 1 fabricados.

𝑥2 - Quantidade de lotes produtos 2 fabricados.

IDENTIFICAÇÃO DA FUNÇÃO OBJETIVO

No caso da Glass Co., a empresa deseja maximizar seu lucro total:

Determine quais devem ser as taxas de produção para maximizar o lucro total (…).

Para cada lote de portas de vidro de 2,5m com esquadria de alumínio (produto 1) vendido, a empresa lucra R$3.000,000,

enquanto o lucro de venda de cada lote de janela adornada com esquadria de madeira 1,2m x 1,8m (produto 2) equivale a

R$5.000,00. Logo, o lucro total é igual a 3000𝑥1 + 5000𝑥2 ., de modo que a função objetivo para o problema é:

𝑀𝑎𝑥 𝑍 = 3𝑥1 + 5𝑥2

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

IDENTIFICAÇÃO DO CONJUNTO DE RESTRIÇÕES

No caso do problema da Glass Co., foram consideradas ilimitadas a demanda por seus produtos e a oferta de matéria-

prima, de modo que não entram como restrições no modelo matemático. Porém, há restrições relacionadas ao tempo de

produção disponível por semana em cada fábrica.

Tempo de produção por lote (em horas)

Fábrica Produtos Tempo de produção disponível por semana (horas)

1 2

Processing math: 100%

 1 1 0 4

2 0 2 12

3 3 2 18

 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal

 Produção empresa Glass Co. Extraída de Hillier e Lieberman, 2013, pág. 21.

Há, ainda, a restrição de não negatividade das variáveis de decisão, uma vez que não se pode produzir um número

negativo de portas ou janelas. Logo, a restrição 4 é dada por: 𝑥1 , 𝑥2 ≥ 0

Logo, temos as seguintes restrições:

𝑥1 ≤ 4

2𝑥2 ≤ 12 → 𝑥2 ≤ 6

3𝑥1 + 2𝑥2 ≤ 18

Enfim, temos o seguinte modelo matemático para o problema da Glass Co.:

𝑀𝑎𝑥 𝑍 = 3𝑥1 + 5𝑥2

S.A.

𝑥1 ≤ 4

2𝑥2 ≤ 12

3𝑥1 + 2𝑥2 ≤ 18

Processing math: 100%

 𝑥1 , 𝑥2 ≥ 0

𝑥1 , 𝑥2 ≥ 0

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

MAS QUAL É O MIX DE PRODUÇÃO QUE NOS DÁ A SOLUÇÃO

ÓTIMA?

O primeiro passo do algoritmo simplex é transformar o modelo em seu formato canônico.

Passando para o formato canônico, temos:

𝑀𝑎𝑥 𝑍 = 3𝑥1 + 5𝑥2

S.A.

𝑥1 + 𝑓 1 = 4 → restrição 1

2 𝑥2 + 𝑓 2 = 12 → restrição 2

3𝑥1 + 2𝑥2 + 𝑓 3 = 18 → restrição 3

𝑥1 , 𝑥2 , 𝑓 1 , 𝑓 2 , 𝑓 3 > = 0

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

Processing math: 100%
 Em seguida, devemos escolher uma solução básica inicial. Observe que temos três equações no sistema de equações e

cinco variáveis. Dessa forma, devemos ter três variáveis-base e duas não base. O modo mais fácil de resolver esta etapa é

escolher as variáveis 𝑥1 e 𝑥2 como variáveis não básicas, uma vez que essa opção elimina o trabalho necessário para

encontrar a solução quando as variáveis básicas são as variáveis de folga (ou excesso) (𝑓1 , 𝑓2 e 𝑓3 ). Nesse caso, se 𝑥1 = 0

e 𝑥2 = 0, z seria igual a zero também, enquanto 𝑓1 = 4, 𝑓2 = 12 e 𝑓3 = 18.

Função objetivo: 𝑍 = 3𝑥1 + 5𝑥2 , logo, para a solução inicial de 𝑥1 = 0 e 𝑥2 = 0, temos 𝑍 = 0.

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

Restrição 1: 𝑥1 + 𝑓1 = 4 → 0 + 𝑓1 = 4 → 𝑓1 = 4

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

Restrição 2: 2𝑥2 + 𝑓2 = 12 → 0 + 𝑓2 = 12 → 𝑓2 = 12

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

Restrição 3: 3𝑥1 + 2𝑥2 + 𝑓3 = 18 → 0 + 0 + 𝑓3 = 18 → 𝑓2 = 18

 Atenção! Para visualização completa da equação utilize a rolagem horizontal


Portanto, temos a solução inicial de (0, 0, 4, 12, 18).

Passamos, então, para o teste da otimalidade. Como 𝑍 = 3𝑥1 + 5𝑥2 , verificamos que o coeficiente de cada variável não

básica (𝑥1 e 𝑥2 ) fornece a taxa de crescimento em 𝑍.

Como as taxas de crescimento são positivas (3 e 5) e este é um problema de maximização, concluímos que a solução

inicial (0, 0, 4, 12, 18) não é a solução ótima!

Já sabemos que a solução básica inicial não é ótima, então uma variável não básica (𝑥1 ou 𝑥2 ) deve entrar na base.

Porém, devemos aumentar 𝑥1 ou 𝑥2 ?

Para determinar isso, devemos verificar a direção de deslocamento. Observe que, para cada unidade que aumentarmos 𝑥1

, temos uma taxa de crescimento em 𝑍 de 3. Ao mesmo tempo, para cada unidade que aumentarmos 𝑥1, temos uma taxa

de crescimento em 𝑍 de 5. Sendo 5 > 3, devemos optar por 𝑥2 para crescer. Logo, 𝑥2 é a variável básica que entra.

Entretanto, para que 𝑥2 passe a ser uma variável básica, uma das variáveis-base da solução inicial (𝑓1 , 𝑓2 e 𝑓3 ) precisa sair

da base. Porém, como determinar qual delas?

Para essa etapa, devemos ter em mente que, ao aumentar 𝑥2 , eleva-se 𝑍. Contudo, não podemos sair do espaço de

soluções, ou seja, da região de soluções viáveis. Assim, devemos aumentar 𝑥2 , mantendo a variável não básica 𝑥1 = 0 e

respeitando que todas as variáveis sejam não negativas.

𝑥1 = 0 (variável não básica)

𝑥1 + 𝑓 1 = 4→ 𝑓1 = 4
Processing math: 100%
 2𝑥2 + 𝑓2 = 12 → 𝑓2 = 12 - 2𝑥2

3𝑥1 + 2𝑥2 + 𝑓3 = 18 → 𝑓3 = 18 - 2𝑥2

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

Como 𝑥1 , 𝑥2 , , 𝑓1 , 𝑓2 , 𝑓3 ≥ 0:

Teste da mínima razão

𝑓1 = 4 → não implica em limite superior em 𝑥2

𝑓2 = 12 - 2𝑥2 ≥ =0→ 𝑥2 ≤ 12 / 2 = 6 ← MÍNIMO

𝑓3 = 18 - 2𝑥2 ≥ 0 → 𝑥2 ≤ 18 / 2 = 9

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

Verificamos, então, que 𝑥2 passa a receber o valor de 6, enquanto 𝑓2 se torna uma variável não base e nula. Assim,

deduzimos intuitivamente o teste da mínima razão.

O objetivo do teste da mínima razão é determinar qual variável básica cai a zero primeiro à medida que a variável básica

que entra é aumentada.

Podemos descartar imediatamente a variável básica em qualquer equação cujo coeficiente da variável básica que entra é

zero ou negativo, já que uma variável básica não decresceria à medida que a variável básica que entra aumentasse.

No caso do problema da Glass Co., ao aumentarmos o valor de 𝑥2 de 0 a 6, temos mudanças na solução.

SOLUÇÃO INICIAL
𝑥1 = 0

𝑥2 = 0

𝐹1 = 4

𝐹2 = 12

𝐹3 = 18

Processing math: 100%

 NOVA SOLUÇÃO
𝑥1 = 0

𝑥2 = 6

𝐹1 = ?

𝐹2 = 0

𝐹3 = ?

Temos que 𝑥2 é igual a 6 e 𝑥1 continua sendo zero. Portanto, temos que 𝑍 = 3𝑥1 + 5𝑥2 = 3 * 0 + 5 * 6 = 30. Devemos

determinar, então, os valores de 𝑓1 , 𝑓2 e 𝑓3 .

𝑥1 + 𝑓 1 = 4→ 0+ 𝑓1 = 4→ 𝑓1 = 4

2 𝑥2 + 𝑓 2 = 12 → 2 * 6 + 𝑓2 = 12 𝑓2 = 0

3 𝑥1 + 2 𝑥2 + 𝑓3 = 18 → 3 * 0 + 2 * 6 + 𝑓3 = 18 → 𝑓3 = 6

A nova solução é (0, 6, 4, 0, 6) e 𝑍 = 30!

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

Então, devemos verificar se essa solução é ótima ou não, por meio do teste de otimalidade. Sendo 𝑍 = 3𝑥1 + 5𝑥2 ,

verificamos que 𝑥1 tem o coeficiente positivo ( = 3), de modo que aumentar 𝑥1 implica em aumentar 𝑍. Portanto, a

solução atual não é ótima e devemos realizar nova iteração, analisando a entrada de 𝑥1 como variável básica. Dessa

forma, devemos realizar o teste da mínima razão para determinar qual variável básica deve se tornar nula, saindo então da

base, para permitir a “entrada” de 𝑥1 .

𝑍 - 3𝑥1 - 2, 5𝑥2 = 30

𝑥1 + 𝑓 1 = 4

2𝑥2 + 𝑓2 = 12

Processing math: 100%

 3𝑥1 + 2𝑥2 + 𝑓3 = 18

Teste da mínima razão

𝑓 1 = 4 - 𝑥1 ≥0→ 𝑥1 ≤ 4/1→ 𝑥1 ≤ 4

𝑓2 = 12 - 2𝑥2 ≥ 0 → nenhum limite superior em 𝑥1

𝑓 3 = 6 - 3 𝑥1 ≥ 0 → 𝑥 → ≤ 6 / 3 → 𝑥1 ≤ 2 → mínima razão

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

Logo, 𝑓3 sai da base para 𝑥1 entrar com o valor igual a 2. Porém, ao aumentarmos o valor de 𝑥1 de 0 a 2, temos mudanças

na solução.

SOLUÇÃO INICIAL
𝑥1 = 0

𝑥2 = 6

𝐹1 = 4

𝐹2 = 0

𝐹3 = 18

NOVA SOLUÇÃO
𝑥1 = 2

𝑥2 = 6

𝐹1 = ?

𝐹2 = 0

𝐹3 = ?

Temos que 𝑥2 é igual a 6 e 𝑥1 equivale a 2. Logo, temos que 𝑍 = 3𝑥1 + 5𝑥2 = 3 * 2 + 5 * 6 = 36. Devemos determinar, então,

os valores de 𝑓1 , 𝑓2 e 𝑓3 .

Processing math: 100%

 𝑥1 + 𝑓1 = 4→ 2+ 𝑓1 = 4→ 𝑓1 = 2

2 𝑥2 + 𝑓 2 = 12 → 2 * 6 + 𝑓2 = 12 → 𝑓2 =0

3 𝑥1 + 2 𝑥2 + 𝑓3 = 18 → 3 * 2 + 2 * 6 + 𝑓3 = 18 → 𝑓3 =0

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

Portanto, concluímos que 𝑥1 substitui 𝑓3 como variável básica, sendo a nova solução igual a (2, 6, 2, 0, 0) e 𝑍 = 36. As

variáveis não básicas agora são 𝑓2 e 𝑓3 . Verificamos que aumentar as atuais variáveis não básicas não implica em

aumento em 𝑍, o que garante que esta é a solução ótima.

MÉTODO SIMPLEX EM SUA FORMA TABULAR

Aprendemos até agora a forma algébrica do simplex, que é a melhor para aprender a lógica por trás do algoritmo. Porém,

não é a forma mais conveniente para realizar cálculos necessários. As operações realizadas no método simplex podem

ser organizadas em tabelas, chamadas tabelas simplex. Essa organização é a mais indicada para quando estivermos

resolvendo um problema de programação linear manualmente.

Considere um problema de otimização linear:

Minimizar 𝑓(𝑥) = 𝑐𝑥

𝐴𝑥 = 𝑏

𝑥 ≥ 0.

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

Nesse problema, temos as variáveis 𝑥1 , 𝑥2 … 𝑥𝑛 . Os coeficientes da função objetivo são 𝑐1 , 𝑐2 … 𝑐𝑛 . Os

coeficientes das restrições são 𝑎1 , 𝑎2 … 𝑎𝑛 e 𝑏.

Processing math: 100%

 Arenales et al. (2007) descrevem as operações realizadas em cada iteração do algoritmo simplex em tabelas, em duas

fases.

Fase 1:

Determine a tabela simplex inicial.


A matriz dos coeficientes contém uma matriz identidade 𝑚𝑥𝑚 (m é o número de equações) e o vetor independente 𝑏 ≥ 0.


A função objetivo é escrita em termos das variáveis não básicas, isto é, os coeficientes das variáveis básicas são nulos.


Faça a iteração = 0.

Fase 2:

Determine o menor dos custos relativos: 𝑐𝑘 = mínimo {𝑐𝑗 para toda variável não básica}.


Se 𝑐𝑘 ≥ 0, então pare (a solução básica na iteração é ótima). Se não, a variável 𝑥𝑘 entra na base.


Se 𝑎𝑖𝑘 ≤ 0, 𝑖 = 1, …, 𝑚, então 𝑓 → - ∞ e o problema não tem solução ótima finita. Nesse caso, pare. Se não,
𝑏𝑙 𝑏
determine 𝑎𝑙𝑘 mínimo {𝑎𝑖𝑘𝑖 tal que 𝑎𝑖𝑘 > 0, 𝑖 = 1, … , 𝑚}. (a variável básica da linha l sai da base).


Atualize a tabela simplex (pivoteamento do elemento (𝑙, 𝑘)). A variável 𝑥𝑘 passa a ser a variável básica na linha l. Faça a

iteração = iteração +1 e retorne ao passo 1.

Na forma de algoritmo, como apresentado por Arenales et al. (2007), o método simplex tabular pode parecer difícil, mas

vamos entendê-lo resolvendo o exemplo da Glass Co., cujo modelo em formato canônico é apresentado a seguir.

𝑀𝑎𝑥 𝑍 = 3𝑥1 + 5𝑥2

S.A.

𝑥1 + 𝑓1 = 4 → restrição 1
Processing math: 100%
 2 𝑥2 + 𝑓 2 = 12 → restrição 2

3𝑥1 + 2𝑥2 + 𝑓3 = 18 → restrição 3

𝑥1 , 𝑥2 , 𝑓 1 , 𝑓 2 , 𝑓 3 > = 0

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

Inicialmente, vamos definir o formato da tabela de maneira a facilitar sua compreensão. A tabela simplex tem, do lado

esquerdo, as variáveis básicas e, do lado direito, as constantes das equações. No meio da tabela, ficam todos os

coeficientes das restrições e da função objetivo. Por padronização, colocaremos na primeira linha (zero) a equação que

representa a função objetivo, conforme apresentado na figura a seguir.

Imagem: Fogliato (2006, p. 61) adaptado por Renata Albergaria de Mello Bandeira

 Tabela simplex.

Uma escolha viável para a primeira base para o problema da Glass Co. seria (𝑓1 , 𝑓2 , 𝑓3 ), pois facilitaria o preenchimento da
-1
tabela simplex inicial, dado que 𝐵 = 𝐼 e 𝐵 = 𝐼.

𝑀𝑎𝑥 𝑍 = 3𝑥1 + 5𝑥2

𝑥1 + 𝑓1 = 4

2 𝑥2 + 𝑓2 = 12

Processing math: 100%

 3 𝑥1 + 2 𝑥2 + 𝑓3 = 18

𝑎3 𝑎4 𝑎5 𝑎1 𝑎2

100𝐼10
𝐴=𝐵 𝐼 𝑁 = 010𝐼02
001𝐼32

𝑓1 𝑓2 𝑓3 𝑥1 𝑥2

100 -1 100
𝐵 = 010 𝐵 = 010
001 001

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

Quando as variáveis de folga constituem a primeira base, na primeira linha da tabela simplex, apenas escrevemos o

negativo dos coeficientes de custo das variáveis não básicas. Como 𝑧𝑗 - 𝑐𝑗 representa a potencial melhoria no valor de 𝑧

da função objetivo representada pela j-ésima variável, as variáveis atualmente básicas devem receber o valor zero, pois já

se encontram na base. Assim, a primeira linha da tabela simplex para o exemplo da Glass Co. é:

𝑥1 𝑥2 𝑓1 𝑓2 𝑓3 RHS

𝑍 -3 -5 0 0 0 𝑍0

 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal

O valor atual de 𝑧, 𝑧0 , para esta primeira tabela, com as variáveis básicas sendo 𝑓1 , 𝑓2 , 𝑓3 , seria igual a zero, pois

𝑍 = 3𝑥1 + 5𝑥2 e 𝑥1 = 𝑥2 = 0. Assim, atualizando a tabela, tem-se:

𝑥1 𝑥2 𝑓1 𝑓2 𝑓3 RHS

𝑍 -3 -5 0 0 0 0

 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal

Em seguida, devem-se escrever as linhas que compõem as restrições da tabela simplex, conforme indicado na figura a

seguir.
Processing math: 100%
 Fogliato (2006, p. 61) adaptado por Renata Albergaria de Mello Bandeira.

 Restrições da tabela simplex.

Para cada variável do problema, deve-se determinar 𝑦 . Como as variáveis de folga foram escolhidas como a primeira
𝑗
-1
base, temos 𝐵 = 𝐼 e 𝐵 = 𝐼. Logo, temos 𝑦𝑗 = 𝑎𝑗 , de modo que as linhas que compõem as restrições no tableau são

copiadas diretamente do problema. Ainda, as variáveis atualmente na base (𝑓1 , 𝑓2 , 𝑓3 ) são identificadas à esquerda da
tabela simplex, como pode ser identificado na figura a seguir.

𝑀𝑎𝑥 𝑍 = 3𝑥1 + 5𝑥2

𝑠.𝑎.

Renata Albergaria de Mello Bandeira

 Preenchendo a tabela simplex para o problema da Glass Co.

Observa-se, por meio da figura anterior, que os únicos elementos faltantes estão do lado direito da tabela simplex e

correspondem à fórmula:

-1
𝑏¯ = 𝐵 𝑏 = 𝐼𝑏 = 𝑏

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

Processing math: 100%

 Desse modo, para a tabela inicial, basta copiar os valores de 𝑏 no lado direito da tabela, conforme apresentado na figura a

seguir.

𝑀𝑎𝑥 𝑍 = 3𝑥1 + 5𝑥2

𝑠.𝑎.

Renata Albergaria de Mello Bandeira

 Tabela simplex inicial para o problema da Glass Co.

Uma vez preenchida a tabela inicial, devemos identificar as variáveis candidatas a entrar na base na primeira linha da

tabela. Para isso, devemos analisar os valores dos coeficientes de cada variável apresentados na segunda linha da tabela

simplex, levando em consideração o tipo de problema apresentado, maximização ou minimização:

Problema de maximização

Em um problema de maximização, a variável cujo coeficiente é negativo e apresenta o maior valor absoluto é aquela que

entrará na base.


Problema de minimização

Em um problema de minimização, a variável a entrar na base será a que tiver o maior valor positivo.

Por meio da figura da Tabela simplex inicial para o problema da Glass Co., observamos que a variável a entrar na base no

problema da Glass Co. é 𝑥2 , uma vez que tanto 𝑥𝑥 quanto 𝑥2 têm valores negativos na segunda linha da tabela, sendo 5 > 3

Depois de identificarmos a variável que entra na base, é preciso determinar a variável básica que deve dar lugar para que

𝑥2 entre na base. Para isso, aplicamos o teste da mínima razão, conforme indicado na figura a seguir. Observa-se que o
menor valor é 6, de modo que a variável a sair da base é 𝑓2 .

Processing math: 100%

 Renata Albergaria de Mello Bandeira

 Teste da mínima razão para o problema da Glass Co.

Para completar a iteração do simplex, devemos, então, proceder com as operações elementares que utilizam a linha que

contém o elemento de pivot, de modo que a coluna 𝑥2 (da variável entrante) assuma a configuração da coluna 𝑓2 (variável

que sai da base). Observe, na figura a seguir, que a linha pivot é a quarta linha da tabela (atual linha do 𝑓2 no lado esquerdo

da tabela) e que os valores para as colunas 𝑥2 e 𝑓2 não coincidem, de modo que é necessário executar a operação

elementar. Portanto, sendo a linha (3)´ a quarta linha da tabela (3) após a operação elementar, tem-se que a operação que

transformará 2 em 1 é: (3)´ = (3) / 2.

Renata Albergaria de Mello Bandeira

 Operações com a linha pivot para o problema da Glass Co.

Observe, na segunda tabela da figura anterior, que, para a coluna 𝑥2 assumir a configuração anterior da coluna 𝑓2 , é

preciso ainda realizar operações elementares nas linhas (1) e (4) da tabela simplex. Assim, para a linha (4)´, é preciso que

(4)´ = (4) - 2 * (3)´, enquanto para a linha (1)´ devemos fazer (1)´ = (1) + 5 * (3)´, conforme indicado na próxima figura.

 DICA

Para a linha (2), não é preciso realizar nenhuma operação, uma vez que os valores para as colunas 𝑥2 e 𝑓2 já são

coincidentes.

Processing math: 100%

 Operações com a linha pivot para o problema da Glass Co.

 Renata Albergaria de Mello Bandeira

Verifique, na figura anterior, que a coluna 𝑥1 ainda apresenta um valor negativo na segunda linha da tabela simplex, de

modo que esta variável deve entrar na base, sendo necessária, então, mais uma iteração. Logo, faz-se o teste da mínima

razão, conforme indicado na figura a seguir, sendo verificado que a variável a sair da base para que 𝑥1 entre é 𝑓3 . Portanto,

são necessárias as operações elementares para que a coluna 𝑥1 receba os valores da coluna 𝑓3 .

Renata Albergaria de Mello Bandeira

 Teste da mínima razão para o problema da Glass Co. — 2a iteração

Observa-se, na figura do Teste da mínima razão para o problema da Glass Co. — 2a iteração, que a quinta linha (4) da

tabela simplex é a linha pivot. Assim, para que a coluna 𝑥1 receba os valores da coluna 𝑓3 , a primeira operação elementar a

ser feita é: (4)´ = (4) / 3, tal como apresentado na figura a seguir.

Renata Albergaria de Mello Bandeira

 Primeira operação elementar (linha (4)) para o problema da Glass Co. — 2a iteração.

Processing math: 100%

 Para a coluna 𝑥1 assumir a configuração anterior da coluna 𝑓3 , ainda é preciso realizar operações elementares nas linhas

(1) e (2) da tabela simplex. Assim, para a linha (2)´, é preciso que (2)´ = (2) - (4)´, enquanto para a linha (1)´ devemos fazer

(1)´ = (1) + 3 * (4)´, conforme indicado na próxima figura.

 DICA

Para a linha (3) não é preciso realizar nenhuma operação, uma vez que os valores para as colunas 𝑥1 e 𝑓3 já são

coincidentes nesta linha.

Renata Albergaria de Mello Bandeira

 Operações com a linha pivot para o problema da Glass Co. — 2a iteração.

 ATENÇÃO

Verifique, na figura anterior, que não há mais valores negativos na segunda linha da tabela simplex (1), de modo que não

há mais variáveis para entrar na base. Logo, concluímos que a solução ótima para o problema da Glass Co. é 𝑥1 = 2, 𝑥2 = 6

e 𝑧 = 36, tal como apresentado na seção método simplex, quando resolvemos este mesmo problema por meio do método

simplex em sua forma analítica.

VERIFICANDO O APRENDIZADO

1. A FITWEAR S/A É UMA CONFECÇÃO DE ROUPAS ESPORTIVAS, TENDO UMA LINHA FITNESS
FEMININA, NA QUAL PRODUZ ROUPAS DE GINÁSTICA EXCLUSIVAS PARA MULHERES, COMO TOPS
E CALÇAS DE LYCRA.

CADA TOP DE GINÁSTICA É VENDIDO POR R$80,00 E UTILIZA R$20,00 DE MATÉRIA-PRIMA, COMO
TECIDO E ALINHAMENTOS, E R$32,00 DE MÃO DE OBRA. TRINTA MINUTOS DE CORTE E 15
MINUTOS DE COSTURA SÃO DEMANDADOS PARA A CONFECÇÃO DE UM TOP DE GINÁSTICA.

CADA CALÇA DE GINÁSTICA É VENDIDA POR R$120,00 E UTILIZA R$35,00 DE MATÉRIA-PRIMA,

COMO TECIDO E ALINHAMENTOS, E R$40,00 DE MÃO DE OBRA. QUINZE MINUTOS DE CORTE E 30
Processing math: 100%
 MINUTOS DE COSTURA SÃO DEMANDADOS PARA A CONFECÇÃO DE UMA CALÇA DE GINÁSTICA.

A FITWEAR SÓ PODE CONTAR COM 100 HORAS DE CORTE POR SEMANA E 160 HORAS DE
COSTURA. A CONFECÇÃO NÃO TEM PROBLEMAS NO FORNECIMENTO DE MATÉRIAS-PRIMAS, DE
MODO QUE SEU SUPRIMENTO PODE SER CONSIDERADO ILIMITADO, BEM COMO A DEMANDA
SEMANAL DE SEUS PRODUTOS.

CONSIDERANDO QUE SERIA POSSÍVEL PRODUZIR NÚMEROS NÃO INTEIROS, QUAL DEVE SER A
PRODUÇÃO SEMANAL A SER ADOTADA PELA FITWEAR DE MODO A MAXIMIZAR SEUS LUCROS?
CONSIDERE AS SEGUINTES VARIÁVEIS DE DECISÃO:

• 𝑥1 = NÚMERO DE TOPS DE GINÁSTICA CONFECCIONADOS A CADA SEMANA

• 𝑥2 = NÚMERO DE CALÇAS DE GINÁSTICA CONFECCIONADAS A CADA SEMANA

A) 𝑥1 = 320, 𝑥2 = 160

B) 𝑥1 = 200, 𝑥2 = 160

C) 𝑥1 = 160, 𝑥2 = 320

D) 𝑥1 = 280, 𝑥2 = 220

E) 𝑥1 = 280, 𝑥2 = 120

2. UTILIZE O MÉTODO SIMPLEX PARA A SOLUÇÃO DESTA PROGRAMAÇÃO LINEAR:

MAX: 350X1 + 300X2

SUJEITO A:

𝑋1 + 𝑋2 < = 200

9𝑋1 + 6𝑋2 < = 1566

12𝑋1 + 16𝑋2 < = 2880

𝑋1 > = 0

𝑋2 > = 0 O VALOR DE Z PARA A SOLUÇÃO ÓTIMA DO PROBLEMA APRESENTADO É IGUAL A:

A) Zero

B) 54.000

C) 60.900

D) 64.000

E) 66.100
Processing math: 100%
 GABARITO

1. A Fitwear S/A é uma confecção de roupas esportivas, tendo uma linha fitness feminina, na qual produz roupas de

ginástica exclusivas para mulheres, como tops e calças de lycra.

Cada top de ginástica é vendido por R$80,00 e utiliza R$20,00 de matéria-prima, como tecido e alinhamentos, e R$32,00

de mão de obra. Trinta minutos de corte e 15 minutos de costura são demandados para a confecção de um top de

ginástica.

Cada calça de ginástica é vendida por R$120,00 e utiliza R$35,00 de matéria-prima, como tecido e alinhamentos, e

R$40,00 de mão de obra. Quinze minutos de corte e 30 minutos de costura são demandados para a confecção de uma

calça de ginástica.

A Fitwear só pode contar com 100 horas de corte por semana e 160 horas de costura. A confecção não tem problemas

no fornecimento de matérias-primas, de modo que seu suprimento pode ser considerado ilimitado, bem como a

demanda semanal de seus produtos.

Considerando que seria possível produzir números não inteiros, qual deve ser a produção semanal a ser adotada pela

Fitwear de modo a maximizar seus lucros? Considere as seguintes variáveis de decisão:

• 𝑥1 = número de tops de ginástica confeccionados a cada semana

• 𝑥2 = número de calças de ginástica confeccionadas a cada semana

A alternativa "A " está correta.

O modelo matemático para este problema é:

𝑀á𝑥 𝑍 = 28 𝑥1 + 40𝑥2

Sujeito a:

0, 5𝑥1 + 0, 25𝑥2 ≤ 100 → restrição de horas de corte

0, 25𝑥1 + 0, 5𝑥2 ≤ 160 → restrição de horas de costura

𝑥1 , 𝑥2 ≥ 0 → restrição de não negatividade das variáveis de decisão

Em sua forma canônica, temos:

𝑀á𝑥 𝑍 = 28 𝑥1 + 40𝑥2

Sujeito a:

0, 5𝑥1 + 0, 25𝑥2 + 𝑓1 = 100

0, 25𝑥1 + 0, 5𝑥2 + 𝑓2 = 160

𝑥1 , 𝑥2 ≥ 0

A solução do problema pela tabela simplex é:

Processing math: 100%

  Solução da Atividade 1 pela tabela simplex. Captura de tela do Excel.

2. Utilize o método simplex para a solução desta programação linear:

MAX: 350X1 + 300X2

Sujeito a:

𝑋1 + 𝑋2 < = 200

9𝑋1 + 6𝑋2 < = 1566

12𝑋1 + 16𝑋2 < = 2880

𝑋1 > = 0

𝑋2 > = 0 O valor de z para a solução ótima do problema apresentado é igual a:

A alternativa "E " está correta.

A resposta correta é a letra E, conforme pode ser verificado na solução obtida pelo método gráfico, apresentada na figura

a seguir.

 Solução da atividade 2 pela tabela simplex. Captura de tela do Excel.

Processing math: 100%

 MÓDULO 2

 Aplicar o solver para solução de problemas de programação linear

UTILIZAÇÃO DO SOLVER PARA SOLUÇÃO DE PROBLEMAS

DE PROGRAMAÇÃO LINEAR

No módulo 1, aprendemos a resolver problemas de programação linear por meio do método simplex, tanto o analítico

quanto o tabular. Aplicamos essas técnicas em alguns exemplos, de modo a entender a lógica do algoritmo. Porém,

pudemos verificar que são muitos os cálculos que precisam ser feitos para resolvermos problemas de programação linear

manualmente, e apenas um erro em uma conta nos levaria a um resultado errado. Contudo, felizmente, existem diversos

softwares de computador que podem ser utilizados para nos auxiliar a encontrar a solução ótima para problemas de

programação matemática, por exemplo:

LINDO

CPLEX

AIMMS

GAMS

MATHPRO

Usando o software de computador adequado, podemos resolver facilmente quaisquer problemas de programação linear.

As técnicas para a solução de problemas de programação linear são, inclusive, desenvolvidas por meio de pacotes de

planilhas eletrônicas. Assim sendo, aprenderemos nesta seção a utilizar o solver do pacote de planilhas eletrônicas Excel

para solução de problemas de programação linear.

Processing math: 100%

  DICA

Os mesmos conceitos e técnicas que apresentaremos a seguir também podem ser aplicados em outros pacotes de

planilhas, dadas as necessidades de alterações em detalhes de implementação.

PASSOS PARA IMPLEMENTAR UM PROBLEMA DE

PROGRAMAÇÃO LINEAR EM PLANILHA

Ragsdale (2009) apresenta cinco passos que devem ser feitos para implementar qualquer problema de programação

linear em uma planilha:

Organize os dados para o modelo (os coeficientes das restrições, os coeficientes da função objetivo etc.) na planilha.

Reserve as células separadas na planilha para representar cada variável de decisão do modelo algébrico. Isso é útil na

determinação de fórmulas para a função e restrições do objetivo.

Crie uma fórmula para cada célula da planilha que corresponda à função objetivo no modelo algébrico.

Para cada restrição, crie uma fórmula em uma célula separada na planilha. Muitas das fórmulas de restrição têm estrutura

semelhante, de modo que, quando possível, crie fórmulas de restrição que possam ser copiadas para implementar outras

fórmulas de restrição.

Processing math: 100%

 5

Use sombras e cores de fundo e/ou bordas para identificar as células que representam as variáveis de decisão, restrições

e funções objetivos do modelo.

INSTALANDO O SOLVER

Demonstraremos, neste módulo, como usar o solver do Excel resolvendo o problema enfrentado pela Fitwear. No entanto,

antes de iniciarmos a resolução do problema, é preciso instalar o solver nos pacotes de planilhas eletrônicas Excel. Para

isso, siga o passo a passo:

Clique em arquivos > opções no Excel, conforme indicado na figura.

 Instalando o solver — Passo 1. Captura do Excel.

O segundo passo é clicar em suplementos na tela que foi aberta.

 Instalando o solver — Passo 2. Captura do Excel.

Na tela seguinte, clique no botão ir, em gerenciar suplementos do Excel.

Processing math: 100%

  Instalando o solver — Passo 3. Captura do Excel.

Na próxima tela, clique na opção solver.

 Instalando o solver — Passo 4. Captura do Excel.

Para finalizar, basta clicar na aba dados para visualizar a opção solver.

 Instalando o solver — Passo 5. Captura do Excel.

UTILIZANDO O SOLVER
Processing math: 100%
 Agora que já temos o solver instalado no nosso Excel, vamos iniciar a resolução do problema da Fitwear visto no módulo

1.

 DICA

Caso seja necessário, retorne ao módulo anterior e relembre como desenvolvemos o modelo matemático do problema.

Observe a seguir o modelo matemático, considerando as variáveis de decisão:

𝑥1

Número de tops de ginástica confeccionados a cada semana.

𝑥2

Número de calças de ginástica confeccionadas a cada semana.

Temos a formulação matemática em sua forma-padrão.

𝑀á𝑥 𝑍 = 28 𝑥1 + 40𝑥2

SUJEITO A:

0, 5𝑥1 + 0, 25𝑥2 ≤ 100 → restrição de horas de corte

0, 25𝑥 → + 0, 5𝑥 → ≤ 160 → restrição de horas de costura

𝑥1 , 𝑥2 ≥ 0 → restrição de não negatividade das variáveis de decisão

 Atenção! Para visualização completa da equação utilize a rolagem horizontal

Processing math: 100%
 Uma das primeiras etapas para a solução do problema deve ser a organização dos dados. Vamos começar representando

as variáveis de decisão, como indicado na figura a seguir. Observe que descrevemos as variáveis de decisão na planilha,

bem como os ganhos semanais com a venda de cada produto (𝑥1 e 𝑥2 ), deixando destacado em amarelo as células

variáveis (ou ajustáveis), que reservamos na planilha para representar as variáveis de decisão do modelo.

 Variáveis de decisão. Captura de tela do Excel.

O próximo passo é criar uma fórmula que represente a função objetivo de acordo com as variáveis de decisão indicadas

na figura. Para isso, devemos utilizar a função “somarproduto” do Excel, que faz o produto escalar entre dois vetores.

 Função “somarproduto”. Captura de tela do Excel.

A figura a seguir ilustra como inserimos a função objetivo na planilha eletrônica no caso do problema da Fitwear. Observe

que fizemos a função “somarproduto” entre o vetor (28,40), que corresponde aos coeficientes da função objetivo, e as

células que destinamos para receber o valor das variáveis de decisão. Com isso, teremos que a célula destacada em

amarelo para a função objetivo recebeu a fórmula 28 * 𝑥1 + 40 * 𝑥2 .

Processing math: 100%

  Função objetivo. Captura de tela do Excel.

De maneira análoga à que fizemos a representação da função objetivo, precisamos representar as restrições. Para isso,

também vamos utilizar a função “somarproduto” do Excel. Veja a seguir como inserimos as duas restrições para o

problema da Fitwear na planilha eletrônica.

RESTRIÇÃO DE HORAS DE CORTE

Observe que fizemos a função “somarproduto” entre os vetores que indicam os coeficientes das restrições e as células

que destinamos para receber o valor das variáveis de decisão. Com isso, teremos que a célula destacada em amarelo na

figura restrição de horas de corte recebeu a fórmula 0, 5𝑥1 + 0, 25𝑥2 .

 Restrição de horas de corte. Captura de tela do Excel.

RESTRIÇÃO DE HORAS DE COSTURA

Observe que a célula destacada em amarelo na figura restrição de horas de costura recebeu a fórmula 0, 25𝑥1 + 0, 5 𝑥2 .

Processing math: 100%

  Restrição de horas de costura. Captura de tela do Excel.

FINALMENTE, TERMINAMOS A IMPLEMENTAÇÃO DO MODELO DO

PROBLEMA DE PROGRAMAÇÃO LINEAR DA FITWEAR NO EXCEL.
ENTRETANTO, AINDA PRECISAMOS RESOLVÊ-LO.

Para isso, é preciso indicar para o solver o que cada célula da planilha representa:

A FUNÇÃO OBJETIVO

AS VARIÁVEIS DE DECISÃO

AS RESTRIÇÕES

Assim sendo, devemos definir a célula de destino, ou seja, aquela que representa a função objetivo na caixa de diálogo

parâmetros do solver, como indicado na próxima figura. Observe que a célula E9 contém a fórmula que representa a

função objetivo para o nosso problema, como havíamos preparado anteriormente. Neste momento, devemos instruir

também o solver para tentar maximizar seu valor, especificando o botão max.

Processing math: 100%

  Definindo a função objetivo na célula de destino. Captura de tela do Excel.

O próximo passo consiste em indicar as células que representam as variáveis de decisão no modelo. Observe, na figura a

seguir, que as células C8 e D8, em nossa planilha, representam as variáveis de decisão para o modelo. O solver

determinará os valores ótimos para essas células.

 Definindo as variáveis de decisão. Captura de tela do Excel.

A seguir, devemos definir as células de restrição na planilha e as restrições que se aplicam a essas células.

 ATENÇÃO

As células de restrição são aquelas em que implementamos as fórmulas para cada restrição.

Para definir as células de restrição, siga os passos:

Clique no botão incluir.

Processing math: 100%

  Especificando as células de restrição — passo 1. Captura de tela do Excel.

Preencha a caixa de diálogo incluir restrições.

 Especificando as células de restrição — passo 2. Captura de tela do Excel.

Observe que as células E13 e E14 representam as células de restrição cujos valores devem ser menores ou iguais aos

indicados nas células G13 e G14, respectivamente.

 Especificando as células de restrição — passo 3. Captura de tela do Excel.

Já especificamos as restrições, mas ainda precisamos determinar que as variáveis de decisão devem ser iguais ou

maiores do que zero. Para isso, basta clicar em tornar variáveis irrestritas não negativas na caixa de diálogo parâmetros

Processing math: 100%

 do solver, conforme indicado na figura a seguir. Enfim, para encontrarmos a solução ótima para o problema, basta clicar

no botão resolver.

 Condições de não negatividade. Captura de tela do Excel.

A figura a seguir apresenta a tela de saída do Excel com a solução ótima para o problema da Fitwear.

 Solução ótima para o problema da Fitwear. Captura de tela do Excel.

Observe que 𝑥1 deve ser 53,33, 𝑥2 recebe 293,333 e o valor ótimo de 𝑧 é igual a 13.226,67.

Processing math: 100%

 UTILIZAÇÃO DO SOLVER PARA A SOLUÇÃO DE
PROBLEMAS DE PROGRAMAÇÃO LINEAR

O vídeo mostra um passo a passo para a resolução de um problema de programação linear no solver do Excel.

VERIFICANDO O APRENDIZADO

1. A FÁBRICA XYZ PRODUZ RAÇÕES PARA A ALIMENTAÇÃO DE GADO. AS RAÇÕES SÃO

ELABORADAS A PARTIR DA MISTURA DE TRÊS DIFERENTES TIPOS DE GRÃOS: 1, 2 E 3. TRÊS
NUTRIENTES SÃO CONSIDERADOS NO PRODUTO FINAL: A, B E C.

SABE-SE QUE O GRÃO DO TIPO 1 CUSTA R$35,00 POR KG. UM QUILO DE GRÃO 1 POSSUI 30MG DE
NUTRIENTE A, 10MG DE NUTRIENTE B E 43MG DE NUTRIENTE C. O GRÃO DO TIPO 2 CUSTA
R$23,00 POR KG. AINDA, UM QUILO DO GRÃO 2 POSSUI 28MG DO NUTRIENTE A, 17MG DO
NUTRIENTE B E 40MG DO NUTRIENTE C. O GRÃO DO TIPO 3 POSSUI APENAS 70MG DO NUTRIENTE
TIPO
Processing math:A100%
E UM QUILO DESTE TIPO DE GRÃO CUSTA R$78,00.
 A RAÇÃO PARA GADO DEVE CONTER, NO MÍNIMO, 1250MG DE NUTRIENTE A, 380MG DO
NUTRIENTE B E 980MG DO NUTRIENTE C.

O ANALISTA DESEJA DETERMINAR UMA COMPOSIÇÃO DA RAÇÃO QUE MINIMIZE OS CUSTOS DE

PRODUÇÃO, CONSIDERANDO QUE AS NECESSIDADES MÍNIMAS DOS NUTRIENTES SEJAM
ATENDIDAS. DESSE MODO, É POSSÍVEL AFIRMAR QUE A SOLUÇÃO ÓTIMA PARA O PROBLEMA TEM
UM VALOR DE 𝑧 IGUAL A:

A) 262,84

B) 1262,84

C) 2262,84

D) 3262,84

E) 4262,84

2. UMA MÃE ESTÁ MUITO PREOCUPADA COM A ALIMENTAÇÃO DE SEUS FILHOS. ELA DESEJA QUE
AS CRIANÇAS TENHAM UMA ALIMENTAÇÃO EQUILIBRADA E, POR ISSO, CONSULTOU UMA
NUTRICIONISTA QUE LHE RECOMENDOU QUE ELES COMAM, NO MÍNIMO, 10MG DE VITAMINA A,
70MG DE VITAMINA C E 250MG DE VITAMINA D POR DIA.

PORÉM, ALÉM DE SE PREOCUPAR COM A QUALIDADE DA ALIMENTAÇÃO, ESSA MÃE TAMBÉM

ESTÁ PREOCUPADA COM OS CUSTOS. ELA DESEJA OFERECER AOS SEUS FILHOS ESSA DIETA
EQUILIBRADA, PORÉM AO MENOR CUSTO POSSÍVEL. POR ISSO, ELA FEZ UMA PESQUISA E
DESCOBRIU AS INFORMAÇÕES NUTRICIONAIS PARA DIFERENTES TIPOS DE ALIMENTO,
CONFORME APRESENTADO NA TABELA.

VITAMINA LEITE (L) CARNE (KG) PEIXE (KG) SALADA (100G)

A 2 2 10 20

C 50 20 10 80

D 80 70 10 80

 ATENÇÃO! PARA VISUALIZAÇÃOCOMPLETA DA TABELA UTILIZE A ROLAGEM HORIZONTAL

 INFORMAÇÕES NUTRICIONAIS EM MG

A MÃE TAMBÉM FOI AO SUPERMERCADO E VERIFICOU QUE UM LITRO DE LEITE CUSTA R$2,00, UM
QUILO DE CARNE CUSTA R$20,00, UM QUILO DE PEIXE CUSTA R$25,00 E PARA PREPARAR 100G DE
Processing math: 100%
 SALADA ELA GASTARIA R$3,00. DESSE MODO, É POSSÍVEL AFIRMAR QUE A SOLUÇÃO ÓTIMA
PARA O PROBLEMA TEM UM VALOR DE Z IGUAL A:

A) 2,46

B) 3,46

C) 4,46

D) 5,46

E) 6,46

GABARITO

1. A fábrica XYZ produz rações para a alimentação de gado. As rações são elaboradas a partir da mistura de três

diferentes tipos de grãos: 1, 2 e 3. Três nutrientes são considerados no produto final: A, B e C.

Sabe-se que o grão do tipo 1 custa R$35,00 por kg. Um quilo de grão 1 possui 30mg de nutriente A, 10mg de nutriente B

e 43mg de nutriente C. O grão do tipo 2 custa R$23,00 por kg. Ainda, um quilo do grão 2 possui 28mg do nutriente A,

17mg do nutriente B e 40mg do nutriente C. O grão do tipo 3 possui apenas 70mg do nutriente tipo A e um quilo deste

tipo de grão custa R$78,00.

A ração para gado deve conter, no mínimo, 1250mg de nutriente A, 380mg do nutriente B e 980mg do nutriente C.

O analista deseja determinar uma composição da ração que minimize os custos de produção, considerando que as

necessidades mínimas dos nutrientes sejam atendidas. Desse modo, é possível afirmar que a solução ótima para o

problema tem um valor de 𝑧 igual a:

A alternativa "B " está correta.

Como as rações são elaboradas a partir de três diferentes tipos de grãos, temos que as variáveis de decisão são:

𝑥1 = quilos de grão tipo 1 usados na produção de um quilo de ração

𝑥2 = quilos de grão tipo 2 usados na produção de um quilo de ração

𝑥3 = quilos de grão tipo 3 usados na produção de um quilo de ração

Como se deseja minimizar o custo de produção e sabe-se o custo do quilo de cada tipo de grão, temos a seguinte função

objetivo:

𝑀𝑖𝑛 𝑍 = 35𝑥1 + 23𝑥2 + 78𝑥3

Logo, podemos afirmar que a resposta certa para o exercício é a Letra E. Porém, vamos continuar a construção do modelo

matemático para este problema.

A ração deve conter, no mínimo, 1250mg de nutriente A, 380mg do nutriente B e 980mg do nutriente C. Assim, teremos

três restrições com relação à quantidade dos diferentes tipos de nutrientes. São elas:

30𝑥1 + 28𝑥2 + 70𝑥3 ≥ 1250 → Nutriente A

10𝑥math:
Processing 1 + 17 𝑥2 ≥
100% 380 → Nutriente B
 43𝑥1 + 40𝑥3 ≥ 980 → Nutriente C

Portanto, temos que o modelo para este problema é:

Min Z = 35x1 + 23x2 + 78x3

Sujeito a:

30x1 + 28x2 + 70x3 ≥ 1250

10x1 + 17x2 ≥ 380

43x1 + 40x3 ≥ 980

x1 , x2 , x3 , x4 ≥ 0

A figura apresenta a tela de saída do Excel com a solução ótima para o problema. Observe que x1 deve ser 22,79, x2

recebe 20,22 e x3 é nulo, sendo o valor ótimo de 𝑧 igual a 1262,84.

 Solução ótima para o problema da Atividade 1. Captura de tela do Excel.

2. Uma mãe está muito preocupada com a alimentação de seus filhos. Ela deseja que as crianças tenham uma

alimentação equilibrada e, por isso, consultou uma nutricionista que lhe recomendou que eles comam, no mínimo, 10mg

de vitamina A, 70mg de vitamina C e 250mg de vitamina D por dia.

Porém, além de se preocupar com a qualidade da alimentação, essa mãe também está preocupada com os custos. Ela

deseja oferecer aos seus filhos essa dieta equilibrada, porém ao menor custo possível. Por isso, ela fez uma pesquisa e

descobriu as informações nutricionais para diferentes tipos de alimento, conforme apresentado na tabela.

Vitamina Leite (l) Carne (kg) Peixe (kg) Salada (100g)

A 2 2 10 20

C 50 20 10 80

Processing math: 100%

 D 80 70 10 80

 Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal

 Informações nutricionais em mg

A mãe também foi ao supermercado e verificou que um litro de leite custa R$2,00, um quilo de carne custa R$20,00, um

quilo de peixe custa R$25,00 e para preparar 100g de salada ela gastaria R$3,00. Desse modo, é possível afirmar que a

solução ótima para o problema tem um valor de z igual a:

A alternativa "E " está correta.

A variável de decisão deve ser xi, sendo x a quantidade de alimento do tipo “i” a ser consumida por dia. Logo, temos:

𝑥1 = litros de leite a serem consumidos por dia pelas crianças

𝑥2 = quilos de carne a serem consumidos por dia pelas crianças

𝑥3 = quilos de peixe a serem consumidos por dia pelas crianças

𝑥4 = 100g de salada a serem consumidos por dia pelas crianças

O modelo para este problema é:

𝑀𝑖𝑛 𝑍 = 2𝑥1 + 20𝑥2 + 25𝑥3 + 3𝑥4

Sujeito a:

2𝑥1 + 2𝑥2 + 10𝑥3 + 20𝑥4 ≥ 10

50𝑥1 + 20𝑥2 + 10𝑥3 + 30𝑥4 ≥ 70

80𝑥1 + 70𝑥2 + 10𝑥3 + 80𝑥4 ≥ 250

𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0

A figura apresenta a tela de saída do Excel com a solução ótima para o problema. Observe que 𝑥1 deve ser 2,91 litros de

leite, 𝑥2 e 𝑥3 são nulos, enquanto 𝑥4 é igual a 208,33g de salada, sendo o valor ótimo de 𝑧 igual a 6,46.

 Solução ótima para o problema da Atividade 2. Captura de tela do Excel.

Processing math: 100%

 CONCLUSÃO

CONSIDERAÇÕES FINAIS

A pesquisa operacional pode nos auxiliar no apoio a processos de decisão, em especial para problemas complexos.

Estudamos o método simplex, tanto pelo modo analítico quanto pelo tabular, por meio do qual aprendemos a resolver

problemas de programação linear, encontrando a solução ótima para este tipo de problema. Contudo, resolvê-los

manualmente é muito trabalhoso, envolvendo um grande número de cálculos. Um simples erro em uma das contas

requeridas implica encontrar uma solução equivocada para o problema. Por isso, é muito importante conhecer softwares

computacionais que permitem a solução de problemas de programação matemática.

São muitos os softwares computacionais dedicados à solução de problemas de programação matemática, como o

CPLEx, o GAMS, o LINDO, o LINGO etc. No entanto, problemas de programação linear podem ser resolvidos pelo solver de

pacotes de planilhas eletrônicas. Aprendemos a solucionar problemas de programação linear por meio do solver do Excel.

Isso certamente facilitará que consigamos aplicar a Pesquisa Operacional para a solução de problemas reais.

AVALIAÇÃO DO TEMA:

REFERÊNCIAS

ARENALES, M. et al. Pesquisa operacional. Rio de Janeiro: Elsevier, 2007.

FOGLIATO, F. Pesquisa operacional. Porto Alegre, 2006. (Notas de aula).

GOLDBARG, M. C.; LUNA, H. P. Otimização combinatória e programação linear. 2. ed. São Paulo: Campus, 2005.

LACHTERMACHER, G. Pesquisa operacional na tomada de decisões. Rio de Janeiro: Campus, 2009.

RAGSDALE, C. T. Modelagem e análise de decisão. São Paulo: Cengage Learning, 2014.

RODRIGUES, L. H.; AHLERT, F.; LACERDA, D. P.; CAMARGO, L. F. R.; LIMA, P. Pesquisa operacional: programação linear

passo a passo: do entendimento do problema à interpretação da solução. São Leopoldo: Unisinos, 2014.

Processing math: 100%

 EXPLORE+

Para saber mais sobre os assuntos tratados nesta aula, leia:

Conheça métodos preparatórios (utilizados antes do emprego do simplex) para resolver problemas diferentes do padrão

de maximização com restrições do tipo menor ou igual no capítulo 4 do livro “Operations research: applications and

algorithms (Vol. 3)”, de Winston e Goldberg (2004).

Para se aprofundar na utilização do solver para a solução de problemas de programação linear, sugerimos a leitura do

capítulo 3 do livro “Modelagem e análise de decisão”, de Ragsdale (2009).

CONTEUDISTA

Renata Albergaria de Mello Bandeira

 CURRÍCULO LATTES

Processing math: 100%