, g/K)-g/K-u)
Pt; -
Задача максимизации преобразуется аналогично. В этом случае р„ >p2l >...>pKl,
откуда следует, что при р < q переменная х всегда будет входить в решение раньше хд1 (см. упражнение 21.2.1.7).
Полученную задачу можно решить симплекс-методом, предназначенным для решения задач с ограниченными сверху переменными (раздел 7.3). При этом исчезает необходимость в соблюдении правила ограниченного ввода в базис, поскольку выпуклость (вогнутость) функций гарантирует надлежащий выбор переменных.
Пример 21.2.2
Рассмотрим задачу
максимизировать z = х, - х2
при ограничениях
Зх4+х2<243, х1+2х\<Ъ2, х,>2,1, х2>3,5.
Отдельными (сепарабельными) функциями этой задачи являются
У!(*.) = *.. Ь{хг) = ~хг< «j(x1) = 3x14, g\{x2) = x2,
gl{*\) = x\> gl{xi) = 2xl-Эти функции выпуклые, что и требуется в задачах минимизации.
Область допустимых значений переменных хх и х2, как следует из ограничений задачи, определяется неравенствами 0<Xj<3 и 0<х2<4. Разбиваем эти интервалы изменения переменных х, и х2. Пусть А", = 3 и К2 = 4 при а01 = а02 = 0. Значения тангенсов углов наклона, соответствующих отдельным функциям рассматриваемой задачи, приведены в следующих таблицах.
Для i = 1 имеем
| | U (вил) = вил | | *i(a.i) = 3a*i | | S.2(a.i) = ati | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| | | | | | | | |
Для i = 2 имеем
Теперь задача принимает следующий вид.
Минимизировать z ~ хп + х21 + х31 - х12 - х22 - х32 - х42 при ограничениях
Зхи + 45х21 + 195х31 +х12 +х22 + х32 +х42< 243, хп +х21 +х31 + 2х12 + 6х22 + Юх32 + 14х42 < 32, хп +х21 "Ьх31 2,1,
*12 + 22 + 32 + Xi2 S 3,5,
0<xtl < 1, к= 1, 2, 3, 0<xi2< 1,к= 1,2,3,4. С помощью программы TORA получено следующее оптимальное решение:
z = -0,52, хп = х12 = 1, х13 = 0,98, х21 = х22 = х23 = 1, х24 = 0,5. Отсюда получаем решение исходной задачи (х,, х2) = (2,98, 3,5).
УПРАЖНЕНИЯ 21.2.1
1. Для следующей задачи постройте аппроксимирующую модель в виде задачи частично-целочисленного программирования.
Максимизировать z = е~х + х, + (х2 +1)2
при ограничениях
х,2 + х2 < 3, х,, х2>0.
2. Решите аппроксимирующую задачу из предыдущего упражнения, используя правило ограниченного ввода в базис. Затем найдите оптимальное решение исходной задачи.
3. Рассмотрите следующую задачу.
Максимизировать z = х,х2х3
при ограничениях
х,2 + х, + х3 < 4, х,, х2, х3 > 0.
Постройте аппроксимирующую задачу в виде задачи линейного программирования с учетом дальнейшего использования правила ограниченного ввода в базис.
4. Покажите, каким образом приведенная ниже задача может быть приведена к сепарабельному виду.
Максимизировать г = х,х2 + х3 + х,х3
при ограничениях
х,х2 + хг + х,х3 < 10,
5. Покажите, каким образом следующую задачу можно преобразовать в задачу сепарабельного программирования.
Минимизировать z = е2"*"*2 + (х3 - 2)2
при ограничениях
х, + х2 + х3 < 6, хх,х2, х3>0.
6. Покажите, как следующую задачу можно преобразовать в задачу сепарабельного программирования.
Максимизировать z = eVl + XjX3 + х4
при ограничениях
хх + х2х3 + х3 < 10,
х4 не ограничена в знаке.
7. Покажите, что при реализации метода выпуклого сепарабельного программирования оптимальное решение не содержит переменной хк1 > 0, если переменная хк Х1 не достигает своей верхней границы.
8. Решите представленную ниже задачу как задачу выпуклого сепарабельного программирования.
Минимизировать z-xf + 2х2 + х]
при ограничениях
х2 + х, + Хз < 4,
х,+х,<0,
х„ х3>0, х2 не ограничена в знаке.
9. Решите как задачу выпуклого сепарабельного программирования следующую задачу.
Минимизировать г = (х, - 2)2 + 4(х2 - б)2 при ограничениях
6х, + 3(х2 + 1)2< 12, хх, х2>0.