最优化线性规划 (1)(1)

线性规划解决最优化问题的数学方法线性规划是一种常见的数学方法，用来解决最优化问题。

它能够帮助我们在给定一组线性约束条件下，找到最优的目标函数值。

在实际应用中，线性规划方法被广泛用于制定优化决策、资源配置、生产计划等领域。

本文将介绍线性规划的基本概念、公式以及解决最优化问题的具体步骤。

一、线性规划的基本概念与公式线性规划的目标是在给定约束条件下，找到使目标函数（也称为优化函数）取得最大或最小值的解。

它包含三个基本要素：决策变量、约束条件和目标函数。

1. 决策变量：决策变量是问题中需要确定的变量，它们可以是实数、整数或布尔变量。

决策变量的取值范围和类型由问题的实际情况决定。

2. 约束条件：约束条件是对决策变量的限制条件，它们可以是线性等式或不等式。

约束条件用于描述问题的限制条件，例如资源约束、技术限制等。

3. 目标函数：目标函数是求解问题的目标，它可以是最小化或最大化一个线性函数。

目标函数的形式通常是关于决策变量的线性组合。

线性规划问题可以用如下的标准形式表示：最小化 Z = c₁x₁ + c₂x₂ + ... + cₙxₙ约束条件：a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂...aₙ₁x₁ + aₙ₂x₂ + ... + aₙₙxₙ ≤ bₙ非负约束：x₁ ≥ 0, x₂ ≥ 0, ... , xₙ ≥ 0其中，Z为目标函数值，c₁, c₂, ... , cₙ为目标函数的系数，aᵢₙ为约束条件的系数，b₁, b₂, ... , bₙ为约束条件的常数项，x₁, x₂, ... , xₙ为决策变量。

二、线性规划的解决步骤解决线性规划问题一般可以遵循以下步骤：1. 定义问题：明确问题的目标函数、约束条件和决策变量，并将其转化为标准形式。

2. 建立数学模型：根据问题的实际情况，根据标准形式建立数学模型，将问题转化为求解目标函数最大或最小值的数学问题。

