Masalah Pemrograman Linier, Solusi & Aplikasi [Dengan Contoh]

Ilmu data memiliki banyak aplikasi, salah satunya yang paling menonjol adalah optimasi. Kita semua cenderung fokus pada pengoptimalan hal-hal. Pengoptimalan berfokus untuk mendapatkan hasil yang paling diinginkan dengan sumber daya terbatas yang Anda miliki.

Ada berbagai macam masalah optimasi yang tersedia, ada yang kecil, ada yang sangat rumit. Saat menelusurinya, Anda akan menemukan kategori khusus yang disebut masalah pemrograman linier. Dalam artikel ini, kami telah membahas apa itu dan bagaimana Anda dapat mengatasinya.

Misalkan Anda seorang penjual buah yang bisa membeli jeruk atau apel atau kombinasi keduanya. Namun Anda hanya memiliki anggaran sebesar INR 5.000 dan Anda hanya dapat menyimpan 30 tas saja. Sekarang, Anda harus membelinya dengan cara yang menghasilkan keuntungan tertinggi bagi Anda.

Sekarang satu kantong jeruk berharga INR 500 sedangkan sekantong apel berharga INR 750. Anda dapat menghasilkan INR 100 dari penjualan satu kantong jeruk dan INR 200 dari penjualan satu kantong apel.

Masalah ini memiliki berbagai kemungkinan. Anda mungkin memilih untuk hanya membeli jeruk tetapi kemudian, Anda hanya memiliki 10 kantong di penyimpanan Anda dan keuntungan Anda akan menjadi INR 1000. Demikian pula, Anda mungkin memilih untuk hanya membeli apel dan menghasilkan INR 1500 sebagai keuntungan. Anda juga dapat membeli kombinasi keduanya.

Masalah seperti itu disebut masalah pemrograman linier dan kita akan membahasnya secara rinci. Mari kita mulai:

Apa itu Pemrograman Linier?

Pemrograman linier adalah metode untuk menggambarkan hubungan yang kompleks dengan menggunakan fungsi linier. Tujuan kami dengan pemrograman linier adalah untuk menemukan solusi yang paling cocok untuk fungsi-fungsi tersebut. Hubungan nyata antara dua titik bisa sangat kompleks, tetapi kita dapat menggunakan pemrograman linier untuk menggambarkannya dengan sederhana. Pemrograman linier menemukan aplikasi di banyak industri.

Dasar-dasar Pemrograman Linier

Berikut adalah beberapa istilah dasar pemrograman linier:

Paksaan

Keterbatasan (atau batasan) dari variabel keputusan Anda disebut batasan. Sebagian besar kendala waktu adalah keterbatasan yang Anda miliki pada sumber daya Anda untuk memecahkan masalah.

Variabel Keputusan

Variabel ini menentukan output Anda. Hasil Anda bergantung pada variabel-variabel ini, itulah sebabnya kami menyebutnya 'variabel keputusan'.

Pembatasan Non-negatif

Variabel keputusan dari masalah program linier hanya dapat memiliki nilai non-negatif. Ini berarti nilai untuk variabel keputusan Anda bisa sama dengan atau lebih besar dari nol saja.

Fungsi objektif

Fungsi tujuan adalah tujuan membuat keputusan Anda. Secara sederhana ini adalah hasil akhir dari masalah pemrograman linier Anda. Misalnya, ketika Anda menemukan keuntungan maksimum yang dapat Anda hasilkan dengan serangkaian sumber daya tertentu, keuntungan maksimum adalah fungsi tujuan.

Merumuskan Masalah Pemrograman Linier

Anda harus tahu bagaimana merumuskan program linier untuk menerapkannya dalam kehidupan nyata. Misalkan Anda adalah produsen mainan dan Anda hanya memproduksi dua mainan: A dan B. Secara kasar, mainan Anda membutuhkan dua sumber daya X dan Y untuk diproduksi. Berikut adalah persyaratan mainan Anda:

• Satu unit mainan A membutuhkan satu unit sumber daya X dan tiga unit sumber daya Y

• Satu unit mainan B membutuhkan satu unit sumber daya X dan dua unit sumber daya Y

Anda memiliki lima unit sumber daya X dan 12 unit sumber daya Y. Margin keuntungan Anda atas penjualan mainan ini adalah:

• INR 6 untuk setiap unit mainan A yang terjual
• INR 5 untuk setiap unit mainan B yang terjual

Berapa unit setiap mainan yang akan Anda hasilkan untuk mendapatkan keuntungan maksimum?

Solusinya

Mari kita nyatakan masalah pemrograman linier kita dalam sebuah persamaan:

Z = 6a + 5b

Di sini, z adalah singkatan dari total keuntungan, a adalah jumlah total mainan A unit dan b singkatan dari jumlah total ke unit B. Tujuan kami adalah untuk memaksimalkan nilai Z (keuntungan).

Sekarang, perusahaan Anda ingin memproduksi sebanyak mungkin unit mainan ini, tetapi Anda memiliki sumber daya yang terbatas. Keterbatasan sumber daya kami adalah kendala dari masalah ini. Kami hanya memiliki total

