Isi-2 [PDF]

Citation preview

BAB I PENDAHULUAN A. LATAR BELAKANG MASALAH Programan linier merupakan kelompok teknik analisis kuantitatif yang mengandalkan model matematika atau model simbolik sebagai wadahnya. Artinya, setiap permasalahan yang kita hadapi dalam suatu sistem permasalahan tertentu harus kita rumuskan dulu dalam simbol-simbol matematika. Programan linier berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu model matematika yang terdiri dari sebuah fungsi tujuan linier dengan beberapa kendala linier. Programan linier meliputi perencanaan aktivitas untuk mendapatkan hasil optimal, yaitu sebuah hasil yang mencapai tujuan terbaik menurut model matematika diantara semua kemungkinan alternatif yang ada. Ada beberapa bagian yang menjadi karakteristik pemerograman linier seperti : fungsi tujuan untuk memaksimumkan atau meminimumkan sesuatu, fungsi pembatas yang membatasi tingkatan pencapaian tujuan , adanya beberapa alternatif tindakan yang bisa dipilih, fungsi tujuan dan kendala dalam permasalahan diekspresikan dalam bentuk persamaan atau pertidaksamaan linier. Metode simpleks merupakan suatu metode yang secara sistematis dimulai dari suatu pemecahan dasar yang dimungkinkan ke pemecahan dasar lainnya dan ini dilakukan tahap demi tahap yang disebut dengan iterasi ( dengan jumlah iterasi yang terbatas) sehingga pada akhirnya akan tercapai suatu pemecahan dasar yang optimum dan setiap langkah menghasilkan suatu nilai dari fungsi tujuan yang selalu lebih optimal atau sama dengan langkah-langkah sebelumnya. Metode simpleks ini terbagi menjadi dua yaitu simpleks primal dan simpleks dual. Metode simpleks primal dengan variabel buatan (variabel artificial) terbagi menjadi dua lagi yaitu Metode-M ( metode penalty) dan dua fase. Namun disini kami hanya akan membahas metode simpleks primal dengan variabel buatan khususnya Metode-M ( metode penalty ). Berdasarkan hal tersebut, maka penulis ingin membuat makalah dengan judul “Metode Simpleks Primal dengan Variabel buatan (Artificial)” yang bertujuan untuk membahas Metode-M atau Metode Penalty secara lebih luas.



1



B. RUMUSAN MASALAH Berdasarkan latar belakang diatas, maka rumusan masalah dari makalah ini adalah sebagai berikut : 1.



Bagaimana metode simpleks primal dengan variabel buatan (artificial) menggunakan Metode-M ?



2.



Bagaimana langkah-langkah penyelesaian metode simpleks primal dengan variabel buatan (artificial) menggunakan Metode-M ?



C. TUJUAN MASALAH Berdasarkan rumusan masalah diatas, maka tujuan masalah dari makalah ini adalah sebagai berikut : 3.



Untuk mengetahui metode simpleks primal dengan variabel buatan (artificial) menggunakan Metode-M



4.



Untuk mengetahui langkah-langkah penyelesaian metode simpleks primal dengan variabel buatan (artificial) menggunakan Metode-M



D. MANFAAT MASALAH Berdasarkan tujuan masalah diatas, maka manfaat masalah dari makalah ini adalah sebagai berikut : 1.



Dapat mengetahui metode simpleks primal dengan variabel buatan (artificial) mengunakan Metode-M



2.



Dapat mengetahui langkah-langkah penyelesaian metode simpleks primal dengan variabel buatan (artificial) menggunakan Metode-M



2



