当前位置：文档之家 › 运筹学第一章

运筹学第一章

  • 格式：ppt
  • 大小：2.66 MB
  • 文档页数：164

下载文档原格式

  / 164

合集下载

运 筹 学 课 件

运 筹 学 课 件

12/3 4
z
1 2
x4
x5 42
x3
2 3
x4
1 3
x5
4
新典式
主元化 为1，主 元所在
x2
1 2
x4
6
列的其 余元素
x1
2 3
x4
1 3
x5
4
化为0
观察最后一个典式，所有检验数均为非负， 故其对应的基本可行解为最优解，即
X * 4,6,6,0,0T z* 42
去掉引入变量，得原问题的最优解为：
运筹学课件
目录
运筹学概论 第一章 线性规划基础 第二章 单纯形法 第三章 LP对偶理论 第四章 灵敏度分析 第五章 运输问题 第六章 整数规划 第七章 动态规划 第八章 网络分析
第二章 单纯形法
(SM-Simplex Method)
1947年，美国运筹学家Dantzig提出，原理是 代数迭代。
单纯形法中的单纯形的这个术语，与该方法毫 无关系，它源于求解方法的早期阶段所研究的一 个特殊问题，并延用下来。
CB B1b B1b
z
CB B1N CN X N X B B1NX N
CB B1b B1b
上述方程组的矩阵形式为
10
0 I
CB
B1N B1N
CN
z XB XN
CB B1b B1b
上式的系数增广阵称为对应于基B的单纯形表：
T(B)
CB B1b B1b
0 I
CB
B1N B1N
CN
形式的LP问题，必须解决三个问题： ⑴初始基本可行解的确定； ⑵解的最优性检验； ⑶基本可行解的转移规则。 这里先放一下⑴，研究⑵和⑶，为此，

《运筹学》课件 第一章 线性规划

《运筹学》课件 第一章 线性规划

10
解：令
xi=
1， Si被选中
min z= ci xi i 1 10
0， Si没被选中
xi 5
i 1
x1 x8 1 x7 x8 1
称为技术系数
b= (b1,b2, …, bm) 称为资源系数
2、非标准型
标准型
（1）Min Z = CX
Max Z' = -CX
（2）约束条件
• “≤”型约束，加松弛变量；
松弛变量
例如： 9 x1 +4x2≤360
9 x1 +4x2+ x3=360
• “≥”型约束，减松弛变量；
例、将如下问题化为标准型
数据模型与决策 (运筹学）
课程教材：
吴育华,杜纲. 《管理科学基础》，天津大学出版社。
绪论
一、运筹学的产生与发展
运筹学（Operational Research) 直译为“运作研究”。
• 产生于二战时期 • 60年代，在工业、农业、社会等各领域得到广泛应用 • 在我国，50年代中期由钱学森等引入
Min z x1 2x2 3x3
x1 x2 x3 7
s.t
.
x1 x2 x3 3x1 x2 2
x3
2
5
x1, x2 , x3 0
解：令 Min z Max z' (z' z) ，第一个约束加松弛变量x5，
第二个约束减松弛变量x6，得标准型：
Max z' x1 2x2 +3x3
x1 x2 x3 x4 7
s.t .
x1 x2 3x1
x3 x2
x5 2 2x3 5
x1 , , x5 0

运筹学第1章-线性规划

运筹学第1章-线性规划
凸集的数学定义:设K为n维欧氏空间的一个点集，若K中任意两个 点X1和X2连线上的所有点都属于K，即“X =αX1+(1-α) X2 ∈ K(0≤a ≤ 1)”，则称K为凸集。设X(x1，x2，…，xn)，X1(u1， u2，...，un)，X2(v1，v2，…，vn)，如图1一5所示，“X =αX1+(1α) X2 ∈ K(0≤a ≤ 1)”的证明思路如下:
下一页 返回
图解法步骤：
（1）建立坐标系； （2）将约束条件在图上表示； （3）确立满足约束条件的解的范围； （4）绘制出目标函数的图形 （5）确定最优解
用图解法求解下列线性规划问题
max z 2x1 3x2
4x1 0x2 16
s.t
10xx11
4x2 2x2
12 8
x1, x2 0
1. 1.1问题举例
(1)生产计划问题。 生产计划问题是典型的已知资源求利润最大化的问题，对于此类
问题通常有三个假设:①在某一计划期内对生产做出的安排;②生产 过程的损失忽略不计;③市场需求无限制，即假设生产的产品全部 卖出。
下一页 返回
1.一般线性规划问题的数学模型
例1 用一块连长为a的正方形铁皮做一个容 器，应如何裁剪，使做成的窗口的容积为最 大？
解：设 x1, x2分别表示从A,B两处采购的原油量（单
位：吨），则所有的采购方案的最优方案为：
min z 200x1 290x2
0.15x1 0.50x2 150000
s.t
0.20x1 0.50x1
0.30x2 0.15x2
120000 120000
x1 0, x2 0
1. 1线性规划问题与模型
也可以写成模型(1-6)和模型(1-7)的形式，其中模型(1-7)较为常用。

运筹学基础及应用课后习题答案(第一二章习题解答)

运筹学基础及应用课后习题答案(第一二章习题解答)

运筹学基础及应用课后习题答案(第一二章习题解答)第一章：线性规划一、选择题1. 线性规划问题中，目标函数可以是（）A. 最大化B. 最小化C. A和B都对D. A和B都不对答案：C解析：线性规划问题中，目标函数可以是最大化也可以是最小化，关键在于问题的实际背景。

2. 在线性规划问题中，约束条件通常表示为（）A. 等式B. 不等式C. A和B都对D. A和B都不对答案：C解析：线性规划问题中的约束条件通常包括等式和不等式两种形式。

二、填空题1. 线性规划问题的基本假设是______。

答案：线性性2. 线性规划问题中，若决策变量个数和约束条件个数相等，则该问题称为______。

答案：标准型线性规划问题三、计算题1. 求解以下线性规划问题：Maximize Z = 2x + 3ySubject to:x + 2y ≤ 83x + 4y ≤ 12x, y ≥ 0答案：最优解为 x = 4, y = 2，最大值为 Z = 14。

解析：画出约束条件的图形，找到可行域，再求目标函数的最大值。

具体步骤如下：1) 将约束条件化为等式，画出直线；2) 找到可行域的顶点；3) 将顶点代入目标函数，求解最大值。

第二章：非线性规划一、选择题1. 以下哪个方法适用于求解非线性规划问题（）A. 单纯形法B. 拉格朗日乘数法C. 柯西-拉格朗日乘数法D. A和B都对答案：B解析：非线性规划问题通常采用拉格朗日乘数法求解，单纯形法适用于线性规划问题。

2. 非线性规划问题中，以下哪个条件不是K-T条件的必要条件（）A. 梯度条件B. 正则性条件C. 互补松弛条件D. 目标函数为凸函数答案：D解析：K-T条件包括梯度条件、正则性条件和互补松弛条件，与目标函数是否为凸函数无关。

二、填空题1. 非线性规划问题中，若目标函数和约束条件都是凸函数，则该问题称为______。

答案：凸非线性规划问题2. 非线性规划问题中，K-T条件是求解______的必要条件。

运筹学课程讲义

运筹学课程讲义

运筹学课程讲义第一部分线性规划第一章线性规划的基本性质1.1 线性规划的数学模型一、线性规划问题的特点胜利家具厂生产桌子和椅子两种家具。

桌子售价50 元/个，椅子售价30 元/个。

生产桌子和椅子需木工和油漆工两种工种。

生产一个桌子需要木工4 小时，油漆工2小时。

生产一个椅子需要木工3 小时，油漆工1 小时。

该厂每月可用木工工时为120 小时，油漆工工时为50 小时。

问该厂如何组织生产才能使每月的销售收入最大？max z 50x1 30x24x1 3x2 1202x1 x2 50x1,x2 0 例：某工厂生产某一种型号的机床。

每台机床上需要 2.9m、2.1m、1.5m的轴，分别为1根、2根和1根。

