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