当前位置：文档之家 › 运筹学基础及应用第四版胡运权主编课后练习答案

运筹学基础及应用第四版胡运权主编课后练习答案

  • 格式：docx
  • 大小：327.43 KB
  • 文档页数：28

下载文档原格式

  / 28

合集下载

清华大学运筹学教程胡运权主编课后习题答案

清华大学运筹学教程胡运权主编课后习题答案

8 10
x1 , x2 0
目标函数最优值（下界）为：6.4
17
第18页/共66页
l.7 分别用单纯形法中的大M法和两阶 段法求解下列线性规划问题，并指出属哪—
类解。
max Z 3x1 x2 2x3
x1 x2 x3 6
(1)
st
2x1 2x2
x3 x3
0
2
x j 0（, j 1,,3）
所以最优解为X*=(1,3/2,0,0)T
第11页/共66页
0点
A1点 A2点
max Z 2x1 x2 3x1 5x2 15
(2) st.6x1 2x2 24 x1, x2 0
11
第12页/共66页
第13页/共66页
第14页/共66页
d
x
2
，
l.5 讨论c
,
上题(1)中，若目标函数变为max Z = d的值如何变化，使该问题可行域的每个
8
第9页/共66页
1.4 分别用图解法和单纯形法求解下述 线性规划问题，并对照指出单纯形表中的各 基可行解对应图解法中可行域的哪一顶点。
max Z 10x1 5x2
(1)
st.35xx11
4 x2 2 x2
9 8
x1, x2 0
9
第10页/共66页
cj
10
5 00
CB
xB
b
x1
x2
max Z x1 x2
(3)
st
6 .
x1 10x2 5 x1
120 10
5 x2 8
唯 一 最 优 解 ，x1 10, x2 6
Z 16
max Z 5x1 6x2 2x1 x2 2

运筹学(胡运权第四版及答案)

运筹学(胡运权第四版及答案)
管理运筹学
主讲：谢先达
2014.09
联系方式 办公室：QL643 87313663 手机： 13600512360 邮箱： xxdhz@
绪
论
绪论
什么是运筹学？
运筹学发展历史 运筹学主要内容 运筹学的基本特征与基本方法
绪论
什么是运筹学？
定义：为决策机构在对其控制下业务活动进行决策 时，提供以数量化为基础的科学方法。
概念：可行解、最优解、最优值
第一章：线性规划及单纯形法
练习：靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天 500万m3，在两个工厂之间有一条流量为每天200万m3支流，第一化工厂每 天排放含有某种有害物质的工业污水2万m3 ，第二化工厂每天排放这种 工业污水1.4万m3 。从第一化工厂排出的工业污水流到第二化工厂以前， 有20%可自净化。根据环保要求，河流中工业污水的含量应不大于0.2%， 这两个工厂都需各自处理一部分工业污水，第一化工厂处理工业污水的 成本是1000元/万m3 。第二化工厂处理污水的的成本是800元/万m3 。现 问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工 厂总的处理工业污水费用最小。
-x1+x2+x3 = 4
-2x1+x2-x3 ≤ 6 x1 ≤ 0,x2 ≥ 0, x3取值无约束
第一章：线性规划及单纯形法
线性规划问题及其数学模型 线性规划图解法
单纯形法原理
单纯形法计算步骤
单纯形法的进一步讨论
第一章：线性规划及单纯形法
x2
目标函数： 约束条件： maxz=50x1+100x2 x1+x2≤300 2x1+x2≤400 x2≤250 x1≥0 ，x2≥0

运筹学基础及指导应用第四版胡运权主编课后练习问题详解

运筹学基础及指导应用第四版胡运权主编课后练习问题详解

运筹学基础及应用 习题解答习题一 P46 1.1 (a)该问题有无穷多最优解，即满足210664221≤≤=+x x x 且的所有()21,x x ，此时目标函数值3=z 。

(b)用图解法找不到满足所有约束条件的公共围，所以该问题无可行解。

1.2(a) 约束方程组的系数矩阵⎪⎪⎪⎭⎫ ⎝⎛--=1000030204180036312A4最优解()T x 0,0,7,0,10,0=。

(b) 约束方程组的系数矩阵⎪⎪⎭⎫⎝⎛=21224321A最优解Tx ⎪⎭⎫⎝⎛=0,511,0,52。

1.3(a)(1) 图解法最优解即为⎩⎨⎧=+=+8259432121x x x x 的解⎪⎭⎫⎝⎛=23,1x ，最大值235=z(2)单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式 ⎩⎨⎧=++=+++++=825943 ..00510 max 4213214321x x x x x x t s x x x x z则43,P P 组成一个基。

令021==x x得基可行解()8,9,0,0=x ，由此列出初始单纯形表 21σσ>。

5839,58min =⎪⎭⎫ ⎝⎛=θ02>σ，2328,1421min =⎪⎭⎫ ⎝⎛=θ0,21<σσ，表明已找到问题最优解0 , 0 , 231,4321====x x x x 。

最大值 235*=z (b)(1) 图解法最优解即为⎩⎨⎧=+=+524262121x x x x 的解⎪⎭⎫⎝⎛=23,27x ，最大值217=z(2) 单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式1234523124125max 2000515.. 62245z x x x x x x x s t x x x x x x =+++++=⎧⎪++=⎨⎪++=⎩21=+x x 2621+x x则3P ，4P ，5P 组成一个基。

令021==x x得基可行解()0,0,15,24,5x =，由此列出初始单纯形表21σσ>。

运筹学 胡运权 课后答案课件

运筹学 胡运权 课后答案课件

m
a ij y i c j
i1
yi 0
y
无
i
约
束
( j 1,..., n1 )
( j n1 1,..., n ) (i 1,...m 1 ) (i m 1 1,...m )
运筹学 胡运权 课后答案
2.4
运筹学 胡运权 课后答案
运筹学 胡运权 课后答案
2.9
运筹学 胡运权 课后答案
（d）
对偶问题：
max w 2y1 3 y2 5 y3
y1 2y2 y3 2
3 y1
y2 4 y3 2
4 y1 3 y2 3 y3 4
y1 0, y2 0, y3取 值 无 约 束
对偶问题：
m
m i n w b i y i i1
m
a ij y i c j
i1
（1，2章）
运筹学 胡运权 课后答案
图解法：
当 x2 2 x 11 5z经 过 运筹点 学 胡（ 运1 权， 课3 2 后） 答案时 ， z最 大 。
单纯形法：添加松弛变量化为标准形式，
max z 10x1 5x2 0x3 0x4
3x1 5 x1
4x2 2x2
x3
x4
9 8

x
j
0
( j 1, 2, 3, 4)
运筹学 胡运权 课后答案
1.6（a）
运筹学 胡运权 课后答案
运筹学 胡运权 课后答案
1.7
运筹学 胡运权 课后答案
1.8
（P36公式）表1-24中，x1，x5为基变量，g=1， h=0，l=0。
运筹学 胡运权 课后答案
1.11
运筹学 胡运权 课后答案

最新《运筹学》第四版课后习题答案

最新《运筹学》第四版课后习题答案
9）/7〈100%，所以最优解不变。
作出可行域．
x2y20
2xy16
得Q(4,8)
z最大200424082720
答：该公司安排甲、乙两种柜的日产量分别为4台和8台，可获最大利润2720元．
8．解：
设需截第一种钢板x张，第二种钢板y张，所用钢板面积zm2． 目标函数z=x＋2y，线性约束条件：
xy12
2xy15
x3y27
x0
y0
x3y27
（4）x16。
x24。
（5）最优解为x1=8，x2=0。
（6）不变化。因为当斜率1≤c1
c2
1，最优解不变，变化后斜率为1，所以最优解3
不变。
7.解：
设x，y分别为甲、乙两种柜的日产量， 目标函数z=200x＋240y，线性约束条件：
6x12y120
8x4y64
即
x0
y0
x2y20
2xy16
x0
y0
x350
得ቤተ መጻሕፍቲ ባይዱ
y100
即C(350，100)．当直线6x＋10y=0即3x＋5y=0平移到
经过点C(350，100)时，z=6x＋10y最大
12．解：
模型maxz500x1400x2
2x1≤300
3x2≤540
2x12x1≤440
1.2x11.5x2≤300
x1,x2≥0
（1）x1150，x270，即目标函数最优值是103000。
《管理运筹学》第四版课后习题解析（上
）
第
1．解：
（1）可行域为OABC。
（2）等值线为图中虚线部分。
（3）由图2-1可知，最优解为B点，最优解x=12，x15

最新《运筹学》第四版课后习题答案

最新《运筹学》第四版课后习题答案

收集于网络，如有侵权请联系管理员删除⎨= 0.6《管理运筹学》第四版课后习题解析（上）第2章 线性规划的图解法1．解：（1）可行域为OABC 。

（2）等值线为图中虚线部分。

（3）由图2-1可知，最优解为B 点，最优解 x =12， x = 15 1727图2-1；最优目标函数值 69。

