HAND OUT PENELITIAN OPERASIONAL I. Oleh : Tim Dosen Penelitian Operasional Program Studi Teknik Industri

HAND OUT PENELITIAN OPERASIONAL I

Oleh : Tim Dosen Penelitian Operasional Program Studi Teknik Industri

Fakultas Teknik Universitas Wijaya Putra 2009

Linear Programming

Pengantar • Masalah dasar ekonomi : bagaimana mengalokasikan sumberdaya terbatas untuk memenuhi kebutuhan manusia yang tidak terbatas (optimal allocation) • Linear Programming (LP) merupakan peralatan (tools) untuk membantu memecahkan masalah-masalah ekonomi • LP merupakan dasar untuk memahami berbagai model yang tercakup dalam teknik mathematical programming • Normative vs positive economics

Karakteristik Utama Masalah LP • Terdapat fungsi tujuan yang dapat dinyatakan dalam bentuk kuantitatif • Harus terdapat berbagai alternatif aktivitas yang saling berkompetisi dalam penggunaan sumberdaya yang sama untuk mencapai tujuan • Sumberdaya harus berada dalam jumlah terbatas • Fungsi tujuan dan sistem kendala harus dapat dinyatakan dalam bentuk persamaan atau pertidaksamaan linier matematis

Formulasi Model • Fahami deskripsi masalah, lihat hubunganhubungan yang ada, identifikasikan fungsi tujuan dan variabel keputusan • Identifikasikan kendala yang ada (≤, =, ≥) • Identifikasikan unit pengukuran • Identifikasi koefisien teknis (matriks A) • Susun hubungan variabel keputusan dengan sistem kendala dalam kata-kata • Nyatakan model dalam notasi matematika

Asumsi-asumsi LP •

Asumsi dasar LP: 1. 2. 3. 4. 5.

•

Linearity (proportionality) Additivity Divisibility Certainty (deterministic) Non-negativity

Asumsi tersebut satu-persatu akan dilepas untuk memodelkan berbagai kasus yang bersifat spesifik, seperti 1. Non-linearity → Non Linear Programming 2. Integer (indivisible)→ Integer Programming

Prototype Model Resource Allocation Problem (Furniture Problem) Seorang perajin furniture memproduksi meja dan kursi. Ia mengetahui kebutuhan kayu dan tenaga kerja untuk produkproduk yang dihasilkannya. Sebuah meja membutuhkan 5 m kayu jati, 2 m kamper dan 4 hari kerja. Sedangkan kursi membutuhkan 2 m kayu jati, 3 m kamper dan 2 hari kerja. Keuntungan yang diperoleh dari penjualan meja adalah Rp 12.000/unit dan kursi Rp 8.000/unit. Ia dibatasi oleh ketersediaan sumberdaya yang dimilikinya, yaitu kayu jati sebanyak 150 m dan kamper 100 m serta 80 HK. Ia ingin mengetahui berapa banyak meja dan kursi yang harus diproduksi dengan kendala sumberdaya yang dimilikinya agar dapat diperoleh keuntungan maksimum. Model matematis? Solusi optimum?

Prototype Model Sumberdaya

Produk

Ketersediaan

meja

kursi

Jati

5

2

150

Kamper

2

3

100

HK

4

2

80

12.000

8.000

Profit

• Model matematis Maximize  = 12 X1 + 8 X2 Subject to, 5 X1 + 2 X2  150 2 X1 + 3 X2  100 4 X1 + 2 X2  80 dan X1, X2  0

(kendala jati) (kendala kamper) (kendala HK) (kendala non-negatif)

Contoh Lain Transportation Problem Suatu perusahaan semen memiliki dua lokasi pabrik dan melayani 3 daerah tujuan. Pabrik 1 dan 2 masing-masing menghasilkan 250 ton dan 300 ton per minggu. Sementara kebutuhan di daerah A, B dan C masing-masing 100 ton, 250 ton, 200 ton per minggu. Bagaimana alokasi distribusi dari pabrik ke tujuan dengan biaya transpor minimum jika diketahui biaya transpor ke masing-masing tujuan adalah sbb. Pabrik

Tujuan A

B

C

1

14

12

10

2

12

8

13

Notasi LP Optimize

f  c1 X 1  c2 X 2  ...  cn X n

Subject to,

a11X 1  a12 X 2  ...  a1n X n  b1 a21X 1  a22 X 2  ...  a2n X n  b2 ... am1 X 1  am 2 X 2  ...  amn X n  bm X 1 , X 2 ,..., X n  0

Notasi LP n

Optimize subject to,

f  cj X j j 1

m

n

 a i 1 j 1

dimana,

ij

X j  bi

atau

f  cX

atau

AX  b

c  c1 c2 ... cn   a11 a A   21  ...  am1

a12 a22 ... am 2

... a1n  ... a2 n  ... ...   ... amn 

 b1   X1  b  X  2 2   b  X  ...   ...      bm  Xn 

Solusi Model LP •

Pendekatan grafis 1. Prinsip dasar: feasible region dan isoprofit 2. Keuntungan: memahami terminologi solusi komputer 3. Kelemahan: analisa hanya untuk 2 variabel keputusan

•

Tabel Simplex 1. Prinsip dasar: operasi matriks Gauss-Jordan 2. Keuntungan: memahami prinsip kerja iterasi hingga optimal 3. Kelemahan: terlalu rumit untuk dipecahkan

•

Computer Software 1. Prinsip dasar: iterasi simpleks 2. Kuntungan: banyak tersedia dari software sederhana hingga kompleks (ABQM, LINDO, GAMS 3. Kelemahan: beberapa software membutuhkan pengetahuan tentang syntax komputer

Prototype Model: Solusi Grafis X2 75

redundant Solusi bersifat unik di titik B (5,30)

K. Jati 40

binding HK

A 33.3

feasible region B

binding

K. Kamper C

isoprofit line O

20

30

50

X1

Solusi Grafis •

Kesimpulan 1. Sistem kendala bersama-sama menentukan bentuk set of feasible region 2. Kemiringan fungsi tujuan (=isoprofit/level profit tertentu yang sama) menentukan dimana letak solusi optimum diperoleh 3. Karena bentuk set of feasible region dan kemiringan fungsi tujuan, solusi umumnya merupakan titik sudut (corner solution)

Aspek Teknis 1. Multiple Optima a. Contoh Maximize

f = 3 X1 + 2 X2

subject to,

6 X1 + 4 X2  24 10 X1 + 3 X2  30 X1, X2  0

b. Karakteristik • • •

Solusi tidak bersifat unik (multiple solution) Disebabkan slope fungsi tujuan = slope kendala Memberi banyak pilihan solusi (kebijakan)

Aspek Teknis 2. Unbounded Solution a. Contoh Maximize subject to

f = 2 X1 + 3 X2 X1 + X2 ≥ 3 X1 - 2 X2  4 X1, X2  0

b. Karakteristik • •

Feasible region bukan convex set Kesalahan dalam formulasi masalah

Aspek Teknis 3. Infeasible Solution a. Contoh Maximize subject to

f = 4 X1 + 3 X2 X1 + X2  3 2X1 - X2  3 X1 4 X1, X2  0

b. Karakteristik • •

Feasible region merupakan ruang kosong Kesalahan dalam formulasi masalah

Linier Programming Metode Grafik

Pendahuluan Linear Programming dengan metode grafik untuk fungsi tujuan baik maksimum maupun minimum. Pada Metode Grafik variabel keputusan yang akan muncul adalah 2 variabel. Harapan setelah mempelajari Linear Programming metode grafik adalah : 1. 2. 3. 4.

Mengenal linear programming sebagai alat pengambilan keputusan Merumuskan permasalahan operasi ke dalam bentuk linear programming Menyelesaikan permasalahan linear programming dengan grafik/ matematik Memahami permasalahan infeasibility, unboundedness, alternative optima, dan redundancy.

Metode Grafik Masalah Maksimasi FORMULASI PERMASALAHAN, langkahlangkah : 1.Analisis secara menyeluruh permasalahan

manajerial yang dihadapi 2.Definisikan variabel keputusannya 3.Identifikasikan tujuan dan kendalanya 4.Gunakan variabel keputusan untuk merumuskan fungsi tujuan dan fungsi kendala secara matematis.

Contoh Permasalahan PT Krisna Furniture yang akan membuat meja dan kursi. Keuntungan yang diperoleh dari satu unit meja adalah $7,- sedang keuntungan yang diperoleh dari satu unit kursi adalah $5,-. Namun untuk meraih keuntungan tersebut Krisna Furniture menghadapi kendala keterbatasan jam kerja. Untuk pembuatan 1 unit meja dia memerlukan 4 jam kerja. Untuk pembuatan 1 unit kursi dia membutuhkan 3 jam kerja. Untuk pengecatan 1 unit meja dibutuhkan 2 jam kerja, dan untuk pengecatan 1 unit kursi dibutuhkan 1 jam kerja. Jumlah jam kerja yang tersedia untuk pembuatan meja dan kursi adalah 240 jam per minggu Jumlah jam kerja untuk pengecatan adalah 100 jam per minggu.

Berapa jumlah meja dan kursi yang sebaiknya diproduksi agar keuntungan perusahaan maksimum?

Penyelesaian Permasalahan Formulasi Permasalahan : 1. Analisis • Tujuan perusahaan adalah memaksimumkan profit • Variabel yg akan dicari berapa banyak meja (x1) dan kursi (x2) yang harus dibuat.

Lanjutan 2. Variabel Keputusan Variabel yg akan dicari berapa banyak meja (x1) dan kursi (x2) yang harus dibuat

Lanjutan 3. Tentukan Fungsi Tujuan dan kendalanya Fungsi Tujuan (Z mak) Z mak = 7x1 + 5x2 Kendala 1. 4x1 + 2x2  240 2. 2x1 + 1x2  100 3. x1  0 4. x2  0

Lanjutan… Penyelesaian untuk menggabarkan Grafik • Tentukan Bidang 2 dimensi untuk

menggambar grafik x1

Jika x1 positif, x2 positif

Jika x1 positif, x2 negatif

x2

0 Jika x1 negatif, x2 negatif

Jika x1 negatif, x2 positif

Ubah tanda Batasan /kendala dg = 1. 2.

4x1 + 2x2  240  4x1 + 2x2 = 240 2x1 + 1x2  100  2x1 + 1x2 = 100

Jika memungkinkan sederhanakan : (yang bisa disderhanakan hanya kendala no 1) 4x1 + 2x2 = 240  2x1 + x2 = 120

Cari titik potong dengan sumbu x1 dan x2 1. Kendala 1. 2x1 + x2 = 120 Titik potong dg sumbu x1, nilai x1 = 0  Hasil (x2,x1) : (120,0) Titik Potong dg sumbu x2, nilai x2 = 0  Hasil (x2,x1) : ( 0, 60)

2. Kendala 2. 2x1 + 1x2 = 100 Titik potong dg sumbu x1, nilai x1 = 0  Hasil (x2,x1) : (100,0) Titik Potong dg sumbu x2, nilai x2 = 0  Hasil (x2,x1) : (0,50)

x1 x2 0

120

60 0 x1 x2 0

100

50 0

Gambarkan grafik ke dalam bidang x1

60

50

2x1 + x2 = 120

2x1 + 1x2 = 100

0

100

x2 120

Gambarkan grafik dg memasukkan tanda x1

60

50

2x1 + x2 = 120

2x1 + 1x2 = 100

0

100

x2 120

Masalah minimasi Seorang ahli penata diet merencanakan untuk membuat dua jenis makanan yaitu makanan A dan B. Kedua makanan tersebut menagndung vitain dan protein. Jenis makanan A paling sedikt diproduksi 2 unit dan jenis makanan B paling sedikit diproduksi 1 unit. Tabel 1 menunjukkan jumlah vitamin dan protein dalam setiap jenis makanan

Tabel 1 Jenis makanan

Vitamin (unit)

Protein (unit)

Biaya per unit (Rp)

A B Minimum Kebutuhan

2 1 8

2 3 12

100 80

Masalah-masalah khusus dalam LP metode Grafik • Multiple Optimum Solution Solusi yang dihasilkan lebih dari satu • No Feasible Solution Tidak ada solusi yang feasible • Unbounded objective function Tidak ada nilai Z dalam daerah feasible yang akan dipilih.

Problem LP 1. PT Lezat merencanakan untuk membuat dua jenis kue kering donat dan bolu. Keuntungan per lusin donat Rp. 600,- dan perlusin bolu Rp. 325,-. Pembuatan kue donat menggunakan peralatan khusus dengan waktu 1/6 jam setiap lusin dan kue bolu menggunakan 2 jam tenaga kerja setiap lusin. Tenaga kerja Lezat 3 orang dan setiap orang dapat bekerja 40 jam per minggu. Permintaan kue donat tidak melebihi 500 lusin per minggu. Tentukan optimal PT lezat.

2. Pdagang eceran Lumayan menyediakan biaya advertensi bulan mendatang Rp. 200.000,-. Ada dua alternatif media yang sedang dipertimbangkan yaitu majalah dan surat kabar. Biaya advertensi daam majalah hanya Rp. 2.500,- dan dapat menjangkau 50 konsumen. Biaya surat kabar 12.000,- dan dapat menjangkau 600 konsumen. Perusahaan merencakan paling sedikit 5 x permuatan dalam surat kabar, tetapi tidak lebih dari 30 x selama satu bulan. Jumlah advertensi di surat kabar paling sedikit 2x jumlah advertensi di majalah. Tentukan kombinasi advertensi yang terbaik, agar memaksimumkan jumlah konsumen yang dapat dijangkau selama satu bulan ?

3. PT Kido memproduksi dua jenis botol minuman byi. Dua jenis produk tersebut diproses melalui dua jenis mesin. Waktu proses (jam) setiap mesin utk ke-2 jenis produk terlihat dalam tabel 1. PT Kido ingin memodifikasi botol bayi, untuk itu diperlukan tambahan satu jenis mesin. Setiap jenis botol memerlukan wkt pemrosesan masing-masing 1 jam di mesin baru dengan kapasitas 200 jam per bulan

Tabel 1 Jenis Botol

Mesin A

B

1 2

2 1/2

1 3

Kapasitas

320

300

Keuntungan (Rp) 750 500 Jam per bulan

6s-1

Linear Programming

DUALITAS DALAM LINEAR PROGRAMING

Operations Management PENELITIAN OPERASIONAL 1

William J. Stevenson

6s-2

Linear Programming

KONSEP DUALITAS 

Setiap persoalan linear programing mempunyai suatu linear program yang berkaitan, yang disebut “dual”.



Solusi dari persoalan asli LP (Primal), juga memberikan solusi pada dualnya

6s-3

Linear Programming

Hubungan primal-dual

Primal

Dual

Batasan i

Variabel i

Fungsi Tujuan

Nilai Kanan

6s-4

Linear Programming

Contoh : (masalah primal) I1

I2

Kapasitas Maksimum

1

2

0

8

2

0

3

15

3

6

5

30

Sumbangan laba

3

5

Merek

Mesin

Tabel primal-dual X1

X2

Y1

2

0

≤8

Y2

0

3

≤ 15

Y3

6

5

≤ 30

≥3

≥5

Merek Mesin

6s-5

Linear Programming

Tabel primal-dual Merek

X1

X2

Y1

2

0

≤8

Y2

0

3

≤ 15

Y3

6

5

≤ 30

≥3

≥5

Mesin

Fungsi primal-dual Kunci 1

Batasan i Variabel i Kunci 2 Fungsi Tujuan Nilai Kanan

Tujuan : Maks Z = 3X1 + 5X2

Tujuan : Min Y = 8Y1 + 15Y2 + 30Y3

Batasan : 2X1 3X2 6X1 + 5X2

Batasan : 2Y1 + 6 Y3 3Y2 + 5 Y3

dan X1 ≥ 0, X2 ≥ 0

8  15  30

≥3 ≥5

dan Y1 ≥ 0, Y2 ≥ 0, Y3 ≥ 0

6s-6

Linear Programming

Interpretasi Ekonomis

Fungsi primal n Tujuan : Maks Z   C j X j j 1

n

Batasan

a j 1

Xj Cj Z bi aij

ij

X j  bi

= Tingkat aktivitas ke j = Laba persatuan aktivitas j = Laba total dari seluruh aktivitas = Jumlah sumber i yang tersedia = jumlah sumber i yang “dipakai” oleh setiap satuan aktivitas j

Dengan menggantikan Zj, metode simpleks dapat diartikan mencari nilai Ym Fungsi dual m Tujuan : Min Y0   biYi m

Batasan

a Y  C i 1

Yi

i 1

ij i

j

= kontribusi persatuan sumber i terhadap laba

6s-7

Linear Programming

Hasil masalah dual

Y = 8(0) + 15(5/6) + 30(1/2)

Y = 271/2

Tujuan : Min Y = 8Y1 + 15Y2 + 30Y3 Batasan : 2Y1 + 6 Y3 3Y2 + 5 Y3

≥3 ≥5

dan Y1 ≥ 0, Y2 ≥ 0, Y3 ≥ 0 Analisis Simplex Y1 = 0, Y2 = 5/6, Y3 = 1/2

WIJAYA PUTRA UNIVERSITY

Penelitian Operasional Perkembangan teknologi dalam era globalisasi yang begitu cepat dan kompleks, salah satunya Penelitian Operasional sebagai salah satu ilmu terapan praktis yang diperlukan dalam penyelesaian suatu permasalahan yang semakin kompleks melalui pendekatan kuantitatif

Penelitian Operasional Thomas dan Da Costa (1979) Penerapan Penelitian Operasional dilakukan sekurang-kurangnya dalam 12 kegiatan manajemen di berbagai bidang kehidupan, terutama manufaktur :            

Perencanaan dan peramalan pasar Inventory control Perencanaan dan penjadwalan produksi Penganggaran biaya Transportasi Perencanaan lokasi pabrik Pengendalian mutu Penelitian promosi dan penjualan Penggantian mesin dan peralatan Pemeliharaan Akunting Pengemasan produk

Penelitian Operasional  Penelitian Operasional adalah sebuah pendekatan

kuantitatif yang menggunakan metode-metode optimisasi untuk menyelesaikan suatu persoalan matematis.  Penggunaan program-program komputer dalam pengajaran Operations Research di antaranya : LINDO, GINO, VNO, Microcomputer Model for Management Decision Making, Computer Models for Management Science, QSB, QSB+, QSQUANT, STORM, CMOM, dan lainnya.

Penelitian Operasional Jilid 1 Bagian I : Pemahaman Awal Bagian II : Pemrograman Linear Bagian III : Perluasan Model Pemrograman Linear Jilid 2 Bagian IV : Model-model Khusus Bagian V : Model-model Lanjutan

Bagian I Pemahaman Awal  Bab 1 : Pemahaman Awal

Bab 1 : Pemahaman Awal 1.1 Sejarah Penelitian Operasional 1.2 Penerapan Penelitian Operasional 1.3 Peranan Model dalam Proses Pembuatan Keputusan 1.4 Parameter dan Variabel 1.5 Parameter Biaya dan Laba 1.6 Keputusan Optimal 1.7 Pembahasan dan Penyajian 1.8 Program—program Komputer

Sejarah Penelitian Operasional  Teori Evolusi Manajemen : Penelitian Operasional

mulai berkembang sejak tahun 1945, pada saat Perang Dunia Kedua.  Pendekatan kuantitatif dalam menyelesaikan persoalan, di mana matematika dan statistika memegang peranan yang sangat dominan telah menempatkan operations research secara teoritis sebagai ilmu pengetahuan yang berakar Scientific Management yang dipelopori oleh Taylor pada Abad XVIII. Di Inggris, dikenal sebagai Operational Research.

Penerapan Operations Research Penelitian berbagai industri di Amerika menggunakan teknik-teknik Operations Research Penelitian Turban di tahun 1969 Teknik-teknik Operations Research Statistical Analysis Simulation Linear programming Inventory Theory PERT/CPM Dynamic Programming Non Linear Programming Queueing Theory Heuristic Programming Miscellaneous

Frekuensi Penggunaan (%) 29 25 19 6 6 4 3 1 1 6

Model dalam Proses Pembuatan Keputusan  Model Verbal  Model Visual  Model Matematis Kurva biaya rata-rata produksi

Parameter Biaya dan Laba  Biaya Variabel : Elemen biaya yang berubah-ubah

secara langsung dengan satuan yang diproduksi  Biaya Tetap : Biaya yang tidak berubah pada setiap satuan barang yang diproduksi  Biaya Semi Variabel : Elemen biaya yang berubah dengan arah yang sama dengan unit yang diproduksi namun kurang proporsional, atau dengan kata lain tidak linear.

Analisis Regresi terhadap biaya total

Output analisis regresi program Microstat

Model dan Penyelesaian Optimal Dunia Nyata

Masalah

PertimbanganPertimbangan Manajemen

Dunia Simbol

Abstraksi Masalah ke Model

Pembuatan Keputusan

Intuisi dan Pengalaman

Model

Analisis

Interpretasi Hasil Olahan Optimal

Penyelesaian Optimal

Program-program Komputer  LINDO (Linear Interaktif Discrete Optimizer).  Solver Microsoft Excel  Graphic LP Opimizer Versi 2.6  Crystal Ball

Bagian II : Pemrograman Linear  Bab 2 : Pemrograman Linear: Konsep Dasar  Bab 3 : Pemrograman Linear: Analisis Geometri  Bab 4 : Pemrograman Linear : Algoritma Simpleks  Bab 5 : Pemrograman Linear : Dualitas, Analisis

Sensitivitas, dan Output LINDO  Bab 6 : Pemrograman Linear : Kasus-kasus Khusus

Bab 2 : Pemrograman Linear : Konsep Dasar 2.1 Pengantar 2.2 Linearitas dan Dalil Matematika 2.3 Model Pemrograman Linear 2.4 PT Sukra Rasmi 2.5 Empat Sehat Lima Sempurna 2.6 Break Even Point Multi Produk 2.7 Ringkasan 2.8 Latihan-latihan 2.9 Soal-soal

Konsep Dasar Pemrograman Linear (Linear Programming) adalah salah satu model Operations Research yang menggunakan teknik Optimisasi matematika linear di mana seluruh fungsi harus berupa fungsi matematika linear.

Model Pemrograman Linear Variabel Keputusan : Variabel persoalan yang akan mempengaruhi nilai tujuan yang hendak dicapai. 2. Fungsi Tujuan : Di mana tujuan yang hendak dicapai harus diwujudkan ke dalam sebuah fungsi matematika linear, yang kemudian fungsi itu dimaksimumkan atau diminimumkan terhadap kendala-kendala yang ada. 3. Fungsi Kendala : Kendala dalam hal ini dapat diumpamakan sebagai suatu pembatas terhadap kumpulan keputusan yang mungkin dibuat dan harus dituangkan ke dalam fungsi matematika linear yang dihadapi oleh manajemen. 1.

PT SUKRA RASMI PT Sukra Rasmi memproduksi Sukra dan Rasmi, bahan baku utama untuk pembuatan produk sangling yang dihasilkan melalui proses Penghancuran dan Penghalusan. Matriks Kasus Sukra Rasmi

X1

X2

Keterangan

Sukra

Rasmi

Pemrosesan:

(jam)

(jam)

Penghancuran

2

1

20 jam

Penghalusan

2

3

32 jam

Permintaan Rutin Contribution Margin

2 ton Rp 40,-

Rp 30,-

Kapasitas

Model matematis pemrograman linear

Break Even Point Multi Product Break Even Point Analysis sebagai salah satu alat yang sangat terkenal di dalam analisis manajerial telah diterapkan pada berbagai bidang kegiatan manajerial, di antaranya : 1. Cost, Volume, and Profit Analysis (Analisis Biaya dan Laba) 2. Financial leverage analysis (Keputusan Keuangan) 3. Capital Investment Decision (Keputusan Investasi) 4. Plant Location (Keputusan Lokasi) 5. Make or Buy Decision (Keputusan Membeli atau Membuat) 6. Pricing Policy (Kebijakan Penentuan Harga)

Model matematis lengkap kasus Break Even Point KUSUMATEX

Bab 3 : Pemrograman Linear : Analisis Geometri 3.1 Pengantar 3.2 Sistem dan Bidang Kerja 3.3 Menggambar Pertidaksamaan dan Persamaan 3.4 Daerah yang Memenuhi Kendala 3.5 Menggambar Fungsi Tujuan 3.6 Geometri Sukra Rasmi : Kasus Pemaksimuman Fungsi Tujuan 3.7 Geometri Gupita : Kasus Peminimuman Fungsi Tujuan 3.8 Kendala Aktif dan Kendala Tidak Aktif 3.9 Ringkasan 3.10 Latihan-latihan 3.11 Soal-soal 3.12 Suplemen : Graphic Linear Programming Optimizer

Pemrograman Linear : Analisis Geometri SISTEM DAN BIDANG KERJA

Sistem untuk menyatakan hubungan antara aljabar dan geometri adalah bidang yang dibagi menjadi empat bidang oleh sumbu tegak (absis) dan sumbu datar (ordinat). Bidang tersebut dikenal sebagai kuadran.

Menggambar Pertidaksamaan dan Persamaan

Menggambar Pertidaksamaan dan Persamaan

Daerah yang memenuhi kendala (DMK)

Geometri Sukra Rasmi: Kasus Pemaksimumam Fungsi Tujuan Model matematis Sukra Rasmi : 1. Fungsi Tujuan : Maks 40 X1 + 30 X2 Terhadap kendala-kendala : 2. 2X1 + X2 ≤ 20 3. 2X1 + 3X2 ≤ 32 4. 2X1 - X2 ≤ 0 5. X2 ≤ 2

DMK Kasus Rasmi

Geometri Gupita: Kasus Peminimuman Fungsi Tujuan

DMK Kasus Gupita

Suplemen: Graphic LP Optimizer Graphic Linear Programming Optimizer (GLP) dirancang untuk membantu analisis masalah pemrograman linear, di mana analis dapat melihat perilaku kendala-kendala dan fungsi tujuan dalam sebuah proses optimisasi pemrograman linear. Selain memberi pilihan pemaksimuman dan peminimuman fungsi tujuan pada sebuah kasus pemrograman linear, GLP juga berfungsi untuk mempelajari sensitivitas parameter fungsi kendala dan tujuan secara langsung sehingga analis dapat langsung melihat hasilnya.

Windows GLP Sukra Rasmi, maksimum fungsi tujuan

Bab 4 : Pemrograman Linear : Algoritma Simpleks 4.1 Pengantar 4.2 Slack dan Surplus 4.3 Titik Sudut dan Karakteristik Variabel 4.4 Titik Sudut Degenerate dan Non Degenerate 4.5 Variabel Basis dan Nonbasis 4.6 Tabel Simpleks 4.7 Algoritma Simpleks I : Kasus Bawika 4.8 Ringkasan 4.9 Latihan-latihan 4.10 Soal-soal

Pemrograman Linear : Algoritma Simpleks Algoritma Simpleks adalah sebuah prosedur matematis berulang untuk menemukan penyelesaian optimal soal pemrograman linear dengan cara menguji titik-titik sudutnya.

Slack dan Surplus Slack Variabel adalah variabel yang berfungsi untuk menampung sisa kapasitas pada kendala yang berupa pembatas Slack Variabel pada setiap kendala yang aktif pasti bernilai nol Slack variabel pada setiap kendala tidak aktif pasti bernilai positif

Kendala aktif dan slack variabel yang bernilai nol

Surplus Variabel adalah variabel yang berfungsi untuk menampung kelebihan nilai ruas kiri pada kendala yang berupa syarat. Surplus variabel pada setiap kendala aktif pasti bernilai nol Surplus variabel pada setiap kendala tidak aktif pasti bernilai positif Kendala-kendala aktif pada setiap macam kendala pasti memiliki slack variabel atau surplus variabel yang bernilai nol

Tabel Simpleks Algoritma simpleks adalah sebuah prosedur berulang untuk menyelesaikan persoalan matematis pemrograman linear denga cara menguji titik-titik sudut DMK. Di dalam algoritma simpleks di mana setiap pengujian titik sudut membutuhkan bantuan sebuah tabel untuk menentukan apakah nilai ekstrem tujuan telah tercapai, maka tabel ini disebut Tabel Simpleks. Proses penyelesaian sebuah tabel simpleks pada pengujian sebuah titik sudut adalah selalu sama, proses ini berulang hingga ditemukan sebuah titik sudut yang menghasilkan nilai tujuan ekstrem. Tabel di mana nilai tujuan ektrem ini ditemukan disebut Tabel Simpleks Optimal.

Algoritma Simpleks : Kasus Bawika

Bab 5 : Pemrograman Linear : Dualitas, Analisis Sensitivitas, dan Output LINDO 5.1 Pengantar 5.2 Dualitas 5.3 Analisis Sensitivitas 5.4 Analisis Sensitivitas Bawika 5.5 LINDO 5.6 Ringkasan 5.7 Latihan-latihan 5.8 Soal-soal 5.9 Suplemen : Penyelesaian Pemrograman Linear dengan Solver Excel

Dualitas Konsep Dualitas menjelaskan secara matematis bahwa sebuah kasus pemrograman linear berhubungan dengan sebuah kasus pemrograman linear yang lain. Bila kasus pemrograman pertama disebut Primal maka kasus pemrograman linear kedua disebut Dual; sehingga penyelesaian kasus primal secara otomatis akan menyelesaikan kasus dual, demikian pula sebalikya.

Model matematis Dual-Primal

Hubungan antara primal dengan dual secara lengkap

Hubungan antara primal-dual bawika dengan program LINDO

Analisis Sensitivitas Analisis sensitivitas menjelaskan sampai sejauh mana parameter-parameter model pemrograman linear, yaitu koefisien fungsi tujuan dan nilai ruas kanan kendala, boleh berubah tanpa harus mempengaruhi jawaban optimal atau penyelesaian optimal. Penyelesaian Optimal menghasilkan informasi : 1. Nilai Variabel Keputusan Optimal 2. Nilai Fungsi Tujuan Ekstrem 3. Nilai Slack/Surplus Variable 4. Nilai Dual Price/Shadow Price

Hasil Output LINDO untuk kasus Bawika

Penyelesaian Pemrograman Linear dengan Solver Excel

Bab 6 : Pemrograman Linear : Kasuskasus Khusus 6.1 Pengantar 6.2 Degenerasi 6.3 Multiple Optimal Solution 6.4 No Feasible Solution 6.5 Nilai Tujuan yang Tidak Terbatas 6.6 Ringkasan

Degenerasi Karakteristik di mana jumlah variabel positif atau variabel basis lebih kecil dari jumlah kendalanya disebut sebagai peristiwa degenerasi. Penggambaran titik-titik sudut degenerasi

Multiple Optimal Solution (MOS) Multiple Optimal Solution adalah sebuah kasus khusus dalam penyelesaian sebuah kasus pemrograman linear di mana titik sudut ekstrem yang menghasilkan nilai fungsi tujuan ekstrem adalah lebih dari satu. Gejala MOS

No Feasible Solution Penyelesaian sebuah kasus pemrograman linear sering menghasilkan jawaban yang tidak terduga, salah satunya adalah no feasible solution atau tidak adak penyelesaian nyata. Output LINDO, no feasible solution

Bagian III : Perluasan Model Pemrograman Linear  Bab 7 : Pemrograman Linear : Bilangan Bulat (Integer

Programming)  Bab 8 : Transportasi dan Penugasan  Bab 9 : Goal Programming  Bab 10: Jaringan (Network)

Bab 7 : Pemrograman Linear : Bilangan Bulat (Integer programming) 7.1 Pengantar 7.2 Pemrograman Bilangan Bulat (General Integer Programming) 7.3 Pemrograman 0-1 (Binary Integer ) 7.4 Sukra Rasmi : Pemilihan Kendala 7.5 Algol : Pemilihan Biaya Tetap dan Biaya Variabel Minimum 7.6 Deimos : Pilihan Alternatif Metode Operasi 7.7 Ringkasan 7.8 Latihan-latihan 7.9 Soal-soal

Pemrograman bilangan bulat Pemrograman bilangan bulat adalah sebuah model penyelesaian matematis yang memungkinkan hasil penyelesaian kasus pemrograman linear yang berupa bilangan pecahan diubah menjadi bilangan bulat tanpa meninggalkan optimalitas penyelesaian. Teknik Integer programming salah satunya adalah Branch dan Bound.

Kasus pemrograman linear Dharmika Penyelesaian Dharmika

Max 2X1 + 3X2 ST X1 + 2X2 ≤ 16 3X1 + 2X2 ≤ 30 X1, X2 ≥ 0 dan integer

Kasus Dharmika dengan LINDO

Pemrograman integer Dharmika dengan Solver Excel

Bab 8 : Transportasi dan Penugasan 8.1 Pengantar 8.2 Model Dasar Transportasi 8.3 Kasus Transportasi : Denebula 8.4 Denebula : Analisis Komputer LINDO 8.5 Model Transportasi dengan Solver Excel 8.6 Assignment atau Penugasan 8.7 Penugasan dengan Solver Excel 8.8 Transportasi Bowman 8.9 Ringkasan 8.10 Latihan-latihan 8.11 Soal-soal

Model dasar transportasi Model transportasi secara khusus berkaitan erat dengan masalah pendistribusian barang-barang dari pusat-pusat pengiriman atau sumber ke pusat-pusat penerimaan atau tujuan. Persoalan yang ingin dipecahkan oleh model transportasi adalah penentuan distribusi barang yang akan meminimumkan biaya total distribusi. Model transportasi memecahkan masalah pendistribusian barang dari sumber ke tujuan dengan biaya total distribusi minimum

Matriks Transportasi

Flow Chart Algoritma Transportasi

Kasus Transportasi Denebula Denebula : Nama sebuah perusahaan penghasil suatu jenis jamur di daerah Kaliurang, Yogyakarta. Denebula memiliki tiga cabang di antaranya Purwokerto, Semarang, dan Madiun

Agen

Permintaan

Purwokerto

5000 Kg

Semarang

4500 Kg

Madiun

5500 Kg

Kasus Transportasi Denebula Pusat Penyemaian

Kapasitas

Yogyakarta

4000 Kg

Magelang

5000 Kg

Surakarta

6000 Kg

Biaya angkut per unit dari pusat penyemaian ke agen Pabrik

Agen Purwokerto

Semarang

Madiun

Yogyakarta

4

5

7

Magelang

6

3

8

Surakarta

5

2

3

Matriks transportasi Denebula

Transportasi Bowman Matriks jadwal produksi Bowman

Bab 9 : Goal Programming 9.1 Pengantar 9.2 Konsep Dasar 9.3 Empat Macam Kendala Sasaran 9.4 Goal Programming Analisis Geometri 9.5 Masalah Bobot dan Prioritas Sasaran 9.6 Goal Programming : Algoritma Kompleks 9.7 Ringkasan 9.8 Latihan-latihan 9.9 Soal-soal

Goal Programming Model Goal programming merupakan perluasan dari model pemrograman linear, sehingga seluruh asumsi, notasi, formulasi model matematis, prosedur perumusan model dan penyelesaiannya tidak berbeda. Perbedaan hanya terletak pada kehadiran sepasang variabel deviasional yang akan muncul di fungsi tujuan dan fungsi-fungsi kendala.

Goal Programming Variabel deviasional : Berfungsi untuk menampung penyimpangan atau deviasi yang akan terjadi pada nilai ruas kiri suatu persamaan kendala terhadap nilai ruas kanannya. Variabel deviasional terbagi menjadi dua : 1. Variabel deviasional untuk menampung deviasi yang berada di bawah sasaran yang dikehendaki 2. Variabel deviasional untuk menampung deviasi yang berada di atas sasaran yang dikehendaki

Goal Programming Empat Macam Kendala Sasaran : Untuk mewujudkan suatu sasaran dengan nilai tertentu 2. Untuk mewujudkan suatu sasaran di bawah nilai tertentu 3. Untuk mewujudkan suatu sasaran di atas nilai tertentu 4. Untuk mewujudkan suatu sasaran yang ada pada interval nilai tertentu 1.

Goal Programming : Analisis Geometri Geometri Bawika Optimal

Goal Programming Tiga macam sasaran di dalam Goal Programming :

Sasaran-sasaran dengan prioritas yang sama 2. Sasaran-sasaran dengan prioritas yang berbeda 3. Sasaran-sasaran dengan prioritas dan bobot yang berbeda 1.

Goal Programming Tabel Awal Simpleks Kasus Goal Programming Bawika tanpa prioritas

Bab 10 : Jaringan (Network) 10.1 Pengantar 10.2 Dari Gantt Milestone Chart ke Grantt Chart 10.3 Terminologi Jaringan 10.4 Distribusi Terkendali 10.5 Rentang Jaringan Minimum 10.6 Rute Terpendek 10.7 Aliran Maksimum 10.8 Ringkasan 10.9 Latihan-latihan 10.10 Soal-soal

Jaringan (Network) Jaringan (Network) merupakan sebuah istilah untuk menandai model-model yang secara visual bisa diidentifikasi sebagai sebuah sistem jaringan yang terdiri dari rangkaian-rangkaian noda (node) dan kegiatan (activity).

Gantt Milestone Chart Gantt Milestone Chart, gagasan dasar

Gantt Milestone Chart Gantt Milestone Chart, kegiatan-kegiatan dalam satu pekerjaan masih terpisah

Gantt Milestone Chart Perubahan Gantt Chart menuju jaringan (Network)

Gantt Milestone Chart Bagan jaringan

Terminologi Jaringan

Contoh-contoh sistem jaringan

Distribusi terkendali Tiga macam noda dalam model distribusi terkendali : 1. Noda sumber yang menunjukkan asal sebuah arus atau dari mana sebuah arus akan mengalir 2. Noda tujuan yang menunjukkan akhir tujuan sebuah arus atau hendak ke mana sebuah arus akan mengalir 3. Noda transit yang menunjukkan tujuan sementara atau terminal sementara yang akan dilewati oleh sebuah arus yang akan menuju noda tujuan berikutnya atau noda tujuan akhir

Konsep keseimbangan arus

Rentang Jaringan Minimum Model rentang jaringan minimum adalah salah satu model jaringan yang menjelaskan pemilihan hubungan antar noda sedemikian rupa sehingga jaringan hubungan itu akan membuat seluruh noda terhubung dengan panjang hubungan total terpendek

Antares : Kasus rentang jaringan minimum

Rute terpendek Model rute terpendek adalah salah satu model jaringan yang dapat digunakan untuk menentukan jarak terpendek dari berbagai alternatif rute yang tersedia.

Model rute terpendek Antares yang optimal

Pengantar Integer Programming

Model Integer Programming  Permasalahan integer programming (IP) adalah suatu Program

Linear (LP) yang beberapa atau seluruh variabel yang digunakan merupakan bilangan integer positif  Jenis-jenis permasalahan IP: 

Pure IP problem: jika semua variabel harus bernilai integer Maximize z = 3x1 + 4x2 subject to 5x1 + 8x2 ≤ 24 x1, x2 ≥ 0, x1 dan x2 integer



Mixed IP problem: jika hanya beberapa variabel yang bernilai integer Maximize z = 3x1 + 4x2 subject to 5x1 + 8x2 ≤ 24 x1, x2 ≥ 0, x1 integer



0-1 IP problem: jika semua variabel harus bernilai 0 atau 1 Maximize z = 3x1 + 4x2 subject to 5x1 + 8x2 ≤ 24 x1, x2 = 0 or 1

Integer Programming dan LP relaxation  Permasalahan

IP biasanya lebih sulit dibandingkan dengan permasalahan LP

untuk diselesaikan

 Hal ini disebabkan banyaknya kombinasi nilai integer yang harus

diuji, dan setiap kombinasi membutuhan penyelesaian “normal” LP atau NLP

 LP relaxation dari IP adalah LP yang diperoleh dengan

menghilangkan pembatas semua bilangan integer atau pembatas 

Contoh Pure IP problem : Maximize z = 3x1 + 4x2 subject to 5x1 + 8x2 ≤ 24 x1, x2 ≥ 0, x1 dan x2 integer



Contoh Pure IP problem yang telah di-longgarkan (relax): Maximize z = 3x1 + 4x2 subject to 5x1 + 8x2 ≤ 24 x1, x2 ≥ 0

Pendekatan sederhana solusi IP Pendekatan 1:  Cari seluruh kemungkinan solusi  Tentukan nilai fungsi tujuannya  Pilih nilai maksimum (minimum) Pendekatan 2:  Selesaikan LP relaxation  Bulatkan pada solusi integer yang feasibel terdekat

3 2

x2

7x1 + 4x2= 13

1 x

x

x

1

2

x1

x

3

Solusi Integer Programming Contoh Problem: Max 1200 x1 + 2000 x2 ST: 2x1 + 6 x2  27 x2  2 3x1 + x2  19 x1 , x2  0 and Integer

x2 6

5

4

3

Penyelesaian problem Integer Programming, Apakah solusi LP dibulatkan untuk mendapakan solusi IP…?

2

1

x1 1

2

3

4

5

6

LP Optimal x1 = 5 7/16 x2 = 2 11/16

7

8

Solusi Integer Programming (2) LP relaxation, kemudian dibulatkan ? x2

Max 1200 x1 + 2000 x2 ST: 2x1 + 6 x2  27 x2  2 3x1 + x2  19 x1 , x2  0 and Integer

6

Pembulatan?

5

x1 = 5 x2 = 3

Pembulatan ke atas? x1 = 6 x2 = 3

4

3

Pembulatan ke bawah? x1 = 5 x2 = 2

2

1

x1 1

2

3

4

5

6

LP Optimal x1 = 5 7/16 x2 = 2 11/16

7

8

Solusi Integer Programming (3) x2

IP Optimal x1 = 4 x2 = 3

6

5

4

3

2

1

x1 1

2

3

4

5

6

7

8

Untuk MAX problem: nilai optimal dari IP ≤ nilai optimal dari LP relaxation

Pemodelan Integer Programming

Contoh 1: Problem investasi  Perusahaan Stockco mempertimbangkan empat jenis investasi  Modal yang tersedia untuk investasi sebesar $ 14,000  Formulasikan model integer programming ini untuk

memaksimumkan NPV dari investasi-investasi berikut:

Pilihan Investasi Modal NPV

1 $5000 $16000

2 $7000 $22000

3 $4000 $12000

4 $3000 $8000

SOLUSI: xi = banyaknya modal yang diinvestasikan pada jenis ke-i Maximize z = 16 x1+ 22 x2 + 12 x3 + 8 x4 Subject to 5 x1 + 7 x2 + 4 x3 + 3 x4 ≤ 14 x1, x2, x3, x4 = 0, 1

Pengembangan Problem investasi Perusahaan Stockco mempertimbangkan batasan-batasan “logis” berikut ini : 1. Tepat 3 investasi yang terpilih 2. Jika investasi ke-2 terpilih, maka investasi ke- 1 juga terpilih 3. Jika investasi ke- 1 terpilih, maka investasi ke- 3 tidak terpilih 4. Salah satu dari investasi ke- 3 atau ke-4 harus terpilih, tetapi tidak dapat kedua-duanya Tambahan pembatas: 1. Tepat 3 investasi yang terpilih x1+ x2+ x3+ x4 =3 2. Jika investasi ke-2 terpilih, maka investasi ke- 1 juga terpilih x1 ≥ x2 3. Jika investasi ke- 1 terpilih, maka investasi ke- 3 tidak terpilih x1 + x3 ≤ 1 4. Salah satu dari investasi ke- 3 atau ke-4 harus terpilih, tetapi tidak dapat kedua-duanya x3 + x4 = 1

Contoh 2: Pemilihan pemain bola basket Perkumpulan bola basket “Pasti Menang” sedang menghadapi kompetisi tingkat nasional. Sang pelatih hendak memilih 5 dari 7 pemain yang akan diturunkan dalam pertandingan malam nanti. Data-data pemain seperti terlihat pada tabel dibawah ini: Pemain Guard 1 Yes 2 No 3 Yes 4 No 5 Yes 6 No 7 Yes

Posisi Kemampuan Forward Center Ball-Handling Shooting Rebounding Total No No 3 1 2 6 No Yes 1 2 1 4 Yes No 1 3 1 5 Yes Yes 1 2 1 4 Yes No 2 1 3 6 Yes Yes 1 3 1 5 Yes No 1 2 2 5

Pemilihan pemain bola basket Pembatas yang dialami pelatih adalah sebagai berikut: 1. Harus ada tepat lima pemain, dengan syarat:  Sedikitnya empat pemain sebagai penyerang.  Sedikitnya dua pemain sebagai pemain depan.  Sedikitnya satu pemain sebagai pemain tengah. 2. Rata-Rata tingkat ketrampilan pemain paling sedikit 2. 3. Salah satu dari pemain ke-2 atau pemain ke-3 harus bermain. 4. Jika pemain ke-3 bermain, maka pemain ke-6 tidak bisa bermain. 5. Jika pemain ke-1 bermain, maka pemain ke-4 dan ke-5 harus bermain juga.

Solusi : Pemilihan pemain bola basket (1) Variabel Keputusan Xi = 1, jika pemain ke-i diturunkan ke lapangan. = 0, jika pemain ke-i tidak diturunkan Fungsi tujuan: Max 6 x1 + 4 x2 + 5 x3 + 4 x4 + 6 x5 + 5 x6 + 5 x7 Pembatas : (1a) Harus ada tepat lima pemain turun ke lapangan x1 + x2 + x3 + x4 + x5 + x6 + x7 = 5 (1b) Paling sedikit terdapat empat pemain penyerang (guard). x1 + x3 + x5 + x7  4 (1c) Paling sedikit terdapat dua pemain depan (forward). x3 + x4 + x5 + x6 + x7  2 (1d) Paling sedikit terdapat satu pemain tengah. x2 + x4 + x6  1

Solusi : Pemilihan pemain bola basket (2) 2. Rata-Rata tingkat ketrampilan pemain paling sedikit 2

(a) Rata-rata ketrampilan pemain menggiring bola lebih dari dua. (3 x1 + x2 + x3 + x4 + 2 x5 + x6 + x7)/5  2 3 x1 + x2 + x3 + x4 + 2 x5 + x6 + x7  10 (b) Rata-rata ketrampilan pemain menembak bola lebih dari dua. x1 + 2 x2 +3 x3 + 2 x4 + x5 + 3 x6 + 2 x7  10 (c) Rata-rata ketrampilan pemain menghadang lebih dari dua. 2 x1 + x2 + x3 + x4 + 3 x5 + x6 + 2 x7  10 3. Salah satu dari pemain ke-2 atau pemain ke-3 harus bermain

x2 + x3  1

Variabel kemungkinan yang terjadi: x2 = 1 & x3 = 0 Feasible x2 = 0 & x3 = 1 Feasible x2 = 1 & x3 = 1 Feasible x2 = 0 & x3 = 0 Infeasible

Solusi : Pemilihan pemain bola basket (3) 4. Jika pemain ke-3 bermain, maka pemain ke-6 tidak bisa bermain x3 + x6  1 Variabel kemungkinan yang terjadi:  Pemain 3 bermain, tetapi pemain 6 tidak bermain. x3 = 1, x6 = 0 Feasible  Pemain 6 bermain, tetapi pemain 3 tidak bermain. x3 = 0, x6 = 1 Feasible  Kedua-duanya bermain x3 = 1, x6 = 1 Infeasible  Kedua-duanya tidak dapat bermain. x3 = 0, x6 = 0 Feasible

Solusi : Pemilihan pemain bola basket (4) 5.

Jika pemain ke-1 bermain, maka pemain ke-4 dan ke-5 harus bermain juga x1  x4 x1  x5 Jika x1 = 1, maka x4 = 1 dan x5 =1. Variabel kemungkinan yang terjadi: x1 1 0 0 0 0

x4 1 0 1 0 1

x5 1 0 0 1 1

Interpretasi ketiga pemain bermain (feasibel). ketiga pemain tidak bermain (feasibel). hanya pemain 4 yang bermain (feasibel). hanya pemain 5 yang bermain (feasibel). pemain 4 dan 5 bermain, sedangkan pemain 1 tidak (feasibel)

Contoh 3 : Pengeboran Minyak 1. Pemilihan paling sedikit 5 lokasi dari 10 lokasi pengeboran

minyak yang telah direncanakan, dengan variabel keputusan X1, X2,…, X10 dan biaya pengeboran C1, C2,…, dan C10. 2. Batasan:  Paling banyak dua dari lokasi X5, X6, X7 dan X8 yang dapat dipilih  Memilih lokasi X3 atau lokasi X4 akan mencegah untuk memilih lokasi X5.  Memilih kombinasi lokasi X1 dan X7 akan mencegah untuk memilih lokasi X8.

Solusi Pengeboran Minyak (1) Variabel Keputusan Xi = 1, jika lokasi ke-i dilakukan pengeboran. = 0, jika lokasi ke-i tidak dilakukan pengeboran. Fungsi tujuan: Min C1 x1 + C2 x2 + C3 x3 + C4 x4 +C5 x5 + C6 x6 + C7 x7 + C8 x8 + C9 x9 + C10 x10 Subject to (1) Pemilihan paling sedikit 5 lokasi dari 10 lokasi pengeboran x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 = 5 (2) Paling banyak dua dari lokasi X5, X6, X7 dan X8 yang dapat dipilih x5 + x6 + x7 + x8  2

Solusi Pengeboran Minyak (2) (3) Memilih lokasi X3 atau lokasi X4 akan mencegah untuk memilih lokasi X5 x3 + x5  1 x4 + x5  1 

x3=1 atau x4=1, maka harus x5=0 (jika memilih lokasi X3 atau lokasi X4, lokasi X5 tidak boleh dipilih)  x5=1, maka nilai x3=0 dan x4=0 (jika memilih lokasi X5, maka lokasi X3 dan lokasi X4 tidak boleh dipilih)

Solusi Pengeboran Minyak (3) (4) Memilih kombinasi lokasi X1 dan X7 akan mencegah untuk memilih lokasi X8 x1 + x7 + x8  2 

kasus 1: tidak memilih lokasi X8 x8 = 0, maka x1 + x7  2 (dapat memilih lokasi S1, S7, atau kedua-duanya, atau tidak keduanya).

x8 x1 x7 Interpretasi 0 0 0 Tidak memilih ketiga lokasi tersebut 0 0 1 Hanya memilih lokasi S7 0 1 0 Hanya memilih lokasi S1 0 1 1 Memilih lokasi S1 dan S7, tetapi lokasi S8 tidak

Solusi Pengeboran Minyak (4) (4) Memilih kombinasi lokasi X1 dan X7 akan mencegah

untuk memilih lokasi X8 x1 + x7 + x8  2 

kasus 2: Menyelidiki lokasi S8 x8 = 1, maka x1 + x7  1 (dapat memilih lokasi x1atau x7, tetapi tidak kedua-duanya) x8 1 1 1 1

x1 0 1 0 1

x7 0 0 1 1

Interpretasi Hanya memilih lokasi S8 Memilih lokasi S8 dan S1, tetapi S7 tidak Memilih lokasi S8 dan S7, tetapi S1 tidak Memilih ketiga lokasi (infeasible)

Contoh 4: Problem “GANDHI”  Perusahaan pakaian Gandhi memproduksi 3 jenis pakaian :

kemeja, celana pendek, dan celana panjang.  Mesin harus di sewa tiap minggu untuk memproduksi ketiga jenis pakaian tersebut dengan biaya sewa :  $ 200 per minggu untuk mesin pembuat kemeja  $ 150 per minggu untuk mesin pembuat celana pendek  $ 100 per minggu untuk mesin pembuat celana panjang  Terdapat 150 jam waktu pekerja dan 160 m² bahan pakaian (kain) yang tersedia per minggunya, dengan data produksi sebagai berikut:

kemeja celana pendek celana panjang

Jam kerja yang Kain yang dibutuhkan dibutuhkan 3 4 2 3 6 4

Biaya variabel $12 $8 $15

Keuntungan per unit $6 $4 $8

Formulasikan permasalahan diatas untuk memaksimumkan keuntungan per minggunya!

Solusi Problem Gandhi Variabel keputusan: xi = jumlah pakaian jenis ke-i yang diproduksi per minggunya yi = 1 jika pakaian jenis ke-i diproduksi, dan 0 jika tidak

Formulasi: Max. z = 6x1 + 4x2 + 7x3 – 200 y1 - 150 y2 - 100y3 subject to 3x1 + 2x2 + 6x3  150 4x1 + 3x2 + 4x3  160 x1  M y1, x2  M y2, x3  M y3 x1, x2, x3  0, dan integer y1, y2, y3  0, dan biner

x1 y1

Contoh 5 : Problem “Western”  Penerbangan Western memutuskan untuk memiliki beberapa kota

transit di USA  Jalur penerbangan yang dimiliki mencakup kota-kota berikut : Atlanta, Boston, Chicago, denver, Houston, Los angeles, New Orleans, New York, Pittsburgh, Salt Lake city, San Francisco, dan Seattle  Western menginginkan untuk mempunyai kota transit dalam 1000 mil dari tiap kota-kota ini  Hitunglah jumlah minimum dari kota transit Atlanta (AT) Boston (BO) Chicago (CH) Denver (DE) Houston (HO) Los Angeles (LA) New Orleans (NO) New York (NY) Pittsburgh (PI) Salt Lake City (SL) San Francisco (SF) Seattle (SE)

Kota dalam 1000 miles AT, CH, HO, NO, NY, PI BO, NY, PI AT, CH, NY, NO, PI DE, SL AT, HO, NO LA, SL, SF AT, CH, HO, NO AT, BO, CH, NY, PI AT, BO, CH, NY, PI DE, LA, SL, SF, SE LA, SL, SF, SE SL, SF, SE

Solusi : Problem “Western” Variabel keputusan  Xi = 1 jika kota i dilokasikan sebagai kota transit  Xi = 0 jika kota i tidak dijadikan sebagai kota transit Minimize XAT + XB0 + XCH + XDE + XHO + XLA + XNO + XNY + XPI + XSL + XSF + XSE Pembatas: AT BO CH DE HO LA NO NY PI SL SF SE

AT BO CH DE HO LA NO NY 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0

PI SL SF SE 1 0 0 0 xAT 1 0 0 0 xBO 1 0 0 0 xCH 0 1 0 0 xDE 0 0 0 0 xHO 0 1 1 0 xLA 0 0 0 0 xNO 1 0 0 0 xNY 1 0 0 0 xPI 0 1 1 1 xSL 0 1 1 1 xSF 0 1 1 1 xSE

Required >= 1 >= 1 >= 1 >= 1 >= 1 >= 1 >= 1 >= 1 >= 1 >= 1 >= 1 >= 1

Contoh 6 : Problem “Alada”  Propinsi Alada mempunyai 6 kota  Propinsi ini memiliki permasalahan pada kota mana akan dibangun

stasiun pemadam kebakaran  Paling sedikit jarak stasiun pemadam kebakaran 15 menit (waktu tempuh) untuk masing – masing kota  Waktu yang dibutuhkan dari kota yang satu ke kota yang lain dilampirkan pada tabel dibawah ini.  Tentukan jumlah minimum dari pemadam kebakaran Kota ke-

1

2

3

4

5

6

1

0

10

20

30

30

20

2

10

0

25

35

20

10

3

20

25

0

15

30

20

4

30

35

15

0

15

25

5

30

20

30

15

0

14

6

20

10

20

25

14

0

Solusi : Problem “Alada”  Sebuah kota dapat dicover oleh stasiun pemadam kebakaran jika

jarak tempuhnya sebesar 15 menit  Covering set untuk setiap kota Kota

Covering sets (15 menit)

1

1,2

2

1,2,6

3

3,4

4

3,4,5

5

4,5,6

6

2,5,6

Solusi : Problem “Alada” Variabel keputusan : xi = 1 jika dibangun stasiun pemadam kebakaran pada kota-i = 0 jika kota-i tidak dibangun stasiun pemadam

Fungsi tujuan : Minimum x1+x2+x3+x4+x5+x6 Fungsi pembatas: Kota 1

2

3

4

5

6

1

1

1

0

0

0

0

xi

<=

1

2

1

1

0

0

0

1

xi

<=

1

3

0

0

1

1

0

0

xi

<=

1

4

0

0

1

1

1

0

xi

<=

1

5

0

0

0

1

1

1

xi

<=

1

6

0

1

0

0

1

1

xi

<=

1

xi = 0 or 1

Konsep : “Either-Or Constraints”  Ada 2 konstrain

f ( x1, x 2,..., xn)  0 g ( x1, x 2,..., xn)  0 diasumsikan bahwa hanya ada satu yang memenuhi  Kita dapat menyelesaikan permasalahan ini dengan menambahkan

metode “either-or constrains”

f ( x1, x 2,..., xn)  My g ( x1, x 2,..., xn)  M (1  y ) y = 0,1  M adalah besarnya nilai yang dapat menjamin bahwa kedua

konstrain dapat memenuhi nilai dari x1,x2,…,xn yang dapat memenuhi konstrain yang lain pada problem yang ada.

Konsep “If-then constraints”  Jika kita ingin memastikan bahwa,

f(x1 ,x2,… ,xn)>0 sama g(x1 ,x2 ,… ,xn)≥0  Kemudian kita tambahkan if-then konstrain

f ( x1, x 2,..., xn)  M (1  y)  g ( x1, x 2,..., xn)  My y = 0,1  Disini, M adalah nilai positif yang besar, pilih yang terbesar

sehingga f < M and – g < M mencakup semua nilai sehingga memenuhi konstrain lain yang ada pada permasalahan

Contoh 7 : “Either-Or Constraints” Memenuhi paling tidak satu dari pembatas berikut : (1) x + y ≤ 4 (2) 3x + 4y ≤15 (salah satu dari pembatas ke-1, atau ke-2, atau kedua-duanya) Feasibel solusinya adalah ; 1) x = 1, y = 3 (memenuhi kedua pembatas) 2) x = 0, y = 4 (memenuhi ke-1, tetapi tidak memenuhi ke-2) 3) x = 5, y = 0 (memenuhi ke-2, tetapi tidak memenuhi ke-1) 4) x = 2, y = 3 (tidak memenuhi kedua-duanya)

Solusi “Either-Or Constraints”  Definiskan variabel baru z sebagai variabel binary (biner)  Nilai M merupakan bilangan besar, konstan positif

Sehingga pembatas ke-1 atau ke-2, dimodifikasi menjadi

(3) x + y ≤ 4 + M z (4) 3 x + 4 y ≤ 15 + M (1 - z) (5) z bilangan biner Pembuktian: 1. Untuk mendapat solusi x = 5 dan y = 0, maka z dibuat = 1 : 5 + 0 = 5 < 4 + M, pembatas ke-3 memenuhi 15 + 0 = 15 + M (1 – 1) = 15, pembatas ke-4 memenuhi 2. Untuk mendapat solusi x = 0 dan y = 4, maka z dibuat = 0: 0 + 4 = 4 = 4 + M (0) = 4, pembatas ke-3 memenuhi 0 + (4) (4) = 16 ≤ 15 + M (1 – z) = 15 + M, pembatas ke-4 memenuhi

Solusi “Either-Or Constraints” 3. Solusi dengan nilai M dibuat = 1000 : Solusi 1a 1b 2a 2b 3a 3c 4a 4b

x 1 1 0 0 5 5 2 2

y x + y 3x + 4y 3 4 15 3 4 15 4 4 16 4 4 16 0 5 15 0 5 15 3 5 18 3 5 18

