Pemrograman Linier Tugas 2

Program Linier adalah program model matematika yang digunakan untuk menyelesaikan masalah optimasi yang dimaksud masalah optimasi disini ialah masalah yang hendak dianalisis.

Setiap model program linier dinyatakan dalam bentuk fungsi tujuan dan fungsi batasan (kendala, constraint).

Fungsi tujuan suatu persamaan fungsi linier dari variable tujuan, dalam fungsi tujuan harus dijelaskan apakah akan memaksimalkan atau meminimalkan fungsi variable dan mengarahkan analisa untuk mendeteksi tujuan perumusan masalah

Fungsi batasan menggambarkan batasan yang dihadapi dalam mencapai tujuan, fungsi batasan biasanya terdiri dari beberapa persamaan yang masing-masing berkorelasi dengan sumberdaya tertentu dan atas permintaan atas sumberdaya tersebut.

Dalam model matematika permasalahan dalam pemrograman linier dapat digambarkan dalam bentuk umum, sebagai berikut :

Fungsi Tujuan (FT)                 maks/min Z =

Dengan pembatasan  (DP)      >=< b₁

                                                Dan X_j ≥ 0 (j = 1, 2, …,n)

                                                        B₁ ≥ 0 (i = 1,2,…m)

Misalnya terdapat variable kegiatan/keputusan dan 3 batasan sumber daya persamaan matematisnya sebagai berikut :

Fungsi Tujuan                         maks/min Z = cX + cX          

Dengan pembatasan                a₁₁ X₁ + a₁₂ X₂ >=< b₁

                                                a₂₁ X₁ + a₂₂ X₂ >=< b₂

                                                a₃₁ X₁ + a₃₂ X₂ >=< b₃

                                                dan X₁, X₂  ≥ 0

keterangan :

Z = nilai dari fungsi tujuan

X_j = jenis kegiatan (variable keputusan)

a_ij = kebutuhan sumberdaya i untuk menghasilkan setiap unit kegiatan j

b_i = banyaknya sumberdaya i yang tersedia

c_j = kenaikan nilai Z jika ada pertambahan satu unti j

a, b, dan c disebut juga sebagai parameter model

m = jumlah sumberdaya yang tersedia

n = jumlah kegiatan

Dalam pembuatan model pemprograman linier harus diusahakan untuk memenuhi criteria sebagai berikut :

• Tujuan yang akan dicapai  dinyatakan dalam fungsi linier, disebut fungsi tujuan.
• Sumber-sumber tersedia dalam jumlah terbatas, dan pembatasan harus dinyatakan dalam bentuk ketidaksamaan yang linier.
• Harus ada alternative pemecahan yaitu suatu solusi/pemecahan yang memenuhi semua batasan/kendala.

Contoh studi kasus

• Perusahaan Bakti Jaya memproduksi cat interior dan exterior dari dua bahan baku, A₁ dan A₂. Tabel dibawah ini adalah informasi mengenai kebutuhan bahan baku, ketersediaan dan keuntungannya.
• Survey pasar menunjukkan bahwa kebutuhan perhari untuk cat interior tidak boleh melebihi cat exterior lebih dari 1 ton, juga kebutuhan harian maksimal untuk cat interior adalah 2 ton.
• Bakti Jaya ingin menentukan jumlah optimal (terbaik) produk antara cat interior dan exterior dengan memaksimalkan total keuntungan harian.

Tabel kebutuhan bahan baku, ketersediaan dan keuntungannya.

Produk	Kebutuhan bahan baku (ton)		Keuntungan (x1000)
	A1	A2
Cat Exterior	6	1	5
Cat Interior	4	2	4
Kapasitas	24	6	Z

Penyelesaian kasus Perusahaan Bakti Jaya harus dengan :

• Menentukan variable keputusan

Tentukan jumlah produksi cat exterior dan interior perhari. Maka variabel dari model didefiisikan sebagai :

X₁ = ton produksi harian cat exterior

