Program Linier By Indra Maipita

presentasi program kerja calon rektor unimed priode 2007 - 2011 - presentasi program kerja calon rektor unimed priode 2007 - 2011 - presentasi program

PEMROGRAMAN LINEAR SEBAGAI TEKNIK PENGAMBILAN KEPUTUSAN Oleh: Indra Maipita

PENGANTAR • Sebagian besar persoalan manajemen berkenaan dengan:

– Penggunaan SD secara efisien; – Alokasi resources yang terbatas, seperti : skill, land,

capital, bahan mentah, dll.

• Dalam keadaan resources yang terbatas harus dicapai suatu hasil yang optimal, atau dengan kata lain bagaimana caranya agar dengan input yang terbatas dapat dicapai output yang optimal. • Pemrogrman linear banyak memberikan solusi persoalan sebagai alternatif dalam mengambil keputusan tetapi hanya ada satu yang “optimal” (maximum or minimum).

Matematika Ekonomi, Masalah OPTIMASI: Pemrograman Linear (Indra Maipita, Fakultas Ekonomi Universitas Negeri Medan 2006)

• Misal: pimpinan suatu perusahaan bermaksud untuk mencapai hasil penjualan yang maksimum (maximum revenue). Diputuskan untuk memproduksi sebanyak mungkin product. Jika barang tersebut semuanya laku terjual maka maximum revenue akan tercapai. Tetapi pimpinan perusahaan ternyata menghadapi beberapa kendala atau batasan-batasan (constraints), misalnya: – Jumlah yang diproduksi tidak habis diserap pasar; – Persediaan bahan mentah tidak cukup; – Tenaga kerja, mesin serta modal yang terbatas, dsb.

• Persoalan yang timbul selanjutnya: ”Bagaimana mengoptimalkan tujuan dengan memperhatikan input yang terbatas? • Ini merupakan sasaran linear programming dimana pemecahan harus mencapai optimal, maximum profit

atau minimum cost.

Matematika Ekonomi, Masalah OPTIMASI: Pemrograman Linear (Indra Maipita, Fakultas Ekonomi Universitas Negeri Medan 2006)

• Prosedur pemecahan persoalan optimasi dilakukan dengan memodelkan persoalan yang ada dengan sebuah program matematis, kemudian memecahkan persoalannya dengaan menggunakan teknik-teknik tertentu. • Langkah-langkah untuk mengubah masalah lisan ke dalam program matematis:

– Tentukan besaran yang akan dioptimasikan dan nyatakan ia sebagai sebuah fungsii matematis. Penentuan ini dengan sendirinya memerlukan pendefenisian variabel masukan. – Identifikasikan semua persyaratan dan pembatasan yang dituntut dan nyatakan mereka secara matematis. Persyaratan ini merupakan kendala - kendala (constraint). – Nyatakan juga setiap persyaratan yang terselubung (hidden conditions). Persyaratan ini tidak dikemukakan secara eksplisit dalam persoalannya tetapi menjadi jelas dalam keadaan fisik yang dimodelkan. Umumnya ini mencakup persyaratan taknegatif atau bulat pada variabel masukan.

Matematika Ekonomi, Masalah OPTIMASI: Pemrograman Linear (Indra Maipita, Fakultas Ekonomi Universitas Negeri Medan 2006)

• CONTOH : • Seorang tukang perabot mempunyai 6 unit kayu dengan waktu luang 28 jam. Ia akan membuat tirai-tirai hiasan. Dua model telah terjual sehingga ia ingin membatasi pekerjaannya pada kedua model itu saja. Ia memperkirakan bahwa model I memerlukan 2 unit kayu dan siap dalam waktu 7 jam, sedangkan model II memerlukan 1 unit kayu dan waktu 8 jam. Harga dari kedua model itu $120 dan $80. Buatlah model matematikanya jika ia ingin memaksimumkan pendapatan.

SOLUSI Tujuan (objektif) adalah memaksimumkan pendapatan (dalam dollar). Andaikan Z adalah objective, maka: Z = 120 kali jumlah tirai I + 80 kali jumlah tirai II Misal: x1 = jumlah tirai model I x2 = jumlah tirai model II sehingga fungsi objektif menjadi : maksimumkan : Z = 120x1 + 80 x2

