B Solving a Linear Programming Problem which Requires Integer Solutions

30
4
Summary
Solving a linear programming related to quantities of plants
Hello,

In grade 11 of high school, I encountered this linear programming problem on my textbook:
Every six months, a decorative plants seller order Aglanonemas (A) and Sansevierias (S) to an agent, which respectively give profit of $500 and $350. The agent requires that plant A must be ordered by minimum of 20% from total plant orders. However, the seller have garden which is only sufficient for 10 As and 15 Ss. Assumed that all plants are sold out and the profit is maximized. How many As and Ss should be ordered?

The "alternative solution" described in the textbook as follows:

Let:
- ##x## : amount of plant A
- ##y## : amount of plant S
- ##L## : garden area
- ##L_x## : area of garden for one plant A
- ##L_y## : area of garden for one plant B

Since the plant order requirement is 20% of total orders are for plant A, we write: $$x \geq \frac 1 5 \left( x + y \right) \text{or } 4x - y \geq 0$$
However, the garden capacity is only for 10 A plants and 15 S plants, that is $$ x \cdot (\frac 1 {10} L) + y \cdot (\frac 1 {15} L \leq L) \text{ or } 3x + 2y \leq 30$$
The objective function is ##Z = 5x + 3.5y## (in the order of $100).

The complete linear problem equations are:
\begin{cases}
4x - y \geq 0 \\
3x + 2y \leq 30 \\
x \geq 0 \\
y \geq 0 \\
Z = 5x + 3.5y \text{ } \text{(maximize)}
\end{cases}

Solving the problem (using graphical method), the solutions are: ##B(2\frac 8 {11}, 10\frac {10} {11})## with ##Z = 51.818182 \text{ or } Z = $5181.8182##. However, the correct solution requires positive integers, because the solution is about amount of goods (plants), which can't be fractional. How can I solve this problem, and would it become integer programming problem? The correct solution is 3 A plants and 10 S plants, with $5000 optimum value.

Cheers, Bagas
 

fresh_42

Mentor
Insights Author
2018 Award
11,143
7,655
The integer values define a lattice and we can apply algorithms which operate only on this lattice. This isn't an easy subject.

In a case as above where the target function behaves smooth and locally monotone (increasing or decreasing), i.e. there are no sudden jumps, singularities or other weird behaviour, we can solve the problem with continuous variables and simply test all values of the target function at the surrounding lattice points.
 

FactChecker

Science Advisor
Gold Member
2018 Award
4,997
1,755
we can solve the problem with continuous variables and simply test all values of the target function at the surrounding lattice points.
This is an integer programming problem. In this case, there is a lot of truncation of the continuous solution to get integers (##2\frac 8 {11} ## => 2 and ##10\frac {10} {11}## => 10). So, depending on the slopes of the constraints and the objective function, one might have to test integer value lattice points farther from the continuous solution.
 

pasmith

Homework Helper
1,733
408
Summary: Solving a linear programming related to quantities of plants

Hello,

In grade 11 of high school, I encountered this linear programming problem on my textbook:
Every six months, a decorative plants seller order Aglanonemas (A) and Sansevierias (S) to an agent, which respectively give profit of $500 and $350. The agent requires that plant A must be ordered by minimum of 20% from total plant orders. However, the seller have garden which is only sufficient for 10 As and 15 Ss. Assumed that all plants are sold out and the profit is maximized. How many As and Ss should be ordered?

The "alternative solution" described in the textbook as follows:

Let:
- ##x## : amount of plant A
- ##y## : amount of plant S
- ##L## : garden area
- ##L_x## : area of garden for one plant A
- ##L_y## : area of garden for one plant B

Since the plant order requirement is 20% of total orders are for plant A, we write: $$x \geq \frac 1 5 \left( x + y \right) \text{or } 4x - y \geq 0$$
However, the garden capacity is only for 10 A plants and 15 S plants, that is $$ x \cdot (\frac 1 {10} L) + y \cdot (\frac 1 {15} L \leq L) \text{ or } 3x + 2y \leq 30$$
The objective function is ##Z = 5x + 3.5y## (in the order of $100).

The complete linear problem equations are:
\begin{cases}
4x - y \geq 0 \\
3x + 2y \leq 30 \\
x \geq 0 \\
y \geq 0 \\
Z = 5x + 3.5y \text{ } \text{(maximize)}
\end{cases}

Solving the problem (using graphical method), the solutions are: ##B(2\frac 8 {11}, 10\frac {10} {11})## with ##Z = 51.818182 \text{ or } Z = $5181.8182##. However, the correct solution requires positive integers, because the solution is about amount of goods (plants), which can't be fractional. How can I solve this problem, and would it become integer programming problem? The correct solution is 3 A plants and 10 S plants, with $5000 optimum value.

Cheers, Bagas
(4,9) satisfies 4(4) - 9 = 7 > 0 and 3(4) + 2(9) = 30, and you've swapped a y for an x thus increasing Z by 1.5.

A bounded region of [itex]\mathbb{R}^n[/itex] contains only a finite number of points in [itex]\mathbb{Z}^n[/itex]. Thus in principle maximizing a function is a question of producing a list of those points and sorting it by the value of the function. This may not be the most efficient algorithm, but it will work.
 
Last edited:

FactChecker

Science Advisor
Gold Member
2018 Award
4,997
1,755
Thus in principle maximizing a function is a question of producing a list of those points and sorting it by the value of the function. This may not be the most efficient algorithm, but it will work.
I would not worry about a list and sorting. Just retain the best solution to date and you will be left with the best solution at the end. It works well on this sized problem and it teaches the point that integer programming is more complicated than it first appears. But this approach is quickly overwhelmed by surprisingly small problems. If the goal is to learn integer programming techniques, the "brute-force" approach misses the point.
 
Last edited:
30
4
This is an integer programming problem. In this case, there is a lot of truncation of the continuous solution to get integers (##2\frac 8 {11} ## => 2 and ##10\frac {10} {11}## => 10). So, depending on the slopes of the constraints and the objective function, one might have to test integer value lattice points farther from the continuous solution.
But the textbook said that the correct solutions are 3 and 10 (by rounding concept).
 

FactChecker

Science Advisor
Gold Member
2018 Award
4,997
1,755
But the textbook said that the correct solutions are 3 and 10 (by rounding concept).
As @pasmith pointed out, x=4, y=9 gives a better feasible solution. So the book answer is not the best. This is a good example of the difficulty with integer programming problems. If there are a few more variables (and in real applications, there are sometimes hundreds), it gets very difficult to find the optimal solution. Integer programming is a large and fascinating subject. For now, you probably should just accept the book's approach and see what is next.
 

fresh_42

Mentor
Insights Author
2018 Award
11,143
7,655
A drawing always helps:
1563837481256.png


The blue dot is the continuous optimum, the black ones near are feasible lattice points.
And although ##(3,10)## is closer to the continuous optimum, which is always at a vertex, there is still room left to optimize ##Z## in the direction of the arrow, because ##(4,9)## is feasible, too.

If we add the restriction, that ##Z## has to be an integer value, too, then ##(3,10)## is the solution.
 
30
4
As @pasmith pointed out, x=4, y=9 gives a better feasible solution. So the book answer is not the best. This is a good example of the difficulty with integer programming problems. If there are a few more variables (and in real applications, there are sometimes hundreds), it gets very difficult to find the optimal solution. Integer programming is a large and fascinating subject. For now, you probably should just accept the book's approach and see what is next.
Yet the textbook just said that we need to be careful when solving integer programming problems. Also, according to the book, rounding concept is required for integer programming.
 

FactChecker

Science Advisor
Gold Member
2018 Award
4,997
1,755
Yes, you need to be careful. The rounding concept is basic for these problems, but you still need to be careful.
 
30
4
Yes, you need to be careful. The rounding concept is basic for these problems, but you still need to be careful.
So what are suggestions for solving integer programming problems, that is the solutions must be integers except objective function?
 

FactChecker

Science Advisor
Gold Member
2018 Award
4,997
1,755
It is a very tough subject. It might lead you far from what the book and class want you to worry about at this time. You can look at this and see if you want to study it now.

Many people, myself included, would use the clever computer programs that are available for solving them and not try to understand the details. I am not expert enough to help you further.
 

fresh_42

Mentor
Insights Author
2018 Award
11,143
7,655
So what are suggestions for solving integer programming problems, that is the solutions must be integers except objective function?
Roughly speaking: start at a feasible lattice point and determine in which direction the objective function optimizes. Go there and repeat. This way you get a path through the lattice which should yield the optimum.

Of course this can be more complicated for higher dimensions, feasible sets which are not connected or not convex, or nonlinear objective functions, especially if they are otherwise weird. It is an entire branch of mathematics (or computer science), which algorithm works best under which conditions. The above example is extremely easy: the feasible set is a convex simplex, the objective function linear, and it is two dimensional, so it can be drawn.
 
30
4
It is a very tough subject. It might lead you far from what the book and class want you to worry about at this time. You can look at this and see if you want to study it now.

Many people, myself included, would use the clever computer programs that are available for solving them and not try to understand the details. I am not expert enough to help you further.
Alright, so that integer programming is special case for linear programming, right?
 

FactChecker

Science Advisor
Gold Member
2018 Award
4,997
1,755
Alright, so that integer programming is special case for linear programming, right?
It's closely related. I am not sure if linear programming is the basis of practical integer programming algorithms.
 

fresh_42

Mentor
Insights Author
2018 Award
11,143
7,655
Alright, so that integer programming is special case for linear programming, right?
No. Integer means a discrete feasible set, linear refers to the objective function. In your case, the relevant algorithm is called simplex algorithm.
 
30
4
So can we close this thread (Q.E.D)?
 

FactChecker

Science Advisor
Gold Member
2018 Award
4,997
1,755
No. Integer means a discrete feasible set, linear refers to the objective function.
Linear programming requires that the objective function and the constraints be linear.
In your case, the relevant algorithm is called simplex algorithm.
The simplex algorithm is for linear programming, not directly for integer programming. It may be part of some integer linear programming algorithms, but it would need to be heavily modified.
 

Want to reply to this thread?

"Solving a Linear Programming Problem which Requires Integer Solutions" You must log in or register to reply here.

Related Threads for: Solving a Linear Programming Problem which Requires Integer Solutions

  • Posted
Replies
3
Views
1K
Replies
3
Views
14K
Replies
7
Views
4K
Replies
1
Views
3K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top