大学运筹学课程知识点总结材料

实用文档文案大全1.用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。83105120106max212121xxxxxxz2.将下述线性规划问题化成标准形式。（1）无约束4,03,2,12321422245243min4321432143214321xxxxxxxxxxxxxxxxxxxxz解：令zz'，''4'44xxx0,,,,,,232142222455243'max65''4'43216''4'43215''4'4321''4'4321''4'4321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxz3.分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应实用文档文案大全图解法中的可行域的哪个顶点。0,825943510max21212121xxxxxxxxz解：①图解法：②单纯形法：将原问题标准化：0,,,825943510max432142132121xxxxxxxxxxxxzCj10500对应图解法中的点CBBbx1x2x3x40x3934103O点0x48[5]2018/5j0105000x321/50[14/5]1-3/53/2C点10x18/512/501/54j-16010-25x23/2015/14-3/14B点10x1110-1/72/7j35/200-5/14-25/14最优解为（1,3/2,0,0），最优值Z=35/2。实用文档文案大全单纯型法步骤：转化为标准线性规划问题；找到一个初始可行解，列出初始单纯型表；最优性检验，求cj-zj，若所有的值都小于0，则表中的解便是最优解，否则，找出最大的值的那一列，求出bi/aij，选取最小的相对应的xij，作为换入基进行初等行变换，重复此步骤。4.写出下列线性规划问题的对偶问题。（1）njmixnjbxmiaxtsxczijjmiijinjijminjijij,,1;,,10,,1,,1..min1111无约束jiijjminimjjmiiiyxnjmicyytsybyaw,,,1;,,1..max11（2）nnjxnnjxmmmibxammibxatsxczjjinjjijinjjijnjjj,,1,10,,2,1,1..max11111111无约束mmiymmiynnjcyannjcyatsybwiijmiiijjmiiijmiii,,1,2,10,,1,2,1..min1111111无约束实用文档文案大全5.给出线性规划问题4,10966283..42max321432214214321jxxxxxxxxxxxxtsxxxxzj要求：（1）写出其对偶问题；（2）已知原问题最优解为TX0,4,2,2*，试根据对偶理论，直接求出对偶问题的最优解。解：（1）4,10114322..9668min314343214214321jyyyyyyyyyyyytsyyyywj（2）因为0,,321xxx，第四个约束取等号，根据互补松弛定理得：0143224434321421yyyyyyyyyy求得对偶问题的最优解为：0,1,53,54*Y，最优值minw=16。例已知原问题Maxz=x1+2x2+3x3+4x4x1+2x2+2x3+3x4≤202x1+x2+3x3+2x4´≤20x1、x2、x3、x4≥0和对偶问题Minw=20y1+20y2y1+2y2≥12y1+y2≥22y1+3y2≥33y1+2y2≥4y1、y2≥0已知对偶问题的最优解y1=1.2、y2=0.2，最优值minw=28，求原问题的最优解及最优值。实用文档文案大全可用如下方法求解：引入将原问题和对偶问题化为标准形式。Maxz=x1+2x2+3x3+4x4x1+2x2+2x3+3x4+x5=202x1+x2+3x3+2x4+x6=20x1、x2、x3、x4、x5、x6≥0Minw=20y1+20y2y1+2y2－y3=12y1+y2－y4=22y1+3y2－y5=33y1+2y2－y6=4y1、y2、y3、y4、y5、y6≥0和（1）y1=1.20，而y1与x5中至少有一个为零，故x5=0。（2）同理，y2=0.20，所以x6=0。（3）对偶问题的第一个约束条件在取最优值时y1+2y2=1.2+2×0.2=1.61这就表示该约束条件的松弛变量：y3=1.6－1=0.60y3与x1中至少有一个为零，故x1=0。（4）同理，对于第2个约束条件在取得最优值时2y1+y2=2×1.2+0.2=2.62y4=2.6－2=0.60y4与x2中至少有一个为零，故x2=0。实用文档文案大全（5）同理，对于第3个约束条件在取得最优值时2y1+3y2=2×1.2+3×0.2=3y5=3－3=0y5与x3中至少有一个为零，故x30或者x3=0。（6）对于第4个约束条件的分析也可得到x40或者x4=0。对于（5）和（6）的分析，对于确定原问题的最优解没有任何帮助。但从（1）到（4）的分析中得知，原问题取得最优解时：x5=0，x6=0，x1=0，x2=0代入原问题的约束方程组得：2x3+3x4=203x3+2x4=20解此方程组，可求得原问题的最优解为：x1=0，x2=0，x3=4，x4=4，x5=0，x6=0弱对偶性的推论：(1)原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界(2)如原问题有可行解且目标函数值无界(具有无界解)，则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解。注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然。(3)若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。强对偶性(或称对偶定理)若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。互补松弛性在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。影子价格资源的市场价格是其价值的客观体现，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。因企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。影子价格是一种边际价格。资源的影子价格实际上又是一种机会成本。随着资源的买进卖出，其影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；又当资源实用文档文案大全的影子价格不为零时，表明该种资源在生产中已耗费完毕。影子价格反映单纯形表中各个检验数的经济意义。一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及资源的最有效利用对偶单纯型法：转化成标准的线性规划问题；确定换入基变量，bi小于0中的最小的那一排，再求（cj-zj）/aij，且aij0,找出最小值，这对应的xi便是换入基，若所有的bi都大于0，则找到了最优解7下列表分别给出了各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。注意要基可行解的个数一定是行列变量数减一销地产地B1B2B3B4产量A141468A212508A337514销量656320解：（1）确定初始方案西北角法：销地产地B1B2B3B4产量A1628A2358A3134销量656320最小元素法：销地产地B1B2B3B4产量A1538A2538A3134销量656320沃格尔法：销地产地B1B2B3B4产量行罚数1234A141468○302253A21250811○562A337514124431销量656320实用文档文案大全列罚数121112○21131141○58.下表给出一个运输问题及它的一个解，试问：（1）表中给出的解是否为最优解？请用位势法进行检验。（2）若价值系数C24由1变为3，所给的解是否仍为最优解？若不是，请求出最优解。（3）若所有价值系数均增加1，最优解是否改变？为什么？（4）若所有价值系数均乘以2，最优解是否改变？为什么？销地产地B1B2B3B4产量A14146853A212611082A33751431销量856322解：（1）销地产地B1B2B3B4产量uiA141468053A2126110182A337514131销量856322vj0140空格检验数为：460125所有检验数均大于等于零，该方案为最优方案。（2）若价值系数C24由1变为3，66-2-145由于有检验数小于零，所以此方案不是最优方案。5（-2）3（+2）8（+2）2（-2）3（-2）1（+2）调整为：358213实用文档文案大全空格检验数为：461225所有检验数均小于等于零，该方案为最优方案。43135122184513minz。（3）不改变，不影响检验数的大小。（4）不改变，不影响检验数的符号。解的最优性检验：1.闭回路法：找各个非基变量的闭合回路，依次加减求检验数，是先减再加，若所有的检验数的值都全非负，那么此可行解是最优解。2.位势法（对偶变量法）：增加位势列ui和位势行vj；计算位势，ui+vj=基可行解的对应的运费，指定其中某一值为0，算出其他几位的值，填入表中；计算检验数，某非基变量对应的运费减对应的位势行和位势列，若检验数全为非负，则为最优解。（检验数都是非基变量经过处理后的值，处理过程中应用的是基变量）解的改进：1.以检验数小于0的xi为换入基（取最小的那个）2.找此xi的闭合回路，以xi为始沿顺逆时针方向把定点依次编号3.在所有偶数顶点中，找出运输量最少的顶点作为xi的换出变量4.将基数顶点的运输量增加xj，偶数顶点的运输量减少xj，重新得到一组新的方案5.进行解的最优性检验9.公司决定使用1000万元新产品开发基金开发A，B，C三种新产品。经预测估计，开发A，B，C三种新产品的投资利润分别为5%、7%、10%。由于新产品开发有一定风险，公司研究后确定了下列优先顺序目标：第一，A产品至少投资300万元；第二，为分散投资风险，任何一种新产品的开发投资不超过开发基金总额的35%；第三，应至少留有10%的开发基金，以备急用；第四，使总的投资利润最大。试建立投资分配方案的目标规划模型。解，设A，B，C三种新产品的开发投资额分别为321,,xxx万元，目标规划模型为：实用文档文案大全6,,10,,,,%101000%10%7%5%1010001000%351000%351000%351000300..,,,min32166321553214433322211116453432211iddxxxddxxxddxxxddxddxddxddxtsdPdPdddPdPiiPl是优先因子，关系为l越小，则有绝对的优先性，还有一种是相对的优先性，用权系数来表示目标