metode simplek presented by: edy setiyo utomo, …...solusi optimal x1 = 2/3, x2 = 5/9 , x3 = 0 dan...
TRANSCRIPT
Metode Simplek Presented by: Edy Setiyo Utomo, S.Pd, M.Pd
Penyelesaian program linier dengan metode simplex adalah metode yang paling efisien dalam memecahkan persoalan program linier. Walaupun cara aljabar dapat dipergunakan untuk jumlah variabel lebih dari dua akan tetapi cara ini tidak efisien untuk variable yang terlalu banyak.
Misalkan kalau ada 10 variabel dengan 5 persamaan, maka akan diperoleh lebih dari 200 persamaan dasar. Sedangkan cara grafik hanya cocok untuk dua variable saja. Untuk variabel lebih dari tiga akan susah dalam penggambarannya.
Oleh karena itu cara simplex adalah metode yang paling efisien untuk dipakai.
Metode simplex adalah suatu metode yang memerlukan perhitungan yang berulang-ulang atau bersifat iterative yang bergerak selangkah demi selangkah menuju titik ekstrim yang optimum. Pemecahanya adalah dengan mengadakan pengubahan pertidaksamaan menjadi persamaan dengan cara menambahkan slack variabel untuk pertidaksamaan yang mengandung tanda ≤ dan mengurangkan variabel surplus untuk pertidaksamaan yang mengandung tanda ≥.
Kegiatan/Sumber
Kegiatan per unit1 2 3………………n
Batasan
123.....
mZ
Tk keg
a 11 a 12 a 13…………..a 1na 21 a 22 a 23 ………….a 2na 31 a 32 a 33 ………….a 3n. . . .. . . .. . . .. . . .. . . .a m1 am2 am3 a mnc1 c2 c3 cn
B1B2B3.....
bn
1. Mengubah fungsi tujuan dalam bentuk implisit ( mengubah semua ruas kanan menjadi ruas kiri )
2. Mengubah fungsi batasan menjadi kesamaan (slack variabel atau surplus variabel)
3. Memasukkan semua fungsi yang ada ke dalam tabel simplek4. Memilih kolom kunci ( dilihat pada f. tujuan dengan indeks negatif
yang terbesar)5. Memilih baris kunci ( bagi nilai kanan yang ada pada f. batasan
dengan indeks angka pada kolom kunci, baris kunci dipilih dengan indeks positif terkecil)
6. Memilih angka kunci ( perpotongan dari baris kunci dan kolom kunci)
7. Membagi baris kunci dengan angka kunci8. Ganti VD baris kunci dengan kolom kunci9. Mengenolkan semua nilai pada kolom kunci kecuali angka kunci ,
baris baru = baris lama – ( angka kolom kunci dikali nilai baru pada baris kunci)
10. Ulangi langkah ke-4 dan seterusnya sampai pada f. tujuan tidak dapat dipilih kolom kunci
VD Z X1 X2 X3 ……….. Xn X(n+1) X(n+2) X(n+3) X(n+m) NK
ZX(n+1)X(n+2)X(n+3).
.
.
.
.X(n+m)
1000
0
- C1a 11a 21a 31
a m1
- C2a 12a 22a 32
a m2
- C3a 13a 23a 33
a m3
……….. - Cna 1na 2na 3n
a mn
0100
0
0010
0
0001
0
0000
1
0B 1B2B3.
.
.
.
.Bm
Tabel simplex
Back
Selesaikan kasus berikut ini menggunakan metode simpleks :
Maksimum z = 8 x1 + 9 x2 + 4x3 Kendala :x1 + x2 + 2x3 ≤ 22x1 + 3x2 + 4x3 ≤ 37x1 + 6x2 + 2x3 ≤ 8x1,x2,x3 ≥ 0
VB X1 X2 X3 S1 S2 S3 NK Rasio
Z -8 -9 -4 0 0 0 0
S1 1 1 2 1 0 0 2
S2 2 3 4 0 1 0 3
S3 7 6 2 0 0 1 8
VB X1 X2 X3 S1 S2 S3 NK Rasio
Z -8 -9 -4 0 0 0 0
S1 1 1 2 1 0 0 2 2
S2 2 3 4 0 1 0 3 1
S3 7 6 2 0 0 1 8 8/6
VB X1 X2 X3 S1 S2 S3 NK Rasio
Z
S1
x2 2/3 1 4/3 0 1/3 0 1
S3
Perhitungan nilai barisnya : Baris z : -8-9-40000 -9 ( 2/3 14/301/301 ) --2 0 80309 Baris s1 : 1121002 1 (2/314/301/301 ) -1/302/31-1/301 Baris s3 : 7620018 6 ( 2/314/301/301 ) -30-60-212
VB X1 X2 X3 S1 S2 S3 NK Rasio
Z -2 0 8 0 3 0 9 -
S1 1/3 0 2/3 1 -1/3 0 1 3
X2 2/3 1 4/3 0 1/3 0 1 3/2
S3 3 0 -6 0 -2 1 2 2/3
VB X1 X2 X3 S1 S2 S3 NK Rasio
Z 0 0 4 0 5/3 2/3 31/3
S1 0 0 4/3 1 -1/9 -1/9 7/9
X2 0 1 8/3 0 7/9 -2/9 5/9
X1 1 0 -2 0 -2/3 1/3 2/3
Solusi optimal X1 = 2/3, X2 = 5/9 , X3 = 0 dan Z = 31/3, artinya untuk mendapatkan keuntungan maksimum sebesar $ 31/3 , maka perusahaan sebaiknya menghasilkan produk 1 sebesar 2/3 unit dan produk 2 sebesar 5/9 unit
S1 = 7/9. Sumber daya ini disebut berlebih (abundant) S2 = S3 = 0. Kedua sumber daya ini disebut habis terpakai
(scarce). Koefisien S1 pada baris fungsi tujuan table optimal = 0,
dengan demikian harga bayangan sumber daya pertama adalah 0
Koefisien S2 pada baris fungsi tujuan table optimal = 5/3, dengan demikian harga bayangan sumber daya kedua adalah 5/3
Koefisien S3 pada baris fungsi tujuan table optimal = 2/3, dengan demikian harga bayangan sumber daya kedua adalah 2/3.
Tentukan nilai x1 dan x2 agar fungsi tujuan maksimum dengan metode simplexZ = 3 x1 + 5 x2Fungsi batasan : 2 x1 ≤ 8 3 x2 ≤ 15 6 x1 + 5 x2 ≤ 30
look
Diketahui Z = x1 + 2 x2 + 3 x3Fungsi batasan x1 + 2 x2 – 3 x3 ≤ 62 x1 – x2 + 4 x3 ≤ 24 x1 + 3 x2 – 2 x3 ≤ 14
look
