运筹学作业王程130404026

《运筹学作业王程130404026》由会员分享，可在线阅读，更多相关《运筹学作业王程130404026（98页珍藏版）》请在装配图网上搜索。

1、 运筹学作业王程信管1302130404026目录运筹学作业1第一章 线性规划与单纯形法3第二章 线性规划的对偶理论与灵敏度分析24第三章 运输问题53第四章 目标规划63第五章 整数规划72第六章 非线性规划84第七章 动态规划93第八章 图与网络分析96第九章 网络计划98第一章 线性规划与单纯形法1.1分别用图解法和单纯形法求如下线性规划问题，指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解；当具有限最优解时，指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。解：图解法： 当经过点时，最小，且有无穷多个最优解。图解法： 该问题无可行解。图解法： 当经过点时，取得唯一最优解。

2、 单纯形法： 在上述问题的约束条件中分别参加松弛变量，化为标准型： 由线性规划问题的标准型可列出单纯初始形表逐步迭代，计算结果如下表所示：图解法： 当经过点时，取得唯一最优解。1.2将下述线性规划问题化成标准形式。1.3 对下述线性规划问题找出所有基解，指出哪些是基可行解，并确定最优解。98 / 98解：1该线性规划问题的全部基解见下表中的，打者为基可行解，注*者为最优解，z* =36。2该线性规划问题的标准形式为：其全部基解见下表中的，打者为基可行解，注*者为最优解，z*=5。1.4 题1.13中，假如目标函数变为，讨论的值如何变化，使该问题可行域的每个顶点依次使目标函数达到最优。解：由目标

3、函数可得：，其中。当 时，可行域的顶点A使目标函数达到最优；当 时，可行域的顶点B使目标函数达到最优；当 时，可行域的顶点C使目标函数达到最优；当或时，最优解为O点。1.6 分别用单纯形法中的大M法和两阶段法求解如下线性规划问题，并指出属哪一类解。其中M是一个任意大的正数，据此可列出初始单纯形表如下：cj23100MMiCBXBbx1x2x3x4x5x6x7MMx6x786134220-100-1100123cj-zj2-4M3-6M1-2MMM003Mx2x7221/45/2101/2-1-1/41/20-11/4-1/20184/5cj-zj32x2x19/54/501103/5-2/5-

4、3/101/51/10-2/53/10-1/5-1/102/5cj-zj0001/21/2M-1/2M-1/2由单纯形表的计算结果得：最优解,目标函数最优值X存在非基变量检验数，故该线性规划问题有无穷多最优解。 据此可列出单纯初始形表如下：cj0000011iCBXBbx1x2x3x4x5x6x711x6x786134220-100-1100123cj-zj-4-6-2110001x2x7221/45/2101/2-1-1/41/20-11/4-1/20184/5cj-zj00x2x19/54/501103/5-2/5-3/101/51/10-2/53/10-1/5-1/102/5cj-zj0

5、000011第一阶段求得的最优解，目标函数的最优值，因人工变量，所以是原线性规划问题的基可行解。于是可以进展第二阶段计算，将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，如下表：cj23100iCBXBbx1x2x3x4x532x2x19/54/501103/5-2/5-3/101/51/10-2/5cj-zj0001/21/2由表中计算可知，原线性规划问题的最优解，目标函数的最优值，由于存在非基变量检验数，故该线性规划问题有无穷多最优解。 其中M是一个任意大的正数，据此可列出单纯形表如下：cj101512000-MiCBXBbx1x2x3x4x5x6x700-Mx4x5x7

6、91555-52361115110001000-10019/5-5/2cj-zj10+2M15+M12+M00-M0100-Mx1x5x79/5247/51003/59-1/51/5163/51/51-2/501000-100193/27/3cj-zj1012-Mx1x3x73/23/21/210039/809/16-43/800103/161/16-7/16-1/801/16-3/8000-1001cj-zj0由单纯性表的最终表可以看出，所有非基变量检验数，且存在人工变量，故原线性规划问题无可行解。据此可列出单纯初始形表如下：cj0000001iCBXBbx1x2x3x4x5x6x7001x

7、4x5x791555-52361115110001000-10019/5-5/2cj-zj-2-1-100101001x1x5x79/5247/51003/59-1/51/5163/51/51-2/501000-100193/27/3cj-zj-1/53/5-2/51001x1x3x73/23/21/210039/809/16-43/800103/161/16-7/16-1/801/16-3/8000-1001cj-zj07/163/801第一阶段求得最优解，因人工变量，且非基变量检验数，所以原线性规划问题无可行解。 考虑下述线性规划问题：解：1上界对应的模型如下c，b取大，a取小 最优值上界

8、为：21；2下界对应的模型如下c，b取小，a取大 最优值下界为：6.4。1.7 某线性规划问题的初始单纯形表和用单纯形法迭代后得到表1-21，试求括弧中未知数的值。1.8 假如X,X(2)均为某线性规划问题的最优解，证明在这两点连线上的所有点也是该问题的最优解。1.9 考虑线性规划问题模型中为参数，要求： 组成两个新的约束，根据式和式，以为基变量，列出初始单纯形表；解： 在表中，假定，如此 为何值时，为问题的最优基； 在表中，假定，如此 为何值时，为问题的最优基。1.10 试述线性规划模型中“线性二字的含义，并用实例说明什么情况下线性的假设将被违背。答：线性的含义：一是严格的比例性，如生产某产

9、品对资源的消耗量和可获取的利润，同其生产数量严格成比例；二是可叠加性，如生产多种产品时，可获取的总利润使各项产品的利润之和，对某项资源的消耗量应等于各产品对该资源的消耗量之和；三是可分性，即模型中的变量可以取值为小数、分数或某一实数；四是确定性，指模型中的参数cj,aij,bi 均为确定的常数。 很多实际问题往往不符合上述条件，例如每件产品售价3元，但成批购置就可以得到折扣优惠。1.11 判断如下说法是否正确，为什么？ 含n个变量m个约束的标准型的线性规划问题，基解数恰好为个； 答：错误。根本解的个数=基的个数 线性规划问题的可行解如为最优解，如此该可行解一定为基可行解； 答：错误。当有唯一最

10、优解时，最优解是可行域顶点，对应根本可行解；当有无穷多最优解时，除了其中的可行域顶点对应根本可行解外，其余最优解不是根本可行解。 如线性规划问题存在可行域，如此可行域一定包含坐标的原点； 答：错误。如果约束条件中有一个约束所对应的区域不包含坐标的原点，如此即使有可行域，也不包含坐标的原点。 单纯形法迭代计算中，必须选取同最大检验数对应的变量作为换入基的变量。答：错误。假如此时最大检验数，可是，如此问题是无界解，计算完毕。1.12 线性规划问题,如是该问题的最优解，又为某一常数，分别讨论如下情况时最优解的变化。 目标函数变为； 目标函数变为； 目标函数变为，约束条件变为。解： 最优解不变； C为

11、常数时最优解不变，否如此可能发生变化； 最优解变为：X/。1.13 某饲养场饲养动物出售，设每头动物每天至少需要700g蛋白质、30g矿物质、100mg维生素。现有五种饲料可供选用，各种饲料每kg营养成分含量与单价如表1-22所示。要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。最优解为1.14 街邮局从周一到周日每天所需的职员人数如下表1-23所示。职员分别安排在周某一天开始上班，并连续工作5天，休息2天。要求确定： 该邮局至少应配备多少职员，才能满足值班需要； 因从周一开始上班的，双休日都能休息；周二或周日开始上班的，双休日只能有一天得到休息；其他时间开始上班的，两个双休日

12、都得不到休息，很不合理。因此邮局准备对每周上班的起始日进展轮换但从起始日开始连续上5天班的规定不变，问如何安排轮换，才能做到在一个星期每名职工享受到同等的双休日的休假天数； 该邮局职员中有一名领班，一名副领班。为便于领导，规定领班于每周一、三、四、五、六上班，副领班于一、二、三、五、日这5天上班。据此试重新对上述要求和建模和求解。对这23名职工分别编号，以23周为一个周期，这23名职工上班安排见下表。此时只需在每天人数中减去领班和副领班两人即可，重现建模如下：1.15 一艘货轮分前、中、后三个舱位，它们的容积与最大允许载重量如表1-24所示。现有三种货物待运，有关数据列于表1-25。 又为了舱

13、运安全，前、中、后舱的实际载重量大体积保持各舱最大允许载重量的比例关系。具体要求：前、后舱分别与中舱之间载重量比例的偏差不超过15%，前、后舱之间不超过10%。问该货轮应装载A、B、C各多少件运费收入为最大？试建立这个问题的线性规划模型。1.16 长城通信公司拟对新推出的一款手机收费套餐服务进展调查，以便进一步设计改良。调查对象设定为商界人士与大学生，要求：总共调查600人，其学生不少于250人；方式分调查和问卷调查，其中问卷调查人数不少于30%；对大学生调查80%以上应安排在周六或周日，对商界人士调查80%以上应安排在周一至周五；问卷调查时间不限。有关调查费用如表1-26所示，问该公司应如何

14、安排调查，使总的费用为最省。1.17 生产存储问题。某厂签订了5种产品i=1，5上半年的交货合同。各产品在第j月j=1，6的合同交货量Dij，该月售价sij、本钱价cij 与生产1件时所需工时aij 。该厂第j月的正常生产工时为tj，但必要时可加班生产，第j月允许的最多加班工时不超过tj，并且加班时间生产出来的产品每件本钱增加额外费用cij元。假如生产出来的产品当月不交货，每件库存1个月交存储费pi元。试为该厂设计一个保证完成合同交货，又使上半年预期盈利总额为最大的生产计划安排。1.18 宏银公司承诺为某建设项目从2003年起的4年中每年年初分别提供以下数额贷款：2003年100万元，2004

15、年150万元，2005年120万元，2006年110万元。以上贷款资金均需于2002年年底前筹集齐。但为了充分发挥这笔资金的作用，在满足每年贷款额情况下，可将多余资金分别用于如下投资项目： 于2003年年初购置A种债券，期限3年，到期后本息合计为投资额的140%，但限购60万元； 于2003年年初购置B种债券，期限2年，到期后本息合计为投资额的125%，且限购90万元； 于2004年年初购置C种债券，期限2年，到期后本息合计为投资额的130%，但限购50万元； 于每年年初将任意数额的资金存放于银行，年息4%，于每年年底取出。求宏银公司应如何运用好这笔筹集到的资金，使2002年年底需筹集到的资金

16、数额为最少。1.19 红豆服装厂新推出一款时装，据经验和市场调查，预测今后6个月对该款时装的需求为：1月3000件，2月3600件，3月4000件，4月4600件，5月4800件，6月5000件。生产每件需熟练工人工作4h，耗用原材料150元，售价为240元/件。该厂1月初有熟练工80人，每人每月工作160h。为适应生产需要，该厂可招收新工人培训，但培训一名新工人需占用熟练工人50h用于指导操作，培训期为一个月，完毕后即可上岗。熟练工人每月工资2000元，新工人培训期间给予生活补贴800元，转正后工资与生产效率同熟练工人。又熟练工人含转正一个月后的新工人每月初有2%因各种原因离职。该厂年初已加

17、工出400件该款时装作为库存，要求6月末存库1000件。又每月生产出来时装如不在当月交货，库存费用为每件每月10元。试为该厂设计一个满足各月与6月末库存要求，又使16月总收入为最大的劳动力安排方案。第二章 线性规划的对偶理论与灵敏度分析2.1 写出如下线性规划问题的对偶问题，并以对偶问题为原问题，再写出对偶的对偶问题。2.2 判断如下说法是否正确，并说明为什么。如果线性规划的原问题存在可行解，如此其对偶问题也一定存在可行解；答：错误。如果原问题是无界解，如此对偶问题无可行解。如果线性规划的对偶问题无可行解，如此原问题也一定无可行解；答：错误。如果对偶问题无可行解，也可能是因为原问题是无界解。在

18、互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值；答：错误。如果原问题是求极小，如此结论相反。任何线性规划问题具有唯一的对偶问题。答：正确。2.5 某求极大线性规划问题用单纯形法求解时的初始单纯形表与最终单纯形表如表2-30所示，求表中各括号未知数(a)(l)的值。解：l=1，k=0，a=2，c=3，h=-1/2，b=10，e=5/4，f=-1/2，d=1/4，g=-3/4，i=-1/4，j=-1/4.2.6 给出线性规划问题写出其对偶问题；用图解法求解对偶问题；利用的结果与根据对偶问题性质写出原问题最优解。解：其对偶问

19、题为： 图解法求解：3根据互补松弛型性质可以得到最优解2.7 给出线性规划问题写出其对偶问题；利用对偶问题性质证明原问题目标函数值。解：其对偶问题为：易得 是对偶问题的一个可行解，带入目标函数得，故原问题的目标函数值。2.8 线性规划问题试根据对偶问题性质证明上述线性规划问题目标函数值无界。2.9 给出线性规划问题要求：写出其对偶问题；原问题最优解为,试根据对偶理论，直接求出对偶问题的最优解。解：其对偶问题为：原问题最优解为，带入原问题，第4个约束不等式成立，故。又由于大于0，上面对偶问题前3个约束取等号，故得到最优解：。2.10 线性规划问题A和B如下：试分别写出同间的关系式。解：.2.11

20、 用对偶单纯形法求解如下线性规划问题。解：先将问题改写为： 列出单纯形表，用对偶单纯形法求解步骤进展计算过程如下：由上表可得原问题最优解为，代入目标函数得 。先将问题改写为： 列出单纯形表，用对偶单纯形法求解步骤进展计算过程如下：由上表可得原问题最优解为，代入目标函数得 。2.12 考虑如下线性规划问题：要求：写出其对偶问题；用对偶单纯形法求解原问题；用单纯形法求解其对偶问题；比照与中每步计算得到的结果。解：其对偶问题为：先将问题改写为 列出单纯形表，用对偶单纯形法求解步骤进展计算过程如下：由上表可得原问题最优解为，代入目标函数得 。用单纯形法求解其对偶问题：由上表可得对偶问题最优解为，代如目

21、标函数。2.13 线性规划问题：先用单纯形法求出最优解，再分析在如下条件单独变化的情况下最优解的变化。目标函数变为;约束右端项由变为；增添一个新的约束条件。解：先用单纯形法计算如下： 由上表可得最优解为当目标函数变为时，反映到最终单纯形表上如下表所示：因变量x2 的检验数大于零，故需继续用单纯形法迭代计算得下表：由上表可得最优解变为因有将其反映到最终单纯形表中如下表所示：由表可得最优解为先将原问题的最优解带入新增约束条件中，因故原问题最优解发生改变。给新增约束条件中参加松弛变量并规化得：以x6 为基变量，将上式反映到最终单纯形表中得下表：因上表中x1列不是单位向量，故需进展变换，得下表：因上表

22、中对偶问题为可行解，原问题为非可行解，故用对偶单纯性法迭代计算得下表：由上表可得最优解为2.14 给出线性规划问题当时用单纯形法求解得最终单纯形表见表2-31。试分析当时，围变化时的变化；当时，围变化时的变化。解：将反映到最终单纯形表中得下表：在上表中，当时，表中解为最优，且当时，变量的检验数0，用单纯形法迭代计算得下表：在上表中，当时，表中解为最优，且在第一个表中，当时，变量的检验数0，用单纯形法迭代计算得下表：在上表中，当时，表中解为最优，且因有将其反映到最终单纯形表中得下表：在上表中，当时，表中解为最优，且当时，表中基变量，这时可用对偶单纯形法继续迭代计算得下表：在上表中，当时，表中解为

23、最优，且在第一个表中，当时，表中基变量，这时可用对偶单纯形法继续迭代计算得下表：在上表中，当时，表中解为最优，且2.15 分析如下线性规划问题中，当变化时最优解的变化，并画出对的变化关系图。解：先令求得最优解，并将反映到最终单纯形表中，得下表：上表中，当时，表中解为最优，且，当时，变量的检验数0，用单纯形法迭代计算得下表：上表中，当时，表中解为最优，且，当时，变量的检验数0，用单纯形法迭代计算得下表：上表中，当时，表中解为最优，且；如下图明确了目标函数值随值变化的情况：先令求得最优解，并将反映到最终单纯形表中，得下表：上表中，当时，表中解为最优，且，当时，变量的检验数0，用单纯形法迭代计算得下

24、表：上表中，当时，表中解为最优，且，当时，变量的检验数0，用单纯形法迭代计算得下表：上表中，当时，表中解为最优，且；如下图明确了目标函数值随值变化的情况：令求解得最终单纯形表，又因有将其反映到最终单纯形表中，得下表：上表中当时，解为最优解且，当时，表中基变量将小于零，这时用对偶单纯形法继续求解得下表：表中当时为最优解，且，当时，原问题无可行解。如下图明确了目标函数值随值变化的情况：令求解得最终单纯形表，又因有将其反映到最终单纯形表中，得下表：上表中当时，解为最优解且，当时，表中基变量将小于零，这时用对偶单纯形法继续求解得下表：表中当时为最优解，且，当时，表中基变量将小于零，这时用对偶单纯形法继

25、续求解得下表：表中当时为最优解，且如下图明确了目标函数值随值变化的情况：2.16 某厂生产A、B、C三种产品，其所需劳动力、材料等有关数据见表2-32。要求：确定获利最大的产品生产计划；产品A的利润在什么围变动时，上述最优计划不变；如果设计一种新产品D，单件劳动力消耗为8h，材料消耗为2kg，每件可获利30元，问该种产品是否值得生产？如果原材料数量不增，劳动力不足时可以从市场购置，为1.8元/h。问：该厂要不要招收劳动力扩大生产，以购多少为宜？解：用x1，x2，x3分别表示该厂生产的三种产品A、B、C的数量，如此对该问题建模如下：解得最优生产计划为：；设产品A的利润为元，反映到最终单纯形表上如

26、下：为使上表中的解仍为最优解，应有解得 即产品A的利润在变动时，生产计划不变。设该公司生产x6 件产品D，有c6 =30，P6=8,2T 。将其反映到最终单纯形表中得下表：因，故用单纯形法继续迭代计算得下表：由上表可知产品D值得投入生产，最优解为。由可知劳动力的价格是2元，大于市场价格。故应该招收劳动力扩大生产。当招收劳动力为150h时，利润达到最大值3600元。2.17 线性规划问题：当时求解得最终单纯形表见表2-33。确定和的值；当时，在什么围变化上述最优解不变；当时，在什么围变化上述最优基不变。解：由题给可得：将目标函数的系数变化直接反映到最终单纯形表中，得下表：为使上表中的解仍为最优解

27、，应有解得 因有将其反映到最终单纯形表中，其b列数字为当时问题的最优基不变，解得2.18 某文教用品厂利用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂现有工人100人，每天白坯纸的供给量为30 000kg。如单独生产各种产品时，每个工人每天可生产原稿纸30捆，或日记本30打，或练习本30箱。原材料消耗为：每捆原稿纸用白坯纸10/3kg，每打日记本用白坯纸40/3kg，每箱练习本用白坯纸80/3kg。生产各种产品的赢利为：每捆原稿纸1元，每打日记本2元，每箱练习本3元。试决定：在现有生产条件下使该厂盈利最大的方案；如白坯纸供给量不变，而工人数量不足时可以从市场上招收临时工，临时工费用为每

28、人每天40元。问：该厂应否招临时工与招收多少人为宜？解：设该厂每天生产x1捆原稿纸，x2打日记本，x3箱练习本，如此对该问题建模如下：用单纯形表法计算如下所示：解得最优生产计划为：.设应招收临时工人，因有将其反映到最终单纯形表中，其b列数字为当时问题的最优基不变，解得 故该厂应从市场招收临时工200人/天，新计划只生产原稿纸9000捆。第三章 运输问题3.1 与一般线性规划的数学模型相比，运输问题的数学模型具有什么特征？答： 运输问题一定有有限最优解； 约束条件系数矩阵的元素只取0或1； 约束条件系数矩阵的每列有两个1，而且只有两个1.前m行中有一个1，后n行中有一个1；对于产销平衡的运输问题

29、，所有的约束都取等式。3.2 运输问题的基可行解应满足什么条件？是判断表3-26和表3-27中给出的调运方案可否作为表上作业迭代法时的基可行解？为什么？答：运输问题基可行解的要基变量的个数等于m+n-1。、表3-26和3-27中给出的方案都不是基可行解，因为数字格的数量不等于m+n-1。3.3 试对给出运输问题初始基可行解的最小元素法和Vogel法进展比拟，分析给出的解之质量不同的原因。答：最小元素法从最小的价格入手，一开始效果很好，但是到了最后因选择余地较少效果不好；Vogel法从产地和销地运价的级差来考虑问题，总体效果很好，但是方法较复杂。3.5 用表上作业法求解运输问题时，在什么情况下会

30、出现退化解？当出现退化解释应如何处理？答：当数字格的数量小于m+n-1时，相应的解就是退化解。如果出现了退化解，首先找到同时划去的行和列，然后在同时划去的行和列中的某个空格中填入数字0，只要数字格的数量保持在m+n-1个的水平即可。3.6 一般线性规划问题具备什么特征才能将其转化为运输问题求解，请举例说明。答：如果线性规划问题有“供和“需的关系，并且有相应的“费用，就可以考虑将线性规划问题转成运输问题求解。例如，生产满足需求的问题。3.4 简要说明用位势法对偶变量法求检验数的原理。解：原问题的检验数也可以利用对偶变量来计算：其中，ui和vj 就是原问题约束条件对应的对偶变量。由于原问题的基变量

31、的个数等于m+n-1，所以相应的检验数就等于0。即有：由于方程有m+n-1个，而变量有m+n个。所以上面的方程有无穷多个解。任意确定一个变量的值都可以通过方程求出一个解，然后再利用这个解就可以求出非基变量的检验数了。3.7 表3-28和表3-29分别给出了各产地和各销地的产量和销量，以与各产地至各销地的单位运价，试用表上作业法求最优解。解：1由最小元素法求得初始基可行解为，如下表：闭回路法求检验数，如下表：由于A2，B4的检验数小于0，故初始基可行解不是最优解。故改良解，直到各非基变量的检验数大于0，得最优解表为：2由于总产量13大于总销量10，需增加一假想销地B5，使其销量为3，如下表，此时

32、产销平衡。由最小元素法求得初始基可行解为，再进展屡次迭代运算求得最优解如下表：3.8 某企业和用户签订设备交货合同，该企业各季度的生产能力、每台设备的生产本钱和每季度末的交货量见表3-30，假如生产出的设备当季度不交货，每台设备每年度需支付保管维护费0.1万元，试问在遵守合同的条件下，企业应如何安排生产计划，才能使年消消耗用最低？解：设xij为第i季度生产而于第j季度交货的设备数量，可列出该运输问题的如下产销平衡表和单位运价表合一的表。表中D为虚设的需求地，M为任意大的正数，明确不允许后面季度的产量用于前面季度交货。表中小方格的单位运价为i季度生产于j季度交货的每台设备消耗的费用，为生产本钱和

33、保管费用之和。用最小元素法得出初始运输方案，如下表所示： 再经过迭代得最优解见下表： 即最优分配计划为：x11 =15，x22 =20，x23=15，x33=10，x34=20，总的消消耗用z*=913.5。3.9 某市有三个面粉厂，它们供给三个面食加工厂所需的面粉。各面粉厂的产量、各面食加工厂加工面粉的能力、各面食加工厂和各面粉厂之间的单位运价，均示于表3-31中。假定在第1、2和3面食加工厂制作单位面粉食品的利润分别为12、16和11，试确定使总效益最大的面粉分配计划假定面粉厂和面食加工厂都属于同一个主管单位。解：根据表3-31，用最小元素法得出初始运输方案，再经过迭代得最优解如下表所示：

34、即最优分配计划为：x1 =0，x3 =20，x1=15，x2=5，x2=20，总收益z*=425。因面粉厂的总产量大于食品厂的总需量，故面粉厂的产量中有10个单位面粉滞留。3.10 表3-32示出一个运输问题与它的一个解，试问：表中给出的解是否为最优解？请用位势法进展检验。假如价值系数C24 由1变为3，所给的解是否仍为最优解？假如不是，请求出最优解。假如所有价值系数均增加1，最优解是否改变？为什么？假如所有价值系数均乘以2，最优解是否改变？为什么？写出该运输问题的对偶问题，并说明二者最优解的关系。解：用位势法检验后算出各空格的检验数于下表：因为所有的检验数0，故表中给出的解即为最优解。假如价

35、值系数C24 由1变为3，用位势法求得检验数于下表所示：由于，故知表中解不再是最优解，且以为换入变量，它对应的闭合回路于下表所示：该闭合回路的偶数顶点位于格A1，B2、A3，B3和A2，B4，由于故应对解作如下调整：得到新的基可行解是：，其它为非基变量，这时的最优解。现再用位势法求这个新解各非基变量的检验数，结果示于下表：由于所有非基变量的检验数全为非负，故这个解为最优解。最优解不变，因为这样做不改变非基变量检验数的值。最优解不变，就如同将单位运价由元/500g变为元/kg，价格增加为原2倍一样，这样做不会改变非基变量检验数的符号。对偶问题如下： 其最优解是：3.11 1、2、3三个城市每年需

36、分别供给电力320个单位、250个单位和350个单位，由、两个电站提供，它们的最大可供电量分别为400个单位和450个单位，单位费用如表3-33所示。由于需要量大于可供量，决定城市1的供给量可减少030个单位，城市2的供给量不变，城市3的供给量不能少于270个单位，试求总费用最低的分配方案将可供电量用完。解：根据表3-33与，解得总费用最低的分配方案如下表所示：即最优分配方案为：电站供给城市1150单位，城市2250单位；电站供给城市1140单位，城市3310单位。第四章 目标规划4.1 假如用以下表达式作为目标规划的目标函数，其逻辑是否正确？为什么？答： 不正确，逻辑不合理； 正确，表示未达

37、到的目标值越大越好； 正确，表示离目标值正负偏差之和最小； 正确，表示超过目标值越大越好。4.2 用图解法解如下目标规划问题：解：解题过程见图4-1。求出的区域没有公共局部，如此取两个最接近的点A、B。可以解出A的坐标为40,70B坐标为55,40。可得A处，B处，比拟找出小者为点B。所以，问题的满意解为解题过程见图4-2：求出的区域没有公共局部，如此取两个最接近的点A、B。可以解出A的坐标为25,15B坐标为(30,70)。可得B处，A处，比拟找出小者为点A。所以，问题的满意解为4.3 用单纯形法解如下目标规划问题：解：解题过程的单纯形表见下表4-3：解题过程的单纯形表见下表4-3：4.4

38、某成品酒有三种商标红、黄、蓝，都是由三种原料酒等级、兑制而成。三种等级的原料酒的日供给量和本钱见表4-13，三种商标的本钱酒的兑制要求和售价见表4-14。决策者规定：首先是必须严格按规定比例兑制各商标的酒；其次是获利最大；最后是红商标的酒每天至少生产2000kg。试列出该问题的数学模型。解：设i=1,2,3表示原料酒、等级，j=1,2,3表红、黄、蓝酒，xij为j酒中使用第i种原料酒的数量，目标规划模型为：4.5 公司决定使用1000万元新产品开发基金开发A、B、C三种新产品。经预测估计，开发A、B、C三种新产品的投资利润率分别为5%、7%、10%。由于新开发产品有一定风险，公司研究后确定了如

39、下优先顺序目标：第一，A产品至少投资300万元；第二，为分散投资风险，任何一种新产品的开发投资不超过开发基金总额的35%；第三，应至少留有10%的开发基金，以备急用；第四，使总的投资利润最大。试建立投资分配方案的目标规划模型。解：设对A、B、C三种新产品分别开发投资x1,x2,x3万元，如此目标规划模型为：4.6 单位牛奶、牛肉、鸡蛋中的维生素与胆固醇含量等有关数据见表4-15.如果只考虑这三种食物，并且设立了如下三个目标：第一，满足三种维生素的每日最小需求量；第二，使每日摄入的胆固醇最少；第三，使每日购置食品的费用最少。要求建立问题的目标规划模型。4.7 金源公司生产三种产品，其整个计划期分

40、为三个阶段。现需编制生产计划，确定各个阶段各种产品的生产数量。计划受市场需求、设备台时、财务资金等方面条件的约束，有关数据如表4-16和表4-17所示。假设计划期初与期末各种产品的库存量皆为零。公司设定以下三个优先等级的目标：P1：与时供货，保证需求，尽量减少缺货，并且第三种产品与时供货的重要性相当于第一种、第二种产品的2倍；P2：尽量使各阶段加工设备不超负荷；P3：流动资金占用量不超过限额。要求建立目标规划的模型。第五章 整数规划5.1要在长度为l的一根圆钢上截取不同长度的零件毛坯，毛坯长度有n种，分别为aj1,2,，n。问每种毛坯应当各截取多少根，才能使圆钢残料最少，试建立本问题的数学模型

41、。5.2 篮球队需要选择5名队员组成出场阵容参加比赛。8名队员的身高与擅长位置见表5-11。出场阵容应满足以下条件：必须且只有一名中锋上场；至少有一名后卫；如1号或4号上场，如此6号不出场，反之如6号上场，如此1号和4号均不出场；2号和8号至少有一个不出场。问应当选择哪5名队员上场，才能使出场队员平均身高最高，试建立数学模型。5.3 一个旅行者要在其背包里装一些最有用的旅行物品。背包容积为a，携带物品总重量最多为b。现有物品m件，第i件物品体积为ai，重量为bii=1,2，m。为了比拟物品的有用程度，假设第i件物品的价值为cii=1,2，m。假如每件物品只能整件携带，每件物品都能放入背包中，并

42、且不考虑物品放入背包后相互的间隙。问旅行者应当携带哪几件物品，才能使携带物品的总价值最大，要求建立本问题的数学模型。5.4 分别用割平面法和用分支定界法解如下整数规划：解：割平面法：引入松弛变量，将问题化为标准形式，用单纯形法解其松弛问题，得最优单纯形表，见表1。由于b列各分数中 有最大小数局部3/4，故从表2中第三行产生割平面约束。割平面约束为引入松弛变量，得割平面方程将上式并入表1，然后利用对偶单纯形法求解，得表2。类似地，从表2中最后一个单纯形表的第二行产生割平面约束引入松弛变量，得割平面方程将上式并入表2中最后一个单纯形表，然后用对偶单纯形法解之，得表3。表3给出的最优解已满足整数要求

43、，因而，原整数规划问题的最优解为分支定界法：根据最终单纯形表可以得到，此时最优解为选x2进展分支，可以得到两个约束条件第一个约束条件：最终化为标准式，相当于增加了一个约束条件和变量x6z0000-1/4-1/3x220100-1/41x45/600013/2-4/3x18/310001/41/3x31/600100-2/3x1x2x3x4x5x6第二个约束条件：最终化为标准式，相当于增加了一个约束条件和变量x6z00-200-1x2 301000-1x4 -1001101/2x1 2102001x5 300-601-4x1x2x3x4x5x6无可行解继续对第一个分支解：引入松弛变量，将问题化为

44、标准形式，用单纯形法解其松弛问题，得最优单纯形表，见表4。表4给出的最优解已满足整数要求，因而，原整数规划问题的最优解为5.5 用隐枚举法解如下0-1型整数规划：解：在列出所有可能情况以后没有满足约束条件的解，所以没有可行解。解：求解过程可以列表表示见表6。所以，最优解 5.6 某城市可划分为11个防火区，已设有4个消防站，如图5-8所示。图5-8中，虚线表示该消防站可以在消防允许时间到达该防火区进展有效的消防灭火。问能否关闭假如干消防站，但仍不影响任何一个防火区的消防救灾工作提示：对每一个消防站建立一个表示是否将关闭的0-1变量。5.7 现有p个约束条件需要从中选择q个约束条件，试借助0-1

45、变量列出表达式。5.8 解如下系数矩阵的最小化指派问题：解：先对各行元素分别减去本行的最小元素，然后对各列也如此，即此时，中各行各列都已出现零元素。为了确定中的独立零元素，对加*，即由于只有4个独立零元素，少于系数矩阵阶数n=5，故需要确定能覆盖所有零元素的最少直线数目的集合。结果如下：为了使中未被直线覆盖的元素中出现零元素，将第二行和第三行中各元素都减去未被直线覆盖的元素中的最小元素1，但这样一来，第一列出现了负元素。为了消除负元素，再对第一列各元素分别加上1，即回到步骤2，对加*：中已有5个独立零元素，故可确定指派问题的最优指派方案。即最优解为解：先对各行元素分别减去本行的最小元素，然后对

46、各列也如此，即此时，中各行各列都已出现零元素。为了确定中的独立零元素，对加*，即中已有6个独立零元素，故可确定指派问题的最优指派方案。即最优解为5.9 需要分派5人去做5项工作，每人做各项工作的能力评分见表5-11。应如何分派，才能使总的得分最大？试分别用匈牙利法和表上作业法求解。解：匈牙利法：先对各行元素分别减去本行的最小元素，然后对各列也如此，即此时，中各行各列都已出现零元素。为了确定中的独立零元素，对加*，即由于只有3个独立零元素，少于系数矩阵阶数n=5，故需要确定能覆盖所有零元素的最少直线数目的集合。结果如下：为了使中未被直线覆盖的元素中出现零元素，将第四、五行中各元素都减去未被直线覆

47、盖的元素中的最小元素0.1，但这样一来，第五列出现了负元素。为了消除负元素，再对第五列各元素分别加上0.1，即回到步骤2，对加*：中已有5个独立零元素，故可确定最优解为表上作业法：用最小元素法求最优解，可以把人员看成产地，业务看成销地，各地产量和销地均为1，于是转化为运输问题。5.10 上题的指派问题也可用分支定界法求解，试说明解题思路。答：用分支定界法时，先根据表列出线性规划模型：例如先不考虑每人完成一项任务的约束，按照谁完成的多进展分配。当不满足问题要求时，按A1， A5中指定1人完成B1，其余 4人再按得分多的进展分配，这样得5个分支。如5个分支均非可行解时，可选一个边界值最大分支，并指

48、定剩下4人中的1人完成任务B2，继续分支，依次进展。5.11 考虑如下问题：式中，为整数值，且的值只能等于0、1、4和6.请用一等价的整数规划模型来表达这个问题。如果在目标函数中，用来代替，请相应地修改的答案。5.12 卡车送货问题覆盖问题。龙运公司目前必须向5家用户送货，需在用户A处卸下1个单位重量的货物，在用户B处卸下2个单位重量的货物，在用户C处卸下3个单位重量的货物，在用户D处卸下4个单位重量的货物，在用户E处卸下8个单位重量的货物。公司有各种卡车四辆：1号车载重量能力为2个单位，2号车载重能力为6个单位，3号车载重能力为8个单位，4号车载重能力为11个单位。每辆车只运货一次，卡车j的

49、一次运费为cj。假定一辆卡车不能同时给用户A和C二者送货；同样，也不能同时给用户B和D二者送货。请列出一个整数规划模型表达式，以确定装运全部货物应如何配置卡车，使其运费为最小。如果卡车j只要给用户i运货时需收附加费Kij同卸货量无关，试述应如何修改这一表达式。第六章 非线性规划6.1试就以下各方面对非线性规划与线性规划加以比拟：1数学模型:线性规划问题的目标函数和约束条件都是其自变量的线性函数。非线性规划问题的目标函数和约束条件中包含非线性函数。2对自变量要求：对自变量的要求，不论是非线性还是线性规划问题都要求在约束条件确定的可行域，并且是大于等于0的。3可行域：都是根据约束条件所确定的。4最

50、优解集：满足约束条件和目标函数的。6.2如何判定函数的凹凸性？说明各种判定方法的适用性和优缺点。答：判定函数凹凸性，有两个条件：1一阶条件：为上的凸凹函数的充要条件是：对任意不同两点和恒有假如式子为严格不等式，它就是严格凸凹函数的充要条件。2二阶条件：假如的黑塞矩阵都是正定负定的，如此为严格的凸函数凹函数。适用性：所给的函数是可微的。优点：不用根据凸凹函数的定义计算函数值来判断是否为凸凹函数。缺点：为了计算函数的梯度和黑塞矩阵需要求一阶和二阶偏导。6.3说明一维搜索的根本概念，试比拟斐波那契法与0.618法。一维搜索还有哪些其他方法？答：一维搜索是沿某一直线方向寻求目标函数极小点的方法，用于求

51、解单变量的无约束极值问题。选择初始近似点，按照某种规如此确定一移动方向，在此方向上移动到下一点，并使，检查所得的点是否满足要求的精度，如满足要求，如此停止运算，就是所求的近似最优解；假如不满足要求，如此在处确定新的移动方向，并在此方向上移动到下一点，再检查，这样继续下去，直至满足要求的精度为止。斐波那契法与0.618法比拟：斐波那契法和0.618法都是1先根据区间缩短的相对精度算出试点个数。2选取前两个试点的位置斐波那契法： 0.618法的缩短率为0.618。3计算函数值，并比拟它们的大小。4用计算试点的一般公式继续计算。5当进展到，斐波那契法是计算出，以函数值较小者为近似极小点。0.618法

52、同理。6.4说明梯度法、牛顿法的根本原理，并对这两种方法的迭代步骤、适用围和优缺点加以比照。答：梯度法和牛顿法都是用来求无约束极值问题，根本原理：均是先找一初始点，然后确定步长和搜索方向，一步步迭代。梯度法的迭代步骤：1确定一个初始点和允许误差，令2计算和，假如，停止迭代，得近似点和近似极小值；否如此，转下一步。3做一维搜索：并计算，然后令转回第2步。牛顿法步骤：对于正定二次函数，从任意近似点出发，沿方向搜索，以1为步长，迭代一步即可达极小点。比拟：迭代步骤：梯度法的搜索方向为负梯度方向，牛顿法为方向。而且梯度法要迭代很屡次直到梯度的式小于误差。牛顿法只需要迭代一步。使用围：梯度法和牛顿法都要

53、求目标函数具有一阶连续偏导数存在极小点。牛顿法还要求目标函数为正定二次函数。优缺点：梯度法迭代时要不断计算梯度和步长这样容易计算错误造成后面的结果错误。牛顿法虽然只需要进展一次迭代可是有局限，因为它要求目标函数为正定二次函数，而且求搜索方向时需要先找出对称矩阵。6.5说明以下概念，并绘图加以解释：1起作用约束：对某一约束条件来说，满足它有两种情况：一种情况这时不在由这个约束条件形成的可行域边界上此时称这一约束为点的不起作用约束。另一情况是，这时在由这个约束条件形成的可行域边界上，此时称这一约束为点的起作用约束。2下降方向：设，对某一方向P来说，假如存在实数，使任意的均有下式成立：就称方向P为点

54、的一个下降方向。3可行方向：设为任一可行点，对某一方向P来说，假如存在实数，使任意的均有下式成立：就称方向P为点的一个可行方向。4可行下降方向：假如点的某个方向P，该点既是的可行方向，又是该点的下降方向就称它为这个点的可行下降方向。5库恩-塔克条件：设是非线性规划的局部极小点，和在点处有一阶连续偏导数，而且处的所有起作用约束的梯度线性无关，如此存在数使6.6试举出一适当的经济问题的实例在简要分析的根底上写出其非线性规划的数学模型。答：某公司经营两种设备，1设备每件售价50元，2设备每件售价450元。售出一件1设备所需营业时间平均是2小时；售出一件2设备需要小时，其中是2设备的售出数量。该公司在

55、这段时间总营业时间1000小时，试决定使营业额最大的营业计划。数学模型:6.7说明罚函数法和障碍函数法的根本原理，其各自适用条件如何？怎样将它们联合起来应用？答：罚函数又称外点法，是从可行域的外部趋于原非线性规划问题的极小点。障碍函数法又称点法。与罚函数法不同，它要求迭代过程始终在可行域部进展。外点法和点法结合起来使用的话，对等式约束和当前不被满足的不等式约束是用罚函数法；对所满足的那些不等式约束，使用障碍函数法。6.8某工地有4个工点，各工点的位置与对混凝土的需要量列入表6-2，现需建一中心混凝土搅拌站，以供给各工点所需要的混凝土，要求混凝土的总运输量运量*运距最小，试决定搅拌站的位置。要求分别考虑以下两种情况：1搅拌站到各工点的道路均为直线；2道路为互相垂直或平行的网络。表6-2答：12试建立数学模型并说明计算过程。6.10对凸规划进展直观说明，并判定下述非线性规划是否为凸规划：1答：目标函数的黑塞矩阵为：为正定，所以为凸函数。约束条件黑塞矩阵为：为正定，所以为凸函数。约束条件为线性函数，可以把它看成凸函数。目标函数和约束条件的函数均为凸函数，所以为凸规划。2答：目标函数的黑塞矩阵为：为正定，所以为凸函数。约束条件黑塞矩阵为：为正定，所以为凸函数。约束条件和均为线性函数，可以把它们都看成凸函数。目标函数和约束条件的函数均为凸函数，所以为凸规划。在区间0,10上的极小点，