1 · Himpunan cembung
- S ⊂ Rn cembung jika garis antara dua titik di S tetap di S
| Cembung | Tak cembung |
|---|---|
| half space 5x1+3x2≤15; hyperplane 5x1+3x2=15; polyhedral (irisan half space); cakram x1²+x2²≤4 | luar lingkaran (x1−3)²+(x2−3)²≥4; himpunan titik bulat (integer) |
x1=(2,0), x2=(0,4), α=0,25: 0,25(2,0)+0,75(0,4) = (0,5; 3). 0,3x1+0,7x2 kombinasi cembung; bobot harus jumlah 1
2 · Ketetanggaan & solusi layak
x=(1,1), ε=0,5: (1,3; 1,3) jarak 0,424 → tetangga; (1,4; 1,4) jarak 0,566 → bukan
- Layak: x ∈ S (memenuhi himpunan pembatas); tak layak: x ∉ S. Himpunan solusi = semua solusi layak
S: 5x1+3x2≤15, −x1+x2≤1, x2≤3, x≥0. (1,5; 2,5): 15≤15, 1≤1, 2,5≤3 → layak. (2,2): 16>15 → tak layak
3 · Fungsi cembung & cekung
| Cembung | Cekung | |
|---|---|---|
| f(αx1+(1−α)x2) | ≤ αf(x1)+(1−α)f(x2) | ≥ αf(x1)+(1−α)f(x2) |
| sempurna | < (ketat) | > (ketat) |
- f cembung ⇔ −f cekung (dan sebaliknya)
- Linier (3x+2): cembung dan cekung (tidak sempurna)
- Tak memenuhi keduanya: tak cembung & tak cekung (mis. −x1²+x2²)
f=x³, x1=−2, x2=0, α=½: f(−1)=−1 > ½(−8)+½(0)=−4 → syarat ≤ dilanggar → bukan cembung
4 · Uji kecembungan dengan turunan
1 variabel: f″(x) > 0 untuk semua x → cembung; f″(x) < 0 untuk semua x → cekung; f″ berubah tanda → tak cembung & tak cekung
| f | f″ | hasil |
|---|---|---|
| x²+2x+3 | 2 | cembung |
| −x²−2x+3 | −2 | cekung |
| x³+3x² | 6x+6 | tak cembung, tak cekung (ganti tanda di x=−1) |
Multi variabel: gradien ∇f = (∂f/∂xj); Hessian H(x) = [∂²f/∂xi∂xj] (n×n)
- H definit/semidefinit positif untuk semua x ∈ S → f cembung
- H definit/semidefinit negatif → f cekung
- H tak definit → tak cembung & tak cekung
† Pelengkap dari pembahasan soal: H definit (tanpa nilai 0) → sempurna; semidefinit (ada 0) → cembung/cekung tapi tak sempurna, mis. (x1−x2)² (LPM 2 dan 0).
5 · Kedefinitan via leading principal minor
LPM orde k = submatriks kiri-atas k×k dari Q simetris (buang n−k baris & kolom terakhir). Hitung det tiap orde, lihat tandanya:
| Q | tanda det LPM orde 1,2,3,… |
|---|---|
| definit positif | semua > 0 (+,+,+) |
| semidefinit positif | semua ≥ 0 (tak negatif) |
| definit negatif | ganjil < 0, genap > 0 (−,+,−) |
| semidefinit negatif | ganjil ≤ 0, genap ≥ 0 |
| tak definit | pola lain, mis. (+,−,+) atau (−,−) |
| Contoh | LPM | hasil |
|---|---|---|
| diag(2,2) | 2, 4 | definit + |
| diag(1,0,1) | 1, 0, 0 | semidef. + |
| diag(−1,−1,−1) | −1, 1, −1 | definit − |
| diag(−1,0,−1) | −1, 0, 0 | semidef. − |
| diag(1,−1,1) | 1, −1, 1 | tak definit |
| diag(−2,2) | −2, −4 | tak definit |
x1³+2x2²+3x1+4x2+5: H=diag(6x1,4), LPM 6x1 dan 24x1 ganti tanda → tak definit → tak cembung & tak cekung.
6 · Solusi optimal: global & lokal
- Optimal global x*: f(x*) ≥ f(x) (maks) / ≤ (min) untuk semua x ∈ S
- Unik: ketidaksamaan ketat (> / <), satu-satunya
- Optimal lokal: hanya untuk x ∈ N(x*) (ketetanggaan)
- Global ⇒ lokal (†); lokal belum tentu global
Slide: maks f(x)=x⁵/5−35x⁴+(6625/3)x³−60375x²+675000x, 0≤x≤63: x=10 lokal, x=45 global.
7 · Transformasi model
maks Z=−x²+4x+7 → min Z′=x²−4x−7: x=2, Z′=4−8−7=−11 → Z=11
Konstanta pada f(x)+c tidak mengubah x*; hanya menggeser nilai Z (Z=Z′+c)
min (x−3)²+100, x≤2: tanpa batas x=3 (tak layak) → x*=2, Z=1+100=101
8 · Model optimisasi cembung
Ciri: f cembung/cekung dan himpunan pembatas S cembung.
| Kasus | f | S | hasil x* |
|---|---|---|---|
| min | cembung | cembung | minimum global |
| maks | cekung | cembung | maksimum global |
Pelanggaran (mis. S himpunan bulat, maksimisasi fungsi cembung) → optimal lokal bisa bukan global.
9 · Pemrograman linier (LP)
- Ciri LP: variabel majemuk & kontinu; berpembatas; f & pembatas linier; tujuan tunggal; parameter deterministik (bukan stokastik)
- LP = kasus khusus model cembung (S polyhedral, f linier). Ada solusi layak → dijamin ada optimal global
maks Z=3x1+2x2; 5x1+3x2≤15; −x1+x2≤1; x2≤3; x≥0. Optimum = perpotongan 5x1+3x2=15 & −x1+x2=1 → (1½, 2½), Z=9½, unik
† Cek titik sudut: (0,0)→0, (3,0)→9, (1,5;2,5)→9,5, (0,1)→2. Untuk Z=4x1+x2 optimum di (3,0), Z=12.