原书出处
Introduction to Algorithms, Fourth Edition
29 第29章 线性规划
, y1 + 2y2 + y3 ≥ 1, 3y1 + 5y2 + 2y3 ≥ 4, you have a valid upper bound of 30y1+24y2+36y3.
The multipliers y1, y2, and y3 must be nonnegative, because otherwise you cannot combine the inequalities. Of course, you would like the upper bound to be as small as possible, and so you want to choose y to minimize 30y1 + 24y2 + 36y3. Observe that we have just described the dual linear program as the problem of finding the smallest possible upper bound on the primal. We’ll formalize this idea and show
in Theorem 29.4 that, if the linear program and its dual are feasible and bounded, then t
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter029.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea