Programação Linear

Licenciatura em Matemática
[Link]@[Link]

Prof. Msc. Ailton Arminda

USTP - FCT

1 de maio de 2024
 Apresentação

Apresentação
Ailton Arminda Lima Pereira José
Licenciado em Matemática Pura (USTP-FCT)
Mestre em Matemática e Aplicações-Estatística e Otimização
(UA-PT)
Especialização em Estatística
Especialização em Programação Linear
Especialização em Números, Sequência e Operações
Professor da USTP-FCT
Professor da USTP-ISEC
Professor do Ensino Secundário 2º ciclo: Liceu Nacional
Coordenador de Matemática do ISEC
Coordenador do curso de Matemática do ISEC
Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 2 / 173
 Apresentação Interesses

Interesses:

Álgebra Linear
Investigação Operacional
Modelos Preditivos (Machine Learnning)
Matemática Financeira-Engenharia Financeira
Estatística-Probabilidade
Equações Diferenciais
Matemática Computacional (Python, Xpress, R-studio, Matlab,
SageMath, Octave, Scilab e LPSolve)
Análise Matemática e Complexa
Educação Matemática-Etnomatemática-Didática Matemática

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 3 / 173
 Programa

Programa

Programação Linear
Modelos de Problemas de Programação Linear
Introdução (P. P. L)
Exemplos clássicos de modelagem: problema de dieta; problema
de alocação de recursos; problema do transporte
Programação Linear: Introdução
Resolução gráfica de um P. P. L.
Forma padrão de um P. P. L.
Soluções básicas viáveis – pontos extremos
P. P. L. na forma básica

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 4 / 173
 Programa

Programa

Programação Linear
Método Simplex
Fundamentos teóricos – Simplex
Quadro ou Tabela do Simplex
Interpretação geométrica do Simplex
Método das duas fases
Dualidade. Formulação do dual
Obtenção da solução dual pela tabela Simplex
Interpretação económica do dual

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 5 / 173
 Programa

Programa

Programação Linear
Uso do software (Solver do Excel e PHPSimplex (Web))
Problema do Transporte
Modelagem
Solução do problema do transporte
O problema de afetação

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 6 / 173
 Programa

Introdução
Introdução
A Programação Linear (PL) está relacionada com a otimização
(minimização ou maximização) de uma função linear, satisfazendo
um conjunto de equações e/ou inequações (restrições) igualmente
lineares. Este problema foi inicialmente concebido por George B.
Dantzig em 1947 quando trabalhava como consultor matemático da
Unidade de Controlo da Forca Aérea Norte Americana. Apesar de
atualmente se saber que o matemático e economista soviético L. V.
Kantorovich formulou e resolveu previamente o mesmo tipo de
problemas em 1939, o seu trabalho permaneceu ignorado até 1959.
Por esse facto, é atribuída a Dantzig a conceção dos problemas de
PL, sendo a denominação Programação Linear usada pela primeira
vez pelo economista e matemático T. C. Koopmans em 1948.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 7 / 173
 Programa

Introdução

Introdução
A programação linear (PL) é uma área da Matemática Aplicada
usada no ramo de Investigação Operacional (IO). A origem da IO
como ciência é atribuída à coordenação das operações militares
durante a 2ª Guerra Mundial. A palavra “programação” refere-se a
uma programação de tarefas ou planificação, não a uma programação
no sentido da informática. A palavra “Linear” advém do facto de as
expressões (condições) utilizadas serem lineares.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 8 / 173
 Programa

Introdução

Introdução
O objetivo é otimizar problemas de decisão, através da utilização de
modelos que representem uma realidade. A solução ótima na
globalidade é um mínimo ou máximo a ser alcançado, nas condições
existentes. A aplicabilidade da PL é enorme, pode aplicar-se a
situações militares, indústria, agricultura, economia, saúde, etc.
Contudo, é na área económica que mais se tem desenvolvido. Desejo
que os alunos se familiarizem com conceitos sobre a decisão em
termos de planeamento, que podem ter a ver com minimizar
consumos, custos ou maximizar lucros.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 9 / 173
 Programa

Um modelo de PL é constituído por:

Variáveis de decisão (quantificam as decisões a tomar).
Objetivo (o que se pretende otimizar).
Restrições (condições que têm de ser satisfeitas).

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 10 / 173
 Programa

Introdução
Os procedimentos para determinar a solução (de modo a que o
objetivo se cumpra) podem ser variados. O mais antigo é o método
simplex. O método simplex consiste de um algoritmo que permite
resolver problemas de Programação Linear. Contudo o método que
iremos utilizar baseia-se na representação gráfica. Foi George Dantzig
que, entre 1947 e 1949, desenvolveu os conceitos principais da PL.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 11 / 173
 Programa

Como curiosidade refira-se que o primeiro problema resolvido por

Dantzig – foi um problema de dieta de custo mínimo. Este problema
necessitava da resolução de um sistema de 9 equações (requisitos de
nutrição) e 77 variáveis de decisão. Em 1947, George Dantzig e
outros cientistas do Departamento da Força Aérea Americana,
apresentaram um método denominado Simplex para a resolução dos
problemas de Programação Linear (PL). As primeiras e grandes
aplicações foram no domínio militar.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 12 / 173
 Programa

Modelos de Problemas

A Programação Linear permite modelar matematicamente muitos

problemas reais. A principal característica destes modelos é a de que
objetivo a otimizar e as restrições podem ser expressas através de
expressões lineares conjunto de variáveis que representam as decisões.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 13 / 173
 Programa

Problema de dieta (problema minimização)

Cinco tipos de alimentos (ver figura) estão disponíveis na elaboração
do lanche escolar numa escola do ensino básico. Cada porção (50
gramas) de cada tipo de alimento contém os elementos nutritivos
calorias, gordura, proteína e hidratos de carbono. A composição dos
alimentos dos tipos 1, 2, 3, 4 e 5 fornecem os seguintes elementos
nutritivos (em gramas):

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 14 / 173
 Programa

Problema de dieta (problema minimização)

Os estudantes devem ingerir pelo menos 225 calorias, 9 g de gordura,

13 g de proteínas e 15 g de Hidratos de carbono por refeição. Os
preços de cada porção dos alimentos do tipo 1, 2, 3, 4 e 5 são: 0.8;
1.0; 1.0; 1.2 e 0.75 dobras, respetivamente. Formule o problema de
modo a que o custo seja minimizado.
Construir um modelo matemático (de Programação Linear) implica
decidir: Quais são as variáveis decisões? quais são as restrições que
existem? Qual é o objetivo?
Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 15 / 173
 Programa

Identificar as variáveis de decisão

As variáveis de decisão são as quantidades de cada tipo de alimento
contidas numa refeição. No presente exemplo, pretendemos garantir
quantidades mínimas por cada elemento nutritivo (calorias, gordura,
proteínas e Hidratos de carbono), em gramas, que os estudantes
devem ingerir na refeição. O objetivo é o de minimizar o custo total
da refeição.
Representando essas quantidades em termos algébricos, tem-se:
x1 = quantidade de porções de alimentos do tipo 1.
x2 = quantidade de porções de alimentos do tipo 2.
x3 = quantidade de porções de alimentos do tipo 3.
x4 = quantidade de porções de alimentos do tipo 4.
x5 = quantidade de porções de alimentos do tipo 5.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 16 / 173
 Programa

Identificar as restrições
As restrições dizem respeito às quantidades mínimas dos elementos
nutritivos que devem ser ingeridos por refeição. Cada porção do tipo
de alimentos 1 fornece 103 Kcal. Como cada refeição inclui x1
porções de tipos de alimentos 1, então o elemento nutritivo calorias
fornecidas por alimentos do tipo 1 será 103x1 por refeição.
Analogamente, as calorias fornecidas pelos restantes tipos alimentos
serão 40x2 , 38x3 ,75x4 , 40x5 , respetivamente. Assim, a quantidade
total de calorias na composição dos cinco tipos de alimentos será:

103x1 + 40x2 + 38x3 + 75x4 + 40x5

Sabe-se que os estudantes devem ingerir pelo menos 225 calorias por
refeição. Assim, a restrição relativa ao elemento nutritivo calorias
será:
103x1 + 40x2 + 38x3 + 75x4 + 40x5 ≥ 225
Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 17 / 173
 Programa

Para obter a restrições relativas aos elementos nutritivos gordura,

proteínas e Hidratos de carbono por refeição, utiliza-se um raciocínio
similar. As restrições resultantes serão:
Restrições
1.5x1 + 3x2 + 2x3 + 8x4 + 2x5 ≥ 9
4x1 + x2 + 2x3 + 6x4 + x5 ≥ 13
30x1 + x2 + 1.3x3 + 1.2x4 + x5 ≥ 15
Para finalizar, deseja-se restringir as variáveis de decisão no domínio
dos reais não-negativos, isto é, xj ≥ 0, j = 1, 2, 3, 4, 5. Essas
restrições, uma para cada variável de decisão, são denominadas
restrições de não-negatividade. Note-se que uma refeição pode incluir
um número não inteiro de porções de cada tipo de alimento.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 18 / 173
 Programa

Identificar o objetivo

Objetivo
O objetivo é minimizar o custo total:
Z1 = 0.80x1 + x2 + x3 + 1.2x4 + 0.75x5
Habitualmente, o modelo de programação linear escreve-se na
seguinte forma:

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 19 / 173
 Programa

Modelo

min Z1 = 0.80x1 + x2 + x3 + 1.2x4 + 0.75x5

sujeito a:
103x1 + 40x2 + 38x3 + 75x4 + 40x5 ≥ 225
1.5x1 + 3x2 + 2x3 + 8x4 + 2x5 ≥ 9
4x1 + x2 + 2x3 + 6x4 + x5 ≥ 13
30x1 + x2 + 1.3x3 + 1.2x4 + x5 ≥ 15
xi ≥ 0, ∀i ∈ {1, 2, 3, 4}.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 20 / 173
 Programa

Problema de alocação de recursos

Com o aumento da procura no mercado internacional, a empresa

NCBA (National Cooperativa Business Association) pretende
aumentar a produção do tipo café robusta e tipo café arábica. Para
aumentar a produção até 30 toneladas café tipo robusta e 20
toneladas do café tipo arábica, a empresa NCBA precisa de novas
terras e de empregar mais trabalhadores. Para produzir uma tonelada
do café tipo robusta, são necessários 20 hectares e 15 trabalhadores.
Para produzir cada tonelada de café tipo arábica são necessários 40
hectares e 12 trabalhadores. A empresa dispõe apenas de 800
hectares e pode recrutar no máximo 450 trabalhadores. A NCBA
quer planear a produção de cada tipo de café de modo a maximizar a
produção total. Para tornar mais fácil criar um modelo matemático,
os dados são condensados numa tabela, como se mostra a seguir:

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 21 / 173
 Programa

Problema de dieta (problema minimização)

De seguida vamos identificar as variáveis decisões e as restrições do

problema.
As variáveis decisão
x1 = quantidade de produção (em toneladas) do tipo café
robusta
x2 = quantidade de produção (em toneladas) do tipo café
arábica.
Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 22 / 173
 Programa

As restrições
As restrições são, respetivamente, a área disponível, o número
máximo de trabalhadores e as quantidades máximas e mínimas a
produzir. Tem-se então:

20x1 + 40x2 ≤ 800

15x1 + 12x2 ≤ 450

x1 ≤ 30
x2 ≤ 20
x1 , x2 ≥ 0

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 23 / 173
 Programa

O objetivo
Maximizar quantidade da produção (em toneladas) dos tipos de café
robusta e arábica:
x1 + x2

Modelo

max Z = x1 + x2
sujeito a:
20x1 + 40x2 ≤ 800
15x1 + 12x2 ≤ 450
x1 ≤ 30
x2 ≤ 20
x1 , x2 ≥ 0.
Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 24 / 173
 Programa

Portanto, ao formulamos um modelo linear devemos ter o cuidado de

distinguir sempre as seguintes fases:
Identificação das variáveis de decisão
Identificação da função objetivo
Identificação das restrições
Formulação matemática
Depois de se ter obtido a formulação matemática é então possível
resolver o problema de otimização.
O método de programação linear permite o recurso à metodologia
gráfica e à metodologia algébrica, manual ou com recurso a um
computador.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 25 / 173
 Programa

Na posse de toda esta informação, é mais fácil tomar decisões

acertadas no domínio da gestão em diversas aplicações, tais como:
Aplicações
Planeamento agregado de produção
Análise de produtividade de serviços
Planeamento de produtos
Otimização do fluxo produtivo Otimização do processo de
produção

Mas as aplicações da programação linear não terminam por aqui.

Esta pode ser extremamente útil em áreas tais como medicina,
agricultura, política florestal, sector militar e redes de transportes.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 26 / 173
 Programa

Definições e Conceitos

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 27 / 173
 Programa

Definições e Conceitos

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 28 / 173
 Programa

Definições e Conceitos

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 29 / 173
 Programa

Definições e Conceitos

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 30 / 173
 Programa

Definições e Conceitos

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 31 / 173
 Programa

Formas de um problema de PL e operações de

reformulação
De seguida apresentamos a forma padrão (standard) e as formas
canónicas de um problema de programação linear com m restrições e
n variáveis.
Resumo

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 32 / 173
 Programa

Em termos de matriciais, a forma de um problema de PL dada por:

Matricial

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 33 / 173
 Programa

Para converter os problemas numa determinada forma, poderemos

ter necessidade de recorrer às seguintes operações de reformulação.
Matricial

No exemplo do problema de alocação, temos:

Resumo

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 34 / 173
 Programa

Resumo

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 35 / 173
 Programa

Resumo

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 36 / 173
 Programa

Convexidade e caracterização de poliedros

O conjunto das soluções admissíveis de um problema de programação

linear é um caso particular de conjuntos convexos.
Para mais fácil compreensão, são apresentados exemplos que
exploram estes conceitos em R2 , no entanto deve ter-se sempre
presente o facto de que os conceitos são válidos em Rn .
Conjunto convexo
Um conjunto S ⊆ Rn é conjunto convexo se ∀x1 , x2 ∈ S, então
λx1 + (1 − λ)x2 ∈ S para todo λ ∈ [0, 1]. Ou seja, um conjunto
S ⊆ Rn diz-se convexo se o segmento de reta entre quaisquer dois
pontos em S está contido em S, isto é, se para quaisquer x1 , x2 ∈ S e
λ[0, 1], verifica-se que λx1 + (1 − λ)x2 ∈ S.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 37 / 173
 Programa

Exemplos
W = {(x1 , x2 ) : x12 + x22 ≤ 4}
V = {(x1 , x2 ) : 0 ≤ x1 ≤ 3, x1 ≥ x2 , x2 ≥ 0}

Nota
Por convenção, o conjunto vazio é um conjunto convexo

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 38 / 173
 Programa

Lemma
O conjunto das soluções admissíveis de um sistema de desigualdades
lineares da forma S = {x ∈ Rn : Ax ≤ b} é um conjunto convexo.

Definition
Poliedro: Um poliedro P é um subconjunto de Rn descrito por um
conjunto finito de desigualdades lineares, P = {x ∈ Rn : Ax ≤ b}.

Nota
Note que o Exemplo anterior W é um conjunto convexo, mas não é
um poliedro, pois não pode ser descrito por um número finito de
desigualdades, e V é um poliedro. Em R2 , um poliedro é a interseção
de um número finito de semiplanos.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 39 / 173
 Programa

Lemma
Um poliedro em Rn é um conjunto convexo.

Definition
Politopo: Seja S ⊂ Rn . Dizemos que um conjunto S é um politopo,
quando S é um poliedro limitado.

Exemplo
P = {(x1 , x2 ) ∈ R2 : x1 + 2x2 ≤ 20; 5x1 + 3x2 ≤ 15 x1 , x2 ≥ 0}
Q = {(x1 , x2 ) ∈ R2 : x1 + 2x2 ≤ 20; 5x1 + 3x2 ≤ 15}
Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 40 / 173
 Programa

Nota
O poliedro P é um politopo, mas o poliedro Q não é um politopo.

Nota
Os poliedros podem ser caracterizados através de um conjunto de
desigualdades (ver atrás) ou através de um conjunto de pontos
(pontos extremos) e vetores (raios extremos). De seguida vamos
introduzir alguns conceitos que nos permitem definir pontos extremos
e raios extremos.

Definition
Combinação linear: Um vetor x ∈ Rn é uma combinação linear dos
vetores x1 , x2 , . . . , xk ∈ Rn , se existirem escalares λ ∈ Rk , tais que
x = ki=1 λi xi
P

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 41 / 173
 Programa

Adicionalmente, se

Ponto extremo
Um ponto x de um conjunto convexo S ⊆ Rn diz-se um ponto
extremo se não existirem dois pontos distintos x1 , x2 ∈ S tais que,
para algum λ, 0 < λ < 1, x = λx1 + (1 − λ)x2 , isto é x não pode ser
escrito como combinação linear convexa de quaisquer dois pontos
distintos de S. Observe que, Figura, x1 é o ponto extremo de S, no
entanto x2 e x3 não são pontos extremos.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 42 / 173
 Programa

Geometricamente

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 43 / 173
 Programa

Combinação convexa dos pontos extremos

Dados os pontos extremos x 1 , x 2 , . . . , x k e o polítopo S. Para
todos x ∈ S, x pode ser escrito como combinação convexa dos
pontos extremos x = ki=1 λi x i , ( ki=1 λi = 1)
P P

Raio
Um vetor r ∈ Rn é um raio de S se e só se para qualquer ponto
x ∈ S, o conjunto {y ∈ Rn : y = x + λr , λ ≥ 0} ⊆ S.
Um raio r de S é um raio extremo de S, se r = λr1 + (1 − λ)r2 ,
onde r1 e r2 são raios de S, então r1 = λ1 r e
r2 = λ2 r , λ1 , λ2 ≥ 0.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 44 / 173
 Programa

Exemplo
S é um poliedro ilimitado (ver Figura). Os vetores r1 e r2 são raios,
isto é o conjunto de pontos da forma {y = x + λr , λ ≥ 0} pertence
ao poliedro S. Os vetores r1 , r2 são raios extremos do poliedro S.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 45 / 173
 Interpretação Geométrica

Região admissível dos problemas de PL

Enunciado
A resolução gráfica de problemas de programação linear só pode ser
realizada quando não estão envolvidas mais de três variáveis decisão,
e particularmente pode ser utilizada facilmente quando existem duas
variáveis de decisão. Na resolução gráfica em R2 começamos por
identificar a região admissível.

Exposição
O conjunto dos pontos que satisfazem a desigualdade da forma
a1 x1 + a2 x2 ≤ b, ou da forma a1 x1 + a2 x2 ≥ b, onde pelo menos uma
das constantes a1 ou a2 é diferente de zero, é denominado como
semiplano. Portanto, uma reta divide o plano (espaço de dimensão 2)
em duas regiões denominadas semiplanos.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 46 / 173
 Interpretação Geométrica

Exposição
Uma inequação do tipo a1 x1 + a2 x2 ≤ b representa o semiplano que
inclui o conjunto dos pontos da reta a1 x1 + a2 x2 = b, juntamente
com os pontos que estão num dos lados da reta. Por exemplo,
20x1 + 40x2 ≤ 800 é o conjunto dos pontos que aparecem
sombreados no gráfico a seguir:

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 47 / 173
 Interpretação Geométrica

Exposição
Um semiplano é a representação gráfica de uma inequação linear em
duas variáveis. A representação gráfica de um sistema de inequações
lineares em duas variáveis será a interseção dos semiplanos
correspondentes a cada inequação linear. As restrições de um
problema de PL juntamente com as condições de não-negatividade
formam um conjunto de semiplanos cuja intersecção determina um
conjunto de pontos em R2 , denominado por região das soluções
admissíveis ou, simplesmente, região admissível.

Definição
As soluções admissíveis são quaisquer especificações de valores para
as variáveis x1 , x2 , . . . , xn que satisfaçam as restrições do problema e
as condições de não negatividade.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 48 / 173
 Interpretação Geométrica

Definição
Região admissível é o conjunto de todas as soluções admissíveis, ou
seja, o conjunto dos pontos que satisfazem todas as restrições.

Nota
A região admissível define um poliedro. O poliedro é limitado
(politopo), ilimitado ou vazio dependendo das restrições que o
definem. Para mais detalhes, vamos considerar o exemplo seguinte.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 49 / 173
 Interpretação Geométrica

Simplex

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 50 / 173
 Interpretação Geométrica

Simplex

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 51 / 173
 Interpretação Geométrica

Simplex

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 52 / 173
 Interpretação Geométrica

Simplex

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 53 / 173
 Interpretação Geométrica

Simplex

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 54 / 173
 Interpretação Geométrica

Simplex

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 55 / 173
 Interpretação Geométrica

Simplex

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 56 / 173
 Interpretação Geométrica

Simplex

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 57 / 173
 Interpretação Geométrica

Método Big M
Até agora abordamos o método >Simplex para PPL’s com
restrições do tipo (≤) e bj ≥ 0.
A SBA/SBV inicial desses PPL’s é encontrada de forma trivial,
deixando as variáveis de folga serem VB’s iniciais.
No entanto, quando o PPL possuir restrições da forma:
n
X n
X n
X
aij xj = bj ; aij xj ≥ bj ; ou aij xj ≤ −bj
j=1 j=1 j=1

a sua forma padrão não equivale à forma canónica e, por

conseguinte, não terá uma SBA/SBV inicial.
Nesse caso, é preciso transformar o problema e buscar esta
SBA/SBV.
Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 58 / 173
 Interpretação Geométrica

Solução inicial artificial

Como encontrar a SBA/SBV inicial?

Usa-se a técnica das variáveis artificiais

Introduz-se uma variável artificial em cada restrição que assim
necessitar;
Essa variável artificial desempenha o papel de folga na primeira
iteração;
Todas as variáveis artificiais são descartadas (tornado-as zero),
uma por vez, em iterações posteriores do simplex;

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 59 / 173
 Interpretação Geométrica

Exemplo

Modelo

min W = x1 − 2x2
sujeito a:
x1 + x2 ≥ 2
x1 ≤1
x2 ≥ 3
x1 , x2 ≥ 0.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 60 / 173
 Interpretação Geométrica

Colocando o PPL na forma padrão, temos:

Modelo

min W = x1 − 2x2
sujeito a:
x1 + x2 − F1 = 2
x1 + +F2 = 1
x2 + +F3 = 3
x1 , x2 , F1 , F2 , F3 ≥ 0.

Observe que não existe nenhuma sequência tal que o PPL está
na forma canónica.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 61 / 173
 Interpretação Geométrica

Como proceder?: Adiciona-se uma variável artificial na 1ª

restrição:
Modelo

min W = x1 − 2x2
sujeito a:
x1 + x2 − F 1 + +A1 = 2
x1 + +F2 = 1
x2 + +F3 = 3
x1 , x2 , F1 , F2 , F3 , A1 ≥ 0.

Agora, a sequência {1ª, 4, 5} é uma base para o problema;

Dois métodos pelos quais se busca a SBA/SBV inicial:
O método Grande M (Big M) e o Método das duas fases .
Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 62 / 173
 Interpretação Geométrica

O objetivo desses métodos é eliminar esta variável da base,

chegando a SBA/SBV inicial do PPL original;
O método grande M começa com um PPL na forma padrão
(equações);
Se a equação i não tiver uma folga (ou uma variável que
desempenhe esse papel), uma variável artificial A é adicionada
para formar uma solução inicial;
Como as variáveis artificiais não são parte do PPL original, elas
recebem uma penalidade muito grande na função objetivo;
Os coeficientes dessas variáveis artificiais na FO é um número
muito grande, representado por M (dai o nome do método);
Essa penalidade força as variáveis artificiais a serem iguais a zero
na solução ótima. Isso sempre ocorrerá se o PPL for viável;

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 63 / 173
 Interpretação Geométrica

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 64 / 173
 Interpretação Geométrica

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 65 / 173
 Interpretação Geométrica

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 66 / 173
 Interpretação Geométrica

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 67 / 173
 Interpretação Geométrica

Método de Duas Fases

Método de Duas Fases

O método das Duas Fase é utilizado quando aparecem variáveis
artificiais na forma padrão do problema. A primeira fase consiste em
resolver o problema Z auxiliar para minimizar a soma das variáveis
artificiais visando obter o valor de zero (para evitar inconsistências
matemáticas).
Depois de resolver este primeiro problema, e contanto que o resultado
seja o esperado, a tabela resultante é reorganizada para utilizá-la na
segunda fase do problema original.
Caso contrário, o problema não é factível, ou seja, não tem solução e
não será necessário continuar com a segunda fase.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 68 / 173
 Interpretação Geométrica

1ª Fase
A primeira fase é muito similar ao método Simplex, com a exceção da
construção da primeira tabela, além de ser necessário estudar o
resultado obtido para determinar se a segunda fase será desenvolvida.
Neste caso, a última tabela desta fase será, com algumas
modificações, utilizada como tabela inicial para a segunda fase.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 69 / 173
 Interpretação Geométrica

Construção da primeira tabela:

É elaborada de maneira análoga à tabela inicial do método Simplex,
porém com algumas diferenças.
Como mencionado, nesta primeira fase é solucionado um problema
auxiliar (minimização da soma das variáveis artificiais), com uma
função objetivo auxiliar. Portanto, na primeira linha da tabela, onde
constam os coeficientes das variáveis da função objetivo, aparecerão
todos os termos zero, exceto os coeficientes de variáveis artificiais. O
valor de cada um destes coeficientes é "−1"porque a soma destas
variáveis está sendo minimizada (lembre-se que minimizar Z ′ é o
mesmo que maximizar (−1)Z ′ ).
A outra diferença para a primeira tabela é que agora é preciso
calcular a linha Z (ou linha indicadora).

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 70 / 173
 Interpretação Geométrica

Exemplificação

Descrição
Sendo Zj = (Cbi Pj ) − Cj para i = 1, . . . , m, onde se
P

j = 0, P0 = bi e C0 = 0, e caso contrário Pj = aij

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 71 / 173
 Interpretação Geométrica

Critério de parada e passagem à fase 2

O critério de parada é o mesmo que ocorre no método Simplex
normal. Isto é, quando na linha indicadora nenhum dos valores dos
custos reduzidos é negativo (tendo em vista que o objetivo é
maximização de (−1)Z ′ ).
Depois de haver satisfeito o critério de parada, é preciso determinar
se é possível passar para segunda fase para obter a solução ótima do
problema original. Isto é feito observando o resultado obtido na
primeira fase: se o seu valor for 0, isso significa que o problema
original tem solução e é possível calcular, caso contrário, indica que é
um problema não factível e sem solução.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 72 / 173
 Interpretação Geométrica

Fase II
A segunda fase do método das Duas Fases é desenvolvida
exatamente como no método Simplex, com a exceção de que antes
de iniciar as iterações deve-se eliminar as colunas que correspondem
às variáveis artificiais, e reconstruir a tabela inicial.
Eliminar coluna de variáveis artificiais:
Caso tenhamos concluído que o problema original tem solução,
devemos preparar nossa tabela para a segunda fase. Este passo é
muito simples, trata-se simplesmente de eliminar as colunas
correspondentes às variáveis artificiais.
Construção da tabela inicial:
A tabela inicial, neste caso, mantém-se muito similar à última
tabela da primeira fase. Deve ser modificada a linha da função
objetivo pela linha do problema original e calcular novamente a
linha Z (da mesma forma que na primeira tabela da fase 1).
Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 73 / 173
 Interpretação Geométrica

A partir deste ponto, todas as iterações até alcançar a solução ótima

do problema não apresentam nenhuma diferença do método Simplex.
Identificando casos anómalos e soluções
Solução ótima: quando o critério de parada é satisfeito e não
existam variáveis artificiais na base com valor positivo (os valores
são indicados na coluna P0 ), a otimização foi alcançada. O valor
Z0 atual é a solução ótima do problema, cumprindo para as
variáveis que estão na base. Caso trate-se de um problema de
minimização, o valor ótimo obtido deverá ser multiplicado por
"−1".

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 74 / 173
 Interpretação Geométrica

Continuação
Soluções infinitas: satisfeito o critério de parada, se alguma
variável de decisão não-básica tem um valor 0 na fila Z , significa
que existe outra solução que fornece o mesmo valor ótimo para a
função objetivo. Neste caso, o problema admite infinitas
soluções, todas as quais abrangidas dentro do segmento (ou
parte do plano, região de espaço, etc., conforme o número de
variáveis do problema) definido por AX1 + BX2 = Z0 . Através de
uma nova iteração e fazendo com que a variável de decisão que
tenha 0 na linha Z entre na base, é obtida uma solução diferente
para o mesmo valor ótimo.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 75 / 173
 Interpretação Geométrica

Continuação
Solução ilimitada (unbounded): se toda coluna da variável que
entra na base tem todos os seus elementos negativos ou nulos,
trata-se de um problema não-limitado, ou seja, que tem solução
ilimitada. Não há valor ótimo concreto para a função objetivo,
mas à medida que os valores das variáveis são aumentados, o
valor Z também aumenta sem violar qualquer restrição.
Não existe solução: quando nenhum ponto satisfaz às
restrições do problema, ocorre a inviabilidade, não existindo
nenhuma solução possível para ele. Neste caso, uma vez
terminadas todas as iterações do algoritmo, existem na base
variáveis artificiais em que o valor é superior a zero.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 76 / 173
 Interpretação Geométrica

Continuação
Empate de variável de entrada: quando ocorre um empate
na escolha da variável que entrará, pode-se optar por qualquer
uma delas sem que isto afete a solução final. Por outro lado, se
ela influencia o número de iterações necessárias para obter a
solução. É aconselhável optar pelas variáveis básicas, já que elas
são as que farão parte da solução ótima.
Empate de variável de saída: novamente é possível optar por
qualquer uma delas. No entanto, a fim de não ampliar o
problema e evitar que a entrada fique em um ciclo infinito (caso
degenerado), discrimina-se a favor das variáveis de decisão
fazendo que permaneçam na base. No caso de ser a primeira
fase do método das Duas Fases, se optará por retirar da base as
variáveis artificiais.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 77 / 173
 Interpretação Geométrica

