Приклад розв’язання транспортної задачi лiнiйного програмування

Розв’язати ТЗЛП, наведену в табл. 5.11.

Таблиця 5.11

Покажемо, що якщо на деякому етапі побудови ДБР будемо мати альтернативу: "що викреслити – стовпчик чи рядок?" (випадок отримання виродженого базисного розв’язку), то не має значення, яку альтернативу обирати. На значення оптимального розв’язку це не вплине.

У цій задачі умова балансу виконується, тому вводити фіктивні пункти не треба.

Оскільки у вихідній задачі , то при знаходженні початкового розв’язку методом північно-західного кута одержимо вироджений розв’язок. Тобто на ітерації 3 побудови ДБР будемо мати альтернативу: "що викреслити – стовпчик чи рядок?"

У табл. 5.12 подано початковий розв’язок, що відповідає випадку, коли після визначення значення змінної викреслюється другий рядок.

Таблиця 5.12

					ѕ
						ѕ
							ѕ
		ѕ	ѕ
ѕ	ѕ

Сумарні витрати за таким планом перевезень складають:

У табл. 5.13 наведено початковий розв’язок, що відповідає випадку, коли після визначення значення змінної викреслюється другий стовпчик.

Таблиця 5.13

					ѕ
							ѕ
						ѕ
ѕ	ѕ	ѕ	ѕ

Сумарні витрати за таким планом перевезень складають:

Спочатку знайдемо оптимальний розв’язок вихідної задачі, відштовхуючись від початкового розв’язку (табл. 5.11). Для нього шукаємо потенціали і за ними – відносні оцінки небазисних змінних (табл. 5.14).

Таблиця 5.14

	v1=4	v2=10	v3=16 Я	v4=9
Ь
u1=0			x13
		ѕ			+14	Е
u2=-2	4
		Е		ѕ
u3=-7		0
	-10			Е		ѕ

Небазисна змінна x₁₃, що має найбільшу додатну оцінку d₁₃=14, увійде до складу базисних. З аналізу компенсаторного циклу, що відповідає x₁₃, , випливає, що з базису повинна бути вилучена одна з трьох змінних, бо . У цьому випадку все одно, яку змінну виводити з базису. Хай це буде змінна .

У табл. 5.15 представлено черговий базисний розв’язок. Сумарні витрати складають: . Оскільки , то розв’язок не оптимальний. Відповідну змінну будемо вводити до базису.

Таблиця 5.15

	v1=-10	Ýv2=-4	v3=2	v4=-5
u1=0
	-14		-7				-5
u2=12		0	x23
Ü				ѕ	+13	Е
u3=7
	-10			Е		ѕ

Для змінної, що вводиться до базису x₂₃, побудуємо компенсаторний цикл: . З аналізу циклу випливає, що з базису може бути вилучена одна з двох змінних. Нехай це буде змінна

У табл. 5.16 подано новий базисний розв’язок. Сумарні витрати на перевезення складають ті самі90од. вартості.

Таблиця 5.16

	v1=3	v2=-4	v3=2	v4=-5
u1=0
	-1		-7				-5
u2=-1
		ѕ	-13			Е	-11
u3=7	X31
	+3	Е				ѕ
	14 Э		10 ß

Оскільки , то розв’язок не оптимальний. Для змінної, що вводиться до базису x₃₁, побудуємо компенсаторний цикл: . Оскільки , то з базису вилучається змінна .

У табл. 5.17 наведено новий базисний розв’язок. Сумарні витрати складають:

Таблиця 5.17

	v1=3	v2=-1	v3=2	v4=-2
u1=0
	-1		-4				-2
u2=-1
			-10				-8
u3=4
					-3

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

Тепер знайдемо оптимальний розв’язок вихідної задачі, спираючись на початковий розв’язок з табл. 5.12. Для нього шукаємо потенціали і за ними – відносні оцінки небазисних змінних (табл. 5.18).

Таблиця 5.18

	v1=4	Ý v2=10	v3=3	v4=-4
u1=0
							-4
u2=-2
Ü				ѕ		Е	-11
u3=6		x32
			+13	Е		ѕ
		10 Э

Оскільки , то розв’язок не оптимальний. Для змінноїx₃₂, що вводиться до базису, побудуємо компенсаторний цикл: . З аналізу циклу випливає, що з базису може бути вилучена одна з двох змінних. Нехай це буде змінна :

Табл. 5.19 містить базисний розв’язок. Сумарні витрати на перевезення складають: Оскільки , то розв’язок не оптимальний. Для змінної x₃₁ , що вводиться до базису, побудуємо компенсаторний цикл: Замкнений цикл вказує на те, що з базису вилучається змінна

Таблиця 5.19

	v1=4	v2=-3	v3=3	v4=-4
u1=0
			-6				-4
u2=-2
		ѕ	-13			Е	-11
u3=6	x31
	+3	Е				ѕ
	14 Э		10 ß

Табл. 5.20 містить черговий базисний розв’язок, сумарні витрати якого дорівнюють:

Таблиця 5.20

	Ý v1=4	v2=0	Я v3=3	v4=-1
u1=0			x13
		ѕ	-3		+1	Е	-1
u2=-2
		Е	-10			ѕ	-8
u3=3
					-3

Оскільки , то розв’язок не оптимальний. Для змінної x₁₃, що вводиться до базису, побудуємо компенсаторний цикл: З аналізу циклу випливає, що з базису може бути вилучена одна з двох змінних. Нехай це буде змінна :

Табл. 5.18 містить черговий базисний розв’язок. Йому відповідають сумарні транспортні витрати:

Таблиця 5.21

	v1=3	v2=-1	v3=2	v4=-2
u1=0
	-1		-4				-2
u2=-1
			-10				-8
u3=4
					-3

Оскільки відносні оцінки всіх небазисних змінних недодатні, розв’язок оптимальний. Відзначимо, що цей розв’язок збігається з розв’язком табл. 5.16.

Отже, оптимальний план перевезень буде таким, як наведено в табл. 5.22.

Таблиця 5.22