Bối cảnh và vấn đề nghiên cứu

Trong lý thuyết tối ưu hóa toán học, bài toán tìm cực tiểu của một hàm lõm (hoặc cực đại của một hàm lồi) xác định trên một tập lồi đóng được gọi là bài toán quy hoạch lõm (Concave Programming Problem). Đây là một trong những bài toán nền tảng của lớp bài toán tối ưu toàn cục (Global Optimization). Sở dĩ quy hoạch lõm giữ vai trò trọng tâm là bởi tính chất phổ biến trong ứng dụng thực tế và việc nhiều bài toán tối ưu toàn cục phức tạp có thể quy về hoặc vận dụng các bước giải của bài toán này. Khác với quy hoạch lồi hay quy hoạch tuyến tính (nơi mọi cực tiểu địa phương đều là cực tiểu toàn cục), bài toán quy hoạch lõm tồn tại nhiều điểm cực trị địa phương, khiến việc tìm kiếm nghiệm tối ưu toàn cục trở nên phức tạp.

Trong thực tiễn kinh tế và quản lý sản xuất, các hàm mục tiêu phi tuyến dạng lõm hoặc tựa lõm xuất hiện thường xuyên do tác động của quy luật hiệu quả kinh tế theo quy mô (economies of scale): khi quy mô hoặc khối lượng sản xuất càng lớn thì chi phí sản xuất tính trên một đơn vị sản phẩm càng có xu hướng giảm dần. Một trường hợp điển hình khác là bài toán chi phí xây dựng và vận hành nhà máy có phụ phí cố định (fixed charge), được mô hình hóa bằng hàm tựa lõm:

$$f_j(x_j) = \begin{cases} c_j x_j + d_j & \text{khi } x_j > 0 \ 0 & \text{khi } x_j = 0 \end{cases}$$

Trong đó, $d_j > 0$ là vốn đầu tư ban đầu để xây dựng nhà máy thứ $j$, còn $c_j x_j$ là chi phí vận hành tương ứng với công suất $x_j$.

Mặc dù quy hoạch lõm với ràng buộc tuyến tính có ý nghĩa ứng dụng cao, các công trình chuyên khảo giải quyết hiệu quả lớp bài toán này khi kết hợp với cấu trúc phân bố sản xuất và vận tải quy mô lớn vẫn còn hạn chế. Đề tài luận văn thạc sĩ toán học "Thuật toán phân rã giải bài toán phân bố sản xuất với chi phí lõm" của học viên Phạm Tiến Đỗ, chuyên ngành Toán ứng dụng (Mã số: 60 46 01 12), dưới sự hướng dẫn khoa học của GS. Trần Vũ Thiệu tại Trường Đại học Khoa học – Đại học Thái Nguyên (bảo vệ tháng 12/2015), được thực hiện nhằm nghiên cứu có hệ thống lý thuyết quy hoạch lõm và xây dựng thuật toán phân rã chuyên biệt cho mô hình phân bố sản xuất kết hợp vận tải có hàm chi phí lõm.

Nhiệm vụ nghiên cứu được xác định cụ thể gồm 3 nội dung chính:

  1. Tổng hợp và hệ thống hóa lý thuyết về hàm lõm, hàm tựa lõm và bài toán cực tiểu hàm lõm trên tập lồi đa diện.
  2. Trình bày chi tiết thuật toán xấp xỉ ngoài (Outer Approximation Algorithm) áp dụng để giải bài toán quy hoạch lõm với hệ ràng buộc tuyến tính.
  3. Nghiên cứu mô hình bài toán phân bố sản xuất với chi phí lõm và xây dựng thuật toán phân rã giải mô hình này dựa trên việc kết hợp kỹ thuật xấp xỉ ngoài và phương pháp thế vị của quy hoạch tuyến tính.