Tukang kayu dibatasi oleh jumlah kayu yang tersedia, kendala kayu dapat ditulis : 2x1 + x2 ≤ 6 Juga dibatasi oleh jumlah waktu yant tersedia, kendala waktu ditulis : 7x1 + 8x2 ≤ 28 Tirai tidak mungkin diproduksi dalam besaran yang negatif, dan tidak ada tirai dijual dalam bentuk setengah jadi, sehingga kendala yang tersembunyi adalah : x1≥0 ; x2≥0 dan x1, x2 є bilangan bulat. Secara lengkap program matematiknya menjadi : Maksimumkan : Z = 120x1 + 80x2 Dengan kendala : 2x1 + x2 ≤ 6 7x1 + 8x2 ≤ 28 x1≥0 ; x2≥0 dan x1, x2 є bilangan bulat.

Contoh 2 † Suatu perusahaan plastik mempunyai persediaan pembungkus transparan sebanyak 1200 kotak di pabriknya yang satu dan 1000 kotak dipabrik yang lain. Perusahaan ini menerima pesanan dari 3 pengecer yang berbeda, masing-masing sejumlah 1000, 700 dan 500 kotak. Biaya pengiriman unit (dalam ribuan rupiah) dari kedua pabrik kepada pengecer sebagai berikut : Pengecer 1 pengecer 2 pengecer 3 Pabrik I 14 13 11 Pabrik II 13 13 12 † Tentukan suatu skedul pengiriman dengan biaya minimum untuk memenuhi semua permintaan dengan persediaan yang ada.

SOLUSI † Dengan menuliskan xij (I = 1,2 ; j=1,2,3) untuk jumlah kotak yang akan dikirim dari pabrik I ke pengecer j, maka diperoleh fungsi tujuan sebagai berikut : Min. Z = 14x11 + 13x12 + 11x13 + 13x21 + 13x22 +12x23 Karena jumlah yang dikirim masing-masing pabrik tidak dapat melebihi jumlah persediaannya, maka : x11 + x12 + x13 ≤ 1200 (pengiriman dari pab.I) x21 + x22 + x23 ≤ 1000 (pengiriman dari pab.II)

† Jumlah total yang dikirim kepada pengecer harus memenuhi permintaan mereka dan tidak boleh kurang, sehingga : x11 + x21 ≥ 1000 (ke pengecer 1) x12 + x22 ≥ 700 (ke pengecer 2) x13 + x23 ≥ 500 (ke pengecer 3) † Karena persediaan totalnya (1200+1000) sama dengan jumlah permintaan total (1000+700+500) dan tidak ada barang yang kurang dan tersisa, maka tiap-tiap ketidak samaan kendala dapat dijadikan suatu kesamaan.

† Program matematiknya menjadi : Min : Z = 14x11 + 13x12 + 11x13 + 13x21 + 13x22 +12x23 † Dengan kendala : x11 + x12 + x13 = 1200 = 1000 x21 + x22 + x23 x11 + x21 =1000 = 700 x12 + x22 x13 + x23 = 500 semua variables tak negative dan bulat.

METODE GRAFIK UNTUK PEMECAHAN PR OGRAM LINEAR • Kemampuan metode grafik untuk memecahkan persoalan pr ogram linier hanya terbatas untuk 2 variabel, karena jika lebi h akan sangat sulit sekali bahkan tidak bisa menggambarkan nya dalam bidang dua dimensi. • Permasalahan : • Sebuah perusahaan kayu membuat dua jenis produk, yaitu meja dan kursi, yang harus diproses melalui perakitan dan p emolesan. Perakitan memiliki 60 jam kerja, sedangkan pemol esan 48 jam kerja, Untuk menghasilkan satu meja dibutuhka n 4 jam kerja perakitan dan 2 jam pemolesan. Untuk kursi di buthkan 2 jam perakitan dan 4 jam pemolesan. Laba tiap me ja dan kursi masing-masing $8 dan $6. Berapa banyakkah m eja dan kursi yang diproduksi agar laba maksimum?

SOLUSI Dapat diringkas dalam bentuk tabel:

Perakitan pemolesan laba per unit

waktu yang dibutuhkan Meja Kursi 4 2 2 4 $8 $6

Total jam 60 48

† Misalkan M = jumlah meja yang diproduksi K = jumlah kursi yang diproduksi † Maka model matematisnya dapat ditulis sebagai berikut : Max. : Z = 8M + 6K † Dengan kendala : 4M + 2K ≤ 60 2M + 4K ≤ 48 semua variables tak negative dan bulat.

K

(0,30)

4M+2K=60

Fisible region/ solution

D(0,12) C(12,6)

2M+4K=48 A(0,0)

B(15,0)

(24,0)

M

† Kombinasi meja dan kursi yang berada dalam ABCD disebut pemecahan yang memungkinkan (fesible solutions), dan bidang ABCD itu sendiri disebut daerah yang memungkinkan (feasible region). † Kombinasi diluar ABCD tidak mungkin terjadi karena tidak memenuhi kendala yang ada. † Koordinat titik D dapat dicari dengan cara mengeliminasi kedua persamaan garis kendala. † Substitusikan ke-empat titik pada fungsi tujuan Z (objective):

Titik A(0,0)

Z = 8M + 6K 8(0) + 6(0) = 0

C(15,0)

8(15) + 6(0) = 120

D(12,6) E(0,12)

8(12) + 6(6) = 132 8(0) + 6(12) = 72

† Berarti keuntungan yang maksimum akan dicapai perusahaan tersebut jika memproduksi 12 meja dan 6 kursi, dengan total keuntungan $132.

PEMROGRAMAN LINER

METODE SIMPLEK

BENTUK STANDAR z Metode untuk memecahkan program linear yang melibatkan banyak variable dapat dilakukan dengan metode simplek. z Kendala linear memiliki bentuk : ∑aijXj ˜ bi , dimana ˜ adalah satu dari relasi ≤, ≥, atau = dan konstanta bi selalu dianggap tak negatif. Jika kendala bi negatif, dapat dikalikan dengan negatif sehingga menjadi positif. z Sebuah kendala linear berbentuk ∑aijXj ≤ bi, dapat diubah menjadi suatu persamaan dengan menambah sebuah variabel tak negatif baru pada ruas kiri. Variabel ini sama dengan selisih antara ruas kanan dan ruas kiri dan diberi nama variabel kurang (slack variable).

Contoh 4X1 + 5X2 + 3X3 + 8X4 ≤ 20000 z Andaikan ruas kiri dari ketaksamaan tsb. Memodelkan jumlah jam untuk memasang semua bodi mobil, sedangkan ruas kanan adalah jumlah jam yang tersedia. Ketaksamaan tersebut ditransformasi menjadi : 4X1 + 5X2 + 3X3 + 8X4 +X5 ≤ 20000 z Disini X5 merupakan jumlah jam pemasangan yang tersedia pada pabrik, tetapi tidak digunakan.

z Sebuah kendala linear yang berbentuk ∑aijXj ≥ bi, dapat diubah menjadi suatu persamaan dengan mengurangkan sebuah variabel baru tak negatif pada ruas kirinya. Variabel ini sama dengan selisih antara ruas kanan dan ruas kiri dan diberi nama variabel surplus (surplus variable). Variabel ini menyatakan kelebihan masukan ke dalam tingkat sistem yang dimodelkan oleh kendala.

Contoh 4X1 + 5X2 + 3X3 + 8X4 ≥ 20000 z Andaikan ruas kiri merupakan gabungan jumlah mobil yang diproduksi dalam setahun, sedangkan ruas kanan jumlah minimum yang dibutuhkan untuk memenuhi kontrak. Ketaksamaan ini ditransformasi menjadi : 4X1 + 5X2 + 3X3 + 8X4 –X5 ≥ 20000

z Pada ruas kiri dari setiap persamaan yang tidak mengandung variabel kurang, masih perlu ditambahkan sebuah variabel baru yang disebut variabel buatan (artificial variable). Dengan demikian setiap persamaan kendala akan memuat variabel kurang atau variabel buatan. z Pemecahan awal yang tak negatif diperoleh dengan menetapkan setiap variabel kurang dan variabel buatan sama dengan ruas kanan dimana ia muncul dan menetapkan semua variabel lainnya termasuk variabel surplus sama dengan nol.

Contoh X1 + 2X2 ≤ 3 4X1 + 5X2 ≥ 6 7X1 + 8X2 = 15 z Setelah ditransformasikan menjadi : X1 + 2X2 + X3 =3 4X1 + 5X2 - X4 + X5 =6 7X1 + 8X2 + X6 = 15 z Pemecahan tak negatif bagi system ini adalah : X3 = 3, X5 = 6, X6 = 15, dan X1 = X2 = X4 = 0

Pemecahan Awal yang Layak z Setelah semua kendala linier ditransformasikan menjadi bentuk persamaan, maka semua persmaan kendala akan memiliki variabel kurang atau variabel buatan. z Pemecahan awal yang layak bagi kendala ini diperoleh dengan menetapkan setiap variabel kurang dan variabel buatan sama dengan ruas kanannya, sedangkan variabel lainnya sama dengan nol.

Contoh

Himpunan kendala : x1 + 2 x2 ≤ 0 4 x1 + x2 ≥ 0 4 x1 + 6 x2 = 0

Tentukan p emecahan awal tak negatif dari kendala tersebut !

BIAYA HUKUMAN (PENALTY COST) z Penambahan variabel kurang dan surplus tidak mengubah sifat kendala maupun tujuan, oleh karena itu variabel tersebut dapat diikuti sertakan dalam fungsi tujuan, tetapi dengan koefisien sama dengan nol. Sedangkan variabel buatan dapat mengubah sifat dari kendala karena variabel buatan ini hanya ditambahkan pada salah satu ruas persamaan saja, maka sistem yang baru ekuivalen dengan persamaan yang lama jika dan hanya jika nilai variabel buatan tersebut sama dengan nol.

BIAYA HUKUMAN (PENALTY COST)..(2) z Untuk menjamin penetapan seperti itu, dalam pemecahan optimal, variabel buatan diturutkan dalam fungsi tujuan tetapi dengan koefisien positif yang besar sekali untuk program meminimumkan (minimisasi) dan koefisien negatif yang besar sekali untuk rogram maksimum. Koefisien-koefisien tersebut dinyatakan dengan M atau –M, menyatakan hukuman yang berat sekali yang dikenakan dalam membuat suatu penetapan satuan pada variabel buatan.

Soal 1. Rumuskan persoalan berkut dalam bentuk standar : Maksmumkan : Z = 5X1 + 2X2 Dengan kendala : 6X1 + X2 ≥ 6 4X1 + 3X2 ≥ 12 X1 + 2X2 ≥ 4 ; X1,X2 >0 2. Maksimumkan : Z = 25X1 + 30X2 Dengan kendala : 4X1 + 7X2 ≥ 1 8X1 + 5X2 ≤ 3 6X1 + 9X2 = -2 X1,X2 >0

METODE SIMPLEK

z Bentuk standar: Optimasikan Z = CTX Dengan kendala : AX = B dan : X ≥ 0

Langkah Penyelesaian Tentukan bilangan yang paling negatif dalam baris terbawah dari table simplek, dengan mengabaikan kolom terakhir. Namakan kolom yang memuat bilangan tersebut dengan kolom kerja (work column), Jika terdapat lebih dari satu bilangan yang paling negatif, maka pilihlah salah satunya. 2. Bentuklah rasio atau nilai perbandingan dengan membagi setiap bilangan positif pada kolom kerja dengan elemen pada baris yang sama dalam kolom terakhir, dimana baris terakhirnya diabaikan. Jika terdapat lebih dari satu elemen yang mempunyai rasio terkecil, pilih salah satunya. Namakan elemen pada kolom kerja yang menghasilkan rasio terkecil tersebut dengan elemen pasak (pivot element),. Jika tidak ada elemen pada kolom kerja yang positif, maka programnya tidak memiliki pemecahan. 1.

3. Gunakan operasi baris elementer untuk

mengubah elemen pivot menjadi 1, kemudian reduksikan semua elemen lainnya dalam kolom kerja menjadi 0. 4. Gantikan variabel X dalam baris pivot pada kolom pertama dengan variabel X dalam baris pertama dan kolom pivot. Kolom pertama yang baru ini adalah himpunan variabel dasar yang baru. 5. Ulangi langkah 1 sampai 4 hingga tidak terdapat lagi elemen negatif dalam baris terakhir, dengan tidak memasukkan kolom terakhir.

6. Pemecahan optimal diperoleh dengan

menetapkan untuk setiap variabel dalam kolom pertama = nilai dalam baris dan kolom terakhir pada baris yang bersangkutan. Semua variabel yang lainnya ditetakan bernilai nol. Nilai optimal dari fungsi objektif adalah bilangan yang terdapat dalam baris terakhir dan kolom terakhir untuk program maksimisasi, sedangkan negaif dari bilangan ini untuk program minimisasi

Modivikasi Program dgn Variabel Buatan z Apabila variabel buatan merupakan bagian dari pemecahan awal X0, maka baris terakhir dari table simplek akan mengandung biaya hukuman. Untuk meminimumkan kesalahan pembulatan, maka modifikasi berikut diikut sertakan dalam metode simplek yang disebut dengan metode dua fasa (two phase method).

Langkah Perubahan Metode Dua Fasa 1. Baris terakhir yang mengandung M dari tabel diuraikan menjadi dua baris, yang pertama baris yang tidak mengandung M dan yang kedua baris yang mengandung koefisien M. z Contoh: Misalkan baris terakhirnya adalah : -2-M 0 3-4M M 12 di ubah menjadi dua baris yaitu : -2 0 3 0 12 -1 0 -4 1 0

2. Langkah 1 dari metode simplek diterapkan

pada baris terakhir yang dibentuk dalam perubahan 1 (kemudian diikuti oleh langkah 2,3 dan 4), hingga baris ini tidak mengandung elemen negatif. Kemudian langkah 1 diterapkan lagi pada elemen dalam baris kedua dari bawah 3. Setiap saat sebuah variabel buatan bukan merupakan suatu variabel dasar, ia dapat dihilangkan dari kolom pertama sebagai hasil dari langkah 4, maka ia dicoret dari baris teratas tabel, demikian juga dengan seluruh isi kolom di bawahnya.

4. Baris terakhir dapat dicoret dari

tabel jika semua elemennya nol. 5. Jika variabel buatan yang tak nol terdapat dalam himpunan elemen dasar yang terakhir, maka programnya tidak memiliki pemecahan.

Contoh Max. : Z = X1 + 9X2 + X3 Kendala : X1 + 2X2 + 3X3 ≤ 9 3X1 + 2X2 + 2X3 ≤ 15 semua var. tak negative

Penyelesaian z Setelah diubah ke dalam bentuk standar, selanjutnya dimasukkan ke dalam tabel simplek seperti berikut :

X4 0 X5 0

X1 1 1 3

x2 9 2 2

x3 1 3 2

x4 0 1 0

x5 0 0 1

9 15

X4 X5

X2 X5

X1

x2

x3

1 3 -1

2* 2 -9

X1

x2

x3

1/2 2 7/2

1 0 0

3/2 1/2 -1 -1 25/2 9/2

3 2 -1

x4

x5

1 0 0

0 1 0

x4

x5 0 1 0

9 15 0

9/2 6 81/2

z Dengan menerapkan langkah 1 hingga 4 pada table 2, diperoleh tabal 3. Karena baris terakhir dari table 3 tidak memuat elemen negatif, maka dari langkah 6 diperoleh pemecahan optimalnya adalah : z X2 = 9/2, X5 = 6, X1 = X3 = X4 = 0, dengan Z = 81/2.

Soal Min : Z = x1 + 2X2 + 3X3 Kendala : 3X1 + 4X3 ≤ 5 5X1 + X2 + 6X3 = 7 8X1 + 9X3 ≥ 2 Semua variabel tak negatif

terimakasih kepada seluruh anggota senat universitas UNIMED yang telah memberikan kesempatan kepada saya untuk menyampaikan strategic plannin