Tugas SM - Program Linier

   MANAJEMEN SAIN

PROGRAM LINIER

                                                               

1.      Pengertian Program Linear

Program Linear adalah suatu cara untuk penyelesaian masalah dengan menggunakan persamaan atau pertidaksamaan linear yang mempunyai banyak penyelesaian, dengan memperhatikan syarat-syarat agar diperoleh hasil yang maksimum/minimum (penyelesaian optimum).

2.      Model Matematika

Model matematika adalah sistim persamaan atau pertidaksamaan yang mengungkapkan semua syarat yang harus dipenuhi oleh x dan y.

Model matematika ini merupakan cara sederhana untuk memandang suatu masalah dengan menggunakan persamaan atau pertidaksamaan matematika.

3. Nilai Optimum

Nilai optimum diperoleh berdasarkan nilai fungsi tujuan yang dikehendaki, yaitu berupa nilai maksimum atau nilai minimum. Cara mencarinya bias dengan :

a.       Mensubstitusi koordinat titik-titik sudut dalam daerah penyelesaian terhadap fungsi tujuan.

b.      Menggunakan garis selidik

A.     Definisi Pemprograman Linier

          Setiap perusahaan atau organisasi memiliki keterbatasan atas sumber dayanya, baik keterbatasan dalam jumlah bahan baku, mesin dan peralatan, ruang tenaga kerja, jam kerja, maupun modal. Dengan keterbatasan ini, perusahaan perlu merencanakan strategi yang dapat mengoptimalkan hasil yang ingin dicapai, baik itu berupa keuntungan maksimal atau biaya minimal. Berbagai cara lain telah ditemukan untuk tujuan itu, salah satu diantaranya pemrograman linear (Eddy, 2008).

Pemprograman linier adalah metode matematik dalam mengalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimalkan keuntungan atau meminimumkan biaya. Program linier berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu model matematik yang terdiri dari sebuah fungsi tujuan linier dengan beberapa kendala linier (Taha, 1993).

Program linier banyak digunakan untuk menyelesaikan masalah optimal didalam industri, perbankan, pendidikan, dan masalah-masalah lain yang dapat dinyatakan dalam bentuk linier.

                  B.        Dua macam fungsi Program Linear:

1. Fungsi tujuan : mengarahkan analisa untuk mendeteksi tujuan perumusan masalah
2. Fungsi kendala : untuk mengetahui sumber daya yang tersedia dan permintaan atas sumber daya tersebut.

C.        Karakteristik  Pemrograman Linier

Sifat linearitas suatu kasus dapat ditentukan dengan menggunakan beberapa cara. Secara statistik, kita dapat memeriksa kelinearan menggunakan grafik (diagram pencar) ataupun menggunakan uji hipotesa. Secara teknis, linearitas ditunjukkan oleh adanya sifat proporsionalitas, additivitas, divisibilitas dan kepastian  fungsi tujuan dan pembatas.

Sifat proporsional dipenuhi jika kontribusi setiap variabel pada fungsi tujuan atau penggunaan sumber daya yang membatasi proporsional terhadap level nilai variabel.

Jika harga per unit produk misalnya adalah sama berapapun jumlah yang dibeli, maka sifat proporsional dipenuhi. Atau dengan kata lain, jika pembelian dalam jumlah besar mendapatkan diskon, maka sifat proporsional tidak dipenuhi. Jika penggunaan sumber daya per unitnya tergantung dari jumlah yang diproduksi, maka sifat proporsionalitas tidak dipenuhi

