METODE LINEAR PROGRAMMING Terbaru [PDF]

Citation preview

DAFTAR ISI BAB II..................................................................................................................................2 METODE LINEAR PROGRAMMING..............................................................................2 2.1



Definisi Linier Programming...........................................................................2



2.2



Manfaat Penggunaan Linear Programming....................................................3



2.3



Metode yang digunakan.................................................................................4



2.4



Kegunaan Linear Programming.......................................................................4



2.5



Empat Ciri Khusus Yang Linear Programming Yang Melekat...........................5



2.6



Lima Syarat Tambahan Yang Ada Pada Permasalahan Linear Programming...5



2.7 Model Matematis dan Kendala dalam Linier Programming.........................................7



BAB II METODE LINEAR PROGRAMMING 2.1 Definisi Linier Programming Linear Programming merupakan salah satu pendekatan matematik yang paling sering diterapkan manajerial dalam pengambilan keputusan. Tujuan dari penggunaan linear programming adalah untuk menyusun suatu model yang dapat dipergunakan untuk membantu pengambilan keputusan dalam menentukan alokasi yang optimal dari sumber daya perusahaan ke berbagai alternatif. Penggunaan linear programming dalam hal ini adalah mengalokasikan sumber daya tersebut, sehingga laba akan maksimum atau alternatif biaya minimum. Alokasi yang dibuat tergantung dari sumber daya yang tersedia dan permintaan atas sumber daya tersebut. Sedangkan tujuan dari alokasi adalah memaksimumkan laba atau meminimalkan biaya. Jadi linear programming adalah sebuah metode matematis yang berkarakteristik linear untuk menemukan suatu penyelesaian optimal dengan cara memaksimumkan atau meminimumkan fungsi tujuan terhadap satu susunan kendala. Program ini memuat metode grafik, simpleks, eliminasi, subtitusi, campuran dan dualitas yang digunakan pada proses alokasi. Program ini akan menjawab persoalan bila: a. Terdapat sejumlah kegiatan untuk dilaksanakan dan terdapat alternative cara untuk melaksanakannya.



b. Sumber dan fasilitas tidak tersedia untuk melaksanakan tiap kegiatan dengan cara yang paling efektif. Persoalan ialah menggabungkan kegiatan dan sumber sedemikian rupa hingga terdapat efektivitas keseluruhan secara maksimal. Berikut ini adalah pendapat yang dikemukakan oleh beberapa ahli: Morse dan Kimball (1951), mendefinisikan Riset Operasi sebagai metode ilmiah yang memungkinkan para manajer mengambil keputusan mengenai kegiatan yang mereka tangani dengan dasar kuantitatif. Yang di muat dalam (Meflinda & Mahyarni, 2011). Sedangkan Churchman, Arkoff dan Arnoff (1957) mengemukakan pengertian riset operasi sebagai aplikasi metode-metode, teknik-teknik, dan peralatan-peralatan ilmiah dalam menghadapi masalah-masalah yang timbul didalam operasi perusahaan dengan tujuan ditemukannya pemecahan yang optimum masalah-masalah tersebut. Yang di muat dalam (Meflinda & Mahyarni, 2011). Miller dan M.K. Star (1960) mengartikan Riset Operasi sebagai peralatan manajemen yang menyatukan ilmu pengetahuan, matematika, dan logika dalam kerangka pemecahan masalah- masalah yang dihadapi seharihari, sehingga akhirnya permasalahan tersebut dapat dipecahkan secara optimal. Yang di muat dalam (Meflinda & Mahyarni, 2011). Dimuat



dalam



(Prasojo,



Bayu



Hari,



2018)



Definisi



Linear



programming adalah suatu teknis matematika yang dirancang guna membantu



manajer dalam merencanakan dan membuat keputusan dalam mengalokasikan sumber daya yang terbatas guna mencapai tujuan perusahaan. Dinyatakan oleh (Hutabarat, 2022) definisi Linear Programing ialah suatu metode analitik paling terkenal dan yang merupakan suatu bagian pada kelompok teknik-teknik yang disebut dengan programisasi matematik. Menurut (Kurniawati, N., & HANDAYANI, 2019) pengertian linear Programing ialah suatu teknik perencanaan yang dengan menggunakan model matematika dengan tujuan untuk menemukan kombinasi-kombinasi produk yang terbaik didalam menyusun suatu alokasi sumber daya yang terbatas guna untuk mencapai tujuan yang digunakan dengan secara optimal. Linear Programing ialah suatu cara yang lazim digunakan dalam pemecahan suatu masalah pengalokasian sumber-sumber yang terbatas dengan secara optimal. Yang dikutip dalam buku karya (Hutabarat, 2022) Menurut Heizer dan Render (2006), pemrograman linier atau Linear Programming (LP) merupakan suatu cara untuk menyelesaikan persoalan pengalokasian sumber-sumber yang terbatas diantara beberapa aktivitas yang bersaing, dengan berbagai cara yang terbaik yang mungkin dilakukan.dikutip dalam(Peternakan & Rimba, 2022) Adapun tujuan dari penggunaan linear programming yang dimuat dalam (Prasojo, Bayu Hari, 2018) Dengan mempelajari Linear Programming, diharapkan Anda dapat memahami permasalahan manajemen operasional dan menemukan solusinya secara efektif dan efisien.



Fungsi tujuan (constraint function) adalah rumusan fungsi yang menjadi sasaranuntuk mencapai pemecahan optimum (maksimisasi atau minimisasi), sedangkan fungsi batasan (constraints functoin) merupakan rumusan dari sediaan sumberdaya yang membatasi proses optimasi. Program linier merupakan model analisis yang diterapkan untuk mengalokasikan sumberdaya yang terbatas pada penggunaan sumberdaya yang bersaing dengan cara sedemikian rupa guna mendapatkan pemecahan yang optimal menurut (Natalia dkk,2013) yang di muat dalam (Aprilyanti, 2019). Dari definisi diatas dapat disimpulkan bahwa Riset Operasi berkenaan dengan pengambilan keputusan optimal dalam penyusunan model dari sistemsistem baik deterministic maupun probabilistic yang berasal dari kehidupan nyata. Aplikasi-aplikasi ini, yang terjadi dalam pemerintah, bisnis, teknik, ekonomi, serta ilmu pengetahuan alam dan social ditandai dengan kebutuhan untuk mengalokasikan sumberdaya-sumberdaya yang terbatas. 2.2



Model linear programming Model linear programming merupakan bentuk dan susunan dalam menyajikan masalah-masalah yang akan dipecahkan dengan teknik Linear Programming (LP). Model LP mempunyai tiga unsur utama, yaitu: 1. Variabel keputusan yaitu variabel persoalan yang akan mempengaruhi nilai tujuan yang hendak dicapai. Didalam proses pemodelan, penemuan variabel keputusan harus dilakukan terlebih dahulu sebelum merumuskan fungsi tujuan dan fungsi batasan (kendala-kendalanya). Misalnya dengan



mengajukan pertanyaan: keputusan apa yang harus dibuat agar nilai fungsi tujuan menjadi maksimum atau minimum. 2. Fungsi tujuan yaitu fungsi yang menggambarkan tujuan dalam permasalahan LP yang berkaitan dengan pengaturan secara optimal sumber daya - sumber daya, untuk memperoleh keuntungan maksimal atau biaya minimum. Dengan simbol Z. Oleh karena itu hanya ada dua kemungkinan fungsi tujuan, yaitu a. Maksimumkan Z = f (X1, X2, ...Xn) b. Minimumkan Z = f (X1, X2, ...Xn) 3. Fungsi batasan (kendala) yaitu bentuk penyajian secara matematis batasan-batasan kapasitas yang tersedia yang akan dialokasikan secara optimal ke berbagai kegiatan. Untuk memudahkan pembahasan model Linear Programming ini, digunakan simbol-simbol sebagai berikut: Xj = banyaknya kegiatan j ( j = 1, 2, ..., n). Variabel Xj ini disebut juga dengan variabel keputusan (decision variables) Z = nilai fungsi tujuan yang diopotimalkan (maksimum atau minimum) Cj = kenaikan nilai Z apabila ada pertambanhan tingkat kegiatan (X j) dengan satu satuan (unit) atau merupakan keuntungan per unit (masalah maksimasi), biaya per unit (masalah minimasi) kegiatan j terhadap nilai Z. aij = banyaknya sumber i yang di perlukan guna menghasilkan setiap unit output kegiatan j (i = 1, 2, ..., m, dan j = 1,2, ..., n) bi = banyaknya sumber (fasilitas) i yang tersedia untuk dialokasikan ke



setiap unit kegiatan (i = 1,2, ..., m) Keseluruhan simbol-simbol diatas selanjutnya disusun ke dalam bentuk tabel standar Linear Programming, seperti pada Tabel 2.1 di bawah ini: Tabel 2.1. Data Model linear programming (Meflinda & Mahyarni, 2011) Sumber Kegiatan



Pemakaian sumber per unit



Kapasitas sumber



1



2



1



a11



a12



2



a21



a22



.



.



.



. ......... .



.



.



.



.



. ......... .



.



m



am1



am2



am3 ........ anm



∆ Z per unit



c1



c2



c3 ......... cn



Banyak kegiatan



x1



x2



3............n a13.........a1n



b1



a23.........a2n



b2



bm



x3 ......... xn



Atas dasar Tabel 2.1 di atas, dapat disusun model standard Linear Programming sebagai berikut: Fungsi tujuan : Maksimumkan/minimumkan: Z = ∑ C j.X = C1X1 + C2X2 + ... + CnXn Dengan kendala atau batasan:







Batasan pertama artinya: jumlah hasil (barang/jasa) 1 yang dihasilkan oleh kegiatan 1 dikalikan dengan kebutuhan akan sumber 1 per satuan (berarti total alokasi 1 untuk kegiatan 1) ditambah dengan hasil kegiatan 2 dikalikan dengan kebutuhan tiap satuan keluaran 2 terhadap sumber 1 (dan seterusnya sampai dengan kegiatan ke-n) tidak akan melebihi atau sama dengan atau tidak boleh kurang dari jumlah (kapasitas) tersedianya sumber 1 (yang dinyatakan dengan b1). Hal ini berlaku untuk batasan-batasan lainnya sampai ke m.







Fungsi-fungsi batasan dapat di kelompokkan menjadi 2 macam, yaitu: 1. Fungsi batasan fungsional, adalah fungsi-fungsi batasan sebanyak m yaitu a11X1 + a12X2 + ... + a1nXn 2. Fungsi batasan non negatif (non negative constraints) yaitu fungsifungsi batasan yang dinyatakan dengan Xi > 0







Variabel Xj disebut sebagai variabel keputusan (decision variables)







aij, bi, Cj, yaitu masukan-masukan input konstan, disebut sebagai parameter model.



Manfaat Penggunaan Linear Programming. Manfaat penggunaan linear programming akan terlihat jika Jumlah permintaan



harus sama dengan jumlah penawaran Persamaan linear atau



disebut juga sebagai persamaan garis adalah persamaan yang mengandung peubah dengan pangkat tertinggi 1. Suatu persamaan linear minimal mengandung salu peubah. Persamaan linear dengan satu peubah bisa diselesaikan secara langsung dengan menggunakan konsep aljabar. Sedangkan untuk persamaan linear dengan dua peuban atau iebih,. untuk mendapatkan penyelesaannya memerlukan minimal persamaan sebanyak peubah pada masing-masing persamaan. Dua persamaan linear atau lebih yang memiliki penyelesaian yang sama disebut sebagai system persamaan linear. system persamaan linear bisa diselesaikan dengan menggunakan metode grafik, substitusi, eliminasi, campuran substitusi-eliminasi, dan dengan menggunakan Matriks. Lincar Programming (Lp) adalah salah satu teknik Riset Operasional untuk



memecahkan



persoalan



optimalisaas



(memaksimalkan



dan



meminimalkan) dengan menggunakan persamaan dan pertidaksamaan linear guna mencari pemecahan yang optimum dengan memperhatikan pembataspembatas yang ada. Dengan demikian dalam keadaan sumber yang terbatas harus dicapai suatu hasil yang optimum, dengan perkataan lain bagaimana cara agar dengan masukan (input) yang serba terbatas dapat dicapai hasil kerja keluaran (Ouput) berupa produk barang dan jasa yang optimum. LP akan memberikan banyak sekali hasil pemecahan persoalan sebai alternatif



pengambilan tindakan atau keputusan akan tetapi hanya ada satu yang optimum.(Sari, 2018) 2.3 Metode yang digunakan Berikut beberapa metode/pendekatan yang dapat digunakan untuk menyelesaikan persoalan-persoalan Linear Programming (LP), yaitu dengan metode grafis dan dengan metode simpleks. Bila persoalan LP hanya mempunyai 2 (dua) variabel keputusan, maka dua metode tersebut dapat dipergunakan. Bila variabel yang terlibat dalam penyelesaian LP lebih dari dua, maka metode grafis tidak dapat dipergunakan lagi. Metode yang lazim diterapkan untuk memecahkan persoalan LP yang mempunyai variabel keputusan lebih dari dua adalah metode simpleks. Melalui metode simpleks, kombinasi variabel keputusan optimal diselesaikan dengan menggunakan pendekatan matematis. Program Linear Sistem Persamaan Linear Dua Variabel Suatu program linear dalam bentuk Sistem Persamaan Linear Dua Variabel dapat diselesaikan dengan beberapa metode, yakni: a. Metode Grafik Metode grafik



dapat



digunakan



untuk



pemecahan



masalah



pemrograman linier yang hanya memiliki dua atau tiga variabel. Grafik disusun dari persamaan yang telah diformulasikan sedemikian sehingga akan didapatkan titik-titik sebagai solusi, yang merupakan hasil dari perpotongan garis. Apabila dalam suatu pemrograman linear terdapat lebih dari 2 variabel, yaitu misalnya tiga variabel dan , maka metode grafik ini tidak dapat digunakan. Berikut ini adalah langkah-langkah pemecahan



dengan metode grafik : 1. Gambarkan garis-garis kendala pada sumbu koordinat. Anggap kendalanya sebagai suatu persamaan. 2. Tentukan daerah dalam bidang koordinat yang memenuhi semua kendala (daerah feasible), kemudian tentukan semua titik daerah feasible tersebut. 3. Membuat grafik untuk kendala-kendala yang ada dalam suatu bagian. Untuk membuat fungsi grafik fungsi kendala yang berbentuk pertidaksamaan (≤ dan ≥) diubah terlebih dahulu kedalam bentuk persamaan (=). 4. Menentukan area kelayakan solusi pada grafik tersebut. Area layak dapat dilihat dari pertidaksamaan pada kendala. Apabila kendala dalam bentuk ≤, maka daerah arsiran/layak terjadi pada bagian kiri/bawah/kiri bawah, tetapi apabila bentuk pertidaksamaan ≥, maka pengasrsiran dilakukan ke kanan/atas/kanan atas. Apabila bentuk persamaan (=), maka daerah layak terjadi pada garis tersebut(berimpit). 5. Hitung nilai fungsi tujuan untuk semua titik sudut daerah layak. Untuk keputusannya, plih koordinat titik yang memberikan nilai terbesar untuk fungsi tujuan maksimasi, dan nilai fungsi terkecil untuk tujuanminimasi. Sebagai illustrasi, misal suatu industri UKM memproduksi dua jenis produk yang dikerjakan secara manual, yaitu produk A dan B. Setiap unit produk A memerlukan waktu 20 menit pada proses II dan 24 menit pada proses III, sedangan setiap unit produk B memerlukan waktu 15 menit pada proses I, 16 menit pada proses II, dan 30 menit pada proses III. Produk A memberikan laba sebesar 170/unit dan produk B memberikan laba sebesar 190/. Jam kerja per hari yang tersedia untuk proses I, II, dan III masingmasing 1050 menit, 1600 menit, dan 2400 menit. Tentukan jumlah produksi A dan B untuk memaksimumkan laba. Selanjutnya akan diuraikan penyelesaian contoh kasus diatas dengan menggunakan metode grafik. Terlebih dahulu tuliskan kembali informasi dalam bentuk tabel. Penyelesaian: Strategi pembelajaran program linear menggunakan metode grafik(Asmara et al., 2018) proses



