Giải bài toán quy hoạch bằng EXCEL

vÝ dô1:
f= X1 - X2 - 2X4 + 2X5 - 3X6 -> MIN *
X1 + X4 + X5 - X6 = 2 1
X2 + X4 + X6 = 12 2
X3 + 2X4 + 4X5 + 3X6 = 9 3
Xj > 0 ; j = 1 -> 6

* Ta cã d¹ng chÝnh t¾c cña quy ho¹ch tuyÕn tÝnh:
f = C1X1+C2X2+C3X3+C4X4+C5X5+C6X6 -> MIN
vËy theo vÝ dô ta cã: C1=1 C3=0 C5=2
C2=-1 C4=-2 C6=-3
"* CB = ( C1, C2,....,CN) trong hµm môc tiªu"
"vËy theo vÝ dô ta cã: hµm môc tiªu chØ cã 3 ph­¬ng tr×nh 1, 2, 3. nªn ta lÊy "
C1=1 C2=-1 C3=0
* Ta cã ®iÒu kiÖn cña d¹ng chÝnh t¾c:
X1+a12X2+a13X3+....+a1mXm+...+a1nXn=b1
X2+a23X3+....+a2mXm+...+a2nXn=b2
X3+....+a3mXm+...+a3nXn=b3
..................................................................
Xn+....+amnXn=bm
Xj >= 0

* ta cã:
3 - 6 = (C1*b1)+(C2*b2)+(C3*b3)
4 - 6 = (C1*a11)+(C2*a21)+(C3*a31) - C1
5 - 6 = (C1*a12)+(C2*a22)+(C3*a32) - C2
6 - 6 = (C1*a13)+(C2*a23)+(C3*a33) - C3
7 - 6 = (C1*a14)+(C2*a24)+(C3*a34) - C4
8 - 6 = (C1*a15)+(C2*a25)+(C3*a35) - C5
9 - 6 = (C1*a16)+(C2*a26)+(C3*a36) - C6
* sau khi tÝnh to¸n ¬ trªn song ta chän « nµo cã gi¸ trÞ d­¬ng cao nhÊt
tõ « ®ã dãng lªn ta ®­îc cét xoay.
"* lÊy lÇn l­ît c¸c ph­¬ng ¸n b1, b2, b3 chia cho c¸c « n»m trªn cét xoay"
chó ý: lÊy c¸c sè th¼ng hµng víi nhau thi chia cho nhau ta ®­îc -0-
*ë cét-0-võa tÝnh ta chän « cã gia trÞ d­¬ng thÊp nhÊt råi dãng sang ta ®­îc dßng xoay
* giao ®iÓm cña cét xoay víi dßng xoay ta ®­îc « trung t©m
* « trung t©m n»m ¬ cét vµ hµng nµo th× ta ®æi vÞ trÝ X t­¬ng øng víi cét thµnh hµng
* ta ®Æt gi¸ trÞ ë cét giao víi hµng cã cïng biÕn X lµ b»ng 1.
c¸c « cïng n»m trªn cét ®ã th× cã gi¸ trÞ b»ng 0

cét kh¸c cét quay cét quay
a b
a`= a-b*c` c`= c/d

c d
dßng quay

Dßng quay= dßng quay cò / phÇn tö quay


STT 1 2 3 4 5 6 7 8 9 10
b¶ng ®¬n h×nh:
1 biÕn c¬ hÖ sè ph­¬ng X1 X2 X3 X4 X5 X6 -0-
2 sè CB ¸n C1=...... C2=...... C3=...... C4=...... C5=....... C6=......
3 X1 C1=...... b1=...... a11=..... a12=...... a13=..... a14=..... a15=.... a16=..... 10-3
4 X2 C2=...... b2=....... a21=..... a22=...... a23=..... a24=..... a25=..... a26=..... 10-4
5 X3 C3=...... b3=....... a31=..... a32=...... a33=..... a34=..... a35=..... a36=..... 10-5
6 B¶ng 1 3-6 4-6 5-6 6-6 7-6 8-6 9-6


STT 1 2 3 4 5 6 7 8 9 10
b¶ng ®¬n h×nh:
1 biÕn c¬ hÖ sè ph­¬ng X1 X2 X3 X4 X5 X6 -0-
2 sè CB ¸n 1 -1 0 -2 2 -3
3 X1 1 2 1 0 0 1 1 -1 2 dßng quay cò
4 X2 -1 12 0 1 0 1 0 1 12
5 X3 0 9 0 0 1 2 4 3 4.5
6 B¶ng 1 -10 0 0 0 2 -1 1
7 X4 -2 0 0 1 dong quay
8 X2 -1 1 0 0
9 X3 0 0 1 0
10 B¶ng 2 0 0 0

STT 1 2 3 4 5 6 7 8 9 10
b¶ng ®¬n h×nh:
1 biÕn c¬ hÖ sè ph­¬ng X1 X2 X3 X4 X5 X6 -0-
2 sè CB ¸n 1 -1 0 -2 2 -3
3 X1 1 2 1 0 0 1 1 -1 2 dßng quay cò
4 X2 -1 12 0 1 0 1 0 1 12
5 X3 0 9 0 0 1 2 4 3 4.5
6 B¶ng 1 -10 0 0 0 2 -1 1
7 X4 -2 2 1 0 0 1 1 -1 -2 dong quay
8 X2 -1 10 -1 1 0 0 -1 2 5
9 X3 0 5 -2 0 1 0 2 5 1
10 B¶ng 2 -14 -2 0 0 0 -3 3
11 X4 -2 0 1 0
12 X2 -1 1 0 0
13 X6 -3 0 0 1
14 B¶ng 3 0 0 0



STT 1 2 3 4 5 6 7 8 9 10
b¶ng ®¬n h×nh:
1 biÕn c¬ hÖ sè ph­¬ng X1 X2 X3 X4 X5 X6 -0-
2 sè CB ¸n 1 -1 0 -2 2 -3
3 X1 1 2 1 0 0 1 1 -1 2
4 X2 -1 12 0 1 0 1 0 1 12
5 X3 0 9 0 0 1 2 4 3 4.5
6 B¶ng 1 -10 0 0 0 2 -1 1
7 X4 -2 2 1 0 0 1 1 -1 -2
8 X2 -1 10 -1 1 0 0 -1 2 5
9 X3 0 5 -2 0 1 0 2 5 1 dßng quay cò
10 B¶ng 2 -14 -2 0 0 0 -3 3
11 X4 -2 3 0.6 0 0.2 1 1.4 0 #DIV/0!
12 X2 -1 8 -0.2 1 -0.4 0 -1.8 0 #DIV/0!
13 X6 -3 1 -0.4 0 0.2 0 0.4 1 1 dong quay
14 B¶ng 3 -17 -0.8 0 -0.6 0 -4.2 0 tÊt c¶ c¸c gi¸ trÞ ®Òu < = 0 nªn ta kÕt thóc v× kh«ng cßn gi¸ trÞ d­¬ng nµo thÊp nhÊt


V¹y ta chän fo = -17 lµm hµm môc tiªu
"ph­¬ng ¸n X2 = ( 0 , 8 , 0 , 3 , 0 , 1 )"
-> tèi ­u