BAB 1 PENDAHULUAN
1.1. Latar Belakang Optimasi (Optimization) adalah aktivitas untuk mendapatkan hasil terbaik di dalam suatu keadaan yang diberikan. Tujuan akhir dari semua aktivitas tersebut adalah meminimumkan usaha (effort) atau memaksimumkan manfaat (benefit) yang diinginkan. Karena usaha yang diperlukan atau manfaat yang diinginkan dapat dinyatakan sebagai fungsi dari variabel keputusan, maka optimasi dapat didefinisikan sebagai proses untuk menemukan kondisi yang memberikan nilai minimum atau maksimum dari sebuah fungsi. Kondisi tersebut akan dimodelkan dalam fungsi tujuan, dimana fungsi tujuan itu dapat berupa fungsi linier dan fungsi non linier (Parwadi Moengin, 2011). Secara matematis fungsi tujuan dapat dinyatakan sebagai berikut. Maksimum π (π) Atau Minimum π (π) Program linier merupakan salah satu teknik riset operasi yang mampu menyelesaikan masalah optimasi dimana fungsi tujuan dan kendalanya adalah fungsi linier. Model matematika pemrograman linier dapat ditulis dalam bentuk formulasi umum sebagai berikut: Masalah Maksimasi. Maksimum:
π(π) = πΆ1 π1 + πΆ2 π2 + β― + πΆπ ππ
(1.1)
dengan kendala: ππ1 π₯1 + ππ2 π₯2 + β― + πππ π₯π β€ ππ
Universitas Sumatera Utara
π₯1 , π₯2 , β¦ , π₯π β₯ 0 Masalah Minimasi. Minimum:
π(π) = πΆ1 π1 + πΆ2 π2 + β― + πΆπ ππ
(1.2)
dengan kendala: ππ1 π₯1 + ππ2 π₯2 + β― + πππ π₯π β₯ ππ π₯1 , π₯2 , β¦ , π₯π β₯ 0 Keterangan: πΆπ
= Koefisien fungsi tujuan
πππ
= Koefisien fungsi kendala
ππ
= Nilai fungsi kendala Program nonlinier juga merupakan teknik riset operasi yang mampu
menyelesaikan masalah optimasi dimana fungsi tujuan dan kendalanya mempunyai bentuk fungsi nonlinier pada salah satu atau keduanya. Dalam menyelesaikan permasalahan nonlinier terdapat dua kondisi yaitu nonlinier tanpa kendala dan nonlinier dengan kendala. Program nonlinier berkendala mempunyai bentuk umum sebagai berikut: Maksimum/ Minimum π = π(π) dengan π₯π = {π₯1 , β¦ , π₯π } dengan kendala ππ (π) = 0
(1.3)
Keterangan: π(π) = Fungsi tujuan ππ (π) = Fungsi kendala
Universitas Sumatera Utara
3
Nilai π = 1, 2, 3, β¦ , π Nilai π = 1, 2, 3, β¦ , π Salah satu metode untuk menyelesaikan optimasi tanpa kendala adalah dengan menggunakan metode kalkulus differensial. Tetapi permasalahan optimasi dengan kendala belum tentu dapat diselesaikan dengan metode tersebut. Metode lain yang digunakan untuk menyelesaikan optimasi dengan kendala adalah dengan cara subsitusi. Dengan metode ini, salah satu variabel bebas, misalnya variabel π§, dari persamaan terkendala disubsitusikan pada fungsi tujuan yang akan dicari nilai ekstrimnya. Dengan metode ini, maka akan dihasilkan suatu fungsi dengan dua variabel bebas. Sebagai hasilnya, masalah ekstrim terkendala diselesaikan melalui penyelesaian ekstrim tanpa kendala fungsi dua variabel. Namun demikian, metode ini tidak selalu membawa hasil, bilamana batasan-batasannya tidak hanya melibatkan satu persamaan kendala. Disamping itu, masalah-masalah optimasi dengan kendala sering timbul dalam masalah-masalah nyata, dimana batasan-batasannya tidak hanya satu fungsi. Hal ini mengakibatkan tidak mudah untuk menyederhanakan masalah, sedemikian sehingga diperoleh satu fungsi saja dengan dua variabel bebas. Di samping itu, masalah yang sering timbul dengan metode subsitusi adalah tidak mudahnya menentukan titik kritisnya. Salah satu metode untuk mengatasi masalah optimasi dengan kendala adalah metode Lagrange. Metode ini dikembangkan didasarkan pada kenyataan bahwa optimasi dengan kendala, nilai ekstrimnya selalu terletak pada titik kritis. Metode Lagrange ini menyediakan suatu metode aljabar untuk menentukan titik kritis, sehingga masalah optimasi dengan kendala dapat diatasi. Metode pengali Lagrange (Multiplier Lagrange) dikemukakan oleh Joseph Louis Lagrange (1736-1813). Metode ini dapat digunakan untuk menangani permasalahan program nonlinier dimana fungsi tujuannya memiliki kendala. Untuk memecahkan masalah optimasi dengan menggunakan fungsi Lagrange dilakukan beberapa langkah sebagai berikut:
Universitas Sumatera Utara
4
Pertama, membentuk suatu fungsi Lagrange dimana dibentuk suatu fungsi πΏ βΆ βπ β βπ€ , yang didefinisikan dengan πΏ (π₯, π) = π(π₯) + βπ π=1 ππ ππ (π₯)
(1.4)
Keterangan: πΏ
= Fungsi Lagrange
π(π₯)
= Fungsi tujuan
ππ
= Fungsi kendala
ππ
= Variabel slack
Kedua, mencari semua solusi (π₯, π) dalam himpunan persamaan ππΏ (π₯, π) = 0, π π₯π
π = 1, 2, 3, β¦ , π
(1.5)
ππΏ (π₯, π) π π₯π
πβ₯0
(1.6)
π = 1, 2, 3, β¦ , π
(1.7)
dimana
ππ
β₯ 0,
ππΏ (π₯, π) = 0, π π₯π
Setiap solusi dari sistem persamaan ini disebut titik kritis dari L. Ketiga, menghitung nilai dari π pada setiap titik π₯ dalam himpunan {π₯|π‘πππππππ‘ π π πππππππππ βπππππ (π₯, π) β π}. Fungsi Lagrange bermanfaat dalam mentransformasi persoalan optimasi berkendala menjadi persoalan optimasi tanpa kendala. Kebanyakan persoalanpersoalan optimasi dengan kendala dapat diselesaikan setelah persoalan tersebut diubah menjadi persoalan optimasi tanpa kendala. Berdasarkan latar belakang di atas, pada penelitian ini penulis akan meneliti tentang bagaimana karakteristik fungsi pengali Lagrange dalam penyelesaikan
Universitas Sumatera Utara
5
permasalahan optimasi. Oleh karena itu penulis memilih judul βAnalisis Karakteristik Fungsi Lagrange Dalam Menyelesaikan Permasalahan Optimasi Berkendala β.
1.2. Perumusan Masalah Berdasarkan latar belakang di atas, maka permasalahan yang akan dibahas dalam penelitian
ini
adalah
bagaimana
karakteristik
fungsi
Lagrange
dalam
menyelesaikan permasalahan optimasi berkendala.
1.3. Batasan Masalah Adapun batasan dalam penelitian ini diantaranya adalah: 1.
Metode penyelesaian optimasi yang digunakan adalah metode Lagrange.
2. Karakteristik fungsi Lagrange dirujuk dari jurnal Lagrange Multiplier and their Application (Huijuan Li, 2008) dan dari jurnal Constrained Optimization Using Lagrange Multipliers (Henri P. Gavin and Jeffrey T. Scruggs, 2016).
1.4. Tinjauan Pustaka Sebagai sumber pendukung teori dalam penulisan ini, penulis mengambil beberapa pustaka yang memberikan kontribusi dalam penyelesaian skripsi ini. Metode Lagrange adalah metode yang paling penting dan berguna untuk optimasi berdasarkan kalkulus. Hal ini dapat digunakan untuk mengoptimalkan fungsi yang bergantung pada sejumlah variabel independen dan ketika kendala fungsional terlibat. Dengan demikian, dapat diterapkan untuk berbagai situasi praktis. Metode Lagrange pada dasarnya mengubah masalah sebelumnya untuk menemukan solusi minimum atau maksimum dari sistem persamaan aljabar, sehingga memberikan skema yang baik untuk menentukan optimal. Fungsi tujuan
Universitas Sumatera Utara
6
dan kendala digabungkan menjadi fungsi baru π, yang dikenal sebagai ekspresi Lagrange (Usman Efendi, 2012). Masalah optimasi dapat diselesaikan dengan berbagai metode, salah satunya adalah metode Lagrange. Metode ini dapat digunakan untuk mendapatkan solusi dari masalah optimasi. Dengan menggunakan metode Lagrange, nilai ekstrem dapat diperoleh, sehingga solusi optimal dapat dicari. Pada penelitian ini, pendapatan maksimum suatu perusahaan UD. Sari Madu dibatasi oleh beberapa kendala. Setelah fungsi tujuan dan fungsi kendala dimodelkan maka pendapatan maksimal dapat dicari. Sehingga pendapatan UD. Sari Madu dapat menjadi optimal. Dalam
pembentukan
portofolio,
seorang
investor
berusaha
memaksimumkan return yang diharapkan (expected return) dari investasi dengan tingkat resiko terendah. Fungsi lagrange digunakan untuk mengoptimalkan besarnya komposisi atau proporsi aset dalam portofolio berdasarkan maksimum mean return yang diberikan. (Di Asih I Maruddani, 2009). Mengoptimalkan portofolio saham dengan menggunakan metode pengali Lagrange dimana pada penelitian ini membahas pemecahan model portofolio investasi Markowitz untuk aset di pasar saham Bursa Efek Kolombia (Eduardo, 2013). Penerapan metode pengali Lagrange dalam bidang ekonomi dimana tujuan dari penelitian ini adalah menentukan nilai optimum suatu fungsi optimasi bersyarat dan menyelesaikan masalah optimasi bersyarat tersebut dengan menggunakan metode pengali Lagrange. Metode pengali Lagrange paling banyak dipakai dengan pertimbangan bahwa prinsip kerjanya sederhana dan mudah untuk dimengerti. Metode pengali Lagrange digunakan untuk memperoleh nilai maksimum atau minimum dari fungsi objektifnya dengan kendala berbentuk persamaan. Selain itu pengali Lagrange juga digunakan untuk menyelesaikan masalah optimasi dalam bentuk program nonlinier. Untuk menentukan nilai ekstrim fungsi berkendala tersebut digunakan metode pengali Lagrange, yaitu dengan cara membentuk sebuah fungsi baru yang merupakan penjumlahan dari fungsi yang hendak dioptimumkan ditambah hasil kali pengali Lagrange atau Ξ» dengan fungsi kendalanya (Rahmad Hidayat, 2015). Dalam
menjalankan
bisnisnya,
PT.
Petrokimia
Gresik
memiliki
dan
mengoperasikan pembangkit listrik tenaga gas dan pembangkit listrik tenaga uap. Untuk
Universitas Sumatera Utara
7
mencapai kondisi operasi yang optimal dan ekonomis maka PT. Petrokimia Gresik membagi daya pada setiap pembangkit listriknya. Untuk itu disimulasikan perhitungan ekonomis pembangkit listrik dengan metode lagrange multiplier yang iterasinya diselesaikan dengan metoda Newton-Raphson, dan karakteristik setiap pembangkit yang didapat diminimalisasi dengan metode lagrange multiplier dengan data yang diambil dari tiap pembangkit. Hubungan antara biaya bahan bakar terhadap daya aktif yang dihasilkan pembangkit dirumuskan oleh persamaan berikut: πΉπ (ππ ) = ππ ππ2 + ππ ππ + ππ
(1.8)
dimana: πΉπ (ππ )
= biaya operasi tiap unit pembangkit ($/h)
(ππ )
= daya keluaran tiap unit pembangkit (MW)
ππ , ππ , ππ = koefisien biaya operasi pembangkit π
= 1, 2, 3, β¦ , π (untuk π pembangkit)
Biaya bahan bakar dan pembangkit tenaga listrik dari suatu sistem tenaga listrik dengan memperhitungkan susut daya pada saluran transmisi dinyatakan seperti pada persamaan berikut: π
πΉπ = β πΉπ (ππ ) = πΉ1 (π1 ) + πΉ2 (π2 ) + πΉ3 (π3 ) + β― + πΉπ (ππ ) (1.9) π=1
Total
daya
yang
disuplai
oleh
π
pembangkit
ke
sistem
adalah
π
ππ = β πΉππ = ππ1 + ππ2 + ππ3 + β― + πππ
(1.10)
π=1
Fungsi biaya persamaan di atas akan diminimalkan dengan memperhatikan fungsi kendala operasi (Constraining), yaitu persamaan neraca daya. π
ππΏ + ππ· β β ππ = 0
(1.11)
π=1
Salah satu cara untuk menyelesaikan masalah optimasi adalah dengan Metode Pengali Lagrange. Sebuah fungsi baru π, dibentuk dengan menggabungkan fungsi biaya pembangkit dan persamaan kendala sistem, yaitu: ππΏ πππ
ππΉ
= πππ β π (1 β π
πππππ π ) πππ
=0
(1.12)
Universitas Sumatera Utara
8
Penelitian ini menggunakan software MATLAB 7.6.0 (R2008a) dengan membuat program simulasi perhitungan pembebanan ekonomis pada PLTU dan PLTG dengan menggunakan Metode Pengali Lagrange. Berdasarkan simulasi, pada permintaan beban rendah, PLTU membangkitkan daya yang lebih besar dari pada PLTU dengan batasan yang ada. Berdasarkan simulasi pada permintaan beban rendah 16 MW, PLTU membangkitkan daya sebesar 13,48 MW dan PLTG membangkitkan daya sebesar 3,05 MW. Biaya pembangkitan sebelum dilakukan optimasi memiliki biaya yang lebih mahal dari pada sesudah dilakukan optimasi. Berdasarkan simulasi dapat disimpulkan bahwa proses optimasi pembangkit dapat memenuhi permintaan beban pada suatu sistem dengan biaya operasi seminimal mungkin (Joko Susilo, Mochammad Facta, dan Susatyo Handoko, 2014). Salah satu metode untuk mengatasi masalah ekstrim terkendala adalah metode Lagrange. Metode ini dikembangkan didasarkan pada kenyataan bahwa ekstrim terbatas, nilai ekstrimnya selalu terletak pada titik kritis. Metode Lagrange ini menyediakan suatu metode aljabar untuk menentukan titik kritis, sehingga masalah ekstrim terkendala dengan metode ini dapat diatasi. Andaikan akan dicari nilai ekstrim relatif fungsi π(π₯, π¦, π§) dengan kendala π(π₯, π¦, π§) = 0. Langkah pertama metode Lagrange adalah membentuk fungsi baru dengan memasukkan variabel baru Ξ», yang disebut dengan faktor pengali Lagrange. Fungsi baru tersebut adalah, πΉ(π₯, π¦, π§, π) = π(π₯, π¦, π§) + ππ(π₯, π¦, π§)
(1.13)
Langkah kedua adalah menentukan titik kritis dari fungsi πΉ. Titik kritis diperoleh dengan cara menyelesaikan secara simulkan dari, πΉπ₯ (π₯, π¦, π§, π) = 0
(1.14)
πΉπ¦ (π₯, π¦, π§, π) = 0 πΉπ§ (π₯, π¦, π§, π) = 0 πΉπ (π₯, π¦, π§, π) = π(π₯, π¦, π§) = 0 Langkah ketiga adalah menentukan nilai ekstrim terkendala. Bilamana (π₯0 , π¦0 , π§0 , π0 ) adalah titik kritis dari πΉ(π₯, π¦, π§, π) maka (π₯0 , π¦0 , π§0 ) adalah juga merupakan titik kritis dari πΉ(π₯, π¦, π§, π) dengan kendala π(π₯, π¦, π§). Jadi nilai ektrim π(π₯, π¦, π§) dengan kendala π(π₯, π¦, π§) adalah π(π₯0 , π¦0 , π§0 ). Contoh:
Universitas Sumatera Utara
9
Tentukan nilai maksimum dan atau minimum dari, π(π₯, π¦, π§) = 4π₯ + 5π¦ + 4π§
(1.15)
pada elips yang merupakan perpotongan silinder lingkaran tegak,
(π₯ β 2)2 +
(π¦ β 4)2 = 100, dan bidang 2π₯ + 3π¦ = 4π§. Penyelesaian: Menentukan fungsi Lagrange. Dari persamaan fungsi kendala, diambil π(π₯, π¦, π§) = 100 β (π₯ β 2)2 β (π¦ β 4)2
(1.16)
β(π₯, π¦, π§) = 4π§ β 2π₯ β 3π¦ Selanjutnya bentuk fungsi pembantu Lagrange, πΉ(π₯, π¦, π§, π, π½) = π(π₯, π¦, π§) + ππ(π₯, π¦, π§) + π½β(π₯, π¦, π§)
(1.17)
= 4π₯ + 5π¦ + 4π§ + π(100 β (π₯ β 2)2 β (π¦ β 4)2 )
+ π½(4π§
β 2π₯ β 3π¦) dimana Ξ» dan π½ adalah faktor pengali Lagrange. Menentukan titik kritis dengan menurunkan secara parsial fungsi πΉ(π₯, π¦, π§, π, π½) maka dihasilkan, πΉπ₯ (π₯, π¦, π§, π, π½) = 4 β 2π(π₯ β 2) β 2π½ πΉπ¦ (π₯, π¦, π§, π, π½) = 5 β 2π(π¦ β 4) β 3π½ πΉπ§ (π₯, π¦, π§, π, π½) = 4 + 4π½
(1.18)
πΉπ (π₯, π¦, π§, π, π½) = 100 β (π₯ β 2)2 β (π¦ β 4)2 πΉπ½ (π₯, π¦, π§, π, π½) = 4π§ β 2π₯ β 3π¦ Dengan menetapkan πΉπ₯ , πΉπ¦ , πΉπ§ , πΉπ dan πΉπ½ sama dengan nol dihasilkan, 4 β 2π(π₯ β 2) β 2π½ = 0 didapatkan π₯ β 2 =
4β2π½ 2π
5 β 2π(π¦ β 4) β 3π½ = 0 didapatkan π¦ β 4 =
5β3π½ 2π
4 + 4π½ = 0 didapatkan π½ = β1 100 β (π₯ β 2)2 β (π¦ β 4)2 = 0 atau (π₯ β 2)2 β (π¦ β 4)2 = 100 4π§ β 2π₯ β 3π¦ = 0 atau 4π§ = 2π₯ β 3π¦
Dengan mensubsitusikan π½ = β1 pada πΉπ₯ = 0 dan πΉπ¦ = 0 dihasilkan, 4 β 2(β1) 3 = 2π π 5 β 3(β1) 4 π¦β4= = 2π π π₯β2=
Universitas Sumatera Utara
10
3 π
4 π
Selanjutnya subsitusikanlah, π₯ β 2 = dan π¦ β 4 = pada πΉπ = 0, maka dihasilkan, 3 4 ( )π + ( )π = 100 π π 9 16 + = 100 ππ ππ 25 = 100 ππ 1
1
1
Karena π β 0 maka dihasilkan π2 = 4 atau π = Β± 2 . Sehingga untuk π = 2, dihasilkan π₯β2= π¦β4=
π§=
3 1 2
( ) 4 1 2
( )
diperoleh π₯ = 8 diperoleh π¦ = 8
1 [2(8) + 3(12) = 13 4 1
Sedangkan untuk π = β 2, dihasilkan π₯β2= π¦β4= π§=
3 1 2
(β ) 4 1 2
(β )
diperoleh π₯ = β4 diperoleh π¦ = β4
1 [2(β4) + 3(β4)] = β5 4 1 2
1 2
Jadi titik kritis πΉ adalah (8, 12, 13, , β1) dan (β4, β4, β5, β , β1).
Menentukan nilai ekstrim. Karena titik kritis fungsi πΉ(π₯, π¦, π§, π, π½) adalah 1
1
(8, 12, 13, 2 , β1) dan (β4, β4, β5, β 2 , β1) maka titik kritis fungsi π(π₯, π¦, π§) adalah (8, 12, 13)
dan
(β4, β4, β5).
Jadi
nilai
ekstrim
π(π₯, π¦, π§) = 4π₯ + 5π¦ + 4π§ dengan kendala (π₯ β 2)2 + (π¦ β 4)2 = 100, dan 2π₯ + 3π¦ = 4π§ adalah (1) π(8, 12, 13) = 4(8) + 5(12) + 4(13) = 144, merupakan nilai maksimum (2) π(β4, β4, β5) = 4(β4) + 5(β4) + 4(β5) = β56, merupakan nilai minimum
(Prayudi, 2009).
Universitas Sumatera Utara
11
1.5. Tujuan Penelitian Tujuan penelitian ini adalah untuk menganalisis bagaimana karakteristik fungsi Lagrange dalam menyelesaikan permasalahan optimasi berkendala.
1.6. Kontribusi Penelitian Manfaat dari penelitian ini adalah sebagai berikut: 1. Dapat dijadikan sebagai bahan pembelajaran bagi pembaca. 2. Dapat digunakan sebagai tambahan informasi dan pertimbangan terlebih bagi mahasiswa yang hendak melakukan penelitian serupa.
1.7. Metodologi Penelitian Metode penelitian yang digunakan adalah dengan menggunakan metode studi literatur yang bersifat penjelasan dan uraian. Dalam penelitian ini diuraikan tentang analisis karakteristik dari fungsi Lagrange yang dinyatakan dalam bentuk pengali Lagrange untuk menyelesaikan permasalahan optimasi berkendala.
Universitas Sumatera Utara