DASAR PROGRAMA LINIER

Pengertian Umum

Suatu cara untuk menyelesaikan persoalan pengalokasian sumber-sumber yang terbatas di antara beberapa aktivitas yang bersaing, dengan cara yang terbaik yang mungkin dilakukan.

Contoh Situasi :

- persoalan pengalokasian fasilitas produksi

- penjadwalan produksi

- pemilihan pola pengiriman, dll

Menggunakan model matematis untuk menjelaskan persoalan yang dihadapi.

Linier = Seluruh fungsi matematis adalah fungsi linier

Programa = Perencanaan

Programa linier :

Perencanaan aktivitas-aktitas untuk memperoleh hasil yang optimum, yaitu suatu hasil yang mencapai tujuan terbaik diantara alternatif yang fisibel.

Contoh Ilustrasi :

PT.Sayang Anak memproduksi dua jenis mainan yang terbuat dari kayu, berupa boneka dan kereta api. Pengerjaan Boneka dan Kereta Api memerlukandua kelompok tenaga kerja (tukang kayu dan tukang poles), ada 100 jam poles/minggu dan 80 jam per kayu/minggu.

Boneka

-dijual dengan harga Rp.27000/lusin

-Biaya material Rp 10000/lusin, biaya tenaga kerja Rp.14000/lusin

-2 jam poles dan 1 jam pek kayu/lusin

-kebutuhan tidak lebih 40 lusin/minggu

Kereta Api

-dijual dengan harga Rp.21000/lusin

-Biaya material Rp 9000/lusin, biaya tenaga kerja Rp.10000/lusin

-1 jam poles dan 1 jam pek kayu/lusin

-kebutuhan kereta api tak terbatas

Berapa lusin jenis mainan masing-masing dibuat untuk mendapatkan keuntungan yang maksimum ?

Dalam membangun model dari formulasi persoalan di atas akan digunakan karakteristik-karakteristik yang biasa digunakan dalam persoalan programa linier, yaitu :

a. Variabel Keputusan

Adalah variabel yang menguraikan secara lengkap keputusan-keputusan yang akan dibuat. Dalam persoalan ini, variabel keputusan akan menentukan berapa banyak boneka dan kereta api yang harus dibuat setiap minggunya.

Misalkan :

x₁ = banyaknya boneka yang dibuat setiap minggu

x₂ = banyaknya kereta api yg dibuat setiap minggu.

b. Fungsi Tujuan

Merupakan fungsi dari variabel keputusan yang akan dimaksimumkan (untuk pendapatan dan keuntungan) atau diminimumkan (untuk ongkos).

Pada persoalan ini akan dimaksimumkan (pendapatan /minggu)-ongkos material/minggu)-(ongkos tenaga kerja/minggu).

Pendapatkan dan ongkos-ongkos ini dapat diekspresikan dengan menggunakan variabel keputusan x₁ dan x_2. Pendapatan dan ongkos dlm ribuan

Pendapatan/minggu : 27 x₁ + 21 x₂

Ongkos material/minggu : 10 x₁ + 9 x₂

Ongkos tenaga kerja/minggu : 14 x₁ + 10 x₂

Sehingga yang akan dimaksimumkan :

(27 x₁ + 21 x₂)-(10 x₁ + 9 x₂)-(14x₁+10 x₂)=3x₁+2x₂

Jadi untuk menyatakan nilai fungsi tujuan akan digunakan variabel z, sehingga :

Z = 3 x₁ + 2 x₂

c. Pembatas

Merupakan kendala yang dihadapi, sehingga kita tidak bisa menentukan harga-harga variabel keputusan secara sembarang.

Pada persoalan diatas, ada 3 pembatas :

Pembatas 1 : Setiap minggu tidak lebih dari 100 jam

pemolesan yang dapat digunakan.

Pembatas 2 : Setiap minggu tidak lebih dari 80 jam

waktu pengerjaan yg boleh digunakan.

Pembatas 3 : Tidak dari 40 lusin boneka yang boleh

dibuat (karena permintaan)

Selanjutnya ekspresikan pembatas-pembatas tsb ke dalam x₁ dan x_2, sbb :

2 x₁ + x₂ ≤ 100

x₁ + x₂ ≤ 80

x₁ ≤ 40

Koefisien dari variabel keputusan pada pembatas disebut koefisien teknologis, bilangan yang berada di sisi kanan pembatas disebut ruas kanan pembatas

d. Pembatas Tanda

Pembatas yang menyatakan apakah variabel keputusan diasumsikan hanya berharga nonegatif.

X₁ ≥ 0

X₂ ≥ 0

Dengan demikian, formulasi lengkap dari persoalan PT Sayang Anak adalah :

Maksimumkan :

Z = 3 x₁ + 2 x₂

Berdasarkan :

2 x₁ + x₂ ≤ 100

x₁ + x₂ ≤ 80

X₁ ≤ 40

X₁ ≥ 0

X₂ ≥ 0

Contoh Ilustrasi 2 :

PT. Indah Gelas adalah suatu perusahaan yang memproduksi kaca berkualitas tinggi untuk digunakan sebagai jendela dan pintu. Perusahaan ini mempunyai tiga buah pabrik, yaitu :

Pabrik 1 ; membuat bingkai aluminium

Pabrik 2 ; membuat bingkai kayu

Pabrik 3 ; memproduksi kaca dan merakit produk

Perusahaan mendapat pesanan 2 macam produk baru yang potensial, yaitu :

-pintu kaca setinggi 8 kaki dg bingkai aluminium (produk 1)

-jendela kaca 4 x 6 kaki dg bingkai kayu (produk 2)

Kepala bagian pemasaran telah menyimpulkan bahwa perusahaan harus dapat menjual kedua produk tsb sebanyak-banyaknya, yaitu sejumlah yang dibuat sesuai dengan kapasitas yang ada.

Berapa banyak masing-masing produk harus dibuat sehingga diperoleh keuntungan terbaik?

Untuk menyelesaikan persoalan diatas, terlebih dahulu dicari data mengenai :

1. Persentase kapasitas produksi masing-masing pabrik yg dapat digunakan untuk kedua macam produk tsb.
2. Prosentase kapasitas yang diperlukan oleh masing-masing produk untuk setiap unit yang diproduksi per menit.
3. Keuntungan per unit untuk masing-masing produk.

Pabrik	Penggunaan per unit		Kapasitas
	Produk 1	Produk 2
1	1	0	4
2	0	2	12
3	3	2	18
z	$3	$5

Karena kapasitas yg telah digunakan oleh suatu produk di pabrik 3 menyebabkan produk lain tidak dpt menggunakannya, persoalan ini dikenal sebagai persoalan programa linier dengan tipe campuran produk atau product mix

Untuk memformulasikan model matematis dari persoalan ini, maka :

a. Variabel Keputusan

x₁ = jumlah unit dari produk 1 yang diproduksi per menit

x₂ = jumlah unit dari produk 2 yang diproduksi per menit

b. Fungsi Tujuan

Z = 3 x₁ + 5 x₂

c. Pembatas & Pembatas Tanda

Kapasitas pabrik yang diekspresikan ke dalam x₁ dan x_2, sbb :

x₁ ≤ 4

2x₂ ≤ 12

3x₁ + 2x₂ ≤ 18

X₁ ≥ 0

X₂ ≥ 0

Sebagai kesimpulan persoalan diatas dinyatakan secara matematis :

Maksimumkan : Z = 3 x₁ + 5 x₂

Berdasarkan :

x₁ ≤ 4

2x₂ ≤ 12

3x₁ + 2x₂ ≤ 18

x₁ ≥ 0

x₂ ≥ 0

Dari ilustrasi diatas dapat ditarik kesimpulan mengenai pengertian persoalan programa linier adalah suatu persoalan optimasi dimana kita melakukan hal-hal berikut :

1. Kita berusaha memaksimumkan atau meminimumkan suatu fungsi linier dari variabel-variabel keputusan yang disebut fungsi tujuan.

2. Harga/besaran dari variabel-variabel keputusan itu harus memenuhi suatu set pembatas. Setiap pembatas harus merupakan persamaan linier atau ketidak samaan linier.

3. Suatu pembatas tanda dikaitkan dengan setiap variabel. Untuk setiap variabel x_i, pembatasan tanda akan menunjukkan apakah x_i harus nonnegatif (x_i ≥ 0) atau x_i tidak terbatas dalam tanda.

MODEL PROGRAMA LINIER

Seperti contoh persoalan PT Indah Gelas terdapat tiga buah sumber terbatas (yaitu kapasitas produksi ketiga pabrik) yang harus dialokasikan diantara dua aktifitas yang bersaing (yaitu dua macam produk baru yang dipesan).

Sekarang, bagaimana jika ada sejumlah (katakan m buah) sumber yang terbatas yang harus dialokasikan diantara sejumlah (katakan n buah) aktifitas yang bersaing?

Model Umum :

