bài tập nhóm giải bài toán tối ưu bằng công cụ lập trình bài toán cần xử lý bài toán vận tải công cụ lập trình sử dụng python cvxopt
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (164.66 KB, 11 trang )
<span class="text_page_counter">Trang 1</span><div class="page_container" data-page="1">
<b>BỘ GIÁO DỤC VÀ ĐÀO TẠO</b>
<b>TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINHKHOA KINH TẾ</b>
<b>BÀI TẬP NHĨM:</b>
<b>GIẢI BÀI TỐN TỐI ƯU BẰNG CƠNG CỤ LẬP TRÌNH</b>
<b>Mơn học: Tối ưu hóa</b>
<b>Bài tốn cần xử lý: BÀI TỐN VẬN TẢI</b>
<b>Cơng cụ lập trình sử dụng: PYTHON (CVXOPT)</b>
</div><span class="text_page_counter">Trang 2</span><div class="page_container" data-page="2"><b>ĐỀ BÀI: Công ty TNHH </b>thiết bị điện tử DAEWOO Việt Nam là doanh nghiệp sản xuất
thiết bị và linh kiện điện tử có 2 chi nhánh tại Bình Dương (A1) và TP. Hồ Chí Minh (A2), trong kho của mỗi chi nhánh có số lượng lơ hàng linh kiện điện tử tối đa tương ứng
với Bảng 1. Doanh nghiệp cần vận chuyển các lô hàng đến 3 cảng: Quy Nhơn (B1), Sài Gòn (B2), Vũng Tàu (B3) để xuất khẩu sang 3 nước Anh, Thổ Nhĩ Kỳ, Philippines bằng đường biển, mỗi cảng cần tối đa số lượng lô hàng tương ứng với Bảng 2. Chi phí vận chuyển trung bình vận chuyển đến các cảng là 20.000VNĐ / 1km, chi phí vận chuyển hàng từ mỗi chi nhánh đến từng cảng biển được quy định theo Bảng 3. Tìm phương án tối ưu để vận chuyển hàng từ các chi nhánh đến các cảng biển để chi phí là thấp nhất.
Bảng 1
<i>(ĐVT: Lô hàng)</i>
Bảng 2
<i>(ĐVT: Lô hàng)</i>
</div><span class="text_page_counter">Trang 3</span><div class="page_container" data-page="3">Cảng Quy Nhơn (B1) 90
</div><span class="text_page_counter">Trang 5</span><div class="page_container" data-page="5"><b>Bước 2: Lập mơ hình bài tốn.</b>
Gọi <i>x<sub>ij</sub></i> là số lượng lô hàng vận chuyển từ chi nhánh i đến cảng j. Ta có hàm mục tiêu tối thiểu hóa chi phí:
</div><span class="text_page_counter">Trang 6</span><div class="page_container" data-page="6"><i>19280 x</i><sub>11</sub>+<i>900 x</i><sub>12</sub>+2000 x<sub>13</sub>+12460 x<sub>21</sub>+220 x<sub>22</sub>+1560 x<sub>23</sub><i>→ min</i> (1)
Do tổng số lượng lô hàng vận chuyển từ mỗi chi nhánh đến các cảng không được vượt quá công suất tối đa của chi nhánh đó, nên ta có:
{x<sub>11</sub>+<i>x</i><sub>12</sub>+<i>x</i><sub>13</sub><i>≤170 x</i><sub>21</sub>+<i>x</i><sub>22</sub>+<i>x</i><sub>23</sub><i>≤130</i>
Do tổng số lượng lơ hàng vận chuyển đến mỗi cảng phải lớn hơn hoặc bằng số lượng lơ hàng mà cảng đó u cầu, nên ta có:
<b>Bước 3: Chuyển bài tốn về dạng Vector.</b>
Chuyển đổi hàm mục tiêu (1): c<small>T</small>x
<i>19280 x</i><sub>11</sub>+<i>900 x</i><sub>12</sub>+2000 x<sub>13</sub>+12460 x<sub>21</sub>+220 x<sub>22</sub>+1560 x<sub>23</sub><i>→ min</i>
<i>x=</i>
[
<i>x</i><sub>11</sub><i>x</i><sub>12</sub><i>x</i><sub>13</sub><i>x</i><sub>21</sub><i>x</i><sub>22</sub><i>x</i><sub>23</sub>]
<i>c=</i>[19280 900 2000 12460220 1560]</div><span class="text_page_counter">Trang 7</span><div class="page_container" data-page="7">x: vector biến số
c: vector hệ số hàm mục tiêu
Ràng buộc dạng bất đẳng thức (2), (3): Gx ≤ h.
{x<sub>11</sub>+<i>x</i><sub>12</sub>+<i>x</i><sub>13</sub><i>≤170 x</i><sub>21</sub>+<i>x</i><sub>22</sub>+<i>x</i><sub>23</sub><i>≤130 x</i><sub>11</sub>+<i>x</i><sub>21</sub><i>≥ 90 x</i><sub>12</sub>+<i>x</i><sub>22</sub><i>≥ 110 x</i><sub>13</sub>+<i>x</i><sub>23</sub><i>≥ 180 x</i><sub>11</sub><i>≥ 0 x</i><sub>12</sub><i>≥ 0 x</i><sub>13</sub><i>≥ 0 x</i><sub>21</sub><i>≥ 0 x</i><sub>22</sub><i>≥0 x</i><sub>23</sub><i>≥ 0</i>
Chuyển dấu tất cả BĐT về dấu <i>' ≤ '</i> vì mỗi phần tử trong ma trận ở vế trái (vector) phải nhỏ hơn hoặc bằng phần tử tương ứng trong ma trận (vector) ở vế phải.
{x<sub>11</sub>+<i>x</i><sub>12</sub>+<i>x</i><sub>13</sub><i>≤170 x</i><sub>21</sub>+<i>x</i><sub>22</sub>+<i>x</i><sub>23</sub><i>≤130−x</i><sub>11</sub>−x<sub>21</sub><i>≤−90−x</i><sub>12</sub>−x<sub>22</sub><i>≤−110−x</i><sub>13</sub>−x<sub>23</sub><i>≤−180−x</i><sub>11</sub><i>≤ 0−x</i><sub>12</sub><i>≤0−x</i><sub>13</sub><i>≤ 0−x</i><sub>21</sub><i>≤ 0−x</i><sub>22</sub><i>≤0−x</i><sub>23</sub><i>≤ 0</i>
</div><span class="text_page_counter">Trang 9</span><div class="page_container" data-page="9"><b>Bước 4: Xử lý bài toán bằng python (cvxopt).</b>
Ta có kết quả:
</div><span class="text_page_counter">Trang 10</span><div class="page_container" data-page="10">File chi tiết:
</div><span class="text_page_counter">Trang 11</span><div class="page_container" data-page="11">Bình Dương x<small>11</small>=0 x<small>12</small>=70 x<small>13</small>=80
Chi phí vận chuyển tối thiểu là:
f (x*) = 1.353.200 (nghìnVNĐ) hay f (x*) = 1.353.200.000 VNĐ
</div>
