tugas pemodelan_sepatu dan tas
Post on 04-Dec-2015
14 Views
Preview:
DESCRIPTION
TRANSCRIPT
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.
top related