Метод потенціалів розв’язання транспортної задачі

Нульова ітерація транспортної задачі. Підготуємо таблицю (табл. 3.3). Другий рядок і другий стовпець зарезервуємо для значень потенціалів. В останній стовпець внесемо відповідні значення запасів, а в останній рядок – потреб. У праві верхні кути комірок (, ) внесемо матрицю транспортних витрат.

Таблиця 3.3 ‑ Нульова ітерація транспортної задачі

						Запаси
		1	1	1	1
	0													30|0
-2						-3			-1
	0													20|0
			-3			-2			-2
	3													40|20|0
										Ө
	-1													10|0
	Ө
0
Потреби	20	30	20	30 20

Крок 1. Побудову вихідного опорного плану здійснюємо методом найменшої вартості. Завантажуючи комірки, відповідні значення обсягів перевезення будемо заносити в нижні ліві кути комірок (, ).

1. Вибираємо комірку з найменшою вартістю (транспортним тарифом). Найменша вартість дорівнює 0, а комірок, що відповідають цій вартості ‑ чотири: , , , . Завантажимо, наприклад, комірку так, щоб . Перерахуємо запаси, що залишилися, =10‑10=0, і потреби, що залишилися, =30‑ ‑10=20, а отримані значення запишемо у відповідних комірках таблиці через риску.

2. Оскільки запаси четвертого пункту виробництва вичерпані, то завантажувати комірки рядка поки не будемо. Серед комірок, що залишилися, виберемо комірку з найменшою вартістю. Маємо дві комірки з вартістю 1. Завантажимо спочатку, наприклад, комірку : . Перерахуємо запаси, що залишилися, і потреби, що залишилися, =30‑30=0. Потім завантажимо комірку : , 20‑20=0, =20‑ ‑20=0.

3. На даний момент вичерпані запаси пунктів виробництва , і , а також задоволені потреби споживачів і . У нашому розпорядженні залишилися дві комірки з однаковими вартостями: і . Завантажимо, наприклад, комірку : , , =20‑20=0. Тепер завантажимо
комірку : , , =20‑20=0.

4. Завантажені комірки відповідають базисним змінним транспортної задачі, їхня кількість на даний момент дорівнює 5, однак, як було відзначено вище, повинна дорівнювати 7. Два відсутні елементи поповнюємо, завантажуючи нульовим обсягом перевезення дві вільні комірки з найменшими тарифами. Причому необхідно подбати про те, щоб жодна з цих комірок не утворювала циклу з наявними завантаженими комірками. Під циклом розуміють замкнуту ламану з прямими кутами переломлення у вершинах. За такі комірки оберемо і .

5. Опорний план нульової ітерації утворить матрицю

.

Його елементи задовольняють системі обмежень (9)-(11). Значення цільової функції на цьому плані дорівнює

(у.о.).

Чи є цей план оптимальним? Відповідь на це питання дає метод потенціалів.

Крок 2. Перевірка оптимальності опорного плану.

1. Побудова системи потенціалів (, ). Кожному постачальнику поставимо у відповідність потенціал , а споживачу ‑ потенціал . При цьому для кожної базисної змінної відповідні їй потенціали і повинні задовольняти рівності

(, ). (12)

Оскільки базисних змінних 7, то сукупність рівностей (12) утворить систему з 8 рівнянь із 7 невідомими. Ця система має нескінченну множину розв’язків, знайдемо одне з них:

· для зручності візьмемо ;

· у рядку знаходиться базисна змінна , тому згідно з (12) ;

· у стовпці знаходиться ще одна (крім ) базисна змінна , тому ;

· за базисною змінною знайдемо ,

· за базисною змінною ‑ ;

· за базисною змінною ‑ ;

· за базисною змінною ‑ ;

· за базисною змінною ‑ .

2. Знайдемо оцінки оптимальності для небазисних змінних. Значення будемо обчислювати за формулою

(, ),

а результат заносити в нижні ліві кути комірок (, ), відокремлюючи їх у рамку:

,

,

,

,

,

,

,

,

.

3. Перевірка оптимальності опорного плану:

· якщо всі оцінки оптимальності небазисних змінних недодатні, тобто , то опорний план є оптимальним, і обчислення більше не проводяться;

· якщо серед оцінок оптимальності є додатні, то опорний план не оптимальний, і його необхідно поліпшувати.

Оскільки для розглянутого плану деякі з оцінок оптимальності є додатними, то вихідний опорний план не є оптимальним.

Крок 3.

