3-Programa Linear Metode Simplek

Report
PROGRAMA LINEAR
DENGAN METODE SIMPLEKS
LANGKAH-LANGKAH METODE SIMPLEKS
1.
2.
3.
4.
5.
6.
7.
Ubah formulasi PL ke bentuk standar, baik fungsi tujuan maupun
fungsi pembatas
Untuk fungsi pembatas dengan tanda (≤), tambahkan dengan
variabel slack
Untuk fungsi pembatas dengan tanda (≥), kurangi dulu dengan
variabel surplus, kemudian tambahkan variabel artificial
Untuk fungsi pembatas dengan tanda (=), tambahkan variabel
artificial
Untuk fungsi tujuan, tambahkan dengan variabel slack (dengan
koefisen=0), variabel surplus (dengan koefisen=0) dan variable
artificial (dengan koefisen=0)
Siapkan tabulasi untuk iterasi
Tabulasi terdiri dari kolom Basis, kolom Variable Keputusan, kolom
Ruas Kanan dan baris Zj-Cj
 Formulasi Programa Linier
Max
Z
=
Pembatas
250x1
+ 200x2
20x1
+
45x2
≤
10.750
30x1
+
25x2
≤
9.750
 Bentuk Standar
Max
Pembatas
Z
= 250x1
20x1
+ 200x2
+
45x2
+ x3
30x1 + 25x2
+ x4
 x3 = variabel slack untuk fungsi pembatas 1
 x4 = variabel slack untuk fungsi pembatas 1
= 10.750
=
9.750
 PROSEDUR TABULASI SIMPLEKS
1.
2.
3.
4.
5.
6.
Lakukan serangkaian OBE sehingga diperoleh jawaban Optimal
Tentukan Variabel Masuk (dari elemen Zj-Cj terkecil)
Tentukan Variabel Keluar (dari rasio antara Ruas Kanan dibagi
dengan koefesien dari Variabel Masuk, danpilih yang kecil)
Tentukan Pivot (elemen penentu iterasi simpleks dan diubah
nilainya menjadi 1), dari perpotongan antar variabel masuk
dan variabel keluar
Lakuan OBE berdasarkan Pivot ini untuk baris lainnya,
termasuk baris Zj-Cj
Proses iterasi dihentikan (berarti solusi sudah optimal) bila
semua nilai Zj-Cj ≥ 0
 Tabulasi Simpleks
Basis
x1
x2
x3
x4
Ruas
Kanan
Rasio
x3
20
45
1
0
10.750
537,5
x4
30
25
0
1
9.750
325
Zj-Cj
-250
-200
0
0
0
Variabel Masuk dari
elemen Zj-Cj yang ter
kecil
Variabel Keluar pilih dari
Rasio yang terkecil
Rasio =Ruas kakan
dibagi elemen dari
variabel masuk
Iterasi 1
Variabel masuk = x1 dan vaiabel keluar
= x4, Pivot adalah elemen (2,1). Baris 2
dibagi 30
OBE baris 1 dan baris 3
Elemen baris 2 dikalikan (-20) dan
ditambahkan pada elemen baris 1
Elemen baris 2 dikalikan (250) dan
ditambahkan pada elemen baris 3
Basis
x1
x2
x3
x4
x3
20
45
1
0
10.750
537,5
x4
30
25
0
1
9.750
325
Zj-Cj
-250
-200
0
0
0
Basis
x1
x2
x3
x4
Ruas Kanan
x3
20,00
45,00
1,00
0,00
10.750,00
x1
1,00
0,83
0,00
0,03
325,00
Zj-Cj
-250,00
-200,00
0,00
0,00
0,00
Basis
x1
x2
x3
x4
Ruas Kanan
x3
0,00
28,33
1,00
-0,67
4.250,00
x1
1,00
0,83
0,00
0,03
325,00
Zj-Cj
0,00
8,33
0,00
8,33
81.250,00
Semua komponen pada Zj-Cj sudah ≥ 0, solusi sdh maksimal.
Jawaban x1=325, x2=0, x3=4.250, x4=0 dan Z=81.250
Ruas Kanan Rasio
CONTOH KE 2
 Formulasi Programa Linier
Max
: Z= 200x1 + 220x2 + 180x3
Pembatas : 4x1 + 6x2 + 9x3 ≤ 9.200
8x1 + 3x2 + 5x3 ≤ 7.800
5x1 + 7x2 + 4x3 ≤ 8.300
 Bentuk Standar
Max
: Z= 200x1 + 220x2 + 180x3
Pembatas : 4x1 + 6x2 + 9x3 + x4
≤ 9.200
8x1 + 3x2 + 5x3
+ x5
≤ 7.800
5x1 + 7x2 + 4x3
+ X6 ≤ 8.300

