Teori Dualitas dan Penerapannya (Duality Theory and Its Application)

Teori Dualitas dan Penerapannya (Duality Theory and Its Application) Kuliah 06

TI2231 Penelitian Operasional I

1

Materi Bahasan ① Teori dualitas ② Metode simpleks dual


2

① Teori Dualitas


3

Teori dualitas • Dari sudut pandang teoritis dan praktis, teori dualitas merupakan salah satu konsep penting dan menarik dalam pemrograman linier. • Ide dasar dibalik teori dualitas adalah bahwa setiap masalah pemrograman linier mempunyai satu pemrograman linier yang terkait yang disebut dual. • Solusi pada masalah pemrograman liniear originalnya juga memberikan solusi bagi dualnya. • Jika suatu solusi masalah pemrograman linier dipecahkan dengan simplex method, pada dasarnya diperoleh solusi untuk dua masalah pemrograman linier. TI2231 Penelitian Operasional I

4

Pemrograman linier dual simetris • Suatu pemrograman linier dikatakan dalam bentuk simetris jika – semua variabel dibatasi tak negatif – semua pembatas dalam bentuk pertidaksamaan • untuk masalah maksimisasi, bentuk pertidaksamaan adalah “lebih kecil atau sama dengan” • untuk masalah minimisasi, bentuk pertidaksamaan adalah “lebih besar atau sama dengan”


5

Masalah primal Memaksimumkan Z = c1x1 + c2x2 + … + cnxn dengan pembatas

a11x1 + a12x2 + … + a1nxn ≤ b1 a21x1 + a22x2 + … + a2nxn ≤ b2 . . .

am1x1 + am2x2 + … + amnxn ≤ bm x1≥0, x2≥0,…, xn≥0


6

Masalah dual Meminimumkan W = b1y1 + b2y2 + … + bmym dengan pembatas

a11y1 + a21y2 + … + am1ym ≥ c1 a12y1 + a22y2 + … + am2yn ≥ c2 . . .

a1ny1 + a2ny2 + … + amnym ≥ cn y1≥0, y2≥0,…, ym≥0


7

Notasi matrix Primal: Memaksimumkan Z = cx dengan pembatas Ax ≤ b x≥0

A b c x y

Dual: Meminimumkan W = yb dengan pembatas yA ≥ c y≥0

: matriks (m x n) : vektor kolom (m x 1) : vektor baris (1 x n) : vektor kolom (n x 1) : vektor baris (1 x m) TI2231 Penelitian Operasional I

8

Masalah primal-dual Primal

Dual

Max Z = 3x1 + 2x2

Min W = 6y1 + 8x2 + y3 + 2y4

dengan pembatas-pembatas: x1 + 2x2 ≤ 6 2x1 + x2 ≤ 8 – x1 + x2 ≤ 1 x2 ≤ 2 x1, x2 ≥ 0

dengan pembatas-pembatas: y1 + 2y2 – y3 ≥3 2y1 + y2 + y3 + y4 ≥2 y1, y2, y3, y4 ≥ 0


9

Hubungan primal-dual • Koefisien fungsi tujuan untuk masalah primal menjadi konstanta ruas kanan bagi dual. • Konstanta ruas kanan dari primal menjadi koefisien fungsi tujuan bagi dual. • Pertidaksamaan untuk pembatas dibalik untuk kedua masalah. • Tujuan diubah dari maksimisasi untuk primal menjadi minimisasi untuk dual. • Tiap kolom dalam primal menjadi (baris) pembatas pada dual; sehingga jumlah pembatas dual sama dengan jumlah variabel primal. • Tiap (baris) pembatas dalam primal berkaitan dengan kolom pada dual; sehingga satu variabel dual berkaitan dengan satu pembatas primal. • Dual dari masalah dual adalah masalah primal TI2231 Penelitian Operasional I

10

Beberapa teorema dalam teori dualitas • • • •

Weak duality theorem Optimality criterion theorem Main duality theorem Complementary slackness theorem


11

Teorema 1: Weak duality theorem (1) Misalkan diberikan program linier primal-dual simetris: P: max Z = cx, Ax ≤ b, x ≥ 0 D: min W = yb, yA ≥ c, y ≥ 0 Nilai fungsi tujuan dari masalah minimimasi (dual) untuk sebarang solusi layak selalu lebih besar atau sama dengan nilai fungsi tujuan masalah maksimisasi (primal). TI2231 Penelitian Operasional I

12

