习题

2.1.

对于 Reddy Mikks 模型，构造下面约束的每一种情况，并将它们表示为线性的左端项和常数的右端项：
（a）内墙涂料的日需求量比外墙涂料的日需求量至少多 1 吨；
（c）内墙涂料的需求量不能少于外墙涂料的需求量；
（e）内墙涂料与内、外墙涂料的总产量之比不能超过 0.5。

解：
$$\begin{gathered} x_1=\text{外墙涂料的日生产吨数}; \\ {x}_2=\text{内墙涂料的日生产吨数}. \end{gathered}$$
（a）$-x_1+x_2\ge 1$；
（c）$x_1-x_2\le 0$；
（e）$0.5x_1-0.5x_2\ge 0$。

2.3.

对于 Reddy Mikks 模型的可行解 $x_1=2,x_2=2$，确定原料 M1 和 M2 没有用完的量。

解：
原料 M1 没有用完的量 = $24-(6x_1+4x_2)=24-(6\ast 2+4\ast 2)=4$；
原料 M2 没有用完的量 = $6-(x_1+2x_2)=6-(2+2\ast 2)=0$。

2.9.

某公司生产 A 和 B 两种产品。产品 A 的销售量至少是产品 A 与 产品 B 销售总和的 80%。然而，公司每天不能销售多于 100 单位的产品 A。两种产品使用同一种原料，并且最大日可用量是 240 磅。生产每单位产品 A 需要原料 2 磅，生产每单位 B 需要原料 4 磅。产品 A 和 产品 B 的单位利润分别是 20 美元和 50 美元。试为该公司确定最优的生产策略。

解：
$$\begin{gathered} x_1=\text{产品 A 的单位数} \\ {x}_2=\text{产品 B 的单位数} \end{gathered}$$
则
$$\max z=20x_1+50x_2$$

