运筹学 大作业

运筹学作业一、 有如下线性规划问题 Max f(x)=2x1 +3x2 x 1 + 2x 2 ≤ 8 4x 1 ≤ 16 4x 2 ≤ 12 x 1 ,x 2 ≥ 0 1） 用图解法求最优解； 解：线性规划问题为： Max f(x)=2x 1 +3x 2x 1 + 2x 2 ≤ 8 ① 4x 1 ≤ 16 ② 4x 2 ≤ 12 ③ x 1 ≥ 0 ④ x 2 ≥ 0 ⑤1、 以x 1为横坐标、x 2为纵坐标，建立平面坐标系。

然后在该平面坐标系上画出各个约束条件，包括非负约束条件。

（见下图1.1）0 1 2 3 4 5 6 7 8543211x图1.12、 图1.1所示的凸多边形OABCD 即为给定线性规划问题的可行域。

3、 将目标函数f(x)=2x 1 + 3x 2，写成x 2 = -2/3x 1 + 1/3f(x) ⑥令f(x)=0，则上式变为x 2 = -2/3x 1，对应直线见下图1.2的⑥。

图1.24、 观察图1.2将直线⑥平行移动至与凸多边形OABCD 的顶点C 相切时，对应直线⑦，目标函数f(x)取得最大值，此时得最优解，为：x 1 =4，x 2 =2（即C 点的坐标值），目标函数值f(x)=14。

即图1.3所示图1.32） 写出所有基本可行解，并指出它在图解法图中的位置； 解：基本可行解如下：(0,0)、(0,3) 、(2,3) 、(4,2) 、(4,0)分别对应图解法图1.1中凸多边形OABCD 的五个顶点O 、A 、B 、C 、D 。

3） 用QSB 软件求最优解，对C 1,C 2,b 1,b 2进行灵敏度分析，打印出计算结果。

解：1、 QSB 软件求出最优解：灵敏度分析：q 1=1.5，资源1的影子价格为1.5，资源1无剩余； q 2=0.5，资源2的影子价格为0.5，资源2无剩余； q 3=0，资源3的影子价格为0，资源3有剩余； q 1最大，资源1最紧缺。

C 1、C 2：从上面最优解可看到，C 1、C 2为当前值2、3时，x 1、x 2均投入生产，此时保持最优解结构不变的C 1、C 2取值范围为C 1≥1.5（C 2不变时），0≤C 2≤4（C 1不变时）。

