Exercícios de Método Simplex com Respostas

Prévia do material em texto

Caṕ ı t u l o 2
 E x e r ćı ci os de M éto do Simplex
Enunciados
 
 
E x e rćı c i o s d e Mé t od o Si m p l e x
 Enun ciados 28
 Problema 1
m a x F = 10x1 + 7x2
s u j . a :
2x1 + x2 ≤ 5000
4x1 + 5x2 ≤ 15000
x1 , x2 ≥ 0
 Problema 2
m a x F = 2x x1 + 2
s u j . a :
x1 + x2 ≥ 2
x1 + x2 ≤ 4
x1 , x2 ≥ 0
 Problema 3
m a x F = x1 + 2x2
s u j . a :
−4x1 + x2 ≤ 4
2x1 − 3 6x2 ≤
x1 , x2 ≥ 0
 Problema 4
m i n z = x x x1 + 2 + 3
s u j . a :
−x1 + x2 ≥ 1
2x1 − 2x x2 − 3 = 2
x1 , x2 , x3 ≥ 0
 Problema 5
m ax F = x + 2y + 3z
s u j . a :
x − y ≥ 0
y + z ≤ 2
−x + z = 0
x ∈ 
y , z ≥ 0
 
 
Caṕ ı t u l o 2
 E x e r ćı ci os de M éto do Simplex
Resoluções
 
 
E x e rćı c i o s d e Mé t od o Si m p l e x
Re s o l u ç ões 30
 Problema 1
m a x F = 10x1 + 7x2
s u j . a :
2x1 + x2 ≤ 5000
4x1 + 5x2 ≤ 15000
x1 , x2 ≥ 0
 O p r o b l e ma p r o p o s t o é um p r ob lem a d e p r ogr am a ção lin ear: a fun ção ob j ectivo e as
 r e s t r ições s ão f u n ç ões lineares das vari áveis d e decis ão x1 e x2. Es te e x empl o si mple s ser á
 usad o para ilus trar a aplicaç ão do méto d o Simplex para resolver p roblemas de programaç ão
 linear. Emb ora a resolu ção pr ática de pr oblemas d este tip o seja (semp re) feita r ecorr endo
 a pr ogr am as de com p u tad or que p erm item obter a soluç ão d e pr oblemas com milhar es
 d e r e s t r ições e vari áveis, é conven iente a compreens ã o d o f u n c i on a m e nt o d a técnica p ara
 facilitar a interpr etaç ão d os r e s u l t ad o s o b t i d os .
 Par a se aplicar o méto do Simplex, é n ecess ário q ue o p rob lema satisf aça os requisitos
 seguintes (forma standard) :
 ( a ) To d a s a s va r i áveis são n ão negativas (s ó p od em assum ir valores p ositivos ou nulos);
 ( b ) To d a s a s r e s t r i ções são equ aç ões (ou r estri çõ es d o ti p o ’ = ’ );
 ( c ) To d o s o s t e r m o s in d e p e n d e nt e s sã o p o sit ivo s.
 No nosso exemp lo, a pr imeira e ú l t i m a co n d iç ão s ã o s at i s f e i t as . Pa r a r e p r e s e nt a r o
 p r o b l em a n a f o r m a s t a n d a r d é n eces s ário trans for m ar as duas i n equ aç ões em equaç ões.
 Pa r a i s s o , sã o i nt r o d u z i d a s n o p r i m e i r o m e mb r o d a s i n e q u ações n ovas vari áveis (também
 não n egativas) com co eficiente +1. E stas vari áveis repr esentam a “folga”entr e o pr imeiro e
 o s e g u n d o m e mb r o d a s i n eq u a ções, ch amand o-se p or isso vari áveis de folga e rep resentando-
 s e p o r s (de slack).
m a x F = 10x1 + 7x2
s u j . a :
2x1 + x2 + s1 = 5000
4x1 + 5x2 + s2 = 15000
x1 , x2 , s1 , s2 ≥ 0
 A aplicaç ão do m étod o Simp lex requer o conh ecimento de uma soluç ão b ásica ad-
 m i s ś ıvel in icial, que servir á de p onto de partid a para o p ro cesso iterativo. Em problemas
 q u e a p e n as c on te n h a m r e s tr i ções d o tip o ≤, a i nt r o d u ção d as vari á ve i s d e f o l g a c o n d u z
 a uma solu ç ão b ásica admisśıvel inicial imed iata: fazem-se nulas as vari áveis or iginais
 d o p r o b l e m a (n o n o s s o e x e m p l o x1 e x2), e as var iáveis de folga ficam iguais aos term os
 i n d e p e n d e nt e s d a s eq u aç ões resp ectivas:
(x1, x2, s1, s2) = (0, , ,0 5000 15000)
 Note-se que esta solu ç ão in icial corr esp onde à o ri ge m d a r eg i ão de s oluç ões admisś ıveis,
 o q ue é s e m p r e ve r d a d e s e t o d a s a s r e s t r iç ões de um pr oblem a forem do tip o ≤ com ter-
 m o s i n d e p e n d e nt e s p o s i t iv os . N e s t e c a s o a o r i g em é u m a s o l uç ão b ásica admisśıvel obtida
 imediatam ente com a intro du ção das vari áveis de folga em to das as r estriç ões. O m éto do
 S i m p l ex p o d e s e r a p l i ca d o m a nu a l m e nt e r e c o r r en d o a u m q u a d r o o n d e s e r ep r e s e nt a m d e
 
 
E x e rć ı c i o s d e Mé t od o S i m p l e x
Re s o l u ç ões 31
 form a cond en s ad a to d os os par â m et r o s d o p r o b l e m a (m a t r i z d o s c o e fi c i en te s , t er m o s i n d e -
 p e n d e nt e s e f u n ção ob jectivo). S ob re esse quadr o s ão ap licad as tran s for m aç ões algébr icas
 d e a c or d o c o m d e t e r m in a d a s r e g r a s , q u e c o n d u ze m à o bt en ção d a soluç ão óptim a.
 va r i áveis básicas x x1 2 s s1 2 t e r m o s i n d e p e n d e nt e s
↓ ↓
s1 2 1 1 0 5000
s2 4 5 0 1 15000
 −F 10 7 0 0 0
 ↑
 custos mar ginais simétrico do valor
 d a f u nç ão ob jectivo
 Uma iteração consiste em tro car uma var iá ve l d a b a s e : d a s va r iáveis n ão básicas
 escolhe-se u ma par a entrar par a a bas e (ir á pas sa r de zer o a u m valo r p osi tivo-e ventua lm ente
 nu l o ) , e d a s va r i áveis b ás icas é seleccion ada uma para sair da b ase. Esta op eraç ã o c or r e s -
 p onde a “saltar ”para um a soluç ão básica adm isśıvel vizinha (ou ad jacente). Matematica-
 m e nt e f a l an d o , d u a s s o l uções adjacentes sã o a q u e la s q u e d if e r e m d e a p e n a s u m a va r iável
 básica; geometr icamente s ão dois “cantos”da r egião de solu ções ad misś ıveis qu e est ã o u n i-
 d o s p o r u m “ la d o ” d o p o l i ed r o q u e r e p r e s en t a n o es p aço es sa regi ão. As s oluç ões bás icas
 d e u m p r o b l e m a co r r e s p o n d e m a t o d a s a s i nt e r s e cç õ es e nt r e a s r e s t r iç õe s , c o n s i d e r an d o
 tamb é m a s r e s tr i ç ões xi ≥ 0. De entr e estas, s ão admis ś ıveis aquelas qu e são r ep r esentadas
 ap enas p or var iáveis não negativas:
 includ egraph ics[scale=0.8]simplex/simp lex1
 va r i áveis básicas x x1 2 s s1 2 t e r m o s i n d e p e n d e nt e s
↓ ↓
s1 2 1 1 0 5000 
5000 
2
(menor quo ciente)
s2 4 5 0 1 15000 
15000
4
 −F 10 7 0 0 0
 ↑
 custos mar ginais o ma is simétr ico d o valor
 p ositivo d a f u n ç ão ob jectivo
• C r i tério de entrada na base:
 E nt r a n a ba s e a var i ável qu e tiver um co efi ciente mais p ositivo na linha F . E s t es
 co eficientes ( custos m arginais ) rep resentam o p eso relativo das vari áveis n ão b ásicas
 (neste caso x1 e x2) , n o va l or d a f u nç ão ob jectivo. Pod emos dizer assim que, entrand o
 a vari ável x1 p ar a a bas e, o valor de F c r e sc e 1 0 u n i d a d es p o r u n i d a d e d e c re s c i m e nt o
 x1. N o t e - s e q u e i s t o a p e n a s é ve r d a d e s e n a li n h a F existirem co eficientes nulos sob
 as var i áveis b ásicas (p orqu ê?). Na realidad e, a lin ha de F é c o n s i d e r ad a c o m o s e n d o
 u m a e q u ação adicional, on de F r epresenta um a var iá ve l q u e n u n ca s a i d a b a s e :
F = 10x1 + 7x2
 p o de ser rep r esentada como a eq u aç ão seguinte:
−F + 10x1 + 7x2 + 0s1 + 0s2 = 0
 
 
E x e rć ı c i o s d e Mé t od o S i m p l e x
Re s o l u ç ões 32
 Escrito d esta for ma, F aparece com o co efi ciente -1; dáı a r az ão de o valor que
 aparece no 2o m e mb r o d a l i n h a F ser igual ao s im é tr i c o d o va l or d a f u n ção ob jectivo.
 S e n d o i nt e r p r e t ad a c o m o u m a e q u ação, p o demos sempre eliminar vari á ve i s ( u s an d o
 op eraç ões de pivotagem aprop r iad as) p or f orm a a que os co efi cientesde F s o b a s
 va r i áveis básicas s ejam sempre nulos.
 Pa r a u m p r o b l e m a d e m i n i m iz a ção o critério de entrada na base ser á obv i a m e nt e o
 contrá r i o : e nt r a n a b a s e a va r iável não b ásica que pr ovo ca um maior decrescimento
 n o va l o r d e F , ou sej a, a que tiver um co eficiente mais negativo na linh a F .
• C r i tério de sáı d a d a b as e :
 S a i d a b a s e a va r iável xk (b ásica na equaç ão i) q u e t iv er u m c o e fi c ie nt e
bi
aij 
m e n o r
 ( s en d o xj a var i ável que entrou para a base).
 A s d u a s e q u ações rep resentadas n o q uadro acima p o dem -se escr ever (x2 = 0 , n ão
básica):
2x1 + s1 = 5000
4x1 + s2 = 15000
ou:
 s1 = 5000 − 2x1
 s2 = 15000 − 4x1
 E nt r a n d o x1 p a r a a b a s e , i s s o s i g n i fi c a q u e x1 vai p as s ar d e zero para um valor p os i-
 tivo. A vari ável a sair d a base vai ser aqu ela qu e pr imeiro s e anular, lim itando ass im
 o cresci mento d e x1 (note-s e que to das as var iáveis envolv idas s ó p o d e m a s s u m i r
 valor es p ositivos ou nulos).
 Pe l a 1 a equação, x1 p o d e s u b i r a té
5000 
2
= 2500 para s1 s e anular (sair d a bas e); p ela
 s e g u n d a eq u a ção, o valor m áx imo p ara x1 é 
15000 
4
= 3750. Logo, a var iável a sair
 d a b a s e s e rá s1, p o i s q u an d o x1 cresce é s1 q u e p r i me i r o s e a nu l a , i m p o n d o as s im o
 limite n o crescim ento da vari ável x1 em 2500. Com o regr a pr ática, b asta calcular os
 quo cientes entre os termos indep endentes e os coefi cientes da matriz sob a var iável
 q u e va i e nt r a r p a r a a b as e , r e t i r a n d o d a b a s e a va r iável bá s ic a d a e q u aç ão qu e tiver
 o menor quo ciente.
 Analisemos com mais detalh e a 1a equaç ão acima:
 5000 (termo ind ep en d ente) é o valor que a vari ável b ásica s1 tomava na iter aç ão
anterior.
 2 (co eficiente da matriz sob x1) é o simétr ico d o p es o da var i ável x1 n e s s a e q u aç ão.
 Po r o u tr a s p a l av r a s , p o d e m o s d i z e r q u e s1 d e c r e sc e 2 u n i d a d e s p o r u n i d a d e d e
 crescimento d e x1, a nu l a n d o- s e ( i . e. s a i n d o d a b a s e ) q u a n d o x1 atinge 
5000
2
.
 Po d e m a s s i m se r t i r a d as a l g u m a s co n c l u sões i nteressantes, em f u n ç ão do valor d os
 co eficientes d a matriz, aik , sob a vari ável que foi escolhida p ara entrar par a a bas e,
xk :
 aik > 0 xbi , a vari ável b ásica na equ a ção i, decr esce aik u n i d a d e s p o r u n i d a d e d e
 crescimento de xk , imp ond o assim um limite sup er ior a xk igu al a
bi
aik 
(bi é
 o t e r m o in d e p e n d e nt e d a e q u ação i).
 
 
