第三章 线性规划及图解法
3.1 根据下面决策变量xl、 x2的约束条件，各画一张图显示满足这个约束的非负解。再将这些约束条件综合在一张图上，表示出在外在约束（函数约束）和简单约束（非负约束）下的可行域。
xl- x2≤2 -3xl+6 x2≥3 4xl-3 x2≥1 解：
3.2 有下面决策变量xl、x2构成的目标函数： max Z=2xl+3 x2
1、在一张图上分别画出Z =6、Z =12、Z =18时相应的目标函数直线。
2、写出这三条直线方程的斜截式形式，比较三条直线的斜率以及在x2轴上的截距。
解： 1、
2?2、三个斜截式中斜率相同，都是 ，在 2轴上的截距分别为2、4、6。 3
3.3 将下列线性规划问题划为标准形式 1、 max Z=3xl+2 x2+4 x3-8 x4 S.T. xl+2 x2+5 x3+6 x4≥8 -2xl+5 x2+3 x3-5 x4≤2 2xl+4 x2+4 x3-5 x4=18
xl、x2、x3 ≥0 x4无约束
解： max Z=3xl+2 x2+4 x3-8 x5+8x6+0x7+0x8
S.T. xl+2 x2+5 x3+6 x5-6x6-x7=8
-2xl+5 x2+3 x3-5 x5+5x6+x8=2 2xl+4 x2+4 x3-5 x5+5x6=18
xl、x2、x3、x4、x5 、x6、x7 、x8 ≥0 2、 min f=5xl-2 x2+4 x3-3 x4 S.T. -xl+2 x2- x3+4 x4=-2 -xl+3 x2+ x3+ x4≤14 2xl- x2+3 x3- x4≥2
xl 符号不限，x2≤0，x3 、x4≥0
解： max f=5x1-5x2 +2 x3+4 x4-3 x5+0x6+0x7
S.T. x1-x2 +2 x3+ x4-4 x5=2
-x1+x2 -3 x3+ x4+ x5+x6=14
2xl-2x2+ x3+3 x4- x5-x7=2
x1、x2、x3、x4 、x5、x6 、x7≥0
3.4 用图解法求解下列线性规划问题 1、max Z=xl+2 x2
S.T. 3xl+5 x2≤15 6xl+2 x2≤12 xl 、 x2≥0
解： 最优解为（0，3），最优值：6。 2、max Z=2xl+2 x2
S.T. xl- x2≥-1 -0.5xl+ x2≤2 xl 、 x2≥0
解： 本问题有无界解。
3、max Z=4xl+8x2
S.T. 2xl+2 x2≤10 -xl+ x2≥8 xl 、 x2≥0
解： 本问题无可行解，即无解。 4、 max Z=3xl+9x2
S.T. xl+3x2≤22 -xl+ x2≤4
x2≤6 2xl-5 x2≤0
xl 、 x2≥0
解：最优解：（与 xl+3x2=22相重合，所以有无穷多解），最优值：66。
5、max Z=3xl-2x2
S.T. xl+ x2≤1 2xl+2 x2≥4 xl 、 x2≥0
解：本问题没有可行域，所以无解。
6、max Z=xl+x2
S.T. 2xl+ x2≤20 xl+ x2≥10 x1≥5 xl 、 x2≥0 解：最优解：（5，10） 最优值：15。
3.5 对于如下线性规划问题
max Z=xl+x2
S.T. 4xl+3 x2≤12 2xl+3 x2≤6 x2≤2 xl 、 x2≥0
1、 用图解法求解。
2、 写出此线性规划问题的标准形式。
3、 求出此线性规划问题各约束条件的松弛量和对偶价格。
解：1、 最优解：（3，0） ，最优值：3
2、本问题的标准形式：
max Z=xl+x2+0S1+0S2+0S3
S.T. 4xl+3 x2+S1=12 2xl+3 x2+S2=6 x2+S3=2
xl 、x2≥0 ，Sl 、S2≥0
松弛量 对偶价格
3、 4xl+3 x2≤12 0 0.1667 2xl+3 x2≤6 0 0.1667 x2≤2 2 0
3.6 对于如下线性规划问题
min Z=40xl+50x2
S.T. 2xl+3 x2≥30 xl+ x2≥12 2xl+ x2≥20 xl 、x2≥0
1、 用图解法求解。
2、 写出此线性规划问题的标准形式。
3、 求出此线性规划问题各约束条件的剩余量和对偶价格。
解：1、 最优解：（7.5，5），最优值：550
2、 本模型的标准形式：
min Z=40xl+50x2+0S1+0S2+0S3
S.T. 2xl+3 x2-S1≥30 xl+ x2-S2≥12 2xl+ x2-S3≥20 xl 、x2≥0
3、 松弛量 对偶价格
2xl+3 x2≥30 0 -15
xl+ x2≥12 0.5 0 2xl+ x2≥20 0 -5
3.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=300xl+500 x2 S.T. xl≤4 2x2≤12 3x1+2x2≤18 5x1+3x2≤45
xl、 x2≥0
2、 最优解（2，6），最优值：3600元。
3、0≤c1≤750 4、200≤c2≤∞
5、最优解不变，最优值：4000元。 6、最优解不变，最优值：2400元。 7、最优解为（4，3），最优值为：3050元。 8、最优解为（2，6），最优值为：3700元。
3.8 某工厂生产甲、乙两种产品，分别经过A、B、C三种设备加工。已知生产单位产品所需要的台时数、设备的现有加工能力及每件产品的利润情况如下表： A B C 单位产品利润（元） 甲 1 10 4 10 乙 1 4 2 6 设备能力（台时） 120 640 260 1、建立线性规划数学模型，用以制定该厂获得利润最大的生产计划。 2、用图解法求解该数学模型。
3、在本模型中，哪些约束条件起到了作用。
4、三个约束条件的松弛量和对偶价格分别是多少，都代表什么含义？ 5、产品甲的利润在多大范围内变化时，原最优计划保持不变？
6、产品甲的利润由现在的10元/件再增加3元，产品乙由现在的6元再减少3元，原最优计划是否需要改变？
7、设备B的台时数怎么变化时，原最优计划必须改变，为什么？
8、设备A的台时数再增加50，设备B的台时数再减少50，原三个约束条件的对偶价格是否发生改变，为什么？
解：
1、 建立数学模型
max z=10 xl+6 x2 S.T. xl+x2≤120 10x1+2x2≤640 4x1+2x2≤260
xl、 x2≥0
2、 最优解：（10，110），最优值：760
3、第一、第三个约束起到了约束作用。
4、 松弛量 对偶价格 xl+x2≤120 0 2 10x1+2x2≤640 320 0 4x1+2x2≤260 0 2 松弛量表示按最优方案安排生产时，该项资源还剩余的量；对偶价格表示每增加一个单位的资源，对总利润的增加值。
5、不变。 6、发生改变。 7、发生改变。 8、发生改变。
3.9 某公司欲制造的两种产品Ⅰ和Ⅱ的利润分别为500元/个和400元/个。生产这两种产品都需要四个工序（分别在四个车间内完成）。公司各个车间的加工能力和制造单位产品所需的加工工时如下表： 车间 产品Ⅰ 产品Ⅱ 车间每天可用加工工时 1 2 3 4 2 0 2 1.2 0 3 2 1.5 300 540 440 300
1、建立线性规划数学模型，用以制定该厂获得利润最大的生产计划。 2、用图解法求解该数学模型。
3、在本模型中，哪些约束条件起到了作用。
4、四个约束条件的松弛量和对偶价格分别是多少，都代表什么含意？ 5、产品Ⅱ的利润在多大范围内变化时，原最优计划保持不变？
6、产品Ⅰ的利润由现在的500元/个再减少50元，产品Ⅱ由现在的400元再增加50元，原最优计划是否需要改变？
7、用车间1和车间3的松弛量和对偶价格分析保持这两个对偶价格不变时，两车间的可用加工能力应该控制在什么范围之内。
8、四个车间的可用加工工时都再增加一倍，其相应的对偶价格是否发生改变？为什么？
解：模型：
max z =500x1 +400x2
2x1 ≤300 3x2 ≤540 2x1 +2x2 ≤440 1.2x1 +1.5 x2 ≤300
x1,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) 不变。