第二章习题。
12、对于下面的线性规划问题,以为基写出相对应的典式。
解:由题可以知:
取一个基,即:且。
在matlab中可以计算得到:
由可得典式的目标函数:
由可得:由此与题中线性规划问题相对应的典式为:
14、用单纯形法求解线面的线性规划问题,并在平面上画出迭代点走过的路线。
解:由题先将题中线性规划问题化为标准形:
由此可写出,即为:
则可以得出是一个单位矩阵,且,所以基是可行基,为基变量,为非基变量。基对应的基本可行解为:,其目标函数值。方程组已是典式,得到一张单纯形表如下:
由题可知,检验数可由可得:不是负数,则当前解不是最优解,列中有三个元素大于零,取:
故转轴元为,为进基变量,为出基变量。
目前的新基为,进行旋转变换后得下表:
它对应的基本可行解为:,其目标函数值为。但为正数,仍不是最优解,此时以为转轴元,为进基变量,为出基变量,进行旋转变化得下表:
它对应的基本可行解为:,目标函数值为,此时检验数向量为负数,故为最优解。
16、用单纯形法求解下列线性规划问题:
解:由题先将题中线性规划问题化为标准形:
由此可以得到矩阵。
则可以得出是一个单位矩阵,且,所以基是可行基,为基变量,为非基变量。基对应的基本可行解为:,其目标函数值。
由此写出最初的单纯性表:
由题可知,检验数可由可得:不是负数,则当前解不是最优解,列中有三个元素大于零,取:
故转轴元为,为进基变量,为出基变量。
进行旋转变换后得下表:
它对应的基本可行解为:,其目标函数值为。但为正数,仍不是最优解,此时以为转轴元,为进基变量,为出基变量,进行旋转变化得下表:
它对应的基本可行解为:,目标函数值为,此时检验数向量为负数,故为最优解。
解:由此可以得到矩阵。
则可以得出是一个单位矩阵,且,所以基是可行基,为基变量,为非基变量。基对应的基本可行解为:,其目标函数值。
由此写出最初的单纯形表:
由题可知,检验数可由可得:不是负数,则当前解不是最优解,故为进基变量,为出基变量。
进行旋转变换后得下表:
它对应的基本可行解为:,其目标函数值为。但为正数,仍不是最优解,此时以为转轴元,为进基变量,为出基变量,进行旋转变化得下表:
它对应的基本可行解为:,目标函数值为,此时检验数向量为负数,故为最优解。
18、写出下面线性规划的对偶规划。
解:由题可得,有定义可得原问题的线性规划问题的对偶规划为:
按分量形式写出的对偶规划为:
20、把线性规划问题:记为,1) 用单纯形算法解;
2) 写出的对偶;
3) 写出的互补松紧条件,并利用他们解对偶。
解:(1)、由题将化为标准形式为:
由此可写出,即为:
则可以得出是一个单位矩阵,且,所以基是可行基,为基变量,为非基变量。基对应的基本可行解为:,其目标函数值。得到一张单纯形表如下:
将第0行化成检验行为:
它对应的为正数,仍不是最优解,以为进基变量,为出基变量,进行旋转变化得下表:
它对应的,所以问题的最优解为,最优值为:
2)、由题可得:
所以可得对偶规划:
3)、由题问题的最优解为以及互补松紧性定律可得:
由此解得:由此对偶问题的最优解为:,最优值为:
22、用对偶单纯形法求解。
解:由题将原问题写成标准形式:
所以有:由题,以为基向量,单纯性表如下:
由此检验数为,以为离基变量,为进基变量,旋转得:
同理,检验数小于零,以为离基变量,为进基变量,旋转得:
由最优化准则可得原问题的最优解为:,最优值为:
第三章整数线性规划。
1、某厂产生两种产品,每件产品均要在甲、乙、丙各台设备上加工。每件第种产品在第i台设备上加工消耗工时为。现在各台设备可用于生产这两种产品的工时分别为每件第j种产品可以提供利润。
根据需要产品的生产量不能少于件,。而生产的产品数量必须取整数。问如何安排生产能使该厂利润最大?
是建立该数学问题的数学模型。
解:设生产两种产品的数量分别为。
则要使利润最大则目标函数为:
根据题意可得限制条件有:
综上可得该问题的数学模型为:
2、指派问题。
设有项任务要完成,恰有n个人有能力去完成任何一项任务,第个人完成第项任务需要的时间为试写出一个使总花费时间最少的人员分配工作方案的数学模型。
解:由题可运用变量,根据题意可设表示。
要使总花费时间最少,则:
根据题意可得限制条件有:
综上可得其数学模型为:
6、用分支定界法解下述问题:
解:由题记原问题的松弛问题为,显然满足替代问题的要求:
的最有解为:均不是整数,则从中选进行分枝。
在中分成两个问题和,如下:
由此的最优解为,的最优解为。
由于两个子问题的最优解仍不是原问题的可行解,所以选取边界较大的子问题继续分枝,在分别分成两个子问题和,如下:
由此的最优解为,的最优解为。
这两个解均为原问题的可行解,所以保留可行解中最大的,即:
总体过程如下:
第4章非线性规划。
5、判别以下函数哪些是凸函数,哪些是凹的,哪些是非凸非凹的?
解:(1的矩阵为:
的各阶顺序主子式分别为:
是正定的,所以是凸函数。
2)的矩阵为:
的各阶顺序主子式分别为:
所以是凹函数。
3)的矩阵为:
的各阶顺序主子式分别为:,是半正定的,所以是凸函数。
7、证明下列规划为凸规划。
1)问:该问题是否存在最优解?
解:由题可得目标函数的矩阵为:
的各阶顺序主子式分别为:
是半正定的,所以是凸函数。
又对于条件,有显然它是一个半正定矩阵,是凸函数,所以该非线性规划是一个凸规划。
8、设已知,试用解析方法求的极小点。
解:由题可得。
带入中得:即:
所以。令则。
所以当时最小。
9、用0.618法求一下问题的近似解已知函数的单谷区间,要求最后区间精度。
解:由题迭代过程如下表:
第三轮迭代开始有,所以近似最优解为。
10、用法求以下问题的近似最优解给定并用解析方法求出该问题的精确最优解,然后比较二者结果。
解:用法求解如下:
先求出 计算结果列于下表:
12、用法对作非精确一维搜索,取增大探索点系数。
解:由题。又因为。
所以有:令选取新的探索点:所以。即:
所以已同时满足规则到的两个要求,停止迭代。
综上可得非精确解。
14、求以下无约束非线性规划问题的最优解。
解:(1),令则有。
由此可得:又矩阵为正定矩阵。
所以整体最优解为:
2),令则有。
由此可得:又矩阵当且仅当为正定矩阵。
所以函数具有局部最优解。
23、写出下列问题的条件,并求出它们的点。
解:由题该问题的函数是:
又。所以该问题的条件问:
作为点,除了满足以上条件外,还应当满足可行性的条件:
经过讨论可得点为。
25、用法求解以下问题。
取初始可行点。
26、用罚函数法求解问题。
1)写出时相应的增广目标函数,并画出它们对应的图形。
2)取求出近似最优解的迭代点列。
3)利用(2)求问题的最优解。
运筹学第二章
第 2 次课 2学时。本次课教学重点 线型规划模型有关概念 法求解线型规划模型。本次课教学难点 线型规划模型有关概念 各种解的情况分析。本次课教学内容 第二章线性规划的 法。第一节问题的提出。一 引例。例1.某工厂在计划期内要安排 两种产品的生产,已知生产单位产品所需的设备台时及a b两种原材料的消...
运筹学第二章答案
1 某人根据医嘱,每天需补充a b c三种营养,a不少于80单位,b不少于150单位,c不少于180单位 此人准备每天从六种食物中摄取这三种营养成分 已知六种食物每百克的营养成分含量及食物 如表2 22所示 1 试建立此人在满足健康需要的基础上花费最少的数学模型 2 假定有一个厂商计划生产一中药丸,...
运筹学第二章课后题
习题2.1 某厂利用a b两种原料生产甲 乙 丙三种产品,已知单位产品所需的原料 利润及有关数据如表2 3所示。表2 3两种原料生产三种产品的有关数据。请分别回答下列问题 1 求使该厂获利最大的生产计划。2 若产品乙 丙的单位利润不变,当产品甲的单位利润在什么范围内变化时,最优解不变?3 若原料a市...