运筹学教材编写组《运筹学》期末考试试卷(A)

运筹学试卷A及参考答案北京理工大学《运筹学》期终试卷(A卷)姓名成绩注意：① 答案一律写在答题纸上，写在其他地方无效。

② 考试过程中，不得拆开试卷。

③ 考试完毕后，试卷一律交回。

一、多项选择题(每小题2分，共12分)1、线性规划模型有特点（）。

A、所有函数都是线性函数；B、目标求最大；C、有等式或不等式约束；D、变量非负。

2、下面命题正确的是（）。

A、线性规划的最优解是基本可行解；B、基本可行解一定是基本解；C、线性规划一定有可行解；D、线性规划的最优值至多有一个。

3、一个线性规划问题（P）与它的对偶问题（D）有关系（）。

A、（P）有可行解则（D）有最优解；B、（P）、（D）均有可行解则都有最优解；C、（P）可行（D）无解，则（P）无有限最优解；D、（P）（D）互为对偶。

4、运输问题的基本可行解有特点（）。

A、有m＋n－1个基变量；B、有m+n个位势；C、产销平衡；D、不含闭回路。

5、关于动态规划问题的下列命题中（）是错误的。

A、动态规划分阶段顺序不同，则结果不同；B、状态对决策有影响；C、在求解最短路径问题时，标号法与逆序法求解的思路是相同的；D、动态规划的求解过程都可以用列表形式实现。

6、顾客泊松到达与相继到达的间隔时间服从负指数分布（）。

A、是相同概念的不同说法；B、是完全不相同的概念；C、它们的均值互为倒数；D、它们的均值是相同的。

二、回答下列各题（每小题8分，共16分）1、考虑线性规划问题Min f(x) = -x1 + 5 x2S.t. 2x1–3x2 ≥3 （P）5x1 ＋ 2x2＝4x1 ≥ 0写出（P）的标准形式；2、某企业生产3种产品甲、乙、丙，产品所需的主要原料有A、B两种，原料A每单位分别可生产产品甲、乙、丙底座12、18、16个；产品甲、乙、丙每个需要原料B分别为13kg、8kg、10kg，设备生产用时分别为10.5、12.5、8台时，每个产品的利润分别为1450元、1650元、1300元。

《运筹学》试题参考答案一、填空题（每空2分，共10分）1、在线性规划问题中，称满足所有约束条件方程和非负限制的解为 可行解 。

2、在线性规划问题中，图解法适合用于处理 变量 为两个的线性规划问题。

3、求解不平衡的运输问题的基本思想是 设立虚供地或虚需求点，化为供求平衡的标准形式 。

4、在图论中，称 无圈的 连通图为树。

5、运输问题中求初始基本可行解的方法通常有 最小费用法 、 西北角法 两种方法。

二、（每小题5分，共10分）用图解法求解下列线性规划问题： 1）max z = 6x 1+4x 2⎪⎪⎩⎪⎪⎨⎧≥≤≤+≤+0781022122121x x x x x x x ， 解：此题在“《运筹学》复习参考资料.doc ”中已有，不再重复。

2）min z =－3x 1+2x 2⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤-≤-≤+-≤+0,137210422422121212121x x x x x x x x x x 解：⑴ ⑵ ⑶ ⑷ ⑸ ⑹、⑺⑴⑵ ⑶ ⑷ ⑸、⑹可行解域为abcda ，最优解为b 点。

由方程组⎩⎨⎧==+02242221x x x 解出x 1=11，x 2=0∴X *=⎪⎪⎭⎫ ⎝⎛21x x =（11，0）T ∴min z =－3×11+2×0=－33三、（15分）某厂生产甲、乙两种产品，这两种产品均需要A 、B 、C 三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：A B C 甲 9 4 3 70 乙 4 6 10 1203602003001）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分）2）用单纯形法求该问题的最优解。

