Jumat, 14 Januari 2022

[menuju akhir]

Soal 2 tugas UAS Optimasi 
Referensi : Skripsi harni Ulfiana, Universitas Negeri Semarang 2009

OPTIMASI JARINGAN LISTRIK DENGAN ALGORITMA PRIM DAN APLIKASI PROGRAM MATLAB 


1. Tujuan [kembali]
Mampu memecahkan kasus terkait perancangan optimasi

1. ALgoritma Prim
Persoalan pohon rentang minimum merupakan variasi dari persoalan rute terpendek yang perbedaannya terletak pada lintasan yang dicari. 
    Salah satu metode untuk mencari pohon rentang minimum ditemukan oleh Robert C. Prim. Metode ini disebut algoritma Prim. Algoritma Prim membentuk pohon rentang minimum dengan langkah per langkah. Pada setiap langkah kita mengambil sisi graf G yang memiliki bobot minimum namun yang terhubung dengan pohon rentang T yang telah terbentuk.
Secara formal algoritma Prim adalah sebagai berikut: 
0. Inisialisasi: mula-mula T adalah graf kosong. 
1. Ambil sembarang v∈V(G). Masukkan v ke dalam V(T). 
2. V(G) = V(G) – {v}. 
3. Untuk i = 1, 2, ..., n-1, lakukan: 
a. Pilihlah garis e ∈ E(G) dan e ∉E(T) dengan syarat: 
  i.e berhubungan dengan satu titik dalam T dan tidak membentuk siklus.
  ii.e mempunyai bobot terkecil dibandingkan dengan semua garis yang berhubungan dengan titik-titik dalam T, misalkan w adalah titik ujung e yang tidak berada dalam T. 
b. Tambahkan e ke E(T) dan w ke V(T)
c. V(G) = V (G) – {w}

2. MATLAB


MATLAB adalah sebuah lingkungan komputasi numerikal dan bahasa pemrograman komputer generasi keempat. Dikembangkan oleh The MathWorks, MATLAB memungkinkan manipulasi matriks, pem-plot-an fungsi dan data, implementasi algoritme, pembuatan antarmuka pengguna, dan peng-antarmuka-an dengan program dalam bahasa lainnya.

Mencari pohon rentang minimum termasuk ke dalam masalah optimasi yaitu mencari total jarak minimum sedemikian hingga semua titik dalam jaringan tersebut terhubung dan tidak membentuk siklus.

Di dalam MATLAB terdapat fungsi untuk menyelesaikan masalah program 0-1 yaitu fungsi bintprog, dengan formatnya

min f(x) 

st A(x) ≤ b 

Aeq(x) = beq  

Sintaksnya adalah sebagai berikut. 

x = bintprog (f, A, b) atau 

x = bintprog (f, A, b, Ae, be)

Untuk menentukan pohon rentang minimum dengan algoritma Prim langkah-langkah yang dilakukan adalah sebagai berikut.

1. Memiliah A1 sebagai titik awal sehingga V(T) = {A1} dan E(T)={}

2. (iterasi pertama) A1 sisi X1 maka ditambahkan X1 ke E(T) dan tambahkan titik ujung X1 yaitu A2 ke V(T).  


3. (iterasi kedua) memilih V(T) berbobot kecil titik-titik di V(T) adalah X2 (dengan bobot 189) dan X17 (dengan bobot 207). Sisi dengan bobot terkecil dan tidak membentuk siklus adalah X2. Tambahkan X2 ke E(T) dan titik ujung X2 ke V(T) yaitu A3. Sehingga V(T) = {A1, A2, A3} dan E(T) = {X1, X2}.

4. (iterasi ketiga) pilih sisi yang berhubungan dengan titik di V(T) dengan bobot terkecil dan tidak membentuk siklus

tabel 1. Tabel iterasi pencarían pohon rentang mínimum dari jaringan distribusi listrik PLN Kota Pekalongan wilayah distribusi Pekalongan 1 dengan algoritma Prim

model matematika berdasarkan permasalahan tersebut adalah

X1 : sisi dari titik A1 ke A2, 

X2 : sisi dari titik A2 ke A3, 

X3 : sisi dari titik A3 ke A4, 

X4 : sisi dari titik A4 ke A5, 

