当前位置：文档之家 › 《运筹学教程》胡云权 第五版 运筹学复习

《运筹学教程》胡云权 第五版 运筹学复习

  • 格式：pptx
  • 大小：1.89 MB
  • 文档页数：141

下载文档原格式

  / 141

合集下载

运筹学教程胡云权第五版孔静静运筹学博弈论专题知识讲座

运筹学教程胡云权第五版孔静静运筹学博弈论专题知识讲座
《运筹学》课程纲领
➢ 课程性质：措施技能类 专业必须课 ➢ 课时数：1-14周，3，42课时 ➢ 课程框架
约束条件、目的最大/小化、最优方案
图
线运 性送 规问 划题
整
动
数
态
规
规
划
划
与 网 络 分
决对 策策 论论
析
➢ 考核方案：作业（40%）+考试（60%）
《运筹学》教材内容
➢ 线性规划 第一章 1-5节 ➢ 运送问题 第三章 1-3节 ➢ 整数规划 第五章 1-5节 ➢ 动态规划 第七章 1-4节 ➢ 图与网络分析 第八章 1-3节 ➢ 对策论 第十二章 1-3节 ➢ 决策论 第十三章 1-3节
严格劣势策略
Strictly dominated strategy
课堂游戏——“同学困境”
α
我
β
同伴
α B-， B-
β A， C
C， A
B+，B+
现实囚徒困境
• 宿舍卫生 • 价格战争 • 过分捕捞 • 碳排放 • 军备竞赛
思索
破解措施
• 沟通
坦白
抵赖
• 协议、协议
坦白 -8， -8
0， -10
《运筹学》课程答疑
时间：周一 8：00——10：00 12：00——18：00
地点：建工楼512 邮箱： 电话
《运筹学》
对策论
• 孔静静 • 2023年3月2日
课堂游戏——“同学困境”
请各位在不被邻桌看到旳情况下，选择α或者β 随机两人一组，鉴定成绩 成绩给定旳原则
• 若你选择α ，同伴选择β ，则你得A，同伴得C； • 若都选择α，则都得B-； • 若你选择β，同伴选择α，则你得C，同伴得A； • 若都选择β，则都得B+。

《运筹学教程》胡云权-第五版-运筹学复习

《运筹学教程》胡云权-第五版-运筹学复习

x6
10
[2]
-5
1
0
-1
1
5
3M+2
3-4M
2M-5
0
-M
0
-z
-M
x4
2
0
[7/2 ]
1/2
1
1/2
-1/2
4/7
2
x1
5
1
-5/2
1/2
0
-1/2
1/2
-
0
7M/2+8
M/2-6
0
M/2+1
-3M/2-1
-z
3
x2
4/7
0
1
1/7
2/7
1/7
-1/7
2
x1
45/7
1
0
6/7
5/7
-1/7
1/7
✓ 右端项非负
解的重要概念
可行解（或可行点）：满足所有约束条件的向量 x ( x1 , x 2 , x n )
可行域：所有的可行解的全体
D { x Ax b, x 0}
最优解：在可行域中目标函数值最大（或最小）的可行解，最优解的全体
称为最优解集合
O {x D c x c y, y D }
0
x3
0
x4
0
x5

9
4
3
4
5
[ 10 ]
1
0
0
0
1
0
0
0
1
90
40
30
7
12
0
0
0
1
90
bi
360

运筹学教程》胡云权第五版第五章图与网络分析

运筹学教程》胡云权第五版第五章图与网络分析

1S
2
3
3K
B2
2 F 2 26 J
D
H
最小支撑树问题
[例]今有煤气站A，将给一居民区供应煤气，居民区各用 户所在位置如图所示，铺设各用户点的煤气管道所需的 费用（单位：万元）如图边上的数字所示。要求设计一 个最经济的煤气管道路线，并求所需的总费用。
A
E
I
2 C
2 G4
5
1S
2
3
3K
B2
2 2F2
图的基本概念
3、顶点的次
定义5：以点v为端点的边数叫点v的次 （degree），记作deg(v)或d(v)。
图5-1中，d(v1)＝４，d(v3)=5，d(v5)=1。 次为奇数的点称作奇点，次为偶数的点称作偶点， 次为0的点称作孤立点。 次为1的点称作悬挂点，连接悬挂点的边为悬挂边。 图的次：各点的次之和。 有向图中顶点的次？
(G1)
(G) (G3)
(G2) (G4)
最小支撑树问题
图的支撑树的应用举例 【例】 某地新建5处居民点，拟修道 路连接5处，经勘测其道路可铺成如 图所示。为使5处居民点都有道路相 连，问至少要铺几条路？
【解】 该问题实为求图的支撑 树问题，共需铺4条路。 v2
v1
5
v2
3.5 4
5.5
3 v5
2
最小支撑树问题
案例分析：默登公司的联网问题
默登（Modern）公司的管理层决定铺设最先进的光纤 网络，为它的主要中心之间提供高速通信。图1中的节点显 示了该公司主要中心的分布图。虚线是铺设光缆可能的位置。 每条虚线旁边的数字表示成本（单位：百万美元）。
问：需要铺设哪些光缆使得总成本最低？
B

胡运权《运筹学教程》(第5版)配套题库-考研真题精选及课后习题(第一~三章)【圣才出品】

胡运权《运筹学教程》(第5版)配套题库-考研真题精选及课后习题(第一~三章)【圣才出品】

2．μ是关于可行流 f 的一条增广链，则在μ上有：对一切（i，j）∈μ－，有 fij＞0。（ ） [暨南大学 2019 研]
【答案】√ 【解析】由增广链定义可知，当边（i，j）属于μ的反向边集时，该条边的流量大于 0。
3．事件 j 的最早时间 TE（j）是指以事件 j 为开工事件的工序最迟必须开工时间。（ ） [暨南大学 2019 研]
零元素的最少直线数目的集合。结果如下：
4 / 113
圣才电子书 十万种考研考证电子书、题库视频学习平台

（4）在未被覆盖的元素中找最小元素，未被覆盖的行分别减去该最小元素，在出现负
数的列上整列加上最小元素，得到新矩阵 C′：
0 2 6 1 0 0 4
表 1-1-1
解：（1）先对各行减去本行的最小元素，再对各列减去本列最小元素，得到矩阵 C 如
下：
0 2 6 9
C 1 4 4 0 1 0 0 3 2 3 6 0
（2）确定独立零元素，对 C 加圈，得到
◎ 2 6 9
C
1
1
4 ◎
4
◎ 3
2
3
6
（3）由于只有 3 个独立零元素，少于系数矩阵阶数 n＝4，故需要确定能够覆盖所有
A．没有无穷多最优解 B．没有最优解 C．有无界解 D．有最优解 【答案】B 【解析】有最优解的前提是有可行解，该题无可行解，则也无最优解。
2．如果某种资源的影子价格大于其市场价格，则说明（ ）。[暨南大学 2019 研] A．该资源稀缺 B．该资源过剩 C．企业应尽快处理该资源 D．企业应充分利用该资源，开辟新的生产途径 【答案】A 【解析】当资源的影子价格不为 0 时，表明该种资源在生产中已耗费完毕；且若影子 价格大于其市场价格，说明企业应买进该种资源，该种资源稀缺。

《运筹学教程》胡云权第五版运筹学-6对策论-矩阵对策

《运筹学教程》胡云权第五版运筹学-6对策论-矩阵对策

矩阵对策的基本原理
矩阵对策的基本原理是将决策问题抽象为一个决策矩阵，其中行表示决策方 案，列表示决策因素。通过对矩阵进行分析和计算，找到最优的决策方案。
矩阵对策的应用领域
矩阵对策可以应用于各种决策问题，包括但不限于供应链管理、投资组合优化、资源分配、人力资源管理等领 域。
矩阵对策的解决方法
矩阵对策可以通过数学方法和算法来求解，例如线性规划、整数规划、动态规划等。不同的决策问题可能需要 不同的解决方法。
案例分析：矩阵对策在实际问题中的应用
本节将通过案例分析展示矩阵对策在实际问题中的应用。我们将介绍一个具体的决策问题，并演示如何使用矩 阵对学习，你已经了解了矩阵对策的基本原理、应用领域和解决方法。希望本节内容对你在运筹学领域 的学习和应用有所帮助。
《运筹学教程》胡云权第 五版运筹学-6对策论-矩 阵对策
本节将介绍运筹学中的矩阵对策，包括其概述、基本原理、应用领域、解决 方法以及在实际问题中的应用。
运筹学简介
运筹学是一门研究在资源有限的情况下如何做出最佳决策的学科。它应用数学方法和模型来协助管理者进行决 策和优化。
矩阵对策概述
矩阵对策是一种运筹学方法，通过构建决策矩阵来帮助管理者进行决策。它 可以同时考虑多个决策因素和多种决策方案，从而找到最佳决策。

运筹学胡运权第五版课件

运筹学胡运权第五版课件
运筹学胡运权第五 版课件大纲
单击此处添加副标题
汇报人：
目录
添加目录项标题 运筹学基础知识 整数规划 图论与网络优化
课件概览 线性规划 动态规划
01
添加章节标题
02
课件概览
课件简介
课程名称：运筹学胡运权第五版课件 课程内容：包括线性规划、非线性规划、整数规划、动态规划、图与网络优化等 课程目标：帮助学生掌握运筹学的基本理论和方法提高分析和解决问题的能力 课程特点：理论与实践相结合注重案例分析和实际问题的解决
最小生成树问题：在无向图中寻找最小生 成树
最大流问题：在流网络中寻找最大流
最小费用流问题：在流网络中寻找最小费 用流
网络可靠性问题：评估网络可靠性提高网 络稳定性
网络优化算法：如Dijkstr算法、Floyd算 法、Kruskl算法等
网络优化算法
最短路径算 法：Dijkstr
算法、 Floyd算法
等
图论与网络优化应用案例
物流网络优化：通过图论方 法优化物流网络降低物流成 本
社交网络优化：通过图论方 法优化社交网络提高社交网
络的稳定性和可靠性
交通网络优化：通过图论方 法优化交通网络提高交通效 率
电力网络优化：通过图论方 法优化电力网络提高电力系
统的稳定性和可靠性
感谢观看
汇报人：
课件结构
• 运筹学概述 • 线性规划 • 非线性规划 • 动态规划 • 随机规划 • 决策分析 • 网络规划 • 排队论 • 库存论 • 博弈论 • 运筹学应用案例 • 运筹学发展前景 • 运筹学与其他学科的关系 • 运筹学学习方法与技巧
课件特点
内容全面：涵盖了运筹学的基本概念、理论和方法 结构清晰：按照章节进行划分便于理解和掌握 实例丰富：提供了大量的实例和案例便于理解和应用 习题丰富：提供了大量的习题和练习便于巩固和提高

(完整版)运筹学胡运权第五版课件(第1章)

四运筹学研究的基本特点?系统的整体优化?多学科的配合?模型方法的应用五五运筹学研究的基本步骤运筹学研究的基本步骤?分析与表述问题?建立数学模型?对问题求解?对模型和模型导出的解进行检验?建立对解的有效控制?方案的实施第一章线性规划及单纯形法linearprogrammingandsimplexmethodggp11一般线性规划问题的数学模型11问题的提出例1用一块边长为a的正方形铁皮做一个无盖长方体容器应如何裁剪可使做成的容器的容积最大
（3）L.P. 的顶点与基可行解一一对应。
§1.3 单纯形法（Simplex Method）原理
3-1 预备知识：凸集与顶点
（1）凸集：对于集合C中任意两点连线段上的点，若全在C内， 则称集合C为凸集。
直观特征：图形从内部向外部凸出。
凸集
非凸集
（2）顶点：凸集中不在任意两点的连线段内部的点。
X1
转化为
（2）若约束条件为不等式，
则依次引入松弛变量或剩余变量（统称为松弛变量），
转化为等式约束条件。
约束为≥不等式，减去松弛变量，化为等式约束条件；
多 退
约束为≤不等式，加上松弛变量，化为等式约束条件。
少 补
注意：松弛变量在目标函数中系数全为0。
例：max z=2 x1+3 x2
2 x1+2 x2 12
s.t.
4x1
16
5 x2 15
x10， x2 0
标准化
max z 2x1 3x2 0x3 0x4 0x5
2x1 2x2 x3
12
s.t.
4
x1
5 x2
x4 16 x5 15
x1, x2 , x3, x4 , x5 0
（3）若决策变量xj≤0，则令

