Talk:Linear programming
This is the talk page for discussing improvements to the Linear programming article. This is not a forum for general discussion of the article's subject. 
Article policies

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL 
Archives: 1Autoarchiving period: 365 days 
This level4 vital article is rated Bclass on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: 


Section 6  Bad Syntax Hides Lines[edit]
If you look at section 6, the 4.1 "Example" section, you'll see that something is wrong at the top, and the Z = ... part is totally missing from the output (and should probably be surrounded by ).
I'm just learning here, so I don't feel comfortable attempting a fix, but it's definitely not right as it is now.
Methods to convert nonlinear problems to linear programming problems[edit]
Hello,
I am not sure where this should go, but I believe there should be examples that convert: absolute value, min, and max into their linear counterparts.
Forgive me I make a mistake in the following examples, I do not know them by heart and am just quickly deriving them as I go.
e.g., min sum abs(x_i)
 into 
min sum e_i,
s.t.
e_i >= x_i, for all i
e_i >= +x_i, for all i
e.g.,
min max(x_i)
 into 
min e,
s.t.
e >= x_i, for all i
e.g., Minimize the minimum of a finite collection
min min(x_i)
 into 
min e,
s.t.
e <= x_i, for all i
NOTE  This has the degenerate solution of e > negative infinity. Some software will ignore this degeneracy. Microsoft Excel's simplex solver appears to (in at least some cases) to return the correct answer for problems of the form min_x min_i(f_i(x)), where f_i(x) is linear.
e.g., Converting equality (not really converting nonlinear problem to an LP problem, but still should be mentioned IMHO)
min x_i,
s.t.
x_i = g_i
 into 
min x_i,
s.t.
x_i <= g_i
x_i >= g_i
Edit: improved the readability
Generic blanket statement[edit]
Hi,
I don't comment much  but this statement seems kind of general, not really relevant and is not unique to the simplex algorithm: "The computing power required to test all the permutations to select the best assignment is vast; the number of possible configurations exceeds the number of particles in the observable universe. However, it takes only a moment to find the optimum solution by posing the problem as a linear program and applying the simplex algorithm. The theory behind linear programming drastically reduces the number of possible solutions that must be checked."
This is a blanket statement which can be said about any algorithm. Here is the same statement about sorting:
"The computing power required to test all the permutations to find the sorted assignment is vast; the number of possible configurations exceeds the number of particles in the observable universe. However, it takes only a moment to find the sorted solution by applying the bubble sort algorithm. The theory behind bubble sort drastically reduces the number of possible solutions that must be checked."
As already stated, the same could be said about almost any polynomial time algorithm. Every (decent) algorithm should be much better than "testing all permutations". Stating "the number of possible configurations exceeds the number of particles in the observable universe" is an amusing fact, but it only sounds impressive if you're not familiar with algorithms and computation.
Basically, I think that the above paragraph should be removed, however I'm not really sure if it's OK if I just remove it or ask you guys first. Usually when I change things I just remove/add single words etc.
Thanks.
 Sorting has never been done that way in practice. Radix sort was used to sort punch cards, with the help of sorting machines operating on one column at a time. People sorting things by hand tend to use bucket sort. Even the simplest computer algorithms are O(N²). LP on the other hand didn't have any decent algorithms before the simplex method was invented, as far as I know. Problems beyond just a few variables simply couldn't be handled since one indeed had to test all basis. KetchupSalt (talk) 16:00, 18 November 2021 (UTC)
Notes[edit]
Standard Form[edit]
Some authors prefer a stricter standard form.
 https://www3.nd.edu/~dgalvin1/30210/30210_F07/presentations/converting.pdf
 https://people.math.carleton.ca/~kcheung/math/notes/MATH5801/04/4_1_standard_form.html
Berebi (talk) 10:07, 13 March 2024 (UTC)
 Oh yeah, the present text doesn't actually show the standard form. Standard form should only use nonnegativity constraints. The volume of the interior for standard form problems is always zero I think, and the solution is always in the positive orthant of the plane defined by Ax=b. KetchupSalt (talk) 15:58, 31 March 2024 (UTC)
 BClass vital articles
 Wikipedia level4 vital articles
 Wikipedia vital articles in Mathematics
 BClass level4 vital articles
 Wikipedia level4 vital articles in Mathematics
 BClass vital articles in Mathematics
 BClass mathematics articles
 Highpriority mathematics articles
 BClass Systems articles
 Highimportance Systems articles
 Systems articles in operations research
 WikiProject Systems articles
 BClass Computer science articles
 Highimportance Computer science articles
 WikiProject Computer science articles