ayaaax: analisis sensitivitas

MASALAH PROGRAM LINEAR

ANALISIS SENSITIVITAS

Makalah ini disusun guna memenuhi tugas akhir mata kuliah Program Linear

Dosen Pembimbing : Heru Kurniawan, M.Pd.

Oleh :

1. Bambang Trikuntoyo (VI A / 092143436)

2. Ngusman (VI C / 092143502)

3. Noer Khayati (VI C / 092143504)

4. Nopiman (VI C / 092143506)

5. Rachmawati (VI C / 092143522)

PROGRAM STUDI PENDIDIKAN MATEMATIKA

FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN

UNIVERSITAS MUHAMMADIYAH PURWOREJO

2012

KATA PENGANTAR

Puji syukur penulis panjatkan kepada Allah SWT atas limpahan rahmat, taufik, dan hidayah-Nya sehingga penulis dapat menyelesaikan makalah yang berjudul “Masalah Program Linear Analisis Sensitivitas” dengan tanpa aral suatu apapun.

Dalam penyusunan makalah ini, penulis tidak bekerja sendiri. Untuk itu pada kesempatan ini penulis ingin mengucapkan terima kasih kepada:

1. Bapak Heru Kurniawan, M.Pd selaku dosen pembimbing mata kuliah Program Linear.

2. Teman-teman yang telah bekerjasama dalam menyelesaikan makalah ini.

3. Semua pihak yang telah membantu.

Namun, karena keterbatasan dari penulis, maka dalam makalah ini masih banyak terdapat kekurangan dan masih jauh dari sempurna. Untuk itu penulis dengan segala kerendahan hati menerima kritik dan saran yang bersifat membangun demi kesempurnaan makalah ini. Semoga makalah ini dapat bermanfaat bagi pembaca.

Purworejo, Juni 2012

Penulis

DAFTAR ISI

Halaman Judul.................................................................................................. i

Kata Pengantar................................................................................................. ii

Daftar Isi.......................................................................................................... iii

BAB I PROGRAM LINEAR

A. Pendahuluan ..................................................................................... 1

B. Sejarah Program Linear..................................................................... 1

C. Pengertian Program Linear................................................................ 2

D. Istilah-istilah dalam Program Linear................................................. 3

E. Kaidah Program Linear..................................................................... 4

F. Contoh Masalah Program Linear....................................................... 6

BAB II ANALISIS SENSITIVITAS

A. Pendahuluan...................................................................................... 9

B. Analisis Sensitivitas........................................................................... 10

Daftar Pustaka

BAB I

PROGRAM LINEAR

A. Pendahuluan

Program Linear adalah suatu model dalam Operations Research (OR) atau Riset Operasional. Operasional Riset adalah metode yang merupakan alat untuk pemecahan masalah optimasi (mamaksimalkan atau meminimalkan) suatu fungsi sasaran dengan syarat tertentu yang harus dipenuhi. Banyak permasalahan yang pemecahannya memerlukan riset operasi dalam hal ini program linear. Program linear merupakan satu diantara metode dalam hal Operasional Riset yang digunakan dibidang industry, transportasi, perdagangan, perkebunan dll. Persoalan dapat menyangkut biaya pemasaran produk, perencanaan produksi, persoalan pencampuran maupun persoalan transportasi.

Dalam penyelesaian program linear, banyak hal yang dapaat terjadi. Dapat sajaa untuk mendapatkan nilai optimum yang sama, digunakan berbagai alternative pilihan. Dapat dikataan penyelesaian umum lebih dari satu. Kasus lain yang dapat terjadi adalah kelebihan pembatas, tidak ada penyelesaian yang layak, penyelesaian tak terbatas dan kasus-kasus yang lain.

B. Sejarah Program Linear

Seorang matematikawan Rusia L.V. Kantorovich pada tahun 1939 berhasil menemukan pemecahan masalah yang berkaitan dengan program linear. Pada waktu itu Kantorovich bekerja untuk kantor pemerintahan Uni Soviet. Ia diberi tugas untuk mengoptimalkan produksi pada industry plywood. Ia kemudian muncul dengan teknik matematis yang disebut pemrograman linear.

