PEMROGRAMAN LINIER: UNTUK APA, MODEL, BATASAN, APLIKASI - MATEMATIKA - 2025

The pemrograman linear adalah metode matematis yang yang digunakan untuk mengoptimalkan (memaksimalkan atau meminimalkan sesuai) fungsi yang variabel dibatasi, sebagai selama fungsi dan kendala yang linear variabel dependen.

Umumnya, fungsi yang akan dioptimalkan memodelkan situasi praktis, seperti keuntungan produsen yang input, tenaga atau mesinnya terbatas.

Gambar 1. Pemrograman linier banyak digunakan untuk mengoptimalkan keuntungan. Sumber: Piqsels.

Salah satu kasus paling sederhana adalah fungsi linier akan dimaksimalkan, yang hanya bergantung pada dua variabel, yang disebut variabel keputusan. Ini bisa berupa:

Z = k ₁ x + k ₂ y

Dengan konstanta k ₁ dan k ₂ . Fungsi ini dikenal sebagai fungsi tujuan. Tentu saja, ada situasi yang membutuhkan lebih dari dua variabel untuk dipelajari, menjadi lebih kompleks:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

Dan kendala juga dimodelkan secara matematis oleh sistem persamaan atau pertidaksamaan, yang sama liniernya pada x dan y.

Himpunan solusi dalam sistem ini disebut solusi layak atau poin layak. Dan di antara poin-poin yang layak setidaknya ada satu, yang mengoptimalkan fungsi tujuan.

Pemrograman linier dikembangkan secara independen oleh fisikawan dan matematikawan Amerika George Dantzig (1914-2005) dan ahli matematika dan ekonom Rusia Leonid Kantorovich (1912-1986) tidak lama setelah Perang Dunia II.

Metode pemecahan masalah yang dikenal sebagai metode simpleks adalah gagasan Dantzig, yang bekerja untuk Angkatan Udara AS, Universitas Berkeley dan Universitas Stanford.

Gambar 2. Matematikawan George Dantzig (kiri) dan Leonid Kantorovich (kanan). Sumber: F. Zapata.

Model pemrograman linier

Elemen-elemen yang diperlukan untuk membuat model pemrograman linier, yang cocok untuk situasi praktis, adalah:

-Fungsi objektif

Variabel keputusan

-Restrictions

Dalam fungsi tujuan, Anda menentukan apa yang ingin Anda capai. Misalnya, Anda ingin memaksimalkan keuntungan yang diperoleh dari pembuatan produk tertentu. Kemudian fungsi "keuntungan" dibentuk, sesuai dengan harga jual produk.

Dalam istilah matematika, fungsi ini dapat disingkat menggunakan notasi penjumlahan:

Z = ∑k _i x _i

Dalam persamaan ini, k _i adalah koefisien dan x _i adalah variabel keputusan.

Variabel keputusan adalah elemen sistem yang kontrolnya dimiliki dan nilainya adalah bilangan real positif. Dalam contoh yang diusulkan, variabel keputusan adalah kuantitas setiap produk yang akan diproduksi untuk memperoleh keuntungan maksimum.

Akhirnya, kami memiliki kendala, yaitu persamaan linier atau pertidaksamaan dalam hal variabel keputusan. Mereka menggambarkan batasan masalah, yang diketahui dan dapat, misalnya, jumlah bahan mentah yang tersedia di pabrik.

Jenis pembatasan

Anda dapat memiliki sejumlah M batasan, mulai dari j = 1 hingga j = M. Secara matematis, batasan ada tiga jenis:

1. A _j = ∑ a _ij . x _i
2. B _j ≥ ∑ b _ij . x _i
3. C _j ≤ ∑ c _ij . x _i

Batasan pertama adalah dari jenis persamaan linier dan artinya nilai A _j , yang diketahui, harus dihormati.

Dua batasan yang tersisa adalah pertidaksamaan linier dan itu berarti bahwa nilai yang diketahui B _j dan C _j dapat dihormati atau dilampaui, ketika simbol yang muncul ≥ (lebih besar dari atau sama dengan) atau dihormati atau tidak dilampaui, jika simbolnya ≤ (kurang dari atau sama dengan).

Contoh model

Bidang aplikasi sangat beragam, mulai dari administrasi bisnis hingga nutrisi, tetapi untuk memahami metodenya, model sederhana dari situasi praktis dengan dua variabel diusulkan di bawah ini.

Sebuah toko kue lokal terkenal dengan dua spesialisasi: kue black forest dan kue sakripantium.

Dalam persiapannya mereka membutuhkan telur dan gula. Untuk black forest Anda membutuhkan 9 butir telur dan 500 gram gula, sedangkan untuk sakripantium membutuhkan 8 butir telur dan 800 gram gula pasir. Harga jual masing-masing adalah $ 8 dan $ 10.

Masalahnya adalah: Berapa banyak kue dari setiap jenis yang harus dibuat oleh toko roti untuk memaksimalkan keuntungannya, mengetahui bahwa ia memiliki 10 kilogram gula dan 144 telur?

Variabel keputusan

Variabel keputusan adalah "x" dan "y", yang mengambil nilai nyata:

-x: jumlah kue black forest

-y: kue jenis sakripantium.

Batasan

Batasan diberikan oleh fakta bahwa jumlah kue adalah kuantitas positif dan terbatasnya jumlah bahan baku untuk menyiapkannya.

Oleh karena itu, dalam bentuk matematis, batasan tersebut berupa:

1. x ≥ 0
2. dan ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8y ≤ 10

Batasan 1 dan 2 merupakan kondisi non-negatif yang sebelumnya terpapar, dan semua ketidaksamaan yang muncul bersifat linier. Dalam batasan 3 dan 4 adalah nilai yang tidak boleh dilampaui: 144 telur dan 10 kg gula.

Fungsi objektif

Terakhir, fungsi tujuan adalah keuntungan yang diperoleh saat membuat kue black forest dalam jumlah “x” ditambah jumlah sakripantina “y”. Itu dibangun dengan mengalikan harga dengan jumlah kue yang dibuat dan menambahkan untuk setiap jenis. Ini adalah fungsi linier yang akan kita sebut G (x, y):

G = 8x + 10y

Metode solusi

Berbagai metodologi solusi termasuk metode grafis, algoritma simpleks, dan metode titik interior, untuk beberapa nama.

- Grafik atau metode geometris

Saat Anda memiliki masalah dua variabel seperti yang ada di bagian sebelumnya, batasan menentukan wilayah poligonal di bidang xy, yang disebut wilayah layak atau wilayah viabilitas.

Gambar 3. Wilayah yang layak, tempat solusi dari masalah pengoptimalan ditemukan. Sumber: Wikimedia Commons.

Wilayah ini dibangun dengan menggunakan garis-garis pembatas, yaitu garis-garis yang diperoleh dari pertidaksamaan batasan tersebut, bekerja hanya dengan tanda persamaan.

Dalam kasus toko roti yang ingin mengoptimalkan keuntungan, batasannya adalah:

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0,5 x + 0,8y = 10

Semua titik di wilayah yang dilingkupi oleh garis-garis ini adalah solusi yang mungkin, jadi ada banyak sekali dari mereka. Kecuali dalam kasus di mana wilayah yang layak ternyata kosong, dalam hal ini masalah yang diajukan tidak ada solusinya.

Untungnya untuk masalah pastry region yang layak tidak kosong, kami punya di bawah ini.

Gambar 4. Wilayah yang layak untuk masalah kue kering. Garis dengan penguatan 0 melintasi titik asal. Sumber: F. Zapata dengan Geogebra.

Solusi optimal, jika ada, ditemukan dengan bantuan fungsi tujuan. Misalnya, ketika mencoba mencari keuntungan maksimum G, kami memiliki baris berikut, yang disebut garis iso-profit:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

Dengan garis ini kita mendapatkan semua pasangan (x, y) yang memberikan keuntungan G, jadi ada keluarga garis sesuai dengan nilai G, tetapi semua dengan kemiringan yang sama -k ₁ / k ₂ , jadi mereka garis sejajar.

Solusi optimal

Sekarang, dapat ditunjukkan bahwa solusi optimal dari masalah linier selalu merupakan titik ekstrim atau puncak dari daerah yang memungkinkan. Begitu:

Jika garis yang paling dekat dengan titik asal memiliki seluruh ruas yang sama dengan wilayah yang layak, dikatakan ada solusi yang tak terbatas. Kasus ini terjadi jika kemiringan garis laba-iso sama dengan kemiringan garis lain yang membatasi wilayah tersebut.

Untuk kue kita, simpul kandidatnya adalah A, B, dan C.

- Metode simpleks Dantzig

Metode grafis atau geometris berlaku untuk dua variabel. Namun, akan lebih rumit bila ada tiga variabel, dan tidak mungkin digunakan untuk variabel yang lebih banyak.

Saat menangani masalah dengan lebih dari dua variabel, digunakan metode simpleks, yang terdiri dari serangkaian algoritma untuk mengoptimalkan fungsi tujuan. Matriks dan aritmatika sederhana sering digunakan untuk melakukan perhitungan.

Metode simpleks dimulai dengan memilih solusi yang layak dan memeriksa apakah sudah optimal. Jika ya, kami telah menyelesaikan masalah, tetapi jika tidak, kami melanjutkan ke solusi yang lebih dekat dengan pengoptimalan. Jika solusinya ada, algoritme menemukannya dalam beberapa percobaan.

Aplikasi

Pemrograman linier dan non-linier diterapkan di banyak bidang untuk membuat keputusan terbaik dalam hal pengurangan biaya dan peningkatan keuntungan, yang tidak selalu berupa uang, karena dapat diukur dalam waktu, misalnya, jika Anda ingin meminimalkan waktu yang diperlukan. untuk melakukan serangkaian operasi.

Berikut beberapa bidang:

-Dalam pemasaran digunakan untuk menemukan kombinasi terbaik dari media (jejaring sosial, televisi, pers dan lain-lain) untuk mengiklankan produk tertentu.

-Untuk penugasan tugas yang memadai kepada personel perusahaan atau pabrik atau jadwal kepada mereka.

-Dalam pemilihan makanan yang paling bergizi dan dengan biaya terendah dalam industri peternakan dan unggas.

Latihan terselesaikan

- Latihan 1

Pecahkan secara grafis model pemrograman linier yang dimunculkan di bagian sebelumnya.

Larutan

Anda perlu membuat grafik kumpulan nilai yang ditentukan oleh sistem batasan yang ditentukan dalam masalah:

1. x ≥ 0
2. dan ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8y ≤ 10

Wilayah yang diberikan oleh pertidaksamaan 1 dan 2 sesuai dengan kuadran pertama bidang Kartesius. Mengenai pertidaksamaan 3 dan 4, kita mulai dengan mencari garis pembatas:

9x + 8y = 144

0,5 x + 0,8y = 10 → 5x + 8y = 100

Daerah yang layak adalah segiempat yang simpulnya adalah titik A, B, C, dan D.

Keuntungan minimum adalah 0, oleh karena itu garis 8x + 10y = 0 adalah batas bawah dan garis keuntungan-iso memiliki kemiringan -8/10 = - 0,8.

Nilai ini berbeda dari kemiringan garis pembatas lainnya dan karena wilayah yang memungkinkan dibatasi, solusi unik ada.

Gambar 5. Solusi grafis dari latihan 1, menunjukkan daerah yang layak dan titik solusi C di salah satu simpul dari daerah tersebut. Sumber: F. Zapata.

Solusi ini sesuai dengan garis kemiringan -0,8 yang melewati salah satu titik A, B atau C, yang koordinatnya adalah:

A (11; 5.625)

B (0; 12,5)

C (16, 0)

Solusi optimal

Kami menghitung nilai G untuk masing-masing poin ini:

- (11; 5,625): G _A = 8 x 11 + 10 x 5,625 = 144,25

- (0; 12,5): G _B = 8 x 0 + 10 x 12,5 = 125

- (16, 0): G _C = 8 x 16 + 10 x 0 = 128

Keuntungan tertinggi ditemukan pada pembuatan 11 kue black forest dan 5.625 kue sakripantium. Solusi ini sesuai dengan yang ditemukan melalui perangkat lunak.

- Latihan 2

Verifikasi hasil latihan sebelumnya dengan menggunakan fungsi Solver yang tersedia di sebagian besar spreadsheet seperti Excel atau LibreOffice Calc, yang menggabungkan algoritme Simplex untuk pengoptimalan dalam pemrograman linier.

Larutan

Gambar 6. Detail solusi dari latihan 1 melalui spreadsheet Libre Office Calc. Sumber: F. Zapata.

Gambar 7. Detail solusi dari latihan 1 melalui spreadsheet Libre Office Calc. Sumber: F. Zapata.

Referensi

1. Cemerlang. Pemrograman Linear. Diperoleh dari: brillian.org.
2. Eppen, G. 2000. Riset Operasi dalam Ilmu Administrasi. 5. Edisi. Prentice Hall.
3. Haeussler, E. 1992. Matematika untuk Manajemen dan Ekonomi. 2nd. Edisi. Grupo Editorial Iberoamericana.
4. Hiru.eus. Pemrograman linier. Diperoleh dari: hiru.eus.
5. Wikipedia. Pemrograman linier. Diperoleh dari: es. wikipedia.org.