s.t. { − 0.2 x 1 + 0.8 x 2 ≤ 0 x 1 ≤ 100 2 x 1 + 4 x 2 ≤ 240 x 1 , x 2 ≥ 0 \text{s.t.}

$$\begin{cases} -0.2x_1+0.8x_2 \leq 0 \\ x_1 \leq 100 \\ 2x_1 + 4x_2 \leq 240 \\ x_1, x_2 \geq 0 \\ \end{cases}$$ s.t.⎩⎪⎪⎪⎨⎪⎪⎪⎧​−0.2x1​+0.8x2​≤0x1​≤1002x1​+4x2​≤240x1​,x2​≥0​
Matlab 代码:

f = [-20; -50];
A = [-0.2, 0.8; 1, 0; 2, 4];
b = [0; 100; 240];
Aeq = [];
beq = [];
lb = zeros(2, 1);
ub = [];
[x, fval] = linprog(f, A, b, Aeq, beq, lb, ub)
1
2
3
4
5
6
7
8

最优解：$(x_1,x_2)=(80,20)$，$z=2600$ 美元。

2.11.

某人打算将 5000 美元投资于下一年度的两类项目：投资项目 A 可盈利 5%，投资项目 B 可盈利 8%。市场研究表明，至少应有 25% 的投资分配给项目 A，至少应有 50% 的投资分配给项目 B。进一步假设，项目 A 的投资至少是项目 B 的投资的一半。如何为这两类投资项目分配这笔专款？

解：
令
$$\begin{gathered} x_1=\text{项目 A 的投资额} \\ {x}_2=\text{项目 B 的投资额} \end{gathered}$$

$$\max z=0.05x_1+0.08x_2$$

s.t. { x 1 + x 2 ≤ 5000 − 0.75 x 1 + 0.25 x 2 ≤ 0 0.5 x 1 − 0.5 x 2 ≤ 0 − x 1 + 0.5 x 2 ≤ 0 x 1 , x 2 ≥ 0 \text{s.t.}

$$\begin{cases} x_1 + x_2 \leq 5000 \\ -0.75x_1 + 0.25x_2 \leq 0 \\ 0.5x_1 -0.5 x_2 \leq 0 \\ -x_1 + 0.5x_2 \leq 0 \\ x_1, x_2 \geq 0 \end{cases}$$ s.t.⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​x1​+x2​≤5000−0.75x1​+0.25x2​≤00.5x1​−0.5x2​≤0−x1​+0.5x2​≤0x1​,x2​≥0​

Matlab 代码：

f = [-0.05, -0.08];
>> A = [1, 1; -0.75, 0.25; 0.5, -0.5; -1, 0.5];
>> b = [5000, 0, 0, 0];
>> Aeq = [];
>> beq = [];
>> lb = zeros(2, 1);
>> ub = [];
>> [x, fval] = linprog(f, A, b, Aeq, beq, lb, ub)
1
2
3
4
5
6
7
8

最优解：$(x_1,x_2)=(1666.7,3333.3)$，$z=350$。

2.18.

怀俄明电力公司拥有一座蒸汽涡轮机发电厂。怀俄明州储藏有丰富的煤，公司用煤发电。然而，这可能导致排放物不符合环保署的标准。环保署的法规限定，每吨煤燃烧后二氧化硫的排放量不能超过 2000 微升/升，从发电厂排出的烟尘累计不能超过每小时 20 磅。公司使用两种等级的煤粉 C1 和 C2 来进行蒸汽发电。这两种等级的煤粉在燃烧前通常被混合在一起。为简单起见，可以假定硫的排放量是两种煤粉混合比例的加权平均。下列数据是基于两种等级的煤每小时消耗量为 1 吨得到的。

（a）确定两种煤混合的最优比例。
（b）求烟尘的排放量限制放松 1 磅对每小时产生的蒸汽量的影响。

解：
令
$$\begin{gathered} x_1=\text{煤粉 C1 每小时消耗的吨数} \\ {x}_2=\text{煤粉 C2 每小时消耗的吨数} \end{gathered}$$

$$\max z=12000x_1+9000x_2$$

s.t. { − 200 x 1 + 100 x 2 ≤ 0 2.1 x 1 + 0.9 x 2 ≤ 20 x 1 , x 2 ≥ 0 \text{s.t.}

$$\begin{cases} -200x_1 + 100x_2 \leq 0 \\ 2.1x_1 + 0.9x_2 \leq 20 \\ x_1, x_2 \geq 0 \end{cases}$$ s.t.⎩⎪⎨⎪⎧​−200x1​+100x2​≤02.1x1​+0.9x2​≤20x1​,x2​≥0​

Matlab 代码：

f = [-12000, -9000];
>> A = [-200, 100; 2.1, 0.9];
>> b = [0, 20];
>> Aeq = [];
>> beq = [];
>> lb = zeros(2, 1);
>> ub = [];
>> [x, fval] = linprog(f, A, b, Aeq, beq, lb, ub)
1
2
3
4
5
6
7
8

最优解：$(x_1,x_2)=(5.1282,10.2564)$，$z=153846$。
（a）最优混合比例：$x_1:x_2=1:2$；
（b）
$$\max z=12000x_1+9000x_2$$

s.t. { − 200 x 1 + 100 x 2 ≤ 0 2.1 x 1 + 0.9 x 2 ≤ 21 x 1 , x 2 ≥ 0 \text{s.t.}

$$\begin{cases} -200x_1 + 100x_2 \leq 0 \\ 2.1x_1 + 0.9x_2 \leq 21 \\ x_1, x_2 \geq 0 \end{cases}$$ s.t.⎩⎪⎨⎪⎧​−200x1​+100x2​≤02.1x1​+0.9x2​≤21x1​,x2​≥0​

Matlab 代码：

f = [-12000, -9000];
>> A = [-200, 100; 2.1, 0.9];
>> b = [0, 21];
>> Aeq = [];
>> beq = [];
>> lb = zeros(2, 1);
>> ub = [];
>> [x, fval] = linprog(f, A, b, Aeq, beq, lb, ub)
1
2
3
4
5
6
7
8

最优解：$(x_1,x_2)=(5.3846,10.7692)$，$z=161540$。
最优比：$x_1:x_2=1:2$，产生的蒸汽增加了 161538 - 153846 = 7692 磅/小时。

出处

《运筹学基础 第10版 $\cdot$ 全球版》 哈姆迪 $\cdot$ 塔哈（Hamdy A. Taha）著

补充

缓慢更新中……