《运筹学》书上有关线性规划的作业题目
一、将给出的线性规划问题化为标准型和对偶型两种类型： Min Z = X 1 + 3X 2 + 2X 3 + 4X 4
2X 1 + 3X 2 - X 3 + X 4 = 10 S.t. 3X 1 - 2X 2 + 2X 3 - X 4 ≥ -5
X 1 - X 2 + X 3 - X 4 ≤ -3
X 1≥0 ， X 2≤ 0， X 3 ≥0 ，X 4符号不限
解：（1）令4
4
4x x x '''=-，其中440,0x x '''≥≥， 在第二个约束不等式左边加上松弛变量5x ， 在第三个约束不等式左边减去松弛变量6x ， 令
z z '=-，化min z 为max z '，则标准型为：
1234
4max 3244z x x x x x ''''=+++- 1234
41234451234461234
456231032215..30,0,,,,,0x x x x x x x x x x x s t x x x x x x x x x x x x x '''+-+-=⎧⎪'''-+-++=⎪⎨
'''-+-+-=-⎪⎪'''≥≤≥⎩
（2）设对偶变量为
123,,y y y ，对偶问题模型为：
Max 1231053w y y y =--
123123123123
123231323..224
0,0,0
y y y y y y s t y y y y y y y y y ++=⎧⎪--≤⎪⎪-++≤⎨⎪--≤⎪⎪≥≤≥⎩ 二、已知某线性规划问题的约束条件为：
2X 1 + X 2 - X 3 = 30 -X 1 + 2X 2 + X 3 - X 4 = 5
5X 2 + X 3 - 2X 4 - X 5 = 60 X j ≥0 ， j = 1, 2, … ,5
判断下列各点是否为该线性规划问题可行域的顶点。

① X = (5,20,0,20,0) ② X = (9,12,0,0,8) ③ X = (15,10,10,0,0) ④ X = (0,30,0,45,0) 解：该线性规划问题中
1215p ⎛⎫ ⎪=- ⎪ ⎪⎝⎭ 2120p ⎛⎫ ⎪= ⎪ ⎪⎝⎭ 3111p -⎛⎫ ⎪= ⎪ ⎪⎝⎭ 4012p ⎛⎫ ⎪=- ⎪ ⎪-⎝⎭ 5001p ⎛⎫ ⎪= ⎪ ⎪-⎝⎭
分别将各点带入上述约束条件：
① 不满足约束条件，故不是可行域的顶点； ② 满足约束条件，为可行域的顶点；
③ 满足约束条件，为可行域的顶点； ④ 满足约束条件，为可行域的顶点； 三、用单纯形法求解该线性规划。

Max Z = 6X 1 - 2X 2 + 2X 3 + 2X 4
X 1 + 4X 2 - 4X 3 + X 4 ≤ 6 S.t. 2X 1 - X 2 + X 3 + 3X 4 ≤ 21
-X 1 + 3X 2 + 3X 3 - X 4 ≤ 29 X 1， X 2， X 3 ， X 4 ≥ 0
解：1、求一份初始基可行解
()12341441,,,21131331A p p p p -⎛⎫ ⎪
==- ⎪
⎪--⎝
⎭
四、某饲养场饲养动物出售，设每头动物每天至少需要650g 蛋白质、3g 矿物质及6mg 维生素。

现有四种饲料可供选用，各种饲料每公斤营养成分含量及单价如下表所示，要求确定既满足动物生长的营养需要，又使费用最省的配料方案（只建模，不求解）。

解：
min z =12340.8x 0.6x 0.3x 1.5x +++
1234123412341234300x 200x 100x 400x 650
X 0.8x 0.4x 2x 3..0.6x 1.2x 0.5x 1.8x 6X ,x ,x ,x 0
s t +++≥⎧⎪+++≥⎪⎨
+++≥⎪⎪≥⎩
五、某厂生产A，B，C三种产品，每种产品都要经过甲、乙两道工序。

设该厂有两种规格的设备甲1甲2能完成甲工序；有三种规格的设备乙1，乙2和乙3能够完成乙工序。

每种设备完成每个产品的加工工时，每台设备的可用工时，每工时的费用以及每件产品的原料费用和销售价格如下表所示，其中空缺位置表示该设备不能加工该种产品，要求安排最优的生产计划，使该厂利润最大，试建立相应的线性规划模型（不求解）。

对产品A来说，设以甲1，甲2完成甲工序的产品分别为X1，X2件，转入乙工序时，以乙2，乙3完成乙工序的产品分别为X3,X4,件；对产品B来说，设以甲1，甲2完成甲工序的产品分别为X5,X6，转入乙工序时，以乙1,乙3完成乙工序的产品为X7，X8件；对产品C来说，设以甲2完成甲工序的产品为X9件，则以乙2完成乙工序的产品也
为X 9件。

由上述条件可得：
12345678x x x x x x x x +=++=+
由题目所给的数据可得解此题的数学模型为：
1256915269793948(1.50.3)()(2.50.5)()(40.8)0.15000(48)0.0511000(379)0.083000(62)0.126000(55)0.074000(63)
z x x x x x x x x x x x x x x x x =-⨯++-⨯++-⨯-⨯⨯+-⨯⨯++-⨯⨯+-⨯⨯+-⨯⨯+ 152
69793948123456789485000
37911000
623000..556000634000
,,,,,,,,0
x x x x x x x s t x x x x x x x x x x x x x +≤⎧⎪++≤⎪⎪+≤⎪⎨
+≤⎪⎪+≤⎪≥⎪⎩ Max
注：以下这道题是星期五(3月9日)早上郭老师板书过的题:在极大化问题的下列表中，六个常数a1 ，a2，a3，β，σ1，σ2之值未知（假定无人工变量），分别写出对六个未知数的约束条件，使以下各小题关于该表的说法为真。

①现行解最优，但不唯一；
②现行解不可行（指出哪个变量造成）；
③一个约束条件有矛盾；
④现行解是退化的基本可行解；
⑤现行解可行，但问题无有限最优解；
⑥现行解是唯一最优解；
⑦现行解可行，但将x1取代 X6后，目标函数能改进。

解：
121212131321512(1)0,0,0(2)0,0,0,,0(3)=00,04=3a 04>3a ;(5)0,0;
(6)0,0a X βσσβσσσσββσβσβσσσ≥<<≥≤≤>>>>≤≤≤；
但中至少一个为；或而且；(4),为人工变量，且。