B 0 21 21 1 0 25 0 16 16 0 -16 C 5 M M 0 M 0 M-5 0 M-8 M 0 V 21 16 24 16 16 (6) 调整后的方案为最优方案 最低费用＝150×15＋250×18＋140×21＋270×16＋40×16＋30×0＋40×0＝14650

五、分配甲、乙、丙、丁四人去完成5项任务。每人完成各项任务时间如下表所示。由于任务数多于人数，故规定其中有一人可兼完成两项任务，其余三人每人完成一项，试确定总花费时间最少的指派方案。（15分） A B C D E 甲 25 29 31 42 37 乙 39 38 26 20 33 丙 34 27 28 40 32 丁 24 42 36 23 45 解：假设增加一个人戊完成各项工作的时间取A、B、C、D、E最小值。 得效率矩阵为：

ABCDE甲?2529314237??3938262033乙???

丙?3427284032???丁?2442362345?戊??2427262032??各行减最小值，各列减最小值：得

ABCDE甲?045177??1918508乙???

丙?70?13????丁?11912?17?戊??475?7??变换得

ABCDE甲?045乙??18174丙?70??丁??1811戊??3647?07?? 14????16??6??18进一步

ABCDE甲?001183??1813003乙???丙?1100180???丁?0147012?戊??32002??最有指派方案

ABCDE

甲?01000?

?00010乙???

丙?00001???丁?10000?戊??00100??

甲——B，乙——C,D，丙——E，丁——A 最低费用＝29＋26＋20＋32＋24＝131 六、某公司打算将3千万元资金用于改造扩建所属的3个工厂，每个工厂的利润增长额与所分配的投资有关。各工厂在获得不同的投资额时所能增加的利润如下

表所示，问应如何分配资金，使公司总的利润为最大（15分） 利润 投0 1千万 2千3千万 资 万 工厂 1 0 2.5 4 10 2 0 3 5 8.5 3 0 2 6 9 解：K为阶段变量，k=1,2,3 Sk:第k阶段所剩的资金数

Xk：第k阶段分配给第k个工厂的资金数 gk（xk）：将xk分配给第k个工厂的效益 状态转移方程：Sk+1= Sk-xk 递推关系：

{gk(xk)?fk?1(sk?xk)}k?n?1,?,1 ?fk(sk)?0max?xk?sk? ?fn(sn)?maxgn(xn)?xn?sn ?第三阶段，k=3 X3=s3

f3(s3)?maxg3(x3)

x3?s3x3 s3 0 1 g3(x3) 2 3 f3(s3) x*3 0 1 2 3 0 2 6 9 0 2 6 9 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 9 x*2 0 1 0 0,1 0 0 1 2 3 0+0 0+2 0+6 0+9 1 3+0 3+2 3+6 2 5+0 5+2 3 8.5+0 第三阶段 S1=3

S2=s1-x1, 0?x1?s1 x1 f1(s1)?max{g1(x1)?f1(s1?x1)} 0?x1?s1s1 0 1 2 3 3 0+9 2.5+6 4+3 10+0 f1(s1) 10 x*1 3 最优分配方案为，x1*=3,x2*=0,x3*=0 最佳获益值：10千万。

第二章 线性规划问题的基本概念 3、本章典型例题分析

例：某工厂要安排生产甲、乙两种产品，已知生产单位产品所需的设备台时及A、B两种原村料的消耗如表所示。该工厂生产一单位产品甲可获利2元，

生产一单位产品乙可获利3元，问应如果安排生产，使其获利最多？

设备 原材料A 原材料B 甲 1 4 0 乙 2 0 4 每日提供资源 8（台时） 16（Kg） 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

X4 0 0 1

X4 10 -1 1/2

X4

解 0 600 400

解 4000 200 200

解