\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{defn}[thm]{Định nghĩa}
\newtheorem{exm}[thm]{Ví dụ}
\newtheorem{prob}{}
\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:
\begin{itemize}
\item{} 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.
\item{} Bài toán quy hoạch tuyến tính.
\item{} Phương pháp đơn hình giải bài toán quy hoạch tuyến tính.
\item{} Mô hình bài toán vận tải.
\end{itemize}

\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ột số mô hình toán kinh tế điển hình}
\textbf{3.1.1.1 Mô hình lập kế hoạch sản xuất}
\vskip 0.2cm
\emph{Phát biểu bài toán:} Một cơ sở có thể sản xuất hai loại sản phẩm A và B, từ các nguyên liệu I, II, III. Chi phí từng loại nguyên liệu và tiền lãi của một đơn vị sản phẩm, cũng như dự trữ nguyên liệu cho trong sau đây.
\vskip 0.1cm
\begin{tabular}{ | p{6cm}  | p{1cm} | p{1cm}  |p{1cm} | p{1cm}  |}
    \hline
Sản phẩm $\setminus$ Nguyên liệu & I & II & III & Lãi\\ \hline
A & 2 & 0 & 1 & 3  \\ \hline
B & 1 & 1 & 0 & 5  \\ \hline
Dự trữ & 8 & 4 & 3 &   \\ \hline
    \end{tabular}
  \vskip 0.1cm

Hãy lập bài toán thể hiện kế hoạch sản xuất sao cho tổng số lãi lớn nhất, trên cơ sở nguồn dự trữ nguyên liệu đã có.
\vskip 0.2cm
\noindent\emph{Thiết lập mô hình toán:} Gọi $x, y$ lần lượt là số sản phẩm A và B được sản xuất ($x,y\geq0$).

