Linear programming

Home » » Linear programming

Pemrograman linier

Dari Wikipedia

Sebuah representasi bergambar dari program linier sederhana dengan dua variabel dan enam ketidaksetaraan. Himpunan solusi layak digambarkan dalam lampu merah dan membentuk polytope 2-dimensi. Fungsi biaya linear diwakili oleh garis merah dan panah: Garis merah adalah seperangkat tingkat fungsi biaya, dan panah menunjukkan arah di mana kita mengoptimalkan.
Linear programming (LP, atau optimasi linier) adalah metode matematika untuk menentukan cara untuk mencapai hasil terbaik (seperti laba maksimum atau biaya terendah) dalam model matematika yang diberikan untuk beberapa daftar persyaratan direpresentasikan sebagai hubungan linear. Pemrograman linier adalah kasus spesifik pemrograman matematika (optimasi matematika).
Lebih formal, program linear adalah teknik untuk optimalisasi fungsi tujuan linear, tergantung pada kesetaraan linear dan kendala pertidaksamaan linear. Daerah layak adalah cembung polyhedron, yang merupakan set didefinisikan sebagai persimpangan finitely banyak setengah spasi, masing-masing didefinisikan oleh pertidaksamaan linear. Fungsi tujuannya adalah fungsi affine bernilai real yang didefinisikan pada polyhedron ini. Sebuah algoritma pemrograman linier menemukan titik di mana polyhedron fungsi ini memiliki terkecil (atau terbesar) nilainya jika titik tersebut ada.
Program linier masalah yang dapat dinyatakan dalam bentuk kanonik:

    
\ Begin {align} & \ text {} memaksimalkan && \ mathbf {c} ^ \ mathrm {T} \ mathbf {x} \ \ & \ text {tunduk} && A \ mathbf {x} \ leq \ mathbf {b } \ \ & \ text {dan} && \ mathbf {x} \ ge \ mathbf {0} \ end {align}
dimana x merupakan vektor variabel (akan ditentukan), c dan b adalah vektor (dikenal) koefisien, A adalah (diketahui) matriks koefisien, dan (\ cdots) ^ \ mathrm {T} adalah transpos matriks. Ekspresi dimaksimalkan atau diminimalkan disebut fungsi tujuan (CTX dalam kasus ini). Ketidaksamaan Ax ≤ b adalah kendala yang menentukan polytope cembung dimana fungsi tujuan yang akan dioptimalkan. Dalam konteks ini, dua vektor sebanding ketika mereka memiliki dimensi yang sama. Jika setiap entri dalam pertama adalah kurang atau sama-dengan entri yang sesuai di kedua maka kita dapat mengatakan vektor pertama kurang-dari atau sama-dengan vektor kedua.
Pemrograman linier dapat diterapkan pada berbagai bidang studi. Hal ini digunakan dalam bisnis dan ekonomi, tetapi juga dapat dimanfaatkan untuk beberapa masalah teknik. Industri yang menggunakan model pemrograman linier meliputi transportasi, energi, telekomunikasi, dan manufaktur. Ini telah terbukti berguna dalam pemodelan beragam jenis masalah dalam perencanaan, routing, penjadwalan, penugasan, dan desain.

Isi

    
1 Sejarah
    
2 Penggunaan
    
3 bentuk standar
        
3.1 Contoh
    
4 Augmented bentuk (bentuk kendur)
        
4.1 Contoh
    
5 Duality
        
5.1 Contoh
        
5.2 Contoh lain
    
6 Meliputi-kemasan dualitas
        
6.1 Contoh
    
7 Pelengkap kelambanan
    
8 Teori
        
8.1 Keberadaan solusi optimal
        
8,2 simpul Optimal (dan sinar) polyhedra
    
9 Algoritma
        
9,1 algoritma pertukaran Dasar
            
9.1.1 Algoritma Simplex Dantzig
            
9.1.2 Algoritma Criss-lintas
            
9.1.3 Algoritma sampel Conic Serang
        
9.2 Titik Interior
            
9.2.1 algoritma ellipsoid, berikut Khachiyan
            
9.2.2 Algoritma proyektif dari Karmarkar
            
9.2.3 algoritma Jalur-berikut
        
9.3 Perbandingan metode interior-point dibandingkan algoritma simpleks
    
10 masalah Terbuka dan karya terbaru
    
11 diketahui Integer
    
12 program linier Integral
    
13 Solvers dan scripting (pemrograman) bahasa
    
14 Lihat juga
    
15 Catatan
    
16 Referensi
    
17 Bacaan lebih lanjut
    