1. Визначимо змінну, що вводиться до базису. Серед знайдених оцінок оптимальності виберемо найбільше позитивне значення. Таким є 2, що відповідає 2. У базис необхідно вводити ту з змінних чи , якій відповідає менший тариф. У даному випадку . Тому введемо до базису будь-яку із цих змінних, наприклад, .

2. Визначимо змінну, що виводиться з базису. Для цього побудуємо цикл, що проходить через деякі з завантажених комірок і комірку (що відповідає змінній , яка вводиться з базису). Нагадаємо, що під циклом розуміють замкнену ламану з прямими кутами переломлення у вершинах. Відомо, що цикл у транспортній задачі можна побудувати єдиним чином. У даному випадку цикл виглядає так, як це показано в табл. 3.3. Вершину циклу в комірці відзначаємо знаком «+», а далі інші вершини позначаємо знаками, що чергуються: «-» або «+», послідовно пересуваючись циклом у будь-якому напрямку. Серед комірок, у які потрапив знак «-», вибираємо комірку з найменшим значенням базисної змінної. У даному випадку це значення дорівнює нулю, воно обведене ромбом, а відповідає воно базисній змінній , котру будемо виводити з базису.

3. Побудова нового базису.

Підготуємо нову таблицю першої ітерації (див. табл. 3.4).

· Заносимо в неї дані в умові значення транспортних тарифів, запасів і потреб.

· Без зміни необхідно перенести в таблицю значення базисних змінних, не задіяних циклом.

· Оскільки виведена з базису змінна дорівнює 0, то змінна, що вводиться з базису, також дорівнюватиме нулю, а значення базисних змінних, що знаходяться у вершинах циклу, у даному випадку не зміняться. Комірка змінної, що виведена з базису, стане в результаті вільною.

4. Побудований опорний план першої ітерації утворить ту ж матрицю, що і для вихідного опорного плану, тому значення цільової функції на цьому плані не зміниться:

, (у.о).

Таблиця 3.4 ‑ Перша ітерація транспортної задачі

	-1	1	1	1
0
-4						-3			-1
2
			-1
3
										Ө
-1
				Ө
-2

Чи є новий опорний план оптимальним? Для відповіді на це питання повертаємося до кроку 2 і кроку 3, виконуючи послідовно аналогічні дії. Результати цих дій занесені в табл. 3.4.

· Будуємо систему потенціалів.

· Обчислюємо оцінки оптимальності небазисних змінних.

· Перевіряємо план на оптимальність: серед оцінок оптимальності є позитивна ; тому план першої ітерації не оптимальний, і вводиться до базису змінна – .

· Будуємо цикл, за допомогою якого визначаємо змінну, що виводиться з базису; такою є .

· Будуємо нову таблицю другої ітерації (табл. 3.5), зберігаючи дані умови і значення базисних змінних, не задіяних циклом. Оскільки , то змінна, що вводиться до базису, також буде дорівнювати нулю, а значення базисних змінних, що знаходяться у вершинах циклу, у даному випадку не зміняться.

Таблиця 3.5 ‑ Друга ітерація транспортної задачі

	1	1	3	3
0
				Ө
-2						-1
0
			-3
1
										Ө
-3
-2			-2

Для опорного плану другої ітерації одержимо

, (у.о.).

Повертаємося до кроку 2 і кроку 3, результати виконаних дій занесені в табл. 3.5. Опорний план другої ітерації не оптимальний. У цьому випадку змінна, що вводиться до базису, ‑ , а та, яка виводиться з базису, ‑ . Зауважимо, що при побудові таблиці третьої ітерації (табл.3.6) значення змінних, задіяним циклом, перераховуємо, додаючи до тих із них, що відмічені знаком «+» значення змінної, що виводиться з базису (тобто «20»), а від змінних, відмічених знаком «-», віднімаємо це значення. Змінна, що вводиться до базису, приймає значення 20. Комірка виявиться вільною.

Для опорного плану третьої ітерації одержимо

,

(у.о.).

Таблиця 3.6 ‑ Третя ітерація транспортної задачі

	1	1	3	2
0
				Ө
-4						-1
0
			-3						-1
1
							Ө
									-1
-2
										Ө
-1			-1

Із табл. 3.6 бачимо, що опорний план третьої ітерації не оптимальний. Змінна в цьому випадку, що вводиться до базису, ‑ , а змінна, що виводиться з базису, ‑ . Проводимо перерахування базисних змінних. Результати обчислень у четвертій ітерації занесені в табл. 3.7. Для опорного плану цієї ітерації виконана умова оптимальності: всі оцінки оптимальності недодатні.

У результаті маємо

,

(у.о.).

Таблиця 3.7 ‑ Четверта ітерація транспортної задачі

	0	0	2	2