Khi đó ta cần tìm $x,y\geq0$ sao cho tổng số lãi là lớn nhất, nghĩa là
$$f(X)=3x+5y\Rightarrow\max$$
với điều kiện nguyên liệu: $2x+y\leq8$, $1.y\leq4$, $1.x\leq3$. Tức là ta cần giải bài toán quy hoạch tuyến tính sau
$$\max\{f(X)=3x+5y\}$$
$$\text{với điều kiện} \left\{ \begin{array}{ll}
\:2x+y\leq8\\
 \:y\leq4\\
x\leq3\\
x,y\geq0.
\end{array} \right.$$
\vskip 0.2cm
\noindent\textbf{3.1.1.2 Mô hình bài toán khẩu phần thức ăn}
\vskip 0.2cm
\emph{Phát biểu bài toán:} Một khẩu phần thức ăn có khối lượng $P$, có thể 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$ và có trong một đơn vị thức ăn loại $j$ là $a_{ij}$. Ta nên cấu tạo một khẩu phần thức ăn như thế nào để ăn đủ no, đủ chất dinh dưỡng mà có giá mua rẻ nhất?
\vskip 0.2cm
\noindent\emph{Thiết lập mô hình toán:} Gọi $x_j$ là số đơn vị thức ăn loại $j$ được cấu tạo trong khẩu phần. Khi đó ta có bài toán quy hoạch tuyến tính
$$\min\{f(X)=\sum_{j=1}^nc_jx_j\}$$
$$\text{với điều kiện} \left\{ \begin{array}{ll}
\:\sum\limits_{j=1}^nx_j=P\\
 \:\sum\limits_{j=1}^na_{ij}x_j\geq b_i, i=1,2, ...,m,\\
x_j\geq0, j=1,2,...,n.
\end{array} \right.$$
\vskip 0.2cm
\noindent\textbf{3.1.1.3 Mô hình bài toán vận tải}
\vskip 0.2cm
\emph{Phát biểu bài toán:} Người ta cần tổ chức vận tải một loại hàng từ $n$ nơi phát đến $m$ nơi thu. Nơi phát thứ $j$ có số lượng hàng là $a_j$, nơi nhận thứ $i$ cần số lượng hàng là $b_i$. Cước phí vận tải một đơn vị hàng từ nơi phát $j$ tới nơi nhận $i$ là $c_{ij}$. Ta nên tổ chức vận tải như thế nào để bảo đảm phát hết và nhận đủ số hàng, mà có tổng cước phí bé nhất.

Đây là bài toán rất hay gặp trong thực tế. Chú ý rằng ``hàng'' ở đây có thể là hàng hoá thông thường, có thể là lượng thông tin cần chuyển tải, có thể là sự phân phối lao động nào đó, ...
\vskip 0.2cm
\noindent\emph{Thiết lập mô hình toán:} Gọi $x_{ij}$ là số lượng hàng vận tải từ $j$ tới $i$ ($x_{ij}\geq0$). Khi đó tổng cước phí sẽ là
$$f(X)=\sum_{j=1}^n\sum_{i=1}^mc_{ij}x_{ij}\Rightarrow\max$$
với điều kiện:

+ nhận đủ hàng: $\sum\limits_{j=1}^nx_{ij}=b_i$, $i=1,2,...,m$,

+ phát hết hàng: $\sum\limits_{i=1}^mx_{ij}=a_j$, $j=1,2,...,n.$
\vskip 0.2cm
Từ đó ta có bài toán quy hoạch tuyến tính
$$\min\{f(X)=\sum_{j=1}^n\sum_{i=1}^mc_{ij}x_{ij}\}$$
$$\text{với điều kiện} \left\{ \begin{array}{ll}
\:\sum\limits_{j=1}^nx_{ij}=b_i, i=1,2,...,m,\\
 \:\sum\limits_{i=1}^mx_{ij}=a_j, j=1,2,...,n,\\
x_{ij}\geq0, i=1,2,...,m, j=1,2,...,n.
\end{array} \right.$$
\vskip 0.2cm
\noindent\textbf{3.1.1.4 Mô hình bài toán lập kế hoạch kinh doanh}
\vskip 0.2cm
\emph{Phát biểu bài toán:} Một doanh nghiệp dự định kinh doanh một loại mặt hàng theo kế hoạch, trong một đơn vị thời gian gồm $n$ kỳ xác định (chẳng hạn 1 năm gồm 12 tháng hoặc 4 quý). Ở kỳ thứ $j$ giá mua vào của một đơn vị hàng là $p_j$ và giá bán ra là $q_j$. Sức chứa của kho dự trữ cho kỳ thứ $j$ tối đa là $Q_j$ và kinh phí lưu kho của một đơn vị hàng là $r_j$. Hỏi nên tổ chức kinh doanh như thế nào (nên mua vào và bán ra bao nhiêu ở mỗi thời kỳ) để có tổng số lãi lớn nhất. Biết rằng dự trữ ban đầu trong kho đã có số lượng hàng là $s_0$.
\vskip 0.2cm
\noindent\emph{Thiết lập mô hình toán:} Gọi $x_j$ ($x_j \geq 0$) là lượng hàng mua vào và $y_j$ ($y_j \geq 0$) là lượng hàng bán ra ở kỳ kế hoạch thứ $j$ ($j = 1, 2, ..., n$). Nếu không tính chi phí bảo quản thì tổng số lãi của doanh nghiệp trong một đơn vị kế hoạch là
$$\sum_{j=1}^nq_jy_j-\sum_{j=1}^np_jx_j.$$

Với tổng số hàng lưu kho ở kỳ kế hoạch thứ $j$ là
$$s_0+\sum_{i=1}^j(x_i-y_i).$$

Tuy nhiên, do hàng lưu kho ở mỗi thời kỳ cần tới kinh phí bảo quản nên theo yêu cầu của bài ra ta cần thêm tổng kinh phí bảo quản lưu kho là
$$\sum_{j=1}^nr_j\big(s_0+\sum_{i=1}^j(x_i-y_i)\big).$$

Vậy tổng số lãi thực có sẽ là
$$\sum_{j=1}^nq_jy_j-\sum_{j=1}^np_jx_j-\sum_{j=1}^nr_j\big(s_0+\sum_{i=1}^j(x_i-y_i)\big)\Rightarrow\max.$$

Với điều kiện phụ thuộc sức chứa của kho ở mỗi kỳ kế hoạch là
$$0\leq s_0+\sum_{i=1}^j(x_i-y_i)\leq Q_j, j=1,2, ...,n.$$

Từ đó ta có mô hình toán học là bài toán quy hoạch tuyến tính:
$$\max\left\{\sum_{j=1}^nq_jy_j-\sum_{j=1}^np_jx_j-\sum_{j=1}^nr_j\big(s_0+\sum_{i=1}^j(x_i-y_i)\big)\right\}$$
$$\text{với điều kiện} \left\{ \begin{array}{ll}
\:0\leq s_0+\sum\limits_{i=1}^j(x_i-y_i)\leq Q_j, j=1,2, ...,n,\\
 x_{j}, y_j\geq0, j=1,2,...,n.
\end{array} \right.$$
\vskip 0.2cm
\noindent\textbf{3.1.1.5 Mô hình bài toán sản xuất đồng bộ}
\vskip 0.2cm
\emph{Phát biểu bài toán:} Có $m$ máy công cụ khác nhau, 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ấu thành sản phẩm được chia theo tỷ lệ một - một (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à $a_{ij}$ (đơn vị chi tiết/đơn vị thời gian), $i = 1, ..., m$, $j = 1, ..., n$. Hãy bố trí thời gian cho các máy sản xuất các chi tiết sao cho số sản phẩm đồng bộ sản xuất được là nhiều nhất.
\vskip 0.2cm
\noindent\emph{Thiết lập mô hình toán:} Ta cần tìm thời gian phân bố cho máy thứ $i$ sản xuất sản phẩm thứ $j$ trong một chu kỳ (một đơn vị thời gian) làm việc.

Gọi $x_{ij}$ là phần thời gian trong một đơn vị thời gian làm việc của máy $i$ sản xuất sản phẩm thứ $j$. Khi đó $x_{ij}$ phải thoả mãn các điều kiện:

+ Giá trị của biến: $x_{ij}\geq0$.

+ Tổng thời gian máy $i$ thực hiện sản xuất $n$ sản phẩm trong 1 đơn vị thời gian làm việc
$$\sum_{j=1}^nx_{ij}\leq1, i=1,2,...,m.$$

+ Số chi tiết thứ $j$ sản xuất được bởi $m$ máy là
$$f_j=\sum_{i=1}^ma_{ij}x_{ij}, j=1,2,...,n.$$

+ Số sản phẩm đủ bộ sẽ có là
$$f=\min\{f_j: j=1,2,...,n\}=\min\{\sum_{i=1}^ma_{ij}x_{ij}, j=1,2,...,n\}.$$

Bài toán đặt ra là: Tìm $X=(x_{ij})$, $i=1,2,...,m$, $j=1,2, ..., n$ sao cho
$$\max f=\max\{\min\limits_j\{\sum_{i=1}^ma_{ij}x_{ij}, j=1,2,...,n\}\}$$
$$\text{với điều kiện} \left\{ \begin{array}{ll}
\:\sum\limits_{j=1}^nx_{ij}\leq1, i=1,2,...,m,\\
 x_{ij}\geq0, i=1,2,...,m, j=1,2,...,n.
\end{array} \right.$$

Chú ý rằng từ điều kiện
$$f=\min\{\sum_{i=1}^ma_{ij}x_{ij}, j=1,2,...,n\},$$
ta có
$$f\leq \sum_{i=1}^ma_{ij}x_{ij}, j=1,2,...,n.$$
Hay là
$$-\sum_{i=1}^ma_{ij}x_{ij}+f\leq 0, j=1,2,...,n.$$

Do vậy, bài toán nêu trên có thể viết lại tương đương với bài toán quy hoạch tuyến tính: Tìm $X=(x_{ij})$, $i=1,2,...,m$, $j=1,2, ..., n$ và $f$ sao cho
$$\max f$$
$$\text{với điều kiện} \left\{ \begin{array}{ll}
\:\sum\limits_{j=1}^nx_{ij}\leq1, i=1,2,...,m,\\
-\sum\limits_{i=1}^ma_{ij}x_{ij}+f\leq 0, j=1,2,...,n,\\
f\geq0,  x_{ij}\geq0, i=1,2,...,m, j=1,2,...,n.
\end{array} \right.$$
\vskip 0.2cm
\noindent\textbf{3.1.1.6 Mô hình bài toán cân đối liên ngành}
\vskip 0.2cm
\emph{Phát biểu bài toán:} Khi nghiên cứu quá trình tái sản xuất xã hội, phương pháp cân đối liên ngành (CĐLN) xem toàn bộ nền kinh tế quốc dân (hoặc một địa phương cụ thể nào đó) như một thể thống nhất, bao gồm $n$ ngành sản xuất sản phẩm khác nhau. Đồng thời cũng chính $n$ ngành sản xuất này lại là ngành tiêu thụ. Các ngành sản xuất được thực hiện tính theo $1$ đơn vị thời gian xác định (chẳng hạn $1$ năm, hoặc $1$ quý, hoặc $5$ năm ...), ta gọi là \emph{thời gian kế hoạch}.

Giả sử trong thời gian kế hoạch, ngành thứ $i$ có tổng sản lượng tương ứng là $X_i$ $(i = 1, 2, ..., n)$ và được sử dụng:

+ một phần giữ lại cho bản thân dưới dạng bán thành phẩm, tiêu dùng nội bộ cho sản xuất của ngành mình, ký hiệu là $x_{ii}$ ($x_{ii}\geq0$),

+ một phần khá lớn đầu tư (cung cấp) cho ngành $j \neq i$ $(j = 1, 2, ..., n)$ dưới dạng thiết bị, nguyên - nhiên - vật liệu, ký hiệu là $x_{ij}$ ($x_{ij}\geq0$),

+ phần còn lại là sản phẩm cuối cùng phục vụ tích luỹ, dự trữ, hao hụt, viện trợ, tiêu dùng, ..., ký hiệu là $Y_i$ ($Y_i \geq 0$).

Khi đó ta có \emph{phương trình CĐLN}
$$X_i=\sum_{j=1}^nx_{ij}+Y_i, i=1,2,..., n,$$
hay là
$$Y_i=X_i-\sum_{j=1}^nx_{ij}, i=1,2,..., n,$$

Phương trình cân đối liên ngành thường được thể hiện trên bảng CĐLN. Việc xây dựng bảng cân đối liên ngành nhằm lập kế hoạch sản xuất cần được thể hiện đầy đủ hơn trên cơ sở đòi hỏi của kế hoạch được đặt ra (cân đối dạng hiện vật hay cân đối dạng giá trị, cân đối liên ngành đóng hay mở, ...). Phương pháp giải quyết bài toán này gọi là phương pháp ma trận lập kế hoạch CĐLN.

Nếu coi $X_0$ là toàn bộ nguồn lao động xã hội có thể huy động vào sản xuất, $a_{0j}$ là số lao động cần thiết để sản xuất ra một đơn vị tổng sản lượng ngành $j$, lấy mục tiêu là làm cực tiểu chi phí lao động xã hội trong toàn bộ nền kinh tế, thì ta được mô hình toán học là bài toán quy hoạch tuyến tính
$$\min\{f=\sum_{j=1}^n\}a_{0j}X_j$$
$$\text{với điều kiện} \left\{ \begin{array}{ll}
\:Y_i=X_i-\sum\limits_{j=1}^nx_{ij}, i=1,2,..., n,\\
 X_i, Y_i, x_{ij}\geq0, i=1,2,...,n, j=1,2,...,n.
\end{array} \right.$$
\vskip 0.2cm
\noindent\textbf{3.1.1.7 Mô hình bài toán đầu tư thị trường chứng khoán}
\vskip 0.2cm
\emph{Phát biểu bài toán:} Một công ty dự định dùng khoản quỹ đầu tư T triệu đồng để mua một số cổ phiếu ở 4 thị trường chứng khoán A, B, C, D. Nhằm đa dạng hoá danh mục đầu tư để phòng ngừa rủi ro, công ty đưa ra các giới hạn trên của số tiền mua từng loại chứng khoán, tương ứng là $T_A, T_B, T_C, T_D$ (đơn vị: triệu đồng). Lãi suất (trung bình năm) của các chứng khoán trong thời điểm hiện tại tương ứng là $c_A, c_B, c_C, c_D$. Ngoài ra, để ngăn ngừa rủi ro trong đầu tư, công ty còn quy định khoản đầu tư vào loại cổ phiếu A và C phải chiếm tỷ lệ ít nhất là $55\%$, loại cổ phiếu B phải chiếm ít nhất $15\%$ trong tổng số tiền đầu tư.

Hãy xác định số tiền công ty sẽ mua từng loại cổ phiếu (một danh mục đầu tư) sao cho không vượt quá khoản dự kiến ban đầu, đảm bảo đòi hỏi về đa dạng hoá, đồng thời đạt mức lãi (trung bình) cao nhất.
\vskip 0.2cm
\noindent\emph{Thiết lập mô hình toán:} Gọi $x_A, x_B, x_C, x_D$, ($x_A, x_B, x_C, x_D \geq 0$), tương ứng là các khoản tiền từ quỹ đầu tư dùng để mua các loại chứng khoán A, B, C, D. Từ các đòi hỏi về đa dạng hoá và về quỹ đầu tư ta có các bất phương trình:
\begin{align*}
  &x_A\leq T_A, x_B\leq T_B, x_C\leq T_C, x_D\leq T_D,\\
&x_A+x_C\geq0,55(x_A+ x_B+ x_C+ x_D),\\
&x_B\geq 0,15(x_A+ x_B+ x_C+ x_D),\\
&x_A+ x_B+ x_C+ x_D\leq T.
\end{align*}
Mức lãi tương ứng với $(x_A, x_B, x_C, x_D)$ là
$$c_Ax_A+ c_Bx_B+ c_Cx_C+ c_Dx_D\rightarrow\max.$$
\par Như vậy, ta có bài toán quy hoạch tuyến tính:

Xác định danh mục đầu tư $(x_A, x_B, x_C, x_D)$ sao cho
$$\max\{c_Ax_A+ c_Bx_B+ c_Cx_C+ c_Dx_D\}$$
$$\text{với điều kiện} \left\{ \begin{array}{ll}
x_A\leq T_A, x_B\leq T_B, x_C\leq T_C, x_D\leq T_D,\\
x_A+x_C\geq0,55(x_A+ x_B+ x_C+ x_D),\\
x_B\geq 0,15(x_A+ x_B+ x_C+ x_D),\\
x_A+ x_B+ x_C+ x_D\leq T,\\
x_A, x_B, x_C, x_D\geq0.
\end{array} \right.$$
\subsection{Bài toán quy hoạch tuyến tính}
\textbf{3.1.2.1 Bài toán quy hoạch tuyến tính dạng tổng quát}
\vskip 0.2cm
Bài toán có dạng
\begin{align}
\min(\text{hoặc}\;\max)\{f(X)=\sum_{j=1}^nc_jx_j\}\label{3.1}
\end{align}
\begin{align*}
\text{với điều kiện:} \left\{ \begin{array}{ll}
\sum\limits_{j=1}^na_{ij}x_j=b_i, i=1, 2, ..., k,\\
\sum\limits_{j=1}^na_{ij}x_j\geq b_i, i=k+1, k+2, ..., m,\\
x_j\geq0, j=1, 2, ..., r\;(r\leq n).
\end{array} \right.
\end{align*}
gọi là \emph{bài toán quy hoạch tuyến tính tổng quát} (hay còn gọi tắt là \emph{bài toán quy hoạch tuyến tính}).

Hàm $f(X)$ gọi là \emph{hàm mục tiêu}.

Các điều kiện đặt ra gọi là \emph{điều kiện buộc} của bài toán.

Điểm $X\in\mathbb{R}^n$ thỏa mãn một điều kiện buộc nào đó và xảy ra dấu đẳng thức thì ta nói $X$ \emph{thỏa mãn chặt}, còn nếu không xảy ra dấu đẳng thức thì ta nói $X$ \emph{thỏa mãn lỏng} điều kiện buộc đó.

Mỗi $X=(x_j)\in\mathbb{R}^n$ thỏa mãn hệ điều kiện buộc gọi là một \emph{phương án}. Ta thường ký hiệu tập phương án là $M$.

Một phương án làm cực tiểu (hoặc cực đại) hàm mục tiêu gọi là một \emph{phương án tối ưu} (hay gọi là \emph{nghiệm} của bài toán).
\vskip 0.2cm
\noindent\textbf{3.1.2.2 Bài toán quy hoạch tuyến tính dạng chính tắc}
\vskip 0.2cm
Bài toán quy hoạch tuyến tính có dạng
\begin{align}
\min\{f(X)=\sum_{j=1}^nc_jx_j\}\;\;\;\;\;\;\;\;\;\;\;\;\label{3.2}\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
\sum\limits_{j=1}^na_{ij}x_j=b_i, i=1, 2, ..., m,\\
x_j\geq0, j=1, 2, ..., n.
\end{array} \right.\notag
\end{align}
 gọi là \emph{bài toán quy hoạch tuyến tính dạng chính tắc}.

Chú ý rằng bài toán quy hoạch tuyến tính tổng quát có thể đưa về bài toán quy hoạch tuyến tính dạng chính tắc tương đương nhờ các quy tắc sau đây (xin dành cho độc giả phần chứng minh tương đương):

+ Nếu có $\max\{f(X)\}$ thì ta đổi thành $\min\{- f(X)\}$. Sau khi tìm được phương án tối ưu, ta có $\max\{f(X)\} = - \min\{-f(X)\}$.

+ Nếu có bất đẳng thức $\sum\limits_{j=1}^na_{ij}x_j\geq b_i$ hoặc $\sum\limits_{j=1}^na_{ij}x_j\leq b_i$ thì ta đưa thêm \emph{ẩn phụ} $x_{n+i}\geq0$ với \emph{hệ số hàm mục tiêu} $c_{n+i} = 0$ để có
$$\sum\limits_{j=1}^na_{ij}x_j-x_{n+i}= b_i\;\text{hoặc}\;\sum\limits_{j=1}^na_{ij}x_j+x_{n+i}= b_i.$$
+ Nếu có ẩn $x_k$ chưa ràng buộc về dấu, thì ta có thể thay nó bởi hai ẩn mới $x_k'\geq0$, $x_k''\geq 0$, với $x_k = x_k' - x_k''$.
\vskip 0.2cm
\noindent\textbf{Ví dụ 1.} Đưa bài toán quy hoạch tuyến tính sau đây về dạng chính tắc
$$\max\{f(X)=- x_1 + x_2 + x_3\}$$
$$\text{với điều kiện:} \left\{ \begin{array}{ll}
x_1 +  x_2 + x_3 = 5\\
x_1 - 2x_2 + x_3 \leq 3\\
x_1 +  x_2 -  x_3 \geq 4\\
x_1, x_3\geq0.
\end{array} \right.$$
\emph{Giải}. Ta thay $\max\{f(X)\}$ bởi $\min\{- f(X)\}$, đưa thêm ẩn phụ $x_4, x_5 \geq 0$ và thay $x_2$ bởi $x_2 = x_2' - x_2''$, với $x_2', x_2'' \geq 0$, để có
$$\min\{x_1 - x_2' + x_2'' - x_3\}$$
$$\text{với điều kiện:} \left\{ \begin{array}{ll}
x_1 +  x_2' -  x_2''  + x_3 = 5\\
x_1 - 2x_2' + 2x_2'' + x_3 + x_4       = 3\\
x_1 +  x_2' -    x_2''  -  x_3     -  x_5   = 4\\
x_1, x_2' , x_2'' , x_3, x_4, x_5 \geq0.
\end{array} \right.$$

Như vậy, từ nay về sau ta chỉ cần nghiên cứu bài toán quy hoạch tuyến tính ở dạng chính tắc. Trong trường hợp cần thiết, chúng ta sẽ nhắc lại với các dạng khác nhau.

Để thuận lợi trong trình bày, chúng ta đưa ra các cách viết khác nhau của bài toán \eqref{3.2} như sau:
\vskip 0.2cm
\emph{a) Cách viết theo ma trận:}

Ký hiệu ma trận hàng $C = (c_1\; c_2\; ...\; c_n)$ cấp $1 \times n$, các ma trận cột $X = (x_1\; x_2\; ...\; x_n)^T$ cấp $n\times1$, $B = (b_1\; b_2\; ...\; b_m)^T$ cấp $m\times1$ và ma trận $A = (a_{ij})$ cấp $m\times n$.

Khi đó ta có bài toán
$$\min\{CX\}$$
$$\text{với điều kiện:} \left\{ \begin{array}{ll}
AX=B\\
X \geq0.
\end{array} \right.$$

\emph{b) Cách viết theo vectơ:}

Ký hiệu các vectơ

$$C = (c_1, c_2, ..., c_n) \in \mathbb{R}^n, X = (x_1, x_2, ..., x_n) \in \mathbb{R}^n$$
$$  A_0 = (b_1, b_2, ..., b_m) \in \mathbb{R}^m, A_j  = (a_{1j}, a_{2j}, ..., a_{mj}) \in \mathbb{R}^m, j = 1, 2, ..., n.$$

Khi đó ta có bài toán
$$\min\langle C, X\rangle$$
$$\text{với điều kiện:} \left\{ \begin{array}{ll}
x_1A_1 + x_2A_2 + ... + x_nA_n = A_0\\
x_1, x_2, ...., x_n \geq0.
\end{array} \right.$$

\noindent\textbf{Ví dụ 2.} Cho bài toán quy hoạch tuyến tính dạng chính tắc
$$\min\{f=x_1 - x_2 + x_3\}$$
$$\text{với điều kiện:} \left\{ \begin{array}{ll}
x_1 +  x_2 + x_3              = 5\\
x_1 - 2x_2 + x_3 + x_4       = 3\\
x_1 +  x_2  -  x_3     -  x_5   = 4\\
x_1, x_2, x_3, x_4, x_5 \geq0.
\end{array} \right.$$

Ta có ma trận  $A$ và các ma trận cột (vectơ cột) $A_j$ là
$$A=\left(\begin{array}{ccccc}
  1 & 1 & 1 & 0 & 0 \\
  1 & -2 & 1 & 1 & 0 \\
  1 & 1 & -1 & 0 & -1
\end{array}\right),$$
$$A_1=\left(
    \begin{array}{c}
      1 \\
      1 \\
      1 \\
    \end{array}
  \right),
 A_2=\left(
    \begin{array}{c}
      1 \\
      -2 \\
      1 \\
    \end{array}
  \right),
  A_3=\left(
    \begin{array}{c}
      1 \\
      1 \\
      -1 \\
    \end{array}
  \right),
  A_4=\left(
    \begin{array}{c}
      0 \\
      1 \\
      0 \\
    \end{array}
  \right),
  A_5=\left(
    \begin{array}{c}
      0 \\
      0 \\
      -1 \\
    \end{array}
  \right).
$$
\vskip 0.2cm
\noindent\textbf{3.1.2.3 Bài toán quy hoạch tuyến tính dạng chuẩn tắc}
\vskip 0.2cm
Khi bài toán quy hoạch tuyến tính có dạng
\begin{align}
\min\{f(X)=\sum_{j=1}^nc_jx_j\}\label{3.3}
\end{align}
\begin{align*}
\text{với điều kiện:} \left\{ \begin{array}{ll}
\sum\limits_{j=1}^na_{ij}x_j\geq b_i, i=1, 2, ..., m,\\
x_j\geq0, j=1, 2, ..., n.
\end{array} \right.
\end{align*}
thì ta nói bài toán có \emph{dạng chuẩn tắc}.

\subsection{Một số tính chất của bài toán quy hoạch tuyến tính}
\textbf{3.1.3.1 Một số kiến thức cần thiết về giải tích lồi trên không gian $\mathbb{R}^n$}
\vskip 0.2cm
$\ast$ \emph{Tổ hợp lồi:} Cho hệ hữu hạn điểm $X_1, X_2, ..., X_k$ trên $\mathbb{R}^n$. Khi đó, mỗi điểm
$$X=\sum_{j=1}^k\lambda_jX_j, \;\lambda_j\geq0, \sum_{j=1}^k\lambda_j=1$$
gọi là một \emph{tổ hợp lồi} của hệ điểm đã cho.
\vskip 0.2cm
$\ast$ \emph{Tập hợp lồi:} Tập hợp $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, Y\in M$ và số thực $\lambda\in[0, 1]$ ta có
$$Z= \lambda X+(1-\lambda) Y\in M.$$

$\ast$ \emph{Điểm cực biên:} Cho $M\subset\mathbb{R}^n$ là một tập hợp lồi. Điểm $X\in M$ được gọi là \emph{điểm cực biên} của $M$ nếu không tồn tại $X_1$ và $X_2$ thuộc $M$ và $\lambda\in (0,1)$ sao cho
$$X= \lambda X_1+(1-\lambda) X_2.$$

$\ast$ Tập $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 $M$ là \emph{tập lồi đa diện}.
\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 gọi là \emph{đa diện lồi}.
\vskip 0.2cm
$\ast$ \textbf{Định lý}. (Định lý biểu diễn đa diện lồi) Đa diện lồi $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 M$ thì
$$X =  \sum_{j=1}^r\lambda_jX_j, \;\lambda_j\geq0, \sum_{j=1}^r\lambda_j=1.$$
\vskip 0.2cm
\noindent\textbf{3.1.3.2 Một số tính chất cơ bản của bài toán quy hoạch tuyến tính}
\vskip 0.2cm
\textbf{Tính chất 1:} \emph{Tập phương án của bài toán quy hoạch tuyến tính là một tập lồi đa diện}.

 Điểm cực biên của tập lồi các phương án gọi là \emph{phương án cực biên}.
\vskip 0.2cm
\textbf{Tính chất 2:} \emph{Nếu tập phương án của bài toán quy hoạch tuyến tính là đa diện lồi thì tồn tại phương án cực biên tối ưu.}
\vskip 0.1cm
\emph{Chứng minh.} Không mất tính tổng quát, ta xét bài toán quy hoạch tuyến tính dạng $\min$. Giả sử M là tập phương án. Theo định lý biểu diễn đa diện lồi thì M có hữu hạn phương án cực biên $X_1, X_2, ..., X_r$ và với mọi $X\in M$ ta có
$$X=\sum_{i=1}^r\lambda_i X_i,\;\text{với mọi}\;\lambda_i\geq0, \sum_{i=1}^r\lambda_i=1.$$

Đặt $$f(X_l)=\min_{1\leq i\leq r}f(X_i).$$

Khi đó,
\begin{align*}
  f(X)&=f(\sum_{i=1}^r\lambda_i X_i)\\
  &=\sum_{i=1}^r\lambda_i f(X_i)\\
  &\geq \sum_{i=1}^r\lambda_i f(X_l)\\
  &=f(X_l)\sum_{i=1}^r\lambda_i f(X_l)=f(X_l).
\end{align*}

Vậy $f(X)\geq f(X_l)$ với mọi $X\in M$. Điều này có nghĩa là $X_l$ là phương án tối ưu.
\vskip 0.2cm
\textbf{Tính chất 3:} \emph{Nếu bài toán quy hoạch tuyến tính có phương án tối ưu, thì có ít nhất một phương án cực biên tối ưu.}
\vskip 0.1cm
\emph{Chứng minh.} Xem tài liệu [2].
\vskip 0.2cm
\textbf{Tính chất 4:} \emph{Xét bài toán quy hoạch tuyến tính dạng chính tắc. Phương án $X = (x_j)$ là cực biên khi và chỉ khi hệ vectơ cột $\{A_j: x_j>0\}$ độc lập tuyến tính.}
\vskip 0.1cm
\emph{Chứng minh.} Không mất tính tổng quát, giả sử phương án $X$ có dạng
$$X=(x_1, x_2, ..., x_k, 0, ..., 0)$$
trong đó $x_1, x_2, ..., x_k>0$.
\vskip 0.2cm
\emph{Điều kiện cần:} Cho $X$ là phương án cực biên. Ta cần chứng minh hệ $A_1A_2...A_k$ độc lập tuyến tính.

Thật vậy, ta chứng minh bằng phương pháp phản chứng: Giả sử ngược lại, hệ $A_1A_2...A_k$  phụ thuộc tuyến tính. Khi đó, tồn tại $\alpha_i\neq 0$ sao cho
$$\alpha_1 A_1+\alpha_2 A_2+...+\alpha_k A_k=0.$$

Do $X$ là phương án nên
$$x_1 A_1+x_2 A_2+...+x_k A_k=A_0.$$

Từ đó, ta có
$$(x_1\pm\theta\alpha_1) A_1+(x_2\pm\theta\alpha_2) A_2+...+(x_k\pm\theta\alpha_k) A_k=A_0.$$

Vì $x_1, x_2, ..., x_k>0$ nên có thể chọn được $\theta>0$ đủ bé sao cho $x_i\pm\theta\alpha_i\geq0$ với mọi $i=1,2,..., k$. Khi đó ta được
\begin{align*}
  X_1&= (x_1+\theta\alpha_1, x_2+\theta\alpha_2, ..., x_k+\theta\alpha_k, 0, ..., 0)\\
  X_2&= (x_1-\theta\alpha_1, x_2-\theta\alpha_2, ..., x_k-\theta\alpha_k, 0, ..., 0)
\end{align*}
là hai phương án khác nhau (vì tồn tại $\alpha_i\neq 0$).

Tuy nhiên, $X=\frac{1}{2}X_1+\frac{1}{2}X_2$. Điều này mâu thuẫn với $X$ là phương án cực biên. Vậy hệ $A_1A_2...A_k$ độc lập tuyến tính.
\vskip 0.2cm
\emph{Điều kiện đủ.} Cho hệ vector cột $A_1A_2...A_k$ của ma trận $A$ sao cho
$$x_1 A_1+x_2 A_2+...+x_k A_k=A_0$$
(với $x_1, x_2, ..., x_k>0$) là độc lập tuyến tính. Ta cần chứng minh
$$X=(x_1, x_2, ..., x_k, 0, ..., 0)$$ là phương án cực biên.

Ta chứng minh bằng phản chứng: Giả sử $X$ không là phương án cực biên. Khi đó, tồn tại $Y_1=(y_i^{(1)})$, $Y_2=(y_i^{(2)})$ thuộc $M$ ($Y_1\neq Y_2$) sao cho
$$X=\lambda Y_1+(1-\lambda)Y_2, 0<\lambda<1.$$

Do $x_j=\lambda y_i^{(1)}+(1-\lambda)y_i^{(2)}=0$ với $0<\lambda<1$, $j=k+1, ..., n$ nên ta có $y_i^{(1)}=y_i^{(2)}=0$, với $i=k+1, ..., n$. Tức là $Y_1$ và $Y_2$ thỏa mãn
\begin{align*}
  y_1^{(1)} A_1+y_2^{(1)} A_2+...+y_k^{(1)} A_k&=A_0\\
  y_1^{(2)} A_1+y_2^{(2)} A_2+...+y_k^{(2)} A_k&=A_0.
\end{align*}
Từ đó, ta được
$$(y_1^{(1)}-y_1^{(2)}) A_1+(y_2^{(1)}-y_2^{(2)}) A_2+...+(y_k^{(1)}-y_k^{(2)}) A_k=0.$$

Vì $Y_1\neq Y_2$ nên tồn tại $y_i^{(1)}-y_i^{(2)}\neq0$. Do vậy, hệ vector $A_1A_2...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$ phải là phương án cực biên.

Tính chất được chứng minh xong.

\vskip 0.2cm
Hệ vectơ cột $\{A_j: x_j>0\}$ nêu trên còn được gọi là \emph{cơ sở liên kết} của phương án cực biên $X = (x_j)$. Các ẩn $x_j$ tương ứng với vectơ cột $A_j$ trong cơ sở liên kết được gọi là \emph{ẩn cơ sở}.

Không mất tính tổng quát, các điều kiện buộc của bài toán quy hoạch tuyến tính được giả thiết độc lập. Từ đó, ta suy ra:

$a)$ \emph{Số toạ độ dương của phương án cực biên của bài toán quy hoạch tuyến tính dạng chính tắc có tối đa là $m$.}

$b)$ \emph{Số phương án cực biên của bài toán quy hoạch tuyến tính là hữu hạn.}
\vskip 0.2cm
\textbf{Tính chất 5:} \emph{Phương án $X$ của bài toán quy hoạch tuyến tính là phương án cực biên khi và chỉ khi $X$ thỏa mãn chặt ít nhất $n$ điều kiện buộc độc lập.}
\vskip 0.2cm
Phương án cực biên có đủ $m$ toạ độ dương được gọi là \emph{phương án cực biên không suy biến}. Từ định nghĩa này, ta thấy rằng phương án cực biên $X$ suy biến khi và chỉ khi nó thoả mãn chặt nhiều hơn $n$ ràng buộc. Bài toán quy hoạch tuyến tính có tất cả các phương án cực biên không suy biến được gọi là \emph{bài toán không suy biến}.
\vskip 0.2cm
\textbf{Ví dụ 3.} Cho bài toán quy hoạch tuyến tính
\begin{align*}
\max \{f(X) = 3x_1 + 5x_2\}\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
2x_1 +  x_2\leq 8\\
x_2 \leq 4\\
x_1 \leq 3\\
x_1, x_2 \geq0.
\end{array} \right.
\end{align*}

$a)$ Hãy chứng tỏ bài toán có phương án tối ưu.

$b)$ Đưa bài toán đã cho về dạng chính tắc. Tìm phương án cực biên (nếu có) ứng với cơ sở liên kết $A_2A_3A_5$.
\vskip 0.2cm
\emph{Giải:} $a)$ Ta thấy điểm $(0, 0)$ là một phương án. Do vậy tập phương án khác rỗng.
Mặt khác, từ điều kiện $2x_1 + x_2 \leq 8$ và $x_1, x_2 \geq 0$, ta có $0 \leq x1, x2 \leq 8$. Điều đó chứng tỏ tập phương án bị chặn. Vậy tập phương án là một đa diện lồi. Theo Tính chất 2 thì bài toán có phương án tối ưu.

$b)$ Đưa thêm ẩn phụ $x_3, x_4, x_5 \geq 0$, ta có bài toán dạng chính tắc như sau
\begin{align*}
\min \{-f(X) = -3x_1 - 5x_2\}\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
2x_1 +  x_2+x_3= 8\\
x_2 +x_4= 4\\
x_1 +x_5= 3\\
x_1, x_2, x_3, x_4, x_5 \geq0.
\end{array} \right.
\end{align*}

 Phương án cực biên ứng với hệ vectơ $A_2A_3A_5$ (nếu có) phải có dạng
$$X = (0, x_2, x_3, 0, x_5).$$

Thay vào hệ điều kiện buộc, ta thu được phương án cực biên cần tìm là $X  = (0, 4, 4, 0, 3)$.
\vskip 0.2cm
\textbf{Tính chất 6:} \emph{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.}
\vskip 0.1cm
\emph{Chứng minh.} Giả sử $X_1$ và $X_2$ là hai phương án tối ưu khác nhau:
$$f(X_1)=f(X_2)\leq f(X)\;\text{với mọi}\;X\in M.$$

Khi đó, ta xét $Y=\lambda X_1+(1-\lambda)X_2$ với $0<\lambda<1$. Do $M$ là tập lồi nên ta suy ra $Y$ là phương án.
Mặt khác,
\begin{align*}
  f(Y)&=\lambda f(X_1)+(1-\lambda)f(X_2)\\
  &=\lambda f(X_1)+(1-\lambda)f(X_1)\\
  &=f(X_1)\leq f(X)
\end{align*}
với mọi $X\in M$.

Điều này chứng tỏ $Y$ cũng là phương án tối ưu. Như vậy bài toán có vô số phương án tối ưu.
\vskip 0.2cm
\textbf{Tính chất 7:} \emph{Mỗi phương án cực biên của tập phương án $M$ đều tồn tại một hàm mục tiêu để nó là phương án tối ưu duy nhất.}
\vskip 0.1cm
\emph{Chứng minh.} Cho $X=(x_j)$ là phương án cực biên với cơ sở liên kết có ma trận ký hiệu là $\mathcal{B}$. Ký hiệu tập chỉ số cơ sở của $X$ là $J$. Đặt
$$c_j=\left\{ \begin{array}{ll}
0\;\;\text{nếu}\;j\in J,\\
1\;\;\text{nếu}\;j\notin J.
\end{array} \right.$$

Rõ ràng ta có $f(X)=0$ ($f$ là hàm mục tiêu có các hệ số là $(c_j)$).

Tuy nhiên, với mọi phương án $Y$ ta đều có $f(Y)\geq 0$. Điều này chứng tỏ $X$ là phương án tối ưu.

Đồng thời, nếu có phương án $Y=(y_j)$ là phương án tối ưu thì $f(Y)=0$. Do $c_j=1$ với mọi $j\notin J$ nên $y_j=0$ với mọi $j\notin J$. Do ma trận $\mathcal{B}$ không suy biến nên từ hệ phương trình $\mathcal{B} X=B$ và $\mathcal{B} Y=B$ ta suy ra $X=Y$. Do đó, phương án $X$ là tối ưu duy nhất.
\vskip 0.2cm
\textbf{Tính chất 8:} \emph{Nếu hàm mục tiêu $f$ bị chặn dưới đối với bài toán $\min f$ (bị chặn trên đối với bài toán $\max f$) trên tập phương án khác rỗng thì bài toán quy hoạch tuyến tính tồn tại phương án tối ưu.}
\vskip 0.2cm
 \textbf{Nhận xét:} Bài toán quy hoạch tuyến tính sẽ không có phương án tối ưu khi và chỉ khi xảy ra một trong hai tình huống: hoặc là tập phương án rỗng, hoặc là hàm mục tiêu không bị chặn trên tập phương án (bị chặn dưới đối với bài toán $\min f$ và bị chặn trên đối với bài toán $\max f$).
\vskip 0.2cm
 \textbf{Ví dụ 4.} Cho bài toán quy hoạch tuyến tính
\begin{align*}
\max \{f(X) = 3x_1 - 5x_2\}\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
2x_1 -  x_2\leq 8\\
x_1 \leq 3\\
x_1, x_2 \geq0.
\end{array} \right.
\end{align*}
 Hãy chứng tỏ bài toán có phương án tối ưu.
\vskip 0.2cm
\emph{Giải.} Rõ ràng tập phương án $M$ không bị chặn. Do đó ta không chứng minh được theo cách đã làm ở Ví dụ 3.

Rõ ràng điểm $(0, 0)$ là một phương án, do vậy tập phương án khác rỗng.  Do điều kiện $x_1\leq 3$ và $x_2\geq 0$ nên
$$f(X)=3x_1 - 5x_2\leq 3x_1\leq 9$$
với mọi $X=(x_1, x_2)\in M$. Do đó, hàm mục tiêu bị chặn trên xét trên tập phương án. Theo Tính chất 8, ta suy ra bài toán đã cho có phương án tối ưu.

\subsection{Cặp bài toán đối ngẫu và ứng dụng}
\textbf{3.1.4.1 Cặp bài toán đối ngẫu}
\vskip 0.2cm
Cho bài toán quy hoạch tuyến tính dạng chuẩn tắc
\begin{align}\label{3.4}
\min \{f(X) = \sum_{j=1}^nc_jx_j\}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
\sum\limits_{j=1}^na_{ij}x_j\geq b_i, i=1,2,..., m\\
x_j \geq0, j=1,2,...,n.
\end{array} \right.\notag
\end{align}
Bài toán \eqref{3.4} gọi là \emph{bài toán gốc}.
\vskip 0.2cm
Bài toán sau sẽ được gọi là \emph{bài toán đối ngẫu đối xứng} của bài toán gốc:
\begin{align}\label{3.5}
\max \{g(Y) = \sum_{i=1}^mb_iy_i\}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
\sum\limits_{i=1}^ma_{ij}y_i\leq c_j, j=1,2,..., n\\
y_i \geq0, i=1,2,...,m.
\end{array} \right.\notag
\end{align}

Bài toán \eqref{3.4} cùng bài toán \eqref{3.5} tạo thành \emph{cặp bài toán đối ngẫu đối xứng}. Chú ý rằng do tính đối xứng của cặp bài toán nên khái niệm bài toán gốc và bài toán đối ngẫu chỉ có tính chất tương đối, nghĩa là nếu bài toán này là gốc thì bài toán kia là đối ngẫu.
\vskip 0.2cm
Các bài toán \eqref{3.4} và \eqref{3.5} được viết dưới dạng ma trận là
\begin{align*}
  \min\{CX: AX\geq B, X\geq0\},\\
  \max\{YB: YA\leq C, Y\geq0\}.
\end{align*}
Ta có thể hình dung cặp bài toán đối ngẫu được viết theo cách mô tả dạng ma trận như sau:


\vskip 0.1cm
\begin{center}
\begin{tabular}{ | p{1cm}  | p{1cm} | p{1cm}  |p{1cm} | p{1cm}  | p{1cm} | p{1cm}  |}
    \hline
$\min$ & $x_1$ & $x_2$ & ... & $x_n$ &  & $\geq0$\\ \hline
$\sum\limits_{j=1}^n$ & $\leq\;c_1$ & $\leq\;c_2$ & ... & $\leq\;c_n$ &  &  \\ \hline
& $a_{11}$ & $a_{12}$ & ... & $a_{1n}$ & $\geq\;b_1$ & $y_1$ \\ \hline
& $a_{21}$ & $a_{22}$ & ... & $a_{2n}$ & $\geq\;b_2$ & $y_2$ \\ \hline
& ... & ... & ... & ... & ... & ... \\\hline
& $a_{m1}$ & $a_{m2}$ & ... & $a_{mn}$ & $\geq\;b_m$ & $y_m$ \\ \hline
     &  &  &  &  & $\max$ & $\sum\limits_{i=1}^m$ \\ \hline
    \end{tabular}
    \end{center}
  \vskip 0.1cm


Tổng quát, ta có các \emph{cặp đối ngẫu}  sau đây giữa bài toán gốc và bài toán đối ngẫu và cũng chính là quy tắc để lập bài toán đối ngẫu của một bài toán quy hoạch tuyến tính:

+ $\min$ đối ngẫu với $\max$;

+ Các hệ số hàm mục tiêu $c_1, c_2, ..., c_n$ đối ngẫu với các hệ số tự do $b_1, b_2, ..., b_m$;

+ Ma trận hệ số $A=(a_{ij})$ đối ngẫu với ma trận chuyển vị của nó;

 + Điều kiện dạng đẳng thức, bất đẳng thức thứ $i$: $\sum\limits_{j=1}^na_{ij}x_j\geq (\leq, =) b_i$ đối ngẫu với điều kiện về dấu của ẩn thứ $i$. Khi đó, dấu của đẳng thức, bất đẳng thức sẽ đối ngẫu với dấu của ẩn theo quy tắc sau:

``Nếu bài toán gốc là $\min$ thì \emph{giữ trước, đổi sau}, nghĩa là dấu của điều kiện dạng bất đẳng thức sẽ giữ nguyên, dấu của ẩn sẽ đổi. Nếu bài toán gốc là $\max$ thì \emph{đổi trước, giữ sau}, nghĩa là dấu của điều kiện dạng bất đẳng thức sẽ đổi, dấu của ẩn sẽ giữ nguyên. Riêng điều kiện dạng đẳng thức sẽ đối ngẫu sẽ là ẩn không ràng buộc về dấu''.
\vskip 0.2cm
\textbf{Ví dụ 5.} Cho bài toán quy hoạch tuyến tính
\begin{align*}
\min \{f = 2x_1 - x_2+x_3\}\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
x_1 + 2 x_2-x_3\geq 2\\
2x_1-x_2+2x_3 \geq 5\\
x_1, x_2, x_3 \geq0.
\end{array} \right.
\end{align*}
Bài toán đối ngẫu là
\begin{align*}
\max \{g = 2y_1 +5 y_2\}\;\;\;\;\;\;\;\;\;\;\;\;\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
y_1 +  2y_2\leq 2\\
2y_1-y_2\leq -1\\
-y_1+2y_2\leq 1\\
y_1, y_2 \geq0.
\end{array} \right.
\end{align*}

Nếu bài toán quy hoạch tuyến tính cho dưới dạng chính tắc
\begin{align}\label{3.6}
\min \{f(X) = \sum_{j=1}^nc_jx_j\}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
\sum\limits_{j=1}^na_{ij}x_j= b_i, i=1,2,..., m\\
x_j \geq0, j=1,2,...,n.
\end{array} \right.\notag
\end{align}
thì bài toán đối ngẫu sẽ là
\begin{align}\label{3.7}
\max \{g(Y) = \sum_{i=1}^mb_iy_i\}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
\sum\limits_{i=1}^ma_{ij}y_i\leq c_j, j=1,2,..., n.
\end{array} \right.\notag
\end{align}
Khi đó, cặp bài toán \eqref{3.6} và \eqref{3.7} gọi là \emph{cặp bài toán đối ngẫu không đối xứng}.
\vskip 0.2cm
\noindent\textbf{3.1.4.2 Tính chất của cặp bài toán đối ngẫu}
\vskip 0.2cm
\textbf{Tính chất 1:} \emph{Với mọi cặp phương án $X$ và $Y$ của cặp bài toán đối ngẫu đối xứng, ta có}
$$g(Y)\leq f(X).$$
\vskip 0.2cm
\textbf{Tính chất 2:} \emph{Nếu $X^*, Y^*$ lần lượt là phương án của cặp bài toán đối ngẫu, thoả mãn $f(X^*) = g(Y^*)$ thì $X^*, Y^*$ lần lượt là phương án tối ưu của mỗi bài toán.}
\vskip 0.2cm
\textbf{Tính chất 3:} (Định lý đối ngẫu) \emph{Xét cặp bài toán đối ngẫu. Khi đó}

$a)$ \emph{Nếu bài toán này có phương án tối ưu thì bài toán kia cũng có phương án tối ưu, đồng thời}
$$\min f(X)=\max g(Y).$$
 $b)$ \emph{Nếu hàm mục tiêu của bài toán này không bị chặn trên tập phương án thì bài toán kia có tập phương án rỗng.}
 \vskip 0.2cm
 \textbf{Nhận xét:} Nếu tập phương án của bài toán gốc và bài toán đối ngẫu đều khác rỗng thì chúng đều có phương án tối ưu.
\vskip 0.2cm
\textbf{Tính chất 4:} (Định lý lệch bù) \emph{Cặp phương án $X^*$, $Y^*$ của cặp bài toán đối ngẫu là phương án tối ưu (của mỗi bài toán tương ứng) khi và chỉ khi với mọi cặp điều kiện đối ngẫu, nếu điều kiện này thỏa mãn lỏng thì điều kiện đối ngẫu thỏa mãn chặt.}
\vskip 0.2cm
Chúng ta có thể phát biểu tường minh định lý lệch bù cho hai trường hợp cặp bài toán đối ngẫu đối xứng và cặp bài toán đối ngẫu không đối xứng như sau:
\vskip 0.2cm
$a)$ Cặp phương án $X^*= (x_j^*), Y^* = (y_i^*)$ của cặp bài toán đối ngẫu đối xứng là phương án tối ưu (tương ứng của mỗi bài toán) khi và chỉ khi

+) Nếu $x_j^*>0$ thì $\sum\limits_{i=1}^ma_{ij}y_i^*=c_j$\\
(hoặc nếu $\sum\limits_{i=1}^ma_{ij}y_i^*<c_j$ thì $x_j^*=0$),

+) Nếu $y_i^*>0$ thì $\sum\limits_{j=1}^na_{ij}x_j^*=b_i$\\
(hoặc nếu $\sum\limits_{j=1}^na_{ij}x_j^*>b_i$ thì $y_i^*=0$).
\vskip 0.2cm
$b)$ Cặp phương án $X^*= (x_j^*), Y^* = (y_i^*)$ của cặp bài toán đối ngẫu không đối xứng là phương án tối ưu (tương ứng của mỗi bài toán) khi và chỉ khi nếu $x_j^*>0$ thì $\sum\limits_{i=1}^ma_{ij}y_i^*=c_j$ (hoặc nếu $\sum\limits_{i=1}^ma_{ij}y_i^*<c_j$ thì $x_j^*=0$).
\vskip 0.2cm
\textbf{Ví dụ 6.} Cho bài toán quy hoạch tuyến tính
\begin{align*}
\min \{f = x_2 - x_4-3x_5\}\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
x_1 + 2 x_2-x_4+x_5=1\\
-4x_2+x_3+2x_4-x_5 =2\\
3x_2+x_5+x_6=2\\
x_1, x_2, x_3, x_4, x_5, x_6 \geq0.
\end{array} \right.
\end{align*}

$a)$ Điểm $X = (1, 0, 0, 2, 2, 0)$ có phải là phương án tối ưu hay không?

$b)$ Thay $c_2 = \lambda$, tìm tất cả các giá trị của $\lambda$ để phương án đã cho ở câu $a)$ là tối ưu.

\emph{Giải.} $a)$ Trước hết ta thử các điều kiện cho thấy $X$ đã cho là một phương án. Xét bài toán đối ngẫu
\begin{align*}
\max \{g = y_1 +2 y_2+2y_3\}\;\;\;\;\;\;\;\;\;\;\;\;\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
y_1 \leq 0\\
2y_1-4y_2+3y_3\leq 1\\
y_2\leq 0\\
-y_1+2y_2\leq -1\\
y_1-y_2+y_3\leq -3\\
y_3 \leq0.
\end{array} \right.
\end{align*}

