MODUL 4
OPTIMASI DENGAN ALGORITMA SIMPLEKS
(LINIER PROGRAMMING)
LINEAR PROGRAMMING
Banyak keputusan utama yang dihadapi oleh seorang
manajer perusahaan untuk mencapai tujuan
perusahaan dibatasi oleh situasi lingkungan operasi.
Batasan dapat berupa:
Sumber daya
Batasan Pedoman
Secara umum tujuan perusahaan :
Memaksimalkan laba
Meminimalkan biaya
Program Linear menggambarkan bahwa fungsi linier
dalam model matematika adalah linier dan teknik
pemecahan masalah terdiri dari langkah-langkah
matematika yang telah ditetapkan disebut program
Algoritma simpleks merupakan salah satu algoritma
untuk memecahkan program linier.
SAMPLE STUDI KASUS,
PERNYATAAN MASALAH:
Perusahaan barang tembikar Colonial memproduksi 2
produk setiap hari, yaitu :
mangkok
cangkir
Perusahaan mempunyai 2 sumber daya yang terbatas
jumlahnya untuk memproduksi produk-produk tersebut
yaitu:
Tanah liat (120 kg/hari)
Tenaga kerja (40 jam/hari)
Dengan keterbatasan sumber daya, perusahaan ingin
mengetahui berapa banyak mangkok dan cangkir yang akan
diproduksi tiap hari dalam rangka memaksimumkan laba
Kedua produk mempunyai kebutuhan sumber daya untuk
produksi serta laba per item seperti ditunjukkan pada tabel
Kebutuhan sumber daya dlm
bentuk tabel:
PEMBUATAN MODEL
1. Menentukan Variabel Keputusan
2. Menentukan Fungsi Tujuan
3. Menentukan Fungsi Batasan
4. Memecahkan Model
5. Implementasi Model
1. VARIABEL KEPUTUSAN
Masalah ini berisi 2 variabel keputusan
yaitu:
X1 = jumlah mangkok yang
diproduksi/hari
X2 = jumlah cangkir yang
diproduksi/hari
2. FUNGSI TUJUAN
Memaksimumkan total laba.
Z = 4000 X1 + 5000 X2
Z = total laba tiap hari
4000 X1 = laba dari mangkok
5000 X2 = laba dari
cangkirDengan
3. BATASAN MODEL
Batasan Tenaga Kerja
1 X1 + 2 X2 <= 40
Batasan Tanah Liat
3 X1 + 2 X2 <= 120
Batasan Non Negatif
X1, X2 > 0
4. PEMECAHAN MODEL
Metode yang dipakai dalam pemecahan
masalah ini adalah metode simplex
5. IMPLEMENTASI
Mengubah Fungsi Tujuan dan batasan
Menyusun persamaan-persamaan di
dalam tabel
Memilih kolom kunci
Perhitungan Indeks
Memilih Baris Kunci
Mengubah Niilai-Nilai
Melanjutkan Perubahan
MENGUBAH FUNGSI TUJUAN DAN
BATASAN-BATASAN
Fungsi Tujuan
Z = 4000 X1 + 5000 X2
Menjadi
Z - 4000X1 -5000X2 = 0
Batasan Batasan
1 X1 + 2 X2 <=40
3 X1 + 2 X2 <= 120
Menjadi
1 X1 + 2 X2 + X3 = 40
3 X1 + 2 X2 + x4 = 120
MENYUSUN PERSAMAAN-
PERSAMAAN DALAM TABEL
MEMILIH KOLOM KUNCI
Kolom kunci : kolom yang merupakan dasar
untuk mengubah tabel diatas
Kolom yang dipilih adalah kolom yang
mempunyai nilai pada baris fungsi tujuan yang
bernilai negatif dengan angka terbesar
Jika tidak ada nilai negatif pada baris fungsi
tujuan maka, solusi optimal sudah diperoleh
PERHITUNGAN INDEKS
Indeks diperoleh dari Nilai kolom Nilai
Kanan dibagi dengan Nilai Kolom Kunci
MEMILIH BARIS KUNCI
Baris kunci dipilih baris yang mempunyai
indeks positif dengan angka terkecil
Nilai kunci merupakan perpotongan
antara kolom kunci dengan baris kunci
MENGUBAH NILAI-NILAI
Baris kunci
Nilai Baru = Nilai Lama / Nilai Kunci
kolom X1 = ½
kolom X2 = 2/2 = 1
kolom X3 = ½
kolom X4 = 0/2 = 0
Kolom Nilai Kanan = 40/2 = 20
Bukan baris kunci
Nilai Baru = Nilai Lama- (Koefisien pada kolom
kunci) x nilai baru baris kunci
Tabel dengan nilai baru:
MELANJUTKAN PERUBAHAN
Ulangi langkah 3 sampai 6 pada tabel baru, perubahan
berhenti ketika pada fungsi tujuan (baris pertama) tidak ada
yang bernilai negatif.
solusi maksimalnya adalah X1 = 40, X4 = 0
dan Z = 160000
Jika ini disubstitusikan ke persamaan
Z = 4000 X1 + 5000 X2
160000 = 4000*40 + 5000*X2
X2 = 0
Tabel lengkap:
Kesimpulan :
solusi maksimalnya adalah X1 = 40, X2 = 0 dan Z = 160000
Ini berarti jumlah produksi mangkok per hari adalah 40, jumlah produksi
cangkir per hari adalah 0 dengan keuntungan yang akan diperoleh
perusahaan sebesar Rp. 160.000,-
Dari hasil ini, kita juga bisa mengetahui bahwa jam kerja yang terpakai
adalah sebesar:
1 X1 + 2 X2 = 40 + 2 * 0
= 40
Karena sumber daya jam kerja yang dimiliki adalah 40 jam, berarti semua
sumber daya jam kerja dipakai untuk memproduksi.
Sedangkan tanah liat yang dibutuhkan untuk produksi sehari sebesar:
3 X1 + 2 X2 = 3*40 + 2*0
= 120
Karena sumber daya tanah liat yang tersedia di perusahaan sebesar 120
kg/hari, berarti semua sumber daya tanah liat dipakai untuk memproduksi.
Rancangan Interface:
HASIL APLIKASI
Listing Program :
List-1
List-2
List-3
List-4
List-5
List-6
List-7
LATIHAN
Jaringan Toko serba ada The Biggs menyewa
perusahaan periklanan untuk jenis dan jumlah iklan
yang harus diperoleh untuk toko.
Tiga jenis iklan yang tersedia adalah iklan komersial
radio, televisi dan iklan surat kabar.
Jaringan toko ingin mengetahui jumlah setiap jenis iklan
yang harus dibeli dalam rangka memaksimumkan
tujuannya.
Berikut ini perkiraan setiap iklan komersial yang akan
mencapai pemirsa potensial dari biaya tertentu.
Lanjutan latihan,,,
Batasan Sumber daya
Batas Anggaran untuk iklan adalah [Link]
Stasiun televisi memiliki 4 waktu komersial
Stasiun radio memiliki 10 waktu komersial
Surat kabar mempunyai jatah yang tersedia untuk 7
iklan
Perusahaan iklan hanya mempunyai waktu dan
karyawan untuk memproduksi tidak melebihi 15
iklan
Pertanyaan
variabel-variabel keputusan
fungsi tujuan
batasan-batasan model
penyelesaian model dengan metode simplex