胡运权《运筹学教程》习题答案(第一章)[1]

第一章习题解答1.1 用图解法求解下列线性规划问题。

并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。

+=32min 21x x Z +=23max 21x x Z ⎪⎩⎪⎨⎧≥≥+≥+0,422664.)1(212121x x x x x x st ⎪⎩⎪⎨⎧≥≥+≤+0,124322.)2(212121x x x x x x st ⎪⎩⎪⎨⎧≤≤≤≤≤++=85105120106.max )3(212121x x x x st x x Z ⎪⎩⎪⎨⎧≥≤+−≥−+=0,23222.65max )4(21212121x x x x x x st x x Z 第一章习题解答无穷多最优解，,422664.32min )1(21212121⎪⎩⎪⎨⎧≥≥+≥++=x x x x x x st x x Z 是一个最优解3,31,121===Z x x 该问题无解⎪⎩⎪⎨⎧≥≥+≤++=0,124322.23max )2(21212121x x x x x x st x x Z 第一章习题解答85105120106.max )3(212121⎪⎩⎪⎨⎧≤≤≤≤≤++=x x x x st x x Z 唯最优解16,6,1021===Z x x 唯一最优解，该问题有无界解⎪⎩⎪⎨⎧≥≤+−≥−+=0,23222.65max )4(21212121x x x x x x st x x Z 第一章习题解答1.2 将下述线性规划问题化成标准形式。

1422245243min )1(432143214321⎪⎪⎧≤+−+−=−+−+−+−=x x x x x x x x x x x x Z .,0,,23243214321⎪⎪⎩⎨≥≥−++−无约束x x x x x x x x st ⎪⎩⎪⎨⎧≥≤≤−+−=++−+−=无约束321321321321,0,0624322min )2(x x x x x x x x x st x x x Z 第一章习题解答.2321422245243min )1(4321432143214321⎪⎪⎪⎨⎧≥−++−≤+−+−=−+−+−+−=x x x x x x x x x x x x st x x x x Z ,0,,4321⎪⎩≥无约束x x x x ⎪⎪⎩⎪⎪⎨⎧≥=−+−++−=+−+−+=−+−+−+−+−=0,,,,,232142222455243max 64241321642413215424132142413214241321x x x x x x x x x x x x x x x x x x x x x x x st x x x x x Z 第一章习题解答⎪⎪⎨⎧≥≤≤−+−=++−+−=无约束321321321321,0,0624322min)2(x x x x x x x x x st x x x Z ⎩⎪⎩⎪⎨⎧≥=++−+=−++−+−+=0,,,,6243322max 43231214323121323121323121x x x x x x x x x x x x x x st x x x x Z第一章习题解答634334max )3(3212121⎪⎪⎧=−+=++=x x x x x st x x Z 517,0,1,59,524,,1,0424321421=====⎪⎪⎩⎨=≥=++Z x x x x j x x x x j 该题是唯一最优解：）（"第一章习题解答⎪⎧≤++−≤++++=151565935121510max 321321x x x x x x x x x Z 该题无可行解。

(完整word版)运筹学(胡运权)第五版课后答案,运筹作业

47页1.1b羅蕿用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解薅47页1。

1d蒂无界解（b）衿1.2蕿约束方程的系数矩阵A=1234莇2112蚄P1P2P3P4,运筹作业肀最优解A=（01/220）T和(0011）T页13题肆49膃设Xij为第i月租j个月的面积羄minz=2800x11+2800x21+2800x31+2800x41+4500x12+4500x22+4500x32+6000x13+6000x23+7300x 14螁s.t.聿x11+x12+x13+x14≥15膃x12+x13+x14+x21+x22+x23≥10膀x13+x14+x22+x23+x31+x32≥20艿x14+x23+x32+x41≥12袇Xij≥0芃用excel求解为：薁用LINDO求解：羁LPOPTIMUMFOUNDATSTEP3薆OBJECTIVEFUNCTIONVALUE 蚇1)118400.0羂VARIABLEVALUEREDUCEDCOST 荿Z0.0000001。

000000虿X113.0000000。

000000螇X210。

0000002800。

000000莃X318。

0000000.000000肁X410.0000001100。

000000莈X120.0000001700.000000袆X220.0000001700。

000000螄X320.0000000。

000000蕿X130.000000400.000000膇X230。

0000001500。

000000袆X1412.0000000.000000袁ROWSLACKORSURPLUSDUALPRICES芁2)0。

