Nama: Mulyadi
Nim: G1D 008 018
Hal: Tugas
PROGRAM LINIER
Persoalan dalam kehidupan sehari-hari yang diselesaikan dengan program linier tidak selalu sederhana dan semudah sebagaimana yang diberikan pada bangku-bangku sekolah. Kesederhanaan yang dimaksud mungkin terbatas pada dua variable saja, akan tetapi bagaimana kalau dihadapkan dengan lebih dari dua variable dan banyaknya pelibatan pembatas (constraint)?. Dan sangat tidak memungkinkan jika kita menggunakan prosedur penyelesaian dengan metode grafik yang masih dalam ruang lingkup cakupannya sangat sempit. Oleh karena itu, prosedur yang mampu menjawabnya hanyalah prosedur yang mempunyai cakupan luas, yaitu metode simplex, kelebihannya selain itu, juga mampu membuat tangga lompatan dalam bidang riset dan sangat banyak diterapkan dalam berbagai applikasi computer.
(sigma dari j=1 _n)aijXj>=bi………………….1
(sigma dari j=1 _n)aijXj<=bi…………………..2
(sigma dari j=1 _n)aijXj=bi……………….….3
Dari ke-3 kendala tersebut, dan fungsi kendala yang masih berbentuk pertidaksamaan harus diubah dalam bentuk persamaan biasa dengan ketentuan sebagai berikut.
jika berbentuk seperti ini, maka ditambahkan variable pengetat misal “si”, maka persamaan akan menjadi
dan jika berbentuk maka ditambahkan variable pengetat “(–si)”, maka persamaan menjadi .
Persamaan fungsi kendala utama yang telah ditambahkan variable pengetat biasa disebut persamaan bentuk kanonik.
Jika menemukan fungsi kendala utama kurang dari maka logikanya untuk membuat sama maka tentunya ditambahkan dengan sesuatu, dan sebaliknya jika fungsi kendalanya lebih besar dari maka dikurangi variable hingga sama.
Dari pengenalan diatas dapat disusun algoritma program linier dengan metode simplex
Langkah 1 Mengubah fungsi kendala/batasan dalam bentuk kanonik
Langkah 2 Mengubah fungsi tujuan dengan memaksimumkan atau meminimumkan menjadi persamaan dengan me nolkan fungsi tujuan, misal z=x1+x2+0s1+0s2 menjadi z-x1-x2-0s1-0s2=0
Langkah 3 Membuat table simplex
Langkah 4 Menentukan kolom kunci dengan memilih z yang paling negative untuk maksimasi dan sebaliknya untuk minimasi
Langkah 5 Menentukan baris kunci dengan mengambil indeks positif terkecil setelah bi dengan kolom kunci
Langkah 6 Menentukan angka kunci yang merupakan perpotongan dari kolom dan baris kunci
Langkah 7 Operasi Baris Elementer (OBE) untuk memaksimasi atau meminimasi
Langkah 8 Jika belum maksimasi atau minimasi maka langkah 4-7 diulang kembali hingga tercapai optimum
Langkah 9 Maksimasi ditandai denganz>=0dan minimasi z<=0
Agar benar-benar dipahami secara keseluruhan maka telaah contoh dibawah ini dengan seksama.
Misal pada suatu perusahaan tas didapatkan datanya berupa
Fungsi tujuan untuk memaksimalkan perolehan pendapat, yaitu:
Max. Z = 3X1 + 2X2
2X1 + 2X2 800
2X1 + 3.3X2 1000
1X1 + 0.5X2 300
2X1 + 1.5X2 <= 650
Solusi
Langkah 1 mengubah dalam bentuk kanonik
2X1 + 2X2 + S1 =800
2X1 + 3.3X2 + S2 =1000
1X1 + 0.5X2 +S3 =300
2X1 + 1.5X2 +S4 = 650
Langkah 2. memaksimumkan fungsi tujuan
Z = 3X1 + 2X2+0S1+0S2+0S3+0S4
Z -3X1 – 2X2-0S1-0S2-0S3-0S4=0
Langkah 3 mengxisi tabel simple
Dv |
X1 |
X2 |
S1 |
S2 |
S3 |
S4 |
bi |
Z |
-3 |
-2 |
0 |
0 |
0 |
0 |
0 |
S1 |
2 |
2 |
1 |
0 |
0 |
0 |
800 |
S2 |
2 |
3.3 |
0 |
1 |
0 |
0 |
1000 |
S3 |
1 |
0.5 |
0 |
0 |
1 |
0 |
300 |
S4 |
2 |
1.5 |
0 |
0 |
0 |
1 |
650 |
Langkah 4 menentukan kolom kunci, yaitu pada kolom x1
Dv |
X1 |
X2 |
S1 |
S2 |
S3 |
S4 |
bi |
Z |
-3 |
-2 |
0 |
0 |
0 |
0 |
0 |
S1 |
2 |
2 |
1 |
0 |
0 |
0 |
800 |
S2 |
2 |
3.3 |
0 |
1 |
0 |
0 |
1000 |
S3 |
1 |
0.5 |
0 |
0 |
1 |
0 |
300 |
S4 |
2 |
1.5 |
0 |
0 |
0 |
1 |
650 |
Langkah 5 menentukan baris kunci, yaitu baris pada s3
Dv |
X1 |
X2 |
S1 |
S2 |
S3 |
S4 |
bi |
index |
Z |
-3 |
-2 |
0 |
0 |
0 |
0 |
0 |
0 |
S1 |
2 |
2 |
1 |
0 |
0 |
0 |
800 |
400 |
S2 |
2 |
3.3 |
0 |
1 |
0 |
0 |
1000 |
500 |
S3 |
1 |
0.5 |
0 |
0 |
1 |
0 |
300 |
300 |
S4 |
2 |
1.5 |
0 |
0 |
0 |
1 |
650 |
325 |
Langkah 6 menentukan angka kunci, yaitu 1 pada baris di s3
Dv |
X1 |
X2 |
S1 |
S2 |
S3 |
S4 |
bi |
Z |
-3 |
-2 |
0 |
0 |
0 |
0 |
0 |
S1 |
2 |
2 |
1 |
0 |
0 |
0 |
800 |
S2 |
2 |
3.3 |
0 |
1 |
0 |
0 |
1000 |
S3 |
1 |
0.5 |
0 |
0 |
1 |
0 |
300 |
S4 |
2 |
1.5 |
0 |
0 |
0 |
1 |
650 |
Langkah 7 operasi OBE
Dv |
X1 |
X2 |
S1 |
S2 |
S3 |
S4 |
bi |
Z |
0 |
-0.5 |
0 |
0 |
3 |
0 |
900 |
S1 |
0 |
1 |
1 |
0 |
-2 |
0 |
200 |
S2 |
0 |
2.3 |
0 |
1 |
-2 |
0 |
400 |
S3 |
1 |
0.5 |
0 |
0 |
1 |
0 |
300 |
S4 |
0 |
0.5 |
0 |
0 |
-2 |
1 |
50 |
Langkah 8 operasi OBE yang kedua
Dv |
X1 |
X2 |
S1 |
S2 |
S3 |
S4 |
bi |
Z |
0 |
0 |
0 |
0 |
-1 |
-1 |
950 |
S1 |
0 |
0 |
1 |
0 |
2 |
-2 |
100 |
S2 |
0 |
0 |
0 |
1 |
7.2 |
-4.6 |
170 |
S3 |
1 |
0 |
0 |
0 |
3 |
-1 |
250 |
S4 |
0 |
1 |
0 |
0 |
-4 |
2 |
100 |
Langkah 9 karena pada OBE ke-2 sudah maksimaum, maka
Karena z>=0pada OBE yang ke-2 maka titik optimum sudah bisa terlihat dengan…
X1=250
X2=100
S1=100
S2=170
Zmax=950
Interpretasi Solusi Optimal
Dari baris evaluasi neto tidak lagi ditemukan nilai positif yang berarti
solusi yang diperoleh sudah maksimum, yaitu X1 = 250, X2 = 100 dan nilai
fungsi tujuan Zj = 950 ( dalam puluhan ribu rupiah)
Dari tabel tersebut diketahui S1 = 100 dan S2 = 170 yang berarti waktu
kerja pada bagian pemotongan masih tersisa (slack) 100 jam sedangkan sisa
waktu pada bagian penjahitan adalah 170 jam. Pada bagian lainnya
(penyelesaian, pemeriksaan & pengepakan) seluruh waktu kerja sudah habis
digunakan.
Merujuk kembali pada gambar terdahulu diketahui bahwa solusi optimal
bergerak mulai dari titik ekstem 1 dengan solusi awal X1=0, X2=0, S1=800,
S2=1000, S3=300, S4=650 dan menghasilkan nilai fungsi tujuan nol. Pada
iterasi pertama variabel X1 memasuki basis dan mengakibatkan variabel S3
menjadi non basic variabel. Solusi basic kedua berada pada titik ekstem 2
yaitu X1=300, X2=0, S1=200, S2=400, S3=0, dan S4=50 serta menghasilkan
nilai 900 pada fungsi tujuan. Pada iterasi selanjutnya X2 memasuki basis
mendorong S4 untuk keluar. Hal ini menyebabkan solusi bergerak kearah sumbu
X2 menuju titik ekstem 3. Pada titik ini solusi yang didapat sudah optimum
yaitu X1=250, X2=100, S1=100, S2=170, S3=0 dan S4=0 sedangkan nilai fungsi tujuan maksimum yaitu 950.