Методы оптимальных решений

НВУЗ АНО «Региональный финансово-экономический институт» МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ ________________________________ http://elearning.rfei.ru СОДЕРЖАНИЕ РАЗДЕЛ 1. О МЕТОДАХ И МОДЕЛЯХ............................................7 Глава 1.1. О моделях и моделировании......................................... 7 Глава 1.2. Из истории экономических методов..........................12 Глава 1.3. Что означают слова «правильное», оптимальное» решение.......................................................................................... 16 Глава 1.4. О применении экономико-математических методов на практике.....................................................................................19 РАЗДЕЛ 2. ИССЛЕДОВАНИЕ ОПЕРАЦИЙ В ЭКОНОМИКЕ.....24 Глава 2.1. Методы оптимизации..................................................24 Глава 2.2. Линейное программирование.....................................33 Глава 2.3. Основная идея симплекс-метода................................39 Глава 2.4. Транспортные задачи...................................................55 Глава 2.5. Об удивительных оптимальных решениях................58 2 ВВЕДЕНИЕ Вот уже более двадцати лет – срок немалый – страна строит новую, рыночную экономику. За это время в открывшемся океане экономической свободы захлебнулись и пошли на дно целые поколения отважных первооткрывателей-предпринимателей. Но коекто – и таких миллионы – выжил, создал собственное дело, процветает. И всем интересно понять, в чем тут дело: почему одни — в пучине, а другие – на поверхности? Тысячи умных книг объясняют причину успеха счастливчиков их высокими бойцовскими качествами: смелостью, способностью идти напролом, упорством в достижении цели, невзирая ни на какие преграды (включая законы). Все это так. Не случайно среди «новых русских» немало крутых ребят, «накачанных» спортсменов, авантюристов, людей с «особым» прошлым (а порой и настоящим). Но как тогда объяснить еще более внушительный и масштабный результат в бизнесе, полученный тщедушными интеллектуалами: математиками, физиками, инженерами, которых трудно заподозрить в «особом» прошлом? Осмелимся предложить наш вариант ответа: успех предпринимательской деятельности в немалой степени зависит от способности «шевелить мозгами», понимать цифры, вести расчеты. Считать сегодня умеют, конечно, все. Но этот счет очень часто ограничивается умением складывать и умножать. Когда же дело доходит до расчетов, связанных с дробями или процентами, школьная эрудиция многих дает осечку. Между тем коммерческие расчеты сегодня не ограничиваются школьной математикой. Вычисления, связанные с кредитными отношениями, работой с биржами и банками, прогнозированием и риском, не укладываются в элементарную арифметику. И дело здесь не только в умении правильно выстроить колонки цифр. Современный бизнес требует современного эконо3 мического мышления, в немалой степени основанного на специальных математических методах. Доход, прибыль, налог, ссуда, дивиденд, рентабельность – все это цифры, и тут без хорошей математики просто не обойтись: чем правильнее расчет, тем прибыльнее результат. В современной экономике математика (часто далеко не элементарная) выступает в качестве необходимого инструмента, с помощью которого предприниматель или сотрудник банка может выбрать наилучший вариант действий из многих возможных. Соединение экономики бизнеса с математическими расчетами получило название экономико-математических методов (с этим курсом вы уже успели познакомиться). Возможности, которые применение математики открывает для рационального решения реальных экономических задач, лучше всего рассмотреть на простых примерах. Пример 1. Вам предлагают купить зерно весом в 100 тонн. Взвешивание производилось некоторое время тому назад и при этом было определено процентное содержание в зерне жидкости, которое составляло 99%. На момент покупки за счет усушки доля жидкости уменьшилась до 96%. Необходимо рассчитать, сколько весит предлагаемый товар. Подавляющее большинство студентов обычно называли вес около 97 тонн. Расчет, однако, показывает, что зерно при покупке должен весить ровно 25 тонн. Пример 2. Вы стали обладателем 27 одинаковых по размеру и внешнему виду бриллиантов. В сертификате на драгоценные камни указано, что один из них весит на незначительную величину меньше, чем остальные. Вес камней неизвестен. Желая отбраковать неполноценный камень, вы попросили ювелира произвести взвешивание бриллиантов. Каждое определение веса на высокоточных чашечных весах стоит 100 руб. Какую сумму придется уплатить ювелиру? Интуитивное решение задачи подсказывает, что число взвешиваний будет значительным, никак не меньше 20, а значит, обойдется более чем в 2000 руб. Между тем математический расчет дает сумму уплаты, равную 300 руб. 4 Пример 3. Вы собираетесь заключить сделку с некоей фирмой, причем знаете, что эта сделка может по отношению к вам оказаться как честной, так и нечестной. Переговоры с вами ведет представитель фирмы, которому известны ее намерения. Представитель может быть как правдивым человеком, так и лжецом. Как вы думаете, можно ли, задав этому представителю единственный вопрос и получив в ответ «да» или «нет», безошибочно оценить, будет ли сделка честной? На первый взгляд задача кажется совершенно нереальной: слишком уж велика степень неопределенности. На самом деле задача имеет вполне определенное решение. Рассмотрением таких примеров мы и начнем наш курс. Главная особенность всех рассмотренных примеров в том, что глазомерные, интуитивные решения оказываются несостоятельными. Сбои, которые дает наша интуиция при решении расчетных задач – явление весьма характерное и вполне объяснимое. Наш мозг приспособлен успешно и быстро решать лишь те задачи, которым обучен. В этом он напоминает компьютер: нет программы – нет и решения. Разница лишь в том, что при отсутствии программы компьютер просто не будет работать, а вот человек – станет и допустит грубую ошибку. Это очень опасно. Ведь за каждым таким решением стоят упущенные возможности, без толку растраченные ресурсы, потерянное время. Экономико-математические методы и методы оптимальных решений, которые выделены в отдельную дисциплину из этого большого курса, как раз и призваны оградить предпринимателей, работников банковской сферы и менеджеров от подобных ошибок, дать им надежное средство для правильного решения экономических задач. Решение большинства задач экономической практики базируется на элементарной математике: арифметике, алгебре, геометрии. Это задачи с дробями, процентами, пропорциями, прогрессиями, уравнениями. Находят применение также функции и графики, комбинаторика, логика. Наряду с элементарной математикой и логикой рассматриваются также задачи, требующие применения 5 аппарата высшей математики, особенно в теории вероятностей и математической статистике, а также в таких сравнительно молодых методах, как математическое программирование (линейное, нелинейное, динамическое), теория игр и статистических решений, теория массового обслуживания (теория очередей), метод статистических испытаний (Монте-Карло), сетевое планирование. Попытаемся рассмотреть отдельные задачи доступными методами, но при таком упрощении неизбежно пострадает строгость изложения и доказательств, за что мы должны принести свои извинения строгой математике. 6 РАЗДЕЛ 1. О МЕТОДАХ И МОДЕЛЯХ Глава 1.1. О моделях и моделировании Рассмотрим типичную производственно-экономическую ситуацию. На предприятии каждый из операторов обслуживает 6 однотипных объектов. Это могут быть потребители, клиенты, технические устройства. При возникновении у одного из объектов потребности в обслуживании оператор получает соответствующий сигнал, производит обслуживание и ждет следующего вызова. Следовательно, какую-то часть своего рабочего времени оператор находится «на простое», что, понятно, ведет к экономическим потерям предприятия. Стремясь сократить простои, менеджер (управляющий банком) увеличивает нагрузку на операционистов: добавляет каждому еще по одному объекту обслуживания. Из этого ничего хорошего не получается: операционисты перестают справляться со своими обязанностями. Пока идет обслуживание одного из объектов, поступает вызов от другого, а поскольку в этот момент операционист, занят образуется очередь на обслуживание. Менеджеру (управляющему банком) приходит на ум интересная идея: а нельзя ли создать бригаду из четырех операционистов и закрепить за всеми вместе 26 объектов? Может быть, в этом случае простои сократятся – из четырех операционистов всегда кто-нибудь да окажется свободен и готов к обслуживанию очередного вызова. При таком распределении появится явный выигрыш: среднее число объектов, приходящихся на одного операциониста, увеличится по сравнению с существующим и станет равным 26 : 4 = 6,5. Налицо прямая выгода. Но почему 26 на четырех, а не, допустим, 21 на троих – при этом выигрыш будет еще больше (21 : 3 = 7). Кстати, а где гарантия, что при предлагаемых увеличениях нагрузки будут устранены очереди? 7 Решить такую задачу опытным путем, перебирая различные варианты прикрепления операционистов к объектам, практически невозможно. Ни в каком опыте нельзя воссоздать все те условия, которые бывают в жизни: вызов от каждого объекта может прийти в любое время (в первую минуту, во вторую минуту и т. д.), да и время обслуживания может быть самым различным. Попробуйка перебрать все возможные сочетания для всех объектов. Как же быть? В подобном положении оказываются представители многих профессий. Скажем, конструктор проектирует новый самолет. Можно сделать его в сотне, тысяче различных вариантов. Но какой из них лучше? Не строить же по каждому варианту самолет! И конструктор находит выход. Он делает вначале не настоящий самолет, а его модель. Несложная по устройству и поэтому недорогая модель не только заменяет на испытаниях реальный объект, но и делает его доступнее для изучения. К моделированию прибегают всегда, когда необходимо разобраться в каком-нибудь сложном явлении, уловить его скрытые закономерности. Например, модель плотины гидроэлектростанции нужна инженерам для того, чтобы решить, каким должно быть это сложнейшее сооружение в действительности. При этом совершенно неважно, из какого материала смоделированы берега реки и железобетонное тело плотины. Они могут быть из обычного дерева или пластмассы. И тем не менее такая игрушка ведет себя во многом совсем как настоящая река, перегороженная настоящей плотиной. Простота модели по сравнению с реальным объектом достигается тем, что в ней сохраняется лишь самое главное, наиболее важное, а все второстепенное, не существенное для интересующей нас задачи, отбрасывается. Модель чем-то напоминает беглый карандашный набросок. Один-два штриха на бумаге – и вот уже видны не только знакомые черты, но и характер, неповторимый образ человека. Кстати, портрет и скульптура, литературный образ и даже фотография любимого человека – это тоже модели. Модели, выполненные художественными средствами. 8 Создание моделей ситуаций, требующих принятия решений, моделей операций, как их называют, безусловно, совершается и в мозгу человека. А нельзя ли попробовать создать модель интересующего нас процесса обслуживания объектов операторами? Вот только из какого материала ее лучше сделать? Оказывается, самым удобным, податливым (и дешевым) «материалом» для подобных моделей является не дерево, не пластмасса, а математика. Представьте себе математическую формулу, показывающую, от чего зависит эффективность работы наших операторов. Подставляя в эту формулу цифры, показывающие возможное число объектов и количество обслуживающих их операторов, а также среднее время обслуживания, мы можем получить решение, обеспечивающее эффективную работу предприятия. Математика – язык, на котором сегодня говорит любая точная наука. В наши дни математика прочно вошла и в такие науки, как биология, психология и в науку о языке. Не отстает и экономика. Поэтому можно утверждать, что сбываются слова великого французского ученого, родоначальника рационализма Рене Декарта (1596-1650): «Все исследования, направленные на изучение порядка и меры, принадлежат математике». Когда с помощью модели «из математики» (она получена на основе теории массового обслуживания) – одного из экономико-математических методов – произвели расчеты нашей задачи, оказалось, что наилучший результат получится, если группу из трех операционистов закрепить за 20-ю объектами. В этом случае без всяких дополнительных затрат заметно увеличивается производительность труда, сокращаются простои операционистов, их загрузка увеличивается примерно на 8%. И еще одно важное обстоятельство. Удобство математического моделирования не только в его простоте и универсальности. Математическая форма модели позволяет привлечь для анализа сложнейших экономических ситуаций и выработки трудных решений мощного помощника – компьютер. Вот несколько примеров экономико-математического моделирования. 9 Пример 1.1. Рассмотрим формулу эффективности (Э): , где Р – результат деятельности, 3 – затраты на получение данного результата. Эта модель просто и наглядно показывает, что эффективность прямо пропорциональна результату и обратно пропорциональна затратам. Пример 1.2. Применим экономическое моделирование для изучения производственных возможностей. Производственные возможности показывают способность предприятия производить различные наборы (сочетания) товаров при постоянстве ресурсов и при условии их полного использования. Рассмотрим несколько ситуаций. На маленький необитаемый остров в результате кораблекрушения или по условиям известной игры, транслируемой на ТВ, выброшена группа людей (небольшой остров здесь нужен для оправдания ограниченности ресурсов). На острове водятся кролики, в реке есть рыба. Наши «робинзоны» в состоянии в день поймать в среднем либо одного кролика и 6 кг рыбы, либо трех кроликов и 4 кг рыбы, либо пять кроликов без рыбы. Построим график производственных возможностей. 10 Рисунок 1.1 Для этого будем откладывать по оси X количество ежедневно отлавливаемых кроликов, а по оси Y – количество килограммов ежедневно вылавливаемой рыбы (рис. 1.1). Для каждого из возможных сочетаний улова отметим точки на графике и по ним построим кривую линию. Это и будет кривая производственных возможностей (она показана двойной линией на рисунке 1.1). Кривая производственных возможностей вогнута относительно начала координат, что говорит о характере зависимости между количеством добываемых источников пищи обоих видов: увеличение одного из них ведет к уменьшению другого, и наоборот. Все точки кривой производственных возможностей соответствуют такому сочетанию товаров (добываемых источников пиши), которое возможно для данных условий или, как принято говорить, соответствует эффективному бизнесу. Это, например, 4 кролика и 2 кг рыбы. Точки, лежащие внутри кривой производственных возможностей, показывают такое сочетание товаров (количества кроликов и рыбы), при котором возможности обитателей острова используются не полностью. А точки, лежащие снаружи кривой, соответствуют такому сочетанию источников пищи, получение которого обитателями острова невозможно. 11 Построенная кривая соответствует вполне определенным возможностям обитателей острова: их количеству, умению охотиться, рыбачить и т. д. Стоит изменить эти возможности – и кривая переместится на графике вправо при росте возможностей или влево при их снижении. Это показано на рисунке 1.1 с помощью одинарных линий. Нетрудно убедиться, что для линии уменьшившихся производственных возможностей количество улова уменьшается, а для линии увеличившихся возможностей – растет. Итак, линия производственных возможностей позволяет решать следующие задачи: определять условия эффективного бизнеса; демонстрировать недостаток или избыток возможностей для конкретного сочетания производимых товаров; оценивать, за счет какого увеличения или уменьшения производимых товаров можно прийти к эффективному бизнесу. Математические модели, созданные для целей экономики, изучаются специальной научной дисциплиной, получившей название «экономико-математические методы и модели», с которой вам уже удалось познакомиться и выполнять практическую работу. Глава 1.2. Из истории экономических методов Экономико-математические методы представляют собой своеобразный инструментальный набор, с помощью которого экономисты, бизнесмены, менеджеры, стремясь добиться наилучшего эффекта, «обрабатывают» свой материал. Этот инструментарий имеет свою историю. В 1938 г. к двадцатипятилетнему профессору Ленинградского университета Леониду Витальевичу Канторовичу обратились представители фанерного треста с необычной для того времени просьбой. Требовалось рассчитать наивыгоднейшее распределение работы восьми станков при условии, что известна производительность каждого станка по каждому из пяти видов материалов. Наука того времени не располагала методами для подобных решений. И молодому ученому ничего другого не оставалось, 12 кроме как придумать свой оригинальный метод решения «станковой» задачи. Но главное, сделанное Л.В. Канторовичем, выходит далеко за пределы забот фанерного треста. Отталкиваясь от частной задачи, ученый нашел общий метод решения целого ряда важнейших экономико-производственных проблем. Новый метод, названный линейным программированием, дал ответ на вопрос: как управлять предприятием, чтобы обеспечить максимально возможную прибыль. И частично вы с этим методом сталкивались при рассмотрении курса «Экономико-математические методы и модели». За разработку метода линейного программирования и экономических моделей академик Л.В. Канторович совместно с американским профессором К. Купмансом в 1975 г. получил Нобелевскую премию по экономике. Линейное и, шире, математическое программирование – сейчас один из основных методов обоснования производственно экономических решений. Но не единственный. Сегодня наряду с ним существует целый арсенал математических средств выработки наилучших решений. С этим замечательным арсеналом и его практическим применением мы познакомимся в рамках этого курса. Среди образцов экономико-математического «вооружения» встречается как старое, проверенное веками «оружие» – арифметика, алгебра, геометрия, так и специально разработанные математические методы, появившиеся сравнительно недавно и получившие название методов исследования операций. Исследование операций было призвано решать те задачи, с которыми традиционная математика уже не могла справиться. Заметный толчок развитию методов исследования операций дала Вторая мировая война. Тогда для выработки военных решений были привлечены значительные научные силы: ученые-математики, физики, биологи (только в США над исследованием операций трудилось более 800 ученых, в том числе – с мировыми именами). Их объединенными усилиями, по сути, было создано новое научное направление. 13 В послевоенные годы методы исследования операций получили широкое распространение во всех отраслях народного хозяйства: в промышленности, на транспорте, в торговле. При этом под операцией стала пониматься любая целенаправленная деятельность человека. Методы исследования операций стали научной основой экономико-математических методов. Исследование операций иногда называют «количественным выражением здравого смысла». Существует, правда, и более скромное определение: «исследование операций представляет собой искусство давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими способами». Как понимать это признание английского ученого Т. Саати? Как пишет известный российский специалист профессор Е.С. Вентцель, исследование операций «способно дать плохой ответ на вопрос, на который нельзя ответить по-другому». Иными словами, эта наука в большинстве случаев остается единственным средством для принятия обоснованных решений в сложных ситуациях. Чем же объяснить, что многие из тех, кому приходится постоянно принимать ответственные экономические решения, и не слышали о существовании столь полезной науки? Думаем, главная причина – в трудности освоения этих методов, которые обычно описываются на сложном языке высшей математики, малодоступной для людей, не имеющих соответствующей подготовки. Поэтому в нашей лекции сделана попытка обойти такие трудности, переложив экономико-математические методы на общедоступный язык школьной математики, который знаком нам с детства. Трудности такого изложения хорошо описал известный американский специалист по исследованию операций Ричард Беллман: приходится идти «прямой и узкой тропой между Западнями Переупрощения и Болотом Переусложнения». И тем не менее другого пути нет. Отправимся же в это нелегкое, но столь необходимое и полезное путешествие. Каждый из экономико-математических методов подобно разнообразным инструментам, находящимся в распоряжении специалиста, имеет свою область применения. 14 Элементарная арифметика и алгебра (уравнения, функции и графики) применяются для экономических расчетов, связанных с определением долей, процентов материальных ресурсов, составлением пропорций, счетом денег, вычислением прибыли, налогов, рентабельности и т.п. Арифметические и геометрические прогрессии позволяют вести расчеты, связанные с последовательностями экономических показателей и объектов (например, так называемые «пирамиды», и вы тут же ассоциируете это с нашумевшей «пирамидой» С. Мавроди, обобравшей тысячи пожилых людей). Комбинаторика дает возможность определять результаты, возникающие при различных сочетаниях экономических объектов, перестановках и размещениях. Геометрия предназначена для вычислений, связанных с пространственными отношениями и формами объектов, интересующих экономиста. Логика позволяет оценить экономическую ситуацию с точки зрения истинности или ложности используемой информации, разобраться в запутанных обстоятельствах, найти рациональный выход из затруднительного положения. Линейное программирование предназначено для выработки оптимального решения экономической задачи для случая, когда ее условия и имеющиеся ограничения описываются уравнениями или неравенствами 1-й степени. Нелинейное программирование служит для выработки оптимального решения экономической задачи в том случае, когда ее условия и ограничения описываются уравнениями или неравенствами 2-й степени и более. Динамическое программирование дает возможность выбора оптимального плана многоэтапных действий, в которых результат каждого последующего этапа зависит от предыдущего. Теория вероятностей обосновывает экономические расчеты, связанные с явлениями случайного характера. Математическая статистика обеспечивает сбор, обработку и анализ экономических статистических материалов. 15 Теория массового обслуживания (теория очередей) дает расчеты производственно-экономических показателей и выработку необходимых рекомендаций для массовых повторяющихся процессов обслуживания. Метод статистических испытаний (Монте-Карло) служит для производства экономических расчетов, связанных с явлениями случайного характера, на основе искусственно произведенных статистических материалов. Теория игр служит для выработки экономических решений в условиях неопределенности, неясности ситуации, вызванной сознательными, злонамеренными действиями конфликтующей стороны. Теория статистических решений применяется для выработки экономических решений в условиях неопределенности, вызванной объективными обстоятельствами, которые либо неизвестны, либо носят случайный характер. Сетевое планирование применяется для составления и реализации рациональных планов ведения экономических операций, предусматривающих решение задачи в кратчайший срок и с наилучшими результатами. Столь богатый арсенал методов решения экономических задач делает весьма актуальным вопрос: а как из многих возможных вариантов решения определить наилучший, правильный, самый хороший или, как часто говорят, оптимальный? Какой смысл вкладывают в понятия «правильное», «оптимальное» решение экономической задачи? Глава 1.3. Что означают слова «правильное», оптимальное» решение Начнем с примера. Пример 1.3. Маркетинговое исследование показало, что в требуемый срок партия однотипного товара может быть продана по цене: – 30 у. ед. (условных денежных единиц) за штуку – в количестве 100 штук; 16 – 40 у. ед. за штуку – в количестве 80 штук; – 50 у. ед. за штуку – в количестве 60 штук. По какой из этих цен следует продавать товар? Иными словами – какое из трех возможных ценовых решений лучше? Не торопитесь с ответом. Ибо «лучшего» решения как такового – на все случаи жизни – не бывает. О качестве решения можно судить, лишь зная цель операции. Таких целей здесь может быть несколько: – продать товар по максимальной цене; – продать максимальное количество товара; – продать товар по цене, обеспечивающей максимальную выручку. Зная цель, можно сказать, какое отвечающее ей решение лучше: если цель – продать товар по максимальной цене – лучшее решение: «продавать по 50 у. ед.»; если цель – продать максимальное количество товара – лучшее решение: «продавать по 30 у. ед.»; если цель – продать товар по цене, обеспечивающей максимальную выручку, – лучшее решение: «продавать по 40 у. ед.». Таким образом, качество решения определяется степенью его соответствия цели: чем с меньшими затратами ресурсов и времени может быть достигнута цель при данном решении, тем оно лучше и «правильнее». Непонимание цели предстоящей экономической операции лишает решение смысла: ведь чтобы получить правильный ответ, нужно задать правильный вопрос. Весьма образно сказал по этому поводу немецкий философ И. Кант: «Если вопрос сам по себе бессмыслен и требует бесполезных ответов, то кроме стыда для вопрошающего он имеет иногда еще тот недостаток, что побуждает неосмотрительного слушателя к нелепым ответам и создает смешное зрелище: один (по выражению древних) доит козла, а другой держит под ним решето». Примером неправильно сформулированного оптимального решения может служить расхожая фраза: «получение максимума 17 доходов и минимума расходов» (ее первоисточник: «максимум надоев при минимуме кормов»). Вдумаемся. Поскольку, как известно, увеличение доходов до максимума отнюдь не ведет к снижению расходов до минимума, совершенно неясно, какое решение принимать. То ли добиваться, чтобы доходов стало как можно больше, то ли, чтобы расходов – как можно меньше. Правильным было бы сформулировать оптимальное решение как «получение максимума доходов при данных расходах» или «получение данных доходов при минимуме расходов». Из всего сказанного ясно, что исследование операций и экономико-математические методы не ограничиваются лишь словесным формулированием цели, а речь идет о количественном обосновании решений. Мало сказать: «хорошее» или «оптимальное» решение, нужно уметь оценить его с помощью конкретной цифры. Как же связать цель, к которой мы стремимся, с определенным числом? Лев Толстой как-то, видимо в шутку, предложил измерять качество человека с помощью дроби, в числителе которой стоит оценка его действительных достоинств, а в знаменателе – показатель его мнения о себе. От действительных достоинств качество человека повышается, от самомнения – падает. В соответствии с идеей великого писателя и с соответствующей степенью серьезности проведем следующий эксперимент. Спросим кого-нибудь из знакомых, как он (она) оценивает себя по пятибалльной системе оценок. Скажем, называется оценка 4. Эта цифра и ставится в знаменатель дроби. Далее просим дать оценку этого человека (желательно анонимно) кого-нибудь из окружающих его людей. Предположим, называется 3. Помещаем тройку в числитель дроби, и «показатель качества человека» готов. Он равен 3 , или 0,75. 4 Заметим, что если бы тот, кого оценивают, был несколько скромнее (допустим, ценил себя на 3 балла) либо заслужил более высокую оценку окружающих (например, 4 балла), то его «показатель по Л.Н. Толстому» поднялся бы в обоих случаях до 1. 18 В рассуждениях Толстого заложен глубокий смысл. Количественные показатели, выражающие цель операции, находят в экономико-математических методах самое широкое применение. Так, работа любого предприятия характеризуется объемом выпускаемой продукции, прибыльностью, затратами и т.д., и если нужно стремиться иметь первые два показателя побольше, то вряд ли это можно сказать о третьем. Используя методы исследования операций, можно установить не только, какой показатель следует наращивать, но и то его требуемое значение, которое необходимо для экономического успеха. Выбор показателя успешности операции, так же как и подбор соответствующего экономической задаче математического метода – не только наука, но и своеобразное искусство. Искусство же, как правило, требует постоянных упражнений. Каким же видится порядок решения практических задач с помощью экономико-математических методов? Глава 1.4. О применении экономико-математических методов на практике Для решения конкретных практических экономических задач можно рекомендовать такую последовательность: 1. Уясняем задачу – ее экономический смысл. На этой основе устанавливаем цель решения. 2. Оцениваем экономическую ситуацию – определяем, от чего зависит достижение установленной цели. 3. Выбираем численный показатель, от которого достижение цели зависит в первую очередь. 4. Строим математическую модель операции, устанавливающую количественные зависимости избранного показателя от условий задачи. 5. С помощью математической модели и найденного экономико-математического метода решаем задачу. 6. Проверяем правильность найденного решения. Лучше всего рассмотреть практическое применение экономико-математических методов на конкретных примерах. В качестве первого такого примера возьмем пример 1 из введения. Итак, по порядку: 19 1. Экономический смысл задачи в том, что, рассчитывая уменьшение веса товара за счет усушки, мы не располагаем прямыми данными об уменьшающемся весе товара. Цель решения — определить по косвенным данным о сокращении процентного содержания в товаре жидкости, насколько снизился вес за счет усушки. 2. Снижение веса зависит от изменения количества испаряющейся в процессе усушки жидкости, что отражается в сокращении ее процентного содержания в товаре. 3. Основным показателем снижения веса товара является его абсолютное изменение, а не изменение процентного содержания жидкости. Ибо изменение содержания жидкости на определенный процент вовсе не означает, что и вес товара изменится на тот же процент. 4. Математическая модель должна установить зависимость абсолютного изменения веса товара при усушке от изменения процентного содержания воды. Поскольку в нашей задаче речь идет об определении процентов и пропорций, в качестве экономико-математического метода целесообразно избрать арифметику и алгебру. В соответствии с алгебраическими правилами обозначим через х искомый вес товара при втором замере содержания жидкости и составим очевидное уравнение, которое и будет математической моделью нашей задачи: x −1 96 = 96% = x 100 . Здесь 1 тонна – это вес сухого остатка, т.е. неиспаряемой части товара, одинаковой для первого и второго замера. Этот вес определяется по результатам первого замера содержания жидкости: 100 т – 99% от 100 т = 1 т. 5. Решая уравнение (пропорцию), получим: 100 ⋅ ( x − 1) = 96 x или 100 x − 96 x = 100 , 4 x = 100 , x = 25т. В рассмотренном примере, как и во многих других практических экономических задачах, нет необходимости производить оптимизацию. Требуется лишь произвести правильный расчет 20 необходимого показателя – получить единственно возможное решение. Следующий пример потребует выполнить оптимизацию. Это пример 2 из введения. Приступим к процедуре расчета: 1. Экономический смысл задачи – найти фальшивый бриллиант с минимальными расходами на взвешивание. Отсюда цель решения: определение минимального числа взвешиваний, достаточного для выявления подделки. 2. Число взвешиваний связано как с количеством исследуемых бриллиантов, так и с порядком разделения их на части для поочередного взвешивания. 3. Поскольку мы имеем дело с чашечными весами, взвешивание должно производиться путем раскладки различных количеств камней по чашкам весов. Если при равных количествах камней на обеих чашках весы уравновешиваются, значит, подделка находится среди тех камней, которые исключены из взвешивания. Если же груз на одной из чашек оказался легче, чем на другой, значит, там и находится фальшивый камень. Самый простой способ поиска – уложить на одну чашку какой-нибудь из камней, а на другую поочередно класть остальные 26 бриллиантов. Это потребует максимально возможного числа взвешиваний – 26-ти. Нас, однако, интересует не максимум, а минимум. Поэтому такой перебор (его в исследовании операций называют сплошным или «слепым») нас явно не устраивает. Следует искать способ более рационального выбора, ведущего к уменьшению количества взвешиваний. Таким образом, достижение поставленной цели зависит от выбора такого разделения камней при взвешивании, при котором количество взвешиваний окажется минимальным. Основным показателем, от которого зависит достижение поставленной цели, является минимум количества взвешиваний, приводящий к решению задачи – определению подделки с минимальными расходами. 21 4. Математическая модель задачи должна связать минимальное количество взвешиваний с общим количеством камней и количеством камней в каждой группе при их разделении. Подобная модель может быть построена с помощью одного из методов оптимизации – линейного программирования, о котором Вы уже частично узнали из практикума к курсу «Экономикоматематические методы и модели», устанавливающего правила направленного, т.е. рационального, перебора вариантов. В данной задаче суть направленного перебора в том, что если разделить камни на три одинаковые части и две из них разложить по чашкам весов, то всего за одно взвешивание можно определить, в какой из трех частей находится фальшивый бриллиант. Затем та часть, где обнаружена подделка, снова делится на три, снова производится взвешивание, и так до тех пор, пока в последней тройке не окажется три камня. Теперь уже взвешивание однозначно укажет на то, какой камень поддельный. Такой направленный перебор резко сократит необходимое количество взвешиваний. В данном примере их потребуется всего лишь три. Перейдем на язык математики: минимальное потребное количество взвешиваний ( Вмин ) можно получить, исходя из очевидного соотношения: откуда В N = 3 , где N – количество исследуемых объектов. Это и есть математическая модель задачи. 5. Произведем численный расчет: подставляя в формулу В N = 3 значение N = 27, получим В 27 = 3 , откуда видно, что минимальное количество взвешиваний равно 3. 6. Расчет легко проверить, проведя мысленный опыт: мин мин мин 22 1-е взвешивание. На чашках весов по 9 камней. Определяем, в какой девятке подделка. 2-е взвешивание. На чашках весов по три камня. Определяем, в какой тройке подделка. 3-е взвешивание. На чашках весов по одному камню. Находим фальшивый бриллиант. Что и требовалось доказать. Итак, рассмотрев примеры решения задач, предложенных во введении в курс, вы заметили, что мы пользовались пока знаниями элементарной математики. Но вы уже познакомились с математикой, которую называют «высшей», поэтому следующая глава будет посвящена рассмотрению оптимизационных задач с помощью «высшей» математики. 23 РАЗДЕЛ 2. ИССЛЕДОВАНИЕ ОПЕРАЦИЙ В ЭКОНОМИКЕ Глава 2.1. Методы оптимизации Как уже было сказано, в реальной экономике нередко приходится искать наилучшее решение, руководствуясь несколькими (порой противоположными) целями. Примерами противоречивых целей являются, например: - минимальные затраты и одновременно минимальное время выполнения определенной работы; - максимальная доходность финансовой операции и при этом минимальный риск; - максимальная прибыль при реализации определенного вида товара и минимальные затраты на ресурсы для его производства; - максимальная эффективность вложенных средств и одновременно максимальный объем производства. Наряду с рассмотренными в предыдущем разделе примерами, представим себе бизнесмена, руководителя фирмы. Он размышляет, не нанять ли ему еще одного работника, чтобы увеличить прибыль фирмы. Существует, однако, простое правило для разрешения подобного вопроса: нанимать следует только тогда, когда дополнительный доход, полученный от этого, превысит назначенную ему зарплату. Это простое правило столь лаконично и значимо, что его называют «золотым правилом экономики». Суть этого правила изложена, придадим ему математическое обрамление. Предположим, фирма выпускает только один товар и обозначим его через y . Используется только один ресурс. Фирма полностью характеризуется своей производственной функцией y = F( x ) – зависимостью объема выпускаемого товара от объема затраченного ресурса x . 24 Предполагается, что производственная функция удовлетворяет двум аксиомам: 1) хотя бы на части ее области определения, называемой экономической областью Е, эта функция неубывающая, тогда производная функции F ' ( x ) неотрицательна. (Об этом вы должны были узнать из раздела «Математический анализ» курса «Математики»). Эта производная функции называется предельным продуктом (это будет означать, что от функции берется производная, т. е. находится F' ( x ) = ∆lim x →0 ∆F ); ∆x 2) существует некоторое подмножество S этой экономической области, в котором вторая производная неположительна. Остановимся на экономическом содержании этих двух аксиом. Первая аксиома утверждает, что производственная функция отражает бесспорное и в то же время тривиальное утверждение: в мало-мальски разумной экономике увеличение затрат не может привести к уменьшению выпуска. Из второй аксиомы поясним только экономический смысл требования неположительности второй производной. Это свойство называется в экономике законом убывающей отдачи или убывающей доходности: по мере увеличения объема затраченного ресурса, начиная с некоторого момента (при входе в область S), начинает уменьшаться предельный продукт. Классическим примером этого закона является добавление все большего и большего количества труда в производство зерна на фиксированном участке земли. В дальнейшем будем считать, что производственная функция имеет необходимые производные и удовлетворяет обеим аксиомам на всей области определения. Приведем пример предельных показателей в микроэкономике. Например, себестоимость С произведенной продукции от ее объема Q задается зависимостью C = f (Q) . Тогда предельная себестоимость характеризует себестоимость ∆C прироста продукции 25 ∆Q и задается видом C' (Q) = lim ∆Q → 0 ∆C . Если, к примеру, зависи∆Q мость издержек производства от объема выпускаемой продукции имеет вид C = 10Q − 0,5Q 2 , то предельные издержки при объеме продукции стоимостью Q = 5 ден.ед. найдутся как значение производной от издержек при Q = 5 . Иными словами, C' = (10Q − 0,5Q 2 )' = 10 − 0,5 ⋅ 2Q = 10 − Q = 10 − 5 = 5 ( ден.ед). Или другой пример. Пусть р — цена единицы ресурса, и v — цена единицы выпускаемого товара. Следовательно, прибыль W, являющаяся в итоге функцией х (и цен, но они считаются постоянными), есть W ( x ) = v ⋅ F( x ) − p ⋅ x. Следовательно, приходим к задаче фирмы, где необходимо максимизировать функцию, при затраченном ресурсе 0 = v ⋅ F ' ( x ) − p. x , т. е. W ( x ) → max , x ≥0. (2.1) Тогда в соответствии с первой аксиомой возьмем от функции W ( x ) производную и приравняем ее к нулю. W ' ( x ) = ( v ⋅ F( x ) − p ⋅ x ) ' . Для дальнейших рассуждений нужны знания из курса математики, а именно то, что производная разности равна разности производных, а так же свойство о том, что постоянный множитель можно выносить за знак производной, ну и, конечно, производную от x по x . А она равна единице. Тогда получим: p 0 = v ⋅ F ' ( x ) − p, или F ' ( x ) = . (2.2) v Очевидно, что объем перерабатываемого ресурса положителен и, следовательно, точка, даваемая соотношением (2.2), оказывается внутренней, т. е. точкой экстремума, а поскольку еще предполагается неположительность второй производной, то это точка максимума. (А почему эта точка будет точкой максимума, вы выясняли в разделе «Математический анализ» курса «Математика»). 26 Там было сказано, что если вторая производная функции в точке будет неположительной ( ≤ 0) , то эта точка будет точкой максимума. Итак, при естественных предположениях на производственную функцию (эти предположения выполняются для производителя со здравым смыслом и в разумной экономике) соотношение (2.2) дает решение задачи фирмы, т. е. определяет объем перерабатываемого ресурса, в результате чего получается выпуск, дающий максимальную прибыль. Точку, даваемую соотношением (2.2), назовем оптимальным решением фирмы. Остановимся на экономическом смысле соотношения (2.2). Напомним, что F'(x) называется предельным продуктом, vF'(x) — это стоимость предельного продукта, дополнительно полученного из единицы ресурса. Однако стоимость единицы ресурса равна р, т. е. получилось равновесие: можно вовлечь в производство дополнительно единицу ресурса, потратив на его закупку р, но в результате выигрыша не будет, так как получим после переработки и реализации произведенного товара столько же денег, сколько затратили на покупку единицы ресурса. Итак, оптимальная точка, даваемая соотношением (2.2), является точкой равновесия — уже невозможно «выжать» из товаров ресурсов больше, чем затрачено на их покупку. Очевидно, наращивание выпуска фирмы происходило постепенно: сначала стоимость предельного продукта была меньше покупной цены потребного для его производства ресурсов. Наращивание объема производства идет до тех пор, пока не начнет выполняться соотношение (2.2): равенство стоимости предельного продукта и покупной цены потребного для его производства ресурса. При условиях, наложенных на производственную функцию, оптимальное решение задачи фирмы, даваемое соотношением (2.2), единственно для всех р и v. Если мы обозначим точку x , являющуюся решением уравнения (2.2), как некоторую точку x 0 , то получим функцию x 0 = x 0 ( p, v) , называемую спросом на ресурс. Что означает эта функция? 27 Если сложились цена р на ресурс и цена v на выпускаемый товар, то фирма, характеризующаяся данной производственной функцией, определяет объем перерабатываемого ресурса в соответствии с функцией x 0 ( p, v) и будет закупать ресурс в этом объеме на рынке, т. е. это есть функция спроса со стороны фирмы на ресурс. А дальше, уже зная объем перерабатываемого ресурса и подставляя этот объем в производственную функцию, получим объем выпускаемого товара как функцию цен. Последняя функция называется функцией предложения продукции. В микроэкономике часто употребляют термин «равновесная цена». Выясним, что это такое. Если не вдаваться глубоко в экономический анализ, то можно сказать, что это цена, при которой спрос равен предложению. А если рассуждать с точки зрения микроэкономики, то можно говорить, что модель равновесных цен позволяет, зная величины норм добавленной стоимости, прогнозировать цены на продукцию отраслей. Модель равновесных цен позволяет прогнозировать изменение цен и инфляцию, являющуюся следствием изменения цены в одной из отраслей. Найдем равновесную цену, если функция спроса на некоторый товар задается видом x = p +1 , а функция предложения видом p −1 s = p − 1 , где р – цена товара. p +1 = p − 1, Из определения равновесной цены x = p , тогда p −1 p + 1 = ( p − 1) ⋅ ( p − 1) , p + 1 = ( p − 1) , 2 p 2 − 2p + 1 = p + 1 , p 2 − 3p = 0, p(p − 3) = 0 . Откуда можно заключить, что p = 0 или p = 3 . Но так как по условию цена не может быть равной нулю, то решением будет цена, равная 3. Модель равновесных цен позволяет прогнозировать изменение цен и инфляцию, являющуюся следствием изменения цены в одной из отраслей. 28 Как вам удалось заметить, даже в рассмотренной ситуации необходимы знания элементарной математики. В других случаях этого явно недостаточно. В связи с этим рассмотрим следующий пример. Пример 2.1. Несколько семей, проживающих в поселке «Камыши» Курской области, взяли в аренду пруд и развели в нем рыбу «Карп». Объем добычи рыбы (обозначим его за y (кг/день)) зависит от количества рыбаков х на пруду так: y = 100 x . Цена 1 кг рыбы 80 руб., зарплата рыбака р = 1000 (руб./день). Кроме зарплаты, другие издержки не учитываются. Найти оптимальный размер бригады рыбаков в день. Решение. Первый способ решения — прямой. Прибыль равна выручке минус зарплата: W = 80 ⋅ 100 x − 1000 x . Находим производную и приравниваем ее нулю: 4000 W ' ( x ) = 80 ⋅ 100( x ) ' − 1000 ⋅ ( x ) ' = − 1000, x 4000 − 1000 = 0 . x Получаем уравнение x = 4 , x = 16 . Второй способ решения — использование соотношения (2.2). Имеем p 1000 50 100 F ' ( x ) = ; (100 x ) ' = ; = ; x = 16. v 80 8 x Следовательно, х = 16. Найдено оптимальное количество рыбаков, которые должны работать на пруду одновременно. Итак, для выяснения оптимального количества рыбаков в день на пруду мы использовали два подхода: 1. Чисто математический, который основан на исследовании функции на максимум, с помощью правила из раздела «Математический анализ». 2. Экономико-математический, основанный на «задаче фирмы». 29 Возникает вопрос, а как быть в тех случаях, когда фирма использует не один ресурс? Рассуждаем аналогично предыдущему: фирма выпускает один товар и его количество обозначим y . Ресурсов, как мы уже сказали, будет несколько, а значит, мы можем ввести вектор ре→ сурсов-затрат и обозначить его X = ( x 1 , x 2 ,..., x n ) . Затраты однозначно определяют выпуск, и эта связь есть производственная функция y = F( X) . Но, как и в первом случае, производственная функция должна удовлетворять экономическим условиям: 1) увеличение затрат не может привести к уменьшению выпуска; 2) должен выполняться закон убывающей отдачи или убывающей доходности. → Пусть P = ( p1 , p 2 ,..., p n ) – вектор цен на ресурсы, а v – цена единицы товара. Тогда прибыль W , являющаяся в итоге функцией X (и цен v , p1 , p 2 ,..., p n , но они считаются постоянными) есть W (X) = v ⋅ y − P ⋅ X = v ⋅ F(X) − P ⋅ X. Таким образом, мы приходим к задаче многоресурсной фирмы: W ( x ) → max , x≥0 Так как речь идет о функции многих переменных, то предстоит находить частные производные и приравнивать их нулю, т. е. ∂F v⋅ =P (2.3) ∂X Точка, определяемая соотношением (2.3), называется стационарной, и, более того, в соответствии с условием 2.2 она должна быть точкой максимума. Рассмотрим следующий пример. Пример.2.2. Оптовый склад-магазин канцелярских товаров города Белгород в своем штате имеет N продавцов-кладовщиков и M постав30 щиков товаров с предприятий. Прибыль от дня работы (выручка минус расходы, но не зарплата) выражается формулой E = 6000 ⋅ 3 M ⋅ N . Зарплата поставщиков 1 200 (руб./день), а продавца-кладовщика – 800 (руб./день). Найти оптимальный состав коллектива, т. е. количество поставщиков и продавцов-кладовщиков склада-магазина. Сделаем небольшое отступление к этой задаче, т. к. однозначно нашелся вдумчивый студент, который задает себе вопрос: «А каким образом была получена формула прибыли от дня работы?». На что ответ студенту таков. За несколько дней работы этого коллектива была получена статистическая сводка выручки от количества работающих продавцов-кладовщиков и поставщиков, ведь не ежедневно же весь коллектив был в полном составе, ктото был болен в некоторые дни, кто-то ушел в отпуск. И по результатам такой статистической сводки было построено уравнение регрессии, которое вы изучали в курсе эконометрики и экономико-математических методов и моделей. А теперь снова возвратимся к рассмотрению задачи. Т. к. речь идет о двухресурсной фирме, то в соответствии с (3), получим систему уравнений: 1  ∂W = 6000 ⋅ ( N) − 2 / 3 ⋅ M 1 / 3 = 800,  ∂N 3    ∂W 1  = 6000 ⋅ (M ) −2 / 3 ⋅ N1 / 3 = 1200. 3  ∂M Следует напомнить, что при нахождении частной производной мы берем производную от того аргумента, который задается в знаменателе левой части системы уравнений, а второй аргумент ∂W выступает в роли постоянной. Т. е. частная производная го∂N ворит нам о том, что берется производная от функции W по переменной N, а переменная М выступает в роли постоянной. 31 Приведем систему к более простому виду: 5M 1 / 3 ( N) −2 / 3 = 2,   5( M ) − 2 / 3 ⋅ N1 / 3 = 3.  Все преобразования мы делаем лишь с одной целью – найти M и N. Как вы успели заметить, неизвестных величин у нас две – M и N. Но и уравнений в системе – тоже два. Значит, если вспомнить элементарную (школьную математику), найти неизвестные можно. Посмотрев внимательно на систему, вы замечаете, что неизвестные являются степенями с конкретными показателями. А потому здесь лучше выполнить деление одного уравнения на другое, т. к. при делении степеней с одинаковыми основаниями их показатели вычитаются. Если мы будем делить первое уравнение на второе, то найдем М относительно N. Если будем делить второе уравнение на первое, то найдем N относительно М. Разделив второе уравнение системы на первое, получим: 3 N = M . Подставив найденное значение N в первое уравнение 2 3 системы, получаем, что 5M 1 / 3 ( M ) −2 / 3 = 2 . Преобразовав уравне2 125 ≈ 7 . Тогда ние с учетом свойств степеней, получим: M = 18 3 N = M ≈ 10 . 2 Получили, что для оптимальной работы склада-магазина необходимо иметь штат в количестве 10 продавцов-кладовщиков и 7 поставщиков товара. На этом примере была рассмотрена двухресурсная задача, и вы убедились, что ее решение требует достаточной математической подготовки. Надеемся, вы представляете сложность задачи, если ресурсов будет больше двух. А потому здесь потребуются другие подходы, о чем мы и будем вести речь в следующей главе. 32 Глава 2.2. Линейное программирование Изучение первой главы этого раздела указало на необходимость рассмотрения практических задач, в которых приходится сталкиваться с ситуациями, когда необходимо одновременное выполнение нескольких, зачастую противоречивых условий (критериев) для достижения наилучшего результата. Мы уже подчеркивали, что успешность решения подавляющего большинства экономических задач зависит от наилучшего, наивыгоднейшего способа использования ресурсов. В процессе экономической деятельности приходится распределять такие важные ресурсы, как деньги, товары, сырье, оборудование, рабочую силу и др. И от того, как будут распределяться эти, как правило, ограниченные ресурсы, зависит конечный результат деятельности, бизнеса. А потому еще раз подчеркнем, что суть метода оптимизации состоит в том, что, исходя из наличия определенных ресурсов, выбирается такой способ их использования (распределения), при котором обеспечивается максимум (минимум) интересующего нас показателя. При этом учитываются определенные ограничения, налагаемые на использование ресурсов условиями экономической ситуации. В качестве методов оптимизации, используемых в экономике, рассмотрим линейное программирование, которое иногда называют линейным планированием. Линейное программирование – математический метод отыскания максимума или минимума линейной функции при наличии ограничений в виде линейных неравенств или уравнений. (Линейное здесь означает, что на графике функции изображаются в виде прямых линий.) В практической работе №6 курса «Экономико-математические методы и модели» отмечалось, что построение математической модели экономической задачи включает следующие этапы: 1) выбор переменных задачи; 2) составление системы ограничений; 3) выбор целевой функции. 33 Вводились важные понятия, о которых мы еще раз напомним. Переменными задачи мы называли величины ( x 1 , x 2 ,..., x n ) , которые полностью характеризуют экономический процесс. Отмечалось, что система ограничений включает систему уравнений и неравенств, которым удовлетворяют переменные задачи и которые следуют из ограниченности ресурсов или других экономических или физических условий, например положительности переменных и т. п. Максимизируемая (минимизируемая) функция представляет собой принятый критерий эффективности решения задачи, соответствующей поставленной цели. А потому она носит название целевой функции. Целевой функцией мы называли функцию переменных задачи, которая характеризует качество выполнения задачи и экстремум которой требуется найти. Ограничения характеризуют имеющиеся возможности решения задачи. Решение, удовлетворяющее условиям задачи и соответствующее намеченной цели, называют оптимальным планом. В общем виде задача линейного программирования может выглядеть так: найти экстремум целевой функции F(X) = f ( x1 , x 2 ,..., x n ) → max(min) (2.4) и соответствующие ему переменные при условии, что эти переменные удовлетворяют системе ограничений i = 1,2,..., l, ϕ i ( x 1 , x 2 ,..., x n ) = 0, (2.5)  ϕ i ( x 1 , x 2 ,..., x n ) ≤ (≥ )0, i = l + 1, l + 2,..., m. Совокупность соотношений, содержащих целевую функцию и ограничения на ее аргументы, называется математической моделью экономической задачи оптимизации. Если речь в задаче идет о двух неизвестных, то можно воспользоваться графическим методом. В связи с этим рассмотрим следующий пример. 34 Пример 2.3. При комбинате крупно-панельного домостроения в г. Курске существует цех по выпуску двух видов плит: древесно–стружечных – обычных и улучшенных. При этом производятся две основные операции – прессование и отделка. Требуется указать, какое количество плит каждого типа можно изготовить в течение месяца так, чтобы обеспечить максимальную прибыль при следующих ограничениях на ресурсы (материал, время, затраты), таблица 2.1: Таблица 2.1 Затраты Материал (кг) Время на прессование (часы) Время на отделку (часы) Средства (доллары) Партия из 100 плит обычных улучшенных 8 16 Имеющиеся ресурсы на месяц 1600 4 6 900 4 4 600 30 50 6000 если за каждые 100 обычных плит фирма получает прибыль, равную 80 долларам, а за каждые 100 плит улучшенного вида – 100 долларов. Перейдем к построению математической модели поставленной задачи. Введем следующие обозначения. Пусть х – количество партий в 100 плит обычного вида, изготавливаемых в течение месяца, а у – то же для плит улучшенного качества. Тогда ожидаемую прибыль можно записать так: F = 80x + 100 y → max . Для изготовления х партий в 100 плит обычного вида и у партий в 100 плит улучшенного вида требуется 8х + 16у кг дерева. Ясно, что полученное число не может превосходить количество материала, имеющегося в наличии, т. е. 1600 кг Тем самым ограничения на материалы имеют вид: 8x + 16 y ≤ 1600 . 35 Подобным же образом рассчитываются ограничения на время изготовления и затраты: прессование: 4x + 6 y ≤ 900, отделка: 4x + 4 y ≤ 600, затраты: 30x + 50 y ≤ 6000. Подведем итог: требуется найти такие значения х и у, подчиненные условиям 8x + 16 y ≤ 1600, 4x + 6 y ≤ 900,  4x + 4 y ≤ 600,  30 x + 50 y ≤ 6000, x ≥ 0,   y ≥ 0, для которых F = 80x + 100 y → max Т. к. по условию системы ( x ≥ 0 и y ≥ 0 ) решение будет находиться в первой четверти, построим прямые по точкам их пересечения с осями координат. 8x + 16 y = 1600; A( 200;0); B(0;100) (2.6) 4x + 6 y = 900; C(225;0); D(0;150) (2.7) 4x + 4 y = 600; E(150;0); F(0;150), (2.8) 30x + 50 y = 6000; G (200;0); H(0;120) (2.9) С учетом масштаба построения (1см:10) предлагаем вам построить эти прямые самостоятельно. У вас должна получиться картинка, как на рисунке 2.1. 36 Y D F H B М E G A С X Рисунок 2.1 Пересечением полученных прямых будет четырехугольник ОВМЕ. Т. к. мы решаем задачу линейного программирования, то отметим важный теоретический факт: линейная функция достигает наибольшего (наименьшего) значения в одной из вершин получившегося многоугольника. Иногда, рассматривая оптимизационную задачу, предлагается ответить на вопрос задачи, в которой уже известны вершины многоугольника (многогранника) и известна целевая функция. И для ответа на вопрос задачи необходимо подставить координаты вершин этого многоугольника (многогранника) в целевую функцию и вычислить ее значение. Далее выбрать из получившихся значений наибольшее, если требуется максимизировать целевую функцию, или наименьшее, если необходимо минимизировать функцию. Теперь снова вернемся к рассматриваемой задаче. 37 В нашем случае речь идет о четырехугольнике ОВМЕ, где точка О – начало координат и ее вершины (0;0). Поэтому для ответа на поставленный вопрос необходимо найти координаты точки пересечения прямых (2.6) и (2.8) – точки М (координаты вершин В и Е известны). А это означает необходимость решения системы двух уравнений для прямых (2.6) и (2.8). Значит, необходимо решить систему: 8x + 16 y = 1600,  4x + 4 y = 600. Первое уравнение разделим на 8, а второе уравнение разделим на 4. В итоге получим систему в виде: x + 2 y = 200,  x + y = 150. Эту систему можно решить методом подстановки, но проще решить ее методом сложения. Для этого второе уравнение системы умножим на (-1) и прибавим получившийся результат к первому уравнению. Окончательно получаем у = 50. А для нахождения значения «х» подставим во второе уравнение системы значение у = 50. Тогда получим х = 100. Итак, мы определили координаты точки М, т. е. M (100;50) . Конечно, если вы строили графики функций с учетом соблюдения масштаба, то координаты точки М можно было найти проще – опустив перпендикуляры из точки М на оси координат, они должны совпасть с теми координатами, которые мы получили расчетным путем. Координаты точек В и Е нами уже определены, мы их использовали для построения прямых: В(0; 100), Е(150; 0), а координаты точки М мы только что определили. Далее вычисляем значения целевой функции F = 80x + 100 y в точках В(0; 100), Е(150; 0), М (100; 50). Это означает, что необходимо подставить координаты каждой из трех точек в целевую функцию. Предлагаем вам это сделать самостоятельно. А мы уже подсчитали значения целевой функции в этих вершинах, и вот что получили: FB = 10000, FE = 12000, FM = 13000 . 38 Т. к. необходимо исследовать целевую функцию на max, то, выбрав из полученных значений наибольшее, т. е. Fmax = 13000 , отмечаем координаты точки, давшей наибольший результат, как искомое решение задачи. Итак, получили, что х = 100, у = 50, Fmax = 13000 долл. Значит, в партии возможно 100 плит обычного вида, 50 плит улучшенного качества, при этом максимальная прибыль достигнет 13 000 долл. Компьютерный способ решения оптимизационных задач мы рассмотрим в компьютерном практикуме к этому курсу. Далее рассмотрим еще один из методов решения оптимизационных задач – симплексный метод. Глава 2.3. Основная идея симплекс-метода В 1947 году американский математик Джон Данциг опубликовал исследование по решению задач линейного программирования, которое было названо симплекс-методом. Позднее этот метод в нашей стране еще называли методом последовательного улучшения плана. Вы уже познакомились с геометрическим методом решения задач линейного программирования, когда на плоскости (пространстве) строится многоугольник (многогранник) с конечным числом вершин, т. е. его крайних точек. Многоугольник (многогранник) представляет собой допустимое множество задачи. В том случае, если задача линейного программирования имеет единственное решение, решение находится в одной из этих вершин. Симплекс-метод состоит в таком направленном переборе вершин, при котором значение целевой функции улучшается (не ухудшается) при переходе от вершины к вершине. Каждая вершина многоугольника (многогранника) является пересечением прямых (плоскостей), каждая из которых задается уравнением, определенным соответствующим ограничением исходной задачи линейного программирования. Другими словами, каждая вершина определяется системой уравнений, выбираемой 39 специальным образом из системы неравенств конкретной задачи. Вспомните, когда, рассматривая задачу о выпуске плит, мы от системы неравенств переходили к системе уравнений. Проще говоря, симплекс-метод представляет собой вычислительную процедуру последовательного решения систем линейных уравнений. Поэтому этот метод содержит в себе правила формирования систем уравнений (правило выбора разрешающего элемента) и схему решения систем линейных уравнений (об этом вы узнали из раздела «Линейная алгебра» курса математики). Такой способ решения достаточно трудоемкий. А потому в рамках этого курса мы рассмотрим другой способ – табличный симплексметод. Он проще реализуется на практике. Табличный симплекс-метод назван так потому, что исходные данные записываются в специальные симплекс-таблицы. И сейчас мы рассмотрим алгоритм решения задач линейного программирования табличным симплекс-методом. Если вернуться к формулам 2.4 и 2.5, то для табличного симплекс метода задача линейного программирования в каноническом виде запишется так, что целевая функция исследуется на максимум: F=a0,1x1+a0,2x2+...a0,nxn +b0 max a1,1x1+a1,2x2+...a1,nxn + xn+1=b1 (2.10) a2,1x1+a2,2x2+...a2,nxn +xn+2 =b2 ....................................... am,1x1+am,2x2+...am,nxn+xn+m=bm Обращаем ваше внимание, что мы говорим о канонической форме записи целевой функции и в ней эта функция исследуется на максимум. Но ведь реально же встречаются различные ситуации, когда, наоборот, необходимо минимизировать функцию, тогда по свойствам неравенств можно умножить обе части этого неравенства на отрицательное число, и знак неравенства изменится на противоположный. Но об этом мы еще поговорим более подробно чуть ниже. Затем составляют исходную таблицу в виде таблицы 2.2. 40 Таблица 2.2 F xn+1 xn+2 ... xn+m x1 x2 ... xn-1 xn Свободные члены -a0,1 a1,1 a2,1 ... am,1 -a0,2 a1,2 a2,2 ... am,2 ... ... ... ... ... -a0,n-1 a1,n-1 a2,n-1 ... am,n-1 -a0,n a1,n a2,n ... am,n -b0 b1 b2 ... bm Прокомментируем таблицу. В этой таблице x1 , x 2 , …, x n – исходные переменные, они записываются в первую строку. Вводят дополнительные переменные x n +1 , x n + 2 , …, x n + m . Эти переменные называют базисными и записывают в первый столбец. При каждой итерации (пересчете) элементы симплекс-таблицы пересчитывают по определенным правилам. Столбец свободных членов условно назвали элементами «b» с различными нижними индексами, которые указывают на номер уравнения, содержащего конкретный свободный член. В случае, если в исходной задаче необходимо найти минимум, знаки коэффициентов целевой функции F меняются на противоположные ( a 0, n = −a 0, n ) . Что и отмечено в строке «F». Далее в таблицу вносятся коэффициенты при неизвестных. При этом знаки коэффициентов ограничивающих условий со знаком «≥», так же меняются на противоположные. В случае, если условие содержит знак «≤», коэффициенты запишутся без изменений. Итак, подготовительный этап завершен. Далее осуществляют проверку на допустимость, назовем ее шаг 1. Что это означает? Шаг 1. Проверяют на положительность элементы столбца свободных членов (b), если среди них нет отрицательных, то найдено допустимое решение (решение соответствующее одной из вершин многогранника условий), и мы переходим к шагу 2. Если же в столбце свободных членов имеются отрицательные элементы, то выбираем среди них максимальный по модулю – он задает разрешающую строку k. В этой строке также находим 41 максимальный по модулю отрицательный элемент, например a k ,s – он задает разрешающий столбец – тогда он будет первый, и этот элемент является разрешающим элементом. Переменная, соответствующая разрешающей строке, исключается из базиса, переменная, соответствующая разрешающему столбцу, включается в базис. Пересчитываем симплекс-таблицу согласно правилам, о которых скажем чуть ниже. Если же среди свободных членов есть отрицательные элементы, а в соответствующей строке – нет, то условия задачи несовместны и решений у нее нет (Об этом следует помнить). Если после перерасчета в столбце свободных членов остались отрицательные элементы, то переходим к первому шагу, если таких нет, то ко второму. Правила преобразований симплексной таблицы При составлении новой симплекс-таблицы в ней происходят следующие изменения. Вместо базисной переменной x k записываем x s , а вместо небазисной переменной x s записываем x k ; разрешающий элемент заменяется на обратную величину a k ,s = 1 a k ,s ; все элементы разрешающего столбца (кроме a k ,s ) умножа−1 ются на a ; k ,s все элементы разрешающей строки (кроме a k ,s ) умножаются 1 на a ; k ,s оставшиеся элементы симплекс-таблицы преобразуются по формуле a 'i , j = a i , j − a i , s ⋅ a k, j a k ,s . (2.11) Схему преобразования элементов симплекс-таблицы (кроме разрешающей строки и разрешающего столбца) называют схемой «прямоугольника», рисунок 2.2. 42 a ij a is ' a kj a ks Рисунок 2.2 Преобразуемый элемент a i, j и соответствующие ему три сомножителя как раз и являются вершинами «прямоугольника». Шаг 2. Этот шаг называют проверкой на оптимальность. В чем это выражается? Первым шагом найдено допустимое решение. Проверяют его на оптимальность. Если среди элементов симплексной таблицы, находящихся в строке «F» (не беря в расчет элемент b 0 – текущее значение целевой функции), нет отрицательных, то найдено оптимальное решение. Если в строке «F» есть отрицательные элементы, то решение требует улучшения. Выбираем среди отрицательных элементов строки «F» максимальный по модулю (исключая значение функции b0 ). a 0,s = min{a 0,i } (2.12) S-ый столбец, в котором находится максимальный по модулю отрицательный элемент, будет разрешающим. Для того чтобы найти разрешающую строку, находят отношение соответствующего свободного члена и элемента из разрешающего столбца, при условии, что они неотрицательны. b  bk = min  i  a k ,s  a i,s  43 a i,s > 0 , bi > 0 (2.13) Поясняем формулу: k – номер cтроки, для которой это отношение минимально. Эту строку называют разрешающей. Элемент a k ,s – разрешающий. Переменная, соответствующая разрешающей строке (xk), исключается из базиса, переменная, соответствующая разрешающему столбцу ( x s ), включается в базис. Пересчитываем симплекс-таблицу по формулам 2.11. Если в новой таблице после перерасчета в строке «F» остались отрицательные элементы, переходим к шагу 2 Если невозможно найти разрешающую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений задачи не ограничена – алгоритм завершает работу. Если в строке «F» и в столбце свободных членов все элементы положительные, то найдено оптимальное решение. В качестве примера решения задачи методом симплексных таблиц рассмотрим следующую. Целевая функция F = 2x1 + 5x 2 + 3x 3 + 8x 4 → min , ограничивающие условия задаются системой неравенств: 3x1 + 6 x 2 − 4 x 3 + x 4 ≤ 12,  4 x1 − 13x 2 + 10 x 3 + 5x 4 ≥ 6, 3x + 7 x + x ≥ 1. 2 3  1 Все рассуждения будем выполнять в соответствии с рассмотренным алгоритмом. А для этого приведем систему ограничений к каноническому виду, т. е. необходимо перейти от неравенств к равенствам, с добавлением дополнительных переменных. Так как наша задача – задача минимизации, то нам необходимо преобразовать ее к задаче на поиск максимума. Для этого изменим знаки коэффициентов целевой функции на противоположные. Элементы первого неравенства записываем без изменений, добавив в него дополнительную переменную x 5 и изменив знак «≤» на «=». Т. к. второе и третье неравенства имеют знаки «≥», необходимо поменять знаки их коэффициентов на противо44 положные и внести в них дополнительные переменные x 6 и x 7 соответственно. В результате получим эквивалентную задачу: 3x1 + 6x 2 − 4 x 3 + x 4 + x 5 = 12,  − 4 x1 + 13x 2 − 10x 3 − 5x 4 + x 6 = −6, − 3x − 7 x − x + x = −1. 1 2 3 7  Если вы внимательно прочитали теоретический момент алгоритма, то вам понятен принцип, по которому мы сформировали новую систему. Ну а если это не совсем понятно, то еще раз скажем, что в начальной системе ограничений первое и второе неравенства содержат по четыре неизвестных х1, х2, х3, х4 , а третье неравенство содержит три неизвестные х1, х2, х3, поэтому вводят дополнительные переменные. Нумеруя их соответственно х 5, х6, х7 и записывая по порядку в первое, второе и третье неравенства. Далее переходим к формированию исходной симплекс-таблицы на основе таблицы 2.2. В строку «F» таблицы заносятся коэффициенты целевой функции с противоположным знаком, т. к. речь идет о минимизации функции. Столбец свободных членов и строки таблицы заполняете, исходя из коэффициентов системы. Назовем эту таблицу 2.3. Таблица 2.3 x1 x2 x3 x4 F x5 -2 3 -5 6 -3 -4 -8 1 Свободные члены 12 x6 -4 13 -10 -5 -6 x7 -3 -7 -1 -1 Далее в соответствии с алгоритмом анализируем столбец «свободные члены» на отрицательность и находим среди его отрицательных значений (это будут -6 и -1) максимальный элемент по модулю. Этим значением будет число -6. Этот элемент определил нам разрешающую строку, она будет x 6 . В этой строке также находим максимальный по модулю отрицательный элемент: -10. Этот элемент находится в столбце x 3 , который будет разрешающим столбцом. На пересечении разрешающей строки и разреша45 ющего столбца получаем разрешающий элемент. Переменная в разрешающей строке исключается из базиса, а переменная, соответствующая разрешающему столбцу, включается в базис (проще говоря, столбец и строка как бы меняются местами). Значит, в новой симплекс-таблице вместо столбца с номером х 3 будет столбец с номером х6, а вместо сроки с номером х6 будет строка с номером х3. Для очередной итерации – пересчета новой симплекс-таблицы – разрешающий элемент (-10) (он выделен заливкой в таблице 2.2) заменяется на обратную величину, т. е. на (-0,1). Далее все элементы разрешающего столбца (х6) (кроме элемента (-0,1)) −1 в новой таблице будут умножаться на число a , т. е. в нашем k ,s случае – на число 0,1. В результате этих преобразований получим, что по столбцу х6 в новой симплексной таблице будут стоять числа: 0,3; -0,4; -0,1; -0,1. Пересчитаем все элементы разрешающей строки, для этого в соответствии с правилами преобразования симплекс-таблицы все элементы разрешающей строки (кроме числа (-0,1)) умножаем 1 на число a , т. е. в нашем случае – на число (- 0,1). Тогда по k ,s строке х3 будут стоять следующие числа:0,4; -1,3; -0,1; 0,5; 0,6. Так как в правилах преобразований симплекс-таблиц сказано, что оставшиеся элементы симплекс-таблицы преобразуются по формуле (2.11), то рассмотрим эту формулу более подробно. Возможно, что кому-то не совсем понятны формула 2.11 и схема «прямоугольника», представленная на рисунке 2.12, а потому поясним, как вычисляются элементы новой симплекс-таблицы на элементарной схеме. Пусть, например, разрешающий элемент d и пересчитываемый элемент «а» находятся в таблице в вершинах прямоугольника, см. рисунок 2.3. При этом элемент «в» – это элемент разрешающего столбца, находящийся на той же строке, что и искомый элемент «а». Элемент «с» – это тот элемент, который находится в разрешающей строке и в том же столбце, что и искомый элемент «а». Элемент «d» – это разрешающий элемент. 46 В нашем случае он был равен (-10). Тогда искомый элемент «а» будет вычисляться по формуле 2.11, которую мы «привяжем» к нашим условным обозначениям элементов, и назовем эту формулу 2.11*. Она задается видом: " а" =" а"− " в"⋅" с" " d" (2.11*) a в c d Рисунок 2.3 Возвращаясь к нашему примеру, рассмотрим, как будут выглядеть элементы новой симплекс-таблицы (кроме разрешающего столбца и разрешающей строки, т. к. мы их уже вычислили). Начнем со строки «F». Напомним, что в нашем случае функция минимизируется, а потому все получающиеся в результате вычислений значения мы будем менять по знаку, т. к. необходимо преобразовать ее к задаче на поиск максимума. Получаем: = −2 − (−3) ⋅ (−4) = −0,8; (−10) = −5 − 13 ⋅ (−3) = −8,9; (−10) = −8 − ( −3) ⋅ ( −5) = −6,5; (−10) =0− (−3) ⋅ (−6) = 1,8. (−10) Не забыв изменить знаки получившихся значений на противоположные, запишем элементы строки «F». В итоге получим:0,8; 8,9; 6,5; -1,8. По формуле 2.11, или по 2.11* найдем элементы строки х 5, в результате получим: 47 = 3− (−4) ⋅ (−4) = 4,6; (−10) =6− (−4) ⋅ (13) = 0,4; ( −10) =1− (−4) ⋅ (−5) = 3; (−10) (−4) ⋅ (−6) = 14,4. ( −10) = 12 − Тогда получаем, что по строке х5 пойдут такие значения: 4,6; 0,8; 3; 14,4. Так как элементы разрешающей строки нами уже определены, то перейдем к вычислению элементов строки х7. Вычисления будут выглядеть так: = −3 − (−4) ⋅ (−1) = −2,6; ( −10) = −7 − 13 ⋅ (−1) = −8,3; (−10) =0− (−5) ⋅ (−1) = 0,5; (−10) = −1 − (−6) ⋅ (−1) = −0,4. (−10) Итак, значения элементов строки х7 будут иметь вид: -2,6; -8,3; 0,5; -0,4. Далее составим пересчитанную симплекс-таблицу, которая будет уже иметь вид, отличный от таблицы 2.3, а потому назовем эту таблицу уже номером 2.4. Таблица 2.4 F х5 х3 х7 х1 х2 0,8 4,6 0,4 -2,6 8,9 0,8 -1,3 -8,3 х6 х4 0,3 -0,4 -0,1 -0,1 48 6,5 3 0,5 0,5 Свободные члены -1,8 14,4 0,6 -0,4 И снова выполняем анализ значений в столбце свободных членов этой преобразованной симплекс-таблицы (не рассматривая значение этого столбца по строке F). Оказалось, что среди значений новой таблицы имеется отрицательный элемент в столбце свободных членов, – это элемент (-0,4), он задает разрешающую строку х7. В этой строке также находим максимальный по модулю отрицательный элемент (-8,3), он находится в столбце х 2, который будет разрешающим столбцом. Разрешающий элемент найден, он равен (-8,3), и мы снова его выделяем заливкой. Переменная в разрешающей строке исключается из базиса, а переменная, соответствующая разрешающему столбцу, включается в базис. Для пересчета симплекс-таблицы снова применяем правила преобразований симплекс-таблицы. Разрешающий элемент (-8,3) заменяется на обратную величину, т. е. на 1 = −0,12 . Обращаем внимание, что здесь выпол− 8,3 нено округление до сотых долей. Далее все элементы разрешающего столбца (х7) новой та−1 блицы (кроме элемента (-0,12)) будут умножаться на число a . В k ,1 нашем случае – на число, противоположное числу (-0,12), т. е. на число 0,12. В результате этих преобразований получим, что по столбцу х7 в новой симплексной таблице будут стоять числа: 1,072; 0,096; -0,156; -0,12. Напоминаем, что последнее число мы не меняем, т. к. оно содержится в разрешающей строке. Давайте посмотрим, как мы их получили: = 8,9 ⋅ 0,12 = 1,072; = 8 ⋅ 0,12 = 0,096; = −1,3 ⋅ 0,12 = −0,156. Пересчитаем все элементы разрешающей строки х 2 в новой симплекс-таблице. Для этого в соответствии с правилами преобразования симплекс-таблицы все элементы разрешающей строки 1 (кроме числа (-0,12)) умножаем на число a , т. е. в нашем случае – k ,1 49 на число (- 0,12). Тогда по строке х2 будут стоять следующие числа: 0,312; -0,12; 0,012; -0,06; 0,048. И снова покажем, как получены эти значения элементов разрешающей строки. = (−2,6) ⋅ (−0,12) = 0,312; = (−0,1) ⋅ (−0,12) = 0,012; = (0,5) ⋅ (−0,12) = −0,06; = (−0,4) ⋅ (−0,12) = 0,048. Как мы уже и выполняли ранее при пересчете симплекс-таблицы, все остальные элементы симплекс-таблицы будем заполнять, руководствуясь формулой 2.11 или 2.11*. Начнем снова со строки «F» симплекс-таблицы. В итоге будем получать значения: 8,9 ⋅ (−2,6) ≈ −1,988; (−8,3) 8,9 ⋅ (−0,1) = 0,3 − ≈ 0,193; (−8,3) 8,9 ⋅ 0,5 = 6,5 − ≈ 7,036; (−8,3) 8,9 ⋅ (−0,4) = −1,8 − ≈ −2,229. (−8,3) = 0,8 − Вы обратили внимание, что в вычислениях стоит знак приближенного равенства, т. к. мы производим округление до разряда тысячных долей. Итак, в новой симплекс-таблице по строке «F» будут стоять значения: -1,988; 1,072; 0,193; 7,036; -2,229. Аналогично произведем пересчет симплекс-таблицы по строке х5 и в результате получим: 0,8 ⋅ (−2,6) ≈ 4,349; (−8,3) 0,8 ⋅ (−0,1) = −0,4 − ≈ −0,41; (−8,3) 0,8 ⋅ 0,5 = 3− ≈ 3,048; (−8,3) 0,8 ⋅ (−0,4) = 14,4 − ≈ 14,361. (−8,3) = 4,6 − 50 Значит, в новой симплекс-таблице по строке х 5 будут стоять значения: 4,349; 0,096; -0,41; 3,048; 14,361. Для формирования новой симплекс-таблицы нам осталось пересчитать строку х3 , что мы сейчас и сделаем. = 0,4 − (−1,3) ⋅ (−2,6) ≈ 0,807; (−8,3) = −0,1 − (−1,3) ⋅ (−0,1) ≈ −0,084; (−8,3) = 0,5 − (−1,3) ⋅ 0,5 ≈ 0,422; (−8,3) = 0,6 − (−1,3) ⋅ (−0,4) ≈ 0,663. (−8,3) Теперь можем записать все значения элементов строки х3: 0,807; -0,156; -0,084; 0,422; 0,663. Ну и наконец мы формируем новую симплекс-таблицу, назвав ее таблицей 2.5. Таблица 2.5 F х5 х3 х2 х1 х7 х6 х4 -1,988 4,349 0,807 0,313 1,072 0,096 -0,156 -0,12 0,193 -0,41 -0,084 0,012 7,036 3,048 0,422 -0,06 Свободные члены -2,229 14,361 0,663 0,048 Снова выполняем анализ значений, стоящих в столбце свободных членов. Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Но в строке «F» имеются отрицательные элементы, это означает что полученное решение не оптимально. Определим разрешающий столбец. Для этого найдем в соответствии с формулой 2.12 в строке «F» максимальный по модулю отрицательный элемент или минимальный элемент – это будет число – 1,988. Значит, столбец х1 будет разрешающим. В соответствии с теоретическими выводами симплекс-метода (формула 2.13) разрешающей строкой будет та, для которой отношение свободного члена к соответствующему элементу разрешающего столбца минимально. 51 Найдем эти отношения: = 14,361 0,663 0,048 ≈ 149,53 ; = ≈ 0,822; = ≈ 0,153 . 0,096 0,807 0,313 Из полученных отношений, выбрав минимальное, замечаем, что разрешающей строкой является х2, а разрешающий элемент: 0,313. Переменная в разрешающей строке х2 исключается из базиса, а переменная, соответствующая разрешающему столбцу х1, включается в базис. Для пересчета симплекс-таблицы разрешающий элемент 0,313 (он выделен заливкой в таблице 2.5) заменяется на обратную величину, т. е. на ( 1 = 3,195 ). Далее все элемен0,313 ты разрешающего столбца (х2) (кроме элемента (3,195)) в новой таблице будут умножаться на число, ему противоположное, т. е. на число (-3,195). В результате этих преобразований получим, что по столбцу х2 в новой симплексной таблице будут стоять числа: 6,351; -13,895; - 2,578. Еще раз покажем, как получены эти значения: = (−3,195) ⋅ (−1,988) ≈ 6,351; = (−3,195) ⋅ 4,349 ≈ −13,895; = (−3,195) ⋅ 0,807 ≈ −2,578. Пересчитаем все элементы разрешающей строки х 1 в новой симплекс-таблице. Для этого в соответствии с правилами преобразования симплекс-таблицы все элементы разрешающей строки 1 (кроме числа (0,313)) умножаем на число a , т. е. в нашем слуk ,1 чае – на число (3,195). Тогда по строке х 1 будут стоять следующие числа: 3,195; -0,383; 0,038; -0,192; 0,153. И снова покажем, как получены эти значения элементов разрешающей строки х1. = 3,195 ⋅ (−0,12) ≈ −0,383; = 3,195 ⋅ 0,012 ≈ 0,038; = 3,195 ⋅ (−0,06) ≈ −0,192; = 3,195 ⋅ 0,048 ≈ 0,153. 52 Остальные элементы новой симплекс-таблицы пересчитываем снова по формуле 2.11*. Покажем пересчет значений по строке «F». = 1,072 − (−1,988) ⋅ (−0,12) ≈ 0,31; 0,313 = 0,193 − (−1,988) ⋅ 0,012 ≈ 0,269; 0,313 = 7,036 − (−1,988) ⋅ (−0,06) ≈ 6,655; 0,313 = −2,229 − (−1,988) ⋅ 0,048 ≈ −1,924. 0,313 Далее пересчитаем по формуле 2.11* значения новой симплекс-таблицы по строке х5 В результате будем получать: = 0,096 − 4,349 ⋅ (−0,12) ≈ 1,763; 0,313 = −0,41 − 4,349 ⋅ 0,012 ≈ −0,577; 0,313 = 3,048 − 4,349 ⋅ (−0,06) ≈ 3,882; 0,313 = 14,361 − 4,349 ⋅ 0,048 ≈ 13,694. 0,313 И теперь приступаем к пересчету значений последней строки х3 , т. к. значения по строке х1 – разрешающей строке – мы уже пересчитали ранее. Значения по строке х3 будут получаться в виде: = −0,156 − 0,807 ⋅ (−0,12) ≈ 0,153; 0,313 = −0,084 − 0,807 ⋅ 0,012 ≈ −0,115; 0,313 = 0,422 − 0,807 ⋅ (−0,06) ≈ −0,577; 0,313 = 0,663 − 0,807 ⋅ 0,048 ≈ 0,539. 0,313 Занесем все полученные значения в новую симплекс-таблицу 2.6. 53 Таблица 2.6 F х5 х3 х1 х2 х7 х6 х4 6,351 -13,895 -2,578 3,195 0,31 1,763 0,152 -0,383 0,269 -0,577 -0,115 0,038 6,655 3,882 0,577 -0,192 Свободные члены -1,924 13,694 0,539 0,153 И снова выполняем анализ строки «F» на наличие отрицательных элементов. Так как в этой строке нет отрицательных элементов, то найдено оптимальное решение. Так как исходной задачей был поиск минимума, то оптимальным решением будет свободный член строки F, взятый с противоположным знаком. Таким образом, F=1,924 при значениях переменных равных: x 3=0,539, x1=0,153. Переменные x2 и x4 не входят в базис, поэтому x2=0 x4=0. Такой поиск оптимального решения конкретной задачи требует усилий и времени со стороны того, кто эту задачу решает. Но согласитесь, что это стоит того, если на чашу весов ставится ваш бизнес, судьба сотрудников вашей компании. Как мы уже и говорили ранее, решение задач на оптимизацию можно выполнять и другим способом, а точнее, компьютерным методом с помощью надстройки «Поиск решения», что мы снова сделаем, но уже в компьютерном практикуме. Далее мы рассмотрим еще один тип задач линейного программирования. 54 Глава 2.4. Транспортные задачи В экономике важным этапом являются перевозки товаров и различных грузов от поставщиков к потребителям. И естественно, для потребителя важно как можно меньше заплатить за доставку товара поставщиком. Как правило, такие задачи (их называют транспортными) сводятся к минимизации полной стоимости перевозок. Следует отметить, что, говоря о транспортных задачах, вводят понятие сбалансированной (закрытой) транспортной задачи. Это такая задача о перевозках, в которой общий объем товаров, готовых к отправлению, равен объему товаров, который готовы принять в пунктах назначения. Например, определить значения a и b , при которых транспортная задача, заданная таблицей 2.7, будет закрытой. Таблица 2.7 20 b 25 11 5 а 3 7 В соответствии с определением, данным выше, это означает, что общий объем товаров, готовых к отправлению, равен объему товаров, который готовы принять в пунктах назначения. Иными словами, если сумма элементов по первой строке равна сумме элементов по первому столбцу, т. е. 25 + a = 20 + b . Откуда b = a + 5 . А это означает, что если, например, a = 10 , то задача будет закрытой при b = a + 5 = 10 + 5 = 15 . Итак, можно утверждать, что заданная таблицей 2.7 транспортная задача будет закрытой (сбалансированной), например, при a = 10 и b = 15 . Эту ситуацию мы рассмотрели для того, чтобы вам было понятно определение закрытой транспортной задачи. А сейчас мы рассмотрим решение транспортной задачи с точки зрения оптимизации перевозок. 55 Например, известная компания «Мебель Черноземья» в Курском регионе имеет два товарных склада в Сеймском округе и трех оптовых покупателей: торговые центры «Невский», «Панорама», «Европа». Как показали маркетинговые исследования, на конкретный момент общий объем запасов на складах составляет 300 тыс. единиц продукции и совпадает с общим объемом заказов покупателей. Все данные о загруженности каждого из складов (в тыс. единиц), потребности каждого оптового покупателя (в тыс. единиц) и стоимость перевозки (десятки тыс. руб. за 1 тыс. единиц) приведены в таблице 2.8. Таблица 2.8 Склады А1 А2 Запрос (тыс. ед.) Стоимость перевозок потребителям (десятки тыс. руб. за 1 тыс. единиц) В1 В2 В3 8 5 6 4 9 7 70 140 90 Наличие (тыс. единиц) 120 180 300 Для решения этой оптимизационной задачи необходимы рассуждения такого плана: пусть хik – количество товара, поставляемого со склада Аi оптовому покупателю Вk, тогда составим функцию стоимости перевозок, которую необходимо минимизировать. Обозначим эту функцию через f, и в соответствии с таблицей 2.8 функция будет иметь вид: f = 8x11 + 5x12 + 6x13 + 4 x 21 + 9x 22 + 7 x 23 → min . Но важнейшим фактором оптимизационных задач является наличие условий, ограничивающих значения. Разберемся с этим в нашем случае. В соответствии с обозначениями, принятыми в этой задаче, получим: 56 x11 + x12 + x13 = 120, x 21 + x 22 + x 23 = 180, x11 + x 21 = 70, x12 + x 22 = 140, x13 + x 23 = 90. Еще важно отметить, что все введенные переменные должны быть неотрицательными, исходя из условия задачи. А потому добавляются еще ограничения: x11 ≥ 0 , x12 ≥ 0 , x13 ≥ 0 , x 21 ≥ 0 , x 22 ≥ 0 , x 23 ≥ 0 . Кроме прочего, отметим, что задача является сбалансированной, т. к. сумма значений по строке «Запрос» равна 300 и сумма значений по столбцу «Наличие» также равна 300. Мы предлагаем вам выполнить решение этой задачи методом симплекс-таблиц самостоятельно и покажем вам компьютерный вариант ее решения в компьютерном практикуме. В качестве рекомендаций следует отметить следующее: в рассматриваемой задаче 6 неизвестных: x11 , x12 , x13 , x 21 , x 22 , x 23 ., чтобы не путаться с двузначными нижними индексами, лучше их переобозначить вот так: x1 , x 2 ,…, x 6 . А далее заполняете симплекс таблицу с учетом переобозначений и выполняете последовательно все итерации. Правильность своих рассуждений сверите с ответом, который мы получим в компьютерном практикуме при реализации этой задачи с помощью надстройки «Поиск решения». Не забудьте снова возвратиться к переменным с учетом переобозначений. 57 Глава 2.5. Об удивительных оптимальных решениях Итак, снова возвращаясь к мысли, что в современной экономике математика выступает в качестве необходимого инструмента, с помощью которого можно найти, выбрать наилучший вариант действий из многих возможных, рассмотрим несколько интересных на наш взгляд фактов. Вот уже более 15 лет ежегодно проводится Московский международный Салон изобретений и инновационных технологий «Архимед». Удивительное оптимальное решение, представленное на этом Салоне в 2012 г., продемонстрировала 16-летняя Лиза Бунькова из города Ирбит, что в Свердловской области (об этом было сообщение и по центральным каналам Российского телевидения и в прессе). Вместе с учителем по труду она представляла свое изобретение — комплект снаряжения туриста. В этом комплекте все складное. Комбинезон трансформируется в футболку и шорты. Брюки преобразовываются в накладной карман-«портфель». Спальник превращается в накидку, гамак или небольшую палатку. Идея пришла во время похода. Холодной ночью, когда так не хотелось вылезать из теплого спального мешка, она подумала, как было бы здорово налить чай или разжечь костер, не покидая спального места. Юная путешественница на пару с педагогом сделала выкройки, за 4 дня сшила образец. Главная идея понятна — все необходимые в походе вещи должны быть универсальными и легкими. Таким оптимальным было решение задачи в конкретной ситуации. Но естественно, что для дальнейшего продвижения этой идеи нужна помощь со стороны бизнеса, взрослых. Принятие наиболее оптимальных решений требуется, как правило, в случаях недостатка каких-либо ресурсов, средств. Но людям, обладающим, казалось бы, в этой жизни всем, также приходится принимать оптимальные решения, и гораздо чаще, чем нам может показаться. В своей удивительной книге «Секс, деньги, счастье и смерть» Манфред Кетс де Врис рассказывает о своем опыте рабо58 ты в качестве консультанта-аналитика с Романом Абрамовичем. Описывая данный опыт, Врис отметил интересный факт: столкнувшись с переизбытком денег, его клиент озадачился целью иметь самую большую и дорогую яхту в мире. Сам автор оценивал такой шаг как проявление разрушительного влияния денег. Мы не будем анализировать этот поступок, однако из чувств патриотизма порадуемся тому, что нашему соотечественнику достичь своей цели удалось. Дал слово — держи, как говорится. И Р. Абрамович стал обладателем мегаяхты Eclipse («Затмение»), рис. 3.1. Рисунок 3.1 Вы, вероятно, читали и слышали о множестве способов для богатых и знаменитых потратить свое состояние: покупка запредельно дорогих домов, дворцов, частных островов — список можно продолжать бесконечно. Добираться до своих владений миллиардеры тоже предпочитают самыми эксклюзивными способами — на личном самолете или яхте, например. Кстати, действительно, шикарная яхта — удовольствие отнюдь не менее дешевое, чем все выше перечисленное. Приобрести такое судно, как Eclipse (будучи, всего-то, миллионером), можно и не мечтать, а вот взять в аренду — гораздо более реально. Оценочная стоимость этой яхты от 400 до 800 млн. долларов. Как указывают эксперты, на обслуживание яхты требуется почти 50 млн. долл. ежегодно, поэтому идея сдавать яхту в аренду, когда она не используется, пришлась кстати. Стоимость аренды составляет 2 млн. долл. в неделю – вот такой поразительный пример оптимального решения. Яхта снабжена системой предупреждения о ракетном нападении, пуленепробиваемыми окнами, двумя вертолетами (с двумя 59 взлетными площадками и ангарами), мини-подлодкой на 12 пассажиров, 4 прогулочными катерами и 20 скутерами. Управляется этот мини-курорт с защитой военного уровня экипажем в 50 человек. Все, о чем мы говорили в различных примерах и ситуациях, предложенных в курсе, направлено на получение оптимального решения. Рассмотрим ситуацию: у вас есть сбережение в размере 600 тыс. руб. Вы стоите перед выбором: поместить эту сумму в банк под 7% годовых, или взять в банке в кредит 700 тыс. руб. и купить однокомнатную квартиру. Для принятия решения вам предстоит взвесить все возможные «за» и «против». Утверждать, что всегда выгоднее вложение средств в недвижимость, нельзя (если, конечно, эта недвижимость человеку не нужна, а приобретается лишь для сохранения накопленного богатства, с целью последующей перепродажи). Во-первых, весьма существенны затраты на куплю-продажу. Вовторых, последующее содержание недвижимости требует каких-то средств – нужно оплачивать коммунальные платежи, налоги и др. В-третьих, любая недвижимость со временем ветшает. Вчетвертых, при покупке недвижимости вероятность быть обманутым больше, чем при помещении средств в надежный банк, могут быть поддельные документы или скрытые дефекты. В-пятых, недвижимость можно потерять полностью или частично в результате пожара, ограбления или стихийных бедствий. Поэтому если реальная ставка банковского процента отрицательна (размер годовых процентов меньше темпов инфляции), но невелика по абсолютной величине, то логичнее держать деньги в банке. Но если рассмотреть ситуацию с другой стороны, когда недвижимость приобретается с целью извлечения дохода, перекрывающего издержки хозяина на ее содержание (например, для сдачи в аренду) либо когда ее покупатель достоверно знает, что темпы роста цен на недвижимость будут существенно выше общих темпов инфляции, тогда выбор остается за покупкой однокомнатной квартиры. 60 Подводя итог нашему курсу, заключаем, что рассуждать, анализировать, считать, для принятия оптимального решения необходимо уметь всем: • и тому, кто рассуждает об оптимальности вложения 600 тыс. руб., • и тому, кто намерен сдать в аренду яхту за 2 млн. долл. в неделю. Надеемся, что в процессе изучения этого курса Вы приобрели для этого определенные навыки. Все замечания и предложения отсылайте по адресу:feedback@rfei.ru 61