Stochastic Optimization: bài toán người nông dân (The farmer’s problem)

Posted: 18/02/2026

Bài toán người nông dân (Farmer’s problem) là một ví dụ kinh điển trong stochastic optimization , được sử dụng trong sách "Introduction to Stochastic Programming" của Birge và Louveaux, dùng để minh họa cách mô hình hóa (modelling) và giải (solve) các bài toán ra quyết định dưới điều kiện không chắc chắn (uncertainty). Bài toán thể hiện cấu trúc two-stage stochastic program với recourse, trong đó các quyết định phải được đưa ra trước khi các biến ngẫu nhiên được hiện thực hóa, và sau đó được điều chỉnh thông qua các quyết định bù (recourse decisions) khi thông tin không chắc chắn trở nên rõ ràng. Trong bài viết này, mình sẽ hướng dẫn cách mô hình hóa bài toán dưới dạng stochastic programming, và cung cấp cách lập trình để tìm nghiệm tối ưu thông qua ngôn ngữ AMPL và Python.

1. Mô tả bài toán

Một người nông dân có 500 acres đất trồng trọt và trồng ba loại cây:

Lúa mì (wheat)
Bắp (Corn)
Củ cải đường (Sugar beets)

Trước khi biết điều kiện thời tiết của năm tới (weather scenario), người nông dân phải quyết định diện tích đất dành cho từng loại cây (first-stage decisions). Trang trại cần tối thiểu 200 tấn lúa mì và 240 tấn bắp để làm thức ăn cho gia súc. Các số lượng này có thể được sản xuất trên trang trại hoặc mua từ trung gian. Phần dư có thể bán ra thị trường.

Giá bán trung bình:

Lúa mì: 170 $/tấn
Bắp: 150 $/tấn
Củ cải đường 36 $/tấn

Giá mua cao hơn 40% so với giá bán. Số liệu được thể hiện qua bảng sau:

Bảng 1: Chi phí và năng suất các loại cây
Mùa vụ (Crop)	Năng suất (Yield) (T/acre)	Chi phí trồng (Planting cost) ($/acre)	Giá bán (Selling price) ($/T)	Giá mua (Purchase price) ($/T)	Yêu cầu tối thiểu (Minimum requirement) (T)
Lúa mì	2.5	150	170	238	200
Bắp	3.0	230	150	210	240
Củ cải đường	20	260	36	-	-

Giả sử bây giờ ta muốn mô hình hóa bài toán với việc xét đến yếu tố năng suất cây trồng là không chắc chắn, phụ thuộc vào điều kiện thời tiết, như được tóm tắt trong bảng dưới đây.

Bảng 2: Kịch bản và năng suất dự kiến
Kịch bản (Scenario)	Mô tả thời tiết (Description)	Năng suất lúa mì (tons/acre)	Năng suất bắp (tons/acre)	Năng suất củ cải đường (tons/acre)	Xác suất (Probability)
s = 1	Tốt (good)	3	3.6	20	0.25
s = 2	Trung bình (average)	2.5	3	15	0.4
s = 3	Tệ (bad)	2	2.4	10	0.35

Từ dữ liệu trên, hãy lập mô hình tính toán để tối đa hóa lợi nhuận kỳ vọng cho người nông dân.

2. Giải deterministic problem

Từ dữ liệu bài toán trên, ta có mô hình linear programming như sau:

$$ \max Z = -150x_w - 230x_c - 260x_b + 170y_w + 150y_c + 36y_b - 238z_w - 210z_c $$ $$ \text{subject to: } \begin{cases} x_w + x_c + x_b \le 500 \\ 2.5 x_w + z_w - y_w \ge 200 \\ 3 x_c + z_c - y_c \ge 240 \\ 20 x_b - y_b \ge 0 \\ x_w, x_c, x_b, y_w, y_c, y_b, z_w, z_c \ge 0 \end{cases} $$

Trong đó:

$ x_w $: diện tích đất trồng lúa mì (acre)

$ x_c $: diện tích đất trồng bắp (acre)

$ x_b $: diện tích đất trồng củ cải đường (acre)

$ y_w $: lượng lúa mì mua từ nhà bán sỉ (tấn)

$ y_c $: lượng bắp mua từ nhà bán sỉ (tấn)

$ z_w $: lượng lúa mì bán ra (tấn)

$ z_c $: lượng bắp bán ra (tấn)

$ z_b $: lượng củ cải đường bán ra (tấn)

Giải bài toán trên, ta thu được kết quả:

$$ x_w = 80 , \quad x_c = 80, \quad x_b=340, \quad y_w = 0, \quad y_c = 0, \quad z_b = 5100, \quad Z = 64,800 $$