OK? Ya Ya Ya Ya Ya Ya Tidak Tidak

z 0 1 0 1 0 1 0 1

4+Mz 15 + M(1-z) Feasible 4 1015 Ya 1004 15 Ya 4 1015 Ya 1004 15 Tidak 4 1015 Tidak 1004 15 Ya 4 1015 Tidak 1004 15 Tidak

Kesimpulan:  Jika solusi yang memenuhi pembatas (1), (2), atau keduanya, dapat ditemukan nilai yang tepat untuk z sehingga pembatas (3) dan (4) juga memenuhi  Solusi yang tidak memenuhi pembatas (1) dan (2), maka pembatas (3), (4), atau keduanya juga tidak akan terpenuhi, berapapun nilai z

Contoh 8: Aplikasi “Dorian”  Perusahaan Dorian automotif memproduksi 3 tipe model mobil

yaitu ; compact (kecil), midsize (menengah), dan large (besar).  Ada 6 ton baja dan 60,000 jam kerja tersedia  Jika suatu tipe mobil diproduksi, maka mobil itu harus diproduksi paling sedikit 1,000 unit mobil  Data produksi seperti terlihat di tabel bawah ini: Kebutuhan baja Kebutuhan jam tenaga kerja Profit

Compact 1.5 ton 30 jam $2000

