2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Hint: what happens if $n=1$? And if $n=2$? $\endgroup$ – Kuifje Jan 15 '18 at 13:59
  • $\begingroup$ @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? $\endgroup$ – Mr.Robot Jan 15 '18 at 18:58
  • 1
    $\begingroup$ An intuitive solution to this problem can be found at: math.stackexchange.com/questions/2607020/… $\endgroup$ – Adam Jan 16 '18 at 1:12
  • $\begingroup$ 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$. $\endgroup$ – M. Winter Jan 16 '18 at 9:32
  • 1
    $\begingroup$ 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. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Jan 16 '18 at 12:02
1
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.