Cara Menggunakan Metode Lagrange/Multiplier Lagrange untuk Maksimal/Minimal Fungsi Objektif

3,063 Views

Dalam matematika dan optimasi, Lagrangian sering digunakan untuk menyelesaikan masalah optimasi dengan pembatasan/constraints, di mana kita ingin memaksimalkan atau meminimalkan suatu fungsi objektif, namun dengan kondisi atau batasan tertentu yang harus dipenuhi. Pendekatan ini dikenal sebagai Metode Lagrange/Metode Multiplier Lagrange

Masalah Optimasi dengan Pembatasan

Contents

1 Masalah Optimasi dengan Pembatasan
- 1.1 Konsep Lagrangian untuk Masalah Optimasi
- 1.2 Prinsip Dasar
2 Contoh Kasus
3 Contoh Kasus: Optimasi Produksi

Misalkan kita memiliki masalah optimasi berikut:

Fungsi objektif: $f(x_1, x_2, \dots, x_n)$ yang ingin kita maksimalkan atau minimalkan.
Pembatasan: $g_i(x_1, x_2, \dots, x_n) = 0$ untuk $i = 1, 2, \dots, m$ , yang membatasi solusi pada subruang tertentu.

Tujuan kita adalah mencari nilai $x_1, x_2, \dots, x_n$ yang memaksimalkan atau meminimalkan $f(x_1, x_2, \dots, x_n)$ , namun dengan syarat bahwa pembatasan $g_i(x_1, x_2, \dots, x_n) = 0$ harus terpenuhi.

Konsep Lagrangian untuk Masalah Optimasi

Untuk menyelesaikan masalah ini, kita memperkenalkan fungsi Lagrangian, yang merupakan kombinasi dari fungsi objektif dan pembatasan yang ada. Fungsi Lagrangian $\mathcal{L}$ untuk masalah optimasi ini dapat dituliskan sebagai:

$\mathcal{L}(x_1, x_2, \dots, x_n, \lambda_1, \lambda_2, \dots, \lambda_m) = f(x_1, x_2, \dots, x_n) - \sum_{i=1}^m \lambda_i g_i(x_1, x_2, \dots, x_n)$

di mana:

$f(x_1, x_2, \dots, x_n)$ adalah fungsi objektif yang ingin kita optimalkan (maksimalkan atau minimalkan),
$g_i(x_1, x_2, \dots, x_n) = 0$ adalah pembatasan yang harus dipenuhi,
$\lambda_i$ adalah multiplier Lagrange yang merupakan parameter tambahan yang digunakan untuk menggabungkan
pembatasan dengan fungsi objektif.

Prinsip Dasar

Inti dari metode Lagrange adalah mencari titik-titik stasioner dari fungsi Lagrangian ini, yaitu dengan cara mengambil turunan parsial dari $\mathcal{L}$ terhadap $x_1, x_2, \dots, x_n$ dan $\lambda_1, \lambda_2, \dots, \lambda_m$ , lalu menyamakan hasilnya dengan nol.

Secara matematis, kita memperoleh sistem persamaan berikut:
$\frac{\partial \mathcal{L}}{\partial x_j} = 0 \quad \text{untuk} \quad j = 1, 2, \dots, n$
$\frac{\partial \mathcal{L}}{\partial \lambda_i} = 0 \quad \text{untuk} \quad i = 1, 2, \dots, m$

Persamaan pertama mengindikasikan bahwa kita mencari titik-titik ekstremum fungsi objektif $f(x_1, x_2, \dots, x_n)$ dengan mempertimbangkan pembatasan yang ada.

Contoh Kasus

Misalkan kita ingin meminimalkan fungsi objektif berikut:

$f(x_1,x_2) = x_1^2+x_2^2$

dengan kendala

$x_1+x_2=1$

Berikut Cara Menggunakan Metode Lagrange/Metode Multiplier Lagrange untuk Maksimal/Minimal Fungsi Objektif

Solusi bebas

Jika tidak ada kendala, fungsi $f(x_1,x_2)=x_1^2+x_2^2$ adalah fungsi kuadratik yang mencapai minimum global di

$x_1=0, x_2=0$

Namun, karena ada kendala $x_1+x_2=1$ , solusi harus berada di garis tersebut, untuk itu, perlu digunakan metode Lagrangian.

