about summary refs log tree commit diff
path: root/usth/MATH2.4/labwork/5/report.tex
blob: 16daad0d77b83d9173216d501abc2f6eabc0fe38 (plain) (blame)
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
\documentclass[a4paper,12pt]{article}
\usepackage[english,vietnamese]{babel}
\usepackage{amsmath}
\usepackage{booktabs}
\usepackage{enumerate}
\usepackage{lmodern}
\usepackage{siunitx}
\usepackage{tikz}

\newcommand{\exercise}[1]{\noindent\textbf{#1.}}

\title{Numerical Methods: Linear Programming}
\author{Nguyễn Gia Phong--BI9-184}
\date{\dateenglish\today}

\begin{document}
\maketitle

Given the production contraints and profits of two grades of heating gas
in the table below.
\begin{center}
  \begin{tabular}{l c c c}
    \toprule
    & \multicolumn{2}{c}{Product}\\
    Resource & Regular & Premium & Availability\\
    \midrule
    Raw gas (\si{\cubic\metre\per\tonne}) & 7 & 11 & 77\\
    Production time (\si{\hour\per\tonne}) & 10 & 8 & 80\\
    Storage (\si{\tonne}) & 9 & 6\\
    \midrule
    Profit (\si{\per\tonne}) & 150 & 175\\
    \bottomrule
  \end{tabular}
\end{center}

\begin{enumerate}[(a)]
  \item Let two nonnegative numbers $x_1$ and $x_2$ respectively be
    the quantities in tonnes of regular and premium gas to be produced.
    The constraints can then be expressed as
    \[\begin{cases}
      7x_1 + 11x^2 &\le 77\\
      10x_1 + 8x_2 &\le 80\\
      x_1 &\le 9\\
      x_2 &\le 6
    \end{cases}
    \iff \begin{bmatrix}
      7 & 11\\
      10 & 8\\
      1 & 0\\
      0 & 1
    \end{bmatrix}\begin{bmatrix}
      x_1\\ x_2
    \end{bmatrix}
    \le \begin{bmatrix}
      77\\ 80\\ 9\\ 6
    \end{bmatrix}\]

    The total profit is the linear function to be maximized:
    \[\Pi(x_1, x_2) = 150x_1 + 175x_2 = \begin{bmatrix}
      150\\ 175
    \end{bmatrix}\cdot\begin{bmatrix}
      x_1\\ x_2
    \end{bmatrix}\]

    Let $\mathbf x = \begin{bmatrix}
      x_1\\ x_2
    \end{bmatrix}$, $A = \begin{bmatrix}
      7 & 11\\
      10 & 8\\
      1 & 0\\
      0 & 1
    \end{bmatrix}$, $\mathbf b = \begin{bmatrix}
      77\\ 80\\ 9\\ 6
    \end{bmatrix}$ and $\mathbf c = \begin{bmatrix}
      150\\ 175
    \end{bmatrix}$, the canonical form of the problem is
    \[\max\left\{\mathbf c^\mathrm T
                 \mid A\mathbf x\le b\land\mathbf x\ge 0\right\}\]
  \item Due to the absense of \verb|linprog| in Octave, we instead use GNU GLPK:
\begin{verbatim}
octave> x = glpk (c, A, b, [], [], "UUUU", "CC", -1)
x =
   4.8889
   3.8889
\end{verbatim}
    Contraint type \verb|UUUU| is used because all contraints are inequalities
    with an upper bound and \verb|CC| indicates continous values of $\mathbf x$.
    With the sense of -1, GLPK looks for the maximization\footnote{I believe
    \emph{minimization} was a typo in the assignment, since it is trivial that
    $\Pi$ has the minimum value of 0 at $\mathbf x = \mathbf 0$.} of
    $\Pi(4.8889, 3.8889) = 1413.9$.

    The two blank arguments are for the lower and upper bounds of $\mathbf x$,
    default to zero and infinite respectively.  Alternatively we can use
    the following to obtain the same result
\begin{verbatim}
glpk (c, [7 11; 10 8], [77; 80], [], [9 6], "UU", "CC", -1)
\end{verbatim}

  \item Within the constrains, the profit can be calculated using the following
    function, which takes two meshes of $x$ and $y$ as arguments
\begin{verbatim}
function z = profit (x, y)
  A = [7 11; 10 8];
  b = [77; 80];
  c = [150; 175];
  [m n] = size (x);
  z = -inf (m, n);
  for s = 1 : m
    for t = 1 : n
      r = [x(s, t); y(s, t)];
      if A * r <= b
        z(s, t) = dot (c, r);
      endif
    endfor
  endfor
endfunction
\end{verbatim}

    Using this, the solution space is then plotted using \verb|ezsurf|,
    which color each grid by their relative values (the smallest is dark purple
    and the largest is bright yellow):
\begin{verbatim}
ezsurf (@(x1, x2) constraints (x1, x2), [0 9 0 6], 58)
\end{verbatim}
\pagebreak

    Since the plot is just a part of a plane, we can rotate it for a better view
    without losing any information about its shape.

    \scalebox{0.69}{\input{profit.tikz}}
\end{enumerate}
\end{document}