Matematikawan Amerika, George B. Dantzig secara independen juga mengembangkan pemecahan masalah tersebut, dimana hasil karyanya pada masalah tersebut pertama kali dipublikasikan pada tahun 1947. Selanjutnya, sebuah teknik yang lebih cepat, tetapi lebih rumit, yang cocok untuk memecahkan masalah program linear dengan ratusan atau bahkan ribuaan variabel, dikembangkan oleh matematikawan Bell Laboratories, Naranda Karmarkar pada tahun 1983. Program linear sangat penting khususnya dalam erencanaan militer dan industry.

C. Pengertian Program Linear

Program linear adalah suatu teknis matematika yang dirancang untuk membantu merancang dan membuat keputusan dalam mengalokasikan sumber daya yang terbatas untuk mencapai tujuan. Tujuan tersebut terkait dengan masalah memaksimalkan atau meminimalkan suatu model. Bentuk fungsi sasaran dan syarat yang berbeda menumbuhkan Operasional Riset yang berbeda pula diantaranya: Mathematical Programming, Dynamic Programming, Network Analisis, Markov Chairv, Games Theory, Non Linear Programming, dll.

Program linear merupakan terapan dari aljabar linear. Masalah program linear dipecahkan melalui beberapa tahap, sebagai barikut:

1. Memahami masalah dibidang yang bersangkutan,

2. Menyusun model matematika,

3. Menyelesaikan model matematika (mencari jawaban model), dan

4. Menafsirkan jawaban model menjadi jawaban atas masalah yang nyata.

Masalah optimasi tidak semuanya dapat diselesaikan dengan metode program linear. Ada beberapa prinsip yang harus ada agar masalah optimasi dapat diselesaikan dengan program linear.

1. Ada sasaran

Sasaran berupa fungsi tujuan atau fungsi objektif yang akan dicari nilai optimalnya (maksimum/minimum). Penyelesaian masalah mengarah pada pencapaian tujuan memaksimalkan atau meminimalkan.

2. Ada tindakan alternative

Nilai fungsi tujuan dapat diperoleh dengan alternative antara lain memberikan nilai optimal. Fungsi tujuan yang hanya dapat dilakukan dengan satu cara tidak memerlukan program linear.

3. Ada keterbatasan sumber daya

Sumber daya atau masukan dapat berupa waktu, tenaga, biaya, bahan dan sebagainya. Pembatasan sumber daya disebut kendala pembatas.

4. Masalah dapat dituangkan dalam model matematika yang memuat fungsi tujuan dan kendala.

Fungsi tujuan berupa fungsi linear dan kendala berupa persamaan atau pertidaksamaan linear.

5. Ada keterkaitan antara variabel yang membentuk fungsi, tujuan dan kendala yang artinya perubahan pada peubah yang satu akan mempengaruhi nilai peubah yang lain.

D. Istilah-istilah dalam Program Linear

Dalam mempaelajari program linear, kita akan sering menjumpai istilah-istilah, sebagai berikut:

1. Variabel Keputusan (decision variable)

Variabel keputusan berupa kumpulan variabel yang akan dicari/ditentukan nilainya, diberi simbol U, V, W, X dan sebagainya atau X_h, X₂, X₃ dan sebagainya.

2. Nilai Ruas kanan (right hand side value)

Nilai ruas kanan yaitu nilai-nilai yang menunjukan jumlah (kuantitas/kapasitas) ketersediaan sumber daya untuk dimanfaatkan, dinyatakan dengan symbol b_i ( i = banyaknya kendala).

3. Variabel Tambahan (slack variable/surplus variable)

Variabel tambahan yaitu variabel yang menyatakan penyimpangan positif atau negative dari nilai ruas kanan, diberi symbol S₁, S₂, S₃,…

4. Koefisien Tehnis

Diberi symbol aij, menyatakan setiap unit penggunaan b_i dari setiap varibel.

5. Z

Z adalah nilai fungsi tujuan yang belum diketahui dan akan dicari nilai optimumnya (dicari sebesar mungkin untuk masalah maksimum dan sekecil mungkin untuk masalah minimum).

6. Koefisien fungsi tujuan (koefisien kontribusi)

Koefisien kontribusi adalah nilai yang menyatakan kontribusi/sumbangan per unit Z untuk setiap X_j dengan symbol C_j.

E. Kaidah Program Linear

1. Prinsip Program Linear