E x e rć ı c i o s d e Mé t od o S i m p l e x
Re s o l u ç ões 33
 a xik = 0 bi , a variável b ásic a na e qu aç ão i, não vê alter ado o s eu valor, q uand o xk
 entr a par a a base. Iss o signifi ca que xbi n u n c a sa i rá d a ba se p o is não limita
 de forma algu ma o crescimento d e xk .
 aik < 0 xbi , a var iável básica n a equaç ão i, cr e s ce aik u n i d a d e s p o r u n i d a d e d e c r e s -
 cimento de xk . A s s i m , d o m e s m o m o d o q u e p a r a o c a s o a nt e r i o r , xbi n ão
 limita o cr escimento d e xk , logo nunca sair á da ba se .
va r i áveis básicas x x x b1 · · · k · · · m
↓
 x a bb1 · · · · · · 1k · · · · · · 1
...
...
...
...
...
...
...
 x a bbi · · · · · · ik · · · · · · i
...
...
...
...
...
...
...
 xbn · · · · · · an k · · · · · · bn
 − −F · · · · · · fk · · · · · · F0
 C o m b a s e n o q u e s e d i s s e , p o d e m o s c o n c l u ir o s e g u in t e: s e t o d o s o s c o e fi c ie n te s
 d a va r iável que s e escolheu p ara entrar par a a b ase for em negativos ou nulos, is so
 signifi ca qu e n enhuma das vari áveis básicas decresce com o cr escimento d a nova
 va r i á ve l c a n d i d a ta a básica. Assim, se esta variável p o de crescer sem que qu alquer
 d a s básicas s e anule, entã o p o d e - s e c on c l u i r q u e o p r o b l e m a não tem u ma solu ção
 óptim a limitada. S ituaç ões destas o cor rem qu and o a região de soluç ões admisś ıveis
 é um d om ı́nio ab erto n o sentid o d e crescimento d a fun ç ão ob jectivo.
 C o nt i nu a n d o c o m a r e s o l ução do exemplo dad o:
b a s e x x b1 2 s s1 2
x1 1
1
2
1
2
0 2500 25001
2
= 5000
 s2 0 3 − 2 1 5000 
5000
3
= 1666.7
−F 0 2 − −5 0 25000
b a s e x x b1 2 s s1 2
x1 1 0 
5
6
−1
6
5000
3
x2 0 1 
−2
3
1
3
5000
3
−F 0 0 −11
3
−2
3
−85000
3
Soluçã o óptima encontrada:
 Nã o e x i s te n e n h u m a va r iável n ão b ásica (s1 ou s2, n este caso) que tenh a um co eficiente
 p o s i ti vo n a l in h a F . S e u m a d e s s a s va r iáveis tivess e um coefi ciente nulo, is so significava
 que ela p o der ia entr ar par a a base s em alterar o valor da f unç ão ob jectivo F ( ch a m a m -
 s e a e s t a s s o l uç õe s al te rn a ti vas à solu ção óptima en contr ada). Note-se que as s oluç ões
 alternativas assim ob tidas s ão igualmente óp timas, j á q ue mantêm o m esmo valor p ara a
 f u nç ão ob jectivo F .
 O valor d a soluç ão óp tima par a este prob lema ser ia F = 85000 
3
e os valores d as vari áveis
d e d e c is ão seriam:
x1 =
5000
3
, x2 =
5000
3
 
 
E x e rć ı c i o s d e Mé t od o S i m p l e x
Re s o l u ç ões 34
Problema 2
m a x F = 2x x1 + 2
s u j . a :
x1 + x2 ≥ 2
x1 + x2 ≤ 4
x1 , x2 ≥ 0
 Em p rimeir o lugar é necess á r i o r e p r e s e nt a r o p r o b le m a n a f o r m a s t an d a r d , i n tr o d u z i n d o
 va r i áveis d e folga p ar a trans for m ar as i n equ aç ões em equ aç ões. A vari ável d e folga d a
 p r i m e i r a r es t r i ção tem co eficiente -1 p or que a inequa ção é d o tip o ≥ (n ote-se q ue to das as
 va r i áveis sã o p osit i va s) .
