262Vol.26No.2 20034ACTA MATHEMATICAE APPLICATAE SINICA Apr.,2003
Benson
?
(710071)
(637001;721007)
Benson
Benson Lagrange
Lagrange
Benson
1
[1–4].[5–10]
Benson
Lagrange
Benson Lagrange[10,11],
[12].
Lagrange
[12]Benson
()
Lagrange
Y Y?Y S Y cl S S int S S s∈S,λ≥0λs∈S S S S∩(?S)={θY}(θY Y),S A?Y,A
cone A={λa:a∈A,λ≥0}.
A=φ,cone(A)A cone(A) B?SθY∈cl B S=cone B,B S
20002202002512
?(69972036),(02J20102-06)
338
26
A ?Y,A =φ,
P min [A,S ]= y ∈A :(?S )∩clcone (A +S ?y )={θY }
,
P min [A,S ]
A
Benson [12]
.
X Y,Z
S ?Y,K ?
Z
Y,Z F :X →2Y
,G :X →2Z
S ?Y
S ?S ?=
s ?∈Y ?:s ?(s )≥0,s ∈S },s ?(s )s ?s
S ?i
= s ?∈Y ?:s ?(s )>0,s ∈S \{θY } .
F :X →2Y ,x 1,x 2∈X λ∈(0,1)
λF (x 1)+(1?λ)F (x 2)?F λx 1+(1?λ)x 2
+S,
F
X
S -
F
epi F
epi F = (x,y )∈X ×Y :x ∈X,y ∈F (x )+S
.
F
S -
epi F
X ×Y
F
X
S -
x 1,x 2∈X
λ∈(0,1)
λF (x 1)+(1?λ)F (x 2)?F (X )+S.
F
X S -
θ∈int S
x 1,x 2∈X ,
λ∈(0,1),
ε>0εθ+λF (x 1)+(1?λ)F (x 2)?F (X )+S.
[12]
F X
S -
(S -)
F (X )+int S F (X )+S
F
X
[6]
,cl F (X )+S S -S -S -S -S -
?S -
?S -?S -[13]S -F :X →2Y
S -clcone F (X )+S S -
?S -[13]
S -S -(VOP)
S ?min s.t.x ∈E
F (x ),
E = x ∈X :G (x )∩(?K )=φ
.
E
F
F (E )=∪x ∈E
F (x ).
x 0∈E
F (x 0)∩P min F (E ),S
=φ,
x 0
(VOP)
Benson
y 0∈F (x 0)∩P min F (E ),S
,
(x 0,y 0)
(VOP)
Benson (VOP),
(VOP ?)
min s.t.x ∈E
(?F )(x ),
2Benson339?∈Y?\{θY?}x∈E,y∈F(x),y∈F(E)?(y)≤?(y), (x,y)(VOP?)x(VOP?)
N A,B?X,
A+B={a+b:a∈A,b∈B},A×B=
(a,b):a∈A,b∈B
.
A?R,A≥0a∈A,a≥0,A≥B a∈A,b∈B a≥b. 2Benson
2.1[12]?∈S?i(x0,y0)(VOP?)(x0,y0) (VOP)Benson F E S-S
(x0,y0)(VOP)Benson?∈S?i(x0,y0)(VOP?)
2.2[14,Th.2.3]Y P Q Y P∩Q={θY}.
Q P C P\{θY}?int(C)C∩Q={θY}.
2.3[15]B C X C
int(B+C)=B+int C.
2.4[16]Y Q Q?
(1)q?∈Q?\{θY?},q∈int Q q?(q)>0;
(2)q?∈int Q?,q∈Q\{θY}q?(q)>0.
2.1(x0,w0)(VOP)Benson
F(x)?w0,G(x)
S×K-
S int K=φ,s?∈S?i∪{θY?},k?∈K?,(s?,k?)=(θY?,θZ?),
inf x∈X
s?
F(x)
+k?
G(x)
=s?(w0),(1) inf k?
G(x0)
=0,(2)
s?
F(x)
=∪
y∈F(x)
s?(y),k?
G(x)
=∪
z∈G(x)
k?(z).
(x0,w0)(VOP)Benson
clcone
F(E)+S?w0
∩(?S)={θY}.(3)
??(x)=
F(x)?w0
×G(x),??(x):X→2Y×Z??(x)S×K-clcone
??(X)+S×K
∩
?(S\{θY}×int K)
=φ.(4)
(4)(α,β)∈Y×Z
(α,β)∈clcone
??(X)+S×K
∩
?(S\{θY}×int K)
,(5)
α∈?S\{θY},β∈?int K,x n∈X,(y n,z n)∈
F(x n),G(x n)
,
y n?
w0,z n
∈??(x n),(s n,k n)∈S×K,λn>0,(α,β)=lim
n→∞
λn
(y n?w0,z n)+(s n,k n)
,
α=lim
n→∞λn(y n?w0+s n),β=lim
n→∞
(z n+k n).?int K
λn(z n+k n)∈?K(n∈N).z n+k n∈?k(n∈N).k n∈K,z n∈?k(n∈
34026
N ).
x n ∈E,y n ∈F (E )(n ∈N )α∈clcone F (E )?w 0+S ∩ ?S \{θY }
,(3)
(4)(4)θY ∈S
clcone ??(X )+S ×K ∩ ?(S ×(int K ∪{θZ }) = (θY ,θZ ) .
θZ ∈int K,(θY ,θZ )∈clcone (??(X )+S ×K ),
clcone ??(X )+S ×K ∩ ?(S ×{θZ }) = (θY ,θZ ) .
(6)S S ×{θZ } 2.2P
? S ×{θZ } \ (θY ,θZ )
?int P
clcone ??(X )+S ×K ∩P = (θY ,θZ ) .
Q =
? (S \{θY })× int K ∪{θZ } +P ∪ (θY ,θZ ) ,Q Q
(x 0,w 0)(VOP)Benson z 0∈G (x 0)∩(?K ),
(s,k )∈S ×K ,
(s,k )=(θY ,z 0)+(s,k ?z 0)∈ F (x 0)?w 0,G (x 0) +S ×K ?clcone ??(X )+S ×K
.S ×K ?clcone ??(X )+S ×K .clcone ??(X )+S ×K ∩P = (θY ,θZ )
(S ×K )∩P = (θY ,θZ ) , (S \{θY })× int K ∪{θZ }
∩P =φ.S,int K ∪{θZ }
P Q 2.3int Q =int P ? S \{θY } × int K ∪{θZ }
.s ∈S \{θY },k ∈
int K ∪{θZ },
?(s,k )=?(s/2,k )?(s/2,θZ )∈? S \{θY } × int K ∪{θZ }
+int P =int Q,? S \{θY } × int K ∪{θZ }
?int Q.
clcone ??(X )+S ×K ∩Q = (θY ,θZ ) .u ∈clcone ??(X )+S ×K ∩
Q,u =(θY ,θZ ).Q
u =u 1+u 2,u 1∈? S \{θY }× int K ∪{θZ }
,u 2∈P.u 2=u ?u 1∈ clcone (??(X )+S ×K )?u 1 ∩P ?clcone ??(X )+S ×K
,
u 2=(θY ,θZ ).
u =u 1∈ ? S \{θY }×(int K ∪{θZ }) ∩clcone ??(X )+S ×K
,
(4)
(s ?,k ?)∈Q ?,(s ?,k ?)=(θY ,θZ ),
s ?(s )+k ?(k )≥0,(s,k )∈clcone ??(X )+S ×K
,
s ? F (x ) +k ? G (x )
≥s ?(w 0),x ∈X
(7)
s ?(s )+k ?(k )<0,(s,k )∈int Q .? S \{θY } × int K ∪{θZ }
?int Q,
s ?(s )+k ?(k )>0,(s,k )∈ S \{θY } × int K ∪{θZ }
,s ?∈S ?i ∪{θY ?}.
s →θY ,k ?∈K ?.
2
Benson 341
(7)x =x 0,w 0∈F (x 0)k ? G (x 0)
≥0.x 0∈E,
G (x 0)∩(?K )=φ,p ∈G (x 0)k ?(p )≤0,k ?(p )=0,0∈k ?
G (x 0) .
s ?(w 0)=s ?(w 0)+0∈s ? F (x 0) +k ?
G (x 0) (1)(2).
2.2(x 0,w 0)(VOP)Benson F (x ),G (x ) S ×K -S int K =φ,s ?∈S ?i ∪{θY ?},k ?∈K ?,(s ?,k ?)=(θY ?,θZ ?),
inf x ∈X
s ? F (x ) +k ? G (x ) =s ?(w 0),inf k ? G (x 0) =0.2.2 F (x )?w 0,G (x ) S ×K -2.2 2.12.3(x 0,w 0)(VOP)Benson
F (x )?w 0,
G (x )
S ×K -S int K =φ,x ∈X G (x )∩(?intK )=φ,
s ?∈S ?i ,k ?∈K ?,
inf x ∈X
s ? F (x ) +k ? G (x )
=s ?(w 0),(8)
inf k ? G (x 0)
=0.
(9)
2.1
s ?∈S ?i ∪{θY ?},k ?∈K ?,(s ?,k ?)=
θY ?,θZ ? ,
(8),
(9)
s ?=θY ?.
k ?=θZ ?inf x ∈X
k ? G (x )
=0.
G (x )∩(?int S )=φ,z ?∈G (x )∩(?int S ), 2.4k ?(z ?)<0,
2.4(x 0,w 0)(VOP)Benson F (x ),G (x ) S ×K -S int K =φ,x ∈X G (x )∩(?int K )=φ,s ?∈S ?i ,k ?∈K ?,inf x ∈X
s ? F (x ) +k ? G (x ) =s ?(w 0),inf k ?
G (x 0) =0.
2.32.5(VOP)
(i)x 0∈E ;(ii)w 0∈F (x 0),(s ?,k ?)∈S ?i ×K ?,
inf x ∈E
s ? F (x ) +k ? G (x )
=s ?(w 0);
(iii)inf k ? G (x 0)
=0,(x 0,w 0)(VOP)Benson
(iii)k ? G (x 0)
≥0.G (x 0)∩(?K )=φ,p ∈G (x 0)∩(?K )
k ?(p )≤0,k ?(p )=0.(ii)s ? F (x )
≥s ?(w 0)x ∈E (x 0,w 0)(VOP ?) 2.1(x 0,w 0)(VOP)Benson
3
Benson
Lagrange
(VOP)
Benson
Lagrange
(DVOP)S ?
max
(x,y,T )∈W
F (x ),
W =
(x,y,T ):T ∈L +(Z,Y ),x ∈E,y ∈F (x )
y ∈P min
F (E )+
T [G (E ) ,S ,T G (x )∩(?K )
={θY } ,L +(Z,Y )
Z Y T (K )?S
T
342
26
3.1
x 0∈E,y 0∈F (x 0),(x 0,y 0)(VOP)Benson
S
x ∈X G (x )∩(?int K )=φ, F (x )?y 0,G (x )
:X →2Y ×Z
S ×K -
T ∈L +(Z,Y )
y 0∈P min F (E )+T G (E ) ,S
T G (x 0)∩(?K )
={θY }.
2.3s ?∈S ?i ,k ?∈K ?,s ? F (x )?y 0 +k ? G (x )
≥0,
x ∈E,k ? G (x 0)
≥0.
k ? G (x 0)∩(?K )
={0}.
s 0∈S \{θY }s ?(s 0)=1.T :Z →Y T (z )=k ?(z )s 0,z ∈Z ,T ∈L +(Z,Y ),T (K )=k ?(K )s 0?S.z 0∈G (x 0)∩(?K )T (z 0)=k ?(z 0)s 0=θY .
x ∈E
s ? F (x )+T (G (x )) =s ? F (x ) +k ? G (x )
s ?(s 0)=s ? F (x ) +k ? G (x )
≥s ?(y 0).
2.1y 0∈P min F (E )+T G (E ) ,S
.
T G (x 0)∩(?K ) =k ? G (x 0)∩(?K )
s 0={0}s 0={θY }.
3.2x 0∈E,y 0∈F (x 0).T ∈L +(Z,Y )T G (x 0)∩(?K )
=
{θY },y 0∈P min F (E )+T [G (E )]
,
x 0(VOP)Benson (x 0,y 0)(VOP)Benson
clcone F (E )+T G (E ) +S ?y 0
∩(?S )={θY },
{θY }?clcone
F (E )+S ?y 0 ∩(?S )
?clcone F (E )+T G (E )
+S ?y 0 ∩(?S )={θY },
y 0∈P min F (E ),S
.
3.3()(x 0,y 0,T 0)(DVOP)
s ?0∈S
?i
(VOP)x 0s ?0 F (x
0)?y 0 ≥0.
(x 0,y 0,T 0)(DVOP)
y 0∈P min
F (E )+T 0
G (E ) ,S
T 0 G (x 0)∩(?K )
={θY }.
s ?0∈S
?i
s ?0 F (x )+T 0 G (x )
≥s ?0(y 0),
x ∈E.
2
Benson
343
x 0
(VOP)
k ?∈K ?
y
0∈G (x 0)
k ?(y
0)≤0.
x =x 0
s ?0 F (x 0)+T 0 G (x
0) ≥s ?0(y 0).
s ?0(F (x
0)?y 0)≥0.
3.4()x 0∈E,y 0∈F (x 0),(x 0,y 0)(VOP)Benson
S x ∈X G (x )∩(?int K )=φ, F (x )?y 0,G (x )
:X →2Y ×Z S ×K -T 0∈L +(Z,Y )(x 0,y 0,T 0)(DVOP)Benson
(x 0,y 0)(VOP)
Benson
3.1
T 0∈L +(Z,Y )(x 0,y 0,T 0)(DVOP)
(x 0,y 0,T 0)
(DVOP)
Benson
clcone F (E )?S ?y 0
∩S ={θY }.
α∈S \{θY },λn ≥0,s n ∈S,x n ∈E,y n ∈F (x n ),α=lim n →∞
λn (y n ?s n ?y 0).
3.3s ?00
λn s ?0(y n )?s ?0(s n )?s ?
0(y 0) ,
n ∈N λn s ?0(y n )?s ?0(s n )?s ?0(y 0) >0,λn s ?0(y n )?s ?
(y 0) >0,s ?0(y 0?y n )<0.
3.33.5()S (x 0,y 0,T 0)(DVOP)(x 0,y 0)
(VOP)Benson
3.2
1Corley H W.Optimality Conditions for Maximizations of Set-valued Functions.J.Optim.Theory Appl.,1988,58(1):1–10
2Lin Laijiu.Optimality of Set-valued Functions.J.Math.Anal.and Appl.,1994,186(1):30–51
3Sawaragi Y,Nakayama H,Tanino T.Theory of Multiobjective Optimization.New York:Academic Presss,Inc.,1985
4Li Yuanxi.Topological Structure of E?cient Set of Optimization Problem of Set-valued mapping.Chin Ann.of Math.(Series B),1994,15(1):115–1225Song Wen.Duality for Vector Optimization of Set-valued Function.J.Math.Anal.and Appl.,1996,201(2):212–225
6Song https://www.doczj.com/doc/5514083899.html,grangian Duality for Minimization of Nonconvex Multifunctions.J.Optim.Theory
and Appl.,1997,93(1):167–182
7Li Zhongfei,Chen https://www.doczj.com/doc/5514083899.html,grangian Multipliers,Saddle Points and Duality in Vector Optimization of Set-valued Maps.J.Math.Anal.and Appl.,1997,215(2):297–316
8Li Zemin.The Optimality Conditions for Vector Optimiaztion of Set-valued Maps.J.Math.Anal.and Appl.,1999,237(3):413–424
9Li Zemin.A Theorem of the Alternative and Its Application to the Optimization of Set-valued Maps.J.Optim.Theory and Appl.,1999,100(2):365–37510Chen Guangya,Rong Weidong.
Characterizations of the Benson Proper E?ciency for Nonconvex
Vector Optimization.J.Optim.Theory and Appl.,1998,98(2):365–384
11Wang Shouyang,Li Zhongfei.Scalarizatons and Lagrange Duality in Multiobjective Optimization.
Optimization,1992,26(3):315–32412
Benson
1998,21(1):123–134
34426
(Li Zhongfei.Benson Proper E?ciency in Vector Optimization of Set-valued Maps.Acta Math.
Appl.Sinica,1998,21(1):123–134
13’98,
1998,12–16
(Yang Xinmin,Wang Shouyang.On the E?ciency of Vector Set-valued Maps.Advances in MCDM’98,Hong Kong:Global Publishing Co.,1998,12–16
14Dauer J P,Saleh O A.A Characterization of Proper Minimal Problem as a Solution of Sublinear Optimization Problems.J.Optim.Theory and Appl.,1993,178(2):227–246
15Zowe J.A Remark on a Regularity Assumption for the Mathematical Programming Problem in Banach Spaces.J.Optim.Theory and Appl.,1978,25(3):375–381
161994,126–127
(Hu Y D.E?ciency Theory of Multiobjective Programming.Shanghai:Shanghai Science and Technique Publisher,1994,126–127
17Frenk J B,Kassay G.On Classes of Generalized Convex Functions,Gordon-Farkas Type Theorem and Lagrangian Duality.J.Optim.Theory and Appl.,1999,102(2):315–343
18Borwein J M.Proper E?cient Points for Maximizations with Respect to Cone.SIAM J.Control Optimization,1877,15(1):57–63
THE OPTIMALITY CONDITIONS AND DUALITY OF
NONCONVEX VECTOR SET-V ALUED OPTIMIZATION WITH BENSON PROPER EFFICIENCY
LIU Sanyang
(Department of Applied Mathematics,Xidian University,Xi’an710071)
SHENG Baohuai
(Post Doctor Station of Southwest Institute of Petroleum,Nanchong637001&
Department of Mathematics,Baoji College of Arts and Sciences,Baoji721007)
Abstract A kind of re?ned optimality necessary and su?cient conditions for constrained vector optimization of set-valued maps with Benson proper e?cient solutions is established without the assumption that the partial order cone’s interior is nonempty,from which a modi?ed Lagrangian duality for nonconvex vector optimization of set-valued maps with Benson proper e?cient solutions is presented.The weak duality theorem,the direct duality theorem and the inverse duality theorem are given.The advantages of this kind of duality over the classical Lagrangian duality in the facts that it has better duality properties.
Key words Set-valued maps,Benson proper e?ciency,optimality conditions,duality
线性规划原问题与对偶问题的转化及其应用 摘要 线性规划对偶问题是运筹学中应用较广泛的一个重要分支，它是辅助人们进行科学管理的一种数学方法.线性规划对偶问题能从不同角度为管理者提供更多的科学理论依据，使管理者的决定更加合理准确.本文主要探讨了线性规划原问题与对偶问题之间的关系、线性规划原问题与对偶问题的转化以及对偶理论的应用.本文的研究主要是将复杂的线性规划原问题转化成对偶问题进行解决，简化了线性规划问题，使人们能够快速的找出线性规划问题的最优解. 关键词：线性规划；原问题；对偶问题；转化LinearProgrammingistheOriginalProblemandtheTransformationoftheDu alProblemandApplications Abstract:Linearprogramminginoperationalresearchisresearchearlier,rapiddevelopmentandw ideapplication,themethodisanimportantbranchofmature,itisoneofthescientificmanagementofa uxiliarypeoplemathematicalmethod.Canfromdifferentanglestolinearprogrammingdualproble mforpolicymakerstoprovidemorescientifictheorybasis.Thisarticlemainlyprobesintothelinearp rogrammingproblemandtherelationshipbetweenthedualproblem,linearprogrammingproblem andthetransformationofthedualproblem,theapplicationoflinearprogrammingdualproblem.Thi sarticleisthecomplexoftheoriginalproblemintoitsdualproblemtobesolved,simplifiesthelinearp rogrammingproblem,enablesustorapidlyfindtheoptimalsolutionoflinearprogrammingproble m. Keywords:linearprogramming;theoriginalproblem;thedualproblem;conversion 目录
机组组合问题的优化方法综述 陈皓勇 王锡凡 (西安交通大学电力工程系 710049 西安) 1998205215收稿。 国家教委博士点基金资助项目。 (上接本刊1999年第4期第56页) 5 拉格朗日松弛法 电力系统是一个非常典型的大系统,是大系统优化和控制理论的一个重要应用领域[42]。大系统的分解协调思想最早见于D an tzig 和W o lfe 对于线性规划问题的分解[43],而用于机组组合问题的主要是拉格朗日松弛(L agrangian relaxati on )法[44～47],该方法产生于70年代,是解决复杂整数和组合优化问题的一类优化算法,它建立在下述思想的基础上:许多困难的整数规划问题可看成是由一些边界约束条件联系在一起的一系列相对容易的子问题组成,利用这个特点,把约束条件被破坏的量和它们各自的对偶变量的乘积加在目标函数上作为惩罚项,形成拉格朗日问题。拉格朗日问题相对容易解决,对于最大(小)化问题,它的优化值是原问题优化值的上(下)界,因此在分支定界法中,它能够取代线性规划法以提供下界。 下面以最大化问题为例来说明这种方法: Z =m ax X {c T X AX ≤b , D X ≤e ,X ≥0且是整数向量} 其中 X 是n 维向量;b ,c ,e 分别为m 维、n 维、k 维向 量;A ,D 分别为m ×n ,k ×n 的矩阵。 假设问题的约束条件可以分为两组,即AX ≤b 和D X ≤e ,并且如果去掉约束AX ≤b ,问题会变得相对容易解决。因此可以构造拉格朗日问题: Z D (u )=m ax X {c T X +u T (b -AX ) D X ≤e , X ≥0且是整数向量} 对偶变量u 的值应该通过解对偶问题Z D =m in u {Z D (u ) u ≥0}来得到。由于Z D (u )对u 是不可 微的,通常用次梯度法来求解,从初始点u 0开始,应用公式u k +1=m ax{0,u k -t k (b -AX k )}迭代求解。其中t k 是标量步长,X k 是第k 步拉格朗日问题的优化解。 拉格朗日松弛法在机组组合问题中应用时,把 所有的约束分成两类,一类是全系统的约束,即文章第1部分模型中的P (X ),一类是可以按单台机组分解的约束,如模型中的R (X ,Z ),M (X ,Z ),U (Z ),P (X )可以写成惩罚项的形式,加入目标函数,形成拉格朗日函数,拉格朗日函数可按单台机组分解成一系列的子问题,子问题一般用动态规划法求解,对偶问题一般用次梯度法[48]求解。 拉格朗日松弛法在机组组合问题中的应用研究始于70年代,80年代逐渐推广,90年代成为主流,有大量的理论和应用成果。早期的应用多结合分支定界法,但在后来的应用中发现分支定界的框架是可以完全抛弃的,直接解对偶问题并结合一些启发式的调整策略即能得出原问题的最优解或次优解。在后来的研究中发现,为解决由于线性费用函数造成的解的振荡问题,需要在目标函数中加入二次惩罚项,采用辅助问题原理(aux iliary p rob lem p rinci p le )和增广拉格朗日法(augm en ted L agrangian )来解决 [49～51] 。文献[52,53]以分支定界法为框架,应用对偶方法求分支定界树各节点的下界,使用近似罚函数法,不但能解对偶问题,而且能为构造原问题的近似优化解提供有用的信息。文献[53]论证了对偶间隙(duality gap ,即原问题的优化值和对偶问题优化值之间的差值)相对值随着机组数增加而减少。由于对偶法提供了主问题紧的下界和构造优化可行解的有用信息,只需检查一个节点,甚至可以完全放弃分支定界框架。随着机组数增加,计算量线性增长。文献[54]直接应用拉格朗日松弛法求解机组组合和水火电负荷经济分配的问题,用次梯度法优化拉格朗日乘子,用动态规划法求解单台热力机组的开停机问题,用罚函数法求解凸水电优化控制问题,用文献[52,53]的方法从对偶问题的解构造原问题的可行解。 文献[55]提出的方法,不用分支定界的框架,而是直接从对偶问题的解构造原问题的解。该方法利用了电力系统的如下特点:若所有投入运行的机组能满足系统的旋转备用要求,则系统的功率一定能够平衡。因此使用特殊的算法来选择拉格朗日乘子,保证在迭代的过程中旋转备用能够满足要求。文献[56]使用拉格朗日松弛法进行分解,用连续逼近 1 51999年3月 电 力 系 统 自 动 化 A utom ati on of E lectric Pow er System s 第23卷 第5期
1、举例说明什么是关键词堆砌？ 本帖隐藏的内容 答：理论上来说，堆砌是指同义关键词的累积叠加组成的标题，比如男裤长裤直筒裤休闲裤商务裤中年裤热卖这样的标题，影响买家的体验； 事实上，我们在组合标题时，只要是通过我们黄金词助手找出的关键词，都是没有太大问题的； 2、举例说明什么叫品牌词和敏感词？ 本帖隐藏的内容 答：滥用品牌词：宝贝卖的不是耐克、阿迪达斯，标题出现耐克、阿迪达斯 滥用敏感词：高仿，同款等； 尤其是在今年，淘宝严打期间，这样的词是绝对不能用的； 3、标题组合中一般用什么符号隔开？ 本帖隐藏的内容 答：理论上来说，是用空格或者/这两种符号，一般情况下我们习惯用空格，但有的时候为了标题看起来更加的可读，会用到/，比如ipone4/4s，要比ipone4 4s 更加的可读； 4、淘宝标题分词的三个原则是什么？ 本帖隐藏的内容 答：三个原则是紧密优先原则，前后无关原则，偏正组合原则； 这里三个原则的重要程度为紧密优先>前后无关>偏正原则，也就是说我们组合标题时最应该考虑的原则是紧密优先原则； 5、举例说明什么叫紧密优先原则？
本帖隐藏的内容 答：对于某一个关键词来说，紧密排列要优于分开排列，比如如果我想做男士单肩包这个词，正品男包男士单肩包这样的写法要优于男士正品男包单肩包这样的写法，这是对于某一个关键词来说； 而很多时候我们需要做很多关键词，如果不能将所有的关键词都紧密排列的时候，我们需要做取舍，这些词里一定有我们最想做的词，那么就选择这个词紧密排列，其他的只能分开； 举例：看下图 对于这两个词来说，都是我们可用的黄金词，第一个词搜索指数为7235，竞争宝贝数为2993，第二个词搜索指数为3767，竞争宝贝数为4093，很明显，第一个优于第二个词，那么我们首先应该将第一个词紧密排列，这就是取舍； 6、举例说明什么叫前后无关原则？ 本帖隐藏的内容 答：前后无关是指，对于两个关键词来说，哪个在前，哪个在后没有关系，比如第一关键词+第二关键词=第二关键词+第一关键词； 这里一定要明确，前后无关原则是针对两个独立的关键词来说的； 7、举例说明什么叫偏正组合原则？ 本帖隐藏的内容
weili@https://www.doczj.com/doc/5514083899.html,
主要内容 ?组合最优化问题概论 ?现代最优化计算方法 –禁忌搜索（tabu search） –模拟退火（simulated annealing） –遗传算法（genetic algorithms） –人工神经网络（neural networks） –拉格朗日松弛算法（Lagrange slack arithmetic）
?组合最优化（combinatorial optimization ） –是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等 –组合最优化问题的数学模型 其中，f(x)为目标函数，g(x)为约束函数，x 为决策变量，D 表示有限个点组成的集合 D x 0 g(x) .t .s ) x (f min ∈≥
?组合最优化（combinatorial optimization ） –一个组合最优化问题可用三参数（D,F,f ）表示，其中D 表示决策变量的定义域，F 表示可行解区域F 中的任何一个元素称为该问题的可行解，f 表示目标函数。满足的可行解称为该问题的最优解 –组合最优化的特点是：可行解集合为有限点集 –有可行解一定有最优解 }0)x (g ,D x |x {F ≥∈=}F x |x)(f {min )x (f *∈=*x
?组合最优化问题 例1.（最优投资问题）设一个人的财富为b ，现有n 只价格为、预期收益分别为的股票，如何选择投资策略使得该人投资收益最大？解：用数学模型表示为： )n ,2,1i (a i L =)n ,2,1i (c i L =(3) n ,2,1i },1,0{ x (2) ,b x a .t .s (1) x c max i n 1 i i i n 1 i i i L =∈≤∑∑==
工作交流 推波助澜的作用。因此政府应引导企业利用当前的高储蓄率进行技术创新,引导储蓄转化为优质投资,同时也能够提升企业的核心竞争力。 同时,由于经济体制本身的问题,一些资源性行业和大型国企在经济增长的过程中积累了大量财富,而这些财富又大部分来自部门垄断产生的超额利润,但这些财富并没有通过再次分配最终流向普通居民手中,导致企业储蓄率居高不下、居民消费水平依然过低的局面。而要改变这一现象就要从收入分配结构上解决问题,国有企业每年应向财政上交一部分利润,财政将这部分利润主要用于落后地区和农村的公共基础设施建设、社会保障支出和救济穷人。另外应对现行的财税制度进行改革,通过国有企业分红和对资源性行业收租的形式促进资源有效利用,疏导企业储蓄,改变初次分配资本所得偏多劳动所得偏少,再分配政府、企业所得偏多,居民所得偏少的局面,缓解行业间收入分配的不均,努力提高低收入群体的收入水平,扩大中等收入群体的比重,调节高收入群体的收入水平,以此增加城乡居民的消费 倾向,为扩大内需创造条件。 第五,对于楼市和股市过热的局面, 我认为要通过政策的调整给短期投机炒作 的行为以根本性的打击,如对楼市可提高 房产交易税,房产闲置税,必要时可以规 定房产的交易期限;对股市要提高证券印 花税。从而遏制短期交易频繁的情况,以 引导人们长期投资。同时,要采取果断措 施打压楼市和股市存在的高收益情况,平 衡各行业的收益率,以使资金比较均匀地 流向各个行业,以让人按照专业,特长在 市场中自由分工,同时也使得各行业协调 发展。 第六,疏导金融机构资金流向中小企 业和农村,转变经营模式。商业银行一直 以来追逐大客户的经营思路,导致一些银 行房地产和按揭贷款的比例占总资产的比 例较高,不断趋同的客户结构和集中的行 业风险,蕴涵着较大的银行信贷风险,但 与此同时中小企业和农村的贷款需求却未 得以满足。而中小企业占企业总数的95% 左右,创造了全国企业利税总数的60%, 解决了75%的就业机会,而可得贷款却不 足三分之一。占全国人口总数65%、占国 土面积80%以上的广大农村,实际上只有 农村信用社一家金融机构在经营,而仅就 广大农村消费需求的调查,至少还要增加3 万亿元的购买力。改变信贷投向结构,将 过剩的流动性用于大力开发中小企业和农 村信贷市场,不仅能够满足中小企业和农 民需求,而且可以将资金利用充分,信贷 风险也得到了均衡的配置。 因此,面对结构失衡的货币现象,单 纯地从总量上加以控制实现收缩经济并不 能从根本上解决流动性不断生成和经济的 结构性问题。综合、协调地运用外贸、财 税、农业、区域、房地产以及收入分配、 资源价格和基本公共服务等各种宏观调控 政策,发挥各部门/合力0作用,从根源 上调整结构和转变经济的增长方式,全面 的过热也就不可能出现。我认为这才是保 持国民经济持续平稳协调健康发展的根本 之道。 (作者单位:云南民族大学经济学院) 组合最优化对策问题的思考 t叶志萍 摘要:组合最优化对策理论的最初应用,主要是抽象的理论性应用。它为经济学提供了一个分析工具,能够将经济生活中利益不同、动机不同但又相互影响的经济主体的效用考虑进去。经济学中用到对策论最多的地方是证明纳什均衡解的存在,而对于如何找到一个具体对策的均衡解,经济学中常常并不关心,因为经济学所考虑的复杂而庞大的系统是很难用实实在在的数据去具体描述的。随着计算机科学的发展,组合最优化对策理论陆续出现许多实际应用,这些实际应用的需求导致算法成为了组合最优化对策理论研究的热点。本文就组合最优化对策的内涵着手,分析了组合最优化对策的算法,探讨了组合最优化对策及其核心,得出了决策系统中的非合作对策模型及纳什均衡解。 关键词:组合最优化对策;纳什均衡解;算法;模型 组合最优化理论在国外已经发展了半个多世纪,而在我国是伴随着证券市场的发展而发展起来的,不过才二十年的时间。组合最优化对策是运用概率论、统计学、随机分析及最优化理论等数学工具,通过建立数学模型讨论市场规律对策的理论。 一、组合最优化对策的理论内涵 对策论,也称博弈论,是使用严谨的数学模型研究冲突对抗条件下最优决策问题的理论,它是运筹学的一个重要分支。对策论根据其所采用的假设不同而分为合作对策理论和非合作对策理论。前者主要强调的是团体理性;而后者主要研究人们在利益相互影响的局势中如何选择策略使得自己的收益最大,即策略选择问题,强调的是个人理性。非合作对策理论中,最重要、最核心的概念是纳什均衡。纳什均衡揭示了对策均衡与经济均衡的内在联系,它的策略组合由所有局中人的最佳策略组合构成,没有人会主动改变自己的策略以便使自己获得更大利益。 组合最优化对策是建立在组合最优化问题上的对策模型,分为组合最优化非合作对策和组合最优化合作对策。当局中人选取策略时不允许局中人之间互通信息,也不允许结伙,则成该对策为非合作对策。在非合作对策#=(N,{S i}i I N,{p i}i I N)中,N 为局中人集合,每个局中人i I N都有自己的策略集合S,i以及支付函数p i。非合作对策中最重要的概念是纳什均衡,它的策略组合由所有局中人的最佳策略组成,没有人会主动改变自己的策略以使自己获得更大的利益。如果对每个i I N,p i可以通过求解某个最优化问题得到,则称该对策为组合最优化非合作对策。如果允许局中人之间合作并联盟,这就导致了合作对策的研究。在合作对策#= (N,v)中,N为局中人的集合,v:2N y R为特征函数(v(U) =0),v(S)表示S作为合作整体可能达到的最大利益(S是N的子集)。如果v(S)可以通过求解S所确定的某个最优化问题得到,则称该对策为组合最优化合作对策。对分配的公平性和合理性的不同要求,导出了不同的分配概念)))对策的解的概念。 二、组合最优化对策的算法 在解决最优化问题时,算法的有效性往往是我们首要关心的问题。所谓有效算法,或称多项式算法,是指其基本运算步数由输入规模的多项式所界定的算法。例如,解线性规划问题的椭球算法,解指派问题的匈牙利方法等都是有效算法。然而,还有许多优化问题,如货郎担问题,顶点覆盖问题和可适定性问题等,它们的算法设计如此之难,以至于人们无法知道是否存在有效算法。 考虑最优化问题的判定形式-判定问题,即答案为/是0或/否0的问题1我们用P表示用多项式时间算法所能解决的判定问 149
练习题一 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、研究线性规划的对偶理论和方法（包括对偶规划模型形式、对偶理论和对偶单纯形法）。 答：略。
组合最优化问题最基本的特点就是变量是离散的, 由此导致其数学模型中的目标函数和约束函数在其可行域内是也是离散的。在现实世界中，许多的实际问题本质上是离散事件的而不是连续事件，都可归结为组合最优化问题。这类问题在理论上多数都属于NP难问题，NP类问题仍属于可计算问题，即存在算法来求解。求解这类组合最优化问题方法分为精确算法和近似算法两类。 常用的精确算法有动态规划、分支定界和枚举等。精确算法只能解决一些小规模问题，当求解小规模组合优化问题时可以用这类精确算法在较短的时间内得到最优解。当求解大规模组合优化问题时，理论上可以得到问题的最优解，但由于计算量太大，所以使用精确算法并不可行。利用精确算法求解NP-hard组合优化问题时，即使能得到最优解，但所需要的计算时间过长，在实际问题中难以直接应用。 近似算法是指在合理的计算时间内找到一个近似的最优解。近似算法虽然求解速度较快，但并不能保证得到问题的全局最优解。近似算法分为基于数学规划（最优化）的近似算法、启发式算法和基于智能优化的近似算法。 1) 基于数学规划（最优化）的近似算法是根据对问题建立的数学规划模型，运用如拉格朗日松弛、列生成等算法以获得问题的近似解，是以数学模型为基础，采用列生成、拉格朗日松弛和状态空间松弛等求解问题。 拉格朗日松弛（LR）算法求解问题的主要思想是分解和协调。首先对于NP难的优化问题，其数学模型须具有可分离性。通过使用拉格朗日乘子向量将模型中复杂的耦合约束引入目标函数，使耦合约束解除，形成松弛问题，从而分解为一些相互独立的易于求解的子问题，设计有效的算法求得所有子问题的最优解。利用乘子的迭代更新来实现子问题解的协调。列生成(Column generation, CG)算法是一种已经被认可的成功用于求解大规模线性规划、整数规划及混合整数规划问题的算法。 与智能优化算法相比，基于数学规划的近似算法的优点是通过建立问题的数学模型，松弛模型中难解的耦合约束或整数约束，得到的松弛问题的最优解可以为原问题提供一个下界。同时基于数学规划的近似算法还具有很好的自我评价功能，通过算法运行给出的问题的近优解(或最优解)为原问题提供一个上界，上界与下界进行比较，可以衡量算法的性能。 2) 启发式算法根据求解问题的特点，按照人们经验或某种规则设计的。这是一种构造式算法，比较直观、快速，利用问题的知识设计求解的方法步骤，相对比较简单，这种方法的求解速度较快，但所得解的质量不一定好。 3) 基于智能优化的近似算法是基于一定的优化搜索机制，并具有全局优化性能的一类算法。这类智能优化算法常见的有：模拟退火(SA)、遗传算法(GA)、蚁群算法(ACO)、路径重连算法(PR)、迭代局部搜索算法(ILS)、禁忌搜索算法(TS)、分散搜索算法(SS)、粒子群算法(PSO)等，这些算法也称超启发式算法(Meta-heuristic)。 智能优化算法是一种通用的算法框架，只要根据具体问题特点对这种算法框架结构进行局部修改，就可以直接应用它去解决不同的问题。这类算法本身不局限于某个框架，具有实践的通用性，适应于求解工业实际问题，能较快地处理大规模数据的同时得到令人满意的解。基于智能优化的近似算法，采用不同的搜索策略和优化搜索机制，寻找问题的近似最优解，具有很好的求解优势。虽然基于智能优化的近似算法不能保证求得全局最优解，但因其高效的优化性能、无需问题特殊信息、易于实现且速度较快等优点, 受到诸多领域广泛的关注和应用。基于智能优化的近似算法(超启发式算法)成为求解复杂组合最优化问题主要的有效方法。
龙源期刊网 https://www.doczj.com/doc/5514083899.html, 组合最优化与计算复杂性综述 作者：王继强 来源：《电脑知识与技术》2013年第13期 摘要：综合论述了组合最优化理论与计算复杂性理论，尤其是NP-完备理论之间的密切关系，揭示出NP-完备理论研究的重大理论和现实意义。 关键词：组合最优化；计算复杂性；NP-完备；近似算法 中图分类号：TP301.6 文献标识码：A 文章编号：1009-3044（2013）13-3140-02 1 组合最优化 经典数学主要研究问题的存在性，唯一性和稳定性等，很少涉及组合最优化问题，一个主要原因就是人们不具备有效的数值计算能力。科学技术的发展使得组合最优化的重要性日益显现出来，而计算机的产生与发展则使得人们的计算能力大大增强，从而为解决组合最优化问题提供了可能；同时，在计算机的发展过程中，人们又提出了不少亟待解决的组合最优化问题。由此可见，组合最优化与计算机科学是相辅相成，紧密联系的。 2 计算复杂性 如上所述，组合最优化就是要找到适用于计算机的计算方法。这一方法应普遍适用于问题包含的所有实例（instance），求出实例的解。这样的计算方法就是算法。算法是计算机科学的核心概念，被誉为计算机科学的“灵魂”。算法的优劣直接关系到软件乃至整个计算机系统的性能.。著名的方正排版软件系统就是基于新的更有效的算法设计的。 那么，评价一个算法是否有效的标准是什么呢？一般而言，理论计算机科学界普遍以算法的计算复杂性，即算法在最坏情形（worst case）下的运行时间作为评价其有效与否的标准。 然而，算法的运行时间与很多因素有关，如计算机的速度，问题的规模等。首先，我们假定算法是在“理想计算机”上运行的。理想计算机只能执行最基本的加、减、乘、除、大小比较等基本运算，且耗费的时间都是一个时间单位。因此，算法的运行时间常用算法所执行的基本运算的次数来表示。其次，一个待解决的问题的实例总是以一定的规模（size）输入计算机中的，如图和网络的顶点数和边数。因此，可设法估计出算法对规模为[n]的实例需执行的基本运算 的次数的一个上界[f（n）]，将函数[f（n）]作为该算法的计算复杂性[1-3]。 显然，即使对于同一个问题的实例，不同的算法的计算复杂性也是不同的。以下面的旅行售货员问题[1]为例：有[n]个城市，任两城市之间都有路相通。一售货员拟从他所在的城市到其它[n-1]个城市去售货。问：这个售货员应如何选择路线，才能经过每个城市恰好一次，再回到原地，且总路程最短？
用对偶单纯形法求对偶问题的最优解 摘要：在线性规划的应用中，人们发现一个线性规划问题往往伴随着与之配对的另一个线性规划问题.将其中一个称为原问题，另一个称为对偶问题.对偶理论深刻揭示了原问题与对偶问题的内在联系.由对偶问题引申出来的对偶解有着重要的经济意义.本文主要介绍了对偶问题的基本形式以及用对偶单纯形法求解对偶问题的最优解. 关键词：线性规划；对偶问题；对偶单纯形 Using Dual Simplex Method To Get The Optimal Solution Of The Dual Problem Abstract：In the application of the linear programming，people find that a linear programming problem is often accompanied by another paired linear programming problem.One is called original problem. Another is called the dual problem. Duality theory reveals the internal relations between the dual problem and the original problem. The solution of the dual problem is of a great economic significance. In this paper，we mainly discuss the basic form of the dual problem and how to use dual simplex method to get the optimal solution of the dual problem. Key words: linear programming；dual problem；dual simplex method 1 引言 首先我们先引出什么是线性规划中的对偶问题.任何一个求极大化的线性规划问题都有一个求极小化的线性规划问题与之对应，反之亦然，如果我们把其中一个叫原问题，则另一个就叫做它的对偶问题，并称这一对互相联系的两个问题为一对对偶问题.每个线性规划都有另一个线性规划(对偶问题)与它密切相关，对偶理论揭示了原问题与对偶问题的内在联系.下面将讨论线性规划的对偶问题的基本形式以及用对偶单纯形法求最优解.在一定条件下，对偶单纯形法与原始单纯形法相比有着显著的优点. 2 对偶问题的形式 对偶问题的形式主要包括对称形对偶问题[]3和非对称性对偶问题. 2.1对称形对偶问题 设原线性规划问题为 Max 1122... n n Z c x c x c x =+++
在管理科学、计算机科学、分子物理学和生物学以及超大规模集成电路(VLSI)设计、代码设计、图象处理和电子工程等科技领域中，存在着大量组合优化问题。其中许多问题如货郎担问题、图着色问题、设备布局问题以及布线问题等，至今没有找到有效的多项式时间算法。这些问题巳被证明是NP 完全问题[1]。 用最优算法如线性规划求NP 完全间题的最优解，需要问题规模的指数阶时间，在问题规模增大时，往往由于计算时间的限制而丧失可行性。用近似算法如贪心法求解NP 完全问题，在多项式界的时间里，只能给出近似最优解。 本章介绍组合优化问题和计算复杂性理论的基本概念，并结合几个组合优化的NP 完全问题实例，介绍其近似算法。最后，在引人邻域结构概念的基础上，介绍一种通用的近似算法—局部搜索算法。 §1组合优化问题 组合优化问题的目标是从组合问题的可行解集中求出最优解。本书研究那些可以用数学语言精确描述的组合优化问题，并假定其可行解集是有限的或可数无限的，同时解的质量可以量化，因而可以比较不同解间的质量差异。 1.1组合优化问题的基本概念 优化问题有三个基本要素:变量、约束和目标函数。在求解过程中选定的基本参数称为变量，对变量取值的种种限制称为约束，表示可行方案衡量标准的函数称为目标函数。 货郎担问题(TSP)是组合优化中最为著名的问题，它易于陈述而难于求解。自1932年K. Menger 提出以来，已引起许多数学家的兴趣，但至今尚未找到有效的求解方法。由于货郎担问题综合了一大类组合优化问题的典型特征，下面以它为例说明组合优化间题的基本概念。 例1.1货郎担问题(TSP) 给定n 个城市和每两个城市间的距离。一个货郎自某一城市出发巡回售货，问这个货郎应该如何选择路线，使每个城市经过一次且仅一次，并且路径长度最短。 设[]ij D d =是距离矩阵，其元素ij d 表示城市j i ,间的距离。则对变量D 的约束是： (1)每个元素是非负整数，即 0,0,ij d i j n ≥≤≤; (2)对角线上的元素为0，即 0,0ii d i n =≤≤; (3)是对称矩阵，即 ,0,ji ij d d i j n =≤≤; (4)任愈三个元素满足三角不等式，即 ,0,,i j j k i k d d d i j k n +≥≤≤; TSP 的一个解可表述为一个循环排列()12,,n ππππ= ，它也可表示为 1231n πππππ→→→→→ . 的一条路径，()1i i n π≤≤是该路径中第i 个经过的城市。显然，满足i j ππ≠，若i j ≠的解才是可行解。所有可行解的集合构成解空间S ，即S={n 个城市的所有循环排列},解空间的规模为()1! 2 n S -=。路径长 度 ()1 ,1 i i n i f d πππ +==∑（约定11n ππ+=） 是货郎担问题的目标函数。TSP 的目标是使路径长度最短，即使目标函数()f π最小。 下面给出组合优化问题的定义。 定义1.1 组合优化问题是在给定的约束条件下，求目标函数最优值(最小值或最大值)的问题。组合优化问题的一个实例可以表示为一个对偶(S, f )，其中解空间S 为可行解集，目标函数f 是一个映射，定义为 :f S R →. 求目标函数最小值的问题称为最小化向题，记为 () m i n ,f i i S ∈； （1.1.1） 求目标函数最大值的同题称为最大化间题，记为
《二维矩形条带装箱问题的底部左齐择优匹配算法_蒋兴波》matlab的实现，不包括遗传算法部分。function area = PackingAlgorithm(length,width,length1,width1,length2,width2,length3,width3,restrict1,restrict2) area = 0; frameCount = 1; count1 = 0; count2 = 0; runLLABF; function runLLABF rectBig.length = length; rectBig.width = width; rectSmall(1).length = length1; rectSmall(1).width = width1; rectSmall(1).color = 'r'; rectSmall(2).length = length2; rectSmall(2).width = width2; rectSmall(2).color = 'b'; rectSmall(3).length = length3; rectSmall(3).width = width3; rectSmall(3).color = 'g'; edges(1).x = 0; edges(1).y = 0; edges(1).length = rectBig.length; edges(2).x = -100; edges(2).y = 10000; edges(2).length = 0; edges(3).x = rectBig.length+100; edges(3).y = 10000; edges(3).length = 0; while(1) flag = -1; if(flag < 0)
山东大学 博士学位论文 几个组合优化问题的研究姓名：董振宁 申请学位级别：博士专业：运筹学与控制论指导教师：刘家壮 20040325
几个组合优化问题的研究 董振宁 （山东大学数学与系统科学学院，济南，２５０１００） 中文摘要 组合优化问题是运筹学中的一个重要分支，随着实践的不断发展，越来越多的新问题利用它的古典模型求解不再合适，比如最短路问题、最小费用流问题、运输问题等．因而需要对原来的古典模型进行改进，构造出新的组和优化模型，并为之设计算法．本文研究了组合优化问题中具有特殊限制的最短路问题、最小费用流同题和运输问题，共分为六章； 第一章绪论，首先介绍了组合优化问题的统一形式，由于现代大多数组合优化问题都是ⅣＰ—ｈａｒｄ的，因此我们接着介绍了ⅣＰ—ｈａｒｄ问题几种常见的处理方法，最后介绍了与本文有关的三类经典组合优化问题的模型及算法．设Ｆ是有限集，ｃ是Ｆ到实数集Ｒ的映射，即ｃ是定义在Ｆ上的一个函数．求＿，∈Ｆ，使得对于任意的Ｙ∈Ｆ，有 ｃ（Ｓ）≤ｃ（ｙ） 成立．。上述问题称为组合优化问题，简记为；求ｒａｉｎｃ（．厂） 早期的组合优化问题通常可以设计出一个方便快捷的算法求得其最优解，比如最小支撑树问题．随着实践的发展，人们遇到了很多组合优化问题都找不到多项式算法．人们将其称为ⅣＰ问题．后来，人们归结出了一类ⅣＰ—ｈａｒｄ问题，认为它们基本上不可能存在多项式时间算法．如果一个算法能够求得这些问题的最优解，则它的计算时间将会很长，以至于无法忍受．由于Ⅳ｜Ｐ—ｈａｒｄ问题无法设计出多项式算法，很多ⅣＰ—ｈａｒｄ问题又非常有应用价值，因而人们都在努力为其设计近似算法、启发式算法或者遗传算法．近似算法能够保证计算结果与最优结果相比较的差别不超过某一常数血，且Ｑ一般较小，但是算法比较复杂，在计算机上编程时比较困难；启发式算法算法通常很简单，很容易在计算机上实现，一般情况下也能够保证计算结果同最优结果差别不超过某一常数ｏ，但是ｎ相对于近似算法要大．也有一些启发式算法无法保证解的近似度，但计算结果通常都比较理想，如本文为
一．单纯性法 1.用单纯形法求解下列线性规划问题（共 15 分） 12212 1212max 25156224 ..5,0 z x x x x x s t x x x x =+≤??+≤?? +≤??≥? 2.用单纯形法求解下列线性规划问题（共 15 分） 12121212 max 2322 ..2210,0z x x x x s t x x x x =+-≥-?? +≤??≥? 3.用单纯形法求解下列线性规划问题（共 15 分） 1234123412341234max 24564282 ..2341,,,z x x x x x x x x s t x x x x x x x x =-+-+-+≤?? -+++≤??≥? 4.用单纯形法求解下列线性规划问题（共 15 分） 123123123 123123max 2360210 ..20,,0 z x x x x x x x x x s t x x x x x x =-+++≤??-+≤?? +-≤??≥? 5.用单纯形法求解下列线性规划问题（共 15 分） 12312312123 max 224..26,,0z x x x x x x s t x x x x x =-++++≤??+≤??≥? 6.用单纯形法求解下列线性规划问题（共 15 分） 121212max 105349 ..528z x x x x s t x x =++≤?? +≤?
7.用单纯形法求解下列线性规划问题（共 16 分） 12121212max 254212..3218,0z x x x x s t x x x x =+≤? ?≤?? +≤??≥?