Metode Pengali Lagrange pada Optimasi Bersyarat dan Contoh Kode Solver

Artikel ini menceritakan penggunaan metode pengali lagrange agar dapat dipahami dengan lebih mudah.

Pembuka

Ada banyak cara dalam memahami sebuah permasalahan. Salah satunya adalah dengan memodelkan permasalahan ke dalam persamaan matematis. Sebagai contoh, bagian perencanaan di sebuah perusahaan memodelkan pendapatan (R) dari sebuah lini bisnis berdasarkan berapa ton baja yang diproses (s) dan berapa jam pekerja beraktivitas (h). Pada persamaan tersebut, C adalah konstanta.

Secara visual, gambar di bawah mengilustrasikan persamaan tersebut ketika C=1. Dari gambar tersebut, terlihat bahwa pendapatan perusahaan semakin meningkat ketika jam kerja dan jumlah baja yang diproses bertambah. Pertambahan jam kerja memberikan efek yang lebih curam kepada pendapatan dibandingkan jumlah baja yang diproses. Artinya, perusahaan hanya perlu membeli baja sebanyak mungkin sebagai modal kerja dan merekrut banyak orang sebagai pekerja.

Walaupun demikian, perusahaan memiliki modal uang yang terbatas. Perusahaan hanya memiliki modal uang sebesar 200 juta rupiah. Sementara itu, perusahaan harus menggaji setiap karyawan per-jam sebesar 200 ribu rupiah. Perusahaan juga harus membeli baja dengan harga 1.7 juta setiap satu ton. Artinya pemilihan banyaknya baja dan lamanya jam karyawan akan mempengaruhi pendapatan perusahaan. Kali ini, kami menggunakan konstanta C = 2 10⁶. Permasalahan tersebut dikenal sebagai optimasi bersyarat.

Optimasi bersyarat adalah sebuah permasalahan yang bertujuan untuk memaksimalkan atau meminimalkan sebuah fungsi objektif dengan memperhatikan batasan atau syarat yang diberikan. Dalam contoh sebelumnya, fungsi yang akan dimaksimalkan adalah fungsi pendapatan perusahaan. Sedangkan modal uang perusahaan adalah batasan yang wajib dipenuhi. Model matematis optimasi bersyarat pada contoh tersebut dapat diekspresikan pada pernyataan di bawah.

Interpretasi Visual

Ekspresi model optimasi bersyarat pada contoh di atas, dapat divisualisasikan pada diagram 3D. Warna hijau menggambarkan fungsi pendapatan (R). Warna merah menggambarkan syaratnya. Data model matematis tersebut dinormalisasi agar dapat divisualisasikan. Dari gambar tersebut, kita dapat menganalisa di mana titik optimal berada. Titk optimal pada contoh ini didefinisikan sebagai pendapatan paling maksimal yang mematuhi syarat modal yang dimiliki. Artinya, posisi titik optimal tersebut berada pada garis yang menghubungkan titik-titik di mana visual berwarna hijau bertemu dengan visual berwarna merah. Selanjutnya titik optimal adalah titik dengan nilai visual warna hijau tertinggi yang berada pada garis tersebut.

Jenis visual lain yang dapat digunakan untuk menemukan titik optimal tersebut adalah diagram kontur. Pada diagram kontur, titik pertemuan antara garis kontur fungsi pendapatan berwarna hijau dan fungsi pendapatan berwarna merah adalah titik optimal.

Penjelasan lebih detil tentang cara membaca diagram 3D, diagram kontur, dan vektor gradien dapat ditemukan pada artikel ini.

Metode Pengali Lagrange

Salah satu metode untuk mensolusikan permasalahan optimasi fungsi bersyarat adalah menggunakan Metode Pengali Lagrange. Metode pengali lagrange memanfaatkan sebuah fenomena yang menunjukkan bahwa vektor gradien fungsi hijau dan merah berhimpitan namun berbeda amplitudo. Artinya kedua vektor gradien memiliki arah yang sama namun berbeda nilai.