X₂ = ton produksi harian cat interior

• Menentukan fungsi tujuan

Fungsi tujuan, perusahaan ingin memaksimalkan total keuntungan harian dari kedua produk.

Cat exterior adalah 5 (x1000) per unit

Cat interior adalah 4 (x1000) per unit

Maka dapat didefinisikan bahwa :

         Total keuntungan dari cat exterior = 5X₁ (x1000) rupiah

         Total keuntungan dari cat exterior = 4X₂ (x1000) rupiah

Jika Z merepresentasikan total keuntungan harian, tujuan perusahaan adalah :

         Maksimalkan Z = 5X₁ + 4X₂

• Menentukan constraint

Constraint yang membatasi bahan baku yang digunakan dan kebutuhan produk pada bahan baku.

         (Penggunaan bahan baku oleh kedua produk) ≤ Kapasitas ketersediaan bahan baku

Pembatasan bahan baku dinyatakan secara verbal sebagai :

Penggunaan harian bahan baku A₁ adalah 6 ton untuk cat exterior dan 4 ton untuk cat interior. Maka :

         Penggunaan bahan baku A₁ oleh cat exterior = 6X ton/hari

         Penggunaan bahan baku A₁ oleh cat exterior = 4X₂ ton/hari

Sehingga :

         Penggunaan bahan baku A₁ oleh kedua cat = 6X₁ + 4X₂ ton/hari

         Penggunaan bahan baku A₂ oleh kedua cat = 1X₁ + 2X₂ ton/hari

Karena ketersediaan harian dari bahan baku A₁ dan A₂ dibatasi 24 dan 6 ton, maka hubungan batasan yang diberikan menjadi :

         6X₁ + 4X₂ ≤ 24 (bahan baku A₁)

          X₁ + 2X₂ ≤ 6 (bahan baku A₂)

• Batasan permintaan yang pertama adalah bahwa batas produksi harian cat interior melebihi cat exterior, X₂ – X₁, seharusnya tidak melewati 1 ton, yang ditranslasikan dengan :

X₂ – X₁ ≤ 1 (batas pasar)

• Batasan permintaan yang kedua adalah bahwa maksmal kebutuhan harian cat interior dibatasi 2 ton, yang ditrnslasikan dengan :

X₂ ≤ 2 (batas permintan)

• Batasan implicit (pemahaman mandiri) adalah bahwa variabel X₁ dan X₂ tidak dapat diasumsikan bernilai negatif, karena tidak mungkin jumlah produksi bernilai negatif. Batasan nonnegative, X₁ ≥ 0, X₂ ≥ 0, dapat dipertangunggjawabkan untuk kebutuhan ini.

Model lengkap

Maksimalkan   Z = 5X₁ + 4X₂

Kendala :         6X₁ +4X₂ ≤ 24            (1)

                        X₁ + 2X₂ ≤ 6               (2)

                        -X₁ + X₂ ≤ 1                (3)

                        X₂ ≤ 2                          (4)

                        X₁, X₂ ≥ 0                   (5)

Sembarang nilai X₁ dan X₂ yang memenuhi semua lima constraint disebut dengan solusi yang layak (feasible solution), jika tidak maka merupakan solusi yang tidak layak (unfeasible).

Prosedur penyelesaian menggunakan metode grafik

• Menentukan lokasi solusi yang layak

Constraint nonnegative X₁ ≥ 0 dan X₂ ≥ 0. Dalam gambar sumbu horizontal X₁ dan vertical X₂ mewakili variabel cat exterior dan interior. Maka untuk nilai variabel nonnegative berada di kuadran pertama.

Constraint yang lain :

Pertama perlu mengganti setiap tanda pertidaksamaan dengan persamaan Menggambar garis lurus dengan memilih dua titik berbeda yang memenuhi persamaan garis pada diagram. Misalnya setelah mengganti 6X₁ + 4X₂ ≤ 24 dengan garis lurus 6X₁ + 4X₂ = 24, kita dapat menentukan dua garis berbeda yang dilalui garis tersebut. Caranya dengan mengganti X₁ = 0 untuk mendapatkan X₂ = 24/4 = 6, dan mengganti X₂ = 0 untuk mendapatkan X₁ = 24/6 = 4.

Maka garis untuk persamaan tersebut melewati dua titik (0,6) dan (4.0), seperti yang ditunjukkan pada gambar. Memperhatikan pengaruh pertidaksamaan.

Garis tersebut membagi daerah menjadi dua bagian, hanya satu bagian yang merupakan sisi yang benar yang memenuhi pertidaksamaan.

Untuk menentukan sisi yang benar, ujilah titik disalah satu sisi (titik yang tidak dilewati garis), misalnya (0,0) maka didapatkan 6 * 0 + 4 * 0 = 0 dan 0 ≤ 24, berarti daerah yang ditempati titik (0,0) adalah daerah yang memnuhi pertidaksamaan tersebut.

Dalam gambar yang ditampilkan daerah tersebut diarsir.

6X₁ + 4X₂ ≤ 24

Dilakukan juga pada constraint yang lain

Constraint	Titik potong dengan sumbu X1 dan X2
6X1 +4X2 ≤ 24	(0,6) dan (4,0)
X1 + 2X2 ≤ 6	(0,3) dan (6,0)
-X1 + X2 ≤ 1	(0,1) dan (-1,0)
X2 ≤ 2	Garis horizontal yang melewati X2 = 2

• Menentukan solusi optimal dari diantara semua titik sudut solusi layak.

Daerah solusi layak seperti pada gambar adalah daerah yang diarsir yang diliputi oleh semua constraint. Semua titik yang berada di daerah tersebut adalah daerah solusi layak. Karena jumlahnya sangat banyak, maka perlu cara yang sistematis untuk mendapatkan titik optimal dari solusi masalah. Daerah solusi layal dibatasi oleh titik ABCDEF seperti pada

Identifikasi arah dari fungsi profit Z = 5X₁ + 4X₂ Ingin memaksimalkan Z. Nilai Z sementara coba digunakan nilai sembarang terlebih dahulu untuk mengetahui arah peningkatan nilai Z pada gambar. Misalnya, menggunakan Z = 10 dan Z = 15, akan memberikan garis putus-putus pada dan Z = 15, akan memberikan garis putus-putus pada gambar dengan persamaan 5X₁ + 4X₂ = 10 dan 5X₁ + 4X₂ = 15.

Maka arah peningkatan Z seperti ditunjukkan pada gambar. Solusi optimal berada dititik E. Untuk mendapatkan nilai X₁ dan X₂ dititik E diselesaikan dengan gabungan garis fungsi constraint (1) dan (2)

6X₁ + 4X₂ = 24

X₁ + 2X₂ = 6 atau X₁ = 6 – 2X₂

Dengan mensubtitusikan persamaan kedua pada persamaan pertama, didapatkan :

6 (6 – 2X₂) + 4X₂ = 24

36 – 12X₂ + 4X₂ = 24

-8X₂ = -12

X₂ = 1.5

X₁ + 2X₂ = 6

X₁ + 2(1.5) = 6

X₁ + 3 = 6

X₁ = 3

Dengan cara aljabar, didapatkan bahwa X₁ = 3 dan X₂ = 1.5 dengan Z = 5*3 + 4*1.5 = 21

Evaluasi semua titik sudut pada daerah solusi yang layak

Solusi optimal didapatkan dititik E dengan nilai X₁ = 3 ton dan X₂ = 1.5 ton dan laba maksimal yang didapat Z = 21000

  

Titik Sudut	(X1, X2)	Z
A	(0,0)	0
B	(0,1)	4
C	(1,2)	13
D	(2,2)	18
E	(3,1.5)	21 (OPTIMAL)
F	(4,0)	20

Konsep Sains Manajemen dan Studi Kasus