Continuação
Curiosidade na fase 1: ao finalizar a fase 1, caso o problema
original tenha solução, todas as variáveis artificiais na linha
indicadora devem ter o valor "1".
O elemento pivô pode ser nulo?: Não, o elemento pivô
sempre será estritamente positivo já que apenas realizam-se os
quocientes entre os valores não-negativos e maiores que zero
(em um problema de maximização).

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 78 / 173
 Interpretação Geométrica

Resumo

Na fase I, com as variáveis originais e as artificiais tentamos

encontrar um solução básica viável para o PL original, e para isto a
variável artificial deve ser “conduzida” a zero. Para fazer isso, uma
função objetivo artificial (W) é criada, que é a soma de todas as
variáveis artificiais e esta função objetivo é minimizada sujeito às
restrições do problema original usando o método simplex. No final da
Fase I, surgem três casos:
Se o valor mínimo de W ∗ ̸= 0 (uma variável artificial aparece na
base em nível positivo) então o PL original não tem solução
viável e o procedimento de otimização termina. O PL é
inviável.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 79 / 173
 Interpretação Geométrica

Se o valor mínimo de W ∗ = 0 e nenhuma variável artificial

aparecer na base, então uma solução básica viável para o PL
original foi obtida. O PL é viável.
Se o valor mínimo de W ∗ = 0 e uma ou mais variáveis artificiais
aparecerem na base em nível zero, então uma solução viável para
o PL original existe e deve ser gerada. Devemos cuidar dessa
variável artificial e garantir que ela nunca fique positiva durante
os cálculos da Fase II. O PL é viável.
Quando a Fase I resulta em ii) ou iii), seguimos para a Fase II para
encontrar uma solução ótima para o PL original.
A solução básica viável encontrada no final da Fase I agora é usada
como uma solução inicial para o PL original. Significa que o quadro
final da Fase I se torna o quadro inicial para a Fase II na qual a
função objetivo artificial é substituída pela função objetivo original. O
método simplex é então aplicado para chegar à solução ótima do PL.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 80 / 173
 Interpretação Geométrica

Exemplo (PL viável)

Modelo

min Z = 4x1 + 3x2 + 9x3

sujeito a:
2x1 + 4x2 + 6x3 ≤ 15
9
x1 + x2 + x3 =
2
6x1 + x2 + 6x3 ≥ 12
x1 , x2 , x3 ≥ 0.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 81 / 173
 Interpretação Geométrica

Exemplo (PL inviável)

Modelo

max Z = 4x1 + 3x2

sujeito a:
2x1 + 4x2 ≤ 15
x1 + x2 = 10
x1 , x2 ≥ 0.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 82 / 173
 Interpretação Geométrica

Exemplo (PL viável)

Modelo

max Z = x1 + 3x2
sujeito a:
− x1 + x2 ≤ 1
x2 = 10
x1 + x2 = 2
x1 , x2 ≥ 0.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 83 / 173
 Interpretação Geométrica

Exemplo (PL inviável)

Modelo

min Z = 2x1 + x2
sujeito a:
3x1 + 2x2 = 12
x1 + 3x2 ≥ 13
x1 , x2 ≥ 0.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 84 / 173
 Interpretação Geométrica

Exercícios

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 85 / 173
 Interpretação Geométrica

Exercícios

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 86 / 173
 Interpretação Geométrica

Método Dual - Simplex

Dual - Simplex
O método dual-simplex é aplicado em situações em que a solução
inicial do primal é inviável (algumas variáveis xj são negativas),
porém os elementos da funções objetivo são todos não negativos,
indicando otimalidade (solução dual yi é viável)

Simplex/ Dual - Simplex

Enquanto o método Simplex começa com uma solução PRIMAL
básica viável, que não é ótima, e opera na direção da otimalidade
PRIMAL, o método Dual Simplex começa com uma solução PRIMAL
inviável e opera na direção da viabilidade PRIMAL.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 87 / 173
 Interpretação Geométrica

Dual - Simplex
O método dual-simplex é aplicado em situações em que a solução
inicial do primal é inviável (algumas variáveis xj são negativas),
porém os elementos da funções objetivo são todos não negativos,
indicando otimalidade (solução dual yi é viável). A seguir, o método
procura alcançar a viabilidade primal, tornando as variáveis xj não
negativas, mas preservando a viabilidade dual.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 88 / 173
 Interpretação Geométrica

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 89 / 173
 Interpretação Geométrica

Formulação

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 90 / 173
 Interpretação Geométrica

Formulação

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 91 / 173
 Interpretação Geométrica

Hipóteses:

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 92 / 173
 Interpretação Geométrica

Exemplo

O método dual simplex tenta encontrar uma solução viável para o

PRIMAL mantendo a solução do DUAL viável (linha do Z ≥ 0)

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 93 / 173
 Interpretação Geométrica

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 94 / 173
 Interpretação Geométrica

Exercícios

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 95 / 173
 Interpretação Geométrica

Exercícios

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 96 / 173
 Teoria da Dualidade

Dualidade

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 97 / 173
 Teoria da Dualidade

Dualidade

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 98 / 173
 Teoria da Dualidade

Dualidade

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 99 / 173
 Teoria da Dualidade

Dualidade

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 100 / 173
 Teoria da Dualidade

Dualidade

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 101 / 173
 Teoria da Dualidade

Dualidade

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 102 / 173
 Teoria da Dualidade

Dualidade

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 103 / 173
 Teoria da Dualidade

Dualidade

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 104 / 173
 Teoria da Dualidade

Dualidade

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 105 / 173
 Teoria da Dualidade

Dualidade

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 106 / 173
 Teoria da Dualidade

Dualidade

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 107 / 173
 Teoria da Dualidade

Dualidade

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 108 / 173
 Teoria da Dualidade

Dualidade

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 109 / 173
 Teoria da Dualidade

Dualidade

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 110 / 173
 Teoria da Dualidade

Problema de transporte

Introdução
O problema de transportes é um dos casos particulares de
programação linear que, pela sua importância e frequência de
utilização, se impõe ser estudado de forma aprofundada.

Conceito
Um problema de transporte é todo aquele problema onde há a
necessidade de programar a distribuição ótima de um produto
homogéneo, produto esse que está disponível em diversas origens e
será enviado para diversos destinos, esgotando as disponibilidades de
cada origem e satisfazendo as necessidades de cada destino, isto é, a
procura é igual à oferta.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 111 / 173
 Teoria da Dualidade

Situação
Sempre que nos encontramos perante um produto um produto
homogéneo, oferecido por um conjunto de centros de oferta ou
origens e procurado por um outro conjunto de centros de procura
ou destinos, estamos perante um problema de transportes, desde
que:
Se pretenda transportar o produto mencionado, dos centros de
oferta para os centros de procura;
Seja nosso objetivo encontrar a forma mais barata ou mais
rápida de o fazer

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 112 / 173
 Teoria da Dualidade

Exemplo
Uma empresa tem 3 fábricas que produzem um determinado produto.
A capacidade de produção mensal das 3 fábricas é de 6, 1 e 10
unidades respectivamente. A empresa tem 4 armazéns de vendas que
vendem mensalmente 7, 5, 3 e 2 unidades do produto
respectivamente. O custo de transportar 1 unidade de cada fábrica
para cada armazém está dado na tabela abaixo:

O objetivo da Empresa é atender as necessidades dos armazéns com

a produção das fábricas, com o menor custo total.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 113 / 173
 Teoria da Dualidade

Formulação como um modelo clássico de P. Linear

xij ⇒ unidades a serem transportadas da fábrica i para o armazém j.

(MIN) Z = 2x11 + 3x12 + 11x13 + 7x14 + x21 + 6x23 + x24 + 5x31 + 8x

sujeito a:
x11 + x12 + x13 + x14 = 6 (f ábrica 1)
x21 + x22 + x23 + x24 = 1 (f ábrica 2)
x31 + x32 + x33 + x34 = 10 (f ábrica 3)
x11 + x21 + x31 = 7 (armazém 1)
x12 + x22 + x32 = 5 (armazém 2)
x13 + x23 + x33 = 3 (armazém 3)
x14 + x24 + x34 = 2 (armazém 4)

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 114 / 173
 Teoria da Dualidade

Explicação
O sinal de igual das restrições deve-se ao fato de que o somatório da
produção das fábricas é igual ao somatório das necessidades dos
armazéns.
Para problemas com esta estrutura particular, qual seja, coeficientes
das restrições iguais a 0 ou 1, é que podemos utilizar o chamado
Algorítimo dos Transportes.
Ele tem este nome porque os exemplos são, como acima,
normalmente de modelos de transporte mas na verdade, qualquer
modelo de [Link] que tenha este tipo de estrutura, pode ser
resolvido pelo algorítimo.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 115 / 173
 Teoria da Dualidade

Quadro (tableau) usado no algorítimo dos

transportes

Nota
Podemos observar que todo o modelo, ou seja a função objetivo e as
restrições estão “escritas” no quadro.
Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 116 / 173
 Teoria da Dualidade

Fonte ou destino artificial

O algorítimo dos transportes obriga que o somatório das
disponibilidades seja igual ao somatório das necessidades, o que nem
sempre ocorre na prática.
Para exemplificar, vamos supor que a capacidade de produção da
fábrica 3 seja de 20 unidades, em vez de 10.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 117 / 173
 Teoria da Dualidade

Será necessário criar então um destino ARTIFICIAL (destino 5), com

custos de transporte iguais a ZERO (o destino não existe
fisicamente):

Nota
Se o somatório das necessidades for maior que o somatório das
disponibilidades, temos que criar uma fonte artificial.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 118 / 173
 Teoria da Dualidade

Impossibilidade de transporte

Vamos supor que no nosso exemplo exista uma impossibilidade de

transporte entre a fábrica 2 e o armazém 4.
Se esta condição está presente no modelo, precisamos garantir que na
∗
solução final teremos x24 = 0, ou seja, que o valor ótimo de x24 seja
igual a 0.
O objetivo do modelo de transportes é minimizar o custo total.
Assim, se atribuirmos um custo unitário muito alto para a cela (2, 4)
estaremos criando uma penalidade ou multa para o valor de Z se a
variável x24 for diferente de zero, lembrando que ela não pode ser
negativa. Este fato fará com que, naturalmente, o valor de x24 seja
levado para zero na solução ótima.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 119 / 173
 Teoria da Dualidade

Em programação matemática, esta “multa” é chamada de “Big M”

e é representada por um M maiscúlo. Quando resolvemos modelos a
mão, podemos trabalhar com o próprio M mas nos computadores, o
M é substituído por um número muito grande (100000000, por
exemplo).
Etapas do algorítimo dos transportes
As etapas básicas do Algorítimo dos Transportes são:
Obter uma solução básica inicial.
Dada uma solução básica testar se ela é a ótima.
Se não for a ótima, obter a melhor sol. básica adjacente e voltar
a etapa 2.

Como dissemos anteriormente, o Algorítimo dos Transportes nada

mais é do que um simplex feito de uma maneira diferente. Logo, nada
mais natural que os seus passos sejam exatamente os do Simplex.
Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 120 / 173
 Teoria da Dualidade

Número de variáveis básicas nas soluções básicas

O número de variáveis básicas em uma solução básica é igual ao
número de equações linearmente independentes.
Em nosso exemplo, a primeira vista, cada solução básica teria 7
variáveis básicas, ou seja, o número de equações (restrições) do
problema.
Ocorre no entanto que, como o somatório das disponibilidades é igual
ao somatório das necessidades, dadas 6 das equações, a sétima não é
mais independente.
Logo temos na verdade 6 equações independentes.
Genericamente
Se temos m fontes e n destinos, cada solução básica terá (m + n − 1)
variáveis básicas e (m × n) − (m + n − 1) variáveis não básicas.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 121 / 173
 Teoria da Dualidade

Métodos para achar a solução básica inicial

Existem vários métodos para se achar a solução básica inicial no
método dos transportes. Usaremos o chamado Método de
Aproximação de Vogel que é reconhecidamente o melhor deles, ou
seja, aquele cuja solução básica inicial, geralmente, está mais próxima
da solução ótima.
Etapas do Método
Calcule para cada linha e cada coluna a diferença entre os 2
menores custos. No caso dos 2 menores custos serem iguais a
diferença é zero.
Identifique a linha ou coluna com a maior diferença. No caso de
empate a escolha é arbitrária.
Coloque a maior quantidade possível na cela de menor custo da
linha ou coluna identificada na etapa 2.
Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 122 / 173
 Teoria da Dualidade

Continuação
Elimine a linha ou coluna esgotada. No caso em que uma linha e
uma coluna são esgotadas ao mesmo tempo, só podemos
esgotar uma delas ficando a outra com zero, mas não esgotada.
Voltar a etapa 1.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 123 / 173
 Teoria da Dualidade

Regra do Canto Noroeste

A regra será aplicada ao quadro de soluções segundo os seguintes
passos:
Algoritmo
Comece pela célula superior esquerda (ou seja, o “canto
Noroeste” do quadro), associado ao custo c11 ;
Coloque nessa célula a maior quantidade permitida pela oferta
(linha) e demanda (coluna) correspondentes;
Atualize os valores da oferta e da demanda que foram
modicados pelo passo (2);
Siga para a célula à direita se houver alguma oferta restante e
volte ao passo (2); Caso contrário, siga para a célula inferior e
volte ao passo (2).

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 124 / 173
 Teoria da Dualidade

Considere o quadro do exemplo anterior:

Na célula (1, 1) (canto noroeste) atribuímos 7 unidades, que é a

quantidade máxima de demanda do destino 1;
Assim, toda demanda do destino 1 foi atendida e ainda restaram
2 unidades na origem 1.
Devemos, então, seguir para a célula (1, 2) e atribuir-lhe 2
unidades, que é o máximo valor que a origem 1 tem disponível.
Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 125 / 173
 Teoria da Dualidade

O processo se repete até alcançarmos a célula inferior direita do

quadro de soluções;
Assim, encontraremos uma solução inicial factível

No caso, temos
x11 = 7, x12 = 2, x22 = 4, x23 = 6, x33 = 4, x34 = 4 e C = 218

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 126 / 173
 Teoria da Dualidade

Observação
É importante observar que na regra do canto Noroeste a solução
inicial é obtida sem levar em consideração os custos dos transportes
cij , isto é, depende exclusivamente das ofertas das origens e das
demandas dos destinos.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 127 / 173
 Teoria da Dualidade

Processo de Custo Mínimo

Algoritmo
Este processo para fornecer uma solução inicial leva em
consideração, além das ofertas e das demandas, os valores dos
custos
Os seguintes passos devem ser seguidos:
Localize no quadro o menor cij que não tenha oferta ou
demanda nula
Coloque na célula a maior quantidade permitida pela oferta e
demanda correspondente
Atualize os valores da oferta e da demanda que foram
modicadas pelo passo (2) e volte ao passo (1).
O processo se repete até que sejam esgotadas as ofertas e
suprimidas as demandas de todos os destinos

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 128 / 173
 Teoria da Dualidade

