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

#### 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 ? ##\ ## 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?

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

##\ ##

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

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

##\ ##

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.

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: 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, ... ?

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

##\ ##

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