Решение. Вводим балансовые переменные х3, х4 и получаем систему:

Вводим балансовые переменные х ₃, х ₄ и получаем систему:

Далее процесс решения мы представляем в виде симплексных таблиц, опуская подробные вычисления.

Таблица 2.20

	х 1	х 2	х 3	х 4
х 3	-1
х 4		-1
f		-16

Таблица 2.21

	х 1	х 2	х 3	х 4
х 2
х 4
f

Таблица 2.22

	х 1	х 2	х 3	х 4
х 2
х 1
f

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

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

Таблица 2.23

	х 1	х 2	х 3	х 4	х 5
х2
х 1
х 5
f

Разрешающий элемент таблицы 23 находим по максимуму модуля отрицательного коэффициента при аргументах в добавленном уравнении.

В силу этого фиктивная переменная х ₅ сразу же выводится из состава базисных переменных и мы переходим к очередным симплексным таблицам.

Таблица 2.24

	х 1	х 2	х 3	х 4	х 5
х 2
х 1				1/5	1/5
х 3				1/5	-24/5
f				-3/5	77/5

Таблица 2.25

	х 1	х 2	х 3	х 4	х 5
х 2
х 4
х 3	-1				-5
f

Так как среди индексов в последней таблице нет отрицательных элементов, то план (0;3; 0; 15; 0) является оптимальным. Таким образом f _max = f (0; 3) = 48, при этом (0; 3) – целочисленное решение.

Пример. f =3 x ₁ + x ₂®max?

x ₁, х ₂ – целые неотрицательные.

Решение. Вводим балансовые переменные х ₃, х ₄, получаем систему:

Решаем задачу симплексным методом с помощью таблиц.

Таблица 2.26

	х 1	х 2	х 3	х 4
х 3
х 4		-3
f	-3	-1

Таблица 2.27

	х 1	х 2	х 3	х 4
х 3				-1
х 1
f

Таблица 2.28

	х 1	х 2	х 3	х 4
х 2
х 1
f

(без учета целочисленности аргументов).

Так как , то составляем неравенство Гомори для уравнения . Оно имеет вид: , или . Вводим фиктивную переменную х ₅ такую, чтобы , или . Последнее уравнение включаем в систему ограничений и переходим к следующей симплексной таблице.

Таблиц 2.29

	х 1	х 2	х 3	х 4	х 5
х 2
х 1
х 5
f

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

Таблица 2.30

	х 1	х 2	х 3	х 4	х 5
х 2
х 1
х 4
f

Так как , то неравенство Гомори имеет вид: , т.е. . Добавляем фиктивную переменную х ₆ такую, чтобы или и переходим к следующей симплексной таблице.

Таблица 2.31

	х 1	х 2	х 3	х 4	х 5	х 6
х 2
х 1
х 4
х 6
f

Теперь к последующим таблицам переходим без подробных объяснений.

Таблица 2.32

	х 1	х 2	х 3	х 4	х 5	х 6
х 2
х 1
х 4
х 5			1/4			-5/4	3/4
f			5/8			7/8	51/8

Таблица 2.33

	х 1	х 2	х 3	х 4	х 5	х 6	х 7
х 2
х 1
х 4
х 5
х 7
f

Таблица 2.34

	х 1	х 2	х 3	х 4	х 5	х 6	х 7
х 2
х 1
х 4							-4
х 5
х 6
f

Таблица 2.35

	х 1	х 2	х 3	х 4	х 5	х 6	х 7	х 8
х 2
х 1
х 4							-4
х 5
х 6
х 8
f

Таблица 2.36

	х 1	х 2	х 3	х 4	х 5	х 6	х 7	х 8
х 2							-1
х 1
х 4							-5
х 5
х 6							-3
х 3								-3
f

Из последней таблицы видно, что f _max= f (1, 1) = 4, где х ₁=1, х ₂ = 1 – целые числа.

РАЗДЕЛ 3. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Тема 3.1. Квадратичное программирование

Под задачей квадратичного программирования будем понимать задачу на отыскание оптимума целевой функции в следующих трех случаях:

1) целевая функция линейная, а ограничения на ее аргументы квадратичные;

2) целевая функция квадратичная, а ограничения на ее аргументы линейные;

3) целевая функция квадратичная и ограничения на ее аргументы квадратичные.

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

Пример. F = 2 x ₁ + 3 x ₂®оптимум,

Решение. Находим и строим область ограничений.

Парабола имеет вершину в точке V (2; 0) и ограничивает область решения системы неравенств сверху. Слева и снизу область ограничена осями координат.

Задаем значения целевой функции. Пусть f = 0. Строим опорную прямую (линию одного уровня) 2 х ₁ + 3 х ₂ = 0. Она проходит через точки (0; 0) и (-3; 2). Двигая опорную прямую параллельно самой себе, находим точки входа и выхода О, А.

Рис 3.1. Графический метод.

При этом f (0; 0) = 2×0 + 3×0 = 0 – наименьшее значение целевой функции, а f (А) – ее наибольшее значение. Теперь находим координаты точки А. Угловой коэффициент касательной к параболе в точке А равен , он же равен значению производной квадратичной функции в точке А. Таким образом . Следовательно, и и значит, .

Пример. оптимум?

Решение. Находим и строим область решения системы неравенств. Так как уравнения х ₁× х ₂ = 1; х ₁ = 0; х ₁ = 2; х ₂ = 0; х ₂ = 2 задают на плоскости координат гиперболу и прямые, то криволинейный четырехугольник ОАВСD является областью решения системы неравенств.

Рис 3.2. Графический метод

Если f = 0, то уравнение определяет начало координат, если f >0, то оно определяет эллипс

с полуосями и .

Таким образом линии одинакового уровня (одинакового значения целевой функции) представляют собой подобные эллипсы с центром подобия в начале координат. Чем крупнее эллипс, тем больше значение целевой функции. Получаем, что

f_min = f (O) = 0 и .

Пример. оптимум?

Решение. Область решения системы неравенств является четырехугольник АВСD (рис. 3.3.).

Рис. 3.3. Геометрический метод

Линией одинакового значения целевой функции является парабола , с вершиной в точке . При движении параболы в положительном направлении оси Ох значение f будет увеличиваться. Исходя из этого имеем:

f _max = f (B) = f (0; 3) = 2×0 + 3² = 9.

Дата добавления: 2014-10-31