Midsize 3 ton 25 jam $3000

Large 5 ton 40 jam $4000

 Formulasikan permasalahan perencanaan produksi tersebut untuk

memaksimumkan profit.

Solusi aplikasi “Dorian” Variabel keputusan  xi = jumlah mobil tipe ke-i yang diproduksi  yi = 1 jika mobil tipe ke-i diproduksi, dan yi=0 jika tidak

Formulasi : Maks z = 2 x1 + 3 x2 + 4 x3 Subject to: x1 ≤ M y1 x2 ≤ M y2 x3 ≤ M y3 1000 – x1 ≤ M (1 – y1) 1000 – x2 ≤ M (1 – y2) 1000 – x3 ≤ M (1 – y3) 1.5 x1 + 3 x2 + 5 x3 ≤ 6000 30 x1 + 25 x2 + 40 x3 ≤ 60000 x1, x2, x3 ≥ 0 dan integer y1, y2, y3 = 0 atau 1

Metode “Percabangan dan Pembatasan” (Branch and Bound)

Metode “Branch and Bound”  Metode “Branch and Bound” adalah metode paling populer

untuk menyelesaikan problem IP  Metode ini mencari solusi optimal IP dengan perhitungan

titik-titik di daerah feasibel “sub-problem”.  Jika solusi optimal dari LP relaxation adalah integer, maka

