KATA PENGANTAR. Bandung, Januari 2016

i

KATA PENGANTAR Metode Kuantitatif adalah mata kuliah yang mempelajari langkah pengambilan keputusan secara ilmiah, dimulai dari pendefinisian masalah, pengembangan model, pengambilan data dan mencari alternatif dari penyelesaian masalah tersebut untuk mendapatkan nilai optimal pada sebuah masalah yang kompleks. Modul Praktikum Metode Kuantitatif edisi 2016 disusun untuk menunjang proses pembelajaran mengenai materi-materi yang diajarkan di kelas selama pelaksanaan praktikum. Praktikum ini juga merupakan salah satu komponen nilai yang dimasukkan dalam perhitungan nilai akhir mahasiswa untuk mata kuliah Metode Kuantitatif. Modul praktikum Metode Kuantitatif edisi 2016 terdiri dari sembilan bab dan memiliki beberapa konten pelengkap yang berbeda dibandingkan dengan modul edisi sebelumnya. Akhir kata, penyusun memohon maaf apabila dalam penyusunan modul ini masih memiliki banyak kekurangan. Saran dan kritik yang membangun akan kami terima dengan hati terbuka.

Bandung, Januari 2016

Tim Asisten Praktikum MOLMKF 2015/2016

ii

DAFTAR ISI

KATA PENGANTAR ................................................................ ii DAFTAR ISI .............................................................................. iii BAB I LINEAR PROGRAMMING ........................................... 1 BAB II METODE SIMPLEX ................................................... 10 BAB III SENSITIVITY ANALYSIS ....................................... 26 BAB IV DUAL PROBLEM ..................................................... 35 BAB V INTEGER PROGRAMMING ..................................... 43 BAB VI TRANSPORTASI .......Error! Bookmark not defined. BAB VII PENUGASAN............Error! Bookmark not defined. BAB VIII TEORI ANTRIAN ....Error! Bookmark not defined. BAB IX DYNAMIC PROGRAMMING. Error! Bookmark not defined.

iii

BAB I LINEAR PROGRAMMING Pengertian Program linear adalah teknis suatu matematika yang dirancang untuk membantu manajer dalam merencanakan dan membuat keputusan dalam mengalokasikan sumber daya yang terbatas untuk mencapai tujuan perusahaan. dalam menyelesaikan permasalahan dengan menggunakan program linear dapat dilakukan dengan dua pendekatan, yaitu metode grafik dan metode simpleks. Metode grafik hanya bisa digunakan

untuk

menyelesaikan

permasalah

dimana

variabel

keputusan sama dengan dua.

Karakteristik program linear 1. Mencari kondisi optimum 2. Adanya keterbatasan sumber daya untuk mencapai fungsi tujuan 3. Adanya alternatif dari tindakan yang diambil 4. Fungsi objektif dan kendala harus dinyatakan dalam persamaan

linear

Asumsi program linear 1. Certainty 2. Proportionally 3. Additive

1

Team Teaching Assistant of MOLMKF 2015/2016

4. Divisibility

Tujuan & Fungsi Program Linear Tujuan dari pemecahan program linear metode grafik tidak hanya terbatas pada tujuan memaksimumkan keuntungan, tetapi juga dapat dilakukan untuk meminimalkan biaya karena adanya keterbatasan sumber daya. Terdapat dua fungsi utama dalam program linear, yaitu: 1. Fungsi Tujuan

Fungsi

yang

menggambarkan

tujuan

sasaran

di

dalam

permasalahan program linear yang berkaitan dengan pengaturan secara optimal sumberdaya-sumberdaya, untuk memperoleh keuntungan maksimal atau biaya minimal. Pada umumnya nilai yang akan dipotimalkan dinyatakan sebagai Z.

2. Fungsi Batasan

Merupakan bentuk penyajian secara matematis batasan-batasan kapasitas yang tersedia yang akan dialokasikan secara optimal ke berbagai kegiatan.

