Ako vyriešiť toto nerovnaké číslo 0-1 Knapsack_Problem v Ruby - rubín, lineárne programovanie, batoh-problém, glpk, integer-programovanie

Otázka:

minimalizácia x1+x2+...+xn

známy k1*x1+k2*x2+...kn*xn = T

k1,k2,...,kn a T sú známe celé čísla a> 0

k1 > k2 > k3 > ... > kn

Všetky x sú tiež celé čísla a> = 0

Nájdite všetky x

Snažil som sa používať Rglpk a Glpk. Ale nemôžem nájsť príklad s iba jedným radom matice.Je to celé Integer programovanie? A je to riešenie? Mnoho vďaky.

---

Niektoré kódy Ruby som napísal:

ks = [33, 18, 15, 5, 3]
t = 999

problem = Rglpk::Problem.new
problem.name = "test"
problem.obj.dir = Rglpk::GLP_MIN

rows = problem.add_rows(1)
rows[0].name = "sum of x equals t"
rows[0].set_bounds(Rglpk::GLP_UP, t, t)

cols = problem.add_cols(ks.size)
ks.each_with_index do |k,index|
cols[index].name = "k: #{k}"
cols[index].set_bounds(Rglpk::GLP_LO, 0.0, 0.0)
end

problem.obj.coefs = Array.new(ks.size, 1)

problem.set_matrix(ks)

problem.simplex
minimum_x_sum = problem.obj.get
xs = []
cols.each do |col|
xs << col.get_prim
end
xs

odpovede:

2 pre odpoveď č. 1

Áno, je to celočíselný program, skôr slávny, takzvaný "problém batohu". Preto môžete vyriešiť niektorý z balíkov, ktoré spomeniete (za predpokladu, že počet premenných nie je príliš veľký), ale omnoho efektívnejším prístupom je použitie dynamického programovania (pozri vyššie uvedený odkaz). Použitie DP tu je veľmi jednoduché. toto je jedna implementácia Ruby, ktorú som našiel spoločnosťou Googling.

Mal by som spomenúť niekoľko súvisiacich úloh. Po prvé, vašim obmedzením je obmedzenie rovnosti:

k₁X₁ + k₂X₂ + ... + k_nX_n = T

ale to sa zvyčajne predpokladá ako nerovnosť pomocou algoritmov (DP) batohov:

k₁X₁ + k₂X₂ + ... + k_nX_n <= T

Ak chcete vyriešiť problém s rovnosťou, môžete modifikovať algoritmus mierne alebo pridať termín:

M * (T - x₁ + x₂ + ... + x_n)

k cieľu, ktorý minimalizujete, kde M je veľmi veľké množstvo (10⁶, snáď), a tým prinútiť rovnosť k optimálnemu riešeniu. (Pri rozšírení koeficient pre každé x_ja stáva 1-M, Konštantný pojem MT nemožno brať do úvahy.)

Ďalšie dve podrobnosti:

• DP algoritmy umožňujú, aby premenné v objekte mali koeficienty iné ako 1 (a nedochádza k zvýšeniu efektívnosti, keď sú všetky koeficienty rovnaké 1); a
• Ak algoritmus DP maximalizuje (a nie minimalizuje) cieľ, môžete jednoducho vylúčiť koeficienty premenných v objekte, aby ste dosiahli optimálne riešenie problému minimalizácie.

---