Linear Programming
DEFINISI LP
PENGANTAR LINEAR PROGRAMMING
• Linear Programming/LP (Program Linear) merupakan salah satu teknik dalam Riset Operasional (Operation Research) yang paling luas digunakan dan dikenal dengan baik. • LP merupakan metode matematika untuk mengalokasikan sumber daya untuk mencapai tujuan tunggal seperti memaksimumkan keuntungan atau meminimumkan biaya. 6623 - Taufiqurrahman
MODEL LINEAR PROGRAMMING
FUNGSI-FUNGSI DALAM PL
Adalah sebuah model matematis yang bersifat umum yang digunakan untuk mengalokasikan faktor produksi atau sumber daya yang jumlahnya terbatas secara optimal, sehingga dapat menghasilkan laba maksimal atau biaya minimal
6623 - Taufiqurrahman
6623 - Taufiqurrahman
2
3
1. Variabel Keputusan
Variabel persoalan yang akan mempengaruhi nilai tujuan yang hendak dicapai. 2. Fungsi Tujuan (objective function)
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. 6623 - Taufiqurrahman
4
1
Linear Programming
FUNGSI-FUNGSI DALAM PL
ASUMSI DASAR
3. Fungsi Kendala (contrains or subject to)
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. 4. Fungsi Status (status function) Fungsi yang menyatakan bahwa setiap variabel yang terdapat di dalam model programasi linear tidak boleh negatif. 6623 - Taufiqurrahman
2.
Proporsionality Alokasi sumber daya dengan goal yang ingin dicapai harus proporsional
3.
Additivity Total dari semua aktivitas adalah sama dengan jumlah dari aktivitas individual 6623 - Taufiqurrahman
6
FORMULASI MODEL
4. Divisibility Jumlah produk yang akhirnya direkomendasikan dalam kondisi optimum, dapat berupa pecahan bukan bilangan bulat 5. Non-negatif variable Semua variabel bukan negatif, bisa nol atau positif (negatif dalam kuantitas fisik a/d mustahil)
6623 - Taufiqurrahman
Certainty Angka yang diasumsikan dalam f.tujuan dan f.kendala secara pasti diketahui dan tidak berubah selama waktu dipelajari.
5
ASUMSI DASAR
6623 - Taufiqurrahman
1.
7
• Permasalahan: mencari nilai-nilai optimal (maksimum atau minimum) dari fungsi linear dengan kendala-kendala tertentu • Fungsi Tujuan: Fungsi linear yang dioptimumkan • Fungsi Kendala: Fungsi-fungsi linear (lebih dari satu) yang harus dipenuhi dalam optimalisasi fungsi tujuan. • Bentuk fungsi pertidaksamaan
tujuan:
6623 - Taufiqurrahman
persamaan
atau
8
2
Linear Programming
FUNGSI MATEMATIKA LP
FORMULASI MODEL
1.
Formulasi model matematika, yang meliputi 3 tahap:
Fungsi Tujuan Max/Min
1. Tentukan variable keputusan dan nyatakan dalam simbol matematika
2. Fungsi Kendala
2. Membentuk suatu fungsi tujuan yang ditunjukkan sebagai suatu hubungan linear dari variable keputusan. 3. Menentukan semua kendala masalah dan mengekspresikan dalam persamaan atau pertidaksamaan yang juga merupakan suatu hubungan linear dari variable keputusan. 6623 - Taufiqurrahman
a12x2
+
a21x1
+
a22x2
+
...
...
... am1x1 3.
+
a1nxn
<
b1
…
+
a2nxn
<
b2
<
bn
...
... +
…
...
...
am2x2
+
…
... +
amnxn
Fungsi Status x1 ; x2 ……………….. Xn > 0 6623 - Taufiqurrahman
10
Karakteristik Formulasi Masalah
Grafis
Simpleks
Simpleks Big – M
Jumlah Variabel
2
>2
>2
Simpleks M-Besar
Jenis fungsi tujuan
maksimisasi & minimisasi
maksimisasi & minimisasi
maksimisasi & minimisasi
Simpleks Dua Fase
Jenis fungsi kendala
semua bentuk
Pertidaksamaan bertanda “<“
Pertidaksamaan bertanda “>“ atau persamaan “=“
Metode Aljabar
6623 - Taufiqurrahman
6623 - Taufiqurrahman
+
PERBEDAAN METODE SOLUSI
Metode Linear Programming
Simpleks Dual
a11x1
9
METODE-METODE DALAM LP
Simpleks Primal
Z = c1x1 + c2x2 + ... + cnxn
Metode Grafik
11
6623 - Taufiqurrahman
12
3
Linear Programming
CONTOH 1 (PEMBUATAN MODEL)
MODEL CONTOH 1
Sebuah perusahaan memperkerjakan pengrajin untuk memproduksi mangkok dan cangkir. Sumber daya utama yang digunakan perusahaan adalah tanah liat dan tenaga kerja. Tersedia 40 jam tenaga kerja dan 120 kg tanah liat setiap hari untuk produksi. Dengan keterbatasan sumber daya, perusahaan ingin mengetahui berapa banyak mangkok dan cangkir yang akan diproduksi tiap hari dalam rangka memaksimalkan laba. Parameter kedua produk adalah sebagai berikut:
Variabel Keputusan Fungsi Tujuan
Kebutuhan Sumber Daya Produk
Tenaga Kerja (jam/unit)
Tanah Liat (kg/unit)
Laba ($/unit)
Mangkok
1
4
40
Cangkir
2
3
50
6623 - Taufiqurrahman
Fungsi Kendala 13
CONTOH 2 (PEMBUATAN MODEL)
• X1 = jumlah mangkok yang diproduksi • X2 = jumlah cangkir yang diproduksi • Maksimalkan Z = 40X1 + 50X2 • Z = total laba per hari • 40X1 = laba dari mangkok • 50X2 = laba dari cangkir
• 1X1 + 2X2 ≤ 40 • 4X1 + 3X2 ≤ 120 • X1 ≥ 0 ; X2 ≥ 0
(kendala tenaga kerja) (kendala tanah liat) (kendala non negatif)
6623 - Taufiqurrahman
14
MODEL CONTOH 2
Seorang petani menyiapkan lahan untuk menanam dan membutuhkan pemupukan. Terdapat dua merek pupuk, Super-grow dan Crop-quick. Setiap merek menghasilkan jumlah nitrogen dan fosfat tertentu, sebagai berikut:
Variabel Keputusan
• X1 = jumlah pupuk SG yang dibeli • X2 = jumlah pupuk CQ yang dibeli
Kontribusi Kimia Merek
Nitorgen (kg/kantong)
Fosfat (kg/kantong)
Super-grow
2
4
Crop-quick
4
3
Fungsi Tujuan
Lahan petani memerlukan paling sedikit 16 kg nitrogen dan 24 kg fosfat. Harga Super-grow $6 per kantong, dan Crop-quick berharga $3. Petani tersebut ingin mengetahui berapa banyak kantong dari setiap merek yang akan dibeli dalam rangka meminimalkan total biaya pemupukan. 6623 - Taufiqurrahman
6623 - Taufiqurrahman
15
Fungsi Kendala
• Minimalkan Z = 6X1 + 3X2 • Z = total biaya pemupukan • 6X1 = harga/biaya dari SG • 3X2 = harga/biaya dari CQ
• 2X1 + 4X2 ≥ 16 • 4X1 + 3X2 ≥ 24 • X1 ; X2 ≥ 0 6623 - Taufiqurrahman
(kendala nitrogen) (kendala fosfat) (kendala non-negatif) 16
4
Linear Programming
PEMBUATAN MODEL: ANALISA TITIK IMPAS
KOMPONEN ANLISA TITIK IMPAS
• Bagian ini merupakan proses pengembangan dan pemecahan model sains manajemen melalui analisa break even atau analisa titik impas.
1. Volume (V)
• Tujuan analisa titik impas adalah untuk menentukan jumlah unit produk (atau volume produksi) yang akan dijual dan diproduksi sehingga pendapatan total akan sama dengan biaya total. • Titik dimana pendapatan total menyamai biaya total disebut titik impas atau titik break even, dan pada titik ini keuntungan sama dengan nol. 6623 - Taufiqurrahman
vcv
cf
Dimana : • Z = keuntungan total • v = volumen (jumlah unit yang dijual) • p = harga per unit • TC = biaya total
Z 6623 - Taufiqurrahman
6623 - Taufiqurrahman
• Biaya tetap (fixed cost), biaya yang tidak tergantung dengan volume produksi atau penjualan. • Biaya variabel (variabel cost), biaya yang tergantung dengan volume produksi atau penjualan. 3. Keuntungan (Z) • Perbedaan antara pendapatan total dan baiaya total. • Pendapatan total merupakan volume dikali dengan harga per unit.
17
PERSAMAAN MATEMATIS ANALISA TITIK IMPAS
TC
• Tingkat pendapatan atau produksi perusahaan. • Dapat dinyatak sebagai: • Jumlah unit (atau kuantitas) yang diproduksi dan dijual. • Volume penjulan dalam satuan mata uang. • Persentase dari kapasitas yang tersedia. 2. Biaya (TC TC))
Dimana : • TC = biaya total • cf = biaya tetap total • v = volumen (jumlah unit yang dijual) • cv = biaya variabel per unit
vp
TC 19
6623 - Taufiqurrahman
18
CONTOH ANALISA TITIK IMPAS Kasus: Sebuah perusahaan memproduksi baju, dengan biaya tetap sebesar $10.000 dan biaya variabel $8 per unit baju. Dalam satu bulan perusahaan dapat menjual 400 unit dengan harga $23. Berapa keuntungan total yang didapat perusahaan? Jawaban: Z = vp − (cf + vcv) = (400)(23) − {10.000 + (400)(8)} = 9.200 − 13.200 Perusahaan Rugi = −$4.000 6623 - Taufiqurrahman
Bagaimana agar untung (minimal keuntungan nol) ???
20
5
Linear Programming
MENGHITUNG TITIK IMPAS • Dengan menggunakan contoh perusahaan baju, dan jika diasumsikan harga statis, serta biaya tetap dan biaya variabel tidak berubah, maka satu-satunya yang dapat diubah ada volume pendapatan. Sehingga, berapa jumlah volume pendapatan yang dapat menghasilkan keuntungan nol? • Pada titik impas, dimana pendapatan total sama dengan biaya total, maka keuntungan akan sama dengan nol. Sehingga, jika angka nol dimasukkan pada Z, maka volume dapat ditentukan, yaitu: Z = vp − (cf + vcv) 0 = (23) − {10.000 + v(8)} 0 = 23v − 10.000 − 8v Titik impas (break (break even 15v = 10.000 point)) perusahaan point v = 666,7 unit baju 6623 - Taufiqurrahman
6623 - Taufiqurrahman
21
6623 - Taufiqurrahman
22
6
