运筹学第1章习题

1、线性规划作业题P52 第2题 某厂的一个车间有，两个工段可以生产三种产品，各工段开工一天生产三种产品的数量和成本，以及合同对三种产品的每周最低需求量由下表给出。问每周各工段对该生产任务应开工几天，可使生产合同的要求得到满足，并使成本最低。建立模型。解：设生产产品的天数为（j=1,2） s.t ,j=1,2P52 第3题一个车间加工三种零件，其需求量分别为4000，5000，3500件。车间内现有四台机床，都可用来加工，每台机床可利用工时分别为1，600；1，250；1，800；2，000。机床加工零件所需工时和成本由下表给出：问如何安排生产，才可使生产成本最低？解：设机床生产零件的件数为，s.

2、t ， ，; P53 第6题某厂月底安排某一产品在下个月四周的生产计划。估计每件产品在第一周和第二周的生产成本150元，后两周为170元，各周产品需求量分别为700，800，1000，1200件，工厂每周至多生产产品900件，在第二周和第三周可加班，加班生产时每周增产300件，但生产成本每件增加30元，过剩的产品存贮费为每件每周15元，问如何安排生产，使总成本最小？解：设4周生产的产品件数分别为；第2，3周加班生产的件数为： s.t ;P53 第7题某企业年出有现金30万元，该企业有两个方案选择（1） 年初贷给其它企业，年息18%，第二年初可以收回（2） 本企业投资扩大生产。若年初投资一定金额

3、，则第二年还需要继续投资第一年的60%，而第三年可有等于第二年投资额的1.4倍收益为使第五年年初企业对这部分资金的最大收益，试确定企业每年资金的使用方案，列出数学模型。解答：设为该企业相似第一方案中第j年初使用资金，为该企业在 第二方案中使用的资金 年份 j(年初 ) 1 2 3 4 5 s.t. P53 第8题把下列线性规划化成标准型s.t 解：原式化为s.t 则代入化为标准型：s.t , j=2,3,5，9第9题：试画出下列线性规划可行域，并求出最优解和最优值（1） s.t ,解：根据约束条件和变量的非负要求，画出各自满足的区域（图）从图中可知当时：，（2） s.t 解：根据约束条件和变量

4、的非负要求，画出各自满足的区域（图）从图中可知当时：，P53 第9题 试画出下列线性规划的可行域，并求出最优解和最优值。（1） s.t. 解： 如图： K无界，有可行域； （2） s.t. 解： 如图：K有界P53 习题10 给定线性规划问题： （1）给出两个最优顶点及其最优值（2）给出它的全部最优解的集合解： （1）两个最优顶点，全部最优解的集合：线段AB上的点都是最优解P54 第12题题目：用单纯形法求解下列线性规划问题 解： 选取初始指标集，B=I，其单纯形表如下表1 XBX1 X2 X3 X4 X5 yit X1 X4 X51 2 1 0 0（2） 1 0 1 0 5 3 0 0 1

5、64156(2)3r（5）4 0 0 0 0选取t=1 x1进基，最小比值准则确定k=2, x4出基，转轴的表2 XBX1 X2 X3 X4 X5 yit X3 X1 X50 5/2 1 -1/2 0 1 -1/2 0 1/2 0 0 (11/2) 0 -5/2 1 62158/5(10/11)r0 (-13/2) 0 5/2 010选取t=2 x2进基，最小比值准则确定k=3, x5出基，转轴的表3 XBX1 X2 X3 X4 X5 yit X3 X1 X20 0 1 (7/11) -5/11 1 0 0 3/11 1/11 0 1 0 -5/11 2/11 19/1127/1110/111

6、9/79r0 0 0 (-5/13) 1175/13选取t=4 x4进基，最小比值准则确定k=1, x3出基，转轴的表4 XBX1 X2 X3 X4 X5 yit X4 X1 X20 0 11/7 1 -5/7 1 0 -3/7 0 2/7 0 1 5/7 0 -1/7 19/712/715/7r0 0 5/7 0 6/7120/7此时,检验数全部非负,算法终止,最优解和最优值为.P54 第15题：应用单纯形法证明下列问题无最优解s.t. 试找出一个可行解，它的目标函数值大于2000解： 令在表中，又 ，最小比值准则失效，（LP）的目标函数值在可行域内无下界 ，无最优解。取 则 为使 取得则

7、即 P55 第16 题 给定线性规划问题： 对基，用矩形运算给出其单纯形表。解答： P56 第21题 用大M法求解下列各个线性规划问题：（1） 解：取初始指标集为,B=I, 计算得,表1：取x3进基,X7出基 得表2： 取x2进基,X6出基 得表3:表3：-2表4：2最优解：最优值：P56 第22题 应用两阶段法求解下列各个线性规划问题（1）解：引进人工变量X6,X7,得(LP1)如下:第一阶段：）取初始指标集,得表1:表1：取x4进基,x6出基,得表2:表2：取x3进基,x7出基,得表3:表3：可知(LP1)的最优值为0,出现情况(2),得（LP）的一个初始可行解：第二阶段：将r行列删去,重新计算r的值,得表4:取x