习题解答将线性规划问题化为标准形式.doc

线性规划化为标准型线性规划是一种数学优化方法，用于在给定约束条件下寻找最优解。

在实际应用中，线性规划问题往往需要转化为标准型，以便使用现有的优化算法进行求解。

本文将介绍线性规划如何转化为标准型，并给出详细的步骤和示例。

首先，让我们来看一个简单的线性规划问题：Maximize 3x + 5y。

Subject to:2x + y ≤ 20。

-4x + 5y ≥ 10。

x, y ≥ 0。

这是一个典型的线性规划问题，我们需要将其转化为标准型。

标准型的线性规划问题具有以下形式：Maximize c^T x。

Subject to:Ax = b。

x ≥ 0。

其中，c是一个n维向量，x是一个n维变量向量，A是一个m×n的矩阵，b 是一个m维向量。

转化为标准型的关键在于将所有的约束条件转化为等式，并引入松弛变量。

对于小于等于形式的约束条件，我们引入一个松弛变量，对于大于等于形式的约束条件，我们引入一个人工变量。

同时，我们将目标函数转化为标准的形式。

在上面的例子中，我们可以将第一个约束条件转化为等式，并引入一个松弛变量：2x + y + s1 = 20。

其中，s1 ≥ 0。

将第二个约束条件转化为等式，并引入一个人工变量：-4x + 5y s2 = 10。

其中，s2 ≥ 0。

然后，我们将目标函数转化为标准的形式：Maximize 3x + 5y + 0s1 + 0s2。

现在，我们的线性规划问题已经转化为标准型，具体形式如下：Maximize c^T x。

Subject to:Ax = b。

x ≥ 0。

其中，。

c = [3, 5, 0, 0]x = [x, y, s1, s2]A = [[2, 1, 1, 0],。

[-4, 5, 0, -1]]b = [20, 10]通过上面的转化过程，我们成功将原始的线性规划问题转化为标准型。

现在，我们可以使用标准的线性规划算法对其进行求解，得到最优解x，y，s1，s2。

这样，我们就可以得到原始线性规划问题的最优解了。

第二章 线性规划73P 4. 将下面的线性规划问题化成标准形式12312312312max 2..236230316x x x s t x x x x x x x x −+⎧⎪−+≥⎪⎪+−≤⎨⎪≤≤⎪⎪−≤≤⎩解：将max 化为 min ， 3x 用45x x −代替，则1245124512451245min 2()..23()62()30316,0x x x x s t x x x x x x x x x x x x −+−−⎧⎪−+−≥⎪⎪+−−≤⎪⎨≤≤⎪⎪−≤≤⎪≥⎪⎩令221x x ′=+，则1245124512451245min12()..2(1)3()62(1)()30307,0x x x x s t x x x x x x x x x x x x ′−+−−−⎧⎪′−−+−≥⎪⎪′+−−−≤⎪⎨≤≤⎪⎪′≤≤⎪≥⎪⎩将线性不等式化成线性等式，则可得原问题的标准形式12451245612457182912456789min221..23342437,,,,,,,0x x x x s t x x x x x x x x x x x x x x x x x x x x x x ′−+−+−⎧⎪′−+−−=⎪⎪′+−++=⎪⎨+=⎪⎪′+=⎪′≥⎪⎩73P 5、用图解法求解下列线性规划问题：(1) 121212min 3..206122x x s t x x x x +⎧⎪+≥⎪⎨≤≤⎪⎪≥⎩解：图2.1的阴影部分为此问题的可行区域.将目标函数的等值线123x x c +=(c 为常数)沿它的负法线方向()13T−−，移动到可行区域的边界上.于是交点T），（812就是该问题的最优解，其最优值为36.75P 16. 用单纯形法求解下列线性规划问题：(1) 123123123123min 2..360210200,1,2,3j z x x x s t x x x x x x x x x x j ⎧=−−+⎪++≤⎪⎪−+≤⎨⎪+−≤⎪⎪≥=⎩解：将此问题化成标准形式123123412351236min 2..360210200,1,2,3,4,5,6j z x x x s t x x x x x x x x x x x x x j ⎧=−−+⎪+++=⎪⎪−++=⎨⎪+−+=⎪⎪≥=⎩以456,,x x x 为基变量，可得第一张单纯形表为以1x 为进基变量，5x 为离基变量旋转得以2x 为进基变量，6x 为离基变量旋转得1x 2x 3x 4x 5x 6x RHS z2 1 -1 0 000 4x 31 1 1 0060 5x 1-121010 6x 11 -1 0 01201x 2x 3x 4x 5x 6x RHS z0 3 -5 0 -20-204x 0 4 -5 1 -3030 1x 1-1 2 0 1010 6x 02-3-11101 注意单纯形表的格式！2 要用记号把转轴元标出来 3要记住在单纯形表的左边，用进基变量代替离基变量注（零行元素的获得）：先将目标函数化成求最小值的形式，再把所有变量移到等式左边，常数移到等式右边。

