Metode Simplex

Agus Yodi Gunawan

October 16, 2014

Pada bagian ini akan diberikan penjelasan mengenai metode dasar yang biasa digunakan
untuk menyelesaikan program linear, yaitu Metode Simplex.
Sumber rujukan: M.S. Bazaraa, J.J. Jarvis, dan H.D. Sherali, ”Linear Programming and Network Flows”, John Wiley

& Sons, 1990.

1. Program linear di ruang variabel nonbasis. Perhatikan masalah program

linear berikut (harus dalam bentuk baku):

Minimum z = ct x (1)

dengan kendala
Ax = b
(2)
x ≥ 0,
dimana matriks A berukuran m × n dengan Rank(A) = m. Selanjuntya matriks A
dituliskan menjadi A = (B, N) dimana B matriks tak singular berukuran m × m
dan N matriks!berukuran m × (n − m). Misalkan kita mempunyai vektor BFS
B−1 b
x0 = , dengan fungsi obyektifnya z0 , yang diberikan oleh
0
! !
B−1 b B−1 b
z0 = ct = (ctB ctN ) = ctB B−1 b. (3)
0 0

Selanjutnya misalkan xB ≥ 0 dan xN ≥ 0 masing-masing secara berurutan me-

nyatakan varibel feasibel basis dan variabel feasibel nonbasis untuk suatu matriks
basis B dan matriks nonbasis N. Dari b = Ax = BxB + NxN dapat diperoleh

xB = B−1 b − B−1 NxN

(4)
= B−1 b − j∈J (B−1 aj )xj
P

dimana J adalah himpunan indeks dari variabel [Link] memperhatikan

kembali Persamaan (3) dan (4), nilai fungsi obyektif dapat dihitung sebagai

z = ct x
= ctB xB + ctN xN  P (5)
= ctB B−1 b − j∈J (B−1 aj )xj + j∈J cj xj
P

= z0 − j∈J (ctB B−1 aj − cj )xj .

P

1
Melalui proses di atas, masalah program linear (1)-(2) dapat dinyatakan kembali
sebagai masalah program linear berikut:
X
Minimum z = z0 − (ctB B−1 aj − cj )xj (6)
j∈J

dengan kendala
xB + j∈J B−1 aj xj = B−1 b
P
(7)
xB ≥ 0 dan xj ≥ 0, j ∈ J.
Tanpa mengurangi keberlakuan secara umum, misalkan xj > 0 untuk setiap j ∈ J
(jika terdapat xj = 0, maka variabel basis pada baris tersebut akan secara langsung
diketahui nilainya sehingga baris ini dapat dihilangkan dalam masalah program
linear ini).
Perhatikan bahwa pada Persamaan (7), variabel basis xB dapat dipandang sebagai
variabel slack untuk masalah program linear di ruang variabel nonbasis (variabel
keputusannya sekarang adalah variabel nonbasis xj , j ∈ J. Dalam variabel nonbasis,
masalah program linearnya menjadi
X
Minimum z = z0 − (ctB B−1 aj − cj )xj (8)
j∈J

dengan kendala
B−1 aj xj ≤ B−1 b
P
j∈J
(9)
xj ≥ 0, j ∈ J.
Ingat bahwa banyaknya variabel non basis adalah p = (n − m). Dengan demikian
pada ruang varibel nonbasis masalah program linear bekerja pada ruang berdimensi
p = (n − m). Koefisien (cj − ctB B−1 aj ) terkadang diistilahkan sebagai koefisien
biaya tereduksi. Bentuk program linear (8)-(9) dimana fungsi obyektif dan variabel
basis xB diselesaikan melalui vaiabel nonbasis biasa disebut representasi solusi basis
dalam bentuk kanonik. Hasil proses ini sebenarnya memberikan hasil utama:

Jika (ctB B−1 aj − cj ) ≤ 0 untuk setiap j ∈ J, maka BFS adalah solusi

optimal.

Hal ini jelas karena (ctB B−1 aj − cj ) ≤ 0 untuk setiap j ∈ J mengakibatkan z ≥ z0

untuk setiap solusi feasibel, dan untuk BFS awal x0 , nilai z = z0 karena xj = 0
untuk setiap j ∈ J.
Untuk mempermudah pembahasan berikutnya, kita akan menggunakan notasi-notasi
berikut
b̄ = B−1 b, yj = B−1 aj , zj = ctB B−1 aj , (10)

2
 sehingga diperoleh X
Minimum z = z0 − (zj − cj )xj (11)
j∈J

dengan kendala
P
≤ b̄
j∈J (yj )xj
(12)
xj ≥ 0, j ∈ J.

2. Motivasi geometris. Perhatikan bahwa representasi program linear pada ruang

variabel nonbasis (Persamaan (8)-(9)), ruang feasibelnya didefinisikan oleh n halfs-
pace: m halfspace terkait dengan kendala pertidaksamaan, dan p = n − m terkait
dengan kendala ketaknegatifan variabel. Untuk setiap ruang kendala terdapat vari-
abel yang disebut variabel penentu (defining varaible). Untuk kendala pertidak-
samaan, variabel penentunya adalah xB , dan untuk kendala ketaknegatifan variabel
penentunya adalah xj .
Untuk melihat motivasi geometris dari Metode Simplex, perhatikan Gambar 1, di-
mana p = 2, n = 6, dan m = 4. Misalkan J = {1, 2} (x1 , x2 sebagai nonbasis
variabel) dan BFS awal diberikan oleh x0 = (x3 , x4 , x5 , x6 ). Titik-titik esktrim pada

Gambar 1: Motivasi geometris Metode Simplex [Bazaraa et al].

ruang feasibel dinyatakan oleh vektor-vektor v1 , · · · , v5 dan c̄ menyatakan vektor

biaya tereduksi. Dalam masalah ini, BFS awal bersesuaian dengan vektor v1 (titik
(0, 0)). Perhatikan bahwa titik-titik ekstrim yang lain didefinisikan oleh irisan p = 2
hyperplane yang saling bebas linear, dengan p variabel penentu yang mendefiniskan
variabel nonbasis. Sebagai contoh, titik ekstrim v2 didefinisikan sebagai perpo-
tongan hyperplane x1 = 0 dan x3 = 0. Dengan demikian untuk titik ini yang men-
jadi variabel nonbasis adalah (x1 , x3 ) dan variabel basisnya (x2 , x4 , x5 , x6 ). Perlu
dicatat bahwa untuk titik ekstrim v3 , titik ini merupakan perpotongan tiga hyper-
plane (x3 = 0, x4 = 0, dan x5 = 0), dua dari hyperplane ini mendefinisikan secara
tunggal titik ekstrim sebagai titik perpotongannya.

3
Sekarang perhatikan titik v1 dan periksa p hyperplane yang memuat titik ini (dalam
contoh ini, x1 = 0 dan x2 = 0). Titik ini digerakkan dalam arah feasibel dari satu
hyperplane yang telah dipilih dari p hyperplane. Dengan kata lain kita menggerakan
titik tersebut sepanjang sinar satu dimensi yang berawal dari titik v1 . Ada p (dalam
contoh ini p = 2) sinar yang mungkin:

• Mempertahankan x2 = 0, titik digerakkan sepanjang x1 dimana fungsi obyektif

akan berubah dengan laju ∂z/∂x1 = −(z1 − c1 ) = (c1 − z1 ) = c̄1 < 0, atau
• Mempertahankan x1 = 0, titik digerakkan sepanjang x3 dimana fungsi obyektif
akan berubah dengan laju ∂z/∂x2 = −(z2 − c2 ) = (c2 − z2 ) = c̄2 < 0.

Arah yang dipilih adalah arah dengan koefisien biaya tereduksi (cj − zj ) paling
negatif. Dalam contoh ini misalkan c̄2 paling negatif, maka titik v1 digerakkan
sejauh mungkin darah arah hyperplane x2 . Akan tetapi gerakan ini akan terblok
oleh hyperplane x3 = 0; jika gerakannya diteruskan maka akan akan mencapai nilai
x3 yang negatif (di luar daerah feasibel). Pada titik dimana terjadi pemblokkan
(blocking), titik tersebut, dalam hal ini titik v2 , merupakan titik ekstrim yang lain.
Pada titik v2 , titik (x1 , x3 ) merupakan variabel nonbasis, dan titik-titik lainnya
merupakan variabel basis. Pada saat tersebut kita telah menyelesaikan satu tahap
yang disebut iterasi atau pivot dari Metode Simplex. Pada tahap ini, variabel
x3 disebut variabel pemblok (blocking variable) atau variabel basis (di v1 ) yang
menghilang (leaving variable). Variabel basis yang lama dengan yang baru hanya
berbeda pada satu variabel saja, artinya juga hanya berbeda pada satu variabel
nonbasisnya. Basis yang baru ini disebut basis berdekatan/berbatasan (adjacent
bases).
Proses diulangi pada titik v2 ini sampai akhirnya pergerakan terblok kembali di titik
v3 . Pada titik ini terdapat lebih dari satu hyperplane pemblok. Misalkan kita pilih
x4 sebagai variabel pemblok. Pada titik v3 variabel nonbasisnya menjadi x3 dan x4 .
Jika kita tetapkan x4 = 0 dan bergerak dalam arah bertambahnya x3 , maka nilai
fungsi obyektifnya akan turun karena arah ini membentuk sudut lancip dengan arah
vektor c̄. Akan tetapi arah ini menuju ke daerah diluar daerah feasibel. Dengan
demikian kita sebenarnya terblok oleh hyperplane x5 = 0. Artinya, x5 menjadi
variabel basis yang menghilang dan sekarang x4 dan x5 variabel nonbasis yang baru
dimana pada saat ini kita berada di titik v3 . Tahap dimana kita mengubah satu
basis menjadi basis baru, akan tetapi kedua basis tersebut masih menghasilkan
solusi titik ekstrim yang sama, tahap ini disebut tahap iterasi/pivot degenerate
(sebenarnya tahap ini tidak diinginkan).
Dengan menetapkan x4 dan x5 sebagai variabel nonbasis untuk titik v3 dan untuk
selanjutnya menetapkan x5 = 0 serta menggerakkan titik v3 , variabel pemblok

4
 yang berikutnya adalah x6 dan akan sampai di titik v4 . Pada titik ini variabel
nonbasis baru adalah x5 dan x6 . Terkait dengan basis ini, tak satupun dari p
sinar (menetapkan (p − 1) variabel nonbasis sama dengan nol dan menaikkan satu
variabel nonbasis lainnya) memberikan nilai fungsi obyektif yang lebih baik. Oleh
karenanya, titik v4 dapat dinyatakan sebagai titik optimal. Lintasan/jalur yang
dilalui oleh algoritma Simplex sepanjang sisi-sisi poihedron (dari titik v1 ke titik v2
sampai dengan titik v4 ) disebut Lintasan/ Jalur Simplex (simplex path).

3. Aljabar Metode Simplex. Iterasi Metode Simplex akan diimplementasikan pada

masalah program linear yang terdefinisi pada ruang variabel nonbasis. Hal ini akan
memudahkan kita dalam melacak nilai fungsi obyektif berdasarkan koefisien biaya
tereduksinya.
Perhatikan kembali masalah program linear dalam ruang variabel nonbasis yang
diberikan oleh Persamaan (6)-(7) dengan notasi (10). Jika (zj − cj ) ≤ 0 untuk
semua j ∈ J, maka xj = 0, j ∈ J dan xB = b̄ merupakan solusi optimal. Jika
kondisi tersebut tidak dipenuhi, maka Metode Simplex melakukan pencarian solusi
baru dengan cara menetapkan (p − 1) variabel nonbasis bernilai nol dan menaikkan
satu nilai variabel nonbasis yang tersisa agar bernilai positif sesuai dengan daerah
feasibilitasnya. Misalkan varibel nonbasis yang dinaikkan tersebut adalah xk . Kita
menginginkan variabel xk dengan (zk − ck ) yang positif (bahkan bernilai positif
terbesar dari semua j ∈ J). Selanjutnya, tetapkan xj = 0 untuk setiap j ∈ J − {k}.
Dari Persamaan (6)-(7) kita peroleh

z = z0 − (zk − ck )xk (13)

dan      
xB 1 b̄1 y1k
 .   ..   .
 ..    .

   .   .


 xBr  =  b̄r  −  yrk  xk . (14)
     
 .   ..   . 
 ..   .   ..
 
   
xBm b̄m ymk
Jika yik ≤ 0, maka xBi akan naik dengan naiknya xk . Jika yik > 0, maka xBi akan tu-
run dengan naiknya xk . Agar memenuhi kondisi ketaknegatifan solusi, xk dinaikkan
sampai dengan variabel basis xBr pertama kali bernilai nol. Lebih jelasnya, xk yang
dipilih adalah  
b̄r b̄i
xk = = min : yik > 0 (15)
yrk 1≤i≤m yik
Untuk kasus nondegenerate, b̄r > 0 dan xk = b̄r /yrk > 0. Variabel yrk di atas
disebut variabel pivot. Dari Persamaan (13) dengan fakta zk − ck > 0, maka z <

5
 z0 (fungsi obyektif terbaharui menjadi lebih baik/bernilai lebih kecil dari iterasi
sebelumnya). Sejalan dengan menaikkan xk dari 0 menjadi b̄r /yrk , variabel solusi
yang baru diberikan oleh
yik
x0Bi = b̄i − b̄r , i = 1, 2, · · · , m dan i 6= k, r,
yrk
b̄r
x0Bk = , (16)
yrk
x0Br = 0,
x0Nj = 0, j yang lainnya.

Dari Persamaan (16), xk dan xBr bertukar peran dari variabel nonbasis menjadi basis
dan sebaliknya. Dengan demikian pada solusi terbaharui paling banyak terdapat m
variabel bernilai positif. Kolom-kolom matriks A yang bersesuaian diberikan oleh
aB1 , · · · , aBr−1 , ak , aBr+1 , · · · , aBm . Kolom-kolom ini bebas linear karena yrk 6= 0
(mengapa?). Dengan demikian, titik-titik yang diberikan oleh (16) merupakan BFS.
Untuk rekapitulasi, iterasi Metode Simplex berisi: menaikkan variabel nonbasis
xk yang memiliki nilai (zk − ck ) positif terbesar, membuat variabel xBr bernilai
nol, variabel xk masuk sebagai basis dan variabel xBr meninggalkan basis (beraksi
sebagai blocking variable). Kriteria untuk masuk dan meninggalkan basis diberikan
oleh kriteria berikut:

• Masuk menjadi basis: xk masuk menjadi basis jika zk − ck > 0.

 
b̄r b̄i
• Meninggalkan basis: xBr meninggalkan basis jika = min : yik > 0
yrk 1≤i≤m yik

Contoh 1 Selesaikan secara aljabar dengan iterasi Metode Simplex

(a) min(x1 + x2 ), X = {(x1 , x2 )|x1 + 2x2 ≤ 4, x2 ≤ 1, x1 ≥ 0, x2 ≥ 0}.

(b) min(2x1 − x2 ), X = {(x1 , x2 )| − x1 + x2 ≤ 2, 2x1 + x2 ≤ 6, x1 ≥ 0, x2 ≥ 0}.

(c) min(−3x1 + x2 ), X = {(x1 , x2 )|x1 + 2x2 ≤ 4, −x1 + x2 ≤ 1, x1 ≥ 0, x2 ≥ 0}.

(d) min(−x1 − 3x2 ), X = {(x1 , x2 )|x1 − 2x2 ≤ 4, −x1 + x2 ≤ 3, x1 ≥ 0, x2 ≥ 0}.

4. Algoritma Metode Simplex. Algoritma ini akan digunakan untuk meyelesaikan

masalah minimasi dalam bentuk baku (1)-(2).

1. (BFS awal). Pilih suatu matriks basis B yang akan memberikan BFS awal.
Kemudian hitung xB = B−1 b. Selanjutnya, misalkan xB = b̄, xN = 0, dan
z = ctB xB .

6
 2. (Keoptimalan solusi). Selesaikan w = ctB B−1 . Vektor w disebut vektor pengali
Simplex, komponen-komponenannya menjadi pengali untuk baris-baris matriks
A yang ditambahkan pada fungsi obyektif agar menjadi bentuk kanonik. Hi-
tung zj − cj = waj − cj untuk semua variabel nonbasis (proses ini disebut
pricing operation). Misalkan

zk − ck = max(zj − cj ),
j∈J

dimana J himpunan indeks terkait variabel nonbasis. Jika zk − ck ≤ 0, iterasi

berhenti dan BFS sekarang merupakan solusi optimal. Jika tidak, lanjutkan
ke tahap 3 dengan xk sebagai variabel yang masuk basis.
3. (Ketakterbatasan solusi optimal). Selesaikan yk = B−1 ak . Jika yk ≤ 0, maka
iterasi berhenti dengan kesimpulan solusi optimalnya tak terbatas sepanjang
sinar  ! ! 
b̄ −yk
+ xk : xk ≥ 0 ,
0 ek
dimana ek adalah vektor berdimensi (n − m) dengan komponen ke-k bernilai
1 dan lainnya 0. Jika yk
0, lanjutkan ke tahap 4.
4. (Uji rasio minimum) Misalkan xk menjadi variabel basis. Indeks r dari variabel
pemblok xBr yang meninggalkan basis ditentukan berdasarkan
 
b̄r b̄i
= min : yik > 0 .
yrk 1≤i≤m yik

Perbaharui matriks basis B dimana ak menggantikan aBr , juga indeks J, dan

ulangi tahap 1.

5. Kekonvergenan Metode Simplex. Untuk kasus nondegenerate, Metode Simplex

akan berhenti pada berhingga iterasi dengan menghasilkan BFS optimal atau solusi
optimal yang tidak terbatas.

6. Metode Simplex dalam bentuk tabel. Misalkan kita mempunyai BFS awal
x dengan matriks basis B. Masalah program linear dapat disajikan dalam bentuk
berikut:
Minimum z (17)
dengan kendala
z − ctB xB − ctN xN = 0
BxB + NxN = b (18)
xB , xN ≥ 0.

7
 Dari persamaan kedua di (18) diperoleh

xB + B−1 NxN = B−1 b. (19)

Hitung hasilkali titik kedua ruas (19) dengan ctB kemudian menjumlahkan hasil yang
diperolehnya dengan persamaan pertama (18) kita peroleh

z + 0xB + (ctB B−1 N − ctN )xN = ctB B−1 b. (20)

Pada saat awal, xN = 0 sehingga diperoleh xB = B−1 b dan z = ctB B−1 b. Dari (19)
dan (20) kita dapat menyajikan BFS awal dengan matriks basis B dalam bentuk
tabel.
Dalam bentuk tabel, z pada (20) akan dipandang sebagai variabel (basis) yang akan
diminimumkan dan akan dirujuk sebagai baris ke-0 di tabel. Sedangkan (20) akan
mengisi baris sisanya, yaitu baris ke-1 sampai dengan barisk ke-m. Kolom ruas
kanan (RK) akan menyatakan nilai fungsi obyektif dan nilai variabel basis. Varibel
basis akan diidentifikasi oleh kolom yang paling kiri (lihat Tabel 1). Tabel dimana
z dan xB telah diselesaikan dalam variabel xN disebut tabel dalam bentuk kanonik.
Tabel tersebut tidak hanya memberikan informasi nilai fungsi obyektif ctB B−1 b dan
nilai variabel basis B−1 b, tetapi juga memberikan informasi berikut:

• baris ctB B−1 N−ctN memberikan informasi nilai zj −cj untuk variabel nonbasis.
• baris ke-0 memberikan indikasi apakah berada di solusi optimal (jika zj −cj ≤ 0)
ataukah tidak. Jika tidak maka memberikan informasi variabel nonbasis mana
yang harus dinaikkan agar menjadi variabel basis.
• misalkan nilai variabel xk dinaikkan. Vektor yk = B−1 ak yang disimpan di
baris ke-1 sampai dengan ke-m akan menginformasikan seberapa besar nilai
xk harus dinaikkan. Jika yk ≤ 0, maka xk dapat dinaikkan sebesar mungkin
tanpa ada variabel lain yang akan membloknya. Jadi, dalam kasus tersebut
solusi optimalnya tak terbatas. Sebaliknya, jika yk  0, yaitu paling sedikit
salah satu komponen yk bernilai positif, maka kenaikkan xk akan terblok oleh
salah satu variabel basis yang selanjutnya memaksa nilai basis tersebut menjadi
nol.
• Uji rasio minimum B−1 b = b̄ dan yk akan menentukan kriteri variabel pem-
blok.

7. Proses pivot. Jika xk menjadi berperan sebagai variabel basis dan xBr menjadi
variabel nonbasis, proses pivot pada yrk dijelaskan sebagai berikut:

• Kalikan baris ke-r dengan faktor 1/yrk .

8
 z xB xN RK
−1
z 1 0 t
cB B N − ctN ctB B−1 b Baris ke-0
−1 −1
xB 0 I B N B b Baris ke-i, i = 1, · · · , m

Tabel 1: Metode Simplex dalam bentuk tabel.

• Untuk i = 1, · · · , m dan i 6= r, perbaharui baris ke-i dengan menambahkan

baris tersebut dengan (−yik ) kali baris ke-r yang sudah diperbaharui.
• Perbaharui baris ke-0 dengan menambahkan baris tersebut dengan (ck − zk )
kali baris ke-r yang sudah diperbaharui. Tabel 2 dan Tabel 3 memperlihatkan
keadaan sebelum dan sesudah proses pivot dilakukan.

z xB1 xBr xBm xj xk RK

z 1 0 ··· 0 ··· 0 ··· zj − cj ··· zk − ck ··· ctB b̄
xB1 0 1 ··· 0 ··· 0 ··· y1j ··· y1k ··· b̄1
.. .. .. .. .. .. .. ..
. . . ··· . ··· . ··· . ··· . ··· .
xBr 0 0 ··· 1 ··· 0 ··· yrj ··· yrk ··· b̄r
.. .. .. .. .. .. .. ..
. . . ··· . ··· . ··· . ··· . ··· .
xBm 0 0 ··· 0 ··· 1 ··· ymj ··· ymk ··· b̄m

Tabel 2: Sebelum proses pivot.

z xB1 xBr xBm xj xk RK

(zk −ck )
z 1 0 ··· − yrk ··· 0 ··· zj − cj ··· 0 ··· ctB b̄ − (zk −c
yrk
k )b̄r

(z −c )y
− k yrkk rj
−y1k yrj y1k
xB1 0 1 ··· yrk
··· 0 ··· y1j − yrk y1k ··· 0 ··· b̄1 − b̄
yrk r
.. .. .. .. .. .. .. ..
. . . ··· . ··· . ··· . ··· . ··· .
1 yrj b̄r
xk 0 0 ··· yrk
··· 0 ··· yrk
··· 1 ··· yrk
.. .. .. .. .. .. .. ..
. . . ··· . ··· . ··· . ··· . ··· .
yrj
xBm 0 0 ··· − yymk
rk
··· 1 ··· ymj − y
yrk mk
··· 0 ··· b̄m − ymk
b̄
yrk r

Tabel 3: Setelah proses pivot.

Sebagai contoh, perhatikan masalah program linear berikut:

Minimum z = x1 + x2 − 4x3

dengan kendala
x1 + x2 + 2x3 ≤ 9
x1 + x2 − x3 ≤ 2
−x1 + x2 + x3 ≤ 4
x1 , x2 , x3 ≥ 0.

9
Masalah di atas diubah menjadi masalah program linear bentuk baku dengan mem-
perkenalkan variabel slack x4 , x5 , dan x6 . Masalah program linearnya sekarang
menjadi
Minimum z = x1 + x2 − 4x3 + 0x4 + 0x5 + 0x6
dengan kendala

x1 + x2 + 2x3 + x4 = 9
x1 + x2 − x3 + x5 = 2
−x1 + x2 + x3 + x6 = 4
x1 , x 2 , x 3 , x4 , x5 , x 6 ≥ 0 .

Karena b ≥ 0, maka kita dapat memilih matriks basis awal kita B = [a4 , a5 , a6 ] = I.
Juga diperoleh B−1 b = b ≥ 0. Berikut tabel iterasinya:
Iterasi ke-1: z3 −c3 = 4 nilai terbesar, kolom x3 dengan uji minimum rasio diperoleh
elemen pivot seperti yang ditandai kotak.

z x4 x5 x6 x1 x2 x3 RK
z 1 0 0 0 −1 −1 4 0
x4 0 1 0 0 1 1 2 9
x5 0 0 1 0 1 1 −1 2
x6 0 0 0 1 −1 1 1 4

Tabel 4: Iterasi ke-1.

Iterasi ke-2:z1 − c1 = 5 nilai terbesar, kolom x1 dengan uji minimum rasio diperoleh
elemen pivot seperti yang ditandai kotak.

z x4 x5 x6 x1 x2 x 3 RK
z 1 0 0 −4 3 −5 0 −16
x4 0 1 0 −2 3 −1 0 1
x5 0 0 1 1 0 2 0 6
x3 0 0 0 1 −1 1 1 4

Tabel 5: Iterasi ke-2.

Iterasi ke-3: tabel ini optimal karena zj − cj ≤ 0 untuk semua variabel nonbasis.
Solusi optimalnya diberikan oleh x1 = 1/3, x2 = 0 dan x3 = 13/3, dengan nilai
fungsi obyektifnya z =  −17. Solusi optimal
 yang diperoleh memberikan matriks
1 0 2
basis B = [a1 , a5 , a3 ] =  1 1 −1  .
 

−1 0 1

10
 z x4 x5 x6 x1 x2 x3 RK
z 1 −1 0 −2 0 −4 0 −17
x1 0 1/3 0 −2/3 1 −1/3 0 1/3
x5 0 0 1 1 0 2 0 6
x3 0 1/3 0 1/3 0 2/3 1 13/3

Tabel 6: Iterasi ke-3.

8. Pemilihan BFS awal. Telah diketahui bahwa Metode Simplex dimulai dari BFS
awal untuk kemudian diiterasi agar diperoleh BFS lain dengan nilai fungsi obyektif
yang lebih baik atau solusi optimalnya diketahui tak terbatas. Perhatikan kembali
masalah program linear berikut

Minimum z = ct x (21)

dengan kendala
Ax ≤ b
(22)
x ≥ 0,
dimana matriks A berukuran m × n dengan Rank(A) = m. Lebih jauh lagi, asum-
sikan b ≥ 0 (vektor taknegatif). Dengan menambahkan variabel slack xs , kendala
(22) dapat dituliskan dalam bentuk baku

Ax + xs = b
(23)
x, xs ≥ 0,

Perhatikan bahwa matriks kendala baru [A, I] yang berukuran m×(m+n) memiliki
Rank m, and BFS awalnya diberikan oleh xs = b dan x = 0. Selanjutnya, Metode
Simplex dapat digunakan untuk menyelesaikannya.
Akan tetapi, jika asumsi ketaknegatifan vektor b diatas dilanggar, maka setelah
memperkenalkan variabel slack xs , kita tidak dapat memilih BFS awalnya diberikan
oleh xs = b dan x = 0, karena hal ini melanggar kendala ketaknegatifan. Masalah
serupa juga terjadi jika kendalanya berbentuk Ax ≥ b, x ≥ 0, dimana b
0.
Setelah memperkenalkan variabel slack xs sehingga diperoleh Ax − xs = b, x, xs ≥
0, maka tidak ada jaminan untuk memilih matriks basis B dari matriks [A, −I]
dengan B−1 b ≥ 0.
Secara umum, dengan memperkenalkan variabel slack dan manipulasi sederhana
dengan perkalian (−1) jika diperlukan kepada setiap kendala, (21)-(22) dapat diubah
menjadi
Minimum z = ct x (24)

11
 dengan kendala
Ax = b
(25)
x ≥ 0,
dimana b ≥ 0. Jika matriks A memuat matriks identitas, maka BFS awal da-
pat dengan langsung diambil dengan memilih B = I dan B−1 b = b ≥ 0. Jika
matriks A tidak memuat matriks identitas, maka teknik lain harus dilakukan den-
gan menambahkan suatu artificial variable (variabel palsu) xa seperti yang akan
dijelaskan berikut. Untuk memudahkan pembahasan, variabel x yang berasal dari
masalah semula (24) akan disebut variabel asli.
Misalkan kendala yang dipunyai dimodifikasi dengan memperkenalkan (variabel
palsu) xa sehingga diperoleh Ax + xa = b, xa , xa ≥ 0. Modifikasi ini memaksa kita
untuk memperoleh matriks identitas sebagai matriks basis dengan variabel palsu xa
sebagai variabel BFS awal, yaitu xa = b. Selanjutnya akan digunakan Metode Sim-
plex untuk menyelesaikan masalah termodifikasi ini. Untuk mengembalikan masalah
termodifikasi menjadi masalah semula, kita harus memaksa variabel palsu ini berni-
lai nol, karena Ax = b jika dan hanya jika Ax + xa = b dengan xa = 0. Dengan
kata lain, variabel palsu digunakan sebagai alat agar Metode Simplex dapat mulai
bekerja dengan BFS awal yang sederhana (bedakan antara variabel slack dengan
variabel palsu!). Berikutnya akan dibahas dua metode untuk pemilihan BFS awal:
Metode dua-fase/tahap dan Metode Big-M.

9. Metode dua-fase/tahap. Kerangka dari metode tersebut diberikan sebagai berikut:

TAHAP I: Menyelesaikan masalah berikut dengan BFS awal x = 0 dan xa = b.

Minimum z = 1t xa (26)

dengan kendala
Ax + xa = b
(27)
x, xa ≥ 0,
Jika solusi optimal tercapai dengan menyisakan variabel palsu tak nol, xa 6= 0,
maka tahap selanjutnya tidak perlu dilanjutkan; masalah semula tidak mempunyai
solusi feasibel. Jika semua variabel palsunya bernilai nol, maka kita gunakan solusi
basis xB dan solusi nonbasis xN yang diperoleh di (26)-(27) sebagai BFS awal untuk
tahap selanjutnya.
TAHAP II: Menyelesaikan masalah berikut dengan BFS awal diperoleh dari tahap
sebelumnya; xB = B−1 b dan xN = 0.

Minimum z = ctB xB + ctN xN (28)

12
dengan kendala
B−1 NxN + xB = B−1 b
(29)
xB , xN ≥ 0,
Sebagai contoh, perhatikan masalah program linear berikut:

Minimum z = x1 − 2x2

dengan kendala
x1 + x2 ≥ 2
−x1 + x2 ≥ 1
(30)
x2 ≤ 3
x1 , x 2 ≥ 0.
Setelah memperkenalkan variabel slack x3 , x4 , dan x5 , kita peroleh

Minimum z = x1 − 2x2 (31)

dengan kendala

x1 + x2 − x3 = 2
−x1 + x2 − x4 = 1
(32)
x2 + x5 = 3
x1 , x 2 , x 3 , x 4 , x 5 ≥ 0.

Pada (32) matriks identitas tidak muncul. Oleh karena itu perlu ditambahkan
variabel palsu x6 dan x7 untuk meminimumkan x0 = x6 + x7 . Pada kasus ini
variabel slack x5 sekaligus berperan sebagai variabel palsu. Dalam bentuk tabel
(lihat Tabel 7), masalah (32) dengan fungsi obyektif meminimumkan x0 = x6 + x7
menjadi

x0 x1 x2 x3 x4 x5 x6 x 7 RK
1 0 0 0 0 0 −1 −1 0
0 1 1 −1 0 0 1 0 2
0 −1 1 0 −1 0 0 1 1
0 0 1 0 0 1 0 0 3

Tabel 7: Bentuk tabel masalah (32).

Tambahkan baris ke-1 dan ke-2 pada baris ke-0 sehingga z6 − c6 = 0 = z7 − c7

(elemen variabel palsu pada baris ke-0 (fungsi obyektif) dinolkan), diperoleh Tabel
8,

13
 x0 x1 x2 x3 x4 x5 x6 x7 RK
x0 1 0 2 −1 −1 0 0 0 3
x6 0 1 1 −1 0 0 1 0 2
x7 0 −1 1 0 −1 0 0 1 1
x5 0 0 1 0 0 1 0 0 3

Tabel 8: Menolkan variabel palsu.

x0 x1 x2 x3 x4 x5 x6 x7 RK
x0 1 2 0 −1 1 0 0 −2 1
x6 0 2 0 −1 1 0 1 −1 1
x2 0 −1 1 0 −1 0 0 1 1
x5 0 1 0 0 1 1 0 −1 2

Tabel 9: Iterasi Metode Simplex.

Berikutnya dilakukan penyelesaian dengan Metode Simplex (Tabel 9-10) sampai

pada akhirnya kita memperoleh BFS awal x1 = 1/2 dan x2 = 3/2 dimana pada saat
tersebut proses TAHAP I berakhir (mengapa?).
Untuk melanjutkan ke TAHAP II, tabel yang sama dari proses terakhir TAHAP
I akan digunakan dengan terlebih dahulu membuang kolom-kolom yang memuat
variabel palsu kemudian menggantikan baris ke-0 dengan fungsi obyektif asal (Tabel
11):
Kalikan baris ke-1 dengan faktor 1 dan baris ke-2 dengan faktor (-2), kemudian
tambahkan pada baris ke-0 sehingga z1 − c1 = 0 = z2 − c2 (elemen variabel basis
pada baris ke-0 dinolkan, lihat Tabel 12). Selanjuntya diterapkan iterasi Metode
Simplex (Tabel 13-14). Karena pada Tabel 14 nilai zj −cj ≤ 0 untuk semua variabel
nonbasis, solusi optimal dicapai saat (x1 , x2 ) = (0, 3).
Pada akhir TAHAP I, variabel palsu dapat bernilai xa 6= 0 atau xa = 0.

• Untuk kasus xa 6= 0, maka masalah awal tidak memiliki solusi feasibel; andaikan
ada solusi feasibel x ≥ 0 dengan Ax = b, maka (x, 0)t merupakan solusi
feasibel untuk TAHAP I dan 0t x + 1t 0 = 0 < 1t xa , bertentangan dengan
keoptimalan solusi xa .
• Untuk kasus xa = 0, terbagi menjadi dua subkasus; pada akhir proses TAHAP
I: 1) semua variabel palsu menjadi variabel nonbasis, 2) terdapat sebagian
variabel palsu bernilai nol yang menjadi variabel basis.
– Untuk subkasus 1), variabel basis hanya diwakili oleh variabel asli. Jika
variabel asli dibagi menjadi variabel basis xB dan variabel nonbasis xN ,

