hand out penelitian operasional i -...

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 hubungan-

hubungan 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. Linearity (proportionality)

2. Additivity

3. Divisibility

4. Certainty (deterministic)

5. 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 produk-

produk 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

• Model matematis

Maximize = 12 X1 + 8 X2

Subject to,

5 X1 + 2 X2 150 (kendala jati)

2 X1 + 3 X2 100 (kendala kamper)

4 X1 + 2 X2 80 (kendala HK)

dan X1, X2 0 (kendala non-negatif)

Sumberdaya Produk Ketersediaan

meja kursi

Jati 5 2 150

Kamper 2 3 100

HK 4 2 80

Profit 12.000 8.000

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

Subject to,

nn XcXcXcf ...2211

11212111 ... bXaXaXa nn

22222121 ... bXaXaXa nn

mnmnmm bXaXaXa ...2211

0,...,, 21 nXXX

...

Notasi LP

Optimize

subject to,

dimana,

n

j

jj Xcf1

m

i

n

j

ijij bXa1 1

atau cXf

atau bAX

ncccc ...21

mnmm

n

n

aaa

aaa

aaa

A

...

............

...

...

21

22221

11211

mb

b

b

b...

2

1

nX

X

X

X...

2

1

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

20 30 50

75

40

33.3

O

A

B

C

K. Jati

K. Kamper

HK

X1

X2

redundant

binding

binding

feasible region

isoprofit line

Solusi bersifat unik di titik B (5,30)

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


subject to 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


subject to 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. Mengenal linear programming sebagai alat pengambilan keputusan

2. Merumuskan permasalahan operasi ke dalam bentuk linear programming

3. Menyelesaikan permasalahan linear programming dengan grafik/ matematik

4. Memahami permasalahan infeasibility, unboundedness, alternative optima, dan redundancy.

Metode Grafik Masalah Maksimasi

FORMULASI PERMASALAHAN, langkah-langkah :

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

x2

x1

0

Jika x1 positif, x2 positif

Jika x1 negatif, x2 positif

Jika x1 negatif, x2 negatif

Jika x1 positif, x2 negatif

Ubah tanda Batasan /kendala dg =

1. 4x1 + 2x2 240 4x1 + 2x2 = 240

2. 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

x2

0 120

60

100

50 2x1 + x2 = 120

2x1 + 1x2 = 100

Gambarkan grafik dg memasukkan tanda

x1

x2

0 120

60

100

50 2x1 + x2 = 120

2x1 + 1x2 = 100

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

2

1

2

3

100

80

Minimum Kebutuhan

8 12

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 Keuntungan

(Rp) A B

1

2

2

1/2

1

3

750

500

Kapasitas 320 300 Jam per bulan

6s-1 Linear Programming

William J. Stevenson

Operations Management

8th edition

PENELITIAN

OPERASIONAL 1

DUALITAS

DALAM LINEAR PROGRAMING


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


Hubungan primal-dual

Primal Dual

Batasan i Variabel i

Fungsi Tujuan Nilai Kanan


Contoh :

Merek

Mesin

I1 I2 Kapasitas

Maksimum

1 2 0 8

2 0 3 15

3 6 5 30

Sumbangan laba 3 5

Merek

Mesin

X1 X2

Y1 2 0 ≤ 8

Y2 0 3 ≤ 15

Y3 6 5 ≤ 30

≥ 3 ≥ 5

Tabel primal-dual

(masalah primal)


Fungsi primal-dual Tujuan :

Maks Z = 3X1 + 5X2

Batasan :

2X1 8

3X2 15

6X1 + 5X2 30

dan

X1 ≥ 0, X2 ≥ 0

Tujuan :

Min Y = 8Y1 + 15Y2 + 30Y3

Batasan :

2Y1 + 6 Y3 ≥ 3

3Y2 + 5 Y3 ≥ 5

dan

Y1 ≥ 0, Y2 ≥ 0, Y3 ≥ 0

Merek

Mesin

X1 X2

Y1 2 0 ≤ 8

Y2 0 3 ≤ 15

Y3 6 5 ≤ 30

≥ 3 ≥ 5

Tabel primal-dual

Batasan i

Variabel i

Fungsi Tujuan

Nilai Kanan

Kunci 1

Kunci 2

6s-6 Linear Programming Interpretasi Ekonomis

Fungsi primal

n

j

jj XCZ1

Maks:Tujuan

n

j

ijij bXa1

Batasan

Dengan menggantikan Zj, metode simpleks dapat

diartikan mencari nilai Ym

Fungsi dual

m

i

iiYbY1

0Min :Tujuan

m

i

jiij CYa1

Batasan

Xj = Tingkat aktivitas ke j

Cj = Laba persatuan aktivitas j

Z = Laba total dari seluruh aktivitas

bi = Jumlah sumber i yang tersedia

aij = jumlah sumber i yang “dipakai” oleh setiap satuan

aktivitas j

Yi = kontribusi persatuan sumber i terhadap laba


Hasil masalah dual

Tujuan :

Min Y = 8Y1 + 15Y2 + 30Y3

Batasan :

2Y1 + 6 Y3 ≥ 3

3Y2 + 5 Y3 ≥ 5

dan

Y1 ≥ 0, Y2 ≥ 0, Y3 ≥ 0

Y1 = 0, Y2 = 5/6, Y3 = 1/2

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

Y = 271/2

Analisis Simplex

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 Frekuensi

Operations Research Penggunaan (%)

Statistical Analysis 29

Simulation 25

Linear programming 19

Inventory Theory 6

PERT/CPM 6

Dynamic Programming 4

Non Linear Programming 3

Queueing Theory 1

Heuristic Programming 1

Miscellaneous 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

Interpretasi Hasil Olahan

Optimal

Abstraksi Masalah ke

Model Model

Analisis

Penyelesaian Optimal

Masalah

Pembuatan Keputusan

Intuisi dan Pengalaman

Dunia Simbol Dunia Nyata

Pertimbangan-

Pertimbangan

Manajemen

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 1. 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.

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 Kapasitas

Pemrosesan: (jam) (jam)

Penghancuran 2 1 20 jam

Penghalusan 2 3 32 jam

Permintaan Rutin 2 ton

Contribution Margin

Rp 40,- Rp 30,-

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

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 : Kasus-kasus 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

Max 2X1 + 3X2

ST

X1 + 2X2 ≤ 16

3X1 + 2X2 ≤ 30

X1, X2 ≥ 0 dan integer

Penyelesaian Dharmika

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 :

1. 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

Goal Programming : Analisis Geometri

Geometri Bawika Optimal

Goal Programming

Tiga macam sasaran di dalam Goal Programming :

1. Sasaran-sasaran dengan prioritas yang sama

2. Sasaran-sasaran dengan prioritas yang berbeda

3. Sasaran-sasaran dengan prioritas dan bobot yang berbeda

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, kegiatan-kegiatan dalam satu pekerjaan masih terpisah


Perubahan Gantt Chart menuju jaringan (Network)


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

Permasalahan IP biasanya lebih sulit untuk diselesaikan dibandingkan dengan permasalahan LP

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

Integer Programming dan LP relaxation

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

x x x x

x1

x2

1 2 3

1

3

2

7x1 + 4x2= 13

1 2 3 4 5 6 7 8

x1

1

2

3

4

5

6

x2

1 2 3 4 5 6 7 8

x1

1

2

3

4

5

6

x2

LP Optimal

x1 = 5 7/16

x2 = 2 11/16

Contoh Problem: Max 1200 x1 + 2000 x2

ST:

2x1 + 6 x2 27

x2 2

3x1 + x2 19

x1 , x2 0 and Integer

Penyelesaian

problem Integer

Programming,

Apakah solusi LP

dibulatkan untuk

mendapakan solusi

IP…?

Solusi Integer Programming

1 2 3 4 5 6 7 8

x1

1

2

