Penyelesaian Dasar Sistem Persamaan Linier Riset Operasional

Slide1Penyelesaian DasarSistem Persamaan Linier Riset Operasional Pertemuan 10 Vivi Tri Widyaningrum,S.Kom, MT

Slide2Pendahuluan Dalam pembahasan sebelumnya telah dijelaskan tentang Program Linier yang diselesaikan dengan metode grafik dan juga dengan metode matriks.  Program linier merupakan salah satu teknik penyelesaian riset operasi dalam hal ini adalah khusus menyelesaikan masalah-masalah optimasi (memaksimalkan atau meminimumkan) tetapi hanya terbatas pada masalah- masalah yang dapat diubah menjadi fungsi linier. Demikian pula kendala-kendala yang ada juga berbentuk linier.  Untuk menyelesaikan Persoalan Program Linier dengan Metode Simpleks untuk fungsi tujuan memaksimumkan dan meminimumkan caranya berbeda sehingga dalam pertemuan ini akan dijelaskan tentang masalah ini.

Slide3Metode Simpleks Kasus MaksimumBerikut ini langkah-langkah penyelesaian Persoalan Program Linier fungsi tujuan memaksimumkan dengan Metode Simpleks. 1.    Mengubah semua kendala ke  Bentuk Kanonik  (yang semula menggunakan tanda pertidaksamaan menjadi persamaan) dengan menambah perubah (variabel)  Slack S.  Perubah- perubah slack yang ada dimasukkan (ditambahkan) ke fungsi sasaran dan  diberi koefisien 0 . 2.   Apakah dalam matriks A = [a ij ] (pada fungsi kendala) sudah terbentuk Matriks Identitas (In) ? 2.1 Apabila dalam matriks A sudah terbentuk Matriks Identitas maka disusun tabel awal simpleks sebagai berikut :

Slide4Lanjutan…Keterangan :  Baris C j  diisi dengan para koefisien Fungsi Tujuan (sasaran)  Baris X j  diisi dengan nama-nama perubah (variabel) yang ada.  Kolom X i  diisi dengan nama-nama perubah yang menjadi basis (variabel yang menyusun matriks Identitas) .  Kolom C i  diisi dengan para koefisien perubah yang menjadi basis  Kolom b i  diisi dengan para konstanta fungsi kendala (Nilai Sebelah Kanan/ NSK).  Baris Z j  diisi dengan rumus  Kolom R i  diisi dengan rumus (a ik  = elemen-elemen yang berada dalam kolom kunci, dan R i  dihitung hanya untuk a ik  ≥  0) Selanjutnya dilanjutkan ke langkah 3,

Slide52.2 jika belum terbentuk matriks identitas, maka matriksidentitas ditimbulkan (dimunculkan) dengan menambah perubah semu  dan diberi notasi ( V ). Perubah semu yang ada dimasukan di fungsi sasaran, sedangkan koefisien dari variabel semu pada fungsi sasaran diberi nilai (-M), dengan M adalah bilangan yang cukup besar. Dilanjutkan ke langkah 2.1. 3. Penelitian terhadap nilai Z j  - C j . (Tabel sudah maksimum jika semua Z j  - C j   ≥  0). 3.1 Jika untuk semua Z j  - C j   ≥  0 dilanjutkan ke langkah 4, 3.2 Jika ada Z j  - C j  < 0, maka dibuat tabel baru dengan cara sbb : 3.2.1 Menentukan kolom kunci yaitu memilih nilai Z j  - C j  yang terkecil (Min{ Z j  - C j }. Sebut dengan Z k  - C k  maka kolom ke-k disebut  kolom kunci. 3.2.2 Pada kolom ke-k dilakukan pemeriksaan terhadap nilai a ik .           3.2.2.1 Jika untuk semua a ik  negatif maka  jawab tidak terbatas (Unbounded) . Lanjutan…

Slide6         3.2.2.2 Jika terdapat aik  yang positif hitung nilai R i , (untuk a ik  yang positif saja) kemudian dilanjutkan ke langkah 3.2.3, 3.2.3 Menentukan baris kunci, yaitu dengan memilih nilai R i yang terkecil (diantara yang positif) Min{ R i }, namakan R r , maka baris ke-r disebut  baris kunci. 3.2.4 Kemudian disusun tabel baru sebagai berikut (dimulai dari baris kunci baru):          3.2.4.1 Untuk elemen baris r baru = elemen baris r lama dibagi a rk  , atau          3.2.4.2 Untuk elemen baris i yang lain, elemen baris i baru = elemen baris i lama -         (a ik  x elemen baris r baru) Kemudian tentukan lagi nilai X i , C i , Z j  , Z j -C j . Kembali ke langkah 3 . Lanjutan…

Slide7Lanjutan…4.  Apakah pada tabel terakhir terdapat nilai  V k  yang positif ? 4.1 Jika ada nilai  V k  yang positif maka  soal asli tidak fisibel (Infeasible Solution). 4.2 Jika tidak ada nilai  V k  yang positif maka akan diperoleh penyelesaian yang maksimum.

Slide8Contoh :Max : Z = 3 X 1  + 3X 2  (dalam ribuan) Yang memenuhi kendala : 1). 2 X 1  + X 2   ≤  30 2). 2 X 1  + 3X 2   ≤  60 3). 4 X 1  + 3X 2   ≤  72 4). X 1   ≥  0, X 2   ≥  0.

