MAKALAH RISET OPERASI
TUGAS 4
TUGAS 4
WELDIANTORO
17315113
2TA03
DOSEN:ASRI
WULAN
JURUSAN TEKNIK SIPIL
FAKULTAS TEKNIK SIPIL DAN PERENCANAAN
UNIVERSITAS GUNADARMA
1. METODE SIMPLEKS
Metode
simpleks adalah salah satu teknik penyelesaian pemrograman linier selain
menggunakan metode grafis. Metode simpleks diaplikasikan pada komputer dan
metode tersebut sangat membantu untuk permasalahan pemrograman linier yang
rumit karena menggunakan fungsi dan variabel yang banyak dan tak mampu
diselesaikan oleh metode grafis.
1.1 Beberapa istilah dalam metode simpleks:
1. Solusi
augmentasi merupakan sebuah solusi untuk variabel-variabel asli
(variabel-variabel keputusan) yang telah diaugmentasi dengan nilai
variabel-variabel slack yang bersesuaian.
2. Solusi titik sudut
layak (corner-points feasible solution) atau CPF adalah
titik perpotongan dari persamaan fungsi batasan yang memenuhi daerah fesibel.
3. Iterasi adalah
tahapan perhitungan dimana nilai dalam perhitungan itu tergantung dari nilai
tabel sebelumnya.
4. 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.
5. 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).
6. 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.
7. 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
1.2 Solusi basis layak (Basic Feasible Solution)
Solusi basis
layak atau basic feasible solution merupakan solusi dari titik sudut layak
(CPF) dimana nilai variabel-variabel asli (variabel-variabel keputusan) telah
diagumentasi dengan nilai dari variabel-variabel slack yang bersesuaian.
Sifat-sifat solusi basis:
a. Setiap variabel ditunjuk
sebagai variabel nonbasis atau sebagai variabel basis
b. Jumlah variabel basis sama
dengan jumlah fungsi kendala (disebut persamaan). Oleh karena itu, jumlah
variabel nonbasis sama dengan total jumlah variabel dikurangi jumlah fungsi
kendala.
c. Variabel-variabel non basis
ditetapkan sama dengan nol.
d. Nilai-nilai variabel basis
ditetapkan sebagai solusi simultan dari sistem persamaan (fungsi kendala pada
bentuk yang diaugmentasi)
e. Jika variabel basis
memenuhi kendala nonnegatif, solusi basis adalah solusi BF.
1.3 Prosedur penyelesaian program linear dengan
Metode Simpleks BFS
1. Formulasikan persoalan
menjadi model linear
2. Tambahkan variabel Slack
pada masing-masing constraint (pembatas) untuk memperoleh bentuk standar. Model
ini digunakan untuk identifikasi solusi feasible awal dari pembatas bertanda
lebih kecil atau sama dengan.
3. Inisialisasi : pemilihan x1 dan
x2 sebagai variabel nonbasis (variabel diberi nilai nol)
sebagai solusi BF awal didasarkan pada konsep semua variabel keputusan sama dengan
nol sebagai solusi CPF awal. Pemilihan ini menghilangkan pekerjaan yang
diperlukan untuk menyelesaikan variabel basis dari sistem pemrograman linier.
4. Uji optimalitas digunakan
untuk menguji apakah variabel nonbasis menunjukkan laju perbaikan pada nilai Z
jika variabel tersebut ditingkatkan nilainya dari nol (sementara ini variabel
basis disesuaikan nilainya agar memenuhi sistem persamaannya). Jika laju
perbaikan dari variabel tersebut positif maka solusi CPF yang bersebrangan
memiliki penyelesaian lebih baik daripada CPF saat ini sehingga disimpulkan
tidak optimal dan berlanjut ke langkah iterasi selanjutnya. Jika tidak
ditemukan laju pergerakan ke arah positif maka solusi CPF saat ini merupakan
solusi yang optimal dan prosedur pun selesai. Iterasi untuk menemukan BF yang
baru dengan prosedur pencarian solusi simultan pada sistem pemrograman linier
atau disebut metode eliminasi Gauss-Jordan. Kemudian melakukan uji optimalitas
sampai tercapai solusi optimal.
1.4 Metode Simpleks Tabel
Metode simpleks
adalah teknik untuk menyelesaikan program linier yang tidak mampu diselesaikan
oleh metode grafis. Metode simpleks sendiri memiliki kerangka berpikir beberapa
macam yaitu dengan menggunakan BFS (basis fesibel solution) dan metode simpleks
dengan menggunakan tabel. Metode simpleks dengan menggunakan tabel hanya memuat
tiga informasi penting yaitu koefisien pada variabel, konstanta pada ruas kanan
persamaan dan variabel basis yang muncul untuk setiap persamaan.
Langkah langkah metode simpleks tabel:
1) Inisialisasi
Langkah pertama yaitu memasukkan variabel slack.
Kemudian pilihlah variabel keputusan yang kemudian akan dijadikan sebagai
variabel nonbasis awal. Lalu pilihlah varibel slack yang akan dijadikan sebagai
variabel basis awal.
2) Uji Optimalitas
Dalam uji optimalitas, BFS saat ini dapat dikatakan
optimal apabila setiap koefisien dalam baris nol adalah nonnegatif, sehingga
langkah-langkah dalam metode simpleks tabel dapat selesai. Namun apabila setiap
koefisien dalam baris nol adalah bukan nonnegatif, maka langkah
selanjutnya adalah iterasi untuk mendapatkan BFS berikutnya.
3) Iterasi
§
Langkah 1:
Tentukanlah variabel basis yang masuk dengan memilih
variabel dengan koefisien negatif yang mempunyai nilai absolut paling besar
(paling negatif). Kemudian letakkanlah kotak di sekitar kolom dibawah koefisien
tersebut, kolom ini sering disebut kolom sumbu atau pivot column.
§
Langkah 2:
Langkah selanjutnya yaitu dengan menentukan variabel
basis yang keluar. Hal ini dapat dilakukan dengan menerapkan uji rasio minimum
yaitu dengan cara:
1.
Mengambil masing-masing koefiien dalam kolom sumbu
yang positif.
2.
Membagi masing-masing angka pada ruas kanan dengan
koefisien pada kolom sumbu dalam baris yang sama
3.
tentukanlah baris mana yang mempunyai rasio yang paling
kecil
4.
variabel basis pada baris adalah variabel basis yang
keluar, kemudian gantilah variabel itu dengan variabel basis yang masuk dalam
kolom variabel basis tabel simpleks yang berikutnya.
Kemudian letakkanlah kota disekitar baris ini yang
biasa disebut baris sumbu (pivot row) dan angka yang berada dalam baris
sumbu dan kolom sumbu disebut angka sumbu (pivot number).
§
Langkah 3:
Langkah selanjutnya adalah carilah BFS baru
dengan menggunakan operasi baris dasar. Hal ini dimaksudkan
untuk membentuk tabel simpleks yang baru.
2. Metode Big M
Metode Big M
digunakan untuk menyelesaikan fungsi-fungsi dalam program linier yang tidak
berada dalam bentuk baku atau standar ( bentuk standar adalah
memaksimalkan Z sesuai dengan kendala fungsional dalam bentuk ≤ dan
kendala nonegativitas di semua variabel) dan salah satu contoh masalah dalam
kendala funsional adalah bila fungsi dalam bentuk-bentuk = atau ≥ atau bahkan
ruas kanan yang negatif.
Masalah ini
akan muncul bila kita akan mencari basis fesibel awal sehingga sebelum mencari
variabel apa yang akan menjadi variabel nonbasis bahkan basis perlu dilakukan
suatu teknik pendekatan khusus untuk mengubah fungsi tersebut ke bentuk baku
atau standar. Teknik pendekatan khusus tersebut dengan cara menambahkan variabel
dummy (variabel artifisial) pada kendala fungsional dan teknik ini disebut
dengan teknik variabel artifisial.
Ada pun prosedur mendapatkan BF awal pada kendala
fungsional adalah
a.
Gunakan teknik variabel artifisial
Tambahkan
variabel artifisal nonegatif pada fungsi kendala yang belum baku, dan anggaplah
variabel artifial tersebut sebagai salah satu variabel slack
b.
Tugaskan pinalty yang besar
Berilah nilai
variabel artifisial dengan nilai > 0 sehingga koefisien variabel artifisial
menjadi M (big m) secara simbolik yang menunjukkan bahwa variabel artifisial
tersebut memiliki angka positif raksasa ( dan pengubahan atas variabel
artifisial bernilai 0 (variabel nonbasis) dalam solusi optimal disebut metode
big m).
3. Metode Dua Phase
Dalam menyelesaiakan
suatu persoalan dimana variabelnya lebih dari dua, juga menggunakan suatu
metode yang bertahap. Metode ini disebut sebagai metode dua phase.
Pada dasarnya
Metode dua fase (phase) sama seperti metode big M yang juga digunakan untuk
menyelesaikan persoalan pemrograman linier yang memiliki bentuk yang tidak
standar. Berikut ini adalah prosedur menggunakan metode dua fase.
1. Inisialisasi
Menambahkan variabel-variabel artifisal pada fungsi
kendala yang memiliki bentuk tidak standar. Variabel artificial ini ditambahkan
pada fungsi batasan yang pada mulanya memiliki tanda (). Hal ini digunakan
agar dapat mencari solusi basic fesibel awal.
2. Fase
1
Digunakan untuk mencari basic fesibel
awal. Pada fase 1 memiliki langkah-langkah dimana tujuannya adalahm
meminimalkan variabel artifisial ( Min Y= Xa)
s.t : Ax = b
X
= 0
Pada fase pertama bertujuan untuk memperoleh
penyelesaian yang optimum dari suatu permasalahan. Pada fase pertama fungsi
tujuan selalu minimum variabel artificial, meskipun permasalahan yang ada
adalah permasalahan yang maksimum. Dalam meyelesaiakan pada fase pertama, yaitu
membuat nilai nol dulu pada variabel artifisial, kemudian melanjutkan iterasi
seperti proses iterasi biasanya(dengan aturan meminimumkan). Berhenti ketika
pada baris ke-0 bernilai 0.
Fase pertama dianggap telah selesai atau memperoleh
penyelesaian yang optimal adalah apabila variabel artifisial adalah merupakan
variabel basis. Sedangkan apabila variabel artifisial adalah variabel non
basis, maka masalah dianggap tidak mempunyai penyelesaian yang optimal,
sehingga harus dilanjutkan ke fase yang kedua.
Pada fase kedua, tujuannya sama seperti fase pertama,
yaitu untuk mendapatkan penyelesaian yang optimal dari suatu permasalahan yang
ada. Fase dua berhenti sesuai dengan tujuan awal permasalahan.
3. Fase
2
Digunakan untuk mencari solusi optimum pada
permasalahan riil. Karena variabel artifisial bukan merupakan termasuk variabel
dalam permasalahan riil, variabel artifisial tersebut dapat dihilangkan (
Xa=0). Bermula dari solusi BF yang didapatkan dari akhir fase 1. Pada fase 2
ini memiliki langkah-langkah sebagai berikut:
1. Fungsi
tujuan bisa memaksimalkan dan juga bisa meminimalkan tergantung pada
permasalahan yang dihadapi.
2. Menggunakan
fungsi batasan (s.t) dari fase 1, melakukan proses iterasi seperti biasanya dan
berhenti sesuai funsi obyektif awal
Contoh kasus:
1.
Metode simpleks
PT. Sana Group bergerak di bidang
percetakan. Perusahaan ini mencetak Antara lain Novel dan Majalah. Seperti percetakan
lainnya, bahan utama yang diperlukan adalah kertas dan tinta. Dalam prosesnya
juga terbatas oleh waktu yang tersedia. Tentukanlah jumlah novel dan majalah
yang harus diproduksi untuk mendapatkan keuntungan maksimum bila diketahui
sebuah novel memberi keuntungan Rp.3.000 sedangkan majalah memberi keuntungan
Rp.2.000. Persediaan yang ada, yaitu kertas 70 Kg, tinta 40 desiliter dan waktu
90 jam.
Tabel 1.1 Data
Produksi
|
Bahan
|
Jenis Produksi
|
Bahan Yang Tersedia
|
|
|
Novel
|
Majalah
|
||
|
Kertas(Kg)Tinta
(desiliter)
Waktu
(jam)
|
2
1
1
|
1
1
3
|
70
40
90
|
|
Keuntungan
(Ribu rupiah)
|
4
|
6
|
|
Selesaikanlah
permasalahan di atas dengan menggunakan metode simpleks dan grafik!
Jawab:
Dari data diatas dapat dilakukan perhitungan secara manual sebagai berikut :
Jawab:
Dari data diatas dapat dilakukan perhitungan secara manual sebagai berikut :
Formulasi Linear
Programming :
a.
Variabel Keputusan
Novel
= X1
Majalah
= X2
b.
Fungsi objektif
Maksimumkan
Z = 4X1 + 6X2
c.
Kendala-kendala
2X1 +
X2 ≤ 70
X1 +
X2 ≤ 40
X1 +
3X3 ≤ 90
X1,
X2 ≥ 0
Penyelesaian
dengan Metode Simpleks
Persoalan
diatas dapat dicari pemecahannya dengan menggunakan metode simpleks. Untuk
penggunaan teknik simplek maka persoalan terlebih dahulu harus diubah ke dalam
bentuk standar :
Maksimumkan
: Z – 4X1 – 6X2 = 0
Kendala-kendala
: 2X1 + X2 + S1= 70
X1 +
X2 + S2 = 40
X1 +
3X3 + S3 = 90
Tabel 1.2 Simpleks
|
Dasar
|
Z
|
X1
|
X2
|
S1
|
S2
|
S3
|
Solusi
|
Rasio
|
|
ZS1
S2
S3
|
10
0
0
|
-42
1
1
|
-61
1
3
|
01
0
0
|
00
1
0
|
00
0
1
|
070
40
90
|
7040
30
|
Entering variable pada tabel
di atas adalah kolom X2 karena -6 pada baris Z adalah nilai begatif
terbesar. Baris S3 merupakan leaving variable karena memiliki
nilai rasio terkecil, yaitu 30. Oleh karena itu, angka 3 pada entering
variable dan leaving variable merupakan nilai pivotnya. Setelah
itu didapat persamaan pivot baru dengan membagi nilai yang ada pada baris
S3 dengan nilai pivot sebagai berikut:
Tabel 1.3 Baris
Pivot Baru
|
Dasar
|
Z
|
X1
|
X2
|
S1
|
S2
|
S3
|
Solusi
|
Rasio
|
|
ZS1
S2
X2
|
0
|
1/3
|
1
|
0
|
0
|
1/3
|
30
|
Sehingga tabel baru yang lengkap
terlihat sebagai berikut :
Tabel 1.4 Iterasi
|
Dasar
|
Z
|
X1
|
X2
|
S1
|
S2
|
S3
|
Solusi
|
Rasio
|
|
ZS1
S2
X2
|
10
0
0
|
-25/3
2/3
1/3
|
00
0
1
|
01
0
0
|
00
1
0
|
2-1/3
-1/3
1/3
|
18040
10
30
|
2415
90
|
Setelah mendapatkan
tabel baru ternyata didalam baris Z masih terdapat nilai negatif. Untuk itu
dilakukan perhitungan seperti diatas. Dimana pada pembuatan tabel baru kolom
masuk terdapat pada X1 karena memiliki nilai negatif yang paling besar dan
persamaan pivot terdapat pada S2 karena memiliki rasio terkecil.
Tabel 1.5 Baris
Pivot Baru
|
Dasar
|
Z
|
X1
|
X2
|
S1
|
S2
|
S3
|
Solusi
|
Rasio
|
|
Z
S1
X1
X2
|
0
|
1
|
0
|
0
|
3/2
|
-1/2
|
15
|
Sehingga tabel baru yang lengkap
terlihat sebagai berikut :
Tabel 1.6 Iterasi
|
Dasar
|
Z
|
X1
|
X2
|
S1
|
S2
|
S3
|
Solusi
|
|
Z
S1
X1
X2
|
1
0
0
0
|
0
0
1
0
|
0
0
0
1
|
0
1
0
0
|
3
-5/2
3/2
-1/2
|
1
1/2
-1/2
1/2
|
210
15
15
25
|
Jadi, jumlah novel
dan majalah yang harus diproduksi adalah 15 dan 25 unit dengan keuntungan
maksimum sebesar 210.
2. Metode Big M
Min. z = 4 x1 + x2
Terhadap:
3x1 + x2 = 3
3x1 + x2 = 3
4x1 + 3x2 ≥ 6
x1 + 2x2 ≤ 4
x1, x2 ≥ 0
Bentuk Baku:
Min. z = 4 x1 + x2
Terhadap:
3x1 + x2 = 3
4x1 + 3x2 - s1 = 6
x1 + 2x2 + s2 = 4
x1 + 2x2 + s2 = 4
x1, x2, s1, s2 ≥ 0
Kendala 1 dan 2 tidak
mempunyai slack variables, sehingga tidak ada variabel basis awal. Untuk
berfungsi sebagai variabel basis awal, pada kendala 1 dan 2 ditambahkan
masing-masing satu variabel buatan (artificial variable). Maka bentuk baku Big
M-nya adalah:
Min. z = 4 x1 + x2 + MA1 + MA2
Terhadap:
3x1 + x2 + A1 = 3
4x1 + 3x2 - s1 + A2 = 6
x1 + 2x2 + s2 = 4
x1, x2, s1, s2 ≥ 0
1. Nilai A1 digantikan dari fungsi kendala pertama.
A1 = 3 - 3x1 - x2
MA1 berubah menjadi M(3 -
3x1 - x2) 3M-3Mx1-Mx2
2. Nilai A2 digantikan dari fungsi kendala ketiga.
A2 = 6 - 4x1 - 3x2 + s1
MA2 berubah menjadi M(6 -
4x1 - 3x2 + s1)
6M- 4Mx1 - 3Mx2 + Ms1
3. Fungsi tujuan berubah menjadi
Min z = 4x1 + x2 +
3M-3Mx1-Mx2 +6M-4Mx1-3Mx2+Ms1
= (4 -7M)x1+(1 - 4M)x2 + Ms1 +9M
5.
Tabel awal simpleks
|
VB
|
X1
|
X2
|
S1
|
A1
|
A2
|
S2
|
Solusi
|
|
z
|
-4 +7M
|
-1 +4M
|
-M
|
0
|
0
|
0
|
9M
|
|
A1
|
3
|
1
|
0
|
1
|
0
|
0
|
3
|
|
A2
|
4
|
3
|
-1
|
0
|
1
|
0
|
6
|
|
S2
|
1
|
2
|
0
|
0
|
0
|
1
|
4
|
3.
Metode dua fase
Tahap 1
Min A = A1 + A2
Terhadap: x1 + x2 + A1 = 90
0.001x1 + 0.002x2 + s1 = 0.9
0.09x1 + 0.6x2 -s2 + A2 = 27
0.02x1 + 0.06x2 + s3 = 4.5
x1, x2, s1, s2, s3 ≥ 0
karena A1 dan A2 berfungsi
sebagai variabel basis pada solusi awal, maka koefisiennya pada fungsi tujuan
harus sama dengan 0. untuk mencapai itu, gantikan nilai A1 dari fungsi kendala
pertama (kendala yang memuat A1) dan nilai A2 dari fungsi kendala ketiga
(kendala yang memuat A2). Dari kendala -1 diperoleh : A1 = 90 - x1 - x2
Dari
kendala-3
diperoleh:
A2
= 27 - 0.09x1 - 0.6x2 + s2
Maka
fungsi tujuan tahap-1 menjadi:
Min
A = (90 - x1 - x2) + (27 - 0.09x1 - 0.6x2 + s2)
=117
- 1.09x1 - 1.6x2 + s2
|
Solusi awal VB
|
X1
|
|
X2
|
|
S1
|
|
S2
|
|
S3
|
|
A1
|
|
A2
|
NK
|
Rasio
|
|
|
A
|
1.09
|
|
1.6
|
|
0
|
|
-1
|
|
0
|
|
0
|
|
0
|
117
|
-
|
|
|
A1
|
1
|
|
1
|
|
0
|
|
0
|
|
0
|
|
1
|
|
0
|
90
|
90
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S1
|
0.001
|
|
0.002
|
|
1
|
|
0
|
|
0
|
|
0
|
|
0
|
0.9
|
450
|
|
|
A2
|
0.09
|
|
0.6
|
|
0
|
|
-1
|
|
0
|
|
0
|
|
1
|
27
|
45
|
|
|
S3
|
0.02
|
|
0.06
|
|
0
|
|
0
|
|
1
|
|
0
|
|
0
|
4.5
|
75
|
|
|
|
||||||||||||||||
Tahap 2
Min z = 2 x1 + 5.5 x2
Terhadap: tabel optimal tahap pertama
Dari tabel optimal tahap 1 diperoleh:
X1 = 52.94 – 17/12s2
X2 = 37.059 + 1.7542s2
Maka fungsi tujuan adalah:
Min z = 2(52.94 – 17/12s2) + 5.5 (37.059 + 1.7542s2)
= -17/6s2 + 9.6481s2 + 309.7045 = 6.814767s2 + 309.7045
|
Solusi awal optimal. VB
|
X1
|
X2
|
S1
|
S2
|
S3
|
NK
|
|
z
|
0
|
0
|
0
|
-6.814767
|
0
|
309.7045
|
|
X1
|
1
|
0
|
0
|
17/12
|
0
|
52.94
|
|
S1
|
0
|
0
|
1
|
0.0023417
|
0
|
0.772942
|
|
X2
|
0
|
1
|
0
|
-1.7542
|
0
|
37.059
|
|
S3
|
0
|
0
|
0
|
0.09358
|
1
|
1.21766
|
Tabel di atas sudah optimal. Solusi optimalnya
adalah:
X1 = 52.94; x2 = 37.059; dan z = 309.7045
Sumber: