Путешествие в космос

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

Итак, представим, что наш космический корабль приближается к одной из планет соседней галактики. Взревели тормозные двигатели, и звездолет мягко касается посадочной площадки.

— Топливо — нуль,— объявляет бортовой компьютер.

Это значит, что бак звездолета пуст. Нужно заправиться. Выглядываем в иллюминатор и видим заправочную станцию. На станции два вида топлива (естественно, оно необычно); топливо номер один называется «Антигравитон-10», другое — «Антигравитон-7», сокращенно А-10 и А-7. Цифра в названии топлива показывает, сколько часов можно пролететь на одном его литре; топливный бак звездолета вмещает 5 л.

Какое же топливо выбрать? Очевидно, А-10 эффективнее, но 1 л его весит 3 кг, а общий вес топлива на борту нашего хосмолета не должен превы-иать 12 кг. Литр А-7 весит 2 кг. Можно залить им полный бак, он будет весить всего 10 кг, но запас хода окажется равным 35 часам.

Есть еще вариант: залить в бак сразу оба сорта топлива (они не перемешиваются) и использовать их поочередно. Но какого топлива сколько взять на борт?

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

Итак, 1 л антигравитона А-7 — это 7 часов полета. Значит, если мы возьмем на борт Х₁ литров, то летное время составит 7Х₁ часов. Точно так же Х₂ литров А-10 гарантируют нам 10Х₂ летных часов, а всего летное время составит Т = 7Х₁ + 10Х₂ часов.

Наша цель — сделать летное время Т как можно больше, но при этом нужно учесть, во-первых, что топливный бак вмещает всего 5 л. Значит, общий объем горючего не может превышать это значение, то есть

Х₁ + Х₂ < 5

Во-вторых, вес топлива не должен превышать 12 кг. Литр А-10 весит 3 кг, значит, общий вес топлива этого сорта будет ЗХ₂, а литр А-7, как сказано, весит 2 кг. Его вес равен 2X₁, a всего горючее весит 2Х₁ + ЗХ₂.

У нас получилась следующая задача:
максимизировать Т = 7Х₁ + 10Х₂
при ограничениях:
Х₁ + Х₂ ≤ 5,
2Х₁ + ЗХ₂ ≤ 12.

Для решения ее прежде всего надо заменить неравенства равенствами. Если мы зальем меньше 5 л топлива, то какой-то объем бака останется неиспользованным, обозначим его через Х₃ Тогда сумма объема топлива и пустой части бака даст нам как раз 5 л, то есть Х₁+Х₂+Х₃=5.

Точно так же поступим и с весовым ограничением. Неиспользованный вес назовем X₄ и в конце концов перепишем нашу задачку так:
Т — 7Х₁ — 10Х₂ = 0
Х₁ + Х₂ + Х₃ = 5
2Х₁ + ЗХ₂ + Х₄ = 12

Любое решение этой системы даст нам объемы каждого сорта топлива, полетное время и величины неиспользованных объема и веса. Но переменных пять, а уравнений только три, значит, система имеет не одно решение. Мы должны найти такое, когда Т—летное время — будет максимальным. Предположим, что мы вообще не заправили космолет, то есть Х₁=Х₂=0. Тогда, естественно, летать просто невозможно, Т=0, а Х₃=5 и Х₄=12. Мы получили одно из решений нашей системы, конечно, не наилучшее. Это решение называют исходным опорным планом. Переменные, входящие в опорный план, называют базисными переменными или просто базисом. 6 нашем случае это Т, Х₃ и Х₄. Обратите внимание: каждая базисная переменная входит только в одно уравнение и коэффициент при ней равен 1. Так как же улучшить опорный план?

Для начала начнем заправку космолета. Только не будем заливать оба сорта топлива сразу, возьмем только один. С точки зрения математики это будет означать, что либо Х₁ — объем А-7, либо Х₂ — объем А-10 — станет отличным от нуля, то есть одна из этих переменных пойдет в базис. Какое же топливо залить, или, что то же самое, какую переменную ввести в базис? Наверное, Х₂. А-10 эффективнее, и введение в базис Х₂ сильнее влияет на Т. Это видно и из нашей системы. В самом деле, коэффициент при Хг равен 10. Значит, увеличение Х₂ на 1 уменьшает левую часть на 10. Чтобы равенство сохранилось, приходится увеличить Т тоже на 10. Тогда как увеличение на единицу Х₁ приводит к возрастанию Т только на 7. Вот мы и получили первое правило симплекс-метода: в базис вводится та переменная, которая имеет наибольший по абсолютной величине отрицательный коэффициент. А количество А-10, которое нужно залить, определяют ограничения. Ведь при заполнении бака уменьшаются пустой объем Х₃ и неиспользованный вес Х₄. Какая-то из этих величин в конце концов обратится в нуль—или бак окажется наполнен, или лимит веса будет исчерпан.

А это, кстати, означает, что переменная, которая стала равной 0, исключится из базиса. Какую же исключить — Х₃ или Х₄?

Из второго соотношения следует, что если X₂ увеличить на 1, то Х₃ уменьшится на столько же. А начальное значение пустого объема было 5. Значит, максимальная величина X не может быть больше 5. Ведь нельзя залить топлива больше, чем вмещает бак.

В третьем соотношении увеличение Х₂ на единицу уменьшает X₄ сразу на 3, ведь 1 л весит 3 кг. Именно на столько убывает неиспользованный вес при добавлении каждого литра топлива. А всего можно залить 12 : 3 = 4 л. В результате получаем, что Х₂ не превышает 4. Ну что ж, зальем 4 л А-10, при этом лимит веса будет исчерпан 2X₄=0. Эта переменная исключается из базиса, а вместо нее входит Х₃.

Вот мы и получили второе правило симплекс-метода: новая базисная переменная увеличивается до тех пор, пока какая-нибудь из переменных старого базиса не обратится в нуль. Теперь в новый базис входят Т, Х₃ и Х₂. Значит, надо соответственно преобразовать систему уравнений, чтобы Х2 присутствовало только в одном уравнении, в третьем, с коэффициентом 1.

Для этого разделим последнее уравнение на 3, затем вычтем его из второго. Тогда переменная X₂ исключится из второго уравнения. Потом исключим X₂ и из первого.

Роль бортового компьютера поручим микрокалькулятору. Прежде всего разделим на 3 все коэффициенты третьего уравнения. Получим:
0.666667Х₁ + Х₂ + 0,ЗЗЗЗЗЗХ₄ = 4,
теперь вычтем из его второго — 1; «-»; 0,666667;=.

На индикаторе появится число 0,333333. Наша система уравнений примет такой вид:
Т — 0,ЗЗЗЗЗЗХ₁ + 3,333333X₄ = 40,
0.333333Х₁ + Х₃ — 0,333333X₄ = 1
0.666667X₁ + X₂ + 0,333333X₄ = 4.

Теперь все переменные, кроме базисных — Т, Х₃ и Х₂,— полагаем равными 0 и получаем: Т=40, Х₃=1, Х₂=4. Это уже неплохо: 40 часов полета. Но можно сделать и лучше. В первом уравнении коэффициент при Х₁ отрицателен, значит, вводя в опорный план эту переменную, можно увеличить Т. А для этого еще раз проделаем подобные вычисления, исключим Х₁ из первого и третьего уравнений, а во втором коэффициент сделаем равным 1. Вот что получится:
Т + Х₃ + ЗХ₄ = 41
Х₁ + ЗХ₃ — Х₄ = 3
Х₂ — 2Х₃ — 0,ЗЗЗЗЗЗХ₄ = 2.

Отсюда ясно, что если залить 3 л А-7 и 2 л А-10, тогда наш космолет сможет летать 41 час. Пора давать задание роботу-заправщику.

Помогают графики

Задача, которую мы решили, не случайно названа задачей линейного программирования. Дело в том, что все переменные входят в уравнения и неравенства в первой степени, или, как говорят математики, линейно. А теперь давайте посмотрим, не поможет ли нам график в решении задачи линейного программирования. Только прежде условимся, что оси координат мы будем называть не X и У, а X₁ и X₂. Давайте возьмем одно из ограничений нашей задачи Х₁ + Х₂ ≤ 5 и найдем на координатной плоскости те точки, которые ему удовлетворяют (считая, что Х₁ и Х₂ больше нуля). Сначала рассмотрим равенство Х₁ + Х₂ = 5. Построим график этой линии. Для этого найдем две точки: если Х₁=0, то Х₂=5 (точка А), и наоборот, Х₁=5, a Х₂=0 (точка В). Соединим точки А и В (см. рис.). Неравенству задачи удовлетворяют точки, лежащие внутри треугольника ОАВ. Координаты каждой из них определяют величины переменных Х₁ и Х₂. Аналогично проведем прямую CD, определяемую вторым ограничением (2X₁ + 3X₂ ≤ 12). Она пересекает АВ в точке Е. Любая точка внутри или на границе четырех угольника ОСЕВ представляет возможное решение нашей задачи. Обратите внимание: точка Е как раз отвечает наилучшему, оптимальному решению. Случайно ли это?

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

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

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

С. ВОЛКОВ

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

Словарик

ПРОГРАММА. Представьте, что нам надо сложить на калькуляторе два числа. Вряд ли кто-нибудь при этом станет нажимать произвольно клавиши. Нет, действовать придется, отдавая себе команды — ввести первое число, нажать одну клавишу, ввести второе число, нажать другую клавишу, прочитать ответ. По сути дела, мы имеем дело С программой — набором команд, котдрые надо выполнить, чтобы получить результат.
При решении задачи на ЭВМ программу составляют заранее и записывают в память машины вместе с исходными данными. Затем управляющее устройство компьютера извлекает команды из памяти и по ним ведет вычисления. При работе с калькулятором программу приходится держать в голове или выписать на бумагу.

ЦИКЛ — серия команд программы, которые выполняются многократно. Использование циклов позволяет строить программы, выполняющие гораздо больше команд, чем их количество в самой программе.
С простейшим циклом мы уже встречались в рассказе о де Мере, когда возводили 35/36 в 24-ю степень. При этом мы многократно, точнее 23 раза, выполняли одну и ту же команду. Другой пример — в прошлом выпуске. Мы выяснили, как калькулятор извлекает квадратный корень. Но в этом случае цикл был заложен в программу вычисления корня, имеющуюся внутри калькулятора. Дело в том, что калькулятор извлекает квадратный корень по программе, заложенной в него,— он несколько раз проводит вычисления по одной и той же формуле, получая все более и более точные значения.