Program linear adalah suatu cara yang bertujuan untuk menentukan himpunan penyelesaian bagi suatu system pertidaksamaan.

a) Prinsip 1: dalam program linear, setiap pernyataan yang harus dipenuhi oleh variabel-variabel seperti x dan y dinyatakan dalam bentuk pertidaksamaan. Misalnya dalam suatu masalah diketahui bahwa jumlah 2x dan 3y tidak boleh kurang dari 12. Pernyataan ini berarti 2x + 3y sama dengan 12 atau lebih dari 12, dan dinyatakan dalam bentuk ertidaksamaan sebagai 2x + 3y ≥ 12.

b) Prinsip 2 : dalam setiap pertidaksamaan akan dibentuk suatu persamaan yang berkaitan. Misalnya, dari pertidaksamaan 2x + 3y ≥ 12, dibentuk persamaan 2x + 3y = 12.

c) Prinsip 3 : persamaan yang dibentuk digunakan untuk melukiskan garis bagi penyelesaian pertidaksamaan.

2x +3y = 12
x	0	3	6
y	4	0	0

d) Prinsip 4 : arsilah daerah yang memenuhi pertidaksamaan 2x +3y ≥12 dengan menggunakan titik selidik, atau berpatokan pada table diatas.

e) Prinsip 5 : koordinat-koordinat setiap titik dalam daerah arsiran mewakili suatu system pertidaksamaan. Misalnya titik (1,4), (4,3), (6,2) dan seterusnya.

Uraian diatas menjelaskan prinsip program linear dan kaidah penggunaannya.

2. Model Matematika

Model matematika berupa ungkapan suatu masalah dalam bahasa matematika. Untuk dapat menyusun model matematika diperlukan kepekaan dalam mengkaitkan berbagai informasi yang diketahui. Langkah-langah dalam menyusun model matematika adalah sebagai berikut:

a) Menentukan tipe masalah

Tipe masalah berupa masalah maksimum atau minimum.

b) Mendefinisikan variabel kputusan

Setiap variabel harus mempunyai koefisien kontribusi. Bilangan dari koefisien kontribusi digunakan untuk menentukan tipe masalah dan untuk membantu mengidentifikasi variabel keputusan.

c) Merumuskan fungsi tujuab dengan mengkombinasikan informasi tentang tipe masalah dan variabel keputusan ke fungsi tujuan.

d) Merumuskan kendala dapat dilakukan dengan dua pedekatan dasar.

1) Pendekatan ruas kanan

Nilai bi dalam daftar informasi merupakan besar maksimum atau minimum dari sumber daya yang tersedia. Jika kuantitas dari sumber daya maksimum atau minimum ditempatkan, variabel keputusan dihubungkan ke bi dapat ditentukan dengan koefisien tehnis yang terkait. Arah ketidaksamaan didasarkan pada nilai bj maksimum atau minimum sumber daya.

2) Pendekatan ruas kiri

Pada pendekatan ini, koefisien tehnis didaftar dalam table atau baris-baris yang dilengkapi dengan melettakkan semua nilai sebagai koefisien tehnis dan daftarnya dalam baris dan kolom.

Dalam merumuskan kendala tidak boleh lupa pada satu hal bahwa variabel keputusan biasanya mewakili banyaknya unit dari beberapa produksi atau sesuatu untuk diproduksi atau suatu pelayanan. Oleh karena itu variabel ini haruslah non negative.

F. Contoh Masalah Program Linear

Petani mempunyai 16 ha tanah yang dapat ditanami padi atau jagung. Sarana produknya ialah tanah , modal dan air yang ketiganya terbatas untuk memperoleh 1 kuintal padi dibutuhkan tanah seluas

ha, modal Rp.50.000.- dan irigasi harus membuka saluran 12 jam . sedangakan untuk memperoleh 1 kuintal jaging diperlukan tanah seluas

ha, dengan modal Rp.30.000,- tanpa harus membuka saluran air. Pada musim itu persediaan air yang ada hanya 360 jam, sedangkan modal yang tersedia Rp.1.200.000,-. Petani tersebiut memiliki lahan seluas 16 ha. Tiap 1 kuintal padi memberikan keuntungan Rp.50.000.- dan jagung member keuntungan Rp.20.000.-. petani ingin menentukan jumlah produksi jagung dan padi agar diperoleh keuntungan maksimal.

