Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Моделирование экономических систем.





ЛЕКЦИИ

 

По дисциплине:

 

МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ

ПРЕПОДАВАТЕЛЬ Тимакин О.А.

 

 

Ростов-на-Дону 2012

СОДЕРЖАНИЕ

 

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. Многокритериальная оптимизация

 

Моделирование экономических систем.

Основные понятия и определения.

 

Возникновение и развитие системных представлений

 

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

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

В различных сферах человеческой деятельности возникли различные подходы и соответствующие методы решения специфических проблем, которые получили различные названия: в военных и экономических вопросах - «исследование операций», в политическом и административном управлении - «системный подход», в философии «диалектический материализм», в прикладных научных исследованиях - «кибернетика». Позже стало ясно, что все эти теоретические и прикладные дисциплины образуют как бы единый поток, «системное движение», которое постепенно оформилось в науку, получившую название «системный анализ». В настоящее время системный анализ является самостоятельной дисциплиной, имеющей свой объект деятельности, свой достаточно мощный арсенал средств и свою прикладную область. Являясь по существу прикладной диалектикой, системный анализ использует все средства современных научных исследований - математику, моделирование, вычислительную технику и натурные эксперименты.

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

 

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

 

 

Виды подобия моделей

 

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

 

þ Прежде всего, это подобие, устанавливаемое в процессе создания модели. Назовем такое подобие прямым. Примером такого подобия являются фотографии, масштабированные модели самолетов, кораблей, макеты зданий, выкройки, куклы и т.д.

 

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

 

þ Второй тип подобия между моделью и оригиналом называется косвенным. Косвенное подобие между оригиналом и моделью объективно существует в природе и обнаруживается в виде достаточной близости или совпадения их абстрактных математических моделей и вследствие этого широко используется в практике реального моделирования. Наиболее характерным примером может служить электромеханическая аналогия между маятником и электрическим контуром.

 

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

 

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

 

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

 

Адекватность моделей

 

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

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

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

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

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

 

Математических моделей

 

Можно выделить следующие основные этапы построения математической модели:

 

À Определение цели, т.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елинейные модели - это модели, в которых либо целевая функция, либо какое-нибудь из ограничений (либо все ограничения) нелинейны по управляющим переменным. Для нелинейных моделей нет единого метода расчета. В зависимости от вида нелинейности, свойств функции и ограничений можно предложить различные способы решения. Однако может случится и так, что для поставленной нелинейной задачи вообще не существует метода расчета. В этом случае задачу следует упростить, либо сведя ее к известным линейным моделям, либо просто линеаризовав модель.

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

þ Графические модели - используются тогда, когда задачу удобно представить в виде графической структуры.

Выпуклые множества

 

Предварительно дадим некоторые понятия, весьма важные для линейного программирования.

 

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

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

þ выпуклой линейной комбинацией точек М1, М2, ... Мn называется любая точка М такая, что:

 

М=a1M1+a2M2 + ... +anMn,

 

где ai ³ 0 и a1+a2+ ... +an=1.

 

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

 

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

 

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

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

 

Линейные неравенства

 

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

Для начала рассмотрим неравенство с одной переменной величиной x1, например x1<4. Если на плоскости провести прямую х1=4, то она разделит всю плоскость на две части - полуплоскости: в одной из них, а именно слева от прямой х1=4, лежат точки, абсциссы которых меньше 4, а справа от прямой - точки, абсциссы которых больше 4. Таким образом, неравенство x1<4 геометрически определяет полуплоскость (Рис.1). Рассмотрим теперь неравенство с двумя переменными типа 1+4х2 < 12. Построим прямую линию 1+4х2=12. Разделим обе части уравнения на 12:

 

 

 

из которого видно, что прямая отсекает по осям отрезки, равные 4 и 3.

Неравенство 1+4х2 < 12 определяет собой совокупность всех точек плоскости, лежащих ниже прямой, т.е. в заштрихованной части (Рис. 2).

 

Чтобы легче было понять, какую именно полуплоскость определяет то или иное неравенство, мы в левую часть неравенства подставим координаты начала координат, т.е. х1=0 и х2=0. Если неравенство удовлетворяется, то оно определяет ту полуплоскость, в которой лежит начало координат, в противном случае - другую полуплоскость. Пользуясь геометрическими соображениями, найти возможные решения системы:

 

ì3х1+4х2 £ 12

íx1< 2

îх1 > 0 и х2 > 0

 

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

Полученный многоугольник является выпуклым, ибо вместе с любыми двумя точками содержит весь соединяющий их отрезок. таким образом, мы видим, что выпуклый многоугольник можно задать аналитически, с помощью системы линейных неравенств. Линейное уравнение с тремя переменными: a11x1+a12x2+a13x3=b1 определяет в пространстве некоторую плоскость, которая рассекает все пространство на два полупространства.

В связи с этим неравенство a11x1+a12x2+a13x3 £ b1 определяет одно из полупространств, к которому принадлежит также и сама граничная плоскость. В общем случае, когда система неравенств совместна, пространство решений образует некоторый выпуклый многогранник - многогранник решений. Частным случаем его могут быть: отдельная грань, ребро или точка. Последнее имеет место, когда система неравенств имеет одно единственное решение. Дальнейшие обобщения приводят нас к рассмотрению m линейных неравенств с n неизвестными. Каждое уравнение ai1x1+ai2x2+ ... +ainxn=bi является уравнением некоторой гиперплоскости в n-мерном пространстве, которая как бы рассекает все пространство на два полупространства.

 

Транспортная задача

 

уголь, добываемый в нескольких месторождениях, отправляется ряду потребителей. нам известно, сколько угля добывается в каждом из месторождений, скажем за месяц и сколько его требуется на тот же срок каждому из потребителей. Известны расстояния между месторождениями и потребителями, а также условия сообщения между ними. Учитывая эти данные. Можно подсчитать, во что обходится перевозка каждой тонны угля из любого месторождения в любой пункт потребления. Требуется при этих условиях спланировать перевозки угля таким образом, чтобы затраты на них были минимальными.

Пусть для простоты заданы всего 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

 

Общее количество угля, привозимое в пункт П1 из всех месторождений, будет х11+х12+х13+х14+х15 = b1; в другие пункты - П2, П3 и т.д. и примет вид уравнений 4.1. общее количество угля, вывозимое из М1, будет: х11+х12+х13+х14+х15 = a1, примет вид 4.2.предполагаем, что стоимость перевозки прямо пропорциональна количеству перевозимого угля, т.е. стоимость перевозки xij тонн угля равна:

 

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.

 

Графическая интерпретация

МЕТОДЫ РЕШЕНИЯ

Таблица 5.1

 

  Характеристика Вид продукции   располаг.
  П1 П2 ресурс
Резервы:      
трудовые
материальные
финансовые
выпуск ---
прибыль 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 1,5 5,5 28,75
F2=x2 ® max A 3,5 3,5 29,75
F3=x1 ® max D 4,5 4,5
F4=4x1+8,5x2 ® max B 33,5
F5= 10х1+10х2

 

Симплексный метод

 

Симплексный метод или метод последовательного улучшения плана является одним из основных методов решения задач ЛП. название симплексный метод берет от слова «симплекс», которым создатель метода Р. Данциг обозначил наложенное на переменные 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+4x







ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2023 zdamsam.ru Размещенные материалы защищены законодательством РФ.