当前位置：文档之家 › 第二章 线性规划问题解的性质分析

第二章 线性规划问题解的性质分析

  • 格式：ppt
  • 大小：763.50 KB
  • 文档页数：35

下载文档原格式

  / 35

合集下载

管理运筹学第二章 线性规划的图解法

管理运筹学第二章 线性规划的图解法


B、约束条件不是等式的问题：
若约束条件为 ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引进一个新的变量si ，使它等于约束右 边与左边之差 si=bi–(ai1 x1 + ai2 x2 + … + ain xn ) 显然，si 也具有非负约束，即si≥0， 这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn+si = bi
第二章 线性规划 的图解法
一、线性规划的概念 二、线性规划问题的提出 三、线性规划的数学模型 四、线性规划的图解法 五、线性规划解的情况 六、LP图解法的灵敏度分析
一、线性规划的概念
线性规划Linear Programming 简称LP，是一 种解决在线性约束条件下追求最大或最小的 线性目标函数的方法。 线性规划的目标和约束条件都可以表示成线 性的式子。
max z 3 x1 2 x2
2 x1 x2 ≤ 10 设备B台时占用 s.t. x1 x2 ≤ 8 x , x ≥ 0 产量非负 1 2
决策变量 （decision variable） 目标函数 （objective function） 约束条件 （subject to）

-ai1
x1-ai2 x2- … -ain xn = -bi 。
例1.3：将以下线性规划问题转化为标准形式 Min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 ≤15.7 4.1 x1 + 3.3 x3 ≥8.9 x1 + x2 + x3 = 38 x 1 , x 2 , x3 ≥ 0
管理运筹学_第二章_线性规划的图解法

管理运筹学_第二章_线性规划的图解法


A
1×250=250千克．
原料B 0 1 250千克
约束条件中没使用的资源或能力称之为松弛量。
用Si表示松弛量，对最优解 x1=50,x2=250来说：
约束条件
松弛变量的值
设备台时数
s1=0
原料A
s2=50
原料B
s3=0
8
线性规划标准型
加了松弛变量后例1的数学模型可写成：
目标函数：max z=50x1+100x2+0s1+0s2+0s3，
约束条件： x1+x2+s1=300,
2x1+x2+s2=400,
x2+s3=250, x1,x2,s1,s2,s3≥0
如何把模型化为 标准型？
三个特征：
一、约束条件为等式；
二、约束条件右端常数项非负；
三、所有变量非负。
称为线性规划的标准形式。
9
线性规划问题解的情况：
1．若有最优解，一定能在可行域的顶点取得。
a21x1+a22x2+…+a2nxn=b2, ………………………… am1x1+am2x2+…+am nxn=bm. x1, x2,…,xn≥0.
其中ci为第i个决策变量xi在目标函数中的系数， aij为第i个约束条件中第j个决策变量xj的系数， bj(≥0)为第j个约束条件中的常数项。
16
灵敏度分析
C 100
1设备台时获利500/10=50
元。 x1
O 100 D300 X1+X2=300
X1+X2=310
你知道对偶价格吗？
21
对偶价格的概念
线性规划的解与最优解知识点总结

线性规划的解与最优解知识点总结

线性规划的解与最优解知识点总结在现实生活和工作中，我们经常会遇到需要最优化某个目标函数的问题。

线性规划作为一种常见的数学优化方法，在各个领域中得到了广泛应用。

它能够帮助我们在一定的约束条件下，找到目标函数的最佳解。

本文将对线性规划的解与最优解的相关知识点进行总结。

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ₙx₁, x₂, ..., xₙ ≥ 0```其中，Z表示目标函数的值，c₁, c₂, ..., cₙ为目标函数的系数，aᵢₙ为约束条件中的系数，b₁, b₂, ..., bₙ为约束条件的右边常数，x₁,x₂, ..., xₙ为决策变量。

2. 解的存在性线性规划问题存在三种解的情况：无解、有界解和无界解。

如果约束条件与目标函数之间存在矛盾，例如出现一个约束条件为 a₁₁x₁ +a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁，而目标函数的系数为 c₁ > a₁₁，那么这个线性规划问题就没有解。

有界解指的是线性规划问题在满足所有约束条件的情况下，能够找到目标函数的最大值或最小值。

无界解意味着目标函数可以无限制地增大或减小。

3. 最优解的性质线性规划问题的最优解具有以下性质：- 最优解必然出现在可行域的顶点上。

可行域是指所有满足约束条件的解的集合，而顶点则指可行域的边界上的点。

- 如果最优解存在，那么至少存在一个顶点是最优解。

- 如果可行域是有限的，则一定存在一个顶点是最优解。

- 如果最优解存在，那么一定有一条或多条约束条件在最优解上取等号。

第2章 线性规划

第2章 线性规划


目标函数下降
MAXZ=4X1-3X2 S.T. X1+2X210 X16 X24 X11 X1,X20
X2=4
B A
目标函数上升
C
X2 0
E
D
X1 X1=6
4X1-3X2=0
X1=1
对解的讨论： .唯一解 .无穷解 .无解： 可行域空集 可行域无界
X2 X1+2X2=10 X2=4
X1 0
a11 a12 a1n 约束方程组 A P1 , P2 , Pn 系数矩阵 a m1 a m 2 a mn
A为m ×n矩阵（ m为约束方程个数，n为变量个数）
a11 a12 a1n A P1 , P2 , Pn a m1 a m 2 a mn
消除负的右端常数项
MAXZ=-X1-3(X3-X4) S.T. 6X1+7(X3-X4)8 X1-3(X3-X4) ≥6 X1-(X3-X4)=3 X1、X3、X4 0
约束方程还不是等式约束
人为添加变量，成为等式约束
对于“≤”约束，添加松弛变量 对于“≥”约束，添加剩余变量
6X1=5X1+3X2 S.T. 3X1+5X215
max Z 5 x1 3 x 2 3 x1 5 x 2 x 3 15 5 x1 3 x 2 x 4 10 x1 , x 2 , x 3 , x 4 0
5X1+2X210
X1,X20
2、给出基本可行解
• 6．基本可行解：满足非负条件
对于D1 ，基变量为X4、X5，X1、X2、X3为非基变量，令 X1、X2、X3=0， X4 = 8、X5 = 1 对于D2 ，基变量为X1、X2，X3、X4、X5为非基变量，令 X3、X4、X5 =0， X1 = -13/4 、X2=15/4
线性规划问题解的概念和性质

线性规划问题解的概念和性质


线性规划问题解的应用之一是生产计划问题，通过合理安排生产计划，最大化利润并满足市场需 求。
线性规划问题解的生产计划问题需要考虑多种因素，如生产成本、市场需求、产品价格等，以制 定最优的生产计划。
线性规划问题解的生产计划问题可以通过建立数学模型进行求解，利用计算机软件进行优化和模 拟。
线性规划问题解的生产计划问题在实际应用中具有广泛的应用价值，可以提高企业的生产效率和 经济效益。
线性规划问题的标准形式
初始解的求解方法
初始解的判断准则
初始解的调整策略
迭代过程：通过不断迭代更新解，逐步逼近最优解 终止条件：当迭代过程中解的变化小于预设阈值或达到最大迭代次数时，终止迭代 收敛性：算法收敛于最优解的充分必要条件是所有约束条件都是“可行”的 算法复杂度：迭代次数与问题规模呈指数关系，需要选择合适的算法和参数
方案。
添加 标题
添加 标题
添加 标题
添加 标题
定义：在给定风险 水平下最大化收益， 或在给定收益水平
下最小化风险
应用场景：股票、 债券等金融资产的
投资组合配置
线性规划问题解的 应用：通过线性规 划方法找到最优投 资组合，实现风险
和收益的平衡
线性规划问题解的 概念和性质：在投 资组合优化问题中， 线性规划方法用于 求解最优解，其概 念和性质对于理解 和应用投资组合优
解的唯一性：线性 规划问题有唯一最 优解
解的稳定性：最优 解不会因约束条件 的微小变化而发生 大的改变
解的敏感性：当目 标函数系数或约束 条件发生变化时， 最优解可能会发生 改变
算法原理：通过 不断迭代，寻找 最优解
适用范围：线性 规划问题
求解步骤：确定 初始解，计算目 标函数值，迭代 更新解
第2章线性规划

第2章线性规划


线性规划数学模型的三个要素： 决策变量、目标函数、约束条件
线性规划数学模型（4）
线性规划数学模型的一般形式的其他表示方式：
（2） max(min)
s.t.
n
z c j x j
j 1


n
aij x j
(, )bi (i 1,, m)
j1
x j 0( j 1,n)
2 0 0


B2 1 1 0
1 0 1
对应的基解分别为 x 1 (0,0,2,2,5) 和 x 2 (1,0,0,3,6) ，其中 x1 为基本可行解， x2 不是基本可行解。
线性规划的基本概念
●线性规划的基矩阵(基)、基变量、非基变量
目标函数 约 束 条 件
d、bi≥0
“bi≤0” —— 乘“-1” ， -bi≥0
线性规划数学模型（8）
练习题：将线性规划数学模型转化为标准形式
1、min z= 2x1-2x2+3x3
-x1+ x2+ x3 = 4
-2x1+ x2 - x3≤6
x1 ≤0, x2 ≥0 ，x3无约束
2、min z= x1+x2 x1- x2+2 x3 ≥2
可行解 满足线性规划所有约束条件的各变量的 一组值X=（x1，x2，…，xn）T，称为线性规划 问题的可行解。全部可行解的集合称为可行域。 最优解 使线性规划的目标函数达到以最优值 （依照具体问题，或者是极大值，或者是极小 值）的可行解称为线性规划问题的最优解。 上述两个概念，对于一般形式、标准形式都适 用，而下述概念，仅适用于标准形式。
基解 在标准形式线性规划的约束方程组中，对应 基B，令所有非基变量都等于零，求解约束方程组 AX=b，可惟一得出基变量的一组值，这些值和取 零的非基变量的值合起来，称为线性规划问题的基 解或基本解。 基的个数不超过 Cnm，一个基对应一个基解，故基解 的个数也不超过 Cnm。基解中非零分量的个数不会大 于约束方程的个数m。若一个基解的基变量中有取 零值的，则此基解称为退化的，否则称为非退化的 。
第二章线性规划

第二章线性规划

线性规划研究的问题主要有以下两类。 (1) 给出一定量的人力、物力、财力等资源，如何统筹规划这些有限资源完成最大 任务。 (2) 给定一项任务，如何运筹规划，合理安排，以最少资源来完成它。 线性规划要研究的两类问题中都有一个限制条件：第一类问题是给出一定量的人力、 物力和财力等资源；第二类问题是给定一项任务。这种限制条件可以用一组线性方程组或 线性不等式组来描述。限制条件所要达到的结果称为“目标”，第一类问题的目标是利用有 限资源完成最大任务，第二类问题的目标是以最少资源完成给定任务。可以用一个线性函 数来描述这种目标，称这个线性函数为目标函数。 由此可见，各类问题尽管限制条件与目标不相同，但规划的目的就是使这些资源发挥 最大限度的作用，从而完成最多最大的任务。换句话说，也就是资源的最优利用问题。用 数学形式表示的话，规划的目的就是在给定的限制条件(或称约束条件)下，求目标函数的极 值问题(包括极小值和极大值)。 下面用一个例题来说明线性规划问题的特点。
0.1x1 0.17x2 0.14x3 0.22x4 0.07x5 ≥140 000 平均信用度不低于 6，即
非负约束，即
(11x1 8x2 10x3 4x4 10x5 ) /(5106 ) ≥6 xi ≥ 0 ， i =1, 2, 3, 4, 5
综上所述，该问题的数学模型可以表示为
16
第二章 线性规划
三、人力资源问题的数学模型
例 2-4 某商场因为每天顾客的数量不同，所以每天需要的营业员人数也不同。经过统 计分析，商场对营业员的需求量如表 2-5 所示。按照规定，营业员每周工作五天后，连续 休息两天。问：应如何安排营业员的作息，既能满足工作需要，又使得雇佣的营业员人数 最少？
表 2-3 产品规格
产品名称 X
第2章 线性规划图解法

第2章 线性规划图解法

-8
x2
6
4
可行域
6
0
x1
23
3. 画出目标函数的图形(通常可画出当目 标函数值为零时的(基准)目标函数图)，确 定目标函数平行移动的方向，并沿目标函 数直线的法向用小箭头标出。
例1. max Z = x1+3x2 s.t. x1+ x2≤6 -x1+2x2≤8 x ≥0, x ≥0 1 2
大轿车座椅的限制： 非负限制：
5 x1 2.5 x2 2500 x1 400 x1 0, x2 0
分析：问题是如何安排生产使得工厂获利最大？
项目 产品 生产能力 5 (小时 ⁄ 辆) 2.5 (小时 ⁄ 辆) 2500 (小时 ⁄ 年) 钢材 (吨 ) 装配座椅 (辆 ⁄ 年 ) 利润 (千元 ⁄ 辆)
4
§2.1
线性规划问题的提出
线性规划研究的内容和问题
线性规划是研究在线性不等式或等式的限 制条件下，使得某一个线性目标函数取得最大 （或最小）的问题。常见的线性规划问题有： （一） 运输问题 （二） 生产的组织与计划问题 （三） 合理下料问题 （四） 配料问题 （五） 布局问题 （六） 分派问题
5
7
例1. 某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产， 已知生产单位产品所需的设备台时及A、B两种原材料的 消耗、资源的限制，如下表：
设备 原料 A 原料 B 单位产品获利 Ⅰ 1 2 0 50 元 Ⅱ 1 1 1 100 元 资源限制 300 台时 400 千克 250 千克
问题:工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获 利最多？
6
§2.1
线性规划问题的提出
线性规划发展前景
另一方面，以线性规划为基础而发展起 来的多部门的线性规划 , 多时期的线性规划， 模糊线性规划，随机线性规划，以及整数规 划，非线性规划，目标规划等等，为现代管 理中各类实际问题的解决提供了科学的方法。 目前线性规划的理论研究仍十分活跃，其应 用前景也越来越广阔，它已成为国家重点推 广的现代管理方法之一。
运筹学第二章线性规划的对偶理论

运筹学第二章线性规划的对偶理论


(5.5) (5.6)
4.3 对偶问题的基本性质
证： 设B是一可行基，于是A=(B,N)
max z=CBXB+ CNXN BXB+BXN +Xξ=b X,XB,Xξ ≥0
其中Yξ=(Yξ1, Yξ2)
min ω =Yb YB－Yξ1=CB YN－Yξ2=CN Y, Yξ1 Yξ2 ≥0
(5.5) (5.6)
x1﹐x2 ≥0
关系？
对原模型设： 1 2
A= 4 0 b=(8,16,12)T C=(2，3) 04
X=（x1，x2）T Y=（y1，y2 ，y3 ） 则可得:
4.1 对偶问题的提出
min ω=8 y1+16y2 +12y3
y1+4y2
≥2
2 y1 +4y3≥3
与
y1 ， y2 ，y3≥0 12
max z＝2x1+3x2 x1＋ 2x2 ≤8
4x1
≤16
4x2 ≤12
x1﹐x2 ≥0
有何关 系？
对愿模型设： A= 4 0 04
b=(8,16,12)T C=(2，3)
X=（x1，x2）T
Y=（y1，y2 ，y3 ） 则可得:
max z=CX AX≤b （5.1） 和
min ω =Yb YA ≥ C （5.2）
120
A=
1 -3
0 2
1 1
1 -1 1
b=(2,3,-5,1)T C=(5,4, 6)
确定约束条件
YA
C
x1 ≥0 ﹐x2≤0, x3 无约束
解：因原问题有3个变 于是 量，4个约束条件， 所以对偶问题4个 变量，3个约束条
北交大交通运输学院《管理运筹学》知识点总结与例题讲解第2章 线性规划

北交大交通运输学院《管理运筹学》知识点总结与例题讲解第2章 线性规划

第二章线性规划教学目的：了解线性规划的基本概念，理解线性规划最优化原理、单纯形法原理，掌握单纯形法及其矩阵描述、人工变量法、，能够对简单的问题建模。

教学重点：线性规划的含义、性质；线性规划问题的求解方法——图解法、单纯形法。

线性规划模型的建立非标准型线性规划问题转化为标准线性规划问题；线性规划问题的图解法；解的存在情况判断；大M法；两阶段法；单纯形法的矩阵表示；教学难点：单纯形法的求解思想、矩阵表示、对偶理论、对偶单纯形法以及灵敏度分析。

学时： 8学时2.1 线性规划(Linear Programming,LP)问题及其数学模型（1学时）我们应用数学规划模型求解实际问题中，将实际问题抽象成数学模型，然后再对其求解。

2.1.1线性规划问题提出我们用一个简单例子来说明如何建立数学规划问题的数学模型。

例2.1 某家具厂生产桌子和椅子两种家具，有关资料见表2－1。

解：用数学语言来描述生产计划安排问题，这个过程称为建立其数学模型，简称建模。

设：①桌子、椅子生产的数量分别为x1，x2，称为决策变量。

因为产量一般是一个非负数，所以有x1，x2≥0，称非负约束。

②限制条件为木工和油漆工的加工时间约束了产品的生产量x1，x2。

约束如下：4x1＋3x2≤1202x1＋x2≤50③生产桌子、椅子x 1，x 2所得总收入为Z ，显然Z ＝50x 1＋30x 2。

我们希望总收入值能达到最大，这个关系用公式表达为max Z ＝50x 1＋30x 2 把上述所有数学公式归纳如下12121212max .0z 50x 30x 4x 3x 120s t 2x x 50x x =++≤⎧⎪+≤⎨⎪≥⎩，这就是一个最大化的线性规划模型。

例 2.2（运输工具的配载问题）有一辆运输卡车，载重2.5t ，容积183m ，用来装载如下的两种货物：箱装件125kg/个、0.43m /个；包装件20kg/个、1.53m /个。

问：如何装配，卡车所装物件个数最多？解 根据题意，设箱装件1x 个，包装件2x 个，那么需要满足条件：体积约束 120.4 1.518x x +≤重量约束 12125202500x x +≤非负约束12,0x x ≥目标要求 max z=12x x +我们对上面的式子稍作整理，便得到下面的形式：max z=12x x +1212120.4 1.518125202500,0x x x x x x +≤⎧⎪+≤⎨⎪≥⎩ 上述两例中所提出的问题，最终都归结为在变量满足线性约束条件的前提下，求使线性目标函数最大或最小的问题，这种问题称为线性规划问题。

线性规划图解法

线性规划图解法

适用于任意变量、但必需将 一般形式变成标准形式
下面我们分析一下简单的情况—— 只有两个决策 变量的线性规划问题，这时可以通过图解的方法来 求解。图解法具有简单、直观、便于初学者窥探线 性规划基本原理和几何意义等优点。
精选课件
图解法
Page 2
一、线性规划的图解法（解的几何表示）
对于只有两个变量的线性规划问题，可以在二维直角坐标 平面上作图表示线性规划问题的有关概念，并求解。
X1 + 1.9X2 = 10.2 (≤)
8=5X1+4X2 此点是唯一最优解 （0，2）
D可行域
43=5X1+4X2
max Z
X1 + 1.9X2 = 3.8(≥)
min Z
o
L0： 0=5X1+4X2
精选课件
X1 - 1.9X2 = 3.8 (≤)
Page 18
x1
图解法
x2
6 3x1+x2=6(≥) 4
X = X1 + (1- ) X2 则必定有X = X1 = X2，则称X为S的一个顶点。
精选课件
图解法
Page 24
可以证明，线性规划的可行域以及最优解有以下 性质：
（1）、若线性规划的可行域非空，则可行域必定为一凸集；
（2）、线性规划问题的基本可行解对应于可行域的顶点；
（3）、若可行域有界，线性规划问题的目标函数一定可以在 其可行域的顶点上达到最优，或在可行域的某个顶点（唯一最 优解）或在某两个顶点及其连线上（无穷多最优解）得到。
2x1+ x2 50 z = 50x1+30x2= 1350
z = 50x1+30x2= 900
(15, 20)

运筹学—线性规划第2章


1 1
1 0
0 1
0 0
6 2 0 0 1
1 0 0
则
B 0
1
0
的列是线性无关的，即
1
0
0 0 1
p3 0, p4 1 0 0
•
0
p5 0 是线性无关，因此 1
x3
x4
x5
是, 0
p2
1 2
不在这个基中，所以x1,
x2为非基变量。
定义10：使目标函数达到最优值的基本可行解，称为基
本最优值。
• 例4：（SLP)如例3，试找一个基本可行解。
1 1 0
解：B1
1
0
0
是其一个基矩阵.p1,p3, p5是一个基。
6 0 1
则 x1 , x3, x5为基变量。X2, x4为非基变量。令 x2=x4=0. 得x1=2, x3=3, x5=9. 故 x1=(2,0,3,0,9)是原问题的一个基本 可行解，B1为基可行基。
•当 由0连续变动到1时，点z由y沿此直线连续的变动到x，且 因z-y平行x-y，则有：z y (x y) 于是有：
z x (1 ) y
•这说明当 0 1 时，x (1 ) y表示以x.y为端点的直线段
上的所有点，因而它代表以 x.y为端点的直线段。 一般地，如果x.y是n维欧氏空间Rn中的两点，则有如下定义：
• 定义14：设R是Rn中的一个点集，（即R Rn），对于任意 两点x R, y R 以及满足0 1 的实数 ,恒有
x (1 )y R
则称R为凸集。
• 根据以上定义12及13可以看到，凸集的几何意义是：连接凸 集中任意两点的直线段仍在此集合内。
其可行域如上图，可行解（3，1，0，0）T。用x1, x2 表示则为图上点（3，1）。由图可见这不是可行域的 顶点。而我们将证明基本可行解是可行域的顶点。而 在例4中p1,p3线性无关，所以B=(p1,p3)是一个基矩阵， 对应的基本解为（4，0，0，0）T。用坐标x1, x2表示则 为平面上的点（4，0），是上图可行域的顶点。

第二章 线性规划解的概念、性质及图解法


上页
下页
返回
习题：用图解法求下列线性规划:
可行域为无界 区域一定无最 优解吗？
x2
2 x1 x2 2
max z = 2x1 + 2x2 s.t. 2x1 – x2 ≥ 2 -x1 + 4x2≤ 4 x1，x2 ≥ 0
Note:
x1 4 x2 4
可行域为无界区域，
目标函数值可无限
x(1) (1 ) x(2) S 则称 S 是一个凸集。
几何意义：如果集合中任意两点连线上的一切点都在 该集合中，则称该集合为凸集。
凸集
上页
下页
返回
定义 2
设 x R , i 0, i 1, 2,, k , 且 i 1， 则称
(i ) n i 1
k
x 1 x (1) 2 x (2) k x ( k )
上页 下页 返回
3.可行解与最优解
Ax=b，x≥0；
上页
下页
返回
4.线性规划的可行域和最优解的性质
1.若线性规划的可行域非空，则可行域必定 为一凸集． 2.若线性规划的可行域非空，则至多有有限 个极点.
3.若线性规划有最优解,则至少有一个极点是 最优解.
可行域内 无限个 可行解 搜索
可行域的 有限个极点
x2
上页 下页 返回
图解法
步骤 一： 由全 部约 束条 件作 图求 出可 行域 ；
9— 8—
目标函数
Max Z = 2x1 + 3x2
约束条件
x2
7—
6— 5—
x1 + 2x2 8 4x1 16 4x2 12 x 1、 x 2 0

线性规划问题解的基本理论

8.基本可行解（对应的基为可行基）：满
足非负条件的基本解。
4
9.退化的基本可行解
非零分量个数小于m（至少有一个基变量 取值为0）。
10.最优基
该基对应的基本可行解为LP的最优解。
结论
基本解的个数≤Cmn
基本可行解的非零分量均为正分量 个数不超过m
5
皮肌炎图片——皮肌炎的症状表现
皮肌炎是一种引起皮肤、肌肉、 心、肺、肾等多脏器严重损害的， 全身性疾病，而且不少患者同时 伴有恶性肿瘤。它的1症状表现如 下：
（即可行域）
D
X
n
Pj x j
j 1
b, x j
0是凸集。
定理3-2 线性规划几何理论基本定理
若
D
X
n
Pj x j
j 1
b,
x，j
0
则X是D的一个顶点的充分必要条件是X为线性
规 划的基本可行解。
8
定理3-3 若可行域非空有界，则线性规划问 题的目标函数一定可以在可行域的顶点上 达到最优值。
化为只在可行域的顶点中找，从而把一 个无限的问题转化为一个有限的问题。
☺ 若已知一个LP有两个或两个以上最
优解，那麽就一定有无穷多个最优解。
11
二、 线性规划问题 解的概念和性质
1
一、LP问题的各种解
1. 可行解：满足约束条件和非负条
件的决策变量的一组取值。
2. 可行解集：所有可行解的集合。 3. 可行域：LP问题可行解集构成n维
空间的区域，可以表示为：
D {X | AX b, X 0}
2
4.最优解:使目标函数达到最优值的可行解。 5.最优值：最优解对应目标函数的取值。 6.求解LP问题:求出问题的最优解和最优值。

解的性质

LP问题解的性质
标准形式
max z c j x j
j 1 n
X ( x1 , x2 ..., xn )T
max Z CX
AX b X 0
a
j 1
n
ij
x j bi i 1,2,...,m
xj 0
j 1,2,...,n
A表示…，C表示…，b表 示…
1
定义1：在线性规划问题中，凡满足所有约束条件的解成为线 性规划问题的可行解。可行解的集合称为可行解集（可行 域），记作D。
极点与基可行解的等价性定理：线性规划问题的可行解 集为D，D的极点与线性规划问题的基可行解是对应的。
若线性规划问题可行域有界，则此问题的最优解一定 可以在其可行域的极点（顶点）上达到。若线性规划 问题可行域无界，则该线性问题可能可能无最优解， 也可能有最优解，若有最优解，该最优解必定在某顶 点上达到。
a11 a B 21 a m1 a12 a22 am 2 a13 ... a23 ( P 1, P 2 ,...P m) am 3 ...
i 1,2,...m ）为基向量，与基向量相应的变量 x （ i 1,2,...m） 称 P（ i 为基变量，不在基向量中的列向量，称为非基向量，其对应 的变量成为非基变量。
5. 满足约束条件而又使目标函数取得极值 (极大或极小) 的 解, 称为最优解。若线性规划问题有最优解,则这个最优解一 定可以在可行解集D的极点上达到。
7
6
线性规划问题的解的结论： 1.满足线性规划问题约束条件的解称为可行解，可行解的全 体称为可行域。 2. 当一个可行解中非零分量所对应的列向量线性元关时, 则 称这个可行解为基可行解, 所有的基可行解都是这一凸集的 极点。 3. 有可行解, 则必有基可行解。 4. 基可行解的个数是有限的, 即凸集的极点个数是有限的。

第2章线性规划(对偶问题)


• 解：根据上述对偶关 系，可以写出原问题 的对偶问题：
m in W 5 y 1 4 y 2 y 3 y1 y1 s .t . y 1 y 1 y1 2 y2 y3 2 y2 1 3 y2 y3 3 y3 1 0 , y3 0 , y 2无 约 束
• 令y4=y2-y3 ，得：
• Min W=y1+2y4 S.t. y1+2y4 1 2y1-3y4 2 5y1-4y4 -3 y1 0, y4无符号约束
原问题与对偶问题的对应关系
原问题（或对偶问题） 目标函数为 Max Z 变量 n个 0 0 无约束 对偶问题（或原问题） 目标函数为 Min W n个 ＝ 约束条件
– 设X*是原问题的可行解，Y*是对偶问题的可行
解，当CTX*=bTY*时，X*，Y*是最优解。
– 证明：由弱对偶性，可知原问题的所有可行解
X’均满足 CT X’ bTY*
又因为CTX* = bTY* ，所以CT X’ CTX* ，即： X*是使目标函数取值最大的可行解。因而是最 优解。 同理可证Y*也是最优解。
m个 ＝ 价值系数cj 约束条件右端项bi 约束条件的系数矩阵A 约束 条件
m个 变量 0 0 无约束 约束条件右端项cj 价值系数bi 约束条件的系数矩阵AT
例：
• 写出下面线性规划问 题的对偶问题： • 1.
m a x Z 2 x1 x 2 3 x 3 x 4 x1 x 2 x 3 x 4 5 2 x x 3x 4 1 2 3 s .t . x1 x 3 x 4 1 x1 , x 3 0 , x 2 , x 4 无 约 束

第二节 线性规划解的概念、性质及图解法

5
2.线性规划的图解法 2.线性规划的图解法
例 2.4: 某工厂拥有 A 、 B 、 C 三种 类型的设备，生产甲、乙两种产品。 类型的设备，生产甲、乙两种产品。 每件产品在生产中需要占用的设备机 时数， 时数，每件产品可以获得的利润以及 三种设备可利用的时数如下表所示：
产品甲 设备A 设备B 设备C 利润（元/件） 3 2 0 1500 产品乙 2 1 3 2500
无可行解的情况
22
2.线性规划的图解法 2.线性规划的图解法
根据以上例题，进一步分析讨 论可知线性规划的可行域和最优解 有以下几种可能的情况 1.可行域为封闭的有界区域 1.可行域为封闭的有界区域 (a)有唯一的最优解； (a)有唯一的最优解； (b)有无穷多个最优解； (b)有无穷多个最优解； 2.可行域为封闭的无界区域 2.可行域为封闭的无界区域 (c)有唯一的最优解； (c)有唯一的最优解；
31
2.线性规划解的概念 2.线性规划解的概念
直线B、E的交点对应于约束条件(A)、（B）、 的交点对应于约束条件( （C）、（E）、（G）的解，即： 的解， x(7) = (20,0,5,0,75)T 20, 75) 直线C、D的交点对应于约束条件(A)、（B）、 的交点对应于约束条件( （C）、（D）、（H）的解，即： 的解， x(8) = (0,25,15,15,0)T 25,15,15, 直线C、E无交点（C、E相互平行） 无交点（ 相互平行） 直线D、E的交点对应于约束条件(A)、（B）、 的交点对应于约束条件( （C）、（D）、（E）的解，即： 的解， x(9) = (0,0,65,40,75)T 65,40,75)
26
2.线性规划解的概念 2.线性规划解的概念
Max z = 1500 x1 + 2500 x2 s.t. 3x1+2x2+x3= 65 (A) (B) 2x1+x2+x4= 40 3x2+x5= 75 (C) x1 ,x2 ,x3 ,x4 ,x5 ≥ 0 用（D）（E）（F）（G）（H） 分别表示x1 = 0、x2 = 0、x3 = 0、 x4 = 0、x5 = 0 。 这里一共有8个约束条件，其中3个等 式约束
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

例2.6 将下面的线性规划问题化为标准形： max s = x1+2x2-3x3
x1 2 x2 x3 5 2 x1 3 x2 x3 6 x1 x2 x3 2 3 x2 12 x1 , x2 , x3 0
解 引进非负变量x4，x5，x6，min s x 2 x 3 x 1 2 3 则原问题的标准形为： x1 2 x2 x3 x4 5 2 x1 3 x2 x3 x5 6 松弛变量 x1 x2 x3 2 3 x2 x6 12 x1 , , x6 0 剩余变量
其中
Ax b s.t . x 0 c=(c1，c2，…，cn)
a1n a2 n amn
价值向量
约束矩阵
a11 a12 a a A 21 22 a m1 am 2
资源向量 b1 x1 待定决策向量 b x 2 b x 2 b x m n
[0,1] x x(1) (1 ) x(2) 0,
Ax A[x (1) (1 ) x ( 2) ] Ax (1) (1 ) Ax ( 2) b
x x(1) (1 ) x(2) S
（二）线性规划问题解的性质
x2 A B 2x1+5x2=19 C
O
D x1 2x1+5x2=0
例2.2 若将例2.1中的目标函数改为S=x1+2x2
x1 4 x2 3 s.t . x1 2 x2 8 x1 , x2 0
x2
A B
x1+2x2=8
C
BC边上每一 点的坐标都 是最优解
O D
①画直线x-y+5=0，确定不等式x-y+5≥0表示的区域； ②画直线x+y=0，确定不等式x+y≥0表示的区域； ③画直线x=3，确定不等式x≤3表示的区域； ④取公共区域部分。
y x+y=0 A
-4 -2 4 2
x-y+5=0 C
o
2 4
B
x
x=3
基本概念： (1) z= 2x+y
x 4 y 3 (2). 3 x 5 y 25 x 1
定理2 x是基础可行解 x是可行域S中的极点. Ax b 证 设LP问题: min s = cx s.t . x0 S是其可行域， “” 即若x是可行域S中的极点，则x是基础可行解. ; (1). 当x 0时, 显然x是基础可行解
(2). 当x 0且为极点时,
设x的所有非零分量为xi1 , xi2 ,, xik (k m), 其所对应的列向量为Pi1 , Pi2 ,, Pik (k m), 问题转化为说明向量组Pi1 , Pi2 ,, Pik 线性无关.
例2.3、若目标函数为 min s = 2x1+2x2
x2
⑵作目标函数 的等值线
⑶确定最优点 因此，最优解 为 x1=1, x2=0
O C B
x1 x2 1 s.t . x1 2 x2 0 x1 0, x2 0
2x1+2x2=10
A
D x1
相应的目标函数 最小值为 s=2。
x2 B 2x1+5x2=19
A
C
O
D
2x1+5x2=0
x1
(3). 确定最优点
先确定目标函数值增大的方向，沿着这个方向平 行移动直线 s= 2x1+5x2，当移动到 B点时，s值就在可 行域上达到最大,从而确定B点就是最优点，
x2 3 x1 2 x 2 8
得最优解为x1=2，x2=3。 相应的目标函数的最大值为 S=2×2+5×3=19.
即 若对于x (1) ，x (2) ∈S，x=α x (1) +(1-α) x (2) ∈S （0≤α≤1），则称S为凸集。 例如： (2) x (2) x (2) x (1) x (1) x (2) x (2) x (1) x x
(1)
x (1)
3. 极点 (顶点)
若凸集S中的点x，不能成为S中的内点，则称x为S的 极点（顶点）。 即， 若对于x (1) x (2) ∈S, 不存在α (0<α<1), 使 x=α x (1) +(1-α) x (2) 则称x为S的极点（顶点）。
2x1+2x2=10
A B D O C x1
2x1+2x2=6
2x1+2x2=2
例2.5、min s =2x1+2x2
x1 x2 1 s.t . x1 x2 2 x1 0, x2 0
x2
如图，
没有可行解， 故没有最优解。
O x1
-x1+x2=1
x1+x2= -2
a1 j a Pj 2 j a mj
( j 1,2,, n)
•
非标准形问题的标准化
下面举例说明如何将非标准形线性规划问题 化为标准形。
（1）目标函数 若问题的目标函数为最大化 max s = cx， 则 可化为求 min s’ = －cx，即可。 （2）约束条件 a) 约束为≤形式的情形。如 2x1-x2+3x3≤18 则加入一个非负变量x4≥0，改为： 2x1-x2+3x3+x4=18 变量x4称为松弛变量。
（二）线性规划问题解的性质 定理1 线性规划问题的可行解集（可行域）为凸集。 Ax b 证 设LP问题: min s = cx s.t . x 0 S是其可行域， 对于x (1) x (2) ∈S, α [0,1]
考查 x=α x (1) +(1-α) x (2) ∈S
由于x (1) , x ( 2) S , x (1) 0, x ( 2) 0, Ax (1) Ax ( 2) b
LP问题
min s = cx
min s = cx
Ax b s.t . x 0
向量表示
n x j Pj b s.t . j 1 x 0
A ( P1 , P2 ,, Pn )
a1 j a Pj 2 j 是约束条件中 x j的系数, ( j 1,2,, n) a mj Pj也称为 x j 对应的向量.
解 (1). 确定可行域 先作: x1≥0 x2≥0 再作： x1 ≤4 x2 ≤3 x2 A B C
O x1 +2 x2 ≤8
D
x1
得可行域(见上图)
(2). 作目标函数的等值线 目标函数s=2x1+5x2 它代表是以 s 为参数 的一族平行线 由小到大给s 赋值，可得一 组平行线，而 位于同一直线 上的点具有相 同的目标函数 值，因而称为 等值线。
A（5，2） B（1，1） 3x+5y-25=0
1 x
2. 两个变量的线性规划问题的图解法一般过程
对于仅具有两个变量的线性规划问题，利用 作图的方法求最优解，简单、直观。 例2.1 max s = 2x1+5x2 x1 4 x 3 约束条件 2 x1 2 x2 8 x1 , x2 0
反证法 若向量组 Pi1 , Pi2 ,, Pik 线性相关 则一组不全为零的数 1 , , k , 使得 1 Pi1 2 Pi2 k Pik 0
定理2 x是基础可行解 x是可行域S中的极点.
1 o
y
x, y
问题2：
x y 1 0
1
x
l：x+y-1=0 y 1 x+y-1＜0 o x+y-1＞0 1 x
以二元一次不等式 x + y-1 ＞0的 解为坐标点的集合 表示什么图形？
l：x+y -1=0
练习
x y50 画出不等式组 x y 0 表示的平面区域。 x 3 解：
§2.3 线性规划问题解的性质
（一）几个概念
1. 可行解、基础可行解、最优解、基础最优解 我们把满足约束条件的 设线性规划问题 ( 0) x min s = cx 1 ( 0) x2 ( 0) x Ax b x ( 0) x 0 n 称为LP问题的可行解。 使目标函数取最小值的可行解，称为最优解。
若 x(0)=0，或 x (0)的非零分量所对应的系数列向 量组线性无关时，称可行解x (0)为基础可行解。使目 标函数取最小值的基础可行解，称为基础最优解。
2. 凸集 点集中任意两点的连线段整个均是该点集的点， 称该点集为凸集。
连接 n 维点集合S中任意两点 x (1) ，x (2)的线段 仍在S内，则称S为凸集 。
(2) 约束条件也有多种形式
这种多样性不仅给研究带来不便，而且使你难以寻 找一种通用解法。
人们发现：线性规划问题的各种不同形式可以相互 转化。因此，只需给出一种形式的解法。
线性规划问题的标准形式如下： min s = c1x1+c2x2+…+cnxn
a11 x1 a12 x2 a1n xn b1 一般有 m n, m, n 0 a x a x a x b 2n n 2 21 1 22 2 s.t . am1 x1 am 2 x2 amn xn bm 矩阵表示 x1 0, x2 0, , xn 0 min s = cx
x1
因此，最优解有无穷多个。
例2.3、若目标函数为 min s = 2x1+2x2
约束条件为
x1 x2 1 s.t . x1 2 x2 0 x1 0, x2 0