Выбор наилучшего варианта

37

Выбор наиболее варианта

Кандидат физико-математических наук
В. Л. ГУТЕНМАХЕР,
.J.K. М. РАБВОТ

В младших классах, а также на вступительных экзаменах вузы, часто предлагают задачи на составление уравнений. При этом приходится, во-первых, занимать переводом условий с общного языка на математический, а во-вторых, решать полученные уравнения и неравенства.
В тексте задачи описана какая-нибудь ситuation и требуется по одним указанным данным определить другие. Вот, например, первые и последние фразы условий задачи из учебника алгебры для 7 класса:
«Две машинстики получили для перечатки рукопись… За сколько часов могла бы перечатать рукопись каждой машинства?»
«Катер отправился от речного вокзала вниз по течению… Сколко времени затратил волосипедист на пути от города до турбазы?»
«Сплав меди с цинком, содержащий 5 кг цинка, сплавлен с 15 кг цинка… Какова была первоначальная масса сплава?»
Важно уметь решать такие задачи, так как в произвольенной и экономической практике часто приходится подводить итоги, перечитывать и суммировать различные показатели, анализировать работу предприя-

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

Постановка и решение таких задач является предметом математического программирования. Однако из первых, кто использовал математку в подобных вопросах, был советский математик, академик Л. В. Канторович (1912—1986). В 1939 г. вышла его книга «Matематические методы организации и планирования произвольства». Во введении к этой книге он писал:

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

С тех пор прошло много лет, и математическое программирование стало целой наукой, основанной на эко-

38

номико-mатематических методах и широко использовей ЭВМ.

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

Где построить баню? В деревне Мочалкино 100 жителей, а в деревне Веники — 50 жителей. В каком месте шоссе, соединяющего эти деревни, надо построить баню, чтобы общее расстояние, которое придется прочит по шоссе всем 150 жителям до бани, было наименьшим?

Переведем условие задачи на математический язык. Пусть расстояние по шоссе между деревнями равно a км и баня находится между деревнями в x км от Мочалкино, тем самым 0≤x≤a. Тогда все 100 жителей этой деревни прочит до бани 100x km, а все 50 жителей деревни Веники — 50(a-x) km. Всего будет прочитено S=100x+50(a-x) км.

Итак, мы получили следующую математическую задачу: найти наименьшее значение величины S=50x+50a при условии, что 0≤x≤a, где a — фиксированное число.

Решить задачу очень легко: достаточно заменить, что величина S уменьшается с уменьшением x, поэтому наименьшее значение S будет при наименьшем возможном значении x, то есть при x=0, и тем самым строить баню нужно в деревне Мочалкино.

Обсудим полученный результат. Почти все, кому мы задавали вопрос, где построить баню, сразу ответили, что ее надо построить в месте, расстояние от которого до деревни Мочалкино в два раза меньше расстояния до деревни Веники. Наверное, у них возникла такая физическая модель: представляются качели, на одном конце доски сидит человек, в два раза более тяжелый, чем сидящий на другом конце.

Если баня будет находиться на расстоянии a/3 от Мочалкино, то все жители вместе прочит до бани такой же путь, что и жители Веников:

100·a/3=50·2a/3. Наверное, это каждая более справедливым, если имеет в виду не всех жителей, а противопоставлять одну деревню другой и искать «точку равновесия». Но это будет решение совсем другой математической задачи: при каком значении x, где 0≤x≤a, величина f=|100x-50(a-x)| будет наименьшей?

Конечно, слова «наилучший вариант» могут пониматься совершенно по-разному. Чтобы в них точный смысл, мы составляем целевую функцию. В нашей задаче это была функция S=50x+50a, а в другом варианте — функция f=|150x-50a|. Найдя x, при котором целевая функция принимает наименьшее значение, мы получили наилучший (с определенной точки зрения) вариант.

Ясно, что жители деревни Веники могут оказаться не в восторге ни от одного из этих вариантов и, возможно, могут вывинуть против них довольно вскоре аргументы. Складем, что стариков и детей у них больше, а машин — меньше, чем в Мочалкино, что у них есть водопровод, а в Мочалкино — нет и т.п. Но если все это учесть, то получится совсем другой математической задача — другой математической модель.

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

Здесь выбор целевой функции в принципие ясен (наименьшая затрата времени), но оптимальное решение зависит не только от числа рабочих в разных цехах, но и от особен-

39

ности производства и других факторов.

Лучший способ добрать до вокзала. Петру Петрович надо срочно добрать до вокзала. Он может вызвать такси, которое придет ядать 24 минуты, и ехать со скоростью 30 km/ч, а может идти пешком со скоростью 6 km/ч. Как ему лучше поступить, если расстояние от дома до вокзала: а) 2 км; б) 3 км; с) 5 км?

Чтобы нагладнее сравнить движение пешхода и автоматили, мы ведем еще один персонал — jenу Петра Петровича.

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

