Ứng dụng quy hoạch tuyến tính-Mở đầu

Trong thực tế hay gặp tình huống là phải chọn một quyết định (bấp bênh) do phải đối mặt với một đối thủ thông minh và có quyền lợi đối lập với ta : ví dụ trong các trò chơi tranh chấp, trong quân sự, trong vận động tranh cử....

Nghiên cứu việc chọn quyết định trong những trường hợp đối kháng này có tên gọi là lý thuyết trò chơi. Ở đây người chọn quyết định và đối thủ đều được gọi là người chơi. Mỗi người chơi có một tập hợp các hành động để lựa chọn được gọi là chiến lược.

Chúng ta xét một trường hợp đơn giản là trò chơi hai người : phần thưởng sẽ là cái được của một người và chính là cái mất của người kia.

Giải một trò chơi nghĩa là tìm chiến lược tốt nhất cho mỗi người chơi. Hai người chơi thường được ký hiệu là A và B, chiến lược tương ứng của mỗi người được ký hiệu là :

A : i (i=1→m)

B : j (j=1→n)

Giải thưởng ứng với chiến lược (i,j) của hai người được ký hiệu là a_ij và được viết thành một bảng như sau :

Ðối với A :

- Nếu A đi nước 1 (dòng 1) thì A sẽ :

. Thắng 1 điểm nếu B đi nước 1 (thắng)

. Thắng 0 điểm nếu B đi nước 2 (hoà)

. Thắng -2 điểm nếu B đi nước 3 (thua)

. Thắng 1 điểm nếu B đi nước 4 (thắng)

Những trường hợp còn lại là tương tự .

Ðối với B :

- Nếu B đi nước 2 (cột 2) thì B sẽ :

. Thua 0 điểm nếu A đi nước 1

. Thua 2 điểm nếu A đi nước 2

. Thua -1 điểm nếu A đi nước 3

Những trường hợp còn lại là tương tự .

Nghiệm tối ưu của trò chơi, có khi gọi tắt là nghiệm, là bộ chiến lược (i*,j*) có tính chất là nếu một người lấy chiến lược khác còn người kia vẫn giữ nguyên thì phần thưởng cho người đi khác sẽ bị thiệt hại. Giải trò chơi có nghĩa là tìm nghiệm tối ưu.