\documentclass[a4paper,12pt]{book}
%\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage[english]{babel}
\usepackage[utf8]{vietnam}
\usepackage{color}
\usepackage{graphicx}
\usepackage{amsmath,amsfonts,amsthm,epsfig,hyperref}
\newenvironment{dedication}
{
   \cleardoublepage
   \thispagestyle{empty}
   \vspace*{\stretch{1}}
   \hfill\begin{minipage}[t]{0.66\textwidth}
   \raggedright
}
{
   \end{minipage}
   \vspace*{\stretch{3}}
   \clearpage
}

\newtheorem{thm}{Định lý}[section]
\newtheorem{prop}[thm]{Mệnh đề}
\newtheorem{lem}[thm]{Bổ đề}
\newtheorem{result}[thm]{Kết quả}
\newtheorem{rem}[thm]{Chú ý}
\newtheorem{cor}[thm]{Hệ quả}
\newtheorem{proper}[thm]{Tính chất}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Định nghĩa}
\newtheorem{exm}{Ví dụ}[chapter]

\newtheorem{prob}{Bài tập}
\newcommand{\thmref}[1]{Định lý~{\rm \ref{#1}}}
\newcommand{\lemref}[1]{Bổ đề~{\rm \ref{#1}}}
\newcommand{\corref}[1]{Hệ quả~{\rm \ref{#1}}}
\newcommand{\propref}[1]{Mệnh đề~{\rm \ref{#1}}}
\newcommand{\defnref}[1]{Định nghĩa~{\rm \ref{#1}}}
\newcommand{\remref}[1]{Chú ý~{\rm \ref{#1}}}
\newcommand{\exmref}[1]{Ví dụ~{\rm \ref{#1}}}

\makeatletter
\renewcommand{\@chapapp}{}% Not necessary...
\newenvironment{chapquote}[2][2em]
  {\setlength{\@tempdima}{#1}%
   \def\chapquote@author{#2}%
   \parshape 1 \@tempdima \dimexpr\textwidth-2\@tempdima\relax%
   \itshape}
  {\par\normalfont\hfill--\ \chapquote@author\hspace*{\@tempdima}\par\bigskip}
\makeatother

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% First page of book which contains 'stuff' like: %
%  - Book title, subtitle                         %
%  - Book author name                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Book's title and subtitle
\title{\Huge \textsc{đề cương bài giảng: xác suất thống kê và toán kinh tế}\\
%  \footnote{This is a footnote.} \\
}
% Author
\author{}
\date{}

\begin{document}
\frontmatter
\maketitle
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Add a dedication paragraph to dedicate your book to someone %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{dedication}
Let your light so shine before men, that they may see your good
works, and glorify your Father which is in heaven (Matthew 5:16).
\end{dedication}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Auto-generated table of contents, list of figures and list of tables %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\tableofcontents
%\listoffigures
%\listoftables

\mainmatter

%%%%%%%%%%%
% Preface %
%%%%%%%%%%%
\chapter*{Thông tin về học phần}
\vskip.1in
\begin{tabular}{ | p{4cm}  | p{10cm} |}
    \hline
Tên học phần: & Xác suất thống kê và toán kinh tế (Probability, Statistics and Mathematical Economics)\\ \hline
Mã số học phần: & MAT20007  \\ \hline
Thuộc khối kiến thức/kỹ năng:& Kiến thức cơ sở ngành  \\ \hline
Số tín chỉ:& 04  \\ \hline
Số tiết lý thuyết:& 48  \\ \hline
Số tiết thảo luận/bài tập:& 12  \\ \hline
Số tiết thực hành: & 0  \\ \hline
Số tiết hoạt động nhóm: & 0  \\ \hline
Số tiết tự học: & 120  \\ \hline
Môn học tiên quyết: & Toán cao cấp cho các nhà kinh tế  \\ \hline
Môn học song hành: & Không   \\ \hline
    \end{tabular}
\vskip.1in


\chapter{Xác suất của biến cố và phân phối xác suất}

\begin{chapquote}{
    Japanese Proverb, \textit{http://quotationsbook.com}}
``Better than a thousand days of diligent study is one day with a
great teacher.''
\end{chapquote}


\section*{Giới thiệu}\label{Int11}




Cho đến nửa đầu thế kỷ hai mươi, lý thuyết xác suất mới trở nên một
khoa học được xây dựng chặt chẽ bằng hệ tiên đề Kolmogorov. Cho đến
nay, lý thuyết xác suất được ứng dụng vào rất nhiều ngành khoa học
khác nhau, trong đó có các ví dụ điển hình như sau:

\begin{itemize}

\item{} Lý thuyết xác suất được sử dụng trong di truyền học như là
một mô hình cho sự đột biến và đóng một vai trò quan trọng trong
ngành tin-sinh.

\item{} Nhiều ngành lý thuyết phát triển cao xem các loại nhiễu
trong các thiết bị điện tử và hệ thống giao tiếp như là các quá
trình ngẫu nhiên.

\item{} Rất nhiều các mô hình trong nghiên cứu biến đổi khí quyển sử
dụng các khái niệm của lý thuyết xác suất.

\item{} Xác suất đóng vai trò nền tảng của ngành lý thuyết tài
chính.

\item{} Xác suất được sử dụng để nghiên cứu các hệ thống phức hợp và
cải tiến độ tin cậy của các hệ thống đó, ví dụ như các hệ thống
trong thương mại hiện đại hoặc không quân.

\end{itemize}


Trong chương này chúng ta sẽ nghiên cứu các khái niệm cơ bản
của lý thuyết xác suất như không gian mẫu, biến cố ngẫu nhiên, độ đo
xác suất, xác suất có điều kiện, và tính độc lập. Qua đó, chúng ta
sẽ từng bước xây dựng nên mô hình toán học cho các hiện tượng
ngẫu nhiên và tính xác suất của các biến cố, xác suất có điều kiện
thông qua các công thức tính xác suất như công thức
cộng xác suất, công thức nhân xác suất,
công thức xác suất toàn phần và công thức Bayes. Bên cạnh đó, chương này cũng giới thiệu
 những kiến thức cơ bản về biến ngẫu nhiên, vector ngẫu nhiên, hàm phân phối,
các phân phối xác suất quan trọng và các đặc trưng của biến ngẫu nhiên như kỳ vọng, phương sai và độ lệch tiêu chuẩn.


\chapter{Thống kê và các suy luận thống kê}


\section*{Giới thiệu}\label{Int11}

Trong Chương 1, chúng ta đã nghiên cứu về các bài toán mang yếu tố ngẫu nhiên.
Dựa vào các kiến thức của Chương 1, chúng ta sẽ nghiên cứu các bài toán của thống kê toán học và xử lý số liệu.

Thống kê toán học là khoa học nghiên cứu các phương pháp thu thập, phân tích, xử lý các số liệu
để đưa ra các suy luận có cơ sở khoa học phục vụ cho việc quản lý tự nhiên, xã hội.

Nội dung chính của chương này bao gồm:

\begin{itemize}
  \item Mẫu ngẫu nhiên
  \item Bài toán ước lượng tham số
  \item Bài toán kiểm định giả thuyết
  \item Bài toán phân tích tương quan và hồi quy.
\end{itemize}






\chapter{Một số mô hình toán kinh tế}

\section*{Giới thiệu}\label{Int11}
Trong Chương này, chúng ta sẽ vận dụng các kiến thức của lý thuyết
xác suất, thống kê, đại số tuyến tính và quy hoạch tuyến tính để nghiên cứu một số
mô hình toán kinh tế. Nội dung của chương bao gồm:

$\bullet$ Một số mô hình toán kinh tế điển hình như mô hình lập kế hoạch sản xuất,
mô hình bài toán vận tải, mô hình bài toán khẩu phần thức ăn, mô hình bài toán lập kế hoạch kinh doanh, mô hình bài toán sản xuất đồng bộ, mô hình bài toán cân đối liên ngành, mô hình bài toán đầu tư thị trường chứng khoán.

$\bullet$ Bài toán quy hoạch tuyến tính.

$\bullet$ Phương pháp đơn hình giải bài toán quy hoạch tuyến tính.

$\bullet$ Mô hình bài toán vận tải.

\section*{Chuẩn đầu ra của chương}


\vskip.1in
\begin{tabular}{ | p{2cm}  | p{8cm} | p{2cm}  |}
    \hline
Mục tiêu & Mô tả CĐR & Mức độ giảng dạy\\ \hline
G1.3 & Nắm vững nội dung và phương pháp giải bài toán quy hoạch tuyến tính, các mô hình toán kinh tế điển hình. & T,U  \\ \hline
G2.7 & Vận dụng các kiến thức về xác suất, thống kê, quy hoạch tuyến tính vào giải quyết một số mô hình toán kinh tế như bài toán lập kế hoạch sản xuất, bài toán vận tải, bài toán khẩu phần thức ăn, bài toán quyết định tối ưu và các mô hình khác nảy sinh trong thực tế ngành kinh tế. & U  \\ \hline
G3.1 & Có thái độ tích cực hợp tác với giáo viên và các sinh viên khác trong quá trình học và làm bài tập. & T  \\ \hline
G3.2 & Phân công công việc trong một nhóm bài tập một cách hiệu quả. & U  \\ \hline
G3.3 & Có khả năng thuyết trình các vấn đề tự học ở nhà và báo cáo kết quả làm việc của bản thân và của nhóm. & U  \\ \hline
    \end{tabular}

\vskip.3in

\section*{Nội dung của chương}
\section{Bài toán quy hoạch tuyến tính}
\subsection{Mở đầu}
Trong thực tế, khi tiến hành kế hoạch hóa sản xuất, điều khiển hệ thống và thiết kế kỹ thuật chúng ta luôn hướng đến một mục đích tiết kiệm được vốn, sức lao động, thời gian và tăng hiệu quả giải quyêt các vấn đề được đặt ra. Vấn đề đặt ra là: "\emph{Làm thế nào để con người chúng ta tối đa hóa được hiệu quả giải quyết của các vấn đề được đặt ra trong điều kiện hiện có các yếu tố về vật chất, khoa học kỹ thuật và nhân sự,\ldots}".
\par Vào những năm $40$ của thế kỷ $XX$ những vấn đề lý luận để giải quyết các bài toán tối ưu hóa được đặt ra mới được quan tâm nghiên cứu một cách có khoa học. Năm $1939$,  nhà toán học người Nga, Leonid Vitaliyevich Kantorovich $(1912-1986)$ đã công bố kết quả nghiên cứu về các phương pháp toán  học trong tổ chức và quy hoạch sản xuất. Kantorovich đã chỉ ra rằng, có rất nhiều các mô hình trong thực tế đều có thể mô hình hóa bởi một dạng mô hình toán học. Tuy vậy,  các kết quả của Kantonovich đã không được công nhận ở thời đó. Năm $1941$ Frank Hitchcock [3] đã ứng dụng ý tưởng này trong nghiên cứu các bài toán về giao thông vận tải. Năm $1945$, George Stigler đã vận dụng lý thuyết này để xác lập khẩu phần ăn cho mỗi cá nhân với chi phí tối thiểu. Thông qua những kết quả nghiên cứu này, đặc biệt là trong các bài toán điều binh trong chiến tranh thế giới thứ hai, đã cho người  ta  thấy rõ ý nghĩa của lý thuyết quy hoạch toán học trong  việc giải quyết các bài toán tối ưu hóa trong thực tiễn. Sau đó, năm $1951$, George Dantzig đã đưa ra phương pháp đơn hình để giải bài toán quy hoạch tuyến tính được đề xuất bởi Kantorovich.
 Với ý nghĩa to lớn của lý thuyết quy hoạch tuyến tính trong việc tối ưu hóa các mô hình trong thực tế Kantorovich đã được nhận giải thưởng Nobel về kinh tế năm $1975$.
 \par \underline{\textbf{Bài toán toán tối ưu hóa tổng quát được phát biểu như sau:}}
\par Tìm $x=(x_1, x_2, \ldots, x_n)$ làm cạc đại hóa (cự tiểu hóa) hàm f(x):
\begin{equation}\label{e1.1}f(x)\rightarrow\max (\min)\end{equation}
với các điều kiện
\begin{equation}\label{e1.2}
\begin{cases}
  g_i(x)(\leq, =,\geq) b_i& i=\overline{1,m}\\
  x\in X\subset   \mathbb{R}^n
\end{cases}
\end{equation}
Bài toán \eqref{e1.2} \eqref{e1.2} được gọi là một quy hoạch. Hàm $f(x)$ được gọi là hàm mục tiêu, các hàm $g_i(x),\; i=\overline{1, m}$ được gọi là các hàm ràng buộc, mỗi đẳng thức hoặc bất đẳng thức trong hệ \eqref{e1.2} được gọi là một ràng buộc. Tập hợp
\begin{equation}
  M=\{x\in \mathbb{R}^n|\text{thỏa mãn điều kiện \eqref{e1.2}}\}
\end{equation}
được gọi là tập các phương án. Mỗi điểm $x=(x_1, x_2,\cdots, x_n)\in M$ được gọi là một phương án (hay một lời giải chấp nhận được). Một phương án $x^*\in M$ là cực đại (hay cực tiểu) hàm mục tiêu, cụ thể là
$$f(x^*)\geq f(x),\;\;\forall \, x\in M\;\;\text{đối với bài toán } \max$$
$$f(x^*)\leq f(x),\;\;\forall \, x\in M\;\;\text{đối với bài toán } \min$$
được gọi là phương án tối ưu (hay lời giải của bài toán). Khi đó, $f(x^*)$ được gọi là giá trị tối ưu của bài toán.
\\
\textbf{\underline{Phân loại các bài toán}}
\par - Nếu cả hàm mục tiêu $f(x)$ và hàm ràng buộc $g_i(x), \, i=\overline{1, m}$ đều là những hàm tuyến tính ta có \emph{bài toán quy hoạch tuyến tính}.
\par - Nếu hàm mục tiêu  $f(x)$ hoặc hàm ràng buộc $g_i(x), \, i=\overline{1, m}$ phụ thuộc tham số ta có \emph{bài toán quy hoạch tham số}.
\par - Nếu quá trình ta xét là quá trình nhiều gia đoạn nói chung, hay quá trình phts triển theo thời gian nói riêng thì ta có \emph{bài toán quy hoạch động}.
\par - Nếu hàm mục tiêu  $f(x)$ hoặc hàm ràng buộc $g_i(x), \, i=\overline{1, m}$ là hàm phi tuyến ta có \emph{bài toán quy hoạch phi tuyến}.
\par - Nếu tập phương án là tập rời rạc  ta có \emph{bài toán quy hoạch rời rạc}. Nếu tập phương án chỉ nhận các giá trị nguyên ta có \emph{bài toán quy hoạch nguyên.}
\par - Nếu trên cùng một tập phương án ta xét các hàm mục tiêu khác nhau ta có  \emph{bài toán quy hoạch đa mục tiêu}.
\subsection{Bài toán quy hoạch tuyến tính}\label{sec1.2}
%Trong mục này, chúng tôi sẽ trình bày một số mô hình trong thực tế và xây dựng mô hình toán học cho các mô hình đó.
%\par Để giải quyết bài toán trong thực tế bằng phương pháp toán học chúng ta cần phải thực hiện 4 bước sau:
%%\begin{itemize}
%  %\item
%  \par \textbf{\underline{Bước 1}}\;  (\emph{Nhận diện mô hình}): Xây dựng mô hình định tính cho mô hình thực tế, tức là xác định các yếu tố có ý nghĩa quan trong nhất và xác lập quy luật mà nó tuân theo (xác định các yếu tố đầu vào, các điều kiện đặt ra, mục tiêu hướng tới ...).
%  %\item
%   \par\underline{\textbf{Bước 2}}\; (\emph{Xây dựng mô hình toán}): Diễn tả mô hình thực tế bằng ngôn ngữ toán học xác định hàm mục tiêu từ các điều kiện  và mục tiêu của mô hình; xây dựng các ràng buộc toán học mà các biến số phải tuân theo dựa vào các điều kiện buộc của các biến số trong mô hình.
%  %\item
%   \par\underline{\textbf{Bước 3}} (\emph{Giải mô hình}):  Sử dụng các phương pháp biến đổi logic của  toán học để khảo sát giải bài toán được thiết lập từ bước 2.
%     % \item
%      \par\textbf{\underline{Bước 4}} (\emph{Phân tích mô hình và dự báo}): Dựa trên kết quả giải được ở bước 3 chúng ta xác định mức độ phù hợp giữa kết quả toán học với mô hình thực tế. Từ đó đưa ra các dự báo để điều chỉnh mô hình và quản trị các mô hình trong thực tế.
%%\end{itemize}
%Sau đây là một số mô hình trong thực tế.
%Chúng ta xét bài toán kế hoạch sản xuất với tình huống cụ thể sau.
%\begin{exm}[Bài toán kế hoạch sản xuất]\label{vd1.2.1}
%  Một xí nghiệp dự định sản xuất 2 loại sản phẩm $A$ và $B$ từ 3 loại nguyên liệu $I, II, III.$ Để sản xuất một đơn vị sản phẩm $A$ cần dùng $2$ đơn vị nguyên liệu loại $I$, $1$ đơn vị nguyên liệu loại $III$; tiền lãi thu được là $3$ đơn vị tiền. Để sản xuất 1 đơn vị  sản phẩm $B$, cần dùng $1$ đơn vị nguyên liêu loại $I$, $1$ đơn vị nguyên liệu loại $II$; tiền lại thu được là $5$ đơn vị tiền. Biết rằng lượng dự trử từng loại nguyên liệu tối đa có trong kho lần lượt là $8, 4, 3$ đơn vị. Hỏi xí nghiệp nên có kế hoạch sản xuất như thế nào để thu được tiền lãi lớn nhất mà không bị thiếu nguyên liệu.
%  \\ \underline{\emph{Thiết lập mô hình}:}
%\par Gọi $x$ là lượng sản phẩm  A được sản xuất ($x\geq 0$).  Gọi $y$ là lượng sản phẩm  B được sản xuất ($y\geq 0$). Khi đó,
%\begin{itemize}
%  \item Tiền lãi thu được là
%$f(x,y)=3x+5y$
%  \item Lượng nguyên liệu loại $I$ phải sử dụng là
%  $2x+y\leq 8.$
%  \item Lượng nguyên liệu loại $II$ phải sử dụng là
%  $y\leq 4.$
%  \item Lượng nguyên liệu loại $III$ phải sử dụng là
%  $x\leq 3.$
%  \end{itemize}
%Vậy ta có bài toán thể hiện kế hoạch sản xuất của xí nghiệp là
%\begin{equation}
%  \max\{f(x,y)=3x+5y\},
%\end{equation}
%\begin{equation}
%\text{với điều kiện}
%  \begin{cases}
%    2x+y\leq 8 \\y\leq 4\\x\leq 3 \\ x, y\geq 0.
%  \end{cases}
%\end{equation}
% \end{exm}
 %Tiếp theo chúng ta xét bài toán tổng quát cho bài toán kế hoạch sản xuất
\begin{exm}[Bài toán về kế hoạch sản xuất]\label{vd1.2.2} Một xí nghiệp dự định sản xuất $n$ loại sản phẩm từ $m$ loại nguyên liệu khác nhau. Để sản xuất 1 đơn vị sản phẩm loại j cần dùng $a_{ij}\; (i=\overline{1, m})$  đơn vị nguyên liệu loại $i$ và tiền lãi thu được là $c_j$ đơn vị tiền. Biết rằng nguyên liệu loại $i$ được cung cấp tối đa là $b_i,\, (i=\overline{1, m})$ và lượng sản phẩm được sản xuất ra đều được tiêu thụ hết. Hãy cho biết xí nghiệp nên có kế hoạch sản xuất như thế nào để thu được tiền lãi lớn nhất với điều kiện cung cấp nguyên liệu thực tế.
\\ \underline{\emph{Thiết lập mô hình}:}
\par Gọi $x_j$ là lượng sản phẩm loại $j\, (j=\overline{1, n})$ mà xí nghiệp sản xuất ($x_j\geq 0$). Khi đó,
\begin{itemize}
  \item Tiền lãi thu được là
  $f(x_1,x_2,\ldots,x_n)=\sum_{j=1}^nc_jx_j.$
  \item Lượng nguyên liệu loại $i$ phải sử dụng là
  $\sum_{j=1}^na_{ij}x_j\leq b_i\;\;i=\overline{1, m}.$
  \end{itemize}
Vậy ta có bài toán thể hiện kế hoạch sản xuất của xí nghiệp là
\begin{equation}
  \max\{f(x_1,x_2,\ldots,x_n)=\sum_{j=1}^nc_jx_j\}
\end{equation}
\begin{equation}
\text{với điều kiện}  \begin{cases}
    \sum\limits_{j=1}^na_{ij}x_j\leq b_i\;\;i=\overline{1, m}
    \\ x_j\geq 0, \;\, j=\overline{1, n}
  \end{cases}
\end{equation}
\end{exm}
$\bullet$\; Nếu bổ sung vào bài toán các điều kiện: sản phẩm loại $j$ được sản xuất ra chỉ bán được $\alpha_j\%$  và mỗi đơn vị sản phẩm loại $j$  tồn kho xí nghiệp phải bỏ ra $\beta_j$ đơn vị tiền để tiêu hủy. Khi đó, hàm mục tiêu sẽ bị thay đổi và ta có bài toán sau
\begin{equation}
  \max\Big\{f(x_1,x_2,\ldots,x_n)=\frac1{100}\sum_{j=1}^nc_j\alpha_jx_j-\frac1{100}\sum_{j=1}^n\beta_j(100-\alpha_j)x_j
  \Big\}
\end{equation}
\begin{equation}
\text{với điều kiện}
  \begin{cases}
    \sum\limits_{j=1}^na_{ij}x_j\leq b_i\;\;i=\overline{1, m}
    \\ x_j\geq 0, \;\, j=\overline{1, n}
  \end{cases}
\end{equation}
%\par $\bullet$\; Bài toán kế hoạch sản xuất được ứng dụng vào rất nhiều ngành sản xuất khác nhau của nền kinh tế. Mỗi ngành khác nhau có các điều kiện của các biến số trong mô hình khác nhau nên chúng ta sẽ có được các điều kiện buộc trong mô hình toán khác nhau. Sau đây chúng tôi xét ứng dụng trong ngành luyện kim.
%\\ \emph{\underline{Bài toán chọn liệu lò để luyện gang}}
%\par Bài toán chọn thành phần hợp lý liệu lò thuộc về lớp bài toán quy hoạch tuyến tính có tên gọi là "Bài toán về hỗn hợp". Liệu lò tối ưu sẽ giải thích được một cách hợp lý cái hỗn hợp rẻ nhất mà thành phần hóa học của nó đáp ứng được những tính chất định trước. Liệu lò là sản phẩm đầu vào để luyện kim loại. Thành phần khác nhau của liệu lò quyết định quá trình công nghệ khác nhau của việc luyện. Vì thế cần chọn một giá trị kim loại được luyện nhờ chỉ số chất lượng của liệu lò.
%\par Ta xét quá trình sản xuất kim loại không phải như việc luyện nó từ hỗn hợp những chất liệu lò khác nhaumaf như là sự trộn những kim loại thành phần hóa học khác nhau, trong đó mỗi loại ấy được xem như được luyện từ một loại liệu lò. Bởi vậy ta gọi đây là \emph{bài toán hoàn nguyên}.
%\par Trong thành phần những liệu lò có những quặng sắt với chủng loại và nhãn hiệu khác nhau, gỉ sắt, xỉ lò Mactanh, thép vụn, \ldots những liệu lò khác nhau xác định thành phần hóa học khác nhau của gang luyện. Trong gang chất lượng, số phần trăm lưu huỳnh, mangan, phootpho và một vài nguyên tố khác không được vượt quá giá trị định trước, một loạt liệu lò là chất thải khâu khác của kỹ nghệ luyện kim (chẳng hạn xỉ lò Mactanh, gỉ sắt). Dự trử những thành phần này ràng buộc với việc sản xuất những khâu tương ứng. Cũng có cả  những hạn chế về kỹ thuật lên thành phần liệu lò xác định trong nạp liệu.
%\par Liệu lò tối ưu được coi là hợp phần của các liệu lò sao cho ứng với nó việc nấu gang rẻ nhất mà vẫn đảm bảo về thành phần hóa học. {\vhtime ở} đây cũng cần phải hạch toán những ràng buộc của những thành phần riêng biệt của liệu lò
  \begin{exm}[Bài toán vận tải]\label{vd1.2.3} Có $m$ nhà phân phối một loại hàng. Lượng hàng có thể cung cấp ở nhà phân phối $i, \; i=\overline{1, m}$ là $a_i.$ Cần phân phối loại hàng này đến $n$ cữa hàng tiêu thụ. Cữa hàng thứ $j, \; j=\overline{1, n} $ cần lượng hàng là $b_j.$ Cước phí vận chuyển 1 đơn vị hàng từ nhà phân phối $i$ đến cữa hàng $j$ là $c_{ij},\; \forall\, i=\overline{1, m}; j=\overline{1, n}.$ Hãy lập kế hoạch phân phối hàng sao cho tổng cước phí vận chuyển bé nhất sao cho các nhà phân phối phát hết hàng và các cữa hàng nhận đủ hàng.
      \\ \underline{\emph{Thiết lập mô hình}:}
\par Gọi $x_{ij}$ là lượng hàng được vận chuyển từ nhà phân phối  $i\, (i=\overline{1, m})$ đến cữa hàng $j  \,(j=\overline{1,n})$ ($x_{ij}\geq 0$). Khi đó,
\begin{itemize}
  \item Tổng cước phí vận chuyển là
  $f(x)=\sum_{i=1}^m\sum_{j=1}^nc_{ij}x_{ij}$
  \item Lượng mà nhà phân phối $i$ phát đi là
  $\sum_{j=1}^nx_{ij}= a_i\;\;i=\overline{1, m}.$
 \item Lượng mà cữa hàng $j$ nhận được là
  $\sum_{i=1}^mx_{ij}= b_j\;\;j=\overline{1, n}.$
  \end{itemize}
Vậy ta có bài toán thể hiện kế hoạch phân phối hàng là
\begin{equation}
  \min\{f(x)=\sum_{i=1}^m\sum_{j=1}^nc_{ij}x_{ij}\}
\end{equation}
\begin{equation}
\text{với điều kiện}  \begin{cases}
    \sum\limits_{j=1}^nx_{ij}= a_i\;\;i=\overline{1, m}\\
    \sum\limits_{i=1}^mx_{ij}= b_j\;\;j=\overline{1, n}
    \\ x_{ij}\geq 0, \;\, \forall\, i=\overline{1, m}, j=\overline{1, n}
  \end{cases}
\end{equation}
\end{exm}
\begin{exm}[Bài toán chiếc túi]\label{vd1.2.5} Một người đi du lich đem theo một chiếc túi. Người đó chỉ có thể mang chiếc túi nặng tối đa là $b$ kilogram. Có $n$ loại đồ vật mà anh ta dự định mang theo. Mỗi đồ vật loại $j$ có khối lượng là $a_j$ kilogram và có giá trị là $c_j,$ người du lịch muốn chất vào túi các đồ vật sao cho tổng giá trị đồ vật đem theo là lớn nhất. Hỏi người du lịch nên chọn đồ vật như thế nào để đạt được mục đích đặt ra.
\\ \underline{\emph{Thiết lập mô hình}:}
\par Gọi $x_j$ là số đồ vật loại $j\, (j=\overline{1, n})$ du khách xếp vào túi ($x_j\geq 0, x_j\in\mathbb{Z}$). Khi đó,
\begin{itemize}
  \item Giá trị đồ vật đem theo là
  $f(x_1,x_2,\ldots,x_n)=\sum_{j=1}^nc_jx_j.$
  \item Tổng khối lượng đồ vật là
  $\sum_{j=1}^na_{j}x_j\leq b.$
  \end{itemize}
Vậy ta có bài toán thể hiện kế hoạch chọn đồ vật bỏ vào túi là là
\begin{equation}
  \max\{f(x_1,x_2,\ldots,x_n)=\sum_{j=1}^nc_jx_j\}
\end{equation}
\begin{equation}
\text{với điều kiện}  \begin{cases}
    \sum_{j=1}^na_{j}x_j\leq b
    \\ x_j\geq 0, \;\, j=\overline{1, n}
    \\ x_j\in \mathbb{Z}, \;\, j=\overline{1, n}
  \end{cases}
\end{equation}
Đây là bài toán quy hoạch nguyên.
\end{exm}
Bài toán chiếc túi được áp dụng nhiều trong phân phối hàng hóa, còn được gọi là bài toán "\emph{người bán hàng}" chúng ta có thể phát biểu lại bài toán này trong tình huống của người bán hàng như sau:
\par Mộ người bán hàng cần vận chuyển các loại hàng đến các cữa hàng để phân phối. Trọng tải của chiếc xe, tối đa là $b$ tấn. Trong kho hàng có n loại hàng cần được đưa đi phân phối. Mỗi đơn vi hàng loại $j$ có khối lượng là $a_j$ kilogam và có giá trị là $c_j$ đơn vị tiền. Hỏi trong mỗi chuyến hàng nhà phân phối nên chuyên chở những loại hàng nào với số lượng là bao nhiêu để tổng giá trị mặt hàng phân phối là lớn nhất mà không vượt quá tải trong của chiếc xe.
\par Ví dụ sau đây thường xuất hiện trong các ngành hóa thực phẩm, chăn nuôi. Bài toán sẽ được nêu ra là khác nhau trong từng tình huống ứng dụng khác nhau, chẳng hạn để lập kế hoạch dài hạn cho việc phát triển công nghiệp ăn uống hoặc kế hoạch hóa việc phân phối thức ăn cho trẻ em ở các nhà trẻ, các đơn vị bộ đội, các bệnh viện điều dưỡng \ldots các bài toán sẽ khác nhau nêu chúng ta hạn chế, thêm bớt, thay đổi tiêu chuẩn đánh giá khẩu phần sẽ cho chúng ta những bài toán khác nhau. Sau đây là một ví dụ cho các tiêu chí cơ bản xác định khẩu phần ăn
\begin{exm}[Bài toán về khẩu phần thức ăn]\label{vd1.2.4} Một khẩu phần thức ăn có khối lượng $P$, có thể được cấu tạo từ $n$ loại thức ăn. Giá mua một đơn vị thức ăn loại $j$ là $c_j.$ Để đảm bảo cơ thể phát triển bình thường thì khẩu phần cần $m$ loại chất dinh dưỡng. Chất dinh dưỡng thứ $i$ cần tối thiểu cho khẩu phần là $b_i$, có trong một đơn vị thức ăn loại $j$ là $a_{ij}.$ Hỏi nên cấu tạo khẩu phần thức ăn như thế nào để ăn đủ no, đủ chất dinh dưỡng mà giá thành rẻ nhất.
\\ \underline{\emph{Thiết lập mô hình}:}
\par Gọi $x_{j}$ là số đơn vị thức ăn loại $j$ có trong khẩu phần($x_{j}\geq 0, \; j=\overline{1, n}$). Khi đó,
\begin{itemize}
  \item Giá thành của khẩu phần  là
  $f(x)=\sum_{j=1}^nc_{j}x_{j}$
  \item Lượng dinh dưỡng loại  $i$ có trong khẩu phần là
  $\sum_{j=1}^na_{ij}x_{j}\geq b_i\;\;i=\overline{1, m}.$
 \item Khối lượng của khẩu phần ăn là
  $\sum_{j=1}^nx_{j}= P$
  \end{itemize}
Vậy ta có bài toán thể hiện kế hoạch tạo khẩu phần ăn  là
\begin{equation}
  \min\{f(x)=\sum_{j=1}^nc_{j}x_{j}\}
\end{equation}
\begin{equation}\text{với điều kiện}
  \begin{cases}
   \sum\limits_{j=1}^nx_{j}= P\\
   \sum\limits_{j=1}^na_{ij}x_j\geq b_i\;\;i=\overline{1, m}
    \\ x_{j}\geq 0, \;\, \forall\, j=\overline{1, n}
  \end{cases}
\end{equation}
\end{exm}
Trong kế hoạch công nghiệp hóa và hiện đại hóa đất nước một trong những nhiệm vụ qua trong là phát triển nguồn năng lượng sạch, trong đó có năng lượng điện. Chúng ta đang phải xây dựng những dự án, tiêu chuẩn về những nhà máy thủy điện và nhiệt điện sử dụng dạng chất đốt khác nhau. Khi giải quyết các vấn đề về điện khí hóa của một vùng người ta cần phân bổ các kiểu nhà máy có khả năng thỏa mãn yêu cầu của vùng với chi tiêu nhỏ nhất. Chúng ta có thể hình dung thông qua ví dụ sau.
\begin{exm}[Quy hoạch nhà máy điện] Với điều kiện tự nhiên ở một  quốc gia  qua việc khảo sát cho thấy có khả năng xây dựng một kiểu nhà máy điện trong $n$ kiểu nhà máy điện. Việc bố trí hệ thống nhà máy phải đảm bảo công suất tiêu chuẩn là $A$, công suất đỉnh $B$ định trước, và mức sản xuất năng lượng cả năm định trước $C$. Chi tiêu cho xây dựng các nhà máy không vượt quá tổng cố định $D$.  Công suất tiêu chuẩn để đảm bảo cho một nhà máy kiểu $j$ là $a_j$; công suất đỉnh của nhà máy kiểu $j$ là $b_j$; năng lượng sản xuất được của 1 nhà máy kiểu $j$ là $c_j$ chi phí sử dụng cho việc vận hành 1 nhà máy kiểu j là $f_j$. Hãy cho biết nên bố trí mạng lưới nhà máy điện như thế nào để đảm bảo được  nhu cầu năng lượng của quốc gia mà chi phí vận hành ít nhất.
\\ \underline{\emph{Thiết lập mô hình}:}
\par Gọi $x_{j}$ là số nhà máy điện loại $j$ được xây dựng ($x_{j}\geq 0, \; j=\overline{1, n}$). Khi đó,
\begin{itemize}
  \item Tổng chi phí để vận hành là
  $f(x)=\sum_{j=1}^nc_{j}x_{j}.$
  \item Công suất tiêu chuẩn đạt được hang năm là
$\sum_{j=1}^na_{j}x_{j}\geq A.$
 \item Công suất đỉnh của hệ thống nhà máy là
  $\sum_{j=1}^nb_jx_{j}\geq B.$
  \item Năng lượng sản xuất được của mạng lưới là
  $\sum_{j=1}^nc_jx_{j}\geq C.$
  \item Chi phí xây dựng cơ bản là
    $\sum_{j=1}^nd_jx_{j}\leq D.$
  \end{itemize}
Vậy ta có bài toán thể hiện kế hoạch xây dựng mạng lưới nhà máy điện  là
\begin{equation}
  \min\{f(x)=\sum_{j=1}^nc_{j}x_{j}\}
\end{equation}
\begin{equation}
\text{với điều kiện}  \begin{cases}
   \sum\limits_{j=1}^na_{j}x_{j}\geq A\\
\sum\limits_{j=1}^nb_{j}x_{j}\geq B
    \\ \sum\limits_{j=1}^nc_{j}x_{j}\geq C
    \\ \sum\limits_{j=1}^nd_{j}x_{j}\leq D
    \\ x_{j}\geq 0, \;\, \forall\, j=\overline{1, n}
  \end{cases}
\end{equation}
\end{exm}
%\section{Bài toán quy hoạch tuyến tính}
%\subsection{Bài toán quy hoạch tuyến tính dạng tổng quát}
Các ví dụ trên cho ta một dạng bài toán giống nhau và đó chính là các bài toán quy hoạch tuyến tính. Dạng tổng quát của bài toán quy hoạch tuyến tính là
\begin{equation}
  \min(\max)\{f(x)=\sum_{j=1}^nc_{j}x_{j}\}
\end{equation}
\begin{equation}
\text{với điều kiện}\,\begin{cases}
   \sum\limits_{j=1}^na_{ij}x_{j}\geq b_i\;\forall \; i\in I_1\\
\sum\limits_{j=1}^na_{ij}x_{j}\leq b_i\;\forall \; i\in I_2
    \\ \sum\limits_{j=1}^na_{ij}x_{j}= b_i\;\forall \; i\in I_3
        \\ x_{j}\geq 0, \, \forall j\in J_1; \;x_{j}\leq 0, \, \forall j\in J_2;\,x_{j}\,\text{tùy ý},  \forall j\in J_3
  \end{cases}
\end{equation}
trong đó $I_1\cup I_2\cup I_3=\{1,2,3,\ldots m\};\; J_1\cup J_2\cup J_3=\{1,2,\ldots n\}.$
\begin{exm} Xét bài toán quy hoạch tuyến tính
\begin{equation}
  \min\{5x_1+3x_2-x_3\}
\end{equation}
\begin{equation}
\text{với điều kiện}\;  \begin{cases}
   x_1-2x_2+7x_3\geq 10\\
-x_1+3x_2+x_3\leq 15
    \\ x_1+x_2+10x_3=20 \\ x_{1}\geq 0, \;x_{2}\leq 0, \;x_{3}\;\text{tùy ý}.
  \end{cases}
\end{equation}
  \end{exm}
\subsection{Các dạng đặc biệt }
\subsubsection{Dạng chính tắc}
Dạng chính tăc của bài toán quy hoạch tuyến tính là
\begin{equation}\label{e2.20}
  \min\{f(x)=\sum_{j=1}^nc_{j}x_{j}\}
\end{equation}
\begin{equation}\label{e2.21}
\text{với điều kiện}  \begin{cases}
   \sum\limits_{j=1}^na_{ij}x_{j}= b_i\;\forall \; i=\overline{1,m}\\
        x_{j}\geq 0, \, \forall j=\overline{1,n}.
  \end{cases}
\end{equation}
Một bài toán quy hoạch tuyến tính luôn đưa về được dạng chính tắc theo quy tắc sau
\par +) Ta có\begin{equation*}
  \begin{cases}
   \max \{f(X)\}\\
        X\in M.
  \end{cases}\Leftrightarrow \begin{cases}
   \min \{-f(X)\}\\
        X\in M.
  \end{cases}
\end{equation*}
\par +) Nếu bài toán gốc có điều kiện $\sum\limits_{j=1}^na_{ij}x_j\leq b_i$ (hoặc $\sum\limits_{j=1}^na_{ij}x_j\geq b_i$) ta đưa thêm ẩn phụ $x_{n+i}$ với $c_{n+i}=0$ để có
$$\sum\limits_{j=1}^na_{ij}x_j+x_{n+i}= b_i\; (\text{tương ứng}\; \sum\limits_{j=1}^na_{ij}x_j-x_{n+i}= b_i).$$
\par +) Nếu $x_j\leq 0$  ta thay bởi ấn $x'_j=-x_j.$ Nếu ẩn số $x_k$ chưa rõ về dấu ta thay thế nó bởi hai ẩn mới $x_k', x_k^{''}\geq 0$ với $x_k=x_k'-x_k^{''}.$
\begin{exm} Đưa bài toán sau về dạng chính tắc
\begin{equation}
  \max\{5x_1+3x_2-x_3\}
\end{equation}
\begin{equation}
\text{với điều kiện}  \begin{cases}
   x_1-2x_2+7x_3\geq 10\\
-x_1+3x_2+x_3\leq 15
    \\ x_1+x_2+10x_3=20 \\ x_{1}\geq 0, \;x_{2}\leq 0, \;x_{3}\;\text{tùy ý}.
  \end{cases}
\end{equation}
Thay $\max f(X)$ bởi $\min\{-f(X)\}$, đưa thêm ẩn phụ $x_4, x_5\geq 0$ thay $x_2$ bởi $x'_2=-x_2$ và thay $x_3=x_3'-x''_3$ với $x_3', x^{''}_3\geq 0.$ Ta có  dạng chính tắc của bài toán là
\begin{equation}
  \min\{-5x_1+3x'_2+x'_3-x''_3\}
\end{equation}
\begin{equation}
\text{với điều kiện}  \begin{cases}
   x_1+2x'_2+7x'_3-7x''_3-x_4\;\;\;\,= 10\\
-x_1-3x'_2+x'_3-x''_3\;\;\;\;+x_5= 15
    \\ x_1-x'_2+10x'_3-10x''_3\;\;\;\;\;\;\;\;\;\,=20 \\ x_{1}, \;x'_{2}, \;x'_{3}, x''_3, x_4, x_5\geq 0.
  \end{cases}
\end{equation}
\end{exm}
\begin{rem}
Mọi bài toán quy hoach tuyến tính tổng quát đều có thể  viết được dưới dạng một bài toán dạng chính tắc bằng cách thêm các ẩn phụ. Vì vậy, chúng ta chỉ nghiên cứu cách giải cho bài toán dạng chính tắc.
\end{rem}
\subsubsection{Dạng chuẩn tắc}
Bài toán quy hoạch tuyến tính dạng chuẩn tắc là
\begin{equation}
  \min\{f(x)=\sum_{j=1}^nc_{j}x_{j}\}
\end{equation}
\begin{equation}\label{e1.29}
\text{với điều kiện}  \begin{cases}
   \sum\limits_{j=1}^na_{ij}x_{j}\geq b_i\;\forall \; i=\overline{1,m}\\
        x_{j}\geq 0, \, \forall j=\overline{1,n}.
  \end{cases}
\end{equation}
Bài toán khẩu phần thức ăn trong ví dụ \ref{vd1.2.4} cho ta bài toán dạng chuẩn tắc.
%\subsection{Thuật toán đồ thị}\label{sec2.4}
%Trong mục này chúng tôi đề xuất thuật giải bài toán quy hoạch tuyến tính hai ẩn sau
%\begin{equation}\label{e1.30}
%  \max (\min)\{f(x,y)=c_1x+c_2y\}
%\end{equation}
%\begin{equation}\label{e1.31}
%\text{với điều kiện}  \begin{cases}
%    a_ix+b_iy\leq d_i\;\;\forall i=\overline{1,n} \\ x, y\geq 0.
%  \end{cases}
%\end{equation}
%bằng cách biểu diễn các điều kiện buộc \eqref{e1.31} lên mặt phẳng tọa độ $Oxy.$ Từ đó, chỉ ra phương án tối ưu của bài toán hoặc chỉ ra bài toán vô nghiệm.
%\subsubsection{Nhận xét}
%Để biểu diễn hệ điều kiện buộc \eqref{e1.31} lên mặt phẳng $Oxy$ chúng tôi nhắc lại một số kiến thức hình học phẳng sau đây.
%\par -\; Một đường thẳng $(\Delta)$ trong mặt phẳng $Oxy$ luôn có phương trình
%$ax+by=c\;\;(a^2+b^2>0).$ Đường thẳng $(\Delta)$ chứa tất cả các điểm $M(x, y)$ sao cho giá trị của biểu thức $ax+by$ nhận giá trị bằng $c$.
%\par - Với đường thẳng $\Delta: ax+by=c$ và điểm $A(x_0, y_0)\not \in (\Delta).$ Nếu $ax_0+by_0<c$ thì nửa mặt phẳng xác định bởi $(\Delta)$ chứa điểm $A$ có phương trình là $ax+by\leq c$ và nửa mặt phẳng kia có phương trình là $ax+by\geq c.$
%\par - \;Nếu tịnh tiến đường thẳng $(\Delta): ax+by=c$ theo hướng của véc tơ pháp tuyến $\overrightarrow{n}=(a, b)$ ta được một đường thẳng mới $(\Delta_1): ax+by=c_1\;\;(c_1>c).$
%\par -\; Nếu tịnh tiến đường thẳng $(\Delta): ax+by=c$ ngược hướng với véc tơ pháp tuyến $\overrightarrow{n}=(a, b)$ ta được một đường thẳng mới $(\Delta_2): ax+by=c_2\;\;(c_2<c).$
%\subsubsection{Thuật toán đồ thị}
%Dựa trên các tính chất hình hoạc trong mặt phẳng $Oxy$ ta có thuật toán đồ thị giải bài toán \eqref{e1.30} và \eqref{e1.31} như sau
%\par \underline{\textbf{Bước 1.}} Biểu diễn các điều kiện buộc trong hệ điều kiện buộc \eqref{e1.31} lên mặt phẳng tọa độ $Oxy.$ Từ đó, ta có tập phương án $M$ được biểu diễn lên mặt phẳng tọa độ $Oxy.$
%\par \underline{\textbf{Bước 2.}} Xác định đường mức $(\Delta):\;\; c_1x+c_2y =f_0$. Trong đó $f_0$ là giá trị thuy chọn và đó là giá trị của hàm mục tiêu mà chúng ta mong muốn một cách sơ bộ.
%\par  \underline{\textbf{Bước 3.}} Tịnh tiến đường mức theo hướng (ngược hướng)  véc tơ pháp tuyến $\overrightarrow{n}=(a, b)$ ứng với bài toán $\max\;(\min)$. Từ đó chỉ ra phương án tối ưu của bài toán hặc chỉ ra bài toán vô nghiệm.
%%\newpage
%\begin{exm}\par Xét bài toán
%\begin{equation}
%  \max\{f(x,y)=3x+5y\}
%\end{equation}
%\begin{equation}\label{e2.33}
%\text{với điều kiện}\;  \begin{cases}
%    2x+y\leq 8 \\y\leq 4\\x\leq 3 \\ x, y\geq 0.
%  \end{cases}
%\end{equation}
% Để giải bài toán trên chúng ta biểu diễn tập phương án (M) thỏa mãn hệ điều kiện \eqref{e2.33} lên mặt phẳng Oxy ta được ngũ giác OABCD trong Hình \ref{H2.1'}. Xác định đường mức $(\Delta): 3x+5y=15.$ Đường $(\Delta)$ chính là đường màu hồng trong hình vẽ. Tịnh tiến $(\Delta)$ theo hướng của véc tơ $\overrightarrow{n}$ ta được đường $(\Delta'): 3x+5y=26$ (đường màu đỏ) đường thẳng này giao với tập phương án điểm $B(2,4).$ Ta có mọi điểm $N(x_0, y_0)$ thuộc tập phương án đều thỏa mãn $3x_0+5y_0\leq26.$ Do vậy phương án của bài toán là
% $$\begin{cases}
%   x=2\\y=4
% \end{cases}\;\;f_{\max}=26.$$
% %\displaystyle
%\begin{figure}[ht]
%  % Requires
%  \begin{center}
%  \includegraphics[width=9cm]{DT1}\\
%  \caption{Hình vẽ biểu diễn lời giải của bài toán}\label{H2.1'}
%  \end{center}
%\end{figure}
% \end{exm}
% \begin{exm} Giải bài toán sau bằng thuật toán đồ thị
% \begin{equation}
%   \min\{f(X)=x-y\}
% \end{equation}
% \begin{equation}
%   \text{với điều kiện}\;\;\begin{cases}
%     -2x+y\leq 4\\
%     x-2y\leq2
%     \\
%x,y\geq 0.
%   \end{cases}
% \end{equation}
% \end{exm}
%\subsection{Bài tập bổ trợ Mục \ref{sec2.4}}
 \subsection{Tính chất của bài toán quy hoạch tuyến tính}
%\subsubsection{Các giả thiết ban đầu}
Trong mục này chúng ta sẽ trình bày các tính chất của bài toán quy hoạch tuyến tính. Các tính chất này có sử dụng đến một số khái niệm và tính chất của tổ hợp lồi. Do đó, trươc hết chúng ta nhắc lại một số khái niệm và tính chất cơ bản của tổ hợp lồi trên không gian $\mathbb{R}^n.$

%$\ast$ \emph{Tập hợp lồi:}
 Tập hợp $\mathcal M\subset\mathbb{R}^n$ được gọi là \emph{tập hợp lồi} nếu với bất kỳ hai điểm $X_1, X2\in\mathcal M$ ta có
$$\lambda X_1+(1-\lambda) X_2\in \mathcal M, \;\;\forall\;\lambda\in[0, 1].$$

Tập $\mathcal M=\{X=(x_j)\in \mathbb{R}^n: \sum_{j=1}^na_{ij}x_j\leq b_i, i=1, 2, ..., m\}$ là một tập lồi. Khi đó, ta gọi $\mathcal M$ là \emph{tập lồi đa diện}. 

%$\ast$ \emph{Điểm cực biên:} 
Giả sử $\mathcal M\subset\mathbb{R}^n$ là một tập hợp lồi. Điểm $X\in \mathcal M$ được gọi là \emph{điểm cực biên} của $\mathcal M$ nếu không thể biểu diễn thành tổ hợp lồi thực sự của hai điểm bất kỳ thuộc $\mathcal M$. Tức là không tồn tại $X_1$ và $X_2$ thuộc $\mathcal M$ và $\lambda\in (0,1)$ sao cho
$$X= \lambda X_1+(1-\lambda) X_2.$$

%$\ast$ 
%\vskip 0.2cm
%$\ast$ Tập lồi đa diện $M$ được gọi là \emph{bị chặn} nếu tồn tại số thực $L>0$ sao cho với mọi $X = (x_j)\in  M$ ta đều có $|x_j|\leq L$, $j = 1, 2, ..., n$.
\vskip 0.2cm
$\ast$ Tập lồi đa diện khác rỗng và bị chặn (tồn tại số thực $L>0$ sao cho với mọi $X = (x_j)\in  \mathcal M$ ta đều có $|x_j|\leq L$, $j = 1, 2, ..., n$) được gọi là \emph{đa diện lồi}.

 Một đa diện lồi $\mathcal M$ có hữu hạn điểm cực biên $X_1, X_2, ..., X_r$ và mọi điểm thuộc đa diện lồi đều là tổ hợp lồi của các điểm cực biên, nghĩa là mọi $X \in \mathcal M$ thì
$$X =  \sum_{j=1}^r\lambda_jX_j, \;\lambda_j\geq0, \sum_{j=1}^r\lambda_j=1.$$
  
Tiếp theo ta sẽ xét một số tính chất của bài toán duy hoach tuyến tính. Không mất tính tổng quát, xét bài toán quy hoạch tuyến tính dạng chính tắc với các giả thiết
\begin{equation}\label{e1.34}
  \min\{f(x)=\sum_{j=1}^nc_{j}x_{j}\}
\end{equation}
\begin{equation}\label{e1.35}
\text{với điều kiện}  \begin{cases}
   \sum\limits_{j=1}^na_{ij}x_{j}= b_i\;\forall \; i=\overline{1,m}\\
        x_{j}\geq 0, \, \forall j=\overline{1,n}.
  \end{cases}
\end{equation}
 Ta có ma trận hệ số của hệ điều kiện \eqref{e1.35} là
\begin{equation}\label{e1.36}A=\begin{array}{ccccc}
    (A_1)&(A_2)&(A_3)&\ldots&(A_n)\\
    \left[\begin{array}{c}a_{11}\\a_{21}\\ \vdots\\a_{m1}\end{array}\right. &\begin{array}{c}a_{12}\\a_{22}\\ \vdots\\a_{m2}\end{array} & \begin{array}{c}a_{13}\\a_{23}\\ \vdots\\a_{m3}\end{array} &\begin{array}{c}\ldots\\ \ldots\\ \vdots\\ \ldots\end{array}&\left.\begin{array}{c}a_{1n}\\a_{2n}\\ \vdots\\a_{mn}\end{array}\right]\end{array}_{m\times n}
    \end{equation}
trong đó $A_j$ ký hiệu véc tơ cột thứ $j$ của ma trận $A$. Tức là 
$$A_j=\begin{bmatrix}a_{1j}\\a_{2j}\\\vdots\\a_{mj}\end{bmatrix}\;\;\forall\; j=\overline{1,n.}$$
    \par+) $m<n$ (trường hợp $m\geq n$ thì bài toán có không quá 1 phương án. Do đó, việc tìm phương án tối ưu là không có ý nghĩa).
    \par +) Hạng của ma trận hệ số $A$ có hạng bằng $m$.
    \par +) $b_i\geq 0\,\forall i=\overline{1, m}.$
    \par +) $M=\{X=(x_1, x_2,\ldots, x_n)| \;\text{thỏa mãn điều kiện buộc \eqref{e1.35}}\}$ là tập phương án của bài toán.
%\begin{defn}

Tập phương án của bài toán quy hoạch tuyến tính là tập lồi.      
Điểm cực biên $X$ của tập lồi các phương án $M$  được gọi là \emph{phương án cực biên} của bài toán.
   % \end{defn}
%\begin{defn}  

Giả sử $X=(x_1,x_2,\ldots, x_n)$ là một phương án cực biên của bài toán. Khi đó $\{A_j|\; x_j>0, j=\overline{1, n}\}$ được gọi là \emph{hệ véc tơ cơ sơ} liên kết với phương án cực biên $X.$
    %\end{defn}

%  \begin{defn}
      Một phương án cực biên có đủ $m$ tọa độ dương được gọi là \emph{phương án cực biên không suy biến}.
      Bài toán  có tất cả các phương án cực biên không suy biến thì được gọi là \emph{bài toán  không suy biến.}
%    \end{defn}
%    \begin{rem} Nếu bài toán quy hoạch tuyến tính tồn tại phương án cực biên không suy biến thì hạng của ma trận hệ số $A$ được xác định bởi \eqref{e1.36} bằng $m.$
%          \end{rem}
% 
%\subsubsection{Các tính chất}
    \begin{proper}\label{proper2.1.8}\text{ }

%\label{lem1.5.1}
      1) Tập phương án $M$ của bài toán là tập lồi đa diện.
%    \end{proper}
%     \begin{proper}\label{thm1.5.3}

    2) Nếu tập phương án $M$ của bài toán khác rỗng và bị chặn thì tồn tại phương án cực biên tối ứu.
    %\end{proper}
%    \begin{proof} Theo Bổ đề \ref{lem1.5.1} thì tập phương án của bài toán quy hoạch là tập lồi đa diện. Mặt khác theo giả thiết của định lý thì $M\ne\emptyset$ và bị chặn nên tập phương án $M$ là đa diện lồi. Do đó, $M$ có hữu hạn điểm cực biên $X_1,X_2, \ldots, X_k$ và với mọi $Y\in M$ ta luôn có
%    $$Y=\sum_{i=1}^k\lambda_i X_i,\;\;\text{với}\; \lambda_i\geq 0\;\text{và}\;\sum_{i=1}^k\lambda_i=1.$$
%      Từ đó suy ra
%      \begin{equation}\label{e1.37}f(Y)=f(\sum_{i=1}^k\lambda_i X_i)=\sum_{i=1}^k\lambda_i f(X_i).\end{equation}
%      Đặt $f(X_l)=\max\{f(X_i):\; i=\overline{1,k}\}.$ Kết hợp với \eqref{e1.37} ta có
%      \begin{align*}\label{e1.37}f(Y)=\sum_{i=1}^k\lambda_i f(X_i)
%      &\geq\sum_{i=1}^k\lambda_i f(X_l)
%      \\&=\left(\sum_{i=1}^k\lambda_i\right)f(X_l)=f(X_l).\end{align*}
%      Vậy $f(Y)\geq f(X_l),\;\forall\, Y\in M.$ Nghĩa là $X_l$ là một phương án cực biên tối ưu.
%    \end{proof}
%    \begin{proper}
   
3)   Nếu bài toán quy hoạch tuyến tính có hai phương án tối ưu khác nhau thì có vô số phương án tối ưu.
%    \end{proper}
%    \begin{proof}
%      Giả sử $X_1, X_2\in M$ là hai phương án tối ưu của bài toán, có nghĩa là
%      $$f(X_1)=f(X_2)=\min\{f(X)|\; X\in M\}.$$
%      Đặt
%      $$Y=\lambda X_1+(1-\lambda)X_2,\;\,\lambda\in[0, 1].$$
%      Khi đó $Y\in M$ và
%      \begin{align*}
%      f(Y)=f(\lambda X_1+(1-\lambda)X_2)&=\lambda f(X_1)+(1-\lambda)f(X_2)
%      \\&=\lambda f(X_1)+(1-\lambda)f(X_1)
%      \\&=f(X_1).
%      \end{align*}
%      Do đó $Y$ cũng là phương án tối ưu của bài toán. Mặt khác, chúng ta có vô số giá trị $\lambda\in[0;1]$ nên có vô số phương án tối ưu.
%    \end{proof}
   % \begin{proper}
      
4) Phương án $X=(x_j)$ là phương án cực biên khi và chỉ khi hệ véc tơ cơ sở $\{A_j |\; x_j>0, j=\overline{1,n} \}$ liên kết với $X$ độc lập tuyến tính.

    5)  Nếu bài toán có phương án tối ưu thì có ít nhất một phương án cực biên tối ưu.
%\end{proper}
%    \begin{proof}
%    Không mất tính tổng quát giả sử $X$ có $k$ tọa độ dương và có dạng
%      $$X=(x_1, x_2,\ldots,x_k, 0,\ldots, 0)$$
%   trong đó $x_1, x_2, \ldots, x_k>0.$ Khi đó
%     \par \textbf{\underline{Điều kiện cần.}} Giả sử $X$ là phương án cực biên. Ta sẽ chứng minh $\{A_1,A_2,\ldots, A_k\}$ độc lập tuyến tính. Thật vậy, giả sử $\{A_1,A_2,\ldots, A_k\}$ phụ thuộc tuyến tính. Khi đó, tồn tại $(\alpha_1, \alpha_2,\ldots, \alpha_k)\ne(0,0,\ldots,0)$ sao cho
%     \begin{equation}\label{e1.38}
%       \alpha_1 A_1+\alpha_2A_2+\ldots+\alpha_kA_k=0.
%     \end{equation}
%     Do $X$ là phương án nên ta cũng có
%     \begin{equation}\label{e1.39}
%       x_1 A_1+x_2A_2+\ldots+x_kA_k=b.
%     \end{equation}
%     Từ \eqref{e1.38} và \eqref{e1.39} ta có
%    \begin{equation*}
%       (x_1\pm\alpha_1\theta) A_1+(x_2\pm\alpha_2\theta)A_2+\ldots+(x_k\pm\alpha_k\theta)A_k=b.
%     \end{equation*}
%     Do $x_1,x_2,\ldots x_k>0$ nên có thể chọn được $\theta>0$ đủ bé sao cho $x_i\pm\alpha_i\theta\geq 0,\;\forall\,i=\overline{1, k}.$ Khi đó ta có
%     \begin{align*}
%       &X_1=(x_1+\alpha_1\theta, x_2+\alpha_2\theta,\ldots,x_k+\alpha_k\theta,0,\ldots,0)
%       \\&X_2=(x_1-\alpha_1\theta, x_2-\alpha_2\theta,\ldots,x_k-\alpha_k\theta,0,\ldots,0)
%     \end{align*}
%     là hai phương án khác nhau (vì tồn tại $\alpha_i\ne 0$).
%     Từ đó suy ra, $X=\frac12X_1+\frac12X_2.$ Điều này mâu thuẩn với $X$ là phương án cực biên. Vậy $\{A_1,A_2,\ldots, A_k\}$ độc lập tuyến tính.
%     \par \textbf{\underline{Điều kiện đủ.}} Giả sử $\{A_1,A_2,\ldots, A_k\}$ độc lập tuyến tính. Ta sẽ chứng minh $X=(x_1,x_2,\ldots,x_k,0,\ldots,0)$ là phương án cực biên. Thật vậy, giả sử $X$ không phải là phương án cực biên, nghĩa là tồn tại $Y_1=(y^{(1)}_1,\ldots, y^{(1)}_n)$ và $Y_2=(y^{(2)}_1,\ldots, y^{(2)}_n)$ là hai phương án khác nhau sao cho $X=\lambda Y_1+(1-\lambda)Y_2, \lambda\in(0,1).$ Do $\lambda y^{(1)}_i+(1-\lambda)y^{(2)}_i=0,$ với $ \lambda\in(0,1), i=k+1, \ldots, n,$ nên ta có $y^{(1)}_i=y^{(2)}_i=0,\;\forall i=k+1,\ldots,n$. Tức là zzx $Y_1=(y^{(1)}_1, y^{(1)}_2,\ldots,y^{(1)}_k,0,\ldots,0), Y_2=(y^{(2)}_1, y^{(2)}_2,\ldots,y^{(2)}_k,0,\ldots,0),$ suy ra
%   \begin{equation}\label{e1.40}
%       y^{(1)}_1 A_1+y^{(1)}_2A_2+\ldots+y^{(1)}_kA_k=b
%     \end{equation}
%     và
%  \begin{equation}\label{e1.41}
%       y^{(2)}_1 A_1+y^{(2)}_2A_2+\ldots+y^{(2)}_kA_k=b
%     \end{equation}
%  Từ \eqref{e1.40} và \eqref{e1.41} ta được $\{A_1,A_2,\ldots, A_k\}$ phụ thuộc tuyến tính. Điều này mâu thuẩn với giả thiết. Vậy $X$ là phương án cực biên.
%  \begin{equation*}
%       (y^{(1)}_1-y^{(2)}_1) A_1+(y^{(1)}_2-y^{(2)}_2)A_2+\ldots+(y^{(1)}_k-y^{(2)}_k)A_k=0.
%     \end{equation*}
%     Vì $Y_1\ne Y_2$ nên tồn tại $y^{(1)}_i-y^{(2)}_i\ne 0$. Do đó, hệ véc tơ  $\{A_1,A_2,\ldots, A_k\}$ phụ thuộc tuyến tính. Điều này mâu thuẩn với giả thiết. Vậy $X$ là phương án cực biên.
%    \end{proof}
   % \begin{cor}\text{ }\label{cor1.5.7}

      6) Số tọa độ dương của phương án cực biên tối đa là $m.$
      \par7) Số phương án cực biên của bài toán là hữu hạn.
      \par 8) $X\in M$ là phương án cực biên khi và chỉ khi $X$ thỏa mãn chặt $n$ điều kiện buộc.
\end{proper}
    \begin{proof} Trong giáo trình này chúng tôi  không trình bày chứng minh các tinh chất này. Để biết chi tiết về các tính chất này người đọc có thể  xem trong tài liệ tham khảo\cite{TXS1}.
\end{proof}
Không mất tính tổng quát chúng ta giả thiết bài toán \eqref{e1.34}\eqref{e1.35} có dạng
\begin{equation}\label{e1.43bs}
  \min\{f(X)=\sum_{i=1}^nc_jx_j\}
\end{equation}
\begin{equation}\label{e1.43}
  \text{với điều kiện}\begin{cases}
    x_i+\sum\limits_{j=1\atop  j\not\in I}^n a_{ij}x_j=b_i, i\in I
    \\ x_j\geq 0, j=1,2, \ldots, n,
  \end{cases}
\end{equation}
trong đó  $I=\{1,2,\ldots, m\}.$
Khi đó ma trận hệ số của hệ điều kiện là
 \begin{equation}A=\begin{array}{ccccccc}
    (A_1)&(A_2)&\ldots&(A_m)&(A_{m+1})&\ldots&(A_n)\\
    \left[\begin{array}{c}1\\0\\ \vdots\\0\end{array}\right. &\begin{array}{c}0\\1\\ \vdots\\0\end{array} & \begin{array}{c}\ldots\\ \ldots\\ \vdots\\ \ldots\end{array} &\begin{array}{c}0\\ 0\\ \vdots\\ 1\end{array}&\begin{array}{c}a_{1m+1}\\a_{2m+1}\\ \vdots\\a_{mm+1}\end{array}&\begin{array}{c}\ldots\\ \ldots \\ \vdots\\ \ldots\end{array}&\left.\begin{array}{c}a_{1n}\\a_{2n}\\ \vdots\\a_{mn}\end{array}\right]\end{array}_{m\times n},
    \end{equation}
    và  ta có phương án cực biên
    $$X_0=\left(x_1^0, x_2^0,\ldots,x_m^0, 0,\ldots,0\right),\; x_i^0=b_i, \, i=1,2,\dots, m$$
    với hệ véc tơ cơ sở là $(A_1 A_2\ldots A_m)$ tạo thành ma trận đơn vị
     \begin{equation}\mathcal{B}=(A_1 A_2\ldots A_m)=\begin{array}{cccc}
    (A_1)&(A_2)&\ldots&(A_m)\\
    \left[\begin{array}{c}1\\0\\ \vdots\\0\end{array}\right. &\begin{array}{c}0\\1\\ \vdots\\0\end{array} & \begin{array}{c}\ldots\\ \ldots\\ \vdots\\ \ldots\end{array} &\left.\begin{array}{c}0\\ 0\\ \vdots\\ 1\end{array}\right]\end{array}_{m\times m},
    \end{equation}
    Ký hiệu
   $$X^*_{\mathcal{B}}=\left(x_1^0, x_2^0,\dots,x^0_m\right), C^*=\left(c_1, c_2,\ldots,c_m\right).$$
 Khi đó,
 \begin{align}&x_1^0A_1 x_2^0A_1+\dots+x^0_mA_m=B\; \text{hay} \;\mathcal{B} X^*_{\mathcal{B}}=B;
 \\&f(X_0)= C^*X^*B=c_1x^0_1+c_2x^0_2+\ldots c_mx^0_m;
 \\& A_j=a_{1j}A_1+a_{2j}A_2+\ldots+a_{mj}A_m.
  \end{align}
 Ký hiệu
 \begin{equation}
   \Delta_j=C^*A_j-c_j=\sum_{i=1}^mc_ia_{ij}-c_j.
 \end{equation}
% \subsubsection{Các định lý cơ sở}
 \begin{proper}\label{proper2.1.8}\text{ }

1) \;\;Nếu tại phương án cực biên $X_0$ có $\Delta_j\leq 0,\;\forall j=1,2,\ldots,n$ thì $X_0$ là phương án tối ưu.

2) \;\;%\label{thm1.6.3}
      Nếu tại phương án cực biên $X_0$ tồn tại $\Delta_k>0$ và mọi $a_{ik}\leq 0, (i=1,\ldots,m)$ thì bài toán không có phương án tối ưu (hàm mục tiêu không bị chặn trên tập phương án).

 3)\;\;  Nếu tại phương án cực biên $X_0$ thỏa mãn với mỗi $\Delta_k>0$ luôn tồn tại $a_{ik}>0$ thì sẽ xây dựng được phương án cực biên $X_1$ tốt hơn phương án $X_0$ theo nghĩa $f(X_1)<f(X_0).$

 \end{proper}
\begin{proof}  Trong giáo trình này chúng tôi  không trình bày chứng minh các tinh chất này. Để biết chi tiết về các tính chất này người đọc có thể  xem trong tài liệ tham khảo\cite{TXS1}.
\end{proof}
% \begin{proof}
% Với các giả thiết ở trên ta có
%   $$X_0=\left(b_1, b_2,\ldots,b_m, 0,\ldots,0\right)\;\text{và}\; f(X_0)=CX_0=\sum_{i=1}^mc_ib_i$$
% Gọi $X=(x_j)$ là một phương án nào đó của bài toán. Khi đó  $X$ thỏa mãn hệ \eqref{e1.43} suy ra
%  $$x_i+\sum\limits_{j=1\atop  j\not\in I}^n a_{ij}x_j=b_i, i\in I,$$
%  hay
%  \begin{equation}
%    x_i-b_i=-\sum\limits_{j=1\atop  j\not\in I}^n a_{ij}x_j, i\in I.
%    \end{equation}
%    Ta có
%    \begin{align*}
%      CX-CX_0&=\sum_{j=1}^nc_jx_j-\sum_{i\in I}c_ib_i
%      =\sum_{j\not\in I}c_jx_j+\sum_{i\in I}c_ix_i-\sum_{i\in I}c_ib_i
%      \\&=\sum_{j\not\in I}c_jx_j+\sum_{i\in I}c_i(x_i-b_i)
%      =\sum_{j\not\in I}c_jx_j-\sum_{i\in I}c_i\sum_{j\not\in I}a_{ij}x_j
%      \\&=\sum_{j\not\in I}\left(c_j-\sum_{i\in I}c_ia_{ij}x_j\right)x_j =-\sum_{j\not\in I}\Delta_jx_j.
%    \end{align*}
%    Nếu mọi $\Delta_j\leq 0$ cùng với $x_j\geq 0$ suy ra $CX-CX_0\geq 0$. Vậy $f(X_0)\leq f(X)\;\forall X\in M.$ Nghĩa là $X_0$ là phương án tối ưu.
%    \end{proof}
%    \begin{thm}[Dấu hiệu bài toán vô nghiệm]\label{thm1.6.3}
%      Nếu tại phương án cực biên $X_0$ tồn tại $\Delta_k>0$ và mọi $a_{ik}\leq 0, (i=1,\ldots,m)$ thì bài toán không có phương án tối ưu (hàm mục tiêu không bị chặn trên tập phương án).
%    \end{thm}
%    \begin{proof}
%
%    \end{proof}
%\begin{thm}
%  Nếu tại phương án cực biên $X_0$ thỏa mãn với mỗi $\Delta_k>0$ luôn tồn tại $a_{ik}>0$ thì sẽ xây dựng được phương án cực biên $X_1$ tốt hơn phương án $X_0$ theo nghĩa $f(X_1)<f(X_0).$
%\end{thm}

\subsection{Phương pháp đơn hình giải bài toán quy hoạch}\label{sec2.6}
\subsubsection{Ý tưởng chung }
%Theo Định lý \ref{thm1.5.3}, nếu tập phương án của bài toán khác rỗng và bị chặn thì có phương án cự biên tối ưu. Mặt khác, theo Định lý \ref{thm1.5.5} thì nếu bài toán có phương án tối ưu thì sẽ tồn tại ít nhất một phương án cực biên tối ưu. Hơn nữa, theo Hệ quả \ref{cor1.5.7}, số phương án cực biên của bài toán là hữu hạn.
Theo Tính chất \ref{proper2.1.8} chúng ta thây rằng số phương án cực biên của bài toán là hữu hạn và nếu bài toán có phương án tối ưu thì có phương án cực biên tối ưu. Mặt khác, 
các bài toán trong thực tể thường chỉ yêu cầu chúng ta chỉ ra một chiến lược tối ưu nào đó. Do vậy, ý tưởng của chúng ta là chỉ cần tìm phương án cực biên tối ưu bằng cách như sau.
\par - Xuất phát tử một phương án cực biên $X_0$ nào đó, tìm cách kiểm tra xem $X_0$ có phải là phương án cực biên không?

  - Nếu $X_0$ là tối ưu thì dừng và kết luận.
 
 -  Nếu không, tìm cách xây dựng một phương án cự biên mới $X_1$ tốt hơn $X_0.$
  
- Quá trình dược lặp đi lặp lại sau hữu hạn bước lặp sẽ tìm được phương án tối ưu hoặc chỉ ra bài toán vô nghiệm.

\par Phương pháp tìm phương án cực biên tối ưu như trên được gọi là "\emph{\textbf{phương pháp đơn hình}}".  Cơ sở để giải bài toán chúng ta dựa vào Tính chất \ref{proper2.1.8}


%\par Từ ý tưởng trên, để thực hiện nó chúng ta cần phải trả lời một số câu hỏi sau:
%\begin{enumerate}
%\item Làm thế nào để xây dựng được phương án cực biên $X_0$?
%  \item Dấu hiệu để kiểm tra một phương án cực biên $X_0$ có phải là phương án  cực biên tối ưu?
%  \item Xây dựng được phương án cực biên $X_1$ tốt hơn phương án $X_0$ như thế nào?
%  \item Dấu hiệu nào cho chúng ta biết được bài toán vô nghiệm?
%\end{enumerate}
%Các mục tiếp theo sẽ giúp chúng ta trả lời những câu hỏi này.
%\subsubsection{Các định lý cơ sở}
%Không mất tính tổng quát chúng ta giả thiết bài toán quy hoạch tuyến tính có dạng
%\begin{equation}
%  \min\{f(X)=\sum_{i=1}^nc_jx_j\}
%\end{equation}
%với điều kiện
%\begin{equation}\label{e1.43}
%  \begin{cases}
%    x_i+\sum\limits_{j=1\atop  j\not\in I}^n a_{ij}x_j=b_i, i\in I
%    \\ x_j\geq 0, j=1,2, \ldots, n,
%  \end{cases}
%\end{equation}
%trong đó mọi $b_i\geq 0, i=1,\ldots, m, I$ là tập gồm $m$ chỉ số, $I\subset\{1,2,\ldots, n\},$ chẳng hạn $I=\{1,2,\ldots, m\}.$
%Khi đó ma trận hệ số của hệ điều kiện là
% \begin{equation}A=\begin{array}{ccccccc}
%    (A_1)&(A_2)&\ldots&(A_m)&(A_{m+1})&\ldots&(A_n)\\
%    \left[\begin{array}{c}1\\0\\ \vdots\\0\end{array}\right. &\begin{array}{c}0\\1\\ \vdots\\0\end{array} & \begin{array}{c}\ldots\\ \ldots\\ \vdots\\ \ldots\end{array} &\begin{array}{c}0\\ 0\\ \vdots\\ 1\end{array}&\begin{array}{c}a_{1m+1}\\a_{2m+1}\\ \vdots\\a_{mm+1}\end{array}&\begin{array}{c}\ldots\\ \ldots \\ \vdots\\ \ldots\end{array}&\left.\begin{array}{c}a_{1n}\\a_{2n}\\ \vdots\\a_{mn}\end{array}\right]\end{array}_{m\times n},
%    \end{equation}
%    và  ta có phương án cực biên
%    $$X_0=\left(x_1^0, x_2^0,\ldots,x_m^0, 0,\ldots,0\right),\; x_i^0=b_i, \, i=1,2,\dots, m$$
%    với hệ véc tơ cơ sở là $(A_1 A_2\ldots A_m)$ tạo thành ma trận đơn vị
%     \begin{equation}\mathcal{B}=(A_1 A_2\ldots A_m)=\begin{array}{cccc}
%    (A_1)&(A_2)&\ldots&(A_m)\\
%    \left[\begin{array}{c}1\\0\\ \vdots\\0\end{array}\right. &\begin{array}{c}0\\1\\ \vdots\\0\end{array} & \begin{array}{c}\ldots\\ \ldots\\ \vdots\\ \ldots\end{array} &\left.\begin{array}{c}0\\ 0\\ \vdots\\ 1\end{array}\right]\end{array}_{m\times m},
%    \end{equation}
%    Ký hiệu
%   $$X^*_{\mathcal{B}}=\left(x_1^0, x_2^0,\dots,x^0_m\right), C^*=\left(c_1, c_2,\ldots,c_m\right).$$
% Khi đó,
% \begin{align}&x_1^0A_1 x_2^0A_1+\dots+x^0_mA_m=B\; \text{hay} \;\mathcal{B} X^*_{\mathcal{B}}=B;
% \\&f(X_0)= C^*X^*B=c_1x^0_1+c_2x^0_2+\ldots c_mx^0_m;
% \\& A_j=a_{1j}A_1+a_{2j}A_2+\ldots+a_{mj}A_m.
%  \end{align}
% Ký hiệu
% \begin{equation}
%   \Delta_j=C^*A_j-c_j=\sum_{i=1}^mc_ia_{ij}-c_j.
% \end{equation}
%% \subsubsection{Các định lý cơ sở}
% \begin{thm}[Dấu hiệu tối ưu] Nếu tại phương án cực biên $X_0$ có $\Delta_j\leq 0,\;\forall j=1,2,\ldots,n$ thì $X_0$ là phương án tối ưu.
% \end{thm}
% \begin{proof}
% Với các giả thiết ở trên ta có
%   $$X_0=\left(b_1, b_2,\ldots,b_m, 0,\ldots,0\right)\;\text{và}\; f(X_0)=CX_0=\sum_{i=1}^mc_ib_i$$
% Gọi $X=(x_j)$ là một phương án nào đó của bài toán. Khi đó  $X$ thỏa mãn hệ \eqref{e1.43} suy ra
%  $$x_i+\sum\limits_{j=1\atop  j\not\in I}^n a_{ij}x_j=b_i, i\in I,$$
%  hay
%  \begin{equation}
%    x_i-b_i=-\sum\limits_{j=1\atop  j\not\in I}^n a_{ij}x_j, i\in I.
%    \end{equation}
%    Ta có
%    \begin{align*}
%      CX-CX_0&=\sum_{j=1}^nc_jx_j-\sum_{i\in I}c_ib_i
%      =\sum_{j\not\in I}c_jx_j+\sum_{i\in I}c_ix_i-\sum_{i\in I}c_ib_i
%      \\&=\sum_{j\not\in I}c_jx_j+\sum_{i\in I}c_i(x_i-b_i)
%      =\sum_{j\not\in I}c_jx_j-\sum_{i\in I}c_i\sum_{j\not\in I}a_{ij}x_j
%      \\&=\sum_{j\not\in I}\left(c_j-\sum_{i\in I}c_ia_{ij}x_j\right)x_j =-\sum_{j\not\in I}\Delta_jx_j.
%    \end{align*}
%    Nếu mọi $\Delta_j\leq 0$ cùng với $x_j\geq 0$ suy ra $CX-CX_0\geq 0$. Vậy $f(X_0)\leq f(X)\;\forall X\in M.$ Nghĩa là $X_0$ là phương án tối ưu.
%    \end{proof}
%    \begin{thm}[Dấu hiệu bài toán vô nghiệm]\label{thm1.6.3}
%      Nếu tại phương án cực biên $X_0$ tồn tại $\Delta_k>0$ và mọi $a_{ik}\leq 0, (i=1,\ldots,m)$ thì bài toán không có phương án tối ưu (hàm mục tiêu không bị chặn trên tập phương án).
%    \end{thm}
%    \begin{proof}
%
%    \end{proof}
%\begin{thm}
%  Nếu tại phương án cực biên $X_0$ thỏa mãn với mỗi $\Delta_k>0$ luôn tồn tại $a_{ik}>0$ thì sẽ xây dựng được phương án cực biên $X_1$ tốt hơn phương án $X_0$ theo nghĩa $f(X_1)<f(X_0).$
%\end{thm}
%\subsubsection{Công thức biến đổi và bảng đơn hình}
%\subsubsection{Công thức biến đổi}
%Tại phương án cực biên $X_0$ thỏa mãn điều kiện của Định lý \ref{thm1.6.3}. Chúng ta cần xây dựng $X_1$ tốt hơn $X_0.$  Ta có
%$$X_0\; \text{có}\;\begin{cases}
%  x^{0}_i, i\in I,\\ A=\left(a_{ij}\right)\\
%  \Delta_{j}, \\f(X_0)
%\end{cases}\xrightarrow{\text{Xác định}}X_0\; \text{có}\;\begin{cases}
%  x^{(1)}_i, i\in I',\\ A'=\left(a'_{ij}\right)\\
%  \Delta'_{j}, \\f(X_1)
%\end{cases}$$
%
%Từ chứng minh  Định lý \ref{thm1.6.3} ta có các công thức biến đổi sau.
%\par +) Xác định $\Delta_k=\max\{\Delta_j:\; \Delta_j>0\}.$
%\par +) Xác định $\lambda_{0k}=\min\left\{\frac{x^0_i}{a_{ik}}:\; a_{ik}>0\right\}=\frac{x^0_l}{a_{lk}}.$
%Khi đó ta có các công thức biến đổi sau
%\begin{equation}\label{e1.51}
%  x'_i=\begin{cases}
%    \frac{x^0_l}{a_{lk}}&\text{nếu}\; i=k\\
%    x^0_i- \frac{x^0_l}{a_{lk}}a_{ik}&\text{nếu}\; i\ne k,
%  \end{cases}
%\end{equation}
%\begin{equation}\label{e1.52}
%  a'_{ij}=\begin{cases}
%    \frac{a_{lj}}{a_{lk}}&\text{nếu}\; i=k\\
%    a_{ij}- \frac{a_{lj}}{a_{lk}}a_{ik}&\text{nếu}\; i\ne k
%  \end{cases}
%\end{equation}
% \begin{equation}\label{e1.53}
%   \Delta'_j=\Delta_j-\frac{a_{lj}}{a_{lk}}\Delta_{k}
% \end{equation}
% và
% \begin{equation}\label{e1.54}
%   f(X_1)=f(X_0)-\lambda_{0k}\Delta_k.
% \end{equation}
% \begin{rem}
%  +) Nếu tại phương án $X_0$ có nhiều $\Delta_j>0$ về nguyên tắc ta có quyền chọn bất kỳ $\Delta_k$ nào đó trong số các $\Delta_j>0$ ta đều được $X_1$ tốt hơn $X_0.$ Tuy nhiên từ \eqref{e1.54} chúng ta thấy rằng chúng ta ưu tiên chọn $\Delta_k>0$ sao cho $\lambda_{0k}\Delta_k$ càng lớn càng tốt. Do đó, ta thường chọn $\Delta_k=\max\{\Delta_j:\; \Delta_j>0\}.$ Trong trường hợp $\max\{\Delta_j:\; \Delta_j>0\}$ ứng với nhiều giá trị $\Delta_k$ thì ta chọn $\Delta_k$ sao cho $\lambda_{0k}\Delta_k$ lớn nhất.
%   \par +) Nếu ký hiệu
%   \begin{equation}
%     x_i=a_{i0}; f(X)=a_{m+10}; \Delta_j=a_{m+1j}
%   \end{equation}
%   thì các công thức \eqref{e1.51}$\div$\eqref{e1.54} có thể viết thành một công thức
%   \begin{equation}\label{e1.56}
%  a'_{ij}=\begin{cases}
%    \frac{a_{lj}}{a_{lk}}&\text{nếu}\; i=k\\
%    a_{ij}- \frac{a_{lj}}{a_{lk}}a_{ik}&\text{nếu}\; i\ne k
%  \end{cases}
%\end{equation}
%với $i=1,2,\ldots,m+1; j=0,1,2,\ldots, n.$
% \end{rem}
 %\subsubsection{Bảng đơn hình}
 % \subsubsection{Thuật toán đơn hình và các ví dụ}
  \subsubsection{Thuật toán}
  { }
  \textbf{\underline{Bước 0}}\;(\emph{Lập bảng xuất phát}) Chọn hệ véc tơ cơ sở đơn vị và phương án cực biên xuất phát.
 \par - Xác đinh $x^0_i, \; i=\overline{0,m}$
 \par- Xác đinh $c_j \;\forall i=\overline{1,n}; \; a_{ij}\; \forall i=\overline{1,m}; j=\overline{1,n}.$
 \par - Xác định $\Delta_j=\sum_{i=1}^mc_ia_{ij}-c_j; \; \forall j=\overline{1,n}.$
 \\ \textbf{\underline{Bước 1}}\; (\emph{kiểm tra tiêu chuẩn tối ưu}) $\Delta_j\leq 0?,\;\forall j=1,\ldots,n.$
 \par - Nếu có, chuyển sang bước 6.
 \par- Nếu không chuyển sang bươc 2.
 \\ \textbf{\underline{Bước 2}}\; (\emph{kiểm tra khả năng không có tối ưu}). Tồn tại $\Delta_k>0$ mà $a_{ik}<0?$
 \par - Nếu có, chuyển sang bước 6.
 \par- Nếu không chuyển sang bươc 3.
 \\ \textbf{\underline{Bước 3}}\; (\emph{chọn véc tơ vào cơ sở}). $\Delta_k=\max\{\Delta_j: \; \Delta_j>0\},$ đưa $A_k$ vào cơ sở.
 \\ \textbf{\underline{Bước 4}}\; (\emph{chọn véc tơ ra khỏi  cơ sở}). $\lambda_0=\min\{\frac{x^{0}_j}{a_{ik}}:\; a_{ik}>0\}=\frac{x^{0}_l}{a_{lk}},$ đưa $A_l$ ra khỏi cơ sở.
 \\ \textbf{\underline{Bước 5}}\; (\emph{Xây dựng phương án cực biên mới}). Xây dựng phương án cực biên mới $X_1$ theo \textbf{quy tắc T}. Gán $X_0:=X_1$ quay trở lại bước 1.
 \\\textbf{\underline{Bước 6}}\; Kết luận.

Để biến đổi từ phương án $X_0$ sang phương án $X_1$ theo thuật toán trên, để thuận tiện người ta mô tả nó trên bảng đơn hình sau
    \begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
\hline
Bảng& Cơ sở &Hệ số &Tọa độ &$c_1$&$c_2$&$\cdots$&$c_j$&$\cdots$&$c_n$
\\
\cline{5-10}&$A_i$&$c_i$&$x_i$&$A_1$&$A_2$& $\cdots$ &$A_j$&$\cdots$&$A_n$
\\
\hline\hline&$A_1$&$c_1$&$x^0_1$&$a_{11}$&$a_{12}$&$\cdots$& $a_{1j}$ &$\cdots$&$a_{1n}$
\\ \cline{2-10}
&$ A_2$&$c_2$&$x^0_2$&$a_{21}$&$a_{22}$&$\cdots$& $a_{2j}$ &$\cdots$&$a_{2n}$
\\ \cline{2-10}
&$\cdots$&$\cdots$&$\cdots$&$\cdots$&$\cdots$&$\cdots$&$\cdots$ &$\cdots$&$\cdots$
\\ \cline{2-10}
I&$A_i$&$c_i$&$x^0_i$&$a_{i1}$&$a_{i2}$&$\cdots$& $a_{ij}$ &$\cdots$&$a_{in}$
\\ \cline{2-10}\cline{2-10}
&$\cdots$&$\cdots$&$\cdots$&$\cdots$&$\cdots$&$\cdots$&$\cdots$ &$\cdots$&$\cdots$
\\ \cline{2-10}
&$A_m$&$c_m$&$x^0_m$&$a_{m1}$&$a_{m2}$&$\cdots$& $a_{mj}$ &$\cdots$&$a_{mn}$
\\ \cline{2-10}
&&&$\textcolor[rgb]{1.00,0.00,0.00}{f(X_1)}$&
$\textcolor[rgb]{1.00,0.00,0.00}{\Delta_1}$&$\textcolor[rgb]{1.00,0.00,0.00}{\Delta_2}$&
$\textcolor[rgb]{1.00,0.00,0.00}{\cdots}$&$\textcolor[rgb]{1.00,0.00,0.00}{\Delta_j}$&$\textcolor[rgb]{1.00,0.00,0.00}{\cdots}$&
$\textcolor[rgb]{1.00,0.00,0.00}{\Delta_n}$
\\
\hline\hline&$A_1$&$c_1$&$x'_1$&$a'_{11}$&$a'_{12}$&$\cdots$& $a'_{1j}$ &$\cdots$&$a'_{1n}$
\\ \cline{2-10}
&$ A_2$&$c_2$&$x'_2$&$a'_{21}$&$a'_{22}$&$\cdots$& $a'_{2j}$ &$\cdots$&$a'_{2n}$
\\ \cline{2-10}
&$\cdots$&$\cdots$&$\cdots$&$\cdots$&$\cdots$&$\cdots$&$\cdots$ &$\cdots$&$\cdots$
\\ \cline{2-10}
II&$A_i$&$c_i$&$x'_i$&$a'_{i1}$&$a'_{i2}$&$\cdots$& $a'_{ij}$ &$\cdots$&$a'_{in}$
\\ \cline{2-10}
&$\cdots$&$\cdots$&$\cdots$&$\cdots$&$\cdots$&$\cdots$&$\cdots$ &$\cdots$&$\cdots$
\\ \cline{2-10}
&$A_m$&$c_m$&$x'_m$&$a'_{m1}$&$a'_{m2}$&$\cdots$& $a'_{mj}$ &$\cdots$&$a'_{mn}$
\\
\cline{2-10}
&&&$\textcolor[rgb]{1.00,0.00,0.00}{f(X_1)}$&
$\textcolor[rgb]{1.00,0.00,0.00}{\Delta'_1}$&$\textcolor[rgb]{1.00,0.00,0.00}{\Delta'_2}$&
$\textcolor[rgb]{1.00,0.00,0.00}{\cdots}$&$\textcolor[rgb]{1.00,0.00,0.00}{\Delta'_j}$&$\textcolor[rgb]{1.00,0.00,0.00}{\cdots}$&$\textcolor[rgb]{1.00,0.00,0.00}{\Delta'_n}$
\\ \hline
\end{tabular}
\end{center}
\noindent{\textbf{\underline{Quy tắc T}}}\\
- Tính toán trong bảng (I) ứng với $X_0$ gồm 2 bước:
\par+) Nhập các số liệu từ bài toán.
\par +) Tính $f(X_), \;\Delta_j$ theo quy tắc
\begin{equation}
  f(X_0)=\sum_{i=1}^mc_ix_i;\;\;\Delta_j=\sum_{j=1}^mc_ia_{ij}-c_j\; \forall j=\overline{1,n}.
\end{equation}
- Để biến đổi bảng (I) sang bảng (II) chúng ta cần chú ý
\par+) Trong bảng (I) cột $A_k$ ứng với $k$ sao cho $\Delta_k=\max\{\Delta_j:\; \Delta_j>0\}.$ được gọi là \emph{cột xoay.}
\par+) Trong bảng (I) hàng $A_l$ ứng với $l$ sao cho $\frac{x^0_l}{a_{lk}}=\min\{\frac{x^0_i}{a_{ik}}:\; a_{ik}>0\}.$ được gọi là \emph{hàng  xoay.}
\par+) Phần tử $a_{lk}$ là giao của hàng xoay và cột xoay được gọi là \emph{phần tử trục.}
\par+) Trong bảng (II) hàng $A_k$ vào thay cho hàng $A_l$ nên được tính đầu tiên, bằng cách lấy hàng $A_l$ ở bảng $(I)$ chia cho phần tử trục $a_{lk}.$
\par+) Các giá trị trong bảng  $(II)$ được tính từ bảng $(I)$ như sau
\begin{equation}\label{e1.51}
  x'_i=\begin{cases}
    \frac{x^0_l}{a_{lk}}&\text{nếu}\; i=k\\
    x^0_i- \frac{x^0_l}{a_{lk}}a_{ik}&\text{nếu}\; i\ne k,
  \end{cases}
\end{equation}
\begin{equation}\label{e1.52}
  a'_{ij}=\begin{cases}
    \frac{a_{lj}}{a_{lk}}&\text{nếu}\; i=k\\
    a_{ij}- \frac{a_{lj}}{a_{lk}}a_{ik}&\text{nếu}\; i\ne k
  \end{cases}
\end{equation}
 \begin{equation}\label{e1.53}
   \Delta'_j=\Delta_j-\frac{a_{lj}}{a_{lk}}\Delta_{k}
 \end{equation}
và \begin{equation}\label{e1.54}
   f(X_1)=f(X_0)-\lambda_{0k}\Delta_k.
 \end{equation}
\begin{exm} Một xí nghiệp dự định sản xuất 2 loại sản phẩm $A$ và $B$ từ 3 loại nguyên liệu $I, II, III.$ Để sản xuất một đơn vị sản phẩm $A$ cần dùng $2$ đơn vị nguyên liệu loại $I$, $1$ đơn vị nguyên liệu loại $III$; tiền lãi thu được là $3$ đơn vị tiền. Để sản xuất 1 đơn vị  sản phẩm $B$, cần dùng $1$ đơn vị nguyên liêu loại $I$, $1$ đơn vị nguyên liệu loại $II$; tiền lại thu được là $5$ đơn vị tiền. Biết rằng lượng dự trử từng loại nguyên liệu tối đa có trong kho lần lượt là $8, 4, 3$ đơn vị. Hỏi xí nghiệp nên có kế hoạch sản xuất như thế nào để thu được tiền lãi lớn nhất mà không bị thiếu nguyên liệu.
\par Gọi $x_1$ là lượng sản phẩm  A được sản xuất ($x_1\geq 0$).  Gọi $x_2$ là lượng sản phẩm  B được sản xuất ($x_2\geq 0$). Khi đó,
ta cần  giải bài toán quy hoạch tuyến tính sau
 \begin{equation}\label{e1.58}
  \max\{f(X)=3x_1+5x_2\}
