1、 运筹学复习题一、 用单纯性表求解线性规划模型例 用单纯形法求下列线性规划的最优解 解：1）将问题化为标准型，加入松驰变量 x3、x4 则标准型为:2）列单纯形表。3）解为：X T=（18，4，0，0） ，目标函数值：maxZ=70解答完毕！二、写出一般线性规划的对偶形式非常重要的法则：由 max min 时0,342max21121xxZ0,3 34 a42121xZ对偶问题的约束与原问题变量一致，变量与约束相反；由 min max 时对偶问题的约束与原问题变量相反，变量与约束一致；三、用表上作业法求解运输问题完整步骤：4、 0-1 整数规划建模问题0-1 变量作为逻辑变量 (logical
2、 variable),常被用来表示系统是否处于某个特定状态，或者决策时是否取某个特定方案。例如当决策取方案 P 时 当决策不取方案 P 时1、投资场所的选定 相互排斥的计划例 5.5 某公司拟在市东、西、南三区建立门市部。拟议中有 7个位置 (点 )Ai (i=1， 2， ， 7)可供选择。规定：在东区，由 A1， A2， A3 三个点中至多选两个；在西区，由 A4， A5 两个点中至少选一个；在南区，由 A6， A7 两个点中至少选一个。如选用 Ai 点，设备投资估计为 bi 元，每年可获利润估计为 ci 元，但投资总额不能超过 B 元。问应选择哪几个点可使年利润为最大 ?解题时先引入 0-
3、1 变量 xi (=1,2， ， 7)01x2、指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。设 数学模型如下：目标函数为7,21,01iAxii点 没 有 被 选 用当 点 被 选 用当令 7171234567max.0 or1iiizcbBxstx工 作 时人 做不 分 配 第 工 作 时人 做分 配 第 jixij01 4434241 34332123 221143121 8809086 90757 875907max xxxx xxZ 要求每人做一项工作，约束条件为：每项工作只能安
4、排一人，约束条件为：变量约束：3、背包问题一只背包最大装载重量为 50 公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：求背包中装入每种物品各多少件，使背包中物品总价值最高。设三种物品的件数各为 x1，x2，x3 件，总价值为 z。max z=17x1+72x2+35x3s.t. 10x1+41x2+20x350x1，x2，x30 x1，x2，x3 为整数4、厂址选择模型在 5 个备选地点中选择 3 处建设生产同一产品的工厂，每个地点建厂所需投资，占用农田，建成以后的生产能力如下。总投资不超过114434241 333 242322111xxxx114342414 333
5、 423221211xxxx4,32,10jiij 、，或800 万元，占有农田不超过 60 亩。如何选择厂址，使总生产能力最大。设 5 个 01 变量 x1，x2，x3，x4，x5，max z=70x1+55x2+42x3+28x4+11x5s.t. 320x1+280x2+240x3+210x4+180x5 80020x1+ 18x2+ 15x3+ 11x4+ 8x5 60x1+ x2+ x3+ x4+ x5= 3x1，x2，x3，x4，x5 为 01 变量5、用标号求解动态规划中的最短路问题6、用标号法求解网络最大流问题不不不 54321iixi ,注：总结标号过程1）如果在前向弧上，有 fij（流量） 0,那么给 vj 标号（-vi , l(vj)）.其中 l (vj)=min l(vi), fji .这时，vj 成为标号未检查点。于是 vi 成为标号已检查的点。
