Modul Praktikum Program Linier TORA PDF

Preview

Summary

BAB I SOFTWARE TORA DAN PENYELESAIAN PROGRAM LINEAR CARA GRAFIK 1.1.TUJUAN PRAKTIKUM a. Mengenalkan fasilitas yang ada pada software TORA beserta cara-cara penggunaannya b. Menyelesaikan masalah program linear dengan cara grafik. 1.2.LANDASAN TEORI Pemrograman linear adalah salah satu cabang dari ri...

Description

BAB I SOFTWARE TORA DAN PENYELESAIAN PROGRAM LINEAR CARA GRAFIK

1.1.TUJUAN PRAKTIKUM a.

Mengenalkan fasilitas yang ada pada software TORA beserta cara-cara penggunaannya

b.

Menyelesaikan masalah program linear dengan cara grafik.

1.2.LANDASAN TEORI Pemrograman linear adalah salah satu cabang dari riset operasi yang mempelajari masalah-masalah optimasi, dengan fungsi tujuan (obyektif) maupun fungsi-fungsi kendalanya berupa fungsi linear. Bentuk umum masalah pemrograman linear adalah sebagai berikut : Optimumkan (Maksimumkan/ Minimumkan) z = f (x1, x2, …, xn)

terhadap kendala

g1 ( x1 , x 2 ,..., x n )  ≤  b1   : . =  . ≥ . bm g m ( x1 , x 2 ,..., x n )

dan kendala tak negatif : x1, x2, …, xn ≥ 0 Keterangan: z : fungsi tujuan gi ,i = 1,2,…, m : fungsi kendala bi ,i = 1,2, …, m : konstanta ruas kanan xj ,j = 1, 2, …, n : variabel keputusan Penyelesaian

masalah

yang

memenuhi

semua

kendala

disebut

penyelesaian fisibel, sedangkan penyelesaian fisibel yang memenuhi fungsi tujuannya disebut penyelesaian optimal.

2

Pada masalah pemrograman linear, metode penyelesaiannya sudah standar yaitu menggunakan metode simpleks. Khusus untuk masalah yang melibatkan 2 variabel, cara grafik dapat dilakukan. Pada Bab I ini, diberikan cara-cara penggunaan TORA untuk menyelesaikan masalah program linear menggunakan cara grafik. Pada awalnya digambarkan lebih dulu himpunan penyelesaian fisibel (HPF) yang merupakan irisan dari himpunan penyelesaian semua kendala. Penyelesaian dengan cara grafik pada intinya adalah menentukan titik (himpunan titik) optimum dari suatu HPF dengan cara menggeser-geser grafik fungsi obyektif kearah maksimum/ minimum hingga menyinggung HPF pada terakhir kali. 1.3.PROSEDUR MENJALANKAN TORA (Penyelesaian Cara Grafik) Untuk menyelesaikan masalah program linear (cara grafik) menggunakan software TORA, berikut ini diberikan langkah-langkah yang perlu dilakukan. 1.Pada tampilan awal TORA (Gambar 1.1), ikuti perintah yang ada

Gambar 1.1. Tampilan awal TORA

3

2.Pada tampilan menu utama terdapat beberapa pilihan program, misalnya: Linear Equation, Linear Programming, Transportation Model, dsb. (Gambar 1.2). Pilih (klik) pada menu Linear Programming. 3. a. Pada opsi Select Input Mode (Gambar 1.3): i. Pilih (klik) Enter New Problem jika akan membuat program baru ii. Pilih (klik) Select Existing File jika akan memanggil file data program yang sudah disimpan. b. Pada opsi Select Input Format, isikan format input data (banyak digit angka di depan/ belakang koma) yang dikehendaki. c. Pilih (klik) opsi Go to Input Screen.

Gambar 1.2. Menu utama

4