72．解：（1）如图2-2所示，由图解法可知有唯一解 ⎧x 1 = 0.2，函数值为3.6。

⎩x 2图2-2（2）无可行解。

（3）无界解。

（4）无可行解。

⎨ （5）无穷多解。

⎧x = （6）有唯一解 ⎪ 1⎪ 203 ，函数值为 92 。

8 3 x = ⎪⎩ 2 33．解： （1）标准形式max f = 3x 1 + 2x 2 + 0s 1 + 0s 2 + 0s 39x 1 + 2x 2 + s 1 = 303x 1 + 2x 2 + s 2 = 13 2x 1 + 2x 2 + s 3 = 9x 1, x 2 , s 1, s 2 , s 3 ≥ 0（2）标准形式min f = 4x 1 + 6x 2 + 0s 1 + 0s 23x 1 - x 2 - s 1 = 6 x 1 + 2x 2 + s 2 = 10 7x 1 - 6x 2 = 4x 1, x 2 , s 1, s 2 ≥ 0（3）标准形式min f = x 1' - 2x 2' + 2x 2'' + 0s 1 + 0s 2-3x 1 + 5x 2' - 5x 2'' + s 1 = 70 2x 1' - 5x 2' + 5x 2'' = 50 3x 1' + 2x 2' - 2x 2'' - s 2 = 30 x 1', x 2' , x 2'' , s 1, s 2 ≥4．解： 标准形式max z = 10x 1 + 5x 2 + 0s 1 + 0s 23x 1 + 4x 2 + s 1 = 9 5x 1 + 2x 2 + s 2 = 8 x 1, x 2 , s 1, s 2 ≥ 0≤松弛变量（0，0）最优解为 x 1 =1，x 2=3/2。

运筹学基础及应用第四版胡运权主编课后练习答案

运筹学基础及应用第四版胡运权主编课后练习答案

运筹学基础及应用 习题解答习题一 P46 1。

1 (a)该问题有无穷多最优解，即满足210664221≤≤=+x x x 且的所有()21,x x ，此时目标函数值3=z . (b ）用图解法找不到满足所有约束条件的公共范围,所以该问题无可行解。

1.2(a) 约束方程组的系数矩阵⎪⎪⎪⎭⎫ ⎝⎛--=1000030204180036312A4最优解()T x 0,0,7,0,10,0=。

(b) 约束方程组的系数矩阵⎪⎪⎭⎫ ⎝⎛=21224321A最优解Tx ⎪⎭⎫⎝⎛=0,511,0,52。

1。

3(a ）（1） 图解法最优解即为⎩⎨⎧=+=+8259432121x x x x 的解⎪⎭⎫⎝⎛=23,1x ，最大值235=z（2）单纯形法首先在各约束条件上添加松弛变量,将问题转化为标准形式⎩⎨⎧=++=+++++=825943 ..00510 max 4213214321x x x x x x t s x x x x z则43,P P 组成一个基。

令021==x x得基可行解()8,9,0,0=x ，由此列出初始单纯形表 21σσ>。

5839,58min =⎪⎭⎫ ⎝⎛=θ02>σ，2328,1421min =⎪⎭⎫⎝⎛=θ0,21<σσ，表明已找到问题最优解0 , 0 , 23 1,4321====x x x x 。

最大值 235*=z(b)(1) 图解法最优解即为⎩⎨⎧=+=+524262121x x x x 的解⎪⎭⎫⎝⎛=23,27x ，最大值217=z（2） 单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式1234523124125max 2000515.. 62245z x x x x x x x s t x x x x x x =+++++=⎧⎪++=⎨⎪++=⎩21=+x x 2621+x x则3P ，4P ,5P 组成一个基。

令021==x x得基可行解()0,0,15,24,5x =，由此列出初始单纯形表21σσ>。

运筹学基础及应用第四版胡运权主编课后练习答案【精】

运筹学基础及应用第四版胡运权主编课后练习答案【精】

运筹学基础及应用 习题解答习题一 P46 1.1 (a)该问题有无穷多最优解，即满足210664221≤≤=+x x x 且的所有()21,x x ，此时目标函数值3=z 。

(b)用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。

1.2(a) 约束方程组的系数矩阵⎪⎪⎪⎭⎫ ⎝⎛--=1000030204180036312A4最优解()T x 0,0,7,0,10,0=。

(b) 约束方程组的系数矩阵⎪⎪⎭⎫⎝⎛=21224321A最优解Tx ⎪⎭⎫⎝⎛=0,511,0,52。

1.3(a)(1) 图解法最优解即为⎩⎨⎧=+=+8259432121x x x x 的解⎪⎭⎫⎝⎛=23,1x ，最大值235=z(2)单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式 ⎩⎨⎧=++=+++++=825943 ..00510 max 4213214321x x x x x x t s x x x x z则43,P P 组成一个基。

令021==x x得基可行解()8,9,0,0=x ，由此列出初始单纯形表 21σσ>。

5839,58min =⎪⎭⎫ ⎝⎛=θ02>σ，2328,1421min =⎪⎭⎫ ⎝⎛=θ0,21<σσ，表明已找到问题最优解0 , 0 , 231,4321====x x x x 。

最大值 235*=z (b)(1) 图解法最优解即为⎩⎨⎧=+=+524262121x x x x 的解⎪⎭⎫⎝⎛=23,27x ，最大值217=z(2) 单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式1234523124125max 2000515.. 62245z x x x x x x x s t x x x x x x =+++++=⎧⎪++=⎨⎪++=⎩21=+x x 2621+x x则3P ，4P ，5P 组成一个基。

令021==x x得基可行解()0,0,15,24,5x =，由此列出初始单纯形表21σσ>。

清华大学胡运权运筹学

清华大学胡运权运筹学

cx°-cx* >0;
V是maxZ = C*X的S优解, 故 /
C*X*-C'X°>0;
Jr
(C*-C)(X*-X°)
= C(X°-X*) + C*(X*-X°)>0
page 25 7 April 2015
25
School of Management
第一章习题解答
1.11考虑线性规划问题
□
minZ =叫 +2JC2 + — 4X4
□
行域的每个顶点依次使目标函数达到最优。 鲤. 锒剎曷錄里姉取妾加下.
c广
cd
0
0
基b Xi x2
x3
d
x2 3/ 0 1
5/14
2
X4 j
-3/4
c
page 14
7 April 2 ns
Xi 1 1 0
Qi—'0
0
-2/14 ^W35
-
3/14d- i
第一章习题解答
□ □
当c/d在3/10到5/2之间时最优解为图中 的A 点；当c/d大于5/2且c大于等于0时最优解 为图中 的B点；当c/d小于3/10且d大于0时最优 解为图中
Bi. ■
规划问题的 maxZ = C1 X (AX =b
□
最优解, 证明[在x >0这两点连线
■
上的所有点也是 对于任何0 < a < 1, 两点连线」:的点¥满足:
X =aX⑴+(l-a)JT2)也是可行解, 且
CTX = CTaXG) +Cf\l-a)X(2y
=CTaXay -aCrX(2} +CrX
School of Management

运筹学基础与应用课后习题答案(第一二章习题解答)

运筹学基础与应用课后习题答案(第一二章习题解答)

运筹学基础及应用 习题解答习题一 P46 1.1 (a)该问题有无穷多最优解，即满足210664221≤≤=+x x x 且的所有()21,x x ，此时目标函数值3=z 。

(b)用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。

1.3 (a)4(1) 图解法最优解即为⎩⎨⎧=+=+8259432121x x x x 的解⎪⎭⎫⎝⎛=23,1x ，最大值235=z(2)单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式 ⎩⎨⎧=++=+++++=825943 ..00510 max 4213214321x x x x x x t s x x x x z则43,P P 组成一个基。

令021==x x得基可行解()8,9,0,0=x ，由此列出初始单纯形表21σσ>。

5839,58min =⎪⎭⎫⎝⎛=θ02>σ，2328,1421min =⎪⎭⎫ ⎝⎛=θ 新的单纯形表为0,21<σσ，表明已找到问题最优解0 , 0 , 231,4321====x x x x 。

最大值 235*=z (b) (1) 图解法\\最优解即为⎩⎨⎧=+=+524262121x x x x 的解⎪⎭⎫⎝⎛=23,27x ，最大值217=z(2) 单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式1234523124125max 2000515.. 62245z x x x x x x x s t x x x x x x =+++++=⎧⎪++=⎨⎪++=⎩则3P ，4P ，5P 组成一个基。

令021==x x得基可行解()0,0,15,24,5x =，由此列出初始单纯形表21=+x x 2621+x x21σσ>。

245min ,,461θ⎛⎫=-= ⎪⎝⎭02>σ，1533min ,24,522θ⎛⎫== ⎪⎝⎭新的单纯形表为0,21<σσ，表明已找到问题最优解11x =，27 2x =，3152x =，40x =，50x =。

运筹学基础及应用第四版胡运权主编课后练习答案

运筹学基础及应用第四版胡运权主编课后练习答案

运筹学基础及应用第四版胡运权主编课后练习答案一、线性规划1. 求解下列线性规划问题：max z = 3x1 + 2x2s.t.2x1 + x2 ≤ 8x1 + 2x2 ≤ 6x1, x2 ≥ 0答案：首先将约束条件化为标准形式，得到：max z = 3x1 + 2x2 + 0s1 + 0s2s.t.2x1 + x2 + s1 = 8x1 + 2x2 + s2 = 6x1, x2, s1, s2 ≥ 0通过单纯形法求解，得到最优解为：x1 = 2, x2 = 2，最优值为8。

2. 求解下列线性规划问题的对偶问题：min z = 2x1 + 3x2s.t.x1 + 2x2 ≥ 42x1 + x2 ≥ 6x1, x2 ≥ 0答案：原问题的对偶问题为：max z' = 4y1 + 6y2s.t.y1 + 2y2 ≤ 22y1 + y2 ≤ 3y1, y2 ≥ 0通过单纯形法求解，得到最优解为：y1 = 1, y2 = 1，最优值为10。

二、非线性规划1. 求解下列非线性规划问题：min f(x) = x^2 + 2x + 3s.t.x ∈ [0, 4]答案：首先求导数，得到f'(x) = 2x + 2。

令导数等于0，得到x = -1。

由于x ∈ [0, 4]，所以只需考虑x = 0和x = 4。

计算f(0) = 3，f(4) = 31。

因此，最小值为3，对应的x = 0。

2. 求解下列非线性规划问题：max f(x) = x^3 - 3x^2 + 4s.t.x ∈ [0, 3]答案：首先求导数，得到f'(x) = 3x^2 - 6x。

令导数等于0，得到x = 0或x = 2。

计算f(0) = 4，f(2) = 2，f(3) = 2。

因此，最大值为4，对应的x = 0。

三、整数规划1. 求解下列整数规划问题：max z = 3x1 + 2x2s.t.x1 + 2x2 ≤ 8x1, x2 ∈ Z答案：通过分支定界法求解，得到最优解为：x1 = 2, x2 = 3，最优值为10。

运筹学基础及应用第四版胡运权主编课后练习答案

运筹学基础及应用第四版胡运权主编课后练习答案

运筹学基础及应用 习题解答习题一 P46 1.1 (a)该问题有无穷多最优解，即满足210664221≤≤=+x x x 且的所有()21,x x ，此时目标函数值3=z 。

(b)用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。

1.2(a) 约束方程组的系数矩阵⎪⎪⎪⎭⎫ ⎝⎛--=1000030204180036312A4最优解()T x 0,0,7,0,10,0=。

(b) 约束方程组的系数矩阵⎪⎪⎭⎫ ⎝⎛=21224321A最优解Tx ⎪⎭⎫⎝⎛=0,511,0,52。

1.3(a)(1) 图解法最优解即为⎩⎨⎧=+=+8259432121x x x x 的解⎪⎭⎫⎝⎛=23,1x ，最大值235=z(2)单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式⎩⎨⎧=++=+++++=825943 ..00510 max 4213214321x x x x x x t s x x x x z则43,P P 组成一个基。

令021==x x得基可行解()8,9,0,0=x ，由此列出初始单纯形表 21σσ>。

5839,58min =⎪⎭⎫ ⎝⎛=θ02>σ，2328,1421min =⎪⎭⎫⎝⎛=θ0,21<σσ，表明已找到问题最优解0 , 0 , 23 1,4321====x x x x 。

最大值 235*=z(b)(1) 图解法最优解即为⎩⎨⎧=+=+524262121x x x x 的解⎪⎭⎫⎝⎛=23,27x，最大值217=z(2) 单纯形法首先在各约束条件上添加松弛变量，将问题转化为标准形式1234523124125max 2000515.. 62245z x x x x x x x s t x x x x x x =+++++=⎧⎪++=⎨⎪++=⎩21=+x x 2621+x x则3P ，4P ，5P 组成一个基。

令021==x x得基可行解()0,0,15,24,5x =，由此列出初始单纯形表21σσ>。

清华大学《运筹学教程》胡运权主编课后习题答案(第一章)

清华大学《运筹学教程》胡运权主编课后习题答案(第一章)

2)c=0
3)c>0
d<0 d=0 d>0
0
c 3 d 4
A1点 A1点 A3点
A2A3线段
3 c 5 4 d 2
c 5 d 2 c 5 d 2
c 3 d 4
A2点
A1A2线段 A1点
l.6 考虑下述线性规划问题：
max Z c1 x1 c2 x2 a11 x1 a12 x2 b1 st .a21 x1 a22 x2 b2 x1 , x2 0
-1
x2
0
x3
0
x4
-M
x5
-M
x6
CB
xB
x5
x6
x4
i
-M -M 0
3 6 4
[3] 4 1
1 3 2
0 -1 0
0 0 1
1 0 0
0 1 0 0
1 3/2 4 3 6/5 9/5
cj zj
7M-4
1 2 3 1 0 0 0
4M-1
1/3 [5/3] 5/3
5M/3+1/3
-M
0 -1 0 -M
0
0 0 1 0
0
1/3 -4/3 -1/3
-7M/3+4/3
-4 -M 0
x1
0
1 0 0
x6
x4
cj zj
cj
x6
是否基 可行解
Z
(x1,x2,x3)
(x1,x2,x4) (x1,x2,x5) (x1,x2,x6)
0
0 0 7/4
61/3
10 3 -4
-7/6
0 0 0

