一、1
页脚内容 1.
2.
3.用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。
83105120106max212121xxxxxxz
2.将下述线性规划问题化成标准形式。
（1）无约束4,03,2,12321422245243min4321432143214321xxxxxxxxxxxxxxxxxxxxz
解：令zz'，''4'44xxx 一、1
页脚内容
0,,,,,,232142222455243'max65''4'43216''4'43215''4'4321''4'4321''4'4321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxz
3.分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中的可行域的哪个顶点。
0,825943510max21212121xxxxxxxxz
解：①图解法：
②单纯形法：将原问题标准化：
0,,,825943510max432142132121xxxxxxxxxxxxz
Cj 10 5 0 0 对应图解法一、1
页脚内容 CB B b x1 x2 x3 x4 中的点
0 x3 9 3 4 1 0 3
O点 0 x4 8 [5] 2 0 1 8/5
j 0 10 5 0 0
0 x3 21/5 0 [14/5] 1 -3/5 3/2
C点 10 x1 8/5 1 2/5 0 1/5 4
j -16 0 1 0 -2
5 x2 3/2 0 1 5/14 -3/14
B点 10 x1 1 1 0 -1/7 2/7
j 35/2 0 0 -5/14 -25/14
最优解为（1,3/2,0,0），最优值Z=35/2。
单纯型法步骤：转化为标准线性规划问题；找到一个初始可行解，列出初始单纯型表；最优性检验，求cj-zj，若所有的值都小于0，则表中的解便是最优解，否则，找出最大的值的那一列，求出bi/aij，选取最小的相对应的xij，作为换入基进行初等行变换，重复此步骤。
4.写出下列线性规划问题的对偶问题。
（1）njmixnjbxmiaxtsxczijjmiijinjijminjijij,,1;,,10,,1,,1..min1111
无约束jiijjminimjjmiiiyxnjmicyytsybyaw,,,1;,,1..max11 一、1
页脚内容 （2）nnjxnnjxmmmibxammibxatsxczjjinjjijinjjijnjjj,,1,10,,2,1,1..max11111111无约束
mmiymmiynnjcyannjcyatsybwiijmiiijjmiiijmiii,,1,2,10,,1,2,1..min1111111无约束
5. 给出线性规划问题
4,10966283..42max321432214214321jxxxxxxxxxxxxtsxxxxzj
要求：（1）写出其对偶问题；（2）已知原问题最优解为TX0,4,2,2*，试根据对偶理论，直接求出对偶问题的最优解。
解：
（1）4,10114322..9668min314343214214321jyyyyyyyyyyyytsyyyywj
（2）因为0,,321xxx，第四个约束取等号，根据互补松弛定理得： 一、1
页脚内容 0143224434321421yyyyyyyyyy
求得对偶问题的最优解为：0,1,53,54*Y，最优值min w=16。
例已知原问题Max z =x1 +2x2 +3x3 +4x4x1 +2x2 +2x3 +3x4≤202x1 +x2 +3x3 +2x4´≤20x1、x2、x3、x4≥ 0和对偶问题Min w =20y1 +20y2y1 +2y2≥12y1 +y2≥22y1 +3y2≥33y1 +2y2≥4y1、y2≥ 0已知对偶问题的最优解y1 =1.2、y2 =0.2，最优值min w=28，求原问题的最优解及最优值。
可用如下方法求解：引入将原问题和对偶问题化为标准形式。Max z =x1 +2x2 +3x3 +4x4x1 +2x2 +2x3 +3x4 +x5 = 202x1 +x2 +3x3 +2x4 +x6 =20x1、x2、x3、x4 、x5 、x6 ≥ 0Min w =20y1 +20y2y1 +2y2 －y3 = 12y1 +y2 －y4 = 22y1 +3y2 －y5 = 33y1 +2y2 －y6 = 4y1、y2 、y3 、y4 、y5 、y6 ≥ 0和 一、1
页脚内容 （1）y1=1.2>0，而y1与x5中至少有一个为零，故x5=0。（2）同理，y2=0.2>0，所以x6=0。（3）对偶问题的第一个约束条件在取最优值时y1+2y2=1.2+2×0.2=1.6>1这就表示该约束条件的松弛变量：y3=1.6－1=0.6>0y3与x1中至少有一个为零，故x1=0。（4）同理，对于第2个约束条件在取得最优值时2y1+y2= 2×1.2+0.2=2.6>2y4=2.6－2=0.6>0y4与x2中至少有一个为零，故x2=0。
（5）同理，对于第3个约束条件在取得最优值时2y1+3y2= 2×1.2+ 3×0.2=3y5=3－3=0y5与x3中至少有一个为零，故x3>0或者x3=0 。（6）对于第4个约束条件的分析也可得到x4>0或者x4=0 。对于（5）和（6）的分析，对于确定原问题的最优解没有任何帮助。但从（1）到（4）的分析中得知，原问题取得最优解时：x5=0，x6=0，x1=0，x2=0代入原问题的约束方程组得：2x3+3x4= 203x3+2x4= 20解此方程组，可求得原问题的最优解为：x1=0，x2=0 ，x3=4 ，x4=4 ，x5=0，x6=0 弱对偶性的推论：
(1) 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界
(2) 如原问题有可行解且目标函数值无界(具有无界解)，则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解。
注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无一、1
页脚内容 可行解，反之亦然。
(3) 若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。
强对偶性(或称对偶定理)
若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。
互补松弛性
在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。
影子价格
资源的市场价格是其价值的客观体现，相对比较稳定，而它的影子价格则有赖于资
源的利用情况，是未知数。因企业生产任务、产品结构等情况发生变化，资源的影
子价格也随之改变。
影子价格是一种边际价格。
资源的影子价格实际上又是一种机会成本。随着资源的买进卖出，其影子价格也将
随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。
生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；又当资源
的影子价格不为零时，表明该种资源在生产中已耗费完毕。
影子价格反映单纯形表中各个检验数的经济意义。
一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及资源的最有效利用
对偶单纯型法：转化成标准的线性规划问题；确定换入基变量，bi小于0中的最小的那一排，再求（cj-zj）/aij，且aij<0,找出最小值，这对应的xi便是换入基，若所有的bi都大于0，则找到了最优解
7 下列表分别给出了各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。
注意要基可行解的个数一定是行列变量数减一
销地
产地 B1 B2 B3 B4 产量
A1 4 1 4 6
8
A2 1 2 5 0 8
A3 3 7 5 1 4
销量 6 5 6 3 20
解：
（1）确定初始方案
西北角法：
销地
产地 B1 B2 B3 B4 产量 一、1
页脚内容 A1 6 2 8
A2 3 5 8
A3 1 3 4
销量 6 5 6 3 20
最小元素法：
销地
产地 B1 B2 B3 B4 产量
A1 5 3 8
A2 5 3 8
A3 1 3 4
销量 6 5 6 3 20
沃格尔法：
销地
产地 B1 B2 B3 B4 产量 行罚数
1 2 3 4
A1 4 1 4 6 8 ○3 0 2 2 5 3
A2 1 2 5 0 8 1 1 ○5 6 2
A3 3 7 5 1 4 1 2 4 4 3 1
销量 6 5 6 3 20
列
罚
数 1 2 1 1 1
2 ○2 1 1
3 1 1
4 1 ○5
8.下表给出一个运输问题及它的一个解，试问：
（1）表中给出的解是否为最优解？请用位势法进行检验。
（2）若价值系数C24由1变为3，所给的解是否仍为最优解？若不是，请求出最优解。
（3）若所有价值系数均增加1，最优解是否改变？为什么？
（4）若所有价值系数均乘以2，最优解是否改变？为什么？
销地
产地 B1 B2 B3 B4 产量
A1 4 1 4 6 8 5 3
A2 1 2 6 1 10 8 2
A3 3 7 5 1 4 3 1
销量 8 5 6 3 22
解：（1）
销地
产地 B1 B2 B3 B4 产量 ui
A1 4 1 4 6 8 0 5 3
A2 1 2 6 1 10 1 8 2
A3 3 7 5 1 4 1