2.3 Выводы к Главе 2

• В данной главе продемонстрированы основные этапы и приемы, используемые для решения полностью и частично целочисленных задач методом отсекающих плоскостей и методом ветвей и границ.

• При использовании обоих методов значения целевой функции получаются одинаковыми, поскольку оба метода являются точными методами решения целочисленных задач.

• По итогам решенных задач видно, что трудоемкость решения методом ветвей и границ намного больше, так как на каждом шагу возникает по две порожденные задачи, а не по одной, как в методе Гомори. Преимуществом метода ветвей и границ является то, что он позволяет найти все оптимальные решения задачи, в то время как метод Гомори только одно.

3. Нелинейное программирование

3.1 Определение вида квадратичной формы

Максимизировать целевую функцию:

Y=21x₁+5x₂+7x₃--2x₁x₂--→ max

При ограничениях:

x₁+3x₂ ≤ 2

3x₁+x₃ ≤ 0

x_1,2,3 ≥ 0

Возьмем приведённые частные производные частные производные от ЦФ:

Перепишем целевую функцию:

Y = (0 +10,5x₁+2,5x₂+3,5x₃)*1+

+(10,5 - 5x₁ - x₂ + 0x₃)*x₁+

+(2,5 - x₁ - x₂ + 0x₃)*x₂+

+(3,5 + 0x₁ + 0x₂ - x₃)*x₃

Матрица D:

Определяем вид квадратичной формы:

1) Критерий Сильвестра.

Определим миноры:

Полученный ряд является знакочередующимся, следовательно, квадратичная форма целевой функции отрицательно определённая.

2) Метод характеристических чисел.

Все корни отрицательные, следовательно, квадратичная форма целевой функции отрицательно определённая.

По результатам исследования квадратичной формы целевой функции можно сделать вывод, что для решения задачи может быть применён квадратичный метод Била.

3.2 Решение задачи методом Била

Допустимое базисное решение:

x₄=2-(x₁+x₂)

x₅=0-(3x₁+x₃)

Целевая функция:

Y = (0 +10,5x₁+2,5x₂+3,5x₃)*1+

+(10,5 - 5x₁ - x₂ + 0x₃)*x₁+

+(2,5 - x₁ - x₂ + 0x₃)*x₂+

+(3,5 + 0x₁ + 0x₂ - x₃)*x₃

Теперь можно сформировать первую таблицу.

Таблица 3.1 – Исходная таблица 1 итерации

БП	СЧ	X1	X2	X3
X1	0	1	0	0
X2	0	0	1	0
X3	0	0	0	1
X4	2	-1	-3	0
X5	0	-3	0	-1
1	0	21/2	5/2	7/2
X1	21/2	-5	-1	0
X2	5/2	-1	-1	0
X3	7/2	0	0	-1

Так как элементы первой строки нижней части таблицы, стоящие на пересечении с U-ми отсутствуют и элементы, стоящие на пересечении с Х-ми столбцами, положительны, следовательно, решение не является оптимальным, что означает продолжение решения.

U-е столбцы отсутствуют, поэтому в качестве направляющего выбираем столбец, имеющий на пересечении с данной строкой положительный элемент, в данном случае, выберем столбец соответствующий переменной x₁. Выбираем направляющую строку, для этого найдём отношение:

, для и

Строка, дающая минимум отношений, является направляющей.

Направляющий столбец – x₁

Направляющая строка – x₅

Элемент, находящийся на пересечении направляющей строки и направляющего столбца – разрешающий (в данном случае он равен -3).

Таблица 3.2 – Промежуточная таблица 1 итерации

БП	СЧ	X5	X2	X3
X1	0	-1/3	0	-1/3
X2	0	0	1	0
X3	0	0	0	1
X4	2	1/3	-3	1/3
X5	0	1	0	0
1	0	-7/2	5/2	0
X5	21/2	5/3	-1	5/3
X2	5/2	1/3	-1	1/3
X3	7/2	0	0	-1

Верхнюю часть окончательной таблицы переписываем без изменений из промежуточной в итоговую.

