1.1线性规划标准型 maxZ=c1x1+c2x2+…+cnxn
s.t. a11x1+a12x2+…+a1nxn =b1 a21x1+a22x2+…+a2nxn =b2
am1x1+am2x2+….+amnxn =bm x1,x2….xn ? 0
用两个变量的差值代替无约束变量，左边加一个变量将＜变=，左边减一个变量将＞变=。目标函数左边乘-1将minZ变maxZ 1用对偶单纯形法解下列线性规划问题
min S = x1 + 4x2 + 3x4
s.t. x1+2x2 - x3 +x4 ? 3 -2x1 - x2+4x3 +x4 ? 2 x1，x2 ， x3， x4 ? 0
解：此题可用人工变量方法求，但也可用对偶单纯形法。
max S’ = -x1- 4x2 - 3x4
s.t. -x1 -2x2+ x3 -x4 +x5= -3 2x1 + x2-4x3 -x4+x6 = -2 x1，x2 ， x3， x4 ，x5 ，x6 ? 0 Cj CB 0 0 XB x5 x6 -1 x1 -1 2 -1 -4 x2 -2 1 -4 0 x3 1 4 0 -3 x4 -1 -1 -3 0 x5 1 0 0 0 x6 0 1 0 b -3 -2 0 σ 常数项是负数且最小，确定出基变量x5。
用出基变量x5行的所有负数分别去除对应的检验数，最小值对应的为进基变量x1，交叉元素为主元（-1） 主元运算：第一行乘（-1）【提示:表格同上，x5行对应数字乘-1，这里不抄】 主元运算：第二行加上 第一行乘（-2）【提示：是对应第二张表的，继续画出表3】 计算检验数 确定出基变量X6 确定进基变量X3，主元（-2）
Cj CB 0 0 XB x1 -1 x1 1 0 0 -4 x2 2 -3 -2 0 -3 x4 1 -3 -2 0 x5 -1 2 -1 0 x6 0 1 0 b 3 -8 -3 x3 1 x6 σ -2 -1 主元运算：第一行加 第二行乘（-1/2） 【根据上表继续画表5，σ行不填】 计算检验数：全为非正。但此时常数b已全大于零，最优解=（7，0，4，0） 最优值 S’ = - 7 S=7
Cj CB -1 0 XB x1 x3 -1 x1 1 0 0 -4 x2 7/2 3/2 -1/2 0 x3 0 1 0 -3 x4 1 -3 -1/2 0 x5 -2 -1 -2 0 x6 -1/2 -1/2 -1/2 b 7 4 -7 σ
2用对偶单纯形法解下列线性规划问题 min S = x1 + 2x2
s.t. -x1+2x2 - x3 ? 1 -x1 -2x2 + x3 ? 6 x1，x2 ， x3 ? 0 解：将原问题化成max S’ = -x1 - 2x2
s.t. x1 - 2x2 + x3 + x4 =-1 x1 + 2x2- x3+ x5 =-6 x1,x2,x3,x4,x5 ? 0 Cj -1 -2 0 0 CB 0 0 XB x1 1 1 -1 0 x5 0 1 0 b -1 -6 0 X4 X5 σ x2 -2 2 -2 x3 1 -1 0 x4 1 0 0 常数项最小出基变量X5，按比值无法比较。
常数项次小出基变量X4，按比值X2为进基变量。主元（-2） 主元运算：第一行乘（-1/2）【提示：表格同上X4行对应数字乘-1/2，画出表格2】 主元运算：第二行加 第一行乘（-2）【提示：是对表2而言的，画出表3】 常数项为负数的行元素全大于零，原问题无可行解。
3某地区在制定十年电力规划
设置决策变量 设备选方案1，2，3的装机台数分别为x1、x2、x3，它们的年发电量分别为x6、x7、x8亿度，备选方案1无前期土建工程要求，备选方案2和3都需要前期土建工程，这两个前期土建工程是否施工用变量x4、x5代表。则x1取值0-5之间的整数，x2、x3取值0-4之间的整数， x4、x5只能取0或1， x6、x7、x8大于零。 约束方程 满足装机容量需求约束：10x1+25x2+ 30x3 ? 180
满足规划年发电量需求约束：x6+x7 + x8 ? 100 各电站容量与发电量平衡方程：每台机组发电量等于单机容量乘全年小时数，再乘与负荷因子，换算亿度量纲，即：
方案1：x6=(0.66×8760×10/10000)×x1 方案2： x7=(0.4×8760×25/10000)×x2
得三个约束方程：5.782 x1-x6= 0 8.76 x2-x7= 0 18.39 x3-x8= 0
每个方案最多的装机台数约束： 方案1：不需前期土建工程； x1 ? 5 方案2：前期土建工程是装机的先决条件，且小于最大允许数； x2 ? 4 x4 方案3：前期土建工程是装机的先决条件，且小于最大允许数； x3 ? 4 x5
变量取值限制 x1、x2、x3 ? 0且整数 x6、x7、x8 ? 0 x4或x5=1前期土建工程要求 x4或x5=0 无前期土建工程要求
设计目标函数 目标函数：年成本费用最低。 成本包括两大部分：
可变成本：与发电量有关的成本，如：原材料，燃料，动力和活劳动消耗等。即参数表中年运行成本。不变成本：指与装机容量及前期土建投资有关的成本。 方案1：单机投资×回收因子=21×0.103=2.163(百万元） 方案2：单机投资×回收因子=70×0.0578=4.046(百万元） 方案3：单机投资×回收因子=65×0.103=6.695(百万元）
方案2和3的前期土建投资的年资本回收成本分别为504×0.0578=29.131(百万元） 240×0.103=24.72(百万元）
对方案1，2，3每发一亿度电的运行成本分别为4.11,2.28,3.65百万元。则数学模型如下： Min Z = 2.163x1+4.046x2+ 6.695x3 + 29.131x4+ 24.72x5 + 4.11x6 + 2.28x7 + 3.65x8 s.t. 10x1+25x2+ 30x3 ? 180 x6+x7 + x8 ? 100
4某石油公司四厂七售区
销售区 日最大售量 1 2 3 4 5 10 6 7 炼油厂
解：平衡问题，用最小元素法求初始方案。
计算检验数。 闭合回路。
最优方案如下，最小运费=元 有非基变量的检验数=0，有无穷多组解，另外一个解如
下：
1 2 25 3 15 4 40 25 20 10 25 15 10 日产量 35 5铁路列车编组站
M/M/1/?/?排队问题。其中? =2， ? =3，?=?/?=2/3<1系统中列车的平均数 Ls= ?/ (1-?)=(2/3)/(1-2/3)=2（列）
列车在系统中的平均停留时间 Ws=Ls/?= 2/2=1（小时）系统中等待编组的列车平均数 Lq=Ls-?= 2-2/3=4/3（列）列车在系统中的平均等待编组时间Wq = Lq/ ?=(4/3)/(1/2)
=2/3（小时）记列车平均延误（由于站内 2股道均被占用而不能进站）时间为W0 则W0 = WP{N>2}=W{1-P0-P1-P2}= W{1-(l-?)- (l-?) ?1 -(l-?) ?2}
=1*?3=?3=(2/3)3=0.296（小时）
故每天列车由于等待而支出的平均费用E=24?W0a=24*2*0.296*a=14.2a元
运筹学课件例题集锦
