# Linear Programming - Integer Solutions (A Level)

Watch
Announcements

Page 1 of 1

Go to first unread

Skip to page:

Is there an easy way to find the integer solution to a linear programming problem?

It's easy when you're dealing with relatively low numbers, but if the problem deals with hundreds, you can't clearly see all the integer points on a graph, and testing them all would take ages.

It's easy when you're dealing with relatively low numbers, but if the problem deals with hundreds, you can't clearly see all the integer points on a graph, and testing them all would take ages.

Last edited by Zuvio; 7 months ago

0

reply

Report

#2

(Original post by

Is there an easy way to find the integer solution to a linear equation?

It's easy when you're dealing with relatively low numbers, but if the problem deals with hundreds, you can't clearly see all the integer points on a graph, and testing them all would take ages.

**Zuvio**)Is there an easy way to find the integer solution to a linear equation?

It's easy when you're dealing with relatively low numbers, but if the problem deals with hundreds, you can't clearly see all the integer points on a graph, and testing them all would take ages.

0

reply

(Original post by

Can you upload a specific question?

**mqb2766**)Can you upload a specific question?

Subject to 9x + 5y < 4500

3x + y < 1200

8x + 7y < 5600

x, y > 0

(all < and > are or equal to, but. i can't type that symbol)

0

reply

Report

#4

(Original post by

Maximise P = x + y

Subject to 9x + 5y < 4500

3x + y < 1200

8x + 7y < 5600

x, y > 0

(all < and > are or equal to, but. i can't type that symbol)

**Zuvio**)Maximise P = x + y

Subject to 9x + 5y < 4500

3x + y < 1200

8x + 7y < 5600

x, y > 0

(all < and > are or equal to, but. i can't type that symbol)

0

reply

(Original post by

Unless I made a slip, that can be solved as normal, and the solution is integer; (x,y) = (0,800). So, no further work required.

**ghostwalker**)Unless I made a slip, that can be solved as normal, and the solution is integer; (x,y) = (0,800). So, no further work required.

e.g. you change the 3rd condition to 7x + 9 y < 5500

Last edited by Zuvio; 7 months ago

0

reply

Report

#6

(Original post by

Ok, so i honestly just wrote out a random problem and didn't try to solve it, but what would you do with a problem like this if the solution wasn't an integer point?

e.g. you change the 3rd condition to 7x + 9 y < 5500

**Zuvio**)Ok, so i honestly just wrote out a random problem and didn't try to solve it, but what would you do with a problem like this if the solution wasn't an integer point?

e.g. you change the 3rd condition to 7x + 9 y < 5500

Instead, let's try

Our solution now becomes (254.054, 437.838) to 3dec.pl. So, non-integer.

What do we do?

The shape of the feasible region is convex, and we can fall back on the integer part, i.e. to (254,437), as a first step.

Our objective will be maximised when x,y have one of the two forms

(x,437), where x >= 254, or (254,y) where y >= 437.

We're going to need to check both.

First part, (x,437)

We check each constraint to find what's the largest value x can be when y=437. You'd need to take the minimum of all those values and then the integer part.

Or you can simply solve the LP setting y=437, which would be far easier. And again take the integer part of the x value. To produce one possible solution.

Repeat with (254,y), in a similar fashion to get a second solution.

The greater of the two is your final solution.

Sorry, rather torturous to describe.

0

reply

Report

#7

Not a level, but I guess the difficulties could be when the active constraint was almost parallel to the contour of the cost function. The non integer solution could occur at one end vertex, but the integer solution could occur at the other end vertex or even along the active constraint. Will try and sketch later.

Edit ...

The grid represents the integer solutions. The feasible region by the red boundary and the cost function (contour) by the blue dashed line. We want to minimise the cost, so lower values (y intercept) are better. The optimal non integer solution is (1) as it is the first point where the cost contour and the feasible region intersect. But if we slide the cost function up slightly, the first integer solution is (2), which is "far" from (1). The integer optimal solution isn't necessarily where constraints intersect either (as it will be for the non integer solution) and could occur along a single constraint.

In general, integer programming is hard (np complete), though I don't know all relevant stuff for integer linear programming. When the active constraint(s) and the cost contour are "distinctly not parallel", you should get the integer/non-integer solutions being close. In answer to your original question, it's not necessarily easy, even with a small number of variables, if the problem is ill posed (small changes to the problem produce a large change in the solution).

Edit ...

The grid represents the integer solutions. The feasible region by the red boundary and the cost function (contour) by the blue dashed line. We want to minimise the cost, so lower values (y intercept) are better. The optimal non integer solution is (1) as it is the first point where the cost contour and the feasible region intersect. But if we slide the cost function up slightly, the first integer solution is (2), which is "far" from (1). The integer optimal solution isn't necessarily where constraints intersect either (as it will be for the non integer solution) and could occur along a single constraint.

In general, integer programming is hard (np complete), though I don't know all relevant stuff for integer linear programming. When the active constraint(s) and the cost contour are "distinctly not parallel", you should get the integer/non-integer solutions being close. In answer to your original question, it's not necessarily easy, even with a small number of variables, if the problem is ill posed (small changes to the problem produce a large change in the solution).

Last edited by mqb2766; 7 months ago

0

reply

X

Page 1 of 1

Go to first unread

Skip to page:

### Quick Reply

Back

to top

to top