刁在筠 运筹学
第二章 线性规划
教学重点：线性规划可行区域的几何结构，基本可行解及可行区域的基本定理，单纯形方法，两阶段法，对偶和对偶理论，灵敏度分析。
教学难点：线性规划可行区域的几何结构，基本可行解及可行区域的基本定理，单纯形方法，两阶段法，对偶性，灵敏度分析。
教学课时：24学时
主要教学环节的组织：首先通过各种形式的例子归纳出线性数学规划的一般形式，然后在详细讲解主要内容的基础上，尽可能以图形和例题的形式给以形象的说明，使学生对知识点有更直观、具体的认识。再通过大量习题巩固知识，也可以应用软件包解决一些实际问题。
第一节 线性规划问题
教学重点：线性规划问题的实例，线性规划的一般形式、规范形式和标准形式
教学难点：线性规划一般形式转换成标准形式。
教学课时：2学时
主要教学环节的组织：首先通过几个实例总结出线性规划问题的一般形式，再介绍如何将一般形式转换成标准形式。
1、线性规划问题举例
生产计划问题
某工厂用三种原料生产三种产品，已知的条件如下表所示，试制订总利润最大的生产计划
单位产品所需原料数量（公斤） 产品Q1 产品
Q2 产品
Q3 原料可用量
（公斤/日）
原料P1 2 3 0 1500
原料P2 0 2 4 800
原料P3 3 2 5 2000
单位产品的利润（千元） 3 5 4
可控因素(所求变量)：设每天生产3种产品的数量分别为321,,xxx.
目标：使得每天的生产利润最大，就是使得利润函数：
321453xxx
达到最大.
受制条件： 每天原料的需求量不超过可用量：
原料1P：15003221xx
原料2P：8004232xx
原料3P：2000523321xxx
蕴含约束：产量为非负数0,,321xxx
模型
321453maxxxx
15003221xx
s.t.
8004232xx
1 第二章 线性方程组习题解答
习题2.1
解下列线性方程组
（1）.053,12,1321321321xxxxxxxxx
解：对方程组的增广矩阵作初等行变换
300002101111342002101111015311211111
由最后一行可得原方程组无解.
（2）.153,22,132,3321321321321xxxxxxxxxxxx
解：对方程组的增广矩阵作初等行变换
0000210030102001000021003010501100001050051103111102205230511031111513212113123111原方程组有唯一解.2,3,2321xxx
（3）.165105,8362,42432143214321xxxxxxxxxxxx
解：对方程组的增广矩阵作初等行变换
10100310203102140400013204112116511058316241121
2 10100232101000001
方程组有无穷多解，其通解为,,1,223,04321cxxcxx其中c为任意数.
（4）.032,03,0432143214321xxxxxxxxxxxx
解 对方程组系数矩阵作初等行变换
000021001011210042001111321131111111
第二章 线性规划（LP）
§2.1 线性规划数学模型的建立
LP问题提出：苏联：康德洛维奇 1939
一、线性规划数学模型的三要素：
1.决策变量(decision variable)：决策问题待定的量值。用字母（例如X1,X2,···,Xn）来表示可控制的因
素。每一组决策变量的实际值就表示一个具体方案。 2.目标函数（objective function）：MaxZ=CX 或 MinZ=CX；(衡量决策优劣的准则)
特点：（1）单一目标；（2）关于决策变量的线性函数。（定义：课本P20） 3.约束条件(constraint conditions)：s.t. (subject to) 受制于约束；AX≤(≥，=)b
特点：若干关于决策变量的线性函数。
二、LP数学模型的一般形式
（1）繁写形式 目标函数：Max （Min）z = c1 x1 + c2 x2 + … + cn xn 约束条件：
a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1
a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2
s.t. …… …… am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm
x1 ，x2 ，… ，xn ≥ 0
（2）向量形式 目标函数：Max （Min） z = CX
≤(≥，=)b
Xj≥ 0 (j=1,2, …,n)
其中，C=(c1 , c2 , … , cn )(价值向量) X= (x1 , x2 , … , xn )T(决策变量向量)
b=(b1 , b2 , … , bm )T (限定向量)
pj= (a1j ， a2j … amj ) T (约束条件系数列向量)
注：矩阵相乘条件：左列=右行 (3)矩阵形式★
目标函数：Max （Min） z = CX
约束条件：
n
jjjxp
第二章 线性表
一．单选
1．在一个长度为n 的顺序表中向第i个元素（1<=i<=n+1）之前插入一个新元素时，需要向后移动（ ）个元素。
A．n-i B．n-i+1 C．n-i-1 D．i
2．链表不具有的特点是（ ）
A．可随机访问任一元素 B．插入删除不需要移动元素
C．不必事先估计存储空间 D．所需空间与线性表长度成正比
3．在线性表的下列存储结构中，读取指定序号的元素花费时间最少的是（ ）
A．单链表 B．双链表 C．循环链表 D．顺序表
4．在单链表中，若*P结点不是尾结点，在其后插入*s结点的操作是（ ）
A．s->next=p;p->next=s; B．s->next=p->next;p->next=s;
C．s->next=p->next;p=s; D．p->next=s;s->next=p;
5．在带头结点*head的循环单链表中，至少有一个结点的条件是（ ），尾结点*p的条件是（ ）
A．head->next!=NULL B．head->next!=head
C．p==NULL D．p->next==head
二．填空题
1．在线性表的顺序存储中，元素之间的逻辑关系是通过（ ）决定的；在线性表的链式存储中，元素之间的逻辑关系是通过（ ）决定的。
2．带头结点的单链表head为空的判定条件是（ ）。
3．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为（ ），在data值为x的结点后插入一个新结点的时间复杂度为（ ）
4．在有n个元素的顺序表中删除任意一个元素所需移动元素的平均次数为（ ）
5．在有n个元素的顺序表中任意位置插入一个元素所需移动元素的平均次数为（ ）
三．编程
1． 设计一个算法，将x 插入到一个有序（从小到大）的线性表（顺序存储结构）的适当位置上，并保持线性表的有序性。