Do $x_1, x_4, x_5 > 0$, nên áp dụng định lý lệch bù, ta có hệ phương trình:
$$\left\{ \begin{array}{ll}
y_1 = 0\\
-y_1+2y_2= -1\\
y_1-y_2+y_3= -3.\\
\end{array} \right.$$
 Giải hệ ta được nghiệm $Y = (0, -1/2, -7/2)$. Thử lại điều kiện cho thấy $Y$ là phương án. Từ đó ta có $X$ là phương án tối ưu (và ta cũng có được $Y$ là phương án tối ưu của bài toán đối ngẫu), với giá trị hàm mục tiêu $f_{\min}= g_{\max} = - 8$.

$b)$ Nếu thay $c_2 = \lambda$ thì bài toán đối ngẫu sẽ là
\begin{align*}
\max \{g = y_1 +2 y_2+2y_3\}\;\;\;\;\;\;\;\;\;\;\;\;\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
y_1 \leq 0\\
2y_1-4y_2+3y_3\leq 1\lambda\\
y_2\leq 0\\
-y_1+2y_2\leq -1\\
y_1-y_2+y_3\leq -3\\
y_3 \leq0.
\end{array} \right.
\end{align*}

Để $X$ tối ưu thì $Y = (0, -1/2, -7/2)$ phải là phương án, tức là $Y$ phải thỏa mãn điều kiện thứ hai (dễ thấy các điều kiện còn lại đã thỏa mãn). Từ đó suy ra
$$2y_1 - 4y_2 + 3y_3  \leq \lambda \Leftrightarrow \lambda\geq -17/2.$$
Độc giả có thể kiểm tra lại để thấy rằng với $\lambda < -(17/2)$ (chẳng hạn  $\lambda = -9$) thì $X$ đã cho không tối ưu.

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

