Linear Programming

[spelare]

Hi!

I am new to use my ti-84 calc. I am wondering if there is a program that can solve linear equations. For example this:

max z= x₁+3x₂
2x₁ + x₂ ≤ 14
x₁ + 2x₂ ≤ 10
x₁ ≥ 2
x₂ ≥ 0

I have tried using inequalz program but I am not able to type that on program
"z= x₁+3x₂"

[DarkerLine]

I don't know of a program for solving such systems specifically. But programs for solving systems of linear equations do exist, and in fact you can use the rref( command to solve them. From there, it's not too hard to solve the system: solve every pair of equations, eliminate the intersection points that don't satisfy the conditions, evaluate z on those that do, and find the maximum.

[thornahawk]

Well, some people have written LP programs for the TI 83+, but unless you're familiar with putting LP problems in "restricted normal form" (i.e., slack and artificial variables and everything), they're not too intuitive to use.

@DarkerLine: In a sense, you could use something like rref( to help solve an LP problem, but there are certain complicating matters one should take into account. I'm no specialist so I might be oversimplifying the matter.

@spelare: In any case, if you're really interested in doing LP problems on your calc, you might want to try looking for the "revised simplex algorithm" as done by Bartels and Golub. The implementation is thorny, but the advantage of it is that it makes efficient use of the "tableau" information.

thornahawk

[CoBB]

[thornahawk]

Which is why the "interior point" approach got much-deserved attention for solving large-scale LP problems. I however think that "revised simplex" would be good enough for most problems that would fit into a normal TI calculator. The need to take care of a good number of subtleties, however, makes me think that the resulting program would be quite large.

To further clarify what I was telling DarkerLine: good implementations of simplex-based LP solvers use LU decomposition: they factor a matrix that is derived from the "tableau" into a lower-triangular and upper-triangular matrix (not much different from what you are familiar with as Gaussian elimination), and then at each step of searching for the optimum point, the factorizations are updated accordingly. This brings down supposedly O(n³) work per iteration down to O(n²) at the expense of some degradation in accuracy; hence the need to do a fresh factorization every so often instead of an update. All these sophistications make for long programs. (An LU decomposition routine I wrote for the TI 83+ is ~ 500 bytes on my calculator. Building from that a routine for solving LP problems would maybe triple or quadruple the size.)

If you're still unfazed, I would recommend that you look into the Journal of the ACM article by Bartels and Golub on their version of the simplex algorithm. Translating their ALGOL code to TI 83+ would be quite the project. ;)

thornahawk

[DarkerLine]