Giải bài tập Quy hoạch tuyến tính

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)

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

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

 

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

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

\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

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

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *