Giáo trình phương pháp tối ưu trong kinh doanh

JƠNG ĐẠI HỌC KINH TẼ QUÕC DẦN

3T.0000018430 IỎN QUẢN TRỊ KINH DOANH TổNG Hựp

NHA XUẤT BẢN ĐẠI HỌC KINH TẾ QUỐC DÂN

N H A X U A I BA

NHA XƯ A! £*.: i',.i

NHA XU A ! BAM rJAl Htic:

TRƯỜNG ĐẠI HỌC KINH TỂ QUỐC DÂN

B ộ MÔN QUẢN TRỊ KINH DOANH TổNG HỢP

TS. TRẦN VIỆT LÂM

Giáo trình

PHƯƠNG PHÁP TỐI ƯU

TRONG KINH DOANH

DẠI HỌC THÁI NC jYEN

TRUNGT aF h QC LiẸU

NHÀ XUẤT BẢN ĐẠI HỌC KINH TỂ QUỐC DÂN

HẦ Nộ i - 2009

Giáo trình Phương pháp tối ưu trong kinh doanh

Tác giả: TS. Trần Việt Lâm

© Đại học Kinh tế quốc dân giữ bản quyền

Cấm mọi hành vi sao chép, in ấn một phần hoặc toàn bộ xuất ban

phâm khi không được sự cho phép của Đại học Kinh tế quốc dân.

Theo dõi bản thào: Thạc sì Nguyễn Anh Tú

LỜI NÓI ĐẦU

Lý thuyết tối ưu là một lĩnh vực của toán học

ứng dụng ra đời vào những năm 40 của thế kỷ 20.

Ngay từ khi mới ra đời, Lý thuyết tối ưu đã có nhiều

dụng trong kinh tế, kỹ thuật và quốc phòng.

Giáo trình Phương pháp tối ưu trong kinh

doanh được hình thành sau nhiều năm giảng dạy môn

học này cho sinh viên và học viên cao học chuyên

ngành Quản trị kinh doanh tổng hợp. Mục tiêu của

giáo trình là trình bày những phương pháp tối ưu tiêu

biểu, có nhiều ứng dụng để hỗ trợ các nhà quản trị ra

quyết định trong kinh doanh. Với thời lượng là 3 đơn

vị học trình, giáo trình tập trung vào việc sử dụng bài

toán tối ưu để mô hình hoá các vấn đề từ thực tiễn

kinh doanh, thuật toán giải các bài toán tối ưu điển

hình và việc sử dụng kết quả từ lời giải bài toán tối ưu

để hỗ trợ việc ra quyết định kinh doanh. Các tính chất

toán học của bài toán tối ưu được trình bày vừa đủ để

người đọc nắm được thuật toán, không chứng minh,

tuy nhiên người đọc có thể tìm hiểu những chứng

minh này trong các tài liệu tham khảo.

Giáo trình bao gồm 6 chương. Chương 1 giới

thiệu khái quát về Lý thuyết quyết định, lý thuyết tối

ưu và các vấn đề chính mà lý thuyết tối ưu quan tâm

giải quyết trong kinh doanh. Chương 2 trình bày bài

toán quy hoạch tuyến tính, chương 3 trình bày bài

toán vận tải là những bài toán tối ưu có rất nhiều ứng

dụng trong hoạt động kinh doanh. Chương 4 trình

bày bài toán sản xuất đồng bộ một bài toán tối ưu có

3

nhiều ựng dụng trong quản trị sản xuất. Chương 5

trình bày một số' bài toán tối ưu trên đồ thị và ứng

dụng của các bài toán này trong quản trị dự án.

Chương 6 trình bày bài toán trò chơi ma trận, một

trường hợp đơn giản của Lý thuyết trò chơi nhằm

giúp cho học viên có cái nhìn mới về cạnh tranh

trong nền kinh tế thị trường. Trong mỗi chương,

ngoài việc trình bày những kiến thức toán học cần

thiết, thuật toán giải bài toán tối ưu, giáo trình tập

trung trình bày việc khai thác ứng dụng các phương

pháp tối ưu để giải quyết những vấn đề trong kinh

doanh. Cuối mỗi chương đều có những câu hỏi để

học viên có thể hệ thống những vấn đề lý thuyết và

các bài tập để học viên rèn luyện kỹ năng. Các vấn

đề được trình bày đơn giản, dễ hiểu phù hợp với

những kiến thức toán học mà sinh viên Trường Đại

học Kinh tế quốc dân được trang bị.

Tác giả xin trân trọng cảm ơn GS.TSKH. Nguyễn

Quang Thái (Bộ Kế hoạch và Đầu tư), PGS.TS. Trần

Thọ Đạt (Trường Đại học Kinh tế quốc dân) đã dành

thời gian đọc bản thảo và đóng góp ý kiến về nội

dung cuốn sách. Tác giả xin chân thành cảm ơn

PGS.TS. Lê Công Hoa, Trường Khoa Quản trị kinh

doanh, PGS.TS. Nguyễn Ngọc Huyền và các thầy, cỏ

giáo Bộ môn Quản trị kinh doanh tổng hợp, Trường

Đại học Kinh tế quốc dân đã động viên khích lệ. tạo

điều kiện để tác giả biên soạn giáo trình này.

Do thời gian và kinh nghiệm còn hạn chế, giáo

trình chắc chắn không tránh khỏi những thiếu sót.

Tác giả rất mong nhận được ý kiến đóng góp cùa

bạn đọc để có thể hoàn thiện giáo trình.

Chương 1

CÁC BÀI TOÁN TỐI ƯU

TRONG VIỆC RA QUYẾT ĐỊNH KINH DOANH ■ ■

1.1. QUYẾT ĐỊNH TRONG KINH DOANH VÀ LÝ THUYẾT

QUYẾT ĐỊNH

1.1.1. Quyết định trong kinh doanh

Một quyết định là một phương án được lựa chọn trong số

các phương án hiện có. Nhà quản trị ở tất cả các cấp của một tổ

chức phải ra quyết định để giải quyết vấn đề. Có thể nói, thực

chất của hoạt động quản trị là việc ra các quyết định. Ra quyết

định là tiến trình xác định vấn đề, phân tích, so sánh và đi đến

lựa chọn phương án để giải quyết vấn đề đặt ra. Có nhiều cách

khác nhau để phân loại quyết định trong kinh doanh.

Quyết định tốt và quyết định không tốt

Quyết định tốt là quyết định được đưa ra trên cơ sở phân

tích logic, xem xét đầy đủ, toàn diện các vấn đề liên quan, xử lý

tối đa các thông tin số liệu thu thập được, đánh giá và so sánh

các phương án có thể lựa chọn để ra quyết định. Cần lưu ý là

một quyết định tốt vẫn có thể dẫn đến những kết quả không tốt,

nhưng nếu việc ra quyết định tuân thủ những yêu cầu như đã nêu

thì quyết định đó vẫn được coi là quyết định tốt.

Quyết định không tốt là quyết định được đưa ra không dựa

trên việc phàn tích logic, dựa vào chủ quan của người ra quyết

định, không phân tích, xử lý những thông tin thu thập được,

không đánh giá, so sánh các phương án có thể lựa chọn. Cũng

cần lưu ý là một quyết định không tốt vẫn có thể đưa đến những

kết quả tốt, nhưng nếu việc ra quyết định mang những đặc trưng

5

như đã nêu trên thì quyết định đó vẫn được coi là quyết định

không tốt.

Quyết định hàng ngày, quyết định thích nghi và quyết

định đổi mới

Quyết định hàng ngày là quyết định đã có tiêu chuẩn cho

việc lựa chọn, đã có quy tắc, thủ tục hành động chuẩn cho các

giải pháp thực hiện. Quyết định hàng ngày thường gắn với công

việc của nhà quản trị cấp cơ sở và gắn với những vấn đề cụ thể,

