Jumat, 02 Desember 2011

makalah teori dualitas

BAB II
PEMBAHASAN

Pengertian Teori Dualitas

Dari waktu ke waktu teknk linier programming mengalami perkembangan dan penyempurnaan. Dalam perjalannannya ditemukan berbagai kelebihan-kelebihan yang berguna dalam penenrapan teknik ini. Salah satunya dalah penemuan yang sangat besar manfatnya dalam dunia Linier Programming yang di gunakan sebagai alai analisa dan pengambilan keputusan. Teknik tersebut kita kenal dengan teori dualitas.
Menurut teori ini, setiap persolan yang dapat diformulasikan sebagai persoalan linier programming saling berhubungan timbale balik dengan persoalan linier programming yang lain yang merupakan “dual”nya. Dari hubungan timbale balik antara suatu persoalan linier programming yang asli (disebut primal) dengan pesrsoalan liner programming yang lain (dual), akan menimbulkan manfaat berupa memudahkan orang dalam mengkaji suatu perhitungan dalam linier programming.
Anggapan utama yang perlu ditekankan disini adalah bahwa masalah primal linier programming dinyatakan dalam bentuk-bentuk standar yaitu sebagai berikut :
Maksimumkan : Z = ∑_(j=1)^n▒C_j X_j
Dengan fungsi pembatas : ∑_(j=1)^n▒a_ij X_ij ≤ bi, untuk I = 1, 2, 3, …, n
Dan Xj ≥ 0 ; untuk j = 1, 2, 3, …, n

Apabila bentuk matematika diatas di masukan kedalam table simplex pertama akan tampak sebagai berikut :

Variabel dasar Z X1 X2………….Xn Xn+1 Xn+2…………….Xn+m Nilai kanan
Z (Z1-C1) (Z2-C2)……(Zn-Cn) Y1 Y2………………. Xm Y0

Kondisi optimal akan diperoleh :
Zj – Cj ≥ 0 ; untuk j = 1, 2, … n
Yi ≥ 0 ; untuk I = 1, 2, … m
Dengan menggantikan Zj, metode simplex lain dapat diinterprestasikan mencari nilai Yi di mana :
Yo = ∑_(i=1)^m▒〖b_i Y〗_i
Dengan pembatas :

∑_(i=1)^m▒〖a_ij Y_i 〗 ≥ C_j, untuk j = 1, 2, 3, …, n
Dimana Y_i ≥ 0 untuk I = 1, 2, 3, …, m

Bentuk di atas disebut sebgai bentuk dual dari permasalahan liner programming tersebut. Apabila kita konsekuen dengan uraian diatas, maka Y_i adalah pengganti Z_j dengan Y_(0 )adalah pengganti Z. Sehingga kita katakana bahwa tujuan dual adalah memaksimumkan nilai Y_0. Tetapi hal ini tidak benar, karena masalah dual di dekati dari arah yang berlawanan dengan masalah primal. Sehingga nilai Z yang maksimum pada permasalahan primal adalah sam dengan nilai Y_0 minimum pada dual. Dengan demikian, masalah dual dituliskan secara lengkap sebagai berikut :
Y_0 = ∑_(i=1)^m▒b_i Y_i
Dengan pembatas :

∑_(i=1)^m▒a_ij Y_i ≥ 0 C_j ; untuk j = 1,2,3, …, n
Dan Y_i ≥ 0 untuk i = 1, 2, 3, …, m

Secara lengkap antara permasalahan primal dan dual suatu persoaln linier programming dapat disusun dalam bentuk table primal dual sebagai berikut :







PRIMAL
Koefisien
X_1 X_2 X_3 NK

Y_1

Y_2

.

.

.

Y_m a_11 a_12 a_m

a_21 a_22 a_2n

. . .

. . .

. . .

a_m1 a_m2 a_mn
b_1

b_2

.

.

.

b_m
NK C_1 C_2 C_n



