Operation Research: Teori Dualitas

 

BAB I

PENDAHULUAN

A.   Latar Belakang

Operation research merupakan metode yang mencakup berbagai teknik untuk memberikan pengaruh pada pengambilan keputusan. Dapat dikatakan metode tersebut menjadi salah satu dasar pengambilan keputusan selain dari faktor-faktor kualitatif. Pada Operation research memiliki berbagai macam pembahsan yang sangat penting untuk diketahu. Salah satunya adalah teori dualitas.

Teori dualitas merupakan salah satu konsep program linear yang penting dan menarik ditinjau dari segi teori dan praktisnya. Ide dasar yang melatar belakangi teori ini adalah bahwa setiap persoalan program linear mempunyai suatu program linear lain yang saling berkaitan yang disebut dual, sedemikian sehingga solusi pada persoalan semula (yang disebut primal) juga memberikan solusi pada dualnya. Sangat penting untuk mengetahui lebih jauh mengenai teori dualitas, oleh karena itu akan dibahas secara mendalam di makalah ini.

 

B.   Rumusan Masalah

1. Apa pengertian teori dualitas?
2. Bagaimana sifat dasar teori dualitas?
3. Bagaimana kaidah transformasi untuk memperoleh nilai dual?
4. Bagaimana keunggulan dual?
5. Bagaiamana dualitas dalam interpretasi ekonomi?

 

C.   Tujuan

1. Mengetahui pengertian teori dualitas.
2. Mengetahui sifat dasar teori dualitas.
3. Mengetahui kaidah transformasi untuk memperoleh nilai dual.
4. Mengetahui keunggulan dual.
5. Mengetahui dualitas dalam interpretasi ekonomi.

BAB II

PEMBAHASAN

A.      Pengertian Teori Dualitas

Teori dualitas merupakan salah satu konsep program linier yang penting dan menarik ditinjau dari segi teori dan praktisnya. Ide dasar yang melatar belakangi teori ini adalah bahwa setiap persoalan program linier mempunyai suatu program linier lain yang saling berkaitan yang disebut dual, sedemikiansehingga solusi pada persoalan semula (yang disebut primal) juga memberi solusi pada dualnya.[1]

Pendefenisian dual ini akan tergantung pada jenis pembatas, tanda-tanda variabel, dan bentuk optimasi dari persoalan primalnya. Akan tetapi, karena setiap persoalan program linier harus dibuat dalam bentuk standar lebih dahu- lu sebelum metodenya dipecahkan, maka pendefinisian dibawah ini akan secara otomatis meliput ketiga hal diatas.

Bentuk umum masalah primal dual adalah sebagai berikut:

Primal:

Maksimumkan: z = c₁x₁ +c₂x₂ +...+c_nx_n

Kendala:

a₁₁x₁ +a₁₂x₂ +···+a_1nx_n 6 b₁

a₂₁x₁ +a₂₂x₂ +···+a_2nx_n 6 b₂

... 

a_m1x₁ +a_m2x₂ +···+a_mnx_n 6b_m

x₁,x₂,...,x_n > 0

Dual;

Minimumkan: w =b₁y₁ +b₂y₂ +...+b_my_m

Kendala

a₁₁y₁ +a₁₂y₂ +···+a_1ny_m 6 c₁

a₂₁y₁ +a₂₂y₂ +···+a_2ny_m 6 c₂

... 

a_m1y₁ +a_m2y₂ +···+a_mny_m 6c_n

y₁,y₂,...,y_n > 0

Jika membandingkan kedua persoalan diatas  ternyata terdapat korespondensi antara primal dengan dual sebagai berikut:

1. Koefisien fungsi tujuan primal menjadi konstanta ruas kanan bagi dual, sedangkan konstanta ruas kanan primal menjadi kosefisien fungsi tujuan bagi
   dual;
2. Untuk tiap pembatas primal ada satu variabel dual dan untuk setiap variabel
   primal ada satu pembatas dual;
3. Tanda ketidaksamaan pada pembatas akan bergantung pada fungsi tujuan-
   nya;
4. Fungsi tujuan berubah bentuk (maksimisasi menjadi minimasi dan seba-
   liknya);
5. Setiap kolom pada primal berkorespondensi dengan baris (pembatas) pada
   dual;
6. Setiap baris (pembatas) pada primal berkorespondensi dengan kolom pada
   dual;
7. Dual dari dual adalah primal;

Hubungan antara primal dual nilai tujuan dalam suatu pasangan masalah primal dan dual harus memenuhi hubungan sebagai berikut ini:

1.          Untuk setiap pasangan pemecahan primal dual yang layak;

Nilai tujuan dalam masalah maksimisasi ≤ Nilai tujuan dalam masalah minimasi

2.          Di pemecahan optimum untuk kedua masalah;

Nilai tujuan dalam masalah maksimasi = Nilai tujuan dalam masalah mini- masi.

