1.线性规划的数学模型：
max (min)z = c1x1 + c2x2 + ··· + cnxn
a11x1 + a12x2 + ··· + a1nxn ≤(=, ≥) b1 a21x1 + a22x2 + ··· + a2nxn ≤(=, ≥) b2 ┆ ┆
am1x1 + am2x2 + ··· + amnxn ≤(=, ≥) bm x1，x2，···，xn ≥ 0
2.图解法求解：
3.
将下述问题化为标准型
4.求基可行解
⎪⎪⎩
⎪⎪⎨
⎧=≥=++=+--=---=5,4,3,2,1;05222
2..min 5214213212
1j x x x x x x x x x x t s x x z j 2 5. 用单纯形法求解
1. max z = x1 + 3x2 x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12 x1,x2 ≥ 0 6. 用单纯形法求解
⎪⎩
⎪
⎨⎧≥≤++≤++++=0,,120
23310032..244540)(max 3213213213
21x x x x x x x x x t s x x x x f
7.大M 法求解
⎪⎪⎩⎪
⎪⎨⎧≥≤≤+≤++=0,78
102..46)(max 2122
1212
1x x x x x x x t s x x x f ⎪⎪⎩⎪⎪⎨⎧≥±≤++≤++≥+++-=0
, ,200400
65300
432..423)(min :2133213
21
321321x x x x x x x x x x x x t s x x x x f 不限原非标准型
min z = x1 + 5x2 + 0x3+0x4
2x1 + 3x2 + x3 = 6 2x1 + x2 – x4 = 1 x1,x2,x3, x4 ≥ 0 8.
用两阶段法求解 min z = x1 + 5x2
2x1 + 3x2 ≤6 2x1 + x2 ≥1 x1,x2 ≥ 0
9. 用大M 法和二阶段法求解
⎪⎩
⎪
⎨⎧≥≥++≥+++=0,,4
6
2..7810)(min 32132121321x x x x x x x x t s x x x x f
10.
试求下述线性规划原问题的对偶问题
11. 试求下述线性规划原问题的对偶问题
min z = 2x1 + 3x2 - 5x3 + x4
x1 + x2 - 3x3 + x4 ≥ 5 2x1 + 2x3 - x4 ≤ 4 x2 + x3 + x4 = 6 x1 ≤ 0,x2,x3 ≥ 0,x4无约束
12.
已知：min w = 20y1 + 20y2 的最优解为y1*=1.2,y2*=0.2 y1 + 2y2 ≥ 1 ① 试用松弛性求对偶 2y1 + y2 ≥ 2 ② 问题的最优解。
2y1 + 3y2 ≥ 3 ③ 3y1 + 2y2 ≥ 4 ④ y1,y2 ≥ 0 13. 用对偶单纯形法求解
min ω=2x1+3x2+4x3 x1+2x2+x3≥3 2x1-x2+3x3≥4 x1，x2，x3≥0
14.
用对偶单纯形法求解
min w = 2x1 + 3x2 + 4x3
()()()⎪⎪
⎩⎪⎪⎨⎧≥≤⇒=++⇒≤-+⇒≥+-++-+=无约束432134322431143214
321,0,,0362422153532min x x x x y x x x y x x x y x x x x x x x x z
x1 + 2x2 + x3 ≥ 1 2x1 - x2 + 3x3 ≥ 4 x1,x2,x3 ≥ 0
15.求解
16. 用对偶单纯形法求解
⎪⎩
⎪
⎨⎧≥≥++--≥+-+++=0,,,4
426
2..35)(min 4321432143214
21x x x x x x x x x x x x t s x x x x f
17.
已知下述问题的最优解及最优单纯形表, 3）求∆c4的变化范围,使最优解不变 4)求 ∆c2的变化范围,使最优解不变.
5）求例1 ∆a24的变化范围,使最优解不变.
0,,40025005.2516002200034max 51514213215
4321≥=++=++=++++++=x x x x x x x x x x x x x x x z ., )12使最优基不变的变化范围求b ∆.
4 )21时的最优解求=∆b ⎪⎪⎩⎪
⎪⎨
⎧≥=+=+=++++++=0,,,,124 164 82 00032max 54321524132154321x x x x x x x x x x x x x x x x x z
18.
19.
P1级目标：充分利用设备有效台时，不加班； P2级目标：产品B 的产量不多于4； P3级目标：尽量实现利润值130万元 求最优生产方案
20.
试用单纯形法来求解
21．
⎪⎪⎪⎩
⎪⎪⎪⎨⎧=≥=-++=-++=-+-=+++++=+-+
-+
-+
--
+-+3
,2,1,0,,,,561081020112)(min 21332122211121213322211i d d x x x d d x x d d x x d d x x x x x d P d d P d P z i i s s 满足约束条件：目标函数：
22.
用分枝定界法求解整数规划
23. 用分枝定界法求解整数规划
⎪⎩⎪
⎨
⎧
≥≤+≤++=且为整数 0,7
2134246)(max 2
121212
1x x x x x x x x x f
24.
利用隐枚举法求解 ()
⎩⎨
⎧==≤++++++=4,3,2,11,0532553643214
321j x x x x x x x x x y Max j 25.
求下面0-1规划的解.
26.
用隐枚举法求解
27.
某医院的四名化验员（甲、乙、丙、丁）完成四项化验工作（A 、B 、C 、D ）所消耗的时间见表2-13。
哪个化验员担当哪项化验工作，可使他们总的消耗时间最短？ 表1-13
A B C D 消耗时间（分） 甲 37.7 43.4 33.3 29.2
⎪⎪⎩⎪⎪⎨
⎧≥≤+≤++=.,0,70
20756799040max 21212
121211为整数x x x x x x x x x x S L 1231231231223Max 32522 (1)44 (2)s.t.3 (3)46 (4)0 1.(1,2,3,)j Y x x x x x x x x x x x x x x j =-+⎧+-≤⎪++≤⎪⎪+≤⎨⎪+≤==⎩或⎪
⎪⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤-+≤-≤++≤++++-=0,,3222
28232243max 313
2132321321123x x x x x x x x x x x x x x x x x S
乙32.9 33.1 28.5 26.4
丙33.8 42.2 38.9 29.6
丁37.0 34.7 30.4 28.5
28.有一份中文说明书，需译成英、日、德、俄四种文字。
分别记作E、J、G、R。
现有甲、乙、丙、丁四人。
他们将中文说明书翻译成不同语种的说明书所需时间如表5-7所示。
问应指派何人去完成何工作，使所需总时间最少?
29
30.有四个熟练工人，他们都是多面手，有四项任务要他们完成。
若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表4.6.1，问如何分配任务使完成四项。