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 · NYT · TWL 
Archives: 1 
Linear programming has been listed as a level4 vital article in Mathematics. If you can improve it, please do. This article has been rated as BClass by WikiProject Vital Articles. 
This article 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.
Unclear Dual Example[edit]
 (the farmer must receive no less than for his wheat)
If y variables determined the unit cost, then the right side in the constraints in the inequality is the cost for producing a unit of wheat, not the revenue (as stated). i.e we force the farmer pay for a unit of wheat more then the profit he gain for unit of wheat (S). which make interpretation and motivation of the problem very unclear. —Preceding unsigned comment added by 84.109.165.179 (talk) 09:17, 16 September 2008 (UTC)
I think one can interpret this as follows: the dual problem is now asked by a person who want to set a price to rent the land and buy the fertilizer and insecticide, so as to convince the farmer to borrow/sell all his belongings. The two inequalities can then be interpreted correctly, since if one of them is violated, the farmer would rather grow the wheat / barley than to borrow / sell. The objective function is the total cost that the person have to pay in total. And it is intuitive that the optimum is just the same as before, since the farmer should be willing to sell everything if he would not be able to gain more by growing wheat / barley.
Isaacto (talk) 05:52, 1 April 2010 (UTC)
Am still not clear Morganfresher31 (talk) 06:26, 1 September 2020 (UTC)
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]
 Wikipedia level4 vital articles in Mathematics
 Wikipedia BClass vital articles in Mathematics
 Wikipedia BClass level4 vital articles
 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