运筹学基础：第2章-线性规划建模（习题笔记）

青旅半醒 2021-09-24 21:42 427阅读 1赞

### 文章目录 ###

*  习题
 *   *  2.1.
     *  2.3.
     *  2.9.
     *  2.11.
     *  2.18.
     *  2.22.
 *  出处
 *  补充

# 习题 #

## 2.1. ##

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

解：  
 x 1 = 外墙涂料的日生产吨数 ; x 2 = 内墙涂料的日生产吨数 . x\_1 = \\text\{外墙涂料的日生产吨数\}; \\\\ x\_2 = \\text\{内墙涂料的日生产吨数\}. x1=外墙涂料的日生产吨数;x2=内墙涂料的日生产吨数.  
（a） − x 1 + x 2 ≥ 1 - x\_1 + x\_2 \\geq 1 −x1\+x2≥1；  
（c） x 1 − x 2 ≤ 0 x\_1 - x\_2 \\leq 0 x1−x2≤0；  
（e） 0.5 x 1 − 0.5 x 2 ≥ 0 0.5x\_1 -0.5 x\_2 \\geq 0 0.5x1−0.5x2≥0。

## 2.3. ##

对于 Reddy Mikks 模型的可行解  x 1 = 2 , x 2 = 2 x\_1 = 2, x\_2 = 2 x1=2,x2=2，确定原料 M1 和 M2 没有用完的量。

解：  
原料 M1 没有用完的量 =  24 − ( 6 x 1 + 4 x 2 ) = 24 − ( 6 ∗ 2 + 4 ∗ 2 ) = 4 24 - (6x\_1 + 4x\_2) = 24 - (6 \* 2 + 4 \* 2) = 4 24−(6x1\+4x2)=24−(6∗2\+4∗2)=4；  
原料 M2 没有用完的量 =  6 − ( x 1 + 2 x 2 ) = 6 − ( 2 + 2 ∗ 2 ) = 0 6 - (x\_1 + 2x\_2) = 6 - (2 + 2 \* 2) = 0 6−(x1\+2x2)=6−(2\+2∗2)=0。

## 2.9. ##

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

解：  
 x 1 = 产品 A 的单位数 x 2 = 产品 B 的单位数 x\_1 = \\text\{产品 A 的单位数\}\\\\ x\_2 = \\text\{产品 B 的单位数\} x1=产品 A 的单位数x2=产品 B 的单位数  
则  
 max ⁡ z = 20 x 1 + 50 x 2 \\max z = 20x\_1 + 50x\_2 maxz=20x1\+50x2

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)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center]  
最优解： ( x 1 , x 2 ) = ( 80 , 20 ) (x\_1, x\_2) = (80, 20) (x1,x2)=(80,20)， z = 2600 z = 2600 z=2600 美元。

## 2.11. ##

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

解：  
令  
 x 1 = 项目 A 的投资额 x 2 = 项目 B 的投资额 x\_1 = \\text\{项目 A 的投资额\} \\\\ x\_2 = \\text\{项目 B 的投资额\} x1=项目 A 的投资额x2=项目 B 的投资额

max ⁡ z = 0.05 x 1 + 0.08 x 2 \\max z = 0.05x\_1 + 0.08x\_2 maxz=0.05x1\+0.08x2

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)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center 1]  
最优解： ( x 1 , x 2 ) = ( 1666.7 , 3333.3 ) (x\_1, x\_2) = (1666.7, 3333.3) (x1,x2)=(1666.7,3333.3)， z = 350 z = 350 z=350。

## 2.18. ##

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

解：  
令  
 x 1 = 煤粉 C1 每小时消耗的吨数 x 2 = 煤粉 C2 每小时消耗的吨数 x\_1 = \\text\{煤粉 C1 每小时消耗的吨数\} \\\\ x\_2 = \\text\{煤粉 C2 每小时消耗的吨数\} x1=煤粉 C1 每小时消耗的吨数x2=煤粉 C2 每小时消耗的吨数

max ⁡ z = 12000 x 1 + 9000 x 2 \\max z = 12000x\_1 + 9000x\_2 maxz=12000x1\+9000x2

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)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center 3]

