BENTUK DUAL SIMPLEKS

Posted on November 4, 2014 by gunawan

DUALITAS DAN ANALISIS SENSITIVITAS

Istilah dualitas merujuk pada kenyataan bahwa setiap LP terdiri atas dua
bentuk.
1) Bentuk asli disebut Primal
2) Bentuk dual.
Solusi terhadap LP yang asli juga memberikan solusi pada bentuk dualnya.
Jadi jika suatu LP diselesaikan dengan metode simpleks sesungguhnya
diperoleh penyelesaian untuk dua masalah LP.
Untuk menjelaskan mengenai bentuk dual ini kembali kita akan membahas
masalah diet.

Tabel 1.
Makanan tiruan

Kebutuhan

Kandungan Daging

Sayur

Mineral

Vitamin
Harga/unit

2
3

2
3

minimum per hari

40
50

2,5

Pokok permasalahannya adalah menentukan biaya pembelian sejumlah

daging dan sayuran sedemikian rupa sehingga kebutuhan minimum per hari
akan mineral dan vitamin dapat dipenuhi.
Rumusan Model LP :

Misalkan Xj (j = 1, 2) menyatakan banyak daging dan

sayuran yang dibeli. Sehingga hendak dicari berapa nilai X1 dan X2?
Minimumkan Z = 3X1 + 2,5X2
Dengan syarat 2X1 + 4X2 > 40
3X1 + 2X2 > 50
X1 > 0 dan X2 > 0.
Kemudian

sekarang

pikirkan

suatu

masalah

yang

berbeda

yang

berhubungan dengan masalah yang pertama (bentuk primal). Misalkan ada

sebuah dealer yang menjual mineral dan vitamin. Pemilik restoran setempat
membeli mineral dan vitamin dari dealer dan membuat daging dan sayur
tiruan yang berisi mineral dan vitamin seperti yang disajikan di tabel 1.
Dealer mengetahui benar bahwa daging dan sayur tiruan memiliki nilai hanya
karena kandungan mineral dan vitaminnya. Masalah bagi dealer adalah
menetapkan harga jual mineral dan vitamin per unit yang maksimum (masih
untung) sedemikian rupa sehingga menghasilkan harga daging dan sayur
tiruan tidak melebihi harga pasar yang berlaku atau yang ada.
Untuk itu perlu dirimuskan masalah secara matematik, misalkan dealer
memutuskan untuk menetapkan harga daging per unit sebesar Y1 dan untuk
sayur Y2.
Maksimumkan W = 40Y1 + 50Y2
Dengan syarat 2Y1 + 3Y2 < 3
4Y1 + 2Y2 < 2,5
Y1 > 0 dan Y2 > 0,
karena nilai neigatif tidak boleh.

Bentuk LP tersebut di atas dinamakan bentuk dual, sedangkan Y1 dan Y2

disebut variabel dual.
Bila masalah primal dibandingkan dengan masalah dual akan terlihat
hubungan sbb.
1) Koefisien fungsi tujuan masalah primal menjadi konstan sisi kanan
masalah dual. Sebaliknya, konstanta sisi kanan primal menjadi

koefisien

fungsi tujuan dual.

2. Tanda pertidaksamaan fungsi kendala dibalik.
3. Tujuan diubah dari minimasi (maksimasi) dalam primal menjadi maksimasi
(minimasi) dalam dual.
4. Setiap kolom pada primal berhubungan dengan suatu baris (fungsi
kendala) dalam dual. Sehingga banyaknya fungsi kendala dua sama dengan
banyaknya variabel primal.
5. Setiap baris (fungsi kendala) pada rpimal berhubungan dengan suatu
kolom dalam dual. Sehingga ada satu variabel dual untuk setiap kendala
primal.
6. Bentuk dual dari dual adalah bentuk primal.

1.

1. Masalah Primal Dual

2.

Masalah Primal Dual Simetrik

Suatu LP dikatakan berbentuk simetrik jika semua variabel dibatasi bernilai

nonnegatif dan semua kendala