Untuk menjelaskan hubungan antara primal dan dual, perhatikan ilustrasi berikut ini:

Primal

Minimumkan z = 16x₁ +30x₂ +36x₃

Kendala:

2x₁ +3x₂ +2x₃ = 60

2x₁ +5x₂ +3x₃ = 80

x₁,x₂,x₃ = 0

Soal ini diselesaikan melalui penyelesaian dualnya, yakni:

Maksimumkan w = 60y₁ +80y₂

Kendala:

2y₁ +2y₂ = 16

3y₁ +5y₂ = 30

2y₁ +3y₂ = 36

y₁,y₂,y₃ = 0

Dengan menggunakan metode simpleks solusi dari permasalahan ini adalah:

w_max = 540 untuk y₁ = 5 unit, y₂ = 3 unit, t₃ = 17 unit, yakni bahan yang tidak terpakai dari konstrain ketiga, sedangkan t₁ =t₂ =0, dan untuk hasil untuk x₁ = 15,x₂ = 10, dan x₃ = 0.

Nilai variabel yang dipilih dari primal jika dimasukkan pada fungsi objektif harus cocok = 540.

z =16x₁ +30x₂ +36x₃

= 16(5)+30(10)+36(0) = 540

z_min = w_max

 

 

 

 

 

 

 

 

B.       Sifat Dasar

Dual mempunyai dua dalil yang bersifat sangat penting untuk linear programming.[2] Dalil tersebut berbunyi:

1.    Nilai optimal dari fungsi obyektif primal selalu sama dengan nilai
optimal dari fungsi obyektif dual, asalkan terdapat suatu penyelesaian optimal yang memungkinkan.

2.    Jika dalam penyelesaian optimal yang mungkin tersebut

a.    Suatu variabel keputusan dalam program primal mempunyai nilai bukan nol, variabel slack (atau surplus) yang berkaitan dalam
program dual harus mempunyai nilai optimal nol.

b.    Suatu variabel slack (atau surplus) dalam primal mempunyai nilai bukan nol, variabel keputusan yang berkaitan dalam program dual 
harus mempunyai nilai optimal nol. 

 

C.      Kaidah Transformasi untuk Memperoleh Nilai Dual

Menurut Dowling Perumusan dual dari suatu soal primal adalah sebagai berikut:[3]

1.    Arah optimisasi adalah terbalik. Maksimisasi dalam primal menjadi minimisasi dalam dual dan sebaliknya.

2.    Tanda pertidaksamaan dari kendala teknis adalah terbalik, tetapi ketidaknegatifan pada variabel-variabel keputusan (decision variables)
selalu dipertahankan.

3.    Baris matriks koefisien dari kendala dalam primal berganti tempat
(transpose) menjadi kolom untuk matriks koefisien dari kendala dalam
dual.

4.    Vektor baris dari koefisien dalam fungsi obyektif dalam primal berganti
tempat menjadi vektor kolom konstan untuk kendala dalam dual.

5.    Vektor kolom konstan dari kendala primal berganti tempat menjadi
vektor baris dari koefisien-koefisien untuk fungsi obyektif dalam dual.

6.    Variabel keputusan primal () digantikan oleh variabel keputusan dual ().
Pemecahan masalah dual juga diberikan oleh pemecahan masalah
primal, dan dalam beberapa kasus bisa terjadi lebih mudah memecahkan
masalah dual. Jumlah iterasi yang dibutuhkan dalam pemecahan masalah
simpleks bergantung pada jumlah baris variabel dalam tabel simpleks; jadi
jika m ˂ n, biasanya pemecahan masalah dual membutuhkan perhitungan yang lebih sedikit dan dengan demikian lebih mudah.

Menurut Weber kaitan antara pemecahan primal dan dual dapat disimpulkan sebagai berikut:[4]

1. Nilai fungsi sasaran dalam pemecahan masalah primal dan dual adalah sama.
2. Kriteria untuk variabel utama primal adalah pemecahan bagi variabel
   ‘slack’ dari dual.
3.  Kriteria untuk variabel ‘slack’ dari primal adalah pemecahan bagi
   variabel utama dari dual.
4. Pemecahan untuk variabel-variabel utama primal merupakan nilai
   negatif dari kriteria untuk variabel-variabel ‘slack’ dari dual.
5. Pemecahan untuk variabel-variabel ‘slack’ primal merupakan nilai
   negatif dari kriteria untuk variabel-variabel utama dari dual.

 

D.      Keunggulan Dual

Terdapat hubungan komplementer antara varibel-varibel keputusan dalam satu program dan variabel-variabel slack (atau surplus) di dalam program lainnya, penyelesaian untuk program yang satu memberikan penyelesaian untuk program lainnya.[5] Ini bermanfaat karena:

1. Hal ini memungkinkan penyelesaian soal minimisasi menurut
   maksimisasi, yang seringkali lebih mudah.
