单纯形法
学院：
专业：
姓名：
学号：
指导教师：
日期：年月日
目录
1 算法描述
1.1单纯形算法 (3)
2 单纯形算法的求解
2.1单纯形法的基本思路 (4)
2.2单纯形法的算法步骤 (4)
2.3单纯形算法求解线性规划的范例 (6)
3基于MATLAB的数学实验
3.1单纯形算法 (10)
3.2计算框图 .............................. (错误！未定义书签。）3.3计算程序 .............................. (错误！未定义书签。）3.4数值试验及结果分析. (13)
参考文献 (14)
1、单纯形法的描述
根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个或多个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。
最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在三种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。
单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。
用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有10^6个决策变量和10^4个约束条件的线性规划问题已能在计算机上解得。
2 单纯形算法求解
2.1单纯形法的基本思路
利用求线性规划问题基本可行解（极点）的方法求解较大规模的问题是不可行的。有选择地取基本可行解，即从可行域的一个极点出发，沿着可行域的边界移动到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。在线性规划的可行域中先找出一个可行解，检验它是否为最优解，如果是最优解，计算停止；如果不是最优解，那么可以判断线性规划无有限最优解，或者根据一定步骤得出使目标函数值接近最优值的另一个基本可行解。由于基本可行解的个数有限，所以总可以通过有限次迭代，得到线性规划的最优基本可行解或判定线性规划无有限最优解。 2.2单纯形法的基本步骤描述
第1步：求初始基可行解，列出初始单纯形表。
对非标准型的线性规划问题首先要化成标准形式。由于总可以设法使约束方程的系数矩阵中包含一个单位矩阵()12,,,m P P P ，
以此作为基求出问题的一个初始基可行解。
为检验一个基可行解是否最优，需要将其目标函数值与相邻基可行解的目标函数值进行比较。为了书写规范和便于计算，对单纯形法的计算设计了一种专门表格，称为单纯形表(见表1-1)。迭代计算中每找出一个新的基可行解时，就重画一张单纯形表。含初始基可行解的单纯形表称初始单纯形表，含最优解的单纯形表称最终单纯形表。
第2步：最优性检验。
表1-1单纯形表
c j
c 1 … c m … c j … c n C B
基
b
x 1
…
x m
…
x j
…
x n
c 1 c 2 … c m
x 1 x 2 … x m
b 1 b 2 … b m
1 0 0
… … … …
0 0 (1)
… … …
a 1j a 2j … a mj
… … … …
a 1n a 2n … a mn
c j -z j 0 … 0 …
1
m
j i ij i c c a =-∑
(1)
m
n i in
i c c a =-∑
如表中所有检验数c j -z j ≦0，且基变量中不含有人工变量时，表中的基可行解即为最优解，计算结束。当表中存在c j -z j >0时，如有P j ≦0，则问题为无界解，计算结束；否则转下一步。
第3步：从一个基可行解转换到相邻的目标函数值更大的基可行解，列出新的单纯形表。
1.确定换入基的变量。只要有检验数δj >0，对应的变量x j 就可作为进基的变量，当有一个以上检验数大于零时，一般从中找出最大一个δk ，其对应的变量x k 作为进基变量。
2.确定出基的变量。min |0i r
ik
ik rk
b b a a a θ???=>=?????
确定x r 是出基变量,a rk 为主元。 3.用进基变量x k 替换出基变量x r ，得到一个新的基()111,
,,,,
,r k r m P P P P P -+。
对应这个基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表(表1-2)。
(1) 把第r 行乘以rk
a 1
之后的结果填入新表的第r 行；对于r i ≠行，把第r 行乘以??
? ?
?-rk ik
a a 之后与原表中第
i 行；在B x 列中的r 行位置填入k x ，其余行不变；
在B c 列中用k c 代替r 行原来的值，其余的行与原表中相同。
(2) 然后用j x 的价值系数j c 减去B c 列的各元素与j x 列各对应元素的乘积，把计算结果填入j x 列的最后一行，得到检验数j δ，计算并填入Z '-的值（以零减去B c 列各元素与b 列各元素的乘积）[1]。
第4步：重复上述过程，就可以得到最优解或判断出无有限最优解。
表1-2初始单纯形表
c j c1…c r…c m…c j…c k…
C
B
基 b x1…x r…x m…x j…x k…
c1 …
c k …
c m x1
…
x k
…
x m
1
rk
r
rk
a
b b
b
-?
…
r
rk
b
a
…
mk
m r
rk
a
b b
a
-?
1
…
…
…
1k
rk
a
a
-
…
1
rk
a
…
mk
rk
a
a
-
…
…
…
1
…
11
rj
j k
rk
a
a a
b
-?
…
rj
rk
a
a
…
rj
mj mk
rk
a
a a
a
-?
…
…
1
…
c j- z j0 …
()
k k
rk
c z
a
-
-…0 …()()
rj
j j k k
rk
a
c z c z
a
---…0 …
2.3单纯形算法求解线性规划的范例
在实践中，根据实际问题的要求，常常可以建立线性规划问题的数学模型。下面这个范例，就是一个用单纯形算法求解的线性规划的范例。
美佳公司计划制造甲,乙两种家电产品。但因财力、物力等原因，资源有限，已知制造一个家电产品分别占用的设备A，B的台时、调试时间、调试工序及每天可用于这两种家电的能力、各售出一件的获利情况，如表1-3所示。问该公司应制造两种家电各多少件，使获取的利润为最大。
表1-3 产品有关数据表
项目甲乙每天可用能力设备A（h）0 5 15
设备B(h) 6 2 24
调试工序(h) 1 1 5
利润（元） 2 1
解：根据题意构建下列线性规划模型：
,,,,5
24261552Max 5432152
14
213
22
1≥=++=++=++=x x x x x x x x x x x x x s.t
x x Z 目标函数
约束条件
用单纯形法求解线性规划问题，标准化后得：
取初始基本可行解()I p p p x x x x x ======54354321,,,5,24,15,0（单位矩阵）。初始化单纯形表并计算的过程如表1-4所示。
在最优单纯形表中，非基变量54,x x 的检验数均为负数，于是得到最优解
T
x ?
?? ??=0,0,215,23,27*
，最优目标值
218*=Z 元（表中-17/2为-Z 的值）。 为了能够更清晰地看清单纯形算法的解题思路以及单纯形算法表格计算过程中表格内各量的关系，把例中的3次迭代计算过程重述如下：
第一次迭代：
取初始可行基()543,,p p p ，那么543,,x x x 为基变量，21,x x 为非基变量。将基变量和目标函数用非基变量表示：
第二次迭代：
当前的可行基()531,,p p p ，那么531,,x x x 为基变量，42,x x 为非基变量。将基变量和目标函数用非基变量表示：
2
152142
32
152********x x x x x x x x x
x Z --=--=-=+=0
,524261552Max 21212122
1>≤+≤+≤+=x x x x x x x s.t.
x x Z
4252
3421426
16415156
162431318x x x x x x x x x x Z +-
=-=--=-+= 第三次迭代：
当前的可行基()321,,p p p ，那么321,,x x x 为基变量，54,x x 为非基变量。将基变量和目标函数用非基变量表示：
5
4
35
4
25
4
154215452
1523
4123
2
1412
72141217x x x x x x x x x x x Z +-=
-+=
+-=
-
-
=
在目标函数542
1
41217x x Z --=
中，非基变量54,x x 的检验数不是正数，于是得
到最优解T
x ?
??
??=0,0,215,23,27*,最优目标值
218*=Z 。
表1-4 单纯形表表格计算过程 c B
x B
b`
2
1
θ
X 1
X 2 X 3 X 4 X 5 0 X 3 15 0 5 1 0 0 -- 0 X 4 24 [6] 2 0 1 0 4 0
X 5
5 1 1 0 0 1 5 -Z 0 2 1 0 0 0 0
X 3 15
5
1
3
2 X 1 4 1 2/6 0 1/6 0 37/
3 0
X 5
1 0 [4/6] 0 -1/6 1 4/3 -Z -8
0 1/3 0 -1/3 0 0 X 3 15/2 0 0 1 5/4 -15/2 -- 2 X 1 7/2 1 0 0 1/4 -1/2 -- 1
X 2
3/2 0 1 0 -1/4 3/2 4/3 -Z
-17/2
-1/4
-1/2
在最优单纯形表中，非基变量54,x x 的检验数均为负数，于是得到最优解
T
x ???
??=0,0,215,23,27*
，最优目标值218
*=Z 元（表中-17/2为-Z 的值）。
3、基于MATLAB 的数学软件实验
3.1算法
对于一般的标准形式线性规划问题(求极小问题),首先给
定一个初始基本可行解。设初始基为B,然后执行如下步骤：
(1).解B Bx b =,求得
1
B x B b -=，0,N B B x f c x ==令计算目标函数值 1(1,2,...,)i m B b i -=i 以b 记的第个分量
(2).计算单纯形乘子w
, B wB C =,得到1
B w
C B -=,对于非基变量，
计算判别数1i i i B i i z c c B p c σ-=-=-,令 max{
}k i i i R
z c σ∈=-,R 为非基变量集合
若判别数0k σ≤ ,则得到一个最优基本可行解，运算结束；否则，转到下一步
(3).解k k By p =,得到
1
k k y B p -=；若0k y ≤,即k y 的每个分量均非正数，则停止计算，问题不存在有限最优解，否则，进行步骤(4).
(4).确定下标r,使
{
}
:0
min ,0
t r
rk
tk
tk b b tk y y t y y >=>且r B x 为离基变量。k x 为进
基变量，用k p 替换r B p ，得到新的基矩阵B ，返回步骤（1）。
对于极大化问题，可以给出完全类似的步骤，只是确定进基变量的准则不同。对于极大化问题，应令
min{}k k j j z c z c -=-
是
否
是
否
初始可行解B
令1,0,B
N B B x B b b x f c x -====
计算单纯形乘子1
B w c B -=，计算判别数,i j j wp c j R σ=-∈（非基变量）
令max{,}k
j j R σσ=∈
0?k σ≤ 解方程k
k By p =，得到1k k y B p -=。
得到最优解
0?k y ≤
不存在有限最优解
确定下标r ，是
{
}:0
min ,0
t r rk
tk
tk b b tk y y t y y >=>且
k x 为进基变量，用
k p 替换r B p ，得到新的基矩阵B
开始
function [x,f]=zuiyouhua(A,b,c)
size(A)=[m,n];
i=n+1:n+m;%基变量集合,后面m个松弛变量为初始基变量;
N=1:n;%初始非基变量;
B=eye(m,m);
xb=b';
xn=zeros(m,1);
f1=0;
w=zeros(1,m);
z=-c;%初始判别数;
flag=1;
while(1)
[a,k]=max(z);%x(k)为进基变量;
if a<=0
flag=0;
break
else
y=inv(B)*A(:,k)
if y<=0
flag=0;
fprintf('不存在最优解')
break
end
t=find(y>0);
[a,r1]=min(b1(t)./y(t))
r=t(r1); %基变量中第r个变量为退基变量;
i(:,r)=k
B(:,r)=A(:,k);%换基，即将原基中第ｒ个变量换成第ｋ个变量;
cb=c(:,i);%新的价值系数; xb=inv(B)*b; b0=xb;
x=zeros(1,n+m) x(:,i)=xb' f=cb*xb
z=cb*inv(B)*A-c;%可用z=cb*(B\A)-c,判别数. end end
3.4数值实验及结果分析
求解线性规划问题:
???????=≥≤-=+-=++--4
,3,2,1,012216443033..3min 21421
3212
1i x x x x x x x x x t s x x i
在工作区输入:
A=[3,3,1,0;-4,-4,0,1;2,-1,0,0]; b=[30,16,12]'; c=[-3,1,0,0];
[x,f]=zuiyouhua(A,b,c) x =
7.3333 2.6667 0 0 0 56.0000 0 f =
-19.3333 检验结果正确
参考文献
[1] 吴祈宗.运筹学（第2版）[M].机械工业出版社
[2] 胡运权.运筹学教程（第二版）.清华大学出版社
[3] 胡运权.运筹学导论（第8版）.清华大学出版社
[4]大藤幹，半场方人.HTML&CSS&JavaScript语法辞典.中国青年出版社
[5] 唐开元，王华.浅析运筹学与计算机技术的结合.才智，2009年06期
最优化方法及其应用 作者：郭科 出版社：高等教育出版社 类别：不限 出版日期：20070701 最优化方法及其应用 的图书简介 系统地介绍了最优化的理论和计算方法,由浅入深,突出方法的原则,对最优化技术的理论作丁适当深度的讨论,着重强调方法与应用的有机结合,包括最优化问题总论,线性规划及其对偶问题,常用无约束最优化方法,动态规划,现代优化算法简介,其中前八章为传统优化算法,最后一章还给出了部分优化问题的设计实例,也可供一般工科研究生以及数学建模竞赛参赛人员和工程技术人员参考, 最优化方法及其应用 的pdf电子书下载 最优化方法及其应用 的电子版预览 第一章 最优化问题总论1.1 最优化问题数学模型1.2 最优化问题的算法1.3 最优化算法分类1.4
组合优化问題简卉习题一第二章 最优化问题的数学基础2.1 二次型与正定矩阵2.2 方向导数与梯度2.3 Hesse矩阵及泰勒展式2.4 极小点的判定条件2.5 锥、凸集、凸锥2.6 凸函数2.7 约束问题的最优性条件习题二第三章 线性规划及其对偶问题3.1线性规划数学模型基本原理3.2 线性规划迭代算法3.3 对偶问题的基本原理3.4 线性规划问题的灵敏度习题三第四章 一维搜索法4.1 搜索区间及其确定方法4.2 对分法4.3 Newton切线法4.4 黄金分割法4.5 抛物线插值法习题四第五章 常用无约束最优化方法5.1 最速下降法5.2 Newton法5.3 修正Newton法5.4 共轭方向法5.5 共轭梯度法5.6 变尺度法5.7 坐标轮换法5.8 单纯形法习題五第六章 常用约束最优化方法6.1外点罚函数法6.2 內点罚函数法6.3 混合罚函数法6.4 约束坐标轮换法6.5 复合形法习题六第七章 动态规划7.1 动态规划基本原理7.2 动态规划迭代算法7.3 动态规划有关说明习题七第八章 多目标优化8.1 多目标最优化问题的基本原理8.2 评价函数法8.3 分层求解法8.4目标规划法习题八第九章 现代优化算法简介9.1 模拟退火算法9.2遗传算法9.3 禁忌搜索算法9.4 人工神经网络第十章 最优化问题程序设计方法10.1 最优化问题建模的一般步骤10.2 常用最优化方法的特点及选用标准10.3 最优化问题编程的一般过程10.4 优化问题设计实例参考文献 更多 最优化方法及其应用 相关pdf电子书下载
陆吾生教授是加拿大维多利亚大学电气与计算机工程系 (Dept. of Elect. and Comp. Eng. University of Victoria) 的正教授, 且为我校兼职教授，曾多次来我校数学系电子系讲学。陆吾生教授的研究方向是：最优化理论和小波理论及其在1维和2维的数字信号处理、数字图像处理、控制系统优化方面的应用。 现陆吾生教授计划在 2007 年 10－11 月来校开设一门为期一个月的短期课程“最优化理论及其应用”（每周两次，每次两节课），对象是数学系、计算机系、电子系的教师、高年级本科生及研究生，以他在2006年出版的最优化理论的专著作为教材。欢迎数学系、计算机系、电子系的研究生及高年级本科生选修该短期课程，修毕的研究生及本科生可给学分。 上课地点及时间：每周二及周四下午2:00开始，在闵行新校区第三教学楼326教室。（自10月11日至11月8日） 下面是此课程的内容介绍。 ----------------------------------- 最优化方法及应用 I. 函数的最优化及应用 1.1 无约束和有约束的函数优化问题 1.2 有约束优化问题的Karush-Kuhn-Tucker条件 1.3 凸集、凸函数和凸规划 1.4 Wolfe对偶 1.5 线性规划与二次规划 1.6 半正定规划 1.7 二次凸锥规划 1.8 多项式规划 1.9解最优化问题的计算机软件 II 泛函的最优化及应用 2.1 有界变差函数 2.2 泛函的变分与泛函的极值问题 2.3 Euler-Lagrange方程 2.4 二维图像的Osher模型 2.5 泛函最优化方法在图像处理中的应用 2.5.1 噪声的消减 2.5.2 De-Blurring 2.5.3 Segmentation ----------------------------------------------- 注：这是一门约二十学时左右的短期课程，旨在介绍函数及泛函的最优化理论和方法，及其在信息处理中的应用。只要学过一元及多元微积分和线性代数的学生就能修读并听懂本课程。课程中涉及到的算法实现和应用举例都使用数学软件MATLAB 华东师大数学系
习题二包括题目：P36页5（1）（4） 5（4）
习题三 包括题目：P61页1(1)(2); 3; 5; 6; 14；15(1) 1(1)(2)的解如下 3题的解如下
5,6题 14题解如下 14. 设22121212()(6)(233)f x x x x x x x =+++---, 求点在(4,6)T -处的牛顿方向。 解：已知 (1) (4,6)T x =-，由题意得 121212212121212(6)2(233)(3)()2(6)2(233)(3)x x x x x x x f x x x x x x x x +++-----?? ?= ?+++-----?? ∴ (1)1344()56g f x -?? =?= ??? 21212122211212122(3)22(3)(3)2(233)()22(3)(3)2(233)22(3)x x x x x x x f x x x x x x x x +--+--------? ??= ? +--------+--?? ∴ (1)2(1)1656()()564G x f x --?? =?= ?-?? (1)1 1/8007/400()7/4001/200G x --?? = ?--?? ∴ (1)(1)11141/100()574/100d G x g -?? =-= ?-?? 15（1）解如下 15. 用DFP 方法求下列问题的极小点 （1）22 121212min 353x x x x x x ++++ 解：取 (0) (1,1)T x =，0H I =时，DFP 法的第一步与最速下降法相同 2112352()156x x f x x x ++???= ?++??， (0)(1,1)T x =，(0) 10()12f x ???= ??? (1)0.07800.2936x -??= ?-??， (1) 1.3760() 1.1516f x ???= ?-?? 以下作第二次迭代 (1)(0) 1 1.07801.2936x x δ-??=-= ?-??， (1)(0) 18.6240()()13.1516f x f x γ-??=?-?= ?-?? 0110 111011101 T T T T H H H H H γγδδδγγγ=+-
利用修正单纯形法解线性规划问题一软件示意：
二代码说明： Dim A(1 To 3, 1 To 6) As Double '矩阵A Dim a1(1 To 3) As Double '矩阵A的第一列向量 Dim a2(1 To 3) As Double '矩阵A的第二列向量 Dim a3(1 To 3) As Double '矩阵A的第三列向量 Dim a4(1 To 3) As Double '矩阵A的第四列向量 Dim a5(1 To 3) As Double '矩阵A的第五列向量 Dim a6(1 To 3) As Double '矩阵A的第六列向量 Dim B_(1 To 3, 1 To 3) As Double '基矩阵B的逆矩阵 Dim XB(1 To 3) As Double '基本可行解 Dim b(1 To 3) As Double '右端向量b Dim C(1 To 6) As Double '检验数 Dim CB(1 To 3) As Double '基本可行解对应的检验数 Dim π(1 To 3) As Double '单纯形乘子矢量 Dim r(1 To 6) As Double '检验矢量r Dim r_min As Double '检验矢量最小值 Dim k_sign As Integer '检验矢量最小值对应的位置 Dim Y(1 To 3, 0 To 6) As Double '矩阵y Dim just_vector(1 To 3) As Double Dim liji_min As Double '用于判断离基变量所用值 Dim r_sign As Integer '用于记录离基变量对应的位置 Dim main_yuan As Double '用于存放主元 Dim Erk(1 To 3, 1 To 3) As Double Dim Exchange_B(1 To 3, 1 To 3) '在矩阵Erk与矩阵B_进行乘法运算时，作为矩阵B_的替换矩阵
最优化方法及其Matlab程序设计 1.最优化方法概述 在生活和工作中，人们对于同一个问题往往会提出多个解决方案，并通过各方面的论证，从中提取最佳方案。最优化方法就是专门研究如何从多个方案中科学合理地提取出最佳方案的科学。最优化是每个人，每个单位所希望实现的事情。对于产品设计者来说，是考虑如何用最少的材料，最大的性能价格比，设计出满足市场需要的产品。对于企业的管理者来说，则是如何合理、充分使用现有的设备，减少库存，降低能耗，降低成本，以实现企业的最大利润。 由于优化问题无所不在，目前最优化方法的应用和研究已经深入到了生产和科研的各个领域，如土木工程、机械工程、化学工程、运输调度、生产控制、经济规划、经济管理等，并取得了显著的经济效益和社会效益。 用最优化方法解决最优化问题的技术称为最优化技术，它包含两个方面的内容： 1）建立数学模型。 即用数学语言来描述最优化问题。模型中的数学关系式反映了最优化问题所要达到的目标和各种约束条件。 2）数学求解。 数学模型建好以后，选择合理的最优化算法进行求解。 最优化方法的发展很快，现在已经包含有多个分支，如线性规划、整数规划、非线性规划、动态规划、多目标规划等。 2.最优化方法（算法）浅析 最优化方法求解很大程度上依赖于最优化算法的选择。这里，对最优化算法做一个简单的分类，并对一些比较常用的典型算法进行解析，旨在加深对一些最优化算法的理解。 最优化算法的分类方法很多，根据不同的分类依据可以得到不同的结果，这里根据优化算法对计算机技术的依赖程度，可以将最优化算法进行一个系统分类：线性规划与整数规划；非线性规划；智能优化方法；变分法与动态规划。 2.1 线性规划与整数规划 线性规划在工业、农业、商业、交通运输、军事和科研的各个研究领域有广泛应用。例如，在资源有限的情况下，如何合理使用人力、物力和资金等资源，以获取最大效益；如何组织生产、合理安排工艺流程或调制产品成分等，使所消耗的资源（人力、设备台时、资金、原始材料等）为最少等。 线性规划方法有单纯形方法、大M法、两阶段法等。 整数规划有割平面法、分枝定界法等。 2.2 非线性规划 20世纪中期，随着计算机技术的发展，出现了许多有效的算法——如一些非线性规划算法。非线性规划广泛用于机械设计、工程管理、经济生产、科学研究和军事等方面。
x zD 天津大学《最优化方法》复习题(含答案) 第一章 概述(包括凸规划) 判断与填空题 arg max f(x)二 arg min 以儿 “ max(x): x D 二 R n 』=-min(x): x D 二 R n ； 设f : D 5 R n > R.若x ： R n ，对于一切R n 恒有f(x”)^f(x)，则称x”为 设f : D 5 R n >R.若x ” ? D ,存在x ”的某邻域N ；(x”)，使得对一切 x ?N .(x)恒有f(x”)：：： f (x)，则称x”为最优化问题 min f (x)的严格局部最 优解? 给定一个最优化问题，那么它的最优值是一个定值 ? V 非空集合D R n 为凸集当且仅当 D 中任意两点连线段上任一点属于 D . V 非空集合D R n 为凸集当且仅当D 中任意有限个点的凸组合仍属于 D . V 任意两个凸集的并集为凸集? 函数f:D R n >R 为凸集D 上的凸函数当且仅当 -f 为D 上的凹函数? V 设f : D R n >R 为凸集D 上的可微凸函数，X ：D ?则对-D ,有 f (x) - f(x )乞 f (x )T (X —X )? 若c(x)是凹函数，则 D={x^R n C(x)启0}是凸集。 V f(x)的算法A 产生的迭代序列，假设算法 A 为下降算法, 则对-k ? 5,1, 2,…匚恒有 ________________ f(x k1)乞 f(x k ) ______________ ? 算法迭代时的终止准则(写出三种) ： ___________________________________________________ 凸规划的全体极小点组成的集合是凸集。 V 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 2 ( ( 最优化方法部分课后习题解答 1.一直优化问题的数学模型为： 习题一 min f (x ) = (x ? 3)2 + (x ? 4)2 ? g (x ) = x ? x ? 5 ≥ ? 1 1 2 2 ? 试用图解法求出： s .t . ?g 2 (x ) = ?x 1 ? x 2 + 5 ≥ 0 ?g (x ) = x ≥ 0 ? 3 1 ??g 4 (x ) = x 2 ≥ 0 （1） 无约束最优点，并求出最优值。 （2） 约束最优点，并求出其最优值。 （3） 如果加一个等式约束 h (x ) = x 1 ? x 2 = 0 ，其约束最优解是什么？ * 解 ：（1）在无约束条件下， f (x ) 的可行域在整个 x 1 0x 2 平面上，不难看出，当 x =（3，4） 时， f (x ) 取最小值，即，最优点为 x * =（3，4）：且最优值为： f (x * ) =0 （2）在约束条件下， f (x ) 的可行域为图中阴影部分所示，此时，求该问题的最优点就是 在约束集合即可行域中找一点 (x 1 , x 2 ) ，使其落在半径最小的同心圆上，显然，从图示中可 以看出，当 x * = 15 , 5 ) 时， f (x ) 所在的圆的半径最小。 4 4 ?g (x ) = x ? x ? 5 = 0 ? 15 ?x 1 = 其中：点为 g 1 (x ) 和 g 2 (x ) 的交点，令 ? 1 1 2 ? 2 求解得到： ? 4 5 即最优点为 x * = ? ?g 2 (x ) = ?x 1 ? x 2 + 5 = 0 15 , 5 ) ：最优值为： f (x * ) = 65 ?x = ?? 2 4 4 4 8 （3）.若增加一个等式约束，则由图可知，可行域为空集，即此时最优解不存在。 2.一个矩形无盖油箱的外部总面积限定为 S ，怎样设计可使油箱的容量最大？试列出这个优 化问题的数学模型，并回答这属于几维的优化问题. 解：列出这个优化问题的数学模型为： max f (x ) = x 1x 2 x 3 ?x 1x 2 + 2x 2 x 3 + 2x 1x 3 ≤ S
一、 填空题 1 ． 若 ()()??? ? ??+???? ?????? ??=212121 312112)(x x x x x x x f ，则 =?)(x f ，=?)(2x f . ２．设f 连续可微且0)(≠?x f ，若向量d 满足 ，则它是f 在x 处的一个下降方向。 3.向量T ) 3,2,1(关于3阶单位方阵的所有线性无关的共轭向量 有 ． 4. 设R R f n →:二次可微，则f 在x 处的牛顿方向为 . 5.举出一个具有二次终止性的无约束二次规划算 法: . 6.以下约束优化问题： )(01)(..)(min 212121 ≥-==+-==x x x g x x x h t s x x f 的K-K-T 条件为： . 7．以下约束优化问题： 1 ..)(min 212 2 21=++=x x t s x x x f 的外点罚函数为(取罚参数为μ) . 二、证明题（７分+8分) 1.设1,2,1,:m i R R g n i =→和m m i R R h n i ,1,:1+=→都是线性函数,证明下 面的约束问题: } ,,1{, 0)(},1{, 0)(..)(min 1112 m m E j x h m I i x g t s x x f j i n k k +=∈==∈≥=∑= 是凸规划问题。
2.设R R f →2 :连续可微，n i R a ∈,R h i ∈,m i ,2,1=,考察如下的约束条件问题: } ,1{,0} 2,1{,0..) (min 11m m E i b x a m I i b x a t s x f i T i i T i +=∈=-=∈≥- 设d 是问题 1 ||||,0,0..)(min ≤∈=∈≥?d E i d a I i d a t s d x f T i T i T 的解，求证：d 是f 在x 处的一个可行方向。 三、计算题（每小题１2分) １.取初始点T x )1,1() 0(=.采用精确线性搜索的最速下降法求解下面的无约束优化问题 (迭代２步）: 2 2212)(m in x x x f += 2.采用精确搜索的BFGS 算法求解下面的无约束问题： 212 2212 1)(min x x x x x f -+= 3.用有效集法求解下面的二次规划问题: . 0,001..42)(min 21212 12 221≥≥≥+----+=x x x x t s x x x x x f 4．用可行方向算法(Zoutend ｉj ｋ算法或Ｆrank Wol ｆｅ算法）求解下面的问题（初值设为)0,0() 0(=x ,计算到)2(x 即可）： . 0,033..22 1)(min 212112 22121≥≥≤+-+-= x x x x t s x x x x x x f
单纯形法求最优解问题 题目（老师布置的那道作业题）：2153m ax x x f +=，其中 ??? ??? ?=≥=++=+=+5,4,3,2,1,0182312245214 231j x x x x x x x x j ，求2153m ax x x f +=的最大值。 这张表是根据题目画的，Cj （行向量）为5432100053m ax x x x x x f ++++=中各个变量的系数，Ci （列向量）为与X B （列向量）相对应的各项的系数，X B 称为基变量（3列，由题目中的方程个数决定），起初的基变量由构造的变量x3、x4、x5组成，b 为对应三个方程等式右边的常数，z j 为Ci 各列与xj 各列乘积的和，如z1=0*1+0*0+0*3=0。i θ为判别将哪个基变量换出的依据，根据c j -z j 为正，要先将x2换入XB 中，关键是判断x3、x4、x5哪个跟x2换，这就要根据各列各列除以2x B i X =θ，与所得的最小的i θ对应的XB 换，如上表可知x2跟x4换，换完之后注意原来x4所对应的列向量为[0 1 0]T ,故要将x2所对应的列向量变换为为[0 1 0]T ，注意b 也要跟着变化，于是得下表.
由上表知c 1-z 1=3>0，故仍需将x1换入XB 中，用各列各列除以2x B i X =θ，与所得的最小的i θ对应的XB 换，结合i θ可知，x1跟x5换，于是得下表。 由上表可知c j -z j 均非正，故5432100053m ax x x x x x f ++++=取最大值时，????? ?? ?????????=00662x ， 对应的最大值36max =f . 系统工程导论知识点整理： 系统是由相互作用和相互依赖的若干组成部分(要素)结合的具有特定功能的有机整体。 系统的特征：整体性、相关性、目的性、环境适应性。 系统的功能是指系统与外部环境相互作用所反映的能力。 结构是功能的内在根据，功能是结构的外在表现。 系统功能的特性：易变性、相关性。 系统工程就是用科学的方法规划和组织人力、物力、财力，通过最优途径的选择，使人们的工作在一定期限内收到最合理、最经济、最有效的效果。 科学的方法：从整体观念出发，通盘筹划，合理安排整体中的每一个局部，以求得整体的最优规划、最优管理和最优控制，使每个局部都服从一个整体目标，力求避免资源的损失和浪费。
分数: ___________任课教师签字：___________ 课程作业 学年学期：2017——2018学年第二学期 课程名称：优化理论 作业名称：作业三 学生姓名： 学号： 提交时间：
一、问题重述 形如的min (x),x R n f ∈问题称为无约束优化问题，常用下降算法来解决这类问题。下降算法的关键在于步长和搜索方向的选取。步长的求取可以借助前面作业中提到的一维搜索等方法求取，而搜索方向算法可以分为两大类，解析法和直接法。 解析法借助了目标函数的导数进行搜索，这类算法搜索速度快、效率高，但是对目标函数的要求更为严格。常用的方法有最速下降法、Newton 法、共轭梯度法、拟Newton 法等。 直接法不使用导数，也不需要得到目标函数的明确解析式，只需要能够得到某些函数上的点即可。因此直接法的适用范围更广，但相应的收敛速度会较慢，计算量也会随着问题维数的增加而迅速增大。常用的方法有单纯形法、Powell 方向加速法以及Powell 改进算法。 本作业以直接法的Powell 法为例，解决具体的无约束优化问题，并对将Powell 方向加速法和Powell 改进算法解决结果进行对比。 二、算法原理 对于n 维正定二次函数(x)0.5T T f x Gx b x c =++，设011,,...(k n)k p p p -<关于G 共轭，0x 与1x 为任意不同点。分别从0x 与1x 出发，依次沿011,,...k p p p -作一维搜索。如果最后找到两个互不相同的极小点x a 与x b ，则x b a x -与011,,...k p p p -关于G 共轭。 Powell 方向加速法正是基于这一原理，每次迭代过程作n+1次一维搜索。第一次沿给定的n 个线性无关的方向011,,...n p p p -依次作一维搜索，之后沿由这一阶段的起点到第n 次搜索所得到的点的方向P 再做一次一维搜索，并把这次所得点作为下一阶段的起点，下一阶段的n 个搜索方向为011,,...,n p p p p -。以此直到找到最优解。 此算法是在迭代中逐次生成共轭方向，而共轭方向又是较好的搜索方向，所以称之为方向加速法。但是，此算法产生的n 个向量可能线性或近似线性相关，这时张不成n 维空间，可能得不到真正的极小点。因此，Powell 原始算法存在一定的缺陷。 Powell 改进算法虽然不再具有二次终止性，但克服了搜索方向的线性相关的不利情形，是解决无约束优化问题较有效的直接法之一。 本次作业一维搜索的过程是利用函数求导，求得最小值。经过试验发现，α是允许为负数的。否则最终寻优得到的极值点与实际结果存在很大的偏差，
三、单纯形法的解题步骤 第一步：作单纯形表. ）（1）把原线性规划问题化为标准形式； ）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵； ）（3）目标函数非基化； ）（4）作初始单纯形表. 第二步：最优解的判定. (1) 若所有检验数都是非正数，即，则此时线性规划问题已取 得最优解. (2) 若存在某个检验数是正数，即，而所对应的列向量无正分量，则线性规划 问题无最优解. 如果以上两条都不满足，则进行下一步. 第三步：换基迭代. ，并确定所在列的非基变量为进基变量. （1）找到最大正检验数，设为 （2）对最大正检验数所在列实施最小比值法，确定出主元，并把主元加上小括号. 主元是最大正检验数 所在列，用常数项与进基变量所对应的列向 量中正分量的比值最小者； 替换出基变量，从而得到新的基变量.也就是主元所在 （3）换基：用进基变量 （4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表； （5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止. 例3 求.
解（1）化标准型：令 ，引进松弛变量 ，其标准型为 求 （2）作单纯形表：在约束方程组系数矩阵中 的系数构成单位矩阵，故取 为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）.表 6.8
（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为 目标函数取得最优值. 原线性规划问题的最优解为：.目标函数的最优值为14，即. 例4 用单纯形方法解线性规划问题. 求. 解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出 ，, 代入目标函数 , 经整理后，目标函数非基化了. 作单纯形表，并进行换基迭代（见表6.9）. 最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变出基，非基变量进基. 换，基变量
分数: ___________ 任课教师签字：___________ 课程作业 学年学期：2017——2018学年第二学期 课程名称：优化理论 作业名称：作业三 学生姓名： 学号： 提交时间：
一、问题重述 形如的min (x),x R n f ∈问题称为无约束优化问题，常用下降算法来解决这类问题。下降算法的关键在于步长和搜索方向的选取。步长的求取可以借助前面作业中提到的一维搜索等方法求取，而搜索方向算法可以分为两大类，解析法和直接法。 解析法借助了目标函数的导数进行搜索，这类算法搜索速度快、效率高，但是对目标函数的要求更为严格。常用的方法有最速下降法、Newton 法、共轭梯度法、拟Newton 法等。 直接法不使用导数，也不需要得到目标函数的明确解析式，只需要能够得到某些函数上的点即可。因此直接法的适用范围更广，但相应的收敛速度会较慢，计算量也会随着问题维数的增加而迅速增大。常用的方法有单纯形法、Powell 方向加速法以及Powell 改进算法。 本作业以直接法的Powell 法为例，解决具体的无约束优化问题，并对将Powell 方向加速法和Powell 改进算法解决结果进行对比。 二、算法原理 对于n 维正定二次函数(x)0.5T T f x Gx b x c =++，设011,,...(k n)k p p p -<关于G 共轭，0x 与1x 为任意不同点。分别从0x 与1x 出发，依次沿011,,...k p p p -作一维搜索。如果最后找到两个互不相同的极小点x a 与x b ，则x b a x -与011,,...k p p p -关于G 共轭。 Powell 方向加速法正是基于这一原理，每次迭代过程作n+1次一维搜索。第一次沿给定的n 个线性无关的方向011,,...n p p p -依次作一维搜索，之后沿由这一阶段的起点到第n 次搜索所得到的点的方向P 再做一次一维搜索，并把这次所得点作为下一阶段的起点，下一阶段的n 个搜索方向为011,,...,n p p p p -。以此直到找到最优解。 此算法是在迭代中逐次生成共轭方向，而共轭方向又是较好的搜索方向，所以称之为方向加速法。但是，此算法产生的n 个向量可能线性或近似线性相关，这时张不成n 维空间，可能得不到真正的极小点。因此，Powell 原始算法存在一定的缺陷。 Powell 改进算法虽然不再具有二次终止性，但克服了搜索方向的线性相关的不利情形，是解决无约束优化问题较有效的直接法之一。 本次作业一维搜索的过程是利用函数求导，求得最小值。经过试验发现，α是允许为负数的。否则最终寻优得到的极值点与实际结果存在很大的偏差，而且寻优的效率特别低下。
一、 填空题 1.若()()??? ? ??+???? ?????? ??=212121 312112)(x x x x x x x f ， 则=?)(x f ，=?)(2x f . 2.设f 连续可微且0)(≠?x f ，若向量d 满足 ，则它是f 在x 处的一个下降方向。 3.向量T )3,2,1(关于3阶单位方阵的所有线性无关的共轭向量有 . 4. 设R R f n →:二次可微，则f 在x 处的牛顿方向为 . 5.举出一个具有二次终止性的无约束二次规划算法： . 6.以下约束优化问题： )(01)(..)(min 212121 ≥-==+-==x x x g x x x h t s x x f 的K-K-T 条件为： . 7.以下约束优化问题： 1 ..)(min 212 2 21=++=x x t s x x x f 的外点罚函数为（取罚参数为μ） . 二、证明题（7分+8分） 1.设1,2,1,:m i R R g n i =→和m m i R R h n i ,1,:1+=→都是线性函数，证明下 面的约束问题： } ,,1{, 0)(},1{, 0)(..)(min 1112 m m E j x h m I i x g t s x x f j i n k k +=∈==∈≥=∑= 是凸规划问题。
2.设R R f →2 :连续可微，n i R a ∈，R h i ∈，m i ,2,1=，考察如下的约束条件问题： } ,1{,0} 2,1{,0..) (min 11m m E i b x a m I i b x a t s x f i T i i T i +=∈=-=∈≥- 设d 是问题 1 ||||,0,0..)(min ≤∈=∈≥?d E i d a I i d a t s d x f T i T i T 的解，求证：d 是f 在x 处的一个可行方向。 三、计算题（每小题12分） 1.取初始点T x )1,1() 0(=.采用精确线性搜索的最速下降法求解下面的无约束优化问题 （迭代2步）： 2 2212)(m in x x x f += 2.采用精确搜索的BFGS 算法求解下面的无约束问题： 212 2212 1)(min x x x x x f -+= 3.用有效集法求解下面的二次规划问题： . 0,001..42)(min 21212 12 221≥≥≥+----+=x x x x t s x x x x x f 4.用可行方向算法（Zoutendijk 算法或Frank Wolfe 算法）求解下面的问题（初值设为)0,0() 0(=x ,计算到)2(x 即可)： . 0,033..22 1)(min 21211222121≥≥≤+-+-= x x x x t s x x x x x x f
动态规划方法在计算机专业的应用 科目：最优化方法 姓名：*** 专业：计算机科学与技术 学号：201320405 指导老师：*** 日期：2014/1/9
动态规划方法在计算机专业的应用 摘要：最优化方法是一门很有用的学科，本文结合计算机专业，讨论了用动态规划方法解决计算最长公共子序列、最大字段和、背包问题的过程，并对比其它算法以说明动态规划方法的高效、实用。 关键词：动态规划，最优化，算法分析 Abstract: The optimization method is a useful discipline, this paper, a computer professional, discusses the process used to calculate the dynamic programming method to solve the longest common subsequence, the maximum field and, knapsack problem, and compared to other algorithms to illustrate the dynamic programming method efficient and practical. Keywords: dynamic programming, optimization, algorithm analysis 动态规划（dynamic programming）是通过结合子问题的解而解决整个问题的。（此处“programming”是指一种规划，而不是指写计算机代码。）动态规划适用于子问题不是独立的情况，也就是各子问题包含公共的子子问题。在这种情况下，若用分治法则会做很多不必要的工作，即重复地求解公共的子子问题。动态规划算法对每个公共的子子问题只求解一次，将其结果保存在一张表中，从而避免了每次遇到各个子问题时重新计算答案。 一、算法设计与优化 动态规划通常应用于最优化问题。此类问题可能有很多可行解。
附录5 《最优化方法》复习题 1、设n n A R ?∈是对称矩阵，,n b R c R ∈∈，求1()2 T T f x x Ax b x c =++在任意点x 处的梯度和Hesse 矩阵． 解 2(),()f x Ax b f x A ?=+?=． 2、设()()t f x td ?=+，其中:n f R R →二阶可导，,,n n x R d R t R ∈∈∈，试求()t ?''． 解 2()(),()()T T t f x td d t d f x td d ??'''=?+=?+． 3、设方向n d R ∈是函数()f x 在点x 处的下降方向，令 ()()()()() T T T T dd f x f x H I d f x f x f x ??=--???， 其中I 为单位矩阵，证明方向()p H f x =-?也是函数()f x 在点x 处的下降方向． 证明 由于方向d 是函数()f x 在点x 处的下降方向，因此()0T f x d ?<，从而 ()()()T T f x p f x H f x ?=-?? ()()()()()()()() T T T T T dd f x f x f x I f x d f x f x f x ??=-?--???? ()()()0T T f x f x f x d =-??+?<， 所以，方向p 是函数()f x 在点x 处的下降方向． 4、n S R ?是凸集的充分必要条件是12122,,,,,,,,m m m x x x S x x x ?≥?∈L L 的一切凸组合都属于S ． 证明 充分性显然．下证必要性．设S 是凸集，对m 用归纳法证明．当2m =时，由凸集的定义知结论成立，下面考虑1m k =+时的情形．令1 1k i i i x x λ+==∑， 其中,0,1,2,,1i i x S i k λ∈≥=+L ，且1 1 1k i i λ+==∑．不妨设11k λ+≠（不然1k x x S +=∈， 结论成立），记11 1k i i i k y x λλ=+=-∑ ，有111(1)k k k x y x λλ+++=-+，
%%%%%%%%%%考虑外部性%%%%%%%%% K=[0.238982596 0.287307802 0.316082138 0.41731 0.44684 0.554375 0.7433476 -0.5]; Ae=[]; be=[]; Au=[-4312.03 -4428.81 -4762.01 -3621 -1742 -1125 -7042 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 16.99234332 15.49032101 16.29521726 0 0 0 0 0 28.69966647 24.77171169 25.46127697 0 0 0 0 0 0.374634341 0.243236446 0.217269563 0 0 0 0 0 3.709548964 3.549331817 3.764874154 0 0 0 0 0 0.519208086 0.439245837 0.453720507 -0.687558374 -0.330772352 -0.213615899 -1.337140588 0 0.800693399 0.626156548 0.637213949 -0.754544082 -0.362998009 -0.234427532 -1.467412158 0 1.389212223 0.956314404 0.910849795 -1.243454189 -0.598204142 -0.386325867 -2.418228224 0 0.02072254 0.007129367 0.003239074 -0.01405806 -0.006763088 -0.004367666 -0.027339646 0 1.481346246 1.260784084 1.304148318 -1.871119181 -0.900162832 -0.581333631 -3.638890162 0 -4070.125117 -4222.427454 -4572.482002 -3578.6343 -1688.3464 -1097.6625 -6592.7204 0 -0.87848773 -0.8804649 -0.87608648 -0.9171424 -0.9362472 -0.95345404 -0.9357319 0]; bu=[0;6.76;2.53;5022.16;300;250;40;36.351;0;0;0;0;0;-59200;-12.3074]; B1=[0;0;0;0;0;0;0;0]; X=linprog(K,Au,bu,Ae,be,B1); X %%%%%%%%%%%%%%%%%%%% %%%%%%不考虑外部性%%%%%%%%%%% K=[0.232622352 0.281860365 0.310653447 0.574625 0.46229 0.56 0.7433476 -0.5]; Ae=[]; be=[]; Au=[-4312.03 -4428.81 -4762.01 -3621 -1742 -1125 -7042 1 0 0 0 1 0 0 0 0
大学《最优化方法》复习题（含答案） 第一章 概述(包括凸规划) 一、 判断与填空题 1 )].([arg )(arg min max x f x f n n R x R x -=∈∈ √ 2 {}{} .:)(m in :)(m ax n n R D x x f R D x x f ?∈-=?∈ ? 3 设.:R R D f n →? 若n R x ∈*，对于一切n R x ∈恒有)()(x f x f ≤*，则称*x 为最优化问题 )(min x f D x ∈的全局最优解. ? 4 设.:R R D f n →? 若D x ∈*，存在*x 的某邻域)(*x N ε，使得对一切 )(*∈x N x ε恒有)()(x f x f <*，则称*x 为最优化问题)(min x f D x ∈的严格局部最 优解. ? 5 给定一个最优化问题，那么它的最优值是一个定值. √ 6 非空集合n R D ?为凸集当且仅当D 中任意两点连线段上任一点属于D . √ 7 非空集合n R D ?为凸集当且仅当D 中任意有限个点的凸组合仍属于D . √ 8 任意两个凸集的并集为凸集. ? 9 函数R R D f n →?:为凸集D 上的凸函数当且仅当f -为D 上的凹函数. √ 10 设R R D f n →?:为凸集D 上的可微凸函数，D x ∈*. 则对D x ∈?，有).()()()(***-?≤-x x x f x f x f T ? 11 若)(x c 是凹函数，则}0)( {≥∈=x c R x D n 是凸集。 √ 12 设{}k x 为由求解)(min x f D x ∈的算法A 产生的迭代序列，假设算法A 为下降算法， 则对{} ,2,1,0∈?k ，恒有 )()(1k k x f x f ≤+ .
精心整理 练习题一 1、建立优化模型应考虑哪些要素? 答：决策变量、目标函数和约束条件。 2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则。 min () f x D ∈，对于则有(f ?1例2.1解：*2、研究线性规划的对偶理论和方法（包括对偶规划模型形式、对偶理论和对偶单纯形法）。 答：略。 3、用单纯形法求解下列线性规划问题：
（1）???????≥≤+-≤++≤-++-=0 ,,4322 2..min 32131 3213213 21x x x x x x x x x x x t s x x x z ；（2）?????? ?=≥=++=+-=+-+-=)5,,2,1(052222..4min 53243232132Λi x x x x x x x x x x t s x x z i 解：（1）引入松弛变量x 4，x 5，x 6 因检验数σj >0，表明已求得最优解：*(0,8/3,1/3,0,0,11/3)X =，去除添加的松弛变量，原问题的最优解为：*(0,8/3,1/3)X =。 （2）根据题意选取x 1，x 4，x 5，为基变量：
因检验数σ2<0最小，故确定x 2为换入非基变量，以x 2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x 4作为换出的基变量。 4根据题意约束条件1和2可以合并为1，引入松弛变量x 3，x 4，构造新问题。
因检验数σj>0，表明已求得最优解：*(3/5,6/5) X 。Matlab调用代码： Matlab调用代码： f=[-10;-15;-12]; A=[5,3,1;-5,6,15;-2,-1,-1]; b=[9;15;-5]; lb=[0;0;0]; x=linprog(f,A,b,[],[],lb) 输出结果：
练习题一 1、建立优化模型应考虑哪些要素? 答：决策变量、目标函数和约束条件。 2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则。 答：针对一般优化模型()()min () .. 0,1,2, 0,1, ,i j f x s t g x i m h x j p ≥===，讨论解的可行域D ，若存在一点*X D ∈，对于X D ?∈ 均有*()()f X f X ≤则称*X 为优化模型最优解，最优解存在；迭代算法的收敛性是指迭代所得到的序列(1)(2)() ,, ,K X X X ，满足(1)()()()K K f X f X +≤， 则迭代法收敛；收敛的停止准则有(1)()k k x x ε+-<， (1)() () k k k x x x ε+-<， ()()(1)()k k f x f x ε+-<， ()()() (1)()()k k k f x f x f x ε+-<，()()k f x ε?<等等。 练习题二 1、某公司看中了例2.1中厂家所拥有的3种资源R 1、R 2、和R 3，欲出价收购（可能用于生产附加值更高的产品）。如果你是该公司的决策者，对这3种资源的收购报价是多少？（该问题称为例2.1的对偶问题）。 解：确定决策变量 对3种资源报价123,,y y y 作为本问题的决策变量。 确定目标函数 问题的目标很清楚——“收购价最小”。 确定约束条件 资源的报价至少应该高于原生产产品的利润，这样原厂家才可能卖。 因此有如下线性规划问题：123min 170100150w y y y =++ 123123123 5210 ..23518,,0y y y s t y y y y y y ++≥??++≥??≥? *2、研究线性规划的对偶理论和方法（包括对偶规划模型形式、对偶理论和对偶单纯形法）。 答：略。