\end{equation}
\begin{equation}\label{e1.59}
\text{với điều kiện}\;  \begin{cases}
    2x_1+x_2\leq 8 \\ \quad\qquad x_2\leq 4\\x_1\quad\qquad\leq 3 \\ x_1, x_2\geq 0.
  \end{cases}
\end{equation}
Thuật toán đơn hình sử dụng để giải bài toán dạng chính tắc. Do vậy, việc đầu tiên của chúng ta là đưa bài toán về dạng chính tắc.
\begin{equation}\label{e1.60}
  \min\{\bar f(X)=-3x_1-5x_2\}
\end{equation}
\begin{equation}\label{e1.61}
\text{với điều kiện}\;  \begin{cases}
    2x_1+x_2+x_3\qquad\quad= 8 \\ \qquad \quad x_2 \qquad+x_4\quad= 4
    \\  x_1\qquad\qquad\quad\quad+x_5= 3
     \\ x_j\geq 0\;\forall j=\overline{1,5}.
  \end{cases}
\end{equation}
Ta có ma trận hệ số
\begin{equation}A=\begin{array}{ccccc}
    (A_1)&(A_2)&(A_3)&(A_4)&(A_5)\\
    \left[\begin{array}{c}2\\0\\ 1\end{array}\right. &\begin{array}{c}1\\1\\ 0\end{array}
    &  \begin{array}{c}1\\ 0\\ 0\end{array} &\begin{array}{c}0\\ 1\\ 0\end{array} &\left.\begin{array}{c}0\\ 0\\ 1\end{array}\right]\end{array}_{3\times 5}.
    \end{equation}
   Chọn hệ véc tơ cơ sở đơn vị $(A_3A_4A_5)$ liên kết với phương án cực biên xuất phát
   $$X_0=(0,0,0,8,4,3).$$
   Ta có bảng đơn hình.
   \begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
