# Optimizing Constraints for Linear Programming Problem

• alpha
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.
alpha
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? Hello @alpha, ##\qquad## !​ Well, I get (with 0.1 voter/dollar for parks, as in the problem statement) So how did you set up your stuff for the solver ? ##\ ## 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.

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?

alpha said:
can you explain how your layout compares to mine?
Mine is very straightforward and looks like this:

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

##\ ##

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

BvU said:
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 :)

BvU
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

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 ...

##\ ##

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.

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

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

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: 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

# 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)
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:
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

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 ?

##\ ##

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

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

@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.

alpha

## 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.

• 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