当前位置：文档之家 › 线性规划01可行区域与基本可行解

线性规划01可行区域与基本可行解

  • 格式：pptx
  • 大小：885.66 KB
  • 文档页数：34

下载文档原格式

  / 34

合集下载

线性规划

线性规划

• 4.2 两阶段法
• 两阶段法是处理人工变量的另一种方法。其具体做 法是在原约束条件中增加人工变量，构造一个新的 目标函数，其中人工变量的系数为-1，其余变量的 系数为0，这样就产生了如下的最优解有三种情形。 （1）这说明在辅助问题的最优解中，还有人工变量是基变量， 且取值不为0，此时原问题无可行解。 （2）且最优解中人工变量均为非基变量，则把它们划去后就得 到了原问题的一个基本可行解。 （3）但最优解中还有人工变量是基变量，其取值为0。这时， 只要选某个不是人工变量的非基变量进基，把在基中的人工 变量替换出来，则情形同（2）。 第二阶段：对于第一阶段的后两种情形，在第一阶段的最优单 纯形表中划去人工变量所在的列，并把检验数行换成原问题 目标函数（消去基变量以后）的系数，从而得到原问题的初 始单纯形表，再继续迭代求解。
2014-6-19 3
例2（运输问题）
• 设有某种物资要从A1，A2，A3三个仓库运往四个 销售点B1，B2，B3，B4。各发点（仓库）的发货 量、各收点（销售点）的收货量以及 到 的单位运 费如表1-2。问如何组织运输才能使总运费最少？
例3（配料问题）
• 在现代化的大型畜牧业中，经常使用工业生产的饲料。 设某种饲料由四种原料B1，B2，B3 ，B4混合而成，要 求它含有三种成份（如维生素、抗菌素等）A1，A2， A3的數量分別不少于25、36、40个单位（这些单位可 以互不相同），各种原料的每百公斤中含三种成份的数 量及各种原料的单价如表1-3.
1.2 线性规划的数学模型
一、一般形式 上述各例具有下列共同特征： 1．存在一组变量 ，称为决策变量，表示某一方案。通 常要求这些变量的取值是非负的。 2．存在若干个约束条件，可以用一组线性等式或线性 不等式来描述。 3．存在一个线性目标函数，按实际问题求最大值或最 小值。

第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。若一个基解的基变量中有取 零值的，则此基解称为退化的，否则称为非退化的 。

川大运筹学资料及试题答案

川大运筹学资料及试题答案
即
x j ay j (1 a)z j (0 a 1, j 1,, n) 因为a>0,1-a>0，故当 x j 0时，必有y j＝z j ＝0
因为 所以
n
r
Pj x j Pj x j b
j1
j1
n
r
Pj y j Pj y j b
j1
ai1 x1 ai 2 x2 ain xn si bi , si 0
或
ai1 x1 ai 2 x2 ain xn bi
松弛变量
ai1 x1 ai 2 x2 ain xn si bi , si 0
剩余变量
几个 概 念
可行解（或可行点）：满足所有约束条件的向量 x ( x1 , x2 , xn ) 可行集（或可行域）：所有的可行解的全体
定理 2 可行解 x 是基本可行解的充要条件是它的正分量 所对应的矩阵 A 中列向量线性无关。
定理 3 x 是基本可行解的充要条件是 x 是可行域 D 的顶 点。
定理 4 一个标准的 LP 问题如果有有限的最优值，则一 定存在一个基本可行解是最优解。
定理2
证明：由基可行解的定义知，必要性显然成立。 充分性：若向量 p1, p2 , pk 线性独立，则必有 k m 当 k m 时，它们恰好构成一个基，从而为相应的 基可行解；当 k m 时，则一定能从剩余的列向量 中取出m-k个与 p1, p2, pk 构成最大的线性独立向量
组 其对应的解恰为x，所以，x是基可行解。
定理3
证明 (1) x不是基可行解，则x不是可行域的顶点。
不失一般性，假设x的前m个分量为正，则有
m
Pi xi b

线性规划问题的基本解

线性规划问题的基本解