Gambar 1.3. Pilihan Input Mode 4. Isikan judul masalah (Problem Title), banyaknya variabel (No. of Variables) dan banyaknya kendala (No. of Constraint) untuk kendala utama (selain kendala non negatif). Kemudian tekan tombol Enter (Gambar 1.4). 5. Masukkan data : a. Nama variabel b. Pilih (klik) sel maximize/ minimize untuk mengerjakan masalah minimisasi/ maksimisasi. c. Isikan koefisien pada fungsi tujuan z d. Isikan koefisien-koefisien pada semua fungsi kendala, juga tanda ketidaksamaan dan konstanta ruas kanan. 6. Pilih (klik) Solve Menu 7. Pilih menu simpan/ tidak simpan data. 8. Pilih (klik) Solve Problem untuk proses penyelesaian masalah. Selanjutnya ada beberapa opsi cara penyelesaian masalah, yaitu cara grafik (Graphical) atau cara aljabar/ simpleks (Algebraic). Pilih (klik) pada opsi Graphical.(Gambar 1.5)

5

Gambar 1.4. Tampilan untuk Problem Title

Gambar 1.5. Pilihan cara penyelesaian

6

9. Isikan format outputnya seperti pada langkah ke-3b. Selanjutnya klik menu Go to Input Screen. 10. Pada tampilan grafik penyelesaian masalah (Gambar 1.6), lakukan: a. Klik 1 kali untuk setiap kendala, kemudian klik fungsi tujuan. b. Terlihat grafik HPF (himpunan penyelesaian fisibel), grafik fungsi tujuan z dan titik optimumnya. Di bagian bawah rumusan model program linear tertulis penyelesaian optimalnya. 11. Jika akan melihat sensitivitas masalah terhadap perubahan model, dapat di klik pada menu View/ Modify Input Data. 12. Klik menu Exit TORA pada bagian bawah layar, untuk keluar dari TORA.(Gambar 1.6)

Gambar 1.6. Tampilan model dan tempat grafik HP

7

1.4. CONTOH Diketahui masalah nyata sebagai berikut (Taha, 1993): Pabrik cat “Reddy Mikks” memproduksi cat interior dan eksterior serta selalu menjual semua produknya. Dua bahan A dan B digunakan untuk produknya. Kebutuhan

per

hari

masing-masing

bahan

untuk

cat

dan

persediaan

maksimumnya sebagai berikut: Bahan

Bahan(dlm ton) / ton cat

Persediaan maksimum

Eksterior

interior

bahan (dalam ton)

Bahan A

1

2

6

Bahan B

2

1

8

Survey menunjukkan bahwa permintaan harian cat interior melebihi cat eksterior tidak lebih dari 1 ton. Permintaan maksimum untuk cat interior adalah 2 ton/ hari. Harga penjualan per ton untuk cat eksterior adalah $ 3000 dan cat interior adalah $ 2000. Permasalahannya adalah akan ditentukan banyaknya cat interior dan eksterior diproduksi per hari supaya hasil penjualan maksimum. a. Tuliskan model program linearnya b. Tentukan hasil optimum masalah tersebut menggunakan TORA dengan cara grafik. Penyelesaian : a. Untuk menyusun model program linearnya, beberapa langkah yang harus dilakukan adalah: 1. Identifikasi variable Ada 2 variabel yaitu xe = banyak produk cat eksterior xi = banyak produk cat interior 2. Identifikasi fungsi obyektif/ fungsi tujuan Fungsi obyektifnya adalah: z = 3000xe + 2000xi = 3xe + 2xi (ribu $)

8

Tujuannya: menentukan nilai xe dan xi sehingga z maksimum 3. Identifikasi fungsi-fungsi kendala: i. Penggunaan bahan kedua cat ≤ persediaan maksimum bahan. Jadi diperoleh : xe + 2 xi ≤ 6 ( bahan A ) 2xe + xi ≤ 8 ( bahan B ) ii. Kelebihan cat interior terhadap eksterior ≤ 1 ton / hari. Jadi diperoleh : xi - xe ≤ 1 iii. Permintaan maksimal cat interior ≤ 2 ton / hari Jadi diperoleh : xi ≤ 2 iv. Kendala tersembunyi (hidden condition) : besar produk setiap cat tidak dapat negatif. Jadi diperoleh : xi ≥ 0 , xe ≥ 0 (syarat tak negatif) Model program linear lengkapnya sbb: Menentukan xe , xi untuk Memaksimumkan z = 3 xe + 2 xi Terhadap kendala : xe + 2 xi ≤ 6 2xe + xi ≤ 8 - x e + xi ≤ 1 xi ≤ 2 xi , xe ≥ 0 b. Menentukan penyelesaian optimum (maksimum) menggunakan TORA. Dengan mengikuti prosedur penggunaan TORA yang sudah diberikan di atas dan memasukkan data model program linearnya, diperoleh tampilan pada

