How to Solve a Linear Programming Problem in $n$ Dimension Space?

Question

Problem

\begin{array}{ll} \text{maximize} & c^T x \\ \text{subject to}& d^T x = \alpha \\ &0 \le x \le 1. \end{array}

The variable is $x\in\Bbb{R}^n$, $\alpha$ and the components of $d$ are positive.

What I Have Done

I do not have many tools available to solve this problem since I have just taken the Linear Programming course for a week and only a bunch of concepts have been introduced.

The only two things I think I could use are:

1. Geometry. Visualize the constraints as a hyperplane and a $n$ dimensional cube and do something...

2. Algebra. I tried to solve this problem with certain "magic" inequalities. From the form of object function I thought of rearrangement inequality, but I do not know how to merge the constraints into this inequality.

P.S. Maybe I miss something and complicate the problem without realizing this since I think this should be a conceptually simple question.

Could anyone help me and give me some hints, thank you in advance.

Answer 1

Hints to solve this / find a algorithm to solve it:

Let $S = \{x | d^Tx = a , x_i \in [0,1]\}$

• if $a,b \in S$ then $(at + (1-t)b)\in S \forall t\in[0,1]$,
• $ diff(x,y) =c^Ty - c^Tx = c^T(y-x)$