BAB 2 TINJAUAN PUSTAKA

BAB 2 TINJAUAN PUSTAKA

2.1 Asumsi dan Sifat-Sifat Teoritis Masalah optimisasi tak terbatas dikaji menggunakan : Asumsi 2.1 (Masalah Terbatas). Untuk setiap nilai parameter p ∈ [0, 1] relaksasi dari LP (1.1) terbatas dari bawah, yaitu persoalan LP-nya tidak layak atau memiliki nilai objektif optimal terbatas.

Sebagai konsekuensi langsung dari asumsi 2.1 parametrik MILP (1.1) terbatas dari bawah untuk semua p ∈ [0, 1].

Asumsi 2.2 (Data fungsi rasional parameter). Data (matriks, vektor biaya, vektor basis) adalah fungsi rasional kontinu dari parameter p ∈ [0, 1], yaitu kutipan polinom dengan penyebut tidak nol.

Berdasarkan asumsi 1 dan 2 himpunan parameter p dapat dibagi kedalam interval jumlah terbatas dan / atau beberapa segmen, sehingga untuk setiap interval atau segmen masalahnya adalah tidak layak meskipun solusi optimal juga merupakan fungsi rasional dalam parameter p yang merupakan variabel konstan. Proses ini merupakan akibat langsung dari jumlah terbatas realisasi integer dan pada dasarnya untuk setiap nilai parameter terdapat basis yang optimal. Beberapa interval optimalitas yang merosot (menurun), tetapi ada juga penelitian dengan hasil tidak nol yang berurutan. Biaya marginal c¯ dalam kasus LP juga fungsi rasional dari parameter. Tidak ada sifat convexity atau concavity dapat ditampilkan untuk nilai obyektif optimal sebagai fungsi dari parameter.

6 Universitas Sumatera Utara

7 2.2 Parametrik Program Linear Seperti yang telah disebutkan dibagian pendahuluan, yang menjadi permasalahan utama dari paramtrik MILP ini adalah parametrik LP. T

min (c(p)) x x

dengan kendala A1x(p)x = b1(p) 2x

(2.1)

2

A (p)x ≤ b (p) x ∈ Rnx , xL ≤ x ≤ xU

Sama halnya dengan persamaan (1.1) data dari c(p) ∈ Rnx , A1(p) ∈ Rm1 xnx , A2 (p) ∈ Rm2 xnx , b1(p) ∈ Rm1 dan b2(p) ∈ Rm2 diasumsikan adalah fungsi rasional yang kontinu dimana parameter p ∈ [pt , pu ]. Dan jika diturunkan persamaan tersebut dari persamaan yang standar untuk menunjukkan keberadaan kendala pertidaksamaan dan batas-batas dari variabel yang ada. Sehingga dapat diselesaikan dengan efisien. Algoritma 0 memberikan garis besar penelitian yang sangat teliti di permasalahan batas-batasnya, yang dapat menjadi solusi dari persamaan (2.1) dan kemudian dua alternatif untuk permasalahan yang mendukung disajikan secara terperinci. Di langkah pertama dalam operasi penyelesaian dengan fungsi yang rasional. Dibagian ini juga terdapat masalah yang masih dapat dikembangkan, yaitu permasalahan atau kendala yang cukup banyak dengan ketidakpastian atau error yang cukup tinggi didalam operasi yang bersifat rasional dan juga permasalahan dalam peningkatan jumlah variabel dan kendala. Untuk mendukung solusi yang akan dibahas dibagian kontinu, pada akhirnya yang kita butuhkan adalah pernyataan terminasi algoritma. Algoritma 0 sebenarnya bermula dari algoritma yang dibuat oleh Dinkelbach (1969), disana dijelaskan secara jelas dalam sebuah tabel implementasi dengan menggunakan metode simpleks untuk kasus parametrik.

Universitas Sumatera Utara