清华大学《运筹学教程》胡运权主编课后习题答案

清华大学《运筹学教程》胡运权主编课后习题答案

0
0
0 -1/5 2/5 0
1
0 3/5 -1/5 0
0
x3
1
0
0
1
1
1 -1
cj zj
0
0
0 -1/5 -M+7/5 -M
由于上表中所有检验数都小于等于零(且非基变量检验数都 小于0)，因此已经得到唯一最优解，最优解为：
X * 25 ,9 /5 ,1 ,0 ,0 ,0 T
方法二：两阶段法
第一阶段：
4x1 x2 2x3 x4 2
(1)
stx12x1x23xx23
2x4 14 x3 x4
. 2
x1, x2, x3 0, x4无约束
minZ 2x1 2x2 3x3
(2)
st
x1 x2 x3 4 2x1 x2 x3 6
x1 0, x2 0, x3无约束
minZ 3x1 4x2 2x3 5x4
7
4 -1
1
1/3 0
0 [5/3] -1
0
5/3 0
0
5/3
-1
0 -1 -1
i
x4
x5
x6
0
10
1
0
0 1 3/2
1
00
4
0
00
0 1/3 0 3
0 -4/3 1 6/5 1 -1/3 0 9/5 0 -7/3 0
cj
0
CB
xB
b
x1
0
x1 3/5
1
0
x 2 6/5
0
0
x4
1
0
cj zj
0
4x1 x2 2x3 x41 x42 2
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

