线性规划习题(20)

0? x1? s1

f1(s1)

x*1

1 2.5+6

2 4+3

3 10+0 10 3

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.代替约束条件，则此问题的数学模型为：

max Z ? 2 x1 ? 3x2

S ?t ?

x1 ? 2 x2 ? 8 4 x1 ? 16 4 x2 ? 12

x1 , x2 ? 0

型。 2、本章重点难点分析 建立初始单纯形表格，并用单纯形方法求解线性规划数学模型。 3、本章典型例题分析 例：

max Z ? 20 x1 ? 15 x2

用单纯形法求解

S ?t ?

2 x1 ? 3x2 ? 600 2 x1 ? x2 ? 400

x1 , x2 ? 0

解：先化为标准形式： max Z ? 20 x1 ? 15 x2

S ?t ?

2 x1 ? 3x2 ? x3 ? 600

2 x1 ? x2 ? x4 ? 400

xj ? 0 ( j ? 1,2,3,4)

把标准形的系数列成一个表 基 S X1 S 1 -20 X3 0 2 X4 0 2 第一次迭代：调入 x1,调出 x4 基 S X1 S 1 0 X3 0 0 X1 0 1 第二次迭代：调入 x2,调出 x3 基 S X1 S 1 0 X2 0 0 X1 0 1

x1 ? 150 x2 ? 100

X2 -15 3 1

X3 0 1 0

X4 0 0 1

解 0 600 400

X2 -5 2 1/2 X2 0 1 0

X3 0 1 0 X3 5/2 1/2 -1/4

X4 10 -1 1/2 X4 15/2 -1/2 3/4

解 4000 200 200 解 4500 100 150

? Z max

? 4500

4、本章作业 见本章练习题 3、本章典型例题分析 例：写出下列线性规划问题的对偶问题 max Z ? 3 x1 ? x2 ? 4 x3

?6 x1 ? 3x2 ? 5 x3 ? 25 ? S ? t ? ?3x1 ? 4 x2 ? 5 x3 ? 20 ? x ? 0 ( j ? 1,2,3) ? j

解：其对偶问题为：

min W ? 25 y1 ? 20 y2 ?6 y1 ? 3 y2 ? 3 ?3 y ? 4 y ? 1 ? 1 2 S ?t ?? ?5 y1 ? 5 y2 ? 4 ? y1 , y2 ? 0 ?

4、本章作业

见本章练习题

第五章

运输模型

1、本章学习要求 （1）应熟悉的内容 运输问题的数学模型。 （2）应掌握的内容 根据实际问题能写出运输问题的数学模型。 （3）应熟练掌握的内容 确定初始方案的方法：最小元素法、元素差额法。 2、本章重点难点分析 先确定初始方案，然后进行检验是否是最优解，如果不是最优解，则进行调 整改进，最终得到最优解。。 3、本章典型例题分析 例：用最小元素法求解（表上作业法） （单位： 吨） 销地 1 2 3 4 5 产地 1 2 3 销量 元） 销地 产地 1 2 3 1 2 4 2 2 1 2 1 3 3 1 1 4 1 3 3 5 2 1 4 250 300 200 200 250 300 200 550 350 100 100 200 （单位：