Python线性规划代写 | CSC 445/545 OPERATIONS RESEARCH: LINEAR PROGRAMMING

本次加拿大代写主要为Python线性规划相关的assignment

1 Overview
This assignment requires implementing an LP solver which reads a text-based representation of a
linear program from standard input and outputs the result of solving the LP (including whether
the LP turned out to be infeasible or unbounded). Unlike the other assignments in this course, you
are permitted to use oating-point computation to solve the LP (so it is not necessary to use exact
fractional arithmetic).

Section 2 describes the input format and Section 3 describes the required output format. For this
assignment, correctness is critical, and no marks will be given for any code that cannot be
rigorously validated on actual inputs (so you should prioritize basic correctness over adding extra
functionality).

The project will be marked based on a combination of empirical validation (i.e. running your solver
on various test LPs), human inspection of your code (which, in general, will not be performed unless
it is clear that your implementation is correct) and evaluation of the accompanying documentation.

You may implement the project in C, C++, Python or Java, and must design your solution to run
correctly on the Computer Science login servers at linux.csc.uvic.ca (which requires working
with the compiler or interpreter versions installed on that system). You may be allowed to use a
dierent language at the instructor’s discretion (but only if given explicit permission in advance).

Note that some aspects of the project might become more dicult depending on the language
choice; this is entirely your responsibility.

2 Input Format
The input format is a simple text-based encoding of a maximization LP in standard form. An LP
of the form
max. c1x1 +c2x2 +: : : +cnxn
s.t. a1;1×1 +a1;2×2 +: : : +a1;nxn  b1
a2;1×1 +a2;2×2 +: : : +a2;nxn  b2
.
.
.
ak;1×1 +ak;2×2 +: : : +ak;nxn  bk
x1; x2; : : : ; xn  0

will be encoded as follows:
ˆ The rst line of the input le will contain the values
c1 c2 : : : cn

separated by whitespace (tabs or spaces)
ˆ Each remaining line will encode one constraint. The line for constraint i will contain
ai;1 ai;2 : : : ai;n bi

separated by whitespace.
ˆ Blank lines (lines which are empty or contain only whitespace characters) may be present
and must be completely ignored.
ˆ The non-negativity constraints (x1; x2; : : : ; xn  0) do not appear in the input encoding,
since they are implied by the use of standard form.

For example, the LP
max. 0:5×1 + 3×2
s.t. x1 + 4×2  4
4×1 + 2×2  4
3×1 + 4×2  5
5×1 + 1:8×2  5
x1; x2  0

would be encoded as
0.5 3
1 4 4
4 2 4
3 4 5
5 1.8 5

Notice that the number of variables and constraints is implied by the number of values on each
line (and the number of non-empty lines). You may assume that the input format is consistent:
If the rst line (containing the objective coecients) contains n values (indicating n optimization
variables), each subsequent line (a constraint) will contain n + 1 values. You are not required to
write error-handling logic to address the case of a malformed input.