ГОСУДАРСТВЕНЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО

ВЫСШЕМУ ОБРАЗОВАНИЮ

МАТИ – РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ

УНИВЕРСИТЕТ им. К.Э. Циолковского

Кафедра высшей математики

Горбацевич В.В.

Современное линейное программирование (Сборник задач с решениями на MAPLE5) Москва 1999 год Посвящается студентам МАТИ PDF created with FinePrint pdfFactory trial version http://www.fineprint.com

ВВЕДЕНИЕ

Данное пособие посвящено современным методам решения современных задач по линейному программированию. При этом под современными задачами понимаются не более сложные или запутанные, чем опубликованные ранее (как часто бывает в современных книгах), а просто более актуальные задачи, для решения которых оказывается удобным применять методы линейного программирования. Что же касается современных методов решения, то это опять не какие-то изощренные математические методы, а просто использование современного подхода к решению многих математических задач. Речь идет об использовании универсальных математических пакетов, в данном пособии речь будет идти о пакете Maple5 (Release 4), который в настоящее время свободно распространяется через Интернет (и потому отечественный пользователь в данном случае избавлен от уже привычного для него состояния нелегального пользователя при работе с хорошей программой). Сейчас уже вышла новая версия - Release5, для нее все сказанное ниже остается справедливым (хотя в программе появились и новые усовершенствования, но они не коснулись методов решения задач линейного программирования). Задачи линейного программирования неплохо решаются и другими математическими программами - от простенькой на нынешний день программы Eureka до таких мощных пакетов, как MathCad и Mathematica, а также специализированными математическими программами.

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

В Части II приводятся примеры конкретных задач, которые можно записать (и решить!) в виде задач линейного программирования. Происхождение приводимых в данном пособии задач по линейному программированию не совсем обычно. Основные идеи в них принадлежат не автору пособия, а тем студентам старших курсов МАТИ, для которых автор в течение нескольких лет читал лекции по методам оптимизации (в которые, в качестве составной части, занимавшей от 10 до 25 академических часов, входило и линейное программирование). Дело в том, что для получения зачета или сдачи экзамена по этому курсу студенты должны были представить постановки и (в простейших случаях) решения РЕАЛЬНЫХ задач, для которых применимо линейное программирование. Под реальными автор (лектор) понимал задачи, достаточно хорошо знакомые студентам на практике. Не секрет, что подавляющее большинство студентов старших курсов сейчас сочетает (с разной степенью успешности) учебу с работой в какой-то, причем далеко не всегда связанной с профилем института, области. Так вот, именно из таких областей студенты в основном и брали темы для задач. Роль лектора на этом этапе составления задач сводилась к настойчивой демонстрации студентам самых различных вариантов применения линейного программирования. Чтобы преодолеть скепсис студентов, лектору приходилось придумывать для них примеры задач на почти произвольно заданную тему. В конце концов, студенты видели, что составить реальную задачу не так уж и сложно, как им поначалу казалось. Однако составленные ими на первых порах задачи носили иногда довольно абстрактный характер (напоминая “прикладные” задачи во многих известных сборниках задач - там говорится об изготовлении абстрактных изделий A, B, C, о смешивании неких компонент А, Б, В, Г и т.п.). Обсуждая эти задачи, лектор и студенты приходили к постановке вполне конкретных (хотя, конечно, и в сильно упрощенной форме) задач, в которых фигурировали совершенно реальные (на то время) цены и другие числовые данные PDF created with FinePrint pdfFactory trial version http://www.fineprint.com (например, для обоснования одной из задач студент принес справочник по технологии питания и распечатку дневной выручки в “Макдональдс”е, где он работал). Было несколько задач “фантазийного” и развлекательного характера, они часто отражали личные пристрастия студентов. В задачах студентов фигурировали (кроме множества естественных для нашего времени разного сорта бизнесменов - от банкира до бабушки, собирающей пустые бутылки), такие персонажи, как Смок Белью, Белоснежка и семь гномов, встречались даже там колдун, ювелир, рэкетир и палач...

При подготовке данного пособия автор пересмотрел заново формулировки задач и уточнил их (не меняя, по возможности, исходных данных, даже если они - например, цены или ассортимент компьютеров - в настоящее время уже устарели), некоторые условия пришлось перерабатывать, так как условия в них носили все же подчас искусственный характер. В результате получилось собрание задач, отражающее сферы деятельности и интересов студентов МАТИ второй половины 90-х годов, которые и приводятся в Части II Студенты не только составляли задачи, но и находили решения некоторых из них (если задача сводилась к задаче с двумя переменными и могла быть решена даже графически на листе бумаги в клетку). На освоение сложных методов решения задач линейного программирования не было достаточного учебного времени, а просить студентов просто автоматически повторять шаги симплекс-метода (самого распространенного метода решения задач линейного программирования), не вдаваясь особенно в его обоснования, лектор не считал возможным. И вот уже сейчас, через несколько лет, становится ясно, что времена рутинных вычислений стремительно откатываются в прошлое. Современные математические программы-пакеты позволяют решить задачу линейного программирования за несколько минут (включая не только время вычислений, но и запуск компьютера, вызов нужной программы и ввод условий задачи). Тратить время на освоение даже просто алгоритма симплекс-метода сейчас нужно уже далеко не всем тем, кому нужно бывает иногда решать задачи линейного программирования. Возможность за одну минуту просмотреть 3-4 варианта решений одной задачи (при изменении некоторых числовых параметров, входящих в условия) - это то, что получает каждый освоивший, например, пакет В Части III данного пособия приводится описания той части универсального математического системы Maple5 (Release4), которая касается линейного программирования вообще и симплекс-метода в частности. Следует отметить, что в изданных на русском языке книгах по Maple’у описания математических пакетов-расширений довольно поверхностны, а часто просто неточны (что связано, видимо, с тем, что их авторы не являются профессиональными математиками и не используют Maple в полной мере). Приводимых в данном пособии сведений о Maple5 вполне достаточно, чтобы с помощью справочной системы Help в Maple5 или самого простого руководства по интерфейсу Maple (на описание интерфейса в данном пособии просто нет достаточного места) решить любую из задач, приведенных в Части I. В приложениях приведены примеры решений задач из Части I (математические постановки задач, тексты программ для Maple, другие примеры приведены в Части II) и ответы ко всем задачам, а также дана формулировка того задания по составлению и решению задач, которое давалось лектором студентам.

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

Работа выполнена при поддержке Государственной программы интеграции высшего образования и фундаментальной науки на 1997-2000 годы, #480.

PDF created with FinePrint pdfFactory trial version http://www.fineprint.com

ЧАСТЬ I

