minW?5y1?2y2?y1?2y2?5?2y?y?12 ?12??y1?3y2?4??y1?0,y2无符号限制292（2）Y*=（，-）
55292（3），-
55?2?5（4）??1??5
1???5? 2??5?（5）变小
1．下面给出某线形规划的单纯形初表（表1）与某一中间表（表2）（Min型）：
表1 0 1 -3 0 2 0 CB XB B-1b x1 x2 x3 x4 x5 x6 0 x1 7 0 x4 12 0 x6 10 1 3 -1 0 2 0 0 -2 4 1 0 0 0 -4 3 0 8 1 ?j
x2 x6 表2 2/5 0 1/10 4/5 1/5 1 3/10 2/5 1 0 -1/2 10 ?j 1) 初表的出基变量为__________，进基变量为_________。
2) 填完表2，该表是否是终表?_________。若是，最优值Z?________ 3) 此线形规划对偶问题的最优解Y?_______
**
(1998)
解：1.下面给出某线形规划的单纯形初表（表1）与某一中间表（表2）（Min型）：
表1 0 1 -3 0 2 0 -1CB XB Bb x1 x2 x3 x4 x5 x6 0 x1 7 0 x4 12 0 x6 10 1 3 -1 0 2 0 0 -2 4 1 0 0 0 -4 3 0 8 1 0 1 -3 0 2 0 表2 2/5 1 0 1/10 4/5 0 1/5 0 1 3/10 2/5 0 ?j ?
1 x2 4 -3 x3 5 0 x6 11 1 0 0 -1/2 10 1 1/5 0 0 4/5 12/5 0 ?j
4) 初表的出基变量为_____x4_____，进基变量为___x3______。
5) 填完表2，该表是否是终表?____是_____。若是，最优值Z?__-11______
*?14?此线形规划对偶问题的最优解Y*???,?,0?
?55? 解： 解： 解： 解：
解： 解：
（二）线性规划建模 二（20分）、某化学制药厂有m种有害副产品，它们的数量为bi（i=1，?，m）。按照规定，必须经过处理，制成n种无害物后才能废弃。设aij为每制成一单位第j（j=1，?，n）种无害物可以处理掉第i种有害物的数量，cj为制成一单位第j种无害物的费用。
1． 现欲求各无害物的产量xj以使总的处理费用为最小，请写出此问题的线性规划模型； 2． 写出此问题的对偶规划模型，并解释对偶规划模型的经济意义。（2007） 解：1．
minz??cjxjj?1n?a11x1?a12x2???a1nxn?b1?ax?ax???ax?b2112222nn2 ??s..t????ax?ax???ax?bmnnm?m11m22??x1,x2,?，xn?02．
maxz??yibii?1m?a11y1?a21y2???am1ym?c1?ay?ay???ay?c121222m2m2 ??s..t????ay?ay???ay?cmnmn?1n12n2??y1,y2,?，ym?0经济意义：yi为第i种有害副产品不经处理直接废弃的费用。
二（10%）、某大型企业每年需要进行多种类型的员工培训。假设共有需要培训的需求（如技术类、管理类）为6种，每种需求的最低培训人数为ai，i=1,?,6, 可供选择的培训方式（如内部自行培训、外部与高校合作培训）有5种，每种的最高培训人数为bj, j=1,?,5。又设若选择了第1种培训方式，则第3种培训方式也要选择。记xij为第i种需求由第j方式培训的人员数量，z为培训总费用。费用的构成包括固定费用和可变费用，第j种方式的固定费用为hj（与人数无关），
与人数xij相应的可变费用为cij（表示第j方式培训第i种需求类型的单位费用）。如果以成本费用为优化目标，请建立该培训问题的结构优化模型（不解）。（2006）
解：二、
?1设xij为第i种需求由第j种方式培训的人员数量，yj???0minz??yjhj???cijxij
j?1i?1j?1565选择j培训方式否则
6??x?bjyj(i?1,2,?,5)?i?1ij?5??xij?ai(i?1,2,?,6)?j?1? ?y1?y3?0?x?0(i?1,?6,j?1,2,?,5)?ij?yj?0或1(j?1,2,?,5)???1.某厂使用A、B两种原料生产甲、乙、丙三种产品，有关数据见下表： 甲 乙 丙 A B 生产成本（万元/吨） 销售价格（万元/吨） 1.0 0.5 0.4 0.6 0.6 0.5 8 5 18 30 20 35 原料成本（万元/吨） 5 7 原料可用数量（吨） 350 460 （1）请写出使总销售利润最大的线性规划模型（其中甲、乙、丙产产量分别记为x1,x2,x3,约束依A,B原料次序）:
(2)写出此问题的对偶规划模型（2003）
解：⒈①maxz=30x1+20x2+35x3-8x1-5x2-18x3-5(x1+0.4x2+0.6x3)-7(0.5x1+0.6x2+0.5x3) 目标函数maxz=13.5x1+8.8x2+10.5x3 约束条件 x1+0.4x2+0.6x3≤350 0.5x1+0.6x2+0.5x3≤460 x1≥0,x2≥0,x3≥0
②对偶规划模型
目标函数 minw=350y1+460y2 约束条件y1+0.5y2≥13.5 0.4y1+0.6y2≥8.8 0.6y1+0.5y2≥10.5 y1≥0,y2≥0 三、（10%）某服装厂制造大、中、小三种尺寸的防寒服，所用资源有尼龙绸、尼龙棉、劳动力和缝纫设备。缝制一件防寒服所需各种资源的数量如表（单位已适当给定）。不考虑固定
费用，则每种防寒服售出一件所得利润分别为10、12、13元，可用资源分别为：尼龙绸1500米，尼龙棉1000米，劳动力4000，设备3000小时。此外，每种防寒服不管缝制多少件，只要做都要支付一定的固定费用：小号为100元，中号为150元，大号为200元。现欲制定一生产计划使获得的利润为最大，请写出其数学模型（不解）。(2002) 型号 资源 尼龙绸 尼龙棉 劳动力 缝纫设备 小 1．6 1．3 4 2．8 中 1．8 1．5 4．5 3．8 大 1．9 1．6 5 4．2
解：三、解：设三种防寒服分别生产x1,x2,x3件。z表示获得的利润,y1,y2,y3分别表示0-1变量，yi=1表示做第xi种防寒服（i=1,2,3）
maxz?10x1?12x2?13x3?100y1?150y2?200y3
?1.6x1?1.8x2?1.9x3?1500??1.3x1?1.5x2?1.6x3?1000?4x1?4.5x2?5x3?4000??2.8x1?3.8x2?4.2x3?3000?s.t.?x1?10000y1 ?x?10000y2?2?x3?10000y3??x1,x2,x3?0??y1,y2,y3?0或1
（三）互补松弛应用
maxz?2x1?3x2??1???1二（8%）、线性规划问题???1???????12x?2x2?12x?2x2?8?164x2?124x
x,x2?0已知其最优解x1，x2 ? 0，而第1，4两种资源（相应于第1，4两约束）均有余量，应用互
补松弛定理求出原问题和对偶问题的最优解。（2005）
解：二 对偶问题