Produk I



Produk II



I



-



15



II



20



16



III



24



30



Laba



170



190



Selanjutnya maksimumkan Z = 170X1 + 190X2 dengan kendala: 150X2 < 1050 20X1 + 16X2 < 1600 24X1 + 30X2 < 2400 X1,X2 > 0 Sedemikian rupa sehingga persamaan yang diperoleh adalah : 



150X2 = 1050 X2 = 70







20X1 + 16X2 = 1600 X1 = 0  X2 = 100 F(0,100) X2 = 0  X2 = 80 D(80,0)







24X1 + 30X2 = 2400 X1 = 0  X2 = 80E(0,80) X2 = 0  X2 = 100H(100,0)



Selanjutnya



Gambar



1.



solusi



dinyatakan



Solusi



dalam



Pemrograman



grafik



Linier



sebagai



Metode



berikut



:



Grafik



Grafik yang ditunjukkan pada Gambar 1 disusun dengan menggunakan aplikasi GeoGebra (Harahap, 2017). Software aplikasi GeoGebra dapat digunakan untuk menggambarkan grafik berdasarkan pada persamaan atau pertidaksamaan yang diketahui, atau berdasarkan pada titik-titik koordinat tertentu (Nur’aini, 2017). Berdasarkan pada Gambar 1, daerah yang bersamaan memenuhi ketiga kendala ditunjukan oleh area gambar diatas yang diarsir O-ABCD dan dinamakan sebagai daerah feasible, karena memenuhi solusi dari semua pembatas yang ada. Titik-titik koordinat dapat diketahui yaitu titik O(0;0), titik



D(80;0), titik A(0;70). Sedangkan titik B dan titik C dapat dicari dengan menemukan perpotongan antara dua garis yang saling menyinggung, yaitu dengan cara substitusi atau eliminasi. Dengan demikian, koordinat dari titik B didapat dengan mensubstitusikan kendala 150 X2 = 1050 dengan kendala 20X1 + 16X2 = 1600 dan diperoleh (12,5;70). Titik C diperoleh dengan cara yang sama antara kendala 20X1 + 16X2 = 166 dengan kendala 24X1 + 30X2 = 2400 yaitu (400/9;400/9). Selanjutnya dilakukan pengujian dari seluruh titik koordinat didaerah feasible yang diperoleh ke persamaan tujuan. Maka akan diperoleh hasil terbesar untuk masalah maksimasi dan hasil terkecil untuk masalah minimasi. Titik A : Z = 170(0) + 190(70) = 13.300 Titik D : Z = 170(80) + 190(0) = 13.600 Titik B : Z = 170(12,5) + 190(70) = 15.425 Titik C : Z = 170(400/9) + 190(400/9) = 16.000 Dari pengujian daerah feasible, maka yang memberikan nilai optimum adalah titik C. Jadi jumlah produksi 1 (X1) yang harus dibuat adalah 400/9 dan jumlah produksi 2 (X2) yang harus dibuat adalah 400/9 agar produksi maksimal dengan keuntungan optimum sebesar Rp.16.000. b. Metode Eliminasi Penyelesaian suatu program linear dengan cara elimimnasi dapat dilakukan dengan menyelesaikan sistem persamaan linear dua variabel menggunakan cara eliminasi dan menghilangkan suatu variabel dari sistem persamaan linear dua variabel dengan menyamakan koefisien dari sistem persamaan linear dua variabel yang ada. c. Metode Subtitusi Menurut Kamus Besar Bahasa Indonesia (KBBI), substitusi berarti penggantian. Metode substitusi dilakukan dengan melakukan penggantian variabel pada persamaan yang satu dengan persamaan lainnya. Metode ini digunakan dengan syarat salah satu persamaan telah diselesaikan untuk variabel tertentu (Fauzziyah, 2020). Metode subtitusi merupakan suatu cara penyelesaian program linear dengan mengganti salah satu variabel dalam sistem persamaan linear dua variabel. Penyelesaian suatu program linear dengan metode subtitusi dapat