（10分） 解：1）建立线性规划数学模型：设甲、乙产品的生产数量应为x 1、x 2，则x 1、x 2≥0，设z 是产品售后的总利润，则max z =70x 1+120x 2s.t.⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤+0300103200643604921212121x x x x x x x x ， 2）用单纯形法求最优解：加入松弛变量x 3，x 4，x 5，得到等效的标准模型：max z =70x 1+120x 2+0 x 3+0 x 4+0 x 5s.t.⎪⎪⎩⎪⎪⎨⎧=≥=++=++=++5,...,2,1,03001032006436049521421321j x x x x x x x x x x j 列表计算如下：∴X *=（11，11，11，0，0）T∴max z =70×11100+120×11300=1143000四、（10分）用大M 法或对偶单纯形法求解如下线性规划模型：min z =5x 1＋2x 2＋4x 3⎪⎩⎪⎨⎧≥≥++≥++0,,10536423321321321x x x x x x x x x解：用大M 法，先化为等效的标准模型：max z / =－5x 1－2x 2－4x 3 s.t.⎪⎩⎪⎨⎧=≥=-++=-++5,...,2,1,010********214321j y x x x x x x x x j增加人工变量x 6、x 7，得到：max z / =－5x 1－2x 2－4x 3－M x 6－M x 7 s.t⎪⎩⎪⎨⎧=≥=+-++=+-++7,...,2,1,010*********2164321j x x x x x x x x x x x j大M 法单纯形表求解过程如下：∴x *=（32，2，0，0，0）T最优目标函数值min z =－max z / =－（－322）=322五、（15分）给定下列运输问题：（表中数据为产地A i 到销地B j 的单位运费）1）用最小费用法求初始运输方案，并写出相应的总运费；（5分） 2）用1）得到的基本可行解，继续迭代求该问题的最优解。

《运筹学》试题参考答案 一、填空题�每空2分�共10分� 1、在线性规划问题中�称满足所有约束条件方程和非负限制的解为 可行解 。

2、在线性规划问题中�图解法适合用于处理 变量 为两个的线性规划问题。

3、求解不平衡的运输问题的基本思想是 设立虚供地或虚需求点�化为供求平衡的标准形式 。

4、在图论中�称 无圈的 连通图为树。

5、运输问题中求初始基本可行解的方法通常有 最小费用法 、 西北角法 两种方法。

二、�每小题5分�共10分�用图解法求解下列线性规划问题� 1�m a x z = 6x 1+4x 2�������������0781022122121x x x x x x x � 解�此题在“《运筹学》复习参考资料.d o c ”中已有�不再重复。

2�m i n z =�3x 1+2x 2 �������������������0,137210422422121212121x x x x x x x x x x解�⑴⑵⑶ ⑷ ⑸⑹、⑺⑴⑵⑶ ⑷ ⑸、⑹可行解域为a b c d a �最优解为b 点。

由方程组������02242221xx x 解出x 1=11�x 2=0 ∴X *=��������21x x =�11�0�T∴m i n z =�3×11+2×0=�33三、�15分�某厂生产甲、乙两种产品�这两种产品均需要A 、B 、C 三种资源�每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示�ABC甲 9 4 3 70 乙 4 6 10 120 360 200 3002�用单纯形法求该问题的最优解。

�10分� 解�1�建立线性规划数学模型� 设甲、乙产品的生产数量应为x 1、x 2�则x 1、x 2≥0�设z 是产品售后的总利润�则 ma x z =70x 1+120x 2 s.t . ��������������0300103200643604921212121x x x x x x x x � 2�用单纯形法求最优解� 加入松弛变量x 3�x 4�x 5�得到等效的标准模型� ma x z =70x 1+120x 2+0 x 3+0 x 4+0 x 5 s.t . ������������������5,...,2,1,03001032006436049521421321j x x x x x x xx x x j 列表计算如下�CB XB b70 120 0θL x1 x2 x3 x4 x5 0x 3 360 94190 0 x 4 200 4 6 0 1 0 100/3 0 x 5 300 3 �10� 0 0 1 300 0 0 0 0 70 120↑ 0 0 0 0 x3 240 39/5 0 1 0 - 2/5 400/13 0 x4 20 �11/5� 0 0 1 - 3/5 100/11 120 x 2 30 3/10 1 0 0 1/10 10036 120 0 0 12 34↑ 0 0 0 �12 0 x3 1860/11 0 0 1 �39/11 19/11 70 x 1 100/11 1 0 0 5/11 - 3/11 120 x 2 300/11 0 1 0 - 3/22 2/11114300070 120 0 170/11 30/11 0 0-170/11 �30/11 ∴X *=�11100�11300�111860�0�0�T ∴m a x z =70×11100+120×11300=1143000四、�10分�用大M 法或对偶单纯形法求解如下线性规划模型� mi n z =5x 1�2x 2�4x 3 ������������0,,10536423321321321x x x x x x x x x解�用大M 法�先化为等效的标准模型� ma x z / =�5x 1�2x 2�4x 3 s.t . ���������������5,...,2,1,01053642353214321j y x x x xx x x x j 增加人工变量x 6、x 7�得到� ma x z / =�5x 1�2x 2�4x 3�M x 6�M x 7 s.t �����������������7,...,2,1,0105364237532164321j x x x x x x x x x x x j 大M 法单纯形表求解过程如下�C B X B b�5�2�400�M�MθLx1x2x3x4x5x6x7�M x64�3�12�10104/3�M x7106350�1015/3�9M�4M�7M M M�M�M9M�5↑4M�27M�4�M�M00�5x14/311/32/3�1/301/30——�M x72011�2��1�211�5-M�5/3-M�10/3-2M+5/3M2M�5/3-M0M�1/3M�2/32M�5/3↑�M�3M+5/30�5x15/311/25/60�1/601/610/3 0x410�1/2�1/21�1/2�11/22�5�5/2�25/605/60�5/601/2↑1/60�5/6�M�M+5/6�5�2x12/3101/3�11/31�1/3 x220112�1�21�322�5�2�11/311/3�1�1/3 00�1/3�1�1/3�M+1�M+1/3∴x*=�32�2�0�0�0�T最优目标函数值m i n z=�m a x z/=���322�=322五、�15分�给定下列运输问题��表中数据为产地A i到销地B j的单位运费�B1 B2 B3 B4 si A 1 A 2 A 3 1 2 3 4 8 7 6 5 9 10 11 9 10 80 15 dj 8 22 12 181�用最小费用法求初始运输方案�并写出相应的总运费��5分� 2�用1�得到的基本可行解�继续迭代求该问题的最优解。

运筹学期考试试卷学院 ________________ 班级 __________ 姓名 __________ 学号 ___________《运筹学（I ）》课程试卷A（本卷考试时间 120 分钟）1.一个极小化线性规划的某轮表格中有r =(-1，-2，0，0，0)，请问是否可以选择1x 作为进基变量？为什么？2.线性规划原问题min{0}TC X AX b X ≥≥，和对偶问题 max{0}T T b U A U C U ≤≥，都有可行解，则原问题的目标函数值一定不小于对偶问题的目标函数值？为什么？3.有一个线性规划，它有8个变量、4个独立的约束。

请问X =(1，2，3，4，5，0，0，0)T是否可以是它的一个基本可行解？为什么？4. m 个发点，n 个收点的产销平衡运输问题数学模型约束条件中，独立约束条件有多少个？为什么？5.一个赋权图的最小生成树是否唯一？为什么？二、求极小化线性规划问题的一个单纯形表如下表。

问a 1、a 2、a 3、a 4、a 5 、a 6分别为何值时：（本题共13(1) (1)(2)表中给出线性规划有无穷多解；(3)表中给出线性规划的可行解无界；(4)表中给出线性规划1x 为换入变量，4x 为换出变量；三、给出线性规划：（本题共10分）ma x321326x x x f +-= t s . 12x 2x -223≤+x1x 443≤+x 01≥x 02≥x 03≥x（1）写出对偶问题；（2）已知41=x ，62=x ，03=x ，是上述线性规划的最优解，用互补松弛定理求 对偶问题的最优解。

四、已知线性规划：（本题共12分）max32110127x x x f ++=t s . 1x 2x +203≤+x2122x x +303≤+x01≥x 02≥x 03≥xf f -='（2）若该LP 问题原目标函数中X 1 的系数由7变为9，问最优解有什么变化？（3） 若右端常数⎪⎪⎭⎫ ⎝⎛21b b 由⎪⎪⎭⎫ ⎝⎛3020变为⎪⎪⎭⎫ ⎝⎛3040，问最优解有什么变化？五、若发点1A ，2A 及收点1B ，2B ，3B 的有关数据如下表所示。

D、分支定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，在求相应的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规划问题通过分支迭代求出最优解。

7、下列变量组是一个闭回路的有（）A、{x21,x11,x12,x32,x33,x23}B、{ x11,x12,x23,x34,x41,x13}C、{x21,x13,x34,x41,x12,x14}D、{ x12,x22,x32,x33,x23,x21}8、工序（i,j）的最早开工时间T ES（i,j）等于（）A、T E（i）B、max{ T Es（k）+ t ki }C、T L（i）D、min{ T L（j）- t ij }9、对于不确定型的决策，某人采用悲观主义准则进行决策，则应在收益表中（）A、大中取小B、大中取大C、小中取小D、小中取大10、以下哪项是决策结果的方法程序（）A、收集信息-确定目标-提出方案-方案优化-决策B、确定目标-收集信息-决策-提出方案-优化方案C、确定目标-收集信息-提出方案-方案优化-决策D、确定目标-提出方案-收集信息-方案优化-决策单项选择题答题表二、判断题，正确打√，错误打×, 并将修改建议简写在对应题号下的改错栏。

（20分，每题2分）1、线性规划问题的每一个基可行解对应可行域的一个顶点。

（√）2、图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。

（√）3、线性规划模型中增加一个约束条件，可行区域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。

（√）4、紧前工序是前道工序，后序工序是紧后工序。

( )5、在折衷主义准则中，乐观系数α的确定与决策者对风险的偏好有关。

( )6、旅行售货员问题是遍历每一条边的问题。

( )7、按最小元素法给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路。

（√）8、在目标规划模型中，正偏差变量应取正值，负偏差变量应取负值。

《运筹学》试题参考答案 一、填空题�每空2分�共10分� 1、在线性规划问题中�称满足所有约束条件方程和非负限制的解为 可行解 。

2、在线性规划问题中�图解法适合用于处理 变量 为两个的线性规划问题。

3、求解不平衡的运输问题的基本思想是 设立虚供地或虚需求点�化为供求平衡的标准形式 。

4、在图论中�称 无圈的 连通图为树。

5、运输问题中求初始基本可行解的方法通常有 最小费用法 、 西北角法 两种方法。

二、�每小题5分�共10分�用图解法求解下列线性规划问题� 1�m a x z = 6x 1+4x 2�������������0781022122121x x x x x x x � 解�此题在“《运筹学》复习参考资料.d o c ”中已有�不再重复。

2�m i n z =�3x 1+2x 2 �������������������0,137210422422121212121x x x x x x x x x x解�⑴⑵⑶ ⑷ ⑸⑹、⑺⑴⑵⑶ ⑷ ⑸、⑹可行解域为a b c d a �最优解为b 点。

由方程组������02242221xx x 解出x 1=11�x 2=0 ∴X *=��������21x x =�11�0�T∴m i n z =�3×11+2×0=�33三、�15分�某厂生产甲、乙两种产品�这两种产品均需要A 、B 、C 三种资源�每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示�ABC甲 9 4 3 70 乙 4 6 10 120 360 200 3002�用单纯形法求该问题的最优解。