14
 x0 x1 x2 x3 x4 x5 x6 x7 RK
x0 1 0 0 0 0 0 −1 −1 0
x1 0 1 0 −1/2 1/2 0 1/2 −1/2 1/2
x2 0 0 1 −1/2 −1/2 0 1/2 1/2 3/2
x5 0 0 0 1/2 1/2 1 −1/2 −1/2 3/2

Tabel 10: Iterasi Metode Simplex.

x0 x1 x2 x3 x4 x5 RK
1 −1 2 0 0 0 0
0 1 0 −1/2 1/2 0 1/2
0 0 1 −1/2 −1/2 0 3/2
0 0 0 1/2 1/2 1 3/2

Tabel 11: Membuang kolom variabel palsu dan mengganti fungsi obyektif.

maka di akhir proses TAHAP I akan diperoleh Tabel 15. Sekarang Tahap
II dapat dimulai dengan menggantikan baris ke-0 dengan fungsi obyektif
semula dan membuang kolom variabel palsu, sehingga diperoleh Tabel 16.

– Untuk subkasus 2), kita dapat melakukannya dengan dua cara:

(a) Proses langsung ke TAHAP II. Proses ini dimulai dengan membuang
kolom variabel palsu yang merupakan variabel nonbasis pada TAHAP
I. Tabel awal TAHAP II akan memuat variabel asli dan beberapa vari-
abel palsu yang bernilai nol. Baris ke-0 yang memuat nilai (zj − cj )
direkonstruksi sedemikian sehingga semua variabel asli yang meru-
pakan variabel basis bernilai nol ((zj − cj ) = 0, demikian pula hal
ini terjadi untuk koefisien biaya dari variabel palsu). Selanjutnya
Metode Simplex diterapkan pada TAHAP II ini tetapi dengan pa-
tokan bahwa variabel palsu tetap dipertahankan bernilai nol, tidak
boleh menjadi bernilai positif (melanggar kondisi ketaknegatifan so-
lusi). Sebagai ilustrasi, misalkan x1 , · · · , xn merupakan variabel asli
dan xn+1 , · · · , xn+m merupakan variabel palsu. Dari kelompok varibel
tersebut, misalkan x1 , · · · , xk variabel asli yang menjadi variabel basis,
xn+1 , · · · , xn+k variabel palsu yang keluar dari basis selama TAHAP
I, xn+k+1 , · · · , xn+m variabel palsu yang muncul sebagai variabel basis
(lihat Tabel 17). Misalkan (zj − cj ) > 0. Dengan demikian xj dapat
dipilih untuk masuk menjadi variabel basis;
∗ Jika yij ≥ 0 untuk i = k + 1, · · · , m, maka variabel palsu xn+i akan