\subsection{Cơ sở lý luận của phương pháp đơn hình}

\textbf{3.2.1.1 Ý tưởng chung của phương pháp}
\vskip 0.2cm
 Trên cơ sở các tính chất đã nêu trong các mục trước, chúng ta có thể duyệt các phương án cực biên bằng cách: Xuất phát từ phương án cực biên X0 nào đó, kiểm tra X0 có tối ưu hay không?

- Nếu $X_0$ tối ưu thì dừng.

- Nếu chưa, xây dựng phương án cực biên mới $X_1$ tốt hơn $X_0$.

Quá trình tiếp tục như vậy, ta được dãy các phương án cực biên tốt dần (theo nghĩa giá trị hàm mục tiêu giảm dần từ phương án cực biên trước đến phương án cực biên sau) $X_0, X_1, ..., X_k$. Sau hữu hạn bước lặp ta được phương án tối ưu hoặc phát hiện ra bài toán không có phương án tối ưu. Đó là nội dung của quá trình xây dựng dãy các phương án cực biên tốt dần, còn gọi là phương pháp đơn hình (simplex method).

Cũng từ ý tưởng của phương pháp đơn hình, tận dụng các tính chất riêng của bài toán vận tải, người ta xây dựng được phương pháp phân phối giải bài toán vận tải.
\vskip 0.2cm
\noindent\textbf{3.2.1.2 Giả thiết ban đầu}
\vskip 0.2cm
Ta xét bài toán quy hoạch tuyến tính sau:
\begin{align}\label{3.8}
\min \{f(X) = \sum_{j=1}^nc_jx_j\}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
x_i+\sum\limits_{j=1,\;j\notin I}^na_{ij}x_j= b_i, i\in I\\
x_j \geq0, j=1,2,...,n.
\end{array} \right.\notag
\end{align}
với điều kiện