000000—2800。

000000羆3）2.0000000.000000羆4)0。

000000—2800.000000节5）0。

000000-1700.000000蝿NO。

ITERATIONS=3罿答若使所费租借费用最小，需第一个月租一个月租期300平方米，租四个月租期1200平方米，第三个月租一个月租期800平方米,页14题肆50蚃设a1，a2，a3,a4,a5分别为在A1，A2，B1，B2，B3加工的Ⅰ产品数量，b1，b2，b3分别为在A1，A2，B1加工的Ⅱ产品数量,c1为在A2，B2上加工的Ⅲ产品数量。

《运筹学教程》胡云权 第五版 第四章 动态规划


* u1 ( A) B1
按计算顺序反推得最优决策序列
* u1 ( A) B1
u* (B1 ) C2 2
* u3 (C2 ) D2
u* ( D2 ) E2 4
最优路线： A B1 C2 D2 E2 F
动态规划的基本思想
可见，求解各阶段都利用了以下关系
f k ( sk ) min dk ( sk , uk ) f k 1 ( sk 1 )
• 动态规划应用
多阶段决策过程的最优化
1、最短路线问题
【例1】从A点铺设一条管道到E点，图中两点间连线上数字表示两 点间距离。现需选一条由A到E的铺管线路，使总距离最短。
2 4 B1 4 8 A 5 3 B3 阶段1 9 B2 7 3 阶段2 2 5 C3 阶段3 阶段4 C2 2 4 1 6 D2 C1 6 5 D1 3
B3
3
阶段2
阶段4
• 状态和状态变量 状态：各阶段开始时的客观条件 状态无后效性: 给定了某阶段状态，则在这阶段以后过程的发展 不受这阶段以前各阶段状态的影响。
动态规划的基本概念和原理
4 A 5 3
B1 4
2
C1 6 1
5 D1 3 4 D2 E
8
B2 7
9
2 5
C2 2 C3
6 4
阶段3
基本概念 • 状态和状态变量 sk： 第k个阶段的状态变量 Sk ：第k个阶段状态变量的集合，称状态集合
* pk . n P k ,n
当k=1时，f1(s1)就是从初始状态s1到全过程结束的整体最优函数。
动态规划的基本思想
【例】选择一条运输线路，使得A到F的运费最小。
2 4
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