15
 x0 x1 x2 x3 x4 x5 RK
z 1 0 0 1/2 3/2 0 −5/2
x1 0 1 0 −1/2 1/2 0 1/2
x2 0 0 1 −1/2 −1/2 0 3/2
x5 0 0 0 1/2 1/2 1 3/2

Tabel 12: Menolkan kolom yang memuat variabel basis.

tetap bernilai nol dan uji rasio minimum biasa dapat diterapkan.
∗ Jika paling sedikit satu komponen yrj < 0, r = k + 1, · · · , m, maka
variabel palsu xn+r akan bernilai positif. Hal ini harus dihindari
dengan cara mengambil variabel pivotnya yang berkaitan dengan
yrj < 0. Dalam kasus ini variabel xn+r akan meninggalkan basis dan
bertukar peran dengan variabel xj . Selain itu, fungsi obyektif akan
bernilai tetap, tidak berubah dari proses sebelumnya.
Setelah modifikasi di atas, Metode Simplex dapat digunakan untuk
menyelesaikan TAHAP II.
(b) Eliminasi variabel palsu di akhir TAHAP I. Tabel 18 menggambarkan
situasi di saat akhir TAHAP I. Karena baris dan kolom fungsi obyek-
tif kurang relevan pada cara ini, maka baris dan kolom tersebut akan
diabaikan untuk sementara waktu. Selanjutnya kita berusaha untuk
membuat variabel palsu xn+k+1 , · · · , xn+m meninggalkan basis dengan
menempatkan (m−k) variabel asli nonbasis xk+1 , · · · , xn menjadi vari-
abel basis. Sebagai contoh, variabel palsu xn+k+1 dapat dibuat mening-
galkan basis dengan melakukan pivot pada sebarang elemen tak nol di
baris pertama R2 . Variabel asli nonbasis yang terkait akan menggan-
tikan variabel palsu tersebut sehingga diperoleh tabel yang terbaharui.
Proses serupa dilanjutkan.
∗ Jika semua variabel palsu dapat dibuat meninggalkan basis, maka
variabel basis yang baru akan memuat semua kolom variabel asli
untuk kemudian proses dilanjutkan ke TAHAP II.

