1运筹学作业题一、将下列线性规划问题化为标准型（1）、123123123123123 235567916..192513,0,Max z x x x x x x x x x s t x x x x x x =+++-≥-⎧⎪-+-=⎪⎨-+≤⎪⎪≥⎩符号不限（2）、123123123123 242+3=20..3+4=25,0,26Max z x x x x x x s t x x x x x x =+++⎧⎪+⎨⎪≥≤≤⎩ 二、求出下面线性规划问题的所有基解、基可行解和最优解12123412341234522+34=7..22++2=3,,,0Min z x x x x x x s t x x x x x x x x =-++⎧⎪+⎨⎪≥⎩三、用图解法求解下列线性规划问题，并说明解的类型（1）、121212212 501003002400..250,0Max z x x x x x x s t x x x =++≤⎧⎪+≤⎪⎨≤⎪⎪≥⎩ （2）、12121221212 393224..6250,0Max z x x x x x x s t x x x x x =++≤⎧⎪-+≤⎪⎪≤⎨⎪-≤⎪⎪≥⎩ 四、分别用图解法和单纯形法求解线性规划问题，并指出每一个单纯形表所对应的可行域的顶点122121212 25156224..5,0Max z x x x x x s t x x x x =+≤⎧⎪+≤⎪⎨+≤⎪⎪≥⎩ 五、分别用大M 法及两阶段法求解下列线性规划问题（1）、1231231231312332+114+23..2 1,,0Max z x x x x x x x x x s t x x x x x =---≤⎧⎪-+≥⎪⎨-=-⎪⎪≥⎩ （2）、121212123222..3412,0Max z x x x x s t x x x x =++≤⎧⎪+≥⎨⎪≥⎩2六、写出线性规划问题的对偶问题（1）、123123123123123 3526304320..40,0,Min z x x x x x x x x x s t x x x x x x =-+--+-≥⎧⎪+-≤⎪⎨-+=-⎪⎪≤≥⎩无约束（2）、123452345123413412345 37588 34162332 222 5..210525,0,Max z x x x x x x x x x x x x x x x x s t x x x x x =--++-+-=-⎧⎪+--≥⎪⎪-+-≤-⎪⎨-≤≤⎪⎪≤≤⎪≥⎪⎩无约束（3）、111111111 1,, 1,2,,..0 1,, 1,2,,nj jj nij j i j n ij j i j j j Max z c x a x b i m m a x b i m m m s t x j n n x j n n n====⎧≤=≤⎪⎪⎪⎪==++⎨⎪⎪≥=≤⎪=++⎪⎩∑∑∑无约束七、用对偶单纯形法求解线性规划问题123123123123524324..63510,,0Min z x x x x x x s t x x x x x x =++++≥⎧⎪++≥⎨⎪≥⎩ 八、灵敏度分析给出下列线性规划：12312312312362124+324..26+330,,0Max z x x x x x x s t x x x x x x =+++≤⎧⎪+≤⎨⎪≥⎩ 的最优单纯形表：3其中，s 1、s 2分别为第1、2约束方程的松弛变量。

（1）、试求出最优基不变的b 2变化范围。

（2）、试求出最优解不变的c 3变化范围。

（3）、在原线性规划约束条件之上，增加下面的约束条件： 1232212x x x ++≤其最优解是否变化？如变化，试求出最优解。

九、灵敏度分析给出线性规划问题：121212112 22227..3,0Max z x x x x x x s t x x x =+-+≤⎧⎪-+≤⎪⎨≤⎪⎪≥⎩ 的最优单纯形表：4（1）、写出其对偶规划。

（2）、解出对偶问题的最优解。

（3）、写出最优基矩阵B 及其逆阵B -1。

（4）、若约束条件右端项变为2122b ⎛⎫ ⎪'= ⎪ ⎪⎝⎭，其最优基是否变化？求出变化后的最优解及其最优目标值。

十、灵敏度分析有线性规划问题：1231231231235513 320..1241090,,0Max z x x x x x x s t x x x x x x =-++-++≤⎧⎪++≤⎨⎪≥⎩ 请进行如下条件的灵敏度分析：（1）、约束条件①的右端常数由20变为30； （2）、约束条件②的右端常数由90变为70； （3）、目标函数中x 3的系数由13变为8；（4）、x 1的系数列向量由112-⎛⎫ ⎪⎝⎭变为05⎛⎫ ⎪⎝⎭ ；（5）、增加一个约束条件③：12323550x x x ++≤； （6）、将原约束条件②改变为：12310510100x x x ++≤。

十一、灵敏度分析某工厂生产A 、B 、C 三种产品，设x 、y 、z 分别为三种产品的产量，为制定最优生产计划建立如下模型。

423224100 136100 2..32120 3,,0Max z x y zx y z x y z s t x y z x y z =++++≤⎧⎪++≤⎪⎨++≤⎪⎪≥⎩原材料约束原材料约束原材料约束 （1）、用单纯形法求解最优生产计划；5（2）、在原最优计划基础上进行如下分析：①、由于市场需求变化，产品B 的利润可能发生变化，试求出保持最优生产计划不变的产品B 单位利润的变化范围；若产品B 单位利润由2变为5，求相应的最优生产计划。

②、由于原材料市场变化，原材料1的供应从100单位降至50单位，此时是否会影响最优生产计划？若存在影响，求新的最优生产计划。

③、由于技术改进，生产产品C 的三种原材料单位消耗由原来的4、6、2依次变为2、2、1，求相应的最优生产计划。

十二、对偶理论问题已知线性规划问题：123412412123134243 82 6.. 9 60,1,2,3,4j Max z x x x x x x x x x s t x x x x x x x j =+++⎧++≤⎪+≤⎪⎪++≤⎨⎪++≤⎪⎪≥=⎩（1）、写出该线性规划问题的对偶问题；（2）、已知原问题的最优解：X *=(2,2,4,0)T ，试根据对偶问题的性质，求出对偶问题的最优解。

十三、求出下列运输问题的最优解 表16表2十四、运输问题甲、乙、丙三个城市每年需要煤炭分别为320、250、350万吨，由A 、B 两个煤矿负责供应，已知两个煤矿产量为400、450万吨，调运单价如下表3所示。

由于需求大于供给，经多方协商达成以下协议，甲城市供煤量可减少0-30万吨，乙城市用煤量要完全满足，丙城市供煤量不少于270万吨。

请给出满足上述条件的最优资源分配计划。

表3十五、用图解法求解目标规划（1）、11213312111222123312 10226..26,,,0 1,2,3i iMin z Pd P d P d x x d d x x d d s t x x d d x x d d i +---+-+-++-=++⎧++-=⎪++-=⎪⎨-++-=⎪⎪≥=⎩7（2）、()112233412111222133124412 4002500..3000.40.3300,,,0 1,2,3,4i i Min z P d d P d P d x x d d x x d d s t x d d x x d d x x d d i ++---+-+-+-++-=+++⎧++-=⎪++-=⎪⎪+-=⎨⎪++-=⎪⎪≥=⎩ （3）()112233412111221233124412 23104..535612,,,0 1,2,3,4i iMin z P d d P d P d x x d d x d d s t x x d d x x d d x x d d i ++-+-+-+-+-++-=+++⎧++-=⎪+-=⎪⎪++-=⎨⎪++-=⎪⎪≥=⎩十六、用割平面法求解下列整数规划问题（1）、12121212322314..29,0Max z x x x x s t x x x x =++≤⎧⎪+≤⎨⎪≥⎩且为整数（2）、12341231234123412319108+1181315.54417119..28824,,,0,,Max z x x x x x x x x x x x s t x x x x x x x =+-⎧-++≤⎪⎪⎪++-≤⎨⎪≥⎪⎪⎩为整数十七、解下列指派问题（1）、四个人去完成四项任务，每人完成任务的时间消耗见表4，问如何分配任务使得总时间消耗最少？ 表48（2）、工厂有四个工人操作四台车床，小时单产数据见表5，求产值最大的资源配置方案。

表5（3）、四个人五件工作，每个人做每件工作所耗时间如表6所示，问如何指派任务总耗时最少。

表6十八、求网络最大流v 13v 7。