Linear programming problem

In summary, the problem is to define the decision variables and formulate the problem as a linear program. The decision variables include the amount of time the investor and worker spend gardening, rewiring the house, insulating the house, and the contractor spends checking ventilation. The objective is to maximize the total cost, while the constraints include the maximum amount of time for each task, the total time spent on gardening, and the ratio of insulation time to gardening time. Some costs are missing and there is a mistake in the constraint for insulation time. A careful check would have helped find the maximum, which can be found manually step by step. The last constraint should have 1/2 on the right-hand side, and there are more tasks for the investor
  • #1
Erenjaeger
141
6
I was given the problem attached in the photo below and the first question is to define the decision variables and formulate the problem as a linear program. There are no solutions online, so it would be helpful if someone on the mighty PF could check them to see if they are correct, thanks.
https://scontent.fhlz2-1.fna.fbcdn.net/v/t34.0-12/23113532_1505762442836859_1149946816_n.png?oh=f7a855d08561239a24b48af9741cbfbf&oe=59FAF30B
decision variables are..
let xig be the amount of time the investor spends gardening
let xwg be the amount of time the worker spends gardening
let xir be the amount of time the investor spends rewiring the house
let xii be the amount of time the investor spends insulating the house
let xcv be the amount of time the contractor spends checking ventilation
Max: 400xig + 400xwg +350xir +200xii + 300xcv - 100xig - 100xir - 60xwg - 150xcv
subject to:
xig + xir + xii ≤ 50
xig ≤ 10
xir ≥ 6
xii / (xig + xwg ) ≥ 2
Note: I'm not that sure about the last constraint, It is meant to be the one that says for 1 hour gardening there has to be at least 30 minutes insulating.
 
Physics news on Phys.org
  • #2
I interpret the last constraint in the same way as you, but it should be 1/2, not 2.
There are some costs missing and i can check the ventilation as well. The maximal hours for each task are missing as well. The i gardening constraint is wrong (although it won’t change the result here).

A more careful check of your statements would have helped.

The problem has a maximum that is easy to find manually step by step, that gives a nice cross check.
 
  • Like
Likes Erenjaeger
  • #3
mfb said:
I interpret the last constraint in the same way as you, but it should be 1/2, not 2.
There are some costs missing and i can check the ventilation as well. The maximal hours for each task are missing as well. The i gardening constraint is wrong (although it won’t change the result here).

A more careful check of your statements would have helped.

The problem has a maximum that is easy to find manually step by step, that gives a nice cross check.
if the last constraint had 1/2 on the RHS wouldn't the LHS read (xig + xwg) / xii instead, since you're given the information in the form of (xig + xwg) ≤ (1/5)xii?
And what do you mean about some costs missing?
Also how is the xig constraint wrong? I took that part of the problem to mean that he doesn't want to spend more than 20% of his total time (50 hours) improving the house, on gardening, 20% of 50 hours is 10 hours so doesn't that just mean he doesn't want to spend more than 10 hours gardening, hence xig ≤ 10 hours ?
 
  • #4
Erenjaeger said:
if the last constraint had 1/2 on the RHS wouldn't the LHS read (xig + xwg) / xii instead
No, that would be wrong again. Currently you require insulation to be at least twice the time spent on gardening, but the requirement is "at least half".
And what do you mean about some costs missing?
You only accounted for two tasks of the investor, but he can do all of them.
Also how is the xig constraint wrong? I took that part of the problem to mean that he doesn't want to spend more than 20% of his total time (50 hours) improving the house, on gardening, 20% of 50 hours is 10 hours so doesn't that just mean he doesn't want to spend more than 10 hours gardening, hence xig ≤ 10 hours ?
He doesn't want to spend more than 20% of the time he spends on gardening. It literally has the bold part in the problem statement. He doesn't have to spend 50 hours.
 

What is a "Linear programming problem"?

A Linear programming problem is a mathematical optimization technique used to find the best possible solution to a given problem. It involves maximizing or minimizing a linear objective function subject to a set of linear constraints. It is widely used in various fields such as economics, engineering, and business management.

What are the key components of a Linear programming problem?

The key components of a Linear programming problem include the objective function, decision variables, and constraints. The objective function represents the goal to be achieved, while the decision variables are the unknown quantities that need to be optimized. The constraints are the limitations or restrictions that must be satisfied in order to reach the optimal solution.

What are the different types of Linear programming problems?

The different types of Linear programming problems include:

  • Maximization problems - where the objective is to maximize a certain quantity.
  • Minimization problems - where the objective is to minimize a certain quantity.
  • Feasibility problems - where the goal is to find a feasible solution that satisfies all the constraints.
  • Unbounded problems - where the objective function can be maximized or minimized without any limitations.
  • Infeasible problems - where no feasible solution exists that satisfies all the constraints.

What is the simplex method and how does it solve Linear programming problems?

The simplex method is an algorithm that is used to solve Linear programming problems. It involves creating a feasible initial solution and then iteratively improving it until the optimal solution is reached. This is done by moving from one corner of the feasible region (also known as the simplex) to another in a systematic way, while simultaneously improving the objective function value. The process continues until no further improvement can be made, and the optimal solution is found.

What are the applications of Linear programming?

Linear programming has a wide range of applications in various fields, including:

  • Production planning and optimization in manufacturing industries.
  • Resource allocation and scheduling in project management.
  • Portfolio optimization in finance and investment management.
  • Transportation and logistics planning.
  • Energy management and resource allocation in renewable energy systems.

Similar threads

Replies
17
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • General Math
Replies
3
Views
999
  • Calculus and Beyond Homework Help
Replies
2
Views
4K
  • Linear and Abstract Algebra
Replies
7
Views
2K
  • General Math
Replies
13
Views
1K
  • Programming and Computer Science
Replies
1
Views
944
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Replies
5
Views
2K
Back
Top