Пример 21.2.3

Рассмотрим следующую задачу.

Максимизировать г = 4х, + 6х, - 2х[ - 2х,х, - 2х;

при ограничениях

х, + 2х2 < 2, х х2>0.

Эту задачу можно записать в матричной форме

r-2 -iy*.

максимизировать г = (4, 6) +(х х2)

при ограничениях

(1,2),2, х х2>0.

Условия Куна-Таккера принимают следующий вид.

(4 2 1 2 4 2 1 2 О

-1 0 0 0-10 0 0 I,

Начальная симплекс-таблица для этапа I строится путем введения искусственных переменных /?, и R2. Имеем

Итерация 1. Поскольку , = 0, вводимой в базис переменной может быть х при этом из числа базисных исключается переменная Rr Получаем следующую симплекс-таблицу .

Итерация 2. Так как /и2 = 0, вводимой в базис переменной является х2. В результате приходим к следующей таблице.

Последняя таблица дает оптимальное решение рассматриваемой на этапе I задачи. Так как г = 0, полученное решение х, = 1/3, хг = 5/6 является допустимым. Оптимальное значение z вычисляется подстановкой полученного решения в выражение для целевой функции исходной задачи и равняется 4,16.

Средство Excel Поиск решения можно использовать для решения задач квадратичного программирования. На рис. 21.5 показано решение задачи из данного примера (файл ch21SolverQuadraticProgramming.xls). Исходные данные для задачи представлены в таком же виде, как и в задачах линейного программирования (см. раздел 2.4.2). Основное отличие состоит в том, что целевая функция сейчас нелинейна. Поскольку в данном примере целевая функция имеет вид

z = 4х, + 6х, - Ix1 ~ х,х2 - 2x1,

в ячейку D5 записывается формула

=4*В10+6*С10-2*В10*2-2*810*С10-2*С10*2

Здесь в ячейках В10 и СЮ записаны значения х, и х2. Отметим, что ячейки В5:С5 не используются (в отличие от задач линейного программирования), поэтому мы ввели в них значения NL, показывающие, что ограничения нелинейны. Чтобы указать, что переменные неотрицательны, надо или установить соответствующую опцию в диалоговом окне Параметры или задать нужные ограничения непосредственно в диалоговом окне Поиск решения.

=4*В10+6*С10-2*В10Л2-2 В1и*С10-2*С10Л2

Поиск . ешения

установить целевую ячейку $D$5 Равной. уаксимальноиу значению г

f минимальному значению Изменяя ячейки

Рис. 21.5. Решение в Excel задачи примера 21.2.3

УПРАЖНЕНИЯ 21.2.2

1. Дана задача, в которой требуется

максимизировать z = 6х, + Ъх2 - 4jc,x2 - 2х\ - Ъх\

при ограничениях

JC, + х2< 1, 2хх + Зх2 < 4, xt, х2> 0.

Покажите, что г - строго вогнутая функция, и решите задачу, используя алгоритм квадратичного программирования.

2. Дана следующая задача.

Минимизировать z = 2х,2 + 2х\ + Ъх] + 2хххг + 2х2х} +х,- Ъх2 - 5х3

при ограничениях

X. + X, + X > 1,

1 2 d

3xl + 2x2 + xa<6, X ) ~ 0

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