当前位置：文档之家 › 运筹学_分支定界法

运筹学_分支定界法

  • 格式：ppt
  • 大小：942.50 KB
  • 文档页数：9

下载文档原格式

  / 9

合集下载

分支定界法

分支定界法

分支定界法分支定界法，也称为分界定义法，是为了确定并将客观事物归类的一种逻辑基础规范。

它是一组文本规范，用于描述和分类客观事物，以及它们之间的关系。

它分析客观事物的共性，从这些共性，弄清楚客观事物以及它们之间的关系，形成分支定义法。

分支定界法最初创造于18世纪的德国，由卡尔文贝因茨（Karl von Bennizs）提出，他的著作 Theorie der classifikation（分类理论）发表于1790年。

他的主要思想是：通过对客观事物的共性的分析，将客观事物归类，并形成一系列的分类方法。

分支定界法一般包括三个层次：主类，亚类，次类。

主要是将客观事物按照一定的共性划分到不同的类别中，然后在每个主类中进行更详细的分析，形成子类，从而将客观事物更细致地分类。

分支定界法有很多优点。

首先，它可以更好地适应新出现的客观事物，以及客观事物可能出现的新情况。

这是因为，分支定界法有着一系列的分类方法，不仅具有某种共性，而且有着不同的子类，这些子类可以更好地形成客观事物之间的关系，并且有利于新类别的形成。

此外，分支定界法还可以帮助人们进行判断。

分界定义法是一种可以把客观事物细致分类的方法，从而可以更好地去判断两个客观事物之间是否有关系，或者相似度如何，从而帮助我们做出判断。

然而，分支定界法也有一定的局限性。

有时，分支定界法所指定的客观事物重叠，或者具有相同的共性，这会降低分类的准确性。

此外，它也会忽略一些客观事物的细微差别，这可能会影响分类的结果。

总之，分支定界法是一种有效的客观事物归类方法。

它可以更好地划分客观事物的共性，也可以更直观地反映客观事物之间的关系，从而有效地把客观事物归类。

此外，它还可以帮助我们做出判断，但它也有一定的局限性，必须在不同的客观事物之间上尽量保持准确性和细微差别。

分支定界法

分支定界法
0
x1=1 z* 10 x1=0
子域2：x1=0，若去x2= x3=x4=x5=0，则这 个解不是可行解，所以这个子域必须进一步 划分。
z*
2
1
2
x2=1
x2=0
3
x3=1 z* 4 x3=0
4
5
x4=1
6
x4=0
z=1Байду номын сангаас
7
x5=1
8
x5=0
9
10
8
分支定界法——实例
0
x1=1 z* 10 x1=0
分支定界法
MAY
2015年6月
分支定界法——概述
定义
将问题分支为子问题集，以及对这些子问题定界的算法，称为分支定界 算法 对有约束的规划问题，设其可行解为有限个，将可行解集合恰当地进行 分组，然后分批系统地搜索，这就是分支定界法研究的内容
几个术语
① 分枝：将原问题分成几个无整数约束的子问题； ② 定界：每一个子问题可以给原问题划出一个边界；
z* 2
0
x1=1
z* 10 x1=0
1
2
x2=1
x2=0
3
x3=1 z* 4 x3=0
4
5
x4=1
6
x4=0
z=1
7
x5=1
8
x5=0
9
10
12
分支定界法——实例
子域9和10 各变量都已被固定，子域中只含 一个点，而且不是可行点，同时也不可能再 进一步细分了。
x3=1 z* 4 z* 2
0
x1=1
子域3：x1=0，x2=1，若取x3=x4=x5=0，则 这个解 不是可行解，所以这个子域必须进一 步划分。

分支定界

分支定界

