Basic Concepts and Principles

Given a linear programming problem as

Primary Problem

\( min\ C^tx \\ Subject\ to \\ Ax \leq b \\\\ x\geq 0 \\ A \in M_{mxn}, \ rank(A)=m \\ b\in \mathbb{R}^m, \ C \in \mathbb{R}^n, x \in \mathbb{R}^n \)

It is associated with another problem which we call Dual form

Dual Problem

\( max\ b^tw \\ Subject\ to \\ A^tw \geq C \\\\ w\geq 0 \\ A \in M_{mxn}, \ rank(A)=m \\ b\in \mathbb{R}^m, \ C \in \mathbb{R}^n, w \in \mathbb{R}^m \)

That is, what was the cost vector, now is constraints vector and vice versa. Constraints matrix is transposed in the dual. In some cases it is easier to solve one than another, or it is possible to give conditions for one that determine properties of solutions of the another one.

Extended Theory

More generally, if we have a Linear Programming problem as

\( max\ C^tx \\ Subject\ to \\ \sum_{j=1}^{n} a_{ij}x_j \leq b_i,\ i \in M_1\\ \sum_{j=1}^{n} a_{ij}x_j = b_i,\ i \in M-M_1\\ x_j\geq 0 , \ j\in N_1 \)

That is, we have only restricted in sign someone of the variables and only in some of the restrictions we have inequality. Then the dual problem becomes:

\( max\ b^tw \\ Subject\ to \\ \sum_{i=1}^{m} a_{ji}w_i \geq C_i,\ j \in N_1\\ \sum_{i=1}^{m} a_{ji}w_i = C_i,\ j \in N - N_1\\ w_i\geq 0 , \ i\in M_1 \)

ie, we have
1. An inequality constraint in the primal variable means restricted in sign variable in the dual.
2. Equality constraint in the primal, resulting in a variable unrestricted in sign in the dual.

Existence Theorem
a) If one of the two problems have finite optimal solution, the other also does.
b) If the primal problem has unbounded solution, then the dual has not feasible optimal solution (the converse is not true).

Corollary 1

Given a pair of dual problems, only one of these conditions is true:

1) Neither have feasible optimal solution.

2) One have solution feasible but is unbounded and the other has no solution.

3) They both have finite optimal solutions.

Corollary 2 (duality theorem)

Given a pair of dual problems, a necessary and sufficient condition for the primal optimal solution has finite x, is that there is a dual feasible solution w such that

\( Cx = bw \)

Was useful? want add anything?

快乐飞艇怎么玩:Post here

Post from other users


2014-11-05 18:08:36
hello,very thanks

快乐飞艇怎么玩:Post here
快乐飞艇开奖 快乐飞艇做任务靠谱吗 熊猫乐园快乐飞艇 华创投资快乐飞艇靠谱吗 快乐飞艇综合走势图 快乐飞艇app首页 快乐飞艇官网 快乐飞艇是不是官方的 快乐飞艇计划 快乐飞艇彩票 快乐飞艇34567玩法 快乐飞艇app下载