Tabel diatas menunjukan semua parameter linier programming (a_ij,b_i,dan e_j) dan bagaimana peranan ketiganya dalam embentuk primal dual. Bagian emndatar diperuntukan masalah primal sedangakan bagian yang tegak bagi masalah dualnya, sehingga secara umum hubungan anatara primal dual dapat dikatakan sebagai berikut :
Parameter daripada batasan-batasan primal (atau dual) merupakn koefisien variable dual (atau primal), dan
koefisien

2.2 Contoh Hubungan Primal Dual
Untuk lebih memudahkan pemahaman masalah hubungan primal dual ini, sebaiknya diambil sebuah contoh sederhana, yakni perusahaan genteng modern.
Masalah primalnya adalah :
Fungsi tujuan :
Maksimumkan Z = 10X_1 + 15X_2 + 20X_3
Dengan fungsi-fungsi pembatas :
10,7X_1+ 5X_2+ 2X_(3 ) ≤ 2.705
5,4X_1+ 10X_2+ 4X_3 ≤ 2.210
0,7X_1+ X_2+ 2X_3 ≤ 445
Dengan pengantian simbol-simbol yang dipakai pada table hubungan primal dual dengan angka-angka diatas maka akan diperoleh hubungan primal dual bagi permasalahan diatas sebai berikut :

X_1 X_2 X_3
Y_1

Y_2

Y_3 10,7

5,4

0,7 5

10

1 2

4

2 ≤ 2.705

≤ 2.210

≤ 445
10 15 20

Selanjutnya dengan melihat hubungan tersebut, maka persoalan diatas dapat disajikan dalam bentuk dual sebagai berikut :
Fungsi tujuan :
Y_0 = 2.705Y_1+ 2.210Y_2+ 445Y_3
Dengan fungsi-fungsi pembatas :
10,7Y_1+ 5,4Y_2+ 0,7Y_3 ≥ 10
5Y_1+ 10Y_2+ Y_3 ≥ 15
2Y_1+ 4Y_2+ 2Y_3 ≥ 20
Apabila masalah dual ini diselesaikan dengan metode simplex maka nilai-nilai Y optimal adalah : Y_1=0,0625 ; Y_2=0,59375 dan Y_3=8,75 dengan nilai Y_0=5,375. Angka-angka optimal tersebut tidak lain merupakan koefisien-koefisien slack variable pada baris tujuan table optimal masalah primal (lihat kembali table maksimal table perusahaan genteng modern).
Hubungan antara kedua table optimal (dual dan primal) dan suatu permasalahan linier programming ini dapat dipakai sebagai alat untuk memeriksa kembali hasil perhitungan simplex. Apabila ternyata nilai Y tidak sama dengan koefisien-koefisien slack variables maka tentu terdapat kesalahan dalam perhitungan-perhitungan yang harus segera diteliti kembali.

2.3 Beberapa Artian Ekonomis dalam Dual

Sebelum mengupas lebih lanjut berbagai artian ekonomis, sebaiknya ditinjau kembali arti simbul-simbul linier programming yang dipaki disini. Arti simbul-simbul tersebut adalah sebagai berikut (dalam bentuk standar) :
X_j : tingkat kegiatan dimana j = 1, 2, 3, …, n
C_j : laba satuan kegiatan ke j
Z : laba total dari seluruh kegiatan
b_i : jumlah sumber ke I yang tersedia, dimana i = 1, 2, 3, …, m
a_ij : jumlah sumber ke I yang dipakai oleh setiap satuan kegiatan ke j

Pada dual Y_i (i= 1, 2, 3, …, m) disebut sebagai variable dual yang merupakan kontribusi per satuan sumber ke-I terhadap laba. Seperti dikatakan di muka, nilai-nilai Y_(i )tampak pada baris tujuan table optimal primal. Pada contoh diatas dapat diartikan bahwa : setiap satuan masing-masing sumber Y_1,Y_2,dan Y_3 memberikan sumbangan terhadapa laba total sebesar Rp. 0,0625; Rp. 0,59375; Rp. 8,75; sehingga diperoleh laba total sebesar :
= 2.705(0,0625) + 2.210(0,59375) + 445(8,75)
= Rp.169,0625 + Rp. 1.132,1875 + Rp. 3.893,85
= Rp. 5.375,00

