operations research -...

Fakultas Teknik

Universitas Pasundan

Jurusan Teknik Industri

Tjutju T Dimyati

OPERATIONS RESEARCH – I

MODEL-MODEL DETERMINISTIK

Jurusan Teknik Industri FT Unpas

PEMROGRAMAN LINIER

Tjutju T. Dimyati

1. Konsep Pemodelan dalam Penelitian Operasional

2. Formulasi Model Pemrograman Linier

3. Konsep Primal-Dual

Jurusan Teknik Industri FT Unpas

Tujuan Pembelajaran

Menguasai perumusan model matematis untuk persoalan Pemrograman Linier

Tjutju T. Dimyati

Jurusan Teknik Industri FT Unpas

Capaian Pembelajaran

Di akhir perkuliahan mahasiswa:

• Dapat mendefinisikan persoalan LP

• Dapat merumuskan variabel dan parameter persoalan LP

• Mampu memformulasikan model persoalan LP

• Mampu memformulasikan bentuk dual dari formulasi persoalan LP

Tjutju T. Dimyati

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

PEMROGRAMAN LINIER (Linear Programming, LP)

LP adalah suatu alat untuk menyelesaikan persoalan optimasi yaitu persoalan yang berkaitan dengan penentuan rancangan dan pengoperasian terbaik dari suatu sistem dengan sumber yang terbatas

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Sumber Terbatas

• Waktu

• Dana

• Tenaga Kerja

• Minyak Bumi

• Sumber-sumber lain

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Karakteristik Persoalan Pemrograman Linier

• Keputusan (Decisions)

• Pembatas (Constraints)

• Tujuan (objective)

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

DEFINISI • Fungsi Tujuan

Merupakan fungsi linier dari variabel-variabel keputusan yang akan dimaksimumkan atau diminimumkan

• Fungsi Pembatas

Merupakan persamaan atau pertaksamaan linier, dan akan membatasi nilai dari seluruh variabel keputusan

• Pembatas Tanda

Menyatakan nilai dari setiap variabel keputusan

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

TERMINOLOGI

• Koefisien dari variabel keputusan pada fungsi tujuan disebut koefisien fungsi tujuan

• Koefisien dari variabel keputusan pada fungsi pembatas disebut koefisien teknologikal

• Nilai di ruas kanan dari setiap fungsi pembatas disebut ruas kanan

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

ASUMSI PERSOALAN LP

• Seluruh persamaan, baik fungsi tujuan maupun fungsi pembatas, merupakan fungsi linier. Asumsi ini dikenal sebagai asumsi Linieritas

• Seluruh koefisien berharga konstan

• Peningkatan output bersifat proporsional terhadap peningkatan input. Asumsi ini dikenal sebagai asumsi Proporsionalitas

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

ASUMSI PERSOALAN LP

• Total ongkos atau keuntungan (nilai fungsi tujuan) adalah jumlah dari ongkos atau keuntungan individual, sedangkan total kontribusi terhadap pembatas adalah jumlah kontribusi individual dari kegiatan individual. Asumsi ini dikenal sebagai asumsi Aditivitas

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

ASUMSI PERSOALAN LP

• Seluruh variabel keputusan dapat berupa bilangan bulat ataupun bilangan pecahan. Asumsi ini dikenal sebagai asumsi Divisibilitas

• Seluruh parameter model merupakan konstanta yang sudah diketahui. Asumsi ini dikenal sebagai asumsi Deterministik

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Bentuk Umum Persoalan LP

MAX (or MIN): c1X1 + c2X2 + … + cnXn

Subject to:

a11X1 + a12X2 + … + a1nXn <= b1

:

ak1X1 + ak2X2 + … + aknXn >=bk

:

am1X1 + am2X2 + … + amnXn = bm

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

FORMULASI PERSOALAN LINEAR PROGRAMMING

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Sebuah perusahaan memproduksi dua jenis produk, A dan B, yang masing-masing dapat memberikan keuntungan per unit sebesar $5 dan $14. Setiap unit produk A membutuhkan

1 m2 bahan fiber dengan 1 jam pengerjaan, sedang setiap unit produk B membutuhkan

2 m2 bahan fiber dengan 4 jam pengerjaan. Pada setiap hari kerja perusahaan itu hanya dapat membeli paling banyak 6 m2 bahan fiber dan bekerja selama 8 jam. Bagaimanakah formulasi LP untuk rencana produksi anda?

Contoh 1 Persoalan LP

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

5 Langkah Memformulasikan Model LP

1. Pahami persoalan.

2. Tentukan variabel keputusan

X1=jumlah produk A yang diproduksi

X2=jumlah produk B yang diproduksi

3. Nyatakan fungsi tujuan sebagai suatu kombinasi linier dari variabel-variabel keputusan

MAX: 5X1 + 14X2

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

5 Langkah Memformulasikan Model LP

4. Nyatakan fungsi-fungsi pembatas sebagai suatu kombinasi linier dari variabel-variabel keputusan

1X1 + 2X2 <= 6 } fiber

1X1 + 4X2 <= 8 } jam kerja

5. Tentukan batas atas dan batas bawah dari

nilai-nilai variabel keputusan.

X1 >= 0

X2 >= 0

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Model LP untuk Contoh Soal 1

MAX: 5X1 + 14X2

S.T.: 1X1 + 2X2 <= 6

1X1 + 4X2 <= 8

X1 >= 0

X2 >= 0

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Contoh 2 Persoalan LP

Sebuah perusahaan memproduksi dua jenis tabung

panas, yaitu jenis Aqua-Spas & Hydro-Luxes. Data

yang terkait dengan kegiatan ini adalah:

Tersedia 200 pompa, 1566 jam kerja, dan 2880

feet tabung. Bagaimana formulasinya?

Aqua-Spa Hydro-Lux

Pompa 1 1

Waktu proses 9 hours 6 hours

Tabung 12 feet 16 feet

Profit/unit $350 $300

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

5 Langkah Memformulasikan Model LP

1. Pahami persoalan.

2. Tentukan variabel keputusan

X1=jumlah Aqua-Spas yang diproduksi

X2=jumlah Hydro-Luxes yang diproduksi

3. Nyatakan fungsi tujuan sebagai suatu kombinasi linier dari variabel-variabel keputusan

MAX: 350X1 + 300X2

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

5 Langkah Memformulasikan Model LP

4. Nyatakan fungsi-fungsi pembatas sebagai suatu kombinasi linier dari variabel-variabel keputusan

1X1 + 1X2 <= 200 } pompa

9X1 + 6X2 <= 1566 } jam kerja

12X1 + 16X2 <= 2880 } tabung

5. Tentukan batas atas dan batas bawah dari

nilai-nilai variabel keputusan.

X1 >= 0

X2 >= 0

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Model LP untuk Persoalan Tabung Panas

MAX: 350X1 + 300X2

S.T.: 1X1 + 1X2 <= 200

9X1 + 6X2 <= 1566

12X1 + 16X2 <= 2880

X1 >= 0

X2 >= 0

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

KONSEP PRIMAL - DUAL • Setiap formulasi persoalan LP mempunyai

bentuk Dual

• Jika fungsi tujuan Primal adalah Maks maka fungsi tujuan Dual adalah Min dan sebaliknya

• Dual dari Dual adalah Primal

• Solusi optimal persoalan Primal (jika ada) adalah sama dengan solusi optimal persoalan Dual

• Jika persoalan Primal tidak fisibel maka Dual akan unbounded dan sebaliknya

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

KONSEP PRIMAL - DUAL • Jumlah baris pada Primal sama dengan

jumlah kolom pada Dual dan sebaliknya

• Ruas kanan pada Primal akan menjadi koefisien fungsi tujuan pada Dual dan sebaliknya

• Jika pembatas Primal normal maka variabel Dual akan normal dan sebaliknya

• Jika pembatas Primal bertanda = maka variabel Dual akan tidak terbatas dalam tanda dan sebaliknya

Jurusan Teknik Industri FT Unpas

Tjutju T. Dimyati

Contoh Soal

Bagaimanakah bentuk Dual dari:

Maks Z = 3 X1 + 5 X2

dengan pembatas

X1 4

2 X2 = 12

3 X1 + 2 X2 18

X1 URS , X2 0