18 Pranala luar
SejarahLeonid Kantorovich
Masalah memecahkan sistem linear kesenjangan tanggal kembali setidaknya sejauh Fourier, setelah siapa metode eliminasi Fourier-Motzkin bernama. Linier programming pertama kali dikembangkan oleh Leonid Kantorovich pada tahun 1939. [1] Leonid Kantorovich dikembangkan awal masalah pemrograman linear pada tahun 1939 untuk digunakan selama Perang Dunia II untuk merencanakan pengeluaran dan kembali dalam rangka untuk mengurangi biaya untuk tentara dan meningkatkan kerugian pada musuh . Metode ini dirahasiakan sampai tahun 1947 ketika George B. Dantzig menerbitkan metode simpleks dan John von Neumann mengembangkan teori dualitas sebagai solusi optimasi linear, dan menerapkannya dalam bidang teori permainan. Pascaperang, banyak industri yang ditemukan penggunaannya dalam perencanaan sehari-hari mereka.
Masalah linear-programming pertama terbukti dipecahkan dalam waktu polinomial oleh Leonid Khachiyan pada tahun 1979, namun terobosan teoritis dan praktis yang lebih besar di lapangan datang pada tahun 1984 ketika Narendra Karmarkar memperkenalkan metode interior-point baru untuk memecahkan masalah linear-programming.
Contoh asli Dantzig adalah untuk menemukan tugas terbaik dari 70 orang untuk 70 pekerjaan. Kekuatan komputasi yang dibutuhkan untuk menguji semua permutasi untuk memilih tugas yang terbaik adalah luas, jumlah konfigurasi yang mungkin melebihi jumlah partikel di alam semesta teramati. Namun, dibutuhkan hanya sesaat untuk menemukan solusi optimum dengan mengajukan masalah sebagai program linier dan menerapkan algoritma simpleks. Teori di balik program linier secara drastis mengurangi jumlah solusi optimal kemungkinan yang harus diperiksa.Menggunakan
Linear programming adalah bidang yang cukup optimasi karena beberapa alasan. Banyak masalah praktis dalam riset operasi dapat dinyatakan sebagai masalah pemrograman linear. Kasus khusus tertentu pemrograman linear, seperti masalah aliran jaringan dan masalah aliran Multicommodity dianggap cukup penting telah menghasilkan banyak penelitian pada algoritma khusus untuk solusi mereka. Sejumlah algoritma untuk jenis lain masalah optimasi bekerja dengan memecahkan masalah LP sebagai sub-masalah. Secara historis, ide dari program linear telah menginspirasi banyak konsep utama teori optimasi, seperti dualitas, dekomposisi, dan pentingnya kecembungan dan generalisasi. Demikian juga, program linier banyak digunakan dalam ekonomi mikro dan manajemen perusahaan, seperti perencanaan, produksi, transportasi, teknologi dan isu-isu lainnya. Meskipun isu-isu manajemen modern selalu berubah, sebagian besar perusahaan ingin memaksimalkan keuntungan atau meminimalkan biaya dengan sumber daya terbatas. Oleh karena itu, banyak masalah dapat dicirikan sebagai masalah pemrograman linear.Bentuk standar
Bentuk standar adalah bentuk biasa dan paling intuitif menggambarkan masalah program linier. Ini terdiri dari tiga bagian berikut:

    
Sebuah fungsi linear untuk dimaksimalkan

    
misalnya f (x_ {1}, x_ {2}) = c_1 x_1 + x_2 c_2

    
Kendala masalah bentuk berikut

    
misalnya

        
\ Begin {matrix} a_ {11} x_1 + a_ {12} x_2 & \ leq b_1 \ \ a_ {21} x_1 + a_ {22} x_2 & \ leq b_2 \ \ a_ {31} x_1 + a_ {32} x_2 & \ leq b_3 \ \ \ end {matrix}

    
Variabel non-negatif

    
misalnya

        
\ Begin {matrix} x_1 \ geq 0 \ \ x_2 \ geq 0 \ end {matrix}
Masalahnya biasanya dinyatakan dalam bentuk matriks, dan kemudian menjadi:

    
\ Max \ {c ^ \ mathrm {T} x \, | \; A x \ leq b \ dan x \ geq 0 \}
Bentuk lain, seperti masalah minimalisasi, masalah dengan kendala pada bentuk-bentuk alternatif, serta masalah yang melibatkan variabel negatif selalu dapat ditulis ulang menjadi masalah setara dalam bentuk standar.Contoh
Misalkan seorang petani memiliki sebidang tanah pertanian, katakanlah L km2, yang akan ditanami gandum atau barley baik atau beberapa kombinasi dari keduanya. Petani memiliki jumlah terbatas pupuk, kilogram F, dan insektisida, P kilogram. Setiap kilometer persegi gandum membutuhkan kilogram F1 pupuk, dan kilogram P1 insektisida, sementara setiap kilometer persegi jelai membutuhkan kilogram F2 pupuk, dan P2 kilogram insektisida. Biarkan S1 menjadi harga jual gandum per kilometer persegi, dan S2 menjadi harga jelai. Jika kita menunjukkan luas lahan yang ditanami gandum dan jelai oleh x1 dan x2 masing-masing, maka keuntungan dapat dimaksimalkan dengan memilih nilai optimal untuk x1 dan x2. Masalah ini dapat dinyatakan dengan masalah program linier berikut dalam bentuk standar:Maksimalkan: S1x1 + S2x2 (memaksimalkan pendapatan-pendapatan adalah "fungsi tujuan")Tunduk: 0 ≤ x1 + x2 ≤ L (batas luas total)0 ≤ F1x1 + F2x2 ≤ F (batas pupuk)0 ≤ P1x1 + P2x2 ≤ P (batas insektisida)x1 ≥ 0, x2 ≥ 0 (tidak bisa menanam area negatif).
Yang dalam bentuk matriks menjadi:

    
memaksimalkan \ begin {bmatrix} S_1 & S_2 \ end {bmatrix} \ begin {bmatrix} x_1 \ \ x_2 \ end {bmatrix}
    
tunduk \ begin {bmatrix} 0 \ \ 0 \ \ 0 \ end {bmatrix} \ le \ begin {bmatrix} 1 & 1 \ \ F_1 & F_2 \ \ P_1 & P_2 \ end {bmatrix} \ begin {bmatrix} x_1 \ \ x_2 \ end {bmatrix} \ le \ begin {bmatrix} L \ \ F \ \ P \ end {bmatrix}, \, \ begin {bmatrix} x_1 \ \ x_2 \ end {bmatrix} \ ge \ begin {bmatrix } 0 \ \ 0 \ end {bmatrix}.
Augmented bentuk (bentuk kendur)
Masalah pemrograman linier harus dikonversi ke dalam bentuk augmented sebelum dipecahkan oleh algoritma simpleks. Formulir ini memperkenalkan variabel slack non-negatif untuk menggantikan kesenjangan dengan kesetaraan dalam kendala. Masalahnya kemudian dapat ditulis dalam bentuk matriks blok berikut:

    
Maksimalkan Z:
    
\ Begin {bmatrix} 1 & - \ mathbf {c} ^ T & 0 \ \ 0 & \ mathbf {A} & \ mathbf {I} \ end {bmatrix} \ begin {bmatrix} Z \ \ \ mathbf {x} \ \ \ mathbf {x} _s \ end {bmatrix} = \ begin {bmatrix} 0 \ \ \ mathbf {b} \ end {bmatrix}
    