Sekali lagi, persamaan diatas dapat digunakan sebagai alat pemeriksaan kembali apakah yang diperolh pada table terakhir sudah betul. Bila terdapat ketidakcocokan pada persamaan diatas berarti telah terjadi kesalahan pad perhitungan-perhitungan yang telah dilakukan, dan perlu perbaikan.
Artian lain dari variable dual adalah bahwa Y_i adalah nilai mariginal sumber i. Nilai akan bertambah jika b_1 dinaikan dengan tingkat kenaikan yang relative kecil. Bila kenaikan b_1 melebihi batas tertentu maka ada kemungkinan bahwa titik optimal tidak dapat tercapai (keadaan infeasible). Artian ini dapat dijelaskan dengan melihat contoh permasalahan yang sederhana sebagai berikut :

Fungsi tujuan :
Memaksimumkan : Z = 3X_1+ 5X_2
Fungsi-fungsi pembatas :
2X_1 ≤ 8
2X_2 ≤ 15
6X_1+ 5X_2 ≤ 30
Apabila persoalan ini dipecahkan dengan menggunakan metode simplex akan diperoleh table optimal sebagai berikut :
Variabel Z X_1 X_2 X_3 X_4 X_5 NK
Z

X_3

X_2

X_1 1

0

0

0 0

0

0

1 0

0

1

0 0

1

0

0 5/6

5/9

1/3

-5/18 ½

-1/3

0

1/6 27 ½

19/3

5

5/6


Bila masalah diatas diselesaikan dengan metode grafik maka tentunya akan diperoleh penyelesaian optimal sudut (corner solution) dimana X_1=5/6,〖 X〗_2 = 5, dan Z maksimum sebesar 27 ½ dengan perhitungan sebagai berikut :
Batasan 1 : 2X_1 = 8
X_1 = 4

Batasan 2 : 3X_2 = 15
X_2 = 5

Batasan 3 : 6X_1+ 5X_2 = 30
X_1 = 0
5X_2 = 30
X_2 = 6
X_2 = 0
6X_1 = 30
X_1 = 5

6 X_1 = 4
5 3X_2 = 15




0 4 5

Apa yang terjadi bila b_1 (secara individu) dinaikan nilainya dengan 1?. Perhatikan bahwa corner point solution bagi masalah tersebut adalah X_1 = 5/6, X_2 = 5, dan Z = 27 ½.
Apabila batasan 1 : 2X_1 ≤ 8, dirubah (dinaikan) menjadi 2X_1 ≤ 9, mka nilai X_1^* dan X_2^* tetap yakni X_1^*=5/6,X_2^*=5,dan〖 Z〗^* = 27 ½. Ini sesuai dengan interprestasi atas Y_1^*=0 sehingga Z juga = 0 (lihat table optimal)

Apabila batasan 2 : 3X_2 ≤ 15 dirubah (dinaikan) menjadi 3X_2 ≤ 16, maka X_1^* dan X_2^* (titik C pada grafik) akan berubah dengan mencari perpotongan batasan 2 (baru) dengan batasan 3

6X_1 + 5X_2=30
3X_2 = 15
18X_1+ 15 X_2=90
15X_2 = 80
18X_1 = 10
X_1^* = 10/18 = 5/9
X_2^* = 16/3

Z = 5/9 (3) + 16/3 (5) = 281/3
Ternyata kenaikan nilai Z sebesar 28 1/3 – 27 ½ = 5/6. Sesuai dengan besarnya Y_2^* = 5/6