a + b 5

Sekarang setiap unit mainan A dan B masing-masing membutuhkan 3 dan 2 unit sumber daya Y. Dan kami hanya memiliki total 12 unit sumber daya Y sehingga secara matematis, akan terlihat seperti ini:

3a + 2b 12

Ingatlah bahwa nilai satuan mainan A hanya dapat berupa bilangan bulat. Ini berarti kita juga memiliki batasan a->0 dan b<-0.

Jadi, sekarang Anda memiliki masalah pemrograman linier yang tepat. Anda dapat merumuskan masalah pemrograman linier lainnya dengan mengikuti contoh ini. Meskipun contoh ini cukup sederhana, masalah LP bisa menjadi sangat rumit.

Baca: Ide & Topik Proyek Pemrograman Linier

Langkah-Langkah Merumuskan Masalah Pemrograman Linier

Untuk merumuskan masalah pemrograman linier, ikuti langkah-langkah berikut:

• Temukan variabel keputusan
• Tentukan fungsi tujuan
• Mengidentifikasi kendala
• Ingat batasan non-negatif

Jika suatu masalah memenuhi kriteria di atas, itu adalah masalah pemrograman linier. Ini adalah praktik terbaik untuk mengingat kriteria ini ketika Anda sedang berusaha mengidentifikasi jenis masalah.

Memecahkan Masalah Pemrograman Linier dengan R

Jika Anda menggunakan R, menyelesaikan masalah pemrograman linier menjadi jauh lebih sederhana. Itu karena R memiliki paket lpsolve yang hadir dengan berbagai fungsi yang dirancang khusus untuk memecahkan masalah tersebut. Sangat mungkin bahwa Anda akan sangat sering menggunakan R untuk menyelesaikan masalah LP sebagai ilmuwan data. Itulah mengapa kami membagikan dua contoh berbeda untuk membantu Anda memahami penerapannya dengan lebih baik:

Contoh

Mari kita mulai dengan masalah dasar. Sebuah organisasi memiliki dua produk dengan harga jual INR 25 dan INR 20 dan masing-masing disebut produk A dan B. Setiap hari, mereka memiliki 1800 unit sumber daya untuk memproduksi produk ini. Produk A membutuhkan 20 unit sumber daya dan B membutuhkan 12 unit sumber daya. Waktu produksi untuk kedua produk ini adalah empat menit dan organisasi mendapatkan total delapan jam kerja setiap hari. Permasalahannya, berapakah jumlah produksi untuk masing-masing produk tersebut untuk memaksimalkan keuntungan perusahaan?

Larutan:

Kami akan mulai memecahkan masalah ini dengan mendefinisikan fungsi tujuannya:

maks(Penjualan) = maks( 25 y 1 + 20 y 2 )

Di sini, 25 dan 20 masing-masing adalah harga produk A dan B, y1 adalah total unit produk A yang diproduksi dan y2 adalah total unit produk B yang diproduksi. Variabel keputusan kami adalah y1 dan y2.

Sekarang kita akan menetapkan batasan untuk masalah kita:

Batasan sumber daya:

20 tahun 1 + 12 tahun 2 1800

Kendala waktu:

4 tahun 1 + 4 tahun 2 8*60

Kami bertujuan untuk menemukan jumlah produk yang benar yang harus kami produksi untuk mendapatkan keuntungan maksimal.

Menggunakan R untuk Memecahkan Masalah:

Kami akan menggunakan lpsolve untuk menyelesaikan masalah LP ini dan mulai dengan menetapkan fungsi tujuan:

> membutuhkan(lpSolve)

Memuat paket yang diperlukan: lpSolve

> objektif.dalam <- c(25, 20)

> objektif.in

[1] 25 20

Kemudian kita akan membangun matriks untuk kendala:

> const <- matriks(c(20, 12, 4, 4), nrow=2, byrow=TRUE)

> konstan

[,1] [,2]

[1,] 20 12

[2,] 4 4

> batasan_waktu <- (8*60)

> resource_constraints <- 1800

> batasan_waktu

[1] 480

> resource_constraints

[1] 1800

Sekarang mari kita buat persamaan yang sudah ditentukan:

> rhs <- c(resource_constraints, time_constraints)

> rhs

[1] 1800 480

> arah <- c(“<=”, “<=”)

> arah

[1] “<=” “<=”

Setelah semua informasi yang diperlukan ditambahkan, kita dapat mulai menemukan jawaban yang optimal. Sintaks untuk paket kami adalah:

lp( arah, tujuan, const.mat, const.dir, const.rhs )

> optimum <- lp(direction=”max”, objective.in, const, direction, rhs)

> optimal

Berhasil: fungsi tujuannya adalah 2625

> ringkasan (optimal)

Mode Kelas Panjang

arah 1 -tidak ada- numerik

x.hitung 1 -tidak ada- numerik

tujuan 2 -tidak ada- numerik

const.count 1 -none- numerik

kendala 8 -none- numerik

int.hitung 1 -none- numerik

