Primitive problem dual problem
Max z=cx min w=yb.
Standard maximum ≤b standard maximum yA≥c
x≥0 y≥0
Where max stands for maximum value, min stands for minimum value, and s.t. stands for "constraint condition is"; Z is the objective function of the original problem, and W is the objective function of the dual problem; X is the decision variable column vector (n× 1) of the original problem, and y is the decision variable row vector (1× m) of the dual problem; A is the coefficient matrix (m× n) of the original problem, b is the right constant sequence vector (m× 1) of the original problem, and c is the row vector of the objective function coefficient (1×n) of the original problem. There are a series of profound connections between the original problem and the dual problem, and the following theorems have been strictly proved by mathematics. If the original problem and dual problem have feasible solutions x0 and y0 respectively, and u0 and v0 are their relaxation variables respectively, then x0 and y0 are their optimal solutions if and only if v0x0=0 and u0y0=0 respectively. V0x0=0 and u0y0=0 are called complementary relaxation conditions.
Symmetric dual linear programming Linear programming with symmetric form has the following characteristics:
① All constraints are inequalities, i.e. ≤ inequality for maximization problem and ≥ inequality for minimization problem.
② All variables are non-negative.
The steps of listing symmetric dual linear programming are:
① Specify non-negative dual variables, and the number of variables is equal to the number of constraint equations of the original problem.
② Take the objective function coefficient of the original problem as the right-hand constant of the constraint inequality of the dual problem.
③ Take the right-hand constant of the constraint inequality of the original problem as the objective function coefficient of the dual problem.
④ transpose the coefficient matrix of the original problem into the coefficient matrix of the dual problem.
⑤ Take the inequality in the constraint conditions of the original problem as the inequality in the constraint conditions of the dual problem.
⑥ Maximize the objective function of the original problem to minimize the objective function of the dual problem.
Asymmetric dual linear programming Sometimes linear programming does not appear symmetrically, for example, the constraints are not all in the same direction, and the variables can be non-positive or without symbolic constraints.
Column write asymmetric dual linear programming can refer to the primal-dual table (see the table below) according to the following steps:
(1) specifies dual variables, and the number of variables is equal to the number of constraint inequalities in the original problem.
② Take the objective function coefficient of the original problem as the right-hand constant of the constraint inequality of the dual problem.
③ Take the right-hand constant of the constraint inequality of the original problem as the objective function coefficient of the dual problem.
④ transpose the coefficient matrix of the original problem into the coefficient matrix of the dual problem.
⑤ Determine the symbolic constraint of dual variables according to the constraint inequality of the original problem.
⑥ According to the sign constraint of the decision variables of the original problem, the sign direction of the constraint inequality of the dual problem is determined.
The optimal solution of the dual problem can be obtained directly from the final simplex table (optimal simplex operator) of the original problem. The test number of relaxation variables in the original problem corresponds to the solution of the dual problem (the sign is opposite). When the simplex method is used, every iteration can get the feasible solution x0 of the original problem and the supplementary solution y0 of the dual problem, cx0=y0b. If x0 is not the optimal solution of the original problem, y0 is not the feasible solution of the dual problem. In the last step, the optimal solution x* of the original problem and the complementary optimal solution y* of the dual problem are obtained by iteration, and CX * = y * b. Y* is the shadow price of the original problem.