第三章 线性规划及图解法

第三章线性规划及图解法3.1根据下面决策变量x l、x2的约束条件，各画一张图显示满足这个约束的非负解。

再将这些约束条件综合在一张图上，表示出在外在约束（函数约束）和简单约束（非负约束）下的可行域。

x l- x2≤2-3x l+6 x2≥34x l-3 x2≥1解：3.2 有下面决策变量x l、x2构成的目标函数：max Z=2x l+3 x21、在一张图上分别画出Z =6、Z =12、Z =18时相应的目标函数直线。

2、写出这三条直线方程的斜截式形式，比较三条直线的斜率以及在x2轴上的截距。

解：1、2、三个斜截式中斜率相同，都是 ，在 2轴上的截距分别为2、4、6。

3.3 将下列线性规划问题划为标准形式 1、 max Z=3x l +2 x 2+4 x 3-8 x 4 S.T. x l +2 x 2+5 x 3+6 x 4≥8 -2x l +5 x 2+3 x 3-5 x 4≤2 2x l +4 x 2+4 x 3-5 x 4=18x l 、x 2、x 3 ≥0 x 4无约束解： max Z=3x l +2 x 2+4 x 3-8 x 5+8x 6+0x 7+0x 8S.T. x l +2 x 2+5 x 3+6 x 5-6x 6-x 7=8-2x l +5 x 2+3 x 3-5 x 5+5x 6+x 8=2 2x l +4 x 2+4 x 3-5 x 5+5x 6=18x l 、x 2、x 3、x 4、x 5 、x 6、x 7 、x 8 ≥0 2、 min f=5x l -2 x 2+4 x 3-3 x 4 S.T. -x l +2 x 2- x 3+4 x 4=-2 -x l +3 x 2+ x 3+ x 4≤14 2x l - x 2+3 x 3- x 4≥2x l 符号不限，x 2≤0，x 3 、x 4≥0解： max f=5x 1-5x 2 +2 x 3+4 x 4-3 x 5+0x 6+0x 7S.T. x 1-x 2 +2 x 3+ x 4-4 x 5=2-x 1+x 2 -3 x 3+ x 4+ x 5+x 6=142x l -2x 2+ x 3+3 x 4- x 5-x 7=2x 1、x 2、x 3、x 4 、x 5、x 6 、x 7≥03.4 用图解法求解下列线性规划问题 1、max Z=x l +2 x 2S.T. 3x l +5 x 2≤15 6x l +2 x 2≤12 x l 、 x 2≥0解： 最优解为（0，3），最优值：6。

2、max Z=2x l +2 x 2S.T. x l - x 2≥-1 -0.5x l + x 2≤2 x l 、 x 2≥032解：本问题有无界解。

3、max Z=4x l+8x2S.T. 2x l+2 x2≤10-x l+ x2≥8x l 、x2≥0解：本问题无可行解，即无解。

4、max Z=3x l+9x2S.T. x l+3x2≤22-x l+ x2≤4x2≤62x l-5 x2≤0x l 、x2≥0解：最优解：（与x l+3x2=22相重合，所以有无穷多解），最优值：66。

5、max Z=3x l-2x2S.T. x l+ x2≤12x l+2 x2≥4x l 、x2≥0解：本问题没有可行域，所以无解。

6、max Z=x l+x2S.T. 2x l+ x2≤20x l+ x2≥10x1≥5x l 、x2≥0解：最优解：（5，10）最优值：15。

3.5对于如下线性规划问题max Z=x l+x2S.T. 4x l+3 x2≤122x l+3 x2≤6x2≤2x l 、x2≥01、用图解法求解。

2、写出此线性规划问题的标准形式。

3、求出此线性规划问题各约束条件的松弛量和对偶价格。

解：1、最优解：（3，0），最优值：32、本问题的标准形式：max Z=x l+x2+0S1+0S2+0S3S.T. 4x l+3 x2+S1=122x l+3 x2+S2=6x2+S3=2x l 、x2≥0 ，S l 、S2≥0松弛量对偶价格3、4x l+3 x2≤12 0 0.16672x l+3 x2≤6 0 0.1667x2≤2 2 03.6 对于如下线性规划问题min Z=40x l+50x2S.T. 2x l+3 x2≥30x l+ x2≥122x l+ x2≥20x l 、x2≥01、用图解法求解。

2、写出此线性规划问题的标准形式。

3、求出此线性规划问题各约束条件的剩余量和对偶价格。

解：1、最优解：（7.5，5），最优值：5502、本模型的标准形式：min Z=40x l+50x2+0S1+0S2+0S3S.T. 2x l+3 x2-S1≥30x l+ x2-S2≥122x l+ x2-S3≥20x l 、x2≥03、松弛量对偶价格2x l+3 x2≥30 0 -15x l+ x2≥12 0.5 02x l+ x2≥20 0 -53.7 某工厂要生产两种新产品：门和窗。

经测算，每生产一扇门需要在车间1加工1 小时、在车间3加工3 小时；每生产一扇窗需要在车间2 和车间3加工2小时。

而车间1每周可用于生产这两种新产品的时间为4小时、车间2为12 小时、车间3为18小时。

又知每生产一扇门需要钢材5公斤，每生产一扇窗需要钢材3公斤，该厂现可为这批新产品提供钢材45公斤。

每扇门的利润为300元，每扇窗的利润为500元。

而且根据市场调查得到的这两种新产品的市场需求状况可以确定，按当前的定价可确保所有新产品都能销售出去。

问该工厂如何安排这两种新产品的生产计划，能使总利润为最大？1、建立本问题的线性规划数学模型。

2、用图解法求解。

3、若门的利润不变，求出窗的利润在什么区间变化可使该计划不变。

4、若窗的利润不变，求出门的利润在什么区间变化可使该计划不变。

5、若门的利润由当前的每扇300元涨到每扇500元，窗的利润不变，求出新的最优解和最优值。

6、若窗的利润由当前的每扇500元降到每扇300元，门的利润不变，求出新的最优解和最优值。

7、若门的利润由当前的每扇300元涨到每扇650元，窗的利润由当前的每扇500元降到每扇150元，求出新的最优解和最优值。

8、若门的利润由当前的每扇300元降到每扇200元，窗的利润由当前的每扇500元涨到每扇550元，求出新的最优解和最优值。

解：1、线性规划数学模型：max z=300x l+500 x2S.T. x l≤42x2≤123x1+2x2≤185x1+3x2≤45x l、x2≥02、最优解（2，6），最优值：3600元。

3、0≤c1≤7504、200≤c2≤∞5、最优解不变，最优值：4000元。

6、最优解不变，最优值：2400元。

7、最优解为（4，3），最优值为：3050元。

8、最优解为（2，6），最优值为：3700元。

3.8 某工厂生产甲、乙两种产品，分别经过A、B、C三种设备加工。

已知生产单位产品所需要的台时数、设备的现有加工能力及每件产品的利润情况如下表：1、建立线性规划数学模型，用以制定该厂获得利润最大的生产计划。

2、用图解法求解该数学模型。

3、在本模型中，哪些约束条件起到了作用。

4、三个约束条件的松弛量和对偶价格分别是多少，都代表什么含义？5、产品甲的利润在多大范围内变化时，原最优计划保持不变？6、产品甲的利润由现在的10元/件再增加3元，产品乙由现在的6元再减少3元，原最优计划是否需要改变？7、设备B的台时数怎么变化时，原最优计划必须改变，为什么？8、设备A的台时数再增加50，设备B的台时数再减少50，原三个约束条件的对偶价格是否发生改变，为什么？解：1、建立数学模型max z=10 x l+6 x2S.T. x l+x2≤12010x1+2x2≤6404x1+2x2≤260x l、x2≥02、最优解：（10，110），最优值：7603、第一、第三个约束起到了约束作用。

4、松弛量对偶价格x l+x2≤120 0 210x1+2x2≤640 320 04x1+2x2≤260 0 2松弛量表示按最优方案安排生产时，该项资源还剩余的量；对偶价格表示每增加一个单位的资源，对总利润的增加值。

5、不变。

6、发生改变。

7、发生改变。

8、发生改变。

3.9 某公司欲制造的两种产品Ⅰ和Ⅱ的利润分别为500元/个和400元/个。

生产这两种产品都需要四个工序（分别在四个车间内完成）。

公司各个车间的加工能力和制造单位产品1、建立线性规划数学模型，用以制定该厂获得利润最大的生产计划。

2、用图解法求解该数学模型。

3、在本模型中，哪些约束条件起到了作用。

4、四个约束条件的松弛量和对偶价格分别是多少，都代表什么含意？5、产品Ⅱ的利润在多大范围内变化时，原最优计划保持不变？6、产品Ⅰ的利润由现在的500元/个再减少50元，产品Ⅱ由现在的400元再增加50元，原最优计划是否需要改变？7、用车间1和车间3的松弛量和对偶价格分析保持这两个对偶价格不变时，两车间的可用加工能力应该控制在什么范围之内。

8、四个车间的可用加工工时都再增加一倍，其相应的对偶价格是否发生改变？为什么？解：模型：max z =500x1 +400x22x1 ≤3003x2 ≤5402x1 +2x2 ≤4401.2x1 +1.5 x2 ≤300x1,x2 ≥0(1)x1=150 x2=70 即目标函数最优值是103000；(2) 2，4 有剩余，分别是330，15。

均为松弛变量；(3) 50，0 ，200，0 额外利润250；(4) 在(0,500)变化，最优解不变；(5) 在400 到正无穷变化，最优解不变；(6) 不变。