Menyusun Fungsi Lagrangian

Fungsi Lagrangian dirumuskan dengan menambahkan kendala $x_1+x_2-1=0$
kedalam fungsi objektif, melalui multiplier Lagrange $\lambda$ :

$L(x_1,x_2,\lambda)= x_1^2+x_2^2+\lambda(x_1+x_2-1)$

Turunan Parsial

Untuk menemukan solusi optimal, kita perlu melakukan perhitungan turunan parsial $L$ terhadap $x_1,x_2$ dan $\lambda$ setara sama dengan nol

Turunan terhadap $x_1$

(1) $\begin{equation*} \begin{split} \frac{\delta L}{\delta x_1} & = x_1^2+x_2^2+\lambda(x_1+x_2-1)\\ \frac{\delta L}{\delta x_1} &= x_1^2+x_2^2+\lambda x_1+\lambda x_2-\lambda1\\ \frac{\delta L}{\delta x_1} &=2 x_1+\lambda \\ \end{split} \end{equation*}$

sehingga

$\lambda = -2x_1$

Turunan terhadap $x_2$

(2) $\begin{equation*} \begin{split} \frac{\delta L}{\delta x_2} & = x_1^2+x_2^2+\lambda(x_1+x_2-1)\\ \frac{\delta L}{\delta x_2} &= x_1^2+x_2^2+\lambda x_1+\lambda x_2-\lambda1\\ \frac{\delta L}{\delta x_2} &=2 x_2+\lambda \\ \end{split} \end{equation*}$

sehingga

$\lambda = -2x_2$

Turunan terhadap $\lambda$

$\frac{\delta L}{\delta \lambda} = x_1+x_2-1=0$

sehingga

$x_1+x_2=1$

Subtitusi

Dari $\lambda = -2x_1$ dan $\lambda = -2x_2$ , kita dapatkan:

$-2x_1=-2x_2 \rightarrow x_1 = x_2$

Subtitusi $x_1=x_2$ ke kendala $x_1+x_2=1$

$x_1+x_1=1 \rightarrow 2x_1=1 \rightarrow x_1=\frac{1}{2}$

karena $x_1=x_2$ , maka

$x_2 =\frac{1}{2}$

Solusi akhir

$x_1 = \frac{1}{2}$ dan $x_2=\frac{1}{2}$
Nilai minimum fungsi objektif

$f(x_1,x_2) = x_1^2+x_2^2=\frac{1}{2}^2+\frac{1}{2}^2 = \frac{1}{2}$

Kesimpulan

Fungsi Lagrangian memungkinkan kita menyelesaikan masalah optimasi dengan kendala, tanpa harus menyelesaikan kendala secara eksplisit terlebih dahulu.
Dalam contoh ini, solusi optimal ditemukan di
$x_1=\frac{1}{2}$ dan $x_2=\frac{1}{2}$ , yang juga memenuhi kendala $x_1+x_2=1$

Berikut adalah contoh kasus lain untuk menunjukkan bagaimana Lagrangian digunakan dalam optimasi dengan kendala.

—

Contoh Kasus: Optimasi Produksi

Problem:
Sebuah perusahaan ingin memaksimalkan keuntungan dengan memproduksi dua produk, $x_1$ dan $x_2$ . Keuntungan dari masing-masing produk diberikan oleh fungsi:

$f(x_1, x_2) = 3x_1 + 5x_2.$

Namun, produksi dibatasi oleh:
1. Keterbatasan waktu kerja:

$x_1 + 2x_2 \leq 8,$

di mana $x_1$ dan $x_2$ membutuhkan sumber daya produksi tertentu.

2. Kapasitas bahan baku:

$2x_1 + x_2 \leq 10.$

Selain itu, jumlah produksi tidak bisa negatif:

$x_1 \geq 0, \quad x_2 \geq 0.$

Menyusun Fungsi Lagrangian

Kita ingin memaksimalkan fungsi objektif $f(x_1, x_2) = 3x_1 + 5x_2$ dengan kendala. Untuk menyusun Lagrangian, kita perkenalkan multiplier Lagrange ( $\lambda_1, \lambda_2$ ) untuk kendala $x_1 + 2x_2 \leq 8$ dan $2x_1 + x_2 \leq 10$ .