文档介绍：第二章 线性规划模型
线性规划是数学规划中研究较早, 发展较快, 应用广泛的
的一个重要分支, 也是数学模型中的一项重要内容. 它在生产
安排、物质运输、投资决策、交通运输等现代工农业和经济
安排、物质运输、投资决策、
线性规划的图解法针对的是具有两个决策变量的线性规
划问题.
设线性规划
求解过程
⑴建立合适的坐标系统;
⑵对约束条件
建立第 条直线
从而确定可行域;
⑶对等值线:
由规划的类型确定等值线
移动方向, 则最优解为等值线在移动过程中与可行域的最
后交点.
例 求解规划
最后交点
移动方向
解 由图中可以看到, 可行域为多边形区域 最
优解为 最优解值为
设线性规划
并进一步假定约束条件系数矩阵中
中有 阶单
位子矩阵.
单纯形方法解题步骤:
, 并保证在该表中基变量的价值系数为0.
, 并判定当前解是否为最优解. （当前解
, 则进行换基:
则检验数行 为新价值系数的相反数行.
的定义是基变量取右端的常数项, 非基变量取为零）.
判定当前解是否为最优解的条件是
⑴确定进基变量 其中 由关系
确定.
⑵确定出基变量 其中
而 为第 行对应的基变量.
⑶以 为主元进行迭代, 目标: 主元化为1, 该列的其余
.
元化为零. （只能用行变换）
注 线性规划的单纯性表
设线性规划为
并且假设在约束条件系数矩阵中前 个列向量为单位向量,
则相应的单纯形表为
表中的 行是检验数行, 中的数是将 消为0后, 取负
值后所得到的.
例2 用单纯形方法求解线性规划.
解 由前面讨论知原问题的单纯形表为
此时, 当前解为
由于 故当
前解非最优解. 所以
主元
主元
故最优解为 最优解值为
检验数非负
二、整数规划
在前面所涉及到的许多线性规划模型中, 很多情况下, 除
了对变量有非负要求外, 有时甚至要求其取值为整数型的.
例如在问题一中, 变量 表示在第 种方案下所使用的原
料钢管数, 则相应取值为非负整数. 这样的线性规划称为
整数规划.
若线性规划中对变量的要求为部分整数型的, 这样的规
称为混合型的.
在整数规划中, 舍弃决策变量的整数限制, 所得到的规
划称为原规划所对应的松弛问题. 求解整数规划并不能通
过求对应的松弛问题的最优解再取其整数部分而求得. 求
解整数规划的方法主要有分枝定界法和割平面法. 这里我
们仅介绍分枝定界法, 有兴趣的读者可以参阅相应的书籍.
求解整数规划的的分枝定界法
设线性规格
为整数.
⑴求出对应松弛问题的最优解, 若该解为整数解, 则该解也
是原规划的最优解, 若该解不是整数解, 则进行分枝;
⑵设 不是整数解, 则最优整数解中的 必然满足
因此将原问题分解成两个规划
为整数.
及
为整数.
分别求出这两个规划所对应的松弛问题的最优解;
⑶若有一个分枝的解为整数解, 而另一个分枝的最优解的
函数值小于该整数解的函数值, 则将该枝剪去（定界）并
由此得到原问题的最优解;
⑷若两个分枝对应的松弛问题的最优解都不是整数解, 则
分别进行分枝, 继续求解.
例3 求解整数规划
且为整数.
解 由单纯性方法得到松弛问题的最优解:
注意到该解不是整数解, 取 进行分枝, 形成2个规划,
规划⑴
且为整数.
及规划⑵
且为整数.
这两个规划所对应的松弛问题的最优解分别为
由于规划⑴所对应的松弛问题的最优解值低于规划⑵所对
应的松弛问题的最优解值, 且规划⑵所对应的松弛问题的
解为整数解, 故规划⑴舍去（定界, 剪枝）, 从而得到原
规划的最优解为
—1规划
整数规划中的一个特殊模型是0—1规划. 在引入0—1规
划之前先看一个例子.
问题三
课程选修方案确定
某学校规定: 运筹学专业的学生毕业时至少学****过两门
数学课, 三门运筹学课和两门计算机课. 这些课程的编号、