+ các điều kiện buộc là độc lập,

+ $b_i\geq 0$ với mọi $i=1, 2, ..., m$,

+ $I$ là tập chỉ số gồm $m$ chỉ số và $I\subset\{1, 2, ..., n\}$.

+ Bài toán không suy biến.
\vskip 0.2cm
Khi đó, ta nói bài toán quy hoạch tuyến tính \emph{có cơ sở đơn vị}.

Không mất tính tổng quát, giả sử $I=\{1, 2, ..., m\}$. Lúc này phương án cực biên $X_0$ có dạng
$$X_0 = (x_1^0, x_2^0, ..., x_m^0, 0, ..., 0), x_i^0 = b_i, i = 1, 2, ..., m.$$
(bạn đọc tự chứng minh)

với cơ sở liên kết $A_1A_2...A_m$ là ma trận đơn vị.

Ký hiệu
$$\triangle_j=\sum_{i=1}^mc_ia_{ij}-c_j.$$

\vskip 0.2cm
\noindent\textbf{3.2.1.3 Các tính chất cơ sở}
\vskip 0.2cm
\textbf{Định lý 1.} (Dấu hiệu tối ưu) \emph{Nếu tại phương án cực biên $X_0$, ta có $\triangle_j\leq 0$ với mọi $j=1, 2, ..., n$ thì $X_0$ là phương án tối ưu.}
\vskip 0.2cm
\textbf{Định lý 2.} (Dấu hiệu bài toán không có phương án tối ưu) \emph{Nếu tại phương án cực biên $X_0$, tồn tại $\triangle_k>0$ và $a_{ik}\leq0$ với mọi $i=1, 2, ..., 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)}.
\vskip 0.2cm
\textbf{Định lý 3.} (Dấu hiệu xây dựng được phương án cực biên mới tốt hơn) \emph{Nếu tại phương án cực biên $X_0$, tồn tại $\triangle_k>0$ và tồn tại $a_{ik}>0$ thì xây dựng được phương án cực biên mới $X_1$ tốt hơn $X_0$.}
\vskip 0.2cm

\subsection{Thuật toán đơn hình giải bài toán quy hoạch tuyến tính có cơ sở đơn vị}

\textbf{3.2.2.1 Thuật toán}
\vskip 0.2cm
\textbf{Bước 1:} \emph{Lập bảng xuất phát (bảng I).}
\vskip 0.1cm
\begin{center}
\begin{tabular}{ | p{1cm}  | p{1cm} | p{1.5cm}  |p{1cm} | p{1cm}  | p{1cm} | p{1cm}  | p{1cm} | p{1cm}  |}
    \hline
Cơ sở & Hệ số & Tọa độ & $c_1$ & $c_2$ & ... & $c_j$ & ... & $c_n$\\ \hline
 &  &  & $A_1$ & $A_2$ & ... & $A_j$ & ... & $A_n$\\ \hline
... & ... & ... & ... & ... & ... & ... & ... & ...\\ \hline
$A_{k_i}$ & $c_{k_i}$ & $x_{k_i}$ & $a_{i1}$ & $a_{i2}$ & ... & $a_{ij}$ & ... & $a_{in}$\\ \hline
... & ... & ... & ... & ... & ... & ... & ... & ...\\ \hline
 &  & $f(X)$ & $\triangle_1$ & $\triangle_2$ & ... & $\triangle_j$ & ... & $\triangle_n$\\ \hline
    \end{tabular}
    \end{center}
  \vskip 0.1cm
+ Chọn cơ sở xuất phát là cơ sở đơn vị;
\vskip 0.1cm
+ Xác định hàng $c_1, c_2, ..., c_n$ (các hệ số hàm mục tiêu);
\vskip 0.1cm
+ Xác định cột hệ số $c_i$ tương ứng với cột cơ sở;
\vskip 0.1cm
+ Xác định cột tọa độ $x_{k_i}=b_i$, $i=1, 2, ..., m$;
\vskip 0.1cm
+ Xác định hệ số $a_{ij}$ của hệ điều kiện buộc;
\vskip 0.1cm
+ Xác định $f(X)$: Lấy cột cơ sở ``\emph{nhân}'' với cột tọa độ, nghĩa là
$$f(X)=\sum_{i=1}^mc_{k_i} x_{k_i};$$

+ Xác định các giá trị $\triangle_j$ ($j=1, 2, ..., n$): Lấy cột hệ số ``\emph{nhân}'' với cột $A_j$, sau đó trừ đi $c_j$. Nghĩa là
$$\triangle_j=\sum_{i=1}^mc_{k_i} a_{ij}-c_j.$$
\vskip 0.1cm
\textbf{Bước 2:} \emph{Kiểm tra tiêu chuẩn tối ưu.}
\vskip 0.1cm
 + Nếu $\triangle_j\leq 0$ với mọi $j=1, 2, ..., n$ thì dừng lại và kết luận phương án cực biên tương ứng là phương án tối ưu;
\vskip 0.1cm
+ Nếu tồn tại $\triangle_k>0$ và $a_{ik}\leq 0$ với mọi $i=1,2, ..., m$ thì dừng lại và kết luận bài toán quy hoạch tuyến tính không có phương án tối ưu;
\vskip 0.1cm
+ Nếu trái lại, ta chuyển sang Bước 3.
\vskip 0.1cm
\textbf{Bước 3:} \emph{Xây dựng phương án cực biên mới tốt hơn.}
\vskip 0.1cm
+ Xác định $\triangle_k=\max\limits_{\triangle_j>0}\triangle_j$ và đưa $A_k$ vào làm cơ sở;
\vskip 0.1cm
+ Xác định $\min\limits_{a_{ik}>0}\frac{x_i}{a_{ik}}=\frac{x_l}{a_{lk}}$ và đưa $A_l$ ra khỏi cơ sở. Phần tử $a_{lk}$ gọi là \emph{phần tử trục}. Xác định cột hệ số tương ứng cho bảng mới;
\vskip 0.1cm
+ Xây dựng phương án cực biên mới tốt hơn (bảng mới) theo quy tắc sau:
\vskip 0.1cm
$a)$ Cột $A_j$ trong cơ sở là vector đơn vị (ô ứng với hàng $A_j$ bằng $1$, các ô còn lại (kể cả ô $\triangle_j$) đều bằng $0$);
\vskip 0.1cm
$b)$ Các ô ở hàng $A_k$ mới đưa vào: Lấy các ô tương ứng ở bảng cũ (hàng $A_l$) chia cho phần tử trục $a_{lk}$;
\vskip 0.1cm
$c)$ Các ô còn lại: Lấy ô tương ứng ở bảng cũ (làm mốc) trừ đi tích của phần tử gióng ngang tới cột $A_k$ (thuộc bảng cũ) với phần tử gióng dọc xuống hàng $A_k$ (thuộc bảng mới). Nghĩa là
\begin{align*}
a_{ij}'&=a_{ij}-a_{ik}\times a_{kj}',\\
x_i'&=x_i-a_{ik}\times x_k',\\
f'(X)&=f(X)-\triangle_k\times x_k',\\
\triangle_j'&=\triangle_j-\triangle_k\times a_{kj}'.
\end{align*}

Lưu ý rằng các giá trị $f(X)$ và $\triangle_j$ ($j=1, 2, ..., n$) có thể được tính như Bước 1 (bảng I).

$\Rightarrow$ Quay trở lại Bước 2.
\vskip 0.2cm
\noindent\textbf{3.2.2.2 Các ví dụ áp dụng}
\vskip 0.2cm
\textbf{Ví dụ 7.} Giải bài toán sau bằng phương pháp đơn hình
\begin{align*}
\min \{f = x_1-x_2+x_3+x_4+x_5-x_6\}\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
x_1 + x_4+6x_6=9\\
3x_1+x_2-4x_3+2x_6 =2\\
x_1+2x_3+x_5+2x_6=6\\
x_1, x_2, x_3, x_4, x_5, x_6 \geq0.
\end{array} \right.
\end{align*}

\emph{Giải.}  Chọn cơ sở liên kết $A_4A_2A_5$ là các vectơ đơn vị nên ta có phương án cực biên xuất phát
$$X=(0, 2, 0, 9, 6, 0).$$
Ta tính được bảng đơn hình sau.
\vskip 0.1cm
\begin{center}
\begin{tabular}{ | p{1cm}| p{1cm}  | p{1cm} | p{1cm}  |p{1cm} | p{1cm}  | p{1cm} | p{1.2cm}  | p{1cm} | p{1cm}  |}
    \hline
Bảng & Cơ sở & Hệ số & Tọa độ & $1$ & $-1$ & $1$ & $1$ & $1$ & $-1$\\ \hline
 &  &  &  & $A_1$ & $A_2$ & $A_3$ & $A_4$ & $A_5$ & $A_6$\\ \hline\hline
I & $A_4$ & $1$ & $9$ & $1$ & $0$ & $0$ & $1$ & $0$ & $6$\\ \hline
& $A_2$ & $-1$ & $2$ & $3$ & $1$ & $-4$ & $0$ & $0$ & $2$\\ \hline
& $A_5$ & $1$ & $6$ & $1$ & $0$ & $2$ & $0$ & $1$ & $2$\\ \hline
& &  & $13$ & $-2$ & $0$ & $5$ & $0$ & $0$ & $7$\\ \hline\hline
II & $A_4$ & $1$ & $3$ & $-8$ & $-3$ & $12$ & $1$ & $0$ & $0$\\ \hline
& $A_6$ & $-1$ & $1$ & $3/2$ & $1/2$ & $-2$ & $0$ & $0$ & $1$\\ \hline
& $A_5$ & $1$ & $4$ & $-2$ & $-1$ & $6$ & $0$ & $1$ & $0$\\ \hline
& &  & $6$ & $-25/2$ & $-7/2$ & $19$ & $0$ & $0$ & $0$\\ \hline\hline
III & $A_3$ & $1$ & $1/4$ & $-2/3$ & $-1/4$ & $1$ & $1/12$ & $0$ & $0$\\ \hline
& $A_6$ & $-1$ & $3/2$ & $1/6$ & $0$ & $0$ & $1/6$ & $0$ & $1$\\ \hline
& $A_5$ & $1$ & $5/2$ & $2$ & $1/2$ & $0$ & $-1/2$ & $1$ & $0$\\ \hline
& &  & $5/4$ & $1/6$ & $5/4$ & $0$ & $-19/12$ & $0$ & $0$\\ \hline\hline
IV & $A_3$ & $1$ & $3/2$ & $1/3$ & $0$ & $1$ & $-1/6$ & $1/2$ & $0$\\ \hline
& $A_6$ & $-1$ & $3/2$ & $1/6$ & $0$ & $0$ & $1/6$ & $0$ & $1$\\ \hline
& $A_2$ & $-1$ & $5$ & $4$ & $1$ & $0$ & $-1$ & $2$ & $0$\\ \hline
& &  & $-5$ & $-29/6$ & $0$ & $0$ & $-1/3$ & $-5/2$ & $0$\\ \hline
    \end{tabular}
    \end{center}
  \vskip 0.1cm
Tại bảng IV ta có $\triangle_j \leq 0$ với mọi $j  = 1, 2, ..., 6$. Từ đó, phương án tối ưu là
$$X^* = (0, 5, 3/2, 0, 0, 3/2),\;\text{với}\; f_{\min} = - 5.$$
\vskip 0.2cm
Thuật toán đơn hình nêu trên đòi hỏi biết trước phương án cực biên xuất phát $X_0$. Khi bài toán có dạng \eqref{3.8}, ma trận A chứa ma trận đơn vị, khi đó chỉ cần chỉ ra hệ cơ sở đơn vị tương ứng các ẩn cơ sở, ta được phương án cực biên xuất phát $X_0$ (như đã làm ở ví dụ trên).

