清华大学运筹学综合习题解析.pptVIP

例1．max z=3x1+x2+3x3 s.t. 2x1+x2+x3≤2 x1+2x2+3x3≤5 2x1+2x2+x3≤6 xi≥0,i=1,2,3 [解] 标准化后，写出单纯形表 ; XB b x1 x2 x3 x4 x5 x6 θ x2 1 5 1 0 3 -1 0 1/5 x3 1 -3 0 1 -2 1 0 - x6 3 -5 0 0 -4 1 1 - 7 0 0 3 -2 0 ;例2.max Ζ=3x1+2x1+x3-x4 s.t. 3x1+2x2+x3 =15; ;*;*;*;*;*;*;例6.求解下列线性规划问题 max Ζ=x1+2x2+3x3+4x4 s.t. x1+2x2+2x3+3x4≤20 2x1+x2+3x3+2x4≤20 xj≥0, j=1,2,3,4 ;用图解法得最优解 y1=1.2, y2=0.2; x1=x2=0 x1+2x2+2x3+3x4=20 2x1+x2+3x3+2x4=20; 例7.max Ζ=x1+4x2+3x3 s.t. 2x1+2x2+x3≤4 x1+2x2+2x3≤6 xj≥0; y1+2y2≥3 y1,y2≥0;1 3/2 1 0 1 -1/2 2 –1 0 1 –1 1 -10 –2 0 0 –1 -1 ;*;*;*;*;*; 例9某公司生产A,B两种塑料布，这两种产品每小时的产量均为1000米(宽度为2米)，该公司每天采用两班制生产，每周最大工作时间为80小时。按预测，A,B两种塑料布每周市场的最大销售量分别为70,000米和45,000米，A种塑料布每米的利润为2.5元，B种塑料布每米的利润是1.5元。试确定公司每周A,B两种塑料布的生产量x1和x2(单位:千米)，公司的目标是：;[解]这个问题的目标规划模型。;3.每周塑料布产量约束;; x1=13/4 x2=5/2 Z(0) =59/4≈14.75 选 x2 进行分枝，即增加两个约束，2 ≥ x2 ≥3 有下式：;;;接(LP1)继续分枝，加入约束 4 ≤ x1≤ 3，有下式：;;;树形图如下：;例11：用割平面法求解数规划问题;在松弛问题最优解中，x1, x2 均为非整数解，由上表有：;以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右边得： ;;例12;-1;◎;◎;◎;◎;◎;◎;◎;◎;例13 用逆推解法求解问题;s1;用逆推解法，从后先前依次有;利用微分法易知：;例14 分配投资问题;建立动态规划模型与求解;4、状态转移方程 sk+1 = sk - xk ;5、???段指标值（函数）： vk（sk，xk）= gk（xk） 所以指标函数为： 6、fk（sk）： 第 k 段初拥有的资金总量为 sk 时， 第 k 至第3段按最优投资策略所获得的第 k 至第3段的总收益。;7. 建立动态规划基本方程：（逆序递推方程）;k = 2;k = 1 第一种情况;k = 1 第二种情况;10、顺序确定最优策略。;vs;例15:求图所示网络中的最小费用最大流，弧旁的权是（bij,cij）。;算法： 取f(0)=0，一般若在第k-1步得到最小费用流f(k-1)， 则构造赋权有向图W(f(k-1))， 在W(f(k-1))中，寻求从vs到vt的最短路。 若不存在最短路 (即最短路权是+∞) ， 则f(k-1)就是最小费用最大流； 若存在最短路 ， 则在原网络D中得到相应的增广链μ ， 在增广链μ 上对f(k-1)进行调整。;4;1;1;2;5;例16:;;;;;例17:建筑工程网络的工序一览表;