solusi LP relaxation tersebut juga merupakan solusi IP

Contoh  Contoh suatu permasalahan IP:

Maximize z = 8x1 + 5x2 subject to x1 + x2  6; 9x1 + 5x2  45; x1, x2 ≥ 0; x1, x2 integer  Permasalahan di atas dimulai

dengan membagi menjadi beberapa sub-problem. Sub-problem 1 adalah penyelesaian LP relaxation dari model awal. Optimal LP Solution: x1 = 3.75 dan x2= 2.25 dengan z = 41.25

Feasible Region for Telfa’s Problem Subproblem 1 : The LP relaxation of original Optimal LP Solution: x1 = 3.75 and x2 = 2.25 and z = 41.25 Subproblem 2: Subproblem 1 + Constraint x1  4 Subproblem 3: Subproblem 1 + Constraint x1  3 Subproblem 4: Subproblem 2 + Constraint x2  2 Subproblem 5: Subproblem 2 + Constraint x2  1

Feasible Region for Telfa Problem

Daerah Feasible untuk Sub-problem Percabangan (Branching): Proses membagi suatu sub-problem menjadi dua atau lebih sub-problem dibawahnya

Sub-problem 1 dibagi 2:  Subproblem 2: Subproblem 1 + Constraint x1  4 (nilai x1 dibulatkan ke atas)  Subproblem 3: Subproblem 1 +

Constraint x1  3 (nilai x1 dibulatkan ke bawah)

Solusi Optimal Sub-problem 2: z = 41, x1 = 4, x2 = 9/5 = 1.8  Solusi optimal sub-problem 2

belum menghasilkan bilangan integer, dan perlu dicabangkan lagi (konsep LIFO sub-problem 3 tidak diproses dahulu) Feasible Region for Subproblems 2 and 3 of Telfa Problem

Feasible Region for Subproblems 4 & 5 Sub-problem 2 dibagi 2:  Subproblem 4: Subproblem 2 + Constraint x1 ³ 4 (nilai x1 dibulatkan ke atas)  Subproblem 5: Subproblem 2 +

Constraint x1 £ 3  (nilai x1 dibulatkan ke bawah) 

Solusi Optimal Sub-problem 2: z = 41, x1 = 4, x2 = 9/5 = 1.8

 Solusi optimal sub-problem 2

belum  menghasilkan bilangan integer, dan  perlu dicabangkan lagi (konsep LIFO  sub-problem 3 tidak diproses dahulu) Feasible Region for Subproblems 4 and 5 of Telfa Problem

The Branch and Bound Tree

3

Optimal solution of Subproblem 5: z = 40.05,

x1 = 4.44,

x2 = 1

Subproblem 6: Subproblem 5 + Constraint x1  5

Subproblem 5: Subproblem 5 + Constraint x1  4

Feasible Region for Subproblems 6 & 7

Optimal solution of Subproblem 7: z = 37,

x1 = 4,

x2 = 1

Optimal solution of Subproblem 6: z = 40,

x1 = 5,

x2 = 0

Feasible Region for Subproblems 6 and 7 of Telfa Problem

The Branch and Bound Tree