Nếu ta giải bài toán theo từng kịch bản riêng biệt, thì ta có kết quả sau:

Tốt (Good)	Trung bình (Fair)	Tệ (Bad)
x_w = 66.67, x_c = 66.67, x_b = 366.67, y_w = 0, y_c = 0, z_b = 7,333.33, z_w = 0, z_c = 0 Z = 143,333.33	x_w = 80, x_c = 80, x_b = 340, y_w = 0, y_c = 0, z_b = 5,100, z_w = 0, z_c = 0 Z = 64,800	x_w = 400, x_c = 100, x_b = 0, y_w = 0, y_c = 0, z_w = 600, z_b = 0, z_c = 0 Z = 19,000

3. Giải 2-stages stochastic problem

Tổng quan

Xét một bài toán w-stages stochastic, trong đó vector biến quyết định được chia thành hai nhóm: biến giai đoạn một (here-and-now) $x \in \mathbb{R}^n$ và biến giai đoạn hai (recourse decisions) $y(\xi) \in \mathbb{R}^m$, phụ thuộc vào biến ngẫu nhiên $\xi$. Khi đó, mô hình hai giai đoạn với recourse có dạng tổng quát:

$$ \min_{x \in X} \; c^\top x + \mathbb{E}_{\xi}[ Q(x, \xi) ] $$

trong đó hàm chi phí giai đoạn hai được định nghĩa bởi:

$$ Q(x, \xi) = \min_{y} \; q(\xi)^\top y $$ $$ \text{s.t.} \quad W(\xi)y = h(\xi) - T(\xi)x, \quad y \ge 0. $$

Ở đây:

$x$ là quyết định được đưa ra trước khi biết $\xi$
$y$ là quyết định điều chỉnh sau khi $\xi$ được quan sát
$c$ là vector chi phí giai đoạn một
$q(\xi)$ là vector chi phí giai đoạn hai
$T(\xi)$ liên kết quyết định giai đoạn một với ràng buộc giai đoạn hai
$W(\xi)$ và $h(\xi)$ xác định cấu trúc hệ ràng buộc sau khi bất định được hiện thực hóa

Nếu không gian bất định rời rạc với tập kịch bản $S = \{1, \dots, |S|\}$ và xác suất $p_s$, mô hình tương đương dạng xác định mở rộng (deterministic equivalent):

$$ \min_{x, y_s} \; c^\top x + \sum_{s \in S} p_s \, q_s^\top y_s. $$

Trở lại bài toán hiện tại, yếu tố stochastic là năng suất cây trồng phụ thuộc vào kịch bản thời tiết theo bảng 2 $s \in S = \{1,2,3\}$.

Biến giai đoạn một:

$$ x = (x_w, x_c, x_b) $$

là diện tích đất phân bổ cho lúa mì ($w$), bắp ($c$) và củ cải đường ($b$). Các quyết định này được đưa ra trước khi biết năng suất thực tế.

Biến giai đoạn hai: với mỗi kịch bản $s$, ta có

$$ y_s = (y_{w,s}, y_{c,s}, z_{w,s}, z_{c,s}, z_{b,s}) $$

bao gồm lượng mua bổ sung và lượng bán ra sau khi năng suất được quan sát.

Hàm mục tiêu

Lợi nhuận kỳ vọng cần tối đa hóa:

$$ \max_x \; -150 x_w - 230 x_c - 260 x_b + \sum_{s \in S} p_s \, Q(x,s). $$

trong đó:

$$ Q(x,s) = \max_{y_s} \; 170 z_{w,s} + 150 z_{c,s} + 36 z_{b,s} - 238 y_{w,s} - 210 y_{c,s}. $$

Ràng buộc

Ràng buộc đất (giai đoạn một):

$$ x_w + x_c + x_b \le 500 $$

Với mỗi kịch bản $s$, ràng buộc cân bằng vật chất:

$$ a_{w,s} x_w + y_{w,s} - z_{w,s} \ge 200, $$ $$ a_{c,s} x_c + y_{c,s} - z_{c,s} \ge 240, $$ $$ a_{b,s} x_b - z_{b,s} \ge 0, $$ $$ x \ge 0, \quad y_s \ge 0. $$

Trong đó $a_{w,s}, a_{c,s}, a_{b,s}$ là năng suất tương ứng theo từng kịch bản thời tiết.

Trở lại bài toán

Thế số vào, ta có:

$$ \begin{alignedat}{2} \max Z = \; & 170(0.25 z_{w,1} + 0.4 z_{w,2} + 0.35 z_{w,3}) \\ & + 150(0.25 z_{c,1} + 0.4 z_{c,2} + 0.35 z_{c,3}) \\ & + 36(0.25 z_{b,1} + 0.4 z_{b,2} + 0.35 z_{b,3}) \\ & - 238(0.25 y_{w,1} + 0.4 y_{w,2} + 0.35 y_{w,3}) \\ & - 210(0.25 y_{c,1} + 0.4 y_{c,2} + 0.35 y_{c,3}) \\ & - (150 x_w + 230 x_c + 260 x_b) \end{alignedat} $$

$$ \begin{alignedat}{2} \text{subject to:} \quad & x_w + x_c + x_b \le 500 \\ & 3 x_w + y_{w,1} - z_{w,1} \ge 200 \\ & 2.5 x_w + y_{w,2} - z_{w,2} \ge 200 \\ & 2 x_w + y_{w,3} - z_{w,3} \ge 200 \\ & 3.6 x_c + y_{c,1} - z_{c,1} \ge 240 \\ & 3 x_c + y_{c,2} - z_{c,2} \ge 240 \\ & 2.4 x_c + y_{c,3} - z_{c,3} \ge 240 \\ & 20 x_b - z_{b,1} \ge 0 \\ & 15 x_b - z_{b,2} \ge 0 \\ & 10 x_b - z_{b,3} \ge 0 \\ & x_w, x_c, x_b, y_{w,s}, z_{w,s} \ge 0 \end{alignedat} $$

Một điểm quan trọng cần lưu ý là các biến quyết định ở giai đoạn hai được tách thành các biến recourse theo từng scenario. Ví dụ, biến $ z_w $ không còn là một biến duy nhất mà được tách thành $ z_{w,1} $, $ z_{w,2} $, $ z_{w,3} $ tương ứng với ba kịch bản thời tiết. Điều này có nghĩa là sau khi thời tiết thực tế được tiết lộ, người nông dân có thể điều chỉnh quyết định bán hoặc mua sao cho phù hợp với từng tình huống cụ thể.

Tương tự, tất cả các biến như $ y_w, y_c, z_c, z_b $ đều được mở rộng theo chỉ số kịch bản $s$. Khi đó, các ràng buộc (ví dụ như nhu cầu thức ăn cho gia súc) cũng phải được viết riêng cho từng scenario. Nhờ vậy, mô hình phản ánh đúng bản chất của two-stage stochastic programming with recourse: quyết định diện tích trồng được đưa ra trước, còn quyết định mua/bán được điều chỉnh sau.

Giải mô hình này, ta thu được nghiệm:

$$ \begin{alignedat}{3} x_w &= 420 &\qquad y_{w,1} &= 0 &\qquad z_{w,1} &= 1060 \\ x_c &= 80 &\qquad y_{c,1} &= 0 &\qquad z_{c,1} &= 48 \\ x_b &= 0 &\qquad y_{b,1} &= 0 &\qquad z_{b,1} &= 0 \\[6pt] & & y_{w,2} &= 0 &\qquad z_{w,2} &= 850 \\ & & y_{c,2} &= 0 &\qquad z_{c,2} &= 0 \\ & & y_{b,2} &= 0 &\qquad z_{b,2} &= 0 \\[6pt] & & y_{w,3} &= 0 &\qquad z_{w,3} &= 640 \\ & & y_{c,3} &= 48 &\qquad z_{c,3} &= 0 \\ & & y_{b,3} &= 0 &\qquad z_{b,3} &= 0 \end{alignedat} $$ $$ Z = 57,\!802 $$

Nếu bạn nhìn vào giá trị của hàm mục tiêu, ta không thể tính nó bằng cách lấy kỳ vọng (expectation) của các giá trị hàm mục tiêu thu được khi giải riêng từng kịch bản:

$$ 0.25 * (143,333.33) + 0.4 * (64,800) + 0.35 * (19,000) = 68,403.33 $$

Nếu giải từng kịch bản riêng lẻ, ta đang vô tình giả định rằng người nông dân biết trước điều kiện thời tiết - tức là có perfect information. Trong thực tế, điều này là không thể. Một phương án tối ưu cho năm tốt hoàn toàn có thể trở nên không khả thi nếu năm đó lại là tệ.

Ngược lại, mô hình two-stage stochastic buộc ta phải chọn quyết định diện tích trồng sao cho tối ưu trên toàn bộ các kịch bản có thể xảy ra. Nói cách khác, đây là một chiến lược ra quyết định có tính đến rủi ro, thay vì dựa trên giả định biết trước tương lai.

4. Python

Dưới đây là đoạn Python code mình đã lập trình để giải bài toán trên, mình chọn solver CBC.


import pulp

# model
m = pulp.LpProblem("stochastic_programming", pulp.LpMaximize)

# parameters
crops = ['wheat','corn','beet']
scenarios = ['S1','S2','S3']

yields = [[3, 3.6, 20],
          [2.5, 3, 15],
          [2, 2.4, 10]]

yields_prop = [0.25, 0.4, 0.35]
selling_profit = [170, 150, 36]
purchase_cost = [238, 210, 1000000]
plant_cost = [150, 230, 260]
rhs = [200, 240, 0]

# decision variables
land = pulp.LpVariable.dicts("x", crops, lowBound=0)
purchase = pulp.LpVariable.dicts("y", (scenarios, crops), lowBound=0)
sold = pulp.LpVariable.dicts("z", (scenarios, crops), lowBound=0)

# constraint: total land
m += pulp.lpSum(land[j] for j in crops) <= 500

# scenario constraints
for j in range(len(scenarios)):
    for i in range(len(crops)):
        m += (yields[j][i] * land[crops[i]]
            + purchase[scenarios[j]][crops[i]]
            - sold[scenarios[j]][crops[i]]
            >= rhs[i])

# objective
m += (pulp.lpSum(
        selling_profit[j] * yields_prop[k] * sold[scenarios[k]][crops[j]]
        for j in range(len(crops))
        for k in range(len(scenarios)))
    - pulp.lpSum(plant_cost[j] * land[crops[j]] for j in range(len(crops)))
    - pulp.lpSum(
        purchase_cost[j] * yields_prop[k] * purchase[scenarios[k]][crops[j]]
        for j in range(len(crops))
        for k in range(len(scenarios))))

# solve with CBC
m.solve(pulp.PULP_CBC_CMD())

# print results
print("land allocation:")
for j in crops:
    if land[j].varValue > 0:
        print(j, round(land[j].varValue,2))

print("\npurchases:")
for s in scenarios:
    for j in crops:
        if purchase[s][j].varValue > 0:
            print(s, j, round(purchase[s][j].varValue,2))

print("\nsold:")
for s in scenarios:
    for j in crops:
        if sold[s][j].varValue > 0:
            print(s, j, round(sold[s][j].varValue,2))

print("\nprofit:", round(pulp.value(m.objective),2))

4. Giải bằng AMPL

File mô hình cho AMPL (model.mod)

Dưới đây là hướng dẫn tạo lập mô hình bằng ngôn ngữ AMPL. Để mô hình hóa bài toán này trong AMPL, ta cần làm theo các bước cơ bản: định nghĩa tập hợp và tham số, khai báo biến quyết định, xây dựng ràng buộc và cuối cùng là định nghĩa hàm mục tiêu.

Định nghĩa tập hợp và tham số

Trước tiên, ta xác định các tập hợp (sets) và tham số (parameters) của bài toán.

# sets
set crops;      # loại cây trồng
set scenarios;  # các kịch bản mùa vụ

# parameters
param yield {scenarios, crops};       # năng suất theo kịch bản
param prob {scenarios};               # xác suất mỗi kịch bản

param selling_profit {crops};         # lợi nhuận bán mỗi loại cây
param purchase_cost {crops};          # chi phí mua thêm
param plant_cost {crops};             # chi phí trồng
param rhs {crops};                    # nhu cầu tối thiểu
param total_land;                     # tổng diện tích đất

Trong đó:

set là tập hợp các đối tượng, tương tự danh sách trong Python. Ở đây, ta có các loại cây và các kịch bản mùa vụ.
param là tham số số liệu, ví dụ năng suất theo kịch bản (yield), chi phí và lợi nhuận.

Việc gắn kịch bản và loại cây giúp mô hình biết cách tính toán cho từng tình huống cụ thể.

Khai báo biến quyết định

Tiếp theo, ta xác định các biến quyết định, tức là những gì mô hình sẽ tối ưu:

var land {crops} >= 0;                     # diện tích trồng mỗi cây
var purchase {scenarios, crops} >= 0;      # mua thêm theo kịch bản
var sold {scenarios, crops} >= 0;          # bán theo kịch bản

Trong đó:

land[j] đại diện cho diện tích trồng cây j.
purchase[s,j] và sold[s,j] đại diện cho lượng mua và bán của loại cây j trong kịch bản s.
Tất cả các biến đều ≥ 0 vì không thể trồng, mua hay bán số âm.

Xây dựng các ràng buộc

a) Ràng buộc tổng diện tích đất

s.t. total_land_constraint:
    sum {j in crops} land[j] <= total_land;

