Dilakukan jika metode grafik tidak bisa dipakai (variabel keputusan  ³  2)

Metode Simpleks :

  1. Simpleks Primal
  2. Simpleks Dua

Bentuk Linear Programming baku (standar) :

* Semua kendala adalah persamaan ( sisi kanan ³ 0 )

* Semua variabel non-negatif

* Fungsi tujuan berupa maksimisasi / minimisasi

Kendala (Constraints)

1.      Kendala jenis £ diubah menjadi = dengan menambahkan Variabel Slack di sisi kiri.

Kendala jenis ³ diubah menjadi = dengan mengurangkan Variabel Surplus di sisi kiri.

Contoh :

Kendala  X1 + X2 £ 15                  ->         X1 + X2 + S1 = 15         dengan S1 ³ 0

(S1 adalah sumber daya yang berlebih)

Kendala  2 X1 + X2 ³ 15    ->         2 X1 + X2 – S2 = 15       dengan S2 ³ 0

(S2 adalah sumber daya yang langka)

2.      Sisi kanan harus dibuat non-negatif

Contoh :

-5 X1 + X2 = -25    diubah menjadi                       5 X1 – X2 = 25

 

3.      Arah pertidaksamaan dibalik jika kedua sisi dikalikan -1

Contoh :

-5 X1 + X2 £  -25  diubah menjadi                       5 X1 – X2 ³  25

Ø  Variabel

Variabel unrestricted (tidak dibatasi) jika bernilai negatif / positif

Misal Xj adalah variabel unrestricted,

maka Xj =  Xj’  –  Xj’’

Xj’  ,  Xj’’  ³ 0

Hanya satu (Xj’  atau  Xj’’) saja yang bernilai positif

 

Ø  Fungsi Tujuan

Maksimisasi fungsi = Minimisasi ”negatif” fungsi itu.

Contoh :

Maks. Z  = 5X1 + 2X2 + 3X3 =          Min. (-Z) = -5X1 – 2X2 – 3X3

Contoh Soal :

Ubah dalam bentuk Standar :

Min. Z = 2X1 + 3X2

Kendala :     X1 +   X2 =  10

-2 X1 + 3 X2 £  -5

7 X1 –  4 X2 £  6

X1 (Unrestricted)

X2 ³  0

 

Jawab :

Min. Z = 2 X1’ – 2 X1’’ +  3 X2 + 0 S2 + 0 S3

Kendala :      X1’ –  X1’’ +   X2 =  10

-2 X1’ + 2 X1’’ + 3 X2 + S2 = -5  ->         2 X1’ – 2 X1’’ – 3 X2 – S2 = 5

7 X1’ – 7 X1’’ –  4 X2 + S3 =  6

X1’ ,  X1’’ , X2 , S2 , S3 ³ 0

 

 

F  Solusi Dasar

  • Jika ada model Linear Programmingdengan m persamaan (kendala) dan n variabel keputusan, maka solusi dasar -> n – m = 0

Sisanya dipecahkan sehingga mendapat solusi layak dan unik.

  • n – m variabel yang dibuat nol disebut variabel non-basis

n variabel sisanya disebut variabel basis

 

Contoh :

2X1 +    X2 + 4X3 + X4 = 2

X1 + 2 X2 + 2X3 + X4 = 3

m = 2

n =  4

n – m = 2   ->  Variabel non-basis

Sisa    = 2   ->   Variabel basis

Pilih 2 variabel yang dibuat nol, misal X3 = 0,  X4 = 0

Maka   2X1 +    X2 = 2

X1 + 2 X2 = 3

Dengan eliminasi dihasilkan X1 = 1/3  dan   X2 = 4/3              {hasil non-negatif = layak}

Solusi dasar X1 = 1/3  ,  X2 = 4/3  ,  X3 = 0  ,  X4 = 0

X1 dan  X2 adalah var. Basis

X3 dan X4 adalah var non-basis.

METODE SIMPLEKS PRIMAL

F  Variabel masuk adalah variabel non-basis yang masuk ke himpunan variabel dasar pada iterasi berikutnya.

F  Variabel keluar adalah variabel basis yang keluar dari solusi basis pada iterasi berikutnya.

Dua kondisi Simpleks Primal:

1. Kondisi Optimal   : Variabel masuk dalam maksimisasi (minimisasi) adalah variabel non-basis dengan koefisien paling negatif (positif) dalam persamaan fungsi tujuan (Z).
2. Kondisi Layak       : Variabel keluar adalah variabel basis yang mempunyai titik potong terkecil (rasio minmum dengan penyebut positif).

 

Langkah-langkah iterasi Simpleks Primal :

