课程报告题目最优化理论与方法 学生姓名 学号 院系 专业 二Ｏ一二年十一月十日
最优化理论与方法综述 最优化方法是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。这就是我理解的整个课程的流程。在这整个学习的过程当中，当然也会遇到很多的问题，不论是从理论上的还是从实际将算法编写出程序来解决一些问题。下面给出学习该课程的必要性及结合老师讲解以及在作业过程中遇到的问题来阐述自己对该课程的理解。 20世纪40年代以来，由于生产和科学研究突飞猛进地发展，特别是电子计算机日益广泛应用，使最优化问题的研究不仅成为一种迫切需要，而且有了求解的有力工具。因此最优化理论和算法迅速发展起来，形成一个新的学科。至今已出现线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分文。 最优化理论与算法包括线性规划单纯形方法、对偶理论、灵敏度分析、运输问题、内点算法、非线性规划K-T条件、无约束最优化方法、约束最优化方法、参数线性规划、运输问题、线性规划路径跟踪法、信赖域方法、二次规划路径跟踪法、整数规划和动态规划等内容。 最优化理论所研究的问题是讨论在众多的方案中什么样的方案最优以及怎样找出最优方案。这类问题普遍存在。例如，工程设计中怎样选择设计参数，使得设计方案满足设计要求，又能降低成本；资源分配中，怎样分配有限资源，使得分配方案既能满足各方面的基本要求，又能获得好的经济效益；生产评价安排中，选择怎样的计划方案才能提高产值和利润；原料配比问题中，怎样确定各种成分的比例，才能提高质量，降低成本；城建规划中，怎样安排基本单位的合理布局，才能方便群众，有利于城市各行各业的发展；农田规划中，怎样安排各种农作物的合理布局，才能保持高产稳产，发挥地区优势；军事指挥中，怎样确定最佳作战方案，才能有效地消灭敌人，保存自己，有利于战争的全局；在人类活动的各个领域中，诸如此类，不胜枚举。最优化这一数学分支，正是为这些问题的解决，提供理论基础和求解方法，它是一门应用广泛、实用性强的学科。 一、最优化学习的必要性 最优化，在热工控制系统中应用非常广泛。为了达到最优化目的所提出的各种求解方法。从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大，或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。
线性规划的对偶原理 3.1 线性规划的对偶问题 一、 对偶问题的提出 换位思考 家具厂的线性规划问题，该问题站在家具厂管理者的角度追求销售收入最大 213050max x x z += ?? ? ??≥≤+≤+0 ,50212034212121x x x x x x 某企业家有一批待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。他 需要与家具厂谈判付给该厂每个工时的价格。如果该企业家已对家具厂的经营情况有详细了 解，他可以构造一个数学模型来研究如何才能既让家具厂觉得有利可图，肯把资源出租给他， 又使自己付的租金最少。 目标:租金最少；1y -付给木工工时的租金；2y -付给油漆工工时的租金 2150120min y y w += 所付租金应不低于家具厂利用这些资源所能得到的利益 1）支付相当于生产一个桌子的木工、油漆工的租金应不低于生产一个桌子的收 入 502421≥+y y 2）支付相当于生产一个椅子的木工、油漆工的租金应不低于生产一个椅子的收 入 30321≥+y y 3）付给每种工时的租金应不小于零 0,021≥≥y y 二、 原问题与对偶问题的数学模型 1. 对称形式的对偶
原问题和对偶问题只含有不等式约束时，一对对偶问题的模型是对称的，称为对称形式的对偶。 原问题： ?? ? ??≥≥=0min X b AX CX z 对偶问题： ?? ? ??≥≤=0max Y C YA Yb w 2. 非对称形式的对偶 若原问题的约束条件全部是等式约束（即线性规划的标准型），即 ?? ? ??≥==0min X b AX CX z 则其对偶问题的数学模型为 ?? ? ??≤=是自由变量Y C YA Yb w max 可把原问题写成其等价的对称形式： min z =CX AX ≥b AX ≤b X ≥0 即 min z =CX ? ? ????-A A X ≥??????-b b X ≥0 设Y 1=(y 1,y 2,…,y m ), Y 2=(y m+1,y m+2,…,y 2m )。根据对称形式的对偶模型，写出上述问题的对偶问题：
线性规划原问题与对偶问题的转化及其应用 摘要 线性规划对偶问题是运筹学中应用较广泛的一个重要分支，它是辅助人们进行科学管理的一种数学方法.线性规划对偶问题能从不同角度为管理者提供更多的科学理论依据，使管理者的决定更加合理准确.本文主要探讨了线性规划原问题与对偶问题之间的关系、线性规划原问题与对偶问题的转化以及对偶理论的应用.本文的研究主要是将复杂的线性规划原问题转化成对偶问题进行解决，简化了线性规划问题，使人们能够快速的找出线性规划问题的最优解. 关键词：线性规划；原问题；对偶问题；转化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期
优化理论与方法
全局及个性化web服务组合可信度的动态规划评估方法 摘要：随着Internet的快速发展,web服务作为一种软件构造形式其应用越来越广泛。单个web服务无法满足日益复杂的用户需求,web服务组合有效地解决了这个问题。然而,随着功能相似的web服务实例的不断出现,如何选择可信的web服务组合成为了人们关注的热点。服务选择依赖于web服务组合的评估结果,因此,本文主要从web服务组合着手,对其可信性进行研究,提供一种可信web服务组合评估方法。：针对web服务组合的全局及个性化问题,提出了基于全局的个性化web服务组合可信评估方法。从全局角度动态地调整评估模型;同时引入用户业务关注度来描述原子web服务对服务组合可信性的影响程度;结合前文的度量及评估方法,构建一个全局的个性化服务组合可信评估模型;并分析了模型的相关应用,给出了改进的动态规划模型。 关键字：web服务组合可信评价；全局个性化；动态规划； 0.引言 随着软件系统规模的日趋复杂，运行环境的不断开放，软件的可信性要求日益增加，可信软件成为了研究的热点。据《中国互联网发展状况统计报告》统计显示，截至2014年12月底，我国网民数量突破8亿，全年新增网民5580万。互联网普及率较上年底提升4个百分点，达到38。3%。因此，随着Internet 的广泛应用和网络技术的快速发展，面向服务的软件体系结构（SOA）作为一种新型的网络化软件应用模式已经被工业界和学术界广为接受。同时，网民对互联网电子商务类应用稳步发展，网络购物、网上支付、网上银行和在线旅游预订等应用的用户规模全面增长。因而，对web服务的可信性要求更高。单个web服务的功能有限，往往难以满足复杂的业务需求，只有通过对已有web服务进行组合，才能真正发挥其潜力。在现有的web服务基础上，通过服务组装或者Mashup方式生成新web服务作为一种新型的软件构造方式，已成为近年的研究热点之一。web服务组合并不是多个原子web服务的简单累加，各原子web服务之间有着较强的联系。因此对web服务组合的可信需求更高。目前大量的研究工作着重于如何实现原子web服务间的有效组合，对服务组合的可信评估研究较少。如今，随着web服务资源快速发展，出现了大量功能相同或相似的web服务，对web服务组合而言，选择可信的web服务变得越来越难。在大量的功能相似的原子web服务中，如何选出一组可信的web服务组合，成为了人们关注的热点问题。本文将从web服务组合着手，对其可信性进行研究，旨在提供一种可信web服务组合评估方法，为web服务组合的选择提供依据。web服务组合的可信度主要包括以下三个部分： 1）基于领域本体的web服务可信度量模型。 2）基于偏好推荐的原子web服务可信评估方法。 3）基于全局的个性化web服务组合可信评估方法。 研究思路： 本文主要研究基于全局的个性化web服务组合的可信评估方法，其研究思路可以大致如下：基于领域本体的web服务可信度和基于偏好推荐的原子web 服务可信评估方法。针对web服务组合的四种基本组合结构模式，主要研究如
最优化原理与方法复习 第1章最优化问题的基本概念§最优化的概念最优化就是依据最优化原理和方法，在满足相关要求的前提下，以尽可能高的效率求得工程问题最优解决方案的过程。§最优化问题的数学模型 1.最优化问题的一般形式?findx1,x2,?,xn?minf(x,x,?,x)?12 n? (x,x,?,x)?0u?1,2,?,pu12n??hv(x1,x2,?,xn)? 0v?1,2,?,q? 2.最优化问题的向量表达式?findX?minf(X)?? (X)?0??H(X)?0?式中：X?[x1,x2,?,xn]T G(X)?[g1(X),g2(X),?,gp(X)]T H(X)?[h1(X),h2(X),?,hp(X)]T 3.优化模型的三要素设计变量、约束条件、目标函数称为优化设计的三要素！设计空间：设计变量所确定的空间。设计空间中的每一个点都代表一个设计方
案。§优化问题的分类按照优化模型中三要素的不同表现形式，优化问题有多种分类方法：1按照模型中是否存在约束条件，分为约束优化和无约束优化问题2按照目标函数和约束条件的性质分为线性优化和非线性优化问题3按照目标函数个数分为单目标优化和多目标优化问题4按照设计变量的性质不同分为连续变量优化和离散变量优化问题第2章最优化问题的数学基础§n元函数的可微性与梯度一、可微与梯度的定义1.可微的定义设f(X)是定义在n维空间Rn的子集D上的n元实值函数，且X0?D。若存在n维向量L，对于任意n维向量P，都有f(X0?P)?f(X0)?LTPlim?0 P?0P则称f(X)在X0处可微。 2.梯度设有函数F(X)，X?[x1,x2,?,xn]T，在其定义域内连续可导。我们把F(X)在定义域内某点X处的所有一阶偏导数构成的列向量，定义为F(X)在点X处的梯度。记
《优化原理与方法》作业解答要点 5.1 建造一容积为V (m 3)的长方形蓄水池（无盖），要求选择其长、宽、高，使表面积最小，从而建筑用料最省。试写出此问题的数学模型。 [解] 选择设计变量x 1、x 2、x 3分别代表蓄水池的长、宽、高，优化数学模型为： 5.2 某公司有资金a 万元，可供选择购置的设备有n 种，已知相应于第i 种设备所需资金为 b i 万元，可得收益为 c i 万元，要求收益最大的投资安排。试写出其数学模型。 [解] 选择设计变量x 1、x 2、…、x n 分别代表n 种可选购设备的购买数量，优化数学模型为： 5.3 某城市要建造一供应服务中心，向该市m 个用户提供服务，设第i 个用户的位置为（a i ， b i ），需要货物量为w i 吨，试寻求这个中心最经济的位置，使运输量（吨公里数）最小。 [解] 选择设计变量x 1、x 2代表中心的位置坐标，优化数学模型为： ?? ?? ? ?? ? ? ≥≥≥=??++= t..s 22 .min ],,[ 3min 32min 21min 1321313221321x x x x x x V x x x x x x x x x x x x T 使得寻求x ????? ? ???? ?? ? ?=?=≥≤?=∑∑==n i x n i x a x b x c x x x i i n i i i n i i i T n ,1,2, , ,1,2, ,0 t..s .max ] , ,,[ 1 1 21为整数使得寻求x ?? ??? -+-=∑=m i i i i T b x a x w x x 1222121)()( .min ],[ 使得寻求x
第3章 对偶理论 §3.1 线性规划的对偶理论 3.1.1 对偶问题的表述 对称形式的对偶： （L ） cx min (D) wb max s.t. b Ax ≥ s.t. c wA ≤ 0≥x 0≥w 其中c 为n 维行向量，A 为n m ?矩阵，b 为m 维列向量，x 表示n 维列向量，w 表示m 维行向量。 称(D)为线性规划(L)的对偶规划问题。 定理1 (L)与(D)互为对偶规划问题。――（对合性） 例 设原问题 对偶问题 , 1 2 5 s.t.min 2121212 1≥≥-≥+-x x x x x x x x 0, 12 1 s.t.5 max 21212121≥-≤-≤++w w w w w w w w 非对称形式的对偶： （LP ） cx min (DP) wb max s.t. b Ax = s.t. c wA ≤ 0≥x 例 设原问题 对偶问题 ,, 5 23 4 s.t.345min 3213213213 21≥=++=++++x x x x x x x x x x x x 3 42 53 s.t.54 max 21212121≤+≤+≤++w w w w w w w w 一般线性规划问题： 可化为上述二者之一讨论其对偶问题，也可直接写出对偶问题，详细的对应法则见教材（陈宝林）124页。
直接写出对偶的弊端之一是对偶最优解不易确定，而对称形式和非对称形式对偶的最优解都可由原问题的单纯形乘子确定出来。 3.1.2 对偶定理(强对偶定理和弱对偶定理) 定理2 (弱对偶定理)：设x 和w 分别是 （L ） cx min 和 (D) wb max s.t. b Ax ≥ s.t. c wA ≤ 0≥x 0≥w 的可行解，则有下列不等式成立： b w x c ≥ 证明：由于b x A ≥和0≥w ，则有b w x A w ≥。 由于A w c ≥和0≥x ，则有x A w x c ≥。 因此有b w x c ≥ 推论 1 设x 和w 分别是(L)和(D)的可行解，且有b w x c =，则x 和w 分别是(L)和(D)的最优解。 推论2 如果(L)的目标函数在可行集上无下界，则对偶规划(D)无可行解。 推论3 如果(D)的目标函数在可行集上无上界，则原始规划(L)无可行解。 定理3 (强对偶定理)：如果互为对偶规划的两个问题之一有最优解，则另一个问题也有最优解，并且二者的目标值相等。 证明：设原问题（L ）存在最优解，引进松弛变量，写成等价形式： s.t. min ≥≥=-v x b v Ax cx （1） 由于（1）存在最优解，因此可以用单纯形方法求出它的一个最优基本可行解，不妨设该最优解是?? ????=v x y ，相应的最优基是B 。此时所有判别数均非正，即 j c p w j j ?≤- ,0 （2） 1-=B c w B 为单纯形乘子。
中南大学考试试卷 2011--2012学年 1 学期 时间100分钟 最优化理论与方法 课程 48 学时 学分 考试形式： 闭 卷 专业年级： 信科08、应数08 总分100分，占总评成绩 70 % 注：此页不作答题纸，请将答案写在答题纸上,可用中英文作答。 1.（15 points ） For an unconstrained optimization problem: ),(min x f Let )0(x be a given point, )0(d be a descent search direction at )0(x . (1) With the exact line search, show that there is a steplength 0α satisfying .0)()0()0(0)0(=+?d d x f T α (2)Show that when applied to a quadratic objective function, the Newton method with the exact line search terminates in at most one iteration. 2. （15 points ）For an unconstrained optimization problem: .2)(min 2 221x x x f += (1) Find a descent direction )0(d of f at .)1,1() 0(T x = (2) By the Armijo line search, find a steplength 0α along )0(d at .)0(x 3.（15 points ） （1）Let .2113???? ??=A Find two directions 1d and 2d such that 1d and 2d are conjugate with respect to the matrix A . （2）Show that when applied to a quadratic objective function, with the exact line search, the PRP conjugate gradient method is equivalent to the FR conjugate gradient method.
第二章线性规划的对偶理论 2.1 写出下列线性规划问题的对偶问题 max z=2x1+2x2－4x3 x1 + 3x2 + 3x3 ≤30 4x1 + 2x2 + 4x3≤80 x1、x2，x3≥0 解：其对偶问题为 min w=30y1+ 80y2 y1+ 4y2≥2 3y1 + 2y2 ≥2 3y1 + 4y2≥－4 y1、y2≥0 2.2 写出下列线性规划问题的对偶问题 min z=2x1+8x2－4x3 x1 + 3x2－3x3 ≥30 －x1 + 5x2 + 4x3 = 80 4x1 + 2x2－4x3≤50 x1≤0、x2≥0，x3无限制 解：其对偶问题为 max w=30y1+80 y2+50 y3 y1－y2 + 4 y3≥2 3y1+5y2 + 2y3≤8 －3y1 + 4y2－4y3 =－4 y1≥0，y2无限制，y3≤0 2.3已知线性规划问题 max z=x1+2x2+3x3+4x4 x1 + 2x2 + 2x3 +3x4≤20 2x1 + x2 + 3x3 +2x4≤20 x1、x2，x3，x4≥0 其对偶问题的最优解为y1*=6/5，y2*=1/5。试用互补松弛定理求该线性规划问题的最优解。 解：其对偶问题为
min w=20y1+ 20y2 y1 + 2y2≥1 （1） 2y1 + y2 ≥2 （2） 2y1 +3y2≥3 （3） 3y1 +2y2≥4 （4） y1、y2≥0 将y1*=6/5，y2*=1/5代入上述约束条件，得（1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。又因y1*>0，y2*>0，故原问题的两个约束条件应取等式，所以 2x3*+3x4* = 20 3x3* +2x4* = 20 解得x3* = x4* = 4。故原问题的最优解为 X*=（0，0，4，4）T 2.4用对偶单纯形法求解下列线性规划 min z=4x1+2x2+6x3 2x1 +4x2 +8x3 ≥24 4x1 + x2 + 4x3≥8 x1、x2，x3≥0 解将问题改写成如下形式 max（－z）=－4x1－2x2－6x3 －2x1－4x2 －8x3 + x4=－24 －4x1－x2－4x3+x5 =－8 x1、x2，x3，x4，x5≥0 显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正侧基。整个问题的计算过程列在表2—7中。
内点法基本原理 摘要：内点法是求解含不等式约束最优化问题的一种十分有效的算法。内点法通过构造障碍函数，求解一系列只含等式约束最优化问题，逐步得到原问题的最优解，具有找初始点容易、线性收敛、迭代次数少等特点。本文主要介绍了内点法的基本原理，障碍方法的一般步骤并分析了该方法的优缺点，进行了算例实践。 关键词：内点法；障碍方法；Newton法 The Theory of Interior Point Method Abstract: Interior point method is a very effective algorithm for solving optimization problems with inequality constrained. Interior point method is constructed to solve a series of optimization problems with equality constraints, and the optimal solution of the original problem is obtained, which has the characteristics of finding the initial point easier, linear convergence, less iteration number and so on. This paper mainly introduces the theory of interior point method, the general steps of barrier method and analyzing the advantages and disadvantages of the method. Key words: interior point method; barrier method;Newton method
线性规划的对偶问题文稿归稿存档编号：[KKUY-KKIO69-OTM243-OLUI129-G00I-FDQS58-
第二章线性规划的对偶问题 习题 2.1 写出下列线性规划问题的对偶问题 (1) max z ＝10x1＋ x2＋2x3 (2) max z ＝2x1＋ x2＋3x3＋ x4 st. x1＋ x2＋2 x3≤10 st. x1＋ x2＋ x3 ＋ x4≤5 4x1＋ x2＋ x3≤20 2x1－ x2＋3x3＝－4 x j≥0 （j＝1,2,3） x1－ x3＋ x4≥1 x1，x3≥0，x2，x4无约束 (3) min z ＝3x1＋2 x2－3x3＋4x4 (4) min z ＝－5 x1－6x2－7x3 st. x1－2x2＋3x3＋4x4≤3 st. －x1＋5x2－3x3≥15 x2＋3x3＋4x4≥－5 －5x1－6x2＋10x3≤20 2x1－3x2－7x3 －4x4＝2＝ x1－ x2－ x3＝－5 x1≥0，x4≤0，x2，，x3无约束 x1≤0， x2≥0，x3无约束 2.2 已知线性规划问题max z＝CX，AX=b，X≥0。分别说明发生下列情况时，其对偶问题的解的变化： （1）问题的第k个约束条件乘上常数λ（λ≠0）； （2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上；（3）目标函数改变为max z＝λCX（λ≠0）； （4）模型中全部x1用3 'x代换。 1 2.3 已知线性规划问题min z＝8x1＋6x2＋3x3＋6x4 st. x1＋2x2＋ x4≥3 3x1＋ x2＋ x3＋ x4≥6
x3 ＋ x4＝2 x1 ＋ x3 ≥2 x j≥0（j＝1,2,3,4） (1) 写出其对偶问题； (2) 已知原问题最优解为x*＝（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。 2.4 已知线性规划问题min z＝2x1＋x2＋5x3＋6x4 对偶变量 st. 2x1 ＋x3＋ x4≤8 y1 2x1＋2x2＋x3＋2x4≤12 y2 x j≥0（j＝1,2,3,4） 其对偶问题的最优解y1*=4；y2*=1，试根据对偶问题的性质，求出原问题的最优解。 2.5 考虑线性规划问题max z＝2x1＋4x2＋3x3 st. 3x1＋4 x2＋2x3≤60 2x1＋ x2＋2x3≤40 x1＋3x2＋2x3≤80 x j≥0 （j＝1,2,3） （1）写出其对偶问题 （2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解； （3）用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解； （4）比较（2）和（3）计算结果。
《最优化理论与方法》讲义 (上) 第一章绪论 1.1 学科简介 最优化这一数学分支，为这些问题的解决提供了理论基础和求解方法。最优化就是在一切可能的方案中选择一个最好的方案以达到最优目标的学科。 1.1.1 优化的含义 优化是从处理各种事物的一切可能的方案中，寻求最优的方案。 （1）来源：优化一语来自英文Optimization，其本意是寻优的过程； （2）优化过程：是寻找约束空间下给定函数取极大值（以max 表示)或极小(以min表示)的过程。 1.2 发展概况 第一阶段—人类智能优化 第二阶段—数学规划方法优化 第三阶段—工程优化 第四阶段—现代优化方法 1.3研究意义 研究意义：最优化在本质上是一门交叉学科，它对许多学科产生了重大影响，并已成为不同领域中很多工作都不可或缺的工具。 应用范围：信息工程及设计、经济规划、生产管理、交通运输、
国防工业以及科学研究等诸多领域。 总之，它是一门应用性相当广泛的学科，讨论决策的问题具有最佳选择之特性。它寻找最佳的计算方法，研究这些计算方法的理论性质及其实际计算表现。 1.4 示例 例1 资源分配问题 某工厂生产A 和B 两种产品，A 产品单位价格为A P 万元，B 产品单位价格为B P 万元。每生产一个单位A 产品需消耗煤C a 吨，电E a 度，人工L a 个人日；每生产一个单位B 产品需消耗煤C b 吨，电E b 度，人工L b 个人日。现有可利用生产资源煤C 吨，电E 度，劳动力L 个人日，欲找出其最优分配方案，使产值最大。分析：(1)产值的表达式；(2)优化变量确定：A 产品A x ，B 产品B x ；(3)优化约束条件： ①生产资源煤约束； ②生产资源电约束； ③生产资源劳动力约束。 例2 指派问题 设有四项任务1B 、2B 、3B 、4B 派四个人1A 、2A 、3A 、4A 去完成。每个人都可以承担四项任务中的任何一项，但所消耗的资金不同。设 i A 完成j B 所需资金为ij c 。如何分配任务，使总支出最少? 分析：设变量?????=任务完成不指派， 任务完成指派j j i ij B A B A x 0,1
《最优化原理与方法》复习题 一．美佳公司计划制造 I 、II 两种家电产品。已知各制造一件时分别占用设备 A 、B 的台时、调试时间、调试工序每天可用于这种家电的能力、各售出一件时的获利情况，如下表所示。 （1）试写出上述问题的数学规划模型； （2）给出求解该模型的lingo 代码。 二．将下列线性规划化为标准型，并列出初始单纯形表。 12341234123412341234min 3425, s.t. 4 22, 314, 2322, ,,0,; y x x x x x x x x x x x x x x x x x x x x =-+-+-+-=-++-≤-+-+≥≥无约束 三．已知线性规划问题 ; ,0,0, ,209 9912 ,85376 ,5 3 s.t. ,432 max 43214321432143214321无约束x x x x x x x x x x x x x x x x x x x x ≤≥≤+--≥-++=--+-+++ 写出其对偶规划。 四．试选用一种方法求解下述线性规划问题 ; 0, , , 623 ,824 s.t. ,32min 32121321321≥≥+≥++++=x x x x x x x x x x x z
五. 用表格单纯形法求解线性规划。 . 0,, ,224 ,222 s.t. ,max 321321321321≥≤++≤++++=x x x x x x x x x x x x z 六. 已知线性规划问题 ; 0, ,3 ,1423 ,42 s.t. ,23max 2121212121≥≤-≤+≤+-+=x x x x x x x x x x z （1） 写出对偶问题； （2） 应用对偶理论证明原问题与对偶问题都存在最优解(不必求解)。 七.已知线性规划问题 . ,0,0 6 ,4 s.t. ,22 min 32132132321无约束x x x kx x x x x x x x x ≥≤≤-+-=++-+- 其最优解为.1,0,5321-==-=x x x 试求 （1）k 的值 （2）写出对偶问题并求其最优解 八．已知线性规划问题 . 0,,, 20232 ,20322 s.t. , 432max 4321432143214321≥≤+++≤++++++=x x x x x x x x x x x x x x x x z 其对偶问题的最优解为.2.0,2.1* 2*1==w w 试根据对偶理论求出原问题的最优解
第二章线性规划的对偶问题 习题 2.1 写出下列线性规划问题的对偶问题 (1) max z ＝10x1＋x2＋2x3(2) max z ＝2x1＋x2＋3x3＋x4 st. x1＋x2＋2 x3≤10 st. x1＋x2＋x3 ＋x4≤5 4x1＋x2＋x3≤20 2x1－x2＋3x3＝－4 x j≥0 （j＝1,2,3）x1－x3＋x4≥1 x1，x3≥0，x2，x4无约束 (3) min z ＝3x1＋2 x2－3x3＋4x4(4) min z ＝－5 x1－6x2－7x3 st. x1－2x2＋3x3＋4x4≤3 st. －x1＋5x2－3x3≥15 x2＋3x3＋4x4≥－5 －5x1－6x2＋10x3≤20 2x1－3x2－7x3 －4x4＝2＝x1－x2－x3＝－5 x1≥0，x4≤0，x2，，x3无约束x1≤0，x2≥0，x3无约束 2.2 已知线性规划问题max z＝CX，AX=b，X≥0。分别说明发生下列情况时，其对偶问题的解的变化： （1）问题的第k个约束条件乘上常数λ（λ≠0）； （2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上； （3）目标函数改变为max z＝λCX（λ≠0）； 'x代换。 （4）模型中全部x1用3 1 2.3 已知线性规划问题min z＝8x1＋6x2＋3x3＋6x4 st. x1＋2x2＋x4≥3 3x1＋x2＋x3＋x4≥6 x3 ＋x4＝2 x1 ＋x3 ≥2 x j≥0（j＝1,2,3,4） (1) 写出其对偶问题； (2) 已知原问题最优解为x*＝（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。 2.4 已知线性规划问题min z＝2x1＋x2＋5x3＋6x4 对偶变量 st. 2x1 ＋x3＋x4≤8 y1 2x1＋2x2＋x3＋2x4≤12 y2 x j≥0（j＝1,2,3,4） 其对偶问题的最优解y1*=4；y2*=1，试根据对偶问题的性质，求出原问题的最优解。 ４７
对偶理论的性质及证明 性质1(对称性) 对偶问题的对偶问题是原问题 证明 设原问题为 max z ..0CX AX b s t X =≤??≥? (1) 对偶问题为 min ..0w Yb YA C s t X =≥??≥? (2) 对偶问题的对偶问题为 max ..0CU AU b s t U ?=≤??≥? (3) 比较式(1)和式(3), 显然二者是等价的, 命题得证. 性质2(弱对偶性) 设原问题为式(1),对偶问题为式(2),X 是原问题的任意一 个可行解,Y 是对偶问题的任意一个可行解,那么总有 CX Yb ≤ (4) 证明 根据式(1), 由于AX b ≤, 又由于0Y ≥, 从而必有 YAX Yb ≤ (5) 根据式(2), 由于YA c ≥, 又由于0X ≥, 从而必有 YAX CX ≥ (6) 结合式(5)和式(6), 立即可得CX Yb ≤,命题得证. 性质3(最优性) 设*X 原问题式(1)的可行解,*Y 是对偶问题式(2)的可行解,当 是**CX Y b =时,*X 是原问题式(1)的最优解,*Y 是对偶问题式(2)的最优解. 证明 设X 是式(1)的最优解, 那么有 *CX CX ≥ (7) 由于**CX Y b =,那么 *CX Y b ≥ (8) 根据弱对偶性质, 又有 *CX Y b ≤ (9)
从而*CX CX =, 也就是*X 是原问题式(1)的最优解。 同理，也可证明*Y 是对偶问题式(2)的最优解。 性质4(无界性) 设原问题为无界解，则对偶问题无解。 证明 用反证法证明。 设原问题为式(1)，对偶问题为式(2)。 假定对偶问题有解，那么存在一个可行解为Y 。这时对偶问题的目标函数值为Yb T =。 由于原问题为无界解，那么一定存在一个可行解X 满足CX T >，因此CX Yb >。 而根据弱对偶性，又有CX Yb ≤，发生矛盾。从而对偶问题没有可行解。 性质5(强对偶性、对偶性定理) 若原问题有最优解，那么对偶问题也有最优解， 且最优目标函数值相等。 证明 设B 为原问题式(1)的最优基，那么当基为B 时的检验数为1B C C B A --，其中B C 为由基变量的价值系数组成的价值向量。 既然B 为原问题式(1)的最优基，那么有10B C C B A --≤。 令1B Y C B -=，那么有0C YA YA C -≤?≥，从而1B Y C B -=是对偶问题式(2)的可行解。 这样一来，1B Y C B -=是对偶问题的可行解，1B X B b -=是原问题的最优基可行解。 由于1B B N N B CX C X C X C B b -=+=，而1B Y b C B b -=，从而有CX Yb =。根据性质3，命题得证。 性质6(对偶松弛定理、松弛性) 若??, X Y 分别是原问题和对偶问题的可行解，那么?0s YX =和?0s Y X =，当且仅当??, X Y 为最优解。 证明 设原问题和对偶问题的标准型是 原问题 对偶问题 max z ..0CX AX b s t X =≤??≥? min ..0w Yb YA C s t X =≥??≥? 将原问题目标函数中的系数向量C 用s C YA Y =-代替后，得到 ()s s Z CX YA Y X YAX Y X ==-=- (10) 将对偶问题的目标函数中系数列向量，用s b AX X =+代替后，得到 ()s s Yb Y AX X YAX YX ω==+=+ (11) 若?0s YX =，?0s Y X =，则????CX YAX Yb ==，由最优性可知??, X Y 分别是原问题和对偶问题的最优解。 又若??, X Y 分别是原问题和对偶问题的可行解，再根据最优性，则有??CX Yb =
最优化理论与方法心得体会 摘要：最优化方法作为研究各种系统的优化途径及方案，为决策者提供科学决策的依据。该文简单叙述了最优化方法及其处理问题的步骤和在各领域的应用，在一个学期的自学，讨论的课程之后，总结对最优化问题的理解和认识，思考优化理论在现实生活的应用，如何解决实际问题，以及自我学习过程的感想与实践。 关键字：优化；应用；感想
在生产过程、科学实验以及日常生活中，人们总希望用最少的人力、物力、财力和时间去办更多的事，获得最大的效益，在管理学中被看作是生产者的利润最大化和消费者的效用最大化，如果从数学的角度来看就被看作是“最优化问题”。在最优化的研究生教学中我们所说的最优化问题一般是在某些特定的“约束条件”下寻找某个“目标函数”的最大(或最小)值，其解法称为最优化方法。最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。本章将介绍最优化方法的研究对象、特点，以及最优化方法模型的建立和模型的分析、求解、应用。主要是线性规划问题的模型、求解（线性规划问题的单纯形解法）及其应用――运输问题；以及动态规划的模型、求解、应用――资源分配问题。简单点，从数学意义上说从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。不同类型的最优化问题可以有不同的最优化方法，即使同一类型的问题也可有多种最优化方法。反之,某些最优化方法可适用于不同类型的模型。最优化问题的求解方法一般可以分成解析法、直接法、数值计算法和其他方法。 ①解析法：这种方法只适用于目标函数和约束条件有明显的解析表达式的情况。求解方法是：先求出最优的必要条件，得到一组方程或不等式，再求解这组方程或不等式，一般是用求导数的方法或变分法求出必要条件，通过必要条件将问题简化，因此也称间接法。②直接法：当目标函数较为复杂或者不能用变量显函数描述时，无法用解析法求必要条件。此时可采用直接搜索的方法经过若干次迭代搜索到最优点。这种方法常常根据经验或通过试验得到所需结果。对于一维搜索(单变量极值问题)，主要用消去法或多项式插值法；对于多维搜索问题(多变量极值问题)主要应用爬山法。③数值计算法：这种方法也是一种直接法。它以梯度法为基础，所以是一种解析与数值计算相结合的方法。④其他方法：如网络最优化方法等。