Teorema 1: Weak duality theorem (2) Bukti Misalkan: x0 : vektor solusi layak untuk primal y0 : vektor solusi layak untuk dual Akan dibuktikan bahwa: y0b ≥ cx0 Karena x0 adalah layak untuk primal, maka Ax0 ≤ b, x0 ≥ 0 (1) Karena y0 adalah layak untuk dual, maka y0A ≥ c, y0 ≥ 0 (2) Perkalian kedua sisi pertidaksamaan (1) dengan y0 Æ y0Ax0 ≤ y0b Perkalian kedua sisi pertidaksamaan (2) dengan x0 : y0Ax0 ≤ cx0 Implikasi : y0b ≥ y0Ax0 ≥ cx0 TI2231 Penelitian Operasional I

13

Teorema 1: Weak duality theorem (3) • Konsekuensi 1: – Nilai fungsi tujuan dari masalah maksimisasi (primal) untuk sebarang solusi layak merupakan batas bawah dari nilai minimum fungsi tujuan dual.

• Konsekuensi 2: – Nilai fungsi tujuan dari masalah minimisasi (dual) untuk sebarang solusi layak (dual) merupakan batas atas dari nilai maksimum fungsi tujuan primal.

• Konsekuensi 3: – Jika masalah primal adalah layak dan nilai fungsi tujuannya tak terbatas (dalam hal ini, max Z →+∞), maka masalah dual adalah tak layak. TI2231 Penelitian Operasional I

14

Teorema 1: Weak duality theorem (4) • Konsekuensi 4: – Jika masalah dual adalah layak dan nilai fungsi tujuannya tak terbatas (dalam hal ini, min W →-∞), maka masalah primal adalah tak layak.

• Konsekuensi 5: – Jika masalah primal adalah layak dan dualnya tak layak maka masalah primal tersebut adalah tak terbatas.

• Konsekuensi 6: – Jika masalah dual adalah layak dan primalnya adalah tak layak maka masalah dual tersebut adalah tak terbatas. TI2231 Penelitian Operasional I

15

Teorema 1: Weak duality theorem (4) - Ilustrasi #1 Primal

Dual

Max Z = 3x1 + 2x2

Min W = 6y1 + 8x2 + y3 + 2y4


dengan pembatas-pembatas: y1 + 2y2 – y3 ≥3 2y1 + y2 + y3 + y4 ≥2 y1, y2, y3, v4 ≥ 0


16

Teorema 1: Weak duality theorem (4) - Ilustrasi #1 adalah solusi layak untuk primal. x10 = 4, x20 = 0 Nilai fungsi tujuan primal Z = cx0 = 12

y10 = 0, y20 = 5, y30 = 0, y40 = 0

adalah solusi layak untuk dual

Nilai fungsi tujuan dual W = y0b = 40 Disini Z = cx0 ≤ y0b = W dan memenuhi weak duality theorem. Berdasarkan Konsekuensi (1), nilai minimum W untuk dual tidak dapat lebih kecil dari 12. Berdasarkan Konsekuensi (2), nilai minimum Z untuk primal tidak dapat melebihi 40. TI2231 Penelitian Operasional I

17

Teorema 1: Weak duality theorem (4) - Ilustrasi #2

Primal:

Dual

Memaksimumkan Z = 4x1 + x2

Meminimumkan W = 2y1 + 3y2

dengan pembatas-pembatas: x1 – x2 ≤ 2 -3x1 + x2 ≤ 3 x1 ≥ 0, x2 ≥ 0

dengan pembatas-pembatas: y1 – 3y2 ≥ 4 - y1 + y2 ≥ 1 y1 ≥ 0, y2 ≥ 0


18

Teorema 1: Weak duality theorem (4) x2 - Ilustrasi #2

Solusi primal Æ tak terbatas

x1 TI2231 Penelitian Operasional I

19

Teorema 1: Weak duality theorem (4) y2 - Ilustrasi #2

Solusi dual Æ tak layak

y1 TI2231 Penelitian Operasional I

20

Teorema 2: Optimality criterion theorem (1) Jika terdapat solusi layak x0 dan y0 untuk masalah pemrograman linier dual simetris sedemikian hingga nilai fungsi tujuannya adalah sama, maka solusi layak ini adalah solusi optimal bagi masing-masing masalah.


21

Teorema 2: Optimality criterion theorem (2) Bukti Misalkan x adalah sebarang solusi layak bagi masalah primal. Maka berdasarkan Teorema 1, cx ≤ y0b Tetapi ini diberikan bahwa cx0 = y0b. Oleh karena itu cx ≤ cx0 untuk semua solusi layak bagi masalah primal. Per definisi, x0 adalah optimal bagi primal. Argumen yang sama juga berlaku bagi optimalitas y0 bagi masalah dual.


22

Teorema 3: Main duality theorem Jika baik masalah primal maupun dual adalah layak, maka keduanya mempunyai solusi optimal sedemikian hingga nilai optimalnya adalah sama.


23

Teorema 4: Complemantary slackness theorem (1) Misalkan diberikan program linier primal-dual simetris: P: max Z = cx, Ax ≤ b, x ≥ 0 D: min W = yb, yA ≥ c, y ≥ 0 dimana A : matriks (m x n) b : vektor kolom (m x 1) c : vektor baris (1 x n) x : vektor kolom (n x 1) y : vektor baris (1 x m) TI2231 Penelitian Operasional I

24

Teorema 4: Complemantary slackness theorem (2) Misalkan: x0 : vektor solusi layak untuk primal y0 : vektor solusi layak untuk dual Maka x0 dan y0 adalah optimal untuk masalah masing jika dan hanya jika

(y A − c)x 0

0

(

)

+ y b − Ax = 0 0

0


25

Teorema 4: Complemantary slackness theorem (3) Bukti: Misalkan

⎛ u1 ⎞ ⎜ ⎟ ⎜ u2 ⎟ u =⎜ ⎟ ( m×1) # ⎜ ⎟ ⎜u ⎟ ⎝ m⎠

adalah vektor slack untuk primal

v = (v1 , v2 , " , vn ) adalah vektor slack untuk dual

(1×n )

Karena x0 dan y0 adalah solusi layak, maka Ax 0 + u 0 = b;

x0 , u0 ≥ 0

y 0 A − v 0 = c;

y0 , v0 ≥ 0

(1) (2)

(u0 dan v0 adalah nilai-nilai dari variabel slack yang berkaitan masing-masing dengan solusi layak x0 dan y0). TI2231 Penelitian Operasional I

26

Teorema 4: Complemantary slackness theorem (4) Perkalian (1) dengan y0 Æ y0Ax0 + y0u0 = y0b Perkalian (2) dengan x0 Æ y0Ax0 – v0x0 = cx0

(3) (4)

Pengurangan (3) dengan (4) Æ y0u0 + v0x0 = y0b – cx0 (5) Untuk membuktikan Teorema 4, harus diperlihatkan bahwa x0 dan y0 adalah solusi optimal bagi masing-masing masalah primal dan dual jika dan hanya jika v0x0 + y0u0 = 0 (6)


27

Teorema 4: Complemantary slackness theorem (5) Bagian 1 Diasumsikan bahwa x0 dan y0 adalah solusi optimal dan harus dibuktikan bahwa Persamaan (6) adalah benar. Karena x0 dan y0 adalah optimal, berdasarkan Teorema 3 maka cx0 = y0b. Oleh karena itu, Persamaan (5) menjadi Persamaan (6) y0u0 + v0x0 = y0b – cx0 Æ v0x0 + y0u0 = 0


28

Teorema 4: Complemantary slackness theorem (6) Bagian 2 Diasumsikan bahwa Persamaan (6) adalah benar dan akan dibuktikan bahwa x0 dan y0 adalah solusi optimal bagi masing-masing masalah primal dan dual Karena Persamaan (6) benar, maka Persamaan (5) menjadi y0b – cx0. y0u0 + v0x0 = y0b – cx0 Æ y0b = cx0 Berdasarkan Teorema 2 maka x0 dan y0 merupakan solusi optimal.


29

Complementary slackness condition

Persamaan (6) : v0x0 + y0u0 = 0 dari complementary slackness theorem dapat disederhanakan sebagai berikut: vj0xj0 = 0 yi0ui0 = 0

untuk semua j = 1, 2, …, n untuk semua i = 1, 2, …, m

dengan memperhatikan hal-hal berikut: 1. x0, u0, v0, y0 ≥ 0 dan oleh karena itu v0x0 ≥ 0 dan y0u0 ≥ 0. 2. Jika jumlah komponen-komponen tak negatif sama dengan nol, maka tiap komponen adalah nol. TI2231 Penelitian Operasional I

30

Complementary slackness condition ① Jika suatu variabel primal (xj0) adalah positif, maka pembatas dual yang bersesuaian memenuhi persamaan pada titik optimalnya (yaitu, vj0 = 0) ② Jika suatu pembatas primal adalah strick inequality pada titik optimal (yaitu, uj0 > 0), maka variabel dual yang bersesuaian (yi0) harus nol. ③ Jika suatu variabel dual (yi0) adalah positif maka pembatas primal yang bersesuaian memenuhi persamaan pada titik optimalnya (yaitu, ui0 = 0) ④ Jika suatu pembatas dual adalah strick inequality pada titik optimal (yaitu vi0 > 0), maka variabel primal yang bersesuaian harus nol TI2231 Penelitian Operasional I

31

Ilustrasi (1) Primal

Dual

Max Z = 3x1 + 2x2

Min W = 6y1 + 8x2 + y3 + 2y4


dengan pembatas-pembatas: y1 + 2y2 – y3 ≥3 2y1 + y2 + y3 + y4 ≥2 y1, y2, v1, v2 ≥ 0


32

Ilustrasi (2) Primal (Penambahan slack variable)

Dual (Penambahan slack variable)

Max Z = 3x1 + 2x2

Min W = 6y1 + 8x2 + y3 + 2y4

dengan pembatas-pembatas: x1 + 2x2 + u1 =6 2x1 + x2 + u2 =8 + u3 =1 – x1 + x2 x2 + u4 = 2 x1, x2, u1, u2, u3, u4 ≥ 0

dengan pembatas-pembatas: y1 + 2y2 – y3 – v1 =3 2y1 + y2 + y3 + y4 – v2 = 2 y1, y2, v1, v2 ≥ 0


33

Ilustrasi (3) Complementary slackness condition mengimplikasikan pada kondisi optimal: u10 y10 = 0 u20 y20 = 0 u30 y30 = 0 u40 y40 = 0

x10 v10 = 0 x20 v20 = 0 TI2231 Penelitian Operasional I

34

Ilustrasi (4) Dengan metode simplex diperoleh solusi optimal untuk masalah primal sebagai berikut:

x10 = 10 / 3 x20 = 4 / 3 Z = 38/3


35

Ilustrasi (5) Dengan penerapan complementary slackness condition, solusi optimal bagi dual ditentukan sebagai berikut 0 0 x = 10 / 3 > 0 → v (1) 1 1 =0 (2) x20 = 4 / 3 > 0 → v20 = 0

(3) x10 + 2 x20 = 10 / 3 + 2(4 / 3) = 6 → u10 = 0, y10 ≥ 0 0 0 0 0 ( ) 2 x + x = 2 10 / 3 + 4 / 3 = 8 → u = 0 , y (4) 1 2 2 2 ≥0 0 0 0 0 ( ) − x + x = − 10 / 3 + 4 / 3 = − 2 < 1 → u > 0 , y (5) 1 2 3 3 =0 (6) x20 = 4 / 3 < 2 → u40 > 0, y40 = 0 TI2231 Penelitian Operasional I

36

Ilustrasi (6) Kondisi (1), (2), (5) dan (6) mengimplikasikan:

y + 2y = 3 2 y + y20 = 2 0 1 0 1

0 2

y10 = 1 / 3 0 y2 = 4 / 3 0 y3 = 0 0 y4 = 0 W = 38/3


37

Penerapan complementary slackness condition • Digunakan untuk mencari solusi primal optimal dari suatu solusi dual optimal, dan sebaliknya. • Digunakan untuk memverifikasi apakah suatu solusi layak adalah optimal untuk masalah primal. • Digunakan untuk menginvestigasi ciri-ciri umum dari solusi optimal pada masalah primal dan dual dengan menguji hipotesis-hipotesis yang berbeda. • Kuhn-Tucker optimality condition untuk pemrograman non linier merupakan pengembangan lebih lanjut dari complementary slackness condition dan sangat berguna dalam pemrograman matematis lanjutan. TI2231 Penelitian Operasional I

38

Karakteristik pokok hubungan primal-dual Primal

Dual

A

Matriks pembatas

Transpos dari matriks pembatas

b

Konstanta ruas kanan

Vektor biaya

c

Vektor biaya

Konstanta ruas kanan

Fungsi tujuan

Max Z = cx

Min W = yb

Pertidaksamaan pembatas

Ax ≤ b

yA ≥ c

Variabel keputusan

x≥0

y≥0


39

Interpretasi ekonomi dari solusi dual (1) • Dalam pandangan ekonomi, solusi dual optimal dapat diinterpretasikan sebagai harga yang dibayarkan untuk sumberdaya pembatas. • Berdasarkan Teorema 3 (main duality), nilai optimal bagi primal dan dual adalah sama. • Jika x0 dan y0 masing-masing adalah solusi optimal, maka Z0 = cx0 = y0b = W0.


40

Interpretasi ekonomi dari solusi dual (2) • Dengan kata lain, nilai optimal dari masalah pemrograman linier (primal atau dual) diberikan oleh Z 0 = y10b1 + y20b2 + " + ym0 bm

dimana b1, b2, …, bm adalah jumlah yang terbatas dari sumberdaya 1, 2, .., m; y10, y10, …, y10 adalah nilai optimal dari variabel dual.


41

Interpretasi ekonomis dari solusi dual (3) • Misalkan diasumsikan bahwa level sumberdaya 1 (yaitu, b1) diubah. • Maka, untuk variasi kecil dalam perubahan nilai b1, katakan Δb1, perubahan dalam nilai optimal dari pemrograman linier Z0 diberikan oleh y10(Δb1). • Dengan kata lain, nilai optimal dari variabel dual untuk tiap pembatas primal memberikan perubahan bersih (net change) dalam nilai optimal dari fungsi tujuan untuk peningkatan satu satuan dalam konstanta ruas kanan. • Oleh karena itu, nilai optimal dari variabel dual disebut shadow price yang dapat digunakan untuk menentukan apakah ekonomis untuk menambah sumberdaya. TI2231 Penelitian Operasional I

42

Contoh interpretasi solusi dual (1) Primal: Memaksimumkan Z = 3x1 + 2x2 dengan pembatas-pembatas: (Bahan A) x1 + 2x2 ≤ 6 2x1 + x2 ≤ 8 (Bahan B) – x1 + x2 ≤ 1 (Selisih permintaan cat interior dan eksterior) x2 ≤ 2 (Permintaan cat interior) x1 ≥ 0 x2 ≥ 0 TI2231 Penelitian Operasional I

43

Contoh interpretasi solusi dual (2) Dual: Meminimumkan W = 6y1 + 8x2 + y3 + 2y4 dengan pembatas-pembatas: y1 + 2y2 – y3 ≥3 2y1 + y2 + y3 + y4 ≥2 y1, y2, y3, y4 ≥ 0


44

Contoh interpretasi solusi dual (3) Solusi optimal dual: y1 = 10/3 Æ shadow price untuk pembatas bahan A, yaitu perubahan dari nilai Z (profit total) per satu satuan peningkatan bahan A. y2 = 4/3 Æ shadow price untuk pembatas Bahan B, yaitu perubahan dari nilai Z (profit total) per satu satuan peningkatan bahan B. y3 = 0 Æ shadow price untuk selisih permintaan cat interior dan exterior, yaitu perubahan dari nilai Z (profit total) per satu satuan peningkatan selisih permintaan cat interior dan exterior. y4 = 0 Æ shadow price untuk pembatas permintaan cat interior, yaitu perubahan dari nilai Z (profit total) per satu satuan peningkatan permintaan cat interior TI2231 Penelitian Operasional I

45

Masalah primal-dual tak simetris (1) Masalah Primal Memaksimumkan Z = 4x1 + 5x2 dengan pembatas 3x1 + 2x2 ≤ 20 4x1 – 3x2 ≥ 10 x1 + x2 = 5 x1 ≥ 0 x2 tak dibatas tanda TI2231 Penelitian Operasional I

46

Masalah primal-dual tak simetris (2) Masalah Primal (Bentuk Simetris) Memaksimumkan Z = 4x1 + 5x3 – 5x4 dengan pembatas 3x1 + 2x3 – 2x4 ≤ 20 – 4x1 + 3x3 – 3x4 ≤ – 10 x1 + x3 – x4 ≤ 5 – x1 – x3 + x4 ≤ – 5 x1, x3, x4 ≥ 0 TI2231 Penelitian Operasional I

47

Masalah primal-dual tak simetris (2) Masalah Dual (Bentuk Simetris) Meminimumkan W = 20w1 – 10w2 +5w3 – 5w4 dengan pembatas 3w1 – 4w2 + w3 – w4 ≥ 4 2w1 + 3w2 + w3 – w4 ≥ 5 – 2w1 – 3w2 – w3 + w4 ≥ – 5 w1, w2, w3, w4 ≥ 0


48

Masalah primal-dual tak simetris (2) Masalah Dual Meminimumkan W = 20y1 + 10y2 +5y3 dengan pembatas

y1 = w1 y2 = – w2 y3 = w3 – w4

3y1 + 4y2 + y3 ≥ 4 2y1 – 3y2 + y3 = 5 y1 ≥ 0 y2 ≤ 0 y3 tak dibatasi tanda TI2231 Penelitian Operasional I

49

Tabel primal-dual secara umum Primal (maksimisasi)

Dual (minimisasi)

Matriks koefisien A

Transpos matriks koefisien

Vektor ruas kanan

Vektor biaya

Vektor harga c

Vektor ruas kanan

Pembatas ke-i adalah persamaan

Variabel dual yi tak dibatasi tanda

Pembatas ke-i bertipe ≤

Varibel dual yi ≥ 0

Pembatas ke-i bertipe ≥

Varibel dual yi ≤ 0

xj tak dibatasi tanda

Pembatas dual ke-j adalah persamaan

xj ≥ 0

Pembatas dual ke-j bertipe ≥

xj ≤ 0

Pembatas ke-j bertipe ≤ TI2231 Penelitian Operasional I

50

Catatan (1) • Teorema (1), (2), (3), dan (4) dari teori dualitas berlaku juga bagi primal-dual tak simetris. • Complementary slackness condition juga berlaku untuk solusi optimal primal-dual tak simetris..


51

Catatan (2) Misalkan diberikan masalah pemrograman linier dalam bentuk standar Memaksimumkan Z = cx dengan pembatas Ax = b x≥0 Masalah dual Meminimumkan W = yb dengan pembatas yA ≥ c y tak dibatasi tanda Complementary slackness condition dipenuhi pada kondisi optimal: (yA – c)x = 0 TI2231 Penelitian Operasional I

52

Menentukan solusi dual optimal (1) • Solusi dual optimal dapat ditentukan dengan complementary slackness condition • Solusi dual optimal dapat juga diperoleh secara langsung dari tabel simplex optimal dari masalah primal.


53

Menentukan solusi dual optimal (2) Meminimumkan Z = cx dengan pembatas Ax = b x≥0


54

Menentukan solusi dual optimal (3) Misalkan : Pj : kolom ke-j dari matrix A B : matrix basis optimal Solusi primal optimal : −1 x ⎛ ⎛ ⎞ B b⎞ B * ⎟ x = ⎜⎜ ⎟⎟ = ⎜⎜ ⎟ x 0 ⎝ N⎠ ⎝ ⎠

dimana xB : varabel basis xN : variabel non basis TI2231 Penelitian Operasional I

55

Menentukan solusi dual optimal (4) Nilai minimum Z = cx* = cBxB = cBB-1b Karena B menunjukkan basis optimal, maka koefisien biaya relatif (c j ) yang berkaitan dengan variabel basis harus tak negatif

c j = c j − πP j ≥ 0

untuk semua j

dimana π = cBB-1 : vektor pengali simplex (simplex multiplier) TI2231 Penelitian Operasional I

56

Menentukan solusi dual optimal (5) Dalam notasi matrix: c-πA≥0

atau

πA ≤ c

yang merupakan pembatas pemrograman linier dual. Sehingga, pengali simplex optimal harus memenuhi pembatas dual.


57

Menentukan solusi dual optimal (6) Nilai fungsi tujuan dual yang berkaitan dengan solusi layak adalah W = yb = πb = cBB-1b yang sama dengan nilai minimum Z. Oleh karena itu, berdasarkan optimality criterion theorem, pengali simplex optimal dari masalah primal merupakan nilai optimal dari variabel dual. TI2231 Penelitian Operasional I

58

Ilustrasi menentukan solusi dual optimal (1) Primal (Dalam bentuk standar)

Dual:

Max Z = 3x1 + 2x2

Min W = 6y1 + 8x2 + y3 + 2y4

dengan pembatas-pembatas: x1 + 2x2 + x3 =6 2x1 + x2 + x4 =8 – x1 + x2 + x5 =1 + x6 = 2 x2 x1, x2, x3, x4, x5, x6 ≥ 0

dengan pembatas-pembatas: y1 + 2y2 – y3 =3 2y1 + y2 + y3 + y4 =2 y1 ≥0 ≥0 y2 y3 ≥0 y4 ≥0 y1, y2, y3, y4 tak dibatasi tanda


59

Ilustrasi menentukan solusi dual optimal (2) Dengan metode revised simplex, solusi optimal untuk primal: x = (x2, x1, x5, x6) = (4/3, 10/3, 3, 2/3) Z = 38/3 Matrix basis optimal: B = [P2

P1

P5

⎡2 1 ⎢1 2 P6 ] = ⎢ ⎢1 − 1 ⎢ ⎣1 0


0 0 1 0

0⎤ 0⎥⎥ 0⎥ ⎥ 1⎦ 60

Ilustrasi menentukan solusi dual optimal (3) Simplex multiplier optimal : ⎡ 2 / 3 −1/ 3 ⎢ −1/ 3 2 / 3 −1 π = c B B = (2,3,0,0 )⎢ ⎢ −1 1 ⎢ ⎣− 2 / 3 1 / 3

0 0⎤ 0 0⎥⎥ = (1 / 3,4 / 3,0,0 ) 1 0⎥ ⎥ 0 1⎦

π memenuhi pembatas dual, dan nilai fungsi tujuannya: W = 6(1/3) + 8(4/3) + 1(0) + 2(0) = 38/3 yang bersesuaian dengan nilai optimal untuk masalah primal. Oleh karena itu, y1 = 1/3, y2 = 3/4, y3 = 0, y4 = 0 Æ optimal untuk dual. Simplex multiplier yang bersesuaian dengan tabel (primal) optimal adalah solusi optimal bagi masalah dual. TI2231 Penelitian Operasional I

61

② Metode Simpleks Dual


62

Masalah Pemrograman Linier (Primal) dalam Bentuk Standar

minimisasi Z = cx dengan pembatas Ax = b x≥0 A : matrix (m x n) P : vektor kolom dari matrix A B : matrix basis untuk masalah primal xB : variabel basis yang bersesuaian dengan B. TI2231 Penelitian Operasional I

63

Basis Layak Primal Basis B : basis layak primal (primal feasible basis) ⇔ B-1b ≥ 0 B : basis layak primal → nilai variabel basis: B-1b solusi layak basis xB = B-1b nilai fungsi tujuan Z = cBB-1b


64

Kondisi Optimalitas (1) Untuk memeriksa apakah basis layak B adalah optimal Æ hitung koefisien fungsi tujuan relatif (c j )

c j = c j − πP j

j = 1, …, n

π = cBB-1 : simplex multiplier Basis layak primal B adalah optimal ⇒ c j ≥ 0 j = 1, …, n


65

Kondisi Optimalitas (2) Pemrograman linier standar bagi dual: maksimisasi W = yb dengan pembatas yA ≤ c y tak dibatas tanda


66

Kondisi Optimalitas (3) Pembatas dual yA ≤ c dapat ditulis: y (P1 , P2 , ", Pn ) ≤ (c1 , c2 , ", cn ) yP j ≤ c j c j − yP j ≥ 0

j = 1, …, n


67

Kondisi Optimalitas (4) Jika basis layak primal B : basis optimal bagi masalah primal Æ simplex multiplier π = cBB-1 memenuhi c j − yP j ≥ 0

j = 1, …, n

Implikasi Æ π : layak bagi masalah dual Nilai fungsi tujuan dual W = πb = cBB-1b sama dengan nilai fungsi tujuan primal ∴Berdasarkan optimality criterion theorem, Æ π : optimal bagi masalah dual TI2231 Penelitian Operasional I

68

Basis Dual Layak (1) Basis B untuk masalah primal minimisasi Z = cx dengan pembatas Ax = b x≥0 layak dual (dual feasible) ⇔ c – cBB-1A ≥ 0 (Identik dengan pemeriksaan apakah basis layak B optimal) TI2231 Penelitian Operasional I

69

Basis Dual Layak (2) Basis B untuk masalah primal : layak primal dan layak dual ÆBasis B : basis optimal Solusi optimal untuk primal : xB = B-1b, xN = 0 Solusi optimal untuk dual : y = cBB-1 Nilai optimal primal = Nilai optimal dual


70

Catatan • Akar dari pemecahan masalah pemrograman linier Æ mendapatkan solusi basis B yang layak primal dan layak dual • Metode simplex Æ bergerak dari satu basis layak primal ke basis yang lain hingga basis tersebut menjadi layak dual – Metode simplex primal (primal simplex method)

• Metode simplex dual (dual simplex method) Æ bergerak dari satu basis layak dual ke basis yang lain TI2231 Penelitian Operasional I

71

Rincian Metode Simplex Dual (1) Pemrograman linier bentuk standar: minimisasi Z = cx dengan pembatas Ax = b x≥0


72

Rincian Metode Simplex Dual (2) • Metode simplex dual menggunakan tabel yang sama dengan metode simplex primal. • Dalam semua tabel, koefisien fungsi tujuan relatif (c j ) dipertahankan tak negatif (Untuk maksimisasi, c j dipertahankan tak positif) • Konstanta ruas kanan tidak perlu tak negatif.


73

Rincian Metode Simplex Dual (3) • Algoritma mulai dengan membuat elemen ruas kanan menjadi tak negatif, dengan pada saat yang sama menjaga koefisien c j tak negatif. • Algoritma berhenti jika semua konstanta ruas kanan telah tak negatif.


74

Rincian Metode Simplex Dual (4) Basis

x1

…

xr

…

xm

xm+1

…

xs

…

xn

Konstanta

x1

1

…

0

…

0

y1,m+1

…

y1s

…

y1n

b1

…

… …

xr

1

…

0

yr,m+1

…

yrs

…

yrn

…

br …

xm

0

…

0

…

1

ym,m+1

…

yms

c

0

…

0

…

0

cm +1

…

cs


ymn …

bm

cn

75

Pemilihan Variabel Basis yang Keluar Basis Pilih variabel basis yang membuat solusi saat ini menjadi tidak layak dengan kata lain Pilih variabel basis yang nilai solusinya negatif Aturan Æ Pilih variabel basis yang nilai bi paling negatif

Misal: br = min (bi ) < 0 i

Ævariabel basis xr diganti baris ke-r : baris pivot TI2231 Penelitian Operasional I

76

Pemilihan Variabel Non Basis yang Masuk Basis (1) Kolom pivot dipilih sedemikian rupa sehingga memenuhi dua kondisi sebagai berikut: 1. Ketidaklayakan primal berkurang (atau paling sedikit, tidak bertambah jelek). Atau, paling sedikit konstanta ruas kanan pada baris r menjadi positif pada tabel berikutnya Æ Variabel non basis (xj) dengan koefisien negatif dalam baris r (yrj < 0) yang memenuhi syarat untuk masuk basis TI2231 Penelitian Operasional I

77

Pemilihan Variabel Non Basis yang Masuk Basis (2) 2. Tabel berikutnya setelah operasi pivot harus tetap layak dual. Dapat dijamin jika variabel non basis yang masuk basis dipilih dengan aturan rasio sebagai berikut:

⎡ cj ⎤ max ⎢ ⎥ y rj < 0 y ⎢⎣ rj ⎥⎦

j = m+1, …, n


78

Ilustrasi Metode Simplex Dual Meminimumkan Z = x1 + 4x2 + 3x4 dengan pembatas x1 + 2x2 – x3 + x4 ≥ 3 – 2x1 – x2 + 4x3 + x4 ≥ 2 x1, x3, x3, x4 ≥ 0

Bentuk standar : Meminimumkan Z = x1 + 4x2 + 3x4 dengan pembatas x1 + 2x2 – x3 + x4 – x5 = 3 – 2x1 – x2 + 4x3 + x4 – x6 = 2 x1, x3, x3, x4, x5, x6 ≥ 0 TI2231 Penelitian Operasional I

79

Tabel 1 cj

1

4

0

3

0

0

cB

Konstanta Basis

x1

x2

x3

x4

x5

x6

0

x5

-1

-2

1

-1

1

0

-3

0

x6

2

1

-4

-1

0

1

-2

1

4

0

3

0

0

Baris c

Tidak layak primal Layak dual TI2231 Penelitian Operasional I

80

Tabel 2 cj

1

4

0

3

0

0

cB

Konstanta Basis

x1

x2

x3

x4

x5

x6

1

x1

1

2

-1

1

-1

0

3

0

x6

0

-3

-2

-3

2

1

-8

0

2

1

2

1

0

Baris c

Tidak layak primal Layak dual TI2231 Penelitian Operasional I

81

Tabel 3 cj

1

4

0

3

0

0

cB

Konstanta Basis

x1

x2

x3

x4

x5

x6

1

x1

1

7/2

0

5/2

-2

-1/2

7

0

x3

0

3/2

1

3/2

-1

-1/2

4

0

1/2

0

1/2

2

1/2

Z=7

Baris c

Layak primal Layak dual TI2231 Penelitian Operasional I

82

Mengidentifikasi Ketidaklayakan Primal dalam Metode Simplex Dual • Dalam metode simplex dual Æ selalu terdapat solusi layak bagi dual. • Metode simplex dual mengenali ketidaklayakan primal jika aturan rasio gagal mengidentifikasi variabel non basis yang masuk basis – Semua elemen dalam kolom pivot : tak negatif


83

Memecahkan Masalah Maksimisasi dengan Metode Simplex Dual Dalam masalah maksimisasi Æ Kondisi optimalitas: Koefisien fungsi tujuan (c j ) ≤ 0 Misal, br < 0 dan xr : variabel keluar basis Variabel non basis yang masuk basis Æ dipilih sedemikian rupa sehingga elemen baris c tetap tak positif pada iterasi berikutnya. Aturan rasio:

⎡ cj ⎤ min ⎢ ⎥ yij < 0 y ⎢⎣ rj ⎥⎦ TI2231 Penelitian Operasional I

84

Penerapan metode simplex dual • Secara umum adalah tidak selalu mudah mendapatkan suatu basis layak dual. • Dalam banyak praktek, masalah tidak mempunyai tabel kanonik baik yang layak primal maupun layak dual. • Metode simpleks primal lebih disukai daripada metode simpleks dual. • Beberapa aplikasi dari metode simpleks dual: – Analisis sensitivitas (sensitivity analysis) dan pemrograman parametrik (parametric programming) – Algoritma pemrograman bilangan bulat (integer programming algorithms) – Algoritma pemrograman non linier (nonlinear programming algorithm) – Varian dari metode simplex: primal-dual algorithm, self-dual parametric algorithm TI2231 Penelitian Operasional I

85

Teori Dualitas dan Penerapannya (Duality Theory and Its Application)

Recommend Documents