Slide9Penyelesian :Bentuk kanonik : 1). 2 X 1  + 1 X 2  + 1 S 1  + 0 S 2  + 0 S 3  = 30 2). 2 X 1  + 3 X 2  + 0 S 1  + 1 S 2  + 0 S 3  = 60 3). 4 X 1  + 3 X 2  + 0 S 1  + 0 S 2  + 1 S 3  = 72 Dan fungsi tujuannya menjadi : Max Z = 3  X 1  + 3  X 2  + 0 S 1  + 0 S 2  +0 S 3

Slide10Lanjutan…Bentuk matriksnya adalah sebagai berikut :  Tabel awal simpleks :

Slide11Lanjutan… Menentukan kolom kunci dengan memilih nilai dari min {Z j - C j }, yaitu pada kolom-1 dan 2 yang nilainya adalah -3 (dapat dipilih salah 1). Dipilih kolom ke-2 sebagai kolom kunci, sehingga k = 2. Karena elemen-elemen dalam kolom kunci ada tidak semuanya nol (ada yang positif) maka dapat ditentukan nilai dari R i  yaitu :  Menentukan baris kunci dengan memilih nilai dari R i  yang terkecil dan nilai a ik  > 0 (positif). Terdapat pada baris yang ke-2 yaitu R 2 =20, sehingga r = 2

Slide12Lanjutan… Membuat tabel baru sebagai berikut : Baris kunci baru (baris 2 yang baru) mempunyai elemen- elemen : Atau elemen-elemen baris 2 baru = elemen-elemen baris 2 lama dibagi dengan 3

Slide13Lanjutan…Untuk baris yang lain (baris ke-1 & 3)    â ij  = a ij  - (a ik  x â rj ) Atau dengan cara lain sebagai berikut : Elemen-elemen baris 1 baru = elemen-elemen baris 1 lama – (a 12  x â 2j )

Slide14Lanjutan…Elemen-elemen baris 3 baru = elemen-elemen baris 3 lama – (a 32  x â 2j ) Sehingga tabel dihasilkan tabel baru sebagai berikut:

Slide15Lanjutan… Karena nilai dari Z j  - C j  masih ada yang negatif maka tabel belum maksimum, sehingga harus ditentukan kolom kunci, baris kunci dan perhitungan untuk menyusun tabel baru seperti langkah diatas, dan diperoleh tabel baru sebagai berikut :  Karena semua nilai dari Z j  - C j   ≥  0 maka tabel sudah maksimum dengan nilai dari X 1   = 6 dan X 2  = 16 dan Zmaks adalah 66.

Slide16Lanjutan…Sehingga hasil akhir dari tabel simpleks persoalan di atas adalah sebagai berikut:

Slide17Metode Simpleks Kasus MinimumBerikut ini langkah-langkah penyelesaian Persoalan Program Linier fungsi tujuan meminimumkan dengan Metode Simpleks. 1. Mengubah semua kendala ke  Bentuk Kanonik Simpleks  (yang semula menggunakan tanda pertidaksamaan menjadi persamaan) dengan menambah perubah (variabel)  Slack S.  Perubah-perubah slack yang ada dimasukkan (ditambahkan) ke fungsi sasaran &  diberi koefisien 0 . 2. Apakah dalam matriks A = [a ij ] (pada fungsi kendala) sudah terbentuk Matriks Identitas (In) ? 2.1 Apabila dalam matriks A sudah terbentuk Matriks Identitas maka disusun tabel awal simpleks sebagai berikut :

Slide18Lanjutan…Keterangan tabel :  Baris C j  diisi dengan para koefisien Fungsi Tujuan (sasaran)  Baris X j  diisi dengan nama-nama perubah (variabel) yang ada.  Kolom X i  diisi dengan nama-nama perubah yang menjadi basis (variabel yang menyusun matriks Identitas) .  Kolom C i  diisi dengan para koefisien perubah yang menjadi basis  Kolom b i  diisi dengan para konstanta fungsi kendala (Nilai Sebelah Kanan/NSK).  Baris Z j  diisi dengan rumus  Kolom R i  diisi dengan rumus (a ik  = elemen 2  yang berada dalam kolom kunci, & R i  dihitung hanya untuk a ik  ≥  0) Selanjutnya dilanjutkan ke langkah 3,

