PENGATURCARAAN TIDAK LINEAR: KAEDAH DAN LATIHAN - MATEMATIK - 2026

The pengaturcaraan linear adalah proses mengoptimumkan fungsi yang bergantung kepada beberapa pembolehubah bebas, yang seterusnya adalah tertakluk kepada sekatan.

Sekiranya satu atau lebih kekangan, atau jika fungsi yang akan dimaksimumkan atau diminimalkan (disebut fungsi objektif), tidak dinyatakan sebagai kombinasi linear dari pemboleh ubah, maka Anda menghadapi masalah pengaturcaraan nonlinier.

Gambar 1. Masalah pengaturcaraan tidak linear (NLP). di mana G adalah fungsi (tidak linier) untuk mengoptimumkan di kawasan hijau, ditentukan oleh kekangan. Sumber: F. Zapata.

Oleh itu, prosedur dan kaedah pengaturcaraan linear tidak dapat digunakan.

Sebagai contoh, kaedah Simplex yang terkenal tidak dapat digunakan, yang hanya berlaku apabila fungsi objektif dan kekangannya adalah semua kombinasi linear dari pemboleh ubah masalah.

Kaedah pengaturcaraan linear

Untuk masalah pengaturcaraan bukan linear kaedah utama yang akan digunakan adalah:

1.- Kaedah grafik.

2.- Pengganda Lagrange untuk meneroka batas wilayah penyelesaian.

3.- Pengiraan kecerunan untuk menerokai fungsi objektif yang keterlaluan.

4.- Kaedah langkah menurun, untuk mencari titik kecerunan nol.

5.- Kaedah modifikasi pengganda Lagrange (dengan keadaan Karush-Kuhn-Tucker).

Contoh penyelesaian dengan kaedah grafik

Contoh penyelesaian dengan kaedah grafik adalah yang dapat dilihat pada gambar 2:

Rajah 2. Contoh masalah bukan linier dengan sekatan bukan linier dan penyelesaian grafiknya. Sumber: F. Zapata.

Latihan

- Latihan 1 (Kaedah grafik)

Keuntungan G syarikat tertentu bergantung pada jumlah penjualan produk X dan jumlah penjualan produk Y, di samping itu, keuntungan ditentukan oleh formula berikut:

G = 2 (X - 2) ² + 3 (Y - 3) ²

Jumlah X dan Y diketahui mempunyai sekatan berikut:

X≥0; Y≥0 dan X + Y ≤ 7

Tentukan nilai X dan Y yang menghasilkan keuntungan maksimum.

Gambar 3. Keuntungan syarikat dapat dimodelkan secara matematik untuk mencari keuntungan maksimum menggunakan pengaturcaraan bukan linier. Sumber: Pixabay.

Penyelesaian

Dalam masalah ini fungsi objektif tidak linear, sementara ketaksamaan yang menentukan kekangannya. Ini adalah masalah pengaturcaraan tidak linier.

Untuk penyelesaian masalah ini, kaedah grafik akan dipilih.

Pertama, wilayah penyelesaian akan ditentukan, yang diberikan oleh sekatan.

Sebagai X≥0; Y≥0, penyelesaiannya mesti dijumpai di kuadran pertama bidang XY, tetapi kerana ia juga mesti benar bahawa X + Y ≤ 7, penyelesaiannya berada di satah separuh bawah garis X + Y = 7.

Kawasan penyelesaian adalah persimpangan kuadran pertama dengan bidang separuh garis bawah, yang menghasilkan kawasan segitiga di mana larutan dijumpai. Sama seperti yang ditunjukkan pada gambar 1.

Sebaliknya, keuntungan G juga dapat ditunjukkan dalam satah Cartesian, kerana persamaannya adalah elips dengan pusat (2,3).

Elips ditunjukkan dalam Rajah 1 untuk pelbagai nilai G. Semakin tinggi nilai G, semakin besar keuntungannya.

Terdapat penyelesaian yang dimiliki wilayah ini, tetapi tidak memberikan nilai G maksimum, sementara yang lain, seperti G = 92.4, berada di luar zon hijau, iaitu zon penyelesaian.

Kemudian, nilai maksimum G, sehingga X dan Y tergolong dalam wilayah penyelesaian sepadan dengan:

G = 77 (keuntungan maksimum), yang diberikan untuk X = 7 dan Y = 0.

Menariknya, keuntungan maksimum berlaku apabila jumlah penjualan produk Y adalah sifar, sementara jumlah produk X mencapai nilai setinggi mungkin.

- Latihan 2 (Kaedah analisis: Pengganda Lagrange)

Cari penyelesaian (x, y) yang menjadikan fungsi f (x, y) = x ² + 2y ² maksimum di rantau g (x, y) = x ² + y ² - 1 = 0.

Penyelesaian

Ini jelas merupakan masalah pengaturcaraan tidak linear, kerana kedua-dua fungsi objektif f (x, y) dan sekatan g (x, y) = 0, bukanlah gabungan linear pemboleh ubah x dan y.

Kaedah pengganda Lagrange akan digunakan, yang pertama memerlukan menentukan fungsi Lagrange L (x, y, λ):

L (x, y, λ) = f (x, y) - λ g (x, y) = x ² + 2y ² - λ (x ² + y ² - 1)

Di mana λ adalah parameter yang disebut pengganda Lagrange.

Untuk menentukan nilai ekstrem fungsi objektif f, di kawasan penyelesaian yang diberikan oleh sekatan g (x, y) = 0, ikuti langkah berikut:

-Cari turunan separa fungsi Lagrange L, berkenaan dengan x, y, λ.

-Kira setiap turunan menjadi sifar.

Berikut urutan operasi ini:

1. ∂L / ∂x = 2x - 2λx = 0
2. ∂L / ∂y = 4y - 2λy = 0
3. ∂L / ∂λ = - (x ² + y ² - 1) = 0

Penyelesaian sistem yang mungkin

Penyelesaian yang mungkin bagi sistem ini adalah λ = 1 supaya persamaan pertama berpuas hati, dalam hal ini y = 0 sehingga kedua puas.

Penyelesaian ini menunjukkan bahawa x = 1 atau x = -1 agar persamaan ketiga berpuas hati. Dengan cara ini, dua penyelesaian S1 dan S2 telah diperoleh:

S1: (x = 1, y = 0)

S2: (x = -1, y = 0).

Alternatif lain ialah λ = 2 supaya persamaan kedua berpuas hati, tanpa mengira nilai y.

Dalam kes ini, satu-satunya cara untuk persamaan pertama dapat memuaskan adalah dengan x = 0. Mengingat persamaan ketiga, hanya ada dua kemungkinan penyelesaian, yang akan kita panggil S3 dan S4:

S3: (x = 0, y = 1)

S4: (x = 0, y = -1)

Untuk mengetahui mana atau penyelesaian mana yang memaksimumkan fungsi objektif, kami meneruskan penggantian dalam f (x, y):

S1: f (1, 0) = 1 ² + 2.0 ² = 1

S2: f (-1, 0) = (-1) ² + 2.0 ² = 1

S3: f (0, 1) = 0 ² + 2.1 ² = 2

S4: f (0, -1) = 0 ² + 2 (-1) ² = 2

Kami menyimpulkan bahawa penyelesaian yang memaksimumkan f, apabila x dan y tergolong dalam lilitan g (x, y) = 0 adalah S3 dan S4.

Pasangan nilai (x = 0, y = 1) dan (x = 0, y = -1) memaksimumkan f (x, y) di kawasan penyelesaian g (x, y) = 0.

- Latihan 3 (Kecerunan Null)

Cari penyelesaian (x, y) untuk fungsi objektif:

f (x, y) = x ² + 2 y ²

Biarkan maksimum di rantau g (x, y) = x ² + y ² - 1 ≤ 0.

Penyelesaian

Latihan ini serupa dengan latihan 2, tetapi kawasan penyelesaian (atau sekatan) meluas ke kawasan pedalaman lilitan g (x, y) = 0, iaitu dengan lingkaran g (x, y) ≤ 0. Ini termasuk ke lilitan dan kawasan dalamnya.

Penyelesaian di perbatasan telah ditentukan dalam latihan 2, tetapi kawasan pedalaman masih perlu dijelajahi.

Untuk melakukan ini, kecerunan fungsi f (x, y) mesti dikira dan ditetapkan sama dengan sifar, untuk mencari nilai ekstrem di kawasan penyelesaian. Ini sama dengan mengira terbitan separa f masing-masing untuk x dan y dan menetapkannya sama dengan sifar:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Sistem persamaan ini mempunyai satu-satunya penyelesaian (x = 0, y = 0) yang termasuk dalam bulatan g (x, y) ≤ 0.

Menggantikan nilai ini dalam fungsi f menghasilkan:

f (0, 0) = 0

Sebagai kesimpulan, nilai maksimum yang diambil oleh fungsi di kawasan penyelesaian adalah 2 dan berlaku pada batas wilayah penyelesaian, untuk nilai (x = 0, y = 1) dan (x = 0, y = -1) .

Rujukan

1. Avriel, M. 2003. Pengaturcaraan Tidak Linier. Penerbitan Dover.
2. Bazaraa. 1979. Pengaturcaraan Nonlinear. John Wiley & Anak.
3. Bertsekas, D. 1999. Pengaturcaraan Nonlinear: edisi ke-2. Athena Saintifik.
4. Nocedal, J. 1999. Pengoptimuman Numerik. Springer-Verlag.
5. Wikipedia. Pengaturcaraan tidak linear. Dipulihkan dari: es.wikipedia.com