Metode Big M , Metode 2 Fase, dan Metode Simpleks

Metode BIG M

Metode Big M digunakan untuk menyelesaikan fungsi-fungsi dalam program linier yang tidak berada dalam bentuk baku atau standar  ( bentuk standar adalah memaksimalkan Z sesuai dengan kendala fungsional dalam bentuk  ≤ dan kendala nonegativitas di semua variabel) dan salah satu contoh masalah dalam kendala funsional adalah bila fungsi dalam bentuk-bentuk = atau ≥ atau bahkan ruas kanan yang negatif.
Masalah ini akan muncul bila kita akan mencari basis fesibel awal sehingga sebelum mencari variabel apa yang akan menjadi variabel nonbasis bahkan basis perlu dilakukan suatu teknik pendekatan khusus untuk mengubah fungsi tersebut ke bentuk baku atau standar. Teknik pendekatan khusus tersebut dengan cara menambahkan variabel dummy (variabel artifisial) pada kendala fungsional dan teknik ini disebut dengan teknik variabel artifisial.
Ada pun prosedur mendapatkan BF awal pada kendala fungsional adalah
  1. Gunakan teknik variabel artifisial
Tambahkan variabel artifisal nonegatif pada fungsi kendala yang belum baku, dan anggaplah variabel artifial tersebut sebagai salah satu variabel slack
  1. Tugaskan pinalty yang besar
Berilah nilai variabel artifisial dengan nilai > 0 sehingga koefisien variabel artifisial menjadi M (big m) secara simbolik yang menunjukkan bahwa variabel artifisial tersebut memiliki angka positif raksasa ( dan pengubahan atas variabel artifisial bernilai 0 (variabel nonbasis) dalam solusi optimal disebut metode big m).

Contoh  =  Min  Z  =  4 X1 +  X2     
                   Kendala     3 X1 +  X2     =  3
                                     4 X1 + 3 X2    ³  6
                                     X1 + 2 X2     £  4
                                          X1 , X2    ³  0
è Bentuk standar
                  Min  Z  =  4 X1 +  X2     
                   Kendala     3 X1 +  X2                   =  3                      ......... ( 1 )
                                     4 X1 + 3 X2  - X3  =  6                    ......... ( 2 )
                                     X1 + 2 X2    + X =  4
                                     X1 , X,  X, X4    ³  0
Karena ( 1 ) dan ( 2 ) tidak memiliki var slack , maka ditambahkan R1 dan R2 sebagai var bantuan
              ( 1 )          3 X1 +  X2             +   R1   =  3
              ( 2 )          4 X1 + 3 X2  - X3 - R2  =  6

Ø  Pada fungsi tujuan berikan koefisien M > 0, untuk R1 dan R; sehingga :   
                  Min  Z  =  4 X1 +  X2   + MR1 + MR2
                   Kendala     3 X1 +  X2                  R1                                       =  3
                                   4 X1 + 3 X2  - X3                   - R2                     =  6
                                                X1 + 2 X2                                                 + X    =  4
                                                    X1 , X,  X, R1 , R2 , X4    ³  0

Ø  Subtitusikan R1 dan Rke fungsi tujuan  :
      R1  =  3  -  3 X1  -   X2
      R2    =  6  -  4 X -   3 X2   +  X3
      Maka :
          Z  =  4 X1 +  X2   + M(3  -  3 X1  -   X2) + M(6  -  4 X -   3 X2   +  X3)
               =  ( 4 - 7M ) X1  +  ( 1 – 4M ) X2  +  M X3  +  9M
      Persamaan Z dalam tabel :
          Z  +  ( 7M - 4 ) X1  +  ( 4M - 1 ) X2  -  M X3  =  9M

Ø  Solusi dasar awal ; X1 = 0, X2  = 0,  X3  = 0        ->  Z  =  9M
Sehingga      X1 , X,  X3   var non basis

Tabel Metode Big M
Iterasi 0 (awal)X1 (paling + ) R1Keluar
Basis
X1
X2
X3
R1
R2
X4
Solusi
Z
(7M – 4)
(4M – 1)
-M
0
0
0
9M
R1
3
1
0
1
0
0
3
3/3 = 1
R2
4
3
-1
0
1
0
6
6/4
X4
1
2
0
0
0
1
4
4/1
( 1 ) X2masukR2keluar
Z
0
(1+5M)/3
-M
(4-7M)/3
0
0
4+2M
X1
1
1/3
0
1/3
0
0
1
1/(1/3)= 3
R2
0
5/3
-1
-4/3
1
0
2
2/(5/3)=6/5
X4
0
5/3
0
-1/3
0
1
3
8/5
( 2 ) X3masuk X4keluar
Z
0
0
1/5
(8/3-M)
(-1/5-M)
0
18/3
X1
1
0
1/5
3/5
-1/5
0
3/5
3
X2
0
1
-3/5
-4/5
3/5
0
6/5
X4
0
0
1
1
-1
1
1
1
( 3 )(optimum)
Z
0
0
0
7/3-M
-M
-1/5
17/5
X1
1
0
0
2/5
0
-1/5
2/5
X2
0
1
0
-1/5
0
3/5
9/5
X3
0
0
1
1
-1
1
1






 Metode 2 Fase
Dalam menyelesaiakan suatu persoalan dimana variabelnya lebih dari dua, juga menggunakan suatu metode yang bertahap. Metode ini disebut sebagai metode dua phase.
Pada dasarnya Metode dua fase (phase) sama seperti metode big M yang juga digunakan untuk menyelesaikan persoalan pemrograman linier yang memiliki bentuk yang tidak standar.  Berikut ini adalah prosedur menggunakan metode dua fase.
1.    Inisialisasi
Menambahkan variabel-variabel artifisal pada fungsi kendala yang memiliki bentuk tidak standar. Variabel artificial ini ditambahkan pada fungsi batasan yang pada mulanya memiliki tanda (³). Hal ini digunakan agar dapat mencari solusi basic fesibel awal.
2.    Fase 1
Digunakan untuk mencari basic fesibel awal.  Pada fase 1 memiliki langkah-langkah dimana tujuannya adalahm meminimalkan variabel artifisial ( Min Y= Xa)
s.t : Ax = b
           X = 0
Pada fase pertama bertujuan untuk memperoleh penyelesaian yang optimum dari suatu permasalahan. Pada fase pertama fungsi tujuan selalu minimum variabel artificial, meskipun permasalahan yang ada adalah permasalahan yang maksimum. Dalam meyelesaiakan pada fase pertama, yaitu membuat nilai nol dulu pada variabel artifisial, kemudian melanjutkan iterasi seperti proses iterasi biasanya(dengan aturan meminimumkan). Berhenti ketika pada baris ke-0 bernilai £ 0.
Fase pertama dianggap telah selesai atau memperoleh penyelesaian yang optimal adalah apabila variabel artifisial adalah merupakan variabel basis. Sedangkan apabila variabel artifisial adalah variabel non basis, maka masalah dianggap tidak mempunyai penyelesaian yang optimal, sehingga harus dilanjutkan ke fase yang kedua.
Pada fase kedua, tujuannya sama seperti fase pertama, yaitu untuk mendapatkan penyelesaian yang optimal dari suatu permasalahan yang ada. Fase dua berhenti sesuai dengan tujuan awal permasalahan.
3.    Fase 2
Digunakan untuk mencari solusi optimum pada permasalahan riil. Karena variabel artifisial bukan merupakan termasuk variabel dalam permasalahan riil, variabel artifisial tersebut dapat dihilangkan ( Xa=0). Bermula dari solusi BF yang didapatkan dari akhir fase 1. Pada fase 2 ini memiliki langkah-langkah sebagai berikut:
1.    Fungsi tujuan bisa memaksimalkan dan juga bisa meminimalkan tergantung pada permasalahan yang dihadapi.
2.    Menggunakan fungsi batasan (s.t) dari fase 1, melakukan proses iterasi seperti biasanya dan berhenti sesuai funsi obyektif awal
Contoh persoalan:

Metode ini digunakan untuk menyelesaikan persoalan PL yang memuat variabel buatan
      Contoh  =  Min  Z  =  4 X1 +  X2     
                   Kendala     3 X1 +  X2     =  3
                                     4 X1 + 3 X2    ³  6
                                     X1 + 2 X2     £  4
                                          X1 , X2    ³  0

Tahap 1 :
Bentuk dengan var buatan : R1 dan R2
Min  r  =  R1 + R2
                   Kendala     3 X1 +  X2                  R1                                       =  3
                                   4 X1 + 3 X2  - X3                   - R2                     =  6
                                                X1 + 2 X2                                                 + X    =  4
                                                    X1 , X,  X, R1 , R2 , X4    ³  0

Fungsi tujuan   r  =  R1 + R2
                            =  ( 3 – 3 X1 -  X2          ) + ( 6 - 4 X1 - 3 X2  + X3  )
                            =  -7 X1  -  4 X2   +   X3   +   9         
      Tabel Awal
VB
X1
X2
X3
R1
R2
X4
NK
r
7
4
-1
0
0
0
9
R1
3
1
0
1
0
0
3
R2
4
3
-1
0
1
0
6
X4
1
2
0
0
0
1
4

Tabel optimum : setelah 2 iterasi ( periksa ! )
VB
X1
X2
X3
R1
R2
X4
NK
r
0
0
0
-1
-1
0
0
X1
1
0
1/5
3/5
-1/5
0
3/5
X2
0
1
-3/5
-4/5
3/5
0
6/5
X4
0
0
1
1
-1
1
1

Karena minimum solusi r = 0, masalah ini memiliki pemecahan ( solusi ) layak. Lanjutkan ke tahap ( Fase ) kedua.
Tahap 2
F Menyingkirkan variabel buatan ( R1 dan R)
F Dari tabel optimum tahap 1 didapatkan :
 X1 +  1/5X3                  =  3/5
 X2 -  3/5X3                  =  6/5
 X3 +  X4                       =  1
            Masalah semula ditulis :
                                    Min  Z  =  4 X1 +  X
 Kendala     X1 +  1/5X3                                =  3/5                   ......... ( 1 )
       X2 -  3/5X3                                    =  6/5                   ......... ( 2 )
       X3 +  X4                                            =  1
       X1 , X,  X, R1 , R2 , X4    ³  0

            Maka terdapat 3 persamaan dan 4 variabel sehingga solusi dasar layak didapat dg membuat      (4 – 3) = 1 variabel dibuat nol
            X3  =  0                         ->         X1  =  3/5  ;  X2  =  6/5  ;  X4  =  1

F Fungsi tujuan  Z  =  4 X1 +  X
   =  4 (  3/5 +  1/X3  ) + (6/5  +  3/5X)
   =  - 1/X3   +  18/5
            Tabel Awal
            Var msk
VB
X1
X2
X3
X4
NK
Z
0
0
1/5
0
18/5
X1
1
0
1/5
0
3/5
X2
0
1
-3/5
0
6/5
X4
0
0
1
1
1









    
Tabel optimum
VB
X1
X2
X3
X4
NK
Z
0
0
0
-1/5
17/5
X1
1
0
0
-1/5
2/5
X2
0
1
0
3/5
9/5
X3
0
0
1
1
1






Metode Simpleks 
pertama sekali diperkenalkan oleh George B.Dantzig dari USA (1950) melalui bukunya Linear Programming and Extension, menyebutkan bahwa ide dari linear programming ini berasal dari ahli matematika Rusia  bernama L.V Kantorivich   yang pada tahun 1939 menerbitkan sebuah karangan yang berjudul “ Mathematical Methods in the Organization and Planning of Production”.  Dalam karangannya tersebut telah dirumuskan persoalan linear programming untuk pertama kalinya.  Akan tetapi ide ini rupanya  di Rusia tidak bisa berkembang. Malah ternyata  dunia barat yang memanfaatkan ide ini selanjutnya.
Secara umum dalam metode Simpleks, solusi berdasarkan teori matriks
A x = b
x =  A-1 b
Yang mana solusi pemrograman linier adalah harga x1,x2,…xn yang memenuhi semua fungsi kendala dan sekaligus mengoptimalkan fungsi tujuan.  Demikian juga bahwa jenis-jenis variabel solusi basis memenuhi
x = A-1 b  (x ≥ 0)
Dan solusi non basis   x = A-1 b , nilainya selalu  nol.
4.1.  Algoritma Metode Simpleks
Metode Simpleks merupakan prosedur aljabar yang bersifat iteratif yang bergerak selangkah demi selangkah, dimulai dari suatu titik ekstrem pada daerah fisibel (ruang solusi) menuju ke titik ekstrem yang optimum.
Metode simpleks akan sangat efektif digunakan untuk persoalan program linear dengan lebih dari dua variabel keputusan, dalam hal ini bukan berarti metode simpleks tidak dapat digunakan untuk menyelesaikan persoalan dengan dua variabel keputusan.
Sangat dibutuhkan pemahaman dan penguasaan yang utuh terhadap metode OBE (Operasi Baris Elementer) untuk menyelesaikan suatu persoalan program linear.  OBE digunakan untuk mencari solusi dari serangkaian persamaan (n persamaan dengan mvariabel) dengan menggunakan konsep aljabar matriks (bukan dengan cara eliminasi atau substitusi yang nantinya sangat berguna untuk metode simpleks).
Contoh :
Jika ada dua buah persamaan, masing-masing :
20x1 + 45 x2 = 10.750
30x1 + 25 x2 =   9.750
Sistem persamaan tersebut akan sama dengan sistem matriks berikut.
20              45        x1         10.750
=
30              25        x2            9.750
Langkah-langkah dalam menyelesaikan persoalan program linear dengan menggunakan metode simpleks adalah :
  1. Konversikan formulasi program linear ke bentuk standar, baik fungsi tujuan maupun fungsi pembatasnya.
  2. Untuk fungsi pembatas dengan tanda (≤), tambahkan variabel
  3. Untuk fungsi pembatas dengan tanda (≥), kurangi dulu dengan variabel surplus, kemudian tambahkan dengan variabel artificial.
  4. Untuk fungsi pembatas dengan tanda (=), tambahkan variabel artificial
  5. Untuk fungsi tujuan tambahkan variabel slack (dengan koefisien 0), variabel surplus(dengan koefisien 0), dan variabel artificial (dengan koefisien –M).
Siapkan tabulasi untuk proses iterasi simpleks dengan memasukkan fungsi pembatas dan fungsi tujuan yang standar.  Tabulasi ini terdiri dari kolom basis, kolom variabel keputusan, kolom ruas kanan dan baris Zj – Cj (untuk persoalan memaksimalkan atau meminimalkan).
Prosedur tabulasi simpleks adalah sebagai berikut :
  1. Lakukan serangkaian operasi baris elementer sehingga diperoleh jawaban optimal.
  2. Tentukan variabel masuk (dari elemen Zj – Cj terkecil)
  3. Tentukan variabel keluar (dari rasio antara ruas kanan dengan koefisien variabel masuk, dipilih yang terkecil).
  4. Tentukan pivot (elemen penentu iterasi simpleks yang akan kita ubah nilainya menjadi 1), dari perpotongan antara variabel masuk dan variabel keluar.
  5. Lakukan operasi baris elementer berdasarkan pivot ini untuk baris lainnya termasuk baris Zj – Cj.
  6. Proses iterasi dihentikan, jika semua nilai pada Zj – Cj ≥ 0, hal ini bisa diartikan bahwa solusi sudah optimal.
Tabel Simpleks
Untuk membuat tabel awal simpleks perlu diperhatikan beberapa syarat yaitu :
  1. Jumlah baris koefisien = jumlah persamaan kendalanya
  2. Semua ruas kanan (bj) ≥ 0
  3. Jumlah varibel basis = jumlah persamaan kendala
Adapun ciri-ciri varibel basis yang digunakan :
  1. Pada kolom variabel terdapat bilangan 1 (satu), bilangan lainnya nol
  2. Harga variabel basis = harga konstanta ruas kanan
  3. Semua kolom variabel basis, bersama sama membentuk matriks identitas
Contoh 1
Akan kita bahas soal no.1 pada bab penyelesian persoalan program linear dengan metode grafik di mana :
Fungsi memaksimalkan Z       =  3x1 + 4x2
S/T       2,5 x1 +   x2 ≤ 20
3x1 + 3x2 ≤ 30
x1 + 2x2  ≤ 16
x1, x2  ≥ 0
Variabel keputusan :   x1  = meja
x2  = kursi
Penyelesaian
Max     Z – 3x1 – 4x2                           =   0
S/T       2,5x1 + x2 + x3                         = 20
3x1 + 3x2       + x4                 = 30
x1 + 2x2                       + x5       = 16

di mana :
xadalah variabel slack untuk fungsi pembatas 1
x4 adalah variabel slack untuk fungsi pembatas 2
x5  adalah variabel slack untuk fungsi pembatas 3
Proses tabulasi simpleks adalah sebagai berikut :
  • Nilai Zj – Cj diperoleh dengan cara merubah bentuk awal Z = 3x1 + 4x2  menjadi
Z – 3x1 – 4x2  =   0, sehingga didapat nilai x1 = -3 dan x2 = -4.
  • Elemen baris dan kolom ( i , j ) ditujukan untuk elemen baris ke- i dan kolom variabel keputusan.
  • Ruas kanan adalah nilai yang terletak di sebelah kanan persamaan, yaitu  nilai di belakang tanda sama dengan (=). Untuk batasan 1 sebesar 20 batasan 2 sebesar 10 dan batasan 3 sebesar 30.
Setelah formulasi dirubah kemudian disusun ke dalam tabel, dalam bentuk simbol seperti berikut ini
Tabel 4.1.  Tabel Simpleks dalam bentuk simbol
Variabel
Basis
Zx1x2……….xnxn+1n+2………xn+mRuas Kanan
xn+10a11a12……a1n10………..0b1
xn+20a21a22……a1n01………..0b1
……….0…….…….…….……..……..0………0……..
……….0……..…….…….……..……..0……..0……..
xn+m0am1am2…….amn00……..1bm
Z1-C1-C2…….–Cn00……..00

