BAB II TINJAUAN PUSTAKA 2.1. Program Linier Program linier adalah suatu teknik optimalisasi dimana variabel- variabelnya linier. Metode ini dipakai pada saat penulis dihadapkan pada beberapa pilihan dengan batasan-batasan tertentu, sedangkan dilain pihak penulis menghendaki keputusan yang optimum (maksimum/minimum).Pemrograman linier berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu model matematika 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 alternatif yang ada. Sekilas tentang sejarah program linier, Seorang Matematikawan Rusia L.V. Kantorovich pada 1939 berhasil menemukan pemecaham masalah yang berkaitan dengan program linear. Pada waktu itu Kantorovich bekerja untuk Kantor Pemerintah Uni Soviet. Ia diberi tugas untuk mengoptimalkan produksi pada industri plywood. Ia kemudian muncul dengan teknik matematis yang diakui sebagai pemrograman linear. Matematikawan Amerika George B. Dantzig secara independen juga mengembangkan pemecahan masalah tersebut, dimana hasil karyanya pada masalah tersebut pertama kali dipublikasikan pada tahun 1947. selanjutnya, sebuah teknik yang lebih cepat, tetapi lebih rumit, yang cocok untuk memecahkan masalah program linear dengan ratusan atau bahkan ribuan variabel, dikembangkan oleh matematikawan Bell Laboratories, Naranda Karmarkar pada tahun 1983, Program linear sangat penting khususnya dalam perencanaan militer dan industri. (wikipedia.org) Program linier (linear programming) merupakan model optimasi persamaan linier yang berkenaan dengan masalah-masalah pertidaksamaan linier, Masalah program linier berarti masalah nilai optimum (maksium atau minimum) sebuah fungsi linier pada suatu sistem pertidaksamaan linier yang harus 6
This document is posted to help you gain knowledge. Please leave a comment to let me know what you think about it! Share it to your friends and learn new things together.
Transcript
6
BAB II
TINJAUAN PUSTAKA
2.1. Program Linier
Program linier adalah suatu teknik optimalisasi dimana variabel-
variabelnya linier. Metode ini dipakai pada saat penulis dihadapkan pada beberapa
pilihan dengan batasan-batasan tertentu, sedangkan dilain pihak penulis
menghendaki keputusan yang optimum (maksimum/minimum).Pemrograman
linier berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu
model matematika 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 alternatif yang ada.
Sekilas tentang sejarah program linier, Seorang Matematikawan Rusia
L.V. Kantorovich pada 1939 berhasil menemukan pemecaham masalah yang
berkaitan dengan program linear. Pada waktu itu Kantorovich bekerja untuk
Kantor Pemerintah Uni Soviet. Ia diberi tugas untuk mengoptimalkan produksi
pada industri plywood. Ia kemudian muncul dengan teknik matematis yang diakui
sebagai pemrograman linear. Matematikawan Amerika George B. Dantzig
secara independen juga mengembangkan pemecahan masalah tersebut, dimana
hasil karyanya pada masalah tersebut pertama kali dipublikasikan pada tahun
1947. selanjutnya, sebuah teknik yang lebih cepat, tetapi lebih rumit, yang cocok
untuk memecahkan masalah program linear dengan ratusan atau bahkan ribuan
variabel, dikembangkan oleh matematikawan Bell Laboratories, Naranda
Karmarkar pada tahun 1983, Program linear sangat penting khususnya dalam
perencanaan militer dan industri.
(wikipedia.org)
Program linier (linear programming) merupakan model optimasi
persamaan linier yang berkenaan dengan masalah-masalah pertidaksamaan linier,
Masalah program linier berarti masalah nilai optimum (maksium atau minimum)
sebuah fungsi linier pada suatu sistem pertidaksamaan linier yang harus
6
7
memenuhi optimasi fungsi objektif. Dalam banyak situasi sering dijumpai
masalah-masalah yang berhubungan dengan program linier. Agar masalah
optimasinya dapat diselesaikan dengan program linier, maka masalah tersebut
harus diterjemahkan dalam bentuk model matematika.( Mulyono, Sri. 2007)
2.2. Bentuk Umum Program Linier
Pada setiap masalah, ditentukan variabel keputusan, fungsi tujuan, dan
sistem kendala, yang bersama-sama membentuk suatu model matematika dari
dunia nyata. Bentuk umum dari program linier adalah :
Maksimumkan ∑=
=n
jjj XCZ
1
Dengan batasan : { }∑=
>=<n
jijij bXa
1
,, untuk i = 1, 2, 3, … , m
Keterangan :
Z: nilai fungsi tujuan.
Cj : sumbangan per unit kegiatan, untuk masalah maksimisasi Cj menunjukkan
keuntungan atau penerimaan per unit, sementara dalam kasus minimisasi
menunjukkan biaya per unit.
Xj: banyaknya kegiatan j, dimana j = 1, 2, 3, … n. berarti disini terdapat n
variabel keputusan.
aij : banyaknya sumberdaya i yang dikonsumsi sumberdaya j.
bi: jumlah sumberdaya i (i = 1, 2, …, m)
(Mulyono, Sri. 2007)
2.3. Metode Simpleks
Persoalan program linier tidak selalu sederhana karena melibatkan
banyak constraint (pembatas) dan banyak variabel sehingga tidak mungkin
diselesaikan dengan metode grafik. Oleh karena itu serangkaian prosedur
8
matematik (aljabar linier) diperlukan untuk mencari solusi dari persoalan yang
rumit tersebut. Prosedur yang paling luas digunakan adalah Metode Simpleks.
Penemuan metode ini merupakan lompatan besar dalam Riset Operasi dan ia
digunakan sebagai prosedur penyelesaian dari setiap program komputer.
Metode simpleks pertama kali diperkenalkan oleh George B. Dantzig
(Mulyono, Sri., 2007) pada tahun 1947 dan telah diperbaiki oleh beberapa ahli
lain. Metode ini menyelesaikan masalah program linier melalui perhitungan-ulang
(iterasi) dimana langkah-langkah perhitungan yang saman diulang berkali-kali
sebelum solusi optimum dicapai.
Metode simpleks adalah suatu prosedur ulang yang bergerak dari satu
jawab layak basis ke jawab berikutnya sedemikian rupa sehingga harga fungsi
tujuan terus menaik (dalam permasalahan maksimisasi). Proses ini akan
berkelanjutan sampai dicapai jawab optimal (kalau ada) yang memberi harga
maksimum (Siagian, P., 2006).
Metode simpleks merupakan suatu cara yang lazim dipakai untuk
menentukan kombinasi optimal dari tiga variabel atau lebih. Masalah-masalah
yang melibatkan banyak variabel-variabel keputusan dapat dengan cepat
dipecahkan dengan bantuan komputer. Bila variabel keputusan yang dikandung
tidak terlalu banyak masalah maka dapat diselesaikan dengan suatu algoritma
yang biasanya sering disebut dengan “metode tabel simpleks”.
2.3.1 Bentuk Aljabar Simpleks
Berikut adalah contoh kasus permasalahan dalam perusahaan tas PT.
Rezeki Jaya.
Sebuah Perusahaan tas PT. Rezeki Jaya mempoduksi dua jenis tas, yaitu tas model
ransel dan tas model samping. Untuk memproduksi 2 unit produksi tas model
ransel dan 2 unit produksi tas model samping dibutuhkan waktu untuk
pemotongan bahan baku selama 800 jam. Untuk memproduksi 2 unit produksi tas
ransel dan 2,3 unit produksi tas samping dibutuhkan waktu 1000 jam untuk
penjahitan. Untuk menyelesaikan satu unit produksi tas ransel dan 0,5 unit
produksi tas samping dibutuhkan waktu 300 jam untuk penyelesaian. Untuk
9
memproduksi 2 unit produksi tas ransel dan 1,5 unit produksi tas samping
dibutuhkan waktu 650 jam untuk pemeriksaan dan pengepakan. Berapakah
keuntungan maksimal yang dapat diperoleh perusahaan tersebut dalam
memprodukksi 3 unit produksi tas ransel dan 2 unit produksi tas samping. Dari
persoalan diatas dimisalkan X1 adalah tas model ransel dan X2 adalah tas
samping. Persamaan linier dari persoalan diatas adalah :
Maks. Z = 3X1 + 2X2
Dengan kendala :
2X1 + 2X2 <= 800
2X1 + 2.3X2 <= 1000
X1 + 0.5X2 <= 300
2X1 + 1.5X2 <= 650
Dengan menyertakan variabel Slack atau surplus maka model tersebut dibuat
menjadi bentuk standar berikut:
Maks. Z = 3X1 + 2X2 + 0S1 + 0S2 + 0S3 + 0S4
Kendala menjadi:
2X1 + 2X2 + S1 = 800 ... (1)
2X1 + 2.3X2 + S2 = 1000 ... (2)
X1 + 0.5X2 + S3 = 300 ... (3)
2X1 + 1.5X2 + S4 = 650 ... (4)
X1,X2,S1,S2,S3,S4 ≥ 0
Keempat fungsi pembatas tersebut merupakan suatu persamaan sistem
dengan enam variabel. Jika suatu sistem persamaan memiliki veriabel yang lebih
banyak dibanding dengan jumlah persamaannya maka solusi dari persamaan sistem
tersebut adalah infinity. Metode simpleks dengan demikian merupakan prosedur
10
aljabar untuk mendapatkan solusi terbaik bagi suatu sistem persamaan. Dalam proses
mencari solusi terbaik (best solution), solusi yang tidak memenuhi persyaratan non
negatif akan dieliminasi.
2.3.2. Mendapat Solusi Dasar Dalam maksimisasi
Oleh karena jumlah variabel dalam persamaan sistem lebih besar dibanding
jumlah persamaaannya –-dalam hal ini ada enam variabel untuk empat persamaan--
maka metode simpleks memberikan nilai nol untuk dua variabel, dan mencari solusi
terbaik bagi empat variabel lainnya dalam sistem persamaan tersebut. Misalkan X2 = 0
dan S1 = 0 sehingga persamaan sistem tersebut menjadi:
2X1 = 800 ... (5)
2X1 + S2 = 1000 ... (6)
X1 + S3 = 300 ... (7)
2X1 + S4 = 650 ... (8)
Dengan menetapkan nilai nol untuk variabel X2 dan S1 maka persamaan sistem
tersebut direduksi menjadi empat persamaan dengan empat variabel (X1,S2,S3,S4).
Dari persamaan (5) diperoleh
2X1 = 800
sehingga X1 = 800/2 = 400.
Dari persamaan (6) masukkan nilai X1 = 400 untuk mendapatkan nilai S2 yaitu
2X1 + S2 = 1000
sehingga S2 = 1000 – (2*400) = 200
Dari persamaan (7) diperoleh
X1 + S3 = 300
sehingga S3 = 300 – 400 = -100
Dari persamaan (8) diperoleh
11
2X1 + S4 = 650
sehingga diperoleh S4 = 650 – (2*400) = -150
Dengan demikian diperoleh solusi dari persamaan sistem dengan enam variabel dan
empat persamaan, yaitu:
X1 = 400
X2 = 0
S1 = 0
S2 = 200
S3 = -100
S4 = -150
Solusi diatas disebut Solusi dasar (Basic Solution). Prosedur umum untuk
mendapatkan basic solution adalah dengan membangun bentuk persamaan standar
untuk n variabel (termasuk variabel keputusan, slack dan surplus) dan m persamaan
pembatas dimana n lebih besar dari m.
Untuk mendapatkan solusi dasar, tetapkan n-m variabel mana saja seb agai variabel
non basis dan beri nilai nol dan temukan solusi dari m persamaan pembatas untuk m
variabel lainnya.
2.3.3. Solusi Fisibel Dasar (Basic Feasible Solution)
Solusi dasar mungkin saja fisibel atau infisibel. Sebuah solusi dasar fisibel
akan memenuhi persyaratan tidak negatif. Solusi dasar yang diperoleh diatas dengan
menetapkan X2 dan S1 sebagai variabel bukan basis dan bernilai sama dengan nol telah
mendapatkan solusi untuk nilai X1,S2,S3,S4 bukan sebagai solusi dasar fisibel karena
nilai S3 = -100 dan S4 = -150. Olehkarena itu pemilihan variabel bukan basis perlu
diubah. Jadi jika variabel yang dipilih sebagai variabel bukan basis adalah X1 dan X2
dan bernilai nol maka solusi basis yang diperoleh adalah fisibel, yaitu:
12
S1 = 800
S2 = 1000
S3 = 300
S4 = 650
dengan variabel bukan basis X1 = 0 dan X2 = 0.
2.3.4. Prosedur Penyelesaian Program Linier Dengan Metode Simpleks
1. Formulasikan persoalan menjadi model linear.
2. Transformasikan model tersebut kedalam bentuk standar dengan
menambahkan variabel slack atau mengurangi dengan variabel surplus.
3. Buatlah tabel simpleks.
2.3.5. Menyusun Tabel Simpleks Awal (Initial Simplex Table)
Setelah melakukan konversi program linier kedalam tabel simpleks maka
tahap pertama adalah membangun tabel simpleks awal (initial simplex table). Pada
tahap ini termasuk pemberian notasi bagi semua konstanta yaitu:
cj = konstanta fungsi tujuan untuk variabel j
bi = konstanta sisi kanan (RHS) untuk constraint ke i
aij = konstanta yang berasosiasi dengan variabel j pada constraint i
Koefisien-koefisien ini merupakan bagian yang menyususn tabel simpleks seperti
berikut :
13
Jadi tabel simpleks awal untuk persoalan diatas adalah :
Tabel 2.1
Baris pertama tabel simpleks awal tersebut menunjukkan koefisien dari masing-
masing variabel pada fungsi tujuan, sedangkan koefisien di bawahnya dan di sebelah
kiri garis vertikal merupakan koefisien dari masing-masing variabel pada setiap
constraint. Elemen di sebelah kanan garis vertikal menunjukkan nilai dari sisi kanan
dari constraint. Demi kemudahan, setiap kategori koefisien diperlakukan sebagai suatu
grup yang terdiri dari:
Baris C = baris dari koefisien fungsi tujuan
Kolom B = kolom dari nilai sisi kanan masing-masing constraint
Matrix A = marupakan matrix m x n dari koefisien masing-masing variabel pada
setiap
constraint.
Guna lebih memudahkan dalam mengingat masing-masing koefisien maka di
bagian paling atas tabel simpleks dituliskan simbol masing-masing variabel menjadi:
Tabel 2.2
14
Dari tabel simpleks awal dapat diketahui dengan mudah solusi fisibel dasar awal (
initial basic feasible solution ) karena untuk setiap kolom dari variabel basis
terdapat koefisien yang bernilai satu demikian juga untuk setiap barisnya. Nilai
dari variabel basis dengan demikian dinyatakan oleh nilai sisi kanan yang berada
pada kolom bi. Misalkan nilai S2 adalah 1000
Tabel 2.3
2.3.6. Perbaikan Solusi
Guna meningkatkan solusi maka metode simpleks harus menghasilkan solusi
fisibel dasar ( basic feasible solution ) yang baru ( ekstreme point ) yang memberikan
perbaikan pada nilai fungsi tujuan. Hal ini dilakukan dengan mengganti salah satu
variabel basis dengan variabel bukan basis, artinya menetapkan variabel yang semula
adalah bukan basis untuk menggantikan satu variabel yang semula variabel basis.
Metode simpleks memberikan cara dan prosedur untuk proses penggantian variabel
ini. Untuk lebih memudahkan proses maka ditambahkan dua kolom pada bagian kiri
tabel simpleks awal, satu kolom diberi label Basis dan kolom lainnya diberi label Cb.
Pada kolom basis ditulis nama variabel basis sedangkan pada kolom Cb ditulis nilai
koefisien dari variabel basis tersebut seperti terdapat pada fungsi tujuan.
Untuk kasus persoalan di atas maka tabel simpleks menjadi :
Tabel 2.4
15
Untuk mengetahui apakah perbaikan solusi masih dapat dilakukan, maka
ditambahkan dua baris lagi pada bagian bawah tabel simpleks ini. Baris yang satu
diberi label Zj yang menunjukkan perubahan pada nilai fungsi tujuan jika satu unit
variabel matrix A pada kolom j dimasukkan menjadi variabel basis. Baris yang kedua
diberi label Cj-Zj yang menyatakan pengaruh neto dari pemasukan satu unit variabel
tersebut pada nilai fungsi tujuan. Baris ini disebut baris evaluasi netto ( net evaluation
row ). Berikut disajikan bagaimana elemen baris Zj disusun bila satu unit variabel X1
menjadi variabel dasar sedangkan variabel X2 tetap sebagai bukan variabel dasar yang
bernilai nol. Dari persamaan pembatas (constraint) pertama diketahui:
2X1 + 2X2 + S1 = 800
Variabel dasar saat ini adalah S1, dan jika X1 yang merupakan bukan variabel
dasar nilainya ditingkatkan satu unit dari 0 menjadi 1 maka nilai S1 harus dikurangi 2
unit agar tetap memenuhi pembatas pertama tersebut. Dari pembatas kedua dan
seterusnya maka variabel S2 juga harus dikurangi 2 unit, variabel S3 berkurang 1 unit
dan variabel S4 berkurang 2 unit. Setelah dilakukan analisis untuk semua persamaan
pembatas maka dapat dikatakan koefisien pada kolom X1 menunjukkan jumlah unit
dari variabel dasar harus dikurangkan dengan masuknya variabel X1 menjadi variabel
dasar bernilai 1 untuk tetap menjaga terpenuhinya semua pembatas. Hal yang sama
dapat dilakukan untuk bukan variabel dasar lainnya seperti X2. Dengan menetapkan X1
sebagai bukan variabel dasar benilai 0 maka untuk satu unit penambahan nilai X2 dari
0 menjadi 1 maka variabel S1 harus dikurangi 2 unit, S2 berkurang 2.3 unit, S3
berkurang 0.5 unit dan S4 berkurang 1.5 unit supaya tetap memenuhi semua fungsi
pembatas secara simultan. Karena kolom Cb merupakan koefisien dari variabel dasar
pada fungsi tujuan maka untuk menghitung perubahan nilai fungsi tujuan (Zj) apabila
nilai variabel dasar Xj meningkat dari nol menjadi 1 adalah:
Z1 = 0(2)+ 0(2) + 0(1) + 0(2) = 0
Z2 = 0(2)+ 0(2.3)+ 0(0.5)+ 0(1.5) = 0
Z3 = 0(1)+ 0(0) + 0(0) + 0(0) = 0
Z4 = 0(0)+ 0(1) + 0(0) + 0(0) = 0
Z5 = 0(0)+ 0(0) + 0(1) + 0(0) = 0
16
Z6 = 0(0)+ 0(0) + 0(1) + 0(1) = 0
Karena nilai koefisien C1, C2, C3, C4, C5, C6 pada fungsi tujuan masing-