资源描述：
《线性规划与单纯形法(I)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1第2章线性规划与单纯形法裴凤合肥工业大学管理学院2第2章线性规划与单纯形法本章重点内容线性规划模型与解的主要概念线性规划的单纯形法，线性规划多解分析线性规划的应用——建模3第2章线性规划与单纯形法章节安排2.1线性规划问题及其数学模型2.2线性规划问题的基本理论2.3单纯形法2.4单纯形法的计算步骤2.5单纯形法的进一步讨论2.6应用举例分析重点问题1：如何建立线性规划的数学模型？问题2：线性规划模型有哪些基本特征？问题3：两变量线性规划模型如何求解？2.1线性规划问题及其数学模型问题4：线性规划模型的标准形式？问题5：标准型线性规划的解的概念？一、线性规划
2、建模举例例1(P15)安排生产计划问题某工厂在计划期内要安排I,II两种产品的生产。生产单位产品所需的设备台时及A,B两种原材料的消耗以及资源的限制如下表所示。工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元，问工厂应如何安排生产才能使获利最多？产品I产品II资源限制设备原材料A原材料B1402048台时16kg12kg获利23-解：设I、II两种产品的产量分别为x1,x2。该问题的数学模型为:一、线性规划建模举例x1+2x2目标函数约束条件设备原材料A原材料B4x14x2≤12x1,x2≥0产品I产品II资源限制设备原料A原料B1402048台时
3、16kg12kg获利23-Maxx1x2≤8≤16Z=2x1+3x27一、线性规划建模举例例2营养配餐问题一个成年人每天需要从食物中获取2500kcal的热量、100g蛋白质和800mg的钙。如果市场上有四种食物可供选择，它们每千克所含热量和营养成分以及市场价格见下表。问如何选择食物才能在满足营养的前提下使购买食物的总费用最小？序号食物热量(kcal)蛋白质(g)钙(mg)价格(元)1猪肉143020360262鸡蛋14401335683大米34607413054白菜170155002需求量2500100800-8一、线性规划建模举例解：设xj为第j种食物每天
4、购买量，该问题的数学模型为：x1x2x3x4Z=26x1+8x2+5x3+2x41430x1目标函数约束条件序号食物热量(kcal)蛋白质(g)钙(mg)价格(元)1猪肉143020360262鸡蛋14401335683大米34607413054白菜170155002需求量2500100800-203x1133x274x315x41440x23460x3170x4+++≥250060x156x2130x3500x4+++≥100x1,x2,x3,x4≥0+++≥800Min热量蛋白质钙分析重点问题1：如何建立线性规划的数学模型？问题2：线性规划模型有哪些基本特
5、征？问题3：两变量线性规划模型如何求解？2.1线性规划问题及其数学模型问题4：线性规划模型的标准形式？问题5：标准型线性规划的解的概念？10MaxZ=2x1+3x2x1+2x2≤84x1≤164x2≤12x1,x2≥0MinZ=14x1+6x2+3x3+2x41000x1+800x2+900x3+200x4≥300050x1+60x2+20x3+10x4≥55400x1+200x2+300x3+500x4≥800x1,x2,x3,x4≥0右端项,(常数项)价值系数决策变量二、线性规划模型的共同特征11目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函
6、数实现最大化或最小化。每一个问题变量都用一组决策变量（x1,x2,…,xn）表示方案，这组决策变量的值代表一个具体方案，这些变量是非负的。存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。结论：线性规划是研究在一组线性不等式或线性等式约束下，使得某一线性目标函数取最大或最小的极值问题。二、线性规划模型的共同特征12Max(Min)Z=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2s.t.……am1x1+am2x2+…+amnxn≤(=,≥)bmxj
7、≥0,j=1,2,…，nn－变量个数；m－约束行数；cj－价值系数；bi－右端项；aij－技术系数线性规划模型的一般形式为：分析重点问题1：如何建立线性规划的数学模型？问题2：线性规划模型有哪些基本特征？问题3：两变量线性规划模型如何求解？2.1线性规划问题及其数学模型问题4：线性规划模型的标准形式？问题5：标准型线性规划的解的概念？141.线性不等式的几何意义—半平面作出LP问题的可行域作出目标函数的等值线移动等值线到可行域边界得到最优点2.图解法步骤三、两变量线性规划问题的图解法154x1=164x2=12x1+2x2=8x1x248430例3（17）Q(
8、4,2)Z=2x1+3x2做目标函数2
