Pertemuan 2

PROGRAM LINIER

Pengantar

 Suatu model umum yang dapat digunakan dalam pemecahan masalah pengalokasian sumber-sumber yang terbatas secara optimal

   Menggunakan model matematis

Mencakup perencanaan kegiatan-kegiatan untuk mencapai suatu hasil yang optimal

Linier programming (pemrograman linier) merupakan sebuah model untuk mencari harga optimum (maksimum atau minimum) sebuah fungsi linier yang membuat beberapa variabel, dimana harga-harga variabel tersebut dibatasi oleh beberapa fungsi linier lainnya.

1

2

2.1 Model Linier

Model matematis perumusan masalah umum dalam pengalokasian sumber daya untuk berbagai kegiatan.

Ada 2 macam fungsi dalam model linier :

• Fungsi tujuan : fungsi yang menggambarkan sasaran/tujuan didalam permasalahan program linier yang berkaitan dengan pengaturan sumber daya secara optimal

• Fungsi pembatas : bentuk penyajian secara matematis batasan-batasan kapasitas yang tersedia yang akan dialokasikan secara optimal ke berbagai kegiatan

2.2 Bentuk umum model pemrograman linier

n

maximum (minimum) Z= ∑ Cj Xj

j

dengan kendala:

n

∑ aij xj ≥≤ bi , i = 1, …, m

j

xj ≥ 0 , j = 1, … , n                                     

3

Atau dapat dijabarkan sebagai berikut :

max (min) Z = c1x1 +c2x2 + … + cnxn

dengan kendala

a11x1 + a12x2 + … + a1nxn b1

a21x1 + a22x2 + … + a2nxn b2

…………..

…………..

am1x1 + am2x2 + … + amn xn bm

x1, x2, …, xn 0

4

Dimana:

xj = variabel keputusan

Z = c1x1 + c2x2 + … + cnxn

adalah fungsi tujuan

cj = bilangan riil, koefisien xj pada fungsi tujuan

aij = bilangan riil, koefisien xj pada kendala

bi = bilangan riil, harga batas kendala i

5

Contoh:Suatu pabrik sepatu “BATA” membuat 2 macam

sepatu, masing-masing dengan merk A dan B. Sepatu merk A dibuat dengan sol karet dan merk B dibuat dengan sol dari kulit. Untuk membuat sepatu perusahaan memiliki 3 macam mesin. Mesin I, khusus untuk membuat sol dari karet, mesin II khusus membuat sol dari kulit dan mesin III membuat bagian atas sepatu dan melakukan assembling bagian atas dengan sol. Setiap lusin sepatu merk A, mula-mula dikerjakan di mesin I selama 2 jam, kemudian tanpa melalui mesin II terus dikerjakan di mesin III selama 6 jam. Untuk sepatu merk B tak diproses di mesin I, tetapi langsung dikerjakan di mesin II selama 3 jam, kemudian di mesin III selama 5 jam. Jam kerja maksimum setiap hari untuk mesin I = 8 jam, mesin II = 15 jam, dan mesin III = 30 jam. Sumbangan terhadap keuntungan untuk setiap lusin sepatu merk A Rp. 300.000,- dan merk B Rp. 500.000,-Tentukan model matematis dari sistem diatas jika ingin ditentukan berapa lusin sebaiknya sepatu merk A dan merk B yang dibuat agar dapat memaksimumkan keuntungan.

6

mesin Jam kerja mesin Laba

Merk sepatu I II III Rp (000)

AB

2 - 6 - 3 5

300500

Kapasitas maksimum 8 15 30

7

Kasus diatas dapat disajikan dalam tabel :

8

Jawab :

Perumusan model sistem permsalahan diatas

1. Variabel Keputusan :

x = jumlah sepatu A yang diproduksi (lusin)

y = jumlah sepatu B yang diproduksi (lusin)

2. Fungsi tujuan : memaksimumkan keuntungan yang diperoleh perusahan. Maks Z = 300 x + 500 y

3. Fungsi kendala (pembatas) :