Bảng& Tọa độ&Hệ số&Toạn độ&-3&-5&0&0&0
\\
\cline{5-9}&$A_i$&$c_i$&$x_i$&$A_1$&$A_2$& $A_3$ &$A_4$&$A_5$
\\\hline
\hline&$A_3$&0&8&2&1&1&0&0
\\
(I)&$\Leftarrow A_4$&0&4&0&{\textcolor[rgb]{0.00,0.50,1.00}{\fbox{1 }}}&0&1&0
\\
&$A_5$&0&3&1&0&0&0&1
\\
\cline{2-9}
&&&0&3&\;$5\Uparrow$&0&0&0
\\
\hline\hline
&$\Leftarrow A_3$&0&4&\textcolor[rgb]{0.00,0.00,1.00}{\fbox{2}}&0&1&-1&0
\\
(II)&$A_2$
&-5
&
\textcolor[rgb]{0.98,0.00,0.00}{4}&\textcolor[rgb]{0.98,0.00,0.00}{0}
&\textcolor[rgb]{0.98,0.00,0.00}{1} &\textcolor[rgb]{0.98,0.00,0.00}{0}&\textcolor[rgb]{0.98,0.00,0.00}{1}
&\textcolor[rgb]{0.98,0.00,0.00}{0}
\\
&$A_5$&0&3&1&0&0&0&1
\\
\cline{2-9}
&&&-20&$3\Uparrow$&0&0&-5&0
\\
\hline\hline
&$A_1$&-3&\textcolor[rgb]{1.00,0.00,0.00}{2}
&\textcolor[rgb]{0.98,0.00,0.00}{1}&
\textcolor[rgb]{0.98,0.00,0.00}{0}&\textcolor[rgb]{0.98,0.00,0.00}{$\frac12$}
&\textcolor[rgb]{0.98,0.00,0.00}{$\frac{-1}2$}&\textcolor[rgb]{1.00,0.00,0.00}{0}
\\
(III)&$A_2$
&-5
&
4&0
&1 &0&1
&0
\\
&$A_5$&0&1&0&0&$\frac{-1}2$&$\frac12$&1
\\
\cline{2-9}
&&&-26&0&0&$\frac{-3}{ \,2}$&$\frac{-7}{\,2}$&0
\\
\hline
\end{tabular}
\end{center}
Tại bảng $(III)$ ta có $\Delta_j\leq 0$ với mọi $j=\overline{1,5}.$ Do đó, bài toán dạng chính tắc \eqref{e1.60} và \eqref{e1.61} có phương án tối ưu là
$$X_2=(2,4,0,0,1); \;\; f_{\min}=\bar f(X_2)=-26.$$
Do vậy,  bài toán gôc \eqref{e1.58} và \eqref{e1.59} có phương án tối ưu là
$$X^*=(2,4); \;\; f_{\max}=f(X^*)=26.$$
Đến đây chúng ta có thể đưa ra dự báo cho mô hình sản xuất  là  xí nghiệp nên sản xuất $2$ sản phẩm $A$ và $4$ sản phẩm $B$ thì lợi nhuận thu được lớn nhất $f_{\max}=26$ đơn vị tiền và khi đó từ phương án tối ưu của bài toán chính tắc chúng ta thấy nguyên liệu loại $I$ và $II$ được sử dụng hết, nguyên liệu loại $III$ thừa $1$ đơn vị.
\end{exm}
\begin{rem} Trong bảng đơn hình, nếu $A_j$ trong cơ sở chúng ta luôn có $a_{jj}=1, a_{ij}=0, \; \forall\; i=\overline{1,m}, i\ne j$ và $\Delta_j=0.$
\end{rem}
%\subsection{Tìm phương án cực biên xuất phát}
Trong thuật toán trên chúng ta giả thiết rằng đã có một phương án cực biên $X_0$ liên kết vớ một hệ vecs tơ cơ sở đơn vị. Để có đuowcj điều này chúng ta cần ma trận hệ số $A$ chứa ma trận con đơn vị cấp $m$. Tuy nhiên rất nhiều bài toán không thỏa mãn điều này. Trong 
trường hợp đó, chúng ta thêm các ẩn giả tạo $x_{n+i}\geq 0$ với hệ số $c_{n+i}=M>0$ đủ lớn, biến đổi bài toán \eqref{e1.34}\eqref{e1.35}, thành bài toán  giả tạo (M):
\begin{equation}\label{e2.49}
  \min\{f(X)=\sum_{j=1}^nc_jx_j+M\sum_{i=1}^nx_i\}
