运筹学复习题.docVIP

线性规划及单纯形法 一、复习思考题 1 试述线性规划数学模型的结构及各要素的特征。 2 线性规划的解有哪几种情况。 3 什么是线性规划问题的标准形式，如何将一个非标准型的线性规划问题转化为标 准形式。 4 试述线性规划问题的可行解、基解、基可行解、最优解的概念以及上述解之间的相互关系。 5 试述单纯形法的计算步骤，如何在单纯形表上去判别问题是具有惟一最优解、无穷多最优解、无界解或无可行解。 6 如果线性规划的标准型式变换为求目标函数的极小化min z，则用单纯形法计算时如何判别问题已得到最优解。 7 在确定初始可行基时，什么情况下要在约束条件中增添人工变量，在目标函数中人工变量前的系数为(一M)的经济意义是什么。 8 什么是单纯形法计算的两阶段法，为什么要将计算分两个阶段进行，以及如何根据第一阶段的计算结果来判定第二阶段的计算是否需继续进行。 9 简述退化的含义及处理退化的勃兰特规则。 10 举例说明生产和生活中应用线性规划的方面，并对如何应用进行必要描述。 二、判断下列说法是否正确 1、 图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的； 2、 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大； 3、线性规划问题的每一个基解对应可行域的一个顶点. 4、如线性规划问题有最优解，则最优解一定对应可行域边界上的一个点； 5、用单纯形法求解标准型式的线性规划问题时，与对应的变量都可被选作换入变量； 6、单纯形法计算中，选取最大正检验数σk对应的变量xk作为换入变量，将使目标函数值得到最快的增长； 7、线性规划问题任一可行解都可以用全部基可行解的线性组合表示； 9、对一个有n个变量，m个约束的标准型的线性规划问题，其可行域的顶点恰好为个； 10、单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解； 11、若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解； 12、线形规划可行域的某一项点若其目标函数值优于所有顶点的目标函数值，则该顶点处的目标函数值达到最优。 三、计算题 1、分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代中的基本可行解跟图解法可行域中哪一顶点相对应。 （1） （2） 2、用单纯形法求解下列线性规划问题 s.t. s.t. s.t. s.t. s.t. s.t. 3、 某一求目标函数极大值的线性规划问题,用单纯形法求解时得到某一步的单纯形如表所示: cBi xBi x1 x2 x3 x4 x5 x6 bi bi/aik 　 x2 0 1 0 0 0 a1 a2 　 　 x3 2 0 1 a4 0 -2 4 　 　 x5 a3 0 0 -4 1 3 10 　 　 　 a5 0 0 a6 0 6 　 　 表中xj 均为非人工变量,为使下列说法正确, 试确定参数a1,a2,a3,a4,a5,a6的范围. (1)现行解为唯一最优解． (2)现行解为最优，但有多重最优解． (3)现行解为退化基本最优解． (4)该线性规划问题有可行解，但目标函数无界． (5)该线性规划问题无可行解． 4 、某厂生产甲、乙两种产品，已知生产一吨甲产品需用资源A：3 吨，资源 B：4 m3 ；生产一吨乙产品需用资源A：2 吨，资源 B：6 m3，，资源C：7个单位。若一吨甲和乙的经济价值分别为7万元和5万元，A、B、C三种资源的限制量分别为90吨、200 m3和210个单位，试决定应生产这两种产品各多少吨才能使创造的总经济价值最高？ 5、制造某机床需要A、B、C 三种轴，其规格、需要量如下表所示。各种轴都用长7.4米的圆钢来截毛坯。如果制造100台机车，问最少要用多少根圆钢？试建立该问题的线性规划模型，并写出其对偶规划。 轴件 规格：长度（米） 每台机床所需轴件数量 A B C 2.9 2.1 1.5 1 1 1 6、试用单纯形法求解下列线性规划问题 2、某工厂生产A、B、C三种产品，现根据订货合同以及生产状况制定生产计划。 已知甲合同为：A产品1000件，单价600元，违约金为120元/件； B产品700件，单价500元，违约金为100元/件。 乙合同为：B产品900件，单价550元，违约金为110元/件； C产品800件，单价450元，违约金为90元/件。 有关各产品生产过程所需工时以及原材料的情况见下表。试以利润最大为目标，建立该工厂的生产计划线性规划模型（不求解）。 工序1 （工时） 工序2 （工时） 原材料1 原材料2 其他成本 （元/件） 产品A 3 5 7 9 12 产品B 2 4 6 8 13 产品C 1 3 5 7 14 总工时、总原材料 6