1 线性规划问题 1
1．1 线性规划问题 1
1．1．1 引言 1
1．1．2 线性规划问题的标准形式 3
1．1．3 线性规划的图解法 5
1．1．4 线性规划的性质 6
1．2 单纯形法 8
1．2．1 单纯形法原理 8
1．2．2 单纯形法的计算步骤 11
1．2．3 单纯形表 12
1．2．4 两阶段法 15
1．2．5 大M法 20
1．2．6 退化与防止循环 22
1．3 修正单纯形法 28
1．3．1 修正单纯形法原理 28
1．3．2 修正单纯形法的计算步骤 29
1．4 有界变量单纯形法 34
1．4．1 基本概念 34
1．4．2 有界变量单纯形法原理 35
1．4．3 有界变量单纯形法的计算步骤 37
1．5 最优性条件和对偶问题 41
1．5．1 Kuhn-Tucker条件 41
1．5．2 对偶问题的表示 42
1．5．3 对偶原理 45
1．5．4 对偶单纯形法 48
1．5．5 原始-对偶单纯形法 51
1．5．6 原始-对偶单纯形表 54
1．5．7 寻找对偶初始解的人工约束法 58
1．6 分解算法 62
1．6．1 D-W分解方法概述 62
1．6．1 D-W分解方法的计算步骤 64
1．7 灵敏度分析 70
1．7．1 改变费用系数向量 71
1．7．2 改变右端向量 73
1．7．3 改变矩阵 74
1．7．5 增加新的不等式约束 76
1．7．4 增加新变量 76
1．7．6 增加新的等式约束 78
1．8 Karmarkar投影尺度算法 78
1．8．1 Karmarkar算法的基本思想 78
1．8．2 Karmarkar标准形式 78
1．8．3 单纯形上的投影变换及势函数 79
1．8．4 Karmarkar算法 80
1．8．5 向Karmarkar标准形式的转换 83
参考文献 86
2 非线性规划 87
2．1 基础知识 87
2．1．1 非线性规划问题 87
2．1．2 凸集与凸函数 89
2．1．3 无约束问题的极值条件 95
2．1．4 约束问题的最优性条件 97
2．1．5 一维搜索 103
2．2 无约束非线性规划 111
2．2．1 最速下降法 111
2．2．2 Newton法 114
2．2．3 共轭梯度法 118
2．2．4 拟Newton法 126
2．2．5 最小二乘法 132
2．2．6 模式搜索法 138
2．2．7 Rosenbrock算法 140
2．2．8 可变多面体搜索法 144
2．2．9 Powell法 148
2．3 约束非线性规划方法 151
2．3．1 Zoutendijk可行方向法 151
2．3．2 Rosen梯度投影法 157
2．3．3 既约梯度法 163
2．3．4 Frank-Wolfe方法 170
2．3．5 近似规划方法 172
2．3．6 割平面法 175
2．3．7 二次规划 179
2．3．8 罚函数法 185
2．3．9 障碍函数法 188
2．3．10 外插技术 190
2．3．11 乘子法 191
参考文献 194
3 整数规划 195
3．1 引言 195
3．2 例子 196
3．3 解法概述 199
3．3．1 分解 201
3．3．2 松弛 202
3．3．3 探测 202
3．4 整数规划的一般解法 204
3．4．1 分支定界法 205
3．4．2 0-1规划的“隐数法” 210
3．5．1 参数表示式 215
3．5 整数规划的割平面方法 215
3．5．2 对偶单纯形算法 217
3．5．3 基本割平面 219
3．5．4 分数割平面算法 220
3．6 分解算法 225
3．7 集合覆盖和分解问题的解法 229
3．8 目标函数为分式时的整数规划 237
3．9 割平面法的新进展 239
3．9．1 常用符号与基本概念 239
3．9．2 分离不等式(分离面) 241
3．9．3 Gomory-Chvatal法 242
3．9．4 同余法 242
3．9．5 逻辑和法 243
3．9．6 (SA)函数法 244
3．9．7 升维法 246
3．9．8 装箱多面体的边界面 246
3．9．9 背包问题的边界面 247
3．9．10 匹配多面体 248
3．9．11 Hamilton圈 250
参考文献 252
4 动态规划 254
4．1 引言 254
4．1．1 动态规划的发展及研究内容 254
4．1．2 决策过程的分类 255
4．2．1 动态规划的基本概念 256
4．2 基本概念、基本方程和计算方法 256
4．2．2 基本定理和基本方程 259
4．2．3 后向算法和前向算法 260
4．2．4 动态规划与静态规划的关系 263
4．3 若干典型问题的动态规划模型 265
4．3．1 最短路线问题 266
4．3．2 生产计划问题 266
4．3．3 货物存储问题 267
4．3．4 设备更新问题 268
4．3．5 资源分配问题 270
4．3．6 系统可靠性问题 272
4．3．7 任务均衡问题 274
4．3．8 排序问题 275
4．3．9 推销商问题 276
4．3．10 线性系统的二次指标函数问题 277
4．4 不定期和无限期决策过程 278
4．4．1 函数迭代法和策略迭代法 281
4．4．2 不定期平稳决策过程和平稳策略 283
4．4．3 无限期平稳过程 285
4．5 随机性多阶段决策过程 286
4．5．1 基本方程 287
4．5．2 几个典型问题 288
4．6 确定性连续决策过程 293
4．7．1 最优值函数近似法 295
4．7 计算方法的改进 295
4．7．2 Lagrange乘子法 298
4．7．3 几种实用算法 300
参考文献 306
5 多目标规划 307
5．1 引言 307
5．2 多目标规划的基本概念与K-T条件 309
5．2．1 多目标规划的基本概念 309
5．2．2 多目标规划的K-T条件 317
5．3 寻求多目标规划非劣解的方法 318
5．3．1 加权法 319
5．3．2 约束法 323
5．4．1 线性多目标规划的单纯形法 327
5．4 寻求线性多目标规划非劣解的方法 327
5．3．3 混合法 327
5．4．2 寻求线性多目标规划相邻非劣极点解的方法 333
5．5 解多目标规划的交互法 337
5．5．1 Geoffrion方法 337
5．5．2 逐步法 339
5．5．3 Zionts-Wallenins方法 344
5．5．4 代替价值交换法 349
5．6 目标规划 354
5．6．1 目标规划的一般形式 355
5．6．2 目标规划的图解法 358
5．6．3 目标规划的单纯形法 361
参考文献 369
6 对策论 371
6．1 矩阵对策 371
6．1．1 引言 371
6．1．2 矩阵对策 374
6．1．3 混合策略 376
6．1．4 最优策略及其性质 378
6．1．5 策略的优超关系 380
6．1．6 2×2矩阵对策的解 384
6．1．7 2×n和m×2矩阵对策的图解法 386
6．1．8 3×3矩阵对策的解 389
6．1．9 矩阵对策与线性规划的关系 395
6．2．1 零和二人无限对策 397
6．2 无限对策 397
6．2．2 混合策略 398
6．2．3 连续对策 399
6．2．4 最优策略的性质 400
6．2．5 具凸支付函数的连续对策 401
6．2．6 定时对策 403
6．3 n人非合作对策 407
6．3．1 基本概念 407
6．3．2 平衡点的存在性 409
6．3．3 2×2双矩阵对策的平衡点 409
6．4 n人合作对策 415
6．4．1 基本概念、特征函数 415
6．4．2 策略等价关系，(0，1)规范化 417
6．4．3 二人合作对策 419
6．4．4 转归及其优超关系 422
6．4．5 核心 428
6．4．6 稳定集 431
6．4．7 广义转归与强ε核心 439
6．4．8 核 442
6．4．9 核仁 448
6．4．10 Shapley值 454
参考文献 455
附录1 中文—外文名词索引 457
附录2 外文—中文名词索引 472
附录3 外国人名表 490