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

1、精选学习资料 - - - 欢迎下载1.用图解法求解以下线性规划问题,并指出问题具有惟一最优解.无穷多最优解.无界解仍为无可行解；精品学习资料精选学习资料 - - - 欢迎下载max z6x1x110x2x2120精品学习资料精选学习资料 - - - 欢迎下载5x1103x282.将下述线性规划问题化成标准形式；精品学习资料精选学习资料 - - - 欢迎下载（ 1）min z4x1x2 x1x23x12x3 x34x2x4 2x42x32145x4精品学习资料精选学习资料 - - - 欢迎下载2x13x2x3x42精品学习资料精选学习资料 - - - 欢迎下载x1、 x2、 x30、 x4无约束

2、精品学习资料精选学习资料 - - - 欢迎下载解：令 z'z , x4'''xx44精品学习资料精选学习资料 - - - 欢迎下载max z'4 x3x1x4x22 x2x34x '5x '4x ''25x ' '精品学习资料精选学习资料 - - - 欢迎下载12x1x2x3342 x'44452x ''x14精品学习资料精选学习资料 - - - 欢迎下载2 x13x2''xx'xx23446精品学习资料精选学习资料 - - - 欢迎下载x1 、 x2、 x3

3、、 x '、 x'' 、 x、 x60精品学习资料精选学习资料 - - - 欢迎下载4453.分别用图解法和单纯形法求解下述线性规划问题,并对比指出单纯形表中的各基可行解对应精品学习资料精选学习资料 - - - 欢迎下载图解法中的可行域的哪个顶点；精品学习资料精选学习资料 - - - 欢迎下载max z 3 x15 x1x1 、 x210x14 x292 x2805x2精品学习资料精选学习资料 - - - 欢迎下载解：图解法：单纯形法：将原问题标准化：精品学习资料精选学习资料 - - - 欢迎下载max z 3x15 x110x14 x22 x25 x2x39x48精品

4、学习资料精选学习资料 - - - 欢迎下载x1、 x2 、 x3 、 x40对应图解法中的点精品学习资料精选学习资料 - - - 欢迎下载cj10500cbbbx 1x 2x 3x40x 39341030x 4852018/5j0105000x 321/5014/51-3/53/210x 18/512/501/54j-16010-25x 23/2015/14-3/1410x 1110-1/72/7j35/200-5/14-25/14o 点c 点b 点最优解为（ 1、3/2、0、0 ）,最优值z=35/2 ；精品学习资料精选学习资料 - - - 欢迎下载单纯型法步骤：转化为标准线性规划问题；找到

5、一个初始可行解,列出初始单纯型表；最优性检验,求 cj-zj ,如全部的值都小于 0,就表中的解便为最优解,否就,找出最大的值的那一列,求出 bi/aij ,选取最小的相对应的 xij ,作为换入基进行初等行变换,重复此步骤；4.写出以下线性规划问题的对偶问题；精品学习资料精选学习资料 - - - 欢迎下载minznmni 1j 1c ijxij精品学习资料精选学习资料 - - - 欢迎下载（1）s.t .x ija ij 1mx ijb ji1、 mj1、 n精品学习资料精选学习资料 - - - 欢迎下载i 1精品学习资料精选学习资料 - - - 欢迎下载x ij0mi1、n、 m ; j1

6、、 n精品学习资料精选学习资料 - - - 欢迎下载max wai yii 1b j y jmi 1精品学习资料精选学习资料 - - - 欢迎下载精品学习资料精选学习资料 - - - 欢迎下载yis.t.ymjciji1、 m; j1、 n精品学习资料精选学习资料 - - - 欢迎下载xi 、max zy j 无约束nc j x j精品学习资料精选学习资料 - - - 欢迎下载（2）s.t .j 1naij x jbij 1 naij x jbij 1i1、im1m1m1、 m12、 m精品学习资料精选学习资料 - - - 欢迎下载精品学习资料精选学习资料 - - - 欢迎下载x j0j x

7、j 无约束m1、n1njn11、 n精品学习资料精选学习资料 - - - 欢迎下载min wmbi yii 1aij yic jj1、2、n1n精品学习资料精选学习资料 - - - 欢迎下载i 1 ms.t.i 1aij yic jjn11、 n精品学习资料精选学习资料 - - - 欢迎下载yi0i1、 2、m1m精品学习资料精选学习资料 - - - 欢迎下载yi 无约束im11、 m精品学习资料精选学习资料 - - - 欢迎下载5. 给出线性规划问题精品学习资料精选学习资料 - - - 欢迎下载max zx1 2x1s.t.x12x13x2x2x2x24x2x3x4x486x3x46x39精

