Checking for optimalitySo far we ha

Checking for optimality
So far we have only looked at ways of obtaining an initial basic feasible solution to the
balanced transportation problem. We now develop a method for checking whether the
current basic feasible solution is optimal. For illustrative purposes, we will start with the
initial basic feasible solution that was provided by the North-West Corner method. Usually,
initial basic feasible solutions obtained by the Least-Cost method (or other methods
given in many text-books, such as Vogel’s method) will give better starting configurations.
Suppose that the cost cij of transporting 1 unit from source i to destination j is made up
of a dispatch cost λi and a reception cost µj so that
λi + µj = cij
whenever xij is a basic variable.
Remarks
• The total number of λi and µj variables is n+m. However, there are only n+m−1
basic variables. Thus, we are free to choose one of the λi
’s or µj
’s arbitrarily. It is
usual to set λ1 = 0.
• These “costs” can take negative values if required.
Considering only these dispatch and reception costs, it would cost λi + µj to send 1 unit
from source i to destination j. For (i, j) not corresponding to a basic variable, it will
often be the case that λi + µj 6= cij . In particular, if λi + µj > cij for a particular (i, j)
not corresponding to a basic variable, then there would be a benefit from sending more
goods that way.
So let sij = cij − λi − µj
. The sij values are entered in the top right of the cells. Then
sij is the change in cost due to allocating 1 extra unit to cell (i, j) (in fact it is a shadow
price). If any sij is negative (so that λi + µj > cij ), then the total cost can be reduced
by allocating as many units as possible to cell (i, j). However, if all the sij are positive
then it will be more expensive to change any of the allocations and so we have found a
minimum cost.
Thus the procedure is as follows:
1. Assign values of λi and µj to the columns.
2. Enter the values sij = cij − λi − µj
in every cell.
3. If all the sij ’s are non-negative, we have an optimal solution.
Assigning values of λi and µj to our example with the initial basic feasible solution given
by the North-West Corner method, gives the following transportation tableau:

ผลลัพธ์ (ไทย) 1:

ตรวจสอบ optimalityจนเราได้เพียงมองที่วิธีการแก้ปัญหาเป็นไปได้พื้นฐานการเริ่มต้นการได้รับการปัญหาการขนส่งที่สมดุล ตอนนี้เราพัฒนาวิธีการตรวจสอบว่าการแก้ปัญหาเป็นไปได้เบื้องต้นปัจจุบันเป็นดีที่สุด สำหรับการแสดง เราจะเริ่มต้นด้วยการเริ่มต้นพื้นฐานเป็นไปได้การแก้ปัญหาที่ได้รับวิธี North-West มุม มักจะเริ่มต้นพื้นฐานเป็นไปได้แก้ไขปัญหาได้ โดยวิธีต้นทุนน้อยที่สุด (หรือวิธีการอื่น ๆกำหนดในหลายข้อความหนังสือ เช่นวิธีของโวเกล) จะกำหนดค่าเริ่มต้นที่ดีสมมติว่า cij ต้นทุนขนส่ง 1 หน่วยจากแหล่งเป็น j ปลายขึ้นเป็นของที่จัดส่ง λi ทุนและรับทุน µj ดังนั้นΛi + µj = cijเมื่อใดก็ตาม xij คือ ตัวแปรพื้นฐานหมายเหตุ•จำนวนของตัวแปร λi และ µj มี n + m อย่างไรก็ตาม มีเฉพาะ n + m−1ตัวแปรพื้นฐาน ดังนั้น เรามีอิสระในการเลือก λi การอย่างใดอย่างหนึ่งของ หรือ µjของโดย จึงปกติการตั้งค่า λ1 = 0•เหล่านี้ "ต้นทุน" สามารถใช้ค่าลบถ้าจำเป็นพิจารณาเฉพาะแผนกต้อนรับและจัดส่งต้นทุนเหล่านี้ มันจะมีต้นทุน λi + µj ส่ง 1 ชิ้นจากแหล่งที่เป็นปลายทางเจ สำหรับ (i, j) ไม่สอดคล้องกับตัวแปรพื้นฐาน จะมักเป็นกรณีที่ λi + µj 6 = cij การ ในกรณีเฉพาะ λi + µj > cij สำหรับ (i, j)ไม่สอดคล้องกับตัวแปรพื้นฐาน แล้วจะมีผลประโยชน์จากการส่งเพิ่มเติมสินค้าที่ทางให้ sij = cij − λi − µj. มีป้อนค่า sij ด้านบนขวาของเซลล์ แล้วsij เป็นการเปลี่ยนแปลงในต้นทุนเนื่องจากการปันส่วนหน่วยพิเศษ 1 เซลล์ (i, j) (ในความเป็นจริงมันเป็นเงาราคา) ถ้า sij ใด ๆ เป็นค่าลบ (ดังนั้นที่ λi + µj > cij), จาก นั้นสามารถลดต้นทุนรวมโดยการปันส่วนหน่วยมากที่สุดเซลล์ (i, j) อย่างไรก็ตาม ถ้า sij ทั้งหมดมีค่าเป็นบวกแล้วมันจะเป็นการเปลี่ยนแปลงการปันส่วน และเพื่อ ให้เราได้พบกับต้นทุนที่ต่ำดังนั้น ขั้นตอนจะเป็นดังนี้:1. กำหนดค่า λi และ µj คอลัมน์2. ป้อน sij ค่า = cij − λi − µjในทุกเซลล์3. ถ้าทั้งหมดของ sij ไม่ลบ เรามีโซลูชันเหมาะสมการกำหนดค่าของ λi และ µj อย่างกับการเริ่มต้นพื้นฐานเป็นไปได้แก้ปัญหาให้โดยวิธี North-West มุม ทำให้ฉากการเดินทางต่อไปนี้:

ผลลัพธ์ (ไทย) 2:

ตรวจสอบ optimality
จนถึงขณะนี้เราได้เพียง
แต่มองไปที่วิธีการของการได้รับการแก้ปัญหาที่เป็นไปได้เริ่มต้นขั้นพื้นฐานกับปัญหาการขนส่งที่สมดุล
ตอนนี้เราพัฒนาวิธีการตรวจสอบว่าเป็นปัจจุบันวิธีการแก้ปัญหาที่เป็นไปได้พื้นฐานที่ดีที่สุด
เพื่อเป็นตัวอย่างที่เราจะเริ่มต้นด้วยการแก้ปัญหาที่เป็นไปได้เริ่มต้นขั้นพื้นฐานที่ได้รับจากวิธีการที่มุมตะวันตกเฉียงเหนือ โดยปกติแล้วการแก้ปัญหาที่เป็นไปได้ขั้นพื้นฐานเริ่มต้นได้โดยวิธีอย่างน้อยค่าใช้จ่าย (หรือวิธีการอื่น ๆ ที่ได้รับในหลายข้อความหนังสือดังกล่าวเป็นวิธีการของ Vogel) จะให้การกำหนดค่าเริ่มต้นที่ดีกว่า. สมมติว่า Cij ค่าใช้จ่ายในการขนส่ง 1 หน่วยจากแหล่งที่ผมไปยังปลายทางญ ถูกสร้างขึ้นของค่าใช้จ่ายการจัดส่งλiและค่าใช้จ่ายในการรับสัญญาณμjเพื่อให้λi + μj = Cij เมื่อใดก็ตามที่ xij เป็นตัวแปรพื้นฐาน. หมายเหตุ•จำนวนλiและตัวแปรμjเป็น n + m แต่มีเพียง n + m-1 ตัวแปรพื้นฐาน ดังนั้นเราจึงมีอิสระที่จะเลือกหนึ่งในλi 'หรือμj' s โดยพลการ มันเป็นเรื่องปกติที่จะตั้งλ1 = 0 •เหล่านี้ "ค่าใช้จ่าย" สามารถใช้ค่าลบถ้าจำเป็นต้องใช้. พิจารณาเฉพาะการจัดส่งค่าใช้จ่ายเหล่านี้และรับมันจะเสียค่าใช้จ่ายλi + μjส่ง 1 หน่วยจากแหล่งที่ผมไปยังปลายทางญ สำหรับ (ฉัน j) ไม่สอดคล้องกับตัวแปรพื้นฐานก็จะมักจะเป็นกรณีที่λi + 6 = μj Cij โดยเฉพาะอย่างยิ่งถ้าλi + μj> Cij สำหรับเฉพาะ (ฉัน j) ไม่สอดคล้องกับตัวแปรพื้นฐานแล้วก็จะได้รับประโยชน์จากการส่งมากขึ้น. สินค้าที่ทางดังนั้นขอSIJ = Cij - λi - μj ค่า SIJ จะเข้าไปอยู่ในมุมขวาบนของเซลล์ จากนั้นSIJ คือการเปลี่ยนแปลงในค่าใช้จ่ายที่เกิดจากการจัดสรร 1 หน่วยพิเศษเพื่อเซลล์ (ฉัน j) (ในความเป็นจริงมันเป็นเงาราคา) หาก SIJ ใด ๆ ที่เป็นลบ (เพื่อให้λi + μj> Cij) แล้วค่าใช้จ่ายทั้งหมดจะลดลงโดยการจัดสรรหน่วยมากที่สุดเท่าที่เป็นไปได้ที่มือถือ(ฉัน j) แต่ถ้าทุก SIJ เป็นบวกแล้วมันจะมีราคาแพงมากขึ้นในการเปลี่ยนแปลงการจัดสรรใดๆ และเพื่อให้เราได้พบ. ค่าใช้จ่ายขั้นต่ำดังนั้นขั้นตอนดังต่อไปนี้คือ: 1 การกำหนดค่าของλiและμjเพื่อคอลัมน์. 2 ป้อนค่า SIJ = Cij - λi - μj. ในทุกเซลล์3 . ถ้าทุก SIJ 's จะไม่ลบเรามีทางออกที่ดีที่สุดการกำหนดค่าของλiและμjตัวอย่างของเรามีวิธีการแก้ปัญหาที่เป็นไปได้เริ่มต้นขั้นพื้นฐานที่กำหนดโดยวิธีมุมตะวันตกเฉียงเหนือ, ให้ฉากการขนส่งต่อไปนี้:

ผลลัพธ์ (ไทย) 3:

ตรวจสอบคุณภาพ
จนเราได้ดูแค่วิธีการได้รับการเริ่มต้นพื้นฐานเป็นไปได้โซลูชั่น
ปัญหาการขนส่งที่สมดุล ตอนนี้เราพัฒนาวิธีตรวจสอบว่า
ปัจจุบันพื้นฐานเป็นไปได้โซลูชั่นที่เหมาะสมที่สุด มีรูปประกอบ เราจะเริ่มด้วยการเริ่มต้นพื้นฐานเป็นไปได้
โซลูชันที่ได้รับจากภาคตะวันตกเฉียงเหนือมุมวิธี โดยปกติ
เริ่มต้นพื้นฐานเป็นไปได้โซลูชั่นได้โดยค่าใช้จ่ายอย่างน้อยวิธีการ ( หรือวิธีอื่น
ระบุในหนังสือ หลายข้อความ เช่น โวเจลวิธีการ ) จะให้ดีกว่าเริ่มต้นการตั้งค่า
สมมติว่าต้นทุนของการขนส่ง cij 1 หน่วยจากแหล่งฉันไปยังปลายทาง J ขึ้น
ของส่งต้นทุนและค่าใช้จ่ายµλแผนกต้อนรับ J แล้ว
λผมµ J = cij
เมื่อ xij เป็นตัวแปรพื้นฐาน

หมายเหตุ- จำนวนλฉันและµ J ตัวแปรคือ n เมตร อย่างไรก็ตาม มีเพียง n m − 1
พื้นฐานตัวแปร ดังนั้นเราจึงมีอิสระที่จะเลือกหนึ่งของλผม
และµ J
โดยพลการ มันเป็นปกติที่จะตั้งλ
1 = 0
- " ต้นทุน " สามารถใช้ลบค่าหากต้องการ ส่งและรับ
พิจารณาเฉพาะต้นทุนเหล่านี้จะต้นทุนλผมµ J ส่ง
1 หน่วยจากแหล่งฉันไปยังปลายทาง เจ สำหรับฉันJ ) ไม่สอดคล้องกับตัวแปรพื้นฐาน มันมักจะเป็นกรณีที่จะ
λผมµ J 6 = cij . โดยเฉพาะถ้าλผมµ J > cij สําหรับเฉพาะ ( I , J )
ไม่สอดคล้องกับตัวแปรพื้นฐาน ก็จะได้รับประโยชน์จากการส่งเพิ่มเติม

สินค้านั้น เพื่อให้ sij = cij −−λผมµ J
การ sij คุณค่าเข้าไปในด้านบนขวาของเซลล์ งั้น
sij คือการเปลี่ยนแปลงในค่าใช้จ่ายเนื่องจากการจัดสรร 1 หน่วยพิเศษเซลล์ ( i , j ) ( ในความเป็นจริงมันคือเงา
ราคา ) ถ้า sij เป็นลบ ( ดังนั้นλผมµ J > cij ) แล้วค่าใช้จ่ายทั้งหมดจะลดลง
โดยจัดสรรหน่วยมากที่สุดกับเซลล์ ( I , J ) อย่างไรก็ตาม ถ้าทุก sij บวก
ก็จะแพงกว่าการเปลี่ยนแปลงใด ๆ ของระบบ และเพื่อให้ เราได้เจอ

ราคาต่ำสุดดังนั้น ขั้นตอนมีดังนี้ :
1 กำหนดคุณค่าของλฉันและµ J คอลัมน์ .
2 ใส่ค่า sij = cij −−λผมµ J
ในทุกเซลล์ .
3 ถ้าทั้งหมด sij ' s จะไม่ลบ เรามีโซลูชั่นที่เหมาะสม .
ให้คุณค่าของλฉันและµ J ตัวอย่างของเรากับเริ่มต้นพื้นฐานเป็นไปได้โซลูชั่นให้
โดยภาคตะวันตกเฉียงเหนือมุมให้ฉากการขนส่งวิธีต่อไปนี้ :