Slide19Lanjutan…2.2 Jika belum terbentuk matriks identitas (In) , maka matriks identitas ditimbulkan (dimunculkan) dengan menambah  perubah semu  dan diberi notasi ( V ). Perubah semu yang ada dimasukan di fungsi sasaran, sedangkan koefisien dari variabel semu pada fungsi sasaran diberi nilai (+M), dengan M adalah bilangan yang cukup besar. Dilanjutkan ke langkah 2.1 3. Penelitian terhadap nilai Z j  - C j . (Tabel sudah minimum jika semua Z j  - C j   ≤  0). 3.1 Jika untuk semua Z j  - C j   ≤  0 dilanjutkan ke langkah 4, 3.2 Jika ada Z j  - C j  > 0 (positif), maka dibuat tabel baru dengan cara sebagai berikut : 3.2.1 Menentukan kolom kunci yaitu memilih nilai Z j  - C j  yang terbesar yaitu (Max{ Z j  - C j }. Sebut dengan Z k  - C k  maka kolom ke-k disebut  kolom kunci. 3.2.2 Pada kolom ke-k dilakukan pemeriksaan terhadap nilai a ik .

Slide203.2.2.1 Jika untuk semua aik  negatif (a ik  < 0) maka jawab tidak terbatas (Nilai Fungsi Tujuan tidak terbatas)/(Unbounded) . 3.2.2.2 Jika terdapat a ik  yang positif hitung nilai R i , (untuk a ik  yang positif saja) kemudian dilanjutkan ke langkah 3.2.3, 3.2.3 Menentukan baris kunci, yaitu dengan memilih nilai R i yang terkecil (diantara yang positif) Min{R i }, namakan R r , maka baris ke-r disebut  baris kunci. 3.2.4 Kemudian disusun tabel baru sebagai berikut (dimulai dari baris kunci baru): 3.2.4.1 Untuk elemen baris r baru = elemen baris r lama dibagi a rk  , atau Lanjutan…

Slide213.2.4.2 Untuk elemen baris i yang lain,elemen baris i  baru = elemen baris i lama - (a ik  x elemen baris r baru)  atau Kemudian tentukan lagi nilai X i , C i , Z j , Z j -C j . Kembali ke langkah 3 . 4. Apakah pada tabel terakhir terdapat nilai  V k  yang positif ? 4.1 Jika ada nilai  V k  yang positif maka  soal asli tidak fisibel (Infeasible Solution). 4.2 Jika tidak ada nilai  V k  yang positif maka akan diperoleh penyelesaian yang minimum. Lanjutan…

Slide22Jadi langkah-langkah Metode Simpleks KasusMeminimumkan hampir sama dengan kasus Maksimum, hanya ada beberapa perbedaaan yaitu :  Pengubahan bentuk kanonik, koefisien dari peubah (variabel) semu (V) pada fungsi sasaran adalah +M (positif M) dimana M bilangan yang sangat besar.  Tabel sudah minimum jika semua nilai dari Z j  -C j   ≤   0.  Penentuan kolom kunci berdasarkan nilai dari Z j  -C j  yang paling besar yaitu (maks {Z j  - C j  }). Lanjutan…

Slide23Contoh :Min : Z = 40 X 1  + 80 X 2 Dengan syarat ikatan : a).  X 1  +  X 2   ≥   4 b).  X 1  + 3 X 2   ≥   6 c).  X 1   ≥   0,  X 2   ≥   0

Slide24Penyelesian :Bentuk kanonik :   X 1  +  X 2  - 1 S 1  + 0 S 2  + 1  V 1  + 0 V 2  = 4   X 1  + 3  X 2  + 0 S 1  - 1 S 2  + 0  V 1  + 1 V 2  = 6 Meminimumkan : Z = 40  X 1  + 80  X 2  + 0 S 1  + 0 S 2  + M V 1  + M V 2

Slide25Lanjutan…Tabel simpleks : Karena semua Z j  – C j   ≤  0, maka tabel sudah minimal, dengan nilai X 1  =  3 , dan X 2  =  1 , dan  Zminimalnya =  200 .

Slide26PenutupMetode Simpleks Kasus Meminimumkan hampir sama dengan kasus Maksimum, beberapa perbedaaan langkah- langkah yaitu :  Pengubahan bentuk kanonik, koefisien dari peubah (variabel) semu (V) pada fungsi sasaran adalah +M (positif M) dimana M bilangan yang sangat besar.  Tabel sudah minimum jika semua nilai dari Z j  -C j   ≤   0.  Penentuan kolom kunci berdasarkan nilai dari Z j  -C j  yang paling besar yaitu (maks {Z j  - C j  }).

Slide27Tugas1. Max  Z = 2 X 1  + X 2 Fungsi Kendala : a. X 1  + 2 X 2   ≤  80 b. 3X 1  + 2 X 2   ≤  120 c. 2X 1   ≤  360 dan X 1   ≥  0, X 2   ≥  0. 2. Max  Z = 2 X 1  + 3X 2 Fungsi Kendala : a. 5X 1  + 6X 2   ≤  60 b. X 1  + 2X 2   ≤  16 c. X 1   ≤  10 d. X 2   ≤  6, dan X 1   ≥  0, X 2   ≥  0. 3. Min F = 22 X 1  + 6 X 2 Fungsi Kendala : a. 11X 1  + 3X 2   ≥   33 b. 8X 1  + 5X 2   ≤   40 c. 7X 1  + 10X 2   ≤   70 dan X 1   ≥   0, X 2   ≥   0,