\end{equation}
với điều kiện
\begin{equation}\label{e2.50}
  \begin{cases}
    x_{n+i}+\sum\limits_{j=1}^n a_{ij}x_j=b_i, i=\overline{1,m,}
    \\ x_j\geq 0, j=1,2, \ldots, n,
  \end{cases}
\end{equation}
Khi đó, ma trận hệ số của \eqref{e2.50} là 
\begin{equation*}A=\begin{array}{cccccccc}
    (A_1)&(A_2)&\ldots&(A_n)&(A_{n+1})&(A_{n+2})&\ldots&(A_{n+m})\\
    \left[\begin{array}{c}a_{11}\\a_{21}\\ \vdots\\a_{m1}\end{array}\right. &\begin{array}{c}a_{12}\\a_{22}\\ \vdots\\a_{m2}\end{array} & \begin{array}{c}\ldots\\ \ldots\\ \vdots\\ \ldots\end{array} &\begin{array}{c}a_{1n}\\ a_{2n}\\ \vdots\\ a_{mn}\end{array}&\begin{array}{c}1\\0\\ \vdots\\0\end{array}&\begin{array}{c}0\\1\\ \vdots\\0\end{array}&\begin{array}{c}\ldots\\ \ldots \\ \vdots\\ \ldots\end{array}&\left.\begin{array}{c}0\\0\\ \vdots\\1\end{array}\right]\end{array}_{m\times (n+m)},
    \end{equation*}
 và  ta có phương án cực biên
    $$X_0=\left( 0,\ldots,0, x_{n+1}^0, x_{n+2}^0,\ldots,x_{n+m}^0\right),\; x_{n+i}^0=b_i, \, i=1,2,\dots, m$$
    với hệ véc tơ cơ sở là $(A_{n+1} A_{n+2}\ldots A_{n+m})$ tạo thành ma trận đơn vị. Từ đó ta giải được bài toán \eqref{e2.49}\eqref{e2.50} bằng phương pháp đơn hình. Từ kết quả giải bài toán này ta có thể suy ra được kết quả đối với bài toán \eqref{e1.34}\eqref{e1.35} bới mệnh đề sau
\begin{prop}[Mối liên hệ giữa bài toán giả tạo và bài toán gốc] Tồn tại số thực $M_0 > 0$ đủ lớn sao cho với mọi  $M > M_0,$ 

i) Nếu bài toán giả tạo \eqref{e2.49}\eqref{e2.50} không có phương án tối ưu thì bài toán gốc \eqref{e1.34}\eqref{e1.35} cúng không có phương án tối ưu.

ii)    Nếu bài toán giả tạo \eqref{e2.49}\eqref{e2.50}  có phương án tối ưu tại phương án tối ưu tồn tại ẩn giả tạo $x_{n+i} > 0$ thì tập phương án của bài toán\eqref{e1.34}\eqref{e1.35} bằng rỗng. 

iii) {Bài toán \eqref{e1.34}\eqref{e1.35} có phương án tối ưu $X$ khi và chỉ khi bài toán giả tạo \eqref{e2.49}\eqref{e2.50} có phương án tối ưu $\overline{X}  = (X, \theta)$}.

Ở đây $(X, \theta)$ ký hiệu cho $n+m$ tọa độ, trong đó $n$ tọa độ đầu là điểm $X$, $m$ tọa độ cuối đều bằng $0$.
\end{prop}

\begin{exm} Một xưởng làm cữa sắt có những thanh thép dài 17 m, cần cắt thành 64 đoạn dài 7 mét, 84 đoạn dài 5 mét và 12 đoạn dài 9 mét. Có 5 mẫu cắt sau:
\par \textbf{Mẫu 1}:  2 đoạn 7 mét,  thừa 3 mét.
\par \textbf{Mẫu 2}:  1 đoạn 7 mét và 1 đoạn 9 mét, thừa 1 mét.
\par \textbf{Mẫu 3}:  1 đoạn 7 mét và 2 đoạn 5 mét, không thừa.
\par \textbf{Mẫu 4}:  1 đoạn 9 mét và 1 đoạn 5 mét, thừa 3 mét.
\par \textbf{Mẫu 5}:  3 đoạn 5 mét, thừa 2 mét.
\par Hỏi xưởng làm cữa sắt nên chọn mẫu cắt như thế nào để có thép thừa ít nhất mà vẫn có đủ số lượng thanh thép cần dùng.
\\ \emph{Giải.} Gọi $x_i$ là số lần chọn mẫu cắt $i,  (x_i\geq 0).$ Khi đó ta có bài toán: Tìm $X=(x_1, x_2, x_3, x_4, x_5)$ sao cho
\begin{equation}\label{e3.51}
\min\{3x_1+x_2+3x_4+2x_5\}
\end{equation}
\begin{equation}\label{e3.52}
\text{với điều kiện}\begin{cases} 2x_1+x_2+x_3&=64\\
\hspace{2cm}2x_3+x_4+3x_5&=84
\\\hspace{1.5cm}x_2\hspace{.9cm}+x_4&=12.
\end{cases}
\end{equation}
Bằng một phép biến đổi đơn giản hệ điệu kiện trên  tương đương với

$$\text{với điều kiện}\begin{cases} x_1+\frac12x_2+\frac12x_3&=32\\
\hspace{2cm}\frac23x_3+\frac13x_4+x_5&=28
\\\hspace{1.3cm}x_2\hspace{.9cm}+x_4&=12.
\end{cases}
$$
Ta có  ma trận hệ số là 
\begin{equation*}A=\begin{array}{ccccc}
    (A_1)&(A_2)&(A_3)&(A_4)&(A_5)\\
    \left[\begin{array}{c}1\\0\\ 0\end{array}\right. &\begin{array}{c}\frac12\\0\\ 1\end{array}
    &  \begin{array}{c}\frac12\\ \frac23\\ 0\end{array} &\begin{array}{c}0\\ \frac13\\ 1\end{array} &\left.\begin{array}{c}0\\ 1\\ 0\end{array}\right]\end{array}_{3\times 5}.
    \end{equation*}
Từ ma trận hệ số chúng ta chỉ mới có 2 véc tơ đơn vị 
$$A_1=\begin{bmatrix}1\\0\\0\end{bmatrix}\;\text{ và }\; A_5=\begin{bmatrix}0\\1\\0\end{bmatrix}.$$ 
Do đó, chúng ta còn thiếu $1$ véc tơ đơn vị để lập được một hệ véc tơ cơ sở đơn vị nên chúng ta thêm $1$ ẩn giả tạo $x_6$ vào phương trình thứ $3$ của hệ điều kiện ta được bài toán giả tạo
$$\min\{3x_1+x_2+3x_4+2x_5+Mx_6\}$$
 $$\text{với điều kiện}\begin{cases} x_1+\frac12x_2+\frac12x_3&=32\\
\hspace{2cm}\frac23x_3+\frac13x_4+x_5&=28
\\\hspace{1.3cm}x_2\hspace{.9cm}+x_4\hspace{.9cm}+x_6&=12.
\end{cases}
$$
Ta có ma trận hệ số của bài toán giả tạo là
\begin{equation*}A=\begin{array}{cccccc}
    (A_1)&(A_2)&(A_3)&(A_4)&(A_5)&(A_6)\\
    \left[\begin{array}{c}1\\0\\ 0\end{array}\right. &\begin{array}{c}\frac12\\0\\ 1\end{array}
    &  \begin{array}{c}\frac12\\ \frac23\\ 0\end{array} &\begin{array}{c}0\\ \frac13\\ 1\end{array} &\begin{array}{c}0\\ 1\\ 0\end{array}&\left.\begin{array}{c}0\\ 0\\ 1\end{array}\right]\end{array}_{3\times 6}.
    \end{equation*}
Chọn hệ véc tơ cơ sở đơn vị $(A_1A_5A_6)$ liên kết với phương án cực biên xuất phát
   $$X_0=(32,0,0,0,0,28, 12).$$
   Ta có bảng đơn hình.
   \begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
Bảng& Tọa độ&Hệ số&Toạn độ&3&1&3&0&2
\\
\cline{5-9}&$A_i$&$c_i$&$x_i$&$A_1$&$A_2$& $A_3$ &$A_4$&$A_5$
\\\hline
\hline&$\;\;\;\;A_1$&3&32&1&$\frac12$&$\frac12$&0&0
\\
(I)&$ \;\;\;\;A_5$&2&28&0&0&$\frac23$&$\frac13$&1
\\
&$\Leftarrow A_6$&M&12&0&\textcolor[rgb]{0.00,0.00,1.00}{\fbox{1}}&0&1&0
\\
\cline{2-9}&&&152&0&$\frac12$&$\frac{17}6$&$\frac{-7}3$&0
\\\cline{4-9}
&&&12&0&\;$1\Uparrow$&0&1&0
\\
\hline\hline
&$ \;\;\;\;A_1$&3&$6$&1&0&$\frac12$&$\frac{-1}2$&0
\\
(II)&$\Leftarrow A_5$
&2
&28&
0&0
&$\frac23$ &$\frac13$&1
\\
&$\;\;\;\;A_2$&1&\textcolor[rgb]{0.98,0.00,0.00}{12}&\textcolor[rgb]{0.98,0.00,0.00}{0}&\textcolor[rgb]{0.98,0.00,0.00}{1}&\textcolor[rgb]{0.98,0.00,0.00}{0}&\textcolor[rgb]{0.98,0.00,0.00}{1}&\textcolor[rgb]{0.98,0.00,0.00}{0}
\\
\cline{2-9}
&&&146&0&0&$\frac{17}6\Uparrow$&$\frac{-17}6$&0
\\
\hline\hline
&$A_1$&3&5
&1&
0&0
&$\frac{-3}4$&$\frac{-3}4$
\\
(III)&$A_3$
&0
&
\textcolor[rgb]{1.00,0.00,0.00}{42}&\textcolor[rgb]{1.00,0.00,0.00}{0}
&\textcolor[rgb]{1.00,0.00,0.00}{0} &\textcolor[rgb]{1.00,0.00,0.00}{1}&\textcolor[rgb]{1.00,0.00,0.00}{$\frac12$}
&\textcolor[rgb]{1.00,0.00,0.00}{$\frac32$}
\\
&$A_2$&1&12&0&1&0&1&0\\
\cline{2-9}
&&&27&0&0&0&$\frac{-17}4$&$\frac{-17}{\,4}$
\\
\hline
\end{tabular}
\end{center}
Tại bảng $(III)$ ta có $\Delta_j\leq 0$ với mọi $j=\overline{1,5}$ và ẩn giả tạo không xuất hiện ở bảng cuối cùng.  Do đó, bài toán  \eqref{e3.51} \eqref{e3.52} có phương án tối ưu là
$$X_2=(5,12,42,0,0); \;\; f_{\min}=\bar f(X_2)=27.$$
Đến đây chúng ta có thể đưa ra dự báo cho cơ sở  sản xuất  là   nên sản sử dụng  $5$ lần chọn mẫu cắt $1$, $12$ lần mẫu $2$,  $42$ lần mẫu $3$, khong dùng mẫu $4$ và $5$ sẽ thu số thanh thép như mong muốn và số thép lảng phí ít nhất là  $f_{\min}=27m$.
\end{exm}
\begin{rem} Vì chúng ta cần có đủ $m$ véc tơ đơn vị để tạo thành một hệ cơ sở đơn vị. Do đó nếu trong ma trận hệ số đã chứa $k$ véc tơ đơn vị thì ta chỉ cần thêm $m-k$ ẩn giả tạo.

Ở bảng đầu tiên các véc tơ đơn vị ứng với ẩn giả tạo luôn ở trong cơ sở nên  các $\Delta_{n+i}=0.$ Do đó ta không cần tính cột $n+i.$ Nếu ở bảng cuối cùng có $\Delta_j\leq 0,\; \forall\; i=\overline{1, n}$ mà vẫn còn $A_{n+i}$ trong hệ cơ sở thì bài toán gốc ban đẫu  không có phương án tối ưu (tập phương án bằng rỗng).  

Nếu ở bảng cuối cùng, trong hệ cơ sở không chứa $A_{n+i}$ thì bài toán gốc có phương án tối ưu được lấy ra từ bảng cuối cùng.

\end{rem}
\section{Phương pháp đơn  hình đối ngẫu}
\subsection{Cặp bài toán đối ngẫu}
\subsection{Phương pháp đơn hình đối ngẫu}
\section{Bài tập chương 2}
\begin{prob}
Một nhà máy sản xuất phân bón có thể sản xuất $2$ loại sản phẩm: Phân Lân  và Phân Kali. Nếu chỉ sản xuất một loại  thì nhà máy chỉ sản xuất được $40$ tấn phân lân hoặc $28$ tấn phân Kali trong 1 giờ. Lợi nhuận thu được khi bán một tấn phân lân là $250$ USD, một tấn phân Kali là $300$ USD. Nhà máy làm việc $40$ giờ trong tuần và thị trường tiêu thụ tối đa là $1200$  tấn phân Lân và $812$  tấn phân Kali trong một tuần. Hỏi nhà máy nên có kế hoạch sản xuất như thế nào để thu được lợi nhuận lớn nhất.
    \end{prob}
   \begin{prob} Một xưởng làm cữa sắt có những thanh thép dài 17 m, cần cắt thành 384 đoạn dài 7 mét, 84 đoạn dài 5 mét và 48 đoạn dài 9 mét. Có 5 mẫu cắt sau:
\par \textbf{Mẫu 1}:  2 đoạn 7 mét,  thừa 3 mét.
\par \textbf{Mẫu 2}:  1 đoạn 7 mét và 1 đoạn 9 mét, thừa 1 mét.
\par \textbf{Mẫu 3}:  1 đoạn 7 mét và 2 đoạn 5 mét, không thừa.
\par \textbf{Mẫu 4}:  1 đoạn 9 mét và 1 đoạn 5 mét, thừa 3 mét.
\par \textbf{Mẫu 5}:  3 đoạn 5 mét, thừa 2 mét.
\par Hỏi xưởng làm cữa sắt nên chọn mẫu cắt như thế nào để có thép thừa ít nhất mà vẫn có đủ số lượng thanh thép cần dùng.
\end{prob}
\begin{prob} Một nhà đầu tư có 20 tỉ đồng muốn đầu tư vào 4 lĩnh vực:
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
Lĩnh vực đẩu tư& Chứng khoán&Công trái&Gửi tiết kiệm&Bất động sản\\
\hline
Lãi suất trên năm& $20\%$&$12\%$& $15\%$ &$18\%$
\\
\hline
\end{tabular}
\end{center}
Ngoài ra để giảm thiểu rủi ro nhà đầu tư cho rằng không nên đầu tư vào chứng khoán vượt quá $30\%$ tổng số vốn; đầu tư vào công trái và tiết kiệm ít nhất là $25\%$ tổng số vốn; gửi tiết kiệm ít nhất 2 tỉ đồng. Hãy xác định kế hoạch phân bổ vốn đầu tư sao cho thu nhập hàng năm là lớn nhất.
\end{prob}
\begin{prob}
{Một cơ sở dự định sản xuất tối đa trong một ngày 450 ổ bánh mì dài và 500 ổ bánh mì tròn với điều kiện như sau
\\ - Giá một ổ bánh mì dài làm từ 400 g bột là 3250 đồng, một ổ bánh mì tròn làm từ 250 g bột là 2200 đồng.
\\ - Số lượng bột được cung cấp tối đa trong ngày là 225 kg, với giá mỗi kg là 3000 đồng.
\\- Lò nướng bánh mì cho phép nướng 75 ổ bánh mì dài hoặc 100 ổ bánh mì tròn trong 1 giờ nhưng không thể nướng 2 loại cùng một lúc. Lò nướng hoạt động tối đa 8 giờ trong ngày. Hỏi cơ sở  bánh mì nên tổ chức sản xuất như thế nào để thu được tiền lời nhiều nhất.}
\end{prob}
\begin{prob} Một xý nghiệp có thể sử dụng tối đa 510 giờ máy cán, 360 giờ máy tiện và 150 giờ máy mài để chế tạo 3 loại sản phảm A,  B và C. Để tạo ra một sản phẩm A cần 9 giờ máy cán, 5 giờ máy tiện 3 giờ máy mài; một đơn vi sản phẩm B cần 3 giờ máy cán, 4 giờ máy tiện; một đơn vị sản phẩm C cần 5 giờ máy cán, 3 giờ máy tiện, 2 giờ máy mài. Mỗi sản phẩm A trị giá 48 nghìn đồng, mỗi sản phẩm B trị giá 16 nghìn đồng và mỗi sản phẩm C trị giá 27 nghì đồng. Hỏi xí nghiệp nên sản xuất thế nào đê cho tổng tiền thu về nhiều nhất. Cho biết số giờ còn lại của các máy  trong trường hợp tối ưu.
 \end{prob}
