TEORI DUALITAS

A.    Pendahuluan

Meminjam pengertian dari buku Wayne Winston dualitas adalah “ Associated with any LP is another LP, called the dual.” Baik dari sudut pandang teori maupun praktik, teori dualitas merupakan salah satu konsep yang sangat penting dan menarik dalam linear programing(LP). Istilah dualitas menunjuk pada kenyataan bahwa setiap LP terdiri dari dua bentuk. Bentuk pertama atau bentuk asli dinamakan primal, sementara bentuk yang kedua yang berhubungan dinamakan dual demikian sehingga suatu 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 konsep duality, mungkin cara yang paling mudahnya dengan memberikan contoh, agar lebih diketahui antara yang primal dan dual berikut contohnya

Misalnya saja tentang masalah diet

Kandungan

Makanan tiruan

Daging                        Sayur

Kebutuhan

Minimum/hari

MineralVitamin

Harga per unit

 

2

3

3

4

2

2,5

40

50

 

Masalahnya adalah menentukan biaya pembeliaan sejumlah daging dan sayuran demikian sehingga kebutuhan minimum per hari akan mineral dan vitamin terpenuhi. Untuk merumuskanya  berikut model matematikanya:

Misalkan Xj(j=1,2) ada;ah jumlah unit daging dan sayuran yang di beli.

Min    Z =3X1 + 2,5X2

s.t        :2X1 + 4X2 ≥ 40

3X1 + 2X2 ≥ 50

X1,X2     ≥ 0

Sekarang, kita pandang dari sudut yang berbeda yang masih berhubungan dengan masalah pertama (bentuk primal) , kali ini misalkan ada  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 vitaminya. Masalah yang dihadapi dealer adalah menetapkan harga jual mineral dan vitamin per unit yang memaksimumkan demikian sehingga harga daging dan sayur tiruan tidak melebihi harga pasar yang ada.

Untuk merumuskan masalah ini  kita menggunakan model berikut

Misalkan dealer memutuskan

Y1 : harga daging per unit

Y2 : harga sayur per  unit

Max  W = 40Y1 + 50 Y2

s.t : 2Y1 + 3Y2 ≤ 3

4Y1 + 2Y2 ≤ 2,5

Y1,Y2          ≥ 0 (karena tidak mungkin negatif)

Bentuk LP yang terakhir ini dinamakan bentuk dual, Y1 dan Y2 dinamakan variabel dual.

Bila masalah primal dibandingkan dengan masalah dual, terlihat beberapa hubungan seperti berikut:

  1. Koefisien fungsi tujuan masalah primal menjadi konstan sisi kanan masalah dual, sebaliknya, konstan sisi kanan primal menjadi koefisien fungsi tujuan dual.
  2. Tanda pertidaksamaan dibalik
  3. Tujuan diubah dari minimasi (maksimasi) dalam primal menjadi maksimasi(minimasi) dalam dual
  4. Setiap kolom pada primal berhubungan dengan suatu baris (kendala) dalam dual. Sehingga banyaknya banyaknya kendala dual sama dengan banyaknya variabel primal.
  5.  Setiap baris (kendala) pada primal berhubungan dengann suatu kolom dalam dual. Sehingga ada satu variabel dual untuk setiap kendala primal
  6. Bentuk dual dari dual adalah bentuk primal.

 

 

 

 

B.     Mencari solusi optimum bentuk dual

Karena setiap LP dapat dipecahkan dengan metode simpleks, maka metode itu dapat diterapkan baik pada masalah primal maupun dual. Main duality theorem menyatakan bahwa suatu solusi optimum terhadap bentuk dual dapat diperoleh melalui solusi primal dan sebalikna. Contoh berikut akan menunjukan bagaimana pernyataan itu bekerja.

Max     Z = 5X1 +12X2 + 4X3

s.t : X1 + 2 X2+ X3 ≤ 5

2×1 – X2 + 3X3= 2

X1,X2          ≥ 0