0
-3			-1			-2
1
			-3
2
-2
-2			-2

Зауважимо, що серед оцінок оптимальності останньої ітерації є такі, значення яких дорівнює нулю, тому побудований опорний план не єдиний, для якого цільова функція приймає мінімальне значення 180 у.о.

Відповідь. Найменші сумарні транспортні витрати, що складають 180 у.о., будуть відповідати такому плану перевезень:

· з пункту виробництва необхідно перевозити 30 т вантажу до пункту споживання ;

· з пункту виробництва ‑ 20 т вантажу до пункту споживання ;

· з пункту виробництва ‑ 30 т вантажу до пункту споживання і 10 т – в .

Оскільки пункт є фіктивним, то споживач залишиться невдоволений на 10 т вантажу.

Результат обчислень можна оформити також у вигляді схеми, показуючи, з якого пункту виробництва в який пункт споживання перевозиться вантаж:

.

3.2 Розв’язання транспортної задачі з використанням інструмента “Поиск решения”

Транспортна задача вже була зведена до закритої моделі. Результат внесений у табл. 3.2. Відповідно до цієї таблиці підготуємо аркуш EXCEL для застосування інструмента «Поиск решения» (див. рис. 3.1).

1. Комірки В4:Е7 заповнюємо матрицею транспортних тарифів транспортної задачі, зведеної до закритого вигляду.

2. У комірках F4:F7 записуємо обсяги запасів на підприємстві ().

3. У комірки В8:Е8 вносимо обсяги потреб споживача ().

4. Комірки B11:E14 резервуємо для значень змінних моделі, що будуть знайдені після виконання процедури «Поиск решения».

5. Комірка F15 (цільова комірка) резервується для обчислення оптимального значення цільової функції моделі.

Рис. 3.1 ‑ Представлення вихідних даних у таблиці EXEL

Після заповнення вихідних даних у цільову комірку F15 вносимо формули СУММПРОИЗВ(В4:Е7; B11:E14), у комірку F11 – СУМ(В11:Е11), що копіюємо з модифікаціями в комірки F12:F14, і в комірку В15 – СУМ(В11:В14), що копіюємо з модифікаціями в комірки С15:Е15. Результат представлений на рис. 3.2.

Рис. 3.2 ‑ Формули розрахунку в таблиці EXEL

Рис. 3.3 ‑ Екранна форма «Поиск решения»

Рис. 3.4 ‑ Результати роботи процедури «Поиск решения» (перший варіант)

Таким чином, усі підготовчі процедури закінчені, тому вибираємо в «Сервис» інструмент «Поиск решения». Заповнюємо екранну форму, що з'явилася, так, як це показано на рис. 3.3, виконуючи дії, аналогічні описаним у
п. 1.2.

Результат розв’язання транспортної задачі з використанням інструмента «Поиск решения» представлений на рис. 3.4. Оптимальний розв’язок
транспортної задачі в цьому випадку можна представити матрицею

,

а мінімальне значення цільової функції на цьому плані дорівнює

(у.о.).

Як було зауважено вище (перед остаточним записом результатів методу потенціалів), розв’язок даної задачі не єдиний. Другий варіант розв’язку представлено на рис. 3.5. Оптимальний розв’язок транспортної задачі в цьому випадку можна представити матрицею

,

Мінімальне значення цільової функції при цьому не зміниться, а саме:

(у.о).

Зауважимо, що для отримання різних варіантів розв’язку транспортної задачі (якщо розв’язок не єдиний) потрібно повторно запускати на виконання процедуру «Поиск решения» без зміни вхідних даних.

Рис. 3.5 ‑ Результати роботи процедури «Поиск решения» (другий варіант)

Відповідь. Найменші сумарні транспортні витрати складають 180 у.о. Це відповідає двом варіантам плану перевезень. Перший варіант:

· з пункту виробництва необхідно перевозити 30 т вантажу до пункту споживання ;

· з пункту виробництва ‑ 20 т вантажу до пункту споживання ;

· з пункту виробництва ‑ 30 т вантажу до пункту споживання і 10 т – в. ;

· при цьому плані споживач залишиться невдоволений на 10 т вантажу.

Другий варіант:

· з пункту виробництва необхідно перевозити 30 т вантажу до пункту
споживання ;

· з пункту виробництва ‑ 10 т вантажу до пункту споживання і 10 т – в ;

· з пункту виробництва ‑ 10 т вантажу до пункту споживання і 30 т – в. ;

· при цьому плані споживач залишиться невдоволений на 10 т вантажу.

Дата добавления: 2014-12-08