Riset Operasi : Tugas 2
MAKALAH
RISET OPERASI
OPTIMASI KEUNTUNGAN
PEMBANGUNAN PERUMAHAN DI DAERAH
TANGERANG
Disusun
Oleh :
DINDA
PRATIWI
12316102
2TA06
JURUSAN
TEKNIK SIPIL
FAKULTAS
TEKNIK SIPIL DAN PERENCANAAN
UNIVERSITAS
GUNADARMA
2018
1.
LATAR BELAKANG
Program linier merupakan metode matematika
dalam mengalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan
seperti memaksimumkan keuntungan dan meminimumkan biaya. Program linier banyak
diterapkan dalam masalah ekonomi, industri, militer, sosial dan lain-lain.
Program linier berkaitn dengan penjelasan suatu kasus dalam dunia nyata sebagai
suatu metode matematika.
Salah satu teknik
penentuan solusi optimal yang digunakan dalam pemrograman linier adalah metode
simpleks. Penentuan solusi optimal menggunakan metode simpleks didasarkan pada
teknik eliminasi Gaus Jordan. penentuan solusi optimal dilakukan dengan
memeriksa titik ekstrim satu persatu dengan cara perhitungan iteratif. sehingga
penentuan solusi optimal dengan simpleks dilakukan dengan tahap demi tahap yang
disebut dengan iterasi.
Metode simpleks ini
adalah metode yang biasanya digunakan untuk memecahkan setiap permasalahan pada
pemrograman linier yang kombinasi variabelnya terdiri dari tiga variabel atau
lebih. Metode
simpleks merupakan sebuah metode lanjutan dari metode grafik. Metode grafik
tidak dapat menyelesaikan persoalan manajemen yang memiliki variabel keputusan
yang cukup besar, sehingga untuk menyelesaikannya dibutuhkan sebuah metode yang
lebih kompleks yaitu dengan menggunakan program komputer QSB ( Quantitative
System For Business) atau menggunakan metode simpleks. Dalam kenyataanya
penggunaan komputer lebih efisien, akan tetapi metode dasar yang digunakan
dalam pengoperasian komputer tetap metode simpleks.
2.
TUJUAN
Tujuan dari penulisan Makalah Riset Operasi ini adalah sebagai
berikut:
1. Menerjemahkan masalah perhitungan keuntungan dalam sebuah proyek pembangunan
perumahan.
2.
Memperoleh hasil perhitungan keuntungan yang optimal.
3. Menentukan jumlah unit yang akan dijual untuk memperoleh keuntungan yang
maksimal.
3.
BATASAN MASALAH
Batasan masalah yang
ada dalam Makalah Riset Operasi ini adalah sebagai berikut:
1. Menghitung keuntungan dan menetukan jumlah unit rumah yang akan dibuat
di lokasi yang terletak di Tangerang.
2. Penggunakan metode simpleks dalam menyelesaikan masalah dalam Makalah
Riset Operasi.
4.
LANDASAN
TEORI
Metode
simpleks adalah metode yang dapat digunakan untuk menyelesaikan persoalan
manajerial yang telah diformulasikan terlebih dahulu ke dalam persamaan
matematika program linear yang mempunyai variabel keputusan mulai dari
lebih besar atau sama dengan 2 (dua) sampai multivariabel. Sedangkan metode
grafik hanya dapat digunalan apabila jumlah variabel
keputusan maksimal 2 (dua) buah. Sehingga dapat disimpulkan bahwa suatu persoalan
linear programing yang diselesaikan dengan metode grafik juga dapat
diselesaikan dengan metode simpleks, sebaliknya suatu persoalan yang hanya bisa
diselesaikan dengan metode simpleks tidak dapat diselesaikan dengan metode
grafik.
Metode
simpleks merupakan salah satu teknik penentuan solusi optimal yang digunakan
dalam pemrograman linier. Penentuan solusi optimal didasarkan pada teknik
eliminasi Gauss Jordan. Penentuan solusi optimal dilakukan dengan memeriksa
titik ekstrim (ingat solusi grafik) satu persatu denagan cara perhitungan
interaktif. Sehingga penentuan solusi optimal dengan simpleks dilakukan dengan
thap demi tahap yang disebut interasi.
Perbedaan
kedua metode diatas sangat jelas, bahwa metode grafik hanya mampu digunakan
untuk dua kendala saja. Namun metode simpleks mampu menyelesaikan masalah
dengan lebih dari dua kendala. Itu artinya metode simpleks memiliki minimal
tiga kendala didalamnya.
Salah
satu teknik penentuan solusi optimal yang digunakan dalam pemrograman linier
adalah metode simpleks. Penentuan solusi optimal menggunakan metode
simpleks didasarkan pada teknik eleminasi Gauss Jordan. Penentuan solusi
optimal dilakukan dengan memeriksa titik ekstrim satu per satu dengan cara
perhitungan iteratif. Sehingga penentuan solusi optimal dengan simpleks
dilakukan tahap demi tahap yang disebut dengan iterasi.
5. METODE
PENELITIAN
Ada beberapa istilah yang sangat sering
digunakan dalam metode simpleks, diantaranya :
1. Iterasi adalah
tahapan perhitungan dimana nilai dalam perhitungan itu tergantung dari nilai
tabel sebelumnya.
2. Variabel non basis adalah
variabel yang nilainya diatur menjadi nol pada sembarang iterasi. Dalam
terminologi umum, jumlah variabel non basis selalu sama dengan derajat
bebas dalam sistem persamaan.
3. Variabel basis merupakan
variabel yang nilainya bukan nol pada sembarang iterasi. Pada solusi awal,
variabel basis merupakan variabel slack (jika fungsi kendala merupakan
pertidaksamaan ≤ ) atau variabel buatan (jika fungsi kendala menggunakan
pertidaksamaan ≥ atau =). Secara umum, jumlah variabel basis selalu sama
dengan jumlah fungsi pembatas (tanpa fungsi non negatif).
4. Solusi atau nilai kanan merupakan
nilai sumber daya pembatas yang masih tersedia. Pada solusi awal, nilai kanan
atau solusi sama dengan jumlah sumber daya pembatas awal yang ada, karena
aktivitas belum dilaksanakan.
5. Variabel slack adalah
variabel yang ditambahkan ke model matematik kendala untuk
mengkonversikan pertidaksamaan ≤ menjadi persamaan (=). Penambahan
variabel ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel slack
akan berfungsi sebagai variabel basis.
6. Variabel surplus adalah
variabel yang dikurangkan dari model matematik kendala untuk
mengkonversikan pertidaksamaan ≥ menjadi persamaan (=). Penambahan ini
terjadi pada tahap inisialisasi. Pada solusi awal, variabel surplus tidak dapat
berfungsi sebagai variabel basis.
7. Variabel buatan adalah
variabel yang ditambahkan ke model matematik kendala dengan bentuk ≥ atau =
untuk difungsikan sebagai variabel basis awal. Penambahan variabel ini terjadi pada
tahap inisialisasi. Variabel ini harus bernilai 0 pada solusi optimal, karena
kenyataannya variabel ini tidak ada. Variabel hanya ada di atas kertas.
8. Kolom pivot (kolom kerja) adalah kolom yang memuat variabel masuk. Koefisien pada
kolom ini akn menjadi pembagi nilai kanan untuk menentukan baris pivot (baris
kerja).
9. Baris pivot (baris kerja) adalah salah satu baris dari antara variabel basis yang
memuat variabel keluar.
10. Elemen pivot (elemen
kerja) adalah
elemen yang terletak pada perpotongan kolom dan baris pivot. Elemen pivot akan
menjadi dasar perhitungan untuk tabel simpleks berikutnya.
11. Variabel masuk adalah variabel yang terpilih untuk menjadi
variabel basis pada iterasi berikutnya. Variabel masuk dipilih satu dari antara
variabel non basis pada setiap iterasi. Variabel ini pada iterasi berikutnya
akan bernilai positif.
12. Variabel keluar adalah variabel yang keluar dari variabel
basis pada iterasi berikutnya dan digantikan oleh variabel masuk. Variabel
keluar dipilih satu dari antara variabel basis pada setiap iterasi. Variabel
ini pada iterasi berikutnya akan bernilai nol.
Sebelum
melakukan perhitungan iteratif untuk menentukan solusi optimal, pertama sekali
bentuk umum pemrograman linier dirubah ke dalam bentuk baku terlebih dahulu.
Bentuk baku dalam metode simpleks tidak hanya mengubah persamaan kendala ke
dalam bentuk sama dengan, tetapi setiap fungsi kendala harus diwakili oleh satu
variabel basis awal. Variabel basis awal menunjukkan status sumber daya pada
kondisi sebelum ada aktivitas yang dilakukan. Dengan kata lain, variabel
keputusan semuanya masih bernilai nol. Dengan demikian, meskipun fungsi kendala
pada bentuk umum pemrograman linier sudah dalam bentuk persamaan, fungsi
kendala tersebut masih harus tetap berubah.
Ada beberapa hal yang harus
diperhatikan dalam membuat bentuk baku, yaitu :
- Fungsi
kendala dengan pertidaksamaan ≤ dalam bentuk umum, dirubah menjadi
persamaan (=) dengan menambahkan satu variabel slack.
- Fungsi
kendala dengan pertidaksamaan ≥ dalam bentuk umum, dirubah menjadi
persamaan (=) dengan mengurangkan satu variabel surplus.
- Fungsi
kendala dengan persamaan dalam benttuk umum,ditambahkan satu artificial
variabel (variabel buatan).
6.
PEMBAHASAN
PT.
Sejahtera akan membangun perumahan di daerah Tangerang. Untuk membangun rumah
di lokasi tersebut diperlukan tenaga kerja dan alat berat. Maksimum penyediaan
tenaga kerja adalah 120 orang dan 80 alat berat.
Kebutuhan
|
Per Unit
|
Maksimum Penyediaan
|
|
Type 21
|
Type 36
|
||
Tenaga Kerja
|
4
|
6
|
120 orang
|
Alat Berat
|
4
|
2
|
80 alat
|
Kedua type
tersebut masing-masing memberi keuntungan, untuk type 21 memberi keuntungan
sebesar 300 juta. Sedangkan, untuk type 36 memberi keuntungan sebesar 400 juta.
Jawab:
4X1 + 6X2 + S1 = 120 S1 =
120 – 4X1 – 6X2
4X1 + 2X2 + S2 =
80 S2 =
80 – 4X1 – 2X2
Langkah-langka
penyelesaian:
Langkah 1 : Buat model matematis
Faktor
tujuan è 300X1 + 400X2 + 0S1 +
0S2
Faktor
kendala è 1. 4X1 + 6X2 +
S1 + 0S2 = 120
2.
4X1 + 2X2 + 0S1 + S2 =
80
Integer X1,
X2 ≥ 0
Langkah 2 : Membuat tabel simpleks
BV
|
CV
|
X1
|
X2
|
S1
|
S2
|
Rasio
|
S1
|
120
|
4
|
6
|
1
|
0
|
|
S2
|
80
|
4
|
2
|
0
|
1
|
|
Z
|
0
|
-400
|
-300
|
0
|
0
|
Tabel 1:
Tabel Simpleks
Langkah 3 : Menetukan baris dan kolom kunci sebagai
dasar iterasi
Kolom kunci ditentukan
oleh nilai negatif terbesar
Baris
kunci ditentukan oleh nilai rasio
terkecil
Elemen pivot adalah pertemuan antara baris dan kolom kunci
Rasio merupakan hasil dari perbandingan CV dengan
kolom kunci diluar Z.
BV
|
CV
|
X1
|
X2
|
S1
|
S2
|
Rasio
|
S1
|
60
|
4
|
6
|
1
|
0
|
300
|
S2
|
40
|
4
|
2
|
0
|
1
|
200
|
Z
|
0
|
-400
|
-300
|
0
|
0
|
0
|
Tabel 2: Tabel Dasar Iterasi
Langkah 4 : Iterasi
Iterasi ke-1
Ket.
Variabel yang masuk sebagai variabel basic adalah X1 dan variabel keluar adalah S2
BV
|
CV
|
X1
|
X2
|
S1
|
S2
|
Rasio
|
S1
|
0
|
0
|
4
|
1
|
-1
|
100
|
X1
|
200
|
1
|
0,5
|
0
|
0,5
|
400
|
Z
|
80000
|
0
|
-100
|
0
|
100
|
-800
|
Tabel 3: Iterasi ke-1
#Perhitungan
elemen baris X1(persamaan pivot baru) adalah perbandingan persamaan
pivot lama (elemen baris S2 pada tabel
2) dengan elemen pivot.
#Perhitungan
elemen S1 dan Z (persamaan baru) adalah persamaan lama
(elemen S1 atau Z pada tabel 2) dikurang
dengan hasil kali dari kolom kunci tabel 2 dengan persamaan
pivot baru.
Catatan: jika
elemen Z masih mengandung nilai negatif maka harus dilakukan iterasi kembali
sampai tidak ada nilai negatif pada elemen Z.
Iterasi ke-2
BV
|
CV
|
X1
|
X2
|
S1
|
S2
|
Rasio
|
S1
|
400
|
0
|
4
|
1
|
-1
|
100
|
X1
|
200
|
1
|
0,5
|
0
|
0,5
|
400
|
Z
|
80000
|
0
|
-100
|
0
|
20
|
-800
|
Tabel 3: Iterasi ke-1
BV
|
CV
|
X1
|
X2
|
S1
|
S2
|
Rasio
|
X2
|
100
|
0
|
1
|
0,5
|
-0,5
|
|
X1
|
150
|
1
|
0
|
-0,25
|
0,75
|
|
Z
|
90000
|
0
|
0
|
5
|
15
|
Tabel 4: Iterasi ke-2
7.
KESIMPULAN
Untuk memperoleh
keuntungan yang optimal, maka yang harus dibangun untuk type 21 (X1)
adalah 150 unit dan untuk type 36 (X2) adalah 100 unit dengan
keuntungan sebesar 9 M.
8.
DAFTAR
PUSTAKA
Komentar
Posting Komentar