Aktifitas	Penggunaan per unit				Kapasitas
Sumber	1	2	...	n
1	A11	A12	...	A1n	B1
2	A21	A22	...		B2
.			.		.
.			.		.
.			.		.
M	Am1	Am2	...	Amn	Bm
z/unit	C1	C2	...	cn
Tingkat	X1	X2	...	xn

Formulasi model matematis dari persoalan pengalokasian sumber-sumber pada aktifitas-aktifitas sebagai berikut :

Maksimumkan : Z = c1 x1 + c2 x2 + …+ cn xn

Berdasarkan pembatas :

a₁₁ x₁ + a₁₂ x₂ + … + a_1n x_n ≤ b₁

a₂₁ x₁ + a₂₂ x₂ + … + a_2n x_n ≤ b₂

_.

_.

_.

a_m1 x₁ + a_m2 x₂ + … + a_mn x_n ≤ b_m

x₁ ≥ 0, x₂ ≥ 0, … , x_n ≥ 0,

Formulasi diatas dinamakan sebagai bentuk standar dari persoalan programa linier, dan setiap situasi yang formulasi matematisnya memenuhi ini adalah persoalan programa linier.

Istilah yg lebih umum dari programa linier ini adalah sebagai berikut :

a. Fungsi yang dimaksimumkan , yaitu c₁ x₁ + c₂ x₂ + …+ c_n x_n , disebut fungsi tujuan _.

b. Pembatas-pembatas atau konstrain.

c. Sebanyak m buah konstrain pertama sering disebut konstrain fungsional atau pembatas teknologis.

d. Pembatas x_j ≥ 0 disebut sebagai konstrain nonnegatif

e. Variabel x_j adalah variabel keputusan.

f. Konstanta-konstanta aij, bi, cj adalah parameter-parameter model.

Selain model programa linier dg bentuk seperti yg telah diformulasikan diatas, ada pula model programa linier dengan bentuk agak lain, seperti :

1. Fungsi tujuan bukan memaksimumkan, melainkan meminimumkan.

Contoh : Minimumkan z = c₁ x₁ + c₂ x₂ + …+ c_n x_n

2. Beberapa konstrain fungsionalnya mempunyai ketidaksamaan lebih besar atau sama dengan. Contoh :

Untuk beberapa harga i

3. Beberapa konstrain fungsionalnya mempunyai bentuk persamaan.

Contoh :

Untuk beberapa harga i

ASUMSI DALAM PROGRAMA LINIER

Dalam menggunakan model programa linier, diperlukan beberapa asumsi sebagai berikut :

1. Asumsi Kesebandingan (proportionality)

2. Asumsi penambahan (addivity)

3. Asumsi pembagian (divisibility)

4. Asumsi kepastian (certainty)

Asumsi Kesebandingan

a. Kontribusi setiap variabel keputusan terhadap fungsi tujuan adalah sebanding dengan nilai variabel keputusan. Contoh : kita membuat 4 lusin boneka, maka kontribusinya terhadap fungsi tujuan adalah 4 kali kontribusi setiap lusin boneka. (atau 4 x Rp.3.000 = Rp. 12.000)

b. Kontribusi suatu variabel keputusan terhadap ruas kiri dari setiap pembatas juga sebanding dengan nilai variabel keputusan. Contoh : jika kita membuat 4 lusin boneka maka diperlukan 4 kali waktu pemolesan yang dibutuhkan oleh setiap lusin boneka. (atau 4 x 2 jam = 8 jam)

Asumsi Penambahan

a. Kontribusi setiap variabel keputusan terhadap fungsi tujuan bersifat tidak tergantung pada nilai dari variabel keputusan yang lain. Contoh : berapapun nilai x2 pembuatan sejumlah x1 boneka akan selalu berkontribusi sebesar Rp.3.000 terhadap fungsi tujuan.

b. Kontribusi suatu variabel keputusan terhadap ruas kiri setiap pembatas bersifat tidak tergantung pada nilai dari variabel keputusan yang lain. Contoh : Berapun nilai x1, pembuatan sejumlah x2 kereta api akan memerlukan sebanyak x2 jam pemolesan dan x2 jam pekerjaan kayu.

Asumsi Pembagian

Dalam persoalan programa linier, variabel keputusan boleh diasumsikan berupa bilangan pecahan.

Asumsi Kepastian

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

Suatu masalah pemrograman hanya dpt dirumuskan ke dalam persoalan programa linier apabila asumsi-asumsi diatas terpenuhi.

Bentuk Kanonik dalam Metode Simplex

1. Persamaan matematis suatu program linier adalah sebagai berikut :

Minimasi :

Z = 6x₁ + 7,5x₂

Dengan pembatas :

7x₁ + 3x₂ 210