x0 x1 x2 x3 x4 x5 RK
z 1 −3 0 2 0 0 −4
x4 0 2 0 −1 1 0 1
x2 0 1 1 −1 0 0 2
x5 0 −1 0 1 0 1 1

Tabel 13: Iterasi Metode Simplex masalah awal.

16
 x0 x1 x2 x3 x4 x5 RK
z 1 −1 0 0 0 −2 −6
x4 0 1 0 0 1 1 2
x2 0 0 1 0 0 1 3
x3 0 −1 0 1 0 1 1

Tabel 14: Iterasi Metode Simplex masalah awal.

x0 xB xN xa RK
x0 1 0 0 −1 0
−1
xB 0 I B N B−1 −1
B b

Tabel 15: Tabel Subkasus 1).

∗ Jika tabel yang diperoleh memuat R2 = 0, maka tak satupun vari-

abel palsu dapat meninggalkan basis. Dalam kasus ini Rank(A, b) =
k < m, yaitu (m − k) persamaan terakhir tidak berfaedah (re-
dundant) sehingga dapat diabaikan; (m − k) baris terakhir pada
tabel dapat dihilangkan untuk selanjutnya TAHAP II dapat diproses
tanpa melibatkan variabel palsu. Variabel basisnya adalah xB =
(x1 , · · · , xk ) dan variabel nonbasisnya adalah xN = (xk+1 , · · · , xn ).
Tabel untuk memulai TAHAP II diberikan oleh Tabel 19 dengan
matriks A11 merupakan submatriks dari matriks Am×n berukuran
k × k, !
A11 A12
Am×n = .
A21 A22