\subsection{Thuật toán đơn hình giải bài toán quy hoạch tuyến tính chưa có cơ sở đơn vị}
\textbf{3.2.3.1 Bài toán giả tạo}
\vskip 0.2cm
Xét bài toán dạng chính tắc sau
\begin{align*}
\min \{f(X) = \sum_{j=1}^nc_jx_j\}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
\sum\limits_{j=1}^na_{ij}x_j= b_i, i=1,2,..., m\\
x_j \geq0, j=1,2,...,n.
\end{array} \right.\notag
\end{align*}

Khi ma trận $A = (a_{ij})$ không chứa ma trận đơn vị, ta đưa thêm ẩn giả tạo $x_{n+i} \geq 0$, với hệ số hàm mục tiêu $c_{n+i} = M > 0$ đủ lớn để có bài toán giả tạo (M) như sau:
\begin{align}\label{3.9}
\min \{f(X) = \sum_{j=1}^nc_jx_j+M(\sum_{i=1}^m)x_{n+i}\}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
\sum\limits_{j=1}^na_{ij}x_j+x_{n+i}= b_i, i=1,2,..., m\\
x_j \geq0, j=1,2,...,n+m.
\end{array} \right.\notag
\end{align}
Lúc này bài toán (M) có ma trận $\overline{A}$ chứa ma trận đơn vị như đã nêu trong mục trước. Ta có thể chọn cơ sở đơn vị $\{A_{n+i}\}$ với các ẩn cơ sở $x_{n+i}$, $i = 1, 2, ..., m$, ta được phương án cực biên xuất phát
$$ X = (0, 0, ..., 0, b_1, b_2, ..., b_m) \in \mathbb{R}^{n+m}.$$

\textbf{Chú ý.} $a)$ Ta chỉ thêm ẩn giả tạo đối với những điều kiện ràng buộc không có \emph{ẩn đơn vị}. Vì vậy không nhất thiết phải có đủ $m$  ẩn giả tạo.

$b)$ Chúng ta cần phân biệt ẩn giả tạo và ẩn phụ:

+	Ẩn phụ $x_{n+i}$ nhằm mục đích đưa điều kiện dạng bất đẳng thức về dạng đẳng thức, với hệ số hàm mục tiêu $c_{n+i} = 0$ và ta thu được bài toán dạng chính tắc tương đương bài toán ban đầu.

+ Ẩn giả tạo $x_{n+i}$ nhằm mục đích tạo ra ma trận đơn vị cấp $m$, với hệ số hàm mục tiêu $c_{n+i} = M > 0$ lớn tuỳ ý và ta thu được bài toán giả tạo.
\vskip 0.2cm
Để minh họa, ta xét ví dụ sau đây.

\textbf{Ví dụ 8.} Cho bài toán quy hoạch tuyến tính
\begin{align*}
\max \{f = x_1+2x_2-x_3\}\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
-x_1 + 4x_2-2x_3\leq 6\\
x_1+x_2+2x_3\geq6\\
2x_1-x_2+2x_3=4\\
x_1, x_2, x_3\geq0.
\end{array} \right.
\end{align*}

Thay $\max\{ f(X)\}$ bởi $\min\{-f(X)\}$; đưa thêm ẩn phụ $x_4, x_5 \geq 0$, ta có bài toán tương đương (dạng chính tắc) như sau
\begin{align*}
\min \{-f = -x_1-2x_2+x_3\}\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
-x_1 + 4x_2-2x_3+x_4= 6\\
x_1+x_2+2x_3-x_5=6\\
2x_1-x_2+2x_3=4\\
x_1, x_2, x_3, x_4, x_5\geq0.
\end{array} \right.
\end{align*}

Ta chỉ mới có $A_4$ là vectơ đơn vị (tương ứng, $x_4$ là ẩn đơn vị). Ta đưa thêm hai ẩn giả tạo $x_6, x_7 \geq 0$ để được bài toán giả tạo (M) như sau:
\begin{align*}
\min \{-f = -x_1-2x_2+x_3+Mx_6+Mx_7\}\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
-x_1 + 4x_2-2x_3+x_4= 6\\
x_1+x_2+2x_3-x_5+x_6=6\\
2x_1-x_2+2x_3+x_7=4\\
x_1, x_2, x_3, x_4, x_5, x_6, x_7\geq0.
\end{array} \right.
\end{align*}

Chọn cơ sở liên kết đơn vị $A_4A_6A_7$, ta có phương án cực biên xuất phát
 $$\overline{X} = (0, 0, 0, 6, 0, 6, 4).$$

 Xuất phát từ $\overline{X}$, ta có thể giải bài toán giả tạo (M) bằng phương pháp đơn hình có cơ sở đơn vị. Vấn đề đặt ra là giữa bài toán đã cho và bài toán giả tạo (M) có mối quan hệ như thế nào? Định lý sau đây sẽ cho ta câu trả lời.

 \textbf{Định lý.} (về mối liên hệ giữa bài toán giả tạo và bài toán gốc) \emph{Tồn tại số thực $M_0 > 0$ đủ lớn sao cho với mọi  $M > M_0$ thì}

$a)$ \emph{Bài toán ban đầu có phương án tối ưu $X$ khi và chỉ khi bài toán giả tạo (M) có phương án tối ưu $\overline{X}  = (X, \theta)$}.

$b)$ \emph{Nếu bài toán giả tạo (M)  có phương án tối ưu nhưng chứa ẩn giả tạo $x_{n+i} > 0$ thì tập phương án của bài toán ban đầu là rỗng.}

Ở đâ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$.
\vskip 0.2cm
\noindent\textbf{3.2.3.2 Sử dụng thuật toán đơn hình khi bài toán quy hoạch tuyến tính chưa có cơ sở đơn vị}
\vskip 0.2cm
\textbf{Bước 1.} Chuyển về bài toán giả tạo.
\vskip 0.1cm
\textbf{Bước 2.} Giải bài toán giả tạo bằng phương pháp đơn hình với một số điều chỉnh như sau:
\vskip 0.1cm
+ Trong bài toán giả tạo (M), các phần tử hàng $f(X)$ và $\triangle_j$ có dạng $\alpha_j + \beta_j M$. Vì vậy ta tách hàng này làm hai hàng ghi $\alpha_j$ và $\beta_j$. Để đánh giá $\triangle_j$ (bao gồm xét dấu và so sánh), trước hết ta xét tới $\beta_j$, sau đó nếu cần thiết mới xét đến $\alpha_j$.
\vskip 0.1cm
+ Khi ẩn giả tạo $x_{n+i} = 0$ với mọi $i$, tức là $A_{n+i}$ không tham gia trong cơ sở nữa thì ta được phương án cực biên của bài toán ban đầu. Do đó, khi $A_{n+i}$ ứng với ẩn giả tạo $x_{n+i}$ được đưa ra khỏi cơ sở thì ta không cần tính cột $A_{n+i}$ ở các bảng tiếp theo.
+ Khi tất cả các ẩn giả tạo đều được đưa khỏi cơ sở thì hàng $f(X)$ và $\triangle_j$ chỉ cần ghi $\beta_j$.
\vskip 0.2cm
\noindent\textbf{3.2.3.3 Các ví dụ áp dụng}
\vskip 0.2cm
\textbf{Ví dụ 9.} Ta giải bài toán quy hoạch tuyến tính cho bởi Ví dụ 8, với cơ sở xuất phát $A_4A_6A_7$ và phương án cực biên
$$\overline{X} = (0, 0, 0, 6, 0, 6, 4).$$
Kết quả thu được bảng đơn hình sau.
\vskip 0.1cm
\begin{center}
\begin{tabular}{ | p{1cm}| p{1cm}  | p{1cm} | p{1cm}  |p{1cm} | p{1cm}  | p{1cm} | p{1.2cm}  | p{1cm} | p{0.7cm}  | p{0.7cm}  |}
    \hline
Bảng & Cơ sở & Hệ số & Tọa độ & $-1$ & $-2$ & $1$ & $0$ & $0$ & $M$ & $M$\\ \hline
 &  &  &  & $A_1$ & $A_2$ & $A_3$ & $A_4$ & $A_5$ & $A_6$ & $A_7$\\ \hline\hline
I & $A_4$ & $0$ & $6$ & $-1$ & $4$ & $-2$ & $1$ & $0$ & $0$ & $0$\\ \hline
& $A_6$ & $M$ & $6$ & $1$ & $1$ & $2$ & $0$ & $-1$ & $1$ &$0$\\ \hline
& $A_7$ & $M$ & $4$ & $2$ & $-1$ & $2$ & $0$ & $0$ & $0$ &$1$\\ \hline
& & $\alpha_j$ & $0$ & $1$ & $2$ & $-1$ & $0$ & $0$ & $0$ & $0$\\ \hline
& & $\beta_j$ & $10$ & $3$ & $0$ & $4$ & $0$ & $-1$ & $0$ & $0$\\ \hline\hline
II & $A_4$ & $0$ & $10$ & $1$ & $3$ & $0$ & $1$ & $0$ & $0$ &\\ \hline
& $A_6$ & $M$ & $2$ & $-1$ & $2$ & $0$ & $0$ & $-1$ & $1$ &\\ \hline
& $A_3$ & $1$ & $2$ & $1$ & $-1/2$ & $1$ & $0$ & $0$ & $0$ &\\ \hline
& & $\alpha_j$ & $2$ & $2$ & $3/2$ & $0$ & $0$ & $0$ & $0$ &\\ \hline
& & $\beta_j$ & $2$ & $-1$ & $2$ & $0$ & $0$ & $-1$ & $0$ &\\ \hline\hline
III & $A_4$ & $0$ & $7$ & $5/2$ & $0$ & $0$ & $1$ & $3/2$ &  & \\ \hline
& $A_2$ & $-2$ & $1$ & $-1/2$ & $1$ & $0$ & $0$ & $-1/2$ &  &\\ \hline
& $A_3$ & $1$ & $5/2$ & $3/4$ & $0$ & $1$ & $0$ & $-1/4$ &  &\\ \hline
& & $\alpha_j$ & $1/2$ & $11/4$ & $0$ & $0$ & $0$ & $3/4$ & &\\ \hline\hline
IV & $A_1$ & $-1$ & $14/5$ & $1$ & $0$ & $0$ & $2/5$ & $3/5$ & & \\ \hline
& $A_2$ & $-2$ & $12/5$ & $0$ & $1$ & $0$ & $1/5$ & $-1/5$ & &\\ \hline
& $A_3$ & $1$ & $2/5$ & $0$ & $0$ & $1$ & $-3/10$ & $-7/10$ & &\\ \hline
& & $\alpha_j$ & $-36/5$ & $0$ & $0$ & $0$ & $-11/10$ & $-9/10$ & &\\ \hline
    \end{tabular}
    \end{center}
  \vskip 0.1cm
Tại bảng IV ta có $\triangle_j \leq 0$ với mọi $j  = 1, 2, ..., 5$. Từ đó, phương án tối ưu là
$$X^* = (14/5, 12/5, 2/5, 0, 0),\;\text{với}\; f_{\max} = 36/5.$$
\vskip 0.2cm
Một thuật toán có ý nghĩa nếu sau hữu hạn bước lặp cho ta kết quả cần thiết.

Nếu bài toán quy hoạch tuyến tính không suy biến thì thuật toán đơn hình kết thúc sau hữu hạn bước lặp.

Trong trường hợp suy biến, thuật toán có thể không hữu hạn. Ví dụ đầu tiên được nêu ra là vào năm $1953$ của Giáo sư Hoffman. Sau đó, năm $1967$, GS. TS. Trần Vũ Thiệu (Viện Toán học) cũng đã đưa ra ví dụ chứng tỏ thuật toán không hữu hạn.

\textbf{Ví dụ 10.} (Ví dụ của GS. TS. Trần Vũ Thiệu) Xét bài toán quy hoạch tuyến tính
\begin{align*}
\min \{f = 4x_1-6x_5-5x_6+64x_7\}\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
x_1 + (1/3)x_4-2x_5-x_6+12x_7=0\\
x_2+(1/2)x_4-x_5-(1/6)x_6+(2/3)x_7=0\\
x_3+x_5+x_6-9x_7=2\\
x_1, x_2, x_3, x_4, x_5, x_6, x_7\geq0.
\end{array} \right.
\end{align*}

Chọn cơ sở $A_1A_2A_3$ ta có phương án cực biên xuất phát
$$X_0=(0, 0, 2, 0, 0, 0, 0).$$
Thực hiện thuật toán đơn hình, ta có bảng sau
\vskip 0.1cm
\begin{center}
\begin{tabular}{ | p{1cm}| p{1cm}  | p{0.7cm} | p{0.7cm}  |p{0.8cm} | p{0.8cm}  | p{0.8cm} | p{0.8cm}  | p{0.8cm} | p{0.8cm}  | p{1cm}  |}
    \hline
Bảng & Cơ sở & Hệ số & Tọa độ & $4$ & $0$ & $0$ & $0$ & $-6$ & $-5$ & $64$\\ \hline
 &  &  &  & $A_1$ & $A_2$ & $A_3$ & $A_4$ & $A_5$ & $A_6$ & $A_7$\\ \hline\hline