Gambar

1.7.

Selanjutnya,

setelah

perintah

Solve

Problem

menggunakan cara grafik (Graphical), diperoleh grafik HPF dan penyelesaian optimalnya seperti pada Gambar 1.8.

9

Gambar 1.7. Tampilan sesudah data dimasukkan

Gambar 1.8. HPF dan penyelesaian optimal

10

Hasil optimum (dalam hal ini adalah maksimum) sebagai berikut: Banyak produk cat eksterior (xe), dalam model adalah x1 = 3,33 ton Banyak produk cat interior (xi), dalam model adalah x2 = 1,33 ton Hasil penjualan maksimum adalah z = 12,67 (ribu $) 1.5.SOAL-SOAL LATIHAN Selesaikan soal-soal berikut menggunakan manual/ software TORA 1. Produksi mobil. (Winston, 1994) Perusahaan automobile memproduksi mobil jenis sedan dan truk. Setiap jenis mobil harus diproses melalui bagian pengecatan dan bagian assembling. Jika bagian pengecatan hanya mengecat truk, maka 40 truk per hari dapat diproses. Jika hanya mengecat sedan, 60 sedan per hari dapat diproses. Di bagian assembling, jika hanya memproses sedan, maka 50 sedan/ hari dapat diproses. Tetapi jika hanya memproses truk, 50 truk/ hari dapat diproses. Setiap truk memberikan $300 keuntungan, dan setiap sedan memberikan $200 keuntungan. Gunakan program linear untuk menentukan skedul produksi harian yang akan memaksimumkan keuntungan perusahaan. 2. Produksi monitor komputer. Suatu pabrik perakitan monitor komputer memproduksi 2 model (model A dan model B) di tempat perakitan yang sama. Tempat perakitan tersebut terdiri dari 3 unit kerja dan masing-masing produk harus melewati proses perakitan di ke-3 unit tersebut. Waktu perakitan di 3 unit kerja tersebut terlihat pada Tabel 1.1. Tiap unit kerja menyediakan waktu untuk proses perakitan dalam sehari adalah: 20 jam (untuk unit 1), 18 jam (untuk unit 2) dan 19 jam (untuk unit 3). Harga penjualan masing-masing monitor adalah: $500 (untuk model A) dan $450 (untuk model B).

11

Tabel 1.1 Jumlah jam/ unit monitor

Unit kerja

Model A

Model B

1

4

4

2

3

4

3

5

3

Berapa unit produksi masing-masing monitor dalam sehari agar hasil penjualan maksimum? 3. Kebutuhan kapsul obat. (Susanto, 1982) Tersedia 2 macam kapsul obat flu, yaitu fluin dan fluon yang masing-masing memuat unsur-unsur aspirin, bikarbonat dan kodein. Kandungan unsur dalam masing-masing kapsul dan syarat kebutuhan minimum pasien akan unsurunsur tersebut supaya sembuh tertera dalam Tabel 1.2. Satuan unsur dalam grain, harga dalam ratusan rupiah. Masalah : Berapa banyak fluin dan fluon yang harus dibeli supaya pasien sembuh dan ongkos beli minimum ? a. Buat model program linearnya b. Selesaikan masalah tersebut menggunakan manual/ TORA Tabel 1.2 Untuk per kapsul Unsur-unsur

Minimum kebutuhan

fluin

fluon

(dlm grain)

Aspirin

2

1

12

Bikarbonat

5

8

74

Kodein

1

6

24

Harga satuan

20

30

12

4. Maksimumkan : z = 5x1 + x2 terhadap kendala : - x1 + x2 ≤ 6 6x1 + x2 ≥ 6 x1 , x2 ≥ 0 5. Maksimumkan : z = x + y terhadap kendala : 2x + y ≤ 6 x + 3y ≤ 9 x

