Optimizing Constraints for Linear Programming Problem

In summary, the congressman is trying to maximize his expected number of votes by distributing money among four programs. His staff's estimates of the expected number of votes gained per dollar spent for the various programs are as follows: job training - 0.02, parks - 0.1, sanitation - 0.06, and mobile library - 0.07. However, the constraints he must observe are that none of the programs can receive more than 50% and less than 6% of the total allocation, the amount allocated to sanitation can not exceed the total allocated to the parks and mobile library programs, and the amount allocated to job training must at least equal the amount spent on sanitation.
  • #1
alpha
9
1
Homework Statement
Hi, trying to figure out this Linear programming problem:
A congressman of Canada is responsible for the allocation of $400000 for programs and projects in his district. It is up to the congressman to decide how to distribute the money.
The congressman has decided to allocate the money to four ongoing programs because of their importance to his district - a job training program, a parks project, a sanitation project, and a mobile library. However, the congressman wants to distribute the money in a manner that will please the most voters, or, in other words, gain him the most votes in the upcoming election. His staff's estimates of the expected number of votes gained per dollar spent for the various programs are as follows.
job training - 0.02
parks - 0.1
sanitation - 0.06
mobile library - 0.07
In order also to satisfy several local influential citizens who financed his election, he is obliged to observe the following guidelines.
None of the programs can receive more than 50% and less than 6% of the total allocation.
The amount allocated to sanitation can not exceed the total allocated to the parks and mobile library programs.
The amount allocated to job training must at least equal the amount spent on sanitation.
What is the maximal expected number of votes the congressman can gain by distributing the money among the programs?

So far I have figured out the following:

maximize 0.02x1 + 0.01x2 +0.06x3 + 0.07x4

subject to:

xi <= 200,000

xi >= 24,000

x3 <= x2 +x4

x1 >= x3

But my constraints are wrong as it is not working in solver, does anyone have any suggestions on the constraints?
Relevant Equations
So far I have figured out the following:

maximize 0.02x1 + 0.01x2 +0.06x3 + 0.07x4

subject to:

xi <= 200,000

xi >= 24,000

x3 <= x2 +x4

x1 >= x3
So far I have figured out the following:

maximize 0.02x1 + 0.01x2 +0.06x3 + 0.07x4

subject to:

xi <= 200,000

xi >= 24,000

x3 <= x2 +x4

x1 >= x3

But when I try to solve this in solver, I get an error which means my contraints must be wrong. Any suggestions on what constaints to put?
 
Physics news on Phys.org
  • #2
Hello @alpha,
:welcome: ##\qquad## !​
Well, I get
1666562715528.png


(with 0.1 voter/dollar for parks, as in the problem statement)

So how did you set up your stuff for the solver ?

##\ ##
 
  • #3
alpha said:
Homework Statement:: Hi, trying to figure out this Linear programming problem:
A congressman of Canada is responsible for the allocation of $400000 for programs and projects in his district. It is up to the congressman to decide how to distribute the money.
The congressman has decided to allocate the money to four ongoing programs because of their importance to his district - a job training program, a parks project, a sanitation project, and a mobile library. However, the congressman wants to distribute the money in a manner that will please the most voters, or, in other words, gain him the most votes in the upcoming election. His staff's estimates of the expected number of votes gained per dollar spent for the various programs are as follows.
job training - 0.02
parks - 0.1
sanitation - 0.06
mobile library - 0.07
In order also to satisfy several local influential citizens who financed his election, he is obliged to observe the following guidelines.
None of the programs can receive more than 50% and less than 6% of the total allocation.
The amount allocated to sanitation can not exceed the total allocated to the parks and mobile library programs.
The amount allocated to job training must at least equal the amount spent on sanitation.
What is the maximal expected number of votes the congressman can gain by distributing the money among the programs?

But my constraints are wrong as it is not working in solver, does anyone have any suggestions on the constraints?
Relevant Equations:: So far I have figured out the following:

maximize 0.02x1 + 0.01x2 +0.06x3 + 0.07x4

subject to:
xi <= 200,000
xi >= 24,000
x3 <= x2 +x4
x1 >= x3

