# input variables
Constraint_Coefficients = #constraintCoefficients#;
Constraint_Constants = #constraintConstants#;
Objective_Coefficents = #objectiveCoefficients#;
Constraint_Type = #constraintTypes#;
Variables_Names = #variableNames#; # can use "x" instead of a array
Variable_Type = #variableTypes#;
Problem_Type = '#ddlMinMax#';
# define function to make tableau (2D array) from the LP dictionary
def tableau(D):
# get current variables from current LP dictionary
current_variables_list=list(D.nonbasic_variables())+list(D.basic_variables());
# get current variable order
current_variables_order = list(range(len(variables_list)));
for variable in variables_list:
current_variables_order[variables_list.index(variable)] = current_variables_list.index(variable);
# define the double array
A = [[0]*len(current_variables_list) for i in list(range(len(D.basic_variables())))];
# retrieve coefficients of current states
for i in range(len(D.basic_variables())):
for j in range(len(D.nonbasic_variables())):
A[i][current_variables_order[j]] = D.column_coefficients(current_variables_list[j])[i];
# fill the one for basic variables
for i in range(len(D.basic_variables())):
A[i][current_variables_order[len(D.nonbasic_variables())+i]] = 1;
# add solution of each row
for i in range(len(D.basic_variables())):
A[i] += [D.constant_terms()[i]];
# add 'basic variables' column
for i in range(len(D.basic_variables())):
A[i] = [D.basic_variables()[i]] + A[i];
# add objective row
objective_row =[0]*len(current_variables_list);
for j in range(len(D.nonbasic_variables())):
if Problem_Type == 'max':
objective_row[current_variables_order[j]] = -1*D.objective_coefficients()[j];
else:
objective_row[current_variables_order[j]] = D.objective_coefficients()[j];
if Problem_Type == 'min':
objective_row += [-1*D.objective_value()];
else:
objective_row += [D.objective_value()];
obj_name = 'z';
objective_row = [obj_name] + objective_row;
A = [objective_row] + A;
# add head row
head_row = ['basic'] + variables_list + ['solution'];
A = [head_row] + A;
return A
# end of tableau function
# display tableau function
def dis_tableau(tableau):
T = tableau;
begin_code = ' $$$$ \\\\begin{array}';
end_code = '\\\\hline \\\\end{array} $$$$ ';
col_code = '{ | c |';
for vl in T[0]:
col_code += ' l ';
col_code += '|}';
#add head row
content_code = '\\\\hline ';
for name in T[0]:
content_code += str(name) + ' & ';
content_code = content_code[:-2];
content_code += '\\\\\\\\ \\\\hline ';
for i in range(1,len(T)):
for j in range(len(T[0])):
content_code += ' ' + str(T[i][j]) ;
content_code += ' & '
content_code += ' \\\\\\\\ ';
if i == 1:
content_code += ' \\\\hline ';
tex_code = begin_code + col_code + content_code + end_code
show(html(tex_code))
#define function to make the ratios table
def ratio_table(D):
entering = D.entering();
entered_ratio = D.ratios();
A = [];
for row in entered_ratio:
row_index = list(D.basic_variables()).index(row[1]);
A += [[row[1],D.column_coefficients(entering)[row_index],D.constant_terms()[row_index],row[0]]]
A = [["Possible Leaving",str(entering) + "(entering)","Solutions","Ratio"]] + A
return A
#ratios table function end
# Construct the interactive LP problem class P
Con_Coe = Constraint_Coefficients;
Con_Const = Constraint_Constants;
Obj_Coe = Objective_Coefficents;
P = InteractiveLPProblem(Con_Coe, Con_Const, Obj_Coe, Variables_Names, problem_type=Problem_Type,constraint_type=Constraint_Type,variable_type=Variable_Type,);
show(P)
if not P.is_feasible():
show(html('This LP is not feasible'))
assert()
# convert problem to standard form Ps
Ps = P.standard_form(slack_variables="s");
# get variables list (including slack variables)
d_variables_list = list(Ps.decision_variables());
s_variables_list = list(Ps.slack_variables());
variables_list = d_variables_list+s_variables_list;
# construct initial dictionary class D
D=Ps.initial_dictionary();
show(D)
iter = 1;
# do simplex iteration
while D.is_optimal()==false:
show(html("Iteration step " + str(iter) ))
dis_tableau(tableau(D))
OC_list=list((D. objective_coefficients()));
enter_index = OC_list.index(max(OC_list));
Entering = D.nonbasic_variables()[enter_index]
D.enter(Entering);
show(html("Enter " + str(D.entering()) ))
show(D)
show(table(ratio_table(D)))
entered_ratio=D.ratios();
possible_leaving_variables = [row[1] for row in entered_ratio];
possible_leaving_ratios = [row[0] for row in entered_ratio];
leave_index = possible_leaving_ratios.index(min(possible_leaving_ratios));
Leaving = possible_leaving_variables[leave_index]
D.leave(Leaving);
show(html("Leave " + str(D.leaving()) ))
show(D)
show(html('
'))
D.update();
iter += 1;
show(html("Iteration step " + str(iter) + ""))
dis_tableau(tableau(D))
show(D)
#retrieve solution
D_final_basic_var = list(D.basic_variables());
D_final_nonbasic_var = list(D.nonbasic_variables());
sol = [];
for vr in d_variables_list:
if vr in D_final_basic_var:
sol += [D.constant_terms()[D_final_basic_var.index(vr)]];
if vr in D_final_nonbasic_var:
sol += [0];
final_obj_value = D.objective_value();
if Problem_Type == 'min':
final_obj_value = -final_obj_value
show(html("The optimal value is " + str(final_obj_value) + ","))
show(html("with the optimal solution " + str(vector(sol)) + "."))