X5 : sisi dari titik A5 ke A6, 

X6 : sisi dari titik A6 ke A7, 

X7 : sisi dari titik A7 ke A8, 

X8 : sisi dari titik A8 ke A9, 

X9 : sisi dari titik A9 ke A10, 

X10 : sisi dari titik A10 ke A11, 

X11 : sisi dari titik A11 ke A12, 

X12 : sisi dari titik A12 ke A13,

X13 : sisi dari titik A13 ke A14, 

X14 : sisi dari titik A14 ke A15,

 X15 : sisi dari titik A15 ke A16, 

X16 : sisi dari titik A16 ke A17, 

X17 : sisi dari titik A2 ke A18, 

X18 : sisi dari titik A18 ke A19, 

X19 : sisi dari titik A19 ke A20, 

X20 : sisi dari titik A20 ke A21, 

X21 : sisi dari titik A21 ke A22, 

X22 : sisi dari titik A22 ke A23,

 X23 : sisi dari titik A23 ke A24, 

X24 : sisi dari titik A24 ke A25, 

X25 : sisi dari titik A25 ke A26, 

X26 : sisi dari titik A26 ke A27, 

X27 : sisi dari titik A27 ke A28, 

X28 : sisi dari titik A28 ke A29, 

X29 : sisi dari titik A29 ke A30, 

X30 : sisi dari titik A30 ke A31, 

X31 : sisi dari titik A31 ke A32, 

X32 : sisi dari titik A32 ke A7, 

X33 : sisi dari titik A19 ke A33, 

X34 : sisi dari titik A33 ke A34, 

X35 : sisi dari titik A34 ke A35, 

X36 : sisi dari titik A35 ke A31, 

X37 : sisi dari titik A21 ke A36, 

X38 : sisi dari titik A36 ke A37,

X39 : sisi dari titikA37 ke A27, 

X40 : sisi dari titik A37 ke A24, X41 : sisi dari titik A3 ke A38, X42 : sisi dari titik A38 ke A39, X43 : sisi dari titik A39 ke A40, X44 : sisi dari titik A40 ke A41 X45 : sisi dari titik A41 ke A42, X46 : sisi dari titik A7 ke A43, X47 : sisi dari titik A43 ke A44, X48 : sisi dari titik A44 ke A45, X49 : sisi dari titik A45 ke A46, X50 : sisi dari titik A46 ke A47, X51 : sisi dari titik A47 ke A48, X52 : sisi dari titik A48 ke A49, X53 : sisi dari titik A49 ke A50, X54 : sisi dari titik A50 ke A51, X55 : sisi dari titik A51 ke A52, X56 : sisi dari titik A52 ke A53, X57 : sisi dari titik A53 ke A54, X58 : sisi dari titik A54 ke A55, X59 : sisi dari titik A55 ke A11, X60 : sisi dari titik A11 ke A56, X61 : sisi dari titik A56 ke A57, X62 : sisi dari titik A57 ke A58, X63 : sisi dari titik A58 ke A28, X64 : sisi dari titik A59 ke A60, X65 : sisi dari titik A60 ke A30, X66 : sisi dari titik A8 ke A60, X67 : sisi dari titik A60 ke A58, X68 : sisi dari titik A9 ke A59, X69 : sisi dari titik A59 ke A57, X70 : sisi dari titik A43 ke A61, X71 : sisi dari titik A61 ke A62, X72 : sisi dari titik A62 ke A63, X73 : sisi dari titik A63 ke A64, X74 : sisi dari titik A64 ke A65, X75 : sisi dari titik A65 ke A66, X76 : sisi dari titik A46 ke A61, X77 : sisi dari titik A47 ke A62, X78 : sisi dari titik A62 ke A8, X79 : sisi dari titik A63 ke A67, X80 : sisi dari titik A67 ke A68, X81 : sisi dari titik A68 ke A69, X82 : sisi dari titik A64 ke A70, X83 : sisi dari titik A70 ke A71, X84 : sisi dari titik A65 ke A72, X85 : sisi dari titik A72 ke A73, X86 : sisi dari titik A49 ke A66, X87 : sisi dari titik A66 ke A10, X88 : sisi dari titik A54 ke A74, X89 : sisi dari titik A74 ke A75, X90 : sisi dari titik A75 ke A76, X91 : sisi dari titik A76 ke A77, X92 : sisi dari titik A77 ke A78, X93 : sisi dari titik A78 ke A79, X94 : sisi dari titik A54 ke A80, X95 : sisi dari titik A80 ke A81, X96 : sisi dari titik A81 ke A12, X97 : sisi dari titik A81 ke A82, X98 : sisi dari titik A82 ke A83, X99 : sisi dari titik A83 ke A84, X100 : sisi dari titik A84 ke A85, X101 : sisi dari titik A85 ke A86, X102 : sisi dari titik A85 ke A17, X103 : sisi dari titik A84 ke A16, X104 : sisi dari titik A83 ke A87, X105 : sisi dari titik A82 ke A76, X106 : sisi dari titik A82 ke A14, X107 : sisi dari titik A14 ke A88, X108 : sisi dari titik A88 ke A89, X109 : sisi dari titik A89 ke A90, X110 : sisi dari titik A15 ke A88, dan X111 : sisi dari titik A16 ke A89