运筹学基础及应用习题解答z 3。

(b)用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。

(a)约束方程组的系数矩阵12 3 6 3 0A 8 1 4 0 23 0 0 0 0基基解是否基可行解目标函数值X1 X2 X3 X4 X5 X6P1 P2 P3163 7-60 0 0否P1 P2 P4 0 10 0 7 0 0 是10P1 P2 P50 3 0 0 72是 3习题一P46x i1-的所有X i,X2，此时目标函数值o(b)约束方程组的系数矩阵A 12 3 4A2 2 12⑻(1)图解法基 基解 是否基可行解 目标函数值X 1X 2X 3X 4P 1P 24 11否"2P 1P 3 2 0 110 是435 ~5~5P 1P 4111否—36P 2P 312是52P 2P 41否22P 3P 40 0 1 1是5最优解xT2 11 5吋omax z 10x 1 5x 2 0x 3 0x 4 3x i 4X 2 X 3st. 5x 1 2x 2 x 48 9 8 12。

min—,— — 5 3 5C j 105 0 0 C B基b X 1X 2X 3X 421143 0 X 3— 1—"5"5582110X 11C j 105 0 0 C B 基bX 1 X 2 X 3 X 4 0 X 3 9 341 0 0X 48[5] 20 1 C j Z j105令 X iX 20,0,9,8，由此列出初始单纯形表最优解即为3x1 4x2 9的解x5x 1 2x 2 81,-，最大值z 竺 2 2(2)单纯形法首先在各约束条件上添加松弛变量,将问题转化为标准形式则P 3，P 4组成一个基。

得基可行解xC j Z j0 1221 8320，min14 22新的单纯形表为C j 105 0 0 C B基b X 1X 2X 3X 435 3 5X 2— 01— —2141410X 11121—7525c jZ j14 143*35x i 1, x 2 - , X 3 0, X 4 0。

