13. Зуховицкий СИ, Радчик НА. Математические методы сетевого планирования. - М.: Наука, 1965.

14. Вентцель Е.С. Исследование операций. - М.: Советское радио, 1972.

Для лучшего усвоения материалов этой главы полезно обратить внимание на задачники:

Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях. - М.: Высшая школа, 1986.

Аранович А.Б., Афанасьев М.Ю., Суворов Б.П. Сборник задач по исследованию операций. - М.: Изд-во МГУ, 1997.

Глава 4

ЛИНЕЙНЫЕ задачи

Издавна тройное правило (позднее - линейная функция) было важным математическим инструментом <...> везде, где человек хотел объяснить и упорядочить наблюдаемые явления. <...> линейная функция является самой удобной математической моделью. Она освобождает от необходимости заново продумывать ситуацию, и ею охотно пользуются ([1], с. 132.)

При изложении материалов этой главы мы во многом будем следовать замечательной книжке Е.С. Вентцель (И. Грековой) Исследование операций. Задачи, принципы, методология . - М.: Дрофа, 2004 [2].

4.1. Линейное программирование

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

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

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

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

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

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

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

Задача 1. Для жизнедеятельности человеку ежесуточно требуется питание, содержащее известное число ингредиентов в количествах, не меньших предписанных нормами. При соблюдении одной из диет потребность в пище можно покрыть посредством ежесуточного потребления двух продуктов; назовем их Ри (?. Дневное питание этими продуктами должно давать не более 14 единиц жира (чтобы похудеть), но и не менее 300 калорий (тоже по вполне понятной причине). На упаковке продукта Р написано, что в одном килограмме этого продукта содержится 15 единиц жира и 150 калорий, а на упаковке продукта Q - 4 единицы жира и 200 калорий соответственно. При этом цена 1 кг продукта Р равна 150 рублям, а 1 кг продукта Q -- 250 рублям.

В какой пропорции нужно брать эти замечательные продукты Р и Q для того, чтобы выдержать предложенную диету при минимальных затратах на их покупку?

Задача 2. Некоторая фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входят 3 фунта азотных, 4 фунта фосфорных и 1 фунт калийных удобрений, а в улучшенный - 2 фунта азотных, 6 фунтов фосфорных и 3 фунта калийных удобрений. Известно, что для некоторого газона требуются по меньшей мере 10 фунтов азотных, 20 фунтов фосфорных и 7 фунтов калийных удобрений. Обычный набор стоит 300 центов, а улучшенный - 400 центов.

Какие и сколько наборов удобрений нужно купить, чтобы обеспечить эффективное питание почвы и минимизировать затраты?

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

Начнем с задачи 1.

Обозначим через х количество продукта Р, а через у - количество продукта Q, требуемые для выполнения условий диеты.