当前位置：文档之家 › 运筹学-4

运筹学-4

  • 格式：ppt
  • 大小：422.00 KB
  • 文档页数：83

下载文档原格式

  / 83

合集下载

运筹学基础及应用第4章-整数规划与分配问题

运筹学基础及应用第4章-整数规划与分配问题

整数规划的特点及应用
解：对每个投资项目都有被选择和不被选择两种可能，因此 分别用0和1表示，令xj表示第j个项目的决策选择，记为：
j投 资 1 对 项 目 xj ( j 1,2,..., n) j不 投 资 0 对 项 目
投资问题可以表示为：
max z
c
j 1
n
j
xj
n a j x j B j 1 x2 x1 s .t x 3 x4 1 x5 x6 x7 2 ） x j 0或者1 （j 1, 2, L n
B1 B2 B3 B4 年生产能力
A1
A2 A3 A4 年需求量
2
8 7 4 350
9
3 6 5 400
3
5 1 2 300
4
7 2 5 150
400
600 200 200
工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万元。 现要决定应该建设工厂A3还是A4，才能使今后每年的总费用最少。
0-1型整数线性规划：决策变量只能取值0或1的整数线性 规划。
整数规划的特点及应用
整数规划的典型例子
例4.1 工厂A1和A2生产某种物资。由于该种物资供不应求，故需要 再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地 有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各 需求地的单位物资运费cij，见下表：
例4.3 设整数规划问题如下
max Z x1 x 2 14x1 9 x 2 51 6 x1 3 x 2 1 x , x 0且 为 整 数 1 2
首先不考虑整数约束，得到线性规划问题（一般称为松弛问 题）。

运筹学-第四章-运输问题和指派问题 PPT课件

运筹学-第四章-运输问题和指派问题 PPT课件

A1 A2 A3 销量
B1
B2
B3
B4
1
32
11 4 3
3 10
3 1 3 9 1 2 -1 8
4
7
6 4 12 10 3 5
3
6
5
6
产量
7 4 9 20
检验数<0表示：例如（A2,B4）如果增加A2到B4的1单位产 品，将会降低1单位的运费，所以，该解不是最优解。
13
解的改进
（1）以 xij 为换入变量，找出它在运输表中的闭回路；
B2 4 11 29
4
6
B3 3
22
3 10
5
B4 产量 10 7
8
4
65
9
5
6
20
求平衡运输问题初始解方法—西北角方法
西
B1
B2
B3
B4 产量
北 角
A1 3
34
11
3
10 7
方
A2
12
92
2
8
4
法
A3
7
43
10 6 5
9
初 始
需求量
3
6
5
6
20
解
x11 3, x12 4, x22 2, x23 2, x33 3, x34 6
min cij xij
s.t.
n
xij si
j 1
m
xij d j
i 1
xij 0
目标函数
n表示物资的n个销地 m表示物资的m个产地
供给约束
需求约束
非负约束
18
问题分析
决策变量 目标函数 约束条件：产量约束、销量约束、非负

《运筹学》第四章决策分析介绍

《运筹学》第四章决策分析介绍
41
P(S2)=0.4时
一般： 般：
E(A1 )=α×500+(1500+(1 α)(-200)=700 )( 200)=700α-200 200 E(A2) )=α×( (-150)+(1150)+(1 α)(1000) )(1000)=-1150 1150α+1000 令E1 =E2 得α=0.65
决策步骤
30
(三)、折衷准则 选择加权系数α(0 α1) max{α(maxVij )+(1-α)(minVij )}
i j j
α=0.6
S1
S2
S3 Vi1 =max Vi2 =min 加权平均
A1 20 A2 9 A3 6
1 8 5
-6 0 4
20 9 6
-6 0 4
9.6 5.4 max=9.6
15
决策分析的主要内容
决策准则 决策树 用决策树分析系列决策问 用决策树分析系列决策问题 检查是否需要获得更多的信息 贝叶斯法 用更新的信息更好地决策 贝叶斯法——用更新的信息更好地决策 效用理论 用效用更好地反映收益的价值 效用理论——用效用更好地反映收益的价值
16
概率论基础
随机事件(实验，试验 实验 试验)
称α=0.65为转折概率 α>0.65 α<0.65 选 A1 选 A2
42