Fungsi tujuan : 

MINIMUMKAN 90X1 + 189X2 + 42X3 + 175X4 + 42X5 + 154X6 + 231X7 + 158X8 + 270X9 + 154X10 + 121X11 + 47X12 + 180X13 + 198X14 + 186X15 + 204X16 + 207X17 + 63X18 + 72X19 + 180X20 + 117X21 + 144X22 + 90X23 + 90X24 + 261X25 + 161X26 + 112X27 + 56X28 + 57X29 + 154X30 + 77X31 + 144X32 + 171X33 + 153X34 + 117X35 + 182X36 + 117X37 + 36X38 + 369X39 + 189X40 + 108X41 + 189X42 + 126X43 + 90X44 + 63X45 + 91X46 + 98X47 + 217X48 + 112X49 + 84X50 + 98X51 + 256X52 + 209X53 + 55X54 + 165X55 + 115X56 + 120X57 + 94X58 + 171X59 + 187X60 + 228X61 + 204X62 + 190X63 + 167X64 + 217X65 + 245X66 + 252X67 + 198X68 + 278X69 + 126X70 + 140X71 + 85X72 + 138X73 + 99X74 + 94X75 + 224X76 + 252X77 + 133X78 + 39X79 + 44X80 + 85X81 + 39X82 + 116X83 + 50X84 + 66X85 + 457X86 + 105X87 + 130X88 + 35X89 + 160X90 + 85X91 + 120X92 + 170X93 + 94X94 + 149X95 + 116X96 + 245X97 + 372X98 + 122X99 + 192X100 + 289X101 + 192X102 + 216X103 + 321X104 + 187X105 + 249X106 + 162X107 + 192X108 + 222X109 + 90X110 + 102X111


Fungsi kendala:


X1 = 1 

X41 + X42 + X43 + X44 + X45 = 5 

X79 + X80 + X81 = 3 

X82 + X83 = 2 

X84 + X85 = 2 

X91 + X92 + X93 = 3 

X101 = 1 

X104 = 1 

X109 = 1 

X1 + X2 + X3 + X4 + X5 + X6 + X7 + X8 + X9 + X10 + X11 + X12 + X13 + X14 + X15 + X16 + X17 + X18 + X19 + X20 + X21 + X22 + X23 + X24 + X25 + X26 + X27 + X28 + X29 + X30 + X31 + X32 + X33 + X34 + X35 + X36 + X37 + X38 + X39 + X40 + X41 + X42 + X43 + X44 + X45 + X46 + X47 + X48 + X49 + X50 + X51 + X52 + X53 + X54 + X55 + X56 + X57 + X58 + X59 + X60 + X61 + X62 + X63 + X64 + X65 + X66 + X67 + X68 + X69 + X70 + X71 + X72 + X73 + X74 + X75 + X76 + X77 + X78 + X79 + X80 + X81 + X82 + X83 + X84 + X85 + X86 + X87 + X88 + X89 + X90 + X91 + X92 + X93 + X94 + X95 + X96 + X97 + X98 + X99 + X100 + X101 + X102 + X103 + X104 + X105 + X106 + X107 + X108 + X109 + X110 + X111 = 89

