Лекція 15 Тема: Знаходження невід’ємних розв’язків системи лінійних нерівностей симплекс-методом

План:

1. Знаходження невід’ємних розв’язків системи лінійних нерівностей симплекс-методом.

2. Приклади.

Короткий зміст лекції:

Канонічну задачу можна використати для з’ясування питання про наявність та знаходження розв’язків системи лінійних нерівностей загального виду:

.

(1)

Виходячи з даної системи, будуємо систему лінійних рівнянь:

(2)

Система (1) має розв’язок тоді і тільки тоді, коли в будь-якому невід’ємному розв’язку системи (2) . Одним з таких розв’язків є (0,0,…,0,1).

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

Задана система лінійних нерівностей має розв’язок тоді і тільки тоді, коли поставлена канонічна задача має оптимальний розв’язок і minf = 1.

Щоб знайти розв’язок системи (1), замінюємо дану канонічну задачу загальною задачею максимізації функції із значенням maxg = 1на множині усіх (не тільки невід’ємних) розв’язків системи:

(3)

Розв’язність цієї задачі означає розв’язність заданої системи лінійних нерівностей.

Для її оптимального розв’язку завдяки maxg = 1 має виконуватись , тобто , і тому є розв’язком даної системи.

Розглянемо приклад.

Для заданої системи лінійних нерівностей:

(1)

з’ясувати, чи сумісна вона, і у випадку сумісності знайти будь-який розв’язок.

Розв’язання.

Для заданої системи лінійних нерівностей будуємо систему лінійних рівнянь:

(2)

Розглянемо канонічну задачу мінімізації функції на множині невід’ємних розв’язків системи (2).

Система нерівностей (1) має розв’язок minf = 1 на множині невід’ємних розв’язків системи (2).

Ранг системи (2) дорівнює 4. Нехай – вільне невідоме. Виражаємо базисні невідомі через вільне невідоме , одержуємо систему:

(3)

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

Таблиця І

Базисні невідомі						Вільні члени
	1	0	0	-1	0	0
	0	1	0	-3	0	0
	0	0	-1	7	0	0
	0	0	0	-15	1	1
– f	0	0	0	15	0	-1

З таблиці І випливає min(– f) = – 1. Відповідно із співвідношення minf = – min(– f) = 1, одержуємо, що оптимальним розв’язком є (0,0,0,0,1) і minf = 1.

Отже, задана система нерівностей сумісна.

Знайдемо будь-який розв’язок системи (1). Для цього побудуємо систему:

(4)

Знаходимо maxg, де , на множині розв’язків системи (4). Відповідно до системи (4) будуємо систему лінійних рівнянь:

(5)

Ранг системи (5) дорівнює 5. За вільні невідомі візьмемо . Одержуємо систему:

(6)

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

Таблиця ІІ

Базисні невідомі										Вільні члени
	1	0	0	0	0	0	–1	0	0	0
	0	1	0	0	0	1	1	0	3	3
	0	0	1	0	0	0	0	–1	0	0
	0	0	0	1	0	0	0	0	–1	–1
	0	0	0	0	1	3	7	1	15	15
g	0	0	0	0	0	0	0	0	1	1

З таблиці ІІ випливає, що оптимальний розв’язок знайдено: maxg = 1 при значенні невідомих (0,3,0,–1,15,0,0,0,0). Тоді (0,3,0) є розв’язок системи нерівностей.

Контрольні питання для самоперевірки:

1. Сформулюйте критерій сумісності системи лінійних нерівностей за допомогою канонічної задачі.

2. Як за допомогою канонічної задачі дослідити систему лінійних нерівностей на сумісність?

3. Як знайти розв’язок сумісної системи лінійних нерівностей симплекс-методом?

4. Для заданих систем лінійних нерівностей за допомогою канонічної задачі та симплекс-методу з’ясувати, чи сумісні вони, і у випадку сумісності знайти будь-який розв’язок:

а) б)

Література:

1. Е.С.Ляпин, А.Е.Евсеев. Алгебра и теория чисел. – М: Просвещение, 1978. – Ч. ІІ, гл. ІІІ, §6.

2. С.Г.Колесник, В.В.Цыбуленко. Алгебра и теория чисел. Ч. І. – Х.: ХГПИ, 1998. – Гл. 5, §2.2.

68,1,66,3,64,5,62,7,60,9,58,11,56,13,54,15,52,17,50,19,48,21,46,23,44,25,42,27,40,29,38,31,36,33

2,67,4,65,6,63,8,61,10,59,12,57,14,55,16,53,18,51,20,49,22,47,24,45,26,43,28,41,30,39,32,37,34,35

65