下载文档原格式
第一章 线性规划及单纯形法一、写出下列线性规划的标准形式，用单纯形法求解，并指出其解属于哪种情况。
1、P55,1.3(a)21510m ax x x Z +=⎪⎩⎪⎨⎧≥≤+≤+0x ,x 8x 2x 59x 4x 3.t .s 212121 解：将模型化为标准型21510x x Z Max +=⎪⎩⎪⎨⎧≥=++=++0,,,825943..4321421321x x x x x x x x x x t s 单纯形表如下因所有检验数0j ≤σ，已达最优解，最优解是)2,1(*=X ，最优目标值为2。
由检验数的情况可知，该问题有唯一最优解。
2、 P55,1.3(b)21x x 2Z m ax +=s.t⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤0,524261552121212x x x x x x x解：将模型化为标准型21x x 2Z Max +=t s . ⎪⎪⎩⎪⎪⎨⎧≥=++=++=+0x ,...,x ,x ,5x x x ,24x x 2x 6,15x x 552152142132 单纯形表如下因所有检验数0j ≤σ，已达最优解，最优解是)0,0,2,2,2(X *=，最有目标值为217。
由检验数的情况可知，该问题有唯一最优解。
3、3212x x x Z Min -+=，t s . ⎪⎪⎩⎪⎪⎨⎧≥≤++≤+-≤-+0,,,5,822,422321321321321x x x x x x x x x x x x 解：将模型化为标准型：3212x x x Z Min -+=t s . ⎪⎪⎩⎪⎪⎨⎧≥=+++=++-=+-+0,,,5,822,422321632153214321x x x x x x x x x x x x x x x 用单纯形法迭代最优解为（0，0，4），最优值为-4。
4、43213x x x x Z Min +++=t s . ⎪⎪⎩⎪⎪⎨⎧≥=++=++-0,,,,,63,4224321421321x x x x x x x x x x 解：因为所有检验数均已非负，故已是最优解，最优解为（0，2，0，4），--10分最优目标值：6Z =*。
第一章线性规划1．1将下述线性规划问题化成标准形式1)min z＝－3x1＋4x2－2x3＋5 x4－x2＋2x3－x4＝－24xst. x1＋x2－x3＋2 x4 ≤14－2x1＋3x2＋x3－x4 ≥2x1，x2，x3≥0，x4无约束2)min z ＝2x1－2x2＋3x3＋x2＋x3＝4－xst. －2x1＋x2－x3≤6x1≤0 ，x2≥0，x3无约束1．2用图解法求解LP问题，并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解。
1)min z＝2x1＋3x24x1＋6x2≥6st2x1＋2x2≥4x1，x2≥02)max z＝3x1＋2x22x1＋x2≤2st3x1＋4x2≥12x1，x2≥03)max z＝3x1＋5x26x1＋10x2≤120st5≤x1≤103≤x2≤84)max z＝5x1＋6x22x1－x2≥2st－2x1＋3x2≤2x1，x2≥01．3找出下述LP问题所有基解，指出哪些是基可行解，并确定最优解（1）min z＝5x1－2x2＋3x3＋2x4x1＋2x2＋3x3＋4x4＝7st2x1＋2x2＋x3 ＋2x4＝3x1，x2，x3，x4≥01．4 分别用图解法与单纯形法求解下列LP 问题，并对照指出最优解所对应的顶点。
1) maxz ＝10x 1＋5x 23x 1＋4x 2≤9 st 5x 1＋2x 2≤8 x 1，x 2≥02) maxz ＝2x 1＋x 2 3x 1＋5x 2≤15 st 6x 1＋2x 2≤24 x 1，x 2≥01．5 分别用大M 法与两阶段法求解下列LP 问题。
1) minz ＝2x 1＋3x 2＋x 3 x 1＋4x 2＋2x 3≥8 st 3x 1＋2x 2 ≥6 x 1，x 2 ，x 3≥02) max z ＝4x 1＋5x 2＋ x 3. 3x 1＋2x 2＋ x 3≥18 St. 2x 1＋ x 2 ≤4x 1＋ x 2－ x 3＝53) maxz ＝ 5x 1＋3x 2 +6x 3 x 1＋2x 2 －x 3 ≤ 18 st 2x 1＋x 2 －3 x 3 ≤ 16 x 1＋x 2 －x 3＝10 x 1，x 2 ，x 3≥01231231231231234)max 101512539561515.25,,0z x x x x x x x x x st x x x x x x =++++≤⎧⎪-++≤⎪⎨++≥⎪⎪≥⎩1．61.7某班有男生30人，女生20人，周日去植树。
运筹学习题集（第一章）判断题判断正误，如果错误请更正第1章线性规划1.任何线形规划一定有最优解。
2.若线形规划有最优解，则一定有基本最优解。
3.线形规划可行域无界，则具有无界解。
4.在基本可行解中非基变量一定为0。
5.检验数λj表示非基变量Xj增加一个单位时目标函数值的改变量。
6.minZ=6X1+4X2｜X1-2X｜︳<=10 是一个线形规划模型X1+X2=100X1>=0,X2>=07.可行解集非空时,则在极点上至少有一点达到最优解.8.任何线形规划都可以化为下列标准型Min Z=∑C j X j∑a ij x j=b1, i=1,2,3……，mX j>=0,j=1,2,3,……，n:b i>=0,i=1,2,3,……m9.基本解对应的基是可行基.10.任何线形规划总可用大M 单纯形法求解.11.任何线形规划总可用两阶段单纯形法求解。
12.若线形规划存在两个不同的最优解，则必有无穷多个最优解。
13.两阶段中第一阶段问题必有最优解。
14.两阶段法中第一阶段问题最优解中基变量全部非人工变量，则原问题有最优解。
15.人工变量一旦出基就不会再进基。
16.普通单纯形法比值规则失效说明问题无界。
17.最小比值规则是保证从一个可行基得到另一个可行基。
18.将检验数表示为λ=C B B-1A-的形式，则求极大值问题时基本可行解是最优解的充要条件为λ》=0。
19.若矩阵B为一可行基，则｜B｜≠0。
20.当最优解中存在为0的基变量时，则线形规划具有多重最优解。
选择题在下列各题中，从4个备选答案中选出一个或从5个备选答案中选出2~5个正确答案。
第1章线性规划1.线形规划具有无界解是指：A可行解集合无界B有相同的最小比值C存在某个检验数λk>0且a ik<=0（i=1，2，3，……，m） D 最优表中所有非基变量的检验数非0。
2.线形规划具有多重最优解是指：A 目标函数系数与某约束系数对应成比例B最优表中存在非基变量的检验数为0 C 可行解集合无界 D 存在基变量等于03. 使函数Z=-X1+X2-4X3增加的最快的方向是：A （-1，1，-4）B （-1，-1，-4）C （1，1，4）D （1，-1，-4-）4. 当线形规划的可行解集合非空时一定A 包含原点X=（0，0，0……） B 有界C 无界D 是凸集5. 线形规划的退化基本可行解是指 A 基本可行解中存在为0的基变量 B 非基变量为C非基变量的检验数为0 D 最小比值为06. 线形规划无可行解是指 A 进基列系数非正 B 有两个相同的最小比值 C 第一阶段目标函数值大于0 D 用大M 法求解时最优解中含有非0的人工变量 E可行域无界7. 若线性规划存在可行基，则 A 一定有最优解 B 一定有可行解 C 可能无可行解 D 可能具有无界解 E 全部约束是〈=的形式8. 线性规划可行域的顶点是 A 可行解 B 非基本解 C 基本可行解 D 最优解 E 基本解9. minZ=X1-2X2，-X1+2X2〈=5，2X1+X2〈=8，X1，X2〉=0，则 A 有惟一最优解 B 有多重最优解 C 有无界解 D 无可行解 E 存在最优解10.线性规划的约束条件为 X1+X2+X3=32X1+2X2+X4=4X1，X2，X3，X4〉=0 则基本可行解是 A （0，0，4，3）B （0，0，3，4）C （3，4，0，0）D （3，0，0，-2）计算题1.1 对于如下的线性规划问题MinZ= X 1+2X 2s.t. X 1+ X 2≤4-X 1+ X 2≥1X 2≤3X 1, X 2≥0的图解如图所示。
第一章 线性规划及单纯形法习题1.用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。
（1）⎪⎩⎪⎨⎧≥≥+≥++=0,42266432min 21212121x x x x x x x x z (2) ⎪⎩⎪⎨⎧≥≥+≥++=0,12432223max 21212121x x x x x x x x(3) ⎪⎩⎪⎨⎧≤≤≤≤≤++=83105120106max 212121x x x x x x z (4)⎪⎩⎪⎨⎧≥≤+-≥-+=0,2322265max 12212121x x x x x x x x z 2.将下列线性规划问题化成标准形式。
(1)⎪⎪⎩⎪⎪⎨⎧≥≥-++-≤+-+-=-+-+-+-=无约束43214321432143214321,0,,2321422245243min x x x x x x x x x x x x x x x x x x x x z (2) ⎪⎪⎩⎪⎪⎨⎧≥≤≥-++-≤-+-=++-+-=无约束3214321321321321,0,023*******min x x x x x x x x x x x x x x x x z3.对下列线性规划问题找出所有基本解，指出哪些是基可行解，并确定最优解。
(1) ⎪⎪⎩⎪⎪⎨⎧=≥=-=+-+=+++++=)6,,1(0231024893631223min 6143214321321 j x x x x x x x x x x x x x x z j (2)⎪⎩⎪⎨⎧=≥=+++=+++++-=)4,,1(01022274322325min 432143214321 j x x x x x x x x x x x x x z j4.分别用图解发法和单纯形法求解下述问题，并对照单纯形表中的各基本可行解对应图解法中可行域的哪一顶点。
(1) ⎪⎩⎪⎨⎧≥≤+≤++=0,825943510max 12212121x x x x x x x x z (2) ⎪⎩⎪⎨⎧≥≤+≤++=0,242615532max 12212121x x x x x x x x z/5.上题（1）中，若目标函数变为21m ax dx cx z +=，讨论c,d 的值如何变化，使该问题可行域的每一顶点依次使目标函数达到最优。
习题答案选01_线性规划和单纯形法运筹学教程（胡运权主编，清华第三版）部分习题答案（第一章）1.1（1）无穷多解：α (6/5, 1/5) + (1- α) (3/2, 0)，α∈ [0,1]。
（2）无可行解；（3）x* = (10,6)，z* = 16；（4）最优解无界。
1.2（1）max z’ = 3x1 - 4x2 + 2x3 - 5x’4 + 5x’’4s.t. –4x1 + x2 –2x3 + x’4–x’’4 = 2x1 + x2 –x3 + 2x’4–2x’’4 + x5 = 14–2x1 + 3x2 + x3 –x’4+ x’’4– x6 = 2x1, x2, x3, x’4, x’’4, x5, x6 ≥ 0（2）max z’ = 2x’1 + 2x2 –3x’3 + 3x’’3s.t. x’1 + x2 + x’3 –x’’3 = 42x’1 + x2 –x’3 + x’’3 + x4 = 6x’1, x2, x’3, x’’3, x4, ≥ 01.3（1）基解：(0, 16/3, -7/6, 0, 0, 0)；(0, 10, 0, -7, 0, 0)；(0, 3, 0, 0, 7/2, 0)，是基可行解，z = 3，是最优解；(7/4, -4, 0, 0, 0, 21/4)；(0, 16/3, -7/6, 0, 0, 0)；(0, 0, -5/2, 8, 0, 0)；(1, 0, -1/2, 0, 0, 3)；(0, 0, 0, 3, 5, 0)，是基可行解，z = 0；(5/4, 0, 0, -2, 0, 15/4)；(3/4, 0, 0, 0, 2, 9/4)，是基可行解，z = 9/4；(0, 0, 3/2, 0, 8, 0)，是基可行解，z = 3，是最优解。
（2）基解：(-4, 11/2, 0, 0)；(2/5, 0, 11/5, 0)，是基可行解，z = 43/5；(-1/3, 0, 0, 11/6)；(0, 1/2, 2, 0)，是基可行解，z = 5，是最优解；(0, -1/2, 0, 2)；(0, 0, 1, 1)，是基可行解，z = 5，是最优解；最优解：α (0, 1/2, 2, 0) + (1- α) (0, 0, 1, 1)，α∈ [0,1]。
![运筹学[第一章线性规划与单纯形法]山东大学期末考试知识点复习](https://img.taocdn.com/s1/m/83512a81ba0d4a7303763a31.png)
第一章线性规划与单纯形法1．线性规划问题的数学模型(1)一般形式(2)标准型式]2．数学模型化为标准型(1)若目标函数实现最小化，则min z=-max z'(令z'=-z)(2)若约束方程为不等式，则若约束方程为“≤”不等式左端+松驰变量(≥0)=右端若约束方程为“≥”不等式左端-剩余变量(≥0)=右端(3)若存在取值无约束的变量x k(1≤k≤咒)，则在标准型中x k=x'k-x"k(其中x k=x'，x"k≥0)3．线性规划的解线性规划问题：(1)可行解：满足约束条件②和③的解X=(x1，x2，…，x n)T。
(2)最优解：使目标函数①达到最大值的可行解。
(3)基：设A为约束方程组②的m×n阶系数矩阵，设n＞m，其秩为m，B 为矩阵A中的一个m×m阶的满秩子矩阵，则称B为线性规划问题的一个基。
不失一般性，设B中每一个列向量P j(j=1，2，…，m)称为基向量，与基向量PJ对应的变量x j称为基变量。
除基变量以外的变量为非基变量。
(4)基本解：在约束方程组②中，令所有非基变量x m+1=x m+2=…=x n=0，此时方程组②有唯一解X B=(x1，x2，…，x m)T，将此解加上非基变量取0的值有X=(x1，x2，…，x m，0，0…，0)T，称X为线性规划问题的基本解。
(5)基本可行解：满足非负条件③的基本解。
(6)可行基：对应于基本可行解的基。
4．初始基可行解的确定(1)直接从A中观察到存在一个初始可行基。
(2)对所有约束条件是“≤”形式的不等式，可利用化为标准型的方法，在每个约束条件左端加上一个松弛变量，这m个松弛变量就构成一个基变量，则对应的m个向量组成的单位矩阵B就是线性规划问题的一个可行基。
(3)对所有约束条件是“≥”形式的不等式以及等式约束情况，采用人造基的方法。
即对不等式约束的左端减去一个非负的剩余变量后，再加上一个非负的人工变量；对于等式约束的左端再加上一个非负的人工变量。
运筹学第1章习题运筹学第1章线性规划与单纯形法习题详解(习题)1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。
（1）max z x1 x25x1+10x2≤50x1+x2≥1x2≤4x1，x2≥0（2）min z=x1+1.5x2x1+3x2≥3x1+x2≥2x1，x2≥0（3）max z=2x1+2x2x1-x2≥-1-0.5x1+x2≤2x1，x2≥0（4）max z=x1+x2x1-x2≥03x1-x2≤-3x1，x2≥01.2将下列线性规划问题变换成标准型，并列出初始单纯形表。
（1）min z=-3x1+4x2-2x3+5x4运筹学4x1-x2+2x3-x4=-2x1+x2+3x3-x4 14-2x1+3x2-x3+2x4 2x1，x2，x3 0，x4无约束（2）max snmzkpkzk aikxiki 1k 1xk 1mik 1(i 1,...,n)xik 0 (i=1。
n; k=1,。
,m)1.3在下面的线性规划问题中找出满足约束条件的所有基解。
指出哪些是基可行解，并代入目标函数，确定最优解。
（1）max z=2x1+3x2+4x3+7x42x1+3x2-x3-4x4=8x1-2x2+6x3-7x4=-3x1,x2,x3,x4 0（2）max z=5x1-2x2+3x3-6x4x1+2x2+3x3+4x4=72x1+x2+x3+2x4=3x1x2x3x4 01.4分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形迭代每一步相当于图形的哪一点。
（1）max z=2x1+x23x1+5x2 15运筹学6x1+2x2 24x1，x2 0（2）max z=2x1+5x2x1 42x2 123x1+2x2 18x1，x2 01.5以1.4题（1）为例，具体说明当目标函数中变量的系数怎样变动时，满足约束条件的可行域的每一个顶点，都可能使得目标函数值达到最优。
运筹学1至6章习题参考答案第1章 线性规划1.1 工厂每月生产A 、B 、C 三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－23所示．310和130.试建立该问题的数学模型,使每月利润最大．【解】设x 1、x 2、x 3分别为产品A 、B 、C 的产量，则数学模型为123123123123123max 1014121.5 1.2425003 1.6 1.21400150250260310120130,,0Z x x x x x x x x x x x x x x x =++++≤⎧⎪++≤⎪⎪≤≤⎪⎨≤≤⎪⎪≤≤⎪≥⎪⎩ 1.2 建筑公司需要用5m 长的塑钢材料制作A 、B 两种型号的窗架．两种窗架所需材料规格及数量如表1－24所示：【解设x j （j =1,2,…，10）为第j 种方案使用原材料的根数，则 （1）用料最少数学模型为10112342567368947910min 28002120026002239000,1,2,,10jj j Z x x x x x x x x x x x x x x x x x x j ==⎧+++≥⎪+++≥⎪⎪+++≥⎨⎪+++≥⎪⎪≥=⎩∑ （2）余料最少数学模型为2345681012342567368947910min 0.50.50.52800212002*********0,1,2,,10j Z x x x x x x x x x x x x x x x x x x x x x x x x j =++++++⎧+++≥⎪+++≥⎪⎪+++≥⎨⎪+++≥⎪⎪≥=⎩1.3某企业需要制定1～6月份产品A 的生产与销售计划。
已知产品A 每月底交货，市场需求没有限制，由于仓库容量有限，仓库最多库存产品A1000件，1月初仓库库存200件。
1～6月份产品A 的单件成本与售价如表1－25所示。
（2）当1月初库存量为零并且要求6月底需要库存200件时，模型如何变化。
1 3 第一章线性规划与单纯形法运筹学习题集第一章线性规划与单纯形13第一章线性规划与单纯形法运筹学习题集第一章线性规划与单纯形法复习思考题1. 试述线性规划数学模型的结构及各要素的特征。
2. 求解线性规划问题时可能出现哪几种结果?哪些结果反映建模时有错误?3. 什么是线性规划问题的标准形式?如何将一个非标准型的线性规划问题转化为标准形式?4. 试述线性规划问题的可行解、基解、基可行解、最优解的概念以及上述解之间的相互关系。
5. 试述单纯形法的计算步骤，如何在单纯形表上判别问题是具有唯一最优解、无穷多最优解、无界解或无可行解?6. 如果线性规划的标准型变换为求目标函数的极小化min z，则用单纯形法计算时如何判别问题已得到最优解?7. 在确定初始可行基时，什么情况下要在约束条件中增添人工变量?在目标函数中人工变量前的系数为(-M)的经济意义是什么?8. 什么是单纯形法计算的两阶段法?为什么要将计算分成两个阶段进行,如何根据第一阶段的计算结果来判定第二阶段的计算是否需要继续进行?9. 简述退化的含义及处理退化的勃兰特规则。
10. 举例说明生产和生活中应用线性规划的可能案例，并对如何应用进行必要描述。
11. 判断下列说法是否正确:(a) 图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的;(b) 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大;(c) 线性规划问题的每一个基解对应可行域的一个顶点;(d) 如线性规划问题存在可行域，则可行域一定包含坐标的原点;(e) 对取值无约束的变量xj，通常令xj=x′j-x″j，其中x′j?0，x″j?0，在用单纯形法求得的最优解中有可能同时出现x′j,0，x″j,0;(f) 用单纯形法求解标准型的线性规划问题时，与σj,0对应的变量都可以被选作换入变量; (g) 单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负;(h) 单纯形法计算中，选取最大正检验数σk对应的变量xk作为换入变量，将使目标函数值得到最快的增长;(i) 一旦一个人工变量在迭代中变为非基变量后，则该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果;(j) 线性规划问题的任一可行解都可以用全部基可行解的线性组合表示; (k)若X1，X2分别是某一线性规划问题的最优解，则X=λ1X1+λ2X2也是该线性规划问题的最优解，其中λ1、λ2可以为任意正的实数;(l) 线性规划用两阶段法求解时，第一阶段的目标函数通常写为minz=?ixai(xai为人工变量)，但也可写为min z=?ikixai,只要所有ki均为大于零的常数;(m)对一个有n个变量、m个约束的标准型的线性规划问题，其可行域的顶点恰好为Cmn个; (n) 单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解; (o) 线性规划问题的可行解如为最优解，则该可行解一定是基可行解; (p) 若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解;(q) 线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值，则该顶点处的目标函数值达到最优;(r) 将线性规划约束条件的“?”号及“?”号变换成“=”号，将使问题的最优目标函数值得到改善;(s) 线性规划目标函数中系数最大的变量在最优解中总是取正的值;(t) 一个企业利用3种资源生产4种产品，建立线性规划模型求解得到的最优解中，最多只含有3种产品的组合;(u) 若线性规划问题的可行域可以伸展到无限，则该问题一定具有无界解; (v) 一个线性规划问题求解时的迭代工作量主要取决于变量数的多少，与约束条件的数量关系相对较小。
练习题1.1用图解法求解下列线性规划问题，并指出各问题是具有唯一最优解、无穷多最优解、无界解或无可行解。
(a) min z=6x1+4x2(b) max z=4x1+8x2s.t.2x1+x2?13x1+4x2?1.5x1, x2?0s.t.2x1+2x2?10-x1+x2?8x1, x2?0(c) max z=x1+x2(d) max z=3x1+9x2 s.t.8x1+6x2?244x1+6x2?-122x2?4x1, x2?0s.t.x1+3x2?22-x1+x2?4x2?62x1-5x2?0x1, x2?01.2某炼油厂根据计划每季度需供应合同单位汽油15万t(吨)、煤油12万t、重油12万t。
该厂从A，B两处运回原油提炼，已知两处原油成分如表11所示。
又如从A处采购原油每t价格(包括运费、下同)为200元，B处原油每t为310元。
试求: (a)选择该炼油厂采购原油的最优决策; (b)如A处价格不变，B处降为290元/t，则最优决策有何改变?表11原油成分AB汽油1550煤油2030重油5015其他1551.3线性规划问题:max z=c1x1+x2s.t.x1+x2?6x1+2x2?10x1, x2?0试用图解法分析，问题最优解随c1(-?<c1<?)取值不同时的变化情况。
1.4将下列线性规划问题变换成标准型，并列出初始单纯形表。
(a) max z=2x1+x2+3x3+x4s.t.x1+x2+x3+x4?72x1-3x2+5x3=-8x1-2x3+2x4?1x1, x3?0， x2?0， x4无约束(b) max z=?ni=1?mk=1aikxik/pks.t.?mk=1xik?bi(i=1,…,n)?ni=1cikxik=dk(k=1,…,m)xik?0(i=1,…,n; k=1,…,m)(c) min z=?mi=1?nj=1cijxijs.t.?nj=1xij?ai(i=1,…,m)?mi=1x ij=bj(j=1,…,n)xij?0(i=1,…,m; j=1,…,n)1.5判断下列集合是否为凸集: (a) X=,,x1，x2,,x1x2?30，x1?0,x2?0,(b) X={,x1，x2,,x2-3?x21,x1?0,x2?0}(c) X={,x1，x2,,x21+x22?1} 1.6在下列线性规划问题中，找出所有基解。
指出哪些是基可行解，并分别代入目标函数，比较找出最优解。
(a) max z=3x1+5x2s.t.x1+x3=42x2+x4=123x1+2x2+x5=18xj?0(j=1, (5)(b) min z=4x1+12x2+18x3s.t.x1+3x3-x4=32x2+2x3-x5=5xj?0(j=1, (5)1.7已知线性规划问题:max z=x1+3x2s.t.x1+x3=5x1+2x2+x4=10x2+x5=4x1,…,x5?0????表12中所列的解(a)~(f)均满足约束条件???，试指出: 表中哪些解是可行解,哪些是基解,哪些是基可行解,表12序号x1x2 x3 x4 x5(a)24300(b)100-504(c)30274(d)14.540-0.5(e)02562(f)045201.8分别用图解法和单纯形法求解下列线性规划问题，并对照指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点。
(a) max z=10x1+5x2s.t.3x1+4x2?95x1+2x2?8x1, x2?0(b) max z=100x1+200x2s.t.x1+x2?500x1?2002x1+6x2?1200x1, x2?01.9已知某线性规划问题的约束条件为s.t.2x1+x2-x3=25x1+3x2-x4=304x1+7x2-x3-2x4-x5=85xj?0(j=1, (5)判断下列各点是否为该线性规划问题可行域的凸集的顶点:(a) X=(5，15，0，20，0)(b) X=(9，7，0，0，8)(c) X=(15，5，10，0，0)1.10已知下述线性规划问题具有无穷多最优解，试写出其最优解的一般表达式。
max z=10x1+5x2+5x3s.t.3x1+4x2+9x3?95x1+2x2+x3?8x1, x2?01.11线性规划问题:min z=CXAX=bX?0其可行域为R，目标函数最优值为z*，若分别发生下列情形之一时，其新的可行域为R′，新的目标函数最优值为(z*)′，试分别回答(a)(b)(c)三种情况下R与R′及z*与(z*)′之间的关系:(a) 增添一个新的约束条件;(b) 减少一个原有的约束条件;(c) 目标函数变为min z=CXλ，同时约束条件变为AX=λb, X?0 (λ,1)。
1.12在单纯形法迭代中，任何从基变量中替换出来的变量在紧接着的下一次迭代中会不会立即再进入基变量，为什么?1.13会不会发生在一次迭代中刚进入基变量的变量在紧接着的下一次迭代中立即被替换出来?什么情况下有这种可能,试举例说明。
图111.14已知线性规划问题:max z=c1x1+c2x2s.t.5x2?156x1+2x2?24x1+x2?5x1, x2?0用图解法求解时，得其可行域顶点分别为O，Q1，Q2，Q3，Q4(见图11)。
试问: c1, c2如何变化时，目标函数值分别在上述各顶点实现最优, 1.15下述线性规划问题中，分别求目标函数值z的上界z-*和下界z*:(a) max z=c1x1+c2x2s.t.a11x1+a12x2?b1a21x1+a22x2?b2x1, x2?0式中: 1?c1?3, 4?c2?6; 8?b1?12, 10?b2?14;-1?a11?3, 2?a12?5; 2?a21?4, 4?a22?6(b) max z=c1x1-c2x2s.t.-a11x1+a12x2?b1a21x1-a22x2?b2x1，x2?0式中: 2?c1?3, 4?c2?6; 8?b1?12, 10?b2?15;-1?a11?1, 2?a12?4; 2?a21?5, 4?a22?6 1.16用单纯形法求解下列线性规划问题，并指出问题的解属于哪一类。
(a) max z=6x1+2x2+10x3+8x4 s.t.5x1+6x2-4x3-4x4?203x1-3x2+2x3+8x4?254x1-2x2+x3+3x4?10x1~4?0(b) max z=x1+6x2+4x3s.t.-x1+2x2+2x3?134x1-4x2+x3?20x1+2x2+x3?17x1?1, x2?2, x3?31.17分别用大M法和两阶段法求解下列线性规划问题，并指出问题的解属于哪一类。
(a) max z=4x1+5x2+x3(b) max z=2x1+x2+x3s.t.3x1+2x2+x3?182x1+x2?4x1+x2-x3=5xj?0(j=1,2,3)s.t.4x1+2x2+2x3?42x1+4x2?204x1+8x2+2x3?16xj?0(j=1,2,3)1.18表13为用单纯形法计算时某一步的表格。
