如何求解下述线性规划问题的无界方向？求分步求解方法

Hey there! Let's break down how to determine if a linear programming (LP) problem has an unbounded direction (also called an extreme ray) and how to find it if it exists. I'll walk through your specific problem step by step, since it's easy to get confused with the constraints and direction conditions.

First, let's write your problem in a more readable format:

Minimize ( z = 50x_1 + 100x_2 )
Subject to:

1. ( 7x_1 + 2x_2 \geq 28 ) (HIW constraint)
2. ( 2x_1 + 12x_2 \geq 24 ) (HIM constraint)
3. ( x_1, x_2 \geq 0 ) (non-negativity)

For a minimization LP, an unbounded direction is a non-zero vector ( \mathbf{d} = (d_1, d_2) ) that satisfies two key conditions:

• Feasibility preservation: For any feasible solution ( \mathbf{x} = (x_1, x_2) ), the point ( \mathbf{x} + t\mathbf{d} ) remains feasible for all ( t \geq 0 ).
• Unbounded objective: As ( t \to \infty ), the objective value ( z(\mathbf{x} + t\mathbf{d}) \to -\infty ) (since we're minimizing, this means we can make ( z ) as small as we want by moving along this direction).

Let's apply the first condition to each of your problem's constraints:

• HIW constraint: ( 7(x_1 + td_1) + 2(x_2 + td_2) \geq 28 )
  Since ( \mathbf{x} ) is feasible, ( 7x_1 + 2x_2 \geq 28 ). To keep the inequality true for all ( t \geq 0 ), the term involving ( t ) must be non-negative:
  ( 7d_1 + 2d_2 \geq 0 )
• HIM constraint: ( 2(x_1 + td_1) + 12(x_2 + td_2) \geq 24 )
  Similarly, since ( 2x_1 + 12x_2 \geq 24 ) for feasible ( \mathbf{x} ), we need:
  ( 2d_1 + 12d_2 \geq 0 )
• Non-negativity constraints: ( x_1 + td_1 \geq 0 ) and ( x_2 + td_2 \geq 0 ) for all ( t \geq 0 )
  Since ( x_1, x_2 \geq 0 ), if ( d_1 < 0 ), eventually ( x_1 + td_1 ) will become negative as ( t ) grows. Same for ( d_2 ). So we must have:
  ( d_1 \geq 0, d_2 \geq 0 )

For the objective to be unbounded below, substituting ( \mathbf{x} + t\mathbf{d} ) into ( z ) must give a value that decreases without bound as ( t ) increases:
( z(\mathbf{x} + t\mathbf{d}) = 50(x_1 + td_1) + 100(x_2 + td_2) = z(\mathbf{x}) + t(50d_1 + 100d_2) )
For this to tend to ( -\infty ) as ( t \to \infty ), the coefficient of ( t ) must be negative:
( 50d_1 + 100d_2 < 0 )

Now let's see if there's a non-zero ( (d_1, d_2) ) that satisfies all these conditions:

1. ( 7d_1 + 2d_2 \geq 0 )
2. ( 2d_1 + 12d_2 \geq 0 )
3. ( d_1 \geq 0, d_2 \geq 0 )
4. ( 50d_1 + 100d_2 < 0 )

Wait a minute—conditions 3 and 4 can't both be satisfied! If ( d_1 ) and ( d_2 ) are non-negative, ( 50d_1 + 100d_2 ) is automatically non-negative (it's a sum of non-negative terms multiplied by positive coefficients). There's no way this sum can be negative.

This means your LP problem does not have an unbounded direction. In fact, it has a finite optimal solution! If you visualize the feasible region (the area in the first quadrant above both lines ( 7x_1 + 2x_2 = 28 ) and ( 2x_1 + 12x_2 = 24 )), the objective function ( z = 50x_1 + 100x_2 ) has its minimum at the intersection of the two constraint lines. Solving those two equations gives ( x_1 = 18/5 = 3.6 ), ( x_2 = 7/5 = 1.4 ), with an optimal objective value of ( z = 320 ).

Just to cover the general case, suppose we had a minimization problem where the objective coefficient condition was possible. For example, if the objective was ( z = -50x_1 + 100x_2 ), then ( -50d_1 + 100d_2 < 0 ) could be satisfied with ( d_1 > 2d_2 ), ( d_1 \geq 0 ), ( d_2 \geq 0 ). We could pick ( \mathbf{d} = (3, 1) ):

• ( 73 + 21 = 23 \geq 0 )
• ( 23 +121 = 18 \geq0 )
• ( d_1=3≥0, d_2=1≥0 )
• ( -503 +1001 = -50 <0 )

This would be a valid unbounded direction, as moving along it keeps solutions feasible and makes the objective value decrease indefinitely.

内容的提问来源于stack exchange，提问作者John Kelly