AB甲?25乙??39丙?34?丁?24戊??24CDE29314237?38262033?? 27284032??42362345?27262032??各行减最小值，各列减最小值：得
ABCDE甲?045177??1918508乙???
丙?70?13????丁?11912?17?戊??475?7??变换得
ABCDE甲?045187??1817407乙???
丙?70?14????丁??1811?16?戊??364?6??进一步
ABCDE甲?001183??1813003乙???丙?1100180???丁?0147012?戊??32002??最有指派方案
ABC甲?0乙??0丙?0?丁?1戊??0
DE
1000?
0010?? 0001?
?
0000?0100??
甲——B，乙——C,D，丙——E，丁——A
最低费用＝29＋26＋20＋32＋24＝131
六、某公司打算将3千万元资金用于改造扩建所属的3个工厂，每个工厂的利润增长额与
所分配的投资有关。各工厂在获得不同的投资额时所能增加的利润如下表所示，问应如何分配资金，使公司总的利润为最大（15分） 利润 投资 工厂 1 2 3 0 0 0 0 1千万 2.5 3 2 2千万 4 5 6 3千万 10 8.5 9 解：K为阶段变量，k=1,2,3 Sk:第k阶段所剩的资金数
Xk：第k阶段分配给第k个工厂的资金数 gk（xk）：将xk分配给第k个工厂的效益 状态转移方程：Sk+1= Sk-xk 递推关系：
?fk(sk)?max{gk(xk)?fk?1(sk?xk)}
0?xk?sk? ?fn(sn)?maxgn(xn)?xn?sn ?第三阶段，k=3 X3=s3
k?n?1,?,1f3(s3)?maxg3(x3)
x3?s3x3 s3 0 1 2 3 0 0 1 2 g3(x3) 2 6 3 9 f3(s3) 0 2 6 9 x*3 0 1 2 3
第二阶段：
s3=s2-x2， 0?s2?3， 0?x2?s2
f2(s2)?max{g2(x2)?f3(s2?x2)}
0?x2?s2x2 s2 f2(s2)?max{g2(x2)?f3(s2?x2)} 0?x2?s2f2(s2) 0 2 6 x*2 0 1 0 0 0 1 2 0+0 0+2 0+6 1 3+0 3+2 2 5+0 3 3 第三阶段 S1=3
S2=s1-x1, 0?x1?s1 0+9 3+6 5+2 8.5+0 9 0,1 x1 s1 0 3 f1(s1)?max{g1(x1)?f1(s1?x1)} 0?x1?s1f1(s1) 10 x*1 3 1 2.5+6 2 4+3 3 10+0 0+9
最优分配方案为，x1*=3,x2*=0,x3*=0 最佳获益值：10千万。
第二章 线性规划问题的基本概念
3、本章典型例题分析
例：某工厂要安排生产甲、乙两种产品，已知生产单位产品所需的设备台时及A、B两种原村料的消耗如表所示。该工厂生产一单位产品甲可获利2元，生产一单位产品乙可获利3元，问应如果安排生产，使其获利最多？ 甲 乙 每日提供资源 设备 1 2 8（台时） 原材料A 4 0 16（Kg） 原材料B 0 4 12（Kg） 解：①确定决策变量：设X1 、X2 为产品甲、乙的生产数量； ②明确目标函数：获利最大，即求2X1+3X2的最大值； ③所满足的约束条件：
设备限制：X1+2X2≤8 原材料A限制：4X1≤16 原材料B限制：4X2≤12 基本要求：X1 ，X2≥0
用max代替最大值，S.t.代替约束条件，则此问题的数学模型为：
maxZ?2x1?3x2 S?t? x1?2x2?8
4x1?16
4x2?12
x1,x2?0
型。
2、本章重点难点分析
建立初始单纯形表格，并用单纯形方法求解线性规划数学模型。 3、本章典型例题分析
例： maxZ?20x1?15x2 用单纯形法求解 S?t? 2x1?3x2?600
2x1?x2?400
x1,x2?0
解：先化为标准形式：maxZ?20x1?15x2 S?t? 2x1?3x2?x3?600
2x1?x2?x4?400
xj?0(j?1,2,3,4)
把标准形的系数列成一个表 基 S X1 X2 X3 S 1 -20 -15 0 X3 0 2 3 1 X4 0 2 1 0
第一次迭代：调入x1,调出x4 基 S X1 X2 X3 S 1 0 -5 0 X3 0 0 2 1 X1 0 1 1/2 0 第二次迭代：调入x2,调出x3 基 S X1 X2 X3 S 1 0 0 5/2 X2 0 0 1 1/2 X1 0 1 0
-1/4
?Zmax
x1?150x2?100?4500
4、本章作业
X4 0 0 1 X4 10 -1 1/2 X4 15/2 -1/2 3/4
解 0 600 400
解 4000 200 200 解 4500 100 150