Sifat additivitas mengasumsikan bahwa tidak ada bentuk perkalian silang diantara berbagai aktivitas, sehingga tidak akan ditemukan bentuk perkalian silang pada model. Sifat additivitas berlaku baik bagi fungsi tujuan maupun pembatas (kendala). Sifat additivitas dipenuhi jika fungsi tujuan merupakan penambahan langsung kontribusi masing-masing variabel keputusan. Untuk fungsi kendala, sifat additivitas dipenuhi jika nilai kanan merupakan total penggunaaan masing-masing variabel keputusan. Jika dua variabel keputusan misalnya merepresentasikan dua produk substitusi, dimana peningkatan volume penjualan salah satu produk akan mengurangi volume penjualan produk lainnya dalam pasar yang sama, maka sifat additivitas tidak terpenuhi.

 berarti unit aktivitas dapat dibagi ke dalam sembarang level fraksional, sehingga nilai variabel keputusan non integer dimungkinkan.

Sifat  kepastian menunjukkan bahwa semua parameter model berupa konstanta. Artinya koefisien fungsi tujuan maupun fungsi pembatas merupakan suatu nilai pasti, bukan merupakan nilai dengan peluang tertentu. 

Keempat asumsi (sifat) ini dalam dunia nyata tidak selalu dapat dipenuhi. Untuk meyakinkan dipenuhinya keempat asumsi ini, dalam pemrograman linier diperlukan analisis sensitivitas terhadap solusi optimal yang diperoleh.

           

D.     ASUMSI-ASUMSI DASAR LINEAR PROGRAMMING :

1.Proportionality
Asumsi ini berarti bahwa naik turunya nilai Z dan penggunaan sumber atau fasilitas yang tersedia akan berubah secara sebanding (proportional) dengan perubahan tingkat kegiatan

2.Additivity
Asumsi ini berarti bahwa nilai tujuan tiap kegiatan tidak saling mempengaruhi, atau dalam LP dianggap bahwa kenaikan dari nilai tujuan (Z) yang diakibatkan oleh kenaikan suatu kegiatan dapat ditambahkan tanpa mempengaruhi bagian nilai Z yang diperoleh dari kegiatan lain

3.Divisibility
Asumsi ini menyatakan bahwa keluaran (output) yang dihasilkan oleh setiap kegiatan dapat berupa bilangan pecahan. Demikian pula dengan nilai Z yang dihasilkan.

4.Deterministik(Certainty)
Asumsi ini enyatakan bahwa semua parameter yang terdapat dalam model LP (                 ) dapat diperkirakan dengan pasti, meskipun jarang dengan tepat

Fungsi Tujuan :

            Max/min            z = c₁x₁ + c₂x₂ + ... + c_nx_n

Berdasarkan kendala :

                                    a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n    (≤, =, ≥) b₁

                                    a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n    (≤, =, ≥) b₂

                                                :

                                    a_m1x₁ + a_m2x₂ + ... + a_mnx_n (≤, =, ≥) b_m

                                               

                                    x_1, x₂ , ... x_n  ≥ 0

            x_j = variabel keputusan ke j

            b_i = kapasitas kendala ke i

            c_j = koefisien fungsi tujuan ke j

            a_ij = koefisien kendala

Terdapat 3 Tahap dalam penggunaan Teknik Program Linier:

1.      Masalah harus dapat diidentifikasi sebagai sesuatu yang dapat diselesaikan dengan Program Linier.

2.      Masalah yang Tidak terstruktur harus dapat diselesaikan dalam Model Matematika sehingga menjadi terstruktur.

3.      Model harus diselesaikan dengan teknik matematika yang telah dibuat.

Secara umum, tujuan perusahaan yang paling sering adalah mencapai laba atau keuntungan maksimum dan dengan biaya yang seminimum mungkin. Saat Manajer/Atasan  berusaha untuk menyelesaikan masalah dengan mencari tujuan yang dibatasi ini, maka Program Linier menjadi salah satu acuan yang sering digunakan.

Ada 3 langkah utama dalam merumuskan model pemrograman linier yaitu:

1.      Tentukan variabe yang ingin diketahui atau variabel keputusan dan gambar dalam simbol-simbol aljbar.

2.      Tentukan semua keterbatasan atau kendala dan gambar dalam bentuk persamaan linier atau ketidaksamaan dari variable tadi