am1
x1
am2 x2
L
amn xn
bm
x1 0, x2 0,L , xn 0
1.2 1.3
满足约束条件的X称为线性规划问题的可行解;
X x1, x2, , xn T
所有可行解的集合称为可行域 (feasible region),
使目标函数(1.1)达到最大值的可行解称为最优解(an optimal solution)。
A.基本可行解 B.非基本解
C.非可行解
D.最优解
4. X是线性规划的基本可行解，则有（ A. X中的基变量非零，非基变量为零 B. X不一定满足约束条件 C. X中的基变量非负，非基变量为零 D. X是最优解
）。
，P4
1
，P5
0
0
2
0
0
1
分别是变量 x1, x2 , x3, x4 , x5 的系数向量。
max z 3x1 5x2
3x1 2x2 x3
18
3 2 1 0 0
x1
x4 4
A 1 0 0 1 0
2x2
x5 12
0 2 0 0 1
x1, x2 , x3, x4 , x5 0
XB x j1 , x j2 ,L , x jm 表示基变量向量，
X N 表示非基变量向量。
现令所有的非基变量都等于0，即
XN 0
则约束方程(1.2)可化为：
Pj1 x j1 Pj 2 x j 2 L Pjm x jm b
BXB b
1.4
它是一个m个变量m个方程组成的线性方程组，B又是可逆
在上例1中，
对应于 B1 的基解为 X1 0, 0,18, 4,12T

线性规划的四个基本原理

线性规划的四个基本原理

线性规划的四个基本原理线性规划是一种常见的数学优化方法，它用于在一组限制条件下寻找最优解。

线性规划的基本原理有四个，分别是目标函数、约束条件、可行域和可行解。

目标函数是线性规划的第一个基本原理。

目标函数是需要最大化或最小化的线性方程，通常表示为z = c1x1 + c2x2 + ... + cnxn，其中c1、c2、...、cn是待优化的系数，x1、x2、...、xn是决策变量。

目标函数的最大值或最小值是我们希望找到的最优解。

约束条件是线性规划的第二个基本原理。

约束条件是一组等式或不等式，用于限制决策变量的取值范围。

约束条件通常表示为a11x1 + a12x2 + ... + a1nxn ≤b1，a21x1 + a22x2 + ... + a2nxn ≤b2，...，am1x1 + am2x2 + ... + amnxn ≤bm，其中a11、a12、...、amn是系数，b1、b2、...、bm是常数。

这些约束条件定义了可行解的集合，即满足所有约束条件的决策变量取值的集合。

可行域是线性规划的第三个基本原理。

可行域是满足所有约束条件的决策变量取值的集合。

可行域通常是一个多维空间中的一个区域，其边界由约束条件定义。

可行域定义了决策变量的取值范围，并且在该范围内寻找最优解。

可行解是线性规划的第四个基本原理。

可行解是满足所有约束条件的决策变量取值。

可行解通常是可行域中的一个具体点，该点使目标函数达到最大值或最小值。

确定最优可行解是线性规划的关键目标。

线性规划的求解过程是通过求解目标函数在可行域上的最大值或最小值来找到最优解。

这个过程可以通过使用线性规划求解方法来实现，例如单纯形法、内点法等。

总结起来，线性规划的四个基本原理分别是目标函数、约束条件、可行域和可行解。

通过优化目标函数在可行域上的取值，寻找满足约束条件的最优解。

线性规划在数学建模、运筹学、经济学等领域有广泛的应用，可以帮助人们做出最优决策。

线性规划原理与解法

线性规划原理与解法

c1 b1 a1,m 1 xm 1 a1,m 2 xm 2 ... a1n xn
z c1b1 c2b ... cmbm
cm1 ci ai,m1
i 1
m
cm 1 c1a1, m 1 c2 a2, m 1 ... cm am , m 1 xm 1 c c a i i ,m 2 m 2

i 1

