Ch1线性规划.ppt

1、，运筹学，第1章线性规划，1.1线性规划的数学模型，1.2图解法，1.3线性规划的标准形式，1.4基本概念，1.5单纯形法，1.1数学模型，2020年7月24日星期五，1.1线性规划的数学模型，线性规划通常研究资源的最佳利用和设备的最佳运行。例如，当任务或目标确定后，如何进行总体规划和合理安排，并使用最少的资源(如资金、设备、原始标准材料、劳动力、时间等)。)完成确定的任务或目标；在一定的资源约束下，如何组织和安排生产以获得最佳的经济效益(如最大的产品数量和最大的利润)。2020年7月24日星期五，示例1-1生产计划问题。企业计划在计划期间生产a和b产品。根据技术数据，每个产品甲需要消耗2公斤

2、材料甲和1公斤材料乙，每个产品乙需要消耗1公斤材料甲和1.5公斤材料乙.据了解，规划期内可利用的材料分别为40公斤和30公斤；产品甲和产品乙每生产一次，企业可分别获得利润40元和30元，如表11所示。假设无限的市场需求。企业决策者应该如何安排生产计划，使企业在计划期内的总利润和总收入最大化？1.1线性规划的线性规划的数学模型，1.1.1应用模型示例，2020年7月24日星期五，解，设x1和x2分别为产品A和B的输出，数学模型为：1.1线性规划的线性规划的数学模型，表1-1，2020年7月24日星期五，线性规划的数学模型由决策变量、目标函数和约束条件组成。叫做三要素。其特征在于：1 .解决问题的

3、目标函数是多个决策变量的线性函数，通常寻求最大值或最小值；解决问题的约束条件是一组具有多个决策变量的线性不等式或方程。如何区分模型和线性规划模型？1.1线性规划的线性规划数学模型，2020年7月24日，星期五，示例1-2一家购物中心决定销售人员在每周连续工作五天后应连续休假两天。据统计，商场每天需要的销售人员见表1-2。表1-2销售人员需求统计表，商场人力资源部应如何安排每天上班的人数，以最大限度地减少商场的销售人员总数？1.1线性规划的线性规划数学模型，2020年7月24日星期五。解如果XJ (j=1，2，7)是两天休息后从星期一到星期天开始工作的店员，这个问题的线性规划模型是，线性规划的线

4、性规划的1.1数学模型。2020年7月24日星期五，最优解：Z617(人)，1.1线性规划的线性规划数学模型，2020年7月24日星期五，示例1-3合理使用材料。一辆汽车需要使用一个轴的甲，乙和丙，其规格分别为1.5，1和0.7米。这些车轴需要用同样的圆钢制成，长度为4米。现在，要制造1000辆汽车，至少需要用多少圆钢来生产这些车轴？解决方案这是一个材料切割问题。让槽口宽度为零。如果圆钢被切割成三个轴：y 1、y2和y3，那么切割方法可以用不等式1.5y1 y2 0.7y34表示，并且可以得到关于y1、y2和y3的该不等式的非负整数解。像这样的非负整数解有10组，即有10种消隐方法，如表1-3

5、所示。表1-3下料方案，1.1线性规划的线性规划数学模型，2020年7月24日星期五，设xj(j=1，2，10)为第j次下料方案中使用的圆钢数量。那么最小材料消耗的数学模型为：在计算下料方案时要注意剩余材料不能超过最短下料长度；最好按降序排列坯料长度，即先切割长度最长的坯料，然后切割长度第二长的坯料，最后切割长度最短的坯料。如果有很多方案，用计算机编程来安排方案，去掉那些有长剩余材料的方案进行初选。1.1线性规划的线性规划数学模型，2020年7月24日星期五，Z812.5，1.1线性规划的线性规划数学模型，2020年7月24日星期五，示例1-4批处理问题。钢铁公司生产的合金要求成分规格：锡不低

6、于28%，锌不超过15%，铅正好是10%，镍在35U之间，不允许有其他成分。钢铁公司计划冶炼五种不同品位的矿石，每种矿石的成分含量和价格见表1-4。矿石杂质在精炼过程中被丢弃，现在需要每吨合金成本最低的矿石量。假设矿石的合金含量在熔炼过程中没有变化。表1-4矿石的金属含量，1.1线性规划的线性规划数学模型，2020年7月24日星期五，让xj(j=1，2，5)为溶液：中jth矿石的数量，并得到以下线性规划模型，注意矿石的金属含量在实际冶炼过程中会发生变化，这在建模时应予以考虑，可能配料问题，也称为配方问题、营养问题或混合问题，在许多行业中都可能会遇到。1.1线性规划的线性规划的数学模型，2020

7、年7月24日星期五，最优解：Z=347.5，1.1线性规划的线性规划的数学模型，2020年7月24日星期五，1.1线性规划的线性规划的数学模型，示例1-5投资问题。一家投资公司计划投资5000万元的国债、地方国债和基金，每种都有两种类型。每种证券的评级、到期日和年税后收益率见表1-5。表15证券投资计划，决策者希望国债投资金额不低于1000万元，平均到期期限不超过5年，平均评级不超过2级。问问每种证券投资多少才能使总回报最大化。2020年7月24日星期五，1.1线性规划的线性规划数学模型，设XJ (j=1，2，6)为第J种证券的投资金额，目标函数为税后总收入、资本约束、国债投资约束、平均评级约

