1. 解 原问题的对偶问题为

由于(0,1,0)是上述对偶问题的可行解，由弱对偶理论可知， z=CX≤Yb。

而，所以z的最大值不大于1。

2. 其对偶问题为

将y*1，y*2分别代入约束条件，得①式和②式为严格不等式，而式③和式④为等式。由互补松弛性YsX=0，可得x*1=x*2=0；其次因为y1,y2>0，由互不松弛性YXs=0，推得Xs1=Xs2=0，即原问题的两个约束应取等号，故有方程组

解得x*3=4，x*4=4，于是原问题的最优解为X*=(0,0,4,4)，最优值z*=4。

3. 考察最小元素法和位势法：

ui+vi=cij

σij=cij-(ui+uj)

利用最小元素法建立初始调运方案如下：

建立位势表如下，求各空格的检验数：

可见空格(1,2)的检验数小于0，所以方案需要调整。其闭回路为：

(1,2)→(1,3)→(2,3)→(2,2)→(1,2)

由闭回路得调整量为50，沿闭回路进行调整得新的调运方案如下：

建立位势表如下，求新方案的各空格的检验数。

4.

　由于r=3<阶数=4，调整0元素的分布得：

此时r=5=阶数，因此能找到最优指派方案。

5. ①把每装载一种产品看称一个阶段，k=1,2,3

②状态变量uk表示第k阶段初可用于装载产品的总容量。

③决策变量xk表示第k阶段装载第k种产品的件数。

④状态转移方程uk+1=uk-akxk，其中ak表示第k种货物的单件重量。

⑤指标函数vk(uk,xk)表示装载第k中产品xk件所得的利润

基本递推方程：

6. 设每个货栈作为一个阶段，共三个阶段，按逆序进行编号，丙i=1，乙i=2，甲i=3，分配车辆的优先顺序为：甲→乙→丙。决策变量xi表示分配给第i个货栈的车辆数，状态变量ui表示第i个阶段初尚未分配的车辆数，采用逆序计算时，其基本方程为：

其中，ci(ui,xi)表示第i个阶段初有ui个车辆，分配给货栈xi个车辆产生的收益。

第1个阶段：u1=0,1,2,3,4

f1(0)=60，f1(1)=71，f1(2)=82，f1(3)=94，f1(5)=94

第2阶段，u2=0,1,2,3,4

第3阶段：u3=4

得最优解：x*3=3，x*2=0，x*1=2，即甲货栈2个，乙货栈0个，丙货栈2个。

7. （1）取f(0)=0为初始可行流。

（2）构造有向赋权图ω(f(0))，如图a。

图a

求出从x到y的最短路(x,v2,v4,y)，如图a（双箭头即为最短路）。

（3）在原网络中与这条最短路相应的增广链为μ=(x,v2,v4,y)。

（4）在μ上进行调整，θ=3，得f(1)（如图b）。

图b

（5）构造有向赋权图ω(f(1))，如图c，并求出从x到y的最短路径(x,v1,v3,v4,y)，如图c（双箭头即为最短路）。

图c

（6）在原网络中与这条最短路相应的增广链为μ=(x,v1,x3,v4,y)。

（7）在μ上进行调整，θ=2，得f(2)（如图d）。

图d

（8）构造有向赋权图ω(f(1))，如图e，因为已经不存在从x到y的最短路，故f(2)为网络的最小费用最大流，其最大流为v(f*)=5，而最小费用为b(f*)=66。

图e