1、1.1 线性规划标准型maxZ=c1x1+c2x2+cnxns.t. a11x1+a12x2+a1nxn =b1 a21x1+a22x2+a2nxn =b2 am1x1+am2x2+.+amnxn =bm x1,x2.xn 0用两个变量的差值代替无约束变量，左边加一个变量将变=，左边减一个变量将变=。目标函数左边乘-1 将 minZ 变 maxZ1 用对偶单纯形法解下列线性规划问题min S = x1 + 4x2 + 3x4s.t. x1+2x2 - x3 +x4 3-2x1 - x2+4x3 +x4 2x1，x 2 ， x3， x4 0解：此题可用人工变量方法求，但也可用对偶单纯形法。max
2、 S = -x1- 4x2 - 3x4s.t. -x1 -2x2+ x3 -x4 +x5= -3 2x1 + x2-4x3 -x4+x6 = -2x1，x 2 ， x3， x4 ，x 5 ，x 6 0Cj -1 -4 0 -3 0 0CB XB x1 x2 x3 x4 x5 x6 b0 x5 -1 -2 1 -1 1 0 -30 x6 2 1 4 -1 0 1 -2 -1 -4 0 -3 0 0 0常数项是负数且最小，确定出基变量 x5。用出基变量 x5 行的所有负数分别去除对应的检验数，最小值对应的为进基变量 x1，交叉元素为主元（-1） 主元运算：第一行乘（-1） 【提示: 表格同上， x
3、5 行对应数字乘-1 ，这里不抄】主元运算：第二行加上 第一行乘（-2） 【提示：是对应第二张表的，继续画出表 3】计算检验数 确定出基变量 X6 确定进基变量 X3，主元（ -2）Cj -1 -4 0 -3 0 0CB XB x1 x2 x3 x4 x5 x6 b0 x1 1 2 1 1 -1 0 30 x6 0 -3 -2 -3 2 1 -8 0 -2 -1 -2 -1 0 -3主元运算：第一行加 第二行乘（-1/2） 【根据上表继续画表 5， 行不填】计算检验数：全为非正。但此时常数 b 已全大于零，最优解=（7，0，4，0）最优值 S = - 7 S=7Cj -1 -4 0 -3 0
4、0CB XB x1 x2 x3 x4 x5 x6 b-1 x1 1 7/2 0 1 -2 -1/2 70 x3 0 3/2 1 -3 -1 -1/2 4 0 -1/2 0 -1/2 -2 -1/2 -72 用对偶单纯形法解下列线性规划问题min S = x1 + 2x2s.t. -x1+2x2 - x3 1 -x1 -2x2 + x3 6 x1，x 2 ， x3 0解：将原问题化成 max S = -x1 - 2x2s.t. x1 - 2x2 + x3 + x4 =-1 x1 + 2x2- x3+ x5 =-6 x1,x2,x3,x4,x5 0Cj -1 -2 0 0 0CB XB x1 x2
5、 x3 x4 x5 b0 X4 1 -2 1 1 0 -10 X5 1 2 -1 0 1 -6 -1 -2 0 0 0 0常数项最小出基变量 X5，按比值无法比较。常数项次小出基变量 X4，按比值 X2 为进基变量。主元（ -2）主元运算：第一行乘（-1/2） 【提示：表格同上 X4 行对应数字乘-1/2，画出表格 2】主元运算：第二行加 第一行乘（-2） 【提示：是对表 2 而言的，画出表 3】常数项为负数的行元素全大于零，原问题无可行解。3 某地区在制定十年电力规划设置决策变量 设备选方案 1，2，3 的装机台数分别为 x1、x 2、x 3，它们的年发电量分别为 x6、x 7、x 8 亿度
6、，备选方案 1 无前期土建工程要求，备选方案 2 和 3 都需要前期土建工程，这两个前期土建工程是否施工用变量 x4、x 5 代表。则 x1 取值 0-5 之间的整数，x 2、x 3取值 0-4 之间的整数， x4、x 5 只能取 0 或 1， x6、x 7、x 8 大于零。约束方程 满足装机容量需求约束：10x 1+25x2+ 30x3 180满足规划年发电量需求约束：x 6+x7 + x8 100各电站容量与发电量平衡方程：每台机组发电量等于单机容量乘全年小时数，再乘与负荷因子，换算亿度量纲，即：方案 1：x 6=(0.66876010/10000)x1方案 2： x7=(0.487602
7、5/10000)x2得三个约束方程：5.782 x 1-x6= 0 8.76 x2-x7= 0 18.39 x3-x8= 0每个方案最多的装机台数约束： 方案 1：不需前期土建工程； x1 5方案 2：前期土建工程是装机的先决条件，且小于最大允许数； x2 4 x4方案 3：前期土建工程是装机的先决条件，且小于最大允许数； x3 4 x5变量取值限制 x1、x 2、x 3 0 且整数 x6、x 7、x 8 0 x4 或 x5=1 前期土建工程要求x4 或 x5=0 无前期土建工程要求设计目标函数 目标函数：年成本费用最低。 成本包括两大部分：可变成本：与发电量有关的成本，如：原材料，燃料，动力
8、和活劳动消耗等。即参数表中年运行成本。不变成本：指与装机容量及前期土建投资有关的成本。方案 1：单机投资回收因子=210.103=2.163(百万元）方案 2：单机投资回收因子=700.0578=4.046(百万元）方案 3：单机投资回收因子=650.103=6.695(百万元）方案 2 和 3 的前期土建投资的年资本回收成本分别为 5040.0578=29.131(百万元）2400.103=24.72(百万元） 对方案 1，2，3 每发一亿度电的运行成本分别为 4.11,2.28,3.65 百万元。则数学模型如下：Min Z = 2.163x1+4.046x2+ 6.695x3 + 29.1
9、31x4+ 24.72x5 + 4.11x6 + 2.28x7 + 3.65x8s.t. 10x1+25x2+ 30x3 180 x6+x7 + x8 1004 某石油公司四厂七售区炼油厂 1 2 3 4日产量 35 25 15 40解：平衡问题，用最小元素法求初始方案。计算检验数。 闭合回路。最优方案如下，最小运费=元 有非基变量的检验数=0，有无穷多组解，另外一个解如下：5 铁路列车编组站M/M/1/排队问题。其中 =2， =3， =/=2/32=W1-P0-P1-P2=W1-(l-)- (l-) 1 -(l-) 2=1*3=3=(2/3)3=0.296（小时）故每天列车由于等待而支出的平
10、均费用E=24W0a=24*2*0.296*a=14.2a 元销售区 1 2 3 4 5 6 7日最大售量 25 20 10 25 10 15 106 某修理店只有一位修理工解：M/M/1/ / 排队问题.其中 =4， =1/0.1=10(人/小时） ，= /=2/51修理店内空闲的概率 P0= 1-= (1-2/5)=0.6店内恰有 3 个顾客的概率P3= 3(1-)=(2/5)3(1-2/5)=0.038店内至少有 1 位顾客的概率 P N1=1-P0=1- (1-)= =2/5=0.4 在店内平均顾客数 L= / (1-)=(2/5)/(1-2/5)= 0.67(人）每位顾客在店内平均逗
11、留时间W=L/=0.67/4=10 分钟等待服务的平均顾客数 Lq=L-=0.67-2/5=0.27(人)每个顾客平均等待服务时间 Wq = Lq/ =0.27/4=0.0675 小时=4 分7 某单人理发店有 6 个椅子N=7 为系统中最大的顾客数，=3 人/小时，=4 人/小时1） 、某顾客一到达就能理发的概率相当于理发店内无顾客的概率：P 0=（1- ）/1- N+1=1- （3/4 ） /1-（3/4） 7+1=0.27782） 、需要等待的顾客数的期望值？LS=（/1- ） -（N+1） N+1/ （1- N+1）=(3/4)/1-(3/4） - 8(3/4) 8/ 1-(3/4)8
12、=2.11Lq=Ls-(1-P0)=2.11-(1-0.2778)=1.39(人)3） 、求有效到达率？ e=(1-P 0)= 4(1-0.2778)=2.89(人/小时)4） 、求一顾客在理发馆内逗留的期望时间？Ws=Ls/ e=2.11/2.89=0.73(小时)=43.8（分钟）5） 、在可能来的顾客中不等待就离开的概率就是求系统中有 7 个顾客的概率：P7=（1- ） n/1- N+1=(1-0.75)0.757/1-0.758=3.7%8 某车间有 5 台机器解：m=5,=1/15，=1/12, = /=0.81） 、P 0=0.805!/5!+0.815!/4!+0.825!/3!
13、+0.835!/2!+0.845!/1!+0.855!/0!-1=1/136.8=0.00732） 、 P5= 0.855!/0! P0=0.287 3） 、L s=5-（1/0.8 ） （1-0.0073）=3.76（台）4） 、L q=3.76-（1-0.0073） =2.77 （台）5） 、W s=5/(1/12)(1-0.0073)-15=46(分钟)6） 、W q=46-12=34 (分钟) 7)、机器停工时间过长，修理工几乎没有空闲时间，应当提高服务效率，减少修理时间或增加修理工人。9 某售票处有三个窗口解：这是一个 M/M/c/ / 型排队问题。其中 c=3, /=0.9/0.4
14、=2.25, =/c=0.7511） 、整个售票处空闲的概率？P 0=(2.25)0/0!+ (2.25)1/1!+ (2.25)2/2!+ (2.25)3/3!1/(1-0.75)-1=0.0748 2） 、平均队长？ lq=(2.25)30.75/3!(1-0.75)20.0748 =1.7Ls=1.7+2.25=3.95 3） 、平均等待时间和逗留时间？W q=1.7/0.9=1.89(分钟); Ws=3.95/0.9=4,39 4） 、顾客必须等待的概率？P(n3)=P(1-P 0-P1-P2)=1-0.0748-1 (2.25)1 0.0748/1!- 1 (2.25)2 0.074
15、8/2!=1-0.0748-0.1683-0.1893=0.567610 两个修理工人 5 台机器解：根据题意，m=5, =1 （次/ 小时） ，=4 （台/ 小时）c=2, =m/c=5/8=0.625,c/m=0.25P0=(1/5!)(1/5!)(1/4)0+ (1/4!）(1/4) 1+( 1/2!3!）(1/4) 2+(22/2!）(1/2! )(1/8)3+(1/8)4+（1/8） 5 -1=0.315 P1=0.394，P 2=0.197，P 3=0.074，P 4=0.018,P5=0.0021） 、L q=P3+2P4+3P5=0.118 2） 、L s=P1+2P2+3P3
16、+4P4+5P5=1.0923） e=1(5-1.092)=3.908 4）W q=0.118/3.908=0.03（小时） 5）W s=1.092/3.908=0.28 小时11 某医院手术室根据病人来诊和完成手术时间的记录（1）算出每小时病人平均到达率=nf n/100=2.1（人/小时）每次手术平均时间=vf v/100=0.4（小时/ 人） 每小时完成手术人数=1/0.4=2.5（人/小时）（2）取 =2.1 =2.5。可认为病人到达服从泊松分布，手术时间服从负指数分布。（3）=/=2.1/2.5=0.84 说明服务机构（手术室）有 84%的时间是繁忙的，16%空闲（4）病房中病人数
17、Ls=2.1/（2.5-2.1）=5.25（人）排队等待病人数 Lq=0.845.25=4.41（人） 病人逗留时间 Ws=1/(2.5-2.1)=2.5(小时)病人排队等待时间 Wq=0.84/（2.5-2.1 ）=2.1（小时）12 目标规划某人有一笔 50 万元的资金可用于长期投资解：设 xi 为第 I 种投资方式在总投资额中的比例，则模型如下：Max Z=11x1+15x2 +25x3 +20x4+10x5 +12x6+3x7s.t. 3x1+10x2 + 6x3+2x4+x5+ 5x6 5 11x1+15x2+25x3+20x4+10x5+12x6+3x7 13x1+ 3x2 + 8
18、x3 + 6x4+x5+ 2x6 4 15x2 +30x3 +20x4+5x5 +10x6 10x1+x2 +x3 + x4 +x5 +x6+ x7 = 1 x1,x2,x3,x4,x5,x6,x7 0整数规划整数规划的一般数学模型:max (min) Z = c jxj s.t. a ijxj bi(i=1,2,m)xj 0 且部分或全部是整数13 登山准备序号 1 2 3 4 5 6 7物品 食品 氧气 冰镐 绳索 帐篷 相机 设备重量 5 5 2 6 12 2 4重要系数 20 15 18 14 8 4 10解：令 xi=1 表示登山队员携带物品 i，x i=0 表示登山队员不携带物品则
19、问题表示成 0-1 规划:max Z= 20x1+15x2 +18x3 +14x4+8x5 +4x6 +10x7s.t. 5x1 + 5x2 +2x3 +6x4 +12x5 +2x6 +4x7 25 xi=1 或 xi=0 i=1,2,.714 某机械化施工公司解：设每天安排 WY50、WY75、WY100 液压挖掘机和 5t、8t、15t 自卸汽车各是 X1 、 X2 、 X3 、 X4 、 X5 、 X6 台，则根据题意建立整数规划模型为：Min Z = 880 X1 +1060 X2 +1420 X3 +318 X4 +458 X5 +726 X6S.t 401 X1 +549 X2 +
20、692 X3 980 28X4 + 45 X5 + 68X6 98028X4 + 45 X5 + 68X6 401 X 1 +549 X2 +692 X3 X14 X22 X3 1 X4 10 X5 20 X6 10 Xj 0,且为整数。 15 某种农作物在生长解：假设用甲、乙、丙、丁为 X1、X 2、X 3、X 4 公斤。数学模型为：min S=4x 1+15x2 + 10x3 +13x4s.t. 0.03x1+0.3x2+0.15x4 33 0.05x1+ 0.2x3 +0.1x4 24 0.14x1+0.07x4 24x1，x 2 ， x3， x4 0 将模型化为： max S= - 4
21、x1-15x2-10x3-13x4- 0.03x1-0.3x2-0.15x4 +x5= -33 - 0.05x1- 0.2x3 -0.1x4+x6= -24 - 0.14x1-0.07x4+x7 = -24 x1,x2,x3,x4,x5,x6,x7 0初始可行基 B1=（P 5，P 6，P 7）Cj -4 -15 -10 -13 0 0 0CB XB x1 x2 x3 x4 x5 x6 x7 b0 x5 -0.03 -0.3 0 -0.15 1 0 0 -330 x6 -0.05 0 -0.2 -0.10 0 1 0 -240 x7 -0.14 0 0 -0.07 0 0 1 -42 -4 -
22、15 -10 -13 0 0 0 0第三行乘以 1/（-0.14） 【提示：根据上表，x 7 对应行乘那个数字，画出表 2】第一行加上 第三行乘（0.03） 【提示：对表 2 而言的，是变第一行，第三行同表 2.画表 3】第二行加上 第三行乘（0.05） 【提示：对表 3 而言的，是变第二行，第三行同表 3.画表 4】第一行除（-0.3） 计算检验数Cj -4 -15 -10 -13 0 0 0CB XB x1 x2 x3 x4 x5 x6 x7 b-15 x2 0 1 0 0.45 -3.33 0 0.7 800 x6 0 0 -0.2 -0.075 0 1 -0.36 -9-4 x1 1
23、0 0 0.5 0 0 -7.14 300 0 0 -10 -4.25 -49.95 0 -18.06 -2400第二行除以（-0.2)Cj -4 -15 -10 -13 0 0 0CB XB x1 x2 x3 x4 x5 x6 x7 b-15 x2 0 1 0 0.45 -3.33 0 0.7 800 x6 0 0 1 0.375 0 -5 1.8 45-4 x1 1 0 0 0.5 0 0 -7.14 300 -2850最优解（300，80，45） 最优值 S= -2850 S=285016 设有街道图，求他的最优投递路线。有四个奇顶点配成两对 v2 v4 ，v 6 v8（1）任取 v2
24、v4 通路 v2 v1 v8 v7 v6 v5 v4 任取 v8 v6 通路 v8 v1 v2 v3 v4 v5 v6将通路上的边各重复一次，无奇顶点是欧拉图，有第一个可行方案重复边总长为=51 （2）调整可行方案：有二条重复边的去了。重复边总长为=21，检查图中圈：总权=24 重复边长=14 大于 24/2（3）去了原重复边，添上原没有的重复边，重复边总长=17，检查图中圈：总权=24， 圈上重复边长=13 大于 24/2 （4）去了原重复边，添上原没有的重复边重复边总长=15，得最优方案17 一个工厂要将产品送到火车站解（1）将各弧的单位运费作为长度，求 v0 到 vn 的最短增流路 v0
25、v1v3v4vn，路长为 8，可增加 1 单位的流值。 （2）再求 v0 到 vn 的最短增流路 v0v1v4vn，路长为 9，可增加 2 单位的流值。（3）再求 v0 到 vn 的最短增流路 v0v2v3v1v4vn，路长为 14，可增加 1 单位的流值。 （4）再求 v0 到 vn 的最短增流路 v0v2v3v5vn，路长为 18，可增加 2 单位的流值。最大流为 8，最小运费=33+54+3 4+11+32+22+29+42+43=9018 一家电脑制造公司自行生产扬声器用于自己的产品若不允许缺货解:R=6000 台/月，c3 =1200 元，c1 =0.10 元/ 月, k=20 元。
26、19 一家电脑制造公司自行生产扬声器用于自己的产品若允许缺货解： R=6000 台/月,c3 =1200 元,k=20 元,c1 =0.10 元/月, c2 =1 元/只。、20 某店拟出售甲商品解：该站的缺货损失每单位商品为 70-50=20。滞销损失每单位商品 50-40=10，故 k=20， h=1021 设某公司利用塑料作原料制成产品出售解：1、计算临界值 N=（C2-K）/ （C1+C2 ）=（1015-800）/（1015+40）=0.2042、选 使不等式 成立的 Si 最小值作 S120（ 元 月 )6120.Rc2）*C（ Q（ 只 ）0612（ 月 ）2cT*31313 1
27、09元 /月6/.120.2)cR/(2cC(Q) 4（ 只 ）0- 58（ 只 ）1.612)c(2R（ 月 ）T1312m01231 。 此 时 损 失 的 期 望 值 最 小 为 7单 位 ，F(7)， 故 订 货 量 应hk因 F(6)0.4r!6e0.63,r!e计 表 。记 作 （ Q） ， 可 查 统PP70kh70506QriSrNP()40， 作 为 0.240.234.2i3、原存储 I=10，订货量 Q=S-I=40-10=304、求 s。由于已算出 S=40，可以作为 s 的 r 值只有 30 或 40 两个值。将 30 作为 s得：80030+1015（40-30）0
28、.2+（50-30）0.4+（60-30）0.2=40240将 40 作为 s 值，得：60+80040+40（40-30）0.2+1015（50-40）0.4+（60-40 ）0.2=40260 即左端数值为 40240，右端数值为 40260，不等式成立，30 已是 r 的最小值，故 s=30.故存储策略为：每个阶段开始时检查存储量 I，当 I 30 箱时不必补充存储。当 I30箱时补充存储量达到 40 箱。22 木器厂有六个车间，办事员经常要到各个车间了解生产进度。最短路23 有一批货物要从 v1 运到 v9 求最短运输路线24 企业要制定一台重要设备更新的五年计划目标是使总费用最小解：
29、用点 vi 表示年初。 （i=1,2,6） ， v6 表示第五年底。弧 aij=（vi，vj）表示第 i 年初购置设备使用到第 j 年初的过程。对应的权期间发生的购置费用和维修费用之和。原问题转变为从 v1 到 v6 的一条最短路。得到两条最短路（v1,v3,v6） （v1,v4,v6）表示在第一、三年或第一、四年各购置一台设备，总费用都为 53 万元。25 已知一个地区的交通网络如下，医院。 。 。平均路程最短解：这是一个选择地址问题，实际要求出图的中心，可化成一系列求最短路问题。先求出v1 到其他各点的最短路长 dj ，令 d（v1）=max （d1,d2d7） ，表示若医院建在 v1，则
30、离医院最远的小区距离为 d（v1）依次计算 v2，v3.v7 到其余各点的最短路，类似求出d（v2） d（v3 ）. d（v7 ） ，d（vi ）中（I=1，27）中最小者。求出各个小区到区中心医院的平均路程的最小者？由于 d（v6）= 48 最小， ，此时离医院最远小区距离为 48，比医院建在其他小区时距离都短。同时将区医院建在v6，平均路程为 23.71，比医院建在其他小区时距离都短，所以医院应建在v6 。26 网络中最大流解：（1）增流路：v 0v3v1v2vn 增流值=2 （2）增流路：v0v2vn 增流值=4 f = 6（3）增流路：v0v1v2v4vn 增流值=4 （4）增流路：v0v3vn 增流值=3 f =13（5）增流路：v0v1v5v4vn 增流值=3 （6）增流路：v0v1v3v4vn 增流值=2 f =18