8、品学习资料精选学习资料 - - - 欢迎下载xj0 j1、4精品学习资料精选学习资料 - - - 欢迎下载要求：（ 1）写出其对偶问题； （ 2）已知原问题最优解为x *接求出对偶问题的最优解；解：2、2、4、0t,试依据对偶理论,直精品学习资料精选学习资料 - - - 欢迎下载min wy1 3y1（1）8 y12 y2y26 y2y36 y3y4y49 y424精品学习资料精选学习资料 - - - 欢迎下载s.t .y1y j0 jy3y41y311、4精品学习资料精选学习资料 - - - 欢迎下载（2）由于x1 、 x2 、 x30 ,第四个约束取等号,依据互补放松定理得：精品学习资料精

9、选学习资料 - - - 欢迎下载y1 3 y12 y2y2y42y3y44y3y41y40*43精品学习资料精选学习资料 - - - 欢迎下载求得对偶问题的最优解为：y、1、055,最优值min w=16 ；精品学习资料精选学习资料 - - - 欢迎下载例已知原问题max z =x1 + 2 x 2 + 3 x 3 + 4 x 4x 1 + 2 x 2 + 2 x 3 + 3 x 4 2042x 1 + x 2 + 3 x 3 + 2 x20精品学习资料精选学习资料 - - - 欢迎下载和对偶问题x 1. x 2 . x 3 .x 4 0min w =20y1 + 20 y 2y 1 + 2

10、y 2 12y 1 + y 222y 1 + 3 y 2 33y 1 + 2 y 2 4y 1 . y 2 0精品学习资料精选学习资料 - - - 欢迎下载已知对偶问题的最优解y 1 = 1.2 . y 2 =0.2 ,最优值min w=28,求原问题的最优解及最优值；精品学习资料精选学习资料 - - - 欢迎下载可用如下方法求解：引入将原问题和对偶问题化为标准形式；max z =x1 + 2x2 + 3x3 + 4x4x1 + 2 x2 + 2x3 + 3x4 + x5= 202x1 + x2 + 3x3 + 2x4+ x6 =20x1.x2.x3 .x4 .x5 .x6 0和min w =

11、20y 1 + 20 y2y1 + 2y2 y3= 12y1 + y2 y4= 22y1 + 3y2 y5= 33y1 + 2y2 y6 = 4y1.y2 .y3 . y4 .y5 . y6 0（1） y1=1.2>0,而y1与x5中至少有一个为零,故x5 =0；（ 2）同理,y2=0.2>0 ,所以 x6 =0 ；（3）对偶问题的第一个约束条件在取最优值时y1+2y2=1.2+2 × 0.2=1.6>1这就表示该约束条件的放松变量：y3=1.6 1=0.6>0y3与x1中至少有一个为零,故x1=0 ；（ 4）同理,对于第2个约束条件在取得最优值时2y1+y2

12、 = 2× 1.2+0.2=2.6>2y4=2.6 2=0.6>0y4与x2中至少有一个为零,故x2=0；精品学习资料精选学习资料 - - - 欢迎下载（ 5）同理,对于第3个约束条件在取得最优值时2y1+3y2 = 2× 1.2+ 3 × 0.2=3y5=3 3=0y5与x3中至少有一个为零,故x3>0或者 x3=0 ；（ 6）对于第 4个约束条件的分析也可得到x4>0 或者 x4=0 ；对于（ 5） 和（ 6）的分析,对于确定原问题的最优解没有任何帮忙；但从（1）到（ 4）的分析中得知,原问题取得最优解时：x5=0 , x6=0, x1

13、= 0, x2=0代入原问题的约束方程组得：2x3+3x4= 203x3+2x4= 20解此方程组,可求得原问题的最优解为：x1=0, x2=0 , x3=4 , x4 =4 , x5=0 , x6=0弱对偶性的推论：(1) 原问题任一可行解的目标函数值为其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值为其原问题目标函数值的上界(2) 如原问题有可行解且目标函数值无界 具有无界解 ,就其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界,就其原问题无可行解；留意：本点性质的逆不成立,当对偶问题无可行解时,其原问题或具有无界解或无可行解,反之亦然；(3) 如原问题有可行解而其对

14、偶问题无可行解,就原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解,就对偶问题的目标函数值无界；强对偶性 或称对偶定理 如原问题及其对偶问题均具有可行解,就两者均具有最优解,且它们最优解的目标函数值相等；互补放松性在线性规划问题的最优解中,假如对应某一约束条件的对偶变量值为非零,就该约束条件取严格等式；反之假如约束条件取严格不等式,就其对应的对偶变量肯定为零；影子价格资源的市场价格为其价值的客观表达,相对比较稳固,而它的影子价格就有赖于资源的利用情形,为未知数；因企业生产任务.产品结构等情形发生变化,资源的影子价格也随之转变；影子价格为一种边际价格；资源的影子价格实际上又为一种机会

