
Quadratic Programming (QP) adalah salah satu metode optimasi matematis yang bertujuan untuk menemukan nilai optimal (maksimum atau minimum) dari sebuah fungsi objektif kuadratik dengan batasan linier. QP adalah kasus khusus dari nonlinear programming yang sering digunakan dalam berbagai bidang seperti pembelajaran mesin, ekonomi, teknik, dan keuangan. Aplikasi Quadratic Programming seperti Optimasi Portofolio Keuangan (Investor menggunakan QP untuk meminimalkan risiko portofolio sambil memaksimalkan return dengan batasan dana yang tersedia); Support Vector Machine (QP digunakan untuk melatih model SVM dalam menemukan hyperplane optimal yang memisahkan dua kelas data); Desain Sistem Kendali (dalam kontrol optimal, QP digunakan untuk menyelesaikan masalah regulasi dan perencanaan jalur); Optimasi Energi (QP membantu mengoptimalkan alokasi sumber daya energi, seperti distribusi daya listrik, dengan meminimalkan biaya operasional) Perencanaan Produksi (QP digunakan untuk memaksimalkan efisiensi produksi dengan batasan kapasitas dan waktu)
Masalah Quadratric Programming secara umum dirumuskan sebagai:
dengan batasan:
dan
: matriks simetris positif semi-definit (definisi fungsi kuadratik).
: vektor koefisien linear.
- : matriks batasan linier.
- : vektor batasan linier.
- arti tanda
adalah transpose dari matrix
Contoh Soal Quadratic Progrmming
Misalkan kita ingin menyelesaikan masalah Quadratic Programming berikut
dengan batasan
dan
Jawab
Cara Menyusun Persamaan Quadratic Programming (QP) untuk metode Optimasi, Mari kita ubah menjadi bentuk seperti berikut, untuk matrix simetris Q yaitu
Maksud dari diatas yaitu ketika
arti tanda adalah transpose dari matrix. Mari kita analisis apakah pernyataan tersebut benar. Matriks yang Diberikan:
Langkah-Langkah Perhitungan
1. Misalkan:
Substitusi menjadi:
2. Hitung :
3. Hitung :
4. Kalikan dengan :
Kesimpulan
Hasil dari operasi tersebut adalah:
sedangkan untuk
yang c karena tidak ada, maka dibuat matrix sebagai berikut
sedangkan batasan dari
,
- dan
harus kita ubah sesuai QP yaitu
, dan
caranya dengan dikali -1
sehingga bila kita ubah menjadi matrix A dan b yaitu
dan
mari kita coba maka hasilnya sesuai dengan batasan dari Quadratic Programming
bila kita jabarkan
dan
menjadi
mari kita uji perkalian antar matrix
baris pertama menghasilkan
sedangkan
- baris kedua
, dan
- baris ketiga
merupakan persamaan yang sama dengan dan
sehingga semuanya sudah memenuhi syarat yaitu
mari kita tulis menggunakan Python
import numpy as np from scipy.optimize import minimize # Definisikan fungsi objektif def objective(x): Q = np.array([[1, 0], [0, 2]]) # Matriks Q return 0.5 * np.dot(x.T, np.dot(Q, x)) # (1/2) x^T Q x # Definisikan batasan def constraint1(x): return x[0] + x[1] - 1 # x1 + x2 >= 1 -> x1 + x2 - 1 >= 0 def constraint2(x): return x[0] # x1 >= 0 def constraint3(x): return x[1] # x2 >= 0 # Titik awal x0 = np.array([0.5, 0.5]) # Titik awal (arbitrer) # Batasan constraints = [ {"type": "ineq", "fun": constraint1}, # x1 + x2 >= 1 {"type": "ineq", "fun": constraint2}, # x1 >= 0 {"type": "ineq", "fun": constraint3}, # x2 >= 0 ] # Optimisasi solution = minimize(objective, x0, constraints=constraints) # Output hasil x_opt = solution.x print("Solusi optimal:", x_opt) print("Nilai optimal fungsi objektif:", objective(x_opt))
hasilnya
Solusi optimal: [0.66666667 0.33333333] Nilai optimal fungsi objektif: 0.3333333333333332
penjelasannya yaitu
Fungsi objektif
- fungsi kuadratik
dihitung sebagai
Batasan
diterjemahkan menjadi fungsi batasan
dan
diterjemahkan menjadi
dan
Visulisasi Grafis
Untuk melakukan visualisasi grafis diatas, kalian bisa menggunakan library matplotib. Sumbu Z akan mininum ketika
dan
Kode python akan tampil jika telah login
Kasus Quadratic Programming yang lain
dengan batasan
Jawab
Fungsi Objektif Q dan c yaitu
Login terlebih dahulu jika ingin mendapatkan jawaban lebih lanjut