metode simpleks -...
TRANSCRIPT
Metode Simpleks Oleh: Litna Nurjannah Ginting, SP, M.Si
PROGRAM STUDI AGRIBISNIS
FAKULTAS PERTANIAN
UNIVERSITAS MEDAN AREA
2019
Metode Simpleks
Metode Simpleks adalah salah satu metode yang digunakan dalam linear programming.
Metode simplek merupakan metode yang paling powerfull diantara semua metode linear programming karena menerapkan proses yang berulang-ulang. Dimulai dari mendesign
program atau solusi dasar yang feasible, menguji setiap solusi yang ada untuk mengetahui solusi mana yang optimal atau tidak. Jika tidak menemukan solusi yang optimal, maka
mendesign dan menguji kembali sampai hasil ujinya optimal. Sehingga dalam metode simpleks ini tergantung dua konsep yaitu Feasibility dan Optimality
Metode Simplex
Metode grafik tidak dapat menyelesaikan persoalan linear program yang memiliki
variabel keputusan yang cukup besar atau lebih dari dua variabel
Bentuk Standar :
Maksimalkan/Minimalkan :
Z = C1X1 + C2X2 + C3X3 + … + CnXn
Fungsi pembatas:
a11X1 + a12X2 + a13X3 + … + a1nXn ≤ b1
a21X1 + a22X2 + a23X3 + … + a2nXn ≤ b2
am1X1 + am2X2 + am3X3 + … + amnXn ≤ bm
1
2
3
4
5
6
Merubah fungsi tujuan dan
batasan-batasan
Menyusun persamaan-
persamaan dalam tabel
Memilih kolom kunci
Memilih baris kunci dan
merubah nilai-nilai baris kunci
Merubah nilai-nilai selain pada
baris kunci
Melanjutkan perbaikan-
perbaikan/perubahan-
perubahan
Langkah Metode Simpleks Lorem ipsum dolor sit amet, alii aliquip ei vel
1. Merubah fungsi tujuan dan batasan-batasan
• Nilai Kanan (NK/RHS) Fungsi tujuan diubah menjadi NOL
Z = 3X1 + 5X2
diubah menjadi:
Z – 3X1 – 5 X2 = 0
• Nilai kanan (RHS) fungsi kendala harus positif. Apabila negatif, nilai tersebut harus dikalikan -1
• Pada bentuk standar,semua batasan mempunyai tanda ≤. Pertidaksamaan tersebut harus diubah
menjadi persamaan. Caranya dengan menambah SLACK VARIABLE (variabel tambahan).
2X1 ≤ 8
3X2 ≤ 15
Diubah menjadi:
2X1 + S1 = 8
3X2 + S2 = 15
Kasus Maksimisasi
Fungsi Tujuan :
Maksimumkan : Z – C1X1-C2X2- . . . . . –CnXn-0S1-0S2-. . .-0Sn = NK
Fungsi Pembatas :
a11X11+a12X12+. . . .+a1nXn+ S1+0S2+. . .+0Sn = b1
a21X21+a22X22+. . . .+a2nXn+ 0S1+1S2+. . .+0Sn = b2
……. …….. ……. ….. ….. …. …..= …
am1Xm1+am2Xm2+. . . .+amnXn+ S1+0S2+. . .+1Sn = bm
Var. Kegiatan Slack Variabel
Variabel slack : variabel tambahan yang mewakili tingkat sumber daya yang
Menganggur atau kapasitas yang merupakan batasan
Tabel Simpleks
Contoh Kasus
Diketahui :
Model Program Linear:
1. Fungsi Tujuan :
Maksimumkan : Z = 15 X1 + 10 X2
2. Fungsi Pembatas :
a. Bahan A : X1 + X2 ≤ 600
b. Bahan B : 2 X1 + X2 ≤ 1.000
Syarat non negative : X1, X2 ≥ 0
Hitung nilai optimum!
Penyelelesaian:
1. Merubah fungsi tujuan dan fungsi
batasan
1. Merubah fungsi tujuan :
Z = 15 X1 + 10 X2 + 0 S1 + 0 S2
Z – 15 X1 – 10 X2 – 0 S1 – 0 S2 = 0
2. Fungsi Pembatas :
a. Bahan A : X1 + X2 + S1 + 0 S2 = 600
b. Bahan B : 2 X1 + X2 + 0 S1 + S2 = 1.000
Syarat non negative : X1, X2, S1, S2 > 0
2. Menyusun persamaan dengan tabel
Variabel
Dasar Z X1 X2 S1 S2 NK
Z 1 -15 -10 0 0 0
S1 0 1 1 1 0 600
S2 0 2 1 0 1 1000
3. Memilih kolom kunci
Kolom kunci: kolom yang merupakan dasar untuk
mengubah tabel simplek. Pilihlah kolom yang mempunyai
nilai pada garis fungsi tujuan yang bernilai negatif dengan
angka terbesar.
4. Memilih baris kunci dan merubah nilai-nilai baris kunci
Variabel
Dasar Z X1 X2 S1 S2 NK
Keterangan
(Indeks)
Z 1 -15 -10 0 0 0 0
S1 0 1 1 1 0 600 600/1 = 600
S2 0 2 1 0 1 1000 1000/2=500
Z
S1
X1 0 1 1/2 0 1/2 500
Note: Jika suatu tabel sudah tidak memiliki nilai negatif pada baris fungsi tujuan, berarti tabel tersebut
sudah optimal
Baris kunci: dasar untuk merubah tabel simpleks dengan cara mencari
indeks tiap-tiap baris dengan membagi nilai-nilai pada kolom NK dengan
nilai yang sebaris pada kolom kunci.
5. Merubah nilai-nilai selain pada baris kunci
Rumus:
Baris baru = baris lama – (koefisien pada kolom kunci) x nilai baru baris kunci
X1 X2 S1 S2 NK
-15 -10 0 0 0
(-15) 1 0.5 0 0.5 500 (-)
Nilai baru = 0 -2.5 0 7.5 7500
Baris Pertama (Z)
Baris Kedua (S1)
X1 X2 S1 S2 NK
1 1 1 0 600
(1) 1 0.5 0 0.5 500 (-)
Nilai baru = 0 0.5 1 -0.5 100
Tabel Simpleks Baru
Variabel
Dasar Z X1 X2 S1 S2 NK
Z 1 -15 -10 0 0 0
S1 0 1 1 1 0 600
S2 0 2 1 0 1 1000
Z 1 0 -2.5 0 7.5 7500
S1 0 0 0.5 1 -0.5 100
X1 0 1 1/2 0 1/2 500
Tabel pertama nilai lama dan tabel kedua nilai baru
6. Melanjutkan perbaikan-perbaikan/perubahan-perubahan
Ulangi langkah-langkah perbaikan mulai dari langkah 3 – 5 untuk memperbaiki tabel-tabel yang
telah diubah/diperbaiki nilainya. Perubahan baru berhenti setelah pada baris pertama (fungsi
tujuan) tidak ada bernilai negatif.
Variabel
Dasar Z X1 X2 S1 S2 NK
Keterangan
(indeks)
Z 1 0 -2.5 0 7.5 7500 = 7500/-2.5 = -
3000
S1 0 0 0.5 1 -0.5 100 = 100/0.5
= 200
S2 0 1 0.5 0 0.5 500 = 500/0.5
=1000
Z
X2 0 0 1 2 -1 200
X1
Nilai baru
X1 X2 S1 S2 NK
0 -2.5 0 7.5 7500
(-2.5) 0 1 2 -1 200 (-)
Nilai baru = 0 0 5 5 8000
Baris pertama
Baris Ketiga
X1 X2 S1 S2 NK
1 0.5 0 0.5 500
(0.5) 0 1 2 -1 200 (-)
Nilai baru = 1 0 -1 1 100
Tabel Simpleks Final Hasil Perubahan
Variabel
Dasar Z X1 X2 S1 S2 NK
Z 1 0 0 5 5 8000
X2 0 0 1 2 -1 200
X1 0 1 0 -1 1 100
Hasil yang di dapat adalah :
X1 = 100
X2 = 200
Zmaksimum = 8.000
“There are only two ways to live your life. One is as though
nothing is a miracle.
The other is as though everything is a miracle.”
- Albert Einstein
That’s all. Thank you! Any Questions?
TUGAS!!
1.Suatu pabrik berkeinginan memproduksi 2 jenis barang yaitu barang A dan barang B.
barang A memberi keuntungan Rp. 10.000,- per buah dan barang B member keuntungan
Rp. 12.000,- per buah. Untuk memproduksi kedua barang itu diperlukan tiga buah mesin,
yaitu mesin I, mesin II dan mesin III. Waktu yang diperlukan untuk memproduksi setiap barang
dengan ketiga mesin tersebut dan waktu yang tersedia untuk setiap mesin selama tiga bulan
diperlihatkan dalam table berikut. Berapakah keuntungan maksimun yang dapat diperoleh?
Mesin I(jam) Mesin II(jam) Mesin III (jam)
Barang A 2 3 1
Barang B 3 2 1
Waktu yang tersedia 1500 1500 600
2. Sebuah pabrikk memproduksi tiga jenis perlengkapan plastik. Waktu
yang dibutuhkan untuk pencetakan, pemangkasan dan pengemasan dalam
tabel berikut ini (waktu dinyatakan dalam jam/lusin perlengakapan)
Berapa lusin untuk setiap perlengakapan yang diproduksi untuk mendapatkan
keuntungan yang maksimal?
Process Tipe A Tipe B Tipe C Total Time
Pencetakan 1 2 1.5 12000
Pemangkasan 0.6 0.6 1 4.600
Pengemasan 0.5 0.3 0.5 2.400
Profit $11 $16 $15