Đối tượng và phạm vi nghiên cứu của luận văn tập trung vào không gian Euclidean $\mathbb{R}^n$, bài toán quy hoạch lõm với hệ ràng buộc tuyến tính tổng quát, và mô hình tối ưu hóa phân bố sản xuất từ $m$ nhà máy cung cấp hàng hóa cho $n$ hộ tiêu thụ trong điều kiện chi phí sản xuất là hàm lõm.

Cơ sở lý thuyết và phương pháp

Luận văn vận dụng khung lý thuyết giải tích lồi, hình học tập lồi đa diện và lý thuyết đối ngẫu trong tối ưu hóa toán học:

  • Lý thuyết tập lồi và đa diện lồi: Các khái niệm không gian afin, bao afin ($\text{aff } C$), bao lồi ($\text{conv } E$), nón lồi, siêu phẳng phân tách, diện (face), cạnh hữu hạn/vô hạn và điểm cực biên (extreme point hay đỉnh) của tập lồi. Đặc biệt là Định lý biểu diễn tập lồi đa diện bị chặn thông qua bao lồi của tập hữu hạn các đỉnh: $M = \text{conv } U$.
  • Lý thuyết hàm lồi, hàm lõm và hàm tựa lõm: Định nghĩa hàm lồi, lồi chặt, hàm lõm, hàm afin; các tập liên đới gồm miền hữu dụng ($\text{dom } f$), tập trên đồ thị ($\text{epi } f$), tập dưới đồ thị ($\text{hypo } f$) và tập mức trên/dưới ($D_\beta, D_{\bar{\beta}}$). Điều kiện tối ưu vi phân và nón pháp tuyến đối với hàm lồi/lõm: $0 \in \partial f(x^) - N_C(x^)$.
  • Nguyên lý cực trị quy hoạch lõm: Điểm cực tiểu toàn cục của một hàm lõm (hoặc tựa lõm) xác định trên một tập lồi compact đa diện luôn đạt được tại ít nhất một điểm cực biên (đỉnh) của tập ràng buộc đó.
  • Lý thuyết đối ngẫu quy hoạch tuyến tính: Dùng để biểu diễn hàm mục tiêu vận tải $g(x)$ thông qua tập các đỉnh cực biên của đa diện đối ngẫu $\ddot{M}$.

Phương pháp nghiên cứu chủ đạo bao gồm:

  • Phương pháp phân tích - tổng hợp toán học: Khảo cứu có hệ thống các kết quả lý thuyết từ các tài liệu kinh điển về giải tích lồi và quy hoạch lõm của Horst, Tuy (1996), Trần Vũ Thiệu (1985, 2004), Lê Dũng Mưu (1998, 2001).
  • Kỹ thuật sinh đỉnh (Vertex Generation Technique): Phương pháp giải tích hình học xác định tập đỉnh mới $V_{k+1}$ của đa diện lồi $S_{k+1}$ khi bổ sung một siêu phẳng cắt ràng buộc $A_{i_k} x + b_{i_k} \le 0$ vào đa diện $S_k$ đã biết trước tập đỉnh $V_k$.
  • Kỹ thuật phân rã toán học (Decomposition Technique): Tách bài toán ban đầu gồm $m$ biến sản xuất phi tuyến lõi $x_i$ và $m \times n$ biến vận tải tuyến tính $x_{ij}$ thành hai bài toán con: bài toán quy hoạch lõm kích thước nhỏ hơn ($m+1$ biến $(t, x)$) và bài toán vận tải tuyến tính cỡ $m \times n$.
  • Thực nghiệm tính toán và giải tích ví dụ số: Sử dụng các bài toán mẫu 2 biến, 5 biến và bài toán phân bố sản xuất 3 nhà máy để kiểm chứng các bước lặp của thuật toán.

Nội dung chính theo từng chương

Chương 1: Kiến thức chuẩn bị