rõ ràng. Những quyết định về xử lý đơn hàng, thanh toán các

biên lai trả tiền, bảo dưỡng và sửa chữa máy móc thiết bị,...thuộc

loại quyết định hàng ngày.

Quyết định thích nghi là quyết định đưa ra sự lựa chọn để

đáp ứng một tập hợp vấn đề và giải pháp thực hiện mới chỉ biết

rõ một phần. Quyết định nhằm hợp lý hoá quy trình sản xuất,

điều chỉnh các hoạt động nhằm giảm chi phí,...là những quyết

định thích nghi. Quyết định thích nghi thường gắn với công việc

của nhà quản trị cấp trung gian và quyết định thích nghi thường

dẫn tới những thay đổi dần về tiêu chuẩn lựa chọn, quy tắc hành

động của quyết định hàng ngày.

Quyết định đổi mới là quyết định cho những vấn đề mới

được khám phá, phát hiện và chẩn đoán, đòi hỏi phải có những

giải pháp thực hiện độc đáo, sáng tạo. Quyết định đổi mới

thường bao gồm nhiều những quyết định nhỏ, diễn ra trong một

khoảng thời gian dài, liên quan đến nhiều bộ phận, nhiều cá

nhân trong tổ chức. Quyết định đưa một sản phẩm mới ra thị

trường, quyết định về một thị trường mục tiêu,... là những quyết

định đổi mới. Quyết định đổi mới thường gắn với công việc của

nhà quản trị cao cấp.

Quyết định được xây dựng chương trình và quyết định

không được xày dựng chương trình

Quyết định được xây dựng chương trình là quyết định được

đưa ra phù hợp với những quy tắc hay là những thủ tục chính

6

thức nào đó. Mỗi một tổ chức có những nguyên tắc thành văn

hay không thành vãn tạo điều kiện thuận lợi cho việc ra quyết

định trong những tình huống được lặp lại, nhờ đó hạn chế số khả

nãng lựa chọn. Ví dụ, nhà quản trị ra quyết định mức lương cho

một lao động mới tuyển dụng. Đây là một quyết định đã được

xây dựng chương trình bởi vì doanh nghiệp đã có thang lương,

bảng lương cho tất cả các vị trí công việc trong doanh nghiệp.

Quyết định mức dự trữ một loại sản phẩm xác định mặc dù phải

thu thập, xử lý một khối lượng lớn thông tin, tiến hành nhiều dự

báo song vẫn được coi là quyết định đã được xây dựng chương

trình. Lý do là vì khi giải quyết những yếu tố riêng lẻ của vấn đề

xác định mức dự trữ một loại sản phẩm chúng ta phải ra nhiều

quyết định đã được xây dựng chương trình. Ở một mức độ nhất

định, quyết định đã được xây dựng chương trình sẽ hạn chế sự tự

do của người ra quyết định nhưng nhờ đó giảm bớt gánh nặng,

tiết kiệm thời gian cho người ra quyết định khi tìm kiếm lời giải

mới cho các vấn đề cũ.

Quyết định không được xây dựng chương trình là quyết định

cho những vấn đề không thông thường hoặc rất ít khi lặp lại. Đó

cũng có thể là những vấn đề rất quan trọng, có những yêu cầu

riêng khi ra quyết định. Ví dụ quyết định liên quan đến việc

phân chia những nguồn lực khan hiếm của doanh nghiệp hay

quyết định liên quan đến tương lai của những sản phẩm không

đáp ứng được mong đợi của doanh nghiệp. Nhà quản trị ở cấp

càng cao phải đảm nhận càng nhiều việc ra những quyết định

không được xây dựng chương trình.

Q uyết định trong điều kiện chắc chắn, quyết định trong

điều kiện có rủi ro và quyết định trong điều kiện không chắc

chắn

Quyết định trong điều kiện chắc chắn là quyết định được

đưa ra trong điều kiện chúng ta đã biết được những khả năng sẽ

xảy ra trong tương lai, tức là chúng ta có thể dựa trên những

