Pemrograman Linier (1)

Pemrograman Linier (1) Bentuk umum dan solusi dengan metode grafis

Ahmad Sabri Universitas Gunadarma, Indonesia

1

Pemrograman Linier (1)

Komponen pada Pemrograman Linier (PL)

Model PL memiliki tiga komponen dasar: Variabel keputusan yang akan dicari nilainya Objektif yang akan dicari nilai optimalnya (maksimal atau minimal) Kendala yang dihadapi dalam mencapai objektif optimal.

2


Data yang dibutuhkan untuk model LP: pengalokasian sumberdaya untuk berbagai aktivitas

Sumber daya 1 2 .. . m Kontribusi pada Z per unit aktivitas

Penggunaan sumberdaya per unit aktivitas Aktivitas 1 2 ... n a11 a12 . . . a1n a21 a22 . . . a2n ... am1

... am2

... ...

... amn

c1

c2

...

cn

Banyaknya sumber daya tersedia b1 b2 .. . bm

3


Bentuk umum model PL

Bentuk umum model PL maksimum Maks Z = c1 x1 + c2 x2 + . . . + cn xn Dengan kendala: a11 x1 + a12 x2 + . . . + a1n xn a21 x1 + a22 x2 + . . . + a2n xn .. . am1 x1 + am2 x2 + . . . + amn xn

≤ ≤ .. .

b1 b2 .. .

≤

bm

xi ≥ 0, i = 1, 2, . . . n.

4


Bentuk umum model PL

Bentuk umum model PL minimum Min Z = c1 x1 + c2 x2 + . . . + cn xn Dengan kendala: a11 x1 + a12 x2 + . . . + a1n xn a21 x1 + a22 x2 + . . . + a2n xn .. . am1 x1 + am2 x2 + . . . + amn xn

≥ ≥ .. .

b1 b2 .. .

≥

bm

xi ≥ 0, i = 1, 2, . . . n.

5


Istilah-istilah terkait solusi dari model Solusi layak: solusi di mana semua kendala terpenuhi Solusi tidak layak: solusi di mana paling sedikit sebuah kendala dilanggar Daerah solusi layak: kumpulan dari semua solusi layak Solusi optimal: solusi layak yang memiliki nilai objektif terbaik (yaitu nilai terbesar untuk problem maksimisasi, dan nilai terkecil untuk problem minimisasi). Solusi optimal berganda: terdapat tak-hingga kemungkinan solusi yang memberikan fungsi objektif bernilai sama. Tidak ada solusi optimal: terjadi jika (1) tidak terdapat solusi layak, atau (2) nilai fungsi objektif selalu dapat diperbesar tanpa melanggar kendala (kasus kedua ini disebut unbounded objective function). 6












Metode penyelesaian PL

Terdapat dua metode untuk penyelesaian model PL: 1

Metode grafik (untuk model dengan dua variabel)

2

Metode simpleks (untuk model dengan dua variabel atau lebih)

7


Metode grafik

Penyelesaian model PL dengan metode grafik mencakup dua langkah: 1

Menentukan daerah solusi layak (feasible solution region)

2

Menentukan solusi optimal dari semua titik layak (feasible points) pada daerah solusi layak.

8


Karakteristik dari solusi optimal

Solusi optimal dari sebuah model PL selalu diasosiasikan sebagai sebuah titik sudut pada daerah solusi (yaitu titik di mana dua garis berpotongan). Jika terdapat dua titik sudut yang memberikan solusi optimal, maka seluruh titik pada ruas garis yang menghubungkan kedua titik tersebut juga memberikan solusi optimal.

9


Karakteristik dari solusi optimal

Solusi optimal dari sebuah model PL selalu diasosiasikan sebagai sebuah titik sudut pada daerah solusi (yaitu titik di mana dua garis berpotongan). Jika terdapat dua titik sudut yang memberikan solusi optimal, maka seluruh titik pada ruas garis yang menghubungkan kedua titik tersebut juga memberikan solusi optimal.

9


Contoh Sebuah rumah produksi coklat memiliki 2 jenis produksi coklat: coklat hand-made dan coklat machine-made. Pengalokasian sumber daya untuk setiap adonan produk diberikan oleh data berikut:

Sumber daya Manusia Mesin Keuntungan per unit adonan

Penggunaan sumberdaya per unit adonan (jam) Adonan Coklat mesin Coklat hand-mande (M) (H) 4 18 12 6 55

Ketersediaan sumber daya (jam) 1296 1824

89

Perusahaan ingin menentukan berapa unit adonan coklat mesin dan coklat hand-made yang harus diproses agar diperoleh keuntungan semaksimal mungkin. Buatlah model PL-nya dan tentukan solusi optimalnya!

10


Variabel keputusan dan model PL untuk problem ini adalah: M : unit adonan coklat buatan mesin H: unit adonan coklat buatan tangan Maks Z = 55M + 89H Dengan kendala: 4M + 18H 12M + 6H M, H ≥ 0

≤ ≤

1296 1824

11


Daerah solusi dari model tersebut

12


Berdasarkan daerah solusi layak, kemungkinan solusi optimal diberikan oleh 4 titik sudut: (0 , 0), (0 , 72), (130.5 , 43) dan (152 , 0). Berikut nilai Z = 55M + 89H untuk setiap titik sudut: (M, H) (0, 0) (0, 72) (130.5, 43) (152, 0)

Z = 55M + 89H 0 6408 11004.5 8360

(maksimum)

Diperoleh solusi optimal Z = 11004.5, dengan M = 130.5 dan H = 43.

13


Contoh Redi Mix memproduksi cat interior dan eksterior dari dua bahan mentah: M1 dan M2. Tabel berikut memberikan data dasar:

M1 M2 Keuntungan per ton (juta)

Kebutuhan bahan mentah untuk per ton dari Cat eksterior (ton) Cat interior (ton) 6 4 1 2 5

Ketersediaan maksimum harian (ton) 24 6

4

Survey pemasaran menunjukkan bahwa permintaan harian untuk cat interior maksimal 1 ton lebih banyak dari yang untuk eksterior. Juga, permintaan harian maksimum untuk cat interior adalah 2 ton. Redi Miks ingin menentukan berapa ton cat interior dan eksterior harus diproduksi untuk memaksimalkan keuntungan harian. Buatlah model PL-nya dan tentukan solusi optimalnya! (diadaptasi dari Operational Research, Hamdy Taha)

14

Pemrograman Linier (1)

Recommend Documents