运筹学网上作业作业名称：2022年秋季运筹学（本）网上作业1出卷人：SA作业总分：100通过分数：60起止时间：2022-11-114:34:26至2022-11-116:59:39学员姓名：dong某y学员成绩：95标准题总分：100标准题得分：95详细信息：题号:1题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5内容:图形:A、B、C、D、标准答案:B学员答案:A本题得分:0题号:2题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5内容:1915年谁首先推导出存贮论的经济批量公式A、ErlangB、HarriC、ShewhartD、Dantzig标准答案:B学员答案:B本题得分:5题号:3题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5内容:对于基B，令所有非基变量为0，满足A某=b的解，称为B所对应的A、可行解B、最优解C、基本解D、退化解标准答案:C学员答案:C本题得分:5题号:4题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5内容:原问题的检验数对应对偶问题的一个A、基本可行解B、最优解C、基本解D、不知标准答案:C学员答案:C本题得分:5题号:5题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5内容:图形:A、B、C、D、标准答案:C学员答案:C本题得分:5题号:6题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5内容:1917年谁首先提出了排队论的一些著名公式A、ErlangB、HarriC、ShewhartD、Dantzig标准答案:A学员答案:A本题得分:5题号:7题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5内容:某、Y分别是原问题和对偶问题的可行解，且C某=Yb，则某、Y分别是原问题和对偶问题的A、基本可行解B、最优解C、基本解D、不知标准答案:B学员答案:B本题得分:5题号:8题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5内容:线性规划的标准型中C称为A、技术向量B、价值向量C、资源向量D、约束矩阵标准答案:B学员答案:B本题得分:5题号:9题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5内容:管梅谷在1962年首先解决了哪类运筹学问题A、随机规划问题B、中国邮路问题C、欧拉图问题D、四色问题标准答案:B学员答案:B本题得分:5题号:10题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5内容:1947年谁得到了线性规划的单纯形法A、ErlangB、HarriC、ShewhartD、Dantzig标准答案:D学员答案:D本题得分:5题号:11题型:多选题（请在复选框中打勾，在以下几个选项中选择正确答案，答案可以是多个）本题分数:5内容:我国运筹学的应用是始于A、重工业B、建筑业C、纺织业D、服务业标准答案:BC学员答案:BC本题得分:5题号:12题型:多选题（请在复选框中打勾，在以下几个选项中选择正确答案，答案可以是多个）本题分数:5内容:研究模型有三种基本形式A、形象模型B、抽象模型C、模拟模型D、数学模型标准答案:ACD学员答案:ACD本题得分:5题号:13题型:多选题（请在复选框中打勾，在以下几个选项中选择正确答案，答案可以是多个）本题分数:5内容:运筹学研究问题的特点表现为A、综合性B、跨学科性C、实用性D、专业性标准答案:ABC学员答案:ABC本题得分:5题号:14题型:是非题本题分数:5内容:线性规划的最优基是唯一的。

运筹学课程上机实践要求及内容（2）一、实验教学的目的和要求目的：借助运筹学软件的强大功能，通过小组的充分讨论，对管理实践中的实际问题进行建模、求解，并对求解结果进行分析（特别是敏感性分析），进而激发学生的学习兴趣和热情，克服对课程学习的“恐惧感”。

要求：熟练掌握LINGO、WinQSB等软件的基本功能和基本语法结构，能用软件对运筹学问题进行求解和分析。

二、请于第1次-第6次上机时间及平时完成。

三、作业务请写清学号、姓名、专业、班级，上机作业格式请用老师提供的模版。

四、编写的代码请用记事本单独保存。

五、要求所有题目用LINGO和教材自带的求解软件各做一遍。

并分析解释求解的结果。

六、各题目中的A，B，C，D，E，F为参数，除特别规定外，请自行设定，各个同学参数值不能相同，若发现完全一致的，作业以零分计。

A=1，B=2，C=2，D=4，E=4，F=1第1题(线性规划)(1)介绍单纯型算法及其处理人工变量的两阶段法；(2)建立下列问题的数学模型并求解，讨论资源的影子价格；某造纸厂拟生产漂白松木浆、包装纸(水泥、松木包装纸、松木本色纸)、漂白桦木纸和胶版纸等四种产品，单位产品所需资源情况见表1，市场上胶版纸的需求量不超过6000吨。

(a)制订该造纸厂的生产计划；(b)若电的资源可用量下降10%，重新制订该造纸厂的生产计划。

(3)结合本题，谈谈你对线性规划的认识。

Hint: 若参数为5，5，5，5，5，5，则最优目标函数值为(a)167236800；(b)167236800。

解：(1)单纯形法是求解线性规划问题的通用方法。

单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。

因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。

如果问题无最优解也可用此法判别。

两阶段单纯形法也是一种人工变量法，它的算法可分为两个阶段：第一阶段，引入人工变量，构造一个具有标准基的新线性规划，求解这个新线性规划，其结果有两种可能：或者将原问题的约束方程组化成具有标准基的形式，或者提供信息，表明原问题没有可行解。

2023年运筹学大作业单纯性法与对偶单纯性法的比较目前，运筹学领域中的单纯性法和对偶单纯性法是两种最为常用的线性规划求解方法。

随着科技和工业的不断发展，未来的运筹学研究也将越来越受到人们的关注。