【最优化】线性规划基本概述什么是线性规划：线性规划就是特殊的有约束优化问题，⽬的是通过⼀组线性等式或者不等式下得可⾏集合点，来寻找⼀个⽬标函数的极值；通常来说，极值可以是极⼤极⼩，但是⼀般采⽤极⼩，看到相关的案例，求极⼤值直接前⾯加负号变为极⼩值即可；线性规划的基本问题形式：线性规划问题可以采⽤最基本的数学符号进⾏描述：minimize c T xsubject to Ax=bx>=0;对于上述可以这样理解，对于某个参数向量x，所满⾜的可⾏域条件为Ax=b，也成为约束⽅程，可⾏域内点集由该⽅程组确定，其中值得注意的是可⾏域条件不⼀定为等式，只需要线性即可；c T x为⽬标等式，两个都为向量，所以值为⼀个单值，旨在找到⼀个极⼩值，使得满⾜minimize的要求；因此，对于任何的问题，都可以转为标准的问题形式进⾏求解；其中，⽐较有意思的是约束条件实际定义了求解的维数，也就是如何直观的通过对x的选择，使得c T x最⼤；如果从空间思想来考虑，就可以分为简单⼆维和三位情况下的最优化；如果是简单的⼆维情况：c T x相当于ax1+bx2，相当于⼆维平⾯上的⼀条直线，其中要求的是如何选定x1,x2的值，使得k=ax1+bx2存在最⼤最⼩值（因为向量c相当于已经确定了斜率）；⽽约束条件也为围成的⼀系列可⾏域，在⼆维平⾯内选择点，使得k=ax1+bx2最⼤，也就是和x2轴交点值最⼤；如下图所⽰，书上也给了⼀个很好的例⼦：⽽对于多维情况，则需要涉及凸多⾯体问题：c T x中的c的个数已经限定了多维空间下n的⽬标函数；约束条件Ax=b，其中A为m*n维数向量，定义了m个超平⾯所围成的⼀个凸多⾯体，并且假设该多⾯体⾮空有界；书上讨论了很多种情况，例如多⾯体超平⾯的维数问题；但是这⾥还是说⼀下常规的转换求法；根据c T x得到⼀个超平⾯c T x=0；找到⼀个⽀撑超平⾯c T x=β，使得整个胞体M在半平⾯，且M和超平⾯交集为M'；所以⽆论任何属于负半区的点y，都会有c T y<β；⽽任何属于M’的点y，都有c T y=β；所以可得到⽀撑超平⾯的点是极值点，同样如果⽀撑超平⾯为单点情况下，仍然适⽤；线性规划问题的标准型：对于标准型，和之前谈到的基本形式类似，实对所有⾼维线性规划下的问题做⼀个基本的形式定义；minimize c T xsubject to Ax=bx>=0值得注意的是Ax=b的条件，所有⼤于等于的线性条件都应该转为等于进⾏讨论，个⼈认为是使得所构成的解集范围是多胞体⽽⾮多个超平⾯围成的范围；⽽对于⾮标准形式，往往有Ax>=b或者Ax<=b，所以通过变换来变成⼀般的标准形式；其中注意下不同的说辞，Ax>=b,Ax<=b，⽆⾮就是加减y⽽已，保持y>=0即可，两种情况称之为剩余变量y和松弛变量y，名字记不记住感觉⽆伤⼤雅；基本解：当给出线性规划的基本形式之后，就可以对基本解进⾏构造；总的来说，解和传统的线性齐次、⾮齐次⽅程组不同，主要关注两个类型：1.基本解；2.可⾏解；两者其实有交集，交集的形式为基本可⾏解；基本解求法：可⾏解求法：可⾏解本质就是满⾜标准形式的解，也就是满⾜Ax=b,且x>=0的解，两个条件缺⼀不可；⽽基本可⾏解就是既为基本解满⾜x>=0的解；对于书上，有给出的相关例题，说明怎么求解可⾏解和基本解：基本解的性质：最优可⾏解：能够使得⽬标函数c T x取最⼩值的解；最优基本可⾏解：该最有可⾏解为基本解；其中对于线性规划来说，有挺重要的⼀条性质：1.如果存在可⾏解，则⼀定存在基本可⾏解；2.如果存在最优可⾏解，则必定存在最优基本可⾏解；基本可⾏解的实际意义：如果对于⼀个凸集，求⽬标函数极值，则必定取值点必定是凸集上的极点，对应的就是可⾏基本解；所以最后只需要寻找可⾏基本解中哪⼀个可以使得⽬标函数c T x最⼤(最⼩)，就可以得到最优基本可⾏解；【注意】关于为什么要找极点：根据前⾯⼆维推⼴⾄多维的推导，都是根据⽀撑超平⾯来进⾏极值寻找，所以找极值点也就相当于找使得距离原点超平⾯最远的⽀撑超平⾯；所以有定理：如若存在⼀个可⾏解组成的凸集，集合中的所有n维向量x满⾜Ax=b，x>=0，其中A维m*n维向量，则x是凸集中的极值点当且仅当x是Ax=b，x>=0的基本可⾏解；证明过程如下所⽰：。

第五章线性规划线性规划（Linear Programming，简记为LP）是数学规划的一个重要的分支，其应用极其广泛．1939年，前苏联数学家康托洛维奇（Л.B.Kah ）在《生产组织与计划中的数学方法》一书中，最早提出和研究了线性规划问题．1947年美国数学家丹泽格（G. B. Dantzig）提出了一般线性规划的数学模型及求解线性规划的通用方法─单纯形方法，为这门科学奠定了基础．此后30年，线性规划的理论和算法逐步丰富和发展．1979年前苏联数学家哈奇扬提出了利用求解线性不等式组的椭球法求解线性规划问题，这一工作有重要的理论意义，但实用价值不高．1984年在美国工作的印度数学家卡玛卡(N. Karmarkar)提出了求解线性规划的一个新的内点法，这是一个有实用价值的多项式时间算法．这些为线性规划更好地应用于实际提供了完善的理论基础和算法．第一节线性规划问题及其数学模型一、问题的提出例1 某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知条件如表所示。

