2023年大学运筹学课程知识点总结

用图解法求解下列线性规划问题,并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。２.将下述线性规划问题化成标准形式。（1)解:令,3.分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解相应图解法中的可行域的哪个顶点。解：＝1\＊GB3①图解法:=2\＊GB3②单纯形法：将原问题标准化：Ｃｊ10500相应图解法中的点ＣＢBbｘ1x2x３ｘ4０x３9３４10３Ｏ点0x４8[5］２018／5j01０5０0０ｘ3２1/50[14/5]1-3／53/2C点10x18／５12/5０1/54j-1６010-２5x23/２015/1４-３/1４B点10ｘ1１10-1/7２/7ｊ３5/2０0-5／14-25/1４最优解为（1,3/2,0,0),最优值Ｚ＝35/2。单纯型法环节:转化为标准线性规划问题;找到一个初始可行解，列出初始单纯型表;最优性检查,求cj-ｚj,若所有的值都小于0，则表中的解便是最优解，否则，找出最大的值的那一列，求出ｂi/aij，选取最小的相相应的xｉj,作为换入基进行初等行变换，反复此环节。4.写出下列线性规划问题的对偶问题。（１）（2)5．给出线性规划问题规定：（1)写出其对偶问题;（２)已知原问题最优解为,试根据对偶理论，直接求出对偶问题的最优解。解:（1）（2)由于,第四个约束取等号,根据互补松弛定理得：求得对偶问题的最优解为：，最优值miｎｗ＝1６。弱对偶性的推论：(1)原问题任一可行解的目的函数值是其对偶问题目的函数值的下界;反之对偶问题任一可行解的目的函数值是其原问题目的函数值的上界（２)如原问题有可行解且目的函数值无界(具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目的函数值无界，则其原问题无可行解。注意:本点性质的逆不成立，当对偶问题无可行解时,其原问题或具有无界解或无可行解,反之亦然。(3)若原问题有可行解而其对偶问题无可行解，则原问题目的函数值无界;反之对偶问题有可行解而其原问题无可行解,则对偶问题的目的函数值无界。强对偶性(或称对偶定理)若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目的函数值相等。互补松弛性在线性规划问题的最优解中，假如相应某一约束条件的对偶变量值为非零,则该约束条件取严格等式;反之假如约束条件取严格不等式，则其相应的对偶变量一定为零。影子价格资源的市场价格是其价值的客观体现，相对比较稳定，而它的影子价格则有赖于资源的运用情况,是未知数。因公司生产任务、产品结构等情况发生变化,资源的影子价格也随之改变。影子价格是一种边际价格。资源的影子价格事实上又是一种机会成本。随着资源的买进卖出,其影子价格也将随之发生变化,一直到影子价格与市场价格保持同等水平时，才处在平衡状态。生产过程中假如某种资源未得到充足运用时，该种资源的影子价格为零;又当资源的影子价格不为零时，表白该种资源在生产中已花费完毕。影子价格反映单纯形表中各个检查数的经济意义。一般说对线性规划问题的求解是拟定资源的最优分派方案，而对于对偶问题的求解则是拟定对资源的恰当估价,这种估价直接涉及资源的最有效运用对偶单纯型法:转化成标准的线性规划问题;拟定换入基变量，bi小于０中的最小的那一排,再求(ｃj－ｚｊ)/aｉj，且ａｉｊ<0,找出最小值,这相应的xｉ便是换入基,若所有的ｂi都大于0,则找到了最优解7下列表分别给出了各产地和各销地的产量和销量，以及各产地至各销地的单位运价,试用表上作业法求最优解。注意要基可行解的个数一定是行列变量数减一销地产地B1Ｂ２B3B4产量A141４６８A２１２5０8A337514销量656３２０解：(1）拟定初始方案西北角法：销地产地B1Ｂ2Ｂ3B4产量Ａ1６28A2３５8Ａ31３4销量65632０最小元素法：销地产地B1Ｂ2B3Ｂ4产量A1５38A２53８A313４销量65632０沃格尔法:销地产地B1B2B3B4产量行罚数1234A141４６8ｅq\o\ac(○,３)0２２5３Ａ2１2５0８1１eq\o\ac(○,5)６2Ａ3３75１４1244３１销量65６320列罚数1２１１12eｑ＼ｏ\ａｃ（○,2）113１1４1eｑ＼o＼ac(○,5)8.下表给出一个运送问题及它的一个解，试问:（１)表中给出的解是否为最优解？请用位势法进行检查。(2）若价值系数C２4由1变为3，所给的解是否仍为最优解？若不是，请求出最优解。(３）若所有价值系数均增长1，最优解是否改变?为什么?(4）若所有价值系数均乘以2，最优解是否改变?为什么？销地产地B1B2B3B4产量Ａ1４１46853Ａ21261108２A３３７51431销量856３2２解:(1)销地产地B1B2B3B4产量uiA１4１4６８0５3A2１2６110182Ａ3375141３1销量8５６３２２vｊ０1４0空格检查数为:46０125所有检查数均大于等于零,该方案为最优方案。(2）若价值系数C24由１变为３,66-２－145由于有检查数小于零,所以此方案不是最优方案。5（-2）3（＋2）8(+2)2(-2)3（-2)１（＋2)调整为：35８213空格检查数为：46122５所有检查数均小于等于零,该方案为最优方案。。（3)不改变,不影响检查数的大小。(４）不改变,不影响检查数的符号。解的最优性检查:1.闭回路法：找各个非基变量的闭合回路，依次加减求检查数，是先减再加，若所有的检查数的值都全非负，那么此可行解是最优解。2.位势法（对偶变量法）:增长位势列ui和位势行vj；计算位势，ｕi+ｖj=基可行解的相应的运费,指定其中某一值为0,算出其他几位的值，填入表中;计算检查数,某非基变量相应的运费减相应的位势行和位势列，若检查数全为非负,则为最优解。(检查数都是非基变量通过解决后的值,解决过程中应用的是基变量）解的改善:１.以检查数小于0的xi为换入基（取最小的那个)找此ｘｉ的闭合回路,以xｉ为始沿顺逆时针方向把定点依次编号在所有偶数顶点中，找出运送量最少的顶点作为ｘi的换出变量将基数顶点的运送量增长ｘj,偶数顶点的运送量减少ｘj,重新得到一组新的方案进行解的最优性检查9.公司决定使用1000万元新产品开发基金开发Ａ,B,Ｃ三种新产品。经预测估计，开发A，Ｂ，C三种新产品的投资利润分别为5％、7%、10%。由于新产品开发有一定风险,公司研究后拟定了下列优先顺序目的:第一，Ａ产品至少投资300万元;第二,为分散投资风险,任何一种新产品的开发投资不超过开发基金总额的3５%;第三,应至少留有１0％的开发基金,以备急用；第四，使总的投资利润最大。试建立投资分派方案的目的规划模型。解，设A,B，Ｃ三种新产品的开发投资额分别为万元，目的规划模型为:Pl是优先因子，关系为ｌ越小,则有绝对的优先性,尚有一种是相对的优先性，用权系数来表达目的规划的一般格式;ｍiｎ{ｐld+或d-}(要明白为什么是写ｄ+或d-,min里的ｄ是要取值为零的，即若不等式要大于零时,则写d-）;必须要满足的绝对约束,尚有目的约束;xｊ>0,d+,d－>０目的规划的图解法：先画绝对约束的可行域,然后按照优先性优先考虑某个目的约束，随着min系数中d+或者d-的增大移动曲线,画出最合适的那条，直到最后１0.用割平面法解下列整数规划：（１)解：引进松弛变量,将问题化为标准形式，用单纯形法解其松弛问题。ｃｊ11０0CBXBbx1x２x3x4０ｘ3６【2】11030x４２0４5015j１10０１ｘ1311／21/２０60ｘ480【３】－２１８/3ｊ0１/2-1／20１x15/3105／6-1/61x28/30１-2/31/3j00-1/６－1/6找出非整数解变量中分数部分最大的一个基变量（x2）,并写下这一行的约束：将上式中的所有常数分写成整数与一个正的分数值之和得:将上式中的分数项移到等式右端,整数项移到等式左端得：得到割平面约束为：引入松弛变量,得割平面方程为:cj１１０00ＣBXBｂｘ1x2x3x4ｘ51x15/3105／6－1/601x２８／３0１-2/3１/300x5-2/300【－1／３】-１/31ｊ00－1/６-1/6０j/arj１/２1/2１ｘ１0100-15/２1x24010１－２0x3200１1-3ｊ0000－1/2最优解为,最优值为4＝0,最优解不唯一？11.用分支定界法解下列整数规划(1）解:最优解(３,１)，最优值z=7。匈牙利解法:见课本145页１３．如图，是一仓库,是商店，求一条从到的最短路。解：P=T=0T＝T=T=T＝T=T＝T=T=T=P=Ｔ=２T=T＝11T=T＝７T=T=4T＝T=T=１3Ｔ=11T＝T=７Ｔ=P=T=４T=T＝T=13T=11T＝P＝T＝７Ｔ＝１１T=１3T=T=13P=Ｔ=11Ｔ=T＝１1T＝13T=T＝13T=1６P=T=11T=13Ｔ=Ｐ=Ｔ=13T=１6Ｔ=13T=2０T=16P=T=13T=１９P=T=1６T=1９Ｐ=19最短路长为1９。最短路为：0１2９，032９，0349,0１249,0７89。14.如图,发点,分别可供应1０和15个单位,收点，可以接受10和25个单位