运筹学作业王程130404026.doc

《运筹学作业王程130404026.doc》由会员分享，可在线阅读，更多相关《运筹学作业王程130404026.doc（98页珍藏版）》请在三一办公上搜索。

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

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

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/50

4、1103/5-2/5-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-

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

6、x6x700-Mx4x5x791555-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 由单纯性表的最终表可以看出，所有非基变量检验数 ，且存在人工变量 ，故原线性规划问题无可行解。据此可列出单纯初始形表如下：cj0000001iCBXBbx

7、1x2x3x4x5x6x7001x4x5x791555-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-zj0 7/163/801 第一阶段求得最优解，因人工变量 ，且非基变量检验数，所以原线性规划问题无可行解。1.5 考虑下述线性规划问题： 解：（

8、1）上界对应的模型如下（c，b取大，a取小） 最优值（上界）为：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 线性规划问题,如是该问题的最优解，又为某一常数，分别讨论下列情况时最优解的变化。 目标函数

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

12、能休息；周二或周日开始上班的，双休日内只能有一天得到休息；其他时间开始上班的，两个双休日都得不到休息，很不合理。因此邮局准备对每周上班的起始日进行轮换（但从起始日开始连续上5天班的规定不变），问如何安排轮换，才能做到在一个星期内每名职工享受到同等的双休日的休假天数； 该邮局职员中有一名领班，一名副领班。为便于领导，规定领班于每周一、三、四、五、六上班，副领班于一、二、三、五、日这5天上班。据此试重新对上述要求和建模和求解。 对这23名职工分别编号， ，以23周为一个周期，这23名职工上班安排见下表。 此时只需在每天人数中减去领班和副领班两人即可，重现建模如下：1.15 一艘货轮分前、中、后三个

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

14、周六或周日，对商界人士电话调查80%以上应安排在周一至周五；问卷调查时间不限。已知有关调查费用如表1-26所示，问该公司应如何安排调查，使总的费用为最省。1.17 生产存储问题。某厂签订了5种产品（i=1，5）上半年的交货合同。已知各产品在第j月（j=1，6）的合同交货量Dij ，该月售价sij 、成本价cij 及生产1件时所需工时aij 。该厂第j月的正常生产工时为tj，但必要时可加班生产，第j月允许的最多加班工时不超过tj，并且加班时间内生产出来的产品每件成本增加额外费用cij元。若生产出来的产品当月不交货，每件库存1个月交存储费pi元。试为该厂设计一个保证完成合同交货，又使上半年预期盈利

15、总额为最大的生产计划安排。1.18 宏银公司承诺为某建设项目从2003年起的4年中每年年初分别提供以下数额贷款：2003年100万元，2004年150万元，2005年120万元，2006年110万元。以上贷款资金均需于2002年年底前筹集齐。但为了充分发挥这笔资金的作用，在满足每年贷款额情况下，可将多余资金分别用于下列投资项目： 于2003年年初购买A种债券，期限3年，到期后本息合计为投资额的140%，但限购60万元； 于2003年年初购买B种债券，期限2年，到期后本息合计为投资额的125%，且限购90万元； 于2004年年初购买C种债券，期限2年，到期后本息合计为投资额的130%，但限购50

16、万元； 于每年年初将任意数额的资金存放于银行，年息4%，于每年年底取出。求宏银公司应如何运用好这笔筹集到的资金，使2002年年底需筹集到的资金数额为最少。1.19 红豆服装厂新推出一款时装，据经验和市场调查，预测今后6个月对该款时装的需求为：1月3000件，2月3600件，3月4000件，4月4600件，5月4800件，6月5000件。生产每件需熟练工人工作4h，耗用原材料150元，售价为240元/件。该厂1月初有熟练工80人，每人每月工作160h。为适应生产需要，该厂可招收新工人培训，但培训一名新工人需占用熟练工人50h用于指导操作，培训期为一个月，结束后即可上岗。熟练工人每月工资2000元