对增广矩阵 作初等行变换 将基变为单位阵
1 0 0
x2 0 ... 0 a1, m 1 ... a1n b : 1 1 ... 0 a2, m 1 ... a2 n b xm 2 ...... x : m 1 bm 0 ... 1 am, m 1 ... amn : x n
第一节 线性规划求解原理
5）若约束条件为“≥”，“≤”和“=”的混合性， 则综合应用以上方法，确定初始基。
max z 3 x1 4 x2 例： x1 2 x2 ≤8 4 x ≤16 1 s.t. 4 x2 ≤12 x1 , x2≥0 max z 3x1 4 x2 0 x3 0 x4 0 x5 =8 x1 2 x2 x3 4 x x4 =16 1 s.t. x5 12 4 x2 x1 , x2 , x3 , x4 , x5≥0
xi bi
j m 1
a x (i 1, 2,..., m)
ij j
n
x1 b1 a1,m1 xm1 a1,m2 xm2 ... a1n xn x2 b2 a2,m1 xm1 a2,m2 xm2 ... a2 n xn ...... xm bm am,m1 xm1 am,m 2 xm 2 ... amn xn

第1章 线性规划

第1章线性规划本章介绍了什么是线性规划，线性规划数学模型的概念及其建立数学模型方法；阐述了线性规划的图解法、解的概念及解的形式；详细介绍了普通单纯形法、人工变量单纯形法及单纯形法计算公式。

1．考核知识点（1） 基本概念：数学模型、决策变量、目标函数、约束条件、标准型、图解法、基矩阵、基变量、非基变量、可行解、基解、基可行解、最优解、基最优解、唯一解、多重解、无界解、无可行解、单纯形法、最小比值、入基变量、出基变量、解的判断、大M法、两阶段法、改进单纯形法。

（2） 建立简单的线性规划数学模型。

（3） 求解线性规划的图解法。

（4） 基、可行基及最优基的定义。

（5） 可行解、基本解、基可行解、最优解、基本最优解的定义及其相互关系。

（6） 有唯一解、有无穷多解、无界解、无可行解的判断。

（7） 求解线性规划的单纯形法。

（8） 求解线性规划的人工变量法。

（9） 单纯形法中的5个计算公式。

2．学习要求（1） 深刻领会线性规划的各种基与解的基本概念，它们之间的相互关系。

（2）掌握图解法的计算步骤，注意怎样将目标函数表达成一条直线，这条直线如何平移使得目标函数值上升或下降。

（3） 熟练掌握单纯形法计算的全过程，特别应注意如何列出单纯形表，如何由一个基可行解换到另一个基可行解，基可行解是最优解、无界解或多重解的判断准则。

（4） 理解在什么情况下加入人工变量，人工变量起何作用，用大M法计算时目标函数的变化，两阶段法计算时目标函数的构成，掌握这两种计算方法的全过程，在什么情形下线性规划无可行解。

（5） 理解用矩阵形式代替单纯形表，并用矩阵公式求解线性规划。

3．重点建立线性规划数学模型，有关线性规划解的概念、解的形式，单纯形法计算、大M法、两阶段法。

4．难点解析（1）建立线性规划数学模型建立数学模型是学习线性规划的第一步也是关键的一步。

建立正确的数学模型要掌握3个要素：研究的问题是求什么，即设置决策变量；问题要达到的目标是什么即建立目标函数，目标函数一定是决策变量的线性函数并且求最大值或求最小值；限制达到目标的条件是什么，即建立约束条件。

01线性规划

-1- 线性规划§1 线性规划在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。

此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。

自从1947年G . B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。

特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。

1.1 线性规划的实例与定义 例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。

生产甲机床需用B A 、机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用C B A 、、三种机器加工，加工时间为每台各一小时。

若每天可用于加工的机器时数分别为A 机器10小时、B 机器8小时和C 机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？上述问题的数学模型：设该厂生产1x 台甲机床和2x 乙机床时总利润最大，则21,x x 应满足（目标函数）2134max x x z += (1)s.t.（约束条件）⎪⎪⎩⎪⎪⎨⎧≥≤≤+≤+0,781022122121x x x x x x x （2）这里变量21,x x 称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式是问题的约束条件，记为s.t.(即subject to)。

由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。

总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。

在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往也是困难的一步，模型建立得是否恰当，直接影响到求解。

而选适当的决策变量，是我们建立有效模型的关键之一。

1.2 线性规划的Matlab 标准形式线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以是小于号也可以是大于号。