15、成本；随着资源的买进卖出,其影子价格也将随之发生变化,始终到影子价格与市场价格保持同等水平常,才处于平稳状态； 生产过程中假如某种资源未得到充分利用时,该种资源的影子价格为零；又当资源精品学习资料精选学习资料 - - - 欢迎下载的影子价格不为零时,说明该种资源在生产中已耗费完毕；影子价格反映单纯形表中各个检验数的经济意义；一般说对线性规划问题的求解为确定资源的最优安排方案,而对于对偶问题的求解就为确定对资源的恰当估价,这种估价直接涉及资源的最有效利用对偶单纯型法： 转化成标准的线性规划问题； 确定换入基变量, bi 小于 0 中的最小的那一排,再求（ cj-zj ）/aij ,且 aij&l

16、t;0、 找出最小值,这对应的 xi 便为换入基, 如全部的 bi 都大于 0,就找到了最优解7 以下表分别给出了各产地和各销地的产量和销量,以及各产地至各销地的单位运价,试用表上作业法求最优解；留意要基可行解的个数肯定为行列变量数减一销地b1b2b 3b 4产量a 141468a 212508a 337514销量656320产地解：（1）确定初始方案西北角法：b 2b 3b 4产量a 1628a 2358a 3134销量656320最小元素法：销地产地b1销地产地b 1b2b 3b 4产量精品学习资料精选学习资料 - - - 欢迎下载a 1538a 2538a 3134销量656320沃格尔

17、法：销地行罚数产地b1b2b3b 4产量1234精品学习资料精选学习资料 - - - 欢迎下载a 141468302253精品学习资料精选学习资料 - - - 欢迎下载a 261250811541244202精品学习资料精选学习资料 - - - 欢迎下载a 3375131销量6563精品学习资料精选学习资料 - - - 欢迎下载列12111罚221 1数3114158.下表给出一个运输问题及它的一个解,试问：（1）表中给出的解为否为最优解？请用位势法进行检验；（2）如价值系数c24 由 1 变为 3,所给的解为否仍为最优解？如不为,恳求出最优解；（3）如全部价值系数均增加1,最优解为否转变？为

18、什么？（4）如全部价值系数均乘以2,最优解为否转变？为什么？销地产地b 1b2b 3b4产量精品学习资料精选学习资料 - - - 欢迎下载a 14146853精品学习资料精选学习资料 - - - 欢迎下载a 281261102精品学习资料精选学习资料 - - - 欢迎下载a 33751431精品学习资料精选学习资料 - - - 欢迎下载销量856322解：（ 1）销地产地b1b 2b3b4产量ui精品学习资料精选学习资料 - - - 欢迎下载a 141534680精品学习资料精选学习资料 - - - 欢迎下载a 2812611012精品学习资料精选学习资料 - - - 欢迎下载a 337351

19、411精品学习资料精选学习资料 - - - 欢迎下载销量856322vj0140空格检验数为：460125全部检验数均大于等于零,该方案为最优方案；（2）如价值系数c24 由 1 变 为 3,66-2-145由于有检验数小于零,所以此方案不为最优方案；5（ -2）3（ +2）8（ +2 ）2（ -2）3（ -2）1（ +2）调整为：358213精品学习资料精选学习资料 - - - 欢迎下载空格检验数为：461225全部检验数均小于等于零,该方案为最优方案；精品学习资料精选学习资料 - - - 欢迎下载min z31548122153143 ；精品学习资料精选学习资料 - - - 欢迎下载（3）

20、不转变,不影响检验数的大小；（4）不转变,不影响检验数的符号；解的最优性检验：1. 闭回路法：找各个非基变量的闭合回路,依次加减求检验数,为先减再加,如全部的检验数的值都全非负,那么此可行解为最优解；2. 位势法（对偶变量法）：增加位势列ui和位势行vj ；运算位势,ui+vj=基可行解的对应的运费,指定其中某一值为0,算出其他几位的值,填入表中；运算检验数,某非基变量对应的运费减对应的位势行和位势列, 如检验数全为非负,就为最优解；（检验数都为非基变量经过处理后的值,处理过程中应用的为基变量）解的改进： 1. 以检验数小于0 的 xi为换入基（取最小的那个）2. 找此xi的闭合回路, 以 x