第一章 线性规划1、由图可得：最优解为2、用图解法求解线性规划： Min z=2x 1+x 2⎪⎪⎩⎪⎪⎨⎧≥≤≤≥+≤+-01058244212121x x x x x x解：由图可得：最优解x=1.6,y=6.4Max z=5x 1+6x 2⎪⎩⎪⎨⎧≥≤+-≥-0,23222212121x x x x x x解：由图可得：最优解Max z=5x 1+6x 2, Max z= +∞Maxz = 2x 1 +x 2⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤0,5242261552121211x x x x x x x由图可得：最大值⎪⎩⎪⎨⎧==+35121x x x ， 所以⎪⎩⎪⎨⎧==2321x xmax Z = 8.1212125.max 23284164120,1,2maxZ .jZ x x x x x x x j =+⎧+≤⎪≤⎪⎨≤⎪⎪≥=⎩如图所示，在（4，2）这一点达到最大值为26将线性规划模型化成标准形式：Min z=x 1-2x 2+3x 3⎪⎪⎩⎪⎪⎨⎧≥≥-=++-≥+-≤++无约束321321321321,0,052327x x x x x x x x x x x x解：令Z ’=-Z,引进松弛变量x 4≥0，引入剩余变量x 5≥0，并令x 3=x 3’-x 3’’,其中x 3’≥0,x 3’’≥0Max z ’=-x 1+2x 2-3x 3’+3x 3’’⎪⎪⎩⎪⎪⎨⎧≥≥≥≥≥≥-=++-=--+-=+-++0,0,0'',0',0,05232'''7'''5433213215332143321x x x x x x x x x x x x x x x x x x x7将线性规划模型化为标准形式Min Z =x 1+2x 2+3x 3⎪⎪⎩⎪⎪⎨⎧≥≤-=--≥++-≤++无约束，321321321321,00632442392-x x x x x x x x x x x x解：令Z ’ = -z ，引进松弛变量x 4≥0,引进剩余变量x 5≥0,得到一下等价的标准形式。

习题解答
1.2将线性规划问题化为标准形式
st.
解：令
则所求规划的标准形式为：
st.
1.4用单纯形法求解线性规划问题：
st.
解：将其化为标准形式为：
st.
设是线性规划问题的最优解。

若目标函数中用代替后，问题的最优解变为。

求证：。

证明：、在目标函数的系数变化之前之后都是问题的可行解，故有，即
（1）
同理即（2）
（1）+（2）
即
某饲养场饲养动物出售，设每头动物每天至少需要700克蛋白质、30克
矿物质、100毫克维
生素。

现有五种饲料可供选用，各种饲料每kg营养成分含量及单价如表
所示：
饲料蛋白质(g) 矿物质(g) 维生素(mg) 价格(元/kg)
1 3 1 0．5 0．2
2 2 0．5 1．0 0．7
3 1 0．2 0．2 0．4
4 6 2 2 0．3
5 18 0．5 0．8 0．8
要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。

（仅建模型）
解：设分别代表5种饲料的采购数，则模型为：
st.。

第一章线性规划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≤24x 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 ≥6x 1，x 2 ，x 3≥02) max z ＝4x 1＋5x 2＋ x 3. 3x 1＋2x 2＋ x 3≥18St. 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)m ax 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 ⽤图解法求解下列线性规划问题。

并指出问题具有惟⼀最优解、⽆穷多最优解、⽆界解还是⽆可⾏解。

1 2x , x ≥ 0 ? ≤ 2 2 1 ? .? 2 x 1 - x 2 ≥ 2st- 2 x + 3x (4) max Z = 5 x 1 + 6 x 2≤ 82 5 ≤ x ? 1 ? 5 ≤ x ≤ 10 .?max Z = x 1 + x 26 x 1 + 10 x 2 ≤ 120st ?(3) 1 2 x , x ≥ 0 ? 2 1 ? ? ? 4 x 1 + 6 x 2 ≥ 6st .?2 x + 2 x ≥ 4 (1) min Z = 2 x 1 +3 x 21 2 ? ≥ 12 2 1 ? x , x ≥ 0 .? ?2 x 1 + x 2 ≤ 2st ?3x + 4 x (2) max Z = 3x 1 + 2 x 2x , x ≥ 0 1 2该问题⽆解≥ 12 2 1 ? ? 2 x 1 + x 2 ≤ 2st .?3 x +4 x ( 2 ) max Z = 3 x 1 + 2 x 2第⼀章习题解答3 2 1x = 1, x = 1, Z = 3是⼀个最优解⽆穷多最优解，1 2x , x ≥ 0 ? 2 1 ? ? ? 4 x 1 + 6 x 2 ≥ 6st .?2 x + 2 x ≥ 4 (1) min Z = 2 x 1 +3 x 2该问题有⽆界解1 2x , x ≥ 0 ? ≤ 2 2 1 ? .? 2 x 1 - x 2 ≥ 2st- 2 x + 3x (4) max Z = 5x 1 + 6 x 2第⼀章习题解答唯⼀最优解， x 1 = 10, x 2 = 6, Z = 16 ≤ 82 5 ≤ x ?1 ? 5 ≤ x ≤ 10 .?max Z = x 1 + x 26 x 1 + 10 x 2 ≤ 120st ?(3)第⼀章习题解答运筹学教程1.2 将下述线性规划问题化成标准形式。

第二章 线性规划（LP ） §2.1 线性规划数学模型的建立LP 问题提出：苏联：康德洛维奇 1939 一、线性规划数学模型的三要素：1.决策变量(decision variable)：决策问题待定的量值。

用字母（例如X1,X2,···,Xn ）来表示可控制的因素。

每一组决策变量的实际值就表示一个具体方案。

2.目标函数（objective function ）：MaxZ=CX 或 MinZ=CX ；(衡量决策优劣的准则) 特点：（1）单一目标；（2）关于决策变量的线性函数。

（定义：课本P20）3.约束条件(constraint conditions)：s.t. (subject to) 受制于约束；AX ≤(≥，=)b 特点：若干关于决策变量的线性函数。

二、LP 数学模型的一般形式（1）繁写形式目标函数：Max （Min ）z = c1 x1 + c2 x2 + … + cn xn 约束条件：a 11 x1 + a 12 x2 + … + a 1n xn ≤ （ =, ≥ ）b1 a 21 x1 + a 22 x2 + … + a 2n xn ≤ （ =, ≥ ）b2 s.t. …… …… a m1 x1 + a m2 x2 + … + a mn xn ≤ （ =, ≥ ）bm x1 ，x2 ，… ，xn ≥ 0 （2）向量形式目标函数：Max （Min ） z = CX≤(≥，=)bXj ≥ 0 (j=1,2, …,n)其中，C=(c1 , c2 , … , cn )(价值向量) X= (x1 , x2 , … , xn )T(决策变量向量) b=(b1 , b2 , … , bm )T (限定向量)pj= (a 1j ， a 2j … a mj ) T (约束条件系数列向量) 注：矩阵相乘条件：左列=右行 (3)矩阵形式★目标函数：Max （Min ） z = CX 约束条件：∑=nj jjx p1AX ≤（=, ≥）bX≥0其中，C=(c1 , c2 , … , cn )(价值向量)X= (x1 , x2 , … , xn )T(决策变量向量)b=(b1 , b2 , … , bm )T (限定向量、资源向量)a11 a12 (1)a21 a22 … a2n (系数矩阵)A= ……a m1 a m2 … a mn三、建模的一般步骤前提假设：假设模型中有n个决策变量，m个约束条件。

第一章线性规划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人，周日去植树。