LINEAR PROGRAMING :SIMPLEKS
A.
MAKSIMASI PROFIT
Maksimasi Profit :
Kendala:
I.
TABEL SIMPLEKS AWAL
I.1. Ubah persamaan dengan menambahkan variable slack
I.2. Ubah
persamaan kendala ke dalam bentuk matriks
I.3. Susun Bentuk variabel simpleks awal
(Bentuk baku
Atau
- Slack variabel (s1, s2, s3) masih
merupakan basic variabel (memiliki nilai masing-masing 1 dan entry 0) yang
membentuk matriks indentitas.
- X1 dan x2 merupakan non basic
variabel (karena nilai x1 dan x2 = 0 / belum ada output) karena itu s1 =
36, s2 = 40 dan s3 = 28
II. ELEMEN PIVOT DAN PERUBAHAN DASAR
Lakukan proses
perubahan basis yaitu pemilihan variable yang dimasukkan dan dikeluarkan.
II.1. Cari
Indikator negatif dengan niali absolut terbesar akan menentukan variabel yang
masuk dalam basis.
-5 (kolom pertama atau x1) merupakan indikator negatif dengan nilai absolut
terbesar sehingga x1 masuk dalam basis (KOLOM x1 menjadi KOLOM PIVOT)
II.2. Variabel
yang dieliminasi ditentukan dari rasio pemindahan. Rasio pemindahan ditentukan
dengan membagi elemen kolom konstan dengan kolom pivot (dengan mengabaikan
rasio-rasio yang lebih kecil atau sama dengan nol).
Maka baris 1
adalah baris pivot.
Elemen pivot
adalah 6 (perpotongan kolom varaibel yang masuk ke basis dan baris yang
berhubungan dengan variabel yang meninggalkan basis)
III. PIVOTING
- Pengubahan elemen pivot menjadi 1 dan
elemen lainnya menjadi matriks identitas
III.1. Kalikan
baris pivot dengan kebalikan nilai elemen pivot (kalikan 1/6)
Tabel Kedua:
III.2. Selesaikan kolom pivotnya- Kurangkan 5 kali baris 1 dari baris 2
- 2 kali baris 1 dari baris 3
- Tambahkan 5 kali baris 1 ke baris 4
Hasil mendasar
dengan menetapkan x2= 0 dan s1=0 maka x1=6, s2= 10 dan s3=16.
IV. OPTIMASI
|
- -4/3 satu-satunya indikator negatif
maka x2 masuk dalam kolom basis dan kolom 2 merupakan kolom pivot
- Bagi kolom konstanta dengan dengan
kolom pivot, ambil rasio terkecil menjadi elemen pivot baru (10/3)
- Kalikan baris 2 dengan 3/10
- Kurangkan1/3 kali baris 2 dari baris
1
- 10/3 kali baris 2 dari baris 3
- Tambahkan 4/3 kali baris 2 ke baris 4
Karena tidak ada
indikator negatif yang tertinggal dalam baris terakhir maka ini merupakan
penyelesaian yang optimal, sehingga x1 = 5, x2 = 3, s1 = 0, s2 = 0, s3 = 6.
Fungsi
objektif maksimum pada Π = 34.
Atau
Interpretasi
:
Laba
maksimum sebesar 34 hanya dapat dicapai jika s1 dan s2 = 0 dengan nilai (jumlah
x1 = 5 dan x2 = 3 unit serta s3 (sisa kapasitas yang tidak tercapai pada unit
3)
Cek:
Π = 5 (5) +
3 (3)= 34 (OK)
Nilai ½ dan
2/5 pada kolom s1 dan s2 merupakan SHADOW PRICE atau IMPUTED PRICES atau
marginal value dari tiap-tiap unit di masing-masing kendala.
Jika ½ (36)
+ 2/5 (40) = 34 (OK)
B. MINIMISASI BIAYA
C = 2x1 +
4x2
Kendala:
I. Tabel Simpleks Awal
I.1. Ubah pertidaksamaan menjadai persamaan dengan mengurangkan variabel
surplus
I.2. Ubah dalam
Bentuk Matriks
Jika x1 = 0 dan x2
= 0 maka s1 =-14, s2= -12 dan s3= -18 (nilai negatif tidak mungkin, untuk
mengatasi tersebut dibuat VARIABEL BUATAN (ARTIFICIAL VARIABLES)
III.3. Tambahakan
variable buatan V ≥ 0
- dipakai untuk menghasilka penyelesaian dasar awal yang mungkin
- tidak mempunyai makna ekonomi
- ditambahkan terpisah bersifat “lebih besar datau sama dengan”.
II. Tabel Simpleks (Yang disesuaikan untuk minimisasi)
II.1. Buat Matriks
Simpleks Awal
Fungsi objektif
memiliki koefisien nol untuk variable
surplus dan koefisien M (variable buatan) nilainya bilangan sangat besar dan
tidak mungkin.
II.2. Pindahkan M dari kolom variebl buatan : M kali (baris 1 + baris 2 +
baris 3) ke baris 4
Menghasilkan tabel awal:
|
Penyelesaian
mendasar pertama jika x1=x2=s1=s2=s3=0 maka A1=14, A2= 12 dan A3=18 dan fungsi
objektif sama dengan 44M (Bilangan besar yang tidak mungkin) Cari perubahan
basis untuk menurunkan biaya.
III. ELEMEN PIVOT
III.1. Untuk minimisasi, indicator positif terbesar akan menentukan kolom
pivot dan variabel basis. (44 M bukan indikator)
Jadi 5M-4 merupakan indikator positif terbesar. X2 dimasukkan ke basis dan
kolom 2 adalah kolom pivot
III.2. Cari rasio konstanta dan kolom 2 yang memiliki rasio terkecil. Rasio
terkecil adalah 18/3, maka baris 3 adalah baris pivot dan elemen pivot adalah
3.
IV. Pivoting
IV.1. Kurangi elemen pivot menjadi 1 dengan mengalikan baris 3 dengan 1/3
IV.2. Rampungkan kolom Pivot
- Mengurangkan baris 3 dari baris 1 dan
baris 2
- (5M-4) kali baris 3 dari baris 4
V. Pengulangan (Reiterasi)
- Selama masih ada indikator positif , proses terus berjalan.
- Kolom pivot baru adalah baris 1. X1
masuk dalam basis dan A1 meninggalkan basis. Elemen pivot 5/3 (Rasio
Konstanta dan kolom pivot yang memiliki nilai terkecil)
- Kalikan baris 1 dengan 3/5
- Rampungkan kolom 1
·
Mengurangkan
2/3 baris 1 dari baris 2
·
1/3
baris 1 dari baris 3
·
(7M –
2)/3 baris 1 dari baris 4
- Cari Kembali nilai indokator
terbesar yaitu kolom 3 dan Rasio terkecil yaitu 2/5
VI. Pivot Keempat
VI.1. Kalikan Baris 2 dengan 5/2
VI.2. Selesaikan pivoting :
- Tambahkan 3/5 baris 2 ke baris 1
- Kurangkan 1/5 baris 2 dari baris ke 3
- (2M-2)/5 baris 2 dari baris 4
Sehingga:
- Semua indikator negatif, suatu
penyelesaian optimal telah tercapai
Hasil x1 = 9; x2 = 3 dan s1 = 7 dan
Biaya opyimum minimal sebesar Rp 30,-
Keslimpulan:
- dengan s2 = s3 = 0 kebutuhan kedua dan
ketiga dipenuhi secara tepat tidak ada yang berlebih, s1 = 7, kebutuhan
pertama terpenuhi secara berlebih sebesar 7 unit.
- nilai absolut s2 dan s3 = 1 maka
pengurangan 1 unit kebutuhan kedua dan ketiga akan mengurangai biaya
sebesar Rp 1,-. Sedangkan s1 = 0 maka pengurangan satu unit dalam
kebutuhan gizi pertama tidak akan mengurangi biaya.
SOAL:
1. 
(maksimasi profit)
(maksimasi profit)
Kendala :
6x1 + 3 x2 + 5x3 ≤ 30
2x1 + 2x2 + 10x3 ≤ 50
X1, x2, x3 ≥ 0
2. c= 60x1 + 80x2
Kendala:
2x1 + 3 x2 ≥ 36
2x1 + 2x2 ≥ 28
8x1 + 2x2 ≥ 32
X1, x2 ≥ 0