21、i为始沿顺逆时针方向把定点依次编号3. 在全部偶数顶点中,找出运输量最少的顶点作为xi的换出变量4. 将基数顶点的运输量增加xj ,偶数顶点的运输量削减xj , 重新得到一组新的方案5. 进行解的最优性检验9.公司打算使用1000 万元新产品开发基金开发a ,b,c 三种新产品； 经猜测估量, 开发 a ,b ,c 三种新产品的投资利润分别为5%.7%.10% ；由于新产品开发有肯定风险,公司讨论后确定了以下优先次序目标：第一, a 产品至少投资300 万元；其次,为分散投资风险,任何一种新产品的开发投资不超过开发基金总额的35% ；第三,应至少留有10%的开发基金,以备急用；第四,使总的投资

22、利润最大；试建立投资安排方案的目标规划模型；精品学习资料精选学习资料 - - - 欢迎下载解,设 a , b, c 三种新产品的开发投资额分别为x1 、 x2 、 x3 万元,目标规划模型为：精品学习资料精选学习资料 - - - 欢迎下载minp1d 1、 p2 d 2d 3d 4 、 p3 d5、 p4 d 6精品学习资料精选学习资料 - - - 欢迎下载x1d1d1300x1d 2d 2100035%x2d 3d 3100035%s.t.x3d 4d 4100035%精品学习资料精选学习资料 - - - 欢迎下载1000x1x2x3d 5d 5100010%精品学习资料精选学习资料 - -

23、 - 欢迎下载精品学习资料精选学习资料 - - - 欢迎下载5% x17% x210% x3d6d 6100010%精品学习资料精选学习资料 - - - 欢迎下载精品学习资料精选学习资料 - - - 欢迎下载x1 、 x2 、 x3 、 di、 d i0 i1、6精品学习资料精选学习资料 - - - 欢迎下载pl为优先因子,关系为l越小,就有肯定的优先性,仍有一种为相对的优先性,用权系数来表示目标规划的一般格式;minpld+或 d-（要明白为什么为写d+或 d- ,min 里的 d 为要取值为零的,即如不等式要大于零时,就写d- ）；必需要满意的肯定约束,仍有目标约束；xj>0、d+、

24、d->0目标规划的图解法： 先画肯定约束的可行域, 然后依据优先性优先考虑某个目标约束,随着 min 系数中 d+或者 d- 的增大移动曲线,画出最合适的那条,直到最终10.用割平面法解以下整数规划：精品学习资料精选学习资料 - - - 欢迎下载max z2 x1（1）x1x2x26精品学习资料精选学习资料 - - - 欢迎下载s.t . 4 x15 x220精品学习资料精选学习资料 - - - 欢迎下载x1 、 x2解：引进放松变量0、 且为整数x3 、 x4 ,将问题化为标准形式,用单纯形法解其放松问题；精品学习资料精选学习资料 - - - 欢迎下载cj1100cbx bbx1x 2

25、x 3x 40x 36【2】11030x 42045015j11001x 1311/21/2060x 480【 3】-218/3j01/2-1/201x 15/3105/6-1/61x 28/301-2/31/3j00-1/6-1/6找出非整数解变量中分数部分最大的一个基变量（x2）,并写下这一行的约束：精品学习资料精选学习资料 - - - 欢迎下载x2x2331 x2 2433精品学习资料精选学习资料 - - - 欢迎下载将上式中的全部常数分写成整数与一个正的分数值之和得：精品学习资料精选学习资料 - - - 欢迎下载1x21x3301x22433精品学习资料精选学习资料 - - - 欢迎下

26、载将上式中的分数项移到等式右端,整数项移到等式左端得：精品学习资料精选学习资料 - - - 欢迎下载得到割平面约束为：x2x3221 x1 x34333精品学习资料精选学习资料 - - - 欢迎下载引入放松变量x5 ,得割平面方程为：112x3x4333112333cj11000cbx bbx1x 2x 3x 4x51x 15/3105/6-1/601x 28/301-2/31/300x 5-2/300【-1/3】-1/31j00-1/6-1/60j/arj1/21/21x 10100-15/21x 240101-20x 320011-3j0000-1/2x3x4x5精品学习资料精选学习资料 - - - 欢迎下载精品学习资料精选学习资料 - - - 欢迎下载*最优解为x0、4、2、0、0t,最优值为max z4精品学习资料精选学习资料 - - - 欢迎下载4=0 ,最优解不唯独？11.用分支定界法解以下整数规划max z2 x1x2x1x25（1）x1x206 x12 x221精品学习资料精选学习资料 - - - 欢迎下载x1