BAB II PEMBAHASAN A. METODE SIMPLEKS PRIMAL DENGAN METODE-M Metode simpleks merupakan suatu metode yang secara sistematis dimulai dari suatu pemecahan dasar yang dimungkinkan ke pemecahan dasar lainnya dan ini dilakukan tahap demi tahap yang disebut dengan iterasi ( dengan jumlah iterasi yang terbatas) sehingga pada akhirnya akan tercapai suatu pemecahan dasar yang optimum dan setiap langkah menghasilkan suatu nilai dari fungsi tujuan yang selalu lebih optimal atau sama dengan langkah-langkah sebelumnya. Sering kita menemukan bahwa fungsi kendala tidak hanya dibentuk oleh pertidaksamaan ≤ tapi juga oleh pertidakasamaan ≥ dan/atau persamaan (=). Fungsi kendala dengan pertidaksamaan ≥ mempunyai surplus variable, dan tidak ada slack variables. Surplus variable tidak bisa menjadi variabel basis awal. Dengan demikian harus ditambahkan satu variabel baru yang dapat berfungsi sebagai variabel basis awal. Variabel yang dapat berfungsi sebagai variabel basis awal hanya slack variables dan artificial variables (variabel buatan). 1.



Jika semua fungsi kendala menggunakan pertidaksamaan



≤



maka



variabel basis awal semuanya adalah slack variables. Penyelesaian solusi optimal untuk kasus seperti ini dilakukan dengan cara yang sudah diperkenalkan sebelumnya. 2. Jika fungsi kendala menggunakan pertidaksamaan ≥ dan/atau ≤ maka variabel basis awal adalah slack variables dan/atau variabel buatan. Penyelesaian solusi optimal untuk kasus seperti ini dilakukan dengan memilih antara metode Big M, Dua Fase atau Dual Simpleks. 3. Jika fungsi kendala ada yang menggunakan persamaan maka variabel buatan akan ditemukan pada variabel basis awal. Penyelesaian solusi optimal untuk kasus seperti ini hanya dapat dilakukan dengan memilih antara metode Big M atau Dua Fase. Perbedaan metode Big M dengan primal simpleks biasa (teknik penyelesaian yang sudah dipelajari sebelumnya), terletak pada pembentukan tabel 3



awal. Jika fungsi kendala menggunakan bentuk pertidaksamaan ≥, perubahan dari bentuk umum ke bentuk baku memerlukan satu variabel surplus. Variabel surplus tidak dapat berfungsi sebagai variabel basis awal, karena koefisiennya bertanda negatif. Sebagai variabel basis pada solusi awal, harus ditambahkan satu variabel buatan. Variabel buatan pada solusi optimal harus bernilai 0, karena variabel ini memang tidak ada. Teknik yang digunakan untuk memaksa variabel buatan bernilai 0 pada solusi optimal adalah dengan cara berikut : 1.



Penambahan variabel buatan pada fungsi kendala yang tidak memiliki variabel slack, menuntut penambahan variabel buatan pada fungsi tujuan.



2.



Jika fungsi tujuan adalah maksimisasi, maka variabel buatan pada fungsi tujuan mempunyai koefisien +M; jika fungsi tujuan adalah minimisasi, maka variabel buatan pada fungsi tujuan mempunyai koefisien -M.



3.



Karena koefisien variabel basis pada tabel simpleks harus bernilai 0, maka variabel buatan pada fungsi tujuan harus digantikan nilai dari fungsi kendala yang memuat variabel buatan tersebut.



B. LANGKAH-LANGKAH MENGGUNAKAN METODE-M Adapun langkah-langkah yang dilakukan untuk menyelesaikan masalah maksimasi/minimasi dengan menggunakan metode-M adalah sebagai berikut : 1.



Menstandarisasi fungsi kendala dengan menambahkan variabel buatan pada fungsi kendala tersebut. Kehadiran variabel buatan pada fungsi kendala juga menyebabkan kehadirannya pada fungsi tujuan. Jika fungsi tujuan adalah maksimisasi, maka variabel buatan pada fungsi tujuan mempunyai koefisien -M; jika fungsi tujuan adalah minimisasi, maka variabel buatan pada fungsi tujuan mempunyai koefisien +M.



2.



Membuat tabel simpleks awal.



3.



