《数据、模型与决策》 课件 2.1线性规划图解法

《MBA数据、模型与决策》

Data,ModelsandDecision-making第2章线性规划模型的图解法什么是

图解法?例2.1广州电器厂生产优化问题广州电器厂生产A、B两种电器产品。产品A与产品B在生产过程中均使用原材料1，其中每件所消耗的原材料1的数量分别为6与2。同时，产品B还需使用原材料2，每件产品的消耗量为1。此外，每生产一件产品A与一件产品B所需的劳动时间分别为2与4。该厂提供的原材料和劳动时间的数量是有限的。在第一个月初，该厂可提供的原材料1的数量是1800，原材料2的数量是350，可提供的2.1一个简单的最大化问题总劳动时间为1600。该两种原材料的保存时间是一个月，也就是说，第一个月用不完的原材料只能丢弃。经财务部门分析计算，产品A与B每件利润分别为3元与8元，而且根据市场调查得到的该两种产品的市场需求状况可以确定，按当前的定价可确保所有产品均能销售出去。问第一个月内产品A与产品B各应生产多少，可使总利润最大？项目1件产品A1件产品B总量原材料1621800原材料201350劳动时间241600利润38表2.1广州电器厂月生产安排分析：在上述问题中，目标是总利润的最大化，所要决策的变量是产品的产量，而产品的产量则受到可提供的原材料与劳动时间的约束，因此，该问题可以用目标、决策变量和约束条件三个因素加以描述。实际上，所有的线性规划问题都包括这三个因素。①目标函数是指系统所追求的目标的数学描述。例如最大利润、最小成本等。②决策变量是指系统中有待确定的未知因素。例如决定企业经营目标的各产品的产量等。③约束条件是指实现系统目标的限制因素，它们限制了目标值所能达到的程度。例如原材料供应量、市场需求等。

解：此问题可用表2.1表示项目1件产品A1件产品B总量原材料1621800原材料201350劳动时间241600利润38表2.1广州电器厂月生产安排①决策变量此问题的决策变量是第一个月产品A与产品B的产量。可设：X为第一个月产品A的产量（件）；Y为第一个月产品B的产量（件）。X、Y即为本问题的决策变量。②目标函数此问题的目标函数是总利润最大。由于产品A与产品B每件利润分别为3元与8元，而其产量分别为X与Y,所以总利润可计算如下：总利润=3X+8Y③约束条件此问题共有四个约束条件。第一个约束是原材料1的约束。每件产品A与产品B对原材料1的消耗量分别为6与2，而两种产品的产量分别为X与Y，所以该两种产品在第一个月对原材料1的总消耗量为6X+2Y。由题意，原材料1的可提供量为1800。由此，可得第一个约束如下：

6X+2Y≤1800第二个约束是原材料2的约束。由于只有产品B需消耗原材料2，而且单位产品B对原材料2的消耗量为1，产品B的产量为Y。由题意，原材料2的可提供量为350。由此可得第二个约束如下：

Y≤350第三个约束是劳动时间的约束。由于每单位产品A与产品B对劳动时间的需要量分别为2与4，而两种产品的产量分别为X与Y，所以两种产品在第一个月所需的总劳动时间为2X+4Y。由题意，劳动时间的可提供量为1600。由此可得第三个约束如下：

2X+4Y≤1600第四个约束是决策变量的非负约束。由于产量不可能为负值，所以有：

X≥0，,Y≥0

由上述分析可建立本问题的线性规划模型如下：o.b.max3X+8Ys.t.6X+2Y≤1800Y≤3502X+4Y≤1600X，,Y≥0所谓的线性规划就是：

(1)每一个问题都用一组决策变量（x1,x2,…xn）表示某一方案；这组决策变量的值就代表一个方案。一般，这些变量取值是非负的。（2）存在一定的约束条件，这些约束条件是一组关于决策变量的线性等式或线性不等式。（3）都有一个要求达到的目标，目标函数是关于决策变量的线性函数。所谓的线性规划就是：

(1)每一个问题都用一组决策变量（x1,x2,…xn）表示某一方案；这组决策变量的值就代表一个方案。一般，这些变量取值是非负的。（2）存在一定的约束条件，这些约束条件是一组关于决策变量的线性等式或线性不等式。（3）都有一个要求达到的目标，目标函数是关于决策变量的线性函数。满足以上三个条件的数学模型称为线性规划的数学模型。它的一般形式为：目标函数

max(min)z=c1x1+c2x2+…+cnxn满足约束条件:

a11x1+a12x2+…+a1nxn≤(＝,≥)b1

a21x1+a22x2+…+a2nxn≤(＝,≥)b2

………….……….am1x1+am2x2+…+amnxn≤(＝,≥)bmx1,x2,…,xn≥0由此可知，线性规划模型有各种不同的形式，目标函数有的求max，有的求min，约束条件可以是“≤”，也可以是“≥”不等式，还可以是等式，决策变量一般是非负约束，在实际问题中有一定的意义,但也允许在（－∞，∞）范围内取值。线性规划问题的解可能出现下列情况：1.有惟一解这里，线性规划问题有惟一解是指该规划问题有且仅有一个既在可行域内，又使目标值达到最优的解，即只有一个最优解。2.2线性规划问题的图解法例如，例2.1广州电器厂生产优化问题，它的线性规划模型为：o.b.max3X+8Y（利润最大化）s.t.6X+2Y≤1800（原材料约束）

Y≤350（原材料约束）

2X+4Y≤1600（劳动时间约束）

X，，,Y≥0（非负约束）1.有惟一解线性问题的图解法2004006008001002003004005006007008009006X+2Y=18002X+4Y=16000ODCBAY=350XY3X+8Y=Z线性问题的图解法步骤在坐标图上作出代表各约束条件的直线；确定满足所有约束条件的可行域；作出任意一条等利润直线；朝着使目标函数最优化的方向，平行移动该等利润直线，直到再继续移动就会离开可行域为止。线性规划问题的解的讨论唯一解无穷多解目标函数为：MaxZ=2X+4Y时线性规划问题无可行域的情况：线性规划问题可行域无界的情况：

6X+2Y=18002X+4Y=1600Y=350X=400max3X+8Ys.t.X+Y=350X，Y≥0本问题是利润最大化，所以应在可行域内选择使利润达到最大值的解。不妨考虑一下哪些解可以使利润达到3X+8Y=1200，可作出等利润线3X+8Y=2400；可得出：3X+8Y=k，k取不同的值表示不同的利润。不难发现所有的等利润都相互平行，且离原点越远的等利润线，利润最高。因此，最优解应是在可行域内离原点最远的那条等利润直线上的点。可见B点就是。而B点是直线②和直线③的交点。解此方程组可得：X=100，Y=350。例如下面一个线性规划模型：o.b.max3X+8Y（利润最大化）s.t.6X+2Y≤1800（原材料约束）

Y≤350（原材料约束）

2X+4Y≤1600（劳动时间约束）

X≥350X，,Y≥0（非负约束）松弛变量与线性规划模型的标准式若在约束条件左边加上一个变量，使原来的“≤”约束不等式变为等式约束Max3X+8Y+0S1+0S2+0S36X+2Y+S1＝1800Y+S2=3502X+4Y+S3=1600X,Y,S1,S2,S3≥0标准型线性规划模型变量S1,S2,S3为松弛变量，表示可提供资源与实际消耗资源之差，即闲置的那部分资源将最优解X=100,Y=350带入约束条件左边，得到三种资源的实际使用量如下：6X+2Y=1300≤1800（原材料1约束）（1）Y=350≤350（原材料2的约束）（2）2X+4Y=1600≤1600（劳动时间约束）（3）原材料1有多余，原材料2、劳动时间没有多于约束1称为非紧约束，表示这时资源有多于约束2和约束3称为紧约束，表示这时资源已全部使用完毕2.有无穷多解这里，线性规划问题有无穷多解是指该规划问题无穷多个既在可行域内，又使目标值达到最优的解，即有无穷多个最优解。2.有无穷多解

例如下面一个线性规划模型：

o.b.max4X+8Y（利润最大化）

s.t.6X+2Y≤1800（原材料约束）

Y≤350（原材料约束）

2X+4Y≤1600（劳动时间约束）

X，，，,Y≥0（非负约束）约束条件和例2.1广州电器厂生产优化问题的约束条件一样，也就是可行域一样，但目标函数不一样，它有无穷多解，解为BC直线上的任意一点，如下图：4X+8Y=KABCOD例如下面一个线性规划模型：o.b.max3X+8Y（利润最大化）s.t.6X+2Y≤1800约束）

Y≤350（原材料约束）

2X+4Y≤1600（劳动时间约束）

X≥350X，,Y≥0（非负约束）如下图，不存在可行域，无解3.无解ABCODEF4.可行域无界

这里，线性规划问题的可行域无界是指最大化问题的目标函数值可以无限增大，或最小化问题的目标函数值可以无限减小。例如下面一个线性规划模型：o.b.max4X+8Y（利润最大化）s.t.X+Y≥350（资源约束）

X，,Y≥0（非负约束）如下图，可行域无界，目标函数值可以无限增大4.可行域无界AB图解法适合于求解含有两个决策变量的线性规划问题。归纳步骤如下：1在坐标图上作出代表各约束条件的直线；2确定满足所有约束条件的可行域；3作出任意一条等利润直线，可令利润函数值等于任意一个特定值；4朝着使目标函数最优化的方向，平行移动该等利润直线，直到再继续移动就会离开可行域为止。此时，该等利润直线在可行域的那些点，就是最优解。图解法步骤例2.3广州金属厂成本优化问题广州金属厂从Ⅰ、Ⅱ两种矿石中提炼A、B两种金属。已知每吨矿石中金属A、B的含量和两种矿石的价格如表2.4.1所示。据预测，金属B的需求量不少于420千克，而金属A由于销路问题，该厂决定，其产量不得超过600千克。此外，矿石Ⅱ由于库存积压，要求其使用量不得少于800吨，问应使用各种矿石多少吨，使得在满足要求的前提下总费用最小？2.3最小化问题

表2.3矿石成分与价格表

金属矿石AB价格（元/吨）Ⅰ0.400.4245Ⅱ0.250.1510解：根据题意可作如下分析：①决策变量本问题的决策变量是两种矿石的使用量。可设：X为矿石Ⅰ的使用量（吨）；Y为矿石Ⅱ的使用量（吨）。②目标函数本问题的目标函数是总费用最小。总费用可计算如下：总费用=45X+10Y（元）③约束条件本问题共有四个约束。第一个约束是金属A的产量约束，第二个约束是金属B的需求约束，第三个约束是矿石Ⅱ的使用量约束，第四个约束是非负约束。由上述分析，可建立该最小化问题的线性规划模型如下：o.b.Min45X+10Ys.t.0.40X+0.25Y≤600（金属A的产量约束）

0.42X+0.15Y≥420（金属B的需求约束）

Y≥800（矿石Ⅱ的使用量约束）

X≥0,Y≥0（非负约束）最小化问题的图解法5001000150020002500Y50010001500XABC0.40X+0.42Y=6000.42X+0.15Y=420Y=800本问题的目标是最小化，所以应在可行域内选择使得费用达到最小值的解。作等费用直线族45X+10Y=k(k可取不同的常数)，对于等费用直线族来说，越靠近原点的等费用直线对应的费用越小。因此，最优解应是在可行域内的、最接近原点的那条等费用直线上的点。本问题中，既在可行域内的、又最接近原点的那条等费用直线上的点是A点，所有A点的坐标就是最优解。而A点直线①和②的交点。解此线性方程组，得到：X=333.3吨，Y=1866.7吨。相应的最优解为：45X+10Y=33666（元）。剩余变量（surplus）若将最优解X=333.3、Y=1866.7代入约束条件的左边0.4X+0.25Y=600≤600（1）0.42X+0.15Y=420≥420（2）Y=1867≥800（3）约束（1）与（2）的左边等于右边，称为“紧约束”约束（3）的左边大于右边，说明矿石乙的实际使用量不仅能够满足所有求的最小使用量，而且还多用了，称约束（3）为“非紧”约束在约束条件（3）的左边减去一个变量，可使原来的“≥”约束不等式变为等式约束。同理，在约束条件（2）的左边减去一个变量，也可使可使原来的“≥”约束不等式变为等式约束。在约束条件（1）的右边加上一个变量，使可使原来的“≤”约束不等式变为等式约束Min45X+10Y+0S1+0S2+0S30.4X+0.25Y+S1=6000.42X+0.15Y-S2=420Y-S3=800X,Y,S1,S1,S1≥0案例分析2-1创业投资基金公司的数据分析

广州某创业投资基金公司为计算机软件和互联网的应用发展提供创业基金。目前该基金公司有两个投资机会：一个是需要资金去开发互联网安全软件的公司；另一个是需要资金去开发对顾客满意度进行调查的应用软件的公司，开发安全软件的公司要求