运筹学课程讲义

《运筹学课程讲义》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运筹学课程讲义第一部分线性规划第一章线性规划的基本性质1.1线性规划的数学模型一、线性规划问题的特点胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子售价30元/个。生产桌子和椅子需木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？例：某工厂生产某一种型号的机床。每台机床上需要2.9m、2.1m、1.5m的轴，分别为1根、2根和1根。这些轴需用同一种圆钢制

2、作，圆钢的长度为74m。如果要生产100台机床，问应如何安排下料，才能用料最省？二、数学模型的标准型1.繁写形式2.缩写形式3.向量形式4.矩阵形式一、任一模型如何化为标准型？1.若原模型要求目标函数实现最大化，如何将其化为最小化问题？2.若原模型中约束条件为不等式，如何化为等式？3.若原模型中变量xk是自由变量，如何化为非负变量？4.若原模型中变量xj有上下界，如何化为非负变量？令1.2图解法该法简单直观，平面作图适于求解二维问题。使用该法求解线性规划问题时，不必把原模型化为标准型。一、图解法步骤1.由全部约束条件

3、作图求出可行域2.作出一条目标函数的等值线3.平移目标函数等值线，作图求解最优点，再算出最优值二、从图解法看线性规划问题解的几种情况1.有唯一最优解2.有无穷多组最优解3.无可行解4.无有限最优解（无界解）最优解，最优值3直观结论：1）线性规划问题的可行域为凸集，特殊情况下为无界域（但有有限个顶点）或空集；2）线性规划问题若有最优解，一定可以在其可行域的顶点上得到。1.3线性规划的基本概念和基本定理一、线性规划问题的基与解可行解最优解基基向量非基向量基变量非基变量基本解基本可行解最优基本可行解退化的基本解一、几何意义

4、上的几个基本概念1.凸集2.凸组合3.顶点二、线性规划问题的基本定理定理1：若线性规划问题存在可行域，则其可行域是凸集。引理1：线性规划问题的可行解为基本可行解的充要条件是X的正分量对应的系数列向量是线性无关的。定理2：线性规划问题的基本可行解对应于可行域的顶点。引理2：K是有界凸集，则任何一点XK可表示为K的顶点的凸组合。定理3：如果线性规划问题有有限最优解，则其目标函数最优值一定可以在可行域的顶点上达到。三、求解线性规划问题的基本思路在有限个基本可行解中寻找最优基本可行解。找一个基本可行解（m个线性无关的系数列向

5、量），由其换到另一个基本可行解。实质即为换基。前提是保证新的基本可行解的目标函数值比原来的更优而不是更劣。第二章单纯形法它是求解线性规划最为成熟的算法。胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子售价30元/个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？将其变形，得将对应的单位矩阵作为初始可行基。令为基变量，为非基变量。原模

6、型变形为如果令非基变量等于零，得一个基本可行解（0，0，120，50），对应的目标函数值z=0最优性检验：该解是否最优？显然不是。经济意义分析：等于零意味着家具厂不开工生产，销售收入为零，资源未得到充分利用。数学角度分析：非基变量前的系数都为正，表明目标函数值有增加的可能。只要将系数为正的非基变量与某一基变量对换，当换入变量的值增加时，目标函数值就可能增加。换基迭代：寻找下一个可行解需要进行换基迭代。换基后需满足：（1）新的解仍是基本可行解；（2）目标函数得到改善。选择入基变量：系数均为正。对求目标函数极大化的问题，

7、我们希望目标值增加得越快越好，因此应选系数最大的入基。选择出基变量：入基后，其值从零增加并引起其他变量取值的变化。由问题的典则表达式和变量必须取正值的条件，得下列不等式关系：因迭代后仍为取零值的非基变量，上式可简化为很明显，只有选时，才能使上述不等式成立，并使基变量变为零，正好满足非基变量必须为零的条件，所以可令出基，新的典则方程变为化简后得代入目标函数可得得到下一个基本可行解（25，0，20，0），并完成了第一次迭代。新解是最优解吗？需进行最优检验。由于目标函数中的系数仍为正，说明多生产椅子仍有利可图，该解仍不是最

8、优解。再次迭代。入基，出基，换基后典则形式变为第三个基本可行解为（15，20，0，0），松弛变量都已为零，表明资源已得到充分利用；非基变量在目标函数中的系数全为负值，说明目标函数已无法进一步改善，因此该解已是最优解。2.1单纯形法原理一、构造初始可行基1.引入附加变量，把数学模型化为标准型2.若约束条件中附加变量的系数是-1或原约束即为等式，则