But when I try to solve this in solver, I get an error which means my contraints must be wrong. Any suggestions on what constaints to put?
The function you're trying to maximize has an error. Per the problem description, the expected no. of votes per dollar spent is 0.1, not 0.01. Either the problem description is wrong or the coefficient of ##x_2## in your function is wrong.
 
  • #4
Hi, so I've been using sumproduct and individually mapping out all of the constraints on it using >= or <= depending on the constraint. I tried running this through wolfram alpha linear programming to see if my constraints are the problem, but it didnt work there either. I don't understand how these constraints worked for you can you explain how your layout compares to mine?
 
  • #5
alpha said:
can you explain how your layout compares to mine?
Not really: I have no idea about your setup :smile: .
Mine is very straightforward and looks like this:

1666563440760.png


with Cell Voters =0.02*x_1+0.1*x_2+0.06*x_3+0.07*x_4
and Cell Sum24_ =x_2+x_4

C4 is x_1 etc. Note that I have cell C7 (x_4 =400000-x_1-x_2-x_3) and no need to let it be varied by the solver

##\ ##
 
  • #6
Mark44 said:
The function you're trying to maximize has an error. Per the problem description, the expected no. of votes per dollar spent is 0.1, not 0.01. Either the problem description is wrong or the coefficient of ##x_2## in your function is wrong.
Hi sorry about that the voets are 0.01** not 0.1
 
  • #7
BvU said:
Not really: I have no idea about your setup :smile: .
Mine is very straightforward and looks like this:

View attachment 315934

with Cell Voters =0.02*x_1+0.1*x_2+0.06*x_3+0.07*x_4
and Cell Sum24_ =x_2+x_4

C4 is x_1 etc. Note that I have cell C7 (x_4 =400000-x_1-x_2-x_3) and no need to let it be varied by the solver

##\ ##
Im trying to compare my notes but nothings going into be honest. I am going to sleep on it and try again tomorrow and let you know how it goes. Thank you for your input so far :)
 
  • Like
Likes BvU
  • #8
OK,

so with Voters =0.02*x_1+0.01*x_2+0.06*x_3+0.07*x_4
it's pretty obvious mobile library wants to be at the max and parks at the minimum.
Job training doesn't yield many votes, but it has to be ##\ge## sanitation. Meaning these two split the remainder.
Oops, now I've posted the answer, a PF nono :woot:

But the answer in itself isn't interesting. What matters is why your setup doesn't work.
However, still have no idea what exactly your setup is ...

##\ ##
 
  • #9
alpha said:
Im trying to compare my notes but nothings going into be honest. I am going to sleep on it and try again tomorrow and let you know how it goes. Thank you for your input so far :)
Hi so turns out I have to do this on spyder using PuLP not excel solver, so looks like I need to get that set up ready.
 
  • #10
BvU said:
OK,

so with Voters =0.02*x_1+0.01*x_2+0.06*x_3+0.07*x_4
it's pretty obvious mobile library wants to be at the max and parks at the minimum.
Job training doesn't yield many votes, but it has to be ##\ge## sanitation. Meaning these two split the remainder.
Oops, now I've posted the answer, a PF nono :woot:

But the answer in itself isn't interesting. What matters is why your setup doesn't work.
However, still have no idea what exactly your setup is ...

##\ ##
Hi so I have to change my set up onto spyder using PuLP. Not sure if that is a better option since I have never used it before.
I think I have done it right on PuLp but I am not sure to be honest. Here is my code.
# -*- coding: utf-8 -*-
""""
Created on Sun Oct 23 21:03:47 2022
Votes problem from assignment

Job Trainings Parks Sanitation Mobile Library RHS

c1 0 -1 1 -1 0
c2 1 0 -1 0
c3 1 0 0 0 153000
c4 0 1 0 0 153000
c5 0 0 1 0 153000
c6 0 0 0 1 153000
c7 -1 0 0 0 -20400
c8 0 -1 0 0 -20400
c9 0 0 -1 0 -20400
c10 0 0 0 -1
votes/$ 0.04 0.09 0.05 0.03 0
max 0.04x1 + 0.09x2 + 0.05x3 + 0.03x4
s.t

xi >= 20400
xi =< 153000
x1 >= x3
x3 =< x2 + x4

@author:
"""

import pulp as pl # library with an LP Solver is named as pl
import pandas as pd

df1 = pd.read_excel('Question1.xlsx', 'Problem1', index_col=0)

# create dictionary with pairs ""product2 - price; got it from df
product = df1.loc[df1.index[-1],df1.columns[0:-1]].to_dict()

# cut off constraint matrix from dataframe; to use format Ax<=b
constraint_matrix = pd.DataFrame(
df1,index= df1.index[0:-1],columns = df1.columns[0:-1]).to_dict('index')

# use here a dictionary to loop through names of products and constraints
# get RHS associated with the constraints; dictionary: 'constraint'-rhs, from df
rhs = df1.loc[df1.index[0:-1],df1.columns[-1]].to_dict()

# ******************** MODEL ************************************************
# Creates the model which is a ""Linear Program"" with ""Max"" objective function
# any name for the model/object is fine
# defined as maximisation
model1 = pl.LpProblem('Problem 1', pl.LpMaximize)

# Creates a dictionary of variables. these are continuous varriables (default)
# use keys from the earlier defined dictionary to loop through variables later
variables = pl.LpVariable.dicts('amount', product, lowBound=0)
# add/define the objective function
model1 += pl.lpSum([product[ i]*variables[ i] for i in product])

# add constraints to the model; format like Ax<=b
for c in rhs: # notice [] in lpSum
model1 += (pl.lpSum([constraint_matrix[c][ u]*variables[ u] for u in product])
<= rhs[c], c) # c here is to name the constraints
# #specification per tonne

model1.solve() # solve the problem with the default solver

# The status of the solution is printed to the screen
print('Status:', pl.LpStatus[model1.status])

# The optimised objective function value is printed to the screen
print("Total Revenue = ", pl.value(model1.objective))

if (pl.LpStatus[model1.status] == 'Optimal'):
# Each of the variables is printed with it's resolved optimum value
for v in model1.variables():
print(v.name, '=', v.varValue)

# # # #see https://realpython.com/linear-programming-python/
# for name, constraint in model1.constraints.items():
# print(f""{name}: {constraint.value()}"")# The problem data is written to an .lp file
model1.writeLP('Mix problem.lp')
 
Last edited by a moderator:
  • #11
alpha said:
Hi so I have to change my set up onto spyder using PuLP. Not sure if that is a better option since I have never used it before.
I think I have done it right on PuLp but I am not sure to be honest. Here is my code.
# -*- coding: utf-8 -*-
""""
Created on Sun Oct 23 21:03:47 2022
Votes problem from assignment

Job Trainings Parks Sanitation Mobile Library RHS

c1 0 -1 1 -1 0
c2 1 0 -1 0
c3 1 0 0 0 153000
c4 0 1 0 0 153000
c5 0 0 1 0 153000
c6 0 0 0 1 153000
c7 -1 0 0 0 -20400
c8 0 -1 0 0 -20400
c9 0 0 -1 0 -20400
c10 0 0 0 -1
votes/$ 0.04 0.09 0.05 0.03 0
max 0.04x1 + 0.09x2 + 0.05x3 + 0.03x4
s.t

xi >= 20400
xi =< 153000
x1 >= x3
x3 =< x2 + x4

@author:
"""

import pulp as pl # library with an LP Solver is named as pl
import pandas as pd

df1 = pd.read_excel('Question1.xlsx', 'Problem1', index_col=0)

# create dictionary with pairs ""product2 - price; got it from df
product = df1.loc[df1.index[-1],df1.columns[0:-1]].to_dict()

# cut off constraint matrix from dataframe; to use format Ax<=b
constraint_matrix = pd.DataFrame(
df1,index= df1.index[0:-1],columns = df1.columns[0:-1]).to_dict('index')

# use here a dictionary to loop through names of products and constraints
# get RHS associated with the constraints; dictionary: 'constraint'-rhs, from df
rhs = df1.loc[df1.index[0:-1],df1.columns[-1]].to_dict()

# ******************** MODEL ************************************************
# Creates the model which is a ""Linear Program"" with ""Max"" objective function
# any name for the model/object is fine
# defined as maximisation
model1 = pl.LpProblem('Problem 1', pl.LpMaximize)