m a x F = 2x1 + x2
s u j . a :
x1 + x2 − s1 = 2
x1 + x2 + + s2 = 4
x1 , x2 , s1 , s2 ≥ 0
 Neste caso já n ão se ob tém a s oluç ão bás ica inicial fazend o as var i áveis d e folga igu ais
 a o s t e r m o s i n d e p e n d e nt e s . A p e s a r d e s s a s e r u m a s o l uç ão b ásica, n ão é adm is śıvel e como
 tal n ã o p o d e s e r u s a d a c o m o p o n to d e p a r t i d a p a r a o méto do Simplex.
 S e rão ap r es entados dois m étod os par a resolver esta quest ão, que p ermitem usar o
 p rópr io Simp lex par a encontrar u ma solu ção básica admisś ıvel in icial. O s méto dos são:
 • mé t o d o d a s d u a s f a s e s
 • mé t o d o d a s p e n a l i d a d e s
 A nt e s d e a p l i ca r q u al q u e r u m d o s méto d os, é no entanto necess ário acrescentar vari áveis
 ( ch a m a d a s va r i á v e i s a r t i fi c i a i s) n a s r e s t r iç õ es q u e n ão têm var iáveis b ásicas.
 I nt r o d u z i n d o u m a va r iável artifi cial na 1a equaç ão:
x1 + +x2 − s1 a1 = 2
x1 + x2 + + s2 = 4
x1 , x2 , s1 , s2 , a1 ≥ 0
 Seguid am ente, amb os os m éto d os u sam o mé t o d o S i m p l e x p a r a an u la r ( r e ti r a r d a b a s e )
 essas variáveis artifi ciais. Qu and o isso acontece, a solu ç ão q u e ent ão se tem é u ma sol uç ão
 básica admisś ıvel d o pr oblema or iginal, qu e é u s a d a c o m o s o l uç ão de p artida p ara aplicar
 o méto do S implex.
 Descriç ãos ucinta dos dois m étod os:
 Mé t o d o d a s d u a s f a s e s
 1a f a s e m i n i m i z a r a f u nç ão ob jectivo artificial W =

ai; o ob jectivo d esta p rimeir a fase
 é re tir ar t o d as a s va ri áveis artifi ciais da base, s ituaç ão em que W atin ge o valor
 mı́nim o de zer o. A solu ç ão b ásica admisśıvel assim ob tida é u ma sol u ção b ásica
 admis ś ıvel inicial para s e aplicar o méto d o Sim plex ao prob lema original.
 
 
E x e rć ı c i o s d e Mé t od o S i m p l e x
Re s o l u ç ões 35
 
2a f a s e U s a n d o
 
c o m o
 
s o l uç ão b ásica
 
inicial a
 
ob tida
 
n a
 
pr imeira
 
fase,
 
r esolver o
 
problema
 
n o r m a lm e n te u s a n d o
 
o
 
a lg o r i t m o
 
d o
 
s i m p l e x ,
 
d e p o i s
 
d e
 
e l i m in a r d o q u a d r o
 
a
 
l i n h a
 
c o r r es p
 
o n d e nt e à
 
f u nç ão ob
 
j ectivo ar tificial W ,
 
e
 
as colun as
 
relativas às
 
var iáveis
artificiais,
 
ai.
 
Mé t o
 
d o d a s p
 
e n a l i d a d e s
 
A
 
f u nç ão ob
 
j ectivo max F = 2x1 + x2 é
 
sub stitú ı d a p e l a f u nç ão ob
 
jectivo max F =
 2x1+x2−M

ai , o n d e M tem u m valor muito elevado. Dad o q ue se trata de um p robl ema
 d e m a x i m i za ç ão , a m e l h or i a d a f u n ção ob j ectivo implica que as vari áveis artificiais passem
 a valer zero (s ejam retir adas d a base). A soluç ão b ásica assim obtid a é u m a so l uç ão b ásica
admis ś ı ve l p a r a o p r o b le m a o r i gi n a l .
 Aplicand o o M é t o d o d a s d u a s f a s e s ao exemp lo apres entado:
1a fase:
 Pretend e-se minimizar W =

ai = a1. C omo nos interessa expr imir o W ap enas em
 f u nç ão de var i áveis n ão b ásicas (p orqu ê?), vamos s ubs tituir cada vari ável artifi cial p ela
 express ão qu e a repres enta ap enas em fu nç ão de vari áveis n ão b ásicas.
 Da 1a equaçã o ( o n d e a1 é variável b ásica e as outras vari áveis s ão n ão b ásicas):
x1 + x a2 − s1 + 1 = 2
 p o de-se es creve r a1 e m f u nç ão d e vari áveis n ão b ásicas:
