BAB I Sekilas tentang Teori-teori sebagai Dasar Program Linear 1. Himpunan konveks Sebuah himpunan X dalam Rn disebut himpunan konveks apabila memenuhi sifat berikut: jika diberikan sebarang dua titik x1 dan x2 di dalam X, maka λx1 + (1- λ)x2 ∈ X untuk setiap λ ∈ [0 , 1]. Selanjutnya kita ketahui bahwa λx1 + (1 - λ)x2 untuk λ dalam interval [0 , 1], menggambarkan titik-titik yang terletak pada ruas garis yang menghubungkan x1 dan x2. Sebarang titik dalam bentuk λx1 + (1- λ)x2 dengan 0 ≤ λ ≤ 1 disebut kombinasi konveks dari x1 dan x2. Jika λ ∈ (0 , 1), maka bentuk λx1 + (1- λ)x2 disebut kombinasi konveks sempurna. Dalam pengertian geometri, himpunan konveks dan himpunan tidak-konkveks dapat digambarkan sebagai berikut:
a. Himpunan konveks
b. Himpunan tidak-konveks
Gambar 1.1. Contoh himpunan konveks dan himpunan tidak konveks. Pada gambar sebelah kiri (Gambar 1.1.a), untuk semua kombinasi konveks dari x1 dan x2 berada dalam X, sedangkan pada gambar sebelah kanan (Gambar 1.1.b), terdapat kombinasii konveks dari x1 dan x2 yang berada diluar X. Jadi gambar sebelah kiri adalah menggambarkan himpunan konveks, sedangkan himpunan gambar sebelah kanan adalah menggambarkan himpunan tidak-konveks. Berikut adalah contoh-contoh himpunan konveks:
{
}
1. ( x1 , x 2 ) : x12 + x 2 2 ≤ 1
1 1 0 2. x : x = λ1 0 + λ 2 1 + λ 3 1, λ1 + λ 2 + λ 3 = 1, λ1 , λ 2 , λ 3 ≥ 0 0 0 1
1
2
2. Titik Ekstrim Dalam kajian pada program linear, titik ekstrim sangat berperan dalam menentukan nilai optimum suatu masalah. Sebuah titik dalam himpunan konveks X disebut titik ekstrem dari himpunan X, jika titik x tersebut tidak dapat dinyatakan dengan kombinasi konveks sempurna dari dua titik yang berbeda dalam X. Dengan kata lain jika x titik ekstrim dan x = λx1 + (1- λ)x2, dengan λ ∈ (0 , 1) dan x1, x2 ∈ X, maka x = x1 = x2. Gambar berikut memperlihatkan titik ekstrim dan bukan titik ekstrim.
Gambar 1. 2. Titik-titik pada himpunan konveks X. Titik x1 adalah titik ekstrimdari X, sedangkan x2 dan x3 bukan titik ekstrim dari X. 3. Sinar dan Arah Himpunan Konveks Sinar pada Himpunan Konveks Misalkan X himpunan konveks. Sinar adalah himpunan titik-titik yang berbentuk {x0 + λd : λ ≥ 0} dimana d vektor tak-nol. Dalam hal ini, x0 disebut titik ujung dari sinar, dan d adalah arah sinar.
Arah Himpunan Konveks Misalkan X himpunan konveks, vektor tak-nol d disebut arah suatu himpunan X, jika untuk setiap x0 di X, {x0 + λd : λ ≥ 0} juga di X. Oleh karena itu seseorang dapat mengambil sebarang titik x0 di X, dan menariknya dengan memperpanjang atau memperpendek (recede) d dengan λ ≥ 0 , maka akan tetap berada di X. Jelas apabila X terbatas, maka X tidak mempunyai arah.
3
Contoh 1.1 Tentukan arah himpunan polihedral X = {x : Ax ≤ b, x ≥ 0}. Jawaban Misalkan d arah himpunan X, maka untuk setiap λ ≥ 0 dan x ∈ X, d ≠ 0 dan memenuhi A(x + λd) ≤ b
.... (1)
x + λd ≥ 0
.... (2)
Karena x ∈ X, maka memenuhi Ax ≤ b. Dari (1) dengan mengambil λ ≥ 0 cukup besar (lim λ →∞) diperoleh Ad ≤ 0. Dengan cara serupa dari (2) akan diperoleh d ≥ 0. Jadi d arah himpunan X jika dan hanya jika d ≥ 0, d ≠ 0, dan Ad ≤ 0. Dengan cara serupa untuk X = {x : Ax = b, x ≥ 0} dan d arah himpunan X, maka d ≥ 0, d ≠ 0 dan Ad ≤ 0.
Contoh 1. 2. Tentukan arah himpunan X = {(x1,x2) : x1 + x2 ≥ 1, x1 - x2 ≥ -2, x1 ≥ 0, dan x2 ≥ 0 }. Jawaban
d1
d
d2 ≤d1
d1
Gambar 1. 3. Himpunan X = {(x1,x2) : x1 + x2 ≥ 1, x1 - x2 ≥ -2, x1 ≥ 0, dan x2 ≥ 0 } Misalkan x0 = (x1,x2) sebarang titik di X dan d = (d1,d2) arah himpunan X.
4
Karena d = (d1,d2) arah himpunan X, maka d ≠ 0 dan untuk setiap λ ≥ 0, berlaku x0 + λd = (x1 + λd1 , x2 + λd2) ∈ X akibatnya: x1 + λd1 + x2 + λd2 ≥ 1
... (1)
x1 + λd1 - x2 - λd2 ≥ -2
... (2)
x1 + λd1 ≥ 0
... (3)
x2 + λd2 ≥ 0
... (4)
Dari (1) dapat dubah menjadi x1 + x2 + λ(d1 + d2) ≥ 1 Karena x1 dan x2 tetap dan dengan λ sebarang, maka untuk λ yang cukup besar berlaku d1 + d2 ≥ 0 atau d2 ≥ -d1. Persamaan (2) juga dapat diubah menjadi x1 - x2 + λ(d1 - d2) ≥ -2. Dari persamaan terakhir ini dengan mengambil x1 dan x2 tetap dan dengan λ sebarang, maka untuk λ yang cukup besar berlaku d1 – d2 ≥ 0 atau d2 ≤ d1. Dengan cara serupa dari (3) dan (4) kita peroleh d1 ≥ 0 dan d2 ≥ 0. Sehingga secara keseluruhan diperolah d2 ≥ - d1, d2 ≤ d1, d1 ≥ 0 dan d2 ≥ 0. Dari keempat hasil ini dapat disederhanakan menjadi d1 ≥ 0 dan 0 ≤ d2 ≤ d1.
4. Arah Ekstrim Himpunan Konveks Pendefinisian arah ekstrim himpunan mirip dengan titik ekstrim. Suatu arah ekstrim himpunan konveks adalah arah suatu himpunan konveks yang tidak dapat di representasikan dengan kombinasi positif dari dua arah himpunan yang berbeda. Dua vektor d1, d2 dikatakan berbeda atau tidak ekivalen jika d1 tidak dapat direpresentasikan dengan perkalian positif dengan kelipatan d2. Pada Contoh 2 di atas, maka d1 = (1,0) dan d2 = (√2/2 , √2/2) adalah arah ekstrim yang telah di normalkan. Untuk setiap arah himpunan konveks dapat dinyatakan sebagai kombinasi dari d1 dan d2 yaitu dalam bentuk λ1d1 + λ2d2, dengan λ1, λ2 > 0. Dengan demikian setiap arah himpunan yang berbentuk d = (d1 , d2) dengan d1 ≥ 0 dan 0 ≤ d2 ≤ d1 dapat ditulis dalam bentuk λ1d1 + λ2d2. Misalnya arah d = (5, 2) adalah memenuhi syarat untuk arah dari X, maka apabila kita tuliskan dalam bentuk kombinasi linear λ1d1 + λ2d2, λ1 = 3 dan λ2 = 2√2.
diperoleh
5
5. Hyperplane dan Halfspace Bidang banyak (Hyperplane) di Rn adalah bentuk generalisasi dari garis di R2 atau sebuah bidang di R3. Bidang banyak H di Rn adalah himpunan yang berbentuk {x:px = k} dimana p vektor tak nol di Rn dan k suatu skalar. Disini p disebut normal dari bidang banyak. Bidang banyak terdiri dari semua titik x = (x1, x2, ..., xn) yang memenuhi persamaan n
∑ p j x j = k . Konstan k dapat dieliminasikan dengan menggunakan suatu titik tertentu j =1
misalnya x0 di H. Jika x0 ∈ H, maka akan memenuhi px0 = k, dan setiap x ∈ H, kita miliki px = k. Jadi dengan proses mengurangkannya kita peroleh p(x - x0) = 0, dimana x0 sebarang titik tetap di H. Bidang banyak adalah konveks. Gambar berikut adalah bidang banyak dan vektor normal p, dimana p ortogonal terhadap x - x0.
Gambar 1.4. Bidang banyak Bidang banyak membagi Rn dalam dua daerah, yang disebut ruang paruh (halfspaces). Dengan demikian ruang paruh adalah himpunan titik-titik yang berbentuk {x: px ≥ k}, dimana p vektor tak-nol di Rn dam k skalar. Sedangkan ruang paruh yang satunya akan berbentuk
6
{x: px ≤ k}. Irisan kedua ruang paruh adalah bidang banyak dan gabungan kedua ruang paruh tersebut adalah Rn.
Gambar 1.5. Ruang Paruh. Berkaitan dengan x0 titik tetap di bidang banyak, maka kedua ruang paruh dapat dinyatakan dengan {x : p(x – x0) ≥ 0} atau {x : p(x – x0) ≤ 0}. Gambar di atas memperlihatkan ruang paruh yang pertama yang terdiri dari titik-titik x sedemikian hingga (x – x0) membentuk sudut lancip (≤ 90°) terhadap p, dan ruang paruh yang kedua terdiri dari titik-titik x sedemikian hingga (x – x0) membentuk sudut tumpul (≥ 90°) terhadap p.
6. Fungsi konveks dan fungsi konkav Fungsi f : Rn → R disebut konveks jika untuk dua vektor x1 dan x2 di Rn berlaku: f (λx1 + (1- λ)x2) ≤ λ f (x1) + (1- λ) f (x2), untuk semua λ ∈ [0 , 1]. Selanjutnya fungsi f : Rn → R disebut konkav jika -f adalah fungsi konveks. Jadi fungsi f adalah konkav jika memenuhi pertidaksamaan berikut: f (λx1 + (1- λ)x2) ≥ λ f (x1) + (1- λ) f (x2), untuk semua λ ∈ [0 , 1]. Fungsi konveks dan fungsi konkav dapat diilustrasikan seperti gambar berikut:
7
(a)
(b)
(c)
Gambar 1.6. Contoh fungsi konveks dan fungsi konkav Gambar (a) adalah fungsi konveks, λ f (x1) + (1- λ) f (x2) digambarkan sebagai titik pada tali busur yang menghubungkan f (x1) dan f (x2), sedangkan f (λx1 + (1- λ)x2) adalah titik pada f yang menghubungkan f (x1) dan f (x2). Dapat dilihat dari gambar bahwa λ f (x1) + (1- λ) f (x2) berada diatas f (λx1 + (1- λ)x2). Jadi f (λx1 + (1- λ)x2) ≤ λ f (x1) + (1- λ) f (x2), yang berarti f konveks. Dengan analogi yang sama, maka dapat dilihat bahwa gambar (b) adalah fungsi konkav dan gambar (c) menggambarkan fungsi yang bukan konveks maupun konkav.
8
7. Representasi Himpunan Polihedral (Polihedron) Polihedral adalah sebuah bangun yang dibentuk oleh beberapa halfspace atau sebuah bangun yang dibentuk oleh oleh sistem pertidaksamaan linear. Misalnya, X adalah Polihedral yang dibatasi oleh: -3x1 + x2 ≤ -2 - x1 + x2 ≤ 2 -x1 + 2x2 ≤ 8 -x2 ≤ -2 x1 ≥ 0, x2 ≥ 0. Polihedral dapat merupakan hipunan terbatas, dan dapat pula tak terbatas. a. Himpunan Polihedral terbatas Himpunan Polihedral terbatas adalah himpunan polihedral yang memenuhi kriteria bahwa terdapat bilangan k sehingga untuk setiap x pada himpunan berlaku x < k. Gambar 5 adalah polihedral terbatas dengan enam halfspace dan memiliki enam titik ekstrim, yaitu x1, x2, x3, x4, x5, x6. x adalah titik di dalam polihedral, maka x dapat dinyatakan dengan kombinasi konveks y dan x1 : x = λ y + (1 – λ) x1, dengan λ ∈ (0 , 1). Selanjutnya y itu sendiri merupakan kombinasi konveks dari x3 dan x4: y = ηx3 + (1 – η) x4, dengan η∈ (0 , 1).
Gambar 1.7. Representasi sebuah titik dalam polihedral terbatas terhadap titik-titik ekstrem
9
Dengan mensubstitusikan x3 dan x4 kedalam y maka kita peroleh: x = ληx3 + λ (1 – η) x4 + (1 – λ) x1 Karena λ ∈ (0 , 1) dan η∈ (0 , 1), maka λη, λ (1 – η) , (1 – λ) ∈ (0 , 1). Juga memenuhi λη+ λ (1 – η) + (1 – λ). Dengan kata lain, x dapat direpresentasikan sebagai kombinasi konveks terhadap titik-titik ekstrim x1, x3, x4. Hal ini dapat diambil genaralisasi bahwa setiap titik dalam himpunan polihedral terbatas, dapat dinyatakan sebagai kombinasi konveks dari titik-titik ekstrimnya.
b. Himpunan Polihedral tak-terbatas Dalam polihedral tak-terbatas, maka sebuah titik dapat di representasikan dalam kombinasi titik ekstrim dan arah ekstrim himpunan. Gambaran berikut adalah sebuah titik representasi sebuah titik pada polihedral tak terbatas.
Gambar 1.8. Repesentasi titik pada Polihedral tak-terbatas Misalkan x ∈ X sebarang, maka x = s + d, s dapat dinyatakan dengan kombinasi konveks dari x2 dan x4 yaitu s = λ1x1 + λ2x2 sedangkan d dapat dinyatakan dengan kombinasi dari d1 dan d2, yaitu d = η1d1 + η2d2. Jadi x = λ1x1 + λ2x2 + η1d1 + η2d2.
10
8. Teorema Representasi Bentuk Umum Misalkan X = {x : Ax ≤ b, x ≥ 0} himpunan tak-kosong (polihedron). Maka himpinan titik-titik ekstrim tak-kosong dan banyaknya titik-titik tersebut berhingga, sebut x1, x2, x3, . . . , xk. Selanjutnya himpunan arah adalah kosong jika dan hanya jika X terbatas. Jika X tak-terbatas, maka himpunan arah tak-kosong dan memiliki sejumlah berhingga vektor, sebut d1, d2, . . ., dm. Kemudian, x ∈ X jika dan hanya jika x dapat dinyatakan sebagai kombinasi konveks dari x1, x2, x3, . . . , xk ditambah dengan kombinasi linear tak negatif dari d1, d2, . . ., dm yaitu, x=
k
∑ λ j x j + ∑ η jd j
m
k
∑ λ j = 1,
j =1
j =1
j =1
λ j ≥ 0, j = 1,2,..., k η j ≥ 0, j = 1,2,..., m
Bukti. Tidak dibuktikan dalam buku ini.
Akibat. Untuk sebarang x*∈X dapat direpresentasikan sebagai x* =
k
∑ λ j x j + ∑ η jd j ,
m
k
∑ λ j = 1,
j =1
j =1
j =1
λ j ≥ 0, j = 1,2,..., k , η j ≥ 0, j = 1,2,..., m .
Soal-soal 1. Tunjukkan bahwa hyperplane H = {x : px = k} dan halfspace H*= {x : px ≥ k} adalah himpunan konveks. 2. Buatlah grafik yang menggambarkan himpunan yang memenuhi {(x1,x2) : -x1 + x2 ≤ 2, x1 + 2x2 ≤ 8, x1 ≥ 0, x2 ≥ 0}. Apakah himpunan ini konveks ? 3. Buatlah grafik yang menggambarkan himpunan yang memenuhi {(x1,x2) : x1 + x2 ≥ 2, x1 ≤ 8, x1 ≥ 0, x2 ≥ 0}. Apakah himpunan ini konveks ?
11
4. Misalkan a1 = (1 , 0), a2 = (2 , 3), a3 = (-1 , 4), a4 = (5 , -3), a5 = (-4 , 4). Ilustrasikan secara geometri kombinasi konveks dari ke-lima titik ini. 5. Tentukan fungsi-fungsi berikut konveks, konkaf atau tidak keduanya. a. f(x) = 2x b. f(x) = x2 c. f(x) = x3 d. f(x1,x2) = x1 2 + 3 x2 6. Misalkan himpunan X = {(x1,x2) : x1 + 2x2 ≥ 2, x1 - 2x2 ≥ -6, x1 ≥ 0, dan x2 ≥ 1}. Tentukan arah himpunan X ini. 7. Diketahui himpunan X = {(x1,x2) : x1 + 2x2 ≥ 2, x1 - 2x2 ≥ -6, x1 ≥ 0, dan x2 ≥ 1}. Nyatakan titik-titik berikut sebagai kombinasi konveks dan arah himpunan: a. (1 , 1) b. (1 , 2) c. (2 , 1) d. (3 , 2) e. (6 , 3)
