Anvek Va 285j2s

BAB I PENDAHULUAN A.

Latar Belakang Dalam matematika terdapat metode untuk mengalokasikan sumber daya

yang terbatas untuk mencapai suatu tujuan yang optimal. Metode ini adalah pemrograman linier. Pemograman linier banyak diterapkan dalam masalah ekonomi, industri, militer, sosial, dan lain-lain. Pemrograman linear berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu model matematika yang terdiri dari sebuah fungsi tujuan linier dengan beberapa kendala linier. Pemrograman linier meliputi perencanaan aktivitas untuk mendapatkan hasil optimal, yaitu sebuah hasil yang mencapai tujuan terbaik (menurut model matematika) diantara semua kemungkinan alternatif yang ada. Karateristik-karakteristik pada pemrograman linier adalah: fungsi tujuan (untuk memaksimumkan atau meminimumkan sesuatu), fungsi pembatas yang membatasi tingkatan pencapaian tujuan, adanya beberapa alternatif tindakan yang bisa dipilih, fungsi tujuan dan kendala dalam permasalahan diekspresikan dalam bentuk persamaan atau pertidaksamaan linier. Metode simpleks adalah suatu metode yang secara sistematis dimulai dari suatu pemecahan dasar yang dimungkinkan ke pemecahan dasar yang lainnya dan ini dilakukan tahap demi tahap yang disebut dengan iterasi (dengan jumlah iterasi yang terbatas) sehingga pada akhirnya akan tercapai suatu pemecahan dasar yang optimum dan setiap langkah menghasilkan suatu nilai dari fungsi tujuan yang selalu lebih optimal atau sama dari langkah-langkah sebelumnya. B.

Rumusan Masalah Adapun rumusan permasalahan yang dibahas didalam makalah ini, sebagai

berikut: 1. Bagaimana menyelesaikan permasalahan program linier dengan metode simpleks? 2. Bagaimana merancang program awal yang memuat atas variabel “slack”?

1

2

3. Bagaimana menentukan kerangka dasar perhitungan nilai minimum dari tabel simpleks? 4. Bagaimana merancang program awal yang hanya terdiri atas variabel “slack tiruan”? 5. Bagaimana siswa memperbaiki program awal dan program-program berikutnya hingga tercapai program minimum? C.

Tujuan Penulisan Dalam setiap penulisan makalah pastilah ada tujuan yang ingin dicapai oleh

penulis, adapun tujuan dari penulisan makalah ini: 1.

Memenuhi tugas mata kuliah Program Linear.

2.

Dapat menyelesaikan permasalahan program linier dengan metode simpleks.

3.

Dapat menentukan kerangka dasar dari tabel simpleks.

4.

Dapat merancang program awal yang memuat atas variabel “slack” atau “slack tiruan”.

5.

Dapat memperbaiki program awal dan program-program berikutnya hingga tercapai program minimum.

BAB II PEMBAHASAN A.

Pengertian Metode simpleks merupakan salah satu teknik penyelesaian dalam program

linier yang digunakan sebagai teknik pengambilan keputusan dalam permasalahan yang berhubungan dengan pengalokasian sumber daya secara optimal. Metode simpleks digunakan untuk mencari nilai optimal dari program linier yang melibatkan banyak constraint (pembatas) dan banyak variabel (lebih dari dua variable). Penemuan metode ini merupakan lompatan besar dalam riset operasi dan digunakan sebagai prosedur penyelesaian dari setiap program komputer. Program Linier merupakan metode matematik dalam mengalokasikan sumber

daya

memaksimumkan

yang

langka

keuntungan

untuk atau

mencapai

tujuan

meminimumkan

tunggal

biaya.

LP

seperti (linear

programming) banyak diterapkan dalam membantu menyelesaikan masalah ekonomi, indutri, militer, sosial dan lain-lain. Dari berbagai metode penyelesaian program linier, metode simpleks merupakan metode yang paling ampuh dan terkenal. Metode simpleks didasarkan atas pengertian bahwa solusi optimal dari masalah program linier, jika ada, selalu dapat ditemukan disalah satu dari “solusi dasar yang berlaku”. Oleh sebab itu dalam metode simpleks, langkah pertama adalah untuk memperoleh solusi dasar yang berlaku. B.

Penentuan Minimum Kasus mencari nilai minimum akan dijelaskan dengan sebuah masalah

serupa dengan masalah diet yang sangat terkenal. Marilah kita merumuskan masalah dimana seseorang memerlukaan sejumlah tertentu dari masing-masing vitamin setiap harinya. Vtamin A dan B terdapat dalam dua makanan yang berbeda M 1 dan M2. Jumlah vitamin disetiap makanan dan vitamin yang diperlukan setiap harinya dapat dilihat pada tabel berikut.