Melakukan iterasi pertama, iterasi kedua, dan seterusnya sampai tidak ada lagi elemen yang positif pada baris persamaan Z (minimasi) atau sampai semua elemen positif pada baris persamaan Z (maksimasi).



4



C. CONTOH SOAL METODE-M/METODE PINALTI 1.



Contoh 1 : Bila diketahui model LP sebagai berikut : Fungsi Tujuan : Minimum Z = 2X1+4X2 Fungsi Kendala: (1) 2X1+X2



≥14



(2) X1+X2



≥12



(3) X1+3X2



≥18



(4) X1≥ 0 ; X2 ≥ 0 Tentukan solusi optimal model LP tersebut dengan metode simpleks! Penyelesaian : Langkah 1 : Buatlah tabel simpleks awal (initial table) (1) 2X1 + X2 ≥ 14 → 2X1 + X2 - S1 + A1 = 14 (2) X1 + X2 ≥ 12 → X1 + X2 - S2 + A2 = 12 (3) X1 + 3X2 ≥ 18 → X1 + 3X2 - S3 + A3 = 18 Tabel Simpleks Awal ( Sementara)



Tabel Simpleks Awal



5



Langkah 2 : Langkah algoritma simpleks Dalam hal ini, kolom pivotnya adalah kolom 2 (elemen baris indikator bernilai positif terbesar) dengan entering variablenya X2, baris pivotnya adalah baris 3 (memiliki nilai rasionya terkecil yaitu 6) dengan leaving variablenya S3, dan elemen pivotnya adalah 3.



Kemudian dilakukan



pivoting, sehingga diperoleh tabel pivoting berikut :



Selanjutnya lakukan operasi baris terhadap baris pivot sehingga semua elemen pada kolom pivot (kolom X2) bernilai nol, kecuali elemen pivot. Dalam hal ini, untuk baris 1 (baris S1) operasi baris − B3 , untuk baris 2 (baris S2) dilakukan operasi baris − B3, dan untuk baris Z dilakukan operasi baris − (5M − 4)B3. Sehingga diperoleh tabel simpleks pertama sebagai berikut :



Langkah 3 : Karena pada baris indikator masih ada elemen bernilai positif, maka solusi optimal belum tercapai.



Selanjutnya dilakukan iterasi pertama dengan



algoritma simpleks seperti di atas. Dalam hal ini, kolom pivotnya adalah kolom 1 dengan entering variablenya X1, baris pivotnya adalah baris 1 dengan leaving variablenya S1, dan elemen pivotnya adalah 5/3. Kemudian dilakukan pivoting, sehingga diperoleh tabel pivoting berikut : Selanjutnya lakukan operasi baris terhadap baris pivot sehingga semua elemen pada kolom pivot (kolom X1) bernilai nol, kecuali elemen pivot, sehingga diperoleh tabel simpleks kedua sebagai berikut:



6



Langkah 4 : Karena pada baris indikator masih ada elemen bernilai positif, maka solusi optimal belum tercapai. Selanjutnya dilakukan iterasi kedua dengan algoritma simpleks seperti di atas. Dalam hal ini, kolom pivotnya adalah kolom 3 dengan entering variablenya S1, baris pivotnya adalah baris 2 dengan leaving variablenya S2, dan elemen pivotnya adalah 2/5. Kemudian dilakukan pivoting, sehingga diperoleh tabel pivoting berikut :



Selanjutnya lakukan operasi baris terhadap baris pivot sehingga semua elemen pada kolom pivot (kolom S1) bernilai nol, kecuali elemen pivot, sehingga diperoleh tabel simpleks ketiga sebagai berikut :



Pada baris indikator sudah tidak ada elemen yang bernilai positif, berarti solusi optimal telah tercapai dan tabel simpleks ketiga tersebut juga merupakan tabel simpleks optimal. Solusi optimal tercapai pada saat X1 = 9, X2 = 3, S1 = 7, S2 = 0, dan S3 = 0 dengan Z minimum sebesar 30. Recheck : Jika X1 = 9, X2 = 3 disubstitusikan ke dalam pesamaan fungsi tujuan : Z = 2X1 + 4X2 maka diperoleh Z = 2(9) + 4(3) = 30.