所谓“分支”就是在处理整数规划问题时，逐步加入 对各变量的整数要求限制。先求解整数规划相应的松弛问 题(记为 P0)，若(P0)的最优解不符合整数条件，假设 xi b i 不符合整数条件，于是增加新的约束条件： xi bi 和
xi bi 1， 分别将其加入到松弛问题(P0)中， 从而形成两
5 x1 7 x2 35 s.t . 4 x1 9 x2 36 x , x 0, 全部为整数 1 2
解 :step1
确定与整数规划问题（记为问题 A）对应的松
弛线性规划问题 (记为问题 B)：
max z 2 x1 3 x2
5 x1 7 x2 35 s.t . 4 x1 9 x2 36 x , x 0 1 2
个分支，称为两个后继子问题。后继子问题的可行域包含 整数规划所有的可行解。根据需要，后继子问题可以产生 类似的分支，从而把原整数规划问题通过分支迭代求出最 优解。
所谓“定界”就是在分支过程中，若某个后继子问题最优 解恰好是整数规划的可行解，则该后继子问题最优目标函 数值成为整数规划的目标函数值的一个“界限” ，从而对 那些最优目标函数值比上述“界限”还差的后继子问题可 以剔除不加考虑。 同时在分支过程中出现更好的 “界限” ， 则用它来取代原来的界限，以提高定界的效率。
则总生产成本的目标函数为：
min z C ( x j ) c j x j k j y j
j 1 j 1
n
n
这里 M 是一个充分大的正数。 所以该产品计划问题可以表 述成如下规划问题：
min z c j x j k j y j
j 1
n
0 x j My j , j 1,2,, n s.t. y j 0 or 1, j 1,2,, n

运筹学_分支定界法

运筹学_分支定界法

⑵
5 x1 6 x 2 3 0
x2
A 3 B
⑴x
1
x2 2
⑶
x1 4
1
1
3
x1 5 x 2 Z
x1
求（LP2） ,如图所示。
m a x Z x1 5 x 2 x1 x 2 2 5 x 6 x2 30 1 ( IP 2 ) x 1 4 x 2 1 x1 , x 2 0 且 为 整 数
x1 x 2 2 x1 x 2 2 5 x 6 x2 30 5 x 6 x2 30 1 1 x1 x1 4 4 ( IP 2 2 ) ( IP 2 1) 2 2 x1 x1 x x 4 3 2 2 x1 , x 2 0 且 为 整 数 x1 , x 2 0 且 为 整 数
第三节 分枝定界法
（一）、基本思路 考虑纯整数问题：
m ax Z
n
c
j 1
n
j
xj
a ij x j b i ( i 1 .2 m ) ( IP ) j 1 x 0 ,( j 1 .2 n ) 且 为 整 数 j
m ax Z
c
j 1
n
记为（IP）
解：首先去掉整数约束，变成一般线性规划问题
m a x Z x1 5 x 2 x1 x 2 2 5 x1 6 x 2 3 0 4 x1 x ,x 0 1 2
记为（LP）
用图解法求（LP）的最 优解，如图所示。
m a x Z x1 5 x 2 x1 x 2 2 5 x1 6 x 2 3 0 4 x1 x ,x 0 1 2

第三节分支定界

第三节分支定界

（P3） ）
1
3
x1
在（P3）的基础上继续分枝。加入条件x1 ≤ 2 ，x1 ≥3 的基础上继续分枝。加入条件 有下式： 有下式：
m in Z = − x1 − 5 x 2 x1 − x 2 ≥ − 2 5 x1 + 6 x 2 ≤ 30 x1 ≤4 ( P5 ) x1 ≥2 x ≤3 2 x1 ≤2 x1 , x 2 ≥ 0 且为整数
例1：用分枝定界法求解整数规划问题（用图解法计算） ：用分枝定界法求解整数规划问题（用图解法计算） min Z = − x 1 − 5 x 2
x1 − x 2 ≥ −2 5 x 1 + 6 x 2 ≤ 30 ≤4 x1 x 1 , x 2 ≥ 0 且全为整数
记为（ 记为（P）
是整数 解，且 z*<z6,
增大下界z0 ≤ z2 ≤ z3 ≤ z*, 减少上界+ ∞ ≥ z的目标函数值 分支后计算松弛的线性规划的最优解: 2. 分支后计算松弛的线性规划的最优解:
整数解且目标值小于原有最好整数解的值则替代 原有最好整数解 整数解且目标值大于原有最好整数解的值， 整数解且目标值大于原有最好整数解的值，则删 除该分支 非整数解且目标值小于原有最好整数 整数解的值则继 非整数解且目标值小于原有最好整数解的值则继 续分支 非整数解且目标值大于等于原有最好整数 整数解的值 非整数解且目标值大于等于原有最好整数解的值 则删除该分支其中无最优整数 整数解 则删除该分支其中无最优整数解
⑵
B
⑴ (18/11,40/11) A C ⑶
（P1）
1 1
（P2）
3
x1
不是整数，故继续分支。 （－16）更小的最优解，但 x2 不是整数，故继续分支。 ）更小的最优解，

运筹学课件第三节分支定界法

运筹学课件第三节分支定界法
算法改进
针对不同问题的特点，分支定界法在算法实现上 不断进行优化和改进，以提高求解效率。
3
理论分析
分支定界法的理论分析涉及算法的收敛性、复杂 度等方面，为算法的改进提供了理论支持。
分支定界法的发展趋势
混合整数规划问题求解
随着混合整数规划问题的广泛应用，分支定界法在求解这类问题 上的研究逐渐成为热点。
理论深化与完善
进一步深化分支定界法的理论分析，完善算法的理论体系。
应用拓展
拓展分支定界法的应用领域，解决更多实际问题。
THANKS
感谢观看
运筹学课件第三节分支定界法
contents
目录
• 分支定界法的概述 • 分支定界法的算法原理 • 分支定界法的实现过程 • 分支定界法的案例分析 • 分支定界法的优缺点分析 • 分支定界法的前沿研究与展望
01
分支定界法的概述
分支定界法的定义
分支定界法是一种求解整数规划问题 的算法个子问题的解的 界，来逐步逼近最优解。
03
分支定界法的实现过程
问题建模与参数设定
确定决策变量
根据问题的具体情况，确定决策 变量，并为其设定合适的取值范
围。
定义目标函数
明确问题的目标，将其表示为一个 数学表达式，以便进行优化。
约束条件
根据问题的限制条件，建立相应的 约束条件。
建立搜索树与初始化
建立搜索树
根据问题建模的结果，建立一个 搜索树，用于表示问题的解空间 。
的获取概率。
优化分支策略
02
通过改进分支策略，减少算法产生的分支数量，降低算法的复
杂度和计算量。
引入智能搜索策略
03
将智能搜索策略（如遗传算法、模拟退火等）与分支定界法结

分支定界法原理简介

分支定界法原理简介分支定界法是一种广义搜索算法，人工使用非常繁琐，但由于计算机的运算速度快的特点，这种算法十分适合计算机进行。

分支定界法是计算机最擅长的广义搜索穷举算法。

基本思想：1. 松弛模型的最优解要优于其相应的整数规划的解由于松弛模型可行解的区域（多边形）包含了对应的整数规划的可行解的集合（多边形内的整数点），因而松弛模型的解要优于整数规划的解。

这就是说，如果问题是求最大值的，则松弛模型最优解对应的目标函数值必大于或等于整数规划最优解对应的目标函数值；如果问题是求最小值的，则松弛模型的最优解对应的目标函数值必小于或等于整数规划最优解对应的目标函数值。

由此可以推出：2. 松弛模型的最优解如果是整数解，则必然也是整数规划的最优解。

3. 松弛模型的最优解如果不是整数解，则如果问题是求最大值的，松弛模型最优解的目标函数值是整数规划最优解目标函数值的一个上界；如果问题是求最小值的，则松弛模型最优解的目标函数值是整数规划最优解目标函数值的一个下界。

我们用例子来说明用分支定界法求解整数规划的步骤。

例 求下面整数规划的最优解1212121212max 4090s.t. 975672070 ,0x ,Z x x x x x x x x x =++≤+≤≥为整数解 从上述各约束条件可见，是一个可行解，对应的松弛模型目标函数值。

本问题是一个求最大值的问题，因而整数规划最优解的目标函数的下界可以取为0，即取整数规划模型最优值的下界(0,0)0Z =0Z =。

先考虑此整数规划问题的线性松弛模型0：其解为 松弛模型0 0123564.811.82Z x x ===由于松弛模型解的目标函数值是整数规划模型最优值的一个上界，可以取此处的0Z 为整数规划模型最优值的一个上界356Z =。

由于该松弛模型解不是整数解，分原问题为和两个子模型：子模型1和子模型2。

14x ≤15x ≥子模型1子模型2 14≤x 15≥x1123494.002.10Z x x ===2123495.001.57Z x x ===子模型1的形式： 121212112max 4090s.t. 975672070 4x ,0Z x x x x x x x x =++≤+≤≤≥子模型2的形式：121212112max 4090s.t. 975672070 5x ,0Z x x x x x x x x =++≤+≤≥≥所求整数规划模型的最优值不会超过这两个子模型的最优值中大的那个，即349。