Solving Knapsack Problems Max z = 16x1+ 22x2 + 12x3 + 8x4 subject to 5x1+ 7x2 + 4x3 + 3x4  14 xi = 0 or 1 for all i = 1, 2, 3, 4 LP Relaxation: Max z = 16x1+ 22x2 + 12x3 + 8x4 subject to

5x1+ 7x2 + 4x3 + 3x4  14 0  xi  1 for all i = 1, 2, 3, 4 Soving the LP Relaxation:  Order xi’s in the decreasing order of ci/ai where ci are the cost coefficients and ai’s are the coefficients in the constraint  Select items in this order until the constraint is satisfied with equality

The Branch and Bound Tree Subproblem 1 z = 44 x1 = x2 = 1 x3 =.5

1

x3 = 1

x3 = 0

7

x4 = 0

8

Subproblem 3 z = 43.7 2 x1 =x3= 1, x2 = .7, x4=0

Subproblem 2 z = 43.3, LB=42 x1 = x2=1 x3 = 0, x4 =.67

Subproblem 8 z = 38, LB=42 x1 = x2=1 x3 = x 4 = 0

x2 = 1

x2 = 0

x4 = 1 Subproblem 9 z= 42.85, LB=42 x1 = x4 =1 9 x3 = 0, x2 = .85

3 Subproblem 4 z = 36 x1 = x3=1 x2 = 0, x4 =1 x1 = 0

5

Subproblem 6 z = 42 x1 =0, x2=x3=1 x4 = 1, LB = 36

4 Subproblem 5 z = 43.6 x1 =.6, x2=x3=1 x4 = 0, LB = 36 x1 = 1

Subproblem 7 LB = 42 6 Infeasible

Strategies of Branch and Bound The branch and bound algorithm is a divide and conquer algorithm, where a problem is divided into smaller and smaller subproblems. Each subproblem is solved separately, and the best solution is taken.

Lower Bound (LB): Objective function value of the best solution found so far.

Branching Strategy : The process of decomposing a subproblem into two or more subproblems is called branching.

Strategies of Branch and Bound (contd.) Upper Bounding Strategy: The process of obtaining an upper bound (UB) for each subproblem is called an upper bounding strategy. Pruning Strategy: If for a subproblem, UB  LB, then the subproblem need not be explored further.

Searching Strategy: The order in which subproblems are examined. Popular search strategies: LIFO and FIFO.

Menyelesaikan Integer Programming dengan LINDO/LINGO

LINDO : Problem Gandhi  Definisi variabel diletakkan setelah perintah “END”  Definisi variabel 0-1 atau biner di LINDO

INTE x  Definisi variabel Integer di LINDO GIN y  Contoh GANDHI di LINDO:

LINDO : Problem Gandhi  Solusi

GANDHI di LINDO:

Metode Branch and Bound

1

PEMROGRAMAN LINEAR BULAT (Integer Linear Programming - ILP) Apa yang dimaksud dengan Pemrograman Bulat ?

METODE SIMPLEKS

Solusi yang didapat optimal, tetapi mungkin tidak integer.

2

Integer Linear Programming

Misalnya saja kita ingin menentukan solusi optimal dari satu lini perakitan televisi, yang memproduksi beberapa tipe televisi.

Mengganggu batasan

Pembulatan matematis ?

ILP 3

Integer Linear Programming



 

Jika model mengharapkan semua variabel basis bernilai integer (bulat positif atau nol), dinamakan pure integer programming. Jika model hanya mengharapkan variabel-variabel tertentu bernilai integer, dinamakan mixed integer programming. Jika model hanya mengharapkan nilai nol atau satu untuk variabelnya, dinamakan zero one integer programming.

4

SOLUSI INTEGER PROGRAMMING PENDEKATAN PEMBULATAN 





Pendekatan ini mudah dan praktis dalam hal usaha, waktu dan biaya. Pendekatan pembulatan dapat merupakan cara yang sangat efektif untuk masalah integer programming yang besar dimana biaya-biaya hitungan sangat tinggi atau untuk masalah nilai-nilai solusi variabel keputusan sangat besar. Contohnya, pembulatan nilai solusi jumlah pensil yang harus diproduksi dari 14.250,2 menjadi 14.250,0 semestinya dapat diterima. Sebab utama kegagalan pendekatan ini adalah bahwa solusi yang diperoleh mungkin bukan solusi integer optimum yang sesungguhnya. Solusi pembulatan dapat lebih jelek dibanding solusi integer optimum yang sesungguhnya atau mungkin merupakan solusi tak layak.

5

PENDEKATAN PEMBULATAN

Maksimumkan

Z =

Dengan syarat

Minimumkan

10 X1 + 5 X1 + X1 ;

Z =

Dengan syarat

Maksimumkan Dengan syarat

100 X1 +

200 X1 + 10 X1 + 3 X1 + X1 ;

Z =

80 X1 + 4 X1 + X1 + X1 ;

90 X2 7 X2 ≤ 10 X2 ≤ X2 ≥

70 50 0

Masalah 1

100 12 0

Masalah 2

12 15 0

Masalah 3

400 X2 25 X2 ≥ 2 X2 ≥ X2 ≥

100 X2 2 X2 ≤ 5 X2 ≤ X2 ≥

6

Perbandingan antara solusi dengan metode simpleks tanpa pembatasan bilangan bulat, pembulatan ke bilangan bulat terdekat dan solusi integer optimum yang sesungguhnya untuk ketiga masalah diatas adalah :

Masalah

Solusi dengan Metode simpleks

Dgn pembulatan terdekat

Bulat optimum sesungguhnya

1

X1 = 5,38 X2 = 2,31 Z = 746,15

X1 = 5 X2 = 2 Z = 680

X1 = 7 X2 = 0 Z = 700

2

X1 = 1,82 X2 = 3,27 Z = 1.672,73

X1 = 2 X2 = 3 tak layak Z

X1 = 3, X2 = 3 X1 = 5, X2 = 2 Z = 1.800

3

X1 = 2,14 X2 = 1,71 Z = 343

X1 = 2 X2 = 2 tak layak Z

X1 = 0 X2 = 3 Z = 300

7

PENDEKATAN GRAFIK Pendekatan ini identik dengan metode grafik LP dalam semua aspek, kecuali bahwa solusi optimum harus memenuhi persyaratan bilangan bulat. Maksimumkan Dengan syarat

Z =

100 X1 + 10 X1 + 5 X1 + X1 ;

90 X2 7 X2 ≤ 70 10 X2 ≤ 50 X2 non negatif integer

8

PENDEKATAN GRAFIK



Model ini serupa dengan model LP biasa. Perbedaanya hanya pada kendala terakhir yang mengharapkan bahwa variabel terjadi pada nilai non negatif integer.



Solusi grafik masalah ini ditunjukkan pada gambar dibawah ini. Ruang solusi layak adalah OABC. Solusi optimum masalah LP ditunjukkan pada titik B, dengan X1 = 5,38 dan X2 = 2,31 serta Z = 746,15. Untuk mencari solusi integer optimum masalah ini, garis Z (slope = -9/10) digeser secara sejajar dari titik B menuju titik asal.



Solusi integer optimum adalah titik integer pertama yang bersinggungan dengan garis Z. Titik itu adalah A, dengan X1 = 7 dan X2 = 0 serta Z = 700.

9

PENDEKATAN GRAFIK

X2 10 10X1 + 7X2 = 70 Z = 746,15

5

C

Z = 700

B 5X1 + 10X2 = 50 O

A 7

10

X1 10

PENDEKATAN GOMORY (CUTTING PLANE ALGORITHM)

Langkah-langkah prosedur Gomory diringkas seperti berikut : 1.

2.

3.

Selesaikan masalah integer programming dengan menggunakan metode simpleks. Jika masalah sederhana, ia dapat diselesaikan dengan pendekatan grafik, sehingga pendekatan Gomory kurang efisien. Periksa solusi optimum. Jika semua variabel basis memiliki nilai integer, solusi optimum integer telah diperoleh dan proses solusi telah berakhir. Jika satu atau lebih variabel basis masih memiliki nilai pecah, teruskan ke tahap 3. Buatlah suatu skala Gomory (suatu bidang pemotong atau cutting plane) dan cari solusi optimum melalui prosedur dual simpleks. Kembali ke tahap 2.

11

KENDALA GOMORY DALAM PURE INTEGER PROGRAMMING

Tabel optimum masalah LP dibawah ini merupakan tabel solusi optimum kontinyu. Basis

X1

Xm

W1

Wn

Solusi

Z

0.....

0

c1. . . . .

cn

b0

X1 . . . Xm

1..... . . . 0

0 . . . 1

a11. . . . . . . . am1

a1n . . . amn

b1 . . . b1

12


 

Variabel Xi (i =1,…, m) menunjukkan variabel basis. Variabel Xj (j = 1,..., n) adalah variabel non basis.

Perhatikan persamaan ke i dimana variabel Xi diasumsikan bernilai non integer. Xi = bi – Σ aij Wj , dimana b non integer

Kemudian pisahkan bi dan aij menjadi bagian yang bulat dan bagian pecah non negatif seperti berikut : bi = bi + f i jadi f i = bi - bi , dimana 0 ≤ f i ≤ 1 aij = aij + f i jadi f i = aij - aij , dimana 0 ≤ f ij ≤ 1

13


  

bi

bi

fi

aij

aij

f ij

3/2 7/8 7/3

1 0 2

½ 7/8 1/3

7/3 -1 - 2/5

-3 -1 -1

2/3 0 3/5

Kendala Gomory yang diinginkan adalah : Sg - f ij Wj = - f i , Sg adalah variabel slack Gomory ke g. Pada umumnya, persamaan kendala yang berhubungan dengan solusi pecah dipilih untuk menghasilkan suatu kendala Gomory. Namun, sebagai aturan main biasanya dipilih persamaan yang memiliki fi, maksimum. 14

Tabel baru setelah penambahan kendala Gomory menjadi :

X1

Xm

W1

Wn

Sg

Z

0.....

0

c1. . . . .

cn

0

b0

X1 . . . Xm

1..... . . . 0

0 . . . 1

a11. . . . . . . . am1

a1n . . . amn

. . . . amn

b1 . . . b1

Sg

0.....

0

- fi1

- fin

1

- fi

Basis

Solusi

15




Jika diperoleh solusi primal optimum tetapi tidak layak maka digunakan metode dual simpleks.



Proses pembentukan kendala Gomory berakhir jika solusi baru semua berupa bilangan bulat.



Jika tidak, suatu kendala Gomory baru dibuat lagi dari tabel yang dihasilkan dan metode dual simpleks digunakan lagi untuk mengatasi ketidak layakan.



Jika pada setiap iterasi metode dual simpleks menunjukkan bahwa tidak ada solusi layak, berarti masalah itu tidak memiliki solusi integer yang layak.

16


Maksimumkan

Z =

Dengan syarat

7 X1 +

9 X2

- X1 + 7 X1 + X1 ;

3 X2 ≤ 6 X2 ≤ 35 X2 non negatif integer

Solusi kontinyu optimumnya diperoleh dalam tabel berikut :

Basis

X1

X2

S1

S2

Solusi

Z

0

0

28/11

15/11