直接使用先验概率 决策步骤 –对于每一种备选方案，将每一个收益乘以 相应自然状态的先验概率，再把乘积相加 就得到收 的加权 均 这就是备选方案 就得到收益的加权平均，这就是备选方案 的期望收益 –选择具有最大期望收益的备选方案作为决 选择具有最大期 收益的备选方案作为决 策方案
34

运筹学笔记4、5-特殊线性规划(整数规划、对偶问题)

运筹学笔记4、5-特殊线性规划(整数规划、对偶问题)

每个线性规划问题都有一个与之对应的对偶问题。

简单考虑如下的生产分配问题我们有下面的对偶问题：该问题的任意一个可行解对应的目标函数值都不小于原问题的目标函数值，但是两个问题的最优目标函数值（有限）相同。

一般而言：1、每个对偶变量对应原问题的一个约束条件2、原问题是等式约束则对偶变量无不等式约束（非负约束）3、原问题是不等式约束则对偶变量有不等式约束4、原问题变量和对偶问题约束条件同样具有如上规律任何原问题和对偶问题之间都存在下述相互关系：弱对偶性：原对偶问题任何可行解的目标值都是另一问题最优目标值的界（推论：原对偶问题目标值相等的一对可行解是各自的最优解）强对偶性：原对偶问题只要有一个有最优解，另一个就有最优解，并且最优目标值相等互为对偶的线性规划问题解之间关系有如下四种：原问题与对偶问题之间存在互补松弛性：一般形式的线性规划互补松弛定理：经济学中有所谓影子价格的概念：如果增加某些约束条件的数值，原问题的最优目标值应该增加，增加单位约束使得原问题最优值的增加量为该约束条件的影子价格。

影子价格可以由对偶线性规划问题清楚地描述：对偶单纯形法：当线性规划问题中地某个约束条件或价值变量中含有参数时，原问题称之为参数线性规划，它有如下的处理方法：1）固定λ的数值解线性规划问题2）确定保持当前最优基不变的λ的区间3）确定λ在上述区间附近的最优基，回2）如以下问题：在实际问题中，许多变量以及它们的约束条件往往是离散的，或者说限定在整数域上，这便引入了整数线性规划的概念。

具体而言，整数线性规划包含纯整数线性规划（所有变量是整数变量）、混合整数线性规划（同时包含整数和非整数变量）、0-1型整数线性规划（变量等于0或1）去除整数规划的整数约束后的问题称为其松弛问题。

一般情况，原问题的解并不一定是其松弛问题的最优解附近的整数解，例如：通常的解决办法是在松弛问题的基础上出发，不断地引入整数的约束条件，从而求出整数规划的解。

运筹学 第4章 整数规划与分配问题

运筹学 第4章 整数规划与分配问题

匈牙利法思路：若能在 [Cij] 中找出 n 个位于
不同行不同列的0元素(称为独立0元素)，则
令解矩阵[xij]中对应这n个独立0元素的元素
取值为 1 ，其他元素取值为 0 ，则它对应目
标函数zb=0是最小的。这就是以[Cij]为系数
矩阵分配问题的最优解，也得原问题的最
优解。
定理1 若从分配问题效率矩阵[cij]的每一行元素中分别减去 (或加上)一个常数ui(称为该行的位势)，从每一列分别减去 (或加上)一个常数vj(称为该列的位势)，得到一个新效率矩阵 [bij]，若其中bij=cij-ui-vj，则[bij]的最优解等价于[cij]的最优解
第1步：找出效率矩阵每行的最小元素，并分别从每行
中减去。
第2步：再找出矩阵每列的最小元素，并分别从各列中 减去。
2 10 9 7 2 15 4 14 8 4 13 14 16 11 11 4 15 13 9 4
0 8 7 5 11 0 10 4 0 3 5 0 0 11 9 5
表明m个约束条件中有(m-k)个的右端项为( bi+M )，不起约 束作用，因而，只有k个约束条件起作用。 ② 约束条件的右端项可能是r个值b1 , b2 ,, br 中的某一个 即： 定义：
n
aij x j b1 或b2或或br
j 1
1 假定约束右端项为 bi yi 否则 0
现用下例来说明： max z=40x1+90x2 9x1+7x2≤56 7x1+20x2≤70 x1，x2≥0 x1，x2整数 ① ② ③ ④ ⑤
解：先不考虑条件⑤，即解相应的线性规划B,①～④(见图5-2)， 得最优解x1=4.81，x2=1.82，z0=356