Dari masalah tersebut hal yang harus dilakukan adalah menyusun model matematikanya. Akan kita ikuti langkah-langakah penyusunan model matematika diatas.

a) tipe masalahnya adalah tipe maksimum.

Misal tipe besarnya laba Z rupiah.

b) Keuntungan dalam masalah ini ditentukan oleh banyaknya padi dan banyaknya jagung, sehingga banyaknya padi dan banyaknya jagung merupakan variable keputusan. Misalkan produksi padi x kuintal dan untuk jumlah produksi jagung y kuintal.

c) Dari informasi bahwa setiap kuintal padi memberikan keuntungan Rp.50.000,- dan tiap kuintal jagung memberikan keuntungan Rp.20.000,- diperolh hubungan Z = 50.000x+ 20.000y dengan tujuan menentukan nilai x dan y sehingga diperoleh Z maksimal.

d) Kendala keterbatasan dana

Produksi tiap kuintal padi memerliukan lahan ha sehingga untuk seluruh produksi diperlukan lahan seluas

. produksi tiap kuintal jagung memerlukan lahan seluas

sehingga seluruh produksi diperlukan lahan seluas

. Kapasitas lahan yang tersedia adalah 16 ha, artinya lahan yang dapat dipergunakan maksimum 16 ha. Dari informasi tersebut diperoleh hubungan

Produksi tiap kuintal padi memerlukan modal Rp 50.000, sehingga untuk seluruh produksi diperlukan modal 50.000x. produksi tiap kuintal jagung memerlukan modal 30.000y. kapasitas modal yang tersedia adalah Rp 1.200.000 artinya modal yang dapat digunakan untuk produksi maksimal Rp 1.200.000. dari informasi tersebut diperoleh hubungan 50.000x + 30.000y ≤ 1.200.000

Persediaan irigasi sebanyak 360 jam hanya digunakan untuk memproduksi padi saja. Tiap kuintal padi memerlukan membuka saluran air selama 12 jam. Dari informasi diperoleh hubungan 12x ≤ 360.

e) Persyaratan non negative

Banyaknya produksi tidk mungkin negative jadi x ≥ 0, y ≥ 0

Dari langkah a sampai e selanjutnya disusun model matematika masalah tersebut. Model matematika dari masalah petani tersebut dapat ditulis sebagai berikut.

Maks (1) Z = 50.000x+20.000y………(fungsi tujuan)

Harus memenuhi :

(2)

……………(kendala kapasitas lahan)

(3) 50.000x + 30.000y ≤ 1.200.000……. (kendala modal)

(4) 12x ≤ 36……….(kendala waktu)

(5) x ≥ 0, y ≥0………….(pernyataan non negative)

Dalam masalah ini x dan y harus bilangan rasional.

Secara umum, masalah program linear dapat dinyatakan sebagai berikut :

Diberikan sebanyak m pertidaksamaan atau persamaan linear dengan n variabel, akan ditentukan nilai-nilai non negative dari variabel-variabeltersebut yang memenuhi syarat-syarat dan mengoptimalkan (memaksimalkan atau meminimalkan) suatu fungsi linear dari variabel-variabel tersebut.

Secara matematik dapat dinyatakan sebagai berikut :

Terdapat m pertidaksamaan/persamaan dalam n variabel dengan m ≥ n atau m < n dalam bentuk.

a_i1x₁ + a_i2 + … + a_in_xn ≥ = ≤ b_i I = 1,2,…,m (1)

Dengan hanya salah satu tanda ≥ = atau ≤ yang benar

Akan dicari nilai xj ≥ 0, j = 1,2,…,n (2)

Sehingga Z = c₁x₁ + c₂x₂ + … + c_nx_n (3)

Mencapai nilai optimal aij, bi dan cj adalah konstanta. Vector X = (P₁, P₂,…, P_n) yang memenuhi persamaan (1) dan (2) disebut penyelesaian fisibel.

BAB II

ANALISIS SENSITIVITAS

A. Pendahuluan

