搜索
第一章第一章1.建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量（DecisionVariable）是决策问题待定的量值，取值一般为非负；约束条件（ConstraintConditions）是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数（ObjectiveFunction）是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。2.（1）设立决策变量；（2）确定极值化的单一线性目标函数；（3）线性的约束条件：考虑到能力制约，保证能力需求量不能突破有效供给量；（4）非负约束。3.（1）唯一最优解：只有一个最优点（2）多重最优解：无穷多个最优解（3）无界解：可行域无界，目标值无限增大（4）没有可行解：线性规划问题的可行域是空集无界解和没有可行解时，可能是建模时有错。4.线性规划的标准形式为：目标函数极大化，约束条件为等式，右端常数项bi≥0,决策变量满足非负性。如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。5.可行解：满足约束条件AX=b,X≥0的解，称为可行解。基可行解：满足非负性约束的基解，称为基可行解。可行基：对应于基可行解的基，称为可行基。最优解：使目标函数最优的可行解，称为最优解。最优基：最优解对应的基矩阵，称为最优基。6.计算步骤：第一步，确定初始基可行解。第二步，最优性检验与解的判别。第三步，进行基变换。第四步，进行函数迭代。判断方式：唯一最优解：所有非基变量的检验数为负数，即σj0无穷多最优解：若所有非基变量的检验数σj≤0，且存在某个非基变量xNk的检验数σk=0，让其进基，目标函数的值仍然保持原值。如果同时存在最小θ值，说明有离基变量，则该问题在两个顶点上同时达到最优，为无穷多最优解。无界解：若某个非基变量xNk的检验数σk0，但其对应的系数列向量Pk'中，每一个元素aik'(i=1,2,3,…,m)均非正数，即有进基变量但找不到离基变量。无可行解：当引入人工变量，最末单纯型发表中的基变量含有非零的人工变量，即人工变量不能全出基，则无可行解。7.单纯形法需要有一个单位矩阵作为初始基。当约束条件都是“≤”时，加入松弛变量就形成了初始基，但实际问题中往往出现“≥”或“＝”型的约束，这就没有现成的单位矩阵。需要采用人造基的办法，无单位列向量的等式中加入人工变量，从而得到一个初始基。人工变量只有取0时，原来的约束条件才是它本来的意义。为保证人工变量取值为0，令其价值系数为-M（M为无限大的正数，这是一个惩罚项）。如果人工变量不为零，则目标函数就不能实现最优，因此必须将其逐步从基变量中替换出。对最小化问题，在目标函数中人工变量的系数取M。8.9.10.（1）C10，C20，且d≥0（2）C1=0，C20或C2=0，C10，a10（3）C10，d0，a20，d/43/a2（4）C20，a1≤0（5）x1为人工变量，且C1为包含M的大于0数，d/43/a2；或者x2为人工变量，且C2为包含M的大于0数，a10，d0。11.12.设xij为电站向某城市分配的电量，建立模型如下：13.设x1为产品A的产量，x2为产品B的产量，x3为副产品C的销售量，x4为副产品C的销毁量，问题模型如下：第二章1.（2）甲生产20件，乙生产60件，材料和设备C充分利用，设备D剩余600单位（3）甲上升到13800需要调整，乙下降60不用调整。（4）非紧缺资源设备D最多可以减少到300，而紧缺资源—材料最多可以增加到300，紧缺资源—设备C最多可以增加到360。2.设第一次投资项目i为xi，第二次投资项目i设为xi'，第三次投资项目i设为xi′。3.设每种家具的产量为4.设每种产品生产xi5．（1）设xi为三种产品生产量通过Lindo计算得x1=33,x2=67,x3=0,Z=733（2）产品丙每件的利润增加到大于6.67时才值得安排生产；如产品丙每件的利润增加到50/6，通过Lindo计算最优生产计划为：x1=29，x2=46，x3=25，Z=774.9。（3）产品甲的利润在[6,15]范围内变化时，原最优计划保持不变。（4）确定保持原最优基不变的q的变化范围为[-4,5]。（5）通过Lindo计算，得到x1=32,x2=58,x3=10,Z=707第三章1.原问题和对偶问题从不同的角度来分析同一个问题，前者从产品产量的角度来考察利润，后者则从形成产品本身所需要的各种资源的角度来考察利润，即利润是产品生产带来的，同时又是资源消耗带来的。对偶变量的值yi∗表示第i种资源的边际价值，称为影子价值。可以把对偶问题的解Y定义为每增加一个单位的资源引起的目标函数值的增量。2.若以产值为目标，则yi是增加单位资源i对产值的贡献，称为资源的影子价格（ShadowPrice）。即有“影子价格=资源成本+影子利润”。因为它并不是资源的实际价格，而是企业内部资源的配比价格，是由企业内部资源的配置状况来决定的，并不是由市场来决定，所以叫影子价格。可以将资源的市场价格与影子价格进行比较，当市场价格小于影子价格时，企业可以购进相应资源，储备或者投入生产；当市场价格大于影子价格时，企业可以考虑暂不购进资源，减少不必要的损失。3.（1）最优性定理：设，分别为原问题和对偶问题的可行解，且C=bT，则，a分别为各自的最优解。（2）对偶性定理：若原问题有最优解，那么对偶问题也有最优解，而且两者的目标函数值相等。（3）互补松弛性：原问题和对偶问题的可行解X*、Y*为最优解的充分必要条件是,。（4）对偶问题的最优解对应于原问题最优单纯形法表中，初始基变量的检验数的负值。若−YS对应原问题决策变量x的检验数；−Y则对应原问题松弛变量xS的检验数。4.表示三种资源的影子利润分别为0.89、4.89和0，应优先增加设备C台时以及增加材料可获利更多；14.8912，所以设备C可以进行外协加工，200.89210，所以暂不外购材料。5.(1)求出该问题的最优解和最优值；x1=x2=x4=0,x3=2,x5=6,Z=4(2)该问题的对偶问题的最优解和最优值：y1=2，y2==0，w=4(3)分别为2、0，对产值贡献的大小；第一种资源限量由2变为4，最优解不会改变。(4)代加工产品丁的价格不低于2×2+0×3=4。46.(1)设四种产品产量为xi,i=1,2,3,4(2)影子价格分别为2、1.25、2.5。对比市场价格和影子价格，当市场价低于影子价格时购进。(3)原料丙可利用量在[900,1100]范围内变化，原最优生产方案中生产产品的品种不变（即最优基不变）。(4)若产品B的价格下降了0.5元，生产计划不需要调整。第四章1.纯整数规划、0-1规划、混合整数规划。2.(1)首先不考虑整数条件，求解整数规划相应的线性规划问题。若相应的线性规划问题没有可行解，停止计算，这时原整数规划也没有可行解。(2)定界过程。对于极大化的整数规划问题，当前所有未分枝子问题中最大的目标函数值为整数规划问题上界；在满足整数约束的子问题的解中，最大的目标函数值为整数规划问题的下界。当上下界相同时，则已得最优解；否则，转入剪枝过程。(3)剪枝过程。在下述情况下剪除这些分枝：①若某一子问题相应的线性规划问题无可行解；②在分枝过程中，求解某一线性规划所得到的目标函数值Z不优于现有下界。(4)分枝过程。当有多个待求分枝时，应先选取目标函数值最优的分枝继续进行分枝。选取一个不符合整数条件的变量xi作为分枝变量，若xi的值是bi*，构造两个新的约束条件：xi≤[bi*]或xi≥[bi*]+1,分别并入相应的数学模型中，构成两个子问题。对任一个子问题，转步骤(1)。最整数解为：x1=4,x2=2,z=3404.解：设,tij为个人对于个任务的时间耗费矩阵，则目标函数为：约束条件为：解之得：x12=1，x21=1，x33=1，x44=1，其余均为0，z=70，即任务A由乙完成，任务B由甲完成，任务C由丙完成，任务D由丁完成。5.解：设在第i天应聘的雇员人数为xi。数学模型为：解得：x1=0，x2=4，x3=32，x4=10，x5=34，x6=10，x7=4，Z=94。第五章1.解：建立目标约束。（1）装配线正常生产设生产A,B,C型号的电脑为x1,x2,x3（台），d1−为装配线正常生产时间未利用数，d1+为装配线加班时间，希望装配线正常生产，避免开工不足，因此装配线目标约束为（2）销售目标优先满足老客户的需求，并根据三种电脑的纯利润分配不同的权因子，A,B,C三种型号的电脑每小时的利润是，，，因此，老客户的销售目标约束为再考虑一般销售。类似上面的讨论，得到（3）加班限制首先是限制装配线加班时间，不允许超过200h，因此得到其次装配线的加班时间尽可能少，即写出目标规划的数学模型经过Lingo计算得到x1=100，x2=55，x3=80。装配线生产时间为1900h，满足装配线加班不超过200h的要求。能够满足老客户的需求，但未能达到销售目标。销售总利润为100×1000+55×1440+80×2520=380800（元）。2.解：假设三个工厂对应的生产量分别为300，200，400。（1）求解原运输问题由于总生产量小于总需求量，虚设工厂4，生产量为100个单位，到各个用户间的运费单价为0。用LINGO软件求解，得到总运费是2950元，运输方案如下表所示。（2）下面按照目标的重要性的等级列出目标规划的约束和目标函数。设xij工厂i(i=1,2,3)调配给用户j(j=1,2,3,4)的运量，cij表示从工厂i到用户j的单位产品的运输费用，aj(j=1,2,3,4)表示第j个用户的需求量，bi(i=1,2,3)表示第i个工厂的生产量。i）供应约束应严格满足，即ii）供应用户1的产品中，工厂3的产品不少于100个单位，即;iii）需求约束。各用户的满足率不低于80％，即应尽量满足各用户的需求，即iv）新方案的总运费不超过原方案的10％（原运输方案的运费为2950元），即v）工厂2到用户4的路线应尽量避免运输任务，即vi）用户1和用户3的满足率应尽量保持平衡，即vii）力求总运费最少，即目标函数为经8次运算，得到最终的计算结果，见下表。总运费为3360元，高于原运费410元，超过原方案10％的上限115元。3.设分别生产A机器x1台，B机器x2台。目标函数为：Lingo计算结果为：生产A机器15台，B机器21台，利润增加4129元，工序Ⅱ加班22.5小时。第六章1.原有问题的求解就化为逐个求解几个简单的阶段子问题，当每一个阶段的决策子问题确定后，就组成了一个决策序列，每个阶段的决策一旦确定，整个决策过程也随之确定，此类把一个问题看作是一个前后关联具有明显阶段性的决策过程就称为多阶段决策问题。2.动态规划最优性原理导出了它的解题思路，即将决策问题划分为若干个阶段，将全过程的优化问题分解为子过程的优化问题；逆着阶段顺序的方向，由后向前逐步倒推；各阶段求解都是在后部子过程最优策略基础上，再考虑本阶段的指标函数，求出本阶段的最优策略；由后向前推算直到第一阶段为止，最优化的子过程逐渐成为最优化的全过程。3.（1）模型建立将三个营业区看作是三个阶段，即阶段变量k=1,2,3；第k阶段初尚未被分配出去的销售点是其决策的起点，则状态变量Sk表示第k阶段初可分配的销售区数，Sk≥0，且初始状态已知S1=6；决策变量xk表示第k阶段分配给区A，B，C的销售店，允许决策集合状态转移方程为Sk+1=Sk-k阶段指标Vk(Sk,xk)表示第k阶段从Sk销售点中分配给第k区xk个的阶段效益；最优指数函数fk(Sk)表示第k阶段从Sk开始到最后阶段采用最优分配策略取得的最大收益，递推方程函数式（2）逆序求解当k=3时当k=2时当k=1时顺序递推，得出结论：第A小组建3个,第B区建2个，第C区建1个，4.（1