63

X2 X1

0 1

1 0

7/22 - 1/22

1/22 3/22

7/2 9/2

17




Karena solusi tidak bulat, suatu kendala Gomory ditambahkan pada tabel itu. Kedua persamaan (X1 dan X2) pada masalah ini memiliki nilai f i yang sama, yaitu f 1 = f 2 = ½ , sehingga salah satu dapat digunakan, misalkan digunakan persamaan X2 , ini menghasilkan :  



X2 + 7/22 S1 + 1/22 S2 = 7/2 atau X2 + (0 + 7/22) S1 + (0 + 1/22) S2 = (3 + ½)

Sehingga kendala Gomorynya adalah : 

Sg1 - 7/22 S1 – 1/22 S2 = - ½

18


Tabel baru setelah penambahan kendala Gomory menjadi : Basis

X1

X2

S1

S2

Sg1

Solusi

Z

0

0

28/11

15/11

0

63

X2 X1

0 1

1 0

7/22 - 1/22

1/22 3/22

0 0

7/2 9/2

Sg1

0

0

- 7/2

- 1/22

1

-½

Dengan memakai metode dual simpleks diperoleh tabel baru yaitu : Basis

X1

X2

S1

S2

Sg1

Solusi

Z

0

0

0

1

8

59

X2 X1 S1

0 1 0

1 0 0

0 0 1

0 1/7 1/7

1 - 1/7 - 22/7

3 32/7 11/7 19

KENDALA GOMORY DALAM PURE INTEGER PROGRAMMING 



Karena solusi baru masih pecah, suatu kendala Gomory bary ditambahkan. Karena persamaan X1 memiliki f 1 terbesar (f 1 = 4/7), maka X1 dituliskan dalam bentuk : X1 + (0 + 1/7) S2 + (0+ 6/7) Sg1 = (4 + 4/7), Menghasilkan kendala Gomory kedua : Sg2 – 1/7 S1 – 6/7 Sg1 = - 4/7, kemudian tambahkan pada tabel :

Basis

X1

X2

S1

S2

Sg1

Sg2

Solusi

Z

0

0

0

1

8

0

59

X2

0

1

0

0

1

0

3

X1

1

0

0

1/7

- 1/7

0

32/7

S1

0

0

1

1/7

- 22/7

0

11/7

Sg2

0

0

0

- 1/7

- 6/7

1

- 4/7 20


Dengan menggunakan dual simpleks diperoleh hasil : Yang menghasilkan solusi bulat optimum X1 = 4, X2 =3 dan Z = 55

 

Basis

X1

X2

S1

S2

Sg1

Sg2

Solusi

Z

0

0

0

0

2

7

55

X2

0

1

0

0

1

0

3

X1

1

0

0

0

-1

1

4

S1

0

0

1

0

-4

1

1

Sg2

0

0

0

1

6

-7

4

21

METODE BRANCH DAN BOUND Metode Branch dan Bound telah menjadi kode komputer standar untuk integer programming, dan penerapan- penerapan dalam praktek tampaknya menyarankan bahwa metode ini lebih efisien dibanding dengan pendekatan Gomory. Teknik ini dapat diterapkan baik untuk masalah pure programming maupun mixed integer programming.

22

Langkah-langkah metode Branch dan Bound untuk masalah maksimasi dapat dilakukan seperti berikut : 1.

Selesaikan LP dengan metode simpleks biasa

2.

Teliti solusi optimumnya. Jika variabel basis yang diharapkan bulat adalah bulat, solusi optimum bulat telah tercapai.

3.

Nilai solusi pecah yang layak dicabangkan ke dalam sub-sub masalah. Tujuannya adalah untuk menghilangkan solusi kontinyu yang tidak memenuhi persyaratan bulat dalam masalah itu.

4.

Untuk setiap sub-masalah, nilai solusi optimum kontinyu fungsi tujuan ditetapkan sebagai batas atas. Solusi bulat terbaik menjadi batas bawah (pada awalnya, ini adalah solusi kontinyu yang dibulatkan ke bawah). Sub-sub masalah yang memiliki batas atas kurang dari batas bawah yang ada, tidak diikut sertakan pada analisa selanjutnya. Suatu solusi bulat layak adalah sama baik atau lebih baik dari batas atas untuk setiap sub masalah yang dicari. Jika solusi yang demikian terjadi, suatu sub masalah dengan batas atas terbaik dipilih untuk dicabangkan. Kembali ke langkah 3.

23

METODE BRANCH DAN BOUND 

Untuk memperoleh gambaran yang lebih jelas tentang metode Branch dan Bound, perhatikan contoh masalah berikut : Maksimumkan Dengan syarat

Z =

3 X1 +

5 X2

2 X1 + X1

4 X2 ≤ 25 ≤ 8 2 X2 ≤ 10 X2 non negatif integer

X1 ; 

Solusi optimum kontinyu masalah ini adalah X1 = 8, X2 = 2,26 dan Z = 35,25.



Solusi ini menunjukkan batas atas awal.

24

METODE BRANCH DAN BOUND







Batas bawah adalah solusi yang dibulatkan ke bawah X1 = 8, X2 = 2 dan Z = 34. Dalam metode Branch dan Bound, masalah itu dibagi ke dalam dua bagian untuk mencari nilai solusi bulat yang mungkin bagi X1 dan X2. Variabel dengan nilai solusi pecah terbesar dipilih. Karena pada solusi ini hanya X2 yang memiliki bagian pecah, ia dipilih. Untuk menghilangkan bagian pecah dari nilai X2 = 2,25, dua kendala baru dibuat. Kendala-kendala ini mewakili dua bagian baru dari masalah itu. Dua nilai bulat terdekat terhadap 2,25 adalah 2 dan 3. Sehingga diperoleh dua masalah baru melalui dua kendala mutually exclusive, X2 ≤ 2 dan X2 ≥ 3, yang akan diuraikan berikut ini sebagai bagian A dan B. Kendala-kendala ini secara efektif menghilangkan semua nilai pecah yang mungkin bagi X2, antara 2 dan 3. Pengaruhnya mereka mengurangi ruang solusi layak sehingga angka solusi bulat yang dievaluasi pada masalah ini makin sedikit

25


Bagian A : Maksimumkan

Z =

Dengan syarat

3 X1 +

5 X2

2 X1 + X1

4 X2 ≤ ≤ 2 X2 ≤ X2 ≤ X2 ≥

X1 ;

25 8 10 (berlebih) 2 0

Bagian B : Maksimumkan Dengan syarat

Z =

3 X1 +

5 X2

2 X1 + X1

4 X2 ≤ ≤ 2 X2 ≤ X2 ≥ X2 ≥

X1 ;

25 8 10 3 0

26




Bagian A dan B diselesaikan tanpa pembatasan bilangan bulat dengan metode simpleks. Solusi simpleksnya adalah :  

Bagian A : X1 = 8, X2 = 2 dan Z = 34 Bagian B : X1 = 6,5, X2 = 3 dan Z = 34,5



Bagian A menghasilkan suatu solusi yang semuanya bulat. Untuk bagian A batas atas dan bawah adalah Z = 34. Solusi pecah bagian B membenarkan pencarian lebih lanjut karena menghasilkan nilai fungsi tujuan yang lebih besar dari batas atas bagian A. Sangat mungkin bahwa pencarian lebih lanjut dapat menghasilkan suatu solusi yang semuanya bulat dengan nilai fungsi tujuan melebihi batas atas bagian A = 34.



Bagian B dicabangkan ke dalam dua sub bagian, B1 dan B2, pertama dengan kendala X1 ≤ 6 dan yang lain dengan X2 ≥ 7.

27


Sub Bagian B1 : Maksimumkan

Z

Dengan syarat

=

3 X1 +

5 X2

2 X1 + X1

4 X2 ≤ ≤ 2 X2 ≤ X2 ≥ ≤ X2 ≥

X1 X1 ;

25 8 (berlebih) 10 3 6 0

Sub Bagian B2 : Maksimumkan Dengan syarat

Z =

3 X1 +

5 X2

2 X1 + X1

4 X2 ≤ ≤ 2 X2 ≤ X2 ≥ ≥ X2 ≥

X1 X1 ;

25 8 10 3 7 0 28




Solusi simpleksnya adalah : 





Sub-bagian B1 : X1 = 6, X2 = 3,25 dan Z = 34,25 Sub-bagian B2 : tidak layak.

Karena sub-bagian B1 menghasilkan nilai fungsi tujuan yang lebih besar dari 34 (batas atas bagian A), maka harus dicabangkan lagi ke dalam dua sub masalah, dengan kendala X2 ≤ 3 dan X2 ≥ 4. Kedua kendala sub masalah diberi nama bagian B1a dan B2b.

29


Bagian B1a : Maksimumkan

Z

=

Dengan syarat

3 X1

+

5 X2

2 X1 X1

+

4 X2 2 X2 X2 X2

X1 X1

;

X2

3 X1

+

5 X2

2 X1 X1

+

4 X2

≤ ≤ ≤ ≥ ≤ ≤ ≥

25 8 10 (berlebih) 3 3 6 0

≤ ≤ ≤ ≥ ≥ ≤ ≥

25 8 10 3 (berlebih) 4 6 0

Bagian B1b : Maksimumkan Dengan syarat

Z

=

2 X2 X2 X2 X1 X1

;

X2

30




Solusi optimum dengan metode simpleks adalah :  

Sub-bagian B1a : X1 = 6, X2 = 3 dan Z = 33 Sub-bagian B1b : X1 = 4,25, X2 = 4 dan Z = 33,5



Kedua solusi itu memiliki batas atas ( Z = 33 dan Z = 33,5) yang lebih buruk dibanding dengan solusi yang dihasilkan oleh bagian A. Karena itu, solusi bulat optimum adalah X1 = 8, X2 = 2 dan Z = 34 yang dihasilkan oleh bagian A.



Jika pencarian telah diselesaikan, solusi bulat dengan fungsi tujuan tertinggi (dalam masalah maksimasi) dipilih sebagai solusi optimum.

31




Kelemahan dasar dari metode ini adalah bahwa diperlukan pemecahan masalah LP untuk setiap pencabangan. Dalam masalah yang besar dapat memakan banyak waktu. Karena itu dalam prosedur pencabangan dan pencarian, analisa selanjutnya dihentikan jika : 1.

Hasil dari sub-problem lebih jelek dibanding dengan batas atas yang sudah diidentifikasi

2.

Pencabangan selanjutnya menghasilkan solusi tak layak.

32


Seluruh prosedur Branch dan Bound untuk contoh yang lalu dapat digambarkan seperti berikut :

0

Solusi bulat optimum X1 = 8 X2 = 2 Z = 34 2 X1 = 6 X2 = 3,25 Z = 34,25

X1 = 8 X2 = 2,25 Z = 35,25

X1 = 6,5 X2 = 3 Z = 34,5

inferior

inferior

Tak layak 33

HAND OUT PENELITIAN OPERASIONAL I. Oleh : Tim Dosen Penelitian Operasional Program Studi Teknik Industri

Recommend Documents