ITERASI 1
Basis
x4
x5
x6
Zj-Cj
x1
4
8
5
-200
x2
6
3
7
-220
x3
9
5
4
-180
x4
1
0
0
0
x5
0
1
0
0
x6
0
0
1
0
Ruas Kanan
9200
7800
8300
0
Rasio
1533
2600
1186
Basis
x4
x5
x2
Zj-Cj
x1
4,000
8,000
0,714
-200,000
x2
6,000
3,000
1,000
-220,000
x3
9,000
5,000
0,571
-180,000
x4
1,000
0,000
0,000
0,000
x5
0,000
1,000
0,000
0,000
x6
0,000
0,000
0,143
0,000
Ruas Kanan
9.200,000
7.800,000
1.185,714
0,000
Rasio
Basis
x4
x5
x2
Zj-Cj
x1
-0,286
5,857
0,714
-42,857
x2
0,000
0,000
1,000
0,000
x3
5,571
3,286
0,571
-54,286
x4
1,000
0,000
0,000
0,000
x5
0,000
1,000
0,000
0,000
x6
-0,857
-0,429
0,143
31,429
Ruas Kanan
2.085,714
4.242,857
1.185,714
260.857,143
Rasio
ITERASI 2
Basis
x4
x5
x2
Zj-Cj
x1
-0,286
5,857
0,714
-42,857
x2
0,000
0,000
1,000
0,000
x3
5,571
3,286
0,571
-54,286
x4
1,000
0,000
0,000
0,000
x5
0,000
1,000
0,000
0,000
x6
-0,857
-0,429
0,143
31,429
Ruas Kanan
2.085,714
4.242,857
1.185,714
260.857,143
Rasio
374,359
1.291,304
2.075,000
Basis
x3
x5
x2
Zj-Cj
x1
-0,051
5,857
0,714
-42,857
x2
0,000
0,000
1,000
0,000
x3
1,000
3,286
0,571
-54,286
x4
0,179
0,000
0,000
0,000
x5
0,000
1,000
0,000
0,000
x6
-0,154
-0,429
0,143
31,429
Ruas Kanan
374,359
4.242,857
1.185,714
260.857,143
Rasio
Basis
x3
x5
x2
Zj-Cj
x1
-0,051
6,026
0,744
-45,641
x2
0,000
0,000
1,000
0,000
x3
1,000
0,000
0,000
0,000
x4
0,179
-0,590
-0,103
9,744
x5
0,000
1,000
0,000
0,000
x6
-0,154
0,077
0,231
23,077
Ruas Kanan
374,359
3.012,821
971,795
281.179,487
Rasio
ITERASI 3
Basis
x3
x5
x2
Zj-Cj
x1
-0,051
6,026
0,744
-45,641
x2
0,000
0,000
1,000
0,000
x3
1,000
0,000
0,000
0,000
x4
0,179
-0,590
-0,103
9,744
x5
0,000
1,000
0,000
0,000
x6
-0,154
0,077
0,231
23,077
Ruas Kanan
374,359
3.012,821
971,795
281.179,487
Rasio
-7.300,000
500,000
1.306,897
Basis
x3
x1
x2
Zj-Cj
x1
-0,051
1,000
0,744
-45,641
x2
0,000
0,000
1,000
0,000
x3
1,000
0,000
0,000
0,000
x4
0,179
-0,098
-0,103
9,744
x5
0,000
0,166
0,000
0,000
x6
-0,154
0,013
0,231
23,077
Ruas Kanan
374,359
500,000
971,795
281.179,487
Rasio
Basis
x3
x1
x2
Zj-Cj
x1
0,000
1,000
0,000
0,000
x2
0,000
0,000
1,000
0,000
x3
1,000
0,000
0,000
0,000
x4
0,174
-0,098
-0,030
5,277
x5
0,009
0,166
-0,123
7,574
x6
-0,153
0,013
0,221
23,660
Ruas Kanan
400,000
500,000
600,000
304.000,000
Rasio
Zj-Cj ≥ 0 maka solusi sdh optimal
x1 = jumlah meja = 500 unit
x2 = jumlah lemari = 600 unit
x3 = jumlah kursi = 400 unit
Tugas
 Maksimumkan Z = 3X1 + 5X2
 Batasan (constrain)
(1)
2X1
8
(2)
3X2
 15
(3)
6X1 + 5X2
 30
 Selesaikan dengan cara grafiks dan simpleks
PENAFSIRAN TABEL SIMPLEKS
Lihat contoh sebagai berikut :
Maksimumkan
Syarat
Z =
3X1 + 2X2
X1 + X2 ≤ 15 Kendala Tenaga
2X1 + X2 ≤ 28 Kendala Kayu
X1 + X2 ≤ 20 Kendala Paku
X1; X2 ≥ 0
Hasilnya adalah sebagai berikut :
Solusi Optimal,
Elemen Zj-Cj
Non Negatif
Basis
X1
X2
S1
S2
S3
Solusi
X2
0
1
2
-1
0
2
X1
1
0
-1
1
0
13
S3
0
0
-3
1
1
3
Zj-Cj
0
0
1
1
0
43
 Pada Tabel Simpleks Optimal dapat ditafsirkan hal berikut:
Solusi Optimal
2. Keadaan Sumberdaya
3. Sumbangan per unit Sumberdaya
1.
A. SOLUSI OPTIMAL
Variabel Keputusan
Nilai Optimum
Keputusan
X1
13
Menghasilkan Kursi 13
X2
2
Menghasilkan Meja 2
Z
43
Menghasilkan Laba 43
 Keadaan Sumberdaya
Keadaan Sumberdaya ada 2 macam yaitu Langka dan Berlebih
2. Slack Positif berati kelebihan Sumberdaya
3. Slack 0 (nol) berarti seluruh sumebr daya terserap.
1.
Sumberdaya
Slack
Keadaan Sumber daya
Tenaga
S1 = 0
Langka
Kayu
S2 = 0
Langka
Paku
S3 = 3
Berlebih
Penambahan Paku
tidak akan
menaikkan Laba
 Sumbangan per unit Sumberdaya
Basis
X1
X2
S1
S2
S3
Solusi
Zj-Cj
0
0
1
1
0
43
 S1 = 1, berarti bahwa Sumberdaya Tenaga ditambah 1 unit
maka Fungsi Tujuan (laba) akan bertambah 1 unit. Demikian
juga untuk S2 yaitu kayu. Akan tetapi S3 (Paku) apabila ditambah
1 unit tidak akan menambah keuntungan
 S1, S2, S3 disebut juga Shadow Price artinya sumbangan
perubahan 1 unit Sumberdaya terhadap kenaikan Fungsi Tujuan

similar documents