3.      Tentukan tujuan atau kreteria dan gambaran sebagai fungsi linier dari variabel keputusan yang akan berbentuk maksimasi atau minimalisasi

Contoh KASUS :

Seorang pengusaha Laptop membuat dua macam tipe, yaitu tipe portable touchscreen (A₁) dan tipe flip standar (A₂). Kedua jenis laptop dibuat dari bahan yang sama yaitu X dan Y, dengan komposisi yang berbeda.

Setiap tipe laptop portable touchscreen dibuat dari campuran 1 unit bahan X dan 3 bahan Y, sedangkan setiap tipe laptop flip standar dibuat dari campuran 2 unit bahan X dan 1 unit bahan Y. Karena keterbatasan pasokan, setiap hari ia hanya memperoleh 20 unit bahan X dan 20 unit  bahan Y.

Untuk setiap laptop tipe portable touchscreen yang ia buat, ia memperoleh keuntungan sebesar 300.000. Untuk setiap laptop tipe flip standar, ia memperoleh keuntungan sebesar 200.000.

Jika diasumsikan bahwa semua laptop laku terjual, berapa laptop masing-masing tipe harus ia buat agar keuntungan yang didapatkan maksimum?

Penyelesaian:

Sistem tabel pemodelan

Bahan	Laptop tipe portabletouchscreen (A1)	Laptop tipe flip standar (A2)	Pasokan Maksimum
X	1	2	20
Y	3	1	20
Untung	300.000	200.000

Maksimumkan, f(x₁, x₂) = 300.000 x₁ + 200.000 x₂ è 3 x₁ + 2 x₂ (dalam ratusan ribu)

Kendala :

x₁ + 2 x₂ ≤ 20

3 x₁ + x₂ ≤ 20

x₁, x₂ ≥ 0

Penggambaran kendala x₁ + 2 x₂ ≤ 20, 3 x₁ + x₂ ≤ 20 dan x₁, x₂ ≥ 0

Perpotongan bidang yang memenuhi semua kendala disebut daerah fisibel. Daerah fisibel dalam kasus ini disebut daerah fisibel AEDO (bagian yang diarsir pada bagian perpotongan bidang AOB dan bidang COD).

Koordinat E dapat dicari dari perpotongan x₁ + 2 x₂ ≤ 20 dan 3 x₁ + x₂ ≤ 20 sehingga diperoleh E(4,8).

Titik-titik sudut daerah fisibel dapat melihat keuntungan maksimum yang ingin dicapai pengusaha:

Titik-titik sudut daerah fisibel	Nilai fungsi , f(x1, x2) = 3 x1 + 2 x2 3 x1 + 2 x2 (dalam ratusan ribu)
O (0,0)	3(0) + 2(0) = 0
A (0,10)	3(0) + 2 (10) = 20
E (4,8)	3(4) + 2(8) = 12 + 16 = 28
D (20/3,0)	3(20/3) + 2(0) = 20

Keuntungan maksimum yang ingin dicapai pengusaha adalah 2.800.000.

PENYELESAIAN DALAM METODE SIMPLEX

Contoh Soal :

Meminimumkan : Z = 40 X1 + 80X2

dengan syarat ikatan :

a). X1 + X2 ³ 4

b). X1 + 3X2 ³ 6

dan X1 ³ 0, X2 ³ 0

Penyelesaian :

*) Bentuk Kanonik :

X1 + X2 - 1S1 + 0S2 + 1 V1 + 0V2 = 4

X1 + 3X2 + 0S1 - 1S2 + 0 V1 + 1V2 = 6

Meminimumkan : Z = 40 X1 + 80X2 + 0S1 + 0S2 + MV1 + MV2

*) Tabel simpleks :

Karena semua Zj – Cj £ 0, maka tabel sudah minimal, dengan nilai X1 = 3, dan X2 = 1, dan

Zminimalnya = 200.