BÀI GIẢNG MÔN
TOÁN KINH TẾ
www.ptit.edu.vn GIẢNG VIÊN: TS. Trần Ngọc Minh
BỘ MÔN: KINH TẾ - KHOA QTKD1 Trang #
CHƢƠNG 4
BÀI TOÁN TỐI ƢU TRÊN MẠNG
-Ý nghĩa mạng của đối ngấu:
Giả sử ta phải chuyển lƣợng hàng bi > 0 từ mỗi đỉnh i = 1, 2, ..., n-1 tới đỉnh n
theo một mạng riêng của mình. Khi đó nghiệm tối ƣu của bài toán dòng trên
mạng cho ta cách vận chuyển tốt nhất.
Lại giả sử có một công ty vận tải mở dịch vụ vận chuyển từ mọi đỉnh i đến đỉnh
n (theo mạng của họ) với giá vận chuyển một đơn vị hàng là pi. Nếu (i, j) là một
cung trong mạng riêng của ta và phí tổn vận chuyển một đơn vị hàng trên cung
này là cij, thì ta có thể tự chuyển hàng từ i đến j rồi giao cho công ty vận tải
chuyển nốt đến đỉnh n, với giá đơn vị là cij + pi. Công ty vận tải biết các véc tơ b
và c và tìm cách bao hết việc vận chuyển hàng của ta, kể cả trên cung (i, j). Khi
đó họ phải ra giá để cạnh tranh là pi ≤ cij + pj và pn = 0. Với giá đủ hấp dẫn này,
coi nhƣ ràng buộc, mục đích của họ tất nhiên là làm cực đại doanh thu . Vậy bài
toán của công ty chính là bài toán đối ngẫu với bài toán tự vận chuyển của ta.
Định lý đối ngẫu mạnh của quy hoạch tuyến tính nói rằng doanh thu tối ƣu của
công ty đúng bằng phí tổn tối ƣu khi ta tự vận chuyển bằng mạng rieng. Nói cách
khác, nếu hai phía đều tìm cách vận chuyển tối ƣu và giá của công ty đặt ra đúng
thì cƣớc phí là nhƣ nhau.
CuuDuongThanCong.com https://fb.com/tailieudientucntt