Второй направляющей строкой является строка, пересекающаяся с направляющим столбцом по главной диагонали нижней части таблицы.

Разделив каждый элемент второй направляющей строки промежуточной таблицы на разрешающий элемент, получим соответствующую строку окончательной таблицы. Оставшиеся элементы рассчитаем по формуле:

,

- искомый элемент, где i – номер строки, а j – номер столбца (нумерация строк начинается с нижней части таблицы)

- элемент из промежуточной таблицы, который находиться в ней на месте искомого

- элемент второй разрешающей строки, где к – номер второй разрешающей строки

- элемент первой разрешающей строки, где h – номер первой разрешающей строки.

Таблица 3.3 - Итоговая таблица 1 итерации

БП	СЧ	X5	X2	X3
X1	0	-1/3	0	-1/3
X2	0	0	1	0
X3	0	0	0	1
X4	2	1/3	-3	1/3
X5	0	1	0	0
1	0	-7/2	5/2	0
X5	-7/2	-5/9	1/3	-5/9
X2	5/2	1/3	-1	1/3
X3	0	-5/9	1/3	-14/9

Элементы первой строки нижней части таблицы, стоящие на пересечении с U-ми столбцами не равны нулю или элементы, стоящие на пересечении с Х-ми столбцами, положительны, следовательно решение не является оптимальным.

В качестве начальной таблицы 2-й итерации воспользуемся итоговой таблицей первой итерации.

Рассматриваем первую строку нижней части таблицы без первого элемента.

U-е столбцы отсутствуют или в первой строке нижней части таблицы на пересечении с ними стоят нули, поэтому в качестве направляющего выбирают столбец, имеющий на пересечении с данной строкой положительный элемент.

Направляющий столбец – x₂

Направляющая строка – x₄

Таблица 3.4 – Промежуточная таблица 2 итерации

БП	СЧ	X5	X4	X3
X1	0	-1/3	0	-1/3
X2	2/3	1/9	-1/3	1/9
X3	0	0	0	1
X4	0	0	1	0
X5	0	1	0	0
1	5/3	-29/9	-5/6	5/18
X5	-59/18	-14/27	-1/9	-14/27
X4	11/6	2/9	1/3	2/9
X3	2/9	-14/27	-1/9	-41/27

Таблица 3.5 – Итоговая таблица 2 итерации

БП	СЧ	X5	X4	X3
X1	0	-1/3	0	-1/3
X2	2/3	1/9	-1/3	1/9
X3	0	0	0	1
X4	0	0	1	0
X5	0	1	0	0
1	26/9	-83/27	-11/18	23/54
X5	-83/27	-40/81	-2/27	-40/81
X4	-11/18	-2/27	-1/9	-2/27
X3	23/54	-40/81	-2/27	-121/81

Решение продолжается. Из базиса выводится x₁ и вводится x₃.

Таблица 3.6 – Промежуточная таблица 3 итерации

БП	СЧ	X5	X4	X1
X1	0	0	0	1
X2	2/3	0	-1/3	-1/3
X3	0	-1	0	-3
X4	0	0	1	0
X5	0	1	0	0
1	26/9	-7/2	-11/18	-23/18
X5	-83/27	0	-2/27	40/27
X4	-11/18	0	-1/9	2/9
X1	23/54	1	-2/27	121/27

Таблица 3.7 – Итоговая таблица 3 итерации

БП	СЧ	X5	X4	X1
X1	0	0	0	1
X2	2/3	0	-1/3	-1/3
X3	0	-1	0	-3
X4	0	0	1	0
X5	0	1	0	0
1	26/9	-7/2	-11/18	-23/18
X5	-7/2	-1	0	-3
X4	-11/18	0	-1/9	2/9
X1	-23/18	-3	2/9	-121/9

В итоговой таблице матрица в нижней части таблицы симметрическая, а в первой строке значения, стоящие на пересечении с Х-ми столбцами отрицательные, на пересечении с U-ми столбцами – равны нулю, а следовательно, полученное решение является оптимальным.

Ответ: Y = 26/9, X = ( 0; 2/3; 0).