Системное програмирование

Рис. 3.3. Определение экстремальных значений целевой функции

  Затем для х_Н = 0,25 и х_В = 0,5 определяем минимальное значение F_min(X) = 2. Таким образом построим на графике ряд параллельных прямых, рис. 3.3, где вектор-градиент N(2; 3) показывает направление возрастания целевой функции.

  Максимальное  значение F(Х) будет в точке Е. Так как точка Е получена в результате пересечения прямых (1) и (2), то для определения ее координат решим систему уравнений:

 Þ ; 

Максимальное  значение целевой функции

F_max(Х) = 2х_Н + 3х_В = 2•З'/з + 3•l'/з = 10²/з (тыс. тг.).

   Целевая функция 2х_Н + 3х_В = 10²/з пересекает ось х_В в точке х_В = , а ось х_Н в точке х_Н = 5¹/з.

  Таким образом, суточный объем производства краски для наружных работ должен быть равен 31/з т, а для внутренних работ –11/з т. Доход от продажи в этом случае будет максимальным и составит 10²/з тыс. тг.

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

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

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

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

  Эти результаты могут быть обобщены.

Решить  геометрически следующие задачи:

a) F = 3х₁ + 3х₂ ® max при ограничениях:   б) F = 2х₁ - 3х₂ +1 ® min при ограничениях:

                                                   

,                                                        ,

Решение. а) Геометрическое решение задачи показано на рис. 4.5а, из которого следует, что линия уровня с максимальным уровнем совпадает с граничной линией АВ многоугольника решений ABCD, т.е. с линией х₁ + х₂ = 8. Следовательно, на всем отрезке АВ линейная функция F=3х₁ + 3х₂ принимает одно и то же максимальное значение, равное 3(х₁ + х₂) = 3*8 = 24. Это означает, что задача имеет бесконечно много оптимальных решений (их задают координаты точек отрезка АВ), среди которых базисных оптимальных решений два — соответственно в угловых точках A(3; 5) и В(6; 2). Точки отрезка АВ задаются уравнением х₂ = 8 – x₁,

где 3£ х₁ £6. 

  

                                                         рис. 2.16

  Итак, .F_max = 24 при бесконечном множестве оптимальных решений x₁ = с, х₂ = 8 — с, где 3 £ с £ 6.

   При геометрическом решении подобных задач  важно точно установить, действительно  ли совпадает линия уровня с границей многоугольника решений или это  связано с неточностью построений, мелким масштабом рисунка и т.п. Ответ на этот вопрос будет положительным, если линия уровня и граничная  прямая параллельны, т.е. их коэффициенты при переменных пропорциональны. В  рассматриваемом примере коэффициенты при переменных линии уровня F = 3x₁ + 3х₂ пропорциональны соответствующим коэффициентам граничной прямой х₁ + х₂=6.

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

Итак, конечного  оптимума линейной функции нет, т.е. F_min= - ¥

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

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

  Однако  только геометрический метод решения  никак не может удовлетворить  ни математиков, ни экономистов. Возможны "технические" погрешности, которые  неизбежно возникают при приближенном построении графиков. Второй недостаток геометрического метода заключается  в том, что многие величины, имеющие  четкий экономический смысл (такие, как остатки ресурсов производства, избыток питательных веществ  и т.п.), не выявляются при геометрическом решении задач. Но самое главное  — геометрический метод неприемлем для решения практических задач. Его можно применить только в  том случае, когда число переменных в стандартной задаче равно двум. Поэтому необходимы аналитические  методы, позволяющие решать задачи линейного программирования с любым  числом переменных и выявить экономический  смысл входящих в них величин. Эти методы будут рассмотрены  в следующих главах.

  Используя геометрическую интерпретацию, найдите  решения задач. 
 
 

Вариант 11.

Принципы  моделирования. 

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

      Необходимым условием моделирования является подобие  объекта и его модели.

      Построенные модели необходимо исследовать и  решить. Но прежде введем некоторые  понятия.

      Операция 

      - всякое мероприятие (система действий), объединенных единым замыслом  и направлением к достижению  какой-либо цели.

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

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

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

      Параметры, совокупность которых образует решение, называется элементами решения.

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

Вариант 12.

Разновидности задач моделирования и подходов к их решению.

Задачи  моделирования делятся на две  категории: прямые и обратные.

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

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

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

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

Их  можно разделить  на:

принятие  решений в условиях определенности - исходные данные - детерминированные; принятие решений в условиях неопределенности - исходные данные - случайные величины.

Классификация задач оптимизации 

А по критерию эффективности:

одноцелевое принятие решений (один критерий эффективности);

многоцелевое  принятие решений  (несколько критериев эффективности).

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

В общем виде обратная детерминированная  задача будет выглядеть  следующим образом.

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

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