-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path1-graphical_eg.Rmd
140 lines (113 loc) · 5.06 KB
/
1-graphical_eg.Rmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
# Graphical example {#graphic}
To motivate the subject of linear programming (LP), we begin
with a planning problem that can be solved graphically.
Say you are a vendor of lemonade and lemon juice.
Each unit of lemonade requires 1 lemon and 2 litres of water.
Each unit of lemon juice requires 3 lemons and 1 litre of water.
Each unit of lemonade gives a profit of three dollars.
Each unit of lemon juice gives a profit of two dollars.
You have 6 lemons and 4 litres of water available.
How many units of lemonade and lemon juice should you
make to maximize profit?
If we let \(x\) denote the number of units of lemonade to be made
and let \(y\) denote the number of units of lemon juice to be made,
then the profit is given by \(3x + 2y\) dollars.
We call \(3x + 2y\) the objective function.
Note that there are a number of
constraints that \(x\) and \(y\) must satisfied.
First of all, \(x\) and \(y\) should be nonnegative.
The number of lemons needed to make \(x\) units of lemonade
and \(y\) units of lemon juice is \(x+3y\) and cannot exceed 6.
The number of litres of water needed to make \(x\) units of lemonade
and \(y\) units of lemon juice is \(2x+y\) and cannot exceed 4.
Hence, to determine the maximum profit, we need to
maximize \(3x + 2y\) subject to \(x\) and \(y\) satisfying
the constraints
\(x + 3y \leq 6\),
\(2x + y \leq 4\),
\(x \geq 0\), and \(y \geq 0.\)
A more compact way to write the problem is as follows:
\[\begin{array}{rrcrll}
\mbox{maximize } & 3x & + & 2y & \\
\mbox{subject to}
& x & + & 3y & \leq & 6 \\
& 2x & +& y & \leq & 4 \\
& x & & & \geq & 0 \\
& & & y & \geq & 0. \\
\end{array}\]
We can solve this maximizationproblem graphically as follows.
We first sketch the set of \(\begin{bmatrix} x\\ y\end{bmatrix}\)
satisfying the constraints, called the feasible region,
on the \((x,y)\)-plane.
We then take the objective function \(3x+2y\) and turn it into
an equation of a line \(3x+2y = z\) where \(z\) is a parameter.
Note that as the value of \(z\) increases,
the line defined by the equation
\(3x+2y=z\) moves in the direction of the normal vector
\(\begin{bmatrix} 3 \\ 2\end{bmatrix}\). We call this direction
the direction of improvement.
Determining the maximum value of the objective function, called
the optimal value, subject
to the contraints amounts to finding the maximum value of \(z\)
so that the line defined by the equation
\(3x+2y=z\) still intersects the feasible region.
```{r svgtest, echo = FALSE, out.width ='80%', fig.align='center'}
knitr::include_graphics("images/lemon.svg")
```
In the figure above, the lines
with \(z\) at 0, 4 and 6.8 have been drawn.
From the picture,
we can see that if \(z\) is greater than 6.8, the
line defined by \(3x+2y = z\) will not intersect the feasible region.
Hence, the profit cannot exceed 6.8 dollars.
As the line \(3x+2y = 6.8\) does intersect the feasible region,
\(6.8\) is the maximum value for the objective function.
Note that there is only one point in the feasible region that
intersects the line \(3x+2y=6.8\), namely
\(\begin{bmatrix} x \\ y\end{bmatrix} =
\begin{bmatrix} 1.2 \\ 1.6\end{bmatrix}.\)
In other words, to maximize profit,
we want to make 1.2 units of lemonade and 1.6 units of lemon juice.
The above solution method can hardly be regarded as rigorous because we
relied on a picture to conclude that \(3x + 2y \leq 6.8\) for all
\(\begin{bmatrix} x\\y\end{bmatrix}\) satisfying the constraints.
But we can actually show this *algebraically*.
Note that multiplying both sides of the constraint \(x + 3y \leq 6\) gives
\(0.2x + 0.6 y \leq 1.2\), and
multiplying both sides of the constraint \(2x + y \leq 4\) gives
\(2.8x + 1.4 y \leq 5.6\).
Hence, any \(\begin{bmatrix} x\\y\end{bmatrix}\) that satisfies both
\(x+3y\leq 6\) and \(2x+y \leq 4\) must also satisfy
\((0.2x+0.6y) + (2.8x+1.4y) \leq 1.2 + 5.6\), which simplifies
to \(3x + 2y \leq 6.8\) as desired! (Here, we used the fact that
if \(a \leq b\) and \(c \leq d\), then \(a+c \leq b+d\).)
Now, one might ask if it is always possible to find an algebraic proof like
the one above for similar problems.
If the answer is yes, how does one find such a proof?
We will see answers to this question later on.
Before we end this segment, let us consider the following problem:
\[\begin{array}{rrcrll}
\mbox{minimize } & -2x & + & y & \\
\mbox{subject to} & -x & + & y & \leq & 3 \\
& x & - & 2y & \leq & 2 \\
& x & & & \geq & 0 \\
& & & y & \geq & 0. \\
\end{array}\]
Note that for any \(t \geq 0\),
\(\begin{bmatrix} x \\ y\end{bmatrix} =
\begin{bmatrix} t \\ t\end{bmatrix}\)
satisfies all the constraints.
The value of the objective function at
\(\begin{bmatrix} x \\ y\end{bmatrix} =
\begin{bmatrix} t \\ t\end{bmatrix}\)
is \(-t\).
As \(t \rightarrow \infty\), the value of
the objective function tends to \(-\infty\).
Therefore, there is no minimum value for the objective function.
The problem is said to be unbounded.
Later on, we will see how to detect
unboundedness algorithmically.
As an exercise, check that unboundedness can also be established by using
\(\begin{bmatrix} x \\ y\end{bmatrix} =
\begin{bmatrix} 2t+2 \\ t\end{bmatrix}\)
for \(t \geq 0\).