Permasalahan dalam linear programming pada umumnya adalah sebagai berikut:
Terdapat dua atau lebih produk yang dibentuk dari campuran dua atau lebih bahan. Terdapat mesin atau fasilitas lain yang digunakan dalam manufaktur berbagai macam produk, dan kapasitasnya terbatas, atau bahan pembentuk produk terbatas. Untuk itu, kita harus memperhitungkan keuntungan yang kita dapatkan dalam memproduksi masing‐masing produk dan keuntungan total yang kita dapatkan. Bentuk Standar dari Linear Programming pada umumnya adalah sebagai berikut:
Aktifitas 2 ….
Sumber daya
1
A B … m
aA1 aB1 … am1
aA2 aB2 … am2
Unit aktifitas Level aktivitas
c1 x1
c2 x2
Maksimalisasi: Z = c1x1 + c2x2 + … + cnxn
n
Jumlah sumberdaya yang ada
… … … …
aAn Abn … amn
b1 b2 … bm
… …
cn xn
101 Dengan kendala: aA1x1 + aA2x2 aB1x1 + aB2x2 … am1x1 + am2x2
+ … + …
+ aAnxn + aBnxn
≤ b1 ≤ b2
+ …
+ amnxn
≤ bm
dan, x1 ≥ 0, x2 ≥ 0, …, xn ≥ 0
Contoh: (Maksimalisasi) PT. Mocin Bodong adalah produsen kendaraan bermotor berkualitas ecek‐ecek dengan banyak lini produk, termasuk becak motor, berbagai jenis skutik dan motor sport. Karena penurunan pendapatan, manajemen perusahaan memutuskan untuk merubah lini produknya. Beberapa produk yang tidak menguntungkan tidak diproduksi lagi, dan keputusan ini akan menyebabkan kapasitas produksi yang ada semuanya digunakan untuk memproduksi salah satu atau kedua produk potensial yang banyak diminta di pasar. Kedua produk tersebut adalah skubek dan skutrail. Dari hasil penelitian manajemen, perusahaan sangat pede untuk bisa menjual semua hasil produksinya yang dihasilkan dengan kapasitas produksinya. PT Mocin Bodong mempunyai 3 pabrik, Pabrik 1 dan 2 digunakan untuk pencetakan body dan spare parts, sedangkan pabrik 3 digunakan untuk perakitan. Profil linear programming‐nya menjadi sebagai berikut: PT. Mocin Bodong
Pabrik
Produk Skubek Skutrail
1 2 3
1 0 3
0 2 2
Unit profit
300
500
Maksimalisasi: Z = 300A + 500B
Kapasitas Produksi 4 12 18
102 Tetapi proses mendapatkan keuntungan sebesar‐besarnya tersebut mempunyai kendala yang berupa kapasitas produksi dari masing‐masing pabrik, dimana pabrik 1 membutuhkan 1 unit satuan bahan baku untuk suku cadang A dan kapasitas produksinya adalah 4. Pabrik 2 membutuhkan 2 unit satuan bahan baku untuk suku cadang B dan kapasitas produksinya adalah 12. Sedangkan pabrik 3 membutuhkan 3 satuan waktu untuk merakit A dan 2 satuan waktu untuk merakit B dan kapasitas produksinya adalah 18. Dapat kita bentuk model sebagai berikut: A =4 2B = 12 3A + 2B = 18
(1) (2) (3)
Persamaan linear sederhana dapat kita kerjakan sebagai berikut: Hitungan 1: (3) 3A + 2B = 18 x 1 3A + 2B = 18 (1) A = 4 x 3 3A = 12 2B =6 B =3 3A + 2 (3) = 18 3A = 12 A =4 Z = 300 (4) + 500 (3) Z = 2.700
Hitungan 2: (3) 3A + 2B = 18 (2) 2B = 12 3A =6 A =2 3 (2) + 2B = 18 2B = 12 B =6 Z = 300 (2) + 500 (6) Z = 3.600
Dari kedua perhitungan tersebut kita mendapatkan 2 hasil yang berbeda, dengan hambatan yang ada, ada 2 kemungkinan produksi, yaitu: 1. Produksi A = 4 dan B = 3, dengan profit sebesar 2.700. 2. Produksi A = 2 dan B = 6, dengan profit sebesar 3.600. Secara logis kita akan memilih alternatif kedua yang menghasilkan profit lebih tinggi, yaitu dengan memproduksi A sebanyak 2 unit dan B sebanyak 6 unit, dengan total keuntungan sebesar 3.600.
103
Soal-soal: 1. Sebuah pabrik pembuat boneka akan memproduksi boneka Si Unyil dan Pak Ogah dengan menggunakan dua mesin. Waktu yang diperlukan untuk memproduksi kedua boneka ini dapat dilihat pada tabel berikut: Jenis
Waktu yang dibutuhkan untuk membuat Sebuah Boneka (menit)
Boneka
Mesin I
Mesin II
Si Unyil Pak Ogah
20 10
10 20
Mesin I dan mesin II masing‐masing beroperasi 8 jam per hari. Jika pabrik tersebut menjual boneka Si Unyil dan boneka Pak Ogah dengan keuntungan masing‐masing Rp10.000 dan Rp 8.500 per buah, buatlah model matematika dari permasalahan ini agar pabrik tersebut dapat memperoleh keuntungan sebesar‐besarnya! 2. Dengan modal Rp 450.000, Pak Jupri membeli pepaya seharga Rp 1.000 dan jeruk seharga Rp 3.500 per kilogram. Buah‐buahan ini dijualnya kembali dengan menggunakan gerobak yang dapat memuat maksimum 300 kg. Jika keuntungan dari penjualan pepaya Rp 500 per kilogram dan dari penjualan jeruk Rp 1.000 per kilogram, tentukanlah keuntungan maksimum yang diperoleh Pak Jupri!
Metode grafik tidak dapat menyelesaikan persoalan linear program yang memiliki variabel keputusan yang cukup besar atau lebih dari dua, maka untuk menyelesaikannya digunakan Metode Simpleks. Metode simpleks adalah suatu prosedur aljabar (yang bukan secara grafik) untuk mencari nilai optimal dari fungsi tujuan dalam masalah optimasi yang terkendala. Perhitungan dalam metode simpleks didasarkan pada aljabar matriks, terutama mencari invers matirks untuk penyelesaian persamaan linier simultan, oleh karena itu penyelesaian optimal dengan metode simpleks diawali pengubahan kendala pertidaksamaan menjadi persamaan. Untuk mencari nilai optimum dengan menggunakan metode simpleks dilakukan dengan proses pengulangan (iterasi) dimulai dari penyelesaian dasar awal yang layak (feasible) hingga penyelesaian dasar akhir yang layak dimana nilai dari fungsi tujuan telah optimum
Persyaratan Metode Simpleks Terdapat tiga persayaratan untuk memecahkan masalah linier programing, yaitu: a. Semua kendala pertidaksamaan harus diubah menjadi persamaan. b. Sisi kanan dari tanda pertidaksamaan kendala tidak boleh ada nilai negatif. c. Semua variabel dibatasi pada nilai non negatif.
105
Penulisan Standar dari Metode Simpleks Berdasarkan ketiga persyaratan di atas, maka kita dapat menulis bentuk standar dari metode simpleks sebagai berikut:
Fungsi Tujuan Maksimisasi Sebagai contoh untuk dua variabel dan dua kendala: Maksimumkan:
Z = C1 X1 + C2 X2
Dengan Kendala:
a11 X 1 a12 X 2 K1 a21 X 1 a 22 X 2 K 2 X 1 0 dan X 2 0 Bentuk standar metode simpleks di atas dapat ditulis menjadi: a. Fungsi tujuan bentuk eksplisit diubah menjadi bentuk implisit. -Z + C1 X1 + C2 X2 = 0 b. Kendala bentuk pertidaksamaan (tanda ) diubah menjadi persamaan dengan cara menambahkan variabel slack pada ruas kiri, sehingga menjadi:
a11 X 1 a12 X 2 S1 K1 a21 X 1 a22 X 2 S 2 K 2 dimana: S1 dan S2 adalah variabel slack (non negatif). c. Dalam notasi matriks, kita peroleh:
1 C1 C2 0 0 0 a11 a22 1 0 0 a21 a22 0 1
X 0 1 X 2 K1 S1 K 2 S1
106 d. Tabel Simpleks Pertama Variabel Dasar
Z
X1
X2
Z
-1
+C1
+C2
0
0
0
S1
0
a11
a12
1
0
K1
S2
0
a21
a22
0
1
K2
S1
Nilai kanan (konstanta)
S2
Fungsi Tujuan Minimalisasi Minimumkan: C = c1 X1 + c2 X2 Dengan kendala:
a11 X 1 a 22 X 2 K1 a11 X 1 a 22 X 2 K 2 X 1 0 dan X 2 0 Bentuk standar metode simpleks dapat ditulis menjadi: a. Fungsi tujuan semula bentuk eksplisit diubah menjadi bentuk implisit: - C + c1 X1 + c2 X2 = 0 b. Kendala pertidaksamaan (tanda ) Diubah menjadi persamaan dengan cara dikurangi variabel slack kemudian ditambah variabel buatan: a11 X1 + a12 X2 – S1 + A1 = K1 a21 X1 + a22 X2 - S2 + A2 = K2 dimana: S1 dan S2 adalah variabel slack A1 dan A2 adalah variabel buatan c. Dalam notasi matriks, kita peroleh:
107
1 c1 c2 0 0 0 0 0 a11 a12 1 0 1 0 0 a 21 a 22 0 0 1 1
C X 1 X 2 0 S1 K1 S 2 K 2 A1 A 2
d. Tabel Simpleks Pertama Variabel Dasar
C
X1
X2
S1
S2
A1
A2
Nilai kanan (konstanta)
-1
+c1
+c2
0
0
0
0
0
S1
0
a11
a12
-1
0
1
0
K1
S2
0
a21
a22
0
-1
0
1
K2
Contoh-contoh: 1. Masalah Maksimalisasi Dengan Kendala Bentuk Baku (Semua Kendala Bertanda ≤): Maksimumkan
Z = 8000 X1 + 7000 X2
Dengan kendala:
2 X 1 3 X 2 24 2 X 1 X 2 16 X 1 4 X 2 27 X 1 0 dan X 2 0
108 Langkah Membentuk Tabel Simpleks I: a. Fungsi tujuan dalam bentuk implisit: - Z + 8000 X1 + 7000 X2 = 0 b. Karena masalah maksimalisasi, maka kendala ditambah variabel slack:
2 X 1 3 X 2 S1 24 2 X 1 X 2 S 2 16 X 1 4 X 2 S3 27 c. Tabel Simpleks I (awal) Variabel Z X1 Dasar
8000
X2
S1
S2
S3
Nilai kanan (konstanta)
7000
0
0
0
0
Baris 1 = Z
-1
Baris 2 = S1
0
2
3
1
0
0
24
Baris 3 = S2
0
2
1
0
1
0
16
Baris 4 = S3
0
1
4
0
0
1
27
Kolom kunci adalah kolom X1 dan Baris kunci adalah baris 3. Langkah Membentuk Tabel Simpleks II: a. Kolom kunci adalah kolom yang berada pada angka positif terbesar dalam baris pertama, yaitu kolom X1. b. Baris kunci adalah: Baris 2 =
Nilai kanan ( NK ) 24 12 Angka kolom kunci ( AKK ) 2
Baris 3 =
Nilai kanan 16 8 positif terkecil Angka kolom kunci 2
109
Baris 4 =
Nilai kolom 27 27 Angka kolom kunci 1
Baris kunci adalah baris 3. c. Baris kunci baru (baris 3 baru): Baris kunci lama: X2 S1 Z X1 0
2
1
0
S2
S3
NK
1
0
16
Baris kunci baru = Baris lama dibagi angka kunci 0 1 ½ 0 ½ 0
8
d. Baris lain yang baru Baris (1) Baru = Baris (1) lama – (Baris kunci baru x 8000) Baris (2) Baru = Baris (2) lama – (Baris kunci baru x 2) Baris (4) Baru = Baris (4) lama – (Baris kunci baru x 1) e. Tabel Simpleks II Variabel
Z
X1
Baris (1) = Z
-1
Baris (2) = S1
Nilai
X2
S1
S2
S3
0
3000
0
-4000
0
-64.000
0
0
2
1
-1
0
8
Baris (3) = X1
0
1
½
0
½
0
8
Baris (4) = S3
0
0
3,5
0
-½
0
19
Dasar
Langkah Membentuk Tabel Simpleks III: a. Kolom kunci = Kolom X2 b. Baris kunci =
Kanan
110
Baris 2 =
NK 8 4 positif terkecil AKK 2
Baris 3 =
NK 8 16 AKK 1 / 2
Baris 4 =
NK 19 5,43 AKK 3,5
Baris kunci adalah baris 2. c. Baris kunci baru (baris 2 baru) = Z X1 X2 S1 0
0
1
½
S2
S3
NK
-½
0
4
d. Baris lain yang baru = Baris (1) Baru = Baris (1) lama – (Baris kunci baru x 3000) Baris (3) Baru = Baris (3) lama – (Baris kunci baru x ½) Baris (4) Baru = Baris 94) lama – (Baris kunci baru x 3,5)
e. Tabel Simpleks III Variabel
Nilai
Z
X1
X2
Baris (1) = Z
-1
0
0 -1500 -2500 0
Baris (2) = X2
0
0
1
½
-½
0
4
Baris (3) = X1
0
1
0
-1/4
¾
0
6
Baris (4) = S3
0
0
0
-7/4
5/4 1
5
Dasar
S1
S2
S3
Kanan -76.000
Karena pada baris (1) tidak ada lagi yang bernilai positif, penyelesaian optimal selesai. X1 = 6 ; X2 = 4 ; - Z = -76.000 Z = 76.000
111 Soal-soal: 1. Fungsi tujuan, maksimumkan: Z = 3X1 + 5X2 Kendala: a. 2X1 <= 8 b. 3X2 <= 15 c. 6X1 + 5X2 <= 30 2. Maksimumkan: Z = 400X1 + 300X2 Fungsi kendala: a. 4X1 + 6X2 <= 1200 b. 4X1 + 2X2 <= 800 c. X1 <= 250 d. X2 <= 300
2. Masalah Minimalisasi Dengan Kendala Bentuk Baku (Semua Kendala Bertanda ≥): Minimumkan:
C = 6X1 + 24X2
Kendala:
X1 + 2X2 ≥ 3 X1 + 4X2 ≥ 4
Dan
X1, X2 ≥ 0
Penyelesaian: Langkah membentuk Tabel Simpleks I: 1. Penyesuaian Fungsi tujuan dan Kendala: Minimisasi:
C = 6X1 + 24X2 + MA1+ MA2
Kendala
X1 + 2X2 –S1 + A1 = 3
:
X1 + 4X2 – S2+ A2 = 4 Keterangan:
S1, S2: Variabel Slack A1,A2: Variabel Buatan
112 2. Penyesuaian Fungsi tujuan agar siap masuk pada Tabel Simpleks I, karena nilai M akan dianggap Nol. a. Fungsi Tujuan dalam bentuk Implisit -C + 6X1 + 24X2 + MX1 + MX2 = 0 b. Penyesuain Fungsi Tujuan: Fungsi Tujuan
X1
X2
S1
S2
A1
A2
NK
Cj-Zj
6
24
0
M
0
M
0
Kendala (1) x M
1M
2M
-M
M
0
0
3M
(6-M) (24-2M) M
0
0
M
-3M
0
0
-M
M
4M
(6-2M) (24-6M) M
0
M
0
-7M (nilai M =0)
Cj-Zj Kendala (2) xM
1M
Cj-Zj
4M
c. Tabel Simpleks I Variabel Dasar
X1
X2
Cj-Zj
(6-2M) (24-6M)
S1
S2
A1
A2
NK
M
0
M
0
0
A1
1
2
-1
1
0
0
3
A2
1
4
0
0
-1
1
4
Langkah Membentuk Tabel Simpleks II: 1. Kolom Kunci: Kolom X2 (Negatif terkecil) 2. Baris Kunci: Baris 3: NK/AKK = 3/2 = 1,5 Baris 3: NK/AKK = 4/4 = 1 ...Baris Kunci 3. Baris Kunci Baru (BKB = BL/AK); 4. Baris lain (Baris 1 dan Baris 2) yang baru; 5. Tabel Simpleks II:
113 Variabel Dasar Cj-Zj
X1
X2
S1
S2
A1
A2
NK
(-1/2M)
0
M
0 (6-1/2M) (-6+3/2M)
(-24+6M)
A1
½
0
-1
1
½
-1/2
1
A2...X2
¼
1
0
0
-1/4
1/4
1
Langkah Membentuk Tabel Simpleks III: 1. Kolom Kunci: Kolom X1(Negatif terkecil) 2. Baris Kunci: Baris 2: NK/AKK = 1/(1/2)=2..Baris Kunci Baris 3: NK/AKK = 1/(1/4) = 4. 3. Baris Kunci Baru (BKB = BL/AK); 4. Baris lain (Baris 1 dan Baris 3) yang baru. 5. Tabel Simpleks III: Variabel Dasar
X1
X2
S1
S2
A1
A2
NK
Cj-Zj
0
0
0
M
6
(-6+M)
(-24+7M)
A1...X1
1
0
-2
2
1
-1
2
X2
0
1
½
2/4
1/2
Titik Optimal: X1 = 2 ; X2 = ½; -Zj = -24+7M.... Zj=C= 24.
-1/2 -2/4
Pendahuluan Persoalan transportasi merupakan bentuk khusus pemrograman linier yang membahas masalah pendistribusian atau pengalokasian suatu komoditas atau produk dari sejumlah sumber (supply) kepada sejumlah tujuan (destination, demand), dengan tujuan meminimumkan ongkos pengangkutan yang terjadi. Beberapa jenis persoalan pemrograman linier dipecahkan dengan menggunakan prosedur perhitungan yang lebih efisien bila dibandingkan metode simpleks, salah satu diantaranya adalah metode transportasi. Persoalan transportasi pada umumnya terpusat pada pemilihan rute dalam jaringan distribusi produk antara pusat industri (pabrik) dan distribusi gudang atau antara distribusi gudang regional dan distribusi lokal (pasar). Selain itu juga dapat berupa penggabungan dari kedua jaringan distribusi tersebut, yaitu pendistribusian dari pusat ke gudang diteruskan distribusi ke distribusi pengeluaran lokal (pasar). Selain masalah-masalah pendistribusian, model transportasi dapat juga digunakan untuk menyelesaikan masalah-masalah penjadualan produksi dan juga masalah inventory. Dalam menggunakan metode transportasi ini pihak manajemen/perusahaan mencari rute pendistribusian barang/produk yang nantinya akan dapat mengoptimalkan suatu tujuan tertentu dari perusahaan yang bersangkutan. Misalnya tujuan untuk meminimumkan total biaya transportasi, meminimumkan waktu yang digunakan dalam pendistribusian, atau tujuan memaksimumkan laba. Persoalan transportasi mempunyai ciri-ciri khusus sebagai berikut: 1. Terdapat sejumlah sumber dan tujuan tertentu 2. Kuantitas komoditas atau barang yang distribusikan dari setiap sumber dan yang diminta oleh setiap tujuan, besarnya tertentu.
115 3. Komoditas yang dikirim atau diangkut dari suatu sumber ke suatu tujuan, besarnya sesuai dengan permintaan dan atau kapasitas sumber. 4. Ongkos pengakutan komoditas dari suatu sumber ke suatu tujuan, besarnya tertentu.
Model Transportasi Secara diagramatik, model transportasi dapat digambarkan sebagai berikut: Misalkan ada m buah sumber dan n buah tujuan.
Gambar 11.1. Model Transportasi -
Masing-masing sumber mempunyai kapasitas ai , i = 1, 2, 3,...,m Masing-masing tujuan membutuhkan komoditas sebanyak bj j = 1, 2, 3,….,n. Jumlah satuan (unit) yang dikirimkan dari sumber i ke tujuan j adalah sebanyak xij. Ongkos pengiriman per unit dari sumber I ke tujuan j adalah cij
116 Dengan demikian, maka formulasi pemrograman liniernya adalah sebagai berikut: m n
Minimumkan:
z = c ij x ij i 1 j1
Berdasarkan pembatas:
n x ij a i , j1
i 1, 2,..., m
m x a j, i 1 ij
i 1, 2,..., n
x ij 0 untuk seluruh i dan j
Sebagai ilustrasi, jika ada 2 buah sumber dan 3 tujuan (m = 2, n = 3)
Gambar 11.2. Ilustrasi Model Transportasi Formulasi: Minimumkan: z = c11.x11 + c12.x12 + c13. x13 + c21.x21 + c22.x22 + c23.x23 Berdasarkan pembatas: x11 + x12 + x13 = a1 Pembatas sumber x21 + x22 + x23 = a2 x11 + x21 = b1 x12 + x22 = b2 Pembatas tujuan x13 + x23 = b3
117 Sedangkan tabel pemrograman liniernya adalah: Persamaan tujuan Pembatas Sumber Pembatas Sumber
z
x11
x12
x13
x21
x22
x23
Solusi
1 0 0 0 0 0
-c11 1
-c12 1
-c13 1
-c21
-c22
-c23
1 1
1
1
0 a1 a2 b1 b2 b3
1 1
1 1
1
Tabel 11.1. Tabel pemrograman linier model Transportasi Semua koefisien teknologis akan berharga nol atau satu (lihat tabel di atas), dan ni merupakan karakter/sifat model transportasi. Dari tabel di atas kita juga tidak dapat melihat solusi awal secara jelas, karena itu pada persoalan transportasi tidak lagi digunakan tabel seperti itu, tetapi diganti dengan tabel sebagai berikut:
1 Sumber (i)
1 2
Demand
c11 x11 c21 x21 b1
Tujuan (j) 2 c12 x12 c22 x22 b2
Supply 3 c13 x13 c23 x23
a1 a2
b3
Tabel 11.2. Tabel matriks persoalan transportasi Dengan demikian, walaupun persoalan transportasi ini dapat diselesaikan dengan metode simpleks, tetapi karena sifat-sifatnya yang khusus itu, maka dapat disusun suatu prosedur yang jauh lebih sederhana, yang secara sepintas lalu seakan-akan tidak ada hubungannya dengan metode simpleks.
Keseimbangan Dalam Model Transportasi Suatu model transportasi dikatakan seimbang apabila total supply (sumber) sama dengan total demand (tujuan). Dengan kata lain: m n ai bj i 1 j1
118 Dalam persoalan yang sebenarnya, batasan ini tidak selalu terpenuhi; atau dengan kata lain, jumlah supply yang tersedia mungkin lebih besar atau lebih kecil daripada jumlah yang diminta. Jika hal ini terjadi, maka model persoalannya disebut sebagai model yang tidak seimbang (unbalanced). Batasan di atas dikemukakan hanya karena ia menjadi dasar dalam pengembangan teknik transportasi. Namun, setiap persoalan transportasi dapat dibuat seimbang dengan cara memasukan artificial variable (semu). Dimana jika jumlah demand melebihi jumlah supply, maka dibuat suatu sumber dummy yang akan mensupply kurangan tersebut, yaitu sebanyak: j b j i a i
Sebaliknya, jika jumlah supply melebihi jumlah demand, maka dibuat suatu tujuan dummy untuk menyerap kelebihan tersebut, yaitu sebanyak: i b i j a j
Ongkos transportasi per unit (cij) dari sumber dummy keseluruh tujuan adalah nol. Hal ini dapat dipahami karena pada kenyataannya dari sumber dummy tidak terjadi pengiriman. Begitu pula dengan ongkos transportasi per unit (cij) dari semua sumber ke tujuan dummy adalah nol. Jika pada persoalan transportasi dinyatakan bahwa dari sumber ke k tidak dilakukan atau tidak boleh terjadi pengiriman ke tujuan ke 1, maka nyatakanlah ck1 dengan suatu harga M yang besarnya tidak terhingga (ingat teknik M pada metode simpleks). Hal ini dilakukan agar dari k ke 1 itu benar-benar tidak terjadi pendistribusian komoditas.
Metode Pemecahan Untuk menyelesaikan persoalan transportasi, harus dilakukan langkahlangkah sebagai berikut: 1. Tentukan solusi fisibel basis awal, 2. Tentukan entering variable dari variable-variabel nonbasis, bila semua variabel sudah memenuhi kondisi optimum, STOP, bila belum, lanjutkan ke langkah 3. 3. Tentukan leaving variable diantara variabel-variabel basis yang ada, kemudian hitung solusi yang baru. Kembali ke langkah 2.
119
Menentukan Solusi Fisibel Basis Awal Terdapat tiga metode yang biasa digunakan untuk menentukan solusi fisibel basis awal: a. Metode pojok kiri atas-pojok kanan bawah (North West Corner) Caranya adalah sebagai berikut: Mulai dari pojok kiri atas, alokasikan sebesar x11 = min (a1,b1). Artinya: jika b1 < a1 maka x11 = b1 ; jika b1 > a1, maka x11 = a1. Kalau x11 = b1, maka selanjutnya yang menjadi yang mendapat giliran untuk dialokasikan adalah x12 sebesar min(a1 – b1,b2); kalau x11 = a1 (atau b1 > a1), maka selanjutnya yang mendapat giliran untuk dialokasikan adalah x21 sebesar min(b1-a1, a2), demikian seterusnya. b. Metode ongkos terkecil (Least Cost) Prinsip cara ini adalah pemberian prioritas pengalokasian pada tempat yang mempunyai satuan ongkos terkecil. Dengan mengambil ongkos terkecil. c. Metode pendekatan Vogel (Vogel’s approximation method, VAM) Cara ini merupakan cara yang terbaik di bandingkan dengan kedua cara diatas. Langkah-langkah pengerjaannya adalah: 1. Hitung Penalty untuk tiap kolom dan baris dengan jalan mengurangkan elemen ongkos terkecil dari yang kedua terkecil. 2. Selidiki kolom atau baris dengan Penalty terbesar. Alokasikan sebanyak mungkin pada variabel dengan ongkos terkecil, sesuiakan supply dengan demand, kemudian tandai kolom atau baris yang sudah terpenuhi. Kalau ada 2 buah kolom atau baris yang terpenuhi secara simultan, pilih salah satu untuk di tandai, sehingga supply atau demand pada baris atau kolom yang tidak terpilih adalah 0. Setiap baris atau kolom denagan supply atau dimana = 0, tidak akan terbawa lagi dalam perhitungan Penalty berikutnya. 3. Selanjutnya: a) Tinggal satu kolom atau baris yang belum di tandai, STOP. b) Bila tinggal satu kolom atau baris dengan supply atau demand positif yang belum di tandai, tentukan variabel basis pada kolom atau baris dengan cara ongkos terkecil. c) Bila semua baris dan kolom yang belum di tandai mempunyai supply dan diman = 0, tentukan varibel-varibel basis yang berharga 0 dengan cara ongkos terkecil kemudian STOP.
120 d) Jika 3a, b, dan c tidak terjadi hitung kembali Penalty untuk baris dan kolom yang belum di tandai kembali ke no.2.
Menentukan Entering Variabel dan Leaving Variabel Menentukan Entering dan Leaving Variable adalah tahap berikutnya dari teknik pemecahan persoalan transportasi, setelah solusi visible basis awal diperoleh. Ada 2 cara yang bisa dipergunakan dalam menetukan Entering dan Leaving Variable yaitu dengan menggunakan metode Stepping Stone atau metode Multipliers. a. Metode Stepping Stone Untuk menentukan entering dan leaving variabel ini, terlebih dahulu harus di buat suatu loop tertutup bagi setiap variabel non basis loop tersebut berawal dan berakhir pada variable nonbasis tadi, dimana tipa sudut loop haruslah merupakan titik-titik yang ditempati oleh variabelvariabel basis dalam tabel transportasi. b. Metode multiplier Cara ini iterasinya sama seperti Stepping Stone. Perbedaan utama terjadi pada cara pengevaluasian variabel non basis, atau penentuan penurunan ongkos transport per unit untuk tiap variabel. Cara ini dikembangkan berdasarkan teori dualitas. Untuk tiap basis I dari tabel transformasi di kenal sutu Multiplier ui , dan untuk kolom j disebut mulitiplier
v j sehingga untuk tiap variabel basis X ij didapat persamaan: uj + vj + cij Dari persamaan di atas kita dapat menghitug beberapa penurunan ongkos transportasi perunit untuk tiap variabel nonbasis xij sebagai berikut: cij = xij – ui - vj Langkah selanjutnya adalah seperti iterasi yang dilakukan oleh metode stepping stone.
121 Contoh: Sebuah perusahaan mempunyai tiga buah tempat perakitan mobil di A, B, dan C. Perusahaan tersebut mempunyai 2 buah pusat distribusi di D dan E. Kapasitas produksi A, B, dan C untuk periode yang akan datang adalah 1000, 1500, dan 1200 unit, sedangkan permintaan pusat distribusi D dan E untuk periode yang akan datang adalah 2300 dan 1400 unit. Biaya pengangkutan per unit dari A, B, dan C ke D dan E adalah seperti pada tabel.
A B C Total Suplai = 1000 + 1500 + 1200 = 3700 Total permintaan = 2300 + 1400 = 3700
D
E
80 100 102
215 108 68
model dalam keadaan seimbang
Model Pemrograman Linier dari persoalan tersebut: Fungsi tujuan: min. Kendala Sumber:
Kendala Tujuan:
Z = 80x11+215x12+100x21+108x22+102x31+ 68x32 x11 + x12 x21 + x22 x31 + x32 x21 + x31 x11 + x12 + x22 + x32 xij 0
= 1000 = 1500 = 1200 = 2300 = 1400
i = 1,2,3 j = 1,2
Jika kita selesaikan dengan metode simpleks maka kita membuat tabel simpleks yang jumlah kolomnya adalah sebanyak i x j (jumlah variabel keputusan) + i + j (jumlah variabel buatan), sedangkan jumlah baris kendala dan baris tujuan dan i + j baris kendala
122 V.D.
x11
x12
x21
x22
x31
x32
R1
R2
R3
R4
R5
R.K.
Z
-80
-215
-100
-108
-102
-68
0
0
0
0
0
0
2M
2M
2M
2M
2M
2M
0
0
0
0
0
7400M
R1
1
1
0
0
0
0
1
0
0
0
0
1000
R2
0
0
1
1
0
0
0
1
0
0
0
1500
R3
0
0
0
0
1
1
0
0
1
0
0
1200
R4
1
0
1
0
1
0
0
0
0
1
0
2300
R5
0
1
0
1
0
1
0
0
0
0
1
1400
Persoalan seperti ini lebih efektif diselesaikan dengan teknik transportasi. Sekarang kita tulis persoalan tersebut dengan tabel transportasi. Kita jadikan kotak yang besar tempat variabel xij dan kotak yang kecil tempat biaya transportasi Cij.
Jumlah suplai:
Jumlah permintaan
80 x11 100 x21 102 x31 2300
215 x12 108 x22 68 x32 1400
1000 1500 1200
Kita tidak selalu mempunyai jumlah sumber yang sama dengan jumlah tujuan. Agar kita dapat menyelesaikan dengan teknik transportasi maka model dibuat seimbang.
- Jika kelebihan suplai maka tambahan tujuan semu yang akan menampung ai b j kelebihan suplai yang permintaannya =
- Jika kekurangan suplai maka tambahan tujuan semu yang akan menyuplai kekurangan tersebut yang kapasitasnya = b j ai
123 Contoh 1.a: Seperti halnya contoh 1 akan tetapi sumber 2 jumlah suplainya 1300 dan bukan 1500. 80
215
x11 100 x21 102 x31 0 x41 2300
x12 108 x22 68 x32 0 X42 1400
1000 1300 1200
200
Contoh 1.b: Seperti halnya contoh 1 akan tetapi tujuan 1 jumlah permintaannya 1900 dan bukan 2300. 80
215
0 x x11 x12 13 100 108 0 x x21 x22 13 102 68 0 x x31 x32 33 1900 1400 400
1000 1500 1200
Sebenarnya tidak ada barang yang dikerjakan dari Sumber Semu ke semua Tujuan atau dari semua Sumber ke Tujuan Semu. Dengan demikian biaya transportasi dari Sumber Semu atau ke Tujuan Semu adalah nol, kecuali: - Jika ada penalti atas pengiriman dari sumber semu atau pengiriman ke tujuan semu. - Biaya tersebut dapat berupa biaya persediaan pada sumber yang mengirim ke tujuan semu atau biaya penalti atas kekurangan suplai. Contoh: Dari persoalan pada contoh 1b di atas, sumber 1 dan 3 memberikan biaya persediaan atas kelebihan barang sebesar $ 5 per unit, sedangkan sumber
124 tidak tidak mau kelebihan suplai (terdapat sisa) maka kita beri biaya yang besar sekali (dalam persoalan ini kita beri biaya sebesar M (bilangan yang besar sekali), maka tabelnya menjadi: 80
215
5 x x11 x12 13 100 108 M x x21 x22 13 102 68 5 x x31 x32 33 1900 1400 400
1000 1500 1200
Model Produksi Persediaan Model transportasi dapat digunakan untuk memecahkan persoalan produksi-persediaan. Contoh: PT. Alfa untuk 4 bulan yang akan datang memperoleh permintaan sebanyak 200, 400, 300, 150. Oleh karena peralatan produksinya juga dipakai untuk memproduksi barang lain, maka jumlah produksi untuk 4 bulan yang akan datang adalah 100, 350, 400, 200. Permintaan pada suatu bulan dapat dipenuhi oleh: Produksi pada bulan tersebut Kelebihan produksi dari bulan sebelumnya yang disimpan sebagai persediaan. Produksi dari bulan berikutnya. Di sini merupakan suplai yang terlambat. Pada persoalan ini: Biaya produksi adalah $4/unit Biaya persediaan adalah $0.5/unit/bulan Biaya penalti adalah $2/unit/bulan Persoalan di atas dapat diselesaikan dengan model transportasi.
125 Model Transportasi
Model Produksi Persediaan
i : sumber tujuan j : tujuan j
bulan produksi i bulan permintaan j
cij : biaya transportasi a I : jumlah suplai
biaya produksi + penalti + persediaan / unit jumlah produksi bulan produksi i
bj : jumlah permintaan
jumlah permintaan bulan persediaan j
Bulan produksi
Bulan permintaan
100
200
1
1 x21:c21
350 2
x22:c22
2
400
x23:c23 300
400 3
3
x24:x24
200 4
150 4
dengan : xij = jumlah jumlah suplai bulan produksi i untuk memenuhi permintaan bulan permintaan j cij = biaya produksi + persediaan + penalti Jika i = j i>j i<j
cij = biaya produksi cij = biaya produksi + biaya penalti cij = biaya produksi + biaya persediaan
126 4
4.5
x11
x12
x13
6
4
x21
5
x22
4.5
6
x131
x14
x23
8 x32
5
4
8
100
x24
x33
10
5.5
350 4.5
x34 6
400 4
x41
x42
x43
X44
200
400
300
150
200
Contoh: Sebuah perusahaan mengoperasikan sebuah pengergajian. Kebutuhan mata gergaji yang tajam bervariasi setiap harinya tergantung jenis kayu yang dipotong seperti pada tabel berikut: Hari Kebutuhan gergaji (unit)
Senin 24
Selasa 12
Rabu 14
Kamis 20
Jum’at 18
Sabtu 14
Minggu 22
Perusahaan tersebut dapat memenuhi kebutuhan gergaji yang tajam dengan cara berikut: 1. Membeli gergaji baru dengan harga Rp. 120.000 per unit. 2. Mengasah gergaji yang telah dipakai yang selesai dalam waktu semalam dengan biaya sebesar Rp. 60.000 per unit. 3. Mengasah gergaji yang telah dipakai yang selesai dalam waktu dua hari dengan biaya sebesar Rp. 30.000 per unit. Buatlah model transportasi untuk menentukan berapa banyak gergaji yang harus dibeli, yang diasah selesai dalam waktu semalam dan yang selesai dalam waktu dua hari. Penyelesaian: Persoalan tersebut dapat diselesaikan dengan model transportasi dengan 8 sumber dan 7 tujuan. Sumber dari persoalan ini adalah sumber pertama yaitu gergaji yang dibeli. Pada kondisi ekstrim jumlah yang dibeli adalah keseluruhan gergaji yang dibutuhkan yaitu total sebanyak 124 unit,
127 sedangkan sumber ke 2 sampai sumber ke 8 sebanyak hari produksi (7 hari) di mana besarnya adalah sebanyak mata gergaji yang telah dipakai pada hari-hari tersebut. Sedangkan tujuannya adalah permintaan/kebutuhan pada hari pertama sampai dengan hari ke tujuh. Oleh karena model tidak dalam keadaan seimbang, di mana terdapat kelebihan suplai maka ditambahkan tujuan semu yang akan menampung kelebihan supai tersebut, sehingga sekarang jumlah tujuan menjadi 8. Biaya transportasi dari persoalan ini adalah Rp. 120.000, Rp. 60.000 dan Rp. 30.000, yaitu biaya pembelian mata gergaji yang baru, mata gergaji yang diasah dan selesai dalam 1 malam dan mata gergaji yang selesai diasah dalam waktu dua hari. Biaya transportasi pada baris 1 adalah Rp. 120.000 yaitu biaya pembelian gergaji baru, sedangkan biaya sebesar Rp. 60.000 adalah biaya dari mata gergaji yang dipakai pada hari ke i yang diasah dalam waktu semalam yang dapat dipakai kembali pada hari ke i + 1 dan hari ke i + 2, Biaya sebesar Rp. 30.000 adalah biaya dari mata gergaji yang dipakai pada hari ke i yang selesai diasah setelah 2 hari yang dapat dipakai pada hari ke i + 3 dan hari berikutnya. Dengan demikian model transportasi dari persoalan ini adalah: 1 Senin 12
2 Selasa 12
3 Rabu 12
4 Kamis 12
5 Jum’at 12
6 Sabtu 12
7 Minggu 12
8 Semu 0
124
M
6
6
3
3
3
3
0
24
M
M
6
6
3
3
3
0
23
M
M
M
6
6
3
3
0
14
M
M
M
M
6
6
3
0
20
M
M
M
M
M
6
6
0
18
M
M
M
M
M
M
6
0
14
M
M
M
M
M
M
M
0
22
24
12
14
20
18
14
22
124