可行解`可行解集(可行域)


最优解x 最优解x(2)=(9,4,1,0,0) 最优值f(x 最优值f(x(2))=1 进行两次单纯形迭代
换基并求出新典式
确定离基变量：min{bi0/bir|bir>0}=bs0/bsr， xjs为离基变量，即用pr代替pjs得新基。 确定进基变量：把对应于正检验数的的非 基变量转变为基变量
例题
min f = x1 − 2 x2 + x4 s.t. x1 + 3x3 + 2 x5 = 12 x2 − 2 x3 + x4 = 2 x2 + x3 + x5 = 5 xi ≥ 0
i =1 j∈R i =1 m −1 −1
( 0)
m
= f
(0)
− ∑ λj xj
j∈R
min s.t.
f = cx = cB B b − (cB B N − cN ) xN xB + B NxN = B b x≥0
min f = f
(0)
−1
−1
−1
−1
− ∑λj xj
j∈R
s.t.x ji = x (0) − ∑ bij x j ji
这时约束等式Ax=b可表示为 BxB + NxN = b
即
xB = B-1b - B-1NxN
特别，当取xN = 0，这时有xB=B-1b=xB(0)。
x ji = x
(0) ji
− ∑ bij x j
j∈R
这时目标函数f=cx可表示为
f = cx = cB xB + cN xN = c B B b − ( cB B N − c N ) x N = ∑ c ji x ji − ∑ (∑ c ji bij − c j ) x j

1.2线性规划的解


. ..
x2 .3 .
. x1 2x2 2 . . . . .
0
x1
解： （1）在直角坐标系上画出可行域
x1 4
x1 2x2 8
（2）做目标函数的等值线 x1 2x2 2
(3)最优值z* 8
求交点：
x1 x2
2x2 3
8
x1 x1
2x2 4
8
(x1, x2 ) (2,3)
(x1, x2 ) (4,2)
max z 7x1 x2
x1 2x2 6
s.t
x1 x2 1 x1 2
x1 , x2 0
其标准型为
max z 7x1 x2
x1 2x2 x3 6
s.t
x1 x2 x4 1 x1 x5 2
x1, x2 , x3 , x4 , x5 0
1 2 1 0 0
系数矩阵A
2x1 x2 3
可行域为空集
无可行解
该问题无最优解
图解法的基本步骤：
1、在直角坐标系x1ox2上做出可行域S的图形
（一般是一个凸多边形）
2、令目标函数值取一个给定的常数k,
做等值线Z c1x1 c2 x2 k 3、对max 问题，令目标函数值k由小变大, 即让等值线向上平移，
若它与可行域S最后交于一个点（一般是S的一个顶点）， 则该点就是所求的最优点， 若与S的一条边界重合，此时边界线上的点均是最优点
退化基本可行解：基本可行解中，存在取0值的基变量
对应的基称为退化基
非退化基本可行解：基本可行解中，基变量的取值均>0
对应的基称为非退化基
线性规划问题
退化的线性规划问题：存在退化基 非退化的线性规划问：题 所有基均非退化
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
运输问题
一般形式 规范形式 标准形式 概念 形式转换
2020/5/24
Ludong University
3
生产计划问题
某工厂用三种原料生产三种产品，已知的条件如表 2.1.1所示，试制订总利润最大的生产计划
单位产品所需原 料数量（公斤）
原料P1
产品 Q1
2
产品 Q2
3
产品 Q3
原料可用量 （公斤/日）
2020/5/24
Ludong University
7
问题分析
可控因素：从仓库 Ai 运往 B j 的产品数量 设为
目标：总运费最小。费用函数
xij , i 1, 2, j 1, 2, 3, 4
24
cij xij
i1 j1
受控条件：从仓库运出总量不超过可用总量，运入零售点的数量不低于需求量。由于总供给量等于 总需求量，所以都是等号。即
D { x Ax b, x 0} 最优解：在可行域中目标函数值最大（或最小）的可行解称为最优解，最优解
的全体称为最优解集合 O {x D c x c y,y D }
最优值：最优解对应的目标函数值 v c x, x O
2020/5/24
Ludong University
13
模型转换
变量转换
不等式变等式
不等式变不等式
2020/5/24
Ludong University
15
约束转换2
等式变不等式 不等式变等式
ai1x1 ai2 x2 L ain xn bi
ai1x1 ai2 x2 L ain xn si bi , si 0 或 ai1x1 ai2 x2 L ain xn bi
松弛变量
ai1x1 ai2 x2 L ain xn si bi , si 0
不等式变不等式
2020/5/24
Ludong University
剩余变量
16
将LP转化为标准形式
例2.1.3
10
注释
x j , j 1, 2,L , n 为待定的决策变量； c (c1, c2 ,L , cn ) 为价值向量； c j , j 1, 2,L , n 为价值系数； b (b1, b2,L , bm ) 为右端向量； 矩阵
为系数矩阵。
a11 a12 a1n
A
a 21 am1
xi1 xi2 xi3 xi4 ai , i 1, 2
蕴含约束：数量非负
x1 j x2 j bj , j 1, 2, 3, 4 xij 0,i 1, 2, j 1, 2,3, 4
2020/5/24
Ludong University
8
模型
24
min
cij xij
i1 j 1
令自由变量 x j
x
j
x
j
，其中
x
j
,
x
j
为非负变量。
目标转换
求最大可以等价成求负的最小
maxc x min c x
约束转换 实例
2020/5/24
Ludong University
14
约束转换1
等式变不等式
ai1x1 ai2 x2 L ain xn bi
ai1x1 ai2 x2 L ain xn bi ai1x1 ai2 x2 L ain xn bi
0 1500
原料P2
0
2
4
800
原料P3
3
2
5 2000
单位产品的利润
3
5
4
（千元）
表2.1.1
2020/5/24
Ludong University
4
问题分析
可控因素：每天生产三种产品的数量，分别设为
x1 , x2 , x3 目标：每天的生产利润最大。利润函数是
3x1 5x2 4x3 受制条件：每天原料的需求量不超过可用量。
a 22 am2
a2n
a mn
2020/5/24
Ludong University
11
规范形式与标准形式
规范形式
标准形式
min c x
Ax b
s.t.
x
0
min c x Ax b
s.t.x 0
2020/5/24
Ludong University
12
概念
可行解（或可行点）：满足所有约束条件的向量 x (x1, x2 ,L , xn ) 可行集（或可行域）：所有的可行解的全体
线性规划
Linear Programming
Ludong University
线性规划
线性规划问题 可行区域与基本可行解 单纯形算法 初始可行解 对偶理论 灵敏度分析 计算软件 案例分析
2020/5/24
Ludong University
2
线性规划问题
线性规划实例 线性规划模型
生产计划问题s.t.ຫໍສະໝຸດ 32xx124x3 2x2
800 5x3
2000
x1, x2 , x3 0
2020/5/24
Ludong University
6
运输问题
一个制造厂要把若干单位的产品从两个仓库 Ai ,i 1, 2 ，发送到 零售点 Bj , j 1, 2,3, 4 ，仓库 Ai 能供应的产品数量为 ai ,i 1, 2 ，零 售点 B j 所需的产品的数量为 bj , j 1, 2,3, 4 。假设供给总量和需 求总量相等，且已知从仓库 Ai 运一个单位产品往 B j 的运价为 cij 。问应如何组织运输才能使总运费最 Ai 小？
s.t.
xi1 x1 j
xi2 xi3 x2 j bj ,
xi 4
ai ,
xij
0,
i 1, 2 j 1, 2,3, 4 i 1, 2, j 1, 2,3, 4
2020/5/24
Ludong University
9
一般形式
目标函数
min z c1x1 c2 x2 L cn xn
ai1x1 ai2 x2 L ain xn bi,i 1, 2,L , p
s.t.
ai1x1
x
j
ai2 x2 L 0, j 1, 2,L
ain xn ,q
bi ,i
p
1,L , m
非负变量
xj无限制, j 1, 2,L , q
自由变量
2020/5/24
约束条件
Ludong University
原料 P1 ：
2x1 3x2 1500
原料 P2 ：
2x2 4x3 800
原料 P3 ： 蕴含约束：产量为非负数
3x1 2x2 5x3 2000
x1 , x2 , x3 0
2020/5/24
Ludong University
5
模型
max 3x1 5x2 4x3
2x1 3x2 1500