Materi Kuliah Optimasi

Soreee semua. Lagi-lagi kali ini deva berbagi tentang materi kuliah OPTIMASI. Materi ini adalah tugas Deva saat mengikuti kuliah ini. Ada banyak materi kuliah, tugas-tugas, dll yang deva buat, tetapi semua file-file itu hilang total. hanya inilah yang tersisa. padahal kalau dihitung-hitung, materi deva sebelum-sebelumnya sudah tak bisa di hitung dengan jari. buaannyyaaakkk sekali.
Langsung aja eaaa... ini Materinya. mudah-mudahan bermanfaat bagi mereka yang mencari bahan referensi kuliah Optimasi ini.

1.     PROGRAM LINIER

—  Program linier terdiri dari:

a.       Variable; sesuatu yang nilainya tidak diketahui pada permulaan permasalahan optimasi.

b.      Fungsi tujuan (objective function); persamaan matematika yang terdiri dari variable-variable dan menyatakan tujuan (goal) dari permasalahan optimasi yang akan diselesaikan.

c.       Fungsi kendala (constrain function); persamaan matematika yang terbentuk dari kombinasi variable-variable dan menyatakan batasan dari kemungkina penyelesaian optimasi.

d.      Variable bound; variable-variable dalam permasalahan optimasi dibatasi pada nilai-nilai tertentu.

2.     OPTIMASI JARINGAN

1.      Sebuah model jaringan terdiri dari dua buah element utama, yaitu:

a.       Arc, marupakan garis penghubung antar node,

b.      Node, merupakan titik hubung sebuah arc.

2.      Sebuah grafik, merupakan susunan beberapa arc dan node yang saling berhubungan

3.      Sebuah directed graph, merupakan grafik dimana setiap arc memiliki arah tertentu (disimbolkan dengan anak panah)

4.      Sebuah model jaringan merupakan sebuah diagram grafik (biasanya merupakan directed graph)

PERT (Program Evaluation and Review Technique)

            Dua konsep penggunaan PERT

1.      Events (kejadian) : suatu keadaan tertentu yang  terjadi pada suatu saat tertentu

2.      Aktivitas : suatu pekerjaan yang diperlukan untuk menyelesaikan kejadian tertentu

 

Contoh jaringan yang sederhana disajikan dengan PERT

3.     BEBERAPA CONTOH JARINGAN

4.     MASALAH OPTIMASI JARINGAN

Masalah-masalah pada sebuah jaringan yang berhubungan dengan teknik optimasi adalah:

a.       Shortest route, jalur terpendek yang menghubungkan titik asal ke titik tujuan dalam sebuah jaringan

b.      Minimum spanning tree, jalur terpendek yang dapat menghubungkan semua node dalam sebuah jaringan

c.       Maximum flow, kapasitas maksimum sebuah jaringan untuk mengalirkan data dari source node ke sink node

5.     A. FORMULASI MODEL PROGRAM LINIER JARINGAN (1)

Ada tiga buah parameter yang berhubungan dengan setiap arc, yaitu lower bound, upper bound, dan cost per-unit of flow

—  Label untuk setiap arc [l,u,c]

Source dan sink node ditentukan oleh label pada node,

a.       jika memiliki lower dan upper yang sama, maka bentuknya adalah persamaan

b.      Jika memiliki lower dan upper yang berbeda, maka bentuknya adalah pertidaksamaan

Setelah diagram jaringan memiliki label untuk setiap arc dan node, maka diagram tersebut dapat diubah ke dalam bentuk program linier

B. FORMULASI MODEL PROGRAM LINIER JARINGAN (2)

C. FORMULASI MODEL PROGRAM LINIER JARINGAN (3)

Fungsi kendala untuk diagram jaringan dihasilkan dari:

Node A                       : x₁+ x₂+ x₃ ≤ 12

Node B                       : x₄ – x₁ = 0

Node C                       : x₅ – x₂ ≥ -4

Node D                       : -x₃ – x₄ – x₅ = -8

Variable bound dihasilkan dari:

Flow bound arc 2        : x₂ ≤ 6

Flow bound arc 3        : x₃ ≤ 3

Flow bound arc 4        : x₄ ≥ 4

