第一章 线性规划
设xij为从供应地 Ai 运往需求地 Bj 的物资数量（i=1,2；j=1,2,3），z为总运费，则总运费最小的线性规划模型为：
min s.t.
xij≥0
z= 2x11 +3x12 +5x13 +4x21 +7x22 +8x23
x11 +x12 +x13 x11
x12
x13
(1) (2) (3) (4) (5)
=35 =10 =30
x21 +x22 +x23 =25 +x22
+x21
+x23 =20
以上约束条件（1）、（2）称为供应地约束，（3）、（4）、（5）称为需求地约束。这个问题的最优解为：x11=0，x12=30，x13=5，x21=10，x22=0，x23=15（吨）；最小运费为：z=275元。
1.2.5 指派问题
例1.5 有n项任务由n个人去完成，每项任务交给一个人，每个人都有一项任务。由第i个人去做第j项任务的成本（或效益）为cij。求使总成本最小（或效益最大）的分配方案。
例如，有张、王、李、赵4位教师被分配教语文、数学、物理、化学4门课程，每位教师教一门课程，每门课程由一位老师教。根据这四位教师以往教课的情况，他们分别教这四门课程的平均成绩如下表：
表 1-5
张 王 李 赵 语文 数学 物理 化学 92 82 83 93 68 91 90 61 85 77 74 83 76 63 65 75 四位教师每人只能教一门课，每一门课只能由一个教师来教。要确定哪一位教师上哪一门课，使四门课的平均成绩之和为最高。
设xij（i=1, 2, 3, 4；j=1, 2, 3, 4）为第i个教师是否教第j门课，xij只能取值0或1，其意义如下：
6
第一章 线性规划
?0第i个教师不教第j门课xij??
1第i个教师教第j门课?变量xij与教师 i 以及课程 j 的关系如下：
表 1-6
j i 张 王 李 赵 语文 数学 物理 化学 x11 x21 x31 x41 x12 x22 x32 x42 x13 x23 x33 x43 x14 x24 x34 x44 这个指派问题的线性规划模型为：
max z= 92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24
+83x31+90x32+74x33+65x34+93x41+61x42+83x43+75x44
s.t.
x11+x12+x13+x14=1 x21+x22+x23+x24=1 x31+x32+x33+x34=1 x41+x42+x43+x44=1 x11+x21+x31+x41=1 x12+x22+x32+x42=1 x13+x23+x33+x43=1 x14+x24+x34+x44=1 xij=0, 1
这个问题的变量只能取值0或1，这样的线性规划问题成为0－1规划。 这个问题的最优解为 x14=1，x23=1，x32=1，x41=1，max z=336；即张老师教化学，王老师教物理，李老师教数学，赵老师教语文，如果这样分配教学任务，四门课的平均总分最高，可以达到336分。
一般的指派问题线性规划模型如下：
?0第i个人不从事第j项任务设： xij??
1第i个人被指派完成第j项任务?得到以下的线性规划模型：
（1） （2） （3） （4） （5） （6） （7） （8）
7
第一章 线性规划
min(max)z?n??cxi?1j?1ijnnijijs.t.?x?xj?1i?1n?1j?1,2,?,n
ij?1i?1,2,?,nxij?0,1在线性规划问题中，如果所有的变量都只能取值0或1。这样的线性规划问题称为（纯）0－1整数规划问题。如果一个线性规划问题中，有的变量是连续变量，而另一些变量是0－1变量，这样的问题称为混合0－1规划问题。
由以上5个例子，我们可以归纳出线性规划问题的一般形式：
max(min)z?c1x1?c2x2???cjxj???cnxns.t.a11x1?a12x2???a1jxj???a1nxn?(?,?)b1a21x1?a22x2???a2jxj???a2nxn?(?,?)b2
???????am1x1?am2x2???amjxj???amnxn?(?,?)bmx1x2?xj?xn?0其中
max(min)z?c1x1?c2x2???cjxj???cnxn
称为目标函数，
a11x1?a12x2???a1jxj???a1nxn?(??)b1a21x1?a22x2???a2jxj???a2nxn?(??)b2
???????am1x1?am2x2???amjxj???anmxn?(??)bm称为约束条件，
x1，x2，?，xj，?，xn?0
称为变量的非负约束。
在线性规划问题中，目标函数是变量的线性函数，约束条件是变量的线性不等式。例如以下的问题就不是线性规划问题：
max z=5x1x2+2x3
1s.t. 2x12+3x2-?15
x3 |x1-x2|+4x3?14 x1，x2，x3?0 记向量和矩阵
8
第一章 线性规划
?c1??x1??b1??a11a12?c??x??b??aa22222Cn?1???，Xn?1???，bm?1???，Am?n??21????????????????????xn??bm??am1am2?cn?
max(min) z＝CTX s.t.
AX≤(＝,≥)b X≥0
?a1n??a2n?? ?????amn?则线性规划问题可由向量和矩阵表示
其中
?x1??x?T?2??cx?cx??cx ??C1X?cc?c?nn?112nnn???1122???xn??a11a12?a1n??x1??a11x1?a12x2??a1nxn??a??x??ax?ax??ax?a?a21222n2222nn???2???211Am?nXn?1?? ??????????????????aa?axax?ax??axmn??n?m22mnn??m1m2?m11AX≤(＝≥)b的分量形式为
?a11x1?a12x2??a1nxn??b1??ax?ax??ax??b?2222nn??211?(??)?2?
??????????ax?ax??axm22mnn??m11?bm?X≥0的分量形式为
?x1??0??x??0?X??2????
???????????xn??0?9
第一章 线性规划
§1.3 线性规划问题的标准形式
为了今后讨论的方便，我们称以下线性规划的形式为标准形式：
min z＝CTX s.t. AX＝b
X≥0
对于各种非标准形式的线性规划问题，我们总可以通过以下的变换，将其转化为标准形式。
1.3.1 极大化目标函数的问题
设目标函数为
maxminz?c1x1?c2x2???cnxn z' ??c1x1?c2x2???cnxn
令z’＝－z，则以上极大化问题和以下极小化问题有相同的最优解。 例如，极大化线性规划问题
max s.t. z=
3x1 +4x2 x1 x1
-x2 x2 -4x2 -x2 x2
2x1 +2x3
+5x3
+2x3 ≤20 +x3 ≤45 x3 -5x3 +2x3 +x3 x3
≥0
≤20 ≤45 ≥0
和相应的极小化线性规划问题
min z’= -3x1 s.t.
的最优解相同，都是
x1=0，x2=14，x3=17
但他们最优解的目标函数值却相差一个符号，即
max z＝141
min z’=-141
x1 x1
2x1 +2x3
1.3.2 约束条件不是等式的问题
设约束条件为
ai1x1?ai2x2???ainxn?bi(i?1,2,?,m)
引进一个新的变量xn+i，使它等于约束右边与左边之差
xn?i?bi?(ai1x1?ai2x2???ainxn)
10