1、第一章 线性规划与单纯形法本章重点内容线性规划模型与解的主要概念线性规划的单纯形法，线性规划多解分析线性规划的应用 建模1第一节 线性规划问题及数学模型 1939年，（苏） 康托洛维奇 1941年，（美） Hichook 1947年， G. B. Dantzig 单纯形法 1979年，（苏） 哈奇安算法 1984年， Karmarkar算法2设 I、 II两种产品的产量分别为x1, x2 。 建立该问题的数学模型为:例 2 现要做 100套钢架，每套需 2.9米、 2.1米和 1.5米的元钢各一根。已知原料长 7.4米，问如何下料，使余料最少？例 1 (书 P8)I II设 备 1 2 8台时
2、 原材料 A 4 0 16公斤原材料 B 0 4 12公斤设工厂每生产一件产品 I 可获利 2元，每生产一件产品 II 可获利 3元，问应如何安排生产使该厂获利最多？一、实例3解： 设 I, II, III, IV, V分别代表五种不同的原料用量方案 , x1, x2 , x3, x4 , x5分别代表采用各方案下料的元钢的根数。方案 根数 2.9米 2.1米 1.5米 合计 余料I x1 1 0 3 7.4 0II x2 2 0 1 7.3 0.1III x3 0 2 2 7.2 0.2IV x4 1 2 0 7.1 0.3V x5 0 1 3 6.6 0.845 目标函数用决策变量的线性函
3、数来表示。按问题的不同，要求目标函数实现最大化或最小化。 每一个问题变量都用一组决策变量 （ x1, x2, , xn） 表示方案，这组决策变量的值代表一个具体方案，这些变量是非负的。 存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。结论： 线性规划是研究在一组线性不等式或线性等式约束下，使得某一线性目标函数取最大或最小的极值问题。二、线性规划问题（ LP问题）的共同特征6Max(Min) Z=c1x1+c2x2+ +cnxna11x1+a12x2+ +a1nxn ( =, ) b1a21x1+a22x2+ +a2nxn ( =, ) b2s.t. am1x1+am2x2
4、+ +amnxn ( =, ) bmxj0, j=1,2, ， nn 变量个数； m 约束行数； cj 价值系数；bi 右端项； aij 技术系数线性规划模型的一般形式为：71.线性不等式的几何意义 半平面1) 作出 LP问题的可行域2) 作出目标函数的等值线3) 移动等值线到可行域边界得到最优点2.图解法步骤三、两变量线性规划问题的 图解法84x1=164x2=12x1+2x2=8x1x248430例 3（书 P8）：Q(4,2)Z=2x1+3x2做目标函数 2x1+3x2的等值线，与阴影部分的边界相交于点Q(4,2) ，表明最优生产计划为：生产 I产品 4件，生产 II产品 2件。9例 4Z=3610
