Download - Tugas Pemodelan_sepatu Dan Tas
ANALISIS KASUS PENGHEMATAN BIAYA TRANSPORTASI
DALAM PENDISTRIBUSIAN SEPATU DAN TAS
disusun oleh :
Tuti Rubianti 140110120002
Mega Novia Andriani 140110120048
Beverly Clarissa Wicaksono 140110120052
Ghiffaniaz Zahra Fadillah 140110120084
Program Studi Matematika
Fakultas Matematika dan Ilmu Pengetahuan Alam
Universitas Padjadjaran
2015
I. Studi Kasus
Sebuah home industry akan memproduksi produk sepatu dan tas yang mendapat
pesanan dari berbagai wilayah kota di Indonesia. Sebagian dari pendistribusian sepatu dan tas
ini dikerjakan sendiri oleh perusahaan tersebut, sebagian lainnya menggunakan jasa perusahaan
lain. Kendaraan yang ada sekarang sudah tua dan akan diganti. Perusahaan ini mempunyai
pilihan 2 tipe kendaraan, dimana kendaraan tipe A hanya dapat mengirimkan sepatu dengan
jumlah maksimum 100 pasang sepatu. Sementara kendaraan B dapat mengirimkan sepatu dan
dalam jumlah maksimum 50 pasang sepatu dan 20 tas.
Untuk membeli kendaraan tipe A akan mengakibatkan perusahaan dapat menghemat
sebanyak 1000 (x 1 dollar) per bulan dibandingkan bila memakai jasa perusahaan lain. Untuk
kendaraan tipe B, perusahaan dapat menghemat sebanyak 700 (x 1 dollar) per bulannya.
Jelaslah bahwa perusahaan ini ingin memaksimumkan besarnya penghematan ini, bila jumlah
sepatu yang harus dikirimkan sebanyak 2425 pasang sepatu dan tas yang harus dikirimkan
sebanyak 510 tas.
II. Tahapan dalam Pemodelan Matematika
Formulasi
1. Menyatakan pertanyaan
Berapa jumlah kendaraan tipe A dan tipe B yang harus dibeli agar perusahaan dapat
memaksimumkan penghematan biaya?
2. Identifikasi faktor yang relevan
Faktor-faktor yang mempengaruhi dalam kasus ini:
- Jenis Kendaraan
- Harga Kendaraan
- Jumlah sepatu dan tas yang akan dikirim
ASUMSI I : Banyaknya jenis kendaraan yang akan dibeli adalah nonnegatif
3. Deskripsi matematika
Kasus ini merupakan masalah pemrograman linier. Metode yang digunakan untuk
menyelesaikan kasus ini adalah metode simpleks.
Bentuk umum masalah pemrograman linier [2]
a. Dalam bentuk skalar
min โ ๐๐๐ฅ๐
๐
๐=1
๐ . ๐ก โ ๐๐๐๐ฅ๐ โฅ ๐๐ , ๐ = 1,2, โฆ , ๐
๐
๐=1
(1)
๐ฅ๐ โฅ 0 , ๐ = 1, โฆ , ๐
dimana
Fungsi objektif yang akan diminimumkan ๐ง = min โ ๐๐๐ฅ๐๐๐=1 .
Koefisien ๐๐, โ๐ = 1, โฆ , ๐ dikenal sebagai koefisien biaya.
Variabel keputusan yang akan ditentukan adalah ๐ฅ๐ untuk ๐ = 1, โฆ , ๐
Pertidaksamaan โ ๐๐๐๐ฅ๐ โฅ ๐๐ , ๐ = 1,2, โฆ , ๐๐๐=1 merupakan fungsi kendala ke-๐.
Koefisien ๐๐๐, ๐ = 1, โฆ , ๐ , ๐ = 1, โฆ , ๐ disebut koefisien teknologi.
Kendala ๐ฅ๐ โฅ 0, ๐ = 1, โฆ , ๐ disebut kendala nonnegatif.
b. Dalam bentuk matriks
min ๐๐๐ฅ
๐ . ๐ก ๐ด๐ฅ โฅ ๐
๐ฅ โฅ 0 (2)
dimana
๐ฅ = [
๐ฅ1
๐ฅ2
โฎ๐ฅ๐
] , ๐ = [
๐1
๐2
โฎ๐๐
] , ๐ = [
๐1
๐2
โฎ๐๐
] , ๐ด = [
๐11 โฆ ๐1๐
โฎ โฑ โฎ๐๐1 โฆ ๐๐๐
]
dan tanda superscript ๐ digunakan untuk mengindikasikan transpose dari vector kolom ๐.
Bentuk standar PL memenuhi :
a. Fungsi objektif merupakan fungsi minimasi.
b. Semua fungsi kendala merupakan fungsi kesamaan dengan tanda (=).
c. Semua variabel keputusan bernilai nonnegatif.
Bentuk standar PL :
min ๐๐๐ฅ
๐ . ๐ก ๐ด๐ฅ = ๐
๐ฅ โฅ 0 (3)
Bentuk kanonik PL :
min ๐๐๐ฅ
๐ . ๐ก ๐ด๐ฅ โฅ ๐
๐ฅ โฅ 0 (4)
Konsep metode simpleks [2]
a. Metode simpleks memberikan algoritma untuk memeriksa solusi fisible basis, dimana
jika suatu solusi tidak optimal, maka metode ini akan mencari kemungkinan solusi
selanjutnya pada solusi fisible basis terdekat yang bernilai lebih rendah atau sama
dengan ๐.
b. Proses ini diulang sampai sejumlah terbatas tahap dimana solusi optimal ditemukan.
Ketentuan metode simpleks [3]
1. Nilai kanan fungsi tujuan harus nol.
2. Nilai kanan fungsi kendala harus positif. Apabila negatif, nilai tersebut harus dikali
dengan -1.
3. Fungsi kendala dengan tanda " โค " harus diubah ke bentuk โ=โ dengan menambahkan
variable slack.
4. Fungsi kendala dengan tanda " โฅ " diubah ke bentuk " โค " dengan cara mengalikan
dengan -1, lalu diubah ke bentuk โ=โ dengan ditambah variabel slack. Kemudian karena
nilai kanannya negatif, dikalikan lagi dengan -1 dan ditambah variabel artifisial (๐).
5. Fungsi kendala dengan tanda โ=โ harus ditambahkan variabel artifisial.
Mencari solusi optimal pada metode simpleks [2]
Langkah 1 : tentukan kolom s sehingga ๏ฟฝฬ๏ฟฝ๐ = min ๐๐
Langkah 2 : periksa apakah ๏ฟฝฬ๏ฟฝ๐ < 0?
1. Jika tidak, maka solusi optimal, prosedur dihentikan.
2. Jika ya, lanjutkan ke langkah 3.
Langkah 3 : periksa apakah ๏ฟฝฬ๏ฟฝ๐๐ โค 0, โ๐ ?
1. Jika ya, maka solusi tidak terbatas, prosedur dihentikan.
2. Jika tidak, lanjutkan ke langkah 4.
Langkah 4 : tentukan rasio ๏ฟฝฬ๏ฟฝ๐
๏ฟฝฬ๏ฟฝ๐๐ untuk ๏ฟฝฬ๏ฟฝ๐๐ โฅ 0.
Langkah 5 : tentukan baris ๐ sehingga berlaku
๏ฟฝฬ๏ฟฝ๐
๏ฟฝฬ๏ฟฝ๐๐ = min
๏ฟฝฬ๏ฟฝ๐๐ >0
๏ฟฝฬ๏ฟฝ๐
๏ฟฝฬ๏ฟฝ๐๐
Langkah 6 : diperoleh bentuk kanonik baru yang memuat fungsi objektif dengan
operasi pivot pada ๏ฟฝฬ๏ฟฝ๐๐ . Kembali ke langkah 1.
Gambar 1. Tabel Simpleks
Manipulasi Matematika
Variabel Keputusan :
๐ฅ1= jumlah kendaraan Tipe A
๐ฅ2= jumlah kendaraan Tipe B
๐๐๐ฅ 1000๐ฅ1 + 700๐ฅ2
๐ ๐ก 100๐ฅ1 + 50๐ฅ2 โค 2425
20๐ฅ2 โค 510
๐ฅ1, ๐ฅ2 โฅ 0 ๐๐๐ ๐๐๐ก๐๐๐๐ (5)
Penyelesaian metode simpleks menggunakan software Maple 15.
>
> > >
>
>
>
x1 = 23/2
x2 = 51/2
f = 29350
Didapat ๐ฅ1 =23
2 , ๐ฅ2 =
51
2, ๐๐๐ ๐ = 29350.
Evaluasi
Solusi model (5) tidak sesuai dengan kenyataan permasalahan yang ada karena solusi yang
diperoleh dalam bentuk fraksional dan secara logika bilangan fraksional tidak sesuai untuk
menyatakan jumlah kendaraan A dan B yang harus dibeli. Sehingga dilakukan reformulasi.
Reformulasi
Menggunakan Metode Branch and Bound for Mixed Integer.
Algoritma MIP (Mixed Integer Programming) [1]
Initialization.Set ๐โ = โ. Kemudian akan digunakan tahapan pembatasan, fathoming atau
pemotongan jalur, dan uji optimalitas. Jika tidak dilakukan fathoming, klasifikasikan masalah
ini sebagai satu dari subproblem selanjutnya untuk satu iterasi pertama secara utuh.
Langkah setiap iterasi:
a. Branching. Diantara supbroblem tersisa yang belum difathom, pilih salah satu yang
merupakan supbrolem terbaru, pilih berdasarkan nilai batas yang lebih besar. Diantara
variable yang dibatasi sebagai variable integer namun belum memiliki solusi integer
pada setiap subprobelem, pilih variable pertama dalam urutan alamiah sebagai variable
yang akan dibranching. Dimisalkan ๐ฅ๐ merupakan variable tersebut dengan ๐ฅ๐โ adalah
nilai pada solusi ini, kemudaian cabangkan titik dari subproblem ini dengan membuat
2 subproblem baru dengan menambahkan fungsi kendala secara berurutan, yaitu.
๐ฅ๐ โค โ๐ฅ๐โโ
๐๐๐
๐ฅ๐ โฅ โ๐ฅ๐โโ + 1
b. Bounding.Untuk setiap subproblem, perolehlan nilai batasnya dengan menggunakan
Metode Simpleks atau Dual Simpleks pada masalah Linear Programming dan gunakan
nilai Z sebagai hasil dari solusi optimal.
c. Fathoming.Untuk setiap subproblem yang baru, gunakan uji fathoming berikut.
i. F(1) : Jika nilai batasnya โค ๐โ, dengan ๐โadalah nilai Z pada incumbent
sekarang.
ii. F(2) : Jika Linear Programming memiliki solusi infisible
iii. F(3) : Jika solusi optimalnya memiliki solusi integer untuk variable yang
dibatasi integer sehinga apabila solusi yang diperoleh ini lebih baik dari solusi
incumbent, maka solusi ini menjadi incumbent baru dan F(1) diujikan kembali
pada seluruh subproblem yang belum difathom dengan nilai ๐โ yang lebih
besar.
d. Tes Optimal. Perhitungan dihentikan ketika tidak ada lagi subproblem yang tersisa dan
incumbent yang diperoleh sudah optimal.
ASUMSI II : Banyaknya jenis kendaraan yang akan dibeli adalah integer.
Manipulasi Matematika
Penyelesaian model (5) menggunakan metode Branch and Bound for mixed integer dengan
software Maple 15.
> >
> >
SUB PROBLEM 1
๐๐๐ฅ 1000๐ฅ1 + 700๐ฅ2
๐ ๐ก 100๐ฅ1 + 50๐ฅ2 โค 2425
20๐ฅ2 โค 510
๐ฅ1 โค 11 (6)
>
SUB PROBLEM 2
๐๐๐ฅ 1000๐ฅ1 + 700๐ฅ2
๐ ๐ก 100๐ฅ1 + 50๐ฅ2 โค 2425
20๐ฅ2 โค 510
๐ฅ1 โฅ 12 (7)
>
SUB PROBLEM 2.1
๐๐๐ฅ 1000๐ฅ1 + 700๐ฅ2
๐ ๐ก 100๐ฅ1 + 50๐ฅ2 โค 2425
20๐ฅ2 โค 510
๐ฅ1 โฅ 12
๐ฅ2 โค 24 (8)
>
SUB PROBLEM 2.2
๐๐๐ฅ 1000๐ฅ1 + 700๐ฅ2
๐ ๐ก 100๐ฅ1 + 50๐ฅ2 โค 2425
20๐ฅ2 โค 510
๐ฅ1 โฅ 12
๐ฅ2 โฅ 25 (9)
>
Error, (in Optimization:-LPSolve) no feasible solution found
SUB PROBLEM 2.1.1
๐๐๐ฅ 1000๐ฅ1 + 700๐ฅ2
๐ ๐ก 100๐ฅ1 + 50๐ฅ2 โค 2425
20๐ฅ2 โค 510
๐ฅ1 โฅ 12
๐ฅ2 โค 24
๐ฅ1 โค 12 (10)
>
SUB PROBLEM 2.1.2
๐๐๐ฅ 1000๐ฅ1 + 700๐ฅ2
๐ ๐ก 100๐ฅ1 + 50๐ฅ2 โค 2425
20๐ฅ2 โค 510
๐ฅ1 โฅ 12
๐ฅ2 โค 24
๐ฅ1 โฅ 13 (11)
>
SUB PROBLEM 1.1
๐๐๐ฅ 1000๐ฅ1 + 700๐ฅ2
๐ ๐ก 100๐ฅ1 + 50๐ฅ2 โค 2425
20๐ฅ2 โค 510
๐ฅ1 โค 11
๐ฅ2 โค 25 (12)
>
SUB PROBLEM 1.2
๐๐๐ฅ 1000๐ฅ1 + 700๐ฅ2
๐ ๐ก 100๐ฅ1 + 50๐ฅ2 โค 2425
20๐ฅ2 โค 510
๐ฅ1 โค 11
๐ฅ2 โค 26 (13)
>
Error, (in Optimization:-LPSolve) no feasible solution found
Jadi, dengan kendaraan tipe A sebanyak 12 buah dan kendaraan tipe B sebanyak 24 buah
perusahaan dapat menghemat sebanyak 28800 (x 1 dollar).
Evaluasi
Dengan menggunakan metode Branch and Bound for mix integer, model (5) menghasilkan solusi yang
integer, sehingga untuk menyelesaikan kasus ini lebih baik menggunakan metode Branch and Bound
for mix integer.
DAFTAR PUSTAKA
[1] Chaerani, Diah. 2015. Modul Praktikum Mata Kuliah Optimisasi. Diktat kuliah. Program
Studi S1 Matematika FMIPA Universitas Padjadjaran.
[2] Chaerani, Diah. 2011. Pemrograman Linier, Bahan Ajar. Diberikan di Jurusan
Matematika FMIPA Universitas Padjadjaran.
[3] Wirdasari, Dian. Metode Simpleks dalam Program Linier. Jurnal Saintikom. Vol. 6, No.1,
Januari 2009, halaman 276-285.