I & $A_1$ & $4$ & $0$ & $1$ & $0$ & $0$ & $1/3$ & $-2$ & $-1$ & $12$\\ \hline
& $A_2$ & $0$ & $0$ & $0$ & $1$ & $0$ & $1/2$ & $-1$ & $-1/6$ & $2/3$\\ \hline
& $A_3$ & $0$ & $2$ & $0$ & $0$ & $1$ & $0$ & $1$ & $1$ &$-9$\\ \hline
& &  & $0$ & $0$ & $0$ & $0$ & $4/3$ & $-2$ & $1$ & $-16$\\ \hline\hline
II & $A_4$ & $0$ & $0$ & $3$ & $0$ & $0$ & $1$ & $-6$ & $-3$ & $36$\\ \hline
& $A_2$ & $0$ & $0$ & $-3/2$ & $1$ & $0$ & $0$ & $2$ & $4/3$ & $-52/3$\\ \hline
& $A_3$ & $0$ & $2$ & $0$ & $0$ & $1$ & $0$ & $1$ & $1$ & $-9$\\ \hline
& &  & $0$ & $1/2$ & $-3$ & $0$ & $0$ & $0$ & $1$ & $-12$\\ \hline\hline
III & $A_4$ & $0$ & $0$ & $-3/2$ & $3$ & $0$ & $1$ & $0$ & $1$ & $-16$ \\ \hline
& $A_5$ & $-6$ & $0$ & $-3/4$ & $1/2$ & $0$ & $0$ & $1$ & $2/3$ & $-26/3$\\ \hline
& $A_3$ & $0$ & $2$ & $3/4$ & $-1/2$ & $1$ & $0$ & $0$ & $1/3$ & $-1/3$\\ \hline
& & & $0$ & $1/2$ & $-3$ & $0$ & $0$ & $0$ & $1$ & $-12$\\ \hline\hline
IV & $A_6$ & $-5$ & $0$ & $-3/2$ & $3$ & $0$ & $1$ & $0$ & $1$ & $-16$\\ \hline
& $A_2$ & $-6$ & $0$ & $1/4$ & $-3/2$ & $0$ & $-2/3$ & $1$ & $0$ & $2$\\ \hline
& $A_3$ & $0$ & $2$ & $5/4$ & $-3/2$ & $1$ & $-1/3$ & $0$ & $0$ & $5$\\ \hline
& & & $0$ & $2$ & $-6$ & $0$ & $-1$ & $0$ & $0$ & $4$\\ \hline\hline
V & $A_6$ & $-5$ & $0$ & $1/2$ & $-9$ & $0$ & $-13/3$ & $8$ & $1$ & $0$\\ \hline
& $A_7$ & $64$ & $0$ & $1/8$ & $-3/4$ & $0$ & $-1/3$ & $1/2$ & $0$ & $1$\\ \hline
& $A_3$ & $0$ & $2$ & $5/8$ & $9/4$ & $1$ & $4/3$ & $-5/2$ & $0$ & $0$\\ \hline
& & & $0$ & $3/2$ & $-3$ & $0$ & $1/3$ & $-2$ & $0$ & $0$\\ \hline\hline
VI & $A_1$ & $4$ & $0$ & $1$ & $-18$ & $0$ & $-26/3$ & $16$ & $2$ & $0$\\ \hline
& $A_7$ & $64$ & $0$ & $0$ & $3/2$ & $0$ & $3/4$ & $-3/2$ & $-1/4$ & $1$\\ \hline
& $A_3$ & $0$ & $2$ & $0$ & $27/2$ & $1$ & $27/4$ & $-25/2$ & $-5/4$ & $0$\\ \hline
& & & $0$ & $0$ & $24$ & $0$ & $40/3$ & $-26$ & $-3$ & $0$\\ \hline\hline
VII & $A_1$ & $4$ & $0$ & $1$ & $0$ & $0$ & $1/3$ & $-2$ & $-1$ & $12$\\ \hline
& $A_2$ & $0$ & $0$ & $0$ & $1$ & $0$ & $1/2$ & $-1$ & $-1/6$ & $2/3$\\ \hline
& $A_3$ & $0$ & $2$ & $0$ & $0$ & $1$ & $0$ & $1$ & $1$ &$-9$\\ \hline
& &  & $0$ & $0$ & $0$ & $0$ & $4/3$ & $-2$ & $1$ & $-16$\\ \hline
    \end{tabular}
    \end{center}
  \vskip 0.1cm
Bảng thứ VII trùng với bảng đầu tiên. Do đó thuật toán đơn hình không hữu hạn.

Nguyên nhân của hiện tượng thuật toán đơn hình không hữu hạn như trên chính là nếu bài toán suy biến thì quá trình vòng lặp có thể xảy ra
$$\min\limits_{a_{ik}>0}\frac{x_i}{a_{ik}}=0.$$
Điều này dẫn tới dù ta có thay đổi phương án cực biên thì giá trị hàm mục tiêu vẫn không giảm. Vì số phương án cực biên là hữu hạn nên đến một lúc nào đó, vòng lặp quay trở về phương án cực biên đã xét.

Bạn đọc có thể tự kiểm tra tính không hữu hạn của thuật toán đơn hình thông qua ví dụ sau.

\textbf{Ví dụ 11.} Xét bài toán quy hoạch tuyến tính sau
\begin{align*}
\min \{f = -10x_1+57x_2+9x_3+24x_4\}\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
-(1/2)x_1 - (11/2)x_2-(5/2)x_3+9x_4+x_5=0\\
(1/2)x_1-x_2-(1/2)x_3+x_4+x_6=0\\
x_1+x_7=1\\
x_1, x_2, x_3, x_4, x_5, x_6, x_7\geq0.
\end{array} \right.
\end{align*}

Các cơ sở liên kết lần lượt cho các bảng sẽ là $A_5A_6A_7$, $A_1A_6A_7$, $A_1A_2A_7$, $A_3A_2A_7$, $A_3A_4A_7$,
$A_5A_4A_7$, $A_5A_6A_7$. Như vậy, bảng thứ VII quay trở về bảng xuất phát (bảng I).

\section{Mô hình bài toán vận tải}