Dalam kehidupan sehari-hari, tidak ada yang pernah stabil atau tetap. Yang tetap ya ketidaktetapan itu. Misalnya, minyak tanah yang dulu bebas diperoleh, sekarang terbatas. Harga BBM dari bulan ke bulan mengalami peningkatan, dan suatu ketika turun lagi. Artinya, kadangkala dalam perencanaan produksi ataupun pemasaran, apa yang telah direncanakan suatu ketika tidak lagi sesuai dengan keadaan di lapangan. Jika suatu masalah program linear sudah memiliki penyelesaian optimal, apakah ketika terjadi perubahan, program tersebut tidak dipakai lagi? Atau bahkan harus merencanakan dari awal lagi

Nah, hal semacam ini yang akan dibahas pada bab inni, yaitu ketika terjadi perubahan pada berbagai unsur produksi, apakah yang akan dilakukan. Bab ini akan membahas mengenai perubahan apa saja yang dapat sesudah program optimal dan bagaimana mengatasinya.

Setelah mempelajari bab ini, Anda diharapkan dapat membuat analisis sesudah program optimal atau analisis sensitivitas. Sebagai penjabaran tujuan tersebut Anda diharapkan dapat:

1. Menjelaskan manfaat analisis sensitivitas

2. Menentukan sensitivitas

3. Menentukan sensitivitas

4. Menentukan penyelesaian optimal ketika terjadi penambahan kendala

5. Menentukan penyelesaian optimal ketika terjadi penambahan produksi, dan

6. Menentukan penyelesaian optimal ketika terjadi perubahan komposisi produksi

B. Analisis Sensitivitas

1. Perubahan Sesudah Program Optimal

Dalam kehidupan sehari-hari banyak perubahan yang terjadi. Begitu pula pada dunia industri, perdagangan, dan produksi. Suatu kemapanan produksi biasanya tidak bertahan lama karena banyak hal yang tidak dapat diatur sendiri. Ketika terjadi perubahan semacam itu, maka pabrik atau produsen tidak harus serta merta memulai lagi perhitungan produksi dari awal. Dengan program yang telah dimiliki, mereka dapat menganalisa perubahan yang terjadi. Apa saja perubahan yang dapat terjadi sesudah suatu program optimal?

Berikut ini adalah beberapa perubahan yang dapat terjadi sesudah program optimal:

a. Perubahan Kapasitas atau Sumberdaya

b. Perubahan Koefisien Fungsi Tujuan

c. Perubahan Koefisien Teknis

d. Penambahan Kendala Baru

e. Penambahan Variabel Baru

Perhatikan masalah program linear berikut!

Sebuah pabrik kimia memproduksi tiga macam zat kimia A, B, dan C. setiap kaleng zat A memerlukan 1 kg zat P dan 2 kg zat Q, serta memberi keuntungan $5. Setiap kaleng zat B memerlukan 1 kg zat P, 3 kg zat Q, dan 1 kg zat R, serta memberikan keuntungan $3. Setiap kaleng zat C memerlukan 2 kg zat P dan 4 kg zat R, serta memberi keuntungan $2. Persediaan zat P, zat Q, dan zat R pada periode itu berturut-turut 860, 920, dan 840 kg. Pabrik menghendaki keuntungan maksimal dari A, B, dan C

Penyelesaian:

Pmax =

h.m.

Dengan metode simpleks diperoleh table optimal berikut:

Table Optimal

			5	3	2	0	0	0
CB	VDB	B	X	Y	Z
2	Z	200	0		1			0
5	X	460	1		0	0		0
0		40	0	2	0	-2	1	1
Zj-cj		2700	0	4	0	1	2	0

Dari table tersebut tampak bahwa pabrik mendapatkan keuntungan maksimal sebesar $2700 yang dicapai jika memproduksi 460 kaleng zat A, 200 kaleng zat C, tanpa memproduksi zat B

Amatilah table optimal tersebut, variable yang masuk program adalah X, Z, dan

. Matriks koefisien yang berkaitan dengan variable tersebut adalah:

B =

Dengan

Penyelesaian optimal dengan X=460, Z=200, dan

=40 dapat diperoleh metode matriks berikut

Ingat, jika AX=B, maka X=

2. Perubahan Kapasitas atau Sumber daya

Misal pada periode 2 terjadi perubahan kapasitas, yaitu persediaan zat P atau

bertambah atau berkurang

maka nilai ruas kanan berubah dari

menjadi

dengan

Apabila pada masalah tersebut tetap menghendaki X, Y, dan