运筹学-非线性规划(四)(名校讲义)

运筹学-非线性规划(四)(名校讲义)

1．外点法（又称惩罚法）
其思路是在目标函数中增加一项使之变为无约束问题，同时 对破坏约束项需付出高昂代价，该法的起始点在可行域外， 一旦进入可行域内便得到最优解。
§1 多维有约束寻优方法 （9）
①思路 设原问题为min：f[X] 约束：XS S是En中一个约束子集，即X的可行域为S，
则将其变成无约束问题： min：f[X]+ p(X)
p(x) =1 =10 =100
=100
b
=10
=1
图4-19
x
a
§1 多维有约束寻优方法 （11）
②求解过程
令{k }（k=1，2，…，）是一无穷序列，且k≥0，k＋1 >k，定义函数q(，X)=f(X)+Xk，若原问题有解，则当k→∞，
§1 多维有约束寻优方法 （2）
一、库恩-塔克（简称库塔）条件
1．可行方向和起作用约束 ①可行方向：
设X(0)是可行点，即X(0) R，若对于某一方向D，存在一 个数 0>0,使对于任意 （0≤≤0 ）均有下式成立：X(0) +DR，则称方向D是点X(0)处的可行方向。 ②下降方向：对于f(X)的台劳级数展开，若▽f[X(0)]T· D<0, 则称D方向为f[X]的下降方向。
第二十四讲 非线性规划（四）
§1 多维有约束寻优方法
§1 多维有约束寻优方法 （1）
非线性规划的一般形式
min f(X) hi(X)=0 i=1，2，…，m (1)
gi(X)≥0 j=1，2，…，l
下面，先阐述非线性规划的重要理论成果——库恩-塔克 条件(Kuhn-Tucker),然后介绍比较重要的几种有约束的寻 优方法。
0 1 2 x1

运筹学——4.运输问题--例题


季度 Ⅰ Ⅱ Ⅲ Ⅳ
生产能力(台) 25 35 30 10
单位成本(万元) 10.8 11.1 11.0 11.3
8
解 由于每个季度生产出来的柴油机不一定当季交货，所以 设xij为第i季度生产的用于第j季度交货的柴油机数。根据合 同要求，必须满足
x11 = 10 x + x = 15 12 22 x13 + x23 + x33 = 25 x14 + x24 + x34 + x44 = 20
B1 3 1 7 2 4 1 1 1 4 2
销 B2 11 9 4 8 5 8 / 1 2 1
地 B3 B4 3 2 10 4 2 2 2 4 2 3
22
10 8 5 6 7 4 6 2 1 3
销 地
解：从表3-40中看出，从A1到B2每吨产品的直接运费为 11元，如从A1经A3运往B2，每吨运价为3+4=7元，从A1 经T2运往B2只需1+5=6元，而从A1到B2运费最少的路径 是从A1经A2，B1到B2，每吨产品的运费只需1+1+1=3元。 可见这个问题中从每个产地到各销地之间的运输方案是 很多的。为了把这个问题仍当作一般的运输问题处理， 可以这样做：
E→D航程17天，在D卸货1天，总计19天。每天3航班，故该航线周转 船只需57条。各条航线周转所需船只数见表3-35。 航线 装货 航程 卸货 小计 航班数 需周转 天数 天数 天数 船只数 17 1 19 3 57 1 1 10 1 3 1 5 2 2 1 9 7 1 9 3 1 15 1 13 1 15 1 4 •以上累计共需周转船只数91条 .
21
产 项 产 地
中 间 转 运 站

