Metode Simpleks 2

Cara Memperbaiki Pemecahan Dasar Fisibel

•

Misalkan suatu pemecahan dasar yang fisibel dari persoalan linear programming diberikan dengan rumus berikut: XB = B-1 H

•

Nilai fungsi tujuan bisa dicari dengan rumus berikut: Z = CB X B

•

Sebagai suatu tambahan kita anggap bahwa untuk pemecahan dasar ini: Yi = B-1A dan zi. = cBYi diketahui untuk setiap kolom Ai dari A yang tidak berada di matriks B.

•

Kita ingin menyelidiki kemungkinan untuk memperoleh pemecahan dasar fisibel lainnya sekaligus memperbaiki nilai fungsi tujuan Z yaitu membuat lebih kecil atau membuat lebih besar lagi sesuai dengan persoalannya.

•

Untuk persoalan yang minimum kita harus berusaha memperkecil sedangkan untuk persoalan yang maksimum harus diperbesar.

•

Perhatian ditujukan kepada pemecahan dasar yang fisibel di mana hanya satu kolom saja dari B yang berubah, yaitu dengan cara mengeluarkan/menyingkirkan satu kolom B serta menggantinya dengan vektor lain dari A.

•

Untuk hal ini, mudah sekali untuk menentukan apakah suatu set vektor yang baru membentuk suatu basis atau tidak.

•

Kita lihat, bahwa kalau Aj = ∑yijBj, kemudian Aj bias mengganti setiap vektor Br untuk Yrj ≠ 0 (merupakan suatu syarat) dan suatu set vektor yang baru, setelah penggantian masih merupakan suatu basis.

•

Mari kita pilih Aj dari A yang tidak berada di B, dengan satu Yij ≠ 0, kemudian vektor A kita masukkan ke dalam salah satu kolom dari B.

•

Untuk keperluan tersebut, misalnya kita putuskan untuk menyingkirkan atau mengeluarkan kolom ke-r dari B yaitu vektor Br (yrj > 0) serta kita ganti dengan vektor A, maka kemudian:

Aj = y1jB1 + y2jB2 +... + yrjBr +... + ymjBm y rj B r = Aj - y lJ B l - y 2j B 2 -... - y mj B m atau Br =

m y 1 ij Aj − ∑ Bi y rj i =1 y rj i≠r

•

Pemecahan dasar fisibel yang as.li bisa ditulis sebagai berikut:

5

m

∑X i =1

Bi

Bi

•

Variabel x4 dan x5 masing-masing sebagai variabel slack dan surplus.

•

Prices dari variabel x4 dan x5, masing-masing nilainya 0.

•

Bisa kita cek bahwa vektor A1 dan A3 linearly independent dan merupakan suatu basis untuk vektor-vektor berkomponen 2.

•

Vektor-vektor tersebut bisa dipergunakan untuk membentuk suatu pemecahan dasar.

•

Suatu matriks basis B akan kita bentuk dengan memasukkan A3 sebagai kolom pertama dari B dan A l sebagai kolom kedua dari B, yaitu B 1 = A 3 , B 2 = A 1

•

Jadi

•

Pemecahan dasar dengan semua variabel bernilai 0 kecuali x1 dan x3 adalah fisibel dan bisa dengan mempergunakan rumus berikut:

• •

Variabel yang berada di dalam basis ialah xB1 = x3 dan xB2 = x1. Prices yang bersesuaian dengan variabel-variabel tersebut ialah cB] = c3 = 3 dan cB2 = c 1 = 2, jadi untuk pemecahan dasar ini cB = (cB1 , cB2) = (3, 2).

•

Setiap vektor Aj lainnya dari matriks A bisa ditulis/dinyatakan sebagai kombinasi linear dari vektor-vektor di dalam basis.

•

Untuk keperluan tersebut perlu dihitung Yj untuk Aj

•

Perhatikan A2 dan menggunakan persamaan (2),

•

Nilai dari z2, bisa dihitung dengan mempergunakan (5), yaitu sebagai berikut:

6

•

Untuk pemecahan dasar yang fisibel ini, nilai Z diperoleh dari rumus berikut:

•

Dengan jalan menghilangkan Br dengan menggunakan (6), kita peroleh pemecahan dasar yang baru yaitu:

•

Pemecahan dasar yang baru ini juga harus fisibel. Hal ini memerlukan syarat-syarat berikut:

