Pengoptimuman membantu anda mencari hasil terbaik yang mendatangkan keuntungan, mengurangkan kos atau menetapkan parameter yang menyebabkan kegagalan proses perniagaan.
Proses ini juga dipanggil pengaturcaraan matematik. Ia menyelesaikan masalah menentukan pengagihan sumber terhad yang diperlukan untuk mencapai matlamat yang ditetapkan oleh ketua masalah pengoptimuman. Daripada semua pilihan yang mungkin, adalah wajar untuk mencari satu yang memaksimumkan (atau mengurangkan) parameter kawalan, contohnya, keuntungan atau kos. Model pengoptimuman juga dipanggil preskriptif atau normatif kerana mereka berusaha untuk mencari strategi yang boleh dilaksanakan untuk perniagaan.
Sejarah pembangunan
Pengaturcaraan linear (LP) berfungsi dengan kelas masalah pengoptimuman di mana semua kekangan adalah linear.
Membentangkan sejarah ringkas perkembangan LP:
- Pada tahun 1762, Lagrange menyelesaikan masalah pengoptimuman mudah dengan kekangan kesaksamaan.
- Pada tahun 1820, Gauss memutuskansistem persamaan linear menggunakan penyingkiran.
- Pada tahun 1866, Wilhelm Jordan menyempurnakan kaedah mencari ralat kuasa dua terkecil sebagai kriteria kesesuaian. Ini kini dipanggil kaedah Gauss-Jordan.
- Komputer digital muncul pada tahun 1945.
- Danzig mencipta kaedah simpleks pada tahun 1947.
- Pada tahun 1968, Fiacco dan McCormick memperkenalkan kaedah Inside Point.
- Pada tahun 1984, Karmarkar menggunakan kaedah dalaman untuk menyelesaikan program linear, sambil menambah analisis inovatifnya.
LP telah terbukti sebagai alat yang sangat berkuasa untuk memodelkan masalah dunia sebenar dan sebagai teori matematik yang digunakan secara meluas. Walau bagaimanapun, banyak masalah pengoptimuman yang menarik adalah bukan linear.
Apa yang perlu dilakukan dalam kes ini? Kajian masalah tersebut melibatkan campuran pelbagai algebra linear, kalkulus multivariat, analisis berangka, dan kaedah pengiraan. Para saintis sedang membangunkan algoritma pengiraan, termasuk kaedah titik dalaman untuk pengaturcaraan linear, geometri, analisis set dan fungsi cembung, dan kajian masalah berstruktur khas seperti pengaturcaraan kuadratik.
Pengoptimuman bukan linear memberikan pemahaman asas tentang analisis matematik dan digunakan secara meluas dalam pelbagai bidang seperti kejuruteraan, analisis regresi, pengurusan sumber, penerokaan geofizik dan ekonomi.
Klasifikasi masalah pengoptimuman
Langkah pentingProses pengoptimuman ialah klasifikasi model, kerana algoritma penyelesaiannya disesuaikan dengan jenis tertentu.
1. Masalah dengan pengoptimuman diskret dan berterusan. Sesetengah model hanya masuk akal jika pembolehubah mengambil nilai daripada subset diskret integer. Lain-lain mengandungi data yang boleh mengambil sebarang nilai sebenar. Mereka biasanya lebih mudah untuk diselesaikan. Penambahbaikan dalam algoritma, digabungkan dengan kemajuan dalam teknologi komputer, telah meningkatkan saiz dan kerumitan masalah pengoptimuman pengaturcaraan linear secara mendadak.
2. Pengoptimuman tanpa had dan terhad. Satu lagi perbezaan penting ialah tugas di mana tiada kekangan pada pembolehubah. Ia boleh berkisar secara meluas daripada penganggar mudah kepada sistem kesamaan dan ketaksamaan yang memodelkan hubungan kompleks antara data. Masalah pengoptimuman sedemikian boleh diklasifikasikan lagi mengikut sifat fungsi (linear dan bukan linear, cembung dan licin, boleh dibezakan dan tidak boleh dibezakan).
3. Tugas kebolehlaksanaan. Matlamat mereka adalah untuk mencari nilai pembolehubah yang memenuhi kekangan model tanpa sebarang matlamat pengoptimuman khusus.
4. Tugasan saling melengkapi. Mereka digunakan secara meluas dalam teknologi dan ekonomi. Matlamatnya adalah untuk mencari penyelesaian yang memenuhi syarat saling melengkapi. Dalam amalan, tugasan dengan beberapa matlamat sering dirumus semula menjadi satu objektif.
5. Pengoptimuman deterministik berbanding stokastik. Pengoptimuman deterministik menganggap bahawa data untuktugasan adalah tepat sepenuhnya. Walau bagaimanapun, dalam banyak isu topikal, ia tidak dapat diketahui atas beberapa sebab.
Yang pertama berkaitan dengan ralat pengukuran yang mudah. Sebab kedua adalah lebih asas. Ia terletak pada fakta bahawa sesetengah data mewakili maklumat tentang masa depan, contohnya, permintaan untuk produk atau harga untuk tempoh masa hadapan. Apabila mengoptimumkan di bawah keadaan pengoptimuman stokastik, ketidakpastian disertakan dalam model.
Komponen Utama
Fungsi objektif ialah fungsi yang perlu diminimumkan atau dimaksimumkan. Kebanyakan jenis masalah pengoptimuman mempunyai satu fungsi objektif. Jika tidak, ia selalunya boleh dirumus semula untuk berfungsi.
Dua pengecualian kepada peraturan ini:
1. Tugas carian sasaran. Dalam kebanyakan aplikasi perniagaan, pengurus ingin mencapai matlamat tertentu sambil memenuhi kekangan model. Pengguna tidak mahu mengoptimumkan sesuatu, jadi tidak masuk akal untuk menentukan fungsi objektif. Jenis ini biasanya dirujuk sebagai masalah kepuasan.
2. Banyak ciri objektif. Selalunya, pengguna ingin mengoptimumkan beberapa matlamat yang berbeza sekaligus. Mereka biasanya tidak serasi. Pembolehubah yang mengoptimumkan untuk satu matlamat mungkin bukan yang terbaik untuk yang lain.
Jenis komponen:
- Input terkawal ialah satu set pembolehubah keputusan yang mempengaruhi nilai fungsi objektif. Dalam tugas pengeluaran, pembolehubah mungkin termasuk pengagihan pelbagai sumber yang ada atau tenaga kerja yang diperlukan untuksetiap tindakan.
- Kekangan ialah hubungan antara pembolehubah keputusan dan parameter. Untuk masalah pengeluaran, adalah tidak masuk akal untuk menghabiskan banyak masa pada sebarang aktiviti, jadi hadkan semua pembolehubah "sementara".
- Penyelesaian yang mungkin dan optimum. Nilai keputusan untuk pembolehubah, di mana semua kekangan dipenuhi, dipanggil memuaskan. Kebanyakan algoritma mula-mula mencarinya, kemudian cuba memperbaikinya. Akhirnya, mereka menukar pembolehubah untuk berpindah dari satu penyelesaian yang boleh dilaksanakan kepada penyelesaian yang lain. Proses ini diulang sehingga fungsi objektif mencapai maksimum atau minimum. Keputusan ini dipanggil penyelesaian optimum.
Algoritma masalah pengoptimuman yang dibangunkan untuk program matematik berikut digunakan secara meluas:
- Convex.
- Boleh dipisahkan.
- Kuadratik.
- Geometrik.
Google Linear Solvers
Pengoptimuman atau pengaturcaraan linear ialah nama yang diberikan kepada proses pengiraan untuk menyelesaikan masalah secara optimum. Ia dimodelkan sebagai satu set perhubungan linear yang timbul dalam banyak disiplin saintifik dan kejuruteraan.
Google menawarkan tiga cara untuk menyelesaikan masalah pengoptimuman linear:
- Pustaka sumber terbuka Glop.
- tambahan Pengoptimuman Linear untuk Helaian Google.
- Perkhidmatan Pengoptimuman Linear dalam Skrip Google Apps.
Glop terbina dalam Googlepenyelesai linear. Ia boleh didapati dalam sumber terbuka. Anda boleh mengakses Glop melalui pembungkus penyelesai linear OR-Tools, yang merupakan pembungkus untuk Glop.
Modul pengoptimuman linear untuk Helaian Google membolehkan anda melakukan pernyataan linear masalah pengoptimuman dengan memasukkan data ke dalam hamparan.
Pengaturcaraan kuadratik
Platform Penyelesai Premium menggunakan versi LP/Kuadratik lanjutan bagi kaedah Simplex dengan had pemprosesan masalah LP dan QP sehingga 2000 pembolehubah keputusan.
SQP Solver untuk masalah berskala besar menggunakan pelaksanaan moden kaedah set aktif dengan jarang untuk menyelesaikan masalah pengaturcaraan kuadratik (QP). Enjin XPRESS Solver menggunakan sambungan semula jadi kaedah "Titik Dalaman" atau Newton Barrier untuk menyelesaikan masalah QP.
MOSEK Solver menggunakan kaedah "Titik Dalam" dan auto dwi tertanam. Ini amat berkesan untuk masalah QP yang berganding longgar. Ia juga boleh menyelesaikan masalah Scale Quadratic Constraint (QCP) dan Second Order Cone Programming (SOCP).
Pengiraan berbilang operasi
Ia agak berjaya digunakan dengan penggunaan ciri Microsoft Office, contohnya, menyelesaikan masalah pengoptimuman dalam Excel.
Dalam jadual di atas, simbolnya ialah:
- K1 - K6 - pelanggan yang perlu menyediakan barangan.
- S1 - S6 ialah tapak pengeluaran berpotensi yang boleh dibina untuk ini. Boleh dibuat1, 2, 3, 4, 5 atau kesemua 6 lokasi.
Terdapat kos tetap untuk setiap kemudahan yang disenaraikan dalam lajur I (Betulkan).
Jika lokasi tidak mengubah apa-apa, ia tidak akan dikira. Kemudian tiada kos tetap.
Kenal pasti lokasi berpotensi untuk mendapatkan kos terendah.
Dalam keadaan ini, lokasi sama ada ditetapkan atau tidak. Kedua-dua keadaan ini ialah: "BENAR - SALAH" atau "1 - 0". Terdapat enam negeri untuk enam lokasi, contohnya, 000001 ditetapkan kepada yang keenam sahaja, 111111 ditetapkan kepada semua.
Dalam sistem nombor binari, terdapat tepat 63 pilihan berbeza daripada 000001 (1) hingga 111111 (63).
L2-L64 kini sepatutnya membaca {=PELBAGAI OPERASI (K1)}, ini adalah hasil semua penyelesaian alternatif. Kemudian nilai minimum ialah=Min (L) dan alternatif yang sepadan ialah INDEX (K).
Pengaturcaraan Integer CPLEX
Kadangkala perhubungan linear tidak mencukupi untuk menyelesaikan masalah perniagaan. Ini benar terutamanya apabila keputusan melibatkan pilihan diskret, seperti sama ada untuk membuka gudang di lokasi tertentu atau tidak. Dalam situasi ini, pengaturcaraan integer mesti digunakan.
Jika masalah melibatkan pilihan diskret dan berterusan, ia adalah program integer bercampur. Ia boleh mempunyai masalah kuadratik linear, cembung dan kekangan tertib kedua yang sama.
Atur cara integer jauh lebih kompleks daripada program linear, tetapi ia mempunyai aplikasi perniagaan yang penting. PerisianPerisian CPLEX menggunakan kaedah matematik yang kompleks untuk menyelesaikan masalah integer. Kaedah beliau melibatkan pencarian secara sistematik untuk kemungkinan gabungan pembolehubah diskret menggunakan kelonggaran perisian linear atau kuadratik untuk mengira had nilai penyelesaian optimum.
Mereka juga menggunakan LP dan kaedah penyelesaian masalah pengoptimuman lain untuk mengira kekangan.
Penyelesai Microsoft Excel Standard
Teknologi ini menggunakan pelaksanaan asas kaedah Simplex utama untuk menyelesaikan masalah LP. Ia terhad kepada 200 pembolehubah. "Premium Solver" menggunakan kaedah simpleks primer yang dipertingkatkan dengan sempadan dua muka untuk pembolehubah. Platform Premium Solver menggunakan versi lanjutan LP/Quadratic Simplex Solver untuk menyelesaikan masalah pengoptimuman dengan sehingga 2000 pembolehubah keputusan.
LP berskala besar untuk platform Penyelesai Premium menggunakan pelaksanaan terkini kaedah ringkas dan berganda, yang menggunakan sparsity dalam model LP untuk menjimatkan masa dan ingatan, strategi lanjutan untuk mengemas kini dan matriks pemfaktoran semula, harga berbilang dan separa dan putaran, dan untuk mengatasi degenerasi. Enjin ini tersedia dalam tiga versi (mampu mengendalikan sehingga 8,000, 32,000 atau pembolehubah dan had tanpa had).
MOSEK Solver termasuk primer dan dwi simpleks, satu kaedah yang juga mengeksploitasi sparsity dan menggunakan strategi lanjutan untuk pengemaskinian matriks dan "pemfaktoran semula". Ia menyelesaikan masalah saiz yang tidak terhad, adalahdiuji pada masalah pengaturcaraan linear dengan berjuta-juta pembolehubah keputusan.
Contoh langkah demi langkah dalam EXCEL
Untuk menentukan model masalah pengoptimuman dalam Excel, lakukan langkah berikut:
- Susun data untuk masalah dalam hamparan dalam bentuk logik.
- Pilih sel untuk menyimpan setiap pembolehubah.
- Buat dalam sel formula untuk mengira model matematik sasaran masalah pengoptimuman.
- Buat formula untuk mengira bahagian kiri setiap kekangan.
- Gunakan dialog dalam Excel untuk memberitahu Solver tentang pembolehubah keputusan, sasaran, kekangan dan had yang dikehendaki pada parameter tersebut.
- Jalankan "Solver" untuk mencari penyelesaian yang optimum.
- Buat helaian Excel.
- Susun data untuk masalah dalam Excel di mana formula untuk fungsi objektif dan kekangan dikira.
Dalam jadual di atas, sel B4, C4, D4 dan E4 telah dikhaskan untuk mewakili pembolehubah keputusan X 1, X 2, X 3 dan X 4. Contoh keputusan:
- Model campuran produk ($450, $1150, $800 dan $400 keuntungan setiap produk) telah dimasukkan dalam sel B5, C5, D5 dan E5, masing-masing. Ini membolehkan sasaran dikira dalam F5=B5B4 + C5C4 + D5D4 + E5E4 atau F5:=SUMPRODUCT (B5: E5, B4: E4).
- Dalam B8 masukkan jumlah sumber yang diperlukan untuk mengeluarkan setiap jenis produk.
- Formula untuk F8:=SUMPRODUCT(B8:E8, $B$4:$E$4).
- Salin iniformula dalam F9. Tanda dolar dalam $B$4:$E$4 menunjukkan bahawa julat sel ini kekal malar.
- Dalam G8 masukkan jumlah sumber yang tersedia bagi setiap jenis, sepadan dengan nilai sekatan di sebelah kanan. Ini membolehkan anda menyatakannya seperti ini: F11<=G8: G11.
- Ini bersamaan dengan empat had F8<=G8, F9 <=G9, F10 <=G10 dan F11=0
Bidang aplikasi praktikal kaedah
Pengoptimuman linear mempunyai banyak aplikasi praktikal sebagai contoh masalah pengoptimuman:
Syarikat boleh membuat beberapa produk dengan margin sumbangan yang diketahui. Pengeluaran unit setiap item memerlukan jumlah sumber terhad yang diketahui. Tugasnya adalah untuk mencipta program pengeluaran untuk menentukan jumlah setiap produk yang perlu dikeluarkan supaya keuntungan syarikat dimaksimumkan tanpa melanggar kekangan sumber.
Masalah pencampuran ialah penyelesaian kepada masalah pengoptimuman yang berkaitan dengan menggabungkan bahan-bahan ke dalam produk akhir. Contohnya adalah masalah diet yang dikaji oleh George Danzig pada tahun 1947. Beberapa bahan mentah diberikan, seperti oat, daging babi dan minyak bunga matahari, bersama dengan kandungan nutrisinya, seperti protein, lemak, vitamin A, dan harganya sekilogram. Cabarannya ialah untuk mengadun satu atau lebih produk akhir daripada bahan mentah pada kos serendah mungkin sambil menghormati had minimum dan maksimum untuk nilai pemakanannya.
Aplikasi klasik masalah pengoptimuman linear adalah untuk menentukan penghalaan untuk keperluantrafik dalam telekomunikasi atau rangkaian pengangkutan. Pada masa yang sama, aliran mesti dihalakan melalui rangkaian sedemikian rupa sehingga semua keperluan trafik dipenuhi tanpa melanggar syarat lebar jalur.
Dalam teori matematik, pengoptimuman linear boleh digunakan untuk mengira strategi optimum dalam permainan jumlah sifar untuk dua orang. Dalam kes ini, taburan kebarangkalian bagi setiap peserta dikira, iaitu pekali percampuran rawak strateginya.
Tiada proses perniagaan yang berjaya di dunia adalah mungkin tanpa pengoptimuman. Terdapat banyak algoritma pengoptimuman yang tersedia. Sesetengah kaedah hanya sesuai untuk jenis masalah tertentu. Adalah penting untuk dapat mengenali ciri-ciri mereka dan memilih kaedah penyelesaian yang sesuai.