单纯形法求解——III.可行性检验
因为，基可行解与基相对应， 所以，寻找新的可行解，即将初始可行基 B0 转化为 B1 ，称基变换。
改善：Z1 Z 0 基变换的原则 1 可行： B 1 b0
换入变量： j 0 中最大的 k 所对 应的 xk 换入基；
1 1 换出变量：由 X B B b B NX N 0 决定出基变量。
单纯形法求解——I.求初始基可行解
因为，基可行解是由一个可行基决定， 所以，构造初始基可行解 X 0 ，相当于确定一个初始可行基 B0 方法：若A中含I， 则 B0 I ；
若A中不含I，则用人工变量法（大M法）构造一个I。
问题：若 B0 I ，则 X 0 ?
1 x1 2 x2 x3 x4 3 2 x1 x2 x , x , x , x 0 1 2 3 4
线性规划模型三要素
• 决策变量
表示某种重要的可变因素，变量的一组数据代表一个解决的方案或措施， 用x1, x2, · · · , xn表示
• 目标函数
决策变量的函数，目标可以是最大化或最小化
• 约束条件
对决策变量取值的限制条件，由决策变量 x1, x2, · · · , xn 的不等式组或方程组 构成
线性规划模型的标准形式
max z = c1x1 + c2x2 + … + cnxn 目标函数：
a x + a x + … + a x = b 11 1 12 2 1 n n 1 约束条件： a21 x1 + a22 x2 + … + a2n xn = b2 …… am1 x1 + am2 x2 + … + amn xn = bm 目标最大化 约束为等式 决策变量均非负
4/7 -
3 2
x2 x1
-z
4/7 45/7
0 1
0
1 0
0
1/7 6/7
-50/7
2/7 5/7
-M-16/7
1/7 -1/7
-1/7
-1/7 1/7
-M+1/7
由此可得，最优解X*=(45/7，4/7，0，0，0，0), Z*=102/7， 具有唯一解。1.6（1）答案23-5
-M
0
-M
x1
1
x2
1
x3
1
x4
1
x5
0
x6
0
Θ 7
x4
-M
x6
-z
10
[2]
3M+2 0 1 0
-5
3-4M
1
2M-5 1/2 1/2 M/2-6
0
0 1 0 0
-1
-M 1/2 -1/2 M/2+1
1
0 -1/2 1/2 -3M/2-1
5
-M 2
x4 x1
-z
2 5
[7/2 ]
-5/2 7M/2+8
1.3——线性规划标准型解的概念
基矩阵（基）：设A是 m n 阶系数矩阵(m n )，秩A=m，则A中一 定存在m个线性无关的列向量，称由m个线性无关的列向量 构成的可逆矩阵 B (P , P ,, P ) 为问题L的一个基，L最多有 Cm 个基。系数矩阵A中的m阶可逆子阵，记为B。其余为 n 非基矩阵，记为N。
9 x1 4 x2 360 4 x + 5x 200 2 s.t. 1 3 x1 10 x2 300 x1 , x2 0
解：（1）转化为标准型
9 x1 4 x2 x3 4 x + 5x x4 1 2 s.t. 3 x1 10 x2 x1 , x2 , x3 , x4 , x5 0 360 200 x5 300
例1中的 X 0 ?
单纯形法求解——II.最优性检验
把目标函数用非基变量表示：
方法：
① 计算每个x j 的检验 数 j c j CB B1Pj ②若所有 j 0 ，则 当前解为最优解
检验数向量，记为 。当 0 时，当前解为最优解。
③否则，有 j 0 ， 则找到最大的 k ， 其对应的 xk 作为 换入变量。
基可行解的个数是有限的，当然凸集的顶点个 数也是有限的。 定理3：若线性规划有最优解，必在可行域某顶点上达到。
在有限个基可行解中间存在最优解。
单纯形法的基本原理
从一个初始基可行解出发，通过对基变量的迭代运算 （每次迭代更换一个基变量，相当于从一个可行极点移动 至与其相邻的另一个可行极点）而得到下一个基可行解， 同时使目标函数值得到改善；经过有限次的迭代运算，就 能得到LP的最优解。 最优性条件：判断是否达到最优解的条件，以及确定下一 次应调入哪一个非基变量为基变量，可使目标函数值得到 改善； 可行性条件：确定应调出哪一个基变量（使其成为非基变 量）可确保新的基本解仍然是可行解。
运筹学复习
《运筹学》课程大纲
课程性质：方法技能类 专业必须课
课时数：1-14周，3，42学时 课程框架
约束条件、目标最大/小化、最优方案
线 性 规 划 运 输 问 题 整 数 规 划 动 态 规 划 图 与 网 络 分 析 对 策 论
决 策 分 析
考核方案：作业（50%）+考试（50%）
线性规划问题的特征
每个问题都用一组未知变量 x1 , x2 ,, xn 表示目标函数 和约束条件。
有一个目标函数，且可表示为一组未知量 x1 , x2 ,, xn 的线性函数，目标函数可以是求最大也可以求最小。 存在一组约束条件，都可以用一组未知量 x1 , x2 ,, xn 的线性等式或不等式表示。
1.6（1）答案
【解】大M法
化为标准型，并加入人工变量得
max z 2 x1 3x2 5x3 Mx4 0 x5 Mx6
x1 x2 x3 x4 7 2 x1 5 x2 x3 x5 x6 10 x16 0
cj CB -M XB b 7
单纯形法的进一步讨论——两阶段法
第一阶段（目的是求解该问题的一个初始基可行解）：在约束中加入
人工变量使系数矩阵出现单位阵，然后目标函数变为maxW＝-∑人 工变量，如果所得最优解中所有的人工变量都为零则得到原问题 的一个基可行解（而非最优解），否则原问题无可行解。如果第 一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量 中含有非零的人工变量，表明原线性规划问题无可行解。
aik 0
例2 用单纯形法求解线性规划问题 max z 7 x1 12 x2 0 x3 0 x4 0 x5
主元素 7 x1 9 4 3 7 12 x2 4 5 [ 10 ] 12
XB
1 c1 CB B P 1
1
CB 0 0 0
B-1b 360 200 300
0 x3 1 0 0 0
1 P 2 P 3 P 4 P 1 2 1 3 1 4 2 2
②∵ P1，P3线性无关，∴（P1, P3）为基. x1 , x3为基变量，令非基变量x2 , x4为0， 得 x1 = 5/2，x3=11/5 则基解为（5/2 , 0 , 11/5 , 0），可行解。 （5/2 , 0 , 11/5 , 0）为基可行解，z2=43/5
《运筹学》教材内容
线性规划 第一章 1-5节
运输问题 第三章 1-4节 整数规划 第五章 1-5节
动态规划 第七章 1-4节
图与网络分析 第八章 1-3节
对策论 第十二章 1-3节
决策论 第十三章 1-3节
第一章 线性规划及单纯形法
主要内容

