考虑如下线性规划问题(新)

考虑如下线性规划问题：

Min z=60

x+402x+803x

1

s.t. 3

x+22x+3x≥2

1

4

x+2x+33x≥4

1

2

x+22x+23x≥3

1

x,2x,3x≥0

1

要求：（1）写出其对偶问题；

（2）用对偶单纯形法求解原问题；

（3）用单纯形法求解其对偶问题；

（4）对比（2）与（3）中每步计算得到的结果。

解：(1)设对应于上述约束条件的对偶变量分别为

y,2y,3y；则由原问

1

题和对偶问题，可以直接写出对偶问题为：

Max Z’=2

y+42y+33y

1

s.t 3

y+42y+23y≤60

1

2

y+2y+23y≤40

1

y+32y+23y≤80

1

y,2y,3y≥0

1

(2)用对偶单纯形法求解原问题（添加松弛变量

x,5x,6x）

4

MaxZ= -60

x-402x-803x+04x+05x+06x

1

s.t -3

x-22x-3x+4x=-2

1

-4

x-2x-33x+5x=-4

1

-2

x-22x-23x+6x=-3

1

x,2x,3x≥0

1

建立此问题的初始单纯形表，可见：

从表中可以看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需进行迭代运算。

换出变量的确定，计算min（-2，-4，-3）=-4，故

x为换出变量。

5

换入变量的确定，计算得15,40，80/3,故

x为换入变量。

1

由表可知，

x为换出变量。2x为换入变量。然后继续画单纯形表：

6

可得

x为换出变量，3x为换入变量。继续做单纯形表：

4

所以此问题的最优解为X=（11/10,19/30，1/10），此对偶问题的最优解为Y=（16,12,30），原问题的最小值为118/3.

（3）MaxZ’=2

y+42y+33y+04y+05y+06y

1

s.t 3

y+42y+23y+4y=60

1

2

y+2y+23y+5y=40

1

y+32y+23y+6y=80

1

y,2y,3y,4y,5y,6y≥0

1

然后建立单纯形表，可得

由此可知，

y为换出变量，2y为换入变量。继续画单纯形表，

4

由此可知，

y为换出变量，3y为换入变量。继续画单纯形表，

5

由此可得最后一行的检验数都已经为负或是零，这表示目标函数值已不可能再增大，于是得到最优解为

Y=（0,20 /3,50/3，0,0,80/3）

目标函数值为230/3

（4）比较第二问和第三问，主要是换出变量和换入变量的关系：

第（2）问里，

x为换出变量，1x为换入变量；6x为换出变量。2x为换

5

入变量；

x为换出变量，3x为换入变量！

4

第（3）问里，

y为换出变量，2y为换入变量；5y为换出变量，3y为

4

换入变量！

考虑如下线性规划问题

考虑如下线性规划问题： Min z=60 x+402x+803x 1 . 3 x+22x+3x≥2 1 4 x+2x+33x≥4 1 2 x+22x+23x≥3 1 x,2x,3x≥0 1 要求：（1）写出其对偶问题； （2）用对偶单纯形法求解原问题； （3）用单纯形法求解其对偶问题； （4）对比（2）与（3）中每步计算得到的结果。 解：(1)设对应于上述约束条件的对偶变量分别为 y,2y,3y；则 1 由原问题和对偶问题，可以直接写出对偶问题为： Max Z’=2 y+42y+33y 1 3 y+42y+23y≤60 1 2 y+2y+23y≤40 1 y+32y+23y≤80 1 y,2y,3y≥0 1 (2)用对偶单纯形法求解原问题（添加松弛变量 x,5x,6x） 4 MaxZ= -60 x-402x-803x+04x+05x+06x 1 -3 x-22x-3x+4x=-2 1 -4 x-2x-33x+5x=-4 1 -2 x-22x-23x+6x=-3 1

1x ,2x ,3x ≥0 建立此问题的初始单纯形表，可见： 从表中可以看到，检验数行对应的对偶问题的解是可行解。因b 列数字为负，故需进行迭代运算。 换出变量的确定，计算min （-2，-4，-3）=-4，故5x 为换出变量。 换入变量的确定，计算得15,40，80/3,故1x 为换入变量。

由表可知，6x 为换出变量。2x 为换入变量。然后继续画单纯形表： 可得4x 为换出变量，3x 为换入变量。继续做单纯形表：

所以此问题的最优解为X=（11/10,19/30，1/10），此对偶问题的最优解为Y=（16,12,30），原问题的最小值为118/3. （3）MaxZ ’=21y +42y +33y +04y +05y +06y 31y +42y +23y +4y =60 21y +2 y +23y +5y =40 1y +32y +23y +6y =80 1y ,2y ,3y ,4y ,5y ,6y ≥0 然后建立单纯形表，可得 i

考虑如下线性规划问题

考虑如下线性规划问题

考虑如下线性规划问题： Min z=60 x+402x+803x 1 s.t. 3 x+22x+3x≥2 1 4 x+2x+33x≥4 1 2 x+22x+23x≥3 1 x,2x,3x≥0 1 要求：（1）写出其对偶问题； （2）用对偶单纯形法求解原问题； （3）用单纯形法求解其对偶问题； （4）对比（2）与（3）中每步计算得到的结果。 解：(1)设对应于上述约束条件的对偶变量分别为 y,2y,3y；则由原问 1 题和对偶问题，可以直接写出对偶问题为： Max Z’=2 y+42y+33y 1 s.t 3 y+42y+23y≤60 1 2 y+2y+23y≤40 1 y+32y+23y≤80 1 y,2y,3y≥0 1 (2)用对偶单纯形法求解原问题（添加松弛变量 x,5x,6x） 4 MaxZ= -60 x-402x-803x+04x+05x+06x 1 s.t -3 x-22x-3x+4x=-2 1 -4 x-2x-33x+5x=-4 1 -2 x-22x-23x+6x=-3 1

x,2x,3x≥0 1 建立此问题的初始单纯形表，可见： 从表中可以看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需进行迭代运算。 换出变量的确定，计算min（-2，-4，-3）=-4，故 x为换出变量。 5 换入变量的确定，计算得15,40，80/3,故 x为换入变量。 1 由表可知， x为换出变量。2x为换入变量。然后继续画单纯形表： 6

可得 x为换出变量，3x为换入变量。继续做单纯形表： 4 所以此问题的最优解为X=（11/10,19/30，1/10），此对偶问题的最优解为Y=（16,12,30），原问题的最小值为118/3. （3）MaxZ’=2 y+42y+33y+04y+05y+06y 1 s.t 3 y+42y+23y+4y=60 1 2 y+2y+23y+5y=40 1 y+32y+23y+6y=80 1 y,2y,3y,4y,5y,6y≥0 1 然后建立单纯形表，可得

《运筹学》习题线性规划部分练习题及答案

《运筹学》线性规划部分练习题 一、思考题 1．什么是线性规划模型，在模型中各系数的经济意义是什么？ 2．线性规划问题的一般形式有何特征？ 3．建立一个实际问题的数学模型一般要几步？ 4．两个变量的线性规划问题的图解法的一般步骤是什么？ 5．求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 6．什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 7．试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8．试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9．在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 10．大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？ 11．什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？ 二、判断下列说法是否正确。 1．线性规划问题的最优解一定在可行域的顶点达到。 2．线性规划的可行解集是凸集。 3．如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。 4．线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。 5．线性规划问题的每一个基本解对应可行域的一个顶点。 6．如果一个线性规划问题有可行解，那么它必有最优解。 7．用单纯形法求解标准形式（求最小值）的线性规划问题时，与 > j σ 对应的变量都 可以被选作换入变量。 8．单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一个基变量的值是负的。 9．单纯形法计算中，选取最大正检验数k σ对应的变量k x作为换入变量，可使目标函数值得到最快的减少。 10．一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。 三、建立下面问题的数学模型 1．某公司计划在三年的计划期内，有四个建设项目可以投资：项目Ⅰ从第一年到 第三年年初都可以投资。预计每年年初投资，年末可收回本利120% ，每年又可以重新将所获本利纳入投资计划；项目Ⅱ需要在第一年初投资，经过两年可收回本利150% ，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目Ⅲ需要在第二年年初投资，经过两年可收回本利160% ，但用于该项目的最大投资额不得超过15万元；项目Ⅳ需要在第三年年初投资，年末可收回本利140% ，但用于该项目的最大投资额不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？ 2．某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、100克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单 价如下表2—1所示：

《运筹学》习题线性规划部分练习题及答案.doc

《运筹学》线性规划部分练习题 一、思考题 1． 什么是线性规划模型，在模型中各系数的经济意义是什么？ 2． 线性规划问题的一般形式有何特征？ 3． 建立一个实际问题的数学模型一般要几步？ 4． 两个变量的线性规划问题的图解法的一般步骤是什么？ 5． 求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 6． 什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 7． 试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8． 试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9． 在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 10．大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？ 11．什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？ 二、判断下列说法是否正确。 1． 线性规划问题的最优解一定在可行域的顶点达到。 2． 线性规划的可行解集是凸集。 3． 如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。 4． 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。 5． 线性规划问题的每一个基本解对应可行域的一个顶点。 6． 如果一个线性规划问题有可行解，那么它必有最优解。 7． 用单纯形法求解标准形式（求最小值）的线性规划问题时，与0 >j σ对应的变量都可以被选作换入变量。 8． 单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一个基变量的值是负的。 9． 单纯形法计算中，选取最大正检验数k σ对应的变量k x 作为换入变量，可使目 标函数值得到最快的减少。 10． 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。 三、建立下面问题的数学模型 1． 某公司计划在三年的计划期内，有四个建设项目可以投资：项目Ⅰ从第一年到 第三年年初都可以投资。预计每年年初投资，年末可收回本利120% ，每年又可以重新将所获本利纳入投资计划；项目Ⅱ需要在第一年初投资，经过两年可收回本利150% ，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目Ⅲ需要在第二年年初投资，经过两年可收回本利160% ，但用于该项目的最大投资额不得超过15万元；项目Ⅳ需要在第三年年初投资，年末可收回本利140% ，但用于该项目的最大投资额不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？ 2．某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、 100克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单 价如下表2—1所示：

线性规划习题

第一章 线性规划习题 1. 将下列线性规划问题变换成标准型，并列出初始单纯形表。 1) min Z ＝－3x 1＋4x 2－2x 3＋5x 4 s.t.???????≥≥+-+-≤-++-=-+-. ,0,,22321432244321432143214321无约束x x x x x x x x x x x x x x x x 2) max S ＝z x ／p k s.t.???? ????? ==≥=-=-=∑∑∑===).,...,2,1;,...,2,1(0),,...,2,1(1, 1 11 m k n i x n i x x a z ik m k ik n i m k ik ik k 2. 分别用单纯法中的大M 法和两阶段法求解下述线性规划问题： min Z ＝2x 1＋3x 2＋x 3 s.t.??? ??≥≥+≥++.0,,,623,8243 212 1321x x x x x x x x 并指出该问题的解属哪一类解。 3. 【表1-6】是某求极大化线性规划问题计算得到单纯形表。表中无人工变量， a 1, a 2, a 3, d , c 1, c 2为待定常数。试说明这些常数分别取何值时，以下结论成立。 1) 表中解为唯一最优解； 2) 表中解为最优解，但存在无穷多最优解； 3) 该线性规划问题具有无界解； 4) 表中解非最优，为对解进行改进，换入变量为x 1，换出变量为x 6。 表1-6 4. 某饲料厂用原料A 、B 、C 加工成三种不同牌号的饲料甲、乙、丙。已知各 种牌号饲料中A 、B 、C 含量，原料成本，各种原料的每月限制用量，三种牌号的饲料的单位加工费及售价如【表1-7】所示。 表1-7

考虑如下线性规划问题

考虑如下线性规划问题： Min z=60 x1+40 x2 +80 x3 s.t. 3 x1 +2 x2 + x3 2 4x1 +x2 +3x3 4 2x1 +2x2 +2x3 3 x1 , x2 , x3 0 要求：（1）写出其对偶问题； （2）用对偶单纯形法求解原问题； （3）用单纯形法求解其对偶问题； （4）对比（2）与（3）中每步计算得到的结果。解：（1）设对应于上述约束条件的对偶变量分别为y1,y2, y3 ；则由原问题和对偶问题，可以直接写出对偶问题为： Max Z'=2 y1+4 y2+3 y3 s.t 3y1+4 y2+2 y3 60 2y1+y2+2 y3 40 y1 +3y2 +2 y3 80 y1,y2,y3 0 （2）用对偶单纯形法求解原问题（添加松弛变量x4 ,x5 , x6 ）MaxZ= -60 x1 -40x2-80x3 +0x4 +0x5 +0x6 s.t -3x1 -2x2- x3+ x4 =-2 -4x1-x2-3x3+x5=-4 -2 x1-2 x2-2 x3+x6=-3

X i, X2 , X3 0 建立此问题的初始单纯形表，可见: 从表中可以看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需进行迭代运算。 换出变量的确定，计算min (-2,-4, -3)=-4，故x为换出变量。换入变量的确定，计算得15,40, 80/3,故x i为换入变量。 由表可知，X6为换出变量。X2为换入变量。然后继续画单纯形表:

X i, X2 , X3 0

可得X4为换出变量，X3为换入变量。继续做单纯形表: 所以此问题的最优解为X= （11/10,19/30, 1/10）,此对偶问题的最优解为Y二（16,12,30），原问题的最小值为118/3. （3）MaxZ '2 y1+4 y2 +3 y +0 y +0 * +0 y S.t 3 y1+4 y2+2 y3+ y4=60 2 y1 + y2 +2 y 3 + y =40 y1 +3y2+2 出 + y6=80 y1, y2, y3, y4, y5, y6 0 然后建立单纯形表，可得

运筹学--线性规划问题最优解的确定与改进

线性规划问题最优解的确定与改进 线性规划是运筹学的一个重要分支。自1947年丹捷格（G.B.Dantzig ）提出了一般线性规划问题求解的方法——单纯形法之后，线性规划在理论上趋向成熟，在实用中日益广泛与深入。线性规划最优解求解问题，在《运筹学》本科版给出了图解法和单纯形法。 一般线性规划问题的标准型为： 1 max (14)n j j i z c x ==-∑ 1,1,2(15)0,1,2,(16) n i j j i j j a x b i m x j n ===-≥=-?∑???? 满足约束条件（1-5）式、（1-6）式的解12(,,,)T n X x x x = ，称为线性规划问题的可行解，其中使目标函数达到最大值的可行解称为最优解。 2009年中国科教创新导刊，第三十期李高秀写的《线性规划中最优解的准确确定》中详细介绍了图解法的过程，图解法适合于二元线性规划问题，对于多元线性规划问题图解法相对较难。 图解法过程： 1 线性目标函数最值的分析 对于线性目标函数Z=ax+by ，若b ≠0时，目标函数可变为a z y x b b =-+，则是直线a z y x b b =-+在y 轴上的截距。 (1)b>0时，随着直线a z y x b b =-+的平移，直线在与可行域有公共点的条件下，它在y 轴上的截距 z b 最大时z 最大；当z b 最小时z 最小。 (2)b<0时，随着直线a z y x b b =-+的平移，直线在与可行域有公共点的条件下，它在y 轴上的 截距z b 最大时z 最小；当z b 最小时z 最大。 由以上两点可知，要求线性目标函数z=ax+by 的最大最小值要注意y 的系数b 的正负和平移直线在y 轴上的截距。 2 在图上分别作出约束函数和目标函数，平移目标函数线到可行域的交点时，要把目标函数的斜率与相交于这一点的直线的斜率进行比较 上述的最值分析是确定平移目标函数的大概方向，而这次是确定最优解的确凿位置。斜率比较大

考虑如下线性规划问题

考虑如下线性规划问题: Min z=60 x+402x+803x 1 s、t、3 x+22x+3x≥2 1 4 x+2x+33x≥4 1 2 x+22x+23x≥3 1 x,2x,3x≥0 1 要求:(1)写出其对偶问题; (2)用对偶单纯形法求解原问题; (3)用单纯形法求解其对偶问题; (4)对比(2)与(3)中每步计算得到的结果。 解:(1)设对应于上述约束条件的对偶变量分别为 y,2y,3y;则由原问题 1 与对偶问题,可以直接写出对偶问题为: Max Z’=2 y+42y+33y 1 s、t 3 y+42y+23y≤60 1 2 y+2y+23y≤40 1 y+32y+23y≤80 1 y,2y,3y≥0 1 (2)用对偶单纯形法求解原问题(添加松弛变量 x,5x,6x) 4 MaxZ= -60 x-402x-803x+04x+05x+06x 1 s、t -3 x-22x-3x+4x=-2 1 -4 x-2x-33x+5x=-4 1 -2 x-22x-23x+6x=-3 1

x,2x,3x≥0 1 建立此问题的初始单纯形表,可见: 从表中可以瞧到,检验数行对应的对偶问题的解就是可行解。因b列数字为负,故需进行迭代运算。 换出变量的确定,计算min(-2,-4,-3)=-4,故 x为换出变量。 5 换入变量的确定,计算得15,40,80/3,故 x为换入变量。 1 由表可知, x为换出变量。2x为换入变量。然后继续画单纯形表: 6

可得 x为换出变量,3x为换入变量。继续做单纯形表: 4 所以此问题的最优解为X=(11/10,19/30,1/10),此对偶问题的最优解为Y=(16,12,30),原问题的最小值为118/3、 (3)MaxZ’=2 y+42y+33y+04y+05y+06y 1 s、t 3 y+42y+23y+4y=60 1 2 y+2y+23y+5y=40 1 y+32y+23y+6y=80 1 y,2y,3y,4y,5y,6y≥0 1 然后建立单纯形表,可得

线性规划模拟练习

综合练习 一、填空题 1、线性规划的解有唯一最优解、无穷多最优解、 无界解 和无可行解四种。 2、在求运费最少的调度运输问题中，如果某一非基变量的检验数为4，则说明 如果在该空格中增加一个运量运费将增加4 。 3、“如果线性规划的原问题存在可行解，则其对偶问题一定存在可行解”，这句话对还是错？ 错 4、如果某一整数规划： MaxZ=X 1+X 2 X 1+9/14X 2≤51/14 -2X 1+X 2≤1/3 X 1,X 2≥0且均为整数 所对应的线性规划（松弛问题）的最优解为X 1=3/2，X 2=10/3，MaxZ=6/29，我们现在要对X 1进行分枝，应该分为 X 1≤1 和 X 1≥2 。 5. 假设某线性规划的可行解的集合为D ，而其所对应的整数规划的可行解集合为B ，那么D 和B 的关系为 D 包含 B 6. 已知下表是制订生产计划问题的一张LP 最优单纯形表（极大化问题，约束条 问：（1）写出B -1 =???? ? ??---1003/20.3/131 2 (2)对偶问题的最优解： Y ＝（5，0，23，0，0）T 7. 极大化的线性规划问题为无界解时，则对偶问题_无解_________； 8. 知下表是制订生产计划问题的一张LP 最优单纯形表（极大化问题，约束条件

问：(1)对偶问题的最优解： Y ＝(4,0,9,0,0,0)T （2）写出B -1= ??? ? ? ??611401102 二、计算题 1、已知线性规划 MaxZ=3X 1+4X 2 1+X 2≤5 2X 1+4X 2≤12 3X 1+2X 2≤8 1,X 2≥0 2）若C 2从4变成5，最优解是否会发生改变，为什么？ 3）若b 2的量从12上升到15，最优解是否会发生变化，为什么？ 4）如果增加一种产品X 6，其P 6=(2,3,1)T ，C 6=4该产品是否应该投产？为什么？ 解： 1)对偶问题为 Minw=5y1+12y2+8y3 y1+2y2+3y 3≥3 y1+4y2+2y 3≥4 y1,y2≥0 2)当C 2从4变成5时， σ4=-9/8 σ5=-1/4 由于非基变量的检验数仍然都是小于0的，所以最优解不变。 3）当若b 2的量从12上升到15 X ＝9/8

图解法和单纯形法求解线性规划问题

图解法和单纯形法求解以下线性规划问题 1.1 图解法解线性规划问题 只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下： (1)以变量x1为横坐标轴，x2为纵坐标轴，适当选取单位坐标长度建立平面坐标直 角坐标系。由变量的非负性约束性可知，满足该约束条件的解均在第一象限内。 (2)图示约束条件，找出可行域（所有约束条件共同构成的图形）。 (3)画出目标函数等值线，并确定函数增大（或减小）的方向。 (4)可行域中使目标函数达到最优的点即为最优解。 然而，由于图解法不适用于求解大规模的线性规划问题，其实用意义不大。 1.2 单纯形法解线性规划问题 它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。 单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。 单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 1.3 线性规划问题的标准化 使用单纯形法求解线性规划时，首先要化问题为标准形式

线性规划问题经典习题

线性规划问题 1线性规划下的非线性问题 1.1线性规划下的距离问题 已知220 240330x y x y x y +-≥?? -+≥??--≤? ，当x ，y 取何值时（1 取得最大值？（2）()222x y ++取 得最小值？ 1.2线性规划下的斜率问题 已知220 240330 x y x y x y +-≥??-+≥??--≤? ，（1）当x ，y 取何值时，11y x ++取得最大值？（2）求3 22x y --取值范围。 1.3线性规划下的向量问题 （1）点P （x ，y ）满足不等式组10 5702x y x y y -+≥?? --≤??≥-? ，i 为x 轴正方向上的单位向量，则向量OP 在向量i 方向上的投影的最大值是____________ （2） 已知(A ，O 是原点，点P （x ，y ） 的坐标满足0200 y x y -

2.非线性规划下的线性问题 （1）实数x ，y 满足2222101212x y x y x y ?+--+≥? ≤≤??≤≤? ，则x+y 取得最小值时，点（x ，y ）的个数 是 ． （2）定义[]x 表示不超过x 的最大整数，又设x ，y 满足方程[][]313 435y x y x ?=+??=-+?? ，如果x 不 是整数，则x+y 的取值范围是 ． 3.非线性规划下的非线性问题 (1)已知钝角三角形ABC 的最大边长为2，其余两边长为x ，y ，则以（x ，y ）为坐标的点表示平面区域的面积是 ． (2)已知实数x ，y 满足不等式组226290 2312x y x y x y ?+--+≤? ≤≤??≤≤? ， 则 x 取值范围 是 ． 4线性规划的逆问题 4.1线性约束条件中的参数问题 （1）已知x ，y 满足140x x y ax by c ≥?? +≤??++≤? ，且目标函数2z x y =+的最大值是7，最小值是1， 则 _______ a b c a ++= (2)设m 为实数，若{}22 250(,)30(,)250x y x y x x y x y m x y ??-+≥????-≥?+≤?????? +≥??? ，则m 的取值范围 是 ． 4.2目标函数中的参数问题 （1）已知变量x ，y 满足的约束条件为23033010x y x y y +-≤?? +-≥??-≤? ，若目标函数z=ax+y （其中a>0） 仅在点（3，0）处取得最大值，则a 的取值范围是 ． （2）已知x ，y 满足4335251x y x y x -≤-?? +≤??≥? ，设z=ax+y （其中a>0），若当z 取得最大值时对应的 点有无数多个，求a 的值。 （3）在平面直角坐标系xOy ，已知平面区域{(,)|1,A x y x y =+≤且0,0}x y ≥≥，则平

线性规划及单纯形法习题

第一章 线性规划及单纯形法习题 1.用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。 （1）??? ??≥≥+≥++=0,42266432min 2121212 1x x x x x x x x z (2) ??? ??≥≥+≥++=0,12432 223max 2 121212 1x x x x x x x x (3) ?? ? ??≤≤≤≤≤++=8 3105120 106max 21212 1x x x x x x z (4) ??? ??≥≤+-≥-+=0,2322 265max 1 2212121x x x x x x x x z 2.将下列线性规划问题化成标准形式。 (1)????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43214321432143214321,0,,2321422 245243min x x x x x x x x x x x x x x x x x x x x z (2) ????? ? ?≥≤≥-++-≤-+-=++-+-=无约束 32143213213213 21,0,023*******min x x x x x x x x x x x x x x x x z 3.对下列线性规划问题找出所有基本解，指出哪些是基可行解，并确定最优解。 (1) ??? ?? ? ?=≥=-=+-+=+++++=)6,,1(0231024893631223min 61432143213 21Λj x x x x x x x x x x x x x x z j (2) ??? ??=≥=+++=+++++-=)4,,1(0102227 4322325min 432143214321Λj x x x x x x x x x x x x x z j 4.分别用图解发法和单纯形法求解下述问题，并对照单纯形表中的各基本可行解对应图解法中可行域的哪一顶点。

线性规划问题的最优解

线性规划问题的最优解 引言 线性规划是运筹学的一个基本分支，其应用极其广泛，其作用以为越来越多的人所重视。线性规划主要就实际问题抽象成数学形式，即求一组变量的值，在满足一定的约束条件下，是某个目标达到最小或最大，而这些约束条件用可以用一组线性不等式或线性方程来表示。而求得目标函数的最优解尤为重要，本文就线性规划问题的最优解求解方法作出阐述，并举出实例加以强化，同时也指出了线性规划问题应用于生产与运作管理的重要性。 1.线性规划问题的最优解探讨 1.1线性规划问题的提出 考虑下面的线性规划问题的标准型： 目标函数： CX Z =min (1) 约束条件： ? ??≥=0X b AX (2) 其中，),,,(21n c c c C =,T n x x x X ),,,(21 =,T m b b b b ),,,(21 =,n m ij a A ?=)(阶矩阵。设B 是A 中m 个线性无关的列向量构成的一个基，m m ij a B ?=)( 阶矩阵，这样将矩阵A 分成两个部分，即A=),(N B ,X=),(N B X X ,C=()N B C C ,,B X ,B C 为基B 对应的非基变量和系数，N X ,N X 为N 对应的非基变量和系数，这样将线性规划问题改写为： minZ ()N B C C ,=?? ? ???B B X X (3) 约束条件：

?????≥=?? ????0),(N B N B X X b X X N B (4) 经过矩阵变换，得出关于基B 的标准型如下： 1min -=B C Z B +(N C -1-B C B N)N X (5) 约束条件： ???≥=+--0,11N B N B X X b B NX B X (6) T m b b b b B ),,,(' '21'1 =- ?????? ? ? ? =++++++-mn mm mm n m m n m m a a a a a a a a a N B 212221 2121111 将（5）（6）展开为： =Z min ' 1i m i i b c ∑=+ ∑ +=n m j 1 (' 1 ij m i i j a c c ∑=-)j x (7) 约束条件： i n m j j ij i b x a x '1 ' =+ ∑+= ,m i ,,2,1 = (8) 0≥j x ,n j ,,2,1 = (9) 令 ' 1 0i m i i b c Z ∑== , =j σ' 1 ij m i i j a c c ∑=- ,n m m j ,,2,1 ++= ,称j σ为检验数。 1.2最优解判别准则 准则一：若 T m b b b X )0,,0,,,,('2'1')1( = ，为对应于基B 的基本可行解，且对于一切的 n m m j ,,2,1 ++= ，j σ>0 ，则X 为线性规划问题的最优解。

写出下列线性规划问题的对偶问题(10分)

命题人： 教研室主任： 第1页 一、写出下列线性规划问题的对偶问题（10分） 二、求解下列线性规划问题（15分） 三、分配甲、乙、丙、丁四个人去完成A 、B 、C 、D 、E 五项任务，每个人完成各项任务的时间如下表所示。由于任务数多于人数，故考虑任务E 必须完成，其它4项中可任选3项完成，试确定最优分配方案，使完成任务的总时间为最少。（15分） 四、某河流中有几个岛屿，如下图所示。从两岸至各岛屿及各岛屿之间的桥梁编号如下图所示，在一次敌对的军事演习中，问至少应炸断几座及哪几座桥梁，才能完全切断两岸的交通联系（15分） ?????≥≥+≥++++=0 x , x ,x 62x 3x 82x 4x x x 3x 2x minz 321 213 21 321?????? ?≥≤=++≤++≥++++=无约束321 321 3213213 21x 0,x ,0x 53x 4x x 3 3x x 2x 2 4x 3x x 4x 2x 2x minz )1(????? ??????==≥===≥=∑∑∑∑====n),1,j m;,1,(i 0x )n ,1,j (b x m),1,(i a x x c minz )2(ij m 1 i j ij n 1j i ij m 1i n 1 j ij ij

命题人： 教研室主任： 第2页 五、试根据下表所提供的条件，绘制出网络计划图（10分） 六、甲、乙、丙三个城市每年分别需要煤炭320、250 、350万吨，由A 、B 两处煤矿负责供应。已知煤炭年供应量为A —400万吨，B —450万吨。有煤矿至各城市的单位运价如下表所示: 单位：万元/万吨。由 于需大于求，经研究平衡决定，甲城市供应量可减少0～30万吨，乙城市需要量应全部满足，丙城市供应量不少于270万吨。试写出该运 输问题的数学模型并用表上作业法求其初始解（15分） 七、某一警卫部门，共有8支巡逻队，负责3个要害部位，A 、B 、 C 的警卫巡逻。对每个部位可分别派2～4支巡逻队，并且派出的 巡逻队数不同，各部位预期在一段时间内可能的损失有差别，具体 数字见下表，问该警卫部门应往各部位分别派多少支巡逻队，使总 的预期损失为最小？试建立动态规划模型并求解。（共20分） A 1 2 3 4 5 6 8 7 9 10 11 12 13 B C D E F

线性规划问题在实际生活中的应用

线性规划问题在实际生活中的应用 线性规划(LP)问题的求解 生活中的很多问题涉及线性规划问题，如组合投资、运输问题、生产组织问题等。本文中通过将线性规划问题的数学模型的一般形式转变为标准形式，从而应用单纯形法求解。但单纯形法的运算量较大，应用excel、matlab等软件求解既快又准。 1.线性规划问题的在实际应用中的作用 资源是有限的，如何通过分配有限的资源获得人们所期望的效果；在工农业生产、交通运输、资本增值等各项经济活动中，如何提高经济效益，做到耗费较少的人力物力财力，创 造出较多的经济价值 这些问题涉及分配，而线性规划为最优分配提供了工具。 线性规划研究的问题主要有两类：一是一项任务确定后，如何统筹安排，尽量做到用最少的人力物力资源去完成这一任务。二是已有一定数量的人力物力资源，如何安排使用它们，使得完成任务最多。常见的线性规划问题如：运输问题，生产的组织与计划问题，合力下料 问题，配料问题、布局问题、分派问题等 考虑约束条件中的非齐次线性方程组，设A为系数矩阵，B为增广矩阵。 线性方程组的解（即可行解）一般有三种情况：无解、唯一解、无穷解。对于上面的非其次线性方程组，当 m

运筹学试题及答案11

运筹学试题及答案 一、填空题：（每空格2分，共16分） 1、线性规划的解有唯一最优解、无穷多最优解、 无界解 和无可行解四种。 2、在求运费最少的调度运输问题中，如果某一非基变量的检验数为4，则说明 如果在该空格中增加一个运量运费将增加4 。 3、“如果线性规划的原问题存在可行解，则其对偶问题一定存在可行解”，这句话对还是错？ 错 4、如果某一整数规划： MaxZ=X 1+X 2 X 1+9/14X 2≤51/14 -2X 1+X 2≤1/3 X 1,X 2≥0且均为整数 所对应的线性规划（松弛问题）的最优解为X 1=3/2，X 2=10/3，MaxZ=6/29，我们现在要对X 1进行分枝，应该分为 X1≤1 和 X1≥2 。 5、在用逆向解法求动态规划时，f k (s k )的含义是： 从第k 个阶段到第n 个阶段的最优解 。 6. 假设某线性规划的可行解的集合为D ，而其所对应的整数规划的可行解集合为B ，那么D 和B 的关系为 D 包含 B 7. 已知下表是制订生产计划问题的一张LP 最优单纯形表（极大化问题，约束条件均为“≤”型不等 问：（1）写出B -1 =???? ? ??---1003/20.3/131 2 (2)对偶问题的最优解： Y ＝（5，0，23，0，0）T 8. 线性规划问题如果有无穷多最优解，则单纯形计算表的终表中必然有___某一个非基变量的检验数为0______； 9. 极大化的线性规划问题为无界解时，则对偶问题_ 无解_____； 10. 若整数规划的松驰问题的最优解不符合整数要求，假设X i =b i 不符合整数要求，INT （b i ）是不超过b i 的最大整数，则构造两个约束条件：Xi ≥INT （b i ）＋1 和 Xi ≤INT （b i ） ，分别将其并入上述松驰问题中，形成两个分支，即两个后继问题。 11. 知下表是制订生产计划问题的一张LP 最优单纯形表（极大化问题，约束条件均为“≤”型不等式）其中

运筹学习题

一、判断 1、在线性规划的模型中全部变量要求是整数。 ( × ) 2、如果在单纯形表中，所有的检验数都为正，则对应的基本可行解就是最优解。 ( × ) 3、一个图中的最短边一定包含在最短路内。 ( × ) 4、如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。 ( √ ) 5、在二元线性规划问题中，如问题有可行解，则一定有最优解。 ( × ) 1、在线性规划的模型中全部变量要求是整数。 ( × ) 2、产地数与销地数相等的运输问题是产销平衡运输问题。 ( × ) 3、如果在单纯形表中，所有的检验数都为正，则对应的基本可行解就是最优解。 ( × ) 4、如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。 ( √ ) 5、无圈且连通简单图G 是树图。 ( √ ) 1、运筹学主要研究对象是各种有组织系统的管理问题及生产经营活动。（ √ ） 2、运筹学的目的在于针对所研究的系统求得一个合理应用人才，物力和财力的最佳方案。（ √ ） 3、如果在单纯形表中，所有的检验数都为正，则对应的基本可行解就是最优解。（ × ） 5、运筹学最早是应用在生产管理方面。（ × ） 6、在线性规划的模型中全部变量要求是整数。（ × ） 7、在二元线性规划问题中，如问题有可行解，则一定有最优解。（ × ） 二、单项选择题 1、线性规划问题的数学模型由目标函数、约束条件和（ D ）三个部分组成。 A. 非负条件 B. 顶点集合 C. 最优解 D. 决策变量 2、对于线性规划 1212312 41 234max 24.. 34 51,,,0 z x x s t x x x x x x x x x x =-+-+=?? ++=??≥? 如果取基1110B ?? = ? ??，则对于基B 的基解为（ B ）。 A.(0,0,4,1)T X = B.(1,0,3,0)T X =