BAB 2 MODEL PERSOALAN LOKASI FASILITAS BERKAPASITAS 2.1 Pengertian Lokasi Fasilitas Pemilihan suatu lokasi merupakan hal yang sangat penting, karena faktor biaya dipengaruhi oleh fasilitas yang akan di tempatkan dan biaya juga mempengaruhi untuk menentukan lokasi dimana secara ekonomis dalam membiayai, produksi, transportasi dan distribusi serta biaya memasok kebutuhan untuk melayani permintaan dari pelanggan. Jadi untuk menempatkan suatu lokasi fasilitas merupakan suatu keputusan yang tepat agar dapat meminimalkan biaya, jika masingmasing fasilitas terbatas untuk melayani pelanggan maka persoalannya menjadi persoalan lokasi fasilitas berkapasitas, jika masing-masing fasilitas tidak terbatas untuk melayani pelanggan maka persoalannya menjadi persoalan lokasi tak berkapasitas (uncapacitated facility location problem disingkat dengan UFLP).
2.2 Model Persoalan Lokasi Fasilitas Berkapasitas Dalam persoalan program linear penyelesaian optimal dapat berupa bilangan real yang berarti bisa bilangan bulat atau bilangan pecahan. Jika pada penyelesaian pecahan dilakukan pembulatan ke bilangan bulat terdekat maka hasil yang diperoleh bisa tidak sesuai dengan hasil yang akan diharapkan. Diberbagai persoalan banyak memerlukan penyelesaian yang bulat sehingga dicari model penyelesaian dari suatu persoalan sedemikian hingga memperoleh penyelesaian optimum yang bulat atau penyelesaian integer yang optimum. Program integer merupakan pengembangan dari program linear, dalam per4
Universitas Sumatera Utara
soalan integer programming jika modelnya mengharapkan semua variabelnya bernilai integer maka disebut pure integer. Jika nilai variabel-variabel tertentu bernilai integer artinya varibelnya tidak semuanya bulat maka programnya disebut dengan program linear integer campuran atau Mixed Integer Linear Program (MILP). Biasanya persoalan lokasi fasilitas berkapasitas atau Capacitated Facility Location Problem (CFLP) disebut juga sebagai program linear integer campuran yang mempunyai model sebagai berikut : Z = min
XX
Ckj xkj +
k∈K j∈J
X
f j yj
(2.2.1)
j∈J
Dengan kendala : X
xkj = 1,
X
dk xkj ≤ sj yj ,
X
s j yj ≥ d k
∀k∈K
(2.2.2)
j∈J
∀j∈J
(2.2.3)
k∈K
(2.2.4)
j∈J
xkj − yi ≤ 0,
∀ k ∈ K,
0 ≤ xkj ≤ 1,
0 ≤ yj ≤ 1,
yj ∈ {0, 1} ,
∀j∈J ∀ k ∈ K,
(2.2.5) ∀j∈J
∀j∈J
(2.2.6) (2.2.7)
Dimana : Z
adalah fungsi tujuan
J
adalah himpunan semua lokasi fasilitas yang potensial
K
adalah himpunan semua pelanggan
Ckj
adalah biaya persediaan dan permintaan dk dari pelanggan ks′ dari fasilitas j
fj
adalah biaya operasi fasilitas j , dan kapasitas Cj jika dibuka 5
Universitas Sumatera Utara
yj = xkj
0 Jika fasilitas j ditutup 1 Jika fasilitas j dibuka adalah biaya permintaan pelanggan ks′ dari fasilitas j
Dan kendala persamaan (2.2.2) merupakan kendala permintaan kendala persamaan (2.2.3) merupakan kendala kapasitas kendala persamaan (2.2.4) merupakan kendala kapasitas secara keseluruhan kendala persamaan (2.2.5) merupakan penambahan batas implisit
Dengan asumsi : Ckj ≥ 0,
∀ k ∈ K dan j ∈ J
(2.2.8)
fj ≥ 0,
∀j∈J
(2.2.9)
sj > 0,
∀j∈J
(2.2.10)
dk ≥ 0,
∀k∈K
(2.2.11)
X
sj > d(K) =
j∈J
X
(2.2.12)
dk
k∈K
Dengan menerapkan relaksasi lagrangean kedalam permasalahan CFLP dengan mengabaikan kendala (2.2.2), maka model relaksasi lagrangean adalah : ZD (η) =
X
k∈K
ηk + min x,y
XX
(Ckj − ηk )xkj +
k∈K j∈J
X
f j yj
(2.2.13)
j∈J
Dengan kendala : X
dk xkj ≤ sj yj ,
X
sj yj ≥ d(K)
∀j∈J
(2.2.14)
k∈K
(2.2.15)
j∈J
6
Universitas Sumatera Utara
xkj − yj ≤ 0,
∀ k ∈ K,
∀j∈J
(2.2.16)
0 ≤ xkj ≤ 1,
∀ k ∈ K,
∀j∈J
(2.2.17)
0 ≤ yj ≤ 1,
∀j∈J
(2.2.18)
yj ∈ {0, 1} ,
∀j∈J
(2.2.19)
Jika kendala persamaan (2.2.2) diganti dengan pengali ηk dengan k ∈ K ma ka pengali lagrangean optimal yaitu η opt dapat ditentukan dari interval η min , η max
Dimana :
ηkmin = min {Ckj , j ∈ J\ {j(k)}} ≥ 0
(2.2.20)
Ckj (k) = min Ckj
(2.2.21)
ηkmax = max Ckj
(2.2.22)
j∈J
j∈J
Didefinisikan bahwa : Vj = max x
(
X
k∈K
) X (ηk − Ckj )xkj dk xkj ≤ sj , 0 ≤ xkj ≤ 1, ∀ k ∈ K (2.2.23) k∈K
Jika persamaan (2.2.23) direduksi ke dalam persamaan (2.2.13) diperoleh : ZD (η) = η0 +
X
(2.2.24)
ηk
k∈K
Dimana : η0 = min
(
X j∈J
) X (fj − vj )yj sj yj ≥ d(K), yj ∈ {0, 1} , ∀ k ∈ K
(2.2.25)
j∈J
Jadi lagrangean dari persamaan (2.2.13) adalah maksimum dari fungsi lagrangean ZD (η) pada himpunan η min , η max , selanjutnya : Misalkan :
7
Universitas Sumatera Utara
{y t , t ∈ T y }
xtj : t ∈ Tjx
adalah himpunan semua solusi yang feasibel untuk persamaan (2.2.25) dan
adalah himpunan semua solusi yang feasibel untuk persamaan (2.2.23)
Dan untuk semua t ∈ T y dan t ∈ Tjx didefinisikan : Ft =
X
fj yjt
(2.2.26)
j∈J
Ctj =
X
Ckj xtkj
(2.2.27)
k∈K
Dengan menggunakan persamaan (2.2.23) dan (2.2.25) maka persamaan (2.2.13) dapat ditulis menjadi : ZD = max η0 +
X
(2.2.28)
ηk
k∈K
Dengan kendala : η0 +
X
∀ t ∈ Ty
yjt vj ≤ Ft ,
(2.2.29)
j∈J
X
xtkj ηk − vj ≤ Ctj ,
∀ j ∈ J,
∀ t ∈ Tjx
(2.2.30)
k∈K
uj ≥ 0,
∀j∈J
ηkmin ≤ ηk ≤ ηkmax ,
(2.2.31) ∀k∈K
(2.2.32)
η0 ∈ R
(2.2.33)
Mengambil dua kali program master ganda diperoleh program master prima yang bentuknya adalah : ZD =
X
t∈T y
F t αt +
XX j∈J
Ctj βtj +
t∈Tjx
X
ηkmax pk − ηkmin pk
(2.2.34)
k∈K
8
Universitas Sumatera Utara
Dengan batasan : X
αt = 1
X
yjt αt −
(2.2.35)
t∈T y
βtj ≥ 0,
∀j∈J
(2.2.36)
t∈Tjx
t∈T y
XX
X
xtkj βtj + pk − pk ≥ 1,
∀k∈K
(2.2.37)
j∈J t∈Tjx
αt ≥ 0,
∀ t ∈ Ty
βtj ≥ 0,
∀ j ∈ J,
pk , pk ≥ 0,
(2.2.38) ∀ t ∈ Tjx
(2.2.39)
∀k∈K
(2.2.40)
Dimana : αt
adalah variabel rangkap dari persamaan (2.2.22)
βtj
adalah variabel rangkap dari persamaan (2.2.23)
pk dan pk adalah variabel rangkap dari persamaan (2.2.25)
9
Universitas Sumatera Utara
