??13???A1??10?5??10?5?A2???85??85???? 得。同理，去除第一行，可得
??5?A3????5?，同理，可得最优对此时，第一列元素比第二列大，去掉第一列元素，得
策值为5。最优策略为(S3,N3)。
7．A,B两家公司各自控制市场的50%。最近这两家公司都改进了各自的产品，并准备发动新的广告宣传，以争取潜在顾客。若双方都不作广告，那么平分市场的局面不会改变，但若单方发动一次强大的广告宣传，则对方将按比例损失一定数量的顾客。市场调查表明，潜在顾客的50%可以通过电视广告争取到，30%通过报纸广告争取到，其余的20%可通过无线电广播广告的形式争取到。问A,B两家公司的最优广告策略各是什么？对策值为多少？
解：策略1为不做广告，策略2为只作电视广告，策略3为只做报纸广告，策略4为制作无线电广告，策略5为做电视和报纸广告，策略6为做电视和无线电广告，策略7为做报纸和无线电广告，策略8为做所有类型广告。 策略 A 1 2 3 4 5 6 7 8 1 1/2 3/4 13/20 3/5 9/10 17/20 3/4 1 2 1/4 1/2 2/5 1/10 13/20 3/5 1/2 3/4 3 7/20 3/5 1/2 9/20 3/4 7/10 3/5 17/20 4 2/5 13/20 11/20 1/2 4/5 3/4 13/20 9/10 B 5 1/10 7/20 1/4 1/5 1/2 9/20 7/20 3/5 6 3/20 2/5 3/10 1/4 11/20 1/2 2/5 13/20 7 1/4 1/2 2/5 7/20 13/20 3/5 1/2 3/4 8 0 1/4 3/20 1/10 2/5 7/20 1/4 1/2 (S1,N1)(S2,N2)(S3,N3)(S4,N4)(S5,N6)(S6,N6)(S7,N7)(S8,N8)。最优策略为：
对策值为：1/2。
8．某市有两家超市相互竞争，超市A有三种广告策略，超市B也有三种广告策略，据预测当双方采用不同的广告策略时，A方所占市场分额增加的百分数如表14-3所示：
表14-3 双方采用不同的广告策略市场分额的改变情况
策略 B 1 1 2 3 3 0 2 1 2 0 2 -3 2 0 4 A试将此对策问题表示为一线形规划模型，并求出最优策略。
?302???A??020??2?14???无鞍点，不能使用优超原理，需用线性规划解。 解：
?3x??2x??13?1??2x2??1x3??1st.??2x1??4x3??11??min(x1??x2??x3?)??x1?,x2?,x3??0 V
?3y??2y??13?1??2y2??1st.??2y1??y2??4y3??11??max(y1??y2??y3?)??y1?,y2?,y3??0V
解之，得V=16/15
??,2??9/1x63,? x1?1/4x1y/1?8?,y12?/?8,??y31/2,
5/16,x1?4/15,x2?3/5,x3?2/15,y1?2/15,y2?8/15,y3?1/3
所以，局中人1的最优混合策略为x?(4/15,3/5,2/15).
*y局中人2的最优混合策略为?(2/15,8/15,1/3).对策值为V=16/15。
*一、（15分）写出下列线性规划模型的对偶模型
minz???cijxiji?1j?1mn?n (i?1,2,?,m)minz?3x1?2x2?4x3?2x5??xij?ai ?1?jn?3x1?5x2?x4?2x5?6?st.??xij?bj (j?1,2,?,n),?x2?4x3?x5?8?i?1st.???xij?0 (j?1,2,?n;i?1,2,?,m)?2x1?3x2?7x3?x4?5x5?0??x1,x2?0,x4?0??
二、（20分）某企业生产甲、乙两种产品，其单位利润分别为2元和3元。每生产一件甲产品需劳动力3个，原材料2个单位。每生产一件乙产品需劳动力6个，原材料1个单位。企业现有劳动力24个，原材料10单位。试问：（1）该企业应如何安排生产才能获得最大利润？（2）若另一个企业想利用该企业的这两种资源（劳动力和原材料），该企业最低应以多少价格转让？
三、（15分）某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，已知产品的规格要求、产品的单价、每天能供应的原材料的数量及原材料单价如表1和表2所示。该厂应如何安排生产使利润最大？（建立模型不用求解）
表1 产品规格要求、单价表 表2 每天供应原料数及原材料单价表
原材料 名称 每天最 多供应量 单价 （元/千克） 产品名称甲乙丙规格要求单价（元/千克）原材料1不少于50P原材料2不超过25%原材料1不少于255原材料2不超过50%不限251 2 3 100 100 60 65 25 35
四、（30分）已知某求最大值的线性规划问题的最初和最优单纯形表如下
xBx3x4x5CB000x112301x222022x301000x400100x500010b1298
xBx1x4x2CB102x111000x220010x3012x400100x50?123212b234
?320?12?j
?j?12（1） 写出最优解和最优基的逆矩阵；（2）求对偶模型的最优解；（3）求c1的变化范围使最优基不变；（3）b1由12变为14时，求原模型最优解；（4）b1由12变为16时，
求原模型最优解。
五、（20分）求解下列模型
minz?5x11?9x12?3x13?x21?3x22?4x23 ?8x31?2x32?6x33x11?x21?x31?18?x11?x12?x13?15?x?x?x?18x12?x22?x32?12?212223st.?x13?x23?x33?16?x31?x32?x33?17?xij?0,i?1,2,3;j?1,2,3?
一、多项选择题(每小题3分，共15分)
1、线性规划模型有特点（ ）。
A、所有函数都是线性函数； B、目标求最大； C、有等式或不等式约束； D、变量非负。 2、下面命题正确的是（ ）。
A、线性规划的最优解是基本可行解；B、基本可行解一定是基本解；
C、线性规划一定有可行解； D、线性规划的最优值至多有一个。 3、一个线性规划问题（P）与它的对偶问题（D）有关系（ ）。 A、（P）有可行解则（D）有最优解；B、（P）、（D）均有可行解则都有最优解； C、（P）可行（D）无解，则（P）无有限最优解；D、（P）（D）互为对偶。 4、运输问题的基本可行解有特点（ ）。
A、有m＋n－1个基变量； B、有m+n个位势； C、产销平衡； D、不含闭回路。 5、关于动态规划问题的下列命题中（ ）是错误的。
A、动态规划分阶段顺序不同，则结果不同；B、状态对决策有影响； C、在求解最短路径问题时，标号法与逆序法求解的思路是相同的； D、动态规划的求解过程都可以用列表形式实现。 二、（25分）考虑下列线性规划：
Max Z(x) = -5x1 + 5x2 + 13x3 - x1 + x2 + 3x3 ≤ 20 12x1 + 4x2 + 10x3 ≤ 90 x1 , x2 , x3 ≥ 0 最优单纯形表为： XB X2 X5 -Z b' 20 10 -100 X1 -1 16 0 X2 1 0 0 X3 3 -2 2 X4 1 -4 5 X5 0 1 0 1、写出此线性规划的最优解、最优基 B 和它的逆 B-1 ； 2、求此线性规划的对偶问题的最优解；
3、试求 c2 在什么范围内，此线性规划的最优解不变； 4、若 b1 = 20 变为 45，最优解及最优值是什么？ 三、（20分）有网络图如下,弧旁的数字是容量。
v2 5 3 5v410vs6vt84 36 6v5v3图11-30 某产地和销地的交通网
1 求网络图中从Vs到Vt的最大流和最小割集；
2 若弧(V2,V4)的容量改变容量为?C24，试讨论对最大流的影响。
四、（20分）某公司决定投资60万元（以10万元为单位），以提高三种主要产品 A、B、C 的产量。现决定每种产品至少要投资10万元。各种产品投资不同资金后可获得的期望利润如下： 分配的 利 润 投资金额 10 20 30 40 产品 A 14.5 16.4 18.0 19.6 产品 B 16.2 18.4 19.9 24.1 产品 C 15.9 18.4 22.6 24.2
试确定如何安排对各种产品的投资数，可获得最大总期望利润？ 五、（20分）用图解法解下面的目标规划模型：
???minz?P1d1?P2d1?P3d3
?x1?x2?d1??d1??10????2x1?x2?d2?d2?26st.?????x1?2x2?d3?d3?6???x,x,d,d?12ii?0 ?i?1,2,3?
一、多项选择题（每一小题3分，共计15分）
1、线性规划模型有特点（ ）。
A、所有函数都是线性函数； B、目标求最大； C、有等式或不等式约束； D、变量非负。 2、下面命题正确的是（ ）。
A、线性规划的最优解是基本可行解；B、基本可行解一定是基本解；
C、线性规划一定有可行解； D、线性规划的最优值至多有一个。 3、一个线性规划问题（P）与它的对偶问题（D）有关系（ ）。 A、（P）有可行解则（D）有最优解；B、（P）、（D）均有可行解则都有最优解； C、（P）可行（D）无解，则（P）无有限最优解；D、（P）（D）互为对偶。 4、运输问题的基本可行解有特点（ ）。
A、有m＋n－1个基变量； B、有m+n个位势； C、产销平衡； D、不含闭回路。 5、关于动态规划问题的下列命题中（ ）是错误的。
A、动态规划分阶段顺序不同，则结果不同；B、状态对决策有影响； C、在求解最短路径问题时，标号法与逆序法求解的思路是相同的； D、动态规划的求解过程都可以用列表形式实现。
二、（30分）考虑下列线性规划：
maxz?x???5x1?5x2?13x3??x1?x2?3x3?20?st.?12x1?4x2?10x3?90?xi?0?i?1,2,3??
最优单纯形表如下表所示：