Беклемишев - Дополнительные главы линейной алгебры (947281), страница 61

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

Текст из файла (страница 61)

й 3. Основы линейного программирования 1. Введение. Методы нахождения наибольшего (или наименьшего) значения линейной функции на выпуклом многогранном множестве объединяются под общим названием линейного программирования. Более подходящим по смыслу названием было бы «линейная оптимизация», но не слишком удачно переведенный с английского ') термин прочно вошел в обиход. Линейное программирование как самостоятельное направление появилось в конце 40-х — начале 50-х годов, т.

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

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

Чтобы иметь перед собой нечто конкретное, рассмотрим следующую модель, называемую стандартной экономической интерпретацией общей задачи линейною программирования. !) Выражение «!!пеги ргоягегппг!пкг лучше было Оы перевести как «липей иое 'яланиропаиие». 274 ГЛ Ч СИСТЕМЫ НЕРАВЕНСТВ И ЛИНЕЙ>!ОЕ ПРОГРАММИРОВАНИЕ Рассматривается предприятие, которое может производить и видов продукции с использованием некоторого набора из т ресурсов (например, труд, станки, энергия, материалы „.). Известно, что на производство единицы продукции )сго вида требуется а«! единиц 1-го ресурса.

Заданы также предельные объемы расхода каждого ресурса: (>«, ! = 1, ..., т, и величина прибыли от продажи единицы продукции каждого вида: сп 1 = 1, ..., и. Требуется указать, сколько продукции какого вида следует выпустить для получения «скспматьной прибыли. Если предприятие произведет х> единиц продукции 1сго вида (/ = 1, ..., и), то оно израсходует а >х«+...+а«„х" единиц !'-го ресурса.

Этот расход пе должен превышать предельно возможного расхода Ь'. Таким образом, ограничения на ресурсы име:от вид системы линейных неравенств аих'+...+а«„х" ~Ь«, !'=1, ..., т. Общая прибыль от выпуска всей продукции будет равна «р (х) = с,х'+... + с„х". От нас требуется подобрать х', ..., х" таким образом, чтобы они удовлетворяли системе линейных неравенств и доставляли функции максимальное значение. Уже при создании первых линейных оптимизационных моделей выяснилось, что задача линейного программирования, к которой онп приводятся, может быть полностью решена.

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

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

Линейные модели первоначально составлялись Э 3. ОСНОВЫ ЛИНВЯНОГО ПРОГРАММИРОВАНИЯ для экономических задач мелкого масштаба (например, для планирования в пределах фирмы), но по мере успехов в этой области стали разрабатываться линейные модели для более крупных задач вплоть до разработки плана по народному хозяйству в целом. Естественно, что такие модели приводят к задачам больших размеров. С практической точки зрения, однако, такие модели не имеют большого значения, так как они не могут быть адекватными. Не говоря уже о том, что невозможно описать большую и сложную эконохншескую задачу при помощи хотя бы и большой системы линейных неравенств, сам подход, лежаШий в основе оптимизационных моделей, требовал бы выразить цель развития большого экономического организма (скажем, всего народного хозяйства) при помощи одной функции, которую нужно максимизировать.

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

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

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

Постановка задачи. В этом параграфе мы будем предполагать, что задана система линейных неравенств вида 276 ГЛ, Ч, СИСТЕМЫ НЕРАВЕНСТВ И ЛИНЕИНОЕ ПРОГРАММИРОВАНИЕ пли, в более подробной записи, амх'+...+а, х" - Ьы а хг+...+а „х»~Ь н отыскивается решение х', ..., х" этой системы, на котором функция ф(х) =с,х'+...+с„х' (2) принимает минимальное значение. Функция (2) называется целевой функцией задачи, система неравенств (1) — системой ограничений, любое решение системы неравенств (1) называется допустимой точкой, а та точка, в которой достигается минимальное значение, — решением задачи.

Стоит отметить, что существует несколько различных систем терминов для описания задачи линейного программирования, Так, например, решение задачи иногда называют «оптимальным планом» и т. п. Как и В 2 2, для геометрической интерпретации неоднородной системы неравенств (1), мы воспользуемся аффинным пространством. Для наших целей можно будет ограничиться одной раз на всегда выбранной системой координат, что, по существу, превращает аффинпое пространство в арифметическое пространство. Мы будем отождествлять точку с ее координатным столбцом. Сформулированная нами задача не является задачей самого общего вида, но обладает тем свойством, что произвольную задачу линейного программирования можно привести к такому виду при помощи несложных преобразований. Во-первых, может оказаться необходимым найти максимум функции, а не минимум.

Но очевидно, что, научившись находить минимум, мы сможем найти и максимум, так как максимум функции ~р (х) принимается в той же точке, что и минимум функции — ~р (х). Во-вторых, система линейных неравенств (1) содержит условия неотрнцательностн переменных. Как мы видели в конце 5 1, гроизвольная система линейных неравенств может быть преобразована в систему с неотрицательными переменными, если вместо каждой нз исходных переменных х' ввести две неотрицательные переменные у' и г' такие, что х' = у' — г'. Подробнее о преобразованиях задачи линейного программирования речь будет идти в п. 2 у 4. Наличие в системе ограничений условий неотрицательностн переменных приводит к тому, что ранг системы неравенств (1) обязательно равен и, и потому Выпуклое многогранное множество допустимых точек имеет вершины, если, конечно, оно не пустое.

Задача линейного программирования не обязательно имеет решенне. Может случиться, что система ограничений не совместна, ио и при совместной системе ограничений решения может не существовать, если целевая функция не ограничена снизу. Последнее 277 $ а ОснОВы линвннОГО пРОГРАммиРОВАния возможно только тогда, когда многогранное множество не ограничено. В этом параграфе мы не будем заниматься способами решения задачи, а исследуем ее основные свойства. 3.

Характеристики

Список файлов книги