线性规划问题及其数学模型 线性规划解的概念、图解法 单纯形法原理 线性规划应用
x1, x2, …, xn ≥ 0
其中bi ≥0 ，i = 1, 2, …, m
右端项非负
解的重要概念
可行解（或可行点） ：满足所有约束条件的向量 x ( x1 , x2 , xn ) 可行域：所有的可行解的全体
D { x Ax b, x 0}
最优解：在可行域中目标函数值最大（或最小）的可行解，最优解的全体 称为最优解集合
j1 j2 jm
基向量：基矩阵B中的列，其余为非基向量。 基变量：与基矩阵B中列向量所对应的变量为基变量，记为 X ( x , x ,, x ) ，其余变量为非基变量，记为 X 。
T B j1 j2 jm
N
1.3（2）答案
【解】此线性规划问题的系数矩阵A为 1 2 3 4 2 1 1 2 令A=(P1，P2，P3，P4)
j 0 , 对应的p j 进基 方法：令 k max j
( B 1b)i 1 令 l min i 1 ( B pk） i 0 , 对应的pl 出基 i ( B pk） i
i
bi aik
检验比
单纯形法求解——IV.求解新的基可行解
①∵ P1，P2线性无关，∴（P1, P2）为基. ③…… x1 , x2为基变量，令非基变量x3 , x4为0， ④…… 得 x1 = -1/3，x2=11/3 ⑤…… 则基解为（-1/3 , 11/3 , 0 , 0），非可行解。⑥…… 最优解为（5/2 , 0 , 11/5 , 0），最优值为43/5。
单纯形法基本步骤
I. 求初始基可行解
II. 确定换入变量的最优性条件
，
初始基可行解
III. 确定换出变量的可行性条件
是否是 最优解
Y
N
找一个较好 基可行解
IV. 运用初等行变换求出新的基 可行解