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

Для решения аппроксимирующей задачи можно использовать также обычный симплекс-метод (глава 3), дополненный правилом ограниченного ввода в базис. В этом случае игнорируются вспомогательные ограничения, содержащие у*. Согласно данному правилу в базисе может находиться не более двух положительных весовых коэффициентов if. Более того, два коэффициента if могут быть положительными лишь тогда, когда они являются смежными. Таким образом, строгое условие оптимальности симплекс-метода только тогда используется для выбора переменной /*, подлежащей введению в число базисных, когда она удовлетворяет

указанным выше требованиям. В противном случае анализ разностей (z* -с*) позволяет выбрать следующую переменную if , которая может быть сделана базисной. Процесс повторяется до тех пор, пока не будет выполнен критерий оптимальности или же установлена невозможность введения в базис новой переменной /* без

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

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

Пример 21.2.1

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

Максимизировать z = х, + х\

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

Зх, + 2х; < 9, хр х2 > 0.

Точное оптимальное решение этой задачи находится непосредственной проверкой: х, =0, х2 = 2,12 и г* = 20,25. Чтобы продемонстрировать использование метода аппроксимации, рассмотрим отдельные функции

/,(*,) = *,> *>(*>) = 3jfi-

g;(x2) = 2xl

Функции/,(х,) и gl(xt) остаются в исходном виде, поскольку они уже являются линейными. В этом случае дг, рассматривается как одна из переменных. Для функций /2(х2) и g~{x,) полагаем, что количество точек разбиения равно четырем (Кг = 4). Так

как значение* не может превышать 3, отсюда следуют данные, приведенные ниже.

Получаем

fM) = t\fM) + if( Ч) + If,) + t.f, №) =

= 0 х t\ +1 х t2 +16 х t\ + 81 х f4 = i; +1 btl + 8 If*.

Аналогично

£,2(x,) = 2f2+8f3 + 18f:4. Следовательно, аппроксимирующая задача принимает вид

максимизировать z = х, +t; + 16f3 + 8 If4

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

Зх,+2f;+8f,3+18f24<9, t\+t;+tl+!* = {, f* >0, Jt = 1,2,3,4, xO.

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

Здесь 5, (> 0) - дополнительная (остаточная) переменная. (В этой задаче начальное решение является очевидным. В общем же случае для его получения могут понадобиться искусственные переменные, см. раздел 3.4.)

Коэффициенты г-строки указывают на то, что в число базисных необходимо ввести переменную /*. Поскольку при этом переменная t\ уже входит в базисные в силу

правила ограниченного ввода в базис, она должна быть выведена из числа базисных перед тем, как базисной станет переменная /,4. Вместе с тем, согласно условию допустимости при введении в базисные переменной t* переменная s, должна выводиться из базиса. Это значит, что t\ нельзя сделать базисной. Следующей подходящей для введения в базисные является переменная t\. Снова при этом переменная t\ должна быть выведена из числа базисных. Условие допустимости на этот раз позволяет вывести из числа базисных переменную t\, что и требуется. Таким образом, получаем новую симплекс-таблицу.

Очевидно, что базисной следует сделать переменную t\ . То, что переменная t\ уже

является базисной, не противоречит правилу ограниченного ввода в базис. В соответствии с симплекс-методом переменная s, исключается из числа базисных. Получаем следующую симплекс-таблицу.

Из этой таблицы следует, что в базис могут вводиться переменные t\ и t;. Переменная t\ не может быть базисной, поскольку не является смежной с переменными / и /2, которые уже находятся среди базисных. Далее, переменную гг также нельзя сделать базисной, поскольку t* нельзя исключить из числа базисных. Поэтому

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

Воспользуемся найденными значениями t\ = 9/10 и(= 1/10, чтобы выразить полученное решение через переменные х, их,. Получаем

х, = 0, х2~ 2t32+3t4=2j+3j=2,l, z = 0 + 2,14 = 22,5.

Полученное приближенное оптимальное значение для хг (=2,1) мало отличается от истинного оптимального значения (= 2,12).

Сепарабельное выпуклое программирование. Задача выпуклого сепарабельного программирования возникает в том случае, когда функции g!(xt) являются вы-