\begin{prob}
  Nhằm mục đích giảm thiểu chi phí để đáp ứng nhu cấu về protein, viatimin và sắt với một khẩu phần thức ăn được hạn chế trên bởi táo, chuối, cà rốt, rau và trứng. Chi phí và giá trị dinh dưỡng có trong 5 loại thức ăn được cho ở bảng sau:
  \begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
Thức ăn& Đơn vị(đv)&Protein&Vitamin&Sắt&Giá thành\\
&& g/đv& g/đv& g/đv&đồng/đv\\
\hline
Táo&quả&0,4&6&0,4&8\\
\hline
Chuối&quả&1,2&10&0,6&10\\
\hline
Rau&kg&0,6&3&0,4&3\\
\hline
Trứng&quả&12.2&0&2,6&15\\
\hline
\end{tabular}
\end{center}
  \par Chế độ ăn uống hằng ngày đòi hỏi tối thiểu $70$ mg protein, $50$ mg Vitamin C, $12$ mg sắt.
  Hãy cho biết nên tạo khẫu phần thức ăn như thế nào để đủ chất dinh dưỡng mà giá thành rẻ nhất.
\end{prob}
\begin{prob} Để đảm bảo cho vật nuôi phát triển bình thường người chăn nuôi phải cung cấp tối thiểu cho vật nôi 60 đơn vị chất dinh dưỡng A, 84 đơn vị chất dinh dưỡng B, 72 đơn vị chất dinh dưỡng C mỗi ngày. Người chăn nuôi có thể mua thức ăn cho vật nuôi từ 3 nguồn khác nhau. Lượng chất dinh dưỡng mỗi loại cũng như giá thành của một đơn vị thức ăn của mỗi nguồn thức ăn được cho ở bảng sau:
    \begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
Thức ăn&A&B&C&Giá \\
\hline
Nguồn 1&3&7&3&10\\
\hline
Nguồn 2&2&2&6&4\\
\hline
Nguồn 3&5&3&4&7\\
\hline
\end{tabular}
\end{center}
Hỏi người chăn nuôi nên có kế hoạch chọn thức ăn như thế nào để chi phí rẻ nhất mà vẫn đảm bảo được chất dinh dưỡng cho vật nuôi.
\end{prob}
\begin{prob}
  Một nhà sản xuất sơn cần tạo ra một loại sản phẩm sơn nước. Để tạo ra được loại sơn này thì phải có 4 loại hoá chất A, B, C và D. Thành phần trong loại sơn này phải chứa ít nhất $5\%$ hoá chất $A$, $3\%$ hoá chất $B$,  $26\%$ hoá chất $C$ và không quá $15\%$ hoá chất $D$. Để có được điều này các nhà sản xuất phải kết hợp 3 loại khoáng sản thô. Thành phần hoá chất có trong một đơn vị khoáng sản thô và chi phí để mua một đơn vị khoáng sản thô được cho ở bảng sau:
    \begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
Khoáng sản&\multicolumn{4}{|c|}{Hoá chất }&Giá \\
\cline{2-5}&A&B&C&D&\\
\hline
I&0&5&30&20&40\\
\hline
II&6&8&30&10&75\\
\hline
III&7&0&25&16&30\\
\hline
\end{tabular}
\end{center}
Hãy xây dựng kế hoạch sản xuất sơn sao cho giá thành rẻ nhất.
\end{prob}
\begin{prob} Đồng tiền xu được đúc chứa ít nhất $40\%$ bạc và ít nhất $50\%$ đồng tỉ lệ bạc và đồng có trong các loại hợp kim $A, B, C$ và $D$ cũng như giá từng loại hợp kim được cho trong bảng sau
\begin{center}
\begin{tabular}{|l|c|c|c|c|}
\hline
Hơpk kim&A&B&C&D\\
\hline
$\%$ Bạc&30&35&50&40\\
\hline
$\%$ Đồng&60&35&50&45\\
\hline
Giá (USD)&11&12&16&14\\
\hline
\end{tabular}
\end{center}
Hãy xây dựng kế hoạch đúc đồng cu từ các hợp kim sao cho tổng chi phí bé nhất.
\end{prob}
\begin{prob}
Một phụ gia nguyên liệu phải có ít nhất $32\%$ hoá chất $A,$ ít nhất $15\%$ và không quá $40\%$ chất trơ $C.$ Để sản xuất phụ gia người ta sẽ điều chế các hoá chất từ 4 loại nguyên liệu W, X, Y và Z. Thành phần hoá chất có trong một đơn vị nguyên liệu và giá một của mối đơn vị nguyên liệu được cho trong bảng sau.
\begin{center}
\begin{tabular}{|l|c|c|c|c|}
\hline
Nguyên liệu&W&X&Y&X\\
\hline
$\%$ Hoá chất A&45&25&28&36\\
\hline
$\%$ Hoá chất B&22&10&0&16\\
\hline

$\%$ Hoá chất C&20&42&44&27\\
\hline
Giá (USD/đv)&35&5&10&15\\
\hline
\end{tabular}
\end{center}
\end{prob}
\par Hỏi nên sản xuất chất phụ gia như thế nào để chi phí rẻ nhất.
\begin{prob}
Một nhà máy sản xuất ba loại thịt: bò, lợn và cừu với số lượng sản xuất mỗi ngày là 480 tấn thịt bò, 400 tấn thịt lợn, 230 tấn thịt cừu. Mỗi loại đều có thể bán được ở dạng tươi hoặc nấu chín. Tổng các loại thịt có thể nấu chín để bán là 420 tấn trong giờ và 250 tấn ngoài giờ. Lợi nhuận thu được từ việc bán một tấn mỗi loại thịt được cho trong bảng sau
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
Loại thịt&Bò &Lợn&Cừu\\
\hline Tươi & 8&14&11\\
\hline
Nấu chín trong giờ&4&12&7\\
\hline
 Nấu chín ngoài giờ&4&13&9\\
\hline
\end{tabular}
\end{center}
Hỏi nhà máy nên sản xuất như thế nào để thu được lợi nhuận cao nhất.
\end{prob}
\begin{prob} Một trại chăn nuôi dự định nuôi 3 loại bò: Bò thịt, bò cày và bò sữa. Số liệu điều tra được cho ở bảng sau với đơn vị tính nghìn đồng/ con:
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
&Bò sữa&Bò cày&Bò thịt&Dự trữ\\
\hline Vốn & 123&167&162&7020\\
\hline
Chi phí chăn nuôi&18&15& 15&800\\
\hline
Lãi & 59& 49&57& \\
\hline
\end{tabular}
\end{center}
 \par Hỏi trại chăn nuôi nên có kế hoạch nuôi bò như thế nào để thu được tiền lãi nhiều nhất. Biết rằng số bò sữa không quá 18 con.
\end{prob}
\begin{prob} Một chủ nông trại sở hữu 100 mẫu đất dự định trồng 3 loại cây Cao su, Cà phê, Ca cao. Chi phí hạt giống số ngày công chăm sóc và lợi nhuận thu được trên một mẫu đất trồng được cho ở bảng sau
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
&Cao su&Cà phê&Ca cao\\
\hline Chi phí giống & $40\$$&$20\$$&$30\$$\\
\hline
Nhân công&10 ngày&10 ngày& 10 ngày\\
\hline
Lãi & $300\$$& $100\$$&$200\$$ \\
\hline
\end{tabular}
\end{center}
\par Hỏi nông trại nên trồng mỗi loại bao nhiêu để loại nhuận thu được nhiều nhất. Biết rằng chủ nông trại có thể huy động tối đa $3200\$$ và 160 ngày công.
\end{prob}

\begin{prob} Một hãng sản xuất đồ chơi trẻ em có thể sản xuất bốn loại xe khác nhau: xe thư, xe cẩu, xe ủi và xe bồn. Để sản xuất ra mỗi loại xe trên cần sử dụng 3 loại máy:Máy dập, máy phun sơn và máy đóng gói. Mức tiêu hao thời gian (giờ) cho mỗi loại xe và lợi nhuận thu đươc cho ở bảng sau:
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
Mức tiêu hao thời gian và lợi nhuận&Xe thư&Xe cẩu&Xe ủi& Xe bồn\\
\hline Máy dập & 2 giờ&2,5 giờ&2 giờ& 2 giờ\\
\hline
Máy phun sơn & 1 giờ&1,5 giờ&1 giờ& 2 giờ\\
\hline
Máy đóng gói  & 0,5 giờ&0,5 giờ&1 giờ& 1 giờ \\
\hline
Lợi nhuận&$0,5\$$&$1\$$&$1,5\$$&$2\$$
\\
\hline
\end{tabular}
\end{center}
\par Công suất tối đa/ tuần của: Máy dập 4000 giờ, máy phun sơn 1800 giờ, máy đóng gói, máy đóng gói 1000 giờ. Hỏi cơ sở nên sản xuất như thế nào để thu được lợi nhuân lớn nhất.
\end{prob}
\begin{prob}
Một công ty chuyên xản xuất 3 loại sản phẩm A, B, C. Trong đó nguyên liệu để sản xuất 3 loại sản phẩm trên được nhập tử 2 nguồn $N_1$ và $N_2$. Chi phí cho mỗi đơn vị nguyên liệu nhập từ $N_1$ là $100\;\$$ và từ nguồn $N_2$ là $90\;\$.$ Các loại sản phẩm sản xuất cần các đơn vị nguyên liệu của từng nguồn được cho bởi bảng sau:
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
Nguồn nguyên liệu&\multicolumn{3}{|c|}{{ Loại sản phẩm}}\\
\cline{2-4}& \quad A\quad\;&\;\quad B\quad \quad& C\quad\\
\hline
$N_1$&100&200&300\\
\hline
$N_1$&200&100&200\\
\hline
\end{tabular}
\end{center}
Biết rằng, trong thời gian tới cần sản xuất tối thiểu $20000$ sản phẩm loại $A$;  $18000$ sản phẩm loại $B$; $15000$ sản phẩm loại $C$. Hãy lập  kế hoạch sản xuất sao cho chi phí công ti phải bỏ ra là nhỏ nhất mà vẫn đảm bảo về yêu cầu sản phẩm.
\end{prob}
\chapter{Một số mô hình tuyến tính đặc biệt}
\section{Bài toán vận tải}
\subsection{Bài toán vận tải cổ điển}

Có $m$ nhà phân phối một loại hàng. Lượng hàng có thể cung cấp ở nhà phân phối $i, \; i=\overline{1, m}$ là $a_i.$ Cần phân phối loại hàng này đến $n$ cữa hàng tiêu thụ. Cữa hàng thứ $j, \; j=\overline{1, n} $ cần lượng hàng là $b_j.$ Cước phí vận chuyển 1 đơn vị hàng từ nhà phân phối $i$ đến cữa hàng $j$ là $c_{ij},\; \forall\, i=\overline{1, m}; j=\overline{1, n}.$ Hãy lập kế hoạch phân phối hàng sao cho tổng cước phí vận chuyển bé nhất sao cho các nhà phân phối phát hết hàng và các cữa hàng nhận đủ hàng.
      \\ \underline{\emph{Thiết lập mô hình}:}
\par Gọi $x_{ij}$ là lượng hàng được vận chuyển từ nhà phân phối  $i\, (i=\overline{1, m})$ đến cữa hàng $j  \,(j=\overline{1,n})$ ($x_{ij}\geq 0$). Khi đó,
\begin{itemize}
  \item Tổng cước phí vận chuyển là
  $$f(x)=\sum_{i=1}^m\sum_{j=1}^nc_{ij}x_{ij}$$
  \item Lượng mà nhà phân phối $i$ phát đi là
  $$\sum_{j=1}^nx_{ij}= a_i\;\;i=\overline{1, m}.$$
 \item Lượng mà cữa hàng $j$ nhận được là
  $$\sum_{i=1}^mx_{ij}= b_j\;\;j=\overline{1, n}.$$
  \end{itemize}
Vậy ta có bài toán thể hiện kế hoạch phân phối hàng là
\begin{equation}
  \min\{f(x)=\sum_{i=1}^m\sum_{j=1}^nc_{ij}x_{ij}\}
\end{equation}
với điều kiện
\begin{equation}
  \begin{cases}
    \sum\limits_{j=1}^nx_{ij}= a_i\;\;i=\overline{1, m}\\
    \sum\limits_{i=1}^mx_{ij}= b_j\;\;j=\overline{1, n}
    \\ x_{ij}\geq 0, \;\, \forall\, i=\overline{1, m}, j=\overline{1, n}
  \end{cases}
\end{equation}
Để thuận tiện cho việc tính toán người ta có thể biểu diễn bài toán
\subsection{Tính chất của bài toán vận tải}
\begin{thm}
  Bài toán vận tải  có phương án tối ưu khi và chỉ kho cân bằng thu phát, nghĩa là
  $$\sum_{j=1}^na_j=\sum_{i=1}^mb_i.$$
\end{thm}
\section{Bài toán sản xuất đồng bộ}
\subsection{Bài toán}
 Có $m$ máy công cụ, tham gia sản xuất một loại sản phẩm gồm $n$  chi tiết khác nhau. Số máy mỗi loại tham gia quá trình được giả thiết là $1$ chiếc, số chi tiết được cấu thành sản phẩm được chia theo tỉ lệ $1:1$ (do vậy có thể coi số chi tiết mỗi loại cấu thành sản phẩm là 1). Năng suất máy thứ $i$ sản xuất chi tiết thứ $j$ là $s_{ij}$ (số đơn vị chi tiết/ đơn vị thời gian) $i=1,2,\ldots,m,\;j=1,2,\ldots,n.$ Hãy bố trí thời gian để các máy sản xuất các chi tiết, sao cho số sản phẩm đủ bộ (đồng bộ) được nhiều nhất.
\\ \underline{\emph{Thiết lập mô hình}:}
\par Gọi $x_{ij}$ là phần thời gian trong một đơn vị thời gian kế hoạch của may $i$ sản xuất chi tiết $j$ ($x_{ij}\geq 0,\;\;i=\overline{1,m},\; j=\overline{1,n}$).
\par +) Tổng thời gian máy $i$ thực hiện sản xuất là $\sum\limits_{j=1}^{n}x_{ij}\textcolor[rgb]{0.00,0.00,1.00}{\leq 1}.$
\par+) Số chi tiết $j$ được sản xuất là
$$f_j=\sum_{i=1}^ma_{ij}x_{ij},\;\;j=\overline{1,n}.$$
\par+) Số sản phẩm đủ bộ sẽ là
$$f=\min\{f_j:\;j=\overline{1,n}\}=\min\{\sum_{i=1}^ma_{ij}x_{ij}: j=\overline{1,n}\}.$$
\par \emph{\underline{\textcolor[rgb]{0.98,0.00,0.00}{Bài toán đặt ra là:}}} Tìm $X=(x_{ij}; i=\overline{1,m};\; j=\overline{1,n})$ sao cho
$$f(X)=\max f=\max\{\min\sum_{i=1}^ma_{ij}x_{ij}\}$$
$$\text{với điều kiện}\;\begin{cases}
  \sum_{j=1}^nx_{ij}\leq 1,\;i=\overline{1,m}\\
  x_{ij}\geq 0,\;\;i=\overline{1,m},\; j=\overline{1,n}.
\end{cases}$$
Chú ý rằng từ điều kiện
$$f=\min\left\{\sum_{i=1}^ma_{ij}x_{ij}:\;\;j=\overline{1,n}\right\}.$$
suy ra,
$$f\leq \sum_{i=1}^ma_{ij}x_{ij}:\;\;j=\overline{1,n}.$$
Hay
$$- \sum_{i=1}^ma_{ij}x_{ij}+f\leq 0\;\;j=\overline{1,n}.$$
Do vậy bài toán được viết lại là: \emph{Tìm $X=(x_{ij}; i=\overline{1,m};\; j=\overline{1,n})$ và $f$ sao cho}
\begin{equation}\label{e3.3}
\max f
\end{equation}
\begin{equation}\label{e3.4}
\text{với điều kiện}\;\begin{cases}
  \sum_{j=1}^nx_{ij}\leq 1,\;i=\overline{1,m}\\
 - \sum_{i=1}^ma_{ij}x_{ij}+f\leq 0\;\;j=\overline{1,n}
 \\ x_{ij}\geq 0,\;\;i=\overline{1,m},\; j=\overline{1,n}.
\end{cases}\end{equation}
Bài toán \eqref{e3.3}\eqref{e3.4} là bài toán quy hoạch tuyến tính có thể giải bằng phương pháp đơn hình. Ta có ma trận hệ số của hệ điều kiện \eqref{e3.4} là
$$
\hskip-.8cm\left(\hskip-.5cm
  \begin{array}{cccccccccccccc}
    1&1&\ldots&1&0&0&\ldots&0&\ldots&0&0&\ldots&0&0\\
    0 & 0 & \ldots & 0 & 1 & 1 & \ldots & 1 & \ldots & 0 & 0 &\ldots & 0 & 0  \\
    \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots &
     \ldots & \ldots & \ldots & \ldots  \\
    0 & 0 & \ldots & 0 & 0 & 0 & \ldots & 0 & \ldots & 1 & 1 & \ldots & 1 & 0  \\
    -a_{11} &0& \ldots &0& -a_{21} & 0 & \ldots & 0 & \ldots & -a_{m1} & 0 & \ldots & 0 & 1   \\
    0 &  -a_{12} &\ldots&0&0& -a_{22}&\ldots&0&\ldots&0&-a_{m2}&\ldots&0&1\\
\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots\\
         0&0&\ldots&-a_{1n}&0&0&\ldots&-a_{2n}&\ldots&0&0&\ldots&-a_{mn}&1\\
  \end{array}
\hskip-.3cm\right)$$
\par Trong thực tế số ẩn của bài toán này khá lớn nên việc tính toán trên bảng đơn hình sẽ gặp khó khăn. Để giải bài toán này người ta vận dụng lý thuyết đối ngẫu và tính chất đặc biệt của bài toán.
\par Để thuận tiện trong các lập luận, không mất tính tổng quát chúng ta có thể giả thiết rằng với mỗi $i,$ mỗi $j$ đều tồn tại $a_{ij}>0$ (mỗi chi tiết $j$ phải được sản xuất ít nhất một máy và mỗi máy $i$ phải sản xuất ít nhất một chi tiết).
\par \underline{\emph{Bài toán đối ngẫu }}
\par Bài toán đối ngẫu của bài toán bài toán sản xuất đồng bộ \eqref{e3.3}\eqref{e3.4} là:
\emph{Tìm các bộ số $u_1, u_2,\ldots, u_m, v_1,v_2,\ldots, v_n$ sao cho}
\begin{equation}\label{e3.5}
  \min\{\sum_{i=1}^mu_i\}
\end{equation}
\begin{equation}\label{e3.6}
  \text{với điều kiện}\;\begin{cases}
    u_i-a_{ij}v_j\geq0,\;i=1,\ldots,m,\;j=1,\ldots,n
    \\
    \sum_{j=1}^n\geq 1,
    \\u_i\geq 0, i=\overline{1, m},\; v_j\geq 0, j=\overline{1, n.}
  \end{cases}
\end{equation}

Các cặp ràng buộc đối ngẫu là
$$x_{ij}\geq 0\leftrightarrow u_i-a_{ij}v_j\geq0,\;i=1,\ldots,m;\;j=1,\ldots,n$$
$$f\geq 0\leftrightarrow\sum_{j=1}^n\nu_j\geq 1$$
$$- \sum_{i=1}^ma_{ij}x_{ij}+f\leq 0\leftrightarrow v_j\geq 0,\;\;j=\overline{1,n}.$$
Để thuận tiện cho việc tính toán trong việc giải bài toán chúng ta có thể biểu diễn thông tin bài toán
\eqref{e3.3}\eqref{e3.4} và \eqref{e3.5}\eqref{e3.6} dưới dạng bảng sau
%\begin{figure}[htb]
%  % Requires
%  \begin{center}
%  \includegraphics[width=11cm]{SXDB}\\
%  \caption{Hình vẽ biểu diễn lời giải của bài toán}\label{H2.1}
%  \end{center}
%\end{figure}
\newpage
\subsection{Tính chất của bài toán sản xuất đồng bộ}
\begin{thm}
  Giá trị $f$ trong bài toán sản xuất đồng bộ luôn dương.
\end{thm}
\begin{proof}
  Theo giả thiết $a_{ij}>0,$ \; $i=1,\ldots, m, \; j=1,\ldots n,$ đồng thời mỗi sản phẩm $i$ ắt phải được sản xuất bởi ít nhất một máy $j$ nên vơi mỗi $i$, tồn tại $j$ để $x_{ij}>0,$ do vậy từ
  $$f=\min f_j=\min\{\sum_{i=1}^ma_{ij}x_{ij},\; j=1,2,\ldots, n\},$$ cho thấy $f>0.$
\end{proof}
\begin{thm}
  Bài toán sản xuất đồng bộ luôn có phương án tối ưu.
\end{thm}
\begin{proof}
  Để chứng minh định lý ta chứng minh tập phương án của bài toán khác rỗng và hàm mục tiêu bị  bị chăn trên tập phương án. Thật vậy,  lấy $X=(x_{ij})$ với $x_{ij}=\frac1n$. Chúng ta kiểm tra thấy $X$ là một phương án của bài toán.
  \par Mặt khác, $\sum_{j=1}^nx_{ij}\leq 1, \; i=\overline{1, m}$ và $x_{ij}\geq 0$ nên $0\leq x_{ij}\leq 1.$ Từ đó suy ra
  \begin{align*}
    f&=\min\left\{\sum_{i=1}^ma_{ij}x_{ij},\; j=1,2,\ldots, n\right\}
    \\&\leq \min\left\{\sum_{i=1}^ma_{ij},\; j=1,2,\ldots, n\right\}=L
  \end{align*}
  Do đó hàm mục tiêu bị chặn trên tập phương án khác rỗng. Vậy bài toán có phương án tối ưu.
\end{proof}
\begin{thm}
  Giả sử $A$ là ma trận hệ số của hệ điều kiện \eqref{e3.4}. Khi đó $\text{rank}(A)=m+n.$
\end{thm}
\begin{proof}