Apabila batasan 3 : 6X_1+ 5X_2≤30 dirubah menjadi 6X_1+ 5X_2 ≤31, makan nilai X_1^* dan X_2^* akan berubah sebgai berikut :
6X_1 + 5X_2=31
3X_2=15
18X_1+ 15X_2=93
15X_2 = 75
18X_1 =18
X_(1 )^(* ) = 1
X_2^* = 5
Z^* = 1 (3) + 5 (5) = 28

Tampak bahwa ∆Z sama dengan Y_3^* sebesar 1/2 menjadi 5/6
Di muka telah disinggung bahwa hal ini hanya relevan bagi kenaikan b_1 yang relative. Batasan kedua misalnya tidak dapat diperlonggar lebih dari 3 satuan (menjadi 3X_2 ≤18). Apabila dijadikan 3X_2 ≤19, maka :
6X_1 + 5X_2=30
3X_2=19
18X_1+ 15X_2=90
15X_2=95
18X_1 = -5
X_1^* = -5/18
Tentu saja melanggar batasan X_1 ≥0 (batasan 0 negatif)

Untuk batasan ketiga nilai kananya tidak dapat dinaikan lebih dari 19 satuan (menjadi 6X_1+ 5X_2=49). Umpama nilai kanannya dinaikan menjadi 50; (menjadi 6X_1+ 5X_2=50) maka :
6X_1 + 5X_2=50
3X_2=15
18X_1+ 15X_2=150
15X_2=72
18X_(1 ) =75
X_1^(* ) = 75/18
Hal ini melanggar batasan pertama dimana 2X_1 ≤ 8 atau X_1 ≤2

Penafsiran tentang dua variable yang dikemukakan diatas merupakan hal yang sangat penting bagi aplikasi (praktek) teknik linier programming. Karena dalam praktek meskipun dalam menyusun model permasalahan linier programming telah ditetapkan besarnya kapasitas sumber maksimal (b_(i.)).
Kadang-kadang dimungkinkan adanya penambahan. Misalnya penambahan budget, dalam hal busget dipakai sebagai salah satu batasan. Apabila jawaban optimal suatu masalah Linier Programming (primal) telah ditemukan, nilai-nilai dula variabelnya (shadow price) lalu dipakai untuk mengevaluasi apakah alokasi sumber-sumber harus dirubah. Shadow price Y_i^* untuk sumber I menunjukan beberapa harga per-unit (maksimum) yang telah tersedia kita bayar untuk menaikan alokasi sumber tersebut.
Hubungan lebih lanjut antara masalah primal dalam linier programming dengan dualnya tampak dalam table berikut. Karena suatu dual dalam hal ini juga dapat berwujud masalah linier programming maka ia juga memiliki corner point solution. Tetapi karena fungsi-fungsi pembatas mengandung tanda ≥ (seperti pada masalah minimasi lainnya) maka untuk merubahnya menjadi persamaan harus dikurangi dengan surplus variable. Dimana surplus variable daripada dual tidak lain adalah variable asli daripada masalah primalnya. Sebaliknya slack variable yang terdapat pada primal, tidak lain adalah variable asli pada masalah dualnya.

Tabel : hubungan antara variable-variabel primal-dual dalam Linier Programming
Variabel Primal Variabel Dual
Variabel asli (original variable ) : X_j
Variabel slack (slack variable) : X_n+ 1 Variabel Suplus (Surplus Variable) : Z_j- C_j
Variabel asli (original variable) : Y_i
Dimana i = 1, 2, 3, …, m
J = 1, 2, 3, …, n

2.4 Penyimpangan-Penyimpangan dari Bentuk Standar