ПОСТАНОВКА ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Линейное программирование - это теория и практика нахождение экстремумов линейных функций нескольких переменных, связанных между собой линейным уравнениями и неравенствами. Такого рода задачи встречаются в самых разнообразных областях человеческой деятельности - в основном на стадии планирования - в экономике, при проектировании предприятий, разработке расписаний движения транспорта (авиационного и наземного), разработке военных операций и др. Для линейной функции и линейных условий удается задачу нахождения экстремума решить (по крайней мере, теоретически) полностью за конечное (хотя, возможно, и очень большое - например, в экономике) число шагов. Для произвольной нелинейной функции и столь же произвольных связей между ними задача оптимизации (т.е. нахождения экстремума) далеко не всегда может быть решена даже при применении самых современных компьютеров. Достаточно глубоко развита здесь теория лишь в случае, когда оптимизируемая функция и уравнения, задающие ограничения на переменные, являются выпуклыми функциями, такими задачами занимается так называемое выпуклое программирование (кстати, слово “программирование”, как и в случае линейного программирования, не имеет прямого отношения к программированию на алгоритмических Функция, экстремум (максимум или минимум) которой нужно найти, в линейном программировании предполагается линейной и потому имеет следующий вид Здесь C0,C1,C2,...CN - некоторые вещественные числа, причем C0 называется свободным членом, а C1,C2,...,CN - коэффициентами линейной функции F от переменных X1,X2,....,XN, звездочкой ‘*’ в компьютерной литературе и языках программирования принято обозначать операцию умножения. Эти переменные можно рассматривать как точку (X1,X2,...XN) в N-мерном векторном пространстве R N, для которой значения отдельных переменных являются координатами. Ясно, что свободный член C0 при поиске точек экстремума можно не учитывать (а потому просто отбросить его), хотя, конечно, на само значение функции в точке экстремума он влияет. Далее, достаточно научиться для произвольных линейных функций находить точки экстремума только одного типа (точки минимума или точки максимума). Пусть мы умеем, например, находить точки максимума, а нам нужно найти точки минимума для функции F=F(X1,X2,...XN). Тогда рассмотрим вместо функции F функцию -F, она тоже линейна и в тех точках, где -F достигает максимума, исходная функция F, очевидно, достигает минимума. Решение задачи линейного программирования - это не одно число, а набор чисел (X1,X2,...XN), его иногда еще называют оптимальным планом.

Ограничения или условия, которым должны удовлетворять переменные X1, X2,..XN в задаче линейного программирования, задаются линейными уравнениями или неравенствами.

Линейные уравнения - это соотношения вида где A1,A2,...AN и B - некоторые вещественные числа (среди них некоторые могут быть равны нулю), причем A1,A2,...AN называются коэффициентами уравнения, а B свободным членом (или правой частью уравнения, когда B стоит в правой части уравнения).

К такому виду можно преобразовать и более общие соотношения, задаваемые, скажем, в виде равенства двух линейных функций. Например, соотношение PDF created with FinePrint pdfFactory trial version http://www.fineprint.com может быть, конечно, преобразовано к виду Условия в виде неравенств могут содержать оба знака неравенства ( и ). В линейном программировании строгие неравенства < и > не используются, так как при задаваемых ими ограничениях задача линейного программирования обычно не имеет решения (ибо точки экстремума, как доказывается в теории линейного программирования, располагаются на границе области, задаваемой неравенствами и потому обязательно должны обращать некоторые из неравенств в равенства). Кстати, программа Maple при попытке решить задачу со строгими неравенствами выдает сообщение об ошибке (т.е. она не может решать такие задачи). Отметим, что любое равенство можно записать в виде системы, состоящей из двух неравенств. Например, равенство вида эквивалентно, очевидно, следующей системе двух неравенств:

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

здесь фигурируют N переменных и M неравенств. Такую систему можно записать и в символической матричной форме где A=[AIJ] - прямоугольная матрица, составленная из коэффициентов AIJ при переменных в системе неравенств, а X и B - столбцы, составленные из переменных и свободных членов этой системы соответственно (столбец B иногда называют вектором ресурсов), а ‘*’ здесь - это операция умножения матриц.

Геометрически система неравенств задает в R N некоторый выпуклый многогранник, который может оказаться и пустым (если система неравенств несовместна), причем тогда задача линейного программирования решения иметь не может. Этот многогранник может быть ограниченным (и тогда любая линейная функция принимает на нем в силу теоремы Вейерштрасса максимальное и минимальное значения и потому любая задача линейного программирования для таких условий - если они совместны - разрешима), но может оказаться и неограниченным. В теории линейного программирования доказывается, что экстремальные значения целевой функции, если они существуют, принимаются в вершинах этого многогранника (хотя могут приниматься, кроме этого, и в других точках В задачах линейного программирования все переменные обычно предполагаются неотрицательными, т.е. предполагаются выполненными условия:

PDF created with FinePrint pdfFactory trial version http://www.fineprint.com Есть задачи, в которых такие условия не накладываются, но это бывает очень редко и потому зачастую условия не отрицательности даже не всегда в явном виде выписывают, предполагая их как бы выполняемыми по умолчанию. Если это необходимо, то можно вообще избавиться от переменных, принимающих произвольные (а не только неотрицательные) значения. А именно, если X - такая переменная, то ее можно заменить разностью X=X + -X, где X + и X две новые переменные, принимающие неотрицательные Иногда бывает полезно не только от равенств переходить к неравенствам, но и наоборот, условия, записываемые в виде неравенств, записывать в виде равенств (добавив к ним условия не отрицательности). Например, пусть задано условие Введем новую переменную (иногда называемую переменной скачков) тогда исходное условие эквивалентно системе, состоящей из одного равенства и одного неравенства стандартного типа Отметим, что при таком преобразовании число переменных и число условий увеличиваются (что не очень существенно, если речь идет о чисто теоретическом исследовании задачи или если для решения предполагается использовать эффективную компьютерную программу). Таким образом, от системы линейных условий, задаваемых равенствами и неравенствами, можно перейти к системе равенств (точнее, к системе линейных алгебраических уравнений), дополненной системой стандартных неравенств условий не отрицательности переменных. Именно к такому виду обычно приводятся условия произвольной задачи линейного программирования во многих алгоритмах для их решения (например, в симплекс-методе, реализованном в математическом пакете Maple, о котором Если среди условий задачи имеются линейные равенства, то их при желании можно использовать для уменьшения числа переменных. Для этого надо с помощью этих уравнений выразить часть переменных через остальные и подставить эти выражения в оставшиеся условия и в целевую функцию. Может оказаться, что в результате число переменных окажется не более двух и тогда задача может быть решена чисто графически - с помощью изображения условий задачи на листе бумаги в клеточку ( линейные условия в этом случаю задают выпуклый многоугольник) и применения простейших приемов решения задач линейного программирования (например, просто перебора всех вершин многоугольника, задаваемого линейными условиями).

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

Поэтому часто задачу с целочисленными переменными решают как обычную задачу PDF created with FinePrint pdfFactory trial version http://www.fineprint.com линейного программирования, получают точку экстремума и, если координаты этой точки не являются целыми числами, то их округляют. Причем для того, чтобы для полученных значений переменных продолжали выполняться все линейные условия, округление должно производиться в большую или меньшую сторону, в зависимости от ситуации. На самом деле, таким методом далеко не всегда можно получить даже удовлетворительное приближение к точке экстремума (хотя само экстремальное значение целевой функции при этом находится с неплохой точностью), но этот прием используют довольно часто, чтобы избежать обращения к сложным методам целочисленного линейного программирования (которых, кстати, нет ни в одном универсальном математическом пакете).

PDF created with FinePrint pdfFactory trial version http://www.fineprint.com

ЧАСТЬ II

ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

На российском рынке продаются растворимые соки (порошки) фирм Zuko, Yupi и Invait. Отпускные цены на них - соответственно 2.5, 1.5 и 1.8 рублей. Количество порошков, продаваемых в одной торговой точке в день, не более 150 шт. Организация, занимающаяся оптовой торговлей, установила следующие условия: оптовая закупка Zuko - от 3000 до шт., а Yupi и Invait - не менее 1000 шт. Как достичь максимума дохода одной торговой точки при ежемесячной оптовой закупке товара?

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

Какое количество ОС нужно приобретать фирме у IBM и Microsoft (производителей этих операционных систем), чтобы ее доход от продаж мог бы быть максимален?

Коммерческая фирма осуществляет продажу автомобилей из салона в Германии в Россию на заказ. Предлагаются автомобили марок BMW, Volvo, Mersedes, Saab. Необходимо так организовать оформление заказов, чтобы за каждый рейс получать максимум прибыли.

За один рейс фирма хочет поставлять автомобилей BMW не менее 2 шт. (так как уверена, что сможет их продать), но не более чем в два раза больше, чем Volvo (с учетом спроса на российском рынке). Общее число автомобилей Mersedes и Saab должно быть (по условиям PDF created with FinePrint pdfFactory trial version http://www.fineprint.com договора с салоном) не менее 5 шт., а общее число автомобилей Mersedes, Volvo, Saab по организационным причинам не должно быть более 20 шт. за один рейс. Прибыль фирмы от продажи автомобилей марок BMW, Mersedes, Volvo, Saab равна соответственно 1000$, Кроликовод собирается везти кроликов на продажу на ВВЦ (бывшая ВДНХ в Москве). Он разводит кроликов четырех пород - Белый великан (сокращенно БВ), Русский косой (РК), Черная кудлашка (ЧК), Белая кудлашка (БК). Спрос на РК ограничен - продается за раз не более 12. БВ необходимо продать не менее 25, до следующей продажи они могут и не дожить. ЧК и БК продать нужно не более 50 (иначе у кроликовода нарушится процесс их размножения), но и не менее 40 (из-за недостатка кормов). С целью продолжения работы по получению новых пород нельзя продавать более 30 БВ и ЧК. Цены на ВВЦ такие: БВ - руб., БК - 18 руб., ЗЛ -45 руб., ЧК -20 руб. Нужно выбрать состав партии кроликов для получения максимума прибыли при продаже.

На дачном участке площадью 600 м2 стоит дом, занимающий площадь 40 м2.

Площадка для настольного тенниса и дорожки занимают в сумме 40 м2. На оставшейся территории планируется посадить картофель, огурцы и помидоры, клубнику, а также всевозможную зелень. Площадь под картофель нужна не менее 300 м2., но и не более чем м2. (картофель выращивается только для собственного потребления, поэтому слишком много его не нужно). Под огурцы и помидоры планируется отвести не менее 50 м2. (овощи полезны!), но не более чем 1/3 от площади, занимаемой картофелем (для соблюдения баланса в питании). Клубникой хочется занять не менее 80 м2. Под зелень предполагается отвести не менее 10 м2., но не более половины площади, занимаемой помидорами и огурцами и не более 1/4 площади под картофель (опять таки для сбалансированности питания). Дачникам не хочется тратить на подготовку почвы слишком много времени.

Известно, что на вскапывание и подготовку почвы к посадке картофеля уходит 10 мин./м2., огурцов и помидоров -20 мин/м2., клубники - 25 мин./м2., зелени -18 мин./м2. Однако работа с клубникой очень приятна, поэтому время на обработку почвы для нее рассматривается как праздник (и потому даже мысленно вычитается из всего времени, потраченного на обработку почвы). Как за минимальное время дачники могут обеспечить себе сбалансированное После получения долгожданной зарплаты семья собирается поехать на мелкооптовый рынок за мясом. В семье (муж, жена и мать жены) из мяса готовят пельмени, котлеты, голубцы и гуляш. У каждого члена семьи - свои соображения о том, на какие блюда лучше использовать мясо. Муж хочет, чтобы на голубцы пошло не менее 1кг., а на пельмени и котлеты - не более 5кг. Жена считает, что на пельмени и голубцы нужно выделить не менее кг., а на гуляш - как минимум в два раза меньше, чем на пельмени. Ее мама хочет на котлеты выделить минимум 2 кг., а на голубцы не более 3 кг. Все они согласны в том, что на котлеты и пельмени нужно отвести не меньше половины всего мяса.

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

PDF created with FinePrint pdfFactory trial version http://www.fineprint.com Строительное предприятие перевозит водным транспортом четыре вида продукции сыпучие материалы (песок и щебень) и несыпучие кирпич и строительные блоки). Перевозки производятся на судне-сухогрузе, который имеет два отсека - для сыпучих грузов и для несыпучих. Стоимость перевозки сухогрузом за один рейс одной тонны кирпича - 7 у.е.

(условных единиц, т.е. долларов), строительных блоков - 8у.е., песка - 3 у.е., щебня - 2 у.е.

Общая вес сыпучих грузов не должна превосходить 65 тонн, а несыпучих - 70 тонн, общий вес всего груза не должен превосходить 120 тонн. При этом разница в загрузке двух отсеков для соблюдения баланса судна не должна превосходить 10 тонн. За один рейс обязательно нужно перевезти не менее 5 тонн щебня. Как выбрать наиболее прибыльный состав груза?

Город Пожарск расположен вокруг озера Пожарского. Город разбит на 5 районов, каждый из которых примыкает к озеру, а их площади соответственно 7.2 км2, 8, 6, 8.8 и кв. км.(перечисление - по часовой стрелке вокруг озера) В каждом районе имеется своя пожарная часть. Известно, что площадь эффективного воздействия одной пожарной машины при пожаре составляет 0.1га = 0.001 км2.

В случае массового возгорания в одном районе тушением должно быть охвачено не менее 2 % территории района, причем возможно привлечение всех пожарных машин из двух соседних районов. Каково должно быть минимальное количество пожарных машин в В магазине организована продажа джинсов пяти марок - ”Motor”, “Cross”, “Dallas”, “Levi’s” и “GAP”. Магазин не имеет складского помещения, весь товар завозится с оптовых складов раз в 3 дня и помещается на полках. На полках можно разместить не более джинсов (с учетом остатка от прошлого завоза). Джинсы “Motor” и “Cross” доставляются с одного склада на машине, которая может вместить не более 1300 джинсов. В последнее время участились кражи джинсов марки “GAP” (самых дорогих), поэтому решено разместить их на отдельных полках в количестве не более 300 шт. Из статистической обработки данных о продажах выяснено, что джинсов марок “Cross” и ”Dallas” за три дня продается не менее В ближайшем будущем ожидается прибытие на склады крупных партий джинсов марок “Motor” и ”Dallas”, поэтому решено, что в рекламных целях доля продажи этих джинсов должна составлять не менее 50% от продажи всех остальных марок.

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

Известно, что цены (за 1 джинсы) таковы:

“Motor” - 30$, “Cross” - 38$, “Dallas” - 38$, “Levi’s” - 44$, “GAP” - 50 $.

Планируется покупка книг для семейной библиотеки. Муж читает только классическую прозу и фантастику, жена - стихи (классику), старший сын - фантастику, а младшему сыну собираются покупать энциклопедии. Муж хочет, чтобы из купленных книг не менее 10 были для него, причем и муж и жена рассчитывают иметь от 2 до 7 книг для чтения каждый. Жена надеется, что и классическая проза ей тоже будет интересна, поэтому PDF created with FinePrint pdfFactory trial version http://www.fineprint.com она согласна купить поэзии не более того количества, в котором будет куплена прозаическая классика. Также договорились, что книг, которые собираются читать муж и старший сын, будет ровно половина от общего числа купленных книг. Всего собираются купить не более 30 книг. Стоимость книг (в среднем):

Сколько и каких книг нужно купить, чтобы с минимальными расходами удовлетворить пожелания всех членов семьи?

Стоимость газеты “МК” - 0.7 р., “АиФ” - 1.5р., “Из рук в руки” - 5р., а “Приглашаю на работу” - 2р. за один экземпляр. Торговая точка в день продает не более 200 экз. “МК” и не более 100 экз. “АиФ”. Газет “Из рук в руки” и ”Принимаем на работу” всего покупают не менее 200 экз., но и не более 300 экз. Из-за определенных обязательств перед издательствами число заказываемых торговой точкой газет “МК” и “Из рук в руки” должно быть больше или равно числу заказов на остальные две газеты.

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

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

Смок Белью собрался в поход из Доусона на Нежданное озеро. Так как в походе запасы пополнить будет негде, он решил обеспечить себя провизией еще в Доусоне. Его обычное меню составляют рыба (цена в Доусоне 1.5$ за фунт), мясо (2.3$ за фунт), сало (1$ за фунт), бобы (0.8$ за фунт) и лепешки (0.5$ за фунт). По опыту предыдущих походов он знает, что стоит придерживаться определенных соотношений между продуктами. Рыбы и сала надо взять в сумме не более 50 фунтов, мяса и бобов - не менее 10 фунтов, лепешек и рыбы - не менее 32 фунтов, мяса и лепешек - не менее 14 фунтов, а рыбы и мяса - не менее 50 фунтов. Смок сильно стеснен в средствах и хочет знать, какой суммы ему будет достаточно для обеспечения себя провизией.

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

Сапфиры должны по эстетическим соображениям занимать площадь не более 25% от площади, занимаемой топазами, но и не менее 10 см2. Площадь золотой инкрустации не должна быть более 10 см2., а площадь серебряной чеканки не менее площади, занимаемой сапфирами и не менее удвоенной площади золотой чеканки, но в то же время и не более см2. Необходимо определить минимальное время, необходимое для инкрустации изделия, если известны затраты времени на каждую операцию: на установку топазов - 20 мин./см2., установку сапфиров - 25 мин./см2., на покрытие золотом - 120мин./ см2., на покрытие PDF created with FinePrint pdfFactory trial version http://www.fineprint.com Один почти разорившийся коммерсант, торгующий женскими колготками, решил поправить свое дело, поставив его на научную основу. Для начала он нарисовал следующую Здесь Вася и Федя - оптовые покупатели, которым он обычно сбывал свой товар. Сам он его закупал на оптовых складах в Кунцево и Измайлово. В таблице указаны цены (в $) упаковок четырех видов колготок разной плотности (измеряемой единицей den).

При этом оптовый покупатель Вася может за раз купить товара на сумму не более 3800$, а Федя - не более чем на 3300$. Оптовые склады продают по указанным в таблице ценам партии не менее чем на 1000$, причем “Измайлово” может предоставить товара не более чем на 2000$, а “Кунцево” - не более чем на 3000$.

Каковы должны быть действия коммерсанта (сколько закупать и кому продавать) для достижения максимальной прибыли?

Фирма специализируется на разработке и установке компьютерных сетей четырех разных классов. Данные о параметрах процесса разработки и установки этих сетей Проекта установку планирован покупку необходимое тестирова проекта, Средства фирмы, задействованные в течение года для установке сетей, не могут По условиям функционирования фирмы имеются ограничения на время планирования сетей - не более 50 дней, на закупку оборудования - не более 52 дней, на установку сетей - не более 110 дней, на тестирование сетей - не более 40 дней. Нужно выяснить, при каком количестве устанавливаемых сетей разных типов прибыль (пропорциональная стоимости выполненных проектов) фирмы будет максимальна.

PDF created with FinePrint pdfFactory trial version http://www.fineprint.com Ателье шьет обмундирование для военных - костюмы летние полевые, костюмы зимние полевые, мешки спальные и фуражки летние. На складе имеется запас фурнитуры ткань, пуговицы, нитки, тесьма х/б, ткань подкладочная, ватин. Возникла необходимость освободить складские помещения. Что и в каких количествах нужно изготовить, чтобы получить максимальную прибыль?

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

В проектную организацию поступил заказ на разработку свайного основания под нагрузку 5000 тонн. У подрядчика в данное время было всего 4 типа забивных свай, причем на складе он одновременно может разместить не более 100 свай. Параметры свай Заказчиком были высказаны несколько дополнительных условий. Воспринимаемая нагрузка свайного основания не должна быть меньше 5000 тонн. Время изготовления свайного основания не должно быть более 50 часов. Удельная нагрузка на единицу площади свайного основания не должна превышать 60 кг/м2м. Площадь фундамента должна быть не необходимые сваи нужно заказать заранее и разместить на складе (вмещающем не более свай). Определить минимально возможную стоимость заказа.

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

PDF created with FinePrint pdfFactory trial version http://www.fineprint.com На оптово-закупочную фирму, специализирующуюся на торговле канцелярскими принадлежностями, в самом конце рабочего дня, когда до выключения подъемных лифтов оставалось всего 15 минут, прибыли три машины с тетрадями общими, тетрадями тонкими и с тушью. Начальство требует немедленно начать разгрузку, так как покупатель сейчас ждет 10 коробок тонких тетрадей, причем уже сегодня требуется выставить образцы привезенного товара. Одновременно с этим сотрудники соседней фармацевтической фирмы предлагают хорошо подзаработать, выгрузив из их машины от 6 до 18 коробок медикаментов. Разгрузка производится с помощью трапов (приспособлений для транспортировки коробок), которых имеется в наличие только пять.

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

Владелец клуба дрессировки собак дал объявление о записи в группы по дрессировке по следующим видам дрессировок: IPO (защитно-караульная служба по европейским стандартам), ЗКС (защитно-караульная служба по российским стандартам), ОКД (общий PDF created with FinePrint pdfFactory trial version http://www.fineprint.com курс дрессировки), ТХ (курс собак-телохранителей). Звонки поступили от владельцев пород собак - ротвейлеров (37 звонков), немецких овчарок (36), колли (25), кавказских По курсу IPO за одну дрессировку инструктор по ротвейлерам может работать только с 3 собаками, инструктор по нем. овчаркам - с 3-мя, а с колли и кав. овчарками дрессировки По курсу ЗКС за одну дрессировку инструктор по ротвейлерам может работать с собаками, инструкторы по нем. овчаркам и по кав. овчаркам - с 2 собаками каждый, с колли дрессировка по ЗКС не производится.

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

По курсу ТХ инструкторы по ротвейлерам и по нем. овчаркам могут за одну дрессировку работать с 4 собаками каждый, инструктор по кав. овчаркам - с 3 собаками, с колли дрессировка по ТХ не проводится.

Прибыль от одной дрессировки по курсу IPO - 20$, по курсу ЗКС - 32$, по ОКД - 45$, Дрессировки проводятся на двух площадках (IPO и ОКД на одной, а ЗКС и ТХ - на другой), это вызвано наличием на площадках определенного необходимого для данного типа дрессировки оборудования. По условиям аренды на площадке для IPO и ОКД в день можно проводить не более 6 дрессировок, а на другой площадке - не более 4.

Определить, сколько дрессировок и по какому курсу проводить для получения Фирма, занимающаяся прокатом автомобилей, решила расширить парк машин, выделив на это 3 млн. $. Стоимости и условия эксплуатации машин, разных марок Фонд з/п шоферам отечественных марок автомашин должен быть не более 3000$, а импортных - не более 4000$. Расходы на специальные сорта бензина для ЗИЛ117 и Линкольн не должны превышать 200$ в месяц. Как расширять парк машин для достижения Книготорговая фирма собирается, имея в своем распоряжении 100000 руб., издать три книги - “Французско-русский словарь”, учебник “Немецкий язык для всех” А. Н. Попова и приложение к нему - “Ключи”, а также взять на реализацию краткий учебник “Немецкий за 13 дней” того же А.Н. Попова. Затраты на издание (в расчете на 1 экз.) составляют 8руб., PDF created with FinePrint pdfFactory trial version http://www.fineprint.com руб. и 5 руб. соответственно. Затраты на перевозку из типографии: 1руб. для словаря, 0.9руб.

для учебника, “Ключи” весьма компактны и перевозятся вместе с учебником, поэтому на стоимость перевозки не влияют. Доставка из другой фирмы краткого учебника обходится в 1.3руб. за 1 экз. На перевозки выделено дополнительно 20000руб. Чтобы типография заключила контракт, общий тираж не должен быть меньше чем 22 тыс. экз.

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

экз. “Ключей” должно быть издано не больше, чем обоих учебников. Краткий учебник новая книга, ее рискованно брать более чем 1/8 от тиража полного учебника.

Имеются также дополнительные расходы (перевозка на рынок, доставка клиентам и др.), которые составляют 1 руб. на 1 экз. полного учебника и словаря, 2 руб. для “Ключей” и 3 руб. для краткого учебника. Нужно минимизировать эти дополнительные расходы выбором оптимальных тиражей книг.

Только что организованный яхт-клуб “Пижон” собирается закупить несколько катеров и яхт. Правление клуба санкционировало закупку 20 катеров и яхт. Продавцами предлагается 3 вида яхт и один вид катера:

Длина выделенного под модели яхт класса “Люкс” (это YT-25L и YTM-50L) причала ограничена, не более 300 м. Цистерна с горючим для обслуживания купленных катеров и яхт рассчитана на 2000 литров. Число членов по организационным соображениям на должно превышать 100 членов плюс 12 членов правления, но и не должно быль меньше 100 человек (по уставу клуба). Как организовать закупки?

Проектируется бак-кессон крыла самолета. Он состоит из уголков (26 штук), гнутиков (14шт.), нервюр (7 шт.), лонжеронов (2 шт. - передний и задний), дополнительных лонжеронов (6 шт.), обшивки (2 шт. - верхняя и нижняя).

По ТУ заданы определенные ограничения на веса компонент. Вес уголков, гнутиков, нервюр и дополнительных лонжеронов с запасом в 10 кг. не должен превышать общего веса обшивок (верхней и нижней). Для стапельных работ необходимо, чтобы вес нервюр, дополнительных лонжеронов и гнутиков был не более 20кг. Вес каркаса одного отсека (две нервюры и один дополнительный лонжерон) должен составлять 10% от веса одной обшивки.

Вес основных и дополнительных лонжеронов не может быть менее 30 кг. Необходимо найти согласованные веса всех составляющих так, чтобы общий вес пустого бака-кессона крыла PDF created with FinePrint pdfFactory trial version http://www.fineprint.com На складе мясоперерабатывающего комбината имеется 4 сорта мяса для производства 4 видов колбасы. По стандарту задается определенное количество каждого сорта мяса на Мясо /колбаса любительская любительская свиная столичная русская ресурс Столичной колбасы нужно изготовить не более 900 кг. (объем холодильника заказчика), но не менее 100 кг (минимальный заказ). При этом необходимо переработать всю говядину, так как истекает срок ее хранения. Как получить максимум прибыли (которая пропорциональна стоимости продажи)?

Студент 5-го курса решил в свободное от учебы время завести свое дело - открыть бар. После аренды помещения и получения лицензии у него осталось 2000$. Эти деньги ему необходимо распределить наиболее эффективно на оформление зала, рекламу, оборудование кухни и покупку напитков. Он считает, что реклама полезна и решил потратить на нее не менее 100$, но тратить более 500$ ему жалко. На первоначальную закупку напитков нужно не менее 200$. Закусочную он устраивать не собирается, поэтому на оборудование кухни готов потратить лишь от 200$ до 500$.

Опытные друзья подсказали ему, что на оформление зала и закупку напитков нужно выделить в 3-4 раза больше средств, чем на рекламу, а на оборудовании кухни в баре его класса нужно тратить на 400$. меньше, чем на начальный набор напитков.

Ему известно, что вложенный в рекламу 1$ дает 4$ прибыли, а вложенный в оформление зала - 2$ прибыли. Продажа напитков дает доход 50%. Вложение 1$ в кухню дает 1.3$ прибыли. Как распределить затраты для получения максимума прибыли на первых В парикмахерской “Галатея” клиентам оказываются следующие услуги: стрижка (мужская и женская), химическая завивка, бритье, окраска волос. В салоне работает мастера, навыки которых в оказании этих услуг различны, поэтому они тратят на них различное время. Общий фонд времени работы каждого мастера в этом салоне по условиям договора с ними ограничен. Общее количество услуг должно быть, по требованию администрации, не менее 12 в день.

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

PDF created with FinePrint pdfFactory trial version http://www.fineprint.com На складе мебельной фабрики имеется 4 вида плит из ДСП, имеющие разные габаритные размеры. Из этих плит изготавливают 4 вида изделий (перечисленные в таблице) для производства столов, шкафов и другой продукции. Для разных плит существуют свои способы раскроя, дающие разное количество изделий.

Стоимость панелей 1-го, 2-го, 3-го и 4-го типов соответственно 100 руб., 80 руб., руб., 60 руб. На складе не все плиты можно разместить в неограниченном количестве, а именно: плит типа 1 - не более 60 штук, а типа 2 - не более 50 шт. Требуется выпустить крышек для столов, дверей, верхних и нижних панелей шкафов, 200 боковых панелей стола, боковых панелей шкафа можно выпустить 300 шт. и более (так как их можно использовать для производства других изделий), а полок шкафов не нужно более 250 шт., так как они будут поступать и с других производств.

Сколько и каких плит нужно заказать для выполнения заказов с минимальными Стандартом предусмотрено, что октановое число автомобильного бензина А-76 не должно быть ниже, чем 76, а содержание серы в нем не должно превосходить 0.3%. Для изготовления этого бензина используется смесь из 4 компонентов I, II, III и IV, имеющих разное октановое число и содержание серы:

I II III IV

Сколько и какого компонента нужно использовать для получения бензина А-76 с минимальной себестоимостью?

PDF created with FinePrint pdfFactory trial version http://www.fineprint.com Фирма специализируется на разработке и установке компьютерных сетей.

Необходимо выбрать типы устанавливаемых операционных систем для получения Время на установку программного обеспечение ограничено и составляет 2000 часов в год, время привлекаемых со стороны специалистов ограничено по финансовым соображением и составляет не более 350 час. в год. Время работы подрядчика согласно соглашению должно составлять не менее 200 часов в год. Согласно курсу руководства фирмы, дающего предпочтение развитию коммуникационных систем на базе ОС UNIX, производится искусственное занижение числа других ОС - их должно быть не более 50. В соответствии с дилерским соглашением фирма обязана устанавливать не менее 50 копий ОС UNIX. Из-за жестокой конкурентной борьбы между компаниями Microsoft и IBM и проводимой ими вследствие этого дилерской политики количество устанавливаемых копий ОС этих фирм должно быть равным. Установка ОС Novell Netware производится для поддержания рабочих станций UNIX и потому число этих ОС должно быть от 1/4 до 1/5 от Заводу, выпускающему прокат, грозит банкротство. Поэтому возникла необходимость оптимизации выпускаемого ассортимента для достижения максимальной прибыли. Известны параметры выпускаемых изделий.

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

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

PDF created with FinePrint pdfFactory trial version http://www.fineprint.com В агентство по торговле недвижимостью обратилось СП “Crocodile”, желающее купить квартиры своим сотрудникам. Филиалы СП находятся в разных районах Москвы (Кутузовский проспект, Коньково, Митино, Текстильщики), поэтому квартиры предполагается покупать в именно этих районах. Агентство предоставило следующую информацию о стоимости квартир в этих районах (в тысячах $) На покупку квартир СП готово израсходовать в этих районах соответственно не более 700 тыс. $, 550тыс.,400тыс. и 250тыс.$, всего не более 2 млн. $. Для всех филиала числа одно-, двух-, трех- и четырех комнатных квартир должны быть одинаковыми (для соблюдения равенства интересов филиалов). Необходимо приобрести не менее 5 двух- и трехкомнатных квартир (в сумме), а число 4-х комнатных не должно превышать числа однокомнатных. Агентство хочет выполнить заказ с максимальной для себя прибылью.

В меню столовой 5 блюд, которые изготавливаются из 5 видов продуктов (картофель, мясо, вермишель, рис, овощи), вода в неограниченном количестве, соль и специи по вкусу.

Нормы продуктов на каждое блюдо следующие:

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

Картофельного пюре с мясом посетители потребляют в день не более 500 порций, супа мясного не более 450 порций, плов едят в 2 раза и менее раза чаше картошки.

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

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

PDF created with FinePrint pdfFactory trial version http://www.fineprint.com В киоске, где продается товар, имеется два холодильника. Первый предназначен для хранения молоко и йогурта, его вместимость 200 пакетов, второй для творога и масла, его вместимость 150 пачек. Какова может быть максимальная прибыль с одной партии товара?

Для производства сэндвичей (биг-маков, чизбургеров, гамбургеров, двойных гамбургеров и филе-о-фиш) и пирожков в ресторане “Макдональдс” используют оборудование - биг-маковский тостер, стандартный тостер, гриль и фритюрницу. Чтобы определить оптимальный режим выхода сотрудников на работу, нужно выяснить загруженность оборудования для каждого часа. Ниже приводятся фактические данные на Используемое биг-мак, чизбургер, чизбургер, двойной Филе-о-фиш, пирожки, Площадь для оборудования выделена ограниченная - 9.5 м2. Для одного тостера необходимо 0.75 м2. площади, для гриля 0.75 м2., а для фритюрницы 0.15 м2. площади. Над каждым грилем и фритюрницей обязательно должны стоять фильтры. Возможности вентиляции не позволяют установить более 10 фильтров.

ЧАСТЬ III

РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПОМОЩЬЮ MAPLE

Здесь будет дано описание той части языка программирования системы Maple и тех элементов этой программы (Maple5, Release 4), которые необходимы (а практически и достаточны) для решения основных задач линейного программирования.

После запуска программы Maple на экране монитора компьютера появляется основное окно программы, в котором уже автоматически открыта первая страница для решения задач. Он имеет наименование “Untitled(1)” (т.е. “без названия (первая)”). Если Вы захотите потом сохранить в памяти компьютера эту страницу (чтобы в дальнейшем не набирать на клавиатуре заново операторы для решения данной и подобных ей задач), то это можно сделать с помощью операции Save (сохранить). При этом создается файл с PDF created with FinePrint pdfFactory trial version http://www.fineprint.com расширением.mws, основное имя которого Вы можете выбрать сами, например problem1.mws. Если вы когда либо захотите вернуться к этой странице, это можно сделать с помощью операции Open (открыть). Кстати, можно использовать одновременно несколько страниц, создавая их одну за одной с помощью операции New (новая). Получаемые при этом страницы будут иметь предварительные названия Untitled(2), Untitled(3) и так далее. Все упомянутые операции (Save, Open, New) производятся после вхождения в элемент File основного окна системы Maple, там также предусмотрено сохранение страницы и в других Переходим к процессу решения задачи линейного программирования на некоторой выбранной странице. Система Maple состоит из нескольких групп основных математических подпрограмм, а также из дополнительных пакетов, которые подключаются по мере необходимости (сразу все их подключать нецелесообразно, так как это загромождает память компьютера и отрицательно сказывается на его быстродействии, а также ограничивает сложность решаемых задач). Для задач линейного программирования нужен дополнительный пакет simplex (его название связано с тем, что основным элементом этого пакета является метод решения задач линейного программирования, называемый симплексметодом). Для подключения этого пакета нужно в строке после символа > (представляющего собой как бы приглашение к вводу команд и условий задачи) набрать строку такого вида:

Заметьте, что строка заканчивается точкой с запятой - этим символом должны заканчиваться все те строки исполняемых системой команд, результаты, действия которых мы хотим увидеть на дисплее. Если команду нужно выполнить, но результат выводить на экран не нужно, то в конце ставится двоеточие, например:

Если в конце не стоит один из этих двух символов (';' или ':'), то команды, записанные в этой строке, выполняться не будут и будет выдано сообщение программы об ошибке.

нужно нажать на клавишу ввода (Enter), которая заставляет Maple выполнить ту команду, которая расположена в строке, занимаемой курсором. На экране появится сообщение:

Здесь сообщается, во первых, о том, что теперь функции maximize и minimize будут пониматься не в том смысле, как в основной программе Maple (где они обозначали нахождение максимума или минимума функции, возможно, нелинейной, но только одной переменной), а как функции решения задач линейного программирования - нахождению PDF created with FinePrint pdfFactory trial version http://www.fineprint.com максимума или минимума линейной функции при заданных линейных ограничениях (в виде равенств или неравенств). Далее, в этом сообщении приводятся имена тех новых функций, которые теперь могут использоваться: basis, convexhull и т.д. Некоторые из этих функций удобно использовать при решении любой задачи линейного программирования, а некоторые носят весьма специальный характер и иллюстрируют отдельные этапы симплекс-метода (что иногда бывает полезно при подробном изучении этого метода). Основными здесь являются функции maximize и minimize для нахождения максимума и минимума соответственно (на самом деле было бы достаточно только одной из этих функций, так как нахождение минимума функции F(x) сводится очевидным образом к нахождению максимума функции F(x) - см. Часть I). Чтобы не перегружать память машины (которая может понадобиться при решении задач с большим числом переменных и условий), можно ограничиться загрузкой только одной необходимой нам функции. Например, команда >with(simplex,minimize);

вызывает одну только функцию minimize из пакета simplex.

После того как нужные нам функции загружены, переходим к записи условий решаемой задачи. Команда minimize используется с дополнительными параметрами, которые указывают целевую функцию (или ее имя, если она уже была задана заранее), линейные ограничения, тип переменных и имена переменных, которым будут присвоены некоторые вспомогательные значения, возникающие при решении задачи. Общая форма записи этой >minimize(F, {C1, C2,...},vartype, ‘NewC’, ‘trANsform’);

Здесь F - это целевая функция задачи линейного программирования. Она может быть задана здесь в явном виде, например, вместо F можно подставить выражение Кстати, использовать переменные с нижними или верхними индексами (например, x 1 ) в Maple не следует (в отличие от текстового редактора Word, в котором это делается Однако не обязательно вставлять выражение для целевой функции прямо в команду minimize. Можно обозначить эту функцию какой-то буквой (например, буквой F или какой либо другой, которая более тесно связана со спецификой решаемой задачи), определив ее предварительно следующим способом:

Здесь ':=' обозначает единый символ (хотя он и набирается последовательным нажатием двух клавиш - двоеточия и равенства). Это символ присваивания, широко используемый в программировании. Он читается как “ положить равным ”, например, строка выше читается “F положить равным x-y”. После этой команды под значением величины F всегда будет пониматься x-y, где значения переменных x,y или неопределенны (как в случае целевой функции) или имеют какие-то числовые значения. Следует отличать ':=' от знака равенства '=' (который используется при записи уравнений).

Что касается условий C1, C2,..., то их тоже можно записывать как внутри команды minimize (заключая их в фигурные скобки '{', '}'), так и задавать предварительно в виде отдельных объектов. Каждое такое условие в задаче линейного программирования задается линейным равенством или неравенством, например, оно может иметь вид PDF created with FinePrint pdfFactory trial version http://www.fineprint.com Здесь символ “больше или равно” записывается последовательным нажатием клавиш > и =, причем именно в указанном порядке, запись в другом порядке, т.е.=>, программа воспринимает как ошибку. Условие может задаваться в виде равенства или неравенства двух линейных функций, например Если линейных условий несколько, то внутри команды minimize они перечисляются через запятую и заключаются в фигурные скобки (означающие образования множества, состоящего из перечисленных элементов), например >minimize(x-y,{2*x+3*y=2};

Если этих условий много или если эти условия по ходу решения задачи нужно будет менять, то удобнее задать их в виде отдельных выражений предварительно (до записи команды minimize) с помощью оператора присваивания. Это может быть сделано, например, >C1:=2*x+3*yC2:=x-7*y >=2:

Заметьте, что здесь стоит двоеточие - т.е. мы не ходим, чтобы результат операции присвоения дополнительно появлялся на экране монитора. Тогда команда минимизации >minimize(x-y,{C1, C2});

Все условия можно перечислить и за один раз, объединив их в единую переменную, скажем в переменную с именем С (рассматриваемую как множество, состоящее из а потом использовать эту переменную в операции minimize:

Что касается параметра vartype (тип переменной), то он может принимать одно из следующих двух значений: NONNEGATIVE (неотрицательный) или UNRESTRICTED (без ограничений). Если используется значение NONNEGATIVE, то ВСЕ используемые в задачи линейного программирования переменные предполагаются неотрицательными. Другими словами, выбор этого значения параметра заменяет условия вида X1>=0, X2>=0,... Если же выбрано значение UNRESTRICTED, то на знаки переменных этот параметр никаких ограничений не накладывает, (что не мешает их ввести, причем не на все, а при необходимости только на часть переменных, дополнительно в списке условий). По умолчанию значение этого параметра принимается равным UNRESTRICTED, т.е. если значение параметра не задано (а команда minimize позволяет так делать), то на знаки переменных не накладывается никаких ограничений. Переход от произвольных переменных к неотрицательным можно осуществить и заменой переменных, как это описано в Части I.

Последние два параметра “NewC” и ”trAnsform” являются необязательными, т.е. их значения можно не задавать. Об их роли будет вкратце сказано ниже.

PDF created with FinePrint pdfFactory trial version http://www.fineprint.com Теперь можно привести пример записи решения задачи линейного программирования с использованием изложенных выше сведений. Например, для Задачи 5 из Главы II эта > minimize(F,{C1,C2,C3,C4,C5,C6,C7,C8,C9},NONNEGATIVE);

После того как введены (и выполнены нажатием клавиши Enter) все условия и целевая функция, выполняется команда minimize - после нажатия клавиши Enter на экране появляется строка, дающая значения переменных, при которых целевая функция достигает Заметьте, что программа может выдавать значения переменных в точке минимума не в порядке их нумерации, а переменных, а в некотором другом порядке (это вызвано спецификой метода решения задачи) Если вся задача уже записана на данной странице, то не обязательно выполнять каждую команды по отдельности, нажимая Enter много раз. Можно с помощью команды Execute, выбрав подпункт меню Worksheet, выполнить все команды, расположенные на данной странице. Команда Execute расположена в разделе Edit основного меню программы Maple. Можно также выделить (например, с помощью мыши) часть операций и выполнить их с помощью подпункта меню Selection, расположенной там же.

Интересно отметить, что, как это ни странно, вычисление оптимального значения целевой функции пакетом simplex не предусмотрено! Переменные X1,X2... остаются неопределенными даже после вывода точки максимума/минимума. Поэтому для нахождения значения целевой функции приходится писать отдельный набор команд. Например, для приведенной выше задачи можно добавить команды и в результате получить оптимальное значение 3380.

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

PDF created with FinePrint pdfFactory trial version http://www.fineprint.com При этом если изменить форму записи исходной задачи линейного программирования (например, просто переставить между собой линейные условия), то Maple может выдать в качестве ответа совсем другую точку. Для незнакомого с методами линейного программирования такое поведение программы таинственно (и тогда часто он предполагает, что где-то есть ошибка), тогда как на самом деле выдача разных ответов при видоизменении условий есть просто признак не единственности решения. Никаким другим способом непосредственно узнать с помощью Maple о не единственности решения обычно не удается.

Если после нажатия Enter числовой ответ не появляется и нет сообщений о синтаксических ошибках (а система Maple старается не только обнаружить ошибки записи команд, но и подсказать, какого рода и где, по ее мнению, находятся эти ошибки), то это означает, что задача не имеет решения. В этом случае в качестве ответа выводится символ пустого множества { }. Это значит, что у заданной целевой функции нет конечного значения минимума (для случая функции minimize), т.е. при выполнении всех заданных линейных ограничений целевая функция может принимать сколь угодно малые (с учетом знака, хотя и сколь угодно большие по абсолютной величине) значения и потому стремится к -. Такая ситуация возможна, только если область пространства переменных, которая задается линейными условиями задачи, не является ограниченной (хотя для некоторых неограниченных областей минимум все же может достигаться и тогда программа его находит). В принципе возможен и еще один случай отсутствия решения - когда система линейных условий несовместна, т.е. не существует ни одного набора переменных, которые бы удовлетворяли всем условиям задачи (включая условие NONNEGATIVE, если оно используется). Специально для проверки совместности условий в пакете simplex имеется операция feasible, которую перед использованием нужно, если это не было сделано ранее, >with(simplex,feasible);

Формат использования этой операции похож на форматы операций нахождения максимума и минимума (здесь отсутствует только целевая функция):

>feasible(C, vartype, ‘NewC”, “TrAnsform’);

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

Теперь дадим описанию двух дополнительных параметров операции minimize, обозначенных ‘NewC’ и “TrAnsform’ (в реальной записи они могут иметь, конечно, и другие имена). Они используются в случае, когда при решении задачи необходимо иметь дополнительную информацию о ходе решения (производимом с помощью симплекс-метода).

Если в операции указан параметр ‘NewC’, например, стоит имя ‘NC’, то приписываемое переменной NC значение - это система уравнений, к которой приводится исходная задача при ее решении симплекс- методом. Например, выполнение команд > minimize(x-y,{x+2*y>=2, 3*x+y>=4}, ‘NC’):

PDF created with FinePrint pdfFactory trial version http://www.fineprint.com дает в результате (заметьте, что выводить оптимальные значения переменных здесь мы не требовали) систему уравнений:

где _SL1,_SL2 - вспомогательные переменные (которые в пакете simplex имеют стандартные Параметр ‘TrAnsform’ задает имя другого множества - состоящего из всех преобразований переменных, которые производились в процессе решения задачи симплексметодом. В достаточно простых задачах такие преобразования обычно не производятся и тогда значением переменной, задаваемой параметром ‘TrAnsform” является пустое множество. символ которого '{}' и выдается в виде ответа.

Вот пример совместного использования всех параметров функции minimize - решение >C3:= X1+X5C4:= X2+X3C5:=3C6:= X2+X4С:={C1,C2,C3,C4,C5,C6};

> F:=80*X1+60*X2+160*X3+130*X4+50*X5;

После выполнение всех операций в результате получаем точку минимума:

систему условий в стандартной форме:

{X4 = -_SL6 - _SL2 - _SL4 - X5, _SL1 = 27 - _SL6, _SL3 = 10 - _SL6 - _SL2 - 2 _SL4 X5, X1 = -_SL4 + 20 - X5, X2 = 30 + _SL2 + _SL4 + X5, X3 = -_SL5 + 170 - _SL2 - _SL4 - и сообщение о том, что дополнительные преобразования переменных при решении не Опишем теперь некоторые дополнительные операции из пакета simplex. Часть из них касается отдельных этапов решения задачи симплекс - методом и потому здесь подробно описываться не будет (ибо это требует знание деталей симплекс-метода).

equality - с помощью этой операции в линейных условиях задачи производится переход от неравенств к равенствам (условия, заданные в виде равенств, остаются при этом неизменными). Область пространства, которая описывается этими равенствами, вполне PDF created with FinePrint pdfFactory trial version http://www.fineprint.com может оказаться пустой даже в том случае, когда исходная область была непуста. Эта операция представляет собой один из начальных шагов симплекс-метода.

>convert(C,equality);

где C - множество условий в виде неравенств и равенств, convert - это более общая операция Maple’а (см. ниже), но с параметром equality она используется только в пакете simplex..

noneqn - проверка, является ли заданное выражение условием вида a>=0.

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

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

где F - целевая функция, C - система линейных условий, Y - имя для переменных двойственной задачи (которыми в данном случае будут Y1,Y2,...).

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

pivoteqn - выдается подсистему уравнений для заданного главного элемента.

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

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

PDF created with FinePrint pdfFactory trial version http://www.fineprint.com где C - система линейных уравнений в специальной форме (получаемой, например, операцией setup), а X - исследуемая переменная.

Несколько операций пакета simplex представляют и самостоятельный интерес, так как их можно использовать не только для решения задач линейного программирования, но и в stAndardize - это операция приведения системы линейных условий к стандартному виду, в который входят только неравенства вида f(X1, X2,..) C1:=X1-3*X3>=2*X2:

> stAndardize({C1,C2,C3});

в результате получаем систему условий:

{2 X2 - X1 + 3 X3 convexhull({[X1,Y1], [X2,Y2],...});

где в фигурных скобках заключен список точек, заданных парами своих евклидовых На самом деле есть еще две операции, связанные с пакетом simplex. Они в явном виде не упомянуты в описании этого пакета, но фигурируют в примерах по его применению в convert(std) - эта операция - один из частных случаев общей операции convert в Maple5, которая преобразует данные из одной формы в другую. Здесь формат операции где С - система линейных условий. В результате получается система условий в виде линейных равенств или неравенств C1:= X1+X2+X3>=4500:

Переменные: X1=число проданных за день MS Windows 3. Целевая функция: F(X1,X2,X3,X4,X5)=80*X1+60*X2+160*X3+130*X4+50*X5 max Переменные: X1–число автомобилей BMW Целевая функция: F(X1,X2,X3,X4)=1000*X1+1200*X2+800*X3+900*X Ответы к задачам 1-3, как и ко всем остальным, приведены в приложении 3.

PDF created with FinePrint pdfFactory trial version http://www.fineprint.com

ОТВЕТЫ К ЗАДАЧАМ

1. Покупать Zuko - 3000, Yupi - 1000, а Invait не брать.

2. MS Windows 3.1 - 20, MS DOS - 30, MS Windows 95 - 170, OS/2 Warp и PC DOS - 0.

5. Под картофель 320 м2., под огурцы и помидоры 50, под клубнику 80 и под зелень 10 м2.

6. Всего нужно купить минимум 6 кг мяса.

7. Строительных блоков 65 тонн, песка 50 тонн, щебня 5 тонн, а кирпич брать не надо.

8. В первом районе нужно 7 пожарных машин, во втором - 0 (соседи помогут), в третьем - или 10, в четвертом - 3, а в пятом - 8 машин (ответ округлен) 9. “Motor” не брать, “Cross” - 30, “Dallas” - 670, “Levi’s” - 1000, “Gap”- 300 (ответ округлен).

10. Купить по 7 книг классики, 3 - фантастики и 3 энциклопедии (всего 20 книг).

11. МК - 200экз., АиФ - 100экз., “Из рук в руки” - 300экз., “Приглашаю на работу”- 0 экз.

12. Рыбы 40 фунтов, мяса 10 ф., сала и бобов по 0 ф., лепешек - 4 фунта, общая стоимость 13. Топазы - 100 см2.. сапфиры и золото - по 25 см2., серебро - 50 см2.

14. Колготок 15 den - 400 упаковок, 20 den - 100, 40 den и 60 den - 0.

15. Local - 8, Global - 2 (ответ округлен).

16. Сшить по 5 зимних костюмов и фуражек, 16 летних костюмов и 8 спальных мешков 17. 83 сваи 3-го типа или 84 (ответ округлен).

18. 245.5 минут, причем Беллу Борисовну и бабу Галю нужно уволить.

19. Разгрузить 73 коробки тонких тетрадей, по 1 коробке общих тетрадей и туши и 6 коробок 20.Проводить 6 тренировок по ЗКС и 5 тренировок по ОКД (ответ округлен).

21. Купить 6 машин ГАЗ 31029 и 6 Линкольнов (ответ округлен).

22. Тираж словаря - приблизительно 5500 экз., учебника - 8000 экз., “Ключей”экз., а краткого учебника взять примерно 1000 экз. (ответ округлен).

23. Купить 15 катеров и 5 яхт YTM-50L (ответ округлен).

24. Лонжероны - по 14.6 кг., обшивки - по 5.4 кг., дополнительные лонжероны - по 0.14 кг., а уголки, гнутики и нервюры можно брать сколь угодно легкими (в решении их веса равны 0).

25. Выпустить любительской свиной колбасы 1090 кг., столичной 900 кг. и русской - 390 кг 26. На оформление - 700$, на рекламу - 500$, на напитки - 600$, оборудование кухни - 200$.

27. 10 стрижек и 5 химзавивок, выручка 800 руб.

28. Панелей первого типа - 18, второго - 48, третьего - 1, четвертого типа - 60 (ответ 29. Бензина I не брать совсем, бензина II - 200 литров, III - 500 литров, IV литров.

30. Сетей Microsoft NT Server - 18, Novell Netware- 13 или 14, IBM LAN Server - 18, 31. Выпустить 12.7 тонн труб и 10 тонн проволоки, а прутки и ленту не производить.

32. В каждом районе продать по 2 двухкомнатные и по 3 трехкомнатные квартиры (ответ 33. Супа мясного 450 порций, овощного 1150 порций, картофеля с мясом 500, плова PDF created with FinePrint pdfFactory trial version http://www.fineprint.com 34..Молока 190 пакетов, йогурта 10 пакетов, творога 84 пачки, масла 41 пачка (ответ 35. Тостеров биг-маковских 4 или 5, тостеров стандартных - столько же, гриль - 4, фритюрниц - 4 (ответ округлен).

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

1. Гасс С. Линейное программирование. М., 1961.

2. Данциг Дж. Линейное программирование, его применения обобщения. М., 1966.

3. Еремин И.И., Евстафьев Н.Н. Введение в теорию линейного и выпуклого программирования, М., 1976.

4. Сборник задач по высшей математике, Ч.4 Методы оптимизации (под ред. А.В. Ефимова), 5. Карманов В.Г. Математическое программирование, М.,1986.

6. Мину М. Математическое программирование, М., 1990.

7. Юдин Д.Б. Гольдштейн Е.Г. Линейное программирование, М.,1969.

1. Говорухин В.Н.. Цибулин В.Г. Введение в MapleV. М., 1997.

2. Дьяконов В.П. Математическая система Maple V, М., 1998.

3. Манзон Б.М. Maple V Power Edition, М., 1998.

4. Прохоров Г.В., Леденев М.А.. Колбеев В.В. Пакет символьных вычислений Maple V., М., PDF created with FinePrint pdfFactory trial version http://www.fineprint.com