运筹学作业2(清华版第二章部分习题)答案

运筹学作业2（第二章部分习题）答案2．1题（P.77）写出下列线性规划问题的对偶问题：（1）123123123123123max224..34223343500,zxxxstxxxxxxxxxxxx无约束，；解：根据原—对偶关系表，可得原问题的对偶规划问题为：123123123123123max235..223424334,0,0wyyystyyyyyyyyyyyy0（2）1111min,1,,,1,,0,1,,;1,,mnijijijnijijijnijijjjijzcxcxaimcxbjnximjn解：根据原—对偶关系表，可得原问题的对偶规划问题为：11max1,,;1,,mniijjijijijiwaubvuvcimjnuj无约束，v无约束2．2判断下列说法是否正确，为什么？（1）如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解；答：错。因为：若线性规划的原问题存在可行解，且其对偶问题有可行解，则原问题和可行问题都将有最优解。但，现实中肯定有一些问题是无最优解的，故本题说法不对。例如原问题1212212max31..30,0zxxxxstxxx有可行解，但其对偶问题1211212min33..10,0wyyystyyyy无可行解。（2）如果线性规划的对偶问题无可行解，则原问题也一定无可行解；答：错，如（1）中的例子。（3）在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或求极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值。答：错。正确说法是：在互为对偶的一对原问题与对偶问题中，求极大的问题可行解的目标函数值一定不超过求极小的问题可行解的目标函数值。（4）任何线性规划问题具有唯一的对偶问题。答：正确。2．5给出线性规划问题123123123123123max221..220,0,0zxxxxxxxxxstxxxxxx写出其对偶问题；（2）利用对偶问题性质证明原问题目标函数值1z解：（1）原问题的对偶问题为：123123123123123min22212..10,,0wyyyyyyyyystyyyyyy无约束（2）取011Ty，既1230,1,0yyy，经验证，011Ty是对偶问题的一个可行解，并且1w。由对偶问题的性质可得1zw2．9用对偶单纯形法求解下列线性规划问题：（2）123123123123min524324..63510,,0zxxxxxxstxxxxxx,解：先将原问题进行标准形化：1231234123512345max()524324..63510,,,,0zxxxxxxxstxxxxxxxxx选45,xx为基变量，并将问题化为：1231234123512345max()524324..63510,,,,0zxxxxxxxstxxxxxxxxx列表计算如下：jc-5-2-400bBCBX1x2x3x4x5x04x-3-1-210-405x-6[-3]-501-10jc-5-2-40004x[-1]0-1/31-1/3-2/3-22x215/30-1/310/3jc-10-2/30-2/3-51x101/3-11/32/3-22x0112-12jc00-1/3-1-1/3因所有检验数小于等于0且右边常数大于0，故此基可行解为最优解，即(2/3,2,0),22/2xz