运筹学第2章答案

第2章对偶理论与灵敏度分析习题详解(习题)

2.1用改进单纯形法求解以下线性规划问题。 （1）Max z=6x1-2x2+3x3

2x1-x2+3x3?2

x1+4x3?4 x1，x2，x3?0 （2）min z=2x1+x2

3x1+x2=3 4x1+3x2?6

x1+2x2?3 x1,x2?0

2.2已知某线性规划问题，用单纯形法计算得到的中间某两步的计算表见表2-1所示，试将空白处数字填上。

表2-1 3 5 4 0 0 0 cj CB 5 0 0 XB x2 x5 x6 cj-zj b 8/3 14/3 20/3 x1 2/3 -4/3 5/3 -1/3 x2 1 0 0 0 . .… . x3 0 5 4 4 x4 1/3 -2/3 -2/3 -5/3 x5 0 1 0 0 x6 0 0 1 0 x2 x3 x1 cj-zj 15/41 -6/41 -2/41 8/41 5/41 -12/41 -10/41 4/41 15/41 2.3写出下列线性规划问题的对偶问题。 （1）min z= 2 x1+2 x2+4 x3

2 x1+3 x2+5 x3 ?2 3 x1+ x2+7 x3 ?3

第二章 线性规划的对偶理论

2.1 写出下列线性规划问题的对偶问题

max z=2x1+2x2－4x3

x1 + 3x2 + 3x3 ≤30 4x1 + 2x2 + 4x3≤80 x1、x2，x3≥0

解：其对偶问题为

min w=30y1+ 80y2 y1+ 4y2 ≥2 3y1 + 2y2 ≥2 3y1 + 4y2 ≥－4 y1、y2≥0

2.2 写出下列线性规划问题的对偶问题

min z=2x1+8x2－4x3

x1 + 3x2－3x3 ≥30 －x1 + 5x2 + 4x3 = 80 4x1 + 2x2－4x3≤50

x1≤0、x2≥0，x3无限制

解：其对偶问题为

max w=30y1+80 y2+50 y3 y1－ y2 + 4 y3 ≥2 3y1+5y2 + 2y3 ≤8 －3y1 + 4y2－4y3 =－4

y1≥0，y2无限制，y3≤0

2.3 已知线性规划问题

max z=x1+2x2+3x3+4x4

x1 + 2x2 + 2x3 +3x4≤20 2x1 + x2 + 3x3 +2x4≤20 x1、x2，x3，x4≥0

其对偶问题的最优解为y1*=6/5，y2*=1/5。试用互补松弛定理

运筹学(第2版) 习题答案 运筹学（第2版）习题答案2

第1章 线性规划 P36~40

第2章 线性规划的对偶理论 P68~69 第3章 整数规划 P82~84 第4章 目标规划 P98~100 第5章 运输与指派问题 P134~136 第6章 网络模型 P164~165 第7章 网络计划 P185~187 第8章 动态规划 P208~210 第9章 排队论 P239~240 第10章 存储论 P269~270 第11章 决策论 Pp297－298 第12章 博弈论 P325~326 全书360页

1

由于大小限制，此文档只显示第6章到第12章，第1章至第5章见《运筹学课后答案1》

习题六

6.1如图6－42所示，建立求最小部分树的0－1整数规划数学模型。

【解】边[i，j]的长度记为cij，设

?1边[i,j]包含在最小部分树内xij???0否则

数学模型为：

图6－42

minZ?cijxij??xij?5?i,j?x?x13?x23?2,x23?x24?x34?2?12?x34?x36?x46?2,x35?x36?x56?2??x12?x13?x24?x34?3 ?x?x?x?x?334354656??x23?x24?x46?x36?

运筹学 第1章 绪论

管理运筹学主讲教师：朱建军

联系方式：15853870192经济管理学院工商管理系

运筹学 第1章 绪论

课程导论课程类别 必修 开课层次 本科 学分 2.5 学时 45

内容提要 是运用数学方法对经济管理系统中 的各种有限资源进行统筹安排，为决策者提 供有依据的最优方案，以实现最有效的管理 的科学。其主要内容包括线性规划、动态规 划、整数规划、图论初步、决策分析等

运筹学 第1章 绪论

教材 《管理运筹学》(第4版),韩伯棠主编，高等教育出 版社。 参考书 1.《运筹学(第2版)》,熊伟编著，机械工业出版 社,2009 2.《运筹学》,孔造杰主编，机械工业出版社，2006 3.《运筹学》,运筹学教材编写组，清华大学出版社， 2005 4.《运筹学导论(第8版)》,[美] Frederick S. Hillier(弗雷德里克· S. 希利 尔) Gerald J. Lieberman(杰拉尔德· J. 利伯曼) 著 胡运权 等译 清华大学出版社 2007

运筹学 第1章 绪论

本课程授课方式与考核本课程理论课(4学时/周):讲授为主，结 合习题作业 上机实验6学时: 软件操作 成绩结构： 平

第三章 运输问题

在生产实际中，经常需要将某种物资从一些产地运往一些销地，因而存在如何调运使总的运费最小的问题。这类问题一般可用线性规划模型来描述，当然可以用单纯形法求解。但由于其模型结构特殊，学者们提供了更为简便和直观的解法——表上作业法。此外，有些线性规划问题从实际意义上看，并非运输问题，但其模型结构类似运输问题，也可以化作运输问题进行求解。

第一节 运输问题及其数学模型

首先来分析下面的问题。

例3.1 农产品经销公司有三个棉花收购站，向三个纺织厂供应棉花。三个收购站A 1、A2、A3的供应量分别为50kt、45kt和65kt，三个纺织厂B1、B2、B3的需求量分别为20kt、70kt和70kt。已知各收购站到各纺织厂的单位运价如表3—1所示（单位：千元/kt），问如何安排运输方案，使得经销公司的总运费最少？

表3—1 纺织厂 收购站 A1 A2 A3 B1 4 6 2 B2 8 3 5 B3 5 6 7 设xij表示从Ai运往Bj的棉花数量，则其运输量表如下表所示。

表3—2

纺织厂 收购站 A1 A2 A3 需求量（kt） B1 x11 x21 x31 20 B2 x12 x22 x32 70 B3 x13 x23 x33 70

运筹学

第1章 线性规划 章

实用运筹学 运用Excel Excel建模和求解 -运用Excel建模和求解 第1章 线性规划 Linear ProgrammingRUC, Information School, Ye Xiang

运筹学

第1章 线性规划 章

本章内容要点线性规划问题及其数学模型； 线性规划问题及其数学模型； 线性规划问题的电子表格建模； 线性规划问题的电子表格建模； 线性规划问题的多解分析。 线性规划问题的多解分析。

RUC, Information School, Ye Xiang

运筹学

本章内容1.1 线性规划问题及其数学模型 1.2 线性规划问题的图解法

第1章 线性规划 章

1.3 用Excel 规划求解”工具求解线性规划问 Excel“规划求解 规划求解” 题 1.4 线性规划问题求解的几种可能结果

RUC, Information School, Ye Xiang

运筹学

第1章 线性规划 章

线性规划是运筹学中研究较早， 线性规划是运筹学中研究较早，理论和 算法比较成熟的重要分支之一。 算法比较成熟的重要分支之一。 它主要研究在线性等式(或不等式)的 它主要研究在线性等式(或不等式) 限制条件下， 限制条件下，使某一线性目标函数取得 最

运筹学试题 (代码：8054)

一、填空题(本大题共8小题，每空2分，共20分)

1．线性规划闯题中，如果在约束条件中出现等式约束，我们通常用增加___的方法来产生初始可行基。

2．线性规划模型有三种参数，其名称分别为价值系数、___和___。 3．原问题的第1个约束方程是“=”型，则对偶问题相应的变量是___变量。 4．求最小生成树问题，常用的方法有：避圈法和 ___。