3

4

5

6

x2

1 2 3 4 5 6 7 8

x1

1

2

3

4

5

6

x2

LP Optimal

x1 = 5 7/16

x2 = 2 11/16

Pembulatan ke atas?

x1 = 6

x2 = 3

Pembulatan? x1 = 5

x2 = 3

Pembulatan

ke bawah?

x1 = 5

x2 = 2

Max 1200 x1 + 2000 x2

ST:

2x1 + 6 x2 27

x2 2

3x1 + x2 19

x1 , x2 0 and Integer

Solusi Integer Programming (2)

LP relaxation, kemudian dibulatkan ?

1 2 3 4 5 6 7 8

x1

1

2

3

4

5

6

x2

1 2 3 4 5 6 7 8

x1

1

2

3

4

5

6

x2 IP Optimal

x1 = 4

x2 = 3

Solusi Integer Programming (3)

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:

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

Pilihan Investasi 1 2 3 4

Modal $5000 $7000 $4000 $3000 NPV $16000 $22000 $12000 $8000

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 Forward Center Ball-Handling Shooting Rebounding Total

1 Yes No No 3 1 2 6

2 No No Yes 1 2 1 4

3 Yes Yes No 1 3 1 5

4 No Yes Yes 1 2 1 4


6 No Yes Yes 1 3 1 5


Posisi Kemampuan

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


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 = 0 Infeasible


4. Jika pemain ke-3 bermain, maka pemain ke-6 tidak bisa bermain

x3 + x6 1


Pemain 3 bermain, tetapi pemain 6 tidak bermain.

x3 = 1, x6 = 0 Feasible

Pemain 6 bermain, tetapi pemain 3 tidak bermain.


Kedua-duanya bermain

x3 = 1, x6 = 1 Infeasible

Kedua-duanya tidak dapat bermain.



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.


x1 x4 x5 Interpretasi

1 1 1 ketiga pemain bermain (feasibel).

0 0 0 ketiga pemain tidak bermain (feasibel).

0 1 0 hanya pemain 4 yang bermain (feasibel).

0 0 1 hanya pemain 5 yang bermain (feasibel).

0 1 1 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


(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)


(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).


0 0 0 Tidak memilih ketiga lokasi tersebut

0 0 1 Hanya memilih lokasi S7


0 1 1 Memilih lokasi S1 dan S7, tetapi lokasi S8 tidak


(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)



1 1 0 Memilih lokasi S8 dan S1, tetapi S7 tidak

1 0 1 Memilih lokasi S8 dan S7, tetapi S1 tidak

1 1 1 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:

Formulasikan permasalahan diatas untuk memaksimumkan

keuntungan per minggunya!

Jam kerja yang

dibutuhkan

Kain yang

dibutuhkan

Biaya

variabel

Keuntungan

per unit

kemeja 3 4 $12 $6

celana pendek 2 3 $8 $4

celana panjang 6 4 $15 $8

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, x1 y1

x2 M y2,

x3 M y3

x1, x2, x3 0, dan integer

y1, y2, y3 0, dan biner

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 Kota dalam 1000 miles Atlanta (AT) AT, CH, HO, NO, NY, PI

Boston (BO) BO, NY, PI Chicago (CH) AT, CH, NY, NO, PI

Denver (DE) DE, SL Houston (HO) AT, HO, NO

Los Angeles (LA) LA, SL, SF New Orleans (NO) AT, CH, HO, NO

New York (NY) AT, BO, CH, NY, PI Pittsburgh (PI) AT, BO, CH, NY, PI

Salt Lake City (SL) DE, LA, SL, SF, SE San Francisco (SF) LA, SL, SF, SE