Kemudian selesaikan dengan metode sipleks. Dalam hal ini dibutuhkan variabel slack S dan artificial variabel A.pada tabel simpleks awal diperoleh variabel basis S = 5 dan A = 2. Pada iterasi terakhir diperoleh tabel simpleks optimum seperti berikut :

Tabel simpleks primal

BV X1 X2 X3 S A solusi
ZX2

X1

00

1

101

0

3/5-1/5

7/5

29/52/5

1/5

-2/5 + M-1/5

2/5

28 1/58/5

9/5

 

Kita ketahui bahwa basis variable awal adalah variable slack S dan artificial variable A, sementara kedua variable basis optimum adalah variabel riel.

Sekarang masalah dual akan dipecahkan dengan metode simpleks. Bentuk dualnya adalah:

Max   W = 5Y1 + 2Y2

s.t : Y1 + 2Y2  ≥ 5

2Y2 – Y2   ≥ 12

Y1 + 3y2  ≥ 4

Y1 =0, Y2 tak terbatas

Karena Y2 tak terbatas, ia digantikan dengan Y2’-Y2” dimana Y2” dan Y2’  ≥ 0. Jika variable surplus S1,S2,S3 di kurangkan dari ketiga kendala dan menambahkan artificial variable A1,A2,A3, maka variable basis awal adalah A1 = 5, A2 = 12, A3 = 4. Kemudian tabel simpleks optimumnya adalah :

Tabel simpleks dual

BV Y1 Y2’ Y2” S1 S2 S3 A1 A2 A3 solusi
ZS3

Y”

Y1

00

0

1

00

-1

0

00

1

1

-9/5-7/5

2/5

-1/5

-8/51/5

-1/5

-2/5

01

0

0

9/5 M7/5

-2/5

1/5

 

8/5 M-1/5

1/5

2/5

-M-1

0

0

28 1/53/5

2/5

29/5

 

Pengamatan terhadap tabel optimum primal dan dual mengungkapkan hasil- hasil yang menarik. Variabel bebas pada solusi awal berbentuk 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

 Variabel basis awal bentuk primal                                 A                                           S
Koefisien persamaan Z pada optimum primal              29/5                                     -2/5 + MVariabel dual yang berhubungan                                   Y1                                          Y2

 

Jika M diabaikan, koefisien Z adalah 29/5 dan -2/5 yang langsung memberikan solusi optimum masalah dual. Yaitu, nilai optimum Y1= 29/5 Y2= -2/5 (= Y2’-Y2” = 0- 2/5) yang sama dengan hasil pemecahan bentuk dual dengan simpleks.

Hasil diatas bukan bersifat kebetulan, tetapi berlaku umum. Suatu pengamatan serupa tehadap variabel basis pada solusi awal (A1,A2,A3) memberi informasi seperti berikut :

Variabel basis awal bentuk dual                                        A1                   A2                      A3
Koefisien persamaan Z pada optimum dual                  9/5 -M            8/5 -M                   0 – MVariabel dual yang berhubungan                                      X1                      X2                   X3

 

Jika M diabaikan , maka hasil dari koefisien persamaan Z secara langsung memberi solusi optimal primal X1= 9/5, X2= 8/5, X3= 0, yang sama dengan penyelesaian bentuk primal metode simpleks.

Berdasarkan simpleks optimum bentuk primal, solusi optimum bentuk dual dapat juga dihitung melalui rumus seperti berikut:

Misalkan terdapat hubungan primal-dual sebagai berikut :

Minimumkan     Z =  cX                     dan                  Maksimumkan W =  Yb

Dengan syarat AX =  b                                               Dengan syarat  YA ≤ c

X ≥ 0                                                             Y   ≥ 0

Maka solusii optimum masalah primal dan dual yang diperoleh melalui penerapan revised simplex method adalah :

Z = W = Cb B-1 b

Keterangan :

Cb  : vektor profit atau biaya variabel basis optimum bentuk primal

B    : matriks variabel basis optimum bentuk primal

[Pj] dimana pj adalah kolom ke j matriks A

B-1  : vector simpleks multimplier

Contoh dapat membantu penjelasanya dari rumus diatas.

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

S.t: x1 + 2X2 + X3 ≤5