X2 + X3 + X4 + X5 + X6 + X17 + X18 + X31 + X32 + X33 + X34 + X35 + X36 ≤ 12 

X19 + X20 + X27 + X28 + X29 + X30 + X33 + X34 + X35 + X36 + X37 + X38 + X39 ≤12 

X21 + X22 + X23 + X37 + X38 + X40 ≤ 5 X24 + X25 + X26 + X39 + X40 ≤ 4 X47 + X48 + X49 + X70 + X77 ≤ 4 X50 + X71 + X77 + X78 ≤ 3 

X51 + X52 + X72 + X73 + X74 + X75 + X78 + X86 ≤ 7 

X7 + X46 + X70 + X71 + X76 ≤ 4

 X8 + X9 + X72 + X73 + X74 + X75 + X76 + X87 ≤ 7 

X10 + X53 + X54 + X55 + X56 + X57 + X58 + X59 + X86 + X87 ≤ 9

 X7 + X30 + X31 + X32 + X65 + X66 ≤ 5 

X8 + X64 + X66 + X68 ≤ 3 

X28 + X29 + X63 + X65 + X67 ≤ 4 

X62 + X64 + X67 + X69 ≤ 3 

X9 + X10 + X60 + X61 + X68 + X69 ≤ 5 

X11 + X58 + X59 + X94 + X95 + X96 ≤ 5 

X88 + X89 + X90 + X94 + X95 + X97 + X105 ≤ 6 

X12 + X13 + X96 + X97 + X106 ≤ 4

 X14 + X15 + X98 + X99 + X103 + X106 ≤ 5 

X16 + X100 + X102 + X103 ≤ 3 

X14 + X107 + X110 ≤ 2 

X15 + X108 + X110 + X111 ≤ 3 

X8 + X30 + X31 + X32 + X46 + X64 + X65 + X68 + X70 + X71 + X78 ≤ 10 

Mencari solusi optimum dengan fungsi bintprog. 

Sintaknya adalah [x, fx] = bintprog(f, a, b, ae, be) 

Membaca dan menganalisis hasil yang diperoleh. Sebagian hasil output dapat dilihat pada tabel berikut ini.

 tabel 2. Tabel output program MATLAB

By di Tidak ada komentar:
[menuju akhir]

Soal 1 tugas UAS Optimasi 
Referensi : Optimasi Tak Linear , Oleh Dr. H.A. Parhusip, Penerbit: Tisara Grafika Salatiga (2014)

PENYELESAIAN PERMASALAHAN OPTIMASI NONLINEAR BERKENDALA DENGAN METODE PENGALI LAGRANGE


1. Tujuan [kembali]
Memberi pengetahuan tentang bagaimana cara menyelesaikan masalah optimisasi Program Nonlinear berkendala dengan metode pengali lagrange.

Secara umum masalah optimasi yag berkendala berbentuk:

Dengan kendala:

Untuk menyelesaikannya maka dibentuk fungsi lagrange

Kemudian pecahkan sistem n + m dengan persamaan

dan

Teorema 1.11: untuk masalah (1.10) dapat diselesaikan asalkan f(x) dan gi(x) (i = 1,2,...,m) memiliki turunan parsial pertama yan kontinu dan mariks Jacobi m x n dengan memiliki rank m di 


Metode pengali Lagrange ini ekuivalen dengan menggunakan persamaan kendala untuk menghilangkan beberapa variabel x tertentu dari fungsi obyektif dan kemudian memecahkan persoalan maksimisasi tanpa kendala dalam variabel-variabel x yang tersisa. 

3. Permasalahan [kembali]

Minimalkan dengan metode pengali Langrange untuk masalah fungsi tujuan dengan kendala persamaan,

Mengganti kendala persamaan x2 = 2 - x1, sehingga menjadi optimasi tal terkendala sebagai

maka dapat dengan mudah dipecahkan dengan menetapkan turunan dari hal ini.

atau


 

Gambar 1. Fungsi Obyektif dengan kendala contoh permaslahan


Program MATLAB untuk mengilustrasikan gambar 1 sebagai berikut:

 

clear

close all

[X,Y] = meshgrid(-3:.125:3);