dilakukan dengan langkah-langkah: a. Ganti salah satu variabel dalam sistem persamaan linear dua variabel menjadi persamaan dalam bentuk: 𝑥 = 𝑎𝑦 + 𝑏 atau 𝑦 = 𝑐𝑥 + 𝑑. b. Subtitusikan persamaan tersebut ke dalam persamaan kedua. c. Selesaikan persamaan kedua yang sudah disubstitusikan. d. Subtitusikan nilai variabel yang sebelumnya sudah didapatkan ke persamaan pertama. d. Metode Campuran Metode campuran adalah suatu metode untuk menyelesaikan sistem persamaan linear dua variabel yang merupakan campuran dari metode eliminasi dan metode subtitusi. e. Metode simpleks Metode Simpleks merupakan salah satu teknik penyelesaian dalam pemrograman linier yang digunakan sebagai teknik pengambilan keputusan dalam permasalahan yang berhubungan dengan pengalokasian sumberdaya secara optimal yang meliputi banyak pertidaksamaan dan banyak variabel. Beberapa studi telah dilakukan dengan menggunakan pendekatan metode Simpleks. Penelitian Wulandari (2012) misalnya melakukan kajian di UD Pabrik Tahu Sukajaya Klender, Jakarta Timur. Kelebihan dari metode ini adalah mampu menghitung dua atau lebih variabel keputusan apabila dibandingkan dengan metode grafik yang hanya mampu mengaplikasikan dua variabel keputusan. Beberapa istilah yang digunakan dalam metode simpleks adalah sebagai berikut: a) Iterasi, seperti yang disebutkan sebelumnya adalah tahapan perhitungan dimana nilai dalam perhitungan itu tergantung dari nilai tabel sebelumnya. b) Variabel non basis, adalah variabel yang nilainya diatur menjadi nol pada sembarang literasi. c) Variabel basis, merupakan variabel yang nilainya bukan nol pada sembarang literasi. Pada solusi awal, variabel basis merupakan variabel slack (jika fungsi kendala menggunakan pertidaksamaan atau =). Secara umum, jumlah variabel batas selalu sama dengan jumlah fungsi pembatas. d) Solusi atau Nilai Kanan (NK), merupakan nilai sumber daya pembatas yang masih tersedia. Pada solusi awal, nilai kanan atau solusi sama dengan jumlah sumber daya pembatas awal yang ada. e) Variabel Slack, adalah variabel yang ditambahkan ke model matematik kendala untuk mengkonversikan pertidaksamaan < menjadi persamaan (=).



f) Variabel Surplus, adalah variabel yang dikurangkan dari model matematik kendala untuk mengkonversikan pertidaksamaan > menjadi persamaan (=). g) Variabel Buatan, adalah variabel yang ditambahkan ke model matematik kendala dengan bentuk > atau = untuk difungsikan sebagai variabel basis awal. h) Kolom Kerja, adalah kolom yang memuat variabel masuk. Koefisien pada kolom ini akan menjadi pembagi nilai kanan untuk menentukan baris kerja. i) Baris Pivot (Baris Kerja), adalah salah satu baris dari antara variabel baris yang memuat variabel keluar. j) Elemen Kerja, adalah elemen yang terletak pada perpotongan kolom dan baris pivot. Elemen pivot akan menjadi dasar perhitungan untuk tabel simpleks k) berikutnya. l) Variabel Masuk, adalah variabel yang terpilih untuk menjadi variabel basis pada iterasi berikutnya. Variabel masuk dipilih satu dari antara variabel non basis pada setiap iterasi. Variabel ini pada iterasi berikutnya akan bernilai positif. m) Variabel Keluar, variabel yang keluar dari variabel basis pada iterasi berikutnya dan digantikan dengan variabel masuk. Variabel keluar dipilih satu dari antara variabel basis pada setiap iterasi dan bernilai 0. Langkah-langkah pemecahan dengan metode Simpleks : 1) Mengubah fungsi tujuan dan batasan-batasan. 2) Menyusun persamaan-persamaan didalam tabel. 3) Memilih kolom kunci. 4) Memilih baris kunci. 5) Mengubah nilai-nilai baris kunci. 6) Mengubah nilai-nilai selain pada baris kunci. 7) Melanjutkan perbaikan. Sebagai contoh kasus, misal suatu perusahaan akan membuat kain sutra dan kain wol, yang terbuat dari benang sutra 3kg untuk pembuatan kain sutra dan benang sutra 4kgdan benang wol 1kg untuk pembuatan kain wol. Masingmasing membutuhkan masa kerja 2 jam untuk kain sutra dan kain wol. Benang sutra kurang dari 1200kg, benang wol kurang dari 20kg dan masa kerja kurang dari 40 jam. Berapakah yang harus diproduksi untuk mendapatkan laba maksimal dengan Z = 30X1 + 40X2 ? Solusi untuk kasus diatas adalah sebagai berikut. Langkah pertama, susun informasi dalam bentuk tabel, selanjutnya tampilkan fungsi tujuan dan fungsi kendala.



Strategi pembelajaran simpleks(Asmara et al., 2018) Produk (kain)



program



linear



menggunakan



metode



Benang sutra



Benang wol



Masa kerja



Laba



(kg)



(kg)



(jam)



Sutra



3



-



2



30



Wol



4



1



2



40



120



20



40



Fungsi tujuan : Z = 30X1 + 40X2 Fungsi kendala : -



Benang sutra : 3X1 + 4X2 < 120



-



Benang wol :



-



Masa kerja : 2X1 + 2X2 < 40



X2 < 20



Batasan non negatif : X1,X2,S1,S2,S3 > 0 1) Mengubah fungsi tujuan dan fungsi kendala



 Fungsi Tujuan : Z = 30X1 + 40X2 Z - 30X1 – 40X2 = 0  Fungsi kendala : - Benang Sutra 3X1+ 4X2 < 120 3X1 +4X2 + S1 < 120  Benang wol X2 < 20 X2 + S2 < 20  Masa kerja : 2X1 + 2X2 < 40 2X1 + 2X2 + S3 < 40 2) Menyusun persamaan ke dalam tabel NB



X1



X2



S1



S2



S3



S4



Ind



Z



-30



-40



0



0



0



0



S1



3



4



0



0



0



120



S2



0



1



0



1



0



20



S3



2



2



0



0



1



40



3) Menentukan kolom kunci Kolom kunci adalah kolom yang mempunyai nilai baris Z yang bernilai negatif dengan angka terbesar. NB



X1



X2



S1



S2



S3



S4



Z



-30



-40



0



0



0



0



S1



3



4



0



0



0



120



S2



0



1



0



1



0



