PENGATURCARAAN LINEAR: UNTUK APA, MODEL, KEKANGAN, APLIKASI - MATEMATIK - 2025

The pengaturcaraan linear adalah satu kaedah matematik yang adalah digunakan untuk mengoptimumkan (memaksimumkan atau meminimumkan sebagaimana yang sesuai) fungsi yang pembolehubah adalah terhad, kerana selagi fungsi dan kekangan adalah linear pembolehubah bersandar.

Umumnya, fungsi yang akan dioptimalkan memodelkan situasi praktikal, seperti keuntungan pengilang yang input, tenaga kerja atau mesinnya terbatas.

Gambar 1. Pengaturcaraan linier banyak digunakan untuk mengoptimumkan keuntungan. Sumber: Piqsels.

Salah satu kes yang paling sederhana adalah fungsi linear untuk dimaksimumkan, yang hanya bergantung pada dua pemboleh ubah, yang disebut pemboleh ubah keputusan. Ia boleh berbentuk:

Z = k ₁ x + k ₂ y

Dengan pemalar k ₁ dan k ₂ . Fungsi ini dikenali sebagai fungsi objektif. Sudah tentu, ada situasi yang memerlukan lebih daripada dua pemboleh ubah untuk belajar, menjadi lebih kompleks:

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

Kekangan juga dimodelkan secara matematik oleh sistem persamaan atau ketaksamaan, sama linear dalam x dan y.

Kumpulan penyelesaian dalam sistem ini disebut penyelesaian yang layak atau titik yang boleh dilaksanakan. Dan di antara titik-titik yang mungkin ada sekurang-kurangnya satu, yang mengoptimumkan fungsi objektif.

Pengaturcaraan linear dikembangkan secara bebas oleh ahli fizik dan matematik Amerika George Dantzig (1914-2005) dan ahli matematik dan ekonomi Rusia Leonid Kantorovich (1912-1986) sejurus selepas Perang Dunia II.

Kaedah penyelesaian masalah yang dikenali sebagai kaedah simplex adalah anak sulung Dantzig, yang bekerja untuk Tentera Udara AS, Universiti Berkeley, dan Universiti Stanford.

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

Model pengaturcaraan linear

Unsur-unsur yang diperlukan untuk mewujudkan model pengaturcaraan linear, sesuai untuk keadaan praktikal, adalah:

-Fungsi objektif

-Pemboleh ubah keputusan

-Sekat

Dalam fungsi objektif anda menentukan apa yang ingin anda capai. Sebagai contoh, andaikan anda ingin memaksimumkan keuntungan yang dihasilkan dari pembuatan produk tertentu. Kemudian fungsi "keuntungan" ditetapkan, sesuai dengan harga di mana produk tersebut dijual.

Dalam istilah matematik, fungsi ini dapat disingkat dengan menggunakan notasi penjumlahan:

Z = ∑k _i x _i

Dalam persamaan ini, k _i adalah pekali dan x _i adalah pemboleh ubah keputusan.

Pemboleh ubah keputusan adalah unsur sistem yang kawalannya ada dan nilainya adalah nombor nyata positif. Dalam contoh yang dicadangkan, pemboleh ubah keputusan adalah kuantiti setiap produk yang akan dihasilkan untuk memperoleh keuntungan maksimum.

Akhirnya, kita mempunyai kekangan, yang merupakan persamaan linear atau ketaksamaan dari segi pemboleh ubah keputusan. Mereka menerangkan batasan masalah, yang diketahui dan dapat, misalnya, jumlah bahan mentah yang ada dalam pembuatannya.

Jenis sekatan

Anda boleh mempunyai had M sebanyak, bermula dari j = 1 hingga j = M. Batasan matematik adalah tiga jenis:

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

Sekatan pertama adalah dari jenis persamaan linear dan bermaksud bahawa nilai A _j , yang diketahui, harus dihormati.

Dua batasan yang tinggal adalah ketaksamaan linear dan ini bermaksud bahawa nilai yang diketahui B _j dan C _j dapat dihormati atau dilampaui, apabila simbol yang muncul adalah ≥ (lebih besar dari atau sama dengan) atau dihormati atau tidak dilampaui, jika simbolnya ≤ (kurang daripada atau sama dengan).

Contoh model

Bidang aplikasi sangat beragam, mulai dari pentadbiran perniagaan hingga pemakanan, tetapi untuk memahami kaedahnya, model sederhana dari situasi praktikal dengan dua pemboleh ubah dicadangkan di bawah.