8 Seperti halnya, algoritma Dinkelbach dapat dilanjutkan atau diteruskan untuk diimplementasikan, dengan tidak menghilangkan sifat-sifat yang ada didalam penyelesaian LP tersebut dan membutuhkan operasional yang cukup banyak dengan fungsi-fungsi rasional. Di algoritma 0 LP (2.1) diharapkan selesai pada titik Break Point (untuk nilai parameter yang statis) dengan menggunakan LP solver yang biasa digunakan. Kemudian diasumsikan permasalahan baru yang didapat dari diagram atau hasil tersebut, algoritma tersebut bergerak untuk menyelesaikan break point tersebut dengan menggunakan semua matriks yang menjadi basis program linear, dimana matriks-matriks tersebut memiliki daerah layak dan kondisi-kondisi optimal. Jika di kasus yang LP-nya infeasible ini menandakan ada daerah parameter yang parametrik LP-nya juga infeasible, dan daerah ini dapat diidentifikasi dengan menggunakan auxiliary problem, berdasarkan fasa pertama dengan metode simplex. Diberikan juga LP Solver yang dapat mengurangi nilai error daripada Algoritma Dinkelbach, karena banyaknya kasus yang tidak terselesaikan dalam permasalahan fungsi rasional jauh, lebih kecil dari pada yang lainnya. Penelitian ini dibuat hanya untuk memfaktorisasi matriks dengan ukuran m1 + m2 dan paling banyak (m1 + m2)3 operasi dengan fungsi yang rasional. Dibagian lainnya, tidak ada cabang ilmu dari heuristik yang dapat menggaransi sebuah angka iterasi untuk metode simplex, dan itu menjadi konsekuensi dari algoritma Dinkelbach. Untuk permasalahan yang besar, diharapkan algoritma Dinkelbach yang dilakukan dapat mengurangi banyaknya iterasi yang akan terjadi. Sejak operasi-operasi yang dilakukan akan mendapati kesimpulan matriks-matriks ((A1(p) dan A2 (p)) dan nilai error yang dihasilkan dari iterasi-iterasi yang terjadi cukup kecil. Untuk penelitian ini, algoritma berikut dapat diterapkan untuk variabel yang lebih banyak dari kendalanya, nx m1 + m2.


9 Algoritma 0 (Parametrik Program Linear)

Input semua data dari permasalahan ke algoritma, dengan toleransi dari pertidaksamaan primal εinf dan batas - batas dari pertidaksamaan εopt dan sebuah nilai yang diperkirakan untuk parameter variabel step δp > 0. Algoritma menggunakan sebuah himpunan R untuk menyimpan nilai-nilai dari solusi optimal. Elemen dari R adalah kembar empat, dibentuk dari nilai parameter pRl , sebuah nilai Boolean g Rl , dapat menjelaskan semua permasalahan yang feasible untuk elemen (g Rl = Benar) atau bukan (g Rl = Salah), sebuah nilai xRl (p), dan harus berkorespondensi dengan fungsi objektif f Rl (p).

1. Inisialkan dengan ps = pl . 2. Ulangi a. Selesaikan LP (2.1) untuk p = ps + δp dan tetapkan menjadi solusi basis. b. IF Daerah Layak Then i. Menetapkan g= Benar ELSE i. Menetapkan g= Benar ii. Menetapkan f(p) = +∞ iii. Selesaikan fasa 1 untuk problem (3.2) untuk p = p¯ = ps + δp dan tetapkan menjadi solusi basis. c. Susunlah sistem parametrik tersebut menjadi persamaan dan pertidaksamaan. d. Tentukan variabel yang tergantung dari solusi x(p), f(p) untuk p ∈ [ps , pu ]. e. Setelah itu ditentukan daerah layak di p ∈ [ps , pu ]. Misalkan pt adalah nilai terendah dari parameter untuk semua kendala primal yang dilarang. IF pt ≤ ps + δp THEN misalkan δp =

δp . 2

GOTO langkah 2a.

Menetapkan pt = min{pt , pu }.


10 f. Tentukan nilai - nilai dari range yang optimal di p ∈ [ps , pt ] Misalkan pt adalah nilai terendah dari parameter untuk semua kendala primal yang dilarang. IF pt ≤ ps + δp THEN misalkan δp =

δp . 2

GOTO langkah 2a.

Mengambil pt = min{pt , pu }. g. Simpan (ps , x(p), f(p), g) di R. h. Mengambil ps = min{pt , pu }. Until ps ≤ pu Pada saat pemberhentian iterasi R didalamnya terdapat solusi untuk parametrik LP. Untuk semua elemen Rl dimana g Rl = Salah, program tersebut menghasilkan daerah tidak layak untuk p ∈ [pRl , pRl+1 ] dan ketika g Rl = Benar, titik xRl (p) memenuhi kendala primal dimana εinf bertoleransi dan nilai dari kendala marginal tanpa εopt bertoleransi, menggunakan sifat konveksitas pRl+1 = pu untuk l = |R|. Menyelesaikan nilai dari parameter yang lebih tinggi dari p = ps + δp memenuhi perubahan yang terjadi dibasis program linear dan juga mengecek kembali nilai-nilai dari daerah layak dan nilai optimal di p ∈ {ps , pu } memenuhi nilai basis yang juga harus optimal di [ps , ps + δp]. Parameter δp harus diperkenalkan dan diatur sehingga menjadi sangat kecil, hal ini bertujuan untuk mencegah perhitungan kembali. Diasumsikan kesederhanaan telah dijelaskan. Yang menjadi catatan penting adalah adalah penyelesaian LP, itu lebih bertipe memberikan keuntungan untuk menyimpan nilai informasi dari basis program linear dan memberikan nilai awal basis program linear untuk langkah selanjutnya.

2.3 Menentukan Solusi Kualitatif Ketika menyelesaikan persamaan (2.1) untuk sebuah nilai parameter p yang spesifik, dikeadaan umum solusi yang valid atau diterima hanyalah solusi dengan nilai parameter yang valid atau dapat diterima. Dibahagian lainnya, dengan diasumsikan batas batas dari fungsi kendala, untuk semua nilai parameter dipersamaan (2.1) adalah layak, terdapat sebuah solusi optimal untuk persamaan (2.1) dan


11 sebuah titik dengan daerah layak yang telah optimal. Sebagai konsekuensinya adalah plausible untuk mendefinisikan solusi kualitatif sebagai nilai pencarian awal ataupun basis program linear. Hasil tersebut menuntun kita menuju sebuah sistem persamaan yang mendukung sistem persamaan parametrik dan memasukkan fungsi yang tergantung pada nilai variabel basis program linear untuk parameter tersebut. Variabel Non Basis juga ada untuk ditentukan batasannya. Berdasarkan ketergantungan fungsional tersebut didapat analisis sensitif post-optimal. Ini adalah permasalahan utama dan sangat penting untuk subproblem didalam algoritma. Dikasus vektor biaya, adalah kasus trivial untuk matriks basis dan matriks ruas sisi kanan tergantung dari parameter. Sebagai konsekuensi dari solusi kualitatif invarian, parameternya adalah bebas. Dikasus basis program linear, elemen matriks adalah parameter bebas dan matriks basis program linear dapat dikonversi dan kemudian dikalikan dengan matriks basis program linear. Meskipun di vektor basis program linear sangat berdampak di parameter tersebut, solusi kualitatif invarian juga memberikan efek terhadap parameter di fungsi tersebut. Di kasus umum (2.1) sebuah matriks telah diinversi sebagai fungsi dari parameter p. Pada dasarnya invers ini didapatkan dengan operasi basis elementer untuk matriks basis B, sebagai contohnya, faktorisasi LU dapat diikuti dengan substitusi kembali, dengan operasi simbolik untuk matriks elemen. Jika semua data berfungsi rasional untuk parameter p, maka dapat dijadikan sebagai kandidat solusi optimal. Berdasarkan ini, Dinkelbach (1969) membuat proposal untuk menggunakan algoritma simpleks untuk fungsi rasional. Pendekatan ini tidak dapat digunakan untuk matriks ukuran besar karena angka yang digunakan dapat mengakibatkan nilai menjadi sangat besar. Dengan catatan penggunaan presisi aritmatik adalah dilarang dengan sangat tegas. Pada penelitian ini juga bertujuan untuk mencari alternatif untuk solusi numerikal dari himpunan persamaan dengan fungsi kontinu selama deteksi kebenaran untuk pertidaksamaan primal dan pertidaksamaan biaya marginal.


12 Sebuah permasalahan kompleks dapat diselesaikan menggunakan solver seperti CPLEX adalah harus diperkenalkan variabel tambahan, seperti surplus dan slack untuk persamaan dan pertidaksamaan. Salah satu alasan untuk itu adalah jarang ditemukan LP yang memiliki kendala bebas linear (redundant atau infeasible). Di terminasi program, solver tersebut memiliki m1 + m2 variabel basis program linear, beberapa diantaranya adalah original dan beberapa adalah variabel slack ataupun surplus. Variabel non basis adalah berada pada batas bawah (xj = xLj ) ataupun batas atas (xj = xuj ). Yang menjadi catatan penting adalah perbandingan secara langsung ke LP dalam bentuk standar dimana variabel nonbasisnya memiliki nilai nol. Sebuah persamaan infeasible untuk semua variabel surplus yang berhubungan adalah basis dan bukan nol, dibagian lainnya persamaan tersebut menjadi redundant jika variabel surplus yang berhubungan adalah basis tetapi terletak pada level nol. Jika persamaan (2.1) adalah ekivalen kepada min (c(p))T x x,s

dengan kendala A1x(p)x + I 1s = b1 (p) A2x(p)x + I 2s = b2 (p)

(2.2)

x ∈ Rnx , xL ≤ x ≤ xU s ∈ Rm1 , s = 0 t ∈ Rm2 , 0 ≤ t, Dimana I 1dan I 2 adalah matriks identitas dengan ukuran m1 dan m2, jelaslah bahwa solusi optimal (2.1) adalah juga optimal di persamaan (2.2) dan sebaliknya. Di algoritma 0, LP Solver digunakan untuk persamaan (2.1) dimana untuk subroutine 1, permasalahan yang di perbaharui tersebut digunakan untuk sistem parametrik. Diharapkan pada saat terminasi, LP solver memberikan 2 vektor integer d ∈ {0, 1, 2}n dan dr ∈ {0, 1}m1 +m2 . Komponen j th dari dv menandakan variabel v

j memiliki batas bawah (dvj = 0), basis (dvj = 1), dan batas atas (dvj = 2). Komponen j th dari dv menandakan variabel tambahan j adalah basis (drj = 1) atau non basis (drj = 0).


13 Subroutine 1 menjelaskan bagaimana sistem persamaan kuadrat disusun dan akan menyimpan sebuah parameter bergantung matriks B(p) ∈ R(m1 +m2 )x(m1 +m2 ) dan sebuah parameter bergantung nilai vektor basis program linear b(p) menyelesaikan sistem B(p)xB = b(p) sebagai fungsi dari parameter yang diberikan dapat memenuhi fungsi yang bergantung tersebut. Untuk selanjutnya batas batas variabel basis tersebut disimpan di xB,L dan xB,U dan nilai basis program linear dari variabel basis disimpan dalam cB (p). Subroutine 1(Penyusunan Parametrik Sistem Persamaan) Subroutine ini menggunakan variabel penghitung i, j dan menyimpan sejumlah varibel basis di nb . 1. Menetapkan bi (p) = b1i (p) untuk i = 1, · · · , m1. 2. Menetapkan bi+m1 (p) = b2i (p) untuk i = 1, · · · , m2. 3. Menetapkan nb = 0. 4. Untuk i = I, · · · , nx Lakukan a. IF dvi = 1 THEN i. nb = nb + 1. ii. Menetapkan bj,nb (p) = A1j,i (p) untuk i = 1, · · · , m1 . iii. Menetapkan bj+m1 ,nb (p) = A2j,i(p) untuk i = 1, · · · , m2. iv. cB nb (p) = ci (p). L v. xB,L nb = xi . U vi. xB,U nb = xi .

b. ELSE IF dvi = 0 THEN i. Menetapkan bj (p) = b1j − A1j,i (p)xLi untuk j = 1, · · · , m1. ii. Menetapkan bj+m1 (p) = b2j (p) − A2j,i(p)xLi untuk j = 1, · · · , m2. c. ELSE i. Menetapkan bj (p) = b1j − A1j,i (p)xUi untuk j = 1, · · · , m1. ii. Menetapkan bj+m1 (p) = b2j (p) − A2j,i(p)xUi untuk j = 1, · · · , m2.


14 END 5. Untuk i = 1, · · · , m1 + m2 Lakukan a. IF dri = 1THEN i. nb = nb + 1. ii. Menetapkan bi,nb (p) = 1 iii. Menetapkan bj,nb (p) = 0 untuk j = 1, · · · , m1 + m2 ; j 6= 1. iv. xB,L nb = 0. B,U v. IF i ≤ m1 THEN Menetapkan xB,U nb = 0 ELSE xnb = +∞.

vi. cB nb = 0. END Seperti yang telah ditunjukkan di contoh 2.2 ada banyak kemungkinan yang akan keluar ketika B(p) menjadi matriks singular dan memberikan hasil yang layak untuk beberapa nilai parameter, karena setelah menjadi basis program linear dan kendala primal serta marginal tidak menjamin persamaan menjadi optimal. Untuk menyederhanakan kasus seperti ini kita harus membuat sebuah asumsi tambahan yaitu :

Asumsi 2.3 Jika sebuah baris tambahan B(p) adalah optimal untuk beberapa p¯ dan singular untuk beberapa nilai parameter nilai p¯ ∈ P kemudian ada nilai δ > 0, dimana untuk ∀p ∈ P : |¯ p − p| < δ sistem persamaan B(p)xB = b(p) tidak memiliki solusi yang dapat memenuhi kendala primal xB ∈ [xB,L, xB,U ].


15 Yang menjadi perhatian yang utama adalah asumsi 2.3 hanya dibutuhkan untuk satu dari dua alternatif yang ditunjukkan disubproblem algoritma 0, yang dinamakan dengan continuation. Jika asumsi ini dibatalkan maka konsekuensinya adalah untuk nilai parameter dengan matriks singular, nilai solusi suboptimal akan diperhitungkan kembali dengan algoritma yang ada. Dan juga untuk variabelvariabel yang memiliki batasan yang jelas asumsi 2.3 dapat diturunkan menggunakan pernyataan yang sederhana yaitu JIka sebuah basis tambahan B(p) adalah optimal untuk beberapa p dan singular untuk semua nilai parameter p¯ ∈ P yang lain, kemudian sistem B(¯ p)xB = b(¯ p) tidak memiliki solusi.

2.3.1 Solusi kualitatif dengan operasi rasional Algoritma yang dilakukan oleh Dinkelbach (1969) menyelesaikan parametrik LP secara langsung menggunakan operasi rasional. Sebagai akibatnya setiap iterasi −1

(B(p)) b(p)dapat digunakan. Makalah ini bertujuan untuk mengambil matriks tersebut dan menunjukkan sebuah faktorisasi LU dengan menggunakan operasi rasional. Penulis mengasumsikan kehadiran sebuah algoritma faktorisasi LU dari matriks rasional B(p) sebagai sebuah permutasi matriks M, dengan semua elemen bebas dari p, sebuah matriks segitiga bawah L(p) dengan semua elemen diagonal utama sama dengan satu dan sebuah matriks segitiga atas U(p) yang memenuhi persamaan berikut:

MB(p) = L(p)U(p) Metode ini diizinkan, minimal untuk sifatnya, karena digunakan untuk melihat jika matriks tersebut menjadi singular untuk beberapa titik parameter, langkah pertama adalah menghitung besar dari nilai determinannya

1 +m2 | det(B(p))| = Πm |UI,i (P )| i=1

Dan ketika menghitung pertama kali nilai parameter untuk yang | det(B(p))| = 0 maka sifat asumsi 2.3. tidak diperlukan. Dengan catatan algoritma yang digunakan oleh Dinkelbach (1969) dibutuhkan. Daerah hasil dari basis


16 yang dapat diinverskan telah dikenal, sistem B(p)xB = b(p)dapat diselesaikan dengan dua langkah. Langkah pertama adalah elminasi L(p)v = MB(p), dapat dilakukan dengan memberikan vektor temporer v(p) sebagai sebuah fungsi untuk parameter. Dan kemudian kembali melakukan substitusi U(p)xB = v(p), dengan syarat kehadiran terikat. Remark 2.1. (Dilakukan kepada matriks sebelum faktorisasi LU). Sejak variabel surplus dan slack hanya memiliki satu elemen tidak nol, adalah sangat efisien untuk menyusun kembali variabel dan matriks basis, dengan meletakkan variabel artifisial disebelah kiri atas, basis untuk menunjukkan proses faktorisasi. Untuk kesederhanaan penulis tidak menjelaskan ini di subroutine 1.

2.3.2 Solusi kualitatif dengan continuation Sebuah permasalahan yang matriks inversnya mendapat perlakuan operasi rasional, adalah sangat banyak penafsiran aritmatika yang dilakukan, dengan larangan perluasan atau kesalahan numerik yang menjadi besar sejalan dengan pembesaran ukuran sistem persamaan. Penulis bertujuan mencari sebuah jalur alternatif untuk melakukan pendekatan menggunakan metode Continuation. Metode ini tidak bisa digunakan untuk operasi dengan fungsi rasional dan juga sistem ukuran besar. Nilai basis di subroutine 1 dapat diselesaikan dengan metode continuation. Sebuah keuntungan tambahan adalah asumsi 2 tidak dibutuhkan. Sebuah kerugian juga muncul disolusi dengan opersai rasional adalah asumsi 3 dibutuhkan. Nazareth (1991) menggunakan sebuah variasi dari metode simpleks berdasarkan continuation untuk parametrik LP, dimana efek parameter itu hanya untuk vektor biaya dan basis program linear. Ide utama dari continuation adalah mengikuti definisi implisit dari kurva F (x, λ) = 0, dimana f : Rn+1 → Rn adalah diasumsikan smooth. Metode predictor-corrector meninggalkan jejak dikurva dan mengeneralisasi barisan dari titik (λi , z i ) yang mana kurvanya memberikan toleransi (||f(z, λ|| < ε). Pada iterasi yang diberikan langkah pertama dimulai dari λi−1 menuju λi dan sebuah predictor z¯i dapat diperhitungkan. Sebagai contoh dengan menggunakan sebuah pendekatan polynomial spline. Koreksi dari jenis ini dapat ditunjukkan meng-


17 gunakan Newton Solver untuk solusi f(λi , z i ) = 0 dengan z¯i sebagai nilai yang diprediksi. Ukuran dari langkahnya adalah λi − λi−1 tergantung kepada kualitas aproksimasi dari langkah langkah sebelumnya. Penelitian ini tidak akan membahas hal yang berhubungan dengan homotopy continuation, dan titik akhir (untuk λ = 1) dikurva yang dibutuhkan. Penulis tertarik dengan yang telah dipaparkan dan mengestimasi solusi dari B(p)xB = b(p)

(2.3)

Untuk sebuah daerah hasil dari nilai parameter dan penulis menggunakan predictor polynomials sebagai sebuah aproksimasi untuk solusi. Meskipun estimasi diperlukan untuk kualitas predictor disemua titik yang digeneralisasikan sebagaimana baiknya untuk titik yang berada diantaranya. Ketika itu mungkin memiliki sifat menguasai semua ||f(z, λ||, Seperti yang telah di kemukakan oleh Neubert (1997), kebanyakan metode memberikan nilai estimasi error (Rheinboldt, 1983). Kesamaan estimasi error dapat diaplikasikan atau dirujuk ke solusi dari sistem persamaan differensial aljabar (Asher et.al., 1998) yang memberikan harapan penelitian ini akan sukses menyelesaikan persoalan diatas dengan latihan perhitungan. Di aplikasi yang dibahas, untuk sebuah nilai parameter yang ditetapkan dalam sistem persamaan linear akan dapat diselesaikan. Meskipun langkah dari corrector dapat ditunjukkan oleh beberapa linear solver yang lain secara langsung maupun iterasi. Dengan mengasumsikan bahwa predictor sangat bagus dalam memperkirakan, itu akan menjadi keuntungan jika menggunakan metode iterasi, khususnya untuk sistem persamaan yang besar. Karena tidak ada invers secara langsung dari basis B(p) dapat ditunjukkan, algoritma yang ada tidak bisa mendeteksi nilai parameter untuk matriks yang singular. Formulasi yang dilakukan hanya dapat mendeteksi sifat singular, tetapi matriks tersebut sangatlah susah untuk mendapatkannya.


18 Kemungkinan yang lain adalah untuk mendeteksi sifat singular adalah dengan metode continuation, tetapi karena alasan efisiensi maka untuk jenis faktor LU tidak dapat dilaksanakan. Ini harus mengandalkan asumsi 3, yang dapat menggaransi kendala primal tidak rusak sebelum matriks tersebut menjadi singular.

2.4 Mencari Daerah Hasil Daerah hasil yang diberikan dengan basis adalah didefinisikan secara implisit dengan B(p)xB = b(p)

(2.4)

xB,L ≤ xB ≤ xB,U Dikasus umum, daerah hasil adalah himpunan Disjoint, di algoritma 0 daerah layak untuk titik parameter ps telah diberikan dan nilai terkecil dari nilai parameter pt untuk persamaan (2.4) adalah tidak layak dan memenuhi toleransi εinf dibutuhkan. Dikasus vektor biaya, langkah ini tidak diperlukan, sejak daerah hasil tidak tergantung pada parameter. Dikasus basis program linear dengan tergantung pada nilai yang diperbaharui di parameter, xB adalah fungsi affine di parameter dan hanya sebuah pertidaksamaan linear dibutuhkan untuk diperiksa kembali.

2.4.1 Solusi dengan operasi rasional Mengingat kembali dengan menggunakan eliminasi maju dan substitusi mundur, didapatkan hasil fungsi tergantung oleh xB di parameter. Subroutine 1 menunjukkan nilai parameter terkecil pt untuk persamaan (2.4) adalah tidak layak dengan menggunakan toleransi εinf .


19 Subroutine 2(Menghasilkan daerah hasil yang layak) 1. Menetapkan pt = pu . 2. Untuk i = 1, · · · , m1 + m2 Lakukan a. IF xB,L > −∞ THEN menetapkan pt sama dengan hasil terkecil dari i B,L xB (p) − εinf untuk p ∈ [ps , pt ]. i (p) = xi

b. IF xB,L > +∞ THEN menetapkan pt sama dengan hasil terkecil dari i B,L xB (p) + εinf untuk p ∈ [ps , pt ]. i (p) = xi

END Langkah ini dapat menunjukkan bahwa operasi rasional tidak memiliki hasil atau akar akar di [ps , pt ] dimana pt yang sisa tidak dapat tergantikan.

2.4.2 Solusi dengan continuation Sebagai tambahan, untuk mengurusi jejak yang ditinggalkan oleh solusi persamaan (2.3) penulis mempunyai tujuan untuk ketidaklayakan εinf untuk kendala kendala primal xB,L ≤ xB ≤ xB,U dengan menggunakan kode deteksi, seperti yang telah dihasilkan Park and Barton (1996) yang menggabungkan sistem persamaan aljabar turunan. Algoritma ini harus menghibridkan sebuah kejadian dengan menyelesaikan interpolasi polynomial tanpa langkah continuation dan kemudian menentukan letak kejadian tersebut dengan akurat.


20 2.5 Mencari Daerah Optimal Di LP secara eksplisit, kondisi optimal adalah tersediaan [31] dan dapat digunakan untuk mengidentifikasi daerah optimal. Mengingat kembali arti dari matrix basis B(p), vektor biaya dari solusi cB (p) dan vektor integer dv dari subroutine 1. Sistem berikut secara implisit mendefinisikan daerah optimal dari sebuah basis (B(p))T z = cB (p) m2 i+m1 2 i 1 1 Σm Ai+m1 ,j (p) ≥ 0, ∀j : dvj = 0 i=1 z Ai,j (p) − Σi=1 z m2 i+m1 2 i 1 1 Ai+m1 ,j (p) ≥ 0, ∀j : dvj = 0 Σm i=1 z Ai,j (p) − Σi=1 z

(2.5)

zj ≤ 0, ∀j ≤ m1 : drj = 0, Dimana z ∈ Rm1 +m2 adalah sebuah vektor dengan variabel tambahan. Pertidaksamaan pertama dan kedua menghitung variabel awal non basis yang terdapat di dalam vektor marginal. Pertidaksamaan ketiga menghitung biaya marginal dari variabel slack untuk pertidaksamaan non basis, sejak nilai dari variabel slack sama dengan nol dan hanya ada satu buah input variabel slack di matriks tersebut. Yang menjadi perhatian, nilai marginal untuk variabel surplus (untuk persamaan non basis) tidak butuh untuk dihitung. Sejak variabel surplus dapat memasuki basis dari daerah tidak layak.

Remark 2.2 (mengeliminasi variabel tambahan). Sejak nilai dari variabel surplus adalah sebuah himpunan yang sama dengan nol dan kolom dari matriks tersebut berkorespondensi dengan variabel surplus yang sama dengan vektor identitas, penulis dapat mengeliminasi variabel z yang berkorespondensi dengan variabel surplus yang menjadi basis dari persamaan (2.5). langkah ini bertujuan untuk penyederhanaan. Dengan tujuan untuk mencari daerah layak, dikasus (2.5) menunjukkan himpunan disjoint untuk parameter tersebut. Di algoritma 0, penulis menunjukkan kondisi optimal dari sebuah nilai parameter ps dan penulis berkeinginan untuk menemukan nilai terkecil parameter pt untuk persamaan (2.5) yang terlarang dengan memenuhi toleransi εopt .


21 Di kasus basis program linear langkah ini tidak diperlukan, sejak nilai marginal tidak tergantung pada parameter. Di kasus nilai vektor dengan ketergantungan affine di parameter, sebuah himpunan pertidaksamaan linear ditbutuhkan untuk diperiksa kembali.

2.5.1 Solusi dengan operasi rasional Setelah penulis menurunkan faktorisasi LU dari matriks B(p). Penulis menggunakan faktorisasi ini untuk menghitung variabel tambahan z dan batas batas nilai marginal seperti yang ditunjukkan dalam subroutine 3.

Subroutine 3 ( Mendapatkan daerah hasil optimal ) 1. Selesaikan U T (p)u = cB (P ) untuk u dengan menggunakan eliminasi maju. 2. Selesaikan LT (p)v = u(P ) untuk v dengan menggunakan eliminasi mundur. 3. Hitung z(p) = M T y(p). 4. Untuk j = 1, · · · , m1 . a. IF drj = 0 THEN menetapkan pt sama dengan hasil pertama dari zj (p) = −εopt di p ∈ [ps , pt ]. END 5. Untuk j = 1, , n, dvj 6= 1 m2 1 2 1 a. Menetapkan t(p) = c(p) − Σm i=1 zi (p)Ai,j (p) − Σi=1 zi+m1 (p)Ai+m1 (p). j

b. IF

dvj

= 0 THEN menetapkan pt sama dengan hasil pertama dari t(p) =

−ε di p ∈ [ps , pt ]. ELSE menetapkan pt sama dengan hasil pertama dari t(p) = ε di p ∈ [ps , pt ] END Yang perlu diperhatikan adalah jika operasi rasional tidak memiliki akar di [ps , pt ], nilai pt yang tertinggal tidak akan berubah lagi.


22 2.5.2 Solusi dengan continuation Penulis bertujuan untuk menunjukkan pembagian dan pengklasifikasian dari fungsi marginal nilai biaya dari pertidaksamaan seperti yang ditunjukkan oleh perlakuan pada pertidaksamaan primal. Sebagai contoh selesaikan (B(p))T z = cB (P ) sebagai fungsi dari p, mengunakan metode continuation sampai salah satu persamaan tersebut tidak digunakan. m2 1 2 v 1 cj (p) − Σm i=1 zi Ai,j (p) − Σi=1 zi+m1 Ai+m1 ,j (p) ≥ 0, ∀j : dj = 0 m2 1 2 v 1 cj (p) − Σm i=1 zi Ai,j (p) − Σi=1 zi+m1 Ai+m1 ,j (p) ≤ 0, ∀j : dj = 2

Zj ≤ 0, ∀j < m1 : drj = 0, Oleh sebuah nilai yang mendekati εopt .

2.6 Daerah Hasil Tidak Layak Diharapkan untuk beberapa nilai parameter p, ¯ parametrik LP (2.1) adalah tidak layak, untuk menentukan daerah hasil yang tidak layak penulis membutuhkan fungsi kendala tambahan, sama seperti fase 1 dari metode simpleks (D. Bertsimas, 1997), dimana variabel surplus diperkenalkan untuk kedua jenis kendala persamaan dan pertidak samaan.

m1 +m2 min Σi=1 si x,s

dengan kendala x x x Σnj=1 A1i,j (p)xj + sign(b1i (¯ p) − Σnj=1 A1i,j xLj (¯ p))si = b1i (p) − Σnj=1 A1i,j xLj , i = 1, · · · , m1 x x Σnj=1 A2i,j (p)xLj − si+m1 ≤ b2i (p)−Σnj=1 A2i,j (p)xLj , i = 1, · · · , m2

x ∈ Rnx ,0 ≤ x ≤ xU − xL s ∈ Rm1 +m2 ,0 ≤ s. (2.6)


23 Penting bahwa, tanda tanda dari variabel tambahan yang dihitung pada nilai tetap parameter p¯ digunakan untuk memenuhi persamaan dengan menggunakan percobaan bahwa persamaan (2.6) adalah sebuah daerah layak untuk nilai nilai dari parameter. Sebelum dijelaskan bagaimana fungsi kendala digunakan, kita harus menunjukkan beberapa sifat yang harus dipenuhi. Proposisi 1 (permasalahan parametrik fase 1) 1. Parametrik lanjutan LP (2.6) adalah layak untuk p = p. ¯ 2. Untuk semua parameter pˆ parameterik LP (2.1) adalah layak jika dan hanya jika nilai solusi optimal dari parametrik lanjutan LP (2.6) adalah sama dengan nol. 3. Untuk semua parameter pˆ parameterik LP (2.1) adalah layak jika dan hanya jika nilai solusi optimal dari parametrik (2.6) adalah lebih besar dari nol. Bukti

1. Batas atas dari persamaan menunjukkan kelayakan dari pasangan (¯ x, s¯). x Ambil x¯ = 0, s¯i = |b1i (¯ p) − Σnj=1 A1I,j xLj(¯ p)| untuk i ≤ m1 dan x s¯i = max{0, −b2i−m1 (¯ p) + Σnj=1 A2i−m1 (p)xLj } untuk i > m1 . Perlakuan ini

harus memenuhi batas-batas variabel. Kendala i adalah ekivalen dengan x x x sign(b1i (¯ p) − Σnj=1 A1I,j xLj (¯ p))|b1i (¯ p) − Σnj=1 A1I,j xLj (¯ p)| = b1i (¯ p) − Σnj=1 A1I,j (¯ p)xLj ,

Dimana dapat memenuhi definisi dari lambang sign dan nilai absolut. Kendala pertidaksamaan i adalah ekivalen terhadap x x − max{0, −b2i (¯ p) − Σnj=1 A2i,j (p)xLj } ≤ b2i (¯ p) − Σnj=1 A2i,j (¯ p)xLj ,

Dimana perlakuan ini memenuhi definisi dari max. 2. a. Untuk nilai solusi dari pˆ dari permasalahan lanjutan (2.6) adalah nol. Penulis secara tidak sengaja menemukan pasangan (¯ x, s¯) yang layak di persamaan (2.6) dan memenuhi sˆ = 0.


24 Dengan sifat kelayakan dan berpatokan ke batasan variabel 0 ≤ xˆ ≤ xU − xL atau ekivalen dengan xL ≤ x˜ ≤ xU , dimana x˜ = xU − xˆ. sifat kelayakan ini berpatokan pada kendala dan memberikan x x A1i,j (ˆ p)ˆ xLj + sign(b1i (¯ p) − Σnj=1 A1i,j xLj (¯ p))0 Σnj=1

x = b1i (ˆ p) − Σnj=1 A1i,j (ˆ p)xLj = i = 1, · · · , m1

atau x Σnj=1 A1i,j (ˆ p)(ˆ xj + xLj ) = b1i (ˆ p), i = 1, · · · , m1.

Sejalan dengan persamaan tersebut, kelayakan dengan kendala pertidaksamaan memberikan x Σnj=1 A2i,j (ˆ p)(ˆ xj + xLj ) = b2i (ˆ p), i = 1, · · · , m2.

Dengan menggunakan hubungan yang terjadi di atas, itu akan dihasilkan nilai x˜ yang layak di persamaan (2.1) untuk pˆ. b. Nilai pˆ yang berasal dari parametrik LP (2.1) adalah layak. Penulis dapat sekaligus mencari nilai x˜ yang layak untuk pˆ. Dengan menggunakan pasangan (ˆ x, sˆ) di persamaan (2.6) untuk pˆ. Sejak nilai solusi optimal di persamaan (2.6) adalah tidak negatif, pasangan (ˆ x, sˆ) adalah optimal untuk pˆ, atau persamaan (2.6) memiliki solusi optimal nol untuk pˆ. 3. Sejak perumusan nilai solusi optimal dari parametrik tambahan LP tidak negatif, itu akan memenuhi hasil yang akan digunakan selanjutnya.

Berdasarkan sifat yang ditunjukkan di proposisi 1 ketika daerah tidak layak persamaan (2.1) ditemukan untuk beberapa nilai parameter p¯, permasalahan kendala (2.6) diselesaikan di p¯ dan kemudian daerah layak dan daerah optimal dapat ditentukan menggunakan kendala ini, didalam analogi bagian sebelumnya. Untuk nilai parameter yang nilai basisnya tergantung pada optimalnya, sisa p¯ untuk persamaan (2.6), permasalahan asal (2.1) menjadi tidak layak.


25 Note bahwa jika beberapa nilai parameter dari basis tersebut tidak layak atau suboptimal, ini tidak langsung menunjukkan kelayakan dari persamaan (2.1), tetapi lebih kepada menunjukkan algoritma 0, ketika nilai basis yang ada di dalam permasalahan tambahan menjadi tidak layak atau suboptimal permasalahan utamanya perlu diselesaikan.

2.7 Terminasi Algoritma Teorema 1. Berdasarkan asumsi 2.1, 2.2, dan 2.3, algoritma 0 terhenti terbatas. Di terminasi R mengandung sebuah perkiraan solusi untuk parameter LP. Untuk g Rl = benar, sebuah basis dari persamaan (2.1) dan sebuah point yang berhubungan xRl (p) diberikan, untuk memenuhi kendala primal dan marginal tanpa toleransi εinf − dan εopt− berturut turut untuk p ∈ [pRl , pRl+1 ]. Untuk g Rl = Salah, ketidaklayakan (perkiraan) dapat terjadi dengan p ∈ [pRl , pRl+1 ] dengan menggunakan persamaan dari basis persamaan (2.6) yang memenuhi kendala primal dan marginal dengan toleransi εinf − dan εopt− berturut-turut. Bukti Asumsi 2.1 memenuhi kehadirsan solusi optima. Asumsi 2.2 mengizinkan penggunaan faktorisasi LU yang berdasarkan kepada operasi rasional. Akhirnya asumsi 2.3, bahwa memenuhi nilai basis yang dapat diinverskan di daerah layak yang menjadi luas (luasan) dan meskipun pertidaksamaan primal dan marginal tidak mendekati nilai optimal. Permasalahan primal dan marginal dari persamaan (2.1) dan (2.6) dipenuhi dengan kontruksi pembangun subpermasalahan. Itu dapat mendekat hasil dari terminasi terbatas. Penulis melakukan perhitungan dengan menunjukkan kehadiran δp maka tidak ada jalur kembali yang dibutuhkan dan algoritma 0 menghasilkan langkah positif di interval parameter [pt, pu ]disetiap iterasi. Untuk kesederhanaan penulis menyelesaikan persamaan (2.1) dan (2.6) tanpa tujuan.


26 Misalkan persamaan (2.1) dan (2.6) dapat diselesaikan untuk p = po dan sebuah basis optimal telah ditemukan. Dengan menggunakan definisi dari sebuah basis, untuk determinan p = po dari basis adalah tidak nol dan kendala primal dan marginal telah memenuhi. Sejak elemen matriks adalah kontinu, determinan dari basis juga merupakan fungsi kontinu dari p. Penulis dapat menentukan sebuah daerah hasil parameter p1 = [p1l , p1u ] dengan p1l ≤ po ≤ p1u untuk yang determinan matriksnya tidak nol, meskipun basis program linear dari matriks non singular dan dapat diinversekan. Variabel basis program linear dan nilai basis program linear adalah fungsi rasional p dan kontinu tanpa p1 . Sebagai konsekuensinya penulis dapat menentukan sebuah daerah hasil dari parameter p2 = [p2l, p2u ] dengan p1l ≤ p2l ≤ p0 ≤ p2u ≤ p1u untuk semua basis program linear tidak berubah akibat kondisi variabel pertidaksamaan basis primal dan marginal dengan menggunakan toleransi yang lebih spesifik. Tetapi dengan nilai basis yang diberikan, penulis dapat menemukan δpmin > 0 dimana jika nilai basis optimal untuk p0 itu juga menyebabkan εoptimal di [p0 − δpmin, p0 + δpmin]. Himpunan yang menjadi host dari p juga mengalami perubahan dan meskipun kekontinuitasan menyebabkan keseragaman sifat kontinu dan memberikan δpmin > 0 dan dapat ditemukan sifat tidak tergantung terhadap p0 . Selanjutnya, sejak ada sebuah basis yang terbatas δpmin > 0 dapat ditentukan tidak tergantung dengan basis yang diberikan. Setelah semua angka terbatas didapat dari iterasi δp memberikan efek yang sangat kecil dan tidak ada jalur kembali jika diperlukan. Lebih lanjut lagi, setiap iterasi bukan langkah 0, di ambil langkah yang maju. Sejak [pt, pu ] di batasi, dan setiap iterasi bukan langkah nol diambil langkah tersebut diambil sampai semua [pt , pu ] diselesaikan. Remark 2.3. Jika salah satu tidak mengizinkan εvioliation dari kendala primal dan dual, ketergantungan linear dari kendala dapat memberikan hasil di salah satu kualifikasi solusi invarian dapat menjadi optimal untuk sebuah nilai parameter. Di kasus ini, algoritma algoritma yang dibutuhkan haruslah dimodifikasi dan lebih elaborasi dengan argument untuk terminasi terbatas yang dibutuhkan.


27 Penggunaan dari presisi terbatas menyebabkan keselarasan dari penggunaan toleransi. Lebih lanjut lagi LP solver memberikan solusi optimal yang diperkirakan, dapat memenuhi toleransi yang sejenis. Meskipun toleransi yang digunakan dalam algoritma ini membutuhkan nilai yang lebih besar dari pada yang digunakan oleh LP solver.


BAB 2 TINJAUAN PUSTAKA

Recommend Documents