运筹学作业-王程130404026-Word格式.docx

运筹学作业-王程130404026-Word格式.docx

《运筹学作业-王程130404026-Word格式.docx》由会员分享，可在线阅读，更多相关《运筹学作业-王程130404026-Word格式.docx（98页珍藏版）》请在冰点文库上搜索。

⑷图解法：

当经过点时，取得唯一最优解。

1.2将下述线性规划问题化成标准形式。

1.3对下述线性规划问题找出所有基解，指出哪些是基可行解，并确定最优解。

（1）该线性规划问题的全部基解见下表中的①～⑧，打√者为基可行解，注*者为最优解，z*=36。

（2）该线性规划问题的标准形式为：

其全部基解见下表中的①～⑥，打√者为基可行解，注*者为最优解，z*=5。

1.4题1.1（3）中，若目标函数变为，讨论的值如何变化，使该问题可行域的每个顶点依次使目标函数达到最优。

由目标函数可得：

，其中。

⑴当时，可行域的顶点A使目标函数达到最优；

⑵当时，可行域的顶点B使目标函数达到最优；

⑶当时，可行域的顶点C使目标函数达到最优；

⑷当或时，最优解为O点。

1.6分别用单纯形法中的大M法和两阶段法求解下列线性规划问题，并指出属哪一类解。

其中M是一个任意大的正数，据此可列出初始单纯形表如下：

cj

2

3

1

M

θi

CB

XB

b

x1

x2

x3

x4

x5

x6

x7

8

6

[4]

-1

cj-zj

2-4M

3-6M

1-2M

1/4

[5/2]

1/2

-1/4

-1/2

4/5

9/5

3/5

-2/5

-3/10

1/5

1/10

3/10

-1/5

-1/10

2/5

M-1/2

由单纯形表的计算结果得：

最优解,

目标函数最优值

X存在非基变量检验数，故该线性规划问题有无穷多最优解。

据此可列出单纯初始形表如下：

-4

-6

-2

第一阶段求得的最优解，目标函数的最优值，因人工变量，所以是原线性规划问题的基可行解。

于是可以进行第二阶段计算，将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，如下表：

由表中计算可知，原线性规划问题的最优解，目标函数的最优值，由于存在非基变量检验数，故该线性规划问题有无穷多最优解。

其中M是一个任意大的正数，据此可列出单纯形表如下：

10

15

12

-M

9

5

[5]

-5

-

5/2

10+2M

15+M

12+M

24

7/5

[16]

3/2

7/3

39/80

9/16

-43/80

3/16

1/16

-7/16

-1/80

-3/80

由单纯性表的最终表可以看出，所有非基变量检验数，且存在人工变量，故原线性规划问题无可行解。

据此可列出单纯初始形表如下：

7/16

3/80

第一阶段求得最优解，因人工变量，且非基变量检验数，所以原线性规划问题无可行解。

1.5考虑下述线性规划问题：

（1）上界对应的模型如下（c，b取大，a取小）

最优值（上界）为：

21；

（2）下界对应的模型如下（c，b取小，a取大）

最优值（下界）为：

6.4。

1.7已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到表1-21，试求括弧中未知数的值。

1.8若X⑴,X

（2）均为某线性规划问题的最优解，证明在这两点连线上的所有点也是该问题的最优解。

1.9考虑线性规划问题

模型中为参数，要求：

⑴组成两个新的约束，根据式和式，以为基变量，列出初始单纯形表；

⑵在表中，假定，则为何值时，为问题的最优基；

⑶在表中，假定，则为何值时，为问题的最优基。

1.10试述线性规划模型中“线性”二字的含义，并用实例说明什么情况下线性的假设将被违背。

答：

线性的含义：

一是严格的比例性，如生产某产品对资源的消耗量和可获取的利润，同其生产数量严格成比例；

二是可叠加性，如生产多种产品时，可获取的总利润使各项产品的利润之和，对某项资源的消耗量应等于各产品对该资源的消耗量之和；

三是可分性，即模型中的变量可以取值为小数、分数或某一实数；

四是确定性，指模型中的参数cj,aij,bi均为确定的常数。

很多实际问题往往不符合上述条件，例如每件产品售价3元，但成批购买就可以得到折扣优惠。

1.11判断下列说法是否正确，为什么？

⑴含n个变量m个约束的标准型的线性规划问题，基解数恰好为个；

答：

错误。

基本解的个数=基的个数

⑵线性规划问题的可行解如为最优解，则该可行解一定为基可行解；

当有唯一最优解时，最优解是可行域顶点，对应基本可行解；

当有无穷多最优解时，除了其中的可行域顶点对应基本可行解外，其余最优解不是基本可行解。

⑶如线性规划问题存在可行域，则可行域一定包含坐标的原点；

如果约束条件中有一个约束所对应的区域不包含坐标的原点，则即使有可行域，也不包含坐标的原点。

⑷单纯形法迭代计算中，必须选取同最大检验数对应的变量作为换入基的变量。

若此时最大检验数，可是，则问题是无界解，计算结束。

1.12线性规划问题,如是该问题的最优解，又为某一常数，分别讨论下列情况时最优解的变化。

⑴目标函数变为；

⑵目标函数变为；

⑶目标函数变为，约束条件变为。

⑴最优解不变；

⑵C为常数时最优解不变，否则可能发生变化；

⑶最优解变为：

X/λ。

1.13某饲养场饲养动物出售，设每头动物每天至少需要700g蛋白质、30g矿物质、100mg维生素。

现有五种饲料可供选用，各种饲料每kg营养成分含量及单价如表1-22所示。

要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。

最优解为

1.14辽源街邮局从周一到周日每天所需的职员人数如下表1-23所示。

职员分别安排在周内某一天开始上班，并连续工作5天，休息2天。

要求确定：

⑴该邮局至少应配备多少职员，才能满足值班需要；

⑵因从周一开始上班的，双休日都能休息；

周二或周日开始上班的，双休日内只能有一天得到休息；

其他时间开始上班的，两个双休日都得不到休息，很不合理。

因此邮局准备对每周上班的起始日进行轮换（但从起始日开始连续上5天班的规定不变），问如何安排轮换，才能做到在一个星期内每名职工享受到同等的双休日的休假天数；

⑶该邮局职员中有一名领班，一名副领班。

为便于领导，规定领班于每周一、三、四、五、六上班，副领班于一、二、三、五、日这5天上班。

据此试重新对上述要求⑴和⑵建模和求解。

⑵对这23名职工分别编号①，②，…，，以23周为一个周期，这23名职工上班安排见下表。

⑶此时只需在每天人数中减去领班和副领班两人即可，重现建模如下：

1.15一艘货轮分前、中、后三个舱位，它们的容积与最大允许载重量如表1-24所示。

现有三种货物待运，已知有关数据列于表1-25。

又为了舱运安全，前、中、后舱的实际载重量大体积保持各舱最大允许载重量的比例关系。

具体要求：

前、后舱分别与中舱之间载重量比例的偏差不超过15%，前、后舱之间不超过10%。

问该货轮应装载A、B、C各多少件运费收入为最大？

试建立这个问题的线性规划模型。

1.16长城通信公司拟对新推出的一款手机收费套餐服务进行调查，以便进一步设计改进。

调查对象设定为商界人士及大学生，要求：

⑴总共调查600人，其中大学生不少于250人；

⑵方式分电话调查和问卷调查，其中问卷调查人数不少于30%；

⑶对大学生电话调查80%以上应安排在周六或周日，对商界人士电话调查80%以上应安排在周一至周五；

⑷问卷调查时间不限。

已知有关调查费用如表1-26所示，问该公司应如何安排调查，使总的费用为最省。

1.17生产存储问题。