10. Metode Big-M. Metode ini pada prinsipnya menggabungkan dua fungsi obyektif,
yaitu fungsi obyektif asal dan fungsi obyektif yang memuat variabel palsu. Bentuk
permasalahannya dapat disajikan sebagai berikut.

Minimum z = ct x + M 1t xa (33)

dengan kendala
Ax + xa = b
(34)
x, xa ≥ 0,
dimana konstanta M adalah bilangan positif yang cukup besar. Suku M 1t xa da-
pat diinterpretasikan sebagai penalti bagi solusi dengan xa 6= 0; untuk xa 6= 0
maka suku kedua obyektif akan membesar (variabel tersebut akan menambah nilai
fungsi obyektif) sehingga variabel tersebut tidak akan terpilih sebagai calon solusi.

17
 z xB xN RK
−1
z 1 0 t
cB B N − ctN ctB B−1 b
−1 −1
xB 0 I B N B b

Tabel 16: Tabel TAHAP II.

z x1 ··· xk xk+1 ··· xj ··· xn xn+k+1 ··· xn+m RK
z 1 0 ··· 0 zj − cj 0 ··· 0 ctB b
x1 1 y1j 0 ··· 0 b1
x2 1 y2j 0 ··· 0 b2
.. ... .. .. .. ..
. . . ··· . .
xk 1 ykj 0 ··· 0 bk
xn+k+1 0 ··· 0 yk+1,j 1 0
.. .. .. .. .. ..
. . . . . .
xn+r 0 ··· 0 yrj 1 0
.. .. .. .. ... ..
. . . . .
xn+m 0 ··· 0 ymj 1 0

