线性规划问题
一、 建模(除排队论，都可以线性规划)
关键：决策变量（维度），目标函数、约束条件； a, b, c
例：
例：某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，这些产品分别需要在A、B、C、D四种不同的设备上加工。按工艺规定：产品Ⅰ和Ⅱ在个设备上所需要的加工时数于下表中。已知各设备在计划期内的有效台时数分别是12、8、16和12。该工厂每生产一件产品Ⅰ可得利润2圆，每生产一件产品Ⅱ可得利润3圆，问：应如何安排生产，可获得最大利润。
设备 产品 Ⅰ Ⅱ
解 设生产产品Ⅰ和Ⅱ分别为x1和x2件，则由条件可得关系
A 2 3 B 1 2 C 4 1 D 2 4 max z?2x1?3x2
?2x1?3x2?12??x1?2x2?8 ??4x1?x2?16?2x?4x?122?1 练习：
xi?0,i?1, 2
二、 转化为标准型
关键：决策变量≥0，目标函数Max、约束条件= （b≥0）
三、 图解法（两维）
关键：纵轴X2系数的正负，目标求大求小 X2>0 X2<0 Max(Z) Min(Z)
例 用图解法求解线性规划问题 极大化 Maxz?2x1?3x2 (?? min或 -3x2)
?x1?2x2?8? ?4x1 ?16
?? 4x2?12 解：最优解X
xi?0,i?1, 2?(4,2),z?14
四、 简单计算(包括大M法,两阶段法)
关键： 标准型转化，步骤 （换基，入基， “Xb=B”）
例 用单纯形法求解线性规划 极大化
z?2x1?3x2?5x3 ?
x1?x2?x3?7
2x?5x?3x?1023?1?xi?0,i?1,2,3
解 引入松弛变量x4,x5，得到原规划的标准型 极大化
z?2x1?3x2?5x3?0x4?0x5
??x1?x2?x3?x4?7 ? 2x?5x?3x?x?10?523?1 单纯形表为
xi?0,i?1,2,3,4,5 xx1x2x3x40100153x50010010710 074521
cx4x5?x2x523?51?1?12?53?2?35171100188?所以，最优解为(0,7,0)t,最优解值为21.
利用大M法或两阶段法求解下列问题
五、 复杂计算
关键：目标函数和检验数 (Z1新 和 Z0 旧的对比) Cj-Zj σ Z1-Z0 Zj-Cj σ Z0-Z1
Max(Z) ** Min(Z)