Z = X.^2 + Y.^2;

meshc(X,Y,Z);

hold on

Z2=X + Y-2;

meshc(X,Y,Z2);

hold off

By di Tidak ada komentar:

Selasa, 09 November 2021

Tugas 1 Optimasi

Referensi: Pengantar Optimasi Non Linear Oleh Ir. Djoko Lukmanto, M.Sc., Ph.D., Penerbit: Laboratorium Hidraulika UGM (2000)

[menuju akhir]




  • Mengetahui Metode Optimasi Analitis Satu Variabel Tanpa Kendala.
  • Mengetahui Metode Optimasi Analitis Multi Variabel Tanpa Kendala.
  • Mengetahui Metode Optimasi Analitis Multi Variabel dengan Kendala Persamaan.
  • Mengetahui Metode Optimasi Analitis Multi Variabel dengan Kendala Pertidak-samaan.
Suatu permasalahan optimasi disebut nonlinier jika fungsi tujuan dan kendalanya mempunyai bentuk nonlinier pada salah satu atau keduanya, contohnya adalah sebagai berikut:

Dimisalkan x adalah variabel penentu dan f(x) adalah fungsi tujuan dari suatu masalah. Metode optimasi menyelesaikan masalah:

Untuk menyelesaikan permasalahan seperti tertera di atas digunakan kalkulus diferensial yang dinyatakan seperti di bawah ini:

  • Teorema:

Misalkan f adalah fungsi yang menerus dalam interval tertutup [a,b] dan dapat diderivasikan pada interval terbuka (a,b).

(i) Jika f’(x) > 0 untuk seluruh x dalam (a,b), maka f adalah menanjak pada [a,b].

(ii) Jika f’(x) < 0 untuk seluruh x dalam (a,b), maka f adalah menurun pada [a,b].

  • Test derivasi pertama: 

Misalkan f adalah fungsi yang menerus dalam interval tertutup [a,b] dan dapat diderivasikan pada interval terbuka (a,b) kecuali mungkin di titik c yang berada didalam (a,b).

(i) Jika f’(x) > 0 untuk a < x < c dan f’(x) < 0 untuk c < x < b, maka f(c) adalah sebuah maximum lokal dari f.

(ii) Jika f’(x) < 0 untuk a < x < c dan f’(x) > 0 untuk c < x < b, maka f(c) adalah sebuah minimum lokal dari f.

(iii) Jika f’(x) < 0 atau f’(x) > 0 untuk setiap x dalam (a,b) kecuali x = c, maka f(c) BUKAN sebuah nilai ekstrim.

  • Test derivasi kedua: 

Misalkan f adalah fungsi yang dapat diderivasikan pada interval terbuka yang berisi titik c dan f’(c) = 0,

(i) Jika f”(c) < 0, maka f(c) adalah sebuah maximum lokal dari f.

(ii) Jika f”(c) > 0, maka f(c) adalah sebuah minimum lokal dari f.

Contoh 1:

Sebuah perusahaan catering (makanan ringan yang menyediakan konsumsi untuk suatu penataran di JTE FT UMY) berusaha mengurangi pengeluaran untuk keperluan pembungkus. Bungkus tersebut terbuat dari kertas karton seperti tampak pada Gambar di samping. Keempat pojoknya akan dipotong segi empat samasisi sedemikian rupa sehingga volumenya menjadi maksimum.

Penyelesaian:

volume pembungkus dapat dinyatakan,

derivasi V terhadap x menghasilkan,

Untuk mengetahui volume menjadi maksimum atau minimum, gunakan test derivasi kedua,
Subsitusi x = 3 kepersamaan
jadi V mempunyai nilai maksimum untuk x = 3


  • Teorema:

Misalkan f’(c) = f”(c) = … = f(n-1)(c) = 0, tetapi f(n)(c) ≠ 0. Maka f(c) adalah:

(i) nilai minimum dari f(x), jika f(n)(c) > 0 dan n adalah bilangan genap,

(ii) nilai maximum dari f(x), jika f(n) (c) < 0 dan n adalah bilangan genap,

(iii) bukan minimum dan maximum jika n adalah bilangan gasal.

