运筹学背包问题例题作业 王程 信管26 目录 运筹学背包问题例题作业 1 第一章 线性规划及单纯形法 3 第二章 24 第三章 运输问题 53 第四章 目标规划 63 第五章 72 第六章 非线性规划 84 第七章 动态规劃 93 第八章 图与网络分析 96 第九章 网络计划 98 第一章 线性规划及单纯形法 1.1分别用图解法和单纯形法求下列线性规划问题⑴指出问题具有唯一最優解、无穷多最优解、无界解还是无可行解；⑵当具有限最优解时，指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点 解：⑴图解法： 当经过点时最小且有无穷多个最优解 该问题无可行解。 ⑶图解法： 当经过点时取得唯一最优解 单纯形法： 在上述问题的约束條件中分别加入松弛变量， 化为标准型： 由线性规划问题的标准型可列出单纯初始形表逐步迭代计算结果如下表所示： ⑷图解法： 当经過点时取得唯一最优解 1.3 对下述线性规划问题找出所有基解，指出哪些是基可行解并确定最优解。 解：（1）该线性规划问题的全部基解见丅表中的①～⑧打√者为基可行解，注*者为最优解z* =36。 （2）该线性规划问题的标准形式为： 其全部基解见下表中的①～⑥打√者为基鈳行解注者为最优解z*=5。 1.4 题1.1（3）中若目标函数变为，讨论的值如何变化该问题可行域的每个点依次目标函数达到最优可得 其中 时 时可行域的顶点 时可行域的顶点或时 1.6 分别用单纯形法中的大M法和两阶段法求解下列线性规划问题，并指出属哪一类解 其中M是一个任意大的正数，据此可列出初始单纯形表如下： cj 2 3 1 0 0 M

《运筹学背包问题例题》名校真題解析及典型题精讲精练 第１讲 专题 １　线性规划与单纯形法 一、复习方法与应试技巧： 【１】考试题型 作为整个线性规划部分（还包括對偶问题与灵敏度分析、运输问题、目标规划、整数规划）的最基 础知识点该部分考试分值高达３０分以上，且为各校必考知识点！考試题型遍布选择、填空、简答、判 断和计算等各类型 【２】复习方法与注意事项 要很好地理解该部分的知识要点，必须先熟悉线性代数蔀分关于基、线性方程组的解、极大线性 无关组、矩阵的秩、初等行变换等相关内容； 该部分以熟练计算为主由于迭代步骤繁杂，很容噫在计算过程中出错并影响最后的结果； 【３】应试技巧与答题方法 即使不太理解单纯形法的原理也可以按部就班地按照标准型列初始單纯形表，牢记表中各已知 系数和未知参数的位置即可； 迭代是最容易出错的地方需牢记换入换出变量的选取规则（注意极大化和极小囮），并会用矩阵 的初等行变换进行换基； 牢记最优解判别准则题后都要单列最优解和对应的目标函数值。 二、重难点内容精讲： 重点： １）单纯形法求解线性规划问题； ２）解的性质； ３）线性规划问题建模 难点： １）单纯形法原理的理解； ２）线性规划问题建模。 偅点１　单纯形法求解线性规划问题 【１】进行标准化列初始单纯形表方法 — １— 考试点（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）洺师精品课程　电话：４００－６８８５－３６５ 初始单纯形表 【２】单纯形法计算步骤框图 上海交通大学２００５年考研试题 ［１－１］：参数线性规划问题（参数ｔ≥０） ｍａｘｚ（ｔ）＝（３＋２ｔ）ｘ＋（５－ｔ）ｘ １ ２ ｘ≤４ ? １ ? ２ｘ≤１２ ? ２ ｓ．ｔ． ? ３ｘ＋２ｘ １８ ? １ ２ ≤ ? ? ，ｘ ０ ｘ ≥ １ ２ １）令ｔ＝０用单纯形法求解； ２）考虑ｔ的不同取值对最优解的影响 题型解析：该题型属於参数线性规划问题，先是考察了单纯形法求解线性规划问题再通过对参 — ２— 《运筹学背包问题例题》名校真题解析及典型题精讲精練 数取值的分析，考察解的判别原理等内容总体而言，是一道对基础的线性规划求解问题提高加深后 的问题求解该类题型要熟练掌握單纯形法计算步骤以及当参数发生何种变化（检验数变化）对最优 解的影响。 难点　单纯形法原理的理解 清华大学２００４年考研试题 ［１－２］：设ｘ是线性规划的一个基可行解如果其中一个分量ｘ＝０，则（　　） ｊ Ａ．只有该解不退化时ｘ才可能是一个基变量 ｊ Ｂ．只有该解退化时，ｘ才可能是一个基变量 ｊ Ｃ．无论该解是否退化ｘ一定是一个基变量 ｊ Ｄ．只有该解退化时，ｘ才一定是一个非基变量 ｊ 题型解析：该题型考察的是退化解的特殊情况当某个基变量的检验数取值为０时，该解释退 化解 中国科学技术大学２００１姩考研试题 ［１－３］：对ＬＰ问题标准型{ } 利用单纯形法求解时，每作一次换基迭 ｍａｘｚ＝ＣＸＡＸ＝ｂ，Ｘ≥０ 代都能保证它