BAB I
PEMROGRAMAN LINIER
TUJUAN PRAKTIKUM
Tujuan Praktikum Pemrograman Linier adalah :
Memahami bagaimana merumuskan/memformulasikan permasalahan yang terdapat dalam dunia nyata.
Memahami dan dapat memformulasikan permasalahan yang telah dirumuskan, dalam format pemrograman linier.
- LANDASAN TEORI
Pemrograman linier disingkat PL merupakan metode matematik dalam mengalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimumkan keuntungan dan meminimumkan biaya. PL banyak diterapkan dalam masalah ekonomi, industri, militer, social dan lain-lain. PL berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu model matematik yang terdiri dari sebuah fungsi tujuan linier dengan beberapa kendala linier.
Pemrograman linier meliputi perencanaan aktivitas untuk mendapatkan hasil optimal, yaitu sebuah hasil yang mencapai tujuan terbaik (menurut model matematika) diantara semua kemungkinan alternative yang ada.
Karateristik-karakteristik pada linear programming adalah: fungsi tujuan (untuk memaksimumkan atau meminimumkan sesuatu),fungsi pembatas yang membatasi tingkatan pencapaian tujuan, adanya beberapa alternative tindakan yang bisa dipilih, fungsi tujuan dan kendala dalam permasalahan diekspresikan dalam bentuk persamaan atau pertidaksamaan linier Metode simplex adalah suatu metode yang secaras istematis dimulai dari suatu pemecahan dasar yang dimungkinkan ke pemecahan dasar yang lainnya dan ini dilakukan tahap demi tahap yang disebut dengan iterasi (dengan jumlah iterasi yang terbatas) sehingga pada akhirnya akan tercapai sesuatu pemecahan dasar yang optimum dan setiap langkah menghasilkan suatu nilai dari fungsi tujuan yang selalu lebih optimal atau sama dari langkah-langkah sebelumnya.
Revised simplex method merupakan metode dari linear programming yang menggunakan bentuk matrix dalam prosesnya. Dengan bantuan matrix,waktu perhitungan bisa dipersingkat dan mempermudah kerumitan perhitungan metodesimplex biasa. Menggunakan metode simplex yang telah direvisi dalam pemrograman akan mampu mengefisienkan memori dan total waktu perhitungan
D.1 Contoh Kasus dan Penyelesaiannya
Sebuah home industry (Perusahaan X) yang bergerak dalam bidang garmen memproduksidua jenis baju yaitu A dan B. Untuk membuat baju A dibutuhkan total waktu 35 menit.orang,sementara untuk baju B membutuhkan waktu 22 menit.orang. Masing-masing jenis baju membutuhkan 1.2 meter untuk jenis A dan 2 meter untuk jenis B. Perusahaan harus menyelesaikan produksi kedua jenis bajunya dalam waktu 3 hari kerja (satu hari kerja adalah 7 jam). Jumlah karyawan perusahaan adalah 10 orang dan bahan baku yang tersisa di gudang hanya 750 meter.Perusahaan hanya dapat menggunakan bahan baku yang tersisa di gudang saja karena bahan baku berikutnya akan datang 4 hari lagi. Keuntungan yang didapat dengan menjual jenis A adalah Rp.4000/stel dan jenis B adalah Rp.3000/stel'.
Pemilik perusahaan tersebut melakukan analisis terhadap permasalahan ini dengan memformulasikannya secara matematis dan mencari solusi terbaik dari permasalahan tersebut.Adapun hasilnya dapat dilihat pada bagian berikut:Total Keuntungan = keuntungan penjualan semua kaos A + keuntungan penjualan semua kaos B
Misalkan: z merupakan notasi matematik dari total keuntungan
x1 merupakan notasi matematik dari kaos A
x2 merupakan notasi matematik dari kaos B
maka total keuntungan dapat diformulasikan secara matematis sebagai berikut:
z =4000x1 +3000x2
Dalam usaha untuk mencari keuntungan yang sebesar-besarnya tersebut, pemilik perusahaan dihadapi permasalahan keterbatasan sumber daya yang dimilikinya yaitu, keterbatasan waktu dalam memproduksi dan keterbatasan bahan baku/jumlah kain yang tersedia di gudang. Untuk itu, pemilik perusahaan harus memutuskan bagaimana pengalokasian sumber daya untuk masing-masing jenis baju sehingga didapatkan keuntungan maksimum. Adapun perhitungannya adalah:
Jumlah waktu yang tersedia adalah 10 orang x 1260 menit = 12600 menit.orang, sehingga total waktu yang digunakan untuk memproduksi kedua jenis baju tersebut harus lebih kecil atau sama dengan 12600 menit.orang. Formulasinya adalah sebagai berikut:
35x1 + 22x2 <= 12600
Jumlah kain yang tersedia adalah 2000 meter, sehingga total jumlah kain yang digunakan untuk memproduksi kedua jenis baju tersebut tidak boleh lebih dari 2000 meter. Formulasinya adalah sebagai berikut:
1.2 x1 + 2x2 <= 750
Selengkapnya formulasi matematis dari permasalahan tersebut adalah:
Fungsi tujuan Z =4000x1 +3000x2
Pembatas
35x1 + 22x2 <= 12600
1.2x1 + 2x2 <= 750
Pemilik perusahaan mencoba mencari solusinya dengan memplot seluruh persamaan matematis tersebut di atas dengan grafis dan hasilnya dapat dilihat pada gambar 1 berikut:
Dari gambar satu dapat dijelaskan, garis putus-putus merupakan representasi fungsi tujuan dalam bentuk grafis dan 2 buah garis tegas yang saling berpotongan dan juga memotong garis putus-putus merupakan representasi pembatas 1,2 dalam bentuk grafis, sementara wilayah arsiran berwarna ungu merupakan seluruh solusi yang layak (feasible) untuk permasalahan ini. Secara visual dapat kita lihat bahwa luas wilayah solusi dari fungsi tujuan menjadi berkurang setelah dibatasi oleh pembatas (C1 dan C2). Lingkaran putus-putus adalah tempat titik perpotongan tiga garis yang merupakan solusi terbaik dari permasalahan tersebut.
Pada gambar 1 dapat dilihat bahwa solusi optimal dari permasalahan ini adalah dengan memproduksi x1 (baju A) sebanyak 199.5413 dan x2 (baju B) sebanyak 255.2752. Solusi ini akan mendatangkan keuntungan maksimum bagi perusahaan sebesar;
Z= 4000(199.5413) + 3000(255.2752)
= 1,563,991
Usaha pencarian solusi terbaik(optimal) yang telah dilakukan oleh pemiliki perusahaan tersebut merupakan salah satu contoh penyelesaian permasalahan dalam pemrograman linier (Linier Programming/LP) dengan menggunakan grafik. Metode grafik ini memperlihatkan bahwa LP yang optimum selalu berkaitan dengan titik ekstrim atau titik sudut dari ruang pemecahan. Berawal dari gagasan ini metode simpleks dikembangkan. Pada intinya, apa yang dilakukan oleh metode simpleks adalah menerjemahkan defenisi geometris dari titik ekstrim menjadi defenisi aljabar. Prosedur bagaimana metode simpleks mengidentifikasi titik ekstrim (atau titik sudut) secara aljabar akan dibahas dalam bagian berikut.
d.2 Pengembangan Metode Simpleks
Pembahasan akan dimulai dengan pembuatan bentuk standar yang diperlukan untuk mewakili ruang pemecahan LP dengan sebuah sistem persamaan simultan. Pembahasan selanjutnya memperlihatkan bagaimana pemecahan dasar yang berturut-turut ditentukan secara selektif dengan maksud untuk mencapai titik pemecahan optimum dalam beberapa iterasi.
D.2.1 Bentuk LP Standar
Untuk mengembangkan sebuah metode pemecahan yang umum, masalah LP harus ditempatkan dalam format yang sama, yang dinamakan sebagai format standar. Beberapa hal yang harus diperhatikan dalam membuat format standar LP adalah sebagai berikut:
A. Batasan
Sebuah batasan variabel yang berjenis D(E) dapat dikonversikan ke dalam sebuah persamaan dengan menambahkan variabel slack ke sisi kiri batasan tersebut, contohnya:
x1 + 3x2 D 10
tambahkan slack s1 E 0 ke sisi kiri untuk memperoleh persamaan:
x1 + 3x2 + s1 = 10, s1 E 0
Kemudian untuk contoh berikut:
x1 + 3x2 - 2x3 E20
karena sisi kiri sekarang lebih besar dari sisi kanan maka kurangkan persamaan dengan nilai variabel surplus s2 E 0 dari sisi kiri sehingga diperoleh persamaan:
x1 + 3x2 - 2x3 - s2 = 20, s2 E 0
B. Variabel
Variabel yang tidak dibatasi yi dapat diekspresikan dalam bentuk dua variabel non- negative dengan menggunakan substitusi.
yi = yi' – yi" yi', yi" E0
Substitusi harus diberlakukan di semua batasan dan dalam fungsi tujuan.
Masalah LP biasanya dipecahkan dalam bentuk yi' dan yi", yang darinya yi ditentukan dengan substitusi balik. Sifat yang menarik dari yi' dan yi" adalah bahwa dalam pemecahan LP (simpleks) yang optimal hanya satu dari dua variabel tersebut yang memiliki nilai positif, tetapi tidak pernah keduanya. Jadi, ketika yi'>0, maka yi" = 0, dan sebaliknya.
C. Fungsi Tujuan
Walaupun model LP standar dapat berjenis maksimasi atau minimasi , konversi dari satumbentuk kebentuk lainnya kadang-kadang berguna. Maksimasi sebuah fungsi adalah setara dengan minimasi negatif dari fungsi yang sama, demikian pula sebaliknya. Misalnya, maksimumkan z = 5x1 + 2x2 + 3x3 Secara matematis setara dengan minimumkan (-z) = - 5x1 - 2x2 - 3x3
D.2.2 Langkah-langkah Metode Simpleks (contoh kasus perusahaan X)
Persoalan perusahaan X bisa diselesaikan dengan metode simpleks, adapun langkahlangkahnya adalah sebagai berikut: Langkah 0 : Buatlah pemecahan dasar awal yang layak (feasible)
Tabel 1. Iterasi 0 : Pemecahan masalah dasar yang layak
Dasar | Z | X1 | X2 | S1 | S2 | Rhas |
z | 1 | -4000 | -3000 | 0 | 0 | 0 |
S1 | 0 | 35 | 22 | 1 | 0 | 12600 |
S2 | 0 | 12 | 2 | 0 | 1 | 750 |
Langkah 1: Pilih entering variable dan leaving variable
Pada Tabel 1 dapat dilihat bahwa x1 memiliki koefisien negatif paling besar dalam persamaan z dan karena itu dipilih sebagai entering variable. Kondisi kelayakan memperlihatkan bahwa s1 bersesuaian dengan titik potong terkecil sehingga menjadi leaving variable.
Langkah 2 : Tentukan nilai variabel dasar yang baru dengan metode eliminasi Gauss-Jordan Metode ini dimulai dengan mengidentifikasi kolom bawah entering variable x1 sebagai entering columm (bagian kolom yang diarsir) dan yang berkaitan dengan baris leaving variable (bagian baris yang diarsir) disebut persamaan pivot (pivot equation) sementara elemen titik potong antara entering columm dan persamaan pivot disebut sebagai elemen pivot (nilai 35).
Metode Gauss-Jordan melakukan perubahan atas dasar penggunaan dua jenis perhitungan:
1. Persamaan Pivot
persamaan pivot baru = persamaan pivot lama / elemen pivot
Tabel 2. Persamaan pivot baru
z | ||||||
X1 | 0 | 1 | 0.628571 | 0.028571 | 0 | 360 |
S2 |
persamaan baru = (persamaan lama)-(koefisien kolom masuk) x (persamaan pivot baru)
Tabel 3. Iterasi 1: Persamaan baru
| -485.714 | 114.2857 | 0 | 1440000 | |||
| 0.628571 | 0.028571 | 0 | 360 | |||
| 1.245714 | 1 | 318 |
Langkah 3 : Lakukan pengecekan terhadap koefisien persamaan z apabila masih positif maka kembali kelangkah 2 (tentukan entering variable dan leaving variable). Dengan cara yang sama dengan langkah 2 sebelumnya maka dapat ditentukan bahwa entering variable-nya adalah x2 (karena memiliki nilai koefisien pada persamaan z yang paling negatif) dan leaving variable-nya adalah s2. Sehingga hasil perhitungannya dapat dilihat pada Tabel 4 berikut:
1.00 | 0.00 | 0.00 | 100.92 | 389.91 | 1563990.83 | |
0.00 | 1.00 | 0.00 | 0.50 | -0.50 | 199.54 | |
0.00 | 0.00 | 1.00 | -0.03 | 0.80 | 255.28 |
Tabel 4 (iterasi 2) ini menrupakan hasil optimal karena tidak satupun variabel non-dasar (non basic) memiliki koefisien negatif. Pemecahan ini menghasilkan x1(baju jenis A) = 199.54 dan x2 (baju jenis B) = 255.28 dengan keuntungan yang diperoleh sebesar Rp. 1,563,990.83.
- PERMASALAHAN
- Soal/kode praktikum : p1/3
Suatu perusahaan akan memperoduksi 2 macam barang yang jumlah nya tidak boleh lebih dari 18 unit.keuntungan yang dari kedua produk tersebut masing-masing adalah Rp.750- dan Rp.425,-per unit serta tenaga kerja yang tersedia adalah 45 jam. Dari survey terlihat bahwa untuk memperoduksi produk I di butuhkan bahan baku 5 unit dengan waktu 5 jam. Sedangkan produk II membutuhkan bahan baku 3 unit dengan waktu 3 jam. Mengingat bahwa bahan baku yang ada maka kedua produk tersebut dapat di buat tidak lebih dari 10 unit. Tentukan banyaknya produk yang harus di buat untuk mendapatkan keuntungan yang maksimum
No | Sumber Daya | Ukuran Produksi | Kapasitas | |
Produk I | Produk II | |||
| 1 | Bahan baku | 5 unit | 3 unit | 10 unit |
| 2 | Waktu pengerjaan | 5 jam | 3 jam | 45 jam |
| 3 | Profit | Rp.750,- | Rp.425,- | |
Variable keputusanX1 = ∑ produk 1 yang di buat
X2 = ∑ produk 2 yang di buat
Fungsi tujuanZmak = 750 x1 + 425 x2
- Fungsi pembatas
- Bahan baku = 5x1 + 3x2 ≤10
Waktu pengerjaan = 5x1 + 3x2 ≤ 45X1,X2 ≥ 0
- Penyelesaian Dengan Menggunakan Manual
Variable keputusanX1 = ∑ produk 1 yang di buat
X2 = ∑ produk 2 yang di buat
Fungsi tujuanZmak = 750 x1 + 425 x2
- Fungsi pembatas
- Bahan baku = 5x1 + 3x2 ≤ 10………..(1)
- Waktu pengerjaan = 5x1 + 3x2 ≤ 45….(2)
Dari persamaan di atas
5x1 + 3x2 = 10Jika x1 = 0 → x2 = (0, 3.33)
x2 = 0 → x1= (2, 0)
5x1 + 3x2 = 45Jika x1 = 0 → x2 = (0, 15)
x2 = 0 → x1 = (9, 0)
Gambar grafik
Dari gambar grafik di atas maka dapat di ketahui bahwa daerah yang layak (feasible) untuk permasalah ini adalah daerah yang di arsir.
Pemilihan alternative
Z = 750 x1 + 425 x2
Koordinat titik A ( 2,0 )
750 ( 2 ) + 425 ( 0 ) = 1500
Koordinat titik B ( 0, 3.33 )
750 ( 0 ) + 425 ( 3,33 ) = 1415,25
Untuk mendapatkan keuntungan yang maksimum yaitu sebesar Rp. 1500 -,
Maka perusahaan tersebut harus membuat produk I ( x1 ) sejumlah 2 buah. dan produk II ( x2 ) sejumlah 0.
- Penyelesaian Dengan Menggunakan Software WinQSB
Buka program LP klik start kemudian pilih: programKwinQSBKLinear an Integer Programming (Lihat gambar 1)
Membuat Program
Setelah jendela LP muncul, mulailah membuat program baru dengan memilih FileKNewproblem sehingga akan muncul kotak dialog LP-ILP Problem Specification. Kemudian isikan kotak dialog tersebut sesuai dengan contoh pada gambar 2.
Pada gambar 2 terlihat bahwa jumlah variabel dan pembatas masing-masing 2 buah, criteria fungsi tujuan adalah maksimasi kemudian tipe data variabelnya adalah integer. Tipe data ini diplih karena dalam kondisi nyata jumlah produk tidaklah mungkin bertipe kontinyu (bilangan berkoma) melainkan berbentuk integer (bilangan bulat). Setelah pengisian kotak dialog selesai klik OK.
Pengisian formulasi masalah (Peng-input-an data)
Langkah berikutnya adalah penulisan formulasi masalah pada format ILP padaWinQSB. Untuk pengisiannya dapat dilihat pada gambar 3.
Gambar 3. Pengisian formulasi masalah dalam format ILP dengan WinQSB
C1 merupakan pembatas pertama dan C2 adalah pembatas kedua.
Menghitung solusi
Setelah pengisian selesai, maka dengan meng-klik menu solve and analize Ksolve problem maka didapatkan hasil penghitungan dengan WinQSB. Adapun untuk membuka hasil dapat dilakukan dengan meng-klik OK pada kotak dialog berikut:
Gambar 4. Kotak dialog yang berisi pernyataan bahwa program sudah dijalankan
Sehingga akan program langsung memunculkan hasil perhitungan seperti pada gambar berikut:
Pada gambar 5. dapat dilihat bahwa keuntungan maksimal adalah Rp. 1.500.0000 dengan memproduksi x1 ( produk 1) sebanyak 2.0000 dan x2 (Produk II) sebanyak 0.
- KESIMPULAN
Permasalahan untuk pengambilan keputusan dapat terjadi diberbagai bidang, baik ekonomi,militer, industri, pertanian, transportasi social, pemerintahan bahkan bidang. Teknik. Metode Grafis Linear Programming adalah salah satu metode yang dapat memecahkan masalah optimasi untuk pengambilan keputusan dengan memperhatikan kendala-kendala yang terjadi di lapangan.Hasil yang dicapai pada pengambilan keputusan ini dapat berupa hasil yang maksimal maupun yang minimal, sesuai dengan tujuan.
Dengan menggunakan program WinQSB dan menggunakan hitungan manual tentang program linier untuk maksimalkan. Untuk mendapatkan keuntungan yang maksimum yaitu sebesar Rp. 1500 -,Maka perusahaan tersebut harus membuat produk I ( x1 ) sejumlah 2 buah. dan produk II ( x2 ) sejumlah 0.
Tidak ada komentar:
Posting Komentar