Подсчитаем время, через которой она его доогнит. Через время $t$ после своего выхода из дома Петр Петрович будет находиться на расстоянии 6т км от дома, а при $t > 24$ мин=2/5 ч такси пройдет 30(t—2/5) км.

Такси может догнать Петра Петровича в момент, когда

$$6t = 30(t - 2/5),$$

то есть при $t = 1/2$ ч. Если до вокзала меньше, чем 1/2 ч хода, жена не успет догнать мужа, если же больше, чем 1/2 ч, то она его доогнит и подвезет на вокзал. За $t = 1/2$ ч Петр Петрович может удалиться от дома на 3 км. В результате этих расхождения мы приходим к следующему выводу.

Если расстояние до вокзала меньше 3 км, как в случае $a$), Петру Петрович лучше идти пешком; если равно 3 км, то все равно — пешком или на такси; а если больше 3 км, как в случае $b$) — лучшие вызвать такси.

Для лучшего понимания решения полезно представить графическое изображение молчально сделан ряд предположений: пешход и такси движут равномерно, вызов и выезд такси проискают мгновенно (на практике это далеко не так) и т.п. Кроме того, по нашему условиядля Петра Петровича самим ценным было время. Но в случае $b$) мы столкнулись с тем, что нашлось два равноценных с этой точки зрения варанта. Для выбор одного из них нужно другое сообщение: или стоимость поездки (тогда он, скорее всего,ойдет пешком), или удобства (тогда он поедет на такси).

Один велосипед на двойх. Два брата, Коля и Сережа, хотя добраться до бабушки, живущей от них в 40 км. У них есть один велосипед, на который они подрузили вещи. Коля ходит пешком со скоростью 6 km/ч, а ездит на велосипеде со скоростью 20 km/ч; скорости Сережа — соответственно 4 km/ч и 30 km/ч. Велосипед можно оставлять на дороге без присторма. Как им вместе быстрее всего добраться до бабушки?

Предположим, что брата прибывает к бабшке одновременно, и найдем время, за которой они могут это сделать. Затем мы покажем, что за меньше времени один из них не сможет добраться до бабшки.

Пусть Коля $x$ км проехал на велосипеде и $(40-x)$ км проехал пешком, а Сережа, наоборот, проехал $x$ км, а проехал $(40-x)$ км.

Тогда Коля затратил на дорогу $(x/20+(40-x)/6)$ часов, а Сережа — $(x/4+(40-x)/30)$ часов.

Если они приближены одновременно,

$$\frac{x}{20} + \frac{40-x}{6} = \frac{x}{4} + \frac{40-x}{30}.$$

41

$$m = \frac{2}{15} + \frac{7}{15} y,$$

которая принимает наименьшее значение при наименьшем возможном значении $y = 0$. Если мы выражали $m$ не через $y$, а через $x$ или через $z$, то было бы сложнее выяснить, на каком промежутке надо искать ее наименьшее значение. Как лучше выбирать, к какой переменной свойить функцию — это тоже важная задача.

Можно было бы обойтись без этих выкладок, если подметить следующие обстоятельства. Чтобы новый сплав содержал 40% кobalта и как можно меньше меди, надо, чтобы в нем было как можно больше никеля. Поэтому второй сплав, который, казалось бы, хорошо тем, что в нем уже 40% кobalта, лучше вообше не трогать, так как в нем совсем нет никеля — см. таблицу. Значит, надо смешать первый и третьий сплавы. Пусть мы взяли $a$ кг первого сплава, тогда надо взять $(1-a)$ кг третьего. В новом сплаве будет содержаться 0,6(1-a) кг кobalта. По условию 0,6(1-a)=0,4, поэтому $a=1/3$, что приводит к ответу.

Новогодняя задача*). На 100 руб. решение купить.elочных церрушек. Елочные церрушки продаются наоборот. Набор, состоящий из 20 церрушек, стоит 4 руб., набор, состоящий из 35 церрушек, стоит 6 руб., набор, состоящий из 50 церрушек, стоит 9 рублей. Сколько и каких наборов нужно купить, чтобы было куплено наименьшее количество церрушек?

Одна церрушка в первом наборе стоит 1/5 руб., во втором наборе — 6/35 руб., в третьем наборе — 9/50 руб. Упорядочим эти числа: 6/35<9/50<1/5. Итак, самые дешевая игрушки во втором наборе, а самые дорогие — в первом.

Чтобы купить на 100 руб. как можно больше церрушек, нужно, конечно, купить побольшие девевых церрушек. Самое большое, мы можем купить 16 наборов по 6 руб. и затратить на это 96 руб.

Остаются 4 руб., на которые можно лишить купить первой набор. Все мы купим таким способом 16·35+20=580 церрушек.

Скорее всего, это самый лучший вариант. Проверим все-tаки еще такой: если купить 15 шестигрублевых наборов, то остается 10 руб. Мы можем тогда купить еще один девятый гублевый набор или два четырехгублевых. И в том, и в другом случае количество церрушек оказывается меньше, чем в первом варианте.

