文档介绍：运筹学复习1线性规划2对偶问题整数规划目标规划运输问题网络模型第一章线性规划一、。,:可行解、基本解、基本可行解、最优解、基本最优解的概念以及上述解之间的相互关系。基、可行基、最优基、凸集、凸组合、:从单纯形表判别线性规划问题具有唯一最优解、无穷多个最优解、无界解、无可行解。二、(有时求最小值);。;其中:通常X记为:。称A为约束方程的系数矩阵,m是约束方程的个数,n是决策变量的个数,一般情况m≤n,且r(A)=m。设线性规划的标准型maxZ=CX()AX=b()X≥0()式中A是m×n矩阵,m≤n并且r(A)=m,显然A中至少有一个m×m子矩阵B,使得r(B)=m。基(basis)A中m×m子矩阵B并且有r(B)=m,则称B是线性规划的一个基(或基矩阵basismatrix)。当m=n时,基矩阵唯一,当m<n时,基矩阵就可能有多个,但数目不超过可行解:满足式()及()的解X=(x1,x2…,xn)T称为可行解。基本可行解:若基本解是可行解则称为是基本可行解(也称基可行解)。基本解:对某一确定的基B,令非基变量等于零,利用式()解出基变量,则这组解称为基B的基本解。最优解:满足式()的可行解称为最优解,即是使得目标函数达到最大值的可行解就是最优解当确定某一矩阵为基矩阵时,则基矩阵对应的列向量称为基向量,其余列向量称为非基向量,基向量对应的变量称为基变量,非基向量对应的变量称为非基变量最优基基可行解对应的基称为可行基;基本最优解对应的基称为最优基,如上述B3就是最优基,最优基也是可行基。当最优解唯一时,最优解亦是基本最优解,当最优解不唯一时,则最优解不一定是基本最优解。例如右图中线段的点为最优解时,Q1点及Q2点是基本最优解,线段的内点是最优解而不是基本最优解。基本最优解最优解是基本解称为基本最优解。例如,满足式()~()是最优解,又是B3的基本解,、最优解、基本可行解、基本解、可行解的关系如下所示:基本最优解基本可行解可行解最优解基本解【】若线性规划可行解K非空,则K是凸集.【】线性规划的可行解集合K的点X是极点的充要条件为X是基本可行解.【】若线性规划有最优解,则最优值一定可以在可行解集合的某个极点上到达,:最优表中所有非基变量的检验数非零,则线规划具有唯一最优解多重最优解的判断:最优表中存在非基变量的检验数为零,:某个λk>0且aik≤0(i=1,2,…,m)则线性规划具有无界解退化基本可行解的判断:存在某个基变量为零的基本可行解。无可行解的判断:(1)当用大M单纯形法计算得到最优解并且存在Ri>0时,则表明原线性规划无可行解。(2)当第一阶段的最优值w≠0时,则原问题无可行解。【例】JT公司生产两种产品,设备及材料的消耗、价格及每周的限量,产品的单价如下表。 根据前段时间市场销售情况分析,公司决定产品1与产品2的产量比例不低于2:3。产品1产品2资源价格(元)每周资源限量设备(h)615(元/h)48材料A(kg)4312(元/kg)48产品售价(元/件)98186(1)求利润最大的生产方案,建立模型并求解。(2)其它条件不变产品比例变为:产品1与产品2的产量比例等于2:3后产品1再多生产2件,建立利润最大的生产计划模型,不求解。二、应用与计算题