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

↑

⇐ ПредыдущаяСтр 17 из 17

F

-3

-3

f

-1

-2

У результаті першого кроку невідоме  виходить з базису. Наступні кроки мають на меті мінімізувати форму F. Переходимо до таблиці 2, викреслюючи стовпчик .

Таблиця 2

Базисні невідомі

Вільні члени

-5

-2

-1

-1

F

-1

f

-1

-2

Розв’язувальний елемент 1 обираємо в рядку  і стовпці . Отже, після другого кроку обидва штучних невідомих стають небазисними. Цей факт свідчить про те, що min F = 0 (оскільки в останньому базисному розв’язку = = 0). Відкидаємо стовпчик , а також рядок F і переходимо до таблиці 3.

Таблиця 3

Базисні невідомі

Вільні члени

–3

– 4

–1

f

–2

Отже, в заданій системі обмежень виділено базис .

Таблицю 3 можна розглянути як першу симплекс-таблицю заданої задачі.

Розв’язувальний елемент 8 обираємо в рядку  і стовпці . Переходимо до таблиці 4.

Таблиця 4

Базисні невідомі

Вільні члени

–3

f

Звідси видно, що форма f  досягає мінімуму, . Оптимальний розв’язок є .

Якщо в процесі мінімізації форми F ми прийшли до такої таблиці, в якій штучні невідомі вже знаходяться серед небазисних, то це свідчить про те, що мінімум F досягнуто, і він дорівнює нулю. Дійсно, в останньому базисному розв’язку , отже, і F = 0.

Тому, переходячи до наступної таблиці, відкидаємо не тільки стовпчик для останнього штучного невідомого, але і рядок для F. Одержана так таблиця розглядається як перша симплекс-таблиця для поставленої задачі.

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

1. Як знайти невід’ємний базисний розв’язок канонічної задачі мінімізації?

2. В чому полягає «метод штучного базису» відшукання базису системи-обмежень канонічної задачі?

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

а) б)

4. Серед невід’ємних розв’язків системи рівнянь:

 знайти такий, що мінімізує функцію .

Література:

1. С.Т.Завало, В.М.Костарчук, Б.І.Хацет. Алгебра і теорія чисел, Ч.2. – К.: Вища школа, 1980. – Гл.І, §4.4.

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

3. Солодовников А.С. Введение в линейную алгебру и линейное программирование. – М.: Просвещение, 1966. – Гл. 6,§ 26.

Лекція 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

-3

-1

-15

– f

-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

–1

–1

–1

g

З таблиці ІІ випливає, що оптимальний розв’язок знайдено: 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

Познавательные статьи:



Техника нижней прямой подачи мяча

Комплекс физических упражнений для развития мышц плечевого пояса

Стандарт Порядок надевания противочумного костюма

Общеразвивающие упражнения без предметов