Solving a Linear Programming Problem which Requires Integer Solutions

In summary, the conversation discusses a linear programming problem involving the quantities of plants. The objective is to maximize the value of the plants while considering constraints such as plant order requirements and garden capacity. The solution can be found using a graphical method, but for integer values, an integer programming problem must be used. The optimal solution is found to be 3 A plants and 10 S plants, with a value of $5000.
  • #1
bagasme
79
9
TL;DR 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
 
Physics news on Phys.org
  • #2
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.
 
  • Like
Likes nuuskur and FactChecker
  • #3
fresh_42 said:
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.
 
  • Like
Likes fresh_42
  • #4
bagasme said:
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:
  • Like
Likes bagasme and FactChecker
  • #5
pasmith said:
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:
  • #6
FactChecker said:
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).
 
  • #7
bagasme said:
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.
 
  • #8
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.
 
  • Like
Likes bagasme
  • #9
FactChecker said:
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.
 
  • Like
Likes FactChecker
  • #10
Yes, you need to be careful. The rounding concept is basic for these problems, but you still need to be careful.
 
  • #11
FactChecker said:
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?
 
  • #12
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.
 
  • #13
bagasme said:
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.
 
  • Like
Likes bagasme
  • #14
FactChecker said:
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?
 
  • #15
bagasme said:
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.
 
  • #16
bagasme said:
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.
 
  • #17
So can we close this thread (Q.E.D)?
 
  • #18
fresh_42 said:
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.
 

1. What is a linear programming problem?

A linear programming problem is a mathematical optimization technique used to find the best possible solution for a given set of constraints and objective function. It involves maximizing or minimizing a linear objective function, subject to a set of linear constraints.

2. What is the difference between integer and non-integer solutions in linear programming?

Integer solutions are those that require the decision variables to be whole numbers, while non-integer solutions allow for fractional values. Integer solutions are often used in practical applications, as they represent realistic and feasible solutions.

3. How do you know if a linear programming problem requires integer solutions?

A linear programming problem requires integer solutions if the decision variables represent discrete quantities, such as the number of units to produce, or if the problem can only be solved using whole numbers. Additionally, if the problem involves a real-life scenario where fractional values do not make sense, integer solutions may be required.

4. What are some common techniques for solving a linear programming problem with integer solutions?

Some common techniques for solving a linear programming problem with integer solutions include the branch and bound method, the cutting plane method, and the integer programming method. These methods use a combination of mathematical algorithms and heuristics to find the optimal solution.

5. Can a linear programming problem with integer solutions have multiple optimal solutions?

Yes, a linear programming problem with integer solutions can have multiple optimal solutions. This occurs when there are multiple combinations of integer values that satisfy the constraints and result in the same optimal objective function value. In such cases, any of the optimal solutions can be considered valid.

Similar threads

  • Linear and Abstract Algebra
Replies
7
Views
2K
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
648
  • Precalculus Mathematics Homework Help
Replies
5
Views
747
  • Linear and Abstract Algebra
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Differential Equations
Replies
5
Views
591
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
Back
Top