Mesin I : 2x ≤ 8

Mesin II : 3y ≤ 15

Mesin III : 6x + 5y ≤ 30

x, y ≥ 0 (non negatif constraint)

9

1. Asumsi kesebandingan ( proportionality )

a. Kontribusi setiap variabel keputusan terhadap fungsi tujuan adalah bersifat sebanding dengan nilai variabel keputusan

b. Kontribusi suatu variabel keputusan terhadap ruas kiri dari setiap pembatas juga sebanding dengan nilai variabel keputusan

2. Asumsi penambahan ( Additivity )

a. Kontribusi setiap variabel keputusan terhadap fungsi tujuan bersifat tidak bergantung pada nilai dari variabel keputusan yang lain

b. Kontribusi suatu variabel keputusan terhadap ruas kiri dari setiap pembatas bersifat tidak bergantung pada nilai dari variabel keputusan yang lain.

2.3 Asumsi dalam Model Program Linier

10

3. Asumsi pembagian ( divisibility )

Dalam persoalan program linier, variabel keputusan boleh diasumsikan berupa bilangan pecahan

4. Asumsi kepastian ( Certainty )

Setiap parameter , yaitu koefisien fungsi tujuan, ruas kanan, dan koefisien teknologis, diasumsikan dapat diketahui secara pasti

BAB III TEKNIK PEMECAHAN MODEL PROGRAM

LINIER

3.1 Metode Grafik

Metode grafik hanya dipergunakan untuk model linier programming yang memuat 2 variabel keputusan, dengan cara menggambarkan grafik garis-garis kendalanya.

11

Langkah-langkah Penyelesaian Metode Grafik :

1. Gambarkan sebuah bidang koordinat dengan kedua variable sebagai sumbu-sumbu koordinat.

2. Gambarkan fungsi kendala dengan menganggap kendalanya sebagai persamaan.

3. Tentukan daerah dalam bidang koordinat yang memenuhi semua kendala disebut daerah feasible / daerah layak (DF).

4. Tentukan koordinat semua titik sudut DF5. Hitung harga fungsi tujuan untuk semua titik

sudut, pilih harga yang optimal merupakan penyelesaian yang dicari.

12

13

Contoh : Penyelesaian kasus pabrik sepatu BATA dengan metode grafik

1. Gambarkan sebuah bidang koordinat dengan kedua variable sebagai sumbu-sumbu koordinat.

2. Menggambarkan fungsi kendala dalam sumbu kordinat . Anggap fungsi kendala sebagai persamaan.(1) 2x = 8

` x = 4….titik potong pd sumbu x (4,0)

4

2x ≤ 8

14

(2) 3y = 15

y = 5….titik potong pada sumbu y (5,0)

5

3y ≤ 15

(3) 6x + 5y = 30

6x + (5x0) = 30

6x = 30

x = 5 ……titik potong pada sumbu x (5,0)

15

(6x0) + 5y = 30

5y = 30

y = 6……titik potong pada sumbu y (0,6)6

5

6x + 5y≤30

16

3. Penentuan daerah feasible (daerah layak)

4 5

6

5 A B

C

D

Daerah feasibel (DF) adalah daerah yang memenuhi semua kondisi kendala, yaitu daerah ABCD

Z = 6x + 5y

A (0,5) Z = 0 + 25 = 25

B (5/6, 5) Z = 5 + 25 = 30

C (4, 6/5) Z = 24 + 6 = 30

D (4,0) Z = 24 + 0 = 2417

4. Penentuan titik sudut daerah feasibel (DF)

A (0,5)

B (5/6, 5)

C (4, 6/5)

D (4,0)

5. Menghitung harga fungsi tujuan untuk semua titik sudut daerah feasibel

?

?

18

Kesimpulan :

Tingkat produksi optimum tercapai pada titik B (5/6,5)

yang memberikan keuntungan maksimum Z =27,5

x = jumlah produksi sepatu A = 5/6 lusin

Y = jumlah produksi sepatu B = 5 lusin

dengan keuntungan tercapai Rp.27.500,00