线性规划1（蒋政）

第一章 线性规划

1、写出下列问题的模型

（1）一家玩具公司制造三种桌上高尔夫玩具，每一种要求不同的制造技术。高级的一种需要17小时加工装配劳动力，8小时检验，每台利润300元。中级的需要10小时劳动力，4小时检验，利润200元。低级的需要2小时劳动力，2小时检验，利润100元。可供利用的加工劳动力为1000小时，检验500小时。

其次，有市场预测表明，对高级的需求量不超过50台，中级的不超过80台，低级的不超过150台。

制造商决定采用一个能使总利润为最大的最优生产计划。

（2）某建筑材料预制厂生产A1、A2两种产品，现有两种原料，第一种有72立方米，第二种有56平方米，，假设生产每种产品都需要两种原材料。生产每件产品所需原料如表1-1所示。每生产一件A1可获得利润60元，生产一件A2可获得利润1000元，预制厂在现有原料的条件下，A1、A2各应生产多少，才能使获得利润最大。

表1-1 产品 第一种 0.18 0.07 原料（单位：立方米） 第二种 0.09 0.68 A1 A2 （3）用长度为500厘米的条材，截成长度分别为98厘米和78厘米的两种毛坯，要求共截出长98厘米的毛坯10000根，78厘米的20000根，问怎样截取，才能使用料最少？

（4）某商店制定某商品7-12月的进货收货计划，已知商店仓库容量不得超过500件，六月底已存货200件，以后每月初进货一次，假设各月份某商品买进、售出单位如下表1-2所示，问各月进货售货各多少，才能使总收入最多?

表1-2

月 买进（元） 售出（元）

7 28 29

8 24 24

9 25 26

10 27 28

11 23 22

12 23 25

（5）某厂生产A、B、C三种产品。每单位产品A需要1小时技术准备（指设针、试验等）、10小时直接劳动和3公斤材料。每单位产品B需要2小时技术准备、4小时劳动和2千克材料。每单位产品C需要1小时技术准备、5小时劳动和1千克材料。可利用的技术准备时间为100小时，劳动时间为700小时，材料为400千克。

公司对大量购买提供较大的折扣，利润数字如下表1-3所示。试列出使利润最大的数模。

表1-3

产品

销售量（件）

0~40 40~100 100~150 150以上

A

单位利润（元）

10 9 8

0~50 50~100 100以上

产品B

销售量（件）

单位利润（元）

6 4 3

0~100 100以上

产品C

销售量（件）

单位利润（元）

5 4

（6）某一市政建设工程项目在随后的四年中需分别拨款200万元、400万元、800万和 500万元，要求拨款在该年年初提供，市政府拟以卖长期公债的方法筹款。长期公债在筹款的四年中市场利息分别预计为9%，8%，8.5%和9.5%，并约定公债利息在工程完工后即开始付息，连续付20年之后还本。在工程建设的头三年，卖公债的多余部分投入银行作为当年有期储蓄，以便用于随后的几年（显然第四年无有期储蓄），银行的有期储蓄利息率分别预计为8%，7.5%和6.5%。现在的问题是求政府最优的卖公债和尤有期储蓄方案，使该项市政建设工程得以完成，且付息最低。

（7）某钢铁公司有三个铁矿，他们日产矿石分别为5000，3000和1000吨。该公司有四个炼钢厂，他们每天所需的矿石量分别为4000，25000，1000和15000吨。这三个铁矿与四个炼钢厂的距离间下表1-4。问该公司应如何安排运输，既能满足各炼钢厂的需要，又能使吨公里数最小。

表1-4

炼钢厂

距离（公里） 矿山

B1 B2 B3 B4

A1 16 30 41 50 A3 34 30 32 45 A3 55 40 24 33

2、用图解法解下列线性规划问题

（1）minz??x1?2x2 （2）maxz??x1?2x2 x1?x2≥?2 x1?x2≥?2

x1?2x2≤6 x1?2x2≤6

x1，x2≤0 x1，x2≤0 （3）maxz??x1?2x2 （4）maxz?3x1?6x2

x1?x2≥?2 x1?x2≥?2 x1，x2≥0 x1?2x2≤6 x1，x2≥0

（5）maxz?3x1?6x2 x1?x2≤?2 x1?x2≤?5 x1，x2≥0

3、有两个变量的线性规划问题

maxz?x1 x1?x2≤a ?x1?x2≤?1 x1≥0，x2≥0

（1） 证明本题当且仅当a≥1时为可行

（2） 应用图解法，对a≥1的一切值，求线性规划以a表示的最优值。

4、考虑标准线性规划问题

maxz?CX AX?b X≥0

设x和x?1??2?是上述问题的两个最优解。求证向量X?????X?1???1???X?2?是最优

解，?为0与1 之间的任意值。

5、用单纯形法求解以下问题

（1）maxz?x1?32 （2）minz?3x1?x2?x3?x4 x1≤5 ?2x1?2x2?x3?4

x1?2x2≤10 3x1?x2?x4=6 x2≤4 xj≥0，j=1，2，3，4 x1，x2≥0

（3）maxz?x1?2x2?x3?4x4 （4）minz??2x1?8x2?x3 x1?2x2?2x3?2x4≤20 2x1?9x2?3x3≤30 2x1?x2?3x3?2x4≤20 x1?5x2?x3≥?20 xj≥0，j=1，2，3，4 4x1?6x2?2x3≤15

最优解是否唯一，为什么？

xj≥0，j=1，2，3，4

（5）用单纯形法证明下列问题无最优解： maxz?x1?2x2

?2x1?x2?x3≤2 ?x1?x2?x3≤1 x1，x2，x3≥0

（6）应用大M法，证明下列线性规划为不可行： minz?2x1?4x2 2x1?3x2≥2 ?x1?x2≥3 x1，x2≥0 （7）应用大M 单纯法解：

minz?6x1?3x2?4x4

x1 ≥30 x2 ≥50 x3 ≥20 x1?x2?x3?120

x1，x2，x3≥0 （8）用二阶段单纯形法解： minz?6x1?3x2?4x3 x1?x2?x3?x4≤30 3x1?6x2?x3?2x4≤0 x1，x2，x3，x4≥0

6、选择填空

（1）若LP最优解不唯一，则在最优单纯表上（ ）。

A、非基变量的检验数必有为零； B、非基变量的检验数不必有为零者。 （2）极小化（minz）线性规划标准化为极大化问题后，原规划与标准型的最优解（ ），目标函数值（ ）。

A、相差一个负号 B、相同 C、没有确定的关系

（3）大M法和两阶段法是用来（ ）的，当用两阶段法求解LP问题时，第一阶段建立的辅助LP标准型的目标函数为（ ）。

A、简化计算； B、处理人工变量； C、人工变量之和； D、Z??cZ； E、进行灵敏度分析 F、松弛变量、剩余变量和人工变量之和 G、人工变量之和的相反数

（4）线性规划问题的标准型最本质的特点是（ ）。

A、目标要求是极小化； B、变量和右端常数要求非负； C、变量可以取任意值； D、约束条件一定是等式形式。 （5）求解线性规划模型时，引用人工变量是为了（ ）。

A、使该模型存在可行解 B、确定一个初始的基可行解 C、使该模型标准化

'

本文来源：https://www.bwwdw.com/article/n6yt.html