Итерация 2. Так как /и2 = 0, вводимой в базис переменной является х2. В результате приходим к следующей таблице.
Базис | | | | | | | | | Решение |
| | | | | | | | | |
| | | | -1/3 | | | | -1/3 | |
| | | | | | | | | |
| | | -1/6 | | | -1/6 | | | |
Итерация 3. | Так как | *i = | 0, в число базисных можно ввести переменную Яг В ре- |
зультате получаем симплекс-таблицу. | | | | | |
Базис | | | | | | | | | Решение |
| | | | | | | | | |
| | | | -1/3 | | | -1/6 | | |
| | | | | -1/2 | | | | |
| | | | | -1/12 | -1/6 | 1/12 | | |
Последняя таблица дает оптимальное решение рассматриваемой на этапе 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
| | | | el . | | | |
| Quadratic Programming Model | | |
| Input data: | | | | | |
| | | | | | | |
| | | | Totals | | Limits | |
| Objective | | | 4 16P6R7 | | | |
| Constraint | | | 2 , | <= | | |
| | >=0 | >=0 | |
| Output results: | |
| | | | | | | |
| Solution | 0 333333 | 0 833333 | 4 166667 | | | |
| | | | | | |
Поиск . ешения
установить целевую ячейку $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»
Покажите, что функция г - строго выпуклая, и найдите решение задачи методом квадратичного программирования.
21.2.3. Геометрическое программирование
В геометрическом программировании рассматриваются задачи нелинейного программирования специального вида. Подход геометрического программирования позволяет находить решение исходной задачи с помощью соответствующей двойственной задачи.
Методами геометрического программирования решаются нелинейные задачи, в которых как целевая функция, так и функции ограничений имеют следующий вид:
г = /(Х) =
uj=cjfl*?> У = Ь2,...,Л.
Предполагается, что здесь все с;. > 0, а число N является конечным. Показатели степени atj по знаку не ограничены. Функция /(X) имеет вид полинома, если не учитывать того, что показатели степени atj могут принимать отрицательные значения. По этой причине, а также в связи с тем, что все коэффициенты с; > 0, функция /(X) называется позиномом.
В этом разделе будут рассмотрены задачи геометрического программирования без ограничений. Исследование задач геометрического программирования с ограничениями выходит за рамки настоящей главы. Детальное рассмотрение излагаемых здесь вопросов содержится в книге [2], глава 6.
Рассмотрим задачу минимизации позиномиальной функции /(X). Будем называть эту задачу прямой. Предполагается, что переменные xt принимают строго положительные значения, т.е. область xt < 0 недопустима. Далее будет показано, что требование х Ф 0 является существенным при получении основных результатов.
Первые частные производные функции z в точке минимума должны обращаться в нуль. Следовательно,
Поскольку по предположению все хк > 0, имеем
= 0 = -JXt/., А =1,2,...,я.
Эх x,
к У-1
Пусть z - минимальное значение функции z. Очевидно, что z > 0, так как z - по-зином, и все хк > 0. Обозначим
Из определения следует, что у1 > 0 и X-i-vj = Величина yt характеризует относительный вклад у-го слагаемого V в оптимальное значение целевой функции z. Необходимые условия экстремума теперь можно записать в следующем виде.
I>V,=0. к = 1,2.....я.