Secara umum teknik yang digunakan pada optimasi satu dimensi dapat digunakan dalam optimasi multi variabel.

Definisi dan simbol-simbol yang digunakan:

  • Teorema:

Jika f(X) mempunyai sebuah titik ekstrem (minimum maupun maximum) pada X = X* dan jika derivasi pertama dari f(X) mempunyai nilai pada titik X*, maka ∇f(X*) = 0

PERHATIAN: Kebalikannya belum tentu benar yaitu jika ∇f(X*) = 0 maka X* adalah titik ekstrem.

  • Teorema:

Titik X* disebut titik maksimum lokal dari f(X) jika dan hanya jika:

(i) ∇f(X*) = 0

(ii) H(X*) < 0 definit negatif dengan H = matrik Hessian yang didefinisikan sebagai:

  • Teorema:

Titik X* disebut titik minimum lokal dari f(X) jika dan hanya jika:

(i) ∇f(X*) = 0

(ii) H(X*) > 0 definit positif atau |H|j > 0 untuk j = 1,2,…,n, sehingga



Pada bagian ini akan didiskusikan teknik optimasi multi variabel dengan kendala persamaan yang mempunyai bentuk umum sebagai berikut:

disini m ≤ n, jika terjadi bahwa m > n, maka biasanya tidak dapat diselesaikan

Untuk menyelesaikan permasalahan optimasi di atas, digunakan metode pengali Lagrange, yaitu:

  •  Teorema:

Syarat perlu bagi sebuah fungsi f(X) dengan kendala gj(X) = 0, dengan j = 1, 2, …, m agar mempunyai minimum relatif pada titik X* adalah derivasi parsial pertama dari fungsi Lagrangenya yang didefinisikan sebagai L = L(x1,x2,…,xn, λ1,λ2,…,λn) terhadap setiap argumennya mempunyai nilai nol.

  • Teorema:

Syarat harus bagi sebuah fungsi f(X) agar mempunyai minimum (atau maximum) relatif pada titik X* adalah jika fungsi kuadrat, Q, yang didefinisikan sebagai

dievaluasi pada X = X* harus definit positif (atau negatif) untuk setiap nilai dX yang memenuhi semua kendala.

Syarat perlu agarmenjadi definit positif (atau negatif) untuk setiap variasi nilai dX adalah setiap akar dari polinomial, zi, yang didapat dari determinan persamaan di bawah ini harus positif (atau negatif).

Pada bab ini akan didiskusikan teknik optimasi multi variabel dengan kendala pertidak-samaan yang mempunyai bentuk umum sebagai berikut:

Jadi permasalahan optimasi di atas dapat ditulis kembali sebagai:

Permasalahan ini dapat diselesaikan metode pengali Lagrange.

Syarat perlu untuk suatu penyelesaian optimum pers diperoleh dari penyelesaian sistem persamaan di bawah ini.

Syarat perlu agar persamaan optimasi, mencapai titik minimumnya dapat pula dicari dengan syarat Kuhn-Tucker. Untuk problema jenis konvex, syarat Kuhn-Tucker menjadi syarat perlu dan cukup untuk sebuah minimum global.

PERHATIAN:

  • Jika permasalahannya adalah memaksimumkan {bukan meminimumkan seperti contoh}, maka λj ≤ 0 dalam Pers.(1.21d).
  • Jika kendalanya adalah gj ≥ 0, maka λj ≤ 0 dalam Pers.(1.21d).
  • Jika permasalahannya adalah memaksimumkan dan jika kendalanya adalah gj ≥ 0, maka λj ≥ 0 dalam Pers.(1.21d).

6. Video Pengenalan Optimasi [kembali]

Video pengenalan optimasi



Video dengan MATLAB



7. Link Download [kembali]

download file materi di sini
download file video 1 di sini
download file video 2 di sini
download ebook di sini

By di Tidak ada komentar:

Minggu, 07 November 2021

Metode Optimasi Analitis




Metode Optimasi Analitis





Suatu permasalahan optimasi disebut nonlinier jika fungsi tujuan dan kendalanya mempunyai bentuk nonlinier pada salah satu atau keduanya, contohnya adalah sebagai berikut:


Dimisalkan x adalah variabel penentu dan f(x) adalah fungsi tujuan dari suatu masalah. Metode optimasi menyelesaikan masalah:

Untuk menyelesaikan permasalahan seperti tertera di atas digunakan kalkulus diferensial yang dinyatakan seperti di bawah ini:

Misalkan f adalah fungsi yang menerus dalam interval tertutup [a,b] dan dapat diderivasikan pada interval terbuka (a,b).

(i) Jika f’(x) > 0 untuk seluruh x dalam (a,b), maka f adalah menanjak pada [a,b].

(ii) Jika f’(x) < 0 untuk seluruh x dalam (a,b), maka f adalah menurun pada [a,b].

Test derivasi pertama: Misalkan f adalah fungsi yang menerus dalam interval tertutup [a,b] dan dapat diderivasikan pada interval terbuka (a,b) kecuali mungkin di titik c yang berada didalam (a,b).

(i) Jika f’(x) > 0 untuk a < x < c dan f’(x) < 0 untuk c < x < b, maka f(c) adalah sebuah maximum lokal dari f.

(ii) Jika f’(x) < 0 untuk a < x < c dan f’(x) > 0 untuk c < x < b, maka f(c) adalah sebuah minimum lokal dari f.

(iii) Jika f’(x) < 0 atau f’(x) > 0 untuk setiap x dalam (a,b) kecuali x = c, maka f(c) BUKAN sebuah nilai ekstrim.

Test derivasi kedua: Misalkan f adalah fungsi yang dapat diderivasikan pada interval terbuka yang berisi titik c dan f’(c) = 0,

(i) Jika f”(c) < 0, maka f(c) adalah sebuah maximum lokal dari f.

(ii) Jika f”(c) > 0, maka f(c) adalah sebuah minimum lokal dari f.

Contoh 1:

Sebuah perusahaan catering (makanan ringan yang menyediakan konsumsi untuk suatu penataran di JTE FT UMY) berusaha mengurangi pengeluaran untuk keperluan pembungkus. Bungkus tersebut terbuat dari kertas karton seperti tampak pada Gambar di samping. Keempat pojoknya akan dipotong segi empat samasisi sedemikian rupa sehingga volumenya menjadi maksimum.

Dari contoh di atas tampak bahwa dengan cara analitis kalkulus diferensial nilai x yang memberikan nilai f maximum dapat dicari tanpa mengetahui nilai dari f itu sendiri.

Untuk melengkapi teorema optimasi nonlinier satu variabel yang telah dijelaskan di atas disajikan teorema yang dapat digunakan untuk menentukan titik-titik ekstrem dari suatu fungsi satu variabel.

Teorema:

Misalkan f’(c) = f”(c) = … = f(n-1)(c) = 0, tetapi f(n)(c) ≠ 0. Maka f(c) adalah:

(i) nilai minimum dari f(x), jika f(n)(c) > 0 dan n adalah bilangan genap,

(ii) nilai maximum dari f(x), jika f(n) (c) < 0 dan n adalah bilangan genap,

(iii) bukan minimum dan maximum jika n adalah bilangan gasal.

Contoh 2.

Tentukan maximum dan minimum dari fungsi di bawah ini

Penyelesaian:

Cara analitis yang diterapkan pada permasalahan optimasi satu variabel dapat pula diterapkan kepada permasalahan multi variabel.

Secara umum teknik yang digunakan pada optimasi satu dimensi dapat digunakan dalam optimasi multi variabel.

Definisi dan simbol-simbol yang digunakan:

Teorema:

Jika f(X) mempunyai sebuah titik ekstrem (minimum maupun maximum) pada X = X* dan jika derivasi pertama dari f(X) mempunyai nilai pada titik X*, maka ∇f(X*) = 0

PERHATIAN: Kebalikannya belum tentu benar yaitu jika ∇f(X*) = 0 maka X* adalah titik ekstrem.

Teorema:

Titik X* disebut titik maksimum lokal dari f(X) jika dan hanya jika:

(i) ∇f(X*) = 0

(ii) H(X*) < 0 definit negatif dengan H = matrik Hessian yang didefinisikan sebagai:

Teorema:

Titik X* disebut titik minimum lokal dari f(X) jika dan hanya jika:

(i) ∇f(X*) = 0