7

thông tin cụ thể, đáng tin cậy, đo lường được để ra quyết định.

Quyết định trong điều kiện có rủi ro là quyết định được đưa

ra trong điều kiện chúng ta biết được xác suất xảy ra mỗi một

khả nãng trong tương lai. Mặc dù không có được những thông

tin đầy đủ về kết quả nhưng chúng ta có thể đánh giá xác suất

nhận được những kết quả riêng biệt khi ra quyết định.

Quyết định trong điều kiện không chắc chắn là quyết định

được đưa ra trong điều kiện chúng ta không biết được xác suất

xảy ra mỗi một khả năng, thậm chí chúng ta không biết được có

những khả năng nào sẽ xảy ra trong tương lai.

1.1.2. Lý thuyết quyết định

Hiện nay chưa có một định nghĩa thống nhất về lý thuyết

quyết định. Một cách chung nhất có thể hiểu lý thuyết quyết

định là lý thuyết nghiên cứu các cách tiếp cận có phân tích, có

hệ thống việc ra quyết định. Kết quả cuối cùng của việc sử dụng

lý thuyết quyết định là những thông tin trực tiếp giúp đỡ, tạo

điều kiện dễ dàng cho chủ thể ra quyết định.*Trong kinh doanh

chủ thể ra quyết định chính là những nhà quản trị. Các kết luận

của lý thuyết quyết định chỉ đóng vai trò định hướng cho việc ra

quyết định, các kết luận này chỉ được thực thi khi nhà quản trị

chấp nhận.

Mặc dù chưa có được một định nghĩa thống nhất song hầu

hết các nhà nghiên cứu đều thống nhất cho rằng lý thuyết quyết

định có những đặc trưng cơ bản sau:

(1). S ử dụng cách tiếp cận hệ thống là đặc trưng đầu tiên

của lý thuyết quyết định. Hệ thống là một thực thể gồm nhiều

yếu tố, bộ phận hợp thành. Các yếu tố, các bộ phận này có quan

hệ tương tác lẫn nhau và với môi trường xung quanh một cách

có quy luật để tạo thành một thực thể thống nhất nhằm thực hiện

một số chức năng hoặc mục tiêu nhất định. Tiếp cận hệ thống có

nghĩa là khi nghiên cứu, đề xuất quyết định về một vấn đề thì

vấn đề đó cần được xem xét nghiên cứu trong toàn bộ hệ thống,

l

8

toàn bộ tổ chức chứ không thể nghiên cứu vấn đề đó một cách

riêng rẽ, biệt lập. Và bản thân vấn đề nghiên cứu cũng được xem

là một hệ thống, tức là nó được cấu thành bởi nhiều bộ phận,

nhiều vấn đề nhỏ hơn có quan hệ tương tác lẫn nhau. Tiếp cận

hệ thống là tiếp cận theo mô hình, tức là chúng ta giải quyết vấn

đề dựa trên mô hình của thực tại chứ không phải dựa vào chính

bản thân thực tại. Tiếp cận hệ thống là tiếp cận theo các mối

quan hệ tương quan, các mối quan hệ nhân-quả, nếu-thì. Và tiếp

cận hệ thống cũng là tiếp cận động tức là các vấn đề được quan

sát, nghiên cứu theo thời gian để từ đó phát hiện sự phát triển

trong tương lai.

(2). Làm việc tập th ể là một đặc trưng của lý thuyết quyết

định. Các vấn đề lý thuyết quyết định quan tâm giải quyết

thường khó và phức tạp, đòi hỏi sự tham gia của nhiều chuyên

gia thuộc các lĩnh vực khác nhau. Các chuyên gia đó có thể là

các nhà thống kê, các nhà kinh tế, các nhà tâm lý học, các nhà

quản lý,... và họ phải liên kết với nhau thành một tập thể làm

việc. Các thành viên của tập thể phụ thuộc vào nội dung của vấn

đề cần quyết định.

(3). S ử dụng các phương pháp khoa học cũng là một đặc