5．排队模型M／M／2中的M，M，2分别表示到达时间为___分布，服务时间服从负指数分布和服务台数为2。

6．如果有两个以上的决策自然条件，但决策人无法估计各自然状态出现的概率，那么这种决策类型称为____型决策。

7．在风险型决策问题中，我们一般采用___来反映每个人对待风险的态度。

8．目标规划总是求目标函数的___信，且目标函数中没有线性规划中的价值系数，而是在各偏差变量前加上级别不同的____。

二、单项选择题(本大题共l0小题，每小题3分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。多选无分。 9．使用人工变量法求解极大化线性规划问题时，当所有的检验数非零的人工变量，表明该线性规

运筹学（第2版）习题答案1--3

习题一

1.1 讨论下列问题：

（1）在例1.2中，如果设xj(j=1，2，…，7)为工作了5天后星期一到星期日开始休息的营业员，该模型如何变化．

（2）在例1.3中，能否将约束条件改为等式；如果要求余料最少，数学模型如何变化；简述板材下料的思路．

（3）在例1.4中，若允许含有少量杂质，但杂质含量不超过1％，模型如何变化．

（4）在例1.6中，假定同种设备的加工时间均匀分配到各台设备上，要求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小时，模型如何变化．

(5)在单纯形法中，为什么说当?k?0并且aik?0(i?1,2,,m)时线性规划具有无界解。 1.2 工厂每月生产A、B、C三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－23所示．

表1－23 产品 资源 材料(kg) 设备(台时) 利润(元/件) A 1.5 3 10 B 1.2 1.6 14 C 4 1.2 12 资源限量 2500 1400 根据市场需求,预测三种产品最低月需求量分别是150、260和120,最高月需求是250、310和130.试建立该问题的数学模型,使每月利润最大．

【解】设

《运 筹 学》教案

主讲人：李军华

课 程 名 称： 《运筹学》 课 程 主 讲 人： 李军华 专 业 班 级： 信息2001级合班 主讲人所在单位： 经济与管理学院信息管理学系

华南师范大学

经济与管理学院信息管理学系 2005年9月

面向21世纪课程教材

普通高等学校管理科学与工程类学科核心课程教材

管 理 运 筹 学

( 第2版) 韩伯棠 编著

高等教育出版社

高等教育电子音像出版社

1

目录

第一章 绪论 第二章 线性规划的图解法 第三章 线性规划问题的计算机求解 第四章 线性规划在工商管理中的应用 第五章 单纯形法 第六章 单纯形法的灵敏度分析与对偶 第七章 运输问题 第八章 整数规划 第九章 目标规划 第十章 动态规划 第十一章 图与网络模型 第十二章 排序与统筹方法 第十三章 存贮论 第十四章 排队论 第十五章 对策论 第十六章 决策分析 第十七章 预测

2

第一章 绪论

?§1 决策、定量分析与管理运筹学 ?§2 运筹学的分

第2章 线性规划 灵敏度分析

实用运筹学 -运用Excel建模和求解第2章 线性规划灵敏度分析 Sensitivity Analysis for Linear ProgrammingRUC, Information School, Ye Xiang

第2章 线性规划 灵敏度分析

本章内容要点线性规划灵敏度分析的概念和内容使用Excel进行灵敏度分析 影子价格的经济意义和应用

RUC, Information School, Ye Xiang

本章节内容2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 线性规划灵敏度分析 单个目标函数系数变动 多个目标函数系数同时变动 单个约束右端值变动 多个约束右端值同时变动 约束条件系数变化 增加一个新变量 增加一个约束条件 影子价格 (Shadow Price)RUC, Information School, Ye Xiang

第2章 线性规划 灵敏度分析

本章主要内容框架图

第2章 线性规划 灵敏度分析

单个 目标函数系数变动 多个 单个 约束右端值变动 多个 影子价格 内容 约束条件系数变化 灵敏度分析