�10分� 解�1�建立线性规划数学模型� 设甲、乙产品的生产数量应为x 1、x 2�则x 1、x 2≥0�设z 是产品售后的总利润�则 ma x z =70x 1+120x 2 s.t . ��������������0300103200643604921212121x x x x x x x x � 2�用单纯形法求最优解� 加入松弛变量x 3�x 4�x 5�得到等效的标准模型� ma x z =70x 1+120x 2+0 x 3+0 x 4+0 x 5 s.t . ������������������5,...,2,1,03001032006436049521421321j x x x x x x xx x x j 列表计算如下�CB XB b70 120 0θL x1 x2 x3 x4 x5 0x 3 360 94190 0 x 4 200 4 6 0 1 0 100/3 0 x 5 300 3 �10� 0 0 1 300 0 0 0 0 70 120↑ 0 0 0 0 x3 240 39/5 0 1 0 - 2/5 400/13 0 x4 20 �11/5� 0 0 1 - 3/5 100/11 120 x 2 30 3/10 1 0 0 1/10 10036 120 0 0 12 34↑ 0 0 0 �12 0 x3 1860/11 0 0 1 �39/11 19/11 70 x 1 100/11 1 0 0 5/11 - 3/11 120 x 2 300/11 0 1 0 - 3/22 2/11114300070 120 0 170/11 30/11 0 0-170/11 �30/11 ∴X *=�11100�11300�111860�0�0�T ∴m a x z =70×11100+120×11300=1143000四、�10分�用大M 法或对偶单纯形法求解如下线性规划模型� mi n z =5x 1�2x 2�4x 3 ������������0,,10536423321321321x x x x x x x x x解�用大M 法�先化为等效的标准模型� ma x z / =�5x 1�2x 2�4x 3 s.t . ���������������5,...,2,1,01053642353214321j y x x x xx x x x j 增加人工变量x 6、x 7�得到� ma x z / =�5x 1�2x 2�4x 3�M x 6�M x 7 s.t �����������������7,...,2,1,0105364237532164321j x x x x x x x x x x x j 大M 法单纯形表求解过程如下�C B X B b�5�2�400�M�MθLx1x2x3x4x5x6x7�M x64�3�12�10104/3�M x7106350�1015/3�9M�4M�7M M M�M�M9M�5↑4M�27M�4�M�M00�5x14/311/32/3�1/301/30——�M x72011�2��1�211�5-M�5/3-M�10/3-2M+5/3M2M�5/3-M0M�1/3M�2/32M�5/3↑�M�3M+5/30�5x15/311/25/60�1/601/610/3 0x410�1/2�1/21�1/2�11/22�5�5/2�25/605/60�5/601/2↑1/60�5/6�M�M+5/6�5�2x12/3101/3�11/31�1/3 x220112�1�21�322�5�2�11/311/3�1�1/3 00�1/3�1�1/3�M+1�M+1/3∴x*=�32�2�0�0�0�T最优目标函数值m i n z=�m a x z/=���322�=322五、�15分�给定下列运输问题��表中数据为产地A i到销地B j的单位运费�B1 B2 B3 B4 si A 1 A 2 A 3 1 2 3 4 8 7 6 5 9 10 11 9 10 80 15 dj 8 22 12 181�用最小费用法求初始运输方案�并写出相应的总运费��5分� 2�用1�得到的基本可行解�继续迭代求该问题的最优解。

一、判断题（共计 分，每小题 分，对的打√，错的打✠） 无孤立点的图一定是连通图。

 对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定有最优解。

 如果一个线性规划问题有可行解，那么它必有最优解。

．对偶问题的对偶问题一定是原问题。

．用单纯形法求解标准形式（求最小值）的线性规划问题时，与>jσ对应的变量都可以被选作换入变量。

．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。

 度为 的点称为悬挂点。

 表上作业法实质上就是求解运输问题的单纯形法。

 一个图☝ 是树的充分必要条件是边数最少的无孤立点的图。

二、建立下面问题的线性规划模型（ 分）某农场有 公顷土地及 元资金可用于发展生产。

农场劳动力情况为秋冬季 人日；春夏季人日。

如劳动力本身用不了时可外出打工，春秋季收入为 元  人日，秋冬季收入为 元  人日。

该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。

种作物时不需要专门投资，而饲养每头奶牛需投资 元，每只鸡投资 元。

养奶牛时每头需拨出 公顷土地种饲料，并占用人工秋冬季为 人日，春夏季为 人日，年净收入 元  每头奶牛。

养鸡时不占用土地，需人工为每只鸡秋冬季 人日，春夏季为 人日，年净收入 元  每只鸡。

农场现有鸡舍允许最多养 只鸡，牛栏允许最多养 头。

三种作物每年需要的人工及收入情况如下表所示：试决定该农场的经营方案，使年净收入为最大。

三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中54,x x 为松弛变量，问题的约束为♉ 形式（共 分）☎✆写出原线性规划问题；（ 分） ☎✆写出原问题的对偶问题；（ 分）☎✆直接由上表写出对偶问题的最优解。

（ 分）四、用单纯形法解下列线性规划问题（ 分）3212max x x x Z +-=♦ ♦  ⌧  ⌧  ⌧  ⌧  ⌧   ⌧    ⌧  ⌧  ⌧   ⌧  ⌧   ⌧  五、求解下面运输问题。

《运筹学》期末考试试卷A-答案一、选择题（每题5分，共25分）1. 运筹学是一门研究在复杂系统中进行决策的科学，以下哪个选项不属于运筹学的研究内容？A. 优化问题B. 随机过程C. 系统建模D. 心理咨询答案：D2. 在线性规划中，若一个线性规划问题的可行域是空集，则该问题称为：A. 无界问题B. 无解问题C. 无可行解问题D. 有解问题答案：C3. 线性规划问题中，目标函数和约束条件均为线性函数的是：A. 线性规划B. 非线性规划C. 动态规划D. 随机规划答案：A4. 在整数规划中，若决策变量只能取整数值，则该问题称为：A. 线性规划B. 整数规划C. 非线性规划D. 动态规划答案：B5. 在排队论中，以下哪个因素对服务效率影响最大？A. 服务速率B. 到达率C. 排队长度D. 服务时间答案：A二、填空题（每题5分，共25分）1. 运筹学的基本方法是________、________和________。

答案：模型化、最优化、计算机模拟2. 线性规划的标准形式包括________、________和________。

答案：目标函数、约束条件、非负约束3. 在非线性规划中，目标函数和约束条件至少有一个是________函数。

答案：非线性4. 动态规划适用于解决________决策问题。

答案：多阶段5. 排队论中的基本参数包括________、________和________。

答案：到达率、服务率、服务台数量三、简答题（每题10分，共30分）1. 请简要介绍线性规划的基本概念。

答案：线性规划是运筹学的一个基本分支，主要研究在一定的线性约束条件下，如何求解目标函数的最大值或最小值问题。

线性规划问题通常包括目标函数、约束条件和非负约束。

目标函数是决策者要优化的目标，约束条件是决策者需要满足的条件，非负约束要求决策变量取非负值。

2. 请简要阐述整数规划的特点。

答案：整数规划是线性规划的一种特殊情况，要求决策变量取整数值。

《运筹学》试题参考答案 一、填空题�每空2分�共10分� 1、在线性规划问题中�称满足所有约束条件方程和非负限制的解为 可行解 。

2、在线性规划问题中�图解法适合用于处理 变量 为两个的线性规划问题。

3、求解不平衡的运输问题的基本思想是 设立虚供地或虚需求点�化为供求平衡的标准形式 。

4、在图论中�称 无圈的 连通图为树。

5、运输问题中求初始基本可行解的方法通常有 最小费用法 、 西北角法 两种方法。

二、�每小题5分�共10分�用图解法求解下列线性规划问题� 1�m a x z = 6x 1+4x 2�������������0781022122121x x x x x x x � 解�此题在“《运筹学》复习参考资料.d o c ”中已有�不再重复。

2�m i n z =�3x 1+2x 2 �������������������0,137210422422121212121x x x x x x x x x x解�⑴⑵⑶ ⑷ ⑸⑹、⑺⑴⑵⑶ ⑷ ⑸、⑹可行解域为a b c d a �最优解为b 点。

由方程组������02242221xx x 解出x 1=11�x 2=0 ∴X *=��������21x x =�11�0�T∴m i n z =�3×11+2×0=�33三、�15分�某厂生产甲、乙两种产品�这两种产品均需要A 、B 、C 三种资源�每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示�ABC甲 9 4 3 70 乙 4 6 10 120 360 200 3002�用单纯形法求该问题的最优解。

�10分� 解�1�建立线性规划数学模型� 设甲、乙产品的生产数量应为x 1、x 2�则x 1、x 2≥0�设z 是产品售后的总利润�则 ma x z =70x 1+120x 2 s.t . ��������������0300103200643604921212121x x x x x x x x � 2�用单纯形法求最优解� 加入松弛变量x 3�x 4�x 5�得到等效的标准模型� ma x z =70x 1+120x 2+0 x 3+0 x 4+0 x 5 s.t . ������������������5,...,2,1,03001032006436049521421321j x x x x x x xx x x j 列表计算如下�CB XB b70 120 0θL x1 x2 x3 x4 x5 0x 3 360 94190 0 x 4 200 4 6 0 1 0 100/3 0 x 5 300 3 �10� 0 0 1 300 0 0 0 0 70 120↑ 0 0 0 0 x3 240 39/5 0 1 0 - 2/5 400/13 0 x4 20 �11/5� 0 0 1 - 3/5 100/11 120 x 2 30 3/10 1 0 0 1/10 10036 120 0 0 12 34↑ 0 0 0 �12 0 x3 1860/11 0 0 1 �39/11 19/11 70 x 1 100/11 1 0 0 5/11 - 3/11 120 x 2 300/11 0 1 0 - 3/22 2/11114300070 120 0 170/11 30/11 0 0-170/11 �30/11 ∴X *=�11100�11300�111860�0�0�T ∴m a x z =70×11100+120×11300=1143000四、�10分�用大M 法或对偶单纯形法求解如下线性规划模型� mi n z =5x 1�2x 2�4x 3 ������������0,,10536423321321321x x x x x x x x x解�用大M 法�先化为等效的标准模型� ma x z / =�5x 1�2x 2�4x 3 s.t . ���������������5,...,2,1,01053642353214321j y x x x xx x x x j 增加人工变量x 6、x 7�得到� ma x z / =�5x 1�2x 2�4x 3�M x 6�M x 7 s.t �����������������7,...,2,1,0105364237532164321j x x x x x x x x x x x j 大M 法单纯形表求解过程如下�C B X B b�5�2�400�M�MθLx1x2x3x4x5x6x7�M x64�3�12�10104/3�M x7106350�1015/3�9M�4M�7M M M�M�M9M�5↑4M�27M�4�M�M00�5x14/311/32/3�1/301/30——�M x72011�2��1�211�5-M�5/3-M�10/3-2M+5/3M2M�5/3-M0M�1/3M�2/32M�5/3↑�M�3M+5/30�5x15/311/25/60�1/601/610/3 0x410�1/2�1/21�1/2�11/22�5�5/2�25/605/60�5/601/2↑1/60�5/6�M�M+5/6�5�2x12/3101/3�11/31�1/3 x220112�1�21�322�5�2�11/311/3�1�1/3 00�1/3�1�1/3�M+1�M+1/3∴x*=�32�2�0�0�0�T最优目标函数值m i n z=�m a x z/=���322�=322五、�15分�给定下列运输问题��表中数据为产地A i到销地B j的单位运费�B1 B2 B3 B4 si A 1 A 2 A 3 1 2 3 4 8 7 6 5 9 10 11 9 10 80 15 dj 8 22 12 181�用最小费用法求初始运输方案�并写出相应的总运费��5分� 2�用1�得到的基本可行解�继续迭代求该问题的最优解。