x, xs ≥ 0
mana xs adalah variabel slack baru diperkenalkan, dan Z adalah variabel yang akan dimaksimalkan.Contoh
Contoh di atas diubah menjadi bentuk augmented berikut:Maksimalkan: S1x1 + S2x2 (fungsi tujuan)Sesuai dengan: x1 + x2 + x3 = L (augmented kendala)F1x1 + + x4 = F2x2 F (augmented kendala)P1x1 + P2x2 + x5 = P (augmented kendala)x1, x2, x3, x4, x5 ≥ 0.
mana x3, x4, x5 adalah (non-negatif) variabel slack, mewakili dalam contoh ini area yang tidak terpakai, jumlah pupuk yang tidak terpakai, dan jumlah insektisida yang tidak terpakai.
Dalam bentuk matriks ini menjadi:

    
Maksimalkan Z:
    
\ Begin {bmatrix} 1 &-S_1 &-S_2 & 0 & 0 & 0 \ \ 0 & 1 & 1 & 1 & 0 & 0 \ \ 0 & F_1 & F_2 & 0 & 1 & 0 \ \ 0 & P_1 & P_2 & 0 & 0 & 1 \ \ \ end {bmatrix} \ begin {bmatrix} Z \ \ x_1 \ \ x_2 \ \ x_3 \ \ x_4 \ \ x_5 \ end {bmatrix} = \ begin {bmatrix} 0 \ \ L \ \ F \ \ P \ end {bmatrix}, \, \ begin {bmatrix} x_1 \ \ x_2 \ \ x_3 \ \ x_4 \ \ x_5 \ end {bmatrix} \ ge 0.
DualityArtikel utama: Duality (optimasi)
Setiap masalah pemrograman linear, disebut sebagai masalah primal, dapat diubah menjadi masalah ganda, yang memberikan batas atas untuk nilai optimal dari masalah primal. Dalam bentuk matriks, kita dapat mengekspresikan masalah primal sebagai:

    
Maksimalkan tunduk CTX ke Ax ≤ b, x ≥ 0;

        
dengan masalah ganda yang sesuai simetris,

    
Minimalkan tunduk BTY ke Aty ≥ c, y ≥ 0.
Formulasi primal alternatif adalah:

    
Maksimalkan tunduk CTX ke Ax ≤ b;

        
dengan masalah ganda yang sesuai asimetris,

    
Minimalkan tunduk BTY ke Aty = c, y ≥ 0.
Ada dua ide dasar teori dualitas. Salah satunya adalah fakta bahwa (untuk simetris ganda) dual dari program linier dual program linier primal asli. Selain itu, setiap solusi yang layak untuk program linier memberikan terikat pada nilai optimal dari fungsi tujuan gandanya. Lemahnya dualitas Teorema menyatakan bahwa nilai fungsi tujuan dari ganda pada setiap solusi layak selalu lebih besar dari atau sama dengan nilai fungsi objektif dari primal setiap solusi yang layak. Yang kuat Dualitas Teorema menyatakan bahwa jika primal memiliki solusi optimal, x *, maka ganda juga memiliki solusi optimal, y *, seperti CTX yang * = Bty *.
Sebuah program linier juga bisa tak terbatas atau tidak layak. Teori dualitas memberitahu kita bahwa jika primal tak terbatas maka ganda menjadi tidak layak secara teorema dualitas lemah. Demikian juga, jika ganda yang tak terbatas, maka primal harus layak. Namun, adalah mungkin untuk kedua ganda dan primal menjadi tidak layak (Lihat juga Farkas 'lemma).Contoh
Kembali contoh di atas dari petani yang dapat menanam gandum dan barley dengan penyediaan set beberapa tanah L, F dan pupuk P insektisida. Asumsikan sekarang bahwa harga satuan untuk masing-masing alat produksi (input) yang ditetapkan oleh dewan perencanaan. Pekerjaan Perencanaan board adalah untuk meminimalkan total biaya pengadaan jumlah set input sambil memberikan petani dengan lantai pada harga satuan dari masing-masing tanaman nya (output), S1 dan S2 untuk gandum untuk jelai. Hal ini sesuai dengan masalah pemrograman linear berikut:Minimalkan: LyL + + FyF PYP (meminimalkan total biaya alat-alat produksi sebagai "fungsi tujuan")Sesuai dengan: YL + + F1yF P1yP ≥ S1 (petani harus menerima tidak kurang dari S1 untuk gandum-Nya)YL + YF F2 + P2yP ≥ S2 (petani harus menerima tidak kurang dari S2 untuk jelai nya)YL ≥ 0, YF ≥ 0, YP ≥ 0 (harga tidak dapat negatif).
Yang dalam bentuk matriks menjadi:

    
Minimalkan: \ begin {bmatrix} L & F & P \ end {bmatrix} \ begin {bmatrix} y_L \ \ y_F \ \ y_P \ end {bmatrix}
    
Sesuai dengan: \ begin {bmatrix} 1 & F_1 & P_1 \ \ 1 & F_2 & P_2 \ end {bmatrix} \ begin {bmatrix} y_L \ \ y_F \ \ y_P \ end {bmatrix} \ ge \ begin {bmatrix} S_1 \ \ S_2 \ end {bmatrix}, \, \ begin {bmatrix} y_L \ \ y_F \ \ y_P \ end {bmatrix} \ ge 0.
Masalah transaksi primal dengan besaran fisika. Dengan semua input tersedia dalam jumlah terbatas, dan dengan asumsi harga satuan semua output yang diketahui, apa kuantitas output untuk menghasilkan untuk memaksimalkan total pendapatan? Masalah transaksi ganda dengan nilai-nilai ekonomi. Dengan jaminan lantai pada semua harga satuan output, dan dengan asumsi jumlah yang tersedia dari semua input yang diketahui, apa masukan Unit skema harga untuk mengatur sehingga dapat meminimalkan total belanja?
Untuk setiap variabel dalam ruang primal sesuai sebuah pertidaksamaan untuk memuaskan dalam ruang ganda, baik diindeks oleh jenis output. Untuk setiap ketidaksetaraan untuk memuaskan dalam ruang primal sesuai variabel dalam ruang ganda, baik diindeks oleh jenis input.
Koefisien yang mengikat ketidaksetaraan dalam ruang utama yang digunakan untuk menghitung tujuan dalam ruang ganda, jumlah masukan dalam contoh ini. Koefisien yang digunakan untuk menghitung tujuan dalam ruang primal terikat ketidaksetaraan dalam ruang ganda, harga satuan output dalam contoh ini.
Baik primal dan masalah ganda menggunakan matriks yang sama. Dalam ruang primal, matriks ini mengungkapkan konsumsi jumlah fisik input yang diperlukan untuk menghasilkan satu set kuantitas output. Dalam ruang ganda, itu mengungkapkan penciptaan nilai ekonomi yang dihubungkan dengan output dari set harga satuan input.
Karena setiap ketimpangan dapat digantikan oleh kesetaraan dan variabel slack, ini berarti setiap variabel primal sesuai dengan variabel ganda kendur, dan masing-masing variabel ganda sesuai dengan variabel slack primal. Hubungan ini memungkinkan kita untuk berbicara tentang kelambanan komplementer.Contoh lain
Kadang-kadang, mungkin akan terasa lebih intuitif untuk mendapatkan program dual tanpa melihat matriks program tersebut. Pertimbangkan program linier berikut:meminimalkan \ sum_ {i = 1} ^ {m c_i x_i} + \ sum_ {j = 1} ^ {n d_j t_j}tunduk \ sum_ {i = 1} ^ m {a_ {ij}} + x_i e_j t_j \ ge g_j, 1 \ le j \ le nf_i x_i + \ sum_ {j = 1} ^ {n b_ {ij}} t_j \ ge h_i, 1 \ le i \ le mx_i \ ge 0, \, t_j \ ge 0, 1 \ le i \ le m, 1 \ le j \ le n
Kami memiliki kondisi m + n dan semua variabel non-negatif. Kita akan mendefinisikan m + n variabel ganda: yj dan si. Kami mendapatkan:meminimalkan \ sum_ {i = 1} ^ {m c_i x_i} + \ sum_ {j = 1} ^ {n d_j t_j}tunduk \ sum_ {i = 1} ^ m {a_ {ij}} x_i \ cdots y_j + e_j t_j \ cdots y_j \ ge g_j \ cdots y_j, 1 \ le j \ le nf_i x_i \ cdots s_i + \ sum_ {j = 1} ^ {n b_ {ij}} t_j \ cdots s_i \ ge h_i \ cdots s_i, 1 \ le i \ le mx_i \ ge 0, \, t_j \ ge 0, 1 \ le i \ le m, 1 \ le j \ le ny_j \ ge 0, \, s_i \ ge 0, 1 \ le j \ le n, 1 \ le i \ le m
Karena ini adalah masalah minimisasi, kami ingin memperoleh program ganda yang merupakan batas bawah dari primal. Dengan kata lain, kami ingin jumlah semua sisi kanan dari kendala menjadi maksimal di bawah kondisi bahwa untuk setiap variabel primal jumlah koefisien yang tidak melebihi koefisien dalam fungsi linear. Misalnya, x1 muncul dalam n + 1 kendala. Jika kita menjumlahkan koefisien kendala 'kita mendapatkan a1, 1Y1 + a1, 2y2 + ... + A1, nyn + f1s1. Jumlah ini harus paling c1. Akibatnya kita mendapatkan:memaksimalkan \ sum_ {j = 1} ^ {n} + g_j y_j \ sum_ {i = 1} ^ {m h_i s_i}tunduk \ sum_ {j = 1} ^ {n a_ {ij}} + y_j f_i s_i \ le c_i, 1 \ le i \ le me_j y_j + \ sum_ {i = 1} ^ {m b_ {ij}} s_i \ le d_j, 1 \ le j \ le ny_j \ ge 0, \, s_i \ ge 0, 1 \ le j \ le n, 1 \ le i \ le m
Perhatikan bahwa kita asumsikan dalam langkah perhitungan kami bahwa program ini dalam bentuk standar. Namun, setiap program linier dapat ditransformasikan ke dalam bentuk standar dan oleh karena itu bukan merupakan faktor pembatas.Meliputi-packing dualitasMeliputi-packing dualitasMasalah meliputi masalah PackingMinimum cover set Maksimum set kemasanMinimum penutup pencocokan maksimum vertexMinimum tepi penutup Maksimum set independen
Sebuah LP meliputi adalah program linier dalam bentuk:

    
Minimalkan: BTY,
    
Sesuai dengan: Aty ≥ c, y ≥ 0,
sehingga matriks A dan vektor b dan c adalah non-negatif.
Ganda dari LP meliputi adalah LP kemasan, program linear dalam bentuk:

    
Maksimalkan: CTX,
    
Sesuai dengan: Ax ≤ b, x ≥ 0,
sehingga matriks A dan vektor b dan c adalah non-negatif.Contoh
Menutupi dan kemasan piringan hitam biasa muncul sebagai relaksasi program linier dari masalah kombinatorial dan penting dalam studi algoritma perkiraan. [2] Sebagai contoh, relaksasi LP dari masalah kemasan mengatur, masalah set independen, dan masalah pencocokan yang kemasan piringan hitam. LP relaksasi dari masalah cover set, masalah penutup vertex, dan masalah set mendominasi juga mencakup piringan hitam.
Mencari pewarna pecahan dari suatu graf adalah contoh lain dari LP menutupi. Dalam kasus ini, ada satu kendala untuk setiap titik dari grafik dan satu variabel untuk setiap set independen grafik.Kelambanan Pelengkap
Hal ini dimungkinkan untuk memperoleh solusi optimal untuk ganda ketika hanya solusi optimal untuk primal dikenal menggunakan teorema kelambanan komplementer. Teorema menyatakan:
Misalkan x = (x1, x2, ..., xn) adalah primal layak dan bahwa y = (y1, y2, ..., ym) dual layak. Biarkan (w1, w2, ..., wm) menunjukkan variabel slack primal yang sesuai, dan biarkan (z1, z2, ..., zn) menunjukkan variabel slack ganda yang sesuai. Maka x dan y adalah optimal untuk masalah masing-masing jika dan hanya jika

    
XJ zj = 0, untuk j = 1, 2, ... , N, dan
    
wi yi = 0, untuk i = 1, 2, ... , M.
Jadi jika variabel slack-i dari primal tidak nol, maka variabel-i dual adalah sama dengan nol. Demikian juga, jika variabel slack j dual ini tidak nol, maka variabel j-th primal sama dengan nol.
Ini kondisi yang diperlukan untuk optimalitas menyampaikan prinsip ekonomi cukup sederhana. Dalam bentuk standar (ketika memaksimalkan), jika ada slack dalam suatu sumber daya primal terbatas (misalnya, ada "sisa"), maka jumlah tambahan sumber daya yang harus memiliki nilai. Demikian juga, jika ada slack di ganda (bayangan) harga non-negatif kendala persyaratan, yaitu, harga tidak nol, maka harus ada pasokan langka (ada "sisa").TeoriAdanya solusi optimal
Geometris, kendala linier menentukan daerah feasible, yang merupakan cembung polyhedron. Sebuah fungsi linear adalah fungsi cembung, yang berarti bahwa setiap minimum lokal adalah minimum global, sama, fungsi linear adalah fungsi cekung, yang berarti bahwa setiap maksimum lokal adalah maksimum global.
Solusi optimal tidak perlu ada, karena dua alasan. Pertama, jika dua kendala tidak konsisten, maka tidak ada solusi yang layak ada: Misalnya, kendala x ≥ 2 dan x ≤ 1 tidak dapat dipenuhi bersama-sama, dalam hal ini, kita mengatakan bahwa LP adalah tidak layak. Kedua, ketika polytope yang tak terbatas dalam arah gradien dari fungsi tujuan (di mana gradien dari fungsi tujuan adalah vektor koefisien fungsi tujuan), maka tidak ada nilai yang optimal dicapai.Simpul yang optimal (dan sinar) polyhedra
Jika tidak, jika solusi yang layak ada dan jika (linear) fungsi tujuan dibatasi, maka nilai optimum selalu dicapai pada batas optimal tingkat-set, dengan prinsip maksimum untuk fungsi cembung (alternatif, dengan prinsip minimum untuk cekung fungsi): Ingatlah bahwa fungsi linear keduanya cembung dan cekung. Namun, beberapa masalah memiliki solusi optimal yang berbeda: Misalnya, masalah menemukan solusi yang layak untuk sebuah sistem linear kesenjangan merupakan masalah pemrograman linear di mana fungsi tujuan adalah fungsi nol (yaitu, fungsi konstan mengambil nilai nol mana-mana): Untuk masalah ini kelayakan dengan nol-fungsi untuk nya tujuan-fungsi, jika ada dua solusi yang berbeda, maka setiap kombinasi cembung solusi adalah solusi.
Simpul dari polytope yang juga disebut solusi dasar layak. Alasan untuk pilihan nama ini adalah sebagai berikut. Biarkan d menunjukkan jumlah variabel. Kemudian teorema dasar linear kesenjangan menyiratkan (untuk masalah layak) bahwa untuk setiap x titik * dari daerah feasible LP, terdapat satu set d (atau kurang) kendala ketimpangan dari LP seperti itu, ketika kita memperlakukan orang-orang d kendala sebagai persamaan, solusi yang unik adalah x *. Dengan demikian kita bisa mempelajari simpul tersebut dengan cara melihat subset tertentu dari himpunan semua kendala (satu set diskrit), daripada kontinum solusi LP. Prinsip ini mendasari algoritma simpleks untuk menyelesaikan program linier.AlgoritmaSerangkaian kendala linear pada dua variabel menghasilkan wilayah nilai yang mungkin untuk variabel tersebut. Masalah dipecahkan akan memiliki daerah layak dalam bentuk poligon sederhana.Algoritma pertukaran DasarAlgoritma Simplex Dantzig
The simplex algoritma, dikembangkan oleh George Dantzig pada tahun 1947, memecahkan masalah LP dengan membangun solusi yang layak di sebuah sudut dari polytope dan kemudian berjalan sepanjang jalan di tepi polytope untuk simpul dengan nilai-nilai non-penurunan fungsi tujuan sampai suatu optimum tercapai pasti. Dalam banyak masalah praktis, "mengulur" terjadi: Banyak pivots dibuat dengan tidak ada peningkatan dalam fungsi tujuan [3] [4] Dalam masalah-masalah praktis yang langka, versi biasa dari algoritma simpleks dapat benar-benar "siklus" [4] Untuk.. menghindari siklus, peneliti mengembangkan aturan baru berputar. [5] [6] [3] [4] [7] [8]
Dalam prakteknya, algoritma simpleks cukup efisien dan dapat dijamin untuk menemukan optimum global jika tindakan pencegahan tertentu terhadap bersepeda diambil. Algoritma simpleks telah terbukti untuk memecahkan "acak" masalah efisien, yaitu di sejumlah kubik langkah, [9] yang mirip dengan perilaku pada masalah-masalah praktis. [3] [10]
Namun, algoritma simpleks memiliki perilaku terburuk miskin: Klee dan Minty dibangun keluarga masalah pemrograman linier yang metode simpleks mengambil sejumlah langkah eksponensial dalam masalah ukuran [3] [6] [7] Bahkan,. untuk beberapa waktu itu tidak diketahui apakah masalah pemrograman linear adalah dipecahkan dalam waktu polinomial, yaitu kompleksitas kelas P.Algoritma silang
Seperti algoritma simpleks dari Dantzig, algoritma silang adalah algoritma dasar pertukaran yang berporos antara dasar. Namun, algoritma silang tidak perlu mempertahankan kelayakan, namun bisa pivot bukan dari dasar layak untuk secara layak. The berselang-seling algoritma tidak memiliki polinomial waktu kompleksitas untuk pemrograman linear. Kedua algoritma mengunjungi semua sudut 2D dari kubus (terganggu) dalam dimensi D, kubus Klee-Minty, dalam kasus terburuk. [8] [11]Algoritma pengambilan sampel kerucut Serang
Seperti algoritma dasar lainnya-tukar, Serang yang kerucut sampel algoritma bergerak antara simpul, tetapi di mana simplex algoritma bergerak sepanjang tepi dengan menghapus dan menambahkan satu basis pada suatu waktu, bursa metode pengambilan sampel kerucut beberapa basis pada suatu waktu, dan tidak terbatas pada bergerak di sepanjang tepi polytope tersebut [12] Mulai dari simpul saat ini, metode pengambilan sampel kerucut memilih vektor acak yang meningkatkan nilai obyektif tanpa melanggar kendala yang berdekatan.. Algoritma kemudian perjalanan sepanjang vektor ini sampai kendala membatasi ditemui. Dari titik ini, algoritma memproyeksikan vektor ortogonal tujuan ini kendala membatasi, dan bergerak sepanjang proyeksi orthogonal ini sampai kendala baru tercapai. Ini kemajuan dan proyeksi diulang sampai titik tercapai. Kemudian, vektor acak yang baru dipilih. Proses ini diulang sampai tidak ada vektor ada yang dapat meningkatkan tujuan tanpa melanggar kendala lokal, menyiratkan optimalitas. Pada dasarnya, metode pengambilan sampel kerucut dapat dianggap sebagai metode sampling titik yang acak sampel dari koleksi simpul dengan peningkatan nilai obyektif. Jika simpul dengan nilai obyektif superior sampel dengan cara yang kasar seragam, maka runtime yang diharapkan adalah logaritmik dalam jumlah simpul (dan dengan demikian polinomial). Sampling simpul dengan cara ini dapat mengizinkan besar, melompat menguntungkan melalui interior, dan menghasilkan improvent runtime substansial atas metode simpleks, terutama ketika sejumlah kendala, sehingga jumlah simpul potensial, besar, namun ketat yang ada Batas atas kompleksitas kasus terburuk dari metode pengambilan sampel kerucut masih eksponensial.Titik InteriorAlgoritma ellipsoid, mengikuti Khachiyan
Ini adalah pertama terburuk algoritma polinomial-waktu untuk pemrograman linear. Untuk memecahkan masalah yang memiliki n variabel dan dapat dikodekan dalam L masukan bit, algoritma ini menggunakan (N4L) operasi aritmatika pseudo-O pada angka dengan O (L) digit. Algoritma Khachiyan dan masalah berdiri terlalu lama diselesaikan oleh Leonid Khachiyan pada tahun 1979 dengan diperkenalkannya metode ellipsoid. Analisis konvergensi memiliki (real-number) pendahulunya, terutama berulang metode yang dikembangkan oleh Naum Z. Shor dan algoritma pendekatan oleh Arkadi Nemirovski dan D. Yudin.Algoritma proyektif Karmarkar
Algoritma Khachiyan adalah tengara penting untuk menetapkan solvabilitas polinomial-waktu program linier. Algoritma bukanlah komputasi terobosan, sebagai metode simpleks lebih efisien untuk semua tapi keluarga dibangun khusus dari program linear.
Namun, algoritma Khachiyan terinspirasi garis baru penelitian dalam pemrograman linear. Pada tahun 1984, N. Karmarkar mengusulkan metode proyektif untuk pemrograman linear. Algoritma Karmarkar membaik pada Khachiyan yang terburuk polinomial terikat (memberikan O (n ^ {3,5} L)). Karmarkar mengklaim bahwa algoritma nya jauh lebih cepat di LP praktis daripada metode simpleks, sebuah klaim yang menciptakan minat yang besar dalam metode interior-point. [13]Algoritma Path-berikut
Berbeda dengan algoritma simpleks, yang menemukan solusi optimal dengan melintasi tepi antara simpul pada set polihedral, metode interior-point bergerak melalui bagian dalam daerah feasible. Sejak itu, banyak metode interior-point telah diusulkan dan dianalisis. Implementasi sukses awal didasarkan pada varian skala affine metode ini. Untuk tujuan baik teoritis dan praktis, metode fungsi barrier atau jalan-berikut telah menjadi yang paling populer sejak tahun 1990-an. [14]Perbandingan metode interior-point dibandingkan algoritma simpleks
Pendapat saat ini adalah bahwa efisiensi implementasi yang baik dari metode berbasis simpleks dan metode titik interior serupa untuk aplikasi rutin pemrograman linear. [14] Namun, untuk jenis tertentu masalah LP, sangat mungkin bahwa salah satu jenis solver yang lebih baik dari yang lain (kadang-kadang lebih baik).
Pemecah LP digunakan secara luas untuk optimasi dari berbagai masalah dalam industri, seperti optimasi aliran dalam jaringan transportasi. [15]Masalah terbuka dan karya terbaruDaftar masalah yang belum terpecahkan dalam ilmu komputer Apakah program linear mengakui algoritma kuat polinomial-waktu?
Ada beberapa masalah terbuka di teori pemrograman linier, solusi yang akan mewakili terobosan mendasar dalam matematika dan kemajuan yang berpotensi besar dalam kemampuan kita untuk menyelesaikan program linier skala besar.

    
Apakah LP mengakui algoritma kuat polinomial-waktu?
    
Apakah LP mengakui algoritma polinomial kuat untuk menemukan solusi ketat melengkapi?
    
Apakah LP mengakui algoritma polinomial dalam jumlah riil (unit cost) model komputasi?
Ini set terkait erat masalah telah dikutip oleh Stephen Smale sebagai salah satu masalah yang belum terpecahkan 18 terbesar abad ke-21. Dengan kata Smale, versi ketiga dari masalah "adalah masalah yang belum terpecahkan utama teori linear programming." Sementara algoritma yang ada untuk menyelesaikan program linear dalam waktu polinomial lemah, seperti metode ellipsoid dan teknik interior-point, tidak ada algoritma belum ditemukan yang memungkinkan kinerja kuat polinomial-waktu dalam jumlah kendala dan jumlah variabel. Pengembangan algoritma tersebut akan menarik teoritis yang besar, dan mungkin memungkinkan keuntungan praktis dalam memecahkan piringan hitam besar juga.
Meskipun dugaan Hirsch baru-baru ini dibantah untuk dimensi yang lebih tinggi, ini masih menyisakan pertanyaan-pertanyaan berikut terbuka.

    
Apakah ada aturan poros yang menyebabkan varian Simplex polinomial-waktu?
    
Apakah semua grafik polytopal telah polynomially dibatasi diameter?
Pertanyaan-pertanyaan ini berhubungan dengan analisis kinerja dan pengembangan metode Simplex-seperti. Efisiensi besar dari algoritma Simplex dalam praktek meskipun kinerja teoritis eksponensial-waktu mengisyaratkan bahwa mungkin ada variasi Simplex yang bergerak dalam polinomial atau bahkan sangat polinomial waktu. Ini akan menjadi signifikansi praktis dan teoritis besar untuk mengetahui apakah varian tersebut ada, terutama sebagai pendekatan untuk memutuskan apakah LP dapat diselesaikan dalam waktu sangat polinomial.
Simplex algoritma dan variannya jatuh dalam keluarga algoritma tepi-berikut, dinamakan demikian karena mereka memecahkan masalah pemrograman linear dengan bergerak dari titik ke titik di sepanjang tepi polytope a. Ini berarti bahwa kinerja teoretis mereka dibatasi oleh jumlah maksimum dari ujung antara dua simpul pada polytope LP. Sebagai hasilnya, kami tertarik untuk mengetahui diameter grafik-grafik teoritis maksimum polytopal. Hal ini telah dibuktikan bahwa semua polytopes berdiameter subexponential. The pembantahan terbaru dari dugaan Hirsch adalah langkah pertama untuk membuktikan apakah polytope pun memiliki diameter superpolynomial. Jika ada polytopes seperti itu ada, maka tidak ada varian tepi-berikut dapat berjalan dalam waktu polinomial. Pertanyaan tentang diameter polytope yang menarik matematika independen.
Metode poros Simplex melestarikan primal (atau dual) kelayakan. Di sisi lain, metode silang poros tidak mempertahankan (primal atau ganda) kelayakan-mereka dapat mengunjungi primal layak, dual layak atau primal-dan-ganda basis tidak layak dalam urutan apapun. Metode Pivot jenis ini telah diteliti sejak tahun 1970-an. Pada dasarnya, metode ini berusaha untuk menemukan jalan poros terpendek di polytope pengaturan di bawah masalah pemrograman linier. Berbeda dengan grafik polytopal, grafik polytopes pengaturan diketahui memiliki diameter kecil, sehingga kemungkinan algoritma poros kuat polinomial-waktu berselang-seling tanpa memecahkan pertanyaan tentang diameter polytopes umum. [8]Diketahui Integer
Jika semua variabel yang tidak diketahui dituntut untuk bilangan bulat, maka masalah ini disebut integer programming (IP) atau bilangan bulat linier programming (ILP) masalah. Berbeda dengan program linear, yang dapat diselesaikan secara efisien dalam kasus terburuk, masalah integer programming dalam banyak situasi praktis (orang-orang dengan variabel dibatasi) NP-keras. 0-1 pemrograman integer atau program integer biner (BIP) merupakan kasus khusus dari integer programming dimana variabel yang diperlukan untuk menjadi 0 atau 1 (bukan bilangan bulat sewenang-wenang). Masalah ini juga diklasifikasikan sebagai NP-keras, dan bahkan versi keputusan adalah salah satu dari 21 masalah NP-lengkap Karp itu.
Jika hanya beberapa variabel yang tidak diketahui dituntut untuk bilangan bulat, maka masalah ini disebut program integer campuran (MIP) masalah. Biasanya ini juga NP-keras karena mereka bahkan lebih umum dari program ILP.
Namun ada beberapa subclass penting IP dan MIP masalah yang efisien dipecahkan, terutama masalah di mana kendala matriks benar-benar unimodular dan sisi kanan kendala adalah bilangan bulat atau - lebih umum - di mana sistem memiliki total ganda integralistik (TDI) properti.
Algoritma canggih untuk memecahkan program integer linear meliputi:

    
Metode pemotongan-pesawat
    
branch and bound
    
cabang dan memotong
    
cabang dan harga
    
jika masalah memiliki beberapa struktur tambahan, dimungkinkan untuk menerapkan generasi kolom tertunda.
Algoritma pemrograman integer tersebut dibahas oleh Padberg dan Beasley.Program linier Integral
Sebuah program linear dalam variabel riil dikatakan terpisahkan jika memiliki setidaknya satu solusi optimal yang tidak terpisahkan. Demikian juga, sebuah polyhedron P = \ {x \ mid Ax \ ge 0 \} dikatakan terpisahkan jika untuk semua tujuan layak dibatasi fungsi c, program linier \ {\ max cx \ mid x \ dalam P \} memiliki optimum x ^ * dengan koordinat bilangan bulat. Seperti yang diamati oleh Edmonds dan Giles pada tahun 1977, satu ekuivalen dapat mengatakan bahwa polyhedron P merupakan bagian integral jika untuk setiap dibatasi layak terpisahkan tujuan fungsi c, nilai optimal dari program linier \ {\ max cx \ mid x \ dalam P \} adalah integer.
Program linier Integral sangat penting sentral dalam aspek polyhedral optimasi kombinatorial karena mereka memberikan karakterisasi alternatif masalah. Secara khusus, untuk masalah apa pun, convex hull dari solusi adalah polyhedron terpisahkan, jika polyhedron ini memiliki deskripsi yang bagus / kompak, maka kita efisien dapat menemukan solusi yang layak optimal dalam setiap tujuan linier. Sebaliknya, jika kita dapat membuktikan bahwa relaksasi program linier merupakan bagian integral, maka itu adalah deskripsi yang diinginkan dari lambung cembung layak (integral) solusi.
Perhatikan bahwa istilah tidak konsisten di seluruh literatur, jadi salah satu harus berhati-hati untuk membedakan dua konsep berikut,

    
dalam program integer linear, dijelaskan pada bagian sebelumnya, variabel secara paksa dibatasi untuk bilangan bulat, dan masalah ini adalah NP-keras pada umumnya,
    
dalam program linear integral, dijelaskan dalam bagian ini, variabel tidak dibatasi untuk bilangan bulat melainkan satu telah membuktikan entah bagaimana bahwa masalah terus menerus selalu memiliki nilai yang optimal terpisahkan (asumsi c merupakan bagian integral), dan nilai ini yang optimal dapat ditemukan efisien karena semua program linier polinomial-ukuran dapat diselesaikan dalam waktu polinomial.
Salah satu cara umum untuk membuktikan bahwa polyhedron merupakan bagian integral adalah untuk menunjukkan bahwa ia benar-benar unimodular. Ada beberapa metode umum lainnya termasuk properti dekomposisi integer dan jumlah ganda integralistik. Piringan hitam terpisahkan spesifik lainnya yang terkenal termasuk polytope cocok, kisi polyhedra, submodular aliran polyhedra, dan persimpangan dari 2 polymatroids umum / g-polymatroids --- misalnya lihat Schrijver 2003.
Sebuah dibatasi terpisahkan polyhedron kadang-kadang disebut kisi polytope cembung, terutama dalam dua dimensi.Pemecah dan scripting (pemrograman) bahasa
Gratis open-source lisensi permisif:Nama Lisensi Info SingkatJOptimizer ASL java cembung optimasi perpustakaan - open sourceOpenOpt BSD Universal cross-platform kerangka optimasi numerik,lihat halaman LP dan masalah lain yang terlibatOpti Toolbox BSD MATLAB Toolbox untuk memecahkan linear, nonlinear, masalah optimasi terus menerus dan diskrit.
Lihat halaman Contoh LP Opti untuk beberapa contoh.
Free open-source copyleft (timbal balik) lisensi:Nama Lisensi Info SingkatKasuari kendala pemecah LGPL sebuah kendala tambahan memecahkan toolkit yang efisien memecahkan sistem persamaan linear dan ketidaksetaraan.glpk GPL GNU Linear Programming Kit, LP / MILP solver gratis. Menggunakan GNU mathprog bahasa pemodelan.Qoca GPL perpustakaan untuk secara bertahap sistem penyelesaian persamaan linier dengan berbagai fungsi tujuanCLP CPL pemecah LP dari COIN-ORR-Proyek GPL bahasa pemrograman dan lingkungan perangkat lunak untuk komputasi statistik dan grafis
Minto (Mixed Integer Optimizer, sebuah pemecah integer programming yang menggunakan cabang dan algoritma bound) memiliki kode sumber yang tersedia untuk umum [16] tetapi tidak open source.
Proprietary:Nama Info SingkatAIMMSAMPL Sebuah bahasa pemodelan populer untuk skala linier, campuran integer dan optimasi nonlinier dengan versi mahasiswa gratis yang tersedia.APMonitor API untuk MATLAB dan Python. Memecahkan contoh Linear Programming (LP) masalah melalui antarmuka web.CPLEX solver Populer dengan API untuk beberapa bahasa pemrograman, dan juga memiliki bahasa pemodelan dan bekerja dengan AIMMS, AMPL, GAMS, MPL, OpenOpt, OPL Development Studio, dan TOMLAB. Gratis untuk penggunaan akademis.EXCEL Solver FungsiFinMath Sebuah perpustakaan numerik NET mengandung versi padat dan jarang dari solver primal dual interior-point..FortMPGAMSGurobi Solver dengan algoritma paralel untuk program linear skala besar, program kuadrat dan program campuran bilangan bulat. Gratis untuk penggunaan akademis.IMSL numerik Perpustakaan Koleksi matematika dan algoritma statistik yang tersedia di C / C + +, Fortran, Java dan C # /. NET. Optimasi rutinitas di Perpustakaan IMSL termasuk dibatasi, linear dan nonlinearly dibatasi minimizations, dan algoritma pemrograman linier.LiPS paket optimasi Gratis ditujukan untuk memecahkan linear, integer dan masalah goal programming.MATLAB Sebuah tujuan umum dan matriks berorientasi bahasa pemrograman untuk komputasi numerik. Pemrograman linear di MATLAB memerlukan Toolbox Optimasi Selain basis MATLAB produk, rutinitas yang tersedia meliputi BINTPROG dan LINPROGMathcad Sebuah editor WYSIWYG matematika. Ini memiliki fungsi untuk memecahkan masalah optimasi baik linier dan nonlinier.Mathematica Sebuah tujuan umum bahasa pemrograman untuk matematika, termasuk kemampuan simbolik dan numerik.MOSEK Sebuah solver untuk optimasi skala besar dengan API untuk beberapa bahasa (C + +, java,. Bersih, Matlab dan python).NAG Numerik Perpustakaan Koleksi rutinitas matematika dan statistik yang dikembangkan oleh Numerik Group untuk beberapa bahasa pemrograman (C, C + +, Fortran, Visual Basic, Java dan C #) dan paket (MATLAB, Excel, R, LabVIEW). Optimasi bab dari Perpustakaan NAG termasuk rutinitas untuk masalah pemrograman linear dengan kedua jarang dan non-linear jarang kendala matriks, bersama dengan rutinitas untuk optimalisasi kuadrat, nonlinier, jumlah kuadrat fungsi linear atau nonlinear dengan nonlinear, dibatasi atau ada kendala . Perpustakaan NAG memiliki rutinitas untuk optimasi lokal maupun global, dan masalah terus-menerus atau integer.NMath Statistik A NET statistik mengandung pemecah simpleks [17]. Tujuan umum.OptimJ Sebuah bahasa pemodelan berbasis Java untuk optimasi dengan versi gratis yang tersedia [18] [19].SAS / OR Sebuah suite pemecah Linear, Integer, nonlinier, Derivatif Bebas, Jaringan, Kombinatorial dan Optimasi Kendala, yang aljabar pemodelan OPTMODEL bahasa, dan berbagai solusi vertikal yang ditujukan untuk masalah / pasar tertentu, yang semuanya terintegrasi dengan Sistem SAS.SCIP Sebuah kendala tujuan umum pemrograman bilangan bulat solver dengan penekanan pada MIP. Kompatibel dengan bahasa pemodelan Zimpl. Gratis untuk penggunaan akademis dan tersedia dalam kode sumber.SuanShu Sebuah perpustakaan matematika berbasis Java yang mendukung pemrograman linear dan jenis lain dari optimasi numerik. [20]UFFLP Sebuah API mudah bagi Campuran, Integer Linear Programming dan [21]VISSIM Sebuah blok diagram bahasa visual untuk simulasi sistem dinamis.
















































.
Share this article :