tetap masuk program pada program optimal maka harus dipenuhi:

Selanjutnya diperoleh:

Dari system tersebut diperoleh

Artinya: apabila banyaknya zat P pada periode 2 ditetapkan

kg maka rentang nilai

adalah

Artinya:

a. Apabila nilai

pada rentang tersebut, maka variabel dalam basis masih tetap optimal yaitu X, Y, dan

b. Rentang nilai

menunjukkan kepekaan (sensitivitas) dari nilai

c. Peningkatan

maksimal sampai 880

d. Penurunan

tidak boleh lebih rendah dari 460

Dengan kata lain, variable yang masuk basis pada program optimal tidak berubah apabila nilai

berada pada interval 460

880

3. Perubahan Koefisien Fungsi Tujuan

Perubahan harga, biaya, dan keuntungan adalah hal yang umum dalam dunia ekonomi. Perubahan ini mengakibatkan perubahan pada koefisien fungsi tujuan. Misalnya adalah seberapa besar perubahan koefisien fungsi tujuan tersebut sehingga penyelesaian optimalnya tetap.

Contoh:

Dari masalah utama, terjadi perubahan keuntungan untuk setiap kaleng zat A dari $5 menjadi $

maka tabel optimal berubah menjadi:

Tabel Optimal Perubahan

				3	2	0	0	0
CB	VDB	B	X	Y	Z
2	Z	200	0		1			0
	X	460	1		0	0		0
0		40	0	2	0	-2	1	1
			0		0	1		0

Agar program tetap optimal dengan variabel yang masuk basis X, Z, dan

atau

Dan

atau

Dengan demikian program tetap optimal jika

. Inilah yang disebut sensitivitas

. Artinya pabrik masih tetap memproduksi zat A dan zat C asalkan keuntungan per kaleng zat A lebih dari $

per kaleng.

4. Perubahan Koefisien Teknis

Misal dari masalah utama terjadi perubahan komposisi zat C sehingga setiap kaleng zat C membutuhkan

kg zat P,

kg zat Q, dan 1kg zat R. sumber daya dan ketentuan lainnya tidak berubah

Maka model Matematika masalah tersebut menjadi:

Maks T = 5X+3Y+Z

Hm. X + Y +

860

2X + 3Y +

Y + Z

840

X, Y, Z

Untuk memecahkan masalah tersebut, dengan memanfaatkan table optimal masalah utama, digunakan rumus:

A*j = B*.Aj

Keterangan:

Aj = matriks kolom ke-j table awal

A*j = matriks kolom ke-j table optimal

B = matriks identitas pada table awal

B* = matriks yang bersesuaian dengan matriks identitas pada table optimal

Pada table awal, variable yang masuk basis adalah

, dan

sehingga diperoleh:

B =

Dengan B* =

Dalam masalah ini, kolom ke-3 yang berubah dari:

A3 =

Menjadi

A3 =

Selanjutnya diperoleh:

A*3 = B*A3 =

Nilai A*3 selanjutnya dimasukkan ke table optimal menggantikan A3 sehingga diperoleh table berikut:

Table Perubahan

			5	3	2	0	0	0
CB	VDB	B	X	Y	Z
2	Z	200	0					0
5	X	460	1			0		0
0		40	0	2		-2	-1	1
Zj-cj		2700	0	4	-1	1	2	0

Dilakukan perbaikan dengan metode simpleks biasa sehingga diperoleh table berikut:

Table Perbaikan 1

			5	3	2	0	0	0
CB	VDB	B	X	Y	Z
2	Z	170	0		0	2	-1
5	X	440	1		0	1	0
2	Z	160	0	8	1	-8	4	4
Zj-cj		2860	0	15	0	-7	6	5

Table Perbaikan 2

			5	3	2	0	0	0
CB	VDB	B	X	Y	Z
0		85	0		0	1		-18
5	X	355	1		0	0
2	Z	840	0	1	1	0	0	3
Zj-cj		3345	0		0	0

Tabel tersebut menunjukkan program optimal dengan Tmaks = 3345 dengan X = 335, Z = 840, dan

= 85. Perubahan komposisi zat C ternyata memberikan keuntungan lebih tinggi dengan sumberdaya dan keuntungan per kaleng tetap.

5. Penambahan Kendala Baru