No exemplo, o menor cij que aparece é 1, na célula (2, 4).

Logo, nesta célula, atribui-se a quantidade máxima de unidades

permitida, levando em conta a restrição de oferta e demanda;
Insere-se, assim, 4 unidades nesta célula, que é a demanda do
destino 4, e atualiza-se a oferta da origem 2 para 6 unidades
uma vez que 4 foram consumidas.
Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 129 / 173
 Teoria da Dualidade

Eliminando o destino 4 do quadro, o menor custo é igual a 2 e

corresponde à célula (2, 1);
A esta célula, serão atribuídas 6 unidades, esgotando-se a oferta
da origem 2 e diminuindo a demanda do destino 1 para 1
unidade.
Este processo se repete até que todas as ofertas sejam
consumidas e todas as demandas atendidas, quando então
encontramos uma solução inicial factível.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 130 / 173
 Teoria da Dualidade

A solução inicial obtida foi:

x13 = 9, x21 = 6, x24 = 4, x31 = 1, x32 = 6, x33 =
1, e o custo da solução inicial ser á C = 161

Método de Vogel ou Método das penalidades

Penalidade em uma linha ou coluna é a diferença positiva entre os
dois custos de menor valor na linha ou coluna.
A idéia desse método é fazer o transporte com prioridade na linha ou
coluna que apresenta a maior penalidade. Como o transporte é feito
na célula de menor custo, tenta-se evitar com isso o transporte na
célula de custo maior, evitando-se assim incorrer num aumento de
custo igual à penalidade calculada.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 131 / 173
 Teoria da Dualidade

Descrição do método
calcular a penalidade para cada linha ou coluna. Escolher a linha
ou coluna para transporte, que tenha a maior penalidade. Caso
haja empate, escolha arbitrariamente uma delas;
transportar o máximo possível na linha ou coluna escolhida,
elegendo a célula de menor custo unitário de transporte. Esse
procedimento zera a oferta ou demanda da célula
correspondente. Alinha ou coluna que tenha sua disponibilidade
zerada deve ser eliminada;
retornar ao item a, até que todos os transportes tenham sido
realizados.

Nota
Geralmente consegue uma solução inicial melhor que os dois métodos
anteriores

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 132 / 173
 Teoria da Dualidade

Algoritmo

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 133 / 173
 Teoria da Dualidade

Método de Vogel
Explicação
Este método tem em geral melhores resultados do que os dois
métodos anteriores, uma vez que a escolha feita para variável básica,
é em cada quadro o de menor custo da linha ou coluna associada à
maior das diferenças entre os dois menores custos de cada linha e de
cada [Link] aplicação deste método é útil acrescentar uma linha
e uma coluna ao quadro para se escreverem as diferenças entre os
dois menores custos de cada linha e de cada coluna.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 134 / 173
 Teoria da Dualidade

Neste caso há empate em toas as diferenças pelo que arbitrariamente

vou escolher a 2ª coluna, isto é, o 2º destino, e aí, a variável de
menor custo é x22 = min{30, 50} = 30. O 2º destino fica esgotado, e
na origem 2 há ainda 50 − 30 = 20 unidades. Voltam a calcular-se as
diferenças para as linhas e colunas, tendo em atenção as quadrículas
que já estão esgotadas.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 135 / 173
 Teoria da Dualidade

Escolhe-se a maior diferença, e de novo há empate para ambas as

linhas. Arbitrariamente escolhe-se a linha 1 (origem 1), cuja variável
de menor custo é X13 = min{40, 100}40, ficando assim esgotado o 3º
destino.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 136 / 173
 Teoria da Dualidade

Agora vai-se afectar à variável x21 = min{80, 20} = 20, e restam

depois 60 unidades para x11 obrigatoriamente.

Solução
Esta solução, tem custo igual a 520. Note-se que é diferente das
obtidas pelos outros dois métodos mas em termos de custo é
exactamente igual.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 137 / 173
 Teoria da Dualidade

Problema do Dual
Característica
Todo o problema de programação linear possui um problema
dual correspondente.
Chamaremos o problema original de “primal” e o problema dual
de “dual”.

Primal Dual
Max Min
Min Max

Descrição
Variáveis do problema primal → z, x1 , x2 , . . . , xn
Variáveis do problema dual → w , y1 , y2 , . . . , yn
Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 138 / 173
 Teoria da Dualidade

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 139 / 173
 Teoria da Dualidade

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 140 / 173
 Teoria da Dualidade

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 141 / 173
 Teoria da Dualidade

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 142 / 173
 Teoria da Dualidade

Significado
O significado económico das variáveis duais é o seguinte:
ui é o preço na origem i (armazém, fábrica) do produto;
vj é o valor do produto no destino j (ponto de demanda)
Restrições do tipo: −ui + vj ≤ cij , significam que o preço de destino
(vj ) do produto menos o preço na origem (ui ) desse produto poderá
ser, no máximo, igual ao custo de transporte da origem i até o
destino correspondente j. Portanto, o transporte não pode dar
origem a ganhos de capital injustificados. Os preços/custos ui , vj ,
são conhecidos por serem preços sombra ou preços fictícios e
representar preços teóricos.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 143 / 173
 Teoria da Dualidade

Interpretação
O significado destes preços é que eles indicam vantagens relativas de
localização do centros de produção (origens) ou centros de consumo
(destinos), devido à proximidade de centros de consumo ou existência
de melhores meios de transporte.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 144 / 173
 Teste de Otimalidade

Obtenção da solução ótima

Obtida uma SBA inicial, esta é submetida ao teste de óptimo,

passando-se em seguida a outra solução caso o critério respectivo não
seja satisfeito; o processo repete-se até obtenção da solução óptima.

O método que vamos aprender é baseado na solução dual, e foi

desenvolvido por Dantzig. Os resultados da dualidade vão servir para
calcular os custos reduzidos (zij − cij ) do problema primal de
transporte. A análise destes valores permite concluir se a SBA
(solução básica admissível) que temos é óptima ou não.

A primeira coisa a fazer, é determinar a solução dual (u, v ) para as

variáveisbásicas tais que ui + vj − cij = 0 ou seja, tal que ui + vj = cij .

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 145 / 173
 Teste de Otimalidade

Solução
Degenerada
Para um problema de transportes equilibrado com m origens e n
destinos, uma solução com menos de m + n − 1 variáveis maiores que
zero é degenerada.

A degeneração ocorre nos seguintes casos:

Casos:
No cálculo de uma solução básica viável inicial: quando as
simultâneas são satisfeitas ordenadamente origem e destino em
uma etapa que não é a última do método Vogel ou o método do
canto noroeste.
Em qualquer iteração do algoritmo de transporte, quando há
empate no critério da variável que sai da base.
Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 146 / 173
 Teste de Otimalidade

Solução

Múltiplas
Uma vez obtida a solução ótima, novas soluções ótimas podem ser
encontradas, se houver algum indicador de um vetor não básico que
vale zero.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 147 / 173
 Teste de Otimalidade

Soluções Degeneradas
Como anteriormente mencionado, ficámos a saber que uma solução
degenerada traduz uma situação especial em que uma das variáveis
básicas assume o valor zero.

Soluções Múltiplas
Quando, numa determinada solução, existe uma ligação não utilizada
que apresenta um custo reduzido nulo, isso significa que esta ligação
poderá passar a ser utilizada, não havendo com isso qualquer
alteração do valor de função objetivo, ou seja, dos custos totais de
transporte. assim, podemos identificar pelo menos duas soluções
(uma com essa ligação utilizada e outra com essa ligação por utilizar)
que apresentam os mesmos custos totais de transportes.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 148 / 173
 Análise de Sensibilidade