某厂签订了5种产品（i=1，…，5）上半年的交货合同。

已知各产品在第j月（j=1，…，6）的合同交货量Dij，该月售价sij、成本价cij及生产1件时所需工时aij。

该厂第j月的正常生产工时为tj，但必要时可加班生产，第j月允许的最多加班工时不超过tj＇，并且加班时间内生产出来的产品每件成本增加额外费用cij＇元。

若生产出来的产品当月不交货，每件库存1个月交存储费pi元。

试为该厂设计一个保证完成合同交货，又使上半年预期盈利总额为最大的生产计划安排。

1.18宏银公司承诺为某建设项目从2003年起的4年中每年年初分别提供以下数额贷款：

2003年—100万元，2004年—150万元，2005年—120万元，2006年—110万元。

以上贷款资金均需于2002年年底前筹集齐。

但为了充分发挥这笔资金的作用，在满足每年贷款额情况下，可将多余资金分别用于下列投资项目：

⑴于2003年年初购买A种债券，期限3年，到期后本息合计为投资额的140%，但限购60万元；

⑵于2003年年初购买B种债券，期限2年，到期后本息合计为投资额的125%，且限购90万元；

⑶于2004年年初购买C种债券，期限2年，到期后本息合计为投资额的130%，但限购50万元；

⑷于每年年初将任意数额的资金存放于银行，年息4%，于每年年底取出。

求宏银公司应如何运用好这笔筹集到的资金，使2002年年底需筹集到的资金数额为最少。

1.19红豆服装厂新推出一款时装，据经验和市场调查，预测今后6个月对该款时装的需求为：

1月—3000件，2月—3600件，3月—4000件，4月—4600件，5月—4800件，6月—5000件。

生产每件需熟练工人工作4h，耗用原材料150元，售价为240元/件。

该厂1月初有熟练工80人，每人每月工作160h。

为适应生产需要，该厂可招收新工人培训，但培训一名新工人需占用熟练工人50h用于指导操作，培训期为一个月，结束后即可上岗。

熟练工人每月工资2000元，新工人培训期间给予生活补贴800元，转正后工资与生产效率同熟练工人。

又熟练工人（含转正一个月后的新工人）每月初有2%因各种原因离职。

已知该厂年初已加工出400件该款时装作为库存，要求6月末存库1000件。

又每月生产出来时装如不在当月交货，库存费用为每件每月10元。

试为该厂设计一个满足各月及6月末库存要求，又使1～6月总收入为最大的劳动力安排方案。

第二章线性规划的对偶理论与灵敏度分析

2.1写出下列线性规划问题的对偶问题，并以对偶问题为原问题，再写出对偶的对偶问题。

2.2判断下列说法是否正确，并说明为什么。

⑴如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解；

如果原问题是无界解，则对偶问题无可行解。

⑵如果线性规划的对偶问题无可行解，则原问题也一定无可行解；

如果对偶问题无可行解，也可能是因为原问题是无界解。

⑶在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值；

如果原问题是求极小，则结论相反。

⑷任何线性规划问题具有唯一的对偶问题。

正确。

2.5已知某求极大线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如表2-30所示，求表中各括号内未知数（a）～（l）的值。

l=1，k=0，a=2，c=3，h=-1/2，b=10，e=5/4，f=-1/2，d=1/4，

g=-3/4，i=-1/4，j=-1/4.

2.6给出线性规划问题

⑴写出其对偶问题；

⑵用图解法求解对偶问题；

⑶利用⑵的结果及根据对偶问题性质写出原问题最优解。

⑴其对偶问题为：

⑵图解法求解：

（3）根据互补松弛型性质可以得到最优解

2.7给出线性规划问题

⑵利用对偶问题性质证明原问题目标函数值。

⑵易得是对偶问题的一个可行解，带入目标函数得，故原问题的目标函数值。

2.8已知线性规划问题

试根据对偶问题性质证明上述线性规划问题目标函数值无界。