Dalam dunia nyata,sering muncul keterbatasan dalam sumber daya tertentu yang sebelumnya tak terbatas.Masalah adalah apakah penambahaan kendala baru akan menyebabkan perubahan penyelesaian optimal.

Contoh: Dari masalah utama terdapat perubahan berikut.

Dari contoh tersebut diperoleh model matematika berikut:

Maks T = 5X + 3Y + 2Z

Hm. X + Y + 2Z≤ 920

Y + 4Z ≤ 840

X + Y + Z ≤ 720

X,Y,Z ≤ 0

Dengan demikian dari masalah optimal semula perlu ditambahkan baris baru yang artinya juga akan menambah kolom baru karena selain bertambah kendala, juga akan bertambah variabel yaitu S_4.Selanjutnya disusun program perubahan dan perbaikan dengan metode simpleks berikut.

Tabel Perubahan

			5	3	2	0	0	0	0
CB	VDB	B	X	Y	Z	S₁	S₂	S₃	S₄
2	Z	200	0	-1/4	1	1/2	-1/4	0	0
5	X	460	1	3/2	0	0	½	0	0
0	S₃	40	0	2	0	-2	1	1	0
0	S₄	720	1	1	1	0	0	0	1
Zj- cj		2700	0	4	0	1	2	0	0

Tabel tersebut belum menunjukkan matriks identitas sehingga perlu dilakukan operasi baris dan kolom untuk membangun bagi variabel dalam basis(VDB).

Tabel Perbaikkan 1

			5	3	2	0	0	0	0
CB	VDB	B	X	Y	Z	S₁	S₁	S₃	S₄
2	Z	200	0	-1/4	1	½	-1/4	0	0
5	X	460	1	3/2	0	0	½	0	0
0	S₃	40	0	2	0	-2	1	1	0
0	S₄	260	0	-1/2	1	0	-1/2	0	1
Zj- cj		2700	0	4	0	1	2	0	0

Tabel Perbaikkan 2

			5	3	2	0	0	0	0
CB	VDB	B	X	Y	Z	S₁	S₁	S₃	S₄
2	Z	200	00	-1/4	1	½	-1/4	0	0
5	X	460	1	3/2	0	0	½	0	0
0	S₃	40	0	2	0	-2	1	1	0
0	S₄	60	0	-1/4	0	-1/2	-1/4	0	1
Zj- cj		2700	0	4	0	1	2	0	0

Tabel tersebut menunjukkan program tetap optimal dengan Z maksimal 2700 dan PO tetap.Artinya penambahan kendala tidak mempengaruhi penyelesaian optimal.Kendala yang demikian disebut sebagai kendala yang tidak aktif.

Berikut akan ditunjukkan adanya penambahan kendala yang menyebabkan perubahan pada PO.

Contoh:

Maks: Z = 3X + 2Y

h.m : 2X + y ≤ 12

x +2y ≤ 12

x,y ≥ 0

Setelah diselesaikan dengan metode simpleks diperoleh program optimal berikut.

Tabel Optimal

			3	2	0	0
CB	VDB	B	X	Y	S₁	S₂
3	X	4	1	0	2/3	-3/4
2	Y	4	0	1	-1/3	3/2
Zj- cj		20	0	0	4/3	3/4

Dari masalah tersebut ditambahkan kendala baru yaitu 3X + 2Y ≤ 15 lanjutnya dilakukan perbaikkan program dengan menambah baris dan kolom baru pada tabel di atas.Diperoleh tabel berikut.

Tabel Perubahan

			3	2	0	0	0
CB	VDB	B	X	Y	S₁	S₂	S₃
3	X	4	1	0	2 /3	-3/4	0
2	Y	4	0	1	-1/3	3 /2	0
0	S₃	15	3	2	0	0	1
Zj- cj		20	0	0	4 /3	3 /4	0

Selanjutnya dilakukan operasi baris dan kolom agar VDB merupakan variabel pembangun matriks identitas.Hasilnya disajikan pada tabel berikut.

Tabel Perbaikkan 1

			3	2	0	0	0
CB	VDB	B	X	Y	S₁	S₂	S₃
3	X	4	1	0	0	-3/4	0
2	Y	4	0	1	1	3 /2	0
0	S₃	3	0	2	-2	9 /4	1
Zj- cj		20	0	0	4 /3	3 /4	0

