MOHAMMAD NUR
PROGRAM LINIER
MODEL TRANSPORTASI
Digunakan untuk menyelesaikan
masalah pendistribusian barang dari beberapa tempat sumber ke beberapa tempat
tujuan secara optimal (biaya distribusi minimal)
Contoh kasus :
MG Auto memiliki 3 pabrik mobil di Los Angeles, Detroit dan New Orleans dan
2 distributor utama di Denver dan Miami. Jumlah produksi mobil tiap tiap pabrik
dalam satu tahun adalah 100 unit, 150 unit dan 50 unit. Permintaan kedua
distributor setiap tahunnya masing masing sejumlah 175 unit dan 125 unit.
Biaya pengiriman tiap unit mobil dari tiap pabrik ke tiap distributor ditunjukkan
pada matriks berikut :
Pabrik
|
Distributor
|
|
Denver
|
Miami
|
|
Los Angeles
|
$ 40
|
$ 50
|
Detroit
|
$100
|
$ 70
|
New Orleans
|
$ 60
|
$ 80
|
Tentukan pendistribusian yang optimal ( jumlah pengiriman mobil dari tiap
pabrik ke tiap distributor, dengan total biaya minimal )
Model PL dari masalah diatas dirumuskan sebagai berikut :
X1 = Jumlah mobil yang dikirim dari Los Angeles ke Denver
X2 = Jumlah mobil yang dikirim dari Los Angeles ke Miami
X3 = Jumlah mobil yang dikirim dari Detroit ke Denver
X4 = Jumlah mobil yang dikirim dari Detroit ke Miami
X5 = Jumlah mobil yang dikirim dari
New Orleans ke Denver
X6 = Jumlah mobil yang dikirim dari New Orleans ke Miami
Min Z = 40X1 + 50X2 + 100X3 + 70X4 + 60X5 + 80X6
Kendala :
X1 + X2 = 100
X3 + X4 = 150
X5 + X6 = 50
X1 + X3 + X5 = 175
X2 + X4 + X6 = 125
X1, X2,.............., X6 ≥ 0
Tahap penyelesaian kasus transportasi :
- Buat tabel transportasi
- Tentukan penyelesaian awal
- Lakukan cek optimalitas
- Lakukan perbaikan tabel
- kembali ke langkah 3
TABEL TRANSPORTASI
Sumber
|
Tujuan
|
|
||||
T1
|
T2
|
T3
|
.....
|
Tn
|
ai
|
|
S1
|
a11
X11
|
a12
X12
|
a13
X13
|
|
a1n
X1n
|
a1
|
S2
|
a21
X21
|
a22
X22
|
a23
X23
|
|
a2n
X2n
|
a2
|
S3
|
a32
X31
|
a32
|
|
|
|
a3
|
.
|
|
|
|
|
|
.
|
.
|
|
|
|
|
|
.
|
Sm
|
am1
Xm1
|
|
|
|
amn
Xmn
|
am
|
bj
|
b1
|
b2
|
b3
|
.......
|
bn
|
|
Keterangan :
Si = Tempat ke – i asal barang
Tj = Tempat ke – j tujuan barang
Xij = Jumlah barang yang akan didistribusikan dari Si ke Tj
aij = Biaya distribusi 1 unit barang dari Si ke Tj
ai = Jumlah seluruh barang dari Si
bj = Kapasitas penerimaan barang di Tj
Penyelesaian Awal
Syarat : =
Penyelesaian awal (pengisian tabel tahap pertama) dapat dilakukan dengan 3
cara :
- Metode North West Corner
- Metode Least Cost
- Metode Vogel
|
Distributor
|
|
|
Pabrik
|
Denver
|
Miami
|
ai
|
Los Angeles
|
40
|
50
|
100
|
Detroit
|
100
|
70
|
150
|
New Orleans
|
60
|
80
|
50
|
bj
|
175
|
125
|
|
Metode North West Corner
Pengisian sel dimulai dari
sudut kiri atas tabel (variable X11) ,
sebanyak banyaknya. Dilanjutkan ke sel berikutnya (X12 atau X21) yang
memungkinkan
Contoh :
|
Distributor
|
|
|
Pabrik
|
Denver
|
Miami
|
ai
|
Los Angeles
|
40
100
|
50
|
100
|
Detroit
|
100
75
|
70
75
|
150
|
New Orleans
|
60
|
80
50
|
50
|
bj
|
175
|
125
|
|
Biaya : 100(40) + 75(100) + 75(70) + 50(80) = 4000 + 7500 + 5250 + 4000
= 20750
Metode Least Cost
Pengisian sel dimulai dari sel yang mempunyai biaya terkecil, sebanyak
banyaknya
|
Distributor
|
|
|
Pabrik
|
Denver
|
Miami
|
ai
|
Los Angeles
|
40
100
|
50
|
100
|
Detroit
|
100
25
|
70
125
|
150
|
New Orleans
|
60
50
|
80
|
50
|
bj
|
175
|
125
|
|
Biaya : 100(40) + 25(100) + 125(70) + 50(60) = 4000 + 2500 + 8750 + 3000=
18250
Metode Vogel
Tahap tahap penyelesaian metode vogel adalah sebagai berikut :
- Tentukan selisih ongkos terkecil dan kedua terkecil dari tiap tiap baris dan tiap tiap kolom
- Pilih baris atau kolom yang memiliki selisih ongkos terbesar
- Isikan pada sel yang memiliki ongkos terkecil di baris atau kolom yang terpilih pada langkah 2
- lanjutkan sampai selesai
|
Distributor
|
|
|
|||
Pabrik
|
Denver
|
New York
|
Conecticut
|
Miami
|
ai
|
|
Los Angeles
|
30
75
|
70
25
|
100
|
50
|
100
|
20 20 20
|
Detroit
|
80
|
100
0
|
40
75
|
70
75
|
150
|
30 10 30
|
New Orleans
|
60
|
70
50
|
90
|
80
|
50
|
10 10 10
|
bj
|
75
|
75
|
75
|
75
|
|
|
|
30
30
|
0
0
0
|
50
|
20
20
20
|
|
|
Cek Optimalitas
Syarat :
Jumlah sel yang terisi : (m + n) – 1
m = jumlah baris tabel transportasi
n = jumlah kolom tabel transportasi
Cek optimalitas dapat dilakukan dengan 2 cara,
Metode Stepping Stone atau
Metode MODI (modified
distribution)
Metode Stepping Stone
|
Distributor
|
|
||||
Pabrik
|
Denver
|
Miami
|
ai
|
|||
Los Angeles
|
40
100
|
50
|
100
|
|||
Detroit
|
100
75
-
|
70
75
+
|
150
|
|||
New Orleans
|
60
+
|
80
50
-
|
50
|
|||
bj
|
175
|
125
|
|
Biaya : 100(40) + 75(100) + 75(70) + 50(80) = 4000 + 7500 + 5250 + 4000
= 20750
Periksa sel kosong :
c12 = 50 – 70 + 100 – 40 = 40
c31 = 60 – 100 + 70 – 80 = -50
karena cek pada c31 menghasikan nilai negatif (-), maka perlu dilakukan
perubahan tabel, sbb :
|
Distributor
|
|
|
Pabrik
|
Denver
|
Miami
|
ai
|
Los Angeles
|
40
100
|
50
|
100
|
Detroit
|
100
25
|
70
125
|
150
|
New Orleans
|
60
50
|
80
|
50
|
bj
|
175
|
125
|
|
Biaya : 100(40) + 25(100) + 125(70) + 50(60) = 4000 + 2500 + 8750 + 3000=
18250
Cek sel kosong :
c12 = 50 – 70 + 100 – 40 = 40
c32 = 80 – 60 + 100 – 70 = 50
Karena harga cij sudah tidak ada yang negatif, maka distrusi tersebut sudah
optimal
METODE MODI
|
Distributor
|
|
||||
Pabrik
|
Denver
|
Miami
|
ai
|
|||
Los Angeles
|
40
100
|
50
|
100
|
|||
Detroit
|
100
75
-
|
70
75
+
|
150
|
|||
New Orleans
|
60
+
|
80
50
-
|
50
|
|||
bj
|
175
|
125
|
|
Sel terisi : diperoleh persamann
c11 = u1 + v1 = 40
c21 = u2 + v1 = 100
c22 = u2 + v2 = 70
c32 = u3 + v2 = 80
harga setiap ui dan vj dengan memisalkan u1 = 0 , diperoleh :
v1 = 40, u2 = 60, v2 = 10 , u3 = 70
Sel kosong :
c12 = 50 – u1 – v2 = 50 – 0 – 10 = 40
c31= 60 – u3 – v1 = 60 – 70 – 40 = -50
karena cek pada c31 menghasikan nilai negatif (-), maka perlu dilakukan
perubahan tabel, sbb :
|
Distributor
|
|
|
Pabrik
|
Denver
|
Miami
|
ai
|
Los Angeles
|
40
100
|
50
|
100
|
Detroit
|
100
25
|
70
125
|
150
|
New Orleans
|
60
50
|
80
|
50
|
bj
|
175
|
125
|
|
Sel terisi : diperoleh persamaan
c11 = u1 + v1 = 40
c21 = u2 + v1 = 100
c22 = u2 + v2 = 70
c31 = u3 + v1 = 60
harga setiap ui dan vj dengan memisalkan u1 = 0 , diperoleh :
v1 = 40, u2 = 60, v2 = 10 , u3 = 20
Sel kosong :
c12 = 50 – u1 – v2 = 50 – 0 – 10 = 40
c32= 80 – u3 – v2 = 60 – 20 – 10 = 50
Karena harga cij sudah tidak ada yang negatif, maka distrusi tersebut sudah
optimal
TRANSPORTASI TAK SEIMBANG
Bila : #
Maka tabel perlu diseimbangkan dengan aturan :
Bila :
< maka tambahkan baris
dummy
Bila :
Syarat : > maka tambahkan kolom
dummy
seluruh sel dummy dikenakan biaya = 0
Contoh :
Asal
|
Tujuan
|
ai
|
||
A
|
B
|
C
|
||
P
|
4
|
9
|
7
|
100
|
Q
|
13
|
6
|
2
|
100
|
R
|
9
|
5
|
6
|
100
|
bj
|
90
|
125
|
125
|
|
= 300
= 340
Maka dilakukan perubahn tabel sbb:
Asal
|
Tujuan
|
ai
|
||
A
|
B
|
C
|
||
P
|
4
|
9
|
7
|
100
|
Q
|
13
|
6
|
2
|
100
|
R
|
9
|
5
|
6
|
100
|
Dummy
|
0
|
0
|
0
|
40
|
Bj
|
90
|
125
|
125
|
|
Contoh soal :Diketahui sebuah
tabel transportasi sebagai berikut; tentukan distribusi barang yang optimal
(penyelesaian awal dengan metode North west Corner, cek dengan Stepping Stone)
|
Tujuan
|
|
|||
Sumber
|
P
|
Q
|
R
|
S
|
ai
|
A
|
8
|
4
|
10
|
6
|
100
|
B
|
2
|
12
|
9
|
7
|
100
|
C
|
5
|
9
|
10
|
6
|
100
|
D
|
12
|
10
|
3
|
8
|
100
|
bj
|
80
|
110
|
120
|
90
|
|
|
Tujuan
|
|
|||
Sumber
|
P
|
Q
|
R
|
S
|
ai
|
A
|
8
|
4
|
10
|
6
|
100
|
B
|
2
|
12
|
9
|
7
|
100
|
C
|
5
|
9
|
10
|
6
|
100
|
D
|
12
|
10
|
3
|
8
|
100
|
bj
|
80
|
110
|
120
|
90
|
|
Latihan Soal
Jawablah seluruh soal berikut dengan langkah 2
yang lengkap dan jelas.
1. Metode Simplex
Dengan menggunakan Metode Simplex, tentukan nilai X1, X2,
X3 dan Z dalam model Linier Programming berikut :
Max Z = 28X1 + 10X2 + 30X3
Kendala :
- X1 + X2 60
- X2 + 2 X3 80
- X1 + X2 + X3 50
X1, X2, X3 0
- Metode Transportasi
Diketahui tabel transportasi dari sebuah kasus
pendistribusian barang dari 4 pabrik ke 3 Gudang penyimpanan sebagai berikut :
Pabrik
|
Gudang
|
Jumlah barang
yg akan didistribusikan
|
||
Surabaya
|
Jogya
|
Jakarta Barat
|
||
Bandung
|
200
|
100
|
70
|
50
|
Bogor
|
90
|
150
|
80
|
50
|
Sukabumi
|
60
|
10
|
09
|
50
|
Bekasi
|
50
|
20
|
60
|
50
|
Kapasitas Gudang
|
60
|
60
|
80
|
|
- Tentukan pendistribusian barang dari tiap pabrik ke tiap gudang yang optimal
- Hitung biaya total pendistribusian
Sangat membantu postingannya,
BalasHapusTapi boleh tau tdk ini referensinya dari buku apa ?
Soalnya saya sedang butuh referensinya untuk penulisan penelitian.
Terima kasih