1.      Dengan bentuk standar, tentukan solusi dasar awal yang layak.

2.      Pilih variabel masuk diantara variabel non-basis dengan menggunakan kondisi optimal.

3.      pilh variabel keluar dari variabel basis dengan menggunakan kondisi layak.

4.      Tentukan nilai variabel basis yang baru dengan membuat variabel masuk tersebut sebagai variabel basis dan variabel keluar sebagai variabel non-basis.

5.      Kembali ke langkah 1.

 

Contoh :

Sebuah perusahaan meubel memproduksi meja dan kursi menggunakan papan, kayu, dan waktu pengerjaan. Setiap meja membutuhkan 5 unit papan, 2 unit kayu, dan 4 jam pengerjaan. Setiap kursi membutuhkan 2 unit papan, 3 unit kayu, dan 2 jam pengerjaan. Perusahaan dapat keuntungan $12 untuk meja dan $8 untuk kursi. Tersedia 150 unit papan, 100 unit Kayu, dan 80 jam pengerjaan. Berapa banyak produk agar keuntungan maksimum?

Jawab :

– Variabel Keputusan  : X1 = meja, dan  X2 = kursi

– Fungsi Tujuan           : Maks. Z = 12 X1 + 8 X2

– Kendala                     : papan, kayu, dan waktu

Formulasi Model :

Maks. Z = 12 X1 + 8 X2

Kendala :     5 X1 +   2 X2 £  150

2 X1 +   3 X2 £  100

4 X1 +   2 X2 £  80

X1 , X2 ³  0

Bentuk standard

Maks. Z = 12 X1 + 8 X2 + 0.S1 + 0.S2 + 0.S3

Kendala :     5 X1 + 2 X2 + S1 = 150

2 X1 + 3 X2 + S2 = 100

4 X1 + 2 X2 + S3 =  80

X1 , X2 , S1 , S2 , S3 ³  0

 

Tabel Simpleks                     non basis

Basis (Dasar) Z X1 X2 S1 S2 S3 Solusi  
Z 1 -12 -8 0 0 0 0 → Pers  Z
S1 0 5 2 1 0 0 150 → Pers  S1
S2 0 2 3 0 1 0 100 → Pers  S2
S3 0 4 2 0 0 1 80 → Pers  S3

 

Var msk

Basis (Dasar) Z X1 X2 S1 S2 S3 Solusi Rasio
Z 1 -12 -8 0 0 0 0  
S1 0 5 2 1 0 0 150 150/5 = 30
S2 0 2 3 0 1 0 100 100/2 =50
S3 0 4 2 0 0 1 80 80/4 = 20

 

Pers Pivot (Var Keluar)    elemen pivot

 

Aturan metode Gauss Jordan :

  1. Pers. Pivot

Pers. Pivot baru = pers. pivot lama : elemen pivot

  1. Pers. Lain

Pers. Baru = pers. Lama – ( koef kolom var masuk * pers. Pivot baru )

 

 

Maka :

S3 X1 =  ( 0   4   2   0   0   1   80 ) / 4

=  ( 0   1  ½  0   0   ¼  20 )

 

S2 baru              =  ( 0   2   3   0   1   0   100 )  – 2 ( 0   1  ½  0   0   ¼  20 )

=  ( 0   2   3   0   1   0   100 )  –  ( 0   2   1   0   0   ½  40 )  =  ( 0   0   2   0   1   -½   60 )

 

S1 baru              =  ( 0   5   2   1   0   0   150 )  – 5 ( 0   1  ½  0   0   ¼  20 )

=  ( 0   5   2   1   0   0   150 )  – ( 0   5  5/2 0   0   5/4 100 )  =  ( 0   0   -½   1   0   –5/4 50 )

 

Z   baru              =  ( 1   -12  -8   0   0   0  0 )  – (-12) ( 0   1  ½  0   0   ¼  20 )

=  ( 1   -12  -8   0   0   0  0 )  – ( 0  -12   6   0   0   -3   -240 )  =  ( 1   0   -2   0   0   3   240 )

 

Var msk

Basis (Dasar) Z X1 X2 S1 S2 S3 Solusi Rasio
Z 1 0 -2 0 0 3 240  
S1 0 0 1 0 5/4 50 50/(-½) = -100
S2 0 0 2 0 1 60 60/2 = 30
X1 0 1 ½ 0 0 ¼ 20 20/(½) = 40

 

Pers Pivot (Var Keluar)             elemen pivot

 

S2 X2 =  ( 0   0   2   0   1   -½   60 ) / 2

=  ( 0   0   1  0   ½   -¼   30 )

 

