Bài giảng Tối ưu hóa: Chương 2 - ThS. Nguyễn Công Trí

Bài giảng "Tối ưu hóa - Chương 2: Bài toán quy hoạch tuyến tính đối ngẫu" cung cấp cho người học các kiến thức: các thành lập bài toán quy hoạch tuyến tính đối ngẫu, các định lý đối ngẫu, giải thuật đơn hình đối ngẫu,... Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Tối ưu hóa: Chương 2 - ThS. Nguyễn Công TríThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 BAØI TOAÙN QUY HOAÏCH CHÖÔNG 2 THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU TUYEÁN TÍNH ÑOÁI NGAÃU Muïc ñích vaø yù nghóa  Vôùi baøi toaùn QHTT, baøi toaùn goác, kyù hieäu laø P 1. CAÙCH THAØNH LAÄP BAØI TOAÙN QUY HOAÏCH (Primal), chuùng ta coù theå thieát laäp baøi toaùn QHTT Ths. Nguyeãn Coâng Trí TUYEÁN TÍNH ÑOÁI NGAÃU (Xem) khaùc, baøi toaùn ñoái ngaãu, kyù hieäu laø D (Dual), sao cho töø lôøi giaûi cuûa baøi toaùn naøy ta coù theå thu 2. CAÙC ÑÒNH LYÙ ÑOÁI NGAÃU (Xem) thaäp ñöôïc thoâng tin veà lôøi giaûi cuûa baøi toaùn kia. Copyright 2001 3. THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU (Xem)  Ñeå coù thoâng tin caàn thieát veà baøi toaùn goác, coù theå nghieân cöùu treân baøi toaùn ñoái ngaãu cuûa noù. 4. MOÄT SOÁ ÖÙNG DUÏNG CUÛA LYÙ THUYEÁT ÑOÁI  Hôn nöõa, khi phaân tích ñoàng thôøi caû hai baøi NGAÃU TRONG BAØI TOAÙN QHTT (Xem) toaùn goác vaø ñoái ngaãu, chuùng ta coù theå ruùt ra Ths. Nguyeãn Coâng Trí caùc keát luaän coù giaù trò veà maët toaùn hoïc laãn veà 5. BAØI TAÄP (Xem) Copyright 2001 maët yù nghóa kinh teá. THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU Xeùt baøi toaùn QHTT (P) döôùi daïng chính taéc Goïi g(y) laø haøm muïc tieâu cuûa baøi toaùn (II), ta coù  f P ( x)  c t x  min g(y) = min{ctx + yt(b – Ax)}, vôùi x ≥ 0.  P   Ax  b I   ≤ ctx + yt(b – Ax), vôùi x ≥ 0.  x  0. Vôùi x = (x1, x2,...…, xn)n, b = (b1, b2,...…, bm)m  Neáu x laø P.A cuûa baøi toaùn (I) thì b – Ax = 0 vaø Giaû söû baøi toaùn (P) coù P.A.T.U laø xopt vaø goïi x0 laø g(y) ≤ ctx. Vaäy g(y) laø moät caän döôùi baát kyø cuûa moät P.A cuûa baøi toaùn (P), ta coù ctxopt ≤ ctx0. haøm muïc tieâu. Goïi x = (x1, x2,...…, xn)n, vôùi x ≥ 0 sao cho  Ta tìm caän döôùi lôùn nhaát Max{g(y)}, thaät vaäy Ax – b  0 g(y) = min{ctx + yt(b – Ax)}, vôùi x ≥ 0. Baøi toaùn töông ñöông:  L ( x, y )  c t x  y t  b  Ax   min = min{ctx + ytb – ytAx}, vôùi x ≥ 0.  P   x0  II  = min{ytb + (ct – ytA)x}, vôùi x ≥ 0.  = ytb + min{ (ct – ytA)x}, vôùi x ≥ 0.  y  Rm. 1ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU Xeùt 0 khi c  y A  0 t t Ví duï 2.1.  min  c t  y t A  x    t t Baøi toaùn ñoái ngaãu cuûa baøi toaùn QHTT sau ñaây x0   khi c  y A  0 Vaäy ta ñöôïc ...