Sebuah kedai pastri tempatan terkenal dengan dua kepakaran: kek hutan hitam dan kue sacripantine.

Dalam penyediaannya, mereka memerlukan telur dan gula. Untuk hutan hitam, anda memerlukan 9 telur dan 500 g gula, sementara untuk sacripantine anda memerlukan 8 telur dan 800 g gula. Harga jualan masing-masing adalah $ 8 dan $ 10.

Masalahnya ialah: Berapa banyak kek setiap jenis yang mesti dibuat roti untuk memaksimumkan keuntungannya, mengetahui bahawa ia mempunyai 10 kilogram gula dan 144 telur?

Pemboleh ubah keputusan

Pemboleh ubah keputusan adalah "x" dan "y", yang mengambil nilai sebenar:

-x: bilangan kek hutan hitam

-y: kek jenis sacripantine.

Sekatan

Sekatan tersebut diberikan oleh fakta bahawa jumlah kuih muih adalah kuantiti positif dan terdapat sejumlah kecil bahan mentah untuk menyediakannya.

Oleh itu, dalam bentuk matematik, sekatan ini berbentuk:

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

Kekangan 1 dan 2 merupakan keadaan tidak negatif yang terdedah sebelumnya, dan semua ketaksamaan yang dibangkitkan adalah linear. Dalam sekatan 3 dan 4 adalah nilai yang tidak boleh melebihi: 144 telur dan 10 kg gula.

Fungsi objektif

Akhirnya, fungsi objektif adalah keuntungan yang diperoleh semasa pembuatan kuih hutan hitam "x" ditambah kuantiti sakripantina "y". Ia dibina dengan mengalikan harga dengan kuantiti kek yang dibuat dan menambahkan untuk setiap jenis. Ini adalah fungsi linear yang akan kita panggil G (x, y):

G = 8x + 10y

Kaedah penyelesaian

Berbagai metodologi penyelesaian merangkumi kaedah grafik, algoritma simplex, dan kaedah titik dalaman, untuk beberapa nama.

- Kaedah grafik atau geometri

Apabila anda mempunyai masalah dua pemboleh ubah seperti yang terdapat di bahagian sebelumnya, kekangan menentukan kawasan poligonal di satah xy, yang disebut wilayah layak atau kawasan daya maju.

Gambar 3. Kawasan yang dapat dilaksanakan, di mana penyelesaian masalah pengoptimuman dijumpai. Sumber: Wikimedia Commons.

Wilayah ini dibina menggunakan garis larangan, yang merupakan garis yang diperoleh dari ketaksamaan sekatan, hanya berfungsi dengan tanda persamaan.

Bagi kedai roti yang ingin mengoptimumkan keuntungan, garis kekangannya adalah:

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0.5 x + 0.8y = 10

Semua titik di wilayah yang diliputi oleh garis-garis ini adalah penyelesaian yang mungkin, jadi terdapat banyak dari mereka. Kecuali dalam keadaan di mana wilayah yang layak ternyata kosong, dalam hal ini masalah yang diajukan tidak dapat diselesaikan.

Nasib baik, untuk masalah pastri kawasan yang layak tidak kosong, kami ada di bawah.

Rajah 4. Kawasan yang boleh dilaksanakan untuk masalah pastri. Garis dengan keuntungan 0 melintasi asal. Sumber: F. Zapata dengan Geogebra.

Penyelesaian optimum, jika ada, dijumpai dengan bantuan fungsi objektif. Contohnya, ketika berusaha mencari keuntungan maksimum G, kita mempunyai baris berikut, yang disebut garis keuntungan-iso:

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

Dengan garis ini kita memperoleh semua pasangan (x, y) yang memberikan keuntungan G yang diberikan, jadi ada sekelompok garis sesuai dengan nilai G, tetapi semuanya dengan kemiringan yang sama -k ₁ / k ₂ , jadi mereka garis selari.

Penyelesaian yang optimum

Sekarang, dapat ditunjukkan bahawa penyelesaian masalah linear yang optimum selalu merupakan titik ekstrem atau titik puncak wilayah yang dapat dilaksanakan. Jadi:

Sekiranya garis yang paling dekat dengan asal mempunyai kesamaan seluruh segmen dengan wilayah yang dapat dilaksanakan, dikatakan bahawa ada penyelesaian yang tidak terbatas. Kes ini berlaku sekiranya kemerosotan garis iso-untung sama dengan garis lain yang membatasi wilayah.

Untuk pastri kami, simpul calon adalah A, B, dan C.

- Kaedah simplex Dantzig