这些轴需用同一种圆钢制作，圆钢的长度为74m。

如果要生产100台机床，问应如何安排下料，才能用料最省？二、数学模型的标准型1. 繁写形式2. 缩写形式3. 向量形式4. 矩阵形式若原模型中变量 x j 有上下界，如何化为非负变量？三、 任一模型如何化为标准型？1. 若原模型要求目标函数实现最大化，如何将其化为最小化问题？2. 若原模型中约束条件为不等式，如何化为等式？3. 若原模型中变量 x k 是自由变量，如何化为非负变量？1. 2 图解法该法简单直观，平面作图适于求解二维问题。

使用该法求解线性规划问题时，不必把原模型化为标准型。

一、 图解法步骤1. 由全部约束条件作图求出可行域2. 作出一条目标函数的等值线3. 平移目标函数等值线，作图求解最优点，再算出最优值 max z 5x 1 6x 2 7x 3x 1 5x 23x 3 15 5x 1 6x 210x 3 20 x 1 x 2 x 3 5x 1 0,x 2 0,x 3无约束令 x 1' x 1,x 3 x 3' x 3'',x 3' ,x 3'' 0, Z 1Z ' 1 1 min z ' 5x 1' 6x 2 7x 3' 7x 3'' 0x 5 Mx 6 1 x 1' 5x 2 1 11 3x 3' 3x 3'' x 4 x 6 15 1 5x 1' 6x 2 10x 3' 10x 3'' x 5 20 1 x ' x 1 ' II '' 54.Mx 7 x 1, x 2 , x 3, x 3, x 4 , x 5 ,x 6, x 7 0从图解法看线性规划问题解的几种情况1. 有唯一最优解2. 有无穷多组最优解3. 无可行解4. 无有限最优解（无界解）min z 6x1 4x?2x〔X2 13 最优解（1,0），最优值33x14x2 22x1, x20直观结论：1）线性规划问题的可行域为凸集，特殊情况下为无界域（但有有限个顶点）或空集；2）线性规划问题若有最优解，一定可以在其可行域的顶点上得到。

运筹学

运筹学

11
目录
（三）LP问题的标准型
1.为了讨论LP问题解的概念和解的性质以及对LP问题求 解方便，必须把LP问题的一般形式化为统一的标准型：
minz=c1x1+c2x2+…+cnxn
j =1 a11 x2 + a12 x2 + + a1n xn = b1 a x + a x + + a x = b n 2n n 2 21 2 22 2 简 aij x j = bi (i = 1,2, L , m) s.t 化 j =1 x j ≥ 0( j = 1,2,L , n) am1 x2 + am 2 x2 + + amn xn = bm x1 , x2 , , xn ≥ 0
A ( 0 ,3 ) 10 15 , ) B( 7 7 5 C ( ,0 ) 2
max
Z = 5 x1 + 4 x 2
3 x 1 + 5 x 2 ≤ 15 2 x1 + x 2 ≤ 5 2 x 1 + 2 x 2 ≤ 11 x1 , x 2 ≥ 0
Z=
110 7
2x1+2x2=11
C 2.5
5x1+4x2=0 红线为目标函数的等值线 等值线. 红线为目标函数的等值线
j i= 1
j
(1.4) (1.5) (1.6)
ì n a ij x j = s .t . j = 1 í 1.从代数的角度看： x j 0 1.
b
i
可行解（Feasible Solution)： 满足约束条件(1.5)和(1.6)的 解X=(x1,x2,…,xn)T称为可行解。所有可行解构成可行解集， 即可行域。 最优解(Optimal Solution): 而使目标函数达到最大值的可 行解称为最优解，对应的目标函数值称为最优值。 求解LP问题就是求其最优解和最优值，但从代数的角 17 度去求是困难的。 目录

运筹学第1章：线性规划问题及单纯型解法


