Tìm một phương án cực biên ban đầu. – Xác định các biến cơ sở xB, các hệ số hàm mục tiêu tương ứng cB. Xác định chỉ số của m biến cơ sở: r(1), r(2), ., r(m). – Tìm ma trận cơ sở B ứng với các cột với chỉ số: r(1), r(2), ., r(m), ma trận nghịch đảo B– | Vx e S pTx a _ T Vx e S2 pTx a H được gọi là tách mạnh strongly S1 và S2 nếu 3s 0 Vx e S PTx a s tvxe S2 p x ia xem hình . H tách không chỉnh S2 Hình . Minh họa các kiểu siêu phẳng tách Siêu phẳng tách một tập lồi và một điểm Định lý 5. Cho tập lồi đóng khác rỗng S c Rn và một điểm y e Rn sao cho y Ể S. Lúc đó tồn tại véc tơ n toạ độ p 0 và a eR sao cho pTy a pTx a Vx e S. Chứng minh Theo định lý 4 ta thấy 3 x e S sao cho x - x T y - x 0 do đó - x T y - x -xT y - x . Mặt khác IIy - x 2 y - x T y - x yT y - x - x T y - x yT y - x - xT y - x yT - xT y - x Hay y - x 2 y - x T y - x y - x T y - x . Đặt p y - x ta có y - x 2 pT y - x từ đó có pTy y - x 2 pTx. Lại đặt a sup pTx x e S thì ta có đpcm pTy a và pTx a Vx e S. Hệ quả 5a. Cho tập lồi đóng khác rỗng S c Rn. Lúc đó S là giao của tất cả các nửa không gian chứa S. Chứng minh Ta chỉ cần chứng minh rằng giao G của tất cả các nửa không gian đóng chứa S là tập con của S. Thật vậy giả sử điều ngược lại tức là 3 y e G sao cho y Ể S. Lúc đó theo định lý 5 trên đây tồn tại một nửa không gian chứa S nhưng không chứa y. Điều này mâu thuẫn với định nghĩa tập G. Hệ quả 5b. Cho tập lồi đóng khác rỗng S c Rn và một điểm y e Rn sao cho y Ể S. Lúc đó luôn tồn tại 140 i Một siêu phẳng tách chặt S và y. ii Một siêu phẳng tách mạnh S và y. iii Véc tơ p sao cho pTy sup pTx x e s . iv Véc tơ p sao cho pT y inf pTx x e s . Việc chứng minh dành cho bạn đọc. Định lý 6 Định lý Farkas . Cho A là ma trận cấp mx n c là véc tơ n toạ độ. Lúc đó chỉ có đúng một trong hai hệ sau có nghiệm ÍAx 0 . _ Hệ 1 t với x là véc tơ thuộc R. Hệ 2 AX cvới y eRm. Giải thích. Cho A 21 1 2 3 và c 4 _4 5 6_ 6 J . Lúc này theo định lý 6 chỉ có đúng một trong hai hệ sau có nghiệm Hệ 1 1 2 3 1 c x x 0 4 5 6 2 0 -1 _x3 _ và 2xi 4x2 6x3 0. Hệ 2 1 4 1 1 2 2 5 4 3 6 1 L y2 J 6 _ và y1 0 y2 0. Chứng minh Giả sử hệ 2 có nghiệm. Lúc đó 3 y 0 sao cho ATy c. Giả sử Ax 0 ta có cTx yTAx 0 do yT 0 và Ax 0 . Vì vậy hệ 1 vô nghiệm. Giả sử hệ 2 vô nghiệm. Đặt S x x à y y
