Metode Grafik Program Linear

LINEAR

PROGRAMMING

CLASS Procedures

World’s Best Teacher

Suatu teknik perencanaan yang
bersifat analitis yang analisisnya
menggunakan model matematis,
dengan tujuan menemukan
beberapa alternatif pemecahan
optimum terhadap persoalan

Pengertian

Setiap organisasi berusaha mencapai tujuan yang telah ditetapkan sesuai dengan keterbatasan sumber daya.

Prinsip

• Pengertian, contoh masalah dan perumusan model

• Metode penyelesaian (grafik dan simpleks)

• Interpretasi hasil

• Analisis sensitivitas

• Penyimpangan-penyimpangan dari bentuk baku

• Model Dualitas

• Penyelesaian kasus (Aplikasi Paket Komputer

Model
Linear Programming

• Perbankan: portofolio investasi

• Periklanan

• Industri Manufaktur: Penggunaan mesin - kapasitas produksi

• Pengaturan komposisi bahan makanan

• Distribusi dan pengangkutan

• Penugasan Karyawan

Penerapan:

Pengalokasian

Sumber Daya

• Ada tujuan yang ingin dicapai

• Tersedia berbagai alternatif untuk mencapai tujuan

• Sumber daya dalam keadaan terbatas

• Dapat dirumuskan dalam bentuk matematika (persamaan/pertidaksamaan)

Karakteristik

Persoalan

Linear

Programming

Model
Linear

Programming

• Fungsi Tujuan:

𝑍 = 𝐶1𝑋1 + 𝐶2𝑋2 + ⋯ + 𝐶𝑛𝑋𝑛

• Batasan:

𝑎11𝑋1 + 𝑎12𝑋2 + ⋯ + 𝑎1𝑛𝑋𝑛 ≤ 𝑏1
𝑎21𝑋1 + 𝑎22𝑋2 + ⋯ + 𝑎2𝑛𝑋𝑛 ≤ 𝑏2

⋮

𝑎𝑚1𝑋1 + 𝑎𝑚2𝑋2 + ⋯ + 𝑎𝑚𝑛𝑋𝑛 ≤ 𝑏𝑚

• dan

𝑋1 ≥ 0, 𝑋2 ≥ 0, ⋯ , 𝑋𝑛 ≥ 0

Model

Matematis

• Proportionality

Naik turunnya nilai 𝑍 dan
penggunaan sumber atau fasilitas
yang tersedia akan berubah
secara sebanding (proportional)
dengan perubahan tingkat
kegiatan

Asumsu-

Asumsi Dasar

Linear

Programming

• Additivity

Nilai tujuan tiap kegiatan tidak
saling memengaruhi, atau dalam
LP dianggap bahwa kenaikan dari
nilai tujuan (𝑍) yang diakibatkan
oleh kenaikan suatu kegiatan
dapat ditambahkan tanpa
memengaruhi bagian nilai 𝑍 yang
diperoleh dari kegiatan lain.

Asumsu-

Asumsi Dasar

Linear

Programming

• Divisibility

Keluaran (output) yang dihasilkan
oleh setiap kegiatan dapat berupa
bilangan rasional, begitu pula dengan 𝑍

• Deterministic (Certainly)

Semua parameter yang terdapat
dalam model LP (𝑎𝑖𝑗, 𝑏𝑖, 𝐶𝑗) dapat
diketahui dengan pasti.

Asumsu-

Asumsi Dasar

Linear
Programming

• Grafik (2 variabel)

• Matematis (Simplex Method)

Metode

penyelesaian

masalah:

Contoh

13

Suatu perusahaan menghasilkan dua produk, meja dan kursi yang diproses melalui dua bagian fungsi: perakitan dan pemolesan.

Pada bagian perakitan tersedia 60 jam kerja, sedangkan pada bagian pemolesan hanya 48 jam kerja. Untuk menghasilkan 1 meja diperlukan 4 jam kerja perakitan dan 2 jam kerja pemolesan, sedangkan untuk menghasilkan 1 kursi diperlukan 2 jam kerja perakitan dan 4 jam kerja pemolesan,

Laba untuk setiap meja dan kursi yang dihasilkan masing-masing Rp 80.000 dan Rp 60.000

Berapa jumlah meja dan kursi yang optimal dihasilkan?

Penyelesaian

14

Perumusan persoalan dalam bentuk tabel:

Perumusan persoalan dalam bentuk kalimat matematika:

Fungis Tujuan:
𝑍 = 8𝑀 + 6𝐾 (× 10.000)

Kendala:
Perakitan: 4𝑀 + 2𝐾 ≤ 60
Pemolesan: 2𝑀 + 4𝐾 ≤ 48

𝑀 ≥ 0, 𝐾 ≥ 0

Penyelesaian

15

Gambar grafik untuk masing-masing kendala:

4𝑀 + 2𝐾 ≤ 60

𝑀

𝟎

𝟏𝟓

𝐾

30

0

2𝑀 + 4𝐾 ≤ 48

𝑀

𝟎

𝟐𝟒

𝐾

12

0

Penyelesaian

16

Gambar grafik untuk masing-masing kendala:

4𝑀 + 2𝐾 ≤ 60

𝑀

𝟎

𝟏𝟓

𝐾

30

0

2𝑀 + 4𝐾 ≤ 48

𝑀

𝟎

𝟐𝟒

𝐾

12

0

Penyelesaian

17

Gambar grafik untuk masing-masing kendala:

4𝑀 + 2𝐾 ≤ 60

𝑀

𝟎

𝟏𝟓

𝐾

30

0

2𝑀 + 4𝐾 ≤ 48

𝑀

𝟎

𝟐𝟒

𝐾

12

0

Penyelesaian

18

Gambar grafik untuk masing-masing kendala:

4𝑀 + 2𝐾 ≤ 60

𝑀

𝟎

𝟏𝟓

𝐾

30

0

2𝑀 + 4𝐾 ≤ 48

𝑀

𝟎

𝟐𝟒

𝐾

12

0

Penyelesaian

19

Gambar grafik untuk masing-masing kendala:

4𝑀 + 2𝐾 ≤ 60

𝑀

𝟎

𝟏𝟓

𝐾

30

0

2𝑀 + 4𝐾 ≤ 48

𝑀

𝟎

𝟐𝟒

𝐾

12

0

Penyelesaian

20

Gambar grafik untuk masing-masing kendala:

4𝑀 + 2𝐾 ≤ 60

𝑀

𝟎

𝟏𝟓

𝐾

30

0

2𝑀 + 4𝐾 ≤ 48

𝑀

𝟎

𝟐𝟒

𝐾

12

0

Penyelesaian

21

Gambar grafik untuk masing-masing kendala:

4𝑀 + 2𝐾 ≤ 60

𝑀

𝟎

𝟏𝟓

𝐾

30

0

2𝑀 + 4𝐾 ≤ 48

𝑀

𝟎

𝟐𝟒

𝐾

12

0

Penyelesaian

22

Gambar grafik untuk masing-masing kendala:

4𝑀 + 2𝐾 ≤ 60

𝑀

𝟎

𝟏𝟓

𝐾

30

0

2𝑀 + 4𝐾 ≤ 48

𝑀

𝟎

𝟐𝟒

𝐾

12

0

Penyelesaian

23

Gambar grafik untuk masing-masing kendala:

4𝑀 + 2𝐾 ≤ 60

𝑀

𝟎

𝟏𝟓

𝐾

30

0

2𝑀 + 4𝐾 ≤ 48

𝑀

𝟎

𝟐𝟒

𝐾

12

0

Penyelesaian

24

Gambar grafik untuk masing-masing kendala:

4𝑀 + 2𝐾 ≤ 60

𝑀

𝟎

𝟏𝟓

𝐾

30

0

2𝑀 + 4𝐾 ≤ 48

𝑀

𝟎

𝟐𝟒

𝐾

12

0

Penyelesaian

25

Titik Ekstrim:

0,12
15,0
12,6

Sehingga agar laba maksimum:
jumlah meja = 12 dan kursi = 6

Sekian

26

Multiple Choice

Wina memiliki waktu untuk membuat kerajinan 8 jam sehari. Waktu yang diperlukan Wina untuk membuat gantungan kunci (x) 15 menit dan tempelan kulkas (y) 20 menit. Model matematikanya adalah...

• 20x + 15 y $$\ge$$   480

• 15x + 20 y $$\ge$$   480

• 15x + 20 y $$\le$$  8

• 15x + 20 y $$\le$$  80

• 15x + 20 y $$\le$$    480

Multiple Choice

Daerah penyelesaian sistem pertidaksamaan $$x-2y\ge10;\ x\ge0;\ y\ge0$$  adalah ....

Multiple Choice

Daerah penyelesaian dari pertidaksamaan $$2x+3y\ge18$$  adalah ....

Multiple Choice

Berdasarkan grafik di atas, yang bukan merupakan titik-titik pojok dari Daerah Himpunan Penyelesaian tersebut adalah …

• A

• B

• C

• D

• E

Multiple Choice

Daerah himpunan penyelesaian $$4x+3y\le12,$$   $$3x+5y\le15,$$   $$x\ge0,\ y\ge0$$  adalah ....

Multiple Choice

Seorang petani memiliki lahan 1 hektar. Untuk menanam 1 pohon jagung diperlukan lahan seluas 1 m persegi dan 1 pohon kedelai seluas 0,5 m persegi. Maka model matematikanya adalah...

• 2x + y $$\le$$   20000

• x + 2y $$\le$$   20000

• 2x + y $$\ge$$    10000

• 2x + y $$\le$$   1000

• x + y $$\le$$   10000

Multiple Choice

Seorang pedagang beras menjual beras jenis I dan jenis II. Daya muat kios tidak lebih dari 6.000 kg. Harga pembelian beras jenis I Rp 12.000,00 per kg dan harga pembelian beras jenis II Rp 10.000,00. Pedagang beras mempunyai modal Rp 48.000.000,00. Jika banyak beras jenis I adalah x kg dan beras jenis II adalah y kg, model matematika dari masalah tersebut adalah ….

• x ≥ 0, y ≥ 0, x + y ≤ 6.000, 5x + 6y ≤ 24.000

• x ≥ 0, y ≥ 0, x + y ≥ 6.000, 5x + 6y ≤ 24.000

• x ≥ 0, y ≥ 0, x + y ≥ 6.000, 6x + 5y ≥ 24.000

• x ≥ 0, y ≥ 0, x + y ≤ 6.000, 6x + 5y ≥ 24.000

• x ≥ 0, y ≥ 0, x + y ≤ 6.000, 6x + 5y ≤ 24.000

Multiple Choice

Nilai maksimum dari fungsi objektif $$10x+15y$$ yang memenuhi sistem pertidaksamaan $$x+y\le4$$ ; $$x+3y\le6$$ ; $$x\ge0$$ ; $$y\ge0$$ adalah ....

• 20

• 30

• 40

• 45

• 50

Multiple Choice

Seorang pengusaha mainan anak akan membeli bebarapa boneka Batman dan Supermen, tidak lebih dari 25 buah. Harga sebuah boneka Batman Rp 60.000,00 dan sebuah bonekam Supermen Rp 80.000,00. Modal yang dimiliki Rp 1.680.000,00. Jika laba penjualan satu buah boneka Batmen Rp 20.000,00 dan satu buah boneka Supermen Rp 30.000,00 maka laba maksimumnya adalah ....

• Rp 750.000,00

• Rp 690.000,00

• Rp 630.000,00

• Rp 590.000,00

• Rp 500.000,00

Multiple Choice

Suatu perusahaan meubel memerlukan 18 unsur A dan 24 unsur B per hari. Untuk membuat barang jenis I dibutuhkan 1 unsur A dan 2 unsur B, sedangkan untuk membuat barang jenis II dibutuhkan 3 unsur A dan 2 unsur B. Jika barang jenis I dijual seharga Rp 250.000,00 per unit dan barang jenis II dijual seharga Rp 400.000,00 per unit, maka agar penjualannya mencapai maksimum, berapa banyak masing-masing barang harus dibuat?

• 6 jenis I dan 6 jenis II

• 9 jenis I dan 3 jenis II

• 3 jenis I dan 9 jenis II

• 6 jenis I

• 12 jenis II