≥4

x , y ≥ 0.

13

BAB II PENYELESAIAN CARA ALJABAR (METODE SIMPLEKS )

2.1.TUJUAN PRAKTIKUM Menyelesaikan masalah program linear dengan cara simpleks. 2.2.LANDASAN TEORI Untuk masalah program linear (PL) yang memuat lebih dari 2 variabel, penyelesaian cara grafik tidak dapat dilakukan. Cara penyelesaian standar yang dapat dilakukan adalah menggunakan cara aljabar (yaitu metode simpleks). Penyelesaian dengan manual, pada langkah awal , masalah PL dibawa ke bentuk standar lebih dahulu, yaitu dengan membuat semua kendala menjadi bertanda “=”, dengan cara sebagai berikut: a.

Untuk kendala bertanda “≤”, pada ruas kiri tambahkan variabel slack yang nilainya non negatif.

b.

Untuk kendala bertanda “≥”, pada ruas kiri kurangkan variabel surplus yang nilainya non negatif.

Jika semua kendala sudah bertanda “=”, pada masalah PL yang semua kendalanya memuat variabel slack, data sudah siap dimasukkan ke tabel simpleks (secara manual). Tetapi untuk masalah yang ada kendala tidak memuat variabel slack, maka pada kendala yang tidak memuat variabel slack tersebut tambahkan variabel semu yang nilainya non negatif (pada kondisi optimal, variabel ini seharusnya bernilai nol). Selanjutnya masalah sudah siap diselesaikan dengan cara simpleks secara manual. Contoh 2.1: Perhatikan masalah program linear dari kasus pabrik cat “Reddy Mikks” (Taha, 1987) Memaksimumkan z = 3x1 + 2x2 terhadap kendala:

x1 + 2x2 ≤ 6

14

2x1 + x2 ≤ 8 -x1 +

x2 ≤ 1 x2 ≤ 2

x1 , x2 ≥ 0 Bentuk standar modelnya adalah sebagai berikut: Memaksimumkan z = 3x1 + 2x2 terhadap kendala:

x1 + 2x2 + sx3 2x1 + x2 -x1 +

=6

+ sx4

x2

=8 + sx5

x2

=1

+ sx6 = 2

x1 , x2 , sx3 , sx4 , sx5 , sx6 ≥ 0 Terlihat bahwa semua kendala memuat variabel slack, secara manual data sudah siap dimasukkan ke tabel simpleks. Perlu dicatat bahwa pada praktikum ini, penyusunan ke bentuk standar tidak dilakukan karena program TORA sudah langsung memproses dari bentuk masalah aslinya. Jika semua kendala memuat variabel slack (yaitu semua kendala bertanda “≤”), maka data sudah siap diisikan ke tabel simpleks, sehingga opsi yang dipilih adalah All-slack starting solutions. Tetapi jika ada kendala yang memuat variabel semu (yaitu ada kendala yang bertanda “≥” atau “=”), cara yang digunakan adalah metode M atau metode Dua-Phase, sehingga opsi yang dipilih adalah M-method atau Two-phase method. Pada praktikum ke-2 ini dibahas lebih dulu untuk masalah PL yang semua kendalanya bertanda “≤” . 2.3.PROSEDUR MENJALANKAN TORA (Cara Simpleks tanpa Variabel Semu) Pada prosedur untuk menyelesaikan masalah PL dengan cara simpleks, langkah ke-1 s/d ke-7 sama dengan prosedur penyelesaian cara grafik. Perbedaan lankah dimulai pada langkah ke-8. Adapun langkah-langkahnya sebagai berikut: 1.Pada tampilan awal TORA, ikuti perintah yang ada

15

