Mercurial > pokemon-types

comparison org/lpsolve.org @ 12:89462678a932

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
spell check
author Robert McIntyre <rlm@mit.edu>
date Wed, 02 Nov 2011 10:31:25 -0700
parents 4ea23241ff5b
children e1b7ef479bd1
comparison
equal deleted inserted replaced
11:4ea23241ff5b 12:89462678a932
1 #+title: Discovering Effective Pok\eacute{}mon Types Using Linear Optimization 1 #+title: Discovering Effective Pok\eacute{}mon Types Using Linear Optimization
2 #+author: Robert McIntyre & Dylan Holmes 2 #+author: Robert McIntyre & Dylan Holmes
3 #+EMAIL: rlm@mit.edu 3 #+EMAIL: rlm@mit.edu
4 #+description: Using Lpsolve to func effective pokemon types in clojure. 4 #+description: Using Lpsolve to find effective pokemon types in clojure.
5 #+keywords: Pokemon, clojure, linear optimization, lp_spolve, LpSolve 5 #+keywords: Pokemon, clojure, linear optimization, lp_solve, LpSolve
6 #+SETUPFILE: ../../aurellem/org/setup.org 6 #+SETUPFILE: ../../aurellem/org/setup.org
7 #+INCLUDE: ../../aurellem/org/level-0.org 7 #+INCLUDE: ../../aurellem/org/level-0.org
8
9
10 8
11 * Introduction 9 * Introduction
12 This post continues the [[./types.org][previous one]] about pok\eacute{}mon types. 10 This post continues the [[./types.org][previous one]] about pok\eacute{}mon types.
13 Pok\eacute{}mon is a game in which adorable creatures battle each 11 Pok\eacute{}mon is a game in which adorable creatures battle each
14 other using fantastic attacks. It was made into a several gameboy 12 other using fantastic attacks. It was made into a several gameboy
19 example, Water attacks are strong against Fire pok\eacute{}mon, while 17 example, Water attacks are strong against Fire pok\eacute{}mon, while
20 Electric attacks are weak against Ground Pok\eacute{}mon. In the 18 Electric attacks are weak against Ground Pok\eacute{}mon. In the
21 games, attacks can be either twice as effective as normal (Water 19 games, attacks can be either twice as effective as normal (Water
22 vs. Fire), neutrally effective (Normal vs. Normal), half as effective 20 vs. Fire), neutrally effective (Normal vs. Normal), half as effective
23 (Fire vs. Water), or not effective at all (Electric vs. Ground). We 21 (Fire vs. Water), or not effective at all (Electric vs. Ground). We
24 represent these strengths and weakessness as the numbers 2, 1, 22 represent these strengths and weaknesses as the numbers 2, 1,
25 $\frac{1}{2}$, and 0, and call them the /susceptance/ of one type to 23 $\frac{1}{2}$, and 0, and call them the /susceptance/ of one type to
26 another. 24 another.
27 25
28 If a pokemon has two types, then the strengths and weakness of each 26 If a pokemon has two types, then the strengths and weakness of each
29 type are /multiplied/ together. Thus Electric (2x weak to Ground) 27 type are /multiplied/ together. Thus Electric (2x weak to Ground)
35 that type. 33 that type.
36 34
37 In the [[./types.org][previous post]], we used the best-first search algorithm to find 35 In the [[./types.org][previous post]], we used the best-first search algorithm to find
38 the most effective Pok\eacute{}mon type combinations. Afterwards, we 36 the most effective Pok\eacute{}mon type combinations. Afterwards, we
39 realized that we could transform this search problem into a /linear 37 realized that we could transform this search problem into a /linear
40 optimization problem/. This conversion offeres several advantages: 38 optimization problem/. This conversion offers several advantages:
41 first, search algorithms are comparatively slow, whereas linear 39 first, search algorithms are comparatively slow, whereas linear
42 optimization algorithms are extremely fast; second, it is difficult to 40 optimization algorithms are extremely fast; second, it is difficult to
43 determine whether a search problem has any solution, whereas it is 41 determine whether a search problem has any solution, whereas it is
44 straightforward to determine whether a linear optimization problem has 42 straightforward to determine whether a linear optimization problem has
45 any solution; finally, because systems of linear equations are so 43 any solution; finally, because systems of linear equations are so
102 | Expense | $120 per acre | $210 per acre | $15000 | 100 | Expense | $120 per acre | $210 per acre | $15000 |
103 | Storage | 110 bushels per acre | 30 bushels per acre | 4000 bushels | 101 | Storage | 110 bushels per acre | 30 bushels per acre | 4000 bushels |
104 |----------+----------------------+---------------------+--------------| 102 |----------+----------------------+---------------------+--------------|
105 | Profit | $1.30 per bushel | $2.00 per bushel | | 103 | Profit | $1.30 per bushel | $2.00 per bushel | |
106 104
107 *** COMMENT
108 can be represented as a linear optimization
109 problem. In this form, it is a problem with two variables\mdash{}the number of
110 acres of wheat, \(w\), and the number of acres of barley, \(b\). The
111 aim is to maximize profit, which
112
113 subject to three constraints: the farmer can't spend more money
114 than he has, the farmer can't use more acres than he owns, and the harvest has
115 to fit in his storage space.
116
117 We can express these constraints succinctly using matrix
118 notation. Denoting the number of acres of barley and wheat by \(b\) and \(w\),
119 we want to maximize the expression \(143 w + 60 b\) subject to
120
121 \(
122 \begin{cases}
123 120 w + 210 b & \leq & 1500\\
124 110 w + 30 b & \leq & 4000\\
125 1 w + 1 w & \leq & 75
126 \end{cases}
127 \)
128
129 #\(\begin{bmatrix}120&210\\110&30\\1 &
130 #1\end{bmatrix}\;\begin{bmatrix}w\\b\end{bmatrix}
131 #\leq \begin{bmatrix}\$15000\\4000\text{ bushels}\\75\text{ acres}\end{bmatrix}\)
132
133 ** Solution using LP Solve 105 ** Solution using LP Solve
134 #(LP solve is available at http://www.example.com.)
135 In a new file, =farmer.lp=, we list the variables and constraints 106 In a new file, =farmer.lp=, we list the variables and constraints
136 of our problem using LP Solve syntax. 107 of our problem using LP Solve syntax.
137 108
138 #+begin_src lpsolve :tangle ../lp/farmer.lp 109 #+begin_src lpsolve :tangle ../lp/farmer.lp
139 /* Maximize Total Profit */ 110 /* Maximize Total Profit */