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

## 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.

• Hint: what happens if $n=1$? And if $n=2$? – Kuifje Jan 15 '18 at 13:59
• @Kuifje I have thought about the $n=1,2$ and 3 cases before posting this question. Suppose the feasible set is not empty, then when $n=1$ only a specific point could be taken, when $n=2$ and 3, one of $x_i$ could take 1 and others could not. It seems that I could then pick points in the feasible set such that the object function could be maximized. However, I do not think I could generalize this thinking into $n$ dimensional space with only "observations" and I do not have a formal way to formulate my thoughts. So could you provide more details? – Mr.Robot Jan 15 '18 at 18:58
• An intuitive solution to this problem can be found at: math.stackexchange.com/questions/2607020/… – Adam Jan 16 '18 at 1:12
• The feasible region is a polyhedron. It is a well-known fact that linear objective functions on polyhedra obtain their maximum in (at least) a vertex of the polyhedron. The vertices of your feasible region are points with only corrdinates zero or one, except one coordinate which must be determines via the plane equation $d^\top x=\alpha$. – M. Winter Jan 16 '18 at 9:32
• I have tried to improve the readability of your question by introducing $\rm \LaTeX$, because pictures may not be legible, cannot be searched and are not view-able to some, such as those who use screen readers. It is possible that I unintentionally changed the meaning of your question. Please proofread the question to ensure this has not happened. – GNUSupporter 8964民主女神 地下教會 Jan 16 '18 at 12:02

## 1 Answer

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)$