MATERI 2 (PROGRAM LINEAR)

Program Linear adalah Model matematika yang digunakan untuk menyelesaikan masalah optimisasi

Memaksimumkan dan meminimumkan fungsi tujuan, yang bergantung pada sejumlah variabel input

Hal terpenting yg harus dilakukan adalah mencari tahu tujuan penyelesaian masalah dan apa penyebab masalah tersebut.

Macam-Macam fungsi Program Linear

1. Fungsi Tujuan = Mengarahkan analisa untuk mendeteksi tujuan perumusan masalah. (Z, R atau P).

2.Fungsi Kendala = Untuk mengatasi sumber daya yang tersedia, dan permintaan atas sumber daya tsb.

Didalam Model  Program Linear terdapat beberapa istilah yang sering dijumpai diantaranya:

1.Suatu model PL akan membuat permasalahan menjadi suatu bentuk pengambilan keputusan mengenai tingkat aktivitas (x1, x2, x3, ……, xn) disebut variabel keputusan.

2.Solusi feasible (layak) adalah solusi di mana semua kendala yang ada terpenuhi, dan solusi disebut infeasible (tak layak) jika paling sedikit ada satu kendala yang tak terpenuhi.

3.Daerah feasible (layak) adalah kumpulan semua solusi feasible.

4.Solusi optimal adalah solusi layak yang memiliki nilai fungsi tujuan terbaik, terbesar jika masalahnya maksimasi dan terkecil jika masalahnya minimasi.

Selain  istilah-istilah tersebut didalam model program linear juga terdapat beberapa asumsi diantaranya:

1.Proportionality : naik turunnya nilai Z dan penggunaan sumber atau fasilitas yang tersedia akan berubah secara sebanding (proportional) dengan perubahan tingkat kegiatan .

2.Additivity : nilai tujuan tiap kegiatan tidak saling mempengaruhi, atau dalam LP dianggap bahwa kenaikan dari nilai tujuan (Z) yang diakibatkan oleh kenaikan suatu kegiatan dapat ditambahkan tanpa mempengaruhi bagian nilai Z yang diperoleh dari kegiatan lain.

3.Divisibility : keluaran (output) yang dihasilkan oleh setiap kegiatan dapat berupa bilangan pecahan. Demikian pula dengan nilai Z yang dihasilkan.

4.Deterministic (Certainty) : Asumsi ini menyatakan bahwa semua parameter yang terdapat dalam model LP (ai, bi Cj) dapat diperkirakan dengan pasti, meskipun jarang dengan tepat.

Berikut contoh Model program Linear.

Fungsi Tujuan :

                Max/min            z = c1x1 + c2x2 + ... + cnxn

Berdasarkan kendala :

                                                a11x1 + a12x2 + ... + a1nxn    (≤, =, ≥) b1

                                                a21x1 + a22x2 + ... + a2nxn    (≤, =, ≥) b2

                                                                :

                                                am1x1 + am2x2 + ... + amnxn (≤, =, ≥) bm

                                               

                                                x1, x2 , ... xn  ≥ 0

                xj = variabel keputusan ke j

                bi = kapasitas kendala ke i

                cj = koefisien fungsi tujuan ke j

                aij = koefisien kendala

Langkah-Langkah dalam melakukan Model Program Linear adalah

1.Tahap 1

Masalah harus dapat diidentifikasi sbg sesuatu yg dapat diselesaikan oleh program linier

2.Tahap 2

Masalah yang tidak terstruktur harus dapat dirumuskan oleh model matematika

3.Tahap 3

Model harus dibuat menggunakan model matematika yag telah dibuat

 Setelah melakukan langkah-langkah diatas kemudian dilakukan tehnik

1.Menggambarkan bahwa hubungan fungsi linier dalam model matematika adalah LINIER

2.Teknik pemecahan masalah terdiri dari langkah-langkah matematika yang telah ditetapkan (program).

Setelah kedua tahap tersebut telah terselesakan kemudian dilanjutkan  dengan Model FORMULASI.

Model FORMULASI meliputi:

1. Variabel Keputusan : Simbol matematika yang menggambarkan tingkatan aktivitas perusahaan

Contoh :

x1 komputer,

x2 radio

2. Fungsi Tujuan : Hubungan matematika  linier yg menjelaskan tujuan perusahaan

Contoh:

-memaksimalkan laba

-meminimumkan biaya

3. Batasan Model : Hubungan linier dari 40 variabel-variabel keputusan

Contoh :

Hanya 40 jam tenaga kerja tersedia untuk membuat komputer

Angka 40 jam dikenal sebagai parameter.

Contoh Kasus:

1.Perusahaan Barang Tembikar memproduksi 2 produk setiap hari, yaitu mangkok dan cangkir.Perusahaan mempunyai 2 sumber daya yang terbatas jumlahnya dimana digunakan untuk memproduksi produk-produk tersebut yaitu tanah liat dan tenaga kerja.Dengan keterbatasan sumber daya, perusahaan ingin mengetahui berapa banyak mangkok dan cangkir yang akan diproduksi tiap hari dalam rangka memaksimalkan Laba.

                                                                Kebutuhan         Sumber                Daya

Produk                                                 Tenaga kerja      Tanah Liat               Laba

                                                                Jam/Unit             pon/unit               $/unit

Mangkok                                                  1                              4                        4

Cangkir                                                     2                              3                        5

Tersedia 40 jam tenaga kerja dan 120 pon tanah liat setiap hari untuk produksi

Jawab:

#variable Keputusan

-Keputusan yang dihadapi manajemen daslam masalah tadi adalah berapa banyak mangkok dan cangkir yang harus diproduksi /hari

-Jumlah yang diproduksi untuk tiap jenis produk adalah

X1 = jumlah mangkok yang diproduksi

X2 = Jumlah cangkir yang diproduksi

# Fungsi  Tujuan

-Memaksimumkan Z =4x1+5x2 dimana

Z = Total laba tiap hari

4x1= laba dari mangkok

5x2=laba dari cangkir

Batasan tenaga kerja : x1 + 2x2 ≤ 40

Batasan Tanah Liat : 4x1 = 3x2 ≤ 120

Batasan Non negatif : x1 ≥ 0 dan x2 ≥ 0

# Model FORMULASI

Memaksimumkan Z = 4x1 + 5x2

Terbatas pada

X1 + 2x2 ≤  40

4x1 + 3x2 ≤ 120

X1,x2 ≥ 0

Contoh Program linear Metode Grafik

Contoh : Perusahaan sepatu membuat 2 macam sepatu. Yang pertama merek I1, dgn sol karet, dan merek I2 dgn sol kulit. Diperlukan 3 macam mesin. Mesin 1 membuat sol karet, mesin 2 membuat sol kulit, dan mesin 3 membuat bagian atas sepatu dan melakukan assembling bagian atas dengan sol. Setiap lusin sepatu merek I1 mula-mula dikerjakan di mesin 1 selama 2 jam, kemudian tanpa melalui mesin 2 terus dikerjakan di mesin 3 selama 6 jam. Sedang untuk sepatu merek I2 tidak diproses di mesin 1, tetapi pertama kali dikerjakan di mesin 2 selama 3 jam kemudian di mesin 3 selama 5 jam. Jam kerja maksimum setiap hari mesin 1 adalah 8 jam, mesin 2 adalah 15 jam, dan mesin 3 adalah 30 jam. Sumbangan terhadap laba setiap lusin sepatu merek I1 = Rp 60.000,00 sedang merek I2 = Rp 50.000,00. Masalahnya adalah menentukan berapa lusin sebaiknya sepatu merek I1 dan merek I2 yang dibuat agar bisa memaksimumkan laba.

Bentuk Tabel dari contoh kasus diatas adalah

Variabel keputusan :

                x1 = banyaknya sepatu merk I1 yang dibuat

                x2 = banyaknya sepatu merk I2 yang dibuat

Maksimumkan Fungsi tujuan :

                                                Z = 6X1 + 5X2

Berdasarkan Kendala (constrain)             

                                (1)          2X1                                         8

                                (2)                            3X2                        15

                                (3)          6X1 + 5X2                              30

                                (4)    X1  0,  X2  0.