berupa pertidaksamaan (dalam masalah

maksimasi pertidaksamaannya harus dalam bentuk < , sementara dalam

minimasi mereka harus > ).
Bentuk umum masalah primal dual yang simetrik
adalah:

Primal:
Maksimalkan

Z = c1 X1 + c2 X2 + . . + cn Xn

Dgn syarat a11 X1 + a12 X2 + . . + a1n Xn < b1

a21 X1 + a22 X2 + . . + a2n Xn < b2

am1 X1 + am2 X2 + . . + amn Xn < bm

X1 > 0,

X2 > 0, . . . , Xn > 0.

Dual:
Minimumkan W = b1 Y1 + b2 Y2 + . . + bm Ym
Dgn syarat a11 Y1 + a21 Y2 + . . + am1 Ym < c1
a12 Y1 + a22 Y2 + . . + am2 Ym < c2

a1n Y1 + a2n Y2 + . . + amn Ym < cn

Y1 > 0, Y2 > 0, . . . , Ym > 0.

Dalam bentuk matriks masalah primal dual akan menjadi sbb.

Primal:

Maksimumkan Z = cX

Dengan syarat AX < b

X >0

Dual

Minimumkan W = Y b

Dengan syarat Y A > c

Y>0

Dimana A adalah suatu matriks m x n,

b adalah vektor kolom m x 1,
c adalah vektor baris 1 x n,
X adalah vektor kolom n x 1, dan
Y adalah vektor baris 1 x m.
Aturan umum untuk menuliskan bentuk dual suatu LP yang simetrik
diringkas sebagai berikut:
1) Misalkan sebuah variabel dual (nonnegatif) untuk setiap kendala primal.
2) Vektor baris koefisien fungsi tujuan primal diubah menjadi vektor kolom
konstan Sisi kanan dual.
3) Vektor kolom sisi kanan primal diubah menjadi vektor baris koefisien fungsi
tujuan dual.
4) Transpose koefisien matriks kendala primal menjadi koefisien matriks
kendala dual.
5) Balik arah pertidaksamaan kendala.
6) Balik arah optimisasi, ubah minimum menjadi maksimum dan sebaliknya.

Beberapa teori mengenai dualitas.

1) Teori Weak duality Theorem
Misalkan suatu bentuk primal dual simetrik sbb.

Maks Z = cX

dan

Min W = Yb

Dengan syarat:
AX < b

YA > c

X>0

Y>0

Nilai fungsi tujuan masalah minimasi (dual) untuk setiap solusi yang layak
selalu lebih besar atau sama dengan masalah maksimasi (primal)-nya
Beberapa Hal yang diperoleh dari Weak Duality Theorem
(i) Nilai fungsi tujuan masalah maksimasi (primal) untuk setiap solusi layak
adalah batas bawah dari nilai minimum fungsi tujuan masalah dual.
(ii) Nilai fungsi tujuan masalah minimasi (dual) untuk setiap solusi layak
adalah batas atas dari nilai maksimum fungsi tujuan masalah primal.
(iii). Jika masalah primal adalah layak dan nilai tujuannya tak terbatas, maka
masalah dualnya tidak akan memiliki suatu solusi layak, atau
(iv). Jika masalah primal adalah layak dan dual tak layak, maka primal tak
terbatas
(v). Jika masalah dual adalah layak dan tak terbatas, maka masalah primal
adalah tak layak, atau

(vi). Jika masalah dual adalah layak dan primal tak layak, maka dual adalah
tak terbatas.
2) Optimality Criterion Theorem
Jika terdapat solusi layak Xo dan Yo pada bentuk primal dual simetrik
sedemikian rupa sehingga nlai-nilai fungsi tujuan yang berhubungan adalah
sama,maka solusi layak ini adalah solusi optimum terhadap

masalah

tersebut.
3) Main Duality Theorem
Jika baik masalah primal maupun dual adalah layak, maka keduanya
memiliki solusi sedemikian rupa sehingga nilai optimum fungsi tujuannya
adalah sama.

4) Complementary Slackness Theorem

Kondisi complementary slackness dapat dinyatakan sbb.
1.

Jika suatu variabel primal X1 bernilai positif maka kendala dual yang
O