7



2.



Contoh 2 : Maksimumkan Z = 3x1 + 5x2 + 2x3 dengan kendala: 2x2 - x3 ≤ -2 x1 + 4x2 + 2x3 = 5 x1,x2, x3 ≥ 0 Penyelesaian: Maksimumkan Z = 3x1 + 5x2 + 2x3 Dengan kendala : -2x2 + x3 ≥ 2 x1 + 4x2 + 2x3 = 5 x1,x2, x3 ≥ 0 Bentuk kanonik kendala utama : -2x2 + x3 –x4 + x5 = 2 x1 + 4x2 + 2x3



=5



x1,x2, x3, x4, x5 ≥ 0 Maksimumkan Z = 3x1 + 5x2 + 2x3 + 0x4 – Mx5 Tabel simpleksnya adalah sebagai berikut :



8



D. LATIHAN SOAL 1.



Minimumkan 𝑍 = 4𝑥1 + 3𝑥2 Terhadap 2𝑥1 + 𝑥2 ≥ 50 𝑥1 + 2𝑥2 ≥ 40 5𝑥1 + 4𝑥2 ≥ 170 𝑥1 , 𝑥2 ≥ 0



2.



Minimumkan 𝑍 = 4𝑥1 + 𝑥2 Terhadap 3𝑥1 + 𝑥2 = 3 4𝑥1 + 3𝑥2 ≥ 6 𝑥1 + 2𝑥2 ≤ 4 𝑥1 , 𝑥2 ≥ 0



9



BAB III PENUTUP A. SIMPULAN Berdasarkan pembahasan yang telah dilakukan, maka diperoleh kesimpulan sebagai berikut : 1.



Metode



simpleks



primal



dengan



Metode-M



dilakukan



dengan



menambahkan variabel buatan (artificial) pada fungsi tujuan dan fungsifungsi kendalanya 2.



Adapun langkah-langkah yang dilakukan untuk menyelesaikan masalah maksimasi/minimasi dengan menggunakan metode-M adalah : (a) menstandarisasi fungsi kendala dan fungsi tujuan dengan menambahkan variabel buatan pada kedua fungsi tersebut, (b) membuat tabel simpleks awal, dan (c) melakukan iterasi pertama, iterasi kedua, dan seterusnya sampai tidak ada lagi elemen yang positif pada baris Z (minimasi) atau sampai semua elemen positif pada baris Z (maksimasi).



B. SARAN Adapun saran yang dapat diberikan oleh penulis kepada pembaca adalah agar pembaca lebih teliti dalam perhitungan yang ada di dalam proses pengerjaan metode-M ini sehingga tidak terjadi kesalahan dalam menentukan nilai-nilai yang ada dan agar pembaca lebih mempelajari lagi tentang materi simpleks primal dengan variabel buatan (artificial) ini .



10



DAFTAR PUSTAKA Dumairy, Ning; dkk. 2016. Matematika Terapan untuk Bisnis dan Ekonomi. Yogyakarta : BPFE-Yogyakarta Syahputra, Edi. 2015. Program Linier. Medan : Unimed Press https://ayundyahkesumawati.files.wordpress.com/2015/03/perkuliahan_4bigm.pdf (23 September 2018) https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rj a&uact=8&ved=2ahUKEwjhorbx3dDdAhUIMo8KHZKRB-8QfjAAe gQIABAC&url=http%3A%2F%2Fishaq.staff.gunadarma.ac.id%2FDown loads%2Ffiles%2F43852%2Fmetode-big-m-dua-fase-dan-dual-simpleks. pdf&usg=AOvVaw0d3L h4S8Pyznvn7480hZif (23 September 2018)



11