2X1 – X2 + 3X3      =2

X1,X2,X3 ≥0

Dual: Minimumkan       W=  5Y1+2Y2

S.t : Y1 + 2Y2  ≥ 5

2Y1  – Y2         ≥ 4

Y1≥ 0 , Y2 tak terbatas

Melalui metode simpleks , solusi terhadap masalh primal telah diperoleh yaitu X1= 9/5,X2= 8/5 dan Z= 28 1/5. Karena X1dan X2 merupakan variabel basis optimum bentuk primal, maka matriks basis optimumnya adalah:

B  =[p1 p2] =

Optimum simpleks multiplier-nya adalah :

Cb B-1 = [5  12] = = [29/5  -2/5]

Terlihat bahwa Y1= 29/5 , Y2= -2/5 memenuhi kendala dual dan fungsi tujuan dual adalah

W = 5(29/5  +  2(-2/5) = 28 1/5

Kesimpulan terpenting dari contoh diatas adalah bahwa suatu solusi optimum primal (dual) juga merupakan solusi optimum masalah dual(primal) . disamping itu kedua cara yang telah dibicarakan, solusi optimum dual dapat dihitung dengan menggunakan teori complentary slackness.

C.    Penafsiran solusi dual

Dari segi ekonomi , solusi optimum, bentuk dual dapat ditafsirkan sebagai sumbangan per unit kendala sumberdaya (shadow price). Brdasarkan main duality theorem nilai optimum fungsi tujuan primal dan dual adalah sama. Jika X0 dan Y0 adalah solusi optimumnya, maka    Z = c X0 = Y0 b =W. Dengan kata lain, nilai optimum program linear ( primal atau dual) dituliskan sebagai

Z = Y01 b1+ Y02 b2 +….+ Ym0 bm

Dimana b1,b2,… menunjukan jumlah sumberdaya 1,2,…m yang terbatas dan Y01,Y02,.. Ym0 adalah nilai optimum variabel dual. Misalkan dianggap bahwa jumlah sumberdaya ke 1 (b1) dapat diubah. Kemudian, untuk perubahan nilai b1 yang sangat kecil, katakan ∆b1, perubahan neto nilai tujuan Z adalah Y01 (∆b1). Perubahan neto nilai optimum karena kenaikan jumlah sumberdaya dinamakan shadow price sumberdaya yang bersangkutan. Ini dapat digunakan untuk menentukan apakah menguntungkan untuk mendapatkan tambahan sumberdaya pada harga pasar.

D.    Keuntungan perhitungan bentuk dual

Telah ditunjukan bahwa setiap masalah LP dapat dipecahkan dengan merumuskan baik dalam bentuk primal maupun dual. Karena solusi satu masalah selalu dapat diperoleh dari solusi bentuk dualnya, maka tidak perlu merumuskan kedua bentuk. Apakah suatu masalah seharusnya dirumuskan dalam bentuk primal atau dual, tergantung sepenuhnya pada kemudahan perhitungan dalam menyelesaikan dua jenis masalah itu.

Namun, tak dapat dikatakan bahwa satu jenis masalah adalah lebih mudah untuk diselesaikan dibanding yang lain tanpa meneliti struktur masalahnya. Terdapat kesepakatan bahwa sejumlah besar kendala membuat masalah perhitungan yang lebih gawat daribada sejumlah besar variabel. Ini karena jumlah kendala menentukan banyaknya vektor basis dalam solusi yang pada giliranya menentukan ukuran matriks basis invers.

Sehingga, jika suatu masalah demikian hingga bentuk primalnya memilikia sejumlah besar kendala sementara variabelnya hanya sedikit, masalah tersebut dapat diselesaikan dengan lebih efisien jika dirumuskan dalam bentuk dual.

 

 

 

Daftar pustaka,

Mulyono ,Sri S.E.,M.Sc. (2007). Riset Operasi Edisi Revisi, Lembaga Penerbit  Fakultas Ekonomi Universitas Indonesia

Winston, Wayne. (2003).Operations Research Applications and Algorithms 4th. Edition,

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s