8、束和平均到期约束，2020年7月24日星期五。完成后，我们得到线性规划模型，1.1线性规划的数学模型，2020年7月24日星期五，例1-6来平衡配套生产问题。一个产品由两个零件甲和三个零件乙组装而成，两种零件必须在设备甲和设备乙上加工，每个零件甲的加工时间分别为5分钟和9分钟，每个零件乙的加工时间分别为4分钟和10分钟。目前有2台设备甲和3台设备乙，加工时间为每天8小时。为了维持两种设备的均衡负荷生产，要求一种设备每天的总加工时间不超过另一种设备一小时的总加工时间。如何安排设备的加工时间，使每天的产品产量最大化。解决方案如果x1和x2是每天加工A和B的零件数，那么产品的产量是：设备A和B每天加

9、工时间的约束是一种设备每天的加工时间不能超过另一种设备的加工时间：1.1线性规划的线性规划数学模型，2020年7月24日星期五，目标函数线性化。产品的输出y等于，线性规划模型被获得并在约束下线性化。绝对值约束被写成两个不等式：1.1线性规划的数学模型，2020年7月24日星期五，1.1.2线性规划的一般模型。通常，假设线性规划的数学模型中有m个约束和n个决策变量xj，j=1，2，n，目标函数的变系数用cj表示，称为值系数。约束条件的可变系数由aij表示，称为过程系数。约束右端的常数由bi表示，称为资源限制。线性规划数学模型的一般表达式可以写成，为了便于编写，上述公式也可以写成：1.1线性规划线

10、性规划数学模型，2020年7月24日星期五，实际上一般使用xj0，但有时xj0或xj是无符号的。，1.1线性规划的线性规划数学模型，2020年7月24日星期五，1。什么是线性规划，掌握线性规划在管理学中的几个应用实例。线性规划数学模型的组成和特点。线性规划数学模型的一般表达式。作业：课本练习1.11.6，1.1线性规划的线性规划数学模型，下一节：图解法，1.2图解法，2020年7月24日星期五，图解法步骤：1。分别得到满足每个约束(包括变量)的非负要求的区域，它们的交集是可行解的集合，或称为可行区域；2。绘制目标函数图。首先，通过原点做一个向量指向点(c1，c2)，向量的方向是目标函数增加的方

11、向，称为梯度方向，然后做一条垂直于向量的直线，即为目标函数图；3.找到最佳解决方案。根据目标函数，找出最大或最小移动目标函数直线，直线与可行域相交点对应的坐标即为最优解。一般来说，当目标函数线被放置在可行区域以获得最大值时，该线沿着向量方向移动，当它获得最小值时，它沿着向量的相反方向移动。1.2图解法，2020年7月24日星期五，X1，X2，O，10，20，30，40，10，20，30，30，40。(15，10)，最优解X=(15，10)，最优值Z=8500，示例1-7，1.2图形方法，2020年7月24日星期五，最小Z=5x1 5x2，示例1-9，有无限个最优解，即有多个解，一般解为0.1，

12、当=0.5=(x1，x2)=0.5 (1，3) 0.5 (3，1)=(2，2)，1.2图解法，2020 6、(1，2)，无界解(无最优解)，最大Z=x1 2x2，示例1-10，1.2，图解法，2020年7月24日星期五，x1有一个唯一的最优解(例1-7，例1-8)，2。有多种解决方案。4.无可行解(例1-11)，1，2例有最优解，3，4例无最优解，1.2图解法，2020年7月24日星期五，1。用图解法理解线性规划的几种解法。2.绘画有三个要点。(1)正确绘制可行解区域。(2)目标函数的增长方向不应画错。(3)如何平行移动目标函数的直线。作业：课本练习1.7，1.2图解法，下一节：标准类型的线性

13、规划。1.3线性规划线性规划标准格式，2020年7月24日星期五，用简单方法求解线性规划问题时，为了便于讨论问题，有必要将线性规划模型化为统一的标准格式。1.3线性规划的标准形式，线性规划问题的标准形式是：1目标函数是找出最大值(或最小值)。2约束都是等式。3个变量xj是非负的，4个常数bi是非负的。2020年7月24日星期五，最大(或最小)z=c1x1c2cnxn。1.3线性规划线性规划的标准形式，注：本教材的默认目标函数为max，星期五，2020年7月24日，或写成以下形式：或写成矩阵形式，1.3线性规划线性规划的标准形式，星期五，2020年7月24日，通常x写成：系数矩阵称为约束方程，m是约束方程的个数，n是决策变量的个数，一般为mn，其中： 1.3线性规划的标准形式LP，2020年7月24日星期五，示例1-12将以下线性规划更改为标准形式，解决方案()因为x3没有符号要求，即x3可以取正值或负值，并且标准形式中的变量要求为非负值，因此，1.3线性规划的标准形式LP，2020年7月24日星期五，(3)第二个约束条件是数字，剩余变量X5和x50从的左端减去也称为松弛变量，1.3线性规划的标准形式，(2)线性规划，(2)第一个约束条件是数字，松弛变量)x4和x40在左端相加，并转化为方程；(4)第三个约束条件是