3

4

Tabel Persiapan Penyusunan Model Matematika Makanan Vitamin

M1

M2

A B Harga

2 3

4 2

3

2.5

Makanan/Unit

Keperluan Sehari 40 50

Dalam menunjukkan bahwa 1 M1 mengandung 2 unit vitamin A dan 3 unit vitamin B, serta 1 unit M2 mengandung 4 unit vitamin A dan 2 unit vitamin B. Keperluan sehari akan vitamin A paling sedikit 40 unit dan vitamin B sejumlah 50 unit. Tujuan kita adalah menentukan jumlah optimal dari makanan M1 dan M2 sehingga keperluan vitamin seharinya dipenuhi dengan biaya serendah mungkin. Misalkan bahwa untuk memenuhi tujuan ini dibeli x makanan M1 dan sejumlah y dari makanan M2. Secara aljabar masalah inni dapat ditulis sebagi berikut: Minimumkan: f = 3x + 2.5y Syarat

: 2x + 4y ≥ 40 3x + 2y ≥ 50 x≥0,y≥0

Metode simpleks II menangani persyaratan “lebih besar atau sama” dengan suatu nilai. Untuk merubah pertidaksamaan menjadi persamaan memerlukan “pengurangan” dengan variabel “slack”. Misalkan sejumlah x dan y dari vitamin A dan B diperlukan seharinya,maka model matematikanya dapat ditulis kembali sebagai berikut: Minimumkan: f = 3x + 2.5y + 0S1 + 0S2 Syarat

: 2x + 4y - S1 = 40 3x + 2y – S2 = 50 x ≥ 0 , y ≥ 0 , S1 ≥ 0 , S2 ≥ 0

C.

Variabel Slact Tiruan (Artificial)

4

5

Jika variabel kerangka (struktual) x dan y dimisalkan nol seperti pada program awal metode simpleks, maka diperoleh nilai-nilai negatif dari S1 dan S2 yang tidak memenuhi persyaratan. Untuk tidak melanggar persyarataanpersyaratan yang telah ditetapkan dalam program-program metode simpleks maka diciptakan variabel slack tiruan. Model

matematika dilengkapi dengan variabel slack tiruan A1 dan A 2

sampai An, sehingga jika x dan y bernilai nol, persamaan-persamaan persyaratan masih memiliki variabel slack yang bernilai positif. Maka model matematika secara lengkap ditulis: Minimumkan: f = 3x + 2.5y + 0S1 + 0S2 + MA1 + MA2 Syarat

: 2x + 4y - S1 + A1 = 40 3x + 2y – S2 + A2 = 50 x ≥ 0 , y ≥ 0 , S1 ≥ 0 , S2 ≥ 0 , A1 ≥ 0 , A2 ≥ 0

Perlu diperhatikan bahwa variabel “slack” S memiliki koefisien biaya sebesar nol, sedangkan variabel “slack tiruan” A memiliki koefisien biaya M yang tak terhingga besarnya. Dengan mengaitkan nilai M yang tak terhingga besarnya pada koefisien slack tiruan A, kita yakin bahwa variabel ini tidak akan pernah masuk dalam penyelesaian optimal. D.

Merancang Program Awal Dalam metode simpleks, program awl hanya melibatkan S1 dan S2,

sedangkan x dan y sebagai variabel kerangka benilai nol. Untuk suatu masalah berdimensi dua, ini berarti menyatakan vektor persyaratan P0 dalam vektor basis

dan

.

6

Dalam contoh yang ditampikan diatas, vektor persyaratan P0 =

dinyatakan dengan vektor-vektor basis

dan

dapat

.

Untuk memudahkan penyusunan program awal dari metode simpleks II, maka dengan menggunakan variabel slack A1 dan A2, model matematika perlu dituliskan kembali selengkapnya. Minimumkan: f = 3x + 2.5y + 0S1 + 0S2 + MA1 + MA2 Syarat

: 2x + 4y - 1.S1 + 0.S2 + 1. A1 + 0.A2 = 40 3x + 2y + 0.S1 – 1.S2 + 0. A1 + 1.A2 = 50 x ≥ 0 , y ≥ 0 , S1 ≥ 0 , S2 ≥ 0 , A1 ≥ 0 , A2 ≥ 0

Program awal dengan memilih x, y, S1, S2 bernilai nol. Dari persamaan diatas, mudah dipahami bahwa ini berkaitan dengan nilai-nilai A1 = 40 dan A2 = 50. Oleh sebab itu tabel yang digunakan untuk perhitungan simpleks II pada program awal dapat dilihat pada tabel dibawah ini. Tabel Program I Biaya/