berhubungan akan dipenuhi sebagai suatu persamaan pada keadaan

optimum (variabel slack atau surplus pada kendala dual = 0)
2.

Jika suatu kendala primal berupa pertidaksamaan murni pada keadaan

optimum (variabel slack atau surplus pada keadaan primal > 0), maka
variabel dual yang berhubungan Y1 harus sama dengan nol
O

pada

keadaan optimum.
3.

Jika suatu variabel Y1 dual bernilai positif, maka kendala primal yang
O

berhubungan akan memenuhi sebagai suatu persamaan pada keadaan

optimum (variabel slack atau surplus pada kendala primal = 0).
4.

Jika suatu kendala dual berupa pertidaksamaan murni (variabel slack

atau surplus pada kendala dual > 0)

maka variabel primal yang

berhubungan Xj harus sama dengan nol pada keadaan optimum.

O

IV.2. Masalah Primal Dual Asimetrik

Tidak semua LP berbentuk simetrik artinya ada yang asimetrik.
Contoh:
Maksimumkan Z = 4X1 + 5X2
Dengan syarat

3X1 + 2X2 < 20

4X1 3X2 > 10

X1 + X2 = 5
X1 > 0 dan X2 tak terbatas.

Coba ubah ke bentuk yang simetris!

Intinya semua fungsi kendala diubah ke < (karena primalnya adalah
maksimasi) dan semua variabel nonnegatif.
Langkah-langkah:
1) Kendalah pertidaksamaan kedua dikalikan -1.
2) Kendala persamaan ketiga diganti dengan suatu pasangan
pertidaksamaan

X1 + X2 < 5 dan X1 + X2 > 5

3) Variabel tak terbatas X2 diganti dengan selisih dua variabel nonnegatif X3

dan X4.
Jadi bentuk simetris masalah primal menjadi:
Maksimalkan Z = 4X1 + 5X3 5X4
Dengan syarat 3X1 + 2X3 2X4 < 20

-4X1 + 3X3 + 3X4 < 10

X1 +

X3 X4 < 5

-X1

X3 + X4 < -5

X1 > 0, X3 > 0, dan X4 > 0.

Bentuk dual simetrisnya adalah

Minimumkan W = 20U1 10U2 + 5U3 5U4
Dgn syarat 3U1 4U2 + U3 U4 > 4
2U1 + 3U2 + U3 U4 > 5
-2U1 + 3U2 U3 + U4 > -5
U1 > 0, U2 > 0, U3 > 0, U4 > 0.

Bila bentuk dual dibandingkan dengan bentuk primal yang belum

disimetriskan, maka terlihat bahwa tak ada ciri-ciri hubungan primal dual
seperti yang telah disebutkan di depan terpenuhi. Koefisien matriks kendala
dual bukan transpose dari kendala primal, vektor sisi kanan primal bukan
merupakan koefisien fungsi tujuan dual dan sebaliknya
Kemudian, misalkan Y1 = U1, Y2 = -U2, Y3 = U3 U4 dan dua
pertidaksamaan

terakhir

pada

bentuk

dual

diganti

dengan

sebuah

persamaan, sehingga diperoleh suatu masalah dual yang telah dimodifikasi

sbb.
Minimumkan

W = 20Y1 + 10Y2 + 5Y3

Dengan syarat 3Y1 + 4Y2 + Y3 > 4

2Y1 3Y2 + Y3 = 5
Y1 < 0, Y2 < 0, dan Y3 tak terbatas.
Bila bentuk dual yang telah dimodifikasi dibandingkan dengan bentuk primal
yang belum disimetriskan, terlihat bahwa semua ciri penting hubungan
primal dual terpenuhi, kecuali arah pertidaksamaan kendala, dan tanda
pembatas variabel. Sehingga untuk setiap LP (simetris atau tidak) bentuk
dual selalu memenuhi ciri-ciri sbb.
1) Elemen matriks kendala bentuk dual adalah transpose elemen kendala
primal,
2) Koefisien fungsi tujuan dual adalah vektor sisi kanan primal,
3) Vektor sisi kanan dual adalah koefisien fungsi tujuan primal,
4) Jika primal adalah masalah maksimas, maka dual menjadi masalah
minimasi dan sebaliknya.
Tabel berikut menyajikan hubungan primal-dual untuk semua masalah LP, di
mana bentuk primal berupa masalah maksimasi (I). Jika bentuk primal adalah
masalah
Minimasi (II), maka hubungan primal-dual berubah.
Tabel
Primal