20



S3



2



2



0



0



1



40



Ind



5) Menentukan nilai baris kunci baru Baris kunci baru = baris kunci/angka kunci sehingga tabel menjadi sebagai berikut: NB



X1



X2



S1



S2



S3



NK



1



1



0



0



1/2



20



Z S1 S2 X2



6) Mengubah nilai-nilai selain baris kunci Baris baru = baris lama – (nilai kolom kunci*nilai baris kunci baru)



Ind



7) Menentukan nilai baris baru NB



X1



X2



S1



S2



S3



NK



Z



10



0



0



0



20



800



S1



-1



1



0



0



-2



40



S2



-1



0



0



1



-1/2



0



X2



1



1



0



0



1/2



20



Ind



Dari hasil diatas dapat disimpulkan bahwa karena nilai Z sudah positif, maka diperoleh hasil: maka Zmax = 800. Apabila nilai Z masih negatif, maka harus melakukan perbaikan sampai diperoleh nilai Z yang positif. Penyelesaian metode simpleks dapat juga dilakukan dengan menggunakan aplikasi komputer, salah satu aplikasi yang umum digunakan adalah QM for Windows.



Gambar 2. Tampilan input data pada QM for Windows untuk selanjutnya akan diproses penyelesaiannya menggunakan metode simpleks



Gambar 3. Solusi akhir dengan penyelesaian menggunakan metode simpleks Berdasarkan pada Gambar 2 dan Gambar 3, dapat dilihat bahwa nilai optimum yang dihasilkan untuk mendapatkan laba yang maksimal adalah 800 dengan memproduksi kain wol sebanyak 20 kg. Fuzzy Linear Programming Menurut Kusumadewi dan Purnomo (2010), penyelesaian dengan Fuzzy Linear Programming (FLP), adalah pencarian suatu nilai Z yang merupakan fungsi obyektif yang akan dioptimasikan sedemikian rupa sehingga tunduk pada batasanbatasan yang dimodelkan dengan menggunakan himpunan fuzzy. Dalam penjelasan selanjutnya hanya akan dibahas untuk persoalan maksimisasi. Model matematika untuk persoalan maksimasi adalah sebagai berikut: Tentukan x sedemikian hingga : Ctx>z Ax0 Dengan tanda < merupakan bentuk fuzzy dari < yang menginterpretasikan pada dasarnya kurang dari atau sama dengan. Demikian pula, tanda < merupakan bentuk fuzzy dari ‘≥’ yang menginterpretasikan pada dasarnya lebih dari atau sama dengan. Untuk kasus minimasi pada Fuzzy Linear Programming. 2.4 Kegunaan Linear Programming a. linear programming sebagai alat pengambilan keputusan b. Penjadwalan merupakan proses pembuatan keputusan yang digunakan secara rutin dalam industri manufaktur dan jasa [1]. Beberapa hal yang perlu diperhatikan sebelum melakukan penjadwalan produksi adalah jumlah dan jenis pekerjaan, perkiraan waktu penyelesaian



suatu pekerjaan, batas waktu penyelesaian pekerjaan, dan situasi pekerjaan yang dihadapi [2]. Situasi pekerjaan yang dihadapi pada suatu perusahaan dengan perusahaan lainnya dapat berbeda. Perbedaan tersebut meliputi jumlah mesin yang digunakan dan sistem produksi yang berlangsung. Menurut Nasution and Prasetyawan [3] terdapat tiga jenis dasar sistem produksi yaitu proyek, job shop, dan flow shop. Yang di jelaskan dalam(Livia & Oktiarso, 2017). 3.Menurut



(Sugiyono,



2019)



linear



programming



membantu



perusahaan dengan cara mengombinasikan variasi produk yang ada berdasarkan keterbatasan sumber daya yang dimiliki oleh perusahaan. Dengan demikian perusahaan dapat melakukan produksi secara optimal untuk memperoleh keuntungan maksimal. Dimuat dalam (Meflinda & Mahyarni, 2011) Operation Research sangat berguna dalam menghadapi masalah-masalah, bagaimana mengarahkan dan mengkoordinasikan operasi-operasi atau kegiatankegiatan dalam suatu organisasi dengan segala keterbatasannya melalui prosedur “search for optimality”. 2.5 Empat Ciri Khusus Linear Programming Yang Melekat 1.



Penyelesaian



masalah



mengarah



pada



pencapaian



tujuan



maksimalisasi atau minimalisasi. 2.



Kendala yang ada mempengaruhi tingkat pencapaian tujuan.



3



Mempunyai beberapa alternatif penyelesaian



4



Hubungan matematis yang bersifat linear



2.6 Lima Syarat Tambahan Yang Ada Pada Permasalahan



Linear Programming. Secara teknis, ada lima syarat tambahan yang harus diperhatikan yang menjadi asumsi dasar, yaitu: 1. Certainty (kepastian). Maksudnya adalah fungsi tujuan dan fungsi kendala yang sudah diketahui dengan pasti dan tidak akan berubah selama periode analisa. 2. Proportionality (proporsionalitas). Maksudnya adalah adanya proporsionalitas dalam fungsi tujuan dan fungsi kendala. 3. Additivity (penambahan). Artinya aktivitas total sama dengan penjumlahan pada aktivitas individu. 4. Divisibility (bisa dibagi-bagi). Maksudnya adalah solusi tidak harus merupakan bilangan integer (bilangan bulat), tetapi bisa juga berupa pecahan. 5. Non-negative variable (variabel tidak negatif). maksudnya bahwa semua nilai jawaban atau variabel tidak negatif. Dalam