Chương 1 hệ thống hóa các định nghĩa, định lý và công cụ toán học nền tảng phục vụ cho việc thiết lập các thuật toán ở các chương sau:

  • Trình bày chi tiết cấu trúc hình học của tập lồi trong $\mathbb{R}^n$, bao afin, nón lồi, diện của tập lồi, phân loại diện 0 chiều (điểm cực biên/đỉnh) và diện 1 chiều (cạnh hữu hạn hoặc vô hạn).
  • Trình bày định lý biểu diễn đa diện lồi $D$: một đa diện lồi compact luôn bằng bao lồi của tập hữu hạn các đỉnh của nó ($D = \text{conv } V$).
  • Phân tích chi tiết thuật toán xác định tập đỉnh mới khi bổ sung một ràng buộc tuyến tính mới $h_0(x) = A_0 x + b_0 \le 0$ vào đa diện lồi $M = {x \in \mathbb{R}^n : A_i x + b_i \le 0, i=1,\dots,m}$ đã biết trước tập đỉnh $U$. Tập đỉnh mới $V$ của đa diện $P = M \cap {x : h_0(x) \le 0}$ được phân tích qua 3 nhóm:
    • Các đỉnh cũ thỏa mãn chặt $h_0(u) \le 0$: $u \in U \setminus U^+$.
    • Đỉnh mới sinh ra là giao điểm $w = t u + (1-t) u'$ giữa siêu phẳng $h_0(x) = 0$ với đoạn thẳng nối đỉnh $u \in U^-$ ($h_0(u) < 0$) và $u' \in U^+$ ($h_0(u') > 0$), với điều kiện chiều của diện nhỏ nhất chứa $w$ thỏa mãn $\dim F(w) = 1$.
  • Định nghĩa hàm lồi, hàm lồi chặt, hàm lõm, hàm tựa lồi và tựa lõm; phân tích các tính chất liên hệ giữa tính lồi/lõm của hàm mục tiêu với tính lồi của các tập trên đồ thị ($\text{epi } f$) và tập dưới đồ thị ($\text{hypo } f$). Trình bày định lý điều kiện cần và đủ cực trị: nếu $f$ khả vi thì góc giữa $\nabla f(x^)$ và vector $(x - x^)$ là góc nhọn với mọi $x \in C$.

Chương 2: Quy hoạch lõm với ràng buộc tuyến tính

Chương 2 tập trung phân tích bài toán quy hoạch lõm tổng quát và xây dựng thuật toán xấp xỉ ngoài giải bài toán với hệ ràng buộc tuyến tính:

  • Phân tích sự khác biệt bản chất giữa cực trị hàm lồi và hàm lõm: Cực tiểu địa phương của hàm lõm không nhất thiết là cực tiểu toàn cục. Mọi điểm cực đại địa phương của hàm lồi trên tập lồi compact đạt tại điểm cực biên. Ngược lại, cực tiểu toàn cục của hàm lõm trên đa diện lồi compact $C$ luôn đạt được tại ít nhất một đỉnh của $C$.
  • Thiết lập mô hình bài toán quy hoạch lõm ràng buộc tuyến tính $(CP)$:

$$\min {f(x) : x \in D}, \quad D = {x \in \mathbb{R}^n : A_i x \le b_i, i=1,\dots,m}$$

  • Trình bày chi tiết thuật toán xấp xỉ ngoài (Outer Approximation):
    • Khởi tạo (Bước 1): Giải bài toán quy hoạch tuyến tính tìm $\beta = \max {\sum_{j=1}^n x_j : x \in D}$ để xây dựng đơn hình ban đầu $S_1 = {x \in \mathbb{R}^n : \sum_{j=1}^n x_j \le \beta, x_j \ge 0}$ bao chứa $D$ ($S_1 \supset D$) với tập đỉnh ban đầu $V_1 = {0, \beta e_1, \dots, \beta e_n}$.
    • Bước lặp $k$ (Bước 2 & 3): Tìm đỉnh $x^k \in V_k$ sao cho $f(x^k) = \min {f(v) : v \in V_k}$. Tính độ vi phạm ràng buộc lớn nhất $\gamma_k = \max {A_i x^k - b_i : i \notin J_k}$.
      • Nếu $\gamma_k \le 0$, thì $x^k \in D$, thuật toán dừng và $x^k$ là nghiệm tối ưu toàn cục.
      • Nếu $\gamma_k > 0$, chọn chỉ số ràng buộc vi phạm nhiều nhất $i_k = \text{argmax} {A_i x^k - b_i}$, thiết lập đa diện mới $S_{k+1} = S_k \cap {x : A_{i_k} x \le b_{i_k}}$ và cập nhật tập đỉnh $V_{k+1}$ từ $V_k$ thông qua kỹ thuật cắt siêu phẳng.
    • Thuật toán dừng sau tối đa $m$ vòng lặp bổ sung ràng buộc.
  • Trình bày các ví dụ số minh họa:
    • Bài toán quy hoạch phi tuyến lõm 2 biến: $f(x) = -3x_1^2 - 2x_2^2 \to \min$ trên miền đa diện gồm 4 bất phương trình tuyến tính và $x_1, x_2 \ge 0$. Khởi tạo đơn hình với $\beta = 10$, tập giá trị hàm mục tiêu tại các đỉnh ban đầu đạt $f \in {0, -300, -200}$.
    • Bài toán cực tiểu hàm lõm bậc hai 5 biến: $f(x) = -(x_1^2 + x_2^2 + x_3^2 + x_4^2 + x_5^2) + 2x_1 + 4x_2 + 8x_3 + 14x_4 + 18x_5$ với 4 ràng buộc tuyến tính trong đơn hình $S_1 = {x \in \mathbb{R}+^5 : \sum{j=1}^5 x_j \le 300}$.

Chương 3: Bài toán phân bố sản xuất với chi phí lõm

Chương 3 là phần đóng góp trọng tâm của luận văn, trình bày mô hình kinh tế toán và thuật toán phân rã:

  • Mô hình toán học của bài toán phân bố sản xuất $(P)$:

$$\min \sum_{i=1}^m f_i(x_i) + \sum_{i=1}^m \sum_{j=1}^n c_{ij} x_{ij}$$

Ràng buộc hệ thống:

$$\begin{cases} \sum_{j=1}^n x_{ij} = x_i, & i=1,\dots,m \ \sum_{i=1}^m x_{ij} = b_j, & j=1,\dots,n \ x_{ij} \ge 0, & i=1,\dots,m; j=1,\dots,n \ x \in X \end{cases}$$

Trong đó: $m$ là số nhà máy, $n$ là số hộ tiêu thụ; $x_i$ là lượng sản xuất tại nhà máy $i$; $x_{ij}$ là lượng hàng chuyển từ nhà máy $i$ tới hộ $j$; $b_j$ là nhu cầu hộ $j$; $c_{ij}$ là cước phí vận chuyển một đơn vị hàng; $f_i(x_i)$ là hàm chi phí sản xuất lõm.

  • Ý tưởng và cơ chế phân rã: Mô hình $(P)$ chứa $m$ biến phi tuyến lõm $x_i$ và $m \times n$ biến tuyến tính $x_{ij}$. Bằng cách cố định vector sản xuất $x$, bài toán trở thành bài toán vận tải thông thường. Sử dụng lý thuyết đối ngẫu, tổng chi phí vận tải tối ưu được biểu diễn thành:

$$g(x) = \max \left{ \sum_{i=1}^m x_i u_i + \sum_{j=1}^n b_j v_j : (u, v) \in \ddot{M} \right}$$

Với $\ddot{M}$ là tập hữu hạn các đỉnh cực biên của đa diện đối ngẫu $M = {(u, v) \in \mathbb{R}^{m+n} : u_i + v_j \le c_{ij}}$. Đưa thêm biến phụ $t \ge t_0$ đại diện cho cận dưới chi phí vận tải, bài toán $(P)$ tương đương với bài toán quy hoạch lõm $(CP)$ trong không gian $\mathbb{R}^{m+1}$:

$$\min_{(t, x)} \sum_{i=1}^m f_i(x_i) + t \quad \text{với } -t + \sum_{i=1}^m u_i x_i + \sum_{j=1}^n v_j b_j \le 0, \quad \forall (u, v) \in \ddot{M}$$

  • Chi tiết thuật toán phân rã:
    • Khởi tạo: Giải bài toán quy hoạch lõm ban đầu $(Q_1): \min {\sum_{i=1}^m f_i(x_i) + t : x \in X, t \ge t_0}$ để tìm phương án sản xuất ban đầu $(t^1, x^1)$.
    • Bước lặp $k$:
      1. Giải bài toán vận tải $(T_k)$ ứng với vector sản xuất $x^k$, thu được phương án vận chuyển tối ưu ${x_{ij}^k}$ và hệ thế vị tương ứng ${u_i^k, v_j^k}$.
      2. Tính giá trị $g_k = \sum_{i=1}^m \sum_{j=1}^n c_{ij} x_{ij}^k = \sum_{i=1}^m u_i^k x_i^k + \sum_{j=1}^n v_j^k b_j$.
      3. Kiểm tra tiêu chuẩn tối ưu: Nếu $g_k \le t^k$, thuật toán dừng, phương án ${x_i^k, x_{ij}^k}$ là nghiệm tối ưu toàn cục của $(P)$.
      4. Nếu $g_k > t^k$, bổ sung ràng buộc cắt $-t + \sum_{i=1}^m u_i^k x_i + \sum_{j=1}^n v_j^k b_j \le 0$ vào bài toán quy hoạch lõm con $(Q_{k+1})$, giải $(Q_{k+1})$ bằng thuật toán xấp xỉ ngoài để tìm $(t^{k+1}, x^{k+1})$ và chuyển sang vòng lặp tiếp theo.
  • Thực nghiệm ví dụ số 3.1: Xét bài toán phân bố sản xuất với 3 nhà máy ($m=3$), hàm chi phí có phụ phí cố định với các vector tham số chi phí và cận trên công suất $c = (1, 7; 8, 4; 4, 7)$ và $d = (1; 88; 39)$. Quá trình tính toán thực hiện qua các bài toán $(Q_k)$ và $(T_k)$, cho nghiệm sản xuất tối ưu toàn cục là $x_1 = 77, x_2 = 51, x_3 = 75$.

Kết quả và đóng góp

Bảng dưới đây tổng hợp so sánh đặc tính vận hành giữa phương pháp tiếp cận trực tiếp và phương pháp phân rã được phân tích trong luận văn:

Tiêu chí so sánh Phương pháp tiếp cận trực tiếp Thuật toán phân rã (Luận văn đề xuất)
Không gian biến giải quy hoạch lõm Không gian $\mathbb{R}^{m + m \times n}$ (gồm cả biến sản xuất và biến vận tải) Không gian rút gọn $\mathbb{R}^{m+1}$ (chỉ gồm biến sản xuất $x$ và biến phụ $t$)
Xử lý thành phần tuyến tính Giải đồng thời cùng các hàm phi tuyến Tách riêng thành bài toán vận tải cỡ $m \times n$, giải hiệu quả bằng phương pháp thế vị
Số lượng ràng buộc cần xét Toàn bộ số phần tử của tập đỉnh đối ngẫu $\ddot{M}$ cùng lúc Sinh dần từng ràng buộc cắt theo từng vòng lặp lặp $k$
Số vòng lặp thực tế ghi nhận Đòi hỏi xử lý đa diện kích thước rất lớn Thường dừng sau khoảng $m + n$ vòng lặp
Mức độ phụ thuộc kích thước $n$ Độ phức tạp tính toán bùng nổ khi $n$ lớn Hiệu quả vượt trội khi số nhà máy $m$ nhỏ hơn nhiều so với số hộ tiêu thụ $n$ ($m \ll n$)

Các kết quả và kết luận rút ra từ thực nghiệm tính toán trong văn bản:

  • Thuật toán phân rã chuyển phần lớn khối lượng tính toán phức tạp về bài toán quy hoạch lõm kích thước nhỏ ($m+1$ biến), trong khi bài toán vận tải $(T_k)$ được giải nhanh chóng bằng thuật toán thế vị.
  • Khi cước phí vận chuyển $c_{ij}$ chiếm tỷ trọng áp đảo so với chi phí sản xuất, nghiệm tối ưu của bài toán $(P)$ tiệm cận với phương án tối thiểu hóa cước vận chuyển (mỗi hộ tiêu thụ nhận hàng từ nhà máy gần nhất, tức $x_{ij}^{opt} = 0$ khi $i \neq i(j)$).
  • Khi chi phí sản xuất $f_i(x_i)$ chiếm ưu thế so với cước phí vận chuyển, nghiệm tối ưu sẽ tập trung khối lượng sản xuất lớn tại các nhà máy có hàm chi phí rẻ hơn, dẫn tới việc một số nhà máy có chi phí cao sẽ có sản lượng bằng 0 ($x_i^{opt} = 0$).
  • Ví dụ số 3.1 minh họa trường hợp cả chi phí sản xuất và cước phí vận chuyển có sự cạnh tranh lẫn nhau, kiểm chứng tính hội tụ hữu hạn của thuật toán.

Hạn chế và hướng nghiên cứu tiếp

  • Hạn chế được đề cập trong văn bản: Thuật toán xấp xỉ ngoài và thuật toán phân rã phụ thuộc vào số lượng nhà máy $m$. Mặc dù số biến phi tuyến được giảm xuống còn $m$, khối lượng tính toán chính vẫn tập trung vào việc giải bài toán quy hoạch lõm con $(Q_k)$ qua từng bước lặp sinh đỉnh. Khi $m$ tăng lên mức lớn, số đỉnh của đa diện xấp xỉ ngoài tăng nhanh, đòi hỏi bộ nhớ và thời gian tính toán lớn.
  • Hướng mở rộng: Tác giả nêu định hướng tiếp tục tìm hiểu, nghiên cứu các thuật toán tối ưu toàn cục khác của quy hoạch lõm (như phương pháp nhánh cận, phương pháp lát cắt) và mở rộng phạm vi ứng dụng của thuật toán cho các mô hình kinh tế - kỹ thuật có cấu trúc phi tuyến phức tạp hơn trong tương lai.

Giá trị tham khảo

Luận văn là tài liệu tham khảo chuyên ngành hữu ích cho:

  • Học viên cao học và sinh viên chuyên ngành: Toán ứng dụng, Toán tin ứng dụng, Vận trù học (Operations Research), Tối ưu hóa kinh tế và Khoa học máy tính.
  • Phần giá trị tham khảo chuyên sâu:
    • Mục 1.2 & Chương 2: Kỹ thuật sinh đỉnh của đa diện lồi khi thêm ràng buộc tuyến tính và các bước chi tiết của thuật toán xấp xỉ ngoài.
    • Mục 3.2 & 3.3: Quy trình toán học chuyển đổi bài toán phân bố sản xuất phi tuyến kết hợp vận tải về bài toán quy hoạch lõm rút gọn trong $\mathbb{R}^{m+1}$ bằng lý thuyết đối ngẫu.

Câu hỏi thường gặp

1. Tại sao cực tiểu của hàm lõm trên đa diện lồi compact luôn đạt tại điểm cực biên (đỉnh)? Do tính chất của hàm lõm $f(\lambda x_1 + (1-\lambda) x_2) \ge \lambda f(x_1) + (1-\lambda) f(x_2) \ge \min{f(x_1), f(x_2)}$, giá trị hàm mục tiêu trên đoạn thẳng nối hai điểm bất kỳ luôn không nhỏ hơn giá trị tại hai đầu mút. Mọi điểm trong tập lồi compact đều biểu diễn được dưới dạng tổ hợp lồi của các đỉnh, do đó giá trị nhỏ nhất của hàm trên toàn bộ tập luôn đạt tại ít nhất một trong các đỉnh cực biên.

2. Điểm khác nhau cơ bản giữa hàm lõm và hàm tựa lõm là gì? Hàm $f$ là tựa lõm nếu $f(\lambda x + (1-\lambda) y) \ge \min{f(x), f(y)}$ với mọi $\lambda \in [0, 1]$, tương đương với việc mọi tập mức trên $D_\beta = {x : f(x) \ge \beta}$ đều là tập lồi. Mọi hàm lõm đều là hàm tựa lõm, nhưng hàm tựa lõm chưa chắc là hàm lõm (ví dụ hàm $f(x) = x^3$ trên $\mathbb{R}$ là tựa lõm nhưng không phải hàm lõm).

3. Tại sao trong mô hình phân bố sản xuất $(P)$, thuật toán phân rã lại hiệu quả hơn giải trực tiếp? Vì trong mô hình $(P)$, số biến phi tuyến lõm chỉ bằng $m$ (số nhà máy), trong khi số biến tuyến tính là $m \times n$ (vận chuyển từ $m$ nhà máy đến $n$ hộ). Kỹ thuật phân rã tách riêng $m \times n$ biến tuyến tính để giải bằng phương pháp thế vị nhanh chóng, chỉ giữ lại $m+1$ biến cho bài toán quy hoạch lõm con $(Q_k)$, giúp giảm đáng kể số chiều không gian cần xấp xỉ ngoài.

4. Đơn hình ban đầu $S_1$ trong thuật toán xấp xỉ ngoài được xác định như thế nào? Đơn hình ban đầu được xác định thông qua việc giải bài toán quy hoạch tuyến tính $\beta = \max {\sum_{j=1}^n x_j : x \in D}$. Khi đó, $S_1 = {x \in \mathbb{R}^n : \sum_{j=1}^n x_j \le \beta, x_j \ge 0}$, có $n+1$ đỉnh gồm gốc tọa độ $v_0 = 0$ và các đỉnh $v_j = \beta e_j$ (với $e_j$ là các vector đơn vị chuẩn tắc trong $\mathbb{R}^n$).

5. Kết quả tính toán của ví dụ số 3.1 trong luận văn cho ra nghiệm sản xuất tối ưu như thế nào? Trong ví dụ số 3.1 với 3 nhà máy có hàm chi phí sản xuất chứa phụ phí cố định và cước phí vận chuyển cạnh tranh, nghiệm sản xuất tối ưu toàn cục thu được là: nhà máy 1 sản xuất $x_1 = 77$ đơn vị, nhà máy 2 sản xuất $x_2 = 51$ đơn vị, và nhà máy 3 sản xuất $x_3 = 75$ đơn vị.

Kết luận

Luận văn đã trình bày hệ thống và chặt chẽ cơ sở giải tích lồi cho bài toán quy hoạch lõm với hệ ràng buộc tuyến tính, làm rõ nguyên lý cực trị tại đỉnh và thuật toán xấp xỉ ngoài. Đóng góp cốt lõi của công trình là việc xây dựng thành công thuật toán phân rã cho bài toán phân bố sản xuất với hàm chi phí lõm, đưa bài toán $(m + m \times n)$ biến về chuỗi các bài toán quy hoạch lõm $(m+1)$ biến kết hợp bài toán vận tải tuyến tính. Các kết quả phân tích lý thuyết và thực nghiệm tính toán đã chứng minh tính đúng đắn và hiệu quả vượt trội của phương pháp phân rã, đặc biệt trong các bài toán thực tiễn có số lượng hộ tiêu thụ lớn hơn nhiều so với số lượng cơ sở sản xuất.