Dual

A elemen matriks kendala

Transpose elemen matriks

b vektor sisi kanan

Koefisien fungsi tujuan

c koefisien fungsi tujuan

Vektor sisi kanan

Kendala ke-i berupa persamaan

Variabel dual Yi tak terbatas

Xj tak terbats

1.

Kendala ke-j berupa persamaan

Maksimisasi

Minimisasi

Kendala ke-i jenis <

Variabel dual Yi > 0

Kendala ke-i jenis >

Variabel dual Yi < 0

Xj > 0

Kendala ke-j jenis >

Xj < 0

Kendala ke-j jenis <

1.

Minimisasi Maksimisasi

Kendala ke-i jenis <

Variabel dual Yi < 0

Kendala ke-i jenis >

Variabel dual Yi > 0

Xj > 0

Kendala ke-j jenis <

Xj < 0

Kendala ke-j jenis >

Contoh
1.

Primal :

Maksimumkan Z = X1 + 4X2 + 3X3

Dengan syarat 2X1 + 3X2 5X3 < 2
3X1

X2 + 6X3 > 1

X1 + X2 + X3 = 4
X1 > 0, X2 < 0, dan X3 tak terbatas.
Dual : Minimumkan W = 2Y1 + Y2 + 4Y3
Dgn syarat 2Y1 + 3Y2 + Y3 > 1
3Y1

Y2 +

Y3 < 4

-5Y1 + 6Y2 + Y3 = 3
Y1 > 0, Y2 < 0, dan Y3 tak terbatas.
2. Primal : Maksimumkan Z = 2X1 + X2 X3
Dgn syarat X1 + X2 X3 = 1
X1 X2 + X3 > 2
X2 + X3 < 3
X1 > 0, X2 < 0, X3 tak terbatas.

Dual : Minimumkan W = Y1 + 2Y2 + 3Y3

Dgn syarat Y1 + Y2
Y1

<2

Y2 + Y3 > 1

-Y1 + Y2 + Y3 = -1
Y1 tak terbatas, Y2 > 0, dan Y3 < 0.

3. Mencari solusi Optimum Bentuk Dual

Setiap LP akan selalu dapat dipecahkan menggunakan metode simpleks,
untuk itu metode ini akan selalu dapat diterapkan baik pada bentuk primal
maupun dual-nya.
Pada Main duality theorem dinyatakan bahwa suatu solusi optimum terhadap
bentuk dual dapat diperoleh melalui solusi primal dan sebaliknya.
Contoh: Maksimumkan Z = 5X1 + 12X2 + 4X3
Dgn syarat
2X1

X1 + 2X2 + X3 < 5

X2 + 3X3 = 2

X1 > 0, X2 > 0, dan X3 > 0.

Bila kita selesaikan dengan metode simpleks, maka diperlukan variabel slack
dan artificial variabel A. Untuk itu pada tabel awal akan diperoleh nilai
variabel basis untuk S = 5 dan A = 2. Pada iterasi terakhir akan diperoleh
tabel simpleks sbb.
Basis

X1

X2

X3

3/5

X2

-1/5

X1

7/5

29/5 -2/5 + M
2/5
1/5

-1/5
2/5

Solusi
28 1/5
8/5
9/5

Ingat bahwa variabel basis awal adalah variabel slack S dan artificial variabel
A, sementara kedua variabel basis optimum adalah variabel riil.
Sekarang kita akan pecahkan masalah dualnya!
Bentuk dualnya adalah:

Minimumkan W = 5Y1 + 2Y2

Dengan syarat Y1 + 2Y2 > 5
2Y1

Y2 > 12