因此，在未来的2023年中，我们不仅需要掌握这两种方法的基本概念和原理，还需要深入的了解它们的比较和应用。

第一章单纯性法的基本原理单纯性法是一种常用的线性规划求解方法，其基本流程可以归纳为以下几个步骤：1. 确定一个基本可行解；2. 判断该基本可行解是否是最优解；3. 如果不是最优解，则选择一个入基变量和一个出基变量；4. 对出基变量进行互换，更新基本可行解；5. 重复执行步骤2至步骤4，直至得到最优解。

单纯性法的优点在于可快速地求得最优解，特别是在少数变量和简单约束的情况下，可以快速解决线性规划问题。

但是，当规模较大或者约束条件复杂时，单纯性法很可能会陷入循环，导致计算时间过长。

第二章对偶单纯性法的基本原理对偶单纯性法是单纯性法的一种扩展，其实质是对线性规划模型的对偶模型进行求解。

其基本流程可以归纳为以下几个步骤：1. 确定一个对偶基本可行解；2. 判断该对偶基本可行解是否是最优解；3. 如果不是最优解，则选择一个入基变量和一个出基变量；4. 对出基变量进行互换，更新对偶基本可行解；5. 重复执行步骤2至步骤4，直至得到最优解。

对偶单纯性法的优点在于可以避免陷入循环的情况，同时，还可以通过求解对偶问题来产生原问题的最优解。

第三章两种方法的比较从计算复杂度的角度来比较单纯性法和对偶单纯性法，很明显对偶单纯性法更加高效。

因为对偶单纯性法的目标函数和限制条件比原问题要少，因此需要的计算步骤相对更少。

但是，在实际操作中，对偶单纯性法的计算结果通常需要进行一次转换才能得到原问题的最优解。

从求解结果的角度来比较单纯性法和对偶单纯性法，也可以发现它们的区别。

在某些情况下，单纯性法得出的最优解不一定是方案的唯一最优解，而对偶单纯性法则可以直接得到原问题的唯一最优解。

中石油管道输气运输成本问题一、背景简介：中国石油天然气集团公司（简称中国石油集团，英文缩写：CNPC）是由中央直接管理的国有特大型央企，根据国务院机构改革方案，于1998年7月在原中国石油天然气总公司的基础上组建的特大型石油石化企业集团，系国家授权投资的机构和国家控股公司，是实行上下游、内外贸、产销一体化、按照现代企业制度运作，跨地区、跨行业、跨国经营的综合性石油公司。

2004年国内生产原油11176.1万吨，生产天然气286.6亿立方米，加工原油11077.5万吨；同时在海外获取权益原油产量1642.3万吨、天燃气产量25.9亿立方米。

全年实现销售收入5707亿元，实现利润1289亿元，实现利润在国内企业中位居榜首。

作为中国境内最大的原油、天然气生产、供应商，中国石油集团业务涉及石油天然气勘探开发、炼油化工、管道运输、油气炼化产品销售、石油工程技术服务、石油机械加工制造、石油贸易等各个领域，在中国石油、天然气生产、加工和市场中占据主导地位。

2008年，中国石油在美国《石油情报周刊》世界50家大石油公司综合排名中，位居第5位，在美国《财富》杂志2011年世界500强公司排名中居第6位，在《巴菲特杂志》2009年中国上市公司百强评选中，荣获“中国25家最受尊敬上市公司全明星奖”第一名。

在“2011中国企业500强”中，以营业收入14654.15亿元人民币列第2位。

在2013年荣获中国品牌价值研究院、中央国情调查委员会、焦点中国网联合发布的2013年度中国品牌500强。

进入新世纪新阶段，中国石油集团在国家大公司、大集团战略和有关政策的指导、支持下，正在实施一整套新的发展战略，瞄准国际石油同行业先进水平，加快建设主业突出、核心竞争力强的大型跨国石油企业集团，继续保持排名前列世界大石油公司地位。

二、运输问题成本实例分析1、问题提出中国天然气产业的快速发展仅是一个新阶段的开始。

从整个天然气上下游一体化的系统工程来看，中国天然气产业依然年轻。

运筹学作业（5）
习题1、清华大学运筹学（第三版）P112 4.2（2）
用图解法找出以下目标规划问题的满意解。

习题2、清华大学运筹学（第三版）P282 10.4（a）
用破圈法和避圈法求图中的最小树。

习题3、清华大学运筹学（第三版）P283 10.7图10-40
用课上介绍的逆推方法，求v1到v11的最短路径，标明路径，求出路长。

习题4：已知条件如表所示
p1：每周总利润不得低于10000元；
p2：因合同要求，A型机每周至少生产10台，B型机每周至少生产15台；
p3：希望工序Ⅰ的每周生产时间正好为150小时，工序Ⅱ的生产时间最好用足，甚至可适当加班。

试建立这个问题的目标规划模型并求解（可利用EXCEL求）。

思考题：在上题中，如果工序Ⅱ在加班时间内生产出来的产品，每台A型机减
少利润10元，每台B型机减少利润25元，并且工序Ⅱ的加班时间每周最多不超过30小时，这是p4级目标，试建立这个问题的目标规划模型并求解。

（此题下周四前会给出参考答案）。

运筹学大作业红牌罐头食品制造商一1、管理部门的目标是什么?在我们看来企业当以有限资源之最小获取利益之最大，也就是将“利润最大化”作为企业的管理目标。

利润代表了企业新创造的财富，利润越多，则说明企业的财富增加得越多，越接近企业的目标。

厂商从事生产或出售商品不仅要求获取利润，而且要求获取最大利润，厂商利润最大化原则就是产量的边际收益等于边际成本的原则。

2、管理部门需要知道什么?我们认为管理部门需要知道市场对我们产品的需求量、产品原料供应量及其他资源等对生产的限制、各个产品的售价、单位产品的人工成本、原料成本和净利润，以及该如何生产才能使利润达到最大。

我们需要知道公司本年度的工作计划，即产品的生产量（销售量）。

3、约束条件有哪些?在这个题目中我们所了解的约束条件主要有三个：一是番茄的数量的限制，总数是300万磅，而其中A级番茄是600000磅，B级番茄是2400000磅，我们在计算产品组合及数量的时候绝对不能超过这个量；二是需求的限制，题中明显给出了需求预测，所以这是生产时的上限，否则生产过多将会供过于求；三是产品质量的限制，题目中明确规定了罐装整番茄的最低输入质量要求为每磅8点，番茄汁为每磅6点，而番茄酱则为每磅5点，所以可完全用B级番茄来制作。

4、你认为红牌罐头食品制造商应生产什么?我们认为红牌罐头食品厂制造商应生产26667箱番茄汁、80000箱番茄酱，才能使利润最大化。

二1、整番茄、番茄酱和番茄汁各应生产多少？设整番茄，番茄汁和番茄酱所使用的A级番茄分别为X1，X2，X3磅，下面计算原料成本。

我们跟迈尔的想法一样，我们认为番茄成本应以质和量两种基础来确定，而不是仅仅依赖于量。

设：Z=每磅A级番茄的成本/美分Y=每磅B级番茄的成本/美分由题可知（600000磅*Z）+(2400000磅*Y)=（3000000磅*6）Z/9=Y/5解得：Z=9.32 Y=5.18所以A级番茄的成本为9.32美分每磅，B级番茄的成本为5.18美分每磅。

《运筹学》期末大作业一、建立线性规划模型。

（30分）某公司生产I、II两种产品，市场对I、II两种产品的需求量为：产品I在1—4月每月需10000件，5—9月每月30000件，10—12月每月100000件；产品II在3—9月每月15000件，其他月每月50000件。

该公司生产这两种产品成本为：产品I在1—5月内生产每件5元，6—12月内生产每件4.5元；产品II在1—5月内生产每件8元，6—12月内生产每件7元。

该公司每月生产这两种产品的能力总和不超过120000件。

产品I容积每件0.2立方米，产品II每件0.4立方米，该公司仓库容量为15000立方米，占用公司仓库每月每立方米库容需1元；如该公司仓库不足时，可从外面租借，租用外面仓库每月每立方米库容需1.5元。

试问在满足市场需求的情况下，该厂应如何安排生产，使总的生产加库存费用为最少？二、建立运输问题的表格模型。

（25分）某北方研究院有一、二、三三个区。

每年分别需要用煤3000、3000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。

供应能力分别为3500、4000吨，运价如下表：由于需大于供，经院研究决定一区供应量可减少0--400吨，二区必须满足需求量，三区供应量不少于1600吨，试求总费用为最低的调运方案。

三、建立线性多目标规划模型。

（25分）一个投资者决定在三个项目中投资，投资总额为100000元，这三个项目是储蓄、债券和股票。

预计每个投资项目的年均收益分别是4%、8%、16%。

投资者希望的目标是，第一优先级目标：至少得到9000元的年均收益；第二优先级目标：股票投资不少于债券和储蓄投资的总和；第三优先级目标：股票投资最少为20000元；第四优先级目标：储蓄投资应在15000元到20000元之间。

试问投资总额应如何分配？四、建立线性整数规划模型。

（20分）某汽车生产厂生产A1、A2、A3三种型号的汽车，已知各生产一台时的钢材、劳动力消耗和利润值，每月可供使用的钢材及劳动小时数如下表所示。

上海电力学院课程设计（大型作业）任务书（2012/2013 学年第1学期）课题名称运筹学大型作业课题代码141303501,141303513院（系）经济与管理学院专业信息管理与信息系统2011级班级2011131学生时间2013.1.14-18老师签名：赵文会，曹金龙教研室主任（系主任）签名：《运筹学》大型作业任务书一、内容1、基础训练——熟悉计算机软件Winqsb的子菜单和Lindo软件求解线性规划问题。

能用Winqsb软件求解运筹学中的常见数学模型。

完成以下内容：2、综合训练：劳动力资源分配问题的见面。

（见附录1）二、目的通过大型作业教学，培养学生利用所学的运筹学知识,根据具体的问题,进行综合分析、计算、评价的能力,以全面理解运筹学的思想和方法并能用于实际工作。

三、要求：1、总体要求全面结合运筹学的内容，根据自己对问题的理解,通过分析,建立合理的运筹学模型,能利用计算机软件Winqsb求出最优解,并能根据自己的理解给出合理分析。

2、形式要求所用的运筹学内容应先有简明阐述，再与具体问题相结合的结论。

整个作业力求全面、丰富，应用资料注明来源。

打印成稿。

四、组织形式基础训练单独完成；每人交一份打印稿作业（正反打印）。

综合训练分组进行，每小组4人(含4人)，小组完成时必须有明确的分工，必须有总负责人(总负责人也必须有自己的局部内容)。

综合训练部分小组提交一份打印稿作业。

任务书与大作业封面要在综合训练部分作业中。

注：小组完成的，应根据各人完成的具体工作,在大型作业的成品上注明,并按顺序排名。

五、考核形式大型作业的所有内容在1月18日结束之前交稿，教师可根据评阅情况的需要,指定部分作品进行答辩质疑与交流。

六、成绩评定1、大作业的总评成绩由三部分组成：基础训练+综合训练报告质量+平时表现（出席和答辩表现），具体比例为：40：30：30成绩由任课老师根据完成质量进行评定,以优\良\中\及格\不及格计分。

2.答辩表述要求答辩,如果由个人完成时由个人全面阐述,小组完成时应由一人总述(总述人也应有自己的局部内容)，各成员陈述自己完成部分。

课堂作业报告运 筹 学报告题目：货物配送问题(图论、整数规划) 专业班级： 报告人：货物配送问题（图论、整数规划）一、 问题重述1.1 背景知识本文研究的内容是以梦想连锁是一家主营鲜猪肉的肉类食品加工与销售公 司为背景而提出的。

针对该公司的具体情况，按照问题的要求，本文进行了以下 研究。

公司在全省县级及以上城镇设立销售连锁店。

全省县级及以上城镇地理位 置及道路连接见数据文件 1：全省交通网络数据.xlsx1.2 1.2.1 问题一要解决的问题目前公司现有 2 个生产基地、23 家销售连锁店，生产基地设在 120 号和 63 号城镇，为 23 家连锁店提供鲜猪肉，连锁店的日销售量见附录 1。

若运输成本 为 0.45 元/吨公里，请你为公司设计生产与配送方案，使运输成本最低。

1.2.2 问题二公司收集了近 5 年全省各城镇的鲜猪肉月度需求数据（文件 2：各城镇月度 需求数据.txt）请你分析各城镇需求特征，并预测未来数年，何时全省鲜猪肉需 求达到峰值，达到峰值时需求达到前 5 位和后 5 位的城镇是那些？1.2.3 问题三通过广告宣传等手段，未来几年公司在全省的市场占有率可增至 3 成左右 （各城镇对公司产品每日需求预测数据见文件 3：公司未来各城镇每日需求预测 数据.txt） ，调查还发现，公司产品的需求量与销售量并不完全一致，若在当地 （同一城镇）购买，则这一部分需求量与销售量相同，若在不足 10 公里的其他 城镇的销售连锁店购买， 则这一部分需求量只能实现一半 （成为公司产品销售量， 由于距离的原因，另一半需求转向购买其他公司或个体工商户的产品） ，而在超 过 10 公里的其他城镇的销售连锁店购买，销售量只能达到需求量的三成。

于是， 公司决定在各城镇增设销售连锁店，基于现有条件、成本等的考虑，原有的 23 家销售连锁店销售能力可在现有销售量的基础上上浮 20%，增设的销售连锁店销 售能力控制在每日 20 吨至 40 吨内， 并且要求增设的销售连锁店的销售量必须达 到销售能力的下限。

运筹大作业
文件说明
rosenbrock.m：函数的matlab符号函数实现。

naive_opt.m：负梯度法
F_R.m：Fletcher-Reeves共轭梯度法
P_R.m：Polak-Ribiere共轭梯度法
B_S.m：Beale-Sorenson共轭梯度法
程序说明
四个程序遵循相同的架构。

对于符号函数，matlab有gradient函数可以求符号函数的梯度，norm函数可以求符号函数的范数。

使用sub可以将符号函数转为数值函数。

之后严格遵循算法流程代入值求解即可。

调用方法
四个程序都不带参数。

直接调用即可获得图像，返回值为double的数值解。

求解结果
负梯度法
共迭代377次，最后结果为(0.999999999906938, 0.999999999790556)（数值解）
Fletcher-Reeves共轭梯度法
（第三个点因为其log为-inf因此无法被画出）
共迭代2次，最后结果为(1.000000000000001, 1.000000000000001)
Polak-Ribiere共轭梯度法
（第三个点因为其log为-inf因此无法被画出）
共迭代2次，最后结果为(1.000000000000001, 1.000000000000001)
Beale-Sorenson共轭梯度法
（第三个点因为其log为-inf因此无法被画出）
共迭代2次，最后结果为(1.000000000000001, 1.000000000000001)。

课程名称：对偶单纯形法1、教学目标在对偶单纯形法的学习过程中，理解和掌握对偶问题；综合运用线性规划和对偶原理知识对对偶单纯形法与单纯形法进行对比分析，了解单纯形法和对偶单纯形法的相同点和不同点，总结出各自的适用范围；掌握对偶单纯形法的求解过程；并能运用对偶单纯形法独立解决一些运筹学问题。

2、 教学内容1) 对偶单纯形法的思想来源(5min)2) 对偶单纯形法原理(5min)3) 总结对偶单纯形法的优点及适用情况(5min)4) 对偶单纯形法的求解过程(10min)5) 对偶单纯形法例题(15min)6) 对比分析单纯形法和对偶单纯形法(10min)3、 教学进程：1）讲述对偶单纯形法思想的来源：1954年美国数学家C.莱姆基提出对偶单纯形法（Dual Simplex Method）。

单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。

对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。

在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。

因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。

2）讲述对偶单纯形法的原理A.对偶问题的基本性质依照书第58页，我们先介绍一下对偶问题的六个基本性质：性质一：弱对偶性性质二：最优性。

如果（j=1...n)原问题的可行解，是其对偶问题可行解，且有=，则是原问题的最优解，是其对偶问题的最优解。

性质三：无界性。

如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）无可行解。

性质四：强对偶性。

如果原问题有最优解，则其对偶问题也一定有最优解。

性质五：互补松弛型。

在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。

性质六：线性规划的原问题及其对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w.B.对偶单纯形法（参考书p64页）设某标准形式的线性规划问题，对偶单纯形表中必须有-≤0（j=1...n),但(i=1...m)的值不一定为正，当对i=1...m，都有≥0时，表中原问题和对偶问题均为最优解，否则通过变换一个基变量，找出原问题的一个目标函数值较小的相邻的基解。

北京科技大学远程教育学院第二学期 《运筹学（36）》大作业模拟题一专业 班级 学号姓名_ _____一、选择题1．下列叙述正确的是( )A ．线性规划问题，若有最优解，则必是一个基变量组的可行基解B ．线性规划问题一定有可行基解C ．线性规划问题的最优解只能在极点上达到D ．单纯形法求解线性规划问题时每换基迭代一次必使目标函数值下降一次2．对于m 个发点、n 个收点的运输问题，叙述错误的是( ) A ．该问题的系数矩阵有m ×n 列 B ．该问题的系数矩阵有m+n 行 C ．该问题的系数矩阵的秩必为m+n-1D ．该问题的最优解必唯一3．某二维线性规划问题的可行域如题6图阴影所示，则该问题的最优解（ ） A.必在正方形的某个顶点达到 B.必在正方形内部达到 C.必在正方形外部达到 D.必在AB 边上达到4.关于运输问题的说法中错误．．的是（ ） A.最优运输方案未必唯一 B.必有最优运输方案C.运输方案的任何调整必会引起总运费的下降D.V ogel 法是一种比较简单的计算方法5．考虑某运输问题，其需求量和供应量相等，且供应点的个数为m ，需求点的个数是n 。

若以西北角法求得其初始运输方案，则该方案中数字格的数目应为（ ）A.（m+n ）个B.（m+n-1）个C.（m-n ）个D.（m-n+1）个6.在运输问题中如果总需求量小于总供应量，则求解时应（）A.虚设一些供应量B.虚设一个供应点C.根据需求短缺量，虚设多个需求点D.虚设一个需求点7．在线性规划中，设约束方程的个数为m,变量个数为n，m＜n时，可以把变量分为基变量和非基变量两部分，基变量的个数为m个，非基变量的个数为( C )A．m个 B.n个C.n-m个D.0个8．在求最大值的线性规划问题中，松弛变量在目标函数中的系数为（）A．0 B．极大的正数C．绝对值极大的负数D．极大的负数9.在求最小值的线性规划问题中，人工变量在目标函数中的系数为( )A.0B.极大的正数C.绝对值极大的负数D.极大的负数10.在线性规划中，设约束方程的个数为m,变量个数为n，m＜n时，我们可以把变量分为基变量和非基变量两部分。