X1 baru              =  ( 0   1   ½   0   0   ¼   200 )  –  ½ ( 0   0   1  0   ½   -¼   30 )

=  ( 0   1   ½   0   0   ¼   200 )  –  ( 0   0   ½  0   ¼  –1/8 15 ) =  ( 0   1   0   0   -¼   3/8 5  )

 

S1 baru              =  ( 0   0   -½   1   0   –5/4 50 )  –  (-½ )( 0   0   1  0   ½   -¼   30 )

=  ( 0   0   -½   1   0   –5/4 50 )  – ( 0   0  -½   0  -¼  1/8 -15 ) =  ( 0  0  0  1  ¼  –11/8 65 )

Z   baru              =  ( 1   0   -2   0   0   3   240 )  –  (-2 )( 0   0   1  0   ½   -¼   30 )

=  ( 1   0   -2   0   0   3   240 )  –  ( 0   0   -2  0   -1   ½   -60 ) =  ( 1   0   0   0   1   5/2 300 )

 

Tabel Akhir

Basis (Dasar) Z X1 X2 S1 S2 S3 Solusi
Z 1 0 0 0 1 5/2 300
S1 0 0 0 1 ¼ 11/8 65
X2 0 0 1 0 ½ 30
X1 0 1 0 0 ¼ 3/8 5

 

Kesimpulan  :  X1 = 5      ( banyak meja )

X2 = 30     ( banyak kursi )

S1 = 65     ( unit papan / pers. Kendala 1  yg berlebih )

Z  =  300   ( keuntungan maks )

 

Bukti

Ø  Fungsi tujuan                     Z  = 12 X1 + 8 X2

=  12 ( 5 ) + 8 ( 30 )

=   60   +   240     =    300

 

Ø  Papan                         5 X1 + 2 X2 £  150

5 ( 5 ) + 2 ( 30 )  =  25  +  60  =  85              150  –  85  =  65   ( sisa )

 

Ø  Kayu                         2 X1 + 3 X2 £  100

2 ( 5 ) + 3 ( 30 )  =  10  +  90  =  100

 

Ø  Waktu                      4 X1 + 2 X2 £  80

4 ( 5 ) + 2 ( 30 )  =  20  +  60  =  80

 

 

METODE SIMPLEKS PRIMAL

DENGAN VARIABEL BUATAN (ARTIFICIAL)

 

1.      TEKNIK M ( METODE PENALTY )             Kendala tidak

2.      TEKNIK DUA FASE                                       semuanya £

 

1. TEKNIK 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 + X4 =  4

X1 , X2 , X3 , 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 R2 ; sehingga :

Min  Z  =  4 X1 +  X2 + MR1 + MR2

Kendala     3 X1 +  X2 + R1 =  3

4 X1 + 3 X2 – X3 – R2 =  6

X1 + 2 X2 + X4 =  4

X1 , X2 , X3 , R1 , R2 , X4 ³  0

 

Ø  Subtitusikan R1 dan R2 ke fungsi tujuan  :

R1 =  3  –  3 X1 –   X2

R2 =  6  –  4 X1 –   3 X2 +  X3

Maka :

Z  =  4 X1 +  X2 + M(3  –  3 X1 –   X2) + M(6  –  4 X1 –   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 , X2 , X3 var non basis

Tabel Metode Big M

Iterasi 0 (awal) X1 (paling + ) R1 Keluar 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 ) X2 masuk R2 keluar 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 ) X3 masuk X4 keluar 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  

2. DUA FASE

Bertujuan untuk mengurangi kesalahan perhitungan dari pemberian nilai yg besar untuk konstanta M pada metode TEKNIK M (penalty)

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 + X4 =  4

X1 , X2 , X3 , 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

Basis X1 X2 X3 R1 R2 X4 Solusi
Z 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 ! )

Basis X1 X2 X3 R1 R2 X4 Solusi
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 R2 )

F  Dari tabel optimum tahap 1 didapatkan :

X11/5X3 3/5

X2 –  3/5X3 6/5

X3 +  X4 =  1

Masalah semula ditulis :

Min  Z  =  4 X1 +  X2

Kendala     X11/5X3 3/5 ……… ( 1 )

X2 –  3/5X3 6/5 ……… ( 2 )

X3 +  X4 =  1

X1 , X2 , X3 , 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 +  X2

=  4 (  3/51/5 X3 ) + (6/5 3/5X3 )

=  – 1/5 X3 18/5

Tabel Awal

Var msk

Basis X1 X2 X3 X4 Solusi
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

Basis X1 X2 X3 X4 Solusi
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

 

 

 

 

 

 

Bandingkan dengan TEKNIK M!