Методи побудови початкового допустимого базисного розв’язку

Розв’язання ЗЛП симплекс-методом починається з деякого ДБР. У методі потенціалів початковий ДБР знаходять методами:

- північно-західного кута;

- найменшої вартості;

- Фогеля.

Метод північно-західного кута. Схема алгоритму така.

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

Крок 2. Якщо a₁< b₁ то виробник 1 повністю використав свої можливості, тому далі його можна не враховувати, а потреба споживача 1 тепер дорівнюватиме b₁ – a₁.

Якщо a₁ > b₁ , то споживач 1 повністю задовольнив свою потребу в продукції, і його можна далі не враховувати, а виробник 1 тепер має лише a₁ – b₁ одиниць продукції.

Якщо a₁ = b₁, то з розгляду можна вилучити виробника і споживача. У цьому разі "вибуває з гри" тільки один з них: або виробник, або споживач, а споживачу (виробнику), що залишився, приписують нульовий попит (обсяг виробництва).

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

Застосуємо описану процедуру до задачі 1 з табл. 5.2.

1. Клітина 11 знаходиться в північно-західному куті початкової таблиці:

x₁₁= =

—

Стовпчик 1 викреслюють, оскільки потреби першого пункту споживання задово­лено. У першому пункті виробництва залишилося од. продукції.

2.У «новій» таблиці в північно-західному куті (клiтина 12)

x₁₂=

						—
—

Рядок 1 викреслюють, а в пункт споживання 2 лишилося доставити b₂ =
= 25 — 5 = 20 од. продукції.

3. У наступній таблиці в північно-західному куті (клiтина 22)

x₂₂=

						—
—
	—

У цьому випадку можна викреслити або стовпчик 2, або рядок 2. Викреслюють стовпчик. Тоді в пункті виробництва 2 залишиться од. продукції.

4.х₂₃=

						—
						—
—
	—

Викреслюють рядок 2, у пункті залишилось од. продукції.

5. x₃₃=

						—
						—
—
	—	—

Викреслюють стовпчик 3, у пункті залишилось од. продукції.

6. х₃₄ = Оскільки залишається тільки один стовпчик і тільки один рядок, процес закінчується. У результаті одержано такий базисний розв’язок (табл. 5.3):

Таблиця 5.3

Базисні змінні набувають значень: х₁₁=5, х₂₁=5, х₂₂=20, х₂₃=0, х₃₃=10, х₃₄=10. Інші змінні – небазисні – зі значеннями, що дорівнюють нулю. Відповідні транспортні витрати дорівнюють

z₀= од. вартості.

Цей розв’язок є виродженим, бо базисна змінна х₂₃ дорівнює нулю. Виродженість у початковому розв’язку, одержаному методом північно-західного кута, виявляється тоді, коли на деякому етапі для обраної клітини (i,j) маємо a_i=b_j (одночасно і рядок і стовпчик задовольняють обмеження). У цьому випадку чергова змінна, що вводиться до базису, обов’язково має нульове значення. Далі виродженість не потребує ніяких додаткових запобіжних заходів; з нульовими базисними змінними оперують так само, як зі змінними, що мають додатне значення.

Приклад невиродженого початкового ДБР, одержаного методом північно-західного кута:

Метод найменшої вартості.Метод північно-західного кута не обов’язково дає «добрий» початковий розв’язок для транспортної задачі. Розглянемо метод найменшої вартості, що забезпечує одержання початкового розв’язку вибором «дешевих» маршрутів.

Схема його алгоритму така.

Крок 1. Обирають змінну, якій відповідає найменша вартість у всій таблиці, і їй надають якомога більше значення. (Якщо таких змінних декілька, то беруть будь-яку з них.)

Крок 2. Викреслюють відповідний стовпчик або рядок (оскільки це обмеження задачі виконано). Якщо обмеження по стовпчику і рядку виконують одночасно, то, як і в методі північно-західного кута, викреслюють або стовпчик, або рядок.

Крок 3. Обчислюють нове значення попиту або обсягу виробництва для невикресленого стовпчика або рядка.

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

Для ілюстрації використання методу найменшої вартості можна скористатися транспортною задачею (табл. 5.2).

Оберемо змінну, якій відповідає мінімальна вартість. Такою є змінна
х₁₄ (с₁₄=0). Відповідні значення попиту й обсягу виробництва визначають як х₁₄ = 10, тобто як по стовпчику, так і по рядку обмеження виконуються одночасно. Викреслювати можна або рядок 1, або стовпчик 4. Викреслимо рядок 1. Після цього обсяг виробництва у стовпчику 4 дорівнює нулю.

					ѕ

Тепер серед елементів, що залишилися, мінімальна вартість відповідає х₂₃.

Одержуємо х₂₃=10. Викреслюємо стовпчик 3:

					ѕ
		ѕ

Далі найменша вартість відповідає х₃₁ і х₃₄. Оберемо х₃₄ і одержимо х₃₄=0. Викреслюємо стовпчик 4:

					ѕ
		ѕ
			ѕ

Серед змінних, що залишилися, найменша вартість відповідає х₃₁. Викреслюємо стовпчик 1:

					ѕ
ѕ		ѕ
			ѕ

Далі викреслюємо рядок 2, бо найменша вартість відповідає х₂₂:

					ѕ
						ѕ
ѕ		ѕ
			ѕ

Тоді х₃₂=15. Оскільки залишається тільки один рядок і тільки один стовпчик, процес закінчується:

					ѕ
						ѕ
ѕ		ѕ
	ѕ		ѕ

У результаті одержано такий базисний розв’язок:

Базисні змінні набувають значень: х₁₄=10, х₂₂=10, х₂₃=10, х₃₁=5, х₃₂=15, х₃₄=0. Інші змінні – небазисні. Сумарні транспортні витрати, що відповідають цьому роз­в’язкові, дорівнюють 10*0+10*4+10*1+5*2+15*6+0*2=150 од. вартості, що краще за результат, одержаний при використанні методу північно-західного кута.

Наближений метод Фогеля. Цей метод є евристичним і зазвичай дозволяє одержати кращий початковий розв’язок, ніж два описаних раніше. Насправді цей метод часто дає оптимальний або близький до оптимального початковий розв’язок.

Алгоритм складається з таких кроків:

Крок 1. Обчислити штраф для кожного рядка (стовпчика), віднімаючи найменший елемент цього рядка (стовпчика) вiд наступного за ним за значенням елемента того ж рядка (стовпчика).

Крок 2. Помітити рядок або стовпчик з найбільшим штрафом, а якщо таких декілька, обрати серед них будь-який рядок або стовпчик. У поміченому рядку чи стовпчику обрати змінну з найнижчою вартістю і надати їй найбільшого можливого значення. Скоректувати обсяг виробництва та попит і викреслити рядок або стовпчик, який відповідає виконаному обмеженню. Якщо обмеження по рядку й по стовпчику виконуються одночасно, то викреслити або рядок, або стовпчик, а стовпчику (рядку), що залишився, приписати нульовий попит (обсяг виробництва). Рядок (або стовпчик) з нульовим обсягом виробництва (або попитом) не використовують в подальших обчисленнях (на кроці 3).