Ada sistem kendala linier . Saya ingin menemukan vektor yang benar-benar positif yang memenuhi batasan-batasan ini. Itu berarti, diperlukan untuk setiap komponen dari . Bagaimana saya bisa menggunakan LP solver untuk menemukan vektor benar-benar positif (atau mengkonfirmasi bahwa tidak ada )? Saya tidak bisa begitu saja memperkenalkan sistem kendala lain , karena kesetaraan harus selalu diizinkan dalam LP — tetapi saya dapat menggunakan pemecah LP beberapa kali, dengan mengubah fungsi tujuan. Saya pikir saya harus menggunakan metode variabel kendur, tapi saya tidak tahu caranya.
15
Untuk masalah kelayakan LP, saya tidak akan menggunakan simpleks standar. Algoritma simpleks primal (atau ganda) standar hanya akan mengunjungi simpul set yang layak dari masalah primal (atau ganda).
Biarkan set yang layak dari masalah yang Anda benar-benar ingin pecahkan menjadi , dan anggap sebaliknya Anda yang memecahkan masalah ( F ε ):F={x:Ax≤b,x>0} Fε
Perkiraan terdekat dari masalah yang ingin Anda selesaikan adalah , yang menerima terlalu banyak poin. Masalahnya adalah bahwa batas dari orthant positif (yaitu, himpunan B = { x : x ≥ 0 , ∃ i : x i = 0 } bisa membuat bagian dari batas dari himpunan layak dari F 0 . Kami akan suka mengecualikan poin-poin itu. Salah satu cara melakukannya adalah dengan melakukan apa yang disarankan Aron, yaitu mengatur εF0 B={x:x≥0,∃i:xi=0} F0 ε untuk beberapa nilai positif kecil, dan kemudian gunakan algoritma LP standar. Strategi ini bagus, dan mungkin akan berhasil dalam berbagai situasi. Namun, itu akan gagal jika tidak layak. Kita tahu bahwa F 0 ⊂ F ⊂ F ε untuk semua ε > 0 (untuk penyalahgunaan notasi dan merujuk pada set yang layak oleh masalah yang terkait), dan mungkin bahkan jika Anda memilih nilai positif kecil ε , solver LP akan menunjukkan bahwa LP Anda tidak mungkin.Fε F0⊂F⊂Fε ε>0 ε
Untuk solver LP, saya akan menggunakan algoritma titik interior untuk piringan hitam yang dimulai dengan titik layak dan tetap layak, yang merupakan cara lain untuk mengecualikan poin di . Anda tidak perlu menyediakan titik yang layak untuk algoritma ini; pemecah standar akan melakukannya untuk Anda. Metode seperti penskalaan affine, pengurangan potensial, dan metode penghalang mengatur piranti bantu bantu yang akan menemukan solusi yang layak, dan iterasi untuk algoritma ini melintasi bagian dalam wilayah yang layak. Anda hanya perlu menemukan satu titik di wilayah layak Anda, jadi selama masalah tambahan yang digunakan oleh pemecah LP menemukan titik layak untuk masalah Anda, dan bahwa titik layak itu benar-benar positif, Anda harus baik-baik saja. Jika memecahkan F ε gagal untuk nilai positif kecil εB Fε ε , Anda mungkin masih dapat menggunakan metode ini untuk mencari titik layak ketat positif dalam .F0
Namun, jangan gunakan simpleks, karena itu hanya akan mengeksplorasi simpul , yang persisnya ingin Anda hindari.Fε
sumber
Masalah kelayakan adalah permainan yang sedikit lebih rumit daripada masalah linier umum, yang telah Anda catat. Jika Anda menyelesaikan kira-kira (dengan menggunakan representasi floating-point dari sistem persamaan dan kendala), sah untuk meminta , di mana ϵ adalah beberapa nilai numerik yang sangat kecil, cukup besar untuk memastikan bahwa x i sebenarnya hidup di ℜ + , tetapi cukup kecil sehingga solusi pada batas tidak dipertimbangkan.xi>=ϵ ϵ xi R+
Anda mungkin harus menyesuaikan , dan solusi Anda akan memenuhi syarat untuk "dalam faktor ϵ ", tetapi ini cukup untuk banyak situasi.ϵ ϵ
sumber
The answer given by aeismail is to be read carefully, regard the lp
s.t.
It has solutions(1,0) and (0,1) as well as others (degenerated). The generality of the question implys that these cases need to be treated as well.
Since you are able to choose you objective function, you could try to modify it iteratively. E.g. Start with all coefficients for all variables equal to one, check wether you gain an approprate solution. If one variable is zero, rise it's coefficient and start again...
Though I can not give a mathematical prove that this works (or a well defined procedure how to modify the objective function). I hope this helps :)
sumber