为了讨论方便,把最大化、等式约束型的线性规划称为线性规划的标准型,即:或简写为:称其为标准形式的一般式。标准型的矩阵形式为:标准型的向量形式为:上述三种表达式: 一般式、矩阵式、向量式是等价的,在应用中可根据需要灵...[继续阅读]

    设线性规划问题为:则从代数学的角度得到如下概念:(1)解: 决策变量的一组取值便构成了线性规划问题的一个解;(2)可行解: 满足约束条件(2.3b)、(2.3c)的解称为可行解;(3)可行域: 所有可行解构成的集合称为可行域;(4)最优解: 使目标函数...[继续阅读]

    图解法可分三步进行: 第一步,画出直角坐标系; 第二步,依次做每条约束条件相应方程的等值线,根据各约束条件所确定的半平面找出它们共同的可行域;第三步,任取一目标函数值做一条目标函数等值线,根据目标函数(最大或最小)类型...[继续阅读]

    (1)确定初始基可行解设给定标准线性规划问题:为了确定初始基可行解,首先要找到初始基可行基。通常,可从Pj中直接观察到存在一个初始可行基B=(P1,…,Pm)=Im×m。如果不能直接观察到初始可行基,可重新对xi和aij(i=1,…,m;j=1,…,n)进行变...[继续阅读]

    为了便于理解计算关系,设计一种计算表,称为单纯形表,其功能与增广矩阵相似。每一次迭代对应一张单纯形表,含初始基可行解的单纯形表称为初始单纯形表,含最优解的单纯形表称为最终单纯形表。1.单纯形表设计将式2-13与目标函数...[继续阅读]

    上述单纯形法第一步,在标准型中系数矩阵有单位矩阵,很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵,为了得到一组基向量和初始基可行解,在约束条件的等式左端加一组虚拟变量,得到一组基变量。这种人为加的...[继续阅读]

    在2.1节的例2.1中天山机器厂用A、B、C三种不同设备生产Ⅰ、Ⅱ两种产品时,其线性规划问题为现从另一角度考虑此问题。假设有客户提出要求,租赁工厂的设备,为其加工生产别的产品,由客户支付台时费,此时工厂应考虑如何为每种设备...[继续阅读]

    (1)单纯形法计算的矩阵描述对称形式线性规划问题式2.16的矩阵表达式加上松弛变量XS后为记A=[B N],相应的X=[XB XN]T。单纯形法计算时,总选取Ⅰ为初始基,其对应基变量XS。设迭代若干步后,基变量为XB,XB在初始单纯形表中的系数矩阵为...[继续阅读]

    在一对原问题和对偶问题中,若原问题的某个约束条件的右端项常数bi(第i种资源的拥有量)增加一个单位时,所引起目标函数最优值z*的改变量称为第i种资源的影子价格。从数学角度分析,在单纯形法的每步迭代中,目标函数值z*＝CBB-1...[继续阅读]

    在求解MAX型线性规划时,当所有非基变量的检验数全部小于或等于零,且基变量XB的值全部非负时,得到最优解。但若所有非基变量的检验数全部非正,且基变量XB的值有小于零的,则可通过对偶单纯形法来求,或可将约束条件左右乘以-1之...[继续阅读]