1. PROGRAM LINIER METODE
ALJABAR
Untuk
memberikan contoh pemecahan persoalan L.P dengan cara aljabar, perhatikan
persoalan L.P yang telah dirumuskan sebagai berikut :
v Contoh persoalan maksimum
Cari x1, x2
s.r.s Z =
8 x1 + 6 x2 : Maksimum
d.k 4 x1 +
2 x2 £ 60
2
x2 + 4 x2 £ 48
x1 ³ 0 ; x2 ³ 0
Langkah-langkah pemecahan persoalan L.P secara aljabar :
v Ketidaksamaan kendala harus diubah dahulu menjadi persamaan
dengan jalan memasukkan slack variabel (misalnya x3 dan x4). Slack variabel
ialah suatu variabel yang ditambahkan di sebelah kiri tanda ketidaksamaan, agar
ketidaksamaan menjadi persamaan. Dengan memasukkan slack variabel x3 dan x4
kita peroleh 2 persamaan berikut :
4 x1 + 2 x2 + x3 =
60
2 x1 + 4 x2
+ x4 = 48
Persoalan L.P yang ketidaksamaannya sudah dirubah
menjadi persamaan disebut persoalan L.P yang standard. Dalam prakteknya x3 dan
x4 merupakan bahan mentah sisa yaitu yang tidak diproduksi, maka dari itu c3
dan c4 masing-masing nilainya sama dengan 0.
v Menyusun persoalan L.P standard
Cari x1, x2, x3, x4
s.r.s : Z = 8 x1 + 6 x2 + 0 x3 + 0 x4 : Maksimum
d.p 4 x1
+ 2 x2 + x3 = 60
2
x1 + 4 x2 + x4 = 48
x1, x2, x3, x4 ³ 0
v Jika ada n variabel yaitu x1, x2, ..., xn akan tetapi hanya
ada m persamaan, maka bisa diperoleh sebanyak K persamaan, dimana K =
kombinasi, dihitung berdasarkan rumus berikut :
n !
K
= ---------------
m! (n-m) !
Keterangan :
N ! = dibaca n faktorial
N ! = n (n-1) (n-2) ... 2.1
Contoh :
0 ! = 1
2 ! = 2.1 = 2
3 ! = 3.2.1 = 6
4 ! = 4.3.2.1 = 24
Dalam contoh persoalan diatas ini n = 4, m = 2, sehingga
4 ! 24
K = ----------------- = ---------- = 6
2 ! (4-2) ! 2 (2)
v
Dari
persoalan diatas ada 2 persamaan dan 4 variabel (x1, x2, x3, x4). Nilai-nilai
x1, x2, x3 dan x4 yang memenuhi persamaan tersebut disebut pemecahan dari
persamaan tersebut. Jadi apabila ada n variabel dan m persamaan maka variabel
yang diperoleh dari m persamaan tersebut disebut variabel dasar (basic variables). Sedangkan pemecahannya
disebut pemecahan dasar (basic solution).
Pemecahan yang memenuhi semua syarat pembatasan disebut pemecahan fisibel
(feasible solution). Kalau pemecahan fisibel maka merupakan pemecahan dasar
fisibel (basic feasible solution). Pemecahan yang menghasilkan paling sedikit
satu variabel yang negatif, maka disebut pemecahan tidak fisibel (not feasible solution)
v
Menyusun
6 persamaan dasar dan mencari pemecahannya
(1) Jika X1 = x2 = 0 (tidak ada produksi)
4
x1 + 2 x2 + x3 = 60
x3 =
60
2
x1 + 4 x2 + x4 = 48
x4 = 48
Z1
= 8 x1 + 6 x2 + 0 x3 + 0 x4
= 8 (0) + 6 (0) + 0 (60) + 0 (48)
= 0 (tidak ada penjualan)
(2) x1 = x3 = 0
4
x1 + 2 x2 + x3 = 60
2 x2 = 60
x2 = 30
2
x1 + 4 x2 + x4 = 48
4 x2 + x4 = 48
4 (30) + x4 = 48
x4 = 48 – 120 = - 72 (tidak fisibel)
Z2
tidak dihitung karena x4 negatif, jadi pemecahan tidak fisibel.
(3) x1 = x4 = 0
4 x1 + 2 x2 + x3 = 60
2 x2 + x3 = 60
2 x1 + 4 x2 + x4 = 48
4 x2 = 48
x2 = 12
2 x2 + x3 = 60
2 (12) + x3 = 60
x3 = 60 –24 = 36
Z3 = 8 (0) + 6
(12) + 0 (36) + 0 (0) = 72
(4) x2 = x3 = 0
4
x1 + 2 x2 + x3 = 60
4 x1 = 60
x1 = 15
2 x1 + 4 x2 + x4 = 48
2 (15) + x4 = 48
x4 = 18
Z4 = 8 (15) + 6
(0) + 0 (0) + 0 (18) =120
(5) x2 =
x4 = 0
4 x1 + 2 x2 + x3 = 60
4 x1 + x3 = 60
2 x1 + 4 x2 + x4 = 48
2 x1 = 48
x1 = 24
4 x1 + x3 = 60
4 (24) + x3 = 60
x3 = - 36
Z5 tidak
dihitung karena x3 negatif
(6) x3 = x4 = 0
4
x1 + 2 x2 + x3 = 60
4 x1 + 2 x2 = 60
2
x1 + 4 x2 + x4 = 48
2 x1 + 4 x2 = 48
v
Persamaan
simultan
4 x1 + 2 x2 = 60
x 1/2
2 x1 + 4 x2 = 48
x 1
2
x1 + x2 = 30
2 x1 + 4 x2 = 48
- 3 x2 = - 18
x2 = 6
2 x1 + 4 x2 = 48
2 x1
+ 4 (6) = 48
2 x1 = 24
x1 = 12
Z6 = 8 (12) + 6
(6) + 0 (0) + 0 (0)
= 132 (terbesar/maksimum)
Oleh
karena Z6 yang memberikan nilai tujuan terbesar maka Z6 = Z maksimum. Jadi
pemecahan dasar ke-6 merupakan pemecahan dasar yang optimal. Misalkan satuannya
dalam ribu, maka jumlah hasil penjualan maksimum = 132 ribu dengan keputusan
yang harus dibuat oleh pemilik perusahaan ialah bahwa barang A dan B dimana A =
x1 dan B = x2 masing-masing harus diproduksi sebesar 12 satuan dan 6 satuan.
v
Contoh persoalan minimum
Cari
x1, x2
s.r.s Z = 5
x1 + 3 x2 : Minimum
d.p 2 x1 + x2
³ 3
x1 + x2 ³ 2
x1, x2 ³ 0
Model
diatas harus diubah dahulu menjadi persamaan standard dengan memasukkan surplus
variabel x3 dan x4, yaitu variabel yang harus dikurangkan didalam suatu
ketidaksamaan agar supaya menjadi persamaan. Persoalan yang standard adalah
sebagai berikut :
Cari
x1, x2, x3 dan x4
s.r.s Z = 5 x1 + 3 x2 – 0 x3 – 0 x4 :
Minimum
d.p 2 x1 + x2 – x3 =
3
x1 + x2 - x4
= 2
x1, x2, x3, x4 ³ 0
Jawab :
(1) x1 = x2 = 0
2
x1 + x2 – x3 = 3
- x 3 = 3
x3 = -
3
x1 +
x2 - x4 = 2
- x4 = 2
x4 = -2
Z1 tidak perlu
dihitung karena pemecahan ini tidak fisibel, x3 dan x4 tidak memenuhi syarat
(nilainya negatif)
(2)
x1 = x3 = 0
2 x1 + x2 – x3 = 3
x2 = 3
x1 + x2 – x4 = 2
3 - x4
= 2
-
x4 =
-1
-
x4 = 1
Z2 = 5 (0) + 3
(3) – 0 (0) – 0 (1) = 9
(2) x1 = x4 = 0
2 x1 + x2 – x3 = 3
x2 – x3 = 3
x1 + x2 – x4 = 2
x2 =
2
2 – x3 = 3
-
x3 = 1
x3 = - 1
Z3 tidak perlu
dihitung karena pemecahan ini tidak fisibel, x3 tidak memenuhi syarat
(negatif).
(3) x2 =
x3 = 0
2
x1 + x2 – x3 = 3
2 x1 = 3
x1 = 1,5
x1
+ x2 – x4 = 2
x1 – x4 = 2
1,5 – x4
= 2
- x4 =
0,5
x4 = - 0,5
Z4 tidak perlu
dihitung.
(4) x2 =
x4 = 0
2
x1 + x2 – x3 = 3
2 x1 – x3 = 3
x1
+ x2 – x4 = 2
x1 = 2
2
(2) – x3 = 3
-
x3 =
-1
x3 = 1
Z5 = 5 (2) + 3
(0) – 0 (1) – 0 (0) = 10
(5) x3 = x4 = 0
2
x1 + x2 – x3 = 3
2
x1 + x2 = 3
x1 + x – x4 = 2
x1
+ x2 =
2
Persamaan
simultan :
2
x1 + x2 = 3
x1
+ x2 = 2
x1 =
1
1 + x2 = 2
x2 = 1
Z6 = 5 (1) + 3
(1) – 0 (0) – 0 (0) = 8
Dari 6
pemecahan dasar dipilih nilai Z yang paling kecil yaitu Z6 = Z minimum = 8.
Interpretasi lebih lanjut dari
penyelesaian persoalan L.P dengan metode aljabar adalah sebagai berikut :
(a) Kombinasi 1 pada kasus maksimalisasi yaitu
x1 = 0 dan x2 = 0 artinya perusahaan tidak berproduksi. Dengan tidak
berproduksi maka sumberdaya yang dimiliki tidak terpakai artinya sisa
sumberdaya sebanyak jumlah yang dimiliki yaitu x3 = 60 dan x4 = 48
(b) Kombinasi ke 3 dngan tidak memproduksi
produk 1 ( x1 = 0), memproduksi produk 2 sebanyak 12 unit ( x2 = 12) maka
penerimaan yang diperoleh sebesar 72. Dengan kombinasi tersebut sumberdaya 1
tersisa 36 unit dan sisa sumberdaya 2 adalah 0 atau habis terpakai.
(c) Kombinasi ke 4 dengan tidak memproduksi
produk 2 (x2 = 0), memproduksi produk 1 sebanyak 15 unit ( x1 = 15) maka
penerimaan yang diperoleh sebanyak 120. Dengan kombinasi tersebut sumberdaya 1
habis terpakai dan sumberdaya ke 2 sisa 18 unit.
(d) Kombinasi ke 6 dimana diupayakan sumberdaya
habis terpakai yaitu sisa masing-masing sumberdaya adalah 0 maka diproduksi
produk 1 sebanyak 12 unit dan produk 2 sebanyak 6 unit. Dengan demikian
penerimaan yang diperoleh adalah sebanyak 132 unit.
Kombinasi
terbaik adalah kombinasi ke 6 karena nilai Z tertinggi dan penggunaan
sumberdaya paling efisien karena kedua sumberdaya habis terpakai.
0 komentar:
Posting Komentar