Sampai tahap ini pembicraan masih terbatas pada pembahasan dari dualitas dalam bentuk standar, dimana masalah primal merupakan masalah maksimasi dengan fungsi-fungsi pembatas yang bertanda. Padahal seperti yang telah disebutkan di muka bahwa semua masalah Linier Programming baik itu dalm bentuk standar atau tidak mempunyai masalah dual. Oleh karena itu, ada baiknya kita membahas pula berbagai penyimpangan dari bentuk standar tersebut.
Setiap penyimpangan dari bentuk standar telah dikupas dalam membahas metode simplex. Dalam hal ini teori dualitas, macam-macam penyimpangan dari bentuk standar yang akan dibicarakan juga serupa dengan macam-macam penyimpangan pada metode simplex, seperti yang tampak pada table. Tabel menunjukan ringkasan empat macam penyimpangan dari bentuk standar tersebut, sedangkan bagian kanan menunjukan perubahan bentuk yang menyimpangan dari bentuk standar tersebut menjadi bentuk yan g memenuhi persyartan-persyaratan bentuk standar.

Tabel konversi bentuk “bukan standar” menjadi bentuk standar dalam model linier programming
Bentuk
“bukan standar” Bentuk standar
(yang ekuivalen)
Minimasi Z

∑_(j=1)^n▒〖a_ij X_j ≥ b_i 〗

∑_(j=1)^n▒〖a_ij X_j= b_i 〗

Nilai X_j tidak terbatas Maksimisasi (-Z)

-∑_(j=1)^n▒〖a_ij X_j ≤ b_i 〗

∑_(j=1)^n▒〖a_ij X_j ≤ b_i 〗 dan

