资源描述：
《第一节一般线性规划问题的数学模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、运筹帷幄之中决胜千里之外线性规划LinearProgramming第一章线性规划及单纯形法一般线性规划问题的数学模型图解法单纯形法原理单纯形法的计算步骤单纯形法的进一步讨论应用举例第一节一般线性规划问题的数学模型线性规划问题的数学模型线性规划问题的标准型及其标准化线性规划问题解的含义一、线性规划的发展1939年，前苏联数学家康托洛维奇用线性模型研究提高组织和生产效率问题1947年，Dantzig提出求解线性规划的单纯形法1950-1956年，主要研究线性规划的对偶理论1958年，发表整数规划的割平面法1960年，Dantzig和Wolfe研究成功分解算法，奠定了大
2、规模线性规划问题理论和算法的基础。1979年，Khachiyan，1984年，Karmarkaa研究成功线性规划的多项式算法。另外，很多现代算法研究如进化、神经网络等。解：一般方法是在铁皮的四个角上剪去四个边长各为x的正方形，折叠做成一个容器，则容积为V=(a-2x)2·x。要让容积最大即确定x(0≤x≤a)的值，使V达到最大。ax图1-1二、问题的提出例1.1用一块长为a的正方形铁皮做一个容器，应如何剪裁，使做成的容器的容积为最大（见图1-1）例1.2Maxz=2x1+3x22x1+2x2≤12x1+2x2≤84x1≤164x2≤12x1，x2≥0例1.3某工厂
3、在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表。问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？Maxz=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1，x2≥0例1.4套裁下料问题某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根，已知原料每根长7.4m。应如何下料，可使所用原料最省？解：共可设计下列5种下料方案设x1,x2,x3,x4,x5分别为上面5种方案下料的原料根数。建立数学模型如下目标函数：Minz=0.1x2+0.2x3+0
4、.3x4+0.8x5约束条件：s.t.x1+2x2+x4=1002x3+2x4+x5=1003x1+x2+2x3+3x5=100x1,x2,x3,x4,x5≥0总结提出问题类似的例子可以举出很多。归结起来有两种情况：一是给定资源，如何充分利用二是给定计划，研究如何统筹安排，用最少的人力物力去完成都是求极值的问题，有些问题可以用微积分解决，但例中除了要求变量非负外带了很多附加条件，解决这类问题就是运筹学中规划论研究的内容。◆线性规划的三个要素决策变量：（x1，x2），一组值代表一个方案目标函数：max或min约束条件：不等式或等式◆线性规划：目标函数、约束条件均为线
5、性函数三、线性规划的数学模型1.一般形式决策变量：X=(x1,x2,…..,xn)T目标函数：max(minz)=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+……..+a1nxn≤(=≥)b1a21x1+a22x2+……..+a2nxn≤(=≥)b2…………………………………………am1x1+am2x2+……..+amnxn≤(=≥)bmx1,x2,……xn≥0其中，“max(minz)”是“maximize(minimize)的缩写，含义为“最大化(最小化)”2.一般形式的其它写法①求和形式②向量形式目标函数：Max（Min）z=CX约束条
6、件：s.t.X≥0其中C=(c1,c2,…,cn)③矩阵形式决策变量常数项系数矩阵价值系数四、线性规划数学模型的建立1.建模条件(1)优化条件：问题所要达到的目标能用线型函数描述，且能够用极值（max或min）来表示；(2)限定条件：达到目标受到一定的限制，且这些限制能够用决策变量的线性等式或线性不等式表示；(3)选择条件：有多种可选择的方案供决策者选择，以便找出最优方案。2.建模步骤(1)确定决策变量：即需要我们作出决策或选择的量。一般情况下，题目问什么就设什么为决策变量。(2)找出所有限定条件：即决策变量受到的所有的约束；(3)写出目标函数：即问题所要达到的目
7、标，并明确是max还是min。例1.5混合配料问题某糖果厂用原料1、2、3加工三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中原料1、2、3的含量、原料每月限用量、三种牌号糖果的加工费及售价，如下表所示。该厂每月如何生产才能获利最大？解:用i=1，2，3代表原料1、2、3，j=1，2，3代表糖果甲、乙、丙。xij表示第j种产品中原料i的含量，则对于原料1：x11，x12，x13；对于原料2：x21，x22，x23；对于原料3：x31，x32，x33；对于甲：x11，x21，x31；对于乙：x12，x22，x32；对于丙：x13，x23，x33；目标函数：利润最大，
8、利润=收入
