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

PEMROGRAMAN LINEAR SEBAGAI PEMROGRAMAN LINEAR SEBAGAI TEKNIK PENGAMBILAN TEKNIK PENGAMBILAN

KEPUTUSANKEPUTUSANOleh:Oleh:

Indra MaipitaIndra Maipita

• 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).

PENGANTAR

• 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 meng-optimalkan 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.

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

SOLUSITujuan (objektif) adalah memaksimumkan pendapatan (dalam dollar).

Andaikan Z adalah objective, maka:Z = 120 kali jumlah tirai I + 80 kali

jumlah tirai IIMisal: x1 = jumlah tirai model I

x2 = jumlah tirai model II sehinggafungsi objektif menjadi :

maksimumkan : Z = 120x1 + 80 x2

Tukang kayu dibatasi oleh jumlah kayu yang tersedia, kendala kayu dapat ditulis :

2x1 + x2 ≤ 6Juga dibatasi oleh jumlah waktu yant tersedia, kendala waktu ditulis :

7x1 + 8x2 ≤ 28Tirai 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 ≤ 67x1 + 8x2 ≤ 28x1≥0 ; x2≥0 dan x1, x2 є bilangan bulat.

Contoh 2Suatu 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 3Pabrik I 14 13 11Pabrik II 13 13 12

Tentukan suatu skedul pengiriman dengan biaya minimum untuk memenuhi semua permintaan dengan persediaan yang ada.

SOLUSIDengan 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 x21 + x22 + x23 = 1000 x11 + x21 =1000 x12 + x22 = 700x13 + x23 = 500

semua variables tak negative dan bulat.

METODE GRAFIK UNTUK PEMECAHAN PROGRAM LINEAR

• Kemampuan metode grafik untuk memecahkan persoalan program linier hanya terbatas untuk 2 variabel, karena jika lebih akan sangat sulit sekali bahkan tidak bisa menggambarkannya dalam bidang dua dimensi.

• Permasalahan :• Sebuah perusahaan kayu membuat dua jenis produk, yaitu

meja dan kursi, yang harus diproses melalui perakitan dan pemolesan. Perakitan memiliki 60 jam kerja, sedangkan pemolesan 48 jam kerja, Untuk menghasilkan satu meja dibutuhkan 4 jam kerja perakitan dan 2 jam pemolesan. Untuk kursi dibuthkan 2 jam perakitan dan 4 jam pemolesan. Laba tiap meja dan kursi masing-masing $8 dan $6. Berapa banyakkah meja dan kursi yang diproduksi agar laba maksimum?

SOLUSI

$6 $8 laba per unit4842pemolesan6024Perakitan

KursiMeja Total jam

waktu yang dibutuhkan

Dapat diringkas dalam bentuk tabel:

Misalkan M = jumlah meja yang diproduksiK = jumlah kursi yang diproduksi

Maka model matematisnya dapat ditulis sebagai berikut :

Max. : Z = 8M + 6KDengan kendala :

4M + 2K ≤ 602M + 4K ≤ 48

semua variables tak negative dan bulat.

K

M

4M+2K=60

2M+4K=48

(24,0)

D(0,12)

B(15,0)

(0,30)

A(0,0)

C(12,6)

Fisible region/ solution

Kombinasi meja dan kursi yang berada dalam ABCD disebut pemecahan yang memungkinkan (fesible solutions), dan bidang ABCDitu 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):

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

8(0) + 6(12) = 72E(0,12)8(12) + 6(6) = 132D(12,6)8(15) + 6(0) = 120C(15,0)8(0) + 6(0) = 0A(0,0)Z = 8M + 6KTitik

PEMROGRAMAN LINER

METODE SIMPLEK

BENTUK STANDAR

Metode untuk memecahkan program linear yang melibatkan banyak variable dapat dilakukan dengan metode simplek.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.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 ≤ 20000Andaikan 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 ≤ 20000Disini X5 merupakan jumlah jam pemasangan yang tersedia pada pabrik, tetapi tidak digunakan.

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 ≥ 20000Andaikan 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

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.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 ≤ 34X1 + 5X2 ≥ 67X1 + 8X2 = 15

Setelah ditransformasikan menjadi :X1 + 2X2 + X3 = 34X1 + 5X2 - X4 + X5 = 67X1 + 8X2 + X6 = 15

Pemecahan tak negatif bagi system ini adalah : X3 = 3, X5 = 6, X6 = 15, dan X1 = X2 = X4 = 0

Pemecahan Awal yang Layak

Setelah semua kendala linier ditransformasikan menjadi bentuk persamaan, maka semua persmaan kendala akan memiliki variabel kurang atau variabel buatan.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

0x6x40xx40x2x

:kendala Himpunan

21

21

21

=+≥+≤+

Tentukan p emecahan awal tak negatif dari kendala tersebut !

BIAYA HUKUMAN (PENALTY COST)

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)

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 + 2X2Dengan kendala :

6X1 + X2 ≥ 64X1 + 3X2 ≥ 12 X1 + 2X2 ≥ 4 ; X1,X2 >0

2. Maksimumkan : Z = 25X1 + 30X2Dengan kendala :

4X1 + 7X2 ≥ 18X1 + 5X2 ≤ 3 6X1 + 9X2 = -2 X1,X2 >0

METODE SIMPLEK

Bentuk standar:

Optimasikan Z = CTXDengan kendala : AX = B

dan : X ≥ 0

Langkah Penyelesaian

1. 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.

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

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.Contoh:Misalkan baris terakhirnya adalah :

-2-M 0 3-4M M 12di 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 + X3Kendala :

X1 + 2X2 + 3X3 ≤ 93X1 + 2X2 + 2X3 ≤ 15semua var. tak negative

Penyelesaian

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

X1 x2 x3 x4 x51 9 1 0 0

X4 0 1 2 3 1 0 9X5 0 3 2 2 0 1 15

X1 x2 x3 x4 x5

X4 1 2* 3 1 0 9X5 3 2 2 0 1 15

-1 -9 -1 0 0 0

X1 x2 x3 x4 x5

X2 1/2 1 3/2 1/2 0 9/2X5 2 0 -1 -1 1 6

7/2 0 25/2 9/2 0 81/2

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 :X2 = 9/2, X5 = 6, X1 = X3 = X4 = 0, dengan Z

= 81/2.

Soal

Min : Z = x1 + 2X2 + 3X3Kendala :

3X1 + 4X3 ≤ 55X1 + X2 + 6X3 = 78X1 + 9X3 ≥ 2

Semua variabel tak negatif

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