运筹学基础(中文版第10版)哈姆迪塔哈课后习题答案解析

运筹学基础（中文版第10版）哈姆迪塔哈课后习题答案解析第一章线性规划模型1.1 线性规划的基本概念1.请解释线性规划模型的基本要素以及线性规划模型的一般形式。

答：- 线性规划模型的基本要素包括决策变量、目标函数、约束条件。

- 线性规划模型的一般形式如下：Max/Min Z = c₁x₁ + c₂x₂ + ... + cₙxₙSubject to:a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂...aₙ₁x₁ + aₙ₂x₂ + ... + aₙₙxₙ ≤ bₙx₁, x₂, ..., xₙ ≥ 01.2 线性规划模型的几何解释1.请说明线性规划模型的几何解释。

答：线性规划模型在几何上可以表示为一个多维空间中的凸多面体（可行域），目标函数为该多面体上的一条直线，通过不同的目标函数系数向量c，可以得到相应的最优解点。

通过多面体的边界和顶点，可以确定最优解点的位置。

如果可行域是无限大的，则最优解点可以在其中的任何位置。

1.3 线性规划模型求解方法1.简要说明线性规划模型的两种求解方法。

答：线性规划模型可以通过以下两种方法进行求解： - 图形法：根据可行域的几何特征，通过图形方法确定最优解点的位置。

- 单纯形法：通过迭代计算，逐步靠近最优解点。

单纯形法是一种高效的求解线性规划问题的方法。

第二章单变量线性规划2.1 单变量线性规划模型1.请给出单变量线性规划模型的一般形式。

答：Max/Min Z = cxSubject to:ax ≤ bx ≥ 02.2 图形解法及其应用1.请解释图形解法在单变量线性规划中的应用。

答：图形解法可以直观地帮助我们确定单变量线性规划模型的最优解。

通过绘制目标函数和约束条件的图像，可以确定最优解点的位置。

对于单变量线性规划模型，图形解法特别简单，只需要绘制一条直线和一条水平线，求解它们的交点即可得到最优解点的位置。

最优化 分支定界

最优化分支定界最优化问题是指在一组约束条件下，寻找某个或某组变量的值，使得目标函数达到最优（最大或最小）的问题。

这类问题在科学研究、工程技术和经济管理等领域中都有广泛的应用。

分支定界法（Branch and Bound）是一种求解最优化问题的经典算法，尤其适用于整数规划、混合整数规划以及组合优化问题。

以下是该方法的详细说明：1.基本思路（1）分支：将问题的可行解空间不断划分为更小的子集，这个过程称为“分支”。

每个子集代表原问题的一个子问题。

（2）定界：对每个子集（或子问题）计算一个目标函数的界（上界或下界），这称为“定界”。

对于最小化问题，通常会计算每个子集的下界；对于最大化问题，则会计算上界。

（3）剪枝：在每次分支后，通过比较子集的目标函数界和当前已知的最优解，可以判断某些子集不可能包含更优的解，因此这些子集可以被“剪枝”，即不再进一步考虑。

（4）迭代：通过不断重复分支、定界和剪枝的过程，直到找到最优解或确定最优解的范围。

2.优点（1）适用性广：分支定界法可以应用于各种类型的最优化问题，包括整数规划、混合整数规划和组合优化问题。

（2）求解效率高：通过有效的剪枝策略，可以大大减少需要探索的解空间，从而提高求解效率。

（3）可以找到全局最优解：与某些只能找到局部最优解的启发式算法不同，分支定界法可以保证找到全局最优解（在给定时间内）。

3.缺点（1）内存消耗大：由于需要存储大量的子问题和它们的界，分支定界法可能会消耗大量的内存空间。

（2）实现复杂：分支定界法的实现通常比较复杂，需要仔细设计分支策略、定界方法和剪枝策略。

（3）可能受问题特性影响：对于某些特定类型的问题，分支定界法可能不是最有效的求解方法。

例如，当问题的解空间非常复杂或难以有效划分时，分支定界法的效率可能会受到严重影响。

4.应用领域分支定界法被广泛应用于各种实际问题的求解中，如生产调度、物流配送、资源分配、网络设计等。

在这些领域中，通过合理地定义变量、约束条件和目标函数，可以将实际问题抽象为最优化问题，并利用分支定界法进行求解。

分支定界法步骤

分支定界法步骤嘿，咱今儿个就来唠唠这分支定界法的步骤。

你说这分支定界法啊，就像是在一个迷宫里找出口，得一步步来，还得有策略呢！首先呢，得有个目标函数，就像你要去一个地方，得知道往哪儿走才是对的呀。

然后根据这个目标函数，把问题给划分成一个个小部分，这就好比把迷宫分成了好多条路。

接下来，就开始在这些小部分里探索啦。

咱得给每个部分设定一个界限，就像给每条路设个关卡一样，超过了这个界限，咱就先不考虑啦。

这一步可得仔细咯，不能马虎。

然后呢，咱就选择一个最有希望的部分继续深入。

这就像在迷宫里选了一条感觉最有可能走到出口的路。

沿着这条路走啊走，看看能不能找到更好的结果。

要是在这个过程中发现了一个比之前更好的解，那可就太棒啦！赶紧把它记下来，这说不定就是咱要找的答案呢。

有时候啊，走着走着发现路走不通了，咋办呢？那就得换条路试试呀，不能在一棵树上吊死嘛。

这分支定界法啊，就像是一场冒险，每一步都充满了未知和挑战。

你得有耐心，还得有智慧，才能在这复杂的迷宫里找到正确的方向。

你想想看，要是没有这一步步的分析和探索，那岂不是像无头苍蝇一样乱撞呀？那可不行，咱得有方法，有策略地去解决问题。

在实际应用中，这分支定界法可帮了大忙呢！它能帮我们解决很多复杂的问题，让我们能更高效地找到最优解。

所以说呀，这分支定界法的步骤可真不简单，每一步都得认真对待。

就像建房子一样，一砖一瓦都得放好，才能建成坚固的大厦。

咱在运用分支定界法的时候，也得这样，一步一个脚印，踏踏实实地去做，才能得到满意的结果呀！你说是不是这个理儿呢？。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

LP2 x1=？, x2=？
Z(2) ＝？
a
15
求（LP2） ,如图所示。
m ax Z x1 5 x2
x1 x2 2
( IP
2)
5
x1 x1
6
x2
30 4
x1
2
x 1 , x 2 0 且 为 整 数
⑵ 5x16x2 30
x2
⑴ x1 x2 2
A
B 3
⑶ x1 4
1
1
3
x1
x1 5x2 Z
a
16
求（LP2） ,如图所示。
m ax Z x1 5 x2
x1 x2 2
( IP
2)
5
x1 x1
6
x2
30 4
x1
2
x 1 , x 2 0 且 为 整 数
在C 点取得最优解。 即x1＝2, x2 =10/3, Z(2) ＝56/3≈18.7
⑵ 5x16x2 30
x2
⑴ x1 x2 2
m)
x
j
0,(
j
1.2L
n)
a
1
n
maxZ cj xj j 1
考虑纯 x j
bi
(i 1.2 m)
xj 0,( j 1.2 m)且为整数
整数问题的松弛问题：
判断题：整数问题的最优函 数值总是小于或等于其松弛 问题的最优函数值。
n
max Z c j x j j 1
a
13
LP x1=18/11, x2=40/11
Z(0) ＝19.8
x1≤1
x1≥2
LP1 x1=？, x2=？
Z(1) ＝？
LP2 x1=？, x2=？
Z(2) ＝？
a
14
LP x1=18/11, x2=40/11
Z(0) ＝19.8
x1≤1
x1≥2
LP1 x1=1, x2=3 Z(1) ＝16
( IP
2)
5
x1 x1
6
x2
30 4
x1
2
x 1 , x 2 0 且 为 整 数
现在只要求出（LP1）和（LP2）的最优解即可。
a
10
LP x1=18/11, x2=40/11
Z(0) ＝19.8
x1≤1
x1≥2
LP1 x1=？, x2=？
Z(1) ＝？
LP2 x1=？, x2=？
Z(2) ＝？
3
x1
x1 5x2 Z
a
9
先将（LP）划分为（LP1）和（LP2）,取x1 ≤1, x1 ≥2，有下式：
m ax Z x1 5 x2
m ax Z x1 5 x2
x1 x2 2
( IP 1)
5
x1 x1
6
x2
30 4
x1
1
x 1 , x 2 0 且 为 整 数
x1 x2 2
第三节 分枝定界法
（一）、基本思路
n
max Z c j x j j 1
考虑纯整数问题：
(
IP)
n
aij x j
j 1
bi
(i 1.2L m)
x
j
0,( j 1.2L
n)且为整数
n
m ax Z c j x j
j 1
整数问题的松弛问题：
(
L
P
)
n j 1
aij x j
bi
(i 1.2L
a
3
LP x1=18/11, x2=40/11
Z(0) ＝19.8
x1≤1
x1≥2
LP1 x1=1, x2=3 Z(1) ＝16
＃
LP2 x1=2, x2=10/3
Z(2) ＝18.5
x2≤3
x2≥4
x1≤2
LP21 x1=12/5, x2=3 Z(21) ＝17.4
x1≥3
LP22 无可 行解
＃
(LP)
n j 1
aij x j
bi
(i 1.2
m)
x j 0, ( j 1.2 m)
a
2
（二）、例题 例一：用分枝定界法求解整数规划问题（用图解法计算）
m ax Z x1 5 x2
x1 x2 2
5
x1
6
x2
30
x1
4
x 1 , x 2 0 且 全 为 整 数
记为（IP）
x1
4
x 1 , x 2 0
⑵ 5x16x2 30 ⑴ x1 x2 2 ⑶ x1 4
3
x1
x1 5x2 Z
a
6
x1＝18/11, x2 =40/11
Z(0) =218/11≈(19.8)
x2
即Z 也是（IP）最大值的上限。
m ax Z x1 5 x2
3
x1 x2 2
5
x1 x1
LP211 x1=2, x2=3 Z(211) ＝17
＃
LP212 x1=3, x2=5/2 Z(212) ＝15.5
＃
a
4
例一：用分枝定界法求解整数规划问题（用图解法计算）
m ax Z x1 5 x2
x1 x2 2
5
x1
6
x2
30
x1
4
x 1 , x 2 0 且 全 为 整 数
A
3
BC
⑶ x1 4
1
1
3
x1
x1 5x2 Z
a
17
LP x1=18/11, x2=40/11
6
x2
30 4
x 1 , x 2 0
⑵ 5x16x2 30 ⑴ x1 x2 2
(18/11,40/11)
⑶ x1 4
3
x1
x1 5x2 Z
a
7
LP x1=18/11, x2=40/11
Z(0) ＝19.8
a
8
x1＝18/11, x2 =40/11
Z(0) =218/11≈(19.8)
x2
m ax Z x1 5 x2
x2
x1 x2 2
( IP 1)
5
x1 x1
6
x2
30 4
3
x1
1
x 1 , x 2 0 且 为 整 数
此时B 在点取得最优解。
1
x1＝1, x2 =3, Z(1)＝16
⑵ 5x16x2 30 ⑴ x1 x2 2
A B
⑶ x1 4
1
3
x1
x1 5x2 Z
即Z 也是（IP）最大值的上限。
对于x1＝18/11≈1.64，
3
取值x1 ≤1， x1 ≥2
对于x2 =40/11 ≈3.64， 取值x2 ≤3 ，x2 ≥4
先将（LP）划分为（LP1）和 （LP2）,取x1 ≤1, x1 ≥2
⑵ 5x16x2 30 ⑴ x1 x2 2
(18/11,40/11)
⑶ x1 4
记为（IP）
解：首先去掉整数约束，变成一般线性规划问题
m ax Z x1 5 x2
x1 x2 2
5
x1 x1
6
x2
30 4
x 1 , x 2 0
记为（LP）
a
5
用图解法求（LP）的最 优解，如图所示。
x2
m ax Z x1 5 x2
3
x1 x2 2
5 x 1 6 x 2 3 0
a
11
先求（LP1）,如图所示。
m ax Z x1 5 x2
x2
x1 x2 2
( IP 1)
5
x1 x1
6
x2
30 4
3
x1
1
x 1 , x 2 0 且 为 整 数
1
⑵ 5x16x2 30 ⑴ x1 x2 2
A
⑶ x1 4
1
3
x1
x1 5x2 Z
a
12
先求（LP1）,如图所示。