Penentuan Solusi Optimal MUHLIS TAHIR
Metode • Ada dua metode yang dapat digunakan untuk menentukan solusi optimal, yaitu : • Metode Stepping Stone • Metode Modified Distribution (Modi) • Prinsip perhitungan kedua metode untuk menentukan sel masuk adalah sama. • Perbedaannya adalah metode Modi menggunakan prinsip dasar primal-dual metode simpleks, sedangkan metode stepping stone tidak.
Metode Modifikasi Distribusi (Modi) • Contoh :
Solusi optimal tercapai jika untuk : • Maksimasi, ui + vj – cij ≥ 0 • Minimasi , ui + vj – cij ≤ 0 Langkah-langkah penyelesaian : 1. Penentuan sel masuk Untuk setiap sel basis, hitung ui + vj = cij. ui menunjukkan baris ke-i, vj menunjukkan kolom ke-j dan cij adalah biaya pada sel ij (baris i kolom j); karena jumlah variabel yang tidak diketahui (ui dan vj) lebih banyak dibandingkan jumlah persamaan yang dibentuk, maka salah satu variabel diasumsikan bernilai 0.
• Untuk setiap sel non basis, hitung cpq = ui + vj – cij • Untuk maksimasi, sel masuk adalah sel dengan nilai cpq paling negatif; sedangkan untuk minimasi, sel masuk adalah sel dengan nilai cpq paling positif. 2. Penentuan sel keluar penentuan sel keluar dilakukan dengan menggunakan loop tertutup. Awal dan akhir loop adalah sel masuk. Garis-garis horizontal ataupun vertikal yang membentuk loop harus berakhir (ujung awal ataupun akhir garis) pada sel basis, kecuali awal dan akhir loop pada sel masuk. 3. Periksa apakah sudah optimal. Syarat optimal dipenuhi jika cpq tidak ada yang bernilai negatif untuk maksimasi dan tidak ada yang bernilai positif untuk minimasi.
Contoh Kasus • Solusi awal yang digunakan adalah solusi yang diperoleh dengan menggunakan sudut barat laut sebelumnya. Solusi awal adalah sbb :
Iterasi 1 : Sel basis adalah sel 11, 12, 22, 23, 33, 34, 35, sel non basis adalah 13, 14, 15, 21, 24, 25, 31,32. 1. Penentuan sel masuk Untuk setiap sel basis : u 1 + v1 = 2 u1 + v2 = 5 u2 + v2 = 10 u 2 + v3 = 3 u3 + v3 = 6 u3 + v4 = 6 u 3 + v5 = 4 Misalkan u1 = 0 maka v1 = 2; v2 = 5; u2 = 5; v3 = -2; u3 = 8; v4 = -2; v5 = -4.
2. Untuk setiap sel non basis : c13 = u1 + v3 – c13 = 0 – 2 – 6 = -8 c14 = u1 + v4 – c14 = 0 – 2 – 3 = -5 c15 = u1 + v5 – c15 = 0 – 4 – 5 = -9 c21 = u2 + v1 – c21 = 5 + 2 – 6 = 1 c24 = u2 + v4 – c24 = 5 – 2 – 3 = 0 c25 = u2 + v5 – c25 = 5 – 4 – 7 = -6 c31 = u3 + v1 – c31 = 8 + 2 – 11 = - 1 c32 = u3 + v2 – c32 = 8 + 5 – 8 = 5 Karena masih ada dua sel non basis yang bernilai positif dan tujuan dari optimasi ini adalah minimasi biaya, maka tabel belum optimal. Sel masuk adalah sel dengan nilai positif terbesar, dalam hal ini adalah sel 32, artinya dengan mengisi sel 32, biaya transportasi dapat berkurang
2. Penentuan Sel Keluar Sel keluar ditentukan menggunakan loop tertutup. Loop harus berawal dan berakhir pada sel 32. Hanya ada satu alternatif loop yang dapat kita bentuk. Loop terbentuk pada sel 32, 33, 23, dan 22. Karena sel 32 akan diisi, maka sel 32 dan 22 akan berkurang dan sel 32 dan 23 akan bertambah. Jumlah yang diperpindahkan sama dengan alokasi terkecil yang ada dalam sel loop.
Alokasi pada iterasi pertama adalah : • Dari pabrik A ke gudang 1 sebesar 300 unit, biaya Rp.60.000.000 • Dari pabrik A menuju gudang 2 sebesar 200 unit, biaya Rp.100.000.000 • Dari pabrik B menuju gudang 2 sebesar 100 unit, biaya Rp.100.000.000 • Dari pabrik B menuju gudang 3 sebesar 200 unit, biaya Rp.60.000.000 • Dari pabrik C menuju gudang 2 sebesar 100 unit, biaya Rp.100.000.000 • Dari pabrik C menuju gudang 4 sebesar 300 unit, biaya Rp.180.000.000 • Dari pabrik C menuju gudang 5 sebesar 200 unit, biaya Rp.80.000.000 • Total biaya = Rp. 680.000.000
Iterasi 2 : 1.Penentuan sel masuk • Sel basis adalah sel 11,12,22, 23, 32, 34 dan 35 u 1 + v1 = 2 u1 + v2 = 5 u2 + v2 = 10 u 2 + v3 = 3 u3 + v3 = 5 u3 + v4 = 6 u3 + v5 = 4 Misal u1 = 0 maka v1 = 2; v2 = 5; u2 = 5; v3 = -2; u3 = 0; v4 = 6; v5 = 4.
2. Untuk setiap sel non basis adalah sel 13,14,15, 21, 24, 25, 31, dan 33 c13 = u1 + v3 – c13 = 0 – 2 – 6 = -8 c14 = u1 + v4 – c14 = 0 + 6 – 3 = 3 c15 = u1 + v5 – c15 = 0 + 4 – 5 = -1 c21 = u2 + v1 – c21 = 5 + 2 – 6 = 1 c24 = u2 + v4 – c24 = 5 + 6 – 3 = 8 c25 = u2 + v5 – c25 = 5 + 4 – 7 = 2 c31 = u3 + v1 – c31 = 0 + 2 – 11 = - 9 c32 = u3 + v2 – c32 = 0 – 2 – 6 = -8
2. Penentuan sel keluar
• Dari pabrik A menuju gudang 1 sebesar 300 unit, biaya Rp.60.000.000 • Dari pabrik A menuju gudang 2 sebesar 200 unit, biaya Rp.100.000.000 • Dari pabrik B menuju gudang 3 sebesar 200 unit, biaya Rp.60.000.000 • Dari pabrik B menuju gudang 4 sebesar 100 unit, biaya Rp.30.000.000 • Dari pabrik C menuju gudang 2 sebesar 200 unit, biaya Rp.100.000.000 • Dari pabrik C menuju gudang 4 sebesar 200 unit, biaya Rp.120.000.000 • Dari pabrik C menuju gudang 5 sebesar 200 unit, biaya Rp.80.000.000 • Total biaya = Rp 550.000.000
Iterasi 3 : 1.Penentuan sel masuk • Sel basis adalah sel 11, 12, 23, 24, 32, 34 dan 35 u 1 + v1 = 2 u1 + v2 = 5 u2 + v3 = 3 u2 + v4 = 3 u3 + v2 = 5 u3 + v4 = 6 u 3 + v5 = 4 Misal u1 = 0 maka v1 = 2; v2 = 5; u2 = -3; v3 = 6; u3 = 0; v4 = 6; v5 = 4.
2. Untuk setiap sel non basis adalah sel 13, 14, 15, 21, 22, 25, 31, dan 33 c13 = u1 + v3 – c13 = 0 – 6 – 6 = - 12 c14 = u1 + v4 – c14 = 0 + 6 – 3 = 3 c15 = u1 + v5 – c15 = 0 + 4 – 5 = -1 c21 = u2 + v1 – c21 = -3 + 2 – 6 = - 7 c24 = u2 + v2 – c22 = -3 + 5 – 10 = - 8 c25 = u2 + v5 – c25 = -3 + 4 – 7 = - 6 c31 = u3 + v1 – c31 = 0 + 2 – 11 = - 9 c32 = u3 + v3 – c33 = 0 – 6 – 6 = - 12
2. Penentuan sel keluar
• Dari pabrik A menuju gudang 1 sebesar 300 unit, biaya Rp.60.000.000 • Dari pabrik A menuju gudang 4 sebesar 200 unit, biaya Rp.60.000.000 • Dari pabrik B menuju gudang 3 sebesar 200 unit, biaya Rp.60.000.000 • Dari pabrik B menuju gudang 4 sebesar 100 unit, biaya Rp.30.000.000 • Dari pabrik C menuju gudang 2 sebesar 400 unit, biaya Rp.200.000.000 • Dari pabrik C menuju gudang 5 sebesar 200 unit, biaya Rp.120.000.000 • Dari pabrik C menuju gudang 5 sebesar 200 unit, biaya Rp.80.000.000 • Total biaya = Rp 490.000.000
Iterasi 4 : 1.Penentuan sel masuk • Sel basis adalah sel 11, 12, 14, 23, 24, 32 dan 35 u 1 + v1 = 2 u1 + v2 = 5 u1 + v4 = 3 u2 + v3 = 3 u2 + v4 = 3 u3 + v2 = 5 u 3 + v5 = 4 Misal u1 = 0 maka v1 = 2; v2 = 5; u2 = 0; v3 = 3; u3 = 0; v4 = 3; v5 = 4.
2. Untuk setiap sel non basis adalah sel 13, 15, 21, 22, 25, 31, 33 dan 34 u1 + v3 – c13 = 0 + 3 – 6 = - 3 u1 + v5 – c15 = 0 + 4 – 5 = -1 u2 + v1 – c21 = 0 + 2 – 6 = -4 u2 + v2 – c22 = 0 + 5 – 10 = - 5 u2 + v5 – c25 = 0 + 4 – 7 = - 3 u3 + v1 – c31 = 0 + 2 – 11 = - 9 u3 + v3 – c33 = 0 + 3 – 6 = - 3 u3 + v4 – c34 = 0 + 4 – 6 = - 2 Karena semua nilai sudah negatif, maka tabel sudah optimal. Solusi optimalnya = solusi iterasi 3
• Dari pabrik A menuju gudang 1 sebesar 300 unit, biaya Rp.60.000.000 • Dari pabrik A menuju gudang 4 sebesar 200 unit, biaya Rp.60.000.000 • Dari pabrik B menuju gudang 3 sebesar 200 unit, biaya Rp.60.000.000 • Dari pabrik B menuju gudang 4 sebesar 100 unit, biaya Rp.30.000.000 • Dari pabrik C menuju gudang 2 sebesar 400 unit, biaya Rp.200.000.000 • Dari pabrik C menuju gudang 5 sebesar 200 unit, biaya Rp.120.000.000 • Dari pabrik C menuju gudang 5 sebesar 200 unit, biaya Rp.80.000.000 • Total biaya = Rp 490.000.000
Kesimpulan • Solusi awal yang dihasilkan menggunakan metode biaya terkecil dan pendekatan vogel. • Solusi optimal pada Modi sama dengan solusi awal yang dihasilkan dengan kedua metode tersebut. • Metode pendekatan vogel dapat menghasilkan solusi awal yang jauh lebih baik dibandingkan dengan metode biaya terkecil untuk kasus yang lebih kompleks
