Teori
Permasalahan sederhana dalam program linier adalah permasalahan yang memerlukan pencarian nilai maksimum (atau minimum) suatu fungsi sederhana dengan batasan tertentu. Contohnya adalah sebuah pabrik yang memproduksi dua komoditas. Dalam setiap proses produksi, pabrik memproduksi x 1 untuk tipe pertama dan x 2 untuk tipe kedua. Jika keuntungan pada tipe kedua adalah dua kali lipat keuntungan pada tipe pertama, maka x 1 + 2 x 2 mewakili total keuntungan. Fungsi x 1 + 2 x 2 disebut fungsi tujuan.
Tentu saja keuntungannya akan paling besar jika pabrik mencurahkan seluruh kapasitas produksinya untuk memproduksi komoditas jenis kedua tersebut. Namun dalam situasi praktis, hal ini mungkin tidak dapat dilakukan; serangkaian kendala disebabkan oleh faktor-faktor seperti ketersediaan waktu mesin, tenaga kerja, dan bahan mentah. Misalnya, jika jenis barang dagangan yang kedua memerlukan bahan baku yang terbatas sehingga tidak lebih dari lima yang dapat dibuat dalam satu batch, maka x 2 harus kurang dari atau sama dengan lima; yaitu, x 2 ≤ 5. Jika komoditas pertama memerlukan jenis bahan lain yang membatasinya menjadi delapan per batch, maka x 1 ≤ 8. Jika x 1 dan x 2 memerlukan waktu pembuatan yang sama dan waktu mesin yang tersedia memungkinkan maksimal 10 untuk dibuat secara batch, maka x 1 + x 2 harus lebih kecil atau sama dengan 10; yaitu x 1 + x 2 ≤ 10.
Sumber: Britannica, Inc
Masalah pengoptimalan
Himpunan batasan dibatasi oleh lima garis x 1 = 0, x 2 = 0, x 1 = 8, x 2 = 5, dan x 1 + x 2 = 10. Garis-garis ini melingkupi titik-titik yang jumlahnya tak terhingga yang mewakili solusi layak.(lagi)
Dua batasan lainnya adalah x 1 dan x 2 masing-masing harus lebih besar atau sama dengan nol, karena tidak mungkin membuat bilangan negatif dari keduanya; yaitu x 1 ≥ 0 dan x 2 ≥ 0. Soalnya adalah mencari nilai x 1 dan x 2 yang menghasilkan keuntungan maksimum. Solusi apa pun dapat dilambangkan dengan sepasang angka ( x 1 , x 2 ); misalnya x 1 = 3 dan x 2 = 6 maka penyelesaiannya adalah (3, 6). Angka-angka ini dapat direpresentasikan dengan titik-titik yang diplot pada dua sumbu, seperti terlihat pada gambar . Pada grafik ini jarak sepanjang sumbu horizontal melambangkan x 1 dan jarak sepanjang sumbu vertikal melambangkan x 2 . Karena kendala yang diberikan di atas, makasolusi yang layak harus berada dalam wilayah grafik tertentu yang terdefinisi dengan baik. Misalnya, batasan x 1 ≥ 0 berarti titik-titik yang mewakili solusi layak terletak pada atau di sebelah kanan sumbu x 2 . Demikian pula, batasan x 2 ≥ 0 berarti bahwa batasan tersebut juga terletak pada atau di atas sumbu x 1 . Penerapan seluruh himpunan kendala menghasilkan himpunan solusi layak, yang dibatasi oleh poligon yang dibentuk oleh perpotongan garis x 1 = 0, x 2 = 0, x 1 = 8, x 2 = 5, dan x 1 + x 2 = 10. Misalnya, produksi tiga jenis barang dagangan x 1 dan empat jenis barang x 2 merupakan penyelesaian yang layak karena titik (3, 4) terletak di daerah ini. Namun, untuk mencari solusi terbaik, fungsi tujuan x 1 + 2 x 2 = k diplot pada grafik untuk beberapa nilai k , katakanlah k = 4. Nilai ini ditunjukkan dengan garis putus-putus pada gambar. Ketika k diperbesar, dihasilkan sekumpulan garis sejajar dan garis untuk k = 15 hanya menyentuhbatasan yang ditetapkan pada titik (5, 5). Jika k dinaikkan lagi, nilai x 1 dan x 2 akan berada di luar himpunan solusi layak. Oleh karena itu, solusi terbaik adalah dengan memproduksi setiap komoditas dalam jumlah yang sama. Bukan suatu kebetulan bahwa solusi optimal terjadi pada suatu titik, atau “titik ekstrim,” di wilayah tersebut. Hal ini selalu berlaku untuk permasalahan linier, meskipun solusi optimal mungkin tidak unik . Oleh karena itu, penyelesaian permasalahan tersebut direduksi menjadi pencarian titik (atau titik-titik) ekstrem mana yang menghasilkan nilai terbesar untuk fungsi tujuan.
Itu metode simpleks
Metode penyelesaian grafis yang diilustrasikan oleh contoh di bagian sebelumnya hanya berguna untuk sistem pertidaksamaan yang melibatkan dua variabel. Dalam praktiknya, soal sering kali melibatkan ratusan persamaan dengan ribuan variabel, yang dapat menghasilkan titik ekstrem yang jumlahnya sangat banyak. Pada tahun 1947 George Dantzig , penasihat matematika Angkatan Udara AS, merancang metode simpleks untuk membatasi jumlah titik ekstrem yang harus diperiksa. Metode simpleks adalah salah satu metode yang paling berguna dan efisienalgoritma yang pernah ditemukan, dan ini masih menjadi metode standar yang digunakan pada komputer untuk memecahkan masalah optimasi. Pertama, metode ini mengasumsikan bahwa titik ekstrim telah diketahui. (Jika tidak ada titik ekstrem yang diberikan, varian dari metode simpleks, yang disebut Tahap I, digunakan untuk menemukan solusi yang layak atau untuk menentukan bahwa tidak ada solusi yang layak .) Selanjutnya, dengan menggunakan spesifikasi aljabar dari masalah tersebut, pengujian menentukan apakah titik tersebut titik ekstrim adalah optimal. Jika uji optimalitas tidak lulus, titik ekstrim yang berdekatan dicari sepanjang tepi ke arah dimana nilai fungsi tujuan meningkat pada tingkat tercepat. Kadang-kadang seseorang dapat bergerak sepanjang suatu tepi dan membuat nilai fungsi tujuan meningkat tanpa batas. Jika hal ini terjadi, prosedur diakhiri dengan menentukan tepi sepanjang tujuan menuju ke tak terhingga positif . Jika tidak, titik ekstrem baru akan dicapai dengan nilai fungsi objektif yang setidaknya sama tinggi dengan pendahulunya. Urutan yang dijelaskan kemudian diulangi. Penghentian terjadi ketika titik ekstrim optimal ditemukan atau terjadi kasus yang tidak terbatas. Meskipun pada prinsipnya langkah-langkah yang diperlukan dapat bertambah secara eksponensial dengan jumlah titik ekstrem, dalam praktiknya metode ini biasanya menyatu pada solusi optimal dalam sejumlah langkah yang hanya merupakan kelipatan kecil dari jumlah titik ekstrem.
Untuk mengilustrasikan metode simpleks, contoh dari bagian sebelumnya akan diselesaikan lagi. Permasalahan pertama-tama dimasukkan ke dalam bentuk kanonik dengan mengubah pertidaksamaan linier menjadi persamaan dengan memperkenalkan “variabel slack” x 3 ≥ 0 (sehingga x 1 + x 3 = 8), x 4 ≥ 0 (sehingga x 2 + x 4 = 5), x 5 ≥ 0 (sehingga x 1 + x 2 + x 5 = 10), dan variabel x 0 untuk nilai fungsi tujuan (sehingga x 1 + 2 x 2 − x 0 = 0). Permasalahan tersebut kemudian dapat dinyatakan kembali sebagai masalah menemukan besaran non-negatif x 1 , …, x 5 dan kemungkinan terbesar x 0 yang memenuhi persamaan yang dihasilkan. Salah satu solusi yang jelas adalah dengan menetapkan variabel tujuan x 1 = x 2 = 0, yang sesuai dengan titik ekstrim di titik asal. Jika salah satu variabel objektif dinaikkan dari nol sementara variabel lainnya ditetapkan nol, nilai objektif x 0 akan meningkat sesuai keinginan (tergantung pada variabel slack yang memenuhi batasan kesetaraan). Variabel x 2 menghasilkan kenaikan x 0 terbesar per satuan perubahan; jadi dipakai dulu. Peningkatannya dibatasi oleh persyaratan non-negatif pada variabel. Khususnya, jika x 2 dinaikkan melebihi 5, x 4 menjadi negatif.
Pada x 2 = 5, situasi ini menghasilkan solusi baru—( x 0 , x 1 , x 2 , x 3 , x 4 , x 5 ) = (10, 0, 5, 8, 0, 5)—yang sesuai dengan titik ekstrim (0, 5) pada gambar. Sistem persamaan tersebut dimasukkan ke dalam bentuk ekuivalen dengan menyelesaikan variabel bukan nol x 0 , x 2 , x 3 , x 5 dengan variabel-variabel tersebut sekarang bernilai nol; yaitu, x 1 dan x 4 . Jadi, fungsi tujuan yang baru adalah x 1 − 2 x 4 = −10, sedangkan kendalanya adalah x 1 + x 3 = 8, x 2 + x 4 = 5, dan x 1 − x 4 + x 5 = 5. Fungsi tersebut sekarang jelas bahwa peningkatan x 1 sambil menahan x 4 sama dengan nol akan menghasilkan peningkatan lebih lanjut pada x 0 . Pembatasan nonnegatif pada x 3 mencegah x 1 melampaui 5. Solusi baru—( x 0 , x 1 , x 2 , x 3 , x 4 , x 5 ) = (15, 5, 5, 3, 0, 0 )—sesuai dengan titik ekstrem (5, 5) pada gambar. Akhirnya, karena menyelesaikan x 0 dalam variabel x 4 dan x 5 (yang saat ini bernilai nol) menghasilkan x 0 = 15 − x 4 − x 5 , dapat dilihat bahwa setiap perubahan lebih lanjut pada variabel slack ini akan mengurangi nilai obyektif. Oleh karena itu, solusi optimal ada pada titik ekstrim (5, 5).
Formulasi standar
Dalam praktiknya, masalah optimasi dirumuskan dalam bentuk matriks —sebuah simbolisme kompak untuk memanipulasi batasan dan menguji fungsi tujuan secara aljabar. Masalah optimasi asli (atau "primal") diberikan formulasi standarnya oleh von Neumann pada tahun 1947. Dalammasalah utama tujuan digantikan oleh produk (px) dari vektor x = ( x 1 , x 2 , x 3 , …, x n ) T , yang komponennya adalah variabel tujuan dan di mana simbol “transpose” superskrip menunjukkan bahwa vektor tersebut harus ditulis secara vertikal, dan vektor lainnya p = ( p 1 , p 2 , p 3 , …, p n ), yang komponennya merupakan koefisien dari masing-masing variabel tujuan. Selain itu, sistem batasan pertidaksamaan digantikan oleh Ax ≤ b, dimana matriks A x m kali n menggantikan batasan m pada n variabel tujuan, dan b = ( b 1 , b 2 , b 3 , …, b m ) T adalah vektor yang komponen-komponennya merupakan batas pertidaksamaan.
Pemrograman nonlinier
Meskipun model pemrograman linier berfungsi dengan baik untuk banyak situasi, beberapa masalah tidak dapat dimodelkan secara akurat tanpa menyertakan komponen nonlinier. Salah satu contohnya adalah soal isoperimetri : menentukan bentuk kurva bidang tertutup yang mempunyai panjang tertentu dan mempunyai luas maksimum. Solusinya, tapi bukan bukti , diketahui olehPappus dari Aleksandria c. 340 M :
Maka, lebah mengetahui fakta yang berguna bagi mereka, bahwa segi enam lebih besar daripada persegi dan segitiga dan akan menampung lebih banyak madu dengan pengeluaran bahan yang sama untuk membangun masing-masing segi enam. Namun kami, yang mengklaim memiliki lebih banyak kebijaksanaan daripada lebah, akan menyelidiki masalah yang lebih luas, yaitu bahwa, dari semua bangun datar sama sisi dan sama sudut yang mempunyai keliling yang sama, bangun datar yang mempunyai jumlah sudut lebih banyak selalu lebih besar, dan jumlah sudutnya lebih besar. semuanya adalah lingkaran yang kelilingnya sama dengan lingkaran tersebut.
Cabang matematika yang dikenal dengan nama kalkulus variasi dimulai dengan upaya untuk membuktikan solusi ini, bersamaan dengan tantangan pada tahun 1696 oleh ahli matematika Swiss Johann Bernoulli menemukan kurva yang meminimalkan waktu yang diperlukan suatu benda untuk meluncur, hanya di bawah gaya gravitasi, antara dua titik nonvertikal. (Solusinya adalah brachistochrone). Selain Johann Bernoulli, saudaranya Jakob Bernoulli , Gottfried Wilhelm Leibniz dari Jerman , dan Isaac Newton dari Inggris semuanya memberikan solusi yang benar. Secara khusus, pendekatan Newton terhadap solusi memainkan peran mendasar dalam banyak algoritma nonlinier . Pengaruh lain pada pengembangan pemrograman nonlinier, seperti analisis cembung , teori dualitas, dan teori kontrol , sebagian besar berkembang setelah tahun 1940. Untuk permasalahan yang mencakup batasan serta fungsi tujuan , kondisi optimalitas ditemukan oleh ahli matematika Amerika William Karush dan lain-lain. pada akhir tahun 1940an menjadi alat penting untuk mengenali solusi dan mendorong perilaku algoritma.
Algoritma awal yang penting untuk menyelesaikan program nonlinier diberikan oleh ekonom Norwegia pemenang Hadiah NobelRagnar Frisch pada pertengahan tahun 1950an. Anehnya, pendekatan ini tidak lagi disukai selama beberapa dekade, dan baru muncul kembali sebagai pendekatan yang layak dan kompetitif pada tahun 1990an. Pendekatan algoritmik penting lainnya termasuk pemrograman kuadrat sekuensial, di mana masalah perkiraan dengan tujuan kuadrat dan batasan linier diselesaikan untuk mendapatkan setiap langkah pencarian; dan metode hukuman, termasuk “metode pengganda,” di mana titik-titik yang tidak memenuhi batasan akan dikenakan ketentuan penalti dengan tujuan untuk mencegah algoritme mengunjungi titik tersebut.
Ekonom Amerika pemenang Hadiah NobelHarry M. Markowitz memberikan dorongan untuk optimasi nonlinier pada tahun 1958 ketika ia merumuskan masalah pencarian portofolio investasi yang efisien sebagai masalah optimasi nonlinier dengan fungsi tujuan kuadrat. Teknik optimasi nonlinier sekarang banyak digunakan di bidang keuangan, ekonomi , manufaktur, pengendalian, pemodelan cuaca, dan semua cabang teknik.
Teori
Suatu permasalahan optimasi bersifat nonlinier jika fungsi tujuan f (x) atau salah satu batasan pertidaksamaan c i (x) ≤ 0, i = 1, 2, …, m , atau batasan persamaan d j (x) = 0, j = 1, 2, …, n , adalah fungsi nonlinier dari vektor variabel x. Misalnya, jika x memuat komponen x 1 dan x 2 , maka fungsi 3 + 2 x 1 − 7 x 2 linier, sedangkan fungsi ( x 1 ) 3 + 2 x 2 dan 3 x 1 + 2 x 1 x 2 + x 2 adalah nonlinier.
Masalah nonlinier muncul ketika tujuan atau batasan tidak dapat dinyatakan sebagai fungsi linier tanpa mengorbankan beberapa fitur nonlinier penting dari sistem dunia nyata. Misalnya, konformasi lipatan molekul protein diyakini meminimalkan fungsi nonlinier tertentu dari jarak antara inti atom komponennya—dan jarak ini sendiri merupakan fungsi nonlinier dari posisi inti. Di bidang keuangan, risiko yang terkait dengan portofolio investasi, yang diukur dengan varians pengembalian portofolio, merupakan fungsi nonlinier dari jumlah yang diinvestasikan pada setiap sekuritas dalam portofolio. Dalam kimia, konsentrasi masing-masing bahan kimia dalam suatu larutan sering kali merupakan fungsi waktu yang nonlinier, karena reaksi antar bahan kimia biasanya berlangsung menurut rumus eksponensial.
Masalah nonlinier dapat dikategorikan menurut beberapa sifat. Terdapat permasalahan yang tujuan dan batasannya merupakan fungsi mulus, dan terdapat permasalahan tidak mulus yang kemiringan atau nilai suatu fungsi dapat berubah secara tiba-tiba. Terdapat permasalahan tak terbatas yang tujuannya adalah meminimalkan (atau memaksimalkan) fungsi tujuan f (x) tanpa batasan pada nilai x, dan terdapat permasalahan terbatas yang komponen x harus memenuhi batasan tertentu atau batasan lain. hubungan timbal balik yang lebih kompleks. Di dalamsoal cembung, grafik fungsi tujuan dan himpunan layak keduanya cembung (di mana suatu himpunan dikatakan cembung jika suatu garis yang menghubungkan dua titik mana pun dalam himpunan tersebut terdapat di dalam himpunan tersebut). Kasus khusus lainnya adalahpemrograman kuadratik, yang batasannya linier tetapi fungsi tujuannya bersifat kuadrat; yaitu berisi suku-suku yang merupakan kelipatan hasil kali dua komponen x. (Misalnya, fungsi 3( x 1 ) 2 + 1,4 x 1 x 2 + 2( x 2 ) 2 adalah fungsi kuadrat dari x 1 dan x 2 .) Cara lain yang berguna untuk mengklasifikasikan soal nonlinier adalah berdasarkan banyaknya variabel (yaitu, komponen x). Secara sederhana, sebuah permasalahan dikatakan “besar” jika permasalahan tersebut mempunyai lebih dari seribu variabel atau lebih, meskipun ambang “kebesaran” terus meningkat seiring dengan semakin canggihnya kemampuan komputer. Perbedaan lain yang berguna adalah antara permasalahan yang secara komputasi “mahal” untuk dievaluasi dan permasalahan yang relatif murah, seperti halnya dalam pemrograman linier.
Algoritme pemrograman nonlinier biasanya dilanjutkan dengan membuat rangkaian tebakan vektor variabel x (dikenal sebagai iterasi dan dibedakan dengan superskrip x 1 , x 2 , x 3 , …) dengan tujuan untuk mengidentifikasi nilai x yang optimal. Seringkali tidak praktis untuk mengidentifikasi nilai x yang optimal secara global. Dalam kasus ini, kita harus memilih optimum lokal—nilai terbaik di beberapa wilayah solusi yang layak. Setiap iterasi dipilih berdasarkan pengetahuan tentang batasan dan fungsi tujuan yang dikumpulkan pada iterasi sebelumnya. Kebanyakan algoritma pemrograman nonlinier ditargetkan pada subkelas masalah tertentu. Sebagai contoh, beberapa algoritma secara khusus ditargetkan untuk masalah-masalah yang besar dan tidak dibatasi dengan halus dimana matriks turunan kedua dari f (x) mengandung sedikit entri bukan nol dan mahal untuk dievaluasi, sementara algoritma-algoritma lainnya ditujukan khusus untuk masalah-masalah pemrograman kuadrat cembung, dan sebagainya. pada.
Perangkat lunak untuk memecahkan masalah optimasi tersedia secara komersial dan dalam domain publik. Selain program optimasi komputer, sejumlah bahasa pemodelan optimasi juga tersedia yang memungkinkan pengguna untuk menggambarkan masalah dalam istilah intuitif , yang kemudian secara otomatis diterjemahkan ke dalam bentuk matematika yang diperlukan oleh perangkat lunak optimasi.
Disadur dari: britannica.com