6x₁ + 12x₂ 180

4x₂ 120

x₁, x₂ 0

Carilah Harga x₁, x₂!

Ubah ke bentuk kanonik

Z – 6x₁ – 7,5x₂ – 0S₁ – 0S₂ – 0S₃ = 0

2x₁ + 5x₂ – S₁ = 200

6x₁ + 12x₂ – S₂ = 360

4x₂ – S₃ = 120

Basis	Z	x1	x2	S1	S2	S3	NK
Z	1	-3	-2	0	0	0
S1	0	2	5	-1	0	0	200
S2	0	6	12	0	-1	0	360
S3	0	0	4	0	0	-1	120

Karena NBV semuanya sudah berkoefisien negatif maka solusinya x₁ , x₂ =0 dengan solusi minimum yaitu Z =0.
------------------------------------------------------------------------------------------------------

2. PT Unilever bermaksud membuat 2 jenis sabun, yakni sabun bubuk dan sabun batang. Untuk itu dibutuhkan 2 macam zat kimia , yakni A dan B. Jumlah zat kimia yang tersedia adalah A= 200 kg dan B= 360 kg.

Untuk membuat 1 kg sabun bubuk diperlukan 2 kg A dan 6 kg B. Untuk membuat 1 kg sabun bubuk diperlukan 5 kg A dan 3 kg B. Bila keuntungan yang akan diperoleh setiap membuat 1 kg sabun bubuk = $3 dan sabun batang = $2, berapa kg jumlah sabun bubuk dan sabun batang yang sebaiknya dibuat?

Jawaban :

Variabel :

x1 = sabun bubuk

x2 = sabun batang

Fungsi Tujuan :

Z = 3x₁ + 2x₂ [ Maksimumkan ]

Fungsi Pembatas :

2x₁ + 5x₂ 200

6x₁ + 3x₂ 360

Ubah ke bentuk kanonik

Z – 3x₁ – 2x₂ + 0S₁ + 0S₂ = 0

2x₁ + 5x₂ + S₁ = 200

6x₁ + 3x₂ + S₂ = 360

(* Agar optimum maka NBV harus memiliki koefisien non negatif.

Tabel Iterasi :

Iterasi ke 0

Basis	Z	x1	x2	S1	S2	NK	Rasio
Z	1	-3	-2	0	0	0
S1	0	2	5	1	0	200	100
S2	0	6	3	0	1	360	60

Pilih NBV yang bernilai paling negative di baris 0, lalu cari rasio yang terkecil untuk dijadikan elemen tumpuan.

X₁ terpilih karena koefisiennya -3 dan baris 2 terpilih dengan X₁ = 6 karena rasionya memiliki nilai terkecil.

Iterasi ke 1

Lakukan ERO untuk membuat elemen tumpuan bernilai 1 dan nilai lain pada baris tumpuan tersebut menjadi 0.

Operasi untuk x₁

0	6	3	0	1	360	|/6|
0	1	1/2	0	1/6	60

Operasi untuk Z

1	-3	-2	0	0	0
0	3	1 1/2	0	1/2	180	+
1	0	-1/2	0	1/2	180

Operasi untuk S₁

0	2	5	1	0	200
0	2	1	0	2/6	120	-
0	0	4	1	-2/6	80

Basis	Z	x1	x2	S1	S2	NK	Rasio
Z	1	0	-1/2	0	1/2	180
S1	0	0	4	1	-2/6	80	20
x1	0	1	1/2	0	1/6	60	120

Solusi x₁ = 60 dan x₂ = 0 belum optimum karena masih ada koefisien negatif pada NBV yaitu x₂.

Maka ulangi step diatas.


Operasi untuk x₂

0	0	4	1	-2/6	80	|/4|
0	0	1	1/4	-1/12	20

Operasi untuk Z

1	0	-1/2	0	1/2	180
0	0	1/2	1/8	-1/24	10	+
1	0	0	1/8	11/24	190

Operasi untuk x₁

0	1	1/2	0	1/6	60
0	0	1/2	1/8	-1/24	10	-
0	1	0	-1/8	5/24	50

Iterasi ke 2

Basis	Z	x1	x2	S1	S2	NK
Z	1	0	0	1/8	11/24	190
x2	0	0	1	1/4	-1/12	20
x1	0	1	0	-1/8	5/24	50

Solusi optimum didapat dengan x₁= 50 dan x₂ = 20 sehingga keuntungannya menjadi maksimum yaitu $190.

.: Sehingga Barang yang harus dibuat adalah 50 kg sabun bubuk dan 20 kg sabun batang.