← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

29 第29章 线性规划

Fourth edition · 核验版本的摘录快照 · 导入于 2026-10-23T08:18:08.754Z

, 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