Юный техник 1985-08, страница 53

(2Xi+3X2^12). Она пересекает АВ в точке Е. Любая точка внутри или на границе четырехугольника ОСЕВ представляет возможное решение нашей задачи. Обратите внимание: точка Е как раз отвечает наилучшему, оптимальному решению. Случайно ли это?

Надеемся, что вы поняли суть графического решения задачи линейного программирования. К сожалению, этот способ хорошо работает только при малом количестве переменных, в самых простейших задачах. В реальной ситуации, когда переменных много, компьютеру приходится отыскивать оптимальное решение, переходя от одной к другой грани огромного тысячегранного тела. Процедура эта медленная, и если число переменных превышает 15—20 тысяч, то симплекс-метод, по словам математиков, «выдыхается». Недавно 25-летний математик Нарендре Кар-макар нашел новый способ решения задачи линейного про

4 «Юный техник» № 8

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

Во саду ли, в огороде...

И здесь может помочь линейное программирование. Представьте себе, что ваш пришкольный участок площадью S вы решили засеять тремя культурами (какие это культуры конкретно, неважно). Урожайность первой — У| кг/м², второй — У₂ кг/м и третьей — Уз кг/м². Под первую надо внести Pi кг удобрений на мпод вторую — Р2 и под третью — Рз, а всего вы имеете П кг удобрений. Постарайтесь найти посевные площади под каждой культурой так, чтобы урожай был наибольшим. При этом не забудьте о возникающих ограничениях. Составьте задачу линейного программирования, задайтесь конкретными цифрами и попробуйте ее решить. Какие еще задачи на отыскание наилучшего решения вы можете придумать?

С. ВОЛКОВ Рисунки Г. ЗАСЛАВСКОЙ 49