trưng quan trọng của lý thuyết quyết định. Lý thuyết quyết định

sử dụng các mô hình toán học để mô hình hoá, mô tả các vấn đề

cần giải quyết, sử dụng các phương pháp, các công cụ toán học

để phân tích cấu trúc và hành vi của hệ thống, sử dụng máy tính

với các phần mềm trợ giúp để tìm lời giải dựa theo các mô hình

toán học đã xây dựng.

1.1.3. Phương pháp lựa chọn quyết định

Phương pháp sử dụng bảng

Bảng ra quyết định CÒI1 được gọi là bảng kết toán . Bảng này

liệt kê tất cả các tình huống Yj ( j = 1,2,...,«) có thể xảy ra, các

quyết định X , (i = mà người ra quyết định có thể lựa

9

chọn và thu nhập au khi người ra quyết định lựa chọn quyết

định X, mà xảy ra tình huống Y j.

Bảng l. Bảng kết toán lựa chọn quyết định

lựa chọn quyết định cho mình.

(1). Tiêu chuẩn M aximin là tiêu chuẩn dành cho những

người thận trọng khi ra quyết định. Người ra quyết định cho

rằng khi lựa chọn quyết định X ' thì tối thiểu họ cũng có được

thu nhập là Min au ( j = 1,2,...,« ). Do được quyền lựa chọn 1

trong m quyết định là X ị , X ĩ ,...,X m nên người ra quyết định

sẽ lưa chon quyết đinh theo tiêu chuẩn Max Min a

1 J 9

(/' = 1,2,.=1,2,.

(2). Tiêu chuẩn M inim ax là tiêu chuẩn dành cho những

người thường hối tiếc khi ra quyết định. Khi lựa chọn quyết

định X , , xảy ra tình huống Y người ra quyết định có được thu

nhập aIJ và mức độ hối tiếc của người ra quyết định sẽ là

aụ = Max ay - aụ . Người ra quyết định chấp nhận sự hối tiếc

lớn nhất khi lưa chon quyết đinh X, là Max a; ( j = 1,2,...,/7)

J

/

i

Do được quyền lựa chọn 1 trong m quyết định là

X i, X 2,.. . , X m nên người ra quyết định sẽ lựa chọn quyết định

theo tiêu chuẩn Min Max a' (/ = 1,2,..., m; j = 1,2,..., n ).

' J

(3). Tiêu chuẩn M axim ax là tiêu chuẩn dành cho những

người rất lạc quan khi lựa chọn quyết định. Tiêu chuẩn lựa chọn

quyết định ở đây là Max Max a .

I J

(4). Tiêu chuẩn cực đại giá trị hiện thực (tiêu chuẩn

Hurwicz) là tiêu chuẩn dựa vào mức độ lạc quan của người ra

quyết định. Ở thời điểm ra quyết định người ra quyết định sẽ xác

định cho mình hệ số a (o < a < l) đánh giá mức độ lạc quan

của mình khi ra quyết định. Nếu a - 1, người ra quyết định

hoàn toàn lạc quan khi lựa chọn quyết định. Nếu a = 0, người

ra quyết định hoàn toàn bi quan khi lựa chọn quyết định.

Với mỗi một quyết định X , người ra quyết định xác định

h = a . M axa + ( ỉ - a ) . M ina . Do được quyền lựa chọn 1

J J

trong m quyết định là X ị , X 2,. . . , X m nên người ra quyết định

sẽ lựa chọn quyết định theo tiêu chuẩn Max h, (/■ = 1,2,..., m ). /

(5). Tiêu chuẩn giá trị kỳ vọng lớn nhất là tiêu chuẩn được

sử dụng trong trường hợp người ra quyết định có thể đánh giá

được xác suất xảy ra mỗi một tình huống khi lựa chọn quyết định.

Gọi P j là xác suất xảy ra tình huống Y j , rõ ràng 1 ằ Pj > 0 và

= 1. Khi lựa chọn quyết định X ' , kết quả mà người ra

7=1

n

quyết định hy vọng thu được là E M V {X Ỉ ) = ' ỵ ^ a IJ ■ P J . Do được

7=1

quyền lựa chọn 1 trong m quyết định là X Ì, X 2,. . . , X nên

11

người ra quyết định sẽ lựa chọn quyết định theo tiêu chuẩn Max

E M V ự ,) (i =

Ví dụ

Một doanh nghiệp trong quý có 3 phương án sản xuất sản

phẩm để tiêu thụ trên thị trường: giữ nguyên loại sản phẩm cũ,

khác biệt hoá sản phẩm và sản xuất loại sản phẩm mới. Lợi

nhuận thu được của mỗi một phương án (đơn vị là triệu đồng)

phụ thuộc vào nhu cầu của thị trường và mức độ cạnh tranh giữa

các doanh nghiệp cùng sản xuất và tiêu thụ sản phẩm trên thị

trường. Qua điều tra đánh giá doanh nghiệp thu được bảng kết

toán sau làm cơ sở cho việc ra quyết định:

Tình huống Nhu cẩu thấp Nhu cẩu cao

Quyết định

Cạnh tranh

tăng (Y1)

Cạnh tranh

giảm (Y2)

Cạnh tranh

tâng (Y3)

Cạnh tranh

giảm (Y4)

Giữ nguyên sản phẩm cũ (X1) -20 15 10 35

Khác biệt hoá sản phẩm (X2) -10 20 5 40

Sản xuất sản phẩm mới (X3) 5 -15 15 50

Xác suất (P) 0,2 0,1 0,5 0,2

- Tiêu chuẩn Maximin

+ Nếu lựa chọn quyết định X I, min a,j = -20

+ Nếu lựa chọn quyết định X2, min a2j = -10

+ Nếu lựa chọn quyết định X3, min a 3j = -15

Như vây, Max Min a = -10, theo tiêu chuẩn Maximin

' J

doanh nghiệp sẽ lựa chọn quyết định X2 tức là tiến hành khác

biệt hoá sản phẩm.

- Tiêu chuẩn Minimax

+ Nếu lựa chọn quyết định XI mức độ hối tiếc lớn nhất là

Max a |J = 35 - (-20) = 55

12

I

+ Nếu lựa chọn quyết định X2 mức độ hối tiếc lớn nhất là

Max a'2j = 40 - (-10) = 50

+ Nếu lựa chọn quyết định X3 mức độ hối tiếc lớn nhất là

Max a ,j = 50 - (-15) = 65.

Như vây, Min M ax a ’ = 50, theo tiêu chuẩn Minimax

i j

doanh nghiệp sẽ lựa chọn quyết định X2 tức là tiến hành khác

biệt hoá sản phẩm.

- Tiêu chuẩn Maximax

+ Nếu lựa chọn quyết định XI kết quả lớn nhất thu được là

Max a,j = 35

+ Nếu lựa chọn quyết định X2 kết quả lớn nhất thu được là

Max a2j = 40

+ Nếu lựa chọn quyết định X3 kết quả lớn nhất thu được là

Max a3j = 50.

Như vậy, Max Max a = 50, theo tiêu chuẩn Maximax

i J

doanh nghiệp sẽ lựa chọn quyết định X3 tức là tiến hành sản

xuất sản phẩm mới.

- Tiêu chuẩn cực đại giá trị hiện thực

Giả sử khi lựa chọn quyết định hệ số lạc quan của doanh

nghiệp là 0,7.

+ Nếu lựa chọn quyết định XI giá trị hiện thực của kết quả

thu được là

h, = 0,7.35 + 0,3.(-20) = 18,5

+ Nếu lựa chọn quyết định X2 giá trị hiện thực của kết quả

thu được là

h2 = 0 ,7.40+ 0,3.(-10) = 25

+ Nếu lựa chọn quyết định X3 giá trị hiện thực của kết quả

thu được là

h, = 0,7.50 + 0,3.(-15) = 30,5.

13