pengantar
Tahap modern perkembangan manusia berbeda di mana abad energi digantikan oleh zaman informatika. Ada pengenalan intensif teknologi baru di semua bidang aktivitas manusia. Ada masalah nyata transisi ke masyarakat informasi, yang pembangunan pendidikan harus menjadi prioritas. Struktur pengetahuan dalam masyarakat juga berubah. Pengetahuan dasar yang berkontribusi pada pengembangan kreatif individu menjadi semakin penting untuk kehidupan praktis. Sifat konstruktif dari pengetahuan yang diperoleh, kemampuan untuk menyusunnya sesuai dengan tujuan juga penting. Atas dasar pengetahuan, sumber informasi baru masyarakat terbentuk. Pembentukan dan perolehan pengetahuan baru harus didasarkan pada metodologi yang ketat dari pendekatan sistematis, di mana tempat terpisah ditempati oleh pendekatan model. Kemungkinan pendekatan pemodelan sangat beragam baik dari segi model formal yang digunakan dan cara menerapkan metode pemodelan. Pemodelan fisik memungkinkan untuk mendapatkan hasil yang andal untuk sistem yang cukup sederhana.
Saat ini, tidak mungkin untuk menyebutkan area aktivitas manusia di mana, pada tingkat tertentu, metode pemodelan tidak akan digunakan. Hal ini terutama berlaku untuk pengelolaan berbagai sistem, di mana yang utama adalah proses pengambilan keputusan berdasarkan informasi yang diterima.
1. Pernyataan masalah
fungsi tujuan minimum
Memecahkan masalah menemukan minimum fungsi tujuan untuk sistem kendala yang ditentukan oleh poligon keputusan sesuai dengan pilihan No. 16 tugas. Poligon keputusan ditunjukkan pada Gambar 1:
Gambar 1 - Poligon solusi masalah
Sistem kendala dan fungsi tujuan dari masalah disajikan di bawah ini:
Perlu untuk memecahkan masalah menggunakan metode berikut:
Metode grafis untuk memecahkan masalah LP;
Metode aljabar untuk memecahkan masalah LP;
Metode simpleks untuk menyelesaikan masalah LP;
Metode untuk menemukan solusi yang layak untuk masalah LP;
Memecahkan masalah LP ganda;
Metode "cabang dan batas" untuk menyelesaikan masalah LP bilangan bulat;
Metode Gomory untuk memecahkan masalah LP bilangan bulat;
Metode balash untuk menyelesaikan masalah LP Boolean.
Bandingkan hasil solusi dengan metode yang berbeda untuk menarik kesimpulan yang sesuai pada pekerjaan.
2. Solusi grafis dari masalah pemrograman linier
Metode grafis untuk memecahkan masalah program linier digunakan dalam kasus di mana jumlah yang tidak diketahui tidak melebihi tiga. Lebih mudah untuk studi kualitatif tentang sifat-sifat solusi dan digunakan bersama dengan metode lain (aljabar, cabang dan terikat, dll.). Ide metode ini didasarkan pada solusi grafis dari sistem pertidaksamaan linier.
Beras. 2 Solusi grafis dari masalah LP
Poin rendah
Persamaan garis lurus yang melalui dua titik A1 dan A2:
AB: (0;1); (3;3)
Matahari: (3;3); (4;1)
CD: (4;1); (3;0)
EA: (1;0); (0;1)
CF: (0;1); (5;2)
dengan batasan:
Memecahkan masalah pemrograman linier dengan metode simpleks aljabar
Penerapan metode aljabar untuk memecahkan masalah memerlukan generalisasi representasi masalah LP. Sistem asli kendala yang diberikan dalam bentuk pertidaksamaan dikonversi ke notasi standar ketika kendala diberikan dalam bentuk persamaan. Mengubah sistem kendala ke bentuk standar mencakup langkah-langkah berikut:
Transformasikan ketidaksetaraan sedemikian rupa sehingga variabel dan anggota bebas berada di sebelah kiri, dan 0 di sebelah kanan, mis. bahwa ruas kiri lebih besar dari atau sama dengan nol;
Perkenalkan variabel tambahan, yang jumlahnya sama dengan jumlah ketidaksetaraan dalam sistem pembatasan;
Memperkenalkan pembatasan tambahan pada non-negatif dari variabel yang ditambahkan, ganti tanda pertidaksamaan dengan tanda sama dengan yang ketat.
Ketika memecahkan masalah LP dengan metode aljabar, kondisi ditambahkan: fungsi tujuan harus cenderung minimum. Jika kondisi ini tidak terpenuhi, maka perlu untuk mentransformasikan fungsi tujuan (kalikan dengan -1) dengan tepat dan menyelesaikan masalah minimisasi. Setelah solusinya ditemukan, substitusikan nilai-nilai variabel dalam fungsi asli dan hitung nilainya.
Penyelesaian masalah menggunakan metode aljabar dianggap optimal ketika nilai semua variabel dasar non-negatif, dan koefisien variabel bebas dalam persamaan fungsi tujuan juga non-negatif. Jika kondisi ini tidak terpenuhi, perlu untuk mengubah sistem ketidaksetaraan, mengungkapkan beberapa variabel dalam hal lain (mengubah variabel bebas dan dasar) untuk mencapai pembatasan di atas. Nilai semua variabel bebas diasumsikan nol.
Metode aljabar untuk menyelesaikan masalah program linier adalah salah satu metode yang paling efektif untuk menyelesaikan masalah dimensi kecil secara manual. tidak memerlukan banyak perhitungan aritmatika. Implementasi mesin dari metode ini lebih rumit daripada, misalnya, untuk metode simpleks, karena algoritma untuk memecahkan metode aljabar sampai batas tertentu heuristik dan efektivitas solusi sangat tergantung pada pengalaman pribadi.
variabel bebas
jalur st - Menambahkan. kit
Kondisi non-negatif terpenuhi, oleh karena itu, solusi optimal ditemukan.
3. Memecahkan masalah pemrograman linier menggunakan tabel simpleks
Solusi: Mari kita bawa masalah ke bentuk standar untuk penyelesaian menggunakan tabel simpleks.
Kami mengurangi semua persamaan sistem menjadi bentuk:
Kami membuat tabel simpleks:
Di sudut atas setiap sel tabel kita memasukkan koefisien dari sistem persamaan;
Kami memilih elemen positif maksimum di baris F, kecuali untuk ini akan menjadi kolom umum;
Untuk menemukan elemen umum, kami membangun hubungan untuk semua yang positif. 3/3; 9/1;- rasio minimum pada baris x3. Oleh karena itu - string umum dan =3 - elemen umum.
Kami menemukan = 1/=1/3. Kami membawa sudut bawah sel, tempat elemen umum berada;
Di semua sudut bawah yang tidak terisi dari garis umum, kami memasukkan produk dari nilai di sudut atas sel dengan;
Pilih sudut atas dari garis umum;
Di semua sudut bawah kolom umum, kami memasukkan produk dari nilai di sudut atas dengan - dan memilih nilai yang dihasilkan;
Sel-sel tabel yang tersisa diisi sebagai produk dari elemen terpilih yang sesuai;
Kemudian kami membuat tabel baru di mana penunjukan sel elemen kolom dan baris umum dibalik (x2 dan x3);
Di sudut atas baris dan kolom umum sebelumnya, nilai-nilai yang sebelumnya ada di sudut bawah ditulis;
Jumlah nilai sudut atas dan bawah sel-sel ini pada tabel sebelumnya ditulis di sudut atas sel yang tersisa
4. Memecahkan masalah program linier dengan mencari solusi yang layak
Biarkan sistem persamaan aljabar linier diberikan:
Kita dapat mengasumsikan bahwa semuanya, jika tidak, kita kalikan persamaan yang sesuai dengan -1.
Kami memperkenalkan variabel tambahan:
Kami juga memperkenalkan fungsi bantu
Kami akan meminimalkan sistem di bawah kendala (2) dan kondisi.
ATURAN UNTUK MENEMUKAN SOLUSI YANG LAYAK: Untuk menemukan solusi yang layak untuk sistem (1), kami meminimalkan bentuk (3) di bawah kendala (2), sebagai tidak diketahui bebas kita mengambil xj sebagai yang dasar.
Saat memecahkan masalah dengan metode simpleks, dua kasus mungkin muncul:
min f=0, maka semua i harus sama dengan nol. Dan nilai xj yang dihasilkan akan menjadi solusi fisibel untuk sistem (1).
min f>0, yaitu sistem asli tidak memiliki solusi yang layak.
Sistem sumber:
Kondisi masalah topik sebelumnya digunakan.
Mari tambahkan variabel tambahan:
Solusi yang dapat diterima untuk masalah awal ditemukan: x1 = 3, x2 = 3, F = -12. Berdasarkan solusi layak yang diperoleh, kami menemukan solusi optimal untuk masalah asli menggunakan metode simpleks. Untuk melakukan ini, kita akan membuat tabel simpleks baru dari tabel yang diperoleh di atas dengan menghapus baris dan baris dengan fungsi target dari tugas bantu:
Menganalisis tabel simpleks yang dibangun, kita melihat bahwa solusi optimal untuk masalah asli telah ditemukan (elemen pada baris yang sesuai dengan fungsi tujuan adalah negatif). Jadi, solusi fisibel yang ditemukan saat menyelesaikan masalah bantu bertepatan dengan solusi optimal dari masalah awal:
6. Masalah ganda dari program linier
Sistem awal kendala dan fungsi tujuan dari masalah ditunjukkan pada gambar di bawah ini.
dengan batasan:
Solusi: Kami membawa sistem pembatasan ke bentuk standar:
Tugas ganda untuk yang ini akan terlihat seperti:
Masalah ganda akan diselesaikan dengan metode simpleks.
Mari kita ubah fungsi tujuan sehingga masalah minimasi diselesaikan dan tulis sistem kendala dalam bentuk standar untuk penyelesaian dengan metode simpleks.
y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)
y7 = 5 - (-3y1 - y2 + y3 + y4)
= 0 - (3y1 + 9y2 + 3y3 + y4) ??min
Mari kita buat tabel simpleks awal untuk menyelesaikan masalah LP ganda.
Langkah kedua dari metode simpleks
Jadi, pada langkah ketiga dari metode simpleks, solusi optimal dari masalah minimisasi ditemukan dengan hasil sebagai berikut: y2 = -7 /8, y1 = -11/8, = 12. Untuk mencari nilai dari fungsi tujuan dari masalah ganda, kami mengganti nilai yang ditemukan dari variabel dasar dan bebas ke dalam fungsi maksimalisasi:
maks = - min = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12
Karena nilai fungsi tujuan dari masalah langsung dan ganda adalah sama, solusi untuk masalah langsung ditemukan dan sama dengan 12.
Fmin \u003d Fmax \u003d -12
7. Memecahkan masalah pemrograman linier bilangan bulat menggunakan metode “cabang dan batas”
Mari kita ubah masalah asli sedemikian rupa sehingga kondisi bilangan bulat tidak terpenuhi ketika diselesaikan dengan metode konvensional.
Poligon awal solusi untuk masalah pemrograman integer.
Mari kita membangun sistem kendala baru untuk poligon solusi yang ditransformasikan.
Kami menuliskan sistem kendala dalam bentuk persamaan, untuk diselesaikan dengan metode aljabar.
Sebagai hasil dari solusi, rencana tugas yang optimal ditemukan: x1 = 9/4, x2 = 5/2, F = -41/4. Solusi ini tidak memenuhi kondisi integral yang ditetapkan dalam masalah. Kami membagi poligon solusi asli menjadi dua wilayah, tidak termasuk wilayah 3 darinya Mengubah poligon solusi masalah Mari kita buat sistem pembatasan baru untuk daerah yang terbentuk dari poligon solusi. Area kiri adalah segi empat (trapesium). Sistem kendala untuk wilayah kiri poligon solusi disajikan di bawah ini. Sistem pembatasan untuk area kiri Wilayah kanan mewakili titik C. Sistem kendala untuk area keputusan yang tepat disajikan di bawah ini. Sistem kendala baru adalah dua masalah tambahan yang perlu diselesaikan secara independen satu sama lain. Mari kita selesaikan masalah pemrograman bilangan bulat untuk wilayah kiri poligon solusi. Sebagai hasil dari solusi, rencana tugas yang optimal ditemukan: x1 = 3, x2 = 3, F = -12. Rencana ini memenuhi kondisi variabel bilangan bulat dalam masalah dan dapat diambil sebagai rencana referensi optimal untuk masalah program linier bilangan bulat asli. Tidak masuk akal untuk melakukan solusi untuk wilayah solusi yang tepat. Gambar di bawah menunjukkan kemajuan penyelesaian masalah program linier bilangan bulat dalam bentuk pohon. Kursus memecahkan masalah pemrograman linier bilangan bulat dengan metode Gomory. Dalam banyak aplikasi praktis, masalah pemrograman bilangan bulat sangat menarik, di mana sistem pertidaksamaan linier dan bentuk linier diberikan Diperlukan untuk menemukan solusi bilangan bulat dari sistem (1) yang meminimalkan fungsi tujuan F, dan semua koefisiennya adalah bilangan bulat. Salah satu metode untuk memecahkan masalah pemrograman integer diusulkan oleh Gomory. Ide dari metode ini adalah menggunakan metode pemrograman linier kontinu, khususnya metode simpleks. 1) Dengan menggunakan metode simpleks, solusi untuk masalah (1), (2) ditentukan, di mana persyaratan bahwa solusi menjadi bilangan bulat dihilangkan; jika solusinya ternyata bilangan bulat, maka solusi yang diinginkan untuk masalah bilangan bulat juga akan ditemukan; 2) Jika tidak, jika beberapa koordinat bukan bilangan bulat, solusi yang diperoleh dari masalah diperiksa untuk kemungkinan keberadaan solusi bilangan bulat (keberadaan titik bilangan bulat dalam polihedron yang dapat diterima): jika dalam setiap baris dengan anggota bebas pecahan, semua koefisien lainnya menjadi bilangan bulat, maka tidak ada bilangan bulat, poin dalam polihedron yang dapat diterima, dan masalah pemrograman bilangan bulat tidak memiliki solusi; Jika tidak, batasan linier tambahan diperkenalkan, yang memotong dari polihedron yang dapat diterima bagian yang tidak menjanjikan untuk menemukan solusi untuk masalah pemrograman bilangan bulat; 3) Untuk membuat kendala linier tambahan, pilih baris ke-l dengan anggota bebas pecahan dan tulis kendala tambahan di mana dan masing-masing adalah bagian pecahan dari koefisien dan bebas anggota. Mari kita perkenalkan variabel tambahan ke dalam kendala (3): Mari kita tentukan koefisien dan termasuk dalam kendala (4): di mana dan adalah bilangan bulat bawah terdekat untuk dan, masing-masing. Gomory membuktikan bahwa sejumlah langkah seperti itu mengarah ke masalah pemrograman linier yang solusinya adalah bilangan bulat dan, oleh karena itu, yang diinginkan. Solusi: Kami mengurangi sistem kendala linier dan fungsi tujuan ke bentuk kanonik: Mari kita tentukan solusi optimal dari sistem kendala linier, sementara membuang kondisi bilangan bulat. Kami menggunakan metode simpleks untuk ini. Tabel di bawah ini secara berurutan menyajikan solusi awal dari masalah, dan transformasi dari tabel asli diberikan untuk mendapatkan solusi optimal untuk masalah tersebut: Memecahkan masalah Boolean LP dengan metode Balash. Buat secara independen varian untuk masalah pemrograman linier bilangan bulat dengan variabel Boolean, dengan mempertimbangkan aturan berikut: masalah menggunakan setidaknya 5 variabel, setidaknya 4 batasan, koefisien batasan dan fungsi tujuan dipilih secara acak, tetapi sedemikian cara agar sistem pembatasan kompatibel. Tugasnya adalah untuk memecahkan ZCLP dengan variabel Boolean menggunakan algoritma Balash dan menentukan pengurangan kompleksitas komputasi dalam kaitannya dengan pemecahan masalah dengan pencarian lengkap. Eksekusi pembatasan nilai F Batasan filter: Perhitungan Pengurangan Penentuan Solusi dari masalah dengan metode pencarian lengkap adalah 6*25=192 ekspresi terhitung. Solusi dari masalah dengan metode Balash adalah 3*6+(25-3)=47 ekspresi terhitung. Pengurangan total dalam kompleksitas perhitungan dalam kaitannya dengan pemecahan masalah dengan metode pencarian lengkap adalah. Kesimpulan Proses perancangan sistem informasi yang mengimplementasikan teknologi informasi baru terus ditingkatkan. Sistem yang semakin kompleks menjadi fokus perhatian para insinyur sistem, yang membuatnya sulit untuk menggunakan model fisik dan meningkatkan pentingnya model matematika dan simulasi komputer dari sistem. Pemodelan mesin telah menjadi alat yang efektif untuk penelitian dan desain sistem yang kompleks. Relevansi model matematika terus meningkat karena fleksibilitasnya, kecukupannya untuk proses nyata, biaya implementasi yang rendah berdasarkan PC modern. Semakin banyak peluang diberikan kepada pengguna, yaitu, spesialis dalam pemodelan sistem melalui teknologi komputer. Penggunaan pemodelan sangat efektif pada tahap awal perancangan sistem otomatis, ketika biaya keputusan yang salah paling signifikan. Alat komputasi modern telah memungkinkan untuk secara signifikan meningkatkan kompleksitas model yang digunakan dalam studi sistem, menjadi mungkin untuk membangun model gabungan, analitik dan simulasi yang memperhitungkan seluruh variasi faktor yang terjadi dalam sistem nyata, yaitu penggunaan model yang lebih memadai terhadap fenomena yang diteliti. Literatur: 1. Lyashchenko I.N. Pemrograman linier dan non-linier / I.N. Lyashchenko, E.A. Karagodova, N.V. Chernikova, N.Z. Shor. - K.: "Sekolah Tinggi", 1975, 372 hal. 2. Pedoman pelaksanaan proyek kursus dalam disiplin "Matematika Terapan" untuk siswa dari "Sistem dan Jaringan Komputer" khusus bentuk pendidikan penuh waktu dan paruh waktu / Disusun oleh: I.A. Balakireva, A.V. Skatkov - Sevastopol: Penerbitan SevNTU , 2003. - 15 hal. 3. Pedoman studi disiplin "Matematika Terapan", bagian "Metode pencarian global dan minimalisasi satu dimensi" / Comp. A.V. Skatkov, I.A. Balakireva, L.A. Litvinova - Sevastopol: Rumah Penerbitan SevGTU, 2000. - 31s. 4. Pedoman untuk mempelajari disiplin "Matematika Terapan" untuk siswa khusus "Sistem dan Jaringan Komputer" Bagian "Memecahkan Masalah Pemrograman Linier Integer" dari bentuk pendidikan penuh waktu dan korespondensi / Disusun oleh: I.A. Balakireva, A.V. Skatkov - Sevastopol : Penerbitan SevNTU, 2000. - 13 hal. 5. Akulich I.L. Pemrograman matematika dalam contoh dan tugas: 6. Prok. tunjangan ekonomi mahasiswa. spesialis. universitas.-M.: Lebih tinggi. sekolah, 1986.- 319s., sakit. 7. Andronov S.A. Metode desain yang optimal: Teks kuliah / SPbGUAP. SPb., 2001. 169 hal.: sakit. Algoritma untuk menyelesaikan masalah program linier dengan metode simpleks. Konstruksi model matematika dari masalah pemrograman linier. Memecahkan masalah pemrograman linier di Excel. Mencari keuntungan dan rencana produksi yang optimal. makalah, ditambahkan 21/03/2012 Pemecahan masalah grafis. Membuat model matematika. Menentukan nilai maksimum dari fungsi tujuan. Solusi dengan metode simpleks dengan basis buatan dari masalah program linier kanonik. Memeriksa optimalitas solusi. tes, ditambahkan 04/05/2016 Dasar teori pemrograman linier. Masalah pemrograman linier, metode solusi. Analisis solusi optimal. Solusi dari masalah program linier indeks tunggal. Pernyataan masalah dan entri data. Pembuatan model dan langkah-langkah solusi. makalah, ditambahkan 12/09/2008 Konstruksi model matematika. Pemilihan, justifikasi dan deskripsi metode penyelesaian masalah langsung program linier dengan metode simpleks, dengan menggunakan tabel simpleks. Perumusan dan solusi dari masalah ganda. Analisis model untuk sensitivitas. makalah, ditambahkan 31/10/2014 Membangun model matematika untuk memaksimalkan keuntungan perusahaan, solusi grafis untuk masalah tersebut. Pemecahan masalah menggunakan add-on SOLVER. Analisis perubahan cadangan sumber daya. Penentuan batas-batas perubahan koefisien fungsi tujuan. makalah, ditambahkan 17/12/2014 Pemrograman matematika. pemrograman linier. Masalah pemrograman linier. Metode grafis untuk memecahkan masalah program linier. Perumusan ekonomi masalah program linier. Konstruksi model matematika. makalah, ditambahkan 13/10/2008 Memecahkan masalah pemrograman linier dengan metode grafis, verifikasi di MS Excel. Analisis struktur internal solusi masalah dalam program. Optimalisasi rencana produksi. Penyelesaian masalah dengan metode simpleks. Sistem antrian multichannel. tes, ditambahkan 05/02/2012 Memecahkan masalah program linier dengan metode simpleks: menetapkan masalah, membangun model ekonomi dan matematika. Solusi masalah transportasi dengan metode potensi: konstruksi rencana referensi awal, penentuan nilai optimalnya. tes, ditambahkan 11/04/2012 Pernyataan masalah pemrograman nonlinier. Penentuan titik stasioner dan jenisnya. Konstruksi garis level, grafik tiga dimensi dari fungsi tujuan dan batasan. Solusi grafis dan analitis dari masalah. Panduan pengguna dan skema algoritma. makalah, ditambahkan 17/12/2012 Analisis solusi dari masalah program linier. Metode simpleks menggunakan tabel simpleks. Pemodelan dan solusi masalah LP di komputer. Interpretasi ekonomi dari solusi optimal masalah. Rumusan matematika dari masalah transportasi. Kami membagi baris ketiga dengan elemen kunci sama dengan 5, kami mendapatkan baris ketiga dari tabel baru. Kolom dasar sesuai dengan kolom tunggal. Perhitungan nilai tabel yang tersisa: "BP - Paket Dasar": ; "x1": "x5": Nilai baris indeks adalah non-negatif, oleh karena itu kami memperoleh solusi optimal: , ; Menjawab: keuntungan maksimum dari penjualan produk manufaktur, sama dengan 160/3 unit, dipastikan dengan pelepasan hanya produk tipe kedua dalam jumlah 80/9 unit. Masalah pemrograman nonlinier diberikan. Temukan maksimum dan minimum dari fungsi tujuan menggunakan metode analisis grafik. Susunlah fungsi Lagrange dan tunjukkan bahwa kondisi minimum (maksimum) yang memadai dipenuhi pada titik-titik ekstrem. Karena digit terakhir cipher adalah 8, maka A=2; B=5. Karena digit terakhir dari cipher adalah 1, maka Anda harus memilih tugas nomor 1. Keputusan: 1) Mari kita menggambar area yang didefinisikan oleh sistem pertidaksamaan. Luas ini adalah segitiga ABC dengan koordinat titik-titik: A(0; 2); B(4; 6) dan C(16/3; 14/3). Tingkat fungsi tujuan adalah lingkaran yang berpusat di titik (2; 5). Kuadrat jari-jari akan menjadi nilai fungsi tujuan. Kemudian gambar menunjukkan bahwa nilai minimum dari fungsi tujuan tercapai pada titik H, nilai maksimum baik pada titik A atau pada titik C. Nilai fungsi tujuan di titik A: ; Nilai fungsi tujuan di titik C: ; Ini berarti bahwa nilai maksimum fungsi tercapai pada titik A(0; 2) dan sama dengan 13. Tentukan koordinat titik H. Untuk melakukan ini, pertimbangkan sistem: Sebuah garis bersinggungan dengan lingkaran jika persamaan memiliki solusi yang unik. Persamaan kuadrat memiliki solusi unik jika diskriminannya adalah 0. 2) Susun fungsi Lagrange untuk mencari solusi minimum: Pada x 1
=2.5;
x 2
=4.5
kita mendapatkan: Sistem memiliki solusi untuk , mis. kondisi ekstrem yang cukup terpenuhi. Kami menyusun fungsi Lagrange untuk menemukan solusi maksimum: Kondisi yang cukup untuk ekstrem: Pada x 1
=0;
x 2
=2
kita mendapatkan: Sistem ini juga memiliki solusi, yaitu kondisi ekstrem yang cukup terpenuhi. Menjawab: minimum dari fungsi tujuan tercapai pada Dua perusahaan dialokasikan dana dalam jumlah d unit. Ketika dialokasikan ke perusahaan pertama selama satu tahun x unit dana yang memberikan pendapatan k 1
x unit, dan ketika dialokasikan ke perusahaan kedua kamu unit dana, itu memberikan pendapatan k 1
kamu unit. Saldo dana pada akhir tahun untuk perusahaan pertama sama dengan nx, dan untuk yang kedua -ku. Bagaimana cara mendistribusikan semua dana dalam waktu 4 tahun agar total pendapatan terbesar? Memecahkan masalah dengan pemrograman dinamis. i=8, k=1. J=2200; k 1 = 6; k2=1; n=0.2; m = 0,5. Keputusan: Seluruh periode 4 tahun dibagi menjadi 4 tahap yang masing-masing sama dengan satu tahun. Mari kita beri nomor tahapan mulai dari tahun pertama. Misalkan X k dan Y k adalah dana yang dialokasikan masing-masing untuk perusahaan A dan B pada tahap ke-k. Maka jumlah X k + Y k =a k adalah jumlah total dana yang digunakan pada tahap k - itu dan sisa dari tahap sebelumnya k - 1. pada tahap pertama semua dana yang dialokasikan digunakan dan a 1 =2200 unit. pendapatan yang akan diterima pada k - tahap itu, ketika unit X k dan Y k dialokasikan, akan menjadi 6X k + 1Y k . biarkan pendapatan maksimum yang diterima pada tahap terakhir dimulai dari k - tahap itu adalah f k (a k) unit. Mari kita tulis persamaan fungsional Bellman yang menyatakan prinsip optimalitas: berapa pun keadaan awal dan solusi awal, solusi selanjutnya harus optimal terhadap keadaan yang diperoleh sebagai hasil dari keadaan awal: Untuk setiap tahap, Anda harus memilih nilai X k , dan nilainya y k=ak- Xk. Dengan mengingat hal ini, kita akan menemukan pendapatan pada tahap ke-k: Persamaan Bellman fungsional akan terlihat seperti: Pertimbangkan semua tahapan, dimulai dengan yang terakhir. (karena maksimum fungsi linier dicapai pada akhir segmen pada x 4 = a 4); fungsi objektif- fungsi nyata atau bilangan bulat dari beberapa variabel, tunduk pada optimasi (minimalisasi atau maksimalisasi) untuk memecahkan beberapa masalah optimasi. Istilah ini digunakan dalam pemrograman matematika, riset operasi, pemrograman linier, teori keputusan statistik dan bidang matematika lainnya, terutama yang bersifat terapan, meskipun tujuan optimasi juga dapat menjadi solusi dari masalah matematika itu sendiri. Selain fungsi tujuan dalam masalah optimasi, variabel dapat dikenakan pembatasan dalam bentuk sistem persamaan atau ketidaksetaraan. Dalam kasus umum, argumen fungsi tujuan dapat ditentukan pada himpunan arbitrer. Masalah penyelesaian sistem persamaan apa pun ( F 1 (x 1 , x 2 , … , x M) = 0 F 2 (x 1 , x 2 , … , x M) = 0 … F N (x 1 , x 2 , … , x M) = 0 ( \displaystyle \left\((\begin(matrix)F_(1)(x_(1),x_(2),\ldots ,x_(M))=0\\F_(2)(x_(1),x_ (2),\ldots ,x_(M))=0\\\ldots \\F_(N)(x_(1),x_(2),\ldots ,x_(M))=0\end(matriks) )\Baik.) dapat dirumuskan sebagai masalah meminimalkan fungsi tujuan S = j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) (\displaystyle S=\sum _(j=1)^(N)F_(j)^(2)( x_(1),x_(2),\ldots ,x_(M))\qquad(1)) Jika fungsinya mulus, maka masalah minimasi dapat diselesaikan dengan metode gradien. Untuk setiap fungsi tujuan halus, seseorang dapat menyamakan dengan 0 (\displaystyle 0) turunan parsial terhadap semua variabel. Fungsi tujuan yang optimal akan menjadi salah satu solusi untuk sistem persamaan tersebut. Dalam kasus fungsi (1) (\displaystyle (1)) ini akan menjadi sistem persamaan kuadrat terkecil (LSM). Setiap solusi dari sistem asli adalah solusi dari sistem kuadrat terkecil. Jika sistem asli tidak konsisten, maka sistem LSM, yang selalu memiliki solusi, memungkinkan untuk mendapatkan solusi perkiraan dari sistem asli. Jumlah persamaan sistem LSM bertepatan dengan jumlah yang tidak diketahui, yang terkadang memfasilitasi solusi sistem awal gabungan. Contoh lain yang terkenal dari fungsi tujuan adalah fungsi linier yang terjadi dalam masalah pemrograman linier. Berbeda dengan fungsi tujuan kuadrat, optimasi fungsi linier hanya dimungkinkan jika terdapat pembatasan berupa sistem persamaan atau pertidaksamaan linier. Contoh khas dari fungsi tujuan kombinatorial adalah fungsi tujuan dari masalah penjual keliling. Fungsi ini sama dengan panjang siklus Hamilton pada grafik. Ini diberikan pada himpunan permutasi n 1 (\displaystyle n-1) dari simpul graf dan ditentukan oleh matriks panjang tepi graf. Solusi yang tepat dari masalah seperti itu sering kali bermuara pada penghitungan opsi. Pemrograman linier adalah cabang dari pemrograman matematika yang mempelajari metode untuk memecahkan masalah ekstrem yang dicirikan oleh hubungan linier antara variabel dan kriteria linier. Tugas-tugas seperti itu menemukan aplikasi yang luas di berbagai bidang aktivitas manusia. Sebuah studi sistematis masalah jenis ini dimulai pada tahun 1939-1940. dalam karya L.V. Kantorovich. Masalah matematika program linier mencakup studi produksi tertentu dan situasi ekonomi, yang dalam satu atau lain bentuk ditafsirkan sebagai masalah penggunaan sumber daya yang terbatas secara optimal. Rentang masalah yang diselesaikan dengan menggunakan metode pemrograman linier cukup luas, antara lain: masalah penggunaan sumber daya yang optimal dalam perencanaan produksi; masalah campuran (merencanakan komposisi produk); masalah menemukan kombinasi optimal dari berbagai jenis produk untuk penyimpanan di gudang (manajemen inventaris atau); tugas transportasi (analisis lokasi perusahaan, pergerakan barang). Pemrograman linier adalah bagian yang paling berkembang dan banyak digunakan dari pemrograman matematika (selain itu, ini termasuk: bilangan bulat, dinamis, non-linier, pemrograman parametrik). Hal ini dijelaskan sebagai berikut: model matematika dari sejumlah besar masalah ekonomi adalah linier terhadap variabel yang diperlukan; jenis masalah saat ini yang paling dipelajari. Baginya, metode khusus telah dikembangkan dengan bantuan yang memecahkan masalah ini, dan program komputer yang sesuai; banyak masalah pemrograman linier, yang dipecahkan, telah menemukan aplikasi yang luas; beberapa masalah yang tidak linier dalam formulasi aslinya, setelah sejumlah batasan dan asumsi tambahan, dapat menjadi linier atau dapat direduksi menjadi bentuk sedemikian rupa sehingga dapat diselesaikan dengan metode pemrograman linier. Model ekonomi dan matematika dari setiap masalah program linier meliputi: fungsi tujuan, nilai optimal yang (maksimum atau minimum) harus ditemukan; pembatasan berupa sistem persamaan atau pertidaksamaan linier; persyaratan non-negatif variabel. Secara umum, model ditulis sebagai berikut: fungsi objektif (1.1) di bawah batasan Masalahnya adalah mencari nilai optimal dari fungsi (1.1) yang tunduk pada kendala (1.2) dan (1.3). Sistem kendala (1.2) disebut kendala fungsional dari masalah, dan kendala (1.3) disebut kendala langsung. Sebuah vektor yang memenuhi kendala (1.2) dan (1.3) disebut solusi layak (rencana) dari masalah program linier. Rencana di mana fungsi (1.1) mencapai nilai maksimum (minimum) disebut optimal. Metode simpleks dikembangkan dan pertama kali diterapkan untuk memecahkan masalah pada tahun 1947 oleh matematikawan Amerika J. Dantzig. Masalah pemrograman linier dua dimensi diselesaikan secara grafis. Untuk kasus N=3, kita dapat mempertimbangkan ruang tiga dimensi dan fungsi tujuan akan mencapai nilai optimalnya di salah satu simpul polihedron. Solusi yang dapat diterima (rencana yang dapat diterima) dari masalah LP yang diberikan dalam bentuk standar adalah himpunan bilangan berurutan (x1, x2, ..., xn) yang memenuhi kendala; adalah titik dalam ruang n-dimensi. Himpunan solusi yang dapat diterima membentuk area solusi yang dapat diterima (SDR) dari masalah LP. ODR adalah polihedron cembung (poligon). Secara umum, ketika N-tidak diketahui terlibat dalam masalah, kita dapat mengatakan bahwa area solusi layak yang ditentukan oleh sistem kondisi pembatas diwakili oleh polihedron cembung dalam ruang n-dimensi dan nilai optimal tujuan fungsi dicapai pada satu atau lebih simpul. Suatu solusi disebut dasar jika semua variabel bebas sama dengan nol. Solusi referensi adalah solusi non-negatif dasar. Solusi dukungan dapat berupa non-degenerasi dan degenerasi. Solusi pendukung disebut non-degenerate jika jumlah koordinat non-nolnya sama dengan peringkat sistem, jika tidak maka akan degenerate. Solusi yang layak, di mana fungsi tujuan mencapai nilai ekstrimnya, disebut optimal dan dilambangkan Sangat sulit untuk menyelesaikan masalah ini secara grafis ketika jumlah variabel lebih dari 3. Ada cara universal untuk menyelesaikan masalah pemrograman linier, yang disebut metode simpleks. Metode simpleks adalah metode universal untuk menyelesaikan masalah LP, yang merupakan proses iteratif yang dimulai dengan satu solusi dan, dalam mencari opsi terbaik, bergerak sepanjang titik sudut dari area solusi yang layak hingga mencapai nilai optimal. . Ini dapat digunakan untuk menyelesaikan masalah pemrograman linier apa pun. Metode simpleks didasarkan pada gagasan peningkatan berturut-turut dari solusi yang dihasilkan. Arti geometris dari metode simpleks adalah berpindah secara berurutan dari satu simpul polihedron kendala ke simpul tetangga, di mana fungsi tujuan mengambil nilai terbaik (atau setidaknya bukan yang terburuk) sampai solusi optimal ditemukan - simpul di mana nilai optimal tercapai fungsi tujuan (jika masalah memiliki optimal terbatas). Jadi, memiliki sistem kendala yang direduksi menjadi bentuk kanonik (semua kendala fungsional dalam bentuk persamaan), seseorang menemukan solusi dasar dari sistem ini, hanya dengan berhati-hati untuk menemukannya sesederhana mungkin. Jika solusi dasar yang pertama kali ditemukan ternyata layak, maka diperiksa optimalitasnya. Jika tidak optimal, maka transisi dibuat ke solusi dasar lain yang tentu dapat diterima. Metode simpleks menjamin bahwa, dengan solusi baru ini, fungsi tujuan, jika tidak mencapai optimum, maka mendekatinya (atau setidaknya tidak menjauhinya). Dengan solusi dasar baru yang dapat diterima, hal yang sama dilakukan sampai ditemukan solusi yang optimal. Proses penerapan metode simpleks melibatkan penerapan tiga elemen utamanya: metode untuk menentukan solusi dasar yang layak awal untuk masalah tersebut; aturan transisi ke solusi terbaik (lebih tepatnya, bukan yang terburuk); kriteria untuk memeriksa optimalitas solusi yang ditemukan. Metode simpleks mencakup sejumlah langkah dan dapat dirumuskan sebagai algoritma yang jelas (instruksi yang jelas untuk melakukan operasi sekuensial). Ini memungkinkan Anda untuk berhasil memprogram dan mengimplementasikannya di komputer. Masalah dengan sejumlah kecil variabel dan kendala dapat diselesaikan dengan metode simpleks secara manual. Optimasi. Bagian 1 Metode pengoptimalan memungkinkan Anda memilih opsi desain terbaik dari semua opsi yang memungkinkan. Dalam beberapa tahun terakhir, banyak perhatian telah diberikan pada metode ini, dan sebagai hasilnya, sejumlah algoritma yang sangat efisien telah dikembangkan yang memungkinkan untuk menemukan opsi desain yang optimal menggunakan komputer digital. Bab ini menguraikan dasar-dasar teori optimasi, mempertimbangkan prinsip-prinsip yang mendasari konstruksi algoritma untuk solusi optimal, menjelaskan algoritma yang paling terkenal, dan menganalisis kelebihan dan kekurangannya. Istilah "optimasi" dalam literatur mengacu pada proses atau urutan operasi yang memungkinkan Anda untuk mendapatkan solusi yang disempurnakan. Meskipun tujuan akhir dari optimasi adalah untuk menemukan solusi terbaik, atau "optimal", seseorang biasanya harus puas dengan meningkatkan solusi yang diketahui daripada menyempurnakannya. Oleh karena itu, optimasi lebih mungkin dipahami sebagai mengejar kesempurnaan, yang mungkin tidak akan tercapai. Mempertimbangkan beberapa sistem arbitrer yang dijelaskan oleh m persamaan dengan n yang tidak diketahui, kita dapat membedakan tiga jenis masalah utama. Jika m=n , masalahnya disebut aljabar. Masalah seperti itu biasanya memiliki satu solusi. Jika m>n, maka masalahnya didefinisikan ulang dan, sebagai aturan, tidak memiliki solusi. Akhirnya, untuk m Sebelum melanjutkan ke pembahasan masalah optimasi, kami memperkenalkan sejumlah definisi. Parameter desain
Istilah ini menunjukkan parameter variabel independen yang secara lengkap dan jelas mendefinisikan masalah desain yang sedang dipecahkan. Parameter desain adalah jumlah yang tidak diketahui, yang nilainya dihitung selama proses optimasi. Setiap kuantitas dasar atau turunan yang berfungsi untuk menggambarkan sistem secara kuantitatif dapat berfungsi sebagai parameter desain. Jadi, dapat diketahui nilai panjang, massa, waktu, suhu. Jumlah parameter desain mencirikan tingkat kompleksitas masalah desain ini. Biasanya jumlah parameter desain dilambangkan dengan n, dan parameter desain itu sendiri dengan x dengan indeks yang sesuai. Dengan demikian, n parameter desain dari masalah ini akan dilambangkan dengan fungsi objektif
Ini adalah ekspresi yang nilainya ingin dimaksimalkan atau diminimalkan oleh insinyur. Fungsi tujuan memungkinkan Anda untuk membandingkan dua solusi alternatif secara kuantitatif. Dari sudut pandang matematika, fungsi tujuan menggambarkan beberapa (n + 1) - permukaan dimensi. Nilainya ditentukan oleh parameter desain M=M(x 1 , x 2 ,...,x n). Contoh fungsi tujuan, yang sering dijumpai dalam praktik rekayasa, adalah biaya, berat, kekuatan, dimensi, efisiensi. Jika hanya ada satu parameter desain, maka fungsi tujuan dapat direpresentasikan dengan kurva pada bidang (Gbr. 6.1). Jika ada dua parameter desain, maka fungsi target akan diwakili oleh permukaan dalam ruang tiga dimensi (Gbr. 6.2). Dengan tiga atau lebih parameter desain, permukaan yang ditentukan oleh fungsi tujuan disebut hypersurfaces dan tidak dapat digambarkan. zheniya berarti konvensional. Sifat topologi permukaan fungsi target memainkan peran penting dalam proses optimasi, karena pilihan algoritma yang paling efisien tergantung pada mereka. Fungsi tujuan dalam beberapa kasus dapat mengambil bentuk yang paling tidak terduga. Misalnya, tidak selalu mungkin untuk mengungkapkannya dalam Gambar 1. Fungsi tujuan satu dimensi. Gbr.6.2.Fungsi tujuan dua dimensi. bentuk matematika tertutup, dalam kasus lain dapat menjadi fungsi halus sepotong-sepotong. Fungsi tujuan terkadang memerlukan tabel data teknis (misalnya, tabel keadaan uap) atau mungkin diperlukan untuk melakukan eksperimen. Dalam beberapa kasus, parameter desain hanya mengambil nilai integer. Contohnya adalah jumlah gigi pada roda gigi atau jumlah baut pada flensa. Terkadang parameter desain hanya memiliki dua nilai - ya atau tidak. Parameter kualitatif, seperti kepuasan pelanggan, keandalan, estetika, sulit untuk diperhitungkan dalam proses pengoptimalan, karena hampir tidak mungkin untuk diukur. Namun, dalam bentuk apa pun fungsi tujuan disajikan, itu harus menjadi fungsi bernilai tunggal dari parameter desain. Dalam sejumlah masalah optimasi, pengenalan lebih dari satu fungsi tujuan diperlukan. Terkadang salah satu dari mereka mungkin tidak cocok dengan yang lain. Contohnya adalah desain pesawat, ketika diperlukan untuk memberikan kekuatan maksimum, berat minimum dan biaya minimum pada saat yang bersamaan. Dalam kasus seperti itu, perancang harus memperkenalkan sistem prioritas dan menetapkan pengali tak berdimensi untuk setiap fungsi tujuan. Akibatnya, "fungsi kompromi" muncul, yang memungkinkan satu fungsi tujuan gabungan untuk digunakan dalam proses optimasi. Mencari minimum dan maksimum
Beberapa algoritma optimasi diadaptasi untuk menemukan maksimum, yang lain untuk menemukan minimum. Namun, terlepas dari jenis masalah ekstrem yang dipecahkan, seseorang dapat menggunakan algoritma yang sama, karena masalah minimasi dapat dengan mudah diubah menjadi masalah maksimum dengan mengubah tanda fungsi tujuan menjadi kebalikannya. Teknik ini diilustrasikan pada Gambar 6.3. Ruang desain
Ini adalah nama area yang ditentukan oleh semua n parameter desain. Ruang desain tidak sebesar yang terlihat, karena biasanya terbatas pada beberapa ruangan kondisi yang terkait dengan esensi fisik masalah. Kendala bisa begitu kuat sehingga tugas tidak akan ada Gbr.6.3 Mengubah tanda fungsi tujuan menjadi kebalikannya Tugas maksimum menjadi tugas minimum. solusi yang memuaskan. Kendala dibagi menjadi dua kelompok: kendala - persamaan dan kendala - ketidaksetaraan. Kendala - kesetaraan
Kendala - persamaan - adalah ketergantungan antara parameter desain yang harus diperhitungkan ketika menemukan solusi. Mereka mencerminkan hukum alam, ekonomi, hak, selera yang berlaku dan ketersediaan bahan yang diperlukan. Jumlah batasan - persamaan bisa berapa saja. Mereka terlihat seperti C 1 (x 1 , x 2 ,...,x n)=0, C 2 (x 1 , x 2 ,...,x n)=0, .................. C j (x 1 , x 2 ,...,x n)=0. Jika salah satu dari hubungan ini dapat diselesaikan sehubungan dengan salah satu parameter desain, maka ini memungkinkan Anda untuk mengecualikan parameter ini dari proses pengoptimalan. Ini mengurangi jumlah dimensi ruang desain dan menyederhanakan solusi masalah. Kendala - ketidaksetaraan
Ini adalah jenis kendala khusus yang diekspresikan oleh ketidaksetaraan. Dalam kasus umum, jumlahnya bisa berapa saja, dan semuanya memiliki bentuk z 1 r 1 (x 1 , x 2 ,...,x n) Z 1 z 2 r 2 (x 1 , x 2 ,...,x n) Z 2 ....................... z k r k (x 1 , x 2 ,...,x n) Z k Perlu dicatat bahwa sangat sering, karena keterbatasan, nilai optimal dari fungsi tujuan tidak tercapai di mana permukaannya memiliki gradien nol. Seringkali solusi terbaik ada di salah satu batas domain desain. Optimal lokal
Ini adalah nama titik dalam ruang desain di mana fungsi tujuan memiliki nilai terbesar dibandingkan dengan nilainya di semua titik lain di lingkungan terdekatnya. Gbr.6.4 Sebuah fungsi tujuan arbitrer dapat memiliki beberapa optimal lokal. pada gambar. Gambar 6.4 menunjukkan fungsi tujuan satu dimensi yang memiliki dua local optima. Seringkali ruang desain mengandung banyak local optima dan harus berhati-hati agar tidak salah memilih solusi optimal untuk masalah tersebut. Optimal Global
Optimal global adalah solusi optimal untuk seluruh ruang desain. Ini lebih baik daripada semua solusi lain yang terkait dengan local optima, dan inilah yang dicari oleh perancang. Kasus beberapa optima global yang sama yang terletak di berbagai bagian ruang desain dimungkinkan. Bagaimana masalah optimasi diajukan paling baik diilustrasikan dengan sebuah contoh. Contoh 6.1
Biarkan diperlukan untuk merancang wadah persegi panjang dengan volume 1 m , yang dirancang untuk mengangkut serat yang tidak dikemas. Diinginkan bahwa bahan sesedikit mungkin dihabiskan untuk pembuatan wadah tersebut (dengan asumsi ketebalan dinding konstan, ini berarti luas permukaan harus minimal), karena akan lebih murah. Agar nyaman membawa wadah dengan forklift, lebarnya harus minimal 1,5 m. Mari kita merumuskan masalah ini dalam bentuk yang nyaman untuk menerapkan algoritma optimasi. Parameter desain: x 1 , x 2 , x 3 . Fungsi objektif (yang perlu diminimalkan) adalah luas permukaan samping wadah: A=2(x 1 x 2 +x 2 x 3 +x 1 x 3), m2. Batasan - kesetaraan: Volume \u003d x 1 x 2 x 3 \u003d 1m3. Batasan - ketidaksetaraan: Pemrograman Linier (LP) adalah salah satu bagian dari pemrograman matematika - disiplin yang mempelajari masalah ekstrem (optimasi) dan mengembangkan metode untuk menyelesaikannya. Masalah pengoptimalan adalah masalah matematika yang terdiri dalam menemukan nilai optimal (yaitu, maksimum atau minimum) dari fungsi tujuan, dan nilai-nilai variabel harus termasuk dalam area nilai yang dapat diterima (ODV) tertentu. Secara umum, rumusan masalah ekstrem pemrograman matematika terdiri dari penentuan nilai terbesar atau terkecil dari fungsi , yang disebut fungsi objektif, di bawah kondisi (pembatasan) , di mana dan diberikan fungsi, dan diberikan konstanta. Pada saat yang sama, pembatasan berupa persamaan dan pertidaksamaan menentukan himpunan (wilayah) solusi layak (ODS), dan disebut parameter desain. Tergantung pada jenis fungsi dan masalah pemrograman matematika dibagi menjadi beberapa kelas (linear, non-linear, cembung, integer, stokastik, pemrograman dinamis, dll). PADA pandangan umum Masalah LP memiliki bentuk berikut: , dimana , , diberikan konstanta. Fungsi (5.1) disebut fungsi tujuan; sistem (5.2), (5.3) - oleh sistem kendala; kondisi (5.4) adalah kondisi non-negatif dari parameter desain. Himpunan parameter desain yang memenuhi batasan (5.2), (5.3) dan (5.4) disebut solusi yang dapat diterima atau rencana. Solusi optimal atau rencana optimal Masalah LP disebut solusi layak, di mana fungsi tujuan (5.1) mengambil nilai optimal (maksimum atau minimum). tugas standar LP disebut masalah menemukan nilai maksimum (minimum) dari fungsi tujuan (5.1) pada kondisi (5.2) dan (5.4), dimana , , yaitu. itu. pembatasan hanya berupa pertidaksamaan (5.2) dan semua parameter desain memenuhi syarat non-negatif, dan tidak ada syarat berupa persamaan: Tugas kanonik (utama) LP disebut masalah menemukan nilai maksimum (minimum) dari fungsi tujuan (5.1) pada kondisi (5.3) dan (5.4), dimana , , yaitu. itu. pembatasan hanya dalam bentuk persamaan (5.3) dan semua parameter desain memenuhi kondisi non-negatif, dan tidak ada kondisi dalam bentuk ketidaksetaraan: Masalah LP kanonik juga dapat ditulis dalam bentuk matriks dan vektor. Bentuk matriks dari masalah LP kanonik memiliki bentuk sebagai berikut: Bentuk vektor dari masalah LP kanonik. Jika hanya ada satu faktor pembatas (misalnya, mesin yang langka), solusinya dapat ditemukan menggunakan rumus sederhana (lihat tautan di awal artikel). Jika terdapat beberapa faktor pembatas, maka digunakan metode program linier. Pemrograman linier adalah nama yang diberikan untuk kombinasi alat yang digunakan dalam ilmu manajemen. Metode ini memecahkan masalah pengalokasian sumber daya yang langka di antara aktivitas yang bersaing untuk memaksimalkan atau meminimalkan beberapa nilai numerik, seperti keuntungan atau biaya marjinal. Dalam bisnis, dapat digunakan di bidang-bidang seperti perencanaan produksi untuk memaksimalkan keuntungan, pemilihan komponen untuk meminimalkan biaya, pemilihan portofolio investasi untuk memaksimalkan profitabilitas, optimalisasi transportasi barang untuk mengurangi jarak, alokasi staf untuk memaksimalkan efisiensi kerja, dan penjadwalan kerja di untuk menghemat waktu. Unduh catatan di , gambar dalam format Pemrograman linier melibatkan konstruksi model matematika dari masalah yang sedang dipertimbangkan. Setelah itu, solusinya dapat ditemukan secara grafis (dibahas di bawah), menggunakan Excel (akan dipertimbangkan secara terpisah) atau program komputer khusus. Mungkin konstruksi model matematika adalah bagian yang paling sulit dari pemrograman linier, yang membutuhkan terjemahan masalah yang sedang dipertimbangkan ke dalam sistem variabel, persamaan dan ketidaksetaraan - sebuah proses yang pada akhirnya tergantung pada keterampilan, pengalaman, kemampuan dan intuisi dari penyusun model. Pertimbangkan contoh membangun model matematika pemrograman linier Nikolai Kuznetsov menjalankan pabrik mekanik kecil. Bulan depan, ia berencana untuk memproduksi dua produk (A dan B), di mana keuntungan marjinal spesifik diperkirakan masing-masing 2.500 dan 3.500 rubel. Pembuatan kedua produk tersebut membutuhkan biaya pemesinan, bahan baku dan tenaga kerja (Gbr. 1). Untuk pembuatan setiap unit produk A, 3 jam pemrosesan mesin, 16 unit bahan baku dan 6 unit tenaga kerja. Persyaratan yang sesuai untuk unit B adalah 10, 4, dan 6. Nikolai memprediksi bahwa bulan depan ia dapat menyediakan 330 jam pemesinan, 400 unit bahan baku, dan 240 unit tenaga kerja. Teknologi proses produksinya sedemikian rupa sehingga setidaknya 12 unit produk B harus diproduksi pada bulan tertentu. Beras. 1. Penggunaan dan penyediaan sumber daya Nikolai ingin membangun sebuah model untuk menentukan jumlah unit produk A dan B yang seharusnya ia produksi pada bulan berikutnya untuk memaksimalkan keuntungan marjinal. Model linier dapat dibangun dalam empat langkah. Tahap 1. Definisi variabel Ada variabel target (sebut saja Z) yang perlu dioptimalkan, yaitu, dimaksimalkan atau diminimalkan (misalnya, laba, pendapatan, atau pengeluaran). Nikolay berusaha memaksimalkan keuntungan marjinal, oleh karena itu, variabel targetnya adalah: Z = total keuntungan marjinal (dalam rubel) yang diterima pada bulan berikutnya sebagai hasil dari produksi produk A dan B. Ada sejumlah variabel yang tidak diketahui yang tidak diketahui (sebutkan x 1, x 2, x 3, dll.), Yang nilainya harus ditentukan untuk mendapatkan nilai optimal dari fungsi tujuan, yang, dalam kasus kami, adalah keuntungan marjinal total. Margin kontribusi ini tergantung pada kuantitas produk A dan B yang dihasilkan. Nilai kuantitas ini harus dihitung, dan oleh karena itu mereka adalah variabel yang diinginkan dalam model. Jadi mari kita tunjukkan: x 1 = jumlah unit produk A yang diproduksi pada bulan berikutnya. x 2 = jumlah unit produk B yang diproduksi pada bulan berikutnya. Sangat penting untuk mendefinisikan dengan jelas semua variabel; berikan perhatian khusus pada unit pengukuran dan periode waktu yang dirujuk oleh variabel. Panggung. 2. Konstruksi fungsi tujuan Fungsi tujuan adalah persamaan linier yang harus dimaksimalkan atau diminimalkan. Ini berisi variabel target yang dinyatakan dalam variabel yang diinginkan, yaitu Z dinyatakan dalam x 1 , x 2 ... sebagai persamaan linier. Dalam contoh kami, setiap produk yang diproduksi A membawa 2.500 rubel. keuntungan marjinal, dan dalam pembuatan x 1 unit produk A, laba marjinal akan menjadi 2500 * x 1. Demikian pula, keuntungan marjinal dari manufaktur x 2 unit produk B akan menjadi 3500 * x 2. Jadi, total keuntungan marjinal yang diterima pada bulan berikutnya karena produksi x 1 unit produk A dan x 2 unit produk B, yaitu variabel target Z adalah: Z = 2500 * x 1 + 3500 * x 2 Nikolay berupaya memaksimalkan indikator ini. Dengan demikian, fungsi tujuan dalam model kami adalah: Maksimalkan Z = 2500 * x 1 + 3500 * x 2 Panggung. 3. Definisi pembatasan Kendala adalah sistem persamaan linier dan/atau pertidaksamaan yang membatasi nilai variabel yang diperlukan. Mereka secara matematis mencerminkan ketersediaan sumber daya, faktor teknologi, kondisi pemasaran, dan persyaratan lainnya. Batasan dapat terdiri dari tiga jenis: "kurang dari atau sama", "lebih besar dari atau sama", "sangat sama". Dalam contoh kita, produk A dan B memerlukan waktu pemrosesan, bahan mentah, dan tenaga kerja untuk diproduksi, dan ketersediaan sumber daya ini terbatas. Volume produksi kedua produk ini (yaitu nilai x 1 dari 2) dengan demikian akan dibatasi oleh fakta bahwa jumlah sumber daya yang dibutuhkan dalam proses produksi tidak dapat melebihi apa yang tersedia. Pertimbangkan situasi dengan waktu pemrosesan mesin. Produksi setiap unit produk A membutuhkan tiga jam pemrosesan mesin, dan jika x 1 unit diproduksi, maka 3 * x 1 jam sumber daya ini akan dihabiskan. Produksi setiap unit produk B membutuhkan 10 jam dan, oleh karena itu, jika x 2 produk diproduksi, maka 10 * x 2 jam akan diperlukan. Jadi, jumlah total waktu mesin yang diperlukan untuk memproduksi x 1 unit produk A dan x 2 unit produk B adalah 3 * x 1 + 10 * x 2 . Total waktu mesin ini tidak boleh melebihi 330 jam. Secara matematis, ini ditulis sebagai berikut: 3 * x 1 + 10 * x 2 330 Pertimbangan serupa berlaku untuk bahan mentah dan tenaga kerja, memungkinkan dua batasan lagi untuk dituliskan: 16 * x 1 + 4 * x 2 400 6 * x 1 + 6 * x 2 240 Akhirnya, perlu dicatat bahwa ada kondisi yang menurutnya setidaknya 12 unit produk B harus diproduksi: Tahap 4. Menulis kondisi non-negatif Variabel yang diperlukan tidak boleh berupa bilangan negatif, yang harus ditulis sebagai pertidaksamaan x 1 0 dan x 2 0. Dalam contoh kita, kondisi kedua adalah redundan, karena ditentukan di atas bahwa x 2 tidak boleh kurang dari 12. Model pemrograman linier lengkap untuk masalah produksi Nikolai dapat ditulis sebagai: Maksimalkan: Z = 2500 * x 1 + 3500 * x 2 Asalkan: 3 * x 1 + 10 * x 2 330 16 * x 1 + 4 * x 2 400 6 * x 1 + 6 * x 2 240 Pertimbangkan metode grafis untuk memecahkan masalah pemrograman linier. Metode ini hanya cocok untuk masalah dengan dua variabel yang diperlukan. Model yang dibangun di atas akan digunakan untuk mendemonstrasikan metode tersebut. Sumbu pada grafik mewakili dua variabel yang tidak diketahui (Gbr. 2). Tidak masalah variabel mana yang akan diplot di sepanjang sumbu mana. Penting untuk memilih skala yang pada akhirnya akan memungkinkan Anda membuat diagram visual. Karena kedua variabel harus non-negatif, hanya kuadran pertama yang ditarik. Beras. 2. Sumbu Grafik Pemrograman Linier Perhatikan, misalnya, kendala pertama: 3 * x 1 + 10 * x 2 330. Pertidaksamaan ini menggambarkan luas di bawah garis: 3 * x 1 + 10 * x 2 = 330. Garis ini memotong sumbu x 1 pada x 2 \u003d 0, yaitu, persamaannya terlihat seperti ini: 3 * x 1 + 10 * 0 \u003d 330, dan solusinya: x 1 \u003d 330 / 3 \u003d 110 Demikian pula, kami menghitung titik potong dengan sumbu x 1 dan x 2 untuk semua kondisi kendala: Secara grafis, batasan pertama ditunjukkan pada Gambar. 3. Beras. 3. Konstruksi domain solusi layak untuk kendala pertama Setiap titik di dalam segitiga yang dipilih atau di perbatasannya akan mematuhi batasan ini. Poin seperti itu disebut valid, dan poin di luar segitiga disebut tidak valid. Demikian pula, kami mencerminkan sisa pembatasan pada grafik (Gbr. 4). Nilai x 1 dan x 2 pada atau di dalam area yang diarsir ABCDE akan memenuhi semua batasan model. Wilayah seperti itu disebut domain solusi yang dapat diterima. Beras. 4. Area solusi yang layak untuk model secara keseluruhan Sekarang, di bidang solusi yang layak, perlu untuk menentukan nilai x 1 dan x 2 yang memaksimalkan Z. Untuk melakukannya, dalam persamaan fungsi tujuan: Z = 2500 * x 1 + 3500 * x 2 kami membagi (atau mengalikan) koefisien sebelum x 1 dan x 2 dengan angka yang sama, sehingga nilai yang dihasilkan berada dalam kisaran yang ditunjukkan pada grafik; dalam kasus kami, kisaran seperti itu adalah dari 0 hingga 120; sehingga koefisien dapat dibagi dengan 100 (atau 50): Z = 25x 1 + 35x 2 kemudian berikan Z nilai yang sama dengan produk dari koefisien sebelum x 1 dan x 2 (25 * 35 = 875): 875 = 25x 1 + 35x 2 dan, akhirnya, temukan titik potong garis dengan sumbu x 1 dan x 2: Mari kita plot persamaan target ini pada grafik dengan cara yang sama seperti kendala (Gbr. 5): Beras. 5. Penerapan fungsi tujuan (garis putus-putus hitam) ke area solusi yang layak Nilai Z konstan sepanjang garis fungsi tujuan. Untuk menemukan nilai x 1 dan x 2 yang memaksimalkan Z, Anda perlu memindahkan secara paralel garis fungsi tujuan ke titik tersebut dalam batas-batas area solusi yang dapat diterima, yang terletak di maksimum jarak dari garis asli fungsi tujuan ke atas dan ke kanan, yaitu ke titik C (Gbr. 6). Beras. 6. Garis fungsi tujuan telah mencapai maksimum dalam wilayah solusi layak (di titik C) Dapat disimpulkan bahwa solusi optimal akan terletak pada salah satu titik ekstrim dari area keputusan. Di mana, itu akan tergantung pada kemiringan fungsi tujuan dan pada masalah apa yang kita selesaikan: memaksimalkan atau meminimalkan. Dengan demikian, tidak perlu menggambar fungsi tujuan - yang diperlukan hanyalah menentukan nilai x 1 dan x 2 di masing-masing titik ekstrem dengan membaca dari diagram atau dengan menyelesaikan pasangan persamaan yang sesuai. Nilai x 1 dan x 2 yang ditemukan kemudian disubstitusikan ke dalam fungsi tujuan untuk menghitung nilai Z yang sesuai. Solusi optimal adalah solusi di mana nilai maksimum Z diperoleh saat menyelesaikan masalah maksimisasi, dan solusi minimum dalam menyelesaikan masalah minimasi. Mari kita tentukan, misalnya, nilai x 1 dan x 2 di titik C. Perhatikan bahwa titik C berada di perpotongan garis: 3x 1 + 10x 2 = 330 dan 6x 1 + 6x 2 = 240. Penyelesaiannya untuk sistem persamaan ini memberikan: x 1 = 10, x 2 = 30. Hasil perhitungan untuk semua simpul dari area solusi yang layak diberikan dalam tabel: Dengan demikian, Nikolai Kuznetsom harus merencanakan produksi 10 item A dan 30 item B untuk bulan berikutnya, yang akan memungkinkannya menerima keuntungan marjinal 130 ribu rubel. Secara singkat, inti dari metode grafis untuk menyelesaikan masalah program linier dapat diringkas sebagai berikut: PEKERJAAN KONTROL PADA DISIPLIN: "METODE SOLUSI OPTIMAL" Opsi nomor 8 1.
Memecahkan masalah pemrograman linier menggunakan metode grafis. Temukan maksimum dan minimum dari fungsi di bawah batasan yang diberikan: Keputusan Penting untuk menemukan nilai minimum dari fungsi tujuan dan maksimum, di bawah sistem pembatasan: 9x1 +3x2 30, (1) X 1 + x 2 4, (2) x 1 + x 2 8, (3) Mari kita buat domain dari solusi yang dapat diterima, mis. menyelesaikan secara grafis sistem pertidaksamaan. Untuk melakukan ini, kami membangun setiap garis lurus dan mendefinisikan setengah bidang yang diberikan oleh pertidaksamaan (setengah bidang ditandai dengan prima). Perpotongan setengah bidang akan menjadi area, koordinat titik-titik yang memenuhi kondisi ketidaksetaraan sistem kendala masalah. Mari kita tunjukkan batas-batas wilayah poligon solusi. Mari kita buat garis lurus yang sesuai dengan nilai fungsi F = 0: F = 2x 1 +3x 2 = 0. Vektor gradien yang terdiri dari koefisien fungsi tujuan menunjukkan arah minimalisasi F(X). Awal dari vektor adalah titik (0; 0), ujungnya adalah titik (2; 3). Mari kita pindahkan garis ini secara paralel. Karena kami tertarik pada solusi minimum, oleh karena itu, kami memindahkan garis lurus sampai sentuhan pertama dari area yang ditentukan. Pada grafik, garis ini ditunjukkan dengan garis putus-putus. Lurus Setelah memecahkan sistem persamaan, kita mendapatkan: x 1 = 3,3333, x 2 = 0. Di mana kita dapat menemukan nilai minimum dari fungsi tujuan: . Pertimbangkan fungsi tujuan dari masalah. Mari kita buat garis lurus yang sesuai dengan nilai fungsi F = 0: F = 2x 1 +3x 2 = 0. Vektor gradien yang terdiri dari koefisien fungsi tujuan menunjukkan arah maksimalisasi F(X). Awal dari vektor adalah titik (0; 0), ujungnya adalah titik (2; 3). Mari kita pindahkan garis ini secara paralel. Karena kami tertarik pada solusi maksimum, kami memindahkan garis lurus hingga sentuhan terakhir dari area yang ditentukan. Pada grafik, garis ini ditunjukkan dengan garis putus-putus. Lurus Di mana kita dapat menemukan nilai maksimum dari fungsi tujuan: . Menjawab: 2
.
Memecahkan masalah pemrograman linier menggunakan metode simpleks: Keputusan Mari kita selesaikan masalah langsung pemrograman linier dengan metode simpleks, menggunakan tabel simpleks. Mari kita tentukan nilai minimum dari fungsi tujuan Untuk menyusun rencana referensi pertama, kami mengurangi sistem pertidaksamaan menjadi sistem persamaan dengan memasukkan variabel tambahan. Dalam ketidaksetaraan makna pertama (≥), kami memperkenalkan variabel dasar x 3
dengan tanda minus. Dalam ketidaksamaan makna ke-2 (≤), kami memperkenalkan variabel dasar x 4
. Dalam pertidaksamaan makna ke-3 (≤), kami memperkenalkan variabel dasar x 5 . Mari kita perkenalkan variabel buatan Untuk menetapkan tugas minimum, kami menulis fungsi tujuan sebagai berikut: . Untuk penggunaan variabel buatan yang dimasukkan ke dalam fungsi tujuan, apa yang disebut penalti M dikenakan, angka positif yang sangat besar, yang biasanya tidak ditentukan. Basis yang dihasilkan disebut artifisial, dan metode penyelesaiannya disebut metode basis buatan. Selain itu, variabel buatan tidak terkait dengan konten tugas, tetapi memungkinkan Anda untuk membangun titik awal, dan proses optimasi memaksa variabel-variabel ini untuk mengambil nilai nol dan memastikan diterimanya solusi optimal. Dari persamaan kami menyatakan variabel buatan: x 6 \u003d 4-x 1 -x 2 +x 3, yang kami substitusikan ke dalam fungsi tujuan: atau. Matriks Koefisien Mari kita selesaikan sistem persamaan sehubungan dengan variabel dasar: x 6
, x 4
, x 5.
Dengan asumsi bahwa variabel bebas adalah 0, kita mendapatkan baseline pertama: X1 = (0,0,0,2,10,4) Sebuah solusi dasar disebut diterima jika non-negatif. x 1
x 2
x 3
x 4
x 5
x 6
x 6
x 4
x 5
Baseline saat ini tidak optimal karena terdapat koefisien positif pada baris indeks. Kami akan memilih kolom yang sesuai dengan variabel x 2 sebagai yang terdepan, karena ini adalah koefisien terbesar. Hitung nilainya D saya Oleh karena itu, baris ke-2 memimpin. Elemen penyelesaian sama dengan (2) dan terletak di persimpangan kolom terdepan dan baris terdepan. x 1
x 2
x 3
x 4
x 5
x 6
x 6
x 4
x 5
Kami membentuk bagian selanjutnya dari tabel simpleks. Alih-alih variabel x 4, variabel x 2 akan masuk ke dalam rencana 1. Garis yang bersesuaian dengan variabel x 2 pada denah 1 diperoleh dengan membagi semua elemen garis x 4 denah 0 dengan elemen pendukung RE=2. Di tempat elemen penyelesaian, kami mendapatkan 1. Di sel yang tersisa dari kolom x 2, kami menulis nol. Jadi, pada denah baru 1 baris x 2 dan kolom x 2 terisi. Semua elemen lain dari rencana 1 baru, termasuk elemen baris indeks, ditentukan oleh aturan persegi panjang. x 1
x 2
x 3
x 4
x 5
x 6
x 6
x 2
x 5
1 1/2 +1 1/2 M Baseline saat ini tidak optimal karena terdapat koefisien positif pada baris indeks. Kami akan memilih kolom yang sesuai dengan variabel x 1 sebagai yang terdepan, karena ini adalah koefisien terbesar. Hitung nilainya D saya dengan baris sebagai hasil bagi pembagian: Oleh karena itu, baris pertama memimpin. Elemen penyelesaian sama dengan (1 1 / 2) dan terletak di persimpangan kolom terdepan dan baris terdepan. x 1
x 2
x 3
x 4
x 5
x 6
x 6
1
1
/
2
x 2
x 5
-1
1
/
2
+1
1
/
2
M Kami membentuk bagian selanjutnya dari tabel simpleks. Alih-alih variabel x 6 , variabel x 1 akan dimasukkan dalam rencana 2. Kami mendapatkan tabel simpleks baru: x 1
x 2
x 3
x 4
x 5
x 6
x 1
x 2
x 5
Tidak ada nilai baris indeks yang positif. Oleh karena itu, tabel ini menentukan rencana tugas yang optimal. Versi terakhir dari tabel simpleks: x 1
x 2
x 3
x 4
x 5
x 6
x 1
x 2
x 5
Karena tidak ada variabel buatan dalam solusi optimal (sama dengan nol), solusi ini layak. Rencana optimal dapat ditulis sebagai berikut: x 1 \u003d 2, x 2 \u003d 2:. Menjawab: 3.
Perusahaan "Tiga Pria Gemuk" bergerak dalam pengiriman daging kaleng dari tiga gudang yang terletak di berbagai bagian kota ke tiga toko. Stok makanan kaleng yang tersedia di gudang, serta volume pesanan dari toko dan tarif pengiriman (dalam unit moneter konvensional) disajikan dalam tabel transportasi. Temukan rencana transportasi yang memberikan biaya tunai paling sedikit (lakukan rencana transportasi awal menggunakan metode "sudut barat laut"). Keputusan Mari kita periksa kondisi perlu dan cukup untuk solvabilitas masalah: Kondisi keseimbangan terpenuhi. Saham sama kebutuhan. Oleh karena itu, model masalah transportasi ditutup. Mari kita masukkan data awal dalam tabel distribusi. Kebutuhan Dengan menggunakan metode sudut barat laut, kita akan membangun rencana dasar pertama dari masalah transportasi. Rencananya mulai diisi dari sudut kiri atas. Elemen yang diinginkan adalah 4. Untuk elemen ini, stoknya 300, kebutuhannya 250. Karena minimal 250, kita kurangi: . 300 - 250 = 50
250 - 250 = 0
Elemen yang diinginkan adalah 2. Untuk elemen ini, stoknya adalah 50, kebutuhannya adalah 400. Karena minimumnya adalah 50, kita kurangi: . 50 - 50 = 0
400 - 50 = 350
Elemen yang diinginkan adalah 5. Untuk elemen ini, stoknya adalah 300, kebutuhannya adalah 350. Karena minimumnya adalah 300, kita kurangi: 300 - 300 = 0
350 - 300 = 50
Elemen yang diinginkan adalah 3. Untuk elemen ini, stoknya adalah 200, kebutuhannya adalah 50. Karena minimumnya adalah 50, kita kurangi: 200 - 50 = 150
50 - 50 = 0
Elemen yang diinginkan adalah 6. Untuk elemen ini, stoknya adalah 150, kebutuhannya adalah 150. Karena minimumnya adalah 150, kita kurangi: 150 - 150 = 0
150 - 150 = 0
Kebutuhan
Dokumen serupa
;
; 
;
; 
.
.
Tugas nomor 2
ó
ó 
Kemudian 
; ; 
- nilai minimum fungsi.
ó 
ó 
ó 
; ; fungsi tujuan maksimum tercapai jika 
; .
Tugas nomor 3
Contoh
Fungsi halus dan sistem persamaan
Pemrograman linier
Optimasi kombinatorial
Bab 1. Pernyataan masalah utama pemrograman linier
Pemrograman linier
(1.2) persyaratan non-negatif
(1.3) dimana x j– variabel (tidak diketahui);
- koefisien dari masalah program linier.1.2. Metode simpleks untuk menyelesaikan masalah program linier
.6.1 Pendahuluan
6.2 Dasar-dasar teori optimasi
X1, x2, x3,...,xn.
Masalah pemrograman linier
, (5.1)
, , (5.2)
, (5.3) , , , (5.5)
. ,
.
Rentang yang dapat diterima
Batas nilai yang diizinkan
Persimpangan dengan sumbu x 1
Persimpangan dengan sumbu x 2
3 * x 1 + 10 * x 2 330
3 * x 1 + 10 * x 2 = 330
x 1 = 110; x 2 = 0
x 1 = 0; x 2 = 33
16 * x 1 + 4 * x 2 400
16 * x 1 + 4 * x 2 = 400
x 1 = 25; x 2 = 0
x 1 = 0; x 2 = 100
6 * x 1 + 6 * x 2 240
6 * x 1 + 6 * x 2 = 240
x 1 = 40; x 2 = 0
x 1 = 0; x 2 = 40
x 2 12
x 2 = 12
tidak menyeberang; berjalan sejajar dengan sumbu x 1
x 1 = 0; x 2 = 12
Dot
Nilai x 1
Nilai x 2
Z \u003d 2500x 1 + 3500x 2
TETAPI
22
12
97 000
PADA
20
20
120 000
Dengan
10
30
130 000
D
0
33
115 500
E
0
12
42 000
,
.
memotong daerah di titik C. Karena titik C diperoleh dari perpotongan garis (4) dan (1), maka koordinatnya memenuhi persamaan garis berikut: 
.
memotong daerah di titik B. Karena titik B diperoleh dari perpotongan garis (2) dan (3), maka koordinatnya memenuhi persamaan garis berikut: 
.
dan 
.
.
di bawah kondisi-pembatasan berikut: 
.
: dalam persamaan pertama kami memperkenalkan variabel x 6
;
sistem persamaan ini memiliki bentuk: 
.
dan pilih yang terkecil dari mereka: min(4: 1 , 2: 2 , 10: 2) = 1.
dan dari mereka kami memilih yang terkecil: min (3: 1 1/2, -, 8: 2) = 2.
,
.
=
300 + 300 + 200 = 800 .
=
250 + 400 + 150 = 800.
