METODE SIMPLEKS
Merupakan metode yang umum digunakan untuk menyelesaikan seluruh problem program linier, baik yang melibatkan dua variabel keputusan maupun lebih dari dua variabel keputusan.
Langkah - langkah :
1. Mengubah bentuk batasan model pertidaksamaan menjadi persamaan.
2. Membentuk tabel awal untuk solusi feasible dasar pada titik orijin dan menghitung nilai-nilai baris zj dan cj – zj.
3. Menentukan kolom pivot (kolom pemutar) dengan cara memilih kolom yang memiliki nilai positif terbesar pada baris cj – zj. Kolom pivot ini digunakan untuk menentukan variabel non-basis yang akan masuk ke dalam variabel basis.
4. Menentukan baris pivot (baris pemutar) dengan cara membagi nilai-nilai pada kolom kuantitas dengan nilai-nilai pada kolom pivot, kemudian memilih baris dengan hasil bagi yang non-negatif terkecil. Baris pivot ini digunakan untuk menentukan variabel basis yang akan keluar dari variabel basis.
5. Perpotongan antara kolom pivot dan baris pivot diperoleh nilai pivot.
6. Mengubah nilai baris pivot yang baru dengan cara :
[nilai baris pivot baru = nilai baris pivot lama / nilai pivot]
Sehingga pada tabel baru, nilai pivot menjadi 1.
7. Menghitung nilai baris lainnya dengan cara :
[nilai baris tabel baru = nilai baris tabel lama - (koef. kolom pivot yang berhubungan x nilai baris pivot tabel baru yang berhubungan]
8. Menghitung baris-baris zj dan cj – zj.
9. Menentukan apakah solusi telah optimal dengan cara mengecek baris cj – zj. Jika nilai cj – zj adalah nol atau negatif, maka solusi telah optimal. Tetapi jika masih terdapat nilai positif, maka kembali ke langkah c dan mengulangi kembali langkah-langkah selanjutnya.
Contoh soal :
1. Perusahaan Maju Terus merencanakan untuk menginvestasikan uang paling banyak $ 1.200.000. uang ini akan ditanamkan pada 2 buah cabang usaha yaitu P dan Q. setiap unit P memerlukan uang sebesar $50 dan dapat memberikan rate of return per unitnya per tahun sebesar 10% sedangkan untuk setiap unit Q memerlukan uang sebesar $100, namun memberikan rate of return per unit per tahunnya sebesar 4%. Perusahaan tersebut telah mempertimbangkan bahwa target rate of return dari kedua usaha tersebut paling sedikit adalah $60.000 per tahunnya. Kemudian hasil analisis perusahaan memperoleh data bahwa setiap unit P dan Q mempunyai index risiko masing-masing 8 dan 3. Padahal perusahana ini tidak mau menanggung resiko yang terlalu besar. Kebijakan lainnya yang diinginkan oleh pemimpin khususnya untuk cabang usaha P ditargetkan paling sedikit jumlah investasinya adalah $3.0000. Bagaimana penyelesaian persoalan diatas apabila perusahaan bermaksud untuk tetap melakukan investasi tetapi dengan menekan atau meminimasi resiko sekecil mungkin. Berapa unit masing-masing usaha dapat diinvestasikan ? (metode grafis dan metode simpleks)
Penyelesaian
Merupakan metode yang umum digunakan untuk menyelesaikan seluruh problem program linier, baik yang melibatkan dua variabel keputusan maupun lebih dari dua variabel keputusan.
Langkah - langkah :
1. Mengubah bentuk batasan model pertidaksamaan menjadi persamaan.
2. Membentuk tabel awal untuk solusi feasible dasar pada titik orijin dan menghitung nilai-nilai baris zj dan cj – zj.
3. Menentukan kolom pivot (kolom pemutar) dengan cara memilih kolom yang memiliki nilai positif terbesar pada baris cj – zj. Kolom pivot ini digunakan untuk menentukan variabel non-basis yang akan masuk ke dalam variabel basis.
4. Menentukan baris pivot (baris pemutar) dengan cara membagi nilai-nilai pada kolom kuantitas dengan nilai-nilai pada kolom pivot, kemudian memilih baris dengan hasil bagi yang non-negatif terkecil. Baris pivot ini digunakan untuk menentukan variabel basis yang akan keluar dari variabel basis.
5. Perpotongan antara kolom pivot dan baris pivot diperoleh nilai pivot.
6. Mengubah nilai baris pivot yang baru dengan cara :
[nilai baris pivot baru = nilai baris pivot lama / nilai pivot]
Sehingga pada tabel baru, nilai pivot menjadi 1.
7. Menghitung nilai baris lainnya dengan cara :
[nilai baris tabel baru = nilai baris tabel lama - (koef. kolom pivot yang berhubungan x nilai baris pivot tabel baru yang berhubungan]
8. Menghitung baris-baris zj dan cj – zj.
9. Menentukan apakah solusi telah optimal dengan cara mengecek baris cj – zj. Jika nilai cj – zj adalah nol atau negatif, maka solusi telah optimal. Tetapi jika masih terdapat nilai positif, maka kembali ke langkah c dan mengulangi kembali langkah-langkah selanjutnya.
Contoh soal :
1. Perusahaan Maju Terus merencanakan untuk menginvestasikan uang paling banyak $ 1.200.000. uang ini akan ditanamkan pada 2 buah cabang usaha yaitu P dan Q. setiap unit P memerlukan uang sebesar $50 dan dapat memberikan rate of return per unitnya per tahun sebesar 10% sedangkan untuk setiap unit Q memerlukan uang sebesar $100, namun memberikan rate of return per unit per tahunnya sebesar 4%. Perusahaan tersebut telah mempertimbangkan bahwa target rate of return dari kedua usaha tersebut paling sedikit adalah $60.000 per tahunnya. Kemudian hasil analisis perusahaan memperoleh data bahwa setiap unit P dan Q mempunyai index risiko masing-masing 8 dan 3. Padahal perusahana ini tidak mau menanggung resiko yang terlalu besar. Kebijakan lainnya yang diinginkan oleh pemimpin khususnya untuk cabang usaha P ditargetkan paling sedikit jumlah investasinya adalah $3.0000. Bagaimana penyelesaian persoalan diatas apabila perusahaan bermaksud untuk tetap melakukan investasi tetapi dengan menekan atau meminimasi resiko sekecil mungkin. Berapa unit masing-masing usaha dapat diinvestasikan ? (metode grafis dan metode simpleks)
Penyelesaian
Fungsi Tujuan : z = 8x + 3y
Fungsi Pembatas : 50x +
100y ≤ 1.200.000
50x ≥ 3.000
5x + 4y ≥ 60.000
Bentuk baku diperoleh dengan menambahkan variabel slack pada
kendala pertama, mengurangkan
variabel surplus pada kendala kedua. Sehingga diperoleh :
Minimumkan : Z =
8x + 3y + 0S1 + 0S2 + 0S3 +MA1 + MA2
50x + 100y + S1 =
1.200.000
50x - S2 + A1 =
3.000
5x + 4y – S3 +
A2 = 60.000
Table Simpleks Awal
Basis
|
X1
|
X2
|
S1
|
S2
|
S3
|
A1
|
A2
|
NK
|
Rasio
|
Z
|
55M-8
|
4M-3
|
0
|
-M
|
-M
|
0
|
0
|
63.000M
|
|
S1
|
50
|
100
|
1
|
0
|
0
|
0
|
0
|
1.200.000
|
1.200.000:50=24.000
|
A1
|
50
|
0
|
0
|
-1
|
0
|
1
|
0
|
3.000
|
3.000:50 = 60
|
A2
|
5
|
4
|
0
|
0
|
-1
|
0
|
1
|
60.000
|
60.000 : 5 = 12.000
|
Iterasi Pertama
Basis
|
X1
|
X2
|
S1
|
S2
|
S3
|
A1
|
A2
|
NK
|
Rasio
|
Z
|
0
|
4M-3
|
0
|
0,1M-0,16
|
0
|
-1,1M+0,16
|
0
|
59.700M+480
|
|
S1
|
0
|
100
|
1
|
1
|
0
|
-1
|
0
|
1.197.000
|
11.970
|
X1
|
1
|
0
|
0
|
-0,02
|
0
|
0,02
|
0
|
60
|
|
A2
|
0
|
4
|
0
|
0,1
|
-1
|
-0,1
|
1
|
5700
|
1.425
|
Iterasi Kedua
Basis
|
X1
|
X2
|
S1
|
S2
|
S3
|
A1
|
A2
|
NK
|
Z
|
0
|
0
|
0
|
-0,085
|
M-0,75
|
-M+0,085
|
-M+0,75
|
54.000M+4755
|
S1
|
0
|
0
|
1
|
-1,5
|
25
|
1,5
|
-25
|
1.054.500
|
X1
|
1
|
0
|
0
|
-0.02
|
0
|
0.02
|
0
|
60
|
X2
|
0
|
1
|
0
|
0,025
|
-0,25
|
-0,025
|
0,25
|
1425
|
Iterasi kedua adalah optimal karena koefisien pada
persamaan Z semuanya non positif, dengan X1= 60, X2 =
1425 dan Z =
54.000M+4755.
2. Budi baru saja
membuka sebuah took sepeda didepan rumahnya. Untuk persediaan budi bermaksud
membeli 50 sebuah sepeda.
Dan sepeda yang ia inginkan ada 3 jenis, yakni sepeda biasa, sepeda balap dan
sepeda gunung. Harga ketiga sepeda tersebut masing-masing adalah 80.000/sepeda,
120.000/sepeda dan 100.000/sepeda. Budi merencanakan untuk tidak mengeluarkan
uang lebih dari Rp. 5.400.000 dengan mengharapkan keuntungan Rp.12.000 dari
setiap sepeda biasanya Rp.20.000 dari setiap sepeda balap, dan Rp.14.000 dari
sepeda gunung. Berapakah masing-masing sepeda yang harus dibeli budi untuk
persediaan ditokonya agar mendapat keuntungan optimal?
Penyelesaian.
Variabel :
Sepeda biasa = X1
Sepeda balap = X2
Sepeda gunung = X3
Fungsi Tujuan :
Zmax = 12.000X1 +
20.000X2 + 14.000X3
Fungsi Kendala :
X1 + X2 +X3 ≤ 50
80.000X1 +
120.000X2 + 100.000X3 ≤ 5.400.000
X1, X2,
X3 ≥ 0
Bentuk Standard :
Zmax = 12X1 +
20X2 + 14X3
Z – 12X1 –
20X2 – 14X3 = 0
S/t X1 + X2 + X3 + X4 = 50
80X1 +
120 X2 +100X3 + X5 = 3400
Proses Tabulasi Simplex
Basis
|
X1
|
X2
|
X3
|
X4
|
X5
|
RK
|
Ratio
|
X3
|
1
|
1
|
1
|
1
|
0
|
160
|
50
|
X4
|
80
|
120
|
100
|
0
|
1
|
5400
|
45
|
Z
|
-12
|
-20
|
-14
|
0
|
0
|
0
|
X2 baru
:
80/120 120/120 100/100 0/120 1/120 5400/120
0,67 1 0,83 0 0,008 45
X3 baru
: Z
baru :
-1
x 0,67 + 1 =
0,33 20
x 0,67 + (-12) = 1,4
-1
x 1 +
1 = 0 20
x 1 + (-20)
= 0
-1
x 0,83 + 1 =
0,17 20
x 0,83 + (-14)
= 2,6
-1
x 0 + 1 =
1 20
x 0 + 0 = 0
-1 x 0,008 + 0 =
-0,008 20
x 0,008
+ 0 = 0,16
-1
x 45 + 50 =
5
20
x 45 + 0 = 900
Hasil Iterasi I
Basis
|
X1
|
X2
|
X3
|
X4
|
X5
|
RK
|
X3
|
0,33
|
0
|
0,17
|
1
|
-0,008
|
5
|
X1
|
0,67
|
1
|
0,83
|
0
|
-0,008
|
45
|
Z
|
-1,4
|
0
|
2,6
|
0
|
0,16
|
900
|
Karena semua komponen
pada Z ≥ 0, maka Solusi sudah optimal.
Maka diperoleh X1 =
0, X2 = 45
, dan X3 = 5
Zmax = 12.000 X1 +
20.000 X2 + 14.000 X3
=
12.000(0) + 20.000(45) + 14.000 (5)
=
0 + 900.000 + 70.000
=
970.000
Karena semua komponen
pada Z ≥ 0, maka Solusi sudah optimal.
Maka diperoleh X1 =
0, X2 = 45
, dan X3 = 5
Zmax = 12.000 X1 +
20.000 X2 + 14.000 X3
=
12.000(0) + 20.000(45) + 14.000 (5)
=
0 + 900.000 + 70.000
=
970.000