upaya



menyelesaikan



permasalahan



dengan



menggunakan Linear Programming, ada dua pendekatan yang bisa digunakan, yaitu metode grafik dan metode simpleks. Metode grafik hanya bisa digunakan untuk menyelesaikan 3 permasalahan dimana variabel keputusan sama dengan dua. Sedangkan metode simpleks bisa digunakan untuk menyelesaikan permasalahan dimana variabel keputusan ada dua atau lebih. Dalam halaman ini, akan dibahas Linear Programming dengan metode grafik maupun simpleks pada fungsi tujuan baik yang



maksimum



ataupun



Programming,



minimum.



diharapkan



Dengan



Anda



sekalian



mempelajari dapat



Linear



memahami



permasalahan yang ada pada manajemen operasi dan menemukan solusinya secara efektif dan efisien.



Disamping itu, setelah mempelajari buku ini diharapkan Anda dapat: 1. Mengenal serta memahami linear programming sebagai alat pengambilan keputusan 2. Merumuskan permasalahan-permasalahan operasional ke dalam bentuk linear programming. 3. Menyelesaikan



permasalahan-permasalahan



linear



programming menggunakan grafik/ matematik 4. Dapat



memahami



permasalahan



infasibility,



unboundedness, alternative optima, dan redundancy. 2.7 Karakteristik Program Linear Berdasarkan penelitian yang dilakukan oleh Tjutju Tarliyah dan Ahmad Dimyati, suatu program linear umumnya memiliki karakteristik sebagai berikut: 1. Sifat linearitas Sifat linearitas dalam suatu program linear dapat ditentukan secara statistik, dengan menggunakan grafik (diagram pencar) atau uji hipotesa dan ditentukan secara teknis dengan adanya sifat proporsionalitas, additivitas, divisibilitas dan



kepastian fungsi tujuan dan pembatas. 2. Sifat proporsional Sifat proporsional dapat dipenuhi jika terdapat kontribusi setiap variabel pada fungsi tujuan atau penggunaan sumber daya yang membatasi proporsional terhadap level nilai variabel. 3. Sifat addivitas Sifat addivitas dalam program linear mengasumsikan bahwa tidak ada bentuk perkalian silang dalam penyelesaian suatu program linear, sehingga tidak akan ditemukan bentuk perkalian silang pada suatu program linear. Sifat additivitas berlaku bagi fungsi tujuan maupun fungsi pembatas (kendala). Sifat additivitas dipenuhi jika fungsi tujuan merupakan penambahan langsung kontribusi masingmasing variabel keputusan. Sedangkan, dalam fungsi kendala, sifat additivitas dipenuhi jika nilai kanan merupakan total penggunaaan masing-masing variabel keputusan. 4. Sifat divisibilitas Sifat divisibilitas dalam program linear berarti unit aktivitas dapat dibagi dalam berbagai level fraksional, sehingga nilai variabel keputusan non integer dapat dimungkinkan. 5. Sifat kepastian



Sifat kepastian menunjukkan bahwa semua parameter model berupa konstanta, seperti dalam koefisien fungsi tujuan dan fungsi pembatas. 6. Ciri Masalah yang Dapat Diselesaikan Menggunakan Program Linear Menurut Jong Jek Siang, masalah matematika yang dapat diselesaikan dengan program linear mempunyai ciri-ciri, yakni: 1. Semua variabel penyusunnya bernilai positif. 2. Fungsi objektif dapat dinyatakan sebagai fungsi linear variabel-variabelnya. 3. Kendala dapat dinyatakan sebagai suatu sistem persamaan linear. 7. Asumsi Dasar Program Linear Menurut Pangestu Subagyo, Tjutju Tarliyah, dan Ahmad Dimyati, untuk membentuk suatu model program linear perlu diterapkan berbagai asumsi dasar, yaitu: 1. Asumsi Kesebandingan (Proportionality) Asumsi kesebandingan menyatakan bahwa naik turunnya fungsi tujuan akan berubah secara sebanding (proportional) dengan perubahan tingkat kegiatan. Sehingga, bedasarkan asumsi kesebandingan, kontribusi setiap variabel keputusan terhadap fungsi tujuan adalah sebanding. 2. Asumsi Penambahan (Addivity) Asumsi penambahan menyatakan bahwa kontribusi setiap variabel keputusan terhadap fungsi tujuan bersifat tidak bergantung pada nilai dari variabel keputusan



lain atau nilai fungsi tujuan pada setiap kegiatan tidak bersifat saling mempengaruhi. 3. Divisibility (Dapat Dibagi) Asumsi divisibility menyatakan bahwa output atau hasil dari suatu proses dapat berupa bilangan pecahan. 4. Deterministic (Kepastian) Asumsi ini menyatakan bahwa semua konstanta (parameter) yang digunakan dalam program liner diasumsikan mempunyai nilai yang dapat diperkirakan pasti. 8. Istilah dalam Program Linear Menurut Siswanto dan Abdillah, suatu program linear disusun oleh berbagai unsur utama, yakni: 1. Variabel Keputusan Variabel keputusan adalah variabel yang akan mempengaruhi nilai tujuan yang akan dicari. Variabel keputusan umumnya diberikan simbol 𝑢, 𝑣, 𝑤, …, dan jika cukup banyak biasanya digunakan 𝑥1, 𝑥2, 𝑥3, . . . , 𝑦1, 𝑦2, 𝑦3, dan seterusnya. 2. Nilai Ruas Kanan Nilai ruas kanan dalah nilai-nilai yang menunjukkan jumlah ketersediaan sumber daya untuk dimanfaatkan sepenuhnya. Simbol yang digunakan biasanya 𝑏1 dengan 1 adalah banyaknya kendala.