Análise de Sensibilidade

Iremos focar naquilo a que normalmente se chama análise

pós-optimal ou análise de sensibilidade. Tal como nos problemas
gerais de Programação Linear, este tipo de análise é de extrema
importância em transportes pois também aqui é muito útil saber
quais as consequências de alterações à situação original, das
necessidades dos destinos ou mesmo dos custos de transportes.
Contextualizando
Todo gestor deverá equacionar, na sua planificação, possíveis
alterações à estrutura do problema para o qual obteve a solução
óptima.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 149 / 173
 Análise de Sensibilidade

Perguntas
Que fazer se uma ligação não utilizada ficar mais barata?
Que fazer se a procura de um determinado armazém ou destino
aumentar?
Que fazer se a oferta de um dos depósitos ou fabrica se alterar?
Para dar resposta a este tipo de questões podíamos introduzir na
formulação inicial do problema restrições do tipo "e se"e resolvê-lo
para encontrar a solução óptima. Mas na prática isto nem sempre é a
melhor opção pois a maioria dos problemas reais envolvem muitas
variáveis e são bastante complexos pelo que a inclusão de restrições
do tipo "e se"pode trazer dificuldades de resolução.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 150 / 173
 Análise de Sensibilidade

A análise de sensibilidade procura, assim, complementar a resolução

de problema de transportes, de duas formas distintas. Por um lado,
evita a reformulação do problema original, tentando dar resposta a
alteração ocorridas após definição do problema, a partir do quadro
final de resolução. Por outro lado, permite determinar os intervalos
de sensibilidade dos parâmetros originais do problema. Estes
intervalos de sensibilidade não são mais do que os limites da variação
dos dados originais do problema, entre os quais o quadro óptimo de
resolução apresenta as mesmas variáveis básicas.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 151 / 173
 Análise de Sensibilidade

Alterações nos Coeficientes da função objetivo

Vejamos o que acontece se houver alteração nos coeficientes da
função objetivo, ou seja, nos custos de transportes. Pois, é razoável
supor que estes custos estão sujeitos a incertezas e mudanças -
incertezas porque, no mundo da gestão, poucas são as coisas
passíveis de serem quantificáveis com precisão; mudanças porque o
ambiente ou o mundo dos negócios não é estável.

Alteração no coeficiente de uma variável não básica

Em quanto é que o custo de uma ligação deveria reduzir para que
esta passasse a ser utilizada na solução?
Resposta: Tem-se assim que enquanto o custo reduzido for maior
ou igual a zero, Cij0 − ui − vj > 0, a variável permanecerá não básica,
pois o custo unitário de transporte é superior ao benefício que esse
transporte proporcionará.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 152 / 173
 Análise de Sensibilidade

Alteração no coeficiente de uma variável básica

Neste caso, a análise de sensibilidade não é tão simples como no caso
anterior porque uma alteração nos coeficientes das variáveis básicas
na função objetivo provoca alterações nos valores das variáveis duais
correspondestes no quadro final. Isso faz com que tenhamos de
recalcular novos valores para os custos reduzidos das variáveis não
básicas afetadas pela alteração do custo unitário de transporte.

Ate quanto é que o custo de uma ligação deve aumentar sem que
esta deixe de ser utilizada?

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 153 / 173
 Problema de Afetação

Problema de Afetação
O problema da afetação é um tipo especial de problema de
programação linear em que os afetados estão sendo indicados para a
realização de tarefas. Por exemplo, os afetados poderiam ser
empregados que precisem receber designações de trabalho.
Afetar pessoas para determinadas tarefas é uma aplicação comum do
problema da afetação. Entretanto, os afetados não precisam ser
necessariamente pessoas.
Eles também podem ser máquinas, veículos ou fábricas, ou até
mesmo períodos a serem destinados a tarefas.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 154 / 173
 Problema de Afetação

Para adequar a definição do problema da designação, esses tipos de

aplicações precisam ser formulados de maneira que satisfaça as
seguintes hipóteses.
Hipóteses
O número de designados e o número de tarefas é o mesmo. Esse
número é representado por n.
Deve-se atribuir a cada designado exatamente uma tarefa.
Cada tarefa deve ser realizada exatamente por um designado.
Há um custo associado ao designado i(i = 1, 2, ..., n)
executando a tarefa (j = 1, 2, ..., n).
O objetivo é determinar como todas as n designações devem ser
feitas para minimizar o custo total.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 155 / 173
 Problema de Afetação

Qualquer problema que satisfaça todas essas hipóteses pode ser

resolvido de forma extremamente eficiente por algoritmos desenhados
especificamente para problemas da designação. As três primeiras
hipóteses são bastante restritivas. Diversas aplicações potenciais não
satisfazem completamente essas hipóteses. Porém, formalmente é
possível reformular o problema para que ele passe a satisfazê-las. Por
exemplo, designados "fantasmas"ou tarefas
"fantasmas"frequentemente podem ser usados para esse propósito.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 156 / 173
 Problema de Afetação

O modelo matemático para o problema da designação usa as

seguintes variáveis de decisão:
Modelo para o Problema de Designação
X X
min cij xij
i∈n j∈m

sujeito a:
X
xij = 1, ∀i ∈ n,
j∈m
X
xij = 1, ∀j ∈ m,
i∈n

(xij ∈ {0, 1}), ∀i ∈ n, ∀j ∈ m.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 157 / 173
 Problema de Afetação

Descrição
O primeiro conjunto de restrições funcionais especifica que cada
designado deve realizar exatamente uma tarefa, ao passo que o
segundo conjunto requer que cada tarefa seja realizada exatamente
por um designado. Se eliminarmos a restrição entre parênteses para
que xij seja binário, o modelo claramente é um tipo especial de
problema de programação linear e, portanto, pode ser resolvido
prontamente. Felizmente, por razões ainda a ser desvendadas,
podemos eliminar essa restrição.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 158 / 173
 Problema de Afetação

o problema da designação é simplesmente um tipo especial de

problema de transporte em que as origens agora são os designados e
os destinos agora são as tarefas e nos quais o:
Número de origens m = número de destinos n
Toda oferta si = 1
Toda demanda dj = 1

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 159 / 173
 Problema de Afetação

Pelo fato de si e dj serem agora inteiros(= 1), essa propriedade

implica que toda solução BV (inclusive uma ótima) é uma solução
inteira para um problema da designação. As restrições funcionais do
modelo do problema da designação impede que qualquer variável seja
maior que 1 e as restrições de não-negatividade impedem valores
menores que O. Portanto, eliminar a restrição binária para nos
permitir resolver um problema de designação como se fosse um
problema de programação linear fará que as soluções BV resultantes
(incluindo a solução ótima final) obtidas automaticamente
satisfaçam, de qualquer modo, a restrição binária.

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 160 / 173
 Problema de Afetação

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 161 / 173
 Problema de Afetação

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 162 / 173
 Problema de Afetação

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 163 / 173
 Problema de Afetação

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 164 / 173
 Problema de Afetação

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 165 / 173
 Problema de Afetação

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 166 / 173
 Problema de Afetação

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 167 / 173
 Problema de Afetação

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 168 / 173
 Problema de Afetação

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 169 / 173
 Problema de Afetação

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 170 / 173
 Problema de Afetação

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 171 / 173
 Problema de Afetação

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 172 / 173
 Problema de Afetação

Prof. Msc. Ailton Arminda (USTP - FCT) Programação Linear 1 de maio de 2024 173 / 173