8-10 (High school
busing problem) The Arden County, Maryland, superintendent of education is
responsible for assigning students to the three high schools in his county. He
recognizes the need to bus a certain number of students, for several sectors of
the county are beyond walking distance to a school. The superintendent
partitions the county into five geographic sectors as he attempts to establish
a plan that will minimize the total number of student miles traveled by bus. He
also recognizes that if a student happens to live in a certain sector and is
assigned to the high school in that sector, there is no need to bus that
student because he or she can walk to school. The three schools are located in
sectors B, C, and E. The following table reflects the number of high school-age
students living in each sector and the distance in miles from each sector to
each school:
Each high school has a capacity of 900 students.
Set up the objective function and constraints of this problem using LP so that
the total number of student miles traveled by bus is minimized. (Note the
resemblance to the transportation problem illustrated earlier in this chapter.)
Then solve the problem.
Optimize function
min miles = 5XAB + 8XAC + 6XAE + 4XBC
+12XBE +4XCB + 7XCE + 7XDB +2XDC
+5XDE +12XEB
+ 7XEC
+ 7XEC
XAB
= จำนวนนักเรียนที่จะต้องเดินทางโดยรถบัสจาก Sector A ไป School in sector B
XAC = จำนวนนักเรียนที่จะต้องเดินทางโดยรถบัสจาก
Sector A ไป School in sector C
XAE = จำนวนนักเรียนที่จะต้องเดินทางโดยรถบัสจาก
Sector A ไป School in sector E
XBC = จำนวนนักเรียนที่จะต้องเดินทางโดยรถบัสจาก
Sector B ไป School in sector C
XBE = จำนวนนักเรียนที่จะต้องเดินทางโดยรถบัสจาก Sector B ไป
School in sector E
XCB = จำนวนนักเรียนที่จะต้องเดินทางโดยรถบัสจาก Sector C ไป
School in sector B
XCE = จำนวนนักเรียนที่จะต้องเดินทางโดยรถบัสจาก Sector C ไป
School in sector E
XDB = จำนวนนักเรียนที่จะต้องเดินทางโดยรถบัสจาก Sector D ไป
School in sector B
XDC = จำนวนนักเรียนที่จะต้องเดินทางโดยรถบัสจาก Sector D ไป
School in sector C
XDE = จำนวนนักเรียนที่จะต้องเดินทางโดยรถบัสจาก Sector D ไป
School in sector E
XEB = จำนวนนักเรียนที่จะต้องเดินทางโดยรถบัสจาก Sector E ไป
School in sector B
XEC = จำนวนนักเรียนที่จะต้องเดินทางโดยรถบัสจาก Sector E ไป
School in sector C
constraint
XAB+ XAC+
XAE
= 700
XBC+
XBE
= 500
XCB+ XCE
= 100
XDB+ XDC+
XDE
= 800
XEB+ XEC
= 400
XAB+ XCB+
XDB+
XEB ≤ 900
XAC+
XBC+
XDC+
XEC ≤ 900
XAE+
XBE+
XCE+
XDE ≤ 900
|
8-10. (High school
busing problem)
|
|||||||||||||||
|
min
|
|||||||||||||||
|
verible(Decision
verible)
|
XAB
|
XAC
|
XAE
|
XBC
|
XBE
|
XCB
|
XCE
|
XDB
|
XDC
|
XDE
|
XEB
|
XEC
|
objective funtion
|
||
|
ระยะทางที่รถบัสจะดินทางไป
|
700
|
0
|
0
|
500
|
0
|
100
|
0
|
0
|
0
|
800
|
0
|
400
|
12700
|
||
|
distance to school
|
5
|
8
|
6
|
4
|
12
|
4
|
7
|
7
|
2
|
5
|
12
|
7
|
|||
|
constraints
|
LHS
|
RHS
|
|||||||||||||
|
c1
|
1
|
1
|
1
|
|
|
|
|
|
|
|
|
|
700
|
=
|
700
|
|
c2
|
|
|
|
1
|
1
|
|
|
|
|
|
|
|
500
|
=
|
500
|
|
c3
|
|
|
|
|
|
1
|
1
|
|
|
|
|
|
100
|
=
|
100
|
|
c4
|
|
|
|
|
|
|
|
1
|
1
|
1
|
|
|
800
|
=
|
800
|
|
c5
|
|
|
|
|
|
|
|
|
|
|
1
|
1
|
400
|
=
|
400
|
|
c6
|
1
|
|
|
|
|
1
|
|
1
|
|
|
1
|
|
800
|
<=
|
900
|
|
c7
|
|
1
|
|
1
|
|
|
|
|
1
|
|
|
1
|
900
|
<=
|
900
|
|
c8
|
|
|
1
|
|
1
|
|
1
|
|
|
1
|
|
|
800
|
<=
|
900
|
ดังนั้น
จำนวนนักเรียนที่จะต้องเดินทางโดยรถบัสจาก
Sector
A ไป School in sector B เท่ากับ 700
จำนวนนักเรียนที่จะต้องเดินทางโดยรถบัสจาก Sector B ไป School in sector C เท่ากับ 500
จำนวนนักเรียนที่จะต้องเดินทางโดยรถบัสจาก Sector C ไป School in sector B เท่ากับ 100
จำนวนนักเรียนที่จะต้องเดินทางโดยรถบัสจาก Sector D ไป School in sector E เท่ากับ 800
จำนวนนักเรียนที่จะต้องเดินทางโดยรถบัสจาก Sector E ไป School in sector C เท่ากับ 400
ซึ่งจะทำให้ระยะทางในการเดินทางของรถบัสต่ำสุดคือ
12700 ไมล์
