线性规划之对偶问题

概念：

1.在线性规划模型中，若原问题中xi为自由变量，那么对偶问题中的第i个约束一定为（等式约束）。
2.对偶单纯形算法判断当前点是否为最优的准则为，单纯形表中（b列数字全部非负，检验数全部非正 ）。
3.关于线性规划原问题与其对偶问题的对应关系，正确的有：（原问题目标函数求极大值，对偶问题目标函数求极小值；原问题约束条件的数目等于对偶问题决策变量的数目；原问题决策变量的数目等于对偶问题约束条件的数目）。

简答题：

1.

解：
根据规则写出对应对偶问题方程:

$$min (z1)=4*y1+5*y2+6*y3$$

s.t.

$$y1+y2+y3>=1$$

$$y1-2*y2+2*y3<=2$$

$$y1+3*y2-3*y3=3$$

$$y1>=0,y2>=0,y3>=0$$

1、对偶问题O-xi的对偶问题O-yi定是原问题O-xi。

2、用单纯形法求解标准形式（求最小值）的线性规划问题O-xi时，与对应的变量都可以被选作换入变量。

3、若线性规划的原问题O-xi有无穷多个最优解时，其对偶问题O-yi也有无穷多个最优解。

4、极大化原问题O-xi的任一可行解的目标函数值，不大于其对偶问题O-yi任意可行解的目标函数值。

5、X°、Y°分别为原问题O-xi与对偶问题O-yi的可行解，且CX°=Y°b，则两者均为最优解。

6、原问题O-xi无界，对偶问题O-yi无可行解。

参考文章 部分引用来自

https://www.cnblogs.com/allegro-vivace/archive/2020/04/04/12630152.html