Y1 + 3Y2 > 4
Y1 > 0 dan Y2 tak terbatas.
Karena Y2 tak terbatas untuk itu kita harus ganti Y2 dengan Y2 Y dimana
baik Y2 maupun Y kedua-duanya > 0. Jika variabel surplus S1, S2, dan S3
dikurangkan dari ketiga kendala dan menambahkan artificial variabel A1, A2,
dan A3, maka variabel basis awal adalah A1 = 5, A2 = 12, dan A3 = 4. Untuk
itu tabel simpleks optimumnya menjadi:
Basis Y1 Y2 Y S1 S2 S3

A1

A2

A3

Sol

-9/5 -8/5 0 9/5 M 8/5M -M 28 1/5

S3

-7/5 1/5 1

Y 0 -1
Y1

1
0

2/5 -1/5 0
0

-1/5 -2/5 0

7/5
-2/5
1/5

-1/5
1/5
2/5

-1

3/5

2/5
0

29/5

Variabel basis pada solusi awal bentuk primal adalah S dan A. Variabel dual
yang berhubungan dengan persamaan kendala primal yang mengandung S
dan A adalah Y1 dan Y2.
Sekarang perhatikan koefisien persamaan Z pada tabel optimum primal.
Hasilnya adalah:
Variabel basis awal bentuk primal

Koefisien persamaan Z
pada optimum primal

29/5

-2/5 + M

Variabel dual yang berhubungan

Y1

Y2

Jika M diabaikan, koefisien persamaan Z adalah 29/5 dan -2/5 yang langsung
memberikan solusi optimum pada masalah dual, yaitu nilai optimum Y1 =
29/5 dan Y2 = -2/5 (= Y2 Y = 0 2/5) yang sama dengan hasil
pemecahan bentuk dual dengan metode simpleks. Ini bukanlah suatu
kebetulan, tetapi berlaku umum. Suatu pengamatan terhadap variabel basis
pada solusi awal (A1, A2, dan A3) memberi informasi sbb.
Var basis awal bentuk dual

A1

A2

A3

Koefisien persamaan Z
pada optimum dual

9/5 M 8/5 M 0 M

Variabel primal yang berhubungan

X1

X2

X3

Jika M diabaikan, maka hasil dari koefisien persamaan Z secara langsung

memberi solusi optimum primal X1 = 9/5, X2 = 8/5, dan X3 = 0 yang sama
dengan penyelesaian bentuk primal menggunakan metode simpleks.
Berdasakan tabel simpleks optimum bentuk primal, solusi optimum bentuk
dual dapat juga dihitung melalui rumus sbb.
Misalkan terdapat hubungan primal dual sbb.
Minimumkan Z = cX

dan Maksimumkan W = Yb

Dengan syarat AX = b

dengan syarat YA < c

X>0

Y>0

Maka solusi optimum masalah primal dan dual yang dioeroleh melalui
penerapan revised simplex-method adalah:
Z

= cB b
B

-1

Dimana c adalah vector profit atau biaya variabel basis

B

bentuk primal.

optimum

B adalah matriks variabel basis optimum bentuk primal

[ Pj ] , dimana Pj adalah kolom ke-j matriks A
C B adalah vektor simpleks multiplier.
B

-1

Contoh: Maksimumkan Z = 5X1 + 12X2 + 4X3

Dengan syarat
2X1

X1 + 2X2 + X3 < 5

X2 + 3X3 = 2

X1 > 0, X2 > 0, dan X3 > 0

Bentuk dualnya menjadi:
Minimumkan

W = 5Y1 + 2Y2

Dengan syarat
2Y1

Y1 + 2Y2

>5

Y2 > 12

Y1 + 3Y2 > 4
Y1 > 0 dan Y2 tak terbatas.
Menggunakan metode simpleks, solusi terhadap masalah primal telah
diperoleh yaitu X1 = 9/5, X2 = 8/5, dan Z = 28 1/5. Karena X1 dan X2
merupakan variabel basis oprtimum bentuk primal, maka matriks basis
optimumnya adalah:

Terlihat bahwa Y1 = 29/5 dan Y2 = -2/5 memenuhi kendala dual dan nilai
fungsi tujuan dual adalah
W = 5(29/5) + 2(-2/5) = 28 1/5

