运筹学用割平面法求解

来源：蜘蛛抓取(WebSpider) 时间：2022-05-08 21:04 标签： 割平面法例题详解

第一章　线性规划及单纯形法 线性规划：线性规划（Linear Programming简称LP）是运筹学的一个重要分支，也是运筹学中理论最成熟，应用最广泛的方法之一。自1947年丹捷格提出一般线性规划问题的求解方法－－单纯形法之后，线性规划已被广泛地应用于解决经济管理和工业企业中的实际问题。 第二章　线性规划的对偶问题及灵敏度分析 基本要求： 了解对偶问题的特点； 熟悉互为对偶的问题之间的关系； 掌握对偶规划的理论和性质； 掌握对偶单纯形法； 熟悉灵敏度分析的概念和内容。 第三章　运输问题 基本要求： 了解运输问题的特点； 掌握表上作业法及其在产销平衡运输问题的求解中的应用； 掌握产销不平衡运输问题的求解方法。 第四章　整数规划 基本要求： 　　了解整数规划决策问题的特点 　　熟悉分枝定界法和割平面法的原理及其应用 　　理解0-1规划及其求解方法－－隐枚举法 　　掌握指派问题及其求解方法－－匈牙利法 第五章　图与网络分析 基本要求： 　　了解图论的相关概念； 　　掌握最短路问题及其求解方法； 　　掌握最大流问题及其求解方法。 　　掌握最小费用流问题及其求解方法。

1、有4个公司来某重点高校招聘企业管理（A）、国际贸易（B）、管理信息系统(C)、工业工程(D)、市场营销(E)专业的本科毕业生。经本人报名和两轮筛选，最后可供选择的各专业毕业生人数分别为4，3，3，2，4人。若公司①想招聘A，B, C,D,E各专业毕业生各1人；公司②拟招聘4人，其中C, D专业各1人，A,B,E 专业生可从任两个专业中各选1人；公司③招聘4人，其中C,B,E专业各1人，再从A或D专业中选1人；公司④招聘3人，其中须有E专业1人，其余2人可从余下A,B,C,D专业中任选其中两个专业各1人。问上述4个公司是否都能招聘到各自需要的专业人才，并将此问题归结为求网络最大流问题。

在以下容量网络图中,如其最大流量为16,则各公司都能招聘到所需人才.图中各弧旁数字

2、图中A, B, C, D,E,F分别代表岛和陆地，它们之间有桥相连。问一个人能否经过图中的每座桥恰好一次既无重复也无遗漏？

用点代表岛和陆地，边代表桥，得图。在这个图中有两个奇点：D和E。因而一个人从D出发到E，或从E出发到D，可以做到经过每座桥一次既无重复又无遗漏。

一、回答下面问题(每小题3分)

1.在单纯形法计算中,如果不按最小比值规则确定换基变量,则在下一个解中一定会出现。

2. 原问题无界时，其对偶问题，反之，当对偶问题无可行解时，原问题。

3．已知y0为线性规划的对偶问题的最优解，若y0>0，说明在最优生产计划中对应的资源。

4．已知y0为线性规划的对偶问题的最优解，若y0=0，说明在最优生产计划中对应的资源。

5．已知线形规划问题的原问题有无穷多最优解，则其对偶问题的最优解一定是

6．m个产地n个销地的产销平衡运输问题的模型其决策变量的个数是个；基变量的个数是个；决策变量的系数列向量的特点是。

7．用位势法求解运输问题，位势的含义是；行位势与列位势中有一个的取值是任意的，这是因为。

8.用割平面法求解整数规划，割平面割去了；但未割去

9．按教材中的符号写出最大流问题的数学模型。

10．什么是截集，何谓最小截集？

下表是用单纯形法计算到某一步的表格，已知该线性规划的目标函数值为z=14

（1）求a—g的值；（8分）

（2）表中给出的解是否为最优解。（2分）

三、（每小题6分共12分）

车间为全厂生产一种零件，其生产准备费是100元，存贮费是0.05元／天·个，需求量为每天30个，而且要保证供应。

（1）设车间生产所需零件的时间很短（即看成瞬时供应）；

（2）设车间生产零件的生产率是50个／天。

我要回帖

更多关于 割平面法例题详解 的文章

 

随机推荐