Model Programisasi linear: 1. Identifikasi variabel (penentuan x1,x2….xn) 2. Penentuan fungsi tujuan (Max ≤ atau Min ≥) 3. Penentuan fungsi kendala 4. Pendefinisian fungsi status (x1,x2……xn ≥ 0

2


Tahap Pengerjaan Metode Grafik 1. Gambarkan fungsi kendala sebagai persamaan pada grafik,

kemudian dengan mempertimbangkan ketidaksamaan batasan, tunjukkan daerah memenuhi kendala 2. Selesaikan persamaan-persamaan pada titik tiap sudut untuk

memperoleh nilai solusi pada tiap sudut. 3. Masukkan nilai-nilai ke dalam fungsi tujuan untuk menentukan

kumpulan nilai yang menghasilkan nilai Z yang optimal.

Ilustrasi Permasalahan : Perusahaan kayu memproduksi meja dan kursi. Bahan utama yaitu kayu Untuk membuat satu meja dibutuhkan 6m kayu, Sedangkan untuk membuat satu kursi diperlukan 3m kayu bahan baku tersedia untuk kayu adalah 90m. Model Programisasi linear: 1. Identifikasi variabel

X1: meja ; X2: kursi 2. Penentuan fungsi tujuan

Zmemaksimumkan = X1+X2 (≤) Zmeminimumkan = X1+ X2 (≥) 3. Penentuan fungsi kendala

Kayu: 6X1 + 3X2 = 90 4. Pendefinisian fungsi status

X1,X2 ≥ 0

3


BENTUK MASALAH PROGRAM LINIER YANG TIDAK TERATUR (IRREGULER) •

Apabila garis fungsi tujuan menjadi sejajar dengan garis batasan, sehingga slope atau kemiringannya sama.

•

Kertika garis fungsi tujuan tersebut bergerak menuju ke luar dari daerah fisibel, garis tersebut bukan akan menyentuh satu titik ektrim, tetapi menyentuh dua titik ekstrim sekaligus yaitu B dan C, sehingga dua titik ekstrim itu membentuk garis BC.

•

Maka garis BC diantara 2 titik ekstrim tersebut sebagai solusi optimal alternatif, terdiri dari beberapa titik yang mungkin (solusi majemuk)

Grafik masalah tidak teratur : X2

A

B

C X1

4


MASALAH YANG TIDAK FISIBEL •

Apabila tidak adanya perpotongan diantara fungsi kendala, maka tidak ada daerah yang fisibel.

•

Hal tersebut dikarenakan kesalahan dalam pembentukan model matematikanya.

MASALAH YANG TIDAK TERBATAS •

Apabila fungsi kendala tidak tertutup. Dalam hal ini fungsi tujuan mungkin saja akan terus menerus naik tidak terbatas, sehingga tidak akan mencapai suatu solusi.

•

Masalah tidak terbatas tersebut tidak mungkin terjadi di dunia nyata,

biasanya

kesalahan

dalam

bembentukan

matematiknya. Grafik masalah tidak terbatas: X2

X1

5


model

SOAL 1 PT Paragon Technology Innovation akan memproduksi dua produk baru, yaitu lipstik Wardah dan lipstik Emina. Bahan baku

yang

dibutuhkan dalam pembuatan lipstik tersebut sebagai berikut: Bahan Baku

Bahan Baku

Wardah

Emina

Olive Oil

4000

3000

150.000

Shea Butter

8000

4000

200.000

Vitamin E

0

2500

75.000

Jojoba Oil

3000

0

60.000

Tersedia

Jika lipstik Wardah dapat dijual dengan harga Rp 75.000 per buahnya dan lipstik Emina dengan harga Rp 65.000 per buahnya, berapa banyak lipstik Wardah dan lipstik Emina yang harus terjual untuk memaksimalkan profit?

QUESTION 2 Persian Café is one of the most unique ice cream store in Indonesia. Persian Café wants to launch 2 new variants of its ice cream. There are sweet corn and lavender flavors. The ingredients needed to make those new variants are: Ingredients Heavy

6

Sweet Corn Ice

Lavender Ice

Minimum

Cream

Cream

Supply

8 cups

5 cups

400 cups


Cream Sugar

6 cups

12 cups

360 cups

The cost needed to make Sweet Corn Ice Cream is about $ 4.5 and Lavender Ice Cream is about $ 3. Please help Persian Café to determine the most optimum quantity for produce both variants, that leads to most efficient cost. Give also your explanation in graphic!

QUESTION 3 DailyBag.Co produce 2 types of bag, which are laptop bag and sling bag. There are three main materials needed to produce those bags, they are fabric, thread, and leather. In starting the production, their store have a supply of 1200m threads, 2000m fabric, and 800m leather. The material requirements are shown below:

Materials

Laptop Bag

Sling Bag

Thread

20m

30m

Fabric

30m

50m

Leather

30m

20m

Price

Rp 300.000,00

Rp 400.000,00

How many units of laptop bags and sling bags should be produced to generate profit? Draw the graph!

7


SOAL 4 Madame cake akan membuat dua jenis kue yaitu cheese cake dan blackforest. Untuk memproduksi kue-kue tersebut, dibutuhkan empat jenis bahan utama yakni terigu, telur, mentega, dan gula. Jumlah terigu yang tersedia adalah 1.5 kg, telur 32 butir, gula 1 kg dan mentega 1.8 kg. Dalam pembuatan satu cheese cake dibutuhkan 250 gram terigu, 200 gram gula, 300 gram mentega dan 4 butir telur. Sedangkan untuk membuat satu blackforest dibutuhkan 600 gram terigu, 160 gram gula, 225 gram mentega dan 5 butir telur. Biaya yang dikeluarkan untuk setiap pembuatan satu Cheese cake adalah Rp 25.000 dan biaya untuk pembuatan satu blackforest adalah Rp 30.000. Berapa jumlah masing-masing kue yang harus diproduksi Madame cake sehingga dapat meminimumkan biaya? (gunakan metode grafik)

SOAL 5 Suatu Perusahaan Memproduksi 3 macam barang, kapasitas mesin adalah sebagai berikut: Mesin Penggiling 400jam/minggu Mesin Bubut 200jam/minggu Mesin Pengasah 100jam/minggu Mesin Penghalus 150 jam/minggu

8


Mesin Penggiling dapat membuat barang A dalam waktu 16 jam, barang B dalam waktu 4 jam, dan barang C dalam waktu 6 jam. Mesin Bubut dapat membuat barang A dalam waktu 8 jam, barang B dalam waktu 4 jam dan barang C dalam waktu 8 jam. Mesin Pengasah membuat A barang dalam waktu 6 jam, barang B dalam waktu 10 jam dan barang C dalam waktu 4 jam. Mesin penghalus membuat barang A dalam waktu 4 jam, barang B dalam waktu 6 jam dan barang C dalam waktu 8 jam. Keuntungan per unit masing-masing barang A, B dan C adalah $10, $ 6 dan $8. Berapa banyak barang produksi tiap-tiap barang agar keuntungan maksimum?

9


BAB II METODE SIMPLEX Pengertian Metode simpleks merupakan salah satu teknik untuk menentukan solusi optimum dalam program linear. Penentuan solusi optimal dilakukan dengan memeriksa titik ekstrem satu per satu dengan cara perhitungan iteratif, sehingga penentuan solusi optimal dengan metode simpleks dilakukan tahap demi tahap yang disebut dengan iterasi.

Tujuan dan Manfaat Pada pengaplikasiannya dalam kehidupan sehari-hari, permasalahan program linear memiliki lebih dari dua variabel keputusan, oleh karena itu kita akan menghadapi kesulitan jika melakukan penyelesaian dengan menggunakan metode grafik yang terbatas hanya pada dua dimensi. Untuk memecahkan persoalan seperti itu, metode simpleks dianggap sebagai metode yang paling tepat untuk menyelesaikan permasalahan tersebut.

Cara Kerja Metode Simplex Secara konsep, cara kerja metode simpleks sama seperti pendekatan dengan menggunakan solusi grafik dimana kita memeriksa setiap titik sudut yang ada dalam sebuah daerah feasible (layak) dan menentukan titik yang merupakan solusi optimum bagi sebuah fungsi tujuan.

10


Dalam metode simpleks, model yang ada diubah menjadi suatu bentuk tabel kemudian dilakukan beberapa langkah matematis pada tabel tersebut. Metode simpleks bergerak dari satu solusi ke solusi yang lebih baik sampai dengan didapatkannya solusi optimal. Langkahlangkah pengulangan tersebut disebut dengan iterasi. Setiap iterasi menghasilkan nilai yang lebih baik bagi fungsi tujuan sehingga membawa kita pada pencapaian solusi optimal.

Persoalan Primal Dilihat dari bentuknya, persoalan dalam program linear dibagi menjadi dua yaitu persoalan primal (asli) dan persoalan dual yang merupakan kebalikan dari primal.

Kasus Maksimasi Langkah 1: Mengubah batasan-batasan (constraint) model Langkah 2: Menentukan variabel dasar Langkah 3: Menentukan variabel masuk (entering variable) Langkah 4: Menentukan variabel keluar (leaving variable) Dalam kasus maksimasi, hasil optimum dicapai ketika nilai C-Z bernilai negatif atau nol.

Kasus Minimasi Langkah-langkah yang terdapat dalam kasus minimasi secara umum hampir sama dengan kasus maksimasi, hanya saja terdapat perbedaan pada langkah ketiga yaitu dimana dalam kasus maksimasi yang

11


menjadi variabel masuk (entering variable) merupakan variabel non dasar yang memiliki nilai C-Z terbesar sedangkan dalam kasus minimasi yang menjadi variabel masuk adalah variabel non dasar yang memiliki nilai C-Z terkecil. Dalam kasus minimasi, solusi optimum tercapai ketika nilai C-Z bernilai positif atau nol.

Kasus Khusus Maksimasi Maximize:

Z = $4X1 + $5X2

Constraints:

X1 + 2X2 ≤ 40 jam tenaga kerja 4X1 + 2X2 ≤ 120 kg kulit sapi X1, X2 ≥ 0

Diketahui:

X1 = jumlah tas yang diproduksi X2 = jumlah sepatu yang diproduksi

Penyelesaian Langkah 1: Mengubah Batasan / Constraints dalam Model Ubahlah batasan – batasan model ke dalam bentuk persamaan (equation) yang merupakan persyaratan untuk pemecahan masalah. Bentuk program linear yang standar sebelum diubah ke dalam metode simpleks memiliki beberapa syarat yaitu: - Fungsi tujuan adalah maksimasi atau minimasi - Seluruh variabel non negatif - Seluruh constraint (kecuali asumsi non negatif) merupakan persamaan dengan sisi kanan (RHS) non negatif

12


Metode simpleks

memberikan suatu prosedur standar untuk

mentransformasikan batasan pertidaksamaan ke dalam bentuk persamaan. Transformasi ini dicapai dengan cara nemambahkan suatu variabel baru, yang dinamakan variabel pengurang (slack variabel) pada tiap batasan. Secara umum, variabel pengurang (slack) mencerminkan jumlah sumber-sumber yang tidak terpakai (unused resource). Untuk contoh kasus perusahaan konveksi diatas, batasan-batasan (contraint) adalah: X1 + 2X2 ≤ 40 jam tenaga kerja 4X1 + 2X2 ≤ 120 kg kulit sapi Penambahan suatu variabel pengurang (S) pada setiap pertidaksamaan akan menghasilkan persamaan – persamaan seperti berikut: X1 + 2X2 = 40 4X1 + 3X2 = 120 Seperti pada variabel X1 dan X2, slack juga hanya dapat memiliki nilai non negatif karena sumber yang bernilai negatif tidak mungkin sehingga jumlah variabel menjadi: X1, X2, S1, S2 ≥ 0 Dengan demikian fungsi tujuannya berubah menjadi: Z= 4X1 + 5X2 + 0S1 + 0S2 Pada fungsi tujuan 4X1 + 5X2, memiliki arti bahwa setiap 1 unit tas yang diproduksi akan menghasilkan keuntungan sebesar $4 dan setiap unit sepatu yang diproduksi akan menghasilkan keuntungan sebesar $5.

13


Langkah 2: Menentukan Variabel Dasar Sebelum menentukan

jumlah

variabel

dasar

terlebih dahulu

menentukan jumlah variabel non dasar dengan rumus n-m, dimana n adalah banyak variabel dan m adalah banyak batasan (constraint). Variabel dasarnya adalah variabel yang tidak masuk ke dalam variabel non dasar. X1, X2, S1, S2 ≥ 0 n=4 ; m= 2 sehingga variabel non dasarnya adalah X1 dan X2 dan variabel dasarnya S1 dan S2.

Iterasi

C

$4

$5

0

0

Nilai

ke

V. Dasar

X1

X2

S1

S2

Kanan

0

0

S1

1

2

1

0

$40

0

S2

4

3

0

1

$120

Z

0

0

0

0

$0

C-Z

4

5

0

0

Rasio

Langkah 3: Menentukan Variabel Masuk / Entering Variable Entering variabel adalah variabel non dasar yang memiliki nilai positif terbesar pada garis C-Z dalam tabel pada kasus maksimisasi. Sebelum menentukan entering variabel, masukan terlebih dahulu angka koefisien pada batasan – batasan ke dalam tabel yang telah

14


dibuat, sehingga dapat diketahui jika jumlah C-Z. Pada tabel tersebut, dapat diketahui jumlah C-Z terbesar adalah X dengan jumlah 5, sehingga X2 menjadi entering variabel kolom yang berkaitan dengan entering variabel disebut dengan kolom pivot.

Iterasi

C

$4

$5

0

0

Nilai

ke

V. Dasar

X1

X2

S1

S2

Kanan

0

0

S1

1

2

1

0

$40

0

S2

4

3

0

1

$120

Z

0

0

0

0

$0

C-Z

4

5

0

0

Rasio

Langkah 4: Menentukan Variabel Keluar / Leaving Variable Leaving variabel adalah variabel yang keluar dari variabel dasar dan diganti oleh variabel yang menjadi entering variabel. Cara menentukan leaving variabel adalah dengan mencari nilai rasio positif terkecil dengan cara membagi kolom kuantitas dengan koefisien kolom entering variabel yang merupakan variabel yang keluar. Pada contoh soal diatas, jumlah kuantitasdibagi kolom pivotnya adalah S1 = 20; S2 = 30 sehingga leaving variabelnya adalah 𝑆1 angka pada perpotongan kolom pivot dengan baris pivot disebut angka pivot. Pada soal tersebut, angka pivotnya adalah 2.

15


Iterasi

C

$4

$5

0

0

Nilai

ke

V. Dasar

X1

X2

S1

S2

Kanan

0

0

S1

1

2*

1

0

$40

(+) 20

0

S2

4

3

0

1

$120

(+) 40

Z

0

0

0

0

$0

C-Z

4

5

0

0

*Angka Pivot

Menghitung Baris Pivot Baru Pada pengerjaan iterasi 1, koefisien yang berada di dalam tabel tidak sama dengan iterasi 0. Untuk mengisi baris pivot baru, caranya dengan membagi angka – angka pada pivot lama dengan angka pivot. Baris X2 baru = 1 2 1 0 40 (:2) = ½ 1 ½ 0 20

Menghitung Nilai Baris Lainnya Pada kasus soal tersebut, baris yang belum terdapat angkanya adalah S2, angka–angka tersebut dapat diperoleh dengan menggunakan cara: Nilai Baris Tabel Baru = Nilai Baris Tabel Lama (Koefisien Entering Variabel x Nilai Baris Pivot Baru)

Setelah semua baris terisi , hitung nilai Z dan C-Z nya seperti pada langkah 4. Karena fungsi tujuannya adalah memaksimisasi laba.

16

Rasio


Maka nilai C-Znya sudah tidak ada yang positif (hanya nilai negatif atau nol saja) maka berhentilah karena persoalan sudah terselesaikan. Namun jika tidak, lanjutkanlah ke iterasi selanjutnya dengan cara yang sama seperti sebelumnya.

17


Iterasi

C

$4

$5

0

0

Nilai

ke

V. Dasar

X1

X2

S1

S2

Kanan

5

S1

0,5

1

0,5

0

20

0

S2

2,5

0

-1,5

1

60

Z

0

0

0

0

100

C-Z

1,5

0

2,5

0

1

Rasio

Karena pada tabel tersebut baris C-Z masih memiliki nilai positif, maka iterasi tersebut belum optimal. Jadi, lanjutkanlah ke iterasi berikutnya: Iterasi

C

$4

$5

0

0

Nilai

ke

V. Dasar

X1

X2

S1

S2

Kanan

5

S1

0,5

1

0,5

0

20

(+) 40

0

S2

2,5

0

-1,5

1

60

(+) 24

Z

0

0

0

0

100

C-Z

1,5

0

2,5

0

1

Rasio

Entering Variable X1, Leaving Variable S2 Lanjutkanlah tahapan-tahapan tersebut ke iterasi 2 dimana langkah yang diambil adalah sama dengan iterasi 0 dan iterasi 1. Iterasi

C

$4

$5

0

0

Nilai

ke

V. Dasar

X1

X2

S1

S2

Kanan

1

5

0

1

0,8

-0,4

8

18

S1


Rasio

4

S2

1

0

-0,6

0,4

24

Z

4

5

1,6

0,6

$136

C-Z

0

0

-1,6

-0,6

Dari hasil tabel iterasi 2 tersebut, kita dapat melihat bahwa hasil dari C-Z sudah tidak memiliki nilai positif sehingga didapatlah sebuah hasil optimum dari iterasi tersebut, yaitu X1=24, X2=8, dan Laba yang diperoleh yaitu sebesar $136, dimana S1=0 dan S2=0.

Kasus Khusus Minimasi Min:

Z = $4𝑋1+$1𝑋2

Constraint:

3X1 + X2 = 3 unit sweater 4X1 + 3X2 ≥ 60 unit sarung tangan X1, X2 ≥ 0

Diketahui:

X1 = jumlah jam perajutan X2 = jumlah jam penjahitan Z = jumlah total pembiayaan pekerjaan

Penyelesaian Langkah 1: Diubah ke Bentuk Simplex Fungsi Tujuan Min:

Z= $4X1 + $1X2 + 0S1 + 0S2 + MA1 +MA2

Constraint:

3X1 + X2 + A1 = 3 4X1 + 3X2 – S1 + A2 = 6

M = nilai yang sangat besar Misal M = 1000

19


Iterasi Ke

C V. Dasar

0

$4

$5

0

M

M

X1

X2

S1

A1

A2

Kanan

Nilai

Rasio

M

A1

3

1

0

1

0

3

(+)1

M

A2

4

3

1

0

1

6

(+)1,5

7M

4M

M

M

M

9M

4-

1-

7M

4M

-M

0

0

Z C-Z

Langkah 2: Lanjutkan ke Iterasi 1 Pada kasus minimasi, yang menjadi variabel masuk adalah variabel yang memiliki nilai C-Z paling kecil (negatif terbesar). Sedangkan untuk variabel keluar sama dengan kasus maksimasi yaitu variabel yang memiliki nilai rasio positif terkecil. Pada kasus ini yang menjadi variabel masuk adalah X1 dan yang menjadi variabel keluar adalah A1.

20


Itera

C

$4

$5

0

M

M

Nilai

si Ke

V. Dasar

X1

X2

S1

A1

A2

Kanan

0

4

X1

1

1/3

0

1/3

0

1

M

A2

0

5/3

1

-4/3

1

2

Z

4

4/3 + 5/3M

M

4/3 – 4/3M

M

4+2M

C-Z

0

1/3 – 5/3M

M

-4/3 – 1/3M

0

Rasio

Langkah 3: Hasil dari iterasi tersebut belum optimal karena masih terdapat hasil C-Z yang bernilai negatif. Untuk itu, lanjutkanlah ke iterasi berikutnya dengan terlebih dahulu menentukan variabel masuk dan variabel keluarnya. Pada kasus ini yang menjadi variabel masuk adalah X2 dan yang menjadi variabel keluar adalah A2. Iteras

C

$4

$5

0

M

M

Nilai

i Ke

V. Dasar

X1

X2

S1

A1

A2

Kanan

1

21

Rasio

4

X1

1

1/3

0

1/3

0

1

(+)3

M

A2

0

5/3

1

-4/3

1

2

(+)6/5

Z

4

4/3 + 5/3M

M

4/3 – 4/3M

M

4+2M

C-Z

0

1/3 – 5/3M

M

-4/3 – 1/3M

0


Langkah 4: Lanjutkan ke Iterasi Selanjutnya C

Iterasi Ke

2

V. Dasar

$4

$5

0

M

M

X1

X2

S1

A1

A2

Kanan

Nilai

4

X1

1

0

1/5

3/5

-3/5

3/5

1

X2

0

1

3/5

-4/5

3/5

6/5

Z

4

1

8/5

9/5

18/5

C-Z

0

0

1/5 1/5

M– 8/5

Rasio

M+9/5

Dari tabel iterasi di atas, dapat dilihat nilai-nilai pada baris C-Z bernilai positif atau 0, hal ini menunjukan hasil tersebut sudah optimal, yaitu: X1: 3/5 jam dan X2: 6/5 jam Z = $24 (total pembiayaan pekerjaan)

22


SOAL 1 Bad Atittude,Inc merupakan produsen dua jenis rudal bermuatan nuklir, yaitu Bad Boy dan Mad Bird. Setiap jenis mengandung campuran bahan uranium dan white phosporus dalam jumlah tertentu.

Kandungan Explosive Materials Uranium (kg/unit) White Phosporus (kg/unit) Bad Boy 2 4 Mad Bird 4 3 Jenis

SEAL Team membutuhkan paling sedikit 16 kg Uranium dan 24 kg White Phosporus untuk sebuah misi. Harga satu unit rudal nuklir Badboy dan Madbird masing-masing $3000 dan $6000. SEAL Team ingin mengetahui berapa unit masing-masing jenis rudal harus dibeli agar total harga rudal mencapai minimum dan kebutuhan rudal untuk misinya terpenuhi

SOAL 2 Maximize:

8X1 + 10 X2

Fungsi kendala:

X1 ≤ 15 3X2 ≤ 30 6X1 + 10X2 ≤ 120

Fungsi status:

X1, X2 ≥ 0

Tentukan kondisi optimum dengan menggunakan metode simplex!

23


QUESTION 3 Pull & Cats sells bags, shoes, and jeans. Pull & Cats expected margin $150, $250, and $75. But, because of the minimum workers, so production for those 3 products is limited. There are only 20 hours available for designing process, 30 hours available for sewing process, and 24 hours for final touches. The making of one bag needs 3 hours of designing, 2 hours of sewing, and 1 hour for final touches. One pair shoes need 2 hours of designing, 5 hours of sewing, and 3 hours of final touches. One jeans needs 2 hours of designing, 1 hour of sewing, and 2 hours of final touches. Please help Pull & Cats to determine the best number produced for each product in order to minimize the processing time!

SOAL 4 Simsalabim Design merupakan sebuah perusahaan yang memproduksi baju kostum terkenal di Inggris. Produk yang menjadi unggulan di Simsalabim Design adalah kostum Harry Potter, kostum Captain America dan kostum Spiderman. Untuk membuat satu kostum Harry Potter dibutuhkan 4 meter benang katun dan 6 meter kain. Sedangkan untuk membuat kostum Captain America dibutuhkan 3 meter benang dan 7 meter kain. Untuk membuat kostum spiderma dibutuhkan 8 meter benang dan 4 meter kain. Saat ini bahan baku yang tersedia dalam gudang Simsalabim Design adalah 72 meter benang dan 48 meter kain.

Keuntungan dalam

menjual satu kostum Harry Poter adalah sebesar 6 poundsterling,

24


kostum Captain America 4 poundsterling dan kostum Spiderman 5 poundsterling. Tentukanlah persamaannya dan setelah itu bantulah Simsalabim Design dalam mencari kombinasi produk yang tepat untuk memaksimalkan keuntungannya.

QUESTION 5 La Bakerie is a famous bakery store at town. They produce cheese cake in three different type. Blueberry Cheese Cake sales generate $28 while Strawberry Cheese Cake $20 and Oreo Cheese Cake is $24. Blueberry Cheese Cake is made of 33kg of flour, 18kg butter, 13kg cheese. While Strawberry Cheese Cake needs, 5kg flour, 27kg butter and 9kg cheese. Oreo Cheese Cake needs 17kg flour, 11kg butter and 25kg cheese. Currently, there are supply of 800kg flour, 500kg butter and 400kg cheese. How many units of the products to get the maximum profit?

25


BAB III SENSITIVITY ANALYSIS Pengertian Analisis sensitivitas merupakan analisis yang berkaitan dengan perubahan diskrit parameter untuk melihat seberapa besar perubahan dapat

ditolerir

sebelum

solusi

optimum

mulai

kehilangan

optimalitasnya. Jika suatu perubahan kecil dalam parameter menyebabkan perubahan drastis dalam solusi, dikatakan bahwa solusi sangat sensitif terhadap nilai parameter tersebut. Sebaliknya, jika perubahan parameter tidak mempunyai pengaruh besar terhadap solusi dikatakan solusi relatif insensitif terhadap nilai parameter itu. Analisis sensitivitas juga biasa disebut interpretasi hasil optimum dari perhitungan metode simpleks.

Tujuan a. Mengetahui besarnya perubahan yang terjadi pada kondisi optimum dari suatu pemecahan masalah pemrograman linear. Sehingga didapatkan solusi optimum yang sifatnya dinamis. b. Mengetahui batas-batas perubahan yang diperbolehkan dan bagaimana dampak perubahan itu terhadap kondisi optimum semula.

26


Contoh Soal a. Persoalan primal  Maksimasi Z = 7X1 + 5X 2  Subject to: 2X1 + X 2 ≤ 100 (jam tenaga kerja pengecatan) 4X1 + 3 X 2 ≤ 240 (jam tenaga kerja perkayuan) X1, X 2 ≥ 0 (syarat non-negatif) Dimana

X1 = jumlah meja yang diproduksi X 2 = jumlah kursi yang diproduksi

b. Bentuk Standar Fungsi tujuan

Z = 7X1 + 5X 2 + 0S1 + 0S2

Fungsi Kendala

2X1 + 1X 2 + S1 = 100

(Pengecatan)

7X1 + 5X 2 + S2 = 240

(Perkayuan)

X1 , X 2 , S1 , S2 ≥ 0

(Non negatif)

Dimana S1 = Jumlah jam tenaga kerja pengecatan yang menganggur S2 = Jumlah jam tenaga kerja perkayuan yang menganggur

c. Tabel Optimum

27


d. Informasi yang Diperoleh 1. Nilai Variabel Nilai variabel X1 (meja yang diproduksi) = 30 buah meja Nilai variabel X2 (kursi yang diproduksi) = 40 buah kursi

2. Nilai Fungsi Objective Nilai fungsi objektif atau nilai solusi optimum (Z) = $ 410 (Asumsi: jumlah yang dibuat sama dengan jumlah yang dijual atau semua yang diproduksi laku terjual)

3. Status Sumber Daya

Nilai unit sumber daya

 Jika 1 jam S1 (jam tenaga kerja pengecatan) ditambah, maka laba akan meningkat sebesar $0.5. Hal ini merupakan shadow price.  Jika 1 jam S2 (jam tenaga kerja perkayuan) ditambah, maka laba akan meningkat sebesar $1.5. Hal ini merupakan shadow price.  Nilai fungsi objektif atau nilai solusi optimum (Z) = $410  Shadow Price adalah perubahan nilai dari fungsi objektif ketika meningkatkan 1 unit sumber daya.

28


4. Berapa besar nilai koefisien variabel fungsi tujuan non-basic dapat berubah? Pada contoh soal, tidak ada variabel keputusan yang merupakan variabel non-basic. Jika ada, maka untuk menentukan besarnya perubahan adalah dengan menjaga syarat optimalitas tetap terpenuhi.

5. Berapa besar nilai koefisien variabel basic dapat berubah agar solusi optimum tetap dipertahankan atau meningkat (kasus maksimasi) dan tetap feasible? Variabel basic adalah variabel yang letaknya pada kolom solution mix, yaitu variabel X1 dan X 2. Pada kondisi optimum saat ini koefisien dari masing-masing variabel adalah untuk X1 = 7 dan untuk X 2 = 5.  Misalkan perubahan untuk variabel X2 adalah delta, maka tabel optimum di atas berubah menjadi:

29


Interpretasinya yaitu harga kursi dapat diubah antara 5-3/2 ≤ harga kursi ≤ 5+1/4, atau kursi dapat dijual dengan rentang harga $3.5 sampai dengan $5.25 (atau harga tetap dipertahankan $5).

6. Berapa rentang perubahan masing-masing bahan baku? Misalnya untuk konstrain pertama, kapasitas jam tenaga kerja pengecatan sebesar 100 ingin ditingkatkan menjadi 110 jam, berapa dampak perubahannya pada fungsi tujuan Z dan apakah masih optimum?

Matriks pengali didapatkan dari kolom S1 dan S2. Karena hasil masih positif, sehingga solusi tetap feasibel. Artinya dengan merubah jam pengecatan dari 100 menjadi 110 jam, didapatkan jumlah meja (X1) dari semula sebesar 30 menjadi 45 buah dan jumlah kursi (X2) dari semula 40 menjadi 20 buah, dengan nilai fungsi tujuan Z = (7x45) + (5x20) = $415 (meningkat sebesar $5). Bisa juga dilihat dari nilai shadow price, untuk jam pengecatan bertambah 110-100 = 10 jam sehingga akan menambah keuntungan sebesar 10 x $0,5 = $5

Mencari rentang batas perubahan ruas kanan (sumber daya) Pertanyaannya adalah berapakah rentang perubahan jam tenaga kerja pengecatan? Artinya jika dinaikkan sampai berapa batas maksimalnya

30


dan jika diturunkan seberapa besar batas minimalnya sehingga solusi tetap feasible? Jawab: Caranya menggunakan rasio antara kolom quantity dengan kolom slack/surplus. Besar perubahan pada contoh diatas untuk sumber daya 1 adalah sebagai berikut:

Berdasarkan rasio, didapatkan kisarannya adalah –20 ≤ sumber daya 1 ≤ 20 atau rentang perubahan Sumber daya 1 adalah 80 unit sampai dengan 120 unit.

Bagaimana dengan rentang sumber daya 2 (perkayuan)?

Didapatkan kisarannya adalah –40 ≤ sumber daya 2 ≤ 60 atau rentang perubahan sumber daya 2 adalah 200 unit sampai dengan 300 unit. (Ratio dibacanya terbalik. Apabila hasilnya (-) berati increase RHS, sedangkan (+) berarti decrease RHS)

31


SOAL 1 Perusahaan Omai Jelly merencanakan untuk membuat dua jenis inovasi jelly yaitu art pudding jelly dan Jelly Candy. Kedua jenis makanan tersebut menggunakan dua komposisi utama yaitu bubuk agar dan gula. Pada tabel berikut menunjukkan jumlah bubuk agar dan gula pada tiap jenis makanan : Bubuk Agar Gula

Keuntungan Per

(gram)

(gram)

Unit (Rp)

Art Pudding Jelly

250

180

12000

Jelly Candy

100

120

8000

Persediaan

400

360

Jenis Makanan

Bagaimana menentukan kombinasi kedua jenis makanan agar dapat memaksimalkan profit serta bagaimana status sumberdaya, nilai shadow price-nya?

QUESTION 2 Heikotolenar.Co is planning to create new and more comfortable couch product. So they consider to add new ornaments on it. To make ornament A, they needs 6 kg of leather and 5 kg of wood. While ornament B, Heikotolenar.Co needs 3 kg of leather and 3 kg of wood. For now, they have 30 kg of leather and 15 kg of wood available, with marginal profit of A is 22 euro and B is 46 euro. Please help them to determine: a. optimum solution with simplex method b. total of unit produced

32


c. resource status d. shadow price e. range basic variable

SOAL 3 Fungsi tujuan:

Zmax = 12X1 + 10X2

Fungsi kendala:

6X1 + 3X2 ≤ 120 5X1 + 8X2 ≤ 100 4X1 + 2X2 ≤ 90

Tabel solusi optimum : Cj

12 Solmix 12 X1 10 X2 0 S3 zj cj-zj

X1

10 X2

1 0 0 12 0

0 S1

0 0.2424 1 -0.1515 0 -0.66667 10 1.3939 0 -1.3939

0 S2

0 S3

-0.0909 -0.1818 0 0.7273 -0.7273

Q 0 0 1 0 0

20 0 10 240

a. Berapa unit produk yang harus diproduksi untuk menghasilkan profit yang optimum? Dan berapakah profit optimumnya? b. Berapakah nilai shadow pricenya dan bagaimana interpretasinya? c. Bagaimana status sumberdayanya? d. Variabel mana yang menjadi basic variable dan berapakah nilai perubahannya? e. Variabel mana yang menjadi non basic variable dan berapakah nilai perubahannya? f. Berapa rentang perubahan untuk masing-masing sumber daya?

33


SOAL 4 4Second Boutique merupakan sebuah perusahaan yang memproduksi celana dan jaket. Namun kapasitas produksinya dibatasi ketersediaan bahan baku dan jam kerja. Kebutuhan bahan baku celana adalah 2 unit dan jam kerjanya 4 jam, sedangkan kebutuhan bahan baku jaket adalah 1 unit dan jam kerjanya 5 jam. Sedangkan hanya tersedia 25 unit bahan baku dan 10 jam kerja. Biaya untuk membuat sebuah celana dan jaket berturut-turut adalah $100 dan $85. Hitunglah: a. Nilai solusi optimum (Z) b. Unit yang diproduksi c. Nilai shadow price beserta interpretasinya d. Status sumber daya

QUESTION 5 Paleyellow Inc. wants to produce Bags (X1) and Suitcase (X2) and receive maximum profit from this. Paleyellow wants margin for Bags is $10 and for Suitcase is $25. This is the following data: Constraints:

6X1 + 2X2 ≤ 200 2X1 + 5X2 ≤ 150

please find: a. optimum solution and the profit b. total of unit produced c. resource status d. shadow price e. basic and non basic variable

34


BAB IV DUAL PROBLEM Pengertian Setiap masalah linear programming memiliki masalah LP terkait dengan itu, yang disebut dual. Cara pertama menyatakan masalah linear disebut primal;kita dapat melihat semua masalah yang dirumuskan sejauh primal. Cara kedua menyatakan masalah yang sama disebut dual. Solusi optimal untuk primal dan dual setara, tetapi mereka diperoleh melalui prosedur alternatif. Kegunaan dual bagi pengambil keputusan adalah bahwa dengan dual mereka dapat melihat alternatif persamaan dari alternatif yang berbeda. Primal akan menghasilkan solusi-solusi dalam bentuk jumlah laba yang di dapat dari memproduksi barang atau dengan kata lain memaksimalkan fungsi laba, sedangkan dual akan memberikan informasi mengenai nilai (harga) dari sumber-sumber yang membatasi tercapainya laba atau dengan kata lain menjelaskan minimalisasi total opportunity cost dengan profit yang lebih besar.

Tujuan Secara sistematis, dualitas merupakan alat bantu masalah linear programming (LP) yang secara langsung didefinisikan dari persoalan aslinya atau dari model LP Primal. Dalam kebanyakan perlakuan LP, dualitas sangat tergantung pada primal dan hal tipe

35


kendala, variabel keputusan dan kondisi optimum. Oleh karena itu dalam kenyataannya teori dualitas secara tegas tidak diharuskan penggunaannya. Dual

berisi

informasi

ekonomi

yang

berguna

untuk

manajemen, dan juga mungkin lebih mudah untuk memecahkan, dalam hal perhitungan yang kurang dari masalah primal. Pada umumnya, jika LP Primal melibatkan maksimasi fungsi keuntungan untuk kurang-dari-atau-sama dengan keterbatasan (constrain) sumber daya, dual akan melibatkan meminimalkan biaya kesempatan untuk lebih besar-dari-atau-sama dengan keterbatasan (constraint) profit dari produk.

Hubungan Primal-Dual Primal-dual menunjukan hubungan secara simetris dengan ketentuan sebagai berikut : a. Koefisien fungsi tujuan primal menjadi konstanta ruas kanan dual b. Konstanta ruas kanan primal menjadi konstanta fungsi tujuan dual c. Semua kolom primal menjadi kendala dual d. Semua kendala primal menjadi variabel keputusan dual e. Koefisien kendala dari variabel primal menjadi koefisien yang berkorespondensi dengan kendala dual

36


Cara Pengerjaan Aturan 1 Umumnya pada model primal “maximize profit function” dengan subject to ≤resources constraint, dual akan “minimize opportunity cost” dengan subject to ≥product profit constraints. Contoh: Maximize:

Z = $4X1 + $5X2

Constraints:

X1 + 2X2 ≤ 40 jam tenaga kerja 4X1 + 2X2 ≤ 120 kg kulitsapi X1, X2 ≥ 0

Diketahui:

X1 = jumlah tas yang diproduksi X2 = jumlah sepatu yang diproduksi

Dual dari masalah ini dengan tujuan meminimasi opportunity cost menggunakan variabel U1 dan U2. U1 = dual dari jam tenaga kerja U2 = dual dari kg kulit sapi

37


Aturan 2 Pada sisi kanan primal, menjadi koefisien fungsi tujuan pada dual. Minimize: Z = $40U1 + $120U2

Aturan 3 Koefisien fungsi tujuan primal menjadi sisi kanan dual.

Aturan 4 Transpose dari koefisien primal constraint menjadi koefisien dual constraint.

Aturan 5 Tanda pertidaksamaan dari constraint merupakan kebalikan. Constraint:

U1 + 4X2 ≥ 4 2U1 + 3X2 ≥ 5

Penyelesaian Model Dual Setelah fungsi persoalan primal diubah ke dalam persoalan dual, maka penyelesaian dilakukan seperti pada persoalan primal. Minimize

Z = $40U1 +$120U2 +0S1 + 0S2 +MA1 +MA2

Constraints:

U1 + 4U2 – S1 + A1 = 4 2U1 + 3U2 – S2 + A2 = 5 U1, U2, S1, S2, A1, A2 ≥ 0

38


Hasil tersebut sudah optimal melihat pada baris Cj-Zj seluruhnya bernilai positif. Dengan demikian hasil dari model dual ini adalah: U1 = 8/5 U2 = 3/5 S1 = 0 S2 = 0 Opportunity cost = $136

39


SOAL 1 Sally Salon memiliki dua jenis penawaran jasa Body Spa yang paling digemari oleh konsumen yaitu Chocolate Body Spa dan Greentea-Strawberry Body Spa dengan profit masing-masing $90 dan $125. Waktu yang dibutuhkan untuk melakukan jasa Chocolate Body Spa yaitu 1 jam dan untuk Greentea-Strawberry Body Spa selama 2 jam. Untuk melayani Chocolate Body Spa dibutuhkan 3 karyawan dan 5 komponen kecantikan. Sedangkan untuk melayani

Greentea-

Strawberry Body Spa dibutuhkan 4 karyawan dan 6 komponen kecantikan dengan waktu kerja selama 10 jam. Saat ini Sally Salon memiliki 24 karyawan dan 40 komponen kecantikan. Tentukanlah pelayanan jasa yang dapat memaksimalkan profit Sally salon dilengkapi jumlah profit yang di dapat juga buat dalam bentuk dual!

SOAL 2 Sebuah usaha furniture sedang mengalami penciutan dalam usahanya, sehingga saat ini ia hanya memproduksi barang-barang yang paling laku di pasar yaitu meja dan kursi. Untuk memproduksi setiap meja membutuhkan 5 unit papan, 2 unit kayu, dan 2 jam pengerjaan.

Sedangkan

untuk

memproduksi

setiap

kursi

membutuhkan 2 unit papan, 3 unit kayu, dan 2 jam pengerjaan. Bahan baku yang tersedia saat ini adalah 150 unit papan dan 100 unit kayu, sedangkan jam pengerjaan yang tersedia adalah 80 jam. Profit yang mampu dihasilkan untuk setiap produk meja dan kursi yang dapat

40


terjual adalah Rp 150.000 dan Rp 80.000. Buatlah formulasi matematis dari persoalan tersebut dalam bentuk primal dan dual dan buatlah tabel iterasi 0 untuk masing-masing model tesebut (primal dan dual)

QUESTION 3 YLI is a company who produce diet snack. There are 2 product that currently been produced, snack bar and dried oat. To produce snack bar, they need 10gr oat, 4gr sugar. For dried out, they need 4gr oat, 6gr sugar. Currently company have stock 300gr of oat and 200gr of sugar. For each snack bar,they earn $10, while dried out $5. From the condition above, please make: a. Mathematics formulation in primal and dual form b. Iteration table of 0 or each form (primal and dual)

SOAL 4 MOLMkf Wedding Cake memproduksi dua jenis produk yaitu kue tart dan cupcake. Keuntungan yang dihasilkan dari penjualan satu buah kue tart adalah Rp 10.000,00 sedangkan dari penjualan cupcake adalah sebesar Rp 7.500,00. Bahan-bahan yang dibutuhkan untuk membuat kedua kue tersebut adalah tepung terigu dan gula. Untuk membuat satu buah kue tart dibutuhkan 50 gram tepung terigu dan 100 gram gula, sedangkan untuk membuat satu buah cupcakes dibutuhkan 25 gram tepung terigu dan 30 gram gula. Persediaan bahan yang

41


dimiliki MolMkf Wedding Cake di gudang adalah sebanyak 1000 gram tepung terigu dan 1500 gram gula. Berapa banyak jumlah kue tart dan cupcake yang harus diproduksi agar keuntungan yang diperoleh MolMkf Wedding Cake maksimal! Buatlah dalam bentuk primal dan dual!

QUESTION 5 Coppa Inc. wants to sell new canned food and snack for cats. For new canned food, Coppa Inc. needs 9X1, 12X2, and 3X3 materials. On the other hand, for new snack, Coppa Inc. needs 1/3 all materials from new canned food materials. Each of the products are sold US$ 6.5 and US$ 7.3 each. There are only 50 kg of X1, 65 kg of X2, and 30 kg of X3 available. Please help the manager of Coppa Inc. to determine the numbers of the products that should be produced to maximize the profit using simplex method! Please also calculate both primal and dual problem!

42


BAB V INTEGER PROGRAMMING Pengertian Integer Programming adalah suatu program Linear dengan tambahan persyaratan bahwa semua atau beberapa variabel bernilai bulat non negative, tetapi tidak perlu parameter model juga bernilai bulat. Satusatunya perbedaan adalah bahwa satu atau lebih dari variable keputusan harus mengambil nilai integer dalam solusi akhir.

Tujuan dan Manfaat Integer Programming dimaksudkan agar pengambilan keputusan dari suatu masalah semakin realistis dan layak solusinya. Ketika dalam pengerjaan soal ditemukan perhitungan jumlah barang lalu adanya koma seperti 102,3 buah , maka nilai tersebut harus dibulatkan. Untuk mengetahui

solusi

pembulatan

yang

optimum

maka

harus

diperhitungkan dengan menggunakan Integer Programming.

Jenis Integer Terdapat tiga jenis masalah integer programming : 1. Pure Integer Programming adalah kasus-kasus di mana semua variabel wajib memiliki nilai integer. Contoh dalam pembelian mesin-mesin, karena tidak mungkin membeli mesin dalam bentuk pecahan ( X1 ≥ 0 dan Integer).

43


2. Mixed

Integer

Programming

adalah

kasus-kasus

dimana

beberapa, tapi tidak semua dari keputusan variabel wajib memiliki nilai integer. Contoh pembelian rumah dan tanah, untuk rumah diharuskan integer namun untuk pembelian tanah tidak harus integer (X1 ≥ 0 dan Integer ; X2 ≥ 0). 3. Zero-One Integer Programming adalah kasus khusus dimana semua keputusan variabel harus memiliki nilai solusi integer 0 atau 1. Contoh pembangunan fasilitas kolam renang di sebuah hotel, bernilai 1 jika fasilitas tersebut dibanggun, dan bernilai 0 jika fasilitas tersebut tidak dibangun ( X1=0 atau 1).

Metode Branch and Bound Metode Branch and Bound telah menjadi kode computer standar untuk integer programming. Teknik ini dapat diterapkan untuk masalah pure maupun mixed integer programming. Langkah-langkah metode Branch and Bound untuk masalah maksimalisasi adalah sebagai berikut : 1. Selesaikan masalah dengan menggunakan program linar, apabila hasilnya merupakan bilangan integer, maka permasalahan selesai, apabila tidak maka nilai Z yang diperoleh menjadi upper bound. 2. Lakukan program linear kembali sehingga diperoleh nilai Z yang baru untuk dijadikan lower bound. 3. Branch salah satu variabel yang tidak memiliki nilai yang integer berdasarkan hasil pada langkah 1. Bagilah permasalahan tersebut menjadi 2 submasalah yang baru berdasar nilai integer yang berada

44


di atas dan di bawah nilai yang non integer, misal X1 = 3,75 maka buat atasa yang pertama X1 ≥ 4 pada submasalah 1 dan batasan X1 ≤ 3 pada submasalah 2. 4. Buat formulasi masalah dari setiap submasalah yang baru, lalu selesaikan program linear (LP) tersebut :  Apabila hasil dari LP submasalah ternyara tidak feasible maka abaikanlah  Apabila hasil LP submasalah feasible, tetapi tidak memberikan hasil yang integer, maka lanjutkan pada langkah ke 6 5. Apabila hasil dari LP submasalah feasible dan integer maka lihat nilai Z nya apabila nilainya sama dengan upper bound maka solusi optimal tercapai. Tetapi apabila tidak sama dengan upper bound dan lebih besar dari lower bound maka jadikanlah lower bound yang baru. Apabila hasilnya lebih kecil dari lower bound maka abaikanlah. 6. Lakukan perhitungan kembali submaslah yang telah ditentukan, diman upperbound sama dengan nilai maksimum dari fungsi tujuan. Apabila upper bound sama dengan lower bound maka proses berhenti.

Contoh Soal Integer  Maksimum Z = $7X1 + $6X2  Batasan :

2X1 + 3X2 ≤ 12 6X1 + 5X2 ≤ 30 X1, X2 ≥ 0 dan integer

45


Penyelesaian dengan metode grafik, akan diperoleh X1 = 3,75 ; X2 = 1,5 dengan Z = $35,25. Hasil Z = 35,25 menjadi Upper Bound, untuk mencari Lower Bound X1 = 3 dan X2 = 1 maka diperoleh Z=27. Karena hasilnya bukan integer maka kita membagi X1 menjadi 2 submaslah dengan batasan X1 ≥ 4 dan X1 ≤ 3.

46


47


Proses berhenti apabila hasil yang diperoleh integer semua dengan nilai Z ≤ Upper bound.

48


QUESTION 1 Broowns.Id is wondering how to make the right combination of product sales to make the maximum profit. Help Broowns.Id to solve the integer program function using “Branch and Bound” method. Objectives : Zmax = 500X1 + 300X2 Constraint : 8X1 + 4X2 ≤ 36 , 5X1 + 7X2 ≤ 35

QUESTION 2 MKF Furniture wants to make garden table and chair sets. The expected margin for one table is $7 and for one garden chair is $6. But MKF Furniture has limited working time. To design 1 table, need 3 working hours. To design 1 chair need 2 working hours. To assembly 1 table and 1 chair need 4 working hours each. MKF Furniture has 15 working hours left for design and 30 working hours left for assembly. How many garden table and chair that MKF Furniture should make for increase their profit?

SOAL 3 Parambidam Company ingin menemukan kombinasi yang tepat dari produksi bantal lukis yang memberikan profit maksimal. Bantulah Parambidam Company untuk memecahkan masalahnya menggunakan integer dengan metode Branch and Bound! Fungsi Tujuan : Zmax : 35X1 + 30X2 Fungsi Kendala : 10X1 + 15X2 ≤ 60 dan 30X1 + 25X2 ≤ 150

49


SOAL 4 Maksimumkan Z= 5X1 + 7X2 + 4X3 Dengan syarat 3X1 + 4X2 ≤ 28 X3 ≤ 8 2X2 + 3X3 ≤ 12 X1;X2 = non negative integer Buatlah solusi optimumnya dengan menggunakan integer metode zero-one!

SOAL 5 Akira Bakery berencana membeli peralatan baru untuk kelangsungan produksinya antara lain oven, mixer, dan food processor. Biaya penggunaan oven, mixer dan food processor sebesar $400, $350, dan $200. Harga beli oven adalah $6 dan menghabiskan 4 meter2 ruangan. Sedangkan harga beli mixer sebesar $8 dan menghabiskan 3,5 meter2. Sementara untuk food processor harga belinya $10 dan menghabiskan 3 meter2. Pemilik perusahaan hanya memiliki anggaran sebesar $100 dan kapasitas ruang sebesar 50 meter2. Buatlah solusi optimumnya dengan menggunakan integer metode branch & bound!

50


TEACHING ASSISTANT OF MOLMKF 2015/2016 FACULTY OF ECONOMICS AND BUSINESS, PADJADJARAN UNIVERSITY

Salsabila Firdausia / 085669963814 / line : salsabilafirdausia Nabila Nur Afifa / 08568814590 / line : nabilanafifa Abdul Haris Asri / 081321037083 / line : abdulharisasri Rachmatika Anjani / 085229708285 / line : ranisudirgo Shima Umari / 081318168068 / line : shimaumr

51


52


KATA PENGANTAR. Bandung, Januari 2016

Recommend Documents