Fdtxjr

How can I protect witches in combat who wear limited clothing?

ELI5: Why do they say that Israel would have been the fourth country to land a spacecraft on the Moon and why do they call it low cost?

What aspect of planet Earth must be changed to prevent the industrial revolution?

Am I ethically obligated to go into work on an off day if the reason is sudden?

Would an alien lifeform be able to achieve space travel if lacking in vision?

Is every episode of "Where are my Pants?" identical?

In horse breeding, what is the female equivalent of putting a horse out "to stud"?

What can I do if neighbor is blocking my solar panels intentionally?

Can undead you have reanimated wait inside a portable hole?

University's motivation for having tenure-track positions

Did God make two great lights or did He make the great light two?

Why can't devices on different VLANs, but on the same subnet, communicate?

How should I replace vector<uint8_t>::const_iterator in an API?

He got a vote 80% that of Emmanuel Macron’s

Would it be possible to rearrange a dragon's flight muscle to somewhat circumvent the square-cube law?

Is this wall load bearing? Blueprints and photos attached

What do you call a plan that's an alternative plan in case your initial plan fails?

Did the UK government pay "millions and millions of dollars" to try to snag Julian Assange?

What are these Gizmos at Izaña Atmospheric Research Center in Spain?

Wall plug outlet change

I could not break this equation. Please help me

What's the point in a preamp?

Create an outline of font

Why did all the guest students take carriages to the Yule Ball?

Dual simplex method when initial reduced costs are negative

0

$begingroup$

I have the following problem which I'm trying to solve by dual simplex method:

$$min -6x_1-14x_2-13x_3$$
s.t $$0.5x_1+2x_2+x_3 le 24$$
$$x_1+2x_2+4x_3 le 60$$
$$x_1+x_2 ge 40$$
$$x_1, x_2, x_3 ge 0$$

I change the constraints into equality as:
$$0.5x_1+2x_2+x_3+s_1 = 24$$
$$x_1+2x_2+4x_3+s_2 = 60$$
$$-x_1-x_2+s_3=-40$$
The problem is that in the initial tableau the reduced costs are $-6, -14, -13, 0, 0, 0$ which violate the non-negativity clause for the reduced costs in dual simplex method.

Similarly there could be another type of problem with atleast 1 initial reduced cost as negative, such as:

$$min x_1-8x_2$$
s.t $$x_1+x_2 ge 1$$
$$-x_1+6x_2 le 3$$
$$x_1 le 2$$
$$x_1, x_2, x_3 ge 0$$

Again, I change the constraints into equality as:
$$-x_1-x_2+s_1 = -1$$
$$-x_1+6x_2+s_2 = 3$$
$$x_1+s_3= 2$$
Here my initial reduced cost is $(1, -8, 0, 0)$.
If I try solving the above two questions without taking the negativity of reduced costs into consideration, I stop at some intermediate solution when my $ B^-1 b$ becomes $ge 0$ which is not optimal solution and my reduced vector is still not $ge 0$.
How should I then proceed with such problem if my reduced costs are negative?

linear-programming simplex

share|cite|improve this question

edited Mar 25 at 6:53

Prachi

asked Mar 25 at 6:30

PrachiPrachi

12

$endgroup$

add a comment | 

0

$begingroup$

I have the following problem which I'm trying to solve by dual simplex method:

$$min -6x_1-14x_2-13x_3$$
s.t $$0.5x_1+2x_2+x_3 le 24$$
$$x_1+2x_2+4x_3 le 60$$
$$x_1+x_2 ge 40$$
$$x_1, x_2, x_3 ge 0$$

I change the constraints into equality as:
$$0.5x_1+2x_2+x_3+s_1 = 24$$
$$x_1+2x_2+4x_3+s_2 = 60$$
$$-x_1-x_2+s_3=-40$$
The problem is that in the initial tableau the reduced costs are $-6, -14, -13, 0, 0, 0$ which violate the non-negativity clause for the reduced costs in dual simplex method.

Similarly there could be another type of problem with atleast 1 initial reduced cost as negative, such as:

$$min x_1-8x_2$$
s.t $$x_1+x_2 ge 1$$
$$-x_1+6x_2 le 3$$
$$x_1 le 2$$
$$x_1, x_2, x_3 ge 0$$

Again, I change the constraints into equality as:
$$-x_1-x_2+s_1 = -1$$
$$-x_1+6x_2+s_2 = 3$$
$$x_1+s_3= 2$$
Here my initial reduced cost is $(1, -8, 0, 0)$.
If I try solving the above two questions without taking the negativity of reduced costs into consideration, I stop at some intermediate solution when my $ B^-1 b$ becomes $ge 0$ which is not optimal solution and my reduced vector is still not $ge 0$.
How should I then proceed with such problem if my reduced costs are negative?

linear-programming simplex

share|cite|improve this question

edited Mar 25 at 6:53

Prachi

asked Mar 25 at 6:30

PrachiPrachi

12

$endgroup$

add a comment | 

$begingroup$

I have the following problem which I'm trying to solve by dual simplex method:

$$min -6x_1-14x_2-13x_3$$
s.t $$0.5x_1+2x_2+x_3 le 24$$
$$x_1+2x_2+4x_3 le 60$$
$$x_1+x_2 ge 40$$
$$x_1, x_2, x_3 ge 0$$

I change the constraints into equality as:
$$0.5x_1+2x_2+x_3+s_1 = 24$$
$$x_1+2x_2+4x_3+s_2 = 60$$
$$-x_1-x_2+s_3=-40$$
The problem is that in the initial tableau the reduced costs are $-6, -14, -13, 0, 0, 0$ which violate the non-negativity clause for the reduced costs in dual simplex method.

Similarly there could be another type of problem with atleast 1 initial reduced cost as negative, such as:

$$min x_1-8x_2$$
s.t $$x_1+x_2 ge 1$$
$$-x_1+6x_2 le 3$$
$$x_1 le 2$$
$$x_1, x_2, x_3 ge 0$$

Again, I change the constraints into equality as:
$$-x_1-x_2+s_1 = -1$$
$$-x_1+6x_2+s_2 = 3$$
$$x_1+s_3= 2$$
Here my initial reduced cost is $(1, -8, 0, 0)$.
If I try solving the above two questions without taking the negativity of reduced costs into consideration, I stop at some intermediate solution when my $ B^-1 b$ becomes $ge 0$ which is not optimal solution and my reduced vector is still not $ge 0$.
How should I then proceed with such problem if my reduced costs are negative?

linear-programming simplex

share|cite|improve this question

edited Mar 25 at 6:53

Prachi

asked Mar 25 at 6:30

PrachiPrachi

12

$endgroup$

share|cite|improve this question

edited Mar 25 at 6:53

Prachi

asked Mar 25 at 6:30

PrachiPrachi

12

share|cite|improve this question

edited Mar 25 at 6:53

Prachi

asked Mar 25 at 6:30

PrachiPrachi

12

asked Mar 25 at 6:30

PrachiPrachi

12

asked Mar 25 at 6:30

PrachiPrachi

12