Nonnegative                : x₁, x₂, x₃, x₄, x₅ ≥ 0

Fungsi tujuan dihasilkan dari:

                        minimize (5A – 6C + 2.5x₃ + 3.7x₄ + 0.5x₅)

7. INTEGER PROGRAMMING

Metode Branch and Bound (1)

—  Terdiri dari beberapa sub-permasalahan,  penyelesaian dan analisis keadaan optimal dari setiap sub-permasalahan sampai pada penyelesaian optimal permasalahan utama.

—  Prinsip metode ini adalah:

1.      Dalam penentuan titik optimal x⁽⁰⁾, ada dua keadaan yang terjadi,

a.       Jika x⁽⁰⁾ memenuhi semua kendala, maka titik tersebut merupakan penyelesaian sementara dan sub-permasalahan diabaikan.

b.      Jika x⁽⁰⁾ tidak memenuhi semua kendala, maka pilih salah satu dari variable berikut ini,

c.       Dan tambahkan ke sub-permasalahan yang ada dan dianalisis pada titik “percabangan” tersebut yang diperoleh dengan menambahkan pada fungsi kendala x_i ≤ k untuk cabang yang satu, dan x_i ≥ k+1

Metode Branch and Bound (2)

—  Setelah diperoleh titik penyelesaian sementara x^*, sub-permsalahan yang telah diperoleh sebenarnya dianalisis dengan prosedur berikut ini:

a.       Jika cx^*≤ cx⁽⁰⁾, sub-permasalahan tersebut tidak digunakan lagi, karena tidak menghasilkan nilai penyelesaian yang lebih baik, pilih sub-permasalahan yang lain.

b.      Jika cx^*> cx⁽⁰⁾ dan memenuhi syarat-syarat fungsi kendala secara keseluruhan, x^*  merupakan penyelesaian sementara yang baru menggantikan x⁽⁰⁾ dan sub-permasalahan lainnya dianalisis

c.       Jika cx^*> cx⁽⁰⁾ dan tidak memenuhi syarat-syarat fungsi kendala secara keseluruhan, buatlah percabangan baru sesuai prosedur percabangan.

Metode Branch and Bound (3)

8. OPTIMASI NON-LINIER

Satu variable tanpa kendala (1)

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

2. Untuk menyelesaikan permasalahan seperti tertera di atas digunakan kalkulus diferensial yang dinyatakan seperti di bawah ini:
3. Misalkan f adalah fungsi yang menerus dalam interval tertutup [a,b] dan dapat diderivasikan pada interval terbuka (a,b).

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

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

9. ANALISA NETWOR METODE ALGORITMA DALAM LINIER PROGRAMING

10. ANALISA NETWORK METODE LINEAR PROGRAMMING

 

11. CONTOH SOAL PEMECAHAN RISET OPERASI   (OPTIMASI):

Karena baris ketiga memiliki Penalty terbesar (=14) dan karena C31 = 0  merupakan ongkos terkecil didalam barisnya, maka alokasikan x31 = 5. Dengan demikian, baris 3 dan kolom 1 sudah terpenuhi secara simultan. Dalam hal ini kita bias memilih baris 3 taua kolom 1 yang akan di tandai. Misalkan dipilih kolom 1 untuk ditandai, maka table baru menjadi :

Selanjutnya kita ulangi menghitung penalty. Kita lihat bahwa baris 1 dan kolom 3 mempunya penalty yang sama (= 11), sehingga kembali kita dapat memilih salah satu untuk ditandai.

Misalkan dipilih kolom 3 untuk ditandai, maka alokasikan x23 = 15. Supply untuk baris 2 sekarang menjadi 10.

Dengan menghitung penalty yang baru, diperoleh penalty terbesar untuk baris 2  (= 13), sehingga alokasikan x22 = 10.  Kemudian tandai baris 2. 

Supply yang masih tersedia adalah 15 (Baris 1), sedangkan demand yang belum terpenuhi adalah kolom 2 sebanyak 5 dan kolom 4 sebanyak 10.

Karena tidak ada pilihan lain. Maka alokasikan x12 = 5 dan x14 = 10. Pengisian table selesai dengan solusi fisibel basis awal : x12 = 5, x14 = 10, x22 = 10, x23 = 15, dan x31 = 5.