a1 = 2 − −x1 x2 + s1
 A s s i m , a f u n ção ob jectivo artificial a m inimizar ser á:
W = a1 = 2 − −x1 x2 + s1
 O p r i m e i r o q u a d r o S im p l e x e s tá r e p r e s en ta d o a s e g u i r . D a d o q u e s e p r e t e n d e m in i m i z a r
 W , teremos que es colh er para entrar n a b ase a var i ável com co eficiente mais negativo na
 l i n h a W . Dado que as var i áveis x1 e x2 têm o mesmo co eficiente (-1), p o demos escolher
 u m a d a s d u as va r iáveis para entrar na b as e.
b a s e x x a b1 2 s s1 2 1
 a1 1 1 −1 0 1 2
2
1
s2 1 1 0 1 0 4
4
1
−F 2 1 0 0 0 0
 − − −W 1 1 1 0 0 −2 (s i métrico de W)
b a s e x x a b1 2 s s1 2 1
x1 1 1 −1 0 1 2
s2 0 0 1 1 −1 2
− −F 0 1 2 0 − −2 4
−W 0 0 0 0 1 0
 O q u ad r o a p r es e nt a d o c o r r es p o n d e a o fi m d a 1 a f a s e d o méto d o das duas f as es, dado
 q u e a f u n ção ob jectivo W foi minim izada até zer o (a1 = 0 ). A s ol u ç ão básica adm isśıvel
 a s s i m o b t i d a é um a solu ção básica admisś ıvel in icial p ara se ap licar o m éto do Simp lex ao
 prob lema origin al.
2a fase:
 
 
E x e rć ı c i o s d e Mé t od o S i m p l e x
Re s o l u ç ões 36
 Nesta fas e preten de-se m aximizar a funç ão ob jectivo in icial, F , toman d o com o quadr o
 d e p a r t id a o ú l ti m o q u a d r o d a 1 a fase, dep ois de eliminar a linha corresp ondente a W e
 as colun as relativas às var iáveis artificiais.
b a s e x x b1 2 s s1 2
x1 1 1 −1 0 2
 s2 0 0 1 1 2
− −F 0 1 2 0 −4
 Note-se q ue x1 nu n c a p o d e r i a s ai r d a b a s e ! E nt r a n d o s1 pa ra a b as e, x1 cr esce 1
 u n i d a d e p o r u n i d a d e d e c r e s c im e nt o d e s1, logo nunca se iria anular (e cons equ entemente
 s a i r d a b a s e ) . s2 sai da b ase limitando o crescimento de s1 em 
2
1
= 2.
b a s e x x b1 2 s s1 2
x1 1 1 0 1 4
s1 0 0 1 1 2
− −F 0 1 0 − −2 8
 Nã o e x i s t e n e n hu m a va r iável n ão b ásica (x2 ou s2, n este caso) qu e tenh a um co efi ciente
 p o s i ti vo n a l i n h a F . O val or da so lu ção óptima p ara este p roblem a ser ia F = 8 e os valor es
 d a s va r iáveis d e decis ão seriam :
x1 = 4, x2 = 0, s1 = 2, s2 = 0
 Aplicand o o M é t o d o d a s p e n a l i d a d e s ao exemplo ap resentado:
 Como n os inter essa exprimir F ap enas em funç ão de vari áveis n ão b ásicas (por quê?),
 va m o s s u b s t i tu i r c a d a va r iável ar tificial p ela ex press ão que a representa ap enas em funç ão
 d e va r iáveis n ão b ásicas.
 Da 1a equaçã o ( o n d e a1 é variável b ásica e as outras vari áveis s ão n ão b ásicas):
x1 + x a2 − s1 + 1 = 2
 p o de-se es creve r a1 e m f u nç ão d e vari áveis n ão b ásicas:
a1 = 2 − −x1 x2 + s1
 A s s i m , a f u n ção ob jectivo a maximizar ser á:
F = 2x1 + x2 −Ma1
= 2x x x x1 + 2 −M ( 2 − 1 − 2 + s1)
= −2M + (2 + M )x1 + (1 + M )x2 −Ms1
 E o qu adr o segu inte é o p r i m e i r o q u a d r o s i m p l ex .
 N o t a: A l i n h a d os c u s t o s m ar g i n a i s es tá divid ida em du as com a ú n i c a fi n al i d a d e d e
 simplificar os cálculos. A s oma das d uas linhas é q u e r e p r es e nt a o c u s t o m ar g i n a l (p . e x . :