Лекция на тему Экономико математические методы и модели 4
Работа добавлена на сайт bukvasha.net: 2013-11-09Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
от 25%
договор
¸Московский киновидео институт (МКВИ0 |
По дисциплине:
Экономико-математические
методы и модели
ПРЕПОДАВАТЕЛЬ МАЦНЕВ А.П.
Москва 2004 год
СОДЕРЖАНИЕ
1. Моделирование экономических систем.
Основные понятия и определения
1.1. Возникновение и развитие системных представлений
1.2. Модели и моделирование. Классификация моделей
1.3. Виды подобия моделей
1.4. Адекватность моделей
2. МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ ИХ РАСЧЕТА
2.1. Понятие операционного исследования
2.2. Классификация и принципы построения математических моделей
3. Некоторые сведения из математики
3.1. Выпуклые множества
3.2. Линейные неравенства
3.3. Значения линейной формы на выпуклом множестве
4. ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
4.1. Транспортная задача
4.2. Общая формулировка задачи линейного программирования
4.3. Графическая интерпретация решения задач линейного программирования
5. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
5.1. Общая и основная задачи линейного программирования
5.2. Геометрический метод решения задач линейного программирования
5.3. Графическое решение задачи распределения ресурсов
5.4. Симплексный метод
5.5. Анализ симплекс-таблиц
5.6. Решение транспортных задач
6. МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
И МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ
6.1. Постановка задачи нелинейного программирования
6.2. Постановка задачи динамического программирования
Основные условия и область применения
6.3. Многокритериальная оптимизация
1. Моделирование экономических систем.
Основные понятия и определения.
1.1. Возникновение и развитие системных представлений
Научно-техническая революция привела к возникновению таких понятий, как большие и сложные экономические системы, обладающие специфическими для них проблемами. Необходимость решения таких проблем привела к появлению особых подходов и методов, которые постепенно накапливались и обобщались, образуя, в конце концов, особую науку - системный анализ.
В начале 80-х годов системность стала не только теоретической категорией, но и осознанным аспектом практической деятельности. Широко распространилось понятие того, что наши успехи связаны с тем, насколько системно мы подходим к решению возникающих проблем, а наши неудачи вызваны отсутствием системности в наших действиях. Сигналом о недостаточной системности в нашем подходе к решению какой-либо задачи является появление проблемы, разрешение же возникшей проблемы происходит, как правило, при переходе на новый, более высокий, уровень системности нашей деятельности. Поэтому системность не только состояние, но и процесс.
В различных сферах человеческой деятельности возникли различные подходы и соответствующие методы решения специфических проблем, которые получили различные названия: в военных и экономических вопросах - «исследование операций», в политическом и административном управлении - «системный подход», в философии «диалектический материализм», в прикладных научных исследованиях - «кибернетика». Позже стало ясно, что все эти теоретические и прикладные дисциплины образуют как бы единый поток, «системное движение», которое постепенно оформилось в науку, получившую название «системный анализ». В настоящее время системный анализ является самостоятельной дисциплиной, имеющей свой объект деятельности, свой достаточно мощный арсенал средств и свою прикладную область. Являясь по существу прикладной диалектикой, системный анализ использует все средства современных научных исследований - математику, моделирование, вычислительную технику и натурные эксперименты.
þ Самая интересная и сложная часть системного анализа - это «вытаскивание» проблемы из реальной практической задачи, отделение важного от несущественного, поиск правильной формулировки для каждой из возникающих проблем, т.е. то, что называется «постановкой задачи».
Многие довольно часто недооценивают работу, связанную с формулировкой задачи. Однако многие специалисты полагают, что «хорошо поставить задачу - значит на половину ее решить». Хотя в большинстве случаев заказчику кажется, что он уже сформулировал свою проблему, системный аналитик знает, что предлагаемая клиентом постановка задачи является моделью его реальной проблемной ситуации и неизбежно имеет целевой характер, оставаясь приблизительной и упрощенной. Поэтому необходимо проверить эту модель на адекватность, что приводит к развитию и уточнению первоначальной модели. Очень часто первоначальная формулировка изложена в терминах не тех языков, которые необходимы для построения модели.
1.2. Модели и моделирование. Классификация моделей
Первоначально моделью называли некое вспомогательное средство, объект, который в определенных ситуациях заменял другой объект. Например, манекен в определенном смысле заменяет человека, являясь моделью человеческой фигуры. Древние философы считали, что отобразить природу можно только с помощью логики и правильных рассуждений, т.е. по современной терминологии с помощью языковых моделей. Через несколько столетий девизом английского Научного общества стал лозунг: «Ничего словами!», признавались только выводы, подкрепленные экспериментально или математическими выкладками.
В настоящее время для постижения истины существует 3 пути:
À теоретическое исследование;
Á эксперимент;
 моделирование.
þ Моделью называется объект-заместитель, который в определенных условиях может заменять объект-оригинал, воспроизводя интересующие нас свойства и характеристики оригинала, причем имеет существенные преимущества:
- дешевизну;
- наглядность;
- легкость оперирования и т.п.
þ В теории моделей моделированием называется результат отображения одной абстрактной математической структуры на другую - тоже абстрактную, либо как результат интерпретации первой модели в терминах и образах второй.
Paзвитие понятия модели вышло за пределы математических моделей и стало относиться к любым знаниям и представлениям о мире. Поскольку модели играют чрезвычайно важную роль в организации любой деятельности человека их можно разделить на познавательные (когницитивные) и прагматические, что соответствует делению целей на теоретические и практические.
þ Познавательная модель ориентирована на приближении модели к реальности, которую эта модель отображает. Познавательные модели являются формой организации и представления знаний, средством соединения новых знаний с имеющимися. Поэтому при обнаружении расхождения между моделью и реальностью встает задача устранения этого расхождения с помощью изменения модели.
þ Прагматические модели являются средством управления, средством организации практических действий, способом представления образцово правильных действий или их результата, т.е. являются рабочим представлением целей. Поэтомy при обнаружении расхождения между моделью и реальностью надо направить усилия на изменение реальности так, чтобы приблизить реальность к модели. Таким образом, прагматические модели носят нормативный характер, играют роль образца, под который подгоняется действительность. Примерами прагматических моделей служат планы, кодексы законов, рабочие чертежи и т.д.
Другим принципом классификации целей моделирования может служить деление моделей на статические и динамические.
þ Для одних целей нам может понадобиться модель конкретного состояния объекта в определенный момент времени, своего рода «моментальная фотография» объекта. Такие модели называются статическими. Примером являются структурные модели систем.
þ В тех же случаях, когда возникает необходимостъ в отображении процесса изменения состояний, требуются динамические модели систем.
В распоряжении человека имеется два типа материалов для построения моделей - средства самого сознания и средства окружающею материального мира. Соответственно этому модели делятся на абстрактные (идеальные) и материальные.
þ Очевидно, что к абстрактным моделям относятся языковые конструкции и математические модели. Математические модели обладают наибольшей точностью, но чтобы дойти до их использования в данной области, необходимо получить достаточное количество знаний. По мнению Канта, любая отрасль знания может тем более именоваться наукой, чем в большей степени в ней используется математика.
1.3. Виды подобия моделей
Чтобы некоторая материальная конструкция могла быть моделью, т.е. замещала в каком-то отношении оригинал, между оригиналом и моделью должно быть установлено отношение подобия. Существуют разные способы установления такого подобия, что придает моделям особенности, специфичные для каждого способа.
þ Прежде всего, это подобие, устанавливаемое в процессе создания модели. Назовем такое подобие прямым. Примером такого подобия являются фотографии, масштабированные модели самолетов, кораблей, макеты зданий, выкройки, куклы и т.д.
Следует помнить, что как бы хороша ни была модель, она все-таки лишь заменитель оригинала, только в определенном отношении. Даже тогда, когда модель прямого подобия выполнена из того же материала, что и оригинал, т.е. подобна ему субстратно, возникают проблемы переноса результатов моделирования на оригинал. Например, при испытании уменьшенной модели самолета в аэродинамической трубе задача пересчета данных модельного эксперимента становится нетривиальной и возникает разветвленная, содержательная теория подобия, позволяющая привести в соответствие масштабы и условия эксперимента, скорость потока, вязкость и плотность воздуха. Трудно достигается взаимозаменяемость модели и оригинала в фотокопиях произведений искусства, голографических изображениях предметов искусства.
þ Второй тип подобия между моделью и оригиналом называется косвенным. Косвенное подобие между оригиналом и моделью объективно существует в природе и обнаруживается в виде достаточной близости или совпадения их абстрактных математических моделей и вследствие этого широко используется в практике реального моделирования. Наиболее характерным примером может служить электромеханическая аналогия между маятником и электрическим контуром.
Оказалось, что многие закономерности электрических и механических процессов описываются одинаковыми уравнениями, различие состоит в разной физической интерпретации переменных, входящих в это уравнение. Роль моделей, обладающих косвенным подобием, очень велика и роль аналогий (моделей косвенного подобия) в науке и практике трудно переоценить. Аналоговые вычислительные машины позволяют найти решение почти всякого дифференциального уравнения, представляя собой, таким образом, модель, аналог процесса, описываемого этим уравнением. Использование электронных аналогов в практике определяется тем, что электрические сигналы легко измерить и зафиксировать, что дает известные преимущества модели.
þ Третий, особый класс моделей составляют модели, подобие которых оригиналу не является ни прямым, ни косвенным, а устанавливается в результате соглашения. Такое подобие называется условным. С моделями условного подобия приходится иметь дело очень часто, поскольку они являются способом материального воплощения абстрактных моделей. Примерами условного подобия служат деньги (модель стоимости), удостоверение личности (модель владельца), всевозможные сигналы (модели сообщения).
Например, сигналом наступления кочевников у древних славян служили костры на курганах. Бумажные денежные знаки могут играть роль модели стоимости только до тех пор, пока в среде их обращения существуют правовые нормы, поддерживающие их функционирование. Керенки в настоящее время имеют только историческую ценность, но это не деньги, в отличие от царских золотых монет, которые представляют материальную ценность из-за наличия благородного металла. Особенно наглядна условность знаковых моделей: цветок в окне явочной квартиры Штирлица означал провал явки, ни сорт, ни цвет не имели никакого отношения к знаковой функции цветка.
1.4. Адекватность моделей
þ Модель, с помощью которой успешно достигается поставленная цель, будем называть адекватной этой цепи. Адекватность означает, что требования полноты, точности и правильности (истинности) модели выполнены не вообще, а лишь в той мере, которая достаточна достижения поставленной цели.
В ряде случаев удается ввести меру адекватности некоторых целей, т.е. указать способ сравнения двух моделей по степени успешности достижения цели с их помощью. Если к тому же есть способ количественно выразить меру адекватности, то задача улучшения модели существенно облегчается. Именно в таких случаях можно количественно ставить, вопросы об идентификации модели т.e. о нахождении в заданном классе моделей наиболее адекватной, об исследовании чувствительности и устойчивости моделей т.e. зависимости меры адекватности модели от ее точности, об адаптации моделей, т.е. подстройке параметров модели с целью повышения ее точности.
Приближенность модели не следует путать с адекватностью. Приближенность модели может быть очень высокой, но во всех случаях модель - это другой объект и различия неизбежны (единственной совершенной моделью любого объекта является сам объект). Величину, меру, степень приемлемости различия можно ввести, только соотнося его с целью моделирования. Так некоторые подделки произведений искусства даже эксперты не могут отличить от оригинала, но все-таки это всего лишь подделка, и с точки зрения вложения капитала не представляет никакой ценности, хотя для любителей искусства ничем не отличается от оригинала. У английского фельдмаршала Монтгомери во время войны был двойник, появление которого на разных участках фронта намеренно дезинформировало разведку немцев.
Упрощение является сильным средством для выявления главных эффектов в исследуемом явлении: это видно на примере таких явлений физики, как идеальный газ, абсолютно упругое тело, математический маятник и абсолютно твердый рычаг.
Есть еще один, довольно загадочный, аспект упрощенности модели. Почему-то оказывается, что из двух моделей, одинаково хорошо описывающих систему, та модель, которая проще, ближе к истине. Геоцентрическая модель Птоломея позволяла рассчитать движение планет, хотя и по очень громоздким формулам, с переплетением сложных циклов. Переход к гелиоцентрической модели Коперника значительно упростил расчеты. Древние говорили, что простота - печать истины.
2. МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ ИХ РАСЧЕТА
2.1. Понятие операционного исследования
Bпервые математические модели были использованы для решения практической задачи в 30-х годах в Великобритании при создании системы противовоздушной обороны. Для разработки данной системы были привлечены ученые различных специальностей. Система создавалась в условиях неопределенности относительно возможных действий противника, поэтому исследования проводились на адекватных математических моделях. В это время впервые был применен термин: «операционное исследование», подразумевающий исследования военной операции. В последующие годы операционные исследования или исследования операций развиваются как наука, результаты которой применяются для выбора оптимальных решений при управлении реальными процессами и системами.
Решения человек принимал всегда и во всех сферах своей деятельности. Раньше хотели, чтобы принимаемые решения всегда были правильными. Теперь принято говорить, что решения должны быть оптимальными. Чем сложнее объект управления, тем труднее принять решение, и, следовательно, тем легче допустить ошибку. Вопросам принятия решений на основе применения ЭВМ и математических моделей посвящена новая наука «Исследование операций», приобретающая в последние годы все более обширное поле приложений. Эта наука сравнительно молодая, ее границы и содержание нельзя считать четко определенными.
Предмет под названием «Исследование операций» входит в программу элитарных вузов, но не всегда в этот термин вкладывается одно и то же содержание. Некоторые ученые под «исследованием операций» понимают, главным образом, математические методы оптимизации, такие как линейные, нелинейные, динамическое программирование. Другие к исследованию операций подходят с позиции теории игр и статистических решений. Наконец, некоторые ученые вкладывают в понятие «исследование операций» чрезмерно широкий смысл, считая ее основой системного анализа и «наукой наук».
Окончательно термин «исследование операций» закрепился в конце Второй мировой войны, когда в вооруженных силах США были сформированы специальные группы математиков и программистов, в задачу которых входила подготовка решений для командующих боевыми действиями. В дальнейшем исследование операций расширило область своих применений на самые разные области практики: экономика, транспорт, связь и даже охрана природы.
чтобы человеку принять решение без ЭВМ, зачастую ничего не надо, кроме опыта и интуиции. Правда, никакой гарантии правильности, а тем более оптимальности при этом нет. Подчеркнем, что ЭВМ никаких решений не принимает. Решение принимает человек (ЛПР). А ЭВМ только помогает найти варианты решений. Непременное присутствие человека (как окончательный инстанции принятия решений) не отменяется даже при наличии полностью автоматизированной системы управления. Нельзя забывать о том, что само создание управляющего алгоритма, выбор одного из возможных его вариантов, есть тоже решение. По мере автоматизации управления функции человека перемещаются с одного уровня управления на другой - высший. Основные этапы решения задачи принятия оптимальных решений с помощью ЭВМ показаны на Рис. 2.1.
Исходные данные | ||||||||||||||||||
H | ||||||||||||||||||
Объект | F | Задача | F | Модель | F | Алгоритм | F | Программа | F | ЭВМ : | ||||||||
Пакет прикладных программ (ППП) | H | |||||||||||||||||
Решение | ||||||||||||||||||
Рис. 2.1. Основные этапы решения задачи принятия решения с помощью ЭВМ.
выбор задачи - важнейший вопрос. Какие основные требования должна удовлетворять задача? Таких требований два:
À должно существовать, как минимум, два варианта ее решения (ведь если вариант один, значит и выбирать не из чего);
Á надо четко знать в каком смысле искомое решение должно быть наилучшим (кто не знает, куда ему плыть - тому нет и попутного ветра).
Выбор задачи завершается ее содержательной постановкой. Когда производится содержательная постановка задачи, к ней привлекаются специалисты в предметной области. Они прекрасно знают свой конкретный предмет, но не всегда представляют, что требуется для формализации задачи и представления ее в виде математической модели.
Хорошую модель составить не просто. Известный математик Р.Беллман сказал так: «Если мы попытаемся включить в нашу модель слишком много черт действительности, то захлебнемся в сложных уравнениях; если слишком упростим ее, то она перестанет удовлетворять нашим требованиям». Таким образом, исследователь должен пройти между западнями Переупрощения и болотом Переусложнения. Для выполнения успеха моделирования надо выполнить три правила, которые, по мнению древних, являются признаками мудрости. Эти правила применительно к задачам математического моделирования и формулируются так: учесть главные свойства моделируемого объекта; пренебрегать его второстепенными свойствами; уметь отделить главные свойства от второстепенных.
Составление модели - это искусство, творчество. Древние говорили: «Если двое смотрят на одно и то же, это не означает, что оба видят одно и то же». И слова древних греков: «Если двое делают одно и то же, это не значит, что получится одно и то же». Эти слова в полной мере относятся к составлению математических моделей. Если математическая модель - это диагноз заболевания, то алгоритм - это метод лечения.
Можно выделить следующие основные этапы операционного исследования:
À наблюдение явления и сбор исходных данных;
Á постановка задачи;
 построение математической модели;
à расчет модели;
Ä тестирование модели и анализ выходных данных. Если полученные результаты не удовлетворяют исследователя, то следует либо вернуться на этап 3, т.e. предложить для решения задачи другую математическую модель; либо вернуться на этап 2, т.e. поставить задачу более корректно;
Å применение результатов исследований.
Таким образом, операционное исследование является итерационным процессом, каждый следующий шаг которого приближает исследователя к решению стоящей перед ним проблемы. В центре операционного исследования находятся построение и расчет математической модели.
þ Математическая модель - это система математических соотношений, приближенно, в абстрактной форме описывающих изучаемый процесс или систему.
þ Экономико-математическая модель - это математическая модель, предназначенная для исследования экономической проблемы.
Проведение операционного исследования, построение и расчет математической модели позволяют проанализировать ситуацию и выбрать оптимальные решения по управлению ею или обосновать предложенные решения. Применение математических моделей необходимо в тех случаях, когда проблема сложна, зависит от большого числа факторов, по-разному влияющих на ее решение.
Использование математических моделей позволяет осуществить предварительный выбор оптимальных или близких к ним вариантов решений по определенным критериям. Они научно обоснованы, и лицо, принимающее решение, может руководствоваться ими при выборе окончательного решения. Следует понимать, что не существует решений, оптимальных «вообще». Любое решение, полученное при расчете математической модели, оптимально по одному или нескольким критериям, предложенным постановщиком задачи и исследователем.
В настоящее время математические модели применяются для анализа, прогнозирования и выбора оптимальных решений в различных областях экономики. Это планирование и оперативное управление производством, управление трудовыми ресурсами, управление запасами, распределение ресурсов, планировка и размещение объектов, руководство проектом, распределение инвестиций и т.п.
2.2. Классификация и принципы построения
математических моделей
Можно выделить следующие основные этапы построения математической модели:
À Определение цели, т.e. чего хотят добиться, решая поставленную задачу.
Á Определение пapaметров модели, т.е. заранее известных фиксированных факторов, на значения которых исследователь не влияет.
 Формирование управляющих переменных, изменяя значение которых можно приближаться к поставленной цели. Значения управляющих переменных являются решениями задачи.
à Определение области допустимых решений, т.е. тех ограничений, которым должны удовлетворять управляющие переменные.
Ä Выявление неизвестных факторов, т.е. величин, которые могут изменяться случайным или неопределенным образом.
Å Выражение цели через управляющие переменные, параметры и неизвестные факторы, т.e. формирование целевой функции, называемой также критерием эффективности или критерием оптимальности задачи.
Введем следующие условные обозначения:
a - параметры модели;
x - управляющие переменные или решения;
X - область допустимых решений;
x - случайные или неопределенные факторы;
W - целевая функция или критерий эффективности (критерий оптимальности).
W=W (x, a, x)
В соответствии с введенными терминами, математическая модель задачи имеет следующий вид:
W=W (x, a, x) ® max (min) (2.1)
x Î X
þ Решить задачу - это значит найти такое оптимальное решение x*ÎX, чтобы при данных фиксированных параметрах a и с учетом неизвестных x факторов значения критерия эффективности W было по возможности максимальным (минимальным).
W*=W (x*, a, x) = max (min) W (x, a, x)
x Î X
þ Таким образом, оптимальное решение - это решение, предпочтительное перед другими по определенному критерию эффективности (одному или нескольким).
Перечислим некоторые основные принципы построения математической модели:
À Необходимо соизмерять точность и подробность модели, во-первых, с точностью тex исходных данных, которыми располагает исследователь, и, во-вторых, с теми результатами, которые требуется получить.
Á Математическая модель должна отражать существенные черты исследуемого явления и при этом не должна его сильно упрощать.
 Математическая модель не может быть полностью адекватна реальному явлению, поэтому для его исследования лучше использовать несколько моделей, для построения которых применены разные математические методы. Если при этом получаются сходные результаты, то исследование заканчивается. Если результаты сильно различаются, то следует пересмотреть постановку задачи.
à Любая сложная система всегда подвергается малым внешним и внутренним воздействиям, следовательно, математическая модель должна быть устойчивой (сохранять свойства и структуру при этих воздействиях).
По числу критериев эффективности математические модели делятся на однокритериальные и многокритериальные. Многокритериальные математические модели содержат два и более критерия.
По учету неизвестных факторов математические модели делятся на детерминированные, стохастические и модели с элементами неопределенности.
þ В стохастических моделях неизвестные факторы - это случайные величины, для которых известны функции распределения и различные статистические характеристики (математическое ожидание, дисперсия, среднеквадратическое отклонение и т.п.). Среди стохастических характеристик можно выделить:
- модели стохастического программирования, в которых либо в целевую функцию (2.1), либо в ограничения (2.2) входят случайные величины;
- модели теории случайных процессов, предназначенные для изучения процессов, состояние которых в каждый момент времени является случайной величиной;
- модели теории массового обслуживания, в которой изучаются многоканальные системы, занятые обслуживанием требований. Также - к стохастическим моделям можно отнести модели теории полезности, поиска и принятия решений.
þ Для моделирования ситуаций, зависящих от факторов, для которых невозможно собрать статистические данные и значения которых не определены, используются модели с элементами неопределенности.
þ В моделях теории игр задача представляется в виде игры, в которой участвуют несколько игроков, преследующих разные цели, например, организацию предприятия в условиях конкуренции.
þ В имитационных моделях реальный процесс разворачивается в машинном времени, и прослеживаются результаты случайных воздействии на него, например, организация производственного процесса.
þ В детерминированных моделях неизвестные факторы не учитываются. Несмотря на кажущуюся простоту этих моделей, к ним сводятся многие практические задачи, в том числе большинство экономических задач. По виду целевой функции и ограничений детерминированные модели делятся на: линейные, нелинейные, динамические и графические.
þ В линейных моделях целевая функция и ограничения линейны по управляющим переменным. Построение и расчет линейных моделей являются наиболее развитым разделом математического моделирования, поэтому часто к ним стараются свести и другие задачи либо на этапе постановки, либо в процессе решения. Для линейных моделей любого вида и достаточно большой размерности известны стандартные методы решения.
þ Hелинейные модели - это модели, в которых либо целевая функция, либо какое-нибудь из ограничений (либо все ограничения) нелинейны по управляющим переменным. Для нелинейных моделей нет единого метода расчета. В зависимости от вида нелинейности, свойств функции и ограничений можно предложить различные способы решения. Однако может случится и так, что для поставленной нелинейной задачи вообще не существует метода расчета. В этом случае задачу следует упростить, либо сведя ее к известным линейным моделям, либо просто линеаризовав модель.
þ В динамических моделях, в отличие от статических линейных и нелинейных моделей, учитывается фактор времени. Критерий оптимальности в динамических моделях может быть самого общего вида (и даже вообще не быть функцией), однако для него должны выполняться определенные свойства. Расчет динамических моделей сложен, и для каждой конкретной задачи необходимо разрабатывать специальный алгоритм решения.
þ Графические модели - используются тогда, когда задачу удобно представить в виде графической структуры.
3. Некоторые сведения из математики
3.1. Выпуклые множества
Предварительно дадим некоторые понятия, весьма важные для линейного программирования.
þ множество точек называется выпуклыми, если оно вместе с любыми двумя точками содержит отрезок, соединяющий эти точки. Простейшими примерами выпуклых множеств могут служить: отрезок, треугольник, квадрат, некоторые геометрические тела, например, пирамида, куб и т.д.
заметим, что выпуклый многоугольник обладает тем свойством, что весь расположен по одну сторону каждой из прямых, участвующих в ее образовании.
þ выпуклой линейной комбинацией точек М1, М2, ... Мn называется любая точка М такая, что:
М=a1M1+a2M2 + ... +anMn,
где ai ³ 0 и a1+a2+ ... +an=1.
þ Обобщая сказанное выше, можно сказать, что множество точек называется выпуклым, если вместе с любыми своими точками оно содержит и выпуклую произвольную комбинацию этих точек. Поскольку произвольная точка отрезка представляет собой выпуклую комбинацию его концов, то это и означает, что выпуклое множество вместе с двумя данными точками содержит весь соединяющий их отрезок.
Очевидно, что всякая точка выпуклого многоугольника, лежащая внутри его или на одной из сторон, за исключением вершин, может быть представлена как выпуклая линейная комбинация других точек этого многоугольника. Напротив, вершины многоугольника не представляются в виде выпуклой комбинации двух каких-нибудь других точек. В этом смысле вершины многоугольника называют экстремальными точками.
þ прямая линия называется опорной, если она имеет с выпуклым многоугольником, по крайней мере, одну общую точку и весь многоугольник расположен по одну сторону от этой прямой. Через каждую из вершин многоугольника можно провести бесконечное множество опорных линий. В пространстве трех измерений, по аналогии с понятием опорной прямой вводится понятие опорной плоскости.
þ Опорной плоскостью называется всякая плоскость, имеющая с выпуклым многогранником, по крайней мере, одну общую точку, причем такую, что весь многогранник расположен по одну сторону от нее. Опорная плоскость может иметь с выпуклым многогранником общую точку (вершину многогранника), прямую (ребро), и, наконец, общую грань.
3.2. Линейные неравенства
рассмотрим подробнее системы линейных неравенств и покажем, что решение их тесно связано с понятиями выпуклого многоугольника и выпуклого многогранника.
|
из которого видно, что прямая отсекает по осям отрезки, равные 4 и 3.
Неравенство 3х1+4х2 < 12 определяет собой совокупность всех точек плоскости, лежащих ниже прямой, т.е. в заштрихованной части (Рис. 2).
|
ì3х1+4х2 £ 12
íx1< 2
îх1 > 0 и х2 > 0
|
Полученный многоугольник является выпуклым, ибо вместе с любыми двумя точками содержит весь соединяющий их отрезок. таким образом, мы видим, что выпуклый многоугольник можно задать аналитически, с помощью системы линейных неравенств. Линейное уравнение с тремя переменными: a11x1+a12x2+a13x3=b1 определяет в пространстве некоторую плоскость, которая рассекает все пространство на два полупространства.
В связи с этим неравенство a11x1+a12x2+a13x3 £ b1 определяет одно из полупространств, к которому принадлежит также и сама граничная плоскость. В общем случае, когда система неравенств совместна, пространство решений образует некоторый выпуклый многогранник - многогранник решений. Частным случаем его могут быть: отдельная грань, ребро или точка. Последнее имеет место, когда система неравенств имеет одно единственное решение. Дальнейшие обобщения приводят нас к рассмотрению m линейных неравенств с n неизвестными. Каждое уравнение ai1x1+ai2x2+ ... +ainxn=bi является уравнением некоторой гиперплоскости в n-мерном пространстве, которая как бы рассекает все пространство на два полупространства.
3.3. Значения линейной формы на выпуклом множестве
Предположим, что задана некоторая система из m-линейных неравенств (или уравнений) с n переменными х1, х2, ..., хn. Система неравенств в случае совместности определяет некоторое выпуклое множество в n-мерном пространстве, ограниченное или бесконечное (многогранник решений).
Допустим далее, что нам задана некоторая линейная форма от этих переменных, определяющая функцию цели:
¦=c1x1+c2x2+ ... +cnxn
В каждой точке выпуклого множества, т.е. для каждого решения нашей системы, линейная форма ¦ принимает определенное значение. Возникает вопрос: в каких точках выпуклого множества линейная форма ¦ достигает своего наибольшего и наименьшего значения, если, конечно, такие существуют? Решение общей задачи линейного программирования сводится, таким образом, к нахождению точек выпуклого множества, в которых заданная линейная форма достигает оптимального значения, и мы ищем такие точки (х1, х2, ..., хn), координаты которых неотрицательны. Сформулируем одно важное утверждение, облегчающее решение задачи.
þ В тех случаях, когда множество решений задачи линейного программирования образует выпуклый многогранник, линейная форма достигает оптимального значения в одной из его вершин, в связи с чем последние и называются экстремальными точками.
В общем случае, линейная форма ¦=c1x1+c2x2+ ... +cnxn задает гиперплоскость в n-мерном пространстве. При ¦=0 эта гиперплоскость проходит через начало координат. Затем передвигаем эту плоскость параллельно самой себе в направлении вектора P перпендикулярно к этой плоскости. Первая из вершин, в которой линейная форма (гиперплоскость) встретит выпуклый многогранник, будет точкой, в которой линейная форма достигает наименьшего значения, а последняя из вершин - точкой, в которой линейная форма достигает наибольшего значения.
Может случиться, что гиперплоскость окажется параллельной одной из граней или ребер выпуклого многогранника, и тогда линейная форма ¦ достигает своего наименьшего или наибольшего значения в любой точке, лежащей на этом ребре. Но и тогда она достигает эти значения в вершине, лежащей на этом ребре.
Существуют различные методы решения задач линейного программирования. Одним из наиболее простых и наглядных методов решения является графический метод. Этот метод позволяет решать задачи, которые приводят к системам уравнений с двумя или тремя переменными. Большинство задач линейного программирования приводит к системам линейных неравенств с большим числом переменных. Эти задачи решаются симплексным методом.
4. ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
4.1. Транспортная задача
уголь, добываемый в нескольких месторождениях, отправляется ряду потребителей. нам известно, сколько угля добывается в каждом из месторождений, скажем за месяц и сколько его требуется на тот же срок каждому из потребителей. Известны расстояния между месторождениями и потребителями, а также условия сообщения между ними. Учитывая эти данные. Можно подсчитать, во что обходится перевозка каждой тонны угля из любого месторождения в любой пункт потребления. Требуется при этих условиях спланировать перевозки угля таким образом, чтобы затраты на них были минимальными.
Пусть для простоты заданы всего 4 месторождения М1, М2, М3, М4, причем их ежемесячная добыча составляет a1, а2, а3, а4 тонн угля. Предположим далее, что этот уголь надо доставить в пункты потребления b1, b2, b3, b4, b5, соответственно с ежемесячными потребностями этих пунктов. Будем считать, что общее производство угля равно суммарной потребности в нем (сбалансированность планов): a1, а2, а3, а4 = b1, b2, b3, b4, b5. Задача состоит в определении такого плана перевозок, при котором общая стоимость перевозок была бы наименьшей. Обозначим через x11 количество угля (в тоннах), предназначенное к отправлению из M1 в П1; вообще через xij обозначим количество угля, отправляемого из месторождения Mi в пункт потребления Пj. Схема перевозок примет вид, изображенный в таблице 4.1.
Схема перевозок таблица 4.1
ПН | в П1 | в П2 | в П3 | в П4 | в П5 | Всего | |
ПО | отправлено | ||||||
из М1 | х11 | х12 | х13 | х14 | х15 | a1 | |
из М2 | х21 | х22 | х23 | х24 | х25 | а2 | |
из М3 | х31 | х32 | х33 | х34 | х35 | а3 | |
из М4 | х41 | х42 | х43 | х44 | х45 | а4 | |
Всего привезено | b1 | b2 | b3 | b4 | b5 |
4.1 | ìх11+х12+х13+х14+х15 = b1 ïх21+х22+х23+х24+х25 = b2 íх31+х32+х33+х34+х35 = b3 îх41+х42+х43+х44+х45 = b4 | 4.2 | ìх11+х12+х13+х14+х15 = a1 ïх21+х22+х23+х24+х25 = a2 íх31+х32+х33+х34+х35 = a3 îх41+х42+х43+х44+х45 = a4 |
x i j = C i j . X i j
Общая стоимость S всех перевозок будет равна: (4.3)
S=c11х11+c12х12+c13х13+c14х14+c15х15+ ... +c41х41+c42х42+c43х43+c44х44+c45х45.
4.2. Общая формулировка задачи линейного программирования
Аналогично транспортной задаче решается задача об оптимизации распределения ресурсов (трудовых, материальных, финансовых) и задача о диете. При всем разнообразии, по своему конкретному содержанию каждая из них была задачей на нахождение наиболее выгодного варианта. С точки зрения математической, в каждой задаче ищутся значения нескольких неизвестных, причем требуется, чтобы:
À эти значения удовлетворяли некоторой системе линейных уравнений или неравенств;
Á при этих значениях некоторая линейная функция (линейная форма) от этих неизвестных обращалась в минимум (максимум);
 эти значения были неотрицательными.
Задачами такого рода и занимается линейное программирование.
þ Говоря точнее, линейное программирование - это математическая дисциплина, изучающая методы нахождения наименьшего (или наибольшего) значения линейной функции нескольких переменных, при условии, что последние удовлетворят конечному числу линейных уравнений или неравенств. Общая математическая формулировка задачи линейного программирования выглядит следующим образом.
Дана система линейных уравнений:
ìа11x1+а12x2+ ... +а1nxn = b1
ïа21x1+а22x2+ ... +а2nxn = b2
(I) í ... ... ... ... ... ... ... ...
îаm1x1+аm2x2+ ... +аmnxn = bm
и линейная функция ¦=c1x1+c2x2+ ... +cnxn (II).
Требуется найти такие неотрицательные решения х1 ³ 0, х2 ³ 0 ... хn ³ 0 (III) системы (I) при которых функция ¦ принимает наименьшее (наибольшее) значение.
Уравнения (I) называются ограничениями данной задачи, уравнение (II) называется линейной формой, а уравнение (III), строго говоря, тоже являются ограничениями, однако их не принято так называть, поскольку они являются общими для всех задач линейного программирования, а не только конкретной задачи. Любое неотрицательное решение системы уравнений называется допустимым. Допустимое решение, дающее минимум функции ¦, оптимальное решение (если оно существует) не обязательно единственно; возможны случаи, когда имеется бесчисленное множество оптимальных решений. Наконец, саму функцию ¦ часто называют линейной формой или функцией цели.
Казалось бы, т.к. задача линейного программирования ставится как задача минимизации некоторой функции ¦, то можно применить классический прием дифференциального исчисления. Однако частные производные ¦ равны коэффициентам при неизвестных, которые в «нуль» одновременно не обращаются.
4.3. Графическая интерпретация
решения задач линейного программирования
Задачу линейного программирования (ЛП) можно решать аналитическими и графическими методами. Аналитические методы являются основой для решения задачи на ЭВМ. Их единственный недостаток состоит в том, что в отличие от графических методов, они недостаточно наглядны. Графические методы очень наглядны, но они пригодны лишь для решения задач на плоскости, т.е. когда размерность пространства К=2. Однако, учитывая большую наглядность графических методов, с их помощью рассмотрим идею решения задачи ЛП на примере задачи распределения ресурсов.
Однако прежде чем заняться решением, сделаем некоторые замечания. Пусть мы имеем систему m уравнения с n неизвестными (I).
Возможны следующие варианты:
À Число неизвестных меньше, чем число уравнений n < m.
например: ì2x1=4, в этом случае n=1;
îx1=5, тогда m=2 (число линейно независимых уравнений). (4.4)
Очевидно, что система (4.4) решения не имеет, и она несовместна;
Á Число неизвестных равно числу уравнений n=m.
В этом случае система имеет единственное решение или не имеет ни одного. Заметим, что m равно числу линейно независимых уравнений.
Для системы: ì2x=10, n=1, m=1;
î6x=30.
 Если число неизвестных больше числа уравнений, то система имеет бесчисленное множество решений. Пусть n > m. Например:
2x1+x2=2 (4.5)
Очевидно, что это уравнение прямой, и все значения x1 и x2, лежащие на этой прямой, являются решением уравнения (4.2). Значит уравнение (4.5) имеет бесчисленное множество решений.
В случае, когда система имеет больше одного возможного решения, может быть поставлена задача оптимизации, суть которой в том, что из всех допустимых решений, удовлетворяющих ограничениям и граничным условиям, выбрать такое, которое придает целевой функции оптимум. Вспомним построение линейных зависимостей. Пусть дано уравнение:
a1x1+a2x2=b (4.6)
Преобразуем его к виду:
Запись (4.7) называют уравнением прямой в отрезках, что изображено на Рис. 4.1. Рассмотрим еще одну форму представления уравнения (4.6). Запишем это уравнение в виде:
a2x2=b-a1x1
или
или
x2=F-kx1 (4.8)
Уравнение (4.8) изображено на рис. 4.2.
|
|
a1x1+a2x2 £ b (4.9)
изображается как полуплоскость, показанная на рис. 4.1. На этом рисунке часть плоскости, удовлетворяющая неравенству, заштрихована. Координаты всех точек, принадлежащих заштрихованному участку, имеют такие значения x1 и x2, которые удовлетворяют заданному неравенству. Значит, эти значения составляют область допустимых решений (ОДР). Саму прямую считаем принадлежащей каждой из двух указанных полуплоскостей. Предположим теперь, что задано не одно неравенство, а система:
ìа11x1+а12x2 £ b1
ïа21x1+а22x2 £ b2
(4.10) í ... ... ... ...
îаm1x1+аm2x2 £ bm,
где первое неравенство определяет некоторую полуплоскость П1, второе - полуплоскость П2 и т.д.
если какая-либо пара чисел (x1, x2) удовлетворяет всем неравенствам (4.10), то, соответствующая точка Р(x1, x2), принадлежит всем полуплоскостям П1, П2, ... Пm одновременно. Другими словами, точка Р принадлежит пересечению (общей части) полуплоскостей П1, П2, ... Пm, т.е. некоторой многоугольной области М (Рис. 4.3), которая является ОДР. Вдоль контура области изображены штрихи, идущие внутрь области. Они одновременно указывают, с какой стороны от данной прямой лежит соответствующая полуплоскость, то же самое указано и с помощью стрелок на каждой линии. Сразу же отметим, что ОДР не всегда бывает, ограничена: в результате пересечения нескольких полуплоскостей может возникнуть и неограниченная область (Рис. 4.4). Возможен и случай, когда область допустимых решений (ОДР) пуста. Это означает, что система (5.7) противоречива (Рис. 4.5). Многоугольник ОДР обладает весьма важным свойством: он является выпуклым.
|
|
|
В случае трех неизвестных, каждое уравнение представляет собой плоскость в пространстве. Каждая плоскость разбивает все пространство на два полупространства. Система неравенств определяет в пространстве выпуклый объемный многогранник, который представляет ОДР.
5. МЕТОДЫ РЕШЕНИЯ
ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
5.1. Общая и основная задачи линейного программирования
К математическим задачам линейного программирования приводят исследования конкретных производственно-хозяйственных ситуаций, которые в том или ином виде интерпретируются как задачи об оптимальном использовании ограниченных ресурсов (задача о раскрое, смесях и т.д.).
Во всех этих задачах требуется найти максимум или минимум линейной функции при условии, что ее переменные принимают неотрицательные значения и удовлетворяют некоторой системе линейных уравнений или линейных неравенств либо системе, содержащей как линейные неравенства, так и линейные уравнения. Каждая из этиx задач является частным случаем общей задачи линейного программирования.
þ Oбщей задачей линейного программирования называется задача, которая coстоит в определении максимального (минимального) значения функции:
при условии:
Xj ³ 0 (j=1, 1; 1 £ n) (5.4)
где aij, bi, сj - заданные постоянные величины и k £ m.
þ Функция (5.1) называется целевой функцией (или линейной формой) задачи (5.1)-(5.4), а условия (5.2)-(5.4) - ограничениями данной задачи.
þ Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (5.1) при выполнении условий (5.2) и (5.4), где k=m и 1=n.
þ Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (5.1) при выполнении условий (5.3) и (5.4), где k=0 и 1=n.
þ Совокупность чисел Х* = (x1, x2, ..., xn), удовлетворяющих ограничениям задачи (5.2)-(5.4), называется допустимым решением (или планом).
þ План Х* = (x1, x2, ..., xn), при котором целевая функция задачи (5.1) принимает свое максимальное (минимальное) значение, называется оптимальным.
значение целевой функции (5.1) при плане X будем обозначать через F(X). Следовательно, Х* - оптимальный план задачи, если для любого X выполняется неравенство F(X) £ F(Х*) (соответственно F(X) ³ F(Х*)).
5.2. Геометрический метод решения
задач линейного программирования
Перепишем основную задачу линейного программирования в векторной форме: найти максимум функции
F=CX (5.5)
при условиях:
x1P1+x2P2+ ... +xnPn = P0 (5.6)
Х ³ 0 (5.7)
где C = (с1, с2, ..., сn), Х = (х1, х2, ..., хn); СХ - скалярное произведение; Р1, Р2, ..., Рn и Р0 - m-мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных членах системы уравнений задачи.
þ План X = (х1, х2, ..., хn) называется опорным планом основной задачи линейного программирования, если система векторов Pj, входящих в разложение (5.6) с положительными коэффициентами xj, линейно независима.
Непустое множество планов основной задачи линейного программирования образует выпуклый многогранник. Каждая вершина этого многогранника определяет опорный план. В одной из вершин многогранника решений (т.е. для одного из опорных планов) значение целевой функции является максимальным (при условии, что функция ограничена сверху на множестве планов). Если максимальное значение функция принимает более чем в одной вершине, то это же значение она принимает в любой точке, являющейся выпуклой линейной комбинацией данных вершин.
Вершину многогранника решений, в которой целевая функция принимает максимальное значение, найти сравнительно просто, если задача, записанная в форме стандартной, содержит не более двух переменных или задача, записанная в форме основной, содержит не более двух свободных переменных. Haйдем решение задачи, состоящей в определении максимального значения функции:
F=c1x1 + с2х2 (5.8)
при условиях:
ai1x1+ai2x2 £ bi (i=1, k) (5.9)
xj ³ 0 (i=1,2) (5.10)
Каждое из неравенств (5.9), (5.10) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми ai1+ai2=bi (i=1, k), x1=0 и x2=0. В этом случае, если система неравенств (5.9), (5.10) совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям.
þ Так как множество точек пересечения данных полуплоскостей выпуклое, то областью допустимых решений (ОДР) задачи (5.8)-(5.10) является выпуклое множество, которое называется многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки точных равенств.
Таким образом, исходная задача линейного программирования состоит в нахождении такой точки области допустимых решений, в которой целевая функция F принимает максимальное значение. Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. При указанных условиях в одной из вершин ОДР целевая функция принимает максимальное значение. Для определения данной вершины построим линию уровня c1x1+c2x2=h (где h - некоторая постоянная), проходящую через ОДР, и будем ее передвигать в направлении вектора C=(с1; с2) до тех пор, пока она не пройдет через последнюю ее общую точку с многоугольником ОДР. Координаты указанной точки и определяю оптимальный план данной задачи.
При нахождении решения задачи могут встретиться случаи, изображенные на рис. 5.1-5.4. Рис. 5.1 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке А. Из рис. 5.2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ. На рис. 5.3 изображен случай, когда целевая функция не ограничена сверху на множестве допустимых решений, а на рис. 5.4 - случай, когда система ограничений задачи несовместна.
Oтметим, что нахождение минимального значения линейной функции при данной системе ограничений отличается от нахождения ее максимального значения при тex же ограничениях лишь тем, что линия уровня c1x1+c2x2=h передвигается не в направлении вектора С, а в противоположном направлении.
|
|
|
Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении ее минимального значения.
Тот факт, что оптимальное решение находится в одной из вершин многоугольника ОДР, позволяет сделать еще два важных вывода:
À если оптимальным решением являются координаты вершины многоугольника ОДР, значит, сколько вершин имеет ОДР, столько существует целевых функций и столько оптимальных решений по этим функциям может иметь задача.
Á поскольку, чем больше ограничений имеет задача, тем больше вершин, тo, следовательно, чем больше целевых функций и, следовательно, тем больше оптимальных решений по этим функциям.
Из рисунков можно сделать вывод, что вершина, координаты которой являются оптимальным решением, определяются углом наклона прямой, описывающей целевую функцию. Значит, каждая вершина будет соответствовать оптимальному решению для некоторой целевой функции. Итак, нахождение решения задачи линейного программирования (5.8)-(5.10) на основе ее геометрической интерпретации включает следующие этапы.
этапы нахождения решения задачи линейного программирования:
À Строят прямые, уравнения которых получаются в результате замены в ограничениях (5.9) и (5.10) знаков неравенств на знаки точных равенств.
Á Находят полуплоскости, определяемые каждым из ограничений задачи.
 Находят многоугольник решений (ОДР).
à Строят вектор C=(с1; с2).
Ä Строят прямую c1x1+c2x2=h, проходящую через многоугольник решений.
Å Передвигают прямую c1x1+c2x2=h в направлении вектора С, в результате чего-либо находят точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность сверху функции на множестве планов.
Æ Определяют координаты точки максимума функции и вычисляют значение целевой функции в этой точке.
5.3. Графическое решение задачи распределения ресурсов
Пусть для двух видов продукции П1 и П2 требуются трудовые, материальные и финансовые ресурсы. Наличие ресурсов каждого вида и их нормы расхода, необходимые для выпуска единицы продукции, приведены в табл. 5.1.
Таблица 5.1
Характеристика | Вид продукции | располаг. | |
П1 | П2 | ресурс | |
Резервы: | |||
трудовые | 1 | 4 | 14 |
материальные | 3 | 4 | 18 |
финансовые | 6 | 2 | 27 |
выпуск | 1 | 1 | --- |
прибыль | 4 | 8,5 | --- |
план | х1 | х2 | --- |
ìx1+4x2 £ 14
ï3x1+4x2 £ 18
(5.11) í6x1+2x2 £ 27
îx1 ³ 0, x2 ³ 0.
|
ìx1/14+x2/7/2 £ 1
ïx1/6+x2/9/2 £ 1
(5.12) íx1/9/2+x2/27/2 £ 1
îx1 ³ 0, x2 ³ 0.
Если мы хотим найти оптимальное решение, то должны принять целевую функцию. Допустим, мы хотим, чтобы решение было оптимальным в смысле максимизации суммарного выпуска. Тогда целевая функция:
F=x1+x2 ® max (5.13)
Эту зависимость представим в виде x2= F-x1. Из графика данного уравнения (Рис. 5.1) следует, что tga = -1, при этом a =135о, а величина F равна отрезку, отсекаемому прямой функции цели на оси координат. Если прямую перемещать параллельно самой себе в направлении, указанном стрелками, то эта величина будет возрастать. Очевидно, что оптимальным решением будут координаты точки С (x*1; x*2). При этом F=F*.
На основании рассмотренного, можно сделать исключительно важный вывод: оптимальным решением являются координаты вершин ОДР. А из этого вывода следует метод решения задачи линейного программирования.
метод решения задачи линейного программирования:
À Найти вершины ОДР, как точки пересечения ограничений.
Á Определить последовательно значения целевой функции в вершинах.
 Вершина, в которой целевая функция приобретает оптимальное значение, является оптимальной вершиной.
à Координаты оптимальной вершины являются оптимальными значениями искомых переменных.
Если направление целевой функции совпадает с направлением одной из сторон, то у задачи будет, по крайней мере, два решения. В таком случае говорят, что задача имеет альтернативные решения. А это значит, что одно и то же оптимальное значение целевой функции может быть получено при различных значениях переменных.
Тот факт, что оптимальное решение находится на вершине ОДР, дает еще два очень важных вывода:
À если оптимальным решением являются координаты вершин ОДР, значит, сколько вершин имеет ОДР, столько оптимальных решений может иметь задача.
Á поскольку чем больше ограничений, тем больше вершин, то, следовательно, чем больше ограничений, тем больше оптимальных решений.
Как видно на Рис. 5.1, вершина, координаты которой являются оптимальным решением, определяется углом наклона прямой, описывающей целевую функцию. Значит, каждая вершина будет соответствовать оптимальному решению для некоторой целевой функции. Поясним это на рассмотренном ранее примере. Раньше мы находили оптимальное решение по максимизации суммарного выпуска F1=x1+x2 ® max. Найдем оптимальные решения еще для четырех целевых функций:
F2=x2 ® max (максимизация выпуска продукции П2)
F3=x1 ® max (максимизация выпуска продукции П1)
F4=4x1+8,5x2 ® max (максимизация прибыли)
F5=(1+3+6)x1 + (4+4+2)x2 = 10х1+10х2 ® max (минимизация используемых ресурсов).
Для каждой целевой функции, так же как и для F1, можно построить линию целевой функции и определить вершину, в которой целевая функция будет иметь оптимальное значение. Результаты решения задачи по пяти целевым функциям сведем в таблицу 5.2, из анализа которой можно сделать вывод: координаты каждой вершины могут быть оптимальным решением в некотором смысле.
Таблица 5.2
Целевая функция | Вершина | x1 | x2 | x1+x2 | Прибыль | Используемый ресурс |
F1=x1+x2 ® max | C | 4 | 1,5 | 5,5 | 28,75 | 55 |
F2=x2 ® max | A | 0 | 3,5 | 3,5 | 29,75 | 35 |
F3=x1 ® max | D | 4,5 | 0 | 4,5 | 18 | 45 |
F4=4x1+8,5x2 ® max | B | 2 | 3 | 5 | 33,5 | 50 |
F5= 10х1+10х2 | 0 | 0 | 0 | 0 | 0 | 0 |
Симплексный метод или метод последовательного улучшения плана является одним из основных методов решения задач ЛП. название симплексный метод берет от слова «симплекс», которым создатель метода Р. Данциг обозначил наложенное на переменные x1, x2 ... xn ограничение x1+x2+ ... +xn=1.
þ В математике симплексом в k-мерном пространстве называется совокупность k+1 вершин.
Так для плоскости при k=2 симплексом будет треугольник; в пространстве при k=3 симплексом будет тетраэдр, имеющий 4 вершины.
С учетом этого понятия аналитический метод решения задачи ЛП называют симплекс-методом. Он основан на алгоритме направленного перебора вершин. Этот алгоритм обеспечивает переход от одной вершины к другой в таком направлении, при котором значение целевой функции от вершины к вершине улучшается.
þ Определение значения целевой функции и переменных в одной вершине считается итерацией.
Число итераций в реальных задачах может измеряться сотнями. Вручную, с помощью симплекс-метода, могут быть решены задачи, содержащие не более 10 итераций. Поэтому в реальных задачах применяют ЭВМ и пакеты прикладных программ (ППП).
Метод решения задач ЛП с помощью симплексных таблиц изложен на конкретном примере. Пусть требуется найти неотрицательное решение системы линейных неравенств:
ì4x1+9x2 £ 56
(5.14) í5x1+3x2 £ 37
î-x1+2x2 £ 2
обращающее в максимум линейную форму:
¦=3x1+4x2 (5.15)
Вначале перейдем от системы неравенств (5.14) к системе уравнений, добавив к левым частям неравенств неотрицательные переменные x3, x4, x5. Мы получим:
ì4x1+9x2+x3+0 . x4+0 . x5=56
(5.16) í5x1+3x2+0 . x3+x4+0 . x5=37
î-x1+2x2+0 . x3+0 . x4+ x5=2
¦= 3x1+4x2+0 . x3+0 . x4+0 . x5 (5.17)
перепишем теперь систему (5.16) в виде системы 0-уравнений:
ì0=56 - (4x1+9x2+1 . x3+0 . x4+0 . x5)
(5.18) í0=37 - (5x1+3x2+0 . x3+1 . x4+0 . x5)
î0=2 - (-x1+2x2+0 . x3+0 . x4+1 . x5)
¦=0 - (-3x1-4x2-0 . x3-0 . x4-0 . x5) (5.19)
заметим, что система (5.18) может быть записана в виде одного векторного равенства:
0=B-(A1x1+A2x2+A3x3+A4x4+A5x5),
где вектор-столбец В имеет своими компонентами свободные члены, а векторы A1, A2, ... , A5 - коэффициенты при соответствующих переменных x1, x2, x3, x4, x5. Иными словами:
56 | 4 | 9 | 1 | 0 | 0 | |||||||||||
В= | 37 | A1= | 5 | A2= | 3 | A3= | 0 | A4= | 1 | A5= | 0 | |||||
2 | -1 | 2 | 0 | 0 | 1 |
Векторы A3, A4, A5 образуют базис. Это означает, что, присвоив х1=0, х2=0, получаем из (5.16) первое базисное решение: x1=0; x2=0; x3=56; x4=37; x5=2.
При этом значение линейной формы ¦=0. На основании (5.18) строим первую симплексную таблицу.
Симплексная таблица строится следующим образом:
В заглавной строке пишем последовательно векторы B, A1, A2, A3, A4 , A5. Слева добавляем колонку «Базисные векторы», рядом с ней колонку «С», в которой поставлены коэффициенты при базисных переменных в линейной форме, в данном случае величины С3, С4, С5. В последней строке, называемой индексной, и обозначаемой через ¦ j-Сj, проставляются числа, равные значению линейной формы, в соответствием с уравнением (j=1, 2, 3, 4, 5). В итоге мы имеем таблицу 5.3.
Таблица 5.3.
Базисные | Коэффициенты | Вектор свободных | 3 | 4 | 0 | 0 | 0 |
векторы | линейной формы С | членов В | A1 | A2 | A3 | A4 | A5 |
A3 | 0 | 56 | 4 | 9 | 1 | 0 | 0 |
A4 | 0 | 37 | 5 | 3 | 0 | 1 | 0 |
A5 | 0 | 2 | -1 | 2 | 0 | 0 | 1 |
Индексная строка ¦ j-Сj | 0 | -3 | -4 | 0 | 0 | 0 |
Т.к. мы решаем задачу на максимум, то из выражения линейной формы видно, что имеет смысл увеличить x1 или x2. Действительно, коэффициенты при этих переменных в скобках отрицательны (а по существу положительны), и если мы положим x1>0 или x2>0, то значение ¦ увеличится. Но эти же коэффициенты с их знаками стоят в индексной строке.
Итак, мы приходим к следующему выводу: наличие в индексной строке отрицательных чисел при решении задачи на максимум свидетельствует о том, что нами оптимальное решение не получено, и то, что от табл. 5.3 надо перейти к следующей.
Переход к новой таблице, т.е. к новой улучшенной программе осуществляем следующим способом: в индексной строке находим наибольшее по абсолютному значению отрицательное (а при задаче на минимум - наибольшее положительное) число. В нашем примере этим числом будет - 4. Найденное число определяет ведущий или ключевой столбец. Затем мы делим свободные члены на положительные элементы ведущего столбца и выбираем из полученных отношений наименьшее. Наименьшее отношение определяет ведущую строку. В данном случае имеем:
Таким образом, ведущей строкой будет строка A5. На пересечении ведущего столбца и ведущей строки стоит разрешающий элемент. В нашем случае - это число 2.
Теперь мы приступаем к составлению второй таблицы или второго плана. Вместо единичного вектора A5 мы в базис вводим вектор A2. Переход к новому базису, как это известно, эквивалентен элементарному преобразованию матрицы, элементами которой служат числа табл. 5.3. А именно: в новой таблице элемент строки, соответствующий элементу ведущей строки прежней таблицы, равен этому элементу ведущей строки, разделенному на разрешающий элемент. чтобы получить любой другой элемент новой симплексной таблицы, нужно от соответствующего элемента прежней таблицы отнять произведение элемента ведущей строки на элемент ведущего столбца, разделенное на разрешающий элемент. Например, элементу 4 (табл. 5.3) будет соответствовать элемент табл. 5.4:
Таким образом, мы переходим ко второй таблице (таблица 5.4). Указанные выше преобразования относятся к столбцам B, A1, A2, A3, A4 , A5.
Таблица 5.4.
Базисные | Коэффициенты | Вектор свободных | 3 | 4 | 0 | 0 | 0 |
векторы | линейной формы С | членов В | A1 | A2 | A3 | A4 | A5 |
A3 | 0 | 47 | 17/2 | 0 | 1 | 0 | -9/2 |
A4 | 0 | 34 | 13/2 | 0 | 0 | 1 | -3/2 |
A5 | 4 | 1 | -1/2 | 1 | 0 | 0 | 1/2 |
Индексная строка ¦ j-Сj | 4 | -5 | 0 | 0 | 0 | 2 |
Итак, разрешающим элементом будет 13/2. Вектор A4 выводим из базиса и вводим вместо него вектор A1. Пересчет коэффициентов осуществляем по указанным выше правилам и получаем таблицу 5.5.
Таблица 5.5
Базисные | Коэффициенты | Вектор свободных | 3 | 4 | 0 | 0 | 0 |
векторы | линейной формы С | членов В | A1 | A2 | A3 | A4 | A5 |
A3 | 0 | 33/13 | 0 | 0 | 1 | -17/13 | -33/13 |
A1 | 3 | 68/13 | 1 | 0 | 0 | 2/13 | -3/13 |
A2 | 4 | 47/13 | 0 | 1 | 0 | 1/13 | 5/13 |
Индексная строка ¦ j-Сj | 392/13 | 0 | 0 | 0 | 10/13 | 11/13 |
x1=68/13; x2=47/13; x3=33/13; x4 = x5 = 0.
5.5. Анализ симплекс-таблиц
Математическая модель является прекрасным средством получения ответов на широкий круг вопросов, возникающих при планировании, проектировании и в ходе управления производством. Так на этапе планирования целесообразно находить варианты плана при различных вариантах номенклатуры, ресурсов, целевых функций и т.д.
При оперативном управлении решается достаточно широкий и важный круг вопросов, которые возникают при ежедневном обеспечении производственного процесса. Мы рассмотрим лишь те вопросы оперативного управления, которые могут быть решены с помощью моделей, уже составленных при планировании. «Что будет, если пять человек из числа трудовых ресурсов отвлекут на другие работы? Что будет, если сырья поставят на 20% меньше? Какую продукцию следует выпускать, если изменились цены?» Рассмотрим, как находить ответы на эти вопросы на конкретном примере.
Допустим, предприятие должно выпускать продукцию четырех видов: П1,П2,П3,П4, используя для этого три вида ресурсов. Располагаемые ресурсы, нормы расходов материалов и прибыль приведены в Таблице 5А.
ТАБЛИЦА 5А
Элемент | Вид продукции | Располагаемый | |||
модели | П1 | П2 | П3 | П4 | ресурс |
Ресурсы: | |||||
трудовые | 1 | 1 | 1 | 1 | 16 |
сырье | 6 | 5 | 4 | 3 | 110 |
оборудование | 4 | 6 | 10 | 13 | 100 |
Прибыль с единицы продукта | 60 | 70 | 120 | 130 | --- |
План | х1 | х2 | х3 | х4 | --- |
ï6x1 + 5x2 + 4x3+ 3x4 £ 110
(5.20) í4x1 + 6x2 + 10x3+ 13x4 £ 100
îxj ³ 0, j ³ 1,4.
F = 60x1 + 70x2 + 120x3 + 130x4 ® max
От системы неравенств (5.20) перейдем к системе уравнений. Для этого, в каждое неравенство добавим по одной дополнительной переменной: yi ³ 0, i ³ 1,m. Тогда получим систему уравнений:
ìx1 + x2 + x3+ x4 + y1 =16
ï6x1 + 5x2 + 4x3+ 3x4 + y2 =110
(5.21) í4x1 + 6x2 + 10x3+ 13x4 + y3 =100
îxj ³ 0, j = 1,4; yi ³ 0, i = 1,3.
F = 60x1 + 70x2 + 120x3 + 130x4 ® max
Затем перепишем систему (5.21) в следующем виде:
ì y1 =16 - (x1 + x2 + x3+ x4)
ï y2 =110 - (6x1 + 5x2 + 4x3+ 3x4)
(5.22) í y3 =100 - (4x1 + 6x2 + 10x3+ 13x4)
î F = 0 - (-60x1 - 70x2 - 120x3 - 130x4)
Систему (5.22) можно представить в виде Таблицы 5В, которую составляют следующим образом: свободные переменные, заключенные в скобки, выносят в верхнюю строку таблицы. В остальные столбцы записывают свободные члены и коэффициенты перед свободными переменными. Эта, так называемая симплекс таблица, служит основой для решения задач линейного программирования. В этой таблице переменные, являющиеся свободными, в данном случае x1, x2, x3, x4 по условию равны 0. Поскольку свободные переменные равны 0, то из системы (5.22) видно, что базисные переменные y1, y2, y3, а также целевая функция F, которую записывают снизу, равны свободным членам. Значит y1=16, y2=110, y3=100, F=0.
ТАБЛИЦА 5В
Величина | Свободный | Свободные переменные | |||
член | х1 | х2 | х3 | х4 | |
Базисные переменные: | |||||
y1 | 16 | 1 | 1 | 1 | 1 |
y2 | 110 | 6 | 5 | 4 | 3 |
y3 | 100 | 4 | 6 | 10 | 13 |
Индексная строка (F) | 0 | - 60 | - 70 | - 120 | - 130 |
þ Свободными переменными будем называть такие, которые равны 0.
Из теории известно, что n переменных в допустимом решении должны быть равны 0 , т.е. столько же переменных, сколько и основных. Однако, из этого ни в коей мере не следует, что нулю равны все основные переменные. Если из общего числа переменных N=n+m будут свободными n переменных, то очевидно, что m переменных будут базисными, т.е. не равны нулю. С учетом введенных терминов можно сказать, что целью решения задачи ЛП является нахождение базисных и свободных переменных.
Для задачи ЛП, записанной в виде симплекс таблицы, можно сформулировать признаки допустимого и оптимального решений. Решение является допустимым, если в симплекс таблице в столбце свободных членов все значения, относящиеся к базисным переменным будут неотрицательными. Оптимальное значение, как мы знаем, может либо минимизировать, либо максимизировать значение целевой функции. В связи с этим, для оптимальных значений есть два признака: один для случая минимизации целевой функции, другой - для случая максимизации.
Целевая функция имеет минимальное значение, если, во-первых, решение является допустимым, т.е. свободные члены будут неотрицательными, а во=вторых, все элементы в строке целевой функции (свободный член не рассматривается) будут неположительными. При этом целевая функция равна свободному члену. Таким образом можно сделать вывод, что в Табл. 5В получено оптимальное решение нашей задачи для случая минимизации целевой функции.
Действительно, если x1= x2= x3= x4 = 0 мы никакой продукции не выпускаем и при этом прибыль F=0. Дополнительные переменные y1, y2, y3, показывающие объем неиспользованных ресурсов, равны, соответственно: 16, 110,100, т.е. тому ресурсу, который имеется в наличии. В самом деле, мы ничего не выпускаем, но не тратим ресурсы. Следовательно, данные в Табл. 5В соответствуют такой вершине ОДР, в которой целевая функция принимает минимальное значение.
Признак максимизации целевой функции формируется следующим образом: целевая функция имеет максимальное значение, если, во-первых, решение является допустимым, а во-вторых, все элементы в строке целевой функции (свободный член не рассматривается) будут неотрицательными.
Поскольку Табл. 5В не удовлетворяет данному признаку, то необходимо перейти к другой вершине ОДР. Переход от одной вершины к другой, производится по определенному алгоритму симплекс-метода, который заключается в обмене переменных.
þ Каждый переход от одной вершины к другой, который называется итерацией, состоит в том, что одна базисная переменная приравнивается к нулю, т.е. переходит в свободную, а одна свободная переменная переводится в базисную.
На каждой итерации проверяют удовлетворение признаков допустимого и оптимального решений. Такая процедура продолжается до тех пор, пока не будут удовлетворены оба признака. Применительно к нашей задаче переходим к следующей симплекс-таблице, полученной после первой итерации.
Переход к новой таблице осуществляем следующим способом: в индексной строке, где находится целевая функция находим наибольшее по абсолютному значению отрицательное число. Найденное число определяет ведущий столбец. Затем мы делим свободные члены на положительные элементы ведущего столбца и выбираем из полученных отношений наименьшее. Наименьшее отношение определяет ведущую строку. В нашем случае имеем:
Таким образом, ведущим столбцом будет столбец х3, а ведущей строкой будет строка y3. На пересечении ведущего столбца и ведущей строки будет разрешающий элемент. В нашем случае это число 10. Таким образом, ведущей строкой будет строка y3, обозначим ее через Ar. Ведущим столбцом будет столбец х4, обозначим его через Ak, и, следовательно, разрешающий элемент Ark = 10.
Теперь приступаем к составлению второй таблицы. В этой таблице элементы направляющей строки равны этому элементу ведущей строки, деленному на разрешающий элемент, и находятся в соотношении:
Элементы любой другой строки j находят из соотношения:
Т.е. чтобы получить любой другой элемент новой симплексной таблицы, нужно от соответствующего элемента прежней таблицы отнять произведение элемента ведущей строки на элемент ведущего столбца, разделенное на разрешающий элемент.
После этих преобразований новая симплексная таблица после первой итерации примет вид Таблицы 5С.
ТАБЛИЦА 5С
Величина | Свободный | Свободные переменные | |||
член | х1 | х2 | х3 | х4 | |
Базисные переменные: | |||||
¬ y1 | 6 | 0,6 | 0,4 | 0 | - 0,3 |
y2 | 70 | 4,4 | 2,6 | 0 | - 2,2 |
¬ y3 | 10 | 0,4 | 0,6 | 1 | 1,3 |
Индексная строка (F) | 1200 | - 12 | 2 | 0 | 26 |
Т. о. Ведущей строкой будет y1, а разрешающим элементом число 0,6.
Применительно к нашей задаче последняя симплекс-таблица, полученная после второй итерации, будет иметь вид:
ТАБЛИЦА 5D
Величина | Свободный | Свободные переменные | |||
член | х1 | х2 | х3 | х4 | |
Базисные переменные: | |||||
х1 | 10 | 5/3 | 2/3 | - 1/6 | - 1/2 |
y2 | 26 | -22/3 | - 1/3 | 1/3 | 0 |
х3 | 6 | - 2/3 | 1/3 | 1/6 | 3/2 |
Индексная строка (F) | 1320 | 20 | 10 | 10 | 20 |
Вот результат решения задачи. Однако, с помощью симплекс-таблицы можно узнать еще много полезных сведений. Так их этой же таблицы видим, что свободные переменные y1=y3=0, а базисная переменная y2=26. А это значит, что в оптимальном плане резервы трудовых ресурсов и оборудования равны нулю. Иными словами, эти ресурсы используются полностью. Вместе с тем резерв ресурсов сырья y2=26, что свидетельствует о том, что имеются излишки сырья. Вот какие полезные сведения можно получить из окончательной симплекс-таблицы.
5.6. Решение транспортных задач
В качестве примера приведем решение транспортной задачи ЛП с помощью таблицы. Транспортная таблица состоит из m строк и n столбцов. В правом верхнем углу каждой клетки будем ставить стоимость Сij перевозки единицы груза из Ai в Bj, а в центр клетки поместим перевозку Xij.
Таблица 5.6
Таблица 5.7
Составим опорный план. Можно применить метод «северо-западного угля». Пусть пункт В1 подал заявки на 18 единиц груза. Удовлетворим ее из запасов А1. После этого в нем остается еще 30-18=12 единиц груза. Отдадим их пункту В2. Но заявка этого пункта еще не удовлетворена. Выделим остаток 27-12 из запасов А2 и т.д. рассуждая аналогичным образом, составим таблицу 5.8. Полученный план перевозок является опорным, но вряд ли он является оптимальным в смысле стоимости перевозок.
þ Напомним, что прямая, которая имеет с областью, по крайней мере, одну общую точку, притом так, что вся область лежит по одну сторону от этой прямой, называется опорной по отношению к этой области.
Таким образом, задача ЛП на геометрическом языке может быть сформулирована так: среди прямых уровня функции цели ¦ найти опорную по отношению к ОДР и притом так, чтобы вся область лежала со стороны больших значений ¦. Наш план - не оптимальный. Сразу видно, что его можно улучшить, если произвести в нем «циклическую перестановку», уменьшив перевозки в «дорогой» клетке (2.3) со стоимостью 12. но зато, увеличив перевозки в «дешевой» клетке (2.4) со стоимостью 6. чтобы план оставался опорным, мы должны при этом сделать одну из свободных клеток базисной, а одну из базисных - свободной.
Сколько единиц груза можем мы перенести по циклу следующему циклу: (2.4) ®(3.4) ®(3.3) ®(2.3), увеличивая перевозки в нечетных вершинах цикла и уменьшая в четных? Очевидно, не больше 11 единиц (иначе перевозки в клетке (3.4) стали бы отрицательными). Также очевидно, что в результате циклического переноса допустимый план остается допустимым - баланс заявок и запасов не нарушается. Произведем перенос и запишем улучшенный план в таблицу 5.8.
таблица 5.8
Таблица 5.9
посмотрим, что мы сэкономили. Общая стоимость плана в табл. 5.7 равна:
‡1=18´13+12´7+15´8+33´12+9´10+11´8+15´10+15´15=1287.
Общая стоимость плана табл. 5.6 равна:
‡2=18´13+12´7+15´8+22´12+11´6+20´10+15´10+15´15=1243.
Таким образом, нам удалось уменьшить стоимость перевозок на 44 единицы.
Действительно алгебраическая сумма стоимостей, стоящих в вершинах цикла со знаком «+», если перевозки в этой вершине увеличиваются, и со знаком «-», если уменьшаются (так называемая «цена цикла»). в данном случае равна 6-8+10-12=-4. Значит, при переносе одной величины груза по этому циклу стоимость уменьшается на 4. А мы перенесем 11 единиц. Следовательно, цена цикла 4 . 11=44.
Попробуем еще раз улучшить план табл. 5.8 с помощью цикла (табл. 5.9) с ценой: 5-15+14-13=9. Перебрасывая 15 единиц груза, сокращаем стоимость на: 9 . 15=135.
6. МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
И МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ
6.1. Постановка задачи нелинейного программирования
В общем виде задача нелинейного программирования (ЗНП) формируется следующим образом:
f (x1, x2, ..., xn) ® max (min) (6.1)
ì gi (x1, x2 ..., xn £ bi, i=1, m1
ï gi (x1, x2 ..., xn ³ bi, i=m1+1, m2
(6.2) í ... ... ... ... ... ... ... ... ... ... ...
î gi (x1, x2 ..., xn = bi, i=m2+1, m2
где xj - управляющие переменные или решения ЗНП, j=1, n;
bi - фиксированные параметры, i=1, m;
f, gi, i=1, n - заданные функции от n переменных.
Если f и gi линейны, то (6.1), (6.2) проходит в задачу линейного программирования.
þ Решить задачу нелинейного программирования - это значит найти такие значения управляющих переменных xj, j=1, n, которые удовлетворяют системе ограничений (6.2) и доставляют максимум или минимум функции f.
Для задачи нелинейного программирования, в отличие от линейных задач, нет единого решения. В зависимости от вида целевой функции (6.1) и ограничений (6.2) разработано несколько специальных методов решения, к которым относятся методы множителей Лагранжа, квадратичное и выпуклое программирование, градиентные методы, ряд приближенных методов решения, графический метод. Заметим, что нелинейное моделирование экономических задач часто бывает довольно искусственным. Большая часть экономических проблем сводится к линейным моделям.
6.2. Постановка задачи динамического программирования.
Основные условия и область применения.
В ряде реальных экономических и производственных задач необходимо учитывать изменение моделируемого процесса во времени и влияние времени на критерий оптимальности. Для решения указанных задач используется метод динамического планирования (программирования). Этот метод более сложен по сравнению с методами расчета статических оптимизационных задач. Также не простым делом является процесс построения для реальной задачи математической модели динамическою программирования.
Пусть рассматривается задача, распадающаяся на m шагов или этапов, например планирование деятельности предприятия на несколько лет, поэтапное планирование инвестиций, управление производственными мощностями в течение длительного срока. Показатель эффективности задачи в целом обозначим через W, а показатели эффективности на отдельных шагах - через ji, i=1, m. Если W обладает свойством аддитивности, т.е.:
(6.3)
можно найти оптимальное решение задачи методом динамического программирования.
þ Таким образом, динамическое программирование - это метод оптимизации многошаговых или многоэтапных процессов, критерий эффективности которых обладает свойством (6.3).
þ В задачах динамического программирования критерий эффективности называется выигрышем. Данные процессы управляемые, и от правильного выбора управления зависит величина выигрыша.
þ Переменная хi, от которой зависят выигрыш на i-м шаге и, следовательно, выигрыш в целом, называются шаговым управлением i=1, m.
þ Управлением процесса в целом (х) называется последовательность шаговых управлений х=(х1, х2, ..., хi, ..., хm).
þ Оптимальное управление х* - это значение управления х, при котором значение W(x*) является максимальным (или минимальным, если требуется уменьшить проигрыш)
W*=W(x*)=max {W(x)}
xÎX, (6.4)
где X - область допустимых управлений.
Oптимальное управление x* определяется последовательностью оптимальных шаговых управлений: x* = (x1*, x2*, ..., xi*, ..., xm*).
þ В основе метода динамического программирования лежит принцип оптимальности Беллмана, формулирующийся следующим образом: управление на каждом шаге надо выбирать так, чтобы оптимальной была сумма выигрышей на всех оставшихся до конца процесса шагах, включая выигрыш на данном шаге.
Поясним это правило. При решении задач динамического программирования на каждом шаге выбирается управление, которое должно привести к оптимальному выигрышу. если считать все шаги независимыми друг от друга, то оптимальным шаговым управлением будет то управление, которое приносит максимальный выигрыш именно на данном шаге. Но, например, при покупке новой техники взамен устаревшей, на ее приобретение затрачиваются определенные средства. Поэтому прибыль от ее эксплуатации вначале может быть небольшой. Однако в следующие годы новая техника будет приносить большую прибыль. И наоборот, если руководитель примет решение оставить старую технику для получения прибыли в текущем году, то в дальнейшем это приведет к значительным убыткам. Данный пример демонстрирует следующий факт: в многошаговых процессах все шаги зависят друг от друга, и, следовательно, управление на каждом конкретном шаге надо выбирать, с учетом его будущих воздействий на весь процесс.
Другой момент, который следует учитывать при выборе управления на данном шаге, - это возможные варианты окончания предыдущего шага. Эти варианты определяют состояние процесса. Например, при определении количества средств в i-ом году, необходимо знать, сколько средств осталось в наличии к этому году, и какая прибыль получена в предыдущем (i-1)-ом году.
Таким образом, при выборе шагового управления необходимо учитывать:
À возможные исходы предыдущего шага.
Á влияние управления на все оставшиеся до конца процесса шаги.
В задачах динамическою программирования первый пункт учитывают, делая на каждом шаге условные предположения о возможных вариантах окончания предыдущего шага, и проводя для каждого из вариантов условную оптимизацию. Выполнение второго пункта обеспечивается тем, что в задачах динамического программирования условная оптимизация проводится от конца процесса к началу. Сперва оптимизируется последний m-й шаг, на котором не надо учитывать возможные воздействия выбранного управления хm, на все последующие шаги, так как эти шаги просто отсутствуют. Делая предположения об условиях окончания (m-1)-го шага, для каждого из них проводят условную оптимизацию m-го шага и определяют условное оптимальное управление хm. Аналогично поступают для (m-1)-го шага, делая предположение об исходах окончания (m-2)-го шага, и, определяя условное оптимальное управление на (m-1)-ом шаге, приносящее оптимальный выигрыш на двух последних шагах - (m-1)-ом и m-ом. Так же действуют на всех остальных шагах до первого. На первом шаге, как правило, не надо делать условных предположений, т.к. состояние системы перед первым шагом обычно известно. Для этого состояния выбирают оптимальное шаговое управление, обеспечивающее оптимальный выигрыш на первом и всех последующих шагах. Это управление является, безусловно, оптимальным управлением на первом шаге и, зная его, определяются оптимальное значение выигрыша и безусловные оптимальные управления на всех ее шагах.
6.3. Многокритериальная оптимизация
þ задачи, в которых оптимизацию проводят по нескольким параметрам, называют задачами многокритериальной или векторной оптимизации.
Как и при линейном программировании задачи многокритериальной оптимизации включают в себя три основные части.
три основные части задачи многокритериальной оптимизации:
À целевую функцию,
Á ограничения,
 граничные условия.
Наиболее часто целевая функция представляется обобщенными показателями эффективности, которые представляют собой взвешенную сумму частных показателей, в которую каждый из них входит с определенным весом, отражающим его важность:
W= a1 .w1 + a2 .w2 + ... + an .wn
Для тex показателей, которые желательно увеличить, веса берутся положительные, а для тex, которые желательно уменьшить - отрицательные.
Назначение коэффициентов весов проводят с помощью экспертных оценок. Методы экспертных оценок достаточно широко распространены. Математических методов определения экспертных оценок достаточно много. Рассмотрим некоторые из них.
Математические методы определения экспертных оценок:
À Непосредственное назначение коэффициентов весов.
Согласно этому методу каждый i-й эксперт для каждого k-ого параметра должен назначить коэффициент веса aik таким образом, чтобы сумма коэффициентов веса, назначенная одним экспертом для различных параметров, равнялась 1.
i=1, n, где n - число экспертов.
В качестве коэффициента веса k-ого параметра ak принимают среднее значение по результатам экспертизы всех экспертов:
Á Oценка важности параметров в баллах. В этом случае каждый эксперт назначает каждому параметру оценку по десяти бальной системе. Наиболее важный параметр оценивается более высоким баллом. В результате экспертизы заполняется таблица, и находятся коэффициенты веса.
В качестве примера приведем решение транспортной задачи ЛП с помощью таблицы. Транспортная таблица состоит из m строк и n столбцов. В правом верхнем углу каждой клетки будем ставить стоимость Сij перевозки единицы груза из Ai в Bj, а в центр клетки поместим перевозку Xij.
Таблица 5.6
ПН | В1 | В2 | В3 | В4 | В5 | Запасы аi | |
ПО | |||||||
A1 | 13 | 7 | 14 | 7 | 5 | 30 | |
A2 | 11 | 8 | 12 | 6 | 8 | 48 | |
A3 | 6 | 10 | 10 | 8 | 11 | 20 | |
A4 | 14 | 8 | 10 | 10 | 15 | 30 | |
Заявки bj | 18 | 27 | 42 | 26 | 15 | 128 |
ПН | В1 | В2 | В3 | В4 | В5 | Запасы аi | |
ПО | |||||||
A1 | 18 13 | 12 7 | 14 | 7 | 5 | 30 | |
A2 | 11 | 15 8 | 33 12 | 6 | 8 | 48 | |
A3 | 6 | 10 | 9 10 | 11 8 | 11 | 20 | |
A4 | 14 | 8 | 10 | 15 10 | 15 15 | 30 | |
Заявки bj | 18 | 27 | 42 | 26 | 15 | 128 |
þ Напомним, что прямая, которая имеет с областью, по крайней мере, одну общую точку, притом так, что вся область лежит по одну сторону от этой прямой, называется опорной по отношению к этой области.
Таким образом, задача ЛП на геометрическом языке может быть сформулирована так: среди прямых уровня функции цели ¦ найти опорную по отношению к ОДР и притом так, чтобы вся область лежала со стороны больших значений ¦. Наш план - не оптимальный. Сразу видно, что его можно улучшить, если произвести в нем «циклическую перестановку», уменьшив перевозки в «дорогой» клетке (2.3) со стоимостью 12. но зато, увеличив перевозки в «дешевой» клетке (2.4) со стоимостью 6. чтобы план оставался опорным, мы должны при этом сделать одну из свободных клеток базисной, а одну из базисных - свободной.
Сколько единиц груза можем мы перенести по циклу следующему циклу: (2.4) ®(3.4) ®(3.3) ®(2.3), увеличивая перевозки в нечетных вершинах цикла и уменьшая в четных? Очевидно, не больше 11 единиц (иначе перевозки в клетке (3.4) стали бы отрицательными). Также очевидно, что в результате циклического переноса допустимый план остается допустимым - баланс заявок и запасов не нарушается. Произведем перенос и запишем улучшенный план в таблицу 5.8.
таблица 5.8
ПН | В1 | В2 | В3 | В4 | В5 | Запасы аi | |
ПО | |||||||
A1 | 18 13 | 12 7 | 14 | 7 | 5 | 30 | |
A2 | 11 | 15 8 | 33 12 | 11 6 | 8 | 48 | |
A3 | 6 | 10 | 20 10 | 8 | 11 | 20 | |
A4 | 14 | 8 | 10 | 15 10 | 15 15 | 30 | |
Заявки bj | 18 | 27 | 42 | 26 | 15 | 128 |
ПН | В1 | В2 | В3 | В4 | В5 | Запасы аi | |
ПО | |||||||
A1 | - 3 13 | 12 7 | 14 | 7 | +15 5 | 30 | |
A2 | 11 | 15 8 | 22 12 | 11 6 | 8 | 48 | |
A3 | 6 | 10 | 20 10 | 8 | 11 | 20 | |
A4 | +15 14 | 8 | 10 | 15 10 | - 15 | 30 | |
Заявки bj | 18 | 27 | 42 | 26 | 15 | 128 |
‡1=18´13+12´7+15´8+33´12+9´10+11´8+15´10+15´15=1287.
Общая стоимость плана табл. 5.6 равна:
‡2=18´13+12´7+15´8+22´12+11´6+20´10+15´10+15´15=1243.
Таким образом, нам удалось уменьшить стоимость перевозок на 44 единицы.
Действительно алгебраическая сумма стоимостей, стоящих в вершинах цикла со знаком «+», если перевозки в этой вершине увеличиваются, и со знаком «-», если уменьшаются (так называемая «цена цикла»). в данном случае равна 6-8+10-12=-4. Значит, при переносе одной величины груза по этому циклу стоимость уменьшается на 4. А мы перенесем 11 единиц. Следовательно, цена цикла 4 . 11=44.
Попробуем еще раз улучшить план табл. 5.8 с помощью цикла (табл. 5.9) с ценой: 5-15+14-13=9. Перебрасывая 15 единиц груза, сокращаем стоимость на: 9 . 15=135.
6. МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
И МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ
6.1. Постановка задачи нелинейного программирования
В общем виде задача нелинейного программирования (ЗНП) формируется следующим образом:
f (x1, x2, ..., xn) ® max (min) (6.1)
ì gi (x1, x2 ..., xn £ bi, i=1, m1
ï gi (x1, x2 ..., xn ³ bi, i=m1+1, m2
(6.2) í ... ... ... ... ... ... ... ... ... ... ...
î gi (x1, x2 ..., xn = bi, i=m2+1, m2
где xj - управляющие переменные или решения ЗНП, j=1, n;
bi - фиксированные параметры, i=1, m;
f, gi, i=1, n - заданные функции от n переменных.
Если f и gi линейны, то (6.1), (6.2) проходит в задачу линейного программирования.
þ Решить задачу нелинейного программирования - это значит найти такие значения управляющих переменных xj, j=1, n, которые удовлетворяют системе ограничений (6.2) и доставляют максимум или минимум функции f.
Для задачи нелинейного программирования, в отличие от линейных задач, нет единого решения. В зависимости от вида целевой функции (6.1) и ограничений (6.2) разработано несколько специальных методов решения, к которым относятся методы множителей Лагранжа, квадратичное и выпуклое программирование, градиентные методы, ряд приближенных методов решения, графический метод. Заметим, что нелинейное моделирование экономических задач часто бывает довольно искусственным. Большая часть экономических проблем сводится к линейным моделям.
6.2. Постановка задачи динамического программирования.
Основные условия и область применения.
В ряде реальных экономических и производственных задач необходимо учитывать изменение моделируемого процесса во времени и влияние времени на критерий оптимальности. Для решения указанных задач используется метод динамического планирования (программирования). Этот метод более сложен по сравнению с методами расчета статических оптимизационных задач. Также не простым делом является процесс построения для реальной задачи математической модели динамическою программирования.
Пусть рассматривается задача, распадающаяся на m шагов или этапов, например планирование деятельности предприятия на несколько лет, поэтапное планирование инвестиций, управление производственными мощностями в течение длительного срока. Показатель эффективности задачи в целом обозначим через W, а показатели эффективности на отдельных шагах - через ji, i=1, m. Если W обладает свойством аддитивности, т.е.:
можно найти оптимальное решение задачи методом динамического программирования.
þ Таким образом, динамическое программирование - это метод оптимизации многошаговых или многоэтапных процессов, критерий эффективности которых обладает свойством (6.3).
þ В задачах динамического программирования критерий эффективности называется выигрышем. Данные процессы управляемые, и от правильного выбора управления зависит величина выигрыша.
þ Переменная хi, от которой зависят выигрыш на i-м шаге и, следовательно, выигрыш в целом, называются шаговым управлением i=1, m.
þ Управлением процесса в целом (х) называется последовательность шаговых управлений х=(х1, х2, ..., хi, ..., хm).
þ Оптимальное управление х* - это значение управления х, при котором значение W(x*) является максимальным (или минимальным, если требуется уменьшить проигрыш)
W*=W(x*)=max {W(x)}
xÎX, (6.4)
где X - область допустимых управлений.
Oптимальное управление x* определяется последовательностью оптимальных шаговых управлений: x* = (x1*, x2*, ..., xi*, ..., xm*).
þ В основе метода динамического программирования лежит принцип оптимальности Беллмана, формулирующийся следующим образом: управление на каждом шаге надо выбирать так, чтобы оптимальной была сумма выигрышей на всех оставшихся до конца процесса шагах, включая выигрыш на данном шаге.
Поясним это правило. При решении задач динамического программирования на каждом шаге выбирается управление, которое должно привести к оптимальному выигрышу. если считать все шаги независимыми друг от друга, то оптимальным шаговым управлением будет то управление, которое приносит максимальный выигрыш именно на данном шаге. Но, например, при покупке новой техники взамен устаревшей, на ее приобретение затрачиваются определенные средства. Поэтому прибыль от ее эксплуатации вначале может быть небольшой. Однако в следующие годы новая техника будет приносить большую прибыль. И наоборот, если руководитель примет решение оставить старую технику для получения прибыли в текущем году, то в дальнейшем это приведет к значительным убыткам. Данный пример демонстрирует следующий факт: в многошаговых процессах все шаги зависят друг от друга, и, следовательно, управление на каждом конкретном шаге надо выбирать, с учетом его будущих воздействий на весь процесс.
Другой момент, который следует учитывать при выборе управления на данном шаге, - это возможные варианты окончания предыдущего шага. Эти варианты определяют состояние процесса. Например, при определении количества средств в i-ом году, необходимо знать, сколько средств осталось в наличии к этому году, и какая прибыль получена в предыдущем (i-1)-ом году.
Таким образом, при выборе шагового управления необходимо учитывать:
À возможные исходы предыдущего шага.
Á влияние управления на все оставшиеся до конца процесса шаги.
В задачах динамическою программирования первый пункт учитывают, делая на каждом шаге условные предположения о возможных вариантах окончания предыдущего шага, и проводя для каждого из вариантов условную оптимизацию. Выполнение второго пункта обеспечивается тем, что в задачах динамического программирования условная оптимизация проводится от конца процесса к началу. Сперва оптимизируется последний m-й шаг, на котором не надо учитывать возможные воздействия выбранного управления хm, на все последующие шаги, так как эти шаги просто отсутствуют. Делая предположения об условиях окончания (m-1)-го шага, для каждого из них проводят условную оптимизацию m-го шага и определяют условное оптимальное управление хm. Аналогично поступают для (m-1)-го шага, делая предположение об исходах окончания (m-2)-го шага, и, определяя условное оптимальное управление на (m-1)-ом шаге, приносящее оптимальный выигрыш на двух последних шагах - (m-1)-ом и m-ом. Так же действуют на всех остальных шагах до первого. На первом шаге, как правило, не надо делать условных предположений, т.к. состояние системы перед первым шагом обычно известно. Для этого состояния выбирают оптимальное шаговое управление, обеспечивающее оптимальный выигрыш на первом и всех последующих шагах. Это управление является, безусловно, оптимальным управлением на первом шаге и, зная его, определяются оптимальное значение выигрыша и безусловные оптимальные управления на всех ее шагах.
6.3. Многокритериальная оптимизация
þ задачи, в которых оптимизацию проводят по нескольким параметрам, называют задачами многокритериальной или векторной оптимизации.
Как и при линейном программировании задачи многокритериальной оптимизации включают в себя три основные части.
три основные части задачи многокритериальной оптимизации:
À целевую функцию,
Á ограничения,
 граничные условия.
Наиболее часто целевая функция представляется обобщенными показателями эффективности, которые представляют собой взвешенную сумму частных показателей, в которую каждый из них входит с определенным весом, отражающим его важность:
W= a1 .w1 + a2 .w2 + ... + an .wn
Для тex показателей, которые желательно увеличить, веса берутся положительные, а для тex, которые желательно уменьшить - отрицательные.
Назначение коэффициентов весов проводят с помощью экспертных оценок. Методы экспертных оценок достаточно широко распространены. Математических методов определения экспертных оценок достаточно много. Рассмотрим некоторые из них.
Математические методы определения экспертных оценок:
À Непосредственное назначение коэффициентов весов.
Согласно этому методу каждый i-й эксперт для каждого k-ого параметра должен назначить коэффициент веса aik таким образом, чтобы сумма коэффициентов веса, назначенная одним экспертом для различных параметров, равнялась 1.
i=1, n, где n - число экспертов.
В качестве коэффициента веса k-ого параметра ak принимают среднее значение по результатам экспертизы всех экспертов:
Á Oценка важности параметров в баллах. В этом случае каждый эксперт назначает каждому параметру оценку по десяти бальной системе. Наиболее важный параметр оценивается более высоким баллом. В результате экспертизы заполняется таблица, и находятся коэффициенты веса.