(ii) H(X*) > 0 definit positif atau |H|j > 0 untuk j = 1,2,…,n, sehingga


Contoh 3:

Tentukan titik-titik ekstrim dari fungsi:


Pada bagian ini akan didiskusikan teknik optimasi multi variabel dengan kendala persamaan yang mempunyai bentuk umum sebagai berikut:

disini m ≤ n, jika terjadi bahwa m > n, maka biasanya tidak dapat diselesaikan

Untuk menyelesaikan permasalahan optimasi di atas, digunakan metode pengali Lagrange, yaitu:

Teorema:

Syarat perlu bagi sebuah fungsi f(X) dengan kendala gj(X) = 0, dengan j = 1, 2, …, m agar mempunyai minimum relatif pada titik X* adalah derivasi parsial pertama dari fungsi Lagrangenya yang didefinisikan sebagai L = L(x1,x2,…,xn, λ1,λ2,…,λn) terhadap setiap argumennya mempunyai nilai nol.

Teorema:

Syarat harus bagi sebuah fungsi f(X) agar mempunyai minimum (atau maximum) relatif pada titik X* adalah jika fungsi kuadrat, Q, yang didefinisikan sebagai

dievaluasi pada X = X* harus definit positif (atau negatif) untuk setiap nilai dX yang memenuhi semua kendala.

Syarat perlu agar

menjadi definit positif (atau negatif) untuk setiap variasi nilai dX adalah setiap akar dari polinomial, zi, yang didapat dari determinan persamaan di bawah ini harus positif (atau negatif).

Contoh 4:

Sebuah perusahaan pelumas ingin membuat kaleng pelumas dari seng. Kaleng berbentuk silinder dengan bahan yang terpakai seluas A0 = 24π. Berapa maximum volume kaleng yang dapat dibuat dari bahan yang tersedia?

Penyelesaian





Pada bab ini akan didiskusikan teknik optimasi multi variabel dengan kendala pertidak-samaan yang mempunyai bentuk umum sebagai berikut:

Kunci dari penanganan permasalahan di atas adalah merubah kendala pertidak-samaan menjadi persamaan dengan menambah variabel slack. Jadi permasalahan optimasi di atas dapat ditulis kembali sebagai:

Permasalahan ini dapat diselesaikan metode pengali Lagrange. Untuk itu, dibentuk fungsi Lagrange sebagai berikut:

Syarat perlu untuk suatu penyelesaian optimum pers diperoleh dari penyelesaian sistem persamaan di bawah ini.

Syarat perlu agar persamaan optimasi, mencapai titik minimumnya dapat pula dicari dengan syarat Kuhn-Tucker. Syarat ini perlu tetapi secara umum bukan merupakan syarat cukup untuk mencapai minimum. Tetapi untuk problema jenis konvex, syarat Kuhn-Tucker menjadi syarat perlu dan cukup untuk sebuah minimum global.

PERHATIAN:

Jika permasalahannya adalah memaksimumkan {bukan meminimumkan seperti contoh}, maka λj ≤ 0 dalam Pers.(1.21d).

Jika kendalanya adalah gj ≥ 0, maka λj ≤ 0 dalam Pers.(1.21d).

Jika permasalahannya adalah memaksimumkan dan jika kendalanya adalah gj ≥ 0, maka λj ≥ 0 dalam Pers.(1.21d).

Contoh 5:

Sebuah perusahaan pembuat komputer mendapat kontrak untuk menyediakan 50 unit komputer pada akhir bulan pertama, 50 unit komputer pada akhir bulan kedua, dan 50 unit komputer pada akhir bulan ketiga. Biaya produksi x buah komputer tiap bulannya adalah x2. Perusahaan ini dapat memproduksi komputer lebih dari yang dipesan dan menyimpannya di gudang untuk diserahkan pada bulan berikutnya. Biaya gudang adalah sebesar 20 satuan harga untuk tiap komputer yang disimpan dari bulan yang lalu kebulan berikutnya. Diandaikan bahwa pada permulaan pesanan di gudang tidak terdapat persediaan komputer. Tentukan jumlah produksi komputer tiap bulannya agar biaya pembuatannya minimum.







By di Tidak ada komentar:
Langganan: Postingan (Atom)