\end{proof}
\section{Bài toán quyết định tối ưu}
Trong thực tế, chúng ta luôn phải lựa chọn một phương án nào đó để đưa ra quyết định cho hành vi của mình. Lúc này, chúng ta thường xem xét cái được và cái mất dựa trên các yếu tố thuận lợi và khó khăn của từng hoàn cảnh thực tế. Xét cho cùng, lúc này xuất hiện một quan hệ tay đôi giữ người đưa ra quyết định và đối thủ. Nếu quyết định đúng thì chủ thể sẽ thành công (thắng cuộc), nếu quyết định sai thì sẽ thất bại và lợi ích sẽ thuộc về đối thủ cạch tranh. Kết quả của người đưa ra quyết định phu thuộc vào quyết định của đối thủ cạnh tranh. Cuộc đấu trí giữa chủ thể và đối thủ được xét đến như một trò chơi 2 đấu thủ. Chẳng hạn như trong các trò chơi cờ tướng, cờ vua, song đề tử tù, thiết lập kế hoạch đầu tư,\ldots. Sau đây chúng ta xét đến một số trò chơi
\begin{exm}[Trò chơi sấp ngửa]
  Có 2 đấu thủ P và Q cùng chơi, mỗi người tung một đồng xu 2 mặt sấp (S) và ngữa (N) cùng lúc bằng một hiệu lệnh nào đó. Nếu cả 2 đồng tiền đều xuất hiện mặt sấp thì (P) thắng (Q) nếu  2 đồng tiền đều xuất hiện mặt ngửa thì (Q) thắng (P) ((P) thua (Q)). Nếu có một mặt sấp  và một mặt ngửa thì hòa.  Nếu (P) thắng (Q) thì (P) nhận được 1 đồng.  (P) thua (Q) thì (P) nhận được  $-1$ đồng. Nếu (P) và (Q) hòa nhau tương  thì (P) nhận được  $0$ đồng. Khi đó trò chơi giữa (P) và (Q) được thể hiện bởi bản sau
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
&\multicolumn{2}{|c|}{P}\\
\cline{2-3}Q& \quad S\quad\;&\;\quad N\quad \quad\\
\hline
$S$&1; -1&0; 0\\
\hline
$N$&0; 0&-1; 1\\
\hline
\end{tabular}
\end{center}
Lúc này  ta có ma trận
$$A_P=\left[\begin{array}{cc}
    1 &0 \\
    0 & -1
  \end{array}\right];\;\;A_Q=\left[\begin{array}{cc}
    -1 &0 \\
    0 & 1
  \end{array}\right].
$$
Ma trận $A_P$ được gọi là ma trận thắng (hay ma trân thu hoạch) của (P); Ma trận $A_Q$ được gọi là ma trận thắng (hay ma trân thu hoạch) của (Q).  Rõ ràng tỷ lệ thắng thua của  trò chơi giữa (P) và (Q) được thể bởi ma trân $A$. Do vậy trò chơi này còn được gọi là trò chơi ma trận.
\end{exm}
\begin{exm}[Song đề tử tù]
Hai kẻ bị tình nghi là tội phạm bị cảnh sát bắt.
Cảnh sát không có đủ chứng cớ để kết án họ, và đã cách ly họ. Cảnh sát gặp từng người một và làm cùng tho thuận:
 nếu một người thú tội mà người kia im lặng, người im lặng sẽ bị phạt 10 năm tù và người thú tội sẽ được thả tự do.
 Nếu cả hai đều im lặng, cảnh sát chỉ phạt được mỗi tù nhân 6 tháng
 tù vì một tội nhỏ khác. Nếu cả hai đều thú tội, mỗi người sẽ bị phạt 2 năm.
Trò chi có thể được tóm tắt như sau:
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
& A im lặng& A thú tội\\
\hline
 B im lặng& Cả hai 6 tháng &B bị 10 năm, A được  tự do\\
\hline
 B thú tội&A bị 10 năm, B được tự do&Cả 2 bị 2 năm \\
\hline
\end{tabular}
\end{center}
Giả sử cả hai tù nhân đều ích kỹ và đều muốn làm giảm thiểu thời gian tù tội của mình. Mỗi tù nhân có 2 lựa chọn hợp tác với kẻ đồng lõa và
giữ im lặng; hoặc phản bôi và thú tội. Kết quả của mỗi sự lựa chọn đều phụ thuộc vào quyết định của người kia. Tuy nhiên không người nào biết sự lựa chọn của người kia. Ngay cả khi họ được gặp nhau họ vẫn có thể không tin tưởng nhau.
\par Nếu cả hai người này đều tin tưởng người kia là im lặng thì lựa chọn tối ưu của họ ta thú tội. Khi đó hắn sẽ được thả tự do trong khi người kia bị tù 10 năm. Ngược lại nếu hắn tin rằng người kia sẽ thú tội thì lựa chon tối ưu của hăn là thú tội vì khi đó cả hai sẽ bị tù 2 năm nếu không nó sẽ bị tù 10 năm nếu như im lặng. Tuy nhiên, nếu cả hai hợp tác được với nhau đề giữ im lặng thì mỗi người chỉ bị 6 tháng.
\par Vì thế ta thấy mỗi người đều nên thú tội bất kể người kia lựa chon như thế nào mỗi tù nhân đều được giảm tội nếu thú tội. Nhưng không may cho cả hai, nếu biết im lặng thì cả hai cùng bị tù 6 tháng.
\par Vậy nếu lý luận tốt cho cả 2 người thì tốt nhất cả hai đều im lặng bởi vì khi đó tổng thời gian tù cả 2 người phải chịu là 1 năm trong khi nếu có 1 người thú tội thì tổng thời gian tù của cả 2 người tối thiểu là 2 năm.
\par Quy tắc thưởng phạt được cho bởi bảng sau
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
& Q im lặng& Q thú tội\\
\hline
 P im lặng& -0,5; -0,5 &-10; 0\\
\hline
 P thú tội&0; -10& -2; -2\\
\hline
\end{tabular}
\end{center}
Ma trận thắng của $(P)$ và (Q) lần lượt là
$$A_P=\left[\begin{array}{cc}
    -0,5 &-10 \\
    0 & -2
  \end{array}\right];\;\;A_Q=\left[\begin{array}{cc}
    -0,5 &0 \\
    -10 & -2
  \end{array}\right].$$
\end{exm}
\begin{exm}[Trò chơi One-Two-Three] Trò chơi gữa $(P)$ và $(Q)$, mỗi người giơ tay ra hiệu "Giấy", "Búa", "Kéo"
 theo quy tắc "Giấy thắng Búa", "Búa thắng Kéo", "Kéo  thắng Giấy". Quy tắc thưởng phạt của trò chơi được cho bởi công thức.
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
& Giấy& Búa&Kéo\\
\hline
 Giấy& 0;0 &1; -1&-1; 1\\
\hline
 Búa&-1;1 & 0; 0&1; -1\\
\hline
Kéo&1; -1&-1; 1&0; 0
\\
\hline
\end{tabular}
\end{center}
Ma trận thắng của $(P)$ và (Q) lần lượt là
$$A_P=\left[\begin{array}{ccc}
    0 &1&-1 \\
    -1 & 0&1\\
    1&-1&0
  \end{array}\right];\;\;A_Q=\left[\begin{array}{ccc}
    0 &-1&1 \\
    1 & 0&-1\\
    -1&1&0
  \end{array}\right].$$
 \end{exm}
Như vậy trong các trò chơi này xuất hiện quan hệ tay đôi giữa người chơi và đối thủ. Lợi ích của người chơi phụ thuộc vào quyết định của đối thủ. Người chơi cần phải lựa chọn quyết định tối ưu cho mình trong mọi lựa chọn của đối thủ. Đó chính là bài toán quyết định tối ưu trong lý thuyết trò chơi và được áp dụng vào các mô hình thực tế
\par Mộ trò chơi 2 đấu thủ được quy định bởi các quy định bời các ma trân tháng của $A_P$ và $A_Q$ được gọi là \emph{bài toán  trò chơi ma trận.}
\subsection{Bài toán trò chơi ma trận tổng bằng không}
Trong mục này chúng ta xét trò chơi ma trận hai đối thủ có tổng bằng không tức là lợi nhuận của người chơi (P) dựa trên thiệt hại của người chơi (Q).
\begin{defn}
  Cho một ma trận $A=(a_{ij})_{m\times n}$ với $a_{ij}\in\mathbb{R}.$ Một trò chơi hai đối thủ sao cho ma trận $A$ là ma trận thắng của người chơi (P) và là ma trận trả tiền của đối thủ (Q) được gọi là trò chơi ma trận hai đối thủ. Trong đó, $m$ là số chiến lược đơn của người chơi $(P)$ và $n$ là số chiến lược đơn của đối thủ (Q).
\end{defn}
\begin{defn}
  +) Với mỗi $i=\overline{1, m}$, một véc tơ đơn vị
  $$X_i=(\underbrace{0,\ldots,0}_{i-1\text{ chữ số }\;0},1,0\ldots0)\in\mathbb{R}^m$$
  được gọi là chiến lược đơn \textbf{i} của người chơi $(P).$
  \par+) Với mỗi $j=\overline{1, n}$, một véc tơ đơn vị
  $$Y_i=(\underbrace{0,\ldots,0}_{j-1\text{ chữ số }\;0},1,0\ldots0)\in\mathbb{R}^n$$
  được gọi là chiến lược đơn \textbf{j} của người chơi $(Q).$
 \end{defn}
 \begin{rem}
   Người chơi $(P)$ có $m$ chiến lược đơn, người chơi $(Q)$ có $n$ chiến lược đơn.
 \end{rem}
\begin{defn}
  +) Mỗi  véc tơ  $X=(x_1, x_2, \ldots, x_m)\in\mathbb{R}^m$ với $x_i\geq 0, \; \sum_{i=1}^mx_i=1$
  được gọi là chiến lược hỗn hợp  của người chơi $(P).$ Trong đó $x_i$ là xác suất để người chơi $(P)$ chọn phương án \textbf{i}.
  \par+) Mỗi  véc tơ  $Y=(y_1, y_2, \ldots, y_n)\in\mathbb{R}^n$ với $y_j\geq 0, \; \sum_{i=1}^ny_j=1$
  được gọi là chiến lược hỗn hợp  của người chơi $(Q).$ Trong đó $y_j$ là xác suất để người chơi $(Q)$ chọn phương án \textbf{j}. \end{defn}
  \begin{defn}Xét trò chơi ma trận hai đấu thủ $(P)$ và $(Q)$  với ma trận thắng của $(P)$ là $A=(a_{ij})_{m\times n}.$ Giả sử  $X=(x_1, x_2, \ldots, x_m)\in\mathbb{R}^m$ và $Y=(y_1, y_2, \ldots, y_n)\in\mathbb{R}^n$ lần lượt là chiến lược hỗn hợp của $(P)$ và $(Q)$. Khi đó
  \begin{equation}
    \mathbb{E}(X, Y)= XAY^T=\sum_{i=1}^mx_i\left(\sum_{j=1}^na_{ij}y_j\right)
  \end{equation}
    được gọi là hàm thu hoạch (kỳ vọng thắng) của $(P)$.
  \end{defn}
  \begin{rem}+) Nếu $\mathbb{E}(X, Y)>0$ thì $(P)$ có thắng $(Q)$; nếu $\mathbb{E}(X, Y)<0$ thì $(P)$ có thua $(Q)$; nếu $\mathbb{E}(X, Y)=0$ thì $(P)$ và $(Q)$ hòa nhau.
  \par
    +) $\mathbb{E}(X_i, Y_j)=a_{ij}.$ Do đó $a_{ij}$ là giá trị lợi nhuận mà $(P)$ nhận được khi $(P)$ chọn chiến lược đơn \textbf{i} và đối thủ chọn chiến lược đơn \textbf{j}.
  \end{rem}
Chúng ta có thể xem quyết định đầu tư của một nhà đầu tư là trò chơi 2 đấu thủ giửa nhà đầu tư và biến động của thị trường ta có  ví dụ sau:
\begin{exm}\label{vd2.7.8}
  Một nhà đầu tư có thể lựa chọn đầu tư vào cổ phiếu $A, B, C$. Sau khi phân tích biến động của thị trường người ta dự báo là sẽ xãy ra 4 tình huống của thị trường là $(I); (II); (III); (IV).$ Hiệu quả đầu tư mang lại (đơn vị: triệu đồng) khi nhà đầu tư  chi ra 100 triệu vào từng cổ phiếu ứng với từng tình huống của thị trường được cho ở bảng sau.
  \begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
Phương án&\multicolumn{4}{|c|}{Hiệu quả}\\
\hline
A&16&8&7&0\\
\hline
B&-7&20&6&15\\
\hline
C&9&10&\textcolor[rgb]{1.00,0.00,0.50}{-12}&5\\
\hline
\cline{2-5}Tình huống&\; I\quad&\quad II \quad&\; III\quad &IV\\
\hline
\end{tabular}
\end{center}
\par\emph{+) Ý nghĩa kinh tế của số "-12" trong bảng số là}:  Nếu nhà đầu tư chỉ chọn phương án $C$ để đầu tư (tức là người chơi chọn chiến lược đơn $X_3=(0,0,1)$) và khi đó thị trường xuất hiện tình huống $(III)$ (đối thủ chọn chiến lược đơn $Y_3=(0,0,1,0)$ ) thì nhà đẫu tư sẽ bị lỗ $12$ triệu đồng khi đầu tư 100 triệu.
\par+) \emph{Giả sử nhà đầu tư đưa 100 triệu của mình đầu tư vào cổ phếu $A$ là 30 triêu, 50 triệu đầu tư cho cổ phiếu $B$ còn lại đầu tư cho cổ phiếu $C.$ Các tình huống của thị trường có khả năng xuất hiện như nhau.} Khi đó,
\begin{itemize}
  \item Chiện lược hổn hợp của nhà đầu tư là: $X=(0,3; 0,5; 0,2)$
  \item Chiến lược hỗn hợp của thị trường (đối thủ) là $Y=(0,25; 0,25; 0,25; 0,25)$.
  \item  Kỳ vọng thắng của nhà đầu tư là
  \begin{align*}
  \mathbb{E}(X, Y)&=XAY^T
  \\&=(0,3; 0,5; 0,2)\left(\begin{array}{cccc}
    16 &8&7&0 \\
    -7 & 20&6&15\\
    9&10&-12&5
  \end{array}\right)\left(\begin{array}{c}
   0,25 \\
   0,25\\
   0,25\\
   0,25
  \end{array}\right)
  \\&=7,175.
  \end{align*}
\end{itemize}
\end{exm}
\subsection{Điểm yên ngựa và chiến lược tối ưu}
%\subsubsection{a) \;Điểm yên ngựa}
Xét trò chơi ma trận hai đối thủ $(P)$ và $(Q)$ với ma trận thắng của $(P)$ là $A=(a_{ij})_{m\times n}$.
\par Nếu người chơi chọn chiến lược đơn \textbf{i} \big(tức là $X_i=(0,\ldots, 0, 1, 0\ldots0)$\big) khi đó người chơi sẽ quan tâm xem mình được lợi nhuận tối thiểu là bao nhiêu. Trong trường hợp đó nếu đối thủ chọn chiến lược hỗn hợp là $Y=(y_1, y_2, \ldots, y_n)$ thì kỳ vọng thắng của $(P)$ là
$$\mathbb{E}(X_i, Y)=\sum_{j=1}^na_{ij}x_j.$$
Giả sử $\min\limits_{j=\overline{1,n}}a_{ij}=a_{il}$. Khi đó
$$\mathbb{E}(X_i, Y)=\sum_{j=1}^na_{ij}y_j\geq\sum_{j=1}^na_{il}y_j=a_{il}\sum_{j=1}^ny_j =a_{il}.$$
Do đó, nếu  người chơi chọn chiến lược đơn \textbf{i} thì lợi nhuận tối thiểu người chơi sẽ nhận được là $\min\limits_{j=\overline{1,n}}a_{ij}.$ Rõ ràng, với cách tư duy đó người chơi $(P)$ sẽ lựa chọn chiến lược đơn \textbf{i} sao cho \emph{lợi nhuận tối thiểu là lớn nhất} tức là chọn chiến lược đơn \textbf{i} sao cho
$$\min\limits_{j=\overline{1,n}}a_{ij}=\max\limits_{k=\overline{1,m}}\min\limits_{j=\overline{1,n}}a_{kj}.$$
Do vậy, người ta nói người chơi $(P)$ chọn chiến lược theo nguyên lý $\max\min.$
\par Đối với đối thủ $(Q),$ khi có thông tin về ma trận thắng của $(P)$, nếu chọn chiến lược đơn \textbf{j} và người chơi chọn chiến lược hỗn hợp $X=(x_1, x_2, \ldots, x_m)$ thì tổn thất mà $(Q)$ phải chịu là
$$\mathbb{E}(X, Y_j)=\sum_{i=1}^ma_{ij}x_i.$$
Đặt $\max\limits_{i=\overline{1,m}}a_{ij}=a_{kj}$. Khi đó
$$\mathbb{E}(X, Y_j)=\sum_{i=1}^ma_{ij}x_i\leq\sum_{i=1}^ma_{il}x_i=a_{kj}\sum_{j=1}^nx_i =a_{kj}.$$
Do đó, nếu  đối thủ $(Q)$ chọn chiến lược đơn \textbf{j} thì tổn thất tối đa mà $(Q)$ phải trả là  $\max\limits_{i=\overline{1,m}}a_{ij}.$ Rõ ràng, với cách tư duy đó  $(Q)$ sẽ lựa chọn chiến lược đơn \textbf{j} sao cho \emph{tổn thất tối đa là bé nhất} tức là chọn chiến lược đơn \textbf{j} sao cho
$$\max\limits_{i=\overline{1,m}}a_{ij}=\min\limits_{l=\overline{1,n}}\max\limits_{i=\overline{1,m}}a_{il}.$$
Do vậy,  ta nói đối thủ $(Q)$ chọn chiến lược theo nguyên lý $\min\max.$
\begin{defn}
  Nếu trò chơi ma trận hai đối thủ $(P)$ và $(Q)$ với ma trận thắng $A=(a_{ij})_{m\times n}$ thỏa mãn
  \begin{equation}
   \max\limits_{i=\overline{1,m}}\min\limits_{j=\overline{1,n}}a_{ij}= \min\limits_{j=\overline{1,n}}\max\limits_{i=\overline{1,m}}a_{ij}=a_{lk}=\nu
     \end{equation}
  thì ta nói trò chơi ma trận có \emph{điểm yên ngựa} và giá của điểm yên ngựa là $a_{lk}=\nu.$
\end{defn}
\begin{rem}
  Nếu bài toán có điểm yên ngựa với giá của điểm yên ngựa là $\nu=a_{lk}$ thì
  \par+) Nếu $(P)$ chọn chiến lược đơn \textbf{l} thì $(P)$ sẽ thu được lợi nhuận tối thiểu là $\nu.$ Khi đó nếu $(Q)$ chọn một chiến lược đơn nào đó khác \textbf{k} thì sẽ có thể thiệt hại tối đa một lượng lớn hơn hoặc bằng $\nu$ và chỉ khi $(Q)$ chọn chiến lược đơn \textbf{k} thì $(Q)$ mới đảm bảo được rằng thiệt hại tối đa là $\nu$. Khi đó, \textbf{k} là chiến lược đơn tối ưu của $(Q).$
  \par+) Nếu $(Q)$ chọn chiến lược đơn \textbf{k} thì $(Q)$ sẽ thiệt hại tối đa là $\nu.$ Khi đó nếu $(P)$ chọn một chiến lược đơn nào đó khác \textbf{l} thì sẽ có thể thu được lợi nhuận tối thiểu một lượng bé thua hoặc bằng $\nu$ và chỉ khi $(P)$ chọn chiến lược đơn \textbf{l} thì $(P)$ mới đảm bảo được rằng lợi nhuận tối thiểu là $\nu$. Khi đó, \textbf{k} là chiến lược đơn tối ưu của $(P).$
\end{rem}
\begin{exm}
  Xét trò chơi ma trận hai đối thủ $(P)$ và (Q) với ma trận với ma trận thắng  của $(P)$ là
  $$A=\left(\begin{array}{cccc}
    4&2&1&13 \\
    4 & 15&5&2\\
    6&7&7&6
  \end{array}\right)$$
   ta có thể biểu diễn lên bảng sau
  \begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
&(I)&(II)&(III)&(IV)&$\min$&$\max$\\
\hline
A&4&2&1&13&1&13\\
\hline
B&4&15&5&2&2&15\\
\hline
C&\fbox{\textcolor[rgb]{1.00,0.00,1.00}{6}}&7&7&6&\textcolor[rgb]{0.00,0.00,1.00}{6}&7\\
\hline
$\max$&\textcolor[rgb]{0.00,0.00,1.00}{6}&15&12&13\\
\cline{1-5}
$\min$&4&2&1&2
\\
\cline{1-5}
\end{tabular}
\end{center}
Từ bảng trên chúng ta thấy
      $$\max\limits_{i=\overline{1,3}}\min\limits_{j=\overline{1,4}}a_{ij}= \min\limits_{j=\overline{1,4}}\max\limits_{i=\overline{1,3}}a_{ij}=a_{31}=6$$
Vậy bài toán có điểm yên ngựa với giá của điểm yên ngựa là $\nu=6.$ Chiến lược đơn tối ưu của $(P)$ là $X_3=(0,0,1)$ và của $(Q)$ là $Y_1=(1,0,0,0).$
Từ bảng trên chúng thấy\\
\textbf{\underline{Đối với người chơi (P) nếu}}
\begin{itemize}
  \item Chọn chiến lược đơn \textbf{1}  thì lợi nhuận tối thiểu là 1 và tối đa có thể  là 13;
  \item Chọn chiến lược đơn \textbf{2} thì lợi nhuận tối thiểu là 2 và tối đa có thể là 15;
  \item Chọn chiến lược đơn \textbf{3}  thì lợi nhuận tối thiểu là 6 và tối đa có thể  là 7.
\end{itemize}
\par\textcolor[rgb]{0.00,0.00,1.00}{Mặc dù chọn các phương án khác có thể người chơi có cơ hội có được lợi nhuận cao hơn  $7$. Tuy vậy người chơi vẫn chọn chiến lược đơn \textbf{3} để đảm bảo lợi nhuận tối thiểu là lớn nhất.}
\\ \textbf{\underline{Đối với đối thủ (Q) nếu}}
\begin{itemize}
  \item Chọn chiến lược đơn \textbf{1}  thì thiệt hại tối thiểu là 4 và tối đa có thể  là 6;
  \item Chọn chiến lược đơn \textbf{2} thì thiệt hại tối thiểu là 2 và tối đa có thể là 15;
  \item Chọn chiến lược đơn \textbf{3}  thì thiệt hại tối thiểu là 1 và tối đa có thể  là 12.
  \item Chọn chiến lược đơn \textbf{4}  thì thiệt hại tối thiểu là 2 và tối đa có thể  là 13.
