Алгоритм розв’язання задачі лінійного програмування за допомогою симплекс-методу

Алгоритм симплекс-методу дозволяє повністю дослідити ЗЛП. Якщо розв’язок існує, то його буде знайдено симплекс-процедурою, якщо розв’язку немає то в процесі реалізації симплекс-процедури буде встановлено факт його відсутності. Схема розв’язання має такий вигляд.

І. Згідно [1], записуємо ЗЛП (5.1), (5.2) в нормальному стандартному вигляді.

(7.1)

ІІ. Будуємо симплекс-таблицю.

	b	x1	x2	x3	…	xn
		c1	c2	c3	…	(7.2) cn
y1	b1	a11	a12	a13	…	a1n
y2	b2	a21	a22	a23	…	a2n
y3	b3	a31	a32	a33	…	a3n
…	…	…	…	…	…	…
ym	bm	am1	am2	am3	…	amn

Змінні назвемо базовими змінними; змінні – вільними змінними. Узагалі кажучи, змінні, які стоять у лівій частині будемо називати базовими, ті, що стоять у правій верхній частині, – вільними.

Суть симплекс-методу полягає у взаємозаміні базових змінних на вільні за спеціальною (описаною нижче) процедурою для одержання спочатку допустимого, а потім і оптимального розв’язку задачі. Розв’язок називатимемо допустимим, якщо він задовольняє нерівності (5.2).

ІІІ. Шукаємо допустимий розв’язок. Для цього побудуємо нову симплекс-таблицю (7.3), згідно наступних правил:

1. Беремо будь-який від’ємний елемент у першому стовпчику таблиці (7.2) (за винятком першого). Якщо такого елемента немає, переходимо до виконання пункту ІV.

Нехай таким елементом є b_m < 0.

2. У рядку, де знаходиться вибраний елемент (у цьому прикладі рядок m) вибираємо будь-який від’ємний елемент (якщо такий є). Стовпчик з цим елементом призначаємо базовим. Якщо від’ємного елемента в рядку немає, вибираємо інший рядок з від’ємним елементом у першому стовпчику. Якщо у всіх рядках від’ємних елементів немає, то й задача розв’язку не має. Область порожня.

3. У базовому стовпчику перебираємо всі елементи (крім першого), які мають однакові знаки з відповідними елементами першого стовпчика. Для них обчислюємо відношення , j₀ – номер базового стовпчика. Нехай j₀ =2 , тоді m рядок призначаємо базовим, а елемент a_m2, який стоїть у клітинці, де перетинаються базовий рядок і базовий стовпчик,– базовим елементом. Проводимо взаємозаміну вільної та базової змінних, які відповідають базовому стовпчику та базовому рядку.

4. У базовій клітинці таблиці (7.3) записуємо елемент обернений до відповідного елемента табл. (7.2).

5. Усі елементи базового рядка ділимо на цей елемент, але обчислень ніяких не виконуємо; виписуємо з таблиці (7.2).

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

7. Усі інші елементи табл. (7.3) утворюються як результат додавання відповідного елемента табл. (7.2) та добутку відповідного елемента базового стовпчика табл. (7.3) на чисельник відповідного елемента базового рядка тієї самої таблиці.

	b	x1	ym	x3	…	xn
					…
y1					…	(7.3)
y2	...				…
y3	...				…
…	…	…	…	…	…	…
x2					…

8. Після заповнення табл. (7.3), повторюємо процедуру починаючи з
п. 1, використовуючи як вихідну табл. (7.3).

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

ІV. Будуємо оптимальний розв’язок ЗЛП

1. Знаходимо серед елементів першого рядка (крім першого елемента) додатні числа. Якщо таких елементів немає, переходимо до виконання
п. V.

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

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

Зауваження 1. Якщо в задачі (5.1), (5.2) тоді в (7.1) перша нерівність виглядатиме так:

,

а в першій симплекс-таблиці перший рядок матиме такий вигляд:

	b	x1	х2	…	xn
		– с1	– с2	…	– сn

Кінцева таблиця симплекс-процедури І-V у першій клітинці міститиме число, яке дорівнює

Зауваження 2. Якщо під час виконання пункту IV з’являється ситуація, коли перший рядок симплекс-таблиці містить додатні елементи, а в стовпчику, де вони містяться, додатних елементів немає, тоді й задача розв’язку не має, область необмежена і розв’язок знаходиться в нескінченності.

Приклад. Розв’язати ЗЛП

за умов

Розв’язування: Запишемо задачу в нормальному вигляді (виконаємо п. І).

Складаємо симплекс-таблицю:

			-1
				-2
	-2		-1	-3
	-6	-3		-1	-3
	-1	-1

Визначаємо базовий стовпчик і базовий рядок, перетин яких дає базовий елемент. Базовий елемент «-1». Будуємо нову таблицю.

	b
	0+(-1)·(-2)=2	2+(-1)·2=0	–1	0+(-1)·(-3)=3	3+(-1)·1=2
	8+2·(-2)=4	1+2·2=5		-2+2·(-3)=-8	2+2·1=4
	-6+(-2)·2=-10	-3+2·2=1		-1+2·(-3)=-7	-3+2·1=-1
	-1+(-2)·0=-1	-1+2·0=-1		0+(-3)·0=0	0+1·0=0
	3+(-2)·0=3	0+2·0=0		1+(-3)·0=1	0+1·0=0

Повторюємо симплекс-процедуру.

b

x1

y2

x3

x4

b

x1

y2

х3

y1

–1

-2

y1

-8

x4

x2

–2

–1

–1

х2

y3

–10

–7

–1

y3

-9

-9

y4

–1

–1

y4

–1

–1

y5

y5

 

b

x1

y2

x3

y1

b

x1

y2

y3

y1

-2

-7

x4

x4

x2

х2

y3

-9

-9

x3

y4

–1

–1

y4

–1

–1

y5

y5

 

 

b

x1

y2

y3

y1

b

y4

y2

y3

y1

-7

x4

x4

х2

х2

x3

x3

y4

–1

–1

x1

–1

y5

y5

 

 

b

y4

y2

y3

y1

b

y4

y2

y5

y1

-2

-7

x4

x4

х2

х2

-1

x3

x3

x1

–1

x1

–1

y5

y3

 

Записуємо фінальну симплекс-таблицю:

	b	y4	y2	y5	y1
			-2	-7
x4
х2				-1
x3
x1		–1
y3

Відповідь:

Завдання для самостійних і контрольних робіт

Розв’язати за допомогою симплекс-методу:

 

1.		2.
3.		4.
5.		6.
7.		8.
9.		10.
11.		12.
13.		14.
15.		16.
17.		18.
19.		20.
21.		22.
23.		24.
25.		26.
27.		28.
29.		30.
31.