Setelah kita mempelajari dua metode yaitu "metode uji titik pojok" dan "metode garis selidik" untuk menyelesaikan masalah program linear, ada satu metode lagi yang jarang dibahas di sekolah yaitu metode gradien. Pada artikel ini kita akan khusus membahas Program Linear : Nilai Optimum dengan Metode Gradien. Agar lebih mudah memahaminya, silahkan baca materi yang berkaitan dengan "gradien suatu persamaan garis lurus".
Catatan :
Metode gradien biasanya bisa diaplikasikan pada soal cerita.
Contoh soal metode gradien :
1). Tentukan nilai minimum fungsi tujuan $ z = 4x + 6y \, $ dengan
kendala : $ 5x + 10y \geq 20 , \, 3x + y \geq 5, \, x \geq 0, \, y \geq 0 $.
Penyelesaian :
*). Menentukan gradien masing-masing :
fungsi tujuan : $ z = 4x + 6y \rightarrow m_z = \frac{-x}{y} = \frac{-4}{6} = -\frac{2}{3} = - 0,67 $
Kendala I : $ 5x + 10y \geq 20 \rightarrow m_1 = \frac{-5}{10} = -0,5 $
Kendala II : $ 3x + y \geq 5 \rightarrow m_2 = \frac{-3}{1} = -3 $
Karenan gradien kendala dan fungsi tujuannya semuanya negatif, maka metode gradien bisa kita gunakan.
Kita peroleh letak $ m_z \, $ adalah : $ m_2 \leq m_z \leq m_1 $.
Artinya fungsi tutujan minimum pada titik perpotongan kedua garis karena gradien fungsi tujuannya ada diantara gradien kedua kendalanya.
*). Menentukan perpotongan kedua garis kendala :
$ \begin{array}{c|c|cc} 5x + 10y = 20 & \times 1 & 5x + 10y = 20 & \\ 3x + y = 5 & \times 10 & 30x + 10y = 50 & - \\ \hline & & -25x = -30 & \\ & & x = \frac{6}{5} & \end{array} $
Substitusi $ x = \frac{6}{5} \, $ ke persamaan $ 3x + y = 5 $
$ 3x + y = 5 \rightarrow 3x \times \frac{6}{5} + y = 5 \rightarrow y = \frac{7}{5} $.
Sehingga titik perpotongannya adalah ($\frac{6}{5},\frac{7}{5}$).
*). Menentukan nilai minimumnya di titik ($\frac{6}{5},\frac{7}{5}$)
$ z = 4x + 6y = 4 \times \frac{6}{5} + 6 \times \frac{7}{5} = 13,2 $.
Jadi, nilai minimum fungsi $ z = 4x + 6y \, $ adalah 13,2.
2). Tentukan nilai minimum fungsi tujuan $ z = x + 5y \, $ dengan
kendala : $ 5x + 10y \geq 20 , \, 3x + y \geq 5, \, x \geq 0, \, y \geq 0 $.
Penyelesaian :
*). Menentukan gradien masing-masing :
fungsi tujuan : $ z = x + 5y \rightarrow m_z = \frac{-x}{y} = \frac{-1}{5} = - 0,2 $
Kendala I : $ 5x + 10y \geq 20 \rightarrow m_1 = \frac{-5}{10} = -0,5 $
Kendala II : $ 3x + y \geq 5 \rightarrow m_2 = \frac{-3}{1} = -3 $
Karenan gradien kendala dan fungsi tujuannya semuanya negatif, maka metode gradien bisa kita gunakan.
Kita peroleh letak $ m_z \, $ adalah : $ m_2 \leq m_1 \leq m_z $.
Artinya fungsi tutujan minimum pada titik pojok garis pertama karena gradiennya lebih dekat dengan gradien garis pertama.
*). Menentukan titik pojok garis I :
$ 5x + 10y = 20 \rightarrow (0,2), (4,0) $.
Kita cek titik (0,2) dan (4,0) ke kendala yang lainya :
$ (0,2) \rightarrow 3x + y \geq 5 \rightarrow 3.0 + 2 \geq 5 \rightarrow 2 \geq 5 \, $ (salah).
titik (0,2) bukan titik pojok.
$ (4,0) \rightarrow 3x + y \geq 5 \rightarrow 3.4 + 0 \geq 5 \rightarrow 12 \geq 5 \, $ (benar).
titik (4,0) adalah titik pojok.
Sehingga fungsi tujuan $ z = x + 5y \, $ minimum di titik pojok (4,0).
*). Menentukan nilai minimumnya di titik (4,0)
$ z = x + 5y = 4 + 5 \times 0 = 4 $.
Jadi, nilai minimum fungsi $ z = x + 5y \, $ adalah 4.
3). Tentukan nilai minimum fungsi tujuan $ z = 20x + 5y \, $ dengan
kendala : $ 5x + 10y \geq 20 , \, 3x + y \geq 5, \, x \geq 0, \, y \geq 0 $.
Penyelesaian :
*). Menentukan gradien masing-masing :
fungsi tujuan : $ z = 20x + 5y \rightarrow m_z = \frac{-x}{y} = \frac{-20}{5} = - 4 $
Kendala I : $ 5x + 10y \geq 20 \rightarrow m_1 = \frac{-5}{10} = -0,5 $
Kendala II : $ 3x + y \geq 5 \rightarrow m_2 = \frac{-3}{1} = -3 $
Karenan gradien kendala dan fungsi tujuannya semuanya negatif, maka metode gradien bisa kita gunakan.
Kita peroleh letak $ m_z \, $ adalah : $ m_z \leq m_2 \leq m_1 $.
Artinya fungsi tutujan minimum pada titik pojok garis kedua karena gradiennya lebih dekat dengan gradien garis kedua.
*). Menentukan titik pojok garis II :
$ 3x + y = 5 \rightarrow (0,5), (\frac{5}{3},0) $.
Kita cek titik (0,5) dan ($\frac{5}{3}$,0) ke kendala yang lainya :
$ (0,5) \rightarrow 5x + 10y \geq 20 \rightarrow 5.0 + 10.5 \geq 20 \rightarrow 50 \geq 20 \, $ (benar).
titik (0,5) adalah titik pojok.
$ (\frac{5}{3},0) \rightarrow 5x + 10y \geq 20 \rightarrow 5.\frac{5}{3} + 10.0 \geq 20 \rightarrow \frac{25}{3} \geq 20 \, $ (salah).
titik ($\frac{5}{3}$,0) bukan titik pojok.
Sehingga fungsi tujuan $ z = 20x + 5y \, $ minimum di titik pojok (0,5).
*). Menentukan nilai minimumnya di titik (0,5)
$ z = 20x + 5y = 20. \times 0 + 5 \times 5 = 25 $.
Jadi, nilai minimum fungsi $ z = 20x + 5y \, $ adalah 25.
Catatan :
*). Sebenarnya soal nomor 1 sampai nomor 3 memiliki kendala yang sama hanya fungsi tujuannya yang dibedakan agar kita bisa menyelesaikan soal dengan berbagai variasi yang ada terutama cara menentukan titik pojoknya dengan tanpa harus menggambar dulu grafik dan DHPnya.
4). Tentukan nilai maksimum fungsi tujuan $ z = 20x + 10y \, $ dengan
kendala : $ x + 2y \leq 4 , \, 5x + 3y \leq 15, \, x \geq 0, \, y \geq 0 $.
Penyelesaian :
*). Menentukan gradien masing-masing :
fungsi tujuan : $ z = 20x + 10y \rightarrow m_z = \frac{-x}{y} = \frac{-20}{10} = - 2 $
Kendala I : $ x + 2y \leq 4 \rightarrow m_1 = \frac{-1}{2} = -0,5 $
Kendala II : $ 5x + 3y \leq 15 \rightarrow m_2 = \frac{-5}{3} = -1,67 $
Karenan gradien kendala dan fungsi tujuannya semuanya negatif, maka metode gradien bisa kita gunakan.
Kita peroleh letak $ m_z \, $ adalah : $ m_z \leq m_2 \leq m_1 $.
Artinya fungsi tutujan maksimum pada titik pojok garis kedua karena gradiennya lebih dekat dengan gradien garis kedua.
*). Menentukan titik pojok garis II :
$ 5x + 3y \leq 15 \rightarrow (0,5), (3,0) $.
Kita cek titik (0,5) dan (3,0) ke kendala yang lainya :
$ (0,5) \rightarrow x + 2y \leq 4 \rightarrow 0 + 2.5 \leq 4 \rightarrow 10 \leq 4 \, $ (salah).
titik (0,5) bukan titik pojok.
$ (3,0) \rightarrow x + 2y \leq 4 \rightarrow 3 + 2.0 \leq 4 \rightarrow 3 \leq 4 \, $ (benar).
titik (3,0) adalah titik pojok.
Sehingga fungsi tujuan $ z = 20x + 10y \, $ maksimum di titik pojok (3,0).
*). Menentukan nilai maksimumnya di titik (3,0)
$ z = 20x + 10y = 20 \times 3 + 10 \times 0 = 60 $.
Jadi, nilai maksimum fungsi $ z = 20x + 10y \, $ adalah 60.
5). Agar fungsi tujuan $ z = ax + 4y \, $ minimum pada perpotongan kedua
kendala : $ 5x + 2y \geq 10 , \, 3x + 4y \geq 12 , \, x \geq 0, \, y \geq 0 $,
Tentukan rentang nilai $ a $?
Penyelesaian :
*). Menentukan gradien masing-masing :
fungsi tujuan : $ z = ax + 4y \rightarrow m_z = \frac{-x}{y} = \frac{-a}{4} $
Kendala I : $ 5x + 2y \geq 10 \rightarrow m_1 = \frac{-5}{2} $
Kendala II : $ 3x + 4y \geq 12 \rightarrow m_2 = \frac{-3}{4} $
*). Agar penyelesaiannya ada di perpotongan kedua kendala, haruslah gradien fungsi tujuannya ada di antara gradien fungsi kendalanya.
$ \begin{align} m_1 \leq & m_z \leq m_2 \\ \frac{-5}{2} \leq & \frac{-a}{4} \leq \frac{-3}{4} \, \, \, \, \text{(kali -4, tanda dibalik)} \\ \frac{-5}{2} \times (-4) \geq & \frac{-a}{4} \times (-4) \geq \frac{-3}{4} \times (-4) \\ 10 \geq & a \geq 3 \end{align} $
Jadi, rentang nilai $ a \, $ adalah $ \, 10 \geq a \geq 3 \, $ atau $ 3 \leq a \leq 10 $ .
Catatan :
Untuk soal nomor (5), jika ada kata solusinya "hanya" di perpotongan kedua kendala, maka yang dipakai adalah $ m_1 < m_z < m_2 $.
Nilai Optimum dengan Metode Gradien
Metode gradien adalah suatu metode yang secara langsung menggunakan gradien. Dengan metode gradien, akan langsung dapat kita tentukan titik pojok yang menyebabkan suatu fungsi tujuan memeiliki nilai optimum (maksimum atau minimum).
Misalkan ada fungsi tujuan $ z = f(x,y) = ax + by \, $ dengan gradien $ m_f$,
dan terdapat dua kendala yaitu kendala I dengan gradien $ m_1 \, $ dan kendala II dengan gradien $ m_2, \, $ maka ada tiga kemungkinan yang terjadi, yaitu :
i). $ m_f \leq m_1 \leq m_2 \, $ artinya nilai optimum diperoleh pada titik pojok garis pertama.
ii). $ m_1 \leq m_f \leq m_2 \, $ artinya nilai optimum diperoleh pada perpotongan kedua garis.
iii). $ m_1 \leq m_2 \leq m_f \, $ artinya nilai optimum diperoleh pada titik pojok garis kedua.
Syarat yang harus dipenuhi :
*). Semua gradien fungsi tujuan dan kendalanya harus negatif.
*). Tanda ketaksamaannya harus sama semua ($\leq \, $ semua atau $ \, \geq \, $ semua).
*). Banyaknya kendala bisa lebih dari 2.
Misalkan ada fungsi tujuan $ z = f(x,y) = ax + by \, $ dengan gradien $ m_f$,
dan terdapat dua kendala yaitu kendala I dengan gradien $ m_1 \, $ dan kendala II dengan gradien $ m_2, \, $ maka ada tiga kemungkinan yang terjadi, yaitu :
i). $ m_f \leq m_1 \leq m_2 \, $ artinya nilai optimum diperoleh pada titik pojok garis pertama.
ii). $ m_1 \leq m_f \leq m_2 \, $ artinya nilai optimum diperoleh pada perpotongan kedua garis.
iii). $ m_1 \leq m_2 \leq m_f \, $ artinya nilai optimum diperoleh pada titik pojok garis kedua.
Syarat yang harus dipenuhi :
*). Semua gradien fungsi tujuan dan kendalanya harus negatif.
*). Tanda ketaksamaannya harus sama semua ($\leq \, $ semua atau $ \, \geq \, $ semua).
*). Banyaknya kendala bisa lebih dari 2.
Metode gradien biasanya bisa diaplikasikan pada soal cerita.
Gradien persamaan Garis
Untuk mengingatkan kembali, berikut cara menentukan gradien ($m$) suatu persamaan garis :
Garis $ \begin{align} ax + by = c \rightarrow m = \frac{- \text{koefisien } x}{\text{koefisien } y} = \frac{-a}{b} \end{align} $
Garis $ \begin{align} ax + by = c \rightarrow m = \frac{- \text{koefisien } x}{\text{koefisien } y} = \frac{-a}{b} \end{align} $
1). Tentukan nilai minimum fungsi tujuan $ z = 4x + 6y \, $ dengan
kendala : $ 5x + 10y \geq 20 , \, 3x + y \geq 5, \, x \geq 0, \, y \geq 0 $.
Penyelesaian :
*). Menentukan gradien masing-masing :
fungsi tujuan : $ z = 4x + 6y \rightarrow m_z = \frac{-x}{y} = \frac{-4}{6} = -\frac{2}{3} = - 0,67 $
Kendala I : $ 5x + 10y \geq 20 \rightarrow m_1 = \frac{-5}{10} = -0,5 $
Kendala II : $ 3x + y \geq 5 \rightarrow m_2 = \frac{-3}{1} = -3 $
Karenan gradien kendala dan fungsi tujuannya semuanya negatif, maka metode gradien bisa kita gunakan.
Kita peroleh letak $ m_z \, $ adalah : $ m_2 \leq m_z \leq m_1 $.
Artinya fungsi tutujan minimum pada titik perpotongan kedua garis karena gradien fungsi tujuannya ada diantara gradien kedua kendalanya.
*). Menentukan perpotongan kedua garis kendala :
$ \begin{array}{c|c|cc} 5x + 10y = 20 & \times 1 & 5x + 10y = 20 & \\ 3x + y = 5 & \times 10 & 30x + 10y = 50 & - \\ \hline & & -25x = -30 & \\ & & x = \frac{6}{5} & \end{array} $
Substitusi $ x = \frac{6}{5} \, $ ke persamaan $ 3x + y = 5 $
$ 3x + y = 5 \rightarrow 3x \times \frac{6}{5} + y = 5 \rightarrow y = \frac{7}{5} $.
Sehingga titik perpotongannya adalah ($\frac{6}{5},\frac{7}{5}$).
*). Menentukan nilai minimumnya di titik ($\frac{6}{5},\frac{7}{5}$)
$ z = 4x + 6y = 4 \times \frac{6}{5} + 6 \times \frac{7}{5} = 13,2 $.
Jadi, nilai minimum fungsi $ z = 4x + 6y \, $ adalah 13,2.
2). Tentukan nilai minimum fungsi tujuan $ z = x + 5y \, $ dengan
kendala : $ 5x + 10y \geq 20 , \, 3x + y \geq 5, \, x \geq 0, \, y \geq 0 $.
Penyelesaian :
*). Menentukan gradien masing-masing :
fungsi tujuan : $ z = x + 5y \rightarrow m_z = \frac{-x}{y} = \frac{-1}{5} = - 0,2 $
Kendala I : $ 5x + 10y \geq 20 \rightarrow m_1 = \frac{-5}{10} = -0,5 $
Kendala II : $ 3x + y \geq 5 \rightarrow m_2 = \frac{-3}{1} = -3 $
Karenan gradien kendala dan fungsi tujuannya semuanya negatif, maka metode gradien bisa kita gunakan.
Kita peroleh letak $ m_z \, $ adalah : $ m_2 \leq m_1 \leq m_z $.
Artinya fungsi tutujan minimum pada titik pojok garis pertama karena gradiennya lebih dekat dengan gradien garis pertama.
*). Menentukan titik pojok garis I :
$ 5x + 10y = 20 \rightarrow (0,2), (4,0) $.
Kita cek titik (0,2) dan (4,0) ke kendala yang lainya :
$ (0,2) \rightarrow 3x + y \geq 5 \rightarrow 3.0 + 2 \geq 5 \rightarrow 2 \geq 5 \, $ (salah).
titik (0,2) bukan titik pojok.
$ (4,0) \rightarrow 3x + y \geq 5 \rightarrow 3.4 + 0 \geq 5 \rightarrow 12 \geq 5 \, $ (benar).
titik (4,0) adalah titik pojok.
Sehingga fungsi tujuan $ z = x + 5y \, $ minimum di titik pojok (4,0).
*). Menentukan nilai minimumnya di titik (4,0)
$ z = x + 5y = 4 + 5 \times 0 = 4 $.
Jadi, nilai minimum fungsi $ z = x + 5y \, $ adalah 4.
3). Tentukan nilai minimum fungsi tujuan $ z = 20x + 5y \, $ dengan
kendala : $ 5x + 10y \geq 20 , \, 3x + y \geq 5, \, x \geq 0, \, y \geq 0 $.
Penyelesaian :
*). Menentukan gradien masing-masing :
fungsi tujuan : $ z = 20x + 5y \rightarrow m_z = \frac{-x}{y} = \frac{-20}{5} = - 4 $
Kendala I : $ 5x + 10y \geq 20 \rightarrow m_1 = \frac{-5}{10} = -0,5 $
Kendala II : $ 3x + y \geq 5 \rightarrow m_2 = \frac{-3}{1} = -3 $
Karenan gradien kendala dan fungsi tujuannya semuanya negatif, maka metode gradien bisa kita gunakan.
Kita peroleh letak $ m_z \, $ adalah : $ m_z \leq m_2 \leq m_1 $.
Artinya fungsi tutujan minimum pada titik pojok garis kedua karena gradiennya lebih dekat dengan gradien garis kedua.
*). Menentukan titik pojok garis II :
$ 3x + y = 5 \rightarrow (0,5), (\frac{5}{3},0) $.
Kita cek titik (0,5) dan ($\frac{5}{3}$,0) ke kendala yang lainya :
$ (0,5) \rightarrow 5x + 10y \geq 20 \rightarrow 5.0 + 10.5 \geq 20 \rightarrow 50 \geq 20 \, $ (benar).
titik (0,5) adalah titik pojok.
$ (\frac{5}{3},0) \rightarrow 5x + 10y \geq 20 \rightarrow 5.\frac{5}{3} + 10.0 \geq 20 \rightarrow \frac{25}{3} \geq 20 \, $ (salah).
titik ($\frac{5}{3}$,0) bukan titik pojok.
Sehingga fungsi tujuan $ z = 20x + 5y \, $ minimum di titik pojok (0,5).
*). Menentukan nilai minimumnya di titik (0,5)
$ z = 20x + 5y = 20. \times 0 + 5 \times 5 = 25 $.
Jadi, nilai minimum fungsi $ z = 20x + 5y \, $ adalah 25.
Catatan :
*). Sebenarnya soal nomor 1 sampai nomor 3 memiliki kendala yang sama hanya fungsi tujuannya yang dibedakan agar kita bisa menyelesaikan soal dengan berbagai variasi yang ada terutama cara menentukan titik pojoknya dengan tanpa harus menggambar dulu grafik dan DHPnya.
4). Tentukan nilai maksimum fungsi tujuan $ z = 20x + 10y \, $ dengan
kendala : $ x + 2y \leq 4 , \, 5x + 3y \leq 15, \, x \geq 0, \, y \geq 0 $.
Penyelesaian :
*). Menentukan gradien masing-masing :
fungsi tujuan : $ z = 20x + 10y \rightarrow m_z = \frac{-x}{y} = \frac{-20}{10} = - 2 $
Kendala I : $ x + 2y \leq 4 \rightarrow m_1 = \frac{-1}{2} = -0,5 $
Kendala II : $ 5x + 3y \leq 15 \rightarrow m_2 = \frac{-5}{3} = -1,67 $
Karenan gradien kendala dan fungsi tujuannya semuanya negatif, maka metode gradien bisa kita gunakan.
Kita peroleh letak $ m_z \, $ adalah : $ m_z \leq m_2 \leq m_1 $.
Artinya fungsi tutujan maksimum pada titik pojok garis kedua karena gradiennya lebih dekat dengan gradien garis kedua.
*). Menentukan titik pojok garis II :
$ 5x + 3y \leq 15 \rightarrow (0,5), (3,0) $.
Kita cek titik (0,5) dan (3,0) ke kendala yang lainya :
$ (0,5) \rightarrow x + 2y \leq 4 \rightarrow 0 + 2.5 \leq 4 \rightarrow 10 \leq 4 \, $ (salah).
titik (0,5) bukan titik pojok.
$ (3,0) \rightarrow x + 2y \leq 4 \rightarrow 3 + 2.0 \leq 4 \rightarrow 3 \leq 4 \, $ (benar).
titik (3,0) adalah titik pojok.
Sehingga fungsi tujuan $ z = 20x + 10y \, $ maksimum di titik pojok (3,0).
*). Menentukan nilai maksimumnya di titik (3,0)
$ z = 20x + 10y = 20 \times 3 + 10 \times 0 = 60 $.
Jadi, nilai maksimum fungsi $ z = 20x + 10y \, $ adalah 60.
5). Agar fungsi tujuan $ z = ax + 4y \, $ minimum pada perpotongan kedua
kendala : $ 5x + 2y \geq 10 , \, 3x + 4y \geq 12 , \, x \geq 0, \, y \geq 0 $,
Tentukan rentang nilai $ a $?
Penyelesaian :
*). Menentukan gradien masing-masing :
fungsi tujuan : $ z = ax + 4y \rightarrow m_z = \frac{-x}{y} = \frac{-a}{4} $
Kendala I : $ 5x + 2y \geq 10 \rightarrow m_1 = \frac{-5}{2} $
Kendala II : $ 3x + 4y \geq 12 \rightarrow m_2 = \frac{-3}{4} $
*). Agar penyelesaiannya ada di perpotongan kedua kendala, haruslah gradien fungsi tujuannya ada di antara gradien fungsi kendalanya.
$ \begin{align} m_1 \leq & m_z \leq m_2 \\ \frac{-5}{2} \leq & \frac{-a}{4} \leq \frac{-3}{4} \, \, \, \, \text{(kali -4, tanda dibalik)} \\ \frac{-5}{2} \times (-4) \geq & \frac{-a}{4} \times (-4) \geq \frac{-3}{4} \times (-4) \\ 10 \geq & a \geq 3 \end{align} $
Jadi, rentang nilai $ a \, $ adalah $ \, 10 \geq a \geq 3 \, $ atau $ 3 \leq a \leq 10 $ .
Catatan :
Untuk soal nomor (5), jika ada kata solusinya "hanya" di perpotongan kedua kendala, maka yang dipakai adalah $ m_1 < m_z < m_2 $.