Sains Manajemen adalah penerapan ilmiah dengan menggunakan perangkat dan metode matematika untuk memecahkan masalah manajemen dalam rangka membantu membantu manajer manajer dan pimpinan pimpinan serta pihak manajemen lain untuk membuat keputusan yang terbaik. Sains Manajemen menggunakan teknik matematika, statistik, ilmu-ilmu murni dan perekayasaan.

Sains Manajemen berfokus terutama pada pengembangan model matematika. Model matematika adalah representasi dari sebuah system, proses, atau hubungan yang disederhanakan.

Pada tingkatnya yang paling dasar, sains manajemen berfokus pada model, persamaan dan representasi sejenisnya dari kenyataan. Sebagai contoh, manajer di Detroit Edison menggunakan model matematika untuk mencari cara terbaik untuk membuat rute bagi petugas terbaik selama terjadinya pemadaman listrik. Bank of New England menggunakan model untuk mengetahui berapa banyak teller yang diperlukan untuk bekerja pada setiap lokasi bank pada sewaktu-waktu yang berbeda sepanjang hari. Pada tahun belakangan ini, seiring dengan kemajuan computer, teknik sains manajemen telah menjadi sangat canggih. Sebagai contoh pembuat mobil Daimler Chrysler dan Ford menggunakan simulasi computer yang realistis untuk mempelajari kerusakan tabrakan pada mobil. Simulasi ini memberikan informasi yang akurat dan menghindari biaya “penghancuran” begitu banyak mobil uji.

Pendekatan Sains Manajemen 

Untuk memecahkan masalah dalam Sains Manajemen dilakukan pendekatan sistematis dan logis dengan metode ilmiah, meliputi :

1. Observasi, pelajari masalah: Krisis, Situasi yang harus diantisipasi dan direncanakan, Dilakukan oleh manajer, dan Pakar Sains Manajemen : orang yang menguasai teknik sains manajemen dan terlatih untuk memecahkan masalah menggunakan teknik sains manajemen
2. Definisi Masalah, masalah yang terjadi harus dijabarkan dan ditegaskan dengan singkat dan jelas, ada masalah sama dengan tujuan perusahaan tidak tercapai.
3. Model Kontruksi, model Sains Manajemen merupakan penyajian yang ringkas dari situasi masalah yang sedang berjalan, dalam bentuk grafik, diagram, atau set hubungan sistematis (angka dan sibol-simbol).
4. Solusi, solusi dari pembuatan model yang sudah dijalankan.
5. Pelaksanaan, pelaksanaan nyata dari model yang sudah dikembangkan atau pemecahan dari masalah yang dihasilkan oleh model yang telah dikembangkan.

Teknik Analisis Kuantitatif

Teknik Analisis Kuantitatif dapat dikelompokkan dalam 4 kategori yaitu, teknik pemrograman matematika, teknik probabilistic, teknik jaringan kerja, dan teknik lainnya.

1. Teknik Pemrograman Matematika, umumnya berupa langkah-langkah matematis yang telah ditentukan dalam rangka memecahkan masalah.
2. Teknik Probabiliti, solusi yang mengandung unsure ketidakpastian, dengan kemungkinan adanya solusi alternative dan umumnya hasilnya bersifat probability.
3. Teknik Jaringan Kerja, menggambarkan system yang sedang dianalisis baik deterministic maupun probabilistic.
4. Teknik lainnya, teknik-teknik yang tidak mudah digolongkan. seperti Tenik Persediaan, teknik Linier dan nonlinier.

Studi Kasus  

Garuda Furniture merupakan suatu perusahaan yang memproduksi mabel dari kayu. Bahan baku utama yang digunakan berupa kayu jati dan kayu kamper. Untuk mendapatkan hasil yang baik, perusahaan ini menggunakan mesin multi guna yang dikendalikan computer. karena persaingan yang semakin tajam, manajemen perusahaan bermaksud meningkatkan efisiensi penggunaan sumber daya peoduksinya sehingga dapat mencapai hasil optimal. Terdapat 2 model yang dibuat A dan B. Jumlah kebutuhan bahan baku dan waktu mesin yang diperlukan untuk membuat setiap set mebel (kursi dan meja) serta kapasitas yang tersedia sebagai berikut .

