0
$\begingroup$

I have an linear-fractional program definied like this: https://en.wikipedia.org/wiki/Linear-fractional_programming#Definition

In my case:

$\max\frac{4x_1+2x_2+5}{2x_1+x_2+2}$

with conditions:

$4x_1+3x_2\le8$

$x_1,x_2\ge0$

Using a Charnes-Cooper transformation

I have created linear program like this:

$\max{4y_1+2y_2+5}$

with conditions:

$4y_1+3y_2-8t\le0$

$2y_1+y_2+2t = 1$

$y_1,y_2,t\ge0$

Now I need to draw a set of possible solutions in 2 dimension $y_1,y_2$ chart. How to do it?

PS: sorry for my english... i'm not familiar with math terms in english.

$\endgroup$
  • $\begingroup$ Charnes-Cooper transformation of a linear program $\max\frac{c^Tx+\alpha}{d^Tx+\beta}$ s.t. $Ax \leq a$ usually gives two linear programms which can be written as (i) $\max c^Ty+\alpha t$ s.t. $Ay - at \leq 0$, $d^Ty + \beta t = 1$ and $t\geq 0$, and (ii) $\max c^Ty+\alpha t$ s.t. $-Ay + at \leq 0$, $d^Ty + \beta t = 1$ and $t\leq 0$. $\endgroup$ – Willem Hagemann Sep 11 '15 at 12:10
  • $\begingroup$ The set of feasible solutions is given as the union of the set of feasible solutions of (i) and (ii). Hence, the set of feasible solutions is the intersection of the double cone $\{ (y,t) \mid Ay -at \leq 0, t\geq 0\}\cup\{ (y,t) \mid -Ay+at \leq 0, t \leq 0\}$ with the half-space $d^Ty + \beta t = 1$. $\endgroup$ – Willem Hagemann Sep 11 '15 at 12:13
  • $\begingroup$ In your case, the double cone is inside $\mathbf{R}^3$, due to the additional paramter $t$. Now, the intersection of this double cone with the half-space mentioned earlier is a union of two convex sets in an affine subspace of dimension 2. $\endgroup$ – Willem Hagemann Sep 11 '15 at 12:17
  • $\begingroup$ After an appropriate base transformation you should be able to draw this intersection in dimension 2. $\endgroup$ – Willem Hagemann Sep 11 '15 at 12:21
  • $\begingroup$ But carefully, these are just my two cents, and does not answer the question how to obtain the y1,y2 chart. (There you would need a portion of projective geometry, I bet) $\endgroup$ – Willem Hagemann Sep 11 '15 at 12:32

Your Answer

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

Browse other questions tagged or ask your own question.