# HG changeset patch # User Robert McIntyre # Date 1320255085 25200 # Node ID 89462678a932187ff3c5e040b847094ee78ea5dc # Parent 4ea23241ff5b02f25004fdc2f76008c48fdfec7c spell check diff -r 4ea23241ff5b -r 89462678a932 org/lpsolve.org --- a/org/lpsolve.org Wed Nov 02 10:28:50 2011 -0700 +++ b/org/lpsolve.org Wed Nov 02 10:31:25 2011 -0700 @@ -1,13 +1,11 @@ #+title: Discovering Effective Pok\eacute{}mon Types Using Linear Optimization #+author: Robert McIntyre & Dylan Holmes #+EMAIL: rlm@mit.edu -#+description: Using Lpsolve to func effective pokemon types in clojure. -#+keywords: Pokemon, clojure, linear optimization, lp_spolve, LpSolve +#+description: Using Lpsolve to find effective pokemon types in clojure. +#+keywords: Pokemon, clojure, linear optimization, lp_solve, LpSolve #+SETUPFILE: ../../aurellem/org/setup.org #+INCLUDE: ../../aurellem/org/level-0.org - - * Introduction This post continues the [[./types.org][previous one]] about pok\eacute{}mon types. Pok\eacute{}mon is a game in which adorable creatures battle each @@ -21,7 +19,7 @@ games, attacks can be either twice as effective as normal (Water vs. Fire), neutrally effective (Normal vs. Normal), half as effective (Fire vs. Water), or not effective at all (Electric vs. Ground). We -represent these strengths and weakessness as the numbers 2, 1, +represent these strengths and weaknesses as the numbers 2, 1, $\frac{1}{2}$, and 0, and call them the /susceptance/ of one type to another. @@ -37,7 +35,7 @@ In the [[./types.org][previous post]], we used the best-first search algorithm to find the most effective Pok\eacute{}mon type combinations. Afterwards, we realized that we could transform this search problem into a /linear -optimization problem/. This conversion offeres several advantages: +optimization problem/. This conversion offers several advantages: first, search algorithms are comparatively slow, whereas linear optimization algorithms are extremely fast; second, it is difficult to determine whether a search problem has any solution, whereas it is @@ -104,34 +102,7 @@ |----------+----------------------+---------------------+--------------| | Profit | $1.30 per bushel | $2.00 per bushel | | -*** COMMENT -can be represented as a linear optimization - problem. In this form, it is a problem with two variables\mdash{}the number of - acres of wheat, \(w\), and the number of acres of barley, \(b\). The - aim is to maximize profit, which - - subject to three constraints: the farmer can't spend more money -than he has, the farmer can't use more acres than he owns, and the harvest has -to fit in his storage space. - -We can express these constraints succinctly using matrix -notation. Denoting the number of acres of barley and wheat by \(b\) and \(w\), -we want to maximize the expression \(143 w + 60 b\) subject to - -\( -\begin{cases} -120 w + 210 b & \leq & 1500\\ -110 w + 30 b & \leq & 4000\\ -1 w + 1 w & \leq & 75 -\end{cases} -\) - -#\(\begin{bmatrix}120&210\\110&30\\1 & -#1\end{bmatrix}\;\begin{bmatrix}w\\b\end{bmatrix} -#\leq \begin{bmatrix}\$15000\\4000\text{ bushels}\\75\text{ acres}\end{bmatrix}\) - ** Solution using LP Solve -#(LP solve is available at http://www.example.com.) In a new file, =farmer.lp=, we list the variables and constraints of our problem using LP Solve syntax.