2.9给出线性规划问题

要求：

⑵已知原问题最优解为,试根据对偶理论，直接求出对偶问题的最优解。

⑵已知原问题最优解为，带入原问题，第4个约束不等式成立，故。

又由于大于0，上面对偶问题前3个约束取等号，故得到最优解：

。

2.10已知线性规划问题A和B如下：

试分别写出同间的关系式。

.

2.11用对偶单纯形法求解下列线性规划问题。

⑴先将问题改写为：

列出单纯形表，用对偶单纯形法求解步骤进行计算过程如下：

由上表可得原问题最优解为，代入目标函数得。

⑵先将问题改写为：

2.12考虑如下线性规划问题：

⑵用对偶单纯形法求解原问题；

⑶用单纯形法求解其对偶问题；

⑷对比⑵与⑶中每步计算得到的结果。

⑵先将问题改写为

⑶用单纯形法求解其对偶问题：

由上表可得对偶问题最优解为，代如目标函数。

2.13已知线性规划问题：

先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。

⑴目标函数变为;

⑵约束右端项由变为；

⑶增添一个新的约束条件。

先用单纯形法计算如下：

由上表可得最优解为

⑴当目标函数变为时，反映到最终单纯形表上如下表所示：

因变量x2的检验数大于零，故需继续用单纯形法迭代计算得下表：

由上表可得最优解变为

⑵因有

将其反映到最终单纯形表中如下表所示：

由表可得最优解为

⑶先将原问题的最优解带入新增约束条件中，因故原问题最优解发生改变。

给新增约束条件中加入松弛变量并规范化得：

以x6为基变量，将上式反映到最终单纯形表中得下表：

因上表中x1列不是单位向量，故需进行变换，得下表：

因上表中对偶问题为可行解，原问题为非可行解，故用对偶单纯性法迭代计算得下表：

由上表可得最优解为

2.14给出线性规划问题

当时用单纯形法求解得最终单纯形表见表2-31。

试分析

⑴当时，范围内变化时的变化；

⑵当时，范围内变化时的变化。

⑴将反映到最终单纯形表中得下表：

在上表中，当时，表中解为最优，且

当时，变量的检验数>

0，用单纯形法迭代计算得下表：

在第一个表中，当时，变量的检验数>

⑵因有

将其反映到最终单纯形表中得下表：

当时，表中基变量，这时可用对偶单纯形法继续迭代计算得下表：

在第一个表中，当时，表中基变量，这时可用对偶单纯形法继续迭代计算得下表：

2.15分析下列线性规划问题中，当变化时最优解的变化，并画出对的变化关系图。

⑴先令求得最优解，并将反映到最终单纯形表中，得下表：

上表中，当时，表中解为最优，且，

上表中，当时，表中解为最优，且；

下图表明了目标函数值随值变化的情况：

⑵先令求得最优解，并将反映到最终单纯形表中，得下表：

⑶令求解得最终单纯形表，又因有

将其反映到最终单纯形表中，得下表：

上表中当时，解为最优解且，

当时，表中基变量将小于零，这时用对偶单纯形法继续求解得下表：

表中当时为最优解，且，

当时，原问题无可行解。

⑷令求解得最终单纯形表，又因有

上表中当时，解为最优解且，

表中当时为最优解，且

2.16某厂生产A、B、C三种产品，其所需劳动力、材料等有关数据见表2-32。

⑴确定获利最大的产品生产计划；

⑵产品A的利润在什么范围内变动时，上述最优计划不变；

⑶如果设计一种新产品D，单件劳动力消耗为8h，材料消耗为2kg，每件可获利30元，问该种产品是否值得生产？

⑷如果原材料数量不增，劳动力不足时可以从市场购买，为1.8元/h。

问：

该厂要不要招收劳动力扩大生产，以购多少为宜？

⑴用x1，x2，x3分别表示该厂生产的三种产品A、B、C的数量，则对该问题建