根据图解法求解线性规划问题的结果知,一个线性规划问题的解可能有四种情况:唯一、无穷、无界和无解。那么利用单纯形计算时,如何判断一个线性规划问题的解可能是哪一种情况呢?这里给出四个判定定理(以标准型线性规划为例...[继续阅读]
海量资源,尽在掌握
根据图解法求解线性规划问题的结果知,一个线性规划问题的解可能有四种情况:唯一、无穷、无界和无解。那么利用单纯形计算时,如何判断一个线性规划问题的解可能是哪一种情况呢?这里给出四个判定定理(以标准型线性规划为例...[继续阅读]
(1)对于检验数的最优判别,若目标是max,则要求所有非基变量的检验数≤0;若目标是min,则要求所有非基变量的检验数≥0。(2)根据最大正检验数来确定进基变量,有时并非是最佳的选择,这里实际上需要考虑从初始基可行解出发沿哪个方向...[继续阅读]
对于标准形式的线性规划问题(问题A):maxZ=c1x1+c2x2+…+cnxn若其约束方程的系数矩阵中不存在现成的初始可行基,则引入所谓的人工变量xn+1,…,xn+m,构造如下形式的线性规划问题(问题B):maxZ=c1x1+c2x2+…+cnxn-Mxn+1-…-Mxn+m问题B中M为任意大的正...[继续阅读]
两阶段法是把一般线性规划问题的求解过程分为两个阶段。即:第一阶段:在原线性规划问题中引入人工变量,并构造仅含有人工变量的目标函数,使其目标函数最小化,用单纯形法求解,以去掉人工变量。若第一阶段求得最优解对应的最...[继续阅读]
本章主要介绍了求解线性规划问题的两种方法:单纯形法和人工变量法。单纯形法是求解线性规划的经典方法,其基本思路是先找出一个初始的基可行解,判断其是否为最优解;如果不是,则转换到另一个基可行解,并使目标函数的值逐步...[继续阅读]
一、判断题1.单纯形法是求解线性规划模型的唯一方法。()2.用单纯形法求解线性规划问题,必须要有单位阵作为初始可行基。()3.单纯形法的迭代计算是从一个可行解转换到目标函数值更大的另一个可行解。()4.基本可行解的个数不会...[继续阅读]
【例4-1】在第二章的【例2-1】中,讨论了某工厂资源的合理利用问题,建立了线性规划模型:maxZ=3x1+5x2已知最优解为:x*1=4,x*2=5,z*=37。现在从另一个角度考虑这个问题。假定该厂的决策者考虑自己不生产甲、乙两种产品,而把原拟用于...[继续阅读]
以上从两个资源利用问题,引出了对资源的估价问题,得到了对偶规划。原问题与其对偶问题之间通常有三种不同的关系形式,以下将原问题记作(P)问题,对偶问题记作(D)问题。1.对称型对偶问题定义4.1:设原LP问题为:maxZ=c1x1+c2x2+…+cnxnx...[继续阅读]
这一节给出对偶问题的一些性质,为叙述方便,仅在对称形式下进行分析。maxZ=cxminw=yb定理4.1(对称性定理)对偶问题的对偶是原问题。证明:先将(D)问题化成原问题形式maxw′=(-bT)yT由定义4.1,设xT为它的对偶变量,写出它的对偶问题。这就是...[继续阅读]
考虑一对对称的对偶问题。从上节对偶问题的基本性质可知,当(P)问题求得最优解x*时,其(D)问题也得到最优解y*,且有:bi代表第i种资源的拥有量;对偶变量y*i的意义代表在资源最优利用条件下对单位第i种资源的估价。这种估价不是资源...[继续阅读]