3. Variabel Tambahan Variabel tambahan adalah suatu variabel yang menyatakan penyimpangan positif atau negatif dari nilai ruas kanan. Variabel tambahan dalam program linear yang umumnya diberi simbol 𝑠1, 𝑠2, 𝑠3. 4. Koefisien Teknik Koefisien teknik umumnya diberi simbol 𝑎ij. Koefisien teknik menyatakan setiap unit penggunaan 𝑏j dari setiap variabel 𝑥j. 5. Fungsi Tujuan (fs tujuan) Fungsi tujuan adalah pernyataan matematika linear yang menyatakan hubungan 𝑍 dengan jumlah dari perkalian semua koefisien fungsi tujuan. Fungsi tujuan selanjutnya akan dioptimumkan terhadap berbagai fungsi kendala yang ada. 6. Nilai Tujuan (𝑍) Nilai tujuan adalah nilai dari fungsi tujuan yang belum diketahui dan akan dicari nilai optimumnya. 𝑍 dibuat sebesar mungkin untuk masalah minimum dan dibuat sekecil mungkin untuk masalah maksimum. 7. Koefisien Fungsi Tujuan Koefisien fungsi tujuan adalah nilai yang menyatakan kontribusi per unit kepada 𝑍 untuk setiap j𝑥 dan disimbolkan dengan j𝑐 . 8. Fungsi Kendala (fs kendala)



Fungsi kendala merupakan suatu pembatas terhadap berbagai variabel keputusan yang telah dibuat. 9. Fungsi Nonnegatif Fungsi nonnegatif menyatakan bahwa setiap variabel dalam program linear harus bernilai



positif.



2.8 Model Matematis dan Kendala dalam Linier Programming Model matematis pemrograman linier mempunyai struktur baku tertentu agar realitas dapat dijelaskan dengan baik oleh model. Struktur model matematis teknik pada pemrograman linier diawali oleh fungsi matematika yang mencerminkan tujuan model. Hanya terdapat dua fungsi tujuan dalam LP yaitu: Maksimumkan Z = f (X1, X2, ….., Xn) Minimumkan Z = f (X1, X2, ….., Xn) Notasi Z dipakai untuk menandai fungsi tujuan, dimana nilai Z tergantung pada nilai X1, X2, ….., Xn yang memiliki fungsi sebagai variabel bebas. Kendala yang ada pada konsep adalah fungsi matematika Linier Programming merupakan faktor yang mengendalikan nilai variabel keputusan. Peranan kendala secara matematis terlihat pada tanda kendala. Kendala berupa pembatas dimasukkan ke dalam fungsi matematika berupa pertidaksamaan dengan tanda ≤.



Kendala yang berupa syarat dimasukkan ke dalam fungsi matematika yang berupa pertidaksamaan dengan tanda ≥. Kendala yang berupa keharusan mengendalikan nilai pada ruas kiri agar nilainya sama dengan nilai pada ruas kanan menggunakan persamaan tanda = Kapasitas/nilai kendala ditaruh disebelah kanan tanda kendala sehingga biasanya disebut sebagai nilai ruas kanan (Right Hand Side / RHS). Pengalokasian dan Penggunaan model linear programming dalam hal ini adalah dengan mengoptimalkan sumberdaya yang tersedia sedemikian rupa sehingga akan maksimum atau alternatif minimum. Ada empat kondisi utama yang diperlukan dalam penerapannya: 1. Harus adanya sumber daya yang terbatas 2. Ada suatu fungsi tujuan seperti memaksimalkan atau meminimalkan 3. Harus ada linearitas 4. Harus ada keseragaman



Aprilyanti, S. (2019). OPTIMASI KEUNTUNGAN PRODUKSI PADA INDUSTRI KAYU PT . INDOPAL HARAPAN MURNI MENGGUNAKAN LINEAR. XIII(1), 1–8. Asmara, T., Rahmawati, M., Aprilla, M., Harahap, E., & Darmawan, D. (2018). Strategi Pembelajaran Pemrograman Linier Menggunakan Metode Grafik Dan Simpleks. Teknologi Pembelajaran, 3(1), 506–514. Hutabarat, J. (2022). Pengantar Teknik Industri. Media Nusa Creative (MNC Publishing). Livia, C. Y., & Oktiarso, T. (2017). Penjadwalan Untuk Memininimalkan Total Tardiness Dengan Metode Integer Linear Programming. Jurnal Teknik Industri, 18(2), 127–137. https://doi.org/10.22219/jtiumm.vol18.no2.127-137 Meflinda, A., & Mahyarni, M. (2011). Operations Research (Riset Operasi): Vol. I (pp. 1–114). UR PRESS pekanbaru. Peternakan, D. I., & Rimba, M. (2022). No Title. Prasojo, Bayu Hari, R. E. F. (2018). Riset Dan Operasi. UMSIDA Press. Sari, F. (2018). Metode dalam pengambilan keputusan. Deepublish. Sugiyono. (2019). Metode penelitian Kuantitatif,Kualitatif dan R&D (2nd ed.). Alfabeta Bandung.