Tổng diện tích trồng không vượt quá tổng diện tích đất sẵn có.

sum {j in crops} land[j] tương đương với tổng diện tích của từng loại cây cộng lại.

b) Ràng buộc cân bằng sản lượng theo kịch bản

s.t. balance {s in scenarios, j in crops}:
    yield[s,j] * land[j] + purchase[s,j] - sold[s,j] >= rhs[j];

Mỗi loại cây trong từng kịch bản phải đáp ứng nhu cầu tối thiểu (rhs[j]).

Công thức giải thích: sản lượng tự trồng (yield[s,j] * land[j]) cộng lượng mua thêm (purchase[s,j]), trừ lượng bán (sold[s,j]) phải lớn hơn hoặc bằng nhu cầu tối thiểu.

Xây dựng hàm mục tiêu

Cuối cùng, ta xác định hàm mục tiêu, là lợi nhuận kỳ vọng cần tối đa hóa:

maximize expected_profit:
    sum {s in scenarios, j in crops}
        prob[s] * selling_profit[j] * sold[s,j]
    - sum {j in crops}
        plant_cost[j] * land[j]
    - sum {s in scenarios, j in crops}
        prob[s] * purchase_cost[j] * purchase[s,j];

Lợi nhuận bán hàng kỳ vọng: tổng lợi nhuận từ bán từng loại cây trong mỗi kịch bản, nhân với xác suất xảy ra kịch bản (prob[s]).

Chi phí trồng: trừ đi chi phí trồng mỗi loại cây (plant_cost[j] * land[j]).

Chi phí mua thêm: trừ đi chi phí mua thêm trong từng kịch bản (prob[s] * purchase_cost[j] * purchase[s,j]).

Từ các thông tin trên, ta có file model.dat như sau:


  # sets
set crops;
set scenarios;

# parameters
param yield {scenarios, crops};
param prob {scenarios};

param selling_profit {crops};
param purchase_cost {crops};
param plant_cost {crops};
param rhs {crops};

param total_land;

# variables
var land {crops} >= 0;
var purchase {scenarios, crops} >= 0;
var sold {scenarios, crops} >= 0;

# constraints

# total land constraint
s.t. total_land_constraint:
    sum {j in crops} land[j] <= total_land;

# scenario constraints
s.t. balance {s in scenarios, j in crops}:
    yield[s,j] * land[j] + purchase[s,j] - sold[s,j] >= rhs[j];

# objective
maximize expected_profit:
    sum {s in scenarios, j in crops}
        prob[s] * selling_profit[j] * sold[s,j]
    - sum {j in crops}
        plant_cost[j] * land[j]
    - sum {s in scenarios, j in crops}
        prob[s] * purchase_cost[j] * purchase[s,j];

File dữ liệu cho AMPL (data.dat)

Đây là phần dữ liệu mà mô hình sẽ dùng, bao gồm tập hợp, tham số, xác suất và năng suất theo từng kịch bản.


# tập hợp
set crops := wheat corn beet;      # các loại cây trồng
set scenarios := s1 s2 s3;         # các kịch bản mùa vụ

# tham số 
param total_land := 500;           # tổng diện tích đất

# xác suất mỗi kịch bản
param prob :=
s1 0.25   # kịch bản tốt
s2 0.4    # kịch bản trung bình
s3 0.35;  # kịch bản xấu

# lợi nhuận bán mỗi cây
param selling_profit :=
wheat 170
corn 150
beet 36;

# chi phí mua thêm mỗi cây
param purchase_cost :=
wheat 238
corn 210
beet 1000000;

# chi phí trồng mỗi cây
param plant_cost :=
wheat 150
corn 230
beet 260;

# nhu cầu tối thiểu
param rhs :=
wheat 200
corn 240
beet 0;

# năng suất từng cây theo từng kịch bản
param yield:
        wheat   corn   beet :=
s1      3       3.6    20
s2      2.5     3      15
s3      2       2.4    10;

Chạy thực nghiệm

Sau khi build xong mô hình và dữ liệu, ta tiến hành chạy mô hình trong Console. Dòng lệnh để chạy mô hình được mô tả như sau:


model "model.mod";        # nạp file mô hình
data "data.dat";          # nạp file dữ liệu

solve option gurobi;      # giải bài toán, có thể chọn các solver khác như cplex, highs, cbc,...

display land;             # hiển thị diện tích trồng mỗi cây
display purchase;         # hiển thị lượng mua theo từng scenario
display sold;             # hiển thị lượng bán theo từng scenario
display expected_profit;  # hiển thị lợi nhuận kỳ vọng

← Back to Blog List