Знаходимо опорний план транспортної задачі, використовуючи метод північно-західного (лівого верхнього) кута

Визначаємо тип транспортної задачі.

Сума запасів а₁+ а₂+ а₃ = 85 + 35 + 20 =140, а потреб b₁+ b₂+ b₃+ b₄ = 10 + 65 + 85 + 50 = 210, тому маємо відкриту ТЗ у якій потреби в пунктах призначення більші за наявність вантажу.. Необхідно в умову задачі ввести додаткового фіктивного постачальника з таким обсягом запасів, на який більший попит: а₄ = ∑b_j - ∑a_i = 210 – 140 =70. Будемо вважати, що вартість перевезення від фіктивного постачальника велика, що означає блокування цих фіктивних маршрутів. Позначимо вартість цих перевезень через М. Вартості усіх інших перевезень від фіктивного постачальника будемо вважати нульовими (табл. 3).

В оптимальному розв’язку нашої задачі потреби визначених споживачів будуть задоволені реальними постачальниками.

Таблиця 3.

Наявність вантажу аі	Потреби в пунктах призначення bj
	М

Отримали закриту ТЗ, яка має розв’язок.

В отриманій закритій ТЗ число пунктів відправлення m=4, а число пунктів призначення n=4. Опорним (базисним) планом ТЗ є план, у якому ненульовими є рівно (m + n – 1) змінна. Таким чином, у табл.3 повинно бути 4 + 4 – 1 = 7 ненульових змінних. Клітини у яких x_ij ≠ 0 – базисні, решта – вільні. Якщо надалі при перетворенні таблиці звільняється більш як одна клітина, то одна з них переходить в число вільних, а в решту записується о і вони вважаються базисними.

Заповнення табл.3 починаємо з клітин для невідомого х₁₁, тобто спробуємо задовольнити потреби першого пункту призначення за рахунок запасів першого пункту відправлення. Через те, що запаси пункту а ₁ більші за потреби пункту b ₁, то покладемо х₁₁ = 10, записуємо це значення в відповідній клітинці табл.4 і тимчасово виключаємо із розгляду стовпчик b ₁, вважаючи при цьому запаси пункту а ₁ рівними 85 – 10 = 75.

Розглядаємо перші із тих, що залишилися, пункти відправлення а ₁ та призначення b ₂. Запаси пункту а ₁ знову більші за потреби пункту b ₂. Покладемо х₁₂ = 65, запишемо це значення у відповідній клітинці табл. 4 і тимчасово виключимо із розгляду стовпчик b₂, вважаючи запаси пункту а ₁ рівними 75 – 65 = 10. Знову розглядаємо пункти, перші із тих, що залишилися, - пункти відправлення а ₁ та призначення b ₃. Запаси пункту а ₁ менші за потреби пункту b ₂, тому покладемо х ₁₃ = 10 та виключаємо із розгляду рядок а ₁ (запаси вичерпалися), при цьому потреби в пункті b ₂ = 85 – 10 = 75.

Тепер переходимо до заповнення клітинки для невідомого х₂₃. Запасів в пункті а ₂ = 35 недостатньо, щоб задовольнити потреби пункту призначення b ₃, тому заповнюємо клітинку х₂₃ = 35 і виключаємо з розгляду рядок а _2. Поступово переходимо до заповнення невідомих х₃₃ = 20 та х₃₄ = 20. На сьомому кроці залишається фіктивний пункт відправлення а ₄ з запасом 50 од. і пункт призначення b ₄ з потребами, що залишились, в 50 од. Відповідно, маємо і одну клітинку, яку і заповнюємо, поклавши х ₄₄ = 50.

Таблиця 4.

Наявність вантажу аі	Потреби в пунктах призначення bj
	М

В табл. 4 записаний опорний план, у якому потреби споживачів задоволені реальними постачальниками (останній рядок опорного плану – фіктивний, тому не будемо його заносити в матрицю):

Витрати С на перевезення для даного опорного плану становлять:

С = 10*7+65*4+10*6+35*6+20*1 = 620 ум. од.

Дата добавления: 2014-10-15