int.vec 1 -none- numerik

bin.count 1 -none- numerik

binary.vec 1 -none- numerik

num.bin.solns 1 -none- numerik

objval 1 -none- numerik

solusi 2 -tidak ada- numerik

selesaikan 1 -none- numerik

compute.sens 1 -none- numerik

sens.coef.from 1 -none- numeric

sens.coef.to 1 -none- numeric

ganda 1 -tidak ada- numerik

ganda.dari 1 -none- numerik

duals.to 1 -none- numerik

skala 1 -tidak ada- numerik

gunakan.padat 1 -none- numerik

density.col 1 -none- numerik

padat.val 1 -none- numerik

density.const.nrow 1 -none- numeric

padat.ctr 1 -none- numerik

gunakan.rw 1 -none- numerik

tmp 1 -tidak ada- karakter

status 1 -tidak ada- numerik

Setelah menjalankan kode di atas, Anda bisa mendapatkan solusi yang diinginkan untuk masalah kita.

Nilai optimum untuk y1 dan y2:

Ingat bahwa y1 dan y2 adalah unit produk A dan produk B yang harus kita produksi:

> optimal$solusi

[1] 45 75

Angka penjualan optimal:

Keuntungan maksimum yang dapat kita hasilkan dengan nilai y1 dan y2 yang diperoleh adalah:

> optimal$objval

[1] 2625

Baca Juga: Aljabar Linier Untuk Pembelajaran Mesin

Penggunaan Pemrograman Linier

Seperti yang kami sebutkan sebelumnya, pemrograman linier menemukan aplikasi di banyak industri. Berikut adalah beberapa area di mana kami menggunakannya:

• Dengan meningkatnya popularitas layanan pengiriman, pemrograman linier telah menjadi salah satu metode yang paling disukai untuk menemukan rute yang optimal. Saat Anda menggunakan Ola atau Uber, perangkat lunak akan menggunakan pemrograman linier untuk menemukan rute terbaik. Perusahaan pengiriman seperti Amazon dan FedEx juga menggunakannya untuk menentukan rute terbaik bagi petugas pengiriman mereka. Mereka fokus pada pengurangan waktu dan biaya pengiriman.
• Pembelajaran terawasi pembelajaran mesin bekerja pada konsep dasar pemrograman linier. Dalam pembelajaran terawasi, Anda harus menemukan model matematika yang optimal untuk memprediksi output sesuai dengan data input yang disediakan.
• Sektor ritel menggunakan program linier untuk mengoptimalkan ruang rak. Dengan begitu banyak merek dan produk yang tersedia, menentukan di mana menempatkannya di toko adalah tugas yang sangat ketat. Penempatan produk di toko dapat sangat mempengaruhi penjualannya. Rantai ritel besar seperti Big Bazaar, Reliance, Walmart, dll. menggunakan program linier untuk menentukan penempatan produk. Mereka harus tetap memperhatikan kepentingan konsumen sambil memastikan penempatan produk yang terbaik untuk menghasilkan keuntungan yang maksimal.
• Perusahaan menggunakan program linier untuk meningkatkan rantai pasokan mereka. Efisiensi rantai pasokan bergantung pada banyak faktor seperti rute yang dipilih, pengaturan waktu, dll. Dengan menggunakan program linier, mereka dapat menemukan rute, pengaturan waktu, dan alokasi sumber daya terbaik lainnya untuk mengoptimalkan efisiensinya.

Pelajari Lebih Lanjut tentang Pemrograman Linier dan Ilmu Data

Pemrograman linier adalah salah satu konsep yang paling penting dari ilmu data. Ini juga merupakan topik mendasar yang harus Anda ketahui untuk menjadi ilmuwan data yang mahir. Seperti yang telah kita bahas, ada banyak aplikasi untuk konsep ini dan Anda dapat menemukan kasus penggunaannya dalam kehidupan sehari-hari Anda.

Anda dapat mempelajari lebih lanjut tentang ilmu data dan konsep terkaitnya, dengan mengunjungi blog kami. Kami memiliki banyak sumber daya berharga untuk membantu Anda mempelajari lebih lanjut. Berikut adalah beberapa untuk bacaan Anda lebih lanjut:

• Alasan Utama untuk menjadi Ilmuwan Data
• Algoritma Yang Harus Diketahui Setiap Ilmuwan Data
• Bagaimana Menjadi Ilmuwan Data

Di sisi lain, Anda bisa mendapatkan kursus ilmu data untuk belajar dari pakar industri. Anda akan belajar secara interaktif melalui video, kuis, dan proyek. Mengambil kursus akan membantu Anda mempelajari keterampilan yang diperlukan untuk menjadi ilmuwan data profesional. Lihat PG Diploma IIIT-B & upGrad dalam Ilmu Data yang dibuat untuk profesional yang bekerja dan menawarkan 10+ studi kasus & proyek, lokakarya praktis, bimbingan dengan pakar industri, 1-on-1 dengan mentor industri, 400+ jam pembelajaran dan bantuan pekerjaan dengan perusahaan-perusahaan top.