(X_j^'.X_j"\")," "X" _"j" "' ≥0," "X" _"j" "≥0

Dapat dimukakan disini bahwa setiap permasalahan dapt dikembalikan ke bentuk standar untuk kemudian dicari dualnya dengan cara biasa. Untuk permasalahan yang agak rumit, dapat dilakukan secra bertahap seperti tamapak pada table berikut ini.
Tabel tersebut menunjukan bagaimana perubahan-perubahan bentuk yang terjadi dalam mencari “dual dari dual” alias “primal”. Contoh sengaja dikemukakan agar kita tidak selalu beranggapan bahwa hanya primal yang hanya dapat dipakai dalam mencari dual. Tabel ini menunjukan hasil akhir yang dicapai dalam proses yang berupa bentuk standar dari primal.
Tabel mencarai bentuk dual dari dual problem

Masalah dual
Minimumkan Y_0= b_1 Y_1+ b_2 Y_2+⋯+ b_m Y_m
Batasan-batasan :
a_11 Y_1+ a_21 Y_2+ …+ a_m1 Y_n ≥ C_1
〖 a〗_12 Y_1+ a_22 Y_2+ …+ a_m2 Y_m ≥ C_2
-
-
-
Dan :
a_1n Y_1+ a_2n Y_2+ …+ a_mn Y_m ≥ Y_m
Y_1 ≥0,Y_2 ≥0,… Y_m ≥0

Perubahan kedalam bentuk standar
Maksimumkan (-Y_o)= -b_1 Y_1- b_2 Y_2- …-b_m Y_m
Batasan-batasan : -a_11 Y_1- a_21 Y_2- a_21 Y_2- …- a_m1 Y_m ≤ -C_1
-a_12 Y_1- a_22 Y_2- a_22 Y_2- …- a_m2 Y_m ≤ -C_2
-
-
-
Dan : -a_11 Y_1- a_2 Y_2- a_21 Y_2- …- a_mn Y_m ≤ -C_m
Y_1 ≥0,Y_2 ≥0,…,-Y_m ≥0

Dual dari dual tersebut (=primal)
Minimumkan (–Z)= -C_1 X_1- C_2 X_2- …- C_n X_n
Batasan-batasan : -a_11 X_1- a_12 X_2 -…- a_1n X_n ≥ -b_1
-a_21 X_1- a_22 X_2- …- a_2n X_n ≥ -b_2
-
-
-a_m1 X_1- a_m2 X_2 - …- a_mn X_n ≥- b_m
Dan : X_1 ≥0,X_2 ≥0-…- X_n 0

Perubahan kedalam bentuk standar
Maksimumkan Z = C_1 X_1+ C_2 X_2+ …+ C_n X_n
Batasan –batasan : -a_11 X_1+ a_12 X_2+ …+ a_1n X n≥ b_1
-a_21 X_1 + a_22 X_2+ …+ a_2n X_n ≥ b_2
-
-
-a_m1 X_1+ a_m2 X_2+ …+ a_mn X_n ≥ b_m
Dan : X_1 ≥0,X_2 ≥0+⋯+ X_n ≥0

Setelah melihat proses yang di tampilkan pada table diatas lalu dapat dipahami apa yang dinamakan rataan sipteris yang terdapat pada teori dualitas ini. Secara tegas kaidah ini mengatakan bahwa segala bentuk hubungan antar satu masalah primer dengan linier programming dengan masalah dualnya dalah simitris. Hal ini disebabkan oleh kenyataan bahawa dual daripada suatu permasalahan dual tidak lain adalah masalah primalnya. Akibatnya segla bentuk hubungan antara dual dengan primal yang telah dihapus terdahulu dapat diterapkan kebalikannya. Akibat lain dari kaidah ini adalah adanya “kebebasan” kita untuk menetapkan mana masalah primal dan masalah dualnya.
Ilustrasi pada table diatas tidak menampilkan adanya penyimpangan dari bentuk standar dalam hal batasan-batasan baik berupa bentuk persamaan (=) maupun tidak batasannya nilai X_j. Apabila kedua macam penyimpangan tersebut terjadi bersama-sama maka jalan ringkas untuk mencari dualnya dapat dipakai yakni batasan yang mengandung tanda kesamaan (=) diperlukan seperti layaknya batasan bertanda ≤ tetapi batasan non-negatif bagi dua variable yang bersangkutan harus dihilangakan (yaitu variable 1 yang tidak terbatas nilainya). Sebaliknya dengan melihat kembali kaidah simetris dimuka, dapat dikatakan bahwa; menghilangkan btasan non-negatif pada masalah primal akan mengakibatkan perubhan batasan pada masalah dual menjadi bentuk persamaan (=). Secra lengkap, penyimpangan-penyimpanagn yang terjadi pada masalah primal (atau dual) dan kaitannya terhadap bentuk masalah dual (atau primal) disajikan pada table berikut ini.

Hubungan bentuk-bentyk primal dual
Masalah primal (atau dual) Masalah dual (atau primal)

Maksimumkan Z (atau Y_0)

Batasan i

Bentuk ≤

Bentuk =

Variable X_j (atau Y_j)

X_ij ≥0

X_j ≥0 dihilangakan

Minimumkan Y_o (atau Z)

Variable Y_i (atau X_i)

Y_1 ≥0
Type equation here.
Y_1 ≥0 dihilangakan

Batasan j

Bentuk ≥

Bentuk =

Sebagai ilustrasi prosedur diatas, kita kembali kepada contoh dimuka yang telah dimudipikasi seperti tampak pada table berikut ini.
Primal Dual

Minimumkan Z =3X_1+5X_2

Batasan –batasan :
-2X_1 ≥ -8
2X_2=15
6X_1+ 2X_2 ≥30
Dan
X_1≥0 ; X_2 ≥0
Maksimumkan Y_o= -8Y_1+ 15Y_2+ 30Y_3

Batasan-batasan :
-Y_1+ 6Y_2 ≤8
3Y_2+ 2Y_3 ≤5
Dan
Y_1 ≥0 ; Y_3 ≥0
(Y_2 ≥0 dihlangkan)

BAB III

Kesimpulan

Teori dualitas merupakan teori yang sanagt berguna dalam penerapan metode linier programming, terutama dalam dunia bisnis. Dengan menguasai teori ini, paling tidak dapat dipetik dua manfaat yakni :
Dalam hal mengartikan (terutama dalam artian ekonomis) angka-angka yang terdapat pada table optimal dari permasalahan primal
Dalam hal memeriksa kembali apakah ada kesalahan dalam melakukan perubahan-perubahan pada setiap langkah dalam menggunakan metode simplex bagi permasalahan primal

Saran

Tidak ada komentar:

Posting Komentar