规划问题

Jessew

三、线性规划、整数规划、多元规划、二次规划
& f, I$ q  h/ d4 s& [6 X' h（1）线性规划
; A* e$ G( O9 _% \1、含义的理解
1 J' x& S+ Y+ Z' Q5 g& G& }) k线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.研究线性约束条件下线性目标函数的极值问题的数学理论和方法，英文缩写LP。它是运筹学的一个重要分支。
% u0 h; q: _( r0 w- {6 z" k$ o在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素。
2、线性规划问题的数学模型的一般形式和模型建立
0 y7 F7 `* z. T% A7 M（1）列出约束条件及目标函数 （2）画出约束条件所表示的可行域 （3）在可行域内求目标函数的最优解及最优值（实际问题中建立数学模型一般有以下三个步骤：根据影响所要达到目的的因素找到决策变量；2.由决策变量和所在达到目的之间的函数关系确定目标函数；3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。）
* f8 i) ^1 z/ X所建立的数学模型具有以下特点：
（1）、每个模型都有若干个决策变量（x1,x2,x3……，xn），其中n为决策变量个数。决策变量的一组值表示一种方案，同时决策变量一般是非负的。
& y$ e; z* X* ^+ [  Q( E8 c（2）、目标函数是决策变量的线性函数，根据具体问题可以是最大化（max）或最小化（min），二者统称为最优化（opt）。
（3）、约束条件也是决策变量的线性函数。当我们得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。
6 b' x; h2 e4 U! A* H3、实例
) {9 Z. [) Q. K: r生产计划问题
问题：
某企业要在计划期内安排生产甲、乙两种产品，这个企业现有的生产资料是：设备18台时，原材料A ：4吨，原材料 B： 12吨；已知单位产品所需消耗生产资料及利润如下表。问应如何确定生产计划使企业获利最多？
      产品
$ X0 {, X3 b/ n/ ~% s# A资源        甲        乙        资源量
+ Z8 A  D! H) i6 V) `9 a3 h设备/台时        3        2        18
! i8 h! V: B. z3 Z' f; l原料A/吨        1        0        4
# x# A. r1 W5 n1 V& W. A原料B/吨        0        2        12
单位赢利/万元        3        5         
# T1 V7 l2 P( k; d* S/ |2 W设x1为甲产品分配的设备台数，x2为乙产品分配的台数。则
) a5 W% P3 W  q  ^2 y: n条件限制为：
3*x1+2*x2 18
! H6 Y: J: l. Q- @2 m1*x1+0*x2 4
$ o; h  C, O  Z! T; Q3 K0*x1+2*x2 12
! d# U" W/ A9 _$ h! `x1 0，x2 0
求max z=3*x1+5*x2
6 Y0 I9 t) V, f' h6 p3 G! o5 i用lingo编程，程序如下：
' }9 s2 {* A$ ~9 ]1 ymax=3*x1+5*x2;
3*x1+2*x2<=18;
4 m* s' N' {) {7 bx1<=4;
x2<=6;
5 u$ n: r+ [+ z. ox1>=0;
x2>=0;
结果为：
. x: ?" @- c- G7 Y! J* GGlobal optimal solution found.
+ r$ }' [# Q3 IObjective value:                              36.00000
Total solver iterations:                             1
% v# M7 T! M, Q; d/ x        Variable           Value        Reduced Cost
                X1        2.000000            0.000000
4 L* _: d) }6 h2 f2 n                X2        6.000000            0.000000

        Row    Slack or Surplus      Dual Price
, e: \  H" d' e# |5 _, `         1        36.00000            1.000000
          2        0.000000            1.000000
  @0 \* O! w/ O; c: H          3        2.000000            0.000000
8 p, A& K& q) j4 c2 s0 x          4        0.000000            3.000000
8 n: h) ]% f" B: T- C' i/ w7 d          5        2.000000            0.000000
3 ~9 P& N, T  z( v+ e! e          6        6.000000            0.000000
即在x1=2，x2=6时，企业获利最多，为36万元。
4、线性规划的应用
2 z9 c9 c5 T; E4 H7 X' E在企业的各项管理活动中,例如计划、生产、运输、技术等问题,线性规划是指从各种限制条件的组合中,选择出最为合理的计算方法,建立线性规划模型从而求得最佳结果. 广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。
（2）整数规划
5 m4 v( i$ P, k" W一类要求问题的解中的全部或一部分变量为整数的数学规划。从约束条件的构成又可细分为线性，二次和非线性的整数规划。 　　在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求某些变量的解必须是整数。例如，当变量代表的是机器的台数，工作的人数或装货的车数等。为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是0-1规划，它的变数仅限于0或1。不同于线性规划问题，整数和0-1规划问题至今尚未找到一般的多项式解法。
组合最优化通常都可表述为整数规划问题。两者都是在有限个可供选择的方案中，寻找满足一定约束的最好方案。有许多典型的问题反映整数规划的广泛背景。例如，背袋（或装载）问题、固定费用问题、和睦探险队问题（组合学的对集问题）、有效探险队问题（组合学的覆盖问题）、旅行推销员问题, 车辆路径问题等。因此整数规划的应用范围也是极其广泛的。它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。
整数规划是从1958年由R.E.戈莫里提出割平面法之后形成独立分支的 。解整数规划最典型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题（衍生问题称为松弛问题的源问题）。通过松弛问题的解来确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。随即再选择一个尚未被舍弃的或替代的原问题的衍生问题，重复以上步骤直至不再剩有未解决的衍生问题为止。目前比较成功又流行的方法是分枝定界法和割平面法，它们都是在上述框架下形成的。
8 T, b5 t" k1 {6 n( `$ W0-1规划在整数规划中占有重要地位，一方面因为许多实际问题，例如指派问题、选地问题、送货问题都可归结为此类规划，另一方面任何有界变量的整数规划都与0-1规划等价，用0-1规划方法还可以把多种非线性规划问题表示成整数规划问题，所以不少人致力于这个方向的研究。求解0-1规划的常用方法是分枝定界法，对各种特殊问题还有一些特殊方法，例如求解指派问题用匈牙利方法就比较方便。
4 w. ~1 V2 q3 ~3 t6 ~  K! w4 S  q（4）二次规划
5 {8 M. u& e; F7 C二次规划是非线形规划中一类特殊的数学规划问题，它的解是可以通过求解得到的。通常通过解其库恩—塔克条件（KT条件）,获取一个KT条件的解称为KT对，其中与原问题的变量对应的部分称为KT点。
; R) u3 S; }, T. _* a+ w二次规划分为凸二次规划与非凸二次规划，前者的KT点便是其全局极小值点，而后者的KT点可能连局部极小值点都不是。若它的目标函数是二次函数，则约束条件是线性的。由于求解二次规划的方法很多，所以较为复杂；其较简便易行的是沃尔夫法，它是依据库恩－塔克条件，在线性规划单纯形法的基础上加以修正而成的。此外还有莱姆基法、毕尔法、凯勒法等。
; V: e- Z+ A8 K) X, ?4 F
* e. G4 B* G8 C6 q2 D$ u

8 W) O% F# S& l" P$ s1 a/ X. T