Kuan

3

2,5

0

0

M

M

Unit

titas

X

Y

S1

S2

A1

A2

A1

M

40

2

4

-1

0

1

0

40/4=10

A2

M

50

3

2

0

-1

0

1

50/2=25

M

0

0

Program

Baris Penilaian:

3-5 M

-6 M M

Variabel keluar

Variabel masuk

Program awal ini melibatkan biaya 90 M yang jelas besar sekali, sehingga program harus diperbaiki. 1.

Perhitungan dari baris penilaian.

2.

mengenali kolom kunci

3.

mengenali baris kunci dan bilangan kunci

7

4.

Transformasi dari baris kunci dan baris bukan kunci untuk memperoleh program yang diperbaiki

Adapun perbedaan yang perlu diperhatikan dalam simpleks II, bahwa dalam kasus mencari minimum, nilai “negatif terbesar” dalam baris penilaian menentukan kolom kunci dan bukan positif terbesar seperti dalam kasus mencari nilai minimum. Dalam kasus mencari nilai minimum, jika bilangan dari baris penilaian dibawah suatu kolom variabel adalah negatif, maka jelas bahwa keikutsertaan variabel ini dalam baris baru akan menurunkan nilai dari fungsi objektifnya. Penghitungan dari baris penilaian sudah dijelaskan dalam kegiatan belajar 1. Memasukan satu unit y akan menurunkan biaya total dengan 2,5M – 6M yang diperoleh dari [+1(2,5) – 4M – 2M] Nilai 2,5M – 6M jelas lebih negatif dari pada 3 – 5M, maka y adalah variabel yang harus masuk dengan mengeluarkan variabel A1. Hasil perbaikan tabel program I dapat dilihat pada tabel 5.3 Tabel 5.3 Tabel program II

Pro

Biaya

Kuan

gram

per unit

titas

Y

2,5

10

A2

M

30

Baris penilaian:

3 X

2,5 Y

0 S1

0 S2

M A1

M A2

0,5 2

1

-0,25

0

0,25

0

10/0,5=20

0

0,5

-1

-0,5

1

30/2=15

0

M

0

Tabel program II jelas belum optimal karena masih memiliki nilai negatif

Variabel Keluar

Variabel Masuk

dalam baris penilaian. Perbaikan program akan melibatkan pergantian variabel A2 oleh x. Dalam transformasi baris lama ke baris baru dalam program yang telah diperbaiki kita berpedoman kepada aturan – aturan yang telah berlaku, yaitu: 1. Baris kunci dibagi dengan bilangan kunci menghasilkan baris baru.

8

2. Bil. baris lama – (bilang berkaitan dalam baris kunci x rasio tertentu bersangkutan)

Bilangan baris baru

3. Rasio tertentu =

Tabel 5.4 Tabel program III Pro

Biaya

Kuan

gram

perunit

titas

Y

2,5

X

3

15

Baris penilaian :

3 0

2,5 1

0

1

1

0

0

0

0 S1

0 S2

M A1

M A2

Tabel program III sudah merupakan program optimal, karena baris penilaian tidak memiliki nilai negatif lagi. Program optimal ini berkaitan dengan pembelian 15 unit makan M1 dan unit makanan M2 seharinya, dengan biaya 51,25 dollar sen. E.

Prosedur Penentuan Struktur Persyaratan Karakteristik dari masalah program linier dapat dicakup dalam 3 jenis yang

berbeda. 1.

persyaratan yang dalam bentuk aslinya dinyatakan oleh pertidaksamaan dari jenis “kurang dari atau sama dengan”, jenis ≤.

2.

persyaratan yang dalam bentuk aslinya dinyatakan oleh pertidaksamaan dari jenis “lebih besar atau sama dengan”, jenis ≥.

3.

persyaratan yang dalam bentuk aslinya merupakan campuran dari persamaan dan pertidaksamaan.

Penyusunan kembali model matematika diperlukan untuk siap dan dapat digunakan dalam perancangan program awal dari metode simpleks.

9

Kasus 1: Jenis ( ≤. ) “lebih kecil dari atau sama dengan” Setiap pertidaksamaan “kurang dari atau sama dengan” diubah menjadi persamaan dengan menambah “variable slack” yang tidak negatif dan memiliki koefesien 0 dalam fungsi objektif. Contoh: Maksimumkan: f = 10x + 15y Syarat

: 4x + 60y ≤. 60 3x + 4y ≤. 80 X ≥ 0, y ≥ 0

Persamaan yang diperlukan untuk table simpleks adalah: 4x + 6y + 1S1 + 0S2 = 60 3x + 4y + 0S1 + 1S2 = 80 Fungsi Objektif: f = 10x + 15y + 0S1 + 0S2 kasus 2: Jenis ( ≥ ) “lebih besar atau sama dengan” Setiap pertidaksamaan dari jenis “lebih besar atau sama dengan” diubah menjadi persamaan dengan mula-mula mengurangi dengan variabel slack yang tidak negative dan memiliki koefesien onkos 0, kemudian menambahkan dengan variabel slack tiruan yang tidak negative dan memiliki koefesien onlos M yang bernilai tak hingga. Contoh: Minimunkan: f = 300x + 180y Syarat

:

8x + 5y ≥ 80 4x + 2y ≥ 70 x ≥ 0, y ≥ 0

10

Persamaan-persamaan yang diperlukan untuk tabel simpleks adalah: 8x + 5y +1S1 + 0S2 + 1A1 + 0A2 = 80 4x + 2y +0S1 + 1S2 + 0A1 + 1A2 = 70 Fungsi Objektif: f: 300x + 180y +0S1 + 0S2 + MA1 + MA2 Kasus 3: Kasus campuran Masalah yang digolongkan kedala kasus 3 adalah masalah yang memiliki persamaan disamping pertidaksamaan. Persamaan ditangani dengan melengkapinya dengan menambahkan variabel slack tiruan yang tidak negative. Contoh: Minimumkan: f = 7x + 15y Syarat

: 2x + 4y ≥ 20 5x + 8y = 30 x ≥0,y≥0

Persamaan-persamaan yang diperlukan untuk tabel simpleks adalah: 2x + 4y +1S1 + 1A1 + 0A2 = 20 5x + 8y +0S1 + 0A1 + 1A2 = 30 Fungsi Objektif: f: 7x + 15y +0S1 + MA1 + MA2

BAB III PENUTUP A.

Kesimpulan Langkah-langkah yang dapat di tempuh dalam menentukan solusi optimal

permasahan program linear dengan metode simpleks adalah : 1. Menentukan model matematika untuk data-data yang terdapat pada permasalahan program linier. 2. Menambahkan dan melakukan pengurangan dengan variabel ”slack” (S1,S2,S3), sehingga model matematika dapat diubah menjadi persamaan linear. 3. Membuat kerangka tabel simpleks, merancang program awal, menguji ke optimalan yang sedang berlangsung. 4. Supaya tidak melanggar syarat yang telah ditetapkan, maka di tambahkan variabel “slack tiruan” (A1,A2,A3). 5. Melakukan perbaikan-perbaikan terhadap program yang berlangsung sampai diperoleh program optimal. Langkah- langakah yang dilakukan dalam perbaikan program tersebut adalah: a. Menetukan kolom kunci, yaitu kolom yang memiliki nilai “negatif terbesar” pada baris penilaian. b. Menentukan baris kunci yaitu baris yang mempunyai bilangan hasil bagi terkecil (bilangan pada kolom kuantitas dibagi dengan bilangan negatif pada kolom kunci) c. Menentukanbilangan kunci, yaitu bialangan yang terdapat pada persilangan antar kolom kunci dan baris kunci d. Menentukan variabel masuk yaitu variabel yang terpilih untuk menjadi variabel basis pada iterasi berikutnya. Variabel masuk dipilih satu dari antara variabel non basis pada setiap iteasi. Variabel ini pada iterasi berikutnya akan bernilai positif. e. Menetukan variabel keluar, yaitu variabel yang keluar dari varibel iterasi (tahapan yang terkait dengan perhitungan nilai sebelumnya) dan digantikan dengan variabel masuk. Variabel keluar dipilih satu dari antara variabel basis pada setiap iterasi dan bernilai nol. f. Menurunkan tabel dari tabel program awal ketabel program berikut nya hasil perbaikan dengan cara:

11

12

 Melakukan transpormasi baris kunci, yaitu membagi semua bilangan dalam baris kunci dan bilangan kunci  Melakukan transpormasi bukan baris kunci, dengan rumus “bilangan baris baru”  Program sudah optimal jika baris penilaian tidak memiliki bilangan nol atau negatif.

B.

Kritik dan Saran Kami sebagai penyusun menyadari bahwa masih terdapat kekurangan di

dalam makalah kami, maka dari itu kritik dan saran yang membangun dari pembaca sangat kami harapkan.

DAFTAR PUSTAKA Ningsih,Yetri.2013.Bahan Ajar Program Linier.Lubuklinggau

13