Kaedah grafik atau geometri boleh digunakan untuk dua pemboleh ubah. Namun, lebih rumit apabila terdapat tiga pemboleh ubah, dan mustahil digunakan untuk sebilangan besar pemboleh ubah.

Ketika menangani masalah dengan lebih dari dua pemboleh ubah, metode simplex digunakan, yang terdiri dari serangkaian algoritma untuk mengoptimumkan fungsi objektif. Matrik dan aritmetik sederhana sering digunakan untuk menjalankan pengiraan.

Kaedah simplex dimulakan dengan memilih penyelesaian yang layak dan memeriksa apakah kaedah itu optimum. Jika ya, kita sudah menyelesaikan masalahnya, tetapi jika tidak, kita terus menuju ke arah penyelesaian yang lebih dekat dengan pengoptimuman. Sekiranya penyelesaiannya ada, algoritma mencarinya dalam beberapa percubaan.

Permohonan

Pengaturcaraan linier dan tidak linier diterapkan dalam banyak bidang untuk membuat keputusan terbaik dari segi mengurangkan kos dan meningkatkan keuntungan, yang tidak selalu berupa wang, kerana dapat diukur pada waktunya, misalnya, jika anda ingin meminimumkan waktu yang diperlukan. untuk menjalankan satu siri operasi.

Berikut adalah beberapa bidang:

-Dalam pemasaran digunakan untuk mencari kombinasi media terbaik (jaringan sosial, televisyen, akhbar dan lain-lain) untuk mengiklankan produk tertentu.

-Untuk memberikan tugas yang mencukupi kepada kakitangan syarikat atau kilang atau jadual kepada mereka.

-Dalam pemilihan makanan yang paling berkhasiat dan dengan kos terendah dalam industri ternakan dan unggas.

Latihan yang diselesaikan

- Latihan 1

Secara grafik menyelesaikan model pengaturcaraan linear yang dibangkitkan pada bahagian sebelumnya.

Penyelesaian

Adalah perlu untuk membuat grafik kumpulan nilai yang ditentukan oleh sistem sekatan yang ditentukan dalam masalah:

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

Kawasan yang diberikan oleh ketaksamaan 1 dan 2 sesuai dengan kuadran pertama pesawat Cartesian. Mengenai ketaksamaan 3 dan 4, kita mulakan dengan mencari garis larangan:

9x + 8y = 144

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

Kawasan yang layak adalah segiempat sama yang bucunya adalah titik A, B, C, dan D.

Keuntungan minimum adalah 0, oleh itu garis 8x + 10y = 0 adalah had yang lebih rendah dan garis keuntungan-iso mempunyai kemiringan -8/10 = - 0,8.

Nilai ini berbeza dengan lereng dari garis sekatan yang lain dan kerana wilayah yang layak dibatasi, penyelesaian unik ada.

Rajah 5. Penyelesaian grafik latihan 1, menunjukkan kawasan yang dapat dilaksanakan dan titik penyelesaian C di salah satu bucu wilayah tersebut. Sumber: F. Zapata.

Penyelesaian ini sesuai dengan garis lereng -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)

Penyelesaian optimum

Kami mengira nilai G untuk setiap titik 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 didapati pembuatan 11 kek hutan hitam dan 5,625 kek sacripantine. Penyelesaian ini sesuai dengan penyelesaian yang dijumpai melalui perisian.

- Latihan 2

Sahkan hasil latihan sebelumnya dengan menggunakan fungsi Solver yang terdapat di kebanyakan spreadsheet seperti Excel atau LibreOffice Calc, yang menggabungkan algoritma Simplex untuk pengoptimuman dalam pengaturcaraan linear.

Penyelesaian

Gambar 6. Perincian penyelesaian dari latihan 1 melalui hamparan Libre Office Calc. Sumber: F. Zapata.

Gambar 7. Perincian penyelesaian dari latihan 1 melalui hamparan Libre Office Calc. Sumber: F. Zapata.

Rujukan

1. Cemerlang. Pengaturcaraan Linear. Dipulihkan dari: brilliant.org.
2. Eppen, G. 2000. Penyelidikan Operasi dalam Sains Pentadbiran. 5hb. Edisi. Dewan Prentice.
3. Haeussler, E. 1992. Matematik untuk Pengurusan dan Ekonomi. Ke-2. Edisi. Pengarang Grupo Iberoamericana.
4. Hiru.eus. Pengaturcaraan linear. Dipulihkan dari: hiru.eus.
5. Wikipedia. Pengaturcaraan linear. Dipulihkan dari: es. wikipedia.org.