# Creates a dictionary of variables. these are continuous varriables (default)
# use keys from the earlier defined dictionary to loop through variables later
variables = pl.LpVariable.dicts('amount', product, lowBound=0)
# add/define the objective function
model1 += pl.lpSum([product[ i]*variables[ i] for i in product])

# add constraints to the model; format like Ax<=b
for c in rhs: # notice [] in lpSum
model1 += (pl.lpSum([constraint_matrix[c][ u]*variables[ u] for u in product])
<= rhs[c], c) # c here is to name the constraints
# #specification per tonne

model1.solve() # solve the problem with the default solver

# The status of the solution is printed to the screen
print('Status:', pl.LpStatus[model1.status])

# The optimised objective function value is printed to the screen
print("Total Revenue = ", pl.value(model1.objective))

if (pl.LpStatus[model1.status] == 'Optimal'):
# Each of the variables is printed with it's resolved optimum value
for v in model1.variables():
print(v.name, '=', v.varValue)

# # # #see https://realpython.com/linear-programming-python/
# for name, constraint in model1.constraints.items():
# print(f""{name}: {constraint.value()}"")# The problem data is written to an .lp file
model1.writeLP('Mix problem.lp')
the question was also altered by the prof so I have updated that as well. Sorry for not mentioning
 
Last edited by a moderator:
  • #12
Had to look up "spyder pulp" to find out this is python-ish. Interesting IDE, thanks for mentioning it !
Can read rudimentary python, but this is a bit more than that o0)

No idea what's going on. What comes out ? Crash, wrong answer, ... ?

alpha said:
the question was also altered by the prof
What's changed ?

##\ ##
 
  • #13
BvU said:
Had to look up "spyder pulp" to find out this is python-ish. Interesting IDE, thanks for mentioning it !
Can read rudimentary python, but this is a bit more than that o0)

No idea what's going on. What comes out ? Crash, wrong answer, ... ?What's changed ?

##\ ##
The number of votes per dollar and the constraints. It doesn't crash but I am not sure the code I've posted above is correct since I've used different sources to figure it out so needed some guidance on the legibility of the code and if I am in the right direction or need drastic changes to my approach
 
  • #14
@alpha, I edited the code in post 10 because your use of indexes i and u within brackets gets rendered by browsers as BBCode for italics and underscore.

I modified it by changing [i] and [u] to [ i] and [ u]. IOW, by adding a space between the left bracket and the character inside.
 
  • Like
Likes alpha

Related to Optimizing Constraints for Linear Programming Problem

1. What is a Linear Programming Problem?

A Linear Programming Problem (LPP) is a mathematical optimization technique used to find the best possible solution to a problem with linear constraints and a linear objective function. It involves maximizing or minimizing a linear objective function while satisfying a set of linear constraints.

2. What are the key components of a Linear Programming Problem?

The key components of a Linear Programming Problem are the decision variables, objective function, and constraints. Decision variables are the unknown quantities that we are trying to optimize. The objective function is a linear mathematical expression that represents the goal of the problem. Constraints are linear inequalities or equations that limit the values of the decision variables.

3. What are the different types of Linear Programming Problems?

The two main types of Linear Programming Problems are maximization problems and minimization problems. In a maximization problem, the goal is to find the maximum value of the objective function. In a minimization problem, the goal is to find the minimum value of the objective function. Other types of Linear Programming Problems include integer programming, mixed-integer programming, and multi-objective programming.

4. What are the steps involved in solving a Linear Programming Problem?

The steps involved in solving a Linear Programming Problem are as follows:

  1. Formulate the problem by identifying the decision variables, objective function, and constraints.
  2. Graph the constraints to create a feasible region.
  3. Identify the corner points of the feasible region.
  4. Evaluate the objective function at each corner point to find the optimal solution.
  5. Check the solution for feasibility and optimality.

5. What are some real-world applications of Linear Programming?

Linear Programming has a wide range of applications in various industries, including transportation, manufacturing, finance, and telecommunications. Some examples include optimizing transportation routes, production planning, portfolio optimization, and network flow optimization.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
4K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Mechanical Engineering
Replies
3
Views
109
  • Programming and Computer Science
Replies
32
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
Back
Top