2. Pada tampilan menu utama terdapat beberapa pilihan program, misalnya: Linear Equation, Linear Programming, Transportation Model, dsb. Pilih (klik) pada menu Linear Programming. 3a. Pada opsi Select Input Mode: i. Pilih (klik) Enter New Problem jika akan membuat program baru ii. Pilih (klik) Select Existing File jika akan memanggil file data program yang sudah disimpan. b. Pada opsi Select Input Format, isikan format input data (banyak digit angka di depan/ belakang koma) yang dikehendaki. c. Pilih (klik) opsi Go to Input Screen. 4. Isikan judul masalah (Problem Title), banyaknya variabel (No. of Variables) dan banyaknya kendala (No. of Constraint) untuk kendala utama (selain kendala non negatif). Kemudian tekan tombol Enter . 5. Masukkan data : a. Nama variable b. Pilih (klik) sel maximize/ minimize untuk mengerjakan masalah minimisasi/ maksimisasi. c. Isikan koefisien pada fungsi tujuan z d. Isikan koefisien-koefisien pada semua fungsi kendala, juga tanda ketidaksamaan dan konstanta ruas kanan. 6. Pilih (klik) Solve Menu 7. Pilih menu simpan/ tidak simpan data. 8. Pilih (klik) Solve Problem untuk proses penyelesaian masalah. Selanjutnya ada beberapa opsi cara penyelesaian masalah, yaitu cara grafik (Graphical) atau cara aljabar/ simpleks (Algebraic), perhatikan Gambar 2.1. Pilih (klik) pada opsi Algebraic, selanjutnya ada opsi Final solution dan Iterations. a. Jika diinginkan tabel hasil akhir, pilih opsi Final solution, selanjutnya pengaturan format output seperti langkah 2b dan klik sesuai perintah. Selanjutnya muncul tabel hasil akhir.

16

b. Jika diinginkan hasil pada tiap iterasi, pilih opsi Iterations. Untuk masalah dengan semua kendala bertanda “≤”, setelah opsi Iterations dilanjutkan opsi Allslack starting solutions. Berikutnya pengaturan format output (seperti langkah 2b) dan klik sesuai perintah. Selanjutnya muncul tampilan tabel iterasi ke-1.

Gambar 2.1. Pilihan Solve Menu 9. Sesudah tampilan tabel iterasi ke-1, jika belum optimal maka iterasi berikutnya akan dikerjakan. Hal ini dapat dilakukan dengan klik pada opsi Next iterations (pada tampilan menu, baris teratas paling kiri), dan langsung diperoleh tabel iterasi ke-2. Atau jika diinginkan menentukan entering variable (ev) dan leaving variable (lv) masing-masing di klik pada posisi variabel non basis (baris ke-1 pada tabel) atau posisi variabel basis (kolom ke-1 pada tabel). Kolom ev akan berwarna hijau, sedangkan baris lv akan berwarna merah. Jika belum mencapai optimal, lanjutkan lagi ke iterasi berikutnya dengan cara seperti di atas (langkah ke-9), sampai diperoleh hasil optimal (hal ini akan ditunjukkan dengan tampilan pemberitahuan pada layar)

17

2.4.CONTOH Pada praktikum ini diselesaikan masalah pada Contoh 2.1 di atas dengan semua kendala bertanda “≤”. Perlu dicatat bahwa untuk praktikum, rumusan masalahnya tidak perlu dibawa ke bentuk standar. Menggunakan TORA, data pada model aslinya (bukan bentuk standar) diisikan ke tabel (langkah ke-5), sehingga diperoleh tampilan pada Gambar 2.2. Selanjutnya pada langkah ke-8, jika dipilih opsi Final solution, diperoleh tampilan pada Gambar 2.3 yang merupakan hasil akhir (optimal). Tetapi jika dipilih opsi Iterations, dilanjutkan opsi All-slack starting solutions, diperoleh tampilan tabel iterasi ke-1 pada Gambar 2.4 yang belum optimal. Dengan klik opsi Next iteration, akan muncul tabel iterasi berikutnya. Begitu dilakukan seterusnya sampai diperoleh tabel akhir (optimal) seperti pada Gambar 2.3.

Gambar 2.2. Tampilan sesudah data diisikan

18

Gambar 2.3. Tampilan hasil akhir (optimal)

Gambar 2.4. Tampilan tabel iterasi ke-1

19

2.5.SOAL-SOAL LATIHAN Selesaikan soal-soal berikut menggunakan manual maupun software TORA. 1. Maksimumkan: z = 2x1 + 3x2 terhadap kendala: x1 + 3x2 ≤ 6 3x1 + 2x2 ≤ 6 x1 , x2 ≥ 0 2. Minimumkan: z = x1 + 2x2 + 3x3 terhadap kendala : x1 + 2x2 + x3 ≤ 10 x1 + x2

≤5

x1

≤1

x1 , x2 , x3 ≥ 0 3. Maksimumkan: z = 10x + 11y terhadap kendala: x + 2y ≤ 150 3x + 4y ≤ 200 6x + y ≤ 175 x,y ≥0 4. Maksimumkan: z = x1 + x2 terhadap kendala: x1 + 5x2 ≤ 5 2x1 + x2 ≤ 4 x1 , x2 ≥ 0 5. Maksimumkan: z = u + 9v + w terhadap kendala : u + 2v + 3w ≤ 9 3u + 2v + 2w ≤ 15 u,v,w≥0

20

BAB III PENYELESAIAN FISIBEL AWAL MEMUAT VARIABEL SEMU (METODE M & METODE DUA-PHASE)

3.1.TUJUAN PRAKTIKUM Menyelesaikan masalah program linear dengan cara simpleks (menggunakan metode M dan metode Dua-Phase), untuk masalah dengan penyelesaian fisibel awal memuat variabel semu. 3.2.LANDASAN TEORI Jika bentuk standar masalah program linear (PL) memuat variabel semu, maka cara penyelesaiannya dapat menggunakan metode M maupun metode 2-Fase (DuaPhase). 3.2.1. Metode M Seperti pada metode simpleks secara umum, PL bentuk aslinya lebih dahulu dibawa ke bentuk standar. Dari bentuk standar tersebut, untuk diisikan ke tabel simpleks, pada kendala yang tidak memuat variabel slack, ditambahkan lebih dahulu dengan variabel semu yang nilainya non negatif. Pada fungsi obyektif, koefisien variabel semu adalah +M (untuk masalah minimisasi) dan –M (untuk masalah maksimisasi), dengan M = konstanta yang dianggap besar. Selanjutnya data sudah siap dimasukkan ke tabel simpleks. Contoh 3.1 Perhatikan masalah program linear: Minimumkan z = 4x1 + x2 terhadap kendala: 3x1 + x2 = 3 4x1 + 3x2 ≥ 6 x1 + 2x2 ≤ 4 x1 , x2 ≥ 0

21

Bentuk standar PL tersebut adalah: Minimumkan z = 4x1 + x2 terhadap kendala: 3x1 + x2

=3

4x1 + 3x2 – sx3 x1 + 2x2

=6 + sx4 = 4

x1 , x2 , sx3, sx4 ≥ 0 sx3 adalah variabel surplus, sedangkan sx4 adalah variabel slack. Dari bentuk standar tersebut, sesudah ditambahkan variabel semu, diperoleh model yang siap ke tabel simpleks, sebagai berikut: Minimumkan z = 4x1 + x2 + 0sx3 + 0sx4 + MRx5 + MRx6 terhadap kendala : 3x1 + x2

+ Rx5

4x1 + 3x2 – sx3 x1 + 2x2

=3

+ Rx6 = 6 + sx4

=4

x1 , x2 , sx3, sx4 , Rx5 , Rx6 ≥ 0 sx3 : variabel surplus, sx4 : variabel slack , Rx5 dan Rx6 : variabel semu. Selanjutnya data sudah siap dimasukkan ke tabel simpleks. 3.2.2. Metode Dua-Fase (Dua-Phase) Masalah PL dibawa dulu ke bentuk standar. Pada kendala yang tidak memuat variabel slack, tambahkan variabel semu. Selanjutnya dilakukan 2 tahapan berikut: 1. Fase 1. Menyelesaikan masalah PL dengan fungsi obyektifnya meminimumkan jumlahan variabel semu dan fungsi kendalanya sama dengan masalah PL semula (aslinya). Jika penyelesaian optimal untuk fungsi obyektifnya bernilai nol, maka berarti PL semula mempunyai penyelesaian fisibel, langk...