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

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

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

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

Задача пятая (о диете)

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

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

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

Задача (история) шестая

(о том, как следует поступать для того, чтобы получить максимальный доход)

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

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

Задача седьмая

(о том, как выгоднее поступить с имеющимся сырьем)

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

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

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

Задача восьмая

(о наиболее выгодной организации перевозок)

Имеется ряд предприятий, потребляющих известные виды сырья, и есть ряд сырьевых баз, которые могут поставлять это сырье предприятиям. Базы связаны с предприятиями какими-то путями сообщения

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

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

Задача девятая

(проблема путешественника)

Отправляющемуся в путешествие нужно упаковать в рюкзак определенное количество предметов, среди которых могут оказаться и одинаковые. При наличии некоторого количества известных ограничений такого типа, как вес, объем, линейные размеры и полезность каждого предмета, требуется поместить их в рюкзак заданной вместимости таким образом, чтобы общая полезность вмещенного была бы наибольшей. То, что эта задача давно актуальна, весьма выразительно показано классиком ([4], с. 36).

Рассказывая далее, как можно решить эту задачу, мы будем называть ее задачей о рюкзаке.

Задача десятая

(о наиболее выгодном использовании имеющегося парка самолетов)

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

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

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

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