2. Untuk primal dengan tiga variabel keputusan, dual menyederhanakan
   program tersebut menjadi dua variabel keputusan, yang kemudian dapat
   digambarkan secara grafis.

Jadi masalah dual benar-benar simetris dengan masalah primal dan pemecahan dari salah satu masalah menghasilkan juga pemecahan dari masalah lain. Jika jumlah iterasi yang dibutuhkan untuk pemecahan simpleks bergantung pada jumlah baris dalam tabel simpleks, dual dapat dipecahkan dengan perhitungan yang lebih mudah daripada primal bila mana tabel simpleks dari dual mempunyai baris yang lebih sedikit dari pada tabel simpleks primal. Pemecahan masalah dual menghasilkan nilai-nilai yang sifatnya implisit, dihubungkan artifisial atau bayangan. Nilai-nilai ini mempunyaiarti ekonomis yang penting dalam beberapa aplikasi pemrogramanlinear, misalnya, dalam analisis alokasi sumber yang optimal.

 

E.       Interpretasi Ekonomi

Masalah primal melibatkan penetuan tingkat output yang menghasilkan laba maksimum untuk masing-masing perusahaanyang memproduksi beberapa produk. Dengan demikian, laba dibatasi oleh tersedianya sumber daya. Sumber daya merupakan nilai yang penting bagi perusahaan. Salah satu pendekatan untuk menentukan nilai dari sumber daya dengan menghitung biayanya, berikut upah buruh, alokasi bahan penolong, penyusutan, biaya pemeliharaan dan sebagainya.  Alternatif lainnya, mengakui bahwa laba bergantung pada sumber daya, beberapa bagian tertentu dari laba perusahaan dapat diperhitungkan setiap setiap sumber daya. Pemecahan problem dual melibatkan penentuan nilai-nilai yang diperhitungkan untuk sumber-sumber daya ini.[6]

Harga dual menunjukan kegunaan perunit sumber daya produksi. Biaya terkurangi   menunjukan   peningkatan   pengembalian   marjinal   atau pengurangan biaya perunit sumber daya yang dibutuhkan untuk membuat satu aktivitas PL lebih menguntungkan. Hubungan primal dual untuk menunjukan arti ekonomis sebenarnya dari harga dual dan biaya terkurangi. Interpretsasi harga dual dan biaya terkurangi akan dibuktikan sangat berguna pada dua aspek, yaitu:

1.    Menyediakan pemahaman fundamental model PL sebagai sistem
output-input ekonomis.

2.    Memungkinkan implementasai efisien analisis sensitivitas atau
postoptimal.

 

 

 

 

 

BAB III

PENUTUP

A.      Kesimpulan

Ditinjau dari teori praktek, maka dualitas merupakan konsep linear programming yang penting dan menarik. Ide dasar dari teori dualitas adalah bahwa setiap persoalan linear programming mempunyai suatu linear program yang berkaitan yang disebut “dual”. Sehingga solusi dari persoalan asli LP (Primal), juga memberikan solusi pada dualnya.

Secara sistematis, dualitas merupakan alat bantu masalah LP, yang secara langsung didefinisikan dari persoalan aslinya atau dari model LP Primal. Dalam kebanyakan perlakuan LP, dualitas sangat tergantung pada primal dalam hal tipe kendala, variabel keputusan dan kondisi optimum. Oleh karena itu dalam kenyataannya teori dualitas secara tegas tidak diharuskan penggunaannya. 

 

B.       Saran

Sebaiknya dalam penggunaan dualitas harus menggunakan data yang yang valid. Sehingga hasil yang didapat akan mendapatkan hasil yang tepat. Melalui hasil tersebut akan memberikan kemudahan dan membantu pekerjaan agar lebih mudah, serta terlaksana dengan baik.

DAFTAR PUSTAKA

 

Batara, Yan. 2017. Dualitas Untuk Persoalan Program Fraksional Multi-Objektif. Medan: Universitas Sumatra Utara.

 

Kakicina. 1999. Analisis Matematik. Jakarta: Erlangga.

 

Sugiarto. 1996. Matematika untuk Ekonomi. Jakarta: Erlangga.

 

 

 

 

---

[1] Yan Batara, Dualitas Untuk Persoalan Program Fraksional Multi-Objektif, (Medan: Universitas Sumatra Utara, 2017), hlm.17.

[2] Sugiarto, Matematika untuk Ekonomi, (Jakarta: Erlangga, 1996), hlm.4.

[3] Ibid… hlm.56.

[4] Kakicina, Analisis Matematik, (Jakarta: Erlangga, 1999), hlm.270.

[5] Sugiarto, Matematika untuk Ekonomi, (Jakarta: Erlangga, 1996), hlm.64.

[6] Kakicina, Analisis Matematik, (Jakarta: Erlangga, 1999), hlm.128.