Tabel 17: Proses langsung ke TAHAP II.

Untuk memudahkan pembahasan selanjutnya, masalah semula akan dinotasikan P

sedangkan (33)-(34) dinotasikan P(M).
Karena P(M) mempunyai solusi feasibel (x = 0 dan xa = b), penyelesaian dengan
Metode Simplex pada P(M) akan mengantarkan kepada salah satu dari dua kasus
berikut:

• tercapainya suatu solusi optimal untuk P(M),

• P(M) mempunyai solusi optimal tak terbatas, z → −∞.

Tentu saja yang menjadi perhatian kita adalah optimasi masalah awal P, bukan
P(M). Analisis berikut akan membantu kita untuk menyimpulkan optimasi P:

(a) P(M) mempunyai solusi optimal hingga. Untuk kasus ini kita memiliki dua
kemungkinan.
i. Semua variabel palsu yang termuat pada solusi optimal P(M) bernilai nol,
yaitu (x∗ , 0). Dalam kasus ini x∗ merupakan solusi optimal P. Bukti:
Misalkan x solusi feasibel P. Maka, (x, 0) solusi feasibel P(M). Karena
(x∗ , 0) solusi optimal P(M) maka ct x∗ + 0 ≤ ct x + 0 atau ct x∗ ≤ ct x.
ii. terdapat variabel palsu tak nol yang termuat pada solusi optimal P(M),
yaitu (x∗ , xa ). Dalam kasus ini, jika M bilangan cukup besar maka P
tidak mempunyai solusi feasibel (buktikan!).

18
 Var. Asli Basis Var. Asli Nonbasis Var. Palsu Nonbasis Var. Palsu Basis
x1 x2 · · · xk xk+1 · · · xn xn+1 · · · xn+k xn+k+1 · · · xn+m RK
x1 1 0 0 ··· 0 b1
x2 1 R1 R3 0 0 ··· 0 b2
.. .. .. .. .. ..
. . . . ··· . .
..
xk 1 0 0 ··· . bk
xn+k+1 0 0 ··· 0 1 0
R2 R4 1 0
.. .. .. .. .. ..
. . . . . .
xn+m 0 0 ··· 0 1 0

