Linear Programming & Games Uni Notes Part I

linear Programming and Games

vectors

e
y iff every ith entry of is e every im entry
of g

Matrices

A is the transpose
of A

Dot product

a 8 b are n dimensional vectors their dot product is
Ig
given by


9 bi 92 bz t t Un bn



we write this as a the




inn
f



bn

Definition

A linear combination a an is an
of expression of form
A Xr t g Iz t Andn
r n
7



real numbers

, can equivalently write this at a


we can also do linear combinations vector
of

C Y A I z t 92 I z t t Un I n




Form matrix X whose
a
jth row is
Then Xa gives a linear combination
of s weighed by a


Loon at the ith entry of Xa



Xa i Xi a t Xi z ar t t Xi n an


Note this combination is the same all entries
for

similarly at X is a linear combination
of the rows
of
Linear Equations t Inequalities
we call an expression the form
of
A X t t an Xn b ie a linear equation
or ate b

,ive can a x t an xn E b linear inequalities
a X t t an xn Z b



e 3I t 2 Z 7 4
g 2 xz

3x t 2 z 7 x Z 4 V a linear inequality

Linear Programs


A mathematical optimisation
program has
11 A set
of
decision variables t sign restrictions

2 An objective function that assigns a value to each

setting of the variables
31 A good Imax or mint
41 A set constraints given as inequality equations
of

e
g maximise sit Sy
subject to 1a E l


Z 15
y
a E O

unrescricted
y is
A note about restrictions

and Ed
suppose u E b c

, it at c at c s b td
cit ax I x z o then ax E bx
nothing f
x then
If so ax 2 b x




optimise the amount
to
of fertiliser
ensure the plant
survives


A linear program is a mathematical program in which



the variables are continuous quantities

the junction is a linear combination
objective
The constraints are all linear
equations or linear inequalities