Fenomena tersebut mengijinkan kita untuk menformulasikan hubungan dari kedua vektor gradien tersebut. Matematika dasar mengajarkan bahwa gradien atau kemiringan adalah turunan pertama dari sebuah fungsi. Dalam kasus ini, kita menggunakan turunan parsial, karena bentuk gradiennya adalah vektor. Fungsi pendapatan berwarna hijau kita namakan fungsi f(h,s) dan fungsi syarat berwarna merah kita namakan fungsi g(h,s). Dengan demikian, maka pernyataan di bawah menjelaskan hubungan kedua vektor gradien. Rasio dari f(h,s) dan g(h,s) adalah pengali lagrange yang disimbolkan oleh λ.

Oleh karena itu, optimasi bersyarat untuk contoh model pendapatan perusahaan dapat dituliskan sebagai berikut.

Persamaan matriks tersebut juga dapat dituliskan kembali pada pernyataan di bawah. Terdapat tiga persamaan yang dapat kita gunakan untuk menemukan h dan s. Kita juga dapat menemukan λ. Persamaan di bawah adalah cara penulisan lain dari persamaan di atas yang dinormalisasi atau dibagi dengan 10 ribu agar lebih ringkas.

Kita solusikan persamaan tersebut. Kita mulai manipulasi persamaan 1 dan 2 agar kita mendapatkan fungsi untuk menghitung s yang bergantung pada h.

Selanjutnya, kita masukkan persamaan s ke persamaan 3. Oleh karena itu kita mendapatkan nilai s.

Sekarang, kita cari nilai h dengan memasukkan nilai s yang telah diketahui ke persamaan 3.

Saat ini nilai s dan h optimal telah kita ketahui. Kita cari nilai λ dengan menggunakan nilai h dan s.

Dari penyelesaian persamaan tersebut, dapat kita rangkum titik optimalnya sebagai berikut.

Selanjutnya kita dapat memaksukkan titik optimal yang dibulatkan ke bawah pada persamaan pendapatan (R). Oleh karena itu kita ketahui pendapatan maksimal yang diraih dengan modal kerja 200 juta rupiah adalah Rp 517.250.517. Rasio modal dengan pendapatan adalah 2.586 dan profit 158%.

Makna Pengali Lagrange

Solusi yang telah kita kerjakan di atas menunjukkan lokasi titik optimal dan nilai pengali lagrange λ. Nilai pengali lagrange λ = 2.593 memiliki makna setiap penambahan modal 1 poin akan memberikan penambahan keuntungan maksimal sebesar 2.593. Nilai ini berbeda sedikit dengan rasio pendapatan dan modal yang kita hitung yaitu 2.586. Hal ini diakibatkan oleh pembulatan ke bawah yang kita lakukan.

Contoh Kode

Pada bagian sebelumnya, kita telah menemukan titik optimal pada permasalahan optimasi bersyarat secara manual dengan metode lagrange. Selanjutnya, kita akan menggunaan komputer untuk mencari solusi permasalahan tersebut. Salah satu caranya adalah dengan menggunakan library scipy yang ada di bahasa pemrograman python.

Berikut adalah baris kode dengan fungsi objektif dan fungsi batasan yang sama dengan contoh soal sebelumnya. Fungsi objektif kita jadikan negatif, sebagai tanda bahwa kita mencari nilai maksimal, sebagai lawan dari minimal. Sementara itu, pada dokumentasi scipy hanya menyertakan fungsi optimasi minimize (minimalisasi).

import numpy as np
from scipy.optimize import minimize

def objective_eq(X):
    x, y = X
    return -(200 * x**(2/3) *  y**(1/3))

def constraint_eq(X):
    x, y = X
    return 20 * x + 170 * y - 20000

sol = minimize(objective_eq, [0., 0.], method="SLSQP", constraints={'type': 'eq', 'fun': constraint_eq})
print(sol)

Di bawah ini adalah hasil keluaran layar konsol. Nilai x yang ditemukan hampir sama yaitu 666 dan 39.

Referensi

• Khan Academy