Tabel 18: Proses eliminasi variabel palsu di akhir TAHAP I.

z xB xN RK
z 1 0 ctB R1− ctN ctB A−1
11 b1
xB 0 I R1 A−1
11 b1

Tabel 19: Tabel kondisi awal ke TAHAP II.

(b) P(M) mempunyai solusi optimal tak terbatas, z → −∞. Misalkan selama
pencarian solusi dengan Metode Big-M, yk ≤ 0 pada kolom ke-k denganzj − cj
bernilai positif terbesar. Maka, P(M) memiliki solusi optimal tak terbatas.
Lebih jauh lagi,
i. Jika semua variabel palsunya bernilai nol, maka P mempunyai nilai opti-
mal tak berhingga.
ii. Jika paling sedikit terdapat satu variabel palsu positif, maka P tak feasibel.

11. Cycling dan aturan Lexicographic. Perhatikan kembali (24)-(25). Karena

Metode Simplex dimulai dengan memilih BFS awal dari matriks identitas, pada
bagian ini kita asumsikan m kolom pertama dari A berbentuk matriks identitas
(ingat, RankA=m). Aturan berikut, yang mengidentifikasi variabel yang mening-
galkan basis jika uji rasio minimum memberikan lebih dari satu calon variabel yang
meninggalkan basis, akan menjamin tidak terjadi cycling.
Aturan Lexicographic. Diberikan BFS dengan matriks basis B dan misalkan variabel
nonbasis dipilih untuk menjadi variabel basis xk . Indeks r dari variabel xBr yang
meninggalkan basis ditentukan sebagai berikut:

• Misalkan I0 = {r : b̄r
yrk
= min { yb̄iki : yik > 0}}. Jika I0 hanya memuat satu
1≤i≤m
elemen, yaitu I0 = {r}, maka xBr yang meninggalkan basis. Jika tidak, bentuk
I1 sebagai berikut
yr1
• I1 = {r : yrk
= min{ yyik
i1
}}. Jika I1 hanya memuat satu elemen, yaitu I1 = {r},
i∈I0
maka xBr yang meninggalkan basis. Jika tidak, bentuk I2 . Secara umum

19
 yrj ijy
• Ij = {r : yrk
= min { yik }}. Pada akhirnya, untuk suatu j ≤ m, Ij hanya akan
i∈Ij−1
memuat satu elemen. Jika Ij hanya memuat satu elemen, yaitu Ij = {r}, maka
xBr yang meninggalkan basis.

Latihan
1. Perhatikan masalah program linear berikut: min ct x dengan kendala Ax ≤ b, x ≥ 0,
dimana c suatu vektor tak nol. Misalkan x0 suatu titik sehingga Ax0 < b, x0 > 0.
Perlihatkan bahwa x0 bukan solusi optimal.

2. Diberikan masalah program linear berikut:

Maksimum z = x1 + 3x2

dengan kendala
x1 − 3x2 ≤ 3
−2x1 + x2 ≤ 2
−3x1 + 4x2 ≤ 12
3x1 + x2 ≤ 9
x1 , x 2 ≥ 0.

(a) Sketsakan daerah feasibelnya di bidang (x1 , x2 ) dan identifikasi solusi optimal-
nya.
(b) Identifikasi semua titik ekstrim dan reformulasi masalah di atas sebagai masalah
kombinasi konveks titik-titik ekstrim. Kemudian cari solusinya.
(c) Misalkan kendala keempat dihilangkan. Identifikasi titik ekstrim dan arah esk-
trimnya kemudian reformulasikan masalahnya sebagai masalah kombinasi kon-
veks titik-titik esktrim dan kombinasi linear arah ekstrim. Selesaikan masalah
tersebut dan interpretasikan hasilnya.

3. Perhatikan masalah program linear memaksimumkan ct x, dimana x1 , x2 , x3 , x4 meru-

pakan titik-titik ekstrim, dan d1 , d2 , d3 merupakan arah ekstrim. Nilai-nilai fungsi
obyektifnya diketahui ct x1 = 5, ct x2 = 7, ct x3 = 4, ct x4 = 7, ct d1 = 0, ct d2 = −3,
dan ct d3 = 0. Karakterisasi himpunan solusi optimal alternatif untuk masalah ini.

4. Perhatikan kendala-kendala berikut:

x1 + x2 ≤ 3
−2x1 + x2 ≤ 2
x1 − 2x2 ≤ 0
x1 , x 2 ≥ 0.

20
 (a) Sketsakan daerah feasibelnya di bidang (x1 , x2 ) dan identifikasi solusi optimal-
nya.
(b) Identifikasi semua titik ekstrim, dan pada setiap titik ekstrim identifikasi semua
variabel basis dan variabel nonbasis yang mungkin.
(c) Misalkan suatu iterasi dimualai dari titik (2, 1) ke arah titik esktrim (0, 0) di
bidang (x1 , x2 ). Identifikasikan varibel yang akan meninggalkan dan menggan-
tikan basis.

5. Selesaikan masalah
Maksimum z = 5x1 + 4x2
dengan kendala
x1 + 2x2 ≤ 6
−2x1 + x2 ≤ 4
5x1 + 3x2 ≤ 15
x1 , x 2 ≥ 0.

(a) secara grafik.

(b) menggunakan aljabar Metode Simplex.

6. Selesaikan masalah berikut dengan tabel Metode Simplex

Maksimum z = x1 − 2x2 + x3

dengan kendala
x1 + 2x2 + x3 ≤ 12
2x1 + x2 − x3 ≤ 6
−x1 + 3x2 ≤ 9
x1 , x 2 , x 3 ≥ 0 .

7. Karakterisasi himpunan solusi optimal alternatif dari tabel berikut:

z x1 x2 x 3 x4 x5 x6 RK
z 1 0 0 0 0 2 3 0
x1 0 1 0 2 −1 −1 1 0
x2 0 0 1 −2 1 2 3 0

8. Gunakan metode dua-tahap untuk menyelesaikan

Maksimum z = −x1 − 2x2

21
 dengan kendala
3x1 + 4x2 ≤ 12
2x1 − x2 ≥ 2
x1 , x2 ≥ 0.

9. Gunakan Metode Big-M untuk menyelesaikan

Maksimum z = x1 − 2x2 + x3

dengan kendala
x1 + x2 − x3 ≥ 4
x1 − 4x2 + x3 ≤ 2
x1 , x 2 , x 3 ≥ 0 .

22