Итак, надо купить 16 наборов по 6 руб. и 1 набор за 4 руб. При этом будет закуплено 580 церрушек.

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

Наши рассудения правдоподобны, но, вообше говоря, мы перебрали не все возможные варианты. Поэтому приведем более строгое решение.

Пусть $x$ — количество наборов I типа, $y$ — II типа, $z$ — III типа. Надо найти такие неотрицательные

42

числа $x$, $y$ и $z$, чтобы выполнялись условия $4x+6y+9z \leq 100$ и чтобы величины $S=20x+35y+50z$ были наиболее.

Поскольку

$$4x+6y+9z = \frac{6}{35}S + \frac{4}{7}x + \frac{3}{7}z \geq \frac{6}{35}S,$$

получается, что $\frac{6}{35}S \leq 100$, откуда $S \leq 583\frac{1}{3}$.

Так как $S=20x+35y+50z$ — целое число, делящаяся на 5, имеем $S \leq 580$. При $x=1$, $y=16$, $z=0$ все условия выполняются и $S=580$.

Эта задача относится к целочисленному программированию, которое является одним из наиболее сложных разделов математического программирования.

Задания

1. Трех молодых продавцов — Юрия, Якова и Льва — распределили на работу в универсаг. Директору универсмаги нужно направить одного из них в отдел радитоваров, другого — в отдел музыкальных инструментов, а третьего — в отдел фототоваров. Директор поросил психолога помочь ему проверсти это назначение наличищим образом. Психолог провод с ними беседу и оценил знания каждого

| РАДИО | ФОТО | МУЗЫКА |
| :— | :— | :— |
| Юрий | 5 | 4 | 7 |
| Яков | 6 | 7 | 3 |
| Леб | 8 | 11 | 2 |

во всех трех областях в баллах. Затем он составил таблицу и представил ее директору универсмага. Как директору распределить новичков, чтобы сумма соответствующих баллов была наиболее? (Например, если Юрия назначит в радиотелел, Якова — в музыкальный, а Льва — в фотоотдел, то сумма баллов будет равна $5+3+11=19$).

2. На сковородке, вместеошёл две котлеты, можно их поджарить с обеих сторон за 10 минут. Как быстрее всего поджарить на этой сковородке 3 котлеты?

3. Даны две точки, $A$ и $B$, расположенные по одному сторону от данной прямой. Как расположить на этой прямой отрезок МК данной длины $a$, чтобы ломана AMKB имела наименьшую длину?

4. Три братьки один вложен, и им нужно добавить до дома, находящемся в 30 км от магазина. Каждый из братьев ходит пешком со скоростью 4 км/ч, а ездит на вложенце со скоростью 20 км/ч. За какое наименьшее время они могут добавиться до дома? (Вложенем можно оставлять на дороге без пристма.)

5*) Малыш может съеть торт за 10 минут, банку варенья — за 8 минут и выпить пакет молока за 4 минут. Карлсон может это сделать соответственно в 2 раза быстрее. За какое наименьшее время они могут вместе покончит с завтраком, состоящим из торта, банки варенья и пакета молока?

6. В каждом из четырех содержится по 1 л смеси кислоты с водой. Процентное содержание кислоты в них равно 10%, 30%, 60%, 80% соответствует. Лаборатору нужно получить 50%-ю смесь кислоты с водой. Какое наименьшее количество таких смеси он может получить, сливая смеси из данных сосудов?

7. Нужно изготовить сплав, содержащий 40% олова. На складе имеются 3 сплава с 60%, 10% и 40% содержанием олова. Цена 1 кг каждой из имеющих сплавов равна 4,3 руб., 5,8 руб. и 5,5 руб. соответствует. Какое сплавы и в какой пропорции надо взять на складе, чтобы 1 кг нового сплава был как можнодешевле?

8. (Задача вступительная экзамена отделений планирования народного хозяйства и экономического библиотека экономического факультета МГУ 1984 г). Из строительных деталей двух видов можно собрать три типа домов. Для сборки 12-квартирного дома необходимо 70 деталей первого и 100 деталей второго вида. Для сборки 16-квартирного дома требуется 110 и 150, а для дома на 21 квартиру нужно 150 и 200 деталей первого и второго вида соответствующего. Все имеется 900 деталей первого и 1300 деталей второго вида. Сколько и каких домов нужно собрать, чтобы общее количество квартир в них было наиболее?

9. На коллецей магистрали расположены три склада и три магазина; расстояние между каждойми двумя соседними пунктами равен 1 км. На рисунке показано наличие товара на складах (в тоннах) со знаком «+» и потребности магазина в товара (в тоннах) со знаком «-». Требуется составить наименьшее экономный план перевозок, чтобы перевести все грузы со склада в магазина и чтобы сумма перевозных тонно-километров была наименьшей. (Приведите наличищий, с вашей точки зрения, вариант перевозок и изложите те сообщения, которые приведены вас к этому ответу.)