\end{itemize}
\par\textcolor[rgb]{0.00,0.00,1.00}{Mặc dù chọn các phương án khác có thể người chơi có cơ hội có được thiệt hại thấp hơn  $4$. Tuy vậy $(Q)$ vẫn chọn chiến lược đơn \textbf{1} để đảm bảo thiệt hại tối đa là bé nhất.}
\end{exm}
\begin{defn}\label{dn2.7.11}
  Nghiệm của trò chơi ma trận hai đấu thủ là bộ ba $(\bar X, \bar Y, \nu)$, trong đó $\bar X$ là chiến lược hỗn hợp của người chơi $(P)$;  $\bar Y$ là chiến lược hỗn hợp của người chơi $(Q)$ và $\nu$ là giá của trò chơi thỏa mãn các điều kiện sau:
  \begin{itemize}
    \item [1)]\;\;$\mathbb{E}(\bar X, \bar Y)=\nu$
    \item [2)]\;\; $\mathbb{E}(\bar X, \textbf{j})\geq\nu$ với mọi chiến lược đơn \textbf{j} của $(Q);$
    \item [3)]\;\; $\mathbb{E}(\textbf{i}, \bar Y)\leq\nu$ với mọi chiến lược đơn \textbf{i} của $(P);$
  \end{itemize}
\end{defn}
\begin{rem} Nếu $(P)$ chọn chiến lược tối ưu  $\bar X$ thì lợi nhuận tối thiểu là $\nu.$ Nếu $(Q)$ chọn chiến lược tối ưu $\bar Y$ thì cho dù $(P)$ chọn phương án nào đi nữa thì thiệt hại tối đa không quá $\nu.$
\end{rem}
\begin{thm}[Định lý minimax]\label{thm2.7.12} Mọi trò chơi ma trận có phần tử dương bao giờ cũng tông tại nghiệm. Tức là chúng ta có đẳng thức sau
$$\max_X\min_Y\mathbb{E}(X,Y)=\min_Y\max_X\mathbb{E}(X,Y)=\nu.$$
  \end{thm}
  \begin{rem}
    +) Nếu $(\bar X, \bar Y, \nu)$ là nghiệm của trò chơ ma trận. Khi đó với mọi cặp chiến lược $(X, Y)$ ta luôn có
    $$\mathbb{E}(X,\bar Y)\leq\mathbb{E}(\bar X, \bar Y)=\nu\leq\mathbb{E}(\bar X, Y).$$
  \end{rem}
  +) Ta có
  $$\left(x_1, \ldots, x_m\right)\left(
                                  \begin{array}{cccc}
                                     p  & \ldots &p  \\
                                   \vdots & \ldots &\vdots  \\
p &  \ldots &p  \\
                                     \end{array}
                                \right)_{m\times n}\left(
                                         \begin{array}{c}
                                           y_1 \\
                                           \vdots \\
                                           y_n \\
                                         \end{array}
                                       \right)=p\left(\sum_{i=1}^mx_i\right)\left(\sum_{j=1}^ny_j\right)=p.
  $$
  Do đó với ma trận thắng $A=(a_{ij})_{m\times n}$. Đặt $A_p=(a_{ij}+p)_{m\times n}.$ Khi đó
  $$\mathbb{E}_p(X, Y)=XA_pY^T=XAY^T+p=\mathbb{E}(X,Y)+p.$$
   Do vậy, nghiệm của bài trò chơi ma trận với ma trận thắng  $A_p$ là $(\bar X, \bar Y, \nu_p)$ khi và chỉ khí nghiệm của bài trò chơi ma trận với ma trận thắng  $A$ là $(\bar X, \bar Y, \nu_p-p).$ Từ đó suy ra: \textcolor[rgb]{0.00,0.00,1.00}{Nếu ma trận thắng $A=(a_{ij})$ có phần tử âm thì có thể tay nó băng ma trận $A_p=(a_{ij}+p)$ với $p=1-\min\{a_{ij}:\;a_{ij}<0$\}. Do vậy chúng ta luôn đưa về được trò chơi ma trận với ma trận thắng chỉ chưa phầ tử dương.}
   \subsection{Mô tả bài toán trò chơi bởi bài toán quy hoạch}
   Xét bài toán trò chơi ma trận 2 đấu thủ $(P)$ và $(Q)$ với ma trận thắng của $(P)$ là $A=(a_{ij})$. Theo Định nghĩa \ref{dn2.7.11}. Người chơi $(P)$ tìm chiến lược tối ưu $X=(x_1, x_2, \ldots, x_m)$ sao cho
   \begin{equation}\label{e2.65}\begin{cases}
     x_1+x_2+\ldots+x_m=1, \;\; x_i\geq 0\;\;\forall i=\overline{1, m.}\\
     \mathbb{E}(X,\textbf{1})=a_{11}x_1+a_{21}x_2+\ldots+a_{m1}x_m\geq \nu\\
     \mathbb{E}(X,\textbf{2})=a_{12}x_1+a_{22}x_2+\ldots+a_{m2}x_m\geq \nu\\
     \ldots\ldots\ldots\ldots\ldots\ldots\ldots\\
     \mathbb{E}(X,\textbf{n})=a_{1n}x_1+a_{2n}x_2+\ldots+a_{mn}x_m\geq \nu
   \end{cases}
   \end{equation}
   Chúng ta luôn giả thiết $a_{ij}>0$ nên $\nu>0.$ Đặt $x'_i=\frac{x_i}{\nu},\;\;\forall\; i=\overline{0, n}.$ Khi đó hệ \eqref{e2.65} tương đương với
   \begin{equation}\label{e2.66}\begin{cases}
     x'_1+x'_2+\ldots+x'_m=\frac1\nu, \;\; x'_i\geq 0\;\;\forall i=\overline{1, m.}\\
     a_{11}x'_1+a_{21}x'_2+\ldots+a_{m1}x'_m\geq 1\\
     a_{12}x'_1+a_{22}x'_2+\ldots+a_{m2}x'_m\geq 1\\
     \ldots\ldots\ldots\ldots\ldots\ldots\ldots\\
     a_{1n}x'_1+a_{2n}x'_2+\ldots+a_{mn}x'_m\geq 1
   \end{cases}
   \end{equation}
   Mục tiêu của người chơi $(P)$ là phải tìm chiến lược $X$ sao cho là tối đa hóa giá của trò chơi, tức là $\nu$ càng lớn càng tốt. Do đó, bài toán của người chơi $(P)$ là: Tìm $X'=(x'_1, x'_2,\ldots, x'_m)$ sao cho
\begin{equation}\label{e2.67'}
  \min\{  x'_1+x'_2+\ldots+x'_m\}
\end{equation}
\begin{equation}\label{e2.68'}\text{với điều kiện}\;\;\begin{cases}
        a_{11}x'_1+a_{21}x'_2+\ldots+a_{m1}x'_m\geq 1\\
     a_{12}x'_1+a_{22}x'_2+\ldots+a_{m2}x'_m\geq 1\\
     \ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\\
     a_{1n}x'_1+a_{2n}x'_2+\ldots+a_{mn}x'_m\geq 1
   \\
    x'_i\geq 0\;\;\forall i=\overline{1, m.}
   \end{cases}
   \end{equation}
        \par Giải bài toán \eqref{e2.67'} \eqref{e2.68'} ta có được $X'=(x'_1, x'_2,\ldots,x'_m).$ Từ đó tính được giá của trò chơi
        $\nu=\frac1{x'_1+x'_2+\ldots+x'_m}$ và chiến lược tối ưu của người chơi $X=(x_1, x_2,\ldots, x_m)$ với $x_i=\nu x'_i\;\;\forall\, i=\overline{1,m}.$
   \par Đối thủ $(Q)$ tìm chiến lược tối ưu $Y=(y_1, y_2, \ldots, y_n)$ sao cho
   \begin{equation}\label{e2.67}\begin{cases}
     y_1+y_2+\ldots+y_n=1, \;\; y_j\geq 0\;\;\forall\, j=\overline{1, n.}\\
     \mathbb{E}(\textbf{1}, Y)=a_{11}y_1+a_{12}y_2+\ldots+a_{1n}y_n\leq \nu\\
     \mathbb{E}(\textbf{2}, Y)=a_{21}y_1+a_{22}y_2+\ldots+a_{2n}y_n\leq \nu\\
     \ldots\ldots\ldots\ldots\ldots\ldots\ldots\\
     \mathbb{E}(\textbf{m}, Y)=a_{m1}y_1+a_{m2}y_2+\ldots+a_{mn}y_n\leq \nu
   \end{cases}
   \end{equation}
    Đặt $y'_j=\frac{y_j}{\nu},\;\;\forall\, j=\overline{1, n}.$ Khi đó hệ \eqref{e2.67} tương đương với
   \begin{equation}\label{e2.68}\begin{cases}
     y'_1+y'_2+\ldots+y'_n=\frac1\nu, \;\; y'_j\geq 0\;\;\forall\, j=\overline{1, n.}\\
     a_{11}y'_1+a_{12}y'_2+\ldots+a_{1n}y'_n\leq 1\\
     a_{21}y'_1+a_{22}y'_2+\ldots+a_{2n}y'_n\leq 1\\
     \ldots\ldots\ldots\ldots\ldots\ldots\ldots\\
     a_{m1}y'_1+a_{m2}y'_2+\ldots+a_{mn}y'_n\leq 1
   \end{cases}
   \end{equation}
   Mục tiêu của đối thủ $(Q)$ là phải tìm chiến lược $Y$ sao cho là cực tiểu hóa giá của trò chơi, tức là $\nu$ càng bé càng tốt. Do đó, bài toán của đối thủ $(Q)$ là: Tìm $Y'=(y'_1, y'_2,\ldots, y'_n)$ sao cho
\begin{equation}\label{e2.70}
  \max\{  y'_1+y'_2+\ldots+y'_n\}
\end{equation}

\begin{equation}\label{e2.71}\text{với điều kiện}\;\;\begin{cases}
         a_{11}y'_1+a_{12}y'_2+\ldots+a_{1n}y'_n\leq 1\\
     a_{21}y'_1+a_{22}y'_2+\ldots+a_{2n}y'_n\leq 1\\
     \ldots\ldots\ldots\ldots\ldots\ldots\ldots\\
     a_{m1}y'_1+a_{m2}y'_2+\ldots+a_{mn}y'_n\leq 1 \\
    y'_j\geq 0\;\;\forall j=\overline{1, n.}
   \end{cases}
   \end{equation}
 \par Giải bài toán \eqref{e2.70} \eqref{e2.71} ta có được $Y'=(y'_1, y'_2,\ldots,y'_n).$ Từ đó tính được giá của trò chơi
        $\nu=\frac1{y'_1+y'_2+\ldots+y'_n}$ và chiến lược tối ưu của đối thủ $Y=(y_1, y_2,\ldots, y_n)$ với $y_j=\nu y'_j\;\;\forall\, j=\overline{1,n}.$
\begin{rem}
 1)\; Bài toán của người chơi \eqref{e2.67'} \eqref{e2.68'} và bài toán của đối thủ \eqref{e2.70} \eqref{e2.71} lập thành cặp bài toán đối ngẫu do vậy, khi cặp bài toán có phương án tối ưu ta có
 $$\max\left\{\sum_{j=1}^ny'_j\right\}=\max\left\{\sum_{i=1}^mx'_i\right\}=\frac1\nu.$$
 \par 2) Từ hệ điều kiện  \eqref{e2.71} ta thấy khi đưa bài toán \eqref{e2.70} \eqref{e2.71} về dạng chính tắc ma trận hệ số luôn chứa ma trận con đơn vị do vậy việc chọn  phương án cực biên xuất phát cho bài toán này được thực hiện dễ dàng. Đây là một thuận lơi. Do vậy, chúng ta thường giả bài toán của đối thủ $(Q).$ Dùng định lý lệch bù để tìm phương án tối ưu của bài toán của người chơi $(P).$
 \par 3) Khi giải bài toán \eqref{e2.70} \eqref{e2.71} bảng đầu tiên bao giờ chúng ta cũng có $\Delta_j=1$ ứng với $A_j$ ngoài cơ sở. Về nguyên tắc chúng ta có quyền chọn một $A_k$ vào cơ sở ứng với nó $\Delta_k>0$. Tuy nhiên, mục đích của chúng ta làm giảm hàm mục tiêu được một lượng càng lớn càng tốt. Do vậy ta chọn $A_k$ vào cơ sở mà ứng với nó $\Delta_k>0$ và
 $$\lambda_{0k}=\max\{\lambda_{0j}|\;\Delta_j>0\};\;\text{với}\;\; \lambda_{0j}=\min\{\frac{x^{(0)_i}}{a_{ij}}|\; \; a_{ij}>0\}.$$
 Vì khi đó ta có
 $$f(Y_1)=f(Y_0)-\lambda_{0k}\Delta_k.$$
\par 4) Khi $a_{ij}>0\;\forall\, i,j$ thì cặp bài toán \eqref{e2.67'} \eqref{e2.68'} và \eqref{e2.70} \eqref{e2.71} luôn có tập phương án khác rỗng. Thật vậy
$$a_{lk}=\max\{a_{ij}:\;\;\forall i=\overline{1, m}; \; j=\overline{1, n}\};\;\;a_{pq}=\min\{a_{ij}:\;\;\forall i=\overline{1, m}; \; j=\overline{1, n}\}.$$
Khi đó
$$X'=(\underbrace{0,0,\ldots,0}_{\text{p-1 số 0}},\frac1{a_{pq}},0,\ldots,0)\in\mathbb{R}^m$$
là một phương án của bài toán \eqref{e2.67'} \eqref{e2.68'} và
$$X'=(\underbrace{0,0,\ldots,0}_{\text{k-1 số 0}},\frac1{a_{lk}},0,\ldots,0)\in\mathbb{R}^n$$
 là một phương án của bài toán  \eqref{e2.70} \eqref{e2.71}.
 Do vậy, áp dụng định lý định lý đối ngẫu suy ra  \eqref{e2.67'} \eqref{e2.68'} và \eqref{e2.70} \eqref{e2.71} có phương án tối ưu. Ngoài ra, $(0,0,\ldots,0)\in\mathbb{R}^m$ không phải là  phương án của bài toán \eqref{e2.67'} \eqref{e2.68'} nên   $\min\{  x'_1+x'_2+\ldots+x'_m\}>0$ suy ra tồn tại giá của trò chơi $\nu$ sao cho $$\nu=\frac1{  \min\{  x'_1+x'_2+\ldots+x'_m\}}>0.$$
 Nhận xét này một lần nữa chỉ ra tính đúng của Định lý \ref{thm2.7.12}.
\end{rem}
\subsection{Thuật toán tìm chiến lược tối ưu của trò chơi}
Để tìm chiến lược tối ưu cho người chơi và đối thủ chúng ta thực hiện các bước sau:
\par \textbf{\underline{Bước 1}} \;Đưa bài toán trò chơi về bài toán có ma trận thắng của $(P)$ có các phần tử dương. Nếu ma trận thắng $A=(a_{ij})_{m\times n}$ tồn tại $a_{ij}<0.$ Đặt $\alpha=-\min\{a_{ij}|\; a_{ij}<0\}.$ Khí đó xét bài toán trò chơi với ma trận thắng $A_\alpha=(a_{ij}+\alpha)_{m\times n}.$
\par \textbf{\underline{Bước 2}}\; Viết bài toán quy hoạch tuyến tính cho chiến lược của người chơi $(P)$ và đối thủ $(Q)$ với ma trận thắng $A_\alpha.$
\par \textbf{\underline{Bước 3}} Giải bài toán của đối thủ $(Q)$ hoặc người chơi $(P)$ ta có được phương án tối ưu  $X'=(x'_1,x'_2,\ldots, x'_m)\in\mathbb{R}^m$ và $Y'=(y'_1, y'_2,\ldots, y'_n)\in\mathbb{R}^n$ của cặp bài toán \eqref{e2.67'} \eqref{e2.68'} và \eqref{e2.70} \eqref{e2.71}.
\par \textbf{\underline{Bước 4}} Tính giá của trò chơi $\nu=\frac1{y'_1+ y'_2+\ldots+ y'_n}$,  chiến lược tối ưu $X=(x_1,x_2,\ldots, x_m)\in\mathbb{R}^m$ với $x_i=\nu x'_i\;\forall i=\overline{1,m}$ của người chơi $(P)$ và chiến lược tối ưu $Y=(y_1,y_2,\ldots, x_n)\in\mathbb{R}^n$ với $y_j=\nu y'_j\;\forall j=\overline{1,n}$ của đối thủ $(Q).$
\begin{exm} Trong Ví dụ \ref{vd2.7.8} chúng ta xem nhà đầu tư là người chơi $(P)$ và thị trường là đấu thủ $(Q)$ với ma trận thắng của $(P)$ là
$$A=\left(\begin{array}{cccc}
    16 &8&7&0 \\
    -7 & 20&6&15\\
    9&10&-12&5
  \end{array}\right)$$
  Ta xét bài toán trò chơi ma trận với ma trận thắng là
  $$A=\left(\begin{array}{cccc}
    29 &21&20&13 \\
    6 & 33&19&28\\
    22&23&1&18
  \end{array}\right)$$
  Bài toán quy hoạch của người chơi $(P)$ là
  \begin{equation}
    \min\{x'_1+x'_2+x'_3\}
  \end{equation}
  \begin{equation}
    \begin{cases}
      29x'_1+6x'_2+22x'_3\geq 1
      \\
      21x'_1+23x'_2+33x'_3\geq 1
      \\      20x'_1+19x'_2+x'_3\geq 1
      \\
      13x'_1+28x'_2+18x'_3\geq 1
      \\x'_1, x'_2,x'_3\geq 0
    \end{cases}
  \end{equation}
  Bài toán quy hoạch của đối thủ $(Q)$ là
  \begin{equation}\label{e2.75}
    \max\{y'_1+y'_2+y'_3+y'_4\}
  \end{equation}
  \begin{equation}\label{e2.76}
    \begin{cases}
      29y'_1+21y'_2+20y'_3+13y'_4\leq 1
      \\
      6y'_1+33y'_2+19y'_3+28y'_4\leq 1
      \\      22y'_1+23y'_2+y'_3+18y'_4\leq 1
            \\y'_1, y'_2,y'_3, y'_4\geq 0
    \end{cases}
  \end{equation}
  Bây giờ chúng ta giải bài toán \eqref{e2.75}\eqref{e2.76}.
  \par Dạng chính tắc của bài toán \eqref{e2.75}\eqref{e2.76} là
\begin{equation}\label{e2.77}
    \min\{-y'_1-y'_2-y'_3-y'_4\}
  \end{equation}
  \begin{equation}\label{e2.78}
    \begin{cases}
      29y'_1+21y'_2+20y'_3+13y'_4+y'_5&= 1
      \\
      6y'_1+33y'_2+19y'_3+28y'_4\hspace{1.2cm}+y'_6&=1
      \\      22y'_1+23y'_2+y'_3+18y'_4\hspace{2.4cm}+y'_7&= 1
            \\y'_j\geq 0,\;\;\forall j=\overline{1,7}.
    \end{cases}
  \end{equation}
  Ta có ma trận hệ số  của \eqref{e2.78} là
  $$A=\begin{array}{ccccccc}
    (A_1)&(A_2)&(A_3)&(A_4)&(A_5)&(A_6)&(A_7)\\
    \left[\quad\begin{array}{c}29\\6\\22\end{array}\right. &\begin{array}{c}21\\33\\23\end{array} & \begin{array}{c}20\\19\\1\end{array} &\begin{array}{c}13\\28\\18\end{array}&\begin{array}{c}1\\0\\0\end{array} &\begin{array}{c}0\\1\\0\end{array} &\left.
    \begin{array}{c}0\\0\\1\end{array}\quad\right]\end{array}$$
Chọn hệ véc tơ cơ sở $A_5A_6A_7$ liên kết với phương án cực biên
$$X_0=(0,0,0,0,1,1,1),$$
ta có bảng đơn hình sau:
 \begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
Bảng& Cơ sở&Hệ số&Toạn độ&-1&-1&-&-1&0&0&0
\\
\cline{5-11}&&&&$A_1$&$A_2$& $A_3$ &$A_4$&$A_5$&$A_6$&$A_7$
\\
\hline&$A_5$&3&192&1&$\frac12$& $\frac12$ &$\frac12$&0&0&0
\\
I&$ A_6$&$2$&28&$0$&$0$&$\frac23$ &0&$\frac13$&1&0
\\
&$ A_7$\qquad&M&48&0&$\fbox{1}$&0&1 &0&0&1
\\
\cline{2-11}
&&$\alpha_i$&632&0&$\frac12$&$\frac{17}{6}$&$\frac12$&$-\frac73$&0&0
\\
\cline{3-11}
&&$\beta_i$&48&0&$1\Uparrow$&0&1&0&0&0
\\
\hline
&$A_1$&3&168&1&0&$\frac12$ &0&0&0&$\times$
\\
II&$\Leftarrow  A_6$\quad&$2$&28&0&$0$&$\frac{2}{3}$&0 &$\frac13$&1&$\times$
\\
&$A_2$&1&48&0&1&0 &1&0&0&$\times$
\\
\cline{2-11}
&&&608&0&0&$\frac{17}6\Uparrow$&0&$-\frac73$&0&$\times$
\\
\hline
&$ A_1$&3&147&1&0&0 &0&$-\frac14$&$-\frac34$&$\textcolor[rgb]{1.00,0.00,0.00}{\times}$
\\
III&$ A_3$&0&$42$&0&0&1 &0&$\frac12$&$\frac32$&$\textcolor[rgb]{1.00,0.00,0.00}{\times}$\\
&$A_2$&1&48&0&1&0 &1&0&0&$\textcolor[rgb]{1.00,0.00,0.00}{\times}$\\
\cline{2-11}
&&&489&0&0&0&0&$-\frac{15}{4}$&$-\frac{17}4$&$\textcolor[rgb]{1.00,0.00,0.00}{\times}$
\\
\hline%
%&$A_1$&3&165&1&0&$\frac12$ &0&0&0&$\textcolor[rgb]{1.00,0.00,0.00}{\times}$
%\\
%IV&$A_5$&2&84&0&0&2 &0&1&3&$\textcolor[rgb]{1.00,0.00,0.00}{\times}$\\
%&$A_2$&1&48&0&1&0 &1&0&0&$\textcolor[rgb]{1.00,0.00,0.00}{\times}$\\
%\cline{2-11}
%&&&185&0&0&$-\frac16$&0&0&$-\frac{9}2$&$\textcolor[rgb]{1.00,0.00,0.00}{\times}$
%\\
%\hline
%B&110&2&7&2&1\\
%\hline
%C&30&6&5&2&6\\
%\hline
%\multicolumn{2}{|c|}{Nhu cầu các vùng}&30&40&60&50\\
%\hline
\end{tabular}
\end{center}
\end{exm}

\chapter{Mô hình cân đối liên ngành}
\chapter{Mô hình phục vụ công cộng}
\chapter{Mô hình lưu trữ}



\begin{thebibliography}{02}
\bibitem{TXS1} Trần Xuân Sinh, \emph{Toán kinh tế}, Nhà xuất bản Đại học quốc gia Hà Nội, 2008.

\bibitem{TXS2} Trần Xuân Sinh,\emph{Quy hoạch tuyến tính}, Nhà xuất bản Đại học sư phạm, 2003.

\bibitem{New} Thêm tài liệu của ĐH Kinh tế quốc dân và Tài liệu nước ngoài.
\end{thebibliography}

\end{document}