最优解： ( x 1 , x 2 ) = ( 5.1282 , 10.2564 ) (x\_1, x\_2) = (5.1282, 10.2564) (x1,x2)=(5.1282,10.2564)， z = 153846 z = 153846 z=153846。  
（a）最优混合比例： x 1 : x 2 = 1 : 2 x\_1 : x\_2 = 1:2 x1:x2=1:2；  
（b）  
 max ⁡ z = 12000 x 1 + 9000 x 2 \\max z = 12000x\_1 + 9000x\_2 maxz=12000x1\+9000x2

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)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center 4]  
最优解： ( x 1 , x 2 ) = ( 5.3846 , 10.7692 ) (x\_1, x\_2) = (5.3846, 10.7692) (x1,x2)=(5.3846,10.7692)， z = 161540 z = 161540 z=161540。  
最优比： x 1 : x 2 = 1 : 2 x\_1 : x\_2 = 1:2 x1:x2=1:2，产生的蒸汽增加了 161538 - 153846 = 7692 磅/小时。

## 2.22. ##

一条装配线由 3 个相邻的工作站组成，生产两种型号的收音机 HiFi-1 和 HiFi-2。下表提供了 3 个工作站的装配时间。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center 5]  
每天维护工作站 1、工作站 2、工作站 3 所好用的时间分贝占每个工作站的总可利用时间的 10%，14%，12%，每个工作站一天的最大可利用时间是 480 分钟。确定最优的生产策略，使 3 个工作站的总空闲（或未使用）时间最少。

解：  
令  
 x 1 = HiFi-1 的产量 x 2 = HiFi-2 的产量 x\_1 = \\text\{HiFi-1 的产量\} \\\\ x\_2 = \\text\{HiFi-2 的产量\} \\\\ x1=HiFi-1 的产量x2=HiFi-2 的产量

min ⁡ z = 480 ∗ ( 1 − 10 % + 1 − 14 % + 1 − 12 % ) − ( 15 x 1 + 15 x 2 ) = 1267.2 − ( 15 x 1 + 15 x 2 ) \\min z = 480\*(1 - 10\\% + 1 - 14\\% + 1 - 12\\%) - (15x\_1 + 15x\_2) = 1267.2-(15x\_1+15x\_2) minz=480∗(1−10%\+1−14%\+1−12%)−(15x1\+15x2)=1267.2−(15x1\+15x2)

s.t. \{ 6 x 1 + 4 x 2 ≤ 432 5 x 1 + 5 x 2 ≤ 412.8 4 x 1 + 6 x 2 ≤ 422.4 x 1 , x 2 , x 3 ≥ 0 \\text\{s.t.\} \\begin\{cases\} 6x\_1 + 4x\_2 \\leq 432 \\\\ 5x\_1 + 5x\_2 \\leq 412.8 \\\\ 4x\_1 + 6x\_2 \\leq 422.4 \\\\ x\_1, x\_2, x\_3 \\geq 0 \\\\ \\end\{cases\} s.t.⎩⎪⎪⎪⎨⎪⎪⎪⎧6x1\+4x2≤4325x1\+5x2≤412.84x1\+6x2≤422.4x1,x2,x3≥0

Matlab:

f = [-15, -15];
    A = [6,4; 5,5; 4,6];
    b = [432,412.8,422.4];
    Aeq = [];
    beq = [];
    lb = zeros(3,1);
    ub = [];
    [x, fval] = linprog(f, A, b, Aeq, beq, lb, ub)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center 6]  
最优解： ( x 1 , x 2 ) = ( 50.88 , 31.68 ) (x\_1, x\_2) = (50.88, 31.68) (x1,x2)=(50.88,31.68)， z = 28.8 z = 28.8 z=28.8。

# 出处 #

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

# 补充 #

缓慢更新中……

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center]: /images/20210923/0cb86ac8000b4b9ea4f90d1d2a8b231e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210923/bd0ebd7f3ff543fbac4104921cce145c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20210923/ca5c6d3310cd4da193b9da534030dc84.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20210923/fd56f6d6e2c0483bb6c3fe223f6de14d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20210923/a4f07edcb0a64ffeb082f979d3afc61c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20210923/77627cb314884dd5ad702d882acafbf7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20210923/ba3c473c5ed045a2b2b5574c01e11a2d.png