原料甲 原料乙 最低含量 VA 0.5 0.5 2 VB1 1.0 0.3 3 VB2 0.2 0.6 1.2 VD 0.5 0.2 2 0.3 0.5 单价
分别代表每粒胶丸中甲, 设 x1, x2分别代表每粒胶丸中甲, 乙两种原料的用量
5
例3,合理下料问题 , 分别代表采用切割方案1~8的套数, 的套数, 设 xj 分别代表采用切割方案 的套数
19
( f(x
)= 3
6
1.2.2 单纯型法的基本思路
确定初试基础可行解
检查是否为 最优解? 最优解?
是
求最优解的目标函数值
否 确定改善方向
求新的基础可行解
20
1.2.3 单纯型表及其格式
IV CB III XB II x1 b c1 a11 a21 c1′′= cn+1 xn+1 b1 c2′′= cn+2 xn+2 b2 x2 … xn c2 … cn a12 … a1n a22 … a2n I xn+1 cn+1 1 0 0 zn+1 xn+2 cn+2 0 1 0 zn+2 … … … … … … xn+m cn+m 0 0 1 zn+m
OBJ : max f ( x) = 6x1 + 4x2 2x1 + x2 ≤ 10 铜资源约束 x1 + x2 ≤ 8 铅资源约束 s.t. x2 ≤ 7 产量约束 x1, x2 ≥ 0 产量不允许为负值 最优解: x1 = 2, x2 = 6, max f ( x) = 36.
4
例2,配料问题(min, ≥) ,配料问题(
2 max 1 O 1 2 3 4 D 5 6 7 H 8

运筹学 第一章 线性规划 清华

x2 2 1 = x1 + z 3 3
① ② ③
x2
②
Q3 Q2
Q4
③
3
①
o
4 Q1
x1
*
6
首先取z = 0，然后，使z逐 渐增大，直至找到最优解所对 应的点。
x2
②
Q3
Q4
③
Q2(4,2)
3
①
*
4 Q1
x1
可见，在Q2点z取到最大值。 因此， Q2点所对应的解为最优解。 Q2点坐标为(4，2)。 即: x1 = 4，x2 = 2
5
1.2 图解法 eg. eg. [eg.3]用图解法求eg.1。 max z = 2x1 + 3x2 1x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12 x1 ，x2 ≥ 0 解： (1)建立x1 - x2坐标； x (2)约束条件的几何表示； (3)目标函数的几何表示； z = 2x1 + 3x2
15
1.4 线性规划解的概念 设线性规划为 max z = CX ① AX = b ② X≥0 ③ 矩阵, (A为行满秩矩阵） A为m × n矩阵, n > m, Rank A = m (A为行满秩矩阵） 为行满秩矩阵 1、可行解：满足条件②、③的X； 可行解：满足条件② 2、最优解：满足条件①的可行解； 最优解：满足条件①的可行解； 条件 子矩阵， 则称B 3、基：取B为A中的m × m子矩阵，Rank B = m，则称B为线性 中的m 规划问题的一个基。 规划问题的一个基。 取B = (P1,P2,,Pm) ,P Pj = (a1j,a2j,,amj)T ,a 则称x1,x2,,xm为基变量，其它为非基变量。 则称x ,x 为基变量，其它为非基变量。

运筹学第1章

（第三版）《运筹学》教材编写组编清华大学出版社运筹学第1章线性规划与单纯形法第1节线性规划问题及其数学模型二.线性规划与目标规划第1章线性规划与单纯形法第2章对偶理论与灵敏度分析第3章运输问题第4章目标规划第1章线性规划与单纯形法第1节线性规划问题及其数学模型第2节线性规划问题的几何意义第3节单纯形法第4节单纯形法的计算步骤第5节单纯形法的进一步讨论第6节应用举例第1节线性规划问题及其数学模型•1.1 问题的提出•1.2 图解法•1.3 线性规划问题的标准形式•1.4 线性规划问题的解的概念第1节线性规划问题及其数学模型线性规划是运筹学的一个重要分支。

线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。

特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。

从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。

它已是现代科学管理的重要手段之一。

解线性规划问题的方法有多种，以下仅介绍单纯形法。

1.1 问题的提出从一个简化的生产计划安排问题开始例1某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。

资源产品ⅠⅡ拥有量设备 1 2 8台时原材料A40 16kg原材料B0 4 12kg续例1该工厂•每生产一件产品Ⅰ可获利2元，•每生产一件产品Ⅱ可获利3元，•问应如何安排计划使该工厂获利最多?如何用数学关系式描述这问题，必须考虑称它们为决策变量。

产品的数量，分别表示计划生产设II I,,21x x ∙12416482212121≤≤≤+∙x ;x ;x x ,x ,x 这是约束条件。

即有量的限制的数量多少，受资源拥生产021≥∙x ,x ,即生产的产品不能是负值这是目标。

最大如何安排生产，使利润,∙数学模型⎪⎪⎩⎪⎪⎨⎧≥≤≤≤++=0124164823221212121x ,x x x x x :x x z max 约束条件目标函数例2. 简化的环境保护问题靠近某河流有两个化工厂(见图1-1)，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。

运筹学教学课件(全)


实用举例
某公司通过市场调研，决定生产高中档新型拉杆箱。 某分销商决定买进该公司3个月内的全部产品。拉杆箱生 产需经过原材料剪裁、缝合、定型、检验和包装4过程。
通过分析生产过程，得出：生产中档拉杆箱需要用 7/10小时剪裁、5/10小时缝合、1小时定型、1/10小时检 验包装；生产高档拉杆箱则需用1小时剪裁、5/6小时缝合、 2/3小时定型、1/4小时检验包装。由于公司生产能力有限， 3月内各部的最大生产时间为剪裁部630小时、缝合部600 小时、定型部708小时、检验包装部135小时。
D {x | Ax b, x (x1,, xi ,, xn ) 0}
是凸集（凸多面体）。
引理2.1：线性规划的可行解 x (x1 ,, xn )T 为基本可行解的 充分必要条件是x的正分量所对应的系数列向量是线性无关的， 即每个正分量都是一个基变量。
定理2.2：线性规划问题的基本可行解x对应于可行域的顶点
通过分析生产过程，得出：生产中档拉杆箱需要用
7/10小时可剪裁以、通5/1过0小线时性缝合规、划1小求时定解型！、1/10小时
检验包装；生产高档拉杆箱则需用1小时剪裁、5/6小时 缝合、2/3小时定型、1/4小时检验包装。由于公司生产 能力有限，3月内各部的最大生产时间为剪裁部630小时、 缝合部600小时、定型部708小时、检验包装部135小时。
x2
L1：x1=6 L3：2x1+3x2=18
B 可行域
L2：x2=4 最优解
x1
4x1+3x2
解的特殊情况——解的特殊情况——无界解
线性规划的基本性质
若线性规划有最 优解，则最优解必在可 行域的顶点上达到。
X
可行域内部的点 • 可行解? 是 • 最优解? 不
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2
②全体可行解-可行域 ③可行域没有和目标函数发生关系
f
1
x1 2 x2 5
1 2 3 4 5 6
x1
O
x1 2 x2 0
目标函数等于0， 该线为等值线
目标函数等于-5， 等值线互相平行
特点：最优解在 可行域顶点上出 现。所以求解注 意力转移到在顶 点上寻找。 如果求极大化， 最优解如何取？
指明求解方向：搜索最优解，可以 直接在顶点上搜索，大大减少了搜 索范围和工作量。
总结前面研究思路
x2
6
2、将线形规划标准化（LP）后， 求出可行域顶点坐标，观察顶点坐 标特征：n个变量中含有n-m个0
x1 x2 3
5
4
2 x1 3x2 6
3
3、于是提醒我们将LP的n个决策 变量中n-m个取0。通过m个线形 约束方程组可能求得于是Cnm组解。 称为LP的基本解。
x1 2 x2 5
1 2 3 4 5 6
x1
O
x1 2 x2 0
• 线性规划几何特征给我们的启示：
1、图解法不是算法，目的是给算法的设计 找到方向 2、线性规划如果存在最优解，一定有一个 最优解在 K 的顶点上实现。所以如果以 后设计算法要搜索最优解，不需要在可行 域内部搜索，可以直接在顶点上搜索，大 大减少了搜索范围和工作量。
m
IB
无序
n m 非基本变量
I D , j
j ID , x j 0
基本解
X Bi bi
0, i 1m
特别的，当
bi 0, i 1m
，n个坐标结合在一起组成基本可行解。
对应LP几何特征中K的顶点。
矩阵B是基本变量在系数矩阵A中对应的系数列向量。
举例单纯形法转基
导 论
2、研究特点 建模是基础，求解是核心， 分析是关键，应用是出路 3、研究步骤 ① 系统分析和问题描述 ② 建立模型 ③ 问题的求解和解的检验 ④ 系统实施和最优控制

运筹学的学科体系
1. 规划论
• • 线性规划、非线性规划、整数规划、分数规划、参数规划、 目标规划、动态规划等
2. 图论与网络
第一章 线性规划
1.1线性规划模型
书上第1页
决策变量含义必须写完整， 下标意义交待清晰
约束条件和目标函 数中自变量都是一 次幂，线性规划
本课程中，一维变量下标用 j 表示， 二维变量下标用 i, j 表示
;
变量非负，考试容易忘记
1.1线性规划模型
• 线性规划
P3页
1.2标准型线性规划
问
x3 ?
x2 ?
通过消元法进行等价变换
• 如何引入数学符号表达？
=3 =4
=3 =2
I是变量下标组成的集合
I 1,, j , n
m
nm
I B B1,Bi ,Bm I D , j 基本变量讲次序，Bi 下标表示第几行， 非基本变量按原
对应值为决策变量下标
• 求解数学模型的算法都是为标准化模型设计的。 为计算机编程方便。
min f c j x j
j 1 n
目标函数系数 cj
s.t.
a x
j 1 ij
n
j
bi ;
i 1, , m
i 为第几个约束条件 bi 为资源
x j 0;
j 1, , n
1.2标准型线性规划
各种形式线性规划模型转化成标准型（LP）的方法
请写出
I是变量下标组成的集合 基本变量
I 1,, j , n
m
n m 非基本变量
I D , j
j ID , x j 0
I B {B1,, Bi , Bm}
若唯一求得
xBi bi bi 0, i 1m
bi 0, i 1m
两边n个坐标结合在一起组成基本解
沈括运粮——决策论
北宋沈括在《梦溪笔谈》中著有多个运筹学案例。他 在指挥作战实践中指出因粮于敌的决策，并作出令人信服 的数据论证：依靠自带粮食作远行征战是不可能的。 每个民夫可以背六斗米，士兵自己可以带五天的干粮， 一个民夫供应一个士兵，一次可以维持十八天。如果要计 回程的话，只能前进九天的路程。两个民夫供应一个士兵 的话，一次可以维持二十六天。如果要计回程的话，只能 前进十三天的路程。三个民夫供应一个士兵，一次可以维 持三十一天。如果要计回程的话，只可以前进十六天的路 程。三个民夫供应一个士兵，已经到了极限了。 他得到的结论是：一支汉、唐的军队能以平均每天40 公里的速度进退，在30万民夫的供应下，7万作战士兵 （另3万负责辎重）的活动半径只有640公里。该结论为军 事统帅的后勤指挥提供了重要战略决策依据。
约 6 学时 约 4 学时 约 2 学时 约 6 学时 约 6 学时 约 4 学时 约 4 学时 约 2 学时 34学时
运筹学发展史 运筹学 Operational Research
运筹帷幄，决胜千里
史记《张良传》
田忌赛马——博弈论
齐将田忌与齐王赛马，孙膑献策： “以下马对齐王上马，以上马对齐王中马， 以中马对齐王下马”。结果田忌以一负两 胜而获胜。 他的基本思想是不强求一局的得失， 而争取全盘的胜利。
运
筹
学
学习目的与要求
1 掌握运筹学的各主要分支的基本理论。
2 运用运筹学的基本方法和思想建立数学模型， 锻炼将管理实践问题数学化的能力。 3 运筹学是交通运输工程学科的必修课，是管理 数学和系统工程的理论基础。
4 运筹学是同学数学建模、从事本专业科学研究 的基础工具。
导 论
运筹学的特点 1. 运筹学已被广泛应用于工商企业、军事部门、民政事业 等研究组织内的统筹协调问题，故其应用不受行业、部 门之限制； 2. 运筹学既对各种经营进行创造性的科学研究，又涉及到 组织的实际管理问题，它具有很强的实践性，最终应能 向决策者提供建设性意见，并应收到实效； 3. 它以整体最优为目标，从系统的观点出发，力图以整个 系统最佳的方式来解决该系统各部门之间的利害冲突。 对所研究的问题求出最优解，寻求最佳的行动方案，所 以它也可看成是一门优化技术，提供的是解决各类问题 的优化方法。
P10页倒数第三段 结论
n 5 n 5
— —
m 3 m 3
=
2
下一节讲如何用代数的方法求顶点坐标。
标准型线形规划矩阵表示
下标 j 的含义，资源b的符号，m和n的含义
aij , c j
标准型线形规划矩阵表示
C,b,X为列向量，0理解为列向量 列向量×行向量=？ 行向量×列向量=？
标准型线形规划矩阵表示
基本
变量
基本 变量 通过消元法进行等价变换，转化成 每一个方程只含一个基本变量，且系数为1；目标函数方程中基本变量系数为0 的形式
典型方程组
• 为了方便的求得基本可行解
典型方程组
xBi yij x j bi
jI D
w rj x j f 0
jI D
典型方程组的特征
1.2线性规划几何特征
• 讨论：目标函数解的情况
1.2线性规划几何特征
• 讨论：目标函数解的情况
虽然最优解不唯一，但一定有一个最优解在顶点上实现。
1.2线性规划几何特征
• 讨论：目标函数解的情况
最优解无下界， f

前提是可行域不为空 且无界。
如果可行域有界就一 定存在最优解。
1.2线性规划几何特征
顺序排下
bi
0, i 1m
j ID , x j 0
两边n个坐标结合在一起组成基本解
特别的，当
bi 0, i 1m
，n个坐标结合在一起组成基本可行解。
对应LP几何特征中K的顶点。
请问上面的单纯形表基本可行解是多少？
B是基本变量在原系 数矩阵A中对应的系 数列向量
P11-12页 定理1
3. 存储论
4. 排队论 5. 决策论 6. 对策论 7. 系统仿真
课程内容及学时安排
第一章 线性规划 第二章 线性规划的对偶理论与灵敏度分析 第三章 运输问题 第五章 整数规划 第六章 网络规划 第七章 排队论 习题课 期中安排一次测验 合计
*目标规划待定
其他章节在研究生阶段讲授，同样使用本教材。
b 当 x j 0, X 0
0
目标函数值为
f X
0
f
1.2标准型线性规划
注意替代掉的变量下标不体现
1.2线性规划几何特征
算法产生的本源。先从最简单的两个变量线性规划分析。
图解法（几何）不是算法，目的是引出代数算法。 P7页
x2
6
5
x1 x2 3
4
2 x1 3x2 6
3
x1 x2 5
①满足全部约束条件的点-可行解
特别的，当 ，n个坐标结合在一起组成基本可行解。
对应LP几何特征中K的顶点。
典型方程组和对应的单纯形表
典型方程组和单纯形表
问 x3
?
x4 ?
上表称为单纯形表(TP)，特征是：每一个方程只含一个基本变量，且系数为1 目标函数方程中基本变量系数为 0
基本 变量
基本 变量
7 1 x1 0 x2 0 x3 x4 w 2 4 4
x1 2 x2 5
1 2 3 4 5 6
x1
2
f
1
O
x1 2 x2 0
4、基本解中符合变量非负条件的 解称为基本可行解。基本可行解对 应可行域的顶点坐标。
几何特征→基本解的代数结构
I是变量下标组成的集合 基本变量 有前后次序 若唯一求得
I 1,, j , n