Seattle (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 Required

AT 1 0 1 0 1 0 1 1 1 0 0 0 xAT >= 1

BO 0 1 0 0 0 0 0 1 1 0 0 0 xBO >= 1

CH 1 0 1 0 0 0 1 1 1 0 0 0 xCH >= 1

DE 0 0 0 1 0 0 0 0 0 1 0 0 xDE >= 1

HO 1 0 0 0 1 0 1 0 0 0 0 0 xHO >= 1

LA 0 0 0 0 0 1 0 0 0 1 1 0 xLA >= 1

NO 1 0 1 0 1 0 1 0 0 0 0 0 xNO >= 1

NY 1 1 1 0 0 0 0 1 1 0 0 0 xNY >= 1

PI 1 1 1 0 0 0 0 1 1 0 0 0 xPI >= 1

SL 0 0 0 1 0 1 0 0 0 1 1 1 xSL >= 1

SF 0 0 0 0 0 1 0 0 0 1 1 1 xSF >= 1

SE 0 0 0 0 0 0 0 0 0 1 1 1 xSE >= 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:

xi = 0 or 1

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

Konsep : “Either-Or Constraints”

Ada 2 konstrain

diasumsikan bahwa hanya ada satu yang memenuhi

Kita dapat menyelesaikan permasalahan ini dengan menambahkan

metode “either-or constrains”

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.

0),...,,(

0),...,,(

21

21

n

n

xxxg

xxxf

)1(),...,,(

),...,,(

21

21

yMxxxg

Myxxxf

n

n

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

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

Myxxxg

yMxxxf

n

n

),...,,(

)1(),...,,(

21

21

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 :

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

Solusi x y x + y 3x + 4y OK? z 4+Mz 15 + M(1-z) Feasible

1a 1 3 4 15 Ya 0 4 1015 Ya

1b 1 3 4 15 Ya 1 1004 15 Ya

2a 0 4 4 16 Ya 0 4 1015 Ya

2b 0 4 4 16 Ya 1 1004 15 Tidak

3a 5 0 5 15 Ya 0 4 1015 Tidak

3c 5 0 5 15 Ya 1 1004 15 Ya

4a 2 3 5 18 Tidak 0 4 1015 Tidak

4b 2 3 5 18 Tidak 1 1004 15 Tidak

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:

Formulasikan permasalahan perencanaan produksi tersebut untuk

memaksimumkan profit.

Compact Midsize Large

Kebutuhan baja 1.5 ton 3 ton 5 ton

Kebutuhan jam tenaga kerja 30 jam 25 jam 40 jam

Profit $2000 $3000 $4000

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


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


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


x3 = 0 x3 = 1

x2 = 0 x4 = 1

Subproblem 1

z = 44

x1 = x2 = 1

x3 =.5 1

7 2

8 9

Subproblem 5

z = 43.6

x1 =.6, x2=x3=1

x4 = 0, LB = 36

Subproblem 4

z = 36

x1 = x3=1

x2 = 0, x4 =1

Subproblem 3

z = 43.7

x1 =x3= 1,

x2 = .7, x4=0

Subproblem 6

z = 42

x1 =0, x2=x3=1

x4 = 1, LB = 36 5

Subproblem 7

LB = 42

Infeasible 6

x2 = 1

x1 = 0 x1 = 1

Subproblem 2

z = 43.3, LB=42

x1 = x2=1

x3 = 0, x4 =.67

Subproblem 8

z = 38, LB=42

x1 = x2=1

x3 = x4 = 0

Subproblem 9

z= 42.85, LB=42

x1 = x4 =1

x3 = 0, x2 = .85

x4 = 0

3 4

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:

1

Metode Branch and Bound

2

PEMROGRAMAN LINEAR BULAT (Integer Linear Programming - ILP)

Apa yang dimaksud dengan Pemrograman Bulat ?

Solusi yang didapat optimal,

tetapi mungkin tidak integer.

METODE SIMPLEKS

3

Integer Linear Programming

Misalnya saja kita ingin menentukan solusi

optimal dari satu lini perakitan televisi, yang

memproduksi beberapa tipe televisi.

Pembulatan matematis ? Mengganggu batasan

ILP

4

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.

Integer Linear Programming

5

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.

6

PENDEKATAN PEMBULATAN

Maksimumkan Z = 100 X1 + 90 X2

Dengan syarat 10 X1 + 7 X2 ≤ 70 5 X1 + 10 X2 ≤ 50 X1 ; X2 ≥ 0

Minimumkan Z = 200 X1 + 400 X2

Dengan syarat 10 X1 + 25 X2 ≥ 100 3 X1 + 2 X2 ≥ 12 X1 ; X2 ≥ 0


Dengan syarat 4 X1 + 2 X2 ≤ 12 X1 + 5 X2 ≤ 15 X1 ; X2 ≥ 0

Masalah 1

Masalah 2

Masalah 3

7

Masalah Solusi dengan

Metode simpleks Dgn pembulatan

terdekat Bulat optimum sesungguhnya

1 X1 = 5,38 X1 = 5 X1 = 7

X2 = 2,31 X2 = 2 X2 = 0

Z = 746,15 Z = 680 Z = 700

2 X1 = 1,82 X1 = 2 X1 = 3, X2 = 3

X2 = 3,27 X2 = 3 X1 = 5, X2 = 2

Z = 1.672,73 Z tak layak Z = 1.800

3 X1 = 2,14 X1 = 2 X1 = 0

X2 = 1,71 X2 = 2 X2 = 3

Z = 343 Z tak layak Z = 300

Perbandingan antara solusi dengan metode simpleks tanpa pemba-

tasan bilangan bulat, pembulatan ke bilangan bulat terdekat dan

solusi integer optimum yang sesungguhnya untuk ketiga masalah

diatas adalah :

8

PENDEKATAN GRAFIK

Pendekatan ini identik dengan metode grafik LP dalam

semua aspek, kecuali bahwa solusi optimum harus meme-

nuhi persyaratan bilangan bulat.


Dengan syarat 10 X1 + 7 X2 ≤ 70 5 X1 + 10 X2 ≤ 50 X1 ; X2 non negatif integer

9

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.

PENDEKATAN GRAFIK

10

A

B

C

O

5

10

X1 10 7

X2

Z = 700

Z = 746,15

5X1 + 10X2 = 50

10X1 + 7X2 = 70

PENDEKATAN GRAFIK

11

PENDEKATAN GOMORY (CUTTING PLANE ALGORITHM)

Langkah-langkah prosedur Gomory diringkas seperti berikut :

1. Selesaikan masalah integer programming dengan meng-gunakan metode simpleks. Jika masalah sederhana, ia dapat diselesaikan dengan pendekatan grafik, sehingga pendekatan Gomory kurang efisien.

2. Periksa solusi optimum. Jika semua variabel basis memi-liki 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.

3. Buatlah suatu skala Gomory (suatu bidang pemotong atau cutting plane) dan cari solusi optimum melalui prosedur dual simpleks. Kembali ke tahap 2.

12

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 1 . . . . . 0 a11. . . . . a1n b1

. . . . . .

. . . . . .

. . . . . .

Xm 0 1 am1 amn b1

13

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


14


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.

bi bi f i aij aij f ij

3/2 1 ½ 7/3 - 3 2/3

7/8 0 7/8 - 1 - 1 0

7/3 2 1/3 - 2/5 - 1 3/5

15

Tabel baru setelah penambahan kendala Gomory menjadi :

Basis X1 Xm W1 Wn Sg Solusi

Z 0 . . . . . 0 c1. . . . . cn 0 b0

X1 1 . . . . . 0 a11. . . . . a1n . b1

. . . . . . .

. . . . . . .

. . . . . . .

Xm 0 1 am1 amn amn b1

Sg 0 . . . . . 0 - fi1 - fin 1 - fi

16


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.

17


Solusi kontinyu optimumnya diperoleh dalam tabel berikut :


Dengan syarat - X1 + 3 X2 ≤ 6 7 X1 + X2 ≤ 35 X1 ; X2 non negatif integer

Basis X1 X2 S1 S2 Solusi

Z 0 0 28/11 15/11 63

X2 0 1 7/22 1/22 7/2

X1 1 0 - 1/22 3/22 9/2

18

Karena solusi tidak bulat, suatu kendala Gomory ditambah-kan 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 = - ½


19


Basis X1 X2 S1 S2 Sg1 Solusi

Z 0 0 28/11 15/11 0 63

X2 0 1 7/22 1/22 0 7/2

X1 1 0 - 1/22 3/22 0 9/2

Sg1 0 0 - 7/2 - 1/22 1 - ½

Tabel baru setelah penambahan kendala Gomory menjadi :

Dengan memakai metode dual simpleks diperoleh tabel baru yaitu :

Basis X1 X2 S1 S2 Sg1 Solusi

Z 0 0 0 1 8 59

X2 0 1 0 0 1 3

X1 1 0 0 1/7 - 1/7 32/7

S1 0 0 1 1/7 - 22/7 11/7

20


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

21

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


22

METODE BRANCH DAN BOUND

Metode Branch dan Bound telah menjadi kode komputer

standar untuk integer programming, dan penerapan- penerap-

an 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.

23

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.

Langkah-langkah metode Branch dan Bound untuk

masalah maksimasi dapat dilakukan seperti berikut :

24


Untuk memperoleh gambaran yang lebih jelas tentang

metode Branch dan Bound, perhatikan contoh masalah

berikut :


Dengan syarat 2 X1 + 4 X2 ≤ 25 X1 ≤ 8 2 X2 ≤ 10 X1 ; X2 non negatif integer

Solusi optimum kontinyu masalah ini adalah X1 = 8, X2 =

2,26 dan Z = 35,25.

Solusi ini menunjukkan batas atas awal.

25

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 se-bagai bagian A dan B. Kendala-kendala ini secara efektif menghi-langkan 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


26


Dengan syarat 2 X1 + 4 X2 ≤ 25 X1 ≤ 8 2 X2 ≤ 10 X2 ≤ 2 X1 ; X2 ≥ 0

(berlebih)


Dengan syarat 2 X1 + 4 X2 ≤ 25 X1 ≤ 8 2 X2 ≤ 10 X2 ≥ 3 X1 ; X2 ≥ 0

Bagian A :

Bagian B :


27

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.


28


Dengan syarat 2 X1 + 4 X2 ≤ 25 X1 ≤ 8 2 X2 ≤ 10 X2 ≥ 3 X1 ≤ 6 X1 ; X2 ≥ 0


Dengan syarat 2 X1 + 4 X2 ≤ 25 X1 ≤ 8 2 X2 ≤ 10 X2 ≥ 3 X1 ≥ 7 X1 ; X2 ≥ 0


Sub Bagian B1 :

Sub Bagian B2 :

(berlebih)

29

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 dica-bangkan lagi ke dalam dua sub masalah, dengan kendala X2 ≤ 3 dan X2 ≥ 4. Kedua kendala sub masalah diberi nama bagian B1a dan B2b.


30


Dengan syarat 2 X1 + 4 X2 ≤ 25 X1 ≤ 8 2 X2 ≤ 10 X2 ≥ 3 X2 ≥ 4 X1 ≤ 6 X1 ; X2 ≥ 0


Dengan syarat 2 X1 + 4 X2 ≤ 25 X1 ≤ 8 2 X2 ≤ 10 X2 ≥ 3 X2 ≤ 3 X1 ≤ 6 X1 ; X2 ≥ 0

Bagian B1a :

Bagian B1b :

(berlebih)

(berlebih)


31


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.

32

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.


33

X1 = 8

X2 = 2

Z = 34

0

Solusi bulat optimum

X1 = 8

X2 = 2,25

Z = 35,25

2

Tak layak

X1 = 6,5

X2 = 3

Z = 34,5

inferior

inferior

X1 = 6

X2 = 3,25

Z = 34,25


Seluruh prosedur Branch dan Bound untuk contoh yang lalu

dapat digambarkan seperti berikut :

hand out penelitian operasional i -...

Documents