Sehingga kita dapatkan tabulasi awal untuk persoalan tersebut adalah sebagai berikut:
Tabel 4.2.  Tabel awal simpleks
Basisx1x2x3x4x5Ruas KananRasio
x3
x4
x5
2,5
3
1
1
3
2
1
0
0
0
1
0
0
0
1
20
30
16
20
10
8
Zj – Cj-3-40000 
Iterasi Pertama :
  • Variabel masuk adalah x2 (dari nilai Zj – Cj terkecil atau negatif terbesar)
  • Variabel yang keluar untuk digantikan dengan variabel masuk adalah x5 yang diperoleh dari rasio ruas kanan terhadap koefisien kolom x2 (nilai Zj – Cj terkeci
  • Pivot ada pada elemen (3,2). Pivot adalah elemen perpotongan antara variabel masuk dan variabel keluar.
Semua nilai pada baris ke – 3 dibagi 2
(3,1)     =  ½     = 0,5
(3,2)     =  2/2  =  1
(3,3)     =  0/2   =  0
(3,4)     =  0/2   =  0
(3,5)     =  ½     =  0,5
(3,6)     =  16/2 =  8
Nilai-nilai baris yang lain, selain pada baris xdapat dirubah dengan rumus sebagai berikut
  • Baris ke -1
(1,1)     =  (-1)  x  0,5 + 2,5 = 2
(1,2)     =  (-1)  x  1  +  1= 0
(1,3)     =  (-1) (0) +  1 = 1
(1,4)     =  (-1) ( 0 ) +  0 = 0
(1,5)     =  (-1)  x  0,5 + 0  =  – 0,5
(1,6)     =  (-1)  x  8  + 20  =  12
  • Baris ke -2
(2,1)     =  (-3) x 0,5  +  3 = 1,5
(2,2)     =  (-3) x 1 + 3 = 0
(2,3)     =  (-3) x 0 + 0 = 0
(2,4)     =  (-3) x 0 + 1 = 1
(2,5)     =  (-3) x 0,5 + 0 = -1,5
(2,6)     =  (-3) x 8 + 30 = 6
  • Baris ke -4
(4,1)     =  4 x 0,5 + (-3) = -1
(4,2)     =  4 x  1 + (-4) = 0
(4,3)     =  4 x 0 + 0 = 0
(4,4)     =  4 x 0 + 0 = 0
(4,5)     =  4 x 0,5 + 0 = 2
(4,6)     =  4 x 8 + 0  =  32
Dengan demikian kita dapat mengisi tabel dengan angka-angka yang telah kita hitung di atas ke dalam bentuk tabulasi untuk  hasil iterasi pertama adalah seperti terlihat pada Tabel 4.3 di bawah ini
Tabel 4.3.   Setelah Dlakukan Iterasi I

Basisx1x2x3x4x5Ruas KananRasio
x3
x4
x2
2
1,5
0,5
0
0
1
1
0
0
0
1
0
-0,5
-1,5
0,5
12
6
8
6
4
16
Zj – Cj-1000232 

Dari tabel hasil iterasi pertama terlihat bahwa nilai pada baris Zj – Cj masih ada yang bernilai negatif dan ini dapat dikatakan bahwa solusi masih belum optimal, berarti pula harus dilakukan iterasi kedua.  Untuk melakukan iterasi kedua ini, langkah-langkah pengerjaannya sama dengan pada iterasi pertama, dimulai dengan menentukan variabel masuk, variabel keluar dan seterusnya.
Elemen (2,1)  :  pivot
Semua nilai pada baris ke -2 dibagi 1,5
  • Baris ke – 2
(2,1) = 1,5/1,5  =  1
(2,2) = 0/1,5  =  0
(2,3) = 0/1,5  =  0
(2,4) = 1/1,5  =  0,67
(2,5) = -1,5/1,5  =  -1
(2,6) = 6/1,5  =  4
  • Baris ke-1
(1,1) = (-2) x 1 + 2 = 0
(1,2) = (-2) x 0 + 0 = 0
(1,3) = (-2) x 0 + 1 = 1
(1,4) = (-2) x 0,67 + 0 = – 1,34
(1,5) = (-2) x (-1) + (-0,5) = 1,5
(1,6) = (-2) x 4 + 12 = 4
  • Baris ke-3
(3,1) = (-0,5) x 1 + 0,5 = 0
(3,2) = (-0,5) x 0 + 1 = 1
(3,3) = (-0,5) x 0 + 0 = 0
(3,4) = (-0,5) x 0,67 + 0 = 0,335
(3,5) = (-0,5) x (-1) + 0,5 = 1
(3,6) = (-0,5) x  4 + 8 = 6
  • Baris ke-4
(4,1) = 1 x 1 + (1) = 0
(4,2) = 1 x 0 + 0
(4,3) = 1 x 0 + 0 = 0
(4,4) = 1 x 0,67 + 0  = 0,67
(4,5) = 1 x (-1) + 2 = 1
(4,6) = 1 x 4 + 32 = 36
Dengan demikian kita dapat mengisi tabel dengan angka-angka yang telah kita hitung di atas ke dalam bentuk tabulasi untuk  hasil iterasi kedua adalah sebagai berikut :
Tabel 4.3.   Setelah Dilakukan  Iterasi II.
Basisx1x2x3x4x5Ruas Kanan
x3
x1
x2
0
1
0
0
0
1
1
0
0
-1,34
0,67
0,335
1,5
-1
1
4
4
6
Zj – Cj0000,67136

Pada baris Zj – Cj nilai semua elemennya sudah tidak ada lagi yang negatif, berarti solusi sudah optimal dan tidak perlu dilakukan iterasi lebih lanjut.
Kesimpulan :
x1 =  4,  x2 = 6, dan  Z = 36
Hasil tersebut sama dengan yang kita dapat dengan menggunakan metode grafik.

Komentar

Postingan populer dari blog ini

Kasus Kegagalan Konstruksi di Indonesia

DEFINISI DAN RUANG LINGKUP EKONOMI TEKNIK DIBIDANG TEKNIK SIPIL