Tabel 1 kebutuhan dan sumber daya produksi Garuda Furniture

Sumber Daya	Model A	Model B	Kapasitas
Kayu Kamer (Unit)	4	2	200
Kayu Jati (Unit)	2	2	100
Mesin (Jam-mesin)	1	3	90

Apabila keuntungan yang diperoleh untuk satu unit model A=$200 dan satu unit model B=$150 berapa unit setiap model harus dibuat agar memperoleh keuntungan yang maksimal.

Model Pemrograman Linier kasus perusahaan ini :

 Fungsi tujuan : maks. Z = 200 X₁ + 150 X₂

Batasan           : 4 X₁+ 2X₂ ≤ 120

                          2 X₁+2 X₂ ≤ 100

                          X₁ + 3 X₂ ≤ 90 dan X₁, X₂ ≥ 0

Dimana :

Z = total keuntungan (dolar)

A = mabel model A yang dibuat (unit)

B = mabel model B yang dibuat (unit)

Simbol x dan Z adalah variable

– Variable : Simbol untuk mewakili item yang dapat memiliki berbagai nilai.

$200 dan $150 adalah paramater

– Parameter : nilai-nilai konstan yang merupakan koefisien dari variable dependen [Z] (tergantung unit yang terjual) atau variable independen [x] (unit yang terjual)

Tujuan model pemrograman linier disini untuk menentukan berapa besar nilai X₁ dan X₂ sehingga dapat memperoleh nilai Z yang maksimum.

• Pemecahan dengan cara aljabar

FT : maks. Z = 200 X₁ + 150 X₂            …….……(0)

DP : 4 X₁+ 2X₂ + 1 S₁                        = 120   ………….(1)

        2 X₁+2 X₂      + 1 S₂        = 100   ……….…(2)

        X₁ + 3 X₂             + 1 S₃  = 90     ………….(3)

        dan X₁, X₂, S₁, S₂, S₃       ≥ 0      ………….(4)

Dalam model di atas 5 variabel yaitu X₁, X₂, S₁, S₂, S₃. Kelima variable tersebut dapat membentuk 10 kombinasi yang terdiri dari 2 pasangan variable yang berbeda. Terhadap kesepuluh kombinasi tersebut, dihitung nilai Z, dengan terlebih dulu memberikan nilai nol pada kedua variable pembentuk kombinasi itu. Tidak semua kombinasi memiliki nilai Z yang layak/fisibel, karena tidak memenuhi persyaratan persamaan keempat (non-negatif). Sehingga dapat diperoleh kombinasi yang memberikan nilai Z terbesar, dan variable keputusan yang diketahui. Contoh perhitungan untuk empat kombinasi pertama sebagai berikut :

 jika :

X₁ = 0, X₂ = 0 maka Z = 200 (0) + 150 (0) = 0

X₁ = 0, S₁ = 0  dari pers (1) diperoleh             X₂ = 120/2 = 60

                        dari pers (2) diperoleh             S₂ = 100 – 120 = -20

                        Z tidak fisibel karena S₂ tidak memenuhi persamaan (4)

X₁ = 0, S₂ = 0  dari pers (2) diperoleh             X₂ = 100/2 = 50

                        dari pers (3) diperoleh             S₃ = 90 – 150 = -60

                        Z tidak fisibel karena S₃ tidak memenuhi persamaan (4)

X₁ = 0, S₃ = 0  dari pers (3) diperoleh             X₂ = 90/3 = 30

                        dari pers (1) diperoleh             S₃ = 120 – 60 = 60

                        dari pers (2) diperoleh             S₂ = 100 – 60 = 40

                        maka Z = 200(0) + 150(30) = 4500

