ЭПИЦЕНТРЫ
Многих сегодня прямо-таки умиляет, как компьютеры помогают нашему самовыражению. Вот только сидящего во мне инженера коробит, сколько же тратится энергии, пока пользователь формулирует свою мысль. Сейчас, например, в то время как я думаю над следующим словом для своей колонки, ЦПУ моего ноутбука каждую секунду выполняет миллиард рабочих циклов - и все это впустую.
Лично меня приводит в восторг мощь компьютера, которая помогает принимать правильные решения и эффективно использовать ресурсы. Наверное, поэтому майское сообщение о смерти Джорджа Данцига произвело на меня особое впечатление. Этот ученый разработал методы линейного программирования, лежащие в основе современного планирования.
Чтобы лучше понять суть линейного программирования, представьте себе мебельную фабрику, выпускающую два вида кресел. Одна модель обита тканью и отделана кожей, а другая - покрыта кожей с тканевой отделкой. В каждое такое кресло вложен труд и кожевников, и драпировщиков, но в разной пропорции. Таким образом, себестоимость кресла состоит из четырех основных компонентов: стоимости кожи и ткани, оплаты труда кожевников и драпировщиков - плюс некоторые дополнительные расходы. При этом между производственными затратами и объемом выпуска продукции существует линейная зависимость. Другими словами, чтобы выпустить в два раза больше кресел, нужно затратить вдвое больше материала и труда.
Доходы фабрики также можно моделировать по линейному закону: сумма прибыли по каждому виду продукции пропорциональна количеству произведенных изделий минус фиксированные расходы на организацию производства.
Однако необходимо учитывать, что доступное количество человеко-часов не беспредельно. Максимальное значение этого параметра определяется тем, сколько специалистов может одновременно работать на фабрике. При желании его можно оценить количеством человеко-часов в рабочее время по одному тарифу оплаты и объемом сверхурочной работы по более высоким ставкам. "Линейная программа" решения задачи в данном случае строится на основе "целевой функции" (общей прибыли), которая в приведенном примере должна иметь максимальное значение с учетом имеющихся ограничений.
Решить такую задачу, равно как и другие задачи максимизации и минимизации, можно графически, с помощью карандаша и прямоугольника. Полученный график позволит также определить, какие ресурсы стоит пополнить в первую очередь или какие ограничения имеет смысл ослабить.
Но на практике очень часто возникают задачи, где количество переменных и ограничительных условий исчисляется десятками, а то и тысячами. Надежно и эффективно решать их позволяет предложенный в 1947 г. алгоритм декомпозиции Данцига, с помощью которого планировщик может анализировать многочисленные сценарии производства.
Работы Данцига стали главным стимулом использования компьютеров для планирования в деловой и военной сферах. "До 80-90-х годов, когда компьютеры начали широко применяться в электронной почте и Всемирной паутине, больше всего машинного времени расходовалось на алгоритм декомпозиции при решении задач линейного программирования. Без этого алгоритма не может существовать и вести дела ни одна крупная организация" - так заявил профессор Стэнфордского университета Кит Девлин, выступая 21 мая по национальному радио по случаю смерти Данцига.
На этом фоне одно из достижений революции настольных вычислительных систем выглядит особенно сомнительным. Мэйнфреймы, как известно, для поиска и обоснования оптимального решения использовали сценарии декомпозиции. Так почему же на персональных компьютерах мы тратим по меньшей мере столько же циклов ЦПУ на манипуляцию с электронными таблицами по методу проб и ошибок? Причем без какой-либо гарантии выдачи наилучшего результата из всех возможных. Вместо того чтобы использовать свой опыт и знания для совершенствования производства и практической оценки точности сделанных допущений, специалисты расходуют массу драгоценного времени на то, с чем вот уже полвека гораздо лучше справляется алгоритм Данцига.
Зачем нужен этот мартышкин труд? Ведь можно воспользоваться надстройкой Solver для Excel или расширением для электронных таблиц стороннего производителя (например, Premium Solver Platform фирмы Frontline Systems). Можно взять на вооружение функции линейного программирования профессиональных математических пакетов наподобие Mathematica фирмы Wolfram Research, Matlab или Optimization Toolbox компании MathWorks. Так или иначе, но пора уже вновь открыть для себя старую истину: задачу нужно прояснить так, чтобы ее можно было запрограммировать - не говоря уж о том, чтобы решить.
С редактором Питером Коффи можно связаться по адресу: peter_coffee@ziffdavis.com.