Jadi kesimpulannya, bahwa suatu solusi optimum primal (dual) juga

merupakan solusi optimum masalah dual (primal). Di samping kedua cara
yang telah dibicarakan, solusi optimum dual dapat dihitung dengan
menggunakan teori complementary slackness.

1.

METODE DUAL SIMPLEKS

Metode ini sering disebut juga dual simplex algorithm adalah suatu prosedur
perhitungan yang memberikan suatu solusi layak optimum, meskipun solusi
awalnya tidak layak. Pertama kali disusun oleh LEMKE. Banyak digunakan
dalam post optimally analysis.
Contoh:

Minimumkan Z = 4X1 + 2X2

Dengan syarat 3X1 + X2 > 27

X1 + X2 > 21
X1 + 2X2 > 30
X1 > 0 dan X2 > 0
Langkah pertama adalah mengubah semua fungsi kendala beruba pertidak
samaan dengan tanda > 0 menjadi < 0 agar tidak menggunakan artificial
variabel, selanjutnya tambahkan slack variabel. Diperoleh:

Minimumkan

Z = 4X1 + 2X2

Dengan syarat -3X1 X2 + S1

-X1 X2

+ S2

-X1 2X2

= -27

= -21
+ S3 = -30

X1 > 0, X2 > 0, S1 > 0, S2 > 0, dan S3 > 0.

Jika bentuk baku di atas diekspresikan sebagai suatu tabel simpleks awal,
maka terlihat bahwa variabel slack (S1, S2, dan S3) tidak memberikan solusi
awal layak. Karena ini merupakan masalah minimasi sementara semua
koefisien pada persamaan Z adalah < 0, maka solusi awal S1 = -27, S2 =
-21, dan S3 = -30 adalah optimum tetapi tidak layak. Ini merupakan ciri khas
dari masalah yang dapat diselesaikan dengan metode dual simpleks.
Tabel solusi awal optimum tapi tak layak adalah:
Basis X1 X2

S1

-4

-2

S2

S3

Solusi

S1

-3

-1

-27

S2

-1

-1

-21

S3

-1 (-2)

-30

Seperti dalam metode simpleks, metode ini didasakan pada optimally and
feasibility condition.
Setelah memilih entering and leaving variable, metode Gauss Jordan
(operasi baris) diterapkan seperti biasa untuk memperoleh solusi berikutnya.
S3 = -30 sebagai leaving kemudian untuk entering variabel, diambil rasionya
pada tabel berikut:

Basis

X1

-4

-2

S3

-1

-2

Rasio

X2

S1

S2

0
0

S3

Untuk itu sebagai entering variabel adalah X2 karena rasionya terkecil yaitu
1. Dengan Operasi baris seperti biasa akan didapat:
Tabel
Basis

X1

-3

S1

(-2,5)

S2

-1/2

X2

1/2

X2
0

S1
0

S2

S3

Solusi

-1

30

1
0

-1/2
-1/2
-1/2

-12
-6
15

Solusi baru masih optimum tetapi tidak layak (S1 = -12 dan S2 = -6).
Kemudian S1 dipilih sebagai leaving variable dan X1 sebagai entering
variable. Ini memberikan iterasi sbb.
Tabel
Basis

X1

X2

X1

S2

S1

-1,2
-0,4
-0,2

S2
0

S3
-0,4

2
1

(-0,4)

Solusi
44,4
4,8
-3,6

X2

-0,2

-0,6

12,6

Pada iterasi kedua belum diperoleh solusi layak (S2 = -3,6). Karena S2
adalah satu-satunya yang bernilai negatif, dengan ssendirinya ia menjadi
leaving variabel dan S3 sebagai entering variabel. Didapat tabel berikut:
Tabel
Basis
Z

X1
0

X2
0

X1

S3

X2

S1
-1
-1/2
1/2
1/2

S2
-1
1/2
-2,5
-1,5

S3
0

Solusi
48

18

Optimum dan Layak dengan nilai fungsi tujuan adalah 48.