•

Apabila Aj paling tidak mempunyai xij > 0, dan apabila kolom yang tepat dari B dipindahkan/di-keluarkan kemudian diganti dengan Aj , maka kemudian bisa ditunjukkan bahwa pemecahan dasar yang baru akan fisibel. kalau yrj > 0 dan yij ≤ 0, (i ≠ r), maka (9a) dan (9b) akan otomatis berlaku untuk yang tidak sama dengan r ini. Jadi kalau demikian halnya hanya dibicarakan mengenai yij > 0. Kita harus memilih di antara Bi dengan yij > 0 suatu vektor Br yang akan kita singkirkan/keluarkan sedemikian rupa sehingga (9a) dan (9b) di atas dipenuhi. Selanjutnya apabila yij > 0, maka syarat-syarat dari (9a) dan (9b) setelah dilakukan pembagian dengan yij bisa dituliskan sebagai berikut:

• • • •

7

•

Sekarang persoalannya menjadi jelas, yaitu apabila kita tentukan kolom ke-r dari B diganti dengan memenuhi syarat berikut:

Maka pemecahan dasar yang baru akan fisibel. RINGKASAN

1. Kita mulai dengan matriks B = (B1 , B2 , ... , Bm) di mana kolom-kolomnya sebanyak m berasal dari matriks A (kita ambil m kolom dari A yang linearly independent, kolom-kolom dari A sendiri sebanyak n buah dan n ≥ m).

2. Kita anggap xB = B-1H sebagai pemecahan dasar yang fisibel dari persoalan linear programming yang bersangkutan.

3. Selanjutnya kita pilih vektor kolom AJ dari A yang tidak berada di B. Kalau Aj mempunyai satu atau lebih yij > 0, di mana Yj = B-1 A, maka telah kita tunjukkan, bahwa kita bisa mengeluarkan beberapa kolom dari B kemudian menggantikannya dengan Aj. Dengan demikian, akan kita peroleh satu pemecahan dasar baru yang fisibel.

4. Pemilihan kolom B yang akan dikeluarkan tidak boleh semau kita saja, tetapi harus memenuhi beberapa syarat tertentu agar pemecahan dasar yang kita peroleh menjadi fisibel. Syarat tersebut ialah seperti tertera pada (10).

5. Mari kita pakai notasi baru B' = (B’ 1 , B’ 2 , . . . , B’ m ) yaitu matriks baru yang nonsingular diperoleh dari B dengan jalan mengeluarkan/menyingkirkan B serta menggantikannya dengan A. Kolom-kolom dari matriks yang baru adalah sebagai berikut: B’ i = B i untuk i ≠ r dan B’ r = A j , i = r ………………………………………….. (11)

6. Apabila pemecahan dasar yang baru diberi simbol x’B maka kemudian x’B = B-1H 7. Dari persamaan (8) kita peroleh nilai-nilai dari variabel-variabel dasar yang baru dinyatakan di dalam variabel yang asli dan yij , yaitu:

8

8. Sampai pada tahap ini kita telah memperoleh pemecahan dasar baru yang fisibel untuk suatu set pembatasan yang telah kita tuliskan, seperti AX = H (variable slackdan surplus telah dimasukkan) dengan jalan mengubah salah satu variabel sebanyak (m-1) yang bisa mengambil nilai berbeda dengan 0 (difference from zero) di dalam pemecahan dasar yang asli. Nilainya, masih bisa berbeda dengan 0 di dalam pemecahan dasar yang baru.

9. Tetapi pada umumnya nilai sesungguhnya dari variabel-variabci tersebut akan berubah dan nilai-nilai yang baru bisa diperoleh deng menggunakan persamaan (12a) dan (12b) di atas. Selain itu variabel \ yang menempati posisi yang ke-r (kolom ke-r), akan berbeda deng. nilai-nilai dari pemecahan sebelumnya. Sebagai contoh misalnya kolom AA sebagai Br jadi berarti XBr = x4 dan A& menggantikan Br (yaitu A), maka xB = x6. Variabel-variabel yang muncul di dalam posisi ke-r akan selalu berbeda-beda, tetapi pada posisi atau kolom-kolom lainnya variabel-variabel itu tidak berubah, akan sama saja hanya nilainya saja yang mungkin berubah.

(bersambung)

9