Views: 319
Dạng 1. Giải bài toán MAX của bài toán QHTT
Bài 1.
$$
\begin{gathered}
\mathrm{z}=8 \mathrm{x}_{1}+3 \mathrm{x}_{2}+2 \mathrm{x}_{3} \rightarrow \max \\
\hline
2 \mathrm{x}_{1}+\mathrm{x}_{2}+\mathrm{x}_{3} \leq 6000 \\
2 \mathrm{x}_{1}+3 \mathrm{x}_{2}+\mathrm{x}_{3} \leq 10000 \\
3 \mathrm{x}_{1}+\mathrm{x}_{2}+\mathrm{x}_{3} \leq 21000 \\
\mathrm{x}_{\mathrm{j}} \geq 0, \mathrm{j}=1 ; 2 ; 3
\end{gathered}
$$
a. Hãy chuyển bài toán $(P)$ về dạng chuẩn ( 1 điểm).
b. Bằng phương pháp đơn hình hãy giải bài toán $(P)$ tìm phương án sản xuất tối ưu và tính tổng tiền lãi lớn nhất. (3 điểm).
c. Lập bài toán đối ngẫu $(\mathrm{D})$ của bài toán $(P)$ (2 điểm).
Giải.
a) Dạng chuẩn của bài toán $(P)$ là
$$
\begin{array}{ll}
z=8 x_{1}+3 x_{2}+2 x_{3} \quad \rightarrow \max \\
\hline 2 x_{1}+x_{2}+x_{3}+x_{4} & =6000, \\
2 x_{1}+3 x_{2}+x_{3}+x_{5} & =10000, \\
3 x_{1}+x_{2}+x_{3}+x_{6} & =21000, \\
x_{j} \geq 0, j=\overline{1 ; 6} . &
\end{array}
$$
b) Bảng đơn hình
Cách 1: (giải bài toán max)
Bảng 1
Do còn tồn tại giá trị Delta nhỏ hơn 0 nên chưa có phương án tôi ưu ta cần tìm biến đưa vào
Cột có giá trị nhỏ nhất ứng với $x_{1}$ vậy biến đưa vào là : $x_{1}$
Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 1
Bảng 2
Vì $\Delta_{j} \geq 0, \forall \mathrm{j}$ nên $\mathrm{PACB}$ ở bảng 2 đã tối ưu.
Vậy kế hoạch sản xuất tối ưu của bt $(\mathrm{P})$ là: $\mathrm{x}^{*}=(3000,0,0)$ (tức là 3000 sản phẩm loại $\mathrm{A}, 0 \mathrm{sp}$ loại $\mathrm{B}$ và $0 \mathrm{sp}$ loại $\mathrm{C}$ ) và tổng tiền lãi lớn nhất là 24 triệu đồng.
Cách 2: (đưa về bài toán min để giải)
Từ bài toán gốc
$$
\begin{gathered}
\mathrm{z}=8 \mathrm{x}_{1}+3 \mathrm{x}_{2}+2 \mathrm{x}_{3} \rightarrow \max \\
\hline
2 \mathrm{x}_{1}+\mathrm{x}_{2}+\mathrm{x}_{3} \leq 6000 \\
2 \mathrm{x}_{1}+3 \mathrm{x}_{2}+\mathrm{x}_{3} \leq 10000 \\
3 \mathrm{x}_{1}+\mathrm{x}_{2}+\mathrm{x}_{3} \leq 21000 \\
\mathrm{x}_{\mathrm{j}} \geq 0, \mathrm{j}=1 ; 2 ; 3
\end{gathered}
$$
Đưa về bài toán tương đương với công thức
$F(x)=-f(x)=-\sum_{j=1}^{n} c_{j} x_{j} \rightarrow \min$
$R b\left(^{*}\right)$
Ta được
$$
\begin{gathered}
\mathrm{z}=-8 \mathrm{x}_{1}-3 \mathrm{x}_{2}-2 \mathrm{x}_{3} \rightarrow \min \\
\hline
2 \mathrm{x}_{1}+\mathrm{x}_{2}+\mathrm{x}_{3} \leq 6000 \\
2 \mathrm{x}_{1}+3 \mathrm{x}_{2}+\mathrm{x}_{3} \leq 10000 \\
3 \mathrm{x}_{1}+\mathrm{x}_{2}+\mathrm{x}_{3} \leq 21000 \\
\mathrm{x}_{\mathrm{j}} \geq 0, \mathrm{j}=1 ; 2 ; 3
\end{gathered}
$$
Bảng đơn hình
Bảng 1
Do còn tồn tại giá trị Delta lớn hơn 0 nên chưa có phương án tôi ưu ta cần tìm biến đưa vào
Cột có giá trị Delta lớn nhất ứng vớ i $x_{1}$ vậy biến đưa vào là : $x_{1}$
Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 1
Bảng 2
Vì $\Delta_{j} \leq 0, \forall \mathrm{j}$ nên $\mathrm{PACB}$ ở bảng 2 đã tối ưu.
Vậy kế hoạch sản xuất tối ưu của bt $(\mathrm{P})$ là: $\mathrm{x}^{*}=(3000,0,0)$.
Giá trị hàm mục tiêu đạt được là: F(x) = -f(x) = -(-24000) = 24000
c) Bài toán đối ngẫu của (P) là:
$$
\begin{gathered}
{6000 y_{1}+10000 y_{2}+21000 y_{3} \rightarrow \min } \\
\hline
{2 y_{1}+2 y_{2}+3 y_{3} \geq 8} \\
y_{1}+3 y_{2}+y_{3} \geq 3 \\
y_{1}+y_{2}+y_{3} \geq 2 \\
y_{i} \geq 0, i=1,2,3 .
\end{gathered}
$$
Bài 2.
$$
\begin{gathered}
F(x)=-6 x_{1}- 3x_{2}+7 x_{3} \rightarrow \max \\
\hline
-x_{1}-x_{2}+3 x_{3} \leq 3 \\
-2 x_{1}-4 x_{2}+2 x_{3} \leq 9 \\
4 x_{1}+2 x_{2}-3 x_{3} \leq 2 \\
x_{1}, x_{2}, x_{3} \geq 0.
\end{gathered}
$$
a. Hãy chuyển bài toán $(P)$ về dạng chuẩn ( 1 điểm).
b. Bằng phương pháp đơn hình hãy giải bài toán $(P)$ tìm phương án sản xuất tối ưu và tính tổng tiền lãi lớn nhất. (3 điểm).
c. Lập bài toán đối ngẫu $(\mathrm{D})$ của bài toán $(P)$ (2 điểm).
Giải.
a) Dạng chuẩn của bài toán $(P)$ là
$$
\begin{array}{ll}
F(x) = -6 x_{1}-3 x_{2}+7 x_{3} \quad \rightarrow \max \\
\hline
– x_{1}-x_{2}+3x_{3}+x_{4} & =3 \\
-2 x_{1}-4 x_{2}+2x_{3}+x_{5} & =9 \\
4 x_{1}+2x_{2}-3x_{3}+x_{6} & =2 \\
x_{j} \geq 0, j=\overline{1 ; 6} . &
\end{array}
$$
b) Bảng đơn hình
Cách 1: (giải bài toán max)
Bảng 1
Do còn tồn tại giá trị Delta nhỏ hơn 0 nên chưa có phương án tối ưu ta cần tìm biến đưa vào
Cột có giá trị nhỏ nhất ứng với $x_{3}$ vậy biến đưa vào là : $x_{3}$
Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 1
Vì $\Delta_{j} \geq 0, \forall \mathrm{j}$ nên $\mathrm{PACB}$ ở bảng 2 đã tối ưu.
Phương án tối ưu của bài toán là: $\mathrm{x}^{*}=(0,0,1)$.
Giá trị hàm mục tiêu f(x) = 7
Cách 2: (đưa về bài toán min để giải)
Từ bài toán gốc
$$
\begin{gathered}
f(x)=-6 x_{1}- 3x_{2}+7 x_{3} \rightarrow \max \\
\hline
-x_{1}-x_{2}+3 x_{3} \leq 3 \\
-2 x_{1}-4 x_{2}+2 x_{3} \leq 9 \\
4 x_{1}+2 x_{2}-3 x_{3} \leq 2 \\
x_{1}, x_{2}, x_{3} \geq 0.
\end{gathered}
$$
Đưa về bài toán tương đương với công thức
$F(x)=-f(x)=-\sum_{j=1}^{n} c_{j} x_{j} \rightarrow \min$
$R b\left(^{*}\right)$
Ta được
$$
\begin{gathered}
\mathrm{z}=6 \mathrm{x}_{1}+3 \mathrm{x}_{2}-7 \mathrm{x}_{3} \rightarrow \min \\
\hline
-x_{1}-x_{2}+3 x_{3} \leq 3 \\
-2 x_{1}-4 x_{2}+2 x_{3} \leq 9 \\
4 x_{1}+2 x_{2}-3 x_{3} \leq 2 \\
x_{1}, x_{2}, x_{3} \geq 0.
\end{gathered}
$$
Bảng đơn hình
Bảng 1
Do còn tồn tại giá trị Delta lớn hơn 0 nên chưa có phương án tôi ưu ta cần tìm biến đưa vào
Cột có giá trị lớn hơn 0 và nhỏ nhất ứng vớ i $x_{1}$ vậy biến đưa vào là : $x_{1}$
Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 3
Bảng 2
Do còn tồn tại giá trị Delta lớn hơn 0 nên chưa có phương án tôi ưu ta cần tìm biến đưa vào
Cột có giá trị lớn hơn 0 và nhỏ nhất ứng vớ i $x_{2}$ vậy biến đưa vào là : $x_{2}$
Hàng có giá trị Lamda nhỏ nhất ứng với cột đó là hàng 3
Bảng 3
Vì $\Delta_{j} \leq 0, \forall \mathrm{j}$ nên $\mathrm{PACB}$ ở bảng 3 đã tối ưu.
Phương án tối ưu của bài toán là (0,1,0)
Giá trị hàm mục tiêu đạt được là: F(x) = -f(x) = -(-7) = 7
c) Bài toán đối ngẫu của (P) là:
$$
\begin{gathered}
{3 y_{1}+9 y_{2}+2 y_{3} \rightarrow \min } \\
\hline
{-y_{1}-2 y_{2}+4 y_{3} \geq -6} \\
-y_{1}-4 y_{2}+2y_{3} \geq -3 \\
3y_{1}+2y_{2}-3y_{3} \geq 7 \\
y_{i} \geq 0, i=1,2,3 .
\end{gathered}
$$