\subsection{Giới thiệu mô hình bài toán vận tải}
Mô hình bài toán vận tải đã được đề cập ở mục 3.1.1.3. Ta nhắc lại như sau:
\vskip 0.2cm
\emph{Phát biểu bài toán:} Người ta cần tổ chức vận tải một loại hàng từ $n$ nơi phát đến $m$ nơi thu. Nơi phát thứ $j$ có số lượng hàng là $a_j$, nơi nhận thứ $i$ cần số lượng hàng là $b_i$. Cước phí vận tải một đơn vị hàng từ nơi phát $j$ tới nơi nhận $i$ là $c_{ij}$. Ta nên tổ chức vận tải như thế nào để bảo đảm phát hết và nhận đủ số hàng, mà có tổng cước phí bé nhất.
\vskip 0.2cm
\noindent\emph{Thiết lập mô hình toán:} Gọi $x_{ij}$ là số lượng hàng vận tải từ $j$ tới $i$ ($x_{ij}\geq0$). Khi đó, ta thu được bài toán quy hoạch tuyến tính dạng chính tắc sau
$$\min\{f(X)=\sum_{j=1}^n\sum_{i=1}^mc_{ij}x_{ij}\}$$
$$\text{với điều kiện} \left\{ \begin{array}{ll}
\:\sum\limits_{j=1}^nx_{ij}=b_i, i=1,2,...,m,\\
 \:\sum\limits_{i=1}^mx_{ij}=a_j, j=1,2,...,n,\\
x_{ij}\geq0, i=1,2,...,m, j=1,2,...,n.
\end{array} \right.$$

Ở đây, $c_{ij}\geq0$, $a_j, b_i\geq0$.
\vskip 0.2cm
\subsection{Một số tính chất cơ bản của bài toán vận tải}
\noindent\par\textbf{Tính chất 1.} \emph{Bài toán vận tải có phương án tối ưu khi và chỉ khi bài toán có cân bằng thu - phát, nghĩa là}
$$\sum_{j=1}^na_j=\sum_{i=1}^mb_i.$$
\vskip 0.2cm
\textbf{Chú ý.} Trong trường hợp bài toán chưa cân bằng thu - phát thì ta lập các trạm giả như sau:

+  Nếu $\sum\limits_{j=1}^na_j>\sum\limits_{i=1}^mb_i$ (phát nhiều hơn thu) thì ta lập nơi thu giả (tồn kho) thứ $m +1$, với lượng thu vào là
$$b_{m +1} = \sum\limits_{j=1}^na_j-\sum\limits_{i=1}^mb_i,\; \text{với cước phí}\; c_{m+1, j} = 0.$$

+ Nếu $\sum\limits_{j=1}^na_j<\sum\limits_{i=1}^mb_i$ (phát ít hơn thu) thì ta lập nơi phát giả (ghi nợ) thứ $n +1$, với lượng phát ra là
$$a_{n +1} = \sum\limits_{i=1}^mb_i-\sum\limits_{j=1}^na_j,\; \text{với cước phí}\; c_{i, n+1} = 0.$$

Như vậy ta có thể thấy rằng bao giờ ta cũng tạo ra được điều kiện cân bằng thu - phát.
\vskip 0.2cm
\textbf{Tính chất 2.} \emph{Ma trận $A = (A_{ij}) = (a_{ij})$ có hạng bằng $m + n - 1$.}
\vskip 0.2cm
Từ đây ta thu được hệ quả quan trọng về phương án cực biên của bài toán vận tải thể hiện ở tính chất sau đây:
\vskip 0.2cm
\textbf{Tính chất 3.} \emph{Số tọa độ dương của của phương án cực biên bài toán vận tải có không quá $m+n-1$.}
\vskip 0.2cm
Kể từ đây trở về sau, ta giả thiết rằng \emph{bài toán vận tải không suy biến}, tức là mọi phương án cực biên có đủ $m + n - 1$ tọa độ dương.

Để thuận tiện theo dõi, ta biểu diễn bài toán vận tải dưới dạng bảng sau
\vskip 0.1cm
\begin{center}
\begin{tabular}{ | p{4cm}  | p{1.7cm} | p{1cm}  |p{1.7cm} | p{1cm}  | p{1.7cm} |}
    \hline
Thu $\setminus$ Phát & $a_1$ & ... & $a_j$ & ... & $a_n$ \\ \hline
$b_1$ & $x_{11}/c_{11}$ & ... & $x_{1j}/c_{1j}$ & ... & $x_{1n}/c_{1n}$ \\ \hline
... & ... & ... & ... & ... & ... \\ \hline
$b_i$ & $x_{i1}/c_{i1}$ & ... & $x_{ij}/c_{ij}$ & ... & $x_{in}/c_{in}$ \\ \hline
... & ... & ... & ... & ... & ... \\ \hline
$b_m$ & $x_{m1}/c_{m1}$ & ... & $x_{mj}/c_{mj}$ & ... & $x_{mn}/c_{mn}$ \\ \hline
    \end{tabular}
    \end{center}
  \vskip 0.1cm
  Nghiên cứu tiếp các tính chất của bài toán vận tải, chúng ta cần định nghĩa sau.

\textbf{Định nghĩa.} Ô $(i, j)$ có $x_{ij} > 0$ gọi là \emph{ô chọn}. Các ô không thuộc ô chọn được gọi là \emph{ô loại}.

Như vậy, \emph{một phương án cực biên không suy biến có $m + n - 1$ ô chọn}.


Một dãy ô liên tiếp sao cho \emph{\textbf{hai ô viết liền nhau cùng hàng hoặc cùng cột}}, \emph{\textbf{không có ba ô nào viết liền nhau cùng hàng hoặc cùng cột}}, gọi là một \emph{dây chuyền}. Một dây chuyền khép kín gọi là \emph{một vòng}. Như vậy một vòng V được ký hiệu là
$V = \{(i_1, j_1), (i_1, j_2), (i_2, j_2), ..., (i_k, j_1)\}.$
\vskip 0.2cm
\textbf{Tính chất 4.} \emph{Phương án $X = (x_{ij})$ của bài toán vận tải là cực biên khi và chỉ khi các ô chọn không lập thành vòng.}
\vskip 0.2cm
\textbf{Tính chất 5.} \emph{Cho phương án cực biên $X$ với tập hợp $H$ gồm  $m+n-1$ ô chọn không lập thành vòng, $(l,k)\notin H$. Khi đó tập hợp $H_1 = H\cup\{(l, k)\}$ lập nên một vòng $V$ duy nhất. Đồng thời nếu $(p, q) \in V$ thì $H_2 = H_1\setminus\{(p, q)\}$ gồm đúng $m+n-1$ ô không có vòng.}
\vskip 0.2cm
Tiếp theo, ta lập được bài toán đối ngẫu của bài toán vận tải là
\begin{align*}
\max \{g = \sum_{i=1}^mb_iu_i+\sum_{j=1}^na_jv_j\}\;\;\;\;\;\;\;\;\;\;\;\;\;\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
u_i+v_j\leq c_{ij}, i=1, 2, ..., m; j=1, 2, ..., n,
\end{array} \right.
\end{align*}
trong đó ẩn $u_i$ đối ngẫu với hàng thứ $i$, ẩn $v_j$ đối ngẫu với hàng $j+m$.

Ký hiệu
$$\triangle_{ij}=u_i+v_j-c_{ij}.$$
\vskip 0.2cm
\textbf{Tính chất 6}. (Dấu hiệu tối ưu) \emph{Nếu tại phương án cực biên $X_0$ tồn tại các số $u_i, v_j$  sao cho $\bigtriangleup_{ij} = 0$ tại các ô chọn và $\bigtriangleup_{ij} \leq 0$ với mọi $i, j$, thì $X_0$ là phương án tối ưu.}
\vskip 0.1cm
\emph{Chứng minh.} Theo định lý lệch bù, ta có phương án $X_0$ tối ưu khi và chỉ khi tồn tại $Y = (u_i, v_j)$, $i = 1,..., m$; $j = 1,..., n$ thoả mãn
$$u_i + v_j \leq c_{ij},\;\text{với mọi}\;(i, j)$$
$$\text{và}\; u_i + v_j = c_{ij},\;\text{với}\;(i, j)\; \text{mà}\; x_{ij} > 0.$$

Điều đó có nghĩa là $X_0$ tối ưu khi và chỉ khi $\triangle_{ij} \leq 0$, với mọi $(i, j)$ và $\triangle_{ij} = 0$ tại ô chọn.

Tính chất được chứng minh.
\vskip 0.2cm
\textbf{Chú ý.} Để tìm $u_i, v_j$, ta cần giải hệ phương trình
$$\{ u_i + v_j = c_{ij},\;\text{ với}\; (i, j) \in H.$$

Hệ này có $m+n$ ẩn và $m+n-1$ phương trình độc lập nên hệ có vô số nghiệm phụ thuộc một tham số. Ta chỉ cần một nghiệm của hệ. Đơn giản nhất là cho giá trị của một ẩn số bằng 0 (thông thường ẩn nào tham gia nhiều trong các phương trình của hệ). Từ đó ta suy trực tiếp ra các ẩn khác.

Để minh họa, ta xét ví dụ sau.

\textbf{Ví dụ 12.} Với $n = 4, m = 3$ và cho phương án cực biên với các ô chọn như trong bảng sau.
\vskip 0.1cm
\begin{center}
\begin{tabular}{ | p{3cm}  | p{3cm} | p{3cm}  |p{3cm} | p{3cm}  |}
    \hline
 $x_{11}=3/c_{11}=5$ & $x_{12}=5/c_{12}=10$ &  &  \\ \hline
&  & $x_{23}=4/c_{23}=5$ & $x_{24}=3/c_{24}=1$ \\ \hline
 $x_{31}=5/c_{31}=2$ &  &  & $x_{34}=4/c_{34}=2$ \\ \hline
    \end{tabular}
    \end{center}
  \vskip 0.1cm
 Ta cần giải hệ phương trình
 $$\left\{ \begin{array}{ll}
u_1+v_1=5,\\
u_1+v_2=10,\\
u_2+v_3=5,\\
u_2+v_4=1,\\
u_3+v_1=2,\\
u_3+v_4=2.
\end{array} \right.$$
Đặt $u_1 = 0$, thì $v_1 = 5$, $v_2 = 10$, từ đó $u_3 = - 3$, $v_4 = 5$, $u_2 = - 4$, $v_3 = 9$.

\vskip 0.2cm
\textbf{Tính chất 7.} \emph{Nếu tại phương án cực biên $X_0$, tồn tại $\bigtriangleup_{lk} > 0$ thì ta xây dựng được phương án cực biên mới $X_1$ tốt hơn $X_0$.}
\vskip 0.1cm
\emph{Chứng minh.} Giả sử $H$ là tập hợp $m+n-1$ ô chọn của $X_0$. Rõ ràng $(l, k) \notin H$. Theo Tính chất 5 thì $$H_1 = H \cup \{(l, k)\}$$
có một vòng $V$ duy nhất. Ta đánh số thứ tự các ô trên $V$ kể từ ô $(l, k)$ là số $1$, khi đó $V$ gồm các ô mang số thứ tự lẻ, ký hiệu là $V^L$, và các ô mang số thứ tự chẵn, ký hiệu là $V^C$.

Chọn
$$x_{pq}=\min_{(i, j)\in V^C}x_{ij}>0.$$

Đưa ô $(l, k)$ vào làm ô chọn của $X_1$ và ô $(p, q)$ ra khỏi ô chọn.

Bằng phép biến đổi
$$x_{ij}'= \left\{ \begin{array}{ll}
x_{ij}\;\;\;\;\;\;\text{nếu}\;(i, j)\notin V,\\
x_{ij}-x_{pq}\;\;\text{nếu}\;(i, j)\in V^C,\\
x_{ij}+x_{pq}\;\;\text{nếu}\;(i, j)\in V^L.
\end{array} \right.$$

Dễ dàng kiểm tra lại $X_1 = (x_{ij}')$ là phương án. Hơn thế nữa, theo Tính chất 5 thì $H_2 = H_1\ \{(p, q)\}$ gồm $m+n-1$ ô không lập thành vòng, tức là $X_1$ là phương án cực biên.

Đồng thời lúc này
$$f(X_1) = f(X_0) - x_{pq}\triangle_{lk}.$$

Vì $x_{pq}>0$ và $\triangle_{lk}>0$ nên $f(X_1) < f(X_0)$.

\subsection{Thuật toán phân phối giải bài toán vận tải}
\textbf{3.3.3.1 Thuật toán tìm phương án cực biên xuất phát}

Xem tài liệu [1].
\vskip 0.2cm
\noindent\textbf{3.3.3.2 Thuật toán phân phối giải bài toán vận tải}

Xem tài liệu [1].

\section*{Bài tập chương}

\begin{prob} {\rm
Hãy cho biết làm thế nào để kiểm tra một phương án của bài toán quy hoạch tuyến tính là phương án cực biên?
}
\end{prob}


\begin{prob} {\rm
Hãy cho biết làm thế nào để kiểm tra một phương án của bài toán quy hoạch tuyến tính là phương án tối ưu?
}
\end{prob}


\begin{prob} {\rm

Một người du lịch mang theo chiếc túi đựng hàng với trọng lượng $L$. Có thể chọn xếp $n$ loại hàng vào túi. Hàng loại $j$ có số lượng là $a_j$ và một đơn vị hàng loại $j$ có trọng lượng $d_j$ với giá trị là $c_j$. Hỏi nên xếp hàng vào túi như thế nào để có tổng giá trị lớn nhất? (Hãy lập bài toán và thử giải bằng kinh nghiệm thực tế).

}
\end{prob}

\begin{prob} {\rm
Thiết lập mô hình bài toán quy hoạch tuyến tính cho bài toán sau (Bài toán phân phối vốn): ``Một cơ sở kinh doanh có $m$ loại nguồn vốn khác nhau, có thể đầu tư vốn vào $n$ ngành sản xuất. Vốn từ nguồn loại $i$ có là $b_i$ (đơn vị vốn) và vốn cần có cho ngành sản xuất thứ $j$ là $a_j$ (đơn vị vốn). Lãi thu được từ $1$ đơn vị vốn nguồn $i$ đầu tư cho ngành sản xuất $j$ là $c_{ij}$. Hãy lập bài toán phân phối vốn sao cho có tổng số lãi lớn nhất, mà đảm bảo sử dụng hết và đủ vốn cho mỗi nguốn vốn, mỗi ngành sản xuất''.

}
\end{prob}


\begin{prob} {\rm
Hãy lập bài toán quy hoạch tuyến tính từ bài toán cho sau đây:

Một xí nghiệp có thể sản xuất $3$ loại sản phẩm A, B, C, từ 3 loại nguyên liệu I, II, III. Một đơn vị sản phẩm mỗi loại sử dụng nguyên liệu và tiền lãi cho trong bảng sau:
\vskip 0.1cm
\begin{tabular}{ | p{6cm}  | p{1cm} | p{1cm}  |p{1cm} | p{1cm}  |}
    \hline
Sản phẩm $\setminus$ Nguyên liệu & I & II & III & Lãi\\ \hline
A & 3 & 1 & 6 & 2  \\ \hline
B & 7 & 3 & 3 & 5  \\ \hline
C & 5 & 2 & 4 & 6  \\ \hline
    \end{tabular}
  \vskip 0.1cm
Hỏi nên sản xuất bao nhiêu sản phẩm mỗi loại để có tổng số tiền lãi lớn nhất mà phù hợp với khả năng cung cấp nguyên liệu. Biết rằng khả năng cung cấp nguyên liệu tối đa từng loại lần lượt $18, 12, 20$.

}
\end{prob}

\begin{prob} {\rm
Đưa bài toán quy hoạch tuyến tính sau đây về dạng chính tắc
\begin{align*}
\max \{f = 2x_1 - x_2\}\;\;\;\;\;\;\;\;\;\;\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
-x_1 - 2 x_2+x_3\leq 2\\
2x_1-x_2-x_3 \geq 3\\
x_1+x_2+x_3 = 4\\
x_1, x_2, x_3 \geq0.
\end{array} \right.
\end{align*}


}
\end{prob}

\begin{prob} {\rm
Cho bài toán quy hoạch tuyến tính:
\begin{align*}
\max \{f = 2x_1 - x_2+x_3\}\;\;\;\;\;\;\;\;\;\;\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
2x_1 +  x_2-x_3\leq 5\\
-x_1+2x_2+x_3 \leq 4\\
x_1-4x_2+x_3 \leq 6\\
x_1, x_2, x_3 \geq0.
\end{array} \right.
\end{align*}

$a)$ Hãy chứng tỏ bài toán có phương án tối ưu.

$b)$ Đưa bài toán đã cho về dạng chính tắc. Điểm $X = (0, 0, 0, 5, 4, 6)$ có phải là phương án cực biên không? Tại sao?

$c)$ Tìm phương án cực biên (nếu có) ứng với cơ sở liên kết $A_3A_4A_6$.

}
\end{prob}


\begin{prob} {\rm
Cho bài toán quy hoạch tuyến tính:
\begin{align*}
\min \{f = x_1 - x_2-\lambda x_3\}\;\;\;\;\;\;\;\;\;\;\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
3x_1 - 7  x_2+3x_3+x_4=2\\
-x_1+2x_2-x_3 = 1\\
2x_1+x_2+2x_3 = 6\\
x_1, x_2, x_3, x_4 \geq0.
\end{array} \right.
\end{align*}

$a)$ Điểm $X = (0, 8/5, 11/5, 33/5)$ có phải là cực biên không?

$b)$ Tìm phương án cực biên (nếu có) ứng với cơ sở liên kết $A_1A_2A_4$.

$c)$ Viết bài toán đối ngẫu của bài toán đã cho. Phương án cực biên tìm được ở câu $b)$, tại $\lambda = 1$, có tối ưu không? Tại sao?

$d)$ Tìm các giá trị của $\lambda$ để phương án cực biên tìm được ở câu $b$) là tối ưu. Với một giá trị xác định của $\lambda$ vừa tìm được, hãy tìm phương án tối ưu của bài toán đối ngẫu.

}
\end{prob}

\begin{prob} {\rm
Cho bài toán quy hoạch tuyến tính:
\begin{align*}
\max \{f = x_1 - x_2 + 2 x_3\}\;\;\;\;\;\;\;\;\;\;\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
2x_1 + 2  x_2-x_3\leq 11\\
x_1+2x_2+x_3 \leq 16\\
-x_1-2x_2+2x_3 \leq 8\\
x_1, x_2, x_3 \geq0.
\end{array} \right.
\end{align*}

$a)$ Đưa bài toán về dạng chính tắc.

$b)$ Giải bài toán đã cho bằng phương pháp đơn hình.

$c)$ Viết bài toán đối ngẫu của bài toán đã cho. Tìm phương án tối ưu của bài toán đối ngẫu.

}
\end{prob}

\begin{prob} {\rm
Giải bài toán quy hoạch tuyến tính sau bằng phương pháp đơn hình:

\begin{align*}
\max \{f = 2x_1 + 4 x_2 + x_3+x_4\}\;\;\;\;\;\;\;\;\;\;\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
x_1 + 3  x_2+x_4\leq 4\\
2x_1+x_2 \leq 3\\
x_2+4x_3+x_4 \leq 3\\
x_1, x_2, x_3, x_4 \geq0.
\end{array} \right.
\end{align*}
}
\end{prob}

\begin{prob} {\rm
Giải bài toán quy hoạch tuyến tính sau bằng phương pháp đơn hình:

 \begin{align*}
\min \{f = x_1 -2 x_2 - x_3\}\;\;\;\;\;\;\;\;\;\;\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
x_1 +  x_2-2x_3\leq 2\\
x_1-x_2+x_3 \leq 1\\
x_2+x_3 \leq 5\\
2x_1-x_2 \leq 2\\
x_1, x_2, x_3 \geq0.
\end{array} \right.
\end{align*}
}
\end{prob}

\begin{prob} {\rm
Giải bài toán quy hoạch tuyến tính sau bằng phương pháp đơn hình:

 \begin{align*}
\min \{f = 2x_1 + x_2 - x_3-x_4\}\;\;\;\;\;\;\;\;\;\;\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
x_1 -  x_2+2x_3-x_4= 2\\
2x_1+x_2-3x_3+x_4 \leq 4\\
x_1+x_2+x_3+x_4 \leq 5\\
x_1, x_2, x_3, x_4 \geq0.
\end{array} \right.
\end{align*}

}
\end{prob}

\begin{prob} {\rm
Cho bài toán quy hoạch tuyến tính:
\begin{align*}
\max \{f = \lambda x_1 + x_2 + x_3\}\;\;\;\;\;\;\;\;\;\;\\
\text{với điều kiện:} \left\{ \begin{array}{ll}
x_1 - x_4-2x_6=2\\
x_2+x_4-3x_5+x_6 =4\\
x_3+2x_4-5x_5+6x_6 =\beta\\
x_1, x_2, x_3, x_4, x_5, x_6 \geq0.
\end{array} \right.
\end{align*}

$a)$ Giải bài toán đã cho bằng phương pháp đơn hình với $\lambda=1$, $\beta=6$.

$b)$ Từ phương án tối ưu tìm được ở câu $a)$, hãy xác định phương án tối ưu của bài toán đối ngẫu.

$c)$ Ký hiệu phương án tối ưu ở câu $a)$ là $X_0$, coi $\lambda$ là tham số, tìm tất cả các giá trị của $\lambda$ để $X_0$ tối ưu.

$d)$ Tại $\lambda$ vừa tìm được, coi $\beta$ là tham số, hãy tìm tất cả các giá trị của $\beta$ để có phương án tối ưu của bài toán đã cho.

}
\end{prob}




\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}
