\ncalled an objective function<\/em>, which describes what you’d like
\nto maximize. Then you have a collection of inequalities, describing
\nthe constraints of the values in the objective function. The solution to
\nthe problem is a set of assignments to the variables in the objective function
\nthat provide a maximum.<\/p>\n
<\/p>\n
For example, imagine that you run a widget factory, which can You can reduce this to the following:<\/p>\n The fourth one is easy to overlook, but it’s really important. One of the tricky things about linear programming is that you need to be sure that you Once you’ve got all of the constraints laid out, you can convert the Maximize: <\/p>\n where<\/p>\n Once you’ve got the constraints worked out, you need to do something So we take the constraint equations, and add slack variables to all of them, We can re-render this into matrix form – but the next matrix needs Now, we need to work the real solution into the matrix. The way that we Once you’ve got the augmented form, there are a variety of techniques that The simplest solution strategy is called the simplex algorithm. In the In general, solving a linear programming problem via simplex is pretty (It’s like a wide range of problems. There are a lot of problems that are, This is getting long, so I think I’ll stop here for today. Next post, I’ll In my last post on game theory, I said that you could find an optimal probabilistic grand strategy for any two-player, simultaneous move, zero-sum game. It’s done through something called linear programming. But linear programming is useful for a whole lot more than just game theory. Linear programming is a general technique for solving a […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[25],"tags":[],"class_list":["post-639","post","type-post","status-publish","format-standard","hentry","category-graph-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-aj","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/639","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=639"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/639\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=639"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=639"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=639"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nproduce a maximum of W widgets per day. You can produce two
\ndifferent kinds of widgets – either widget 1, or widget 2. Widget one
\ntakes s1<\/sub> grams of iron to produce; widget 2 needs s2<\/sub>
\ngrams of iron. You can sell a widget 1 for a profit p1<\/sub> dollars,
\nand a widget 2 for a profit of p2<\/sub> dollars. You’ve got G grams of iron
\navailable for producing widgets. In order to maximize your profit, how
\nmany widgets of each type should you produce with the iron you have
\navailable to you?<\/p>\n\n
\np1<\/sub>x1<\/sub> + p2<\/sub>x2<\/sub>, where x1<\/sub> is the number of type 1 widgets you’ll produce, and x2<\/sub> is the number
\nof type 2 widgets.<\/li>\n
\nthe constraint imposed by the amount of iron you have available to produce
\nwidgets.)<\/li>\n
\nnegative number of either type of widgets.)<\/li>\n<\/ol>\n
\nreally include all of the constraints. You can very easily get non-sensical
\nresults if you miss a constraint. For example, if we left that constraint out
\nof this problem, and the profit on a type 2 widget was significantly higher
\nthan the profit on a type 1 widget, then you might wind up producing a negative<\/em> number of type 1 widgets, in order to allow you to produce
\nmore than W widgets per day.<\/p>\n
\nproblem to a matrix form, which is what we’ll use for the
\nsolution. Basically, for each constraint equation where you’ve got
\nboth x1<\/sub> and x2<\/sub>, you add a row to a coefficient
\nmatrix containing the coefficients, and a row to the result matrix containing the right-hand side of the inequality. So, for example, you’d convert
\nthe inequality “s1<\/sub>x1<\/sub> + s2<\/sub>x2<\/sub> ≤ G” to a row [s1<\/sub>,s2<\/sub>] in the coefficient matrix,
\nand “G” as a row in the result matrix. This rendering of the inequalities
\nis show below.<\/p>\n![\"linear-objective.png\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_307.png?resize=120%2C63\")
<\/p>\n![\"linear-simple.png\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_308.png?resize=264%2C62\")
<\/p>\n
\ncalled adding slack<\/em>. The idea is that you want to convert the
\ninequalities to equalities. The way to do that is by adding variables. For
\nexample, given the inequality x1<\/sub> + x2<\/sub>≤W, you
\ncan convert that to an equality by adding a variable representing
\nW-(x1<\/sub>+x2<\/sub>): x1<\/sub>+x2<\/sub>+xslack<\/sub>=W, where xslack<\/sub>≥0.<\/p>\n
\nwhich gives us the following:<\/p>\n\n
\nto includes rows and columns for the slack variables.<\/p>\n![\"linear-slack.png\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_309.png?resize=297%2C93\")
<\/p>\n
\ndo that is by taking the solution – the maximum of the objective function – and naming it “Z”, and adding the new objective function equation into the
\nmatrix. In our example, since we’re trying to maximize the
\nobjective “p1<\/sub>x1<\/sub> + p2<\/sub>x2<\/sub>“,
\nwe represent that with an equation “Z-p1<\/sub>x1<\/sub>-p2<\/sub>x2<\/sub>=0″. So the
\nfinal matrix, called the augmented form matrix<\/em> of our
\nlinear programming problem is:<\/p>\n![\"linear-augmented.png\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_310.png?resize=337%2C99\")
<\/p>\n
\nyou can use to get a solution. The intuition behind it is fairly simple: the
\nset of inequalities, interpreted geometrically, form a convex polyhedron. The
\nmaximum will be at one of the vertices of the polyhedron.<\/p>\n
\nsimplex algorithm, you basically start by finding an arbitrary vertex
\nof the polyhedron. You then look to see if either of the edges incident to that point slope upwards. If they do, you trace the edge upward to the next
\nvertex. And then you look to see if the other edge from that vertex slopes
\nupwards – and so on, until you reach a vertex where you can’t follow an edge to a higher point.<\/p>\n
\nfast – but it’s not necessarily so. The worst case time of it is
\nexponential. But in real linear programming problems, the
\nexponential case basically doesn’t come up.<\/p>\n
\nin theory, incredibly difficult – but because the difficult cases are
\nvery rare and rather contrived, they’re actually very easy to solve. Two
\nexamples of this that I find particularly interesting are both NP complete.
\nType checking in Haskell is one of them: in fact, the general type
\ninference in Haskell is worse that NP complete: the type validation is
\nNP-complete; type inference is NP-hard. But on real code, it’s effectively
\napproximately linear. The other one is a logic problem called 3-SAT. I
\nonce attended a great talk by a guy named Daniel Jackson, talking about
\na formal specification language he’d designed called Alloy<\/a>.
\nAlloy reduces
\nits specification checking to 3-SAT. Dan explained this saying: “The bad news
\nis, analyzing Alloy specifications is 3-SAT, so it’s exponential and NP-complete. But the good news is that analyzing Alloy specifications is 3-SAT,
\nso we can solve it really quickly.”)<\/p>\n
\nshow an implementation of the simplex algorithm, and maybe talk a little bit
\nabout the basic idea behind the non-exponential algorithms. After that, we’ll
\nget back to game theory, and I’ll show how you can construct a linear
\nprogramming problem out of a game.<\/p>\n","protected":false},"excerpt":{"rendered":"