• Pemecahan dengan cara Grafik

Pemecahan persoalan dengan cara grafik dilakukan dengan cara membuat garis masing-masing persamaan batasan dalam suatu grafik. Apabila garis persamaan batasan sudah dibuat maka dapat diperoleh suatu daerah yang fisibel bagi nilai-nilai variabelnya, yaitu daerah yang memenuhi semua persamaan batasan yang ada. Dari daerah fisibel tersebut dicari titik-titik ekstrim yang memungkinkan diperolehnya niali optimal dari fungsi tujuan. Selanjutnya dengan memasukkan titik-titik ekstrim tersebut ke dalam fungsi tujuan akan diperoleh suatu titik ekstrim yang optimal.

Model pemrograman linear Garuda Furniture ditulis lagi berikut ini :

FT        : maks. Z = 200 X₁ + 150 X₂ …..(0) fungsi tujuan

DP       : 4 X₁+ 2X₂ ≤ 120                   …..(1) kendala kayu kamper

              2 X₁+2 X₂ ≤ 100                   …..(2) kendala kayu jati

              X₁ + 3 X₂ ≤ 90                      …..(3) kendala mesin

  dan X₁, X₂ ≥ 0                       …..(4) kendala non-negatif

pemecahan secara grafik diuraikan sebagai berikut :

• Fungsi batasan kayu kamper 4 X₁+ 2X₂ ≤ 120 dan kendala non-negatif X₁, X₂ ≥ 0 membentuk suatu daerah fisibel OAB. Daerah ini merupakan daerah dimana titik-titik kombinasi X₁ dan X₂ masih dapat dipenuhi oleh kapasitas kayu kamper sebesar 120 unit.

• Dengan dimasukkannya  fungsi batasan kayu jati 2 X₁+2 X₂ ≤ 100, kini daerah yang fisibel menjadi OAED. Daerah BDE menjadi tidak fisibel karena meskipun kapasitas kayu kamper mencukupi tetapi kapasitas kayu jati tidak mencukupi.

• Dengan penambahan batasan ketiga yaitu jam mesin  X₁ + 3 X₂ ≤ 90 maka daerah fisibel berubah menjadi OAHG. Dengan kata lain, daerah OAHG merupakan daerah dimana titik-titik yang merupakan kombinasi X₁ dan X₂ memenuhi ketiga kendala sumber daya.

Cacatan :

Untuk menggambarkan garis 4 X₁+ 2X₂ = 120 dapat dilakukan dengan mencari titik potong garis itu sumbu X₁ dan X₂. Jika X₁ = 0 maka X₂ = 60 dan jika X₂ = 0 maka X₁ = 30, diperoleh titik A (30;0) dan B (0;60) tarik garis lurus yang menghubungkan kedua titik itu sehingga diperoleh garis persamaan 4 X₁+ 2X₂ = 120. Titik H merupakan perpotongan garis fungsi kayu kamper dan dan garis fungsi mesin. Koordinat titik H dapat diperoleh dengan cara menyamakan koefisien salah satu variable, misalnya X₁, sehingga X₂ dapat dihitung. Selanjutnya dengan memasukkan kedalam salah satu persamaan maka nilai X₁ dapat diperoleh :

Kayu kamper   : 4 X₁+ 2X₂ = 120       |x1| 4 X₁+ 2X₂ = 120

Mesin              : X₁ + 3 X₂ = 90          |x4| 4X₁ + 12X₂ = 360

                                                                           -10 X₂ = -240

                                                                                 X₂ = 24

                          X₁ + 3 (24) = 90 maka X₁ = 18

Kesimpulan :

Sains Manajemen adalah penerapan ilmiah yang menggunakan pendekatan ilmiah untuk memecahkan masalah manajemen dalam rangka membantu Manajer untuk mengambil keputusan yang baik. Dengan adanya Sains Manajemen perusahaan dapat mengambil keputusan dalam bentuk aljabar atau dengan menggunakan grafik.