最大值 z —2 25x 2 x 3 15 st. 6x 1 2x 2 X 4 24X i X 2 X 55表明已找到问题最优解最优解即为6x 1 x i2X2 24的解x x 2 5I ，最大值z 号（2）单纯形法首先在各约束条件上添加松弛变量,将问题转化为标准形式max z 2x 1 x 2 0x 3 0x 40x 5(b则R , F 4, F 5组成一个基。

令X 1 X 2得基可行解x 0,0,15,24,5，由此列出初始单纯形表新的单纯形表为C B基bX 1X 2X 3X 4X 50 X 3 15 0 5 1 0 0 0 X 4 24 ⑹ 2 0 1 0 0 X 55111C j 2 10 0 02 10 0 0C j Z j C j2 1 00 0CB基bX 1X 2X 3X 4X 551X 315111 ——2X 443621X 510 —0 —136C jZ j1 01 0332 0,1 2。

min ,24,5 4 6 115 3 min —,24,— 5 2在约束条件中添加松弛变量或剩余变量，且令X 2 X 2 X 2 X 2 0,X 2 00 X sC j Z j1 41 40 0 0 -42_ 1 0,表明已找到问题最优解X 11， X 227一 ，X 3 215 —，X 40， X s 0。

最大2 X3 X 3, z' z该问题转化为max z' 3X 1 X 2 X 2 2X 3 0X 4 0X 5st.2x 1 3x 2 3x 2 4x 3 x 4 I 11I 4X 1 X 2 X 2 2X 3 X sI 11 I3x 1 x 2 x 2 3x 3 6IMI12其约束系数矩阵为在A 中人为地添加两列单位向量P 7,P 8令 max z'3X 1 X 2 X 20x 4 0X 5 M X 6 Mx y(b)在约束条件中添加松弛变量或剩余变量，且令X 3X 3 X 3 X 3 0,X 3 0 z' z该问题转化为X i , X 2, X 3, X 3, X 4, X 5其约束系数矩阵为表在上述线性规划问题中分别减去剩余变量x 4,x 6,x 8,再加上人工变量x 5, x 7,x 9,得max z 2x 1x 22x 30x 4Mx 50x 6Mx 70x 8Mx 9C j Z j3 7M 11 2 5M 0 M 0max z' 3x 15x 2X3X30x 40x 5st.X 1 2x 2 X 3I2x 1x 23x 3x-i x 25x 35X 3X 3 3x 3X 4 X51016在A 中人为地添加两列单位向量P 7,P 8令max 3X 15X 2X 3 X 30X 4 0X 5 M X 6 MX 7N X 2 X 3 X 4 X 52X I X 3 X 6 X 7 2 2X 2 X 3 X 8 X 9 0 X i ,X 2,X 3,X 4,X 5,X 6,X 7,X 8,X 9解2:两阶段法。

现在上述线性规划问题的约束条件中分别减去剩余变量X 4,X 6,X 8,再加上人工变量X 5,X 7,X 9,得第一阶段的数学模型s,t.由单纯形表计算结果可以看出，40且a i4 0(i 1,2,3)，所以该线性规划问题有无界解C j 0 0 0 0 1 0 1 0 1C b 基 b X 1X 2X 3X 4X 5X 6X 7X 8X 9i1 X 5 6 1 1 1 1 1 0 0 0 06 1 X7 2 2 0 1 0 0 1 1 0 01 X 9 0 0[2]111C j Z j1311111 X 5 6 1 0 3/2 1 1 0 0 1/21/ 24 1 x 7 2 2 0 [1] 0 0 1 1 0 020 x 2 0 0 1 1/2 0 0 0 0 1/ 2 1/ 2C j Z j 15/2110 132 21 X 5 3 [4] 0 0 1 1 3/23/21/2 1/ 2 3/40 X 3 2 2 0 1 0 0 1 1 0 0 0 X 2 1 111/ 2 1/ 21/2 1/ 2C j Z j 00 1 0112 x 1 3/4 1 0 0 1/ 4 1/ 4 3/8 3/8 1/8 1/ 82 X3 7/2 0 0 1 1/ 2 1/2 1/4 1/4 1/41/41 x2 7/411/41/41/81/83/8 3/8据此可列出单纯形表0 0 0 0 1 0 1 0 1C j Z j3 7 7第一阶段求得的最优解 X *(―, —, —,0,0,0,0,0,0) T ,目标函数的最优值4 4 2 C j Z j2 1 2 0 0 0 0iC b 基bX 1X 2X 3X 4X 6X 82 X 1 3/4 1 0 0 1/4 3/81/82 X3 7/2 0 0 1 1/2 1/4 1/4 1 x 2 7/411/41/83/8因人工变量x 5x 7x 90，所以X (-,丄，丄，0,0,0,0,0,0) T是原线性规划问题的基可4 4 2行解。

于是可以进行第二阶段运算。

将第一阶段的最终表中的人工变量取消， 并填入原问题的目标函数的系数，进行第二阶段的运算，见下表。

现在上述线性规划问题的约束条件中分别减去剩余变量X 4, X 5,再加上人工变量 X 6, X 7,得第40且a i4 0(i 1,2,3)，所以原线性规划问题有无界解。

在上述线性规划问题中分别减去剩余变量X 4,X 6, X 8,再加上人工变量X 5, X 7,X 9,得z 2x 4 3X 2 X 3 0X 4 0X 5 M X 6 M X 7X i 4X 2 2X 3 X 4 X 683X I 2X 2 X 5 X 7 6X i ，X 2，X 3，X 4，X 5，X 6，X 7，X 8，X 9 097。

X 存在非基变量检验数 3 0，故该线性规划问题有无穷多最优解。

C j Z j 0 5/43/8 9/8 C j2 1 2 0 M 0 M0 MC b 基 bX 1 X 2X 3X 4X 5X 6 X 7iM x 6 8 1[4] 2 1 0 1 0 2 Mx 7 632113C j Z j2 4M3 6M1 2M M M 0 03 x 2 2 1/4 1 1/2 1/4 0 1/4 0 8 M X 72[5/2] 01 1/2 1 1/2 14/55 5 “ 1 3 1M 3M 3C j Z j——M 0 M -M4 22 4 22 43 x 29/50 1 3/53/10 1 /10 3/10 1/102 X 4/512/51/52/51/52/5C j Z j 0 0 0 1/2 1/2 M 1/2 M 1/2其中 M 是一个任意大的正数。

据此可列出单纯形表由单纯形表计算结果可以看出，最优解* 4 9 TX (― , —,0,0,0,0,0) T，目标函数的最优解值5 5由表中计算结果可以看出,min s,t.*4 z 2 —3 55现在上述线性规划问题的约束条件中分别减去剩余变量 X 4, X 5,再加上人工变量 X 6, X 7,得第X i 4x 2 2x 3 X 4 X 683x i 2X 2 X 5 X 7 6第一阶段求得的最优解 0。

X l ,X 2,X 3,X 4,X 5,X 6,X 7,X 8,X 9 0据此可列出单纯形表以进行第二阶段运算。

将第一阶段的最终表中的人工变量取消， 并填入原问题的目标函数的一阶段的数学模型minX 6 X 7s,t,*49 TX (-,-,0,0,0,0,0)，目标函数的最优值5 54 9 T0(一,,0,0,0,0,0)因人工变量x 6x 7z * 2 43 97。

由于存在非基变量检验数3 0,故该线性规划问题有无穷多最优55解。

表 1-23表由单纯形表计算结果可以看出，最优解X (4,-,0,0,0,0,0) T，目标函数的最优解值5 54 X3 14/15 4/15 0 1 2/15 15 0现在上述线性规划问题的约束条件中分别减去剩余变量X4, X5,再加上人工变量X6, X7,得第解: 先将问题改写为求目标函数极大化，并化为标准形式(a) 错误。

原问题存在可行解，对偶问题可能存在可行解，也可能无可行解。

(b) 错误。

线性规划的对偶问题无可行解，则原问题可能无可行解，也可能为无界解。

(C)错误。

(d)正确。

对偶单纯形法最后一个表为所求。

min z 2x 1 2X 2 4X 3max w 2y 13y25y 3X 1 3x 2 4x 32y 1 2y 2 y 3 st.2x 1 X 2 3x 3 y 4 3对偶问题为：3y 1 S ・t.y 2 4y 3X 1 4x 2 3x 3 5 4y 1 3y2 3y 32 y i 2 4习题二 P76 写出对偶问题X 1,X 2 0,X 3无约束z 5X 16X 23x 3X 1 2X 2 2x 3 5 X 1 5X 2 X 3 3 4X 17X 2 3X 3 8X 1无约1 束,X 2 0,X 3 st .0 (b)max 对偶问题为：st.0, y 2 0, y 3无约束5y 1 3y 28y 3y 1 y 2 4y 3 52y 1 5y 2 7y 3 6 2y 1 y 23y33min w y i 无约束川2 0, y 3 0min st.z 4x 1 12X 2 X 13x 3 2X 2 2X 3X 1, X 2 , X 3 018X 3 3max z'4x i 12x 2 18X 30x 4 0x 5(b)max z'5x 1 2x 2 4x 3 0x 4 0x 5列单纯形表，用对偶单纯形法求解C jx ist.X i 3x 3 2X 2 2x 30i 1,,5X 4 X 5列单纯形表，用对偶单纯形法求解,步骤如下3 T目标值z 39。