Metode Simpleks Dual [PDF]

Citation preview

Metode simpleks dual A. Masalah Primal-Dual Simetrik Program linier dikatakan simetri jika ruas kanan pembatas bernilai tidak negatif, semua pembatas menggunnakan bentuk pertidaksamaan, jika dalam masalah maksimasi bentuk pertidaksamaan berupa ≤ sedangkan dalam masalah minimasi bentuk pertidaksamaan berupa ≥. Notasi matiks masalah primal-dual simetri adalah: Primal : Maksimasi Z=cX dengan pembatas berupa AX ≤ b X ≥ 0+ Dual :+ Minimasi Z=Yb dengan pembatas berupa YA ≥ c Y ≥0 Keterangan : 1. A : matriks (m ×n) 2. b : vektor kolom (m ×1) 3. c : vektor baris (1 ×n) 4. x : vektor kolom (n ×1) 5. y : vektor baris (1 ×m) Bentuk umum dari primal-dual simetri Primal Maksimasi : Z=c 1 X 1+ c 2 X 2 +...+c n X n



fungsi tujuan



a 11 X 1+ a12 X 2+...+ a1 n X n ≤ b1 fungsi pembatas a 21 X 1 +a22 X 2 +...+a2 n X n ≤b 2 a m 1 X 1 +a m 2 X 2+...+ amn X n ≤ b m X 1 , X 2 ,... , X n ≥ 0



Dual Minimasi : W =b1 Y 1+ b2 Y 2+...+b m Y m



fungsi tujuan



a 11 Y 1 +a 21 Y 2 +...+am 1 Y m ≥ c1 fungsi pembatas a 12 Y 1+ a22 Y 2 +...+a m 2 Y m ≥ c 2 a 1n Y 1 +a2 n Y 2+...+ amn Y m ≥ c n Y 1 ,Y 2 , ... ,Y m ≥ 0



Primal Minimasi : Z=c 1 X 1+ c 2 X 2 +...+c n X n



fungsi tujuan



a 11 X 1+ a12 X 2+...+ a1 n X n ≥ b1 fungsi pembatas a 21 X 1 +a22 X 2 +...+a2 n X n ≥b 2 a m 1 X 1 +a m 2 X 2+...+ amn X n ≥ b m X 1 , X 2 ,... , X n ≥ 0



Dual Masimasi : W =b1 Y 1+ b2 Y 2+...+b m Y m



fungsi tujuan



a 11 Y 1 +a 21 Y 2 +...+am 1 Y m ≤c 1 fungsi pembatas a 12 Y 1+ a22 Y 2 +...+a m 2 Y m ≤ c 2 a 1n Y 1 +a2 m Y 2+ ...+ amn Y m ≤ c m Y 1 ,Y 2 , ... ,Y m ≥ 0 Dari keempat bentuk umum primal-dual simetri terbentuk hubungan antara primal dan dual, yaitu: 1.



2. 3.



4.



Ruas kanan pembatas dari masalah dual merupakan koefisien fungsi tujuan dari masalah primal, begitupun sebaliknya ruas kanan pembatas dari masalah primal menjadi koefisien fungsi tujuan dari masalah dual. Tanda pertidaksamaan pembatas dibalik, tanda dari masalah dual minimasi merupakan kebalikan dari tanda masalah primal maksimasi. Tujuan dari maksimasi masalah primal menjadi minimasi masalah dual, begitu juga sebaliknya tujuan minimasi masalah primal menjadi maksimasi masalah dual. Setiap kolom pembatas pada masalah primal berhubungan dengan satu baris pembatas masalah dual, sehingga banyaknya pembatas pada masalah dual



5.



6.



sama dengan banyaknya variabel masalah primal. Dengan kata lain ialah 1 kolom pembatas primal akan ditranpos menjadi baris pembatas dual. Setiap baris pembatas pada masalah primal berhubungan dengan satu kolom pada variabel dual, sehingga ada satu variabel dual menjadi bagian dari pembatas primal. Bentuk dual dari masalah dual merupakan bentuk primal.



B. Masalah primal-dual asimetri Bentuk umum primal-dual asimetri Primal Maksimasi atau minimasi : Z=c 1 X 1+ c 2 X 2 +...+c n X n



fungsi tujuan



a 11 X 1+ a12 X 2+...+ a1 n X n ≥ b1 fungsi pembatas a 21 X 1 +a22 X 2 +...+a2 n X n ≤b 2 a m 1 X 1 +a m 2 X 2+...+ amn X n=b m X 1 , X 2 ,... , X n ≥ 0 Beberapa di bawah ini yang harus diperhatikan pada primal-dual asimetri: 1.



2. 3.



Persoalan : a. Maksimasi : Jika pembatas primal ke-i bertanda ≥, maka variabel dual yang berkorespondensi dengan pembatas tersebut akan memenuhi y i ≤0. b. Minimasi : Jikai pembatas primal ke-i bertanda ≤, maka variabel dual yang berkorespondensi dengan kendala tersebut akan memenuhi y i ≤0 . Jika pembatas primal ke-i bertanda ¿, maka variabel dual yang berkorespondensi dengan pembatas tersebut ialah tidak terbatas dalam tanda. Jika variabel primal ke-i tidak terbatas dalam tanda, maka pembatas dual ke-i akan bertanda ¿.



apabila ingin memperlihatkan keterkaitan antara solusi primal dan solusi dual pada hubungan primal-dual asimetri perlu ditransformasikan ke dalam bentuk simetri, berikut ini langkah transformasi dari bentuk asimetri ke bentuk simetri. 1. Mengalikan setiap pembatas dengan tanda ≥ pada fungsi tujuan maksimasi atau pembatas dengan tanda ≤ pada fungsi tujuan minimasi dengan (-1). 2. Menggantikan setiap pembatas yang bertanda ¿ dengan dua tanda pertidaksamaan yaitu ≤ dan ≥. 3. Menggantikan setiap variabel x j tak terbatas menjadi x j= x'j−x j ' ' yang mana x j ' ≥ 0, x j ' ' ≥ 0.



Contoh bentuk primal-dual simetri sebagai berikut: 1. Primal Maksimasi Z=2000 X 1 +5000 X 2 +4000 X 3 Pembatas



2 X 1 +3 X 2 +6 X 3 ≤ 60 2 X 1 +2 X 2 +4 X 3 ≤ 40 X 1 +3 X 2 +5 X 3 ≤ 30 X1 , X2 , X3≥ 0



Dual Minimasi W =60 X 1 +40 X 2+30 X 3 Pembatas



2 X 1 +2 X 2 + X 3 ≥2000 3 X 1 +2 X 2 +3 X 3 ≥5000 6 X 1 + 4 X 2 +5 X 3 ≥ 4000 X1 , X2 , X3≥ 0



Penjelasan dari contoh di atas, Fungsi tujuan dari masalah primal menjadi ruas kanan dari masalah dual, setiap kolom pada pembatas primal menjadi baris di pembatas dual dan fungsi tujuan masalah dual berasal dari ruas kanan pembatas primal.



2.



Suatu perusahaan bahan baku bangunan mendistribusikan produksi terbesar mereka yaitu; semen, cat, pipa ke pada Toko Adi Makmur, Toko Jaya Sentosa, dan Toko Sumber Bangunan dengan waktu pendistribusiannya berbeda. Berikut data waktu yang dibutuhkan pada saat pendistribusian ke masing-masing Toko. Tabel 1 Data waktu distribusi produksi bahan bangunan ke toko Nama Toko



Jenis Produksi yang akan didistribusikan



Waktu untuk



Adi Makmur Jaya Sentosa Sumber Bangunan Laba



Semen 10 30



Cat 5 15



Pipa 20 25



tiap toko 20 90



15



20



30



60



4



5



6



Primal Variabel keputusan:



Fungsi tujuan: Maksimasi Fungsi pembatas



x 1 = jumlah produksi semen x 2 = jumlah produksi cat x 3 = jumlah produksi pipa



Z=4 x 1 +5 x 2+6 x 3