物流运筹学1-2,3-4


该小区800米半径 内的各小区 ＡＣＥＧＨＩ ＢＨＩ ＡＣＧＨＩ ＤＪ ＡＥＧ ＦＪＫ ＡＣＥＧ ＡＢＣＨＩ ＡＢＣＨＩ ＤＦＪＫＬ ＦＪＫＬ ＪＫＬ
13
绪论
• 物流运筹学典型案例３： 博弈论应用（市场营销）（二人有限零和对策模型——无鞍点即纯策略意 义下无解的对策模型）
在W城的冰箱市场上，以往的市场份额由本市生产的A 牌冰箱占有绝大部分。本年初，一个全国知名的B牌冰箱进入 W城的市场。在这场竞争中假设双方考虑可采用的市场策略 均为三种：广告、降价、完善售后服务，且双方用于营销的
罪，但可以私入民宅的罪名将两人各判入狱1年。
16
绪论
（非合作二人有限非零和对策） 下表给出了囚徒困境这个博弈的收益矩阵。 注意：A与B不能在作出决定之前事先串供，那么每个罪犯 都在不知道对方决策的前提下，从有利于自己的理性角度 (个人利益最大化)，同时他认为对方也是理性的，然后去 考虑问题作出决策。
平时成绩20%（作业+考勤+课堂表现） 期中测验10% 期末成绩70%
2
What’s 运筹学？
运筹学跟 我有什么 关系？！
Be happy
improve ability
用数学理论 建模来解决 管理决策问 题
基础学科： 数学、管理 学、系统论、 经济学 1考研专业课 2思维能力和学 习能力的培养
Our goal
资金相同。根据市场预测，A的市场占有率为： B品牌
根据已知条件，试确 定双方的最优策略？
广告1 降价2 售后服务3
广告1 0.60 0.62
0.65
A 品牌= 降价2 0.75 0.70 0.72
售后服务3 0.73 试确定双方的最优策略。
0.76

全国自考运筹学基础-试卷4_真题(含答案与解析)-交互

全国自考（运筹学基础）-试卷4(总分80, 做题时间90分钟)1. 单项选择题1.“运筹帷幄”这一成语表明，在中国古代英明的军队指挥员已能运用( )SSS_SINGLE_SELA 单纯的主观判断方法B 定性决策方法C 定性决策与简单的定量决策相结合的方法D 只凭自己的经验决策的方法分值: 2答案:C解析：混合性决策：运用定性和定量两种方法才能制定的决策。

2.指数平滑预测方法是一种 ( )SSS_SINGLE_SELA 纯定量预测法B 纯定性预测法C 定性与定量相结合的方法D 既非定性也非定量分值: 2答案:C解析：指数平滑预测方法是一种定性与定量相结合的方法。

3.加权平均数预测法是一种 ( )SSS_SINGLE_SELA 纯定性预测B 定性和定量相结合的方法C 既非定性又非定量的预测法D 纯定量方法分值: 2答案:B解析：加权平均数预测法是一种定性和定量相结合的方法。

4.最大最小原则是用来解决下列哪项条件下的决策问题? ( )SSS_SINGLE_SELA 不确定B 确定C 风险D 风险或不确定分值: 2答案:A解析：不确定条件下的决策包括最大最大决策标准，最大最小决策标准，最小最大遗憾值决策标准，现实主义决策标准。

5.下列有关存货台套的说法中，错误的是 ( )SSS_SINGLE_SELA 存货台套是存货管理的单位B 某个存货台套中可以包括不同的单项存货C 存货台套法简化了库存管理的工作内容D 每个存货台套包括的单项存货在数目上一般是相同的分值: 2答案:D解析：存货台套包括的单项存货在数目上可以有多有少。