问应如何安排计划使该工厂获利最多？ⅠⅡ现有资源设备原材料A 原材料B 14248台时16kg12kg每件利润23ⅠⅡ现有资源设备原材料A 原材料B 1402048台时16kg12kg每件利润23解: 设x 1、x 2 分别表示在计划期内产品Ⅰ、Ⅱ的产量。

12max 23z x x =+..s t 1228x x +≤1416x ≤2412x ≤12,0x x ≥二、线性规划问题的标准型112211112211211222221122123max ..,,0n nn n n n m m m mn n mn z c x c x c x s t a x a x a x b a x a x a x b a x a x a x b x x x x =+++⎧⎪+++=⎪⎪+++=⎨⎪⎪+++=⎪≥⎩，，其中1,,0m b b ≥11max ..,1,2,,0,1,2,,nj jj nij j i j j z c x s t a x b i mx j n=====≥=∑∑ 12(,,,)T n c c c =c 12(,,,)Tn x x x =x 12(,,,)Tm b b b =b 111212122212n nm m mn a a a a a a a a a ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦A 12[,,,]n = p p pmax ..()Tz s t ⎧=⎪=≥⎨⎪≥⎩c x Ax b b x 001max ..()Tnj j j z s tx =⎧=⎪⎪=≥⎨⎪⎪≥⎩∑c xp bb x 00对于不是标准形式的线性规划问题，可以通过下列方法将线性规划的数学模型化为标准形式：（1）目标函数的转换对min z 可以化max()z -（2）右端项的转换对0i b <，给方程两边同时乘以1-（3）约束条件的转换约束条件为≤方程左边加上一个变量,称为松弛变量约束条件为≥方程左边减上一个变量,称为剩余变量（4）变量的非负约束变量j x 无限制时，令,,0j j j j j x x x x x ''''''=-≥变量0j x ≤时，令j jx x '=-例将下列线性规划模型转化为标准形式12312312312312min 23..7232500x x x s t x x x x x x x x x x x -+-⎧⎪++≤⎪⎪-+≥⎨⎪--=-⎪≥≥⎪⎩，解（1）变量的非负约束令345x x x =-1245max 233x x x x -+-..s t 612457x x x x x ++-+=712452x x x x x -+--=12453225x x x x -++-=§2 两变量线性规划问题的图解法例1 求下列线性规划的解12121212max ..284300z x x s t x x x x x x =+⎧⎪+≤⎪⎪≤⎨⎪≤⎪≥≥⎪⎩，解（1）画可行域c A B D C 2x 1x O （2）画出目标函数的梯度向量：（3）作目标函数的一条等值线,120x x z +=将等值线沿梯度方向移动当等值线即将离开可行例2 求下列线性规划的解12121212max 2..284300z x x s t x x x x x x =+⎧⎪+≤⎪⎪≤⎨⎪≤⎪≥≥⎪⎩，解（1）画可行域c A B D C 2x 1x O （2）画出目标函数的梯度向量：（3）作目标函数的一条等值线,1202x x z +=将等值线沿梯度方向移动当等值线即将离开可行域时与可行域“最后的交点点为问题的最优解例3 求下列线性规划的解12121212max ..2200z x x s t x x x x x x =+⎧⎪-≤⎪⎨-≥-⎪⎪≥≥⎩，c2x 1x O无解例4 求下列线性规划的解12121212min 3..123600z x x s t x x x x x x =-⎧⎪≤⎪⎨≥⎪⎪≥≥⎩++，2x 1x O线性规划问题的性质：（1）线性规划的可行域为凸集，顶点个数有限．若可行域非空有界，则可行域为凸多边形．（2）线性规划可能有唯一最优解，可能有无数多个最优解，也可能无解最优解．无最优解可能是目标函数在可行域上无界，也可能可行域为空集．（３）若线性规划有最优解，则最优解必可在可行域的某个顶点达到．若两个顶点都为最优解，那么这两点连线上的所有点都是线性规划的最优解．§3 线性规划解的概念及其性质1 线性规划解的概念考虑线性规划问题max ..()Tz s t ⎧=⎪=≥⎨⎪≥⎩c x Ax b b x 00定义.1 矩阵A 中任何一组m 个线性无关的列向量构成的可逆矩阵B 称为线性规划的一个基矩阵与这些列向量对应的变量称为基变量(basis variable ）其余变量称为基对应的非基变量(nonbasis variable ）B 若设一个基为12(,,)m B p p p = ，12,,,m x x x ——为基B 对应的基变量1,,m n x x + ——为基B 对应的非基变量1B m x x x ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦1m N n x x x +⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦12(,,,)m m n ++= N p p p (,)=A B N 从而令=Ax b 则(,)N x ⎡⎤=⎢⎥⎣⎦B x B N b11B Nx B b B Nx --=-B N Bx Nx b+=令0N x =则1B x B b-=10B b -⎡⎤⎢⎥⎣⎦——基本解（basis solution ）满足10B b -⎡⎤≥⎢⎥⎣⎦,=≥0Ax b x 的基本解——基本可行解（basis feasible solution ）对应的基称为可行基（feasible basis ）．B 可以写成即:定义4 若基本可行解中所有基变量都为正，这样的基本可行解称为非退化解（non-degenerate solution）．若基本可行解中某基变量为零，这样的基本可行解称为退化解（degenerate solution）．例1212112max ..28400z x x s t x x x x x =-⎧⎪+≤⎪⎨≤⎪⎪≥≥⎩，标准化得：12123141234max ..28400,00z x x s t x x x x x x x x x =-⎧⎪++=⎪⎨+=⎪⎪≥≥≥≥⎩，，12341210(,,,)1001⎡⎤==⎢⎥⎣⎦A p p p p 子阵是否为基基变量非基变量基本解目标函数值134(,)=B p p 34,x x 12,x x (0,0,8,4)是231(,)=B p p 31,x x 24,x x (4,0,4,0)312(,)=B p p 12,x x 34,x x (4,2,0,0)424(,)=B p p 24,x x 13,x x (0,4,0,4)-4514(,)=B p p 14,x x 23,x x (8,0,0,4)-是是是是042基本可行解1x O(4,0)(4,2)(0,4)(8,0)2x 顶点2 解的判别定理定理1 最优解的判别准则设B 为线性规划LP 的一个基，1(1)0-≥B b 1(2)T T--≥0Bc B A c 则基对应的基本可行解1-⎡⎤⎢⎥⎣⎦0B b 是LP 的最优解．1(1,2,,)σ--== TBj j j c B p c j n 为变量对应的检验数j x 112[0,,0,,,]σσσ-++-= ，T TBm m n c B A c 显然基变量对应得检验数为零．定理2 无穷多个最优解的判别定理在线性规划的最优解中，某个非基变量对应的检验数为零，则线性规划有无数多最优解．定理3 无界解的判别定理设B 为线性规划的一个可行基，若基本可行解中s x 对应的检验数0σ<s ，且1-≤0s B p 则线性规划具有无界解（或称无解）．某非基变量§3.4 单纯形表设B 为线性规划的一个基，x 为对应的可行解，则=Ax b两边同乘得1-B 11--=B Ax B b两边同乘得T Bc 11T T --=BBc B Ax c B b T z =c xTz -=c x 11T T --+-=TBBz c B Ax c x c B b 11(T T --+-=)TBBz c B A c x c B b1111()T TT z ----⎧+-=⎨=⎩BBc B A c x c B b B Ax B b 11111T T Tz ----⎡⎤⎡⎤-⎡⎤=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦0BBc B b c B A c x B A B b 定义矩阵1111TT----⎡⎤-⎢⎥⎣⎦T BBc B b c B A c B bB A 为基B 对应的单纯形表（table of simplex ）,记为()T B1111()T T----⎡⎤-=⎢⎥⎣⎦T BBc B b c B A c T B B bB A 检验数函数值基变量的值各变量的系数100T b -=Bc B b 101020(,,,)--= T TBn c B A c b b b 10201-⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥ b b B b则单纯形表可写成000101011102()⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦B n n m m mn b b b b b b T b b b 1112121222111112(,,)---⎡⎤⎢⎥⎢⎥==⎢⎥⎢⎥⎣⎦n n n m m mn b b b b b b B A B p B p bb b上例中1212112max ..28400z x x s t x x x x x =-⎧⎪+≤⎪⎨≤⎪⎪≥≥⎩，标准化得：121231412max ..28400z x x s t x x x x x x x =-⎧⎪++=⎪⎨+=⎪⎪≥≥⎩，12341210(,,,)1001⎡⎤==⎢⎥⎣⎦A p p p p 子阵是否为基基变量非基变量基本解目标函数值134(,)=B p p 34,x x 12,x x (0,0,8,4)是231(,)=B p p 31,x x 24,x x (4,0,4,0)312(,)=B p p 12,x x 34,x x (4,2,0,0)424(,)=B p p 24,x x 13,x x (0,4,0,4)-4514(,)=B p p 14,x x 23,x x (8,0,0,4)-是是是是042基本可行解1x O(4,0)(4,2)(0,4)(8,0)2x 顶点13410(,)01⎡⎤==⎢⎥⎣⎦B p p 231(,)=B p p 12341210(,,,)1001⎡⎤==⎢⎥⎣⎦A p p p p T(0,0)=B C 10()T⎡⎤-=⎢⎥⎣⎦c T B b A 34011008121041001z x x -⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦23140101()4021141001x x ⎡⎤⎢⎥=-⎢⎥⎢⎥z T B 121101--⎡⎤=⎢⎥⎣⎦B 31401014021141001z x x ⎡⎤⎢⎥−−→-⎢⎥⎢⎥⎣⎦T(0,1)=B C单纯形表的特点：1、基变量对应的检验数为零2、基变量的系数构成单位阵§5旋转变换（基变换）设已知12(,,,,,)= r m j j j j B p p p p T()=B 1 r m j j j z x x x 1sn x x x 0001001011110102⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦sn s n r r rs rn m m ms mn b b b b b b b b b b b b b b b b为了将s x 变为基变量，而将r j x 变为非基变量，必须使表中的第s 列向量变为单位向量，变换按下列步骤进行：（1）将()T B 中第r 行，第s 列的元素化为1．01(,,,,,1,,) rj r rnr rs rs rs rsb b b b b b b b （2）将()T B 中第s 列的的其余元素化为0．0101(,,,,,0,,)---- is rn is rj is r is r i i ij in rs rs rs rsb b b b b b b b b b b b b b b b由此得出变换后矩阵中各元素的变换关系式如下，其中,01== ，，，rjrj rsb b j nb ,,01,01=-≠== ，，，，，，is rjij ij rsb b b b i r i m j nb 变换式称为旋转变换rs b 称为旋转元，r称为旋转行称为旋转列，s s x 称为入基变量，称为出基变量，r j x {,}r s定理3.5.1,01== ，，，rj rj rsb b j n b ,,0,01=-≠== ，，，，，is rj ij ij rsb b b b i r i m j n b 在变换之下，将基12(,,,,,)= r m j j j j B p p p p 的单纯形表变为基12(,,,,,)= m j s j j B p p p p 的单纯形表第6节单纯形法基本思路是：线性规划(通常是求最小值的形式)若有最优解，其必定在可行域(在相应几何空间中是一个凸多面体)的顶点达到，故从某一个顶点出发，沿着凸多面体的棱向另一顶点迭代，使得目标函数的值增加,经过有限次迭代，将达到最优解点.1.入基变量及出基变量的确定入基变量的确定由上面可知，目标函数用非基变量表示的形式为01n j jj m z z x σ=+=-∑若某检验数0j σ<则j x 的系数大于零，将j x 由零变为非零，目标函数值增大．所以，为了使的取值目标函数值增加，可以将某检验数0j σ<对应的非基变量j x 中的某个变为基变量．{}min 0j s j σ=<则s x 可选作为入基变量．即：在负检验数中，列标最小的检验数对应的非基变量入基．２．出基变量的确定在确定出基变量时应满足两个原则：（1）目标函数值不减；（2）保证新的基本解为基本可行解．0min 0,0i is is b b i m b θ⎧⎫=>≤≤⎨⎬⎩⎭min ,00i is is b r i b i m b θ⎧⎫==>≤≤⎨⎬⎩⎭，2 单纯形法设已知一个初始可行基及B T()B 基变量指标集合为{}1,,B m J j j = 非基变量的指标集合为{}1,2,,\N BJ n J =单纯形法若所有()00j N b j J ≥∈，则停止，最优解为0,1,,0,ij i j N x b i m x j J **⎧==⎪⎨=∈⎪⎩否则转（2）．（1）最优性检验（2）选入基变量{}0min 0,j N s j b j J =<∈若()01~is b i m ≤=,则停止,(LP)无最优解，否则转(3)（3）选出基变量0min 0,0i is is b b i m b θ⎧⎫=>≤≤⎨⎬⎩⎭0min ,00i is is b r i b i m b θ⎧⎫==>≤≤⎨⎬⎩⎭，（4）作{},r s 旋转运算,01rj rj rsb b j n b == ，，，,,01,01is rj ij ij rsb b b b i r i m j n b =-≠== ，，，，，，得B 的单纯形表()()ijT B b =，以ij b 代替ij b ，转(1)例1 求线性规划问题的解解标准型为:121231425max 2328416.412,,,,0z x x x x x x x s t x x x x x x x =+++=⎧⎪+=⎪⎨+=⎪⎪≥12121212max 2328416.412,0z x x x x x s t x x x =++≤⎧⎪≤⎪⎨≤⎪⎪≥⎩12123142512345max 2328416.412,,,,0z x x x x x x x s t x x x x x x x =+++=⎧⎪+=⎪⎨+=⎪⎪≥⎩-20-381612121004001004001345z x x x 12345x x x x x 000⎤⎥⎥⎥⎥⎥⎥⎡⎢⎢⎢⎢⎢⎢0T()B =0345[,,]B p p p =00T()T c B bA ⎡⎤-=⎢⎥⎣⎦-20-381612121004001004001345z x x x 12345x x x x x 000⎤⎥⎥⎥⎥⎥⎥⎦⎡⎢⎢⎢⎢⎢⎢⎣0T()B =8/116/408-3441202101001/400400135z x x 12345x x x x x 01/20⎤⎥⎥⎥⎥⎥⎥⎡⎢⎢⎢⎢⎢⎢1/4-41x08-3441202101001/400400135z x x 12345x x x x x 01/20⎤⎥⎥⎥⎥⎥⎥⎦⎡⎢⎢⎢⎢⎢⎢⎣1/4-1x 4/212/40140244011/201001/40002-15z x 12345x x x x x 3/21/80⎤⎥⎥⎥⎥⎥⎥⎦⎡⎢⎢⎢⎢⎢⎢⎣1/8-1x 32x 1/2例2求线性规划问题的解解标准型为:121231425max 228416.412,,,,0z x x x x x x x s t x x x x x x x =+++=⎧⎪+=⎪⎨+=⎪⎪≥12121212max 228416.412,0z x x x x x s t x x x =++≤⎧⎪≤⎪⎨≤⎪⎪≥⎩12123142512345max 228416.412,,,,0z x x x x x x x s t x x x x x x x =+++=⎧⎪+=⎪⎨+=⎪⎪≥⎩-10-281612121004001004001345z x x x 12345x x x x x 000⎤⎥⎥⎥⎥⎥⎥⎡⎢⎢⎢⎢⎢⎢0T()B =0345[,,]B p p p =00T()T c B bA ⎡⎤-=⎢⎥⎣⎦-10-281612121004001004001345z x x x 12345x x x x x 000⎤⎥⎥⎥⎥⎥⎥⎦⎡⎢⎢⎢⎢⎢⎢⎣0T()B =8/116/404-2441202101001/400400135z x x 12345x x x x x 01/40⎤⎥⎥⎥⎥⎥⎥⎡⎢⎢⎢⎢⎢⎢1/4-41x0-2441202101001/400400135z x x 12345x x x x x 00⎤⎥⎥⎥⎥⎥⎥⎦⎡⎢⎢⎢⎢⎢⎢⎣1/4-1x 4/212/4080244011/201001/400015z x 12345x x x x x 100⎤⎥⎥⎥⎥⎥⎥⎦⎡⎢⎢⎢⎢⎢⎢⎣1/8-1x 32x 41/42-1/2080244011/201001/400015z x 12345x x x x x 100⎤⎥⎥⎥⎥⎥⎥⎦⎡⎢⎢⎢⎢⎢⎢⎣1/8-1x 2x 2T 0803280101/410101/2-004-12z 12345x x x x x 00⎤⎥⎥⎥⎥⎥⎥⎦⎡⎢⎢⎢⎢⎢⎢⎣01x 2x 42-1/25x 11212x k x k x =+12120,1,1k k k k ≤≤+=全部最优解为§7 两阶段法第二阶段从初始可行基开始，用单纯形法求解原问题．（LP ）max ..(0)0T z c x s t Ax b b x ⎧=⎪=≥⎨⎪≥⎩（ALP ）max ..0()T w s t z ⎧=-⎪-=⎪⎨+≥⎪⎪≥⎩00T e y c x A =b b x y x 第一阶段引入人工变量，构造辅助问题，求辅助问题的最优解，得出原问题的初始可行基及对应的基本可行解．（ALP）12112211112211121122222211212312max..0 ,,,,0mn nn nn nm m mn n m mn mw y y ys t z c x c x c xa x a x a x y ba x a x a x y ba x a x a x y bx x x x y y y=----⎧⎪----=⎪⎪++++=⎪++++=⎨⎪⎪++++=⎪⎪≥⎩，，，，，121111211112122122212000000100()010001m m m m i i i in i=1i i i n n n m m m mn b a a a c c c b a a a T B b a a a b a a a ===⎡⎤----⎢⎥⎢⎥---⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦∑∑∑∑。

习题一1.1利用图解法求下列线性规划问题： （1）21x x z max +=⎪⎪⎩⎪⎪⎨⎧≥≤+≥+0x ,x 5x 2x 2x x 3.t .s 212121 解：根据条件，可行域为下面图形中的阴影部分，，有图形可知，原问题在A 点取得最优值，最优值z=5（2）21x 6x z min -=⎪⎪⎩⎪⎪⎨⎧≥≤+-≤+0x ,x 7x x 1x x 2.t .s 212121 解：图中阴影部分表示可行域，由图可知原问题在点A 处取得最优值，最优值z=-6.（3）21x 2x 3z max +=⎪⎪⎩⎪⎪⎨⎧≥-≥-≤+-0x ,x 4x 2x 1x x .t .s 212121 解：如图所示，可行域为图中阴影部分，易得原线性规划问题为无界解。

（4）21x 5x 2z min -=⎪⎪⎩⎪⎪⎨⎧≥≤+≥+0x ,x 2x x 6x 2x .t .s 212121 解：由图可知该线性规划可行域为空，则原问题无可行解。

1.2 对下列线性规划问题，找出所有的基解，基可行解，并求出最优解和最优值。

（1）4321x 6x 3x 2x 5z min -+-=⎪⎪⎩⎪⎪⎨⎧≥=+++=+++0x ,x ,x ,x 3x 2x x x 27x 4x 3x 2x .t .s 432143214321 解：易知1x 的系数列向量⎪⎪⎭⎫ ⎝⎛=21p 1，2x 的系数列向量⎪⎪⎭⎫ ⎝⎛=12p 2，3x 的系数列向量⎪⎪⎭⎫⎝⎛=13p 3，4x 的系数列向量⎪⎪⎭⎫⎝⎛=24p 4。

①因为21p ,p 线性无关，故有⎪⎩⎪⎨⎧--=+--=+43214321x 2x 3x x 2x 4x 37x 2x ，令非基变量为0x x 43==，得⎪⎪⎩⎪⎪⎨⎧=-=311x 31x 21，所以得到一个基解)0,0,311,31(x )1(-=是非基可行解； ②因为31p ,p 线性无关，可得基解)0,511,0,52(x)2(=，543z 2=；③因为41p ,p 线性无关，可得基解611,0,0,31(x )3(-=，是非基可行解；④因为32p ,p 线性无关，可得基解)0,1,2,0(x )4(=，1z 4-=；⑤因为42p ,p 线性相关，42x ,x 不能构成基变量； ⑥因为43p ,p 线性无关，可得基解)1,1,0,0(x )6(=，3z 6-=；所以)6()4()2(x ,x ,x是原问题的基可行解，)6(x 是最优解，最优值是3z -=。

（1）线性规划1212121max 23..43510x x s t x x x x x -+≤-+≥-≥的对偶规划为。

（2）用乘子法求解问题12min ()..0f x s t x x -=，其增广Lagrange 函数为 。

（3）在三维空间3R 中，集合22{(,,)|1,0,0,0}x y z x y x y z +≤≥≥≥的极点构成的集合为 。

（4）用黄金分割法求解某个函数在区间[-5,1]上的极小点，若要求缩短后的区间的长度小于1，则需要计算函数值的次数为 。

（5）对二次函数22121()2f x x x =+，取初始点(0)(2,1)T x =，用最速下降法一步得到的下一迭代点(1)x= 。

（6）函数2212112212(,)221f x x x x x ax x x =+++++为严格凸函数，则常数a 的取值范围是 。

（7）对于二次规划22121212121212min 22246..2055000x x x x x x s t x x x x x x +-----≥--≥≥≥，点(0,1)T的有效集为 ，写出在(0,1)T的一个可行下降方向： 。

1）线性规划1212122min 2..243510x x s t x x x x x --≥-+≤≤的对偶规划为。

（2）用外罚函数法求解问题12min ()..0f x s t x x -=，其增广目标函数为 。

（3）用黄金分割法求函数在[0,1]上的极小点，第一步所取的两个点为 。

（4）若221212()3f x x x ax x =++为严格凸函数，则a 的取值范围是 ，用Newton 法求该函数的极小点，取(0)(2,3)T x=，迭代一步得到的点为 。

（5）在最速下降法，Newton 法，FR 方法，DFP 方法，BFGS 方法中不具备二次终止性的算法为 。

（6）已知两个向量12(1,),(1,1)T T p a p ==-关于矩阵2113⎡⎤⎢⎥⎣⎦共轭，则a = 。