《运筹学习题课课件.ppt》由会员分享，可在线阅读，更多相关《运筹学习题课课件.ppt（69页珍藏版）》请在三一办公上搜索。
1、运筹学第一次习题课,1.1用图解法求解下列线性规划问题，并指出问题具有最优解、无穷解无界解还是无可行解。,（a）S.T,解：,该问题有无穷最优解，即满足 且 的所有（），此时目标函数值为3,（c）由图可知在点（10，6）处目标函数取得最大值16。线性规划有唯一最优解。,（补充）,（b）,解：,用图解法找不到满足所有约束条件的公共范围，则该问题无解。,1.2对下述线性规划找出所有基解，指出哪些是基可行解，并确定最优解。,（a）s.t.,解:写出约束方程的系数矩阵 A=1 4-2 8-1 2 3 4R(A)=2，所以只要找出2个列向量组成矩阵满秩，这两个向量就是线性规划问题的一个基，由于 与 线性
2、相关不能构成基，构建表格列出全部基，基解，指出基可行解，*标注的为最优解：,(补充),（b）,1.3 分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基行解分别,对应图解法中可行域的哪一个定点.(b)S.t.,由图可知最优解为的解x=(7/2,3/2),最大值z=17/2,(2)单纯形法,首先在各约束条件上添加松弛变脸，将问题转化为标准形式S.t.,则 组成一个基，令得基可行解，由此列出初始单纯形表,初始表对应定点（0，0）,对应点（4，0）,表明已经找到问题的最优解 对应点，最大值为17/2,(补充),（a）st,（图解法）,（单纯形法）,1.6将下列线性规划问题化为标准
3、形式，并列出初始单纯形表。,（a）st,解：,在约束条件中添加松弛变量或剩余变量，且令，该问题转化为,其约束系数矩阵为 2 3-3 4 1 0A=4 1-1-2 0-1 3-1 1-3 0 0在A中人为的添加两列单位向量,2 3-3 4 1 0 0 0A=4 1-1-2 0-1 1 0 3-1 1-3 0 0 0 1令得到初始单纯形表,1.7分别用单纯形法中的大M法和两阶段法求解下列线性规划问题,并指出属那里类解,(a)st,(1)大M法,将上述线性规划问题中分别减去剩余变量 再加上人工变量，得st,其中M是一个任意大的正数。据此列出单纯形表,由于 0且，则该线性规划问题有无界解,（2）两阶段
4、法,现在上述线性规划问题的约束条件中分别减去剩余变量，再加上人工变量，得第一阶段的数学模型由此可列出单纯形表,-,第一阶段求得最优解目标函数的最优值为0。,因为人工变量全部为0，则X是线性规划问题的基可行解，于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量表取消，并填入原问题的目标函数的系数，进行第二阶段的运算，其表如下：,You有表知道 0,而 所以线性规划问题有无界解,(补充),（b）st,（大M法）,化成标准形,（二阶段法）,1.10判断并说明理由,（a）对取值无约束的变量 通常令，其中，在单纯形法求得的最优解中，有可能同时出现（b）若X1,X2分别是某一线性规划的最优解，则X=
5、aX1+(1-a)X2也该是线性规划问题的最优解，其中0 a 1。,（c）单纯形法计算中选取最大正校验数 对应的变量 作为换入基的变量，将使得迭代后的目标函数值得到最快增长。（d）含有n个变量m个约束的标准型的线性规划问题，基解数恰好为。（e）如线性规划问题存在可行域，则可行域一定包含坐标的原点。,1.12已知线性规划问题,St用单纯形法求解最终单纯形表如下，表中 为松弛变量,解：,由表可知 为此线性规划问题最优解，必在可行域顶点上，此顶点为带入解得,由表可知解得,1.19已知线性规划问题迭代某步的单纯形表如下：,问在什么条件下：（a）表中解为唯一最优解；（b）表中解最优，但具有无穷多最优解；
6、（c）现有基解为退化解；（d）问题具有无界解；（e）现有基解中，用 替换 后目标函数进一步优化。,1.21北海银行一个分理处每天个时间段对职员的需求如下表：,该分理处分别聘用部分全日制职员和部分非全日制职员。全日制职员每天从9：00工作到17：00，中间安排一小时午餐休,息（分两批，一批为12：0013：00，另一批为13：0014:00）每天薪金240元。非全日制职员分留批次上班，时间分别为9：0012：00，10：0013:00，11：0014：00，12：0015：00，13：0016：00，14：0017:00。每人每天薪金80元。问该分理处聘用全日制和各批此的非全日制职员各多少人，能满足需求又使薪金支出最少。,解：,令两种全日制的员工人数为 和，个时段非全日的人数为，则,以st,1.22工业原材料合理利用,要制作100套架子，每套有长2.9m、2.1m和1.5m的钢筋各一根。已知原材料长7.4m，应如何切割，使用原材料最节省，试建立线性规划模型并求解。,
