Linear Programming - Integer Solutions (A Level)

Watch
Zuvio
Badges: 16
Rep:
?
#1
Report Thread starter 7 months ago
#1
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.
Last edited by Zuvio; 7 months ago
0
reply
mqb2766
Badges: 19
Rep:
?
#2
Report 7 months ago
#2
(Original post by 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.
Can you upload a specific question?
0
reply
Zuvio
Badges: 16
Rep:
?
#3
Report Thread starter 7 months ago
#3
(Original post by mqb2766)
Can you upload a specific question?
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
ghostwalker
  • Study Helper
Badges: 17
#4
Report 7 months ago
#4
(Original post by 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)
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.
0
reply
Zuvio
Badges: 16
Rep:
?
#5
Report Thread starter 7 months ago
#5
(Original post by 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.
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
Last edited by Zuvio; 7 months ago
0
reply
ghostwalker
  • Study Helper
Badges: 17
#6
Report 7 months ago
#6
(Original post by 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
That gives a solution of (265,405)

Instead, let's try 7x +8.5y\leq 5500

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
mqb2766
Badges: 19
Rep:
?
#7
Report 7 months ago
#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 ...
Name:  IMG_20201208_083634.jpg
Views: 9
Size:  63.7 KB
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

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

How would you feel if uni students needed to be double vaccinated to start in Autumn?

I'd feel reassured about my own health (20)
17.09%
I'd feel reassured my learning may be less disrupted by isolations/lockdowns (37)
31.62%
I'd feel less anxious about being around large groups (12)
10.26%
I don't mind if others are vaccinated or not (13)
11.11%
I'm concerned it may disadvantage some students (5)
4.27%
I think it's an unfair expectation (28)
23.93%
Something else (tell us in the thread) (2)
1.71%

Watched Threads

View All
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise