model transportasi
DESCRIPTION
Model Transportasi. Pemrograman Linier Semester Ganjil 2012/2013. Transportation Simplex Method. Memanfaatkan notasi matriks untuk koefisien baris nol Tableau yang digunakan adalah tableau dua arah seperti pada pertemuan sebelumnya - PowerPoint PPT PresentationTRANSCRIPT
Model Transportasi
Pemrograman Linier Semester Ganjil 2012/2013
Dr. Rahma Fitriani, S.Si., M.Sc,
Transportation Simplex Method
• Memanfaatkan notasi matriks untuk koefisien baris nol• Tableau yang digunakan adalah tableau dua arah seperti
pada pertemuan sebelumnya• Walaupun ada m+n kendala, hanya m+n-1 yang bebas• Tercermin dari struktur berikut:
nmBV vvvuuu 21321 Bc
m-1 kendala supply n kendala demand
01 u
• Dengan struktur tersebut, koefisien baris nol (fs obyektif) dari masalah transportasi untuk BV tertentu akan bersifat istimewa:
01 ijijBVij cac Bc
0
0
1
0
0
1
0
12
ijnjmiij cvvvuuuc
0 ijji cvu
ijji cvu
Untuk seluruh xij BV dan 01 u
• Koefisien baris nol untuk keseluruhan xij mempunyai bentuk:
zx
zx
x
cvuc
ij
ij
ij
ijjiij
nilai menaikkandapat NBV, :0
nilai menurunkandapat NBV, :0
BV:0
Langkah-langkah metode simpleks untuk Transportation Problem
• Langkah 1: Jika TP tidak balanced, dibuat agar balanced• Langkah 2: Gunakan salah satu metode (Northwest
Corner/Min Cost/Vogel) untuk menentukan BFS yang pertama (initial solution)
• Langkah 3: manfaatkan sifatijji cvu
Untuk seluruh BV dan 01 u
Untuk menentukan seluruh u dan v dari BFS yang ada• Langkah 4: Hitung koefisien baris nol pada seluruh sel.
Perhatikan kriteria optimalitas pada koefisien baris nol (kasus min),
• Langkah 4 (lanjut): • Jika ada sel dengan koefisien baris nol yang dapat
menurunkan z (bernilai +) pilih yang paling banyak menurunkan nilai z
• pilih xij sebagai BV yang baru, dengan memanfaatkan sifat looping (lebih detil pada contoh) pada tableu
• Langkah 5: dapatkan BFS yang baru, kembali ke langkah 3 dan 4
Permasalah Powerco dengan solusi awal menggunakan metode Northwest Corner
(Langkah 2) v 1 v2 v3 v4 Supply
u1 8 6 10 9 35 35u2 9 12 13 7 10 20 20 50u3 14 9 16 5
10 30 40
Demand 45 20 30 30
Tabel koefisien baris nol (Langkah 3)• Sementara abaikan nilai xij
• Pertahankan posisi sel letak BV (grey highlighted)• Cari solusi untuk seluruh u dan v secara bertahap untuk setiap BV
v 1 v2 v3 v4U1 8 6 10 9 U2 9 12 13 7 U3 14 9 16 5
811 vu
01 u
912 vu 1222 vu 1332 vu
1633 vu 543 vu
U1 0v 1 8 – 0=8
U2 9 – 8 =1
v 2 12 – 1=11
U3 16 – 12 =4
v 3 13 – 1=12 v4 5 –4=1
Perhitungan koefisien baris nol untuk seluruh sel (Langkah 4)
v 1 8v2 11v3 12v4 1u1 0 8 6 10 9 u2 1 9 12 13 7 u3 4 14 9 16 5
ijjiij cvuc
111111 cvuc
0+8-8=0
122112 cvuc
0+11-6=5
dst untuk semua sel
0+12-10=2
0+1-9=-8
1+8-9=0
1+11-12=0
1+12-13=0
1+1-7=-5
4+8-14=-2
4+11-9=6
4+12-16=0
4+1-5=0
Perhatikan semua BV mempunyai koefisien = 0
v 1 8v2 11v3 12v4 1u1 0 0 8 5 6 2 10 -8 9 u2 1 0 9 0 12 0 13 -5 7 u3 4 -2 14 6 9 0 16 0 5
• Belum optimal, karena belum semua (-)• Xij yang dapat digunakan sebagai BV berikutnya ada
pada sel yang dapat menurunkan z paling banyak• Koefisien baris nol paling positif (X32)
Kembali ke tableau yang memuat Xij
(Langkah 4 lanjut)
• Penentuan BV mana yang keluar menggantikan X32 menggunakan sistem looping untuk mempertahankan terpenuhinya supply dan demand
v 1 v2 v3 v4 Supplyu1 8 6 10 9 35 35u2 9 12 13 7 10 20 20 50u3 14 9 16 5
10 30 40
Demand 45 20 30 30
Kembali ke tableau yang memuat Xij
(Langkah 4 lanjut)
• Looping diawali dari X32 melewati sel-sel BV yang ada sebagai titik-titik pojok dan kembali ke X32 searah jarum jam
v 1 v2 v3 v4 Supplyu1 8 6 10 9 35 35u2 9 12 13 7 10 20 20 50u3 14 9 16 5
10 30 40
Demand 45 20 30 30
Kembali ke tableau yang memuat Xij
(Langkah 4 lanjut)
• Sel sebagai titik-titik pojok loop: dinyatakan sebagai sel ganjil dan genap• Sel X32 adalah awal diberi nomor 0
• Sel X22 adalah diberi nomor 1
• Sel X23 adalah diberi nomor 2
• Sel X33 adalah diberi nomor 3
v 1 v2 v3 v4 Supplyu1 8 6 10 9 35 35u2 9 12 13 7 10 20 20 50u3 14 9 16 5
10 30 40
Demand 45 20 30 30
Kembali ke tableau yang memuat Xij
(Langkah 4 lanjut)
• Alokasi perubahan adalah pada sel ganjil (yellow highlighted)• min(X22 , X33)=min(20 ,10)=10• Setiap sel genap (pink highlighted) tambah dengan 10• Setiap sel ganjil (yellow highlighted) kurangi dengan 10
v 1 v2 v3 v4 Supplyu1 8 6 10 9 35 35u2 9 12 13 7 10 20 20 50u3 14 9 16 5
10 30 40
Demand 45 20 30 30
10
10 30
10
Langkah 5: Tableau dengan BFS yang baru
v 1 v2 12v3 v4 Supplyu1 8 6 10 9 35 35u2 9 12 13 7 10 10 30 50u3 14 9 16 5 10 30 40Demand 45 20 30 30
• Kembali ke langkah 3 untuk menghitung seluruh u dan v bagi koefisien baris nol.
• Menentukan apakah sudah diperoleh solusi optimal berdasarkan kriteria optimalitas dari koefisien baris nol
• Sementara abaikan nilai xij
• Pertahankan posisi sel letak BV (grey highlighted)• Cari solusi untuk seluruh u dan v secara bertahap untuk setiap BV
Tabel koefisien baris nol (Langkah 3)
v 1 v2 V3 V4u1 8 6 10 9 u2 9 12 13 7 u3 14 9 16 5
811 vu
01 u
0
8 – 0 =8
912 vu
9 – 8 =1
1222 vu
12 – 1 =11
1332 vu
13 – 1 =12
923 vu
9 – 11 =- 2
543 vu
5 + 2 =7
Perhitungan koefisien baris nol untuk seluruh sel (Langkah 4)
v 1 8 v2 11 V3 12 V4 7u1 0 8 6 10 9 u2 1 9 12 13 7 u3 -2 14 9 16 5
ijjiij cvuc
111111 cvuc 122112 cvuc dst untuk semua sel
0+8-8=0
1+8-9=0 1+11-12=0 1+12-13=0
0+11-6=5 0+12-10=2 0+7-9=-2
1+7-7=1
-1+8-14=-7 -2+11-9=0 -2+12-16=-6 -2+7-5=0
Perhatikan semua BV mempunyai koefisien = 0
v 1 8v2 11v3 12v4 7u1 0 0 8 5 6 2 10 -2 9 u2 1 0 9 0 12 0 13 1 7 u3 -2 -8 14 0 9 -6 16 0 5
• Belum optimal, karena belum semua (-)• Xij yang dapat digunakan sebagai BV berikutnya ada
pada sel yang dapat menurunkan z paling banyak• Koefisien baris nol paling positif (X12)
Kembali ke tableau yang memuat Xij
(Langkah 4 lanjut)
v 1 v2 12v3 v4 Supplyu1 8 6 10 9 35 35u2 9 12 13 7 10 10 30 50u3 14 9 16 5 10 30 40Demand 45 20 30 30
• Penentuan BV mana yang keluar menggantikan X12 menggunakan sistem looping untuk mempertahankan terpenuhinya supply dan demand
Kembali ke tableau yang memuat Xij
(Langkah 4 lanjut)
v 1 v2 12v3 v4 Supplyu1 8 6 10 9 35 35u2 9 12 13 7 10 10 30 50u3 14 9 16 5 10 30 40Demand 45 20 30 30
• Looping diawali dari X12 melewati sel-sel BV yang ada sebagai titik-titik pojok dan kembali ke X12 searah jarum jam
Kembali ke tableau yang memuat Xij
(Langkah 4 lanjut)
v 1 v2 12v3 v4 Supplyu1 8 6 10 9 35 35u2 9 12 13 7 10 10 30 50u3 14 9 16 5 10 30 40Demand 45 20 30 30
• Sel sebagai titik-titik pojok loop: dinyatakan sebagai sel ganjil dan genap• Sel X12 adalah awal diberi nomor 0 • Sel X22 adalah diberi nomor 1
• Sel X21 adalah diberi nomor 2
• Sel X11 adalah diberi nomor 3
Kembali ke tableau yang memuat Xij
(Langkah 4 lanjut)
v 1 v2 12v3 v4 Supplyu1 8 6 10 9 35 35u2 9 12 13 7 10 10 30 50u3 14 9 16 5 10 30 40Demand 45 20 30 30
• Alokasi perubahan adalah pada sel ganjil (yellow highlighted)• min(X22 , X11)=min(10 ,35)=10• Setiap sel genap (pink highlighted) tambah dengan 10• Setiap sel ganjil (yellow highlighted) kurangi dengan 10
10
020
25
Langkah 5: Tableau dengan BFS yang baru
v 1 v2 12v3 v4 Supplyu1 8 6 10 9 25 10 35u2 9 12 13 7 20 30 50u3 14 9 16 5 10 30 40Demand 45 20 30 30
• Kembali ke langkah 3 untuk menghitung seluruh u dan v bagi koefisien baris nol.
• Menentukan apakah sudah diperoleh solusi optimal berdasarkan kriteria optimalitas dari koefisien baris nol
• Lakukan perhitungan koefisien baris nol sekali lagi• Cari loop sekali lagi• Diperoleh tableau berikut yang sudah optimal
Tableau Optimalv 1 v2 v3 v4 Supply
u1 8 6 10 9 10 25 35u2 9 12 13 7 45 5 50u3 14 9 16 5 10 30 40Demand 45 20 30 30
Tabel koefisien baris nol
v 1 6v2 6v3 10v4 2u1 0 -2 8 0 6 0 10 -7 9 u2 3 0 9 -3 12 0 13 -2 7 u3 3 -5 14 0 9 -3 16 0 5
Tidak ada lagi yang >0, sudah optimal
Tableau Optimalv 1 v2 v3 v4 Supply
u1 8 6 10 9 10 25 35u2 9 12 13 7 45 5 50u3 14 9 16 5 10 30 40Demand 45 20 30 30
Nilai Z: biaya minimum
10205301025610 i j
ijijXcZ