6.一元线性回归预测中，相关系数R的取值范围一般是 ( )SSS_SINGLE_SELA R≥0B Q≤R≤1C -1≤R≤1D 0．5≤R≤0．9分值: 2答案:C解析：一元线性回归中R的取值范围是：-1≤R≤1。

7.在Ft+1 =Ft+a(xt-Ft)中，a的取值范围是 ( ) SSS_SINGLE_SELA -1≤a＜0B 0≤a≤1C a＞1D a＜-1分值: 2答案:B解析：指数平滑预测法中a的取值范围是：0≤a≤1。

管理运筹学 第四章 目标规划


再来考虑风险约束： 总风险不能超过700， 投资的总风险为 0.5x1＋0.2x2 引入两个变量d1+和d1-，建立等式如下： 0.5x1 +0.2x2=700+d1+-d1根据要求有
min ｛d1+｝
0.5x1 +0.2x2-d1++d1-=700。
再来考虑年收入:
3x1+4x2
引入变量 d2+和d2-，分别表示年收入超过与低于 10000 的数量。于是，第2个目标可以表示为 min ｛d2-｝ 3x1+4x2-d2++d2-=10000。
2. 统一处理目标和约束。
对有严格限制的资源使用建立系统约束，数学形式同线性规划 中的约束条件。如C和D设备的使用限制。
x1 2 x2 40 3x2 24
(3)Ｃ和Ｄ为贵重设备，严格禁止超时使用
对不严格限制的约束，连同原线性规划建模时的目标，均通 过目标约束来表达。 （1）力求使利润指标不低于250元：
本问题中第一个目标的优先权比第二个目标大。即最重要 的目标是满足风险不超过700。分配给第一个目标较高的优先 权P1，分配给第二个目标较低的优先权P2。
Minz= P1（d1+）+P2（d2-） s.t. 20x1＋50x2≤90000 0.5x1 +0.2x2-d1++d1-=700 3x1+4x2-d2++d2-=10000 x1,x2,d1+,d1-,d2+,d2-≥0
现假定： 第1优先级P1——企业利润；
第2优先级P2——Ｉ、II产品的产量保持1:2的比例
第3优先级P3——设备A,B尽量不超负荷工作。其中设备A的重要性 比设备B大三倍。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

