4 1 0 0 0 4 1 0 0 0
2 0 2 2 0 2 0 2 2 0
7 4 4 0 0 7 4 4 0 0
c) 若 x1≤2，则x2≥1，否则x2≤4 x1 2 yM x 1 yM 2 x1 2 (1 y ) M x 4 (1 y ) M 2 y 0或1
d) 以下四个约束条件中至少满足两个： x1 + x2≤5，x1≤2，x3≥2，x3+x4≥6
量分别为Q1，Q2，…，Q6，生产每个箱的可变费用分别为
c1,c2,…c6 (c1<c2<…<c6)，生产不同规格包装箱的固定费用 分别为k1,k2,…k6，并且有
for xi 0 0 C ( xi ) ki ci xi for xi 1
式中xi为生产第i种规格包装箱的数量。若某种规格较小的包 装箱不生产或生产数量不够时，可用比其大的任一规格的包
x2 x6 x9 x10 2
4.4 已知分配问题的效率矩阵如下，试用匈牙利法分别求出 最优解
3 8 6 8 9
2 10 3 7 2 9 7 4 2 7 5 4 2 3 5 10 6 9 10 8
第一步：找出效率矩阵每行的最小元素，并分别从每行中
4.1 试利用0-1变量对下列各题分别表示成一般线性约束条件 a) x1 + x2≤2 或 2x1 + 3x2≥5 b) 变量 x 只能取值0、3、5或7中的一个 c) 若 x1≤2，则x2≥1，否则x2 ≤4 d) 以下四个约束条件中至少满足两个：
x1 + x2≤5，x1≤2，x3≥2，x3+x4≥6
4.3 某钻井队要从以下10个可供选择的井位中确定5个钻井
探油，目的使总的钻探费用最小。若10个井位代号为 S1,S2，…S10，相应的钻探费用为c1,c2,…,c10，并且 井位的选择上要满足下列条件： ① 或选择S1和S7，或选择钻探S8 ② 选择了S3或S4就不能选S5，或反过来也一样 ③ 在S2、S6、S9、S10中最多只能选两个
4 0 7 0 3 0 6 4 0 0 4 2 0 0 0 2 2 0 2 3
＋2
－2
－2
0 3 3 5 0
4 1 0 0 2 2 1
第五步：用最少直线覆盖
0 3 3 5 0 0 3 3 5 0
0 设 xj 1
选择第 sj 个井位 不选择第 sj 个井位
① 或选择S1和S7，或选择钻探S8
x1 x8 1 x7 x8 1
② 选择了S3或S4就不能选S5，或反过来也一样
x3 x5 1 x4 x5 1
③ 在S2、S6、S9、S10中最多只能选两个
减去最小元素，有
1 6 0 8 1 3 8 2 10 3 2 6 5 0 7 5 8 7 2 9 7 2 4 2 0 5 3 6 4 2 7 5 2 6 2 0 1 3 8 4 2 3 5 2 3 4 0 3 4 9 10 6 9 10 6 第二步：找出矩阵每列的最小元素，再分别从每列中减去，有 1 6 0 8 1 0 4 0 7 0 6 5 0 7 5 5 3 0 6 4 4 2 0 5 3 3 0 0 4 2 6 2 0 1 3 5 0 0 0 2 3 4 0 3 4 2 2 0 2 3
a) x1 + x2≤2 或 2x1 + 3x2≥5
x1 x2 2 y1M 2 x 3x 5 y M 1 2 2 y1 y2 1 y1 , y2 0或1
b) 变量 x 只能取值0、3、5或7中的一个
x 3 y1 5 y2 7 y3 y1 y2 y3 1 y , y , y 0或1 1 2 3
1 2 0 1 1
第三步：用最少的直线覆盖所有“0”，得
0 5 3 5 2
4 0 7 0 3 0 6 4 0 0 4 2 0 0 0 2 2 0 2 3
覆盖所有零最少需要4条直线，表明矩阵中最多存在4个不同 行不同列的零元素．需要作变换
0 5 3 5 2
x1 x2 5 y1M x 2 y M 2 1 x3 2 y3 M x3 x4 6 y4 M y1 y2 y3 y4 2 y1~ 4 0或1
4.2 某厂经常往外发送零部件。工厂根据长期发货情况决定 专门生产一批为A1,A2,…A6的6种不同规格的包装箱，其中A1 最小，A2次之，…A6最大。已知上述6种规格包装箱的需求
装箱代替。
试为该厂建立一个生产上述6种规格包装箱各多少个的决策的数 学模型，即满足该厂对6种规格包装箱的需求，又使总的费用为 最小
min Z yi (ki ci xi )
i 1
6
for i 1, 2...6 xi Myi 6 6 xi Q j i 1 j 1 5 5 xi Q j i 1 j 1 4 4 xi Q j st. i 1 j 1 3 3 xi Q j i 1 j 1 2 2 xi Q j i 1 j 1 x1 Q1 y 取0或1 ；x1~6 0且为整数 1~6