250分悬赏线性计划后果(纯真形法)

  1、线性计划纯真形法的概念

  (一)线性计划纯真形解法的基本思路

  若一个凸集仅包罗有限个顶点,则称此凸集为纯真形。

  线性计划的可行域是纯真形(证实略,但可以从上节图解法的例子掉掉落认同),进而线性计划的基可行解又与线性计划后果可行域的顶点1-1对应(定理2.2.2), 线性计划纯真形法就是基于线性计划可行域的如许的几何特点设计发生的。这个方法最后是在20世纪40年代由George Dantzig研究出来的。这个线性计划纯真形解法的基本思路是:先求得一个初始基可行解,以这个初始基可行解在可行域中对应的顶点为出发点,依据最优准绳辨别这个基可行解可否是最优解,假设不是转换到相邻的一个顶点,即掉掉落一个新的基可行解,并使目标函数值降低,如许重复停止有限次后,可找到最解或辨别后果无最优解。

  (二)纯真形法的最优准绳

  设:线性计划(LP)为:

  min cx

  s.t. Ax=b

  x≥0

  A为(LP)的束缚方程组的m*n阶系数矩阵(设n≥m),A的秩为m;B是线性计划的一个基,不掉遍及性,记

  定义

  则:称λ,或许λj,(j=1,2,…,n)为考验数。

  若:λ≤0,即全部λi非正,

  则:由B肯定的基可行解是(LP)的最优解。

  (参看附录2.3.1)

  2、线性计划纯真形法的表格解法

  较复杂的线性计划可以采取纯真形法的表格方法,如许应用计算器便可求解。纯真形法的表格解法的基本思路是,对基可行解建立纯真形表,依据此表作最优解辨别,和从原基可行解向目标值更小的新可行解转换的计算。

  关于由基阵B肯定的基可行解,其纯真形表为表2.3.1方法。关于初始基可行解,其纯真形表的构建方法为:先建立表2.3.2方法的表格,然后应用“行变换”将表2.3.2中的前m列,即基变量对应的列

  转换为

  个中0是m元0向量:0=(0,0,…,0), 是m阶单位方阵。在如许的行变换下,表2.3.2将转换为表2.3.1

  表2.3.1

  考验数

  基变量

  cBB-1A-c cBB-1b

  xB B-1A B-1b

  表2.3.2

  考验数

  基变量

  -cB -cN o

  xB B N B-1b

  (参看附录2.3.2)

  (一)直接求解

  对以下方法的较复杂的线性计划可直接采取纯真形法的表格方法求解:

  min cx

  s.t. Ax≤b

  x≥0

  这类方法的线性计划规范化后,为

  min cx+ox'

  s.t. Ax+lx'=b

本文地址//a/tyzxxw/20200330-54.html,转载请注明出处!

上一篇:王晨光《麦田里的守望者——关于梵高的札记》 下一篇:没有了