搜索
一、考虑下面给出的不完全初始单纯形表：C63025000θcBxBbX1X2X3X4X5X640310100500210102021-1001σ1、把上面的表格填写完整；2、按照上面的完整表格，写出此线性规划模型；3、写出初始基可行解和其对应的目标函数值；4、为下一次迭代确定进基变量和出基变量，说明理由，并在表格上标出主元素。5、若解得此模型对偶问题最优解之一y1﹡=m，试说明其经济意义。二、求解下列运输问题，说明初始调运表中某变量检验数为负的经济意义。销地产地B1B2B3B4产量A1A283741642088A3571062销量5526三、五人翻译五种外文的速度（百个印刷符号/小时）如下表所示：语种人英俄日德法甲乙98456981056丙97358丁48695戊653108若规定每人专门负责一个语种的翻译工作，应如何指派，使总的翻译效率最高？作业：将资金分配看作三阶段的动态过程1(项目A)2(项目B)3(项目C)可分配资金S1百万元可分配资金S2可分配资金S3分配U1百万元分配u2S4=0分配u3资源分配问题模型1、设阶段为分配过程（步骤），K=1，2，32、状态变量SK为第K步可供分配的资金数(百万元)3、决策变量UK为分配给第K各项目的资金数4、状态转移方程：SK+1=SK－UK5、gK(UK)为UK资金分配给该项目所产生的收益6、fk(Sk)=max{gK+fk+1(SK+1)}f4(S4)=0基本方程边界条件1、f4(S4)=0,fk(Sk)=max{gK(UK)+fk+1(SK+1)}2、K=3时，S3=0,1,2,3,4=max{g3(U3)+f4(S4)}=max[g3(U3)]∴U3=0,1,2,3,4f3(S3)1(项目A)2(项目B)3(项目C)可分配资金S1百万元可分配资金S2可分配资金S3分配U1百万元分配u2S4=0分配u32、K=3时，S3=0,1,2,3,4U3=0,1,2,3,4f3(S3)=max{g3(U3)+f4(S4)}=max[g3(U3)]47070437070326868216262103838043210U3﹡f3(S3)g3(U3)U3S301234A3841486066B4042506065C38626870703、K=2时，S2=0,1,2,3,4B：分U2，盈利g2(U2)C：分S2-U2，盈利f3(S3)f2(S2)=max{g2(U2)+f3(S3)}312265+3860+6250+6842+7040+70211260+3850+6242+6840+70010850+3842+6240+68010242+3840+6207840+384321043210U2﹡f2(S2)g2(U2)+f3(S3)U2S2S3f3(S3)U3﹡0380162126823703470401234A3841486066B4042506065C38626870703、K=1时，S1=4甲：分U1，盈利g1(U1)乙+丙：分4–U1，盈利f2(S2)f1(S1)=max{g1(U1)+f2(S2)}316266+7860+10248+10841+11238+122443210U1﹡f1(S1)g1(U1)+f2(S2)U1S1S3f3(S3)U3﹡07801102021080311224122301234A3841486066B4042506065C3862687070资金分配问题最优方案A：追加投资3百万元B：0C：追加投资1百万元最大盈利162百万元s.t.X11+X12+X13+X14+X15≤1，X21+X22+X23+X24+X25≤1X31+X32+X33+X34+X35≤1，设xij=1第i电厂在第j年投资0第i电厂在第j年不投资X41+X42+X43+X44+X45≤170X11+50X21+60X31+40X41≥30，70(X11+X12)+50(X21+X22)+60(X31+X32)+40(X41+X42)≥50，70(X11+X12+X13)+50(X21+X22+X23)+60(X31+X32+X33)+40(X41+X42+X43)≥70，70(X11+X12+X13+X14)+50(X21+X22+X23+X24)+60(X31+X32+X33+X34)+40(X41+X42+X43+X44)≥90，70(X11+X12+X13+X14+X15)+50(X21+X22+X23+X24+X25)+60(X31+X32+X33+X34+X35)+40(X41+X42+X43+X44+X45)≥110作业:9468585910697358486951053681642525104137526241505742minZ′=∑∑(-cij)xijminZ〞=∑∑(M-cij)xij其中M是一大的常数目标函数极大化maxZ=∑∑cijxij0310234003115406020303530第八章图与网络分析图论的起源哥尼斯堡七桥问题ABDCABCD一笔划问题V1V2V3V5V4中国邮递员问题（管梅谷）右图为一街道图。点表示街口，线表示街道。v点处有一邮局。某邮递员从邮局v出发送邮件，需每条街至少经过一次，最后回到邮局。问他应怎样选择路线，才能使走的路程最短？v图的基本概念图:反映现象之间关系的工具,由点和点间连线组成。如四国单循环制足球邀请赛，以图表示赛制V1V2V3V4例:（V1）张林（V2）孙（V3）（V4）李吴（V6）王（V5）郑（V7）（V1）张孙（V2）林（V3）（V4）李吴（V6）王（V5）郑（V7）若以图表示比赛结果V1V2V3V4（V1）张王（V2）孙（V3）（V4）李吴（V6）林（V5）郑（V7）无向图•两点间不带箭头的联线称边边的集合记为E点的集合记为V•一个由点及边构成的图，称为无向图，记为G=(V,E)V1V2V3V4有向图•两点间带箭头的联线称弧弧的集合记为A•一个由点及弧构成的图，称为有向图，记为D=(V,A)V1V2V3V4点的次•以点v为端点的边的个数称为点v的次•次为1的点——悬挂点•次为0的点——孤立点天津南京常州上海杭州郑州连云港济南徐州台北链和圈•链中，若vi1=vik，则称此链为一个圈。•一个点边交错的序列(vi1,ei1,vi2,ei1,…vik-1,eik-1,vik)称为一条联结vi1和vik链。V1V2V3V5V4e1e3e2e4e5e6e7连通图•图G=(V,E)中，若任何两点之间，至少有一条链，则称G为连通图，否则为不连通图。路和回路•在有向图中，若点弧交错形成的链中弧方向均相同，则为一条路。•有向图中若点弧交错形成的圈中弧方向均相同，则为一条回路。v7v6v5v4v3v26341014366122410v8v1支撑子图•给定图G=(V,E)，若有图G′=(V′,E′)，使V′=V,E′∈E，则G′称G是的一个支撑子图。V1V2V3V5V4e1e3e2e4e5e6e7V1V2V3V5V4e1e3e2e5e6树一个无圈的连通图为树。树的性质如下：•必有次为1的点，称为树叶。•树是无回路的连通图，所以任意两点之间有且仅有一条通路，任意去掉一个树枝，树被分成不连通图。天津南京常州上海郑州连云港济南徐州树•树的任意两个顶点间加一条边，构成一个回路，不再成为树。•一个连通图有很多树，这些树都是原连通图的部分图，即包括了原连通图的所有顶点。天津南京常州上海郑州连云港济南徐州支撑树•若图T=(V,E′)是图G=(V,E)的支撑子图，且G′是一个树，则称T是G的一个支撑树。V1V2V3V5V4e1e3e2e4e5e6e7V1V2V3V5V4e1e2e4e5最小支撑树•在图G=(V,E)中，对每条边[vi,vj]相应给一个数wij，则G为赋权图，wij称为边[vi,vj]上的权。权可表示距离、时间、费用等。w12w25w23w34w45w15V1V2V3V5V4w25最小支撑树•若T=(V,E′)是图G=(V,E)的一个支撑树，则E′中所有边的权之和为支撑树T的权。•若支撑树T﹡的权w（T﹡）是G的所有支撑树的权中最小者，则称T﹡是G的最小支撑树（最小树）。w12w25w23w34w45w15V1V2V3V5V4w25w12w23w45w15V1V2V3V5V4w12w23w34w45V1V2V3V5V4w12w23w34V1V2V3V5V4w25w12w25w23w34w45w15V1V2V3V5V4254453v1v2v3v4243v1v2v3v4最小支撑树的避圈法w（T﹡）=9最小支撑树的破圈法254453v1v2v3v4254453v1v2v3v4w（T﹡）=9例：某大学准备对所属的7个学院办公室计算机联网，可能连通的途径如图，请设计一个铺线方法既能连通7个学院办公室，又使总的线路长度最短。v1v2v3v4v5v6125333748v7104v1v2v3v4v5v6125333748v7123337v1v2v3v4v5v6v7104w（T﹡）=19最短路问题v1v8v7v6v5v4v3v26341014366122410﹢∞﹢∞﹢∞﹢∞＼v16v13v11v411v59v35v26v510v512＼＼＼＼＼＼＼＼0Dijkstra标号法•使用两种标号给图中每一点vi标号：T标号（Temporarylabel），P标号（Permanentlabel）。•给vi点一个P标号时，表示从始点vs到vi点的最短路权，此标号不再改变；给vi点一个T标号时，表示从vs到vi点的最短路权的上界，是一种临时标号，没有得到P标号的点都是T标号。•计算的每一步就是把某一点的T标号改为P标号，当所有点都得到P标号时，计算结束。Dijkstra标号法步骤1、给始点vs以P标号，P(vs)=0，其余各点给T标号，T（vi）=﹢∞2、若vi点为刚得到P标号的点，考虑与vi相邻的另一顶点vj，且vj为T标号。对vj的T标号进行如下更改：T（vj）=min[T（vj）,P(vi)+Lij]3、比较所有具有T标号的点，把最小者改为P标号若全部点均为P标号则停止，否则转回第2步。无向图的Dijkstra标号法v1v9v8v7v6v5v4v3v26334210143662122﹢∞＼65＼﹢∞3＼﹢∞＼﹢∞7＼﹢∞1110＼＼﹢∞8＼1﹢∞9＼﹢∞12＼＼6＼110用最短路解设备更新问题v1v2v3v4v5v6161822413022301659312317412317V1，0V1，16V1，22V1，41V1，30V1，59V2，57V3，53V4，53年数0-11-22-33-44-5费用5681118年份12345价格1111121213v1v2v3v4v5v6161822413022301659312317412317V1，0V1，16V1，22V1，41V1，30V1，59V2，57V3，53V4，53网络最大流问题vsv4v2vt（4，3）（3，2）（5，2）（1，1）（5，3）（2，1）v3v1（4，2）例：流量容量基本概念1、网络在有向连通图D=(V,A)中，D的每条弧上有非负数的权Cij（弧的容量），且存在一个发点Vs和一个收点Vt，则称此D为网络。记为：D=(V,A,C)vsv3v4v2v1vt2411532532、流•在网络D=(V,A,C)中，对任一弧（vi,vj）有流量fij，称集合f={fij}为网络上的一个流。vsv3v4v2v1vt（4，3）（3，3）（5，1）（1，1）（3，0）（2，2）（5，3）（2，1）Cij（1，1）2、流•如：vsv3v4v2v1vt3311023113、可行流vsv3v4v2v1vt（4，3）（3，3）（5，1）（1，1）（3，0）（2，2）（5，3）（2，1）（1，1）（3，4）（5，2）3、可行流•满足下列条件的流称为可行流。（1）容量限制条件：0≤fij≤Cij（2）平衡条件：对于中间点：流入的流量=流出的流量对于发点Vs和收点Vt：Vs的流出量=Vt的流入量•对于一个网络，可行流