Tabel Perbaikkan 2

			3	2	0	0	0
CB	VDB	B	X	Y	S₁	S₂	S₃
3	X	4	1	0	2 /3	-3/4	0
2	Y	4	0	1	-1/3	3 /2	0
0	S₃	-5	0	0	-4/3	-3/4	1
Zj- cj		20	20	0	0	4 /3	3 /4

Tabel tersebut menunjukkan program tetap optimal.Meskipun demikian program tersebut memiliki penyelesaian yang tidak layak karena ada variabel dalam basis yang bernilai negatif.

Bila PDF tabel simpleks tidak layak maka digunakan aturan simpleks dual berikut.

Aturan simpleks untuk menentukan elemen kunci:

1. Br =Maks {[bil], bi <0}

2. Zk-ck/ark=Min {Zj-cj/arj,arj<0}

Dengan aturan simpleks dual selanjutnya dilakukan perbaikkan pada tabel tersebut.

Tabel Perbaikkan 3

			3	2	0	0	0
CB	VDB	B	X	Y	S₁	S₂	S₃
3	X	3 /2	1	0	0	25 /4	½
2	Y	21 /4	0	1	0	15 /16	-1/4
0	S₁	15 /4	0	0	1	-9/16	-3/4
Zj-cj		15	20	0	0	165 /8	1

Tampak I bahwa penyelesaiannya layak.Ternyata penambahan kendala baru pada masalah tersebut menyebabkan perubahan PO yaitu Z menurun dari 20 menjadi 15 dengan PO variabel dalam basis tetap.Kendala yang demikian disebut sebagai kendala aktif.

6.Penambahan Variabel baru

Misal pada periode II terjadi penambahan banyaknya macam zat yang diproduksi.Karena tuntutan pasar,pabrik mengeluarkan produksi baru yaitu zat D.Setiap kaleng zat D membutuhkan 1kg zat P,1 kg zat Q,dan 1 kg zat R dengan keuntungan $10 per kaleng.

Model matematika masalah tersebut menjadi:

Maks T = 5X + 2Z + 10P

Hm.X +Y+2Z +P ≤ 860

2X + 3Y + Z ≤ 920

Y + 4Z + P ≤840

X,Y,Z,P ≥0

Untuk menyelesaikan masalah tersebut, digunakan tabel optimal masalah utama dengan menambah kolom baru di sebelah kanan dan memperbaikinya dengan metode simpleks biasa.Hasilnya disajikan pada tabel berikut.

Tabel Perubahan

			5	3	2	0	0	0	10
CB	VDB	B	X	Y	Z	S₁	S₁	S₃	P
2	Z	200	00	-1/4	1	½	-1/4	0	1
5	X	460	1	3 /2	0	0	½	0	1
0	S₃	40	0	2	0	-2	1	1	1
Zj-cj		2700	0	4	0	1	2	0	-3

Tabel Perbaikan1

			5	3	2	0	0	0	10
CB	VDB	B	X	Y	Z	S₁	S₁	S₃	P
2	Z	160	0	-9/4	1	5 /2	-5/4	-1	0
5	X	420	1	-3/2	0	2	-1/2	1	0
10	P	40	0	2	0	-2	1	1	1
Zj-cj		2820	0	10	0	-5	5	3	0

Tabel Perbaikkan 2

			5	3	2	0	0	0	10
CB	VDB	B	X	Y	Z	S₁	S₁	S₃	P
2	Z	160	0	-9/4	1	5 /2	-5/4	-1	0
5	X	420	1	-3/2	0	2	-1/2	1	0
10	P	40	0	2	0	-2	1	1	1
Zj-cj		2820	0	10	0	-5	5	3	0

Tabel tersebut menunjukkan program optimal dengan Zmaks 2820 dan mempunyai penyelesaian optimal yang berbeda dari masalah semula yaitu zat A 420 kaleng,zat C 420 kaleng,dan zat D 40 kaleng.Artinya,penambahan variabel baru dalam hal ini ternyata dapat meningkatkan keuntungan.

DAFTAR PUSTAKA

ml.scribd.com/doc/16325617/Program-Linear

ayaaax

Senin, 25 Juni 2012

analisis sensitivitas

1 komentar: