My Mind : Program Linear

PROGRAM LINEAR

Nama : Rizky Pratama (3115140536)

Kelas : Pendidikan Matematika Bilingual 2014

Universitas : Universitas Negeri Jakarta

Berdasarkan sejarah, program linear berkembang sebagai teknik untuk meyelesaikan masalah-masalah yang berkaitan dengan sumber alokasi barang dan material Angkatan Udara Amerika Serikat selama Perang Dunia II. Sekarang, ini program linear telah dikembangkan untuk memecahkan berbagai masalah seperti pengoptimalan jadwal penerbangan, penetapan jaringan-jaringan listrik, atau saluran-saluran telepon.

Dalam prakteknya, masalah program linear melibatkan banyak variabel dan banyak pertidaksamaan linear. Metode untuk memecahkan masalah-masalah program linear seperti ini dikembangkan kali pertama pada tahun 1947 oleh matematikawan Amerika, George B. Dantzig (1914-sekarang), dan dikenal dengan sebutan metode simpleks.

Metode ini dengan mudah dapat di adaptasi ke penyelesaian komputer. Pada tahun 1984, Narendra Karmarkar dari Bell Laboratories menemukan suatu cara yang memperbaiki kemempuan metode simpleks untuk memecahkan masalah-masalah program linear bernilai besar, dengan ribuan variabel dan ratusan pertidaksamaan linear.

Dalam tulisan ini, masalah dibatasi hanya pada program linear dengan sistem pertidaksamaan linear yang pertidaksamaan-petidaksamaan memiliki 2 variabel aja ( x dan y ). Dengan demikian, masalah, masalah program linear seperti meminimumkan biaya produksi atau biaya angkut atau memaksimalkan keuntungan, dapat dipecahkan secara sederhana dengan pendekatan grafik.

Masalah pengoptimalan selalu dikaitkan dengan kendala-kendala atau batasan-batasan yang terdapat dalam sistem tersebut. Misalkan bahan-bahan yang diperlukan ataupun peralatan yang akan digunakan. Kendala-kendala tersebut harus diterjemahkan ke dalam bentuk sistem pertidaksamaan linear. Dari sistem pertidaksaam yang terbentuk akan di peroleh 1 atau beberapa penyelesaian yang dapat memaksimalkan atau meminimalkan masalah.

1. Model Matematika

Seperti yang telah kita ketahui bahwa untuk memecahkan masalah pengoptimalan dengan program linear terdapat kendala-kendala yang harus diterjemahkan ke dalam suatu sistem pertidaksamaan linear. Pembentukan sistem pertidaksamaan linear tersebut dinamakan pemodelan matematika. Sedangkan sistem pertidaksamaan yang terbentuk adalah model matematika dari masalah program linear.

Didalam pemodelan matematika untuk masalah program linear terdapat 2 macam fungsi, yaitu fungsi tujuan atau fungsi objektifdan kendala atau batasan. Fungsi tujuan adalah fungsi yang menjelaskan tujuan atau sasaran dari pengoptimalan yang mungkin dicapai berdasarkan kendala yang ada.

CONTOH SOAL

Sebuah pabrik roti memproduksi 2 jenis roti, yaitu roti isi coklat dan roti isi keju. Pembuatan 1 buah roti isi coklat memerlukan 6 gram terigu dan 5 gram mentega, sedangkan untuk 1 buah roti isi keju memerlukan 4 gram terigu dan 5 gram mentega. Keuntungan roti isi coklat Rp550,00 perbuah dan roti isi keju Rp400,00 perbuah. Bahan yang tersedia adalah 2.400 gram terigu dan 2.500 gram mentega. Buatlah model matematika untuk permasalahan diatas, apabila banyaknya roti isi coklat x buah dan isi roti keju y buah.

PENYELESAIAN

Langkah 1

Barang yang diproduksi adalah 2 jenis roti: roti coklat dan roti keju. Mulailah dengan pemisalan. Misalkan, roti coklat yang diproduksi = x buah. Roti keju yang diproduksi = y buah. Tak mungkin membuat -2 roti sebab pernyataan seperti ini tak bermakna. Dari sini diperoleh 2 fungsi kendala yang tak mungkin negatif yaitu x ≥ 0 dan y ≥ 0

Langkah 2

Roti terbuat dari terigu dan mentega sehingga fungsi kendala berikutnya pastilah berkaitaan dengan persediaan terigu dan mentega.

1 roti coklat memerlukan 6 gr terigu dan 5 gr mentega.

X roti coklat memerlukan 6x gr terigu dan 5x gr mentega.

1 roti keju memerlukan 4 gr terigu dan 5 gr mentega

Y roti keju memerlukan 4y gr terigu dan 5y gr mentega.

Jadi, terigu yang diperlukan adalah (6x + 4y) gr dan mentega yang diperlukan adalah (5x + 5y) gr.

Persediaan terigu = 2.400 gr sehingga PtLDVnya adalah 6x + 4y ≤ 2.400

Persediaan mentega = 2.500 gr sehingga PtLDVnya adalah 5x + 5y ≤ 2.500

Langkah 3

Fungsi kendala yang diperoleh dari langkah 1 dan langkah 2 menghasilkan model matematika sebagai berikut

6x + 4y ≤ 2.400 ...(1)

5x + 5y ≤ 2.500 ...(2)

x ≥ 0 ...(3)

y ≥ 0 ...(4)

langkah 4

adapun fungsi tujuan berkaitan dengan keuntungan menjual roti isi cokelat dan roti isi keju

1 roti isi coklat memperoleh untung RP550,00

X roti isi coklat memperoleh untung 550x rupiah.

1 roti isi keju memperoleh untung RP400,00

Y 1 roti isi keju memperoleh untung 400y

Jadi, fungsi tujuan adalah = 550x + 400y. Fungsi tujuan inilah yang biasanya dimaksimalkan atau diminimumkan.

2. Menyelesaikan Masalah Program Linear

Dalam menyelesaikan masalah program linear bisa dilakukan dengan beberapa metode. Metode yang dimaksud adalah metode garis selidik untuk menentukan titik optimum dan metode titik pojok.

2.1 metode garis selidik

1. untuk masalah memaksimumkan: fungsi tujuan, geser garis selidik primitif ax + by = 0 secara sejajar sampai memotong titik paling jauh dari daerah yang memenuhi sistem pertidaksamaan linear. Titik paling jauh biasanya adalah titik pojok yang paling atas atau paling kanan dari daerah yang memotong SPtl.

2. untuk masalah meminimumkan: fungsi tujuan, geser garis selidik primitif ax + by = 0 secara sejajar sampai memotong titik paling daerah dari daerah yang memenuhi sistem pertidaksamaan linear. Titik paling dekat biasanya adalah titik pojok yang paling bawah atau paling kiri dari daerah yang memotong SPtl.

2.2 metode titik pojok

1. jika suatu masalah program linear memiliki penyelesaian maka daerah penyelesaiannya akan berada pada titik-titik pojok dari titik-titik yang mungkin. Titik-titik yang mungkin adalah titik-titik yang berada dalam daerah yang memenuhi SPtl

2. jika suatu masalah program linear memiliki banyak penyelesaian maka paling sedikit suatu penyelesaian akan berada di suatu titik pojok dari grafik titik-titik yang mungkin

Langkah-langkah untuk memecahkan masalah program linear dengan metode grafik.

1. Menentukan fungsi tujuan dan menyatakan ke dalam model matematika berupa satu persamaan dengan bentuk umum : z = ax + by, dengan a,b є R serta a ≠ 0 dan b ≠ 0.

2. Mengidentifikasi kendala serta menyatakannya ke dalam model matematika berupa sekumpulan pertidaksamaan linear dua variabel.

3. Menggambar semua garis pada fungsi kendala dalam satu koordinat Cartesius.

4. Menentukan daerah himpunan penyelesaian yang memenuhi semua pertidaksamaan linear dalam langkah 2. Daerah ini biasanya diwarnai

5. Menentukan koordinat (x,y) dari semua titik pojok dari daerah yang diwarnai dalam langkah 4.

6. Menyubstitusikan x dan y dari setiap titik pojok dalam langkah 5 ke dalam fungsi tujuan z = ax + by untuk menemukan nilai z optimum.

CONTOH SOAL

Harga sebuah baju Rp. 25.000 sedangkan sebuah celana Rp.50.000. modal yang tersisa Rp.1.500.000. kapasitas took tersebut maksimal memuat 50 buah. Tentukan model matematika untuk memperoleh keuntungan yang sebesar-besarnya, jika laba untuk baju Rp.3.000 dan untuk celana Rp.2.000?

Jawab:

1. Model matematika

Misalkan x = banyaknya baju dan y = banyaknya celana.

	Jumlah barang	harga	laba
Baju (x)	1	Rp. 25.000	Rp.3.000
Celana (y)	1	Rp.50.000	Rp.2.000
Jumlah	50	Rp.1.500.000.	F_obj

Model matematika:

· Fungsi Kendala

x + 2y ≤ 60; x+ y ≤50; x ≥ 0; y≥0

· Fungsi Objektif

F(x,y) = 3.000x + 2.000y

Daerah penyelesaian

· Bentuk persamaan dari sistem pertidaksamaan di atas adalah

x + 2y = 60; x + y =50; x = 0; y=0

· grafik persamaan di atas dalam koordinat kartesius, sebagai berikut:

titik-titik potong terhadap sumbu-x dan sumbu-y

	x + 2y = 60			x + y =80
X	0	60	X	0	50
y	30	0	y	50	0
(x,y)	(0,30)	(60,0)	(x,y)	(0, 50)	(50,0)

· daerah penyelesaiannya

misal kita ambil titik (0,0) [karena titik (0,0) di luar garis x + 2y = 60 dan x+ y =50

subtitusi (0,0) ke pertidaksamaan di atas

subtitusi (0,0) ke x + 2y ≤ 60 dan x+ y ≤50

0 + 2.0 ≤ 60 dan 0 + 0 ≤50

0 ≤ 60 dan 0 ≤50 (benar)

sehingga arsir daerah yang tidak memuat titik (0,0).

3. Titik-titik pojok dari daerah penyelesaian

A(0,0), B(50,0), C(0,30) dan D (?,?)

Titik D dapat dicari dengan mengeliminasi sistem persamaan di atas, yaitu x + 2y = 60 dan x+ y =50

x + 2y = 60
x+ y =50	-
y=10

Sehingga x+ y =50

x+ 10 =50

x = 50 – 10

x = 40

titik D(40, 10)

4. Nilai optimum

Nilai optimum( maksimum) dapat dicari dengan membandingkan hasil subtitusi

titik-titik pojok ke fungsi objektif.

Titik pojok		F(x,y) = 3.000x + 2.000y
A	(0,0)	Rp.0
B	(50,0)	Rp.150.000
C	(0,30)	Rp.60.000
D	(40,10)	Rp.140.000

Kesimpulan

Jadi titik optimumnya adalah B(50,0), dengan kata lain untuk memperoleh keuntungan yang maksimal, maka jumlah baju (x) yang dijual ialah 50 buah dan jumlah celana yang dijual 0 buah