总结求解过程：
LP问题 标准形 找一可行解 （！） 判别迭代（多次） 结论 【 推设】 求解LP问题的关键在于： （1）迭代的基础——初始的可行解 （2）判别的标准 （3）迭代方法（有效迭代）
第二节 单纯形法的基本原理
一、几个概念 前提：针对标准形 Min S=CX St：AX= b X≥0
一、几个概念
三、求初始可行基的方法 — 观察法
例1、求Max S=2x1+5x2
st：x1 ≤4 x2 ≤3 x1+2x2 ≤8 x1，x2 ≥0
三、求初始可行基的方法 — 观察法例1
解：令f= -s，引进松弛变量xi （i=3、4、 5） 将原问题化为标准形： 求Min f = -2x1 － 5x2 st：x1 + x3 =4 x2 + x4 =3 x1 +2x2 + x5 =8 xi≥0（i=1、2、3、4、5） B=（P3 P4 P5）= I 为可行基 对应的单纯形表如下：
第三节 单纯形法的操作步骤
前提：针对标准形 Min S=CX St：AX= b X≥0 设：B为该LP问题的一个基
一、对应于基B的（初始）单纯形表
（一）AX= b BXB+NXN = b XB =B-1 b － B-1 NXN （二）S=CB B-1 b －（ CB B-1 N － CN ）XN
x1 x2 0 0 1 x3 2 1 2
S
x1 x2
3 1 1
0 1 0
一、对应于基B的（初始）单纯形表
例1、 B2＝（P1，P3）对应的单纯形表如下：
x1 x2 -1 -1/2 1 /2 x3 0 0 1
S
x1 x3
2 1/2 1/2
0 1 0
一、对应于基B的（初始）单纯形表
例1、 B3＝（P2，P3）对应的单纯形表如下：
一、对应于基B的（初始）单纯形表
例1、找出下列LP问题的所有基，并写出其对 应的单纯形表。 Min S ＝x1＋2x2＋3x3 st：2x1－x2 ＝1 x1 ＋ x3＝1 x1，x2，x3≥0
一、对应于基B的（初始）单纯形表
例1、本题有三个基：
B1＝（P1，P2），B2＝（P1，P3）， B3＝（P2，P3） B1＝（P1，P2）对应的单纯形表如下：
设B=（Pj1 Pj2 … Pjr-1 Pjr Pjr+1 … Pjm ）为可行基对应单纯形表如下：
S xj1 xj2 … xjr … xjm
b00 b10 b20 … br0 … bm0
x1 x2 …… xs …… xn b01 b02 ……b0s…… b0n b11 b12 ……b1k…… b1n b21 b22 ……b2s…… b2n …… …… …… br1 br2 ……brs …… brn …… …… …… bm1 bm2……bms ……bmn
二、换基迭代——3、新基的特征
（2）换基迭代后，目标函数值下降；当且仅当br0 ＝0 时，目标函数值不变。 证： ∵ b100 － b00 ＝ b00－ b0s （ br0 / brs ） － b00 ＝ － b0s （ br0 / brs ） ≤0 上式中当且仅当br0 ＝0时取等号 ∴ 命题得证。
【分析】B=（P3 P4 P5）= I 对应的单纯形表如下： S x3 x4 x5 0 4 3 8 x1 2 -1 0 -1 x2 5 0 1 2 x3 0 1 0 0 x4 0 0 1 0 x5 0 0 0 1
令： x1 = λ ， x2 = 0 则 X=（λ 0 4+λ 3 8+λ）T为可行解 相应的目标函数值为 S = -2λ 当λ +∞时 S -∞
记CB B-1 b = b00 ，CB B-1 A － C =（ b01 b02 … b0n ） B-1 b=
b10 b20 … bm0 b11 b12 … b1n
B-1 A=
b21 b22 … b2n …… bm1 bm2 …bmn
一、对应于基B的（初始）单纯形表
则T（B） 具体化为： x1 x2 …… xs …… xn S xj1 xj2 … xjr … xjm b00 b10 b20 … br0 … bm0 b01 b02 ……b0s…… b0n b11 b12 ……b1k…… b1n b21 b22 ……b2s…… b2n …… …… …… br1 br2 ……brs …… brn …… …… …… bm1 bm2……bms …… bmn
1、基：设A为约束方程组m×n维系数矩阵， 秩（A）= m，称A的任一m× m的非奇异 子矩阵B为该LP问题的一个基。 非基： N 1-1、基向量 // 非基向量 1-2、基变量 （XB ） // 非基变量（ XN ） 2、基础解：设X=（ XB XN ）T 若XN =0，则求得一组解 X（0）=（ XB 0 ）T 称X（0）为基础（本）解。
x1 S x1 x2 S
x1 x3
x2 0 0 1 -1 - 1/2 1/2
x3 2 1 2 0 0 1
3 1 1 2 1/2 1/2
0 1 0 0 1 0
二、换基迭代
1、换基迭代的步骤：
初始单纯形表T（B）
判别
Y
END
N
找轴心项 换基B— B1
新基B1对应的单纯形表T（B1）
二、换基迭代—2、换基迭代计算公式
二、换基迭代—2、换基迭代计算公式
（1）检验判别： 若b0j≤0（j=1、2、…、n），则B为最优基 —— END 否则无妨假设存在b0s ＞ 0 ，则需换基迭代 （2）找轴心项 Min Min〔 bi0/ bis 〕 ＝ br0 / brs
（ bis ＞0）
（无妨假设）
则：轴心项为brs （3）得新基B1 = （Pj1 Pj2 … Pjr-1 PS Pjr+1 … Pjm ） （4）写出新基B1对应的单纯形表T（ B1 ）： b1rj ＝ brj / brs （ 0≤ j≤ n ） b1ij ＝ bij － bis （brj / brs ） （ 0≤ j≤ n；0≤i≠r≤m） （5）转步骤（1）
三、求初始可行基的方法
针对标准形 Min S=CX St：AX= b X≥0 其中： b ≥0 1、观察法： 若从系数矩阵A中能直接找出m个单位向量 Pjk（k=1、2、… 、m ），则B=（ Pj1 Pj2 …Pjm ） 即为可行基（系数矩阵A中存在m维单位矩阵I， 则该m维单位矩阵I即为可行基）
一、对应于基B的（初始）单纯形表
（五） CB B-1 N － CN ≤0等价于 CB B-1 A － C ≤0 （六）判别准则：对于基B ，若B-1 b≥0 且 CB B-1 A － C ≤0 则对应于基B的基础解便是 原LP问题的最优解。
一、对应于基B的（初始）单纯形表
T（B）： CB B-1 b B-1 b CB B-1 A － C B-1 A
二、换基迭代——3、新基的特征
（1）新基仍是可行基 证：㈠ i ＝ r ∵bro≥0 ， brs ＞ 0 ∴ b1r0 ＝ bro / brs ≥0 b ㈡ i≠ r 有 b1i0 ＝ bi0－ bis （br0 / brs ） 其中bi0 ≥0 ，br0 / brs ≥0 若 bis≤0 则 b1i0 ≥0 若 bis ＞ 0 则 b1i0 ＝ bi0－ bis （ br0 / brs ） ＝ bis（ bi0 / bis － br0 / brs ）≥0 ∴新基仍是可行基
x1 x2 0 1 0 x3 0 0 1
S
x2 x3
1 -1Байду номын сангаас1
-2 -2 1
一、对应于基B的（初始）单纯形表
例1、分析判断： B1是可行基 B2是最优基 B3仅是一个基 该LP问题最优解为： X =（1/2 0 1/2）T 相应的目标函数最优值为：S = 2
二、换基迭代
例1、 B1＝（P1，P1）对应的单纯形表如下：
则（ Ⅱ）有如下等价形式（Ⅲ）： st： x1 = 4 － x3 x4 = 1 －0.5x3+0.5 x5 x2 = 2 + 0.5x3 － 0.5 x5 xi≥0（i=1、2、3、4、5） 相应的目标函数为：f = -18 －0.5 x3+ 2.5x5 显然：x=（4 2 0 1 0）t为一可行解 相应的目标函数值 f 3= -18 由 f = -18 －0.5 x3+ 2.5x5 看出 若 x3 +则 f 于是 将自由未知量 x3 换为 x4
第四章 单纯形法
【教学目标】 1、了解单纯形法的基本思路 2、掌握单纯形法方法 3、利用单纯形法方法求解LP问题并能分析和 解释各种解的意义
第一节 用消去法求解LP问题
例：求Max S=2x1+5x2 st：x1 ≤4 x2 ≤3 x1+2x2 ≤8 x1，x2 ≥0
解：令f= -s，引进松弛变量xi （i=3、4、5）将 原问题化为标准形： 求Min f = -2x1 － 5x2 st：x1 + x3 =4 x2 + x4 =3 x1 +2x2 + x5 =8 xi≥0（i=1、2、3、4、5）
则（ Ⅲ ）有如下等价形式（Ⅳ）： st： x1 = 2 + 2 x4 － x5 x3 = 2 － 2x4 + x5 x2 = 3 － x4 xi≥0（i=1、2、3、4、5） 相应的目标函数为：f = -19 + x4+ 2 x5 显然：x=（2 3 2 0 0）t为一可行解 相应的目标函数值 f 4= -19 由f = -19 + x4+ 2 x5 可见 f 4 = -19是目标函数 最小值 即 x=（2 3 2 0 0）t是最优解 ∴原问题的最优解为x1 = 2 ， x2 = 3 相应的目标函数最优值为 S=19
一、几个概念