17、，新工人培训期间给予生活补贴800元，转正后工资与生产效率同熟练工人。又熟练工人（含转正一个月后的新工人）每月初有2%因各种原因离职。已知该厂年初已加工出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

19、，i=-1/4，j=-1/4.2.6 给出线性规划问题 写出其对偶问题；用图解法求解对偶问题；利用的结果及根据对偶问题性质写出原问题最优解。解：其对偶问题为： 图解法求解： （3）根据互补松弛型性质可以得到最优解 2.7 给出线性规划问题 写出其对偶问题；利用对偶问题性质证明原问题目标函数值 。解：其对偶问题为： 易得 是对偶问题的一个可行解，带入目标函数得 ，故原问题的目标函数值。2.8 已知线性规划问题 试根据对偶问题性质证明上述线性规划问题目标函数值无界。 2.9 给出线性规划问题 要求：写出其对偶问题；已知原问题最优解为,试根据对偶理论，直接求出对偶问题的最优解。 解：其对偶问题为：

20、已知原问题最优解为，带入原问题，第4个约束不等式成立，故。又由于大于0，上面对偶问题前3个约束取等号，故得到最优解：。2.10 已知线性规划问题A和B如下： 试分别写出同间的关系式。解： .2.11 用对偶单纯形法求解下列线性规划问题。 解：先将问题改写为： 列出单纯形表，用对偶单纯形法求解步骤进行计算过程如下：由上表可得原问题最优解为，代入目标函数得 。先将问题改写为： 列出单纯形表，用对偶单纯形法求解步骤进行计算过程如下：由上表可得原问题最优解为，代入目标函数得 。2.12 考虑如下线性规划问题： 要求：写出其对偶问题；用对偶单纯形法求解原问题；用单纯形法求解其对偶问题；对比与中每步计算得

21、到的结果。解：其对偶问题为： 先将问题改写为 列出单纯形表，用对偶单纯形法求解步骤进行计算过程如下：由上表可得原问题最优解为，代入目标函数得 。 用单纯形法求解其对偶问题：由上表可得对偶问题最优解为，代如目标函数。2.13 已知线性规划问题：先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。 目标函数变为; 约束右端项由变为； 增添一个新的约束条件。解：先用单纯形法计算如下： 由上表可得最优解为 当目标函数变为时，反映到最终单纯形表上如下表所示：因变量x2 的检验数大于零，故需继续用单纯形法迭代计算得下表：由上表可得最优解变为 因有 将其反映到最终单纯形表中如下表所示：由表

22、可得最优解为先将原问题的最优解带入新增约束条件中，因故原问题最优解发生改变。给新增约束条件中加入松弛变量并规范化得： 以x6 为基变量，将上式反映到最终单纯形表中得下表：因上表中x1列不是单位向量，故需进行变换，得下表：因上表中对偶问题为可行解，原问题为非可行解，故用对偶单纯性法迭代计算得下表：由上表可得最优解为2.14 给出线性规划问题当时用单纯形法求解得最终单纯形表见表2-31。试分析 当时，范围内变化时的变化； 当时，范围内变化时的变化。解：将反映到最终单纯形表中得下表：在上表中，当时，表中解为最优，且当时，变量的检验数0，用单纯形法迭代计算得下表：在上表中，当时，表中解为最优，且在第一

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

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

25、目标函数值随值变化的情况： 令求解得最终单纯形表，又因有 将其反映到最终单纯形表中，得下表： 上表中当时，解为最优解且，当时，表中基变量将小于零，这时用对偶单纯形法继续求解得下表： 表中当时为最优解，且，当时，表中基变量将小于零，这时用对偶单纯形法继续求解得下表： 表中当时为最优解，且下图表明了目标函数值随值变化的情况： 2.16 某厂生产A、B、C三种产品，其所需劳动力、材料等有关数据见表2-32。要求：确定获利最大的产品生产计划；产品A的利润在什么范围内变动时，上述最优计划不变；如果设计一种新产品D，单件劳动力消耗为8h，材料消耗为2kg，每件可获利30元，问该种产品是否值得生产？如果原材

26、料数量不增，劳动力不足时可以从市场购买，为1.8元/h。问：该厂要不要招收劳动力扩大生产，以购多少为宜？解：用x1，x2，x3分别表示该厂生产的三种产品A、B、C的数量，则对该问题建模如下： 解得最优生产计划为：；设产品A的利润为元，反映到最终单纯形表上如下：为使上表中的解仍为最优解，应有 解得 即产品A的利润在内变动时，生产计划不变。设该公司生产x6 件产品D，有c6 =30，P6=（8,2）T 。 将其反映到最终单纯形表中得下表：因，故用单纯形法继续迭代计算得下表： 由上表可知产品D值得投入生产，最优解为。由可知劳动力的价格是2元，大于市场价格。故应该招收劳动力扩大生产。当招收劳动力为15

27、0h时，利润达到最大值3600元。2.17 已知线性规划问题： 当时求解得最终单纯形表见表2-33。确定和的值；当时，在什么范围内变化上述最优解不变；当时，在什么范围内变化上述最优基不变。解：由题给可得： 将目标函数的系数变化直接反映到最终单纯形表中，得下表：为使上表中的解仍为最优解，应有 解得 因有 将其反映到最终单纯形表中，其b列数字为 当时问题的最优基不变，解得2.18 某文教用品厂利用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂现有工人100人，每天白坯纸的供应量为30 000kg。如单独生产各种产品时，每个工人每天可生产原稿纸30捆，或日记本30打，或练习本30箱。已知原材料

28、消耗为：每捆原稿纸用白坯纸10/3kg，每打日记本用白坯纸40/3kg，每箱练习本用白坯纸80/3kg。已知生产各种产品的赢利为：每捆原稿纸1元，每打日记本2元，每箱练习本3元。试决定：在现有生产条件下使该厂盈利最大的方案；如白坯纸供应量不变，而工人数量不足时可以从市场上招收临时工，临时工费用为每人每天40元。问：该厂应否招临时工及招收多少人为宜？解：设该厂每天生产x1捆原稿纸，x2打日记本，x3箱练习本，则对该问题建模如下： 用单纯形表法计算如下所示： 解得最优生产计划为：.设应招收临时工人，因有 将其反映到最终单纯形表中，其b列数字为 当时问题的最优基不变，解得 故该厂应从市场招收临时工2

29、00人/天，新计划只生产原稿纸9000捆。第三章 运输问题3.1 与一般线性规划的数学模型相比，运输问题的数学模型具有什么特征？答： 运输问题一定有有限最优解； 约束条件系数矩阵的元素只取0或1； 约束条件系数矩阵的每列有两个1，而且只有两个1.前m行中有一个1，后n行中有一个1；对于产销平衡的运输问题，所有的约束都取等式。3.2 运输问题的基可行解应满足什么条件？是判断表3-26和表3-27中给出的调运方案可否作为表上作业迭代法时的基可行解？为什么？答：运输问题基可行解的要求是基变量的个数等于m+n-1。、表3-26和3-27中给出的方案都不是基可行解，因为数字格的数量不等于m+n-1。3.

30、3 试对给出运输问题初始基可行解的最小元素法和Vogel法进行比较，分析给出的解之质量不同的原因。答：最小元素法从最小的价格入手，一开始效果很好，但是到了最后因选择余地较少效果不好；Vogel法从产地和销地运价的级差来考虑问题，总体效果很好，但是方法较复杂。3.5 用表上作业法求解运输问题时，在什么情况下会出现退化解？当出现退化解释应如何处理？答：当数字格的数量小于m+n-1时，相应的解就是退化解。如果出现了退化解，首先找到同时划去的行和列，然后在同时划去的行和列中的某个空格中填入数字0，只要数字格的数量保持在m+n-1个的水平即可。3.6 一般线性规划问题具备什么特征才能将其转化为运输问题求

31、解，请举例说明。答：如果线性规划问题有“供”和“需”的关系，并且有相应的“费用”，就可以考虑将线性规划问题转成运输问题求解。例如，生产满足需求的问题。3.4 简要说明用位势法（对偶变量法）求检验数的原理。解：原问题的检验数也可以利用对偶变量来计算： 其中，ui和vj 就是原问题约束条件对应的对偶变量。由于原问题的基变量的个数等于m+n-1，所以相应的检验数就等于0。即有： 由于方程有m+n-1个，而变量有m+n个。所以上面的方程有无穷多个解。任意确定一个变量的值都可以通过方程求出一个解，然后再利用这个解就可以求出非基变量的检验数了。3.7 表3-28和表3-29分别给出了各产地和各销地的产量和

32、销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。解：（1）由最小元素法求得初始基可行解为，如下表：闭回路法求检验数，如下表：由于（A2，B4）的检验数小于0，故初始基可行解不是最优解。故改进解，直到各非基变量的检验数大于0，得最优解表为：（2）由于总产量13大于总销量10，需增加一假想销地B5，使其销量为3，如下表，此时产销平衡。由最小元素法求得初始基可行解为，再进行多次迭代运算求得最优解如下表：3.8 某企业和用户签订设备交货合同，已知该企业各季度的生产能力、每台设备的生产成本和每季度末的交货量（见表3-30），若生产出的设备当季度不交货，每台设备每年度需支付保管维护费0.1万元

33、，试问在遵守合同的条件下，企业应如何安排生产计划，才能使年消耗费用最低？解：设xij为第i季度生产而于第j季度交货的设备数量，可列出该运输问题的如下产销平衡表和单位运价表合一的表。表中D为虚设的需求地，M为任意大的正数，表明不允许后面季度的产量用于前面季度交货。表中小方格内的单位运价为i季度生产于j季度交货的每台设备消耗的费用，为生产成本和保管费用之和。用最小元素法得出初始运输方案，如下表所示： 再经过迭代得最优解见下表： 即最优分配计划为：x11 =15，x22 =20，x23=15，x33=10，x34=20，总的消耗费用z*=913.5。3.9 某市有三个面粉厂，它们供给三个面食加工厂所

34、需的面粉。各面粉厂的产量、各面食加工厂加工面粉的能力、各面食加工厂和各面粉厂之间的单位运价，均示于表3-31中。假定在第1、2和3面食加工厂制作单位面粉食品的利润分别为12、16和11，试确定使总效益最大的面粉分配计划（假定面粉厂和面食加工厂都属于同一个主管单位）。解：根据表3-31，用最小元素法得出初始运输方案，再经过迭代得最优解如下表所示：即最优分配计划为：x1 =0，x3 =20，x1=15，x2=5，x2=20，总收益z*=425。因面粉厂的总产量大于食品厂的总需量，故面粉厂的产量中有10个单位面粉滞留。3.10 表3-32示出一个运输问题及它的一个解，试问：表中给出的解是否为最优解？

35、请用位势法进行检验。若价值系数C24 由1变为3，所给的解是否仍为最优解？若不是，请求出最优解。若所有价值系数均增加1，最优解是否改变？为什么？若所有价值系数均乘以2，最优解是否改变？为什么？写出该运输问题的对偶问题，并说明二者最优解的关系。解：用位势法检验后算出各空格的检验数于下表：因为所有的检验数0，故表中给出的解即为最优解。若价值系数C24 由1变为3，用位势法求得检验数于下表所示：由于，故知表中解不再是最优解，且以为换入变量，它对应的闭合回路于下表所示：该闭合回路的偶数顶点位于格（A1，B2）、（A3，B3）和（A2，B4），由于 故应对解作如下调整： 得到新的基可行解是：，其它为非基

36、变量，这时的最优解。现再用位势法求这个新解各非基变量的检验数，结果示于下表：由于所有非基变量的检验数全为非负，故这个解为最优解。最优解不变，因为这样做不改变非基变量检验数的值。最优解不变，就如同将单位运价由元/500g变为元/kg，价格增加为原2倍一样，这样做不会改变非基变量检验数的符号。对偶问题如下： 其最优解是： 3.11 1、2、3三个城市每年需分别供应电力320个单位、250个单位和350个单位，由、两个电站提供，它们的最大可供电量分别为400个单位和450个单位，单位费用如表3-33所示。由于需要量大于可供量，决定城市1的供应量可减少030个单位，城市2的供应量不变，城市3的供应量不

37、能少于270个单位，试求总费用最低的分配方案（将可供电量用完）。解：根据表3-33与已知，解得总费用最低的分配方案如下表所示：即最优分配方案为：电站供给城市1150单位，城市2250单位；电站供给城市1140单位，城市3310单位。第四章 目标规划4.1 若用以下表达式作为目标规划的目标函数，其逻辑是否正确？为什么？ 答： 不正确，逻辑不合理； 正确，表示未达到的目标值越大越好； 正确，表示离目标值正负偏差之和最小； 正确，表示超过目标值越大越好。4.2 用图解法解下列目标规划问题： 解：解题过程见图4-1。求出的区域没有公共部分，则取两个最接近的点A、B。可以解出A的坐标为（40,70）B坐

38、标为（55,40）。可得A处，B处，比较找出小者为点B。所以，问题的满意解为解题过程见图4-2：求出的区域没有公共部分，则取两个最接近的点A、B。可以解出A的坐标为（25,15）B坐标为(30,70)。可得B处，A处，比较找出小者为点A。所以，问题的满意解为4.3 用单纯形法解下列目标规划问题： 解：解题过程的单纯形表见下表4-3： 解题过程的单纯形表见下表4-3：4.4 某成品酒有三种商标（红、黄、蓝），都是由三种原料酒（等级、）兑制而成。三种等级的原料酒的日供应量和成本见表4-13，三种商标的成本酒的兑制要求和售价见表4-14。决策者规定：首先是必须严格按规定比例兑制各商标的酒；其次是获利

39、最大；最后是红商标的酒每天至少生产2000kg。试列出该问题的数学模型。解：设i=1,2,3表示原料酒、等级，j=1,2,3表红、黄、蓝酒，xij为j酒中使用第i种原料酒的数量，目标规划模型为： 4.5 公司决定使用1000万元新产品开发基金开发A、B、C三种新产品。经预测估计，开发A、B、C三种新产品的投资利润率分别为5%、7%、10%。由于新开发产品有一定风险，公司研究后确定了下列优先顺序目标：第一，A产品至少投资300万元；第二，为分散投资风险，任何一种新产品的开发投资不超过开发基金总额的35%；第三，应至少留有10%的开发基金，以备急用；第四，使总的投资利润最大。试建立投资分配方案的目

40、标规划模型。解：设对A、B、C三种新产品分别开发投资x1,x2,x3万元，则目标规划模型为： 4.6 已知单位牛奶、牛肉、鸡蛋中的维生素及胆固醇含量等有关数据见表4-15.如果只考虑这三种食物，并且设立了下列三个目标：第一，满足三种维生素的每日最小需求量；第二，使每日摄入的胆固醇最少；第三，使每日购买食品的费用最少。要求建立问题的目标规划模型。 4.7 金源公司生产三种产品，其整个计划期分为三个阶段。现需编制生产计划，确定各个阶段各种产品的生产数量。计划受市场需求、设备台时、财务资金等方面条件的约束，有关数据如表4-16和表4-17所示。假设计划期初及期末各种产品的库存量皆为零。公司设定以下三个优先等级的目标：P1：及时供货，