WorksheetsTransportation Problem and Optimization Methods Worksheet
Total questions: 50
Worksheet time: 1hrs 3mins
Metode transportasi digunakan untuk menyelesaikan masalah:
Penjadwalan proyek
Penugasan pekerja
Distribusi dari beberapa sumber ke beberapa tujuan dengan biaya minimal
Optimasi jaringan
Antrian
Dalam masalah transportasi, syarat untuk mencapai solusi fisibel awal adalah:
Jumlah sel terisi = m + n
Jumlah sel terisi = m + n + 1
Jumlah sel terisi = m + n - 1
Jumlah sel terisi = m x n
Jumlah sel terisi = m - n
Metode solusi awal yang biasanya memberikan solusi paling dekat dengan optimal adalah:
North West Corner
Vogel’s Approximation Method (VAM)
Least Cost Method
Stepping Stone
Modi
Metode North West Corner (NWC) dalam mencari solusi awal mengabaikan:
Kapasitas sumber
Permintaan tujuan
Biaya transportasi
Jumlah sel terisi
Sel kosong
Dalam VAM, penalty dihitung dari:
Selisih biaya terbesar dan terkecil pada baris/kolom
Rata-rata biaya pada baris/kolom
Total biaya pada baris/kolom
Biaya terendah pada baris/kolom
Biaya tertinggi pada baris/kolom
Solusi awal dengan metode Least Cost:
Selalu memberikan solusi optimal
Memilih sel dengan biaya tertinggi
Memilih sel dengan biaya terendah secara iteratif
Mengabaikan kapasitas dan permintaan
Untuk masalah transportasi seimbang, total supply dan total demand:
Sama
Supply lebih besar
Demand lebih besar
Tidak berpengaruh
Harus nol
Jika masalah tidak seimbang (supply > demand), maka:
Ditambahkan dummy demand
Ditambahkan dummy supply
Diabaikan kelebihan supply
Biaya dummy diatur = 0
a dan d benar
Solusi optimal dicapai ketika:
Semua sel terisi
Semua nilai opportunity cost ui+vj ≤ cij untuk sel kosong (minimasi)
Total biaya = 0
m+n-1 sel terisi
Penalty = 0
Metode MODI (Modified Distribution) disebut juga:
u-v method
Vogel’s method
NWC method
Dual simplex
Stepping stone matrix
Masalah transportasi di atas bersifat:
Seimbang (total supply = total demand)
Tidak seimbang, supply > demand
Tidak seimbang, demand > supply
Tidak dapat diselesaikan
Tidak memerlukan dummy
Dengan NWC, alokasi pertama (S1-P1) adalah:
120
150
70
80
30
Setelah alokasi pertama NWC (S1-P1=120), sisa demand P1 adalah:
0
30
70
80
150
Dengan metode Least Cost, sel pertama yang dialokasi adalah:
S1-P2 (biaya 5)
S3-P1 (biaya 3)
S1-P3 (biaya 6)
Dengan VAM, penalty baris S1 adalah:
1 (6-5)
2 (8-6)
3 (8-5)
5
8
Banyaknya sel terisi pada solusi awal adalah:
3
4
5
6
7
Jika solusi awal dengan NWC menghasilkan biaya total = 2450, lalu dengan Stepping Stone ditemukan sel S3-P1 memiliki opportunity cost negatif, maka:
Solusi sudah optimal
Solusi belum optimal, S3-P1 masuk basis
Solusi belum optimal, S3-P1 keluar basis
Biaya akan naik
Tidak perlu perubahan
Dalam MODI, untuk sel basis berlaku rumus:
ui + vj = cij
ui + vj ≤ cij
ui + vj ≥ cij
ui - vj = cij
ui * vj = cij
Jika dengan MODI ditemui sel kosong dengan nilai ui+vj > cij, maka:
Solusi optimal
Biaya dapat dikurangi dengan memasukkan sel tersebut
Biaya akan naik
Tidak perlu perubahan
Penalty negatif
Solusi optimal tercapai jika semua sel kosong memiliki:
ui + vj ≤ cij
ui + vj ≥ cij
Banyaknya sel terisi pada solusi awal adalah:
3
4
5
6
7
Dengan NWC, alokasi pertama (A-X) adalah:
35
40
30
25
10
SOAL STUDI KASUS 2 (Untuk soal 21-30) Supply: A=40, B=30, C=50 Demand: X=35, Y=25, Z=30, W=20 Total supply = 120, total demand = 110 → supply > demand, tambah dummy demand 10. Biaya (A ke X,Y,Z,W) = 10, 8, 12, 6 Biaya (B ke X,Y,Z,W) = 5, 7, 9, 11 Biaya (C ke X,Y,Z,W) = 12, 10, 8, 9 Biaya ke dummy = 0. 23. Dengan Least Cost, sel pertama dialokasi ke:
A-W (6)
B-X (5)
B-Y (7)
C-Z (8)
Dummy
Pada VAM, jika suatu baris/kolom memiliki dua biaya terendah sama, maka penalty-nya:
0
1
Jika solusi awal NWC menghasilkan biaya total 950, dan setelah MODI ditemukan sel B-W memiliki evaluasi = -2, artinya:
Setiap unit yang dialokasikan ke B-W menaikkan biaya 2
Setiap unit yang dialokasikan ke B-W menurunkan biaya 2
Solusi sudah optimal
Tidak boleh alokasi ke B-W
Biaya dummy berubah
Jika dalam Stepping Stone, sel masuk yang dipilih adalah yang memiliki opportunity cost negatif terbesar (paling negatif), maka:
Biaya turun paling cepat
Biaya naik
Jumlah iterasi mungkin lebih sedikit
a dan c benar
b dan c benar
Dalam masalah dengan dummy, biaya transportasi ke dummy selalu:
0
1
M
Tak terhingga
Sama dengan biaya terendah
Jika setelah MODI semua sel dummy memiliki opportunity cost ≤ 0, maka:
Solusi sudah optimal
Dummy harus diganti
Masalah harus diubah
Ada degenerasi
Supply kurang
Degenerasi terjadi jika jumlah sel terisi:
> m+n-1
< m+n-1
= m+n-1
= m x n
= 0
Untuk mengatasi degenerasi, langkah yang dilakukan:
Menambah alokasi di sel dummy
Menambah alokasi sangat kecil (ε) di sel kosong tertentu
Mengganti metode solusi awal
Menghapus satu sel terisi
Mengabaikan saja
Metode transportasi merupakan kasus khusus dari:
Program dinamik
Program linear
Teori permainan
Analisis Markov
Teori antrian
Yang bukan termasuk metode solusi awal transportasi:
Vogel’s Approximation
Least Cost
North West Corner
Stepping Stone
a dan b
Jika dalam tabel transportasi jumlah sel terisi < m+n-1, maka:
Terjadi degenerasi
Solusi tidak fisibel
Perlu dummy
MODI tidak bisa dihitung semua ui, vj
a dan d benar
Dalam MODI, nilai ui atau vj pertama biasanya diberi nilai:
0
1
-1
Tak terhingga
Rata-rata cij
Kelebihan VAM dibanding NWC dan Least Cost:
Lebih cepat
Memberikan solusi awal lebih dekat optimal
Biaya opportunity pada sel kosong menunjukkan:
Besarnya kenaikan biaya jika sel tersebut dialokasi 1 unit
Besarnya pengurangan biaya jika sel tersebut dialokasi 1 unit
Biaya transportasi sel tersebut
Penalty dalam VAM
Nilai ui+vj
Jika semua opportunity cost non-negatif, maka solusi:
Optimal untuk minimisasi
Optimal untuk maksimisasi
Belum optimal
Degenerate
Tidak fisibel
Pada masalah maksimisasi (keuntungan), solusi optimal tercapai jika:
Opportunity cost ≤ 0 untuk sel kosong
Opportunity cost ≥ 0 untuk sel kosong
Opportunity cost = 0
ui+vj ≥ cij
Tidak ada bedanya dengan minimisasi
Stepping Stone dan MODI pada dasarnya:
Memberikan hasil akhir berbeda
Sama-sama metode optimalisasi
MODI lebih mudah untuk tabel besar
Stepping Stone menghitung loop untuk setiap sel kosong
b, c, d benar
Loop dalam Stepping Stone:
Selalu berbentuk persegi panjang
Dapat memotong
Hanya melalui sel terisi
Dimulai dan diakhiri di sel kosong
a dan d benar
Total supply dan demand:
Supply > demand
Demand > supply
Seimbang
Perlu dummy di supply
Tidak dapat dihitung
Dengan NWC, alokasi O1-D1 adalah:
20
50
30
40
95
Setelah alokasi O1-D1=20, sisa supply O1:
0
30
50
70
95
Dengan Least Cost, alokasi pertama pada sel:
O1-D1 (2)
O2-D3 (1)
O3-D2 (4)
O2-D2 (3)
Dengan VAM, penalty kolom D2 pada iterasi pertama:
1 (4-3)
3 (7-4)
0 (biaya sama)
4
7
Jika solusi awal VAM menghasilkan biaya total 300, lalu MODI menghitung u1=0, v1=2, v2=7, u2=-4, maka nilai u2 didapat dari:
u2 + v1 = c21 → u2 = 3-2 = 1? (tidak ada -4)
Dari sel basis O2-D3: u2+v3=1
Dari sel basis O2-D2: u2+v2=3 → u2=3-7=-4
Asumsi
c benar
Jika sel O3-D1 adalah sel kosong, opportunity cost-nya = c31 - (u3+v1). Jika hasilnya = -3, artinya:
Jika dialokasikan 1 unit ke sel itu, biaya naik 3
Jika dialokasikan 1 unit ke sel itu, biaya turun 3
Tidak boleh dialokasikan
Solusi optimal
Nilai u3+v1=8
Dalam loop Stepping Stone untuk sel O3-D1, sel yang dikurangi alokasinya adalah:
Sel basis dengan alokasi terkecil dalam loop
Sel basis dengan alokasi terbesar
Sel kosong
Sel dummy
Semua sel basis
Jika dalam loop ditemukan dua sel dengan alokasi terkecil sama, maka:
Pilih salah satu, sisanya menjadi degenerate
Keduanya dikurangi
Loop salah
Tidak boleh terjadi
Hanya satu yang keluar basis
Setelah optimal, biaya total minimum adalah:
